Deduplicating With a Hash

Part II · Module 19 · Chapter 19.3 · Deduplicating With a Hash

1. Three Strategies, One Tree

The generator is given three roots: rtl, rtl/core and tb. The second is inside the first, which is the ordinary way this happens — somebody needed the core files listed first, added a root, and did not remove the old one. There is also a symlink, counter_alias.sv, pointing at counter.sv.

use strict;
use warnings;
use File::Find;
use Cwd qw(abs_path);

# A symlink is how one file gets a second spelling. Make one here so the
# measurement does not depend on how the tree was copied.
unlink "rtl/core/counter_alias.sv";
symlink "counter.sv", "rtl/core/counter_alias.sv" or die "symlink: $!";

# THREE search roots, and rtl/ already contains rtl/core/.
my @ROOTS = ("rtl", "rtl/core", "tb");

sub walk {
    my @hits;
    find({ no_chdir => 1, wanted => sub {
        my $p = $File::Find::name;
        return unless -f $p && $p =~ /\.sv$/;
        return if $p =~ m{(^|/)generated/};
        return if (split m{/}, $p)[-1] =~ /^\./;
        push @hits, $p;
    }}, @ROOTS);
    return @hits;
}
sub pkgs_first { my @l = @_; return ((grep { /_pkg\.sv$/ } @l), (grep { !/_pkg\.sv$/ } @l)) }
sub build {
    my ($tag, @list) = @_;
    open my $o, ">", "d_$tag.f" or die $!;
    print $o "$_\n" for pkgs_first(@list);
    close $o;
    my $log = `iverilog -g2012 -I rtl/include -o /dev/null -c d_$tag.f 2>&1`;
    my $rc  = $? >> 8;
    my ($first) = grep { /\S/ } split /\n/, ($log // "");
    return ($rc, $rc == 0 ? "compiles" : ($first // "failed"));
}

my @raw = walk();
printf "roots walked: %s\n", join(", ", @ROOTS);
printf "paths collected before any deduplication: %d\n\n", scalar @raw;

my @a = sort @raw;                                       # A: none
my %seen_b;
my @b = sort grep { !$seen_b{$_}++ } @raw;               # B: key on the string
my (%seen_c, @c);                                        # C: key on the resolved path
for my $p (@raw) { my $r = abs_path($p); next if $seen_c{$r}++; push @c, $p }
@c = sort @c;

printf "%-38s %s\n", "STRATEGY", "ENTRIES";
printf "%-38s %d\n", "A  no deduplication",            scalar @a;
printf "%-38s %d\n", "B  hash on the path string",     scalar @b;
printf "%-38s %d\n", "C  hash on abs_path (resolved)", scalar @c;

print "\nwhat B still contains that C does not:\n";
my %printed;
for my $p (@b) {
    my $r = abs_path($p);
    printf "  %-28s (a second spelling of one file)\n", $p if $printed{$r}++;
}

print "\nthe two spellings resolve to the same file?\n";
my $one = abs_path("rtl/core/counter.sv");
my $two = abs_path("rtl/core/counter_alias.sv");
printf "  counter.sv       -> ...%s\n", ($one =~ m{(/rtl/.*)$} ? $1 : "?");
printf "  counter_alias.sv -> ...%s\n", ($two =~ m{(/rtl/.*)$} ? $1 : "?");
printf "  same?  %s\n", ($one eq $two ? "YES" : "no");

print "\nhand each list to the compiler (packages first):\n";
for my $r (["A", \@a], ["B", \@b], ["C", \@c]) {
    my ($tag, $list) = @$r;
    my ($rc, $msg) = build($tag, @$list);
    printf "  %s  rc=%-3s %s\n", $tag, $rc, $msg;
}

# ---- D: two DIFFERENT files declaring the SAME module.
# A path-keyed set cannot see this: the paths really are different.
open my $v2, ">", "rtl/core/counter_v2.sv" or die $!;
print $v2 "module counter (input logic clk, input logic rst_n,\n",
          "                output logic [7:0] count);\n",
          "  always_ff @(posedge clk) count <= count + 8'd1;\n",
          "endmodule\n";
close $v2;

my (%seen_d, @d);
for my $p (@c, "rtl/core/counter_v2.sv") {
    my $r = abs_path($p);
    next if $seen_d{$r}++;
    push @d, $p;
}

print "\nadd a DIFFERENT file declaring the SAME module (counter_v2.sv):\n";
printf "  resolved-path dedup keeps both?       %s (%d entries)\n",
    (@d == @c + 1 ? "YES -- the paths differ" : "no"), scalar @d;

my %by_module;
for my $p (@d) {
    open my $fh, "<", $p or next;
    while (my $l = <$fh>) { push @{ $by_module{$1} }, $p if $l =~ /^\s*module\s+(\w+)/ }
    close $fh;
}
my @clash = grep { @{ $by_module{$_} } > 1 } sort keys %by_module;
printf "  a MODULE-NAME index finds the clash?  %s\n",
    (@clash ? join(", ", map { "YES: $_ declared in " . scalar(@{ $by_module{$_} }) . " files" } @clash)
            : "no");
my ($rcd, $msgd) = build("D", @d);
printf "  compiler: rc=%-3s %s\n", $rcd, $msgd;

unlink "rtl/core/counter_alias.sv", "rtl/core/counter_v2.sv";

roots walked: rtl, rtl/core, tb
paths collected before any deduplication: 11

STRATEGY                               ENTRIES
A  no deduplication                    11
B  hash on the path string             6
C  hash on abs_path (resolved)         5

what B still contains that C does not:
  rtl/core/counter_alias.sv    (a second spelling of one file)

the two spellings resolve to the same file?
  counter.sv       -> .../rtl/core/counter.sv
  counter_alias.sv -> .../rtl/core/counter.sv
  same?  YES

hand each list to the compiler (packages first):
  A  rc=2   rtl/core/chip_pkg.sv:1: syntax error
  B  rc=2   rtl/core/counter_alias.sv:2: error: 'counter' has already been declared in this scope.
  C  rc=0   compiles

add a DIFFERENT file declaring the SAME module (counter_v2.sv):
  resolved-path dedup keeps both?       YES -- the paths differ (6 entries)
  a MODULE-NAME index finds the clash?  YES: counter declared in 2 files
  compiler: rc=2   rtl/core/counter_v2.sv:1: error: 'counter' has already been declared in this scope.

Eleven paths for five files. Then 6, then 5 — and the compiler rejects everything except the last one.

2. The Hash As A Set

The idiom is one line, and it is Chapter 6.9's:

my %seen;
my @unique = grep { !$seen{$_}++ } @paths;

It reads oddly the first time. $seen{$_}++ returns the value before incrementing, so the first time a path is seen it returns 0 — false — and ! makes it true, so the path is kept. Every later time it returns a non-zero count, and the path is dropped. One hash, one pass, order preserved.

Three things worth knowing about it:

It preserves first-seen order, unlike keys %seen, whose order changes between runs (Chapter 6.6 measured that). For a filelist this matters: the order is meaningful (Chapter 19.5), and a dedup step that scrambles it has broken something else to fix this.

$seen{$_}++ autovivifies, so there is no need to test exists first. Chapter 6.4's distinction still applies if you want to ask without creating — but here creating is the point.

The counts are a by-product worth keeping. After the grep, %seen holds how many times each path appeared, so reporting the duplicates costs nothing:

for my $p (sort keys %seen) {
    printf "note: %s appeared %d times\n", $p, $seen{$p} if $seen{$p} > 1;
}

A generator that silently removes duplicates is fine. A generator that removes them and says it did tells the next person their root list has a redundant entry, which is the actual bug.

3. What "The Same File" Means

Here is where the obvious implementation stops working.

String-keyed deduplication took 11 entries to 6. The five real sources plus one: rtl/core/counter_alias.sv, which is a symlink to counter.sv. Two spellings of one file are two different strings, so a set keyed on the string cannot see that they are the same.

The fix is to key on the resolved path:

my (%seen, @unique);
for my $p (@paths) {
    my $real = abs_path($p);
    next if $seen{$real}++;
    push @unique, $p;          # keep the ORIGINAL spelling, key on the resolved one
}

Note the asymmetry in that loop: it keys on the resolved path but keeps the original. That is usually what you want — the filelist stays readable and relative to the tree people recognise, while the uniqueness test uses the real identity of the file.

abs_path collapses three things at once, and each of them occurs in real trees:

Symlinks — a release view, a current/ pointer, a shared IP directory linked into several projects.

. and .. segments — rtl/core/../core/counter.sv is the same file, and paths like that come out of naive joins.

Repeated slashes and trailing slashes — the residue of string concatenation.

4. Path Identity Is Not Module Identity

The resolved-path set is correct about files. It is silent about a different problem, and the last block of the measurement is that problem.

Add counter_v2.sv — a different file that declares module counter. Someone's work-in-progress copy, a variant kept for comparison, a vendor wrapper with a colliding name. Resolved-path deduplication keeps both entries, and it is right to: the paths differ, the files differ, neither is a second spelling of the other.

The compiler rejects it anyway, because what must be unique in a design is not the path but the module name.

An index by declared name finds it, and the measurement shows it does:

my %by_module;
for my $p (@files) {
    open my $fh, "<", $p or next;
    while (my $l = <$fh>) {
        push @{ $by_module{$1} }, $p if $l =~ /^\s*module\s+(\w+)/;
    }
}
my @clash = grep { @{ $by_module{$_} } > 1 } sort keys %by_module;

counter declared in 2 files, reported before the tool runs, naming both paths and the module.

Two honest limitations of that scan, because it is a pattern over source and Chapter 18.11 was about exactly this:

The anchor ^\s*module\s+ is deliberately narrow. It misses a module keyword that is not the first thing on its line, and it would match one inside a block comment. For a filelist pre-check that trade is right — a false clash is a loud, quickly-dismissed message, while a missed clash is the compile error you were trying to avoid.

It cannot tell you which copy is wanted. It can only tell you that two files claim one name, which is the fact a human needs. Resolving it is a decision about the design, not about the filelist.

5. The Asymmetry Nobody Expects

The compiler verdicts in the measurement are worth reading closely, because the two duplicates fail differently.

A duplicate module — list B, where the symlink survived — gives:

counter_alias.sv:2: error: 'counter' has already been declared in this scope.

It names the offending declaration and, as Chapter 19.1 measured, the other path too. That is an actionable message.

A duplicate package — list A, where the overlapping roots listed chip_pkg.sv twice — gives:

rtl/core/chip_pkg.sv:1: syntax error
I give up.

Line 1 of a file that is perfectly correct, no name, no second path, and then the compiler stops. Measured on its own with nothing but that file listed twice, the result is the same.

So the worse message belongs to the case you are more likely to hit. Package files live in shared directories — rtl/core, common/, a verification library — which are exactly the directories that end up in two search roots. The module duplicate tells you what happened; the package duplicate tells you that line 1 of a working file is a syntax error.

This is the same shape as Chapter 19.1's anchor finding. The compiler's message is not a reliable guide back to the cause, so the generator has to make the problem impossible rather than diagnosable.

6. What To Remember

• Overlapping search roots are normal, not a mistake someone made once — rtl and rtl/core both appear because each was added for a reason.
• Measured: 3 roots collected 11 paths for 5 files.
• The hash-as-set idiom is grep { !$seen{$_}++ } (6.9) — one hash, one pass, first-seen order preserved.
• $seen{$_}++ returns the value before incrementing, which is why the ! works.
• Preserving order matters here because filelist order is meaningful (19.5); keys %seen would scramble it (6.6).
• Keep the counts and report them — a redundant root entry is the real bug, and %seen already holds the evidence.
• Measured: string-keyed deduplication got 11 → 6 and stopped. The symlink survived.
• Two spellings of one file are two different strings. Key on abs_path, not on the path.
• Key on the resolved path, keep the original spelling — readable filelist, correct uniqueness test.
• abs_path collapses symlinks, ./.. segments, and slash residue — all three occur in real trees.
• abs_path returns undef for a missing path, and undef as a hash key becomes "" — so every bad path collapses into one entry and the evidence is lost. Guard it and keep the path for validation (19.7).
• Measured: resolved-key deduplication gave 5, and only that list compiled.
• The compiler's duplicate messages are asymmetric. A duplicate module names both paths; a duplicate package says syntax error on line 1 and I give up.
• The worse message belongs to the likelier case — packages live in the shared directories that end up in two roots.
• Measured: a different file declaring the same module survives resolved-path dedup — correctly, since the paths really do differ.
• What must be unique in a design is the module name, not the path.
• Three kinds of duplicate, three tests: the path string, abs_path, and an index of declared module names.
• An index by declared name reports the clash before the tool runs, naming the module and both files.
• A ^\s*module\s+ scan is deliberately narrow — a false clash is cheap, a missed one is the error you were avoiding (18.11).
• Order of operations: walk → filter → deduplicate → order → validate → emit. Deduplicating after ordering produces the confusing failure.

Chapter 19.4 turns to the second thing a filelist carries. The include directories are not a fixed list to hardcode — they are derivable from the files themselves, and deriving them is how you stop a header moving and breaking a build nobody connected to the move.