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
  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
  35 struct cmd_token *
  36 cmd_token_new (enum cmd_token_type type, u_char attr,
  37                const char *text, const char *desc)
  38 {
  39   struct cmd_token *token = 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
  52 void
  53 cmd_token_del (struct cmd_token *token)
  54 {
  55   if (!token) 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
  65 struct cmd_token *
  66 cmd_token_dup (struct cmd_token *token)
  67 {
  68   struct cmd_token *copy = 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 = token->varname ? XSTRDUP (MTYPE_CMD_VAR, token->varname) : NULL;
  75
  76   return copy;
  77 }
  78
  79 void cmd_token_varname_set(struct cmd_token *token, const char *varname)
  80 {
  81   XFREE (MTYPE_CMD_VAR, token->varname);
  82   if (!varname)
  83     {
  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       {
  94         case '-':
  95         case '+':
  96         case '*':
  97         case ':':
  98           token->varname[i] = '_';
  99           break;
 100         default:
 101           token->varname[i] = tolower (varname[i]);
 102       }
 103   token->varname[len] = '\0';
 104 }
 105
 106 static bool
 107 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 *
 122 cmd_loopstop(struct graph_node *gn)
 123 {
 124   struct cmd_token *tok = gn->data;
 125   if (tok->type == JOIN_TKN)
 126     return tok->forkjoin;
 127   else
 128     return gn;
 129 }
 130
 131 static bool
 132 cmd_subgraph_equal (struct graph_node *ga, struct graph_node *gb,
 133                     struct graph_node *a_join)
 134 {
 135   size_t i, j;
 136   struct graph_node *a_fork, *b_fork;
 137   a_fork = cmd_loopstop (ga);
 138   b_fork = cmd_loopstop (gb);
 139
 140   if (vector_active (ga->to) != vector_active (gb->to))
 141     return false;
 142   for (i = 0; i < vector_active (ga->to); i++)
 143     {
 144       struct graph_node *cga = vector_slot (ga->to, i);
 145
 146       for (j = 0; j < vector_active (gb->to); j++)
 147         {
 148           struct graph_node *cgb = vector_slot (gb->to, i);
 149
 150           if (cga == a_fork && cgb != b_fork)
 151             continue;
 152           if (cga == a_fork && cgb == b_fork)
 153             break;
 154
 155           if (cmd_nodes_equal (cga, cgb))
 156             {
 157               if (cga == a_join)
 158                 break;
 159               if (cmd_subgraph_equal (cga, cgb, a_join))
 160                 break;
 161             }
 162         }
 163       if (j == vector_active (gb->to))
 164         return false;
 165     }
 166   return true;
 167 }
 168
 169 /* deep compare -- for FORK_TKN, the entire subgraph is compared.
 170  * this is what's needed since we're not currently trying to partially
 171  * merge subgraphs */
 172 static bool
 173 cmd_nodes_equal (struct graph_node *ga, struct graph_node *gb)
 174 {
 175   struct cmd_token *a = ga->data, *b = gb->data;
 176
 177   if (a->type != b->type || a->allowrepeat != b->allowrepeat)
 178     return false;
 179   if (a->type < SPECIAL_TKN && strcmp (a->text, b->text))
 180     return false;
 181   /* one a ..., the other not. */
 182   if (cmd_nodes_link (ga, ga) != cmd_nodes_link (gb, gb))
 183     return false;
 184   if (!a->varname != !b->varname)
 185     return false;
 186   if (a->varname && strcmp (a->varname, b->varname))
 187     return false;
 188
 189   switch (a->type)
 190     {
 191     case RANGE_TKN:
 192       return a->min == b->min && a->max == b->max;
 193
 194     case FORK_TKN:
 195       /* one is keywords, the other just option or selector ... */
 196       if (cmd_nodes_link (a->forkjoin, ga) != cmd_nodes_link (b->forkjoin, gb))
 197         return false;
 198       if (cmd_nodes_link (ga, a->forkjoin) != cmd_nodes_link (gb, b->forkjoin))
 199         return false;
 200       return cmd_subgraph_equal (ga, gb, a->forkjoin);
 201
 202     default:
 203       return true;
 204     }
 205 }
 206
 207 static void
 208 cmd_fork_bump_attr (struct graph_node *gn, struct graph_node *join,
 209                     u_char attr)
 210 {
 211   size_t i;
 212   struct cmd_token *tok = gn->data;
 213   struct graph_node *stop = cmd_loopstop (gn);
 214
 215   tok->attr = attr;
 216   for (i = 0; i < vector_active (gn->to); i++)
 217     {
 218       struct graph_node *next = vector_slot (gn->to, i);
 219       if (next == stop || next == join)
 220         continue;
 221       cmd_fork_bump_attr (next, join, attr);
 222     }
 223 }
 224
 225 /* move an entire subtree from the temporary graph resulting from
 226  * parse() into the permanent graph for the command node.
 227  *
 228  * this touches rather deeply into the graph code unfortunately.
 229  */
 230 static void
 231 cmd_reparent_tree (struct graph *fromgraph, struct graph *tograph,
 232                    struct graph_node *node)
 233 {
 234   struct graph_node *stop = cmd_loopstop (node);
 235   size_t i;
 236
 237   for (i = 0; i < vector_active (fromgraph->nodes); i++)
 238     if (vector_slot (fromgraph->nodes, i) == node)
 239       {
 240         /* agressive iteration punching through subgraphs - may hit some
 241          * nodes twice.  reparent only if found on old graph */
 242         vector_unset (fromgraph->nodes, i);
 243         vector_set (tograph->nodes, node);
 244         break;
 245       }
 246
 247   for (i = 0; i < vector_active (node->to); i++)
 248     {
 249       struct graph_node *next = vector_slot (node->to, i);
 250       if (next != stop)
 251         cmd_reparent_tree (fromgraph, tograph, next);
 252     }
 253 }
 254
 255 static void
 256 cmd_free_recur (struct graph *graph, struct graph_node *node,
 257                 struct graph_node *stop)
 258 {
 259   struct graph_node *next, *nstop;
 260
 261   for (size_t i = vector_active (node->to); i; i--)
 262     {
 263       next = vector_slot (node->to, i - 1);
 264       if (next == stop)
 265         continue;
 266       nstop = cmd_loopstop (next);
 267       if (nstop != next)
 268         cmd_free_recur (graph, next, nstop);
 269       cmd_free_recur (graph, nstop, stop);
 270     }
 271   graph_delete_node (graph, node);
 272 }
 273
 274 static void
 275 cmd_free_node (struct graph *graph, struct graph_node *node)
 276 {
 277   struct cmd_token *tok = node->data;
 278   if (tok->type == JOIN_TKN)
 279     cmd_free_recur (graph, tok->forkjoin, node);
 280   graph_delete_node (graph, node);
 281 }
 282
 283 /* recursive graph merge.  call with
 284  *   old ~= new
 285  * (which holds true for old == START_TKN, new == START_TKN)
 286  */
 287 static void
 288 cmd_merge_nodes (struct graph *oldgraph, struct graph *newgraph,
 289                  struct graph_node *old, struct graph_node *new,
 290                  int direction)
 291 {
 292   struct cmd_token *tok;
 293   struct graph_node *old_skip, *new_skip;
 294   old_skip = cmd_loopstop (old);
 295   new_skip = cmd_loopstop (new);
 296
 297   assert (direction == 1 || direction == -1);
 298
 299   tok = old->data;
 300   tok->refcnt += direction;
 301
 302   size_t j, i;
 303   for (j = 0; j < vector_active (new->to); j++)
 304     {
 305       struct graph_node *cnew = vector_slot (new->to, j);
 306       if (cnew == new_skip)
 307         continue;
 308
 309       for (i = 0; i < vector_active (old->to); i++)
 310         {
 311           struct graph_node *cold = vector_slot (old->to, i);
 312           if (cold == old_skip)
 313             continue;
 314
 315           if (cmd_nodes_equal (cold, cnew))
 316             {
 317               struct cmd_token *told = cold->data, *tnew = cnew->data;
 318
 319               if (told->type == END_TKN)
 320                 {
 321                   if (direction < 0)
 322                     {
 323                       graph_delete_node (oldgraph, vector_slot (cold->to, 0));
 324                       graph_delete_node (oldgraph, cold);
 325                     }
 326                   else
 327                     /* force no-match handling to install END_TKN */
 328                     i = vector_active (old->to);
 329                   break;
 330                 }
 331
 332               /* the entire fork compared as equal, we continue after it. */
 333               if (told->type == FORK_TKN)
 334                 {
 335                   if (tnew->attr < told->attr && direction > 0)
 336                     cmd_fork_bump_attr (cold, told->forkjoin, tnew->attr);
 337                   /* XXX: no reverse bump on uninstall */
 338                   told = (cold = told->forkjoin)->data;
 339                   tnew = (cnew = tnew->forkjoin)->data;
 340                 }
 341               if (tnew->attr < told->attr)
 342                 told->attr = tnew->attr;
 343
 344               cmd_merge_nodes (oldgraph, newgraph, cold, cnew, direction);
 345               break;
 346             }
 347         }
 348       /* nothing found => add new to old */
 349       if (i == vector_active (old->to) && direction > 0)
 350         {
 351           assert (vector_count (cnew->from) ==
 352                           cmd_nodes_link (cnew, cnew) ? 2 : 1);
 353           graph_remove_edge (new, cnew);
 354
 355           cmd_reparent_tree (newgraph, oldgraph, cnew);
 356
 357           graph_add_edge (old, cnew);
 358         }
 359     }
 360
 361   if (!tok->refcnt)
 362     cmd_free_node (oldgraph, old);
 363 }
 364
 365 void
 366 cmd_graph_merge (struct graph *old, struct graph *new, int direction)
 367 {
 368   assert (vector_active (old->nodes) >= 1);
 369   assert (vector_active (new->nodes) >= 1);
 370
 371   cmd_merge_nodes (old, new,
 372                    vector_slot (old->nodes, 0), vector_slot (new->nodes, 0),
 373                    direction);
 374 }
 375
 376 static void
 377 cmd_node_names (struct graph_node *gn, struct graph_node *join,
 378                 const char *prevname)
 379 {
 380   size_t i;
 381   struct cmd_token *tok = gn->data, *jointok;
 382   struct graph_node *stop = cmd_loopstop (gn);
 383
 384   switch (tok->type)
 385     {
 386     case WORD_TKN:
 387       prevname = tok->text;
 388       break;
 389
 390     case VARIABLE_TKN:
 391       if (!tok->varname
 392           && strcmp (tok->text, "WORD")
 393           && strcmp (tok->text, "NAME"))
 394         cmd_token_varname_set (tok, tok->text);
 395       /* fallthrough */
 396     case RANGE_TKN:
 397     case IPV4_TKN:
 398     case IPV4_PREFIX_TKN:
 399     case IPV6_TKN:
 400     case IPV6_PREFIX_TKN:
 401       if (!tok->varname && prevname)
 402         cmd_token_varname_set (tok, prevname);
 403       prevname = NULL;
 404       break;
 405
 406     case START_TKN:
 407     case END_TKN:
 408     case JOIN_TKN:
 409       /* "<foo|bar> WORD" -> word is not "bar" or "foo" */
 410       prevname = NULL;
 411       break;
 412
 413     case FORK_TKN:
 414       /* apply "<A.B.C.D|X:X::X:X>$name" */
 415       jointok = tok->forkjoin->data;
 416       if (!jointok->varname)
 417         break;
 418       for (i = 0; i < vector_active (tok->forkjoin->from); i++)
 419         {
 420           struct graph_node *tail = vector_slot (tok->forkjoin->from, i);
 421           struct cmd_token *tailtok = tail->data;
 422           if (tail == gn || tailtok->varname)
 423             continue;
 424           cmd_token_varname_set (tailtok, jointok->varname);
 425         }
 426       break;
 427     }
 428
 429   for (i = 0; i < vector_active (gn->to); i++)
 430     {
 431       struct graph_node *next = vector_slot (gn->to, i);
 432       if (next == stop || next == join)
 433         continue;
 434       cmd_node_names (next, join, prevname);
 435     }
 436
 437   if (tok->type == FORK_TKN && tok->forkjoin != join)
 438     cmd_node_names (tok->forkjoin, join, NULL);
 439 }
 440
 441 void
 442 cmd_graph_names (struct graph *graph)
 443 {
 444   struct graph_node *start;
 445
 446   assert (vector_active (graph->nodes) >= 1);
 447   start = vector_slot (graph->nodes, 0);
 448
 449   /* apply varname on initial "[no]" */
 450   do
 451     {
 452       if (vector_active (start->to) != 1)
 453         break;
 454
 455       struct graph_node *first = vector_slot (start->to, 0);
 456       struct cmd_token *tok = first->data;
 457       /* looking for an option with 2 choices, nothing or "no" */
 458       if (tok->type != FORK_TKN || vector_active (first->to) != 2)
 459         break;
 460
 461       struct graph_node *next0 = vector_slot (first->to, 0);
 462       struct graph_node *next1 = vector_slot (first->to, 1);
 463       /* one needs to be empty */
 464       if (next0 != tok->forkjoin && next1 != tok->forkjoin)
 465         break;
 466
 467       struct cmd_token *tok0 = next0->data;
 468       struct cmd_token *tok1 = next1->data;
 469       /* the other one needs to be "no" (only one will match here) */
 470       if ((tok0->type == WORD_TKN && !strcmp(tok0->text, "no")))
 471         cmd_token_varname_set (tok0, "no");
 472       if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))
 473         cmd_token_varname_set (tok1, "no");
 474     }
 475   while (0);
 476
 477   cmd_node_names (start, NULL, NULL);
 478 }