keyword-gen.c   [plain text]

/*
 * keyword-gen.c -- generate keyword scanner finite state machine and
 *		    keyword_text array.
 *		    This program is run to generate ntp_keyword.h
 */
#include <config.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <ntp_stdlib.h>
#include <ntp_config.h>
#include <lib_strbuf.h>
#include "ntp_scanner.h"
#include "ntp_parser.h"


#ifdef QSORT_USES_VOID_P
typedef const void *	QSORTP;
#else
typedef char *		QSORTP;
#endif

/* Define a structure to hold a (keyword, token) pair */
struct key_tok {
	char *	key;		/* Keyword */
	int	token;		/* Associated Token */
	follby	followedby;	/* nonzero indicates the next token(s)
				   forced to be string(s) */
};

struct key_tok ntp_keywords[] = {
{ "automax",		T_Automax,		FOLLBY_TOKEN },
{ "broadcast",		T_Broadcast,		FOLLBY_STRING },
{ "broadcastclient",	T_Broadcastclient,	FOLLBY_TOKEN },
{ "broadcastdelay",	T_Broadcastdelay,	FOLLBY_TOKEN },
{ "calldelay",		T_Calldelay,		FOLLBY_TOKEN },
{ "disable",		T_Disable,		FOLLBY_TOKEN },
{ "driftfile",		T_Driftfile,		FOLLBY_STRING },
{ "enable",		T_Enable,		FOLLBY_TOKEN },
{ "end",		T_End,			FOLLBY_TOKEN },
{ "filegen",		T_Filegen,		FOLLBY_TOKEN },
{ "fudge",		T_Fudge,		FOLLBY_STRING },
{ "includefile",	T_Includefile,		FOLLBY_STRING },
{ "leapfile",		T_Leapfile,		FOLLBY_STRING },
{ "logconfig",		T_Logconfig,		FOLLBY_STRINGS_TO_EOC },
{ "logfile",		T_Logfile,		FOLLBY_STRING },
{ "manycastclient",	T_Manycastclient,	FOLLBY_STRING },
{ "manycastserver",	T_Manycastserver,	FOLLBY_STRINGS_TO_EOC },
{ "multicastclient",	T_Multicastclient,	FOLLBY_STRINGS_TO_EOC },
{ "peer",		T_Peer,			FOLLBY_STRING },
{ "phone",		T_Phone,		FOLLBY_STRINGS_TO_EOC },
{ "pidfile",		T_Pidfile,		FOLLBY_STRING },
{ "pool",		T_Pool,			FOLLBY_STRING },
{ "discard",		T_Discard,		FOLLBY_TOKEN },
{ "restrict",		T_Restrict,		FOLLBY_TOKEN },
{ "server",		T_Server,		FOLLBY_STRING },
{ "setvar",		T_Setvar,		FOLLBY_STRING },
{ "statistics",		T_Statistics,		FOLLBY_TOKEN },
{ "statsdir",		T_Statsdir,		FOLLBY_STRING },
{ "tick",		T_Tick,			FOLLBY_TOKEN },
{ "tinker",		T_Tinker,		FOLLBY_TOKEN },
{ "tos",		T_Tos,			FOLLBY_TOKEN },
{ "trap",		T_Trap,			FOLLBY_STRING },
{ "unconfig",		T_Unconfig,		FOLLBY_STRING },
{ "unpeer",		T_Unpeer,		FOLLBY_STRING },
/* authentication_command */
{ "controlkey",		T_ControlKey,		FOLLBY_TOKEN },
{ "crypto",		T_Crypto,		FOLLBY_TOKEN },
{ "keys",		T_Keys,			FOLLBY_STRING },
{ "keysdir",		T_Keysdir,		FOLLBY_STRING },
{ "ntpsigndsocket",	T_NtpSignDsocket,	FOLLBY_STRING },
{ "requestkey",		T_Requestkey,		FOLLBY_TOKEN },
{ "revoke",		T_Revoke,		FOLLBY_TOKEN },
{ "trustedkey",		T_Trustedkey,		FOLLBY_TOKEN },
/* IPv4/IPv6 protocol override flag */
{ "-4",			T_Ipv4_flag,		FOLLBY_TOKEN },
{ "-6",			T_Ipv6_flag,		FOLLBY_TOKEN },
/* option */
{ "autokey",		T_Autokey,		FOLLBY_TOKEN },
{ "bias",		T_Bias,			FOLLBY_TOKEN },
{ "burst",		T_Burst,		FOLLBY_TOKEN },
{ "iburst",		T_Iburst,		FOLLBY_TOKEN },
{ "key",		T_Key,			FOLLBY_TOKEN },
{ "maxpoll",		T_Maxpoll,		FOLLBY_TOKEN },
{ "minpoll",		T_Minpoll,		FOLLBY_TOKEN },
{ "mode",		T_Mode,			FOLLBY_TOKEN },
{ "noselect",		T_Noselect,		FOLLBY_TOKEN },
{ "preempt",		T_Preempt,		FOLLBY_TOKEN },
{ "true",		T_True,			FOLLBY_TOKEN },
{ "prefer",		T_Prefer,		FOLLBY_TOKEN },
{ "ttl",		T_Ttl,			FOLLBY_TOKEN },
{ "version",		T_Version,		FOLLBY_TOKEN },
{ "xleave",		T_Xleave,		FOLLBY_TOKEN },
/* crypto_command */
{ "host",		T_Host,			FOLLBY_STRING },
{ "ident",		T_Ident,		FOLLBY_STRING },
{ "pw",			T_Pw,			FOLLBY_STRING },
{ "randfile",		T_Randfile,		FOLLBY_STRING },
{ "sign",		T_Sign,			FOLLBY_STRING },
{ "digest",		T_Digest,		FOLLBY_STRING },
/*** MONITORING COMMANDS ***/
/* stat */
{ "clockstats",		T_Clockstats,		FOLLBY_TOKEN },
{ "cryptostats",	T_Cryptostats,		FOLLBY_TOKEN },
{ "loopstats",		T_Loopstats,		FOLLBY_TOKEN },
{ "peerstats",		T_Peerstats,		FOLLBY_TOKEN },
{ "rawstats",		T_Rawstats,		FOLLBY_TOKEN },
{ "sysstats", 		T_Sysstats,		FOLLBY_TOKEN },
{ "protostats",		T_Protostats,		FOLLBY_TOKEN },
{ "timingstats",	T_Timingstats,		FOLLBY_TOKEN },
/* filegen_option */
{ "file",		T_File,			FOLLBY_STRING },
{ "link",		T_Link,			FOLLBY_TOKEN },
{ "nolink",		T_Nolink,		FOLLBY_TOKEN },
{ "type",		T_Type,			FOLLBY_TOKEN },
/* filegen_type */
{ "age",		T_Age,			FOLLBY_TOKEN },
{ "day",		T_Day,			FOLLBY_TOKEN },
{ "month",		T_Month,		FOLLBY_TOKEN },
{ "none",		T_None,			FOLLBY_TOKEN },
{ "pid",		T_Pid,			FOLLBY_TOKEN },
{ "week",		T_Week,			FOLLBY_TOKEN },
{ "year",		T_Year,			FOLLBY_TOKEN },
/*** ORPHAN MODE COMMANDS ***/
/* tos_option */
{ "minclock",		T_Minclock,		FOLLBY_TOKEN },
{ "maxclock",		T_Maxclock,		FOLLBY_TOKEN },
{ "minsane",		T_Minsane,		FOLLBY_TOKEN },
{ "floor",		T_Floor,		FOLLBY_TOKEN },
{ "ceiling",		T_Ceiling,		FOLLBY_TOKEN },
{ "cohort",		T_Cohort,		FOLLBY_TOKEN },
{ "mindist",		T_Mindist,		FOLLBY_TOKEN },
{ "maxdist",		T_Maxdist,		FOLLBY_TOKEN },
{ "beacon",		T_Beacon,		FOLLBY_TOKEN },
{ "orphan",		T_Orphan,		FOLLBY_TOKEN },
/* access_control_flag */
{ "default",		T_Default,		FOLLBY_TOKEN },
{ "flake",		T_Flake,		FOLLBY_TOKEN },
{ "ignore",		T_Ignore,		FOLLBY_TOKEN },
{ "limited",		T_Limited,		FOLLBY_TOKEN },
{ "mssntp",		T_Mssntp,		FOLLBY_TOKEN },
{ "kod",		T_Kod,			FOLLBY_TOKEN },
{ "lowpriotrap",	T_Lowpriotrap,		FOLLBY_TOKEN },
{ "mask",		T_Mask,			FOLLBY_TOKEN },
{ "nomodify",		T_Nomodify,		FOLLBY_TOKEN },
{ "nopeer",		T_Nopeer,		FOLLBY_TOKEN },
{ "noquery",		T_Noquery,		FOLLBY_TOKEN },
{ "noserve",		T_Noserve,		FOLLBY_TOKEN },
{ "notrap",		T_Notrap,		FOLLBY_TOKEN },
{ "notrust",		T_Notrust,		FOLLBY_TOKEN },
{ "ntpport",		T_Ntpport,		FOLLBY_TOKEN },
/* discard_option */
{ "average",		T_Average,		FOLLBY_TOKEN },
{ "minimum",		T_Minimum,		FOLLBY_TOKEN },
{ "monitor",		T_Monitor,		FOLLBY_TOKEN },
/* fudge_factor */
{ "flag1",		T_Flag1,		FOLLBY_TOKEN },
{ "flag2",		T_Flag2,		FOLLBY_TOKEN },
{ "flag3",		T_Flag3,		FOLLBY_TOKEN },
{ "flag4",		T_Flag4,		FOLLBY_TOKEN },
{ "refid",		T_Refid,		FOLLBY_STRING },
{ "stratum",		T_Stratum,		FOLLBY_TOKEN },
{ "time1",		T_Time1,		FOLLBY_TOKEN },
{ "time2",		T_Time2,		FOLLBY_TOKEN },
/* system_option */
{ "auth",		T_Auth,			FOLLBY_TOKEN },
{ "bclient",		T_Bclient,		FOLLBY_TOKEN },
{ "calibrate",		T_Calibrate,		FOLLBY_TOKEN },
{ "kernel",		T_Kernel,		FOLLBY_TOKEN },
{ "ntp",		T_Ntp,			FOLLBY_TOKEN },
{ "stats",		T_Stats,		FOLLBY_TOKEN },
/* tinker_option */
{ "step",		T_Step,			FOLLBY_TOKEN },
{ "panic",		T_Panic,		FOLLBY_TOKEN },
{ "dispersion",		T_Dispersion,		FOLLBY_TOKEN },
{ "stepout",		T_Stepout,		FOLLBY_TOKEN },
{ "allan",		T_Allan,		FOLLBY_TOKEN },
{ "huffpuff",		T_Huffpuff,		FOLLBY_TOKEN },
{ "freq",		T_Freq,			FOLLBY_TOKEN },
/* miscellaneous_command */
{ "port",		T_Port,			FOLLBY_TOKEN },
{ "interface",		T_Interface,		FOLLBY_TOKEN },
{ "qos",		T_Qos,			FOLLBY_TOKEN },
{ "saveconfigdir",	T_Saveconfigdir,	FOLLBY_STRING },
/* interface_command (ignore and interface already defined) */
{ "nic",		T_Nic,			FOLLBY_TOKEN },
{ "all",		T_All,			FOLLBY_TOKEN },
{ "ipv4",		T_Ipv4,			FOLLBY_TOKEN },
{ "ipv6",		T_Ipv6,			FOLLBY_TOKEN },
{ "wildcard",		T_Wildcard,		FOLLBY_TOKEN },
{ "listen",		T_Listen,		FOLLBY_TOKEN },
{ "drop",		T_Drop,			FOLLBY_TOKEN },
/* simulator commands */
{ "simulate",		T_Simulate,		FOLLBY_TOKEN },
{ "simulation_duration",T_Sim_Duration,		FOLLBY_TOKEN },
{ "beep_delay",		T_Beep_Delay,		FOLLBY_TOKEN },
{ "duration",		T_Duration,		FOLLBY_TOKEN },
{ "server_offset",	T_Server_Offset,	FOLLBY_TOKEN },
{ "freq_offset",	T_Freq_Offset,		FOLLBY_TOKEN },
{ "wander",		T_Wander,		FOLLBY_TOKEN },
{ "jitter",		T_Jitter,		FOLLBY_TOKEN },
{ "prop_delay",		T_Prop_Delay,		FOLLBY_TOKEN },
{ "proc_delay",		T_Proc_Delay,		FOLLBY_TOKEN },
};


