1 /* Parser simulator for unifying counterexample search
2
3 Copyright (C) 2020-2021 Free Software Foundation, Inc.
4
5 This file is part of Bison, the GNU Compiler Compiler.
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <https://www.gnu.org/licenses/>. */
19
20 #include <config.h>
21
22 #include "parse-simulation.h"
23
24 #include <gl_linked_list.h>
25 #include <gl_xlist.h>
26 #include <stdlib.h>
27
28 #include "lssi.h"
29 #include "nullable.h"
30
31 struct parse_state
32 {
33 // Path of state-items the parser has traversed.
34 struct si_chunk
35 {
36 // Elements newly added in this chunk.
37 state_item_list contents;
38 // Properties of the linked list this chunk represents.
39 const state_item *head_elt;
40 const state_item *tail_elt;
41 size_t total_size;
42 } state_items;
43 // List of derivations of the symbols.
44 struct deriv_chunk
45 {
46 derivation_list contents;
47 const derivation *head_elt;
48 const derivation *tail_elt;
49 size_t total_size;
50 } derivs;
51 struct parse_state *parent;
52 int reference_count;
53 // Incremented during productions, decremented during reductions.
54 int depth;
55 // Whether the contents of the chunks should be prepended or
56 // appended to the list the chunks represent.
57 bool prepend;
58 // Causes chunk contents to be freed when the reference count is
59 // one. Used when only the chunk metadata will be needed.
60 bool free_contents_early;
61 };
62
63
64 static void
65 ps_si_prepend (parse_state *ps, const state_item *si)
66 {
67 struct si_chunk *sic = &ps->state_items;
68 gl_list_add_first (sic->contents, si);
69 sic->head_elt = si;
70 ++sic->total_size;
71 if (!sic->tail_elt)
72 sic->tail_elt = si;
73 }
74
75 static void
76 ps_si_append (parse_state *ps, const state_item *si)
77 {
78 struct si_chunk *sic = &ps->state_items;
79 gl_list_add_last (sic->contents, si);
80 sic->tail_elt = si;
81 ++sic->total_size;
82 if (!sic->head_elt)
83 sic->head_elt = si;
84 }
85
86 static void
87 ps_derivs_prepend (parse_state *ps, derivation *d)
88 {
89 struct deriv_chunk *dc = &ps->derivs;
90 derivation_list_prepend (dc->contents, d);
91 dc->head_elt = d;
92 ++dc->total_size;
93 if (!dc->tail_elt)
94 dc->tail_elt = d;
95 }
96
97 static void
98 ps_derivs_append (parse_state *ps, derivation *d)
99 {
100 struct deriv_chunk *dc = &ps->derivs;
101 derivation_list_append (dc->contents, d);
102 dc->tail_elt = d;
103 ++dc->total_size;
104 if (!dc->head_elt)
105 dc->head_elt = d;
106 }
107
108 static int allocs = 0;
109 static int frees = 0;
110
111 static parse_state *
112 empty_parse_state (void)
113 {
114 parse_state *res = xcalloc (1, sizeof *res);
115 res->state_items.contents
116 = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
117 res->derivs.contents = derivation_list_new ();
118 ++allocs;
119 return res;
120 }
121
122 parse_state *
123 new_parse_state (const state_item *si)
124 {
125 parse_state *res = empty_parse_state ();
126 ps_si_append (res, si);
127 ps_derivs_append (res, derivation_dot ());
128 return res;
129 }
130
131 static parse_state *
132 copy_parse_state (bool prepend, parse_state *parent)
133 {
134 parse_state *res = xmalloc (sizeof *res);
135 *res = *parent;
136 res->state_items.contents
137 = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
138 res->derivs.contents = derivation_list_new ();
139 res->parent = parent;
140 res->prepend = prepend;
141 res->reference_count = 0;
142 res->free_contents_early = false;
143 parse_state_retain (parent);
144 ++allocs;
145 return res;
146 }
147
148 bool
149 parse_state_derivation_completed (const parse_state *ps)
150 {
151 return ps->derivs.total_size == 1;
152 }
153
154 derivation *
155 parse_state_derivation (const parse_state *ps)
156 {
157 return (derivation *) ps->derivs.head_elt;
158 }
159
160 const state_item *
161 parse_state_head (const parse_state *ps)
162 {
163 return ps->state_items.head_elt;
164 }
165
166 const state_item *
167 parse_state_tail (const parse_state *ps)
168 {
169 return ps->state_items.tail_elt;
170 }
171
172 int
173 parse_state_length (const parse_state *ps)
174 {
175 return ps->state_items.total_size;
176 }
177
178 int
179 parse_state_depth (const parse_state *ps)
180 {
181 return ps->depth;
182 }
183
184 void
185 parse_state_retain (parse_state *ps)
186 {
187 ++ps->reference_count;
188 }
189
190 void
191 parse_state_free_contents_early (parse_state *ps)
192 {
193 ps->free_contents_early = true;
194 }
195
196 void
197 free_parse_state (parse_state *original_ps)
198 {
199 bool free_contents = true;
200 parse_state *parent_ps = NULL;
201 for (parse_state *ps = original_ps; ps && free_contents; ps = parent_ps)
202 {
203 --ps->reference_count;
204 free_contents = (ps->reference_count == 1 && ps->free_contents_early)
205 || (ps->reference_count == 0 && !ps->free_contents_early);
206 // need to keep the parse state around for visited hash set,
207 // but its contents and parent can be freed
208 if (free_contents)
209 {
210 if (ps->state_items.contents)
211 gl_list_free (ps->state_items.contents);
212 if (ps->derivs.contents)
213 derivation_list_free (ps->derivs.contents);
214 }
215 parent_ps = ps->parent;
216 if (ps->reference_count <= 0)
217 {
218 free (ps);
219 ++frees;
220 }
221 }
222 }
223
224 size_t
225 parse_state_hasher (const parse_state *ps, size_t max)
226 {
227 const struct si_chunk *sis = &ps->state_items;
228 return ((state_item *) sis->head_elt - state_items +
229 (state_item *) sis->tail_elt - state_items + sis->total_size) % max;
230 }
231
232 bool
233 parse_state_comparator (const parse_state *ps1, const parse_state *ps2)
234 {
235 const struct si_chunk *sis1 = &ps1->state_items;
236 const struct si_chunk *sis2 = &ps2->state_items;
237 return sis1->head_elt == sis2->head_elt
238 && sis1->tail_elt == sis2->tail_elt
239 && sis1->total_size == sis2->total_size;
240 }
241
242
243 void
244 parse_state_completed_steps (const parse_state *ps, int *shifts, int *productions)
245 {
246 // traverse to the root parse_state,
247 // which will have a list of all completed productions.
248 const parse_state *root_ps = ps;
249 while (root_ps->parent)
250 root_ps = root_ps->parent;
251
252 state_item_list sis = root_ps->state_items.contents;
253 int count = 0;
254
255 state_item *last = NULL;
256 state_item *next = NULL;
257 for (gl_list_iterator_t it = gl_list_iterator (sis);
258 state_item_list_next (&it, &next);
259 )
260 {
261 if (last && last->state == next->state)
262 ++count;
263 last = next;
264 }
265 *productions = count;
266 *shifts = root_ps->state_items.total_size - count;
267 }
268
269 typedef void (*chunk_append_fn) (gl_list_t, const void *);
270
271 // A version of gl_list_add_last which has the chunk_append_fn
272 // signature.
273 static void
274 list_add_last (gl_list_t list, const void *elt)
275 {
276 gl_list_add_last (list, elt);
277 }
278
279 // takes an array of n gl_lists and flattens them into two list
280 // based off of the index split
281 static void
282 list_flatten_and_split (gl_list_t *list, gl_list_t *rets, int split, int n,
283 chunk_append_fn append_fn)
284 {
285 int ret_index = 0;
286 int ret_array = 0;
287 for (int i = 0; i < n; ++i)
288 {
289 const void *p = NULL;
290 gl_list_iterator_t it = gl_list_iterator (list[i]);
291 while (gl_list_iterator_next (&it, &p, NULL))
292 if (p)
293 {
294 gl_list_t l = (gl_list_t) p;
295 const void *si = NULL;
296 gl_list_iterator_t it2 = gl_list_iterator (l);
297 while (gl_list_iterator_next (&it2, &si, NULL))
298 {
299 if (ret_index++ == split)
300 ++ret_array;
301 if (rets[ret_array])
302 append_fn (rets[ret_array], si);
303 }
304 gl_list_iterator_free (&it2);
305 }
306 gl_list_iterator_free (&it);
307 }
308 }
309
310 static parse_state_list
311 parse_state_list_new (void)
312 {
313 return gl_list_create_empty (GL_LINKED_LIST, NULL, NULL,
314 (gl_listelement_dispose_fn)free_parse_state,
315 true);
316 }
317
318 static void
319 parse_state_list_append (parse_state_list pl, parse_state *ps)
320 {
321 parse_state_retain (ps);
322 gl_list_add_last (pl, ps);
323 }
324
325 // Emulates a reduction on a parse state by popping some amount of
326 // derivations and state_items off of the parse_state and returning
327 // the result in ret. Returns the derivation of what's popped.
328 static derivation_list
329 parser_pop (parse_state *ps, int deriv_index,
330 int si_index, parse_state *ret)
331 {
332 // prepend sis, append sis, prepend derivs, append derivs
333 gl_list_t chunks[4];
334 for (int i = 0; i < 4; ++i)
335 chunks[i] = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
336 for (parse_state *pn = ps; pn != NULL; pn = pn->parent)
337 if (pn->prepend)
338 {
339 gl_list_add_last (chunks[0], pn->state_items.contents);
340 gl_list_add_last (chunks[2], pn->derivs.contents);
341 }
342 else
343 {
344 gl_list_add_first (chunks[1], pn->state_items.contents);
345 gl_list_add_first (chunks[3], pn->derivs.contents);
346 }
347 derivation_list popped_derivs = derivation_list_new ();
348 gl_list_t ret_chunks[4] = { ret->state_items.contents, NULL,
349 ret->derivs.contents, popped_derivs
350 };
351 list_flatten_and_split (chunks, ret_chunks, si_index, 2,
352 list_add_last);
353 list_flatten_and_split (chunks + 2, ret_chunks + 2, deriv_index, 2,
354 (chunk_append_fn)derivation_list_append);
355 size_t s_size = gl_list_size (ret->state_items.contents);
356 ret->state_items.total_size = s_size;
357 if (s_size > 0)
358 {
359 ret->state_items.tail_elt = gl_list_get_at (ret->state_items.contents,
360 s_size - 1);
361 ret->state_items.head_elt =
362 gl_list_get_at (ret->state_items.contents, 0);
363 }
364 else
365 {
366 ret->state_items.tail_elt = NULL;
367 ret->state_items.head_elt = NULL;
368 }
369 size_t d_size = gl_list_size (ret->derivs.contents);
370 ret->derivs.total_size = d_size;
371 if (d_size > 0)
372 {
373 ret->derivs.tail_elt = gl_list_get_at (ret->derivs.contents,
374 d_size - 1);
375 ret->derivs.head_elt = gl_list_get_at (ret->derivs.contents, 0);
376 }
377 else
378 {
379 ret->derivs.tail_elt = NULL;
380 ret->derivs.head_elt = NULL;
381 }
382 for (int i = 0; i < 4; ++i)
383 gl_list_free (chunks[i]);
384 return popped_derivs;
385 }
386
387 void
388 parse_state_lists (parse_state *ps, state_item_list *sitems,
389 derivation_list *derivs)
390 {
391 parse_state *temp = empty_parse_state ();
392 size_t si_size = ps->state_items.total_size;
393 size_t deriv_size = ps->derivs.total_size;
394 derivation_list dl = parser_pop (ps, si_size, deriv_size, temp);
395 *sitems = temp->state_items.contents;
396 *derivs = temp->derivs.contents;
397 // prevent the return lists from being freed
398 temp->state_items.contents = NULL;
399 temp->derivs.contents = NULL;
400 free_parse_state (temp);
401 derivation_list_free (dl);
402 }
403
404 /**
405 * Compute the parse states that result from taking a transition on
406 * nullable symbols whenever possible from the given state_item.
407 */
408 static void
409 nullable_closure (parse_state *ps, state_item *si, parse_state_list state_list)
410 {
411 parse_state *current_ps = ps;
412 state_item_number prev_sin = si - state_items;
413 for (state_item_number sin = si->trans; sin != -1;
414 prev_sin = sin, sin = state_items[sin].trans)
415 {
416 state_item *psi = &state_items[prev_sin];
417 symbol_number sp = item_number_as_symbol_number (*psi->item);
418 if (ISTOKEN (sp) || !nullable[sp - ntokens])
419 break;
420
421 state_item *nsi = &state_items[sin];
422 current_ps = copy_parse_state (false, current_ps);
423 ps_si_append (current_ps, nsi);
424 ps_derivs_append (current_ps,
425 derivation_new (sp, derivation_list_new (),
426 state_item_rule (nsi)));
427 parse_state_list_append (state_list, current_ps);
428 }
429 }
430
431 parse_state_list
432 simulate_transition (parse_state *ps)
433 {
434 const state_item *si = ps->state_items.tail_elt;
435 symbol_number sym = item_number_as_symbol_number (*si->item);
436 // Transition on the same next symbol, taking nullable
437 // symbols into account.
438 parse_state_list result = parse_state_list_new ();
439 state_item_number si_next = si->trans;
440 // Check for disabled transition, shouldn't happen as any
441 // state_items that lead to these should be disabled.
442 if (si_next < 0)
443 return result;
444 parse_state *next_ps = copy_parse_state (false, ps);
445 ps_si_append (next_ps, &state_items[si_next]);
446 ps_derivs_append (next_ps, derivation_new_leaf (sym));
447 parse_state_list_append (result, next_ps);
448
449 nullable_closure (next_ps, &state_items[si_next], result);
450 return result;
451 }
452
453 /**
454 * Determine if the given symbols are equal or their first sets
455 * intersect.
456 */
457 static bool
458 compatible (symbol_number sym1, symbol_number sym2)
459 {
460 if (sym1 == sym2)
461 return true;
462 if (ISTOKEN (sym1) && ISVAR (sym2))
463 return bitset_test (FIRSTS (sym2), sym1);
464 else if (ISVAR (sym1) && ISTOKEN (sym2))
465 return bitset_test (FIRSTS (sym1), sym2);
466 else if (ISVAR (sym1) && ISVAR (sym2))
467 return !bitset_disjoint_p (FIRSTS (sym1), FIRSTS (sym2));
468 else
469 return false;
470 }
471
472 parse_state_list
473 simulate_production (parse_state *ps, symbol_number compat_sym)
474 {
475 parse_state_list result = parse_state_list_new ();
476 const state_item *si = parse_state_tail (ps);
477 if (si->prods)
478 {
479 bitset_iterator biter;
480 state_item_number sin;
481 BITSET_FOR_EACH (biter, si->prods, sin, 0)
482 {
483 // Take production step only if lhs is not nullable and
484 // if first rhs symbol is compatible with compat_sym
485 state_item *next = &state_items[sin];
486 item_number *itm1 = next->item;
487 if (!compatible (*itm1, compat_sym) || !production_allowed (si, next))
488 continue;
489 parse_state *next_ps = copy_parse_state (false, ps);
490 ps_si_append (next_ps, next);
491 parse_state_list_append (result, next_ps);
492 if (next_ps->depth >= 0)
493 ++next_ps->depth;
494 nullable_closure (next_ps, next, result);
495 }
496 }
497 return result;
498 }
499
500 // simulates a reduction on the given parse state, conflict_item is the
501 // item associated with ps's conflict. symbol_set is a lookahead set this
502 // reduction must be compatible with
503 parse_state_list
504 simulate_reduction (parse_state *ps, int rule_len, bitset symbol_set)
505 {
506 parse_state_list result = parse_state_list_new ();
507
508 int s_size = ps->state_items.total_size;
509 int d_size = ps->derivs.total_size;
510 if (ps->depth >= 0)
511 d_size--; // account for dot
512 parse_state *new_root = empty_parse_state ();
513 derivation_list popped_derivs =
514 parser_pop (ps, d_size - rule_len,
515 s_size - rule_len - 1, new_root);
516
517 // update derivation
518 state_item *si = (state_item *) ps->state_items.tail_elt;
519 const rule *r = item_rule (si->item);
520 symbol_number lhs = r->lhs->number;
521 derivation *deriv = derivation_new (lhs, popped_derivs, state_item_rule (si));
522 --new_root->depth;
523 ps_derivs_append (new_root, deriv);
524
525 if (s_size != rule_len + 1)
526 {
527 state_item *tail = (state_item *) new_root->state_items.tail_elt;
528 ps_si_append (new_root, &state_items[tail->trans]);
529 parse_state_list_append (result, new_root);
530 }
531 else
532 {
533 // The head state_item is a production item, so we need to prepend
534 // with possible source state-items.
535 const state_item *head = ps->state_items.head_elt;
536 state_item_list prev = lssi_reverse_production (head, symbol_set);
537 // TODO: better understand what causes this case.
538 if (gl_list_size (prev) == 0)
539 {
540 // new_root needs to have an RC of 1 to be freed correctly here.
541 parse_state_retain (new_root);
542 free_parse_state (new_root);
543 }
544 else
545 {
546 state_item *psis = NULL;
547 for (gl_list_iterator_t it = gl_list_iterator (prev);
548 state_item_list_next (&it, &psis);
549 )
550 {
551 // Prepend the result from the reverse production.
552 parse_state *copy = copy_parse_state (true, new_root);
553 ps_si_prepend (copy, psis);
554
555 // Append the left hand side to the end of the parser state
556 copy = copy_parse_state (false, copy);
557 struct si_chunk *sis = ©->state_items;
558 const state_item *tail = sis->tail_elt;
559 ps_si_append (copy, &state_items[tail->trans]);
560 parse_state_list_append (result, copy);
561 nullable_closure (copy, (state_item *) sis->tail_elt, result);
562 }
563 }
564 gl_list_free (prev);
565 }
566 return result;
567 }
568
569 parse_state_list
570 parser_prepend (parse_state *ps)
571 {
572 parse_state_list res = parse_state_list_new ();
573 const state_item *head = ps->state_items.head_elt;
574 symbol_number prepend_sym =
575 item_number_as_symbol_number (*(head->item - 1));
576 bitset_iterator biter;
577 state_item_number sin;
578 BITSET_FOR_EACH (biter, head->revs, sin, 0)
579 {
580 parse_state *copy = copy_parse_state (true, ps);
581 ps_si_prepend (copy, &state_items[sin]);
582 if (SI_TRANSITION (head))
583 ps_derivs_prepend (copy, derivation_new_leaf (prepend_sym));
584 parse_state_list_append (res, copy);
585 }
586 return res;
587 }
588
589 void
590 print_parse_state (parse_state *ps)
591 {
592 FILE *out = stderr;
593 fprintf (out, "(size %zu depth %d rc %d)\n",
594 ps->state_items.total_size, ps->depth, ps->reference_count);
595 state_item_print (ps->state_items.head_elt, out, "");
596 state_item_print (ps->state_items.tail_elt, out, "");
597 if (ps->derivs.total_size > 0)
598 derivation_print (ps->derivs.head_elt, out, "");
599 putc ('\n', out);
600 }