1/*
2 * keyword-gen.c -- generate keyword scanner finite state machine and
3 *		    keyword_text array.
4 *
5 * This program is run to generate ntp_keyword.h
6 * After making a change here, two output files should be committed at
7 * the same time as keyword-gen.c:
8 *	ntp_keyword.h
9 *	keyword-gen-utd
10 *
11 * keyword-gen-utd is a sentinel used by Makefile.am to avoid compiling
12 * keyword_gen.c and generating ntp_keyword.h if the input keyword-gen.c
13 * has not changed.  This is not solely an optimization, it also breaks
14 * a dependency chain that otherwise would cause programs to be compiled
15 * when running "make dist" or "make distdir".  We want these to package
16 * the existing source without building anything but a tarball.  See
17 * [Bug 1470].
18 */
19#include <config.h>
20#include <stdio.h>
21#include <stdlib.h>
22#include <time.h>
23
24#include <ntp_stdlib.h>
25#include <ntp_config.h>
26#include <lib_strbuf.h>
27#include "ntp_scanner.h"
28#include "ntp_parser.h"
29
30
31/* Define a structure to hold a (keyword, token) pair */
32struct key_tok {
33	char *	key;		/* Keyword */
34	u_short	token;		/* Associated Token */
35	follby	followedby;	/* nonzero indicates the next token(s)
36				   forced to be string(s) */
37};
38
39struct key_tok ntp_keywords[] = {
40{ "...",		T_Ellipsis,		FOLLBY_TOKEN },
41{ "allpeers",		T_Allpeers,		FOLLBY_TOKEN },
42{ "automax",		T_Automax,		FOLLBY_TOKEN },
43{ "broadcast",		T_Broadcast,		FOLLBY_STRING },
44{ "broadcastclient",	T_Broadcastclient,	FOLLBY_TOKEN },
45{ "broadcastdelay",	T_Broadcastdelay,	FOLLBY_TOKEN },
46{ "checkhash",		T_Checkhash,		FOLLBY_TOKEN },
47{ "ctl",		T_Ctl,			FOLLBY_TOKEN },
48{ "disable",		T_Disable,		FOLLBY_TOKEN },
49{ "driftfile",		T_Driftfile,		FOLLBY_STRING },
50{ "dscp",		T_Dscp,			FOLLBY_TOKEN },
51{ "enable",		T_Enable,		FOLLBY_TOKEN },
52{ "end",		T_End,			FOLLBY_TOKEN },
53{ "filegen",		T_Filegen,		FOLLBY_TOKEN },
54{ "fudge",		T_Fudge,		FOLLBY_STRING },
55{ "ignorehash",		T_Ignorehash,		FOLLBY_TOKEN },
56{ "io",			T_Io,			FOLLBY_TOKEN },
57{ "includefile",	T_Includefile,		FOLLBY_STRING },
58{ "leapfile",		T_Leapfile,		FOLLBY_STRING },
59{ "leapsmearinterval",	T_Leapsmearinterval,	FOLLBY_TOKEN },
60{ "logconfig",		T_Logconfig,		FOLLBY_STRINGS_TO_EOC },
61{ "logfile",		T_Logfile,		FOLLBY_STRING },
62{ "manycastclient",	T_Manycastclient,	FOLLBY_STRING },
63{ "manycastserver",	T_Manycastserver,	FOLLBY_STRINGS_TO_EOC },
64{ "mem",		T_Mem,			FOLLBY_TOKEN },
65{ "multicastclient",	T_Multicastclient,	FOLLBY_STRINGS_TO_EOC },
66{ "peer",		T_Peer,			FOLLBY_STRING },
67{ "phone",		T_Phone,		FOLLBY_STRINGS_TO_EOC },
68{ "pidfile",		T_Pidfile,		FOLLBY_STRING },
69{ "pollskewlist",	T_PollSkewList,		FOLLBY_TOKEN },
70{ "pool",		T_Pool,			FOLLBY_STRING },
71{ "discard",		T_Discard,		FOLLBY_TOKEN },
72{ "reset",		T_Reset,		FOLLBY_TOKEN },
73{ "restrict",		T_Restrict,		FOLLBY_TOKEN },
74{ "rlimit",		T_Rlimit,		FOLLBY_TOKEN },
75{ "server",		T_Server,		FOLLBY_STRING },
76{ "serverresponse",	T_Serverresponse,	FOLLBY_TOKEN },
77{ "fuzz",		T_Fuzz,			FOLLBY_TOKEN },
78{ "poll",		T_Poll,			FOLLBY_TOKEN },
79{ "setvar",		T_Setvar,		FOLLBY_STRING },
80{ "statistics",		T_Statistics,		FOLLBY_TOKEN },
81{ "statsdir",		T_Statsdir,		FOLLBY_STRING },
82{ "sys",		T_Sys,			FOLLBY_TOKEN },
83{ "tick",		T_Tick,			FOLLBY_TOKEN },
84{ "timer",		T_Timer,		FOLLBY_TOKEN },
85{ "tinker",		T_Tinker,		FOLLBY_TOKEN },
86{ "tos",		T_Tos,			FOLLBY_TOKEN },
87{ "trap",		T_Trap,			FOLLBY_STRING },
88{ "unconfig",		T_Unconfig,		FOLLBY_STRING },
89{ "unpeer",		T_Unpeer,		FOLLBY_STRING },
90{ "xmtnonce",		T_Xmtnonce,		FOLLBY_TOKEN },
91/* authentication_command */
92{ "controlkey",		T_ControlKey,		FOLLBY_TOKEN },
93{ "crypto",		T_Crypto,		FOLLBY_TOKEN },
94{ "keys",		T_Keys,			FOLLBY_STRING },
95{ "keysdir",		T_Keysdir,		FOLLBY_STRING },
96{ "ntpsigndsocket",	T_NtpSignDsocket,	FOLLBY_STRING },
97{ "requestkey",		T_Requestkey,		FOLLBY_TOKEN },
98{ "revoke",		T_Revoke,		FOLLBY_TOKEN },
99{ "trustedkey",		T_Trustedkey,		FOLLBY_TOKEN },
100/* IPv4/IPv6 protocol override flag */
101{ "-4",			T_Ipv4_flag,		FOLLBY_TOKEN },
102{ "-6",			T_Ipv6_flag,		FOLLBY_TOKEN },
103/* option */
104{ "autokey",		T_Autokey,		FOLLBY_TOKEN },
105{ "burst",		T_Burst,		FOLLBY_TOKEN },
106{ "iburst",		T_Iburst,		FOLLBY_TOKEN },
107{ "key",		T_Key,			FOLLBY_TOKEN },
108{ "maxpoll",		T_Maxpoll,		FOLLBY_TOKEN },
109{ "mdnstries",		T_Mdnstries,		FOLLBY_TOKEN },
110{ "minpoll",		T_Minpoll,		FOLLBY_TOKEN },
111{ "mode",		T_Mode,			FOLLBY_TOKEN },
112{ "noselect",		T_Noselect,		FOLLBY_TOKEN },
113{ "preempt",		T_Preempt,		FOLLBY_TOKEN },
114{ "true",		T_True,			FOLLBY_TOKEN },
115{ "prefer",		T_Prefer,		FOLLBY_TOKEN },
116{ "ttl",		T_Ttl,			FOLLBY_TOKEN },
117{ "version",		T_Version,		FOLLBY_TOKEN },
118{ "xleave",		T_Xleave,		FOLLBY_TOKEN },
119/* crypto_command */
120{ "host",		T_Host,			FOLLBY_STRING },
121{ "ident",		T_Ident,		FOLLBY_STRING },
122{ "pw",			T_Pw,			FOLLBY_STRING },
123{ "randfile",		T_Randfile,		FOLLBY_STRING },
124{ "digest",		T_Digest,		FOLLBY_STRING },
125/*** MONITORING COMMANDS ***/
126/* stat */
127{ "clockstats",		T_Clockstats,		FOLLBY_TOKEN },
128{ "cryptostats",	T_Cryptostats,		FOLLBY_TOKEN },
129{ "loopstats",		T_Loopstats,		FOLLBY_TOKEN },
130{ "peerstats",		T_Peerstats,		FOLLBY_TOKEN },
131{ "rawstats",		T_Rawstats,		FOLLBY_TOKEN },
132{ "sysstats", 		T_Sysstats,		FOLLBY_TOKEN },
133{ "protostats",		T_Protostats,		FOLLBY_TOKEN },
134{ "timingstats",	T_Timingstats,		FOLLBY_TOKEN },
135/* filegen_option */
136{ "file",		T_File,			FOLLBY_STRING },
137{ "link",		T_Link,			FOLLBY_TOKEN },
138{ "nolink",		T_Nolink,		FOLLBY_TOKEN },
139{ "type",		T_Type,			FOLLBY_TOKEN },
140/* filegen_type */
141{ "age",		T_Age,			FOLLBY_TOKEN },
142{ "day",		T_Day,			FOLLBY_TOKEN },
143{ "month",		T_Month,		FOLLBY_TOKEN },
144{ "none",		T_None,			FOLLBY_TOKEN },
145{ "pid",		T_Pid,			FOLLBY_TOKEN },
146{ "week",		T_Week,			FOLLBY_TOKEN },
147{ "year",		T_Year,			FOLLBY_TOKEN },
148/*** ORPHAN MODE COMMANDS ***/
149/* tos_option */
150{ "minclock",		T_Minclock,		FOLLBY_TOKEN },
151{ "maxclock",		T_Maxclock,		FOLLBY_TOKEN },
152{ "minsane",		T_Minsane,		FOLLBY_TOKEN },
153{ "floor",		T_Floor,		FOLLBY_TOKEN },
154{ "ceiling",		T_Ceiling,		FOLLBY_TOKEN },
155{ "cohort",		T_Cohort,		FOLLBY_TOKEN },
156{ "mindist",		T_Mindist,		FOLLBY_TOKEN },
157{ "maxdist",		T_Maxdist,		FOLLBY_TOKEN },
158{ "bcpollbstep",	T_Bcpollbstep,		FOLLBY_TOKEN },
159{ "beacon",		T_Beacon,		FOLLBY_TOKEN },
160{ "orphan",		T_Orphan,		FOLLBY_TOKEN },
161{ "orphanwait",		T_Orphanwait,		FOLLBY_TOKEN },
162{ "nonvolatile",	T_Nonvolatile,		FOLLBY_TOKEN },
163{ "basedate",		T_Basedate,		FOLLBY_STRING },
164/* access_control_flag */
165{ "default",		T_Default,		FOLLBY_TOKEN },
166{ "source",		T_Source,		FOLLBY_TOKEN },
167{ "epeer",		T_Epeer,		FOLLBY_TOKEN },
168{ "noepeer",		T_Noepeer,		FOLLBY_TOKEN },
169{ "flake",		T_Flake,		FOLLBY_TOKEN },
170{ "ignore",		T_Ignore,		FOLLBY_TOKEN },
171{ "ippeerlimit",	T_Ippeerlimit,		FOLLBY_TOKEN },
172{ "limited",		T_Limited,		FOLLBY_TOKEN },
173{ "mssntp",		T_Mssntp,		FOLLBY_TOKEN },
174{ "kod",		T_Kod,			FOLLBY_TOKEN },
175{ "lowpriotrap",	T_Lowpriotrap,		FOLLBY_TOKEN },
176{ "mask",		T_Mask,			FOLLBY_TOKEN },
177{ "nomodify",		T_Nomodify,		FOLLBY_TOKEN },
178{ "nomrulist",		T_Nomrulist,		FOLLBY_TOKEN },
179{ "nopeer",		T_Nopeer,		FOLLBY_TOKEN },
180{ "noquery",		T_Noquery,		FOLLBY_TOKEN },
181{ "noserve",		T_Noserve,		FOLLBY_TOKEN },
182{ "notrap",		T_Notrap,		FOLLBY_TOKEN },
183{ "notrust",		T_Notrust,		FOLLBY_TOKEN },
184{ "ntpport",		T_Ntpport,		FOLLBY_TOKEN },
185/* discard_option */
186{ "average",		T_Average,		FOLLBY_TOKEN },
187{ "minimum",		T_Minimum,		FOLLBY_TOKEN },
188{ "monitor",		T_Monitor,		FOLLBY_TOKEN },
189/* mru_option */
190{ "incalloc",		T_Incalloc,		FOLLBY_TOKEN },
191{ "incmem",		T_Incmem,		FOLLBY_TOKEN },
192{ "initalloc",		T_Initalloc,		FOLLBY_TOKEN },
193{ "initmem",		T_Initmem,		FOLLBY_TOKEN },
194{ "mindepth",		T_Mindepth,		FOLLBY_TOKEN },
195{ "maxage",		T_Maxage,		FOLLBY_TOKEN },
196{ "maxdepth",		T_Maxdepth,		FOLLBY_TOKEN },
197{ "maxmem",		T_Maxmem,		FOLLBY_TOKEN },
198{ "mru",		T_Mru,			FOLLBY_TOKEN },
199/* fudge_factor */
200{ "abbrev",		T_Abbrev,		FOLLBY_STRING },
201{ "flag1",		T_Flag1,		FOLLBY_TOKEN },
202{ "flag2",		T_Flag2,		FOLLBY_TOKEN },
203{ "flag3",		T_Flag3,		FOLLBY_TOKEN },
204{ "flag4",		T_Flag4,		FOLLBY_TOKEN },
205{ "refid",		T_Refid,		FOLLBY_STRING },
206{ "stratum",		T_Stratum,		FOLLBY_TOKEN },
207{ "time1",		T_Time1,		FOLLBY_TOKEN },
208{ "time2",		T_Time2,		FOLLBY_TOKEN },
209{ "minjitter",		T_Minjitter,		FOLLBY_TOKEN },
210/* system_option */
211{ "auth",		T_Auth,			FOLLBY_TOKEN },
212{ "bclient",		T_Bclient,		FOLLBY_TOKEN },
213{ "calibrate",		T_Calibrate,		FOLLBY_TOKEN },
214{ "kernel",		T_Kernel,		FOLLBY_TOKEN },
215{ "mode7",		T_Mode7,		FOLLBY_TOKEN },
216{ "ntp",		T_Ntp,			FOLLBY_TOKEN },
217{ "peer_clear_digest_early",	T_PCEdigest,	FOLLBY_TOKEN },
218{ "stats",		T_Stats,		FOLLBY_TOKEN },
219{ "unpeer_crypto_early",	T_UEcrypto,	FOLLBY_TOKEN },
220{ "unpeer_crypto_nak_early",	T_UEcryptonak,	FOLLBY_TOKEN },
221{ "unpeer_digest_early",	T_UEdigest,	FOLLBY_TOKEN },
222/* rlimit_option */
223{ "memlock",		T_Memlock,		FOLLBY_TOKEN },
224{ "stacksize",		T_Stacksize,		FOLLBY_TOKEN },
225{ "filenum",		T_Filenum,		FOLLBY_TOKEN },
226/* tinker_option */
227{ "step",		T_Step,			FOLLBY_TOKEN },
228{ "stepback",		T_Stepback,		FOLLBY_TOKEN },
229{ "stepfwd",		T_Stepfwd,		FOLLBY_TOKEN },
230{ "panic",		T_Panic,		FOLLBY_TOKEN },
231{ "dispersion",		T_Dispersion,		FOLLBY_TOKEN },
232{ "stepout",		T_Stepout,		FOLLBY_TOKEN },
233{ "allan",		T_Allan,		FOLLBY_TOKEN },
234{ "huffpuff",		T_Huffpuff,		FOLLBY_TOKEN },
235{ "freq",		T_Freq,			FOLLBY_TOKEN },
236/* miscellaneous_command */
237{ "port",		T_Port,			FOLLBY_TOKEN },
238{ "interface",		T_Interface,		FOLLBY_TOKEN },
239{ "saveconfigdir",	T_Saveconfigdir,	FOLLBY_STRING },
240/* interface_command (ignore and interface already defined) */
241{ "nic",		T_Nic,			FOLLBY_TOKEN },
242{ "all",		T_All,			FOLLBY_TOKEN },
243{ "ipv4",		T_Ipv4,			FOLLBY_TOKEN },
244{ "ipv6",		T_Ipv6,			FOLLBY_TOKEN },
245{ "wildcard",		T_Wildcard,		FOLLBY_TOKEN },
246{ "listen",		T_Listen,		FOLLBY_TOKEN },
247{ "drop",		T_Drop,			FOLLBY_TOKEN },
248/* simulator commands */
249{ "simulate",		T_Simulate,		FOLLBY_TOKEN },
250{ "simulation_duration",T_Sim_Duration,		FOLLBY_TOKEN },
251{ "beep_delay",		T_Beep_Delay,		FOLLBY_TOKEN },
252{ "duration",		T_Duration,		FOLLBY_TOKEN },
253{ "server_offset",	T_Server_Offset,	FOLLBY_TOKEN },
254{ "freq_offset",	T_Freq_Offset,		FOLLBY_TOKEN },
255{ "wander",		T_Wander,		FOLLBY_TOKEN },
256{ "jitter",		T_Jitter,		FOLLBY_TOKEN },
257{ "prop_delay",		T_Prop_Delay,		FOLLBY_TOKEN },
258{ "proc_delay",		T_Proc_Delay,		FOLLBY_TOKEN },
259};
260
261typedef struct big_scan_state_tag {
262	char	ch;		/* Character this state matches on */
263	char	followedby;	/* Forces next token(s) to T_String */
264	u_short	finishes_token;	/* nonzero ID if last keyword char */
265	u_short	match_next_s;	/* next state to check matching ch */
266	u_short	other_next_s;	/* next state to check if not ch */
267} big_scan_state;
268
269/*
270 * Note: to increase MAXSTATES beyond 2048, be aware it is currently
271 * crammed into 11 bits in scan_state form.  Raising to 4096 would be
272 * relatively easy by storing the followedby value in a separate
273 * array with one entry per token, and shrinking the char value to
274 * 7 bits to free a bit for accepting/non-accepting.  More than 4096
275 * states will require expanding scan_state beyond 32 bits each.
276 */
277#define MAXSTATES	2048
278#define MAX_TOK_LEN	63
279
280const char *	current_keyword;/* for error reporting */
281big_scan_state	sst[MAXSTATES];	/* scanner FSM state entries */
282u_short		sst_highwater;	/* next entry index to consider */
283char *		symb[1024];	/* map token ID to symbolic name */
284
285/* for libntp */
286const char *	progname = "keyword-gen";
287
288int		main			(int, char **);
289static void	generate_preamble	(void);
290static void	generate_fsm		(void);
291static void	generate_token_text	(void);
292static u_short	create_keyword_scanner	(void);
293static u_short	create_scan_states	(char *, u_short, follby, u_short);
294int		compare_key_tok_id	(const void *, const void *);
295int		compare_key_tok_text	(const void *, const void *);
296void		populate_symb		(char *);
297const char *	symbname		(u_short);
298
299
300int main(int argc, char **argv)
301{
302	if (argc < 2) {
303		fprintf(stderr, "Usage:\n%s t_header.h\n", argv[0]);
304		exit(1);
305	}
306	debug = 1;
307
308	populate_symb(argv[1]);
309
310	generate_preamble();
311	generate_token_text();
312	generate_fsm();
313
314	return 0;
315}
316
317
318static void
319generate_preamble(void)
320{
321	time_t now;
322	char timestamp[128];
323	char preamble[] =
324"/*\n"
325" * ntp_keyword.h\n"
326" * \n"
327" * NOTE: edit this file with caution, it is generated by keyword-gen.c\n"
328" *\t Generated %s UTC	  diff_ignore_line\n"
329" *\n"
330" */\n"
331"#include \"ntp_scanner.h\"\n"
332"#include \"ntp_parser.h\"\n"
333"\n";
334
335	time(&now);
336	if (!strftime(timestamp, sizeof(timestamp),
337		      "%Y-%m-%d %H:%M:%S", gmtime(&now)))
338		timestamp[0] = '\0';
339
340	printf(preamble, timestamp);
341}
342
343
344static void
345generate_fsm(void)
346{
347	char rprefix[MAX_TOK_LEN + 1];
348	char prefix[MAX_TOK_LEN + 1];
349	char token_id_comment[16 + MAX_TOK_LEN + 1];
350	size_t prefix_len;
351	char *p;
352	char *r;
353	u_short initial_state;
354	u_short this_state;
355	u_short state;
356	u_short i;
357	u_short token;
358
359	/*
360	 * Sort ntp_keywords in alphabetical keyword order.  This is
361	 * not necessary, but minimizes nonfunctional changes in the
362	 * generated finite state machine when keywords are modified.
363	 */
364	qsort(ntp_keywords, COUNTOF(ntp_keywords),
365	      sizeof(ntp_keywords[0]), compare_key_tok_text);
366
367	/*
368	 * To save space, reserve the state array entry matching each
369	 * token number for its terminal state, so the token identifier
370	 * does not need to be stored in each state, but can be
371	 * recovered trivially.  To mark the entry reserved,
372	 * finishes_token is nonzero.
373	 */
374
375	for (i = 0; i < COUNTOF(ntp_keywords); i++) {
376		token = ntp_keywords[i].token;
377		if (1 > token || token >= COUNTOF(sst)) {
378			fprintf(stderr,
379				"keyword-gen sst[%u] too small "
380				"for keyword '%s' id %d\n",
381				(int)COUNTOF(sst),
382				ntp_keywords[i].key,
383				token);
384			exit(4);
385		}
386		sst[token].finishes_token = token;
387	}
388
389	initial_state = create_keyword_scanner();
390
391	fprintf(stderr,
392		"%d keywords consumed %d states of %d max.\n",
393		(int)COUNTOF(ntp_keywords),
394		sst_highwater - 1,
395		(int)COUNTOF(sst) - 1);
396
397	printf("#define SCANNER_INIT_S %d\n\n", initial_state);
398
399	printf("const scan_state sst[%d] = {\n"
400	       "/*SS_T( ch,\tf-by, match, other ),\t\t\t\t */\n"
401	       "  0,\t\t\t\t      /* %5d %-17s */\n",
402	       sst_highwater,
403	       0, "");
404
405	for (i = 1; i < sst_highwater; i++) {
406
407		/* verify fields will fit */
408		if (sst[i].followedby & ~0x3) {
409			fprintf(stderr,
410				"keyword-gen internal error "
411				"sst[%d].followedby %d too big\n",
412				i, sst[i].followedby);
413			exit(7);
414		}
415
416		if (sst_highwater <= sst[i].match_next_s
417		    || sst[i].match_next_s & ~0x7ff) {
418			fprintf(stderr,
419				"keyword-gen internal error "
420				"sst[%d].match_next_s %d too big\n",
421				i, sst[i].match_next_s);
422			exit(8);
423		}
424
425		if (sst_highwater <= sst[i].other_next_s
426		    || sst[i].other_next_s & ~0x7ff) {
427			fprintf(stderr,
428				"keyword-gen internal error "
429				"sst[%d].other_next_s %d too big\n",
430				i, sst[i].other_next_s);
431			exit(9);
432		}
433
434		if (sst[i].finishes_token) {
435			snprintf(token_id_comment,
436				 sizeof(token_id_comment), "%5d %-17s",
437				 i, symbname(sst[i].finishes_token));
438			if (i != sst[i].finishes_token) {
439				fprintf(stderr,
440					"keyword-gen internal error "
441					"entry %d finishes token %d\n",
442					i, sst[i].finishes_token);
443				exit(5);
444			}
445		} else {
446		/*
447		 * Determine the keyword prefix that leads to this
448		 * state.  This is expensive but keyword-gen is run
449		 * only when it changes.  Distributing keyword-gen-utd
450		 * achieves that, which is why it must be committed
451		 * at the same time as keyword-gen.c and ntp_keyword.h.
452		 *
453		 * Scan the state array iteratively looking for a state
454		 * which leads to the current one, collecting matching
455		 * characters along the way.  There is only one such
456		 * path back to the starting state given the way our
457		 * scanner state machine is built and the practice of
458		 * using the spelling of the keyword as its T_* token
459		 * identifier, which results in never having two
460		 * spellings result in the same T_* value.
461		 */
462			prefix_len = 0;
463			this_state = i;
464			do {
465				for (state = 1; state < sst_highwater; state++)
466					if (sst[state].other_next_s == this_state) {
467						this_state = state;
468						break;
469					} else if (sst[state].match_next_s == this_state) {
470						this_state = state;
471						rprefix[prefix_len] = sst[state].ch;
472						prefix_len++;
473						break;
474					}
475			} while (this_state != initial_state);
476
477			if (prefix_len) {
478				/* reverse rprefix into prefix */
479				p = prefix + prefix_len;
480				r = rprefix;
481				while (r < rprefix + prefix_len)
482					*--p = *r++;
483			}
484			prefix[prefix_len] = '\0';
485
486			snprintf(token_id_comment,
487				 sizeof(token_id_comment), "%5d %-17s",
488				 i, (initial_state == i)
489					? "[initial state]"
490					: prefix);
491		}
492
493		printf("  S_ST( '%c',\t%d,    %5u, %5u )%s /* %s */\n",
494		       sst[i].ch,
495		       sst[i].followedby,
496		       sst[i].match_next_s,
497		       sst[i].other_next_s,
498		       (i + 1 < sst_highwater)
499			   ? ","
500			   : " ",
501		       token_id_comment);
502	}
503
504	printf("};\n\n");
505}
506
507
508/* Define a function to create the states of the scanner. This function
509 * is used by the create_keyword_scanner function below.
510 *
511 * This function takes a suffix of a keyword, the token to be returned on
512 * recognizing the complete keyword, and any pre-existing state that exists
513 * for some other keyword that has the same prefix as the current one.
514 */
515static u_short
516create_scan_states(
517	char *	text,
518	u_short	token,
519	follby	followedby,
520	u_short	prev_state
521	)
522{
523	u_short my_state;
524	u_short return_state;
525	u_short prev_char_s;
526	u_short curr_char_s;
527
528	return_state = prev_state;
529	curr_char_s = prev_state;
530	prev_char_s = 0;
531
532	/* Find the correct position to insert the state.
533	 * All states should be in alphabetical order
534	 */
535	while (curr_char_s && (text[0] < sst[curr_char_s].ch)) {
536		prev_char_s = curr_char_s;
537		curr_char_s = sst[curr_char_s].other_next_s;
538	}
539
540	/*
541	 * Check if a previously seen keyword has the same prefix as
542	 * the current keyword.  If so, simply use the state for that
543	 * keyword as my_state, otherwise, allocate a new state.
544	 */
545	if (curr_char_s && (text[0] == sst[curr_char_s].ch)) {
546		my_state = curr_char_s;
547		if ('\0' == text[1]) {
548			fprintf(stderr,
549				"Duplicate entries for keyword '%s' in"
550				" keyword_gen.c ntp_keywords[].\n",
551				current_keyword);
552			exit(2);
553		}
554	} else {
555		do
556			my_state = sst_highwater++;
557		while (my_state < COUNTOF(sst)
558		       && sst[my_state].finishes_token);
559		if (my_state >= COUNTOF(sst)) {
560			fprintf(stderr,
561				"fatal, keyword scanner state array "
562				"sst[%d] is too small, modify\n"
563				"keyword-gen.c to increase.\n",
564				(int)COUNTOF(sst));
565			exit(3);
566		}
567		/* Store the next character of the keyword */
568		sst[my_state].ch = text[0];
569		sst[my_state].other_next_s = curr_char_s;
570		sst[my_state].followedby = FOLLBY_NON_ACCEPTING;
571
572		if (prev_char_s)
573			sst[prev_char_s].other_next_s = my_state;
574		else
575			return_state = my_state;
576	}
577
578	/* Check if the next character is '\0'.
579	 * If yes, we are done with the recognition and this is an accepting
580	 * state.
581	 * If not, we need to continue scanning
582	 */
583	if ('\0' == text[1]) {
584		sst[my_state].finishes_token = (u_short)token;
585		sst[my_state].followedby = (char)followedby;
586
587		if (sst[token].finishes_token != (u_short)token) {
588			fprintf(stderr,
589				"fatal, sst[%d] not reserved for %s.\n",
590				token, symbname(token));
591			exit(6);
592		}
593		/* relocate so token id is sst[] index */
594		if (my_state != token) {
595			sst[token] = sst[my_state];
596			ZERO(sst[my_state]);
597			do
598				sst_highwater--;
599			while (sst[sst_highwater].finishes_token);
600			my_state = token;
601			if (prev_char_s)
602				sst[prev_char_s].other_next_s = my_state;
603			else
604				return_state = my_state;
605		}
606	} else
607		sst[my_state].match_next_s =
608		    create_scan_states(
609			&text[1],
610			token,
611			followedby,
612			sst[my_state].match_next_s);
613
614	return return_state;
615}
616
617
618/* Define a function that takes a list of (keyword, token) values and
619 * creates a keywords scanner out of it.
620 */
621
622static u_short
623create_keyword_scanner(void)
624{
625	u_short scanner;
626	u_short i;
627
628	sst_highwater = 1;	/* index 0 invalid, unused */
629	scanner = 0;
630
631	for (i = 0; i < COUNTOF(ntp_keywords); i++) {
632		current_keyword = ntp_keywords[i].key;
633		scanner =
634		    create_scan_states(
635			ntp_keywords[i].key,
636			ntp_keywords[i].token,
637			ntp_keywords[i].followedby,
638			scanner);
639	}
640
641	return scanner;
642}
643
644
645static void
646generate_token_text(void)
647{
648	u_short lowest_id;
649	u_short highest_id;
650	u_short id_count;
651	u_short id;
652	u_short i;
653
654	/* sort ntp_keywords in token ID order */
655	qsort(ntp_keywords, COUNTOF(ntp_keywords),
656	      sizeof(ntp_keywords[0]), compare_key_tok_id);
657
658	lowest_id = ntp_keywords[0].token;
659	highest_id = ntp_keywords[COUNTOF(ntp_keywords) - 1].token;
660	id_count = highest_id - lowest_id + 1;
661
662	printf("#define LOWEST_KEYWORD_ID %d\n\n", lowest_id);
663
664	printf("const char * const keyword_text[%d] = {", id_count);
665
666	id = lowest_id;
667	i = 0;
668	while (i < COUNTOF(ntp_keywords)) {
669		while (id < ntp_keywords[i].token) {
670			printf(",\n\t/* %-5d %5d %20s */\tNULL",
671			       id - lowest_id, id, symbname(id));
672			id++;
673		}
674		if (i > 0)
675			printf(",");
676		printf("\n\t/* %-5d %5d %20s */\t\"%s\"",
677		       id - lowest_id, id, symbname(id),
678		       ntp_keywords[i].key);
679		i++;
680		id++;
681	}
682
683	printf("\n};\n\n");
684}
685
686
687int
688compare_key_tok_id(
689	const void *a1,
690	const void *a2
691	)
692{
693	const struct key_tok *p1 = a1;
694	const struct key_tok *p2 = a2;
695
696	if (p1->token == p2->token)
697		return 0;
698
699	if (p1->token < p2->token)
700		return -1;
701	else
702		return 1;
703}
704
705
706int
707compare_key_tok_text(
708	const void *a1,
709	const void *a2
710	)
711{
712	const struct key_tok *p1 = a1;
713	const struct key_tok *p2 = a2;
714
715	return strcmp(p1->key, p2->key);
716}
717
718
719/*
720 * populate_symb() - populate symb[] lookup array with symbolic token
721 *		     names such that symb[T_Age] == "T_Age", etc.
722 */
723void
724populate_symb(
725	char *header_file
726	)
727{
728	FILE *	yh;
729	char	line[2 * MAX_TOK_LEN];
730	char	name[2 * MAX_TOK_LEN];
731	int	token;
732
733	yh = fopen(header_file, "r");
734	if (NULL == yh) {
735		perror("unable to open yacc/bison header file");
736		exit(4);
737	}
738
739	while (NULL != fgets(line, sizeof(line), yh))
740		if (2 == sscanf(line, "#define %s %d", name, &token)
741		    && 'T' == name[0] && '_' == name[1] && token >= 0
742		    && token < COUNTOF(symb)) {
743
744			symb[token] = estrdup(name);
745			if (strlen(name) > MAX_TOK_LEN) {
746				fprintf(stderr,
747					"MAX_TOK_LEN %d too small for '%s'\n"
748					"Edit keyword-gen.c to raise.\n",
749					MAX_TOK_LEN, name);
750				exit(10);
751			}
752		}
753	fclose(yh);
754}
755
756
757const char *
758symbname(
759	u_short token
760	)
761{
762	char *name;
763
764	if (token < COUNTOF(symb) && symb[token] != NULL) {
765		name = symb[token];
766	} else {
767		LIB_GETBUF(name);
768		snprintf(name, LIB_BUFLENGTH, "%d", token);
769	}
770
771	return name;
772}
773