lib/command_graph.c

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