CLIgen code stuck in recursion at the time of parsing

[ashuagarwal01]

Hi,

I am trying to parse following sample input file and cligen code hangs at the time of parsing. I enabled debug flag and screen is flooded with following message.
cgy_list_push

The cligen file I am using is as below:

`#CLIgen input file
treename="main";
@config_command;

treename="config_command";
show("Retrieve yang object data") @show, show_cb();

treename="container_inventory_list_show";
list(""), fn_cb();{
("list key name"), fn_cb();
{
[aa ("des")]
[ab ("des")]
[ac ("des")]
[ad ("des")]
[ae ("des")]
[af ("des")]
[ag ("des")]
[ah ("des")]
[ai ("des")]
[aj ("des")]
[ak ("des")]
[al ("des")]
[am ("des")]
[an ("des")]
[ao ("des")]
[ap ("des")]
[aq ("des")]
[ar ("des")]
[as ("des")]
[at ("des")]
[au ("des")]
[av ("des")]
[aw ("des")]
[ax ("des")]
[ay ("des")]
[az ("des")]
[ba ("des")]
[bb ("des")]
[bc ("des")]
[bd ("des")]
[be ("des")]
[bf ("des")], fn_cb();
}
}

treename="container_inventory_show";
inventory(""), fn_cb();
{
[@container_inventory_list_show], fn_cb();
}

treename="container_show";
container(""), fn_cb();
{
<string length[1:32]>("The name of the container."), fn_cb();
{
[@container_inventory_show], fn_cb();
}
}

treename="show";
@container_show;
`

• I tried to narrow down the problem and come up with following observations: If i remove some parameters from container_inventory_list_show tree (say if I remove ax to be), the code works perfectly fine. After adding new parameter one by one in same tree, the code become slower. And after adding few more parameters, the cligen code hang in parsing.
• The issue is not in bison because I tried with different bison versions (2.6, 3.0.4, 3.2 etc) and issue still there.

[olofhagsand]

@ashuagarwal01
Interesting.
First, this scaling problem does not depend on trees. So simplifying it and reducing makes it easier to handle:

list(""), fn_cb();{
    [aa ("des")]
    [ab ("des")]
    [ac ("des")], fn_cb();
}

Second, the [] is the optional operator and they are arranged in a sequence. I.e [aa][ab][ac] etc. It is implemented to expand all possibilities, and when a large of number of these are arranged in a sequence you get a state explosion . For every [] you add you double the number of states. So
as an example, [aa][ab][ac] results in 8 states, and the list above with 32 options have 2^32 = 4M states. There may even be a problem when going to from 31 to 32 options due to ints and not unsigned ints.

To see this, you can use the -p command-line to cligen_file. If you run the syntax above as you can see how it expand to the eight basic sequences:

olof@vandal> ./cligen_file -p -f foo
list, fn_cb(), fn_cb();{
   aa("des"), fn_cb();{
      ab("des"), fn_cb();{
         ac("des"), fn_cb();
      }
      ac("des"), fn_cb();
   }
   ab("des"), fn_cb();{
      ac("des"), fn_cb();
   }
   ac("des"), fn_cb();
}

If you have 32 options, there will be 4M of these. This will consume memory (quadratically), I dont think CPU is a problem. See for example for some 20 entries:

USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
olof     18925 25.4 37.3 1155260 1154012 pts/8 S+   20:55   0:07 ./cligen_file -f foo

Finally I wouldlike to know if you really want this sequence of options? Is it not just option between these alternatives you need?
--Olof

[ashuagarwal01]

Hi, Thanks for the prompt reply.

Okay, understood.

And yes for my case if a given container has say 50 leaves then all those are optional. Also looking at the expanded tree, it seems they also need to be in order. A user can pass in any number of leaves and very much possibly in any random order.

Regards.

[olofhagsand]

New "sets" feature added, see:
ed1997a
Example: list @{
aa("des");
ab("des");
ac("des");
...
}