5.4.1 Matching expressions

The most basic application of patterns is to check whether an expression matches a given pattern. This is done by the function

bool ex::match(const ex & pattern);
bool ex::match(const ex & pattern, lst & repls);

This function returns true when the expression matches the pattern and false if it doesn't. If used in the second form, the actual subexpressions matched by the wildcards get returned in the repls object as a list of relations of the form ‘wildcard == expression’. If match() returns false, the state of repls is undefined. For reproducible results, the list should be empty when passed to match(), but it is also possible to find similarities in multiple expressions by passing in the result of a previous match.

The matching algorithm works as follows:

• A single wildcard matches any expression. If one wildcard appears multiple times in a pattern, it must match the same expression in all places (e.g. ‘$0’ matches anything, and ‘$0*($0+1)’ matches ‘x*(x+1)’ but not ‘x*(y+1)’).
• If the expression is not of the same class as the pattern, the match fails (i.e. a sum only matches a sum, a function only matches a function, etc.).
• If the pattern is a function, it only matches the same function (i.e. ‘sin($0)’ matches ‘sin(x)’ but doesn't match ‘exp(x)’).
• Except for sums and products, the match fails if the number of subexpressions (nops()) is not equal to the number of subexpressions of the pattern.
• If there are no subexpressions, the expressions and the pattern must be equal (in the sense of is_equal()).
• Except for sums and products, each subexpression (op()) must match the corresponding subexpression of the pattern.

Sums (add) and products (mul) are treated in a special way to account for their commutativity and associativity:

• If the pattern contains a term or factor that is a single wildcard, this one is used as the global wildcard. If there is more than one such wildcard, one of them is chosen as the global wildcard in a random way.
• Every term/factor of the pattern, except the global wildcard, is matched against every term of the expression in sequence. If no match is found, the whole match fails. Terms that did match are not considered in further matches.
• If there are no unmatched terms left, the match succeeds. Otherwise the match fails unless there is a global wildcard in the pattern, in which case this wildcard matches the remaining terms.

In general, having more than one single wildcard as a term of a sum or a factor of a product (such as ‘a+$0+$1’) will lead to unpredictable or ambiguous results.

Here are some examples in ginsh to demonstrate how it works (the match() function in ginsh returns ‘FAIL’ if the match fails, and the list of wildcard replacements otherwise):

> match((x+y)^a,(x+y)^a);
{}
> match((x+y)^a,(x+y)^b);
FAIL
> match((x+y)^a,$1^$2);
{$1==x+y,$2==a}
> match((x+y)^a,$1^$1);
FAIL
> match((x+y)^(x+y),$1^$1);
{$1==x+y}
> match((x+y)^(x+y),$1^$2);
{$1==x+y,$2==x+y}
> match((a+b)*(a+c),($1+b)*($1+c));
{$1==a}
> match((a+b)*(a+c),(a+$1)*(a+$2));
{$1==b,$2==c}
  (Unpredictable. The result might also be [$1==c,$2==b].)
> match((a+b)*(a+c),($1+$2)*($1+$3));
  (The result is undefined. Due to the sequential nature of the algorithm
   and the re-ordering of terms in GiNaC, the match for the first factor
   may be {$1==a,$2==b} in which case the match for the second factor
   succeeds, or it may be {$1==b,$2==a} which causes the second match to
   fail.)
> match(a*(x+y)+a*z+b,a*$1+$2);
  (This is also ambiguous and may return either {$1==z,$2==a*(x+y)+b} or
   {$1=x+y,$2=a*z+b}.)
> match(a+b+c+d+e+f,c);
FAIL
> match(a+b+c+d+e+f,c+$0);
{$0==a+e+b+f+d}
> match(a+b+c+d+e+f,c+e+$0);
{$0==a+b+f+d}
> match(a+b,a+b+$0);
{$0==0}
> match(a*b^2,a^$1*b^$2);
FAIL
  (The matching is syntactic, not algebraic, and "a" doesn't match "a^$1"
   even though a==a^1.)
> match(x*atan2(x,x^2),$0*atan2($0,$0^2));
{$0==x}
> match(atan2(y,x^2),atan2(y,$0));
{$0==x^2}