Cadabra
Computer algebra system for field theory problems
Props.hh
Go to the documentation of this file.
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 // Classes handling storage of property information. Actual property
22 // implementations are in the properties directory in separate files.
23 
24 #pragma once
25 
26 #include <map>
27 #include <list>
28 #include <type_traits>
29 #include "Storage.hh"
30 
31 namespace cadabra {
32 
33  class Properties;
34  class Kernel;
35  class Accent;
36  class LaTeXForm;
37  class Ex_comparator;
38 
39  class pattern {
40  public:
41  pattern();
42  pattern(const Ex&);
43 
54 
55  bool match(const Properties&, const Ex::iterator&, bool ignore_parent_rel=false, bool ignore_properties=false) const;
56  bool children_wildcard() const;
57 
61  bool match_ext(const Properties&, const Ex::iterator&, Ex_comparator& comp, bool ignore_parent_rel=false, bool ignore_properties=false) const;
62 
64  };
65 
67 
68  class keyval_t {
69  public:
70  typedef std::pair<std::string, Ex::iterator> kvpair_t;
71  typedef std::list<kvpair_t> kvlist_t;
72 
73  typedef kvlist_t::const_iterator const_iterator;
74  typedef kvlist_t::iterator iterator;
76 
77  const_iterator find(const std::string&) const;
78  iterator find(const std::string&);
79  const_iterator begin() const;
80  const_iterator end() const;
81  void push_back(const kvpair_t&);
82  void erase(iterator);
83 
84  private:
86  };
87 
103  // default implementation returns true for any pattern.
125 
126 
127  class property {
128  public:
129  property(bool hidden=false);
130  virtual ~property() {};
131 
132  // Parse the argument tree into key-value pairs. Returns false on error.
133  bool parse_to_keyvals(const Ex&, keyval_t&);
134 
135  // Use the pre-parsed arguments in key/value form to set parameters.
136  // Parses universal arguments by default. Will be called once for
137  // every property; assigning a non-list property to multiple patterns
138  // still calls this only once.
139  // FIXME: failure to call
140  // into superclass may lead to problems for labelled properties.
141  virtual bool parse(Kernel&, keyval_t& keyvals);
142 
143  // New entry point, which also passes the Ex of the pattern, so that
144  // the property itself can inject other properties automatically (e.g.
145  // declare an InverseMetric if a Metric is declared).
146  virtual bool parse(Kernel&, std::shared_ptr<Ex>, keyval_t& keyvals);
147 
148  // Check whether the property can be associated with the pattern.
149  // Throw an error if validation fails. Needs access to all other
150  // declared properties so that it can understand what the pattern
151  // means (which objects are indices etc.).
152  virtual void validate(const Kernel&, const Ex&) const;
153 
155  // virtual void display(std::ostream&) const;
156 
159  virtual void latex(std::ostream&) const;
160 
161  virtual std::string name() const=0;
162  virtual std::string unnamed_argument() const;
163 
164  // To compare properties we sometimes need to compare their variables, not only
165  // their type. The following function needs to be overridden in all properties
166  // for which comparison by type is not sufficient to establish equality.
167  //
168  // id_match: only one of these properties can be registered, but their data is not the same
169  // exact_match: these properties are exactly identical
171  virtual match_t equals(const property *) const;
172 
176  void hidden(bool h);
177  bool hidden(void) const;
178 
179  private:
180  bool parse_one_argument(Ex::iterator arg, keyval_t& keyvals);
181  bool hidden_;
182  };
183 
184  class labelled_property : virtual public property {
185  public:
186  virtual bool parse(Kernel&, std::shared_ptr<Ex>, keyval_t&) override;
187  std::string label;
188  };
189 
192 
193  class list_property : public property {
194  public:
195  };
196 
202 
203  template<class T>
204  class Inherit : virtual public property {
205  public:
206  virtual ~Inherit() {};
207  virtual std::string name() const
208  {
209  return std::string("Stay Away");
210  };
211  };
212 
215 
216  class PropertyInherit : virtual public property {
217  public:
218  virtual std::string name() const
219  {
220  return std::string("PropertyInherit");
221  };
222  };
223 
233 
234  class Properties {
235  public:
236  // Registering property types.
238  public:
240 
241  typedef std::map<std::string, property* (*)()> internal_property_map_t;
242  typedef internal_property_map_t::iterator iterator;
243 
245  };
246 
250 
251  void register_property(property* (*)(), const std::string& name);
253  typedef std::pair<pattern *, const property *> pat_prop_pair_t;
254 
262  typedef std::multimap<nset_t::iterator, pat_prop_pair_t, nset_it_less> property_map_t;
263  typedef std::multimap<const property *, pattern *> pattern_map_t;
264 
268  std::string master_insert(Ex proptree, const property *thepropbase);
269 
270  void clear();
271 
276  property_map_t props; // pattern -> property
277  pattern_map_t pats; // property -> pattern; for list properties, patterns are stored here in order
278 
280  template<class T> const T* get(Ex::iterator, bool ignore_parent_rel=false) const;
281  template<class T> const T* get(Ex::iterator, int& serialnum, bool doserial=true, bool ignore_parent_rel=false) const;
283  template<class T> const T* get(Ex::iterator, const std::string& label) const;
284  template<class T> const T* get(Ex::iterator, int& serialnum, const std::string& label, bool doserial=true) const;
286  template<class T> const T* get(Ex::iterator, Ex::iterator, bool ignore_parent_rel=false) const;
287  template<class T> const T* get(Ex::iterator, Ex::iterator, int&, int&, bool ignore_parent_rel=false) const;
288 
292  template<class T>
293  std::pair<const T*, const pattern *> get_with_pattern(Ex::iterator, int& serialnum,
294  const std::string& label,
295  bool doserial=true, bool ignore_parent_rel=false) const;
296 
297  template<class T>
298  std::pair<const T*, const pattern *> get_with_pattern_ext(Ex::iterator, Ex_comparator&, int& serialnum,
299  const std::string& label,
300  bool doserial=true, bool ignore_parent_rel=false) const;
301 
302  // Get the outermost node which has the given property attached, i.e. go down through
303  // all (if any) nodes which have just inherited the property.
304  template<class T> Ex::iterator head(Ex::iterator, bool ignore_parent_rel=false) const;
305 
306  // Inverse search: given a property type, get a pattern which has this property.
307  // When given an iterator, it starts to search in the property
308  // map from this particular point. Note: this searches on property type, not exact property.
309  // template<class T>
310  // property_map_t::iterator get_pattern(property_map_t::iterator=props.begin());
311 
312  // Equivalent search: given a node, get a pattern of equivalents.
313  // property_map_t::iterator get_equivalent(Ex::iterator,
314  // property_map_t::iterator=props.begin());
315 
316  private:
317  // Insert a property. Do not use this directly, use the public
318  // interface `master_insert` instead.
319  void insert_prop(const Ex&, const property *);
320  void insert_list_prop(const std::vector<Ex>&, const list_property *);
321  bool check_label(const property *, const std::string&) const;
322  bool check_label(const labelled_property *, const std::string&) const;
323  // Search through pointers
324  bool has(const property *, Ex::iterator);
325  // Find serial number of a pattern in a given list property
326  int serial_number(const property *, const pattern *) const;
328  void destroy_comparator(Ex_comparator *) const;
329  };
330 
331  template<class T>
332  const T* Properties::get(Ex::iterator it, bool ignore_parent_rel) const
333  {
334  int tmp;
335  return get<T>(it, tmp, false, ignore_parent_rel);
336  }
337 
338  template<class T>
339  const T* Properties::get(Ex::iterator it, int& serialnum, bool doserial, bool ignore_parent_rel) const
340  {
341  auto ret = get_with_pattern<T>(it, serialnum, "", doserial, ignore_parent_rel);
342  return ret.first;
343  }
344 
345  template<class T>
346  std::pair<const T*, const pattern *> Properties::get_with_pattern(Ex::iterator it, int& serialnum, const std::string& label,
347  bool doserial, bool ignore_parent_rel) const
348  {
349  Ex_comparator *compptr = create_comparator();
350  // FIXME: catch and rethrow all exceptions so we do not leak memory
351  auto ret = get_with_pattern_ext<T>(it, *compptr, serialnum, label, doserial, ignore_parent_rel);
352  destroy_comparator(compptr);
353  return ret;
354  }
355 
356  template<class T>
357  std::pair<const T*, const pattern *> Properties::get_with_pattern_ext(Ex::iterator it, Ex_comparator& comp,
358  int& serialnum, const std::string& label,
359  bool doserial, bool ignore_parent_rel) const
360  {
361  std::pair<const T*, const pattern *> ret;
362  ret.first=0;
363  ret.second=0;
364  bool inherits=false;
365 
366  //std::cerr << *it->name_only() << std::endl;
367  // std::cerr << props.size() << std::endl;
368  std::pair<property_map_t::const_iterator, property_map_t::const_iterator> pit=props.equal_range(it->name_only());
369 
370  // First look for properties of the node itself. Go through the loop twice:
371  // once looking for patterns which do not have wildcards, and then looking
372  // for wildcard patterns.
373  bool wildcards=false;
374 
375  // For some properties, we cannot lookup properties lower down the
376  // tree, because it would lead to an endless recursion (and it would
377  // not make sense anyway). At the moment, this is only for Accent.
378  bool ignore_properties=false;
379  if(std::is_same<T, Accent>::value)
380  ignore_properties=true;
381 
382  for(;;) {
383  property_map_t::const_iterator walk=pit.first;
384  while(walk!=pit.second) {
385  if(wildcards==(*walk).second.first->children_wildcard()) {
386  // First check property type; a dynamic cast is much faster than a pattern match.
387  ret.first=dynamic_cast<const T *>((*walk).second.second);
388  if(ret.first) {
389  if((*walk).second.first->match_ext(*this, it, comp, ignore_parent_rel, ignore_properties)) {
390  ret.second=(*walk).second.first;
391  if(!check_label(ret.first, label))
392  ret.first=0;
393  else {
394  if(doserial)
395  serialnum=serial_number( (*walk).second.second, (*walk).second.first );
396  break;
397  }
398  }
399  }
400  ret.first=0;
401  if(dynamic_cast<const PropertyInherit *>((*walk).second.second))
402  inherits=true;
403  else if(dynamic_cast<const Inherit<T> *>((*walk).second.second))
404  inherits=true;
405  }
406  ++walk;
407  }
408  if(!wildcards && !ret.first) {
409  // std::cerr << "not yet found, switching to wildcards" << std::endl;
410  wildcards=true;
411  }
412  else break;
413  }
414 
415  // Do not walk down the tree if the property cannot be passed up the tree.
416  // FIXME: see issue/259.
417  if(std::is_same<T, LaTeXForm>::value)
418  inherits=false;
419 
420  // If no property was found, figure out whether a property is inherited from a child node.
421  if(!ret.first && inherits) {
422  // std::cout << "no match but perhaps inheritance?" << std::endl;
423  Ex::sibling_iterator sib=it.begin();
424  while(sib!=it.end()) {
425  std::pair<const T*, const pattern *> tmp=get_with_pattern<T>((Ex::iterator)(sib), serialnum, label, doserial);
426  if(tmp.first) {
427  ret=tmp;
428  break;
429  }
430  ++sib;
431  }
432  }
433 
434  // std::cout << ret << std::endl;
435  return ret;
436  }
437 
438  template<class T>
439  const T* Properties::get(Ex::iterator it, const std::string& label) const
440  {
441  int tmp;
442  return get<T>(it, tmp, label, false);
443  }
444 
445  template<class T>
446  const T* Properties::get(Ex::iterator it, int& serialnum, const std::string& label, bool doserial) const
447  {
448  auto ret=get_with_pattern<T>(it, serialnum, label, doserial, false);
449  return ret.first;
450  }
451 
452  template<class T>
453  const T* Properties::get(Ex::iterator it1, Ex::iterator it2, bool ignore_parent_rel) const
454  {
455  int tmp1, tmp2;
456  return get<T>(it1,it2,tmp1,tmp2, ignore_parent_rel);
457  }
458 
459  template<class T>
460  const T* Properties::get(Ex::iterator it1, Ex::iterator it2, int& serialnum1, int& serialnum2, bool ignore_parent_rel) const
461  {
462  const T* ret1=0;
463  const T* ret2=0;
464  bool found=false;
465 
466  bool inherits1=false, inherits2=false;
467  std::pair<property_map_t::const_iterator, property_map_t::const_iterator> pit1=props.equal_range(it1->name_only());
468  std::pair<property_map_t::const_iterator, property_map_t::const_iterator> pit2=props.equal_range(it2->name_only());
469 
470  property_map_t::const_iterator walk1=pit1.first;
471  while(walk1!=pit1.second) {
472  if((*walk1).second.first->match(*this, it1, ignore_parent_rel)) { // match for object 1 found
473  ret1=dynamic_cast<const T *>((*walk1).second.second);
474  if(ret1) { // property of the right type found for object 1
475  property_map_t::const_iterator walk2=pit2.first;
476  while(walk2!=pit2.second) {
477  if((*walk2).second.first->match(*this, it2, ignore_parent_rel)) { // match for object 2 found
478  ret2=dynamic_cast<const T *>((*walk2).second.second);
479  if(ret2) { // property of the right type found for object 2
480  if(ret1==ret2 && walk1!=walk2) { // accept if properties are the same and patterns are not
481  serialnum1=serial_number( (*walk1).second.second, (*walk1).second.first );
482  serialnum2=serial_number( (*walk2).second.second, (*walk2).second.first );
483  found=true;
484  goto done;
485  }
486  }
487  }
488  if(dynamic_cast<const PropertyInherit *>((*walk2).second.second))
489  inherits2=true;
490  ++walk2;
491  }
492  }
493  if(dynamic_cast<const PropertyInherit *>((*walk1).second.second))
494  inherits1=true;
495  }
496  ++walk1;
497  }
498 
499  // If no property was found, figure out whether a property is inherited from a child node.
500  if(!found && (inherits1 || inherits2)) {
501  Ex::sibling_iterator sib1, sib2;
502  if(inherits1) sib1=it1.begin();
503  else sib1=it1;
504  bool keepgoing1=true;
505  do { // 1
506  bool keepgoing2=true;
507  if(inherits2) sib2=it2.begin();
508  else sib2=it2;
509  do { // 2
510  const T* tmp=get<T>((Ex::iterator)(sib1), (Ex::iterator)(sib2), serialnum1, serialnum2, ignore_parent_rel);
511  if(tmp) {
512  ret1=tmp;
513  found=true;
514  goto done;
515  }
516  if(!inherits2 || ++sib2==it2.end())
517  keepgoing2=false;
518  }
519  while(keepgoing2);
520  if(!inherits1 || ++sib1==it1.end())
521  keepgoing1=false;
522  }
523  while(keepgoing1);
524  }
525 
526 done:
527  if(!found) ret1=0;
528  return ret1;
529  }
530 
531  template<class T>
532  Ex::iterator Properties::head(Ex::iterator it, bool ignore_parent_rel) const
533  {
534  Ex::iterator dn=it;
535  for(;;) {
536  if(get<PropertyInherit>(dn, ignore_parent_rel)) {
537  dn=dn.begin();
538  }
539  else {
540  assert(get<T>(dn));
541  break;
542  }
543  }
544  return dn;
545  }
546 
547  }
A generic tree comparison class which will take into account index contractions and will also keep tr...
Definition: Compare.hh:192
Basic storage class for symbolic mathemematical expressions.
Definition: Storage.hh:142
If a property X derives from Inherit<Y>, and get<Y> is called on an object which has an X property (b...
Definition: Props.hh:204
virtual ~Inherit()
Definition: Props.hh:206
virtual std::string name() const
Definition: Props.hh:207
Definition: Kernel.hh:15
internal_property_map_t store
Definition: Props.hh:244
std::map< std::string, property *(*)()> internal_property_map_t
Definition: Props.hh:241
internal_property_map_t::iterator iterator
Definition: Props.hh:242
~registered_property_map_t()
Definition: Props.cc:175
Class holding a collection of properties attached to expressions.
Definition: Props.hh:234
void insert_list_prop(const std::vector< Ex > &, const list_property *)
Definition: Props.cc:435
Ex::iterator head(Ex::iterator, bool ignore_parent_rel=false) const
Definition: Props.hh:532
std::pair< pattern *, const property * > pat_prop_pair_t
Definition: Props.hh:253
std::string master_insert(Ex proptree, const property *thepropbase)
Register a property for the indicated Ex.
Definition: Props.cc:580
std::pair< const T *, const pattern * > get_with_pattern_ext(Ex::iterator, Ex_comparator &, int &serialnum, const std::string &label, bool doserial=true, bool ignore_parent_rel=false) const
Definition: Props.hh:357
pattern_map_t pats
Definition: Props.hh:277
registered_property_map_t registered_properties
Definition: Props.hh:252
bool check_label(const property *, const std::string &) const
Definition: Props.cc:643
std::multimap< const property *, pattern * > pattern_map_t
Definition: Props.hh:263
void register_property(property *(*)(), const std::string &name)
Registering properties.
Definition: Props.cc:180
std::multimap< nset_t::iterator, pat_prop_pair_t, nset_it_less > property_map_t
We keep two multi-maps: one from the pattern to the property (roughly) and one from the property to t...
Definition: Props.hh:262
bool has(const property *, Ex::iterator)
Definition: Props.cc:140
Ex_comparator * create_comparator() const
Definition: Props.cc:653
std::pair< const T *, const pattern * > get_with_pattern(Ex::iterator, int &serialnum, const std::string &label, bool doserial=true, bool ignore_parent_rel=false) const
General property finder, which will return not only the property but also the pattern which matched t...
Definition: Props.hh:346
void destroy_comparator(Ex_comparator *) const
Definition: Props.cc:658
const T * get(Ex::iterator, bool ignore_parent_rel=false) const
Normal search: given a pattern, get its property if any.
Definition: Props.hh:332
void insert_prop(const Ex &, const property *)
Definition: Props.cc:349
property_map_t props
The following two maps own the pointers to the properties and patterns stored in them; use clear() to...
Definition: Props.hh:276
int serial_number(const property *, const pattern *) const
Definition: Props.cc:530
void clear()
Definition: Props.cc:156
PropertyInherit is like Inherit<T> for all properties.
Definition: Props.hh:216
virtual std::string name() const
Definition: Props.hh:218
Arguments to properties get parsed into a keyval_t structure.
Definition: Props.hh:68
kvlist_t::const_iterator const_iterator
Definition: Props.hh:73
std::list< kvpair_t > kvlist_t
Definition: Props.hh:71
void push_back(const kvpair_t &)
Definition: Props.cc:217
const_iterator end() const
Definition: Props.cc:212
kvlist_t keyvals
Definition: Props.hh:85
kvlist_t::iterator iterator
Definition: Props.hh:74
const_iterator begin() const
Definition: Props.cc:207
std::pair< std::string, Ex::iterator > kvpair_t
Definition: Props.hh:70
kvpair_t value_type
Definition: Props.hh:75
void erase(iterator)
Definition: Props.cc:222
const_iterator find(const std::string &) const
Definition: Props.cc:185
Definition: Props.hh:184
std::string label
Definition: Props.hh:187
virtual bool parse(Kernel &, std::shared_ptr< Ex >, keyval_t &) override
Definition: Props.cc:320
Something cannot be both a list property and a normal property at the same time, so we can safely inh...
Definition: Props.hh:193
Definition: Props.hh:39
bool match(const Properties &, const Ex::iterator &, bool ignore_parent_rel=false, bool ignore_properties=false) const
Match a pattern to an expression.
Definition: Props.cc:43
bool match_ext(const Properties &, const Ex::iterator &, Ex_comparator &comp, bool ignore_parent_rel=false, bool ignore_properties=false) const
As match, but using a comparator object which is externally provided, so that the caller can use the ...
Definition: Props.cc:49
Ex obj
Definition: Props.hh:63
bool children_wildcard() const
Definition: Props.cc:132
pattern()
Definition: Props.cc:34
Base class for all properties, handling argument parsing and defining the interface.
Definition: Props.hh:127
virtual match_t equals(const property *) const
Definition: Props.cc:315
property(bool hidden=false)
Definition: Props.cc:228
virtual bool parse(Kernel &, keyval_t &keyvals)
Definition: Props.cc:243
virtual void latex(std::ostream &) const
Display the property on the stream.
Definition: Props.cc:305
bool parse_to_keyvals(const Ex &, keyval_t &)
Definition: Props.cc:279
virtual std::string unnamed_argument() const
Definition: Props.cc:310
bool parse_one_argument(Ex::iterator arg, keyval_t &keyvals)
Definition: Props.cc:259
bool hidden(void) const
Definition: Props.cc:238
bool hidden_
Definition: Props.hh:181
virtual ~property()
Definition: Props.hh:130
virtual std::string name() const =0
match_t
Definition: Props.hh:170
@ exact_match
Definition: Props.hh:170
@ no_match
Definition: Props.hh:170
@ id_match
Definition: Props.hh:170
virtual void validate(const Kernel &, const Ex &) const
Definition: Props.cc:255
Functions to handle the exchange properties of two or more symbols in a product.
Definition: Adjform.cc:83