llvm-cov: Instantiation groups are printed in non-deterministic order

[Zalathar]

When llvm-cov show shows instantiation groups, it seems to print them in a non-deterministic order (presumably influenced by hash bucket order).

This is a hassle for Rust's -Cinstrument-coverage tests, since they have to jump through hoops to ignore instantiation names when comparing output snapshots.

Ideally the instantiations should at least be naïvely sorted by their function name. That would at least be deterministic in the common case where all instantiations have distinct names.

[Zalathar]

It seems that the instantiations do get sorted for display:

llvm-project/llvm/tools/llvm-cov/SourceCoverageView.cpp

Lines 197 to 201 in e46aa7f

	// We need the expansions, instantiations, and branches sorted so we can go
	// through them while we iterate lines.
	llvm::stable_sort(ExpansionSubViews);
	llvm::stable_sort(InstantiationSubViews);
	llvm::stable_sort(BranchSubViews);

But this sort only compares their (last) line number so that they display after the correct line, and does not compare the function name for instantiations with the same line:

llvm-project/llvm/tools/llvm-cov/SourceCoverageView.h

Lines 64 to 67 in e46aa7f

	friend bool operator<(const InstantiationView &LHS,
	const InstantiationView &RHS) {
	return LHS.Line < RHS.Line;
	}

[Zalathar]

Here's an example of Rust's instrument-coverage tests accidentally being broken, due to a bug in the regex used to ignore instantiation names: rust-lang/rust#110942

[Zalathar]

Another potential explanation is that llvm-cov is faithfully preserving the order of entries in the binary’s __llvm_covfun section, and those entries are linked in an unpredictable order.