GN: (HeaderChecker) Allow any chain to forward direct dependent configs.

tools/gn/header_checker.cc

Index: tools/gn/header_checker.cc
diff --git a/tools/gn/header_checker.cc b/tools/gn/header_checker.cc
index 62a0f44d580baa41a03d2938fd6f36dc0b7d6ba7..29e0d485495e84e5fde51a4030e9b9ecc60c3189 100644
--- a/tools/gn/header_checker.cc
+++ b/tools/gn/header_checker.cc
@@ -274,6 +274,7 @@ bool HeaderChecker::CheckInclude(const Target* from_target,
 
   const TargetVector& targets = found->second;
   std::vector<const Target*> chain;  // Prevent reallocating in the loop.
+  bool direct_dependent_configs_apply = false;
 
   // For all targets containing this file, we require that at least one be
   // a dependency of the current target, and all targets that are dependencies
@@ -286,7 +287,13 @@ bool HeaderChecker::CheckInclude(const Target* from_target,
     if (to_target == from_target)
       return true;
 
-    if (IsDependencyOf(to_target, from_target, &chain)) {
+    bool has_direct_dependent_compiler_settings =
+        HasDirectDependentCompilerSettings(to_target);
+    if (IsDependencyOf(to_target,
+                       from_target,
+                       has_direct_dependent_compiler_settings,
+                       &chain,
+                       &direct_dependent_configs_apply)) {
       DCHECK(chain.size() >= 2);
       DCHECK(chain[0] == to_target);
       DCHECK(chain[chain.size() - 1] == from_target);
@@ -318,9 +325,10 @@ bool HeaderChecker::CheckInclude(const Target* from_target,
 
       // If the to_target has direct_dependent_configs, they must apply to the
       // from_target.
-      if (HasDirectDependentCompilerSettings(to_target)) {
-        size_t problematic_index;
-        if (!DoDirectDependentConfigsApply(chain, &problematic_index)) {
+      if (has_direct_dependent_compiler_settings &&
+          !direct_dependent_configs_apply) {
+        size_t problematic_index = GetDependentConfigChainProblemIndex(chain);
+        if (!direct_dependent_configs_apply) {
           *err = Err(CreatePersistentRange(source_file, range),
                      "Can't include this header from here.",
                      GetDependentConfigChainError(chain, problematic_index));
@@ -373,33 +381,67 @@ bool HeaderChecker::CheckInclude(const Target* from_target,
 
 bool HeaderChecker::IsDependencyOf(const Target* search_for,
                                    const Target* search_from,
-                                   std::vector<const Target*>* chain) const {
-  std::set<const Target*> checked;
-  return IsDependencyOf(search_for, search_from, chain, &checked);
+                                   bool prefer_direct_dependent_configs,
+                                   std::vector<const Target*>* chain,
+                                   bool* direct_dependent_configs_apply) const {
+  if (search_for == search_from)
+    return false;
+
+  // Find the shortest path that forwards dependent configs, if one exists.
+  if (prefer_direct_dependent_configs &&
+      IsDependencyOf(search_for, search_from, true, chain)) {
+    if (direct_dependent_configs_apply)
+      *direct_dependent_configs_apply = true;
+    return true;
+  }
+
+  // If not, try to find any dependency path at all.
+  if (IsDependencyOf(search_for, search_from, false, chain)) {
+    if (direct_dependent_configs_apply)
+      *direct_dependent_configs_apply = false;
+    return true;
+  }
+
+  return false;
 }
 
 bool HeaderChecker::IsDependencyOf(const Target* search_for,
                                    const Target* search_from,
-                                   std::vector<const Target*>* chain,
-                                   std::set<const Target*>* checked) const {
-  if (checked->find(search_for) != checked->end())
-    return false;  // Already checked this subtree.
-
-  const LabelTargetVector& deps = search_from->deps();
-  for (size_t i = 0; i < deps.size(); i++) {
-    if (deps[i].ptr == search_for) {
-      // Found it.
+                                   bool requires_dependent_configs,
+                                   std::vector<const Target*>* chain) const {
+  // This maps targets to the target which receives dependent configs from it.

[brettw, 2014/07/31 20:50:49]

I'm a bit confused about this function. Rather than have me stare at it some
more, let's try to comment it so I don't have to...

The breadcrumbs maps one target to another target, which I find surprising and
could use some explanation. I also think a quick high-level overview of how the
algorithm works above the work queue declaration might be nice.

[jbroman, 2014/07/31 22:05:37]

It maps targets to their predecessor in a shortest path from search_from.
e.g. if the entire dependency graph is: search_from -> T1 -> T2 -> search_for

Then breadcrumbs will ultimately be { search_for -> T2,  T2 -> T1, T1 ->
search_from }.

Added a comment which I hope clarifies things. I think working in Blink has
messed up my threshold for commenting. :)

+  std::map<const Target*, const Target*> breadcrumbs;
+  std::queue<const Target*> work_queue;
+  breadcrumbs.insert(std::make_pair(
+      search_from, static_cast<const Target*>(NULL)));

[brettw, 2014/07/31 20:50:49]

I see you add this to make the reconstruction step below terminate, but it would
be nice if this was covered in the above comments.

[jbroman, 2014/07/31 22:05:37]

It's unnecessarily clever. I can just make getting back to search_from the loop
exit condition, and then explicitly push search_from at the end. No need for a
sentinel that way. :)

+  work_queue.push(search_from);
+
+  while (!work_queue.empty()) {
+    const Target* target = work_queue.front();
+    work_queue.pop();
+
+    if (target == search_for) {
+      // Found it! Reconstruct the chain.
       chain->clear();
-      chain->push_back(deps[i].ptr);
-      chain->push_back(search_from);
+      while (target) {
+        chain->push_back(target);
+        target = breadcrumbs[target];
+      }
       return true;
     }
 
-    // Recursive search.
-    checked->insert(deps[i].ptr);
-    if (IsDependencyOf(search_for, deps[i].ptr, chain, checked)) {
-      chain->push_back(search_from);
-      return true;
+    // All deps of a group implicitly forward dependent configs.
+    bool uses_all_deps = !requires_dependent_configs ||
+        target == search_from ||
+        target->output_type() == Target::GROUP;
+
+    const LabelTargetVector& deps = uses_all_deps ? target->deps() :
+        target->forward_dependent_configs();
+    for (size_t i = 0; i < deps.size(); i++) {
+      bool seeing_for_first_time = breadcrumbs.insert(
+          std::make_pair(deps[i].ptr, target)).second;
+      if (seeing_for_first_time)
+        work_queue.push(deps[i].ptr);
     }
   }
 
@@ -407,24 +449,18 @@ bool HeaderChecker::IsDependencyOf(const Target* search_for,
 }
 
 // static
-bool HeaderChecker::DoDirectDependentConfigsApply(
-    const std::vector<const Target*>& chain,
-    size_t* problematic_index) {
+size_t HeaderChecker::GetDependentConfigChainProblemIndex(
+    const std::vector<const Target*>& chain)
+{
   // Direct dependent configs go up the chain one level with the following
   // exceptions:
   // - Skip over groups
   // - Skip anything that explicitly forwards it
 
-  // All chains should be at least two (or it wouldn't be a chain).
-  DCHECK(chain.size() >= 2);
-
-  // A chain of length 2 is always OK as far as direct dependent configs are
-  // concerned since the targets are direct dependents.
-  if (chain.size() == 2)
-    return true;
+  // Chains of length less than three have no problems.
+  // These should have been filtered out earlier.
+  DCHECK(chain.size() >= 3);
 
-  // Check the middle configs to make sure they're either groups or configs
-  // are forwarded.
   for (size_t i = 1; i < chain.size() - 1; i++) {
     if (chain[i]->output_type() == Target::GROUP)
       continue;  // This one is OK, skip to next one.
@@ -434,11 +470,10 @@ bool HeaderChecker::DoDirectDependentConfigsApply(
     const LabelTargetVector& forwarded = chain[i]->forward_dependent_configs();
     if (std::find_if(forwarded.begin(), forwarded.end(),
                      LabelPtrPtrEquals<Target>(chain[i - 1])) ==
-        forwarded.end()) {
-      *problematic_index = i;
-      return false;
-    }
+        forwarded.end())
+      return i;
   }
 
-  return true;
+  CHECK(false) << "Unable to diagnose dependent config chain problem.";
+  return 0;
 }