Alternative graph matching

I am currently stuck on several recipes (fuseToMetaOps, improved version of fuseMulAdd, work-in-progress mergeCopyTape...) because there are still some open issues with GraphRegex. As GraphRegex development is currently on idle, I propose for the time being to merge an alternative, simple graph matching implementation that can be used side by side with GraphRegex when needed, at least the time GraphRegex issues are solved. While this graph matching is currently on the separate experimental branch, I cannot progress on the dev branch on current features requiring it without merge.

As a reminder, here are the GraphRegex issues that still need to be addressed:

• #112 (closed)
• #91 (closed) (fix not merged yet)
• #30 (closed) (not a blocking issue)

Please note that the implementations of GraphRegex and this aternative graph matching are completely different. GraphRegex use an intermediate AST representation for the matching (with a lot of flexibility and potential for intermediate input/output formats adaptation and graph generation), whereas this alternative graph matching use a direct recursive parse and match approach (with some restrictions in the query formulation and with no evolutivity in mind).

. . .

Alternative graph matching rules:

• The first node of the first sequence is the root node and cannot be optional

  • WRONG: Conv?->ReLU (will throw an error)
  • GOOD: ReLU<-Conv?

• The first node of any further sequence must be an existing anchor (the anchor cannot be in the middle of the sequence)

  • WRONG: Conv->ReLU;Pad->Conv (will throw an error)
  • GOOD: Conv#->ReLU;Conv#<-Pad
  • WRONG: Pad->Conv;Conv->ReLU (will throw an error)
  • GOOD: Pad->Conv#;Conv#->ReLU

• Any node already matched cannot be matched again (except for anchors)

• By default, an edge matches the first output to the first input.

  • EXAMPLE: ReLU->Conv is equivalent to ReLU-0-0>Conv
    • To match the second input, use ReLU-0-1>Conv (or ReLU-1>Conv)
    • To match the second output, use ReLU-1-0>Conv
    • To match any input and/or any output, use *, like ReLU-1-*>Conv or ReLU-*-0>Conv or ReLU-*-*>Conv
    • The same is true for the <- edge syntax.

• When several nodes could match for a given node query, the first one not already in the matching result is matched, following the childs/parents ordered node list

  • EXAMPLE: Producer in Conv<*-Producer will match the weights Producer first
  • EXAMPLE: Producer in Conv#<1-.;Conv#<*-Producer will match the bias Producer because the weights Producer has already been matched

• One always matches a sub-graph: additional connections can exist anywhere in the matched sub-graph

  • EXAMPLE: Add<*-. will match the Add operator and its first input, any additional inputs will not be included in the result
  • EXAMPLE: (Add#<*-.)+ will match the Add operator and all of its inputs. Note that the anchor is required since we intend to match several inputs of the same node!

• In Aidge, a node output can be connected to multiple other nodes. In your query, you can allow it or not, with the ~ or - modifier.

  • EXAMPLE: Conv->ReLU will match the Conv that are only connected a ReLU node at their output #0.
  • EXAMPLE: Conv~>ReLU will match all the Conv connected to a ReLU even if they are also connected to other nodes at the same output #0.
  • When implementing a match & replace recipe, beware that you don't break branches in the middle of your matching result if you use ~!

• The matching results can be overlapping, meaning that some nodes may be found in multiple results. Some results may be subsets of other results.

  • EXAMPLE: assume graph "Conv#1->ReLU#1->Conv#2->ReLU#2": Conv->ReLU?->Conv?->ReLU? will return both "Conv#1->ReLU#1->Conv#2->ReLU#2" and "Conv#2->ReLU#2". To avoid this behavior, set the disjoint argument to true. In this case, only "Conv#1->ReLU#1->Conv#2->ReLU#2" will be kept in the example above.

• Whitespaces are allowed anywhere in the query