Certain sys.monitoring "not taken" branches in a for loop not showing correctly

@markshannon

Bug report

Bug description:

With the code from PR 122564, the destinations of the "not taken" branches out of lines 2 and 3 show as going out of scope, rather than the correct line 6. Additionally, the ("taken") branch into if's block also shows as going out of scope:

def foo():
    for v in [1, 2]:
        if v > 0:
            x += v

    return x

Results:

  1          0       RESUME                   0

  2          2       LOAD_CONST               1 ((1, 2))
             4       GET_ITER
      L1:    6       FOR_ITER                18 (to L3)
            10       NOT_TAKEN
            12       STORE_FAST               0 (v)

  3         14       LOAD_FAST                0 (v)
            16       LOAD_CONST               2 (0)
            18       COMPARE_OP             148 (bool(>))
            22       POP_JUMP_IF_TRUE         2 (to L2)
            26       JUMP_BACKWARD           12 (to L1)
      L2:   30       NOT_TAKEN

  4         32       LOAD_FAST_CHECK          1 (x)
            34       LOAD_FAST                0 (v)
            36       BINARY_OP               13 (+=)
            40       STORE_FAST               1 (x)
            42       JUMP_BACKWARD           20 (to L1)

  2   L3:   46       END_FOR
            48       POP_TOP

  6         50       LOAD_FAST_CHECK          1 (x)
            52       RETURN_VALUE
'foo' branches:
    ex10.py 2:13-2:19 "[1, 2]" (foo@6) -> 2:8-2:9 "v" (foo@12) [for -> block]
    ex10.py 2:13-2:19 "[1, 2]" (foo@6) -> 2:13-2:19 "[1, 2]" (foo@46) [for -> out]
    ex10.py 3:11-3:16 "v > 0" (foo@22) -> 3:11-3:16 "v > 0" (foo@28) [if/while -> out]
    ex10.py 3:11-3:16 "v > 0" (foo@22) -> 3:11-3:16 "v > 0" (foo@30) [if/while -> out]

@markshannon @nedbat

CPython versions tested on:

CPython main branch

Operating systems tested on:

macOS

There's a few things going on here.
First:
The jump in if v > 0: is miscompiled to

            22       POP_JUMP_IF_TRUE         2 (to L2)
            26       JUMP_BACKWARD           12 (to L1)
      L2:   30       NOT_TAKEN

Conceptually the this is a single instruction: POP_JUMP_IF_TRUE_BACKWARD L1.
We only have one backward jump, JUMP_BACKWARD, so the assembler converts POP_JUMP_IF_TRUE_BACKWARD label
to

    POP_JUMP_IF_TRUE over
    JUMP_BACKWARD label
over:

We need to account for NOT_TAKEN here (which probably means emitting NOT_TAKEN in the assembler).
Even then, the location of the instruction following NOT_TAKEN is likely not the location of label, but that of POP_JUMP_IF_TRUE.

We don't want to prevent the compiler from generating efficient code, so we needs a means to handle these complex cases, so we'll need to handle this sys.monitoring somehow.

Since this isn't bug until we add the new branch events, I'm marking this as a feature request.

Updating the disassembly for the current code in pull/122564; the branches around the if are still unclear.

   1          0       RESUME                   0

   2          2       LOAD_CONST               1 (0)
              4       STORE_FAST               0 (x)

   3          6       LOAD_CONST               2 ((1, 2))
              8       GET_ITER
       L1:   10       FOR_ITER                18 (to L3)
             14       NOT_TAKEN
             16       STORE_FAST               1 (v)

   4         18       LOAD_FAST                1 (v)
             20       LOAD_CONST               1 (0)
             22       COMPARE_OP             148 (bool(>))
             26       POP_JUMP_IF_TRUE         3 (to L2)
             30       NOT_TAKEN
             32       JUMP_BACKWARD           13 (to L1)

  --   L2:   36       NOP

   5         38       LOAD_FAST_LOAD_FAST      1 (x, v)
             40       BINARY_OP               13 (+=)
             44       STORE_FAST               0 (x)
             46       JUMP_BACKWARD           20 (to L1)

   3   L3:   50       END_FOR
             52       POP_TOP

   7         54       LOAD_FAST                0 (x)
             56       RETURN_VALUE

