1 """Various utility functions."""
2
3 from collections import namedtuple, Counter
4 from 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)
16 assert _MIN_DIFF_LEN >= 0
17
18 def _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
24 def _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
45 def 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
54 def strclass(cls):
55 return "%s.%s" % (cls.__module__, cls.__qualname__)
56
57 def 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
98 def 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
115 def 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
121 def _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
156 def _count_diff_hashable(actual, expected):
157 'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ'
158 # elements must be hashable
159 s, t = Counter(actual), Counter(expected)
160 result = []
161 for elem, cnt_s in s.items():
162 cnt_t = t.get(elem, 0)
163 if cnt_s != cnt_t:
164 diff = _Mismatch(cnt_s, cnt_t, elem)
165 result.append(diff)
166 for elem, cnt_t in t.items():
167 if elem not in s:
168 diff = _Mismatch(0, cnt_t, elem)
169 result.append(diff)
170 return result