Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
jaltmayerpizzorno opened this issue Aug 15, 2024 · 13 comments
Open

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

jaltmayerpizzorno opened this issue Aug 15, 2024 · 13 comments
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) type-feature A feature request or enhancement

Comments

@jaltmayerpizzorno
Copy link

jaltmayerpizzorno commented Aug 15, 2024 •
edited by github-actions bot
Loading

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
@jaltmayerpizzorno jaltmayerpizzorno added the type-bug An unexpected behavior, bug, or error label Aug 15, 2024
@jaltmayerpizzorno jaltmayerpizzorno mentioned this issue Aug 15, 2024
Merged
@picnixz picnixz added the interpreter-core (Objects, Python, Grammar, and Parser dirs) label Aug 16, 2024
@markshannon markshannon mentioned this issue Aug 16, 2024
Open
@markshannon
Copy link
Member

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.

@markshannon markshannon added type-feature A feature request or enhancement and removed type-bug An unexpected behavior, bug, or error labels Aug 20, 2024
@markshannon markshannon mentioned this issue Aug 20, 2024
Open
@jaltmayerpizzorno
Copy link
Author

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)]

@markshannon
Copy link
Member

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.

@markshannon
Copy link
Member

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?

@jaltmayerpizzorno
Copy link
Author

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?

@jaltmayerpizzorno
Copy link
Author

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.

@nedbat
Copy link
Member

nedbat commented Jan 20, 2025

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.

@jaltmayerpizzorno
Copy link
Author

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:.

@markshannon
Copy link
Member

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

@jaltmayerpizzorno
Copy link
Author

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?

@nedbat
Copy link
Member

nedbat commented Mar 3, 2025

@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
Copy link
Author

jaltmayerpizzorno commented Mar 3, 2025 •
edited
Loading

@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.

@jaltmayerpizzorno jaltmayerpizzorno mentioned this issue Mar 3, 2025
Merged
@jaltmayerpizzorno
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) type-feature A feature request or enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@nedbat @markshannon @picnixz @jaltmayerpizzorno