// 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 "gn/header_checker.h"

#include <algorithm>

#include "base/containers/queue.h"
#include "base/files/file_util.h"
#include "base/strings/string_util.h"
#include "gn/build_settings.h"
#include "gn/builder.h"
#include "gn/c_include_iterator.h"
#include "gn/config.h"
#include "gn/config_values_extractors.h"
#include "gn/err.h"
#include "gn/filesystem_utils.h"
#include "gn/hash_table_base.h"
#include "gn/scheduler.h"
#include "gn/swift_values.h"
#include "gn/target.h"
#include "gn/trace.h"
#include "util/worker_pool.h"

// This class includes a list of all known files in the build and which targets
// they are in. When CheckFile is called, it identifies which targets the file
// is in. If it is in at least one binary target (like a static or shared
// library, but not a config or an action), then the toolchain is following
// the rules.
//
// The rules are:
//    1. A target lists a header as public (the default) or private (detected
//       properly).
//
//    2. A target lists a header as private. Then another target depends on the
//       first target. The second target cannot include the private header.
//       This is the more advanced check.
//
//    3. A target lists a header as public (the default). Then another target
//       depends on the first target. The second target can include the public
//       header.
//
//    4. A target lists a header. Another target that does not depend on the
//       first target cannot include the header.
//
namespace {

struct PublicGeneratedPair {
  PublicGeneratedPair() : is_public(false), is_generated(false) {}
  bool is_public;
  bool is_generated;
};

// This class makes InputFiles on the stack as it reads files to check. When
// we throw an error, the Err indicates a locatin which has a pointer to
// an InputFile that must persist as long as the Err does.
//
// To make this work, this function creates a clone of the InputFile managed
// by the InputFileManager so the error can refer to something that
// persists. This means that the current file contents will live as long as
// the program, but this is OK since we're erroring out anyway.
LocationRange CreatePersistentRange(const InputFile& input_file,
                                    const LocationRange& range) {
  InputFile* clone_input_file;
  std::vector<Token>* tokens;              // Don't care about this.
  std::unique_ptr<ParseNode>* parse_root;  // Don't care about this.

  g_scheduler->input_file_manager()->AddDynamicInput(
      input_file.name(), &clone_input_file, &tokens, &parse_root);
  clone_input_file->SetContents(input_file.contents());

  return LocationRange(Location(clone_input_file, range.begin().line_number(),
                                range.begin().column_number()),
                       Location(clone_input_file, range.end().line_number(),
                                range.end().column_number()));
}

// Given a reverse dependency chain where the target chain[0]'s includes are
// being used by chain[end] and not all deps are public, returns the string
// describing the error.
std::string GetDependencyChainPublicError(const HeaderChecker::Chain& chain) {
  std::string ret =
      "The target:\n  " +
      chain[chain.size() - 1].target->label().GetUserVisibleName(false) +
      "\nis including a file from the target:\n  " +
      chain[0].target->label().GetUserVisibleName(false) + "\n";

  // Invalid chains should always be 0 (no chain) or more than two
  // (intermediate private dependencies). 1 and 2 are impossible because a
  // target can always include headers from itself and its direct dependents.
  DCHECK(chain.size() != 1 && chain.size() != 2);
  if (chain.empty()) {
    ret += "There is no dependency chain between these targets.";
  } else {
    // Indirect dependency chain, print the chain.
    const Target* strict_target = nullptr;
    for (size_t i = 1; i < chain.size() - 1; i++) {
      if (chain[i].target->check_includes_strict()) {
        strict_target = chain[i].target;
        break;
      }
    }

    if (strict_target) {
      ret +=
          "\nPlease depend directly on the destination target.\n"
          "Including headers from the public_deps of " +
          strict_target->label().GetUserVisibleName(false) +
          " is blocked because check_includes_strict = true is enabled on it.\n"
          "check_includes_strict = true is highly recommended for all new code "
          "to ensure a correct build graph.\n";
    } else {
      ret +=
          "\nIt's usually best to depend directly on the destination target.\n"
          "In some cases, the destination target is considered a subcomponent\n"
          "of an intermediate target. In this case, the intermediate target\n"
          "should depend publicly on the destination to forward the ability\n"
          "to include headers.\n";
    }
    ret += "\nDependency chain (there may also be others):\n";

    for (int i = static_cast<int>(chain.size()) - 1; i >= 0; i--) {
      ret.append("  " + chain[i].target->label().GetUserVisibleName(false));
      if (i != 0) {
        // Identify private dependencies so the user can see where in the
        // dependency chain things went bad. Don't list this for the first link
        // in the chain since direct dependencies are OK, and listing that as
        // "private" may make people feel like they need to fix it.
        if (i == static_cast<int>(chain.size()) - 1 || chain[i - 1].is_public) {
          if (i != static_cast<int>(chain.size()) - 1 &&
              chain[i].target->check_includes_strict()) {
            ret.append(" --[check_includes_strict = true]-->");
          } else {
            ret.append(" -->");
          }
        } else {
          ret.append(" --[private]-->");
        }
      }
      ret.append("\n");
    }
  }
  return ret;
}

// Returns true if the two targets have the same label not counting the
// toolchain.
bool TargetLabelsMatchExceptToolchain(const Target* a, const Target* b) {
  return a->label().dir() == b->label().dir() &&
         a->label().name() == b->label().name();
}

// Returns true if the target |annotation_on| includes a friend annotation
// that allows |is_marked_friend| as a friend.
bool FriendMatches(const Target* annotation_on,
                   const Target* is_marked_friend) {
  return LabelPattern::VectorMatches(annotation_on->friends(),
                                     is_marked_friend->label());
}

}  // namespace

