Match statements by arihant2math · Pull Request #5485 · RustPython/RustPython · GitHub

This pr turns the parsed AST of a match-case statement into bytecode for the VM.

Progress:

Add NOP instruction
Add SWAP instrution
compile_match
compile_match_inner
compile_pattern
compile_pattern_value
compile_pattern_singleton
compile_pattern_sequence (requires instruction MATCH_SEQUENCE instruction)
compile_pattern_mapping
compile_pattern_class
compile_pattern_star
compile_pattern_as
compile_pattern_or
Add optimized support for default case requires compile_pattern_as first (might be done in a separate pr)
Add tests

Resolves: #4770

awesome, you already got the key parts

It almost finishes codegen, the only problem faced right now is this error:

D:/Documents/Programming/GitHub/RustPython/target/debug/rustpython.exe match_test.py
thread 'main' panicked at compiler\codegen\src\compile.rs:3287:9:
assertion `left == right` failed: switching to completed block
  left: BlockIdx(2)
 right: BlockIdx(4294967295)
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\panicking.rs:665
   1: core::panicking::panic_fmt
             at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/core\src\panicking.rs:76
   2: core::panicking::assert_failed_inner
             at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/core\src\panicking.rs:413
   3: core::panicking::assert_failed<rustpython_codegen::ir::BlockIdx,rustpython_codegen::ir::BlockIdx>
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\panicking.rs:373
   4: rustpython_codegen::compile::Compiler::switch_to_block
             at .\compiler\codegen\src\compile.rs:3287
   5: rustpython_codegen::compile::Compiler::compile_match_inner
             at .\compiler\codegen\src\compile.rs:1997
   6: rustpython_codegen::compile::Compiler::compile_match
             at .\compiler\codegen\src\compile.rs:2012
   7: rustpython_codegen::compile::Compiler::compile_statement
             at .\compiler\codegen\src\compile.rs:771
   8: rustpython_codegen::compile::Compiler::compile_statements
             at .\compiler\codegen\src\compile.rs:501
   9: rustpython_codegen::compile::Compiler::compile_program
             at .\compiler\codegen\src\compile.rs:416
  10: core::ops::function::FnOnce::call_once<enum2$<core::result::Result<tuple$<>,rustpython_parser_core::source_code::LocatedError<enum2$<rustpython_codegen::error::CodegenErrorType> > > > (*)(ref_mut$<rustpython_codegen::compile::Compiler>,ref$<slice2$<enum2$<
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ops\function.rs:250
  11: rustpython_codegen::compile::compile_impl<slice2$<enum2$<rustpython_ast::generic::Stmt<rustpython_parser_core::source_code::SourceRange> > >,enum2$<core::result::Result<rustpython_codegen::symboltable::SymbolTable,rustpython_codegen::symboltable::SymbolTab
             at .\compiler\codegen\src\compile.rs:138
  12: rustpython_codegen::compile::compile_program
             at .\compiler\codegen\src\compile.rs:150
  13: rustpython_codegen::compile::compile_top
             at .\compiler\codegen\src\compile.rs:110
  14: rustpython_compiler::compile
             at .\compiler\src\lib.rs:66
  15: rustpython_vm::vm::VirtualMachine::compile_with_opts
             at .\vm\src\vm\compile.rs:26
  16: rustpython_vm::vm::VirtualMachine::compile
             at .\vm\src\vm\compile.rs:16
  17: rustpython_vm::vm::VirtualMachine::run_code_string
             at .\vm\src\vm\compile.rs:61
  18: rustpython_vm::vm::VirtualMachine::run_script
             at .\vm\src\vm\compile.rs:49
  19: rustpython::run_rustpython
             at .\src\lib.rs:206
  20: rustpython::run::closure$0<rustpython::main::closure_env$0>
             at .\src\lib.rs:99
  21: rustpython_vm::vm::interpreter::impl$0::run::closure$0<rustpython::run::closure_env$0<rustpython::main::closure_env$0> >
             at .\vm\src\vm\interpreter.rs:104
  22: rustpython_vm::vm::interpreter::impl$0::enter::closure$0<rustpython_vm::vm::interpreter::impl$0::run::closure_env$0<rustpython::run::closure_env$0<rustpython::main::closure_env$0> >,enum2$<core::result::Result<tuple$<>,rustpython_vm::object::core::PyRef<ru
             at .\vm\src\vm\interpreter.rs:72
  23: core::panic::unwind_safe::impl$25::call_once<enum2$<core::result::Result<tuple$<>,rustpython_vm::object::core::PyRef<rustpython_vm::exceptions::types::PyBaseException> > >,rustpython_vm::vm::interpreter::impl$0::enter::closure_env$0<rustpython_vm::vm::inte
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\panic\unwind_safe.rs:272
  24: std::panicking::try::do_call<core::panic::unwind_safe::AssertUnwindSafe<rustpython_vm::vm::interpreter::impl$0::enter::closure_env$0<rustpython_vm::vm::interpreter::impl$0::run::closure_env$0<rustpython::run::closure_env$0<rustpython::main::closure_env$0>
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:557
  25: std::panic::catch_unwind<core::panic::unwind_safe::AssertUnwindSafe<rustpython_vm::vm::interpreter::impl$0::enter::closure_env$0<rustpython_vm::vm::interpreter::impl$0::run::closure_env$0<rustpython::run::closure_env$0<rustpython::main::closure_env$0> >,en
  26: std::panicking::try
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panicking.rs:520
  27: std::panic::catch_unwind<core::panic::unwind_safe::AssertUnwindSafe<rustpython_vm::vm::interpreter::impl$0::enter::closure_env$0<rustpython_vm::vm::interpreter::impl$0::run::closure_env$0<rustpython::run::closure_env$0<rustpython::main::closure_env$0> >,en
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\panic.rs:358
  28: rustpython_vm::vm::thread::enter_vm::closure$0<enum2$<core::result::Result<tuple$<>,rustpython_vm::object::core::PyRef<rustpython_vm::exceptions::types::PyBaseException> > >,rustpython_vm::vm::interpreter::impl$0::enter::closure_env$0<rustpython_vm::vm::in
             at .\vm\src\vm\thread.rs:31
  29: std::thread::local::LocalKey<core::cell::RefCell<alloc::vec::Vec<core::ptr::non_null::NonNull<rustpython_vm::vm::VirtualMachine>,alloc::alloc::Global> > >::try_with<core::cell::RefCell<alloc::vec::Vec<core::ptr::non_null::NonNull<rustpython_vm::vm::Virtual
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\thread\local.rs:283
  30: std::thread::local::LocalKey<core::cell::RefCell<alloc::vec::Vec<core::ptr::non_null::NonNull<rustpython_vm::vm::VirtualMachine>,alloc::alloc::Global> > >::with<core::cell::RefCell<alloc::vec::Vec<core::ptr::non_null::NonNull<rustpython_vm::vm::VirtualMach
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\std\src\thread\local.rs:260
  31: rustpython_vm::vm::thread::enter_vm<enum2$<core::result::Result<tuple$<>,rustpython_vm::object::core::PyRef<rustpython_vm::exceptions::types::PyBaseException> > >,rustpython_vm::vm::interpreter::impl$0::enter::closure_env$0<rustpython_vm::vm::interpreter::
             at .\vm\src\vm\thread.rs:28
  32: rustpython_vm::vm::interpreter::Interpreter::enter<rustpython_vm::vm::interpreter::impl$0::run::closure_env$0<rustpython::run::closure_env$0<rustpython::main::closure_env$0> >,enum2$<core::result::Result<tuple$<>,rustpython_vm::object::core::PyRef<rustpyth
             at .\vm\src\vm\interpreter.rs:72
  33: rustpython_vm::vm::interpreter::Interpreter::run<rustpython::run::closure_env$0<rustpython::main::closure_env$0> >
             at .\vm\src\vm\interpreter.rs:104
  34: rustpython::run<rustpython::main::closure_env$0>
             at .\src\lib.rs:99
  35: rustpython::main
             at .\src\main.rs:2
  36: core::ops::function::FnOnce::call_once<std::process::ExitCode (*)(),tuple$<> >
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ops\function.rs:250
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

What seems to be happening is the self.switch_to_block(end_block); from the let end_block = self.new_block(); isn't working because of a previous block having been completed. I tried moving instantiation around but it didn't fix it. @youknowone how should I proceed?

When I encountered similar issue before, it was related to wrong order of value stack/block stack operations. #5275 was one of them
Could you share match_test.py?

Currently there is a test in compile.rs called test_match that reproduces the issue (the code is identical).

https://github.com/arihant2math/RustPython/blob/a1586d0089868e87bb8cc887ce5f1f1802341437/compiler/codegen/src/compile.rs#L3728C1-L3742C6

Though I don't know well how this blocks are working, switch_to_block in jump_to_fail_pop doesn't look safe.

@coolreader18 do you have advices?

I merged #5489 for easier debug.
Here is my rough suggestion how to create and switch to blocks:
3720152
As I understand, when any jump might happen, they must be separated as blocks. In match statement, pattern guard can jump to next pattern. Then a pattern need at least one block.

The cpython implementation also has a hacky way of popping things off the stack (by repeatedly switching to blocks) and I'm not sure that's going to run without panicking anymore

Seems like codegen almost works, it's currently getting an u32::MAX mixed in somewhere it's not supposed to be however.

Debug printing:

===BLOCK 0===
LoadConst("one"): 0 +1 => 1
StoreLocal(0, v): 1 -1 => 0
LoadNameAny(0, v): 0 +1 => 1
Duplicate: 1 +1 => 2
LoadConst("one"): 2 +1 => 3
CompareOperation(Equal): 3 -1 => 2
Pop: 2 -1 => 1
LoadConst("two"): 1 +1 => 2
StoreLocal(0, v): 2 -1 => 1
Jump(5): 1 +0 => 1
===BLOCK 5===
index out of bounds: the len is 7 but the index is 4294967295
thread 'compile::tests::test_match' panicked at compiler\codegen\src\ir.rs:311:28:
index out of bounds: the len is 7 but the index is 4294967295
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/std\src\panicking.rs:665
   1: core::panicking::panic_fmt
             at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/core\src\panicking.rs:76
   2: core::panicking::panic_bounds_check
             at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/core\src\panicking.rs:281
   3: rustpython_codegen::ir::stackdepth_push
             at .\src\ir.rs:311
   4: rustpython_codegen::ir::CodeInfo::max_stackdepth
             at .\src\ir.rs:277
   5: rustpython_codegen::ir::CodeInfo::finalize_code
             at .\src\ir.rs:88
   6: rustpython_codegen::compile::Compiler::pop_code_object
             at .\src\compile.rs:365
   7: rustpython_codegen::compile::tests::compile_exec
             at .\src\compile.rs:3675
   8: rustpython_codegen::compile::tests::test_match
             at .\src\compile.rs:3737
   9: rustpython_codegen::compile::tests::test_match::closure$0
             at .\src\compile.rs:3736
  10: core::ops::function::FnOnce::call_once<rustpython_codegen::compile::tests::test_match::closure_env$0,tuple$<> >
             at C:\Users\ariha\.rustup\toolchains\stable-x86_64-pc-windows-msvc\lib\rustlib\src\rust\library\core\src\ops\function.rs:250
  11: core::ops::function::FnOnce::call_once
             at /rustc/9fc6b43126469e3858e2fe86cafb4f0fd5068869\library/core\src\ops\function.rs:250
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Seems like all the blocks target u32::MAX as their next block. I modified them to point at the next block as their target and string together that way.

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

Currently the output is as follows:

===BLOCK 0===
LoadConst(0): 0 +1 => 1
LoadConst(None): 1 +1 => 2
ImportName(0, sys): 2 -1 => 1
StoreLocal(0, sys): 1 -1 => 0
LoadNameAny(0, sys): 0 +1 => 1
LoadAttr(1, path): 1 +0 => 1
LoadMethod(2, insert): 1 +2 => 3
LoadConst(0): 3 +1 => 4
LoadConst(""): 4 +1 => 5
CallMethodPositional(2): 5 -4 => 1
Pop: 1 -1 => 0
ReturnConst(None): 0 +0 => 0
DONE: 5
created pattern_blocks: BlockIdx(1) - BlockIdx(5)(end block)
linking: 1 -> 2
linking: 2 -> 3
linking: 3 -> 4
linking: 4 -> 5
linking: 5 -> 7
0
0: 4294967295 28
1: 2 0
2: 3 0
3: 4 0
4: 5 0
5: 7 0
6: 4294967295 0
7: 4294967295 0
switch_to_block BlockIdx(0) -> BlockIdx(7)
block: 1 -> 2
block: 2 -> 3
block: 3 -> 4
block: 4 -> 5
block: 5 -> 7
block: 7 -> 4294967295
===BLOCK 0===
LoadConst("one"): 0 +1 => 1
StoreLocal(0, v): 1 -1 => 0
LoadNameAny(0, v): 0 +1 => 1
Duplicate: 1 +1 => 2
LoadConst("one"): 2 +1 => 3
CompareOperation(Equal): 3 -1 => 2
Pop: 2 -1 => 1
LoadConst("two"): 1 +1 => 2
StoreLocal(0, v): 2 -1 => 1
Jump(5): 1 +0 => 1
===BLOCK 5===
===BLOCK 7===
ReturnConst(None): 1 +0 => 1
DONE: 3
[vm\src\frame.rs:2103:9] self = ExecutingFrame {
    code: code: <code object <module> at ??? file "match_test.py", line 1>,
    state: FrameState {
        stack: [
            [PyObject PyStr { value: "one", kind: Ascii, hash: -1 }],
            [PyObject PyStr { value: "one", kind: Ascii, hash: -1 }],
            [PyObject PyStr { value: "one", kind: Ascii, hash: -1 }],
        ],
        blocks: [],
        lasti: 5,
    },
}
thread 'main' panicked at vm\src\frame.rs:522:22:
tried to push value onto stack but overflowed max_stackdepth
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: process didn't exit successfully: `target\debug\rustpython.exe match_test.py` (exit code: 101)

for

# match_test.py
v = "one"
match v:
    case "one":
        v = "two"
    case "two":
        v = "three"
    case "three":
        v = "one"
    case _:
        v = "one"

If you'd like to investigate how stackdepth work, trying this issue probably be helpful #5154

I think I will try solving this by carefully checking the generated instructions

Expression: compile_exec(
    r#"\
match v:
    case "one":
        v = "two"
    case "two":
        v = "three"
    case "three":
        v = "one"
    case _:
        v = "one"
"#,
)
───────────────────────────────────────────────────────────────────────────────
+new results
────────────┬──────────────────────────────────────────────────────────────────
          0 │+  2     >>    0 LoadNameAny          (0, v)
          1 │+              1 Duplicate
          2 │+
          3 │+  3           2 LoadConst            ("one")
          4 │+              3 CompareOperation     (Equal)
          5 │+              4 Pop
          6 │+
          7 │+  4           5 LoadConst            ("two")
          8 │+              6 StoreLocal           (0, v)
          9 │+              7 Jump                 (0)
         10 │+              8 Duplicate
         11 │+
         12 │+  5           9 LoadConst            ("two")
         13 │+             10 CompareOperation     (Equal)
         14 │+             11 Pop
         15 │+
         16 │+  6          12 LoadConst            ("three")
         17 │+             13 StoreLocal           (0, v)
         18 │+             14 Jump                 (0)
         19 │+             15 Duplicate
         20 │+
         21 │+  7          16 LoadConst            ("three")
         22 │+             17 CompareOperation     (Equal)
         23 │+             18 Pop
         24 │+
         25 │+  8          19 LoadConst            ("one")
         26 │+             20 StoreLocal           (0, v)
         27 │+             21 Jump                 (0)
         28 │+             22 Pop
         29 │+
         30 │+ 10          23 LoadConst            ("one")
         31 │+             24 StoreLocal           (0, v)
         32 │+             25 Jump                 (0)
         33 │+             26 ReturnConst          (None)
────────────┴──────────────────────────────────────────────────────────────────

the issue is that everything is jumping to line 0 for no reason (see line 21, line 9, and line 32 of the bytecode)

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

Ok I rewrote some parts of it and it works for basic match statements now.

@youknowone do I have to pop stuff from the stack when I'm done with it?
Currently I'm just doing JumpIfFalse directly after the comparison without popping anything.

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

If there are redundant stack elements for other purpose, yes, I guess so.
But every instruction has its own expectation for stack changes. So when everything goes well and my changes were correct about stack, they just fit easy. where do you find the redundant elements?

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

Due to the other functions being much more complicated than expected I think we can let this PR be merged for now and I can follow up with more PRs that fix the unimplemented sections.

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

If there are redundant stack elements for other purpose, yes, I guess so. But every instruction has its own expectation for stack changes. So when everything goes well and my changes were correct about stack, they just fit easy. where do you find the redundant elements?

See compile_pattern_inner and compile_pattern_value, the values are not popped at the end.

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

I agree to merge it. It compiles without panic. It is already a big progress

@arihant2math I removed unused nop, swap op in this merge. Please cherry-pick this commit to get it back

youknowone@64f4d7f

youknowone marked this pull request as ready for review January 21, 2025 14:52

youknowone marked this pull request as draft January 21, 2025 14:53

arihant2math force-pushed the match-statements branch 2 times, most recently from a1586d0 to be4df5d Compare January 21, 2025 19:31

arihant2math force-pushed the match-statements branch from f644179 to be4df5d Compare January 21, 2025 23:31

arihant2math added 15 commits January 21, 2025 23:36

initial stub implementation of match statements

9fbd359

formatting

bfb4091

solved compilation errors

c021326

almost working

6c7a543

formatting

8617786

as and * support for switch case

a01240f

replace todos with errors

d8c4cff

fix compile

aaccadb

added Noop instruction

f9d2418

finished default for switch case

5839dfd

fix compile

40e380e

formatting

8af2c42

more implementation

0774cbd

rename codegen_* to compile_*

cd0f1cf

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

implement SWAP instruction

223fbe4

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

arihant2math force-pushed the match-statements branch from 45c622e to aa6a040 Compare January 22, 2025 07:36

formatting

822d565

basic match statement working

ad164c0

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

basic match statement working

e955ede

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

arihant2math added 3 commits January 22, 2025 20:29

working as pattern (default works too by extension)

4649898

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

fix rust tests

493fc6e

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

cleanup

fe7f8a3

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

arihant2math marked this pull request as ready for review January 23, 2025 08:11

fix clippy errors

805757a

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

formatting

b176f9c

Signed-off-by: Ashwin Naren <arihant2math@gmail.com>

arihant2math mentioned this pull request Jan 23, 2025

Bytecode updates for match statements #5491

Closed

6 tasks

youknowone force-pushed the match-statements branch 2 times, most recently from 64f439f to ed55da1 Compare January 25, 2025 13:55

trivial edits

8e78c6d

youknowone force-pushed the match-statements branch from ed55da1 to 1ca706c Compare January 25, 2025 14:00

youknowone approved these changes Jan 25, 2025

View reviewed changes

Remove currently unused Nop,Swap op

4beef2c

youknowone force-pushed the match-statements branch from 1ca706c to 4beef2c Compare January 25, 2025 14:05

youknowone merged commit 396a0ca into RustPython:main Jan 25, 2025

arihant2math deleted the match-statements branch February 3, 2025 18:11

Match statements by arihant2math · Pull Request #5485 · RustPython/RustPython · GitHub

Uh oh!

Match statements - #5485

Match statements#5485youknowone merged 27 commits intoRustPython:mainRustPython/RustPython:mainfrom arihant2math:match-statementsarihant2math/RustPython:match-statementsCopy head branch name to clipboard

Conversation

arihant2math commented Jan 19, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

youknowone commented Jan 20, 2025

Uh oh!

arihant2math commented Jan 20, 2025

Uh oh!

youknowone commented Jan 21, 2025

Uh oh!

arihant2math commented Jan 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

youknowone commented Jan 21, 2025

Uh oh!

youknowone commented Jan 21, 2025

Uh oh!

youknowone commented Jan 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

arihant2math commented Jan 21, 2025

Uh oh!

arihant2math commented Jan 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

arihant2math commented Jan 22, 2025

Uh oh!

arihant2math commented Jan 22, 2025

Uh oh!

youknowone commented Jan 22, 2025

Uh oh!

arihant2math commented Jan 22, 2025

Uh oh!

arihant2math commented Jan 22, 2025

Uh oh!

arihant2math commented Jan 22, 2025

Uh oh!

youknowone commented Jan 23, 2025

Uh oh!

arihant2math commented Jan 23, 2025

Uh oh!

arihant2math commented Jan 23, 2025

Uh oh!

youknowone commented Jan 25, 2025

Uh oh!

youknowone commented Jan 25, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Match statements#5485
youknowone merged 27 commits into
RustPython:mainfrom
arihant2math:match-statements

arihant2math commented Jan 19, 2025 •
edited
Loading

arihant2math commented Jan 21, 2025 •
edited
Loading

youknowone commented Jan 21, 2025 •
edited
Loading

arihant2math commented Jan 21, 2025 •
edited
Loading