Back to index

texmacs  1.0.7.15
tree_cursor.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : tree_cursor.cpp
00004 * DESCRIPTION: abstract cursor handling
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 "tree_cursor.hpp"
00013 #include "drd_std.hpp"
00014 #include "drd_mode.hpp"
00015 #include "analyze.hpp"
00016 #include "vars.hpp"
00017 
00018 /******************************************************************************
00019 * Finding a closest cursor inside a tree
00020 ******************************************************************************/
00021 
00022 bool
00023 is_inside (tree t, path p) {
00024   if (is_nil (p)) return false;
00025   else if (is_atomic (t)) {
00026     string s= t->label;
00027     int i, n= N(s), k= p->item;
00028     if (!is_atom (p) || k<0 || k>n) return false;
00029     for (i=0; i<k; tm_char_forwards (s, i)) {}
00030     return i == k;
00031   }
00032   else if (is_atom (p)) return p->item == 0 || p->item == 1;
00033   else return p->item >= 0 && p->item < N(t) &&
00034              is_inside (t[p->item], p->next);
00035 }
00036 
00037 path
00038 closest_inside (tree t, path p) {
00039   // Arbitrary paths may be outside the tree.
00040   // This routine returns a closest path to p inside the tree t
00041   if (is_nil (p)) return path (0);
00042   else if (is_atomic (t)) {
00043     string s= t->label;
00044     int i, n= N(s), k= max (0, min (n, p->item));
00045     for (i=0; i<k; tm_char_forwards (s, i)) {}
00046     return i;
00047   }
00048   else if (is_atom (p) || p->item < 0 || p->item >= N(t))
00049     return path (max (0, min (1, p->item)));
00050   else return path (p->item, closest_inside (t[p->item], p->next));
00051 }
00052 
00053 static bool
00054 is_modified_accessible (tree t, path p, bool activate, bool persistent) {
00055   if (p->item != 0) return false;
00056   t= t[0]; p= p->next;
00057   if (is_atomic (t)) return is_accessible_cursor (t, p);
00058   else if (is_atom (p) && !persistent) return false;
00059   else {
00060     bool r;
00061     int old= set_access_mode (activate? DRD_ACCESS_NORMAL: DRD_ACCESS_SOURCE);
00062     if (persistent) r= is_accessible_cursor (t, p);
00063     else r= the_drd->is_accessible_child (t, p->item);
00064     set_access_mode (old);
00065     if (!persistent) r= r && is_accessible_cursor (t[p->item], p->next);
00066     return r;
00067   }
00068 }
00069 
00070 static bool
00071 next_without_border (tree t, path p) {
00072   return false;
00073   // Assuming that t is a concat, check whether p does not correspond
00074   // to an inaccessible border position
00075   int i= p->item + 1;
00076   if (i >= N(t)) return false;
00077   if (is_compound (t[i]) && the_drd->is_child_enforcing (t[i]))
00078     return p->next == end (t[p->item]);
00079   return false;
00080 }
00081 
00082 bool
00083 is_accessible_cursor (tree t, path p) {
00084   if (is_atomic (t) || is_atom (p)) {
00085     if (get_writable_mode () == DRD_WRITABLE_INPUT &&
00086        get_access_mode () != DRD_ACCESS_SOURCE)
00087       return false;
00088     else if (is_atomic (t))
00089       return is_atom (p) && p->item >= 0 && p->item <= N(t->label);
00090     else return !the_drd->is_child_enforcing (t);
00091   }
00092   else if (0 > p->item || p->item >= N(t)) return false;
00093   else if (the_drd->is_parent_enforcing (t) &&
00094           ((p->item == 0 && p->next == start (t[0])) ||
00095            (p->item == N(t)-1 && p->next == end (t[p->item]))))
00096     return false;
00097   else switch (L(t)) {
00098     case CONCAT:
00099       if (!is_accessible_cursor (t[p->item], p->next)) return false;
00100       else return !next_without_border (t, p);
00101     case ACTIVE:
00102       return is_modified_accessible (t, p, true, false);
00103     case VAR_ACTIVE:
00104       return is_modified_accessible (t, p, true, true);
00105     case INACTIVE:
00106       return is_modified_accessible (t, p, false, false);
00107     case VAR_INACTIVE:
00108       return is_modified_accessible (t, p, false, true);
00109     default:
00110       if (!the_drd->is_accessible_child (t, p->item)) return false;
00111       else if (the_drd->get_env_child (t, p->item, MODE, "") == "src") {
00112        int old_mode= set_access_mode (DRD_ACCESS_SOURCE);
00113        bool r= is_accessible_cursor (t[p->item], p->next);
00114        set_access_mode (old_mode);
00115        return r;
00116       }
00117       else {
00118        int old_mode= get_writable_mode ();
00119        if (old_mode != DRD_WRITABLE_ANY) {
00120          int w  = the_drd->get_writability_child (t, p->item);
00121          if (w == WRITABILITY_DISABLE)
00122            set_writable_mode (DRD_WRITABLE_INPUT);
00123          else if (w == WRITABILITY_ENABLE)
00124            set_writable_mode (DRD_WRITABLE_NORMAL);
00125        }
00126        bool r= is_accessible_cursor (t[p->item], p->next);
00127        set_writable_mode (old_mode);
00128        return r;
00129       }
00130     }
00131 }
00132 
00133 path
00134 closest_accessible (tree t, path p) {
00135   // Given a path p inside t, the path may be unaccessible
00136   // This routine returns the closest path to p inside t which is accessible
00137   // The routine returns nil if there exists no accessible path inside t
00138   if (is_atomic (t)) return p;
00139   else if (is_atom (p) && !the_drd->is_child_enforcing (t)) return p;
00140   else {
00141     int i, k= p->item, n= N(t);
00142     if (p == 1) k= max (0, n-1);
00143     for (i=0; i<n; i++) {
00144       int j= ((i&1) == 0? (k+(i>>1) % n): (k+n-((i+1)>>1) % n));
00145       if (the_drd->is_accessible_child (t, j)) {
00146        // FIXME: certain tags modify source accessability props
00147        // FIXME: cells with non-trivial span may lead to unaccessability
00148        // FIXME: very dynamic markup should be treated after typesetting
00149        if (is_atom (p) && is_atomic (t[j]))
00150          return path (j, p->item * (j < k? N (t[j]->label): 0));
00151        path sp= (is_atom (p)? (j < k? path (1): path (0)): p->next);
00152        path r= closest_accessible (t[j], sp);
00153        if (!is_nil (r)) {
00154          r= path (j, r);
00155          if (!is_concat (t) || !next_without_border (t, r)) {
00156            if (the_drd->is_parent_enforcing (t)) {
00157              if (r->item == 0 && r->next == start (t[0]))
00158               return path (0);
00159              if (r->item == N(t)-1 && r->next == end (t[r->item]))
00160               return path (1);         
00161            }
00162            return r;
00163          }
00164        }
00165       }
00166     }
00167     return path ();
00168   }
00169 }
00170 
00171 /******************************************************************************
00172 * Shifting the cursor
00173 ******************************************************************************/
00174 
00175 bool
00176 is_shifted (tree t, path p, int dir= -1, bool flag= false) {
00177   if (dir == 0) return true;
00178   else if (is_atom (p)) {
00179     if (flag) {
00180       if (dir < 0) return p->item != 0;
00181       else return p->item != right_index (t);
00182     }
00183     else return true;
00184   }
00185   else if (is_concat (t)) {
00186     int  i    = p->item;
00187     bool sflag= flag || (dir<0? i>0: i<N(t)-1);
00188     return is_shifted (t[i], p->next, dir, sflag);
00189   }
00190   else return is_shifted (t[p->item], p->next, dir, false);
00191 }
00192 
00193 static path
00194 extreme (tree t, int dir) {
00195   if (dir < 0) return start (t);
00196   else return end (t);
00197 }
00198 
00199 path
00200 shift (tree t, path p, int dir) {
00201   if (dir == 0 || is_nil (p) || is_atom (p)) return p;
00202   else if (is_concat (t) && p->next == extreme (t[p->item], dir)) {
00203     for (int i= p->item + dir; i >= 0 && i < N(t); i += dir)
00204       if (the_drd -> is_accessible_child (t, i))
00205        return path (i, extreme (t[i], -dir));
00206     return p;
00207   }
00208   else return path (p->item, shift (t[p->item], p->next, dir));
00209 }
00210 
00211 /******************************************************************************
00212 * Subroutines for cursor paths in trees
00213 ******************************************************************************/
00214 
00215 bool
00216 valid_cursor (tree t, path p, bool start_flag) {
00217   if ((!is_nil (p)) && (!is_atom (p)) &&
00218       ((p->item < 0) || (p->item >= arity (t)))) {
00219     cerr << "TeXmacs] testing valid cursor " << p << " in " << t << "\n";
00220     FAILED ("bad path");
00221   }
00222 
00223   if (is_nil (p)) return false;
00224   if (is_atom (p)) {
00225     if (the_drd->is_child_enforcing (t)) return false;
00226     if (start_flag) return (p->item!=0);
00227     return true;
00228   }
00229   if (the_drd->is_parent_enforcing (t))
00230     if ((p->item == 0 && p->next == start (t[0])) ||
00231        (p->item == N(t)-1 && p->next == end (t[p->item])))
00232       return false;
00233   if (is_concat (t)) {
00234     if (next_without_border (t, p)) return false;
00235     return valid_cursor (t[p->item], p->next, start_flag || (p->item!=0));
00236   }
00237   if (is_mod_active_once (t))
00238     return is_atomic (t[0]) || (!is_atom (p->next));
00239   if (is_prime (t)) return false;
00240   // FIXME: hack for treating VAR_EXPAND "math"
00241   if (is_compound (t, "input", 2) && (N(p) == 2) &&
00242       is_compound (t[1], "math", 1) && (p->item == 1))
00243     return false;
00244   if (is_func (t, BIG_AROUND) && p->item == 1) {
00245     if (p == path (1, 0) && is_right_script_prime (t[1])) return false;
00246     if (p == path (1, 0, 0) && is_concat (t[1]) &&
00247         N(t[1]) > 0 && is_right_script_prime (t[1][0])) return false;
00248   }
00249   return valid_cursor (t[p->item], p->next, false);
00250 }
00251 
00252 static path
00253 pre_correct (tree t, path p) {
00254   //cout << "Precorrect " << p << " in " << t << "\n";
00255   if ((!is_nil (p)) && (!is_atom (p)) && ((p->item < 0) || (p->item >= arity (t)))) {
00256     cerr << "TeXmacs] precorrecting " << p << " in " << t << "\n";
00257     FAILED ("bad path");
00258   }
00259 
00260   if (is_nil (p)) return pre_correct (t, path(0));
00261   if (is_atom (p)) {
00262     if (!is_atomic (t) && the_drd->is_child_enforcing (t)) {
00263       if (p->item == 0) {
00264         for (int i=0; i<N(t); i++)
00265           if (i == N(t)-1 || the_drd->is_accessible_child (t, i))
00266             return path (i, pre_correct (t[i], path (0)));
00267       }
00268       else {
00269         for (int i=N(t)-1; i>=0; i--)
00270           if (i == 0 || the_drd->is_accessible_child (t, i))
00271             return path (i, pre_correct (t[i], path (right_index (t[i]))));
00272       }
00273       FAILED ("nullary tree with no border");
00274     }
00275     return p;
00276   }
00277   if (is_mod_active_once (t) && is_compound (t[0]) && is_atom (p->next)) {
00278     if (N (t[0]) == 0) return path (0);
00279     t= t[0]; p= p->next;
00280     if (p->item==0) return path (0, path (0, pre_correct (t[0], path (0))));
00281     else {
00282       int l=N(t)-1;
00283       return path (0, path (l, pre_correct (t[l], path (right_index (t[l])))));
00284     }
00285   }
00286   if (is_prime (t)) {
00287     if (p->next->item == 0) return path (0);
00288     else return path (1);
00289   }
00290   // FIXME: hack for treating VAR_EXPAND "math"
00291   if (is_compound (t, "input", 2) && (N(p) == 2) &&
00292       is_compound (t[1], "math", 1) && (p->item == 1))
00293     {
00294       int i= (p->next->item == 0? 0: right_index (t[1][0]));
00295       return path (1, 0, pre_correct (t[1][0], path (i)));
00296     }
00297   path r (p->item, pre_correct (t[p->item], p->next));
00298   if (the_drd->is_parent_enforcing (t)) {
00299     if (r->item == 0 && r->next == start (t[0])) return path (0);
00300     if (r->item == N(t)-1 && r->next == end (t[r->item])) return path (1);
00301   }
00302   return r;
00303 }
00304 
00305 static bool
00306 left_most (tree t, path p) {
00307   if (is_nil (p)) FAILED ("invalid nil path");
00308   if ((!is_atom (p)) && ((p->item < 0) || (p->item >= arity (t)))) {
00309     cerr << "TeXmacs] left most " << p << " in " << t << "\n";
00310     FAILED ("bad path");
00311   }
00312 
00313   int i=p->item;
00314   if (is_atom (p)) return i==0;
00315   if (is_concat (p)) return (i==0) && left_most (t[0], p->next);
00316   return false;
00317 }
00318 
00319 static path
00320 left_correct (tree t, path p) {
00321   //cout << "Left correct " << p << " in " << t << "\n";
00322   if (is_nil (p)) FAILED ("invalid nil path");
00323   if ((!is_atom (p)) && ((p->item < 0) || (p->item >= arity (t)))) {
00324     cerr << "TeXmacs] left correcting " << p << " in " << t << "\n";
00325     FAILED ("bad path");
00326   }
00327 
00328   int i=p->item;
00329   if (is_atom (p)) return p;
00330   if (is_concat (t) && (i>0) && left_most (t[i], p->next))
00331     return path (i-1, pre_correct (t[i-1], path (right_index (t[i-1]))));
00332   if (is_prime (t)) return path (0);
00333   return path (i, left_correct (t[i], p->next));
00334 }
00335 
00336 static bool
00337 right_most (tree t, path p) {
00338   if (is_nil (p)) FAILED ("invalid nil path");
00339   if ((!is_atom (p)) && ((p->item < 0) || (p->item >= arity (t)))) {
00340     cerr << "TeXmacs] right most " << p << " in " << t << "\n";
00341     FAILED ("bad path");
00342   }
00343 
00344   int i=p->item;
00345   if (is_atom (p)) return i==right_index (t);
00346   if (is_concat (p)) return (i==1) && right_most (t[N(t)-1], p->next);
00347   return false;
00348 }
00349 
00350 static path
00351 right_correct (tree t, path p) {
00352   if (is_nil (p)) FAILED ("invalid nil path");
00353   if ((!is_atom (p)) && ((p->item < 0) || (p->item >= arity (t)))) {
00354     cerr << "TeXmacs] right correcting " << p << " in " << t << "\n";
00355     FAILED ("bad path");
00356   }
00357 
00358   int i=p->item;
00359   if (is_atom (p)) return p;
00360   if (is_concat (t) && (i<N(t)-1) && right_most (t[i], p->next))
00361     return path (i+1, pre_correct (t[i+1], path (0)));
00362   if (is_prime (t)) return path (1);
00363   return path (i, right_correct (t[i], p->next));
00364 }
00365 
00366 /******************************************************************************
00367 * Exported routines for cursor paths in trees
00368 ******************************************************************************/
00369 
00370 path
00371 correct_cursor (tree t, path p, bool forwards) {
00372   //cout << "Correct cursor " << p << " in " << t << "\n";
00373   path pp= pre_correct (t, p);
00374   if (forwards) return right_correct (t, pp);
00375   else return left_correct (t, pp);
00376 }
00377 
00378 path
00379 start (tree t, path p) {
00380   //cout << "Start " << p << " in " << t << "\n";
00381   if ((!is_nil (p)) && (arity (parent_subtree (t, p)) == 0)) return p;
00382   return correct_cursor (t, p * 0);
00383 }
00384 
00385 path
00386 end (tree t, path p) {
00387   //cout << "End " << p << " in " << t << "\n";
00388   if ((!is_nil (p)) && (arity (parent_subtree (t, p)) == 0)) return p;
00389   return correct_cursor (t, p * right_index (subtree (t, p)));
00390 }
00391 
00392 path start (tree t) { return start (t, path ()); }
00393 path end (tree t) { return end (t, path ()); }
00394 
00395 path
00396 up_correct (tree t, path p, bool active= true) {
00397   //cout << "Up correct " << p << " in " << t << "\n";
00398   if (is_nil (p)) return p;
00399   if ((p->item<0) || (p->item>=N(t))) return path ();
00400   if (active && (!the_drd->is_accessible_child (t, p->item))) return path ();
00401   return path (p->item,
00402               up_correct (t[p->item], p->next, !is_mod_active_once (t)));
00403 }
00404 
00405 path
00406 super_correct (tree t, path p, bool forwards) {
00407   path q= path_up (p);
00408   path r= up_correct (t, q);
00409   if (q != r) {
00410     ASSERT (!is_nil (r), "unexpected situation");
00411     int last= (forwards? 1: 0);
00412     if (is_atomic (subtree (t, r))) p= path_up (r) * last;
00413     else p= r * last;
00414   }
00415   return correct_cursor (t, p, forwards);
00416 }