1
2 /******************************************************************************
3 * MODULE : tree.cpp
4 * DESCRIPTION: fixed size trees with reference counting
5 * COPYRIGHT : (C) 1999 Joris van der Hoeven
6 *******************************************************************************
7 * This software falls under the GNU general public license version 3 or later.
8 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
9 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
10 ******************************************************************************/
11
12 #include "generic_tree.hpp"
13 #include "drd_std.hpp"
14 #include "hashset.hpp"
15
16 /******************************************************************************
17 * Main routines for trees
18 ******************************************************************************/
19
20 tree type_helper<tree>::init (UNINIT);
21 int type_helper<tree>::id = new_type_identifier ();
22
23 void
destroy_tree_rep(tree_rep * rep)24 destroy_tree_rep (tree_rep* rep) {
25 if (((int) rep->op) == 0) tm_delete (static_cast<atomic_rep*> (rep));
26 else if (((int) rep->op) > 0) tm_delete (static_cast<compound_rep*>(rep));
27 else tm_delete (static_cast<generic_rep*>(rep));
28 }
29
tree(tree_label l,tree t1)30 tree::tree (tree_label l, tree t1):
31 rep (tm_new<compound_rep> (l, array<tree> (1)))
32 {
33 (static_cast<compound_rep*> (rep))->a[0]=t1;
34 }
35
tree(tree_label l,tree t1,tree t2)36 tree::tree (tree_label l, tree t1, tree t2):
37 rep (tm_new<compound_rep> (l, array<tree> (2)))
38 {
39 (static_cast<compound_rep*> (rep))->a[0]=t1;
40 (static_cast<compound_rep*> (rep))->a[1]=t2;
41 }
42
tree(tree_label l,tree t1,tree t2,tree t3)43 tree::tree (tree_label l, tree t1, tree t2, tree t3):
44 rep (tm_new<compound_rep> (l, array<tree> (3)))
45 {
46 (static_cast<compound_rep*> (rep))->a[0]=t1;
47 (static_cast<compound_rep*> (rep))->a[1]=t2;
48 (static_cast<compound_rep*> (rep))->a[2]=t3;
49 }
50
tree(tree_label l,tree t1,tree t2,tree t3,tree t4)51 tree::tree (tree_label l, tree t1, tree t2, tree t3, tree t4):
52 rep (tm_new<compound_rep> (l, array<tree> (4)))
53 {
54 (static_cast<compound_rep*> (rep))->a[0]=t1;
55 (static_cast<compound_rep*> (rep))->a[1]=t2;
56 (static_cast<compound_rep*> (rep))->a[2]=t3;
57 (static_cast<compound_rep*> (rep))->a[3]=t4;
58 }
59
tree(tree_label l,tree t1,tree t2,tree t3,tree t4,tree t5)60 tree::tree (tree_label l, tree t1, tree t2, tree t3, tree t4, tree t5):
61 rep (tm_new<compound_rep> (l, array<tree> (5)))
62 {
63 (static_cast<compound_rep*> (rep))->a[0]=t1;
64 (static_cast<compound_rep*> (rep))->a[1]=t2;
65 (static_cast<compound_rep*> (rep))->a[2]=t3;
66 (static_cast<compound_rep*> (rep))->a[3]=t4;
67 (static_cast<compound_rep*> (rep))->a[4]=t5;
68 }
69
tree(tree_label l,tree t1,tree t2,tree t3,tree t4,tree t5,tree t6)70 tree::tree (tree_label l,
71 tree t1, tree t2, tree t3, tree t4, tree t5, tree t6):
72 rep (tm_new<compound_rep> (l, array<tree> (6)))
73 {
74 (static_cast<compound_rep*> (rep))->a[0]=t1;
75 (static_cast<compound_rep*> (rep))->a[1]=t2;
76 (static_cast<compound_rep*> (rep))->a[2]=t3;
77 (static_cast<compound_rep*> (rep))->a[3]=t4;
78 (static_cast<compound_rep*> (rep))->a[4]=t5;
79 (static_cast<compound_rep*> (rep))->a[5]=t6;
80 }
81
tree(tree_label l,tree t1,tree t2,tree t3,tree t4,tree t5,tree t6,tree t7)82 tree::tree (tree_label l,
83 tree t1, tree t2, tree t3, tree t4, tree t5, tree t6, tree t7):
84 rep (tm_new<compound_rep> (l, array<tree> (7)))
85 {
86 (static_cast<compound_rep*> (rep))->a[0]=t1;
87 (static_cast<compound_rep*> (rep))->a[1]=t2;
88 (static_cast<compound_rep*> (rep))->a[2]=t3;
89 (static_cast<compound_rep*> (rep))->a[3]=t4;
90 (static_cast<compound_rep*> (rep))->a[4]=t5;
91 (static_cast<compound_rep*> (rep))->a[5]=t6;
92 (static_cast<compound_rep*> (rep))->a[6]=t7;
93 }
94
tree(tree_label l,tree t1,tree t2,tree t3,tree t4,tree t5,tree t6,tree t7,tree t8)95 tree::tree (tree_label l,
96 tree t1, tree t2, tree t3, tree t4,
97 tree t5, tree t6, tree t7, tree t8):
98 rep (tm_new<compound_rep> (l, array<tree> (8)))
99 {
100 (static_cast<compound_rep*> (rep))->a[0]=t1;
101 (static_cast<compound_rep*> (rep))->a[1]=t2;
102 (static_cast<compound_rep*> (rep))->a[2]=t3;
103 (static_cast<compound_rep*> (rep))->a[3]=t4;
104 (static_cast<compound_rep*> (rep))->a[4]=t5;
105 (static_cast<compound_rep*> (rep))->a[5]=t6;
106 (static_cast<compound_rep*> (rep))->a[6]=t7;
107 (static_cast<compound_rep*> (rep))->a[7]=t8;
108 }
109
110 tree
operator ()(int begin,int end)111 tree::operator () (int begin, int end) {
112 int i;
113 tree r (rep->op, end-begin);
114 for (i=begin; i<end; i++)
115 r[i-begin]= (static_cast<compound_rep*> (rep))->a[i];
116 return r;
117 }
118
119 bool
operator ==(tree t,tree u)120 operator == (tree t, tree u) {
121 if (strong_equal (t, u)) return true;
122 return (L(t)==L(u)) &&
123 (L(t)==STRING? (t->label==u->label): (A(t)==A(u)));
124 }
125
126 bool
operator !=(tree t,tree u)127 operator != (tree t, tree u) {
128 if (strong_equal (t, u)) return false;
129 return (L(t)!=L(u)) ||
130 (L(t)==STRING? (t->label!=u->label): (A(t)!=A(u)));
131 }
132
133 tree
copy(tree t)134 copy (tree t) {
135 if (is_atomic (t)) return tree (copy (t->label));
136 else {
137 int i, n= N(t);
138 tree t2 (t, n);
139 for (i=0; i<n; i++) t2[i]= copy (t[i]);
140 return t2;
141 }
142 }
143
144 tree
freeze(tree t)145 freeze (tree t) {
146 if (is_atomic (t)) return copy (t->label);
147 if (is_func (t, UNFREEZE, 1)) return t[0];
148 else {
149 int i, n= N(t);
150 tree r (t, n);
151 for (i=0; i<n; i++)
152 r[i]= freeze (t[i]);
153 return r;
154 }
155 }
156
157 tree
operator *(tree t1,tree t2)158 operator * (tree t1, tree t2) {
159 int i;
160 if (is_atomic (t1)) t1= tree (L(t2), t1);
161 if (is_atomic (t2)) t2= tree (L(t1), t2);
162 tree r (t1, N(t1)+N(t2));
163 for (i=0; i<N(t1); i++) r[i]= t1[i];
164 for (i=0; i<N(t2); i++) r[i+N(t1)]= t2[i];
165 return r;
166 }
167
168 tree&
operator <<(tree & t,tree t2)169 operator << (tree& t, tree t2) {
170 CHECK_COMPOUND (t);
171 (static_cast<compound_rep*> (t.rep))->a << t2;
172 return t;
173 }
174
175 tree&
operator <<(tree & t,array<tree> a)176 operator << (tree& t, array<tree> a) {
177 CHECK_COMPOUND (t);
178 (static_cast<compound_rep*> (t.rep))->a << a;
179 return t;
180 }
181
182 tm_ostream&
operator <<(tm_ostream & out,tree t)183 operator << (tm_ostream& out, tree t) {
184 if (is_atomic (t)) return out << t->label;
185 else if (is_compound (t)) {
186 int i, n= N(t);
187 out << as_string (L(t));
188 if (n==0) return out << "()";
189 out << " (";
190 for (i=0; i< n-1; i++)
191 out << t[i] << ", ";
192 out << t[i] << ")";
193 return out;
194 }
195 else out << as_blackbox (t);
196 return out;
197 }
198
199 void
print_tree(tree t,int tab=0)200 print_tree (tree t, int tab=0) {
201 int i;
202 for (i=0; i<tab; i++) cout << " ";
203 if (is_atomic (t)) cout << t->label << "\n";
204 else {
205 cout << as_string (L(t)) << "\n";
206 for (i=0; i<N(t); i++) print_tree (t[i], tab+2);
207 }
208 }
209
210 int
hash(array<tree> a)211 hash (array<tree> a) {
212 register int i, h=0, n=N(a);
213 for (i=0; i<n; i++) {
214 h=(h<<7) + (h>>25);
215 h=h + hash(a[i]);
216 }
217 return h;
218 }
219
220 int
hash(tree t)221 hash (tree t) {
222 if (is_atomic (t)) return hash (t->label);
223 else return ((int) L(t)) ^ hash (A(t));
224 }
225
226 string
tree_as_string(tree t)227 tree_as_string (tree t) {
228 if (is_atomic (t)) return t->label;
229 else if (is_concat (t) || is_document (t)) {
230 int i, n= N(t);
231 string cumul;
232 for (i=0; i<n; i++)
233 cumul << tree_as_string (t[i]);
234 return cumul;
235 }
236 else if (is_func (t, WITH))
237 return tree_as_string (t[N(t)-1]);
238 else if (is_compound (t, "nbsp", 0))
239 return " ";
240 return "";
241 }
242
243 tree
replace(tree t,tree w,tree b)244 replace (tree t, tree w, tree b) {
245 if (t == w) return b;
246 else if (is_atomic (t)) return t;
247 else {
248 int i, n= N(t);
249 tree r (t, n);
250 for (i=0; i<n; i++)
251 r[i]= replace (t[i], w, b);
252 return r;
253 }
254 }
255
256 /******************************************************************************
257 * Tree predicates
258 ******************************************************************************/
259
260 bool
is_document(tree t)261 is_document (tree t) {
262 return L(t) == DOCUMENT;
263 }
264
265 bool
is_concat(tree t)266 is_concat (tree t) {
267 return L(t) == CONCAT;
268 }
269
270 bool
is_format(tree t)271 is_format (tree t) {
272 return is_document (t) || is_concat (t);
273 }
274
275 bool
is_formatting(tree t)276 is_formatting (tree t) {
277 return (L(t)>=WITH_LIMITS) && (L(t)<=NEW_DPAGE);
278 }
279
280 bool
is_table(tree t)281 is_table (tree t) {
282 return
283 is_func (t, TABLE) || is_func (t, SUBTABLE) ||
284 is_func (t, ROW) || is_func (t, CELL);
285 }
286
287 bool
is_table_format(tree t)288 is_table_format (tree t) {
289 return is_func (t, TFORMAT);
290 }
291
292 bool
is_multi_paragraph(tree t)293 is_multi_paragraph (tree t) {
294 switch (L(t)) {
295 case DOCUMENT:
296 return true;
297 case SURROUND:
298 return is_multi_paragraph (t[2]);
299 case DATOMS:
300 case DLINES:
301 case DPAGES:
302 case WITH:
303 case MARK:
304 case EXPAND_AS:
305 case STYLE_WITH:
306 case VAR_STYLE_WITH:
307 case STYLE_ONLY:
308 case VAR_STYLE_ONLY:
309 case ACTIVE:
310 case VAR_ACTIVE:
311 return is_multi_paragraph (t[N(t)-1]);
312 case VAR_INCLUDE:
313 return true;
314 case LOCUS:
315 case CANVAS:
316 return is_multi_paragraph (t[N(t)-1]);
317 default:
318 {
319 static hashset<tree_label> inline_set; // FIXME: use drd
320 if (N(inline_set) == 0) {
321 inline_set->insert (make_tree_label ("footnote"));
322 inline_set->insert (make_tree_label ("script-input"));
323 inline_set->insert (make_tree_label ("converter-input"));
324 }
325 if (L(t) < START_EXTENSIONS) return false;
326 else if (inline_set->contains (L(t))) return false;
327 else {
328 int i, n= N(t);
329 for (i=0; i<n; i++)
330 if (is_multi_paragraph (t[i]))
331 return true;
332 return false;
333 }
334 }
335 }
336 }
337
338 bool
is_around(tree t)339 is_around (tree t) {
340 return is_func (t, AROUND, 3) || is_func (t, VAR_AROUND, 3);
341 }
342
343 bool
is_script(tree t)344 is_script (tree t) {
345 return
346 is_func (t, LSUB) || is_func (t, LSUP) ||
347 is_func (t, RSUB) || is_func (t, RSUP);
348 }
349
350 bool
is_script(tree t,bool & right)351 is_script (tree t, bool& right) {
352 if (is_func (t, LSUB) ||
353 is_func (t, LSUP)) { right=false; return true; }
354 if (is_func (t, RSUB) ||
355 is_func (t, RSUP)) { right=true; return true; }
356 return false;
357 }
358
359 bool
is_prime(tree t)360 is_prime (tree t) {
361 return ((L(t) == LPRIME) || (L(t) == RPRIME)) && (N(t) == 1);
362 }
363
364 bool
is_right_script_prime(tree t)365 is_right_script_prime (tree t) {
366 return is_func (t, RSUB, 1) || is_func (t, RSUP, 1) ||
367 is_func (t, RPRIME, 1);
368 }
369
370 bool
is_mod_active(tree t)371 is_mod_active (tree t) {
372 return (N(t) == 1) && (L(t) >= STYLE_ONLY) && (L(t) <= VAR_INACTIVE);
373 }
374
375 bool
is_mod_active_once(tree t)376 is_mod_active_once (tree t) {
377 return (N(t) == 1) &&
378 ((L(t) == STYLE_ONLY) || (L(t) == ACTIVE) || (L(t) == INACTIVE));
379 }
380
381 bool
is_graphical_text(tree t)382 is_graphical_text (tree t) {
383 return is_func (t, TEXT_AT) || is_func (t, MATH_AT);
384 }
385
386 bool
is_empty(tree t)387 is_empty (tree t) {
388 if (is_atomic (t)) return (t == "");
389 if (is_document (t) || is_concat (t)) {
390 int i, n= N(t);
391 for (i=0; i<n; i++)
392 if (!is_empty (t[i])) return false;
393 return is_concat (t) || (n<=1);
394 }
395 return is_compound (t, "suppressed");
396 }
397
398 /******************************************************************************
399 * Compound trees
400 ******************************************************************************/
401
402 tree
compound(string s)403 compound (string s) {
404 return tree (make_tree_label (s));
405 }
406
407 tree
compound(string s,tree t1)408 compound (string s, tree t1) {
409 return tree (make_tree_label (s), t1);
410 }
411
412 tree
compound(string s,tree t1,tree t2)413 compound (string s, tree t1, tree t2) {
414 return tree (make_tree_label (s), t1, t2);
415 }
416
417 tree
compound(string s,tree t1,tree t2,tree t3)418 compound (string s, tree t1, tree t2, tree t3) {
419 return tree (make_tree_label (s), t1, t2, t3);
420 }
421
422 tree
compound(string s,tree t1,tree t2,tree t3,tree t4)423 compound (string s, tree t1, tree t2, tree t3, tree t4) {
424 return tree (make_tree_label (s), t1, t2, t3, t4);
425 }
426
427 tree
compound(string s,array<tree> a)428 compound (string s, array<tree> a) {
429 return tree (make_tree_label (s), a);
430 }
431
432 bool
is_extension(tree_label l)433 is_extension(tree_label l) {
434 return l >= START_EXTENSIONS;
435 }
436
437 bool
is_extension(tree t)438 is_extension (tree t) {
439 return L(t) >= START_EXTENSIONS;
440 }
441
442 bool
is_extension(tree t,int n)443 is_extension (tree t, int n) {
444 return (L(t) >= START_EXTENSIONS) && (N(t) == n);
445 }
446
447 bool
is_compound(tree t,string s)448 is_compound (tree t, string s) {
449 return as_string (L(t)) == s;
450 }
451
452 bool
is_compound(tree t,string s,int n)453 is_compound (tree t, string s, int n) {
454 return (as_string (L(t)) == s) && (N(t) == n);
455 }
456
457 /******************************************************************************
458 * Routines for simplification and correction
459 ******************************************************************************/
460
461 static void
simplify_concat(tree & r,tree t)462 simplify_concat (tree& r, tree t) {
463 if (is_atomic (t)) {
464 r= concat (t);
465 return;
466 }
467 int i, n= N(t);
468 for (i=0; i<n; i++)
469 if (is_concat (t[i])) simplify_concat (r, t[i]);
470 else if (t[i] == "");
471 else if (is_atomic (t[i]) && (N(r)>0) && is_atomic (r[N(r)-1]))
472 r[N(r)-1]= tree (r[N(r)-1]->label * t[i]->label);
473 else r << t[i];
474 }
475
476 tree
simplify_concat(tree t)477 simplify_concat (tree t) {
478 if (is_atomic (t)) return t;
479 tree r (CONCAT);
480 simplify_concat (r, t);
481 if (N(r) == 0) return "";
482 if (N(r) == 1) return r[0];
483 return r;
484 }
485
486 static void
simplify_document(tree & r,tree t)487 simplify_document (tree& r, tree t) {
488 int i, n= N(t);
489 for (i=0; i<n; i++)
490 if (is_document (t[i])) simplify_document (r, t[i]);
491 else r << t[i];
492 }
493
494 tree
simplify_document(tree t)495 simplify_document (tree t) {
496 if (!is_document (t)) return t;
497 tree r (DOCUMENT);
498 simplify_document (r, t);
499 return r;
500 }
501
502 tree
simplify_correct(tree t)503 simplify_correct (tree t) {
504 if (is_atomic (t)) return t;
505 if (is_func (t, QUOTE, 1) && (is_atomic (t[0]))) return t[0];
506 int i, n= N(t);
507 tree r (t, n);
508 for (i=0; i<n; i++)
509 r[i]= simplify_correct (t[i]);
510 if (is_concat (r)) r= simplify_concat (r);
511 if (is_document (r)) r= simplify_document (r);
512 return r;
513 }
514