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 "Stopwatch.hh" 24 #include "Storage.hh" 25 #include "Compare.hh" 26 #include "Props.hh" 27 #include "Exceptions.hh" 28 #include "Kernel.hh" 29 #include "IndexIterator.hh" 30 #include "ProgressMonitor.hh" 31 #include "IndexClassifier.hh" 32 33 #include <map> 34 #include <fstream> 35 #include <cstddef> 36 37 namespace cadabra { 38 39 /// \ingroup core 40 /// 41 /// Base class for all algorithms, containing generic routines and in 42 /// particular the logic for index classification. Also contains static 43 /// algorithms acting on Ex objects which require property 44 /// information and can therefore not be a member of Ex. 45 /// 46 /// In order to implement a new algorithm, subclass Algorithm and 47 /// implement the abstract members Algorithm::can_apply and 48 /// Algorithm::apply (see there for further documentation). The 49 /// general logic is that the implementation of 50 /// Algorithm::apply(iterator&) is not allowed to make the node pointed 51 /// at by the iterator invalid. If the algorithm makes the node vanish, 52 /// it should indicate so by setting its multiplier to zero; the 53 /// calling logic will then take care of cleaning up the subtree 54 /// at the node. 55 /// 56 /// The algorithm is, however, allowed to change the node itself or 57 /// replace it with another one, as long as it updates the iterator. 58 59 class Algorithm : public IndexClassifier { 60 public: 61 /// Initialise the algorithm with a reference to the expression 62 /// tree, but do not yet do anything with this tree. Algorithms 63 /// are not typically allowed to mess with the settings in the 64 /// Kernel, so it is passed const. 65 66 Algorithm(const Kernel&, Ex&); 67 68 virtual ~Algorithm(); 69 70 typedef Ex::iterator iterator; 71 typedef Ex::post_order_iterator post_order_iterator; 72 typedef Ex::sibling_iterator sibling_iterator; 73 typedef Ex::result_t result_t; 74 75 bool interrupted; 76 77 /// Provide the algorithm with a ProgressMonitor object on which to register 78 /// (nested) progress information, to be reported out-of-band to a client. 79 80 void set_progress_monitor(ProgressMonitor *); 81 82 /// The main entry points for running algorithms, which traverse 83 /// the tree post-order ('child before parent'). The 'deep' flag 84 /// indicates whether sub-expressions should be acted on 85 /// too. The 'repeat' flag indicates whether the algorithm 86 /// should be applied until the expression no longer 87 /// changes. The 'depth' flag, if not equal to -1, indicates the 88 /// depth in the tree where the algorithm should start applying. 89 90 result_t apply_generic(bool deep=true, bool repeat=false, unsigned int depth=0); 91 result_t apply_generic(iterator&, bool deep, bool repeat, unsigned int depth); 92 93 /// Apply algorithm with alternative traversal: starting from 94 /// the top node, traverse the tree pre-order ('parent before 95 /// child') and once the algorithm acts at a given node, do not 96 /// traverse the subtree below anymore. 97 98 result_t apply_pre_order(bool repeat=false); 99 100 // Global information 101 unsigned int number_of_calls; 102 unsigned int number_of_modifications; 103 bool suppress_normal_output; 104 bool discard_command_node; 105 106 /// Given an expression top node, check index consistency. 107 bool check_consistency(iterator) const; 108 bool check_index_consistency(iterator) const; 109 /// Given an expression top node, check differential form degree consistency. 110 bool check_degree_consistency(iterator) const; 111 112 void report_progress(const std::string&, int todo, int done, int count=2); 113 114 mutable Stopwatch index_sw; 115 mutable Stopwatch get_dummy_sw; 116 mutable Stopwatch report_progress_stopwatch; 117 118 index_iterator begin_index(iterator it) const; 119 index_iterator end_index(iterator it) const; 120 121 // The number of indices of a node, taking into account IndexInherit-ance. These 122 // indices do therefore not all have to be direct child nodes of 'it', they can 123 // sit deeper down the tree. 124 unsigned int number_of_indices(iterator it); 125 static unsigned int number_of_indices(const Properties&, iterator it); 126 127 // The number of indices of a node, counting only the direct ones (i.e. not those 128 // inherited from child nodes). 129 static unsigned int number_of_direct_indices(iterator it); 130 131 // The set to which the first index belongs.. 132 std::string get_index_set_name(iterator it) const; 133 134 /// Rename the dummies in the sub-tree starting with head at the given iterator. 135 /// Ensures that no dummies in this sub-tree overlap with the indices elsewhere 136 /// in the tree. 137 bool rename_replacement_dummies(iterator, bool still_inside_algo=false); 138 139 /// Determines whether the indicated node is 'like a term in a 140 /// sum'. This requires that the node is not a `\sum` node, not 141 /// a child of a `\prod` node, and that its parent rel is of 142 /// argument-type (p_none). 143 static bool is_termlike(iterator); 144 145 /// Determines whether the indicated node is 'like a factor in a product'. 146 /// This requires that the parent is a `\prod' node. 147 static bool is_factorlike(iterator); 148 149 150 protected: 151 Ex& tr; 152 ProgressMonitor *pm; 153 154 // The main entry point which is used by the public entry points listed 155 // above. Override these in any subclass. 156 // 157 virtual bool can_apply(iterator)=0; 158 virtual result_t apply(iterator&)=0; 159 160 // Index stuff 161 int index_parity(iterator) const; 162 static bool less_without_numbers(nset_t::iterator, nset_t::iterator); 163 static bool equal_without_numbers(nset_t::iterator, nset_t::iterator); 164 165 /// Finding objects in sets. 166 typedef std::pair<sibling_iterator, sibling_iterator> range_t; 167 typedef std::vector<range_t> range_vector_t; 168 169 bool contains(sibling_iterator from, sibling_iterator to, sibling_iterator arg); 170 void find_argument_lists(range_vector_t&, bool only_comma_lists=true) const; 171 template<class Iter> 172 range_vector_t::iterator find_arg_superset(range_vector_t&, Iter st, Iter nd); 173 range_vector_t::iterator find_arg_superset(range_vector_t&, sibling_iterator it); 174 175 // Locate objects inside the tree (formerly in the 'locate' algorithm). 176 unsigned int locate_single_object(Ex::iterator obj_to_find, 177 Ex::iterator st, Ex::iterator nd, 178 std::vector<unsigned int>& store); 179 bool locate_object_set(const Ex& objs, 180 Ex::iterator st, Ex::iterator nd, 181 std::vector<unsigned int>& store); 182 static bool compare_(const str_node&, const str_node&); 183 184 185 /// Take a single non-product node in a sum and wrap it in a 186 /// product node, so it can be handled on the same footing as a proper product. 187 bool is_single_term(iterator); 188 bool is_nonprod_factor_in_prod(iterator); 189 bool prod_wrap_single_term(iterator&); 190 bool prod_unwrap_single_term(iterator&); 191 bool sum_wrap_single_term(iterator&); 192 bool sum_unwrap_single_term(iterator&); 193 194 /// Wrap a term in a product or sum in a node with indicated 195 /// name, irrespective of its parent (it usually makes more 196 /// sense to call the safer prod_wrap_single_term or 197 /// sum_wrap_single_term above). Sets the iterator to the 198 /// new node. 199 void force_node_wrap(iterator&, std::string); 200 201 /// Figure out whether two objects (commonly indices) are separated by a derivative 202 /// operator, as in \f[ \partial_{a}{A_{b}} C^{b} \f]. 203 /// If the last iterator is pointing to a valid node, check whether it is 204 /// independent of the derivative (using the Depends property). 205 bool separated_by_derivative(iterator, iterator, iterator check_dependence) const; 206 207 // Given a node with non-zero multiplier, distribute this 208 // multiplier up the tree when the node is a \sum node, or push it into the 209 // `\prod` node if that is the parent. Do this recursively 210 // in case a child is a sum as well. Note that 'pushup' is actually 'pushdown' 211 // in the case of sums. 212 // This never changes the tree structure, only the distribution of multipliers. 213 214 // FIXME: this is now superseded by code in Cleanup.cc, and the generic way 215 // to make a tree consistent is to call cleanup_dispatch, not pick-and-match from 216 // the various algorithms. 217 void pushup_multiplier(iterator); 218 219 // Return the number of elements in the first range for which an identical element 220 // is present in the second range. 221 template<class BinaryPredicate> 222 unsigned int intersection_number(sibling_iterator, sibling_iterator, 223 sibling_iterator, sibling_iterator, BinaryPredicate) const; 224 225 // Turn a node into a '1' or '0' node. 226 void node_zero(iterator); 227 void node_one(iterator); 228 void node_integer(iterator, int); 229 230 231 232 protected: 233 bool traverse_ldots; 234 235 private: 236 237 // Single or deep-scan apply operations. Do not call directly. 238 result_t apply_once(Ex::iterator& it); 239 result_t apply_deep(Ex::iterator& it); 240 241 /// Given a node with zero multiplier, propagate this zero 242 /// upwards in the tree. Changes the iterator so that it points 243 /// to the next node in a post_order traversal (post_order: 244 /// children first, then node). The second node is the topmost 245 /// node, beyond which this routine is not allowed to touch the 246 /// tree (i.e. the 2nd iterator will always remain valid). 247 void propagate_zeroes(post_order_iterator&, const iterator&); 248 249 // bool cleanup_anomalous_products(Ex& tr, Ex::iterator& it); 250 }; 251 252 253 /// Determine the number of elements in the first range which also occur in the 254 /// second range. 255 template<class BinaryPredicate> intersection_number(sibling_iterator from1,sibling_iterator to1,sibling_iterator from2,sibling_iterator to2,BinaryPredicate fun) const256 unsigned int Algorithm::intersection_number(sibling_iterator from1, sibling_iterator to1, 257 sibling_iterator from2, sibling_iterator to2, 258 BinaryPredicate fun) const 259 { 260 unsigned int ret=0; 261 sibling_iterator it1=from1; 262 while(it1!=to1) { 263 sibling_iterator it2=from2; 264 while(it2!=to2) { 265 if(fun(*it1,*it2)) 266 ++ret; 267 ++it2; 268 } 269 ++it1; 270 } 271 return ret; 272 } 273 274 275 } 276