[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20121206010000.GO20323@brightrain.aerifal.cx>
Date: Wed, 5 Dec 2012 20:00:00 -0500
From: Rich Felker <dalias@...ifal.cx>
To: musl@...ts.openwall.com
Subject: Re: Fix strverscmp
On Wed, Dec 05, 2012 at 04:43:29PM -0800, Isaac Dunham wrote:
> On Wed, 5 Dec 2012 14:35:21 -0500
> Rich Felker <dalias@...ifal.cx> wrote:
>
> > I'm not opposed to adding this, but the code has some bugs, most
> > notably integer overflow. On filenames consisting of long digit
> > strings, it will invoke undefined behavior. If the results are
> > unpredictable, it might even cause qsort to invoke very bad undefined
> > behavior.
> The first I can see now (overflow -> l[-n]),
> but I'm not understanding the second.
>
> > It would also, for example, cause these two names to compare equal:
> >
> > - foobar-1.1.2
> > - foobar-1.01.3
> >
> > just because the first component that differs textually compares equal
> > numerically.
>
> This should not be equal, but not for the reason I'd expected: a
> leading 0 is supposed to be interpreted as "0.0". Decimal points are
> not factored in...
My understanding of the code is that, after it hits the first place
where the strings differ, it switches to reading a digit string as a
decimal number, and the result is the difference of those decimal
numbers. I just used the decimal point as an example because it
terminates the loop.
I also don't understand what you mean about leading zero. If leading
zeros are not considered equal to the number without leading zeros,
then a simple algorithm would be to, on the first mismatching byte,
remember the difference, then count the number of consecutive digits
starting at that position in both strings. If this count is the same
(possibly zero) for both strings, return the saved byte difference. If
the count is different, consider the string with fewer digits to be
less than the one with more digits. This is trivial to implement with
no arithmetic, but I'm not sure it matches the original semantics.
>
> >
> > It also shares the same issues (which we should arguably duplicate
> > anyway) with the original strverscmp, that names consisting of hex
> > values get sorted in a ridiculous and harmful way.
>
> Per the specification, hex is unsupported. It would be possible to
> support it, but it may be rather expensive in terms of size...
I don't think we really want to "support" hex versions. My frustration
with the strverscmp interface is that it butchers the ordering of
directories containing hex filenames, and Thunar (xfce file manager)
insists on using it with no option to turn it off.
My thought for a possible solution to the problem would be only
interpreting decimal numbers where the number is delimited by
non-alphanumeric characters, and otherwise doing pure byte comparison
on digits. This would avoid lots of spurious misorderings. But I would
like to hear some opinions on whether it's harmful to differ from
glibc's behavior here...
> The attached is an attempt to figure out how it should work (more
> notes than final implementation).
I'll take a look.
> It seems to get the right sign consistently, which is all that the
> manpage indicates can be counted on.
Yes, only the sign matters.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