HeaderChecker::HeaderChecker(const BuildSettings* build_settings,
                             const std::vector<const Target*>& targets,
                             bool check_generated,
                             bool check_system)
    : build_settings_(build_settings),
      check_generated_(check_generated),
      check_system_(check_system),
      errors_lock_(),
      task_count_cv_() {
  for (auto* target : targets)
    AddTargetToFileMap(target, &file_map_);
}

HeaderChecker::~HeaderChecker() = default;

bool HeaderChecker::Run(const std::vector<const Target*>& to_check,
                        bool force_check,
                        std::vector<Violation>* violations) {
  FileMap files_to_check;
  for (auto* check : to_check) {
    // This function will get called with all target types, but check only
    // applies to binary targets.
    if (check->IsBinary())
      AddTargetToFileMap(check, &files_to_check);
  }

  WorkerPool pool;
  {
    ScopedTrace precompute_trace(TraceItem::TRACE_CHECK_HEADERS,
                                 "Precompute reachability");
    std::set<const Target*> targets_to_precompute;
    for (const auto& file : files_to_check) {
      for (const auto& target_info : file.second) {
        if (target_info.target->check_includes())
          targets_to_precompute.insert(target_info.target);
      }
    }

    if (!targets_to_precompute.empty()) {
      task_count_.Increment();
      for (const auto* target : targets_to_precompute) {
        task_count_.Increment();
        pool.PostTask([this, target]() {
          ReachabilityCache& cache = GetReachabilityCacheForTarget(target);
          cache.PerformDependencyWalk(true);
          cache.PerformDependencyWalk(false);
          if (!task_count_.Decrement()) {
            std::unique_lock<std::mutex> lock(task_count_lock_);
            task_count_cv_.notify_one();
          }
        });
      }

      if (!task_count_.Decrement()) {
        std::unique_lock<std::mutex> lock(task_count_lock_);
        task_count_cv_.notify_one();
      }

      std::unique_lock<std::mutex> lock(task_count_lock_);
      while (!task_count_.IsZero())
        task_count_cv_.wait(lock);
    }
  }

  RunCheckOverFiles(files_to_check, force_check, &pool);

  if (violations_.empty())
    return true;
  if (violations)
    *violations = violations_;
  return false;
}

