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