GH-88116: Use a compact format to represent end line and column offsets. (GH-91666)

* Stores all location info in linetable to conform to PEP 626.

* Remove column table from code objects.

* Remove end-line table from code objects.

* Document new location table format

6 files changed, 161 insertions, 77 deletions

diff --git a/Lib/test/test_code.py b/Lib/test/test_code.py
index 872f728..a37ebd2 100644
--- a/Lib/test/test_code.py
+++ b/Lib/test/test_code.py
@@ -230,9 +230,7 @@ class CodeTest(unittest.TestCase):
                         co.co_name,
                         co.co_qualname,
                         co.co_firstlineno,
-                        co.co_lnotab,
-                        co.co_endlinetable,
-                        co.co_columntable,
+                        co.co_linetable,
                         co.co_exceptiontable,
                         co.co_freevars,
                         co.co_cellvars)
@@ -273,8 +271,6 @@ class CodeTest(unittest.TestCase):
             ("co_filename", "newfilename"),
             ("co_name", "newname"),
             ("co_linetable", code2.co_linetable),
-            ("co_endlinetable", code2.co_endlinetable),
-            ("co_columntable", code2.co_columntable),
         ):
             with self.subTest(attr=attr, value=value):
                 new_code = code.replace(**{attr: value})
@@ -311,9 +307,7 @@ class CodeTest(unittest.TestCase):
                          co.co_name,
                          co.co_qualname,
                          co.co_firstlineno,
-                         co.co_lnotab,
-                         co.co_endlinetable,
-                         co.co_columntable,
+                         co.co_linetable,
                          co.co_exceptiontable,
                          co.co_freevars,
                          co.co_cellvars,
@@ -391,14 +385,17 @@ class CodeTest(unittest.TestCase):
         )
 
     def test_endline_and_columntable_none_when_no_debug_ranges(self):
-        # Make sure that if `-X no_debug_ranges` is used, the endlinetable and
-        # columntable are None.
+        # Make sure that if `-X no_debug_ranges` is used, there is
+        # minimal debug info
         code = textwrap.dedent("""
             def f():
                 pass
 
-            assert f.__code__.co_endlinetable is None
-            assert f.__code__.co_columntable is None
+            positions = f.__code__.co_positions()
+            for line, end_line, column, end_column in positions:
+                assert line == end_line
+                assert column is None
+                assert end_column is None
             """)
         assert_python_ok('-X', 'no_debug_ranges', '-c', code)
 
@@ -408,8 +405,11 @@ class CodeTest(unittest.TestCase):
             def f():
                 pass
 
