ActiveState Code

Recipe 576944: The goto decorator

A function-decorator that provides the goto command.

Python 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
import dis
import new

class MissingLabelError(Exception):
    """'goto' without matching 'label'."""
    pass


def goto(fn):
    """
    A function decorator to add the goto command for a function.

    Specify labels like so:

    label .foo
    
    Goto labels like so:

    goto .foo
    """
    labels = {}
    gotos = {}
    globalName = None
    index = 0
    end = len(fn.func_code.co_code)
    i = 0

    # scan through the byte codes to find the labels and gotos
    while i < end:
        op = ord(fn.func_code.co_code[i])
        i += 1
        name = dis.opname[op]

        if op > dis.HAVE_ARGUMENT:
            b1 = ord(fn.func_code.co_code[i])
            b2 = ord(fn.func_code.co_code[i+1])
            num = b2 * 256 + b1
            
            if name == 'LOAD_GLOBAL':
                globalName = fn.func_code.co_names[num]
                index = i - 1
                i += 2
                continue
                
            if name == 'LOAD_ATTR':
                if globalName == 'label':
                    labels[fn.func_code.co_names[num]] = index
                elif globalName == 'goto':
                    gotos[fn.func_code.co_names[num]] = index
                    
            name = None
            i += 2

    # no-op the labels
    ilist = list(fn.func_code.co_code)
    for label,index in labels.items():
        ilist[index:index+7] = [chr(dis.opmap['NOP'])]*7

    # change gotos to jumps
    for label,index in gotos.items():
        if label not in labels:
            raise MissingLabelError("Missing label: %s"%label)
        
        target = labels[label] + 7   # skip NOPs
        ilist[index] = chr(dis.opmap['JUMP_ABSOLUTE'])
        ilist[index + 1] = chr(target & 255)
        ilist[index + 2] = chr(target >> 8)

    # create new function from existing function
    c = fn.func_code
    newcode = new.code(c.co_argcount,
                       c.co_nlocals,
                       c.co_stacksize,
                       c.co_flags,
                       ''.join(ilist),
                       c.co_consts,
                       c.co_names,
                       c.co_varnames,
                       c.co_filename,
                       c.co_name,
                       c.co_firstlineno,
                       c.co_lnotab)
    newfn = new.function(newcode,fn.func_globals)
    return newfn


if __name__ == '__main__':
    
    @goto
    def test1(n):

        s = 0

        label .myLoop

        if n <= 0:
            return s
        s += n
        n -= 1

        goto .myLoop

    assert(test1(10) == 55)

Discussion

This is the recipe for you if you are sick of the slow speed of the existing goto module http://entrian.com/goto/. The goto in this recipe is about 60x faster and is also cleaner (abusing sys.settrace seems hardly pythonic). Because this is a decorator, it alerts the reader which functions use goto. It does not implement the comefrom command, although it is not difficult to extend it to do so (exercise for the reader). Also, computed gotos aren't supported; they're not pythonic.

  • Use dis.dis(fn) to show the bytecode disassembly of a function.
  • The bytecodes of a function are accessed by fn.func_code.co_code. This is readonly so:
  • The decorated function is created exactly the same as the old one, but with the bytecode updated to obey the goto commands.
  • This is 2.x only; the new module is not in python 3.x (another exercise for the reader!)

Comments

  1. 1. At 2:39 a.m. on 3 nov 2009, Gabriel Genellina said:

    How bizarre! And you're even concerned about speed! :)

  2. 2. At 6:05 a.m. on 3 nov 2009, Valentine Gogichashvili said:

    I wonder, why you need goto operator at all?

    I can imagine making 'break' and 'continue' operator for loops be aware of the labels, but for the God's sake, when do you use the goto?

    Thank you for a nice example of adding new operators to the code :)

  3. 3. At 7:34 a.m. on 3 nov 2009, Paul Miller said:

    +1 for hack value.

  4. 4. At 12:17 p.m. on 3 nov 2009, Carl Cerecke (the author) said:

    Valentine Gogichashvili said "I wonder, why you need goto operator at all?"

    There is one use case that I can think of where having a fast goto is valuable: finite state machines. If you have a FSM that you want to run fast (perhaps a shift-reduce parser), then gotos will allow you to avoid the overhead of a function-call/dispatch method.

Sign in to comment