problematic recursion in optparse() and optparse_long()

[E5ten]

The use of recursion in these functions (particularly in the way it is used, which prevents tail-call optimization), leads to increasing stack usage for every non-option argument, and eventually stack overflow. The recursion should probably be removed to avoid this (setting a variable within the functions to indicate that the function has restarted, along with a goto to the beginning and some other refactoring, might be a solution).

[skeeto]

Good catch! I'd like to fix this issue, and to help with that I just pushed a test suite (f0c65c9) so that the parser can be changed with confidence. (Or I can accept a patch with confidence.) I would have fixed it at the same time, but it seems it's going to take longer than have time to commit at the moment. It needs to track the first non-option index, continuing hunting for the next option (without recursing), then permute the option backwards (potentially two elements) to that first non-option index. The current code, and my description above, are also quadratic time. I don't think that can be improved without allocating. Idea: Add a "scratch" pointer where the caller can optionally supply a scratch argv that is at least the same size as the input argv. If present, it will use the scratch space to permute in linear time instead of quadratic. When it sees a non-option, push its pointer onto the scratch buffer.

[youpong]

Could you assign me this issue?

[brdjns]

Hi, any updates on this?

[skeeto]

I haven't looked into it further in the past 4 years. As I realized back then, addressing it would require either allocating or a change in the interface. I favor the latter, but I also don't think it's that important. I see a couple reasonable possibilities:

1. Replace permute with an optional pointer to an output argv in which to accumulate positional argument. If null, do not permute.

2. Add a function like optparse_arg that iterates over just positional arguments. It essentially re-parses the command line in a second pass, and so needs the option listings again.

In either case the original argv isn't mutated. Since I last looked at this I've adopted arena allocation, and now I just arena-allocate whatever is necessary in a bespoke option parser. This would fit quite well with an interface like (1) in Optparse, so I strongly favor it.

So I just whipped that up in f4cf784. Permutes in linear time, without mutating argv, and without recursion (what was I thinking?!). Since I'm breaking things, I might overhaul even more. I originally wrote this over a decade ago, and this all seems like baby stuff now.

[N-R-K]

Since I last looked at this I've adopted arena allocation, and now I just arena-allocate whatever is necessary in a bespoke option parser. This would fit quite well with an interface like (1) in Optparse, so I strongly favor it.

While I agree with the points, it's probably also worth noting that most projects that are using optparse are likely not using arena allocation or the like.

In my case, I'm using optparse in nsxiv, a fairly old project which uses the traditional C memory management with malloc and friends. In this case, adding an allocation just to do permutation would be slightly inconvenient. Having the option to do the permutation in place would be ideal.

The other interface change of having optparse_init() return the struct seems fine. No complaint with that.