]>
git.proxmox.com Git - mirror_frr.git/blob - lib/command_graph.c
5 * Copyright (C) 2016 Cumulus Networks, Inc.
6 * Copyright (C) 1997, 98, 99 Kunihiro Ishiguro
7 * Copyright (C) 2013 by Open Source Routing.
8 * Copyright (C) 2013 by Internet Systems Consortium, Inc. ("ISC")
10 * This program is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by the Free
12 * Software Foundation; either version 2 of the License, or (at your option)
15 * This program is distributed in the hope that it will be useful, but WITHOUT
16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
20 * You should have received a copy of the GNU General Public License along
21 * with this program; see the file COPYING; if not, write to the Free Software
22 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 #include "command_graph.h"
29 DEFINE_MTYPE_STATIC(LIB
, CMD_TOKENS
, "Command Tokens");
30 DEFINE_MTYPE_STATIC(LIB
, CMD_DESC
, "Command Token Text");
31 DEFINE_MTYPE_STATIC(LIB
, CMD_TEXT
, "Command Token Help");
32 DEFINE_MTYPE(LIB
, CMD_ARG
, "Command Argument");
33 DEFINE_MTYPE_STATIC(LIB
, CMD_VAR
, "Command Argument Name");
35 struct cmd_token
*cmd_token_new(enum cmd_token_type type
, uint8_t attr
,
36 const char *text
, const char *desc
)
38 struct cmd_token
*token
=
39 XCALLOC(MTYPE_CMD_TOKENS
, sizeof(struct cmd_token
));
42 token
->text
= text
? XSTRDUP(MTYPE_CMD_TEXT
, text
) : NULL
;
43 token
->desc
= desc
? XSTRDUP(MTYPE_CMD_DESC
, desc
) : NULL
;
46 token
->allowrepeat
= false;
47 token
->varname
= NULL
;
52 void cmd_token_del(struct cmd_token
*token
)
57 XFREE(MTYPE_CMD_TEXT
, token
->text
);
58 XFREE(MTYPE_CMD_DESC
, token
->desc
);
59 XFREE(MTYPE_CMD_ARG
, token
->arg
);
60 XFREE(MTYPE_CMD_VAR
, token
->varname
);
62 XFREE(MTYPE_CMD_TOKENS
, token
);
65 struct cmd_token
*cmd_token_dup(struct cmd_token
*token
)
67 struct cmd_token
*copy
=
68 cmd_token_new(token
->type
, token
->attr
, NULL
, NULL
);
69 copy
->max
= token
->max
;
70 copy
->min
= token
->min
;
71 copy
->text
= token
->text
? XSTRDUP(MTYPE_CMD_TEXT
, token
->text
) : NULL
;
72 copy
->desc
= token
->desc
? XSTRDUP(MTYPE_CMD_DESC
, token
->desc
) : NULL
;
73 copy
->arg
= token
->arg
? XSTRDUP(MTYPE_CMD_ARG
, token
->arg
) : NULL
;
75 token
->varname
? XSTRDUP(MTYPE_CMD_VAR
, token
->varname
) : NULL
;
80 void cmd_token_varname_set(struct cmd_token
*token
, const char *varname
)
82 XFREE(MTYPE_CMD_VAR
, token
->varname
);
84 token
->varname
= NULL
;
88 size_t len
= strlen(varname
), i
;
89 token
->varname
= XMALLOC(MTYPE_CMD_VAR
, len
+ 1);
91 for (i
= 0; i
< len
; i
++)
97 token
->varname
[i
] = '_';
100 token
->varname
[i
] = tolower((unsigned char)varname
[i
]);
102 token
->varname
[len
] = '\0';
105 static bool cmd_nodes_link(struct graph_node
*from
, struct graph_node
*to
)
107 for (size_t i
= 0; i
< vector_active(from
->to
); i
++)
108 if (vector_slot(from
->to
, i
) == to
)
113 static bool cmd_nodes_equal(struct graph_node
*ga
, struct graph_node
*gb
);
115 /* returns a single node to be excluded as "next" from iteration
116 * - for JOIN_TKN, never continue back to the FORK_TKN
117 * - in all other cases, don't try the node itself (in case of "...")
119 static inline struct graph_node
*cmd_loopstop(struct graph_node
*gn
)
121 struct cmd_token
*tok
= gn
->data
;
122 if (tok
->type
== JOIN_TKN
)
123 return tok
->forkjoin
;
128 static bool cmd_subgraph_equal(struct graph_node
*ga
, struct graph_node
*gb
,
129 struct graph_node
*a_join
)
132 struct graph_node
*a_fork
, *b_fork
;
133 a_fork
= cmd_loopstop(ga
);
134 b_fork
= cmd_loopstop(gb
);
136 if (vector_active(ga
->to
) != vector_active(gb
->to
))
138 for (i
= 0; i
< vector_active(ga
->to
); i
++) {
139 struct graph_node
*cga
= vector_slot(ga
->to
, i
);
141 for (j
= 0; j
< vector_active(gb
->to
); j
++) {
142 struct graph_node
*cgb
= vector_slot(gb
->to
, i
);
144 if (cga
== a_fork
&& cgb
!= b_fork
)
146 if (cga
== a_fork
&& cgb
== b_fork
)
149 if (cmd_nodes_equal(cga
, cgb
)) {
152 if (cmd_subgraph_equal(cga
, cgb
, a_join
))
156 if (j
== vector_active(gb
->to
))
162 /* deep compare -- for FORK_TKN, the entire subgraph is compared.
163 * this is what's needed since we're not currently trying to partially
165 static bool cmd_nodes_equal(struct graph_node
*ga
, struct graph_node
*gb
)
167 struct cmd_token
*a
= ga
->data
, *b
= gb
->data
;
169 if (a
->type
!= b
->type
|| a
->allowrepeat
!= b
->allowrepeat
)
171 if (a
->type
< SPECIAL_TKN
&& strcmp(a
->text
, b
->text
))
173 /* one a ..., the other not. */
174 if (cmd_nodes_link(ga
, ga
) != cmd_nodes_link(gb
, gb
))
176 if (!a
->varname
!= !b
->varname
)
178 if (a
->varname
&& strcmp(a
->varname
, b
->varname
))
183 return a
->min
== b
->min
&& a
->max
== b
->max
;
186 /* one is keywords, the other just option or selector ... */
187 if (cmd_nodes_link(a
->forkjoin
, ga
)
188 != cmd_nodes_link(b
->forkjoin
, gb
))
190 if (cmd_nodes_link(ga
, a
->forkjoin
)
191 != cmd_nodes_link(gb
, b
->forkjoin
))
193 return cmd_subgraph_equal(ga
, gb
, a
->forkjoin
);
200 static void cmd_fork_bump_attr(struct graph_node
*gn
, struct graph_node
*join
,
204 struct cmd_token
*tok
= gn
->data
;
205 struct graph_node
*stop
= cmd_loopstop(gn
);
208 for (i
= 0; i
< vector_active(gn
->to
); i
++) {
209 struct graph_node
*next
= vector_slot(gn
->to
, i
);
210 if (next
== stop
|| next
== join
)
212 cmd_fork_bump_attr(next
, join
, attr
);
216 /* move an entire subtree from the temporary graph resulting from
217 * parse() into the permanent graph for the command node.
219 * this touches rather deeply into the graph code unfortunately.
221 static void cmd_reparent_tree(struct graph
*fromgraph
, struct graph
*tograph
,
222 struct graph_node
*node
)
224 struct graph_node
*stop
= cmd_loopstop(node
);
227 for (i
= 0; i
< vector_active(fromgraph
->nodes
); i
++)
228 if (vector_slot(fromgraph
->nodes
, i
) == node
) {
229 /* agressive iteration punching through subgraphs - may
231 * nodes twice. reparent only if found on old graph */
232 vector_unset(fromgraph
->nodes
, i
);
233 vector_set(tograph
->nodes
, node
);
237 for (i
= 0; i
< vector_active(node
->to
); i
++) {
238 struct graph_node
*next
= vector_slot(node
->to
, i
);
240 cmd_reparent_tree(fromgraph
, tograph
, next
);
244 static void cmd_free_recur(struct graph
*graph
, struct graph_node
*node
,
245 struct graph_node
*stop
)
247 struct graph_node
*next
, *nstop
;
249 for (size_t i
= vector_active(node
->to
); i
; i
--) {
250 next
= vector_slot(node
->to
, i
- 1);
253 nstop
= cmd_loopstop(next
);
255 cmd_free_recur(graph
, next
, nstop
);
256 cmd_free_recur(graph
, nstop
, stop
);
258 graph_delete_node(graph
, node
);
261 static void cmd_free_node(struct graph
*graph
, struct graph_node
*node
)
263 struct cmd_token
*tok
= node
->data
;
264 if (tok
->type
== JOIN_TKN
)
265 cmd_free_recur(graph
, tok
->forkjoin
, node
);
266 graph_delete_node(graph
, node
);
269 /* recursive graph merge. call with
271 * (which holds true for old == START_TKN, new == START_TKN)
273 static void cmd_merge_nodes(struct graph
*oldgraph
, struct graph
*newgraph
,
274 struct graph_node
*old
, struct graph_node
*new,
277 struct cmd_token
*tok
;
278 struct graph_node
*old_skip
, *new_skip
;
279 old_skip
= cmd_loopstop(old
);
280 new_skip
= cmd_loopstop(new);
282 assert(direction
== 1 || direction
== -1);
285 tok
->refcnt
+= direction
;
288 for (j
= 0; j
< vector_active(new->to
); j
++) {
289 struct graph_node
*cnew
= vector_slot(new->to
, j
);
290 if (cnew
== new_skip
)
293 for (i
= 0; i
< vector_active(old
->to
); i
++) {
294 struct graph_node
*cold
= vector_slot(old
->to
, i
);
295 if (cold
== old_skip
)
298 if (cmd_nodes_equal(cold
, cnew
)) {
299 struct cmd_token
*told
= cold
->data
,
302 if (told
->type
== END_TKN
) {
306 vector_slot(cold
->to
,
308 graph_delete_node(oldgraph
,
311 /* force no-match handling to
313 i
= vector_active(old
->to
);
317 /* the entire fork compared as equal, we
318 * continue after it. */
319 if (told
->type
== FORK_TKN
) {
320 if (tnew
->attr
< told
->attr
323 cold
, told
->forkjoin
,
325 /* XXX: no reverse bump on uninstall */
326 told
= (cold
= told
->forkjoin
)->data
;
327 tnew
= (cnew
= tnew
->forkjoin
)->data
;
329 if (tnew
->attr
< told
->attr
)
330 told
->attr
= tnew
->attr
;
332 cmd_merge_nodes(oldgraph
, newgraph
, cold
, cnew
,
337 /* nothing found => add new to old */
338 if (i
== vector_active(old
->to
) && direction
> 0) {
339 graph_remove_edge(new, cnew
);
341 cmd_reparent_tree(newgraph
, oldgraph
, cnew
);
343 graph_add_edge(old
, cnew
);
348 cmd_free_node(oldgraph
, old
);
351 void cmd_graph_merge(struct graph
*old
, struct graph
*new, int direction
)
353 assert(vector_active(old
->nodes
) >= 1);
354 assert(vector_active(new->nodes
) >= 1);
356 cmd_merge_nodes(old
, new, vector_slot(old
->nodes
, 0),
357 vector_slot(new->nodes
, 0), direction
);
360 static void cmd_node_names(struct graph_node
*gn
, struct graph_node
*join
,
361 const char *prevname
)
364 struct cmd_token
*tok
= gn
->data
, *jointok
;
365 struct graph_node
*stop
= cmd_loopstop(gn
);
369 prevname
= tok
->text
;
373 if (!tok
->varname
&& strcmp(tok
->text
, "WORD")
374 && strcmp(tok
->text
, "NAME"))
375 cmd_token_varname_set(tok
, tok
->text
);
379 case IPV4_PREFIX_TKN
:
381 case IPV6_PREFIX_TKN
:
384 if (!tok
->varname
&& prevname
)
385 cmd_token_varname_set(tok
, prevname
);
392 /* "<foo|bar> WORD" -> word is not "bar" or "foo" */
397 /* apply "<A.B.C.D|X:X::X:X>$name" */
398 jointok
= tok
->forkjoin
->data
;
399 if (!jointok
->varname
)
401 for (i
= 0; i
< vector_active(tok
->forkjoin
->from
); i
++) {
402 struct graph_node
*tail
=
403 vector_slot(tok
->forkjoin
->from
, i
);
404 struct cmd_token
*tailtok
= tail
->data
;
405 if (tail
== gn
|| tailtok
->varname
)
407 cmd_token_varname_set(tailtok
, jointok
->varname
);
415 for (i
= 0; i
< vector_active(gn
->to
); i
++) {
416 struct graph_node
*next
= vector_slot(gn
->to
, i
);
417 if (next
== stop
|| next
== join
)
419 cmd_node_names(next
, join
, prevname
);
422 if (tok
->type
== FORK_TKN
&& tok
->forkjoin
!= join
)
423 cmd_node_names(tok
->forkjoin
, join
, NULL
);
426 void cmd_graph_names(struct graph
*graph
)
428 struct graph_node
*start
;
430 assert(vector_active(graph
->nodes
) >= 1);
431 start
= vector_slot(graph
->nodes
, 0);
433 /* apply varname on initial "[no]" */
435 if (vector_active(start
->to
) != 1)
438 struct graph_node
*first
= vector_slot(start
->to
, 0);
439 struct cmd_token
*tok
= first
->data
;
440 /* looking for an option with 2 choices, nothing or "no" */
441 if (tok
->type
!= FORK_TKN
|| vector_active(first
->to
) != 2)
444 struct graph_node
*next0
= vector_slot(first
->to
, 0);
445 struct graph_node
*next1
= vector_slot(first
->to
, 1);
446 /* one needs to be empty */
447 if (next0
!= tok
->forkjoin
&& next1
!= tok
->forkjoin
)
450 struct cmd_token
*tok0
= next0
->data
;
451 struct cmd_token
*tok1
= next1
->data
;
452 /* the other one needs to be "no" (only one will match here) */
453 if ((tok0
->type
== WORD_TKN
&& !strcmp(tok0
->text
, "no")))
454 cmd_token_varname_set(tok0
, "no");
455 if ((tok1
->type
== WORD_TKN
&& !strcmp(tok1
->text
, "no")))
456 cmd_token_varname_set(tok1
, "no");
459 cmd_node_names(start
, NULL
, NULL
);
462 #ifndef BUILDING_CLIPPY
467 void cmd_graph_node_print_cb(struct graph_node
*gn
, struct buffer
*buf
)
472 struct cmd_token
*tok
= gn
->data
;
480 if (tok
->type
== END_TKN
) {
485 snprintf(nbuf
, sizeof(nbuf
), " n%p [ shape=box, label=<", gn
);
486 buffer_putstr(buf
, nbuf
);
487 snprintf(nbuf
, sizeof(nbuf
), "<b>%s</b>",
488 lookup_msg(tokennames
, tok
->type
, NULL
));
489 buffer_putstr(buf
, nbuf
);
490 if (tok
->attr
== CMD_ATTR_DEPRECATED
)
491 buffer_putstr(buf
, " (d)");
492 else if (tok
->attr
== CMD_ATTR_HIDDEN
)
493 buffer_putstr(buf
, " (h)");
495 if (tok
->type
== WORD_TKN
)
498 "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",
501 snprintf(nbuf
, sizeof(nbuf
), "<br/>%s", tok
->text
);
502 buffer_putstr(buf
, nbuf
);
525 snprintf(nbuf
, sizeof(nbuf
),
526 ">, style = filled, fillcolor = \"%s\" ];\n", color
);
527 buffer_putstr(buf
, nbuf
);
529 for (unsigned int i
= 0; i
< vector_active(gn
->to
); i
++) {
530 struct graph_node
*adj
= vector_slot(gn
->to
, i
);
532 if (((struct cmd_token
*)adj
->data
)->type
== END_TKN
) {
533 snprintf(nbuf
, sizeof(nbuf
), " n%p -> end%p;\n", gn
,
535 buffer_putstr(buf
, nbuf
);
538 " end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",
541 snprintf(nbuf
, sizeof(nbuf
), " n%p -> n%p;\n", gn
,
544 buffer_putstr(buf
, nbuf
);
548 char *cmd_graph_dump_dot(struct graph
*cmdgraph
)
550 struct graph_node
*start
= vector_slot(cmdgraph
->nodes
, 0);
552 return graph_dump_dot(cmdgraph
, start
, cmd_graph_node_print_cb
);
555 #endif /* BUILDING_CLIPPY */