Back to index

texmacs  1.0.7.15
tree.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : tree.cpp
00004 * DESCRIPTION: fixed size trees with reference counting
00005 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #include "generic_tree.hpp"
00013 #include "drd_std.hpp"
00014 #include "hashset.hpp"
00015 
00016 /******************************************************************************
00017 * Main routines for trees
00018 ******************************************************************************/
00019 
00020 tree type_helper<tree>::init (UNINIT);
00021 int type_helper<tree>::id  = new_type_identifier ();
00022 
00023 void
00024 destroy_tree_rep (tree_rep* rep) {
00025   if (((int) rep->op) == 0) tm_delete (static_cast<atomic_rep*> (rep));
00026   else if (((int) rep->op) > 0) tm_delete (static_cast<compound_rep*>(rep));
00027   else tm_delete (static_cast<generic_rep*>(rep));
00028 }
00029 
00030 tree::tree (tree_label l, tree t1):
00031   rep (tm_new<compound_rep> (l, array<tree> (1)))
00032 {
00033   (static_cast<compound_rep*> (rep))->a[0]=t1;
00034 }
00035 
00036 tree::tree (tree_label l, tree t1, tree t2):
00037   rep (tm_new<compound_rep> (l, array<tree> (2)))
00038 {
00039   (static_cast<compound_rep*> (rep))->a[0]=t1;
00040   (static_cast<compound_rep*> (rep))->a[1]=t2;
00041 }
00042 
00043 tree::tree (tree_label l, tree t1, tree t2, tree t3):
00044   rep (tm_new<compound_rep> (l, array<tree> (3)))
00045 {
00046   (static_cast<compound_rep*> (rep))->a[0]=t1;
00047   (static_cast<compound_rep*> (rep))->a[1]=t2;
00048   (static_cast<compound_rep*> (rep))->a[2]=t3;
00049 }
00050 
00051 tree::tree (tree_label l, tree t1, tree t2, tree t3, tree t4):
00052   rep (tm_new<compound_rep> (l, array<tree> (4)))
00053 {
00054   (static_cast<compound_rep*> (rep))->a[0]=t1;
00055   (static_cast<compound_rep*> (rep))->a[1]=t2;
00056   (static_cast<compound_rep*> (rep))->a[2]=t3;
00057   (static_cast<compound_rep*> (rep))->a[3]=t4;
00058 }
00059 
00060 tree::tree (tree_label l, tree t1, tree t2, tree t3, tree t4, tree t5):
00061   rep (tm_new<compound_rep> (l, array<tree> (5)))
00062 {
00063   (static_cast<compound_rep*> (rep))->a[0]=t1;
00064   (static_cast<compound_rep*> (rep))->a[1]=t2;
00065   (static_cast<compound_rep*> (rep))->a[2]=t3;
00066   (static_cast<compound_rep*> (rep))->a[3]=t4;
00067   (static_cast<compound_rep*> (rep))->a[4]=t5;
00068 }
00069 
00070 tree::tree (tree_label l,
00071            tree t1, tree t2, tree t3, tree t4, tree t5, tree t6):
00072   rep (tm_new<compound_rep> (l, array<tree> (6)))
00073 {
00074   (static_cast<compound_rep*> (rep))->a[0]=t1;
00075   (static_cast<compound_rep*> (rep))->a[1]=t2;
00076   (static_cast<compound_rep*> (rep))->a[2]=t3;
00077   (static_cast<compound_rep*> (rep))->a[3]=t4;
00078   (static_cast<compound_rep*> (rep))->a[4]=t5;
00079   (static_cast<compound_rep*> (rep))->a[5]=t6;
00080 }
00081 
00082 tree::tree (tree_label l,
00083            tree t1, tree t2, tree t3, tree t4, tree t5, tree t6, tree t7):
00084   rep (tm_new<compound_rep> (l, array<tree> (7)))
00085 {
00086   (static_cast<compound_rep*> (rep))->a[0]=t1;
00087   (static_cast<compound_rep*> (rep))->a[1]=t2;
00088   (static_cast<compound_rep*> (rep))->a[2]=t3;
00089   (static_cast<compound_rep*> (rep))->a[3]=t4;
00090   (static_cast<compound_rep*> (rep))->a[4]=t5;
00091   (static_cast<compound_rep*> (rep))->a[5]=t6;
00092   (static_cast<compound_rep*> (rep))->a[6]=t7;
00093 }
00094 
00095 tree::tree (tree_label l,
00096            tree t1, tree t2, tree t3, tree t4,
00097            tree t5, tree t6, tree t7, tree t8):
00098   rep (tm_new<compound_rep> (l, array<tree> (8)))
00099 {
00100   (static_cast<compound_rep*> (rep))->a[0]=t1;
00101   (static_cast<compound_rep*> (rep))->a[1]=t2;
00102   (static_cast<compound_rep*> (rep))->a[2]=t3;
00103   (static_cast<compound_rep*> (rep))->a[3]=t4;
00104   (static_cast<compound_rep*> (rep))->a[4]=t5;
00105   (static_cast<compound_rep*> (rep))->a[5]=t6;
00106   (static_cast<compound_rep*> (rep))->a[6]=t7;
00107   (static_cast<compound_rep*> (rep))->a[7]=t8;
00108 }
00109 
00110 tree
00111 tree::operator () (int begin, int end) {
00112   int i;
00113   tree r (rep->op, end-begin);
00114   for (i=begin; i<end; i++)
00115     r[i-begin]= (static_cast<compound_rep*> (rep))->a[i];
00116   return r;
00117 }
00118 
00119 bool
00120 operator == (tree t, tree u) {
00121   return (L(t)==L(u)) &&
00122     (L(t)==STRING? (t->label==u->label): (A(t)==A(u)));
00123 }
00124 
00125 bool
00126 operator != (tree t, tree u) {
00127   return (L(t)!=L(u)) ||
00128     (L(t)==STRING? (t->label!=u->label): (A(t)!=A(u)));
00129 }
00130 
00131 tree
00132 copy (tree t) {
00133   if (is_atomic (t)) return tree (copy (t->label));
00134   else {
00135     int i, n= N(t);
00136     tree t2 (t, n);
00137     for (i=0; i<n; i++) t2[i]= copy (t[i]);
00138     return t2;
00139   }
00140 }
00141 
00142 tree
00143 freeze (tree t) {
00144   if (is_atomic (t)) return copy (t->label);
00145   if (is_func (t, UNFREEZE, 1)) return t[0];
00146   else {
00147     int i, n= N(t);
00148     tree r (t, n);
00149     for (i=0; i<n; i++)
00150       r[i]= freeze (t[i]);
00151     return r;
00152   }
00153 }
00154 
00155 tree
00156 operator * (tree t1, tree t2) {
00157   int i;
00158   if (is_atomic (t1)) t1= tree (L(t2), t1);
00159   if (is_atomic (t2)) t2= tree (L(t1), t2);
00160   tree r (t1, N(t1)+N(t2));
00161   for (i=0; i<N(t1); i++) r[i]= t1[i];
00162   for (i=0; i<N(t2); i++) r[i+N(t1)]= t2[i];
00163   return r;
00164 }
00165 
00166 tree&
00167 operator << (tree& t, tree t2) {
00168   CHECK_COMPOUND (t);
00169   (static_cast<compound_rep*> (t.rep))->a << t2;
00170   return t;
00171 }
00172 
00173 tree&
00174 operator << (tree& t, array<tree> a) {
00175   CHECK_COMPOUND (t);
00176   (static_cast<compound_rep*> (t.rep))->a << a;
00177   return t;
00178 }
00179 
00180 tm_ostream&
00181 operator << (tm_ostream& out, tree t) {
00182   if (is_atomic (t)) return out << t->label;
00183   else if (is_compound (t)) {
00184     int i, n= N(t);
00185     out << as_string (L(t));
00186     if (n==0) return out << "()";
00187     out << " (";
00188     for (i=0; i< n-1; i++)
00189       out << t[i] << ", ";
00190     out << t[i] << ")";
00191     return out;
00192   }
00193   else out << as_blackbox (t);
00194   return out;
00195 }
00196 
00197 void
00198 print_tree (tree t, int tab) {
00199   int i;
00200   for (i=0; i<tab; i++) cout << " ";
00201   if (is_atomic (t)) cout << t->label << "\n";
00202   else {
00203     cout << as_string (L(t)) << "\n";
00204     for (i=0; i<N(t); i++) print_tree (t[i], tab+2);
00205   }
00206 }
00207 
00208 int
00209 hash (array<tree> a) {
00210   register int i, h=0, n=N(a);
00211   for (i=0; i<n; i++) {
00212     h=(h<<7) + (h>>25);
00213     h=h + hash(a[i]);
00214   }
00215   return h;
00216 }
00217 
00218 int
00219 hash (tree t) {
00220   if (is_atomic (t)) return hash (t->label);
00221   else return ((int) L(t)) ^ hash (A(t));
00222 }
00223 
00224 string
00225 tree_as_string (tree t) {
00226   if (is_atomic (t)) return t->label;
00227   else if (is_concat (t) || is_document (t)) {
00228     int i, n= N(t);
00229     string cumul;
00230     for (i=0; i<n; i++)
00231       cumul << tree_as_string (t[i]);
00232     return cumul;
00233   }
00234   else if (is_func (t, WITH))
00235     return tree_as_string (t[N(t)-1]);
00236   else if (is_compound (t, "nbsp", 0))
00237     return " ";
00238   return "";
00239 }
00240 
00241 /******************************************************************************
00242 * Tree predicates
00243 ******************************************************************************/
00244 
00245 bool
00246 is_document (tree t) {
00247   return L(t) == DOCUMENT;
00248 }
00249 
00250 bool
00251 is_concat (tree t) {
00252   return L(t) == CONCAT;
00253 }
00254 
00255 bool
00256 is_format (tree t) {
00257   return is_document (t) || is_concat (t);
00258 }
00259 
00260 bool
00261 is_formatting (tree t) {
00262   return (L(t)>=WITH_LIMITS) && (L(t)<=NEW_DPAGE);
00263 }
00264 
00265 bool
00266 is_table (tree t) {
00267   return
00268     is_func (t, TABLE) || is_func (t, SUBTABLE) ||
00269     is_func (t, ROW) || is_func (t, CELL);
00270 }
00271 
00272 bool
00273 is_table_format (tree t) {
00274   return is_func (t, TFORMAT);
00275 }
00276 
00277 bool
00278 is_multi_paragraph (tree t) {
00279   switch (L(t)) {
00280   case DOCUMENT:
00281     return true;
00282   case SURROUND:
00283     return is_multi_paragraph (t[2]);
00284   case DATOMS:
00285   case DLINES:
00286   case DPAGES:
00287   case WITH:
00288   case MARK:
00289   case EXPAND_AS:
00290   case STYLE_WITH:
00291   case VAR_STYLE_WITH:
00292   case STYLE_ONLY:
00293   case VAR_STYLE_ONLY:
00294   case ACTIVE:
00295   case VAR_ACTIVE:
00296     return is_multi_paragraph (t[N(t)-1]);
00297   case INCLUDE:
00298     return true;
00299   case LOCUS:
00300   case CANVAS:
00301     return is_multi_paragraph (t[N(t)-1]);
00302   default:
00303     {
00304       static hashset<tree_label> inline_set; // FIXME: use drd
00305       if (N(inline_set) == 0) {
00306        inline_set->insert (make_tree_label ("footnote"));
00307        inline_set->insert (make_tree_label ("script-input"));
00308        inline_set->insert (make_tree_label ("converter-input"));
00309       }
00310       if (L(t) < START_EXTENSIONS) return false;
00311       else if (inline_set->contains (L(t))) return false;
00312       else {
00313        int i, n= N(t);
00314        for (i=0; i<n; i++)
00315          if (is_multi_paragraph (t[i]))
00316            return true;
00317        return false;
00318       }
00319     }
00320   }
00321 }
00322 
00323 bool
00324 is_around (tree t) {
00325   return is_func (t, AROUND, 3) || is_func (t, VAR_AROUND, 3);
00326 }
00327 
00328 bool
00329 is_script (tree t) {
00330   return
00331     is_func (t, LSUB) || is_func (t, LSUP) ||
00332     is_func (t, RSUB) || is_func (t, RSUP);
00333 }
00334 
00335 bool
00336 is_script (tree t, bool& right) {
00337   if (is_func (t, LSUB) ||
00338       is_func (t, LSUP)) { right=false; return true; }
00339   if (is_func (t, RSUB) ||
00340       is_func (t, RSUP)) { right=true; return true; }
00341   return false;
00342 }
00343 
00344 bool
00345 is_prime (tree t) {
00346   return ((L(t) == LPRIME) || (L(t) == RPRIME)) && (N(t) == 1);
00347 }
00348 
00349 bool
00350 is_right_script_prime (tree t) {
00351   return is_func (t, RSUB, 1) || is_func (t, RSUP, 1) ||
00352          is_func (t, RPRIME, 1);
00353 }
00354 
00355 bool
00356 is_mod_active (tree t) {
00357   return (N(t) == 1) && (L(t) >= STYLE_ONLY) && (L(t) <= VAR_INACTIVE);
00358 }
00359 
00360 bool
00361 is_mod_active_once (tree t) {
00362   return (N(t) == 1) &&
00363     ((L(t) == STYLE_ONLY) || (L(t) == ACTIVE) || (L(t) == INACTIVE));
00364 }
00365 
00366 bool
00367 is_graphical_text (tree t) {
00368   return is_func (t, TEXT_AT) || is_func (t, MATH_AT);
00369 }
00370 
00371 bool
00372 is_empty (tree t) {
00373   if (is_atomic (t)) return (t == "");
00374   if (is_document (t) || is_concat (t)) {
00375     int i, n= N(t);
00376     for (i=0; i<n; i++)
00377       if (!is_empty (t[i])) return false;
00378     return is_concat (t) || (n<=1);
00379   }
00380   return false;
00381 }
00382 
00383 /******************************************************************************
00384 * Compound trees
00385 ******************************************************************************/
00386 
00387 tree
00388 compound (string s) {
00389   return tree (make_tree_label (s));
00390 }
00391 
00392 tree
00393 compound (string s, tree t1) {
00394   return tree (make_tree_label (s), t1);
00395 }
00396 
00397 tree
00398 compound (string s, tree t1, tree t2) {
00399   return tree (make_tree_label (s), t1, t2);
00400 }
00401 
00402 tree
00403 compound (string s, tree t1, tree t2, tree t3) {
00404   return tree (make_tree_label (s), t1, t2, t3);
00405 }
00406 
00407 tree
00408 compound (string s, tree t1, tree t2, tree t3, tree t4) {
00409   return tree (make_tree_label (s), t1, t2, t3, t4);
00410 }
00411 
00412 tree
00413 compound (string s, array<tree> a) {
00414   return tree (make_tree_label (s), a);
00415 }
00416 
00417 bool
00418 is_extension(tree_label l) {
00419   return l >= START_EXTENSIONS;
00420 }
00421 
00422 bool
00423 is_extension (tree t) {
00424   return L(t) >= START_EXTENSIONS;
00425 }
00426 
00427 bool
00428 is_extension (tree t, int n) {
00429   return (L(t) >= START_EXTENSIONS) && (N(t) == n);
00430 }
00431 
00432 bool
00433 is_compound (tree t, string s) {
00434   return as_string (L(t)) == s;
00435 }
00436 
00437 bool
00438 is_compound (tree t, string s, int n) {
00439   return (as_string (L(t)) == s) && (N(t) == n);
00440 }
00441 
00442 /******************************************************************************
00443 * Routines for simplification and correction
00444 ******************************************************************************/
00445 
00446 static void
00447 simplify_concat (tree& r, tree t) {
00448   int i, n= N(t);
00449   for (i=0; i<n; i++)
00450     if (is_concat (t[i])) simplify_concat (r, t[i]);
00451     else if (t[i] == "");
00452     else if (is_atomic (t[i]) && (N(r)>0) && is_atomic (r[N(r)-1]))
00453       r[N(r)-1]= tree (r[N(r)-1]->label * t[i]->label);
00454     else r << t[i];
00455 }
00456 
00457 tree
00458 simplify_concat (tree t) {
00459   tree r (CONCAT);
00460   simplify_concat (r, t);
00461   if (N(r) == 0) return "";
00462   if (N(r) == 1) return r[0];
00463   return r;
00464 }
00465 
00466 tree
00467 simplify_correct (tree t) {
00468   if (is_atomic (t)) return t;
00469   if (is_func (t, QUOTE, 1) && (is_atomic (t[0]))) return t[0];
00470   int i, n= N(t);
00471   tree r (t, n);
00472   for (i=0; i<n; i++)
00473     r[i]= simplify_correct (t[i]);
00474   if (is_concat (r)) r= simplify_concat (r);
00475   return r;
00476 }