win msvs: make ordering match .gyp order

pylib/gyp/generator/msvs.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.
 
+import collections
 import copy
 import ntpath
 import os
 import posixpath
 import re
 import subprocess
 import sys
 
 import gyp.common
 import gyp.easy_xml as easy_xml
@@ skipping 64 matching lines @@
     'msvs_precompiled_source',
 ]
 
 
 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
 # 64-bit.
 def _GetDomainAndUserName():
   if sys.platform not in ('win32', 'cygwin'):
     return ('DOMAIN', 'USERNAME')
   global cached_username
   global cached_domain
   if not cached_domain or not cached_username:
@@ skipping 309 matching lines @@
 def _AddAccumulatedActionsToMSVS(p, spec, actions_dict):
   """Add actions accumulated into an actions_dict, merging as needed.
 
   Arguments:
     p: the target project
     spec: the target project dict
     actions_dict: dictionary keyed on input name, which maps to a list of
         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.
     description = ', and also '.join(descriptions)
     command = '\r\n'.join(commands)
     _AddCustomBuildToolForMSVS(p, spec,
                                primary_input=primary_input,
                                inputs=inputs,
                                outputs=outputs,
                                description=description,
@@ skipping 35 matching lines @@
   """Find the inputs and outputs generated by a rule.
 
   Arguments:
     rule: the rule in question.
     trigger_file: the main trigger for this rule.
   Returns:
     The pair of (inputs, outputs) involved in this rule.
   """
   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))
   for o in raw_outputs:
     outputs.add(_RuleExpandPath(o, trigger_file))
   return (inputs, outputs)
 
 
 def _GenerateNativeRulesForMSVS(p, rules, output_dir, spec, options):
   """Generate a native rules file.
@@ skipping 50 matching lines @@
     sources: set of sources known
     options: global generator options
     actions_to_add: The list of actions we will add to.
   """
   filename = '%s_rules%s.mk' % (spec['target_name'], options.suffix)
   mk_file = gyp.common.WriteOnDiff(os.path.join(output_dir, filename))
   # Find cygwin style versions of some paths.
   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])
       # Get the unique output directories for this rule.
       output_dirs = [os.path.split(i)[0] for i in outputs]
       for od in output_dirs:
         all_output_dirs.add(od)
   first_outputs_cyg = [_Cygwinify(i) for i in first_outputs]
   # Write out all: target, including mkdir for each output directory.
   mk_file.write('all: %s\n' % ' '.join(first_outputs_cyg))
@@ skipping 220 matching lines @@
 
 def _AdjustSourcesForRules(spec, rules, sources, excluded_sources):
   # Add outputs generated by each rule (if applicable).
   for rule in rules:
     # Done if not processing outputs as sources.
     if int(rule.get('process_outputs_as_sources', False)):
       # Add in the outputs from this rule.
       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'):
           excluded_sources.update(inputs)
         sources.update(outputs)
 
 
 def _FilterActionsFromExcluded(excluded_sources, actions_to_add):
   """Take inputs with actions attached out of the list of exclusions.
 
   Arguments:
     excluded_sources: list of source files not to be built.
     actions_to_add: dict of actions keyed on source file they're attached to.
   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]
 
 
 def _GetDefaultConfiguration(spec):
   return spec['configurations'][spec['default_configuration']]
 
 
 def _GetGuidOfProject(proj_path, spec):
   """Get the guid for the project.
 
@@ skipping 127 matching lines @@
 
 def _GetUniquePlatforms(spec):
   """Returns the list of unique platforms for this spec, e.g ['win32', ...].
 
   Arguments:
     spec: The target dictionary containing the properties of the target.
   Returns:
     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)
   return platforms
 
 
 def _CreateMSVSUserFile(proj_path, version, spec):
   """Generates a .user file for the user running this Gyp program.
 
   Arguments:
@@ skipping 166 matching lines @@
   Arguments:
     spec: The target dictionary containing the properties of the target.
   Returns:
     The list of directory paths.
   """
   libraries = spec.get('libraries', [])
   # Strip out -l, as it is not used on windows (but is needed so we can pass
   # 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)
     if not os.path.splitext(library)[1]:
       library += '.lib'
     if library not in found:
       found.add(library)
       unique_libraries_list.append(library)
   unique_libraries_list.reverse()
   return unique_libraries_list
