# Various approaches to a "safe" repr that never generates too much text.
# Demonstrates various approaches to laziness in a Python setting.
# In order to be more comprehensible, doesn't cover every Python type,
# leaving out new-style classes in particular; and it doesn't even try
# to be object-oriented.

# I want to emphasize that this code is not part of any production
# code, and several of the implementations use a number of techniques
# that make it unnecessarily hard to understand.  There may be places
# where these techniques are called for, but they should be used very
# sparingly!

# (If you're programming in Haskell, you're probably using these
# techniques without even knowing it.  They cause less trouble in
# Haskell due to being implicit in the language.)

# I am writing this warning because in my early days as a programmer,
# I was enthusiastic about learning advanced new algorithms and ways
# of structuring programs, and I would often use them in contexts
# where they weren't really helpful.  In this case, the entire point
# of this module is to demonstrate different approaches to structuring
# a problem and understand their strengths and weaknesses; most
# programs have some more practical purpose that includes
# maintainability, which conflicts with complexity and unfamiliar
# program structures.

# If you need something like this module in Python in real life, you
# might try the TextRepr class inside pydoc.  It works reasonably well
# for most things, even though it's not too hard to get it to produce
# uselessly voluminous output:
# >>> yy = []
# >>> for ii in range(4): yy = [yy] * 20
# ... 
# >>> xx = pydoc.TextRepr().repr(yy)
# Or take several hours to run; just change the 4 to a larger number,
# such as 7.

import types

class UnhandledType(Exception): pass

### Dumb simple version: generate whole thing, then truncate it.  22 lines.
# Doesn't "work" in the sense of "never generating too much text", and
# it's trivial to make it painfully slow; for example:
# >>> x = 'x' * 10485760
# >>> for ii in range(100): x = [x]
# ... 
# >>> safe_repr.safe_repr_1(x, 200)
# It takes a few seconds to generate that result, as does repr(x)[:200].
# All the other implementations (except for safe_repr_2, which doesn't handle
# strings) generate it instantly.

def _safe_repr_1(val):
    if isinstance(val, types.ListType):
        return '[%s]' % ', '.join(map(_safe_repr_1, val))
    elif isinstance(val, types.TupleType):
        return '(%s)' % ', '.join(map(_safe_repr_1, val))
    elif isinstance(val, types.IntType):
        return '%d' % val
    elif isinstance(val, types.DictType):
        return '{%s}' % ', '.join(['%s: %s' % (_safe_repr_1(k), _safe_repr_1(v))
                                   for k, v in val.items()])
    elif isinstance(val, types.InstanceType):
        # note that this is very different behavior from the standard
        # Python repr!
        return '%s %s' % (val.__class__.__name__, _safe_repr_1(val.__dict__))
    elif isinstance(val, types.StringType):
        return repr(val)  # I'm not going to bother writing out how that works
        raise UnhandledType(val)

def safe_repr_1(val, length):
    "A dumb version that generates it all, then truncates.  For comparison."
    return _safe_repr_1(val)[:length]

### Badly programmed version: never append more than you
# need to.  24 lines, incomplete.

def safe_repr_2(val, length):
    """A partial version that never appends more than it needs to.  
    Too painful to complete."""
    rv = []
    if isinstance(val, types.ListType):
        if length > 0:
            length -= 1
        for ii in range(len(val)):
            item = val[ii]
            if length <= 0: break
            rv.append(safe_repr_2(item, length))
            length -= len(rv[-1])
            if ii < len(val) - 1:
                rv.append(', '[:length])
                length -= len(rv[-1])
        if length > 0:
            length -= 1
    elif isinstance(val, types.IntType):
        rv.append(('%d' % val)[:length])
        raise UnhandledType(val)
    return ''.join(rv)

### Refactored version: never append more than you need to, and use an
# exception to quit when you've generated enough.  54 lines.

def _safe_repr_3_items(xform, items, buf):
    for ii in range(len(items)):
        xform(items[ii], buf)
        if ii < len(items) - 1: buf.append(', ')

def _safe_repr_3_dict_item((k, v), buf):
    _safe_repr_3(k, buf)
    buf.append(': ')
    _safe_repr_3(v, buf)

