src/state-item.h

   1 /* Counterexample Generation Search Nodes
   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 #ifndef STATE_ITEM_H
  21 # define STATE_ITEM_H
  22
  23 # include <bitsetv.h>
  24 # include <gl_list.h>
  25 # include <hash.h>
  26
  27 # include "gram.h"
  28 # include "state.h"
  29
  30 /* Initializes a graph connecting (state, production item) pairs to
  31    pairs they can make a transition or production step to.  This graph
  32    is used to search for paths that represent counterexamples of some
  33    conflict.
  34
  35    state_items is an array of state state-item pairs ordered by state.
  36    state_item_map maps state numbers to the first item which
  37    corresponds to it in the array.  A state's portion in state_items
  38    begins with its items in the same order as it was in the state.
  39    This is then followed by productions from the closure of the state
  40    in order by rule.
  41
  42    There are two type of edges in this graph transitions and
  43    productions.  Transitions are the same as transitions from the
  44    parser except edges are only between items from the same
  45    rule.
  46
  47    Productions are edges from items with a nonterminal after the dot to
  48    the production of that nonterminal in the same state. These edges are
  49    stored as a bitset in a state-item.
  50
  51    The inverses of these edges are stored in a bitset in the state-item,
  52    "revs."  A state-item that begins with a dot will have reverse
  53    production edges, and all others will have reverse transition
  54    edges. */
  55
  56 # define SI_DISABLED(Sin) (state_items[Sin].trans == -2)
  57 # define SI_PRODUCTION(Si) ((Si) == state_items || *((Si)->item - 1) < 0)
  58 # define SI_TRANSITION(Si) ((Si) != state_items && *((Si)->item - 1) >= 0)
  59
  60 typedef int state_item_number;
  61
  62 typedef struct
  63 {
  64   const state *state;
  65   item_number *item;
  66   state_item_number trans;
  67   bitset prods;
  68   bitset revs;
  69   bitset lookahead;
  70 } state_item;
  71
  72 // A path of state-items.
  73 typedef gl_list_t state_item_list;
  74
  75 extern bitsetv firsts;
  76 # define FIRSTS(sym) firsts[(sym) - ntokens]
  77
  78 extern size_t nstate_items;
  79 extern state_item_number *state_item_map;
  80
  81 /** Array mapping state_item_numbers to state_items */
  82 extern state_item *state_items;
  83
  84 state_item *state_item_lookup (state_number s, state_item_number off);
  85
  86 static inline state_item_number
  87 state_item_index_lookup (state_number s, state_item_number off)
  88 {
  89   return state_item_map[s] + off;
  90 }
  91
  92 void state_items_init (void);
  93 void state_items_free (void);
  94
  95 void state_item_print (const state_item *si, FILE *out, const char *prefix);
  96 const rule *state_item_rule (const state_item *si);
  97
  98 bool production_allowed (const state_item *si, const state_item *next);
  99
 100 // Iterating on a state_item_list.
 101 static inline bool
 102 state_item_list_next (gl_list_iterator_t *it, state_item **si)
 103 {
 104   const void *p = NULL;
 105   bool res = gl_list_iterator_next (it, &p, NULL);
 106   if (res)
 107     *si = (state_item *) p;
 108   else
 109     gl_list_iterator_free (it);
 110   return res;
 111 }
 112
 113
 114 #endif /* STATE_ITEM_H */