1Description of exception handling in Python 3.11
2------------------------------------------------
3
4Python 3.11 uses what is known as "zero-cost" exception handling.
5Prior to 3.11, exceptions were handled by a runtime stack of "blocks".
6
7In zero-cost exception handling, the cost of supporting exceptions is minimized.
8In the common case (where no exception is raised) the cost is reduced
9to zero (or close to zero).
10The cost of raising an exception is increased, but not by much.
11
12The following code:
13
14def f():
15    try:
16        g(0)
17    except:
18        return "fail"
19
20compiles as follows in 3.10:
21
22  2           0 SETUP_FINALLY            7 (to 16)
23
24  3           2 LOAD_GLOBAL              0 (g)
25              4 LOAD_CONST               1 (0)
26              6 CALL_NO_KW               1
27              8 POP_TOP
28             10 POP_BLOCK
29             12 LOAD_CONST               0 (None)
30             14 RETURN_VALUE
31
32  4     >>   16 POP_TOP
33             18 POP_TOP
34             20 POP_TOP
35
36  5          22 POP_EXCEPT
37             24 LOAD_CONST               3 ('fail')
38             26 RETURN_VALUE
39
40Note the explicit instructions to push and pop from the "block" stack:
41SETUP_FINALLY and POP_BLOCK.
42
43In 3.11, the SETUP_FINALLY and POP_BLOCK are eliminated, replaced with
44a table to determine where to jump to when an exception is raised.
45
46  1           0 RESUME                   0
47
48  2           2 NOP
49
50  3           4 LOAD_GLOBAL              1 (NULL + g)
51             16 LOAD_CONST               1 (0)
52             18 PRECALL                  1
53             22 CALL                     1
54             32 POP_TOP
55             34 LOAD_CONST               0 (None)
56             36 RETURN_VALUE
57        >>   38 PUSH_EXC_INFO
58
59  4          40 POP_TOP
60
61  5          42 POP_EXCEPT
62             44 LOAD_CONST               2 ('fail')
63             46 RETURN_VALUE
64        >>   48 COPY                     3
65             50 POP_EXCEPT
66             52 RERAISE                  1
67ExceptionTable:
68  4 to 32 -> 38 [0]
69  38 to 40 -> 48 [1] lasti
70
71(Note this code is from 3.11, later versions may have slightly different bytecode.)
72
73If an instruction raises an exception then its offset is used to find the target to jump to.
74For example, the CALL at offset 22, falls into the range 4 to 32.
75So, if g() raises an exception, then control jumps to offset 38.
76
77
78Unwinding
79---------
80
81When an exception is raised, the current instruction offset is used to find following:
82target to jump to, stack depth, and 'lasti', which determines whether the instruction
83offset of the raising instruction should be pushed.
84
85This information is stored in the exception table, described below.
86
87If there is no relevant entry, the exception bubbles up to the caller.
88
89If there is an entry, then:
90 1. pop values from the stack until it matches the stack depth for the handler.
91 2. if 'lasti' is true, then push the offset that the exception was raised at.
92 3. push the exception to the stack.
93 4. jump to the target offset and resume execution.
94
95
96Format of the exception table
97-----------------------------
98
99Conceptually, the exception table consists of a sequence of 5-tuples:
100    1. start-offset (inclusive)
101    2. end-offset (exclusive)
102    3. target
103    4. stack-depth
104    5. push-lasti (boolean)
105
106All offsets and lengths are in instructions, not bytes.
107
108We want the format to be compact, but quickly searchable.
109For it to be compact, it needs to have variable sized entries so that we can store common (small) offsets compactly, but handle large offsets if needed.
110For it to be searchable quickly, we need to support binary search giving us log(n) performance in all cases.
111Binary search typically assumes fixed size entries, but that is not necessary, as long as we can identify the start of an entry.
112
113It is worth noting that the size (end-start) is always smaller than the end, so we encode the entries as:
114    start, size, target, depth, push-lasti
115
116Also, sizes are limited to 2**30 as the code length cannot exceed 2**31 and each instruction takes 2 bytes.
117It also happens that depth is generally quite small.
118
119So, we need to encode:
120    start (up to 30 bits)
121    size (up to 30 bits)
122    target (up to 30 bits)
123    depth (up to ~8 bits)
124    lasti (1 bit)
125
126We need a marker for the start of the entry, so the first byte of entry will have the most significant bit set.
127Since the most significant bit is reserved for marking the start of an entry, we have 7 bits per byte to encode offsets.
128Encoding uses a standard varint encoding, but with only 7 bits instead of the usual 8.
129The 8 bits of a bit are (msb left) SXdddddd where S is the start bit. X is the extend bit meaning that the next byte is required to extend the offset.
130
131In addition, we will combine depth and lasti into a single value, ((depth<<1)+lasti), before encoding.
132
133For example, the exception entry:
134    start:  20
135    end:    28
136    target: 100
137    depth:  3
138    lasti:  False
139
140is encoded first by converting to the more compact four value form:
141    start:         20
142    size:          8
143    target:        100
144  depth<<1+lasti:  6
145
146which is then encoded as:
147    148 (MSB + 20 for start)
148    8   (size)
149    65  (Extend bit + 1)
150    36  (Remainder of target, 100 == (1<<6)+36)
151    6
152
153for a total of five bytes.
154
155
156
157Script to parse the exception table
158-----------------------------------
159
160def parse_varint(iterator):
161    b = next(iterator)
162    val = b & 63
163    while b&64:
164        val <<= 6
165        b = next(iterator)
166        val |= b&63
167    return val
168
169def parse_exception_table(code):
170    iterator = iter(code.co_exceptiontable)
171    try:
172        while True:
173            start = parse_varint(iterator)*2
174            length = parse_varint(iterator)*2
175            end = start + length - 2 # Present as inclusive, not exclusive
176            target = parse_varint(iterator)*2
177            dl = parse_varint(iterator)
178            depth = dl >> 1
179            lasti = bool(dl&1)
180            yield start, end, target, depth, lasti
181    except StopIteration:
182        return
183