Fix race condition when using validations

To allow a validation B on a target A to depend on A I previously
decoupled resolution of A from resolution of B. While testing this with
fuchsia I ran into a race condition where target A would be written
while B was not fully resolved. This caused the Ninja file to contain
garbled output for B.

This CL decouples resolution and writing so that a target A can resolve
but waits with writing until all its validations are resolved too.

Bug: 478798763
Change-Id: Ica3d89f90b3753fde9edbbf8ad7d9fe2e1ca372a
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/20920
Commit-Queue: Neri Marschik <nerima@google.com>
Reviewed-by: Takuto Ikuta <tikuta@google.com>

src/gn/builder.cc

diff --git a/src/gn/builder.cc b/src/gn/builder.cc
index 84eff84..51f9a02 100644
--- a/src/gn/builder.cc
+++ b/src/gn/builder.cc
@@ -529,7 +529,7 @@
     if (!ResolveDeps(&target->public_deps(), err) ||
         !ResolveDeps(&target->private_deps(), err) ||
         !ResolveDeps(&target->data_deps(), err) ||
-        !ResolveDeps(&target->validations(), err) ||
+        !ResolveValidationDeps(&target->validations(), err) ||
         !ResolveConfigs(&target->configs(), err) ||
         !ResolveConfigs(&target->all_dependent_configs(), err) ||
         !ResolveConfigs(&target->public_configs(), err) ||
@@ -586,8 +586,10 @@
 bool Builder::CompleteItemResolution(BuilderRecord* record, Err* err) {
   record->set_resolved(true);
 
-  if (record->should_generate() && resolved_and_generated_callback_)
+  if (record->should_generate() && record->can_write() &&
+      resolved_and_generated_callback_) {
     resolved_and_generated_callback_(record);
+  }
 
   // Recursively update everybody waiting on this item to be resolved.
   const BuilderRecordSet waiting_deps = record->waiting_on_resolution();
@@ -599,6 +601,21 @@
     }
   }
   record->waiting_on_resolution().clear();
+
+  // Check for any targets waiting on this one for writing.
+  const BuilderRecordSet waiting_for_writing =
+      record->waiting_on_resolution_for_writing();
+  for (auto it = waiting_for_writing.begin(); it.valid(); ++it) {
+    BuilderRecord* waiting = *it;
+    if (waiting->OnResolvedValidationDep(record)) {
+      if (waiting->can_write() && waiting->should_generate() &&
+          resolved_and_generated_callback_) {
+        resolved_and_generated_callback_(waiting);
+      }
+    }
+  }
+  record->waiting_on_resolution_for_writing().clear();
+
   return true;
 }
 
@@ -615,6 +632,34 @@
   return true;
 }
 
