/************************************************************************/
/*                                                                      */
/* Copyright (c) 1988 -                                                 */
/*     The Rector and Visitors of the University of Virginia            */
/*                                                                      */
/* This code may not be distributed further without permission          */
/*      from the University of Virginia.                                */
/* This code is distributed WITHOUT ANY WARRANTY.  No claims are        */
/*      made as to whether it serves any particular purpose or even     */
/*      works at all.                                                   */
/*                                                                      */
/************************************************************************/

#include <string.h>
#include "types.h"
#include "tword.h"
#include "scan.h"
#include "stopset.h"
#include "object.h"
#include "node.h"
#include "error.h"

extern int p_reached;

struct casebuf {
	int csval, cslab;
};

/*
 * case-statement = "case" case-index "of" case-list-element
 *		{ ";" case-list-element } [ [ ";" ] "otherwise" statement ]
 *		[ ";" ] "end" .
 *
 * case-list-element = case-constant-list ":" statement .
 *
 */

p_case_stmt(stop)
	STOPSET stop;
{
	OBJECT *caseidx, *list, *biglist=OB_NULL;
	STOPBUF mystop1, mystop2, mystop3, mystop4;
	int count, total=0, caselab, othlab, toplab, nextstmt;
	NODE *idxnode;

	/* parse case-index expression and emit code to compute it */

	c_bgnstmt(src_linenum());
	set_or(mystop1, stop, expr_begin, stmt_begin, set_cons(SY_OF,
		SY_SEMI, SY_COLON, SY_OTHERW, SY_END, 0), S0);
	p_expect(SY_CASE, mystop1);
	set_or(mystop1, stop, const_begin, stmt_begin, set_cons(SY_OF,
		SY_SEMI, SY_COLON, SY_OTHERW, SY_END, 0), S0);
	caseidx = p_expression(&idxnode, mystop1);
	if (!OB_ISORDINAL(caseidx)) {
		sprintf(err_text, err_ord, "case expression");
		err_msg(E_FATAL, E_PREVSYMBOL);
		caseidx = std_universal;
		idxnode->nd_type = TW_INT;
	}
	idxnode = nd_build(ND_SCONV, TW_INT, idxnode, ND_NULL);
	nd_compile(idxnode);
	c_switchv(TW_INT);

	/*
	 * emit jump to label that will be put at the end of the last
	 * case arm.
	 */

	c_goto(toplab = lb_new(), ob_level);
	othlab = nextstmt = lb_new();

	/*
	 * parse all the case arms.  We generate a label at the start
	 * of each arm.  We build a linked list of OBJECTS containing
	 * all of the case-constants.  Each list OBJECT also stores
	 * the appropriate case arm statement label
	 */

	set_or(mystop1, stop, const_begin, stmt_begin, set_cons(SY_SEMI,
		SY_COLON, SY_OTHERW, SY_END, 0), S0);
	p_expect(SY_OF, mystop1);
	set_or(mystop1, stop, stmt_begin, set_cons(SY_SEMI, SY_COLON,
		SY_OTHERW, SY_END, 0), S0);
	set_or(mystop2, stop, const_begin, stmt_begin, set_cons(SY_SEMI,
		SY_OTHERW, SY_END, 0), S0);
	set_or(mystop3, stop, const_begin, set_cons(SY_SEMI, SY_COLON,
		SY_OTHERW, SY_END, 0), S0);
	set_or(mystop4, stop, const_begin, stmt_begin, set_cons(SY_COLON,
		SY_OTHERW, SY_END, 0), S0);
	do {
		list = p_case_const_list(&count, caseidx, mystop1);
		total += count;
		p_expect(SY_COLON, mystop2);
		c_label(caselab = lb_new());

		while (list) {		/* merge case lists onto one */
			OBJECT *next;
			next = list->ob_prev;
			list->ob_prev = biglist;
			list->ob.const.cslab = caselab;
			biglist = list;
			list = next;
		}

		p_reached = 1;
		lb_descend();
		p_statement(mystop3);  /* parse case arm */
		lb_ascend();
		c_goto(nextstmt, ob_level);
		if (symbol != SY_SEMI)
			break;
		p_expect(SY_SEMI, mystop4);
	}while (set_in(symbol, const_begin));

	/* parse "otherwise" clause */

	if (symbol == SY_OTHERW) {
		set_or(mystop1, stop, stmt_begin, set_cons(SY_SEMI, SY_END,
			0), S0);
		p_expect(SY_OTHERW, mystop1);
		set_or(mystop1, stop, set_cons(SY_SEMI, SY_END, 0), S0);
		c_label(othlab = lb_new());
		lb_descend();
		p_statement(mystop1);
		lb_ascend();
		c_goto(nextstmt, ob_level);
		if (symbol == SY_SEMI) {
			set_or(mystop1, stop, set_cons(SY_END, 0), S0);
			p_expect(SY_SEMI, mystop1);
		}
	}

	p_expect(SY_END, stop);
	c_label(toplab);
	p_build_case(biglist, total, othlab);
	c_label(nextstmt);
}

