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> 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 //
153 // This is currently also the point where properties are allowed
154 // to insert other, related properties (see e.g. `Indices`), and form
155 // that reason the Kernel parameter is not const. FIXME: split and
156 // then make Kernel const again).
157 virtual void validate(Kernel&, std::shared_ptr<Ex>) const;
158
160 // virtual void display(std::ostream&) const;
161
164 virtual void latex(std::ostream&) const;
165
166 virtual std::string name() const=0;
167 virtual std::string unnamed_argument() const;
168
169 // To compare properties we sometimes need to compare their variables, not only
170 // their type. The following function needs to be overridden in all properties
171 // for which comparison by type is not sufficient to establish equality.
172 //
173 // id_match: only one of these properties can be registered, but their data is not the same
174 // exact_match: these properties are exactly identical
176 virtual match_t equals(const property *) const;
177
181 void hidden(bool h);
182 bool hidden(void) const;
183
184 private:
185 bool parse_one_argument(Ex::iterator arg, keyval_t& keyvals);
187 };
188
189 class labelled_property : virtual public property {
190 public:
191 virtual bool parse(Kernel&, std::shared_ptr<Ex>, keyval_t&) override;
192 std::string label;
193 };
194
197
198 class list_property : public property {
199 public:
200 };
201
207
208 template<class T>
209 class Inherit : virtual public property {
210 public:
211 virtual ~Inherit() {};
212 virtual std::string name() const
213 {
214// T tmp;
215 // T can be abstract, so we cannot instantiate. Maybe use typeid,
216 // but then we need to be careful about name mangling.
217 return std::string("Inherit");
218 };
219 };
220
223
224 class PropertyInherit : virtual public property {
225 public:
226 virtual std::string name() const
227 {
228 return std::string("PropertyInherit");
229 };
230 };
231
241
243 public:
244 // Registering property types.
246 public:
248
249 typedef std::map<std::string, property* (*)()> internal_property_map_t;
250 typedef internal_property_map_t::iterator iterator;
251
253 };
254
258
259 void register_property(property* (*)(), const std::string& name);
261 typedef std::pair<pattern *, const property *> pat_prop_pair_t;
262
270 typedef std::multimap<nset_t::iterator, pat_prop_pair_t, nset_it_less> property_map_t;
271 typedef std::multimap<const property *, pattern *> pattern_map_t;
272
276 std::string master_insert(Ex proptree, const property *thepropbase);
277
278 void clear();
279
284 property_map_t props; // pattern -> property
285 pattern_map_t pats; // property -> pattern; for list properties, patterns are stored here in order
286
288 template<class T> const T* get(Ex::iterator, bool ignore_parent_rel=false) const;
289 template<class T> const T* get(Ex::iterator, int& serialnum, bool doserial=true, bool ignore_parent_rel=false) const;
291 template<class T> const T* get(Ex::iterator, const std::string& label) const;
292 template<class T> const T* get(Ex::iterator, int& serialnum, const std::string& label, bool doserial=true) const;
294 template<class T> const T* get(Ex::iterator, Ex::iterator, bool ignore_parent_rel=false) const;
295 template<class T> const T* get(Ex::iterator, Ex::iterator, int&, int&, bool ignore_parent_rel=false) const;
296
300 template<class T>
301 std::pair<const T*, const pattern *> get_with_pattern(Ex::iterator, int& serialnum,
302 const std::string& label,
303 bool doserial=true, bool ignore_parent_rel=false) const;
304
305 template<class T>
306 std::pair<const T*, const pattern *> get_with_pattern_ext(Ex::iterator, Ex_comparator&, int& serialnum,
307 const std::string& label,
308 bool doserial=true, bool ignore_parent_rel=false) const;
309
310 // Get the outermost node which has the given property attached, i.e. go down through
311 // all (if any) nodes which have just inherited the property.
312 template<class T> Ex::iterator head(Ex::iterator, bool ignore_parent_rel=false) const;
313
314 // Inverse search: given a property type, get a pattern which has this property.
315 // When given an iterator, it starts to search in the property
316 // map from this particular point. Note: this searches on property type, not exact property.
317 // template<class T>
318 // property_map_t::iterator get_pattern(property_map_t::iterator=props.begin());
319
320 // Equivalent search: given a node, get a pattern of equivalents.
321 // property_map_t::iterator get_equivalent(Ex::iterator,
322 // property_map_t::iterator=props.begin());
323
324 private:
325 // Insert a property. Do not use this directly, use the public
326 // interface `master_insert` instead.
327 void insert_prop(const Ex&, const property *);
328 void insert_list_prop(const std::vector<Ex>&, const list_property *);
329 bool check_label(const property *, const std::string&) const;
330 bool check_label(const labelled_property *, const std::string&) const;
331 // Search through pointers
332 bool has(const property *, Ex::iterator);
333 // Find serial number of a pattern in a given list property
334 int serial_number(const property *, const pattern *) const;
336 void destroy_comparator(Ex_comparator *) const;
337 };
338
339 template<class T>
340 const T* Properties::get(Ex::iterator it, bool ignore_parent_rel) const
341 {
342 int tmp;
343 return get<T>(it, tmp, false, ignore_parent_rel);
344 }
345
346 template<class T>
347 const T* Properties::get(Ex::iterator it, int& serialnum, bool doserial, bool ignore_parent_rel) const
348 {
350 return ret.first;
351 }
352
353 template<class T>
354 std::pair<const T*, const pattern *> Properties::get_with_pattern(Ex::iterator it, int& serialnum, const std::string& label,
355 bool doserial, bool ignore_parent_rel) const
356 {
358 // FIXME: catch and rethrow all exceptions so we do not leak memory
361 return ret;
362 }
363
364 template<class T>
365 std::pair<const T*, const pattern *> Properties::get_with_pattern_ext(Ex::iterator it, Ex_comparator& comp,
366 int& serialnum, const std::string& label,
367 bool doserial, bool ignore_parent_rel) const
368 {
369 std::pair<const T*, const pattern *> ret;
370 ret.first=0;
371 ret.second=0;
372 bool inherits=false;
373
374 //std::cerr << *it->name_only() << std::endl;
375 // std::cerr << props.size() << std::endl;
376 std::pair<property_map_t::const_iterator, property_map_t::const_iterator> pit=props.equal_range(it->name_only());
377
378 // First look for properties of the node itself. Go through the loop twice:
379 // once looking for patterns which do not have wildcards, and then looking
380 // for wildcard patterns.
381 bool wildcards=false;
382
383 // For some properties, we cannot lookup properties lower down the
384 // tree, because it would lead to an endless recursion (and it would
385 // not make sense anyway). At the moment, this is only for Accent.
386 bool ignore_properties=false;
387 if(std::is_same<T, Accent>::value)
389
390 for(;;) {
391 property_map_t::const_iterator walk=pit.first;
392 while(walk!=pit.second) {
393 if(wildcards==(*walk).second.first->children_wildcard()) {
394 // First check property type; a dynamic cast is much faster than a pattern match.
395 ret.first=dynamic_cast<const T *>((*walk).second.second);
396 if(ret.first) {
397 if((*walk).second.first->match_ext(*this, it, comp, ignore_parent_rel, ignore_properties)) {
398 ret.second=(*walk).second.first;
399 if(!check_label(ret.first, label))
400 ret.first=0;
401 else {
402 if(doserial)
403 serialnum=serial_number( (*walk).second.second, (*walk).second.first );
404 break;
405 }
406 }
407 }
408 ret.first=0;
409 if(dynamic_cast<const PropertyInherit *>((*walk).second.second))
410 inherits=true;
411 else if(dynamic_cast<const Inherit<T> *>((*walk).second.second))
412 inherits=true;
413 }
414 ++walk;
415 }
416 if(!wildcards && !ret.first) {
417 // std::cerr << "not yet found, switching to wildcards" << std::endl;
418 wildcards=true;
419 }
420 else break;
421 }
422
423 // Do not walk down the tree if the property cannot be passed up the tree.
424 // FIXME: see issue/259.
425 if(std::is_same<T, LaTeXForm>::value)
426 inherits=false;
427
428 // If no property was found, figure out whether a property is inherited from a child node.
429 if(!ret.first && inherits) {
430 // std::cout << "no match but perhaps inheritance?" << std::endl;
431 Ex::sibling_iterator sib=it.begin();
432 while(sib!=it.end()) {
433 std::pair<const T*, const pattern *> tmp=get_with_pattern<T>((Ex::iterator)(sib), serialnum, label, doserial);
434 if(tmp.first) {
435 ret=tmp;
436 break;
437 }
438 ++sib;
439 }
440 }
441
442 // std::cout << ret << std::endl;
443 return ret;
444 }
445
446 template<class T>
447 const T* Properties::get(Ex::iterator it, const std::string& label) const
448 {
449 int tmp;
450 return get<T>(it, tmp, label, false);
451 }
452
453 template<class T>
454 const T* Properties::get(Ex::iterator it, int& serialnum, const std::string& label, bool doserial) const
455 {
456 auto ret=get_with_pattern<T>(it, serialnum, label, doserial, false);
457 return ret.first;
458 }
459
460 template<class T>
461 const T* Properties::get(Ex::iterator it1, Ex::iterator it2, bool ignore_parent_rel) const
462 {
463 int tmp1, tmp2;
465 }
466
467 template<class T>
468 const T* Properties::get(Ex::iterator it1, Ex::iterator it2, int& serialnum1, int& serialnum2, bool ignore_parent_rel) const
469 {
470 const T* ret1=0;
471 const T* ret2=0;
472 bool found=false;
473
474 bool inherits1=false, inherits2=false;
475 std::pair<property_map_t::const_iterator, property_map_t::const_iterator> pit1=props.equal_range(it1->name_only());
476 std::pair<property_map_t::const_iterator, property_map_t::const_iterator> pit2=props.equal_range(it2->name_only());
477
478 property_map_t::const_iterator walk1=pit1.first;
479 while(walk1!=pit1.second) {
480 if((*walk1).second.first->match(*this, it1, ignore_parent_rel)) { // match for object 1 found
481 ret1=dynamic_cast<const T *>((*walk1).second.second);
482 if(ret1) { // property of the right type found for object 1
483 property_map_t::const_iterator walk2=pit2.first;
484 while(walk2!=pit2.second) {
485 if((*walk2).second.first->match(*this, it2, ignore_parent_rel)) { // match for object 2 found
486 ret2=dynamic_cast<const T *>((*walk2).second.second);
487 if(ret2) { // property of the right type found for object 2
488 if(ret1==ret2 && walk1!=walk2) { // accept if properties are the same and patterns are not
489 serialnum1=serial_number( (*walk1).second.second, (*walk1).second.first );
490 serialnum2=serial_number( (*walk2).second.second, (*walk2).second.first );
491 found=true;
492 goto done;
493 }
494 }
495 }
496 if(dynamic_cast<const PropertyInherit *>((*walk2).second.second))
497 inherits2=true;
498 ++walk2;
499 }
500 }
501 if(dynamic_cast<const PropertyInherit *>((*walk1).second.second))
502 inherits1=true;
503 }
504 ++walk1;
505 }
506
507 // If no property was found, figure out whether a property is inherited from a child node.
508 if(!found && (inherits1 || inherits2)) {
509 Ex::sibling_iterator sib1, sib2;
510 if(inherits1) sib1=it1.begin();
511 else sib1=it1;
512 bool keepgoing1=true;
513 do { // 1
514 bool keepgoing2=true;
515 if(inherits2) sib2=it2.begin();
516 else sib2=it2;
517 do { // 2
518 const T* tmp=get<T>((Ex::iterator)(sib1), (Ex::iterator)(sib2), serialnum1, serialnum2, ignore_parent_rel);
519 if(tmp) {
520 ret1=tmp;
521 found=true;
522 goto done;
523 }
524 if(!inherits2 || ++sib2==it2.end())
525 keepgoing2=false;
526 }
527 while(keepgoing2);
528 if(!inherits1 || ++sib1==it1.end())
529 keepgoing1=false;
530 }
531 while(keepgoing1);
532 }
533
534done:
535 if(!found) ret1=0;
536 return ret1;
537 }
538
539 template<class T>
540 Ex::iterator Properties::head(Ex::iterator it, bool ignore_parent_rel) const
541 {
542 Ex::iterator dn=it;
543 for(;;) {
545 dn=dn.begin();
546 }
547 else {
548 assert(get<T>(dn));
549 break;
550 }
551 }
552 return dn;
553 }
554
555 }
A generic tree comparison class which will take into account index contractions and will also keep tr...
Definition Compare.hh:197
Definition Storage.hh:170
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:209
virtual ~Inherit()
Definition Props.hh:211
virtual std::string name() const
Definition Props.hh:212
Definition Kernel.hh:15
internal_property_map_t store
Definition Props.hh:252
std::map< std::string, property *(*)()> internal_property_map_t
Definition Props.hh:249
internal_property_map_t::iterator iterator
Definition Props.hh:250
~registered_property_map_t()
Definition Props.cc:175
Class holding a collection of properties attached to expressions.
Definition Props.hh:242
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:540
std::pair< pattern *, const property * > pat_prop_pair_t
Definition Props.hh:261
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:365
pattern_map_t pats
Definition Props.hh:285
registered_property_map_t registered_properties
Definition Props.hh:260
bool check_label(const property *, const std::string &) const
Definition Props.cc:643
std::multimap< const property *, pattern * > pattern_map_t
Definition Props.hh:271
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:270
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:354
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:340
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:284
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:224
virtual std::string name() const
Definition Props.hh:226
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
std::pair< std::string, Ex > kvpair_t
Definition Props.hh:70
kvlist_t::iterator iterator
Definition Props.hh:74
const_iterator begin() const
Definition Props.cc:207
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:189
std::string label
Definition Props.hh:192
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:198
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 void validate(Kernel &, std::shared_ptr< Ex >) const
Definition Props.cc:255
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:186
virtual ~property()
Definition Props.hh:130
virtual std::string name() const =0
match_t
Definition Props.hh:175
@ exact_match
Definition Props.hh:175
@ no_match
Definition Props.hh:175
@ id_match
Definition Props.hh:175
Functions to handle the exchange properties of two or more symbols in a product.
Definition Adjform.cc:83
void set(rset_t::iterator &num, multiplier_t fac)
Definition Storage.cc:1179