-            assert f.__code__.co_endlinetable is None
-            assert f.__code__.co_columntable is None
+            positions = f.__code__.co_positions()
+            for line, end_line, column, end_column in positions:
+                assert line == end_line
+                assert column is None
+                assert end_column is None
             """)
         assert_python_ok('-c', code, PYTHONNODEBUGRANGES='1')
 
@@ -421,35 +421,10 @@ class CodeTest(unittest.TestCase):
             x = 1
         new_code = func.__code__.replace(co_linetable=b'')
         positions = new_code.co_positions()
-        next(positions) # Skip RESUME at start
         for line, end_line, column, end_column in positions:
             self.assertIsNone(line)
             self.assertEqual(end_line, new_code.co_firstlineno + 1)
 
-    @requires_debug_ranges()
-    def test_co_positions_empty_endlinetable(self):
-        def func():
-            x = 1
-        new_code = func.__code__.replace(co_endlinetable=b'')
-        positions = new_code.co_positions()
-        next(positions) # Skip RESUME at start
-        for line, end_line, column, end_column in positions:
-            self.assertEqual(line, new_code.co_firstlineno + 1)
-            self.assertIsNone(end_line)
-
-    @requires_debug_ranges()
-    def test_co_positions_empty_columntable(self):
-        def func():
-            x = 1
-        new_code = func.__code__.replace(co_columntable=b'')
-        positions = new_code.co_positions()
-        next(positions) # Skip RESUME at start
-        for line, end_line, column, end_column in positions:
-            self.assertEqual(line, new_code.co_firstlineno + 1)
-            self.assertEqual(end_line, new_code.co_firstlineno + 1)
-            self.assertIsNone(column)
-            self.assertIsNone(end_column)
-
 
 def isinterned(s):
     return s is sys.intern(('_' + s + '_')[1:-1])
@@ -527,6 +502,122 @@ class CodeWeakRefTest(unittest.TestCase):
         self.assertFalse(bool(coderef()))
         self.assertTrue(self.called)
 
+# Python implementation of location table parsing algorithm
+def read(it):
+    return next(it)
+
+def read_varint(it):
+    b = read(it)
+    val = b & 63;
+    shift = 0;
+    while b & 64:
+        b = read(it)
+        shift += 6
+        val |= (b&63) << shift
+    return val
+
+def read_signed_varint(it):
+    uval = read_varint(it)
+    if uval & 1:
+        return -(uval >> 1)
+    else:
+        return uval >> 1
+
+def parse_location_table(code):
+    line = code.co_firstlineno
+    it = iter(code.co_linetable)
+    while True:
+        try:
+            first_byte = read(it)
+        except StopIteration:
+            return
+        code = (first_byte >> 3) & 15
+        length = (first_byte & 7) + 1
+        if code == 15:
+            yield (code, length, None, None, None, None)
+        elif code == 14:
+            line_delta = read_signed_varint(it)
+            line += line_delta
+            end_line = line + read_varint(it)
+            col = read_varint(it)
+            if col == 0:
+                col = None
+            else:
+                col -= 1
+            end_col = read_varint(it)
+            if end_col == 0:
+                end_col = None
+            else:
+                end_col -= 1
+            yield (code, length, line, end_line, col, end_col)
+        elif code == 13: # No column
+            line_delta = read_signed_varint(it)
+            line += line_delta
+            yield (code, length, line, line, None, None)
+        elif code in (10, 11, 12): # new line
+            line_delta = code - 10
+            line += line_delta
+            column = read(it)
+            end_column = read(it)
+            yield (code, length, line, line, column, end_column)
+        else:
+            assert (0 <= code < 10)
+            second_byte = read(it)
+            column = code << 3 | (second_byte >> 4)
+            yield (code, length, line, line, column, column + (second_byte & 15))
+
+def positions_from_location_table(code):
+    for _, length, line, end_line, col, end_col in parse_location_table(code):
+        for _ in range(length):
+            yield (line, end_line, col, end_col)
+
+def misshappen():
+    """
+
+
+
+
+
+    """
+    x = (
+
+
+        4
+
+        +
+
+        y
+
+    )
+    y = (
+        a
+        +
+            b
+                +
+
+                d
+        )
+    return q if (
+
+        x
+
+        ) else p
+
+
+class CodeLocationTest(unittest.TestCase):
+
+    def check_positions(self, func):
+        pos1 = list(func.__code__.co_positions())
+        pos2 = list(positions_from_location_table(func.__code__))
+        for l1, l2 in zip(pos1, pos2):
+            self.assertEqual(l1, l2)
+        self.assertEqual(len(pos1), len(pos2))
+
+
+    def test_positions(self):
+        self.check_positions(parse_location_table)
+        self.check_positions(misshappen)
+
 
 if check_impl_detail(cpython=True) and ctypes is not None:
     py = ctypes.pythonapi
diff --git a/Lib/test/test_compile.py b/Lib/test/test_compile.py
index a4e8080..5a9c618 100644
--- a/Lib/test/test_compile.py
+++ b/Lib/test/test_compile.py
@@ -158,7 +158,9 @@ if 1:
         s256 = "".join(["\n"] * 256 + ["spam"])
         co = compile(s256, 'fn', 'exec')
         self.assertEqual(co.co_firstlineno, 1)
-        self.assertEqual(list(co.co_lines()), [(0, 2, None), (2, 10, 257)])
+        lines = list(co.co_lines())
+        self.assertEqual(lines[0][2], None)
+        self.assertEqual(lines[1][2], 257)
 
     def test_literals_with_leading_zeroes(self):
         for arg in ["077787", "0xj", "0x.", "0e",  "090000000000000",
@@ -892,12 +894,19 @@ if 1:
             with self.subTest(func=func):
                 code = func.__code__
                 lines = list(code.co_lines())
-                self.assertEqual(len(lines), 1)
                 start, end, line = lines[0]
                 self.assertEqual(start, 0)
-                self.assertEqual(end, len(code.co_code))
                 self.assertEqual(line, code.co_firstlineno)
 
+    def get_code_lines(self, code):
+        last_line = -2
+        res = []
+        for _, _, line in code.co_lines():
+            if line is not None and line != last_line:
+                res.append(line - code.co_firstlineno)
+                last_line = line
+        return res
+
     def test_lineno_attribute(self):
         def load_attr():
             return (
@@ -939,9 +948,7 @@ if 1:
 
         for func, lines in zip(funcs, func_lines, strict=True):
             with self.subTest(func=func):
-                code_lines = [ line-func.__code__.co_firstlineno
-                              for (_, _, line) in func.__code__.co_lines()
-                              if line is not None ]
+                code_lines = self.get_code_lines(func.__code__)
                 self.assertEqual(lines, code_lines)
 
     def test_line_number_genexp(self):
@@ -952,11 +959,10 @@ if 1:
                     x
                     in
                     y)
-        genexp_lines = [1, 3, 1]
+        genexp_lines = [0, 2, 0]
 
         genexp_code = return_genexp.__code__.co_consts[1]
-        code_lines = [ None if line is None else line-return_genexp.__code__.co_firstlineno
-                      for (_, _, line) in genexp_code.co_lines() ]
+        code_lines = self.get_code_lines(genexp_code)
         self.assertEqual(genexp_lines, code_lines)
 
     def test_line_number_implicit_return_after_async_for(self):
@@ -966,8 +972,7 @@ if 1:
                 body
 
         expected_lines = [0, 1, 2, 1]
-        code_lines = [ None if line is None else line-test.__code__.co_firstlineno
-                      for (_, _, line) in test.__code__.co_lines() ]
+        code_lines = self.get_code_lines(test.__code__)
         self.assertEqual(expected_lines, code_lines)
 
     def test_big_dict_literal(self):
@@ -1112,14 +1117,14 @@ f(
             line=1, end_line=3, column=0, end_column=1)
 
     def test_very_long_line_end_offset(self):
-        # Make sure we get None for when the column offset is too large to
-        # store in a byte.
+        # Make sure we get the correct column offset for offsets
+        # too large to store in a byte.
         long_string = "a" * 1000
         snippet = f"g('{long_string}')"
 
         compiled_code, _ = self.check_positions_against_ast(snippet)
         self.assertOpcodeSourcePositionIs(compiled_code, 'CALL',
-            line=1, end_line=1, column=None, end_column=None)
+            line=1, end_line=1, column=0, end_column=1005)
 
     def test_complex_single_line_expression(self):
         snippet = "a - b @ (c * x['key'] + 23)"
diff --git a/Lib/test/test_dis.py b/Lib/test/test_dis.py
index f560a55..0bd589d 100644
--- a/Lib/test/test_dis.py
+++ b/Lib/test/test_dis.py
@@ -196,7 +196,7 @@ def bug42562():
 
 
 # Set line number for 'pass' to None
-bug42562.__code__ = bug42562.__code__.replace(co_linetable=b'\x04\x80')
+bug42562.__code__ = bug42562.__code__.replace(co_linetable=b'\xf8')
 
 
 dis_bug42562 = """\
