Repository: HypothesisWorks/hypothesis
Pull request: Shrink NaN to canonical form
Closes #4277.

The first issue (`-nan`) is a one-liner, switching from `sign_aware_lte` to `math.copysign` to detect the sign of a choice.

Second issue (`struct.unpack('d', struct.pack('Q', 0xfff8000000000001))[0]`) requires distinguishing NaNs in float shrinking, so that code is reshuffled a bit to separate out the "immutable" value for the shrinker from the "hashable" value for tracking of seen values.

Problem statement:
Shrink NaN to canonical form
```
for s in [0, 2, 4]:
    @given(st.lists(st.integers()|st.floats()))
    @seed(s)
    def sort_is_reversible(l):
        assert sorted(l, reverse=True) == list(reversed(sorted(l)))
    try:
        sort_is_reversible()
    except AssertionError as e:
        print(e.__notes__[0].replace("\n", ""))
```
→
```
Falsifying example: sort_is_reversible(l=[0, -nan],)
Falsifying example: sort_is_reversible(l=[0, nan],)
Falsifying example: sort_is_reversible(l=[0, struct.unpack('d', struct.pack('Q', 0xfff8000000000001))[0]],)
```

Hints from issue discussion:

Commit message: Use constant for SIGNALING_NAN

Patch to review:
diff --git a/hypothesis-python/RELEASE.rst b/hypothesis-python/RELEASE.rst
new file mode 100644
index 0000000000..9c0a8cac20
--- /dev/null
+++ b/hypothesis-python/RELEASE.rst
@@ -0,0 +1,3 @@
+RELEASE_TYPE: patch
+
+Improve shrinking of non-standard NaN float values (:issue:`4277`).
diff --git a/hypothesis-python/src/hypothesis/internal/conjecture/choice.py b/hypothesis-python/src/hypothesis/internal/conjecture/choice.py
index 16db7ca8f2..fe52e1e5fc 100644
--- a/hypothesis-python/src/hypothesis/internal/conjecture/choice.py
+++ b/hypothesis-python/src/hypothesis/internal/conjecture/choice.py
@@ -417,7 +417,7 @@ def choice_to_index(choice: ChoiceT, kwargs: ChoiceKwargsT) -> int:
             to_order=intervals.index_from_char_in_shrink_order,
         )
     elif isinstance(choice, float):
-        sign = int(sign_aware_lte(choice, -0.0))
+        sign = int(math.copysign(1.0, choice) < 0)
         return (sign << 64) | float_to_lex(abs(choice))
     else:
         raise NotImplementedError
