// SPDX-License-Identifier: GPL-2.0-or-later

/*

 * CLI graph handling

 *

 * --

 * Copyright (C) 2016 Cumulus Networks, Inc.

 * Copyright (C) 1997, 98, 99 Kunihiro Ishiguro

 * Copyright (C) 2013 by Open Source Routing.

 * Copyright (C) 2013 by Internet Systems Consortium, Inc. ("ISC")

 */

#include <zebra.h>

#include "command_graph.h"

DEFINE_MTYPE_STATIC(LIB, CMD_TOKENS, "Command Tokens");

DEFINE_MTYPE_STATIC(LIB, CMD_DESC, "Command Token Text");

DEFINE_MTYPE_STATIC(LIB, CMD_TEXT, "Command Token Help");

DEFINE_MTYPE(LIB, CMD_ARG, "Command Argument");

DEFINE_MTYPE_STATIC(LIB, CMD_VAR, "Command Argument Name");

struct cmd_token *cmd_token_new(enum cmd_token_type type, uint8_t attr,

        const char *text, const char *desc)

{

  struct cmd_token *token =

    XCALLOC(MTYPE_CMD_TOKENS, sizeof(struct cmd_token));

  token->type = type;

  token->attr = attr;

  token->text = text ? XSTRDUP(MTYPE_CMD_TEXT, text) : NULL;

  token->desc = desc ? XSTRDUP(MTYPE_CMD_DESC, desc) : NULL;

  token->refcnt = 1;

  token->arg = NULL;

  token->allowrepeat = false;

  token->varname = NULL;

  return token;

}

void cmd_token_del(struct cmd_token *token)

{

  if (!token)

    return;

  XFREE(MTYPE_CMD_TEXT, token->text);

  XFREE(MTYPE_CMD_DESC, token->desc);

  XFREE(MTYPE_CMD_ARG, token->arg);

  XFREE(MTYPE_CMD_VAR, token->varname);

  XFREE(MTYPE_CMD_TOKENS, token);

}

struct cmd_token *cmd_token_dup(struct cmd_token *token)

{

  struct cmd_token *copy =

    cmd_token_new(token->type, token->attr, NULL, NULL);

  copy->max = token->max;

  copy->min = token->min;

  copy->text = token->text ? XSTRDUP(MTYPE_CMD_TEXT, token->text) : NULL;

  copy->desc = token->desc ? XSTRDUP(MTYPE_CMD_DESC, token->desc) : NULL;

  copy->arg = token->arg ? XSTRDUP(MTYPE_CMD_ARG, token->arg) : NULL;

  copy->varname =

    token->varname ? XSTRDUP(MTYPE_CMD_VAR, token->varname) : NULL;

  return copy;

}

static void cmd_token_varname_do(struct cmd_token *token, const char *varname,

         uint8_t varname_src)

{

  if (token->varname_src >= varname_src)

    return;

  XFREE(MTYPE_CMD_VAR, token->varname);

  size_t len = strlen(varname), i;

  token->varname = XMALLOC(MTYPE_CMD_VAR, len + 1);

  token->varname_src = varname_src;

  for (i = 0; i < len; i++)

    switch (varname[i]) {

    case '-':

    case '+':

    case '*':

    case ':':

      token->varname[i] = '_';

      break;

    default:

      token->varname[i] = tolower((unsigned char)varname[i]);

    }

  token->varname[len] = '\0';

}

void cmd_token_varname_set(struct cmd_token *token, const char *varname)

{

  if (varname) {

    cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);

    return;

  }

  if (token->type == VARIABLE_TKN) {

    if (strcmp(token->text, "WORD") && strcmp(token->text, "NAME"))

      cmd_token_varname_do(token, token->text, VARNAME_TEXT);

  }

}

static void cmd_token_varname_fork(struct graph_node *node,

           struct cmd_token *prevtoken)

{

  for (size_t i = 0; i < vector_active(node->to); i++) {

    struct graph_node *next = vector_slot(node->to, i);

    struct cmd_token *nexttoken = next->data;

    if (nexttoken->type == FORK_TKN) {

      cmd_token_varname_fork(next, prevtoken);

      continue;

    }

    if (nexttoken->varname)

      continue;

    if (!IS_VARYING_TOKEN(nexttoken->type))

      continue;

    cmd_token_varname_do(nexttoken, prevtoken->text, VARNAME_TEXT);

  }

}

void cmd_token_varname_join(struct graph_node *join, const char *varname)

{

  if (!varname)

    return;

  for (size_t i = 0; i < vector_active(join->from); i++) {

    struct graph_node *prev = vector_slot(join->from, i);

    struct cmd_token *token = prev->data;

    if (token->type == JOIN_TKN)

      cmd_token_varname_join(prev, varname);

    else if (token->type < SPECIAL_TKN)

      cmd_token_varname_do(token, varname, VARNAME_EXPLICIT);

  }

}

