1 /* Part of SWI-Prolog
2
3 Author: Jan Wielemaker
4 E-mail: J.Wielemaker@vu.nl
5 WWW: http://www.swi-prolog.org
6 Copyright (c) 2009-2016, University of Amsterdam
7 VU University Amsterdam
8 All rights reserved.
9
10 Redistribution and use in source and binary forms, with or without
11 modification, are permitted provided that the following conditions
12 are met:
13
14 1. Redistributions of source code must retain the above copyright
15 notice, this list of conditions and the following disclaimer.
16
17 2. Redistributions in binary form must reproduce the above copyright
18 notice, this list of conditions and the following disclaimer in
19 the documentation and/or other materials provided with the
20 distribution.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
37 Provide primitives for walking a term, while protecting against cycles.
38 There are two scenarios: avoid walking a sub-term twice in general and
39 avoid cycles. I.e. given the term A=a(1), T = t(A,A), we have
40
41 - If walk-whole-term: walks A twice
42 - If avoid double: walks A once
43
44 Next, sometimes we want to get control after processing the arguments of
45 a compound and sometimes we do not care. In the latter case, we can
46 simply jump to the last argument.
47 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
48
49 #if !AC_TERM_WALK
50
51 typedef struct aNode
52 { Word location;
53 size_t size;
54 } aNode;
55
56 typedef struct term_agenda
57 { aNode work; /* current work */
58 segstack stack;
59 char first_chunk[256];
60 } term_agenda;
61
62
63 static inline void
initTermAgenda(term_agenda * a,size_t size,Word p)64 initTermAgenda(term_agenda *a, size_t size, Word p)
65 { initSegStack(&a->stack, sizeof(aNode),
66 sizeof(a->first_chunk), a->first_chunk);
67 a->work.location = p;
68 a->work.size = size;
69 }
70
71
72 static inline void
clearTermAgenda(term_agenda * a)73 clearTermAgenda(term_agenda *a)
74 { clearSegStack(&a->stack);
75 }
76
77 #define nextTermAgenda(a) \
78 nextTermAgenda__LD(a PASS_LD)
79
80 static inline Word
nextTermAgenda__LD(term_agenda * a ARG_LD)81 nextTermAgenda__LD(term_agenda *a ARG_LD)
82 { Word p;
83
84 if ( a->work.size > 0 )
85 { ok:
86 a->work.size--;
87 p = a->work.location++;
88 deRef(p);
89
90 return p;
91 }
92
93 if ( popSegStack(&a->stack, &a->work, aNode) )
94 goto ok;
95
96 return NULL;
97 }
98
99
100 static inline Word
nextTermAgendaNoDeRef(term_agenda * a)101 nextTermAgendaNoDeRef(term_agenda *a)
102 { Word p;
103
104 if ( a->work.size > 0 )
105 { ok:
106 a->work.size--;
107 p = a->work.location++;
108
109 return p;
110 }
111
112 if ( popSegStack(&a->stack, &a->work, aNode) )
113 goto ok;
114
115 return NULL;
116 }
117
118
119
120
121 /*******************************
122 * PUSH VARIATIONS *
123 *******************************/
124
125 static inline int
pushWorkAgenda(term_agenda * a,size_t amount,Word start)126 pushWorkAgenda(term_agenda *a, size_t amount, Word start)
127 { if ( a->work.size > 0 )
128 { if ( !pushSegStack(&a->stack, a->work, aNode) )
129 return FALSE;
130 }
131 a->work.location = start;
132 a->work.size = amount;
133
134 return TRUE;
135 }
136
137 #endif /*!AC_TERM_WALK*/
138
139
140 #if AC_TERM_WALK
141
142 /*******************************
143 * WALK ACYCLIC TERM *
144 *******************************/
145
146 typedef struct acNode
147 { Functor term;
148 Word location;
149 size_t size;
150 } acNode;
151
152 typedef struct ac_term_agenda
153 { acNode work; /* current work */
154 segstack stack;
155 char first_chunk[64*sizeof(acNode)];
156 } ac_term_agenda;
157
158
159 static void
ac_initTermAgenda(ac_term_agenda * a,Word p)160 ac_initTermAgenda(ac_term_agenda *a, Word p)
161 { initSegStack(&a->stack, sizeof(acNode),
162 sizeof(a->first_chunk), a->first_chunk);
163 a->work.term = NULL;
164 a->work.location = p;
165 a->work.size = 1;
166 }
167
168
169 static void
ac_clearTermAgenda(ac_term_agenda * a)170 ac_clearTermAgenda(ac_term_agenda *a)
171 { do
172 { if ( a->work.term )
173 clear_marked((Word)&a->work.term->definition);
174 } while(popSegStack(&a->stack, &a->work, acNode));
175 }
176
177
178 #define ac_nextTermAgenda(a) \
179 ac_nextTermAgenda__LD(a PASS_LD)
180
181 static Word
ac_nextTermAgenda__LD(ac_term_agenda * a ARG_LD)182 ac_nextTermAgenda__LD(ac_term_agenda *a ARG_LD)
183 { Word p;
184
185 while ( a->work.size == 0 )
186 { if ( a->work.term )
187 clear_marked((Word)&a->work.term->definition);
188 if ( !popSegStack(&a->stack, &a->work, acNode) )
189 return NULL;
190 }
191 a->work.size--;
192
193 p = a->work.location++;
194 deRef(p);
195
196 return p;
197 }
198
199 #define ac_pushTermAgenda(a, w, fp) \
200 ac_pushTermAgenda__LD(a, w, fp PASS_LD)
201
202 static int
ac_pushTermAgenda__LD(ac_term_agenda * a,word w,functor_t * fp ARG_LD)203 ac_pushTermAgenda__LD(ac_term_agenda *a, word w, functor_t *fp ARG_LD)
204 { Functor term = valueTerm(w);
205
206 if ( is_marked((Word)&term->definition) )
207 return FALSE; /* hit cycle */
208 if ( !pushSegStack(&a->stack, a->work, acNode) )
209 return -1; /* no memory */
210 a->work.term = term;
211 a->work.location = term->arguments;
212 a->work.size = arityFunctor(term->definition);
213 *fp = term->definition;
214 set_marked((Word)&term->definition);
215
216 return TRUE;
217 }
218
219 #endif /*AC_TERM_WALK*/
220
221
222 /*******************************
223 * POP ON ONE TERM *
224 *******************************/
225
226 #if AC_TERM_WALK_POP
227
228 #define AC_TERM_POP(n) ((Word)(((n)<<1)|0x1))
229 #define IS_AC_TERM_POP(p) (((uintptr_t)(p)&0x1) ? (uintptr_t)(p)>>1 : 0)
230
231 typedef struct aNode_P
232 { Word location;
233 size_t size;
234 size_t depth;
235 } aNode_P;
236
237 typedef struct term_agenda_P
238 { aNode_P work; /* current work */
239 segstack stack;
240 char first_chunk[sizeof(segchunk)+sizeof(aNode_P)*64];
241 } term_agenda_P;
242
243
244 static void
initTermAgenda_P(term_agenda_P * a,size_t size,Word p)245 initTermAgenda_P(term_agenda_P *a, size_t size, Word p)
246 { initSegStack(&a->stack, sizeof(aNode_P),
247 sizeof(a->first_chunk), a->first_chunk);
248 a->work.location = p;
249 a->work.size = size;
250 a->work.depth = 0;
251 }
252
253
254 static void
clearTermAgenda_P(term_agenda_P * a)255 clearTermAgenda_P(term_agenda_P *a)
256 { clearSegStack(&a->stack);
257 }
258
259 #define nextTermAgenda_P(a) \
260 nextTermAgenda_P__LD(a PASS_LD)
261
262 static inline Word
nextTermAgenda_P__LD(term_agenda_P * a ARG_LD)263 nextTermAgenda_P__LD(term_agenda_P *a ARG_LD)
264 { Word p;
265
266 while ( a->work.size == 0 )
267 { size_t popn;
268 if ( (popn=a->work.depth) > 0 )
269 { a->work.depth = 0;
270 return AC_TERM_POP(popn);
271 }
272 if ( !popSegStack(&a->stack, &a->work, aNode_P) )
273 return NULL;
274 }
275
276 a->work.size--;
277 p = a->work.location++;
278 deRef(p);
279
280 return p;
281 }
282
283
284 /*******************************
285 * PUSH VARIATIONS *
286 *******************************/
287
288 static inline int
pushWorkAgenda_P(term_agenda_P * a,size_t amount,Word start)289 pushWorkAgenda_P(term_agenda_P *a, size_t amount, Word start)
290 { if ( a->work.size > 0 )
291 { if ( !pushSegStack(&a->stack, a->work, aNode_P) )
292 return FALSE;
293 a->work.depth = 1;
294 } else
295 a->work.depth++;
296
297 a->work.location = start;
298 a->work.size = amount;
299
300 return TRUE;
301 }
302
303 #endif /*!AC_TERM_WALK_POP*/
304
305 #if AC_TERM_WALK_LR
306
307 /*******************************
308 * OPERATIONS ON TWO TERMS *
309 *******************************/
310
311 typedef struct aNodeLR
312 { Word left; /* left term */
313 Word right; /* right term */
314 size_t size;
315 } aNodeLR;
316
317 typedef struct term_agendaLR
318 { aNodeLR work; /* current work */
319 segstack stack;
320 char first_chunk[256];
321 } term_agendaLR;
322
323
324 static void
initTermAgendaLR(term_agendaLR * a,size_t count,Word left,Word right)325 initTermAgendaLR(term_agendaLR *a, size_t count, Word left, Word right)
326 { initSegStack(&a->stack, sizeof(aNodeLR),
327 sizeof(a->first_chunk), a->first_chunk);
328 a->work.left = left;
329 a->work.right = right;
330 a->work.size = count;
331 }
332
333
334 static inline void
initTermAgendaLR0(term_agendaLR * a)335 initTermAgendaLR0(term_agendaLR *a)
336 { initSegStack(&a->stack, sizeof(aNodeLR),
337 sizeof(a->first_chunk), a->first_chunk);
338 a->work.size = 0;
339 }
340
341
342 static void
clearTermAgendaLR(term_agendaLR * a)343 clearTermAgendaLR(term_agendaLR *a)
344 { clearSegStack(&a->stack);
345 }
346
347
348 static int
nextTermAgendaLR(term_agendaLR * a,Word * lp,Word * rp)349 nextTermAgendaLR(term_agendaLR *a, Word *lp, Word *rp)
350 { if ( a->work.size > 0 )
351 { ok:
352 a->work.size--;
353 *lp = a->work.left++;
354 *rp = a->work.right++;
355
356 return TRUE;
357 }
358
359 if ( popSegStack(&a->stack, &a->work, aNodeLR) )
360 goto ok;
361
362 return FALSE;
363 }
364
365
366 static inline int
pushWorkAgendaLR(term_agendaLR * a,size_t amount,Word left,Word right)367 pushWorkAgendaLR(term_agendaLR *a, size_t amount, Word left, Word right)
368 { if ( a->work.size > 0 )
369 { if ( !pushSegStack(&a->stack, a->work, aNodeLR) )
370 return FALSE;
371 }
372 a->work.left = left;
373 a->work.right = right;
374 a->work.size = amount;
375
376 return TRUE;
377 }
378
379 #endif /*AC_TERM_WALK_LR*/
380
381 #if AC_TERM_WALK_LRD
382
383 /*************************************
384 * OPERATIONS ON TWO TERMS WITH DEPTH *
385 *************************************/
386
387 typedef struct aNodeLRD
388 { Word left; /* left term */
389 Word right; /* right term */
390 size_t size;
391 size_t depth;
392 } aNodeLRD;
393
394 typedef struct term_agendaLRD
395 { aNodeLRD work; /* current work */
396 segstack stack;
397 char first_chunk[256];
398 } term_agendaLRD;
399
400
401 static void
initTermAgendaLRD(term_agendaLRD * a,size_t count,Word left,Word right)402 initTermAgendaLRD(term_agendaLRD *a, size_t count, Word left, Word right)
403 { initSegStack(&a->stack, sizeof(aNodeLRD),
404 sizeof(a->first_chunk), a->first_chunk);
405 a->work.left = left;
406 a->work.right = right;
407 a->work.size = count;
408 a->work.depth = 0;
409 }
410
411
412 static inline void
initTermAgendaLRD0(term_agendaLRD * a)413 initTermAgendaLRD0(term_agendaLRD *a)
414 { initSegStack(&a->stack, sizeof(aNodeLRD),
415 sizeof(a->first_chunk), a->first_chunk);
416 a->work.size = 0;
417 }
418
419
420 static void
clearTermAgendaLRD(term_agendaLRD * a)421 clearTermAgendaLRD(term_agendaLRD *a)
422 { clearSegStack(&a->stack);
423 }
424
425
426 static int
nextTermAgendaLRD(term_agendaLRD * a,Word * lp,Word * rp)427 nextTermAgendaLRD(term_agendaLRD *a, Word *lp, Word *rp)
428 { if ( a->work.size > 0 )
429 { ok:
430 a->work.size--;
431 *lp = a->work.left++;
432 *rp = a->work.right++;
433
434 return TRUE;
435 }
436
437 if ( popSegStack(&a->stack, &a->work, aNodeLRD) )
438 goto ok;
439
440 return FALSE;
441 }
442
443
444 static inline int
pushWorkAgendaLRD(term_agendaLRD * a,size_t amount,Word left,Word right)445 pushWorkAgendaLRD(term_agendaLRD *a, size_t amount, Word left, Word right)
446 { if ( a->work.size > 0 )
447 { if ( !pushSegStack(&a->stack, a->work, aNodeLRD) )
448 return FALSE;
449 }
450 a->work.left = left;
451 a->work.right = right;
452 a->work.size = amount;
453 a->work.depth++;
454
455 return TRUE;
456 }
457
458 #endif /*AC_TERM_WALK_LRD*/
459
460 #if AC_TERM_WALK_LRS
461
462 /*******************************
463 * TWO TERMS WITH POP *
464 *******************************/
465
466 typedef struct aNodeLRS
467 { Functor left; /* left term */
468 Functor right; /* right term */
469 int arg;
470 int arity;
471 void *data;
472 } aNodeLRS;
473
474 typedef void (*popLRS)(Functor left, Functor right, void *data);
475
476 typedef struct term_agendaLRS
477 { aNodeLRS work; /* current work */
478 popLRS pop;
479 segstack stack;
480 char first_chunk[sizeof(aNodeLRS)*25];
481 } term_agendaLRS;
482
483
484 static void
initTermAgendaLRS(term_agendaLRS * a,Functor left,Functor right,popLRS pop,void * data)485 initTermAgendaLRS(term_agendaLRS *a,
486 Functor left, Functor right,
487 popLRS pop, void *data)
488 { initSegStack(&a->stack, sizeof(aNodeLRS),
489 sizeof(a->first_chunk), a->first_chunk);
490 a->pop = pop;
491 a->work.data = data;
492 a->work.left = left;
493 a->work.right = right;
494 a->work.arg = 0;
495 a->work.arity = arityFunctor(left->definition);
496 }
497
498
499 static void
clearTermAgendaLRS(term_agendaLRS * a)500 clearTermAgendaLRS(term_agendaLRS *a)
501 { do
502 { if ( a->work.arg != -1 )
503 (*a->pop)(a->work.left, a->work.right, a->work.data);
504 } while(popSegStack(&a->stack, &a->work, aNodeLRS));
505 }
506
507
508 #define nextTermAgendaLRS(a, lp, rp) \
509 nextTermAgendaLRS__LD(a, lp, rp PASS_LD)
510
511 static int
nextTermAgendaLRS__LD(term_agendaLRS * a,Word * lp,Word * rp ARG_LD)512 nextTermAgendaLRS__LD(term_agendaLRS *a, Word *lp, Word *rp ARG_LD)
513 { Word p;
514
515 while ( a->work.arg == a->work.arity )
516 { (*a->pop)(a->work.left, a->work.right, a->work.data);
517 a->work.arg = -1;
518 if ( !popSegStack(&a->stack, &a->work, aNodeLRS) )
519 return FALSE;
520 }
521
522 deRef2(&a->work.left->arguments[a->work.arg], p); *lp = p;
523 deRef2(&a->work.right->arguments[a->work.arg],p); *rp = p;
524 a->work.arg++;
525
526 return TRUE;
527 }
528
529
530 static int
pushWorkAgendaLRS(term_agendaLRS * a,Functor left,Functor right,void * data)531 pushWorkAgendaLRS(term_agendaLRS *a, Functor left, Functor right, void *data)
532 { if ( !pushSegStack(&a->stack, a->work, aNodeLRS) )
533 return FALSE;
534
535 a->work.data = data;
536 a->work.left = left;
537 a->work.right = right;
538 a->work.arg = 0;
539 a->work.arity = arityFunctor(left->definition);
540
541 return TRUE;
542 }
543
544 #endif /*AC_TERM_WALK_LRS*/
545
546