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