path: root/lib/command_match.c

#include <zebra.h>
#include "memory.h"
#include "vector.h"
#include "command_match.h"

/* prototypes */
static int
add_nexthops(struct list *, struct graph_node *);

static enum match_type
cmd_ipv4_match (const char *);

static enum match_type
cmd_ipv4_prefix_match (const char *);

static enum match_type
cmd_ipv6_match (const char *);

static enum match_type
cmd_ipv6_prefix_match (const char *);

static enum match_type
cmd_range_match (struct graph_node *, const char *str);

static enum match_type
cmd_word_match (struct graph_node *, enum filter_type, const char *);

static vector
cmd_make_strvec (const char *);

static enum match_type
match_token (struct graph_node *, char *, enum filter_type);

static vector
cmd_make_strvec (const char *);

/* matching functions */

/**
 * Attempt to find an exact command match for a line of user input.
 *
 * @return cmd_element found, or NULL if there is no match.
 */
struct cmd_element
match_command (struct graph_node *start, vector *command, enum filter_type filter)
{
  // get all possible completions
  struct list completions = match_command_complete (start, command, filter);

  // one of them should be END_GN if this command matches
  struct graph_node *gn;
  struct listnode *node;
  for (ALL_LIST_ELEMENTS_RO(current,node,gn))
  {
    if (gn->type == END_GN)
      break;
    gn = NULL;
  }
  return gn ? gn->element : NULL;
}

/**
 * Compiles next-hops for a given line of user input.
 *
 * Given a string of input and a start node for a matching DFA, runs the input
 * against the DFA until the input is exhausted or a mismatch is encountered.
 *
 * This function returns all valid next hops away from the current node.
 *  - If the input is a valid prefix to a longer command(s), the set of next
 *    hops determines what tokens are valid to follow the prefix. In other words,
 *    the returned list is a list of possible completions.
 *  - If the input matched a full command, exactly one of the next hops will be
 *    a node of type END_GN and its function pointer will be set.
 *  - If the input did not match any valid token sequence, the returned list
 *    will be empty (there are no transitions away from a nonexistent state).
 *
 * @param[in] start the start node of the DFA to match against
 * @param[in] filter the filtering method
 * @param[in] input the input string
 * @return pointer to linked list with all possible next hops from the last
 *         matched token. If this is empty, the input did not match any command.
 */
struct list *
match_command_complete (struct graph_node *start, const char *input, enum filter_type filter)
{
  // break command
  vector command = cmd_make_strvec (input);

  // pointer to next input token to match
  char *token;

  struct list *current  = list_new(), // current nodes to match input token against
              *matched  = list_new(), // current nodes that match the input token
              *next     = list_new(); // possible next hops to current input token

  // pointers used for iterating lists
  struct graph_node *gn;
  struct listnode *node;

  // add all children of start node to list
  add_nexthops(next, start);

  unsigned int idx;
  for (idx = 0; idx < vector_active(command) && next->count > 0; idx++)
  {
    list_free (current);
    current = next;
    next = list_new();

    token = vector_slot(command, idx);

    list_delete_all_node(matched);

    for (ALL_LIST_ELEMENTS_RO(current,node,gn))
    {
      if (match_token(gn, token, filter) == exact_match) {
        listnode_add(matched, gn);
        add_nexthops(next, gn);
      }
    }
  }

  /* Variable summary
   * -----------------------------------------------------------------
   * token    = last input token processed
   * idx      = index in `command` of last token processed
   * current  = set of all transitions from the previous input token
   * matched  = set of all nodes reachable with current input
   * next     = set of all nodes reachable from all nodes in `matched`
   */
  list_free (current);
  list_free (matched);

  return next;
}

/**
 * Adds all children that are reachable by one parser hop
 * to the given list. NUL_GN, SELECTOR_GN, and OPTION_GN
 * nodes are treated as though their children are attached
 * to their parent.
 *
 * @param[out] l the list to add the children to
 * @param[in] node the node to get the children of
 * @return the number of children added to the list
 */
static int
add_nexthops(struct list *l, struct graph_node *node)
{
  int added = 0;
  struct graph_node *child;
  for (unsigned int i = 0; i < vector_active(node->children); i++)
  {
    child = vector_slot(node->children, i);
    switch (child->type) {
      case OPTION_GN:
      case SELECTOR_GN:
      case NUL_GN:
        added += add_nexthops(l, child);
        break;
      default:
        listnode_add(l, child);
        added++;
    }
  }
  return added;
}

/**
 * Build the appropriate argv for a matched command.
 *
 * @param[in] command the command element
 * @param[in] the input line matching this command
 * @param[out] argv
 * @return argc
 *
int
match_build_argv (struct cmd_element *command, vector *input, char *argv)
{
  // build individual command graph
  struct graph_node *start = new_node(NUL_GN);
  cmd_parse_format(start, command->string);
  
}
*/


/* matching utility functions */

static enum match_type
match_token (struct graph_node *node, char *token, enum filter_type filter)
{
  switch (node->type) {
    case WORD_GN:
      return cmd_word_match (node, filter, token);
    case IPV4_GN:
      return cmd_ipv4_match (token);
    case IPV4_PREFIX_GN:
      return cmd_ipv4_prefix_match (token);
    case IPV6_GN:
      return cmd_ipv6_match (token);
    case IPV6_PREFIX_GN:
      return cmd_ipv6_prefix_match (token);
    case RANGE_GN:
      return cmd_range_match (node, token);
    case NUMBER_GN:
      return cmd_number_match (node, token);
    case VARIABLE_GN:
      return cmd_variable_match (node, token);
    default:
      return no_match;
  }
}

#define IPV4_ADDR_STR   "0123456789."
#define IPV4_PREFIX_STR "0123456789./"