+bool Builder::ResolveValidationDeps(LabelTargetVector* deps, Err* err) {
+  for (LabelTargetPair& cur : *deps) {
+    DCHECK(!cur.ptr);
+
+    // We only need the item to be defined, not resolved.
+    BuilderRecord* record = GetRecord(cur.label);
+    if (!record || !record->item()) {
+      *err = Err(cur.origin, "Item not found",
+                 "\"" + cur.label.GetUserVisibleName(true) +
+                     "\" doesn't\n"
+                     "refer to an existent thing.");
+      return false;
+    }
+
+    if (!BuilderRecord::IsItemOfType(record->item(),
+                                     BuilderRecord::ITEM_TARGET)) {
+      *err =
+          Err(cur.origin, "This is not a target",
+              "\"" + cur.label.GetUserVisibleName(true) + "\" refers to a " +
+                  record->item()->GetItemTypeName() + " instead of a target.");
+      return false;
+    }
+
+    cur.ptr = record->item()->AsTarget();
+  }
+  return true;
+}
+
 bool Builder::ResolveConfigs(UniqueVector<LabelConfigPair>* configs, Err* err) {
   for (const auto& cur : *configs) {
     DCHECK(!cur.ptr);

src/gn/builder.h

diff --git a/src/gn/builder.h b/src/gn/builder.h
index 6578a89..d6c42eb 100644
--- a/src/gn/builder.h
+++ b/src/gn/builder.h
@@ -132,6 +132,7 @@
   // that everything should be resolved by this point, so will return an error
   // if anything isn't found or if the type doesn't match.
   bool ResolveDeps(LabelTargetVector* deps, Err* err);
+  bool ResolveValidationDeps(LabelTargetVector* deps, Err* err);
   bool ResolveConfigs(UniqueVector<LabelConfigPair>* configs, Err* err);
   bool ResolvePool(Target* target, Err* err);
   bool ResolveToolchain(Target* target, Err* err);

src/gn/builder_record.cc

diff --git a/src/gn/builder_record.cc b/src/gn/builder_record.cc
index f5af711..ff1a613 100644
--- a/src/gn/builder_record.cc
+++ b/src/gn/builder_record.cc
@@ -76,9 +76,24 @@
 }
 
 void BuilderRecord::AddValidationDep(BuilderRecord* record) {
-  if (all_deps_.add(record) && !record->item()) {
-    unresolved_count_ += 1;
-    record->waiting_on_definition_.add(this);
+  // Validation dependencies are treated differently than normal dependencies:
+  // 1. They are added to all_deps_ for graph traversal (should_generate
+  //    propagation) and error checking.
+  // 2. They block resolution ONLY if they are undefined (!item). This allows
+  //    cycles (A is validated by B, B depends on A) to resolve.
+  // 3. They block writing if they are unresolved. This prevents race conditions
+  //    where we might write the ninja file before the validation output path
+  //    is computed.
+  all_deps_.add(record);
+  if (validation_deps_.add(record)) {
+    if (!record->item()) {
+      unresolved_count_ += 1;
+      record->waiting_on_definition_.add(this);
+    }
+    if (!record->resolved()) {
+      unresolved_validation_count_ += 1;
+      record->waiting_on_resolution_for_writing_.add(this);
+    }
   }
 }
 
@@ -94,6 +109,12 @@
   return --unresolved_count_ == 0;
 }
 
+bool BuilderRecord::OnResolvedValidationDep(const BuilderRecord* dep) {
+  DCHECK(validation_deps_.contains(const_cast<BuilderRecord*>(dep)));
+  DCHECK(unresolved_validation_count_ > 0);
+  return --unresolved_validation_count_ == 0;
+}
+
 std::vector<const BuilderRecord*> BuilderRecord::GetSortedUnresolvedDeps()
     const {
   std::vector<const BuilderRecord*> result;

src/gn/builder_record.h

diff --git a/src/gn/builder_record.h b/src/gn/builder_record.h
index 06ff6c3..b3b4aba 100644
--- a/src/gn/builder_record.h
+++ b/src/gn/builder_record.h
@@ -73,6 +73,10 @@
 
   bool can_resolve() const { return item_ && unresolved_count_ == 0; }
 
+  bool can_write() const {
+    return resolved_ && unresolved_validation_count_ == 0;
+  }
+
   // All records this one is depending on. Note that this includes gen_deps for
   // targets, which can have cycles.
   BuilderRecordSet& all_deps() { return all_deps_; }
@@ -97,6 +101,19 @@
     return waiting_on_resolution_;
   }
 
+  // Records that are waiting on this one to be resolved before they can be
+  // written to the ninja file. This is used for "validations" dependencies.
+  BuilderRecordSet& waiting_on_resolution_for_writing() {
+    return waiting_on_resolution_for_writing_;
+  }
+  const BuilderRecordSet& waiting_on_resolution_for_writing() const {
+    return waiting_on_resolution_for_writing_;
+  }
+
+  // Validation dependencies.
+  BuilderRecordSet& validation_deps() { return validation_deps_; }
+  const BuilderRecordSet& validation_deps() const { return validation_deps_; }
+
   void AddDep(BuilderRecord* record);
   void AddGenDep(BuilderRecord* record);
   void AddValidationDep(BuilderRecord* record);
@@ -111,6 +128,11 @@
   // should now be resolved.
   bool OnResolvedDep(const BuilderRecord* dep);
 
+  // Call this method to notify the record that its validation dependency |dep|
+  // was just resolved. This returns true to indicate that the current record
+  // is now ready to be written.
+  bool OnResolvedValidationDep(const BuilderRecord* dep);
+
   // Comparator function used to sort records from their label.
   static bool LabelCompare(const BuilderRecord* a, const BuilderRecord* b) {
     return a->label_ < b->label_;
@@ -125,9 +147,12 @@
   const ParseNode* originally_referenced_from_ = nullptr;
 
   size_t unresolved_count_ = 0;
+  size_t unresolved_validation_count_ = 0;
   BuilderRecordSet all_deps_;
+  BuilderRecordSet validation_deps_;
   BuilderRecordSet waiting_on_resolution_;
   BuilderRecordSet waiting_on_definition_;
+  BuilderRecordSet waiting_on_resolution_for_writing_;
 
   BuilderRecord(const BuilderRecord&) = delete;
   BuilderRecord& operator=(const BuilderRecord&) = delete;

src/gn/builder_unittest.cc

diff --git a/src/gn/builder_unittest.cc b/src/gn/builder_unittest.cc
index da497c7..e53bf29 100644
--- a/src/gn/builder_unittest.cc
+++ b/src/gn/builder_unittest.cc
@@ -431,4 +431,150 @@
   EXPECT_EQ(b_ptr, a_ptr->validations()[0].ptr);
 }
 
+// Tests that validation dependencies block writing until resolved.
+TEST_F(BuilderTest, ValidationsBlockWriting) {
+  DefineToolchain();
+  SourceDir toolchain_dir = settings_.toolchain_label().dir();
+  std::string toolchain_name = settings_.toolchain_label().name();
+
+  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);
+
+  // Define A. A lists B in validations.
+  auto a = std::make_unique<Target>(&settings_, a_label);
+  a->set_output_type(Target::ACTION);
+  a->validations().push_back(LabelTargetPair(b_label));
+  a->visibility().SetPublic();
+  builder_.ItemDefined(std::move(a));
+
+  // Define B. B depends on C.
+  auto b = std::make_unique<Target>(&settings_, b_label);
+  b->set_output_type(Target::ACTION);
+  b->private_deps().push_back(LabelTargetPair(c_label));
+  b->visibility().SetPublic();
+  builder_.ItemDefined(std::move(b));
+
+  // C is unresolved (waiting on definition).
+  // B is unresolved (waiting on C).
+  // A should be RESOLVED (because B is defined, and validations only wait on
+  // definition for resolution). BUT A should be blocked from WRITING because B
+  // is not resolved.
+
+  BuilderRecord* a_record = builder_.GetRecord(a_label);
+  BuilderRecord* b_record = builder_.GetRecord(b_label);
+
+  scheduler().Run();
+
+  EXPECT_TRUE(a_record->resolved());
+  EXPECT_FALSE(b_record->resolved());
+
+  // Check that B knows A is waiting on it for writing.
+  EXPECT_TRUE(b_record->waiting_on_resolution_for_writing().contains(a_record));
+}
+
+// Tests that a target can validate a target that depends on it.
+// A -> validations -> B
+// B -> deps -> A
+TEST_F(BuilderTest, ValidationsWithCycle) {
+  DefineToolchain();
+  SourceDir toolchain_dir = settings_.toolchain_label().dir();
+  std::string toolchain_name = settings_.toolchain_label().name();
+
+  Label a_label(SourceDir("//a/"), "a", toolchain_dir, toolchain_name);
+  Label b_label(SourceDir("//b/"), "b", toolchain_dir, toolchain_name);
+
+  // Define A. A lists B in validations.
+  auto a = std::make_unique<Target>(&settings_, a_label);
+  a->set_output_type(Target::ACTION);
+  a->validations().push_back(LabelTargetPair(b_label));
+  a->visibility().SetPublic();
+  builder_.ItemDefined(std::move(a));
+
+  // Define B. B depends on A.
+  auto b = std::make_unique<Target>(&settings_, b_label);
+  b->set_output_type(Target::ACTION);
+  b->private_deps().push_back(LabelTargetPair(a_label));
+  b->visibility().SetPublic();
+  builder_.ItemDefined(std::move(b));
+
+  BuilderRecord* a_record = builder_.GetRecord(a_label);
+  BuilderRecord* b_record = builder_.GetRecord(b_label);
+
+  scheduler().Run();
+
+  // Both should be resolved.
+  EXPECT_TRUE(a_record->resolved());
+  EXPECT_TRUE(b_record->resolved());
+
+  // There should be no errors (cycle detection passed).
+  Err err;
+  EXPECT_TRUE(builder_.CheckForBadItems(&err));
+  EXPECT_FALSE(err.has_error());
+}
+
+// Tests that if a validation resolves, the target does NOT write if it
+// is still waiting on other dependencies to resolve.
+// A -> deps -> B
+// A -> validations -> C
+// Sequence: C resolves. A should NOT write. B resolves. A writes.
+TEST_F(BuilderTest, ValidationsPrematureWrite) {
+  DefineToolchain();
+  SourceDir toolchain_dir = settings_.toolchain_label().dir();
+  std::string toolchain_name = settings_.toolchain_label().name();
+
+  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);
+
+  // Define A. A depends on B and has validation C.
+  auto a = std::make_unique<Target>(&settings_, a_label);
+  a->set_output_type(Target::ACTION);
+  a->private_deps().push_back(LabelTargetPair(b_label));
+  a->validations().push_back(LabelTargetPair(c_label));
+  a->visibility().SetPublic();
+  builder_.ItemDefined(std::move(a));
+
+  // Define C. C is standalone.
+  auto c = std::make_unique<Target>(&settings_, c_label);
+  c->set_output_type(Target::ACTION);
+  c->visibility().SetPublic();
+  builder_.ItemDefined(std::move(c));
+
+  // Track written targets.
+  std::vector<const BuilderRecord*> written;
+  builder_.set_resolved_and_generated_callback(
+      [&written](const BuilderRecord* record) { written.push_back(record); });
+
+  // C should resolve. A is waiting on B.
+  scheduler().Run();
+
+  BuilderRecord* a_record = builder_.GetRecord(a_label);
+  BuilderRecord* c_record = builder_.GetRecord(c_label);
+
+  EXPECT_TRUE(c_record->resolved());
+  EXPECT_FALSE(a_record->resolved());
+
+  // Only C should be written.
+  ASSERT_EQ(1u, written.size());
+  EXPECT_EQ(c_record, written[0]);
+
+  // Define B.
+  auto b = std::make_unique<Target>(&settings_, b_label);
+  b->set_output_type(Target::ACTION);
+  b->visibility().SetPublic();
+  builder_.ItemDefined(std::move(b));
+  BuilderRecord* b_record = builder_.GetRecord(b_label);
+
+  scheduler().Run();
+
+  EXPECT_TRUE(a_record->resolved());
+
+  // Order should be C, B, A.
+  ASSERT_EQ(3u, written.size());
+  EXPECT_EQ(c_record, written[0]);
+  EXPECT_EQ(b_record, written[1]);
+  EXPECT_EQ(a_record, written[2]);
+}
+
 }  // namespace gn_builder_unittest

src/gn/target.cc

diff --git a/src/gn/target.cc b/src/gn/target.cc
index 9cba6af..e3c95f3 100644
--- a/src/gn/target.cc
+++ b/src/gn/target.cc
@@ -913,6 +913,12 @@
     }
   }
 
+  // Targets with validations must be written to ensure the validations run,
+  // even if they have no other inputs or dependencies.
+  if (!validations_.empty()) {
+    return true;
+  }
+
   if (output_type() == BUNDLE_DATA) {
     return !sources().empty();
   }