[mirror_frr.git] / 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 */

/**
 * Compiles matches or 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 (struct graph_node *start, enum filter_type filter, const char *input)
{
  // 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 *cnode;
  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,cnode))
    {
      if (match_token(cnode, token, filter) == exact_match) {
        listnode_add(matched, cnode);
        add_nexthops(next, cnode);
      }
    }
  }

  /* 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);
    if (child->type == OPTION_GN || child->type == SELECTOR_GN || child->type == NUL_GN)
      added += add_nexthops(l, child);
    else {
      listnode_add(l, child);
      added++;
    }
  }
  return added;
}


/* 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 node->value == atoi(token);
    case NUL_GN:
      return exact_match;
    case VARIABLE_GN:
    default:
      return no_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;
    }
}

#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;
}

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

#ifdef HAVE_IPV6
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;

  if (!word)
    return no_match;

  if (filter == FILTER_RELAXED && !strncmp(wordnode->text, word, strlen(word)))
  {
    if (!strcmp(wordnode->text, word))
      return exact_match;
    return partly_match;
  }
  if (filter == FILTER_STRICT && !strcmp(wordnode->text, word))
    return exact_match;

  return no_match;
}
Commit	Line	Data
9d0662e0 QY	1	#include <zebra.h>
9d0662e0 QY	2	#include "memory.h"
18be0e59	3	#include "vector.h"
9d0662e0 QY	4	#include "command_match.h"
9d0662e0 QY	5
880e24a1 QY	6	/* prototypes */
	7	static int
	8	add_nexthops(struct list , struct graph_node );
18be0e59	9
880e24a1 QY	10	static enum match_type
880e24a1 QY	11	cmd_ipv4_match (const char *);
18be0e59	12
880e24a1 QY	13	static enum match_type
880e24a1 QY	14	cmd_ipv4_prefix_match (const char *);
18be0e59	15
880e24a1 QY	16	static enum match_type
880e24a1 QY	17	cmd_ipv6_match (const char *);
18be0e59	18
880e24a1 QY	19	static enum match_type
880e24a1 QY	20	cmd_ipv6_prefix_match (const char *);
18be0e59	21
880e24a1 QY	22	static enum match_type
880e24a1 QY	23	cmd_range_match (struct graph_node , const char str);
18be0e59	24
880e24a1 QY	25	static enum match_type
880e24a1 QY	26	cmd_word_match (struct graph_node , enum filter_type, const char );
18be0e59	27
880e24a1 QY	28	static vector
880e24a1 QY	29	cmd_make_strvec (const char *);
18be0e59	30
880e24a1 QY	31	static enum match_type
880e24a1 QY	32	match_token (struct graph_node , char , enum filter_type);
18be0e59	33
880e24a1 QY	34	static vector
880e24a1 QY	35	cmd_make_strvec (const char *);
18be0e59	36
880e24a1	37	/* matching functions */
18be0e59 QY	38
	39	/**
	40	* Compiles matches or next-hops for a given line of user input.
	41	*
	42	* Given a string of input and a start node for a matching DFA, runs the input
880e24a1	43	* against the DFA until the input is exhausted or a mismatch is encountered.
18be0e59	44	*
880e24a1 QY	45	* This function returns all valid next hops away from the current node.
	46	* - If the input is a valid prefix to a longer command(s), the set of next
	47	* hops determines what tokens are valid to follow the prefix. In other words,
	48	* the returned list is a list of possible completions.
	49	* - If the input matched a full command, exactly one of the next hops will be
	50	* a node of type END_GN and its function pointer will be set.
	51	* - If the input did not match any valid token sequence, the returned list
	52	* will be empty (there are no transitions away from a nonexistent state).
18be0e59 QY	53	*
	54	* @param[in] start the start node of the DFA to match against
	55	* @param[in] filter the filtering method
	56	* @param[in] input the input string
880e24a1 QY	57	* @return pointer to linked list with all possible next hops from the last
880e24a1 QY	58	* matched token. If this is empty, the input did not match any command.
18be0e59	59	*/
880e24a1	60	struct list *
9d0662e0 QY	61	match_command (struct graph_node start, enum filter_type filter, const char input)
9d0662e0 QY	62	{
18be0e59 QY	63	// break command
	64	vector command = cmd_make_strvec (input);
	65
	66	// pointer to next input token to match
	67	char *token;
	68
	69	struct list *current = list_new(), // current nodes to match input token against
	70	*matched = list_new(), // current nodes that match the input token
	71	*next = list_new(); // possible next hops to current input token
	72
	73	// pointers used for iterating lists
	74	struct graph_node *cnode;
	75	struct listnode *node;
	76
	77	// add all children of start node to list
	78	add_nexthops(next, start);
	79
	80	unsigned int idx;
	81	for (idx = 0; idx < vector_active(command) && next->count > 0; idx++)
	82	{
	83	list_free (current);
	84	current = next;
	85	next = list_new();
	86
	87	token = vector_slot(command, idx);
	88
	89	list_delete_all_node(matched);
	90
	91	for (ALL_LIST_ELEMENTS_RO(current,node,cnode))
	92	{
	93	if (match_token(cnode, token, filter) == exact_match) {
	94	listnode_add(matched, cnode);
	95	add_nexthops(next, cnode);
	96	}
	97	}
	98	}
	99
	100	/* Variable summary
	101	* -----------------------------------------------------------------
	102	* token = last input token processed
	103	* idx = index in `command` of last token processed
	104	* current = set of all transitions from the previous input token
	105	* matched = set of all nodes reachable with current input
	106	* next = set of all nodes reachable from all nodes in `matched`
	107	*/
880e24a1 QY	108	list_free (current);
	109	list_free (matched);
	110
	111	return next;
	112	}
	113
	114	/**
	115	* Adds all children that are reachable by one parser hop
	116	* to the given list. NUL_GN, SELECTOR_GN, and OPTION_GN
	117	* nodes are treated as though their children are attached
	118	* to their parent.
	119	*
	120	* @param[out] l the list to add the children to
	121	* @param[in] node the node to get the children of
	122	* @return the number of children added to the list
	123	*/
	124	static int
	125	add_nexthops(struct list l, struct graph_node node)
	126	{
	127	int added = 0;
	128	struct graph_node *child;
	129	for (unsigned int i = 0; i < vector_active(node->children); i++)
	130	{
	131	child = vector_slot(node->children, i);
	132	if (child->type == OPTION_GN \|\| child->type == SELECTOR_GN \|\| child->type == NUL_GN)
	133	added += add_nexthops(l, child);
	134	else {
	135	listnode_add(l, child);
	136	added++;
	137	}
	138	}
	139	return added;
	140	}
