Types reduce too early in Depth

[ptal]

Consider the following grammar:

  underscore = "_"
  digits = (underscore* digit)+ > id
  digit = ["0-9"]

  fn id(v: Vec<char>) -> Vec<char> {
    v
  }

There is a type mismatch because the type inferred of (underscore* digit)+ is Vec<(Vec<()>, char)> instead of Vec<char>. The problem is due to the depth algorithm:

1. Surface is called and underscore has the type (^), however (underscore* digit)+ is not typed since it is under a semantic action.
2. Depth is called and reduce the type of underscore to () because of the final type reduction (TypeRewriting::final_reduce).
3. Surface is called by depth on (underscore* digit)+ but it is too late because underscore has already be reduced.

The possible solutions are:

• Topological sort of the rules such as digits would be executed first. However since we have loop, it should be a multi-layered topological sort (one per call to surface) and it seems overly complex.
• Re-engineering of the final reduction:
  1. After the first call to surface we know that every rule should have a type, therefore we can safely reduce rec to (^).
  2. Launch Depth and do not reduce (^) in visit_expr.
  3. Final reduction of the expression annotated with (^) to ().