co_lnotab supports negative line number delta

Issue #26107: The format of the co_lnotab attribute of code objects changes to
support negative line number delta.

Changes:

* assemble_lnotab(): if line number delta is less than -128 or greater than
  127, emit multiple (offset_delta, lineno_delta) in co_lnotab
* update functions decoding co_lnotab to use signed 8-bit integers

  - dis.findlinestarts()
  - PyCode_Addr2Line()
  - _PyCode_CheckLineNumber()
  - frame_setlineno()

* update lnotab_notes.txt
* increase importlib MAGIC_NUMBER to 3361
* document the change in What's New in Python 3.6
* cleanup also PyCode_Optimize() to use better variable names

3 files changed, 29 insertions, 21 deletions

diff --git a/Objects/codeobject.c b/Objects/codeobject.c
index b0e3446..0f03dfe 100644
--- a/Objects/codeobject.c
+++ b/Objects/codeobject.c
@@ -557,7 +557,8 @@ PyCode_Addr2Line(PyCodeObject *co, int addrq)
         addr += *p++;
         if (addr > addrq)
             break;
-        line += *p++;
+        line += (signed char)*p;
+        p++;
     }
     return line;
 }
@@ -592,17 +593,19 @@ _PyCode_CheckLineNumber(PyCodeObject* co, int lasti, PyAddrPair *bounds)
         if (addr + *p > lasti)
             break;
         addr += *p++;
-        if (*p)
+        if ((signed char)*p)
             bounds->ap_lower = addr;
-        line += *p++;
+        line += (signed char)*p;
+        p++;
         --size;
     }
 
     if (size > 0) {
         while (--size >= 0) {
             addr += *p++;
-            if (*p++)
+            if ((signed char)*p)
                 break;
+            p++;
         }
         bounds->ap_upper = addr;
     }
diff --git a/Objects/frameobject.c b/Objects/frameobject.c
index 425a9ee..da2d2ed 100644
--- a/Objects/frameobject.c
+++ b/Objects/frameobject.c
@@ -137,7 +137,7 @@ frame_setlineno(PyFrameObject *f, PyObject* p_new_lineno)
         new_lasti = -1;
         for (offset = 0; offset < lnotab_len; offset += 2) {
             addr += lnotab[offset];
-            line += lnotab[offset+1];
+            line += (signed char)lnotab[offset+1];
             if (line >= new_lineno) {
                 new_lasti = addr;
                 new_lineno = line;
diff --git a/Objects/lnotab_notes.txt b/Objects/lnotab_notes.txt
index d247edd..8af10db 100644
--- a/Objects/lnotab_notes.txt
+++ b/Objects/lnotab_notes.txt
@@ -12,42 +12,47 @@ pairs.  The details are important and delicate, best illustrated by example:
         0		    1
         6		    2
        50		    7
-      350                 307
-      361                 308
+      350                 207
+      361                 208
 
 Instead of storing these numbers literally, we compress the list by storing only
-the increments from one row to the next.  Conceptually, the stored list might
+the difference from one row to the next.  Conceptually, the stored list might
 look like:
 
-    0, 1,  6, 1,  44, 5,  300, 300,  11, 1
+    0, 1,  6, 1,  44, 5,  300, 200,  11, 1
 
-The above doesn't really work, but it's a start. Note that an unsigned byte
-can't hold negative values, or values larger than 255, and the above example
-contains two such values. So we make two tweaks:
+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. So we make two tweaks:
 
- (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 co_lnotab desiring to find the source line number
- corresponding to a bytecode address A should do something like this
+ (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, 300 to
+until 2.2) expand 300, 200 to
     255, 255, 45, 45,
 but to
-    255, 0, 45, 255, 0, 45.
+    255, 0, 45, 128, 0, 72.
 
 The above is sufficient to reconstruct line numbers for tracebacks, but not for
 line tracing.  Tracing is handled by PyCode_CheckLineNumber() in codeobject.c