1258945Sroberto/* 2258945Sroberto * keyword-gen.c -- generate keyword scanner finite state machine and 3258945Sroberto * keyword_text array. 4280849Scy * 5280849Scy * This program is run to generate ntp_keyword.h 6280849Scy * After making a change here, two output files should be committed at 7280849Scy * the same time as keyword-gen.c: 8280849Scy * ntp_keyword.h 9280849Scy * keyword-gen-utd 10280849Scy * 11280849Scy * keyword-gen-utd is a sentinel used by Makefile.am to avoid compiling 12280849Scy * keyword_gen.c and generating ntp_keyword.h if the input keyword-gen.c 13280849Scy * has not changed. This is not solely an optimization, it also breaks 14280849Scy * a dependency chain that otherwise would cause programs to be compiled 15280849Scy * when running "make dist" or "make distdir". We want these to package 16280849Scy * the existing source without building anything but a tarball. See 17280849Scy * [Bug 1470]. 18258945Sroberto */ 19258945Sroberto#include <config.h> 20258945Sroberto#include <stdio.h> 21258945Sroberto#include <stdlib.h> 22258945Sroberto#include <time.h> 23258945Sroberto 24258945Sroberto#include <ntp_stdlib.h> 25258945Sroberto#include <ntp_config.h> 26258945Sroberto#include <lib_strbuf.h> 27258945Sroberto#include "ntp_scanner.h" 28258945Sroberto#include "ntp_parser.h" 29258945Sroberto 30258945Sroberto 31258945Sroberto/* Define a structure to hold a (keyword, token) pair */ 32258945Srobertostruct key_tok { 33258945Sroberto char * key; /* Keyword */ 34280849Scy u_short token; /* Associated Token */ 35258945Sroberto follby followedby; /* nonzero indicates the next token(s) 36258945Sroberto forced to be string(s) */ 37258945Sroberto}; 38258945Sroberto 39258945Srobertostruct key_tok ntp_keywords[] = { 40258945Sroberto{ "...", T_Ellipsis, FOLLBY_TOKEN }, 41280849Scy{ "allpeers", T_Allpeers, FOLLBY_TOKEN }, 42258945Sroberto{ "automax", T_Automax, FOLLBY_TOKEN }, 43258945Sroberto{ "broadcast", T_Broadcast, FOLLBY_STRING }, 44258945Sroberto{ "broadcastclient", T_Broadcastclient, FOLLBY_TOKEN }, 45258945Sroberto{ "broadcastdelay", T_Broadcastdelay, FOLLBY_TOKEN }, 46358659Scy{ "checkhash", T_Checkhash, FOLLBY_TOKEN }, 47280849Scy{ "ctl", T_Ctl, FOLLBY_TOKEN }, 48258945Sroberto{ "disable", T_Disable, FOLLBY_TOKEN }, 49258945Sroberto{ "driftfile", T_Driftfile, FOLLBY_STRING }, 50285169Scy{ "dscp", T_Dscp, FOLLBY_TOKEN }, 51258945Sroberto{ "enable", T_Enable, FOLLBY_TOKEN }, 52258945Sroberto{ "end", T_End, FOLLBY_TOKEN }, 53258945Sroberto{ "filegen", T_Filegen, FOLLBY_TOKEN }, 54258945Sroberto{ "fudge", T_Fudge, FOLLBY_STRING }, 55358659Scy{ "ignorehash", T_Ignorehash, FOLLBY_TOKEN }, 56280849Scy{ "io", T_Io, FOLLBY_TOKEN }, 57258945Sroberto{ "includefile", T_Includefile, FOLLBY_STRING }, 58258945Sroberto{ "leapfile", T_Leapfile, FOLLBY_STRING }, 59285169Scy{ "leapsmearinterval", T_Leapsmearinterval, FOLLBY_TOKEN }, 60258945Sroberto{ "logconfig", T_Logconfig, FOLLBY_STRINGS_TO_EOC }, 61258945Sroberto{ "logfile", T_Logfile, FOLLBY_STRING }, 62258945Sroberto{ "manycastclient", T_Manycastclient, FOLLBY_STRING }, 63258945Sroberto{ "manycastserver", T_Manycastserver, FOLLBY_STRINGS_TO_EOC }, 64280849Scy{ "mem", T_Mem, FOLLBY_TOKEN }, 65258945Sroberto{ "multicastclient", T_Multicastclient, FOLLBY_STRINGS_TO_EOC }, 66258945Sroberto{ "peer", T_Peer, FOLLBY_STRING }, 67258945Sroberto{ "phone", T_Phone, FOLLBY_STRINGS_TO_EOC }, 68258945Sroberto{ "pidfile", T_Pidfile, FOLLBY_STRING }, 69358659Scy{ "pollskewlist", T_PollSkewList, FOLLBY_TOKEN }, 70258945Sroberto{ "pool", T_Pool, FOLLBY_STRING }, 71258945Sroberto{ "discard", T_Discard, FOLLBY_TOKEN }, 72280849Scy{ "reset", T_Reset, FOLLBY_TOKEN }, 73258945Sroberto{ "restrict", T_Restrict, FOLLBY_TOKEN }, 74280849Scy{ "rlimit", T_Rlimit, FOLLBY_TOKEN }, 75258945Sroberto{ "server", T_Server, FOLLBY_STRING }, 76358659Scy{ "serverresponse", T_Serverresponse, FOLLBY_TOKEN }, 77358659Scy{ "fuzz", T_Fuzz, FOLLBY_TOKEN }, 78358659Scy{ "poll", T_Poll, FOLLBY_TOKEN }, 79258945Sroberto{ "setvar", T_Setvar, FOLLBY_STRING }, 80258945Sroberto{ "statistics", T_Statistics, FOLLBY_TOKEN }, 81258945Sroberto{ "statsdir", T_Statsdir, FOLLBY_STRING }, 82280849Scy{ "sys", T_Sys, FOLLBY_TOKEN }, 83258945Sroberto{ "tick", T_Tick, FOLLBY_TOKEN }, 84280849Scy{ "timer", T_Timer, FOLLBY_TOKEN }, 85258945Sroberto{ "tinker", T_Tinker, FOLLBY_TOKEN }, 86258945Sroberto{ "tos", T_Tos, FOLLBY_TOKEN }, 87258945Sroberto{ "trap", T_Trap, FOLLBY_STRING }, 88258945Sroberto{ "unconfig", T_Unconfig, FOLLBY_STRING }, 89258945Sroberto{ "unpeer", T_Unpeer, FOLLBY_STRING }, 90358659Scy{ "xmtnonce", T_Xmtnonce, FOLLBY_TOKEN }, 91258945Sroberto/* authentication_command */ 92258945Sroberto{ "controlkey", T_ControlKey, FOLLBY_TOKEN }, 93258945Sroberto{ "crypto", T_Crypto, FOLLBY_TOKEN }, 94258945Sroberto{ "keys", T_Keys, FOLLBY_STRING }, 95258945Sroberto{ "keysdir", T_Keysdir, FOLLBY_STRING }, 96258945Sroberto{ "ntpsigndsocket", T_NtpSignDsocket, FOLLBY_STRING }, 97258945Sroberto{ "requestkey", T_Requestkey, FOLLBY_TOKEN }, 98258945Sroberto{ "revoke", T_Revoke, FOLLBY_TOKEN }, 99258945Sroberto{ "trustedkey", T_Trustedkey, FOLLBY_TOKEN }, 100258945Sroberto/* IPv4/IPv6 protocol override flag */ 101258945Sroberto{ "-4", T_Ipv4_flag, FOLLBY_TOKEN }, 102258945Sroberto{ "-6", T_Ipv6_flag, FOLLBY_TOKEN }, 103258945Sroberto/* option */ 104258945Sroberto{ "autokey", T_Autokey, FOLLBY_TOKEN }, 105258945Sroberto{ "burst", T_Burst, FOLLBY_TOKEN }, 106258945Sroberto{ "iburst", T_Iburst, FOLLBY_TOKEN }, 107258945Sroberto{ "key", T_Key, FOLLBY_TOKEN }, 108258945Sroberto{ "maxpoll", T_Maxpoll, FOLLBY_TOKEN }, 109280849Scy{ "mdnstries", T_Mdnstries, FOLLBY_TOKEN }, 110258945Sroberto{ "minpoll", T_Minpoll, FOLLBY_TOKEN }, 111258945Sroberto{ "mode", T_Mode, FOLLBY_TOKEN }, 112258945Sroberto{ "noselect", T_Noselect, FOLLBY_TOKEN }, 113258945Sroberto{ "preempt", T_Preempt, FOLLBY_TOKEN }, 114258945Sroberto{ "true", T_True, FOLLBY_TOKEN }, 115258945Sroberto{ "prefer", T_Prefer, FOLLBY_TOKEN }, 116258945Sroberto{ "ttl", T_Ttl, FOLLBY_TOKEN }, 117258945Sroberto{ "version", T_Version, FOLLBY_TOKEN }, 118258945Sroberto{ "xleave", T_Xleave, FOLLBY_TOKEN }, 119258945Sroberto/* crypto_command */ 120258945Sroberto{ "host", T_Host, FOLLBY_STRING }, 121258945Sroberto{ "ident", T_Ident, FOLLBY_STRING }, 122258945Sroberto{ "pw", T_Pw, FOLLBY_STRING }, 123258945Sroberto{ "randfile", T_Randfile, FOLLBY_STRING }, 124258945Sroberto{ "digest", T_Digest, FOLLBY_STRING }, 125258945Sroberto/*** MONITORING COMMANDS ***/ 126258945Sroberto/* stat */ 127258945Sroberto{ "clockstats", T_Clockstats, FOLLBY_TOKEN }, 128258945Sroberto{ "cryptostats", T_Cryptostats, FOLLBY_TOKEN }, 129258945Sroberto{ "loopstats", T_Loopstats, FOLLBY_TOKEN }, 130258945Sroberto{ "peerstats", T_Peerstats, FOLLBY_TOKEN }, 131258945Sroberto{ "rawstats", T_Rawstats, FOLLBY_TOKEN }, 132258945Sroberto{ "sysstats", T_Sysstats, FOLLBY_TOKEN }, 133258945Sroberto{ "protostats", T_Protostats, FOLLBY_TOKEN }, 134258945Sroberto{ "timingstats", T_Timingstats, FOLLBY_TOKEN }, 135258945Sroberto/* filegen_option */ 136258945Sroberto{ "file", T_File, FOLLBY_STRING }, 137258945Sroberto{ "link", T_Link, FOLLBY_TOKEN }, 138258945Sroberto{ "nolink", T_Nolink, FOLLBY_TOKEN }, 139258945Sroberto{ "type", T_Type, FOLLBY_TOKEN }, 140258945Sroberto/* filegen_type */ 141258945Sroberto{ "age", T_Age, FOLLBY_TOKEN }, 142258945Sroberto{ "day", T_Day, FOLLBY_TOKEN }, 143258945Sroberto{ "month", T_Month, FOLLBY_TOKEN }, 144258945Sroberto{ "none", T_None, FOLLBY_TOKEN }, 145258945Sroberto{ "pid", T_Pid, FOLLBY_TOKEN }, 146258945Sroberto{ "week", T_Week, FOLLBY_TOKEN }, 147258945Sroberto{ "year", T_Year, FOLLBY_TOKEN }, 148258945Sroberto/*** ORPHAN MODE COMMANDS ***/ 149258945Sroberto/* tos_option */ 150258945Sroberto{ "minclock", T_Minclock, FOLLBY_TOKEN }, 151258945Sroberto{ "maxclock", T_Maxclock, FOLLBY_TOKEN }, 152258945Sroberto{ "minsane", T_Minsane, FOLLBY_TOKEN }, 153258945Sroberto{ "floor", T_Floor, FOLLBY_TOKEN }, 154258945Sroberto{ "ceiling", T_Ceiling, FOLLBY_TOKEN }, 155258945Sroberto{ "cohort", T_Cohort, FOLLBY_TOKEN }, 156258945Sroberto{ "mindist", T_Mindist, FOLLBY_TOKEN }, 157258945Sroberto{ "maxdist", T_Maxdist, FOLLBY_TOKEN }, 158309007Sdelphij{ "bcpollbstep", T_Bcpollbstep, FOLLBY_TOKEN }, 159258945Sroberto{ "beacon", T_Beacon, FOLLBY_TOKEN }, 160258945Sroberto{ "orphan", T_Orphan, FOLLBY_TOKEN }, 161280849Scy{ "orphanwait", T_Orphanwait, FOLLBY_TOKEN }, 162280849Scy{ "nonvolatile", T_Nonvolatile, FOLLBY_TOKEN }, 163330106Sdelphij{ "basedate", T_Basedate, FOLLBY_STRING }, 164258945Sroberto/* access_control_flag */ 165258945Sroberto{ "default", T_Default, FOLLBY_TOKEN }, 166280849Scy{ "source", T_Source, FOLLBY_TOKEN }, 167330106Sdelphij{ "epeer", T_Epeer, FOLLBY_TOKEN }, 168330106Sdelphij{ "noepeer", T_Noepeer, FOLLBY_TOKEN }, 169258945Sroberto{ "flake", T_Flake, FOLLBY_TOKEN }, 170258945Sroberto{ "ignore", T_Ignore, FOLLBY_TOKEN }, 171330106Sdelphij{ "ippeerlimit", T_Ippeerlimit, FOLLBY_TOKEN }, 172258945Sroberto{ "limited", T_Limited, FOLLBY_TOKEN }, 173258945Sroberto{ "mssntp", T_Mssntp, FOLLBY_TOKEN }, 174258945Sroberto{ "kod", T_Kod, FOLLBY_TOKEN }, 175258945Sroberto{ "lowpriotrap", T_Lowpriotrap, FOLLBY_TOKEN }, 176258945Sroberto{ "mask", T_Mask, FOLLBY_TOKEN }, 177258945Sroberto{ "nomodify", T_Nomodify, FOLLBY_TOKEN }, 178280849Scy{ "nomrulist", T_Nomrulist, FOLLBY_TOKEN }, 179258945Sroberto{ "nopeer", T_Nopeer, FOLLBY_TOKEN }, 180258945Sroberto{ "noquery", T_Noquery, FOLLBY_TOKEN }, 181258945Sroberto{ "noserve", T_Noserve, FOLLBY_TOKEN }, 182258945Sroberto{ "notrap", T_Notrap, FOLLBY_TOKEN }, 183258945Sroberto{ "notrust", T_Notrust, FOLLBY_TOKEN }, 184258945Sroberto{ "ntpport", T_Ntpport, FOLLBY_TOKEN }, 185258945Sroberto/* discard_option */ 186258945Sroberto{ "average", T_Average, FOLLBY_TOKEN }, 187258945Sroberto{ "minimum", T_Minimum, FOLLBY_TOKEN }, 188258945Sroberto{ "monitor", T_Monitor, FOLLBY_TOKEN }, 189280849Scy/* mru_option */ 190280849Scy{ "incalloc", T_Incalloc, FOLLBY_TOKEN }, 191280849Scy{ "incmem", T_Incmem, FOLLBY_TOKEN }, 192280849Scy{ "initalloc", T_Initalloc, FOLLBY_TOKEN }, 193280849Scy{ "initmem", T_Initmem, FOLLBY_TOKEN }, 194280849Scy{ "mindepth", T_Mindepth, FOLLBY_TOKEN }, 195280849Scy{ "maxage", T_Maxage, FOLLBY_TOKEN }, 196280849Scy{ "maxdepth", T_Maxdepth, FOLLBY_TOKEN }, 197280849Scy{ "maxmem", T_Maxmem, FOLLBY_TOKEN }, 198280849Scy{ "mru", T_Mru, FOLLBY_TOKEN }, 199258945Sroberto/* fudge_factor */ 200280849Scy{ "abbrev", T_Abbrev, FOLLBY_STRING }, 201258945Sroberto{ "flag1", T_Flag1, FOLLBY_TOKEN }, 202258945Sroberto{ "flag2", T_Flag2, FOLLBY_TOKEN }, 203258945Sroberto{ "flag3", T_Flag3, FOLLBY_TOKEN }, 204258945Sroberto{ "flag4", T_Flag4, FOLLBY_TOKEN }, 205258945Sroberto{ "refid", T_Refid, FOLLBY_STRING }, 206258945Sroberto{ "stratum", T_Stratum, FOLLBY_TOKEN }, 207258945Sroberto{ "time1", T_Time1, FOLLBY_TOKEN }, 208258945Sroberto{ "time2", T_Time2, FOLLBY_TOKEN }, 209358659Scy{ "minjitter", T_Minjitter, FOLLBY_TOKEN }, 210258945Sroberto/* system_option */ 211258945Sroberto{ "auth", T_Auth, FOLLBY_TOKEN }, 212258945Sroberto{ "bclient", T_Bclient, FOLLBY_TOKEN }, 213258945Sroberto{ "calibrate", T_Calibrate, FOLLBY_TOKEN }, 214258945Sroberto{ "kernel", T_Kernel, FOLLBY_TOKEN }, 215301247Sdelphij{ "mode7", T_Mode7, FOLLBY_TOKEN }, 216258945Sroberto{ "ntp", T_Ntp, FOLLBY_TOKEN }, 217301247Sdelphij{ "peer_clear_digest_early", T_PCEdigest, FOLLBY_TOKEN }, 218258945Sroberto{ "stats", T_Stats, FOLLBY_TOKEN }, 219294554Sdelphij{ "unpeer_crypto_early", T_UEcrypto, FOLLBY_TOKEN }, 220294554Sdelphij{ "unpeer_crypto_nak_early", T_UEcryptonak, FOLLBY_TOKEN }, 221294554Sdelphij{ "unpeer_digest_early", T_UEdigest, FOLLBY_TOKEN }, 222280849Scy/* rlimit_option */ 223280849Scy{ "memlock", T_Memlock, FOLLBY_TOKEN }, 224280849Scy{ "stacksize", T_Stacksize, FOLLBY_TOKEN }, 225280849Scy{ "filenum", T_Filenum, FOLLBY_TOKEN }, 226258945Sroberto/* tinker_option */ 227258945Sroberto{ "step", T_Step, FOLLBY_TOKEN }, 228282408Scy{ "stepback", T_Stepback, FOLLBY_TOKEN }, 229282408Scy{ "stepfwd", T_Stepfwd, FOLLBY_TOKEN }, 230258945Sroberto{ "panic", T_Panic, FOLLBY_TOKEN }, 231258945Sroberto{ "dispersion", T_Dispersion, FOLLBY_TOKEN }, 232258945Sroberto{ "stepout", T_Stepout, FOLLBY_TOKEN }, 233258945Sroberto{ "allan", T_Allan, FOLLBY_TOKEN }, 234258945Sroberto{ "huffpuff", T_Huffpuff, FOLLBY_TOKEN }, 235258945Sroberto{ "freq", T_Freq, FOLLBY_TOKEN }, 236258945Sroberto/* miscellaneous_command */ 237258945Sroberto{ "port", T_Port, FOLLBY_TOKEN }, 238258945Sroberto{ "interface", T_Interface, FOLLBY_TOKEN }, 239258945Sroberto{ "saveconfigdir", T_Saveconfigdir, FOLLBY_STRING }, 240258945Sroberto/* interface_command (ignore and interface already defined) */ 241258945Sroberto{ "nic", T_Nic, FOLLBY_TOKEN }, 242258945Sroberto{ "all", T_All, FOLLBY_TOKEN }, 243258945Sroberto{ "ipv4", T_Ipv4, FOLLBY_TOKEN }, 244258945Sroberto{ "ipv6", T_Ipv6, FOLLBY_TOKEN }, 245258945Sroberto{ "wildcard", T_Wildcard, FOLLBY_TOKEN }, 246258945Sroberto{ "listen", T_Listen, FOLLBY_TOKEN }, 247258945Sroberto{ "drop", T_Drop, FOLLBY_TOKEN }, 248258945Sroberto/* simulator commands */ 249258945Sroberto{ "simulate", T_Simulate, FOLLBY_TOKEN }, 250258945Sroberto{ "simulation_duration",T_Sim_Duration, FOLLBY_TOKEN }, 251258945Sroberto{ "beep_delay", T_Beep_Delay, FOLLBY_TOKEN }, 252258945Sroberto{ "duration", T_Duration, FOLLBY_TOKEN }, 253258945Sroberto{ "server_offset", T_Server_Offset, FOLLBY_TOKEN }, 254258945Sroberto{ "freq_offset", T_Freq_Offset, FOLLBY_TOKEN }, 255258945Sroberto{ "wander", T_Wander, FOLLBY_TOKEN }, 256258945Sroberto{ "jitter", T_Jitter, FOLLBY_TOKEN }, 257258945Sroberto{ "prop_delay", T_Prop_Delay, FOLLBY_TOKEN }, 258258945Sroberto{ "proc_delay", T_Proc_Delay, FOLLBY_TOKEN }, 259258945Sroberto}; 260258945Sroberto 261258945Srobertotypedef struct big_scan_state_tag { 262258945Sroberto char ch; /* Character this state matches on */ 263258945Sroberto char followedby; /* Forces next token(s) to T_String */ 264258945Sroberto u_short finishes_token; /* nonzero ID if last keyword char */ 265258945Sroberto u_short match_next_s; /* next state to check matching ch */ 266258945Sroberto u_short other_next_s; /* next state to check if not ch */ 267258945Sroberto} big_scan_state; 268258945Sroberto 269258945Sroberto/* 270258945Sroberto * Note: to increase MAXSTATES beyond 2048, be aware it is currently 271258945Sroberto * crammed into 11 bits in scan_state form. Raising to 4096 would be 272258945Sroberto * relatively easy by storing the followedby value in a separate 273258945Sroberto * array with one entry per token, and shrinking the char value to 274258945Sroberto * 7 bits to free a bit for accepting/non-accepting. More than 4096 275258945Sroberto * states will require expanding scan_state beyond 32 bits each. 276258945Sroberto */ 277280849Scy#define MAXSTATES 2048 278280849Scy#define MAX_TOK_LEN 63 279258945Sroberto 280258945Srobertoconst char * current_keyword;/* for error reporting */ 281258945Srobertobig_scan_state sst[MAXSTATES]; /* scanner FSM state entries */ 282280849Scyu_short sst_highwater; /* next entry index to consider */ 283258945Srobertochar * symb[1024]; /* map token ID to symbolic name */ 284258945Sroberto 285258945Sroberto/* for libntp */ 286258945Srobertoconst char * progname = "keyword-gen"; 287258945Sroberto 288258945Srobertoint main (int, char **); 289258945Srobertostatic void generate_preamble (void); 290258945Srobertostatic void generate_fsm (void); 291258945Srobertostatic void generate_token_text (void); 292280849Scystatic u_short create_keyword_scanner (void); 293280849Scystatic u_short create_scan_states (char *, u_short, follby, u_short); 294280849Scyint compare_key_tok_id (const void *, const void *); 295280849Scyint compare_key_tok_text (const void *, const void *); 296258945Srobertovoid populate_symb (char *); 297280849Scyconst char * symbname (u_short); 298258945Sroberto 299258945Sroberto 300258945Srobertoint main(int argc, char **argv) 301258945Sroberto{ 302258945Sroberto if (argc < 2) { 303258945Sroberto fprintf(stderr, "Usage:\n%s t_header.h\n", argv[0]); 304258945Sroberto exit(1); 305258945Sroberto } 306280849Scy debug = 1; 307280849Scy 308258945Sroberto populate_symb(argv[1]); 309258945Sroberto 310258945Sroberto generate_preamble(); 311258945Sroberto generate_token_text(); 312258945Sroberto generate_fsm(); 313258945Sroberto 314258945Sroberto return 0; 315258945Sroberto} 316258945Sroberto 317258945Sroberto 318258945Srobertostatic void 319258945Srobertogenerate_preamble(void) 320258945Sroberto{ 321258945Sroberto time_t now; 322258945Sroberto char timestamp[128]; 323258945Sroberto char preamble[] = 324258945Sroberto"/*\n" 325258945Sroberto" * ntp_keyword.h\n" 326258945Sroberto" * \n" 327258945Sroberto" * NOTE: edit this file with caution, it is generated by keyword-gen.c\n" 328258945Sroberto" *\t Generated %s UTC diff_ignore_line\n" 329258945Sroberto" *\n" 330258945Sroberto" */\n" 331258945Sroberto"#include \"ntp_scanner.h\"\n" 332258945Sroberto"#include \"ntp_parser.h\"\n" 333258945Sroberto"\n"; 334258945Sroberto 335258945Sroberto time(&now); 336258945Sroberto if (!strftime(timestamp, sizeof(timestamp), 337258945Sroberto "%Y-%m-%d %H:%M:%S", gmtime(&now))) 338258945Sroberto timestamp[0] = '\0'; 339258945Sroberto 340258945Sroberto printf(preamble, timestamp); 341258945Sroberto} 342258945Sroberto 343258945Sroberto 344258945Srobertostatic void 345258945Srobertogenerate_fsm(void) 346258945Sroberto{ 347280849Scy char rprefix[MAX_TOK_LEN + 1]; 348280849Scy char prefix[MAX_TOK_LEN + 1]; 349280849Scy char token_id_comment[16 + MAX_TOK_LEN + 1]; 350280849Scy size_t prefix_len; 351280849Scy char *p; 352280849Scy char *r; 353280849Scy u_short initial_state; 354280849Scy u_short this_state; 355280849Scy u_short state; 356280849Scy u_short i; 357280849Scy u_short token; 358258945Sroberto 359285169Scy /* 360258945Sroberto * Sort ntp_keywords in alphabetical keyword order. This is 361258945Sroberto * not necessary, but minimizes nonfunctional changes in the 362258945Sroberto * generated finite state machine when keywords are modified. 363258945Sroberto */ 364258945Sroberto qsort(ntp_keywords, COUNTOF(ntp_keywords), 365258945Sroberto sizeof(ntp_keywords[0]), compare_key_tok_text); 366258945Sroberto 367258945Sroberto /* 368285169Scy * To save space, reserve the state array entry matching each 369258945Sroberto * token number for its terminal state, so the token identifier 370258945Sroberto * does not need to be stored in each state, but can be 371258945Sroberto * recovered trivially. To mark the entry reserved, 372258945Sroberto * finishes_token is nonzero. 373258945Sroberto */ 374258945Sroberto 375258945Sroberto for (i = 0; i < COUNTOF(ntp_keywords); i++) { 376258945Sroberto token = ntp_keywords[i].token; 377258945Sroberto if (1 > token || token >= COUNTOF(sst)) { 378258945Sroberto fprintf(stderr, 379258945Sroberto "keyword-gen sst[%u] too small " 380258945Sroberto "for keyword '%s' id %d\n", 381280849Scy (int)COUNTOF(sst), 382258945Sroberto ntp_keywords[i].key, 383258945Sroberto token); 384258945Sroberto exit(4); 385258945Sroberto } 386258945Sroberto sst[token].finishes_token = token; 387258945Sroberto } 388258945Sroberto 389258945Sroberto initial_state = create_keyword_scanner(); 390258945Sroberto 391258945Sroberto fprintf(stderr, 392258945Sroberto "%d keywords consumed %d states of %d max.\n", 393258945Sroberto (int)COUNTOF(ntp_keywords), 394258945Sroberto sst_highwater - 1, 395258945Sroberto (int)COUNTOF(sst) - 1); 396258945Sroberto 397258945Sroberto printf("#define SCANNER_INIT_S %d\n\n", initial_state); 398258945Sroberto 399258945Sroberto printf("const scan_state sst[%d] = {\n" 400258945Sroberto "/*SS_T( ch,\tf-by, match, other ),\t\t\t\t */\n" 401258945Sroberto " 0,\t\t\t\t /* %5d %-17s */\n", 402258945Sroberto sst_highwater, 403258945Sroberto 0, ""); 404258945Sroberto 405258945Sroberto for (i = 1; i < sst_highwater; i++) { 406258945Sroberto 407258945Sroberto /* verify fields will fit */ 408258945Sroberto if (sst[i].followedby & ~0x3) { 409258945Sroberto fprintf(stderr, 410258945Sroberto "keyword-gen internal error " 411258945Sroberto "sst[%d].followedby %d too big\n", 412258945Sroberto i, sst[i].followedby); 413258945Sroberto exit(7); 414258945Sroberto } 415258945Sroberto 416258945Sroberto if (sst_highwater <= sst[i].match_next_s 417258945Sroberto || sst[i].match_next_s & ~0x7ff) { 418258945Sroberto fprintf(stderr, 419258945Sroberto "keyword-gen internal error " 420258945Sroberto "sst[%d].match_next_s %d too big\n", 421258945Sroberto i, sst[i].match_next_s); 422258945Sroberto exit(8); 423258945Sroberto } 424258945Sroberto 425258945Sroberto if (sst_highwater <= sst[i].other_next_s 426258945Sroberto || sst[i].other_next_s & ~0x7ff) { 427258945Sroberto fprintf(stderr, 428258945Sroberto "keyword-gen internal error " 429258945Sroberto "sst[%d].other_next_s %d too big\n", 430258945Sroberto i, sst[i].other_next_s); 431258945Sroberto exit(9); 432258945Sroberto } 433258945Sroberto 434280849Scy if (sst[i].finishes_token) { 435285169Scy snprintf(token_id_comment, 436258945Sroberto sizeof(token_id_comment), "%5d %-17s", 437258945Sroberto i, symbname(sst[i].finishes_token)); 438258945Sroberto if (i != sst[i].finishes_token) { 439258945Sroberto fprintf(stderr, 440258945Sroberto "keyword-gen internal error " 441258945Sroberto "entry %d finishes token %d\n", 442258945Sroberto i, sst[i].finishes_token); 443258945Sroberto exit(5); 444258945Sroberto } 445280849Scy } else { 446280849Scy /* 447280849Scy * Determine the keyword prefix that leads to this 448280849Scy * state. This is expensive but keyword-gen is run 449280849Scy * only when it changes. Distributing keyword-gen-utd 450280849Scy * achieves that, which is why it must be committed 451280849Scy * at the same time as keyword-gen.c and ntp_keyword.h. 452280849Scy * 453280849Scy * Scan the state array iteratively looking for a state 454280849Scy * which leads to the current one, collecting matching 455280849Scy * characters along the way. There is only one such 456280849Scy * path back to the starting state given the way our 457280849Scy * scanner state machine is built and the practice of 458280849Scy * using the spelling of the keyword as its T_* token 459280849Scy * identifier, which results in never having two 460280849Scy * spellings result in the same T_* value. 461280849Scy */ 462280849Scy prefix_len = 0; 463280849Scy this_state = i; 464280849Scy do { 465280849Scy for (state = 1; state < sst_highwater; state++) 466280849Scy if (sst[state].other_next_s == this_state) { 467280849Scy this_state = state; 468280849Scy break; 469280849Scy } else if (sst[state].match_next_s == this_state) { 470280849Scy this_state = state; 471280849Scy rprefix[prefix_len] = sst[state].ch; 472280849Scy prefix_len++; 473280849Scy break; 474280849Scy } 475280849Scy } while (this_state != initial_state); 476280849Scy 477280849Scy if (prefix_len) { 478280849Scy /* reverse rprefix into prefix */ 479280849Scy p = prefix + prefix_len; 480280849Scy r = rprefix; 481280849Scy while (r < rprefix + prefix_len) 482280849Scy *--p = *r++; 483280849Scy } 484280849Scy prefix[prefix_len] = '\0'; 485280849Scy 486280849Scy snprintf(token_id_comment, 487280849Scy sizeof(token_id_comment), "%5d %-17s", 488285169Scy i, (initial_state == i) 489285169Scy ? "[initial state]" 490280849Scy : prefix); 491258945Sroberto } 492258945Sroberto 493258945Sroberto printf(" S_ST( '%c',\t%d, %5u, %5u )%s /* %s */\n", 494258945Sroberto sst[i].ch, 495258945Sroberto sst[i].followedby, 496258945Sroberto sst[i].match_next_s, 497258945Sroberto sst[i].other_next_s, 498258945Sroberto (i + 1 < sst_highwater) 499258945Sroberto ? "," 500258945Sroberto : " ", 501258945Sroberto token_id_comment); 502258945Sroberto } 503258945Sroberto 504258945Sroberto printf("};\n\n"); 505258945Sroberto} 506258945Sroberto 507258945Sroberto 508258945Sroberto/* Define a function to create the states of the scanner. This function 509258945Sroberto * is used by the create_keyword_scanner function below. 510258945Sroberto * 511258945Sroberto * This function takes a suffix of a keyword, the token to be returned on 512258945Sroberto * recognizing the complete keyword, and any pre-existing state that exists 513258945Sroberto * for some other keyword that has the same prefix as the current one. 514258945Sroberto */ 515280849Scystatic u_short 516258945Srobertocreate_scan_states( 517285169Scy char * text, 518285169Scy u_short token, 519258945Sroberto follby followedby, 520280849Scy u_short prev_state 521258945Sroberto ) 522258945Sroberto{ 523280849Scy u_short my_state; 524280849Scy u_short return_state; 525280849Scy u_short prev_char_s; 526280849Scy u_short curr_char_s; 527258945Sroberto 528258945Sroberto return_state = prev_state; 529258945Sroberto curr_char_s = prev_state; 530258945Sroberto prev_char_s = 0; 531258945Sroberto 532285169Scy /* Find the correct position to insert the state. 533258945Sroberto * All states should be in alphabetical order 534258945Sroberto */ 535258945Sroberto while (curr_char_s && (text[0] < sst[curr_char_s].ch)) { 536258945Sroberto prev_char_s = curr_char_s; 537258945Sroberto curr_char_s = sst[curr_char_s].other_next_s; 538258945Sroberto } 539258945Sroberto 540285169Scy /* 541258945Sroberto * Check if a previously seen keyword has the same prefix as 542258945Sroberto * the current keyword. If so, simply use the state for that 543258945Sroberto * keyword as my_state, otherwise, allocate a new state. 544258945Sroberto */ 545258945Sroberto if (curr_char_s && (text[0] == sst[curr_char_s].ch)) { 546258945Sroberto my_state = curr_char_s; 547258945Sroberto if ('\0' == text[1]) { 548258945Sroberto fprintf(stderr, 549258945Sroberto "Duplicate entries for keyword '%s' in" 550258945Sroberto " keyword_gen.c ntp_keywords[].\n", 551258945Sroberto current_keyword); 552258945Sroberto exit(2); 553258945Sroberto } 554258945Sroberto } else { 555258945Sroberto do 556258945Sroberto my_state = sst_highwater++; 557258945Sroberto while (my_state < COUNTOF(sst) 558258945Sroberto && sst[my_state].finishes_token); 559258945Sroberto if (my_state >= COUNTOF(sst)) { 560258945Sroberto fprintf(stderr, 561258945Sroberto "fatal, keyword scanner state array " 562258945Sroberto "sst[%d] is too small, modify\n" 563258945Sroberto "keyword-gen.c to increase.\n", 564258945Sroberto (int)COUNTOF(sst)); 565258945Sroberto exit(3); 566258945Sroberto } 567258945Sroberto /* Store the next character of the keyword */ 568285169Scy sst[my_state].ch = text[0]; 569258945Sroberto sst[my_state].other_next_s = curr_char_s; 570258945Sroberto sst[my_state].followedby = FOLLBY_NON_ACCEPTING; 571258945Sroberto 572258945Sroberto if (prev_char_s) 573258945Sroberto sst[prev_char_s].other_next_s = my_state; 574258945Sroberto else 575258945Sroberto return_state = my_state; 576258945Sroberto } 577258945Sroberto 578258945Sroberto /* Check if the next character is '\0'. 579258945Sroberto * If yes, we are done with the recognition and this is an accepting 580258945Sroberto * state. 581258945Sroberto * If not, we need to continue scanning 582258945Sroberto */ 583258945Sroberto if ('\0' == text[1]) { 584258945Sroberto sst[my_state].finishes_token = (u_short)token; 585258945Sroberto sst[my_state].followedby = (char)followedby; 586258945Sroberto 587258945Sroberto if (sst[token].finishes_token != (u_short)token) { 588258945Sroberto fprintf(stderr, 589258945Sroberto "fatal, sst[%d] not reserved for %s.\n", 590258945Sroberto token, symbname(token)); 591258945Sroberto exit(6); 592258945Sroberto } 593258945Sroberto /* relocate so token id is sst[] index */ 594258945Sroberto if (my_state != token) { 595258945Sroberto sst[token] = sst[my_state]; 596280849Scy ZERO(sst[my_state]); 597258945Sroberto do 598258945Sroberto sst_highwater--; 599258945Sroberto while (sst[sst_highwater].finishes_token); 600258945Sroberto my_state = token; 601258945Sroberto if (prev_char_s) 602258945Sroberto sst[prev_char_s].other_next_s = my_state; 603258945Sroberto else 604258945Sroberto return_state = my_state; 605258945Sroberto } 606258945Sroberto } else 607285169Scy sst[my_state].match_next_s = 608258945Sroberto create_scan_states( 609258945Sroberto &text[1], 610258945Sroberto token, 611258945Sroberto followedby, 612258945Sroberto sst[my_state].match_next_s); 613258945Sroberto 614258945Sroberto return return_state; 615258945Sroberto} 616258945Sroberto 617258945Sroberto 618258945Sroberto/* Define a function that takes a list of (keyword, token) values and 619258945Sroberto * creates a keywords scanner out of it. 620258945Sroberto */ 621258945Sroberto 622280849Scystatic u_short 623258945Srobertocreate_keyword_scanner(void) 624258945Sroberto{ 625280849Scy u_short scanner; 626280849Scy u_short i; 627258945Sroberto 628258945Sroberto sst_highwater = 1; /* index 0 invalid, unused */ 629258945Sroberto scanner = 0; 630258945Sroberto 631258945Sroberto for (i = 0; i < COUNTOF(ntp_keywords); i++) { 632258945Sroberto current_keyword = ntp_keywords[i].key; 633258945Sroberto scanner = 634258945Sroberto create_scan_states( 635285169Scy ntp_keywords[i].key, 636285169Scy ntp_keywords[i].token, 637258945Sroberto ntp_keywords[i].followedby, 638258945Sroberto scanner); 639258945Sroberto } 640258945Sroberto 641258945Sroberto return scanner; 642258945Sroberto} 643258945Sroberto 644258945Sroberto 645258945Srobertostatic void 646258945Srobertogenerate_token_text(void) 647258945Sroberto{ 648280849Scy u_short lowest_id; 649280849Scy u_short highest_id; 650280849Scy u_short id_count; 651280849Scy u_short id; 652280849Scy u_short i; 653258945Sroberto 654258945Sroberto /* sort ntp_keywords in token ID order */ 655258945Sroberto qsort(ntp_keywords, COUNTOF(ntp_keywords), 656258945Sroberto sizeof(ntp_keywords[0]), compare_key_tok_id); 657258945Sroberto 658258945Sroberto lowest_id = ntp_keywords[0].token; 659258945Sroberto highest_id = ntp_keywords[COUNTOF(ntp_keywords) - 1].token; 660258945Sroberto id_count = highest_id - lowest_id + 1; 661258945Sroberto 662258945Sroberto printf("#define LOWEST_KEYWORD_ID %d\n\n", lowest_id); 663258945Sroberto 664258945Sroberto printf("const char * const keyword_text[%d] = {", id_count); 665258945Sroberto 666258945Sroberto id = lowest_id; 667258945Sroberto i = 0; 668258945Sroberto while (i < COUNTOF(ntp_keywords)) { 669258945Sroberto while (id < ntp_keywords[i].token) { 670258945Sroberto printf(",\n\t/* %-5d %5d %20s */\tNULL", 671258945Sroberto id - lowest_id, id, symbname(id)); 672258945Sroberto id++; 673258945Sroberto } 674258945Sroberto if (i > 0) 675258945Sroberto printf(","); 676258945Sroberto printf("\n\t/* %-5d %5d %20s */\t\"%s\"", 677285169Scy id - lowest_id, id, symbname(id), 678258945Sroberto ntp_keywords[i].key); 679258945Sroberto i++; 680258945Sroberto id++; 681258945Sroberto } 682258945Sroberto 683258945Sroberto printf("\n};\n\n"); 684258945Sroberto} 685258945Sroberto 686285169Scy 687258945Srobertoint 688258945Srobertocompare_key_tok_id( 689280849Scy const void *a1, 690280849Scy const void *a2 691258945Sroberto ) 692258945Sroberto{ 693280849Scy const struct key_tok *p1 = a1; 694280849Scy const struct key_tok *p2 = a2; 695258945Sroberto 696258945Sroberto if (p1->token == p2->token) 697258945Sroberto return 0; 698258945Sroberto 699258945Sroberto if (p1->token < p2->token) 700258945Sroberto return -1; 701258945Sroberto else 702258945Sroberto return 1; 703258945Sroberto} 704258945Sroberto 705258945Sroberto 706258945Srobertoint 707258945Srobertocompare_key_tok_text( 708280849Scy const void *a1, 709280849Scy const void *a2 710258945Sroberto ) 711258945Sroberto{ 712280849Scy const struct key_tok *p1 = a1; 713280849Scy const struct key_tok *p2 = a2; 714258945Sroberto 715258945Sroberto return strcmp(p1->key, p2->key); 716258945Sroberto} 717258945Sroberto 718258945Sroberto 719258945Sroberto/* 720258945Sroberto * populate_symb() - populate symb[] lookup array with symbolic token 721258945Sroberto * names such that symb[T_Age] == "T_Age", etc. 722258945Sroberto */ 723258945Srobertovoid 724258945Srobertopopulate_symb( 725258945Sroberto char *header_file 726258945Sroberto ) 727258945Sroberto{ 728258945Sroberto FILE * yh; 729280849Scy char line[2 * MAX_TOK_LEN]; 730280849Scy char name[2 * MAX_TOK_LEN]; 731258945Sroberto int token; 732258945Sroberto 733258945Sroberto yh = fopen(header_file, "r"); 734258945Sroberto if (NULL == yh) { 735258945Sroberto perror("unable to open yacc/bison header file"); 736258945Sroberto exit(4); 737258945Sroberto } 738258945Sroberto 739258945Sroberto while (NULL != fgets(line, sizeof(line), yh)) 740258945Sroberto if (2 == sscanf(line, "#define %s %d", name, &token) 741258945Sroberto && 'T' == name[0] && '_' == name[1] && token >= 0 742280849Scy && token < COUNTOF(symb)) { 743258945Sroberto 744258945Sroberto symb[token] = estrdup(name); 745280849Scy if (strlen(name) > MAX_TOK_LEN) { 746280849Scy fprintf(stderr, 747280849Scy "MAX_TOK_LEN %d too small for '%s'\n" 748280849Scy "Edit keyword-gen.c to raise.\n", 749280849Scy MAX_TOK_LEN, name); 750280849Scy exit(10); 751280849Scy } 752280849Scy } 753258945Sroberto fclose(yh); 754258945Sroberto} 755258945Sroberto 756258945Sroberto 757258945Srobertoconst char * 758258945Srobertosymbname( 759280849Scy u_short token 760258945Sroberto ) 761258945Sroberto{ 762258945Sroberto char *name; 763258945Sroberto 764280849Scy if (token < COUNTOF(symb) && symb[token] != NULL) { 765280849Scy name = symb[token]; 766280849Scy } else { 767280849Scy LIB_GETBUF(name); 768280849Scy snprintf(name, LIB_BUFLENGTH, "%d", token); 769285169Scy } 770258945Sroberto 771258945Sroberto return name; 772258945Sroberto} 773