typedef struct big_scan_state_tag {
	char	ch;		/* Character this state matches on */
	char	followedby;	/* Forces next token(s) to T_String */
	u_short	finishes_token;	/* nonzero ID if last keyword char */
	u_short	match_next_s;	/* next state to check matching ch */
	u_short	other_next_s;	/* next state to check if not ch */
} big_scan_state;

/*
 * Note: to increase MAXSTATES beyond 2048, be aware it is currently
 * crammed into 11 bits in scan_state form.  Raising to 4096 would be
 * relatively easy by storing the followedby value in a separate
 * array with one entry per token, and shrinking the char value to
 * 7 bits to free a bit for accepting/non-accepting.  More than 4096
 * states will require expanding scan_state beyond 32 bits each.
 */
#define MAXSTATES 2048

const char *	current_keyword;/* for error reporting */
big_scan_state	sst[MAXSTATES];	/* scanner FSM state entries */
int		sst_highwater;	/* next entry index to consider */
char *		symb[1024];	/* map token ID to symbolic name */

/* for libntp */
const char *	progname = "keyword-gen";
volatile int	debug = 1;

int		main			(int, char **);
static void	generate_preamble	(void);
static void	generate_fsm		(void);
static void	generate_token_text	(void);
static int	create_keyword_scanner	(void);
static int	create_scan_states	(char *, int, follby, int);
int		compare_key_tok_id	(QSORTP, QSORTP);
int		compare_key_tok_text	(QSORTP, QSORTP);
void		populate_symb		(char *);
const char *	symbname		(int);


