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.").

diff --git a/check/Makefile.am b/check/Makefile.am
index b656c631bc5628f1b44865964f87994f22c70a18..9b92a0b9b4919e6ea6f01232090b9b200535abaf 100644 (file)
--- 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 (file)
index 0000000..6b2dfe6
--- /dev/null
+++ b/check/error_report.hpp
@@ -0,0 +1,17 @@
+#ifndef GINAC_CHECK_ERROR_REPORT_HPP
+#define GINAC_CHECK_ERROR_REPORT_HPP
+#include <sstream>
+#include <stdexcept>
+
+#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 (file)
index 0000000..d80faca
--- /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 <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 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 3ed9e2892a23040c8bbb8e2ce4bf3ebfed36705f..229710b2fcc922fb04fa09ae443ed84d48e2609f 100644 (file)
--- 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