]>
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"
31 DEFINE_MTYPE_STATIC(LIB
, CMD_TOKENS
, "Command Tokens")
32 DEFINE_MTYPE_STATIC(LIB
, CMD_DESC
, "Command Token Text")
33 DEFINE_MTYPE_STATIC(LIB
, CMD_TEXT
, "Command Token Help")
34 DEFINE_MTYPE(LIB
, CMD_ARG
, "Command Argument")
35 DEFINE_MTYPE_STATIC(LIB
, CMD_VAR
, "Command Argument Name")
37 struct cmd_token
*cmd_token_new(enum cmd_token_type type
, uint8_t attr
,
38 const char *text
, const char *desc
)
40 struct cmd_token
*token
=
41 XCALLOC(MTYPE_CMD_TOKENS
, sizeof(struct cmd_token
));
44 token
->text
= text
? XSTRDUP(MTYPE_CMD_TEXT
, text
) : NULL
;
45 token
->desc
= desc
? XSTRDUP(MTYPE_CMD_DESC
, desc
) : NULL
;
48 token
->allowrepeat
= false;
49 token
->varname
= NULL
;
54 void cmd_token_del(struct cmd_token
*token
)
59 XFREE(MTYPE_CMD_TEXT
, token
->text
);
60 XFREE(MTYPE_CMD_DESC
, token
->desc
);
61 XFREE(MTYPE_CMD_ARG
, token
->arg
);
62 XFREE(MTYPE_CMD_VAR
, token
->varname
);
64 XFREE(MTYPE_CMD_TOKENS
, token
);
67 struct cmd_token
*cmd_token_dup(struct cmd_token
*token
)
69 struct cmd_token
*copy
=
70 cmd_token_new(token
->type
, token
->attr
, NULL
, NULL
);
71 copy
->max
= token
->max
;
72 copy
->min
= token
->min
;
73 copy
->text
= token
->text
? XSTRDUP(MTYPE_CMD_TEXT
, token
->text
) : NULL
;
74 copy
->desc
= token
->desc
? XSTRDUP(MTYPE_CMD_DESC
, token
->desc
) : NULL
;
75 copy
->arg
= token
->arg
? XSTRDUP(MTYPE_CMD_ARG
, token
->arg
) : NULL
;
77 token
->varname
? XSTRDUP(MTYPE_CMD_VAR
, token
->varname
) : NULL
;
82 void cmd_token_varname_set(struct cmd_token
*token
, const char *varname
)
84 XFREE(MTYPE_CMD_VAR
, token
->varname
);
86 token
->varname
= NULL
;
90 size_t len
= strlen(varname
), i
;
91 token
->varname
= XMALLOC(MTYPE_CMD_VAR
, len
+ 1);
93 for (i
= 0; i
< len
; i
++)
99 token
->varname
[i
] = '_';
102 token
->varname
[i
] = tolower((int)varname
[i
]);
104 token
->varname
[len
] = '\0';
107 static bool cmd_nodes_link(struct graph_node
*from
, struct graph_node
*to
)
109 for (size_t i
= 0; i
< vector_active(from
->to
); i
++)
110 if (vector_slot(from
->to
, i
) == to
)
115 static bool cmd_nodes_equal(struct graph_node
*ga
, struct graph_node
*gb
);
117 /* returns a single node to be excluded as "next" from iteration
118 * - for JOIN_TKN, never continue back to the FORK_TKN
119 * - in all other cases, don't try the node itself (in case of "...")
121 static inline struct graph_node
*cmd_loopstop(struct graph_node
*gn
)
123 struct cmd_token
*tok
= gn
->data
;
124 if (tok
->type
== JOIN_TKN
)
125 return tok
->forkjoin
;
130 static bool cmd_subgraph_equal(struct graph_node
*ga
, struct graph_node
*gb
,
131 struct graph_node
*a_join
)
134 struct graph_node
*a_fork
, *b_fork
;
135 a_fork
= cmd_loopstop(ga
);
136 b_fork
= cmd_loopstop(gb
);
138 if (vector_active(ga
->to
) != vector_active(gb
->to
))
140 for (i
= 0; i
< vector_active(ga
->to
); i
++) {
141 struct graph_node
*cga
= vector_slot(ga
->to
, i
);
143 for (j
= 0; j
< vector_active(gb
->to
); j
++) {
144 struct graph_node
*cgb
= vector_slot(gb
->to
, i
);
146 if (cga
== a_fork
&& cgb
!= b_fork
)
148 if (cga
== a_fork
&& cgb
== b_fork
)
151 if (cmd_nodes_equal(cga
, cgb
)) {
154 if (cmd_subgraph_equal(cga
, cgb
, a_join
))
158 if (j
== vector_active(gb
->to
))
164 /* deep compare -- for FORK_TKN, the entire subgraph is compared.
165 * this is what's needed since we're not currently trying to partially
167 static bool cmd_nodes_equal(struct graph_node
*ga
, struct graph_node
*gb
)
169 struct cmd_token
*a
= ga
->data
, *b
= gb
->data
;
171 if (a
->type
!= b
->type
|| a
->allowrepeat
!= b
->allowrepeat
)
173 if (a
->type
< SPECIAL_TKN
&& strcmp(a
->text
, b
->text
))
175 /* one a ..., the other not. */
176 if (cmd_nodes_link(ga
, ga
) != cmd_nodes_link(gb
, gb
))
178 if (!a
->varname
!= !b
->varname
)
180 if (a
->varname
&& strcmp(a
->varname
, b
->varname
))
185 return a
->min
== b
->min
&& a
->max
== b
->max
;
188 /* one is keywords, the other just option or selector ... */
189 if (cmd_nodes_link(a
->forkjoin
, ga
)
190 != cmd_nodes_link(b
->forkjoin
, gb
))
192 if (cmd_nodes_link(ga
, a
->forkjoin
)
193 != cmd_nodes_link(gb
, b
->forkjoin
))
195 return cmd_subgraph_equal(ga
, gb
, a
->forkjoin
);
202 static void cmd_fork_bump_attr(struct graph_node
*gn
, struct graph_node
*join
,
206 struct cmd_token
*tok
= gn
->data
;
207 struct graph_node
*stop
= cmd_loopstop(gn
);
210 for (i
= 0; i
< vector_active(gn
->to
); i
++) {
211 struct graph_node
*next
= vector_slot(gn
->to
, i
);
212 if (next
== stop
|| next
== join
)
214 cmd_fork_bump_attr(next
, join
, attr
);
218 /* move an entire subtree from the temporary graph resulting from
219 * parse() into the permanent graph for the command node.
221 * this touches rather deeply into the graph code unfortunately.
223 static void cmd_reparent_tree(struct graph
*fromgraph
, struct graph
*tograph
,
224 struct graph_node
*node
)
226 struct graph_node
*stop
= cmd_loopstop(node
);
229 for (i
= 0; i
< vector_active(fromgraph
->nodes
); i
++)
230 if (vector_slot(fromgraph
->nodes
, i
) == node
) {
231 /* agressive iteration punching through subgraphs - may
233 * nodes twice. reparent only if found on old graph */
234 vector_unset(fromgraph
->nodes
, i
);
235 vector_set(tograph
->nodes
, node
);
239 for (i
= 0; i
< vector_active(node
->to
); i
++) {
240 struct graph_node
*next
= vector_slot(node
->to
, i
);
242 cmd_reparent_tree(fromgraph
, tograph
, next
);
246 static void cmd_free_recur(struct graph
*graph
, struct graph_node
*node
,
247 struct graph_node
*stop
)
249 struct graph_node
*next
, *nstop
;
251 for (size_t i
= vector_active(node
->to
); i
; i
--) {
252 next
= vector_slot(node
->to
, i
- 1);
255 nstop
= cmd_loopstop(next
);
257 cmd_free_recur(graph
, next
, nstop
);
258 cmd_free_recur(graph
, nstop
, stop
);
260 graph_delete_node(graph
, node
);
263 static void cmd_free_node(struct graph
*graph
, struct graph_node
*node
)
265 struct cmd_token
*tok
= node
->data
;
266 if (tok
->type
== JOIN_TKN
)
267 cmd_free_recur(graph
, tok
->forkjoin
, node
);
268 graph_delete_node(graph
, node
);
271 /* recursive graph merge. call with
273 * (which holds true for old == START_TKN, new == START_TKN)
275 static void cmd_merge_nodes(struct graph
*oldgraph
, struct graph
*newgraph
,
276 struct graph_node
*old
, struct graph_node
*new,
279 struct cmd_token
*tok
;
280 struct graph_node
*old_skip
, *new_skip
;
281 old_skip
= cmd_loopstop(old
);
282 new_skip
= cmd_loopstop(new);
284 assert(direction
== 1 || direction
== -1);
287 tok
->refcnt
+= direction
;
290 for (j
= 0; j
< vector_active(new->to
); j
++) {
291 struct graph_node
*cnew
= vector_slot(new->to
, j
);
292 if (cnew
== new_skip
)
295 for (i
= 0; i
< vector_active(old
->to
); i
++) {
296 struct graph_node
*cold
= vector_slot(old
->to
, i
);
297 if (cold
== old_skip
)
300 if (cmd_nodes_equal(cold
, cnew
)) {
301 struct cmd_token
*told
= cold
->data
,
304 if (told
->type
== END_TKN
) {
308 vector_slot(cold
->to
,
310 graph_delete_node(oldgraph
,
313 /* force no-match handling to
315 i
= vector_active(old
->to
);
319 /* the entire fork compared as equal, we
320 * continue after it. */
321 if (told
->type
== FORK_TKN
) {
322 if (tnew
->attr
< told
->attr
325 cold
, told
->forkjoin
,
327 /* XXX: no reverse bump on uninstall */
328 told
= (cold
= told
->forkjoin
)->data
;
329 tnew
= (cnew
= tnew
->forkjoin
)->data
;
331 if (tnew
->attr
< told
->attr
)
332 told
->attr
= tnew
->attr
;
334 cmd_merge_nodes(oldgraph
, newgraph
, cold
, cnew
,
339 /* nothing found => add new to old */
340 if (i
== vector_active(old
->to
) && direction
> 0) {
341 graph_remove_edge(new, cnew
);
343 cmd_reparent_tree(newgraph
, oldgraph
, cnew
);
345 graph_add_edge(old
, cnew
);
350 cmd_free_node(oldgraph
, old
);
353 void cmd_graph_merge(struct graph
*old
, struct graph
*new, int direction
)
355 assert(vector_active(old
->nodes
) >= 1);
356 assert(vector_active(new->nodes
) >= 1);
358 cmd_merge_nodes(old
, new, vector_slot(old
->nodes
, 0),
359 vector_slot(new->nodes
, 0), direction
);
362 static void cmd_node_names(struct graph_node
*gn
, struct graph_node
*join
,
363 const char *prevname
)
366 struct cmd_token
*tok
= gn
->data
, *jointok
;
367 struct graph_node
*stop
= cmd_loopstop(gn
);
371 prevname
= tok
->text
;
375 if (!tok
->varname
&& strcmp(tok
->text
, "WORD")
376 && strcmp(tok
->text
, "NAME"))
377 cmd_token_varname_set(tok
, tok
->text
);
381 case IPV4_PREFIX_TKN
:
383 case IPV6_PREFIX_TKN
:
386 if (!tok
->varname
&& prevname
)
387 cmd_token_varname_set(tok
, prevname
);
393 /* "<foo|bar> WORD" -> word is not "bar" or "foo" */
398 /* apply "<A.B.C.D|X:X::X:X>$name" */
399 jointok
= tok
->forkjoin
->data
;
400 if (!jointok
->varname
)
402 for (i
= 0; i
< vector_active(tok
->forkjoin
->from
); i
++) {
403 struct graph_node
*tail
=
404 vector_slot(tok
->forkjoin
->from
, i
);
405 struct cmd_token
*tailtok
= tail
->data
;
406 if (tail
== gn
|| tailtok
->varname
)
408 cmd_token_varname_set(tailtok
, jointok
->varname
);
416 for (i
= 0; i
< vector_active(gn
->to
); i
++) {
417 struct graph_node
*next
= vector_slot(gn
->to
, i
);
418 if (next
== stop
|| next
== join
)
420 cmd_node_names(next
, join
, prevname
);
423 if (tok
->type
== FORK_TKN
&& tok
->forkjoin
!= join
)
424 cmd_node_names(tok
->forkjoin
, join
, NULL
);
427 void cmd_graph_names(struct graph
*graph
)
429 struct graph_node
*start
;
431 assert(vector_active(graph
->nodes
) >= 1);
432 start
= vector_slot(graph
->nodes
, 0);
434 /* apply varname on initial "[no]" */
436 if (vector_active(start
->to
) != 1)
439 struct graph_node
*first
= vector_slot(start
->to
, 0);
440 struct cmd_token
*tok
= first
->data
;
441 /* looking for an option with 2 choices, nothing or "no" */
442 if (tok
->type
!= FORK_TKN
|| vector_active(first
->to
) != 2)
445 struct graph_node
*next0
= vector_slot(first
->to
, 0);
446 struct graph_node
*next1
= vector_slot(first
->to
, 1);
447 /* one needs to be empty */
448 if (next0
!= tok
->forkjoin
&& next1
!= tok
->forkjoin
)
451 struct cmd_token
*tok0
= next0
->data
;
452 struct cmd_token
*tok1
= next1
->data
;
453 /* the other one needs to be "no" (only one will match here) */
454 if ((tok0
->type
== WORD_TKN
&& !strcmp(tok0
->text
, "no")))
455 cmd_token_varname_set(tok0
, "no");
456 if ((tok1
->type
== WORD_TKN
&& !strcmp(tok1
->text
, "no")))
457 cmd_token_varname_set(tok1
, "no");
460 cmd_node_names(start
, NULL
, NULL
);
463 #ifndef BUILDING_CLIPPY
465 void cmd_graph_node_print_cb(struct graph_node
*gn
, struct buffer
*buf
)
470 struct cmd_token
*tok
= gn
->data
;
473 if (wasend
== true) {
478 if (tok
->type
== END_TKN
) {
483 snprintf(nbuf
, sizeof(nbuf
), " n%p [ shape=box, label=<", gn
);
484 buffer_putstr(buf
, nbuf
);
485 snprintf(nbuf
, sizeof(nbuf
), "<b>%s</b>",
486 lookup_msg(tokennames
, tok
->type
, NULL
));
487 buffer_putstr(buf
, nbuf
);
488 if (tok
->attr
== CMD_ATTR_DEPRECATED
)
489 buffer_putstr(buf
, " (d)");
490 else if (tok
->attr
== CMD_ATTR_HIDDEN
)
491 buffer_putstr(buf
, " (h)");
493 if (tok
->type
== WORD_TKN
)
496 "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",
499 snprintf(nbuf
, sizeof(nbuf
), "<br/>%s", tok
->text
);
500 buffer_putstr(buf
, nbuf
);
520 snprintf(nbuf
, sizeof(nbuf
),
521 ">, style = filled, fillcolor = \"%s\" ];\n", color
);
522 buffer_putstr(buf
, nbuf
);
524 for (unsigned int i
= 0; i
< vector_active(gn
->to
); i
++) {
525 struct graph_node
*adj
= vector_slot(gn
->to
, i
);
527 if (((struct cmd_token
*)adj
->data
)->type
== END_TKN
) {
528 snprintf(nbuf
, sizeof(nbuf
), " n%p -> end%p;\n", gn
,
530 buffer_putstr(buf
, nbuf
);
533 " end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",
536 snprintf(nbuf
, sizeof(nbuf
), " n%p -> n%p;\n", gn
,
539 buffer_putstr(buf
, nbuf
);
543 char *cmd_graph_dump_dot(struct graph
*cmdgraph
)
545 struct graph_node
*start
= vector_slot(cmdgraph
->nodes
, 0);
547 return graph_dump_dot(cmdgraph
, start
, cmd_graph_node_print_cb
);
550 #endif /* BUILDING_CLIPPY */