| // 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 "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>; |
| |
| using DepSet = base::hash_set<const Target*>; |
| |
| 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"); |
| } |
| |
| // 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 Target* current, |
| const Target* desired, |
| DepStack* stack, |
| DepSet* reject, |
| int* found_count, |
| bool print_all) { |
| if (reject->find(current) != reject->end()) |
| return; |
| int initial_found_count = *found_count; |
| |
| if (current == desired) { |
| (*found_count)++; |
| if (print_all || *found_count == 1) { |
| stack->push_back(TargetDep(current, DEP_NONE)); |
| PrintDepStack(*stack); |
| stack->pop_back(); |
| } |
| return; |
| } |
| |
| stack->push_back(TargetDep(current, DEP_PUBLIC)); |
| for (const auto& pair : current->public_deps()) |
| RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all); |
| |
| stack->back().second = DEP_PRIVATE; |
| for (const auto& pair : current->private_deps()) |
| RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all); |
| |
| stack->back().second = DEP_DATA; |
| for (const auto& pair : current->data_deps()) |
| RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all); |
| stack->pop_back(); |
| |
| if (*found_count == initial_found_count) |
| reject->insert(current); // Eliminated this target. |
| } |
| |
| } // 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" |
| " Each dependency will be annotated with its type. By default, only the\n" |
| " first path encountered will be printed, which is not necessarily the\n" |
| " shortest path.\n" |
| "\n" |
| "Options\n" |
| "\n" |
| " --all\n" |
| " Prints all paths found rather than just the first one.\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; |
| |
| bool print_all = base::CommandLine::ForCurrentProcess()->HasSwitch("all"); |
| |
| // 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. |
| DepStack stack; |
| DepSet rejected; |
| int found = 0; |
| RecursiveFindPath(target1, target2, &stack, &rejected, &found, print_all); |
| if (found == 0) { |
| // Need to reset the rejected set for a new invocation since the reverse |
| // search will revisit the same targets looking for something else. |
| rejected.clear(); |
| RecursiveFindPath(target2, target1, &stack, &rejected, &found, print_all); |
| } |
| |
| if (found == 0) { |
| OutputString("No paths found between these two targets.\n", |
| DECORATION_YELLOW); |
| } else if (found == 1) { |
| OutputString("1 path found.\n", DECORATION_YELLOW); |
| } else { |
| if (print_all) { |
| OutputString(base::StringPrintf("%d unique paths found.\n", found), |
| DECORATION_YELLOW); |
| } else { |
| OutputString( |
| base::StringPrintf("Showing the first of %d unique paths. ", found), |
| DECORATION_YELLOW); |
| OutputString("Use --all to print all paths.\n"); |
| } |
| } |
| return 0; |
| } |
| |
| } // namespace commands |