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