// Copyright (c) 2013 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/builder.h"

#include "tools/gn/config.h"
#include "tools/gn/err.h"
#include "tools/gn/loader.h"
#include "tools/gn/scheduler.h"
#include "tools/gn/settings.h"
#include "tools/gn/target.h"
#include "tools/gn/trace.h"

namespace {

typedef BuilderRecord::BuilderRecordSet BuilderRecordSet;

// Recursively looks in the tree for a given node, returning true if it
// was found in the dependecy graph. This is used to see if a given node
// participates in a cycle.
//
// If this returns true, the cycle will be in *path. This should point to an
// empty vector for the first call. During computation, the path will contain
// the full dependency path to the current node.
//
// Return false means no cycle was found.
bool RecursiveFindCycle(const BuilderRecord* search_in,
                        std::vector<const BuilderRecord*>* path) {
  path->push_back(search_in);

  const BuilderRecord::BuilderRecordSet& unresolved =
      search_in->unresolved_deps();
  for (BuilderRecord::BuilderRecordSet::const_iterator i = unresolved.begin();
       i != unresolved.end(); ++i) {
    const BuilderRecord* cur = *i;

    std::vector<const BuilderRecord*>::iterator found =
        std::find(path->begin(), path->end(), cur);
    if (found != path->end()) {
      // This item is already in the set, we found the cycle. Everything before
      // the first definition of cur is irrelevant to the cycle.
      path->erase(path->begin(), found);
      path->push_back(cur);
      return true;
    }

    if (RecursiveFindCycle(cur, path))
      return true;  // Found cycle.
  }
  path->pop_back();
  return false;
}

}  // namespace

Builder::Builder(Loader* loader) : loader_(loader) {
}

Builder::~Builder() {
}

void Builder::ItemDefined(scoped_ptr<Item> item) {
  ScopedTrace trace(TraceItem::TRACE_DEFINE_TARGET, item->label());
  trace.SetToolchain(item->settings()->toolchain_label());

  BuilderRecord::ItemType type = BuilderRecord::TypeOfItem(item.get());

  Err err;
  BuilderRecord* record =
      GetOrCreateRecordOfType(item->label(), item->defined_from(), type, &err);
  if (!record) {
    g_scheduler->FailWithError(err);
    return;
  }

  // Check that it's not been already defined.
  if (record->item()) {
    err = Err(item->defined_from(), "Duplicate definition.",
        "The item\n  " + item->label().GetUserVisibleName(false) +
        "\nwas already defined.");
    err.AppendSubErr(Err(record->item()->defined_from(),
                         "Previous definition:"));
    g_scheduler->FailWithError(err);
    return;
  }

  record->set_item(item.Pass());

  // Do target-specific dependency setup. This will also schedule dependency
  // loads for targets that are required.
  switch (type) {
    case BuilderRecord::ITEM_TARGET:
      if (!TargetDefined(record, &err)) {
        g_scheduler->FailWithError(err);
        return;
      }
      break;
    case BuilderRecord::ITEM_TOOLCHAIN:
      loader_->ToolchainLoaded(record->item()->AsToolchain());
      break;
    default:
      break;
  }

  if (record->can_resolve()) {
    if (!ResolveItem(record, &err)) {
      g_scheduler->FailWithError(err);
      return;
    }
  }
}

const Item* Builder::GetItem(const Label& label) const {
  const BuilderRecord* record = GetRecord(label);
  if (!record)
    return NULL;
  return record->item();
}

const Toolchain* Builder::GetToolchain(const Label& label) const {
  const BuilderRecord* record = GetRecord(label);
  if (!record)
    return NULL;
  if (!record->item())
    return NULL;
  return record->item()->AsToolchain();
}

std::vector<const BuilderRecord*> Builder::GetAllRecords() const {
  std::vector<const BuilderRecord*> result;
  result.reserve(records_.size());
  for (RecordMap::const_iterator i = records_.begin();
       i != records_.end(); ++i)
    result.push_back(i->second);
  return result;
}

