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 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 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 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 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 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 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 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 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 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 * 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