src/state-item.c

/* Counterexample Generation Search Nodes

   Copyright (C) 2020-2021 Free Software Foundation, Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */

#include <config.h>

#include "state-item.h"

#include <assert.h>
#include <gl_linked_list.h>
#include <gl_xlist.h>
#include <stdlib.h>
#include <time.h>

#include "closure.h"
#include "getargs.h"
#include "nullable.h"

size_t nstate_items;
state_item_number *state_item_map;
state_item *state_items;

// Hash functions for index -> bitset hash maps.
typedef struct
{
  int key;
  bitset l;
} hash_pair;

static size_t
hash_pair_hasher (const hash_pair *sl, size_t max)
{
  return sl->key % max;
}

static bool
hash_pair_comparator (const hash_pair *l, const hash_pair *r)
{
  return l->key == r->key;
}

static void
hash_pair_free (hash_pair *hp)
{
  bitset_free (hp->l);
  free (hp);
}

static Hash_table *
hash_pair_table_create (int size)
{
  return hash_xinitialize (size,
                           NULL,
                           (Hash_hasher) hash_pair_hasher,
                           (Hash_comparator) hash_pair_comparator,
                           (Hash_data_freer) hash_pair_free);
}

static bitset
hash_pair_lookup (Hash_table *tab, int key)
{
  hash_pair probe;
  probe.key = key;
  hash_pair *hp = hash_lookup (tab, &probe);
  return hp ? hp->l : NULL;
}

static void
hash_pair_insert (Hash_table *tab, int key, bitset val)
{
  hash_pair *hp = xmalloc (sizeof *hp);
  hp->key = key;
  hp->l = val;
  hash_pair *res = hash_xinsert (tab, hp);
  // This must be the first insertion.
  (void) res;
  assert (res == hp);
}

/* A state_item from a state's id and the offset of the item within
   the state. */
state_item *
state_item_lookup (state_number s, state_item_number off)
{
  return &state_items[state_item_index_lookup (s, off)];
}

static inline void
state_item_set (state_item_number sidx, const state *s, item_number off)
{
  state_items[sidx].state = s;
  state_items[sidx].item = &ritem[off];
  state_items[sidx].lookahead = NULL;
  state_items[sidx].trans = -1;
  state_items[sidx].prods = NULL;
  state_items[sidx].revs = bitset_create (nstate_items, BITSET_SPARSE);
}

/**
 * Initialize state_items set
 */
static void
init_state_items (void)
{
  nstate_items = 0;
  bitsetv production_items = bitsetv_create (nstates, nritems, BITSET_SPARSE);
  for (int i = 0; i < nstates; ++i)
    {
      const state *s = states[i];
      nstate_items += s->nitems;
      closure (s->items, s->nitems);
      for (size_t j = 0; j < nitemset; ++j)
        if (0 < itemset[j]
            && item_number_is_rule_number (ritem[itemset[j] - 1]))
          {
            bitset_set (production_items[i], itemset[j]);
            ++nstate_items;
          }
    }
  state_item_map = xnmalloc (nstates + 1, sizeof (state_item_number));
  state_items = xnmalloc (nstate_items, sizeof (state_item));
  state_item_number sidx = 0;
  for (int i = 0; i < nstates; ++i)
    {
      state_item_map[i] = sidx;
      int rule_search_idx = 0;
      const state *s = states[i];
      const reductions *red = s->reductions;
      for (int j = 0; j < s->nitems; ++j)
        {
          state_item_set (sidx, s, s->items[j]);
          state_item *si = &state_items[sidx];
          const rule *r = item_rule (si->item);
          if (rule_search_idx < red->num && red->rules[rule_search_idx] < r)
            ++rule_search_idx;
          if (rule_search_idx < red->num && r == red->rules[rule_search_idx])
            {
              bitsetv lookahead = red->lookaheads;
              if (lookahead)
                si->lookahead = lookahead[rule_search_idx];
            }
          ++sidx;
        }
      bitset_iterator biter;
      item_number off;
      BITSET_FOR_EACH (biter, production_items[i], off, 0)
        {
          state_item_set (sidx, s, off);
          if (item_number_is_rule_number (ritem[off]))
            {
              bitsetv lookahead = red->lookaheads;
              if (lookahead)
                state_items[sidx].lookahead = lookahead[rule_search_idx];
              ++rule_search_idx;
            }
          ++sidx;
        }

    }
  state_item_map[nstates] = nstate_items;
  bitsetv_free (production_items);
}

