Intermediate changes

5 files changed, 118 insertions, 37 deletions

diff --git a/contrib/python/hypothesis/py3/.dist-info/METADATA b/contrib/python/hypothesis/py3/.dist-info/METADATA
index 2e17c15b99..c61fb5cb38 100644
--- a/contrib/python/hypothesis/py3/.dist-info/METADATA
+++ b/contrib/python/hypothesis/py3/.dist-info/METADATA
@@ -1,6 +1,6 @@
 Metadata-Version: 2.1
 Name: hypothesis
-Version: 6.99.8
+Version: 6.99.9
 Summary: A library for property-based testing
 Home-page: https://hypothesis.works
 Author: David R. MacIver and Zac Hatfield-Dodds
diff --git a/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/data.py b/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/data.py
index e29fc553fc..c35b533ecb 100644
--- a/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/data.py
+++ b/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/data.py
@@ -325,6 +325,11 @@ class Example:
         return self.end - self.start
 
     @property
+    def ir_length(self) -> int:
+        """The number of ir nodes in this example."""
+        return self.ir_end - self.ir_start
+
+    @property
     def children(self) -> "List[Example]":
         """The list of all examples with this as a parent, in increasing index
         order."""
@@ -465,7 +470,11 @@ class ExampleRecord:
     def record_ir_draw(self, ir_type, value, *, kwargs, was_forced):
         self.trail.append(IR_NODE_RECORD)
         node = IRNode(
-            ir_type=ir_type, value=value, kwargs=kwargs, was_forced=was_forced
+            ir_type=ir_type,
+            value=value,
+            kwargs=kwargs,
+            was_forced=was_forced,
+            index=len(self.ir_nodes),
         )
         self.ir_nodes.append(node)
 
@@ -950,11 +959,15 @@ class IRNode:
     value: IRType = attr.ib()
     kwargs: IRKWargsType = attr.ib()
     was_forced: bool = attr.ib()
+    index: Optional[int] = attr.ib(default=None)
 
     def copy(self, *, with_value: IRType) -> "IRNode":
         # we may want to allow this combination in the future, but for now it's
         # a footgun.
         assert not self.was_forced, "modifying a forced node doesn't make sense"
+        # explicitly not copying index. node indices are only assigned via
+        # ExampleRecord. This prevents footguns with relying on stale indices
+        # after copying.
         return IRNode(
             ir_type=self.ir_type,
             value=with_value,
@@ -962,6 +975,48 @@ class IRNode:
             was_forced=self.was_forced,
         )
 
+    @property
+    def trivial(self):
+        """
+        A node is trivial if it cannot be simplified any further. This does not
+        mean that modifying a trivial node can't produce simpler test cases when
+        viewing the tree as a whole. Just that when viewing this node in
+        isolation, this is the simplest the node can get.
+        """
+        if self.was_forced:
+            return True
+
+        if self.ir_type == "integer":
+            shrink_towards = self.kwargs["shrink_towards"]
+            min_value = self.kwargs["min_value"]
+            max_value = self.kwargs["max_value"]
+
+            if min_value is not None:
+                shrink_towards = max(min_value, shrink_towards)
+            if max_value is not None:
+                shrink_towards = min(max_value, shrink_towards)
+
+            return self.value == shrink_towards
+        if self.ir_type == "float":
+            # floats shrink "like integers" (for now, anyway), except shrink_towards
+            # is not configurable and is always 0.
+            shrink_towards = 0
+            shrink_towards = max(self.kwargs["min_value"], shrink_towards)
+            shrink_towards = min(self.kwargs["max_value"], shrink_towards)
+
+            return ir_value_equal("float", self.value, shrink_towards)
+        if self.ir_type == "boolean":
+            return self.value is False
+        if self.ir_type == "string":
+            # smallest size and contains only the smallest-in-shrink-order character.
+            minimal_char = self.kwargs["intervals"].char_in_shrink_order(0)
+            return self.value == (minimal_char * self.kwargs["min_size"])
+        if self.ir_type == "bytes":
+            # smallest size and all-zero value.
+            return len(self.value) == self.kwargs["size"] and not any(self.value)
+
+        raise NotImplementedError(f"unhandled ir_type {self.ir_type}")
+
     def __eq__(self, other):
         if not isinstance(other, IRNode):
             return NotImplemented
