lib/command_match.c

   1 #include "command_match.h"
   2 #include "command_parse.h"
   3 #include <zebra.h>
   4 #include "memory.h"
   5
   6 /* matcher helper prototypes */
   7 static int
   8 add_nexthops(struct list *, struct graph_node *);
   9
  10 static struct list *
  11 match_command_r (struct graph_node *, vector, unsigned int);
  12
  13 static int
  14 score_precedence (enum graph_node_type);
  15
  16 static enum match_type
  17 min_match_level(enum node_type);
  18
  19 static struct graph_node *
  20 copy_node (struct graph_node *);
  21
  22 static void
  23 delete_nodelist (void *);
  24
  25 static struct graph_node *
  26 disambiguate (struct graph_node *, struct graph_node *, char *);
  27
  28 static struct list *
  29 disambiguate_nodelist (struct list *, struct list *, vector, unsigned int);
  30
  31 /* token matcher prototypes */
  32 static enum match_type
  33 match_token (struct graph_node *, char *);
  34
  35 static enum match_type
  36 match_ipv4 (const char *);
  37
  38 static enum match_type
  39 match_ipv4_prefix (const char *);
  40
  41 static enum match_type
  42 match_ipv6 (const char *);
  43
  44 static enum match_type
  45 match_ipv6_prefix (const char *);
  46
  47 static enum match_type
  48 match_range (struct graph_node *, const char *);
  49
  50 static enum match_type
  51 match_word (struct graph_node *, const char *);
  52
  53 static enum match_type
  54 match_number (struct graph_node *, const char *);
  55
  56 static enum match_type
  57 match_variable (struct graph_node *, const char *);
  58
  59 /* matching functions */
  60 static enum matcher_rv matcher_result_value;
  61
  62 enum matcher_rv
  63 match_command (struct graph_node *start,
  64                const char *line,
  65                struct list **argvv,
  66                struct cmd_element **el)
  67 {
  68   matcher_result_value = MATCHER_NO_MATCH;
  69   // parse command
  70   vector vline = cmd_make_strvec (line);
  71
  72   for (unsigned int i = 0; i < vector_active(start->children); i++)
  73   {
  74     // call recursive matcher on each starting child
  75     *argvv = match_command_r(vector_slot(start->children, i), vline, 0);
  76     if (*argvv) break;
  77   }
  78
  79   if (*argvv) {
  80     struct listnode *ln;
  81     struct graph_node *gn;
  82     for (ALL_LIST_ELEMENTS_RO(*argvv,ln,gn))
  83       if (gn->type == END_GN) {
  84         *el = gn->element;
  85         break;
  86       }
  87     assert(*el);
  88   }
  89
  90   return matcher_result_value;
  91 }
  92
  93 /**
  94  * Builds an argument list given a DFA and a matching input line.
  95  *
  96  * First the function determines if the node it is passed matches the first
  97  * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
  98  * does match, then it saves the input token as the head of an argument list.
  99  *
 100  * The next step is to see if there is further input in the input line. If
 101  * there is not, the current node's children are searched to see if any of them
 102  * are leaves (type END_GN). If this is the case, then the bottom of the
 103  * recursion stack has been reached, the leaf is pushed onto the argument list,
 104  * the current node is pushed, and the resulting argument list is
 105  * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
 106  * that there is no match for the input along this path (MATCHER_INCOMPLETE).
 107  *
 108  * If there is further input, then the function recurses on each of the current
 109  * node's children, passing them the input line minus the token that was just
 110  * matched. For each child, the return value of the recursive call is
 111  * inspected. If it is null, then there is no match for the input along the
 112  * subgraph headed by that child. If it is not null, then there is at least one
 113  * input match in that subgraph (more on this in a moment).
 114  *
 115  * If a recursive call on a child returns a non-null value, then it has matched
 116  * the input given it on the subgraph that starts with that child. However, due
 117  * to the flexibility of the grammar, it is sometimes the case that two or more
 118  * child graphs match the same input (two or more of the recursive calls have
 119  * non-NULL return values). This is not a valid state, since only one true
 120  * match is possible. In order to resolve this conflict, the function keeps a
 121  * reference to the child node that most specifically matches the input. This
 122  * is done by assigning each node type a precedence. If a child is found to
 123  * match the remaining input, then the precedence values of the current
 124  * best-matching child and this new match are compared. The node with higher
 125  * precedence is kept, and the other match is discarded. Due to the recursive
 126  * nature of this function, it is only necessary to compare the precedence of
 127  * immediate children, since all subsequent children will already have been
 128  * disambiguated in this way.
 129  *
 130  * In the event that two children are found to match with the same precedence,
 131  * then the input is ambiguous for the passed cmd_element and NULL is returned.
 132  *
 133  * The ultimate return value is an ordered linked list of nodes that comprise
 134  * the best match for the command, each with their `arg` fields pointing to the
 135  * matching token string.
 136  *
 137  * @param[out] start the start node.
 138  * @param[in] vline the vectorized input line.
 139  * @param[in] n the index of the first input token. Should be 0 for external
 140  * callers.
 141  */
 142 static struct list *
 143 match_command_r (struct graph_node *start, vector vline, unsigned int n)
 144 {
 145   // get the minimum match level that can count as a full match
 146   enum match_type minmatch = min_match_level(start->type);
 147
 148   // get the current operating token
 149   char *token = vector_slot(vline, n);
 150
 151   // if we don't match this node, die
 152   if (match_token(start, token) < minmatch)
 153     return NULL;
 154
 155   // pointers for iterating linklist
 156   struct graph_node *gn;
 157   struct listnode   *ln;
 158
 159   // get all possible nexthops
 160   struct list *next = list_new();
 161   add_nexthops(next, start);
 162
 163   // determine the best match
 164   int ambiguous = 0;
 165   struct list *currbest = NULL;
 166   for (ALL_LIST_ELEMENTS_RO(next,ln,gn))
 167   {
 168     // if we've matched all input we're looking for END_GN
 169     if (n+1 == vector_active (vline)) {
 170       if (gn->type == END_GN) {
 171         currbest = list_new();
 172         listnode_add(currbest, copy_node(gn));
 173         currbest->del = &delete_nodelist;
 174         break;
 175       }
 176       else continue;
 177     }
 178
 179     // else recurse on candidate child node
 180     struct list *result = match_command_r (gn, vline, n+1);
 181
 182     // save the best match, subtle logic at play here
 183     if (result && currbest) {
 184       struct list *newbest = disambiguate_nodelist(currbest, result, vline, n+1);
 185       ambiguous = !newbest || (ambiguous && newbest == currbest);
 186       list_delete ((newbest && newbest == result) ? currbest : result);
 187       currbest = newbest ? newbest : currbest;
 188     }
 189     else if (result)
 190       currbest = result;
 191   }
 192
 193   if (currbest) {
 194     if (ambiguous) {
 195       list_delete(currbest);
 196       currbest = NULL;
 197       matcher_result_value = MATCHER_AMBIGUOUS;
 198     }
 199     else {
 200       // copy current node, set arg and prepend to currbest
 201       struct graph_node *curr = copy_node(start);
 202       curr->arg = XSTRDUP(MTYPE_CMD_TOKENS, token);
 203       list_add_node_prev (currbest, currbest->head, curr);
 204       matcher_result_value = MATCHER_OK;
 205     }
 206   }
 207   else {
 208     if (n+1 == vector_active(vline) && matcher_result_value == MATCHER_NO_MATCH)
 209       matcher_result_value = MATCHER_INCOMPLETE;
 210   }
 211
 212   // cleanup
 213   list_delete (next);
 214
 215   return currbest;
 216 }
 217
 218 struct list *
 219 match_command_complete (struct graph_node *start, const char *line)
 220 {
 221   // vectorize command line
 222   vector vline = cmd_make_strvec (line);
 223
 224   // pointer to next input token to match
 225   char *token;
 226
 227   struct list *current = list_new(), // current nodes to match input token against
 228                  *next = list_new(); // possible next hops after current input token
 229
 230   // pointers used for iterating lists
 231   struct graph_node *gn;
 232   struct listnode *node;
 233
 234   // add all children of start node to list
 235   add_nexthops(next, start);
 236
 237   unsigned int idx;
 238   for (idx = 0; idx < vector_active(vline) && next->count > 0; idx++)
 239   {
 240     list_free (current);
 241     current = next;
 242     next = list_new();
 243
 244     token = vector_slot(vline, idx);
 245
 246     for (ALL_LIST_ELEMENTS_RO(current,node,gn))
 247     {
 248       switch (match_token(gn, token)) {
 249         case partly_match:
 250           if (idx == vector_active(vline) - 1) {
 251             listnode_add(next, gn);
 252             break;
 253           }
 254         case exact_match:
 255           add_nexthops(next, gn);
 256           break;
 257         default:
 258           break;
 259       }
 260     }
 261   }
 262
 263   /* Variable summary
 264    * -----------------------------------------------------------------
 265    * token    = last input token processed
 266    * idx      = index in `command` of last token processed
 267    * current  = set of all transitions from the previous input token
 268    * next     = set of all nodes reachable from all nodes in `matched`
 269    */
 270
 271   matcher_result_value =
 272      idx + 1 == vector_active(vline) && next->count ?
 273      MATCHER_OK :
 274      MATCHER_NO_MATCH;
 275
 276   list_free (current);
 277   cmd_free_strvec(vline);
 278
 279   return next;
 280 }
 281
 282 /**
 283  * Adds all children that are reachable by one parser hop
 284  * to the given list. NUL_GN, SELECTOR_GN, and OPTION_GN
 285  * nodes are treated as transparent.
 286  *
 287  * @param[out] l the list to add the children to
 288  * @param[in] node the node to get the children of
 289  * @return the number of children added to the list
 290  */
 291 static int
 292 add_nexthops(struct list *l, struct graph_node *node)
 293 {
 294   int added = 0;
 295   struct graph_node *child;
 296   for (unsigned int i = 0; i < vector_active(node->children); i++)
 297   {
 298     child = vector_slot(node->children, i);
 299     switch (child->type) {
 300       case OPTION_GN:
 301       case SELECTOR_GN:
 302       case NUL_GN:
 303         added += add_nexthops(l, child);
 304         break;
 305       default:
 306         listnode_add(l, child);
 307         added++;
 308     }
 309   }
 310   return added;
 311 }
 312
 313 /**
 314  * Determines the node types for which a partial match may count as a full
 315  * match. Enables command abbrevations.
 316  */
 317 static enum match_type
 318 min_match_level(enum node_type type)
 319 {
 320   switch (type) {
 321     case WORD_GN:
 322       return partly_match;
 323     default:
 324       return exact_match;
 325   }
 326 }
 327
 328 /* Precedence score used to disambiguate matches. */
 329 static int
 330 score_precedence (enum graph_node_type type)
 331 {
 332   switch (type)
 333   {
 334     // some of these are mutually exclusive, so they share
 335     // the same precedence value
 336     case IPV4_GN:
 337     case IPV4_PREFIX_GN:
 338     case IPV6_GN:
 339     case IPV6_PREFIX_GN:
 340     case NUMBER_GN:
 341       return 1;
 342     case RANGE_GN:
 343       return 2;
 344     case WORD_GN:
 345       return 3;
 346     case VARIABLE_GN:
 347       return 4;
 348     default:
 349       return 10;
 350   }
 351 }
 352
 353 /* Disambiguation logic to pick the best of two possible matches */
 354 static struct graph_node *
 355 disambiguate (struct graph_node *first, struct graph_node *second, char *token)
 356 {
 357   // if the types are different, simply go off of type precedence
 358   if (first->type != second->type) {
 359     int firstprec = score_precedence(first->type);
 360     int secndprec = score_precedence(second->type);
 361     if (firstprec != secndprec)
 362       return firstprec < secndprec ? first : second;
 363     else
 364       return NULL;
 365   }
 366
 367   // if they're the same, return the more exact match
 368   enum match_type fmtype = match_token (first, token);
 369   enum match_type smtype = match_token (second, token);
 370   if (fmtype != smtype)
 371     return fmtype > smtype ? first : second;
 372
 373   return NULL;
 374 }
 375
 376 static struct list *
 377 disambiguate_nodelist (struct list *first, struct list *second, vector vline, unsigned int n)
 378 {
 379   fprintf(stderr, "%d --- %d\n", first->count, n);
 380
 381   // doesn't make sense for these to be inequal length
 382   assert(first->count == second->count);
 383   assert(first->count == vector_active(vline) - n+1);
 384
 385   struct listnode *fnode = listhead(first),
 386                   *snode = listhead(second);
 387   struct graph_node *fgn = listgetdata(fnode),
 388                     *sgn = listgetdata(snode),
 389                     *best = NULL;
 390
 391   // compare each node, if one matches better use that one
 392   for (unsigned int i = n; i < vector_active(vline); i++) {
 393     if ((best = disambiguate (fgn, sgn, (char*) vector_slot(vline, i))))
 394       return best == fgn ? first : second;
 395     fnode = listnextnode(fnode);
 396     fgn = (struct graph_node *) listgetdata (fnode);
 397     snode = listnextnode(snode);
 398     sgn = (struct graph_node *) listgetdata (snode);
 399   }
 400
 401   return NULL;
 402 }
 403
 404 static struct graph_node *
 405 copy_node (struct graph_node *node)
 406 {
 407   struct graph_node *new = new_node(node->type);
 408   new->children = NULL;
 409   new->is_start = node->is_start;
 410   new->end      = NULL;
 411   new->text     = node->text ? XSTRDUP(MTYPE_CMD_TOKENS, node->text) : NULL;
 412   new->value    = node->value;
 413   new->min      = node->min;
 414   new->max      = node->max;
 415   new->element  = node->element ? copy_cmd_element(node->element) : NULL;
 416   new->arg      = node->arg ? XSTRDUP(MTYPE_CMD_TOKENS, node->arg) : NULL;
 417   new->refs     = 0;
 418   return new;
 419 }
 420
 421 /* Linked list data deletion callback */
 422 static void
 423 delete_nodelist (void *node)
 424 {
 425   free_node ((struct graph_node *) node);
 426 }
 427
 428
 429 /* token level matching functions */
 430
 431 static enum match_type
 432 match_token (struct graph_node *node, char *token)
 433 {
 434   switch (node->type) {
 435     case WORD_GN:
 436       return match_word (node, token);
 437     case IPV4_GN:
 438       return match_ipv4 (token);
 439     case IPV4_PREFIX_GN:
 440       return match_ipv4_prefix (token);
 441     case IPV6_GN:
 442       return match_ipv6 (token);
 443     case IPV6_PREFIX_GN:
 444       return match_ipv6_prefix (token);
 445     case RANGE_GN:
 446       return match_range (node, token);
 447     case NUMBER_GN:
 448       return match_number (node, token);
 449     case VARIABLE_GN:
 450       return match_variable (node, token);
 451     case END_GN:
 452     default:
 453       return no_match;
 454   }
 455 }
 456
 457 #define IPV4_ADDR_STR   "0123456789."
 458 #define IPV4_PREFIX_STR "0123456789./"
 459
 460 static enum match_type
 461 match_ipv4 (const char *str)
 462 {
 463   const char *sp;
 464   int dots = 0, nums = 0;
 465   char buf[4];
 466
 467   if (str == NULL)
 468     return partly_match;
 469
 470   for (;;)
 471     {
 472       memset (buf, 0, sizeof (buf));
 473       sp = str;
 474       while (*str != '\0')
 475         {
 476           if (*str == '.')
 477             {
 478               if (dots >= 3)
 479                 return no_match;
 480
 481               if (*(str + 1) == '.')
 482                 return no_match;
 483
 484               if (*(str + 1) == '\0')
 485                 return partly_match;
 486
 487               dots++;
 488               break;
 489             }
 490           if (!isdigit ((int) *str))
 491             return no_match;
 492
 493           str++;
 494         }
 495
 496       if (str - sp > 3)
 497         return no_match;
 498
 499       strncpy (buf, sp, str - sp);
 500       if (atoi (buf) > 255)
 501         return no_match;
 502
 503       nums++;
 504
 505       if (*str == '\0')
 506         break;
 507
 508       str++;
 509     }
 510
 511   if (nums < 4)
 512     return partly_match;
 513
 514   return exact_match;
 515 }
 516
 517 static enum match_type
 518 match_ipv4_prefix (const char *str)
 519 {
 520   const char *sp;
 521   int dots = 0;
 522   char buf[4];
 523
 524   if (str == NULL)
 525     return partly_match;
 526
 527   for (;;)
 528     {
 529       memset (buf, 0, sizeof (buf));
 530       sp = str;
 531       while (*str != '\0' && *str != '/')
 532         {
 533           if (*str == '.')
 534             {
 535               if (dots == 3)
 536                 return no_match;
 537
 538               if (*(str + 1) == '.' || *(str + 1) == '/')
 539                 return no_match;
 540
 541               if (*(str + 1) == '\0')
 542                 return partly_match;
 543
 544               dots++;
 545               break;
 546             }
 547
 548           if (!isdigit ((int) *str))
 549             return no_match;
 550
 551           str++;
 552         }
 553
 554       if (str - sp > 3)
 555         return no_match;
 556
 557       strncpy (buf, sp, str - sp);
 558       if (atoi (buf) > 255)
 559         return no_match;
 560
 561       if (dots == 3)
 562         {
 563           if (*str == '/')
 564             {
 565               if (*(str + 1) == '\0')
 566                 return partly_match;
 567
 568               str++;
 569               break;
 570             }
 571           else if (*str == '\0')
 572             return partly_match;
 573         }
 574
 575       if (*str == '\0')
 576         return partly_match;
 577
 578       str++;
 579     }
 580
 581   sp = str;
 582   while (*str != '\0')
 583     {
 584       if (!isdigit ((int) *str))
 585         return no_match;
 586
 587       str++;
 588     }
 589
 590   if (atoi (sp) > 32)
 591     return no_match;
 592
 593   return exact_match;
 594 }
 595
 596 #ifdef HAVE_IPV6
 597 #define IPV6_ADDR_STR   "0123456789abcdefABCDEF:."
 598 #define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
 599
 600 static enum match_type
 601 match_ipv6 (const char *str)
 602 {
 603   struct sockaddr_in6 sin6_dummy;
 604   int ret;
 605
 606   if (str == NULL)
 607     return partly_match;
 608
 609   if (strspn (str, IPV6_ADDR_STR) != strlen (str))
 610     return no_match;
 611
 612   ret = inet_pton(AF_INET6, str, &sin6_dummy.sin6_addr);
 613
 614   if (ret == 1)
 615     return exact_match;
 616
 617   return no_match;
 618 }
 619
 620 static enum match_type
 621 match_ipv6_prefix (const char *str)
 622 {
 623   struct sockaddr_in6 sin6_dummy;
 624   const char *delim = "/\0";
 625   char *dupe, *prefix, *mask, *context, *endptr;
 626   int nmask = -1;
 627
 628   if (str == NULL)
 629     return partly_match;
 630
 631   if (strspn (str, IPV6_PREFIX_STR) != strlen (str))
 632     return no_match;
 633
 634   /* tokenize to address + mask */
 635   dupe = XMALLOC(MTYPE_TMP, strlen(str)+1);
 636   strncpy(dupe, str, strlen(str)+1);
 637   prefix = strtok_r(dupe, delim, &context);
 638   mask   = strtok_r(NULL, delim, &context);
 639
 640   if (!mask)
 641     return partly_match;
 642
 643   /* validate prefix */
 644   if (inet_pton(AF_INET6, prefix, &sin6_dummy.sin6_addr) != 1)
 645     return no_match;
 646
 647   /* validate mask */
 648   nmask = strtoimax (mask, &endptr, 10);
 649   if (*endptr != '\0' || nmask < 0 || nmask > 128)
 650     return no_match;
 651
 652   XFREE(MTYPE_TMP, dupe);
 653
 654   return exact_match;
 655 }
 656 #endif
 657
 658 static enum match_type
 659 match_range (struct graph_node *rangenode, const char *str)
 660 {
 661   char *endptr = NULL;
 662   long long val;
 663
 664   if (str == NULL)
 665     return 1;
 666
 667   val = strtoll (str, &endptr, 10);
 668   if (*endptr != '\0')
 669     return 0;
 670
 671   if (val < rangenode->min || val > rangenode->max)
 672     return no_match;
 673   else
 674     return exact_match;
 675 }
 676
 677 static enum match_type
 678 match_word(struct graph_node *wordnode, const char *word)
 679 {
 680   // if the passed token is null or 0 length, partly match
 681   if (!word || !strlen(word))
 682     return partly_match;
 683
 684   // if the passed token is strictly a prefix of the full word, partly match
 685   if (strlen(word) < strlen(wordnode->text))
 686     return !strncmp(wordnode->text, word, strlen(word)) ? partly_match : no_match;
 687
 688   // if they are the same length and exactly equal, exact match
 689   else if (strlen(word) == strlen(wordnode->text))
 690     return !strncmp(wordnode->text, word, strlen(word)) ? exact_match : no_match;
 691
 692   return no_match;
 693 }
 694
 695 static enum match_type
 696 match_number(struct graph_node *numnode, const char *word)
 697 {
 698   if (!strcmp("\0", word)) return no_match;
 699   char *endptr;
 700   long long num = strtoll (word, &endptr, 10);
 701   if (endptr != '\0') return no_match;
 702   return num == numnode->value ? exact_match : no_match;
 703 }
 704
 705 #define VARIABLE_ALPHABET "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890:"
 706
 707 static enum match_type
 708 match_variable(struct graph_node *varnode, const char *word)
 709 {
 710   return strlen(word) == strspn(word, VARIABLE_ALPHABET) ?
 711      exact_match : no_match;
 712 }