void cmd_token_varname_seqappend(struct graph_node *node)

{

  struct graph_node *prevnode = node;

  struct cmd_token *token = node->data;

  struct cmd_token *prevtoken;

  if (token->type == WORD_TKN)

    return;

  do {

    if (vector_active(prevnode->from) != 1)

      return;

    prevnode = vector_slot(prevnode->from, 0);

    prevtoken = prevnode->data;

  } while (prevtoken->type == FORK_TKN);

  if (prevtoken->type != WORD_TKN)

    return;

  if (token->type == FORK_TKN)

    cmd_token_varname_fork(node, prevtoken);

  else

    cmd_token_varname_do(token, prevtoken->text, VARNAME_TEXT);

}

static bool cmd_nodes_link(struct graph_node *from, struct graph_node *to)

{

  for (size_t i = 0; i < vector_active(from->to); i++)

    if (vector_slot(from->to, i) == to)

      return true;

  return false;

}

static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb);

/* returns a single node to be excluded as "next" from iteration

 * - for JOIN_TKN, never continue back to the FORK_TKN

 * - in all other cases, don't try the node itself (in case of "...")

 */

static inline struct graph_node *cmd_loopstop(struct graph_node *gn)

{

  struct cmd_token *tok = gn->data;

  if (tok->type == JOIN_TKN)

    return tok->forkjoin;

  else

    return gn;

}

static bool cmd_subgraph_equal(struct graph_node *ga, struct graph_node *gb,

             struct graph_node *a_join)

{

  size_t i, j;

  struct graph_node *a_fork, *b_fork;

  a_fork = cmd_loopstop(ga);

  b_fork = cmd_loopstop(gb);

  if (vector_active(ga->to) != vector_active(gb->to))

    return false;

  for (i = 0; i < vector_active(ga->to); i++) {

    struct graph_node *cga = vector_slot(ga->to, i);

    for (j = 0; j < vector_active(gb->to); j++) {

      struct graph_node *cgb = vector_slot(gb->to, i);

      if (cga == a_fork && cgb != b_fork)

        continue;

      if (cga == a_fork && cgb == b_fork)

        break;

      if (cmd_nodes_equal(cga, cgb)) {

        if (cga == a_join)

          break;

        if (cmd_subgraph_equal(cga, cgb, a_join))

          break;

      }

    }

    if (j == vector_active(gb->to))

      return false;

  }

  return true;

}

/* deep compare -- for FORK_TKN, the entire subgraph is compared.

 * this is what's needed since we're not currently trying to partially

 * merge subgraphs */

static bool cmd_nodes_equal(struct graph_node *ga, struct graph_node *gb)

{

  struct cmd_token *a = ga->data, *b = gb->data;

  if (a->type != b->type || a->allowrepeat != b->allowrepeat)

    return false;

  if (a->type < SPECIAL_TKN && strcmp(a->text, b->text))

    return false;

  /* one a ..., the other not. */

  if (cmd_nodes_link(ga, ga) != cmd_nodes_link(gb, gb))

    return false;

  if (!a->varname != !b->varname)

    return false;

  if (a->varname && strcmp(a->varname, b->varname))

    return false;

  switch (a->type) {

  case RANGE_TKN:

    return a->min == b->min && a->max == b->max;

  case FORK_TKN:

    /* one is keywords, the other just option or selector ... */

    if (cmd_nodes_link(a->forkjoin, ga)

        != cmd_nodes_link(b->forkjoin, gb))

      return false;

    if (cmd_nodes_link(ga, a->forkjoin)

        != cmd_nodes_link(gb, b->forkjoin))

      return false;

    return cmd_subgraph_equal(ga, gb, a->forkjoin);

  case VARIABLE_TKN:

  case IPV4_TKN:

  case IPV4_PREFIX_TKN:

  case IPV6_PREFIX_TKN:

  case IPV6_TKN:

  case MAC_TKN:

  case MAC_PREFIX_TKN:

  case JOIN_TKN:

  case START_TKN:

  case END_TKN:

  case NEG_ONLY_TKN:

  case WORD_TKN:

  case ASNUM_TKN:

    return true;

  }

  assert(!"Reached end of function we should never hit");

}

static void cmd_fork_bump_attr(struct graph_node *gn, struct graph_node *join,

             uint8_t attr)

{

  size_t i;

  struct cmd_token *tok = gn->data;

  struct graph_node *stop = cmd_loopstop(gn);

  tok->attr = attr;

  for (i = 0; i < vector_active(gn->to); i++) {

    struct graph_node *next = vector_slot(gn->to, i);

    if (next == stop || next == join)

      continue;

    cmd_fork_bump_attr(next, join, attr);

  }

}