void HeaderChecker::RunCheckOverFiles(const FileMap& files,
                                      bool force_check,
                                      WorkerPool* pool) {
  task_count_.Increment();

  for (const auto& file : files) {
    // Only check C-like source files (RC files also have includes).
    const SourceFile::Type type = file.first.GetType();
    if (type != SourceFile::SOURCE_CPP && type != SourceFile::SOURCE_H &&
        type != SourceFile::SOURCE_C && type != SourceFile::SOURCE_M &&
        type != SourceFile::SOURCE_MM && type != SourceFile::SOURCE_RC)
      continue;

    if (!check_generated_) {
      // If any target marks it as generated, don't check it. We have to check
      // file_map_, which includes all known files; files only includes those
      // being checked.
      bool is_generated = false;
      for (const auto& vect_i : file_map_[file.first])
        is_generated |= vect_i.is_generated;
      if (is_generated)
        continue;
    }

    TargetVector targets_to_check;
    for (const auto& vect_i : file.second) {
      if (vect_i.target->check_includes()) {
        targets_to_check.push_back(vect_i);
      }
    }
    if (targets_to_check.empty())
      continue;

    task_count_.Increment();
    pool->PostTask([this, targets = std::move(targets_to_check),
                    file = file.first]() { DoWork(targets, file); });
  }

  if (!task_count_.Decrement()) {
    std::unique_lock<std::mutex> lock(task_count_lock_);
    task_count_cv_.notify_one();
  }

  // Wait for all tasks posted by this method to complete.
  std::unique_lock<std::mutex> auto_lock(task_count_lock_);
  while (!task_count_.IsZero())
    task_count_cv_.wait(auto_lock);
}

void HeaderChecker::DoWork(const TargetVector& targets,
                           const SourceFile& file) {
  std::vector<Violation> violations;
  if (!CheckFile(targets, file, &violations)) {
    std::lock_guard<std::mutex> lock(errors_lock_);
    violations_.insert(violations_.end(),
                       std::make_move_iterator(violations.begin()),
                       std::make_move_iterator(violations.end()));
  }

  if (!task_count_.Decrement()) {
    // Signal |task_count_cv_| when |task_count_| becomes zero.
    std::unique_lock<std::mutex> auto_lock(task_count_lock_);
    task_count_cv_.notify_one();
  }
}

// static
void HeaderChecker::AddTargetToFileMap(const Target* target, FileMap* dest) {
  // Files in the sources have this public bit by default.
  bool default_public = target->all_headers_public();

  std::map<SourceFile, PublicGeneratedPair> files_to_public;

  // First collect the normal files, they get the default visibility. If you
  // depend on the compiled target, it should be enough to be able to include
  // the header.
  for (const auto& source : target->sources()) {
    files_to_public[source].is_public = default_public;
  }

  // Add in the public files, forcing them to public. This may overwrite some
  // entries, and it may add new ones.
  if (default_public)  // List only used when default is not public.
    DCHECK(target->public_headers().empty());
  for (const auto& source : target->public_headers()) {
    files_to_public[source].is_public = true;
  }

  // If target generates a swiftmodule, then
  //  - it may use a bridge header which has default visibility
  //  - it may generate public header which must be considered public
  if (target->builds_swift_module()) {
    const SourceFile& bridge_header = target->swift_values().bridge_header();
    if (!bridge_header.is_null()) {
      files_to_public[bridge_header].is_public = default_public;
    }

    std::vector<SourceFile> outputs;
    target->swift_values().GetOutputsAsSourceFiles(target, &outputs);

    for (const SourceFile& output : outputs) {
      if (output.GetType() == SourceFile::SOURCE_H) {
        PublicGeneratedPair* pair = &files_to_public[output];
        pair->is_public = true;
        pair->is_generated = true;
      }
    }
  }

  // Add in outputs from actions. These are treated as public (since if other
  // targets can't use them, then there wouldn't be any point in outputting).
  std::vector<SourceFile> outputs;
  target->action_values().GetOutputsAsSourceFiles(target, &outputs);
  for (const auto& output : outputs) {
    PublicGeneratedPair* pair = &files_to_public[output];
    pair->is_public = true;
    pair->is_generated = true;
  }

  // Add the merged list to the master list of all files.
  for (const auto& cur : files_to_public) {
    (*dest)[cur.first].push_back(
        TargetInfo(target, cur.second.is_public, cur.second.is_generated));
  }
}

bool HeaderChecker::IsFileInOuputDir(const SourceFile& file) const {
  const std::string& build_dir = build_settings_->build_dir().value();
  return file.value().compare(0, build_dir.size(), build_dir) == 0;
}

