Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/yacc/lalr.c	Lines:	288	289	99.7 %
Date:	2016-12-06	Branches:	136	140	97.1 %


/*	$OpenBSD: lalr.c,v 1.18 2015/12/11 20:25:47 mmcc Exp $	*/
/*	$NetBSD: lalr.c,v 1.4 1996/03/19 03:21:33 jtc Exp $	*/

/*
 * Copyright (c) 1989 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Robert Paul Corbett.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "defs.h"

typedef struct shorts {
	struct shorts *next;
	short value;
} shorts;

int tokensetsize;
short *lookaheads;
short *LAruleno;
unsigned *LA;
short *accessing_symbol;
core **state_table;
shifts **shift_table;
reductions **reduction_table;
short *goto_map;
short *from_state;
short *to_state;

short **transpose();
void set_state_table(void);
void set_accessing_symbol(void);
void set_shift_table(void);
void set_reduction_table(void);
void set_maxrhs(void);
void initialize_LA(void);
void set_goto_map(void);
void initialize_F(void);
void build_relations(void);
void compute_FOLLOWS(void);
void compute_lookaheads(void);
int map_goto(int, int);
void digraph(short **);
void add_lookback_edge(int, int, int);
void traverse(int);

static int infinity;
static int maxrhs;
static int ngotos;
static unsigned *F;
static short **includes;
static shorts **lookback;
static short **R;
static short *INDEX;
static short *VERTICES;
static int top;

void
lalr(void)
{
	tokensetsize = WORDSIZE(ntokens);

	set_state_table();
	set_accessing_symbol();
	set_shift_table();
	set_reduction_table();
	set_maxrhs();
	initialize_LA();
	set_goto_map();
	initialize_F();
	build_relations();
	compute_FOLLOWS();
	compute_lookaheads();
	free_derives();
	free_nullable();
}


void
set_state_table(void)
{
	core *sp;

	state_table = NEW2(nstates, core *);
	for (sp = first_state; sp; sp = sp->next)
		state_table[sp->number] = sp;
}


void
set_accessing_symbol(void)
{
	core *sp;

	accessing_symbol = NEW2(nstates, short);
	for (sp = first_state; sp; sp = sp->next)
		accessing_symbol[sp->number] = sp->accessing_symbol;
}


void
set_shift_table(void)
{
	shifts *sp;

	shift_table = NEW2(nstates, shifts *);
	for (sp = first_shift; sp; sp = sp->next)
		shift_table[sp->number] = sp;
}


void
set_reduction_table(void)
{
	reductions *rp;

	reduction_table = NEW2(nstates, reductions *);
	for (rp = first_reduction; rp; rp = rp->next)
		reduction_table[rp->number] = rp;
}


void
set_maxrhs(void)
{
	short *itemp, *item_end;
	int length, max;

	length = 0;
	max = 0;
	item_end = ritem + nitems;
	for (itemp = ritem; itemp < item_end; itemp++) {
		if (*itemp >= 0) {
			length++;
		} else {
			if (length > max) max = length;
			length = 0;
		}
	}

	maxrhs = max;
}


void
initialize_LA(void)
{
	int i, j, k;
	reductions *rp;

	lookaheads = NEW2(nstates + 1, short);

	k = 0;
	for (i = 0; i < nstates; i++) {
		lookaheads[i] = k;
		rp = reduction_table[i];
		if (rp)
			k += rp->nreds;
	}
	lookaheads[nstates] = k;

	LA = NEW2(k * tokensetsize, unsigned);
	LAruleno = NEW2(k, short);
	lookback = NEW2(k, shorts *);

	k = 0;
	for (i = 0; i < nstates; i++) {
		rp = reduction_table[i];
		if (rp) {
			for (j = 0; j < rp->nreds; j++) {
				LAruleno[k] = rp->rules[j];
				k++;
			}
		}
	}
}

void
set_goto_map(void)
{
	shifts *sp;
	int i, k, symbol;
	int state1, state2;
	short *temp_map;

	goto_map = NEW2(nvars + 1, short) - ntokens;
	temp_map = NEW2(nvars + 1, short) - ntokens;

	ngotos = 0;
	for (sp = first_shift; sp; sp = sp->next) {
		for (i = sp->nshifts - 1; i >= 0; i--) {
			symbol = accessing_symbol[sp->shift[i]];

			if (ISTOKEN(symbol)) break;

			if (ngotos == MAXSHORT)
				fatal("too many gotos");

			ngotos++;
			goto_map[symbol]++;
		}
	}

	k = 0;
	for (i = ntokens; i < nsyms; i++) {
		temp_map[i] = k;
		k += goto_map[i];
	}

	for (i = ntokens; i < nsyms; i++)
		goto_map[i] = temp_map[i];

	goto_map[nsyms] = ngotos;
	temp_map[nsyms] = ngotos;

	from_state = NEW2(ngotos, short);
	to_state = NEW2(ngotos, short);

	for (sp = first_shift; sp; sp = sp->next) {
		state1 = sp->number;
		for (i = sp->nshifts - 1; i >= 0; i--) {
			state2 = sp->shift[i];
			symbol = accessing_symbol[state2];

			if (ISTOKEN(symbol)) break;

			k = temp_map[symbol]++;
			from_state[k] = state1;
			to_state[k] = state2;
		}
	}

	free(temp_map + ntokens);
}



/*  Map_goto maps a state/symbol pair into its numeric representation.	*/

