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