Details

Reviewers

rpokala
lwhsu
pstef
imp
pauamma_gundo.com
gbe
kib

Group Reviewers

manpages

Commits

rG05c9a0158f68: libc: Add strverscmp(3) and versionsort(3)

Summary

Add a strverscmp(3) function to libc, a GNU extension I implemented by reading its glibc manual page.
It orders strings following a much more natural ordering (e.g. "ent1 < ent2 < ent10" as opposed to "ent1 < ent10 < ent2" with strcmp(3)'s lexicographic ordering).

Also add versionsort(3) for use as scandir(3)'s compar argument.

Update manual page for scandir(3) and add one for strverscmp(3).

Add tests for strverscmp(3).

Original diff: D35783

Test Plan

Tests pass on my side.

Diff Detail

Repository

rS FreeBSD src repository - subversion

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 46457
Build 43346: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

pauamma_gundo.com requested changes to this revision.Jul 15 2022, 7:52 AM

pauamma_gundo.com added inline comments.

lib/libc/gen/scandir.3
96–97	"naturally" doesn't explain anything to me.
lib/libc/string/strverscmp.3
39
42	No contractions.
lib/libc/string/strverscmp.c
27	Does the original use isdigit or isnumber?

This revision now requires changes to proceed.Jul 15 2022, 7:52 AM

obiwac added inline comments.Jul 15 2022, 11:20 AM

lib/libc/gen/scandir.3
96–97	Indeed "naturally" isn't very descriptive. I'm not sure I understand in a combined numeric (for base-10 digit sequences) and text (for other characters) using strverscmp(3) though.
lib/libc/string/strverscmp.3
42	Alright
lib/libc/string/strverscmp.c
27	It uses `isdigit`. `strverscmp` is analog to `strcmp` and not `strcoll`, so it wouldn't make much sense to use `isnumber` I believe.

pstef added inline comments.Jul 15 2022, 4:21 PM

lib/libc/gen/scandir.3
96–97	But "natural sort order" is an established term!

Remove contraction in manual page

Harbormaster completed remote builds in B46451: Diff 108209.Jul 15 2022, 8:39 PM

pauamma_gundo.com added inline comments.Jul 16 2022, 3:32 AM

lib/libc/gen/scandir.3
96–97	If it is, I never got the memo.
96–97	I was trying to convey in a single sentence that fragments made of digits are sorted numerically (with the extra wrinkle for those starting with 0) and fragments made of text without digits are sorted as strings, with the earliest differing fragment pair determining the overall order. And I just thought of something; given 2 strings foo123456 and foobar789, are the first fragment pairs compared: "foo" and "foobar" (string comparison), with 123456 and 789 never compared or "foo123" and "foobar" (string comparison), with 456 and 789 never compared? This may matter depending on the relative ordering of letters and digits, eg EBCDIC or for future-proofing if this is changed in 10 years to accept all Unicode digits.

pstef added inline comments.Jul 16 2022, 7:30 AM

lib/libc/string/strverscmp.c
24	Style: test non-booleans against values. In this case: `*u1 != '\0' etc.`
78	If I'm not missing something, there is a possible optimization here: digit_count_1 is always equal to `u1 - num_1`, so there should be no need for the variable and the instruction to increment it. Same applies to digit_count_2.

pstef accepted this revision.Jul 16 2022, 7:30 AM

obiwac added inline comments.Jul 16 2022, 1:39 PM

lib/libc/gen/scandir.3
96–97	And I just thought of something; given 2 strings foo123456 and foobar789, are the first fragment pairs compared Both strings are compared byte-by-byte, so it would go up to "foo1" and "foob" before returning. This may matter depending on the relative ordering of letters and digits, eg EBCDIC or for future-proofing if this is changed in 10 years to accept all Unicode digits. Again, `strverscmp` is analog to `strcmp`, not `strcoll`, so I don't think that matters.
lib/libc/string/strverscmp.c
24	Got it
78	You're not missing anything. Although I agree it's more readable without the extra variables, looking at the output of both GCC & Clang, the unnecessary increment is optimized away anyway. Modern compilers are wonderful aren't they 😄 This also applies to `zero_count_#`; I'll change that shortly.

Simplify digit counting code & style

Harbormaster completed remote builds in B46457: Diff 108232.Jul 16 2022, 4:59 PM

I accept this revision. I don't mind declarations after statements, but others might.

Hey guys, is there anything here that I still need to do?

In D35807#815011, @obiwac_gmail.com wrote:

Hey guys, is there anything here that I still need to do?

My remaining 2 concerns/questions;

https://reviews.freebsd.org/D35807#inline-220489
https://reviews.freebsd.org/D35807#inline-220575 (first sentence)

In D35807#815011, @obiwac_gmail.com wrote:

Hey guys, is there anything here that I still need to do?

No, it just needs someone with a commit bit to do the commit. I've been busy recently.

In D35807#816089, @pauamma wrote:

My remaining 2 concerns/questions;

https://reviews.freebsd.org/D35807#inline-220489

https://reviews.freebsd.org/D35807#inline-220575 (first sentence)

IMHO, at that point, the user should just read the strverscmp(3) manpage.
Explaining what strverscmp(3) does in scandir(3) in a precise manner would clutter things up and give quite a bit of redundant information I feel.
And since "natural sort order" is indeed an established term as @pstef mentioned, I personally think it's better as it currently is.

In D35807#816151, @pstef wrote:

No, it just needs someone with a commit bit to do the commit. I've been busy recently.

Okay, sorry, no pressure. It's my first time using Phabricator - was just wondering if I had missed something!

LGTM for the man page changes.

In D35807#815011, @obiwac_gmail.com wrote:

Hey guys, is there anything here that I still need to do?

While @pstef is busy, I suggest you can have a post on -hackers mailing list to call for more reviews and tests.

In D35807#815011, @obiwac_gmail.com wrote:

Hey guys, is there anything here that I still need to do?

Sorry for the delay. In the meantime style(9) was clarified to forbid declarations following statements, the rule that this patch breaks.
Also the commit message should be in the imperative form: "add", "update" instead of "adds", "updates".
I can fix both of those - or do you want to do it yourself and update this review?

In D35807#823356, @pstef wrote:

I can fix both of those - or do you want to do it yourself and update this review?

I can do it myself this evening, if that doesn't slow you down for anything else. (Aswell as making that post on -hackers that @lwhsu mentioned, if that's still necessary.)

