tree 94f40e79eb8e143589b21d0d87753db3849b1af2
parent d417bc7ecb4e20b3b2cccec7c426831a6082f9fb
author David 'Digit' Turner <digit@google.com> 1639132629 +0100
committer Commit Bot <commit-bot@chromium.org> 1639413160 +0000

Ensure circular dependency check output is deterministic.

When BuilderRecordMap changed from an std::map<Label, BuilderRecord>
to an unordered container, the order ot BuilderRecord::GetUnresolvedDeps()
and a few other functions became non-deterministic.

This CL fixes that by sorting records based on their label when necessary,
which all happen to be outside of the critical Builder performance loop.
I.e.:

  Builder::CheckForBadItems()
    Sorting happens it has been determined that there are bad items,
    so doesn't impact the regular case.

  Builder::GetAllRecords()
  Builder::GetAlResolvedItems()
  Builder::GetAllResolvedTargets()

+ Add a small unit-test for BuilderRecord::GetSortedUnresolvedDeps().

Measurements show no impact on performance.

Bug: 271
Change-Id: Iaa054127c140797e178dd1360ff46ed293029e27
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/12620
Reviewed-by: Brett Wilson <brettw@chromium.org>
Commit-Queue: David Turner <digit@google.com>