'foo' branches:
    ex10.py 3:13-3:19 "[1, 2]" (foo@10) -> 3:8-3:9 "v" (foo@16) [for -> block]
    ex10.py 3:13-3:19 "[1, 2]" (foo@10) -> 3:13-3:19 "[1, 2]" (foo@50) [for -> out]
    ex10.py 4:11-4:16 "v > 0" (foo@26) -> 4:11-4:16 "v > 0" (foo@32) [if/while -> out]
    ex10.py 4:11-4:16 "v > 0" (foo@26) -> (start_line=None) (foo@36) [(dst.start_line=None)]

Latest disassembly (with offsets) on main:

   1          0       RESUME                   0

   2          2       LOAD_CONST               0 ((1, 2))
              4       GET_ITER
       L1:    6       FOR_ITER                19 (to L3)
             10       NOT_TAKEN
             12       STORE_FAST               0 (v)

   3         14       LOAD_FAST                0 (v)
             16       LOAD_SMALL_INT           0
             18       COMPARE_OP             148 (bool(>))
             22       POP_JUMP_IF_TRUE         3 (to L2)
             26       NOT_TAKEN
             28       JUMP_BACKWARD           13 (to L1)

  --   L2:   32       NOP

   4         34       LOAD_FAST_CHECK          1 (x)
             36       LOAD_FAST                0 (v)
             38       BINARY_OP               13 (+=)
             42       STORE_FAST               1 (x)
             44       JUMP_BACKWARD           21 (to L1)

   2   L3:   48       END_FOR
             50       POP_TOP

   6         52       LOAD_FAST_CHECK          1 (x)
             54       RETURN_VALUE

I don't know why the NOP at label L2 is left in, rather than being merged into the following line, but that doesn't make the generated code wrong.

The branch from 22 to L2 (32) jumps to an instruction with no line number, but execution will immediately proceed to 34 (line 4).
The "not taken" branch can likewise be followed from 26 to 28 and back to L1 (offset 6) on line 2.
In other words the "taken" branch goes from line 3 to 4 and the "not taken" branch goes from line 3 to line 2.

@jaltmayerpizzorno

On latest main the disassembly now looks like this:

  1          0       RESUME                   0

  2          2       LOAD_CONST               0 ((1, 2))
             4       GET_ITER
      L1:    6       FOR_ITER                17 (to L3)
            10       STORE_FAST               0 (v)

  3         12       LOAD_FAST                0 (v)
            14       LOAD_SMALL_INT           0
            16       COMPARE_OP             148 (bool(>))
            20       POP_JUMP_IF_TRUE         3 (to L2)
            24       NOT_TAKEN
            26       JUMP_BACKWARD           12 (to L1)

  4   L2:   30       LOAD_FAST_CHECK          1 (x)
            32       LOAD_FAST                0 (v)
            34       BINARY_OP               13 (+=)
            38       STORE_FAST               1 (x)
            40       JUMP_BACKWARD           19 (to L1)

  2   L3:   44       END_FOR
            46       POP_ITER

  6         48       LOAD_FAST_CHECK          1 (x)
            50       RETURN_VALUE

And the branches:

>>> list(foo.__code__.co_branches())
[(6, 10, 48), (20, 26, 30)]

which, to me, looks correct.
@jaltmayerpizzorno does this work for you?

@markshannon

Hi @markshannon, thank you. That 20->26 branch maps the same location in source and destination,

3:11-3:16 "v > 0" (foo@20) -> 3:11-3:16 "v > 0" (foo@26)

which I think we previously said means an exit from the function?