std::vector<const Target*> Builder::GetAllResolvedTargets() const {
  std::vector<const Target*> result;
  result.reserve(records_.size());
  for (RecordMap::const_iterator i = records_.begin();
       i != records_.end(); ++i) {
    if (i->second->type() == BuilderRecord::ITEM_TARGET &&
        i->second->should_generate() && i->second->item())
      result.push_back(i->second->item()->AsTarget());
  }
  return result;
}

const BuilderRecord* Builder::GetRecord(const Label& label) const {
  // Forward to the non-const version.
  return const_cast<Builder*>(this)->GetRecord(label);
}

BuilderRecord* Builder::GetRecord(const Label& label) {
  RecordMap::iterator found = records_.find(label);
  if (found == records_.end())
    return NULL;
  return found->second;
}

bool Builder::CheckForBadItems(Err* err) const {
  // Look for errors where we find a defined node with an item that refers to
  // an undefined one with no item. There may be other nodes in turn depending
  // on our defined one, but listing those isn't helpful: we want to find the
  // broken link.
  //
  // This finds normal "missing dependency" errors but does not find circular
  // dependencies because in this case all items in the cycle will be GENERATED
  // but none will be resolved. If this happens, we'll check explicitly for
  // that below.
  std::vector<const BuilderRecord*> bad_records;
  std::string depstring;
  for (RecordMap::const_iterator i = records_.begin();
       i != records_.end(); ++i) {
    const BuilderRecord* src = i->second;
    if (!src->should_generate())
      continue;  // Skip ungenerated nodes.

    if (!src->resolved()) {
      bad_records.push_back(src);

      // Check dependencies.
      for (BuilderRecord::BuilderRecordSet::const_iterator dest_iter =
               src->unresolved_deps().begin();
          dest_iter != src->unresolved_deps().end();
          ++dest_iter) {
        const BuilderRecord* dest = *dest_iter;
        if (!dest->item()) {
          depstring += src->label().GetUserVisibleName(true) +
              "\n  needs " + dest->label().GetUserVisibleName(true) + "\n";
        }
      }
    }
  }

  if (!depstring.empty()) {
    *err = Err(Location(), "Unresolved dependencies.", depstring);
    return false;
  }

  if (!bad_records.empty()) {
    // Our logic above found a bad node but didn't identify the problem. This
    // normally means a circular dependency.
    depstring = CheckForCircularDependencies(bad_records);
    if (depstring.empty()) {
      // Something's very wrong, just dump out the bad nodes.
      depstring = "I have no idea what went wrong, but these are unresolved, "
          "possible due to an\ninternal error:";
      for (size_t i = 0; i < bad_records.size(); i++) {
        depstring += "\n\"" +
            bad_records[i]->label().GetUserVisibleName(false) + "\"";
      }
      *err = Err(Location(), "", depstring);
    } else {
      *err = Err(Location(), "Dependency cycle:", depstring);
    }
    return false;
  }

  return true;
}

bool Builder::TargetDefined(BuilderRecord* record, Err* err) {
  Target* target = record->item()->AsTarget();

  if (!AddDeps(record, target->deps(), err) ||
      !AddDeps(record, target->datadeps(), err) ||
      !AddDeps(record, target->configs(), err) ||
      !AddDeps(record, target->all_dependent_configs(), err) ||
      !AddDeps(record, target->direct_dependent_configs(), err) ||
      !AddToolchainDep(record, target, err))
    return false;

  // All targets in the default toolchain get generated by default. We also
  // check if this target was previously marked as "required" and force setting
  // the bit again so the target's dependencies (which we now know) get the
  // required bit pushed to them.
  if (record->should_generate() || target->settings()->is_default())
    RecursiveSetShouldGenerate(record, true);

  return true;
}

