Cadabra
Computer algebra system for field theory problems
Loading...
Searching...
No Matches
Props.hh
Go to the documentation of this file.
1/*
2
3Cadabra: a field-theory motivated computer algebra system.
4Copyright (C) 2001-2014 Kasper Peeters <kasper.peeters@phi-sci.com>
5
6This program is free software: you can redistribute it and/or
7modify it under the terms of the GNU General Public License as
8 published by the Free Software Foundation, either version 3 of the
9License, or (at your option) any later version.
10
11This program is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
31namespace 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);
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
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
526done:
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:141
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
virtual bool parse(Kernel &, keyval_t &keyvals)
Definition: Props.cc:243
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