static size_t
state_sym_hasher (const void *st, size_t max)
{
  return ((state *) st)->accessing_symbol % max;
}

static bool
state_sym_comparator (const void *s1, const void *s2)
{
  return ((state *) s1)->accessing_symbol == ((state *) s2)->accessing_symbol;
}

static state *
state_sym_lookup (symbol_number sym, Hash_table *h)
{
  state probe;
  probe.accessing_symbol = sym;
  return hash_lookup (h, &probe);
}

static void
init_trans (void)
{
  for (state_number i = 0; i < nstates; ++i)
    {
      // Generate a hash set that maps from accepting symbols to the states
      // this state transitions to.
      state *s = states[i];
      transitions *t = s->transitions;
      Hash_table *transition_set
        = hash_xinitialize (t->num, NULL, (Hash_hasher) state_sym_hasher,
                            (Hash_comparator) state_sym_comparator, NULL);
      for (int j = 0; j < t->num; ++j)
        if (!TRANSITION_IS_DISABLED (t, j))
          hash_xinsert (transition_set, t->states[j]);
      for (state_item_number j = state_item_map[i]; j < state_item_map[i + 1]; ++j)
        {
          item_number *item = state_items[j].item;
          if (item_number_is_rule_number (*item))
            continue;
          state *dst = state_sym_lookup (*item, transition_set);
          if (!dst)
            continue;
          // find the item in the destination state that corresponds
          // to the transition of item
          for (int k = 0; k < dst->nitems; ++k)
            if (item + 1 == ritem + dst->items[k])
              {
                state_item_number dstSI =
                  state_item_index_lookup (dst->number, k);

                state_items[j].trans = dstSI;
                bitset_set (state_items[dstSI].revs, j);
                break;
            }
        }
      hash_free (transition_set);
    }
}

static void
init_prods (void)
{
  for (int i = 0; i < nstates; ++i)
    {
      state *s = states[i];
      // closure_map is a hash map from nonterminals to a set
      // of the items that produce those nonterminals
      Hash_table *closure_map = hash_pair_table_create (nsyms - ntokens);

      // Add the nitems of state to skip to the production portion
      // of that state's state_items
      for (state_item_number j = state_item_map[i] + s->nitems;
           j < state_item_map[i + 1]; ++j)
        {
          state_item *src = &state_items[j];
          item_number *item = src->item;
          symbol_number lhs = item_rule (item)->lhs->number;
          bitset itms = hash_pair_lookup (closure_map, lhs);
          if (!itms)
            {
              itms = bitset_create (nstate_items, BITSET_SPARSE);
              hash_pair_insert (closure_map, lhs, itms);
            }
          bitset_set (itms, j);
        }
      // For each item with a dot followed by a nonterminal,
      // try to create a production edge.
      for (state_item_number j = state_item_map[i]; j < state_item_map[i + 1]; ++j)
        {
          state_item *src = &state_items[j];
          item_number item = *(src->item);
          // Skip reduce items and items with terminals after the dot
          if (item_number_is_rule_number (item) || ISTOKEN (item))
            continue;
          symbol_number sym = item_number_as_symbol_number (item);
          bitset lb = hash_pair_lookup (closure_map, sym);
          if (lb)
            {
              bitset copy = bitset_create (nstate_items, BITSET_SPARSE);
              bitset_copy (copy, lb);
              // update prods.
              state_items[j].prods = copy;

              // update revs.
              bitset_iterator biter;
              state_item_number prod;
              BITSET_FOR_EACH (biter, copy, prod, 0)
                bitset_set (state_items[prod].revs, j);
            }
        }
      hash_free (closure_map);
    }
}

