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