int main(int argc, char **argv)
{
	if (argc < 2) {
		fprintf(stderr, "Usage:\n%s t_header.h\n", argv[0]);
		exit(1);
	}
	populate_symb(argv[1]);

	generate_preamble();
	generate_token_text();
	generate_fsm();

	return 0;
}


static void
generate_preamble(void)
{
	time_t now;
	char timestamp[128];
	char preamble[] =
"/*\n"
" * ntp_keyword.h\n"
" * \n"
" * NOTE: edit this file with caution, it is generated by keyword-gen.c\n"
" *\t Generated %s UTC	  diff_ignore_line\n"
" *\n"
" */\n"
"#include \"ntp_scanner.h\"\n"
"#include \"ntp_parser.h\"\n"
"\n";

	time(&now);
	if (!strftime(timestamp, sizeof(timestamp),
		      "%Y-%m-%d %H:%M:%S", gmtime(&now)))
		timestamp[0] = '\0';

	printf(preamble, timestamp);
}


static void
generate_fsm(void)
{
	char token_id_comment[128];
	int initial_state;
	int i;
	int token;

	/* 
	 * Sort ntp_keywords in alphabetical keyword order.  This is
	 * not necessary, but minimizes nonfunctional changes in the
	 * generated finite state machine when keywords are modified.
	 */
	qsort(ntp_keywords, COUNTOF(ntp_keywords),
	      sizeof(ntp_keywords[0]), compare_key_tok_text);

	/*
	 * To save space, reserve the state array entry matching each 
	 * token number for its terminal state, so the token identifier
	 * does not need to be stored in each state, but can be
	 * recovered trivially.  To mark the entry reserved,
	 * finishes_token is nonzero.
	 */

	for (i = 0; i < COUNTOF(ntp_keywords); i++) {
		token = ntp_keywords[i].token;
		if (1 > token || token >= COUNTOF(sst)) {
			fprintf(stderr,
				"keyword-gen sst[%u] too small "
				"for keyword '%s' id %d\n",
				COUNTOF(sst),
				ntp_keywords[i].key,
				token);
			exit(4);
		}
		sst[token].finishes_token = token;
	}

	initial_state = create_keyword_scanner();

	fprintf(stderr,
		"%d keywords consumed %d states of %d max.\n",
		(int)COUNTOF(ntp_keywords),
		sst_highwater - 1,
		(int)COUNTOF(sst) - 1);

	printf("#define SCANNER_INIT_S %d\n\n", initial_state);

	printf("const scan_state sst[%d] = {\n"
	       "/*SS_T( ch,\tf-by, match, other ),\t\t\t\t */\n"
	       "  0,\t\t\t\t      /* %5d %-17s */\n",
	       sst_highwater,
	       0, "");

	for (i = 1; i < sst_highwater; i++) {

		/* verify fields will fit */
		if (sst[i].followedby & ~0x3) {
			fprintf(stderr,
				"keyword-gen internal error "
				"sst[%d].followedby %d too big\n",
				i, sst[i].followedby);
			exit(7);
		}

		if (sst_highwater <= sst[i].match_next_s
		    || sst[i].match_next_s & ~0x7ff) {
			fprintf(stderr,
				"keyword-gen internal error "
				"sst[%d].match_next_s %d too big\n",
				i, sst[i].match_next_s);
			exit(8);
		}

		if (sst_highwater <= sst[i].other_next_s
		    || sst[i].other_next_s & ~0x7ff) {
			fprintf(stderr,
				"keyword-gen internal error "
				"sst[%d].other_next_s %d too big\n",
				i, sst[i].other_next_s);
			exit(9);
		}

		if (!sst[i].finishes_token)
			snprintf(token_id_comment,
				 sizeof(token_id_comment), "%5d %-17s",
				 i, (initial_state == i) 
					? "initial state" 
					: "");
		else {
			snprintf(token_id_comment, 
				 sizeof(token_id_comment), "%5d %-17s",
				 i, symbname(sst[i].finishes_token));
			if (i != sst[i].finishes_token) {
				fprintf(stderr,
					"keyword-gen internal error "
					"entry %d finishes token %d\n",
					i, sst[i].finishes_token);
				exit(5);
			}
		}

		printf("  S_ST( '%c',\t%d,    %5u, %5u )%s /* %s */\n",
		       sst[i].ch,
		       sst[i].followedby,
		       sst[i].match_next_s,
		       sst[i].other_next_s,
		       (i + 1 < sst_highwater)
			   ? ","
			   : " ",
		       token_id_comment);
	}

	printf("};\n\n");
}


