Back to index

texmacs  1.0.7.15
tree_brackets.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : tree_brackets.cpp
00004 * DESCRIPTION: upgrade to tree with matching brackets
00005 * COPYRIGHT  : (C) 2010  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_correct.hpp"
00013 #include "tree_analyze.hpp"
00014 #include "scheme.hpp"
00015 
00016 static array<tree> upgrade_brackets (array<tree> a, int level);
00017 
00018 /******************************************************************************
00019 * Extra routines for symbol types
00020 ******************************************************************************/
00021 
00022 static bool
00023 is_dubious_open_middle (array<int> tp, int j) {
00024   j--;
00025   while (j >= 0 && (tp[j] == SYMBOL_SKIP || tp[j] == SYMBOL_SCRIPT))
00026     j--;
00027   return
00028     j < 0 ||
00029     tp[j] == SYMBOL_PREFIX ||
00030     tp[j] == SYMBOL_INFIX ||
00031     tp[j] == SYMBOL_SEPARATOR;
00032 }
00033 
00034 static bool
00035 is_dubious_close_middle (array<int> tp, int j) {
00036   j++;
00037   while (j < N(tp) && (tp[j] == SYMBOL_SKIP || tp[j] == SYMBOL_SCRIPT))
00038     j++;
00039   return
00040     j >= N(tp) ||
00041     tp[j] == SYMBOL_POSTFIX ||
00042     tp[j] == SYMBOL_INFIX ||
00043     tp[j] == SYMBOL_SEPARATOR;
00044 }
00045 
00046 static array<int>
00047 downgrade_dubious (array<int> tp_in) {
00048   array<int> tp= copy (tp_in);
00049   // NOTE: we also might forbid combinations such as OPEN MIDDLE
00050   for (int i=0; i<N(tp); i++)
00051     if (tp[i] >= SYMBOL_PROBABLE_OPEN && tp[i] <= SYMBOL_PROBABLE_CLOSE) {
00052       if (is_dubious_open_middle (tp, i)) {
00053         if (tp[i] == SYMBOL_PROBABLE_MIDDLE) tp[i]= SYMBOL_DUBIOUS_MIDDLE;
00054         if (tp[i] == SYMBOL_PROBABLE_CLOSE) tp[i]= SYMBOL_DUBIOUS_CLOSE;
00055       }
00056       if (is_dubious_close_middle (tp, i)) {
00057         if (tp[i] == SYMBOL_PROBABLE_OPEN) tp[i]= SYMBOL_DUBIOUS_OPEN;
00058         if (tp[i] == SYMBOL_PROBABLE_MIDDLE) tp[i]= SYMBOL_DUBIOUS_MIDDLE;
00059       }
00060     }
00061   return tp;
00062 }
00063 
00064 static array<int>
00065 upgrade_probable (array<int> tp_in) {
00066   array<int> tp= copy (tp_in);
00067   for (int i=0; i<N(tp); i++)
00068     if (tp[i] >= SYMBOL_PROBABLE_OPEN) {
00069       int j= i-1;
00070       while (j >= 0 && (tp[j] == SYMBOL_SKIP || tp[j] == SYMBOL_SCRIPT))
00071        j--;
00072       if (j < 0 ||
00073          tp[j] == SYMBOL_PREFIX ||
00074          tp[j] == SYMBOL_INFIX ||
00075          tp[j] == SYMBOL_SEPARATOR)
00076        tp[i]= SYMBOL_PROBABLE_OPEN;
00077       j= i+1;
00078       while (j < N(tp) && (tp[j] == SYMBOL_SKIP || tp[j] == SYMBOL_SCRIPT))
00079        j++;
00080       if (j >= N(tp) ||
00081          tp[j] == SYMBOL_POSTFIX ||
00082          tp[j] == SYMBOL_INFIX ||
00083          tp[j] == SYMBOL_SEPARATOR)
00084        tp[i]= SYMBOL_PROBABLE_CLOSE;
00085     }
00086   return tp;
00087 }
00088 
00089 static array<int>
00090 confirm_all (array<int> tp_in) {
00091   array<int> tp= upgrade_probable (tp_in);
00092   for (int i=0; i<N(tp); i++)
00093     if (tp[i] == SYMBOL_PROBABLE_OPEN) tp[i]= SYMBOL_OPEN;
00094     else if (tp[i] == SYMBOL_PROBABLE_MIDDLE) tp[i]= SYMBOL_MIDDLE;
00095     else if (tp[i] == SYMBOL_PROBABLE_CLOSE) tp[i]= SYMBOL_CLOSE;
00096   return tp;
00097 }
00098 
00099 static bool
00100 admits_brackets (array<int> tp) {
00101   for (int i=0; i<N(tp); i++)
00102     if (tp[i] >= SYMBOL_OPEN) return true;
00103   return false;
00104 }
00105 
00106 static bool
00107 admits_bigops (array<int> tp) {
00108   for (int i=0; i<N(tp); i++)
00109     if (tp[i] == SYMBOL_OPEN_BIG) return true;
00110   return false;
00111 }
00112 
00113 static array<tree>
00114 replace_dummies (array<tree> a) {
00115   array<tree> b (N(a));
00116   for (int i=0; i<N(a); i++)
00117     if (a[i] == "<cdot>") b[i]= "<cdummy>";
00118     else b[i]= a[i];
00119   return b;
00120 }
00121 
00122 /******************************************************************************
00123 * Heuristic determination of several bracket notations
00124 ******************************************************************************/
00125 
00126 static array<int>
00127 detect_french_interval (array<tree> a, array<int> tp_in) {
00128   // NOTE: we might only allow [ and ]
00129   array<int> tp= upgrade_probable (tp_in);
00130   int last_open= -1, last_comma= -1;
00131   for (int i=0; i<N(tp); i++)
00132     if (tp[i] == SYMBOL_SEPARATOR) {
00133       if (a[i] == "," && last_comma == -1) last_comma= i;
00134       else last_open= last_comma= -1;
00135     }
00136     else if (tp[i] >= SYMBOL_OPEN) {
00137       if (tp[i] == SYMBOL_OPEN || tp[i] == SYMBOL_PROBABLE_OPEN) {
00138        last_open= i;
00139        last_comma= -1;
00140       }
00141       else if (tp[i] == SYMBOL_CLOSE || tp[i] == SYMBOL_PROBABLE_CLOSE) {
00142        if (last_open != -1 && last_comma != -1 && last_comma != i-1) {
00143          tp[last_open]= SYMBOL_OPEN;
00144          tp[i]= SYMBOL_CLOSE;
00145        }
00146        else last_open= last_comma= -1;
00147       }
00148       else if (tp[i] == SYMBOL_MIDDLE || tp[i] == SYMBOL_PROBABLE_MIDDLE);
00149       else last_open= last_comma= -1;
00150     }
00151   return tp;
00152 }
00153 
00154 static array<int>
00155 detect_absolute (array<tree> a, array<int> tp_in, bool insist) {
00156   array<int> tp= upgrade_probable (tp_in);
00157   //cout << "    a = " << a << "\n";
00158   //cout << "    in= " << tp_in << "\n";
00159   //cout << "    tp= " << tp << "\n";
00160   int last_open= -1;
00161   for (int i=0; i<N(tp); i++)
00162     if (tp[i] == SYMBOL_SEPARATOR) last_open= -1;
00163     else if (tp[i] >= SYMBOL_OPEN) {
00164       if (tp[i] == SYMBOL_PROBABLE_OPEN ||
00165          (last_open == -1 && tp[i] == SYMBOL_PROBABLE_MIDDLE))
00166        last_open= i;
00167       else if (tp[i] == SYMBOL_PROBABLE_CLOSE ||
00168               (last_open != -1 && tp[i] == SYMBOL_PROBABLE_MIDDLE))
00169        {
00170          if (last_open != -1 &&
00171               a[i] == a[last_open] &&
00172               ((tp[last_open] == SYMBOL_PROBABLE_OPEN) ||
00173                (tp[i] == SYMBOL_PROBABLE_CLOSE) ||
00174                //(i == last_open + 2 &&
00175                //a[i-1] == "<cdot>") ||
00176                (insist &&
00177                 !is_dubious_open_middle (tp, last_open) &&
00178                 !is_dubious_close_middle (tp, i))))
00179            {
00180              tp[last_open]= SYMBOL_OPEN;
00181              tp[i]= SYMBOL_CLOSE;
00182               last_open= -1;
00183            }
00184          else if (tp[i] == SYMBOL_PROBABLE_MIDDLE) last_open= i;
00185          else last_open= -1;
00186        }
00187       else last_open= -1;
00188     }
00189   return tp;
00190 }
00191 
00192 static array<int>
00193 detect_probable (array<tree> a, array<int> tp_in) {
00194   array<int> tp= upgrade_probable (tp_in);
00195   int last_open= -1;
00196   for (int i=0; i<N(tp); i++)
00197     if (tp[i] >= SYMBOL_OPEN) {
00198       if (tp[i] == SYMBOL_OPEN || tp[i] == SYMBOL_PROBABLE_OPEN)
00199        last_open= i;
00200       else if (tp[i] == SYMBOL_CLOSE || tp[i] == SYMBOL_PROBABLE_CLOSE) {
00201        if (last_open != -1) {
00202          tp[last_open]= SYMBOL_OPEN;
00203          tp[i]= SYMBOL_CLOSE;
00204        }
00205        else last_open= -1;
00206       }
00207       else if (tp[i] == SYMBOL_MIDDLE || tp[i] == SYMBOL_PROBABLE_MIDDLE);
00208       else last_open= -1;
00209     }
00210   return tp;
00211 }
00212 
00213 /******************************************************************************
00214 * Process matching brackets
00215 ******************************************************************************/
00216 
00217 static tree
00218 make_small (tree br) {
00219   if (is_atomic (br)) return br;
00220   if (is_func (br, LEFT) ||
00221       is_func (br, MID) ||
00222       is_func (br, RIGHT) ||
00223       is_func (br, BIG))
00224     if (N(br) > 0 && is_atomic (br[0])) {
00225       string s= br[0]->label;
00226       if (s == ".") return "<nobracket>";
00227       if (N(s) <= 1) return s;
00228       return "<" * s * ">";
00229     }
00230   return "<nobracket>";
00231 }
00232 
00233 static tree
00234 make_around (tree l, tree m, tree r) {
00235   tree_label kind= VAR_AROUND;
00236   if (is_atomic (l) && is_atomic (r)) kind= AROUND;
00237   return tree (kind, make_small (l), m, make_small (r));
00238 }
00239 
00240 static tree
00241 make_around (tree l, tree m) {
00242   return tree (BIG_AROUND, make_small (l), m);
00243 }
00244 
00245 static array<tree>
00246 simplify_matching (array<tree> a, array<int> tp_in, int level) {
00247   //cout << "Simplify matching " << a << ", " << tp_in << "\n";
00248   array<int> tp= copy (tp_in);
00249   int last_open= -1;
00250   for (int i=0; i<N(tp); i++) {
00251     if (tp[i] == SYMBOL_OPEN) last_open= i;
00252     else if (tp[i] >= SYMBOL_PROBABLE_OPEN) last_open= -1;
00253     else if (tp[i] == SYMBOL_CLOSE && last_open != -1) {
00254       array<tree> b= range (a, last_open+1, i);
00255       b= upgrade_brackets (b, level+1);
00256       tree body= concat_recompose (b);
00257       a[last_open]= make_around (a[last_open], body, a[i]);
00258       tp[last_open]= SYMBOL_BASIC;
00259       for (int j= last_open+1; j<=i; j++) tp[j]= SYMBOL_DELETED;
00260       last_open= -1;
00261     }
00262   }
00263 
00264   array<tree> r;
00265   for (int i=0; i<N(tp); i++)
00266     if (tp[i] != SYMBOL_DELETED)
00267       r << a[i];
00268   return r;
00269 }
00270 
00271 static array<tree>
00272 add_missing_left (array<tree> a, array<int> tp) {
00273   array<tree> b;
00274   for (int i=0; i<N(tp); i++)
00275     if (tp[i] == SYMBOL_CLOSE) {
00276       tree body= concat_recompose (b);
00277       b= array<tree> ();
00278       if (is_atomic (a[i])) b << make_around ("<nobracket>", body, a[i]);
00279       else b << make_around (tree (LEFT, "."), body, a[i]);
00280     }
00281     else b << a[i];
00282   return b;
00283 }
00284 
00285 static array<tree>
00286 add_missing_right (array<tree> a, array<int> tp) {
00287   array<tree> b;
00288   for (int i=N(tp)-1; i>=0; i--)
00289     if (tp[i] == SYMBOL_OPEN) {
00290       tree body= concat_recompose (reverse (b));
00291       b= array<tree> ();
00292       if (is_atomic (a[i])) b << make_around (a[i], body, "<nobracket>");
00293       else b << make_around (a[i], body, tree (RIGHT, "."));
00294     }
00295     else b << a[i];
00296   return reverse (b);
00297 }
00298 
00299 /******************************************************************************
00300 * Splitting concats with big operators
00301 ******************************************************************************/
00302 
00303 static array<tree>
00304 prefix_split (array<tree> a, array<int> tp, int level) {
00305   for (int i=1; i<N(tp); i++)
00306     if (tp[i] == SYMBOL_OPEN_BIG) {
00307       array<tree> r= range (a, 0, i);
00308       r << upgrade_brackets (range (a, i, N(tp)), level);
00309       return r;
00310     }
00311   return a;
00312 }
00313 
00314 static array<tree>
00315 infix_split (array<tree> a, array<int> tp_in, array<int> pri, int level) {
00316   array<int> tp= upgrade_probable (tp_in);
00317   int weakest= PRIORITY_RADICAL;
00318   for (int i=0; i<N(tp); i++)
00319     if (tp[i] == SYMBOL_OPEN_BIG)
00320       weakest= min (weakest, pri[i]);
00321     else if (tp[i] == SYMBOL_INFIX ||
00322             tp[i] == SYMBOL_SEPARATOR ||
00323             tp[i] == SYMBOL_MIDDLE ||
00324             tp[i] == SYMBOL_PROBABLE_MIDDLE)
00325       if (pri[i] <= weakest) {
00326        array<tree> r= upgrade_brackets (range (a, 0, i), level);
00327        r << range (a, i, i+1);
00328        r << upgrade_brackets (range (a, i+1, N(a)), level);
00329        return r;
00330       }
00331   return a;
00332 }
00333 
00334 static array<tree>
00335 postfix_split (array<tree> a, array<int> tp_in, int level) {
00336   array<int> tp= upgrade_probable (tp_in);
00337   int i= N(a);
00338   while (i>0 &&
00339         (tp[i-1] == SYMBOL_PREFIX ||
00340          tp[i-1] == SYMBOL_INFIX ||
00341          tp[i-1] == SYMBOL_SEPARATOR ||
00342          tp[i-1] == SYMBOL_OPEN ||
00343          tp[i-1] == SYMBOL_MIDDLE ||
00344          tp[i-1] == SYMBOL_PROBABLE_OPEN ||
00345          tp[i-1] == SYMBOL_PROBABLE_MIDDLE ||
00346          tp[i-1] == SYMBOL_SKIP ||
00347          a[i-1] == "."))
00348     i--;
00349   if (i != N(a)) {
00350     array<tree> r= upgrade_brackets (range (a, 0, i), level);
00351     r << range (a, i, N(a));
00352     return r;
00353   }
00354   return a;
00355 }
00356 
00357 /******************************************************************************
00358 * Extra subroutines for big operators
00359 ******************************************************************************/
00360 
00361 static bool
00362 is_concat_big (tree t) {
00363   if (!is_concat (t) || N(t) == 0 || !is_func (t[0], BIG)) return false;
00364   for (int i=1; i<N(t); i++)
00365     if (!is_func (t[i], RSUB, 1) && !is_func (t[i], RSUP, 1))
00366       return false;
00367   return true;
00368 }
00369 
00370 tree
00371 upgrade_above_below (tree t) {
00372   if (is_atomic (t)) return t;
00373   else if (is_concat (t)) {
00374     tree r (CONCAT);
00375     for (int i=0; i<N(t); i++) {
00376       tree x= upgrade_above_below (t[i]);
00377       if (is_concat (x)) r << A(x);
00378       else r << x;
00379     }
00380     return r;
00381   }
00382   else {
00383     int i, n= N(t);
00384     tree r (t, n);
00385     for (i=0; i<n; i++)
00386       r[i]= upgrade_above_below (t[i]);
00387     if (is_func (r, ABOVE, 2)) {
00388       if (is_func (r[0], BIG))
00389        r= tree (CONCAT, r[0], tree (RSUP, r[1]));
00390       else if (is_concat_big (r[0]))
00391        r= tree (r[0] * tree (CONCAT, tree (RSUP, r[1])));
00392     }
00393     if (is_func (r, BELOW, 2)) {
00394       if (is_func (r[0], BIG))
00395        r= tree (CONCAT, r[0], tree (RSUB, r[1]));
00396       else if (is_concat_big (r[0]))
00397        r= tree (r[0] * tree (CONCAT, tree (RSUB, r[1])));
00398     }
00399     return r;
00400   }
00401 }
00402 
00403 /******************************************************************************
00404 * Master routine for upgrading brackets
00405 ******************************************************************************/
00406 
00407 static array<tree>
00408 upgrade_brackets (array<tree> a, int level) {
00409   array<int> tp= symbol_types (a);
00410   //cout << "Upgrade " << a << ", " << tp << "\n";
00411   if (admits_brackets (tp)) {
00412     //cout << "  Downgrade dubious\n";
00413     array<tree> r= simplify_matching (a, downgrade_dubious (tp), level);
00414     if (r != a) return upgrade_brackets (r, level);
00415     //cout << "  Detect french\n";
00416     r= simplify_matching (a, detect_french_interval (a, tp), level);
00417     if (r != a) return upgrade_brackets (r, level);
00418     //cout << "  Detect absolute 1\n";
00419     r= simplify_matching (a, detect_absolute (a, tp, false), level);
00420     if (r != a) return upgrade_brackets (r, level);
00421     //cout << "  Detect absolute 2\n";
00422     r= simplify_matching (a, detect_absolute (a, tp, true), level);
00423     if (r != a) return upgrade_brackets (r, level);
00424     //cout << "  Detect probable\n";
00425     r= simplify_matching (a, detect_probable (a, tp), level);
00426     if (r != a) return upgrade_brackets (r, level);
00427     //cout << "  Detect dummy substitution\n";
00428     if (replace_dummies (a) != a) {
00429       array<tree> a2= replace_dummies (a);
00430       array<int> tp2= symbol_types (a2);
00431       r= simplify_matching (a2, detect_probable (a2, tp2), level);
00432       if (r != a2) return upgrade_brackets (r, level);
00433     }
00434     //cout << "  Confirm all\n";
00435     r= simplify_matching (a, confirm_all (tp), level);
00436     if (r != a) return upgrade_brackets (r, level);
00437     //cout << "  Missing left\n";
00438     if (get_preference ("automatic brackets") != "off")
00439       r= add_missing_left (a, tp);
00440     if (r != a) return upgrade_brackets (r, level);
00441     //cout << "  Missing right\n";
00442     if (get_preference ("automatic brackets") != "off")
00443       r= add_missing_right (a, tp);
00444     if (r != a) return upgrade_brackets (r, level);
00445   }
00446   if (admits_bigops (tp)) {
00447     array<tree> r= prefix_split (a, tp, level);
00448     if (r != a) return upgrade_brackets (r, level);
00449     r= infix_split (a, tp, symbol_priorities (a), level);
00450     if (r != a) return upgrade_brackets (r, level);
00451     r= postfix_split (a, tp, level);
00452     if (r != a) return upgrade_brackets (r, level);
00453     ASSERT (tp[0] == SYMBOL_OPEN_BIG, "invalid situation");
00454     r= upgrade_brackets (range (a, 1, N(a)), level + 1);
00455     tree body= concat_recompose (r);
00456     r= array<tree> ();
00457     r << make_around (a[0], body);
00458     return r;
00459   }
00460   return a;
00461 }
00462 
00463 static tree
00464 upgrade_brackets_bis (tree t, string mode) {
00465   //cout << "Upgrade " << t << ", " << mode << "\n";
00466   tree r= t;
00467   if (is_compound (t)) {
00468     int i, n= N(t);
00469     r= tree (t, n);
00470     for (i=0; i<n; i++) {
00471       tree tmode= the_drd->get_env_child (t, i, MODE, mode);
00472       string smode= (is_atomic (tmode)? tmode->label: string ("text"));
00473       if (is_correctable_child (t, i, true))
00474        r[i]= upgrade_brackets_bis (t[i], smode);
00475       else r[i]= t[i];
00476     }
00477   }
00478       
00479   if (mode == "math") {
00480     array<tree> a= concat_tokenize (r);
00481     a= upgrade_brackets (a, 0);
00482     tree ret= concat_recompose (a);
00483     //if (ret != r) cout << "< " << r << LF << "> " << ret << LF;
00484     return ret;
00485   }
00486   else return r;
00487 }
00488 
00489 tree
00490 upgrade_brackets (tree t, string mode) {
00491   //cout << "Upgrade " << t << "\n";
00492   with_drd drd (get_document_drd (t));
00493   t= upgrade_above_below (t);
00494   return upgrade_brackets_bis (t, mode);
00495 }
00496 
00497 tree
00498 upgrade_big_bis (tree t) {
00499   if (is_atomic (t)) return t;
00500   int i, n= N(t);
00501   tree r (t, n);
00502   for (i=0; i<n; i++)
00503     r[i]= upgrade_big_bis (t[i]);
00504   if (is_concat (r))
00505     for (int j=0; j<N(r); j++)
00506       if (is_func (r[j], BIG)) {
00507         array<tree> a= concat_tokenize (r);
00508         a= upgrade_brackets (a, 0);
00509         return concat_recompose (a);
00510       }
00511   return r;
00512 }
00513 
00514 tree
00515 upgrade_big (tree t) {
00516   with_drd drd (get_document_drd (t));
00517   return upgrade_big_bis (t);
00518 }
00519 
00520 /******************************************************************************
00521 * Downgrading brackets
00522 ******************************************************************************/
00523 
00524 static tree
00525 downgrade_bracket (tree t, bool large) {
00526   if (!is_atomic (t)) return t;
00527   string s= t->label;
00528   if (large) {
00529     if (t == "<nobracket>") return tree (".");
00530     if (starts (s, "<") && ends (s, ">")) return s (1, N(s)-1);
00531   }
00532   else if (s == "<nobracket>") return "";
00533   return t;
00534 }
00535 
00536 tree
00537 downgrade_brackets (tree t, bool delete_missing, bool big_dot) {
00538   if (is_atomic (t)) return t;
00539   int i, n= N(t);
00540   tree r (t, n);
00541   for (i=0; i<n; i++)
00542     r[i]= downgrade_brackets (t[i], delete_missing, big_dot);
00543   if (is_func (r, AROUND, 3)) {
00544     if (delete_missing && r[0] == "<nobracket>" && r[2] == "<nobracket>")
00545       return concat (r[0], r[1], r[2]);
00546     tree lb= downgrade_bracket (r[0], false);
00547     tree rb= downgrade_bracket (r[2], false);
00548     r= concat (lb, r[1], rb);
00549   }
00550   if (is_func (r, VAR_AROUND, 3)) {
00551     tree lb= tree (LEFT, downgrade_bracket (r[0], true));
00552     tree rb= tree (RIGHT, downgrade_bracket (r[2], true));
00553     if (delete_missing) {
00554       if (lb == tree (LEFT, ".") && rb == tree (RIGHT, "."));
00555       else if (lb == tree (LEFT, ".")) lb= "";
00556       else if (rb == tree (RIGHT, ".")) rb= "";
00557     }
00558     r= concat (lb, r[1], rb);
00559   }
00560   if (is_func (r, BIG_AROUND, 2)) {
00561     tree op= downgrade_bracket (r[0], true);
00562     if (big_dot) r= concat (tree (BIG, op), r[1], tree (BIG, "."));
00563     else r= concat (tree (BIG, op), r[1]);
00564   }
00565   if (is_concat (r)) r= concat_recompose (concat_decompose (r));
00566   return r;
00567 }
00568 
00569 tree
00570 downgrade_big (tree t) {
00571   if (is_atomic (t)) return t;
00572   int i, n= N(t);
00573   tree r (t, n);
00574   for (i=0; i<n; i++)
00575     r[i]= downgrade_big (t[i]);
00576   if (is_func (r, BIG_AROUND, 2)) {
00577     tree op= downgrade_bracket (r[0], true);
00578     r= concat (tree (BIG, op), r[1]);
00579   }
00580   if (is_concat (r)) r= concat_recompose (concat_decompose (r));
00581   return r;
00582 }
00583 
00584 /******************************************************************************
00585 * Moving wrongly brackets across 'math' tag boundary
00586 ******************************************************************************/
00587 
00588 static bool
00589 is_simple_opening (string s) {
00590   return s == "(" || s == "[" || s == "{" || s == "|";
00591 }
00592 
00593 static bool
00594 is_simple_closing (string s) {
00595   return s == ")" || s == "]" || s == "}" || s == "|";
00596 }
00597 
00598 static bool
00599 is_simple_matching (string l, string r) {
00600   return
00601     (l == "(" && r == ")") ||
00602     (l == "[" && r == "]") ||
00603     (l == "{" && r == "}") ||
00604     (l == "|" && r == "|");
00605 }
00606 
00607 static tree
00608 move_brackets_sub (tree t, bool in) {
00609   //cout << t << INDENT << LF;
00610   if (is_compound (t)) {
00611     int i, n= N(t);
00612     tree r= tree (t, n);
00613     for (i=0; i<n; i++)
00614       r[i]= move_brackets_sub (t[i], in);
00615     t= r;
00616   }
00617 
00618   while (true) {
00619     tree r= t;
00620     bool search= true;
00621     if (is_concat (t))
00622       for (int i=0; i<N(t) && search; i++)
00623         if (is_compound (t[i], "math")) {
00624           array<tree> a= concat_tokenize (t[i][0]);
00625           for (int j=0; j<N(a) && search; j++)
00626             if (is_atomic (a[j]) && is_simple_opening (a[j]->label))
00627               for (int k= i+1; k<N(t) && search; k++)
00628                 if (is_atomic (t[k])) {
00629                   string s= t[k]->label;
00630                   for (int l=0; l<N(s) && search; tm_char_forwards (s, l))
00631                     if (is_simple_matching (a[j]->label, s (l, l+1))) {
00632                       if (k == i+1 && l == 0 && in) {
00633                         array<tree> c= concat_decompose (t);
00634                         a << tree (s (0, 1));
00635                         c[i]= compound ("math", concat_recompose (a));
00636                         c[i]= upgrade_brackets (c[i]);
00637                         c[i+1]= s (1, N(s));
00638                         r= move_brackets_sub (concat_recompose (c), in);
00639                         search= false;
00640                       }
00641                       else if (j == 0 && !in) {
00642                         tree x= a[0];
00643                         array<tree> c= concat_decompose (t);
00644                         a= range (a, 1, N(a));
00645                         c[i]= compound ("math", concat_recompose (a));
00646                         c= append (range (c, 0, i),
00647                                    append (x, range (c, i, N(c))));
00648                         r= move_brackets_sub (concat_recompose (c), in);
00649                         search= false;
00650                       }
00651                     }
00652                 }
00653           for (int j=N(a)-1; j>=0 && search; j--)
00654             if (is_atomic (a[j]) && is_simple_closing (a[j]->label))
00655               for (int k= i-1; k>=0 && search; k--)
00656                 if (is_atomic (t[k])) {
00657                   string s= t[k]->label;
00658                   for (int l=N(s); l>0 && search; tm_char_backwards (s, l))
00659                     if (is_simple_matching (s (l-1, l), a[j]->label)) {
00660                       if (k == i-1 && l == N(s) && in) {
00661                         array<tree> c= concat_decompose (t);
00662                         a= append (tree (s (l-1, l)), a);
00663                         c[i]= compound ("math", concat_recompose (a));
00664                         c[i]= upgrade_brackets (c[i]);
00665                         c[i-1]= s (0, l-1);
00666                         r= move_brackets_sub (concat_recompose (c), in);
00667                         search= false;
00668                       }
00669                       else if (j == N(a)-1 && !in) {
00670                         tree x= a[j];
00671                         array<tree> c= concat_decompose (t);
00672                         a= range (a, 0, j);
00673                         c[i]= compound ("math", concat_recompose (a));
00674                         c= append (range (c, 0, i+1),
00675                                    append (x, range (c, i+1, N(c))));
00676                         r= move_brackets_sub (concat_recompose (c), in);
00677                         search= false;
00678                       }
00679                     }
00680                 }
00681         }
00682     if (search) break;
00683     else {
00684       //cout << "< " << t << LF;
00685       //cout << "> " << r << LF;
00686       t= r;
00687     }
00688   }
00689   //cout << UNINDENT << "Done" << LF;
00690   return t;
00691 }
00692 
00693 tree
00694 move_brackets (tree t) {
00695   return move_brackets_sub (move_brackets_sub (t, true), false);
00696 }