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