Store named parameters in sorted lists instead of using maps.

lib/ast.dart

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 /// -----------------------------------------------------------------------
 ///                           ERROR HANDLING
 /// -----------------------------------------------------------------------
 ///
 /// As a rule of thumb, errors that can be detected statically are handled by
 /// the frontend, typically by translating the erroneous code into a 'throw' or
@@ skipping 926 matching lines @@
   DartType get setterType {
     return isSetter
         ? function.positionalParameters[0].type
         : const BottomType();
   }
 
   _MemberAccessor get _getterInterface => _reference;
   _MemberAccessor get _setterInterface => _reference;
 }
 
-enum ProcedureKind { Method, Getter, Setter, Operator, Factory, }
+enum ProcedureKind {
+  Method,
+  Getter,
+  Setter,
+  Operator,
+  Factory,
+}
 
 // ------------------------------------------------------------------------
 //                     CONSTRUCTOR INITIALIZERS
 // ------------------------------------------------------------------------
 
 /// Part of an initializer list in a constructor.
 abstract class Initializer extends TreeNode {
   accept(InitializerVisitor v);
 }
 
@@ skipping 135 matching lines @@
 
 /// A function declares parameters and has a body.
 ///
 /// This may occur in a procedure, constructor, function expression, or local
 /// function declaration.
 class FunctionNode extends TreeNode {
   AsyncMarker asyncMarker;
   List<TypeParameter> typeParameters;
   int requiredParameterCount;
   List<VariableDeclaration> positionalParameters;
-  List<VariableDeclaration> namedParameters;
+  List<VariableDeclaration> namedParameters; // Must be sorted.
   InferredValue inferredReturnValue; // May be null.
   DartType returnType; // Not null.
   Statement body;
 
   FunctionNode(this.body,
       {List<TypeParameter> typeParameters,
       List<VariableDeclaration> positionalParameters,
       List<VariableDeclaration> namedParameters,
       int requiredParameterCount,
       this.returnType: const DynamicType(),
       this.inferredReturnValue,
       this.asyncMarker: AsyncMarker.Sync})
       : this.positionalParameters =
             positionalParameters ?? <VariableDeclaration>[],
         this.requiredParameterCount =
             requiredParameterCount ?? positionalParameters?.length ?? 0,
         this.namedParameters = namedParameters ?? <VariableDeclaration>[],
         this.typeParameters = typeParameters ?? <TypeParameter>[] {
     assert(returnType != null);
     setParents(this.typeParameters, this);
     setParents(this.positionalParameters, this);
     setParents(this.namedParameters, this);
     body?.parent = this;
   }
 
   static DartType _getTypeOfVariable(VariableDeclaration node) => node.type;
 
+  static NamedType _getNamedTypeOfVariable(VariableDeclaration node) {
+    return new NamedType(node.name, node.type);
+  }
+
   FunctionType get functionType {
     Map<String, DartType> named = const <String, DartType>{};
     if (namedParameters.isNotEmpty) {
       named = <String, DartType>{};
       for (var node in namedParameters) {
         named[node.name] = node.type;
       }
     }
     TreeNode parent = this.parent;
     return new FunctionType(
         positionalParameters.map(_getTypeOfVariable).toList(), returnType,
-        namedParameters: named,
+        namedParameters: namedParameters.map(_getNamedTypeOfVariable).toList(),
         typeParameters: parent is Constructor
             ? parent.enclosingClass.typeParameters
             : typeParameters,
         requiredParameterCount: requiredParameterCount);
   }
 
   accept(TreeVisitor v) => v.visitFunctionNode(this);
 
   visitChildren(Visitor v) {
     visitList(typeParameters, v);
@@ skipping 821 matching lines @@
 
 /// Expression of form `x ? y : z`.
 class ConditionalExpression extends Expression {
   Expression condition;
   Expression then;
   Expression otherwise;
 
   /// The static type of the expression. Should not be `null`.
   DartType staticType;
 
-  ConditionalExpression(this.condition, this.then, this.otherwise,
-      this.staticType) {
+  ConditionalExpression(
+      this.condition, this.then, this.otherwise, this.staticType) {
     condition?.parent = this;
     then?.parent = this;
     otherwise?.parent = this;
   }
 
   DartType getStaticType(TypeEnvironment types) => staticType;
 
   accept(ExpressionVisitor v) => v.visitConditionalExpression(this);
 
   visitChildren(Visitor v) {
@@ skipping 960 matching lines @@
 }
 
 /// Declaration of a local variable.
 ///
 /// This may occur as a statement, but is also used in several non-statement
 /// contexts, such as in [ForStatement], [Catch], and [FunctionNode].
 ///
 /// When this occurs as a statement, it must be a direct child of a [Block].
 //
 // DESIGN TODO: Should we remove the 'final' modifier from variables?
-class VariableDeclaration extends Statement {
+class VariableDeclaration extends Statement
+    implements Comparable<VariableDeclaration> {
   /// For named parameters, this is the name of the parameter. No two named
   /// parameters (in the same parameter list) can have the same name.
   ///
   /// In all other cases, the name is cosmetic, may be empty or null,
   /// and is not necessarily unique.
   String name;
   int flags = 0;
   DartType type; // Not null, defaults to dynamic.
   InferredValue inferredValue; // May be null.
 
@@ skipping 52 matching lines @@
     type = v.visitDartType(type);
     if (initializer != null) {
       initializer = initializer.accept(v);
       initializer?.parent = this;
     }
   }
 
   /// Returns a possibly synthesized name for this variable, consistent with
   /// the names used across all [toString] calls.
   String toString() => debugVariableDeclarationName(this);
+
+  int compareTo(VariableDeclaration other) {
+    return name.compareTo(other.name);
+  }
 }
 
 /// Declaration a local function.
 ///
 /// The body of the function may use [variable] as its self-reference.
 class FunctionDeclaration extends Statement {
   VariableDeclaration variable; // Is final and has no initializer.
   FunctionNode function;
 
   FunctionDeclaration(this.variable, this.function) {
@@ skipping 206 matching lines @@
     }
     return hash;
   }
 }
 
 /// A possibly generic function type.
 class FunctionType extends DartType {
   final List<TypeParameter> typeParameters;
   final int requiredParameterCount;
   final List<DartType> positionalParameters;
-  final Map<String, DartType> namedParameters;
+  final List<NamedType> namedParameters; // Must be sorted.
   final DartType returnType;
   int _hashCode;
 
   FunctionType(List<DartType> positionalParameters, this.returnType,
-      {this.namedParameters: const <String, DartType>{},
+      {this.namedParameters: const <NamedType>[],
       this.typeParameters: const <TypeParameter>[],
       int requiredParameterCount})
       : this.positionalParameters = positionalParameters,
         this.requiredParameterCount =
             requiredParameterCount ?? positionalParameters.length;
 
   accept(DartTypeVisitor v) => v.visitFunctionType(this);
 
   visitChildren(Visitor v) {
     visitList(typeParameters, v);
     visitList(positionalParameters, v);
-    visitIterable(namedParameters.values, v);
+    visitList(namedParameters, v);
     returnType.accept(v);
   }
 
   bool operator ==(Object other) {
     if (identical(this, other)) return true;
     if (other is FunctionType) {
       if (typeParameters.length != other.typeParameters.length ||
           requiredParameterCount != other.requiredParameterCount ||
           positionalParameters.length != other.positionalParameters.length ||
           namedParameters.length != other.namedParameters.length) {
         return false;
       }
       if (typeParameters.isEmpty) {
         for (int i = 0; i < positionalParameters.length; ++i) {
           if (positionalParameters[i] != other.positionalParameters[i]) {
             return false;
           }
         }
-        for (var name in namedParameters.keys) {
-          // If the other function type declared differently named parameters,
-          // one side of this equality will be null and we're good.
-          if (namedParameters[name] != other.namedParameters[name]) {
+        for (int i = 0; i < namedParameters.length; ++i) {
+          if (namedParameters[i] != other.namedParameters[i]) {
             return false;
           }
         }
         return returnType == other.returnType;
       } else {
         // Structural equality does not tell us if two generic function types
         // are the same type.  If they are unifiable without substituting any
         // type variables, they are equal.
         return unifyTypes(this, other, new Set<TypeParameter>()) != null;
       }
@@ skipping 20 matching lines @@
     int hash = 1237;
     hash = 0x3fffffff & (hash * 31 + requiredParameterCount);
     for (int i = 0; i < typeParameters.length; ++i) {
       TypeParameter parameter = typeParameters[i];
       _temporaryHashCodeTable[parameter] = _temporaryHashCodeTable.length;
       hash = 0x3fffffff & (hash * 31 + parameter.bound.hashCode);
     }
     for (int i = 0; i < positionalParameters.length; ++i) {
       hash = 0x3fffffff & (hash * 31 + positionalParameters[i].hashCode);
     }
-    // TODO: Using a sorted list of names would be better than a map here.
-    namedParameters.forEach((String name, DartType type) {
-      // Note that we use only addition and truncation here, so that we do not
-      // rely on the iteration of the of the map.
-      hash = 0x3fffffff & (hash + name.hashCode);
-      hash = 0x3fffffff & (hash + type.hashCode);
-    });
+    for (int i = 0; i < namedParameters.length; ++i) {
+      hash = 0x3fffffff & (hash * 31 + namedParameters[i].hashCode);
+    }
     hash = 0x3fffffff & (hash * 31 + returnType.hashCode);
     for (int i = 0; i < typeParameters.length; ++i) {
       // Remove the type parameters from the scope again.
       _temporaryHashCodeTable.remove(typeParameters[i]);
     }
     return hash;
   }
 }
 
+/// A named parameter in [FunctionType].
+class NamedType extends Node implements Comparable<NamedType> {
+  final String name;
+  final DartType type;
+
+  NamedType(this.name, this.type);
+
+  bool operator ==(Object other) {
+    return other is NamedType && name == other.name && type == other.type;
+  }
+
+  int get hashCode {
+    return name.hashCode * 31 + type.hashCode * 37;
+  }
+
+  int compareTo(NamedType other) => name.compareTo(other.name);
+
+  accept(Visitor v) => v.visitNamedType(this);
+
+  void visitChildren(Visitor v) {
+    type.accept(v);
+  }
+}
+
 /// Stores the hash code of function type parameters while computing the hash
 /// code of a [FunctionType] object.
 ///
 /// This ensures that distinct [FunctionType] objects get the same hash code
 /// if they represent the same type, even though their type parameters are
 /// represented by different objects.
 final Map<TypeParameter, int> _temporaryHashCodeTable = <TypeParameter, int>{};
 
 /// Reference to a type variable.
 class TypeParameterType extends DartType {
@@ skipping 235 matching lines @@
 
   @override
   defaultTreeNode(TreeNode node) {
     if (node == child) {
       return replacement;
     } else {
       return node;
     }
   }
 }