jpayne@68: """Various utility functions.""" jpayne@68: jpayne@68: from collections import namedtuple, Counter jpayne@68: from os.path import commonprefix jpayne@68: jpayne@68: __unittest = True jpayne@68: jpayne@68: _MAX_LENGTH = 80 jpayne@68: _PLACEHOLDER_LEN = 12 jpayne@68: _MIN_BEGIN_LEN = 5 jpayne@68: _MIN_END_LEN = 5 jpayne@68: _MIN_COMMON_LEN = 5 jpayne@68: _MIN_DIFF_LEN = _MAX_LENGTH - \ jpayne@68: (_MIN_BEGIN_LEN + _PLACEHOLDER_LEN + _MIN_COMMON_LEN + jpayne@68: _PLACEHOLDER_LEN + _MIN_END_LEN) jpayne@68: assert _MIN_DIFF_LEN >= 0 jpayne@68: jpayne@68: def _shorten(s, prefixlen, suffixlen): jpayne@68: skip = len(s) - prefixlen - suffixlen jpayne@68: if skip > _PLACEHOLDER_LEN: jpayne@68: s = '%s[%d chars]%s' % (s[:prefixlen], skip, s[len(s) - suffixlen:]) jpayne@68: return s jpayne@68: jpayne@68: def _common_shorten_repr(*args): jpayne@68: args = tuple(map(safe_repr, args)) jpayne@68: maxlen = max(map(len, args)) jpayne@68: if maxlen <= _MAX_LENGTH: jpayne@68: return args jpayne@68: jpayne@68: prefix = commonprefix(args) jpayne@68: prefixlen = len(prefix) jpayne@68: jpayne@68: common_len = _MAX_LENGTH - \ jpayne@68: (maxlen - prefixlen + _MIN_BEGIN_LEN + _PLACEHOLDER_LEN) jpayne@68: if common_len > _MIN_COMMON_LEN: jpayne@68: assert _MIN_BEGIN_LEN + _PLACEHOLDER_LEN + _MIN_COMMON_LEN + \ jpayne@68: (maxlen - prefixlen) < _MAX_LENGTH jpayne@68: prefix = _shorten(prefix, _MIN_BEGIN_LEN, common_len) jpayne@68: return tuple(prefix + s[prefixlen:] for s in args) jpayne@68: jpayne@68: prefix = _shorten(prefix, _MIN_BEGIN_LEN, _MIN_COMMON_LEN) jpayne@68: return tuple(prefix + _shorten(s[prefixlen:], _MIN_DIFF_LEN, _MIN_END_LEN) jpayne@68: for s in args) jpayne@68: jpayne@68: def safe_repr(obj, short=False): jpayne@68: try: jpayne@68: result = repr(obj) jpayne@68: except Exception: jpayne@68: result = object.__repr__(obj) jpayne@68: if not short or len(result) < _MAX_LENGTH: jpayne@68: return result jpayne@68: return result[:_MAX_LENGTH] + ' [truncated]...' jpayne@68: jpayne@68: def strclass(cls): jpayne@68: return "%s.%s" % (cls.__module__, cls.__qualname__) jpayne@68: jpayne@68: def sorted_list_difference(expected, actual): jpayne@68: """Finds elements in only one or the other of two, sorted input lists. jpayne@68: jpayne@68: Returns a two-element tuple of lists. The first list contains those jpayne@68: elements in the "expected" list but not in the "actual" list, and the jpayne@68: second contains those elements in the "actual" list but not in the jpayne@68: "expected" list. Duplicate elements in either input list are ignored. jpayne@68: """ jpayne@68: i = j = 0 jpayne@68: missing = [] jpayne@68: unexpected = [] jpayne@68: while True: jpayne@68: try: jpayne@68: e = expected[i] jpayne@68: a = actual[j] jpayne@68: if e < a: jpayne@68: missing.append(e) jpayne@68: i += 1 jpayne@68: while expected[i] == e: jpayne@68: i += 1 jpayne@68: elif e > a: jpayne@68: unexpected.append(a) jpayne@68: j += 1 jpayne@68: while actual[j] == a: jpayne@68: j += 1 jpayne@68: else: jpayne@68: i += 1 jpayne@68: try: jpayne@68: while expected[i] == e: jpayne@68: i += 1 jpayne@68: finally: jpayne@68: j += 1 jpayne@68: while actual[j] == a: jpayne@68: j += 1 jpayne@68: except IndexError: jpayne@68: missing.extend(expected[i:]) jpayne@68: unexpected.extend(actual[j:]) jpayne@68: break jpayne@68: return missing, unexpected jpayne@68: jpayne@68: jpayne@68: def unorderable_list_difference(expected, actual): jpayne@68: """Same behavior as sorted_list_difference but jpayne@68: for lists of unorderable items (like dicts). jpayne@68: jpayne@68: As it does a linear search per item (remove) it jpayne@68: has O(n*n) performance.""" jpayne@68: missing = [] jpayne@68: while expected: jpayne@68: item = expected.pop() jpayne@68: try: jpayne@68: actual.remove(item) jpayne@68: except ValueError: jpayne@68: missing.append(item) jpayne@68: jpayne@68: # anything left in actual is unexpected jpayne@68: return missing, actual jpayne@68: jpayne@68: def three_way_cmp(x, y): jpayne@68: """Return -1 if x < y, 0 if x == y and 1 if x > y""" jpayne@68: return (x > y) - (x < y) jpayne@68: jpayne@68: _Mismatch = namedtuple('Mismatch', 'actual expected value') jpayne@68: jpayne@68: def _count_diff_all_purpose(actual, expected): jpayne@68: 'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ' jpayne@68: # elements need not be hashable jpayne@68: s, t = list(actual), list(expected) jpayne@68: m, n = len(s), len(t) jpayne@68: NULL = object() jpayne@68: result = [] jpayne@68: for i, elem in enumerate(s): jpayne@68: if elem is NULL: jpayne@68: continue jpayne@68: cnt_s = cnt_t = 0 jpayne@68: for j in range(i, m): jpayne@68: if s[j] == elem: jpayne@68: cnt_s += 1 jpayne@68: s[j] = NULL jpayne@68: for j, other_elem in enumerate(t): jpayne@68: if other_elem == elem: jpayne@68: cnt_t += 1 jpayne@68: t[j] = NULL jpayne@68: if cnt_s != cnt_t: jpayne@68: diff = _Mismatch(cnt_s, cnt_t, elem) jpayne@68: result.append(diff) jpayne@68: jpayne@68: for i, elem in enumerate(t): jpayne@68: if elem is NULL: jpayne@68: continue jpayne@68: cnt_t = 0 jpayne@68: for j in range(i, n): jpayne@68: if t[j] == elem: jpayne@68: cnt_t += 1 jpayne@68: t[j] = NULL jpayne@68: diff = _Mismatch(0, cnt_t, elem) jpayne@68: result.append(diff) jpayne@68: return result jpayne@68: jpayne@68: def _count_diff_hashable(actual, expected): jpayne@68: 'Returns list of (cnt_act, cnt_exp, elem) triples where the counts differ' jpayne@68: # elements must be hashable jpayne@68: s, t = Counter(actual), Counter(expected) jpayne@68: result = [] jpayne@68: for elem, cnt_s in s.items(): jpayne@68: cnt_t = t.get(elem, 0) jpayne@68: if cnt_s != cnt_t: jpayne@68: diff = _Mismatch(cnt_s, cnt_t, elem) jpayne@68: result.append(diff) jpayne@68: for elem, cnt_t in t.items(): jpayne@68: if elem not in s: jpayne@68: diff = _Mismatch(0, cnt_t, elem) jpayne@68: result.append(diff) jpayne@68: return result