18be0e59	141
18be0e59	142
880e24a1 QY	143	/* matching utility functions */
	144
	145	static enum match_type
	146	match_token (struct graph_node node, char token, enum filter_type filter)
	147	{
	148	switch (node->type) {
	149	case WORD_GN:
	150	return cmd_word_match (node, filter, token);
	151	case IPV4_GN:
	152	return cmd_ipv4_match (token);
	153	case IPV4_PREFIX_GN:
	154	return cmd_ipv4_prefix_match (token);
	155	case IPV6_GN:
	156	return cmd_ipv6_match (token);
	157	case IPV6_PREFIX_GN:
	158	return cmd_ipv6_prefix_match (token);
	159	case RANGE_GN:
	160	return cmd_range_match (node, token);
	161	case NUMBER_GN:
	162	return node->value == atoi(token);
	163	case NUL_GN:
	164	return exact_match;
	165	case VARIABLE_GN:
	166	default:
	167	return no_match;
	168	}
9d0662e0 QY	169	}
9d0662e0 QY	170
880e24a1 QY	171	static vector
	172	cmd_make_strvec (const char *string)
	173	{
	174	const char cp, start;
	175	char *token;
	176	int strlen;
	177	vector strvec;
	178
	179	if (string == NULL)
	180	return NULL;
	181
	182	cp = string;
	183
	184	/* Skip white spaces. */
	185	while (isspace ((int) cp) && cp != '\0')
	186	cp++;
	187
	188	/* Return if there is only white spaces */
	189	if (*cp == '\0')
	190	return NULL;
	191
	192	if (cp == '!' \|\| cp == '#')
	193	return NULL;
	194
	195	/* Prepare return vector. */
	196	strvec = vector_init (VECTOR_MIN_SIZE);
	197
	198	/* Copy each command piece and set into vector. */
	199	while (1)
	200	{
	201	start = cp;
	202	while (!(isspace ((int) cp) \|\| cp == '\r' \|\| *cp == '\n') &&
	203	*cp != '\0')
	204	cp++;
	205	strlen = cp - start;
	206	token = XMALLOC (MTYPE_STRVEC, strlen + 1);
	207	memcpy (token, start, strlen);
	208	*(token + strlen) = '\0';
	209	vector_set (strvec, token);
	210
	211	while ((isspace ((int) cp) \|\| cp == '\n' \|\| *cp == '\r') &&
	212	*cp != '\0')
	213	cp++;
	214
	215	if (*cp == '\0')
	216	return strvec;
	217	}
	218	}
9d0662e0 QY	219
	220	#define IPV4_ADDR_STR "0123456789."
	221	#define IPV4_PREFIX_STR "0123456789./"
	222
880e24a1	223	static enum match_type
9d0662e0 QY	224	cmd_ipv4_match (const char *str)
	225	{
	226	struct sockaddr_in sin_dummy;
	227
	228	if (str == NULL)
	229	return partly_match;
	230
	231	if (strspn (str, IPV4_ADDR_STR) != strlen (str))
	232	return no_match;
	233
	234	if (inet_pton(AF_INET, str, &sin_dummy.sin_addr) != 1)
	235	return no_match;
	236
	237	return exact_match;
	238	}
	239