BuilderRecord* Builder::GetOrCreateRecordOfType(const Label& label,
                                                const ParseNode* request_from,
                                                BuilderRecord::ItemType type,
                                                Err* err) {
  BuilderRecord* record = GetRecord(label);
  if (!record) {
    // Not seen this record yet, create a new one.
    record = new BuilderRecord(type, label);
    records_[label] = record;
    return record;
  }

  // Check types.
  if (record->type() != type) {
    *err = Err(request_from, "Item type does not match.",
        "The item \"" + label.GetUserVisibleName(false) +
        "\" was expected\nto be a " +
        BuilderRecord::GetNameForType(type) +
        " but was previously\n referenced as a " +
        BuilderRecord::GetNameForType(record->type()));
    err->AppendSubErr(Err(record->originally_referenced_from(),
                          "The previous reference was here."));
    return NULL;
  }

  return record;
}

BuilderRecord* Builder::GetResolvedRecordOfType(const Label& label,
                                                const ParseNode* origin,
                                                BuilderRecord::ItemType type,
                                                Err* err) {
  BuilderRecord* record = GetRecord(label);
  if (!record) {
    *err = Err(origin, "Item not found",
        "\"" + label.GetUserVisibleName(false) + "\" doesn't\n"
        "refer to an existant thing.");
    return NULL;
  }

  const Item* item = record->item();
  if (!item) {
    *err = Err(origin, "Item not resolved.",
        "\"" + label.GetUserVisibleName(false) + "\" hasn't been resolved.\n");
    return NULL;
  }

  if (!BuilderRecord::IsItemOfType(item, type)) {
    *err = Err(origin,
        std::string("This is not a ") + BuilderRecord::GetNameForType(type),
        "\"" + label.GetUserVisibleName(false) + "\" refers to a " +
        item->GetItemTypeName() + " instead of a " +
        BuilderRecord::GetNameForType(type) + ".");
    return NULL;
  }
  return record;
}

bool Builder::AddDeps(BuilderRecord* record,
                      const LabelConfigVector& configs,
                      Err* err) {
  for (size_t i = 0; i < configs.size(); i++) {
    BuilderRecord* dep_record = GetOrCreateRecordOfType(
        configs[i].label, configs[i].origin, BuilderRecord::ITEM_CONFIG, err);
    if (!dep_record)
      return false;
    record->AddDep(dep_record);
  }
  return true;
}

bool Builder::AddDeps(BuilderRecord* record,
                      const LabelTargetVector& targets,
                      Err* err) {
  for (size_t i = 0; i < targets.size(); i++) {
    BuilderRecord* dep_record = GetOrCreateRecordOfType(
        targets[i].label, targets[i].origin, BuilderRecord::ITEM_TARGET, err);
    if (!dep_record)
      return false;
    record->AddDep(dep_record);
  }
  return true;
}

bool Builder::AddToolchainDep(BuilderRecord* record,
                              const Target* target,
                              Err* err) {
  BuilderRecord* toolchain_record = GetOrCreateRecordOfType(
      target->settings()->toolchain_label(), target->defined_from(),
      BuilderRecord::ITEM_TOOLCHAIN, err);
  if (!toolchain_record)
    return false;
  record->AddDep(toolchain_record);

  return true;
}

void Builder::RecursiveSetShouldGenerate(BuilderRecord* record,
                                         bool force) {
  if (!force && record->should_generate())
    return;  // Already set.
  record->set_should_generate(true);

  const BuilderRecordSet& deps = record->all_deps();
  for (BuilderRecordSet::const_iterator i = deps.begin();
       i != deps.end(); i++) {
    BuilderRecord* cur = *i;
    if (!cur->should_generate()) {
      ScheduleItemLoadIfNecessary(cur);
      RecursiveSetShouldGenerate(cur, false);
    }
  }
}

void Builder::ScheduleItemLoadIfNecessary(BuilderRecord* record) {
  loader_->Load(record->label());
}

