contrib/ntp/ntpd/keyword-gen.c

   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 */
  32 struct 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
  39 struct 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
 261 typedef 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
 280 const char *    current_keyword;/* for error reporting */
 281 big_scan_state  sst[MAXSTATES]; /* scanner FSM state entries */
 282 u_short         sst_highwater;  /* next entry index to consider */
 283 char *          symb[1024];     /* map token ID to symbolic name */
 284
 285 /* for libntp */
 286 const char *    progname = "keyword-gen";
 287
 288 int             main                    (int, char **);
 289 static void     generate_preamble       (void);
 290 static void     generate_fsm            (void);
 291 static void     generate_token_text     (void);
 292 static u_short  create_keyword_scanner  (void);
 293 static u_short  create_scan_states      (char *, u_short, follby, u_short);
 294 int             compare_key_tok_id      (const void *, const void *);
 295 int             compare_key_tok_text    (const void *, const void *);
 296 void            populate_symb           (char *);
 297 const char *    symbname                (u_short);
 298
 299
 300 int 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
 318 static void
 319 generate_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
 344 static void
 345 generate_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  */
 515 static u_short
 516 create_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
 622 static u_short
 623 create_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
 645 static void
 646 generate_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
 687 int
 688 compare_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
 706 int
 707 compare_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  */
 723 void
 724 populate_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
 757 const char *
 758 symbname(
 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 }