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

tools/gn/header_checker.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "tools/gn/header_checker.h"
 
 #include <algorithm>
 
 #include "base/bind.h"
 #include "base/file_util.h"
@@ skipping 256 matching lines @@
   // check it. It would be nice if we could give an error if this happens, but
   // our include finder is too primitive and returns all includes, even if
   // they're in a #if not executed in the current build. In that case, it's
   // not unusual for the buildfiles to not specify that header at all.
   FileMap::const_iterator found = file_map_.find(include_file);
   if (found == file_map_.end())
     return true;
 
   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
   // must have the file listed in the public section.
   bool found_dependency = false;
   for (size_t i = 0; i < targets.size(); i++) {
     // We always allow source files in a target to include headers also in that
     // target.
     const Target* to_target = targets[i].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);
 
       // The include is in a target that's a proper dependency. Verify that
       // the including target has visibility.
       if (!to_target->visibility().CanSeeMe(from_target->label())) {
         std::string msg = "The included file is in " +
             to_target->label().GetUserVisibleName(false) +
             "\nwhich is not visible from " +
@@ skipping 11 matching lines @@
         // Danger: must call CreatePersistentRange to put in Err.
         *err = Err(CreatePersistentRange(source_file, range),
                    "Including a private header.",
                    "This file is private to the target " +
                        targets[i].target->label().GetUserVisibleName(false));
         return false;
       }
 
       // 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));
           return false;
         }
       }
 
       found_dependency = true;
     }
   }
@@ skipping 32 matching lines @@
   //
   //  - Save the includes found in each file and actually compute the graph of
   //    includes to detect when A implicitly includes C's header. This will not
   //    have the annoying false positive problem, but is complex to write.
 
   return true;
 }
 
 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.
+                                   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);
 
-  const LabelTargetVector& deps = search_from->deps();
-  for (size_t i = 0; i < deps.size(); i++) {
-    if (deps[i].ptr == search_for) {
-      // Found it.
+  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);
     }
   }
 
   return false;
 }
 
 // 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);
+  // Chains of length less than three have no problems.
+  // These should have been filtered out earlier.
+  DCHECK(chain.size() >= 3);
 
-  // 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;
-
-  // 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.
 
     // The forward list on this target should have contained in it the target
     // at the next lower level.
     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;
 }