* Implementation of GiNaC's light-weight expression handles. */
/*
- * GiNaC Copyright (C) 1999-2001 Johannes Gutenberg University Mainz, Germany
+ * GiNaC Copyright (C) 1999-2019 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
*
* 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
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include <iostream>
-#include <stdexcept>
-
#include "ex.h"
#include "add.h"
#include "mul.h"
#include "ncmul.h"
#include "numeric.h"
+#include "matrix.h"
#include "power.h"
+#include "lst.h"
#include "relational.h"
-#include "indexed.h"
-#include "input_lexer.h"
-#include "debugmsg.h"
#include "utils.h"
+#include <iostream>
+#include <stdexcept>
+
namespace GiNaC {
//////////
-// other ctors
+// other constructors
//////////
// none (all inlined)
-//////////
-// functions overriding virtual functions from bases classes
-//////////
-
-// none
-
-//////////
-// new virtual functions which can be overridden by derived classes
-//////////
-
-// none
-
//////////
// non-virtual functions in this class
//////////
// public
-
-/** Efficiently swap the contents of two expressions. */
-void ex::swap(ex & other)
-{
- debugmsg("ex swap",LOGLEVEL_MEMBER_FUNCTION);
-
- GINAC_ASSERT(bp!=0);
- GINAC_ASSERT(bp->flags & status_flags::dynallocated);
- GINAC_ASSERT(other.bp!=0);
- GINAC_ASSERT(other.bp->flags & status_flags::dynallocated);
- basic * tmpbp = bp;
- bp = other.bp;
- other.bp = tmpbp;
-}
-
/** Print expression to stream. The formatting of the output is determined
* by the kind of print_context object that is passed. Possible formattings
* include ginsh-parsable output (the default), tree-like output for
* @see print_context */
void ex::print(const print_context & c, unsigned level) const
{
- debugmsg("ex print", LOGLEVEL_PRINT);
- GINAC_ASSERT(bp!=0);
bp->print(c, level);
}
-/** Print expression to stream in a tree-like format suitable for debugging. */
-void ex::printtree(std::ostream & os) const
-{
- debugmsg("ex printtree", LOGLEVEL_PRINT);
- GINAC_ASSERT(bp!=0);
- bp->print(print_tree(os));
-}
-
/** Little wrapper arount print to be called within a debugger. */
-void ex::dbgprint(void) const
+void ex::dbgprint() const
{
- debugmsg("ex dbgprint", LOGLEVEL_PRINT);
- GINAC_ASSERT(bp!=0);
bp->dbgprint();
}
/** Little wrapper arount printtree to be called within a debugger. */
-void ex::dbgprinttree(void) const
+void ex::dbgprinttree() const
{
- debugmsg("ex dbgprinttree", LOGLEVEL_PRINT);
- GINAC_ASSERT(bp!=0);
bp->dbgprinttree();
}
ex ex::expand(unsigned options) const
{
- GINAC_ASSERT(bp!=0);
- if (bp->flags & status_flags::expanded)
- return *bp;
+ if (options == 0 && (bp->flags & status_flags::expanded)) // The "expanded" flag only covers the standard options; someone might want to re-expand with different options
+ return *this;
else
return bp->expand(options);
}
* @return partial derivative as a new expression */
ex ex::diff(const symbol & s, unsigned nth) const
{
- GINAC_ASSERT(bp!=0);
-
if (!nth)
return *this;
else
return bp->diff(s, nth);
}
-/** Simplify/canonicalize expression containing indexed objects. This
- * performs contraction of dummy indices where possible and checks whether
- * the free indices in sums are consistent.
- *
- * @return simplified expression */
-ex ex::simplify_indexed(void) const
+/** Check whether expression matches a specified pattern. */
+bool ex::match(const ex & pattern) const
{
- return GiNaC::simplify_indexed(*this);
+ exmap repl_lst;
+ return bp->match(pattern, repl_lst);
}
-/** Simplify/canonicalize expression containing indexed objects. This
- * performs contraction of dummy indices where possible, checks whether
- * the free indices in sums are consistent, and automatically replaces
- * scalar products by known values if desired.
- *
- * @param sp Scalar products to be replaced automatically
- * @return simplified expression */
-ex ex::simplify_indexed(const scalar_products & sp) const
+/** Find all occurrences of a pattern. The found matches are appended to
+ * the "found" list. If the expression itself matches the pattern, the
+ * children are not further examined. This function returns true when any
+ * matches were found. */
+bool ex::find(const ex & pattern, exset& found) const
{
- return GiNaC::simplify_indexed(*this, sp);
+ if (match(pattern)) {
+ found.insert(*this);
+ return true;
+ }
+ bool any_found = false;
+ for (size_t i=0; i<nops(); i++)
+ if (op(i).find(pattern, found))
+ any_found = true;
+ return any_found;
}
-ex ex::operator[](const ex & index) const
+/** Substitute objects in an expression (syntactic substitution) and return
+ * the result as a new expression. */
+ex ex::subs(const lst & ls, const lst & lr, unsigned options) const
{
- debugmsg("ex operator[ex]",LOGLEVEL_OPERATOR);
- GINAC_ASSERT(bp!=0);
- return (*bp)[index];
+ GINAC_ASSERT(ls.nops() == lr.nops());
+
+ // Convert the lists to a map
+ exmap m;
+ for (auto its = ls.begin(), itr = lr.begin(); its != ls.end(); ++its, ++itr) {
+ m.insert(std::make_pair(*its, *itr));
+
+ // Search for products and powers in the expressions to be substituted
+ // (for an optimization in expairseq::subs())
+ if (is_exactly_a<mul>(*its) || is_exactly_a<power>(*its))
+ options |= subs_options::pattern_is_product;
+ }
+ if (!(options & subs_options::pattern_is_product))
+ options |= subs_options::pattern_is_not_product;
+
+ return bp->subs(m, options);
}
-ex ex::operator[](int i) const
+/** Substitute objects in an expression (syntactic substitution) and return
+ * the result as a new expression. There are two valid types of
+ * replacement arguments: 1) a relational like object==ex and 2) a list of
+ * relationals lst{object1==ex1,object2==ex2,...}. */
+ex ex::subs(const ex & e, unsigned options) const
{
- debugmsg("ex operator[int]",LOGLEVEL_OPERATOR);
- GINAC_ASSERT(bp!=0);
- return (*bp)[i];
+ if (e.info(info_flags::relation_equal)) {
+
+ // Argument is a relation: convert it to a map
+ exmap m;
+ const ex & s = e.op(0);
+ m.insert(std::make_pair(s, e.op(1)));
+
+ if (is_exactly_a<mul>(s) || is_exactly_a<power>(s))
+ options |= subs_options::pattern_is_product;
+ else
+ options |= subs_options::pattern_is_not_product;
+
+ return bp->subs(m, options);
+
+ } else if (e.info(info_flags::list)) {
+
+ // Argument is a list: convert it to a map
+ exmap m;
+ GINAC_ASSERT(is_a<lst>(e));
+ for (auto & r : ex_to<lst>(e)) {
+ if (!r.info(info_flags::relation_equal))
+ throw(std::invalid_argument("basic::subs(ex): argument must be a list of equations"));
+ const ex & s = r.op(0);
+ m.insert(std::make_pair(s, r.op(1)));
+
+ // Search for products and powers in the expressions to be substituted
+ // (for an optimization in expairseq::subs())
+ if (is_exactly_a<mul>(s) || is_exactly_a<power>(s))
+ options |= subs_options::pattern_is_product;
+ }
+ if (!(options & subs_options::pattern_is_product))
+ options |= subs_options::pattern_is_not_product;
+
+ return bp->subs(m, options);
+
+ } else
+ throw(std::invalid_argument("ex::subs(ex): argument must be a relation_equal or a list"));
}
-/** Return modifyable operand/member at position i. */
-ex & ex::let_op(int i)
+/** Traverse expression tree with given visitor, preorder traversal. */
+void ex::traverse_preorder(visitor & v) const
+{
+ accept(v);
+
+ size_t n = nops();
+ for (size_t i = 0; i < n; ++i)
+ op(i).traverse_preorder(v);
+}
+
+/** Traverse expression tree with given visitor, postorder traversal. */
+void ex::traverse_postorder(visitor & v) const
+{
+ size_t n = nops();
+ for (size_t i = 0; i < n; ++i)
+ op(i).traverse_postorder(v);
+
+ accept(v);
+}
+
+/** Return modifiable operand/member at position i. */
+ex & ex::let_op(size_t i)
{
- debugmsg("ex let_op()",LOGLEVEL_MEMBER_FUNCTION);
makewriteable();
- GINAC_ASSERT(bp!=0);
return bp->let_op(i);
}
+ex & ex::operator[](const ex & index)
+{
+ makewriteable();
+ return (*bp)[index];
+}
+
+ex & ex::operator[](size_t i)
+{
+ makewriteable();
+ return (*bp)[i];
+}
+
/** Left hand side of relational expression. */
-ex ex::lhs(void) const
+ex ex::lhs() const
{
- debugmsg("ex lhs()",LOGLEVEL_MEMBER_FUNCTION);
- if (!is_ex_of_type(*this,relational))
+ if (!is_a<relational>(*this))
throw std::runtime_error("ex::lhs(): not a relation");
- return (*static_cast<relational *>(bp)).lhs();
+ return bp->op(0);
}
/** Right hand side of relational expression. */
-ex ex::rhs(void) const
+ex ex::rhs() const
{
- debugmsg("ex rhs()",LOGLEVEL_MEMBER_FUNCTION);
- if (!is_ex_of_type(*this,relational))
+ if (!is_a<relational>(*this))
throw std::runtime_error("ex::rhs(): not a relation");
- return (*static_cast<relational *>(bp)).rhs();
+ return bp->op(1);
}
-/** Used internally by operator+() to add two ex objects together. */
-ex ex::exadd(const ex & rh) const
+/** Check whether expression is a polynomial. */
+bool ex::is_polynomial(const ex & vars) const
{
- return (new add(*this,rh))->setflag(status_flags::dynallocated);
+ if (is_a<lst>(vars)) {
+ const lst & varlst = ex_to<lst>(vars);
+ for (auto & it : varlst)
+ if (!bp->is_polynomial(it))
+ return false;
+ return true;
+ }
+ else
+ return bp->is_polynomial(vars);
}
-/** Used internally by operator*() to multiply two ex objects together. */
-ex ex::exmul(const ex & rh) const
+/** Check whether expression is zero or zero matrix. */
+bool ex::is_zero_matrix() const
{
- // Check if we are constructing a mul object or a ncmul object. Due to
- // ncmul::eval()'s rule to pull out commutative elements we need to check
- // only one of the elements.
- if (rh.bp->return_type()==return_types::commutative ||
- bp->return_type()==return_types::commutative)
- return (new mul(*this,rh))->setflag(status_flags::dynallocated);
- else
- return (new ncmul(*this,rh))->setflag(status_flags::dynallocated);
+ if (is_zero())
+ return true;
+ else {
+ ex e = evalm();
+ return is_a<matrix>(e) && ex_to<matrix>(e).is_zero_matrix();
+ }
}
// private
* unlinking the object and creating an unshared copy of it. */
void ex::makewriteable()
{
- debugmsg("ex makewriteable",LOGLEVEL_MEMBER_FUNCTION);
- GINAC_ASSERT(bp!=0);
GINAC_ASSERT(bp->flags & status_flags::dynallocated);
- if (bp->refcount > 1) {
- basic * bp2 = bp->duplicate();
- ++bp2->refcount;
- bp2->setflag(status_flags::dynallocated);
- --bp->refcount;
- bp = bp2;
- }
- GINAC_ASSERT(bp->refcount==1);
+ bp.makewritable();
+ GINAC_ASSERT(bp->get_refcount() == 1);
+}
+
+/** Share equal objects between expressions.
+ * @see ex::compare(const ex &) */
+void ex::share(const ex & other) const
+{
+ if ((bp->flags | other.bp->flags) & status_flags::not_shareable)
+ return;
+
+ if (bp->get_refcount() <= other.bp->get_refcount())
+ bp = other.bp;
+ else
+ other.bp = bp;
}
-/** Ctor from basic implementation.
+/** Helper function for the ex-from-basic constructor. This is where GiNaC's
+ * automatic evaluator and memory management are implemented.
* @see ex::ex(const basic &) */
-void ex::construct_from_basic(const basic & other)
+ptr<basic> ex::construct_from_basic(const basic & other)
{
- if ((other.flags & status_flags::evaluated)==0) {
- // cf. copy ctor
- const ex & tmpex = other.eval(1); // evaluate only one (top) level
- bp = tmpex.bp;
- GINAC_ASSERT(bp!=0);
- GINAC_ASSERT(bp->flags & status_flags::dynallocated);
- ++bp->refcount;
- if ((other.flags & status_flags::dynallocated)&&(other.refcount==0))
- delete &const_cast<basic &>(other);
+ if (!(other.flags & status_flags::evaluated)) {
+
+ // The object is not yet evaluated, so call eval() to evaluate
+ // the top level. This will return either
+ // a) the original object with status_flags::evaluated set (when the
+ // eval() implementation calls hold())
+ // or
+ // b) a different expression.
+ //
+ // eval() returns an ex, not a basic&, so this will go through
+ // construct_from_basic() a second time. In case a) we end up in
+ // the "else" branch below. In case b) we end up here again and
+ // apply eval() once more. The recursion stops when eval() calls
+ // hold() or returns an object that already has its "evaluated"
+ // flag set, such as a symbol or a numeric.
+ const ex & tmpex = other.eval();
+
+ // Eventually, the eval() recursion goes through the "else" branch
+ // below, which assures that the object pointed to by tmpex.bp is
+ // allocated on the heap (either it was already on the heap or it
+ // is a heap-allocated duplicate of another object).
+ GINAC_ASSERT(tmpex.bp->flags & status_flags::dynallocated);
+
+ // If the original object is not referenced but heap-allocated,
+ // it means that eval() hit case b) above. The original object is
+ // no longer needed (it evaluated into something different), so we
+ // delete it (because nobody else will).
+ if ((other.get_refcount() == 0) && (other.flags & status_flags::dynallocated))
+ delete &other; // yes, you can apply delete to a const pointer
+
+ // We can't return a basic& here because the tmpex is destroyed as
+ // soon as we leave the function, which would deallocate the
+ // evaluated object.
+ return tmpex.bp;
+
} else {
+
+ // The easy case: making an "ex" out of an evaluated object.
if (other.flags & status_flags::dynallocated) {
- // ok, it is already on the heap, so just copy bp:
- bp = &const_cast<basic &>(other);
+
+ // The object is already heap-allocated, so we can just make
+ // another reference to it.
+ return ptr<basic>(const_cast<basic &>(other));
+
} else {
- // create a duplicate on the heap:
- bp = other.duplicate();
+
+ // The object is not heap-allocated, so we create a duplicate
+ // on the heap.
+ basic *bp = other.duplicate();
bp->setflag(status_flags::dynallocated);
+ GINAC_ASSERT(bp->get_refcount() == 0);
+ return bp;
}
- GINAC_ASSERT(bp!=0);
- ++bp->refcount;
}
- GINAC_ASSERT(bp!=0);
- GINAC_ASSERT(bp->flags & status_flags::dynallocated);
}
-void ex::construct_from_int(int i)
+basic & ex::construct_from_int(int i)
{
- switch (i) { // some tiny efficiency-hack
+ switch (i) { // prefer flyweights over new objects
+ case -12:
+ return *const_cast<numeric *>(_num_12_p);
+ case -11:
+ return *const_cast<numeric *>(_num_11_p);
+ case -10:
+ return *const_cast<numeric *>(_num_10_p);
+ case -9:
+ return *const_cast<numeric *>(_num_9_p);
+ case -8:
+ return *const_cast<numeric *>(_num_8_p);
+ case -7:
+ return *const_cast<numeric *>(_num_7_p);
+ case -6:
+ return *const_cast<numeric *>(_num_6_p);
+ case -5:
+ return *const_cast<numeric *>(_num_5_p);
+ case -4:
+ return *const_cast<numeric *>(_num_4_p);
+ case -3:
+ return *const_cast<numeric *>(_num_3_p);
case -2:
- bp = _ex_2().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num_2_p);
case -1:
- bp = _ex_1().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num_1_p);
case 0:
- bp = _ex0().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num0_p);
case 1:
- bp = _ex1().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num1_p);
case 2:
- bp = _ex2().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num2_p);
+ case 3:
+ return *const_cast<numeric *>(_num3_p);
+ case 4:
+ return *const_cast<numeric *>(_num4_p);
+ case 5:
+ return *const_cast<numeric *>(_num5_p);
+ case 6:
+ return *const_cast<numeric *>(_num6_p);
+ case 7:
+ return *const_cast<numeric *>(_num7_p);
+ case 8:
+ return *const_cast<numeric *>(_num8_p);
+ case 9:
+ return *const_cast<numeric *>(_num9_p);
+ case 10:
+ return *const_cast<numeric *>(_num10_p);
+ case 11:
+ return *const_cast<numeric *>(_num11_p);
+ case 12:
+ return *const_cast<numeric *>(_num12_p);
default:
- bp = new numeric(i);
- bp->setflag(status_flags::dynallocated);
- ++bp->refcount;
- GINAC_ASSERT((bp->flags) & status_flags::dynallocated);
- GINAC_ASSERT(bp->refcount==1);
+ return dynallocate<numeric>(i);
}
}
-void ex::construct_from_uint(unsigned int i)
+basic & ex::construct_from_uint(unsigned int i)
{
- switch (i) { // some tiny efficiency-hack
+ switch (i) { // prefer flyweights over new objects
case 0:
- bp = _ex0().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num0_p);
case 1:
- bp = _ex1().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num1_p);
case 2:
- bp = _ex2().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num2_p);
+ case 3:
+ return *const_cast<numeric *>(_num3_p);
+ case 4:
+ return *const_cast<numeric *>(_num4_p);
+ case 5:
+ return *const_cast<numeric *>(_num5_p);
+ case 6:
+ return *const_cast<numeric *>(_num6_p);
+ case 7:
+ return *const_cast<numeric *>(_num7_p);
+ case 8:
+ return *const_cast<numeric *>(_num8_p);
+ case 9:
+ return *const_cast<numeric *>(_num9_p);
+ case 10:
+ return *const_cast<numeric *>(_num10_p);
+ case 11:
+ return *const_cast<numeric *>(_num11_p);
+ case 12:
+ return *const_cast<numeric *>(_num12_p);
default:
- bp = new numeric(i);
- bp->setflag(status_flags::dynallocated);
- ++bp->refcount;
- GINAC_ASSERT((bp->flags) & status_flags::dynallocated);
- GINAC_ASSERT(bp->refcount==1);
+ return dynallocate<numeric>(i);
}
}
-void ex::construct_from_long(long i)
+basic & ex::construct_from_long(long i)
{
- switch (i) { // some tiny efficiency-hack
+ switch (i) { // prefer flyweights over new objects
+ case -12:
+ return *const_cast<numeric *>(_num_12_p);
+ case -11:
+ return *const_cast<numeric *>(_num_11_p);
+ case -10:
+ return *const_cast<numeric *>(_num_10_p);
+ case -9:
+ return *const_cast<numeric *>(_num_9_p);
+ case -8:
+ return *const_cast<numeric *>(_num_8_p);
+ case -7:
+ return *const_cast<numeric *>(_num_7_p);
+ case -6:
+ return *const_cast<numeric *>(_num_6_p);
+ case -5:
+ return *const_cast<numeric *>(_num_5_p);
+ case -4:
+ return *const_cast<numeric *>(_num_4_p);
+ case -3:
+ return *const_cast<numeric *>(_num_3_p);
case -2:
- bp = _ex_2().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num_2_p);
case -1:
- bp = _ex_1().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num_1_p);
case 0:
- bp = _ex0().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num0_p);
case 1:
- bp = _ex1().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num1_p);
case 2:
- bp = _ex2().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num2_p);
+ case 3:
+ return *const_cast<numeric *>(_num3_p);
+ case 4:
+ return *const_cast<numeric *>(_num4_p);
+ case 5:
+ return *const_cast<numeric *>(_num5_p);
+ case 6:
+ return *const_cast<numeric *>(_num6_p);
+ case 7:
+ return *const_cast<numeric *>(_num7_p);
+ case 8:
+ return *const_cast<numeric *>(_num8_p);
+ case 9:
+ return *const_cast<numeric *>(_num9_p);
+ case 10:
+ return *const_cast<numeric *>(_num10_p);
+ case 11:
+ return *const_cast<numeric *>(_num11_p);
+ case 12:
+ return *const_cast<numeric *>(_num12_p);
default:
- bp = new numeric(i);
- bp->setflag(status_flags::dynallocated);
- ++bp->refcount;
- GINAC_ASSERT((bp->flags) & status_flags::dynallocated);
- GINAC_ASSERT(bp->refcount==1);
+ return dynallocate<numeric>(i);
}
}
-void ex::construct_from_ulong(unsigned long i)
+basic & ex::construct_from_ulong(unsigned long i)
{
- switch (i) { // some tiny efficiency-hack
+ switch (i) { // prefer flyweights over new objects
case 0:
- bp = _ex0().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num0_p);
case 1:
- bp = _ex1().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num1_p);
case 2:
- bp = _ex2().bp;
- ++bp->refcount;
- break;
+ return *const_cast<numeric *>(_num2_p);
+ case 3:
+ return *const_cast<numeric *>(_num3_p);
+ case 4:
+ return *const_cast<numeric *>(_num4_p);
+ case 5:
+ return *const_cast<numeric *>(_num5_p);
+ case 6:
+ return *const_cast<numeric *>(_num6_p);
+ case 7:
+ return *const_cast<numeric *>(_num7_p);
+ case 8:
+ return *const_cast<numeric *>(_num8_p);
+ case 9:
+ return *const_cast<numeric *>(_num9_p);
+ case 10:
+ return *const_cast<numeric *>(_num10_p);
+ case 11:
+ return *const_cast<numeric *>(_num11_p);
+ case 12:
+ return *const_cast<numeric *>(_num12_p);
default:
- bp = new numeric(i);
- bp->setflag(status_flags::dynallocated);
- ++bp->refcount;
- GINAC_ASSERT((bp->flags) & status_flags::dynallocated);
- GINAC_ASSERT(bp->refcount==1);
+ return dynallocate<numeric>(i);
}
}
-void ex::construct_from_double(double d)
+basic & ex::construct_from_double(double d)
{
- bp = new numeric(d);
- bp->setflag(status_flags::dynallocated);
- ++bp->refcount;
- GINAC_ASSERT((bp->flags) & status_flags::dynallocated);
- GINAC_ASSERT(bp->refcount==1);
+ return dynallocate<numeric>(d);
}
-void ex::construct_from_string_and_lst(const std::string &s, const ex &l)
-{
- set_lexer_string(s);
- set_lexer_symbols(l);
- ginac_yyrestart(NULL);
- if (ginac_yyparse())
- throw (std::runtime_error(get_parser_error()));
- else {
- bp = parsed_ex.bp;
- GINAC_ASSERT(bp!=0);
- GINAC_ASSERT((bp->flags) & status_flags::dynallocated);
- ++bp->refcount;
- }
-}
-
//////////
// static member variables
//////////