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