win msvs: make ordering match .gyp order

pylib/gyp/generator/msvs.py

Index: pylib/gyp/generator/msvs.py
diff --git a/pylib/gyp/generator/msvs.py b/pylib/gyp/generator/msvs.py
index 0287eb19e0671d505f31a7ed2bed0b311096f296..3a1b6105d6ca9a1bd62b62bb86ba71aee19614c8 100644
--- a/pylib/gyp/generator/msvs.py
+++ b/pylib/gyp/generator/msvs.py
@@ -2,6 +2,7 @@
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
+import collections
 import copy
 import ntpath
 import os
@@ -86,6 +87,46 @@ cached_username = None
 cached_domain = None
 
 
+# Based on http://code.activestate.com/recipes/576694/.
+class OrderedSet(collections.MutableSet):
+  def __init__(self, iterable=None):
+    self.end = end = []
+    end += [None, end, end]         # sentinel node for doubly linked list
+    self.map = {}                   # key --> [key, prev, next]
+    if iterable is not None:
+      self |= iterable
+
+  def __len__(self):
+    return len(self.map)
+
+  def discard(self, key):

[Nico, 2013/12/06 20:35:54]

Is this needed?

[scottmg, 2013/12/06 20:43:46]

Yup:
http://docs.python.org/2/library/collections.html#collections-abstract-base-c...
I didn't even know there was such a thing in python. Without them it complains:

    TypeError: Can't instantiate abstract class OrderedSet with abstract methods
__len__, discard

(I could remove the bodies I guess, but that seems like asking for trouble in
the future).

+    if key in self.map:
+      key, prev, next = self.map.pop(key)
+      prev[2] = next
+      next[1] = prev
+
+  def __contains__(self, key):
+    return key in self.map
+
+  def add(self, key):
+    if key not in self.map:
+      end = self.end
+      curr = end[1]
+      curr[2] = end[1] = self.map[key] = [key, curr, end]
+
+  def update(self, iterable):
+    for i in iterable:
+      if i not in self:
+        self.add(i)
+
+  def __iter__(self):
+    end = self.end
+    curr = end[2]
+    while curr is not end:
+      yield curr[0]
+      curr = curr[2]
+
+
 # TODO(gspencer): Switch the os.environ calls to be
 # win32api.GetDomainName() and win32api.GetUserName() once the
 # python version in depot_tools has been updated to work on Vista
@@ -415,13 +456,13 @@ def _AddAccumulatedActionsToMSVS(p, spec, actions_dict):
         dicts describing the actions attached to that input file.
   """
   for primary_input in actions_dict:
-    inputs = set()
-    outputs = set()
+    inputs = OrderedSet()
+    outputs = OrderedSet()
     descriptions = []
     commands = []
     for action in actions_dict[primary_input]:
-      inputs.update(set(action['inputs']))
-      outputs.update(set(action['outputs']))
+      inputs.update(OrderedSet(action['inputs']))
+      outputs.update(OrderedSet(action['outputs']))
       descriptions.append(action['description'])
       commands.append(action['command'])
     # Add the custom build step for one input file.
@@ -477,8 +518,8 @@ def _RuleInputsAndOutputs(rule, trigger_file):
   """
   raw_inputs = _FixPaths(rule.get('inputs', []))
   raw_outputs = _FixPaths(rule.get('outputs', []))
-  inputs = set()
-  outputs = set()
+  inputs = OrderedSet()
+  outputs = OrderedSet()
   inputs.add(trigger_file)
   for i in raw_inputs:
     inputs.add(_RuleExpandPath(i, trigger_file))