/* Since lookaheads are only generated for reductions, we need to
   propagate lookahead sets backwards as the searches require each
   state_item to have a lookahead. */
static inline void
gen_lookaheads (void)
{
  for (state_item_number i = 0; i < nstate_items; ++i)
    {
      state_item *si = &state_items[i];
      if (item_number_is_symbol_number (*(si->item)) || !si->lookahead)
        continue;

      bitset lookahead = si->lookahead;
      state_item_list queue =
        gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
                        (const void **) &si);

      // For each reduction item, traverse through all state_items
      // accessible through reverse transition steps, and set their
      // lookaheads to the reduction items lookahead
      while (gl_list_size (queue) > 0)
        {
          state_item *prev = (state_item *) gl_list_get_at (queue, 0);
          gl_list_remove_at (queue, 0);
          prev->lookahead = lookahead;
          if (SI_TRANSITION (prev))
            {
              bitset rsi = state_items[prev - state_items].revs;
              bitset_iterator biter;
              state_item_number sin;
              BITSET_FOR_EACH (biter, rsi, sin, 0)
                gl_list_add_first (queue, &state_items[sin]);
            }
        }
      gl_list_free (queue);
    }
}

bitsetv firsts = NULL;

static void
init_firsts (void)
{
  firsts = bitsetv_create (nnterms, nsyms, BITSET_FIXED);
  for (rule_number i = 0; i < nrules; ++i)
    {
      rule *r = &rules[i];
      item_number *n = r->rhs;
      // Iterate through nullable nonterminals to try to find a terminal.
      while (item_number_is_symbol_number (*n) && ISVAR (*n)
             && nullable[*n - ntokens])
        ++n;
      if (item_number_is_rule_number (*n) || ISVAR (*n))
        continue;

      symbol_number lhs = r->lhs->number;
      bitset_set (FIRSTS (lhs), *n);
    }
  bool change = true;
  while (change)
    {
      change = false;
      for (rule_number i = 0; i < nrules; ++i)
        {
          rule *r = &rules[i];
          symbol_number lhs = r->lhs->number;
          bitset f_lhs = FIRSTS (lhs);
          for (item_number *n = r->rhs;
               item_number_is_symbol_number (*n) && ISVAR (*n);
               ++n)
            {
              bitset f = FIRSTS (*n);
              if (!bitset_subset_p (f_lhs, f))
                {
                  change = true;
                  bitset_union (f_lhs, f_lhs, f);
                }
              if (!nullable[*n - ntokens])
                break;
            }
        }
    }
}

static inline void
disable_state_item (state_item *si)
{
  si->trans = -2;
  bitset_free (si->revs);
  if (si->prods)
    bitset_free (si->prods);
}

/* Disable all state_item paths that lead to/from SI and nowhere
   else.  */
static void
prune_state_item (const state_item *si)
{
  state_item_list queue =
    gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
                    (const void **) &si);

  while (gl_list_size (queue) > 0)
    {
      state_item *dsi = (state_item *) gl_list_get_at (queue, 0);
      gl_list_remove_at (queue, 0);
      if (SI_DISABLED (dsi - state_items))
        continue;

      if (dsi->trans >= 0 && !SI_DISABLED (dsi->trans))
      {
        const state_item *trans = &state_items[dsi->trans];
        bitset_reset (trans->revs, dsi - state_items);
        if (bitset_empty_p (trans->revs))
          gl_list_add_last (queue, trans);
      }

      if (dsi->prods)
        {
          bitset_iterator biter;
          state_item_number sin;
          BITSET_FOR_EACH (biter, dsi->prods, sin, 0)
            {
              if (SI_DISABLED (sin))
                continue;
              const state_item *prod = &state_items[sin];
              bitset_reset (prod->revs, dsi - state_items);
              if (bitset_empty_p (prod->revs))
                gl_list_add_last (queue, prod);
            }
        }

      bitset_iterator biter;
      state_item_number sin;
      BITSET_FOR_EACH (biter, dsi->revs, sin, 0)
        {
          if (SI_DISABLED (sin))
            continue;
          state_item *rev = &state_items[sin];
          if (&state_items[rev->trans] == dsi)
            gl_list_add_last (queue, rev);
          else if (rev->prods)
            {
              bitset_reset (rev->prods, dsi - state_items);
              if (bitset_empty_p (rev->prods))
                gl_list_add_last (queue, rev);
            }
          else
            gl_list_add_last (queue, rev);
        }
      disable_state_item (dsi);
    }
  gl_list_free (queue);
}

