• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1"""Various utility functions."""
2
3from collections import namedtuple, OrderedDict
4from os.path import commonprefix
5
6__unittest = True
7
8_MAX_LENGTH = 80
9_PLACEHOLDER_LEN = 12
10_MIN_BEGIN_LEN = 5
11_MIN_END_LEN = 5
12_MIN_COMMON_LEN = 5
13_MIN_DIFF_LEN = _MAX_LENGTH - \
14               (_MIN_BEGIN_LEN + _PLACEHOLDER_LEN + _MIN_COMMON_LEN +
15                _PLACEHOLDER_LEN + _MIN_END_LEN)
16assert _MIN_DIFF_LEN >= 0
17
18def _shorten(s, prefixlen, suffixlen):
19    skip = len(s) - prefixlen - suffixlen
20    if skip > _PLACEHOLDER_LEN:
21        s = '%s[%d chars]%s' % (s[:prefixlen], skip, s[len(s) - suffixlen:])
22    return s
23
24def _common_shorten_repr(*args):
25    args = tuple(map(safe_repr, args))
26    maxlen = max(map(len, args))
27    if maxlen <= _MAX_LENGTH:
28        return args
29
30    prefix = commonprefix(args)
31    prefixlen = len(prefix)
32
33    common_len = _MAX_LENGTH - \
34                 (maxlen - prefixlen + _MIN_BEGIN_LEN + _PLACEHOLDER_LEN)
35    if common_len > _MIN_COMMON_LEN:
36        assert _MIN_BEGIN_LEN + _PLACEHOLDER_LEN + _MIN_COMMON_LEN + \
37               (maxlen - prefixlen) < _MAX_LENGTH
38        prefix = _shorten(prefix, _MIN_BEGIN_LEN, common_len)
39        return tuple(prefix + s[prefixlen:] for s in args)
40
41    prefix = _shorten(prefix, _MIN_BEGIN_LEN, _MIN_COMMON_LEN)
42    return tuple(prefix + _shorten(s[prefixlen:], _MIN_DIFF_LEN, _MIN_END_LEN)
43                 for s in args)
44
45def safe_repr(obj, short=False):
46    try:
47        result = repr(obj)
48    except Exception:
49        result = object.__repr__(obj)
50    if not short or len(result) < _MAX_LENGTH:
51        return result
52    return result[:_MAX_LENGTH] + ' [truncated]...'
53
54def strclass(cls):
55    return "%s.%s" % (cls.__module__, cls.__qualname__)
56
57def sorted_list_difference(expected, actual):
58    """Finds elements in only one or the other of two, sorted input lists.
59
60    Returns a two-element tuple of lists.    The first list contains those
61    elements in the "expected" list but not in the "actual" list, and the
62    second contains those elements in the "actual" list but not in the
63    "expected" list.    Duplicate elements in either input list are ignored.
64    """
65    i = j = 0
66    missing = []
67    unexpected = []
68    while True:
69        try:
70            e = expected[i]
71            a = actual[j]
72            if e < a:
73                missing.append(e)
74                i += 1
75                while expected[i] == e:
76                    i += 1
77            elif e > a:
78                unexpected.append(a)
79                j += 1
80                while actual[j] == a:
81                    j += 1
82            else:
83                i += 1
84                try:
85                    while expected[i] == e:
86                        i += 1
87                finally:
88                    j += 1
89                    while actual[j] == a:
90                        j += 1
91        except IndexError:
92            missing.extend(expected[i:])
93            unexpected.extend(actual[j:])
94            break
95    return missing, unexpected
96
97
98def unorderable_list_difference(expected, actual):
99    """Same behavior as sorted_list_difference but
100    for lists of unorderable items (like dicts).
101
102    As it does a linear search per item (remove) it
103    has O(n*n) performance."""
104    missing = []
105    while expected:
106        item = expected.pop()
107        try:
108            actual.remove(item)
109        except ValueError:
110            missing.append(item)
111
112    # anything left in actual is unexpected
113    return missing, actual
114
115def three_way_cmp(x, y):
116    """Return -1 if x < y, 0 if x == y and 1 if x > y"""
117    return (x > y) - (x < y)
118
119_Mismatch = namedtuple('Mismatch', 'actual expected value')
120
121def _count_diff_all_purpose(actual, expected):
122    'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ'
123    # elements need not be hashable
124    s, t = list(actual), list(expected)
125    m, n = len(s), len(t)
126    NULL = object()
127    result = []
128    for i, elem in enumerate(s):
129        if elem is NULL:
130            continue
131        cnt_s = cnt_t = 0
132        for j in range(i, m):
133            if s[j] == elem:
134                cnt_s += 1
135                s[j] = NULL
136        for j, other_elem in enumerate(t):
137            if other_elem == elem:
138                cnt_t += 1
139                t[j] = NULL
140        if cnt_s != cnt_t:
141            diff = _Mismatch(cnt_s, cnt_t, elem)
142            result.append(diff)
143
144    for i, elem in enumerate(t):
145        if elem is NULL:
146            continue
147        cnt_t = 0
148        for j in range(i, n):
149            if t[j] == elem:
150                cnt_t += 1
151                t[j] = NULL
152        diff = _Mismatch(0, cnt_t, elem)
153        result.append(diff)
154    return result
155
156def _ordered_count(iterable):
157    'Return dict of element counts, in the order they were first seen'
158    c = OrderedDict()
159    for elem in iterable:
160        c[elem] = c.get(elem, 0) + 1
161    return c
162
163def _count_diff_hashable(actual, expected):
164    'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ'
165    # elements must be hashable
166    s, t = _ordered_count(actual), _ordered_count(expected)
167    result = []
168    for elem, cnt_s in s.items():
169        cnt_t = t.get(elem, 0)
170        if cnt_s != cnt_t:
171            diff = _Mismatch(cnt_s, cnt_t, elem)
172            result.append(diff)
173    for elem, cnt_t in t.items():
174        if elem not in s:
175            diff = _Mismatch(0, cnt_t, elem)
176            result.append(diff)
177    return result
178