1 2 #pragma once 3 4 #include "Storage.hh" 5 #include "Props.hh" 6 #include "properties/Indices.hh" 7 8 namespace cadabra { 9 10 /// \ingroup compare 11 /// 12 /// Basic building block subtree comparison function for tensors 13 /// without dummy indices, which determines whether two tensor 14 /// subtrees are equal up to the names of indices. This uses NO 15 /// property information whatsoever; when indices are compared, 16 /// they are simply compared based on their name, not on the 17 /// index set they may belong to. In most cases, this is NOT what 18 /// you want. 19 /// 20 /// In MOST cases, the use of Ex_comparator below is recommended 21 /// instead, as it can do much more complicated matching and will 22 /// also keep track of the relation between symbols in the pattern 23 /// and symbols in the object to be matched. 24 /// 25 /// Examples: 26 /// 27 /// A_m equals A_n up to index names 28 /// \diff{A*B_g*\diff{C}_k}_m equals \diff{A*B_h*\diff{C}_r}_s up to index names 29 /// 30 /// return | meaning 31 /// -------|----------------------------------------------- 32 /// 0 | structure equal, and all indices the same name 33 /// 1 | structure equal, index names of one < two 34 /// -1 | structure equal, index names of one > two 35 /// 2 | structure different, one < two 36 /// -2 | structure different, one > two 37 /// 38 /// @param one object 39 /// @param two pattern 40 /// @param mod_prel see below 41 /// @param checksets ignored FIXME: remove 42 /// @param compare_multiplier whether to match the multiplier field too. 43 /// @param literal_wildcards whether to treat wildcard names as ordinary names. 44 /// 45 /// The mod_prel variable determines whether parent relations are taken into 46 /// account when comparing: 47 /// FIXME: now that subtree_compare does not use properties anymore, a lot can be simplified. 48 /// 49 /// -3: require that parent relations match, unless indexpos=free. 50 /// -2: require that parent relations match (even when indexpos = free) 51 /// -1: do not require that parent relations match 52 /// >=0: do not require parent relations to match up to and including this level 53 /// 54 /// Similar logic holds for the compare_multiplier parameter. 55 56 int subtree_compare(const Properties*, 57 Ex::iterator one, Ex::iterator two, 58 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2, 59 bool literal_wildcards=false); 60 61 /// Various comparison functions, some exact, some with pattern logic. 62 63 bool tree_less(const Properties*, 64 const Ex& one, const Ex& two, 65 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2); 66 bool tree_equal(const Properties*, 67 const Ex& one, const Ex& two, 68 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2); 69 bool tree_exact_less(const Properties*, 70 const Ex& one, const Ex& two, 71 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2, 72 bool literal_wildcards=false); 73 bool tree_exact_equal(const Properties*, 74 const Ex& one, const Ex& two, 75 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2, 76 bool literal_wildcards=false); 77 78 bool subtree_less(const Properties*, 79 Ex::iterator one, Ex::iterator two, 80 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2); 81 bool subtree_equal(const Properties*, 82 Ex::iterator one, Ex::iterator two, 83 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2); 84 bool subtree_exact_less(const Properties*, 85 Ex::iterator one, Ex::iterator two, 86 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2, 87 bool literal_wildcards=false); 88 bool subtree_exact_equal(const Properties*, 89 Ex::iterator one, Ex::iterator two, 90 int mod_prel=-2, bool checksets=true, int compare_multiplier=-2, 91 bool literal_wildcards=false); 92 93 /// Compare two trees by pattern logic, i.e. modulo index names. 94 // 95 class tree_less_obj { 96 public: 97 tree_less_obj(const Properties*); 98 bool operator()(const Ex& first, const Ex& second) const; 99 private: 100 const Properties* properties; 101 }; 102 103 class tree_less_modprel_obj { 104 public: 105 tree_less_modprel_obj(const Properties*); 106 bool operator()(const Ex& first, const Ex& second) const; 107 private: 108 const Properties* properties; 109 }; 110 111 class tree_equal_obj { 112 public: 113 tree_equal_obj(const Properties*); 114 bool operator()(const Ex& first, const Ex& second) const; 115 private: 116 const Properties* properties; 117 }; 118 119 /// Compare two trees exactly, i.e. including exact index names. 120 // 121 class tree_exact_less_obj { 122 public: 123 tree_exact_less_obj(const Properties*); 124 bool operator()(const Ex& first, const Ex& second) const; 125 private: 126 const Properties* properties; 127 }; 128 129 class tree_exact_less_mod_prel_obj { 130 public: 131 tree_exact_less_mod_prel_obj(const Properties*); 132 bool operator()(const Ex& first, const Ex& second) const; 133 private: 134 const Properties* properties; 135 }; 136 137 class tree_exact_equal_obj { 138 public: 139 tree_exact_equal_obj(const Properties*); 140 bool operator()(const Ex& first, const Ex& second) const; 141 private: 142 const Properties* properties; 143 }; 144 145 class tree_exact_equal_mod_prel_obj { 146 public: 147 tree_exact_equal_mod_prel_obj(const Properties*); 148 bool operator()(const Ex& first, const Ex& second) const; 149 private: 150 const Properties* properties; 151 }; 152 153 /// Compare for indexmap_t. The only comparator object that does not use 154 /// properties info to lookup properties. This one compares exactly (it cannot 155 /// do any matching which requires knowledge about index sets because it does 156 /// not know about properties). It requires parent relations to match including 157 /// at top level. It requires multipliers to match including at top level. 158 /// Names with '?' or '??' suffixes are matched literally, not as patterns. 159 160 class tree_exact_less_for_indexmap_obj { 161 public: 162 bool operator()(const Ex& first, const Ex& second) const; 163 }; 164 165 /// Compare two trees exactly, treat wildcard names as ordinary names. 166 // 167 class tree_exact_less_no_wildcards_obj { 168 public: 169 tree_exact_less_no_wildcards_obj(); // disables property handling 170 tree_exact_less_no_wildcards_obj(const Properties*); 171 bool operator()(const Ex& first, const Ex& second) const; 172 private: 173 const Properties* properties; 174 }; 175 176 class tree_exact_less_no_wildcards_mod_prel_obj { 177 public: 178 tree_exact_less_no_wildcards_mod_prel_obj(const Properties*); 179 bool operator()(const Ex& first, const Ex& second) const; 180 private: 181 const Properties* properties; 182 }; 183 184 185 /// \ingroup compare 186 /// 187 /// A generic tree comparison class which will take into account index 188 /// contractions and will also keep track of a replacement list for 189 /// all types of cadabra wildcards. The entry point is typically 190 /// 'equal_subtree' or 'match_subproduct'. 191 192 class Ex_comparator { 193 public: 194 Ex_comparator(const Properties&); 195 196 enum class match_t { 197 node_match=0, // a single node matches 198 subtree_match=1, // identical match, including index names 199 match_index_less=2, // structure match, indices in same set, but different names 200 match_index_greater=3, 201 no_match_indexpos_less=4, // mismatch but only for index positions 202 no_match_indexpos_greater=5, 203 no_match_less=6, // more serious mismatch 204 no_match_greater=7 205 }; 206 207 enum class useprops_t { 208 always=0, // always use property info 209 not_at_top, // don't use property info at top level of the expression 210 never=2 // never use property info 211 }; 212 213 /// Reset the object for a new match. 214 215 void clear(); 216 217 /// Determine whether Coordinates in the pattern (first argument 218 /// to functions below) can match against Indices in the object 219 /// (second argument). That is to say, whether the pattern 220 /// `\partial_{t}{A}` matches against the expression 221 /// `\partial_{\mu}{A}` when `\mu` can take the value `t`. This is 222 /// used in 'evaluate', but should generically be turned off for 223 /// 'substitute'. 224 225 void set_value_matches_index(bool); 226 227 /// Match two subtrees taking into account symbol 228 /// properties. 'i1' can be a pattern. 229 /// Returns subtree_match or one of the no_match 230 /// results. You need to fill lhs_contains_dummies before 231 /// calling! 232 /// If use_props is false, it will not try to fetch any property 233 /// information at the TOP level of the comparison. Properties 234 /// will always be used at levels. 235 236 match_t equal_subtree(Ex::iterator i1, Ex::iterator i2, 237 useprops_t use_props=useprops_t::always, bool ignore_parent_rel=false); 238 239 /// Match two subtrees, new-style equal_subtree that handles conditions; this is 240 /// what substitute uses. 241 242 match_t match_subtree(const Ex&, Ex::iterator i1, Ex::iterator i2, Ex::iterator conditions); 243 244 /// Find a sub-product in a product. The 'lhs' iterator points to the product which 245 /// we want to find, the 'tofind' iterator to the current factor which we are looking 246 /// for. The product in which to search is pointed to by 'st'. 247 /// Once 'tofind' is found, this routine calls itself to find the next factor in 248 /// 'lhs'. If the next factor cannot be found, we backtrack and try to find the 249 /// previous factor again (it may have appeared multiple times). 250 251 match_t match_subproduct(const Ex&, 252 Ex::sibling_iterator lhs, Ex::sibling_iterator tofind, 253 Ex::sibling_iterator st, Ex::iterator conditions); 254 255 /// Find a sub-sum in a sum. The 'lhs' iterator points to the sum which 256 /// we want to find, the 'tofind' iterator to the current term which we are looking 257 /// for. The sum in which to search is pointed to by 'st'. 258 /// Once 'tofind' is found, this routine calls itself to find the next term in 259 /// 'lhs'. Since Cadabra assumes all terms in a sum commute, we do not 260 /// need the backtracking logic of subproduct. 261 262 match_t match_subsum(const Ex&, 263 Ex::sibling_iterator lhs, Ex::sibling_iterator tofind, 264 Ex::sibling_iterator st, Ex::iterator conditions); 265 266 /// Check whether the a match found by calling equal_subtree or match_subproduct 267 /// satisfies the conditions as stated. 268 /// FIXME: document possible conditions. 269 270 bool satisfies_conditions(Ex::iterator conditions, std::string& error); 271 272 /// Map for the replacement of nodes (indices, patterns). 273 274 typedef std::map<Ex, Ex, tree_exact_less_no_wildcards_obj> replacement_map_t; 275 replacement_map_t replacement_map; 276 277 /// Map for the replacement of entire subtrees (object patterns). 278 279 typedef std::map<nset_t::iterator, Ex::iterator, nset_it_less> subtree_replacement_map_t; 280 subtree_replacement_map_t subtree_replacement_map; 281 282 /// Map for matching of index names to index values. Note: this is in the opposite order 283 /// from replacement_map! 284 285 replacement_map_t index_value_map; 286 287 /// Information to keep track of where individual factors/terms 288 /// in a sub-product/sub-sum were found, and (for sub-products) 289 /// whether moving them into the searched-for order leads to 290 /// sign flips. 291 292 std::vector<Ex::sibling_iterator> factor_locations; 293 std::vector<int> factor_moving_signs; 294 multiplier_t term_ratio; 295 296 /// Flag to indicate whether additional care must be taken to handle dummies in the 297 /// lhs of the pattern. 298 /// FIXME: would be better if this were automatic. 299 bool lhs_contains_dummies; 300 301 /// Determine whether two objects should be swapped according to 302 /// the available SortOrder properties. 303 304 bool should_swap(Ex::iterator obj, match_t subtree_comparison) ; 305 306 /// Determine whether obj and obj+1 be exchanged? If yes, return 307 /// the sign, if no return zero. This is the general entry point 308 /// for two arbitrary nodes (which may be a product or sum). 309 /// 310 /// The last flag ('ignore_implicit_indices') is used to disable 311 /// all checks dealing with implicit indices (this is useful for 312 /// algorithms which re-order objects with implicit indices, 313 /// which would otherwise always receive a 0 from this 314 /// function). 315 316 int can_swap(Ex::iterator one, Ex::iterator two, match_t subtree_comparison, 317 bool ignore_implicit_indices=false); 318 319 /// Wrapper for can_swap which is meant for objects that have implicit 320 /// indices. This checks whether a single component of A commutes or 321 /// anticommutes with a single component of B, saying nothing about 322 /// whether A and B commute under matrix multiplication. 323 324 int can_swap_components(Ex::iterator one, Ex::iterator two, 325 match_t subtree_comparison); 326 327 /// Determine whether object 'one' and 'two' can be moved next 328 /// to each other by moving either one or the other: if fix_one==true 329 /// the first node is kept fixed, otherwise the second node is kept fixed. 330 331 int can_move_adjacent(Ex::iterator prod, Ex::sibling_iterator one, 332 Ex::sibling_iterator two, bool fix_one=false) ; 333 334 335 /// Determine whether object 'one' can be moved to be the first 336 /// factor in the given product. 337 int can_move_to_front(Ex&, Ex::iterator prod, Ex::sibling_iterator one); 338 339 /// Alternative to the above, which handles more complicated versions where we 340 /// need to keep track of previously moved factors (used by algorithms/substitute.cc). 341 342 int can_move_adjacent(Ex::iterator prod, const std::vector<Ex::sibling_iterator>& factors, Ex::sibling_iterator to_move); 343 344 protected: 345 const Properties& properties; 346 347 bool value_matches_index; 348 349 /// Internal entry point. This comparison function tries to match 350 /// a single node in the tree, except when the node is an 351 /// index. Indices are considered to be leaf-nodes, and for these 352 /// a full subtree match will be attempted (using subtree_compare). 353 354 match_t compare(const Ex::iterator&, const Ex::iterator&, 355 bool nobrackets=false, 356 useprops_t use_props=useprops_t::always, 357 bool ignore_parent_rel=false); 358 359 // Internal functions used by can_swap. 360 int can_swap_prod_obj(Ex::iterator prod, Ex::iterator obj, bool) ; 361 int can_swap_prod_prod(Ex::iterator prod1, Ex::iterator prod2, bool) ; 362 int can_swap_sum_obj(Ex::iterator sum, Ex::iterator obj, bool) ; 363 int can_swap_prod_sum(Ex::iterator prod, Ex::iterator sum, bool) ; 364 int can_swap_sum_sum(Ex::iterator sum1, Ex::iterator sum2, bool) ; 365 int can_swap_ilist_ilist(Ex::iterator obj1, Ex::iterator obj2); 366 bool can_swap_different_indexsets(Ex::iterator obj1, Ex::iterator obj2); 367 368 std::string tab() const; 369 match_t report(match_t r) const; 370 371 /// Match the `name` elements of a node, but take into account that 372 /// one of them can be an autodeclare name `XXX#`. 373 bool name_match_with_autodeclare(Ex::sibling_iterator one, Ex::sibling_iterator two) const; 374 375 static int offset; 376 }; 377 378 /// \ingroup core 379 /// 380 /// Basic comparison operator for tree iterators, so we can use them as keys in maps. 381 382 class Ex_is_equivalent { 383 public: 384 Ex_is_equivalent(const Properties&); 385 bool operator()(const Ex&, const Ex&); 386 private: 387 const Properties& properties; 388 }; 389 390 class Ex_is_less { 391 public: 392 Ex_is_less(const Properties&, int mod_prel); 393 bool operator()(const Ex&, const Ex&); 394 private: 395 const Properties& properties; 396 int mod_prel; 397 }; 398 399 400 401 } 402 403 bool operator<(const cadabra::Ex::iterator&, const cadabra::Ex::iterator&); 404 bool operator<(const cadabra::Ex&, const cadabra::Ex&); 405 std::ostream& operator<<(std::ostream&, cadabra::Ex_comparator::useprops_t up); 406