From 3918e4767063fb45e5728bd9b3a09dd8ac30d055 Mon Sep 17 00:00:00 2001 From: Alexei Sheplyakov Date: Thu, 11 Sep 2008 16:59:30 +0400 Subject: [PATCH 1/1] expairseq::match(): remove the code which works around basic::match bug. basic::match() used to have side effects in a case of a failed match. As a result of that bug exparsed::match did not work correctly in some cases, see [1] for more details. These false negatives were worked around by [2]. Now that match() has no unwanted side effects [3] we don't need any work arounds any more. Just in a case add a regression test (from [1]). [1] http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html [2] Commit 73f0ce4cf8d91f073f35a45443f5fbe886921c5c ("Fixed bugs in ::match"). [3] Commit 192ed7390b7b2b705ad100e3db0a92eedd2b20ad ("match: don't modify subexpression list if expression doesn't match the pattern."). --- check/Makefile.am | 4 +++ check/error_report.hpp | 17 +++++++++++ check/match_bug.cpp | 66 ++++++++++++++++++++++++++++++++++++++++++ ginac/expairseq.cpp | 10 ------- 4 files changed, 87 insertions(+), 10 deletions(-) create mode 100644 check/error_report.hpp create mode 100644 check/match_bug.cpp diff --git a/check/Makefile.am b/check/Makefile.am index b656c631..9b92a0b9 100644 --- a/check/Makefile.am +++ b/check/Makefile.am @@ -7,6 +7,7 @@ CHECKS = check_numeric \ EXAMS = exam_paranoia \ exam_heur_gcd \ + match_bug \ exam_numeric_archive \ exam_numeric \ exam_powerlaws \ @@ -74,6 +75,9 @@ exam_paranoia_LDADD = ../ginac/libginac.la exam_heur_gcd_SOURCES = heur_gcd_bug.cpp exam_heur_gcd_LDADD = ../ginac/libginac.la +match_bug_SOURCES = match_bug.cpp error_report.hpp +match_bug_LDADD = ../ginac/libginac.la + exam_numeric_archive_SOURCES = numeric_archive.cpp exam_numeric_archive_LDADD = ../ginac/libginac.la diff --git a/check/error_report.hpp b/check/error_report.hpp new file mode 100644 index 00000000..6b2dfe61 --- /dev/null +++ b/check/error_report.hpp @@ -0,0 +1,17 @@ +#ifndef GINAC_CHECK_ERROR_REPORT_HPP +#define GINAC_CHECK_ERROR_REPORT_HPP +#include +#include + +#define bug_on(cond, what) \ +do { \ +if (cond) { \ + std::ostringstream err_stream; \ + err_stream << __FILE__ << ':' << __LINE__ \ + << what; \ + throw std::logic_error(err_stream.str()); \ +} \ +} while (0) + +#endif // GINAC_CHECK_ERROR_REPORT_HPP + diff --git a/check/match_bug.cpp b/check/match_bug.cpp new file mode 100644 index 00000000..d80faca3 --- /dev/null +++ b/check/match_bug.cpp @@ -0,0 +1,66 @@ +/** + * @file match_bug.cpp + * + * Check for bug in GiNaC::ex::match() described here: + * http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html + */ +#include "ginac.h" +#include "error_report.hpp" +#include +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 happend to be very confusing *even for GiNaC + * developers*, see + * http://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 + lst repl_lst; + bool match_p = e.match(pattern, repl_lst); + bug_on(match_p, "match(" << e << ", " << pattern << ") says \"Yes\""); + bug_on(repl_lst.nops() != 0, + "failed match have side effects: repl_lst = " << repl_lst); +} + +/* + * 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)); + lst repl_lst; + bool match_p = e.match(pattern, repl_lst); + bug_on(!match_p, "false negative: " << e << " did not match " + << pattern); +} + +int main(int argc, char** argv) +{ + std::cout << "checking for historical bugs in match()... " << std::flush; + failed_match_have_side_effects(); + match_false_negative(); + std::cout << "not found. "; + return 0; +} + diff --git a/ginac/expairseq.cpp b/ginac/expairseq.cpp index 3ed9e289..229710b2 100644 --- a/ginac/expairseq.cpp +++ b/ginac/expairseq.cpp @@ -427,20 +427,10 @@ bool expairseq::match(const ex & pattern, lst & repl_lst) const continue; exvector::iterator it = ops.begin(), itend = ops.end(); while (it != itend) { - lst::const_iterator last_el = repl_lst.end(); - --last_el; if (it->match(p, repl_lst)) { ops.erase(it); goto found; } - while(true) { - lst::const_iterator next_el = last_el; - ++next_el; - if(next_el == repl_lst.end()) - break; - else - repl_lst.remove_last(); - } ++it; } return false; // no match found -- 2.44.0