// Copyright 2015 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 <stddef.h>

#include <algorithm>

#include "base/command_line.h"
#include "base/containers/hash_tables.h"
#include "base/strings/stringprintf.h"
#include "tools/gn/commands.h"
#include "tools/gn/setup.h"
#include "tools/gn/standard_out.h"

namespace commands {

namespace {

enum DepType {
  DEP_NONE,
  DEP_PUBLIC,
  DEP_PRIVATE,
  DEP_DATA
};

// As we do a depth-first search, this vector will store the current path
// the current target for printing when a match is found.
using TargetDep = std::pair<const Target*, DepType>;
using DepStack = std::vector<TargetDep>;

// Note that this uses raw pointers. These need to be manually deleted (which
// we won't normally bother with). This allows the vector to be resized
// more quickly.
using DepStackVector = std::vector<DepStack*>;

using DepSet = base::hash_set<const Target*>;

struct Options {
  Options()
      : all(false),
        public_only(false),
        with_data(false) {
  }

  bool all;
  bool public_only;
  bool with_data;
};

struct State {
  State() : found_count(0) {
    // Reserve fairly large buffers for the found vectors.
    const size_t kReserveSize = 32768;
    found_public.reserve(kReserveSize);
    found_other.reserve(kReserveSize);
  }

  // Stores targets that do not have any paths to the destination. This is
  // an optimization to avoid revisiting useless paths.
  DepSet rejected;

  // Total number of paths found.
  int found_count;