def _safe_repr_3(val, buf):
    if isinstance(val, types.ListType):
        _safe_repr_3_items(_safe_repr_3, val, buf)
    elif isinstance(val, types.TupleType):
        _safe_repr_3_items(_safe_repr_3, val, buf)
    elif isinstance(val, types.IntType):
        buf.append('%d' % val)
    elif isinstance(val, types.DictType):
        _safe_repr_3_items(_safe_repr_3_dict_item, val.items(), buf)
    elif isinstance(val, types.InstanceType):
        buf.append(val.__class__.__name__ + ' ')
        _safe_repr_3(val.__dict__, buf)
    elif isinstance(val, types.StringType):
        raise UnhandledType(val)

class BufferFull(Exception): pass
class Buf:
    def __init__(self, maxlen):
        self.maxlen = maxlen
        self.buf = []
        self.curlen = 0
    def append(self, astr):
        astr = astr[:self.maxlen - self.curlen]
        self.curlen += len(astr)
        if self.curlen == self.maxlen:
            raise BufferFull()
    def contents(self):
        return ''.join(self.buf)

def safe_repr_3(val, length):
    "A version that uses an exception to break out of recursion."
    buf = Buf(length)
    try: _safe_repr_3(val, buf)
    except BufferFull: pass
    return buf.contents()

### Recursive Generator Version, in which we simply stop iterating
# when we have enough.  49 lines.

# This one is able to handle deeply nested data structures, as long as
# you don't ask it to traverse the whole thing; on my Python, that
# means you're safe as long as you don't want more than 499
# characters.

def _safe_repr_4_items(xform, items):
    for ii in range(len(items)):
        for item in xform(items[ii]): yield item
        if ii < len(items) - 1: yield (', ')

def _safe_repr_4_dict_item((k, v)):
    for item in _safe_repr_4(k): yield item
    yield ': '
    for item in _safe_repr_4(v): yield item

def _safe_repr_4(val):
    if isinstance(val, types.ListType):
        yield '['
        for item in _safe_repr_4_items(_safe_repr_4, val): yield item
        yield ']'
    elif isinstance(val, types.TupleType):
        yield '('
        for item in _safe_repr_4_items(_safe_repr_4, val): yield item
        yield ')'
    elif isinstance(val, types.IntType):
        yield '%d' % val
    elif isinstance(val, types.DictType):
        yield '{'
        for item in _safe_repr_4_items(_safe_repr_4_dict_item, val.items()):
            yield item
        yield '}'
    elif isinstance(val, types.InstanceType):
        yield val.__class__.__name__ + ' '
        for item in _safe_repr_4(val.__dict__): yield item
    elif isinstance(val, types.StringType):
        # This time I will bother to write it out.
        yield "'"
        for each_char in val:
            if each_char == '\\': yield '\\\\'
            elif each_char == "'": yield "\\'"
            else: yield each_char
        yield "'"
        raise UnhandledType(val)

def safe_repr_4(val, length):
    "A version using recursive generators."
    rv = []
    for chunk in _safe_repr_4(val):
        chunk = chunk[:length]
        length -= len(chunk)
        if length == 0: break
    return ''.join(rv)

### Stream version without generators.  64 lines, plus 11 lines of streams.
# Here we see how we could do the same thing more painfully in a
# language with closures but without generators.  Surprisingly, this
# is only about 20% more code, if you discount the first four
# functions whose sole reason for being is to manipulate streams.
# However, it did have several bugs in it at first, so I think it's
# clearly harder to understand.

# At present, it dies with a stack overflow on deeply nested data
# structures, even when it shouldn't have to be traversing all the
# levels in order to produce the requested number of characters.  In
# that sense, it's "more eager" and "less lazy" than the generator
# version.  It's possible to make it lazier to solve that problem, but
# I haven't figured out how yet.

def stream_append(a, b):
    afirst, arest = a
    if afirst is None: return b
    return (afirst, lambda: stream_append(arest(), b))
empty_stream = (None, None)
def one_item_stream(x): return (x, lambda: empty_stream)
def stream_append_n(streams):
    rv = empty_stream
    for stream in streams: rv = stream_append(stream, rv)
    return rv

def _safe_repr_5_map(xform, val, ii):
    if ii == len(val): return empty_stream
        return (xform(val[ii]), lambda: _safe_repr_5_map(xform, val, ii+1))

def _safe_repr_5_items(xform, val, ii):
    if ii == len(val): return empty_stream
    elif ii == len(val) - 1: return xform(val[ii])
        # we explicitly cons up the second stream here to maintain laziness
        # in case there are a lot of items
        return stream_append(xform(val[ii]),
            (", ", lambda: _safe_repr_5_items(xform, val, ii+1)))

