Order, Duplicates and Stability

Part II · Module 26 · Chapter 26.4 · Order, Duplicates and Stability

Two engineers generate a filelist from the same tree and get two different files. A diff shows forty changed lines and no changed design. Three separate causes, and only one of them is the one people name.

1. find's Order Is Not Random — It Is Name-Hashed and Stable

The folklore is that unsorted find output is "random" or "depends on creation order". On this filesystem both are wrong, and the truth is more useful.

Three runs of the same command:

$ for i in 1 2 3; do /usr/bin/find rtl -name '*.sv' | md5; done
0a8131e779a0bbee461b50b108be8326
0a8131e779a0bbee461b50b108be8326
0a8131e779a0bbee461b50b108be8326

Identical. So within one machine and one directory the order is stable, and a filelist regenerated twice will not differ.

Is it creation order? Eight files, created in one order and then the same eight names created in the reverse order in a second directory:

$ find /tmp/ot3 -name '*.sv' | sed 's|.*/||' | tr '\n' ' '
fifo.sv chip_top.sv axi_master.sv i2c.sv clk_div.sv dma.sv uart_tx.sv spi.sv
$ find /tmp/ot4 -name '*.sv' | sed 's|.*/||' | tr '\n' ' '
fifo.sv chip_top.sv axi_master.sv i2c.sv clk_div.sv dma.sv uart_tx.sv spi.sv

Identical, despite opposite creation orders. So the order is a function of the names, not of when the files were made — APFS hashes directory entries.

And it is neither alphabetical nor reverse, checked programmatically rather than by eye:

$ a=$(find /tmp/ot3 -name '*.sv' | sed 's|.*/||')
$ [ "$a" = "$(printf '%s\n' "$a" | sort)" ] && echo ALPHABETICAL || echo "not alphabetical"
not alphabetical
$ [ "$a" = "$(printf '%s\n' "$a" | sort -r)" ] && echo REVERSE || echo "not reverse alphabetical"
not reverse alphabetical
$ ls /tmp/ot3 | tr '\n' ' '
axi_master.sv chip_top.sv clk_div.sv dma.sv fifo.sv i2c.sv spi.sv uart_tx.sv

ls sorts; find does not. So ls and find disagree about the same directory, which is why a filelist built with one and checked with the other looks wrong.

2. The Locale Changes the Sorted Order

Sorting is necessary and not sufficient, because sort itself is configuration — Chapter 22.6 §3 measured it and a filelist is where it bites.

$ cat order.f
rtl/Top.sv
rtl/axi.sv
rtl/Bus.sv
$ LC_ALL=C sort order.f
rtl/Bus.sv
rtl/Top.sv
rtl/axi.sv
$ LC_ALL=en_US.UTF-8 sort order.f
rtl/axi.sv
rtl/Bus.sv
rtl/Top.sv

Completely different orders. Under LC_ALL=C the comparison is by byte value, so all uppercase precedes all lowercase; under a UTF-8 locale it is by collation, which interleaves case and ignores it for the primary comparison.

In a design with mixed-case module names — which is most SystemVerilog — two engineers with different locales generate two differently ordered lists from the same tree, and neither of them has done anything wrong.

So every sort in a generator needs its locale pinned:

LC_ALL=C sort

And not just sort. LC_ALL=C belongs on the whole generator, because find's -name patterns and any [a-z] range in a filter are locale-sensitive too — Chapter 22.1 §5 measured case B in [a-z]) answering differently in two locales.

#!/usr/bin/env bash
export LC_ALL=C          # before anything else: ordering and ranges are now byte-wise

One line at the top of a generation script, and the output is the same for everybody.

3. sort -u file > file Destroys the File

The registry's suggestion is correct and the obvious variant is not. Both measured.

The correct form uses sort's own output option, which reads the whole input before writing:

$ printf 'b\na\nb\n' > s.f
$ sort -u s.f -o s.f
$ cat s.f
a
b

In place, deduplicated, three lines to two. And the shell-redirect version:

$ printf 'b\na\nb\n' > s2.f
$ sort -u s2.f > s2.f
$ wc -c < s2.f
       0

Zero bytes. The redirect truncates s2.f before sort opens it, so sort reads an empty file and writes nothing. Chapter 12.2 §4 measured this truncation-before-execution behaviour; here the casualty is the list of files your design is made of.

Three safe forms:

sort -u list.f -o list.f                       # sort's own in-place, measured above
sort -u list.f > tmp && mv tmp list.f          # explicit, portable to any tool
{ rm list.f; sort -u > list.f; } < list.f      # the fd trick: clever, and avoid it

Use the first when the tool is sort — it is specified behaviour, not a trick. Use the second for every other tool, because almost nothing else has -o. The third works because the file is opened before it is removed, and it is the kind of cleverness that fails silently when someone edits it later.