SourceFile HeaderChecker::SourceFileForInclude(
    const IncludeStringWithLocation& include,
    const std::vector<SourceDir>& include_dirs,
    const InputFile& source_file,
    Err* err) const {
  using base::FilePath;

  Value relative_file_value(nullptr, std::string(include.contents));

  auto find_predicate = [relative_file_value, err,
                         this](const SourceDir& dir) -> bool {
    SourceFile include_file = dir.ResolveRelativeFile(relative_file_value, err);
    return file_map_.find(include_file) != file_map_.end();
  };
  if (!include.system_style_include) {
    const SourceDir& file_dir = source_file.dir();
    if (find_predicate(file_dir)) {
      return file_dir.ResolveRelativeFile(relative_file_value, err);
    }
  }

  auto it =
      std::find_if(include_dirs.begin(), include_dirs.end(), find_predicate);

  if (it != include_dirs.end())
    return it->ResolveRelativeFile(relative_file_value, err);

  return SourceFile();
}

void HeaderChecker::ReachabilityCache::PerformDependencyWalk(bool permitted) {
  // Conduct the actual BFS.
  if (permitted ? permitted_complete_.load(std::memory_order_relaxed)
                : any_complete_.load(std::memory_order_relaxed)) {
    return;
  }

  BreadcrumbTable& breadcrumbs =
      permitted ? permitted_breadcrumbs_ : any_breadcrumbs_;

  // work_queue maintains a queue of targets which need to be considered as part
  // of dependency chain, in the order they were first traversed. Each time a
  // new transitive dependency of source_target_ is discovered for the first
  // time, it is added to work_queue and a "breadcrumb" is added, indicating
  // which target it was reached from when first discovered.
  base::queue<const Target*> work_queue;
  work_queue.push(source_target_);
  breadcrumbs.Insert(source_target_, nullptr, true);

  while (!work_queue.empty()) {
    const Target* target = work_queue.front();
    work_queue.pop();

    if (permitted && target != source_target_ &&
        target->check_includes_strict()) {
      continue;
    }

    for (const auto& dep : target->public_deps()) {
      if (breadcrumbs.Insert(dep.ptr, target, true))
        work_queue.push(dep.ptr);
    }

    if (!permitted || target == source_target_) {
      // Consider all dependencies since all target paths are allowed, so add
      // in private ones. Also do this the first time through the loop, since
      // a target can include headers from its direct deps regardless of
      // public/private-ness.
      for (const auto& dep : target->private_deps()) {
        if (breadcrumbs.Insert(dep.ptr, target, false))
          work_queue.push(dep.ptr);
      }
    }
  }
  if (permitted) {
    permitted_complete_.store(true, std::memory_order_release);
  } else {
    any_complete_.store(true, std::memory_order_release);
  }
}

bool HeaderChecker::ReachabilityCache::SearchForDependencyTo(
    const Target* search_for,
    bool permitted,
    Chain* chain) {
  if (permitted ? permitted_complete_.load(std::memory_order_acquire)
                : any_complete_.load(std::memory_order_acquire)) {
    return SearchBreadcrumbs(search_for, permitted, chain);
  }

  {
    std::unique_lock<std::shared_mutex> write_lock(lock_);
    if (!(permitted ? permitted_complete_.load(std::memory_order_relaxed)
                    : any_complete_.load(std::memory_order_relaxed))) {
      PerformDependencyWalk(permitted);
    }
  }

  return SearchBreadcrumbs(search_for, permitted, chain);
}

bool HeaderChecker::ReachabilityCache::SearchBreadcrumbs(
    const Target* search_for,
    bool permitted,
    Chain* chain) const {
  const BreadcrumbTable& breadcrumbs =
      permitted ? permitted_breadcrumbs_ : any_breadcrumbs_;
  ChainLink incoming_link = breadcrumbs.GetLink(search_for);
  if (!incoming_link.target)
    return false;

  // Found it! Reconstruct the chain.
  chain->clear();
  const Target* cur = search_for;
  while (cur != source_target_) {
    ChainLink link = breadcrumbs.GetLink(cur);
    chain->push_back(ChainLink(cur, link.is_public));
    cur = link.target;
  }
  chain->push_back(ChainLink(source_target_, true));

  return true;
}