In D35807#823358, @obiwac_gmail.com wrote:

I can do it myself this evening, if that doesn't slow you down for anything else. (Aswell as making that post on -hackers that @lwhsu mentioned, if that's still necessary.)

Please go ahead.
As for the post on -hackers, I don't think it ever was necessary, but it's not a bad idea either.

strverscmp: Respect new rules in style(9)

Harbormaster completed remote builds in B47023: Diff 109563.Aug 19 2022, 8:02 PM

obiwac edited the summary of this revision. (Show Details)Aug 19 2022, 8:05 PM

In D35807#823359, @pstef wrote:

Please go ahead.

Done :) (All should be okay, but I still need to check if everything compiles 100%.)

Writing post on -hackers...

strverscmp: Respect new rules in style(9)

Harbormaster completed remote builds in B47025: Diff 109565.Aug 19 2022, 8:23 PM

emaste added a subscriber: emaste.Aug 20 2022, 3:55 PM

kib added a subscriber: kib.Aug 20 2022, 11:50 PM

kib added inline comments.

lib/libc/gen/scandir.c
157	`return (...);`
lib/libc/string/strverscmp.c
15	Extra blank line
17	Extra blank line
17	Extra blank line
18	No space needed after `)`. But there must be a space between void and *. Why not use __DECONST() instead of explicit void cast?
22	s1 == s2 is not aliasing, it is identity
25	Extra blank line
27	`return (0);`
48	This is a block comment which scope, as I see, extends to the end of u2 loop. Therefore, there is no need for a blank lines 51 and 54.
77	Extra blank line, same comment as above.
83	';' should be on the new line, indented
96	Extra blank line

I'll make those changes a little later, thank you :)

lib/libc/string/strverscmp.c
18	The void cast is simply to cast to `unsigned char` without having to explicitly type out the type name. I'm not sure I see why `__DECONST` is apt here?

Integrate styling comments from @kib

