]>
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 static void cmd_token_varname_do(struct cmd_token
*token
, const char *varname
,
83 if (token
->varname_src
>= varname_src
)
86 XFREE(MTYPE_CMD_VAR
, token
->varname
);
88 size_t len
= strlen(varname
), i
;
89 token
->varname
= XMALLOC(MTYPE_CMD_VAR
, len
+ 1);
90 token
->varname_src
= varname_src
;
92 for (i
= 0; i
< len
; i
++)
98 token
->varname
[i
] = '_';
101 token
->varname
[i
] = tolower((unsigned char)varname
[i
]);
103 token
->varname
[len
] = '\0';
106 void cmd_token_varname_set(struct cmd_token
*token
, const char *varname
)
109 cmd_token_varname_do(token
, varname
, VARNAME_EXPLICIT
);
112 if (token
->type
== VARIABLE_TKN
) {
113 if (strcmp(token
->text
, "WORD") && strcmp(token
->text
, "NAME"))
114 cmd_token_varname_do(token
, token
->text
, VARNAME_TEXT
);
118 static void cmd_token_varname_fork(struct graph_node
*node
,
119 struct cmd_token
*prevtoken
)
121 for (size_t i
= 0; i
< vector_active(node
->to
); i
++) {
122 struct graph_node
*next
= vector_slot(node
->to
, i
);
123 struct cmd_token
*nexttoken
= next
->data
;
125 if (nexttoken
->type
== FORK_TKN
) {
126 cmd_token_varname_fork(next
, prevtoken
);
129 if (nexttoken
->varname
)
131 if (!IS_VARYING_TOKEN(nexttoken
->type
))
134 cmd_token_varname_do(nexttoken
, prevtoken
->text
, VARNAME_TEXT
);
138 void cmd_token_varname_join(struct graph_node
*join
, const char *varname
)
143 for (size_t i
= 0; i
< vector_active(join
->from
); i
++) {
144 struct graph_node
*prev
= vector_slot(join
->from
, i
);
145 struct cmd_token
*token
= prev
->data
;
147 if (token
->type
== JOIN_TKN
)
148 cmd_token_varname_join(prev
, varname
);
149 else if (token
->type
< SPECIAL_TKN
)
150 cmd_token_varname_do(token
, varname
, VARNAME_EXPLICIT
);
154 void cmd_token_varname_seqappend(struct graph_node
*node
)
156 struct graph_node
*prevnode
= node
;
157 struct cmd_token
*token
= node
->data
;
158 struct cmd_token
*prevtoken
;
160 if (token
->type
== WORD_TKN
)
164 if (vector_active(prevnode
->from
) != 1)
167 prevnode
= vector_slot(prevnode
->from
, 0);
168 prevtoken
= prevnode
->data
;
169 } while (prevtoken
->type
== FORK_TKN
);
171 if (prevtoken
->type
!= WORD_TKN
)
174 if (token
->type
== FORK_TKN
)
175 cmd_token_varname_fork(node
, prevtoken
);
177 cmd_token_varname_do(token
, prevtoken
->text
, VARNAME_TEXT
);
180 static bool cmd_nodes_link(struct graph_node
*from
, struct graph_node
*to
)
182 for (size_t i
= 0; i
< vector_active(from
->to
); i
++)
183 if (vector_slot(from
->to
, i
) == to
)
188 static bool cmd_nodes_equal(struct graph_node
*ga
, struct graph_node
*gb
);
190 /* returns a single node to be excluded as "next" from iteration
191 * - for JOIN_TKN, never continue back to the FORK_TKN
192 * - in all other cases, don't try the node itself (in case of "...")
194 static inline struct graph_node
*cmd_loopstop(struct graph_node
*gn
)
196 struct cmd_token
*tok
= gn
->data
;
197 if (tok
->type
== JOIN_TKN
)
198 return tok
->forkjoin
;
203 static bool cmd_subgraph_equal(struct graph_node
*ga
, struct graph_node
*gb
,
204 struct graph_node
*a_join
)
207 struct graph_node
*a_fork
, *b_fork
;
208 a_fork
= cmd_loopstop(ga
);
209 b_fork
= cmd_loopstop(gb
);
211 if (vector_active(ga
->to
) != vector_active(gb
->to
))
213 for (i
= 0; i
< vector_active(ga
->to
); i
++) {
214 struct graph_node
*cga
= vector_slot(ga
->to
, i
);
216 for (j
= 0; j
< vector_active(gb
->to
); j
++) {
217 struct graph_node
*cgb
= vector_slot(gb
->to
, i
);
219 if (cga
== a_fork
&& cgb
!= b_fork
)
221 if (cga
== a_fork
&& cgb
== b_fork
)
224 if (cmd_nodes_equal(cga
, cgb
)) {
227 if (cmd_subgraph_equal(cga
, cgb
, a_join
))
231 if (j
== vector_active(gb
->to
))
237 /* deep compare -- for FORK_TKN, the entire subgraph is compared.
238 * this is what's needed since we're not currently trying to partially
240 static bool cmd_nodes_equal(struct graph_node
*ga
, struct graph_node
*gb
)
242 struct cmd_token
*a
= ga
->data
, *b
= gb
->data
;
244 if (a
->type
!= b
->type
|| a
->allowrepeat
!= b
->allowrepeat
)
246 if (a
->type
< SPECIAL_TKN
&& strcmp(a
->text
, b
->text
))
248 /* one a ..., the other not. */
249 if (cmd_nodes_link(ga
, ga
) != cmd_nodes_link(gb
, gb
))
251 if (!a
->varname
!= !b
->varname
)
253 if (a
->varname
&& strcmp(a
->varname
, b
->varname
))
258 return a
->min
== b
->min
&& a
->max
== b
->max
;
261 /* one is keywords, the other just option or selector ... */
262 if (cmd_nodes_link(a
->forkjoin
, ga
)
263 != cmd_nodes_link(b
->forkjoin
, gb
))
265 if (cmd_nodes_link(ga
, a
->forkjoin
)
266 != cmd_nodes_link(gb
, b
->forkjoin
))
268 return cmd_subgraph_equal(ga
, gb
, a
->forkjoin
);
275 static void cmd_fork_bump_attr(struct graph_node
*gn
, struct graph_node
*join
,
279 struct cmd_token
*tok
= gn
->data
;
280 struct graph_node
*stop
= cmd_loopstop(gn
);
283 for (i
= 0; i
< vector_active(gn
->to
); i
++) {
284 struct graph_node
*next
= vector_slot(gn
->to
, i
);
285 if (next
== stop
|| next
== join
)
287 cmd_fork_bump_attr(next
, join
, attr
);
291 /* move an entire subtree from the temporary graph resulting from
292 * parse() into the permanent graph for the command node.
294 * this touches rather deeply into the graph code unfortunately.
296 static void cmd_reparent_tree(struct graph
*fromgraph
, struct graph
*tograph
,
297 struct graph_node
*node
)
299 struct graph_node
*stop
= cmd_loopstop(node
);
302 for (i
= 0; i
< vector_active(fromgraph
->nodes
); i
++)
303 if (vector_slot(fromgraph
->nodes
, i
) == node
) {
304 /* agressive iteration punching through subgraphs - may
306 * nodes twice. reparent only if found on old graph */
307 vector_unset(fromgraph
->nodes
, i
);
308 vector_set(tograph
->nodes
, node
);
312 for (i
= 0; i
< vector_active(node
->to
); i
++) {
313 struct graph_node
*next
= vector_slot(node
->to
, i
);
315 cmd_reparent_tree(fromgraph
, tograph
, next
);
319 static void cmd_free_recur(struct graph
*graph
, struct graph_node
*node
,
320 struct graph_node
*stop
)
322 struct graph_node
*next
, *nstop
;
324 for (size_t i
= vector_active(node
->to
); i
; i
--) {
325 next
= vector_slot(node
->to
, i
- 1);
328 nstop
= cmd_loopstop(next
);
330 cmd_free_recur(graph
, next
, nstop
);
331 cmd_free_recur(graph
, nstop
, stop
);
333 graph_delete_node(graph
, node
);
336 static void cmd_free_node(struct graph
*graph
, struct graph_node
*node
)
338 struct cmd_token
*tok
= node
->data
;
339 if (tok
->type
== JOIN_TKN
)
340 cmd_free_recur(graph
, tok
->forkjoin
, node
);
341 graph_delete_node(graph
, node
);
344 /* recursive graph merge. call with
346 * (which holds true for old == START_TKN, new == START_TKN)
348 static void cmd_merge_nodes(struct graph
*oldgraph
, struct graph
*newgraph
,
349 struct graph_node
*old
, struct graph_node
*new,
352 struct cmd_token
*tok
;
353 struct graph_node
*old_skip
, *new_skip
;
354 old_skip
= cmd_loopstop(old
);
355 new_skip
= cmd_loopstop(new);
357 assert(direction
== 1 || direction
== -1);
360 tok
->refcnt
+= direction
;
363 for (j
= 0; j
< vector_active(new->to
); j
++) {
364 struct graph_node
*cnew
= vector_slot(new->to
, j
);
365 if (cnew
== new_skip
)
368 for (i
= 0; i
< vector_active(old
->to
); i
++) {
369 struct graph_node
*cold
= vector_slot(old
->to
, i
);
370 if (cold
== old_skip
)
373 if (cmd_nodes_equal(cold
, cnew
)) {
374 struct cmd_token
*told
= cold
->data
,
377 if (told
->type
== END_TKN
) {
381 vector_slot(cold
->to
,
383 graph_delete_node(oldgraph
,
386 /* force no-match handling to
388 i
= vector_active(old
->to
);
392 /* the entire fork compared as equal, we
393 * continue after it. */
394 if (told
->type
== FORK_TKN
) {
395 if (tnew
->attr
< told
->attr
398 cold
, told
->forkjoin
,
400 /* XXX: no reverse bump on uninstall */
401 told
= (cold
= told
->forkjoin
)->data
;
402 tnew
= (cnew
= tnew
->forkjoin
)->data
;
404 if (tnew
->attr
< told
->attr
)
405 told
->attr
= tnew
->attr
;
407 cmd_merge_nodes(oldgraph
, newgraph
, cold
, cnew
,
412 /* nothing found => add new to old */
413 if (i
== vector_active(old
->to
) && direction
> 0) {
414 graph_remove_edge(new, cnew
);
416 cmd_reparent_tree(newgraph
, oldgraph
, cnew
);
418 graph_add_edge(old
, cnew
);
423 cmd_free_node(oldgraph
, old
);
426 void cmd_graph_merge(struct graph
*old
, struct graph
*new, int direction
)
428 assert(vector_active(old
->nodes
) >= 1);
429 assert(vector_active(new->nodes
) >= 1);
431 cmd_merge_nodes(old
, new, vector_slot(old
->nodes
, 0),
432 vector_slot(new->nodes
, 0), direction
);
435 void cmd_graph_names(struct graph
*graph
)
437 struct graph_node
*start
;
439 assert(vector_active(graph
->nodes
) >= 1);
440 start
= vector_slot(graph
->nodes
, 0);
442 /* apply varname on initial "[no]" */
444 if (vector_active(start
->to
) != 1)
447 struct graph_node
*first
= vector_slot(start
->to
, 0);
448 struct cmd_token
*tok
= first
->data
;
449 /* looking for an option with 2 choices, nothing or "no" */
450 if (tok
->type
!= FORK_TKN
|| vector_active(first
->to
) != 2)
453 struct graph_node
*next0
= vector_slot(first
->to
, 0);
454 struct graph_node
*next1
= vector_slot(first
->to
, 1);
455 /* one needs to be empty */
456 if (next0
!= tok
->forkjoin
&& next1
!= tok
->forkjoin
)
459 struct cmd_token
*tok0
= next0
->data
;
460 struct cmd_token
*tok1
= next1
->data
;
461 /* the other one needs to be "no" (only one will match here) */
462 if ((tok0
->type
== WORD_TKN
&& !strcmp(tok0
->text
, "no")))
463 cmd_token_varname_do(tok0
, "no", VARNAME_AUTO
);
464 if ((tok1
->type
== WORD_TKN
&& !strcmp(tok1
->text
, "no")))
465 cmd_token_varname_do(tok1
, "no", VARNAME_AUTO
);
469 #ifndef BUILDING_CLIPPY
474 void cmd_graph_node_print_cb(struct graph_node
*gn
, struct buffer
*buf
)
479 struct cmd_token
*tok
= gn
->data
;
487 if (tok
->type
== END_TKN
) {
492 snprintf(nbuf
, sizeof(nbuf
), " n%p [ shape=box, label=<", gn
);
493 buffer_putstr(buf
, nbuf
);
494 snprintf(nbuf
, sizeof(nbuf
), "<b>%s</b>",
495 lookup_msg(tokennames
, tok
->type
, NULL
));
496 buffer_putstr(buf
, nbuf
);
497 if (tok
->attr
& CMD_ATTR_DEPRECATED
)
498 buffer_putstr(buf
, " (d)");
499 /* DEPRECATED implies HIDDEN, don't print both */
500 else if (tok
->attr
& CMD_ATTR_HIDDEN
)
501 buffer_putstr(buf
, " (h)");
503 if (tok
->type
== WORD_TKN
)
506 "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",
509 snprintf(nbuf
, sizeof(nbuf
), "<br/>%s", tok
->text
);
510 buffer_putstr(buf
, nbuf
);
533 snprintf(nbuf
, sizeof(nbuf
),
534 ">, style = filled, fillcolor = \"%s\" ];\n", color
);
535 buffer_putstr(buf
, nbuf
);
537 for (unsigned int i
= 0; i
< vector_active(gn
->to
); i
++) {
538 struct graph_node
*adj
= vector_slot(gn
->to
, i
);
540 if (((struct cmd_token
*)adj
->data
)->type
== END_TKN
) {
541 snprintf(nbuf
, sizeof(nbuf
), " n%p -> end%p;\n", gn
,
543 buffer_putstr(buf
, nbuf
);
546 " end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",
549 snprintf(nbuf
, sizeof(nbuf
), " n%p -> n%p;\n", gn
,
552 buffer_putstr(buf
, nbuf
);
556 char *cmd_graph_dump_dot(struct graph
*cmdgraph
)
558 struct graph_node
*start
= vector_slot(cmdgraph
->nodes
, 0);
560 return graph_dump_dot(cmdgraph
, start
, cmd_graph_node_print_cb
);
563 #endif /* BUILDING_CLIPPY */