int
map_goto(int state, int symbol)
{
	int high, low, middle, s;

	low = goto_map[symbol];
	high = goto_map[symbol + 1];

	for (;;) {
		assert(low <= high);
		middle = (low + high) >> 1;
		s = from_state[middle];
		if (s == state)
			return (middle);
		else if (s < state)
			low = middle + 1;
		else
			high = middle - 1;
	}
}


void
initialize_F(void)
{
	int i, j, k;
	shifts *sp;
	short *edge, *rp, **reads;
	unsigned int *rowp;
	int nedges, stateno, symbol, nwords;

	nwords = ngotos * tokensetsize;
	F = NEW2(nwords, unsigned);

	reads = NEW2(ngotos, short *);
	edge = NEW2(ngotos + 1, short);
	nedges = 0;

	rowp = F;
	for (i = 0; i < ngotos; i++) {
		stateno = to_state[i];
		sp = shift_table[stateno];

		if (sp) {
			k = sp->nshifts;

			for (j = 0; j < k; j++) {
				symbol = accessing_symbol[sp->shift[j]];
				if (ISVAR(symbol))
					break;
				SETBIT(rowp, symbol);
			}

			for (; j < k; j++) {
				symbol = accessing_symbol[sp->shift[j]];
				if (nullable[symbol])
					edge[nedges++] = map_goto(stateno, symbol);
			}

			if (nedges) {
				reads[i] = rp = NEW2(nedges + 1, short);

				for (j = 0; j < nedges; j++)
					rp[j] = edge[j];

				rp[nedges] = -1;
				nedges = 0;
			}
		}

		rowp += tokensetsize;
	}

	SETBIT(F, 0);
	digraph(reads);

	for (i = 0; i < ngotos; i++)
		free(reads[i]);

	free(reads);
	free(edge);
}


void
build_relations(void)
{
	int i, j, k;
	short *rulep, *rp;
	shifts *sp;
	int length, nedges, done;
	int state1, stateno, symbol1, symbol2;
	short *shortp, *edge, *states;
	short **new_includes;

	includes = NEW2(ngotos, short *);
	edge = NEW2(ngotos + 1, short);
	states = NEW2(maxrhs + 1, short);

	for (i = 0; i < ngotos; i++) {
		nedges = 0;
		state1 = from_state[i];
		symbol1 = accessing_symbol[to_state[i]];

		for (rulep = derives[symbol1]; *rulep >= 0; rulep++) {
			length = 1;
			states[0] = state1;
			stateno = state1;

			for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++) {
				symbol2 = *rp;
				sp = shift_table[stateno];
				k = sp->nshifts;

				for (j = 0; j < k; j++) {
					stateno = sp->shift[j];
					if (accessing_symbol[stateno] == symbol2)
						break;
				}

				states[length++] = stateno;
			}

			add_lookback_edge(stateno, *rulep, i);

			length--;
			done = 0;
			while (!done) {
				done = 1;
				rp--;
				if (ISVAR(*rp)) {
					stateno = states[--length];
					edge[nedges++] = map_goto(stateno, *rp);
					if (nullable[*rp] && length > 0)
						done = 0;
				}
			}
		}

		if (nedges) {
			includes[i] = shortp = NEW2(nedges + 1, short);
			for (j = 0; j < nedges; j++)
				shortp[j] = edge[j];
			shortp[nedges] = -1;
		}
	}

	new_includes = transpose(includes, ngotos);

	for (i = 0; i < ngotos; i++)
		free(includes[i]);

	free(includes);

	includes = new_includes;

	free(edge);
	free(states);
}

