llvm::MachO::InterfaceFile::symbols is non-deterministic

[MaskRay]

llvm-project/llvm/include/llvm/TextAPI/InterfaceFile.h

Line 447 in 0991bd7

std::unique_ptr<SymbolSet> SymbolsSet;

std::unique_ptr<SymbolSet> SymbolsSet; is implemented as a using SymbolsMapType = llvm::DenseMap<SymbolsMapKey, Symbol *>;, which has a non-deterministic iteration order in LLVM_ENABLE_ABI_BREAKING_CHECKS=on builds (hash_combine(hash_value(Key.Kind), hash_value(Key.Name)) uses a non-deterministic seed #96282).

This hade made lld/test/MachO/dead-strip.s flaky until I fixed by it with ceeea91.
The fix is imperfect, since it's better for llvm/include/llvm/TextAPI/InterfaceFile.h to provide a stable iteration order.

[llvmbot]

@llvm/issue-subscribers-lld-macho

Author: Fangrui Song (MaskRay)

https://github.com/llvm/llvm-project/blob/0991bd7887a313d4d6bb66ca44d11939ad71b660/llvm/include/llvm/TextAPI/InterfaceFile.h#L447 `std::unique_ptr<SymbolSet> SymbolsSet;` is implemented as a `using SymbolsMapType = llvm::DenseMap<SymbolsMapKey, Symbol *>;`, which has a non-deterministic iteration order in `LLVM_ENABLE_ABI_BREAKING_CHECKS=on` builds (`hash_combine(hash_value(Key.Kind), hash_value(Key.Name))` uses a non-deterministic seed #96282).

This hade made lld/test/MachO/dead-strip.s flaky until I fixed by it with ceeea91.
The fix is imperfect, since it's better for llvm/include/llvm/TextAPI/InterfaceFile.h to provide a stable iteration order.

[MaskRay]

@cyndyishida @int3

[tgymnich]

here is a draft addressing the issue using std::map #97615

[cyndyishida]

For most operations it's not necessary, so I'd prefer to keep the DenseMap container to keep TAPI & Apple's linker's usage of tbd files fast.
I'd be happy to provide an API in InterfaceFile that provides an ordered view of the symbols though, so it doesn't need to be handled on the client side. WDYT?