/* To make searches more efficient, prune away paths that are caused
   by disabled transitions.  */
static void
prune_disabled_paths (void)
{
  for (int i = nstate_items - 1; i >= 0; --i)
    {
      state_item *si = &state_items[i];
      if (si->trans == -1 && item_number_is_symbol_number (*si->item))
        prune_state_item (si);
    }
}

void
state_item_print (const state_item *si, FILE *out, const char *prefix)
{
  fputs (prefix, out);
  item_print (si->item, NULL, out);
  putc ('\n', out);
}

const rule*
state_item_rule (const state_item *si)
{
  return item_rule (si->item);
}

/**
 * Report the state_item graph
 */
static void
state_items_report (FILE *out)
{
  fprintf (out, "# state items: %zu\n", nstate_items);
  for (state_number i = 0; i < nstates; ++i)
    {
      fprintf (out, "State %d:\n", i);
      for (state_item_number j = state_item_map[i]; j < state_item_map[i + 1]; ++j)
        {
          const state_item *si = &state_items[j];
          item_print (si->item, NULL, out);
          if (SI_DISABLED (j))
            fputs ("  DISABLED\n", out);
          else
            {
              putc ('\n', out);
              if (si->trans >= 0)
                {
                  fputs ("    -> ", out);
                  state_item_print (&state_items[si->trans], out, "");
                }

              bitset sets[2] = { si->prods, si->revs };
              const char *txt[2] = { "    => ", "    <- " };
              for (int seti = 0; seti < 2; ++seti)
                {
                  bitset b = sets[seti];
                  if (b)
                    {
                      bitset_iterator biter;
                      state_item_number sin;
                      BITSET_FOR_EACH (biter, b, sin, 0)
                        {
                          fputs (txt[seti], out);
                          state_item_print (&state_items[sin], out, "");
                        }
                    }
                }
            }
          putc ('\n', out);
        }
    }
  fprintf (out, "FIRSTS\n");
  for (symbol_number i = ntokens; i < nsyms; ++i)
    {
      fprintf (out, "  %s firsts\n", symbols[i]->tag);
      bitset_iterator iter;
      symbol_number j;
      BITSET_FOR_EACH (iter, FIRSTS (i), j, 0)
        fprintf (out, "    %s\n", symbols[j]->tag);
    }
  fputs ("\n\n", out);
}

void
state_items_init (void)
{
  time_t start = time (NULL);
  init_state_items ();
  init_trans ();
  init_prods ();
  gen_lookaheads ();
  init_firsts ();
  prune_disabled_paths ();
  if (trace_flag & trace_cex)
    {
      fprintf (stderr, "init: %f\n", difftime (time (NULL), start));
      state_items_report (stderr);
    }
}

void
state_items_free (void)
{
  for (state_item_number i = 0; i < nstate_items; ++i)
    if (!SI_DISABLED (i))
      {
        state_item *si = &state_items[i];
        if (si->prods)
          bitset_free (si->prods);
        bitset_free (si->revs);
      }
  free (state_items);
  bitsetv_free (firsts);
}

/**
 * Determine, using precedence and associativity, whether the next
 * production is allowed from the current production.
 */
bool
production_allowed (const state_item *si, const state_item *next)
{
  sym_content *s1 = item_rule (si->item)->lhs;
  sym_content *s2 = item_rule (next->item)->lhs;
  int prec1 = s1->prec;
  int prec2 = s2->prec;
  if (prec1 >= 0 && prec2 >= 0)
    {
      // Do not expand if lower precedence.
      if (prec1 > prec2)
        return false;
      // Do not expand if same precedence, but left-associative.
      if (prec1 == prec2 && s1->assoc == left_assoc)
        return false;
    }
  return true;
}