3 files changed, 246 insertions, 0 deletions

diff --git a/meta/recipes-devtools/python/python3-hypothesis/run-ptest b/meta/recipes-devtools/python/python3-hypothesis/run-ptest
new file mode 100644
index 0000000000..8d44d7c49a
--- /dev/null
+++ b/meta/recipes-devtools/python/python3-hypothesis/run-ptest
@@ -0,0 +1,10 @@
+#!/bin/sh
+
+# Upstream "fast" tests take about 5 minutes and currently do not run cleanly
+# (tests/cover and tests/pytest)
+# https://github.com/HypothesisWorks/hypothesis/tree/master/hypothesis-python/tests
+# https://github.com/HypothesisWorks/hypothesis/blob/master/hypothesis-python/scripts/basic-test.sh#L18
+#
+# Instead we run two test suites imported from examples/
+
+pytest -o log_cli=true -o log_cli_level=INFO | sed -e 's/\[...%\]//g'| sed -e 's/PASSED/PASS/g'| sed -e 's/FAILED/FAIL/g'|sed -e 's/SKIPPED/SKIP/g'| awk '{if ($NF=="PASS" || $NF=="FAIL" || $NF=="SKIP" || $NF=="XFAIL" || $NF=="XPASS"){printf "%s: %s\n", $NF, $0}else{print}}'| awk '{if ($NF=="PASS" || $NF=="FAIL" || $NF=="SKIP" || $NF=="XFAIL" || $NF=="XPASS") {$NF="";print $0}else{print}}'
diff --git a/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py b/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py
new file mode 100644
index 0000000000..21267c4ac2
--- /dev/null
+++ b/meta/recipes-devtools/python/python3-hypothesis/test_binary_search.py
@@ -0,0 +1,135 @@
+# This file is part of Hypothesis, which may be found at
+# https://github.com/HypothesisWorks/hypothesis/
+#
+# Most of this work is copyright (C) 2013-2021 David R. MacIver
+# (david@drmaciver.com), but it contains contributions by others. See
+# CONTRIBUTING.rst for a full list of people who may hold copyright, and
+# consult the git log if you need to determine who owns an individual
+# contribution.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public License,
+# 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/.
+#
+# END HEADER
+#
+# SPDX-License-Identifier: MPL-2.0
+
+"""This file demonstrates testing a binary search.
+
+It's a useful example because the result of the binary search is so clearly
+determined by the invariants it must satisfy, so we can simply test for those
+invariants.
+
+It also demonstrates the useful testing technique of testing how the answer
+should change (or not) in response to movements in the underlying data.
+"""
+
+from hypothesis import given, strategies as st
+
+
+def binary_search(ls, v):
+    """Take a list ls and a value v such that ls is sorted and v is comparable
+    with the elements of ls.
+
+    Return an index i such that 0 <= i <= len(v) with the properties:
+
+    1. ls.insert(i, v) is sorted
+    2. ls.insert(j, v) is not sorted for j < i
+    """
+    # Without this check we will get an index error on the next line when the
+    # list is empty.
+    if not ls:
+        return 0
+
+    # Without this check we will miss the case where the insertion point should
+    # be zero: The invariant we maintain in the next section is that lo is
+    # always strictly lower than the insertion point.
+    if v <= ls[0]:
+        return 0
+
+    # Invariant: There is no insertion point i with i <= lo
+    lo = 0
+
+    # Invariant: There is an insertion point i with i <= hi
+    hi = len(ls)
+    while lo + 1 < hi:
+        mid = (lo + hi) // 2
+        if v > ls[mid]:
+            # Inserting v anywhere below mid would result in an unsorted list
+            # because it's > the value at mid. Therefore mid is a valid new lo
+            lo = mid
+        # Uncommenting the following lines will cause this to return a valid
+        # insertion point which is not always minimal.
+        # elif v == ls[mid]:
+        #   return mid
+        else:
+            # Either v == ls[mid] in which case mid is a valid insertion point
+            # or v < ls[mid], in which case all valid insertion points must be
+            # < hi. Either way, mid is a valid new hi.
+            hi = mid
+    assert lo + 1 == hi
+    # We now know that there is a valid insertion point <= hi and there is no
+    # valid insertion point < hi because hi - 1 is lo. Therefore hi is the
+    # answer we were seeking
+    return hi
+
+
+def is_sorted(ls):
+    """Is this list sorted?"""
+    for i in range(len(ls) - 1):
+        if ls[i] > ls[i + 1]:
+            return False
+    return True
+
+
+Values = st.integers()
+
+# We generate arbitrary lists and turn this into generating sorting lists
+# by just sorting them.
+SortedLists = st.lists(Values).map(sorted)
+
+# We could also do it this way, but that would be a bad idea:
+# SortedLists = st.lists(Values).filter(is_sorted)
+# The problem is that Hypothesis will only generate long sorted lists with very
+# low probability, so we are much better off post-processing values into the
+# form we want than filtering them out.
+
+
+@given(ls=SortedLists, v=Values)
+def test_insert_is_sorted(ls, v):
+    """We test the first invariant: binary_search should return an index such
+    that inserting the value provided at that index would result in a sorted
+    set."""
+    ls.insert(binary_search(ls, v), v)
+    assert is_sorted(ls)
+
+
+@given(ls=SortedLists, v=Values)
+def test_is_minimal(ls, v):
+    """We test the second invariant: binary_search should return an index such
+    that no smaller index is a valid insertion point for v."""
+    for i in range(binary_search(ls, v)):
+        ls2 = list(ls)
+        ls2.insert(i, v)
+        assert not is_sorted(ls2)
+
+
+@given(ls=SortedLists, v=Values)
+def test_inserts_into_same_place_twice(ls, v):
+    """In this we test a *consequence* of the second invariant: When we insert
+    a value into a list twice, the insertion point should be the same both
+    times. This is because we know that v is > the previous element and == the
+    next element.
+
+    In theory if the former passes, this should always pass. In practice,
+    failures are detected by this test with much higher probability because it
+    deliberately puts the data into a shape that is likely to trigger a
+    failure.
+
+    This is an instance of a good general category of test: Testing how the
+    function moves in responses to changes in the underlying data.
+    """
+    i = binary_search(ls, v)
+    ls.insert(i, v)
+    assert binary_search(ls, v) == i
diff --git a/meta/recipes-devtools/python/python3-hypothesis/test_rle.py b/meta/recipes-devtools/python/python3-hypothesis/test_rle.py
new file mode 100644
index 0000000000..4d618865ac
--- /dev/null
+++ b/meta/recipes-devtools/python/python3-hypothesis/test_rle.py
@@ -0,0 +1,101 @@
+# This file is part of Hypothesis, which may be found at
+# https://github.com/HypothesisWorks/hypothesis/
+#
+# Most of this work is copyright (C) 2013-2021 David R. MacIver
+# (david@drmaciver.com), but it contains contributions by others. See
+# CONTRIBUTING.rst for a full list of people who may hold copyright, and
+# consult the git log if you need to determine who owns an individual
+# contribution.
+#
+# This Source Code Form is subject to the terms of the Mozilla Public License,
+# 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/.
+#
+# END HEADER
+#
+# SPDX-License-Identifier: MPL-2.0
+
+"""This example demonstrates testing a run length encoding scheme. That is, we
+take a sequence and represent it by a shorter sequence where each 'run' of
+consecutive equal elements is represented as a single element plus a count. So
+e.g.
+
+[1, 1, 1, 1, 2, 1] is represented as [[1, 4], [2, 1], [1, 1]]
+
+This demonstrates the useful decode(encode(x)) == x invariant that is often
+a fruitful source of testing with Hypothesis.
+
+It also has an example of testing invariants in response to changes in the
+underlying data.
+"""
+
+from hypothesis import assume, given, strategies as st
+
+
+def run_length_encode(seq):
+    """Encode a sequence as a new run-length encoded sequence."""
+    if not seq:
+        return []
+    # By starting off the count at zero we simplify the iteration logic
+    # slightly.
+    result = [[seq[0], 0]]
+    for s in seq:
+        if (
+            # If you uncomment this line this branch will be skipped and we'll
+            # always append a new run of length 1. Note which tests fail.
+            # False and
+            s
+            == result[-1][0]
+            # Try uncommenting this line and see what problems occur:
+            # and result[-1][-1] < 2
+        ):
+            result[-1][1] += 1
+        else:
+            result.append([s, 1])
+    return result
+
+
+def run_length_decode(seq):
+    """Take a previously encoded sequence and reconstruct the original from
+    it."""
+    result = []
+    for s, i in seq:
+        for _ in range(i):
+            result.append(s)
+    return result
+
+
+# We use lists of a type that should have a relatively high duplication rate,
+# otherwise we'd almost never get any runs.
+Lists = st.lists(st.integers(0, 10))
+
+
+@given(Lists)
+def test_decodes_to_starting_sequence(ls):
+    """If we encode a sequence and then decode the result, we should get the
+    original sequence back.
+
+    Otherwise we've done something very wrong.
+    """
+    assert run_length_decode(run_length_encode(ls)) == ls
+
+
+@given(Lists, st.data())
+def test_duplicating_an_element_does_not_increase_length(ls, data):
+    """The previous test could be passed by simply returning the input sequence
+    so we need something that tests the compression property of our encoding.
+
+    In this test we deliberately introduce or extend a run and assert
+    that this does not increase the length of our encoding, because they
+    should be part of the same run in the final result.
+    """
+    # We use assume to get a valid index into the list. We could also have used
+    # e.g. flatmap, but this is relatively straightforward and will tend to
+    # perform better.
+    assume(ls)
+    i = data.draw(st.integers(0, len(ls) - 1))
+    ls2 = list(ls)
+    # duplicating the value at i right next to it guarantees they are part of
+    # the same run in the resulting compression.
+    ls2.insert(i, ls2[i])
+    assert len(run_length_encode(ls2)) == len(run_length_encode(ls))