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         case ASNUM_TKN:
 270                 return true;
 271         }
 272
 273         assert(!"Reached end of function we should never hit");
 274 }
 275
 276 static void cmd_fork_bump_attr(struct graph_node *gn, struct graph_node *join,
 277                                uint8_t attr)
 278 {
 279         size_t i;
 280         struct cmd_token *tok = gn->data;
 281         struct graph_node *stop = cmd_loopstop(gn);
 282
 283         tok->attr = attr;
 284         for (i = 0; i < vector_active(gn->to); i++) {
 285                 struct graph_node *next = vector_slot(gn->to, i);
 286                 if (next == stop || next == join)
 287                         continue;
 288                 cmd_fork_bump_attr(next, join, attr);
 289         }
 290 }
 291
 292 /* move an entire subtree from the temporary graph resulting from
 293  * parse() into the permanent graph for the command node.
 294  *
 295  * this touches rather deeply into the graph code unfortunately.
 296  */
 297 static void cmd_reparent_tree(struct graph *fromgraph, struct graph *tograph,
 298                               struct graph_node *node)
 299 {
 300         struct graph_node *stop = cmd_loopstop(node);
 301         size_t i;
 302
 303         for (i = 0; i < vector_active(fromgraph->nodes); i++)
 304                 if (vector_slot(fromgraph->nodes, i) == node) {
 305                         /* agressive iteration punching through subgraphs - may
 306                          * hit some
 307                          * nodes twice.  reparent only if found on old graph */
 308                         vector_unset(fromgraph->nodes, i);
 309                         vector_set(tograph->nodes, node);
 310                         break;
 311                 }
 312
 313         for (i = 0; i < vector_active(node->to); i++) {
 314                 struct graph_node *next = vector_slot(node->to, i);
 315                 if (next != stop)
 316                         cmd_reparent_tree(fromgraph, tograph, next);
 317         }
 318 }
 319
 320 static void cmd_free_recur(struct graph *graph, struct graph_node *node,
 321                            struct graph_node *stop)
 322 {
 323         struct graph_node *next, *nstop;
 324
 325         for (size_t i = vector_active(node->to); i; i--) {
 326                 next = vector_slot(node->to, i - 1);
 327                 if (next == stop)
 328                         continue;
 329                 nstop = cmd_loopstop(next);
 330                 if (nstop != next)
 331                         cmd_free_recur(graph, next, nstop);
 332                 cmd_free_recur(graph, nstop, stop);
 333         }
 334         graph_delete_node(graph, node);
 335 }
 336
 337 static void cmd_free_node(struct graph *graph, struct graph_node *node)
 338 {
 339         struct cmd_token *tok = node->data;
 340         if (tok->type == JOIN_TKN)
 341                 cmd_free_recur(graph, tok->forkjoin, node);
 342         graph_delete_node(graph, node);
 343 }
 344
 345 /* recursive graph merge.  call with
 346  *   old ~= new
 347  * (which holds true for old == START_TKN, new == START_TKN)
 348  */
 349 static void cmd_merge_nodes(struct graph *oldgraph, struct graph *newgraph,
 350                             struct graph_node *old, struct graph_node *new,
 351                             int direction)
 352 {
 353         struct cmd_token *tok;
 354         struct graph_node *old_skip, *new_skip;
 355         old_skip = cmd_loopstop(old);
 356         new_skip = cmd_loopstop(new);
 357
 358         assert(direction == 1 || direction == -1);
 359
 360         tok = old->data;
 361         tok->refcnt += direction;
 362
 363         size_t j, i;
 364         for (j = 0; j < vector_active(new->to); j++) {
 365                 struct graph_node *cnew = vector_slot(new->to, j);
 366                 if (cnew == new_skip)
 367                         continue;
 368
 369                 for (i = 0; i < vector_active(old->to); i++) {
 370                         struct graph_node *cold = vector_slot(old->to, i);
 371                         if (cold == old_skip)
 372                                 continue;
 373
 374                         if (cmd_nodes_equal(cold, cnew)) {
 375                                 struct cmd_token *told = cold->data,
 376                                                  *tnew = cnew->data;
 377
 378                                 if (told->type == END_TKN) {
 379                                         if (direction < 0) {
 380                                                 graph_delete_node(
 381                                                         oldgraph,
 382                                                         vector_slot(cold->to,
 383                                                                     0));
 384                                                 graph_delete_node(oldgraph,
 385                                                                   cold);
 386                                         } else
 387                                                 /* force no-match handling to
 388                                                  * install END_TKN */
 389                                                 i = vector_active(old->to);
 390                                         break;
 391                                 }
 392
 393                                 /* the entire fork compared as equal, we
 394                                  * continue after it. */
 395                                 if (told->type == FORK_TKN) {
 396                                         if (tnew->attr < told->attr
 397                                             && direction > 0)
 398                                                 cmd_fork_bump_attr(
 399                                                         cold, told->forkjoin,
 400                                                         tnew->attr);
 401                                         /* XXX: no reverse bump on uninstall */
 402                                         told = (cold = told->forkjoin)->data;
 403                                         tnew = (cnew = tnew->forkjoin)->data;
 404                                 }
 405                                 if (tnew->attr < told->attr)
 406                                         told->attr = tnew->attr;
 407
 408                                 cmd_merge_nodes(oldgraph, newgraph, cold, cnew,
 409                                                 direction);
 410                                 break;
 411                         }
 412                 }
 413                 /* nothing found => add new to old */
 414                 if (i == vector_active(old->to) && direction > 0) {
 415                         graph_remove_edge(new, cnew);
 416
 417                         cmd_reparent_tree(newgraph, oldgraph, cnew);
 418
 419                         graph_add_edge(old, cnew);
 420                 }
 421         }
 422
 423         if (!tok->refcnt)
 424                 cmd_free_node(oldgraph, old);
 425 }
 426
 427 void cmd_graph_merge(struct graph *old, struct graph *new, int direction)
 428 {
 429         assert(vector_active(old->nodes) >= 1);
 430         assert(vector_active(new->nodes) >= 1);
 431
 432         cmd_merge_nodes(old, new, vector_slot(old->nodes, 0),
 433                         vector_slot(new->nodes, 0), direction);
 434 }
 435
 436 void cmd_graph_names(struct graph *graph)
 437 {
 438         struct graph_node *start;
 439
 440         assert(vector_active(graph->nodes) >= 1);
 441         start = vector_slot(graph->nodes, 0);
 442
 443         /* apply varname on initial "[no]" */
 444         do {
 445                 if (vector_active(start->to) != 1)
 446                         break;
 447
 448                 struct graph_node *first = vector_slot(start->to, 0);
 449                 struct cmd_token *tok = first->data;
 450                 /* looking for an option with 2 choices, nothing or "no" */
 451                 if (tok->type != FORK_TKN || vector_active(first->to) != 2)
 452                         break;
 453
 454                 struct graph_node *next0 = vector_slot(first->to, 0);
 455                 struct graph_node *next1 = vector_slot(first->to, 1);
 456                 /* one needs to be empty */
 457                 if (next0 != tok->forkjoin && next1 != tok->forkjoin)
 458                         break;
 459
 460                 struct cmd_token *tok0 = next0->data;
 461                 struct cmd_token *tok1 = next1->data;
 462                 /* the other one needs to be "no" (only one will match here) */
 463                 if ((tok0->type == WORD_TKN && !strcmp(tok0->text, "no")))
 464                         cmd_token_varname_do(tok0, "no", VARNAME_AUTO);
 465                 if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))
 466                         cmd_token_varname_do(tok1, "no", VARNAME_AUTO);
 467         } while (0);
 468 }
 469
 470 #ifndef BUILDING_CLIPPY
 471
 472 #include "command.h"
 473 #include "log.h"
 474
 475 void cmd_graph_node_print_cb(struct graph_node *gn, struct buffer *buf)
 476 {
 477         static bool wasend;
 478
 479         char nbuf[512];
 480         struct cmd_token *tok = gn->data;
 481         const char *color = NULL;
 482
 483         if (wasend) {
 484                 wasend = false;
 485                 return;
 486         }
 487
 488         if (tok->type == END_TKN) {
 489                 wasend = true;
 490                 return;
 491         }
 492
 493         snprintf(nbuf, sizeof(nbuf), "  n%p [ shape=box, label=<", gn);
 494         buffer_putstr(buf, nbuf);
 495         snprintf(nbuf, sizeof(nbuf), "<b>%s</b>",
 496                  lookup_msg(tokennames, tok->type, NULL));
 497         buffer_putstr(buf, nbuf);
 498         if (tok->attr & CMD_ATTR_DEPRECATED)
 499                 buffer_putstr(buf, " (d)");
 500         /* DEPRECATED implies HIDDEN, don't print both */
 501         else if (tok->attr & CMD_ATTR_HIDDEN)
 502                 buffer_putstr(buf, " (h)");
 503         if (tok->text) {
 504                 if (tok->type == WORD_TKN)
 505                         snprintf(
 506                                 nbuf, sizeof(nbuf),
 507                                 "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",
 508                                 tok->text);
 509                 else
 510                         snprintf(nbuf, sizeof(nbuf), "<br/>%s", tok->text);
 511                 buffer_putstr(buf, nbuf);
 512         }
 513
 514         switch (tok->type) {
 515         case START_TKN:
 516                 color = "#ccffcc";
 517                 break;
 518         case FORK_TKN:
 519                 color = "#aaddff";
 520                 break;
 521         case JOIN_TKN:
 522                 color = "#ddaaff";
 523                 break;
 524         case NEG_ONLY_TKN:
 525                 color = "#ffddaa";
 526                 break;
 527         case WORD_TKN:
 528                 color = "#ffffff";
 529                 break;
 530         case RANGE_TKN:
 531         case IPV4_TKN:
 532         case IPV4_PREFIX_TKN:
 533         case IPV6_TKN:
 534         case IPV6_PREFIX_TKN:
 535         case MAC_TKN:
 536         case MAC_PREFIX_TKN:
 537         case END_TKN:
 538         case VARIABLE_TKN:
 539         case ASNUM_TKN:
 540                 color = "#ffffff";
 541                 break;
 542         }
 543
 544         /*
 545          * Some compilers have the mistaken belief that we can
 546          * get here without initializing color.
 547          */
 548         snprintf(nbuf, sizeof(nbuf),
 549                  ">, style = filled, fillcolor = \"%s\" ];\n", color);
 550         buffer_putstr(buf, nbuf);
 551
 552         for (unsigned int i = 0; i < vector_active(gn->to); i++) {
 553                 struct graph_node *adj = vector_slot(gn->to, i);
 554
 555                 if (((struct cmd_token *)adj->data)->type == END_TKN) {
 556                         snprintf(nbuf, sizeof(nbuf), "  n%p -> end%p;\n", gn,
 557                                  adj);
 558                         buffer_putstr(buf, nbuf);
 559                         snprintf(
 560                                 nbuf, sizeof(nbuf),
 561                                 "  end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",
 562                                 adj);
 563                 } else
 564                         snprintf(nbuf, sizeof(nbuf), "  n%p -> n%p;\n", gn,
 565                                  adj);
 566
 567                 buffer_putstr(buf, nbuf);
 568         }
 569 }
 570
 571 char *cmd_graph_dump_dot(struct graph *cmdgraph)
 572 {
 573         struct graph_node *start = vector_slot(cmdgraph->nodes, 0);
 574
 575         return graph_dump_dot(cmdgraph, start, cmd_graph_node_print_cb);
 576 }
 577
 578 #endif /* BUILDING_CLIPPY */