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 */