bool HeaderChecker::CheckFile(const TargetVector& targets,
                              const SourceFile& file,
                              std::vector<Violation>* violations) const {
  ScopedTrace trace(TraceItem::TRACE_CHECK_HEADER, file.value());

  // Sometimes you have generated source files included as sources in another
  // target. These won't exist at checking time. Since we require all generated
  // files to be somewhere in the output tree, we can just check the name to
  // see if they should be skipped.
  if (!check_generated_ && IsFileInOuputDir(file))
    return true;

  base::FilePath path = build_settings_->GetFullPath(file);
  std::string contents;
  if (!base::ReadFileToString(path, &contents)) {
    // A missing (not yet) generated file is an acceptable problem
    // considering this code does not understand conditional includes.
    if (IsFileInOuputDir(file))
      return true;

    for (const TargetInfo& from_target_info : targets) {
      const Target* from_target = from_target_info.target;
      violations->emplace_back(
          Err(from_target->defined_from(), "Source file not found.",
              "The target:\n  " +
                  from_target->label().GetUserVisibleName(false) +
                  "\nhas a source file:\n  " + file.value() +
                  "\nwhich was not found."),
          file, SourceFile());
    }
    return false;
  }

  InputFile input_file(file);
  input_file.SetContents(contents);

  std::vector<IncludeStringWithLocation> includes;
  CIncludeIterator iter(&input_file);
  IncludeStringWithLocation include;
  while (iter.GetNextIncludeString(&include)) {
    if (include.system_style_include && !check_system_)
      continue;
    includes.push_back(include);
  }

  if (includes.empty())
    return true;

  size_t violations_count_before = violations->size();

  for (const TargetInfo& from_target_info : targets) {
    const Target* from_target = from_target_info.target;
    std::vector<SourceDir> include_dirs;
    for (ConfigValuesIterator target_iter(from_target); !target_iter.done();
         target_iter.Next()) {
      const std::vector<SourceDir>& target_include_dirs =
          target_iter.cur().include_dirs();
      include_dirs.insert(include_dirs.end(), target_include_dirs.begin(),
                          target_include_dirs.end());
    }

    ReachabilityCache& from_target_cache =
        GetReachabilityCacheForTarget(from_target);

    for (const auto& inc : includes) {
      Err err;
      SourceFile included_file =
          SourceFileForInclude(inc, include_dirs, input_file, &err);
      if (!included_file.is_null()) {
        std::vector<Err> include_errors;
        CheckInclude(from_target_cache,
                     from_target_info.is_public &&
                         file.GetType() == SourceFile::SOURCE_H,
                     input_file, included_file, inc.location, &include_errors);
        for (auto& e : include_errors) {
          violations->emplace_back(std::move(e), file,
                                   std::move(included_file));
        }
      }
    }
  }

  return violations->size() == violations_count_before;
}