@@ -549,16 +590,16 @@ def _GenerateExternalRules(rules, output_dir, spec,
   mk_file.write('OutDirCygwin:=$(shell cygpath -u "$(OutDir)")\n')
   mk_file.write('IntDirCygwin:=$(shell cygpath -u "$(IntDir)")\n')
   # Gather stuff needed to emit all: target.
-  all_inputs = set()
-  all_outputs = set()
-  all_output_dirs = set()
+  all_inputs = OrderedSet()
+  all_outputs = OrderedSet()
+  all_output_dirs = OrderedSet()
   first_outputs = []
   for rule in rules:
     trigger_files = _FindRuleTriggerFiles(rule, sources)
     for tf in trigger_files:
       inputs, outputs = _RuleInputsAndOutputs(rule, tf)
-      all_inputs.update(set(inputs))
-      all_outputs.update(set(outputs))
+      all_inputs.update(OrderedSet(inputs))
+      all_outputs.update(OrderedSet(outputs))
       # Only use one target from each rule as the dependency for
       # 'all' so we don't try to build each rule multiple times.
       first_outputs.append(list(outputs)[0])
@@ -799,8 +840,8 @@ def _AdjustSourcesForRules(spec, rules, sources, excluded_sources):
       trigger_files = _FindRuleTriggerFiles(rule, sources)
       for trigger_file in trigger_files:
         inputs, outputs = _RuleInputsAndOutputs(rule, trigger_file)
-        inputs = set(_FixPaths(inputs))
-        outputs = set(_FixPaths(outputs))
+        inputs = OrderedSet(_FixPaths(inputs))
+        outputs = OrderedSet(_FixPaths(outputs))
         inputs.remove(_FixPath(trigger_file))
         sources.update(inputs)
         if not spec.get('msvs_external_builder'):
@@ -817,7 +858,7 @@ def _FilterActionsFromExcluded(excluded_sources, actions_to_add):
   Returns:
     excluded_sources with files that have actions attached removed.
   """
-  must_keep = set(_FixPaths(actions_to_add.keys()))
+  must_keep = OrderedSet(_FixPaths(actions_to_add.keys()))
   return [s for s in excluded_sources if s not in must_keep]
 
 
@@ -965,7 +1006,7 @@ def _GetUniquePlatforms(spec):
     The MSVSUserFile object created.
   """
   # Gather list of unique platforms.
-  platforms = set()
+  platforms = OrderedSet()
   for configuration in spec['configurations']:
     platforms.add(_ConfigPlatform(spec['configurations'][configuration]))
   platforms = list(platforms)
@@ -1152,7 +1193,7 @@ def _GetLibraries(spec):
   # in libraries that are assumed to be in the default library path).
   # Also remove duplicate entries, leaving only the last duplicate, while
   # preserving order.
-  found = set()
+  found = OrderedSet()
   unique_libraries_list = []
   for entry in reversed(libraries):
     library = re.sub('^\-l', '', entry)
@@ -1331,8 +1372,7 @@ def _GetMSVSAttributes(spec, config, config_type):
 
 
 def _AddNormalizedSources(sources_set, sources_array):
-  sources = [_NormalizedSource(s) for s in sources_array]
-  sources_set.update(set(sources))
+  sources_set.update(_NormalizedSource(s) for s in sources_array)
 
 
 def _PrepareListOfSources(spec, generator_flags, gyp_file):
@@ -1350,9 +1390,9 @@ def _PrepareListOfSources(spec, generator_flags, gyp_file):
     A pair of (list of sources, list of excluded sources).
     The sources will be relative to the gyp file.
   """
-  sources = set()
+  sources = OrderedSet()
   _AddNormalizedSources(sources, spec.get('sources', []))
-  excluded_sources = set()
+  excluded_sources = OrderedSet()
   # Add in the gyp file.
   if not generator_flags.get('standalone'):
     sources.add(gyp_file)
@@ -1362,7 +1402,7 @@ def _PrepareListOfSources(spec, generator_flags, gyp_file):
     inputs = a['inputs']
     inputs = [_NormalizedSource(i) for i in inputs]
     # Add all inputs to sources and excluded sources.
-    inputs = set(inputs)
+    inputs = OrderedSet(inputs)
     sources.update(inputs)
     if not spec.get('msvs_external_builder'):
       excluded_sources.update(inputs)
@@ -1391,7 +1431,7 @@ def _AdjustSourcesAndConvertToFilterHierarchy(
                path of excluded IDL file)
   """
   # Exclude excluded sources coming into the generator.
-  excluded_sources.update(set(spec.get('sources_excluded', [])))
+  excluded_sources.update(OrderedSet(spec.get('sources_excluded', [])))
   # Add excluded sources into sources for good measure.
   sources.update(excluded_sources)
   # Convert to proper windows form.
@@ -1484,7 +1524,7 @@ def _GetExcludedFilesFromBuild(spec, excluded_sources, excluded_idl):
 
 def _AddToolFilesToMSVS(p, spec):
   # Add in tool files (rules).
-  tool_files = set()
+  tool_files = OrderedSet()
   for _, config in spec['configurations'].iteritems():
     for f in config.get('msvs_tool_files', []):
       tool_files.add(f)
@@ -3207,16 +3247,16 @@ def _GenerateActionsForMSBuild(spec, actions_to_add):
   Returns:
     A pair of (action specification, the sources handled by this action).
   """
-  sources_handled_by_action = set()
+  sources_handled_by_action = OrderedSet()
   actions_spec = []
   for primary_input, actions in actions_to_add.iteritems():
-    inputs = set()
-    outputs = set()
+    inputs = OrderedSet()
+    outputs = OrderedSet()
     descriptions = []
     commands = []
     for action in actions:
-      inputs.update(set(action['inputs']))
-      outputs.update(set(action['outputs']))
+      inputs.update(OrderedSet(action['inputs']))
+      outputs.update(OrderedSet(action['outputs']))
       descriptions.append(action['description'])
       cmd = action['command']
       # For most actions, add 'call' so that actions that invoke batch files