  // The pointers in these vectors are owned by this object, but are
  // deliberately leaked. There can be a lot of them which can take a long time
  // to free, and GN will just exit after this is used anyway.
  DepStackVector found_public;
  DepStackVector found_other;
};

void PrintDepStack(const DepStack& stack) {
  // Don't print toolchains unless they differ from the first target.
  const Label& default_toolchain = stack[0].first->label().GetToolchainLabel();

  for (const auto& pair : stack) {
    OutputString(pair.first->label().GetUserVisibleName(default_toolchain));
    switch (pair.second) {
      case DEP_NONE:
        break;
      case DEP_PUBLIC:
        OutputString(" --[public]-->", DECORATION_DIM);
        break;
      case DEP_PRIVATE:
        OutputString(" --[private]-->", DECORATION_DIM);
        break;
      case DEP_DATA:
        OutputString(" --[data]-->", DECORATION_DIM);
        break;
    }
    OutputString("\n");
  }
  OutputString("\n");
}

bool AreAllPublic(const DepStack& stack) {
  // Don't check the type of the last one since that doesn't point to anything.
  for (size_t i = 0; i < stack.size() - 1; i++) {
    if (stack[i].second != DEP_PUBLIC)
      return false;
  }
  return true;
}

// Increments *found_count to reflect how many results are found. If print_all
// is not set, only the first result will be printed.
//
// As an optimization, targets that do not have any paths are added to
// *reject so this function doesn't waste time revisiting them.
void RecursiveFindPath(const Options& options,
                       State* state,
                       const Target* current,
                       const Target* desired,
                       DepStack* stack) {
  if (state->rejected.find(current) != state->rejected.end())
    return;
  int initial_found_count = state->found_count;

  if (current == desired) {
    // Found a path.
    state->found_count++;
    stack->push_back(TargetDep(current, DEP_NONE));
    if (AreAllPublic(*stack))
      state->found_public.push_back(new DepStack(*stack));
    else
      state->found_other.push_back(new DepStack(*stack));
    stack->pop_back();
    return;
  }

  stack->push_back(TargetDep(current, DEP_PUBLIC));
  for (const auto& pair : current->public_deps())
    RecursiveFindPath(options, state, pair.ptr, desired, stack);

  if (!options.public_only) {
    stack->back().second = DEP_PRIVATE;
    for (const auto& pair : current->private_deps())
      RecursiveFindPath(options, state, pair.ptr, desired, stack);
  }

  if (options.with_data) {
    stack->back().second = DEP_DATA;
    for (const auto& pair : current->data_deps())
      RecursiveFindPath(options, state, pair.ptr, desired, stack);
  }

  stack->pop_back();

  if (state->found_count == initial_found_count)
    state->rejected.insert(current);  // Eliminated this target.
}

bool StackLengthLess(const DepStack* a, const DepStack* b) {
  return a->size() < b->size();
}

// Prints one result vector. The vector will be modified.
void PrintResultVector(const Options& options, DepStackVector* result) {
  if (!options.all && !result->empty()) {
    // Just print the smallest one.
    PrintDepStack(**std::min_element(result->begin(), result->end(),
                                     &StackLengthLess));
    return;
  }

  // Print all in order of increasing length.
  std::sort(result->begin(), result->end(), &StackLengthLess);
  for (const auto& stack : *result)
    PrintDepStack(*stack);
}

void PrintResults(const Options& options, State* state) {
  PrintResultVector(options, &state->found_public);

  // Consider non-public paths only if all paths are requested or there were
  // no public paths.
  if (state->found_public.empty() || options.all)
    PrintResultVector(options, &state->found_other);
}

}  // namespace

const char kPath[] = "path";
const char kPath_HelpShort[] =
    "path: Find paths between two targets.";
const char kPath_Help[] =
    "gn path <out_dir> <target_one> <target_two>\n"
    "\n"
    "  Finds paths of dependencies between two targets. Each unique path\n"
    "  will be printed in one group, and groups will be separate by newlines.\n"
    "  The two targets can appear in either order: paths will be found going\n"
    "  in either direction.\n"
    "\n"
    "  By default, a single path will be printed. If there is a path with\n"
    "  only public dependencies, the shortest public path will be printed.\n"
    "  Otherwise, the shortest path using either public or private\n"
    "  dependencies will be printed. If --with-data is specified, data deps\n"
    "  will also be considered. If there are multiple shortest paths, an\n"
    "  arbitrary one will be selected.\n"
    "\n"
    "Options\n"
    "\n"
    "  --all\n"
    "     Prints all paths found rather than just the first one. Public paths\n"
    "     will be printed first in order of increasing length, followed by\n"
    "     non-public paths in order of increasing length.\n"
    "\n"
    "  --public\n"
    "     Considers only public paths. Can't be used with --with-data.\n"
    "\n"
    "  --with-data\n"
    "     Additionally follows data deps. Without this flag, only public and\n"
    "     private linked deps will be followed. Can't be used with --public.\n"
    "\n"
    "Example\n"
    "\n"
    "  gn path out/Default //base //tools/gn\n";

int RunPath(const std::vector<std::string>& args) {
  if (args.size() != 3) {
    Err(Location(), "You're holding it wrong.",
        "Usage: \"gn path <out_dir> <target_one> <target_two>\"")
        .PrintToStdout();
    return 1;
  }

  Setup* setup = new Setup;
  if (!setup->DoSetup(args[0], false))
    return 1;
  if (!setup->Run())
    return 1;

  const Target* target1 = ResolveTargetFromCommandLineString(setup, args[1]);
  if (!target1)
    return 1;
  const Target* target2 = ResolveTargetFromCommandLineString(setup, args[2]);
  if (!target2)
    return 1;

  Options options;
  options.all = base::CommandLine::ForCurrentProcess()->HasSwitch("all");
  options.public_only =
      base::CommandLine::ForCurrentProcess()->HasSwitch("public");
  options.with_data =
      base::CommandLine::ForCurrentProcess()->HasSwitch("with-data");
  if (options.public_only && options.with_data) {
    Err(Location(), "Can't use --public with --with-data for 'gn path'.",
        "Your zealous over-use of arguments has inevitably resulted in an "
        "invalid\ncombination of flags.").PrintToStdout();
    return 1;
  }

  // If we don't find a path going "forwards", try the reverse direction. Deps
  // can only go in one direction without having a cycle, which will have
  // caused a run failure above.
  State state;
  DepStack stack;
  RecursiveFindPath(options, &state, target1, target2, &stack);
  if (state.found_count == 0) {
    // Need to reset the rejected set for a new invocation since the reverse
    // search will revisit the same targets looking for something else.
    state.rejected.clear();
    RecursiveFindPath(options, &state, target2, target1, &stack);
  }

  PrintResults(options, &state);

  // This string is inserted in the results to annotate whether the result
  // is only public or includes data deps or not.
  const char* path_annotation = "";
  if (options.public_only)
    path_annotation = "public ";
  else if (!options.with_data)
    path_annotation = "non-data ";

  if (state.found_count == 0) {
    // No results.
    OutputString(base::StringPrintf(
        "No %spaths found between these two targets.\n", path_annotation),
        DECORATION_YELLOW);
  } else if (state.found_count == 1) {
    // Exactly one result.
    OutputString(base::StringPrintf("1 %spath found.", path_annotation),
                 DECORATION_YELLOW);
    if (!options.public_only) {
      if (state.found_public.empty())
        OutputString(" It is not public.");
      else
        OutputString(" It is public.");
    }
    OutputString("\n");
  } else {
    if (options.all) {
      // Showing all paths when there are many.
      OutputString(base::StringPrintf("%d unique %spaths found.",
                                      state.found_count, path_annotation),
                   DECORATION_YELLOW);
      if (!options.public_only) {
        OutputString(base::StringPrintf(" %d of them are public.",
            static_cast<int>(state.found_public.size())));
      }
      OutputString("\n");
    } else {
      // Showing one path when there are many.
      OutputString(
          base::StringPrintf("Showing one of %d unique %spaths.",
                             state.found_count, path_annotation),
          DECORATION_YELLOW);
      if (!options.public_only) {
        OutputString(base::StringPrintf(" %d of them are public.\n",
            static_cast<int>(state.found_public.size())));
      }
      OutputString("Use --all to print all paths.\n");
    }
  }
  return 0;
}

}  // namespace commands