Lalrpop 0.20.2 exception "no entry found for key"

[Storyyeller]

Repo: Storyyeller/cubiml-demo@502da7a

run "RUST_BACKTRACE=full lalrpop src/grammar.lalr"

produces the error

processing file `src/grammar.lalr`
thread 'main' panicked at /home/rsg/.cargo/registry/src/index.crates.io-6f17d22bba15001f/lalrpop-0.20.2/src/lr1/lane_table/construct/merge.rs:203:35:
no entry found for key
stack backtrace:
   0:     0x563f5a075586 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h67bb2d10ecb8af10
   1:     0x563f5a0987f0 - core::fmt::write::h5987d5bee25e3bd6
   2:     0x563f5a072f9f - std::io::Write::write_fmt::h0876e0f4bddb923c
   3:     0x563f5a075364 - std::sys_common::backtrace::print::h1d97d5831d0262fb
   4:     0x563f5a0768c7 - std::panicking::default_hook::{{closure}}::h39fabb1b3e65f47a
   5:     0x563f5a076629 - std::panicking::default_hook::h416520d6bb2cb53f
   6:     0x563f5a076d58 - std::panicking::rust_panic_with_hook::h99ef5cbc4b3b0ae4
   7:     0x563f5a076c32 - std::panicking::begin_panic_handler::{{closure}}::h2284f60633c08873
   8:     0x563f5a075a86 - std::sys_common::backtrace::__rust_end_short_backtrace::h84bc49437da26b5c
   9:     0x563f5a076984 - rust_begin_unwind
  10:     0x563f59dd5685 - core::panicking::panic_fmt::hfa0af2309df9012f
  11:     0x563f59dd5643 - core::option::expect_failed::hee4b38d562c1aee6
  12:     0x563f59ebb3be - lalrpop::lr1::lane_table::construct::merge::ContextSets::union::h4b30069552aa0692
  13:     0x563f59eba3fc - lalrpop::lr1::lane_table::construct::merge::Merge::walk::h8c444bf665268054
  14:     0x563f59eb9dcd - lalrpop::lr1::lane_table::construct::merge::Merge::start::h5f6b8034a006f3f3
  15:     0x563f59f0dce5 - lalrpop::lr1::lane_table::construct::LaneTableConstruct::construct::hb8c92e7d18984d4c
  16:     0x563f59de8ed4 - lalrpop::lr1::lane_table::build_lane_table_states::h43ea42028cbdd64f
  17:     0x563f59eeeb6b - lalrpop::lr1::build::build_lr1_states::h57c4adf8e06ee2bf
  18:     0x563f59e88c21 - lalrpop::lr1::build_states::h595add96ad68ebc1
  19:     0x563f59de390d - lalrpop::build::process_file_into::hc55a95faee152d69
  20:     0x563f59ddae92 - lalrpop::build::process_file::h95c324464dd82c3a
  21:     0x563f59dd8662 - lalrpop::api::Configuration::process_file::h909a3be569a4f8d5
  22:     0x563f59dd7bbf - lalrpop::main::ha7aa5380d9a52229
  23:     0x563f59ddab13 - std::sys_common::backtrace::__rust_begin_short_backtrace::heb7abe9d39a778b9
  24:     0x563f59ddab31 - std::rt::lang_start::{{closure}}::h69aa2e285f69979b
  25:     0x563f5a06dc81 - std::rt::lang_start_internal::h000d84e53c076064
  26:     0x563f59dd7fe5 - main
  27:     0x7f5c274f9083 - __libc_start_main
                               at /build/glibc-e2p3jK/glibc-2.31/csu/../csu/libc-start.c:308:16
  28:     0x563f59dd5e3e - _start
  29:                0x0 - <unknown>

lalrpop version is 0.20.2

[dburgener]

Thanks for the report! I'm looking into this.

This part of the code is hit when the grammar is not LALR(1), so the lane table algorithm needs to split states in order to resolve inconsistencies. I checked our existing test coverage, and we have a few tests that hit this path, but all of them resolve shift-reduce conflicts, while this grammar needs to resolve a reduce-reduce conflict (Note that this is not an actual conflict in the grammar, but rather a step in the lane table algorithm, which initially treats the grammar as LR(0), and then resolves conflicts as needed in order to handle full LR(1) in a space efficient way). So I imagine this code path just doesn't have much test coverage.

It looks to me as though the problem is that the conflicting state isn't being added to the lane table, leading to the panic reported here, since we attempt to access the state when resolving. I tried simply adding it to the lane table, but that seems to cause a lot of reduce/reduce conflicts in valid grammars - I'm not sure why. That's all pretty tentative.

My next step will be to try to come up with a much more minimal reproducer that will be easier to reason about. We'll need that anyways to add test coverage for this case. Hopefully with a smaller reproducer it will be easier to figure out exactly what's going on here.

My time over the next few days to work on this will likely be spotty, but I wanted to update that I'm looking at it and slowly narrowing in towards a root cause.

[dburgener]

The minimal example came together quicker than I expected. I can reproduce with this grammar:

grammar;

pub G2 = {
        "a" X "d",
        "a" Y "c",
        "b" X "c",
        "b" Y "d",
};

X = {
        "e"
};

Y = {
        "e"
};

This is based on the G1 grammar described here, which we test. The difference is that while the actual conflict in G1 is reduce/reduce, it happens that the conflicting state also has a shift action. This grammar, which I'm calling G2 has a reduce/reduce conflict that can be resolved via the lane table, but no additional shift action.

The code adds the original state to the lane table on a shift action, but not a reduce action, so the presence of a consistent shift action ensures that the missing state ends up in the lane table. I'm pretty sure we need to get that state into the table in this case as well, but my naive attempts to do that have broken other things, so I need to investigate exactly why.

[dburgener]

Okay, I think I have it. Some tweaks to exactly how I added the state to the lane table, and things are mostly working. The G2 grammar I posted above builds successfully, and the cubimpl grammar shared in the report no longer panics, but instead produces conflict messages. That grammar is pretty involved, so I have no idea if it should be valid or not, but we're not panicing anymore, so I suspect the conflicts are legitimate, particular since the more understandable G2 works.

I need to do some cleanup and put G2 into a unit test, and then I'll submit a PR.