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 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")
34
cmd_token_new(enum cmd_token_type type,uint8_t attr,const char * text,const char * desc)35 struct cmd_token *cmd_token_new(enum cmd_token_type type, uint8_t attr,
36 const char *text, const char *desc)
37 {
38 struct cmd_token *token =
39 XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct cmd_token));
40 token->type = type;
41 token->attr = attr;
42 token->text = text ? XSTRDUP(MTYPE_CMD_TEXT, text) : NULL;
43 token->desc = desc ? XSTRDUP(MTYPE_CMD_DESC, desc) : NULL;
44 token->refcnt = 1;
45 token->arg = NULL;
46 token->allowrepeat = false;
47 token->varname = NULL;
48
49 return token;
50 }
51
cmd_token_del(struct cmd_token * token)52 void cmd_token_del(struct cmd_token *token)
53 {
54 if (!token)
55 return;
56
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);
61
62 XFREE(MTYPE_CMD_TOKENS, token);
63 }
64
cmd_token_dup(struct cmd_token * token)65 struct cmd_token *cmd_token_dup(struct cmd_token *token)
66 {
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;
74 copy->varname =
75 token->varname ? XSTRDUP(MTYPE_CMD_VAR, token->varname) : NULL;
76
77 return copy;
78 }
79
cmd_token_varname_set(struct cmd_token * token,const char * varname)80 void cmd_token_varname_set(struct cmd_token *token, const char *varname)
81 {
82 XFREE(MTYPE_CMD_VAR, token->varname);
83 if (!varname) {
84 token->varname = NULL;
85 return;
86 }
87
88 size_t len = strlen(varname), i;
89 token->varname = XMALLOC(MTYPE_CMD_VAR, len + 1);
90
91 for (i = 0; i < len; i++)
92 switch (varname[i]) {
93 case '-':
94 case '+':
95 case '*':
96 case ':':
97 token->varname[i] = '_';
98 break;
99 default:
100 token->varname[i] = tolower((unsigned char)varname[i]);
101 }
102 token->varname[len] = '\0';
103 }
104
cmd_nodes_link(struct graph_node * from,struct graph_node * to)105 static bool cmd_nodes_link(struct graph_node *from, struct graph_node *to)
106 {
107 for (size_t i = 0; i < vector_active(from->to); i++)
108 if (vector_slot(from->to, i) == to)
109 return true;
110 return false;
111 }
112
113 static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb);
114
115 /* returns a single node to be excluded as "next" from iteration
116 * - for JOIN_TKN, never continue back to the FORK_TKN
117 * - in all other cases, don't try the node itself (in case of "...")
118 */
cmd_loopstop(struct graph_node * gn)119 static inline struct graph_node *cmd_loopstop(struct graph_node *gn)
120 {
121 struct cmd_token *tok = gn->data;
122 if (tok->type == JOIN_TKN)
123 return tok->forkjoin;
124 else
125 return gn;
126 }
127
cmd_subgraph_equal(struct graph_node * ga,struct graph_node * gb,struct graph_node * a_join)128 static bool cmd_subgraph_equal(struct graph_node *ga, struct graph_node *gb,
129 struct graph_node *a_join)
130 {
131 size_t i, j;
132 struct graph_node *a_fork, *b_fork;
133 a_fork = cmd_loopstop(ga);
134 b_fork = cmd_loopstop(gb);
135
136 if (vector_active(ga->to) != vector_active(gb->to))
137 return false;
138 for (i = 0; i < vector_active(ga->to); i++) {
139 struct graph_node *cga = vector_slot(ga->to, i);
140
141 for (j = 0; j < vector_active(gb->to); j++) {
142 struct graph_node *cgb = vector_slot(gb->to, i);
143
144 if (cga == a_fork && cgb != b_fork)
145 continue;
146 if (cga == a_fork && cgb == b_fork)
147 break;
148
149 if (cmd_nodes_equal(cga, cgb)) {
150 if (cga == a_join)
151 break;
152 if (cmd_subgraph_equal(cga, cgb, a_join))
153 break;
154 }
155 }
156 if (j == vector_active(gb->to))
157 return false;
158 }
159 return true;
160 }
161
162 /* deep compare -- for FORK_TKN, the entire subgraph is compared.
163 * this is what's needed since we're not currently trying to partially
164 * merge subgraphs */
cmd_nodes_equal(struct graph_node * ga,struct graph_node * gb)165 static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb)
166 {
167 struct cmd_token *a = ga->data, *b = gb->data;
168
169 if (a->type != b->type || a->allowrepeat != b->allowrepeat)
170 return false;
171 if (a->type < SPECIAL_TKN && strcmp(a->text, b->text))
172 return false;
173 /* one a ..., the other not. */
174 if (cmd_nodes_link(ga, ga) != cmd_nodes_link(gb, gb))
175 return false;
176 if (!a->varname != !b->varname)
177 return false;
178 if (a->varname && strcmp(a->varname, b->varname))
179 return false;
180
181 switch (a->type) {
182 case RANGE_TKN:
183 return a->min == b->min && a->max == b->max;
184
185 case FORK_TKN:
186 /* one is keywords, the other just option or selector ... */
187 if (cmd_nodes_link(a->forkjoin, ga)
188 != cmd_nodes_link(b->forkjoin, gb))
189 return false;
190 if (cmd_nodes_link(ga, a->forkjoin)
191 != cmd_nodes_link(gb, b->forkjoin))
192 return false;
193 return cmd_subgraph_equal(ga, gb, a->forkjoin);
194
195 default:
196 return true;
197 }
198 }
199
cmd_fork_bump_attr(struct graph_node * gn,struct graph_node * join,uint8_t attr)200 static void cmd_fork_bump_attr(struct graph_node *gn, struct graph_node *join,
201 uint8_t attr)
202 {
203 size_t i;
204 struct cmd_token *tok = gn->data;
205 struct graph_node *stop = cmd_loopstop(gn);
206
207 tok->attr = attr;
208 for (i = 0; i < vector_active(gn->to); i++) {
209 struct graph_node *next = vector_slot(gn->to, i);
210 if (next == stop || next == join)
211 continue;
212 cmd_fork_bump_attr(next, join, attr);
213 }
214 }
215
216 /* move an entire subtree from the temporary graph resulting from
217 * parse() into the permanent graph for the command node.
218 *
219 * this touches rather deeply into the graph code unfortunately.
220 */
cmd_reparent_tree(struct graph * fromgraph,struct graph * tograph,struct graph_node * node)221 static void cmd_reparent_tree(struct graph *fromgraph, struct graph *tograph,
222 struct graph_node *node)
223 {
224 struct graph_node *stop = cmd_loopstop(node);
225 size_t i;
226
227 for (i = 0; i < vector_active(fromgraph->nodes); i++)
228 if (vector_slot(fromgraph->nodes, i) == node) {
229 /* agressive iteration punching through subgraphs - may
230 * hit some
231 * nodes twice. reparent only if found on old graph */
232 vector_unset(fromgraph->nodes, i);
233 vector_set(tograph->nodes, node);
234 break;
235 }
236
237 for (i = 0; i < vector_active(node->to); i++) {
238 struct graph_node *next = vector_slot(node->to, i);
239 if (next != stop)
240 cmd_reparent_tree(fromgraph, tograph, next);
241 }
242 }
243
cmd_free_recur(struct graph * graph,struct graph_node * node,struct graph_node * stop)244 static void cmd_free_recur(struct graph *graph, struct graph_node *node,
245 struct graph_node *stop)
246 {
247 struct graph_node *next, *nstop;
248
249 for (size_t i = vector_active(node->to); i; i--) {
250 next = vector_slot(node->to, i - 1);
251 if (next == stop)
252 continue;
253 nstop = cmd_loopstop(next);
254 if (nstop != next)
255 cmd_free_recur(graph, next, nstop);
256 cmd_free_recur(graph, nstop, stop);
257 }
258 graph_delete_node(graph, node);
259 }
260
cmd_free_node(struct graph * graph,struct graph_node * node)261 static void cmd_free_node(struct graph *graph, struct graph_node *node)
262 {
263 struct cmd_token *tok = node->data;
264 if (tok->type == JOIN_TKN)
265 cmd_free_recur(graph, tok->forkjoin, node);
266 graph_delete_node(graph, node);
267 }
268
269 /* recursive graph merge. call with
270 * old ~= new
271 * (which holds true for old == START_TKN, new == START_TKN)
272 */
cmd_merge_nodes(struct graph * oldgraph,struct graph * newgraph,struct graph_node * old,struct graph_node * new,int direction)273 static void cmd_merge_nodes(struct graph *oldgraph, struct graph *newgraph,
274 struct graph_node *old, struct graph_node *new,
275 int direction)
276 {
277 struct cmd_token *tok;
278 struct graph_node *old_skip, *new_skip;
279 old_skip = cmd_loopstop(old);
280 new_skip = cmd_loopstop(new);
281
282 assert(direction == 1 || direction == -1);
283
284 tok = old->data;
285 tok->refcnt += direction;
286
287 size_t j, i;
288 for (j = 0; j < vector_active(new->to); j++) {
289 struct graph_node *cnew = vector_slot(new->to, j);
290 if (cnew == new_skip)
291 continue;
292
293 for (i = 0; i < vector_active(old->to); i++) {
294 struct graph_node *cold = vector_slot(old->to, i);
295 if (cold == old_skip)
296 continue;
297
298 if (cmd_nodes_equal(cold, cnew)) {
299 struct cmd_token *told = cold->data,
300 *tnew = cnew->data;
301
302 if (told->type == END_TKN) {
303 if (direction < 0) {
304 graph_delete_node(
305 oldgraph,
306 vector_slot(cold->to,
307 0));
308 graph_delete_node(oldgraph,
309 cold);
310 } else
311 /* force no-match handling to
312 * install END_TKN */
313 i = vector_active(old->to);
314 break;
315 }
316
317 /* the entire fork compared as equal, we
318 * continue after it. */
319 if (told->type == FORK_TKN) {
320 if (tnew->attr < told->attr
321 && direction > 0)
322 cmd_fork_bump_attr(
323 cold, told->forkjoin,
324 tnew->attr);
325 /* XXX: no reverse bump on uninstall */
326 told = (cold = told->forkjoin)->data;
327 tnew = (cnew = tnew->forkjoin)->data;
328 }
329 if (tnew->attr < told->attr)
330 told->attr = tnew->attr;
331
332 cmd_merge_nodes(oldgraph, newgraph, cold, cnew,
333 direction);
334 break;
335 }
336 }
337 /* nothing found => add new to old */
338 if (i == vector_active(old->to) && direction > 0) {
339 graph_remove_edge(new, cnew);
340
341 cmd_reparent_tree(newgraph, oldgraph, cnew);
342
343 graph_add_edge(old, cnew);
344 }
345 }
346
347 if (!tok->refcnt)
348 cmd_free_node(oldgraph, old);
349 }
350
cmd_graph_merge(struct graph * old,struct graph * new,int direction)351 void cmd_graph_merge(struct graph *old, struct graph *new, int direction)
352 {
353 assert(vector_active(old->nodes) >= 1);
354 assert(vector_active(new->nodes) >= 1);
355
356 cmd_merge_nodes(old, new, vector_slot(old->nodes, 0),
357 vector_slot(new->nodes, 0), direction);
358 }
359
cmd_node_names(struct graph_node * gn,struct graph_node * join,const char * prevname)360 static void cmd_node_names(struct graph_node *gn, struct graph_node *join,
361 const char *prevname)
362 {
363 size_t i;
364 struct cmd_token *tok = gn->data, *jointok;
365 struct graph_node *stop = cmd_loopstop(gn);
366
367 switch (tok->type) {
368 case WORD_TKN:
369 prevname = tok->text;
370 break;
371
372 case VARIABLE_TKN:
373 if (!tok->varname && strcmp(tok->text, "WORD")
374 && strcmp(tok->text, "NAME"))
375 cmd_token_varname_set(tok, tok->text);
376 /* fallthrough */
377 case RANGE_TKN:
378 case IPV4_TKN:
379 case IPV4_PREFIX_TKN:
380 case IPV6_TKN:
381 case IPV6_PREFIX_TKN:
382 case MAC_TKN:
383 case MAC_PREFIX_TKN:
384 if (!tok->varname && prevname)
385 cmd_token_varname_set(tok, prevname);
386 prevname = NULL;
387 break;
388
389 case START_TKN:
390 case JOIN_TKN:
391 /* "<foo|bar> WORD" -> word is not "bar" or "foo" */
392 prevname = NULL;
393 break;
394
395 case FORK_TKN:
396 /* apply "<A.B.C.D|X:X::X:X>$name" */
397 jointok = tok->forkjoin->data;
398 if (!jointok->varname)
399 break;
400 for (i = 0; i < vector_active(tok->forkjoin->from); i++) {
401 struct graph_node *tail =
402 vector_slot(tok->forkjoin->from, i);
403 struct cmd_token *tailtok = tail->data;
404 if (tail == gn || tailtok->varname)
405 continue;
406 cmd_token_varname_set(tailtok, jointok->varname);
407 }
408 break;
409
410 case END_TKN:
411 return;
412 }
413
414 for (i = 0; i < vector_active(gn->to); i++) {
415 struct graph_node *next = vector_slot(gn->to, i);
416 if (next == stop || next == join)
417 continue;
418 cmd_node_names(next, join, prevname);
419 }
420
421 if (tok->type == FORK_TKN && tok->forkjoin != join)
422 cmd_node_names(tok->forkjoin, join, NULL);
423 }
424
cmd_graph_names(struct graph * graph)425 void cmd_graph_names(struct graph *graph)
426 {
427 struct graph_node *start;
428
429 assert(vector_active(graph->nodes) >= 1);
430 start = vector_slot(graph->nodes, 0);
431
432 /* apply varname on initial "[no]" */
433 do {
434 if (vector_active(start->to) != 1)
435 break;
436
437 struct graph_node *first = vector_slot(start->to, 0);
438 struct cmd_token *tok = first->data;
439 /* looking for an option with 2 choices, nothing or "no" */
440 if (tok->type != FORK_TKN || vector_active(first->to) != 2)
441 break;
442
443 struct graph_node *next0 = vector_slot(first->to, 0);
444 struct graph_node *next1 = vector_slot(first->to, 1);
445 /* one needs to be empty */
446 if (next0 != tok->forkjoin && next1 != tok->forkjoin)
447 break;
448
449 struct cmd_token *tok0 = next0->data;
450 struct cmd_token *tok1 = next1->data;
451 /* the other one needs to be "no" (only one will match here) */
452 if ((tok0->type == WORD_TKN && !strcmp(tok0->text, "no")))
453 cmd_token_varname_set(tok0, "no");
454 if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))
455 cmd_token_varname_set(tok1, "no");
456 } while (0);
457
458 cmd_node_names(start, NULL, NULL);
459 }
460
461 #ifndef BUILDING_CLIPPY
462
463 #include "command.h"
464 #include "log.h"
465
cmd_graph_node_print_cb(struct graph_node * gn,struct buffer * buf)466 void cmd_graph_node_print_cb(struct graph_node *gn, struct buffer *buf)
467 {
468 static bool wasend;
469
470 char nbuf[512];
471 struct cmd_token *tok = gn->data;
472 const char *color;
473
474 if (wasend) {
475 wasend = false;
476 return;
477 }
478
479 if (tok->type == END_TKN) {
480 wasend = true;
481 return;
482 }
483
484 snprintf(nbuf, sizeof(nbuf), " n%p [ shape=box, label=<", gn);
485 buffer_putstr(buf, nbuf);
486 snprintf(nbuf, sizeof(nbuf), "<b>%s</b>",
487 lookup_msg(tokennames, tok->type, NULL));
488 buffer_putstr(buf, nbuf);
489 if (tok->attr == CMD_ATTR_DEPRECATED)
490 buffer_putstr(buf, " (d)");
491 else if (tok->attr == CMD_ATTR_HIDDEN)
492 buffer_putstr(buf, " (h)");
493 if (tok->text) {
494 if (tok->type == WORD_TKN)
495 snprintf(
496 nbuf, sizeof(nbuf),
497 "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",
498 tok->text);
499 else
500 snprintf(nbuf, sizeof(nbuf), "<br/>%s", tok->text);
501 buffer_putstr(buf, nbuf);
502 }
503
504 switch (tok->type) {
505 case START_TKN:
506 color = "#ccffcc";
507 break;
508 case FORK_TKN:
509 color = "#aaddff";
510 break;
511 case JOIN_TKN:
512 color = "#ddaaff";
513 break;
514 case WORD_TKN:
515 color = "#ffffff";
516 break;
517 default:
518 color = "#ffffff";
519 break;
520 }
521 snprintf(nbuf, sizeof(nbuf),
522 ">, style = filled, fillcolor = \"%s\" ];\n", color);
523 buffer_putstr(buf, nbuf);
524
525 for (unsigned int i = 0; i < vector_active(gn->to); i++) {
526 struct graph_node *adj = vector_slot(gn->to, i);
527
528 if (((struct cmd_token *)adj->data)->type == END_TKN) {
529 snprintf(nbuf, sizeof(nbuf), " n%p -> end%p;\n", gn,
530 adj);
531 buffer_putstr(buf, nbuf);
532 snprintf(
533 nbuf, sizeof(nbuf),
534 " end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",
535 adj);
536 } else
537 snprintf(nbuf, sizeof(nbuf), " n%p -> n%p;\n", gn,
538 adj);
539
540 buffer_putstr(buf, nbuf);
541 }
542 }
543
cmd_graph_dump_dot(struct graph * cmdgraph)544 char *cmd_graph_dump_dot(struct graph *cmdgraph)
545 {
546 struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
547
548 return graph_dump_dot(cmdgraph, start, cmd_graph_node_print_cb);
549 }
550
551 #endif /* BUILDING_CLIPPY */
552