880e24a1	240	static enum match_type
9d0662e0 QY	241	cmd_ipv4_prefix_match (const char *str)
	242	{
	243	struct sockaddr_in sin_dummy;
	244	const char *delim = "/\0";
	245	char dupe, prefix, mask, context, *endptr;
	246	int nmask = -1;
	247
	248	if (str == NULL)
	249	return partly_match;
	250
	251	if (strspn (str, IPV4_PREFIX_STR) != strlen (str))
	252	return no_match;
	253
	254	/* tokenize to address + mask */
	255	dupe = XMALLOC(MTYPE_TMP, strlen(str)+1);
	256	strncpy(dupe, str, strlen(str)+1);
	257	prefix = strtok_r(dupe, delim, &context);
	258	mask = strtok_r(NULL, delim, &context);
	259
	260	if (!mask)
	261	return partly_match;
	262
	263	/* validate prefix */
	264	if (inet_pton(AF_INET, prefix, &sin_dummy.sin_addr) != 1)
	265	return no_match;
	266
	267	/* validate mask */
	268	nmask = strtol (mask, &endptr, 10);
	269	if (*endptr != '\0' \|\| nmask < 0 \|\| nmask > 32)
	270	return no_match;
	271
	272	XFREE(MTYPE_TMP, dupe);
	273
	274	return exact_match;
	275	}
	276
	277	#define IPV6_ADDR_STR "0123456789abcdefABCDEF:."
	278	#define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
	279
	280	#ifdef HAVE_IPV6
880e24a1	281	static enum match_type
9d0662e0 QY	282	cmd_ipv6_match (const char *str)
	283	{
	284	struct sockaddr_in6 sin6_dummy;
	285	int ret;
	286
	287	if (str == NULL)
	288	return partly_match;
	289
	290	if (strspn (str, IPV6_ADDR_STR) != strlen (str))
	291	return no_match;
	292
	293	ret = inet_pton(AF_INET6, str, &sin6_dummy.sin6_addr);
	294
	295	if (ret == 1)
	296	return exact_match;
	297
	298	return no_match;
	299	}
	300
880e24a1	301	static enum match_type
9d0662e0 QY	302	cmd_ipv6_prefix_match (const char *str)
	303	{
	304	struct sockaddr_in6 sin6_dummy;
	305	const char *delim = "/\0";
	306	char dupe, prefix, mask, context, *endptr;
	307	int nmask = -1;
	308
	309	if (str == NULL)
	310	return partly_match;
	311
	312	if (strspn (str, IPV6_PREFIX_STR) != strlen (str))
	313	return no_match;
	314
	315	/* tokenize to address + mask */
	316	dupe = XMALLOC(MTYPE_TMP, strlen(str)+1);
	317	strncpy(dupe, str, strlen(str)+1);
	318	prefix = strtok_r(dupe, delim, &context);
	319	mask = strtok_r(NULL, delim, &context);
	320
	321	if (!mask)
	322	return partly_match;
	323
	324	/* validate prefix */
	325	if (inet_pton(AF_INET6, prefix, &sin6_dummy.sin6_addr) != 1)
	326	return no_match;
	327
	328	/* validate mask */
	329	nmask = strtol (mask, &endptr, 10);
	330	if (*endptr != '\0' \|\| nmask < 0 \|\| nmask > 128)
	331	return no_match;
	332
	333	XFREE(MTYPE_TMP, dupe);
	334
	335	return exact_match;
	336	}
	337	#endif
	338
880e24a1	339	static enum match_type
9d0662e0 QY	340	cmd_range_match (struct graph_node rangenode, const char str)
	341	{
	342	char *endptr = NULL;
	343	signed long long val;
	344
	345	if (str == NULL)
	346	return 1;
	347
	348	val = strtoll (str, &endptr, 10);
	349	if (*endptr != '\0')
	350	return 0;
	351	val = llabs(val);
	352
	353	if (val < rangenode->min \|\| val > rangenode->max)
	354	return no_match;
	355	else
	356	return exact_match;
	357	}
	358
880e24a1	359	static enum match_type
9d0662e0 QY	360	cmd_word_match(struct graph_node *wordnode,
	361	enum filter_type filter,
	362	const char *word)
	363	{
	364	if (filter == FILTER_RELAXED)
	365	if (!word \|\| !strlen(word))
	366	return partly_match;
	367
	368	if (!word)
	369	return no_match;
	370
	371	if (filter == FILTER_RELAXED && !strncmp(wordnode->text, word, strlen(word)))
	372	{
	373	if (!strcmp(wordnode->text, word))
	374	return exact_match;
	375	return partly_match;
	376	}
	377	if (filter == FILTER_STRICT && !strcmp(wordnode->text, word))
	378	return exact_match;
	379
	380	return no_match;
	381	}