vlib/vlib/parse.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 #include <vlib/parse.h>
  16
  17 #define PARSE_DEBUG 0
  18
  19 u16 word_type_index, number_type_index, eof_type_index, rule_eof_type_index,
  20     plus_type_index, minus_type_index, star_type_index, slash_type_index,
  21     lpar_type_index, rpar_type_index;
  22
  23 u8 * format_vlib_parse_value (u8 * s, va_list * args)
  24 {
  25   vlib_parse_main_t *pm = va_arg (*args, vlib_parse_main_t *);
  26   vlib_parse_type_t *type;
  27   vlib_parse_value_t *v;
  28   u16 type_index;
  29
  30   s = format (s, "%d items:\n", vec_len (pm->parse_value));
  31   vec_foreach (v, pm->parse_value)
  32     {
  33       type_index = v->type;
  34       type = pool_elt_at_index (pm->parse_types, type_index);
  35       if (type->format_value)
  36         s = format (s, "[%d]: %U\n", v - pm->parse_value,
  37                     type->format_value, v);
  38       else
  39         s = format (s, "[%d]: (nofun)\n", v - pm->parse_value);
  40     }
  41   return s;
  42 }
  43
  44 static u8 * format_vlib_parse_match (u8 * s, va_list * args)
  45 {
  46   vlib_parse_match_t m = va_arg (*args, vlib_parse_match_t);
  47   char * t = 0;
  48   switch (m)
  49     {
  50 #define _(a) case VLIB_PARSE_##a: t = #a; break;
  51       foreach_parse_match_type
  52 #undef _
  53     default: t = 0; break;
  54     }
  55
  56   if (t)
  57     return format (s, "%s", t);
  58   else
  59     return format (s, "unknown 0x%x", m);
  60 }
  61
  62 static u8 * format_vlib_parse_item (u8 * s, va_list * args)
  63 {
  64   vlib_parse_main_t *pm = va_arg (*args, vlib_parse_main_t *);
  65   vlib_parse_item_t *item = va_arg (*args, vlib_parse_item_t *);
  66   vlib_parse_type_t *type = pool_elt_at_index (pm->parse_types, item->type);
  67
  68   if (item->type == word_type_index)
  69     s = format (s, "%s", item->value.as_pointer);
  70   else
  71     s = format (s, "<%s>", type->name);
  72   return s;
  73 }
  74
  75 static u8 * format_vlib_parse_graph (u8 * s, va_list * args)
  76 {
  77   vlib_parse_main_t *pm = va_arg (*args, vlib_parse_main_t *);
  78   vlib_parse_graph_t *node = va_arg (*args, vlib_parse_graph_t *);
  79   vlib_parse_item_t *item;
  80   vlib_parse_type_t *type;
  81
  82   /* $$$ hash table */
  83   pool_foreach (type, pm->parse_types,
  84                 ({
  85                   if (type->rule_index == node - pm->parse_graph)
  86                     s = format (s, "\n<%s>\n", type->name);
  87                 }));
  88
  89   if (pm->root_index == (node - pm->parse_graph))
  90     s = format (s, "\n<root>\n");
  91
  92   item = pool_elt_at_index (pm->parse_items, node->item);
  93
  94   s = format (s, "[%d] %U ", node - pm->parse_graph,
  95               format_vlib_parse_item, pm, item);
  96
  97   if (node->peer == (u32)~0)
  98     s = format (s, "peer nil  ");
  99   else
 100     s = format (s, "peer %4u ", node->peer);
 101
 102   if (node->deeper == (u32)~0)
 103     s = format (s, "deeper nil  ");
 104   else
 105     s = format (s, "deeper %4u ", node->deeper);
 106
 107   return s;
 108 }
 109
 110 void dump_parse_graph (void)
 111 {
 112   vlib_parse_main_t *pm = &vlib_parse_main;
 113   vlib_parse_graph_t *node;
 114
 115   pool_foreach (node, pm->parse_graph, ({
 116     fformat(stdout, "%U\n", format_vlib_parse_graph, pm, node);
 117   }));
 118 }
 119
 120 always_inline void
 121 parse_cleanup_value (vlib_parse_main_t *pm, vlib_parse_value_t *pv)
 122 {
 123   vlib_parse_type_t *type = pool_elt_at_index (pm->parse_types, pv->type);
 124   if (type->value_cleanup_function)
 125     type->value_cleanup_function (pv);
 126 }
 127
 128 static void parse_reset (vlib_parse_main_t *pm, u8 *input)
 129 {
 130   vlib_lex_token_t *t;
 131   vlib_parse_value_t *pv;
 132
 133   vlib_lex_reset (pm->lex_main, input);
 134
 135   vec_foreach (t, pm->tokens)
 136     vlib_lex_cleanup_token (t);
 137
 138   vec_foreach (pv, pm->parse_value)
 139     parse_cleanup_value (pm, pv);
 140
 141   _vec_len (pm->parse_value) = 0;
 142   _vec_len (pm->tokens) = 0;
 143   pm->current_token_index = 0;
 144 }
 145
 146 static void parse_help (vlib_parse_main_t *pm, u32 index)
 147 {
 148   vlib_parse_graph_t *node;
 149   vlib_parse_item_t  *item;
 150   vlib_parse_type_t  *type;
 151   vlib_main_t *vm = pm->vlib_main;
 152   u8 *help_input;
 153   int i;
 154
 155   help_input = vec_dup (pm->lex_main->input_vector);
 156
 157   for (i = vec_len(help_input)-1; i >= 0; i--)
 158     if (help_input[i] == '?')
 159       {
 160         help_input[i] = 0;
 161         _vec_len(help_input) = i;
 162         break;
 163       }
 164
 165   for (i = vec_len(help_input)-1; i >= 0; i--)
 166     {
 167       if (help_input[i] != ' ' && help_input[i] != '\t')
 168         break;
 169       help_input[i] = 0;
 170       break;
 171     }
 172   _vec_len(help_input) = i+1;
 173
 174   while (index != (u32)~0)
 175     {
 176       node = pool_elt_at_index (pm->parse_graph, index);
 177       item = pool_elt_at_index (pm->parse_items, node->item);
 178       type = pool_elt_at_index (pm->parse_types, item->type);
 179
 180       if (item->type == eof_type_index && vec_len (pm->match_items) == 0)
 181         /* do nothing */;
 182       else if (item->type == word_type_index)
 183         vlib_cli_output (vm, "%s %s\n", help_input, item->value.as_pointer);
 184       else
 185         vlib_cli_output (vm, "%s <%s>\n", help_input, type->name);
 186       index = node->peer;
 187     }
 188   vec_free (help_input);
 189 }
 190
 191 static vlib_parse_match_t
 192 parse_eval_internal (vlib_parse_main_t *pm, u32 index)
 193 {
 194   vlib_parse_graph_t *node;
 195   vlib_parse_item_t  *item;
 196   vlib_parse_type_t  *type;
 197   vlib_parse_value_t value, *pv;
 198   vlib_parse_match_t rv;
 199   u32 *partial_matches = 0;
 200   vlib_lex_token_t *t;
 201   u32 save_token_index=(u32)~0, save_match_items=0;
 202   int had_value = 0;
 203
 204   if (pm->current_token_index >= vec_len(pm->tokens))
 205     return VLIB_PARSE_MATCH_FAIL;
 206
 207   /* current token */
 208   t = vec_elt_at_index (pm->tokens, pm->current_token_index);
 209
 210   /* Help ? */
 211   if (PREDICT_FALSE(t->token == VLIB_LEX_qmark))
 212     {
 213       parse_help (pm, index);
 214       _vec_len (pm->match_items) = 0;
 215       return VLIB_PARSE_MATCH_DONE;
 216     }
 217
 218   /* Across all peers at this level of the parse graph */
 219   while (index != (u32)~0)
 220     {
 221       node = pool_elt_at_index (pm->parse_graph, index);
 222       item = pool_elt_at_index (pm->parse_items, node->item);
 223       type = pool_elt_at_index (pm->parse_types, item->type);
 224
 225       /*
 226        * Save the token index. We may have to back up several
 227        * trie plies. Type-specific match functions can consume
 228        * multiple tokens, and they may not be optimally careful
 229        */
 230       save_token_index = pm->current_token_index;
 231       save_match_items = vec_len (pm->match_items);
 232       vec_add1 (pm->match_items, node->item);
 233
 234       if (PARSE_DEBUG > 1)
 235         clib_warning ("Try to match token %U against node %d",
 236                       format_vlib_lex_token, pm->lex_main, t, index);
 237
 238       /* Call the type-specific match function */
 239       rv = type->match_function (pm, type, t, &value);
 240
 241       if (PARSE_DEBUG > 1)
 242         clib_warning ("returned %U", format_vlib_parse_match, rv);
 243
 244       switch (rv)
 245         {
 246         case VLIB_PARSE_MATCH_VALUE:
 247           /*
 248            * Matched, and returned a value to append to the
 249            * set of args passed to the action function
 250            */
 251           value.type = item->type;
 252           vec_add1 (pm->parse_value, value);
 253           had_value = 1;
 254           /* fallthrough */
 255
 256         case VLIB_PARSE_MATCH_FULL:
 257         unambiguous_partial_match:
 258           /* Consume the matched token */
 259           pm->current_token_index++;
 260
 261           /* continue matching along this path */
 262           rv = parse_eval_internal (pm, node->deeper);
 263
 264           /* this is not the right path */
 265           if (rv == VLIB_PARSE_MATCH_FAIL)
 266             {
 267               if (had_value)
 268                 {
 269                   /* Delete the value */
 270                   value = pm->parse_value [vec_len (pm->parse_value)-1];
 271                   parse_cleanup_value (pm, &value);
 272                   _vec_len (pm->parse_value) -= 1;
 273                 }
 274               /* Continue with the next sibling */
 275               pm->current_token_index = save_token_index;
 276               _vec_len (pm->match_items) = save_match_items;
 277               index = node->peer;
 278               break;
 279             }
 280           return rv;
 281
 282         case VLIB_PARSE_MATCH_PARTIAL:
 283           /* Partial (substring) match, remember it but keep going */
 284           vec_add1 (partial_matches, node - pm->parse_graph);
 285           index = node->peer;
 286           break;
 287
 288         case VLIB_PARSE_MATCH_FAIL:
 289           /* Continue with the next sibling */
 290           index = node->peer;
 291           _vec_len (pm->match_items) = save_match_items;
 292           break;
 293
 294         case VLIB_PARSE_MATCH_DONE:
 295           /* Parse complete, invoke the action function */
 296           if (PARSE_DEBUG > 0)
 297             clib_warning ("parse_value: %U", format_vlib_parse_value, pm);
 298
 299           {
 300             vlib_parse_eval_function_t * f = item->value.as_pointer;
 301             if (f)
 302               rv = f (pm, item, pm->parse_value);
 303           }
 304
 305           vec_foreach (pv, pm->parse_value)
 306             parse_cleanup_value (pm, pv);
 307           _vec_len (pm->parse_value) = 0;
 308           _vec_len (pm->match_items) = 0;
 309           return rv;
 310
 311         case VLIB_PARSE_MATCH_AMBIGUOUS:
 312         case VLIB_PARSE_MATCH_EVAL_FAIL:
 313         case VLIB_PARSE_MATCH_RULE:
 314           _vec_len (pm->match_items) = save_match_items;
 315           return rv;
 316         }
 317     }
 318
 319   /*
 320    * Out of siblings. If we have exactly one partial match
 321    * we win
 322    */
 323   if (vec_len (partial_matches) == 1)
 324     {
 325       index = partial_matches[0];
 326       node = pool_elt_at_index (pm->parse_graph, index);
 327       vec_free (partial_matches);
 328       goto unambiguous_partial_match;
 329     }
 330
 331   /* Ordinary loser */
 332   rv = VLIB_PARSE_MATCH_FAIL;
 333
 334   /* Ambiguous loser */
 335   if (vec_len (partial_matches) > 1)
 336     {
 337       vec_free (partial_matches);
 338       rv = VLIB_PARSE_MATCH_AMBIGUOUS;
 339     }
 340
 341   _vec_len (pm->match_items) = save_match_items;
 342   return rv;
 343 }
 344
 345 vlib_parse_match_t rule_match (vlib_parse_main_t *pm, vlib_parse_type_t *type,
 346                                vlib_lex_token_t *t,
 347                                vlib_parse_value_t *valuep)
 348 {
 349   vlib_parse_match_t rv;
 350   static int recursion_level;
 351
 352   if (PARSE_DEBUG > 1)
 353     clib_warning ("[%d]: try to match type %s graph index %d",
 354                   recursion_level,
 355                   type->name,
 356                   type->rule_index);
 357   recursion_level++;
 358   rv = parse_eval_internal (pm, type->rule_index);
 359   recursion_level--;
 360
 361   /* Break the recusive unwind here... */
 362   if (rv == VLIB_PARSE_MATCH_RULE)
 363     {
 364       if (PARSE_DEBUG > 1)
 365         clib_warning ("[%d]: type %s matched", recursion_level, type->name);
 366
 367       return VLIB_PARSE_MATCH_FULL;
 368     }
 369   else
 370     {
 371       if (PARSE_DEBUG > 1)
 372         clib_warning ("[%d]: type %s returns %U", recursion_level, type->name,
 373                       format_vlib_parse_match, rv);
 374     }
 375   return rv;
 376 }
 377
 378 static int parse_eval (vlib_parse_main_t *pm, u8 *input)
 379 {
 380   vlib_lex_token_t * t;
 381
 382   parse_reset (pm, input);
 383
 384   /* Tokenize the entire input vector */
 385   do {
 386     vec_add2 (pm->tokens, t, 1);
 387     vlib_lex_get_token (pm->lex_main, t);
 388   } while (t->token != VLIB_LEX_eof);
 389
 390   /* Feed it to the parser */
 391   return parse_eval_internal (pm, pm->root_index);
 392 }
 393
 394 /* Temporary vlib stub */
 395 vlib_parse_match_t vlib_parse_eval (u8 *input)
 396 {
 397   return parse_eval (&vlib_parse_main, input);
 398 }
 399
 400 u16 parse_type_find_or_create (vlib_parse_main_t *pm, vlib_parse_type_t *t)
 401 {
 402   uword *p;
 403   vlib_parse_type_t *n;
 404   u8 *name_copy;
 405
 406   p = hash_get_mem (pm->parse_type_by_name_hash, t->name);
 407   if (p)
 408     return p[0];
 409
 410   pool_get (pm->parse_types, n);
 411   *n = *t;
 412   n->rule_index = (u32) ~0;
 413
 414   name_copy = format (0, "%s%c", n->name, 0);
 415
 416   hash_set_mem (pm->parse_type_by_name_hash, name_copy, n - pm->parse_types);
 417   return n - pm->parse_types;
 418 }
 419
 420 u16 parse_type_find_by_name (vlib_parse_main_t *pm, char *name)
 421 {
 422   uword *p;
 423
 424   p = hash_get_mem (pm->parse_type_by_name_hash, name);
 425   if (p)
 426     return p[0];
 427
 428   return (u16) ~0;
 429 }
 430
 431 u32 parse_item_find_or_create (vlib_parse_main_t *pm, vlib_parse_item_t *item)
 432
 433 {
 434   uword *p;
 435   vlib_parse_item_t *i;
 436
 437   /* Exact match the entire item */
 438   p = mhash_get (&pm->parse_item_hash, item);
 439   if (p)
 440     return p[0];
 441
 442   pool_get (pm->parse_items, i);
 443   *i = *item;
 444
 445   mhash_set (&pm->parse_item_hash, i, i - pm->parse_items, 0);
 446   return i - pm->parse_items;
 447 }
 448
 449 static void parse_type_and_graph_init (vlib_parse_main_t *pm)
 450 {
 451   u32 eof_index;
 452   vlib_parse_type_t type;
 453   vlib_parse_item_t item;
 454
 455   memset (&type, 0, sizeof (type));
 456
 457 #define foreach_token_type                      \
 458   _ (eof)                                       \
 459   _ (rule_eof)                                  \
 460   _ (word)                                      \
 461   _ (number)                                    \
 462   _ (plus)                                      \
 463   _ (minus)                                     \
 464   _ (star)                                      \
 465   _ (slash)                                     \
 466   _ (lpar)                                      \
 467   _ (rpar)
 468
 469 #define _(a) a##_type_index = parse_type_find_by_name (pm, #a);
 470     foreach_token_type
 471 #undef _
 472
 473   memset (&item, 0, sizeof (item));
 474   item.type = eof_type_index;
 475
 476   eof_index = parse_item_find_or_create (pm, &item);
 477   pm->root_index = (u32)~0;
 478
 479 #if 0
 480   pool_get (pm->parse_graph, g);
 481   memset (g, 0xff, sizeof (*g));
 482   g->item = eof_index;
 483   pm->root_index = 0;
 484 #endif
 485 }
 486
 487
 488
 489 static void tokenize (vlib_parse_main_t *pm, parse_registration_t *pr)
 490 {
 491   vlib_lex_token_t *t;
 492   pm->register_input = format (pm->register_input,
 493                                "%s%c", pr->initializer, 0);
 494
 495   parse_reset (pm, pm->register_input);
 496
 497   do {
 498     vec_add2 (pm->tokens, t, 1);
 499     vlib_lex_get_token (pm->lex_main, t);
 500   } while (t->token != VLIB_LEX_eof);
 501   _vec_len (pm->register_input) = 0;
 502 }
 503
 504 static int is_typed_rule (vlib_parse_main_t *pm)
 505 {
 506   vlib_lex_token_t *t = vec_elt_at_index (pm->tokens, 0);
 507
 508   /* <mytype> = blah blah blah */
 509   if (vec_len(pm->tokens) >= 4
 510       && t[0].token == VLIB_LEX_lt
 511       && t[1].token == VLIB_LEX_word
 512       && t[2].token == VLIB_LEX_gt
 513       && t[3].token == VLIB_LEX_equals)
 514     return 1;
 515   return 0;
 516 }
 517
 518 static int token_matches_graph_node (vlib_parse_main_t *pm,
 519                                      vlib_lex_token_t *t,
 520                                      vlib_parse_graph_t *node,
 521                                      vlib_parse_item_t *item,
 522                                      vlib_parse_type_t *type,
 523                                      u32 *token_increment)
 524 {
 525   /* EOFs don't match */
 526   if (t->token == VLIB_LEX_eof)
 527     return 0;
 528
 529   /* New chain element is a word */
 530   if (t->token == VLIB_LEX_word)
 531     {
 532       /* but the item in hand is not a word */
 533       if (item->type != word_type_index)
 534         return 0;
 535
 536       /* Or it's not this particular word */
 537       if (strcmp (t->value.as_pointer, item->value.as_pointer))
 538         return 0;
 539       *token_increment = 1;
 540       return 1;
 541     }
 542   /* New chain element is a type-name: < TYPE-NAME > */
 543   if (t->token == VLIB_LEX_lt)
 544     {
 545       u16 token_type_index;
 546
 547       /* < TYPE > */
 548       if (t[1].token != VLIB_LEX_word ||
 549           t[2].token != VLIB_LEX_gt)
 550         {
 551           clib_warning (0, "broken type name in '%s'", pm->register_input);
 552           return 0;
 553         }
 554
 555       token_type_index = parse_type_find_by_name (pm, t[1].value.as_pointer);
 556       if (token_type_index == (u16)~0)
 557         {
 558           clib_warning (0, "unknown type '%s'", t[1].value.as_pointer);
 559           return 0;
 560         }
 561
 562       /* Its a known type but does not match. */
 563       if (item->type != token_type_index)
 564         return 0;
 565
 566       *token_increment = 3;
 567       return 1;
 568     }
 569   clib_warning ("BUG: t->token = %d", t->token);
 570   return 0;
 571 }
 572
 573 u32 generate_subgraph_from_tokens (vlib_parse_main_t *pm,
 574                                    vlib_lex_token_t *t,
 575                                    u32 *new_subgraph_depth,
 576                                    parse_registration_t *pr,
 577                                    int not_a_rule)
 578 {
 579   vlib_parse_graph_t *g, *last_g;
 580   vlib_parse_item_t new_item;
 581   u32 rv = (u32)~0, new_item_index, last_index = (u32)~0;
 582   u16 token_type_index;
 583   u32 depth = 0;
 584
 585   while (t < pm->tokens + vec_len (pm->tokens))
 586     {
 587       memset (&new_item, 0, sizeof (new_item));
 588
 589       if (t->token == VLIB_LEX_word)
 590         {
 591           new_item.type = word_type_index;
 592           new_item.value.as_pointer = vec_dup ((u8 *) t->value.as_pointer);
 593           new_item_index = parse_item_find_or_create (pm, &new_item);
 594           t++;
 595         }
 596       else if (t->token == VLIB_LEX_lt)
 597         {
 598           if (t[1].token != VLIB_LEX_word ||
 599               t[2].token != VLIB_LEX_gt)
 600             {
 601               clib_warning ("broken type name in '%s'", pm->register_input);
 602               goto screwed;
 603             }
 604           token_type_index = parse_type_find_by_name (pm,
 605                                                       t[1].value.as_pointer);
 606           if (token_type_index == (u16)~0)
 607             {
 608               clib_warning ("unknown type 2 '%s'", t[1].value.as_pointer);
 609               goto screwed;
 610             }
 611
 612           new_item.type = token_type_index;
 613           new_item.value.as_pointer = 0;
 614           new_item_index = parse_item_find_or_create (pm, &new_item);
 615           t += 3; /* skip < <type-name> and > */
 616         }
 617       else if (t->token == VLIB_LEX_eof)
 618         {
 619         screwed:
 620           new_item.type = not_a_rule ? eof_type_index : rule_eof_type_index;
 621           new_item.value.as_pointer = pr->eof_match;
 622           new_item_index = parse_item_find_or_create (pm, &new_item);
 623           t++;
 624         }
 625       else
 626         {
 627           clib_warning ("unexpected token %U index %d in '%s'",
 628                         format_vlib_lex_token, pm->lex_main, t,
 629                         t - pm->tokens, pm->register_input);
 630           goto screwed;
 631         }
 632
 633       pool_get (pm->parse_graph, g);
 634       memset (g, 0xff, sizeof (*g));
 635       g->item = new_item_index;
 636       depth++;
 637
 638       if (rv == (u32)~0)
 639         {
 640           rv = g - pm->parse_graph;
 641           last_index = rv;
 642         }
 643       else
 644         {
 645           last_g = pool_elt_at_index (pm->parse_graph, last_index);
 646           last_index = last_g->deeper = g - pm->parse_graph;
 647         }
 648     }
 649   *new_subgraph_depth = depth;
 650   return rv;
 651 }
 652
 653 static u32 measure_depth (vlib_parse_main_t *pm, u32 index)
 654 {
 655   vlib_parse_graph_t *node;
 656   vlib_parse_item_t *item;
 657   u32 max=0;
 658   u32 depth;
 659
 660   if (index == (u32)~0)
 661     return 0;
 662
 663   node = pool_elt_at_index (pm->parse_graph, index);
 664   item = pool_elt_at_index (pm->parse_items, node->item);
 665
 666   if (item->type == eof_type_index)
 667     return 1;
 668
 669   while (index != (u32)~0)
 670     {
 671       node = pool_elt_at_index (pm->parse_graph, index);
 672       depth = measure_depth (pm, node->deeper);
 673       if (max < depth)
 674         max = depth;
 675       index = node->peer;
 676     }
 677
 678   return max + 1;
 679 }
 680
 681 static void add_subgraph_to_graph (vlib_parse_main_t *pm,
 682                                    u32 last_matching_index,
 683                                    u32 graph_root_index,
 684                                    u32 new_subgraph_index,
 685                                    u32 new_subgraph_depth)
 686 {
 687   vlib_parse_graph_t *parent_node;
 688   int new_subgraph_longest = 1;
 689   u32 current_peer_index;
 690   u32 current_depth;
 691   vlib_parse_graph_t *current_peer = 0;
 692   vlib_parse_graph_t *new_subgraph_node =
 693     pool_elt_at_index (pm->parse_graph, new_subgraph_index);
 694
 695   /*
 696    * Case 1: top-level peer. Splice into the top-level
 697    * peer chain according to rule depth
 698    */
 699   if (last_matching_index == (u32)~0)
 700     {
 701       u32 index = graph_root_index;
 702       while (1) {
 703         current_peer = pool_elt_at_index (pm->parse_graph, index);
 704         current_depth = measure_depth (pm, index);
 705         if (current_depth < new_subgraph_depth
 706             || current_peer->peer == (u32)~0)
 707           break;
 708         index = current_peer->peer;
 709       }
 710       new_subgraph_node->peer = current_peer->peer;
 711       current_peer->peer = new_subgraph_index;
 712       return;
 713     }
 714
 715   parent_node = pool_elt_at_index (pm->parse_graph, last_matching_index);
 716   current_peer_index = parent_node->deeper;
 717
 718   while (current_peer_index != (u32)~0)
 719     {
 720       current_peer = pool_elt_at_index (pm->parse_graph, current_peer_index);
 721       current_depth = measure_depth (pm, current_peer_index);
 722       if (current_depth < new_subgraph_depth)
 723         break;
 724       new_subgraph_longest = 0;
 725       current_peer_index = current_peer->peer;
 726     }
 727
 728   ASSERT (current_peer);
 729
 730   if (new_subgraph_longest)
 731     {
 732       new_subgraph_node->peer = parent_node->deeper;
 733       parent_node->deeper = new_subgraph_index;
 734     }
 735   else
 736     {
 737       new_subgraph_node->peer = current_peer->peer;
 738       current_peer->peer = new_subgraph_index;
 739     }
 740 }
 741
 742 static clib_error_t *
 743 parse_register_one (vlib_parse_main_t *pm, parse_registration_t *pr)
 744 {
 745   u32 graph_root_index;
 746   u16 subgraph_type_index = (u16)~0;
 747   vlib_parse_type_t *subgraph_type = 0;
 748   vlib_lex_token_t *t;
 749   vlib_parse_graph_t *node;
 750   u32 node_index, last_index, token_increment, new_subgraph_index;
 751   u32 new_subgraph_depth, last_matching_index;
 752   vlib_parse_item_t *item;
 753   vlib_parse_type_t *type;
 754
 755   int use_main_graph = 1;
 756
 757   tokenize (pm, pr);
 758
 759   /* A typed rule? */
 760   if (is_typed_rule (pm))
 761     {
 762       /* Get the type and its current subgraph root, if any */
 763       t = vec_elt_at_index (pm->tokens, 1);
 764       subgraph_type_index = parse_type_find_by_name (pm, t->value.as_pointer);
 765       if (subgraph_type_index == (u16)~0)
 766         return clib_error_return (0, "undeclared type '%s'",
 767                                   t->value.as_pointer);
 768       subgraph_type = pool_elt_at_index (pm->parse_types, subgraph_type_index);
 769       graph_root_index = subgraph_type->rule_index;
 770       /* Skip "mytype> = */
 771       t += 3;
 772       use_main_graph = 0;
 773   }
 774   else
 775     {
 776       /* top-level graph */
 777       graph_root_index = pm->root_index;
 778       t = vec_elt_at_index (pm->tokens, 0);
 779     }
 780
 781   last_matching_index = (u32)~0;
 782   last_index = node_index = graph_root_index;
 783
 784   /* Find the first token which isn't already being parsed */
 785   while (t < pm->tokens + vec_len (pm->tokens) && node_index != (u32) ~0)
 786     {
 787       node = pool_elt_at_index (pm->parse_graph, node_index);
 788       item = pool_elt_at_index (pm->parse_items, node->item);
 789       type = pool_elt_at_index (pm->parse_types, item->type);
 790       last_index = node_index;
 791
 792       if (token_matches_graph_node (pm, t, node, item, type, &token_increment))
 793         {
 794           t += token_increment;
 795           last_matching_index = node_index;
 796           node_index = node->deeper;
 797         }
 798       else
 799         node_index = node->peer;
 800     }
 801
 802   new_subgraph_index =
 803     generate_subgraph_from_tokens (pm, t, &new_subgraph_depth, pr,
 804                                    use_main_graph);
 805
 806   /* trivial cases: first graph node or first type rule */
 807   if (graph_root_index == (u32)~0)
 808     {
 809       if (use_main_graph)
 810         pm->root_index = new_subgraph_index;
 811       else
 812         subgraph_type->rule_index = new_subgraph_index;
 813       return 0;
 814     }
 815
 816   add_subgraph_to_graph (pm, last_matching_index, graph_root_index,
 817                          new_subgraph_index,
 818                          new_subgraph_depth);
 819   return 0;
 820 }
 821
 822 static clib_error_t *
 823 parse_register (vlib_main_t * vm,
 824                 parse_registration_t * lo,
 825                 parse_registration_t * hi,
 826                 vlib_parse_main_t *pm)
 827 {
 828   parse_registration_t * pr;
 829
 830   for (pr = lo; pr < hi; pr = vlib_elf_section_data_next (pr, 0))
 831     vec_add1 (pm->parse_registrations, pr);
 832
 833   return 0;
 834 }
 835
 836 static clib_error_t *
 837 parse_register_one_type (vlib_parse_main_t *pm, vlib_parse_type_t *rp)
 838 {
 839   (void) parse_type_find_or_create (pm, (vlib_parse_type_t *)rp);
 840   return 0;
 841 }
 842
 843 static clib_error_t *
 844 parse_type_register (vlib_main_t * vm,
 845                      vlib_parse_type_t * lo,
 846                      vlib_parse_type_t * hi,
 847                      vlib_parse_main_t *pm)
 848 {
 849   clib_error_t * error = 0;
 850   vlib_parse_type_t * ptr;
 851
 852   for (ptr = lo; ptr < hi; ptr = vlib_elf_section_data_next (ptr, 0)) {
 853     error = parse_register_one_type (pm, ptr);
 854     if (error)
 855       goto done;
 856   }
 857
 858  done:
 859   return error;
 860 }
 861
 862 clib_error_t *vlib_stdlex_init (vlib_main_t *vm) __attribute__((weak));
 863 clib_error_t *vlib_stdlex_init (vlib_main_t *vm)
 864 {
 865   (void) vlib_lex_add_table ("ignore_everything");
 866   return 0;
 867 }
 868
 869 static int compute_rule_length (parse_registration_t *r)
 870 {
 871   int length, i;
 872   vlib_parse_main_t *pm = &vlib_parse_main;
 873
 874   if (r->rule_length)
 875     return r->rule_length;
 876
 877   length = 0;
 878
 879   tokenize (pm, r);
 880   length = vec_len (pm->tokens);
 881
 882   /* Account for "<foo> = " in "<foo> = bar" etc. */
 883   if (is_typed_rule (pm))
 884     length -= 2;
 885
 886   for (i = 0; i < vec_len (pm->tokens); i++)
 887     {
 888       switch (pm->tokens[i].token)
 889         {
 890         case VLIB_LEX_lt:
 891         case VLIB_LEX_gt:
 892           length -= 1;
 893
 894         default:
 895           break;
 896         }
 897     }
 898
 899   ASSERT (length > 0);
 900   r->rule_length = length;
 901   return length;
 902 }
 903
 904 static int rule_length_compare (parse_registration_t *r1,
 905                                 parse_registration_t *r2)
 906 {
 907   compute_rule_length (r1);
 908   compute_rule_length (r2);
 909   /* Descending sort */
 910   return r2->rule_length - r1->rule_length;
 911 }
 912
 913
 914 static clib_error_t * parse_init (vlib_main_t *vm)
 915 {
 916   vlib_parse_main_t *pm = &vlib_parse_main;
 917   vlib_lex_main_t *lm = &vlib_lex_main;
 918   vlib_elf_section_bounds_t * b, * bounds;
 919   clib_error_t * error = 0;
 920   parse_registration_t *rule;
 921   int i;
 922
 923   if ((error = vlib_call_init_function (vm, lex_onetime_init)))
 924     return error;
 925
 926   if ((error = vlib_stdlex_init(vm)))
 927     return error;
 928
 929   if ((error = vlib_call_init_function (vm, parse_builtin_init)))
 930     return error;
 931
 932   pm->vlib_main = vm;
 933   pm->lex_main = lm;
 934
 935   mhash_init (&pm->parse_item_hash, sizeof (u32), sizeof (vlib_parse_item_t));
 936   pm->parse_type_by_name_hash = hash_create_string (0, sizeof (u32));
 937
 938   vec_validate (pm->parse_value, 16);
 939   vec_validate (pm->tokens, 16);
 940   vec_validate (pm->register_input, 32);
 941   vec_validate (pm->match_items, 16);
 942
 943   _vec_len (pm->parse_value) = 0;
 944   _vec_len (pm->tokens) = 0;
 945   _vec_len (pm->register_input) = 0;
 946   _vec_len (pm->match_items) = 0;
 947
 948   bounds = vlib_get_elf_section_bounds (vm, "parse_type_registrations");
 949   vec_foreach (b, bounds)
 950     {
 951       error = parse_type_register (vm, b->lo, b->hi, pm);
 952       if (error)
 953         break;
 954     }
 955   vec_free (bounds);
 956
 957   parse_type_and_graph_init (pm);
 958
 959   bounds = vlib_get_elf_section_bounds (vm, "parse_registrations");
 960   vec_foreach (b, bounds)
 961     {
 962       error = parse_register (vm, b->lo, b->hi, pm);
 963       if (error)
 964         break;
 965     }
 966   vec_free (bounds);
 967
 968   vec_sort (pm->parse_registrations, r1, r2,
 969             rule_length_compare (r1[0], r2[0]));
 970
 971   for (i = 0; i < vec_len (pm->parse_registrations); i++)
 972     {
 973       rule = pm->parse_registrations[i];
 974       parse_register_one (pm, rule);
 975     }
 976
 977   return error;
 978 }
 979
 980 VLIB_INIT_FUNCTION (parse_init);