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