Anyway, I have been increasingly thinking that we may be asking for too much... we could maybe just report on the number of branches taken/existing per line, and give up on filtering out clause branches. @nedbat, what do you think?

BTW, I missed initializing x in the example:

def foo():
    x = 0
    for v in [1, 2]:
        if v > 0:
            x += v

    return x

If we continue on this, let's please use this version instead.

give up on filtering out clause branches.

I don't know what this means. It feels like we are close to getting the data we want.

give up on filtering out clause branches.

I don't know what this means. It feels like we are close to getting the data we want.

I mean filtering out the branches such as the one between the A and B in if A and B:.

@nedbat

@nedbat @jaltmayerpizzorno
Can I close this, or is there more to do?

I still am getting a branch whose destination maps back to the same portion of code... Using the code in 'main' (c6513f7), I get:

1: def foo():
2:     x = 0
3:     for v in [1, 2]:
4:        if v > 0:
5:            x += v
6:
7:     return x

Disassembly of <code object foo at 0x104c2e340, file "/Users/juan/project/slipcover/ex10.py", line 1>:
  1          0       RESUME                   0

  2          2       LOAD_SMALL_INT           0
             4       STORE_FAST               0 (x)

  3          6       LOAD_CONST               1 ((1, 2))
             8       GET_ITER
      L1:   10       FOR_ITER                20 (to L3)
            14       STORE_FAST               1 (v)

  4         16       LOAD_FAST                1 (v)
            18       LOAD_SMALL_INT           0
            20       COMPARE_OP             148 (bool(>))
            24       POP_JUMP_IF_TRUE         3 (to L2)
            28       NOT_TAKEN
            30       JUMP_BACKWARD           12 (to L1)

  5   L2:   34       LOAD_FAST_LOAD_FAST      1 (x, v)
            36       BINARY_OP               13 (+=)
            48       STORE_FAST               0 (x)
            50       JUMP_BACKWARD           22 (to L1)

  3   L3:   54       END_FOR
            56       POP_ITER

  7         58       LOAD_FAST                0 (x)
            60       RETURN_VALUE

'foo' branches:
     [(10, 14, 58), (24, 30, 34)]
    ex10.py 3:13-3:19 "[1, 2]" (foo@10) -> 3:8-3:9 "v" (foo@14)
    ex10.py 3:13-3:19 "[1, 2]" (foo@10) -> 7:11-7:12 "x" (foo@58)
    ex10.py 4:11-4:16 "v > 0" (foo@24) -> 4:11-4:16 "v > 0" (foo@30)
    ex10.py 4:11-4:16 "v > 0" (foo@24) -> 5:12-5:13 "x" (foo@34)

This is, as before, using co_positions to map offsets back to source code.

All branches but the 3rd are fairly clear. The 3rd branch, from 24 to 30, is really 4->3... there's no else, so we go back to the next for iteration (if any). Shouldn't the JUMP_BACKWARD in offset 30 really map to somewhere in line 3?

@jaltmayerpizzorno

@jaltmayerpizzorno are there some typos in your description?

I think we have the information we need. Coverage.py now follows trails of instructions until a new line is reached.

Here is what I see for the disassembly, and how the latest coverage.py code interprets it:

1:0-1:0             0       RESUME                   0

2:8-2:9             2       LOAD_SMALL_INT           0
2:4-2:5             4       STORE_FAST               0 (x)

3:13-3:19           6       LOAD_CONST               1 ((1, 2))
3:13-3:19           8       GET_ITER
3:13-3:19    L1:   10       FOR_ITER                20 (to L3)
3:8-3:9            14       STORE_FAST               1 (v)

4:10-4:11          16       LOAD_FAST                1 (v)
4:14-4:15          18       LOAD_SMALL_INT           0
4:10-4:15          20       COMPARE_OP             148 (bool(>))
4:10-4:15          24       POP_JUMP_IF_TRUE         3 (to L2)
4:10-4:15          28       NOT_TAKEN
4:10-4:15          30       JUMP_BACKWARD           12 (to L1)