// If the file exists:
//  - The header must be in the public section of a target, or it must
//    be in the sources with no public list (everything is implicitly public).
//  - The dependency path to the included target must follow only public_deps.
//  - If there are multiple targets with the header in it, only one need be
//    valid for the check to pass.
void HeaderChecker::CheckInclude(ReachabilityCache& from_target_cache,
                                 bool is_public_header,
                                 const InputFile& source_file,
                                 const SourceFile& include_file,
                                 const LocationRange& range,
                                 std::vector<Err>* errors) const {
  // Assume if the file isn't declared in our sources that we don't need to
  // 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;

  const TargetVector& targets = found->second;
  Chain chain;  // Prevent reallocating in the loop.

  const Target* from_target = from_target_cache.source_target();

  // If the file is unknown in the current toolchain (rather than being private
  // or in a target not visible to the current target), ignore it. This is a
  // bit of a hack to account for the fact that the include finder doesn't
  // understand the preprocessor.
  //
  // When not cross-compiling, if a platform specific header is conditionally
  // included in the build, and preprocessor conditions around #includes of
  // that match the build conditions, everything will be OK because the file
  // won't be known to GN even though the #include finder identified the file.
  //
  // Cross-compiling breaks this. When compiling Android on Linux, for example,
  // we might see both Linux and Android definitions of a target and know
  // about the union of all headers in the build. Since the #include finder
  // ignores preprocessor, we will find the Linux headers in the Android
  // build and note that a dependency from the Android target to the Linux
  // one is missing (these might even be the same target in different
  // toolchains!).
  bool present_in_current_toolchain = false;
  for (const auto& target : targets) {
    if (from_target->label().ToolchainsEqual(target.target->label())) {
      present_in_current_toolchain = true;
      break;
    }
  }
  if (!present_in_current_toolchain)
    return;

  // For all targets containing this file, we require that at least one be
  // a direct or public dependency of the current target, and either (1) the
  // header is public within the target, or (2) there is a friend definition
  // allowlisting the includor.
  //
  // If there is more than one target containing this header, we may encounter
  // some error cases before finding a good one. This error stores the previous
  // one encountered, which we may or may not throw away.
  Err last_error;

  bool found_dependency = false;
  for (const auto& target : targets) {
    // We always allow source files in a target to include headers also in that
    // target, unless strict checking is enabled and a public header includes
    // a private header.
    const Target* to_target = target.target;
    if (to_target == from_target) {
      if (from_target->check_includes_strict() && is_public_header &&
          !target.is_public) {
        last_error = Err(
            CreatePersistentRange(source_file, range),
            "Public headers cannot include private headers of the same target.",
            "The public header:\n  " + source_file.name().value() +
                "\nis including a private header of the same target:\n  " +
                include_file.value() +
                "\nEither make the included header public, make the includer "
                "private,\n"
                "or make a source_set containing public = [private_headers] "
                "and add it to public_deps.");
        errors->push_back(std::move(last_error));
      }
      return;
    }

    bool is_permitted_chain = false;
    if (IsDependencyOf(to_target, from_target_cache, &chain,
                       &is_permitted_chain)) {
      DCHECK(chain.size() >= 2);
      DCHECK(chain[0].target == to_target);
      DCHECK(chain[chain.size() - 1].target == from_target);
      found_dependency = true;

      bool effectively_public =
          target.is_public || FriendMatches(to_target, from_target);

      if (effectively_public && is_permitted_chain) {
        if (from_target->check_includes_strict() && is_public_header &&
            !chain[chain.size() - 2].is_public) {
          last_error = Err(
              CreatePersistentRange(source_file, range),
              "Public headers cannot include private dependencies.",
              "The public header:\n  " + source_file.name().value() +
                  "\nis including a header from private dependency:\n  " +
                  to_target->label().GetUserVisibleName(false) +
                  "\nEither move the dependency to public_deps, or make this "
                  "header private.");
          continue;
        }
        // This one is OK, we're done.
        last_error = Err();
        break;
      }

      // Diagnose the error.
      if (!effectively_public) {
        // Danger: must call CreatePersistentRange to put in Err.
        last_error = Err(CreatePersistentRange(source_file, range),
                         "Including a private header.",
                         "This file is private to the target " +
                             target.target->label().GetUserVisibleName(false));
      } else if (!is_permitted_chain) {
        last_error = Err(CreatePersistentRange(source_file, range),
                         "Can't include this header from here.",
                         GetDependencyChainPublicError(chain));
      } else {
        NOTREACHED();
      }
    } else if (to_target->allow_circular_includes_from().find(
                   from_target->label()) !=
               to_target->allow_circular_includes_from().end()) {
      // Not a dependency, but this include is allowlisted from the destination.
      found_dependency = true;
      last_error = Err();
      break;
    }
  }

  if (!found_dependency || last_error.has_error()) {
    if (!found_dependency) {
      DCHECK(!last_error.has_error());
      Err err = MakeUnreachableError(source_file, range, from_target, targets);
      errors->push_back(std::move(err));
    } else {
      // Found at least one dependency chain above, but it had an error.
      errors->push_back(std::move(last_error));
    }
    return;
  }

  // One thing we didn't check for is targets that expose their dependents
  // headers in their own public headers.
  //
  // Say we have A -> B -> C. If C has public_configs, everybody getting headers
  // from C should get the configs also or things could be out-of-sync. Above,
  // we check for A including C's headers directly, but A could also include a
  // header from B that in turn includes a header from C.
  //
  // There are two ways to solve this:
  //  - If a public header in B includes C, force B to publicly depend on C.
  //    This is possible to check, but might be super annoying because most
  //    targets (especially large leaf-node targets) don't declare
  //    public/private headers and you'll get lots of false positives.
  //
  //  - 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.
}