diff --git a/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/shrinker.py b/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/shrinker.py
index b67242cc78..ce232c67f1 100644
--- a/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/shrinker.py
+++ b/contrib/python/hypothesis/py3/hypothesis/internal/conjecture/shrinker.py
@@ -20,7 +20,13 @@ from hypothesis.internal.conjecture.choicetree import (
     prefix_selection_order,
     random_selection_order,
 )
-from hypothesis.internal.conjecture.data import ConjectureData, ConjectureResult, Status
+from hypothesis.internal.conjecture.data import (
+    ConjectureData,
+    ConjectureResult,
+    Status,
+    bits_to_bytes,
+    ir_value_permitted,
+)
 from hypothesis.internal.conjecture.dfa import ConcreteDFA
 from hypothesis.internal.conjecture.floats import is_simple
 from hypothesis.internal.conjecture.junkdrawer import (
@@ -377,7 +383,6 @@ class Shrinker:
 
     def consider_new_tree(self, tree):
         data = self.engine.ir_tree_to_data(tree)
-
         return self.consider_new_buffer(data.buffer)
 
     def consider_new_buffer(self, buffer):
@@ -825,12 +830,10 @@ class Shrinker:
         )
 
         ls = self.examples_by_label[label]
-
         i = chooser.choose(range(len(ls) - 1))
-
         ancestor = ls[i]
 
-        if i + 1 == len(ls) or ls[i + 1].start >= ancestor.end:
+        if i + 1 == len(ls) or ls[i + 1].ir_start >= ancestor.ir_end:
             return
 
         @self.cached(label, i)
@@ -839,22 +842,22 @@ class Shrinker:
             hi = len(ls)
             while lo + 1 < hi:
                 mid = (lo + hi) // 2
-                if ls[mid].start >= ancestor.end:
+                if ls[mid].ir_start >= ancestor.ir_end:
                     hi = mid
                 else:
                     lo = mid
-            return [t for t in ls[i + 1 : hi] if t.length < ancestor.length]
+            return [t for t in ls[i + 1 : hi] if t.ir_length < ancestor.ir_length]
 
-        descendant = chooser.choose(descendants, lambda ex: ex.length > 0)
+        descendant = chooser.choose(descendants, lambda ex: ex.ir_length > 0)
 
-        assert ancestor.start <= descendant.start
-        assert ancestor.end >= descendant.end
-        assert descendant.length < ancestor.length
+        assert ancestor.ir_start <= descendant.ir_start
+        assert ancestor.ir_end >= descendant.ir_end
+        assert descendant.ir_length < ancestor.ir_length
 
-        self.incorporate_new_buffer(
-            self.buffer[: ancestor.start]
-            + self.buffer[descendant.start : descendant.end]
-            + self.buffer[ancestor.end :]
+        self.consider_new_tree(
+            self.nodes[: ancestor.ir_start]
+            + self.nodes[descendant.ir_start : descendant.ir_end]
+            + self.nodes[ancestor.ir_end :]
         )
 
     def lower_common_block_offset(self):
@@ -1221,7 +1224,6 @@ class Shrinker:
             and not is_simple(node.value),
         )
 
-        i = self.nodes.index(node)
         # the Float shrinker was only built to handle positive floats. We'll
         # shrink the positive portion and reapply the sign after, which is
         # equivalent to this shrinker's previous behavior. We'll want to refactor
