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