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