diff --git a/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/common.py b/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/common.py
index b0c5ec8694..8290ec6737 100644
--- a/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/common.py
+++ b/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/common.py
@@ -34,7 +34,7 @@ def __init__(
         self.name = name
 
         self.__predicate = predicate
-        self.__seen = set()
+        self.__seen = {self.make_canonical(self.current)}
         self.debugging_enabled = debug
 
     @property
@@ -107,39 +107,46 @@ def run(self):
             self.run_step()
         self.debug("COMPLETE")
 
-    def incorporate(self, value):
+    def consider(self, value):
         """Try using ``value`` as a possible candidate improvement.
 
-        Return True if it works.
+        Return True if self.current is canonically equal to value after the call, either because
+        the value was incorporated as an improvement or because it had that value already.
         """
         value = self.make_immutable(value)
+        self.debug(f"considering {value!r}")
+        canonical = self.make_canonical(value)
+        if canonical == self.make_canonical(self.current):
+            return True
+        if canonical in self.__seen:
+            return False
+        self.__seen.add(canonical)
         self.check_invariants(value)
         if not self.left_is_better(value, self.current):
-            if value != self.current and (value == value):
-                self.debug(f"Rejected {value!r} as worse than {self.current=}")
-            return False
-        if value in self.__seen:
+            self.debug(f"Rejected {value!r} as no better than {self.current=}")
             return False
-        self.__seen.add(value)
         if self.__predicate(value):
             self.debug(f"shrinking to {value!r}")
             self.changes += 1
             self.current = value
             return True
-        return False
+        else:
+            self.debug(f"Rejected {value!r} not satisfying predicate")
+            return False
 
-    def consider(self, value):
-        """Returns True if make_immutable(value) == self.current after calling
-        self.incorporate(value)."""
-        self.debug(f"considering {value}")
-        value = self.make_immutable(value)
-        if value == self.current:
-            return True
-        return self.incorporate(value)
+    def make_canonical(self, value):
+        """Convert immutable value into a canonical and hashable, but not necessarily equal,
+        representation of itself.
+
+        This representation is used only for tracking already-seen values, not passed to the
+        shrinker.
+
+        Defaults to just returning the (immutable) input value.
+        """
+        return value
 
     def make_immutable(self, value):
-        """Convert value into an immutable (and hashable) representation of
-        itself.
+        """Convert value into an immutable representation of itself.
 
         It is these immutable versions that the shrinker will work on.
 
diff --git a/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/floats.py b/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/floats.py
index e2f52a281b..2b61ce3903 100644
--- a/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/floats.py
+++ b/hypothesis-python/src/hypothesis/internal/conjecture/shrinking/floats.py
@@ -9,6 +9,7 @@
 # obtain one at https://mozilla.org/MPL/2.0/.
 
 import math
+import struct
 import sys
 
 from hypothesis.internal.conjecture.floats import float_to_lex
@@ -19,19 +20,19 @@
 
 class Float(Shrinker):
     def setup(self):
-        self.NAN = math.nan
         self.debugging_enabled = True
 
-    def make_immutable(self, f):
-        f = float(f)
+    def make_canonical(self, f):
         if math.isnan(f):
-            # Always use the same NAN so it works properly in self.seen
-            f = self.NAN
+            # Distinguish different NaN bit patterns, while making each equal to itself.
+            # Returning bytes instead of integer (float_to_int) avoids accidental
+            # equality with valid large floats.
+            return struct.pack("d", f)
         return f
 
     def check_invariants(self, value):
-        # We only handle positive floats because we encode the sign separately
-        # anyway.
+        # We only handle positive floats (including NaN) because we encode the sign
+        # separately anyway.
         assert not (value < 0)
 
     def left_is_better(self, left, right):
diff --git a/hypothesis-python/tests/conjecture/test_float_encoding.py b/hypothesis-python/tests/conjecture/test_float_encoding.py
index 8781ad152b..30f41d7fce 100644
--- a/hypothesis-python/tests/conjecture/test_float_encoding.py
+++ b/hypothesis-python/tests/conjecture/test_float_encoding.py
@@ -8,6 +8,7 @@
 # v. 2.0. If a copy of the MPL was not distributed with this file, You can
 # obtain one at https://mozilla.org/MPL/2.0/.
 
+import math
 import sys
 
 import pytest
@@ -16,7 +17,7 @@
 from hypothesis.internal.compat import ceil, extract_bits, floor
 from hypothesis.internal.conjecture import floats as flt
 from hypothesis.internal.conjecture.engine import ConjectureRunner
-from hypothesis.internal.floats import float_to_int
+from hypothesis.internal.floats import SIGNALING_NAN, float_to_int
 
 EXPONENTS = list(range(flt.MAX_EXPONENT + 1))
 assert len(EXPONENTS) == 2**11
@@ -200,3 +201,9 @@ def test_reject_out_of_bounds_floats_while_shrinking():
     kwargs = {"min_value": 103.0}
     g = minimal_from(103.1, lambda x: x >= 100, kwargs=kwargs)
     assert g == 103.0
+
+
+@pytest.mark.parametrize("nan", [-math.nan, SIGNALING_NAN, -SIGNALING_NAN])
+def test_shrinks_to_canonical_nan(nan):
+    shrunk = minimal_from(nan, math.isnan)
+    assert float_to_int(shrunk) == float_to_int(math.nan)
diff --git a/hypothesis-python/tests/cover/test_shrink_budgeting.py b/hypothesis-python/tests/cover/test_shrink_budgeting.py
index 6abdca4132..5664cccaf1 100644
--- a/hypothesis-python/tests/cover/test_shrink_budgeting.py
+++ b/hypothesis-python/tests/cover/test_shrink_budgeting.py
@@ -20,7 +20,7 @@
     [
         (Integer, 2**16),
         (Integer, int(sys.float_info.max)),
-        (Ordering, [[100] * 10]),
+        (Ordering, [(100,) * 10]),
         (Ordering, [i * 100 for i in (range(5))]),
         (Ordering, [i * 100 for i in reversed(range(5))]),
     ],


Code review comments:
diff_hunk: @@ -19,19 +20,19 @@
 
 class Float(Shrinker):
     def setup(self):
-        self.NAN = math.nan
         self.debugging_enabled = True
 
-    def make_immutable(self, f):
-        f = float(f)
+    def make_canonical(self, f):
         if math.isnan(f):
-            # Always use the same NAN so it works properly in self.seen
-            f = self.NAN
+            # Distinguish different NaN bit patterns, while making each equal to itself.
+            # Returning bytes instead of integer (float_to_int) avoids accidental
+            # equality with valid large floats.
+            return struct.pack("d", f)
path: hypothesis-python/src/hypothesis/internal/conjecture/shrinking/floats.py
text: @user1:
I'm surprised we can't use `float_to_int` for a unique key here - did you find two floats with the same `float_to_int` value? that would be bad news for places where we rely on `float_to_int` for equality (see `choice_equal`)

@author:
We could use `float_to_int` unconditionally, but here we're only transforming the nans (for performance), so the int could be compared to a plain float.

@user1:
gotcha. I'd prefer `("nan", float_to_int(f))` or `int_to_bytes(float_to_int(f))` so we don't forget to update this when supporting different float widths (https://github.com/HypothesisWorks/hypothesis/issues/3959).

@user2:
eh, I think that's far enough away and will be enough of a rewrite that I'm not worried, and I like the simplicity of this approach in the meantime.

@author:
I think the suggested tuple is easier to understand the purpose of though, so I'll go with that.