expairseq::match(): no side effects if match failed. Fixes spurious match failures.

> match(sin(y)*exp(b)+sin(x)*exp(a), sin($0)*exp(a)+exp(b)*sin($1))
FAIL

The reason is that expairseq::match() might assign a wildcard even if
the match fails. The first attempted submatch is sin(y)*exp(b) with
sin($0)*exp(a). It fails (as it should) but $0 == y gets assigned as
a side effect (which is wrong). Next submatch is sin(x)*exp(a) with
sin($0)*exp(a) (the same pattern as in the first submatch). This one
fails because of spurious $0 == y assignment.

Due to the unpredicatable term ordering the sequence of submatches might
be different and the match might succeed (as it should). This makes
debugging a bit more funny.

Signed-off-by: Matthias Dellweg <dellweg@tp1.uni-duesseldorf.de>
[Alexei Sheplyakov: figure out the cause of the problem, make a test case]

diff --git a/check/match_bug.cpp b/check/match_bug.cpp
index c9af2f873baa723d70323ac8ffe68ae051c0fbb3..d1e40a6f754d53457c356162a49aa7286947849c 100644 (file)
--- a/check/match_bug.cpp
+++ b/check/match_bug.cpp
@@ -73,11 +73,55 @@ static void match_false_negative()
                        << pattern);
 }
 
+/*
+ * expairseq::match() should not have any side effects if the match failed.
+ */
+static void expairseq_failed_match_no_side_effect(int count)
+{
+       for (int i = 0; i < count; ++i) {
+               exmap repls;
+               symbol t("t"), A("A");
+               ex e = pow(t, 2)*exp(t*A);
+               ex pattern = pow(t, wild(0))*exp(wild(1))*A;
+               bool matched = e.match(pattern, repls);
+               cbug_on(matched, "unexpected match: " << e << " vs " << pattern);
+               cbug_on(repls.size(), "failed match has side effects");
+       }
+}
+
+/*
+ * exp(a)*sin(x) + exp(b)*sin(y) used to fail to match
+ * exp(a)*sin($0) + exp(b)*sin($1). The failure was not deterministic.
+ *
+ * The first attempted submatch is sin(y)*exp(b) with sin($0)*exp(a).
+ * It fails but $0 == y gets assigned due to a spurious side effect.
+ * Next submatch is sin(x)*exp(a) with sin($0)*exp(a) (the same pattern
+ * as in the first submatch). This one fails because of (incorrect)
+ * $0 == y assignment.
+ *
+ * Note: due to the unstable term ordering the sequence of submatches
+ * might be different and the match might succeed (as it should), hence
+ * we repeat the test several times.
+ */
+static void expairseq_match_false_negative(int count)
+{
+       for (int i = 0; i < count; ++i) {
+               symbol a("a"), b("b"), x("x"), y("y");
+               ex e = exp(a)*sin(x) + exp(b)*sin(y);
+               ex pattern = exp(a)*sin(wild(0)) + exp(b)*sin(wild(1));
+               cbug_on(!e.match(pattern), "match failed: " << e << "did not"
+                       "match " << pattern);
+       }
+}
+
 int main(int argc, char** argv)
 {
+       const int repetitions = 100;
        std::cout << "checking for historical bugs in match()... " << std::flush;
        failed_match_have_side_effects();
        match_false_negative();
+       expairseq_failed_match_no_side_effect(repetitions);
+       expairseq_match_false_negative(repetitions);
        std::cout << "not found. ";
        return 0;
 }

diff --git a/ginac/expairseq.cpp b/ginac/expairseq.cpp
index 7c6e5223653889730407aa0fd5a246417cc06f6d..7dc55824e52f4252377d27386d70877f7ca927d8 100644 (file)
--- a/ginac/expairseq.cpp
+++ b/ginac/expairseq.cpp
@@ -394,6 +394,12 @@ bool expairseq::match(const ex & pattern, exmap & repl_lst) const
                        }
                }
 
+               // Even if the expression does not match the pattern, some of
+               // its subexpressions could match it. For example, x^5*y^(-1)
+               // does not match the pattern $0^5, but its subexpression x^5
+               // does. So, save repl_lst in order to not add bogus entries.
+               exmap tmp_repl = repl_lst;
+
                // Unfortunately, this is an O(N^2) operation because we can't
                // sort the pattern in a useful way...
 
@@ -411,7 +417,7 @@ bool expairseq::match(const ex & pattern, exmap & repl_lst) const
                                continue;
                        exvector::iterator it = ops.begin(), itend = ops.end();
                        while (it != itend) {
-                               if (it->match(p, repl_lst)) {
+                               if (it->match(p, tmp_repl)) {
                                        ops.erase(it);
                                        goto found;
                                }
@@ -432,10 +438,16 @@ found:            ;
                        for (size_t i=0; i<num; i++)
                                vp->push_back(split_ex_to_pair(ops[i]));
                        ex rest = thisexpairseq(vp, default_overall_coeff());
-                       for (exmap::const_iterator it = repl_lst.begin(); it != repl_lst.end(); ++it) {
-                               if (it->first.is_equal(global_wildcard))
-                                       return rest.is_equal(it->second);
+                       for (exmap::const_iterator it = tmp_repl.begin(); it != tmp_repl.end(); ++it) {
+                               if (it->first.is_equal(global_wildcard)) {
+                                       if (rest.is_equal(it->second)) {
+                                               repl_lst = tmp_repl;
+                                               return true;
+                                       }
+                                       return false;
+                               }
                        }
+                       repl_lst = tmp_repl;
                        repl_lst[global_wildcard] = rest;
                        return true;
 
@@ -443,7 +455,11 @@ found:             ;
 
                        // No global wildcard, then the match fails if there are any
                        // unmatched terms left
-                       return ops.empty();
+                       if (ops.empty()) {
+                               repl_lst = tmp_repl;
+                               return true;
+                       }
+                       return false;
                }
        }
        return inherited::match(pattern, repl_lst);