5:11-5:12    L2:   34       LOAD_FAST_LOAD_FAST      1 (x, v)
5:11-5:17          36       BINARY_OP               13 (+=)
5:11-5:12          48       STORE_FAST               0 (x)
5:11-5:12          50       JUMP_BACKWARD           22 (to L1)

3:13-3:19    L3:   54       END_FOR
3:13-3:19          56       POP_ITER

7:11-7:12          58       LOAD_FAST                0 (x)
7:4-7:12           60       RETURN_VALUE

The possible branch points are instructions with jump targets that aren't unconditional jumps: offsets 10 and 24.

Offset 10 is line 3. It can proceed to 14 and then 16, which is line 4, so we have a branch from 3 to 4.
Offset 10 can jump to 54, then to 56 then 58, which is line 8, so we have a branch from 3 to 7.
Offset 24 (line 4) can proceed to 28, then 30, then 10, which is line 3, so we have a branch from 4 to 3.
Offset 24 can jump to 34, which is line 5, so we have a branch from 4 to 5.

Final result is line 3 branches to either 4 or 7, and line 4 branches to 3 or 5.

@jaltmayerpizzorno are there some typos in your description?

Quite possibly, but I don't see them... If you are referring to the tuples showing the branches, that is simply list(code.co_branches())...

I think we have the information we need. Coverage.py now follows trails of instructions until a new line is reached.

I tried that method for finding out the branch destinations for SlipCover (years ago) and found it unreliable... Essentially, I'd:

read the bytecode
for each conditional jump found, the branch source is the line that bytecode is on
to find the branch destination, track where the bytecode goes, following unconditional jumps

When do we stop tracking the bytecode, though? Stopping when you reach a new line works well for things like skipping over a for's variable initialization and into its block. But it misses same-line cases like

if x: f()

Also, while tracking, what do we do about conditional jump opcodes? Do we stop there? Do we ignore them? Or do we track both branches and extract the destination somehow from the (potentially various) resulting paths?

I think ideally we wouldn't trace the code at all, but instead rely on a given mapping (co_positions or something else, using the branch destination offset) to tell us where in the source code that branch goes to.

@nedbat

I thought I should clarify what I'm saying.

As @nedbat shared, he coded a mechanism that enumerates branches and deduces their destination by stepping through bytecode. I understand that he is satisfied that it works well enough for Coverage.py, and that's great! Seriously.

I just don't think coding something like that should be necessary to fully utilize sys.monitoring's branch feature. Most users only ever look at Python source code; the bytecode is an implementation detail. In my mind, it follows that there should be an obvious, reliable way to map from branch offsets to the source code that originated it.

I don't know if using co_locations should be that; it was designed to allow showing error messages. Perhaps it would be better to simply indicate the source code origin and destination for each branch along with the offsets in co_branches—or something else entirely. But if we don't provide something, the next tool author wanting to use sys.monitoring's branches will likely have to code around the feature like Ned did.

Navigation Menu

Repository navigation

Certain sys.monitoring "not taken" branches in a `for` loop not showing correctly #123050

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Certain sys.monitoring "not taken" branches in a for loop not showing correctly #123050

Description

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Activity

markshannon commented on Aug 20, 2024

jaltmayerpizzorno commented on Sep 16, 2024

markshannon commented on Dec 31, 2024

markshannon commented on Jan 7, 2025

jaltmayerpizzorno commented on Jan 19, 2025

jaltmayerpizzorno commented on Jan 19, 2025

nedbat commented on Jan 20, 2025

jaltmayerpizzorno commented on Jan 22, 2025

markshannon commented on Feb 27, 2025

jaltmayerpizzorno commented on Mar 2, 2025

nedbat commented on Mar 3, 2025

jaltmayerpizzorno commented on Mar 3, 2025

jaltmayerpizzorno commented on Mar 7, 2025

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

Certain sys.monitoring "not taken" branches in a `for` loop not showing correctly #123050