A lab directory for experiments in progress.

1 files changed, 122 insertions, 0 deletions

diff --git a/lab/lnotab.py b/lab/lnotab.py
new file mode 100644
index 00000000..230e42bb
--- /dev/null
+++ b/lab/lnotab.py
@@ -0,0 +1,122 @@
+# Comment copied from Python/compile.c:
+#
+# All about a_lnotab.
+# 
+# c_lnotab is an array of unsigned bytes disguised as a Python string.
+# It is used to map bytecode offsets to source code line #s (when needed
+# for tracebacks).
+# 
+# The array is conceptually a list of
+#     (bytecode offset increment, line number increment)
+# pairs. The details are important and delicate, best illustrated by example:
+# 
+#     byte code offset   source code line number
+#        0                   1
+#        6                   2
+#       50                   7
+#      350                 307
+#      361                 308
+# 
+# The first trick is that these numbers aren't stored, only the increments
+# from one row to the next (this doesn't really work, but it's a start):
+# 
+#     0, 1,  6, 1,  44, 5,  300, 300,  11, 1
+# 
+# The second trick is that an unsigned byte can't hold negative values, or
+# values larger than 255, so (a) there's a deep assumption that byte code
+# offsets and their corresponding line #s both increase monotonically, and (b)
+# if at least one column jumps by more than 255 from one row to the next, more
+# than one pair is written to the table. In case #b, there's no way to know
+# from looking at the table later how many were written.	That's the delicate
+# part.  A user of c_lnotab desiring to find the source line number
+# corresponding to a bytecode address A should do something like this
+# 
+#     lineno = addr = 0
+#     for addr_incr, line_incr in c_lnotab:
+#         addr += addr_incr
+#         if addr > A:
+#             return lineno
+#         lineno += line_incr
+# 
+# In order for this to work, when the addr field increments by more than 255,
+# the line # increment in each pair generated must be 0 until the remaining addr
+# increment is < 256.  So, in the example above, assemble_lnotab (it used
+# to be called com_set_lineno) should not (as was actually done until 2.2)
+# expand 300, 300 to 255, 255, 45, 45, 
+#             but to 255,   0, 45, 255, 0, 45.
+# 
+
+def lnotab(pairs, first_lineno=0):
+    """Yields byte integers representing the pairs of integers passed in."""
+    assert first_lineno <= pairs[0][1]
+    cur_byte, cur_line = 0, first_lineno
+    for byte_off, line_off in pairs:
+        byte_delta = byte_off - cur_byte
+        line_delta = line_off - cur_line
+        assert byte_delta >= 0
+        assert line_delta >= 0
+        while byte_delta > 255:
+            yield 255 # byte
+            yield 0   # line
+            byte_delta -= 255
+        yield byte_delta
+        while line_delta > 255:
+            yield 255 # line
+            yield 0   # byte
+            line_delta -= 255
+        yield line_delta
+        cur_byte, cur_line = byte_off, line_off
+
+def lnotab_string(pairs, first_lineno=0):
+    return "".join(chr(b) for b in lnotab(pairs, first_lineno))
+
+def byte_pairs(lnotab):
+    """Yield pairs of integers from a string."""
+    for i in range(0, len(lnotab), 2):
+        yield ord(lnotab[i]), ord(lnotab[i+1])
+        
+def lnotab_numbers(lnotab, first_lineno=0):
+    """Yields the byte, line offset pairs from a packed lnotab string."""
+
+    last_line = None
+    cur_byte, cur_line = 0, first_lineno
+    for byte_delta, line_delta in byte_pairs(lnotab):
+        if byte_delta:
+            if cur_line != last_line:
+                yield cur_byte, cur_line
+                last_line = cur_line
+            cur_byte += byte_delta
+        cur_line += line_delta
+    if cur_line != last_line:        
+        yield cur_byte, cur_line
+    
+
+## Tests
+
+def same_list(a, b):
+    a = list(a)
+    assert a == b
+    
+def test_simple():
+    same_list(lnotab([(0,1)]), [0, 1])
+    same_list(lnotab([(0,1), (6, 2)]), [0, 1,  6, 1])
+
+def test_starting_above_one():
+    same_list(lnotab([(0,100), (6,101)]), [0, 100,  6, 1])
+    same_list(lnotab([(0,100), (6,101)], 50), [0, 50,  6, 1])
+    
+def test_large_gaps():
+    same_list(lnotab([(0,1), (300, 300)]), [0, 1,  255, 0,  45, 255,  0, 44])
+    same_list(lnotab([(0,1), (255, 300)]), [0, 1,  255, 255,  0, 44])
+    same_list(lnotab([(0,1), (255, 256)]), [0, 1,  255, 255])
+    
+def test_strings():
+    assert lnotab_string([(0,1), (6, 2)]) == "\x00\x01\x06\x01"
+    assert lnotab_string([(0,1), (300, 300)]) == "\x00\x01\xff\x00\x2d\xff\x00\x2c"
+
+def test_numbers():
+    same_list(lnotab_numbers("\x00\x01\x06\x01"), [(0,1), (6,2)])
+    same_list(lnotab_numbers("\x00\x01\xff\x00\x2d\xff\x00\x2c"), [(0,1), (300, 300)])
+
+def test_numbers_firstlineno():
+    same_list(lnotab_numbers("\x00\x01\xff\x00\x2d\xff\x00\x2c", 10), [(0,11), (300, 310)])