Improve pattern matching

[pjljvandelaar]

The current implementation of match pattern fails in some cases. This is however not needed.

($M_X, $M_X) fails on (1,2,3,1,2,3)

($M_X, 1,1, $M_Y) fails on (1,2,1,1,3,4)

($M_X, $S_Y, $S_Z) fails on (1,2,3)

Note we should not backtrack with ($M_Args) on (1,2,3,4,5,6), just match on length: $M_Args has length of 6!

Note: ($M_X, 1,1, $M_Y) on (1,1,2,1,1,3,4) has 2 solutions: not only pattern but also instance determines number of matches

Solution

• Known lengths
  • actual ASTnodes
  • single place holders
  • already known/decided multiplaceholders
• Bag of unknown multi placeholders [match with list instance]
  • Only one multi placeholders: length can be determined (length instance - sum of known length) / occurrence of multi placeholder
  • Pick a multi placeholder: iterate length from 0 to (length instance - sum of known length) / occurrence of multi

Point of attention (ignore patterns - present in C++ version)

[pjljvandelaar]

Should we introduce the category of overlapping and non-overlapping matches (comparable to contained and non-contained matches)?

I think it is relevant for replacements: I don't think we can find an acceptable definition for replacing overlapping matches!

If so, can we check it locally (at a list) or do we need to check it globally?

[pjljvandelaar]

How many matches should be found when searching with the pattern f ($$before, 1, 1, $$after); on the instances such as

• f (1, 1, 1); - 1 or 2? and
• f (1, 1, 1, 1); - 2 or 3?

[pjljvandelaar]

Where single placeholders just claim a place /AST node in the list of AST nodes, an actual AST node divides the list in parts.

matching ($$before, a, $$after) on pattern (c, b, a, b, c, b, a, b, c) (1, 2, 3, 4, 5, 6, 7, 8, 9) has only two valid location for a: position 3 and position 7.

So we could use standard find functionality to split the instance, and do pattern matching on the remaining / split sublists!

[pjljvandelaar]

Maybe we should do something special for the head and tail elements when the pattern contains actual AST nodes there: we can check them, if different -> no match if the same -> continue with smaller sublist.

[pjljvandelaar]

Done in latest release

[pjljvandelaar]

Only done for C/C++ version - So need to keep it open for the Ada version.