From 9ada7a7f5c47e512b7bf6057d4c013612be9a33b Mon Sep 17 00:00:00 2001 From: Matthias Dellweg Date: Tue, 10 Dec 2013 10:55:28 +0200 Subject: [PATCH] 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 [Alexei Sheplyakov: figure out the cause of the problem, make a test case] --- check/match_bug.cpp | 44 ++++++++++++++++++++++++++++++++++++++++++++ ginac/expairseq.cpp | 26 +++++++++++++++++++++----- 2 files changed, 65 insertions(+), 5 deletions(-) diff --git a/check/match_bug.cpp b/check/match_bug.cpp index c9af2f87..d1e40a6f 100644 --- 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 7c6e5223..7dc55824 100644 --- 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; ipush_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); -- 2.44.0