bool Builder::ResolveItem(BuilderRecord* record, Err* err) {
  DCHECK(record->can_resolve() && !record->resolved());

  if (record->type() == BuilderRecord::ITEM_TARGET) {
    Target* target = record->item()->AsTarget();
    if (!ResolveDeps(&target->deps(), err) ||
        !ResolveDeps(&target->datadeps(), err) ||
        !ResolveConfigs(&target->configs(), err) ||
        !ResolveConfigs(&target->all_dependent_configs(), err) ||
        !ResolveConfigs(&target->direct_dependent_configs(), err) ||
        !ResolveForwardDependentConfigs(target, err))
      return false;
  }

  record->set_resolved(true);
  record->item()->OnResolved();
  if (!resolved_callback_.is_null())
    resolved_callback_.Run(record->item());

  // Recursively update everybody waiting on this item to be resolved.
  BuilderRecordSet& waiting_set = record->waiting_on_resolution();
  for (BuilderRecordSet::iterator i = waiting_set.begin();
       i != waiting_set.end(); ++i) {
    BuilderRecord* waiting = *i;
    DCHECK(waiting->unresolved_deps().find(record) !=
           waiting->unresolved_deps().end());
    waiting->unresolved_deps().erase(record);

    if (waiting->can_resolve()) {
      if (!ResolveItem(waiting, err))
        return false;
    }
  }
  waiting_set.clear();
  return true;
}

bool Builder::ResolveDeps(LabelTargetVector* deps, Err* err) {
  for (size_t i = 0; i < deps->size(); i++) {
    LabelTargetPair& cur = (*deps)[i];
    DCHECK(!cur.ptr);

    BuilderRecord* record = GetResolvedRecordOfType(
        cur.label, cur.origin, BuilderRecord::ITEM_TARGET, err);
    if (!record)
      return false;
    cur.ptr = record->item()->AsTarget();
  }
  return true;
}

bool Builder::ResolveConfigs(LabelConfigVector* configs, Err* err) {
  for (size_t i = 0; i < configs->size(); i++) {
    LabelConfigPair& cur = (*configs)[i];
    DCHECK(!cur.ptr);

    BuilderRecord* record = GetResolvedRecordOfType(
        cur.label, cur.origin, BuilderRecord::ITEM_CONFIG, err);
    if (!record)
      return false;
    cur.ptr = record->item()->AsConfig();
  }
  return true;
}

// "Forward dependent configs" should refer to targets in the deps that should
// have their configs forwarded.
bool Builder::ResolveForwardDependentConfigs(Target* target, Err* err) {
  const LabelTargetVector& deps = target->deps();
  LabelTargetVector& configs = target->forward_dependent_configs();

  // Assume that the lists are small so that brute-force n^2 is appropriate.
  for (size_t config_i = 0; config_i < configs.size(); config_i++) {
    for (size_t dep_i = 0; dep_i < deps.size(); dep_i++) {
      if (configs[config_i].label == deps[dep_i].label) {
        DCHECK(deps[dep_i].ptr);  // Should already be resolved.
        configs[config_i].ptr = deps[dep_i].ptr;
        break;
      }
    }
    if (!configs[config_i].ptr) {
      *err = Err(target->defined_from(),
          "Target in forward_dependent_configs_from was not listed in the deps",
          "The target \"" + configs[config_i].label.GetUserVisibleName(false) +
          "\"\n was not present in the deps. This thing is used to forward\n"
          "configs from direct dependents.");
      return false;
    }
  }
  return true;
}

std::string Builder::CheckForCircularDependencies(
    const std::vector<const BuilderRecord*>& bad_records) const {
  std::vector<const BuilderRecord*> cycle;
  if (!RecursiveFindCycle(bad_records[0], &cycle))
    return std::string();  // Didn't find a cycle, something else is wrong.

  // Walk backwards since the dependency arrows point in the reverse direction.
  std::string ret;
  for (int i = static_cast<int>(cycle.size()) - 1; i >= 0; i--) {
    ret += "  " + cycle[i]->label().GetUserVisibleName(false);
    if (i != 0)
      ret += " ->\n";
  }

  return ret;
}