1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
/** @file exam_match.cpp
*
* Check for bug in GiNaC::ex::match() described here:
* https://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html */
/*
* GiNaC Copyright (C) 1999-2025 Johannes Gutenberg University Mainz, Germany
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
#include "ginac.h"
#include "error_report.h"
#include <iostream>
using namespace GiNaC;
/*
* basic::match(lst&) used to have an obscure side effect: repl_lst
* could be modified even if the match failed! Although this "feature"
* was documented it happened to be very confusing *even for GiNaC
* developers*, see
* https://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html
*
* It was fixed in 192ed7390b7b2b705ad100e3db0a92eedd2b20ad. Let's make
* sure it will be never re-added:
*/
static void failed_match_have_side_effects()
{
symbol x("x");
ex e = pow(x, 5);
ex pattern = pow(wild(0), -1);
// obviously e does NOT match the pattern
exmap repls;
bool match_p = e.match(pattern, repls);
cbug_on(match_p, "match(" << e << ", " << pattern << ") says \"Yes\"");
cbug_on(repls.size() != 0,
"failed match have side effects: repls = " << repls);
}
/*
* As a consequence of the bug described above pattern matching can wrongly
* fail. In particular, x^5*y^(-1) fails to match ($0)^(-1)*x^($2).
*
* The first thing that is attempted to match is x^5 with $0^(-1). This match
* will fail. However repl_lst will contain $0 == x as a side effect. This
* repl_lst will prevent the match of y^(-1) to ($0)^(-1) to succeed.
*
* This issue was worked around by 73f0ce4cf8d91f073f35a45443f5fbe886921c5c.
* Now we have a real fix (192ed7390b7b2b705ad100e3db0a92eedd2b20ad), but
* let's add a check.
*/
static void match_false_negative()
{
symbol x("x"), y("y");
ex e = pow(x, 5)*pow(y, -1);
ex pattern = pow(wild(0), -1)*pow(x, wild(2));
exmap repls;
bool match_p = e.match(pattern, repls);
cbug_on(!match_p, "false negative: " << e << " did not match "
<< 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 << "examining 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;
}
|