@@ -1231,9 +1233,9 @@ class Shrinker:
         Float.shrink(
             abs(node.value),
             lambda val: self.consider_new_tree(
-                self.nodes[:i]
+                self.nodes[: node.index]
                 + [node.copy(with_value=sign * val)]
-                + self.nodes[i + 1 :]
+                + self.nodes[node.index + 1 :]
             ),
             random=self.random,
             node=node,
@@ -1245,32 +1247,56 @@ class Shrinker:
         to exceed some bound, lowering one of them requires raising the
         other. This pass enables that."""
 
-        block = chooser.choose(self.blocks, lambda b: not b.all_zero)
+        node = chooser.choose(
+            self.nodes, lambda node: node.ir_type == "integer" and not node.trivial
+        )
 
-        for j in range(block.index + 1, len(self.blocks)):
-            next_block = self.blocks[j]
-            if next_block.length == block.length:
+        # The preconditions for this pass are that the two integer draws are only
+        # separated by non-integer nodes, and have the same size value in bytes.
+        #
+        # This isn't particularly principled. For instance, this wouldn't reduce
+        # e.g. @given(integers(), integers(), integers()) where the sum property
+        # involves the first and last integers.
+        #
+        # A better approach may be choosing *two* such integer nodes arbitrarily
+        # from the list, instead of conditionally scanning forward.
+
+        for j in range(node.index + 1, len(self.nodes)):
+            next_node = self.nodes[j]
+            if next_node.ir_type == "integer" and bits_to_bytes(
+                node.value.bit_length()
+            ) == bits_to_bytes(next_node.value.bit_length()):
                 break
         else:
             return
 
-        buffer = self.buffer
+        if next_node.was_forced:
+            # avoid modifying a forced node. Note that it's fine for next_node
+            # to be trivial, because we're going to explicitly make it *not*
+            # trivial by adding to its value.
+            return
 
-        m = int_from_bytes(buffer[block.start : block.end])
-        n = int_from_bytes(buffer[next_block.start : next_block.end])
+        m = node.value
+        n = next_node.value
 
         def boost(k):
             if k > m:
                 return False
-            attempt = bytearray(buffer)
-            attempt[block.start : block.end] = int_to_bytes(m - k, block.length)
-            try:
-                attempt[next_block.start : next_block.end] = int_to_bytes(
-                    n + k, next_block.length
-                )
-            except OverflowError:
+
+            node_value = m - k
+            next_node_value = n + k
+            if (not ir_value_permitted(node_value, "integer", node.kwargs)) or (
+                not ir_value_permitted(next_node_value, "integer", next_node.kwargs)
+            ):
                 return False
-            return self.consider_new_buffer(attempt)
+
+            return self.consider_new_tree(
+                self.nodes[: node.index]
+                + [node.copy(with_value=node_value)]
+                + self.nodes[node.index + 1 : next_node.index]
+                + [next_node.copy(with_value=next_node_value)]
+                + self.nodes[next_node.index + 1 :]
+            )
 
         find_integer(boost)
 
diff --git a/contrib/python/hypothesis/py3/hypothesis/version.py b/contrib/python/hypothesis/py3/hypothesis/version.py
index afa2d3040a..670380b619 100644
--- a/contrib/python/hypothesis/py3/hypothesis/version.py
+++ b/contrib/python/hypothesis/py3/hypothesis/version.py
@@ -8,5 +8,5 @@
 # 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/.
 
-__version_info__ = (6, 99, 8)
+__version_info__ = (6, 99, 9)
 __version__ = ".".join(map(str, __version_info__))
diff --git a/contrib/python/hypothesis/py3/ya.make b/contrib/python/hypothesis/py3/ya.make
index 117eaa5eb0..f6d2f61d06 100644
--- a/contrib/python/hypothesis/py3/ya.make
+++ b/contrib/python/hypothesis/py3/ya.make
@@ -2,7 +2,7 @@
 
 PY3_LIBRARY()
 
-VERSION(6.99.8)
+VERSION(6.99.9)
 
 LICENSE(MPL-2.0)