tools/permutations.c

   1 /*
   2  * Generates all possible matching inputs for a command string.
   3  * --
   4  * Copyright (C) 2016 Cumulus Networks, Inc.
   5  *
   6  * This file is part of GNU Zebra.
   7  *
   8  * GNU Zebra is free software; you can redistribute it and/or modify it
   9  * under the terms of the GNU General Public License as published by the
  10  * Free Software Foundation; either version 2, or (at your option) any
  11  * later version.
  12  *
  13  * GNU Zebra is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  20  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  21  * 02111-1307, USA.
  22  */
  23
  24 #include "command.h"
  25 #include "graph.h"
  26 #include "vector.h"
  27
  28 #define USAGE "usage: permutations <cmdstr>"
  29
  30 void
  31 permute (struct graph_node *);
  32 void
  33 pretty_print_graph (struct graph_node *start, int level);
  34
  35 int main (int argc, char *argv[])
  36 {
  37   if (argc < 2)
  38   {
  39     fprintf(stdout, USAGE"\n");
  40     exit(EXIT_SUCCESS);
  41   }
  42   struct cmd_element *cmd = calloc (1, sizeof (struct cmd_element));
  43   cmd->string = strdup(argv[1]);
  44
  45   struct graph *graph = graph_new();
  46   struct cmd_token *token = new_cmd_token (START_TKN, cmd->attr, NULL, NULL);
  47   graph_new_node (graph, token, NULL);
  48   command_parse_format (graph, cmd);
  49
  50   permute (vector_slot (graph->nodes, 0));
  51   pretty_print_graph (vector_slot (graph->nodes, 0), 0);
  52 }
  53
  54 void
  55 permute (struct graph_node *start)
  56 {
  57   static struct list *position = NULL;
  58   if (!position) position = list_new ();
  59
  60   // recursive dfs
  61   listnode_add (position, start);
  62   for (unsigned int i = 0; i < vector_active (start->to); i++)
  63   {
  64     struct graph_node *gn = vector_slot (start->to, i);
  65     struct cmd_token *tok = gn->data;
  66     if (tok->type == END_TKN)
  67     {
  68       struct graph_node *gnn;
  69       struct listnode *ln;
  70       for (ALL_LIST_ELEMENTS_RO (position,ln,gnn))
  71       {
  72         struct cmd_token *tt = gnn->data;
  73         if (tt->type < SPECIAL_TKN)
  74           fprintf (stdout, "%s ", tt->text);
  75       }
  76       fprintf (stdout, "\n");
  77     }
  78     else
  79       permute (gn);
  80   }
  81   list_delete_node (position, listtail(position));
  82 }
  83
  84 void
  85 pretty_print_graph (struct graph_node *start, int level)
  86 {
  87   // print this node
  88   struct cmd_token *tok = start->data;
  89   fprintf (stdout, "%s[%d] ", tok->text, tok->type);
  90
  91   int numto = vector_active (start->to);
  92   if (numto)
  93     {
  94       if (numto > 1)
  95         fprintf (stdout, "\n");
  96       for (unsigned int i = 0; i < vector_active (start->to); i++)
  97         {
  98           struct graph_node *adj = vector_slot (start->to, i);
  99           // if we're listing multiple children, indent!
 100           if (numto > 1)
 101             for (int j = 0; j < level+1; j++)
 102               fprintf (stdout, "    ");
 103           // if this node is a vararg, just print *
 104           if (adj == start)
 105             fprintf (stdout, "*");
 106           else
 107             pretty_print_graph (adj, numto > 1 ? level+1 : level);
 108         }
 109     }
 110   else
 111     fprintf(stdout, "\n");
 112 }