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 83814 : struct cmd_token *cmd_token_new(enum cmd_token_type type, uint8_t attr,
36 : const char *text, const char *desc)
37 : {
38 83814 : struct cmd_token *token =
39 83814 : XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct cmd_token));
40 83814 : token->type = type;
41 83814 : token->attr = attr;
42 83814 : token->text = text ? XSTRDUP(MTYPE_CMD_TEXT, text) : NULL;
43 83814 : token->desc = desc ? XSTRDUP(MTYPE_CMD_DESC, desc) : NULL;
44 83814 : token->refcnt = 1;
45 83814 : token->arg = NULL;
46 83814 : token->allowrepeat = false;
47 83814 : token->varname = NULL;
48 :
49 83814 : return token;
50 : }
51 :
52 83814 : void cmd_token_del(struct cmd_token *token)
53 : {
54 83814 : if (!token)
55 : return;
56 :
57 83814 : XFREE(MTYPE_CMD_TEXT, token->text);
58 83814 : XFREE(MTYPE_CMD_DESC, token->desc);
59 83814 : XFREE(MTYPE_CMD_ARG, token->arg);
60 83814 : XFREE(MTYPE_CMD_VAR, token->varname);
61 :
62 83814 : XFREE(MTYPE_CMD_TOKENS, token);
63 : }
64 :
65 1886 : struct cmd_token *cmd_token_dup(struct cmd_token *token)
66 : {
67 1886 : struct cmd_token *copy =
68 1886 : cmd_token_new(token->type, token->attr, NULL, NULL);
69 1886 : copy->max = token->max;
70 1886 : copy->min = token->min;
71 1886 : copy->text = token->text ? XSTRDUP(MTYPE_CMD_TEXT, token->text) : NULL;
72 1886 : copy->desc = token->desc ? XSTRDUP(MTYPE_CMD_DESC, token->desc) : NULL;
73 1886 : copy->arg = token->arg ? XSTRDUP(MTYPE_CMD_ARG, token->arg) : NULL;
74 3772 : copy->varname =
75 1886 : token->varname ? XSTRDUP(MTYPE_CMD_VAR, token->varname) : NULL;
76 :
77 1886 : return copy;
78 : }
79 :
80 15044 : static void cmd_token_varname_do(struct cmd_token *token, const char *varname,
81 : uint8_t varname_src)
82 : {
83 15044 : if (token->varname_src >= varname_src)
84 : return;
85 :
86 12728 : XFREE(MTYPE_CMD_VAR, token->varname);
87 :
88 12728 : size_t len = strlen(varname), i;
89 12728 : token->varname = XMALLOC(MTYPE_CMD_VAR, len + 1);
90 12728 : token->varname_src = varname_src;
91 :
92 90348 : for (i = 0; i < len; i++)
93 77620 : switch (varname[i]) {
94 1428 : case '-':
95 : case '+':
96 : case '*':
97 : case ':':
98 1428 : token->varname[i] = '_';
99 1428 : break;
100 : default:
101 76192 : token->varname[i] = tolower((unsigned char)varname[i]);
102 : }
103 12728 : token->varname[len] = '\0';
104 : }
105 :
106 45504 : void cmd_token_varname_set(struct cmd_token *token, const char *varname)
107 : {
108 45504 : if (varname) {
109 3832 : cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);
110 3832 : return;
111 : }
112 41672 : if (token->type == VARIABLE_TKN) {
113 2672 : if (strcmp(token->text, "WORD") && strcmp(token->text, "NAME"))
114 1760 : cmd_token_varname_do(token, token->text, VARNAME_TEXT);
115 : }
116 : }
117 :
118 5532 : static void cmd_token_varname_fork(struct graph_node *node,
119 : struct cmd_token *prevtoken)
120 : {
121 20792 : for (size_t i = 0; i < vector_active(node->to); i++) {
122 15260 : struct graph_node *next = vector_slot(node->to, i);
123 15260 : struct cmd_token *nexttoken = next->data;
124 :
125 15260 : if (nexttoken->type == FORK_TKN) {
126 780 : cmd_token_varname_fork(next, prevtoken);
127 780 : continue;
128 : }
129 14480 : if (nexttoken->varname)
130 3464 : continue;
131 11016 : if (!IS_VARYING_TOKEN(nexttoken->type))
132 9316 : continue;
133 :
134 1700 : cmd_token_varname_do(nexttoken, prevtoken->text, VARNAME_TEXT);
135 : }
136 5532 : }
137 :
138 9252 : void cmd_token_varname_join(struct graph_node *join, const char *varname)
139 : {
140 9252 : if (!varname)
141 : return;
142 :
143 3548 : for (size_t i = 0; i < vector_active(join->from); i++) {
144 3012 : struct graph_node *prev = vector_slot(join->from, i);
145 3012 : struct cmd_token *token = prev->data;
146 :
147 3012 : if (token->type == JOIN_TKN)
148 0 : cmd_token_varname_join(prev, varname);
149 3012 : else if (token->type < SPECIAL_TKN)
150 2976 : cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);
151 : }
152 : }
153 :
154 36964 : void cmd_token_varname_seqappend(struct graph_node *node)
155 : {
156 36964 : struct graph_node *prevnode = node;
157 36964 : struct cmd_token *token = node->data;
158 36964 : struct cmd_token *prevtoken;
159 :
160 36964 : if (token->type == WORD_TKN)
161 : return;
162 :
163 13140 : do {
164 13140 : if (vector_active(prevnode->from) != 1)
165 : return;
166 :
167 13120 : prevnode = vector_slot(prevnode->from, 0);
168 13120 : prevtoken = prevnode->data;
169 13120 : } while (prevtoken->type == FORK_TKN);
170 :
171 13120 : if (prevtoken->type != WORD_TKN)
172 : return;
173 :
174 8896 : if (token->type == FORK_TKN)
175 4752 : cmd_token_varname_fork(node, prevtoken);
176 : else
177 4144 : cmd_token_varname_do(token, prevtoken->text, VARNAME_TEXT);
178 : }
179 :
180 59504 : static bool cmd_nodes_link(struct graph_node *from, struct graph_node *to)
181 : {
182 207648 : for (size_t i = 0; i < vector_active(from->to); i++)
183 150700 : 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 542216 : static inline struct graph_node *cmd_loopstop(struct graph_node *gn)
195 : {
196 542216 : struct cmd_token *tok = gn->data;
197 542216 : if (tok->type == JOIN_TKN)
198 186192 : return tok->forkjoin;
199 : else
200 : return gn;
201 : }
202 :
203 7076 : static bool cmd_subgraph_equal(struct graph_node *ga, struct graph_node *gb,
204 : struct graph_node *a_join)
205 : {
206 7076 : size_t i, j;
207 7076 : struct graph_node *a_fork, *b_fork;
208 7076 : a_fork = cmd_loopstop(ga);
209 7076 : b_fork = cmd_loopstop(gb);
210 :
211 7076 : if (vector_active(ga->to) != vector_active(gb->to))
212 : return false;
213 16168 : for (i = 0; i < vector_active(ga->to); i++) {
214 9568 : struct graph_node *cga = vector_slot(ga->to, i);
215 :
216 10216 : for (j = 0; j < vector_active(gb->to); j++) {
217 9796 : struct graph_node *cgb = vector_slot(gb->to, i);
218 :
219 9796 : if (cga == a_fork && cgb != b_fork)
220 0 : continue;
221 9796 : if (cga == a_fork && cgb == b_fork)
222 : break;
223 :
224 9796 : if (cmd_nodes_equal(cga, cgb)) {
225 9356 : if (cga == a_join)
226 : break;
227 5044 : if (cmd_subgraph_equal(cga, cgb, a_join))
228 : break;
229 : }
230 : }
231 9568 : 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 175376 : static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb)
241 : {
242 175376 : struct cmd_token *a = ga->data, *b = gb->data;
243 :
244 175376 : if (a->type != b->type || a->allowrepeat != b->allowrepeat)
245 : return false;
246 160068 : if (a->type < SPECIAL_TKN && strcmp(a->text, b->text))
247 : return false;
248 : /* one a ..., the other not. */
249 25308 : if (cmd_nodes_link(ga, ga) != cmd_nodes_link(gb, gb))
250 : return false;
251 25308 : if (!a->varname != !b->varname)
252 : return false;
253 25260 : if (a->varname && strcmp(a->varname, b->varname))
254 : return false;
255 :
256 25164 : switch (a->type) {
257 632 : case RANGE_TKN:
258 632 : return a->min == b->min && a->max == b->max;
259 :
260 2228 : case FORK_TKN:
261 : /* one is keywords, the other just option or selector ... */
262 4456 : if (cmd_nodes_link(a->forkjoin, ga)
263 2228 : != cmd_nodes_link(b->forkjoin, gb))
264 : return false;
265 4432 : if (cmd_nodes_link(ga, a->forkjoin)
266 2216 : != cmd_nodes_link(gb, b->forkjoin))
267 : return false;
268 2032 : 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 479720 : static void cmd_reparent_tree(struct graph *fromgraph, struct graph *tograph,
310 : struct graph_node *node)
311 : {
312 479720 : struct graph_node *stop = cmd_loopstop(node);
313 479720 : size_t i;
314 :
315 24561084 : for (i = 0; i < vector_active(fromgraph->nodes); i++)
316 24142652 : 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 61288 : vector_unset(fromgraph->nodes, i);
321 61288 : vector_set(tograph->nodes, node);
322 61288 : break;
323 : }
324 :
325 953392 : for (i = 0; i < vector_active(node->to); i++) {
326 473672 : struct graph_node *next = vector_slot(node->to, i);
327 473672 : if (next != stop)
328 470904 : cmd_reparent_tree(fromgraph, tograph, next);
329 : }
330 479720 : }
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 24160 : 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 24160 : struct cmd_token *tok;
366 24160 : struct graph_node *old_skip, *new_skip;
367 24160 : old_skip = cmd_loopstop(old);
368 24160 : new_skip = cmd_loopstop(new);
369 :
370 24160 : assert(direction == 1 || direction == -1);
371 :
372 24160 : tok = old->data;
373 24160 : tok->refcnt += direction;
374 :
375 24160 : size_t j, i;
376 48320 : for (j = 0; j < vector_active(new->to); j++) {
377 24160 : struct graph_node *cnew = vector_slot(new->to, j);
378 24160 : if (cnew == new_skip)
379 0 : continue;
380 :
381 174396 : for (i = 0; i < vector_active(old->to); i++) {
382 165580 : struct graph_node *cold = vector_slot(old->to, i);
383 165580 : if (cold == old_skip)
384 0 : continue;
385 :
386 165580 : if (cmd_nodes_equal(cold, cnew)) {
387 15344 : struct cmd_token *told = cold->data,
388 15344 : *tnew = cnew->data;
389 :
390 15344 : 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 15344 : if (told->type == FORK_TKN) {
408 1364 : 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 1364 : told = (cold = told->forkjoin)->data;
415 1364 : tnew = (cnew = tnew->forkjoin)->data;
416 : }
417 15344 : if (tnew->attr < told->attr)
418 392 : told->attr = tnew->attr;
419 :
420 15344 : cmd_merge_nodes(oldgraph, newgraph, cold, cnew,
421 : direction);
422 15344 : break;
423 : }
424 : }
425 : /* nothing found => add new to old */
426 24160 : if (i == vector_active(old->to) && direction > 0) {
427 8816 : graph_remove_edge(new, cnew);
428 :
429 8816 : cmd_reparent_tree(newgraph, oldgraph, cnew);
430 :
431 8816 : graph_add_edge(old, cnew);
432 : }
433 : }
434 :
435 24160 : if (!tok->refcnt)
436 0 : cmd_free_node(oldgraph, old);
437 24160 : }
438 :
439 8816 : void cmd_graph_merge(struct graph *old, struct graph *new, int direction)
440 : {
441 8816 : assert(vector_active(old->nodes) >= 1);
442 8816 : assert(vector_active(new->nodes) >= 1);
443 :
444 8816 : cmd_merge_nodes(old, new, vector_slot(old->nodes, 0),
445 8816 : vector_slot(new->nodes, 0), direction);
446 8816 : }
447 :
448 8816 : void cmd_graph_names(struct graph *graph)
449 : {
450 8816 : struct graph_node *start;
451 :
452 8816 : assert(vector_active(graph->nodes) >= 1);
453 8816 : start = vector_slot(graph->nodes, 0);
454 :
455 : /* apply varname on initial "[no]" */
456 17632 : do {
457 8816 : if (vector_active(start->to) != 1)
458 : break;
459 :
460 8816 : struct graph_node *first = vector_slot(start->to, 0);
461 8816 : struct cmd_token *tok = first->data;
462 : /* looking for an option with 2 choices, nothing or "no" */
463 8816 : if (tok->type != FORK_TKN || vector_active(first->to) != 2)
464 : break;
465 :
466 632 : struct graph_node *next0 = vector_slot(first->to, 0);
467 632 : struct graph_node *next1 = vector_slot(first->to, 1);
468 : /* one needs to be empty */
469 632 : if (next0 != tok->forkjoin && next1 != tok->forkjoin)
470 : break;
471 :
472 632 : struct cmd_token *tok0 = next0->data;
473 632 : struct cmd_token *tok1 = next1->data;
474 : /* the other one needs to be "no" (only one will match here) */
475 632 : if ((tok0->type == WORD_TKN && !strcmp(tok0->text, "no")))
476 632 : cmd_token_varname_do(tok0, "no", VARNAME_AUTO);
477 632 : if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))
478 0 : cmd_token_varname_do(tok1, "no", VARNAME_AUTO);
479 : } while (0);
480 8816 : }
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 */
|