HeaderChecker::ReachabilityCache& HeaderChecker::GetReachabilityCacheForTarget(
    const Target* target) const {
  size_t shard_index = target->label().hash() % kNumShards;
  auto& shard = dependency_cache_[shard_index];
  std::unique_lock<std::shared_mutex> lock(shard.lock);
  auto it = shard.cache.find(target);
  if (it == shard.cache.end()) {
    it =
        shard.cache.emplace(target, std::make_unique<ReachabilityCache>(target))
            .first;
  }
  return *it->second;
}

bool HeaderChecker::IsDependencyOf(const Target* search_for,
                                   ReachabilityCache& from_target_cache,
                                   Chain* chain,
                                   bool* is_permitted) const {
  const Target* search_from = from_target_cache.source_target();
  if (search_for == search_from) {
    // A target is always visible from itself.
    *is_permitted = true;
    return false;
  }

  // 1. Try permitted dependency.
  if (from_target_cache.SearchForDependencyTo(search_for, true, chain)) {
    *is_permitted = true;
    return true;
  }

  // 2. Try any dependency.
  if (from_target_cache.SearchForDependencyTo(search_for, false, chain)) {
    *is_permitted = false;
    return true;
  }

  return false;
}

Err HeaderChecker::MakeUnreachableError(const InputFile& source_file,
                                        const LocationRange& range,
                                        const Target* from_target,
                                        const TargetVector& targets) {
  // Normally the toolchains will all match, but when cross-compiling, we can
  // get targets with more than one toolchain in the list of possibilities.
  std::vector<const Target*> targets_with_matching_toolchains;
  std::vector<const Target*> targets_with_other_toolchains;
  for (const TargetInfo& candidate : targets) {
    if (candidate.target->toolchain() == from_target->toolchain())
      targets_with_matching_toolchains.push_back(candidate.target);
    else
      targets_with_other_toolchains.push_back(candidate.target);
  }

  // It's common when cross-compiling to have a target with the same file in
  // more than one toolchain. We could output all of them, but this is
  // generally confusing to people (most end-users won't understand toolchains
  // well).
  //
  // So delete any candidates in other toolchains that also appear in the same
  // toolchain as the from_target.
  for (int other_index = 0;
       other_index < static_cast<int>(targets_with_other_toolchains.size());
       other_index++) {
    for (const Target* cur_matching : targets_with_matching_toolchains) {
      if (TargetLabelsMatchExceptToolchain(
              cur_matching, targets_with_other_toolchains[other_index])) {
        // Found a duplicate, erase it.
        targets_with_other_toolchains.erase(
            targets_with_other_toolchains.begin() + other_index);
        other_index--;
        break;
      }
    }
  }

  // Only display toolchains on labels if they don't all match.
  bool include_toolchain = !targets_with_other_toolchains.empty();

  std::string msg = "It is not in any dependency of\n  " +
                    from_target->label().GetUserVisibleName(include_toolchain);
  msg += "\nThe include file is in the target(s):\n";
  for (auto* target : targets_with_matching_toolchains)
    msg += "  " + target->label().GetUserVisibleName(include_toolchain) + "\n";
  for (auto* target : targets_with_other_toolchains)
    msg += "  " + target->label().GetUserVisibleName(include_toolchain) + "\n";
  if (targets_with_other_toolchains.size() +
          targets_with_matching_toolchains.size() >
      1)
    msg += "at least one of ";
  msg += "which should somehow be reachable.\n";
  msg +=
      "This might be a false alarm if you are using conditional include. "
      "See \"gn help nogncheck\".";

  // Danger: must call CreatePersistentRange to put in Err.
  return Err(CreatePersistentRange(source_file, range), "Include not allowed.",
             msg);
}