/* Define a function to create the states of the scanner. This function
 * is used by the create_keyword_scanner function below.
 *
 * This function takes a suffix of a keyword, the token to be returned on
 * recognizing the complete keyword, and any pre-existing state that exists
 * for some other keyword that has the same prefix as the current one.
 */
static int
create_scan_states(
	char *	text, 
	int	token, 
	follby	followedby,
	int	prev_state
	)
{
	int my_state;
	int return_state;
	int prev_char_s;
	int curr_char_s;

	return_state = prev_state;
	curr_char_s = prev_state;
	prev_char_s = 0;

	/* Find the correct position to insert the state. 
	 * All states should be in alphabetical order
	 */
	while (curr_char_s && (text[0] < sst[curr_char_s].ch)) {
		prev_char_s = curr_char_s;
		curr_char_s = sst[curr_char_s].other_next_s;
	}

	/* 
	 * Check if a previously seen keyword has the same prefix as
	 * the current keyword.  If so, simply use the state for that
	 * keyword as my_state, otherwise, allocate a new state.
	 */
	if (curr_char_s && (text[0] == sst[curr_char_s].ch)) {
		my_state = curr_char_s;
		if ('\0' == text[1]) {
			fprintf(stderr,
				"Duplicate entries for keyword '%s' in"
				" keyword_gen.c ntp_keywords[].\n",
				current_keyword);
			exit(2);
		}
	} else {
		do
			my_state = sst_highwater++;
		while (my_state < COUNTOF(sst)
		       && sst[my_state].finishes_token);
		if (my_state >= COUNTOF(sst)) {
			fprintf(stderr,
				"fatal, keyword scanner state array "
				"sst[%d] is too small, modify\n"
				"keyword-gen.c to increase.\n",
				(int)COUNTOF(sst));
			exit(3);
		}
		/* Store the next character of the keyword */
		sst[my_state].ch = text[0]; 
		sst[my_state].other_next_s = curr_char_s;
		sst[my_state].followedby = FOLLBY_NON_ACCEPTING;

		if (prev_char_s)
			sst[prev_char_s].other_next_s = my_state;
		else
			return_state = my_state;
	}

	/* Check if the next character is '\0'.
	 * If yes, we are done with the recognition and this is an accepting
	 * state.
	 * If not, we need to continue scanning
	 */
	if ('\0' == text[1]) {
		sst[my_state].finishes_token = (u_short)token;
		sst[my_state].followedby = (char)followedby;

		if (sst[token].finishes_token != (u_short)token) {
			fprintf(stderr,
				"fatal, sst[%d] not reserved for %s.\n",
				token, symbname(token));
			exit(6);
		}
		/* relocate so token id is sst[] index */
		if (my_state != token) {
			sst[token] = sst[my_state];
			memset(&sst[my_state], 0,
			       sizeof(sst[my_state]));
			do
				sst_highwater--;
			while (sst[sst_highwater].finishes_token);
			my_state = token;
			if (prev_char_s)
				sst[prev_char_s].other_next_s = my_state;
			else
				return_state = my_state;
		}
	} else
		sst[my_state].match_next_s = 
		    create_scan_states(
			&text[1],
			token,
			followedby,
			sst[my_state].match_next_s);

	return return_state;
}