void
add_lookback_edge(int stateno, int ruleno, int gotono)
{
	int i, k, found;
	shorts *sp;

	i = lookaheads[stateno];
	k = lookaheads[stateno + 1];
	found = 0;
	while (!found && i < k) {
		if (LAruleno[i] == ruleno)
			found = 1;
		else
			++i;
	}
	assert(found);

	sp = NEW(shorts);
	sp->next = lookback[i];
	sp->value = gotono;
	lookback[i] = sp;
}



short **
transpose(short **R, int n)
{
	short **new_R, **temp_R, *nedges, *sp;
	int i, k;

	nedges = NEW2(n, short);

	for (i = 0; i < n; i++) {
		sp = R[i];
		if (sp) {
			while (*sp >= 0)
				nedges[*sp++]++;
		}
	}

	new_R = NEW2(n, short *);
	temp_R = NEW2(n, short *);

	for (i = 0; i < n; i++) {
		k = nedges[i];
		if (k > 0) {
			sp = NEW2(k + 1, short);
			new_R[i] = sp;
			temp_R[i] = sp;
			sp[k] = -1;
		}
	}

	free(nedges);

	for (i = 0; i < n; i++) {
		sp = R[i];
		if (sp) {
			while (*sp >= 0)
				*temp_R[*sp++]++ = i;
		}
	}

	free(temp_R);

	return (new_R);
}


void
compute_FOLLOWS(void)
{
	digraph(includes);
}

void
compute_lookaheads(void)
{
	int i, n;
	unsigned int *fp1, *fp2, *fp3;
	shorts *sp, *next;
	unsigned int *rowp;

	rowp = LA;
	n = lookaheads[nstates];
	for (i = 0; i < n; i++) {
		fp3 = rowp + tokensetsize;
		for (sp = lookback[i]; sp; sp = sp->next) {
			fp1 = rowp;
			fp2 = F + tokensetsize * sp->value;
			while (fp1 < fp3)
				*fp1++ |= *fp2++;
		}
		rowp = fp3;
	}

	for (i = 0; i < n; i++)
		for (sp = lookback[i]; sp; sp = next) {
			next = sp->next;
			free(sp);
		}

	free(lookback);
	free(F);
}

void
digraph(short **relation)
{
	int i;

	infinity = ngotos + 2;
	INDEX = NEW2(ngotos + 1, short);
	VERTICES = NEW2(ngotos + 1, short);
	top = 0;
	R = relation;

	memset(INDEX, 0, ngotos * sizeof(short));
	for (i = 0; i < ngotos; i++)
		if (R[i])
			traverse(i);

	free(INDEX);
	free(VERTICES);
}


