Merge from 3.1: Issue #13703: add a way to randomize the hash values of basic types (str, bytes, datetime)

in order to make algorithmic complexity attacks on (e.g.) web apps much more complicated.

The environment variable PYTHONHASHSEED and the new command line flag -R control this
behavior.

1 files changed, 140 insertions, 0 deletions

diff --git a/Lib/unittest/util.py b/Lib/unittest/util.py
new file mode 100644
index 0000000000..ccdf0b81fa
--- /dev/null
+++ b/Lib/unittest/util.py
@@ -0,0 +1,140 @@
+"""Various utility functions."""
+
+from collections import namedtuple, OrderedDict
+
+__unittest = True
+
+_MAX_LENGTH = 80
+def safe_repr(obj, short=False):
+    try:
+        result = repr(obj)
+    except Exception:
+        result = object.__repr__(obj)
+    if not short or len(result) < _MAX_LENGTH:
+        return result
+    return result[:_MAX_LENGTH] + ' [truncated]...'
+
+def strclass(cls):
+    return "%s.%s" % (cls.__module__, cls.__name__)
+
+def sorted_list_difference(expected, actual):
+    """Finds elements in only one or the other of two, sorted input lists.
+
+    Returns a two-element tuple of lists.    The first list contains those
+    elements in the "expected" list but not in the "actual" list, and the
+    second contains those elements in the "actual" list but not in the
+    "expected" list.    Duplicate elements in either input list are ignored.
+    """
+    i = j = 0
+    missing = []
+    unexpected = []
+    while True:
+        try:
+            e = expected[i]
+            a = actual[j]
+            if e < a:
+                missing.append(e)
+                i += 1
+                while expected[i] == e:
+                    i += 1
+            elif e > a:
+                unexpected.append(a)
+                j += 1
+                while actual[j] == a:
+                    j += 1
+            else:
+                i += 1
+                try:
+                    while expected[i] == e:
+                        i += 1
+                finally:
+                    j += 1
+                    while actual[j] == a:
+                        j += 1
+        except IndexError:
+            missing.extend(expected[i:])
+            unexpected.extend(actual[j:])
+            break
+    return missing, unexpected
+
+
+def unorderable_list_difference(expected, actual):
+    """Same behavior as sorted_list_difference but
+    for lists of unorderable items (like dicts).
+
+    As it does a linear search per item (remove) it
+    has O(n*n) performance."""
+    missing = []
+    while expected:
+        item = expected.pop()
+        try:
+            actual.remove(item)
+        except ValueError:
+            missing.append(item)
+
+    # anything left in actual is unexpected
+    return missing, actual
+
+def three_way_cmp(x, y):
+    """Return -1 if x < y, 0 if x == y and 1 if x > y"""
+    return (x > y) - (x < y)
+
+_Mismatch = namedtuple('Mismatch', 'actual expected value')
+
+def _count_diff_all_purpose(actual, expected):
+    'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ'
+    # elements need not be hashable
+    s, t = list(actual), list(expected)
+    m, n = len(s), len(t)
+    NULL = object()
+    result = []
+    for i, elem in enumerate(s):
+        if elem is NULL:
+            continue
+        cnt_s = cnt_t = 0
+        for j in range(i, m):
+            if s[j] == elem:
+                cnt_s += 1
+                s[j] = NULL
+        for j, other_elem in enumerate(t):
+            if other_elem == elem:
+                cnt_t += 1
+                t[j] = NULL
+        if cnt_s != cnt_t:
+            diff = _Mismatch(cnt_s, cnt_t, elem)
+            result.append(diff)
+
+    for i, elem in enumerate(t):
+        if elem is NULL:
+            continue
+        cnt_t = 0
+        for j in range(i, n):
+            if t[j] == elem:
+                cnt_t += 1
+                t[j] = NULL
+        diff = _Mismatch(0, cnt_t, elem)
+        result.append(diff)
+    return result
+
+def _ordered_count(iterable):
+    'Return dict of element counts, in the order they were first seen'
+    c = OrderedDict()
+    for elem in iterable:
+        c[elem] = c.get(elem, 0) + 1
+    return c
+
+def _count_diff_hashable(actual, expected):
+    'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ'
+    # elements must be hashable
+    s, t = _ordered_count(actual), _ordered_count(expected)
+    result = []
+    for elem, cnt_s in s.items():
+        cnt_t = t.get(elem, 0)
+        if cnt_s != cnt_t:
+            diff = _Mismatch(cnt_s, cnt_t, elem)
+            result.append(diff)
+    for elem, cnt_t in t.items():
+        if elem not in s:
+            diff = _Mismatch(0, cnt_t, elem)
+            result.append(diff)
+    return result