VIATRA2/Components

TODO model space, interpreter, etc.

Pattern matcher

Role

The pattern matcher is the component responsible for finding the occurrences of the defined VTCL patterns. The pattern matcher is invoked whenever the interpreter executes a forall or choose construct having a with find somepattern(...) or with apply somegtrule(...) clause. The first invokation of a certain pattern might last longer due to pattern analysis, search plan generation, and other preparatory tasks.

Alternatives

VIATRA2 R3 ships with two alternative pattern matcher engine.

The local-search based default pattern matcher searches the model space each time a pattern query is requested. Pattern matching may consume a significant amount of time on each query, but no other maintenance costs arise.

The incremental pattern matcher has a radically different approach: the occurrence set of patterns is constructed on their first usage, preserved in-memory and maintained from that time on. After each model manipulation step, the necessary local changes to these stored occurrence sets are calculated and the updates are performed. The great advantage of the incremental pattern matcher is that pattern queries can be fulfilled virtually instantly, as the result set is already available. The disadvantages are that model manipulation costs are somewhat increased due to the maintenance of occurrence sets, and the stored results sets may consume a significant amount of memory. It is recommended to use the incremental pattern matcher engine with a high amount of memory allotted to the Java VM.

Our measurements and experiments show that choosing the incremental pattern matcher may improve performance by several orders of magnitude in some cases. If large models are used with frequent pattern matching queries and relatively minor model changes, consider using the incremental pattern matcher.

Important note: the incremental pattern matcher currently does not inline (flatten) patterns, and therefore does not support locally unresolvable pattern variables. An example of an unsupported pattern would look like this:

pattern incompletePattern(A,B) = 
{ 
  Type(A); 
  // no declaration of B
  check(value(A) == value(B)); 
}

Selecting the pattern matcher engine

@incremental
pattern myIncrementalPattern(X,Y) = 
{
   /* ... */
}
 
@localsearch
pattern myLocalSearchPattern(A,B) = 
{
   /* ... */
}

With annotations, you can select on a per-pattern basis which pattern will be matched incrementally and which with local search. It is your responsibility that if patterns call each other, you have to make sure that each pattern along the call chain is used with the same annotation. To avoid annotating each pattern, the same annotations can be applied on a per-machine basis to provide machine-level defaults. Per-pattern annotations can be used to locally override the machine default.

You can also use these annotation on a per-gtRule basis to select which pattern matcher to use for matching the LHS side of a gtRule. Machine level annotation also sets the default matcher for the GT matcher.

@incremental
pattern myIncrementallyMatchedGTRule(X,Y) = 
{
   /* ... */
}
 
@localsearch
pattern myLocallyMatchedGtRule(A,B) = 
{
   /* ... */
}

Initial experience shows that combining the two pattern matcher can easily result in a low memory consumption but fast matching strategy.