diff options
| -rw-r--r-- | lib/cmdtree.c | 55 | ||||
| -rw-r--r-- | lib/cmdtree.h | 44 | ||||
| -rw-r--r-- | lib/command_parse.y | 25 | ||||
| -rw-r--r-- | lib/grammar_sandbox.c | 27 |
4 files changed, 111 insertions, 40 deletions
diff --git a/lib/cmdtree.c b/lib/cmdtree.c index da647a7ae..38632dca4 100644 --- a/lib/cmdtree.c +++ b/lib/cmdtree.c @@ -13,12 +13,11 @@ struct graph_node * add_node(struct graph_node *parent, struct graph_node *child) { - unsigned int index; struct graph_node *p_child; - for (index = 0; index < vector_active(parent->children); index++) + for (unsigned int i = 0; i < vector_active(parent->children); i++) { - p_child = vector_slot(parent->children, index); + p_child = vector_slot(parent->children, i); if (cmp_node(child, p_child)) return p_child; } @@ -29,7 +28,36 @@ add_node(struct graph_node *parent, struct graph_node *child) int cmp_node(struct graph_node *first, struct graph_node *second) { - return 0; + // compare types + if (first->type != second->type) return 0; + + switch (first->type) { + case WORD_GN: // words and variables are equal if their + case VARIABLE_GN: // text value is equal + if (first->text && second->text) { + if (strcmp(first->text, second->text)) return 0; + } + else if (first->text != second->text) return 0; + break; + case RANGE_GN: // ranges are equal if their bounds are equal + if (first->min != second->min || first->max != second->max) + return 0; + break; + case NUMBER_GN: // numbers are equal if their values are equal + if (first->value != second->value) return 0; + break; + /* selectors and options should be equal if all paths are equal, + * but the graph isomorphism problem is not solvable in polynomial + * time so we consider selectors and options inequal in all cases + */ + case SELECTOR_GN: + case OPTION_GN: + return 0; + default: + break; + } + + return 1; } struct graph_node * @@ -40,6 +68,11 @@ new_node(enum graph_node_type type) node->children = vector_init(VECTOR_MIN_SIZE); node->is_leaf = 0; node->is_root = 0; + node->end = NULL; + node->text = NULL; + node->value = 0; + node->min = 0; + node->max = 0; node->func = NULL; return node; @@ -77,22 +110,24 @@ walk_graph(struct graph_node *start, int level) fprintf(stderr, "[%d] ", vector_active(start->children)); if (vector_active(start->children)) - for (unsigned int i = 0; i < vector_active(start->children); i++) { + for (unsigned int i = 0; i < vector_active(start->children); i++) + { struct graph_node *r = vector_slot(start->children, i); if (!r) { fprintf(stderr, "Child seems null?\n"); break; } else { - if (start->type == OPTION_GN || start->type == SELECTOR_GN) { + if (vector_active(start->children) > 1) { fprintf(stderr, "\n"); for (int i = 0; i < level+1; i++) - fprintf(stderr, "\t"); + fprintf(stderr, " "); + walk_graph(r, level+1); } - walk_graph(r, level+1); + else + walk_graph(r, level); } } - else { + if (level == 0) fprintf(stderr, "\n"); - } } diff --git a/lib/cmdtree.h b/lib/cmdtree.h index 9b512e3bb..3d2366b00 100644 --- a/lib/cmdtree.h +++ b/lib/cmdtree.h @@ -20,20 +20,23 @@ struct graph_node { enum graph_node_type type; vector children; - int is_root; // true if first token in command - int is_leaf; // true if last token in command + int is_root; // true if first token in command + int is_leaf; // true if last token in command + struct graph_node * end; // pointer to end for selector & option int (*func)(struct vty *, int, const char *[]); /* various data fields for nodes */ char* text; // for words and variables int value; // for numbers - int start, end; // for ranges + int min, max; // for ranges }; /* - * Adds a child to a node. If the node already has the exact same - * child, nothing is done. + * Adds a child to a node. + * If the node already has the exact same child, nothing is done. This is + * decided with cmp_node. + * * @param[in] parent node * @param[in] child node * @return the new child, or the existing child if the parent already has the @@ -43,16 +46,35 @@ extern struct graph_node * add_node(struct graph_node *, struct graph_node *); /* - * Compares two nodes for equivalence. - * What exactly constitutes two nodes being equal depends on the - * node type. - * @return 0 if equal, nonzero otherwise. + * Compares two nodes for parsing equivalence. + * Equivalence in this case means that a single user input token + * should be able to unambiguously match one of the two nodes. + * For example, two nodes which have all fields equal except their + * function pointers would be considered equal. + * + * @param[in] first node to compare + * @param[in] second node to compare + * @return 1 if equal, zero otherwise. */ extern int -cmp_node(struct graph_node *first, struct graph_node *second); +cmp_node(struct graph_node *, struct graph_node *); +/* + * Create a new node. + * Initializes all fields to default values and sets the node type. + * + * @param[in] node type + * @return pointer to the newly allocated node + */ extern struct graph_node * -new_node(enum graph_node_type type); +new_node(enum graph_node_type); +/** + * Walks a command DFA, printing structure to stdout. + * For debugging. + * + * @param[in] start node of graph to walk + * @param[in] graph depth for recursion, caller passes 0 + */ extern void walk_graph(struct graph_node *, int); diff --git a/lib/command_parse.y b/lib/command_parse.y index 7bdec6dca..cf2cd95bd 100644 --- a/lib/command_parse.y +++ b/lib/command_parse.y @@ -48,7 +48,7 @@ struct graph_node *selnode_start, // start node for selector set %type <node> option_token %type <node> option_token_seq %type <node> selector -%type <node> selector_root +%type <node> selector_element_root %type <node> selector_token %type <node> selector_token_seq @@ -70,7 +70,7 @@ sentence_root: WORD currnode = $$; currnode->is_root = 1; - add_node(startnode, currnode); + currnode = add_node(startnode, currnode); }; /* valid top level tokens */ @@ -106,22 +106,22 @@ placeholder_token: $$->text = strdup(yylval.string); } | IPV4_PREFIX -{ +{ $$ = new_node(IPV4_PREFIX_GN); $$->text = strdup(yylval.string); } | IPV6 -{ +{ $$ = new_node(IPV6_GN); $$->text = strdup(yylval.string); } | IPV6_PREFIX -{ +{ $$ = new_node(IPV6_PREFIX_GN); $$->text = strdup(yylval.string); } | VARIABLE -{ +{ $$ = new_node(VARIABLE_GN); $$->text = strdup(yylval.string); } @@ -132,9 +132,9 @@ placeholder_token: // get the numbers out strsep(&yylval.string, "(-)"); - $$->start = atoi( strsep(&yylval.string, "(-)") ); + $$->min = atoi( strsep(&yylval.string, "(-)") ); strsep(&yylval.string, "(-)"); - $$->end = atoi( strsep(&yylval.string, "(-)") ); + $$->max = atoi( strsep(&yylval.string, "(-)") ); // we could do this a variety of ways with either // the lexer or the parser, but this is the simplest @@ -148,7 +148,7 @@ literal_token: $$ = new_node(WORD_GN); $$->text = strdup(yylval.string); fprintf(stderr, ">>>>>>>> YYLVAL.STRING: %s\n", yylval.string); - fprintf(stderr, ">>>>>>>> TEXT: %s\n", $$->text); + fprintf(stderr, ">>>>>>>> TEXT: %s\n", $$->text); } | NUMBER { @@ -172,13 +172,14 @@ selector_part: ; selector_element: - selector_root selector_token_seq + selector_element_root selector_token_seq { // if the selector start and end do not exist, create them if (!selnode_start || !selnode_end) { // if one is null assert(!selnode_start && !selnode_end); // both should be null selnode_start = new_node(SELECTOR_GN); // diverging node selnode_end = new_node(NUL_GN); // converging node + selnode_start->end = selnode_end; // duh } // add element head as a child of the selector @@ -210,13 +211,13 @@ selector_token_seq: } ; -selector_root: +selector_element_root: literal_token | placeholder_token ; selector_token: - selector_root + selector_element_root | option ; diff --git a/lib/grammar_sandbox.c b/lib/grammar_sandbox.c index 0cc6896d8..807ada9d9 100644 --- a/lib/grammar_sandbox.c +++ b/lib/grammar_sandbox.c @@ -4,9 +4,11 @@ #define GRAMMAR_STR "CLI grammar sandbox\n" +struct graph_node * nodegraph; + DEFUN (grammar_test, grammar_test_cmd, - "grammar .COMMAND", + "grammar parse .COMMAND", GRAMMAR_STR "command to pass to new parser\n") { @@ -22,17 +24,28 @@ DEFUN (grammar_test, strcat(cat, " "); } - struct graph_node *result = new_node(NUL_GN); - /* cmd_parse_format_new((const char*) cat, "lol", result);*/ - cmd_parse_format_new ("test <command|options> lol", "lol", result); - cmd_parse_format_new ("test <command|options> lol", "lol", result); - walk_graph(result, 0); - + //struct graph_node *result = new_node(NUL_GN); + cmd_parse_format_new((const char*) cat, "lol", nodegraph); + walk_graph(nodegraph, 0); + return CMD_SUCCESS; } +DEFUN (grammar_test_show, + grammar_test_show_cmd, + "grammar tree", + GRAMMAR_STR + "print current accumulated DFA\n") +{ + walk_graph(nodegraph, 0); + return CMD_SUCCESS; +} + void grammar_sandbox_init(void); void grammar_sandbox_init() { + fprintf(stderr, "reinitializing graph\n"); + nodegraph = new_node(NUL_GN); install_element (ENABLE_NODE, &grammar_test_cmd); + install_element (ENABLE_NODE, &grammar_test_show_cmd); } |