Remove premature target writing before validation during `gn gen`.
This change modifies the way GN schedules writing targets to the
Ninja build plan to remove random crashes that have been affecting
the Fuchsia build for several weeks now.
The root cause of the problem, described in the associated bug,
is that a target and *all* its dependencies, including validations,
must be resolved to ensure there are no crash during the write
(which can call Target::GetMetadata() for generated_file() targets,
which will walk standard and validation targets).
Before this CL, the code used the condition that a target had to
be resolved, and all its validations *defined*, which is NOT
sufficient.
The crash was hidden by the fact that target resolution was pushed
to the background, resulting in race conditions and non-deterministic
ordering of the writes. This behavior was removed in a previous CL,
the current one focuses on the actual logic fix.
The fix includes defining a new RecordState enum to better describe
the different states of a given BuilderRecord, replacing the simple
`resolved_` boolean flag. State transitions can only happen under
specific conditions that are now properly documented.
- builder_record.h: Introduce RecordState enum to model the
state of each record (Init/Defined/Resolved/Finalized). and
document them properly, along with the conditions when a
record can change state.
Rename resolved() to is_resolved(), can_write() to can_finalize(),
add is_defined() and is_finalized()
Add Set{Defined,Resolved,Finalized}() methods to change the
state and document what the caller should do just after that
to ensure proper tracking of state changes.
Add NotifyWaitingDependentsOnXXX() template methods to
clarify the builder.cc code and keep the BuilderRecordSet
values hidden.
Remove validation_deps_ which is no longer useful.
Rename the BuilderRecordSet variables for clarity, better
explaining their purpose.
Add DEBUG_BUILDER_RECORD macro. Set this to 1 to enable
debug logs during Builder operations during development.
- builder.cc: Add FinalizeItem() method, and modify the logic
accordingly, using the new BuilderRecord methods. Add
DEBUG_BUILDER_RECORD_LOG() statements to print debug traces
when DEBUG_BUILD_RECORD is set to 1.
- builder_unittest.cc: Adjust unit-tests to reflect the new
logic.
Benchmarking shows now statistically difference in `gn gen`
and `gn gen --check` times for Fuchsia and Chrome builds on
a local cloudtop.
Bug: 494481832
Change-Id: Ibeae5350818c6b73fb88247fc73f85ab596c9531
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/21721
Commit-Queue: David Turner <digit@google.com>
Reviewed-by: Andrew Grieve <agrieve@google.com>
diff --git a/src/gn/builder.cc b/src/gn/builder.cc
index 9a85e20..cc4d6ff 100644
--- a/src/gn/builder.cc
+++ b/src/gn/builder.cc
@@ -73,6 +73,9 @@
return;
}
+ DEBUG_BUILDER_RECORD_LOG("BEGIN_DEFINED %s\n",
+ record->ToDebugString().c_str());
+
// Check that it's not been already defined.
if (record->item()) {
bool with_toolchain =
@@ -87,20 +90,20 @@
return;
}
- record->set_item(std::move(item));
+ record->SetDefined(std::move(item));
- // Notify anyone waiting on this item's definition.
- const BuilderRecordSet& waiting_deps = record->waiting_on_definition();
- for (auto it = waiting_deps.begin(); it.valid(); ++it) {
- BuilderRecord* waiting = *it;
- if (waiting->OnDefinedDep(record)) {
- if (!ResolveItem(waiting, &err)) {
- g_scheduler->FailWithError(err);
- return;
- }
- }
+ // Notify anyone waiting on this item's definition, and resolve those
+ // that are no longer waiting.
+ if (!record->NotifyDependentsWaitingOnValidationDefinition(
+ [&](BuilderRecord* waiting) {
+ DEBUG_BUILDER_RECORD_LOG(" VALDEFNOTIFY %s -> %s\n",
+ record->ToDebugString().c_str(),
+ waiting->ToDebugString().c_str());
+ return ResolveItem(waiting, &err);
+ })) {
+ g_scheduler->FailWithError(err);
+ return;
}
- record->waiting_on_definition().clear();
// Do target-specific dependency setup. This will also schedule dependency
// loads for targets that are required.
@@ -128,6 +131,7 @@
return;
}
}
+ DEBUG_BUILDER_RECORD_LOG("END_DEFINED %s\n", record->ToDebugString().c_str());
}
const Item* Builder::GetItem(const Label& label) const {
@@ -211,7 +215,7 @@
if (!src.should_generate())
continue; // Skip ungenerated nodes.
- if (!src.resolved())
+ if (!src.is_resolved())
bad_records.push_back(&src);
}
if (bad_records.empty())
@@ -329,6 +333,7 @@
RecursiveSetShouldGenerate(record, true);
loader_->ToolchainLoaded(toolchain);
+
return true;
}
@@ -499,7 +504,7 @@
// that case.
record->set_should_generate(true);
- // This may have caused the item to go into "resolved and generated" state.
+ // This may have caused the item to go into "finalized and generated" state.
CheckAndTriggerWrite(record);
} else if (!force) {
return; // Already set and we're not required to iterate dependencies.
@@ -520,7 +525,7 @@
}
bool Builder::ResolveItem(BuilderRecord* record, Err* err) {
- DCHECK(record->can_resolve() && !record->resolved());
+ DCHECK(record->can_resolve() && !record->is_resolved());
if (record->type() == BuilderRecord::ITEM_TARGET) {
Target* target = record->item()->AsTarget();
@@ -535,6 +540,9 @@
!ResolvePool(target, err) || !ResolveToolchain(target, err))
return false;
+ DEBUG_BUILDER_RECORD_LOG("BEGIN_RESOLVE %s\n",
+ record->ToDebugString().c_str());
+
if (!target->OnResolvedWithoutChecks(err))
return false;
@@ -572,32 +580,56 @@
}
bool Builder::CompleteItemResolution(BuilderRecord* record, Err* err) {
- record->set_resolved(true);
-
- CheckAndTriggerWrite(record);
+ record->SetResolved();
// Recursively update everybody waiting on this item to be resolved.
- const BuilderRecordSet waiting_deps = record->waiting_on_resolution();
- for (auto it = waiting_deps.begin(); it.valid(); ++it) {
- BuilderRecord* waiting = *it;
- if (waiting->OnResolvedDep(record)) {
- if (!ResolveItem(waiting, err))
- return false;
- }
+ if (!record->NotifyDependentsWaitingOnResolution([&](BuilderRecord* waiting) {
+ DEBUG_BUILDER_RECORD_LOG(" RESOLVE DEP %s -> %s\n",
+ record->ToDebugString().c_str(),
+ waiting->ToDebugString().c_str());
+ return ResolveItem(waiting, err);
+ })) {
+ return false;
}
- 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)) {
- CheckAndTriggerWrite(waiting);
- }
+ if (!record->NotifyDependentsWaitingOnValidationResolution(
+ [&](BuilderRecord* waiting) {
+ DEBUG_BUILDER_RECORD_LOG(" VALRESOLVE DEP %s -> %s\n",
+ record->ToDebugString().c_str(),
+ waiting->ToDebugString().c_str());
+ return FinalizeItem(waiting, err);
+ })) {
+ return false;
}
- record->waiting_on_resolution_for_writing().clear();
+ if (record->can_finalize()) {
+ return FinalizeItem(record, err);
+ }
+
+ DEBUG_BUILDER_RECORD_LOG("END_RESOLVE %s\n", record->ToDebugString().c_str());
+
+ return true;
+}
+
+bool Builder::FinalizeItem(BuilderRecord* record, Err* err) {
+ record->SetFinalized();
+
+ DEBUG_BUILDER_RECORD_LOG("BEGIN_FINALIZE %s\n",
+ record->ToDebugString().c_str());
+ CheckAndTriggerWrite(record);
+
+ if (!record->NotifyDependentsWaitingOnFinalization(
+ [&](BuilderRecord* waiting) {
+ DEBUG_BUILDER_RECORD_LOG(" FINALIZE DEP %s -> %s\n",
+ record->ToDebugString().c_str(),
+ waiting->ToDebugString().c_str());
+ return FinalizeItem(waiting, err);
+ })) {
+ return false;
+ }
+
+ DEBUG_BUILDER_RECORD_LOG("END_FINALIZE %s\n",
+ record->ToDebugString().c_str());
return true;
}
@@ -709,8 +741,9 @@
}
void Builder::CheckAndTriggerWrite(BuilderRecord* record) {
- if (record->resolved() && record->should_generate() && record->can_write() &&
+ if (record->is_finalized() && record->should_generate() &&
resolved_and_generated_callback_) {
+ DEBUG_BUILDER_RECORD_LOG("WRITE %s\n", record->ToDebugString().c_str());
resolved_and_generated_callback_(record);
}
}
diff --git a/src/gn/builder.h b/src/gn/builder.h
index ebff0cc..5e6c88a 100644
--- a/src/gn/builder.h
+++ b/src/gn/builder.h
@@ -127,6 +127,10 @@
void ScheduleBackgroundTargetChecks(BuilderRecord* record);
bool CompleteItemResolution(BuilderRecord* record, Err* err);
+ // Finalizes the given item, scheduling its write to the Ninja file if
+ // should_generate() is true, then notifying all dependents.
+ bool FinalizeItem(BuilderRecord* record, Err* err);
+
// Fills in the pointers in the given vector based on the labels. We assume
// 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.
diff --git a/src/gn/builder_record.cc b/src/gn/builder_record.cc
index ff1a613..5c0b84d 100644
--- a/src/gn/builder_record.cc
+++ b/src/gn/builder_record.cc
@@ -62,20 +62,44 @@
return ITEM_UNKNOWN;
}
-void BuilderRecord::AddDep(BuilderRecord* record) {
- if (all_deps_.add(record) && !record->resolved()) {
- unresolved_count_ += 1;
- record->waiting_on_resolution_.add(this);
+void BuilderRecord::SetDefined(std::unique_ptr<Item> item) {
+ DCHECK(state_ == STATE_INIT);
+ state_ = STATE_DEFINED;
+ item_ = std::move(item);
+}
+
+void BuilderRecord::AddDep(BuilderRecord* dep) {
+ DCHECK(state_ == STATE_DEFINED);
+ all_deps_.add(dep);
+ if (!dep->is_resolved()) {
+ // This cannot be resolved yet if any of its standard dependencies is not
+ // resolved.
+ if (dep->waiting_on_resolution_.add(this)) {
+ unresolved_count_++;
+ DEBUG_BUILDER_RECORD_LOG("-- AddDep waiting_on_resolution %s -> %s\n",
+ dep->ToDebugString().c_str(),
+ this->ToDebugString().c_str());
+ }
+ }
+ if (!dep->is_finalized()) {
+ // Finalization of the current record is blocked until the
+ // dependency is finalized.
+ if (dep->waiting_on_finalization_.add(this)) {
+ unfinalized_count_++;
+ DEBUG_BUILDER_RECORD_LOG("-- AddDep waiting_on_finalization %s -> %s\n",
+ dep->ToDebugString().c_str(),
+ this->ToDebugString().c_str());
+ }
}
}
-void BuilderRecord::AddGenDep(BuilderRecord* record) {
- // Records don't have to wait on resolution of their gen deps, since all they
- // need to do is propagate should_generate to them.
- all_deps_.insert(record);
+void BuilderRecord::AddGenDep(BuilderRecord* dep) {
+ DCHECK(state_ == STATE_DEFINED);
+ all_deps_.insert(dep);
}
-void BuilderRecord::AddValidationDep(BuilderRecord* record) {
+void BuilderRecord::AddValidationDep(BuilderRecord* dep) {
+ DCHECK(state_ == STATE_DEFINED);
// Validation dependencies are treated differently than normal dependencies:
// 1. They are added to all_deps_ for graph traversal (should_generate
// propagation) and error checking.
@@ -84,35 +108,77 @@
// 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);
+ all_deps_.add(dep);
+ if (!dep->is_defined()) {
+ // The record cannot be resolved yet if any of its validation dependencies
+ // is not defined.
+ if (dep->waiting_on_validation_definition_.add(this)) {
+ unresolved_count_++;
+ DEBUG_BUILDER_RECORD_LOG(
+ "-- AddValidationDep waiting_on_validation_definition %s -> %s\n",
+ dep->ToDebugString().c_str(), this->ToDebugString().c_str());
}
- if (!record->resolved()) {
- unresolved_validation_count_ += 1;
- record->waiting_on_resolution_for_writing_.add(this);
+ }
+ if (!dep->is_resolved()) {
+ // This record cannot be finalized if any of its validation deps is not
+ // resolved.
+ if (dep->waiting_on_validation_resolution_.add(this)) {
+ unfinalized_count_++;
+ DEBUG_BUILDER_RECORD_LOG(
+ "-- AddValidationDep waiting_on_validation_resolution %s -> %s\n",
+ dep->ToDebugString().c_str(), this->ToDebugString().c_str());
}
}
}
-bool BuilderRecord::OnDefinedDep(const BuilderRecord* dep) {
+bool BuilderRecord::OnDefinedValidationDep(const BuilderRecord* dep) {
DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
DCHECK(unresolved_count_ > 0);
- return --unresolved_count_ == 0;
+ bool result = (--unresolved_count_ == 0);
+ DEBUG_BUILDER_RECORD_LOG("-- OnDefinedValidationDep %s -> %s result=%d\n",
+ dep->ToDebugString().c_str(),
+ this->ToDebugString().c_str(), result);
+ return result;
+}
+
+void BuilderRecord::SetResolved() {
+ DCHECK(can_resolve());
+ state_ = STATE_RESOLVED;
}
bool BuilderRecord::OnResolvedDep(const BuilderRecord* dep) {
DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
DCHECK(unresolved_count_ > 0);
- return --unresolved_count_ == 0;
+ bool result = (--unresolved_count_ == 0);
+ DEBUG_BUILDER_RECORD_LOG("-- OnResolvedDep %s -> %s result=%d\n",
+ dep->ToDebugString().c_str(),
+ this->ToDebugString().c_str(), result);
+ return result;
}
bool BuilderRecord::OnResolvedValidationDep(const BuilderRecord* dep) {
- DCHECK(validation_deps_.contains(const_cast<BuilderRecord*>(dep)));
- DCHECK(unresolved_validation_count_ > 0);
- return --unresolved_validation_count_ == 0;
+ DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
+ DCHECK(unfinalized_count_ > 0);
+ bool result = (--unfinalized_count_ == 0);
+ DEBUG_BUILDER_RECORD_LOG("-- OnResolvedValidationDep %s -> %s result=%d\n",
+ dep->ToDebugString().c_str(),
+ this->ToDebugString().c_str(), result);
+ return result;
+}
+
+void BuilderRecord::SetFinalized() {
+ DCHECK(can_finalize());
+ state_ = STATE_FINALIZED;
+}
+
+bool BuilderRecord::OnFinalizedDep(const BuilderRecord* dep) {
+ DCHECK(all_deps_.contains(const_cast<BuilderRecord*>(dep)));
+ DCHECK(unfinalized_count_ > 0);
+ bool result = (--unfinalized_count_ == 0);
+ DEBUG_BUILDER_RECORD_LOG("-- OnFinalizedDep %s -> %s result=%d\n",
+ dep->ToDebugString().c_str(),
+ this->ToDebugString().c_str(), result);
+ return result;
}
std::vector<const BuilderRecord*> BuilderRecord::GetSortedUnresolvedDeps()
@@ -122,9 +188,40 @@
BuilderRecord* dep = *it;
if (dep->waiting_on_resolution_.contains(
const_cast<BuilderRecord*>(this)) ||
- dep->waiting_on_definition_.contains(const_cast<BuilderRecord*>(this)))
+ dep->waiting_on_validation_definition_.contains(
+ const_cast<BuilderRecord*>(this)))
result.push_back(dep);
}
std::sort(result.begin(), result.end(), LabelCompare);
return result;
}
+
+#if DEBUG_BUILDER_RECORD
+std::string BuilderRecord::ToDebugString() const {
+ std::string result = label_.GetUserVisibleName(false);
+ result += " (";
+ switch (state_) {
+ case STATE_INIT:
+ result += "INIT";
+ break;
+ case STATE_DEFINED:
+ result += "DEFINED";
+ break;
+ case STATE_RESOLVED:
+ result += "RESOLVED";
+ break;
+ case STATE_FINALIZED:
+ result += "FINALIZED";
+ break;
+ default:
+ result += "UNKNOWN";
+ break;
+ }
+ result += " unresolved=" + std::to_string(unresolved_count_);
+ result += " unfinalized=" + std::to_string(unfinalized_count_);
+ if (should_generate_)
+ result += " generated";
+ result += ")";
+ return result;
+}
+#endif // DEBUG_BUILDER_RECORD
\ No newline at end of file
diff --git a/src/gn/builder_record.h b/src/gn/builder_record.h
index b3b4aba..9c3f0be 100644
--- a/src/gn/builder_record.h
+++ b/src/gn/builder_record.h
@@ -14,23 +14,115 @@
class ParseNode;
-// This class is used by the builder to manage the loading of the dependency
-// tree. It holds a reference to an item and links to other records that the
-// item depends on, both resolved ones, and unresolved ones.
+// Set this to 1 to enable builder record logging during development.
+#define DEBUG_BUILDER_RECORD 0
+
+#if DEBUG_BUILDER_RECORD
+#define DEBUG_BUILDER_RECORD_LOG(fmt, ...) fprintf(stderr, fmt, ##__VA_ARGS__)
+#else // !DEBUG_BUILDER_RECORD
+#define DEBUG_BUILDER_RECORD_LOG(fmt, ...) \
+ do { \
+ } while (0)
+#endif // !DEBUG_BUILDER_RECORD
+
+// This class models what GN knows about labelled items when resolving
+// all dependencies in the configured graph.
//
-// If a target depends on another one that hasn't been defined yet, we'll make
-// a placeholder BuilderRecord with no item, and try to load the buildfile
-// associated with the new item. The item will get filled in when we encounter
-// the declaration for the item (or when we're done and realize there are
-// undefined items).
+// Each BuilderRecord provides information about a given graph item
+// label, that is augmented by the Builder class. It can be in one of
+// the following states, which are taken sequentially, always in the
+// same order.
//
-// You can also have null item pointers when the target is not required for
-// the current build (should_generate is false).
+// Init
+// The record only includes a label, an ItemType and the
+// location where that label was first found in the parse tree
+// (for error reporting). All other fields are empty or should be
+// ignored.
+//
+// Defined
+// An Item instance is also associated with the record, however its
+// content is not final, meaning that its Item::OnResolved() method
+// has not been called yet.
+//
+// Resolved
+// The record's item's OnResolved() method has been called, and the
+// item's state is now final and immutable.
+//
+// Finalized
+// This indicates that the item can be written to the Ninja file.
+//
+// Records can only change state under certain conditions:
+//
+// Init -> Defined:
+// This requires a new Item instance coming from the BUILD.gn
+// evaluator matching the same label. Note that the Item returned
+// by the evaluator is incomplete. In particular its ConfigLabelVector
+// and TargetLabelVector values only contain null pointers, since
+// their labels haven't been resolved yet.
+//
+// Defined -> Resolved:
+// This requires that all standard dependencies are themselves
+// in the Resolved state, and that all validations are in the Defined
+// state.
+//
+// Once this condition is reached, the builder adjusts all label
+// vectors in the Item to point to the right dependency, then
+// the item's OnResolved() method is called.
+//
+// For example Target::OnResolved() performs config propagation,
+// visibility checks, and other computations, then returns the Item
+// in its final state, which cannot include null pointers.
+//
+// Resolved -> Finalized:
+// This requires all standard dependencies to be Finalized, and all
+// validation dependencies to be Resolved. Ensuring that the
+// dependency graph from the root to this item is fully immutable.
+//
+// Every time a record's state is changed, checks are performed to see
+// if the state of other dependents can now be changed accordingly.
+// For example, a Defined target needs to wait for all its dependencies
+// to be Resolved, before changing its own state to Resolved. This is
+// tracked by various counters and sets in the records.
+//
+// The record's should_generate() flag is set to true to indicate that
+// a corresponding Ninja build statement should be generated for the item.
+// By default, it is set to true for all targets defined in BUILD.gn files
+// evaluated in the default toolchain, and only for targets reachable from
+// the root in other toolchains.
+//
+// The Ninja build statement can only be written if the target's record
+// is in the Finalized state.
+//
+// A note on validations:
+//
+// Validation dependencies are a bit special, because they can introduce
+// cycles in the dependency graph. For example, this is valid:
+//
+// foo ------validation------> bar
+// ^ |
+// | |
+// +--------deps------------+
+//
+// In this case, foo can be Resolved as soon as bar is Defined, but
+// won't be Finalized until bar is Resolved itself. This ensures that
+// bar's output path is known when foo is written to the Ninja file,
+// as it is required by the build statement which will look like:
+//
+// build foo.output: some_rule |@ bar.output
+//
+// Ninja doesn't enforce an order for the build statements of foo and
+// bar, but computing `bar.output` can only be done when `bar` is
+// Resolved.
+//
+// Another issue is that metadata walks, performed when writing
+// the build statement for generated_file() targets, will walk over
+// validation dependencies as well. This requires these to be resolved.
+//
class BuilderRecord {
public:
using BuilderRecordSet = PointerSet<BuilderRecord>;
- enum ItemType {
+ enum ItemType : char {
ITEM_UNKNOWN,
ITEM_TARGET,
ITEM_CONFIG,
@@ -38,6 +130,13 @@
ITEM_POOL
};
+ enum RecordState : char {
+ STATE_INIT,
+ STATE_DEFINED,
+ STATE_RESOLVED,
+ STATE_FINALIZED,
+ };
+
BuilderRecord(ItemType type,
const Label& label,
const ParseNode* originally_referenced_from);
@@ -56,7 +155,6 @@
Item* item() { return item_.get(); }
const Item* item() const { return item_.get(); }
- void set_item(std::unique_ptr<Item> item) { item_ = std::move(item); }
// Indicates from where this item was originally referenced from that caused
// it to be loaded. For targets for which we encountered the declaration
@@ -68,13 +166,110 @@
bool should_generate() const { return should_generate_; }
void set_should_generate(bool sg) { should_generate_ = sg; }
- bool resolved() const { return resolved_; }
- void set_resolved(bool r) { resolved_ = r; }
+ // Return true if this record is in the Defined state or a later one.
+ bool is_defined() const { return state_ >= STATE_DEFINED; }
- bool can_resolve() const { return item_ && unresolved_count_ == 0; }
+ // Change the record's state to Defined. This only requires
+ // a new Item instance to be provided. After this, the caller
+ // should call Add{Dep,GenDep,ValidationDep}() for each
+ // dependency type for the Item, then call
+ // NotifyDependentsWaitingOnValidationDefinition().
+ void SetDefined(std::unique_ptr<Item> item);
- bool can_write() const {
- return resolved_ && unresolved_validation_count_ == 0;
+ // After a call to SetDefined()call these methods for each dependency
+ // based on its type. This is later used to control state changes.
+ void AddDep(BuilderRecord* dep_record);
+ void AddGenDep(BuilderRecord* dep_record);
+ void AddValidationDep(BuilderRecord* dep_record);
+
+ // Iterate over all records waiting on this one to be defined, and call
+ // |func| on each one that no longer needs to wait. If |func| returns
+ // false, stop and return false.
+ template <typename Func>
+ bool NotifyDependentsWaitingOnValidationDefinition(Func&& func) {
+ BuilderRecordSet waiting_deps =
+ std::move(waiting_on_validation_definition_);
+ for (auto it = waiting_deps.begin(); it.valid(); ++it) {
+ BuilderRecord* waiting = *it;
+ if (waiting->OnDefinedValidationDep(this) && !func(waiting))
+ return false;
+ }
+ return true;
+ }
+
+ // Returns true if the items has been resolved.
+ bool is_resolved() const { return state_ >= STATE_RESOLVED; }
+
+ // Returns true if the item can be resolved. This requires all its
+ // standard dependencies to be resolved, and all its validations to
+ // be defined.
+ bool can_resolve() const {
+ return state_ == STATE_DEFINED && unresolved_count_ == 0;
+ }
+
+ // Change the record's state to Resolved. This requires can_resolve()
+ // to be true.
+ //
+ // IMPORTANT: Caller should then call Add{Dep,GenDep,ValidationDep}()
+ // for each dependency of the current item, then call
+ // NotifyDependentsWaitingOnResolution() and
+ // NotifyDependentsWaitingOnValidationResolution().
+ void SetResolved();
+
+ // Iterate over all records waiting on this one to be resolved, and call
+ // |func| on each one that no longer needs to wait. If |func| returns false,
+ // stop and return false.
+ template <typename Func>
+ bool NotifyDependentsWaitingOnResolution(Func&& func) {
+ BuilderRecordSet waiting_deps = std::move(waiting_on_resolution_);
+ for (auto it = waiting_deps.begin(); it.valid(); ++it) {
+ BuilderRecord* waiting = *it;
+ if (waiting->OnResolvedDep(this) && !func(waiting))
+ return false;
+ }
+ return true;
+ }
+
+ // Iterate over all records waiting on this one to be resolved as a
+ // validation, and call |func| on each one that no longer needs to wait. If
+ // |func| returns false, stop and return false.
+ template <typename Func>
+ bool NotifyDependentsWaitingOnValidationResolution(Func&& func) {
+ BuilderRecordSet waiting_deps =
+ std::move(waiting_on_validation_resolution_);
+ for (auto it = waiting_deps.begin(); it.valid(); ++it) {
+ BuilderRecord* waiting = *it;
+ if (waiting->OnResolvedValidationDep(this) && !func(waiting))
+ return false;
+ }
+ return true;
+ }
+
+ // Return true if this record has been finalized.
+ bool is_finalized() const { return state_ >= STATE_FINALIZED; }
+
+ // Return true if this record can be finalized.
+ bool can_finalize() const {
+ return state_ == STATE_RESOLVED && unfinalized_count_ == 0 &&
+ unresolved_count_ == 0;
+ }
+
+ // Change the state to Finalized. This requires can_finalize() to be true.
+ // Callers should then call NotifyDependentsWaitingOnFinalization().
+ void SetFinalized();
+
+ // Iterate over all records waiting on this one to be finalized, and call
+ // |func| on each one that no longer needs to wait. If |func| returns false,
+ // stop and return false.
+ template <typename Func>
+ bool NotifyDependentsWaitingOnFinalization(Func&& func) {
+ BuilderRecordSet waiting_deps = std::move(waiting_on_finalization_);
+ for (auto it = waiting_deps.begin(); it.valid(); ++it) {
+ BuilderRecord* waiting = *it;
+ if (waiting->OnFinalizedDep(this) && !func(waiting))
+ return false;
+ }
+ return true;
}
// All records this one is depending on. Note that this includes gen_deps for
@@ -89,9 +284,11 @@
// Records that are waiting on this one to be defined. This is used for
// "validations" dependencies which don't require the target to be fully
// resolved, only defined.
- BuilderRecordSet& waiting_on_definition() { return waiting_on_definition_; }
- const BuilderRecordSet& waiting_on_definition() const {
- return waiting_on_definition_;
+ BuilderRecordSet& waiting_on_validation_definition() {
+ return waiting_on_validation_definition_;
+ }
+ const BuilderRecordSet& waiting_on_validation_definition() const {
+ return waiting_on_validation_definition_;
}
// Records that are waiting on this one to be resolved. This is the other
@@ -103,56 +300,67 @@
// 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_;
+ BuilderRecordSet& waiting_on_validation_resolution() {
+ return waiting_on_validation_resolution_;
}
- const BuilderRecordSet& waiting_on_resolution_for_writing() const {
- return waiting_on_resolution_for_writing_;
+ const BuilderRecordSet& waiting_on_validation_resolution() const {
+ return waiting_on_validation_resolution_;
}
- // 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);
-
- // Call this method to notify the record that its dependency |dep| was
- // just defined. This returns true to indicate that the current record
- // should now be resolved.
- bool OnDefinedDep(const BuilderRecord* dep);
-
- // Call this method to notify the record that its dependency |dep| was
- // just resolved. This returns true to indicate that the current record
- // 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_;
}
+ // Create debug string describing this record.
+ std::string ToDebugString() const;
+
private:
+ // Called by NotifyDependentsWaitingOnXXX() methods. This should update
+ // the counters and return true if the record is no longer waiting for
+ // its dependents and can change state.
+ bool OnDefinedValidationDep(const BuilderRecord* dep);
+ bool OnResolvedDep(const BuilderRecord* dep);
+ bool OnResolvedValidationDep(const BuilderRecord* dep);
+ bool OnFinalizedDep(const BuilderRecord* dep);
+
+ RecordState state_ = STATE_INIT;
ItemType type_;
bool should_generate_ = false;
- bool resolved_ = false;
Label label_;
std::unique_ptr<Item> item_;
const ParseNode* originally_referenced_from_ = nullptr;
+ // The number of dependencies preventing this record from being resolved.
+ // This is the sum of two numbers:
+ //
+ // - The number of unresolved standard dependencies this record is
+ // waiting for. For each such dep, dep[record].waiting_on_resolution_
+ // contains 'this'.
+ //
+ // - The number of undefined validation dependencies this record is
+ // waiting for. For each such dep, dep[record].waiting_on_definition_
+ // contains 'this'.
+ //
size_t unresolved_count_ = 0;
- size_t unresolved_validation_count_ = 0;
+
+ // The number of dependencies preventing this record from being finalized.
+ // This is the sum of two numbers:
+ //
+ // - The numnber of unfinalized standard dependencies this record is
+ // waiting for. For each such dep, dep[record].waiting_on_finalization_
+ // contains 'this'.
+ //
+ // - The number of unresolved validation dependencies this record is
+ // waiting for. For each such dep,
+ // dep[record].waiting_on_validation_resolution_ contains |this|.
+ size_t unfinalized_count_ = 0;
+
BuilderRecordSet all_deps_;
- BuilderRecordSet validation_deps_;
BuilderRecordSet waiting_on_resolution_;
- BuilderRecordSet waiting_on_definition_;
- BuilderRecordSet waiting_on_resolution_for_writing_;
+ BuilderRecordSet waiting_on_finalization_;
+ BuilderRecordSet waiting_on_validation_definition_;
+ BuilderRecordSet waiting_on_validation_resolution_;
BuilderRecord(const BuilderRecord&) = delete;
BuilderRecord& operator=(const BuilderRecord&) = delete;
diff --git a/src/gn/builder_unittest.cc b/src/gn/builder_unittest.cc
index 68f365e..990cb35 100644
--- a/src/gn/builder_unittest.cc
+++ b/src/gn/builder_unittest.cc
@@ -127,13 +127,15 @@
// A should be unresolved with an item
BuilderRecord* a_record = builder_.GetRecord(a_label);
EXPECT_TRUE(a_record->item());
- EXPECT_FALSE(a_record->resolved());
+ EXPECT_TRUE(a_record->is_defined());
+ EXPECT_FALSE(a_record->is_resolved());
EXPECT_FALSE(a_record->can_resolve());
// B should be unresolved, have no item, and no deps.
BuilderRecord* b_record = builder_.GetRecord(b_label);
EXPECT_FALSE(b_record->item());
- EXPECT_FALSE(b_record->resolved());
+ EXPECT_FALSE(b_record->is_defined());
+ EXPECT_FALSE(b_record->is_resolved());
EXPECT_FALSE(b_record->can_resolve());
EXPECT_TRUE(b_record->all_deps().empty());
@@ -175,9 +177,9 @@
// All targets should now be resolved.
BuilderRecord* c_record = builder_.GetRecord(c_label);
- EXPECT_TRUE(a_record->resolved());
- EXPECT_TRUE(b_record->resolved());
- EXPECT_TRUE(c_record->resolved());
+ EXPECT_TRUE(a_record->is_resolved());
+ EXPECT_TRUE(b_record->is_resolved());
+ EXPECT_TRUE(c_record->is_resolved());
EXPECT_TRUE(a_record->GetSortedUnresolvedDeps().empty());
EXPECT_TRUE(b_record->GetSortedUnresolvedDeps().empty());
@@ -209,6 +211,11 @@
BuilderRecord* c_record = builder_.GetOrCreateRecordForTesting(c_label);
BuilderRecord* d_record = builder_.GetOrCreateRecordForTesting(d_label);
+ // Set A's state to Defined as this is required by AddDep() to know
+ // which kind of update to perform internally. Don't provide an Item
+ // though, as this test doesn't need it.
+ a_record->SetDefined(nullptr);
+
a_record->AddDep(b_record);
a_record->AddDep(d_record);
a_record->AddDep(c_record);
@@ -404,7 +411,7 @@
// A should NOT be resolved yet (waiting for B definition).
BuilderRecord* a_record = builder_.GetRecord(a_label);
EXPECT_TRUE(a_record);
- EXPECT_FALSE(a_record->resolved());
+ EXPECT_FALSE(a_record->is_resolved());
// Define B. B depends on A.
auto b = std::make_unique<Target>(&settings_, b_label);
@@ -417,9 +424,9 @@
scheduler().Run();
// Now both should be resolved.
- EXPECT_TRUE(a_record->resolved());
+ EXPECT_TRUE(a_record->is_resolved());
BuilderRecord* b_record = builder_.GetRecord(b_label);
- EXPECT_TRUE(b_record->resolved());
+ EXPECT_TRUE(b_record->is_resolved());
// There should be no cycle.
Err err;
@@ -431,7 +438,7 @@
EXPECT_EQ(b_ptr, a_ptr->validations()[0].ptr);
}
-// Tests that validation dependencies block writing until resolved.
+// Tests that validation dependencies block finalization until resolved.
TEST_F(BuilderTest, ValidationsBlockWriting) {
DefineToolchain();
SourceDir toolchain_dir = settings_.toolchain_label().dir();
@@ -458,19 +465,22 @@
// 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
+ // definition for resolution). BUT A should not be FINALIZED because B
// is not resolved.
BuilderRecord* a_record = builder_.GetRecord(a_label);
BuilderRecord* b_record = builder_.GetRecord(b_label);
+ BuilderRecord* c_record = builder_.GetRecord(c_label);
scheduler().Run();
- EXPECT_TRUE(a_record->resolved());
- EXPECT_FALSE(b_record->resolved());
+ EXPECT_FALSE(c_record->is_resolved());
+ EXPECT_FALSE(b_record->is_resolved());
+ EXPECT_TRUE(a_record->is_resolved());
+ EXPECT_FALSE(a_record->is_finalized());
// Check that B knows A is waiting on it for writing.
- EXPECT_TRUE(b_record->waiting_on_resolution_for_writing().contains(a_record));
+ EXPECT_TRUE(b_record->waiting_on_validation_resolution().contains(a_record));
}
// Tests that a target can validate a target that depends on it.
@@ -504,8 +514,8 @@
scheduler().Run();
// Both should be resolved.
- EXPECT_TRUE(a_record->resolved());
- EXPECT_TRUE(b_record->resolved());
+ EXPECT_TRUE(a_record->is_resolved());
+ EXPECT_TRUE(b_record->is_resolved());
// There should be no errors (cycle detection passed).
Err err;
@@ -517,7 +527,7 @@
// 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.
+// Sequence: C finalizes. A should NOT be finalized. B resolves. A is finalized.
TEST_F(BuilderTest, ValidationsPrematureWrite) {
DefineToolchain();
SourceDir toolchain_dir = settings_.toolchain_label().dir();
@@ -546,18 +556,21 @@
c->visibility().SetPublic();
builder_.ItemDefined(std::move(c));
- // C should resolve. A is waiting on B.
+ // C should resolve then finalize. 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());
+ EXPECT_TRUE(c_record->is_resolved());
+ EXPECT_TRUE(c_record->is_finalized());
+ EXPECT_FALSE(a_record->is_resolved());
// Only C should be written.
ASSERT_EQ(1u, written.size());
EXPECT_EQ(c_record, written[0]);
+ EXPECT_TRUE(c_record->is_finalized());
+ EXPECT_FALSE(a_record->is_finalized());
// Define B.
auto b = std::make_unique<Target>(&settings_, b_label);
@@ -568,7 +581,8 @@
scheduler().Run();
- EXPECT_TRUE(a_record->resolved());
+ EXPECT_TRUE(a_record->is_resolved());
+ EXPECT_TRUE(a_record->is_finalized());
// Order should be C, B, A.
ASSERT_EQ(3u, written.size());
@@ -617,14 +631,14 @@
builder_.ItemDefined(std::move(b));
BuilderRecord* b_record = builder_.GetRecord(b_label);
- // A resolves (validations don't block resolution).
+ // A resolves (validations don't block resolution) but does not finalize.
// B waits for E.
scheduler().Run();
- EXPECT_TRUE(a_record->resolved());
- EXPECT_FALSE(b_record->resolved());
- EXPECT_FALSE(a_record->can_write());
+ EXPECT_TRUE(a_record->is_resolved());
+ EXPECT_FALSE(a_record->is_finalized());
EXPECT_FALSE(a_record->should_generate());
+ EXPECT_FALSE(b_record->is_resolved());
EXPECT_TRUE(written.empty());
// Define C depending on A.
@@ -641,9 +655,12 @@
EXPECT_TRUE(c_record->should_generate());
EXPECT_TRUE(a_record->should_generate());
- // Only C should be written now.
- std::vector<const BuilderRecord*> expected_c = {c_record};
- EXPECT_EQ(expected_c, written);
+ // C cannot be written because A is not finalized.
+ EXPECT_TRUE(c_record->is_resolved());
+ EXPECT_FALSE(c_record->is_finalized());
+
+ // Nothing could be written for now.
+ EXPECT_EQ(written.size(), 0u);
// Define E to cause B to resolve and write A.
auto e = std::make_unique<Target>(&settings_, e_label);
@@ -654,11 +671,22 @@
scheduler().Run();
- // B writes (resolved), then A writes (unblocked).
- // C was already written.
- std::vector<const BuilderRecord*> expected_final = {c_record, e_record,
- b_record, a_record};
- EXPECT_EQ(expected_final, written);
+ // Due to the way the Builder is implemented, here's what happens:
+ //
+ // E is resolved, notifies B immediately.
+ // B is resolved, notifies A immediately.
+ // A is finalized, writes, notifies C
+ // C writes.
+ // A returns from finalization.
+ // B returns from resolution.
+ // E returns from resolution.
+ // E finalizes, notifies B
+ // B finalizes.
+ ASSERT_EQ(written.size(), 4u);
+ EXPECT_EQ(written[0], a_record);
+ EXPECT_EQ(written[1], c_record);
+ EXPECT_EQ(written[2], e_record);
+ EXPECT_EQ(written[3], b_record);
}
} // namespace gn_builder_unittest