def _safe_repr_5_dict_item((k, v)):
    return stream_append_n([_safe_repr_5(k), one_item_stream(": "),

def _safe_repr_5(val):
    "A stream is a (first_chunk, stream) pair, or (None, dontcare) for empty."
    if isinstance(val, types.ListType):
        return stream_append_n([one_item_stream('['),
                                _safe_repr_5_items(_safe_repr_5, val, 0),
    elif isinstance(val, types.TupleType):
        return stream_append_n([one_item_stream('('),
                                _safe_repr_5_items(_safe_repr_5, val, 0),
    elif isinstance(val, types.IntType):
        return one_item_stream('%d' % val)
    elif isinstance(val, types.DictType):
        return stream_append_n([
                # note that we may lose some laziness here building a big list
                _safe_repr_5_items(_safe_repr_5_dict_item, val.items(), 0),
    elif isinstance(val, types.InstanceType):
        return stream_append(one_item_stream(val.__class__.__name__ + ' '),
    elif isinstance(val, types.StringType):
        def chartrans(each_char):
            if each_char == '\\': return '\\\\'
            elif each_char == "'": return "\\'"
            else: return each_char
        return stream_append_n([one_item_stream("'"),
            _safe_repr_5_map(chartrans, val, 0),
        return one_item_stream(repr(val))
        raise UnhandledType(val)

def safe_repr_5(val, length):
    "A version using lazy streams."
    rv = []
    stream = _safe_repr_5(val)
    while 1:
        chunk, tail = stream
        if chunk is None: break
        chunk = chunk[:length]
        length -= len(chunk)
        if length == 0: break
        stream = tail()
    return ''.join(rv)

### Explicit stack version, eschewing recursion and even functions.  61 lines.
# Unsurprisingly, this is nearly the longest version of all, although
# it had surprisingly few bugs.
# In a sense, it's "safer" than the other implementations because it 
# can handle data structures that are nested thousands of levels deep
# without trouble.

def safe_repr_6(val, length):
    "Explicit stack version, eschewing recursion and functions entirely."
    stack = [('val', val)]
    rv = []
    while stack:
        tag, val = stack.pop()
        to_add = None
        if tag == 'val':
            if isinstance(val, types.ListType):
                to_add = '['
                stack.append(('literal', ']'))
                stack.append(('list_contents', (val, 0)))
            elif isinstance(val, types.TupleType):
                to_add = '('
                stack.append(('literal', ')'))
                stack.append(('list_contents', (val, 0)))
            elif isinstance(val, types.IntType):
                to_add = '%d' % val
            elif isinstance(val, types.DictType):
                to_add = '{'
                stack.append(('literal', '}'))
                stack.append(('dict_contents', (val.items(), 0)))
            elif isinstance(val, types.InstanceType):
                to_add = val.__class__.__name__ + ' '
                stack.append(('val', val.__dict__))
            elif isinstance(val, types.StringType):
                to_add = "'"
                stack.append(('literal', "'"))
                stack.append(('string', (val, 0)))
                raise UnhandledType(val)
        elif tag == 'literal':
            to_add = val
        elif tag == 'list_contents' or tag == 'dict_contents':
            val, ii = val
            if len(val) > 1 + ii:
                stack.append((tag, (val, ii + 1)))
                stack.append(('literal', ', '))
            if len(val) > ii:
                item = val[ii]
                if tag == 'list_contents':
                    stack.append(('val', item))
                else:  # tag == 'dict_contents'
                    k, v = item
                    stack.append(('val', v))
                    stack.append(('literal', ': '))
                    stack.append(('val', k))
        elif tag == 'string':
            val, ii = val
            if len(val) > ii:
                stack.append((tag, (val, ii + 1)))
                each_char = val[ii]
                if each_char == '\\': to_add = '\\\\'
                elif each_char == "'": to_add = "\\'"
                else: to_add = each_char
        if to_add is not None:
            to_add = to_add[:length]
            length -= len(to_add)
            if length == 0: break
    return ''.join(rv)

### Unit tests, to verify that these functions all work.

def test_fun_on(fun, val):
    for length in range(40):
        rstr = fun(val, length)
        assert len(rstr) <= length, (rstr, val, length, len(rstr))
        assert rstr == safe_repr_1(val, length), (rstr, 
                                                  safe_repr_1(val, length))

def test_fun(fun):
    test_fun_on(fun, range(11))
    y = []
    for ii in range(10): y = [y]
    test_fun_on(fun, y)

def test_fun_harder(fun):
    class Foo: pass
    x = Foo()
    x.blarg = 37
    test_fun_on(fun, (x, {}, [(131, 'foo')]))

def test_all():



Reply via email to