infer.scala

JAVA 语言的函数式编程扩展

      isNullary(tpe1) && !isNullary(tpe2) ||
      isStrictlyBetter(tpe1, tpe2)
    }

    /** Is type `tpe1' a strictly better alternative than type `tpe2'?
     *  non-methods are always strictly better than methods
     *  nullary methods are always strictly better than non-nullary
     *  if both are non-nullary methods, then tpe1 is strictly better than tpe2 if
     *   - tpe1 specializes tpe2 and tpe2 does not specialize tpe1
     *   - tpe1 and tpe2 specialize each other and tpe1 has a strictly better resulttype than
     *     tpe2
     */
    def isStrictlyBetter(tpe1: Type, tpe2: Type) = {
      def isNullary(tpe: Type): Boolean = tpe match {
        case tp: RewrappingTypeProxy => isNullary(tp.underlying)
        case _ => tpe.paramSectionCount == 0 || tpe.paramTypes.isEmpty
      }
      def isMethod(tpe: Type): Boolean = tpe match {
        case tp: RewrappingTypeProxy => isMethod(tp.underlying)
        case MethodType(_, _) | PolyType(_, _) => true
        case _ => false
      }
      def hasStrictlyBetterResult = 
        resultIsBetter(tpe1, tpe2, List(), List()) && !resultIsBetter(tpe2, tpe1, List(), List())
      if (!isMethod(tpe1))
        isMethod(tpe2) || hasStrictlyBetterResult
      
      isNullary(tpe1) && !isNullary(tpe2) ||
      is
      
      else if (isNullary(tpe1))
        isMethod(tpe2) && (!isNullary(tpe2) || hasStrictlyBetterResult)
      else 
        specializes(tpe1, tpe2) && (!specializes(tpe2, tpe1) || hasStrictlyBetterResult)
    }