4. Deduplicating Without Destroying the Order

§3's sort -u reorders, which Chapter 26.1 §3 established can break the compile. When the order is load-bearing, deduplication must keep the first occurrence and leave everything else alone:

$ printf 'pkg.sv\naxi.sv\npkg.sv\nuart.sv\naxi.sv\n' | awk '!seen[$0]++'
pkg.sv
axi.sv
uart.sv

awk '!seen[$0]++' — Chapter 25.6 §4's idiom, used there for PATH and here for a filelist. Order preserved, first occurrence kept, duplicates gone. For a filelist that is almost always the right deduplication, because the first occurrence is the one that satisfied the dependency.

Two refinements for real lists:

# keep comments and blank lines, deduplicate only paths and options
awk '/^[[:space:]]*(#|$)/ { print; next } !seen[$0]++'

# report what was removed, rather than removing it silently
awk '/^[[:space:]]*(#|$)/ { print; next }
     seen[$0]++ { printf "# duplicate removed: %s\n", $0 > "/dev/stderr"; next }
     { print }'

The second is worth defaulting to. A duplicate in a filelist is a fact about how the lists are composed, and Chapter 26.6 is about that composition — so a generator that reports duplicates on stderr while emitting a clean list gives you both the working list and the diagnosis.

5. Making a Diff Mean Something

The payoff for all of the above: a filelist diff that shows design changes and nothing else.

That last row is the test, and it is one command:

genlist -o /tmp/new.f rtl tb && cmp -s /tmp/new.f filelists/rtl.f && echo "no change"

If regenerating a committed filelist produces identical bytes, every property above holds. If it does not, one of them is missing, and diff names which. That is Chapter 26.3 §6's golden-file check, and it is also a self-test for this chapter's rules — which is why it is worth running once deliberately rather than only in CI.

6. The Normaliser

#!/usr/bin/env bash
# flnorm — make a filelist canonical: stable order, no duplicates, reported
#
# usage: flnorm [-s] [-q] <filelist>
#   -s  sort the paths (default: preserve order, deduplicate first-wins)
#   -q  do not report duplicates on stderr
# exit: 0 clean · 1 duplicates were removed · 2 unusable
set -o nounset
export LC_ALL=C

dosort=0; quiet=0
while getopts ':sq' o; do
  case $o in
    (s) dosort=1 ;;
    (q) quiet=1 ;;
    (\?) printf 'flnorm: unknown option -%s\n' "$OPTARG" >&2; exit 2 ;;
  esac
