check/match_bug.cpp

   1 /** @file match_bug.cpp
   2  *
   3  *  Check for bug in GiNaC::ex::match() described here:
   4  *  http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html */
   5
   6 /*
   7  *  GiNaC Copyright (C) 1999-2015 Johannes Gutenberg University Mainz, Germany
   8  *
   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.
  13  *
  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.
  18  *
  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
  22  */
  23
  24 #include "ginac.h"
  25 #include "error_report.h"
  26
  27 #include <iostream>
  28 using namespace GiNaC;
  29
  30 /*
  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
  34  * developers*, see
  35  * http://www.ginac.de/pipermail/ginac-devel/2006-April/000942.html
  36  *
  37  * It was fixed in 192ed7390b7b2b705ad100e3db0a92eedd2b20ad. Let's make
  38  * sure it will be never re-added:
  39  */
  40 static void failed_match_have_side_effects()
  41 {
  42         symbol x("x");
  43         ex e = pow(x, 5);
  44         ex pattern = pow(wild(0), -1);
  45         // obviously e does NOT match the pattern
  46         exmap repls;
  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);
  51 }
  52
  53 /*
  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).
  56  *
  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.
  60  *
  61  * This issue was worked around by 73f0ce4cf8d91f073f35a45443f5fbe886921c5c.
  62  * Now we have a real fix (192ed7390b7b2b705ad100e3db0a92eedd2b20ad), but
  63  * let's add a check.
  64  */
  65 static void match_false_negative()
  66 {
  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));
  70         exmap repls;
  71         bool match_p = e.match(pattern, repls);
  72         cbug_on(!match_p, "false negative: " << e << " did not match "
  73                         << pattern);
  74 }
  75
  76 /*
  77  * expairseq::match() should not have any side effects if the match failed.
  78  */
  79 static void expairseq_failed_match_no_side_effect(int count)
  80 {
  81         for (int i = 0; i < count; ++i) {
  82                 exmap repls;
  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");
  89         }
  90 }
  91
  92 /*
  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.
  95  *
  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.
 101  *
 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.
 105  */
 106 static void expairseq_match_false_negative(int count)
 107 {
 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);
 114         }
 115 }
 116
 117 int main(int argc, char** argv)
 118 {
 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. ";
 126         return 0;
 127 }