Harbormaster completed remote builds in B47035: Diff 109619.Aug 21 2022, 12:03 PM

Integrate styling comments from @kib

Harbormaster completed remote builds in B47036: Diff 109620.Aug 21 2022, 12:05 PM

Where can I find the rules for vertical spacing? I can't find it explicitly in style(9)

In D35807#823735, @obiwac_gmail.com wrote:

Where can I find the rules for vertical spacing? I can't find it explicitly in style(9)

Do you mean indentation? style(9) says "Indentation is an 8 character tab. Second level indents are four spaces." and where the rule isn't stated explicitly, it is shown by example.

In D35807#823736, @pstef wrote:

Do you mean indentation?

Nah I meant vertical spacing as in where I may or may not add blank lines, as @kib was talking about, but thank you :)

In D35807#823737, @obiwac_gmail.com wrote:

In D35807#823736, @pstef wrote:

Do you mean indentation?

Nah I meant vertical spacing as in where I may or may not add blank lines, as @kib was talking about, but thank you :)

Yes, it is implicit in examples, and in the existing code.
Not to mention that excess blank lines stole the screen space in editor.

lib/libc/string/strverscmp.c
18	__DECONST is somewhat unfortunate name for the macro. De-facto contract for it is to provide the type cast without triggering any warnings from any possible compiler warning/error flags DECONST/DEVOLATILE/__DEQUALIFY are about the same. We guarantee to maintain them regardless of the insanity level compiler authors go for.

Replace casts with __DECONST & remove some blank lines

Harbormaster completed remote builds in B47039: Diff 109624.Aug 21 2022, 4:53 PM

Does spacing like this work for you @kib? Hopefully I'll get the feeling for where blank spaces are/aren't appropriate in FreeBSD code in future patches 😄

kib added inline comments.Aug 23 2022, 1:31 AM

lib/libc/string/strverscmp.c
16	Did you tried to compile this?
lib/libc/tests/string/strverscmp_test.c
72	Indent should be +4 spaces for the continuation line.

I still haven't tried compiling anything yet; I don't have access to a FreeBSD machine for the moment.

Code style

Harbormaster completed remote builds in B47088: Diff 109740.Aug 23 2022, 8:52 PM

Stupid mistake in usage of __DECONST

Harbormaster completed remote builds in B47093: Diff 109745.Aug 23 2022, 9:22 PM

scandir: Add man link from versionsort.3

Harbormaster completed remote builds in B47094: Diff 109746.Aug 23 2022, 9:28 PM

kib accepted this revision.Aug 24 2022, 4:15 AM

Could you please send me the complete patch in the form of git format-patch by mail? With the author set, proper commit message etc. This would expedite the commit.

This revision was not accepted when it landed; it landed in state Needs Review.Aug 25 2022, 12:29 AM

Closed by commit rG05c9a0158f68: libc: Add strverscmp(3) and versionsort(3) (authored by obiwac, committed by kib). · Explain Why

This revision was automatically updated to reflect the committed changes.

kib added a commit: rG05c9a0158f68: libc: Add strverscmp(3) and versionsort(3).

libc: Add `strverscmp(3)` & `versionsort(3)`
ClosedPublic
Actions

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 108232

include/dirent.h

include/string.h

lib/libc/gen/Symbol.map

lib/libc/gen/scandir.3

lib/libc/gen/scandir.c

lib/libc/string/Makefile.inc

lib/libc/string/Symbol.map

lib/libc/string/strverscmp.3

lib/libc/string/strverscmp.c

lib/libc/tests/string/Makefile

lib/libc/tests/string/strverscmp_test.c

libc: Add `strverscmp(3)` & `versionsort(3)`ClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 108232

include/dirent.h

include/string.h

lib/libc/gen/Symbol.map

lib/libc/gen/scandir.3

lib/libc/gen/scandir.c

lib/libc/string/Makefile.inc

lib/libc/string/Symbol.map

lib/libc/string/strverscmp.3

lib/libc/string/strverscmp.c

lib/libc/tests/string/Makefile

lib/libc/tests/string/strverscmp_test.c

libc: Add `strverscmp(3)` & `versionsort(3)`
ClosedPublic
Actions

Revision Contents
Changeset List