root/trunk/ProjectFortress/src/com/sun/fortress/scala_src/typechecker/impls/Functionals.scala @ 3915

Revision 3915, 16.7 KB (checked in by jrhil47, 5 months ago)

[index] Changed all Functional indices to store a thunk to get the return types, since during type checking the return types might need to be lazily evaluated. Also changed Functional indices to yield an Option for return types.
[type checker] Started implementing extraction of bindings from nodes for type environments.
Line 
1/*******************************************************************************
2    Copyright 2009 Sun Microsystems, Inc.,
3    4150 Network Circle, Santa Clara, California 95054, U.S.A.
4    All rights reserved.
5
6    U.S. Government Rights - Commercial software.
7    Government users are subject to the Sun Microsystems, Inc. standard
8    license agreement and applicable provisions of the FAR and its supplements.
9
10    Use is subject to license terms.
11
12    This distribution may include materials developed by third parties.
13
14    Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered
15    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
16 ******************************************************************************/
17
18package com.sun.fortress.scala_src.typechecker.impls
19
20import com.sun.fortress.compiler.index.Method
21import com.sun.fortress.exceptions.StaticError.errorMsg
22import com.sun.fortress.nodes._
23import com.sun.fortress.nodes_util.NodeFactory
24import com.sun.fortress.nodes_util.NodeUtil
25import com.sun.fortress.scala_src.typechecker._
26import com.sun.fortress.scala_src.typechecker.ScalaConstraintUtil._
27import com.sun.fortress.scala_src.nodes._
28import com.sun.fortress.scala_src.useful.Lists._
29import com.sun.fortress.scala_src.useful.Options._
30import com.sun.fortress.scala_src.useful.Sets._
31import com.sun.fortress.scala_src.useful.SExprUtil._
32import com.sun.fortress.scala_src.useful.STypesUtil._
33import com.sun.fortress.useful.NI
34
35/**
36 * Provides the implementation of cases relating to functionals and functional
37 * application.
38 *
39 * This trait must be mixed in with an `STypeChecker with Common` instance
40 * in order to provide the full type checker implementation.
41 *
42 * (The self-type annotation at the beginning declares that this trait must be
43 * mixed into STypeChecker along with the Common helpers. This is what
44 * allows this trait to implement abstract members of STypeChecker and to
45 * access its protected members.)
46 */
47trait Functionals { self: STypeChecker with Common =>
48
49  // ---------------------------------------------------------------------------
50  // HELPER METHODS ------------------------------------------------------------
51
52  /**
53   * Given a type, which could be a VarType, Intersection or Union, return the TraitTypes
54   * that this type could be used as for the purposes of calling methods and fields.
55   */
56  protected def traitTypesCallable(typ: Type): Set[TraitType] = typ match {
57    case t:TraitType => Set(t)
58
59    // Combine all the trait types callable from constituents.
60    case typ:IntersectionType =>
61      conjuncts(typ).filter(NodeUtil.isTraitType).flatMap(traitTypesCallable)
62
63    // Get the trait types callable from the upper bounds of this parameter.
64    case SVarType(_, name, _) => toOption(env.staticParam(name)) match {
65      case Some(s@SStaticParam(_, _, ts, _, _, SKindType(_))) =>
66        Set(ts:_*).filter(NodeUtil.isTraitType).flatMap(traitTypesCallable)
67      case _ => Set.empty[TraitType]
68    }
69
70    case SUnionType(_, ts) =>
71      signal(typ, errorMsg("You should be able to call methods on this type,",
72                           "but this is not yet implemented."))
73      Set.empty[TraitType]
74
75    case _ => Set.empty[TraitType]
76  }
77
78  /**
79   * Not yet implemented.
80   * Waiting for _RewriteFnApp to be implemented.
81   */
82  protected def findMethodsInTraitHierarchy(methodName: IdOrOpOrAnonymousName,
83                                            receiverType: Type)
84                                            : Set[Method] = {
85
86    val traitTypes = traitTypesCallable(receiverType)
87    val ttAsWheres = traitTypes.map(NodeFactory.makeTraitTypeWhere)
88    val allMethods = inheritedMethods(ttAsWheres.toList)
89    toSet(allMethods.matchFirst(methodName))
90  }
91 
92  /**
93   * Determines if the given overloading is dynamically applicable.
94   */
95  protected def isDynamicallyApplicable(overloading: Overloading,
96                                        smaArrow: ArrowType,
97                                        inferredStaticArgs: List[StaticArg])
98                                        : Option[Overloading] = {
99    // Is this arrow type applicable.
100    def arrowTypeIsApplicable(overloadingType: ArrowType): Option[Type] = {
101      val typ =
102        // If static args given, then instantiate the overloading first.
103        if (inferredStaticArgs.isEmpty)
104          overloadingType
105        else
106          staticInstantiation(inferredStaticArgs, overloadingType).
107            getOrElse(return None).asInstanceOf[ArrowType]
108
109      if (isSubtype(typ.getDomain, smaArrow.getDomain))
110        Some(typ)
111      else
112        None
113    }
114
115    // If overloading type is an intersection, check that any of its
116    // constituents is applicable.
117    val applicableArrows = conjuncts(toOption(overloading.getType).get).
118      map(_.asInstanceOf[ArrowType]).
119      flatMap(arrowTypeIsApplicable)
120
121    val overloadingType = applicableArrows.toList match {
122      case Nil => return None
123      case t::Nil => t
124      case _ => NodeFactory.makeIntersectionType(applicableArrows)
125    }
126    Some(SOverloading(overloading.getInfo,
127                      overloading.getUnambiguousName,
128                      Some(overloadingType)))
129  }
130
131  /**
132   * Calls the other overloading with the conjuncts of the given function type.
133   */
134  protected def staticallyMostApplicableArrow(fnType: Type,
135                                              argType: Type,
136                                              expectedType: Option[Type])
137                                              : Option[(ArrowType, List[StaticArg])] = {
138
139    val arrows = conjuncts(fnType).toList.map(_.asInstanceOf[ArrowType])
140    staticallyMostApplicableArrow(arrows, argType, expectedType)
141  }
142
143  /**
144   * Return the statically most applicable arrow type along with the static args
145   * that instantiated that arrow type. This method assumes that all the arrow
146   * types in fnType have already been instantiated if any static args were
147   * supplied.
148   */
149  protected def staticallyMostApplicableArrow(allArrows: List[ArrowType],
150                                              argType: Type,
151                                              expectedType: Option[Type])
152                                              : Option[(ArrowType, List[StaticArg])] = {
153
154    // Filter applicable arrows and their instantiated args.
155    val arrowsAndInstantiations =
156      allArrows.flatMap(ty => checkApplicable(ty.asInstanceOf[ArrowType],
157                                              argType,
158                                              expectedType))
159
160    // Define an ordering relation on arrows with their instantiations.
161    def lessThan(overloading1: (ArrowType, List[StaticArg]),
162                 overloading2: (ArrowType, List[StaticArg])): Boolean = {
163
164      val SArrowType(_, domain1, range1, _, _) = overloading1._1
165      val SArrowType(_, domain2, range2, _, _) = overloading2._1
166
167      if (equivalentTypes(domain1, domain2)) false
168      else isSubtype(domain1, domain2)
169    }
170
171    // Sort the arrows and instantiations to find the statically most
172    // applicable. Return None if none were applicable.
173    arrowsAndInstantiations.sort(lessThan).firstOption
174  }
175
176  /**
177   * Checks whether an arrow type if applicable to the given args. If so, then
178   * the [possible instantiated] arrow type along with any inferred statics args
179   * are returned.
180   */
181  protected def checkApplicable(fnType: ArrowType,
182                                argType: Type,
183                                expectedType: Option[Type])
184                                : Option[(ArrowType, List[StaticArg])] = {
185                                 
186    val sparams = getStaticParams(fnType)
187
188    // Substitute inference variables for static parameters in fnType.
189
190    // 1. build substitution S = [T_i -> $T_i]
191    // 2. instantiate fnType with S to get an arrow type with inf vars, infArrow
192    val sargs = sparams.map(makeInferenceArg)
193    val infArrow = staticInstantiation(sargs, sparams, fnType).
194      getOrElse(return None).asInstanceOf[ArrowType]
195
196    // 3. argType <:? dom(infArrow) yields a constraint, C1
197    val domainConstraint = checkSubtype(argType, infArrow.getDomain)
198
199    // 4. if expectedType given, C := C1 AND range(infArrow) <:? expectedType
200    val rangeConstraint = expectedType.map(
201      t => checkSubtype(infArrow.getRange, t)).getOrElse(TRUE_FORMULA)
202    val constraint = domainConstraint.scalaAnd(rangeConstraint, isSubtype)
203
204    // Get an inference variable type out of a static arg.
205    def staticArgType(sarg: StaticArg): Option[_InferenceVarType] = sarg match {
206      case sarg:TypeArg => Some(sarg.getTypeArg.asInstanceOf)
207      case _ => None
208    }
209
210    // 5. build bounds map B = [$T_i -> S(UB(T_i))]
211    val infVars = sargs.flatMap(staticArgType)
212    val sparamBounds = sparams.flatMap(staticParamBoundType).
213      map(t => insertStaticParams(t, sparams))
214    val boundsMap = Map(infVars.zip(sparamBounds): _*)
215
216    // 6. solve C to yield a substitution S' = [$T_i -> U_i]
217    val subst = constraint.scalaSolve(boundsMap).getOrElse(return None)
218
219    // 7. instantiate infArrow with [U_i] to get resultArrow
220    val resultArrow = substituteTypesForInferenceVars(subst, infArrow).
221      asInstanceOf[ArrowType]
222
223    // 8. return (resultArrow,StaticArgs([U_i]))
224    val resultArgs = infVars.map((t) =>
225      NodeFactory.makeTypeArg(resultArrow.getInfo.getSpan, subst.apply(t)))
226    Some((resultArrow,resultArgs))
227  }
228
229  /**
230   * Given an applicand, the statically most applicable arrow type for it,
231   * and the static args from the application, return the applicand updated
232   * with the dynamically applicable overloadings, arrow type, and static args.
233   */
234  protected def rewriteApplicand(fn: Expr,
235                                 arrow: ArrowType,
236                                 sargs: List[StaticArg]): Expr = fn match {
237    case fn: FunctionalRef =>
238
239      // Get the dynamically applicable overloadings.
240      val overloadings =
241        toList(fn.getNewOverloadings).
242        flatMap(o => isDynamicallyApplicable(o, arrow, sargs))
243
244      // Add in the filtered overloadings, the inferred static args,
245      // and the statically most applicable arrow to the fn.
246      addType(
247        addStaticArgs(
248          addOverloadings(fn, overloadings), sargs), arrow)
249
250    case _ if !sargs.isEmpty =>
251      NI.nyi("No place to put inferred static args in application.")
252
253    // Just add the arrow type if the applicand is not a FunctionalRef.
254    case _ => addType(fn, arrow)
255  }
256
257  /**
258   * Signal a static error for an application for which there were no applicable
259   * functions.
260   */
261  protected def noApplicableFunctions(application: Expr,
262                                      fn: Expr,
263                                      fnType: Type,
264                                      argType: Type) = {
265    val kind = fn match {
266      case _:FnRef => "function"
267      case _:OpRef => "operator"
268      case _ => ""
269    }
270    val argTypeStr = normalize(argType) match {
271      case tt:TupleType => tt.getElements.toString
272      case _ => "[" + argType.toString + "]"
273    }
274    val message = fn match {
275      case fn:FunctionalRef =>
276        val name = fn.getOriginalName
277        val sargs = fn.getStaticArgs
278        if (sargs.isEmpty)
279          "Call to %s %s has invalid arguments, %s".
280            format(kind, name, argTypeStr)
281        else
282          "Call to %s %s with static arguments %s has invalid arguments, %s".
283            format(kind, name, sargs, argTypeStr)
284      case _ =>
285        "Expression of type %s is not applicable to argument type %s.".
286          format(normalize(fnType), argTypeStr)
287      }
288      signal(application, message)
289    }
290
291  // ---------------------------------------------------------------------------
292  // CHECK IMPLEMENTATION ------------------------------------------------------
293 
294  def checkFunctionals(node: Node): Node = node match {
295
296    case SOverloading(info, name, _) => {
297      val checkedName = check(name).asInstanceOf[IdOrOp]
298      getTypeFromName(checkedName) match {
299        case Some(checkedType) =>
300          SOverloading(info, checkedName, Some(checkedType))
301        case None => node
302      }
303    }
304
305    case _ => throw new Error(errorMsg("not yet implemented: ", node.getClass))
306  }
307 
308  // ---------------------------------------------------------------------------
309  // CHECKEXPR IMPLEMENTATION --------------------------------------------------
310
311  def checkExprFunctionals(expr: Expr,
312                           expected: Option[Type]): Expr = expr match {
313
314    case SSubscriptExpr(SExprInfo(span, paren, _), obj, subs, op, sargs) => {
315      val checkedObj = checkExpr(obj)
316      val checkedSubs = subs.map(checkExpr)
317      val objType = getType(checkedObj).getOrElse(return expr)
318
319      // Convert sub types into a single type or tuple of types.
320      if (!haveTypes(checkedSubs)) return expr
321      val subsType = checkedSubs.map(s => getType(s).get) match {
322        case t :: Nil => t
323        case t =>
324          NodeFactory.makeTupleType(NodeUtil.getSpan(expr), toJavaList(t))
325      }
326
327      // Get the methods and arrows from the op.
328      val methods = findMethodsInTraitHierarchy(op.get, objType)
329      val arrows =
330        if (sargs.isEmpty) methods.map(makeArrowFromFunctional)
331        else methods.flatMap(m =>
332               staticInstantiation(sargs, makeArrowFromFunctional(m))).
333               map(_.asInstanceOf[ArrowType])
334
335      staticallyMostApplicableArrow(arrows.toList, subsType, None) match {
336        case Some((arrow, sargs)) =>
337          SSubscriptExpr(SExprInfo(span, paren, Some(arrow.getRange)),
338                         checkedObj,
339                         checkedSubs,
340                         op,
341                         sargs)
342        case one =>
343          signal(expr, "Receiver type %s does not have applicable overloading of %s for argument type %s.".
344                         format(objType, op.get, subsType))
345          expr
346      }
347    }
348
349    case fn@SFunctionalRef(_, sargs, _, name, _, _, overloadings, _) => {
350      // Note that ExprDisambiguator inserts the static args from a
351      // FunctionalRef into each of its Overloadings.
352
353      // Check all the overloadings and filter out any that have the wrong
354      // number or kind of static parameters.
355      def rewriteOverloading(o: Overloading): Option[Overloading] = check(o) match {
356        case  SOverloading(info, name, Some(ty)) =>
357          staticInstantiation(sargs, ty).map(t => SOverloading(info,name,Some(t)))
358        case _ => None
359      }
360      val checkedOverloadings = overloadings.flatMap(rewriteOverloading)
361
362      if (checkedOverloadings.isEmpty)
363        signal(expr, errorMsg("Wrong number or kind of static arguments for function: ",
364                              name))
365
366      // Make the intersection type of all the overloadings.
367      val overloadingTypes = checkedOverloadings.map(_.getType.unwrap)
368      val intersectionType =
369        NodeFactory.makeIntersectionType(NodeUtil.getSpan(fn),
370                                         toJavaList(overloadingTypes))
371      addType(addOverloadings(fn, checkedOverloadings), intersectionType)
372    }
373
374    case S_RewriteFnApp(SExprInfo(span, paren, optType), fn, arg) => {
375      val checkedFn = checkExpr(fn)
376      val checkedArg = checkExpr(arg)
377
378      // Check fn and arg and get their types.
379      (getType(checkedFn), getType(checkedArg)) match {
380        case (Some(fnType), Some(_)) if !isArrows(fnType) =>
381          signal(expr, errorMsg("Applicand has a type that is not an arrow: ",
382                                normalize(fnType)))
383          expr
384        case (Some(fnType), Some(argType)) =>
385
386          staticallyMostApplicableArrow(fnType, argType, None) match {
387            case Some((smostApp, sargs)) =>
388
389              // Rewrite the applicand to include the arrow and static args
390              // and update the application.
391              val newFn = rewriteApplicand(checkedFn, smostApp, sargs)
392              S_RewriteFnApp(SExprInfo(span, paren, Some(smostApp.getRange)), newFn, checkedArg)
393
394            case None =>
395              noApplicableFunctions(expr, checkedFn, fnType, argType)
396              expr
397        }
398
399        case _ => expr
400      }
401    }
402
403    case SOpExpr(info, fn, args) => {
404      val checkedOp = checkExpr(fn)
405      val checkedArgs = args.map(checkExpr)
406      val opType = getType(checkedOp).getOrElse(return expr)
407      if (!haveTypes(checkedArgs)) return expr
408      val argType =
409        NodeFactory.makeTupleType(info.getSpan,
410                                  toJavaList(checkedArgs.map(t => getType(t).get)))
411      staticallyMostApplicableArrow(opType, argType, None) match {
412        case Some((smostApp, sargs)) =>
413          val newOp = rewriteApplicand(checkedOp,smostApp,sargs).asInstanceOf[OpRef]
414          addType(SOpExpr(info, newOp, checkedArgs),smostApp.getRange)
415
416        case None =>
417          noApplicableFunctions(expr, checkedOp, opType, argType)
418          expr
419      }
420
421    }
422   
423    case _ => throw new Error(errorMsg("Not yet implemented: ", expr.getClass))
424  } 
425}
Note: See TracBrowser for help on using the browser.