Line data Source code
1 : /*
2 : * CLI graph handling
3 : *
4 : * --
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")
9 : *
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)
13 : * any later version.
14 : *
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
18 : * more details.
19 : *
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
23 : */
24 :
25 : #include <zebra.h>
26 :
27 : #include "command_graph.h"
28 :
29 36 : DEFINE_MTYPE_STATIC(LIB, CMD_TOKENS, "Command Tokens");
30 36 : DEFINE_MTYPE_STATIC(LIB, CMD_DESC, "Command Token Text");
31 36 : DEFINE_MTYPE_STATIC(LIB, CMD_TEXT, "Command Token Help");
32 36 : DEFINE_MTYPE(LIB, CMD_ARG, "Command Argument");
33 36 : DEFINE_MTYPE_STATIC(LIB, CMD_VAR, "Command Argument Name");
34 :
35 51347 : struct cmd_token *cmd_token_new(enum cmd_token_type type, uint8_t attr,
36 : const char *text, const char *desc)
37 : {
38 51347 : struct cmd_token *token =
39 51347 : XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct cmd_token));
40 51347 : token->type = type;
41 51347 : token->attr = attr;
42 51347 : token->text = text ? XSTRDUP(MTYPE_CMD_TEXT, text) : NULL;
43 51347 : token->desc = desc ? XSTRDUP(MTYPE_CMD_DESC, desc) : NULL;
44 51347 : token->refcnt = 1;
45 51347 : token->arg = NULL;
46 51347 : token->allowrepeat = false;
47 51347 : token->varname = NULL;
48 :
49 51347 : return token;
50 : }
51 :
52 51347 : void cmd_token_del(struct cmd_token *token)
53 : {
54 51347 : if (!token)
55 : return;
56 :
57 51347 : XFREE(MTYPE_CMD_TEXT, token->text);
58 51347 : XFREE(MTYPE_CMD_DESC, token->desc);
59 51347 : XFREE(MTYPE_CMD_ARG, token->arg);
60 51347 : XFREE(MTYPE_CMD_VAR, token->varname);
61 :
62 51347 : XFREE(MTYPE_CMD_TOKENS, token);
63 : }
64 :
65 727 : struct cmd_token *cmd_token_dup(struct cmd_token *token)
66 : {
67 727 : struct cmd_token *copy =
68 727 : cmd_token_new(token->type, token->attr, NULL, NULL);
69 727 : copy->max = token->max;
70 727 : copy->min = token->min;
71 727 : copy->text = token->text ? XSTRDUP(MTYPE_CMD_TEXT, token->text) : NULL;
72 727 : copy->desc = token->desc ? XSTRDUP(MTYPE_CMD_DESC, token->desc) : NULL;
73 727 : copy->arg = token->arg ? XSTRDUP(MTYPE_CMD_ARG, token->arg) : NULL;
74 1454 : copy->varname =
75 727 : token->varname ? XSTRDUP(MTYPE_CMD_VAR, token->varname) : NULL;
76 :
77 727 : return copy;
78 : }
79 :
80 11272 : static void cmd_token_varname_do(struct cmd_token *token, const char *varname,
81 : uint8_t varname_src)
82 : {
83 11272 : if (token->varname_src >= varname_src)
84 : return;
85 :
86 9648 : XFREE(MTYPE_CMD_VAR, token->varname);
87 :
88 9648 : size_t len = strlen(varname), i;
89 9648 : token->varname = XMALLOC(MTYPE_CMD_VAR, len + 1);
90 9648 : token->varname_src = varname_src;
91 :
92 67792 : for (i = 0; i < len; i++)
93 58144 : switch (varname[i]) {
94 724 : case '-':
95 : case '+':
96 : case '*':
97 : case ':':
98 724 : token->varname[i] = '_';
99 724 : break;
100 : default:
101 57420 : token->varname[i] = tolower((unsigned char)varname[i]);
102 : }
103 9648 : token->varname[len] = '\0';
104 : }
105 :
106 27944 : void cmd_token_varname_set(struct cmd_token *token, const char *varname)
107 : {
108 27944 : if (varname) {
109 3200 : cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);
110 3200 : return;
111 : }
112 24744 : if (token->type == VARIABLE_TKN) {
113 1932 : if (strcmp(token->text, "WORD") && strcmp(token->text, "NAME"))
114 1376 : cmd_token_varname_do(token, token->text, VARNAME_TEXT);
115 : }
116 : }
117 :
118 2764 : static void cmd_token_varname_fork(struct graph_node *node,
119 : struct cmd_token *prevtoken)
120 : {
121 11020 : for (size_t i = 0; i < vector_active(node->to); i++) {
122 8256 : struct graph_node *next = vector_slot(node->to, i);
123 8256 : struct cmd_token *nexttoken = next->data;
124 :
125 8256 : if (nexttoken->type == FORK_TKN) {
126 448 : cmd_token_varname_fork(next, prevtoken);
127 448 : continue;
128 : }
129 7808 : if (nexttoken->varname)
130 3244 : continue;
131 4564 : if (!IS_VARYING_TOKEN(nexttoken->type))
132 4108 : continue;
133 :
134 456 : cmd_token_varname_do(nexttoken, prevtoken->text, VARNAME_TEXT);
135 : }
136 2764 : }
137 :
138 5212 : void cmd_token_varname_join(struct graph_node *join, const char *varname)
139 : {
140 5212 : if (!varname)
141 : return;
142 :
143 3424 : for (size_t i = 0; i < vector_active(join->from); i++) {
144 2936 : struct graph_node *prev = vector_slot(join->from, i);
145 2936 : struct cmd_token *token = prev->data;
146 :
147 2936 : if (token->type == JOIN_TKN)
148 0 : cmd_token_varname_join(prev, varname);
149 2936 : else if (token->type < SPECIAL_TKN)
150 2912 : cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);
151 : }
152 : }
153 :
154 22420 : void cmd_token_varname_seqappend(struct graph_node *node)
155 : {
156 22420 : struct graph_node *prevnode = node;
157 22420 : struct cmd_token *token = node->data;
158 22420 : struct cmd_token *prevtoken;
159 :
160 22420 : if (token->type == WORD_TKN)
161 : return;
162 :
163 8068 : do {
164 8068 : if (vector_active(prevnode->from) != 1)
165 : return;
166 :
167 8068 : prevnode = vector_slot(prevnode->from, 0);
168 8068 : prevtoken = prevnode->data;
169 8068 : } while (prevtoken->type == FORK_TKN);
170 :
171 8068 : if (prevtoken->type != WORD_TKN)
172 : return;
173 :
174 5064 : if (token->type == FORK_TKN)
175 2316 : cmd_token_varname_fork(node, prevtoken);
176 : else
177 2748 : cmd_token_varname_do(token, prevtoken->text, VARNAME_TEXT);
178 : }
179 :
180 25136 : static bool cmd_nodes_link(struct graph_node *from, struct graph_node *to)
181 : {
182 91248 : for (size_t i = 0; i < vector_active(from->to); i++)
183 67432 : if (vector_slot(from->to, i) == to)
184 : return true;
185 : return false;
186 : }
187 :
188 : static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb);
189 :
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 "...")
193 : */
194 449952 : static inline struct graph_node *cmd_loopstop(struct graph_node *gn)
195 : {
196 449952 : struct cmd_token *tok = gn->data;
197 449952 : if (tok->type == JOIN_TKN)
198 165064 : return tok->forkjoin;
199 : else
200 : return gn;
201 : }
202 :
203 1836 : static bool cmd_subgraph_equal(struct graph_node *ga, struct graph_node *gb,
204 : struct graph_node *a_join)
205 : {
206 1836 : size_t i, j;
207 1836 : struct graph_node *a_fork, *b_fork;
208 1836 : a_fork = cmd_loopstop(ga);
209 1836 : b_fork = cmd_loopstop(gb);
210 :
211 1836 : if (vector_active(ga->to) != vector_active(gb->to))
212 : return false;
213 4008 : for (i = 0; i < vector_active(ga->to); i++) {
214 2504 : struct graph_node *cga = vector_slot(ga->to, i);
215 :
216 3000 : for (j = 0; j < vector_active(gb->to); j++) {
217 2668 : struct graph_node *cgb = vector_slot(gb->to, i);
218 :
219 2668 : if (cga == a_fork && cgb != b_fork)
220 0 : continue;
221 2668 : if (cga == a_fork && cgb == b_fork)
222 : break;
223 :
224 2668 : if (cmd_nodes_equal(cga, cgb)) {
225 2356 : if (cga == a_join)
226 : break;
227 1020 : if (cmd_subgraph_equal(cga, cgb, a_join))
228 : break;
229 : }
230 : }
231 2504 : if (j == vector_active(gb->to))
232 : return false;
233 : }
234 : return true;
235 : }
236 :
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
239 : * merge subgraphs */
240 101552 : static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb)
241 : {
242 101552 : struct cmd_token *a = ga->data, *b = gb->data;
243 :
244 101552 : if (a->type != b->type || a->allowrepeat != b->allowrepeat)
245 : return false;
246 90068 : if (a->type < SPECIAL_TKN && strcmp(a->text, b->text))
247 : return false;
248 : /* one a ..., the other not. */
249 10840 : if (cmd_nodes_link(ga, ga) != cmd_nodes_link(gb, gb))
250 : return false;
251 10840 : if (!a->varname != !b->varname)
252 : return false;
253 10792 : if (a->varname && strcmp(a->varname, b->varname))
254 : return false;
255 :
256 10792 : switch (a->type) {
257 220 : case RANGE_TKN:
258 220 : return a->min == b->min && a->max == b->max;
259 :
260 864 : case FORK_TKN:
261 : /* one is keywords, the other just option or selector ... */
262 1728 : if (cmd_nodes_link(a->forkjoin, ga)
263 864 : != cmd_nodes_link(b->forkjoin, gb))
264 : return false;
265 1728 : if (cmd_nodes_link(ga, a->forkjoin)
266 864 : != cmd_nodes_link(gb, b->forkjoin))
267 : return false;
268 816 : return cmd_subgraph_equal(ga, gb, a->forkjoin);
269 :
270 : case VARIABLE_TKN:
271 : case IPV4_TKN:
272 : case IPV4_PREFIX_TKN:
273 : case IPV6_PREFIX_TKN:
274 : case IPV6_TKN:
275 : case MAC_TKN:
276 : case MAC_PREFIX_TKN:
277 : case JOIN_TKN:
278 : case START_TKN:
279 : case END_TKN:
280 : case NEG_ONLY_TKN:
281 : case WORD_TKN:
282 : return true;
283 : }
284 :
285 0 : assert(!"Reached end of function we should never hit");
286 : }
287 :
288 24 : static void cmd_fork_bump_attr(struct graph_node *gn, struct graph_node *join,
289 : uint8_t attr)
290 : {
291 24 : size_t i;
292 24 : struct cmd_token *tok = gn->data;
293 24 : struct graph_node *stop = cmd_loopstop(gn);
294 :
295 24 : tok->attr = attr;
296 56 : for (i = 0; i < vector_active(gn->to); i++) {
297 32 : struct graph_node *next = vector_slot(gn->to, i);
298 32 : if (next == stop || next == join)
299 16 : continue;
300 16 : cmd_fork_bump_attr(next, join, attr);
301 : }
302 24 : }
303 :
304 : /* move an entire subtree from the temporary graph resulting from
305 : * parse() into the permanent graph for the command node.
306 : *
307 : * this touches rather deeply into the graph code unfortunately.
308 : */
309 417776 : static void cmd_reparent_tree(struct graph *fromgraph, struct graph *tograph,
310 : struct graph_node *node)
311 : {
312 417776 : struct graph_node *stop = cmd_loopstop(node);
313 417776 : size_t i;
314 :
315 23758280 : for (i = 0; i < vector_active(fromgraph->nodes); i++)
316 23381176 : if (vector_slot(fromgraph->nodes, i) == node) {
317 : /* agressive iteration punching through subgraphs - may
318 : * hit some
319 : * nodes twice. reparent only if found on old graph */
320 40672 : vector_unset(fromgraph->nodes, i);
321 40672 : vector_set(tograph->nodes, node);
322 40672 : break;
323 : }
324 :
325 832820 : for (i = 0; i < vector_active(node->to); i++) {
326 415044 : struct graph_node *next = vector_slot(node->to, i);
327 415044 : if (next != stop)
328 411776 : cmd_reparent_tree(fromgraph, tograph, next);
329 : }
330 417776 : }
331 :
332 0 : static void cmd_free_recur(struct graph *graph, struct graph_node *node,
333 : struct graph_node *stop)
334 : {
335 0 : struct graph_node *next, *nstop;
336 :
337 0 : for (size_t i = vector_active(node->to); i; i--) {
338 0 : next = vector_slot(node->to, i - 1);
339 0 : if (next == stop)
340 0 : continue;
341 0 : nstop = cmd_loopstop(next);
342 0 : if (nstop != next)
343 0 : cmd_free_recur(graph, next, nstop);
344 0 : cmd_free_recur(graph, nstop, stop);
345 : }
346 0 : graph_delete_node(graph, node);
347 0 : }
348 :
349 0 : static void cmd_free_node(struct graph *graph, struct graph_node *node)
350 : {
351 0 : struct cmd_token *tok = node->data;
352 0 : if (tok->type == JOIN_TKN)
353 0 : cmd_free_recur(graph, tok->forkjoin, node);
354 0 : graph_delete_node(graph, node);
355 0 : }
356 :
357 : /* recursive graph merge. call with
358 : * old ~= new
359 : * (which holds true for old == START_TKN, new == START_TKN)
360 : */
361 14240 : static void cmd_merge_nodes(struct graph *oldgraph, struct graph *newgraph,
362 : struct graph_node *old, struct graph_node *new,
363 : int direction)
364 : {
365 14240 : struct cmd_token *tok;
366 14240 : struct graph_node *old_skip, *new_skip;
367 14240 : old_skip = cmd_loopstop(old);
368 14240 : new_skip = cmd_loopstop(new);
369 :
370 14240 : assert(direction == 1 || direction == -1);
371 :
372 14240 : tok = old->data;
373 14240 : tok->refcnt += direction;
374 :
375 14240 : size_t j, i;
376 28480 : for (j = 0; j < vector_active(new->to); j++) {
377 14240 : struct graph_node *cnew = vector_slot(new->to, j);
378 14240 : if (cnew == new_skip)
379 0 : continue;
380 :
381 104884 : for (i = 0; i < vector_active(old->to); i++) {
382 98884 : struct graph_node *cold = vector_slot(old->to, i);
383 98884 : if (cold == old_skip)
384 0 : continue;
385 :
386 98884 : if (cmd_nodes_equal(cold, cnew)) {
387 8240 : struct cmd_token *told = cold->data,
388 8240 : *tnew = cnew->data;
389 :
390 8240 : if (told->type == END_TKN) {
391 0 : if (direction < 0) {
392 0 : graph_delete_node(
393 : oldgraph,
394 0 : vector_slot(cold->to,
395 : 0));
396 0 : graph_delete_node(oldgraph,
397 : cold);
398 : } else
399 : /* force no-match handling to
400 : * install END_TKN */
401 0 : i = vector_active(old->to);
402 : break;
403 : }
404 :
405 : /* the entire fork compared as equal, we
406 : * continue after it. */
407 8240 : if (told->type == FORK_TKN) {
408 652 : if (tnew->attr < told->attr
409 8 : && direction > 0)
410 8 : cmd_fork_bump_attr(
411 : cold, told->forkjoin,
412 : tnew->attr);
413 : /* XXX: no reverse bump on uninstall */
414 652 : told = (cold = told->forkjoin)->data;
415 652 : tnew = (cnew = tnew->forkjoin)->data;
416 : }
417 8240 : if (tnew->attr < told->attr)
418 308 : told->attr = tnew->attr;
419 :
420 8240 : cmd_merge_nodes(oldgraph, newgraph, cold, cnew,
421 : direction);
422 8240 : break;
423 : }
424 : }
425 : /* nothing found => add new to old */
426 14240 : if (i == vector_active(old->to) && direction > 0) {
427 6000 : graph_remove_edge(new, cnew);
428 :
429 6000 : cmd_reparent_tree(newgraph, oldgraph, cnew);
430 :
431 6000 : graph_add_edge(old, cnew);
432 : }
433 : }
434 :
435 14240 : if (!tok->refcnt)
436 0 : cmd_free_node(oldgraph, old);
437 14240 : }
438 :
439 6000 : void cmd_graph_merge(struct graph *old, struct graph *new, int direction)
440 : {
441 6000 : assert(vector_active(old->nodes) >= 1);
442 6000 : assert(vector_active(new->nodes) >= 1);
443 :
444 6000 : cmd_merge_nodes(old, new, vector_slot(old->nodes, 0),
445 6000 : vector_slot(new->nodes, 0), direction);
446 6000 : }
447 :
448 6000 : void cmd_graph_names(struct graph *graph)
449 : {
450 6000 : struct graph_node *start;
451 :
452 6000 : assert(vector_active(graph->nodes) >= 1);
453 6000 : start = vector_slot(graph->nodes, 0);
454 :
455 : /* apply varname on initial "[no]" */
456 12000 : do {
457 6000 : if (vector_active(start->to) != 1)
458 : break;
459 :
460 6000 : struct graph_node *first = vector_slot(start->to, 0);
461 6000 : struct cmd_token *tok = first->data;
462 : /* looking for an option with 2 choices, nothing or "no" */
463 6000 : if (tok->type != FORK_TKN || vector_active(first->to) != 2)
464 : break;
465 :
466 580 : struct graph_node *next0 = vector_slot(first->to, 0);
467 580 : struct graph_node *next1 = vector_slot(first->to, 1);
468 : /* one needs to be empty */
469 580 : if (next0 != tok->forkjoin && next1 != tok->forkjoin)
470 : break;
471 :
472 580 : struct cmd_token *tok0 = next0->data;
473 580 : struct cmd_token *tok1 = next1->data;
474 : /* the other one needs to be "no" (only one will match here) */
475 580 : if ((tok0->type == WORD_TKN && !strcmp(tok0->text, "no")))
476 580 : cmd_token_varname_do(tok0, "no", VARNAME_AUTO);
477 580 : if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))
478 0 : cmd_token_varname_do(tok1, "no", VARNAME_AUTO);
479 : } while (0);
480 6000 : }
481 :
482 : #ifndef BUILDING_CLIPPY
483 :
484 : #include "command.h"
485 : #include "log.h"
486 :
487 0 : void cmd_graph_node_print_cb(struct graph_node *gn, struct buffer *buf)
488 : {
489 0 : static bool wasend;
490 :
491 0 : char nbuf[512];
492 0 : struct cmd_token *tok = gn->data;
493 0 : const char *color = NULL;
494 :
495 0 : if (wasend) {
496 0 : wasend = false;
497 0 : return;
498 : }
499 :
500 0 : if (tok->type == END_TKN) {
501 0 : wasend = true;
502 0 : return;
503 : }
504 :
505 0 : snprintf(nbuf, sizeof(nbuf), " n%p [ shape=box, label=<", gn);
506 0 : buffer_putstr(buf, nbuf);
507 0 : snprintf(nbuf, sizeof(nbuf), "<b>%s</b>",
508 0 : lookup_msg(tokennames, tok->type, NULL));
509 0 : buffer_putstr(buf, nbuf);
510 0 : if (tok->attr & CMD_ATTR_DEPRECATED)
511 0 : buffer_putstr(buf, " (d)");
512 : /* DEPRECATED implies HIDDEN, don't print both */
513 0 : else if (tok->attr & CMD_ATTR_HIDDEN)
514 0 : buffer_putstr(buf, " (h)");
515 0 : if (tok->text) {
516 0 : if (tok->type == WORD_TKN)
517 0 : snprintf(
518 : nbuf, sizeof(nbuf),
519 : "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",
520 : tok->text);
521 : else
522 0 : snprintf(nbuf, sizeof(nbuf), "<br/>%s", tok->text);
523 0 : buffer_putstr(buf, nbuf);
524 : }
525 :
526 0 : switch (tok->type) {
527 0 : case START_TKN:
528 0 : color = "#ccffcc";
529 0 : break;
530 0 : case FORK_TKN:
531 0 : color = "#aaddff";
532 0 : break;
533 0 : case JOIN_TKN:
534 0 : color = "#ddaaff";
535 0 : break;
536 0 : case NEG_ONLY_TKN:
537 0 : color = "#ffddaa";
538 0 : break;
539 : case WORD_TKN:
540 0 : color = "#ffffff";
541 : break;
542 : case RANGE_TKN:
543 : case IPV4_TKN:
544 : case IPV4_PREFIX_TKN:
545 : case IPV6_TKN:
546 : case IPV6_PREFIX_TKN:
547 : case MAC_TKN:
548 : case MAC_PREFIX_TKN:
549 : case END_TKN:
550 : case VARIABLE_TKN:
551 0 : color = "#ffffff";
552 : break;
553 : }
554 :
555 : /*
556 : * Some compilers have the mistaken belief that we can
557 : * get here without initializing color.
558 : */
559 0 : snprintf(nbuf, sizeof(nbuf),
560 : ">, style = filled, fillcolor = \"%s\" ];\n", color);
561 0 : buffer_putstr(buf, nbuf);
562 :
563 0 : for (unsigned int i = 0; i < vector_active(gn->to); i++) {
564 0 : struct graph_node *adj = vector_slot(gn->to, i);
565 :
566 0 : if (((struct cmd_token *)adj->data)->type == END_TKN) {
567 0 : snprintf(nbuf, sizeof(nbuf), " n%p -> end%p;\n", gn,
568 : adj);
569 0 : buffer_putstr(buf, nbuf);
570 0 : snprintf(
571 : nbuf, sizeof(nbuf),
572 : " end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",
573 : adj);
574 : } else
575 0 : snprintf(nbuf, sizeof(nbuf), " n%p -> n%p;\n", gn,
576 : adj);
577 :
578 0 : buffer_putstr(buf, nbuf);
579 : }
580 : }
581 :
582 0 : char *cmd_graph_dump_dot(struct graph *cmdgraph)
583 : {
584 0 : struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
585 :
586 0 : return graph_dump_dot(cmdgraph, start, cmd_graph_node_print_cb);
587 : }
588 :
589 : #endif /* BUILDING_CLIPPY */
|