done
shift $(( OPTIND - 1 ))
[ $# -eq 1 ] || { printf 'usage: flnorm [-s] [-q] <filelist>\n' >&2; exit 2; }
[ -r "$1" ] || { printf 'flnorm: cannot read %s\n' "$1" >&2; exit 2; }

dups=0
emit() {
  awk -v quiet="$quiet" '
    /^[[:space:]]*(#|$)/ { print; next }
    seen[$0]++ {
      if (!quiet) printf "flnorm: duplicate removed: %s\n", $0 > "/dev/stderr"
      d++
      next
    }
    { print }
    END { if (d > 0) exit 1 }
  ' "$1"
}

if [ "$dosort" -eq 1 ]; then
  # options and comments first, in order; then the paths, sorted
  grep -E '^[[:space:]]*(#|-|\+)' -- "$1" || true
  grep -vE '^[[:space:]]*(#|$|-|\+)' -- "$1" | sort -u
else
  emit "$1" || dups=1
fi

[ "$dups" -eq 0 ]

$ cat dup.f
# the design
+incdir+rtl/include
rtl/core/chip_top.sv
rtl/axi/axi_master.sv
rtl/core/chip_top.sv
$ flnorm dup.f
# the design
+incdir+rtl/include
rtl/core/chip_top.sv
rtl/axi/axi_master.sv
flnorm: duplicate removed: rtl/core/chip_top.sv
$ echo $?
1
$ flnorm -q dup.f > /dev/null; echo $?
1
$ flnorm -s dup.f
# the design
+incdir+rtl/include
rtl/axi/axi_master.sv
rtl/core/chip_top.sv

Eight decisions:

export LC_ALL=C on the second line, before any comparison happens — §2's rule, applied to the tool that does the comparing.

Order-preserving is the default and -s is opt-in, because Chapter 26.1 §3 measured that sorting can break a compile. A normaliser whose default could stop a design compiling would be the wrong default.

Duplicates exit 1 and are reported on stderr while the clean list goes to stdout. That separation is what makes it usable in a pipeline and as a check: flnorm list.f > new.f works, and flnorm list.f > /dev/null || echo "had duplicates" works.

The -s branch keeps options and comments in their original order and sorts only the paths, because sorting +incdir+ lines among paths would scatter the configuration Chapter 26.2 §4 argued for keeping at the top.

awk reports to /dev/stderr rather than the shell doing it, so the duplicate is named at the point it is found rather than collected and printed afterwards.

END { if (d > 0) exit 1 } — and the status is set only in END, for the reason Chapter 25.4 measured: an exit in the body would run END anyway, and END's status would replace it.

|| true after the first grep, because a filelist with no options or comments makes grep exit 1 and would otherwise abort the branch.

And one inconsistency this script has, disclosed rather than hidden: the -s branch deduplicates with sort -u, which neither reports nor counts, so it exits 0 on a list that had duplicates:

$ flnorm /tmp/dup.f > /dev/null; echo $?
1
$ flnorm -s /tmp/dup.f > /dev/null; echo $?
0

Same input, same duplicate removed, two different statuses. That is a defect in a tool meant to be usable as a check, and the fix is to count in the -s branch too:

before=$(grep -cvE '^[[:space:]]*(#|$|-|\+)' -- "$1")
after=$(grep -vE '^[[:space:]]*(#|$|-|\+)' -- "$1" | sort -u | grep -c .)
[ "$before" -eq "$after" ] || dups=1

It is left in the version above as written, with this note, because the inconsistency is more instructive than the fix: two code paths that look equivalent and differ in their contract is the commonest way a script's exit status stops meaning anything. Chapter 21.4's contract has to hold on every path, and the only way to know it does is to exercise each one — which is how this was found.

Practice

1. Run find on a directory three times and compare the digests. Stable?
2. Create the same eight file names in two directories in opposite orders. Do the two find outputs match?
3. Check programmatically whether your find order is alphabetical or reverse. Is it either?
4. Compare ls and find on one directory. Where do they disagree?
5. Sort a mixed-case filelist under LC_ALL=C and under a UTF-8 locale. How many lines move?
6. Run sort -u list.f > list.f on a copy and check the byte count.
7. Then run sort -u list.f -o list.f and confirm it works.
8. Find the uniq -d duplicates in a real filelist. Any?
9. Write three spellings of one path into a list and confirm sort -u keeps all three.
10. Write the normaliser from §3's callout and confirm it collapses them to one.
11. Deduplicate an order-sensitive list with awk '!seen[$0]++' and confirm the first occurrence survives.
12. Write flnorm. Run it on a list with duplicates and confirm exit 1 with the clean list on stdout.
13. Run flnorm -s on a list with options and confirm the options stay at the top.
14. Regenerate a committed filelist and cmp it against the committed copy. Identical bytes?

Check Your Understanding

1. Is find's unsorted order random, creation-ordered, or something else?
2. What did two directories with opposite creation orders demonstrate?
3. Given that the order is stable, why must you still sort?
4. How do ls and find differ on one directory?
5. What did LC_ALL=C versus a UTF-8 locale do to a mixed-case filelist?
6. Why does LC_ALL=C belong on the whole generator rather than just the sort?
7. What does sort -u list.f > list.f leave you with, and why?
8. Name three safe in-place forms and say when each is right.
9. What does sort | uniq -c tell you that sort -u does not?
10. Why does sort -u fail to deduplicate three spellings of one path?
11. When must deduplication preserve order, and what is the idiom?
12. Why is order-preserving the default in flnorm?
13. Why is the exit status set only in awk's END block?

7. Remember

• find's order is stable and name-hashed, not random and not creation-ordered. Measured: identical digests across runs, and identical order in two directories built in opposite orders.
• ls sorts; find does not. They disagree on the same directory.
• Sort anyway: the hash is per-filesystem, one added file can move others, and an arbitrary order cannot encode dependencies.
• LC_ALL=C changes the sorted order of a mixed-case list completely. Pin it on the whole generator, not just the sort.
• sort -u f > f leaves a zero-byte file — the shell truncates before sort opens it.
• sort -u f -o f works in place; sort -u f > tmp && mv tmp f is the general form.
• sort -u discards duplicates; uniq -c counts them, and the count tells you two lists overlap.
• sort -u cannot see that three path spellings are one file. Normalise with cd … && pwd -P first, and know it costs two subshells per line.
• When order matters, deduplicate with awk '!seen[$0]++' — first occurrence wins.
• Report duplicates on stderr and emit the clean list on stdout, so one tool serves as a filter and a check.
• Set an awk exit status only in END.
• Every code path must honour the documented status. Measured: flnorm and flnorm -s returned 1 and 0 for the same duplicate, because one path counted and the other did not.
• The test for all of it: regenerate and cmp. Identical bytes means every rule above holds.

8. What Is Next

Chapter 26.5 checks the list before the tool sees it — every path present, every variable resolved — so that a four-hundred-line compile error becomes one line naming the file that is not there.