| Description of the internal format of the line number table | |
| Conceptually, the line number table consists of a sequence of triples: | |
| start-offset (inclusive), end-offset (exclusive), line-number. | |
| Note that not all byte codes have a line number so we need handle `None` for the line-number. | |
| However, storing the above sequence directly would be very inefficient as we would need 12 bytes per entry. | |
| First, note that the end of one entry is the same as the start of the next, so we can overlap entries. | |
| Second, we don't really need arbitrary access to the sequence, so we can store deltas. | |
| We just need to store (end - start, line delta) pairs. The start offset of the first entry is always zero. | |
| Third, most deltas are small, so we can use a single byte for each value, as long we allow several entries for the same line. | |
| Consider the following table | |
| Start End Line | |
| 0 6 1 | |
| 6 50 2 | |
| 50 350 7 | |
| 350 360 No line number | |
| 360 376 8 | |
| 376 380 208 | |
| Stripping the redundant ends gives: | |
| End-Start Line-delta | |
| 6 +1 | |
| 44 +1 | |
| 300 +5 | |
| 10 No line number | |
| 16 +1 | |
| 4 +200 | |
| Note that the end - start value is always positive. | |
| Finally, in order to fit into a single byte we need to convert start deltas to the range 0 <= delta <= 254, | |
| and line deltas to the range -127 <= delta <= 127. | |
| A line delta of -128 is used to indicate no line number. | |
| Also note that a delta of zero indicates that there are no bytecodes in the given range, | |
| which means we can use an invalid line number for that range. | |
| Final form: | |
| Start delta Line delta | |
| 6 +1 | |
| 44 +1 | |
| 254 +5 | |
| 46 0 | |
| 10 -128 (No line number, treated as a delta of zero) | |
| 16 +1 | |
| 0 +127 (line 135, but the range is empty as no bytecodes are at line 135) | |
| 4 +73 | |
| Iterating over the table. | |
| ------------------------- | |
| For the `co_lines` attribute we want to emit the full form, omitting the (350, 360, No line number) and empty entries. | |
| The code is as follows: | |
| def co_lines(code): | |
| line = code.co_firstlineno | |
| end = 0 | |
| table_iter = iter(code.internal_line_table): | |
| for sdelta, ldelta in table_iter: | |
| if ldelta == 0: # No change to line number, just accumulate changes to end | |
| end += odelta | |
| continue | |
| start = end | |
| end = start + sdelta | |
| if ldelta == -128: # No valid line number -- skip entry | |
| continue | |
| line += ldelta | |
| if end == start: # Empty range, omit. | |
| continue | |
| yield start, end, line | |
| The historical co_lnotab format | |
| ------------------------------- | |
| prior to 3.10 code objects stored a field named co_lnotab. | |
| This was an array of unsigned bytes disguised as a Python bytes object. | |
| The old co_lnotab did not account for the presence of bytecodes without a line number, | |
| nor was it well suited to tracing as a number of workarounds were required. | |
| The old format can still be accessed via `code.co_lnotab`, which is lazily computed from the new format. | |
| Below is the description of the old co_lnotab format: | |
| The array is conceptually a compressed 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 207 | |
| 361 208 | |
| Instead of storing these numbers literally, we compress the list by storing only | |
| the difference from one row to the next. Conceptually, the stored list might | |
| look like: | |
| 0, 1, 6, 1, 44, 5, 300, 200, 11, 1 | |
| The above doesn't really work, but it's a start. An unsigned byte (byte code | |
| offset) can't hold negative values, or values larger than 255, a signed byte | |
| (line number) can't hold values larger than 127 or less than -128, and the | |
| above example contains two such values. (Note that before 3.6, line number | |
| was also encoded by an unsigned byte.) So we make two tweaks: | |
| (a) there's a deep assumption that byte code offsets increase monotonically, | |
| and | |
| (b) if byte code offset jumps by more than 255 from one row to the next, or if | |
| source code line number jumps by more than 127 or less than -128 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 co_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 co_lnotab: | |
| addr += addr_incr | |
| if addr > A: | |
| return lineno | |
| if line_incr >= 0x80: | |
| line_incr -= 0x100 | |
| lineno += line_incr | |
| (In C, this is implemented by PyCode_Addr2Line().) 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 in compile.c should not (as was actually done | |
| until 2.2) expand 300, 200 to | |
| 255, 255, 45, 45, | |
| but to | |
| 255, 0, 45, 127, 0, 73. | |
| The above is sufficient to reconstruct line numbers for tracebacks, but not for | |
| line tracing. Tracing is handled by PyCode_CheckLineNumber() in codeobject.c | |
| and maybe_call_line_trace() in ceval.c. | |
| *** Tracing *** | |
| To a first approximation, we want to call the tracing function when the line | |
| number of the current instruction changes. Re-computing the current line for | |
| every instruction is a little slow, though, so each time we compute the line | |
| number we save the bytecode indices where it's valid: | |
| *instr_lb <= frame->f_lasti < *instr_ub | |
| is true so long as execution does not change lines. That is, *instr_lb holds | |
| the first bytecode index of the current line, and *instr_ub holds the first | |
| bytecode index of the next line. As long as the above expression is true, | |
| maybe_call_line_trace() does not need to call PyCode_CheckLineNumber(). Note | |
| that the same line may appear multiple times in the lnotab, either because the | |
| bytecode jumped more than 255 indices between line number changes or because | |
| the compiler inserted the same line twice. Even in that case, *instr_ub holds | |
| the first index of the next line. | |
| However, we don't *always* want to call the line trace function when the above | |
| test fails. | |
| Consider this code: | |
| 1: def f(a): | |
| 2: while a: | |
| 3: print(1) | |
| 4: break | |
| 5: else: | |
| 6: print(2) | |
| which compiles to this: | |
| 2 0 SETUP_LOOP 26 (to 28) | |
| >> 2 LOAD_FAST 0 (a) | |
| 4 POP_JUMP_IF_FALSE 18 | |
| 3 6 LOAD_GLOBAL 0 (print) | |
| 8 LOAD_CONST 1 (1) | |
| 10 CALL_FUNCTION 1 | |
| 12 POP_TOP | |
| 4 14 BREAK_LOOP | |
| 16 JUMP_ABSOLUTE 2 | |
| >> 18 POP_BLOCK | |
| 6 20 LOAD_GLOBAL 0 (print) | |
| 22 LOAD_CONST 2 (2) | |
| 24 CALL_FUNCTION 1 | |
| 26 POP_TOP | |
| >> 28 LOAD_CONST 0 (None) | |
| 30 RETURN_VALUE | |
| If 'a' is false, execution will jump to the POP_BLOCK instruction at offset 18 | |
| and the co_lnotab will claim that execution has moved to line 4, which is wrong. | |
| In this case, we could instead associate the POP_BLOCK with line 5, but that | |
| would break jumps around loops without else clauses. | |
| We fix this by only calling the line trace function for a forward jump if the | |
| co_lnotab indicates we have jumped to the *start* of a line, i.e. if the current | |
| instruction offset matches the offset given for the start of a line by the | |
| co_lnotab. For backward jumps, however, we always call the line trace function, | |
| which lets a debugger stop on every evaluation of a loop guard (which usually | |
| won't be the first opcode in a line). | |
| Why do we set f_lineno when tracing, and only just before calling the trace | |
| function? Well, consider the code above when 'a' is true. If stepping through | |
| this with 'n' in pdb, you would stop at line 1 with a "call" type event, then | |
| line events on lines 2, 3, and 4, then a "return" type event -- but because the | |
| code for the return actually falls in the range of the "line 6" opcodes, you | |
| would be shown line 6 during this event. This is a change from the behaviour in | |
| 2.2 and before, and I've found it confusing in practice. By setting and using | |
| f_lineno when tracing, one can report a line number different from that | |
| suggested by f_lasti on this one occasion where it's desirable. |