*/
    /** error if arguments not within bounds. */
    def checkBounds(pos: Position, pre: Type, owner: Symbol, 
                    tparams: List[Symbol], targs: List[Type], prefix: String) = {
      //@M validate variances & bounds of targs wrt variances & bounds of tparams
      //@M TODO: better place to check this? 
      //@M TODO: errors for getters & setters are reported separately
      val kindErrors = checkKindBounds(tparams, targs, pre, owner)
           
      if(!kindErrors.isEmpty)
        error(pos, 
          prefix + "the kinds of the type arguments " + targs.mkString("(", ",", ")") + 
          " do not conform to the expected kinds of the type parameters "+ tparams.mkString("(", ",", ")") + tparams.head.locationString+ "." +
          kindErrors.toList.mkString("\n", ", ", "")) 
      else if (!isWithinBounds(pre, owner, tparams, targs)) { 
        if (!(targs exists (_.isErroneous)) && !(tparams exists (_.isErroneous))) {
          error(pos, 
                prefix + "type arguments " + targs.mkString("[", ",", "]") + 
                " do not conform to " + tparams.head.owner + "'s type parameter bounds " + 
                (tparams map (_.defString)).mkString("[", ",", "]"))
        }
        if (settings.explaintypes.value) {
          val bounds = tparams map (tp => tp.info.instantiateTypeParams(tparams, targs).bounds)
          List.map2(targs, bounds)((targ, bound) => explainTypes(bound.lo, targ))
          List.map2(targs, bounds)((targ, bound) => explainTypes(targ, bound.hi))
          ()
        }
      }
    }
    
    /** Check whether <arg>sym1</arg>'s variance conforms to <arg>sym2</arg>'s variance
     *
     * If <arg>sym2</arg> is invariant, <arg>sym1</arg>'s variance is irrelevant. Otherwise they must be equal.
     */
    def variancesMatch(sym1: Symbol, sym2: Symbol): Boolean = (sym2.variance==0 || sym1.variance==sym2.variance)
      
    /** Check well-kindedness of type application (assumes arities are already checked) -- @M
     * 
     * This check is also performed when abstract type members become concrete (aka a "type alias") -- then tparams.length==1
     * (checked one type member at a time -- in that case, prefix is the name of the type alias)
     *
     * Type application is just like value application: it's "contravariant" in the sense that 
     * the type parameters of the supplied type arguments must conform to the type parameters of 
     * the required type parameters:
     *   - their bounds must be less strict
     *   - variances must match (here, variances are absolute, the variance of a type parameter does not influence the variance of its higher-order parameters)     
     *   - @M TODO: are these conditions correct,sufficient&necessary?
     *
     *  e.g. class Iterable[t, m[+x <: t]] --> the application Iterable[Int, List] is okay, since 
     *       List's type parameter is also covariant and its bounds are weaker than <: Int
     */
    def checkKindBounds(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): List[String] = {
      def transform(tp: Type, clazz: Symbol): Type = tp.asSeenFrom(pre, clazz) // instantiate type params that come from outside the abstract type we're currently checking

      // check that the type parameters <arg>hkargs</arg> to a higher-kinded type conform to the expected params <arg>hkparams</arg>
      def checkKindBoundsHK(hkargs: List[Symbol], arg: Symbol, param: Symbol, paramowner: Symbol): (List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)]) = {
// NOTE: sometimes hkargs != arg.typeParams, the symbol and the type may have very different type parameters
        val hkparams = param.typeParams

        if(hkargs.length != hkparams.length) {
          if(arg == AnyClass || arg == AllClass) (Nil, Nil, Nil) // Any and Nothing are kind-overloaded
          else (List((arg, param)), Nil, Nil)
        } else {
          val _arityMismatches = new ListBuffer[(Symbol, Symbol)]
          val _varianceMismatches = new ListBuffer[(Symbol, Symbol)]
          val _stricterBounds = new ListBuffer[(Symbol, Symbol)] 
          def varianceMismatch(a: Symbol, p: Symbol) { _varianceMismatches += (a, p) }
          def stricterBound(a: Symbol, p: Symbol) { _stricterBounds += (a, p) }
          def arityMismatches(as: Iterable[(Symbol, Symbol)]) { _arityMismatches ++= as }
          def varianceMismatches(as: Iterable[(Symbol, Symbol)]) { _varianceMismatches ++= as }
          def stricterBounds(as: Iterable[(Symbol, Symbol)]) { _stricterBounds ++= as }

          for ((hkarg, hkparam) <- hkargs zip hkparams) { 
            if (hkparam.typeParams.isEmpty) { // base-case: kind *
              if (!variancesMatch(hkarg, hkparam))
                varianceMismatch(hkarg, hkparam)                                         
              
              // instantiateTypeParams(tparams, targs) --> higher-order bounds may contain references to type arguments
              // substSym(hkparams, hkargs) --> these types are going to be compared as types of kind * 
              //    --> their arguments use different symbols, but are conceptually the same 
              //        (could also replace the types by polytypes, but can't just strip the symbols, as ordering is lost then)
              if (!(transform(hkparam.info.instantiateTypeParams(tparams, targs).bounds.substSym(hkparams, hkargs), paramowner) <:< transform(hkarg.info.bounds, owner)))
                stricterBound(hkarg, hkparam)
            } else {
              val (am, vm, sb) = checkKindBoundsHK(hkarg.typeParams, hkarg, hkparam, paramowner)
              arityMismatches(am)
              varianceMismatches(vm)
              stricterBounds(sb)
            }
          }      
              
          (_arityMismatches.toList, _varianceMismatches.toList, _stricterBounds.toList)
        }    
      }

      // @M TODO this method is duplicated all over the place (varianceString)
      def varStr(s: Symbol): String =
        if (s.isCovariant) "covariant"
        else if (s.isContravariant) "contravariant"
        else "invariant";                                                

      def qualify(a0: Symbol, b0: Symbol): String = if (a0.toString != b0.toString) "" else { 
        assert(a0 ne b0)
        assert(a0.owner ne b0.owner)
        var a = a0; var b = b0
        while (a.owner.name == b.owner.name) { a = a.owner; b = b.owner}
        if (a.locationString ne "") " (" + a.locationString.trim + ")" else ""
      }
      
      val errors = new ListBuffer[String]
      (tparams zip targs).foreach{ case (tparam, targ) if(targ.isHigherKinded || !tparam.typeParams.isEmpty) => //println("check: "+(tparam, targ))
        val (arityMismatches, varianceMismatches, stricterBounds) = 
          checkKindBoundsHK(targ.typeParams, targ.typeSymbolDirect, tparam, tparam.owner) // NOTE: *not* targ.typeSymbol, which normalizes
            // NOTE 2: must use the typeParams of the type targ, not the typeParams of the symbol of targ!!
        
        if (!(arityMismatches.isEmpty && varianceMismatches.isEmpty && stricterBounds.isEmpty)){
          errors += (targ+"'s type parameters do not match "+tparam+"'s expected parameters: "+ 
            (for ((a, p) <- arityMismatches)
             yield a+qualify(a,p)+ " has "+reporter.countElementsAsString(a.typeParams.length, "type parameter")+", but "+
              p+qualify(p,a)+" has "+reporter.countAsString(p.typeParams.length)).toList.mkString(", ") +
            (for ((a, p) <- varianceMismatches)
             yield a+qualify(a,p)+ " is "+varStr(a)+", but "+
              p+qualify(p,a)+" is declared "+varStr(p)).toList.mkString(", ") +
            (for ((a, p) <- stricterBounds)
              yield a+qualify(a,p)+"'s bounds "+a.info+" are stricter than "+
              p+qualify(p,a)+"'s declared bounds "+p.info).toList.mkString(", "))
        }
       // case (tparam, targ) => println("no check: "+(tparam, targ, tparam.typeParams.isEmpty))                                                             
       case _ =>
      }
      
      errors.toList
    }
      
    /** Substitite free type variables `undetparams' of polymorphic argument
     *  expression `tree', given two prototypes `strictPt', and `lenientPt'.
     *  `strictPt' is the first attempt prototype where type parameters
     *  are left unchanged. `lenientPt' is the fall-back prototype where type
     *  parameters are replaced by `WildcardType's. We try to instantiate
     *  first to `strictPt' and then, if this fails, to `lenientPt'. If both
     *  attempts fail, an error is produced.
     */
    def inferArgumentInstance(tree: Tree, undetparams: List[Symbol],
                              strictPt: Type, lenientPt: Type) {
      if (inferInfo)
        println("infer argument instance "+tree+":"+tree.tpe+"\n"+
                "  undetparams = "+undetparams+"\n"+
                "  strict pt = "+strictPt+"\n"+
                "  lenient pt = "+lenientPt)
      var targs = exprTypeArgs(undetparams, tree.tpe, strictPt)
      if ((targs eq null) || !(tree.tpe.subst(undetparams, targs) <:< strictPt)) {
        targs = exprTypeArgs(undetparams, tree.tpe, lenientPt)
      }
      substExpr(tree, undetparams, targs, lenientPt)
    }

    /** Substitute free type variables `undetparams; of polymorphic expression
     *  <code>tree</code>, given prototype <code>pt</code>.
     *
     *  @param tree ...
     *  @param undetparams ...
     *  @param pt ...
     */
    def inferExprInstance(tree: Tree, undetparams: List[Symbol], pt: Type) {
      if (inferInfo)
        println("infer expr instance "+tree+"\n"+
                "  undetparams = "+undetparams+"\n"+
                "  pt = "+pt)
      substExpr(tree, undetparams, exprTypeArgs(undetparams, tree.tpe, pt), pt)
    }

    /** Substitite free type variables `undetparams' of polymorphic argument
     *  expression <code>tree</code> to `targs', Error if `targs' is null
     *
     *  @param tree ...
     *  @param undetparams ...
     *  @param targs ...
     *  @param pt ...
     */
    private def substExpr(tree: Tree, undetparams: List[Symbol],
                          targs: List[Type], pt: Type) {
      if (targs eq null) {
        if (!tree.tpe.isErroneous && !pt.isErroneous)
          error(tree.pos, "polymorphic expression cannot be instantiated to expected type" + 
                foundReqMsg(PolyType(undetparams, skipImplicit(tree.tpe)), pt))
      } else {
        new TreeTypeSubstituter(undetparams, targs).traverse(tree)
      }
    }

    /** Substitite free type variables <code>undetparams</code> of application
     *  <code>fn(args)</code>, given prototype <code>pt</code>.
     *
     *  @param fn          ...
     *  @param undetparams ...
     *  @param args        ...
     *  @param pt          ...
     *  @return            Return the list of type parameters that remain uninstantiated.
     */
    def inferMethodInstance(fn: Tree, undetparams: List[Symbol],
                            args: List[Tree], pt: Type): List[Symbol] = fn.tpe match {
      case MethodType(formals0, _) =>
        if (inferInfo)
          println("infer method instance "+fn+"\n"+
                  "  undetparams = "+undetparams+"\n"+
                  "  args = "+args+"\n"+
                  "  pt = "+pt)
        try {
          val formals = formalTypes(formals0, args.length)
          val argtpes = actualTypes(args map (_.tpe.deconst), formals.length)
          val restpe = fn.tpe.resultType(argtpes)
          val uninstantiated = new ListBuffer[Symbol]
          val targs = methTypeArgs(undetparams, formals, restpe, argtpes, pt, uninstantiated)
          checkBounds(fn.pos, NoPrefix, NoSymbol, undetparams, targs, "inferred ")
          //Console.println("UNAPPLY subst type "+undetparams+" to "+targs+" in "+fn+" ( "+args+ ")")
          val treeSubst = new TreeTypeSubstituter(undetparams, targs)
          treeSubst.traverse(fn)
          treeSubst.traverseTrees(args)
          //Console.println("UNAPPLY gives "+fn+" ( "+args+ "), argtpes = "+argtpes+", pt = "+pt)
          uninstantiated.toList
        } catch {
          case ex: NoInstance =>
            errorTree(fn, 
              "no type parameters for " +
              applyErrorMsg(
                fn, " exist so that it can be applied to arguments ",
                args map (_.tpe.widen), WildcardType) +
              "\n --- because ---\n" + ex.getMessage())
            List()
        }
    }

    /** Type with all top-level occurrences of abstract types replaced by their bounds */
    def widen(tp: Type): Type = tp match { // @M don't normalize here (compiler loops on pos/bug1090.scala )
      case TypeRef(_, sym, _) if sym.isAbstractType => 
        widen(tp.bounds.hi)
      case TypeRef(_, sym, _) if sym.isAliasType => 
        widen(tp.normalize)
      case rtp @ RefinedType(parents, decls) => 
        copyRefinedType(rtp, List.mapConserve(parents)(widen), decls)
      case AnnotatedType(_, underlying, _) =>
        widen(underlying)
      case _ =>
        tp
    }

    /** Substitite free type variables <code>undetparams</code> of type constructor
     *  <code>tree</code> in pattern, given prototype <code>pt</code>.
     *
     *  @param tree        ...
     *  @param undetparams ...
     *  @param pt          ...
     */
    def inferConstructorInstance(tree: Tree, undetparams: List[Symbol], pt0: Type) {
      val pt = widen(pt0)
      //println("infer constr inst "+tree+"/"+undetparams+"/"+pt0)
      var restpe = tree.tpe.finalResultType
      var tvars = undetparams map freshVar

      /** Compute type arguments for undetermined params and substitute them in given tree.
       */
      def computeArgs =
        try {
          val targs = solvedTypes(tvars, undetparams, undetparams map varianceInType(restpe), true)
//          checkBounds(tree.pos, NoPrefix, NoSymbol, undetparams, targs, "inferred ")
//          no checkBounds here. If we enable it, test bug602 fails.
          new TreeTypeSubstituter(undetparams, targs).traverse(tree)
        } catch {
          case ex: NoInstance => 
            errorTree(tree, "constructor of type " + restpe +
                      " cannot be uniquely instantiated to expected type " + pt +
                      "\n --- because ---\n" + ex.getMessage())
        }
      def instError = {
        if (settings.debug.value) Console.println("ici " + tree + " " + undetparams + " " + pt)
        if (settings.explaintypes.value) explainTypes(restpe.instantiateTypeParams(undetparams, tvars), pt)
        errorTree(tree, "constructor cannot be instantiated to expected type" +
                  foundReqMsg(restpe, pt))
      }
      if (restpe.instantiateTypeParams(undetparams, tvars) <:< pt) {
        computeArgs
      } else if (isFullyDefined(pt)) {
        if (settings.debug.value) log("infer constr " + tree + ":" + restpe + ", pt = " + pt)
        var ptparams = freeTypeParamsOfTerms.collect(pt)
        if (settings.debug.value) log("free type params = " + ptparams)
        val ptWithWildcards = pt.instantiateTypeParams(ptparams, ptparams map (ptparam => WildcardType))
        tvars = undetparams map freshVar
        if (restpe.instantiateTypeParams(undetparams, tvars) <:< ptWithWildcards) {
          computeArgs
          restpe = skipImplicit(tree.tpe.resultType)
          if (settings.debug.value) log("new tree = " + tree + ":" + restpe)
          val ptvars = ptparams map freshVar
          val pt1 = pt.instantiateTypeParams(ptparams, ptvars)
          if (isPopulated(restpe, pt1)) {
            ptvars foreach instantiateTypeVar
          } else { if (settings.debug.value) Console.println("no instance: "); instError }
        } else { if (settings.debug.value) Console.println("not a subtype " + restpe.instantiateTypeParams(undetparams, tvars) + " of " + ptWithWildcards); instError }
      } else { if (settings.debug.value) Console.println("not fuly defined: " + pt); instError }
    }

    def instantiateTypeVar(tvar: TypeVar) = {
      val tparam = tvar.origin.typeSymbol
      if (false && 
          tvar.constr.inst != NoType && 
          isFullyDefined(tvar.constr.inst) && 
          (tparam.info.bounds containsType tvar.constr.inst)) {
        context.nextEnclosing(_.tree.isInstanceOf[CaseDef]).pushTypeBounds(tparam)
        tparam setInfo tvar.constr.inst
        tparam resetFlag DEFERRED
        if (settings.debug.value) log("new alias of " + tparam + " = " + tparam.info)
      } else {
        val instType = toOrigin(tvar.constr.inst)
        val (loBounds, hiBounds) =
          if (instType != NoType && isFullyDefined(instType)) (List(instType), List(instType))
          else (tvar.constr.lobounds, tvar.constr.hibounds)
        val lo = lub(tparam.info.bounds.lo :: loBounds map toOrigin)
        val hi = glb(tparam.info.bounds.hi :: hiBounds map toOrigin)