numeric.cpp, archive.cpp: don't include config.h
[ginac.git] / ginac / archive.cpp
1 /** @file archive.cpp
2  *
3  *  Archiving of GiNaC expressions. */
4
5 /*
6  *  GiNaC Copyright (C) 1999-2020 Johannes Gutenberg University Mainz, Germany
7  *
8  *  This program is free software; you can redistribute it and/or modify
9  *  it under the terms of the GNU General Public License as published by
10  *  the Free Software Foundation; either version 2 of the License, or
11  *  (at your option) any later version.
12  *
13  *  This program is distributed in the hope that it will be useful,
14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  *  GNU General Public License for more details.
17  *
18  *  You should have received a copy of the GNU General Public License
19  *  along with this program; if not, write to the Free Software
20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
21  */
22
23 #include "archive.h"
24 #include "registrar.h"
25 #include "ex.h"
26 #include "lst.h"
27 #include "version.h"
28
29 #include <iostream>
30 #include <stdexcept>
31
32 namespace GiNaC {
33
34
35 void archive::archive_ex(const ex &e, const char *name)
36 {
37         // Create root node (which recursively archives the whole expression tree)
38         // and add it to the archive
39         archive_node_id id = add_node(archive_node(*this, e));
40
41         // Add root node ID to list of archived expressions
42         archived_ex ae = archived_ex(atomize(name), id);
43         exprs.emplace_back(ae);
44 }
45
46
47 /** Add archive_node to archive if the corresponding expression is
48  *  not already archived.
49  *  @return ID of archived node */
50 archive_node_id archive::add_node(const archive_node &n)
51 {
52         // Look if expression is known to be in some node already.
53         if (n.has_ex()) {
54                 auto i = exprtable.find(n.get_ex());
55                 if (i != exprtable.end())
56                         return i->second;
57                 nodes.push_back(n);
58                 exprtable[n.get_ex()] = nodes.size() - 1;
59                 return nodes.size() - 1;
60         }
61
62         // Not found, add archive_node to nodes vector
63         nodes.push_back(n);
64         return nodes.size()-1;
65 }
66
67
68 /** Retrieve archive_node by ID. */
69 archive_node &archive::get_node(archive_node_id id)
70 {
71         if (id >= nodes.size())
72                 throw (std::range_error("archive::get_node(): archive node ID out of range"));
73
74         return nodes[id];
75 }
76
77
78 ex archive::unarchive_ex(const lst &sym_lst, const char *name) const
79 {
80         // Find root node
81         std::string name_string = name;
82         archive_atom id = atomize(name_string);
83         auto i = exprs.begin(), iend = exprs.end();
84         while (i != iend) {
85                 if (i->name == id)
86                         goto found;
87                 i++;
88         }
89         throw (std::runtime_error("expression with name '" + name_string + "' not found in archive"));
90
91 found:
92         // Recursively unarchive all nodes, starting at the root node
93         lst sym_lst_copy = sym_lst;
94         return nodes[i->root].unarchive(sym_lst_copy);
95 }
96
97 ex archive::unarchive_ex(const lst &sym_lst, unsigned index) const
98 {
99         if (index >= exprs.size())
100                 throw (std::range_error("index of archived expression out of range"));
101
102         // Recursively unarchive all nodes, starting at the root node
103         lst sym_lst_copy = sym_lst;
104         return nodes[exprs[index].root].unarchive(sym_lst_copy);
105 }
106
107 ex archive::unarchive_ex(const lst &sym_lst, std::string &name, unsigned index) const
108 {
109         if (index >= exprs.size())
110                 throw (std::range_error("index of archived expression out of range"));
111
112         // Return expression name
113         name = unatomize(exprs[index].name);
114
115         // Recursively unarchive all nodes, starting at the root node
116         lst sym_lst_copy = sym_lst;
117         return nodes[exprs[index].root].unarchive(sym_lst_copy);
118 }
119
120 unsigned archive::num_expressions() const
121 {
122         return exprs.size();
123 }
124
125 const archive_node &archive::get_top_node(unsigned index) const
126 {
127         if (index >= exprs.size())
128                 throw (std::range_error("index of archived expression out of range"));
129
130         return nodes[exprs[index].root];
131 }
132
133
134 /*
135  *  Archive file format
136  *
137  *   - 4 bytes signature 'GARC'
138  *   - unsigned version number
139  *   - unsigned number of atoms
140  *      - atom strings (each zero-terminated)
141  *   - unsigned number of expressions
142  *      - unsigned name atom
143  *      - unsigned root node ID
144  *   - unsigned number of nodes
145  *      - unsigned number of properties
146  *        - unsigned containing type (PTYPE_*) in its lower 3 bits and
147  *          name atom in the upper bits
148  *        - unsigned property value
149  *
150  *  Unsigned quantities are stored in a compressed format:
151  *   - numbers in the range 0x00..0x7f are stored verbatim (1 byte)
152  *   - numbers larger than 0x7f are stored in 7-bit packets (1 byte per
153  *     packet), starting with the LSBs; all bytes except the last one have
154  *     their upper bit set
155  *
156  *  Examples:
157  *   0x00           =   0x00
158  *    ..                 ..
159  *   0x7f           =   0x7f
160  *   0x80 0x01      =   0x80
161  *    ..   ..            ..
162  *   0xff 0x01      =   0xff
163  *   0x80 0x02      =  0x100
164  *    ..   ..            ..
165  *   0xff 0x02      =  0x17f
166  *   0x80 0x03      =  0x180
167  *    ..   ..            ..
168  *   0xff 0x7f      = 0x3fff
169  *   0x80 0x80 0x01 = 0x4000
170  *    ..   ..   ..       ..
171  */
172
173 /** Write unsigned integer quantity to stream. */
174 static void write_unsigned(std::ostream &os, unsigned val)
175 {
176         while (val >= 0x80) {
177                 os.put((val & 0x7f) | 0x80);
178                 val >>= 7;
179         }
180         os.put(val);
181 }
182
183 /** Read unsigned integer quantity from stream. */
184 static unsigned read_unsigned(std::istream &is)
185 {
186         unsigned char b;
187         unsigned ret = 0;
188         unsigned shift = 0;
189         do {
190                 char b2;
191                 is.get(b2);
192                 b = b2;
193                 ret |= (b & 0x7f) << shift;
194                 shift += 7;
195         } while (b & 0x80);
196         return ret;
197 }
198
199 /** Write archive_node to binary data stream. */
200 std::ostream &operator<<(std::ostream &os, const archive_node &n)
201 {
202         // Write properties
203         unsigned num_props = n.props.size();
204         write_unsigned(os, num_props);
205         for (unsigned i=0; i<num_props; i++) {
206                 write_unsigned(os, n.props[i].type | (n.props[i].name << 3));
207                 write_unsigned(os, n.props[i].value);
208         }
209         return os;
210 }
211
212 /** Write archive to binary data stream. */
213 std::ostream &operator<<(std::ostream &os, const archive &ar)
214 {
215         // Write header
216         os.put('G');    // Signature
217         os.put('A');
218         os.put('R');
219         os.put('C');
220         write_unsigned(os, GINACLIB_ARCHIVE_VERSION);
221
222         // Write atoms
223         unsigned num_atoms = ar.atoms.size();
224         write_unsigned(os, num_atoms);
225         for (unsigned i=0; i<num_atoms; i++)
226                 os << ar.atoms[i] << std::ends;
227
228         // Write expressions
229         unsigned num_exprs = ar.exprs.size();
230         write_unsigned(os, num_exprs);
231         for (unsigned i=0; i<num_exprs; i++) {
232                 write_unsigned(os, ar.exprs[i].name);
233                 write_unsigned(os, ar.exprs[i].root);
234         }
235
236         // Write nodes
237         unsigned num_nodes = ar.nodes.size();
238         write_unsigned(os, num_nodes);
239         for (unsigned i=0; i<num_nodes; i++)
240                 os << ar.nodes[i];
241         return os;
242 }
243
244 /** Read archive_node from binary data stream. */
245 std::istream &operator>>(std::istream &is, archive_node &n)
246 {
247         // Read properties
248         unsigned num_props = read_unsigned(is);
249         n.props.resize(num_props);
250         for (unsigned i=0; i<num_props; i++) {
251                 unsigned name_type = read_unsigned(is);
252                 n.props[i].type = (archive_node::property_type)(name_type & 7);
253                 n.props[i].name = name_type >> 3;
254                 n.props[i].value = read_unsigned(is);
255         }
256         return is;
257 }
258
259 /** Read archive from binary data stream. */
260 std::istream &operator>>(std::istream &is, archive &ar)
261 {
262         // Read header
263         char c1, c2, c3, c4;
264         is.get(c1); is.get(c2); is.get(c3); is.get(c4);
265         if (c1 != 'G' || c2 != 'A' || c3 != 'R' || c4 != 'C')
266                 throw (std::runtime_error("not a GiNaC archive (signature not found)"));
267         constexpr unsigned max_version = GINACLIB_ARCHIVE_VERSION;
268         constexpr unsigned min_version = GINACLIB_ARCHIVE_VERSION - GINACLIB_ARCHIVE_AGE;
269         unsigned version = read_unsigned(is);
270         if ((version > max_version) || (version < min_version))
271                 throw (std::runtime_error("archive version " + std::to_string(version) + " cannot be read by this GiNaC library (which supports versions " + std::to_string(min_version) + " thru " + std::to_string(max_version)));
272
273         // Read atoms
274         unsigned num_atoms = read_unsigned(is);
275         ar.atoms.resize(num_atoms);
276         for (unsigned i=0; i<num_atoms; i++) {
277                 getline(is, ar.atoms[i], '\0');
278                 ar.inverse_atoms[ar.atoms[i]] = i;
279         }
280
281         // Read expressions
282         unsigned num_exprs = read_unsigned(is);
283         ar.exprs.resize(num_exprs);
284         for (unsigned i=0; i<num_exprs; i++) {
285                 archive_atom name = read_unsigned(is);
286                 archive_node_id root = read_unsigned(is);
287                 ar.exprs[i] = archive::archived_ex(name, root);
288         }
289
290         // Read nodes
291         unsigned num_nodes = read_unsigned(is);
292         ar.nodes.resize(num_nodes, ar);
293         for (unsigned i=0; i<num_nodes; i++)
294                 is >> ar.nodes[i];
295         return is;
296 }
297
298
299 /** Atomize a string (i.e. convert it into an ID number that uniquely
300  *  represents the string). */
301 archive_atom archive::atomize(const std::string &s) const
302 {
303         // Search for string in inverse_atoms map.
304         inv_at_cit i = inverse_atoms.find(s);
305         if (i!=inverse_atoms.end())
306                 return i->second;
307
308         // Not found, add to atoms vector
309         archive_atom id = atoms.size();
310         atoms.push_back(s);
311         inverse_atoms[s] = id;
312         return id;
313 }
314
315 /** Unatomize a string (i.e. convert the ID number back to the string). */
316 const std::string &archive::unatomize(archive_atom id) const
317 {
318         if (id >= atoms.size())
319                 throw (std::range_error("archive::unatomize(): atom ID out of range"));
320
321         return atoms[id];
322 }
323
324
325 /** Assignment operator of archive_node. */
326 const archive_node &archive_node::operator=(const archive_node &other)
327 {
328         if (this != &other) {
329                 // archive &a member doesn't get copied
330                 props = other.props;
331                 has_expression = other.has_expression;
332                 e = other.e;
333         }
334         return *this;
335 }
336
337
338 /** Recursively construct archive node from expression. */
339 archive_node::archive_node(archive &ar, const ex &expr)
340   : a(ar), has_expression(true), e(expr)
341 {
342         expr.bp->archive(*this);
343 }
344
345
346 /** Check if the archive_node stores the same expression as another
347  *  archive_node.
348  *  @return "true" if expressions are the same */
349 bool archive_node::has_same_ex_as(const archive_node &other) const
350 {
351         if (!has_expression || !other.has_expression)
352                 return false;
353         return e.bp == other.e.bp;
354 }
355
356 archive_node::archive_node_cit
357 archive_node::find_first(const std::string &name) const
358 {
359         archive_atom name_atom = a.atomize(name);
360         for (auto i=props.begin(); i!=props.end(); ++i)
361                 if (i->name == name_atom)
362                         return i;
363         return props.end();
364 }
365
366 archive_node::archive_node_cit
367 archive_node::find_last(const std::string &name) const
368 {
369         archive_atom name_atom = a.atomize(name);
370         for (auto i=props.end(); i!=props.begin();) {
371                 --i;
372                 if (i->name == name_atom)
373                         return i;
374         }
375         return props.end();
376 }
377
378 archive_node::archive_node_cit_range
379 archive_node::find_property_range(const std::string &name1, const std::string &name2) const
380 {
381         archive_atom name1_atom = a.atomize(name1),
382                      name2_atom = a.atomize(name2);
383         archive_node_cit_range range = {props.end(), props.end()};
384         for (auto i=props.begin(); i!=props.end(); ++i) {
385                 if (i->name == name1_atom && range.begin == props.end()) {
386                         range.begin = i;
387                 }
388                 if (i->name == name2_atom && range.begin != props.end()) {
389                         range.end = i + 1;
390                 }
391         }
392         return range;
393 }
394
395 void archive_node::add_bool(const std::string &name, bool value)
396 {
397         props.emplace_back(property(a.atomize(name), PTYPE_BOOL, value));
398 }
399
400 void archive_node::add_unsigned(const std::string &name, unsigned value)
401 {
402         props.emplace_back(property(a.atomize(name), PTYPE_UNSIGNED, value));
403 }
404
405 void archive_node::add_string(const std::string &name, const std::string &value)
406 {
407         props.emplace_back(property(a.atomize(name), PTYPE_STRING, a.atomize(value)));
408 }
409
410 void archive_node::add_ex(const std::string &name, const ex &value)
411 {
412         // Recursively create an archive_node and add its ID to the properties of this node
413         archive_node_id id = a.add_node(archive_node(a, value));
414         props.emplace_back(property(a.atomize(name), PTYPE_NODE, id));
415 }
416
417
418 bool archive_node::find_bool(const std::string &name, bool &ret, unsigned index) const
419 {
420         archive_atom name_atom = a.atomize(name);
421         auto i = props.begin(), iend = props.end();
422         unsigned found_index = 0;
423         while (i != iend) {
424                 if (i->type == PTYPE_BOOL && i->name == name_atom) {
425                         if (found_index == index) {
426                                 ret = i->value;
427                                 return true;
428                         }
429                         found_index++;
430                 }
431                 i++;
432         }
433         return false;
434 }
435
436 bool archive_node::find_unsigned(const std::string &name, unsigned &ret, unsigned index) const
437 {
438         archive_atom name_atom = a.atomize(name);
439         auto i = props.begin(), iend = props.end();
440         unsigned found_index = 0;
441         while (i != iend) {
442                 if (i->type == PTYPE_UNSIGNED && i->name == name_atom) {
443                         if (found_index == index) {
444                                 ret = i->value;
445                                 return true;
446                         }
447                         found_index++;
448                 }
449                 i++;
450         }
451         return false;
452 }
453
454 bool archive_node::find_string(const std::string &name, std::string &ret, unsigned index) const
455 {
456         archive_atom name_atom = a.atomize(name);
457         auto i = props.begin(), iend = props.end();
458         unsigned found_index = 0;
459         while (i != iend) {
460                 if (i->type == PTYPE_STRING && i->name == name_atom) {
461                         if (found_index == index) {
462                                 ret = a.unatomize(i->value);
463                                 return true;
464                         }
465                         found_index++;
466                 }
467                 i++;
468         }
469         return false;
470 }
471
472 void archive_node::find_ex_by_loc(archive_node_cit loc, ex &ret, lst &sym_lst) const
473 {
474         ret = a.get_node(loc->value).unarchive(sym_lst);
475 }
476
477 bool archive_node::find_ex(const std::string &name, ex &ret, lst &sym_lst, unsigned index) const
478 {
479         archive_atom name_atom = a.atomize(name);
480         auto i = props.begin(), iend = props.end();
481         unsigned found_index = 0;
482         while (i != iend) {
483                 if (i->type == PTYPE_NODE && i->name == name_atom) {
484                         if (found_index == index) {
485                                 ret = a.get_node(i->value).unarchive(sym_lst);
486                                 return true;
487                         }
488                         found_index++;
489                 }
490                 i++;
491         }
492         return false;
493 }
494
495 const archive_node &archive_node::find_ex_node(const std::string &name, unsigned index) const
496 {
497         archive_atom name_atom = a.atomize(name);
498         auto i = props.begin(), iend = props.end();
499         unsigned found_index = 0;
500         while (i != iend) {
501                 if (i->type == PTYPE_NODE && i->name == name_atom) {
502                         if (found_index == index)
503                                 return a.get_node(i->value);
504                         found_index++;
505                 }
506                 i++;
507         }
508         throw (std::runtime_error("property with name '" + name + "' not found in archive node"));
509 }
510
511
512 void archive_node::get_properties(propinfovector &v) const
513 {
514         v.clear();
515         auto i = props.begin(), iend = props.end();
516         while (i != iend) {
517                 property_type type = i->type;
518                 std::string name = a.unatomize(i->name);
519
520                 auto a = v.begin(), aend = v.end();
521                 bool found = false;
522                 while (a != aend) {
523                         if (a->type == type && a->name == name) {
524                                 a->count++;
525                                 found = true;
526                                 break;
527                         }
528                         ++a;
529                 }
530                 if (!found)
531                         v.emplace_back(property_info(type, name));
532                 i++;
533         }
534 }
535
536 static synthesize_func find_factory_fcn(const std::string& name)
537 {
538         static unarchive_table_t the_table;
539         synthesize_func ret = the_table.find(name);
540         return ret;
541 }
542
543 /** Convert archive node to GiNaC expression. */
544 ex archive_node::unarchive(lst &sym_lst) const
545 {
546         // Already unarchived? Then return cached unarchived expression.
547         if (has_expression)
548                 return e;
549
550         // Find instantiation function for class specified in node
551         std::string class_name;
552         if (!find_string("class", class_name))
553                 throw (std::runtime_error("archive node contains no class name"));
554
555         // Call instantiation function
556         synthesize_func factory_fcn = find_factory_fcn(class_name);
557         ptr<basic> obj(factory_fcn());
558         obj->setflag(status_flags::dynallocated);
559         obj->read_archive(*this, sym_lst);
560         e = ex(*obj);
561         has_expression = true;
562         return e;
563 }
564
565 int unarchive_table_t::usecount = 0;
566 unarchive_map_t* unarchive_table_t::unarch_map = nullptr;
567
568 unarchive_table_t::unarchive_table_t()
569 {
570         if (usecount == 0)
571                 unarch_map = new unarchive_map_t();
572         ++usecount;
573 }
574
575 synthesize_func unarchive_table_t::find(const std::string& classname) const
576 {
577         unarchive_map_t::const_iterator i = unarch_map->find(classname);
578         if (i != unarch_map->end())
579                 return i->second;
580         throw std::runtime_error(std::string("no unarchiving function for \"")
581                         + classname + "\" class");
582 }
583
584 void unarchive_table_t::insert(const std::string& classname, synthesize_func f)
585 {
586         if (unarch_map->find(classname) != unarch_map->end())
587                 throw std::runtime_error(std::string("Class \"" + classname
588                                         + "\" is already registered"));
589         unarch_map->operator[](classname) = f;
590 }
591
592 unarchive_table_t::~unarchive_table_t()
593 {
594         if (--usecount == 0)
595                 delete unarch_map;
596 }
597
598
599 void archive::clear()
600 {
601         atoms.clear();
602         inverse_atoms.clear();
603         exprs.clear();
604         nodes.clear();
605         exprtable.clear();
606 }
607
608
609 /** Delete cached unarchived expressions in all archive_nodes (mainly for debugging). */
610 void archive::forget()
611 {
612         for_each(nodes.begin(), nodes.end(), std::mem_fun_ref(&archive_node::forget));
613 }
614
615 /** Delete cached unarchived expressions from node (for debugging). */
616 void archive_node::forget()
617 {
618         has_expression = false;
619         e = 0;
620 }
621
622
623 /** Print archive to stream in ugly raw format (for debugging). */
624 void archive::printraw(std::ostream &os) const
625 {
626         // Dump atoms
627         os << "Atoms:\n";
628         {
629                 std::vector<std::string>::const_iterator i = atoms.begin(), iend = atoms.end();
630                 archive_atom id = 0;
631                 while (i != iend) {
632                         os << " " << id << " " << *i << std::endl;
633                         i++; id++;
634                 }
635         }
636         os << std::endl;
637
638         // Dump expressions
639         os << "Expressions:\n";
640         {
641                 auto i = exprs.begin(), iend = exprs.end();
642                 unsigned index = 0;
643                 while (i != iend) {
644                         os << " " << index << " \"" << unatomize(i->name) << "\" root node " << i->root << std::endl;
645                         i++; index++;
646                 }
647         }
648         os << std::endl;
649
650         // Dump nodes
651         os << "Nodes:\n";
652         {
653                 auto i = nodes.begin(), iend = nodes.end();
654                 archive_node_id id = 0;
655                 while (i != iend) {
656                         os << " " << id << " ";
657                         i->printraw(os);
658                         i++; id++;
659                 }
660         }
661 }
662
663 /** Output archive_node to stream in ugly raw format (for debugging). */
664 void archive_node::printraw(std::ostream &os) const
665 {
666         // Dump cached unarchived expression
667         if (has_expression)
668                 os << "(basic * " << e.bp << " = " << e << ")\n";
669         else
670                 os << "\n";
671
672         // Dump properties
673         auto i = props.begin(), iend = props.end();
674         while (i != iend) {
675                 os << "  ";
676                 switch (i->type) {
677                         case PTYPE_BOOL: os << "bool"; break;
678                         case PTYPE_UNSIGNED: os << "unsigned"; break;
679                         case PTYPE_STRING: os << "string"; break;
680                         case PTYPE_NODE: os << "node"; break;
681                         default: os << "<unknown>"; break;
682                 }
683                 os << " \"" << a.unatomize(i->name) << "\" " << i->value << std::endl;
684                 i++;
685         }
686 }
687
688
689 } // namespace GiNaC