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