@@ skipping 158 matching lines @@
     intermediate = '$(ConfigurationName)\\obj\\$(ProjectName)'
     prepared_attrs['IntermediateDirectory'] = _FixPath(intermediate) + '\\'
   else:
     intermediate = _FixPath(prepared_attrs['IntermediateDirectory']) + '\\'
     intermediate = MSVSSettings.FixVCMacroSlashes(intermediate)
     prepared_attrs['IntermediateDirectory'] = intermediate
   return prepared_attrs
 
 
 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):
   """Prepare list of sources and excluded sources.
 
   Besides the sources specified directly in the spec, adds the gyp file so
   that a change to it will cause a re-compile. Also adds appropriate sources
   for actions and copies. Assumes later stage will un-exclude files which
   have custom build steps attached.
 
   Arguments:
     spec: The target dictionary containing the properties of the target.
     gyp_file: The name of the gyp file.
   Returns:
     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)
 
   # Add in 'action' inputs and outputs.
   for a in spec.get('actions', []):
     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)
     if int(a.get('process_outputs_as_sources', False)):
       _AddNormalizedSources(sources, a.get('outputs', []))
   # Add in 'copies' inputs and outputs.
   for cpy in spec.get('copies', []):
     _AddNormalizedSources(sources, cpy.get('files', []))
   return (sources, excluded_sources)
 
 
 def _AdjustSourcesAndConvertToFilterHierarchy(
     spec, options, gyp_dir, sources, excluded_sources, list_excluded):
   """Adjusts the list of sources and excluded sources.
 
   Also converts the sets to lists.
 
   Arguments:
     spec: The target dictionary containing the properties of the target.
     options: Global generator options.
     gyp_dir: The path to the gyp file being processed.
     sources: A set of sources to be included for this project.
     excluded_sources: A set of sources to be excluded for this project.
   Returns:
     A trio of (list of sources, list of excluded sources,
                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.
   # NOTE: sources goes from being a set to a list here.
   # NOTE: excluded_sources goes from being a set to a list here.
   sources = _FixPaths(sources)
   # Convert to proper windows form.
   excluded_sources = _FixPaths(excluded_sources)
 
   excluded_idl = _IdlFilesHandledNonNatively(spec, sources)
@@ skipping 72 matching lines @@
   for f in excluded_idl:
     excluded_configs = []
     for config_name, config in spec['configurations'].iteritems():
       excluded_configs.append((config_name, config))
     exclusions[f] = excluded_configs
   return exclusions
 
 
 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)
   for f in tool_files:
     p.AddToolFile(f)
 
 
 def _HandlePreCompiledHeaders(p, sources, spec):
   # Pre-compiled header source stubs need a different compiler flag
   # (generate precompiled header) and any source file not of the same
@@ skipping 1702 matching lines @@
   """Add actions accumulated into an actions_to_add, merging as needed.
 
   Arguments:
     spec: the target project dict
     actions_to_add: dictionary keyed on input name, which maps to a list of
         dicts describing the actions attached to that input file.
 
   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
       # return and continue executing.  msbuild_use_call provides a way to
       # disable this but I have not seen any adverse effect from doing that
       # for everything.
       if action.get('msbuild_use_call', True):
         cmd = 'call ' + cmd
       commands.append(cmd)
     # Add the custom build action for one input file.
@@ skipping 30 matching lines @@
   action_spec.extend(
       # TODO(jeanluc) 'Document' for all or just if as_sources?
       [['FileType', 'Document'],
        ['Command', command],
        ['Message', description],
        ['Outputs', outputs]
       ])
   if additional_inputs:
     action_spec.append(['AdditionalInputs', additional_inputs])
   actions_spec.append(action_spec)