Back to index

texmacs  1.0.7.15
tree_traverse.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : tree_traverse.cpp
00004 * DESCRIPTION: abstract cursor movement and tree traversal
00005 * COPYRIGHT  : (C) 2005  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 "tree_traverse.hpp"
00013 #include "drd_std.hpp"
00014 #include "analyze.hpp"
00015 #include "hashset.hpp"
00016 #include "scheme.hpp"
00017 
00018 /******************************************************************************
00019 * Accessability
00020 ******************************************************************************/
00021 
00022 int
00023 minimal_arity (tree t) {
00024   return the_drd->get_minimal_arity (L(t));
00025 }
00026 
00027 int
00028 maximal_arity (tree t) {
00029   return the_drd->get_maximal_arity (L(t));
00030 }
00031 
00032 bool
00033 correct_arity (tree t, int n) {
00034   return the_drd->correct_arity (L(t), n);
00035 }
00036 
00037 int
00038 insert_point (tree t, int i) {
00039   return the_drd->insert_point (L(t), i, N(t));
00040 }
00041 
00042 bool
00043 is_dynamic (tree t) {
00044   return the_drd->is_dynamic (t, false);
00045 }
00046 
00047 bool
00048 is_accessible_child (tree t, int i) {
00049   return the_drd->is_accessible_child (t, i);
00050 }
00051 
00052 array<tree>
00053 accessible_children (tree t) {
00054   array<tree> a;
00055   int i, n= N(t);
00056   for (i=0; i<n; i++)
00057     if (the_drd->is_accessible_child (t, i))
00058       a << t[i];
00059   return a;
00060 }
00061 
00062 bool
00063 all_accessible (tree t) {
00064   if (is_atomic (t)) return false;
00065   return the_drd->all_accessible (L(t));
00066 }
00067 
00068 bool
00069 none_accessible (tree t) {
00070   if (is_atomic (t)) return false;
00071   return the_drd->none_accessible (L(t));
00072 }
00073 
00074 /******************************************************************************
00075 * Further properties
00076 ******************************************************************************/
00077 
00078 string
00079 get_name (tree t) {
00080   return the_drd->get_name (L(t));
00081 }
00082 
00083 string
00084 get_long_name (tree t) {
00085   return the_drd->get_long_name (L(t));
00086 }
00087 
00088 string
00089 get_child_name (tree t, int i) {
00090   return the_drd->get_child_name (t, i);
00091 }
00092 
00093 string
00094 get_child_long_name (tree t, int i) {
00095   return the_drd->get_child_long_name (t, i);
00096 }
00097 
00098 string
00099 get_child_type (tree t, int i) {
00100   return drd_decode_type (the_drd->get_type_child (t, i));
00101 }
00102 
00103 tree
00104 get_env_child (tree t, int i, string var, tree val) {
00105   return the_drd->get_env_child (t, i, var, val);
00106 }
00107 
00108 /******************************************************************************
00109 * Traversal of a tree
00110 ******************************************************************************/
00111 
00112 static path
00113 move_any (tree t, path p, bool forward) {
00114   path q = path_up (p);
00115   int  l = last_item (p);
00116   tree st= subtree (t, q);
00117   if (is_atomic (st)) {
00118     string s= st->label;
00119     ASSERT (l >= 0 && l <= N(s), "out of range");
00120     if (forward) {
00121       if (l<N(s)) {
00122        tm_char_forwards (s, l);
00123        return q * l;
00124       }
00125     }
00126     else {
00127       if (l>0) {
00128        tm_char_backwards (s, l);
00129        return q * l;
00130       }
00131     }
00132   }
00133   else if ((forward && l==0) || (!forward && l==1)) {
00134     int i, n= N(st);
00135     if (forward) {
00136       for (i=0; i<n; i++)
00137        if (the_drd->is_accessible_child (st, i))
00138          return q * path (i, 0);
00139     }
00140     else {
00141       for (i=n-1; i>=0; i--)
00142        if (the_drd->is_accessible_child (st, i))
00143          return q * path (i, right_index (st[i]));
00144     }
00145     return q * (1-l);
00146   }
00147   else if (is_nil (q)) return p;
00148 
00149   l = last_item (q);
00150   q = path_up (q);
00151   st= subtree (t, q);
00152   int i, n= N(st);
00153   if (forward) {
00154     for (i=l+1; i<n; i++)
00155       if (the_drd->is_accessible_child (st, i))
00156        return q * path (i, 0);
00157   }
00158   else {
00159     for (i=l-1; i>=0; i--)
00160       if (the_drd->is_accessible_child (st, i)) {
00161        return q * path (i, right_index (st[i]));
00162     }
00163   }
00164   return q * (forward? 1: 0);
00165 }
00166 
00167 path next_any (tree t, path p) {
00168   return move_any (t, p, true); }
00169 path previous_any (tree t, path p) {
00170   return move_any (t, p, false); }
00171 
00172 /******************************************************************************
00173 * Traversal of a valid cursor positions inside a tree
00174 ******************************************************************************/
00175 
00176 static path
00177 move_valid (tree t, path p, bool forward) {
00178   ASSERT (is_inside (t, p), "invalid cursor");
00179   path q= p;
00180   while (true) {
00181     path r= move_any (t, q, forward);
00182     if (r == q) return p;
00183     if (valid_cursor (t, r)) return r;
00184     q= r;
00185   }
00186 }
00187 
00188 path next_valid (tree t, path p) {
00189   return move_valid (t, p, true); }
00190 path previous_valid (tree t, path p) {
00191   return move_valid (t, p, false); }
00192 
00193 static path
00194 move_accessible (tree t, path p, bool forward) {
00195   ASSERT (is_inside (t, p), "invalid cursor");
00196   path q= p;
00197   while (true) {
00198     path r= move_any (t, q, forward);
00199     if (r == q) return p;
00200     if (is_accessible_cursor (t, r)) return r;
00201     q= r;
00202   }
00203 }
00204 
00205 path next_accessible (tree t, path p) {
00206   return move_accessible (t, p, true); }
00207 path previous_accessible (tree t, path p) {
00208   return move_accessible (t, p, false); }
00209 
00210 /******************************************************************************
00211 * Word based traversal of a tree
00212 ******************************************************************************/
00213 
00214 static inline bool
00215 is_iso_alphanum (char c) {
00216   return is_iso_alpha (c) || is_digit (c);
00217 }
00218 
00219 static bool
00220 at_border (tree t, path p, bool forward) {
00221   tree st= subtree (t, path_up (p));
00222   int l= last_item (p), n= N(st);
00223   if (!is_concat (st) && !is_document (st)) return true;
00224   if ((forward && l!=n-1) || (!forward && l!=0)) return false;
00225   return at_border (t, path_up (p), forward);
00226 }
00227 
00228 static bool
00229 next_is_word (tree t, path p) {
00230   tree st= subtree (t, path_up (p));
00231   int l= last_item (p), n= N(st);
00232   if (!is_concat (st) || l+1 >= n) return false;
00233   if (is_compound (st[l+1])) return true;
00234   return st[l+1] != "" && is_iso_alphanum (st[l+1]->label[0]);
00235 }
00236 
00237 static path
00238 move_word (tree t, path p, bool forward) {
00239   while (true) {
00240     path q= move_valid (t, p, forward);
00241     int l= last_item (q);
00242     if (q == p) return p;
00243     tree st= subtree (t, path_up (q));
00244     if (is_atomic (st)) {
00245       string s= st->label;
00246       int n= N(s);
00247       if (s == "") return q;
00248       if (forward && l>0 &&
00249          (is_iso_alphanum (s[l-1]) ||
00250           (l==n && at_border (t, path_up (q), forward))) &&
00251          (l==n || !is_iso_alphanum (s[l])))
00252        return q;
00253       if (!forward && l<n &&
00254          (is_iso_alphanum (s[l]) ||
00255           (l==0 && at_border (t, path_up (q), forward))) &&
00256          (l==0 || !is_iso_alphanum (s[l-1])))
00257        return q;
00258       if (!forward && l==n && next_is_word (t, path_up (q)))
00259        return q;
00260     }
00261     else {
00262       if (forward && l==1) return q;
00263       if (!forward && l==0) return q;
00264       if (!forward && next_is_word (t, path_up (q)))
00265        return q;
00266     }
00267     p= q;
00268   }
00269 }
00270 
00271 path next_word (tree t, path p) {
00272   return move_word (t, p, true); }
00273 path previous_word (tree t, path p) {
00274   return move_word (t, p, false); }
00275 
00276 /******************************************************************************
00277 * Node based traversal of a tree
00278 ******************************************************************************/
00279 
00280 static path
00281 move_node (tree t, path p, bool forward) {
00282   tree st= subtree (t, path_up (p));
00283   if (is_atomic (st)) {
00284     if (forward) p= path_up (p) * N (st->label);
00285     else p= path_up (p) * 0;
00286   }
00287   return move_valid (t, p, forward);
00288 }
00289 
00290 path next_node (tree t, path p) {
00291   return move_node (t, p, true); }
00292 path previous_node (tree t, path p) {
00293   return move_node (t, p, false); }
00294 
00295 /******************************************************************************
00296 * Tag based traversal of a tree
00297 ******************************************************************************/
00298 
00299 static int
00300 tag_border (tree t, path p) {
00301   if (none_accessible (subtree (t, path_up (p)))) {
00302     if (last_item (p) == 0) return -1;
00303     if (last_item (p) == 1) return 1;
00304   }
00305   return 0;
00306 }
00307 
00308 static bool
00309 distinct_tag_or_argument (tree t, path p, path q, hashset<int> labs) {
00310   path c= common (p, q);
00311   path r= path_up (q);
00312   if (labs->contains ((int) L (subtree (t, r))) && tag_border (t, q) != 0)
00313     return true;
00314   while (!is_nil (r) && (r != c)) {
00315     r= path_up (r);
00316     if (labs->contains ((int) L (subtree (t, r)))) return true;
00317   }
00318   return false;
00319 }
00320 
00321 static bool
00322 acceptable_border (tree t, path p, path q, hashset<int> labs) {
00323   if (tag_border (t, q) == 0) return true;
00324   if (!labs->contains ((int) L (subtree (t, path_up (q))))) return true;
00325   if (tag_border (t, q) < 0) return false;
00326   return tag_border (t, p) != 0;
00327 }
00328 
00329 static int
00330 tag_index (tree t, path p, hashset<int> labs) {
00331   p= path_up (p);
00332   while (!is_nil (p)) {
00333     if (labs->contains ((int) L (subtree (t, path_up (p)))))
00334       return last_item (p);
00335     else p= path_up (p);
00336   }
00337   return -1;
00338 }
00339 
00340 static path
00341 move_tag (tree t, path p, hashset<int> labs, bool forward, bool preserve) {
00342   path q= p;
00343   while (true) {
00344     path r= move_node (t, q, forward);
00345     if (r == q) return p;
00346     if (distinct_tag_or_argument (t, p, r, labs) &&
00347         acceptable_border (t, p, r, labs) &&
00348        (!preserve || tag_index (t, r, labs) == tag_index (t, p, labs)))
00349       return r;
00350     q= r;
00351   }
00352 }
00353 
00354 static hashset<int>
00355 get_labels (scheme_tree t) {
00356   hashset<int> labs;
00357   if (is_atomic (t))
00358     labs->insert ((int) as_tree_label (t->label));
00359   else {
00360     int i, n= N(t);
00361     for (i=0; i<n; i++)
00362       if (is_atomic (t[i]))
00363        labs->insert ((int) as_tree_label (t[i]->label));
00364   }
00365   return labs;
00366 }
00367 
00368 path next_tag (tree t, path p, scheme_tree which) {
00369   return move_tag (t, p, get_labels (which), true, false); }
00370 path previous_tag (tree t, path p, scheme_tree which) {
00371   return move_tag (t, p, get_labels (which), false, false); }
00372 
00373 path next_tag_same_argument (tree t, path p, scheme_tree which) {
00374   return move_tag (t, p, get_labels (which), true, true); }
00375 path previous_tag_same_argument (tree t, path p, scheme_tree which) {
00376   return move_tag (t, p, get_labels (which), false, true); }
00377 
00378 /******************************************************************************
00379 * Traverse the children of a node
00380 ******************************************************************************/
00381 
00382 static path
00383 move_argument (tree t, path p, bool forward) {
00384   path q = path_up (p);
00385   int  l = last_item (p);
00386   tree st= subtree (t, q);
00387   int i, n= N(st);
00388   if (forward) {
00389     for (i=l+1; i<n; i++)
00390       if (the_drd->is_accessible_child (st, i))
00391        return start (t, q * i);
00392   }
00393   else {
00394     for (i=l-1; i>=0; i--)
00395       if (the_drd->is_accessible_child (st, i))
00396        return end (t, q * i);
00397   }
00398   return path ();
00399 }
00400 
00401 path next_argument (tree t, path p) {
00402   return move_argument (t, p, true); }
00403 path previous_argument (tree t, path p) {
00404   return move_argument (t, p, false); }
00405 
00406 /******************************************************************************
00407 * Other routines
00408 ******************************************************************************/
00409 
00410 static path
00411 search_upwards (tree t, path p, tree_label which) {
00412   if (is_nil (p) || L (subtree (t, p)) == which) return p;
00413   else return search_upwards (t, path_up (p), which);
00414 }
00415 
00416 bool
00417 inside_same (tree t, path p, path q, tree_label which) {
00418   return
00419     search_upwards (t, path_up (p), which) ==
00420     search_upwards (t, path_up (q), which);
00421 }
00422 
00423 bool
00424 more_inside (tree t, path p, path q, tree_label which) {
00425   return
00426     search_upwards (t, path_up (q), which) <=
00427     search_upwards (t, path_up (p), which);
00428 }
00429 
00430 /******************************************************************************
00431 * Find sections in document
00432 ******************************************************************************/
00433 
00434 hashset<tree_label> section_traverse_tags;
00435 hashset<tree_label> section_tags;
00436 
00437 void
00438 init_sections () {
00439   if (N(section_traverse_tags) == 0) {
00440     section_traverse_tags= hashset<tree_label> ();
00441     section_traverse_tags->insert (DOCUMENT);
00442     section_traverse_tags->insert (CONCAT);
00443     section_traverse_tags->insert (as_tree_label ("ignore"));
00444     section_traverse_tags->insert (as_tree_label ("show-part"));
00445     section_traverse_tags->insert (as_tree_label ("hide-part"));
00446   }
00447   if (N(section_tags) == 0) {
00448     eval ("(use-modules (text std-text-drd))");
00449     object l= eval ("(append (section-tag-list) (section*-tag-list))");
00450     while (!is_null (l)) {
00451       section_tags->insert (as_tree_label (as_symbol (car (l))));
00452       l= cdr (l);
00453     }
00454   }
00455 }
00456 
00457 path
00458 previous_section_impl (tree t, path p) {
00459   if (is_atomic (t)) return path ();
00460   else if (N(t) == 1 && section_tags->contains (L(t)))
00461     return p * 0;
00462   else if (section_traverse_tags->contains (L(t))) {
00463     int i= is_nil (p)? N(t)-1: p->item;
00464     for (; i>=0; i--) {
00465       if (!is_nil (p) && i == p->item) {
00466        path r= previous_section_impl (t[i], p->next);
00467        if (!is_nil (r)) return path (i, r);
00468       }
00469       else {
00470        path r= previous_section_impl (t[i], path ());
00471        if (!is_nil (r)) return path (i, r);
00472       }
00473     }
00474   }
00475   return path ();
00476 }
00477 
00478 path
00479 previous_section (tree t, path p) {
00480   init_sections ();
00481   path r= previous_section_impl (t, p);
00482   if (is_nil (r)) return p;
00483   return path_up (r);
00484 }
00485 
00486 void
00487 search_sections (array<tree>& a, tree t) {
00488   if (is_atomic (t)) return;
00489   else if (N(t) == 1 && section_tags->contains (L(t))) a << t;
00490   else if (section_traverse_tags->contains (L(t)))
00491     for (int i=0; i<N(t); i++)
00492       search_sections (a, t[i]);
00493 }
00494 
00495 array<tree>
00496 search_sections (tree t) {
00497   init_sections ();
00498   array<tree> a;
00499   search_sections (a, t);
00500   return a;
00501 }