void
traverse(int i)
{
	unsigned int *base, *fp1, *fp2, *fp3;
	int j, height;
	short *rp;

	VERTICES[++top] = i;
	INDEX[i] = height = top;

	base = F + i * tokensetsize;
	fp3 = base + tokensetsize;

	rp = R[i];
	if (rp) {
		while ((j = *rp++) >= 0) {
			if (INDEX[j] == 0)
				traverse(j);

			if (INDEX[i] > INDEX[j])
				INDEX[i] = INDEX[j];

			fp1 = base;
			fp2 = F + j * tokensetsize;

			while (fp1 < fp3)
				*fp1++ |= *fp2++;
		}
	}

	if (INDEX[i] == height) {
		for (;;) {
			j = VERTICES[top--];
			INDEX[j] = infinity;

			if (i == j)
				break;

			fp1 = base;
			fp2 = F + j * tokensetsize;

			while (fp1 < fp3)
				*fp2++ = *fp1++;
		}
	}
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: lalr.c,v 1.18 2015/12/11 20:25:47 mmcc Exp $ */
2			/* $NetBSD: lalr.c,v 1.4 1996/03/19 03:21:33 jtc Exp $ */
3
4			/*
5			* Copyright (c) 1989 The Regents of the University of California.
6			* All rights reserved.
7			*
8			* This code is derived from software contributed to Berkeley by
9			* Robert Paul Corbett.
10			*
11			* Redistribution and use in source and binary forms, with or without
12			* modification, are permitted provided that the following conditions
13			* are met:
14			* 1. Redistributions of source code must retain the above copyright
15			* notice, this list of conditions and the following disclaimer.
16			* 2. Redistributions in binary form must reproduce the above copyright
17			* notice, this list of conditions and the following disclaimer in the
18			* documentation and/or other materials provided with the distribution.
19			* 3. Neither the name of the University nor the names of its contributors
20			* may be used to endorse or promote products derived from this software
21			* without specific prior written permission.
22			*
23			* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24			* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25			* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26			* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27			* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28			* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29			* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30			* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31			* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32			* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33			* SUCH DAMAGE.
34			*/
35
36			#include "defs.h"
37
38			typedef struct shorts {
39			struct shorts *next;
40			short value;
41			} shorts;
42
43			int tokensetsize;
44			short *lookaheads;
45			short *LAruleno;
46			unsigned *LA;
47			short *accessing_symbol;
48			core **state_table;
49			shifts **shift_table;
50			reductions **reduction_table;
51			short *goto_map;
52			short *from_state;
53			short *to_state;
54
55			short **transpose();
56			void set_state_table(void);
57			void set_accessing_symbol(void);
58			void set_shift_table(void);
59			void set_reduction_table(void);
60			void set_maxrhs(void);
61			void initialize_LA(void);
62			void set_goto_map(void);
63			void initialize_F(void);
64			void build_relations(void);
65			void compute_FOLLOWS(void);
66			void compute_lookaheads(void);
67			int map_goto(int, int);
68			void digraph(short **);
69			void add_lookback_edge(int, int, int);
70			void traverse(int);
71
72			static int infinity;
73			static int maxrhs;
74			static int ngotos;
75			static unsigned *F;
76			static short **includes;
77			static shorts **lookback;
78			static short **R;
79			static short *INDEX;
80			static short *VERTICES;
81			static int top;
82
83			void
84			lalr(void)
85		21	{
86		21	tokensetsize = WORDSIZE(ntokens);
87
88		21	set_state_table();
89		21	set_accessing_symbol();
90		21	set_shift_table();
91		21	set_reduction_table();
92		21	set_maxrhs();
93		21	initialize_LA();
94		21	set_goto_map();
95		21	initialize_F();
96		21	build_relations();
97		21	compute_FOLLOWS();
98		21	compute_lookaheads();
99		21	free_derives();
100		21	free_nullable();
101		21	}
102
103
104			void
105			set_state_table(void)
106		21	{
107			core *sp;
108
109		21	state_table = NEW2(nstates, core *);
110	✓✓	4023	for (sp = first_state; sp; sp = sp->next)
111		4002	state_table[sp->number] = sp;
112		21	}
113
114
115			void
116			set_accessing_symbol(void)
117		21	{
118			core *sp;
119
120		21	accessing_symbol = NEW2(nstates, short);
121	✓✓	4023	for (sp = first_state; sp; sp = sp->next)
122		4002	accessing_symbol[sp->number] = sp->accessing_symbol;
123		21	}
124
125
126			void
127			set_shift_table(void)
128		21	{
129			shifts *sp;
130
131		21	shift_table = NEW2(nstates, shifts *);
132	✓✓	2118	for (sp = first_shift; sp; sp = sp->next)
133		2097	shift_table[sp->number] = sp;
134		21	}
135
136
137			void
138			set_reduction_table(void)
139		21	{
140			reductions *rp;
141
142		21	reduction_table = NEW2(nstates, reductions *);
143	✓✓	2440	for (rp = first_reduction; rp; rp = rp->next)
144		2419	reduction_table[rp->number] = rp;
145		21	}
146
147
148			void
149			set_maxrhs(void)
150		21	{
151			short itemp, item_end;
152			int length, max;
153
154		21	length = 0;
155		21	max = 0;
156		21	item_end = ritem + nitems;
157	✓✓	6928	for (itemp = ritem; itemp < item_end; itemp++) {
158	✓✓	6907	if (*itemp >= 0) {
159		4623	length++;
160			} else {
161	✓✓	2284	if (length > max) max = length;
162		2284	length = 0;
163			}
164			}
165
166		21	maxrhs = max;
167		21	}
168
169
170			void
171			initialize_LA(void)
172		21	{
173			int i, j, k;
174			reductions *rp;
175
176		21	lookaheads = NEW2(nstates + 1, short);
177
178		21	k = 0;
179	✓✓	4023	for (i = 0; i < nstates; i++) {
180		4002	lookaheads[i] = k;
181		4002	rp = reduction_table[i];
182	✓✓	4002	if (rp)
183		2419	k += rp->nreds;
184			}
185		21	lookaheads[nstates] = k;
186
187		21	LA = NEW2(k * tokensetsize, unsigned);
188		21	LAruleno = NEW2(k, short);
189		21	lookback = NEW2(k, shorts *);
190
191		21	k = 0;
192	✓✓	4023	for (i = 0; i < nstates; i++) {
193		4002	rp = reduction_table[i];
194	✓✓	4002	if (rp) {
195	✓✓	4864	for (j = 0; j < rp->nreds; j++) {
196		2445	LAruleno[k] = rp->rules[j];
197		2445	k++;
198			}
199			}
200			}
201		21	}
202
203			void
204			set_goto_map(void)
205		21	{
206			shifts *sp;
207			int i, k, symbol;
208			int state1, state2;
209			short *temp_map;
210
211		21	goto_map = NEW2(nvars + 1, short) - ntokens;
212		21	temp_map = NEW2(nvars + 1, short) - ntokens;
213
214		21	ngotos = 0;
215	✓✓	2118	for (sp = first_shift; sp; sp = sp->next) {
216	✓✓	4228	for (i = sp->nshifts - 1; i >= 0; i--) {
217		4139	symbol = accessing_symbol[sp->shift[i]];
218
219	✓✓	4139	if (ISTOKEN(symbol)) break;
220
221	✗✓	2131	if (ngotos == MAXSHORT)
222			fatal("too many gotos");
223
224		2131	ngotos++;
225		2131	goto_map[symbol]++;
226			}
227			}
228
229		21	k = 0;
230	✓✓	908	for (i = ntokens; i < nsyms; i++) {
231		887	temp_map[i] = k;
232		887	k += goto_map[i];
233			}
234
235	✓✓	908	for (i = ntokens; i < nsyms; i++)
236		887	goto_map[i] = temp_map[i];
237
238		21	goto_map[nsyms] = ngotos;
239		21	temp_map[nsyms] = ngotos;
240
241		21	from_state = NEW2(ngotos, short);
242		21	to_state = NEW2(ngotos, short);
243
244	✓✓	2118	for (sp = first_shift; sp; sp = sp->next) {
245		2097	state1 = sp->number;
246	✓✓	4228	for (i = sp->nshifts - 1; i >= 0; i--) {
247		4139	state2 = sp->shift[i];
248		4139	symbol = accessing_symbol[state2];
249
250	✓✓	4139	if (ISTOKEN(symbol)) break;
251
252		2131	k = temp_map[symbol]++;
253		2131	from_state[k] = state1;
254		2131	to_state[k] = state2;
255			}
256			}
257
258		21	free(temp_map + ntokens);
259		21	}
260
261
262
263			/* Map_goto maps a state/symbol pair into its numeric representation. */
264
265			int
266			map_goto(int state, int symbol)
267		2404	{
268			int high, low, middle, s;
269
270		2404	low = goto_map[symbol];
271		2404	high = goto_map[symbol + 1];
272
273			for (;;) {
274	✗✓	5577	assert(low <= high);
275		5577	middle = (low + high) >> 1;
276		5577	s = from_state[middle];
277	✓✓	5577	if (s == state)
278		2404	return (middle);
279	✓✓	3173	else if (s < state)
280		1573	low = middle + 1;
281			else
282		1600	high = middle - 1;
283			}
284			}
285
286
287			void
288			initialize_F(void)
289		21	{
290			int i, j, k;
291			shifts *sp;
292			short edge, rp, **reads;
293			unsigned int *rowp;
294			int nedges, stateno, symbol, nwords;
295
296		21	nwords = ngotos * tokensetsize;
297		21	F = NEW2(nwords, unsigned);
298
299		21	reads = NEW2(ngotos, short *);
300		21	edge = NEW2(ngotos + 1, short);
301		21	nedges = 0;
302
303		21	rowp = F;
304	✓✓	2152	for (i = 0; i < ngotos; i++) {
305		2131	stateno = to_state[i];
306		2131	sp = shift_table[stateno];
307
308	✓✓	2131	if (sp) {
309		987	k = sp->nshifts;
310
311	✓✓	3925	for (j = 0; j < k; j++) {
312		3569	symbol = accessing_symbol[sp->shift[j]];
313	✓✓	3569	if (ISVAR(symbol))
314		631	break;
315		2938	SETBIT(rowp, symbol);
316			}
317
318	✓✓	1521	for (; j < k; j++) {
319		1521	symbol = accessing_symbol[sp->shift[j]];
320	✓✓	1521	if (nullable[symbol])
321		229	edge[nedges++] = map_goto(stateno, symbol);
322			}
323
324	✓✓	987	if (nedges) {
325		214	reads[i] = rp = NEW2(nedges + 1, short);
326
327	✓✓	443	for (j = 0; j < nedges; j++)
328		229	rp[j] = edge[j];
329
330		214	rp[nedges] = -1;
331		214	nedges = 0;
332			}
333			}
334
335		2131	rowp += tokensetsize;
336			}
337
338		21	SETBIT(F, 0);
339		21	digraph(reads);
340
341	✓✓	2152	for (i = 0; i < ngotos; i++)
342		2131	free(reads[i]);
343
344		21	free(reads);
345		21	free(edge);
346		21	}
347
348
349			void
350			build_relations(void)
351		21	{
352			int i, j, k;
353			short rulep, rp;
354			shifts *sp;
355			int length, nedges, done;
356			int state1, stateno, symbol1, symbol2;
357			short shortp, edge, *states;
358			short **new_includes;
359
360		21	includes = NEW2(ngotos, short *);
361		21	edge = NEW2(ngotos + 1, short);
362		21	states = NEW2(maxrhs + 1, short);
363
364	✓✓	2152	for (i = 0; i < ngotos; i++) {
365		2131	nedges = 0;
366		2131	state1 = from_state[i];
367		2131	symbol1 = accessing_symbol[to_state[i]];
368
369	✓✓	7520	for (rulep = derives[symbol1]; *rulep >= 0; rulep++) {
370		5389	length = 1;
371		5389	states[0] = state1;
372		5389	stateno = state1;
373
374	✓✓	15899	for (rp = ritem + rrhs[rulep]; rp >= 0; rp++) {
375		10510	symbol2 = *rp;
376		10510	sp = shift_table[stateno];
377		10510	k = sp->nshifts;
378
379	✓✗	50949	for (j = 0; j < k; j++) {
380		50949	stateno = sp->shift[j];
381	✓✓	50949	if (accessing_symbol[stateno] == symbol2)
382		10510	break;
383			}
384
385		10510	states[length++] = stateno;
386			}
387
388		5389	add_lookback_edge(stateno, *rulep, i);
389
390		5389	length--;
391		5389	done = 0;
392	✓✓	16692	while (!done) {
393		5914	done = 1;
394		5914	rp--;
395	✓✓	5914	if (ISVAR(*rp)) {
396		2175	stateno = states[--length];
397		2175	edge[nedges++] = map_goto(stateno, *rp);
398	✓✓	2175	if (nullable[*rp] && length > 0)
399		525	done = 0;
400			}
401			}
402			}
403
404	✓✓	2131	if (nedges) {
405		958	includes[i] = shortp = NEW2(nedges + 1, short);
406	✓✓	3133	for (j = 0; j < nedges; j++)
407		2175	shortp[j] = edge[j];
408		958	shortp[nedges] = -1;
409			}
410			}
411
412		21	new_includes = transpose(includes, ngotos);
413
414	✓✓	2152	for (i = 0; i < ngotos; i++)
415		2131	free(includes[i]);
416
417		21	free(includes);
418
419		21	includes = new_includes;
420
421		21	free(edge);
422		21	free(states);
423		21	}
424
425			void
426			add_lookback_edge(int stateno, int ruleno, int gotono)
427		5389	{
428			int i, k, found;
429			shorts *sp;
430
431		5389	i = lookaheads[stateno];
432		5389	k = lookaheads[stateno + 1];
433		5389	found = 0;
434	✓✓	16202	while (!found && i < k) {
435	✓✓	5424	if (LAruleno[i] == ruleno)
436		5389	found = 1;
437			else
438		35	++i;
439			}
440	✗✓	5389	assert(found);
441
442		5389	sp = NEW(shorts);
443		5389	sp->next = lookback[i];
444		5389	sp->value = gotono;
445		5389	lookback[i] = sp;
446		5389	}
447
448
449
450			short **
451			transpose(short **R, int n)
452		21	{
453			short new_R, temp_R, nedges, sp;
454			int i, k;
455
456		21	nedges = NEW2(n, short);
457
458	✓✓	2152	for (i = 0; i < n; i++) {
459		2131	sp = R[i];
460	✓✓	2131	if (sp) {
461	✓✓	3133	while (*sp >= 0)
462		2175	nedges[*sp++]++;
463			}
464			}
465
466		21	new_R = NEW2(n, short *);
467		21	temp_R = NEW2(n, short *);
468
469	✓✓	2152	for (i = 0; i < n; i++) {
470		2131	k = nedges[i];
471	✓✓	2131	if (k > 0) {
472		1420	sp = NEW2(k + 1, short);
473		1420	new_R[i] = sp;
474		1420	temp_R[i] = sp;
475		1420	sp[k] = -1;
476			}
477			}
478
479		21	free(nedges);
480
481	✓✓	2152	for (i = 0; i < n; i++) {
482		2131	sp = R[i];
483	✓✓	2131	if (sp) {
484	✓✓	3133	while (*sp >= 0)
485		2175	temp_R[sp++]++ = i;
486			}
487			}
488
489		21	free(temp_R);
490
491		21	return (new_R);
492			}
493
494
495			void
496			compute_FOLLOWS(void)
497		21	{
498		21	digraph(includes);
499		21	}
500
501			void
502			compute_lookaheads(void)
503		21	{
504			int i, n;
505			unsigned int fp1, fp2, *fp3;
506			shorts sp, next;
507			unsigned int *rowp;
508
509		21	rowp = LA;
510		21	n = lookaheads[nstates];
511	✓✓	2466	for (i = 0; i < n; i++) {
512		2445	fp3 = rowp + tokensetsize;
513	✓✓	7834	for (sp = lookback[i]; sp; sp = sp->next) {
514		5389	fp1 = rowp;
515		5389	fp2 = F + tokensetsize * sp->value;
516	✓✓	26688	while (fp1 < fp3)
517		15910	fp1++ \|= fp2++;
518			}
519		2445	rowp = fp3;
520			}
521
522	✓✓	2466	for (i = 0; i < n; i++)
523	✓✓	7834	for (sp = lookback[i]; sp; sp = next) {
524		5389	next = sp->next;
525		5389	free(sp);
526			}
527
528		21	free(lookback);
529		21	free(F);
530		21	}
531
532			void
533			digraph(short **relation)
534		42	{
535			int i;
536
537		42	infinity = ngotos + 2;
538		42	INDEX = NEW2(ngotos + 1, short);
539		42	VERTICES = NEW2(ngotos + 1, short);
540		42	top = 0;
541		42	R = relation;
542
543		42	memset(INDEX, 0, ngotos * sizeof(short));
544	✓✓	4304	for (i = 0; i < ngotos; i++)
545	✓✓	4262	if (R[i])
546		1634	traverse(i);
547
548		42	free(INDEX);
549		42	free(VERTICES);
550		42	}
551
552
553			void
554			traverse(int i)
555		2547	{
556			unsigned int base, fp1, fp2, fp3;
557			int j, height;
558			short *rp;
559
560		2547	VERTICES[++top] = i;
561		2547	INDEX[i] = height = top;
562
563		2547	base = F + i * tokensetsize;
564		2547	fp3 = base + tokensetsize;
565
566		2547	rp = R[i];
567	✓✓	2547	if (rp) {
568	✓✓	5150	while ((j = *rp++) >= 0) {
569	✓✓	3053	if (INDEX[j] == 0)
570		913	traverse(j);
571
572	✓✓	3053	if (INDEX[i] > INDEX[j])
573		6	INDEX[i] = INDEX[j];
574
575		3053	fp1 = base;
576		3053	fp2 = F + j * tokensetsize;
577
578	✓✓	15015	while (fp1 < fp3)
579		8909	fp1++ \|= fp2++;
580			}
581			}
582
583	✓✓	2547	if (INDEX[i] == height) {
584			for (;;) {
585		2547	j = VERTICES[top--];
586		2547	INDEX[j] = infinity;
587
588	✓✓	2547	if (i == j)
589		2541	break;
590
591		6	fp1 = base;
592		6	fp2 = F + j * tokensetsize;
593
594	✓✓	23	while (fp1 < fp3)
595		11	fp2++ = fp1++;
596			}
597			}
598		2547	}