This is an ordered set tailored to GN's (simple) needs.

This vector is now used to store all config lists. Previously the code did a bunch of work to uniquify configs at certain points (in target.cc) but direct_dependent_configs still ended up with lots of duplicates.

Before this patch the chrome/browser target has 41098 direct_dependent_configs, and after this patch it has 7. Apparently we were also spending a lot of time on these. Before this patch Windows wall clock time was 1031ms, and after this patch it's 831ms. Linux was 834ms before and 593ms after.

Also fix minor build issues in base I noticed while working on this.

R=viettrungluu@chromium.org

Review URL: https://codereview.chromium.org/26537002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@287865 0039d316-1c4b-4281-b951-d872f2087c98

23 files changed, 565 insertions, 174 deletions

diff --git a/tools/gn/BUILD.gn b/tools/gn/BUILD.gn
index 7f7101d..2538784 100644
--- a/tools/gn/BUILD.gn
+++ b/tools/gn/BUILD.gn
@@ -152,6 +152,7 @@ static_library("gn_lib") {
     "toolchain.h",
     "trace.cc",
     "trace.h",
+    "unique_vector.h",
     "value.cc",
     "value.h",
     "value_extractors.cc",
@@ -222,6 +223,7 @@ test("gn_unittests") {
     "test_with_scope.cc",
     "test_with_scope.h",
     "tokenizer_unittest.cc",
+    "unique_vector_unittest.cc",
     "value_unittest.cc",
     "visibility_unittest.cc",
   ]
diff --git a/tools/gn/builder.cc b/tools/gn/builder.cc
index 50a027b..d498b10 100644
--- a/tools/gn/builder.cc
+++ b/tools/gn/builder.cc
@@ -228,7 +228,7 @@ bool Builder::TargetDefined(BuilderRecord* record, Err* err) {
 
   if (!AddDeps(record, target->deps(), err) ||
       !AddDeps(record, target->datadeps(), err) ||
-      !AddDeps(record, target->configs(), err) ||
+      !AddDeps(record, target->configs().vector(), err) ||
       !AddDeps(record, target->all_dependent_configs(), err) ||
       !AddDeps(record, target->direct_dependent_configs(), err) ||
       !AddToolchainDep(record, target, err))
@@ -337,6 +337,19 @@ bool Builder::AddDeps(BuilderRecord* record,
 }
 
 bool Builder::AddDeps(BuilderRecord* record,
+                      const UniqueVector<LabelConfigPair>& configs,
+                      Err* err) {
+  for (size_t i = 0; i < configs.size(); i++) {
+    BuilderRecord* dep_record = GetOrCreateRecordOfType(
+        configs[i].label, configs[i].origin, BuilderRecord::ITEM_CONFIG, err);
+    if (!dep_record)
+      return false;
+    record->AddDep(dep_record);
+  }
+  return true;
+}
+
+bool Builder::AddDeps(BuilderRecord* record,
                       const LabelTargetVector& targets,
                       Err* err) {
   for (size_t i = 0; i < targets.size(); i++) {
@@ -440,16 +453,16 @@ bool Builder::ResolveDeps(LabelTargetVector* deps, Err* err) {
   return true;
 }
 
-bool Builder::ResolveConfigs(LabelConfigVector* configs, Err* err) {
+bool Builder::ResolveConfigs(UniqueVector<LabelConfigPair>* configs, Err* err) {
   for (size_t i = 0; i < configs->size(); i++) {
-    LabelConfigPair& cur = (*configs)[i];
+    const LabelConfigPair& cur = (*configs)[i];
     DCHECK(!cur.ptr);
 
     BuilderRecord* record = GetResolvedRecordOfType(
         cur.label, cur.origin, BuilderRecord::ITEM_CONFIG, err);
     if (!record)
       return false;
-    cur.ptr = record->item()->AsConfig();
+    const_cast<LabelConfigPair&>(cur).ptr = record->item()->AsConfig();
   }
   return true;
 }
@@ -458,14 +471,18 @@ bool Builder::ResolveConfigs(LabelConfigVector* configs, Err* err) {
 // have their configs forwarded.
 bool Builder::ResolveForwardDependentConfigs(Target* target, Err* err) {
   const LabelTargetVector& deps = target->deps();
-  LabelTargetVector& configs = target->forward_dependent_configs();
+  const UniqueVector<LabelTargetPair>& configs =
+      target->forward_dependent_configs();
 
   // Assume that the lists are small so that brute-force n^2 is appropriate.
   for (size_t config_i = 0; config_i < configs.size(); config_i++) {
     for (size_t dep_i = 0; dep_i < deps.size(); dep_i++) {
       if (configs[config_i].label == deps[dep_i].label) {
         DCHECK(deps[dep_i].ptr);  // Should already be resolved.
-        configs[config_i].ptr = deps[dep_i].ptr;
+        // UniqueVector's contents are constant so uniqueness is preserved, but
+        // we want to update this pointer which doesn't change uniqueness
+        // (uniqueness in this vector is determined by the label only).
+        const_cast<LabelTargetPair&>(configs[config_i]).ptr = deps[dep_i].ptr;
         break;
       }
     }
diff --git a/tools/gn/builder.h b/tools/gn/builder.h
index cdb60fe..654a6ad 100644
--- a/tools/gn/builder.h
+++ b/tools/gn/builder.h
@@ -12,6 +12,7 @@
 #include "tools/gn/builder_record.h"
 #include "tools/gn/label.h"
 #include "tools/gn/label_ptr.h"
+#include "tools/gn/unique_vector.h"
 
 class Config;
 class Err;
@@ -84,6 +85,9 @@ class Builder : public base::RefCountedThreadSafe<Builder> {
                const LabelConfigVector& configs,
                Err* err);
   bool AddDeps(BuilderRecord* record,
+               const UniqueVector<LabelConfigPair>& configs,
+               Err* err);
+  bool AddDeps(BuilderRecord* record,
                const LabelTargetVector& targets,
                Err* err);
   bool AddToolchainDep(BuilderRecord* record,
@@ -112,7 +116,7 @@ class Builder : public base::RefCountedThreadSafe<Builder> {
   // that everything should be resolved by this point, so will return an error
   // if anything isn't found or if the type doesn't match.
   bool ResolveDeps(LabelTargetVector* deps, Err* err);
-  bool ResolveConfigs(LabelConfigVector* configs, Err* err);
+  bool ResolveConfigs(UniqueVector<LabelConfigPair>* configs, Err* err);
   bool ResolveForwardDependentConfigs(Target* target, Err* err);
 
   // Given a list of unresolved records, tries to find any circular
diff --git a/tools/gn/command_desc.cc b/tools/gn/command_desc.cc
index 53e322d..f89ea41 100644
--- a/tools/gn/command_desc.cc
+++ b/tools/gn/command_desc.cc
@@ -250,8 +250,27 @@ void PrintConfigsVector(const Target* target,
   }
 }
 
+void PrintConfigsVector(const Target* target,
+                        const UniqueVector<LabelConfigPair>& configs,
+                        const std::string& heading,
+                        bool display_header) {
+  if (configs.empty())
+    return;
+
+  // Don't sort since the order determines how things are processed.
+  if (display_header)
+    OutputString("\n" + heading + " (in order applying):\n");
+
+  Label toolchain_label = target->label().GetToolchainLabel();
+  for (size_t i = 0; i < configs.size(); i++) {
+    OutputString("  " +
+        configs[i].label.GetUserVisibleName(toolchain_label) + "\n");
+  }
+}
+
 void PrintConfigs(const Target* target, bool display_header) {
-  PrintConfigsVector(target, target->configs(), "configs", display_header);
+  PrintConfigsVector(target, target->configs().vector(), "configs",
+                     display_header);
 }
 
 void PrintDirectDependentConfigs(const Target* target, bool display_header) {
diff --git a/tools/gn/gn.gyp b/tools/gn/gn.gyp
index a3627b0..eb79dc6 100644
--- a/tools/gn/gn.gyp
+++ b/tools/gn/gn.gyp
@@ -154,6 +154,7 @@
         'tokenizer.h',
         'toolchain.cc',
         'toolchain.h',
+        'unique_vector.h',
         'trace.cc',
         'trace.h',
         'value.cc',
@@ -222,6 +223,7 @@
         'test_with_scope.cc',
         'test_with_scope.h',
         'tokenizer_unittest.cc',
+        'unique_vector_unittest.cc',
         'value_unittest.cc',
         'visibility_unittest.cc',
       ],
diff --git a/tools/gn/header_checker.cc b/tools/gn/header_checker.cc
index 62a0f44..f2c9db5 100644
--- a/tools/gn/header_checker.cc
+++ b/tools/gn/header_checker.cc
@@ -64,7 +64,8 @@ bool ConfigHasCompilerSettings(const Config* config) {
 // Returns true if the given target has any direct dependent configs with
 // compiler settings in it.
 bool HasDirectDependentCompilerSettings(const Target* target) {
-  const LabelConfigVector& direct = target->direct_dependent_configs();
+  const UniqueVector<LabelConfigPair>& direct =
+      target->direct_dependent_configs();
   for (size_t i = 0; i < direct.size(); i++) {
     if (ConfigHasCompilerSettings(direct[i].ptr))
       return true;
@@ -431,7 +432,8 @@ bool HeaderChecker::DoDirectDependentConfigsApply(
 
     // The forward list on this target should have contained in it the target
     // at the next lower level.
-    const LabelTargetVector& forwarded = chain[i]->forward_dependent_configs();
+    const UniqueVector<LabelTargetPair>& forwarded =
+        chain[i]->forward_dependent_configs();
     if (std::find_if(forwarded.begin(), forwarded.end(),
                      LabelPtrPtrEquals<Target>(chain[i - 1])) ==
         forwarded.end()) {
diff --git a/tools/gn/label.h b/tools/gn/label.h
index 2b7ef4e..1028b30 100644
--- a/tools/gn/label.h
+++ b/tools/gn/label.h
@@ -83,6 +83,13 @@ class Label {
     return toolchain_name_ < other.toolchain_name_;
   }
 
+  void swap(Label& other) {
+    dir_.swap(other.dir_);
+    name_.swap(other.name_);
+    toolchain_dir_.swap(other.toolchain_dir_);
+    toolchain_name_.swap(other.toolchain_name_);
+  }
+
   // Returns true if the toolchain dir/name of this object matches some
   // other object.
   bool ToolchainsEqual(const Label& other) const {
@@ -121,4 +128,8 @@ inline size_t hash_value(const Label& v) {
 
 }  // namespace BASE_HASH_NAMESPACE
 
+inline void swap(Label& lhs, Label& rhs) {
+  lhs.swap(rhs);
+}
+
 #endif  // TOOLS_GN_LABEL_H_
diff --git a/tools/gn/label_ptr.h b/tools/gn/label_ptr.h
index f2519d3..771b14b 100644
--- a/tools/gn/label_ptr.h
+++ b/tools/gn/label_ptr.h
@@ -7,7 +7,11 @@
 
 #include <functional>
 
+#include "tools/gn/label.h"
+
+class Config;
 class ParseNode;
+class Target;
 
 // Structure that holds a labeled "thing". This is used for various places
 // where we need to store lists of targets or configs. We sometimes populate
@@ -80,4 +84,37 @@ struct LabelPtrLabelLess : public std::binary_function<LabelPtrPair<T>,
   }
 };
 
+// Default comparison operators -----------------------------------------------
+//
+// The default hash and comparison operators operate on the label, which should
+// always be valid, whereas the pointer is sometimes null.
+
+template<typename T> inline bool operator==(const LabelPtrPair<T>& a,
+                                            const LabelPtrPair<T>& b) {
+  return a.label == b.label;
+}
+
+template<typename T> inline bool operator<(const LabelPtrPair<T>& a,
+                                           const LabelPtrPair<T>& b) {
+  return a.label < b.label;
+}
+
+namespace BASE_HASH_NAMESPACE {
+
+#if defined(COMPILER_GCC)
+template<typename T> struct hash< LabelPtrPair<T> > {
+  std::size_t operator()(const LabelPtrPair<T>& v) const {
+    BASE_HASH_NAMESPACE::hash<Label> h;
+    return h(v.label);
+  }
+};
+#elif defined(COMPILER_MSVC)
+template<typename T>
+inline size_t hash_value(const LabelPtrPair<T>& v) {
+  return BASE_HASH_NAMESPACE::hash_value(v.label);
+}
+#endif  // COMPILER...
+
+}  // namespace BASE_HASH_NAMESPACE
+
 #endif  // TOOLS_GN_LABEL_PTR_H_
diff --git a/tools/gn/ninja_binary_target_writer.cc b/tools/gn/ninja_binary_target_writer.cc
index c5a7ad1..a5b858e 100644
--- a/tools/gn/ninja_binary_target_writer.cc
+++ b/tools/gn/ninja_binary_target_writer.cc
@@ -320,9 +320,9 @@ void NinjaBinaryTargetWriter::WriteLinkCommand(
        << helper_.GetRulePrefix(target_->settings())
        << Toolchain::ToolTypeToName(tool_type_);
 
-  std::set<OutputFile> extra_object_files;
-  std::vector<const Target*> linkable_deps;
-  std::vector<const Target*> non_linkable_deps;
+  UniqueVector<OutputFile> extra_object_files;
+  UniqueVector<const Target*> linkable_deps;
+  UniqueVector<const Target*> non_linkable_deps;
   GetDeps(&extra_object_files, &linkable_deps, &non_linkable_deps);
 
   // Object files.
@@ -330,10 +330,9 @@ void NinjaBinaryTargetWriter::WriteLinkCommand(
     out_ << " ";
     path_output_.WriteFile(out_, object_files[i]);
   }
-  for (std::set<OutputFile>::iterator i = extra_object_files.begin();
-       i != extra_object_files.end(); ++i) {
+  for (size_t i = 0; i < extra_object_files.size(); i++) {
     out_ << " ";
-    path_output_.WriteFile(out_, *i);
+    path_output_.WriteFile(out_, extra_object_files[i]);
   }
 
   // Libs.
@@ -360,9 +359,9 @@ void NinjaBinaryTargetWriter::WriteSourceSetStamp(
        << helper_.GetRulePrefix(target_->settings())
        << "stamp";
 
-  std::set<OutputFile> extra_object_files;
-  std::vector<const Target*> linkable_deps;
-  std::vector<const Target*> non_linkable_deps;
+  UniqueVector<OutputFile> extra_object_files;
+  UniqueVector<const Target*> linkable_deps;
+  UniqueVector<const Target*> non_linkable_deps;
   GetDeps(&extra_object_files, &linkable_deps, &non_linkable_deps);
 
   // The classifier should never put extra object files in a source set:
@@ -382,24 +381,22 @@ void NinjaBinaryTargetWriter::WriteSourceSetStamp(
 }
 
 void NinjaBinaryTargetWriter::GetDeps(
-    std::set<OutputFile>* extra_object_files,
-    std::vector<const Target*>* linkable_deps,
-    std::vector<const Target*>* non_linkable_deps) const {
+    UniqueVector<OutputFile>* extra_object_files,
+    UniqueVector<const Target*>* linkable_deps,
+    UniqueVector<const Target*>* non_linkable_deps) const {
   const LabelTargetVector& deps = target_->deps();
-  const std::set<const Target*>& inherited = target_->inherited_libraries();
+  const UniqueVector<const Target*>& inherited =
+      target_->inherited_libraries();
 
   // Normal deps.
   for (size_t i = 0; i < deps.size(); i++) {
-    if (inherited.find(deps[i].ptr) != inherited.end())
-      continue;  // Don't add dupes.
     ClassifyDependency(deps[i].ptr, extra_object_files,
                        linkable_deps, non_linkable_deps);
   }
 
   // Inherited libraries.
-  for (std::set<const Target*>::const_iterator i = inherited.begin();
-       i != inherited.end(); ++i) {
-    ClassifyDependency(*i, extra_object_files,
+  for (size_t i = 0; i < inherited.size(); i++) {
+    ClassifyDependency(inherited[i], extra_object_files,
                        linkable_deps, non_linkable_deps);
   }
 
@@ -411,9 +408,9 @@ void NinjaBinaryTargetWriter::GetDeps(
 
 void NinjaBinaryTargetWriter::ClassifyDependency(
     const Target* dep,
-    std::set<OutputFile>* extra_object_files,
-    std::vector<const Target*>* linkable_deps,
-    std::vector<const Target*>* non_linkable_deps) const {
+    UniqueVector<OutputFile>* extra_object_files,
+    UniqueVector<const Target*>* linkable_deps,
+    UniqueVector<const Target*>* non_linkable_deps) const {
   // Only these types of outputs have libraries linked into them. Child deps of
   // static libraries get pushed up the dependency tree until one of these is
   // reached, and source sets don't link at all.
@@ -441,7 +438,7 @@ void NinjaBinaryTargetWriter::ClassifyDependency(
             input_file_type != SOURCE_H) {
           // Note we need to specify the target as the source_set target
           // itself, since this is used to prefix the object file name.
-          extra_object_files->insert(helper_.GetOutputFileForSource(
+          extra_object_files->push_back(helper_.GetOutputFileForSource(
               dep, dep->sources()[i], input_file_type));
         }
       }
@@ -454,7 +451,7 @@ void NinjaBinaryTargetWriter::ClassifyDependency(
 }
 
 void NinjaBinaryTargetWriter::WriteImplicitDependencies(
-    const std::vector<const Target*>& non_linkable_deps) {
+    const UniqueVector<const Target*>& non_linkable_deps) {
   const std::vector<SourceFile>& data = target_->data();
   if (!non_linkable_deps.empty() || !data.empty()) {
     out_ << " ||";
diff --git a/tools/gn/ninja_binary_target_writer.h b/tools/gn/ninja_binary_target_writer.h
index 10fc3ab..1476253 100644
--- a/tools/gn/ninja_binary_target_writer.h
+++ b/tools/gn/ninja_binary_target_writer.h
@@ -8,6 +8,7 @@
 #include "base/compiler_specific.h"
 #include "tools/gn/ninja_target_writer.h"
 #include "tools/gn/toolchain.h"
+#include "tools/gn/unique_vector.h"
 
 // Writes a .ninja file for a binary target type (an executable, a shared
 // library, or a static library).
@@ -40,18 +41,18 @@ class NinjaBinaryTargetWriter : public NinjaTargetWriter {
 
   // Gets all target dependencies and classifies them, as well as accumulates
   // object files from source sets we need to link.
-  void GetDeps(std::set<OutputFile>* extra_object_files,
-               std::vector<const Target*>* linkable_deps,
-               std::vector<const Target*>* non_linkable_deps) const;
+  void GetDeps(UniqueVector<OutputFile>* extra_object_files,
+               UniqueVector<const Target*>* linkable_deps,
+               UniqueVector<const Target*>* non_linkable_deps) const;
 
   // Classifies the dependency as linkable or nonlinkable with the current
   // target, adding it to the appropriate vector. If the dependency is a source
   // set we should link in, the source set's object files will be appended to
   // |extra_object_files|.
   void ClassifyDependency(const Target* dep,
-                          std::set<OutputFile>* extra_object_files,
-                          std::vector<const Target*>* linkable_deps,
-                          std::vector<const Target*>* non_linkable_deps) const;
+                          UniqueVector<OutputFile>* extra_object_files,
+                          UniqueVector<const Target*>* linkable_deps,
+                          UniqueVector<const Target*>* non_linkable_deps) const;
 
   // Writes the implicit dependencies for the link or stamp line. This is
   // the "||" and everything following it on the ninja line.
@@ -59,7 +60,7 @@ class NinjaBinaryTargetWriter : public NinjaTargetWriter {
   // The implicit dependencies are the non-linkable deps passed in as an
   // argument, plus the data file depdencies in the target.
   void WriteImplicitDependencies(
-      const std::vector<const Target*>& non_linkable_deps);
+      const UniqueVector<const Target*>& non_linkable_deps);
 
   Toolchain::ToolType tool_type_;
 
diff --git a/tools/gn/ninja_binary_target_writer_unittest.cc b/tools/gn/ninja_binary_target_writer_unittest.cc
index eb22f38..5e03871 100644
--- a/tools/gn/ninja_binary_target_writer_unittest.cc
+++ b/tools/gn/ninja_binary_target_writer_unittest.cc
@@ -29,8 +29,6 @@ TEST(NinjaBinaryTargetWriter, SourceSet) {
     NinjaBinaryTargetWriter writer(&target, setup.toolchain(), out);
     writer.Run();
 
-    // TODO(brettw) I think we'll need to worry about backslashes here
-    // depending if we're on actual Windows or Linux pretending to be Windows.
     const char expected_win[] =
         "defines =\n"
         "includes =\n"
@@ -66,8 +64,6 @@ TEST(NinjaBinaryTargetWriter, SourceSet) {
     NinjaBinaryTargetWriter writer(&shlib_target, setup.toolchain(), out);
     writer.Run();
 
-    // TODO(brettw) I think we'll need to worry about backslashes here
-    // depending if we're on actual Windows or Linux pretending to be Windows.
     const char expected_win[] =
         "defines =\n"
         "includes =\n"
@@ -85,11 +81,12 @@ TEST(NinjaBinaryTargetWriter, SourceSet) {
         "ldflags = /MANIFEST /ManifestFile:obj/foo/shlib.intermediate."
             "manifest\n"
         "libs =\n"
-        // Ordering of the obj files here is arbitrary. Currently they're put
-        // in a set and come out sorted.
-        "build shlib.dll shlib.dll.lib: solink ../../foo/input3.o "
-            "../../foo/input4.obj obj/foo/bar.input1.obj "
-            "obj/foo/bar.input2.obj\n"
+        // Ordering of the obj files here should come out in the order
+        // specified, with the target's first, followed by the source set's, in
+        // order.
+        "build shlib.dll shlib.dll.lib: solink obj/foo/bar.input1.obj "
+            "obj/foo/bar.input2.obj ../../foo/input3.o "
+            "../../foo/input4.obj\n"
         "  soname = shlib.dll\n"
         "  lib = shlib.dll\n"
         "  dll = shlib.dll\n"
@@ -112,8 +109,6 @@ TEST(NinjaBinaryTargetWriter, SourceSet) {
     NinjaBinaryTargetWriter writer(&stlib_target, setup.toolchain(), out);
     writer.Run();
 
-    // TODO(brettw) I think we'll need to worry about backslashes here
-    // depending if we're on actual Windows or Linux pretending to be Windows.
     const char expected_win[] =
         "defines =\n"
         "includes =\n"
@@ -158,8 +153,6 @@ TEST(NinjaBinaryTargetWriter, ProductExtension) {
   NinjaBinaryTargetWriter writer(&target, setup.toolchain(), out);
   writer.Run();
 
-  // TODO(brettw) I think we'll need to worry about backslashes here
-  // depending if we're on actual Windows or Linux pretending to be Windows.
   const char expected[] =
       "defines =\n"
       "includes =\n"
@@ -207,8 +200,6 @@ TEST(NinjaBinaryTargetWriter, EmptyProductExtension) {
   NinjaBinaryTargetWriter writer(&target, setup.toolchain(), out);
   writer.Run();
 
-  // TODO(brettw) I think we'll need to worry about backslashes here
-  // depending if we're on actual Windows or Linux pretending to be Windows.
   const char expected[] =
       "defines =\n"
       "includes =\n"
diff --git a/tools/gn/output_file.h b/tools/gn/output_file.h
index 2e7a0ce..252fae4 100644
--- a/tools/gn/output_file.h
+++ b/tools/gn/output_file.h
@@ -7,6 +7,7 @@
 
 #include <string>
 
+#include "base/containers/hash_tables.h"
 #include "tools/gn/build_settings.h"
 #include "tools/gn/source_file.h"
 
@@ -41,4 +42,25 @@ class OutputFile {
   std::string value_;
 };
 
+namespace BASE_HASH_NAMESPACE {
+
+#if defined(COMPILER_GCC)
+template<> struct hash<OutputFile> {
+  std::size_t operator()(const OutputFile& v) const {
+    hash<std::string> h;
+    return h(v.value());
+  }
+};
+#elif defined(COMPILER_MSVC)
+inline size_t hash_value(const OutputFile& v) {
+  return hash_value(v.value());
+}
+#endif  // COMPILER...
+
+}  // namespace BASE_HASH_NAMESPACE
+
+inline void swap(OutputFile& lhs, OutputFile& rhs) {
+  lhs.value().swap(rhs.value());
+}
+
 #endif  // TOOLS_GN_OUTPUT_FILE_H_
diff --git a/tools/gn/source_dir.h b/tools/gn/source_dir.h
index 99be5c3..719579b 100644
--- a/tools/gn/source_dir.h
+++ b/tools/gn/source_dir.h
@@ -5,6 +5,7 @@
 #ifndef TOOLS_GN_SOURCE_DIR_H_
 #define TOOLS_GN_SOURCE_DIR_H_
 
+#include <algorithm>
 #include <string>
 
 #include "base/containers/hash_tables.h"
@@ -90,6 +91,10 @@ class SourceDir {
     return value_ < other.value_;
   }
 
+  void swap(SourceDir& other) {
+    value_.swap(other.value_);
+  }
+
  private:
   friend class SourceFile;
   std::string value_;
@@ -114,4 +119,8 @@ inline size_t hash_value(const SourceDir& v) {
 
 }  // namespace BASE_HASH_NAMESPACE
 
+inline void swap(SourceDir& lhs, SourceDir& rhs) {
+  lhs.swap(rhs);
+}
+
 #endif  // TOOLS_GN_SOURCE_DIR_H_
diff --git a/tools/gn/source_file.h b/tools/gn/source_file.h
index 0c1508e..7d07a53 100644
--- a/tools/gn/source_file.h
+++ b/tools/gn/source_file.h
@@ -5,6 +5,7 @@
 #ifndef TOOLS_GN_SOURCE_FILE_H_
 #define TOOLS_GN_SOURCE_FILE_H_
 
+#include <algorithm>
 #include <string>
 
 #include "base/containers/hash_tables.h"
@@ -75,6 +76,10 @@ class SourceFile {
     return value_ < other.value_;
   }
 
+  void swap(SourceFile& other) {
+    value_.swap(other.value_);
+  }
+
  private:
   friend class SourceDir;
 
@@ -100,4 +105,8 @@ inline size_t hash_value(const SourceFile& v) {
 
 }  // namespace BASE_HASH_NAMESPACE
 
+inline void swap(SourceFile& lhs, SourceFile& rhs) {
+  lhs.swap(rhs);
+}
+
 #endif  // TOOLS_GN_SOURCE_FILE_H_
diff --git a/tools/gn/target.cc b/tools/gn/target.cc
index a83c60e..1983374 100644
--- a/tools/gn/target.cc
+++ b/tools/gn/target.cc
@@ -13,39 +13,25 @@ namespace {
 typedef std::set<const Config*> ConfigSet;
 
 // Merges the dependent configs from the given target to the given config list.
-// The unique_configs list is used for de-duping so values already added will
-// not be added again.
 void MergeDirectDependentConfigsFrom(const Target* from_target,
-                                     ConfigSet* unique_configs,
-                                     LabelConfigVector* dest) {
-  const LabelConfigVector& direct = from_target->direct_dependent_configs();
-  for (size_t i = 0; i < direct.size(); i++) {
-    if (unique_configs->find(direct[i].ptr) == unique_configs->end()) {
-      unique_configs->insert(direct[i].ptr);
-      dest->push_back(direct[i]);
-    }
-  }
+                                     UniqueVector<LabelConfigPair>* dest) {
+  const UniqueVector<LabelConfigPair>& direct =
+      from_target->direct_dependent_configs();
+  for (size_t i = 0; i < direct.size(); i++)
+    dest->push_back(direct[i]);
 }
 
 // Like MergeDirectDependentConfigsFrom above except does the "all dependent"
 // ones. This additionally adds all configs to the all_dependent_configs_ of
 // the dest target given in *all_dest.
 void MergeAllDependentConfigsFrom(const Target* from_target,
-                                  ConfigSet* unique_configs,
-                                  LabelConfigVector* dest,
-                                  LabelConfigVector* all_dest) {
-  const LabelConfigVector& all = from_target->all_dependent_configs();
+                                  UniqueVector<LabelConfigPair>* dest,
+                                  UniqueVector<LabelConfigPair>* all_dest) {
+  const UniqueVector<LabelConfigPair>& all =
+      from_target->all_dependent_configs();
   for (size_t i = 0; i < all.size(); i++) {
-    // Always add it to all_dependent_configs_ since it might not be in that
-    // list even if we've seen it applied to this target before. This may
-    // introduce some duplicates in all_dependent_configs_, but those will
-    // we removed when they're actually applied to a target.
     all_dest->push_back(all[i]);
-    if (unique_configs->find(all[i].ptr) == unique_configs->end()) {
-      // One we haven't seen yet, also apply it to ourselves.
-      dest->push_back(all[i]);
-      unique_configs->insert(all[i].ptr);
-    }
+    dest->push_back(all[i]);
   }
 }
 
@@ -110,26 +96,10 @@ void Target::OnResolved() {
     }
   }
 
-  // Only add each config once. First remember the target's configs.
-  ConfigSet unique_configs;
-  for (size_t i = 0; i < configs_.size(); i++)
-    unique_configs.insert(configs_[i].ptr);
-
   // Copy our own dependent configs to the list of configs applying to us.
-  for (size_t i = 0; i < all_dependent_configs_.size(); i++) {
-    if (unique_configs.find(all_dependent_configs_[i].ptr) ==
-        unique_configs.end()) {
-      unique_configs.insert(all_dependent_configs_[i].ptr);
-      configs_.push_back(all_dependent_configs_[i]);
-    }
-  }
-  for (size_t i = 0; i < direct_dependent_configs_.size(); i++) {
-    if (unique_configs.find(direct_dependent_configs_[i].ptr) ==
-        unique_configs.end()) {
-      unique_configs.insert(direct_dependent_configs_[i].ptr);
-      configs_.push_back(direct_dependent_configs_[i]);
-    }
-  }
+  configs_.Append(all_dependent_configs_.begin(), all_dependent_configs_.end());
+  configs_.Append(direct_dependent_configs_.begin(),
+                  direct_dependent_configs_.end());
 
   // Copy our own libs and lib_dirs to the final set. This will be from our
   // target and all of our configs. We do this specially since these must be
@@ -146,7 +116,7 @@ void Target::OnResolved() {
     // be treated as direct dependencies of A, so this is unnecessary and will
     // actually result in duplicated settings (since settings will also be
     // pulled from G to A in case G has configs directly on it).
-    PullDependentTargetInfo(&unique_configs);
+    PullDependentTargetInfo();
   }
   PullForwardedDependentConfigs();
   PullRecursiveHardDeps();
@@ -156,28 +126,25 @@ bool Target::IsLinkable() const {
   return output_type_ == STATIC_LIBRARY || output_type_ == SHARED_LIBRARY;
 }
 
-void Target::PullDependentTargetInfo(std::set<const Config*>* unique_configs) {
+void Target::PullDependentTargetInfo() {
   // Gather info from our dependents we need.
   for (size_t dep_i = 0; dep_i < deps_.size(); dep_i++) {
     const Target* dep = deps_[dep_i].ptr;
-    MergeAllDependentConfigsFrom(dep, unique_configs, &configs_,
-                                 &all_dependent_configs_);
-    MergeDirectDependentConfigsFrom(dep, unique_configs, &configs_);
+    MergeAllDependentConfigsFrom(dep, &configs_, &all_dependent_configs_);
+    MergeDirectDependentConfigsFrom(dep, &configs_);
 
     // Direct dependent libraries.
     if (dep->output_type() == STATIC_LIBRARY ||
         dep->output_type() == SHARED_LIBRARY ||
         dep->output_type() == SOURCE_SET)
-      inherited_libraries_.insert(dep);
+      inherited_libraries_.push_back(dep);
 
     // Inherited libraries and flags are inherited across static library
     // boundaries.
     if (dep->output_type() != SHARED_LIBRARY &&
         dep->output_type() != EXECUTABLE) {
-      const std::set<const Target*> inherited = dep->inherited_libraries();
-      for (std::set<const Target*>::const_iterator i = inherited.begin();
-           i != inherited.end(); ++i)
-        inherited_libraries_.insert(*i);
+      inherited_libraries_.Append(dep->inherited_libraries().begin(),
+                                  dep->inherited_libraries().end());
 
       // Inherited library settings.
       all_lib_dirs_.append(dep->all_lib_dirs());
@@ -188,8 +155,10 @@ void Target::PullDependentTargetInfo(std::set<const Config*>* unique_configs) {
 
 void Target::PullForwardedDependentConfigs() {
   // Groups implicitly forward all if its dependency's configs.
-  if (output_type() == GROUP)
-    forward_dependent_configs_ = deps_;
+  if (output_type() == GROUP) {
+    for (size_t i = 0; i < deps_.size(); i++)
+      forward_dependent_configs_.push_back(deps_[i]);
+  }
 
   // Forward direct dependent configs if requested.
   for (size_t dep = 0; dep < forward_dependent_configs_.size(); dep++) {
@@ -200,8 +169,7 @@ void Target::PullForwardedDependentConfigs() {
     DCHECK(std::find_if(deps_.begin(), deps_.end(),
                         LabelPtrPtrEquals<Target>(from_target)) !=
            deps_.end());
-    direct_dependent_configs_.insert(
-        direct_dependent_configs_.end(),
+    direct_dependent_configs_.Append(
         from_target->direct_dependent_configs().begin(),
         from_target->direct_dependent_configs().end());
   }
diff --git a/tools/gn/target.h b/tools/gn/target.h
index 572333d..f0301e9 100644
--- a/tools/gn/target.h
+++ b/tools/gn/target.h
@@ -20,6 +20,7 @@
 #include "tools/gn/label_ptr.h"
 #include "tools/gn/ordered_set.h"
 #include "tools/gn/source_file.h"
+#include "tools/gn/unique_vector.h"
 
 class InputFile;
 class Settings;
@@ -105,38 +106,38 @@ class Target : public Item {
 
   // List of configs that this class inherits settings from. Once a target is
   // resolved, this will also list all- and direct-dependent configs.
-  const LabelConfigVector& configs() const { return configs_; }
-  LabelConfigVector& configs() { return configs_; }
+  const UniqueVector<LabelConfigPair>& configs() const { return configs_; }
+  UniqueVector<LabelConfigPair>& configs() { return configs_; }
 
   // List of configs that all dependencies (direct and indirect) of this
   // target get. These configs are not added to this target. Note that due
   // to the way this is computed, there may be duplicates in this list.
-  const LabelConfigVector& all_dependent_configs() const {
+  const UniqueVector<LabelConfigPair>& all_dependent_configs() const {
     return all_dependent_configs_;
   }
-  LabelConfigVector& all_dependent_configs() {
+  UniqueVector<LabelConfigPair>& all_dependent_configs() {
     return all_dependent_configs_;
   }
 
   // List of configs that targets depending directly on this one get. These
   // configs are not added to this target.
-  const LabelConfigVector& direct_dependent_configs() const {
+  const UniqueVector<LabelConfigPair>& direct_dependent_configs() const {
     return direct_dependent_configs_;
   }
-  LabelConfigVector& direct_dependent_configs() {
+  UniqueVector<LabelConfigPair>& direct_dependent_configs() {
     return direct_dependent_configs_;
   }
 
   // A list of a subset of deps where we'll re-export direct_dependent_configs
   // as direct_dependent_configs of this target.
-  const LabelTargetVector& forward_dependent_configs() const {
+  const UniqueVector<LabelTargetPair>& forward_dependent_configs() const {
     return forward_dependent_configs_;
   }
-  LabelTargetVector& forward_dependent_configs() {
+  UniqueVector<LabelTargetPair>& forward_dependent_configs() {
     return forward_dependent_configs_;
   }
 
-  const std::set<const Target*>& inherited_libraries() const {
+  const UniqueVector<const Target*>& inherited_libraries() const {
     return inherited_libraries_;
   }
 
@@ -157,7 +158,7 @@ class Target : public Item {
  private:
   // Pulls necessary information from dependencies to this one when all
   // dependencies have been resolved.
-  void PullDependentTargetInfo(std::set<const Config*>* unique_configs);
+  void PullDependentTargetInfo();
 
   // These each pull specific things from dependencies to this one when all
   // deps have been resolved.
@@ -190,10 +191,10 @@ class Target : public Item {
   LabelTargetVector deps_;
   LabelTargetVector datadeps_;
 
-  LabelConfigVector configs_;
-  LabelConfigVector all_dependent_configs_;
-  LabelConfigVector direct_dependent_configs_;
-  LabelTargetVector forward_dependent_configs_;
+  UniqueVector<LabelConfigPair> configs_;
+  UniqueVector<LabelConfigPair> all_dependent_configs_;
+  UniqueVector<LabelConfigPair> direct_dependent_configs_;
+  UniqueVector<LabelTargetPair> forward_dependent_configs_;
 
   bool external_;
 
@@ -202,7 +203,7 @@ class Target : public Item {
   // sets do not get pushed beyond static library boundaries, and neither
   // source sets nor static libraries get pushed beyond sahred library
   // boundaries.
-  std::set<const Target*> inherited_libraries_;
+  UniqueVector<const Target*> inherited_libraries_;
 
   // These libs and dirs are inherited from statically linked deps and all
   // configs applying to this target.
@@ -219,4 +220,20 @@ class Target : public Item {
   DISALLOW_COPY_AND_ASSIGN(Target);
 };
 
+namespace BASE_HASH_NAMESPACE {
+
+#if defined(COMPILER_GCC)
+template<> struct hash<const Target*> {
+  std::size_t operator()(const Target* t) const {
+    return reinterpret_cast<std::size_t>(t);
+  }
+};
+#elif defined(COMPILER_MSVC)
+inline size_t hash_value(const Target* t) {
+  return reinterpret_cast<size_t>(t);
+}
+#endif  // COMPILER...
+
+}  // namespace BASE_HASH_NAMESPACE
+
 #endif  // TOOLS_GN_TARGET_H_
diff --git a/tools/gn/target_generator.cc b/tools/gn/target_generator.cc
index 4821da6..bdccf43 100644
--- a/tools/gn/target_generator.cc
+++ b/tools/gn/target_generator.cc
@@ -283,11 +283,11 @@ bool TargetGenerator::EnsureSubstitutionIsInOutputDir(
 }
 
 void TargetGenerator::FillGenericConfigs(const char* var_name,
-                                         LabelConfigVector* dest) {
+                                         UniqueVector<LabelConfigPair>* dest) {
   const Value* value = scope_->GetValue(var_name, true);
   if (value) {
-    ExtractListOfLabels(*value, scope_->GetSourceDir(),
-                        ToolchainLabelForScope(scope_), dest, err_);
+    ExtractListOfUniqueLabels(*value, scope_->GetSourceDir(),
+                              ToolchainLabelForScope(scope_), dest, err_);
   }
 }
 
@@ -304,8 +304,8 @@ void TargetGenerator::FillForwardDependentConfigs() {
   const Value* value = scope_->GetValue(
       variables::kForwardDependentConfigsFrom, true);
   if (value) {
-    ExtractListOfLabels(*value, scope_->GetSourceDir(),
-                        ToolchainLabelForScope(scope_),
-                        &target_->forward_dependent_configs(), err_);
+    ExtractListOfUniqueLabels(*value, scope_->GetSourceDir(),
+                              ToolchainLabelForScope(scope_),
+                              &target_->forward_dependent_configs(), err_);
   }
 }
diff --git a/tools/gn/target_generator.h b/tools/gn/target_generator.h
index 7428a4d..fce599f 100644
--- a/tools/gn/target_generator.h
+++ b/tools/gn/target_generator.h
@@ -73,7 +73,8 @@ class TargetGenerator {
 
   // Reads configs/deps from the given var name, and uses the given setting on
   // the target to save them.
-  void FillGenericConfigs(const char* var_name, LabelConfigVector* dest);
+  void FillGenericConfigs(const char* var_name,
+                          UniqueVector<LabelConfigPair>* dest);
   void FillGenericDeps(const char* var_name, LabelTargetVector* dest);
 
   void FillForwardDependentConfigs();
diff --git a/tools/gn/target_unittest.cc b/tools/gn/target_unittest.cc
index f9a1f97..9dcaf08 100644
--- a/tools/gn/target_unittest.cc
+++ b/tools/gn/target_unittest.cc
@@ -221,19 +221,19 @@ TEST_F(TargetTest, InheritLibs) {
   a.OnResolved();
 
   // C should have D in its inherited libs.
-  const std::set<const Target*>& c_inherited = c.inherited_libraries();
+  const UniqueVector<const Target*>& c_inherited = c.inherited_libraries();
   EXPECT_EQ(1u, c_inherited.size());
-  EXPECT_TRUE(c_inherited.find(&d) != c_inherited.end());
+  EXPECT_TRUE(c_inherited.IndexOf(&d) != static_cast<size_t>(-1));
 
   // B should have C and D in its inherited libs.
-  const std::set<const Target*>& b_inherited = b.inherited_libraries();
+  const UniqueVector<const Target*>& b_inherited = b.inherited_libraries();
   EXPECT_EQ(2u, b_inherited.size());
-  EXPECT_TRUE(b_inherited.find(&c) != b_inherited.end());
-  EXPECT_TRUE(b_inherited.find(&d) != b_inherited.end());
+  EXPECT_TRUE(b_inherited.IndexOf(&c) != static_cast<size_t>(-1));
+  EXPECT_TRUE(b_inherited.IndexOf(&d) != static_cast<size_t>(-1));
 
   // A should have B in its inherited libs, but not any others (the shared
   // library will include the static library and source set).
-  const std::set<const Target*>& a_inherited = a.inherited_libraries();
+  const UniqueVector<const Target*>& a_inherited = a.inherited_libraries();
   EXPECT_EQ(1u, a_inherited.size());
-  EXPECT_TRUE(a_inherited.find(&b) != a_inherited.end());
+  EXPECT_TRUE(a_inherited.IndexOf(&b) != static_cast<size_t>(-1));
 }
diff --git a/tools/gn/unique_vector.h b/tools/gn/unique_vector.h
new file mode 100644
index 0000000..16f797e
--- /dev/null
+++ b/tools/gn/unique_vector.h
@@ -0,0 +1,189 @@
+// Copyright 2014 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.
+
+#ifndef TOOLS_GN_UNIQUE_VECTOR_H_
+#define TOOLS_GN_UNIQUE_VECTOR_H_
+
+#include <algorithm>
+
+#include "base/containers/hash_tables.h"
+
+namespace internal {
+
+// This lass allows us to insert things by reference into a hash table which
+// avoids copies. The hash function of a UniquifyRef is that of the object it
+// points to.
+//
+// There are two ways it can store data: (1) by (vector*, index) which is used
+// to refer to the array in UniqueVector and make it work even when the
+// underlying vector is reallocated; (2) by T* which is used to do lookups
+// into the hash table of things that aren't in a vector yet.
+//
+// It also caches the hash value which allows us to query and then insert
+// without recomputing the hash.
+template<typename T>
+class UniquifyRef {
+ public:
+  UniquifyRef()
+      : value_(NULL),
+        vect_(NULL),
+        index_(static_cast<size_t>(-1)),
+        hash_val_(0) {
+  }
+
+  // Initialize with a pointer to a value.
+  UniquifyRef(const T* v)
+      : value_(v),
+        vect_(NULL),
+        index_(static_cast<size_t>(-1)) {
+    FillHashValue();
+  }
+
+  // Initialize with an array + index.
+  UniquifyRef(const std::vector<T>* v, size_t i)
+      : value_(NULL),
+        vect_(v),
+        index_(i) {
+    FillHashValue();
+  }
+
+  // Initialize with an array + index and a known hash value to prevent
+  // re-hashing.
+  UniquifyRef(const std::vector<T>* v, size_t i, size_t hash_value)
+      : value_(NULL),
+        vect_(v),
+        index_(i),
+        hash_val_(hash_value) {
+  }
+
+  const T& value() const { return value_ ? *value_ : (*vect_)[index_]; }
+  size_t hash_val() const { return hash_val_; }
+  size_t index() const { return index_; }
+
+ private:
+  void FillHashValue() {
+#if defined(COMPILER_GCC)
+    BASE_HASH_NAMESPACE::hash<T> h;
+    hash_val_ = h(value());
+#elif defined(COMPILER_MSVC)
+    hash_val_ = BASE_HASH_NAMESPACE::hash_value(value());
+#else
+    #error write me
+#endif  // COMPILER...
+  }
+
+  // When non-null, points to the object.
+  const T* value_;
+
+  // When value is null these are used.
+  const std::vector<T>* vect_;
+  size_t index_;
+
+  size_t hash_val_;
+};
+
+template<typename T> inline bool operator==(const UniquifyRef<T>& a,
+                                            const UniquifyRef<T>& b) {
+  return a.value() == b.value();
+}
+
+template<typename T> inline bool operator<(const UniquifyRef<T>& a,
+                                           const UniquifyRef<T>& b) {
+  return a.value() < b.value();
+}
+
+}  // namespace internal
+
+namespace BASE_HASH_NAMESPACE {
+
+#if defined(COMPILER_GCC)
+template<typename T> struct hash< internal::UniquifyRef<T> > {
+  std::size_t operator()(const internal::UniquifyRef<T>& v) const {
+    return v.hash_val();
+  }
+};
+#elif defined(COMPILER_MSVC)
+template<typename T>
+inline size_t hash_value(const internal::UniquifyRef<T>& v) {
+  return v.hash_val();
+}
+#endif  // COMPILER...
+
+}  // namespace BASE_HASH_NAMESPACE
+
+// An ordered set optimized for GN's usage. Such sets are used to store lists
+// of configs and libraries, and are appended to but not randomly inserted
+// into.
+template<typename T>
+class UniqueVector {
+ public:
+  typedef std::vector<T> Vector;
+  typedef typename Vector::iterator iterator;
+  typedef typename Vector::const_iterator const_iterator;
+
+  const Vector& vector() const { return vector_; }
+  size_t size() const { return vector_.size(); }
+  bool empty() const { return vector_.empty(); }
+  void clear() { vector_.clear(); set_.clear(); }
+  void reserve(size_t s) { vector_.reserve(s); }
+
+  const T& operator[](size_t index) const { return vector_[index]; }
+
+  const_iterator begin() const { return vector_.begin(); }
+  iterator begin() { return vector_.begin(); }
+  const_iterator end() const { return vector_.end(); }
+  iterator end() { return vector_.end(); }
+
+  // Returns true if the item was appended, false if it already existed (and
+  // thus the vector was not modified).
+  bool push_back(const T& t) {
+    Ref ref(&t);
+    if (set_.find(ref) != set_.end())
+      return false;  // Already have this one.
+
+    vector_.push_back(t);
+    set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val()));
+    return true;
+  }
+
+  // Like push_back but swaps in the type to avoid a copy.
+  bool PushBackViaSwap(T* t) {
+    using std::swap;
+
+    Ref ref(t);
+    if (set_.find(ref) != set_.end())
+      return false;  // Already have this one.
+
+    size_t new_index = vector_.size();
+    vector_.resize(new_index + 1);
+    swap(vector_[new_index], *t);
+    set_.insert(Ref(&vector_, vector_.size() - 1, ref.hash_val()));
+    return true;
+  }
+
+  // Appends a range of items from an iterator.
+  template<typename iter> void Append(const iter& begin, const iter& end) {
+    for (iter i = begin; i != end; ++i)
+      push_back(*i);
+  }
+
+  // Returns the index of the item matching the given value in the list, or
+  // (size_t)(-1) if it's not found.
+  size_t IndexOf(const T& t) const {
+    Ref ref(&t);
+    typename HashSet::const_iterator found = set_.find(ref);
+    if (found == set_.end())
+      return static_cast<size_t>(-1);
+    return found->index();
+  }
+
+ private:
+  typedef internal::UniquifyRef<T> Ref;
+  typedef base::hash_set<Ref> HashSet;
+
+  HashSet set_;
+  Vector vector_;
+};
+
+#endif  // TOOLS_GN_UNIQUE_VECTOR_H_
diff --git a/tools/gn/unique_vector_unittest.cc b/tools/gn/unique_vector_unittest.cc
new file mode 100644
index 0000000..0f5d461
--- /dev/null
+++ b/tools/gn/unique_vector_unittest.cc
@@ -0,0 +1,43 @@
+// Copyright (c) 2013 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 <algorithm>
+
+#include "base/time/time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "tools/gn/unique_vector.h"
+
+TEST(UniqueVector, PushBack) {
+  UniqueVector<int> foo;
+  EXPECT_TRUE(foo.push_back(1));
+  EXPECT_FALSE(foo.push_back(1));
+  EXPECT_TRUE(foo.push_back(2));
+  EXPECT_TRUE(foo.push_back(0));
+  EXPECT_FALSE(foo.push_back(2));
+  EXPECT_FALSE(foo.push_back(1));
+
+  EXPECT_EQ(3u, foo.size());
+  EXPECT_EQ(1, foo[0]);
+  EXPECT_EQ(2, foo[1]);
+  EXPECT_EQ(0, foo[2]);
+
+  // Verify those results with IndexOf as well.
+  EXPECT_EQ(0u, foo.IndexOf(1));
+  EXPECT_EQ(1u, foo.IndexOf(2));
+  EXPECT_EQ(2u, foo.IndexOf(0));
+  EXPECT_EQ(static_cast<size_t>(-1), foo.IndexOf(99));
+}
+
+TEST(UniqueVector, PushBackViaSwap) {
+  UniqueVector<std::string> vect;
+  std::string a("a");
+  EXPECT_TRUE(vect.PushBackViaSwap(&a));
+  EXPECT_EQ("", a);
+
+  a = "a";
+  EXPECT_FALSE(vect.PushBackViaSwap(&a));
+  EXPECT_EQ("a", a);
+
+  EXPECT_EQ(0u, vect.IndexOf("a"));
+}
diff --git a/tools/gn/value_extractors.cc b/tools/gn/value_extractors.cc
index 372156e..7927b83 100644
--- a/tools/gn/value_extractors.cc
+++ b/tools/gn/value_extractors.cc
@@ -9,9 +9,55 @@
 #include "tools/gn/label.h"
 #include "tools/gn/source_dir.h"
 #include "tools/gn/source_file.h"
+#include "tools/gn/target.h"
+#include "tools/gn/value.h"
 
 namespace {
 
+// Sets the error and returns false on failure.
+template<typename T, class Converter>
+bool ListValueExtractor(const Value& value,
+                        std::vector<T>* dest,
+                        Err* err,
+                        const Converter& converter) {
+  if (!value.VerifyTypeIs(Value::LIST, err))
+    return false;
+  const std::vector<Value>& input_list = value.list_value();
+  dest->resize(input_list.size());
+  for (size_t i = 0; i < input_list.size(); i++) {
+    if (!converter(input_list[i], &(*dest)[i], err))
+      return false;
+  }
+  return true;
+}
+
+// Like the above version but extracts to a UniqueVector and sets the error if
+// there are duplicates.
+template<typename T, class Converter>
+bool ListValueUniqueExtractor(const Value& value,
+                              UniqueVector<T>* dest,
+                              Err* err,
+                              const Converter& converter) {
+  if (!value.VerifyTypeIs(Value::LIST, err))
+    return false;
+  const std::vector<Value>& input_list = value.list_value();
+
+  for (size_t i = 0; i < input_list.size(); i++) {
+    T new_one;
+    if (!converter(input_list[i], &new_one, err))
+      return false;
+    if (!dest->push_back(new_one)) {
+      // Already in the list, throw error.
+      *err = Err(input_list[i], "Duplicate item in list");
+      size_t previous_index = dest->IndexOf(new_one);
+      err->AppendSubErr(Err(input_list[previous_index],
+                            "This was the previous definition."));
+      return false;
+    }
+  }
+  return true;
+}
+
 // This extractor rejects files with system-absolute file paths. If we need
 // that in the future, we'll have to add some flag to control this.
 struct RelativeFileConverter {
@@ -110,16 +156,6 @@ bool ExtractListOfRelativeDirs(const BuildSettings* build_settings,
 bool ExtractListOfLabels(const Value& value,
                          const SourceDir& current_dir,
                          const Label& current_toolchain,
-                         LabelConfigVector* dest,
-                         Err* err) {
-  return ListValueExtractor(value, dest, err,
-                            LabelResolver<Config>(current_dir,
-                                                  current_toolchain));
-}
-
-bool ExtractListOfLabels(const Value& value,
-                         const SourceDir& current_dir,
-                         const Label& current_toolchain,
                          LabelTargetVector* dest,
                          Err* err) {
   return ListValueExtractor(value, dest, err,
@@ -127,6 +163,26 @@ bool ExtractListOfLabels(const Value& value,
                                                   current_toolchain));
 }
 
+bool ExtractListOfUniqueLabels(const Value& value,
+                               const SourceDir& current_dir,
+                               const Label& current_toolchain,
+                               UniqueVector<LabelConfigPair>* dest,
+                               Err* err) {
+  return ListValueUniqueExtractor(value, dest, err,
+                                  LabelResolver<Config>(current_dir,
+                                                        current_toolchain));
+}
+
+bool ExtractListOfUniqueLabels(const Value& value,
+                               const SourceDir& current_dir,
+                               const Label& current_toolchain,
+                               UniqueVector<LabelTargetPair>* dest,
+                               Err* err) {
+  return ListValueUniqueExtractor(value, dest, err,
+                                  LabelResolver<Target>(current_dir,
+                                                        current_toolchain));
+}
+
 bool ExtractRelativeFile(const BuildSettings* build_settings,
                          const Value& value,
                          const SourceDir& current_dir,
diff --git a/tools/gn/value_extractors.h b/tools/gn/value_extractors.h
index 38c89ab..afda1d6 100644
--- a/tools/gn/value_extractors.h
+++ b/tools/gn/value_extractors.h
@@ -8,30 +8,15 @@
 #include <string>
 #include <vector>
 
-#include "tools/gn/target.h"
-#include "tools/gn/value.h"
+#include "tools/gn/label_ptr.h"
+#include "tools/gn/unique_vector.h"
 
 class BuildSettings;
 class Err;
 class Label;
 class SourceDir;
 class SourceFile;
-
-// Sets the error and returns false on failure.
-template<typename T, class Converter>
-bool ListValueExtractor(const Value& value, std::vector<T>* dest,
-                        Err* err,
-                        const Converter& converter) {
-  if (!value.VerifyTypeIs(Value::LIST, err))
-    return false;
-  const std::vector<Value>& input_list = value.list_value();
-  dest->resize(input_list.size());
-  for (size_t i = 0; i < input_list.size(); i++) {
-    if (!converter(input_list[i], &(*dest)[i], err))
-      return false;
-  }
-  return true;
-}
+class Value;
 
 // On failure, returns false and sets the error.
 bool ExtractListOfStringValues(const Value& value,
@@ -57,14 +42,23 @@ bool ExtractListOfRelativeDirs(const BuildSettings* build_settings,
 bool ExtractListOfLabels(const Value& value,
                          const SourceDir& current_dir,
                          const Label& current_toolchain,
-                         LabelConfigVector* dest,
-                         Err* err);
-bool ExtractListOfLabels(const Value& value,
-                         const SourceDir& current_dir,
-                         const Label& current_toolchain,
                          LabelTargetVector* dest,
                          Err* err);
 
+// Extracts the list of labels and their origins to the given vector. Only the
+// labels are filled in, the ptr for each pair in the vector will be null. Sets
+// an error and returns false if a label is maformed or there are duplicates.
+bool ExtractListOfUniqueLabels(const Value& value,
+                               const SourceDir& current_dir,
+                               const Label& current_toolchain,
+                               UniqueVector<LabelConfigPair>* dest,
+                               Err* err);
+bool ExtractListOfUniqueLabels(const Value& value,
+                               const SourceDir& current_dir,
+                               const Label& current_toolchain,
+                               UniqueVector<LabelTargetPair>* dest,
+                               Err* err);
+
 bool ExtractRelativeFile(const BuildSettings* build_settings,
                          const Value& value,
                          const SourceDir& current_dir,