/* IELR main implementation.
Copyright (C) 2009-2012 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 <http://www.gnu.org/licenses/>. */
#include <config.h>
#include "system.h"
#include "ielr.h"
#include <bitset.h>
#include <timevar.h>
#include "AnnotationList.h"
#include "derives.h"
#include "getargs.h"
#include "lalr.h"
#include "muscle-tab.h"
#include "nullable.h"
#include "relation.h"
#include "state.h"
#include "symtab.h"
/** Records the value of the \%define variable lr.type. */
typedef enum { LR_TYPE__LALR, LR_TYPE__IELR, LR_TYPE__CANONICAL_LR } LrType;
/**
* \post:
* - \c result = a new \c bitset of size \c ::nritems such that any bit \c i
* is set iff <tt>ritem[i]</tt> is a nonterminal after which all ritems in
* the same RHS are nullable nonterminals. In other words, the follows of
* a goto on <tt>ritem[i]</tt> include the lookahead set of the item.
*/
static bitset
ielr_compute_ritem_sees_lookahead_set (void)
{
bitset result = bitset_create (nritems, BITSET_FIXED);
unsigned int i = nritems-1;
while (i>0)
{
--i;
while (!item_number_is_rule_number (ritem[i])
&& ISVAR (ritem[i])
&& nullable [item_number_as_symbol_number (ritem[i]) - ntokens])
bitset_set (result, i--);
if (!item_number_is_rule_number (ritem[i]) && ISVAR (ritem[i]))
bitset_set (result, i--);
while (!item_number_is_rule_number (ritem[i]) && i>0)
--i;
}
if (trace_flag & trace_ielr)
{
fprintf (stderr, "ritem_sees_lookahead_set:\n");
debug_bitset (result);
fprintf (stderr, "\n");
}
return result;
}
/**
* \pre:
* - \c ritem_sees_lookahead_set was computed by
* \c ielr_compute_ritem_sees_lookahead_set.
* \post:
* - Each of \c *edgesp and \c *edge_countsp is a new array of size
* \c ::ngotos.
* - <tt>(*edgesp)[i]</tt> points to a \c goto_number array of size
* <tt>(*edge_countsp)[i]+1</tt>.
* - In such a \c goto_number array, the last element is \c ::END_NODE.
* - All remaining elements are the indices of the gotos to which there is an
* internal follow edge from goto \c i.
* - There is an internal follow edge from goto \c i to goto \c j iff both:
* - The from states of gotos \c i and \c j are the same.
* - The transition nonterminal for goto \c i appears as the first RHS
* symbol of at least one production for which both:
* - The LHS is the transition symbol of goto \c j.
* - All other RHS symbols are nullable nonterminals.
* - In other words, the follows of goto \c i include the follows of
* goto \c j and it's an internal edge because the from states are the
* same.
*/
static void
ielr_compute_internal_follow_edges (bitset ritem_sees_lookahead_set,
goto_number ***edgesp, int **edge_countsp)
{
*edgesp = xnmalloc (ngotos, sizeof **edgesp);
*edge_countsp = xnmalloc (ngotos, sizeof **edge_countsp);
{
bitset sources = bitset_create (ngotos, BITSET_FIXED);
goto_number i;
for (i = 0; i < ngotos; ++i)
(*edge_countsp)[i] = 0;
for (i = 0; i < ngotos; ++i)
{
int nsources = 0;
{
rule **rulep;
for (rulep = derives[states[to_state[i]]->accessing_symbol
- ntokens];
*rulep;
++rulep)
{
/* If there is at least one RHS symbol, if the first RHS symbol
is a nonterminal, and if all remaining RHS symbols (if any)
are nullable nonterminals, create an edge from the LHS
symbol's goto to the first RHS symbol's goto such that the RHS
symbol's goto will be the source of the edge after the
eventual relation_transpose below.
Unlike in ielr_compute_always_follows, I use a bitset for
edges rather than an array because it is possible that
multiple RHS's with the same first symbol could fit and thus
that we could end up with redundant edges. With the
possibility of redundant edges, it's hard to know ahead of
time how large to make such an array. Another possible
redundancy is that source and destination might be the same
goto. Eliminating all these possible redundancies now might
possibly help performance a little. I have not proven any of
this, but I'm guessing the bitset shouldn't entail much of a
performance penalty, if any. */
if (bitset_test (ritem_sees_lookahead_set,
(*rulep)->rhs - ritem))
{
goto_number source =
map_goto (from_state[i],
item_number_as_symbol_number (*(*rulep)->rhs));
if (i != source && !bitset_test (sources, source))
{
bitset_set (sources, source);
++nsources;
++(*edge_countsp)[source];
}
}
}
}
if (nsources == 0)
(*edgesp)[i] = NULL;
else
{
(*edgesp)[i] = xnmalloc (nsources + 1, sizeof *(*edgesp)[i]);
{
bitset_iterator biter_source;
bitset_bindex source;
int j = 0;
BITSET_FOR_EACH (biter_source, sources, source, 0)
(*edgesp)[i][j++] = source;
}
(*edgesp)[i][nsources] = END_NODE;
}
bitset_zero (sources);
}
bitset_free (sources);
}
relation_transpose (edgesp, ngotos);
if (trace_flag & trace_ielr)
{
fprintf (stderr, "internal_follow_edges:\n");
relation_print (*edgesp, ngotos, stderr);
}
}
/**
* \pre:
* - \c ritem_sees_lookahead_set was computed by
* \c ielr_compute_ritem_sees_lookahead_set.
* - \c internal_follow_edges was computed by
* \c ielr_compute_internal_follow_edges.
* \post:
* - \c *follow_kernel_itemsp is a new \c bitsetv in which the number of rows
* is \c ngotos and the number of columns is maximum number of kernel items
* in any state.
* - <tt>(*follow_kernel_itemsp)[i][j]</tt> is set iff the follows of goto
* \c i include the lookahead set of item \c j in the from state of goto
* \c i.
* - Thus, <tt>(*follow_kernel_itemsp)[i][j]</tt> is always unset if there is
* no item \c j in the from state of goto \c i.
*/
static void
ielr_compute_follow_kernel_items (bitset ritem_sees_lookahead_set,
goto_number **internal_follow_edges,
bitsetv *follow_kernel_itemsp)
{
{
size_t max_nitems = 0;
state_number i;
for (i = 0; i < nstates; ++i)
if (states[i]->nitems > max_nitems)
max_nitems = states[i]->nitems;
*follow_kernel_itemsp = bitsetv_create (ngotos, max_nitems, BITSET_FIXED);
}
{
goto_number i;
for (i = 0; i < ngotos; ++i)
{
size_t nitems = states[from_state[i]]->nitems;
item_number *items = states[from_state[i]]->items;
size_t j;
for (j = 0; j < nitems; ++j)
/* If this item has this goto and if all subsequent symbols in this
RHS (if any) are nullable nonterminals, then record this item as
one whose lookahead set is included in this goto's follows. */
if (item_number_is_symbol_number (ritem[items[j]])
&& item_number_as_symbol_number (ritem[items[j]])
== states[to_state[i]]->accessing_symbol
&& bitset_test (ritem_sees_lookahead_set, items[j]))
bitset_set ((*follow_kernel_itemsp)[i], j);
}
}
relation_digraph (internal_follow_edges, ngotos, follow_kernel_itemsp);
if (trace_flag & trace_ielr)
{
fprintf (stderr, "follow_kernel_items:\n");
debug_bitsetv (*follow_kernel_itemsp);
}
}
/**
* \pre
* - \c *edgesp and \c edge_counts were computed by
* \c ielr_compute_internal_follow_edges.
* \post
* - \c *always_followsp is a new \c bitsetv with \c ngotos rows and
* \c ntokens columns.
* - <tt>(*always_followsp)[i][j]</tt> is set iff token \c j is an always
* follow (that is, it's computed by internal and successor edges) of goto
* \c i.
* - Rows of \c *edgesp have been realloc'ed and extended to include
* successor follow edges. \c edge_counts has not been updated.
*/
static void
ielr_compute_always_follows (goto_number ***edgesp,
int const edge_counts[],
bitsetv *always_followsp)
{
*always_followsp = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
{
goto_number *edge_array = xnmalloc (ngotos, sizeof *edge_array);
goto_number i;
for (i = 0; i < ngotos; ++i)
{
goto_number nedges = edge_counts[i];
{
int j;
transitions *trans = states[to_state[i]]->transitions;
FOR_EACH_SHIFT (trans, j)
bitset_set ((*always_followsp)[i], TRANSITION_SYMBOL (trans, j));
for (; j < trans->num; ++j)
{
symbol_number sym = TRANSITION_SYMBOL (trans, j);
if (nullable[sym - ntokens])
edge_array[nedges++] = map_goto (to_state[i], sym);
}
}
if (nedges - edge_counts[i])
{
(*edgesp)[i] =
xnrealloc ((*edgesp)[i], nedges + 1, sizeof *(*edgesp)[i]);
memcpy ((*edgesp)[i] + edge_counts[i], edge_array + edge_counts[i],
(nedges - edge_counts[i]) * sizeof *(*edgesp)[i]);
(*edgesp)[i][nedges] = END_NODE;
}
}
free (edge_array);
}
relation_digraph (*edgesp, ngotos, always_followsp);
if (trace_flag & trace_ielr)
{
fprintf (stderr, "always follow edges:\n");
relation_print (*edgesp, ngotos, stderr);
fprintf (stderr, "always_follows:\n");
debug_bitsetv (*always_followsp);
}
}
/**
* \post
* - \c result is a new array of size \c ::nstates.
* - <tt>result[i]</tt> is an array of pointers to the predecessor
* <tt>state</tt>'s of state \c i.
* - The last element of such an array is \c NULL.
*/
static state ***
ielr_compute_predecessors (void)
{
state_number i;
int *predecessor_counts = xnmalloc (nstates, sizeof *predecessor_counts);
state ***result = xnmalloc (nstates, sizeof *result);
for (i = 0; i < nstates; ++i)
predecessor_counts[i] = 0;
for (i = 0; i < nstates; ++i)
{
int j;
for (j = 0; j < states[i]->transitions->num; ++j)
++predecessor_counts[states[i]->transitions->states[j]->number];
}
for (i = 0; i < nstates; ++i)
{
result[i] = xnmalloc (predecessor_counts[i]+1, sizeof *result[i]);
result[i][predecessor_counts[i]] = NULL;
predecessor_counts[i] = 0;
}
for (i = 0; i < nstates; ++i)
{
int j;
for (j = 0; j < states[i]->transitions->num; ++j)
{
state_number k = states[i]->transitions->states[j]->number;
result[k][predecessor_counts[k]++] = states[i];
}
}
free (predecessor_counts);
return result;
}
/**
* \post
* - \c *follow_kernel_itemsp and \c *always_followsp were computed by
* \c ielr_compute_follow_kernel_items and
* \c ielr_compute_always_follows.
* - Iff <tt>predecessorsp != NULL</tt>, then \c *predecessorsp was computed
* by \c ielr_compute_predecessors.
*/
static void
ielr_compute_auxiliary_tables (bitsetv *follow_kernel_itemsp,
bitsetv *always_followsp,
state ****predecessorsp)
{
goto_number **edges;
int *edge_counts;
{
bitset ritem_sees_lookahead_set = ielr_compute_ritem_sees_lookahead_set ();
ielr_compute_internal_follow_edges (ritem_sees_lookahead_set,
&edges, &edge_counts);
ielr_compute_follow_kernel_items (ritem_sees_lookahead_set, edges,
follow_kernel_itemsp);
bitset_free (ritem_sees_lookahead_set);
}
ielr_compute_always_follows (&edges, edge_counts, always_followsp);
{
int i;
for (i = 0; i < ngotos; ++i)
free (edges[i]);
}
free (edges);
free (edge_counts);
if (predecessorsp)
*predecessorsp = ielr_compute_predecessors ();
}
/**
* \note
* - FIXME: It might be an interesting experiment to compare the space and
* time efficiency of computing \c item_lookahead_sets either:
* - Fully up front.
* - Just-in-time, as implemented below.
* - Not at all. That is, just let annotations continue even when
* unnecessary.
*/
bool
ielr_item_has_lookahead (state *s, symbol_number lhs, size_t item,
symbol_number lookahead, state ***predecessors,
bitset **item_lookahead_sets)
{
if (!item_lookahead_sets[s->number])
{
size_t i;
item_lookahead_sets[s->number] =
xnmalloc (s->nitems, sizeof item_lookahead_sets[s->number][0]);
for (i = 0; i < s->nitems; ++i)
item_lookahead_sets[s->number][i] = NULL;
}
if (!item_lookahead_sets[s->number][item])
{
item_lookahead_sets[s->number][item] =
bitset_create (ntokens, BITSET_FIXED);
/* If this kernel item is the beginning of a RHS, it must be the kernel
item in the start state, and so its LHS has no follows and no goto to
check. If, instead, this kernel item is the successor of the start
state's kernel item, there are still no follows and no goto. This
situation is fortunate because we want to avoid the - 2 below in both
cases.
Actually, IELR(1) should never invoke this function for either of
those cases because (1) follow_kernel_items will never reference a
kernel item for this RHS because the end token blocks sight of the
lookahead set from the RHS's only nonterminal, and (2) no reduction
has a lookback dependency on this lookahead set. Nevertheless, I
didn't change this test to an aver just in case the usage of this
function evolves to need those two cases. In both cases, the current
implementation returns the right result. */
if (s->items[item] > 1)
{
/* If the LHS symbol of this item isn't known (because this is a
top-level invocation), go get it. */
if (!lhs)
{
unsigned int i;
for (i = s->items[item];
!item_number_is_rule_number (ritem[i]);
++i)
;
lhs = rules[item_number_as_rule_number (ritem[i])].lhs->number;
}
/* If this kernel item is next to the beginning of the RHS, then
check all predecessors' goto follows for the LHS. */
if (item_number_is_rule_number (ritem[s->items[item] - 2]))
{
state **predecessor;
aver (lhs != accept->number);
for (predecessor = predecessors[s->number];
*predecessor;
++predecessor)
bitset_or (item_lookahead_sets[s->number][item],
item_lookahead_sets[s->number][item],
goto_follows[map_goto ((*predecessor)->number,
lhs)]);
}
/* If this kernel item is later in the RHS, then check all
predecessor items' lookahead sets. */
else
{
state **predecessor;
for (predecessor = predecessors[s->number];
*predecessor;
++predecessor)
{
size_t predecessor_item;
for (predecessor_item = 0;
predecessor_item < (*predecessor)->nitems;
++predecessor_item)
if ((*predecessor)->items[predecessor_item]
== s->items[item] - 1)
break;
aver (predecessor_item != (*predecessor)->nitems);
ielr_item_has_lookahead (*predecessor, lhs,
predecessor_item, 0 /*irrelevant*/,
predecessors, item_lookahead_sets);
bitset_or (item_lookahead_sets[s->number][item],
item_lookahead_sets[s->number][item],
item_lookahead_sets[(*predecessor)->number]
[predecessor_item]);
}
}
}
}
return bitset_test (item_lookahead_sets[s->number][item], lookahead);
}
/**
* \pre
* - \c follow_kernel_items, \c always_follows, and \c predecessors
* were computed by \c ielr_compute_auxiliary_tables.
* \post
* - Each of <tt>*inadequacy_listsp</tt> and <tt>*annotation_listsp</tt>
* points to a new array of size \c ::nstates.
* - For <tt>0 <= i < ::nstates</tt>:
* - <tt>(*inadequacy_listsp)[i]</tt> contains the \c InadequacyList head
* node for <tt>states[i]</tt>.
* - <tt>(*annotation_listsp)[i]</tt> contains the \c AnnotationList head
* node for <tt>states[i]</tt>.
* - <tt>*max_annotationsp</tt> is the maximum number of annotations per
* state.
*/
static void
ielr_compute_annotation_lists (bitsetv follow_kernel_items,
bitsetv always_follows, state ***predecessors,
AnnotationIndex *max_annotationsp,
InadequacyList ***inadequacy_listsp,
AnnotationList ***annotation_listsp,
struct obstack *annotations_obstackp)
{
bitset **item_lookahead_sets =
xnmalloc (nstates, sizeof *item_lookahead_sets);
AnnotationIndex *annotation_counts =
xnmalloc (nstates, sizeof *annotation_counts);
ContributionIndex max_contributions = 0;
unsigned int total_annotations = 0;
state_number i;
*inadequacy_listsp = xnmalloc (nstates, sizeof **inadequacy_listsp);
*annotation_listsp = xnmalloc (nstates, sizeof **annotation_listsp);
for (i = 0; i < nstates; ++i)
{
item_lookahead_sets[i] = NULL;
(*inadequacy_listsp)[i] = NULL;
(*annotation_listsp)[i] = NULL;
annotation_counts[i] = 0;
}
{
InadequacyListNodeCount inadequacy_list_node_count = 0;
for (i = 0; i < nstates; ++i)
AnnotationList__compute_from_inadequacies (
states[i], follow_kernel_items, always_follows, predecessors,
item_lookahead_sets, *inadequacy_listsp, *annotation_listsp,
annotation_counts, &max_contributions, annotations_obstackp,
&inadequacy_list_node_count);
}
*max_annotationsp = 0;
for (i = 0; i < nstates; ++i)
{
if (annotation_counts[i] > *max_annotationsp)
*max_annotationsp = annotation_counts[i];
total_annotations += annotation_counts[i];
}
if (trace_flag & trace_ielr)
{
for (i = 0; i < nstates; ++i)
{
fprintf (stderr, "Inadequacy annotations for state %d:\n", i);
AnnotationList__debug ((*annotation_listsp)[i],
states[i]->nitems, 2);
}
fprintf (stderr, "Number of LR(0)/LALR(1) states: %d\n", nstates);
fprintf (stderr, "Average number of annotations per state: %f\n",
(float)total_annotations/nstates);
fprintf (stderr, "Max number of annotations per state: %d\n",
*max_annotationsp);
fprintf (stderr, "Max number of contributions per annotation: %d\n",
max_contributions);
}
for (i = 0; i < nstates; ++i)
if (item_lookahead_sets[i])
{
size_t j;
for (j = 0; j < states[i]->nitems; ++j)
if (item_lookahead_sets[i][j])
bitset_free (item_lookahead_sets[i][j]);
free (item_lookahead_sets[i]);
}
free (item_lookahead_sets);
free (annotation_counts);
}
typedef struct state_list {
struct state_list *next;
state *state;
/** Has this state been recomputed as a successor of another state? */
bool recomputedAsSuccessor;
/**
* \c NULL iff all lookahead sets are empty. <tt>lookaheads[i] = NULL</tt>
* iff the lookahead set on item \c i is empty.
*/
bitset *lookaheads;
/**
* nextIsocore is the next state in a circularly linked-list of all states
* with the same core. The one originally computed by generate_states in
* LR0.c is lr0Isocore.
*/
struct state_list *lr0Isocore;
struct state_list *nextIsocore;
} state_list;
/**
* \pre
* - \c follow_kernel_items and \c always_follows were computed by
* \c ielr_compute_auxiliary_tables.
* - <tt>n->class = nterm_sym</tt>.
* \post
* - \c follow_set contains the follow set for the goto on nonterminal \c n
* in state \c s based on the lookaheads stored in <tt>s->lookaheads</tt>.
*/
static void
ielr_compute_goto_follow_set (bitsetv follow_kernel_items,
bitsetv always_follows, state_list *s,
symbol *n, bitset follow_set)
{
goto_number n_goto = map_goto (s->lr0Isocore->state->number, n->number);
bitset_copy (follow_set, always_follows[n_goto]);
if (s->lookaheads)
{
bitset_iterator biter_item;
bitset_bindex item;
BITSET_FOR_EACH (biter_item, follow_kernel_items[n_goto], item, 0)
if (s->lookaheads[item])
bitset_or (follow_set, follow_set, s->lookaheads[item]);
}
}
/**
* \pre
* - \c follow_kernel_items and \c always_follows were computed by
* \c ielr_compute_auxiliary_tables.
* - \c lookahead_filter was computed by
* \c AnnotationList__computeLookaheadFilter for the original LR(0) isocore
* of \c t.
* - The number of rows in \c lookaheads is at least the number of items in
* \c t, and the number of columns is \c ::ntokens.
* \post
* - <tt>lookaheads[i][j]</tt> is set iff both:
* - <tt>lookahead_filter[i][j]</tt> is set.
* - The isocore of \c t that will be the transition successor of \c s will
* inherit from \c s token \c j into the lookahead set of item \c i.
*/
static void
ielr_compute_lookaheads (bitsetv follow_kernel_items, bitsetv always_follows,
state_list *s, state *t, bitsetv lookahead_filter,
bitsetv lookaheads)
{
size_t s_item = 0;
size_t t_item;
bitsetv_zero (lookaheads);
for (t_item = 0; t_item < t->nitems; ++t_item)
{
/* If this kernel item is the beginning of a RHS, it must be the
kernel item in the start state, but t is supposed to be a successor
state. If, instead, this kernel item is the successor of the start
state's kernel item, the lookahead set is empty. This second case is
a special case to avoid the - 2 below, but the next successor can be
handled fine without special casing it. */
aver (t->items[t_item] != 0);
if (t->items[t_item] > 1
&& !bitset_empty_p (lookahead_filter[t_item]))
{
if (item_number_is_rule_number (ritem[t->items[t_item] - 2]))
{
unsigned int rule_item;
for (rule_item = t->items[t_item];
!item_number_is_rule_number (ritem[rule_item]);
++rule_item)
;
ielr_compute_goto_follow_set (
follow_kernel_items, always_follows, s,
rules[item_number_as_rule_number (ritem[rule_item])].lhs,
lookaheads[t_item]);
}
else if (s->lookaheads)
{
/* We don't have to start the s item search at the beginning
every time because items from both states are sorted by their
indices in ritem. */
for (; s_item < s->state->nitems; ++s_item)
if (s->state->items[s_item] == t->items[t_item] - 1)
break;
aver (s_item != s->state->nitems);
if (s->lookaheads[s_item])
bitset_copy (lookaheads[t_item], s->lookaheads[s_item]);
}
bitset_and (lookaheads[t_item],
lookaheads[t_item], lookahead_filter[t_item]);
}
}
}
/**
* \pre
* - \c follow_kernel_items and \c always_follows were computed by
* \c ielr_compute_auxiliary_tables.
* - Either:
* - <tt>annotation_lists = NULL</tt> and all bits in work2 are set.
* - \c annotation_lists was computed by \c ielr_compute_annotation_lists.
* - The number of rows in each of \c lookaheads and \c work2 is the maximum
* number of items in any state. The number of columns in each is
* \c ::ntokens.
* - \c lookaheads was computed by \c ielr_compute_lookaheads for \c t.
* - \c ::nstates is the total number of states, some not yet fully computed,
* in the list ending at \c *last_statep. It is at least the number of
* original LR(0) states.
* - The size of \c work1 is at least the number of annotations for the LR(0)
* isocore of \c t.
* \post
* - Either:
* - In the case that <tt>annotation_lists != NULL</tt>,
* <tt>lookaheads \@pre</tt> was merged with some isocore of \c t if
* permitted by the annotations for the original LR(0) isocore of \c t.
* If this changed the lookaheads in that isocore, those changes were
* propagated to all already computed transition successors recursively
* possibly resulting in the splitting of some of those successors.
* - In the case that <tt>annotation_lists = NULL</tt>,
* <tt>lookaheads \@pre</tt> was merged with some isocore of \c t if the
* isocore's lookahead sets were identical to those specified by
* <tt>lookaheads \@pre</tt>.
* - If no such merge was permitted, a new isocore of \c t containing
* <tt>lookaheads \@pre</tt> was appended to the state list whose
* previous tail was <tt>*last_statep \@pre</tt> and \c ::nstates was
* incremented. It was also appended to \c t's isocore list.
* - <tt>*tp</tt> = the isocore of \c t into which
* <tt>lookaheads \@pre</tt> was placed/merged.
* - \c lookaheads, \c work1, and \c work2 may have been altered.
*/
static void
ielr_compute_state (bitsetv follow_kernel_items, bitsetv always_follows,
AnnotationList **annotation_lists, state *t,
bitsetv lookaheads, state_list **last_statep,
ContributionIndex work1[], bitsetv work2, state **tp)
{
state_list *lr0_isocore = t->state_list->lr0Isocore;
state_list **this_isocorep;
bool has_lookaheads;
/* Determine whether there's an isocore of t with which these lookaheads can
be merged. */
{
AnnotationIndex ai;
AnnotationList *a;
if (annotation_lists)
for (ai = 0, a = annotation_lists[lr0_isocore->state->number];
a;
++ai, a = a->next)
work1[ai] =
AnnotationList__computeDominantContribution (
a, lr0_isocore->state->nitems, lookaheads, false);
for (this_isocorep = &t->state_list;
this_isocorep == &t->state_list || *this_isocorep != t->state_list;
this_isocorep = &(*this_isocorep)->nextIsocore)
{
if (!(*this_isocorep)->recomputedAsSuccessor)
break;
if (annotation_lists)
{
for (ai = 0, a = annotation_lists[lr0_isocore->state->number];
a;
++ai, a = a->next)
{
if (work1[ai] != ContributionIndex__none)
{
/* This isocore compatibility test depends on the fact
that, if the dominant contributions are the same for the
two isocores, then merging their lookahead sets will not
produce a state with a different dominant contribution.
*/
ContributionIndex ci =
AnnotationList__computeDominantContribution (
a, lr0_isocore->state->nitems,
(*this_isocorep)->lookaheads, false);
if (ci != ContributionIndex__none && work1[ai] != ci)
break;
}
}
if (!a)
break;
}
else
{
size_t i;
for (i = 0; i < t->nitems; ++i)
{
if (!(*this_isocorep)->lookaheads
|| !(*this_isocorep)->lookaheads[i])
{
if (!bitset_empty_p (lookaheads[i]))
break;
}
/* bitset_equal_p uses the size of the first argument,
so lookaheads[i] must be the second argument. */
else if (!bitset_equal_p ((*this_isocorep)->lookaheads[i],
lookaheads[i]))
break;
}
if (i == t->nitems)
break;
}
}
}
has_lookaheads = false;
{
size_t i;
for (i = 0; i < lr0_isocore->state->nitems; ++i)
if (!bitset_empty_p (lookaheads[i]))
{
has_lookaheads = true;
break;
}
}
/* Merge with an existing isocore. */
if (this_isocorep == &t->state_list || *this_isocorep != t->state_list)
{
bool new_lookaheads = false;
*tp = (*this_isocorep)->state;
/* Merge lookaheads into the state and record whether any of them are
actually new. */
if (has_lookaheads)
{
size_t i;
if (!(*this_isocorep)->lookaheads)
{
(*this_isocorep)->lookaheads =
xnmalloc (t->nitems, sizeof (*this_isocorep)->lookaheads);
for (i = 0; i < t->nitems; ++i)
(*this_isocorep)->lookaheads[i] = NULL;
}
for (i = 0; i < t->nitems; ++i)
if (!bitset_empty_p (lookaheads[i]))
{
if (!(*this_isocorep)->lookaheads[i])
(*this_isocorep)->lookaheads[i] =
bitset_create (ntokens, BITSET_FIXED);
bitset_andn (lookaheads[i],
lookaheads[i], (*this_isocorep)->lookaheads[i]);
bitset_or ((*this_isocorep)->lookaheads[i],
lookaheads[i], (*this_isocorep)->lookaheads[i]);
if (!bitset_empty_p (lookaheads[i]))
new_lookaheads = true;
}
}
/* If new lookaheads were merged, propagate those lookaheads to the
successors, possibly splitting them. If *tp is being recomputed for
the first time, this isn't necessary because the main
ielr_split_states loop will handle the successors later. */
if (!(*this_isocorep)->recomputedAsSuccessor)
(*this_isocorep)->recomputedAsSuccessor = true;
else if (new_lookaheads)
{
int i;
/* When merging demands identical lookahead sets, it is impossible to
merge new lookaheads. */
aver (annotation_lists);
for (i = 0; i < (*tp)->transitions->num; ++i)
{
state *t2 = (*tp)->transitions->states[i];
/* At any time, there's at most one state for which we have so
far initially recomputed only some of its successors in the
main ielr_split_states loop. Because we recompute successors
in order, we can just stop at the first such successor. Of
course, *tp might be a state some of whose successors have
been recomputed as successors of other states rather than as
successors of *tp. It's fine if we go ahead and propagate to
some of those. We'll propagate to them again (but stop when
we see nothing changes) and to the others when we reach *tp in
the main ielr_split_states loop later. */
if (!t2->state_list->recomputedAsSuccessor)
break;
AnnotationList__computeLookaheadFilter (
annotation_lists[t2->state_list->lr0Isocore->state->number],
t2->nitems, work2);
ielr_compute_lookaheads (follow_kernel_items, always_follows,
(*this_isocorep), t2, work2,
lookaheads);
/* FIXME: If splitting t2 here, it's possible that lookaheads
that had already propagated from *tp to t2 will be left in t2
after *tp has been removed as t2's predecessor:
- We're going to recompute all lookaheads in phase 4, so these
extra lookaheads won't appear in the final parser table.
- If t2 has just one annotation, then these extra lookaheads
cannot alter the dominating contribution to the associated
inadequacy and thus cannot needlessly prevent a future merge
of some new state with t2. We can be sure of this because:
- The fact that we're splitting t2 now means that some
predecessors (at least one) other than *tp must be
propagating contributions to t2.
- The fact that t2 was merged in the first place means that,
if *tp propagated any contributions, the dominating
contribution must be the same as that from those other
predecessors.
- Thus, if some new state to be merged with t2 in the future
proves to be compatible with the contributions propagated
by the other predecessors, it will also be compatible with
the contributions made by the extra lookaheads left behind
by *tp.
- However, if t2 has more than one annotation and these extra
lookaheads contribute to one of their inadequacies, it's
possible these extra lookaheads may needlessly prevent a
future merge with t2. For example:
- Let's say there's an inadequacy A that makes the split
necessary as follows:
- There's currently just one other predecessor and it
propagates to t2 some contributions to inadequacy A.
- The new lookaheads that we were attempting to propagate
from *tp to t2 made contributions to inadequacy A with a
different dominating contribution than those from that
other predecessor.
- The extra lookaheads either make no contribution to
inadequacy A or have the same dominating contribution as
the contributions from the other predecessor. Either
way, as explained above, they can't prevent a future
merge.
- Let's say there's an inadequacy B that causes the trouble
with future merges as follows:
- The extra lookaheads make contributions to inadequacy B.
- Those extra contributions did not prevent the original
merge to create t2 because the other predecessor
propagates to t2 no contributions to inadequacy B.
- Thus, those extra contributions may prevent a future
merge with t2 even though the merge would be fine if *tp
had not left them behind.
- Is the latter case common enough to worry about?
- Perhaps we should track all predecessors and iterate them
now to recreate t2 without those extra lookaheads. */
ielr_compute_state (follow_kernel_items, always_follows,
annotation_lists, t2, lookaheads,
last_statep, work1, work2,
&(*tp)->transitions->states[i]);
}
}
}
/* Create a new isocore. */
else
{
state_list *old_isocore = *this_isocorep;
(*last_statep)->next = *this_isocorep = xmalloc (sizeof **last_statep);
*last_statep = *this_isocorep;
(*last_statep)->state = *tp = state_new_isocore (t);
(*tp)->state_list = *last_statep;
(*last_statep)->recomputedAsSuccessor = true;
(*last_statep)->next = NULL;
(*last_statep)->lookaheads = NULL;
if (has_lookaheads)
{
size_t i;
(*last_statep)->lookaheads =
xnmalloc (t->nitems, sizeof (*last_statep)->lookaheads);
for (i = 0; i < t->nitems; ++i)
{
if (bitset_empty_p (lookaheads[i]))
(*last_statep)->lookaheads[i] = NULL;
else
{
(*last_statep)->lookaheads[i] =
bitset_create (ntokens, BITSET_FIXED);
bitset_copy ((*last_statep)->lookaheads[i], lookaheads[i]);
}
}
}
(*last_statep)->lr0Isocore = lr0_isocore;
(*last_statep)->nextIsocore = old_isocore;
}
}
/**
* \pre
* - \c follow_kernel_items and \c always_follows were computed by
* \c ielr_compute_auxiliary_tables.
* - Either:
* - <tt>annotation_lists = NULL</tt> and <tt>max_annotations=0</tt>.
* - \c annotation_lists and \c max_annotations were computed by
* \c ielr_compute_annotation_lists.
* \post
* - \c ::states is of size \c ::nstates (which might be greater than
* <tt>::nstates \@pre</tt>) and no longer contains any LR(1)-relative
* inadequacy. \c annotation_lists was used to determine state
* compatibility or, if <tt>annotation_lists = NULL</tt>, the canonical
* LR(1) state compatibility test was used.
* - If <tt>annotation_lists = NULL</tt>, reduction lookahead sets were
* computed in all states. TV_IELR_PHASE4 was pushed while they were
* computed from item lookahead sets.
*/
static void
ielr_split_states (bitsetv follow_kernel_items, bitsetv always_follows,
AnnotationList **annotation_lists,
AnnotationIndex max_annotations)
{
state_list *first_state;
state_list *last_state;
bitsetv lookahead_filter = NULL;
bitsetv lookaheads;
/* Set up state list and some reusable bitsets. */
{
size_t max_nitems = 0;
state_number i;
state_list **nodep = &first_state;
for (i = 0; i < nstates; ++i)
{
*nodep = states[i]->state_list = last_state = xmalloc (sizeof **nodep);
(*nodep)->state = states[i];
(*nodep)->recomputedAsSuccessor = false;
(*nodep)->lookaheads = NULL;
(*nodep)->lr0Isocore = *nodep;
(*nodep)->nextIsocore = *nodep;
nodep = &(*nodep)->next;
if (states[i]->nitems > max_nitems)
max_nitems = states[i]->nitems;
}
*nodep = NULL;
lookahead_filter = bitsetv_create (max_nitems, ntokens, BITSET_FIXED);
if (!annotation_lists)
bitsetv_ones (lookahead_filter);
lookaheads = bitsetv_create (max_nitems, ntokens, BITSET_FIXED);
}
/* Recompute states. */
{
ContributionIndex *work = xnmalloc (max_annotations, sizeof *work);
state_list *this_state;
for (this_state = first_state; this_state; this_state = this_state->next)
{
state *s = this_state->state;
int i;
for (i = 0; i < s->transitions->num; ++i)
{
state *t = s->transitions->states[i];
if (annotation_lists)
AnnotationList__computeLookaheadFilter (
annotation_lists[t->state_list->lr0Isocore->state->number],
t->nitems, lookahead_filter);
ielr_compute_lookaheads (follow_kernel_items, always_follows,
this_state, t, lookahead_filter,
lookaheads);
ielr_compute_state (follow_kernel_items, always_follows,
annotation_lists, t, lookaheads, &last_state,
work, lookahead_filter,
&s->transitions->states[i]);
}
}
free (work);
}
bitsetv_free (lookahead_filter);
bitsetv_free (lookaheads);
/* Store states back in the states array. */
states = xnrealloc (states, nstates, sizeof *states);
{
state_list *node;
for (node = first_state; node; node = node->next)
states[node->state->number] = node->state;
}
/* In the case of canonical LR(1), copy item lookahead sets to reduction
lookahead sets. */
if (!annotation_lists)
{
timevar_push (TV_IELR_PHASE4);
initialize_LA ();
state_list *node;
for (node = first_state; node; node = node->next)
if (!node->state->consistent)
{
size_t i = 0;
item_number *itemset = node->state->items;
size_t r;
for (r = 0; r < node->state->reductions->num; ++r)
{
rule *this_rule = node->state->reductions->rules[r];
bitset lookahead_set =
node->state->reductions->lookahead_tokens[r];
if (item_number_is_rule_number (*this_rule->rhs))
ielr_compute_goto_follow_set (follow_kernel_items,
always_follows, node,
this_rule->lhs, lookahead_set);
else if (node->lookaheads)
{
/* We don't need to start the kernel item search back at
i=0 because both items and reductions are sorted on rule
number. */
while (!item_number_is_rule_number (ritem[itemset[i]])
|| item_number_as_rule_number (ritem[itemset[i]])
!= this_rule->number)
{
++i;
aver (i < node->state->nitems);
}
if (node->lookaheads[i])
bitset_copy (lookahead_set, node->lookaheads[i]);
}
}
}
timevar_pop (TV_IELR_PHASE4);
}
/* Free state list. */
while (first_state)
{
state_list *node = first_state;
if (node->lookaheads)
{
size_t i;
for (i = 0; i < node->state->nitems; ++i)
if (node->lookaheads[i])
bitset_free (node->lookaheads[i]);
free (node->lookaheads);
}
first_state = node->next;
free (node);
}
}
void
ielr (void)
{
LrType lr_type;
/* Examine user options. */
{
char *type = muscle_percent_define_get ("lr.type");
if (0 == strcmp (type, "lalr"))
lr_type = LR_TYPE__LALR;
else if (0 == strcmp (type, "ielr"))
lr_type = LR_TYPE__IELR;
else if (0 == strcmp (type, "canonical-lr"))
lr_type = LR_TYPE__CANONICAL_LR;
else
aver (false);
free (type);
}
/* Phase 0: LALR(1). */
timevar_push (TV_LALR);
if (lr_type == LR_TYPE__CANONICAL_LR)
set_goto_map ();
else
lalr ();
if (lr_type == LR_TYPE__LALR)
{
bitsetv_free (goto_follows);
timevar_pop (TV_LALR);
return;
}
timevar_pop (TV_LALR);
{
bitsetv follow_kernel_items;
bitsetv always_follows;
InadequacyList **inadequacy_lists = NULL;
AnnotationList **annotation_lists = NULL;
struct obstack annotations_obstack;
AnnotationIndex max_annotations = 0;
{
/* Phase 1: Compute Auxiliary Tables. */
state ***predecessors;
timevar_push (TV_IELR_PHASE1);
ielr_compute_auxiliary_tables (
&follow_kernel_items, &always_follows,
lr_type == LR_TYPE__CANONICAL_LR ? NULL : &predecessors);
timevar_pop (TV_IELR_PHASE1);
/* Phase 2: Compute Annotations. */
timevar_push (TV_IELR_PHASE2);
if (lr_type != LR_TYPE__CANONICAL_LR)
{
obstack_init (&annotations_obstack);
ielr_compute_annotation_lists (follow_kernel_items, always_follows,
predecessors, &max_annotations,
&inadequacy_lists, &annotation_lists,
&annotations_obstack);
{
state_number i;
for (i = 0; i < nstates; ++i)
free (predecessors[i]);
}
free (predecessors);
bitsetv_free (goto_follows);
lalr_free ();
}
timevar_pop (TV_IELR_PHASE2);
}
/* Phase 3: Split States. */
timevar_push (TV_IELR_PHASE3);
{
state_number nstates_lr0 = nstates;
ielr_split_states (follow_kernel_items, always_follows,
annotation_lists, max_annotations);
if (inadequacy_lists)
{
state_number i;
for (i = 0; i < nstates_lr0; ++i)
InadequacyList__delete (inadequacy_lists[i]);
}
}
free (inadequacy_lists);
if (annotation_lists)
obstack_free (&annotations_obstack, NULL);
free (annotation_lists);
bitsetv_free (follow_kernel_items);
bitsetv_free (always_follows);
timevar_pop (TV_IELR_PHASE3);
}
/* Phase 4: Compute Reduction Lookaheads. */
timevar_push (TV_IELR_PHASE4);
free (goto_map);
free (from_state);
free (to_state);
if (lr_type == LR_TYPE__CANONICAL_LR)
{
/* Reduction lookaheads are computed in ielr_split_states above
but are timed as part of phase 4. */
set_goto_map ();
}
else
{
lalr ();
bitsetv_free (goto_follows);
}
timevar_pop (TV_IELR_PHASE4);
}