1 /* 2 3 Cadabra: a field-theory motivated computer algebra system. 4 Copyright (C) 2001-2014 Kasper Peeters <kasper.peeters@phi-sci.com> 5 6 This program is free software: you can redistribute it and/or 7 modify it under the terms of the GNU General Public License as 8 published by the Free Software Foundation, either version 3 of the 9 License, or (at your option) any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program. If not, see <http://www.gnu.org/licenses/>. 18 19 */ 20 21 #pragma once 22 23 #include <cstddef> 24 #include <iostream> 25 #include <gmpxx.h> 26 #include <string> 27 #include <vector> 28 #include <set> 29 #include <map> 30 #include <stdint.h> 31 #include <assert.h> 32 #include <initializer_list> 33 34 #include "tree.hh" 35 36 namespace cadabra { 37 38 typedef mpq_class multiplier_t; 39 typedef std::set<std::string> nset_t; 40 typedef std::set<multiplier_t> rset_t; 41 typedef uintptr_t hashval_t; 42 43 long to_long(multiplier_t); 44 std::string to_string(long); 45 46 extern nset_t name_set; 47 extern rset_t rat_set; 48 49 /// \ingroup core 50 /// 51 /// Elementary building block for a mathematical expression. Contains information about the 52 /// way in which the node is related to the parent node, and iterators into the global 53 /// list of names and rationals. 54 55 class str_node { // size: 9 bytes (32 bit arch), can be reduced to 5 bytes. 56 public: 57 enum bracket_t { b_round=0, b_square=1, b_curly=2, b_pointy=3, b_none=4, b_no=5, b_invalid=6 }; 58 59 /// Child nodes are related to their parent node by a so-called parent relation, which can 60 /// be one of these values. 61 enum parent_rel_t { p_sub=0, p_super=1, p_none=2, p_property=3, p_exponent=4, p_components=5, p_invalid=7 }; 62 63 str_node(void); 64 str_node(nset_t::iterator name, bracket_t btype=b_none, parent_rel_t ptype=p_none); 65 str_node(const std::string& name, bracket_t btype=b_none, parent_rel_t ptype=p_none); 66 str_node(const std::u32string& name, bracket_t btype=b_none, parent_rel_t ptype=p_none); 67 68 bool operator==(const str_node&) const; 69 bool operator<(const str_node&) const; 70 71 nset_t::iterator name; 72 rset_t::iterator multiplier; 73 74 #ifdef _WIN32 75 struct flag_t { 76 bool keep_after_eval ; 77 bracket_t bracket ; 78 parent_rel_t parent_rel ; 79 bool line_per_node ; 80 }; 81 #else 82 struct flag_t { // kept inside 8 bits for speed and size 83 bool keep_after_eval : 1; 84 bracket_t bracket : 3; 85 parent_rel_t parent_rel : 3; 86 bool line_per_node : 1; 87 }; 88 #endif 89 90 flag_t fl; 91 92 /// Change the parent relation from sub to super and vice versa (throws error 93 /// when this is not an index). 94 void flip_parent_rel(); 95 96 bool is_zero() const; 97 bool is_identity() const; 98 bool is_rational() const; 99 bool is_unsimplified_rational() const; 100 bool is_integer() const; 101 bool is_unsimplified_integer() const; 102 bool is_index() const; // _ or ^ parent_rel (does not query properties) 103 bool is_quoted_string() const; 104 bool is_command() const; 105 bool is_inert_command() const; 106 bool is_name_wildcard() const; // ? 107 bool is_object_wildcard() const; // ?? 108 bool is_range_wildcard() const; // #{..} 109 bool is_siblings_wildcard() const; // a... 110 bool is_autodeclare_wildcard() const; // m# 111 bool is_indexstar_wildcard() const; // ?* in sub/super 112 bool is_indexplus_wildcard() const; // ?+ in sub/super 113 bool is_numbered_symbol() const; // [a-zA-Z]+[0-9]+ 114 115 nset_t::iterator name_only(); 116 117 static bool compare_names_only(const str_node&, const str_node&); 118 static bool compare_name_brack_par(const str_node&, const str_node&); 119 static bool compare_name_inverse_par(const str_node&, const str_node&); 120 }; 121 122 /// \ingroup core 123 /// 124 /// Helper functions for manipulation of multipliers. 125 void multiply(rset_t::iterator&, multiplier_t); 126 void add(rset_t::iterator&, multiplier_t); 127 void zero(rset_t::iterator&); 128 void one(rset_t::iterator&); 129 void flip_sign(rset_t::iterator&); 130 void half(rset_t::iterator&); 131 132 /// \ingroup core 133 /// 134 /// Basic storage class for symbolic mathemematical expressions. The 135 /// full meaning of an expression typically requires knowledge about 136 /// properties of patterns in it, which this class does _not_ 137 /// contain. All property dependent algorithms acting on Ex 138 /// objects are in Algorithm.hh. 139 140 class Ex : public std::enable_shared_from_this<Ex>, public tree<str_node> { 141 public: 142 Ex(); 143 // Ex(const tree<str_node>&); 144 Ex(tree<str_node>::iterator); 145 Ex(const str_node&); 146 Ex(const Ex&); 147 /// Initialise with given string as head node (does not parse this string). 148 Ex(const std::string&); 149 Ex(int); 150 151 /// Keeping track of what algorithms have done to this expression. 152 /// After a reset_state (or at initialisation), the expression sits 153 /// in the 'checkpointed' state. When an algorithm acts, it can then 154 /// move to 'no_action' (unchanged), 'applied' (changed) or 'error'. 155 /// Once it is in 'error', it will stay there until the next 'reset'. 156 /// FIXME: the following should implement a stack of states, 157 /// so that it can be used with nested functions. 158 159 enum result_t { l_checkpointed, l_no_action, l_applied, l_applied_no_new_dummies, l_error }; 160 result_t state() const; 161 void update_state(result_t); 162 void reset_state(); 163 164 /// A status query method mainly to implement a simple method to 165 /// apply algorithms until they converge. Returns true when the 166 /// expression is in 'checkpointed' or 'applied' state. Will 167 /// set the state to 'no_action'. 168 bool changed_state(); 169 170 /// Test if the expression is a rational number. 171 /// FIXME: add tests for integers as well. 172 bool is_rational() const; 173 multiplier_t to_rational() const; 174 bool is_integer() const; 175 long to_integer() const; 176 177 /// Display expression in Python/Cadabra input form. This is 178 /// fairly straightforward so not handled with a separate 179 /// DisplayBase derived class. 180 static std::ostream& print_python(std::ostream& str, Ex::iterator it); 181 182 /// Output helpers mainly for debugging purposes. 183 std::ostream& print_entire_tree(std::ostream& str) const; 184 static std::ostream& print_recursive_treeform(std::ostream& str, Ex::iterator it); 185 static std::ostream& print_recursive_treeform(std::ostream& str, Ex::iterator it, unsigned int& number); 186 187 /// Print a representation like Python's 'repr'. 188 std::ostream& print_repr(std::ostream& str, Ex::iterator it) const; 189 190 /// Step up until matching node is found (if current node matches, do nothing) 191 iterator named_parent(iterator it, const std::string&) const; 192 iterator erase_expression(iterator it); 193 194 /// Calculate the hash value for the subtree starting at 'it'. 195 hashval_t calc_hash(iterator it) const; 196 197 /// Quick access to arguments or argument lists for A(B)(C,D) type nodes. 198 static sibling_iterator arg(iterator, unsigned int); 199 static unsigned int arg_size(sibling_iterator); 200 201 multiplier_t arg_to_num(sibling_iterator, unsigned int) const; // shorthand for numerical arguments 202 203 // Like 'child', but using index iterators instead. 204 // sibling_iterator tensor_index(const iterator_base& position, unsigned int) const; 205 206 // Number of \\history nodes in an expression 207 unsigned int number_of_steps(iterator it) const; 208 // Given an iterator pointing to any node in the tree, figure 209 // out to which equation number it belongs. 210 unsigned int number_of_equations() const; 211 unsigned int equation_number(iterator it) const; 212 nset_t::iterator equation_label(iterator it) const; 213 iterator equation_by_number(unsigned int i) const; 214 iterator equation_by_name(nset_t::iterator it) const; 215 iterator equation_by_name(nset_t::iterator it, unsigned int& ) const; 216 iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation) const; 217 iterator equation_by_number_or_name(iterator it, unsigned int last_used_equation, 218 unsigned int&) const; 219 std::string equation_number_or_name(iterator it, unsigned int last_used_equation) const; 220 iterator procedure_by_name(nset_t::iterator it) const; 221 222 // Determine whether a node has an '\ldots' parent (not necessarily direct). 223 bool is_hidden(iterator) const; 224 225 /// Replace the index-like object (originally intended to 226 /// replace indices only, but now used also for e.g. normal 227 /// function arguments, as in \f[ \partial_{z}{ A(z) } \f] with 228 /// a replacement of z). 229 /// 230 /// Note: this originally kept the bracket and parent_rel, but 231 /// that is not a good idea, because it prevents us from 232 /// changing those. If we want to use a _{z} pattern replacing a 233 /// A(z) index, it is better to make a rule that matches (z) and 234 /// at the time we find and match _{z}. So this should be 235 /// handled by the replacement_map logic in Compare.cc. 236 iterator replace_index(iterator position, const iterator& from, bool keep_parent_rel=false); 237 238 /// As in replace_index, but moves the index rather than making a copy (so that iterators 239 /// pointing to the original remain valid). 240 iterator move_index(iterator position, const iterator& from); 241 242 /// Make sure that the node pointed to is a \\comma object, i.e. wrap the node if not already 243 /// inside such a \\comma. 244 /// DEPRECATED: in favour of 'do_list' in Functional.hh. 245 void list_wrap_single_element(iterator&); 246 void list_unwrap_single_element(iterator&); 247 248 /// Replace the node with the children of the node, useful for e.g. 249 /// \\prod{A} -> A. This algorithm takes care of the multiplier of the 250 /// top node, i.e. it does 2\\prod{A} -> 2 A. Returns an iterator 251 /// to the new location of the first child of the original node. 252 iterator flatten_and_erase(iterator position); 253 254 /// Compare two Ex objects for exact equality; no dummy equivalence or other 255 /// things that require property information. 256 257 bool operator==(const Ex& other) const; 258 259 /// Push a copy of the current state of the expression onto the 260 /// history stack. Also pushes a set of paths to terms which 261 /// will be kept in the next history step. 262 /// DEPRECATED, only used by take_match/replace_match. 263 void push_history(const std::vector<Ex::path_t>&); 264 265 /// Pop the most recent state of the expression off the history stack; returns 266 /// the set of paths that we are replacing. 267 /// DEPRECATED, only used by take_match/replace_match. 268 std::vector<Ex::path_t> pop_history(); 269 270 /// Return the size of the history; 0 means no history, just the current 271 /// expression. 272 int history_size() const; 273 274 private: 275 result_t state_; 276 277 std::vector<tree<str_node> > history; 278 /// Patterns which describe how to get from one history step to the next. 279 std::vector<std::vector<Ex::path_t> > terms; 280 }; 281 282 283 /// \ingroup core 284 /// 285 /// Compare two nset iterators by comparing the strings to which they point. 286 287 class nset_it_less { 288 public: 289 bool operator()(nset_t::iterator first, nset_t::iterator second) const; 290 }; 291 292 template <typename T> is_in(const T & val,const std::initializer_list<T> & list)293 bool is_in(const T& val, const std::initializer_list<T>& list) 294 { 295 for (const auto& i : list) { 296 if (val == i) { 297 return true; 298 } 299 } 300 return false; 301 } 302 303 } 304 305 /// \ingroup core 306 /// 307 /// Bare output operator for Ex objects, mainly to provide a simple 308 /// way to generate debugging output. Does not do any fancy 309 /// formatting; just prints a nested list representation. For more 310 /// fancy output, look at DisplayTeX, DisplaySympy and 311 /// DisplayTerminal. 312 313 std::ostream& operator<<(std::ostream&, const cadabra::Ex&); 314 std::ostream& operator<<(std::ostream&, cadabra::Ex::iterator); 315