@@ -1560,32 +1560,19 @@ class InstructionTests(InstructionTestCase):
     @requires_debug_ranges()
     def test_co_positions_missing_info(self):
         code = compile('x, y, z', '<test>', 'exec')
-        code_without_column_table = code.replace(co_columntable=b'')
-        actual = dis.get_instructions(code_without_column_table)
+        code_without_location_table = code.replace(co_linetable=b'')
+        actual = dis.get_instructions(code_without_location_table)
         for instruction in actual:
             with self.subTest(instruction=instruction):
                 positions = instruction.positions
                 self.assertEqual(len(positions), 4)
                 if instruction.opname == "RESUME":
                     continue
-                self.assertEqual(positions.lineno, 1)
-                self.assertEqual(positions.end_lineno, 1)
+                self.assertIsNone(positions.lineno)
+                self.assertIsNone(positions.end_lineno)
                 self.assertIsNone(positions.col_offset)
                 self.assertIsNone(positions.end_col_offset)
 
-        code_without_endline_table = code.replace(co_endlinetable=b'')
-        actual = dis.get_instructions(code_without_endline_table)
-        for instruction in actual:
-            with self.subTest(instruction=instruction):
-                positions = instruction.positions
-                self.assertEqual(len(positions), 4)
-                if instruction.opname == "RESUME":
-                    continue
-                self.assertEqual(positions.lineno, 1)
-                self.assertIsNone(positions.end_lineno)
-                self.assertIsNotNone(positions.col_offset)
-                self.assertIsNotNone(positions.end_col_offset)
-
 # get_instructions has its own tests above, so can rely on it to validate
 # the object oriented API
 class BytecodeTests(InstructionTestCase, DisTestBase):
