hashify::tiny_set! causes build to be not reproducible

[nmeum]

I was debugging a reproducible build failure in pimsync [1] [2]. pimsync uses hashify indirectly through mail-parser, which then uses hashify.

In this context, reproducible build means that the compiler output is deterministic. Hence, if I run the build twice I get the same binary. This is important for verifying binaries provided, for example, by Linux distributions. For more information refer to the reproducible builds website: https://reproducible-builds.org/.

Problem

The underlying problem is hashify::tiny_set!, which is a proc_macro that is used by mail-parser. Unfortunately, this macro makes the compiler output non-deterministic as it iterates over a HashMap. The Rust standard library documentation clearly states that HashMap iteration occurs in ”arbitrary order”. Therefore, the compiler output is non-deterministic.

Reproducing the Problem

Use the following commands:

$ cat src/lib.rs
pub fn is_re_prefix(prefix: &str) -> bool {
    hashify::tiny_set! {prefix.as_bytes(),
        "re",
        "res",
        "sv",
        "antw",
        "ref",
        "aw",
        "απ",
        "השב",
        "vá",
        "r",
        "rif",
        "bls",
        "odp",
        "ynt",
        "atb",
        "رد",
        "回复",
        "转发",
    }
}
$ cargo build --release && mv target target.1
$ cargo build --release && mv target target.2
$ md5sum target.?/release/*.rlib
b1baf6bbdba2e06c5b5cd2fcc0e604d0  target.1/release/librepro.rlib
359d5e96fb9d38c3280a4fe761d9ee12  target.2/release/librepro.rlib

This builds a library with a function using hashify::tiny_set! twice. As we can see in the md5sum output, the resulting .rlib file is not identical, but should be as otherwise its build not reproducible.

For more information refer to the following write-up: https://notes.8pit.net/notes/iqfs.html.

[WhyNotHugo]

Should be feasible to use BTreeMap in the macros instead of HashMap.

I'm just not familiar enough with the codebase to fully understand where the offending usage happens.

[WhyNotHugo]

I think that most usages of HashMap can be replaced with BTreeMap. This would have no performance change at runtime, and may have an insignificant performance change at build time.

A definite source of non-determinism is the following, which seems a random entry when the group has more than one:

hashify/src/tiny.rs

Line 250 in 242c78f

keys.keys().next().unwrap(),

I don't think this randomness was intentional, I suspect it was done in a "just use any" intent.

[WhyNotHugo]

The use of HashSet seems safe: it's only used for counting unique entries.

[WhyNotHugo]

Test script to compare output with cargo expand:

#!/bin/sh

set -e

HASHIFY_DIR="$(cd "$(dirname "$0")/.." && pwd)"
TMPDIR=$(mktemp -d)
trap "rm -rf $TMPDIR" EXIT

mkdir -p "$TMPDIR/repro/src"

cat > "$TMPDIR/repro/Cargo.toml" <<EOF
[package]
name = "repro"
version = "0.1.0"
edition = "2021"

[dependencies]
hashify = { path = "$HASHIFY_DIR" }
EOF

cat > "$TMPDIR/repro/src/lib.rs" <<'EOF'
pub fn is_reply_prefix(prefix: &[u8]) -> bool {
    hashify::tiny_set!(
        prefix,
        "re",
        "res",
        "sv",
        "antw",
        "ref",
        "aw",
        "απ",
        "השב",
        "vá",
        "r",
        "rif",
        "bls",
        "odp",
        "ynt",
        "atb",
        "رد",
        "回复",
        "转发",
    )
}
EOF

cd "$TMPDIR/repro"

ATTEMPTS=5
HASH_FILE="$TMPDIR/hashes"
truncate -s 0 "$HASH_FILE"

i=1
while [ "$i" -le "$ATTEMPTS" ]; do
    cargo clean 2>/dev/null
    HASH=$(cargo expand 2>/dev/null | md5sum | cut -d' ' -f1)
    echo "$HASH" >> "$HASH_FILE"
    echo "Build $i: $HASH"
    i=$((i + 1))
done

echo ""
UNIQUE=$(sort -u "$HASH_FILE" | wc -l)
if [ "$UNIQUE" -eq 1 ]; then
    echo "PASS: All $ATTEMPTS builds produced identical output (reproducible)"
    exit 0
else
    echo "FAIL: $UNIQUE distinct outputs from $ATTEMPTS builds (non-reproducible)"
    exit 1
fi

[WhyNotHugo]

#5 shows deterministic results with the above script.