1
2 /******************************************************************************
3 * MODULE : modification.hpp
4 * DESCRIPTION: elementary tree modifications
5 * COPYRIGHT : (C) 2008 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 "modification.hpp"
13
14 /******************************************************************************
15 * Equality and Output
16 ******************************************************************************/
17
18 bool
operator ==(modification m1,modification m2)19 operator == (modification m1, modification m2) {
20 return m1->k == m2->k && m1->p == m2->p && m1->t == m2->t;
21 }
22
23 bool
operator !=(modification m1,modification m2)24 operator != (modification m1, modification m2) {
25 return m1->k != m2->k || m1->p != m2->p || m1->t != m2->t;
26 }
27
28 tm_ostream&
operator <<(tm_ostream & out,modification mod)29 operator << (tm_ostream& out, modification mod) {
30 switch (mod->k) {
31 case MOD_ASSIGN:
32 return out << "assign (" << root (mod)
33 << ", " << mod->t << ")";
34 case MOD_INSERT:
35 return out << "insert (" << root (mod)
36 << ", " << index (mod) << ", " << mod->t << ")";
37 case MOD_REMOVE:
38 return out << "remove (" << root (mod)
39 << ", " << index (mod) << ", " << argument (mod) << ")";
40 case MOD_SPLIT:
41 return out << "split (" << root (mod)
42 << ", " << index (mod) << ", " << argument (mod) << ")";
43 case MOD_JOIN:
44 return out << "join (" << root (mod)
45 << ", " << index (mod) << ")";
46 case MOD_ASSIGN_NODE:
47 return out << "assign_node (" << root (mod)
48 << ", " << mod->t << ")";
49 case MOD_INSERT_NODE:
50 return out << "insert_node (" << root (mod)
51 << ", " << argument (mod) << ", " << mod->t << ")";
52 case MOD_REMOVE_NODE:
53 return out << "remove_node (" << root (mod)
54 << ", " << index (mod) << ")";
55 case MOD_SET_CURSOR:
56 return out << "set_cursor (" << root (mod)
57 << ", " << index (mod) << ", " << mod->t << ")";
58 default: FAILED ("invalid modification type");
59 return out;
60 }
61 }
62
63 /******************************************************************************
64 * Accessors
65 ******************************************************************************/
66
67 path
root(modification mod)68 root (modification mod) {
69 switch (mod->k) {
70 case MOD_ASSIGN: return mod->p;
71 case MOD_INSERT: return path_up (mod->p);
72 case MOD_REMOVE: return path_up (path_up (mod->p));
73 case MOD_SPLIT: return path_up (path_up (mod->p));
74 case MOD_JOIN: return path_up (mod->p);
75 case MOD_ASSIGN_NODE: return mod->p;
76 case MOD_INSERT_NODE: return path_up (mod->p);
77 case MOD_REMOVE_NODE: return path_up (mod->p);
78 case MOD_SET_CURSOR: return path_up (mod->p);
79 default: FAILED ("invalid modification type");
80 }
81 }
82
83 int
index(modification mod)84 index (modification mod) {
85 switch (mod->k) {
86 case MOD_INSERT: return last_item (mod->p);
87 case MOD_REMOVE: return last_item (path_up (mod->p));
88 case MOD_SPLIT: return last_item (path_up (mod->p));
89 case MOD_JOIN: return last_item (mod->p);
90 case MOD_REMOVE_NODE: return last_item (mod->p);
91 case MOD_SET_CURSOR: return last_item (mod->p);
92 default: FAILED ("invalid modification type");
93 }
94 }
95
96 int
argument(modification mod)97 argument (modification mod) {
98 switch (mod->k) {
99 case MOD_REMOVE: return last_item (mod->p);
100 case MOD_SPLIT: return last_item (mod->p);
101 case MOD_INSERT_NODE: return last_item (mod->p);
102 default: FAILED ("invalid modification type");
103 }
104 }
105
106 tree_label
L(modification mod)107 L (modification mod) {
108 ASSERT (mod->k == MOD_ASSIGN_NODE, "assign_node modification expected");
109 return L (mod->t);
110 }
111
112 /******************************************************************************
113 * Constructor and accessors for scheme interface
114 ******************************************************************************/
115
116 modification
make_modification(string s,path p,tree t)117 make_modification (string s, path p, tree t) {
118 modification_type k= MOD_ASSIGN;
119 if (s == "assign") k= MOD_ASSIGN;
120 else if (s == "insert") k= MOD_INSERT;
121 else if (s == "remove") k= MOD_REMOVE;
122 else if (s == "split") k= MOD_SPLIT;
123 else if (s == "join") k= MOD_JOIN;
124 else if (s == "assign-node") k= MOD_ASSIGN_NODE;
125 else if (s == "insert-node") k= MOD_INSERT_NODE;
126 else if (s == "remove-node") k= MOD_REMOVE_NODE;
127 else if (s == "set-cursor") k= MOD_SET_CURSOR;
128 return modification (k, p, t);
129 }
130
131 string
get_type(modification mod)132 get_type (modification mod) {
133 switch (mod->k) {
134 case MOD_ASSIGN: return "assign";
135 case MOD_INSERT: return "insert";
136 case MOD_REMOVE: return "remove";
137 case MOD_SPLIT: return "split";
138 case MOD_JOIN: return "join";
139 case MOD_ASSIGN_NODE: return "assign-node";
140 case MOD_INSERT_NODE: return "insert-node";
141 case MOD_REMOVE_NODE: return "remove-node";
142 case MOD_SET_CURSOR: return "set-cursor";
143 default: FAILED ("invalid modification type");
144 }
145 }
146
147 path
get_path(modification mod)148 get_path (modification mod) {
149 return mod->p;
150 }
151
152 tree
get_tree(modification mod)153 get_tree (modification mod) {
154 return mod->t;
155 }
156
157 /******************************************************************************
158 * Test applicability of modifications
159 ******************************************************************************/
160
161 bool
can_assign(tree t,path p,tree u)162 can_assign (tree t, path p, tree u) {
163 (void) u;
164 return has_subtree (t, p);
165 }
166
167 bool
can_insert(tree t,path p,int pos,tree u)168 can_insert (tree t, path p, int pos, tree u) {
169 if (!has_subtree (t, p)) return false;
170 tree st= subtree (t, p);
171 if (is_atomic (st)) return pos >= 0 && pos <= N(st->label) && is_atomic (u);
172 else return pos >= 0 && pos <= N(st) && is_compound (u);
173 }
174
175 bool
can_remove(tree t,path p,int pos,int nr)176 can_remove (tree t, path p, int pos, int nr) {
177 if (!has_subtree (t, p)) return false;
178 tree st= subtree (t, p);
179 if (is_atomic (st)) return pos >= 0 && pos+nr <= N(st->label);
180 else return pos >= 0 && pos+nr <= N(st);
181 }
182
183 bool
can_split(tree t,path p,int pos,int at)184 can_split (tree t, path p, int pos, int at) {
185 if (!has_subtree (t, p * pos)) return false;
186 tree st= subtree (t, p * pos);
187 if (is_atomic (st)) return at >= 0 && at <= N(st->label);
188 else return at >= 0 && at <= N(st);
189 }
190
191 bool
can_join(tree t,path p,int pos)192 can_join (tree t, path p, int pos) {
193 if (!has_subtree (t, p)) return false;
194 tree st= subtree (t, p);
195 if (pos < 0 || pos+1 >= N(st)) return false;
196 if (is_atomic (st[pos]) && is_atomic (st[pos+1])) return true;
197 if (is_compound (st[pos]) && is_compound (st[pos+1])) return true;
198 return false;
199 }
200
201 bool
can_assign_node(tree t,path p,tree_label op)202 can_assign_node (tree t, path p, tree_label op) {
203 (void) op;
204 return has_subtree (t, p) && is_compound (subtree (t, p));
205 }
206
207 bool
can_insert_node(tree t,path p,int pos,tree u)208 can_insert_node (tree t, path p, int pos, tree u) {
209 return has_subtree (t, p) && is_compound (u) && pos >= 0 && pos <= N(u);
210 }
211
212 bool
can_remove_node(tree t,path p,int pos)213 can_remove_node (tree t, path p, int pos) {
214 return has_subtree (t, p * pos);
215 }
216
217 bool
can_set_cursor(tree t,path p,int pos,tree data)218 can_set_cursor (tree t, path p, int pos, tree data) {
219 (void) data;
220 if (!has_subtree (t, p)) return false;
221 return pos >= 0 && pos <= right_index (subtree (t, p));
222 }
223
224 bool
is_applicable(tree t,modification mod)225 is_applicable (tree t, modification mod) {
226 switch (mod->k) {
227 case MOD_ASSIGN:
228 return can_assign (t, root (mod), mod->t);
229 case MOD_INSERT:
230 return can_insert (t, root (mod), index (mod), mod->t);
231 case MOD_REMOVE:
232 return can_remove (t, root (mod), index (mod), argument (mod));
233 case MOD_SPLIT:
234 return can_split (t, root (mod), index (mod), argument (mod));
235 case MOD_JOIN:
236 return can_join (t, root (mod), index (mod));
237 case MOD_ASSIGN_NODE:
238 return can_assign_node (t, root (mod), L (mod));
239 case MOD_INSERT_NODE:
240 return can_insert_node (t, root (mod), argument (mod), mod->t);
241 case MOD_REMOVE_NODE:
242 return can_remove_node (t, root (mod), index (mod));
243 case MOD_SET_CURSOR:
244 return can_set_cursor (t, root (mod), index (mod), mod->t);
245 default:
246 return false;
247 }
248 }
249
250 /******************************************************************************
251 * Functional application of modifications
252 ******************************************************************************/
253
254 tree
clean_assign(tree t,path p,tree u)255 clean_assign (tree t, path p, tree u) {
256 if (is_nil (p)) return copy (u);
257 else {
258 int i, j= p->item, n= N(t);
259 if (j >= n) FAILED("clean_remove(): Invalid path."); //return copy(u); // FIXME? check whether this is the right return value.
260 tree r (t, n);
261 for (i=0; i<j; i++) r[i]= t[i];
262 r[j]= clean_assign (t[j], p->next, u);
263 for (i++; i<n; i++) r[i]= t[i];
264 return r;
265 }
266 }
267
268 tree
clean_insert(tree t,path p,tree u)269 clean_insert (tree t, path p, tree u) {
270 if (is_nil (p->next) && is_atomic (t)) {
271 string s= t->label;
272 return s (0, p->item) * u->label * s (p->item, N(s));
273 }
274 else if (is_nil (p->next)) {
275 int i, j= p->item, n= N(t), nr= N(u);
276 tree r (t, n+nr);
277 for (i=0; i<j; i++) r[i]= t[i];
278 for (; i<n; i++) r[i+nr]= t[i];
279 for (i=0; i<nr; i++) r[j+i]= copy (u[i]);
280 return r;
281 }
282 else {
283 int i, j= p->item, n= N(t);
284 tree r (t, n);
285 for (i=0; i<j; i++) r[i]= t[i];
286 r[j]= clean_insert (t[j], p->next, u);
287 for (i++; i<n; i++) r[i]= t[i];
288 return r;
289 }
290 }
291
292 tree
clean_remove(tree t,path p,int nr)293 clean_remove (tree t, path p, int nr) {
294 if (is_nil (p->next) && is_atomic (t)) {
295 string s= t->label;
296 if (N(s) < p->item+nr)
297 FAILED ("clean_remove: Invalid remove from atomic tree");
298 return s (0, p->item) * s (p->item+nr, N(s));
299 }
300 else if (is_nil (p->next)) {
301 int i, j= p->item, n= N(t);
302 tree r (t, n-nr);
303 for (i=0; i<j; i++) r[i]= t[i];
304 for (i+=nr; i<n; i++) r[i-nr]= t[i];
305 return r;
306 }
307 else {
308 int i, j= p->item, n= N(t);
309 if (j >= n) FAILED ("clean_remove: Invalid path"); //return t; // FIXME? check whether this is the right return value.
310 tree r (t, n);
311 for (i=0; i<j; i++) r[i]= t[i];
312 r[j]= clean_remove (t[j], p->next, nr);
313 for (i++; i<n; i++) r[i]= t[i];
314 return r;
315 }
316 }
317
318 tree
clean_split(tree t,path p)319 clean_split (tree t, path p) {
320 if (is_nil (p->next->next)) {
321 tree u= t[p->item];
322 int i, n1= p->next->item, n2= N(u)-n1;
323 tree s1, s2;
324 if (is_atomic (u)) {
325 s1= u->label (0, n1);
326 s2= u->label (n1, N(u->label));
327 }
328 else {
329 s1= tree (u, n1);
330 s2= tree (u, n2);
331 for (i=0; i<n1; i++) s1[i]= u[i];
332 for (i=0; i<n2; i++) s2[i]= u[n1+i];
333 }
334
335 int j= p->item, n= N(t);
336 tree r (t, n+1);
337 for (i=0; i<j; i++) r[i]= t[i];
338 r[j]= s1; r[j+1]= s2;
339 for (i++; i<n; i++) r[i+1]= t[i];
340 return r;
341 }
342 else {
343 int i, j= p->item, n= N(t);
344 tree r (t, n);
345 for (i=0; i<j; i++) r[i]= t[i];
346 r[j]= clean_split (t[j], p->next);
347 for (i++; i<n; i++) r[i]= t[i];
348 return r;
349 }
350 }
351
352 tree
clean_join(tree t,path p)353 clean_join (tree t, path p) {
354 if (is_nil (p->next)) {
355 int i, j= p->item;
356 tree s1= t[j], s2= t[j+1], u;
357 if (is_atomic (s1))
358 u= tree (s1->label * s2->label);
359 else {
360 int n1= N(s1), n2= N(s2);
361 u= tree (s1, n1+n2);
362 for (i=0; i<n1; i++) u[i]= s1[i];
363 for (i=0; i<n2; i++) u[n1+i]= s2[i];
364 }
365
366 int n= N(t);
367 tree r (t, n-1);
368 for (i=0; i<j; i++) r[i]= t[i];
369 r[j]= u;
370 for (i+=2; i<n; i++) r[i-1]= t[i];
371 return r;
372 }
373 else {
374 int i, j= p->item, n= N(t);
375 tree r (t, n);
376 for (i=0; i<j; i++) r[i]= t[i];
377 r[j]= clean_join (t[j], p->next);
378 for (i++; i<n; i++) r[i]= t[i];
379 return r;
380 }
381 }
382
383 tree
clean_assign_node(tree t,path p,tree_label op)384 clean_assign_node (tree t, path p, tree_label op) {
385 if (is_nil (p)) {
386 int i, n= N(t);
387 tree r (op, n);
388 for (i=0; i<n; i++) r[i]= t[i];
389 return r;
390 }
391 else {
392 int i, j= p->item, n= N(t);
393 tree r (t, n);
394 for (i=0; i<j; i++) r[i]= t[i];
395 r[j]= clean_assign_node (t[j], p->next, op);
396 for (i++; i<n; i++) r[i]= t[i];
397 return r;
398 }
399 }
400
401 tree
clean_insert_node(tree t,path p,tree u)402 clean_insert_node (tree t, path p, tree u) {
403 if (is_nil (p->next)) {
404 int i, j= p->item, n= N(u);
405 tree r (u, n+1);
406 for (i=0; i<j; i++) r[i]= u[i];
407 r[j]= t;
408 for (; i<n; i++) r[i+1]= u[i];
409 return r;
410 }
411 else {
412 int i, j= p->item, n= N(t);
413 tree r (t, n);
414 for (i=0; i<j; i++) r[i]= t[i];
415 r[j]= clean_insert_node (t[j], p->next, u);
416 for (i++; i<n; i++) r[i]= t[i];
417 return r;
418 }
419 }
420
421 tree
clean_remove_node(tree t,path p)422 clean_remove_node (tree t, path p) {
423 if (is_nil (p->next)) return t[p->item];
424 else {
425 int i, j= p->item, n= N(t);
426 tree r (t, n);
427 for (i=0; i<j; i++) r[i]= t[i];
428 r[j]= clean_remove_node (t[j], p->next);
429 for (i++; i<n; i++) r[i]= t[i];
430 return r;
431 }
432 }
433
434 tree
clean_set_cursor(tree t,path p,tree data)435 clean_set_cursor (tree t, path p, tree data) {
436 (void) p; (void) data;
437 return t;
438 }
439
440 tree
clean_apply(tree t,modification mod)441 clean_apply (tree t, modification mod) {
442 switch (mod->k) {
443 case MOD_ASSIGN:
444 return clean_assign (t, mod->p, mod->t);
445 case MOD_INSERT:
446 return clean_insert (t, mod->p, mod->t);
447 case MOD_REMOVE:
448 return clean_remove (t, path_up (mod->p), last_item (mod->p));
449 case MOD_SPLIT:
450 return clean_split (t, mod->p);
451 case MOD_JOIN:
452 return clean_join (t, mod->p);
453 case MOD_ASSIGN_NODE:
454 return clean_assign_node (t, mod->p, L(mod));
455 case MOD_INSERT_NODE:
456 return clean_insert_node (t, mod->p, mod->t);
457 case MOD_REMOVE_NODE:
458 return clean_remove_node (t, mod->p);
459 case MOD_SET_CURSOR:
460 return clean_set_cursor (t, mod->p, mod->t);
461 default:
462 FAILED ("invalid modification type");
463 return "";
464 }
465 }
466