lib/command_match.c

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