]>
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 with
21 * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
22 * Place, Suite 330, Boston, MA 02111-1307 USA
27 #include "command_graph.h"
29 DECLARE_MTYPE(CMD_TOKEN_DATA
)
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")
38 cmd_token_new (enum cmd_token_type type
, u_char attr
,
39 const char *text
, const char *desc
)
41 struct cmd_token
*token
= 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
;
55 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
);
68 cmd_token_dup (struct cmd_token
*token
)
70 struct cmd_token
*copy
= 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
;
76 copy
->varname
= token
->varname
? XSTRDUP (MTYPE_CMD_VAR
, token
->varname
) : NULL
;
81 void cmd_token_varname_set(struct cmd_token
*token
, const char *varname
)
83 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
++)
100 token
->varname
[i
] = '_';
103 token
->varname
[i
] = tolower (varname
[i
]);
105 token
->varname
[len
] = '\0';
109 cmd_nodes_link (struct graph_node
*from
, struct graph_node
*to
)
111 for (size_t i
= 0; i
< vector_active (from
->to
); i
++)
112 if (vector_slot (from
->to
, i
) == to
)
117 static bool cmd_nodes_equal (struct graph_node
*ga
, struct graph_node
*gb
);
119 /* returns a single node to be excluded as "next" from iteration
120 * - for JOIN_TKN, never continue back to the FORK_TKN
121 * - in all other cases, don't try the node itself (in case of "...")
123 static inline struct graph_node
*
124 cmd_loopstop(struct graph_node
*gn
)
126 struct cmd_token
*tok
= gn
->data
;
127 if (tok
->type
== JOIN_TKN
)
128 return tok
->forkjoin
;
134 cmd_subgraph_equal (struct graph_node
*ga
, struct graph_node
*gb
,
135 struct graph_node
*a_join
)
138 struct graph_node
*a_fork
, *b_fork
;
139 a_fork
= cmd_loopstop (ga
);
140 b_fork
= cmd_loopstop (gb
);
142 if (vector_active (ga
->to
) != vector_active (gb
->to
))
144 for (i
= 0; i
< vector_active (ga
->to
); i
++)
146 struct graph_node
*cga
= vector_slot (ga
->to
, i
);
148 for (j
= 0; j
< vector_active (gb
->to
); j
++)
150 struct graph_node
*cgb
= vector_slot (gb
->to
, i
);
152 if (cga
== a_fork
&& cgb
!= b_fork
)
154 if (cga
== a_fork
&& cgb
== b_fork
)
157 if (cmd_nodes_equal (cga
, cgb
))
161 if (cmd_subgraph_equal (cga
, cgb
, a_join
))
165 if (j
== vector_active (gb
->to
))
171 /* deep compare -- for FORK_TKN, the entire subgraph is compared.
172 * this is what's needed since we're not currently trying to partially
175 cmd_nodes_equal (struct graph_node
*ga
, struct graph_node
*gb
)
177 struct cmd_token
*a
= ga
->data
, *b
= gb
->data
;
179 if (a
->type
!= b
->type
|| a
->allowrepeat
!= b
->allowrepeat
)
181 if (a
->type
< SPECIAL_TKN
&& strcmp (a
->text
, b
->text
))
183 /* one a ..., the other not. */
184 if (cmd_nodes_link (ga
, ga
) != cmd_nodes_link (gb
, gb
))
186 if (!a
->varname
!= !b
->varname
)
188 if (a
->varname
&& strcmp (a
->varname
, b
->varname
))
194 return a
->min
== b
->min
&& a
->max
== b
->max
;
197 /* one is keywords, the other just option or selector ... */
198 if (cmd_nodes_link (a
->forkjoin
, ga
) != cmd_nodes_link (b
->forkjoin
, gb
))
200 if (cmd_nodes_link (ga
, a
->forkjoin
) != cmd_nodes_link (gb
, b
->forkjoin
))
202 return cmd_subgraph_equal (ga
, gb
, a
->forkjoin
);
210 cmd_fork_bump_attr (struct graph_node
*gn
, struct graph_node
*join
,
214 struct cmd_token
*tok
= gn
->data
;
215 struct graph_node
*stop
= cmd_loopstop (gn
);
218 for (i
= 0; i
< vector_active (gn
->to
); i
++)
220 struct graph_node
*next
= vector_slot (gn
->to
, i
);
221 if (next
== stop
|| next
== join
)
223 cmd_fork_bump_attr (next
, join
, attr
);
227 /* move an entire subtree from the temporary graph resulting from
228 * parse() into the permanent graph for the command node.
230 * this touches rather deeply into the graph code unfortunately.
233 cmd_reparent_tree (struct graph
*fromgraph
, struct graph
*tograph
,
234 struct graph_node
*node
)
236 struct graph_node
*stop
= cmd_loopstop (node
);
239 for (i
= 0; i
< vector_active (fromgraph
->nodes
); i
++)
240 if (vector_slot (fromgraph
->nodes
, i
) == node
)
242 /* agressive iteration punching through subgraphs - may hit some
243 * nodes twice. reparent only if found on old graph */
244 vector_unset (fromgraph
->nodes
, i
);
245 vector_set (tograph
->nodes
, node
);
249 for (i
= 0; i
< vector_active (node
->to
); i
++)
251 struct graph_node
*next
= vector_slot (node
->to
, i
);
253 cmd_reparent_tree (fromgraph
, tograph
, next
);
258 cmd_free_recur (struct graph
*graph
, struct graph_node
*node
,
259 struct graph_node
*stop
)
261 struct graph_node
*next
, *nstop
;
263 for (size_t i
= vector_active (node
->to
); i
; i
--)
265 next
= vector_slot (node
->to
, i
- 1);
268 nstop
= cmd_loopstop (next
);
270 cmd_free_recur (graph
, next
, nstop
);
271 cmd_free_recur (graph
, nstop
, stop
);
273 graph_delete_node (graph
, node
);
277 cmd_free_node (struct graph
*graph
, struct graph_node
*node
)
279 struct cmd_token
*tok
= node
->data
;
280 if (tok
->type
== JOIN_TKN
)
281 cmd_free_recur (graph
, tok
->forkjoin
, node
);
282 graph_delete_node (graph
, node
);
285 /* recursive graph merge. call with
287 * (which holds true for old == START_TKN, new == START_TKN)
290 cmd_merge_nodes (struct graph
*oldgraph
, struct graph
*newgraph
,
291 struct graph_node
*old
, struct graph_node
*new,
294 struct cmd_token
*tok
;
295 struct graph_node
*old_skip
, *new_skip
;
296 old_skip
= cmd_loopstop (old
);
297 new_skip
= cmd_loopstop (new);
299 assert (direction
== 1 || direction
== -1);
302 tok
->refcnt
+= direction
;
305 for (j
= 0; j
< vector_active (new->to
); j
++)
307 struct graph_node
*cnew
= vector_slot (new->to
, j
);
308 if (cnew
== new_skip
)
311 for (i
= 0; i
< vector_active (old
->to
); i
++)
313 struct graph_node
*cold
= vector_slot (old
->to
, i
);
314 if (cold
== old_skip
)
317 if (cmd_nodes_equal (cold
, cnew
))
319 struct cmd_token
*told
= cold
->data
, *tnew
= cnew
->data
;
321 if (told
->type
== END_TKN
)
325 graph_delete_node (oldgraph
, vector_slot (cold
->to
, 0));
326 graph_delete_node (oldgraph
, cold
);
329 /* force no-match handling to install END_TKN */
330 i
= vector_active (old
->to
);
334 /* the entire fork compared as equal, we continue after it. */
335 if (told
->type
== FORK_TKN
)
337 if (tnew
->attr
< told
->attr
&& direction
> 0)
338 cmd_fork_bump_attr (cold
, told
->forkjoin
, tnew
->attr
);
339 /* XXX: no reverse bump on uninstall */
340 told
= (cold
= told
->forkjoin
)->data
;
341 tnew
= (cnew
= tnew
->forkjoin
)->data
;
343 if (tnew
->attr
< told
->attr
)
344 told
->attr
= tnew
->attr
;
346 cmd_merge_nodes (oldgraph
, newgraph
, cold
, cnew
, direction
);
350 /* nothing found => add new to old */
351 if (i
== vector_active (old
->to
) && direction
> 0)
353 assert (vector_count (cnew
->from
) ==
354 cmd_nodes_link (cnew
, cnew
) ? 2 : 1);
355 graph_remove_edge (new, cnew
);
357 cmd_reparent_tree (newgraph
, oldgraph
, cnew
);
359 graph_add_edge (old
, cnew
);
364 cmd_free_node (oldgraph
, old
);
368 cmd_graph_merge (struct graph
*old
, struct graph
*new, int direction
)
370 assert (vector_active (old
->nodes
) >= 1);
371 assert (vector_active (new->nodes
) >= 1);
373 cmd_merge_nodes (old
, new,
374 vector_slot (old
->nodes
, 0), vector_slot (new->nodes
, 0),
379 cmd_node_names (struct graph_node
*gn
, struct graph_node
*join
,
380 const char *prevname
)
383 struct cmd_token
*tok
= gn
->data
, *jointok
;
384 struct graph_node
*stop
= cmd_loopstop (gn
);
389 prevname
= tok
->text
;
394 && strcmp (tok
->text
, "WORD")
395 && strcmp (tok
->text
, "NAME"))
396 cmd_token_varname_set (tok
, tok
->text
);
400 case IPV4_PREFIX_TKN
:
402 case IPV6_PREFIX_TKN
:
403 if (!tok
->varname
&& prevname
)
404 cmd_token_varname_set (tok
, prevname
);
411 /* "<foo|bar> WORD" -> word is not "bar" or "foo" */
416 /* apply "<A.B.C.D|X:X::X:X>$name" */
417 jointok
= tok
->forkjoin
->data
;
418 if (!jointok
->varname
)
420 for (i
= 0; i
< vector_active (tok
->forkjoin
->from
); i
++)
422 struct graph_node
*tail
= vector_slot (tok
->forkjoin
->from
, i
);
423 struct cmd_token
*tailtok
= tail
->data
;
424 if (tail
== gn
|| tailtok
->varname
)
426 cmd_token_varname_set (tailtok
, jointok
->varname
);
431 for (i
= 0; i
< vector_active (gn
->to
); i
++)
433 struct graph_node
*next
= vector_slot (gn
->to
, i
);
434 if (next
== stop
|| next
== join
)
436 cmd_node_names (next
, join
, prevname
);
439 if (tok
->type
== FORK_TKN
&& tok
->forkjoin
!= join
)
440 cmd_node_names (tok
->forkjoin
, join
, NULL
);
444 cmd_graph_names (struct graph
*graph
)
446 struct graph_node
*start
;
448 assert (vector_active (graph
->nodes
) >= 1);
449 start
= vector_slot (graph
->nodes
, 0);
451 /* apply varname on initial "[no]" */
454 if (vector_active (start
->to
) != 1)
457 struct graph_node
*first
= vector_slot (start
->to
, 0);
458 struct cmd_token
*tok
= first
->data
;
459 /* looking for an option with 2 choices, nothing or "no" */
460 if (tok
->type
!= FORK_TKN
|| vector_active (first
->to
) != 2)
463 struct graph_node
*next0
= vector_slot (first
->to
, 0);
464 struct graph_node
*next1
= vector_slot (first
->to
, 1);
465 /* one needs to be empty */
466 if (next0
!= tok
->forkjoin
&& next1
!= tok
->forkjoin
)
469 struct cmd_token
*tok0
= next0
->data
;
470 struct cmd_token
*tok1
= next1
->data
;
471 /* the other one needs to be "no" (only one will match here) */
472 if ((tok0
->type
== WORD_TKN
&& !strcmp(tok0
->text
, "no")))
473 cmd_token_varname_set (tok0
, "no");
474 if ((tok1
->type
== WORD_TKN
&& !strcmp(tok1
->text
, "no")))
475 cmd_token_varname_set (tok1
, "no");
479 cmd_node_names (start
, NULL
, NULL
);