1 
2 /******************************************************************************
3 * MODULE     : tree_analyze.cpp
4 * DESCRIPTION: routines for analyzing trees
5 * COPYRIGHT  : (C) 2010  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 "tree_analyze.hpp"
13 #include "convert.hpp"
14 
15 drd_info get_style_drd (tree style);
16 
17 /******************************************************************************
18 * Tokenize mathematical concats and recomposition
19 ******************************************************************************/
20 
21 array<tree>
concat_tokenize(tree t)22 concat_tokenize (tree t) {
23   static language lan= math_language ("std-math");
24   array<tree> r;
25   if (is_atomic (t)) {
26     int i= 0;
27     while (i<N(t->label)) {
28       int start= i;
29       (void) lan->advance (t, i);
30       r << tree (t->label (start, i));
31     }
32   }
33   else if (is_concat (t))
34     for (int i=0; i<N(t); i++)
35       r << concat_tokenize (t[i]);
36   else if (is_func (t, BIG, 1) && t[0] == "."); // NOTE: discard old <big|.>
37   else r << t;
38   return r;
39 }
40 
41 array<tree>
concat_decompose(tree t)42 concat_decompose (tree t) {
43   array<tree> r;
44   if (t == "");
45   else if (is_atomic (t)) r << t;
46   else if (is_concat (t))
47     for (int i=0; i<N(t); i++)
48       r << concat_decompose (t[i]);
49   else r << t;
50   return r;
51 }
52 
53 tree
concat_recompose(array<tree> a)54 concat_recompose (array<tree> a) {
55   array<tree> r;
56   string s;
57   for (int i=0; i<N(a); i++)
58     if (is_atomic (a[i])) s << a[i]->label;
59     else {
60       if (s != "") r << tree (s);
61       r << a[i];
62       s= "";
63     }
64   if (s != "") r << tree (s);
65   if (N(r) == 0) return "";
66   else if (N(r) == 1) return r[0];
67   else return tree (CONCAT, r);
68 }
69 
70 /******************************************************************************
71 * Subroutines for WITH-like macros
72 ******************************************************************************/
73 
74 bool
is_with_like(tree t)75 is_with_like (tree t) {
76   return the_drd->is_with_like (t);
77 }
78 
79 tree&
with_body(tree w)80 with_body (tree w) {
81   return w[N(w)-1];
82 }
83 
84 bool
with_same_type(tree w1,tree w2)85 with_same_type (tree w1, tree w2) {
86   ASSERT (is_with_like (w1) && is_with_like (w2), "with-like trees expected");
87   return w1 (0, N(w1)-1) == w2 (0, N(w2)-1);
88 }
89 
90 bool
with_similar_type(tree w1,tree w2)91 with_similar_type (tree w1, tree w2) {
92   ASSERT (is_with_like (w1) && is_with_like (w2), "with-like trees expected");
93   if (is_compound (w1, "math") || is_compound (w1, "text"))
94     return is_compound (w2, "math") || is_compound (w2, "text");
95   if (!is_func (w1, WITH) || !is_func (w2, WITH))
96     return with_same_type (w1, w2);
97   if (N(w1) != N(w2)) return false;
98   for (int i=0; i<N(w1)-1; i+=2)
99     if (w1[i] != w2[i]) return false;
100   return true;
101 }
102 
103 array<tree>
with_decompose(tree w,tree t)104 with_decompose (tree w, tree t) {
105   array<tree> r;
106   if (t == "");
107   else if (is_atomic (t)) r << t;
108   else if (is_concat (t))
109     for (int i=0; i<N(t); i++)
110       r << with_decompose (w, t[i]);
111   else if (is_with_like (t) && with_same_type (w, t))
112     r << with_decompose (w, with_body (t));
113   else r << t;
114   return r;
115 }
116 
117 tree
with_recompose(tree w,array<tree> a)118 with_recompose (tree w, array<tree> a) {
119   tree r= w (0, N(w));
120   with_body (r)= concat_recompose (a);
121   return r;
122 }
123 
124 /******************************************************************************
125 * Determine symbol type
126 ******************************************************************************/
127 
128 int
symbol_type(tree t)129 symbol_type (tree t) {
130   static language lan= math_language ("std-math");
131   tree r= the_drd->get_syntax (t);
132   if (r != UNINIT) {
133     if (is_compound (t, "text")) return SYMBOL_SKIP;
134     else if (is_compound (t, "eq-number")) return SYMBOL_SKIP;
135     else if (is_compound (t, "bl")) return SYMBOL_OPEN;
136     else if (is_compound (t, "br")) return SYMBOL_CLOSE;
137     else return symbol_type (r);
138   }
139   else if (is_atomic (t)) {
140     int pos= 0;
141     text_property prop= lan->advance (t, pos);
142     switch (prop->op_type) {
143     case OP_UNKNOWN:
144     case OP_TEXT:
145     case OP_SKIP:
146     case OP_SYMBOL:
147     case OP_UNARY:
148     case OP_BINARY:
149     case OP_N_ARY:
150       return SYMBOL_BASIC;
151     case OP_PREFIX:
152       return SYMBOL_PREFIX;
153     case OP_POSTFIX:
154       return SYMBOL_POSTFIX;
155     case OP_INFIX:
156       return SYMBOL_INFIX;
157     case OP_SEPARATOR:
158       return SYMBOL_SEPARATOR;
159     case OP_OPENING_BRACKET:
160       return SYMBOL_PROBABLE_OPEN;
161     case OP_MIDDLE_BRACKET:
162       return SYMBOL_PROBABLE_MIDDLE;
163     case OP_CLOSING_BRACKET:
164       return SYMBOL_PROBABLE_CLOSE;
165     default:
166       return SYMBOL_BASIC;
167     }
168   }
169   else switch (L(t)) {
170     case HSPACE:
171     case VAR_VSPACE:
172     case VSPACE:
173     case SPACE:
174     case HTAB:
175       return SYMBOL_SKIP;
176 
177     case LEFT:
178       return SYMBOL_OPEN;
179     case MID:
180       return SYMBOL_MIDDLE;
181     case RIGHT:
182       return SYMBOL_CLOSE;
183     case BIG:
184       if (is_func (t, BIG, 1) && t[0] == ".") return SYMBOL_CLOSE_BIG;
185       else return SYMBOL_OPEN_BIG;
186     case LPRIME:
187     case RPRIME:
188     case LSUB:
189     case LSUP:
190     case RSUB:
191     case RSUP:
192       return SYMBOL_SCRIPT;
193 
194     case WITH:
195     case STYLE_WITH:
196     case VAR_STYLE_WITH:
197       return symbol_type (t[N(t)-1]);
198     case LABEL:
199       return SYMBOL_SKIP;
200 
201     default:
202       return SYMBOL_BASIC;
203   }
204 }
205 
206 array<int>
symbol_types(array<tree> a)207 symbol_types (array<tree> a) {
208   array<int> tp (N(a));
209   for (int i=0; i<N(a); i++)
210     tp[i]= symbol_type (a[i]);
211   return tp;
212 }
213 
214 /******************************************************************************
215 * Determine symbol priority
216 ******************************************************************************/
217 
218 #define PRIORITY_SEPARATOR          0
219 #define PRIORITY_ASSIGN             1
220 #define PRIORITY_FLUX               2
221 #define PRIORITY_MODELS             3
222 #define PRIORITY_IMPLY              4
223 #define PRIORITY_OR                 5
224 #define PRIORITY_AND                6
225 #define PRIORITY_RELATION           7
226 #define PRIORITY_ARROW              8
227 #define PRIORITY_UNION              9
228 #define PRIORITY_INTERSECTION      10
229 #define PRIORITY_PLUS              11
230 #define PRIORITY_TIMES             12
231 #define PRIORITY_POWER             13
232 #define PRIORITY_RADICAL           14
233 
234 int
symbol_priority(tree t)235 symbol_priority (tree t) {
236   static language lan= math_language ("std-math");
237   if (is_atomic (t)) {
238     string g= lan->get_group (t->label);
239     if (starts (g, "Separator")) return PRIORITY_SEPARATOR;
240     if (starts (g, "Ponctuation")) return PRIORITY_SEPARATOR;
241     if (starts (g, "Assign")) return PRIORITY_ASSIGN;
242     if (starts (g, "Flux")) return PRIORITY_FLUX;
243     if (starts (g, "Models")) return PRIORITY_MODELS;
244     if (starts (g, "Imply")) return PRIORITY_IMPLY;
245     if (starts (g, "Or")) return PRIORITY_OR;
246     if (starts (g, "And")) return PRIORITY_AND;
247     if (starts (g, "Relation")) return PRIORITY_RELATION;
248     if (starts (g, "Arrow")) return PRIORITY_ARROW;
249     if (starts (g, "Union")) return PRIORITY_UNION;
250     if (starts (g, "Exclude")) return PRIORITY_UNION;
251     if (starts (g, "Intersection")) return PRIORITY_INTERSECTION;
252     if (starts (g, "Plus")) return PRIORITY_PLUS;
253     if (starts (g, "Minus")) return PRIORITY_PLUS;
254     if (starts (g, "Times")) return PRIORITY_TIMES;
255     if (starts (g, "Over")) return PRIORITY_TIMES;
256     if (starts (g, "Power")) return PRIORITY_POWER;
257     return PRIORITY_RADICAL;
258   }
259   else if (is_func (t, BIG, 1) && is_atomic (t[0])) {
260     string s= t[0]->label;
261     if (s == "parallel") return PRIORITY_SEPARATOR;
262     if (s == "interleave") return PRIORITY_SEPARATOR;
263     if (s == "vee") return PRIORITY_OR;
264     if (s == "curlyvee") return PRIORITY_OR;
265     if (s == "wedge") return PRIORITY_AND;
266     if (s == "curlywedge") return PRIORITY_AND;
267     if (s == "cup") return PRIORITY_UNION;
268     if (s == "sqcup") return PRIORITY_UNION;
269     if (s == "amalg") return PRIORITY_UNION;
270     if (s == "uplus") return PRIORITY_UNION;
271     if (s == "box") return PRIORITY_UNION;
272     if (s == "cap") return PRIORITY_INTERSECTION;
273     if (s == "sqcap") return PRIORITY_INTERSECTION;
274     if (s == "int") return PRIORITY_PLUS;
275     if (s == "oint") return PRIORITY_PLUS;
276     if (s == "intlim") return PRIORITY_PLUS;
277     if (s == "ointlim") return PRIORITY_PLUS;
278     if (s == "sum") return PRIORITY_PLUS;
279     if (s == "oplus") return PRIORITY_PLUS;
280     if (s == "triangledown") return PRIORITY_PLUS;
281     if (s == "prod") return PRIORITY_TIMES;
282     if (s == "otimes") return PRIORITY_TIMES;
283     if (s == "odot") return PRIORITY_TIMES;
284     if (s == "triangleup") return PRIORITY_TIMES;
285     return PRIORITY_RADICAL;
286   }
287   else return PRIORITY_RADICAL;
288 }
289 
290 array<int>
symbol_priorities(array<tree> a)291 symbol_priorities (array<tree> a) {
292   array<int> tp (N(a));
293   for (int i=0; i<N(a); i++)
294     tp[i]= symbol_priority (a[i]);
295   return tp;
296 }
297 
298 /******************************************************************************
299 * Further routines
300 ******************************************************************************/
301 
302 bool
is_correctable_child(tree t,int i,bool noaround)303 is_correctable_child (tree t, int i, bool noaround) {
304   int type= the_drd->get_type_child (t, i);
305   if (is_compound (t, "body", 1)) return true;
306   else if (!is_concat (t)) {
307     switch (type) {
308     case TYPE_INVALID:
309     case TYPE_REGULAR:
310     case TYPE_GRAPHICAL:
311     case TYPE_ANIMATION:
312     case TYPE_UNKNOWN:
313       return true;
314     default:
315       return false;
316     }
317   }
318   else if (is_atomic (t[i]) ||
319 	   (noaround && is_func (t[i], AROUND)) ||
320 	   (noaround && is_func (t[i], VAR_AROUND)) ||
321 	   (noaround && is_func (t[i], BIG_AROUND)) ||
322 	   is_func (t[i], LEFT) ||
323 	   is_func (t[i], MID) ||
324 	   is_func (t[i], RIGHT) ||
325 	   is_func (t[i], BIG) ||
326 	   is_compound (t[i], "bl") ||
327 	   is_compound (t[i], "br"))
328     return false;
329   else return true;
330 }
331