src/lssi.c

/* Lookahead sensitive state item searches for counterexample generation

   Copyright (C) 2020-2022 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 "lssi.h"

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

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

// Lookahead sensitive state item.
typedef struct lssi
{
  state_item_number si;
  struct lssi *parent;
  // this is the precise lookahead set (follow_L from the CupEx paper)
  bitset lookahead;
  bool free_lookahead;
} lssi;

static lssi *
new_lssi (state_item_number si, lssi *p, bitset l, bool free_l)
{
  lssi *res = xmalloc (sizeof *res);
  res->si = si;
  res->parent = p;
  res->lookahead = l;
  res->free_lookahead = free_l;
  return res;
}

static void
lssi_free (lssi *sn)
{
  if (sn == NULL)
    return;
  if (sn->free_lookahead)
    bitset_free (sn->lookahead);
  free (sn);
}

static size_t
lssi_hasher (lssi *sn, size_t max)
{
  size_t hash = sn->si;
  bitset_iterator biter;
  symbol_number syn;
  BITSET_FOR_EACH (biter, sn->lookahead, syn, 0)
    hash += syn;
  return hash % max;
}

static bool
lssi_comparator (lssi *s1, lssi *s2)
{
  if (s1->si == s2->si)
    {
      if (s1->lookahead == s2->lookahead)
        return true;
      return bitset_equal_p (s1->lookahead, s2->lookahead);
    }
  return false;
}

typedef gl_list_t lssi_list;

static inline bool
append_lssi (lssi *sn, Hash_table *visited, lssi_list queue)
{
  if (hash_lookup (visited, sn))
    {
      sn->free_lookahead = false;
      lssi_free (sn);
      return false;
    }
  hash_xinsert (visited, sn);
  gl_list_add_last (queue, sn);
  return true;
}

#if 0
static void
lssi_print (lssi *l)
{
  FILE *out = stderr;
  print_state_item (&state_items[l->si], out);
  if (l->lookahead)
    {
      fprintf (out, "FOLLOWL = { ");
      bitset_iterator biter;
      symbol_number sin;
      BITSET_FOR_EACH (biter, l->lookahead, sin, 0)
        fprintf (out, "%s, \n", symbols[sin]->tag);
      fprintf (out, "}\n");
    }
}
#endif

/**
 * Compute the set of state-items that can reach the given conflict item via
 * a combination of transitions or production steps.
 */
static bitset
eligible_state_items (state_item *target)
{
  bitset result = bitset_create (nstate_items, BITSET_FIXED);
  state_item_list queue =
    gl_list_create (GL_LINKED_LIST, NULL, NULL, NULL, true, 1,
                    (const void **) &target);
  while (gl_list_size (queue) > 0)
    {
      state_item *si = (state_item *) gl_list_get_at (queue, 0);
      gl_list_remove_at (queue, 0);
      if (bitset_test (result, si - state_items))
        continue;
      bitset_set (result, si - state_items);
      // search all reverse edges.
      bitset rsi = si->revs;
      bitset_iterator biter;
      state_item_number sin;
      BITSET_FOR_EACH (biter, rsi, sin, 0)
        gl_list_add_last (queue, &state_items[sin]);
    }
  gl_list_free (queue);
  return result;
}

/**
 * Compute the shortest lookahead-sensitive path from the start state to
 * this conflict. If optimized is true, only consider parser states
 * that can reach the conflict state.
 */
