[mirror_frr.git] / lib / command_match.c

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

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 VARIABLE_GN:
    default:
      return no_match;
  }
}

/* Breaking up string into each command piece. I assume given
   character is separated by a space character. Return value is a
   vector which includes char ** data element. */
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;
    }
}

/**
 * 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;
}

/**
 * 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, there are no possible
 * transitions, or both.
 * If there are no further state transitions available, one of two scenarios is possible:
 *  - The end of input has been reached. This indicates a valid command.
 *  - The end of input has not yet been reached. The input does not match any command.
 * If there are further transitions available, one of two scenarios is possible:
 *  - The current input is a valid prefix to a longer command
 *  - The current input matches a command
 *  - The current input matches a command, and is also a valid prefix to a longer command
 *
 * Any other states indicate a programming error.
 *
 * @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 an array with two lists. The first list is
 */
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`
   */

  struct list **result = malloc( 2 * sizeof(struct list *) );
  result[0] = matched;
  result[1] = next;

  return result;
}


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

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

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

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

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

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