check/match_bug.cpp

   1 /**
   2  * @file match_bug.cpp
   3  *
   4  * Check for bug in GiNaC::ex::match() described here:
   5  * http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html
   6  */
   7 #include "ginac.h"
   8 #include "error_report.hpp"
   9 #include <iostream>
  10 using namespace GiNaC;
  11
  12 /*
  13  * basic::match(lst&) used to have an obscure side effect: repl_lst
  14  * could be modified even if the match failed! Although this "feature"
  15  * was documented it happend to be very confusing *even for GiNaC
  16  * developers*, see
  17  * http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html
  18  *
  19  * It was fixed in 192ed7390b7b2b705ad100e3db0a92eedd2b20ad. Let's make
  20  * sure it will be never re-added:
  21  */
  22 static void failed_match_have_side_effects()
  23 {
  24         symbol x("x");
  25         ex e = pow(x, 5);
  26         ex pattern = pow(wild(0), -1);
  27         // obviously e does NOT match the pattern
  28         exmap repls;
  29         bool match_p = e.match(pattern, repls);
  30         bug_on(match_p, "match(" << e << ", " << pattern << ") says \"Yes\"");
  31         bug_on(repls.size() != 0,
  32                 "failed match have side effects: repls = " << repls);
  33 }
  34
  35 /*
  36  * As a consequence of the bug described above pattern matching can wrongly
  37  * fail. In particular, x^5*y^(-1) fails to match ($0)^(-1)*x^($2).
  38  *
  39  * The first thing that is attempted to match is x^5 with $0^(-1). This match
  40  * will fail. However repl_lst will contain $0 == x as a side effect. This
  41  * repl_lst will prevent the match of y^(-1) to ($0)^(-1) to succeed.
  42  *
  43  * This issue was worked around by 73f0ce4cf8d91f073f35a45443f5fbe886921c5c.
  44  * Now we have a real fix (192ed7390b7b2b705ad100e3db0a92eedd2b20ad), but
  45  * let's add a check.
  46  */
  47 static void match_false_negative()
  48 {
  49         symbol x("x"), y("y");
  50         ex e = pow(x, 5)*pow(y, -1);
  51         ex pattern = pow(wild(0), -1)*pow(x, wild(2));
  52         exmap repls;
  53         bool match_p = e.match(pattern, repls);
  54         bug_on(!match_p, "false negative: " << e << " did not match "
  55                         << pattern);
  56 }
  57
  58 int main(int argc, char** argv)
  59 {
  60         std::cout << "checking for historical bugs in match()... " << std::flush;
  61         failed_match_have_side_effects();
  62         match_false_negative();
  63         std::cout << "not found. ";
  64         return 0;
  65 }
  66