// 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 generateIsFunctionTypeTest(FunctionType type) {
      String operator = namer.operatorIsType(type);
      builder.addProperty(operator, new jsAst.LiteralBool(true));
    }

    void generateFunctionTypeSignature(Element method, FunctionType type) {
      assert(method.isImplementation);
      jsAst.Expression thisAccess = new jsAst.This();
      Node node = method.parseNode(compiler);
      ClosureClassMap closureData =
          compiler.closureToClassMapper.closureMappingCache[node];
      if (closureData != null) {
        Element thisElement =
            closureData.freeVariableMapping[closureData.thisElement];
        if (thisElement != null) {
          assert(thisElement.hasFixedBackendName());
          String thisName = thisElement.fixedBackendName();
          thisAccess = js('this')[js.string(thisName)];
        }
      }
      RuntimeTypes rti = backend.rti;
      jsAst.Expression encoding = rti.getSignatureEncoding(type, thisAccess);
      String operatorSignature = namer.operatorSignature();
      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,
        generateIsFunctionTypeTest, 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),
                         FunctionTypeTestEmitter emitIsFunctionTypeTest,
                         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;
      if (b.isUnnamedMixinApplication) {
        return false;
      }
      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, emitIsFunctionTypeTest);
     }
    }

    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) {
      if (compiler.types.isSubtype(type, functionType)) {
        functionTypeMap[functionType] = true;
      } else if (compiler.types.isPotentialSubtype(type, functionType)) {
        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,
      FunctionTypeTestEmitter emitIsFunctionTypeTest) {
    bool hasDynamicFunctionTypeCheck = false;
    int neededPredicates = 0;
    functionTypeChecks.forEach((FunctionType functionType, bool knownSubtype) {
      if (!knownSubtype) {
        registerDynamicFunctionTypeCheck(functionType);
        hasDynamicFunctionTypeCheck = true;
      } else if (!backend.rti.isSimpleFunctionType(functionType)) {
        // Simple function types are always checked using predicates and should
        // not provoke generation of signatures.
        neededPredicates++;
      }
    });
    bool alwaysUseSignature = false;
    if (hasDynamicFunctionTypeCheck ||
        neededPredicates > MAX_FUNCTION_TYPE_PREDICATES) {
      emitFunctionTypeSignature(method, methodType);
      alwaysUseSignature = true;
    }
    functionTypeChecks.forEach((FunctionType functionType, bool knownSubtype) {
      if (knownSubtype) {
        if (backend.rti.isSimpleFunctionType(functionType)) {
          // Simple function types are always checked using predicates.
          emitIsFunctionTypeTest(functionType);
        } else if (alwaysUseSignature) {
          registerDynamicFunctionTypeCheck(functionType);
        } else {
          emitIsFunctionTypeTest(functionType);
        }
      }
    });
  }

  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);
      }
    }

    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);
      }
    });
  }
}