1 /** @file match_bug.cpp
3 * Check for bug in GiNaC::ex::match() described here:
4 * http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html */
7 * GiNaC Copyright (C) 1999-2016 Johannes Gutenberg University Mainz, Germany
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 #include "error_report.h"
28 using namespace GiNaC;
31 * basic::match(lst&) used to have an obscure side effect: repl_lst
32 * could be modified even if the match failed! Although this "feature"
33 * was documented it happened to be very confusing *even for GiNaC
35 * http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html
37 * It was fixed in 192ed7390b7b2b705ad100e3db0a92eedd2b20ad. Let's make
38 * sure it will be never re-added:
40 static void failed_match_have_side_effects()
44 ex pattern = pow(wild(0), -1);
45 // obviously e does NOT match the pattern
47 bool match_p = e.match(pattern, repls);
48 cbug_on(match_p, "match(" << e << ", " << pattern << ") says \"Yes\"");
49 cbug_on(repls.size() != 0,
50 "failed match have side effects: repls = " << repls);
54 * As a consequence of the bug described above pattern matching can wrongly
55 * fail. In particular, x^5*y^(-1) fails to match ($0)^(-1)*x^($2).
57 * The first thing that is attempted to match is x^5 with $0^(-1). This match
58 * will fail. However repl_lst will contain $0 == x as a side effect. This
59 * repl_lst will prevent the match of y^(-1) to ($0)^(-1) to succeed.
61 * This issue was worked around by 73f0ce4cf8d91f073f35a45443f5fbe886921c5c.
62 * Now we have a real fix (192ed7390b7b2b705ad100e3db0a92eedd2b20ad), but
65 static void match_false_negative()
67 symbol x("x"), y("y");
68 ex e = pow(x, 5)*pow(y, -1);
69 ex pattern = pow(wild(0), -1)*pow(x, wild(2));
71 bool match_p = e.match(pattern, repls);
72 cbug_on(!match_p, "false negative: " << e << " did not match "
77 * expairseq::match() should not have any side effects if the match failed.
79 static void expairseq_failed_match_no_side_effect(int count)
81 for (int i = 0; i < count; ++i) {
83 symbol t("t"), A("A");
84 ex e = pow(t, 2)*exp(t*A);
85 ex pattern = pow(t, wild(0))*exp(wild(1))*A;
86 bool matched = e.match(pattern, repls);
87 cbug_on(matched, "unexpected match: " << e << " vs " << pattern);
88 cbug_on(repls.size(), "failed match has side effects");
93 * exp(a)*sin(x) + exp(b)*sin(y) used to fail to match
94 * exp(a)*sin($0) + exp(b)*sin($1). The failure was not deterministic.
96 * The first attempted submatch is sin(y)*exp(b) with sin($0)*exp(a).
97 * It fails but $0 == y gets assigned due to a spurious side effect.
98 * Next submatch is sin(x)*exp(a) with sin($0)*exp(a) (the same pattern
99 * as in the first submatch). This one fails because of (incorrect)
100 * $0 == y assignment.
102 * Note: due to the unstable term ordering the sequence of submatches
103 * might be different and the match might succeed (as it should), hence
104 * we repeat the test several times.
106 static void expairseq_match_false_negative(int count)
108 for (int i = 0; i < count; ++i) {
109 symbol a("a"), b("b"), x("x"), y("y");
110 ex e = exp(a)*sin(x) + exp(b)*sin(y);
111 ex pattern = exp(a)*sin(wild(0)) + exp(b)*sin(wild(1));
112 cbug_on(!e.match(pattern), "match failed: " << e << "did not"
113 "match " << pattern);
117 int main(int argc, char** argv)
119 const int repetitions = 100;
120 std::cout << "checking for historical bugs in match()... " << std::flush;
121 failed_match_have_side_effects();
122 match_false_negative();
123 expairseq_failed_match_no_side_effect(repetitions);
124 expairseq_match_false_negative(repetitions);
125 std::cout << "not found. ";