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