gyp: use a set() in DeepDependencies for less O(n^2).

pylib/gyp/input.py

 # Copyright (c) 2012 Google Inc. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 from compiler.ast import Const
 from compiler.ast import Dict
 from compiler.ast import Discard
 from compiler.ast import List
 from compiler.ast import Module
 from compiler.ast import Node
@@ skipping 1584 matching lines @@
     dependencies that a dependency has advertised settings should be exported
     through the dependency for.
     """
 
     dependencies = self.DirectDependencies(dependencies)
     return self._AddImportedDependencies(targets, dependencies)
 
   def DeepDependencies(self, dependencies=None):
     """Returns a list of all of a target's dependencies, recursively."""
     if dependencies == None:
-      dependencies = []
+      # Using a list to get ordered output and a set to do fast "is it
+      # already added" checks.
+      dependencies = ([], set())
+
+    dependency_list, dependency_set = dependencies
 
     for dependency in self.dependencies:
       # Check for None, corresponding to the root node.
-      if dependency.ref != None and dependency.ref not in dependencies:
-        dependencies.append(dependency.ref)
+      if dependency.ref is None:
+        continue
+      if dependency.ref not in dependency_set:
+        dependency_list.append(dependency.ref)
+        dependency_set.add(dependency.ref)
         dependency.DeepDependencies(dependencies)
 
-    return dependencies
+    return dependency_list
 
   def _LinkDependenciesInternal(self, targets, include_shared_libraries,
                                 dependencies=None, initial=True):
     """Returns a list of dependency targets that are linked into this target.
 
     This function has a split personality, depending on the setting of
     |initial|.  Outside callers should always leave |initial| at its default
     setting.
 
     When adding a target to the list of dependencies, this function will
@@ skipping 1191 matching lines @@
     ValidateRunAsInTarget(target, target_dict, build_file)
     ValidateActionsInTarget(target, target_dict, build_file)
 
   # Generators might not expect ints.  Turn them into strs.
   TurnIntIntoStrInDict(data)
 
   # TODO(mark): Return |data| for now because the generator needs a list of
   # build files that came in.  In the future, maybe it should just accept
   # a list, and not the whole data dict.
   return [flat_list, targets, data]