1d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// Copyright (c) 2013 The Chromium Authors. All rights reserved. 2d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// found in the LICENSE file. 4d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 5d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#ifndef TOOLS_GN_ITEM_TREE_H_ 6d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#define TOOLS_GN_ITEM_TREE_H_ 7d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 8d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "base/containers/hash_tables.h" 9d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "base/memory/scoped_ptr.h" 10d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "base/synchronization/lock.h" 11d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#include "tools/gn/label.h" 12d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 13a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)class BuildSettings; 14d3868032626d59662ff73b372b5d584c1d144c53Ben Murdochclass Err; 15d3868032626d59662ff73b372b5d584c1d144c53Ben Murdochclass Item; 16d3868032626d59662ff73b372b5d584c1d144c53Ben Murdochclass ItemNode; 17d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 18d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// Represents the full dependency tree if labeled items in the system. 19d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch// Generally you will interact with this through the target manager, etc. 20a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 21a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// There are two modes for filling out the dependency tree: 22a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 23a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// - In greedy mode, every target we encounter will be generated. This means 24a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// that we'll recursively load all of its subdependencies. So if you have 25a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// a build file that's loaded for any reason, all targets in that build file 26a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// will be generated. 27a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 28a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// - In non-greedy mode, we'll only generate and load dependncies for targets 29a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// that have the should_generate bit set. This allows us to load the minimal 30a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// set of buildfiles required for one or more targets. 31a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// 32a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// The main build is generally run in greedy mode, since people expect to be 33a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// be able to write random tests and have them show up in the output. We'll 34a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// switch into non-greed mode when doing diagnostics (like displaying the 35a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// dependency tree on the command line) and for dependencies on targets in 36a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// other toolchains. The toolchain behavior is important, if target A depends 37a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// on B with an alternate toolchain, it doesn't mean we should recursively 38a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// generate all targets in the buildfile just to get B: we should generate the 39a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles)// and load the minimum number of files in order to resolve B. 40d3868032626d59662ff73b372b5d584c1d144c53Ben Murdochclass ItemTree { 41d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch public: 42d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch ItemTree(); 43d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch ~ItemTree(); 44d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 45d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // This lock must be held when calling the "Locked" functions below. 462385ea399aae016c0806a4f9ef3c9cfe3d2a39dfBen Murdoch base::Lock& lock() const { return lock_; } 47d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 48d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // Returns NULL if the item is not found. 49d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // 50d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // The lock must be held. 51d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch ItemNode* GetExistingNodeLocked(const Label& label); 52d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 53d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // There must not be an item with this label in the tree already. Takes 54d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // ownership of the pointer. 55d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // 56d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // The lock must be held. 57d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch void AddNodeLocked(ItemNode* node); 58d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 59a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) // Mark the given item as being defined. If it has no unresolved 60d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // dependencies, it will be marked resolved, and the resolved state will be 61d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // recursively pushed into the dependency tree. Returns an error if there was 62d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // an error. 63a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) bool MarkItemDefinedLocked(const BuildSettings* build_settings, 64a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) const Label& label, 65a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) Err* err); 66d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 67d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // Fills the given vector with all known items. 68d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch void GetAllItemsLocked(std::vector<const Item*>* dest) const; 69d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 70d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // Returns an error if there are unresolved dependencies, or no error if 71d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // there aren't. 72d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // 73d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // The lock should not be held. 74d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch Err CheckForBadItems() const; 75d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 76d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch private: 77a36e5920737c6adbddd3e43b760e5de8431db6e0Torne (Richard Coles) void MarkItemResolvedLocked(ItemNode* node); 78d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 79d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // Given a set of unresolved nodes, looks for cycles and returns the error 80d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch // message describing any cycles it found. 81d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch std::string CheckForCircularDependenciesLocked( 82d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch const std::vector<const ItemNode*>& bad_nodes) const; 83d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 84d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch mutable base::Lock lock_; 85d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 86d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch typedef base::hash_map<Label, ItemNode*> StringToNodeHash; 87d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch StringToNodeHash items_; // Owning pointer. 88d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 89d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch DISALLOW_COPY_AND_ASSIGN(ItemTree); 90d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch}; 91d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch 92d3868032626d59662ff73b372b5d584c1d144c53Ben Murdoch#endif // TOOLS_GN_ITEM_TREE_H_ 93