diff --git a/Lib/test/test_exceptions.py b/Lib/test/test_exceptions.py
index 2b5b519..ff1a028 100644
--- a/Lib/test/test_exceptions.py
+++ b/Lib/test/test_exceptions.py
@@ -2658,7 +2658,7 @@ class PEP626Tests(unittest.TestCase):
         def f():
             1/0
         self.lineno_after_raise(f, 1)
-        f.__code__ = f.__code__.replace(co_linetable=b'\x04\x80\xff\x80')
+        f.__code__ = f.__code__.replace(co_linetable=b'\xf8\xf8\xf8\xf9\xf8\xf8\xf8')
         self.lineno_after_raise(f, None)
 
     def test_lineno_after_raise_in_with_exit(self):
diff --git a/Lib/test/test_marshal.py b/Lib/test/test_marshal.py
index 8d55382..aae86cc 100644
--- a/Lib/test/test_marshal.py
+++ b/Lib/test/test_marshal.py
@@ -129,18 +129,18 @@ class CodeTestCase(unittest.TestCase):
         self.assertEqual(co2.co_filename, "f2")
 
     @requires_debug_ranges()
-    def test_no_columntable_and_endlinetable_with_no_debug_ranges(self):
+    def test_minimal_linetable_with_no_debug_ranges(self):
         # Make sure when demarshalling objects with `-X no_debug_ranges`
-        # that the columntable and endlinetable are None.
+        # that the columns are None.
         co = ExceptionTestCase.test_exceptions.__code__
         code = textwrap.dedent("""
         import sys
         import marshal
         with open(sys.argv[1], 'rb') as f:
             co = marshal.load(f)
-
-            assert co.co_endlinetable is None
-            assert co.co_columntable is None
+            positions = list(co.co_positions())
+            assert positions[0][2] is None
+            assert positions[0][3] is None
         """)
 
         try:
diff --git a/Lib/test/test_traceback.py b/Lib/test/test_traceback.py
index 962322c..ed5ddf9 100644
--- a/Lib/test/test_traceback.py
+++ b/Lib/test/test_traceback.py
@@ -615,6 +615,7 @@ class TracebackErrorLocationCaretTests(unittest.TestCase):
             '    ^^^^^^^^^^\n'
             f'  File "{TESTFN}", line {lineno_f}, in <module>\n'
             f'    {source}\n'
+            f'    {"^"*len(source)}\n'
         )
         self.assertEqual(result_lines, expected_error.splitlines())