summaryrefslogtreecommitdiffstats
path: root/lib/command_match.c
blob: f740b726008cf7ab5a757e460f11aa00c43a31ab (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Input matching routines for CLI backend.
 *
 * --
 * Copyright (C) 2016 Cumulus Networks, Inc.
 */

#include <zebra.h>

#include "command_match.h"
#include "memory.h"
#include "asn.h"

DEFINE_MTYPE_STATIC(LIB, CMD_MATCHSTACK, "Command Match Stack");

#ifdef TRACE_MATCHER
#define TM 1
#else
#define TM 0
#endif

#define trace_matcher(...)                                                     \
	do {                                                                   \
		if (TM)                                                        \
			fprintf(stderr, __VA_ARGS__);                          \
	} while (0);

/* matcher helper prototypes */
static int add_nexthops(struct list *, struct graph_node *,
			struct graph_node **, size_t, bool);

static enum matcher_rv command_match_r(struct graph_node *, vector,
				       unsigned int, struct graph_node **,
				       struct list **);

static int score_precedence(enum cmd_token_type);

static enum match_type min_match_level(enum cmd_token_type);

static void del_arglist(struct list *);

static struct cmd_token *disambiguate_tokens(struct cmd_token *,
					     struct cmd_token *, char *);

static struct list *disambiguate(struct list *, struct list *, vector,
				 unsigned int);

int compare_completions(const void *, const void *);

/* token matcher prototypes */
static enum match_type match_token(struct cmd_token *, char *);

static enum match_type match_ipv4(const char *);

static enum match_type match_ipv4_prefix(const char *);

static enum match_type match_ipv6_prefix(const char *, bool);

static enum match_type match_range(struct cmd_token *, const char *);

static enum match_type match_word(struct cmd_token *, const char *);

static enum match_type match_variable(struct cmd_token *, const char *);

static enum match_type match_mac(const char *, bool);

static bool is_neg(vector vline, size_t idx)
{
	if (idx >= vector_active(vline) || !vector_slot(vline, idx))
		return false;
	return !strcmp(vector_slot(vline, idx), "no");
}

enum matcher_rv command_match(struct graph *cmdgraph, vector vline,
			      struct list **argv, const struct cmd_element **el)
{
	struct graph_node *stack[CMD_ARGC_MAX];
	enum matcher_rv status;
	*argv = NULL;

	// prepend a dummy token to match that pesky start node
	vector vvline = vector_init(vline->alloced + 1);
	vector_set_index(vvline, 0, XSTRDUP(MTYPE_TMP, "dummy"));
	memcpy(vvline->index + 1, vline->index,
	       sizeof(void *) * vline->alloced);
	vvline->active = vline->active + 1;

	struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
	status = command_match_r(start, vvline, 0, stack, argv);
	if (status == MATCHER_OK) { // successful match
		struct listnode *head = listhead(*argv);
		struct listnode *tail = listtail(*argv);

		assert(head);
		assert(tail);

		// delete dummy start node
		cmd_token_del((struct cmd_token *)head->data);
		list_delete_node(*argv, head);

		// get cmd_element out of list tail
		*el = listgetdata(tail);
		list_delete_node(*argv, tail);

		// now argv is an ordered list of cmd_token matching the user
		// input, with each cmd_token->arg holding the corresponding
		// input
		assert(*el);
	} else if (*argv) {
		del_arglist(*argv);
		*argv = NULL;
	}

	if (!*el) {
		trace_matcher("No match\n");
	} else {
		trace_matcher("Matched command\n->string %s\n->desc %s\n",
			      (*el)->string, (*el)->doc);
	}

	// free the leader token we alloc'd
	XFREE(MTYPE_TMP, vector_slot(vvline, 0));
	// free vector
	vector_free(vvline);

	return status;
}

/**
 * Builds an argument list given a DFA and a matching input line.
 *
 * First the function determines if the node it is passed matches the first
 * token of input. If it does not, it returns NULL (MATCHER_NO_MATCH). If it
 * does match, then it saves the input token as the head of an argument list.
 *
 * The next step is to see if there is further input in the input line. If
 * there is not, the current node's children are searched to see if any of them
 * are leaves (type END_TKN). If this is the case, then the bottom of the
 * recursion stack has been reached, the leaf is pushed onto the argument list,
 * the current node is pushed, and the resulting argument list is
 * returned (MATCHER_OK). If it is not the case, NULL is returned, indicating
 * that there is no match for the input along this path (MATCHER_INCOMPLETE).
 *
 * If there is further input, then the function recurses on each of the current
 * node's children, passing them the input line minus the token that was just
 * matched. For each child, the return value of the recursive call is
 * inspected. If it is null, then there is no match for the input along the
 * subgraph headed by that child. If it is not null, then there is at least one
 * input match in that subgraph (more on this in a moment).
 *
 * If a recursive call on a child returns a non-null value, then it has matched
 * the input given it on the subgraph that starts with that child. However, due
 * to the flexibility of the grammar, it is sometimes the case that two or more
 * child graphs match the same input (two or more of the recursive calls have
 * non-NULL return values). This is not a valid state, since only one true
 * match is possible. In order to resolve this conflict, the function keeps a
 * reference to the child node that most specifically matches the input. This
 * is done by assigning each node type a precedence. If a child is found to
 * match the remaining input, then the precedence values of the current
 * best-matching child and this new match are compared. The node with higher
 * precedence is kept, and the other match is discarded. Due to the recursive
 * nature of this function, it is only necessary to compare the precedence of
 * immediate children, since all subsequent children will already have been
 * disambiguated in this way.
 *
 * In the event that two children are found to match with the same precedence,
 * then the input is ambiguous for the passed cmd_element and NULL is returned.
 *
 * @param[in] start the start node.
 * @param[in] vline the vectorized input line.
 * @param[in] n the index of the first input token.
 * @return A linked list of n elements. The first n-1 elements are pointers to
 * struct cmd_token and represent the sequence of tokens matched by the input.
 * The ->arg field of each token points to a copy of the input matched on it.
 * The final nth element is a pointer to struct cmd_element, which is the
 * command that was matched.
 *
 * If no match was found, the return value is NULL.
 */
static enum matcher_rv command_match_r(struct graph_node *start, vector vline,
				       unsigned int n,
				       struct graph_node **stack,
				       struct list **currbest)
{
	assert(n < vector_active(vline));

	enum matcher_rv status = MATCHER_NO_MATCH;

	// get the minimum match level that can count as a full match
	struct cmd_token *copy, *token = start->data;
	enum match_type minmatch = min_match_level(token->type);

	/* check history/stack of tokens
	 * this disallows matching the same one more than once if there is a
	 * circle in the graph (used for keyword arguments) */
	if (n == CMD_ARGC_MAX)
		return MATCHER_NO_MATCH;
	if (!token->allowrepeat)
		for (size_t s = 0; s < n; s++)
			if (stack[s] == start)
				return MATCHER_NO_MATCH;

	// get the current operating input token
	char *input_token = vector_slot(vline, n);

#ifdef TRACE_MATCHER
	fprintf(stdout, "\"%-20s\" matches \"%-30s\" ? ", input_token,
		token->text);
	enum match_type mt = match_token(token, input_token);
	fprintf(stdout, "type: %d ", token->type);
	fprintf(stdout, "min: %d - ", minmatch);
	switch (mt) {
	case trivial_match:
		fprintf(stdout, "trivial_match ");
		break;
	case no_match:
		fprintf(stdout, "no_match ");
		break;
	case partly_match:
		fprintf(stdout, "partly_match ");
		break;
	case exact_match:
		fprintf(stdout, "exact_match ");
		break;
	}
	if (mt >= minmatch)
		fprintf(stdout, " MATCH");
	fprintf(stdout, "\n");
#endif

	// if we don't match this node, die
	if (match_token(token, input_token) < minmatch)
		return MATCHER_NO_MATCH;

	stack[n] = start;

	// pointers for iterating linklist
	struct listnode *ln;
	struct graph_node *gn;

	// get all possible nexthops
	struct list *next = list_new();
	add_nexthops(next, start, NULL, 0, is_neg(vline, 1));

	// determine the best match
	for (ALL_LIST_ELEMENTS_RO(next, ln, gn)) {
		// if we've matched all input we're looking for END_TKN
		if (n + 1 == vector_active(vline)) {
			struct cmd_token *tok = gn->data;
			if (tok->type == END_TKN) {
				// if more than one END_TKN in the follow set
				if (*currbest) {
					status = MATCHER_AMBIGUOUS;
					break;
				} else {
					status = MATCHER_OK;
				}
				*currbest = list_new();
				// node should have one child node with the
				// element
				struct graph_node *leaf =
					vector_slot(gn->to, 0);
				// last node in the list will hold the
				// cmd_element; this is important because
				// list_delete() expects that all nodes have
				// the same data type, so when deleting this
				// list the last node must be manually deleted
				struct cmd_element *el = leaf->data;
				listnode_add(*currbest, el);
				(*currbest)->del =
					(void (*)(void *)) & cmd_token_del;
				// do not break immediately; continue walking
				// through the follow set to ensure that there
				// is exactly one END_TKN
			}
			continue;
		}

		// else recurse on candidate child node
		struct list *result = NULL;
		enum matcher_rv rstat =
			command_match_r(gn, vline, n + 1, stack, &result);

		// save the best match
		if (result && *currbest) {
			// pick the best of two matches
			struct list *newbest =
				disambiguate(*currbest, result, vline, n + 1);

			// current best and result are ambiguous
			if (!newbest)
				status = MATCHER_AMBIGUOUS;
			// current best is still the best, but ambiguous
			else if (newbest == *currbest
				 && status == MATCHER_AMBIGUOUS)
				status = MATCHER_AMBIGUOUS;
			// result is better, but also ambiguous
			else if (newbest == result
				 && rstat == MATCHER_AMBIGUOUS)
				status = MATCHER_AMBIGUOUS;
			// one or the other is superior and not ambiguous
			else
				status = MATCHER_OK;

			// delete the unnecessary result
			struct list *todelete =
				((newbest && newbest == result) ? *currbest
								: result);
			del_arglist(todelete);

			*currbest = newbest ? newbest : *currbest;
		} else if (result) {
			status = rstat;
			*currbest = result;
		} else if (!*currbest) {
			status = MAX(rstat, status);
		}
	}
	if (*currbest) {
		// copy token, set arg and prepend to currbest
		token = start->data;
		copy = cmd_token_dup(token);
		copy->arg = XSTRDUP(MTYPE_CMD_ARG, input_token);
		listnode_add_before(*currbest, (*currbest)->head, copy);
	} else if (n + 1 == vector_active(vline) && status == MATCHER_NO_MATCH)
		status = MATCHER_INCOMPLETE;

	// cleanup
	list_delete(&next);

	return status;
}

static void stack_del(void *val)
{
	XFREE(MTYPE_CMD_MATCHSTACK, val);
}

enum matcher_rv command_complete(struct graph *graph, vector vline,
				 struct list **completions)
{
	// pointer to next input token to match
	char *input_token;
	bool neg = is_neg(vline, 0);

	struct list *
		current =
		       list_new(), // current nodes to match input token against
		*next = list_new(); // possible next hops after current input
				    // token
	current->del = next->del = stack_del;

	// pointers used for iterating lists
	struct graph_node **gstack, **newstack;
	struct listnode *node;

	// add all children of start node to list
	struct graph_node *start = vector_slot(graph->nodes, 0);
	add_nexthops(next, start, &start, 0, neg);

	unsigned int idx;
	for (idx = 0; idx < vector_active(vline) && next->count > 0; idx++) {
		list_delete(&current);
		current = next;
		next = list_new();
		next->del = stack_del;

		input_token = vector_slot(vline, idx);

		int exact_match_exists = 0;
		for (ALL_LIST_ELEMENTS_RO(current, node, gstack))
			if (!exact_match_exists)
				exact_match_exists =
					(match_token(gstack[0]->data,
						     input_token)
					 == exact_match);
			else
				break;

		for (ALL_LIST_ELEMENTS_RO(current, node, gstack)) {
			struct cmd_token *token = gstack[0]->data;

			if (token->attr & CMD_ATTR_HIDDEN)
				continue;

			enum match_type minmatch = min_match_level(token->type);
			trace_matcher("\"%s\" matches \"%s\" (%d) ? ",
				      input_token, token->text, token->type);

			unsigned int last_token =
				(vector_active(vline) - 1 == idx);
			enum match_type matchtype =
				match_token(token, input_token);
			switch (matchtype) {
			// occurs when last token is whitespace
			case trivial_match:
				trace_matcher("trivial_match\n");
				assert(last_token);
				newstack = XMALLOC(MTYPE_CMD_MATCHSTACK,
						   sizeof(struct graph_node *));
				/* we're not recursing here, just the first
				 * element is OK */
				newstack[0] = gstack[0];
				listnode_add(next, newstack);
				break;
			case partly_match:
				trace_matcher("trivial_match\n");
				if (exact_match_exists && !last_token)
					break;
			/* fallthru */
			case exact_match:
				trace_matcher("exact_match\n");
				if (last_token) {
					newstack = XMALLOC(
						MTYPE_CMD_MATCHSTACK,
						sizeof(struct graph_node *));
					/* same as above, not recursing on this
					 */
					newstack[0] = gstack[0];
					listnode_add(next, newstack);
				} else if (matchtype >= minmatch)
					add_nexthops(next, gstack[0], gstack,
						     idx + 1, neg);
				break;
			case no_match:
				trace_matcher("no_match\n");
				break;
			}
		}
	}

	/* 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
	 * next     = set of all nodes reachable from all nodes in `matched`
	 */

	enum matcher_rv mrv = idx == vector_active(vline) && next->count
				      ? MATCHER_OK
				      : MATCHER_NO_MATCH;

	*completions = NULL;
	if (!MATCHER_ERROR(mrv)) {
		// extract cmd_token into list
		*completions = list_new();
		for (ALL_LIST_ELEMENTS_RO(next, node, gstack)) {
			listnode_add(*completions, gstack[0]->data);
		}
	}

	list_delete(&current);
	list_delete(&next);

	return mrv;
}

/**
 * Adds all children that are reachable by one parser hop to the given list.
 * special tokens except END_TKN are treated as transparent.
 *
 * @param[in] list to add the nexthops to
 * @param[in] node to start calculating nexthops from
 * @param[in] stack listing previously visited nodes, if non-NULL.
 * @param[in] stackpos how many valid entries are in stack
 * @return the number of children added to the list
 *
 * NB: non-null "stack" means that new stacks will be added to "list" as
 * output, instead of direct node pointers!
 */
static int add_nexthops(struct list *list, struct graph_node *node,
			struct graph_node **stack, size_t stackpos, bool neg)
{
	int added = 0;
	struct graph_node *child;
	struct graph_node **nextstack;
	for (unsigned int i = 0; i < vector_active(node->to); i++) {
		child = vector_slot(node->to, i);
		size_t j;
		struct cmd_token *token = child->data;
		if (!token->allowrepeat && stack) {
			for (j = 0; j < stackpos; j++)
				if (child == stack[j])
					break;
			if (j != stackpos)
				continue;
		}

		if (token->type == NEG_ONLY_TKN && !neg)
			continue;

		if (token->type >= SPECIAL_TKN && token->type != END_TKN) {
			added +=
				add_nexthops(list, child, stack, stackpos, neg);
		} else {
			if (stack) {
				nextstack = XMALLOC(
					MTYPE_CMD_MATCHSTACK,
					(stackpos + 1)
						* sizeof(struct graph_node *));
				nextstack[0] = child;
				memcpy(nextstack + 1, stack,
				       stackpos * sizeof(struct graph_node *));

				listnode_add(list, nextstack);
			} else
				listnode_add(list, child);
			added++;
		}
	}

	return added;
}

/**
 * Determines the node types for which a partial match may count as a full
 * match. Enables command abbrevations.
 *
 * @param[in] type node type
 * @return minimum match level needed to for a token to fully match
 */
static enum match_type min_match_level(enum cmd_token_type type)
{
	switch (type) {
	// anything matches a start node, for the sake of recursion
	case START_TKN:
		return no_match;
	// allowing words to partly match enables command abbreviation
	case WORD_TKN:
		return partly_match;
	case RANGE_TKN:
	case IPV4_TKN:
	case IPV4_PREFIX_TKN:
	case IPV6_TKN:
	case IPV6_PREFIX_TKN:
	case MAC_TKN:
	case MAC_PREFIX_TKN:
	case FORK_TKN:
	case JOIN_TKN:
	case END_TKN:
	case NEG_ONLY_TKN:
	case VARIABLE_TKN:
	case ASNUM_TKN:
		return exact_match;
	}

	assert(!"Reached end of function we should never hit");
}

/**
 * Assigns precedence scores to node types.
 *
 * @param[in] type node type to score
 * @return precedence score
 */
static int score_precedence(enum cmd_token_type type)
{
	switch (type) {
	// some of these are mutually exclusive, so they share
	// the same precedence value
	case IPV4_TKN:
	case IPV4_PREFIX_TKN:
	case IPV6_TKN:
	case IPV6_PREFIX_TKN:
	case MAC_TKN:
	case MAC_PREFIX_TKN:
	case RANGE_TKN:
		return 2;
	case ASNUM_TKN:
	case WORD_TKN:
		return 3;
	case VARIABLE_TKN:
		return 4;
	case JOIN_TKN:
	case START_TKN:
	case END_TKN:
	case NEG_ONLY_TKN:
	case SPECIAL_TKN:
		return 10;
	}

	assert(!"Reached end of function we should never hit");
}

/**
 * Picks the better of two possible matches for a token.
 *
 * @param[in] first candidate node matching token
 * @param[in] second candidate node matching token
 * @param[in] token the token being matched
 * @return the best-matching node, or NULL if the two are entirely ambiguous
 */
static struct cmd_token *disambiguate_tokens(struct cmd_token *first,
					     struct cmd_token *second,
					     char *input_token)
{
	// if the types are different, simply go off of type precedence
	if (first->type != second->type) {
		int firstprec = score_precedence(first->type);
		int secndprec = score_precedence(second->type);
		if (firstprec != secndprec)
			return firstprec < secndprec ? first : second;
		else
			return NULL;
	}

	// if they're the same, return the more exact match
	enum match_type fmtype = match_token(first, input_token);
	enum match_type smtype = match_token(second, input_token);
	if (fmtype != smtype)
		return fmtype > smtype ? first : second;

	return NULL;
}

/**
 * Picks the better of two possible matches for an input line.
 *
 * @param[in] first candidate list of cmd_token matching vline
 * @param[in] second candidate list of cmd_token matching vline
 * @param[in] vline the input line being matched
 * @param[in] n index into vline to start comparing at
 * @return the best-matching list, or NULL if the two are entirely ambiguous
 */
static struct list *disambiguate(struct list *first, struct list *second,
				 vector vline, unsigned int n)
{
	assert(first != NULL);
	assert(second != NULL);
	// doesn't make sense for these to be inequal length
	assert(first->count == second->count);
	assert(first->count == vector_active(vline) - n + 1);

	struct listnode *fnode = listhead_unchecked(first),
			*snode = listhead_unchecked(second);
	struct cmd_token *ftok = listgetdata(fnode), *stok = listgetdata(snode),
			 *best = NULL;

	// compare each token, if one matches better use that one
	for (unsigned int i = n; i < vector_active(vline); i++) {
		char *token = vector_slot(vline, i);
		if ((best = disambiguate_tokens(ftok, stok, token)))
			return best == ftok ? first : second;
		fnode = listnextnode(fnode);
		snode = listnextnode(snode);
		ftok = listgetdata(fnode);
		stok = listgetdata(snode);
	}

	return NULL;
}

/*
 * Deletion function for arglist.
 *
 * Since list->del for arglists expects all listnode->data to hold cmd_token,
 * but arglists have cmd_element as the data for the tail, this function
 * manually deletes the tail before deleting the rest of the list as usual.
 *
 * The cmd_element at the end is *not* a copy. It is the one and only.
 *
 * @param list the arglist to delete
 */
static void del_arglist(struct list *list)
{
	// manually delete last node
	struct listnode *tail = listtail(list);
	tail->data = NULL;
	list_delete_node(list, tail);

	// delete the rest of the list as usual
	list_delete(&list);
}

/*---------- token level matching functions ----------*/

static enum match_type match_token(struct cmd_token *token, char *input_token)
{
	// nothing trivially matches everything
	if (!input_token)
		return trivial_match;

	switch (token->type) {
	case WORD_TKN:
		return match_word(token, input_token);
	case IPV4_TKN:
		return match_ipv4(input_token);
	case IPV4_PREFIX_TKN:
		return match_ipv4_prefix(input_token);
	case IPV6_TKN:
		return match_ipv6_prefix(input_token, false);
	case IPV6_PREFIX_TKN:
		return match_ipv6_prefix(input_token, true);
	case RANGE_TKN:
		return match_range(token, input_token);
	case VARIABLE_TKN:
		return match_variable(token, input_token);
	case MAC_TKN:
		return match_mac(input_token, false);
	case MAC_PREFIX_TKN:
		return match_mac(input_token, true);
	case ASNUM_TKN:
		return asn_str2asn_match(input_token);
	case END_TKN:
	case FORK_TKN:
	case JOIN_TKN:
	case START_TKN:
	case NEG_ONLY_TKN:
		return no_match;
	}

	assert(!"Reached end of function we should never hit");
}

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

static enum match_type match_ipv4(const char *str)
{
	const char *sp;
	int dots = 0, nums = 0;
	char buf[4];

	for (;;) {
		memset(buf, 0, sizeof(buf));
		sp = str;
		while (*str != '\0') {
			if (*str == '.') {
				if (dots >= 3)
					return no_match;

				if (*(str + 1) == '.')
					return no_match;

				if (*(str + 1) == '\0')
					return partly_match;

				dots++;
				break;
			}
			if (!isdigit((unsigned char)*str))
				return no_match;

			str++;
		}

		if (str - sp > 3)
			return no_match;

		memcpy(buf, sp, str - sp);

		int v = atoi(buf);

		if (v > 255)
			return no_match;
		if (v > 0 && buf[0] == '0')
			return no_match;

		nums++;

		if (*str == '\0')
			break;

		str++;
	}

	if (nums < 4)
		return partly_match;

	return exact_match;
}

static enum match_type match_ipv4_prefix(const char *str)
{
	const char *sp;
	int dots = 0;
	char buf[4];

	for (;;) {
		memset(buf, 0, sizeof(buf));
		sp = str;
		while (*str != '\0' && *str != '/') {
			if (*str == '.') {
				if (dots == 3)
					return no_match;

				if (*(str + 1) == '.' || *(str + 1) == '/')
					return no_match;

				if (*(str + 1) == '\0')
					return partly_match;

				dots++;
				break;
			}

			if (!isdigit((unsigned char)*str))
				return no_match;

			str++;
		}

		if (str - sp > 3)
			return no_match;

		memcpy(buf, sp, str - sp);

		int v = atoi(buf);

		if (v > 255)
			return no_match;
		if (v > 0 && buf[0] == '0')
			return no_match;

		if (dots == 3) {
			if (*str == '/') {
				if (*(str + 1) == '\0')
					return partly_match;

				str++;
				break;
			} else if (*str == '\0')
				return partly_match;
		}

		if (*str == '\0')
			return partly_match;

		str++;
	}

	sp = str;
	while (*str != '\0') {
		if (!isdigit((unsigned char)*str))
			return no_match;

		str++;
	}

	if (atoi(sp) > IPV4_MAX_BITLEN)
		return no_match;

	return exact_match;
}

#define IPV6_ADDR_STR   "0123456789abcdefABCDEF:."
#define IPV6_PREFIX_STR "0123456789abcdefABCDEF:./"
#define STATE_START     1
#define STATE_COLON     2
#define STATE_DOUBLE    3
#define STATE_ADDR      4
#define STATE_DOT       5
#define STATE_SLASH     6
#define STATE_MASK      7

static enum match_type match_ipv6_prefix(const char *str, bool prefix)
{
	int state = STATE_START;
	int colons = 0, nums = 0, double_colon = 0;
	int mask;
	const char *sp = NULL, *start = str;
	char *endptr = NULL;

	if (str == NULL)
		return partly_match;

	if (strspn(str, prefix ? IPV6_PREFIX_STR : IPV6_ADDR_STR)
	    != strlen(str))
		return no_match;

	while (*str != '\0' && state != STATE_MASK) {
		switch (state) {
		case STATE_START:
			if (*str == ':') {
				if (*(str + 1) != ':' && *(str + 1) != '\0')
					return no_match;
				colons--;
				state = STATE_COLON;
			} else {
				sp = str;
				state = STATE_ADDR;
			}

			continue;
		case STATE_COLON:
			colons++;
			if (*(str + 1) == '/')
				return no_match;
			else if (*(str + 1) == ':')
				state = STATE_DOUBLE;
			else {
				sp = str + 1;
				state = STATE_ADDR;
			}
			break;
		case STATE_DOUBLE:
			if (double_colon)
				return no_match;

			if (*(str + 1) == ':')
				return no_match;
			else {
				if (*(str + 1) != '\0' && *(str + 1) != '/')
					colons++;
				sp = str + 1;

				if (*(str + 1) == '/')
					state = STATE_SLASH;
				else
					state = STATE_ADDR;
			}

			double_colon++;
			nums += 1;
			break;
		case STATE_ADDR:
			if (*(str + 1) == ':' || *(str + 1) == '.'
			    || *(str + 1) == '\0' || *(str + 1) == '/') {
				if (str - sp > 3)
					return no_match;

				for (; sp <= str; sp++)
					if (*sp == '/')
						return no_match;

				nums++;

				if (*(str + 1) == ':')
					state = STATE_COLON;
				else if (*(str + 1) == '.') {
					if (colons || double_colon)
						state = STATE_DOT;
					else
						return no_match;
				} else if (*(str + 1) == '/')
					state = STATE_SLASH;
			}
			break;
		case STATE_DOT:
			state = STATE_ADDR;
			break;
		case STATE_SLASH:
			if (*(str + 1) == '\0')
				return partly_match;

			state = STATE_MASK;
			break;
		default:
			break;
		}

		if (nums > 11)
			return no_match;

		if (colons > 7)
			return no_match;

		str++;
	}

	if (!prefix) {
		struct sockaddr_in6 sin6_dummy;
		int ret = inet_pton(AF_INET6, start, &sin6_dummy.sin6_addr);
		return ret == 1 ? exact_match : partly_match;
	}

	if (state < STATE_MASK)
		return partly_match;

	mask = strtol(str, &endptr, 10);
	if (*endptr != '\0')
		return no_match;

	if (mask < 0 || mask > IPV6_MAX_BITLEN)
		return no_match;

	return exact_match;
}

static enum match_type match_range(struct cmd_token *token, const char *str)
{
	assert(token->type == RANGE_TKN);

	char *endptr = NULL;
	long long val;

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

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

static enum match_type match_word(struct cmd_token *token, const char *word)
{
	assert(token->type == WORD_TKN);

	// if the passed token is 0 length, partly match
	if (!strlen(word))
		return partly_match;

	// if the passed token is strictly a prefix of the full word, partly
	// match
	if (strlen(word) < strlen(token->text))
		return !strncmp(token->text, word, strlen(word)) ? partly_match
								 : no_match;

	// if they are the same length and exactly equal, exact match
	else if (strlen(word) == strlen(token->text))
		return !strncmp(token->text, word, strlen(word)) ? exact_match
								 : no_match;

	return no_match;
}

static enum match_type match_variable(struct cmd_token *token, const char *word)
{
	assert(token->type == VARIABLE_TKN);
	return exact_match;
}

#define MAC_CHARS "ABCDEFabcdef0123456789:"

static enum match_type match_mac(const char *word, bool prefix)
{
	/* 6 2-digit hex numbers separated by 5 colons */
	size_t mac_explen = 6 * 2 + 5;
	/* '/' + 2-digit integer */
	size_t mask_len = 1 + 2;
	unsigned int i;
	char *eptr;
	unsigned int maskval;

	/* length check */
	if (strlen(word) > mac_explen + (prefix ? mask_len : 0))
		return no_match;

	/* address check */
	for (i = 0; i < mac_explen; i++) {
		if (word[i] == '\0' || !strchr(MAC_CHARS, word[i]))
			break;
		if (((i + 1) % 3 == 0) != (word[i] == ':'))
			return no_match;
	}

	/* incomplete address */
	if (i < mac_explen && word[i] == '\0')
		return partly_match;
	else if (i < mac_explen)
		return no_match;

	/* mask check */
	if (prefix && word[i] == '/') {
		if (word[++i] == '\0')
			return partly_match;

		maskval = strtoul(&word[i], &eptr, 10);
		if (*eptr != '\0' || maskval > 48)
			return no_match;
	} else if (prefix && word[i] == '\0') {
		return partly_match;
	} else if (prefix) {
		return no_match;
	}

	return exact_match;
}