lib/command_graph.c

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