]>
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")
36 cmd_token_new (enum cmd_token_type type
, u_char attr
,
37 const char *text
, const char *desc
)
39 struct cmd_token
*token
= 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
;
53 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
);
66 cmd_token_dup (struct cmd_token
*token
)
68 struct cmd_token
*copy
= 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
;
74 copy
->varname
= token
->varname
? XSTRDUP (MTYPE_CMD_VAR
, token
->varname
) : NULL
;
79 void cmd_token_varname_set(struct cmd_token
*token
, const char *varname
)
81 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
++)
98 token
->varname
[i
] = '_';
101 token
->varname
[i
] = tolower (varname
[i
]);
103 token
->varname
[len
] = '\0';
107 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
*
122 cmd_loopstop(struct graph_node
*gn
)
124 struct cmd_token
*tok
= gn
->data
;
125 if (tok
->type
== JOIN_TKN
)
126 return tok
->forkjoin
;
132 cmd_subgraph_equal (struct graph_node
*ga
, struct graph_node
*gb
,
133 struct graph_node
*a_join
)
136 struct graph_node
*a_fork
, *b_fork
;
137 a_fork
= cmd_loopstop (ga
);
138 b_fork
= cmd_loopstop (gb
);
140 if (vector_active (ga
->to
) != vector_active (gb
->to
))
142 for (i
= 0; i
< vector_active (ga
->to
); i
++)
144 struct graph_node
*cga
= vector_slot (ga
->to
, i
);
146 for (j
= 0; j
< vector_active (gb
->to
); j
++)
148 struct graph_node
*cgb
= vector_slot (gb
->to
, i
);
150 if (cga
== a_fork
&& cgb
!= b_fork
)
152 if (cga
== a_fork
&& cgb
== b_fork
)
155 if (cmd_nodes_equal (cga
, cgb
))
159 if (cmd_subgraph_equal (cga
, cgb
, a_join
))
163 if (j
== vector_active (gb
->to
))
169 /* deep compare -- for FORK_TKN, the entire subgraph is compared.
170 * this is what's needed since we're not currently trying to partially
173 cmd_nodes_equal (struct graph_node
*ga
, struct graph_node
*gb
)
175 struct cmd_token
*a
= ga
->data
, *b
= gb
->data
;
177 if (a
->type
!= b
->type
|| a
->allowrepeat
!= b
->allowrepeat
)
179 if (a
->type
< SPECIAL_TKN
&& strcmp (a
->text
, b
->text
))
181 /* one a ..., the other not. */
182 if (cmd_nodes_link (ga
, ga
) != cmd_nodes_link (gb
, gb
))
184 if (!a
->varname
!= !b
->varname
)
186 if (a
->varname
&& strcmp (a
->varname
, b
->varname
))
192 return a
->min
== b
->min
&& a
->max
== b
->max
;
195 /* one is keywords, the other just option or selector ... */
196 if (cmd_nodes_link (a
->forkjoin
, ga
) != cmd_nodes_link (b
->forkjoin
, gb
))
198 if (cmd_nodes_link (ga
, a
->forkjoin
) != cmd_nodes_link (gb
, b
->forkjoin
))
200 return cmd_subgraph_equal (ga
, gb
, a
->forkjoin
);
208 cmd_fork_bump_attr (struct graph_node
*gn
, struct graph_node
*join
,
212 struct cmd_token
*tok
= gn
->data
;
213 struct graph_node
*stop
= cmd_loopstop (gn
);
216 for (i
= 0; i
< vector_active (gn
->to
); i
++)
218 struct graph_node
*next
= vector_slot (gn
->to
, i
);
219 if (next
== stop
|| next
== join
)
221 cmd_fork_bump_attr (next
, join
, attr
);
225 /* move an entire subtree from the temporary graph resulting from
226 * parse() into the permanent graph for the command node.
228 * this touches rather deeply into the graph code unfortunately.
231 cmd_reparent_tree (struct graph
*fromgraph
, struct graph
*tograph
,
232 struct graph_node
*node
)
234 struct graph_node
*stop
= cmd_loopstop (node
);
237 for (i
= 0; i
< vector_active (fromgraph
->nodes
); i
++)
238 if (vector_slot (fromgraph
->nodes
, i
) == node
)
240 /* agressive iteration punching through subgraphs - may hit some
241 * nodes twice. reparent only if found on old graph */
242 vector_unset (fromgraph
->nodes
, i
);
243 vector_set (tograph
->nodes
, node
);
247 for (i
= 0; i
< vector_active (node
->to
); i
++)
249 struct graph_node
*next
= vector_slot (node
->to
, i
);
251 cmd_reparent_tree (fromgraph
, tograph
, next
);
256 cmd_free_recur (struct graph
*graph
, struct graph_node
*node
,
257 struct graph_node
*stop
)
259 struct graph_node
*next
, *nstop
;
261 for (size_t i
= vector_active (node
->to
); i
; i
--)
263 next
= vector_slot (node
->to
, i
- 1);
266 nstop
= cmd_loopstop (next
);
268 cmd_free_recur (graph
, next
, nstop
);
269 cmd_free_recur (graph
, nstop
, stop
);
271 graph_delete_node (graph
, node
);
275 cmd_free_node (struct graph
*graph
, struct graph_node
*node
)
277 struct cmd_token
*tok
= node
->data
;
278 if (tok
->type
== JOIN_TKN
)
279 cmd_free_recur (graph
, tok
->forkjoin
, node
);
280 graph_delete_node (graph
, node
);
283 /* recursive graph merge. call with
285 * (which holds true for old == START_TKN, new == START_TKN)
288 cmd_merge_nodes (struct graph
*oldgraph
, struct graph
*newgraph
,
289 struct graph_node
*old
, struct graph_node
*new,
292 struct cmd_token
*tok
;
293 struct graph_node
*old_skip
, *new_skip
;
294 old_skip
= cmd_loopstop (old
);
295 new_skip
= cmd_loopstop (new);
297 assert (direction
== 1 || direction
== -1);
300 tok
->refcnt
+= direction
;
303 for (j
= 0; j
< vector_active (new->to
); j
++)
305 struct graph_node
*cnew
= vector_slot (new->to
, j
);
306 if (cnew
== new_skip
)
309 for (i
= 0; i
< vector_active (old
->to
); i
++)
311 struct graph_node
*cold
= vector_slot (old
->to
, i
);
312 if (cold
== old_skip
)
315 if (cmd_nodes_equal (cold
, cnew
))
317 struct cmd_token
*told
= cold
->data
, *tnew
= cnew
->data
;
319 if (told
->type
== END_TKN
)
323 graph_delete_node (oldgraph
, vector_slot (cold
->to
, 0));
324 graph_delete_node (oldgraph
, cold
);
327 /* force no-match handling to install END_TKN */
328 i
= vector_active (old
->to
);
332 /* the entire fork compared as equal, we continue after it. */
333 if (told
->type
== FORK_TKN
)
335 if (tnew
->attr
< told
->attr
&& direction
> 0)
336 cmd_fork_bump_attr (cold
, told
->forkjoin
, tnew
->attr
);
337 /* XXX: no reverse bump on uninstall */
338 told
= (cold
= told
->forkjoin
)->data
;
339 tnew
= (cnew
= tnew
->forkjoin
)->data
;
341 if (tnew
->attr
< told
->attr
)
342 told
->attr
= tnew
->attr
;
344 cmd_merge_nodes (oldgraph
, newgraph
, cold
, cnew
, direction
);
348 /* nothing found => add new to old */
349 if (i
== vector_active (old
->to
) && direction
> 0)
351 graph_remove_edge (new, cnew
);
353 cmd_reparent_tree (newgraph
, oldgraph
, cnew
);
355 graph_add_edge (old
, cnew
);
360 cmd_free_node (oldgraph
, old
);
364 cmd_graph_merge (struct graph
*old
, struct graph
*new, int direction
)
366 assert (vector_active (old
->nodes
) >= 1);
367 assert (vector_active (new->nodes
) >= 1);
369 cmd_merge_nodes (old
, new,
370 vector_slot (old
->nodes
, 0), vector_slot (new->nodes
, 0),
375 cmd_node_names (struct graph_node
*gn
, struct graph_node
*join
,
376 const char *prevname
)
379 struct cmd_token
*tok
= gn
->data
, *jointok
;
380 struct graph_node
*stop
= cmd_loopstop (gn
);
385 prevname
= tok
->text
;
390 && strcmp (tok
->text
, "WORD")
391 && strcmp (tok
->text
, "NAME"))
392 cmd_token_varname_set (tok
, tok
->text
);
396 case IPV4_PREFIX_TKN
:
398 case IPV6_PREFIX_TKN
:
399 if (!tok
->varname
&& prevname
)
400 cmd_token_varname_set (tok
, prevname
);
407 /* "<foo|bar> WORD" -> word is not "bar" or "foo" */
412 /* apply "<A.B.C.D|X:X::X:X>$name" */
413 jointok
= tok
->forkjoin
->data
;
414 if (!jointok
->varname
)
416 for (i
= 0; i
< vector_active (tok
->forkjoin
->from
); i
++)
418 struct graph_node
*tail
= vector_slot (tok
->forkjoin
->from
, i
);
419 struct cmd_token
*tailtok
= tail
->data
;
420 if (tail
== gn
|| tailtok
->varname
)
422 cmd_token_varname_set (tailtok
, jointok
->varname
);
427 for (i
= 0; i
< vector_active (gn
->to
); i
++)
429 struct graph_node
*next
= vector_slot (gn
->to
, i
);
430 if (next
== stop
|| next
== join
)
432 cmd_node_names (next
, join
, prevname
);
435 if (tok
->type
== FORK_TKN
&& tok
->forkjoin
!= join
)
436 cmd_node_names (tok
->forkjoin
, join
, NULL
);
440 cmd_graph_names (struct graph
*graph
)
442 struct graph_node
*start
;
444 assert (vector_active (graph
->nodes
) >= 1);
445 start
= vector_slot (graph
->nodes
, 0);
447 /* apply varname on initial "[no]" */
450 if (vector_active (start
->to
) != 1)
453 struct graph_node
*first
= vector_slot (start
->to
, 0);
454 struct cmd_token
*tok
= first
->data
;
455 /* looking for an option with 2 choices, nothing or "no" */
456 if (tok
->type
!= FORK_TKN
|| vector_active (first
->to
) != 2)
459 struct graph_node
*next0
= vector_slot (first
->to
, 0);
460 struct graph_node
*next1
= vector_slot (first
->to
, 1);
461 /* one needs to be empty */
462 if (next0
!= tok
->forkjoin
&& next1
!= tok
->forkjoin
)
465 struct cmd_token
*tok0
= next0
->data
;
466 struct cmd_token
*tok1
= next1
->data
;
467 /* the other one needs to be "no" (only one will match here) */
468 if ((tok0
->type
== WORD_TKN
&& !strcmp(tok0
->text
, "no")))
469 cmd_token_varname_set (tok0
, "no");
470 if ((tok1
->type
== WORD_TKN
&& !strcmp(tok1
->text
, "no")))
471 cmd_token_varname_set (tok1
, "no");
475 cmd_node_names (start
, NULL
, NULL
);