/* Define a function that takes a list of (keyword, token) values and
 * creates a keywords scanner out of it.
 */

static int
create_keyword_scanner(void)
{
	int scanner;
	int i;

	sst_highwater = 1;	/* index 0 invalid, unused */
	scanner = 0;

	for (i = 0; i < COUNTOF(ntp_keywords); i++) {
		current_keyword = ntp_keywords[i].key;
		scanner =
		    create_scan_states(
			ntp_keywords[i].key, 
			ntp_keywords[i].token, 
			ntp_keywords[i].followedby,
			scanner);
	}

	return scanner;
}


static void
generate_token_text(void)
{
	int lowest_id;
	int highest_id;
	int id_count;
	int id;
	int i;

	/* sort ntp_keywords in token ID order */
	qsort(ntp_keywords, COUNTOF(ntp_keywords),
	      sizeof(ntp_keywords[0]), compare_key_tok_id);

	lowest_id = ntp_keywords[0].token;
	highest_id = ntp_keywords[COUNTOF(ntp_keywords) - 1].token;
	id_count = highest_id - lowest_id + 1;

	printf("#define LOWEST_KEYWORD_ID %d\n\n", lowest_id);

	printf("const char * const keyword_text[%d] = {", id_count);

	id = lowest_id;
	i = 0;
	while (i < COUNTOF(ntp_keywords)) {
		while (id < ntp_keywords[i].token) {
			printf(",\n\t/* %-5d %5d %20s */\tNULL",
			       id - lowest_id, id, symbname(id));
			id++;
		}
		if (i > 0)
			printf(",");
		printf("\n\t/* %-5d %5d %20s */\t\"%s\"",
		       id - lowest_id, id, symbname(id), 
		       ntp_keywords[i].key);
		i++;
		id++;
	}

	printf("\n};\n\n");
}

	
int
compare_key_tok_id(
	QSORTP a1,
	QSORTP a2
	)
{
	const struct key_tok *p1 = (const void *)a1;
	const struct key_tok *p2 = (const void *)a2;

	if (p1->token == p2->token)
		return 0;

	if (p1->token < p2->token)
		return -1;
	else
		return 1;
}


int
compare_key_tok_text(
	QSORTP a1,
	QSORTP a2
	)
{
	const struct key_tok *p1 = (const void *)a1;
	const struct key_tok *p2 = (const void *)a2;

	return strcmp(p1->key, p2->key);
}


/*
 * populate_symb() - populate symb[] lookup array with symbolic token
 *		     names such that symb[T_Age] == "T_Age", etc.
 */
void
populate_symb(
	char *header_file
	)
{
	FILE *	yh;
	char	line[128];
	char	name[128];
	int	token;

	yh = fopen(header_file, "r");
	if (NULL == yh) {
		perror("unable to open yacc/bison header file");
		exit(4);
	}

	while (NULL != fgets(line, sizeof(line), yh))
		if (2 == sscanf(line, "#define %s %d", name, &token)
		    && 'T' == name[0] && '_' == name[1] && token >= 0
		    && token < COUNTOF(symb))

			symb[token] = estrdup(name);

	fclose(yh);
}


const char *
symbname(
	int token
	)
{
	char *name;

	if (token >= 0 && token < COUNTOF(symb) && symb[token] != NULL)
		return symb[token];

	LIB_GETBUF(name);
	snprintf(name, LIB_BUFLENGTH, "%d", token);
	return name;
}