tools/gn/command_path.cc

   1 // Copyright 2015 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "base/command_line.h"
   6 #include "base/containers/hash_tables.h"
   7 #include "base/strings/stringprintf.h"
   8 #include "tools/gn/commands.h"
   9 #include "tools/gn/setup.h"
  10 #include "tools/gn/standard_out.h"
  11
  12 namespace commands {
  13
  14 namespace {
  15
  16 enum DepType {
  17   DEP_NONE,
  18   DEP_PUBLIC,
  19   DEP_PRIVATE,
  20   DEP_DATA
  21 };
  22
  23 // As we do a depth-first search, this vector will store the current path
  24 // the current target for printing when a match is found.
  25 using TargetDep = std::pair<const Target*, DepType>;
  26 using DepStack = std::vector<TargetDep>;
  27
  28 using DepSet = base::hash_set<const Target*>;
  29
  30 void PrintDepStack(const DepStack& stack) {
  31   // Don't print toolchains unless they differ from the first target.
  32   const Label& default_toolchain = stack[0].first->label().GetToolchainLabel();
  33
  34   for (const auto& pair : stack) {
  35     OutputString(pair.first->label().GetUserVisibleName(default_toolchain));
  36     switch (pair.second) {
  37       case DEP_NONE:
  38         break;
  39       case DEP_PUBLIC:
  40         OutputString(" --[public]-->", DECORATION_DIM);
  41         break;
  42       case DEP_PRIVATE:
  43         OutputString(" --[private]-->", DECORATION_DIM);
  44         break;
  45       case DEP_DATA:
  46         OutputString(" --[data]-->", DECORATION_DIM);
  47         break;
  48     }
  49     OutputString("\n");
  50   }
  51   OutputString("\n");
  52 }
  53
  54 // Increments *found_count to reflect how many results are found. If print_all
  55 // is not set, only the first result will be printed.
  56 //
  57 // As an optimization, targets that do not have any paths are added to
  58 // *reject so this function doesn't waste time revisiting them.
  59 void RecursiveFindPath(const Target* current,
  60                        const Target* desired,
  61                        DepStack* stack,
  62                        DepSet* reject,
  63                        int* found_count,
  64                        bool print_all) {
  65   if (reject->find(current) != reject->end())
  66     return;
  67   int initial_found_count = *found_count;
  68
  69   if (current == desired) {
  70     (*found_count)++;
  71     if (print_all || *found_count == 1) {
  72       stack->push_back(TargetDep(current, DEP_NONE));
  73       PrintDepStack(*stack);
  74       stack->pop_back();
  75     }
  76     return;
  77   }
  78
  79   stack->push_back(TargetDep(current, DEP_PUBLIC));
  80   for (const auto& pair : current->public_deps())
  81     RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all);
  82
  83   stack->back().second = DEP_PRIVATE;
  84   for (const auto& pair : current->private_deps())
  85     RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all);
  86
  87   stack->back().second = DEP_DATA;
  88   for (const auto& pair : current->data_deps())
  89     RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all);
  90   stack->pop_back();
  91
  92   if (*found_count == initial_found_count)
  93     reject->insert(current);  // Eliminated this target.
  94 }
  95
  96 }  // namespace
  97
  98 const char kPath[] = "path";
  99 const char kPath_HelpShort[] =
 100     "path: Find paths between two targets.";
 101 const char kPath_Help[] =
 102     "gn path <out_dir> <target_one> <target_two>\n"
 103     "\n"
 104     "  Finds paths of dependencies between two targets. Each unique path\n"
 105     "  will be printed in one group, and groups will be separate by newlines.\n"
 106     "  The two targets can appear in either order: paths will be found going\n"
 107     "  in either direction.\n"
 108     "\n"
 109     "  Each dependency will be annotated with its type. By default, only the\n"
 110     "  first path encountered will be printed, which is not necessarily the\n"
 111     "  shortest path.\n"
 112     "\n"
 113     "Options\n"
 114     "\n"
 115     "  --all\n"
 116     "     Prints all paths found rather than just the first one.\n"
 117     "\n"
 118     "Example\n"
 119     "\n"
 120     "  gn path out/Default //base //tools/gn\n";
 121
 122 int RunPath(const std::vector<std::string>& args) {
 123   if (args.size() != 3) {
 124     Err(Location(), "You're holding it wrong.",
 125         "Usage: \"gn path <out_dir> <target_one> <target_two>\"")
 126         .PrintToStdout();
 127     return 1;
 128   }
 129
 130   Setup* setup = new Setup;
 131   if (!setup->DoSetup(args[0], false))
 132     return 1;
 133   if (!setup->Run())
 134     return 1;
 135
 136   const Target* target1 = ResolveTargetFromCommandLineString(setup, args[1]);
 137   if (!target1)
 138     return 1;
 139   const Target* target2 = ResolveTargetFromCommandLineString(setup, args[2]);
 140   if (!target2)
 141     return 1;
 142
 143   bool print_all = base::CommandLine::ForCurrentProcess()->HasSwitch("all");
 144
 145   // If we don't find a path going "forwards", try the reverse direction. Deps
 146   // can only go in one direction without having a cycle, which will have
 147   // caused a run failure above.
 148   DepStack stack;
 149   DepSet rejected;
 150   int found = 0;
 151   RecursiveFindPath(target1, target2, &stack, &rejected, &found, print_all);
 152   if (found == 0) {
 153     // Need to reset the rejected set for a new invocation since the reverse
 154     // search will revisit the same targets looking for something else.
 155     rejected.clear();
 156     RecursiveFindPath(target2, target1, &stack, &rejected, &found, print_all);
 157   }
 158
 159   if (found == 0) {
 160     OutputString("No paths found between these two targets.\n",
 161                  DECORATION_YELLOW);
 162   } else if (found == 1) {
 163     OutputString("1 path found.\n", DECORATION_YELLOW);
 164   } else {
 165     if (print_all) {
 166       OutputString(base::StringPrintf("%d unique paths found.\n", found),
 167                    DECORATION_YELLOW);
 168     } else {
 169       OutputString(
 170           base::StringPrintf("Showing the first of %d unique paths. ", found),
 171           DECORATION_YELLOW);
 172       OutputString("Use --all to print all paths.\n");
 173     }
 174   }
 175   return 0;
 176 }
 177
 178 }  // namespace commands