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>
diff --git a/src/gn/builder.cc b/src/gn/builder.cc
index 7e36deb..adb39ab 100644
--- a/src/gn/builder.cc
+++ b/src/gn/builder.cc
@@ -5,6 +5,7 @@
#include "gn/builder.h"
#include <stddef.h>
+#include <algorithm>
#include <utility>
#include "gn/action_values.h"
@@ -34,9 +35,7 @@
bool RecursiveFindCycle(const BuilderRecord* search_in,
std::vector<const BuilderRecord*>* path) {
path->push_back(search_in);
- BuilderRecordSet unresolved_deps = search_in->GetUnresolvedDeps();
- for (auto it = unresolved_deps.begin(); it.valid(); ++it) {
- const BuilderRecord* cur = *it;
+ for (const auto& cur : search_in->GetSortedUnresolvedDeps()) {
std::vector<const BuilderRecord*>::iterator found =
std::find(path->begin(), path->end(), cur);
if (found != path->end()) {
@@ -136,6 +135,8 @@
result.reserve(records_.size());
for (const auto& record : records_)
result.push_back(&record);
+ // Ensure deterministic outputs.
+ std::sort(result.begin(), result.end(), BuilderRecord::LabelCompare);
return result;
}
@@ -148,7 +149,10 @@
result.push_back(record.item());
}
}
-
+ // Ensure deterministic outputs.
+ std::sort(result.begin(), result.end(), [](const Item* a, const Item* b) {
+ return a->label() < b->label();
+ });
return result;
}
@@ -160,6 +164,10 @@
record.should_generate() && record.item())
result.push_back(record.item()->AsTarget());
}
+ // Ensure deterministic outputs.
+ std::sort(result.begin(), result.end(), [](const Target* a, const Target* b) {
+ return a->label() < b->label();
+ });
return result;
}
@@ -183,21 +191,27 @@
// but none will be resolved. If this happens, we'll check explicitly for
// that below.
std::vector<const BuilderRecord*> bad_records;
- std::string depstring;
for (const auto& src : records_) {
if (!src.should_generate())
continue; // Skip ungenerated nodes.
- if (!src.resolved()) {
+ if (!src.resolved())
bad_records.push_back(&src);
+ }
+ if (bad_records.empty())
+ return true;
- // Check dependencies.
- BuilderRecordSet unresolved_deps = src.GetUnresolvedDeps();
- for (const auto* dest : unresolved_deps) {
- if (!dest->item()) {
- depstring += src.label().GetUserVisibleName(true) + "\n needs " +
- dest->label().GetUserVisibleName(true) + "\n";
- }
+ // Sort by label to ensure deterministic outputs.
+ std::sort(bad_records.begin(), bad_records.end(),
+ BuilderRecord::LabelCompare);
+
+ std::string depstring;
+ for (const auto& src : bad_records) {
+ // Check dependencies.
+ for (const auto* dest : src->GetSortedUnresolvedDeps()) {
+ if (!dest->item()) {
+ depstring += src->label().GetUserVisibleName(true) + "\n needs " +
+ dest->label().GetUserVisibleName(true) + "\n";
}
}
}
@@ -301,6 +315,11 @@
return true;
}
+BuilderRecord* Builder::GetOrCreateRecordForTesting(const Label& label) {
+ Err err;
+ return GetOrCreateRecordOfType(label, nullptr, BuilderRecord::ITEM_UNKNOWN, &err);
+}
+
BuilderRecord* Builder::GetOrCreateRecordOfType(const Label& label,
const ParseNode* request_from,
BuilderRecord::ItemType type,
diff --git a/src/gn/builder.h b/src/gn/builder.h
index 4b85824..bebaa81 100644
--- a/src/gn/builder.h
+++ b/src/gn/builder.h
@@ -60,6 +60,9 @@
// If there are any undefined references, returns false and sets the error.
bool CheckForBadItems(Err* err) const;
+ // Get or create an empty record for unit-testing.
+ BuilderRecord* GetOrCreateRecordForTesting(const Label& label);
+
private:
bool TargetDefined(BuilderRecord* record, Err* err);
bool ConfigDefined(BuilderRecord* record, Err* err);
diff --git a/src/gn/builder_record.cc b/src/gn/builder_record.cc
index 7849d91..d1d0c53 100644
--- a/src/gn/builder_record.cc
+++ b/src/gn/builder_record.cc
@@ -74,13 +74,15 @@
return --unresolved_count_ == 0;
}
-BuilderRecord::BuilderRecordSet BuilderRecord::GetUnresolvedDeps() const {
- BuilderRecordSet result;
+std::vector<const BuilderRecord*> BuilderRecord::GetSortedUnresolvedDeps()
+ const {
+ std::vector<const BuilderRecord*> result;
for (auto it = all_deps_.begin(); it.valid(); ++it) {
BuilderRecord* dep = *it;
if (dep->waiting_on_resolution_.contains(const_cast<BuilderRecord*>(this)))
- result.add(dep);
+ result.push_back(dep);
}
+ std::sort(result.begin(), result.end(), LabelCompare);
return result;
}
diff --git a/src/gn/builder_record.h b/src/gn/builder_record.h
index 28f75fe..c4dc867 100644
--- a/src/gn/builder_record.h
+++ b/src/gn/builder_record.h
@@ -78,9 +78,9 @@
BuilderRecordSet& all_deps() { return all_deps_; }
const BuilderRecordSet& all_deps() const { return all_deps_; }
- // Return the set of unresolved records this one is depend on.
- // This is a subset of all_deps() above.
- BuilderRecordSet GetUnresolvedDeps() const;
+ // Get the set of unresolved records this one depends on,
+ // as a list sorted by label.
+ std::vector<const BuilderRecord*> GetSortedUnresolvedDeps() const;
// Call this method to notify the record that its dependency |dep| was
// just resolved. This returns true to indicate that the current record
@@ -97,6 +97,11 @@
void AddGenDep(BuilderRecord* record);
void AddDep(BuilderRecord* record);
+ // Comparator function used to sort records from their label.
+ static bool LabelCompare(const BuilderRecord* a, const BuilderRecord* b) {
+ return a->label_ < b->label_;
+ }
+
private:
ItemType type_;
bool should_generate_ = false;
diff --git a/src/gn/builder_unittest.cc b/src/gn/builder_unittest.cc
index 2a354d5..79285ab 100644
--- a/src/gn/builder_unittest.cc
+++ b/src/gn/builder_unittest.cc
@@ -138,10 +138,13 @@
// A should have two deps: B and the toolchain. Only B should be unresolved.
EXPECT_EQ(2u, a_record->all_deps().size());
- EXPECT_EQ(1u, a_record->GetUnresolvedDeps().size());
EXPECT_TRUE(a_record->all_deps().contains(toolchain_record));
EXPECT_TRUE(a_record->all_deps().contains(b_record));
- EXPECT_TRUE(a_record->GetUnresolvedDeps().contains(b_record));
+
+ std::vector<const BuilderRecord*> a_unresolved =
+ a_record->GetSortedUnresolvedDeps();
+ EXPECT_EQ(1u, a_unresolved.size());
+ EXPECT_EQ(a_unresolved[0], b_record);
// B should be marked as having A waiting on it.
EXPECT_EQ(1u, b_record->waiting_on_resolution().size());
@@ -174,15 +177,47 @@
EXPECT_TRUE(b_record->resolved());
EXPECT_TRUE(c_record->resolved());
- EXPECT_TRUE(a_record->GetUnresolvedDeps().empty());
- EXPECT_TRUE(b_record->GetUnresolvedDeps().empty());
- EXPECT_TRUE(c_record->GetUnresolvedDeps().empty());
+ EXPECT_TRUE(a_record->GetSortedUnresolvedDeps().empty());
+ EXPECT_TRUE(b_record->GetSortedUnresolvedDeps().empty());
+ EXPECT_TRUE(c_record->GetSortedUnresolvedDeps().empty());
EXPECT_TRUE(a_record->waiting_on_resolution().empty());
EXPECT_TRUE(b_record->waiting_on_resolution().empty());
EXPECT_TRUE(c_record->waiting_on_resolution().empty());
}
+TEST_F(BuilderTest, SortedUnresolvedDeps) {
+ SourceDir toolchain_dir = settings_.toolchain_label().dir();
+ std::string toolchain_name = settings_.toolchain_label().name();
+
+ // Construct a dependency graph with:
+ // A -> B
+ // A -> D
+ // A -> C
+ //
+ // Ensure that the unresolved list of A is always [B, C, D]
+ //
+ Label a_label(SourceDir("//a/"), "a", toolchain_dir, toolchain_name);
+ Label b_label(SourceDir("//b/"), "b", toolchain_dir, toolchain_name);
+ Label c_label(SourceDir("//c/"), "c", toolchain_dir, toolchain_name);
+ Label d_label(SourceDir("//d/"), "d", toolchain_dir, toolchain_name);
+
+ BuilderRecord* a_record = builder_.GetOrCreateRecordForTesting(a_label);
+ BuilderRecord* b_record = builder_.GetOrCreateRecordForTesting(b_label);
+ BuilderRecord* c_record = builder_.GetOrCreateRecordForTesting(c_label);
+ BuilderRecord* d_record = builder_.GetOrCreateRecordForTesting(d_label);
+
+ a_record->AddDep(b_record);
+ a_record->AddDep(d_record);
+ a_record->AddDep(c_record);
+
+ std::vector<const BuilderRecord*> a_unresolved = a_record->GetSortedUnresolvedDeps();
+ EXPECT_EQ(3u, a_unresolved.size()) << a_unresolved.size();
+ EXPECT_EQ(b_record, a_unresolved[0]);
+ EXPECT_EQ(c_record, a_unresolved[1]);
+ EXPECT_EQ(d_record, a_unresolved[2]);
+}
+
// Tests that the "should generate" flag is set and propagated properly.
TEST_F(BuilderTest, ShouldGenerate) {
DefineToolchain();