/* move an entire subtree from the temporary graph resulting from

 * parse() into the permanent graph for the command node.

 *

 * this touches rather deeply into the graph code unfortunately.

 */

static void cmd_reparent_tree(struct graph *fromgraph, struct graph *tograph,

            struct graph_node *node)

{

  struct graph_node *stop = cmd_loopstop(node);

  size_t i;

  for (i = 0; i < vector_active(fromgraph->nodes); i++)

    if (vector_slot(fromgraph->nodes, i) == node) {

      /* agressive iteration punching through subgraphs - may

       * hit some

       * nodes twice.  reparent only if found on old graph */

      vector_unset(fromgraph->nodes, i);

      vector_set(tograph->nodes, node);

      break;

    }

  for (i = 0; i < vector_active(node->to); i++) {

    struct graph_node *next = vector_slot(node->to, i);

    if (next != stop)

      cmd_reparent_tree(fromgraph, tograph, next);

  }

}

static void cmd_free_recur(struct graph *graph, struct graph_node *node,

         struct graph_node *stop)

{

  struct graph_node *next, *nstop;

  for (size_t i = vector_active(node->to); i; i--) {

    next = vector_slot(node->to, i - 1);

    if (next == stop)

      continue;

    nstop = cmd_loopstop(next);

    if (nstop != next)

      cmd_free_recur(graph, next, nstop);

    cmd_free_recur(graph, nstop, stop);

  }

  graph_delete_node(graph, node);

}

static void cmd_free_node(struct graph *graph, struct graph_node *node)

{

  struct cmd_token *tok = node->data;

  if (tok->type == JOIN_TKN)

    cmd_free_recur(graph, tok->forkjoin, node);

  graph_delete_node(graph, node);

}

/* recursive graph merge.  call with

 *   old ~= new

 * (which holds true for old == START_TKN, new == START_TKN)

 */

static void cmd_merge_nodes(struct graph *oldgraph, struct graph *newgraph,

          struct graph_node *old, struct graph_node *new,

          int direction)

{

  struct cmd_token *tok;

  struct graph_node *old_skip, *new_skip;

  old_skip = cmd_loopstop(old);

  new_skip = cmd_loopstop(new);

  assert(direction == 1 || direction == -1);

  tok = old->data;

  tok->refcnt += direction;

  size_t j, i;

  for (j = 0; j < vector_active(new->to); j++) {

    struct graph_node *cnew = vector_slot(new->to, j);

    if (cnew == new_skip)

      continue;

    for (i = 0; i < vector_active(old->to); i++) {

      struct graph_node *cold = vector_slot(old->to, i);

      if (cold == old_skip)

        continue;

      if (cmd_nodes_equal(cold, cnew)) {

        struct cmd_token *told = cold->data,

             *tnew = cnew->data;

        if (told->type == END_TKN) {

          if (direction < 0) {

            graph_delete_node(

              oldgraph,

              vector_slot(cold->to,

                    0));

            graph_delete_node(oldgraph,

                  cold);

          } else

            /* force no-match handling to

             * install END_TKN */

            i = vector_active(old->to);

          break;

        }

        /* the entire fork compared as equal, we

         * continue after it. */

        if (told->type == FORK_TKN) {

          if (tnew->attr < told->attr

              && direction > 0)

            cmd_fork_bump_attr(

              cold, told->forkjoin,

              tnew->attr);

          /* XXX: no reverse bump on uninstall */

          told = (cold = told->forkjoin)->data;

          tnew = (cnew = tnew->forkjoin)->data;

        }

        if (tnew->attr < told->attr)

          told->attr = tnew->attr;

        cmd_merge_nodes(oldgraph, newgraph, cold, cnew,

            direction);

        break;

      }

    }

    /* nothing found => add new to old */

    if (i == vector_active(old->to) && direction > 0) {

      graph_remove_edge(new, cnew);

      cmd_reparent_tree(newgraph, oldgraph, cnew);

      graph_add_edge(old, cnew);

    }

  }

  if (!tok->refcnt)

    cmd_free_node(oldgraph, old);

}

void cmd_graph_merge(struct graph *old, struct graph *new, int direction)

{

  assert(vector_active(old->nodes) >= 1);

  assert(vector_active(new->nodes) >= 1);

  cmd_merge_nodes(old, new, vector_slot(old->nodes, 0),

      vector_slot(new->nodes, 0), direction);

}

void cmd_graph_names(struct graph *graph)

