From b9cd4b49ffbfbf3e1c36a2b594ec3148a5baca64 Mon Sep 17 00:00:00 2001 From: Christian Bauer Date: Thu, 24 May 2001 00:43:11 +0000 Subject: [PATCH] - first implementation of pattern matching --- NEWS | 5 ++ doc/tutorial/ginac.texi | 16 ++++-- ginac/Makefile.am | 4 +- ginac/basic.cpp | 69 +++++++++++++++++++--- ginac/basic.h | 5 +- ginac/color.cpp | 1 - ginac/container.pl | 47 ++++----------- ginac/ex.h | 8 ++- ginac/expairseq.cpp | 93 +++++++++++++++++++++++++++--- ginac/expairseq.h | 5 +- ginac/function.pl | 9 +++ ginac/ginac.h | 1 + ginac/idx.cpp | 4 +- ginac/idx.h | 2 +- ginac/matrix.cpp | 22 +------ ginac/matrix.h | 3 +- ginac/power.cpp | 17 +++--- ginac/power.h | 2 +- ginac/pseries.cpp | 8 +-- ginac/pseries.h | 2 +- ginac/tinfos.h | 2 + ginac/wildcard.cpp | 124 ++++++++++++++++++++++++++++++++++++++++ ginac/wildcard.h | 72 +++++++++++++++++++++++ ginsh/ginsh.1.in | 3 + ginsh/ginsh_lexer.ll | 3 + ginsh/ginsh_parser.yy | 10 ++++ 26 files changed, 431 insertions(+), 106 deletions(-) create mode 100644 ginac/wildcard.cpp create mode 100644 ginac/wildcard.h diff --git a/NEWS b/NEWS index d349c8fa..d08e730e 100644 --- a/NEWS +++ b/NEWS @@ -5,6 +5,11 @@ This file records noteworthy changes. simplified to "2*a.i*a.i". * Added canonicalize_clifford() function that can be helpful when comparing expressions containing Dirac matrices. +* Added a new function match() for performing pattern matching. subs() and + has() also accept patterns as arguments. A pattern can be any expression, + optionally containing wildcard objects. These are constructed with the + call "wild()" and are denoted as "$0", "$1" etc. in the output + and in ginsh. * Fixed possible crash when calling subs() on expressions with non-commutative products. diff --git a/doc/tutorial/ginac.texi b/doc/tutorial/ginac.texi index 4dc99450..46e37772 100644 --- a/doc/tutorial/ginac.texi +++ b/doc/tutorial/ginac.texi @@ -4216,8 +4216,14 @@ work in the GiNaC framework. For a real algebraic class, there are probably some more functions that you will want to re-implement, such as @code{evalf()}, @code{series()} or @code{op()}. Have a look at @file{basic.h} or the header file of the class you want to make a subclass of to see -what's there. You can, of course, also add your own new member functions. -In this case you will probably want to define a little helper function like +what's there. One member function that you will most likely want to +implement for terminal classes like the described string class is +@code{calcchash()} that returns an @code{unsigned} hash value for the object +which will allow GiNaC to compare and canonicalize expressions much more +efficiently. + +You can, of course, also add your own new member functions. In this case you +will probably want to define a little helper function like @example inline const mystring &ex_to_mystring(const ex &e) @@ -4226,9 +4232,9 @@ inline const mystring &ex_to_mystring(const ex &e) @} @end example -that let's you get at the object inside an expression (after you have verified -that the type is correct) so you can call member functions that are specific -to the class. +that let's you get at the object inside an expression (after you have +verified that the type is correct) so you can call member functions that are +specific to the class. That's it. May the source be with you! diff --git a/ginac/Makefile.am b/ginac/Makefile.am index faaa66e3..595e1f5c 100644 --- a/ginac/Makefile.am +++ b/ginac/Makefile.am @@ -8,7 +8,7 @@ libginac_la_SOURCES = add.cpp archive.cpp basic.cpp constant.cpp ex.cpp \ symbol.cpp pseries.cpp utils.cpp ncmul.cpp structure.cpp exprseq_suppl.cpp \ lst.cpp lst_suppl.cpp input_parser.yy input_lexer.ll input_lexer.h \ remember.h remember.cpp debugmsg.h utils.h idx.cpp indexed.cpp tensor.cpp \ - color.cpp clifford.cpp + color.cpp clifford.cpp wildcard.cpp libginac_la_LDFLAGS = -version-info $(LT_CURRENT):$(LT_REVISION):$(LT_AGE) \ -release $(LT_RELEASE) ginacincludedir = $(includedir)/ginac @@ -16,7 +16,7 @@ ginacinclude_HEADERS = ginac.h add.h archive.h basic.h constant.h ex.h \ expair.h expairseq.h exprseq.h fail.h flags.h function.h inifcns.h \ lst.h matrix.h mul.h ncmul.h normal.h numeric.h operators.h power.h \ registrar.h relational.h pseries.h structure.h symbol.h tinfos.h assertion.h \ - version.h idx.h indexed.h tensor.h color.h clifford.h print.h + version.h idx.h indexed.h tensor.h color.h clifford.h wildcard.h print.h LFLAGS = -Pginac_yy -olex.yy.c YFLAGS = -p ginac_yy -d EXTRA_DIST = container.pl function.pl structure.pl input_parser.h version.h.in diff --git a/ginac/basic.cpp b/ginac/basic.cpp index bf5bd6cb..c899d19f 100644 --- a/ginac/basic.cpp +++ b/ginac/basic.cpp @@ -33,6 +33,7 @@ #include "symbol.h" #include "lst.h" #include "ncmul.h" +#include "relational.h" #include "print.h" #include "archive.h" #include "utils.h" @@ -219,7 +220,8 @@ ex basic::operator[](int i) const bool basic::has(const ex & other) const { GINAC_ASSERT(other.bp!=0); - if (is_equal(*other.bp)) return true; + lst repl_lst; + if (match(*other.bp, repl_lst)) return true; if (nops()>0) { for (unsigned i=0; i #include "color.h" -#include "ex.h" #include "idx.h" #include "ncmul.h" #include "numeric.h" diff --git a/ginac/container.pl b/ginac/container.pl index 8a025033..f13c9657 100755 --- a/ginac/container.pl +++ b/ginac/container.pl @@ -211,12 +211,11 @@ public: unsigned nops() const; ex & let_op(int i); ex expand(unsigned options=0) const; - bool has(const ex & other) const; ex eval(int level=0) const; ex evalf(int level=0) const; ex normal(lst &sym_lst, lst &repl_lst, int level=0) const; ex derivative(const symbol & s) const; - ex subs(const lst & ls, const lst & lr) const; + ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const; protected: bool is_equal_same_type(const basic & other) const; unsigned return_type(void) const; @@ -238,7 +237,7 @@ protected: ${STLT} evalfchildren(int level) const; ${STLT} normalchildren(int level) const; ${STLT} diffchildren(const symbol & s) const; - ${STLT} * subschildren(const lst & ls, const lst & lr) const; + ${STLT} * subschildren(const lst & ls, const lst & lr, bool no_pattern = false) const; protected: ${STLT} seq; @@ -442,18 +441,6 @@ ex ${CONTAINER}::expand(unsigned options) const return this${CONTAINER}(s); } -// a ${CONTAINER} 'has' an expression if it is this expression itself or a child 'has' it - -bool ${CONTAINER}::has(const ex & other) const -{ - GINAC_ASSERT(other.bp!=0); - if (is_equal(*other.bp)) return true; - for (${STLT}::const_iterator it=seq.begin(); it!=seq.end(); ++it) { - if ((*it).has(other)) return true; - } - return false; -} - ex ${CONTAINER}::eval(int level) const { if (level==1) { @@ -481,13 +468,13 @@ ex ${CONTAINER}::derivative(const symbol & s) const return this${CONTAINER}(diffchildren(s)); } -ex ${CONTAINER}::subs(const lst & ls, const lst & lr) const +ex ${CONTAINER}::subs(const lst & ls, const lst & lr, bool no_pattern) const { - ${STLT} * vp=subschildren(ls,lr); - if (vp==0) - return inherited::subs(ls, lr); - - return this${CONTAINER}(vp); + ${STLT} *vp = subschildren(ls, lr, no_pattern); + if (vp) + return this${CONTAINER}(vp).bp->basic::subs(ls, lr, no_pattern); + else + return basic::subs(ls, lr, no_pattern); } // protected @@ -676,19 +663,7 @@ ${STLT} ${CONTAINER}::diffchildren(const symbol & y) const return s; } -/* obsolete subschildren -${STLT} ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const -{ - ${STLT} s; - RESERVE(s,seq.size()); - for (${STLT}::const_iterator it=seq.begin(); it!=seq.end(); ++it) { - s.push_back((*it).subs(ls,lr)); - } - return s; -} -*/ - -${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const +${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr, bool no_pattern) const { // returns a NULL pointer if nothing had to be substituted // returns a pointer to a newly created epvector otherwise @@ -697,7 +672,7 @@ ${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const ${STLT}::const_iterator last=seq.end(); ${STLT}::const_iterator cit=seq.begin(); while (cit!=last) { - const ex & subsed_ex=(*cit).subs(ls,lr); + const ex & subsed_ex=(*cit).subs(ls,lr,no_pattern); if (!are_ex_trivially_equal(*cit,subsed_ex)) { // something changed, copy seq, subs and return it @@ -715,7 +690,7 @@ ${STLT} * ${CONTAINER}::subschildren(const lst & ls, const lst & lr) const ++cit2; // copy rest while (cit2!=last) { - s->push_back((*cit2).subs(ls,lr)); + s->push_back((*cit2).subs(ls,lr,no_pattern)); ++cit2; } return s; diff --git a/ginac/ex.h b/ginac/ex.h index 7b36eff8..1449b635 100644 --- a/ginac/ex.h +++ b/ginac/ex.h @@ -105,8 +105,9 @@ public: ex evalf(int level = 0) const { return bp->evalf(level); } ex diff(const symbol & s, unsigned nth = 1) const; ex series(const ex & r, int order, unsigned options = 0) const; - ex subs(const lst & ls, const lst & lr) const { return bp->subs(ls, lr); } - ex subs(const ex & e) const { return bp->subs(e); } + bool match(const ex & pattern, lst & repl_lst) const { return bp->match(pattern, repl_lst); } + ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const { return bp->subs(ls, lr, no_pattern); } + ex subs(const ex & e, bool no_pattern = false) const { return bp->subs(e, no_pattern); } exvector get_free_indices(void) const { return bp->get_free_indices(); } ex simplify_indexed(void) const; ex simplify_indexed(const scalar_products & sp) const; @@ -370,6 +371,9 @@ inline ex diff(const ex & thisex, const symbol & s, unsigned nth = 1) inline ex series(const ex & thisex, const ex & r, int order, unsigned options = 0) { return thisex.series(r, order, options); } +inline bool match(const ex & thisex, const ex & pattern, lst & repl_lst) +{ return thisex.match(pattern, repl_lst); } + inline ex subs(const ex & thisex, const ex & e) { return thisex.subs(e); } diff --git a/ginac/expairseq.cpp b/ginac/expairseq.cpp index b14ffb30..2d9a8f6b 100644 --- a/ginac/expairseq.cpp +++ b/ginac/expairseq.cpp @@ -26,6 +26,7 @@ #include "expairseq.h" #include "lst.h" +#include "relational.h" #include "print.h" #include "archive.h" #include "debugmsg.h" @@ -321,13 +322,87 @@ ex expairseq::normal(lst &sym_lst, lst &repl_lst, int level) const return n.bp->basic::normal(sym_lst,repl_lst,level); } -ex expairseq::subs(const lst &ls, const lst &lr) const +bool expairseq::match(const ex & pattern, lst & repl_lst) const { - epvector *vp = subschildren(ls,lr); - if (vp==0) - return inherited::subs(ls, lr); - - return thisexpairseq(vp,overall_coeff); +//clog << "match " << *this << " with " << pattern << ", repl_lst = " << repl_lst << endl; + // This differs from basic::match() because we want "a+b+c+d" to + // match "d+*+b" with "*" being "a+c", and we want to honor commutativity + + if (tinfo() == pattern.bp->tinfo()) { + + // Check whether global wildcard (one that matches the "rest of the + // expression", like "*" above) is present + bool has_global_wildcard = false; + ex global_wildcard; + for (unsigned int i=0; imatch(p, repl_lst)) { + ops.erase(it); + goto found; + } + it++; + } + return false; // no match found +found: ; + } + + if (has_global_wildcard) { + + // Assign all the remaining terms to the global wildcard (unless + // it has already been matched before, in which case the matches + // must be equal) + epvector *vp = new epvector(); + vp->reserve(ops.size()); + for (unsigned i=0; ipush_back(split_ex_to_pair(ops[i])); + ex rest = thisexpairseq(vp, default_overall_coeff()); + for (unsigned i=0; ibasic::subs(ls, lr, no_pattern); + else + return basic::subs(ls, lr, no_pattern); } // protected @@ -1586,7 +1661,7 @@ epvector expairseq::diffchildren(const symbol &y) const * @see expairseq::subs() * @return pointer to epvector containing pairs after application of subs or zero * pointer, if no members were changed. */ -epvector * expairseq::subschildren(const lst &ls, const lst &lr) const +epvector * expairseq::subschildren(const lst &ls, const lst &lr, bool no_pattern) const { // returns a NULL pointer if nothing had to be substituted // returns a pointer to a newly created epvector otherwise @@ -1596,7 +1671,7 @@ epvector * expairseq::subschildren(const lst &ls, const lst &lr) const epvector::const_iterator last = seq.end(); epvector::const_iterator cit = seq.begin(); while (cit!=last) { - const ex &subsed_ex=(*cit).rest.subs(ls,lr); + const ex &subsed_ex=(*cit).rest.subs(ls,lr,no_pattern); if (!are_ex_trivially_equal((*cit).rest,subsed_ex)) { // something changed, copy seq, subs and return it @@ -1615,7 +1690,7 @@ epvector * expairseq::subschildren(const lst &ls, const lst &lr) const ++cit2; // copy rest while (cit2!=last) { - s->push_back(combine_ex_with_coeff_to_pair((*cit2).rest.subs(ls,lr), + s->push_back(combine_ex_with_coeff_to_pair((*cit2).rest.subs(ls,lr,no_pattern), (*cit2).coeff)); ++cit2; } diff --git a/ginac/expairseq.h b/ginac/expairseq.h index fac36eec..3851a578 100644 --- a/ginac/expairseq.h +++ b/ginac/expairseq.h @@ -97,7 +97,8 @@ public: ex evalf(int level=0) const; ex normal(lst &sym_lst, lst &repl_lst, int level=0) const; ex to_rational(lst &repl_lst) const; - ex subs(const lst & ls, const lst & lr) const; + bool match(const ex & pattern, lst & repl_lst) const; + ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const; protected: ex derivative(const symbol & s) const; int compare_same_type(const basic & other) const; @@ -168,7 +169,7 @@ protected: epvector evalfchildren(int level) const; epvector normalchildren(int level) const; epvector diffchildren(const symbol & s) const; - epvector * subschildren(const lst & ls, const lst & lr) const; + epvector * subschildren(const lst & ls, const lst & lr, bool no_pattern = false) const; // member variables diff --git a/ginac/function.pl b/ginac/function.pl index a08d35f1..b0564e6e 100755 --- a/ginac/function.pl +++ b/ginac/function.pl @@ -344,6 +344,7 @@ public: ex evalf(int level=0) const; unsigned calchash(void) const; ex series(const relational & r, int order, unsigned options = 0) const; + bool match(const ex & pattern, lst & repl_lst) const; ex thisexprseq(const exvector & v) const; ex thisexprseq(exvector * vp) const; protected: @@ -801,6 +802,14 @@ ${series_switch_statement} throw(std::logic_error("function::series(): invalid nparams")); } +bool function::match(const ex & pattern, lst & repl_lst) const +{ + // Serial number must match + if (is_ex_of_type(pattern, function) && serial != ex_to_function(pattern).serial) + return false; + return inherited::match(pattern, repl_lst); +} + // protected diff --git a/ginac/ginac.h b/ginac/ginac.h index 1dc48fe0..e7684e59 100644 --- a/ginac/ginac.h +++ b/ginac/ginac.h @@ -41,6 +41,7 @@ #include "relational.h" #include "structure.h" #include "symbol.h" +#include "wildcard.h" #include "expair.h" #include "expairseq.h" diff --git a/ginac/idx.cpp b/ginac/idx.cpp index d54f5192..117a02b2 100644 --- a/ginac/idx.cpp +++ b/ginac/idx.cpp @@ -318,7 +318,7 @@ int spinidx::compare_same_type(const basic & other) const return 0; } -ex idx::subs(const lst & ls, const lst & lr) const +ex idx::subs(const lst & ls, const lst & lr, bool no_pattern) const { GINAC_ASSERT(ls.nops() == lr.nops()); @@ -339,7 +339,7 @@ ex idx::subs(const lst & ls, const lst & lr) const } // None, substitute objects in value (not in dimension) - const ex &subsed_value = value.subs(ls, lr); + const ex &subsed_value = value.subs(ls, lr, no_pattern); if (are_ex_trivially_equal(value, subsed_value)) return *this; diff --git a/ginac/idx.h b/ginac/idx.h index f8c1f060..02caba5a 100644 --- a/ginac/idx.h +++ b/ginac/idx.h @@ -52,7 +52,7 @@ public: unsigned nops() const; ex & let_op(int i); protected: - ex subs(const lst & ls, const lst & lr) const; + ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const; // new virtual functions in this class public: diff --git a/ginac/matrix.cpp b/ginac/matrix.cpp index 8a68b663..65b12549 100644 --- a/ginac/matrix.cpp +++ b/ginac/matrix.cpp @@ -208,22 +208,6 @@ ex matrix::expand(unsigned options) const return matrix(row, col, tmp); } -/** Search ocurrences. A matrix 'has' an expression if it is the expression - * itself or one of the elements 'has' it. */ -bool matrix::has(const ex & other) const -{ - GINAC_ASSERT(other.bp!=0); - - // tautology: it is the expression itself - if (is_equal(*other.bp)) return true; - - // search all the elements - for (exvector::const_iterator r=m.begin(); r!=m.end(); ++r) - if ((*r).has(other)) return true; - - return false; -} - /** Evaluate matrix entry by entry. */ ex matrix::eval(int level) const { @@ -272,14 +256,14 @@ ex matrix::evalf(int level) const return matrix(row, col, m2); } -ex matrix::subs(const lst & ls, const lst & lr) const +ex matrix::subs(const lst & ls, const lst & lr, bool no_pattern) const { exvector m2(row * col); for (unsigned r=0; rbasic::subs(ls, lr, no_pattern); } // protected diff --git a/ginac/matrix.h b/ginac/matrix.h index 53929bc5..56428871 100644 --- a/ginac/matrix.h +++ b/ginac/matrix.h @@ -47,10 +47,9 @@ public: ex op(int i) const; ex & let_op(int i); ex expand(unsigned options=0) const; - bool has(const ex & other) const; ex eval(int level=0) const; ex evalf(int level=0) const; - ex subs(const lst & ls, const lst & lr) const; + ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const; ex eval_indexed(const basic & i) const; ex add_indexed(const ex & self, const ex & other) const; ex scalar_mul_indexed(const ex & self, const numeric & other) const; diff --git a/ginac/power.cpp b/ginac/power.cpp index eee137bb..d4c12c17 100644 --- a/ginac/power.cpp +++ b/ginac/power.cpp @@ -472,17 +472,16 @@ ex power::evalf(int level) const return power(ebasis,eexponent); } -ex power::subs(const lst & ls, const lst & lr) const +ex power::subs(const lst & ls, const lst & lr, bool no_pattern) const { - const ex & subsed_basis=basis.subs(ls,lr); - const ex & subsed_exponent=exponent.subs(ls,lr); + const ex &subsed_basis = basis.subs(ls, lr, no_pattern); + const ex &subsed_exponent = exponent.subs(ls, lr, no_pattern); - if (are_ex_trivially_equal(basis,subsed_basis)&& - are_ex_trivially_equal(exponent,subsed_exponent)) { - return inherited::subs(ls, lr); - } - - return power(subsed_basis, subsed_exponent); + if (are_ex_trivially_equal(basis, subsed_basis) + && are_ex_trivially_equal(exponent, subsed_exponent)) + return basic::subs(ls, lr, no_pattern); + else + return ex(power(subsed_basis, subsed_exponent)).bp->basic::subs(ls, lr, no_pattern); } ex power::simplify_ncmul(const exvector & v) const diff --git a/ginac/power.h b/ginac/power.h index 480e091a..8f7ac501 100644 --- a/ginac/power.h +++ b/ginac/power.h @@ -59,7 +59,7 @@ public: ex eval(int level=0) const; ex evalf(int level=0) const; ex series(const relational & s, int order, unsigned options = 0) const; - ex subs(const lst & ls, const lst & lr) const; + ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const; ex normal(lst &sym_lst, lst &repl_lst, int level = 0) const; ex to_rational(lst &repl_lst) const; exvector get_free_indices(void) const; diff --git a/ginac/pseries.cpp b/ginac/pseries.cpp index 9d04f6a9..1477449c 100644 --- a/ginac/pseries.cpp +++ b/ginac/pseries.cpp @@ -393,13 +393,13 @@ ex pseries::evalf(int level) const return (new pseries(relational(var,point), new_seq))->setflag(status_flags::dynallocated | status_flags::evaluated); } -ex pseries::subs(const lst & ls, const lst & lr) const +ex pseries::subs(const lst & ls, const lst & lr, bool no_pattern) const { // If expansion variable is being substituted, convert the series to a // polynomial and do the substitution there because the result might // no longer be a power series if (ls.has(var)) - return convert_to_poly(true).subs(ls, lr); + return convert_to_poly(true).subs(ls, lr, no_pattern); // Otherwise construct a new series with substituted coefficients and // expansion point @@ -407,10 +407,10 @@ ex pseries::subs(const lst & ls, const lst & lr) const newseq.reserve(seq.size()); epvector::const_iterator it = seq.begin(), itend = seq.end(); while (it != itend) { - newseq.push_back(expair(it->rest.subs(ls, lr), it->coeff)); + newseq.push_back(expair(it->rest.subs(ls, lr, no_pattern), it->coeff)); ++it; } - return (new pseries(relational(var,point.subs(ls, lr)), newseq))->setflag(status_flags::dynallocated); + return (new pseries(relational(var,point.subs(ls, lr, no_pattern)), newseq))->setflag(status_flags::dynallocated); } /** Implementation of ex::expand() for a power series. It expands all the diff --git a/ginac/pseries.h b/ginac/pseries.h index 18baed39..72586eaf 100644 --- a/ginac/pseries.h +++ b/ginac/pseries.h @@ -54,7 +54,7 @@ public: ex eval(int level=0) const; ex evalf(int level=0) const; ex series(const relational & r, int order, unsigned options = 0) const; - ex subs(const lst & ls, const lst & lr) const; + ex subs(const lst & ls, const lst & lr, bool no_pattern = false) const; ex normal(lst &sym_lst, lst &repl_lst, int level = 0) const; ex expand(unsigned options = 0) const; protected: diff --git a/ginac/tinfos.h b/ginac/tinfos.h index 2a5fad61..3faea2fc 100644 --- a/ginac/tinfos.h +++ b/ginac/tinfos.h @@ -82,6 +82,8 @@ const unsigned TINFO_diracone = 0x000e100cU; const unsigned TINFO_diracgamma = 0x000e100dU; const unsigned TINFO_diracgamma5 = 0x000e100eU; +const unsigned TINFO_wildcard = 0x000f0001U; + } // namespace GiNaC #endif // ndef __GINAC_TINFOS_H__ diff --git a/ginac/wildcard.cpp b/ginac/wildcard.cpp new file mode 100644 index 00000000..0d782622 --- /dev/null +++ b/ginac/wildcard.cpp @@ -0,0 +1,124 @@ +/** @file wildcard.cpp + * + * Implementation of GiNaC's wildcard objects. */ + +/* + * GiNaC Copyright (C) 1999-2001 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include "wildcard.h" +#include "print.h" +#include "archive.h" +#include "utils.h" +#include "debugmsg.h" + +namespace GiNaC { + +GINAC_IMPLEMENT_REGISTERED_CLASS(wildcard, basic) + +////////// +// default constructor, destructor, copy constructor assignment operator and helpers +////////// + +wildcard::wildcard() : label(0) +{ + debugmsg("wildcard default constructor", LOGLEVEL_CONSTRUCT); + tinfo_key = TINFO_wildcard; +} + +void wildcard::copy(const wildcard & other) +{ + inherited::copy(other); + label = other.label; +} + +DEFAULT_DESTROY(wildcard) + +////////// +// other constructors +////////// + +wildcard::wildcard(unsigned l) : label(l) +{ + debugmsg("wildcard constructor from unsigned", LOGLEVEL_CONSTRUCT); + tinfo_key = TINFO_wildcard; +} + +////////// +// archiving +////////// + +wildcard::wildcard(const archive_node &n, const lst &sym_lst) : inherited(n, sym_lst) +{ + debugmsg("wildcard constructor from archive_node", LOGLEVEL_CONSTRUCT); + n.find_unsigned("label", label); +} + +void wildcard::archive(archive_node &n) const +{ + inherited::archive(n); + n.add_unsigned("label", label); +} + +DEFAULT_UNARCHIVE(wildcard) + +////////// +// functions overriding virtual functions from bases classes +////////// + +int wildcard::compare_same_type(const basic & other) const +{ + GINAC_ASSERT(is_of_type(other, wildcard)); + const wildcard &o = static_cast(other); + + if (label == o.label) + return 0; + else + return label < o.label ? -1 : 1; +} + +void wildcard::print(const print_context & c, unsigned level = 0) const +{ + debugmsg("wildcard print", LOGLEVEL_PRINT); + + if (is_of_type(c, print_tree)) { + c.s << std::string(level, ' ') << class_name() << " (" << label << ")" + << std::hex << ", hash=0x" << hashvalue << ", flags=0x" << flags << std::dec + << std::endl; + } else + c.s << "$" << label; +} + +unsigned wildcard::calchash(void) const +{ + // this is where the schoolbook method + // (golden_ratio_hash(tinfo()) ^ label) + // is not good enough yet... + hashvalue = golden_ratio_hash(golden_ratio_hash(tinfo()) ^ label); + setflag(status_flags::hash_calculated); + return hashvalue; +} + +bool wildcard::match(const ex & pattern, lst & repl_lst) const +{ + // Wildcards must match exactly (this is required for subs() to work + // properly because in the final step it substitues all wildcards by + // their matching expressions) + return is_equal(*pattern.bp); +} + +} // namespace GiNaC diff --git a/ginac/wildcard.h b/ginac/wildcard.h new file mode 100644 index 00000000..e55788e7 --- /dev/null +++ b/ginac/wildcard.h @@ -0,0 +1,72 @@ +/** @file wildcard.h + * + * Interface to GiNaC's wildcard objects. */ + +/* + * GiNaC Copyright (C) 1999-2001 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef __GINAC_WILDCARD_H__ +#define __GINAC_WILDCARD_H__ + +#include "ex.h" + +namespace GiNaC { + + +/** This class acts as a wildcard for subs() and matches(). An integer label + * is used to identify different wildcards. */ +class wildcard : public basic +{ + GINAC_DECLARE_REGISTERED_CLASS(wildcard, basic) + + // other constructors +public: + /** Construct wildcard with specified label. */ + wildcard(unsigned label); + + // functions overriding virtual functions from bases classes +public: + void print(const print_context & c, unsigned level = 0) const; + unsigned calchash(void) const; + bool match(const ex & pattern, lst & repl_lst) const; + + // non-virtual functions in this class +public: + unsigned get_label(void) const {return label;} + + // member variables +private: + unsigned label; /**< Label used to distinguish different wildcards */ +}; + + +// global functions +inline const wildcard &ex_to_wildcard(const ex &e) +{ + return static_cast(*e.bp); +} + +/** Create a wildcard object with the specified label. */ +inline ex wild(unsigned label = 0) +{ + return wildcard(label); +} + +} // namespace GiNaC + +#endif // ndef __GINAC_WILDCARD_H__ diff --git a/ginsh/ginsh.1.in b/ginsh/ginsh.1.in index 97c0bbbc..a19be9c0 100644 --- a/ginsh/ginsh.1.in +++ b/ginsh/ginsh.1.in @@ -292,6 +292,9 @@ detail here. Please refer to the GiNaC documentation. .BI lsolve( equation-list ", " symbol-list ) \- solve system of linear equations .br +.BI match( expression ", " pattern ) +\- check whether expression matches a pattern; returns a list of wildcard substitutions or "FAIL" if there is no match +.br .BI nops( expression ) \- number of operands in expression .br diff --git a/ginsh/ginsh_lexer.ll b/ginsh/ginsh_lexer.ll index 20cb3297..a8a2b10e 100644 --- a/ginsh/ginsh_lexer.ll +++ b/ginsh/ginsh_lexer.ll @@ -113,6 +113,9 @@ score return T_SCORE; return T_SYMBOL; } + /* wildcards */ +\${D}+ yylval = wild(atoi(yytext + 1)); return T_LITERAL; + /* everything else */ . return *yytext; diff --git a/ginsh/ginsh_parser.yy b/ginsh/ginsh_parser.yy index 3f862bda..48d839a0 100644 --- a/ginsh/ginsh_parser.yy +++ b/ginsh/ginsh_parser.yy @@ -400,6 +400,15 @@ static ex f_ldegree(const exprseq &e) return e[0].ldegree(e[1]); } +static ex f_match(const exprseq &e) +{ + lst repl_lst; + if (e[0].match(e[1], repl_lst)) + return repl_lst; + else + return fail(); +} + static ex f_normal2(const exprseq &e) { CHECK_ARG(1, numeric, normal); @@ -530,6 +539,7 @@ static const fcn_init builtin_fcns[] = { {"lcoeff", fcn_desc(f_lcoeff, 2)}, {"ldegree", fcn_desc(f_ldegree, 2)}, {"lsolve", fcn_desc(f_lsolve, 2)}, + {"match", fcn_desc(f_match, 2)}, {"nops", fcn_desc(f_nops, 1)}, {"normal", fcn_desc(f_normal1, 1)}, {"normal", fcn_desc(f_normal2, 2)}, -- 2.44.0