ptal / oak

A typed parser generator embedded in Rust code for Parsing Expression Grammars
Apache License 2.0
142 stars 14 forks source link

Bad inference due to visit order (random compile-error because of `HashMap`) #65

Closed ptal closed 9 years ago

ptal commented 9 years ago

This error rarely occurs because it surely a problem due to the random traversal of a HashMap. We must investigate the bottom-up and top-down algorithms.

➜  oak git:(master) ✗ cargo test
   Compiling oak v0.1.2 (file:///home/ptalbot/repositories/oak)
tests/testoak.rs:1:1: 137:2 error: mismatched types:
 expected `core::result::Result<oak_runtime::ParseState<collections::vec::Vec<()>>, _>`,
    found `core::result::Result<oak_runtime::ParseState<()>, collections::string::String>`
(expected struct `collections::vec::Vec`,
    found ()) [E0308]
(internal compiler error: unprintable span)
note: in expansion of closure expansion
tests/grammars/ntcc.rs:18:1: 137:2 note: expansion site
tests/testoak.rs:15:1: 321:1 note: in expansion of grammar!
tests/grammars/ntcc.rs:18:1: 137:2 note: expansion site
tests/testoak.rs:1:1: 137:2 help: run `rustc --explain E0308` to see a detailed explanation
error: aborting due to previous error
Could not compile `oak`.

To learn more, run the command again with --verbose.
ptal commented 9 years ago

Consider the grammar ntcc, after IntraRule::propagate, the following rules (forming a cycle) have types:

expression: (^)
expression2: Vec<()>
sum: Vec<()>
sum_body: ()
when: ()

The problem is that types infered by InterRule::propagate depends on the order in which we visit these rules. Indeed, the type of expression2 is not modified if we start with sum since the type of sum is modified after we visit the rules, and expression2 has the type of sum before the loop is closed. The top-down and bottom-up unit propagation algorithm could probably be merged into a flow graph algorithm. However, this should not impact the correctness of the code after fixing this bug. Because we do not really care about performance (it is already fast enough), we can call InterRule::propagate twice. It fixes the bug which is provoked by rules that form a loop r1 -> r2 -> ... -> rN while calling each others. If we start by propagating ei, it is possible that e(i-1) has not the good type, notably for invisibility, since the type of ei is being computed.