{

  struct graph_node *start;

  assert(vector_active(graph->nodes) >= 1);

  start = vector_slot(graph->nodes, 0);

  /* apply varname on initial "[no]" */

  do {

    if (vector_active(start->to) != 1)

      break;

    struct graph_node *first = vector_slot(start->to, 0);

    struct cmd_token *tok = first->data;

    /* looking for an option with 2 choices, nothing or "no" */

    if (tok->type != FORK_TKN || vector_active(first->to) != 2)

      break;

    struct graph_node *next0 = vector_slot(first->to, 0);

    struct graph_node *next1 = vector_slot(first->to, 1);

    /* one needs to be empty */

    if (next0 != tok->forkjoin && next1 != tok->forkjoin)

      break;

    struct cmd_token *tok0 = next0->data;

    struct cmd_token *tok1 = next1->data;

    /* the other one needs to be "no" (only one will match here) */

    if ((tok0->type == WORD_TKN && !strcmp(tok0->text, "no")))

      cmd_token_varname_do(tok0, "no", VARNAME_AUTO);

    if ((tok1->type == WORD_TKN && !strcmp(tok1->text, "no")))

      cmd_token_varname_do(tok1, "no", VARNAME_AUTO);

  } while (0);

}

#ifndef BUILDING_CLIPPY

#include "command.h"

#include "log.h"

void cmd_graph_node_print_cb(struct graph_node *gn, struct buffer *buf)

{

  static bool wasend;

  char nbuf[512];

  struct cmd_token *tok = gn->data;

  const char *color = NULL;

  if (wasend) {

    wasend = false;

    return;

  }

  if (tok->type == END_TKN) {

    wasend = true;

    return;

  }

  snprintf(nbuf, sizeof(nbuf), "  n%p [ shape=box, label=<", gn);

  buffer_putstr(buf, nbuf);

  snprintf(nbuf, sizeof(nbuf), "<b>%s</b>",

     lookup_msg(tokennames, tok->type, NULL));

  buffer_putstr(buf, nbuf);

  if (tok->attr & CMD_ATTR_DEPRECATED)

    buffer_putstr(buf, " (d)");

  /* DEPRECATED implies HIDDEN, don't print both */

  else if (tok->attr & CMD_ATTR_HIDDEN)

    buffer_putstr(buf, " (h)");

  if (tok->text) {

    if (tok->type == WORD_TKN)

      snprintf(

        nbuf, sizeof(nbuf),

        "<br/>\"<font color=\"#0055ff\" point-size=\"11\"><b>%s</b></font>\"",

        tok->text);

    else

      snprintf(nbuf, sizeof(nbuf), "<br/>%s", tok->text);

    buffer_putstr(buf, nbuf);

  }

  switch (tok->type) {

  case START_TKN:

    color = "#ccffcc";

    break;

  case FORK_TKN:

    color = "#aaddff";

    break;

  case JOIN_TKN:

    color = "#ddaaff";

    break;

  case NEG_ONLY_TKN:

    color = "#ffddaa";

    break;

  case WORD_TKN:

    color = "#ffffff";

    break;

  case RANGE_TKN:

  case IPV4_TKN:

  case IPV4_PREFIX_TKN:

  case IPV6_TKN:

  case IPV6_PREFIX_TKN:

  case MAC_TKN:

  case MAC_PREFIX_TKN:

  case END_TKN:

  case VARIABLE_TKN:

  case ASNUM_TKN:

    color = "#ffffff";

    break;

  }

  /*

   * Some compilers have the mistaken belief that we can

   * get here without initializing color.

   */

  snprintf(nbuf, sizeof(nbuf),

     ">, style = filled, fillcolor = \"%s\" ];\n", color);

  buffer_putstr(buf, nbuf);

  for (unsigned int i = 0; i < vector_active(gn->to); i++) {

    struct graph_node *adj = vector_slot(gn->to, i);

    if (((struct cmd_token *)adj->data)->type == END_TKN) {

      snprintf(nbuf, sizeof(nbuf), "  n%p -> end%p;\n", gn,

         adj);

      buffer_putstr(buf, nbuf);

      snprintf(

        nbuf, sizeof(nbuf),

        "  end%p [ shape=box, label=<end>, style = filled, fillcolor = \"#ffddaa\" ];\n",

        adj);

    } else

      snprintf(nbuf, sizeof(nbuf), "  n%p -> n%p;\n", gn,

         adj);

    buffer_putstr(buf, nbuf);

  }

}

char *cmd_graph_dump_dot(struct graph *cmdgraph)

{

  struct graph_node *start = vector_slot(cmdgraph->nodes, 0);

  return graph_dump_dot(cmdgraph, start, cmd_graph_node_print_cb);

}

#endif /* BUILDING_CLIPPY */