sdk/lib/_internal/compiler/implementation/js_emitter/type_test_emitter.dart - sdk.git - Git at Google

 // Copyright (c) 2013, 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.

 part of dart2js.js_emitter;

 class TypeTestEmitter extends CodeEmitterHelper {
   static const int MAX_FUNCTION_TYPE_PREDICATES = 10;

   /**
    * Raw ClassElement symbols occuring in is-checks and type assertions.  If the
    * program contains parameterized checks `x is Set<int>` and
    * `x is Set<String>` then the ClassElement `Set` will occur once in
    * [checkedClasses].
    */
   Set<ClassElement> checkedClasses;

   /**
    * The set of function types that checked, both explicity through tests of
    * typedefs and implicitly through type annotations in checked mode.
    */
   Set<FunctionType> checkedFunctionTypes;

   Map<ClassElement, Set<FunctionType>> checkedGenericFunctionTypes =
       new Map<ClassElement, Set<FunctionType>>();

   Set<FunctionType> checkedNonGenericFunctionTypes =
       new Set<FunctionType>();

   final Set<ClassElement> rtiNeededClasses = new Set<ClassElement>();

   Iterable<ClassElement> cachedClassesUsingTypeVariableTests;

   Iterable<ClassElement> get classesUsingTypeVariableTests {
     if (cachedClassesUsingTypeVariableTests == null) {
       cachedClassesUsingTypeVariableTests = compiler.codegenWorld.isChecks
           .where((DartType t) => t is TypeVariableType)
           .map((TypeVariableType v) => v.element.getEnclosingClass())
           .toList();
     }
     return cachedClassesUsingTypeVariableTests;
   }

   void emitIsTests(ClassElement classElement, ClassBuilder builder) {
     assert(invariant(classElement, classElement.isDeclaration));

     void generateIsTest(Element other) {
       if (other == compiler.objectClass && other != classElement) {
         // Avoid emitting [:$isObject:] on all classes but [Object].
         return;
       }
       other = backend.getImplementationClass(other);
       builder.addProperty(namer.operatorIs(other), js('true'));
     }

     void generateFunctionTypeSignature(Element method, FunctionType type) {
       assert(method.isImplementation);
       jsAst.Expression thisAccess = new jsAst.This();
       ClosureClassMap closureData;
       // TODO(lry): Once the IR can express methods containing closures, find
       // a way to get the [:thisName:]. The solution to this problem depends on
       // how closures are represented in the IR, which is not yet decided.
       if (!compiler.irBuilder.hasIr(method)) {
         Node node = method.parseNode(compiler);
         closureData = compiler.closureToClassMapper.closureMappingCache[node];
       }
       if (closureData != null) {
         Element thisElement =
             closureData.freeVariableMapping[closureData.thisElement];
         if (thisElement != null) {
           String thisName = namer.instanceFieldPropertyName(thisElement);
           thisAccess = js('this')[js.string(thisName)];
         }
       }
       RuntimeTypes rti = backend.rti;
       jsAst.Expression encoding = rti.getSignatureEncoding(type, thisAccess);
       String operatorSignature = namer.operatorSignature();
       if (!type.containsTypeVariables) {
         builder.functionType = '${task.metadataEmitter.reifyType(type)}';
       } else {
         builder.addProperty(operatorSignature, encoding);
       }
     }

     void generateSubstitution(ClassElement cls, {bool emitNull: false}) {
       if (cls.typeVariables.isEmpty) return;
       RuntimeTypes rti = backend.rti;
       jsAst.Expression expression;
       bool needsNativeCheck = task.nativeEmitter.requiresNativeIsCheck(cls);
       expression = rti.getSupertypeSubstitution(
           classElement, cls, alwaysGenerateFunction: true);
       if (expression == null && (emitNull || needsNativeCheck)) {
         expression = new jsAst.LiteralNull();
       }
       if (expression != null) {
         builder.addProperty(namer.substitutionName(cls), expression);
       }
     }

     generateIsTestsOn(classElement, generateIsTest,
         generateFunctionTypeSignature,
         generateSubstitution);
   }

   /**
    * Generate "is tests" for [cls]: itself, and the "is tests" for the
    * classes it implements and type argument substitution functions for these
    * tests.   We don't need to add the "is tests" of the super class because
    * they will be inherited at runtime, but we may need to generate the
    * substitutions, because they may have changed.
    */
   void generateIsTestsOn(ClassElement cls,
                          void emitIsTest(Element element),
                          FunctionTypeSignatureEmitter emitFunctionTypeSignature,
                          SubstitutionEmitter emitSubstitution) {
     if (checkedClasses.contains(cls)) {
       emitIsTest(cls);
       emitSubstitution(cls);
     }

     RuntimeTypes rti = backend.rti;
     ClassElement superclass = cls.superclass;

     bool haveSameTypeVariables(ClassElement a, ClassElement b) {
       if (a.isClosure()) return true;
       return a.typeVariables == b.typeVariables;
     }

     if (superclass != null && superclass != compiler.objectClass &&
         !haveSameTypeVariables(cls, superclass)) {
       // We cannot inherit the generated substitutions, because the type
       // variable layout for this class is different.  Instead we generate
       // substitutions for all checks and make emitSubstitution a NOP for the
       // rest of this function.
       Set<ClassElement> emitted = new Set<ClassElement>();
       // TODO(karlklose): move the computation of these checks to
       // RuntimeTypeInformation.
       if (backend.classNeedsRti(cls)) {
         emitSubstitution(superclass, emitNull: true);
         emitted.add(superclass);
       }
       for (DartType supertype in cls.allSupertypes) {
         ClassElement superclass = supertype.element;
         if (classesUsingTypeVariableTests.contains(superclass)) {
           emitSubstitution(superclass, emitNull: true);
           emitted.add(superclass);
         }
         for (ClassElement check in checkedClasses) {
           if (supertype.element == check && !emitted.contains(check)) {
             // Generate substitution.  If no substitution is necessary, emit
             // [:null:] to overwrite a (possibly) existing substitution from the
             // super classes.
             emitSubstitution(check, emitNull: true);
             emitted.add(check);
           }
         }
       }
       void emitNothing(_, {emitNull}) {};
       emitSubstitution = emitNothing;
     }

     Set<Element> generated = new Set<Element>();
     // A class that defines a [:call:] method implicitly implements
     // [Function] and needs checks for all typedefs that are used in is-checks.
     if (checkedClasses.contains(compiler.functionClass) ||
         !checkedFunctionTypes.isEmpty) {
       Element call = cls.lookupLocalMember(Compiler.CALL_OPERATOR_NAME);
       if (call == null) {
         // If [cls] is a closure, it has a synthetic call operator method.
         call = cls.lookupBackendMember(Compiler.CALL_OPERATOR_NAME);
       }
       if (call != null && call.isFunction()) {
         generateInterfacesIsTests(compiler.functionClass,
                                   emitIsTest,
                                   emitSubstitution,
                                   generated);
         FunctionType callType = call.computeType(compiler);
         Map<FunctionType, bool> functionTypeChecks =
             getFunctionTypeChecksOn(callType);
         generateFunctionTypeTests(
             call, callType, functionTypeChecks,
             emitFunctionTypeSignature);
      }
     }

     for (DartType interfaceType in cls.interfaces) {
       generateInterfacesIsTests(interfaceType.element, emitIsTest,
                                 emitSubstitution, generated);
     }
   }

   /**
    * Generate "is tests" where [cls] is being implemented.
    */
   void generateInterfacesIsTests(ClassElement cls,
                                  void emitIsTest(ClassElement element),
                                  SubstitutionEmitter emitSubstitution,
                                  Set<Element> alreadyGenerated) {
     void tryEmitTest(ClassElement check) {
       if (!alreadyGenerated.contains(check) && checkedClasses.contains(check)) {
         alreadyGenerated.add(check);
         emitIsTest(check);
         emitSubstitution(check);
       }
     };

     tryEmitTest(cls);

     for (DartType interfaceType in cls.interfaces) {
       Element element = interfaceType.element;
       tryEmitTest(element);
       generateInterfacesIsTests(element, emitIsTest, emitSubstitution,
                                 alreadyGenerated);
     }

     // We need to also emit "is checks" for the superclass and its supertypes.
     ClassElement superclass = cls.superclass;
     if (superclass != null) {
       tryEmitTest(superclass);
       generateInterfacesIsTests(superclass, emitIsTest, emitSubstitution,
                                 alreadyGenerated);
     }
   }

   /**
    * Returns a mapping containing all checked function types for which [type]
    * can be a subtype. A function type is mapped to [:true:] if [type] is
    * statically known to be a subtype of it and to [:false:] if [type] might
    * be a subtype, provided with the right type arguments.
    */
   // TODO(johnniwinther): Change to return a mapping from function types to
   // a set of variable points and use this to detect statically/dynamically
   // known subtype relations.
   Map<FunctionType, bool> getFunctionTypeChecksOn(DartType type) {
     Map<FunctionType, bool> functionTypeMap = new Map<FunctionType, bool>();
     for (FunctionType functionType in checkedFunctionTypes) {
       int maybeSubtype = compiler.types.computeSubtypeRelation(type, functionType);
       if (maybeSubtype == Types.IS_SUBTYPE) {
         functionTypeMap[functionType] = true;
       } else if (maybeSubtype == Types.MAYBE_SUBTYPE) {
         functionTypeMap[functionType] = false;
       }
     }
     // TODO(johnniwinther): Ensure stable ordering of the keys.
     return functionTypeMap;
   }

   /**
    * Generates function type checks on [method] with type [methodType] against
    * the function type checks in [functionTypeChecks].
    */
   void generateFunctionTypeTests(
       Element method,
       FunctionType methodType,
       Map<FunctionType, bool> functionTypeChecks,
       FunctionTypeSignatureEmitter emitFunctionTypeSignature) {

     // TODO(ahe): We should be able to remove this forEach loop.
     functionTypeChecks.forEach((FunctionType functionType, bool knownSubtype) {
       registerDynamicFunctionTypeCheck(functionType);
     });

     emitFunctionTypeSignature(method, methodType);
   }

   void registerDynamicFunctionTypeCheck(FunctionType functionType) {
     ClassElement classElement = Types.getClassContext(functionType);
     if (classElement != null) {
       checkedGenericFunctionTypes.putIfAbsent(classElement,
           () => new Set<FunctionType>()).add(functionType);
     } else {
       checkedNonGenericFunctionTypes.add(functionType);
     }
   }

   void emitRuntimeTypeSupport(CodeBuffer buffer) {
     task.addComment('Runtime type support', buffer);
     RuntimeTypes rti = backend.rti;
     TypeChecks typeChecks = rti.requiredChecks;

     // Add checks to the constructors of instantiated classes.
     for (ClassElement cls in typeChecks) {
       // TODO(9556).  The properties added to 'holder' should be generated
       // directly as properties of the class object, not added later.
       String holder = namer.isolateAccess(backend.getImplementationClass(cls));
       for (TypeCheck check in typeChecks[cls]) {
         ClassElement cls = check.cls;
         buffer.write('$holder.${namer.operatorIs(cls)}$_=${_}true$N');
         Substitution substitution = check.substitution;
         if (substitution != null) {
           CodeBuffer body =
              jsAst.prettyPrint(substitution.getCode(rti, false), compiler);
           buffer.write('$holder.${namer.substitutionName(cls)}$_=${_}');
           buffer.write(body);
           buffer.write('$N');
         }
       };
     }

     void addSignature(FunctionType type) {
       jsAst.Expression encoding = rti.getTypeEncoding(type);
       buffer.add('${namer.signatureName(type)}$_=${_}');
       buffer.write(jsAst.prettyPrint(encoding, compiler));
       buffer.add('$N');
     }

     checkedNonGenericFunctionTypes.forEach(addSignature);

     checkedGenericFunctionTypes.forEach((_, Set<FunctionType> functionTypes) {
       functionTypes.forEach(addSignature);
     });
   }

   /**
    * Returns the classes with constructors used as a 'holder' in
    * [emitRuntimeTypeSupport].
    * TODO(9556): Some cases will go away when the class objects are created as
    * complete.  Not all classes will go away while constructors are referenced
    * from type substitutions.
    */
   Set<ClassElement> classesModifiedByEmitRuntimeTypeSupport() {
     TypeChecks typeChecks = backend.rti.requiredChecks;
     Set<ClassElement> result = new Set<ClassElement>();
     for (ClassElement cls in typeChecks) {
       for (TypeCheck check in typeChecks[cls]) {
         result.add(backend.getImplementationClass(cls));
         break;
       }
     }
     return result;
   }

   Set<ClassElement> computeRtiNeededClasses() {
     void addClassWithSuperclasses(ClassElement cls) {
       rtiNeededClasses.add(cls);
       for (ClassElement superclass = cls.superclass;
           superclass != null;
           superclass = superclass.superclass) {
         rtiNeededClasses.add(superclass);
       }
     }

     void addClassesWithSuperclasses(Iterable<ClassElement> classes) {
       for (ClassElement cls in classes) {
         addClassWithSuperclasses(cls);
       }
     }

     // 1.  Add classes that are referenced by type arguments or substitutions in
     //     argument checks.
     // TODO(karlklose): merge this case with 2 when unifying argument and
     // object checks.
     RuntimeTypes rti = backend.rti;
     rti.getRequiredArgumentClasses(backend).forEach((ClassElement c) {
       // Types that we represent with JS native types (like int and String) do
       // not need a class definition as we use the interceptor classes instead.
       if (!rti.isJsNative(c)) {
         addClassWithSuperclasses(c);
       }
     });

     // 2.  Add classes that are referenced by substitutions in object checks and
     //     their superclasses.
     TypeChecks requiredChecks =
         rti.computeChecks(rtiNeededClasses, checkedClasses);
     Set<ClassElement> classesUsedInSubstitutions =
         rti.getClassesUsedInSubstitutions(backend, requiredChecks);
     addClassesWithSuperclasses(classesUsedInSubstitutions);

     // 3.  Add classes that contain checked generic function types. These are
     //     needed to store the signature encoding.
     for (FunctionType type in checkedFunctionTypes) {
       ClassElement contextClass = Types.getClassContext(type);
       if (contextClass != null) {
         rtiNeededClasses.add(contextClass);
       }
     }

     bool canTearOff(Element function) {
       if (!function.isFunction() ||
           function.isConstructor() ||
           function.isAccessor()) {
         return false;
       } else if (function.isInstanceMember()) {
         if (!function.getEnclosingClass().isClosure()) {
           return compiler.codegenWorld.hasInvokedGetter(function, compiler);
         }
       }
       return false;
     }

     backend.generatedCode.keys.where((element) {
       return element is FunctionElement &&
           element is! ConstructorBodyElement &&
           (canTearOff(element) || backend.isAccessibleByReflection(element));
     }).forEach((FunctionElement function) {
       DartType type = function.computeType(compiler);
       for (ClassElement cls in backend.rti.getReferencedClasses(type)) {
         while (cls != null) {
           rtiNeededClasses.add(cls);
           cls = cls.superclass;
         }
       }
     });

     return rtiNeededClasses;
   }

   void computeRequiredTypeChecks() {
     assert(checkedClasses == null && checkedFunctionTypes == null);

     backend.rti.addImplicitChecks(compiler.codegenWorld,
                                   classesUsingTypeVariableTests);

     checkedClasses = new Set<ClassElement>();
     checkedFunctionTypes = new Set<FunctionType>();
     compiler.codegenWorld.isChecks.forEach((DartType t) {
       if (t is InterfaceType) {
         checkedClasses.add(t.element);
       } else if (t is FunctionType) {
         checkedFunctionTypes.add(t);
       }
     });
   }
 }
	// Copyright (c) 2013, 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.

	part of dart2js.js_emitter;

	class TypeTestEmitter extends CodeEmitterHelper {
	static const int MAX_FUNCTION_TYPE_PREDICATES = 10;

	/**
	* Raw ClassElement symbols occuring in is-checks and type assertions. If the
	* program contains parameterized checks `x is Set<int>` and
	* `x is Set<String>` then the ClassElement `Set` will occur once in
	* [checkedClasses].
	*/
	Set<ClassElement> checkedClasses;

	/**
	* The set of function types that checked, both explicity through tests of
	* typedefs and implicitly through type annotations in checked mode.
	*/
	Set<FunctionType> checkedFunctionTypes;

	Map<ClassElement, Set<FunctionType>> checkedGenericFunctionTypes =
	new Map<ClassElement, Set<FunctionType>>();

	Set<FunctionType> checkedNonGenericFunctionTypes =
	new Set<FunctionType>();

	final Set<ClassElement> rtiNeededClasses = new Set<ClassElement>();

	Iterable<ClassElement> cachedClassesUsingTypeVariableTests;

	Iterable<ClassElement> get classesUsingTypeVariableTests {
	if (cachedClassesUsingTypeVariableTests == null) {
	cachedClassesUsingTypeVariableTests = compiler.codegenWorld.isChecks
	.where((DartType t) => t is TypeVariableType)
	.map((TypeVariableType v) => v.element.getEnclosingClass())
	.toList();
	}
	return cachedClassesUsingTypeVariableTests;
	}

	void emitIsTests(ClassElement classElement, ClassBuilder builder) {
	assert(invariant(classElement, classElement.isDeclaration));

	void generateIsTest(Element other) {
	if (other == compiler.objectClass && other != classElement) {
	// Avoid emitting [:$isObject:] on all classes but [Object].
	return;
	}
	other = backend.getImplementationClass(other);
	builder.addProperty(namer.operatorIs(other), js('true'));
	}

	void generateFunctionTypeSignature(Element method, FunctionType type) {
	assert(method.isImplementation);
	jsAst.Expression thisAccess = new jsAst.This();
	ClosureClassMap closureData;
	// TODO(lry): Once the IR can express methods containing closures, find
	// a way to get the [:thisName:]. The solution to this problem depends on
	// how closures are represented in the IR, which is not yet decided.
	if (!compiler.irBuilder.hasIr(method)) {
	Node node = method.parseNode(compiler);
	closureData = compiler.closureToClassMapper.closureMappingCache[node];
	}
	if (closureData != null) {
	Element thisElement =
	closureData.freeVariableMapping[closureData.thisElement];
	if (thisElement != null) {
	String thisName = namer.instanceFieldPropertyName(thisElement);
	thisAccess = js('this')[js.string(thisName)];
	}
	}
	RuntimeTypes rti = backend.rti;
	jsAst.Expression encoding = rti.getSignatureEncoding(type, thisAccess);
	String operatorSignature = namer.operatorSignature();
	if (!type.containsTypeVariables) {
	builder.functionType = '${task.metadataEmitter.reifyType(type)}';
	} else {
	builder.addProperty(operatorSignature, encoding);
	}
	}

	void generateSubstitution(ClassElement cls, {bool emitNull: false}) {
	if (cls.typeVariables.isEmpty) return;
	RuntimeTypes rti = backend.rti;
	jsAst.Expression expression;
	bool needsNativeCheck = task.nativeEmitter.requiresNativeIsCheck(cls);
	expression = rti.getSupertypeSubstitution(
	classElement, cls, alwaysGenerateFunction: true);
	if (expression == null && (emitNull \|\| needsNativeCheck)) {
	expression = new jsAst.LiteralNull();
	}
	if (expression != null) {
	builder.addProperty(namer.substitutionName(cls), expression);
	}
	}

	generateIsTestsOn(classElement, generateIsTest,
	generateFunctionTypeSignature,
	generateSubstitution);
	}

	/**
	* Generate "is tests" for [cls]: itself, and the "is tests" for the
	* classes it implements and type argument substitution functions for these
	* tests. We don't need to add the "is tests" of the super class because
	* they will be inherited at runtime, but we may need to generate the
	* substitutions, because they may have changed.
	*/
	void generateIsTestsOn(ClassElement cls,
	void emitIsTest(Element element),
	FunctionTypeSignatureEmitter emitFunctionTypeSignature,
	SubstitutionEmitter emitSubstitution) {
	if (checkedClasses.contains(cls)) {
	emitIsTest(cls);
	emitSubstitution(cls);
	}

	RuntimeTypes rti = backend.rti;
	ClassElement superclass = cls.superclass;

	bool haveSameTypeVariables(ClassElement a, ClassElement b) {
	if (a.isClosure()) return true;
	return a.typeVariables == b.typeVariables;
	}

	if (superclass != null && superclass != compiler.objectClass &&
	!haveSameTypeVariables(cls, superclass)) {
	// We cannot inherit the generated substitutions, because the type
	// variable layout for this class is different. Instead we generate
	// substitutions for all checks and make emitSubstitution a NOP for the
	// rest of this function.
	Set<ClassElement> emitted = new Set<ClassElement>();
	// TODO(karlklose): move the computation of these checks to
	// RuntimeTypeInformation.
	if (backend.classNeedsRti(cls)) {
	emitSubstitution(superclass, emitNull: true);
	emitted.add(superclass);
	}
	for (DartType supertype in cls.allSupertypes) {
	ClassElement superclass = supertype.element;
	if (classesUsingTypeVariableTests.contains(superclass)) {
	emitSubstitution(superclass, emitNull: true);
	emitted.add(superclass);
	}
	for (ClassElement check in checkedClasses) {
	if (supertype.element == check && !emitted.contains(check)) {
	// Generate substitution. If no substitution is necessary, emit
	// [:null:] to overwrite a (possibly) existing substitution from the
	// super classes.
	emitSubstitution(check, emitNull: true);
	emitted.add(check);
	}
	}
	}
	void emitNothing(_, {emitNull}) {};
	emitSubstitution = emitNothing;
	}

	Set<Element> generated = new Set<Element>();
	// A class that defines a [:call:] method implicitly implements
	// [Function] and needs checks for all typedefs that are used in is-checks.
	if (checkedClasses.contains(compiler.functionClass) \|\|
	!checkedFunctionTypes.isEmpty) {
	Element call = cls.lookupLocalMember(Compiler.CALL_OPERATOR_NAME);
	if (call == null) {
	// If [cls] is a closure, it has a synthetic call operator method.
	call = cls.lookupBackendMember(Compiler.CALL_OPERATOR_NAME);
	}
	if (call != null && call.isFunction()) {
	generateInterfacesIsTests(compiler.functionClass,
	emitIsTest,
	emitSubstitution,
	generated);
	FunctionType callType = call.computeType(compiler);
	Map<FunctionType, bool> functionTypeChecks =
	getFunctionTypeChecksOn(callType);
	generateFunctionTypeTests(
	call, callType, functionTypeChecks,
	emitFunctionTypeSignature);
	}
	}

	for (DartType interfaceType in cls.interfaces) {
	generateInterfacesIsTests(interfaceType.element, emitIsTest,
	emitSubstitution, generated);
	}
	}

	/**
	* Generate "is tests" where [cls] is being implemented.
	*/
	void generateInterfacesIsTests(ClassElement cls,
	void emitIsTest(ClassElement element),
	SubstitutionEmitter emitSubstitution,
	Set<Element> alreadyGenerated) {
	void tryEmitTest(ClassElement check) {
	if (!alreadyGenerated.contains(check) && checkedClasses.contains(check)) {
	alreadyGenerated.add(check);
	emitIsTest(check);
	emitSubstitution(check);
	}
	};

	tryEmitTest(cls);

	for (DartType interfaceType in cls.interfaces) {
	Element element = interfaceType.element;
	tryEmitTest(element);
	generateInterfacesIsTests(element, emitIsTest, emitSubstitution,
	alreadyGenerated);
	}

	// We need to also emit "is checks" for the superclass and its supertypes.
	ClassElement superclass = cls.superclass;
	if (superclass != null) {
	tryEmitTest(superclass);
	generateInterfacesIsTests(superclass, emitIsTest, emitSubstitution,
	alreadyGenerated);
	}
	}

	/**
	* Returns a mapping containing all checked function types for which [type]
	* can be a subtype. A function type is mapped to [:true:] if [type] is
	* statically known to be a subtype of it and to [:false:] if [type] might
	* be a subtype, provided with the right type arguments.
	*/
	// TODO(johnniwinther): Change to return a mapping from function types to
	// a set of variable points and use this to detect statically/dynamically
	// known subtype relations.
	Map<FunctionType, bool> getFunctionTypeChecksOn(DartType type) {
	Map<FunctionType, bool> functionTypeMap = new Map<FunctionType, bool>();
	for (FunctionType functionType in checkedFunctionTypes) {
	int maybeSubtype = compiler.types.computeSubtypeRelation(type, functionType);
	if (maybeSubtype == Types.IS_SUBTYPE) {
	functionTypeMap[functionType] = true;
	} else if (maybeSubtype == Types.MAYBE_SUBTYPE) {
	functionTypeMap[functionType] = false;
	}
	}
	// TODO(johnniwinther): Ensure stable ordering of the keys.
	return functionTypeMap;
	}

	/**
	* Generates function type checks on [method] with type [methodType] against
	* the function type checks in [functionTypeChecks].
	*/
	void generateFunctionTypeTests(
	Element method,
	FunctionType methodType,
	Map<FunctionType, bool> functionTypeChecks,
	FunctionTypeSignatureEmitter emitFunctionTypeSignature) {

	// TODO(ahe): We should be able to remove this forEach loop.
	functionTypeChecks.forEach((FunctionType functionType, bool knownSubtype) {
	registerDynamicFunctionTypeCheck(functionType);
	});

	emitFunctionTypeSignature(method, methodType);
	}

	void registerDynamicFunctionTypeCheck(FunctionType functionType) {
	ClassElement classElement = Types.getClassContext(functionType);
	if (classElement != null) {
	checkedGenericFunctionTypes.putIfAbsent(classElement,
	() => new Set<FunctionType>()).add(functionType);
	} else {
	checkedNonGenericFunctionTypes.add(functionType);
	}
	}

	void emitRuntimeTypeSupport(CodeBuffer buffer) {
	task.addComment('Runtime type support', buffer);
	RuntimeTypes rti = backend.rti;
	TypeChecks typeChecks = rti.requiredChecks;

	// Add checks to the constructors of instantiated classes.
	for (ClassElement cls in typeChecks) {
	// TODO(9556). The properties added to 'holder' should be generated
	// directly as properties of the class object, not added later.
	String holder = namer.isolateAccess(backend.getImplementationClass(cls));
	for (TypeCheck check in typeChecks[cls]) {
	ClassElement cls = check.cls;
	buffer.write('$holder.${namer.operatorIs(cls)}$_=${_}true$N');
	Substitution substitution = check.substitution;
	if (substitution != null) {
	CodeBuffer body =
	jsAst.prettyPrint(substitution.getCode(rti, false), compiler);
	buffer.write('$holder.${namer.substitutionName(cls)}$_=${_}');
	buffer.write(body);
	buffer.write('$N');
	}
	};
	}

	void addSignature(FunctionType type) {
	jsAst.Expression encoding = rti.getTypeEncoding(type);
	buffer.add('${namer.signatureName(type)}$_=${_}');
	buffer.write(jsAst.prettyPrint(encoding, compiler));
	buffer.add('$N');
	}

	checkedNonGenericFunctionTypes.forEach(addSignature);

	checkedGenericFunctionTypes.forEach((_, Set<FunctionType> functionTypes) {
	functionTypes.forEach(addSignature);
	});
	}

	/**
	* Returns the classes with constructors used as a 'holder' in
	* [emitRuntimeTypeSupport].
	* TODO(9556): Some cases will go away when the class objects are created as
	* complete. Not all classes will go away while constructors are referenced
	* from type substitutions.
	*/
	Set<ClassElement> classesModifiedByEmitRuntimeTypeSupport() {
	TypeChecks typeChecks = backend.rti.requiredChecks;
	Set<ClassElement> result = new Set<ClassElement>();
	for (ClassElement cls in typeChecks) {
	for (TypeCheck check in typeChecks[cls]) {
	result.add(backend.getImplementationClass(cls));
	break;
	}
	}
	return result;
	}

	Set<ClassElement> computeRtiNeededClasses() {
	void addClassWithSuperclasses(ClassElement cls) {
	rtiNeededClasses.add(cls);
	for (ClassElement superclass = cls.superclass;
	superclass != null;
	superclass = superclass.superclass) {
	rtiNeededClasses.add(superclass);
	}
	}

	void addClassesWithSuperclasses(Iterable<ClassElement> classes) {
	for (ClassElement cls in classes) {
	addClassWithSuperclasses(cls);
	}
	}

	// 1. Add classes that are referenced by type arguments or substitutions in
	// argument checks.
	// TODO(karlklose): merge this case with 2 when unifying argument and
	// object checks.
	RuntimeTypes rti = backend.rti;
	rti.getRequiredArgumentClasses(backend).forEach((ClassElement c) {
	// Types that we represent with JS native types (like int and String) do
	// not need a class definition as we use the interceptor classes instead.
	if (!rti.isJsNative(c)) {
	addClassWithSuperclasses(c);
	}
	});

	// 2. Add classes that are referenced by substitutions in object checks and
	// their superclasses.
	TypeChecks requiredChecks =
	rti.computeChecks(rtiNeededClasses, checkedClasses);
	Set<ClassElement> classesUsedInSubstitutions =
	rti.getClassesUsedInSubstitutions(backend, requiredChecks);
	addClassesWithSuperclasses(classesUsedInSubstitutions);

	// 3. Add classes that contain checked generic function types. These are
	// needed to store the signature encoding.
	for (FunctionType type in checkedFunctionTypes) {
	ClassElement contextClass = Types.getClassContext(type);
	if (contextClass != null) {
	rtiNeededClasses.add(contextClass);
	}
	}

	bool canTearOff(Element function) {
	if (!function.isFunction() \|\|
	function.isConstructor() \|\|
	function.isAccessor()) {
	return false;
	} else if (function.isInstanceMember()) {
	if (!function.getEnclosingClass().isClosure()) {
	return compiler.codegenWorld.hasInvokedGetter(function, compiler);
	}
	}
	return false;
	}

	backend.generatedCode.keys.where((element) {
	return element is FunctionElement &&
	element is! ConstructorBodyElement &&
	(canTearOff(element) \|\| backend.isAccessibleByReflection(element));
	}).forEach((FunctionElement function) {
	DartType type = function.computeType(compiler);
	for (ClassElement cls in backend.rti.getReferencedClasses(type)) {
	while (cls != null) {
	rtiNeededClasses.add(cls);
	cls = cls.superclass;
	}
	}
	});

	return rtiNeededClasses;
	}

	void computeRequiredTypeChecks() {
	assert(checkedClasses == null && checkedFunctionTypes == null);

	backend.rti.addImplicitChecks(compiler.codegenWorld,
	classesUsingTypeVariableTests);

	checkedClasses = new Set<ClassElement>();
	checkedFunctionTypes = new Set<FunctionType>();
	compiler.codegenWorld.isChecks.forEach((DartType t) {
	if (t is InterfaceType) {
	checkedClasses.add(t.element);
	} else if (t is FunctionType) {
	checkedFunctionTypes.add(t);
	}
	});
	}
	}