This is an archive of the discontinued LLVM Phabricator instance.

[clang][deps] Ensure deterministic order of TU '-fmodule-file=' arguments
ClosedPublic

Authored by jansvoboda11 on Jun 7 2021, 6:09 AM.

Details

Summary

Translation units with multiple direct modular dependencies trigger a non-deterministic ordering in clang-scan-deps. This boils down to usage of std::unordered_map, which gets replaced by std::map in this patch.

Depends on D103526.

Diff Detail

Event Timeline

jansvoboda11 created this revision.Jun 7 2021, 6:09 AM
jansvoboda11 requested review of this revision.Jun 7 2021, 6:09 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 7 2021, 6:09 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript

I'm not sure the performance problems with std::map will matter in practice here, but have you considered sorting before emission rather than relying on the data structure's iteration order? (It'd make it easy to switch to StringMap in the future.)

jansvoboda11 planned changes to this revision.Aug 4 2021, 4:55 AM
jansvoboda11 requested review of this revision.Aug 23 2021, 5:59 AM

I'm aware of the drawbacks of std::map, but I think having the container sorted at all times promotes correctness/determinism which we really care about in this context. Forgetting to call sort at all the right places is very easy as this patch demonstrates.

But if you are strongly opposed to using std::map here, I'm okay with using std::unordered_map or llvm::StringMap and sorting where necessary.

dexonsmith accepted this revision.Aug 23 2021, 9:01 AM

Another option to be aware of is MapVector (https://llvm.org/docs/ProgrammersManual.html#llvm-adt-mapvector-h). Does not sort, but guarantees iteration order.

But LGTM anyway. I don't think the exact data structure is important here. Please just add a comment documenting that consumers need a deterministic iteration order so anyone updating or optimizing this later knows what the constraints are.

This revision is now accepted and ready to land.Aug 23 2021, 9:01 AM
This revision was landed with ongoing or failed builds.Aug 25 2021, 2:14 AM
This revision was automatically updated to reflect the committed changes.