Re: getopt_long permutation algorithm questions

[Jens Gustedt <jens.gustedt@inria.fr>]

[-- Attachment #1: Type: text/plain, Size: 3387 bytes --]

Am Mittwoch, den 03.12.2014, 14:56 -0500 schrieb Rich Felker:
> On Wed, Dec 03, 2014 at 08:43:09PM +0100, Jens Gustedt wrote:
> > sounds all a bit complicated and fragile to me.  getopt should neither
> > be performance nor memory critical, so there is not much need for
> > optimization here, no?
> > 
> > Why don't you just keep track of the cases in an array on the stack,
> > and then do all the moves after the processing in a second scan? You
> > have argc, so you know the size of a VLA (`char[argc]` should suffice)
> > that you would have to define.
> 
> I'm not trying to optimize anything for performance here, just get it
> correct and simple. I don't quite understand what you're proposing,

so I have to explain better

> but doing a multi-pass,

actually two-pass

> out-of-place operation does not sound simple,

but in place

> and it's not robust since the kernel allows huge argument lists
> whereby char[argc] would overflow the stack (and even if it didn't,
> assuming that it doesn't allow them would be an unwarranted assumption
> unless it actually bought us some simplicity, which I don't see).

My idea was just to do a first pass for the "real" argument processing
and to note during that pass if an argument wasn't used. Then in a
second pass reorder argv with that information.

For the storage of that information, this is one bit per argc, and if
we waste one byte for it to have life simple, then `char[argc]` should
suffice. argc can be greater than several K ?

But thinking of it:

> > Am Mittwoch, den 03.12.2014, 14:29 -0500 schrieb Rich Felker:
> > > As part of resolving the rest of the dist-local changes Alpine is
> > > applying to musl, I'm trying to figure out how to add GNU-style
> > > argument permutation to getopt_long. The basic concept is simple: when
> > > a non-option argument is encountered, skip forward until the next
> > > option (argument beginning with '-') and move it (and possibly its
> > > argument) before the non-option arguments. However, there are some
> > > ugly corner cases like:
> > > 
> > > arg1 -ab foo arg2
> > > 
> > > where 'a' and 'b' are options, and 'b' takes an argument, foo. Here it
> > > seems like, in order to perform the correct permutation, lookahead is
> > > required to see that foo also needs to be moved. Is this correct?

I wouldn't call it "lookahead".

Why don't you

 - have k as the position where the next option argument should be
   placed and p as the next position that has not been processed yet
 - move p such that argv[p] is the next option argument
 - process argv[p] in place, including an eventual argument
   argv[p+1] that a long option or the last option character takes
 - shuffle the found argv[p] (plus eventually argv[p+1]) to the
   correct position argv[k] (and argv[k+1])
 - increment k and p by 1 (or 2)
 - iterate

The disadvantage of that general approach is that it can be
quadratic. For very long argument lists, if you have argc more than
several K, this could be prohibitive.

Jens

-- 
:: INRIA Nancy Grand Est ::: AlGorille ::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536   ::
:: :::::::::::::::::::::: gsm France : +33 651400183   ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::




[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 198 bytes --]