Improve gn path command. Finds only non-data dependencies by default. A new flag is added to include these. Normally users are only interested in linked dependencies. Adds a --public flag to print only public dependencies. Sorts any output first by public-ness, then by length of the path. This generally matches what users are looking for. Review URL: https://codereview.chromium.org/1424313009 Cr-Original-Commit-Position: refs/heads/master@{#358051} Cr-Mirrored-From: https://chromium.googlesource.com/chromium/src Cr-Mirrored-Commit: c20901b3694df1dfcd5197f6baead231c48de07f
diff --git a/tools/gn/command_path.cc b/tools/gn/command_path.cc index ae39c8c..021ffe3 100644 --- a/tools/gn/command_path.cc +++ b/tools/gn/command_path.cc
@@ -2,6 +2,8 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. +#include <algorithm> + #include "base/command_line.h" #include "base/containers/hash_tables.h" #include "base/strings/stringprintf.h" @@ -25,8 +27,47 @@ 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(); @@ -51,46 +92,89 @@ 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 Target* current, +void RecursiveFindPath(const Options& options, + State* state, + const Target* current, const Target* desired, - DepStack* stack, - DepSet* reject, - int* found_count, - bool print_all) { - if (reject->find(current) != reject->end()) + DepStack* stack) { + if (state->rejected.find(current) != state->rejected.end()) return; - int initial_found_count = *found_count; + int initial_found_count = state->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(); - } + // 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(pair.ptr, desired, stack, reject, found_count, print_all); + RecursiveFindPath(options, state, pair.ptr, desired, stack); - stack->back().second = DEP_PRIVATE; - for (const auto& pair : current->private_deps()) - RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all); + if (!options.public_only) { + stack->back().second = DEP_PRIVATE; + for (const auto& pair : current->private_deps()) + RecursiveFindPath(options, state, pair.ptr, desired, stack); + } - stack->back().second = DEP_DATA; - for (const auto& pair : current->data_deps()) - RecursiveFindPath(pair.ptr, desired, stack, reject, found_count, print_all); + 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 (*found_count == initial_found_count) - reject->insert(current); // Eliminated this target. + 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 @@ -106,14 +190,26 @@ " 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" + " 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.\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" @@ -140,35 +236,79 @@ if (!target2) return 1; - bool print_all = base::CommandLine::ForCurrentProcess()->HasSwitch("all"); + 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; - DepSet rejected; - int found = 0; - RecursiveFindPath(target1, target2, &stack, &rejected, &found, print_all); - if (found == 0) { + 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. - rejected.clear(); - RecursiveFindPath(target2, target1, &stack, &rejected, &found, print_all); + state.rejected.clear(); + RecursiveFindPath(options, &state, target2, target1, &stack); } - if (found == 0) { - OutputString("No paths found between these two targets.\n", + 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); - } else if (found == 1) { - OutputString("1 path found.\n", 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 (print_all) { - OutputString(base::StringPrintf("%d unique paths found.\n", found), + 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 the first of %d unique paths. ", found), + 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"); } }