state_item_list
shortest_path_from_start (state_item_number target, symbol_number next_sym)
{
  bitset eligible = eligible_state_items (&state_items[target]);
  Hash_table *visited = hash_initialize (32,
                                         NULL,
                                         (Hash_hasher) lssi_hasher,
                                         (Hash_comparator) lssi_comparator,
                                         (Hash_data_freer) lssi_free);
  bitset il = bitset_create (nsyms, BITSET_FIXED);
  bitset_set (il, 0);
  lssi *init = new_lssi (0, NULL, il, true);
  lssi_list queue = gl_list_create_empty (GL_LINKED_LIST, NULL, NULL,
                                          NULL, true);
  append_lssi (init, visited, queue);
  // breadth-first search
  bool finished = false;
  lssi *n;
  while (gl_list_size (queue) > 0)
    {
      n = (lssi *) gl_list_get_at (queue, 0);
      gl_list_remove_at (queue, 0);
      state_item_number last = n->si;
      if (target == last && bitset_test (n->lookahead, next_sym))
        {
          finished = true;
          break;
        }
      state_item *si = &state_items[last];
      // Transitions don't change follow_L
      if (si->trans >= 0)
        {
          if (bitset_test (eligible, si->trans))
            {
              lssi *next = new_lssi (si->trans, n, n->lookahead, false);
              append_lssi (next, visited, queue);
            }
        }
      // For production steps, follow_L is based on the symbol after the
      // nonterminal being produced.
      // if no such symbol exists, follow_L is unchanged
      // if the symbol is a terminal, follow_L only contains that terminal
      // if the symbol is not nullable, follow_L is its FIRSTS set
      // if the symbol is nullable, follow_L is its FIRSTS set unioned with
      // this logic applied to the next symbol in the rule
      if (si->prods)
        {
          // Compute follow_L as above
          bitset lookahead = bitset_create (nsyms, BITSET_FIXED);
          item_number *pos = si->item + 1;
          for (; !item_number_is_rule_number (*pos); ++pos)
            {
              item_number it = *pos;
              if (ISTOKEN (it))
                {
                  bitset_set (lookahead, it);
                  break;
                }
              else
                {
                  bitset_union (lookahead, lookahead, FIRSTS (it));
                  if (!nullable[it - ntokens])
                    break;
                }
            }
          if (item_number_is_rule_number (*pos))
            bitset_union (lookahead, n->lookahead, lookahead);

          bool lookahead_used = false;
          // Try all possible production steps within this parser state.
          bitset_iterator biter;
          state_item_number nextSI;
          BITSET_FOR_EACH (biter, si->prods, nextSI, 0)
            {
              if (!bitset_test (eligible, nextSI))
                continue;
              lssi *next = new_lssi (nextSI, n, lookahead,
                                     !lookahead_used);
              lookahead_used = append_lssi (next, visited, queue)
                               || lookahead_used;
            }
          if (!lookahead_used)
            bitset_free (lookahead);
        }
    }

  bitset_free (eligible);
  if (!finished)
    {
      gl_list_free (queue);
      fputs ("Cannot find shortest path to conflict state.", stderr);
      abort ();
    }
  state_item_list res =
    gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
  for (lssi *sn = n; sn != NULL; sn = sn->parent)
    gl_list_add_first (res, &state_items[sn->si]);

  hash_free (visited);
  gl_list_free (queue);

  if (trace_flag & trace_cex)
    {
      fputs ("REDUCE ITEM PATH:\n", stderr);
      gl_list_iterator_t it = gl_list_iterator (res);
      const void *sip;
      while (gl_list_iterator_next (&it, &sip, NULL))
        state_item_print ((state_item *) sip, stderr, "");
    }
  return res;
}

/**
 * Determine if the given terminal is in the given symbol set or can begin
 * a nonterminal in the given symbol set.
 */
bool
intersect_symbol (symbol_number sym, bitset syms)
{
  if (!syms)
    return true;
  bitset_iterator biter;
  symbol_number sn;
  BITSET_FOR_EACH (biter, syms, sn, 0)
    {
      if (sym == sn)
        return true;
      if (ISVAR (sn) && bitset_test (FIRSTS (sn), sym))
        return true;
    }
  return false;
}

/**
 * Determine if any symbol in ts is in syms
 * or can begin a nonterminal syms.
 */
bool
intersect (bitset ts, bitset syms)
{
  if (!syms || !ts)
    return true;
  bitset_iterator biter;
  symbol_number sn;
  BITSET_FOR_EACH (biter, syms, sn, 0)
    {
      if (bitset_test (ts, sn))
        return true;
      if (ISVAR (sn) && !bitset_disjoint_p (ts, FIRSTS (sn)))
        return true;
    }
  return false;
}


/**
 * Compute a list of state_items that have a production to n with respect
 * to its lookahead
 */
state_item_list
lssi_reverse_production (const state_item *si, bitset lookahead)
{
  state_item_list result =
    gl_list_create_empty (GL_LINKED_LIST, NULL, NULL, NULL, true);
  if (SI_TRANSITION (si))
    return result;
  // A production step was made to the current lalr_item.
  // Check that the next symbol in the parent lalr_item is
  // compatible with the lookahead.
  bitset_iterator biter;
  state_item_number sin;
  BITSET_FOR_EACH (biter, si->revs, sin, 0)
  {
    state_item *prevsi = &state_items[sin];
    if (!production_allowed (prevsi, si))
      continue;
    bitset prev_lookahead = prevsi->lookahead;
    if (item_number_is_rule_number (*(prevsi->item)))
      {
        // reduce item
        // Check that some lookaheads can be preserved.
        if (!intersect (prev_lookahead, lookahead))
          continue;
      }
    else
      {
        // shift item
        if (lookahead)
          {
            // Check that lookahead is compatible with the first
            // possible symbols in the rest of the production.
            // Alternatively, if the rest of the production is
            // nullable, the lookahead must be compatible with
            // the lookahead of the corresponding item.
            bool applicable = false;
            bool nlable = true;
            for (item_number *pos = prevsi->item + 1;
                 !applicable && nlable && item_number_is_symbol_number (*pos);
                 ++pos)
              {
                symbol_number next_sym = item_number_as_symbol_number (*pos);
                if (ISTOKEN (next_sym))
                  {
                    applicable = intersect_symbol (next_sym, lookahead);
                    nlable = false;
                  }
                else
                  {
                    applicable = intersect (FIRSTS (next_sym), lookahead);
                    if (!applicable)
                      nlable = nullable[next_sym - ntokens];
                  }
              }
            if (!applicable && !nlable)
              continue;
          }
      }
    gl_list_add_last (result, prevsi);
  }
  return result;
}