/*
 * case-constant-list = constant { "," constant } .
 */

OBJECT *
p_case_const_list(count, type, stop)
	OBJECT *type;
	int *count;
	STOPSET stop;
{
	STOPBUF mystop1, mystop2;
	OBJECT *const, *list=OB_NULL;
	int errflag=0;

	/*
	 * return a linked list of constant OBJECTS and stash the
	 * number of constants in (*count)
	 */
	set_or(mystop1, stop, set_cons(SY_COMMA, 0), S0);
	set_or(mystop2, stop, const_begin, S0);
	(*count) = 0;
	for (;;) {
		const = p_constant(ID_NULL, mystop1);
		if (!ck_constant(const, type))
			errflag++;
		else if (const->ob_type != std_universal) {
			const->ob_prev = list;
			list = const;
			(*count)++;
		}
		if (symbol != SY_COMMA)
			break;
		p_expect(SY_COMMA, mystop2);
	}
	if (errflag) {
		strcpy(err_text,
			"case constant list has constant(s) of wrong type");
		err_msg(E_FATAL, E_PREVSYMBOL);
	}
	return(list);
}

/*
 * p_build_case() emits the code that selects which arm of the
 * case statement to execute.  We process a linked list of
 * constant OBJECTS.  Each list element has a constant value
 * and the appropriate case arm statement label to jump to
 * if the case-index expression is equal to the constant value.
 */

p_build_case(list, count, othlab)
	OBJECT *list;
	int count, othlab;
{
	struct casebuf *cb;
	int i, j, value, range;

	extern char *malloc();
	extern void free();

	cb = (struct casebuf *) malloc ((unsigned) (count *
		sizeof(struct casebuf)));
	if (!cb) {
		sprintf(err_text, err_nomem, "p_build_case()");
		err_msg(E_INTERNAL, E_CURLINE);
	}

	/*
	 * Build a sorted array of case constants and their statement labels.
	 * Use insertion sort and look for duplicates.
	 */

	for (i = -1; list; list = list->ob_prev, i++) {
		value = list->ob.const.val.i;
		for (j = i+1; j > 0 && cb[j-1].csval > value; j--)
			cb[j] = cb[j-1];
		cb[j].csval = value;
		cb[j].cslab = list->ob.const.cslab;
		if (j > 0 && cb[j-1].csval == value) {
			strcpy(err_text, "duplicate values in case constant lists");
			err_msg(E_FATAL, E_CURLINE);
			free(cb);
			return;
		}
	}
	range = cb[count-1].csval - cb[0].csval;
	c_switchs (TW_INT, count, cb[0].csval, range);

	/*
	 * Three styles of case statements:  1) Jump table for when the
	 * case values fall within a fairly narrow range. 3) Binary search
	 * for a large number of values over a wide range.  2) Linear
	 * search for a small number of values.
	 */

	if (range < (3 * count) && count >= 4) {	/* Jump table */
		c_casel(cb[0].csval, range);
		value = cb[0].csval;
		for (i = 0; i < count; value++)
			c_word((value == cb[i].csval) ? cb[i++].cslab : othlab);
		c_goto(othlab, ob_level);
	}

	else if (count > 8) {		/* Binary search */
		p_binary_case(cb, 0, count-1, 0, othlab);
	}

	else {		/* Linear search */
		for (i = 0; i < count; i++)
			c_cmpeq(TW_INT, cb[i].csval, cb[i].cslab);
		c_goto(othlab, ob_level);
	}

	free(cb);
}

/*
 * p_binary_case codes a binary search of the case list values.
 * p_binary_case emits code that examines the midpoint of the case value
 * array and recursively applies itself to the array segments
 * preceeding and following the midpoint.
 */

p_binary_case (cb, low, high, label, othlab)
	struct casebuf cb[];
	int low, high, label, othlab;
{
	int med, gtlab;

	med = (low + high) / 2;
	if (label)
		c_label(label);
	c_cmpeq (TW_INT, cb[med].csval, cb[med].cslab);
	if (high > med)
		c_cmpgt (TW_INT, cb[med].csval, gtlab = lb_new());
	if (low < med)
		p_binary_case (cb, low, med-1, 0, othlab);
	else
		c_goto(othlab, ob_level);	/* search failure -- goto otherwise */
	if (high > med)
		p_binary_case (cb, med+1, high, gtlab, othlab);
}