static enum match_type
cmd_ipv4_match (const char *str)
{
  struct sockaddr_in sin_dummy;

  if (str == NULL)
    return partly_match;

  if (strspn (str, IPV4_ADDR_STR) != strlen (str))
    return no_match;

  if (inet_pton(AF_INET, str, &sin_dummy.sin_addr) != 1)
    return no_match;

  return exact_match;
}

static enum match_type
cmd_ipv4_prefix_match (const char *str)
{
  struct sockaddr_in sin_dummy;
  const char *delim = "/\0";
  char *dupe, *prefix, *mask, *context, *endptr;
  int nmask = -1;

  if (str == NULL)
    return partly_match;

  if (strspn (str, IPV4_PREFIX_STR) != strlen (str))
    return no_match;

  /* tokenize to address + mask */
  dupe = XMALLOC(MTYPE_TMP, strlen(str)+1);
  strncpy(dupe, str, strlen(str)+1);
  prefix = strtok_r(dupe, delim, &context);
  mask   = strtok_r(NULL, delim, &context);

  if (!mask)
    return partly_match;

  /* validate prefix */
  if (inet_pton(AF_INET, prefix, &sin_dummy.sin_addr) != 1)
    return no_match;

  /* validate mask */
  nmask = strtol (mask, &endptr, 10);
  if (*endptr != '\0' || nmask < 0 || nmask > 32)
    return no_match;

  XFREE(MTYPE_TMP, dupe);

  return exact_match;
}

#ifdef HAVE_IPV6
#define IPV6_ADDR_STR   "0123456789abcdefABCDEF:."
#define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"

static enum match_type
cmd_ipv6_match (const char *str)
{
  struct sockaddr_in6 sin6_dummy;
  int ret;

  if (str == NULL)
    return partly_match;

  if (strspn (str, IPV6_ADDR_STR) != strlen (str))
    return no_match;

  ret = inet_pton(AF_INET6, str, &sin6_dummy.sin6_addr);

  if (ret == 1)
    return exact_match;

  return no_match;
}

static enum match_type
cmd_ipv6_prefix_match (const char *str)
{
  struct sockaddr_in6 sin6_dummy;
  const char *delim = "/\0";
  char *dupe, *prefix, *mask, *context, *endptr;
  int nmask = -1;

  if (str == NULL)
    return partly_match;

  if (strspn (str, IPV6_PREFIX_STR) != strlen (str))
    return no_match;

  /* tokenize to address + mask */
  dupe = XMALLOC(MTYPE_TMP, strlen(str)+1);
  strncpy(dupe, str, strlen(str)+1);
  prefix = strtok_r(dupe, delim, &context);
  mask   = strtok_r(NULL, delim, &context);

  if (!mask)
    return partly_match;

  /* validate prefix */
  if (inet_pton(AF_INET6, prefix, &sin6_dummy.sin6_addr) != 1)
    return no_match;

  /* validate mask */
  nmask = strtol (mask, &endptr, 10);
  if (*endptr != '\0' || nmask < 0 || nmask > 128)
    return no_match;

  XFREE(MTYPE_TMP, dupe);

  return exact_match;
}
#endif

static enum match_type
cmd_range_match (struct graph_node *rangenode, const char *str)
{
  char *endptr = NULL;
  signed long long val;

  if (str == NULL)
    return 1;

  val = strtoll (str, &endptr, 10);
  if (*endptr != '\0')
    return 0;
  val = llabs(val);

  if (val < rangenode->min || val > rangenode->max)
    return no_match;
  else
    return exact_match;
}

static enum match_type
cmd_word_match(struct graph_node *wordnode,
               enum filter_type filter,
               const char *word)
{

  if (filter == FILTER_RELAXED)
  {
    if (!word || !strlen(word))
      return partly_match;
    else if (!strncmp(wordnode->text, word, strlen(word)))
      return !strcmp(wordnode->text, word) ? exact_match : partly_match;
    else
      return no_match;
  }
  else
  {
     if (!word)
       return no_match;
     else
       return !strcmp(wordnode->text, word) ? exact_match : no_match;
  }
}

cmd_number_match(struct graph_node *numnode, const char *word)
{
  if (!strcmp("\0", word)) return no_match;
  char *endptr;
  long num = strtol(word, &endptr, 10);
  if (endptr != '\0') return no_match;
  return num == numnode->value ? exact_match : no_match;
}

cmd_variable_match(struct graph_node *varnode, const char *word)
{
  // I guess this matches whatever?
  return exact_match;
}

static vector
cmd_make_strvec (const char *string)
{
  const char *cp, *start;
  char *token;
  int strlen;
  vector strvec;

  if (string == NULL)
    return NULL;

  cp = string;

  /* Skip white spaces. */
  while (isspace ((int) *cp) && *cp != '\0')
    cp++;

  /* Return if there is only white spaces */
  if (*cp == '\0')
    return NULL;

  if (*cp == '!' || *cp == '#')
    return NULL;

  /* Prepare return vector. */
  strvec = vector_init (VECTOR_MIN_SIZE);

  /* Copy each command piece and set into vector. */
  while (1)
    {
      start = cp;
      while (!(isspace ((int) *cp) || *cp == '\r' || *cp == '\n') &&
            *cp != '\0')
         cp++;
      strlen = cp - start;
      token = XMALLOC (MTYPE_STRVEC, strlen + 1);
      memcpy (token, start, strlen);
      *(token + strlen) = '\0';
      vector_set (strvec, token);

      while ((isspace ((int) *cp) || *cp == '\n' || *cp == '\r') &&
            *cp != '\0')
         cp++;

      if (*cp == '\0')
        return strvec;
    }
}