parallelmatching.scala

来自「JAVA 语言的函数式编程扩展」· SCALA 代码 · 共 1,405 行 · 第 1/4 页

      tp1.isInstanceOf[TypeRef] && tp2.isInstanceOf[TypeRef] &&
      ((tp1.prefix =:= tp2.prefix) && 
       ((tp1.typeSymbol eq tp2.typeSymbol) && 
        (tp1.typeSymbol ne definitions.ArrayClass)) ||
       tp1.parents.exists(_.typeSymbol eq tp2.typeSymbol)) 
      // rather: tp1.baseTypes.exists...?
    }

    /** returns true if pattern tests an object */
    final def objectPattern(pat:Tree): Boolean = try {
      (pat.symbol ne null) && 
      (pat.symbol != NoSymbol) && 
      pat.symbol.tpe.prefix.isStable &&
      headPatternType =:= singleType(pat.symbol.tpe.prefix, pat.symbol)
    } catch {
      case e =>
        Console.println("object pattern test throws "+e.getMessage())
        throw e
    }
    /*init block*/ {
      var sr = (moreSpecific,subsumed,remaining)
      var j = 0; var pats = column; while(pats ne Nil) {
        val (ms,ss,rs) = sr // more specific, more general(subsuming current), remaining patterns
        val pat = pats.head 
        val strippedPattern = strip2(pat)
        val patternType = strippedPattern.tpe
        sr = strippedPattern match {
          case Literal(Constant(null)) if !(headPatternType =:= patternType) => // special case for constant null pattern
            (ms,ss,(j,pat)::rs);
          case _ if objectPattern(pat) =>
            (EmptyTree::ms, (j,dummies)::ss, rs);                                 // matching an object
          
          case Typed(p, _) if (strip2(p).isInstanceOf[UnApply] && (patternType /*is never <equals>*/ <:< headPatternType)) => 
            (p::ms, (j, dummies)::ss, rs); 

          case q @ Typed(pp,_) if (patternType_wrtEquals(patternType) <:< headPatternType) => 
            ({if (pat.tpe =:= headPatternType /*never true for <equals>*/) pp else q}::ms, (j, dummies)::ss, rs); 

          case z:UnApply =>
            (ms,ss,(j,pat)::rs)

          case qq if subsumes_erased(patternType, headPatternType) || (patternType_wrtEquals(patternType) <:< headPatternType) && !isDefaultPattern(pat) => 
            ({if (pat.tpe =:= headPatternType /*never true for <equals>*/) EmptyTree else pat}::ms, (j,subpatterns(pat))::ss, rs); 
          
          case _ if subsumes_erased(headPatternType, patternType) || (headPatternType <:< patternType /*never true for <equals>*/) || isDefaultPattern(pat) =>
            (EmptyTree::ms, (j, dummies)::ss, (j,pat)::rs)  // subsuming (matched *and* remaining pattern)
          
          case _ =>
            (ms,ss,(j,pat)::rs)
        }
        j += 1
        pats = pats.tail
      }
      this.moreSpecific = sr._1.reverse
      this.subsumed     = sr._2.reverse
      this.remaining    = sr._3.reverse
      sr = null
    } /* init block */

    override def toString = {
      "MixTypes("+scrutinee+":"+scrutinee.tpe+") {\n  moreSpecific:"+moreSpecific+"\n  subsumed:"+subsumed+"\n  remaining"+remaining+"\n}"
    }

    /** returns casted symbol, success matrix and optionally fail matrix for type test on the top of this column */
    final def getTransition(implicit theOwner: Symbol): (Symbol, Rep, Option[Rep]) = {
      casted = if (scrutinee.tpe =:= headPatternType) scrutinee else newVar(scrutinee.pos, headPatternType)
      if (scrutinee.hasFlag(symtab.Flags.TRANS_FLAG))
        casted.setFlag(symtab.Flags.TRANS_FLAG)
      // succeeding => transition to translate(subsumed) (taking into account more specific)
      val nmatrix = {
        var ntemps  = if (!isCaseHead) Nil else casted.caseFieldAccessors map { 
          meth => 
            val ctemp = newVar(scrutinee.pos, casted.tpe.memberType(meth).resultType) 
            if (scrutinee.hasFlag(symtab.Flags.TRANS_FLAG))
              ctemp.setFlag(symtab.Flags.TRANS_FLAG)
            ctemp
        } // (***) flag needed later
        var subtests = subsumed
        if (moreSpecific.exists { x => x != EmptyTree }) {
          ntemps   = casted::ntemps
          subtests = moreSpecific.zip(subsumed) map { 
            case (mspat, (j,pats)) => (j,mspat::pats) 
          }
        }
        ntemps = ntemps ::: rest.temp
        val ntriples = subtests map {
          case (j,pats) => 
            val (vs,thePat) = strip(column(j))
            val Row(opats, osubst, og, bx) = rest.row(j)
            val nsubst = osubst.add(vs.elements, casted)
            Row(pats ::: opats, nsubst, og, bx) 
        }
        rep.make(ntemps, ntriples)
      }
      // fails      => transition to translate(remaining)
      val nmatrixFail: Option[Rep] = {
        val ntemps   = scrutinee :: rest.temp 
        val ntriples = remaining map {
          case (j, pat) => val r = rest.row(j);  Row(pat :: r.pat, r.subst, r.guard, r.bx)
        }
        if (ntriples.isEmpty) None else Some(rep.make(ntemps, ntriples))
      }
      (casted, nmatrix, nmatrixFail)
    }

    final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = {
      val (casted,srep,frep) = this.getTransition
      val condUntyped = condition(casted.tpe, this.scrutinee)
      var cond = rep.handleOuter(typed { condUntyped })
      if (needsOuterTest(casted.tpe, this.scrutinee.tpe, theOwner)) {  // @todo merge into def condition
        cond = addOuterCondition(cond, casted.tpe, mkIdent(this.scrutinee), rep.handleOuter)
      }
      val succ = repToTree(srep)
      
      val fail = if (frep.isEmpty) failTree else repToTree(frep.get)
      
      // dig out case field accessors that were buried in (***)
      val cfa  = if (!isCaseHead) Nil else casted.caseFieldAccessors 
      val caseTemps = (if (!srep.temp.isEmpty && srep.temp.head == casted) srep.temp.tail else srep.temp).zip(cfa)
      
      try{
        var vdefs     = caseTemps map { 
          p => 
            val tmp = p._1; 
            val accessorMethod = p._2
            val untypedAccess = Apply(Select(mkIdent(casted), accessorMethod),List()) 
            val typedAccess = typed { untypedAccess }
            typedValDef(tmp, typedAccess)
        }
      
      if (casted ne this.scrutinee) 
        vdefs = ValDef(casted, gen.mkAsInstanceOf(mkIdent(this.scrutinee), casted.tpe)) :: vdefs
      
      return typed { If(cond, squeezedBlock(vdefs, succ), fail) }
      } catch {
        case e =>
          throw new FatalError("EXCEPTION:"+e.getMessage())
      }
    }
  }

  /** converts given rep to a tree - performs recursive call to translation in the process to get sub reps
   */
  final def repToTree(r: Rep)(implicit theOwner: Symbol, failTree: Tree, rep: RepFactory): Tree = {
    r.applyRule.tree
  }

  case class Row(pat:List[Tree], subst:Binding, guard:Tree, bx:Int)

  object Rep {
    type RepType = Product2[List[Symbol], List[Row]]
    final def unapply(x:Rep)(implicit rep:RepFactory):Option[RepType] = 
      if (x.isInstanceOf[rep.RepImpl]) Some(x.asInstanceOf[RepType]) else None
  }
  class RepFactory(val handleOuter: Tree => Tree) {
  case class RepImpl(val temp:List[Symbol], val row:List[Row]) extends Rep with Rep.RepType {
    (row.find { case Row(pats, _, _, _) => temp.length != pats.length }) match {
      case Some(row) => assert(false, "temp == "+temp+" row.pats == "+row.pat);
      case _ =>
    }
    def _1 = temp
    def _2 = row
  }

  var vss: List[SymList] = _
  var labels:  Array[Symbol] = new Array[Symbol](4)
  var targets: List[Tree] = _
  var reached64: Set64 = _
  var reached: List[Int] = Nil
  var shortCuts: List[Symbol] = Nil;

  final def make(temp:List[Symbol], row:List[Row], targets: List[Tree], vss:List[SymList])(implicit theOwner: Symbol): Rep = {
    // ensured that labels(i) eq null for all i, cleanup() has to be called after translation
    this.targets   = targets
    if (targets.length > labels.length) 
      this.labels    = new Array[Symbol](targets.length)
    this.vss       = vss
    this.reached64 = if (targets.length < 64) new Set64 else null
    return make(temp, row)
  }

  final def shortCut(theLabel:Symbol): Int = {
    this.shortCuts = shortCuts:::theLabel::Nil;
    return -shortCuts.length
  }

  final def cleanup(tree: Tree)(implicit theOwner: Symbol): Tree = { 
    object lxtt extends Transformer {
      override def transform(tree:Tree): Tree = tree match {
        case blck @ Block(vdefs, ld @ LabelDef(name,params,body)) =>
          val bx = labelIndex(ld.symbol)
          if ((bx >= 0) && !isReachedTwice(bx)) {
            squeezedBlock(vdefs,body)
          }
          else 
            blck

        case If(cond, Literal(Constant(true)), Literal(Constant(false))) => 
          super.transform(cond)
        case If(cond1, If(cond2, thenp, elsep1), elsep2) if (elsep1 equalsStructure elsep2) => 
          super.transform(If(And(cond1,cond2), thenp, elsep1))
        case If(cond1, If(cond2, thenp, Apply(jmp,List())), ld:LabelDef) if (jmp.symbol eq ld.symbol) => 
          super.transform(If(And(cond1,cond2), thenp, ld))

        case t => super.transform(t)
      }
    }
    val res = lxtt.transform(tree)
    cleanup()
    res
  }
  final def cleanup() {
    var i = targets.length; 
    while (i>0) { i-=1; labels(i) = null; }; 
    reached = Nil 
    shortCuts = Nil
  }
  final def isReached(bx:Int)   = { labels(bx) ne null }
  final def markReachedTwice(bx:Int) = if (reached64 ne null) { reached64 |= bx } else { reached = insertSorted(bx, reached) }
  /** @pre bx < 0 || labelIndex(bx) != -1 */
  final def isReachedTwice(bx:Int) = (bx < 0) || (if (reached64 ne null) { reached64 contains bx } else { findSorted(bx,reached) })
  /* @returns bx such that labels(bx) eq label, -1 if no such bx exists */
  final def labelIndex(label:Symbol): Int = {
    var bx = 0; while((bx < labels.length) && (labels(bx) ne label)) { bx += 1 }
    if (bx >= targets.length) bx = -1
    return bx
  }
  /** first time bx is requested, a LabelDef is returned. next time, a jump.
   *  the function takes care of binding
   */
  final def requestBody(bx:Int, subst:Binding)(implicit theOwner: Symbol): Tree = {
    if (bx < 0) { // is shortcut
      val jlabel = shortCuts(-bx-1)
      val jump = Apply(mkIdent(jlabel), Nil)
      return jump
    }
    if (!isReached(bx)) { // first time this bx is requested
      val argts = new ListBuffer[Type] // types of
      var vrev: List[Symbol] = Nil
      var vdefs:List[Tree] = Nil
      val it = vss(bx).elements; while(it.hasNext) {
        val v = it.next
        val substv = subst(v)
        if (substv ne null) { // might be bound elsewhere ( see `x @ unapply' )
          vrev   = v :: vrev 
          argts += v.tpe
          vdefs  = typedValDef(v, substv)::vdefs
        } 
      }
      val body  = targets(bx)
      // @bug: typer is not able to digest a body of type Nothing being assigned result type Unit
      val tpe = if (body.tpe.typeSymbol eq definitions.AllClass) body.tpe else resultType
      val label = theOwner.newLabel(body.pos, "body%"+bx).setInfo(new MethodType(argts.toList, tpe))
      labels(bx) = label

      if (body.isInstanceOf[Throw] || body.isInstanceOf[Literal]) {
        return squeezedBlock(vdefs.reverse, body.duplicate setType tpe)
      }
      return squeezedBlock(vdefs, LabelDef(label, vrev.reverse, body setType tpe))
    } 
 
    // jump
    markReachedTwice(bx) // if some bx is not reached twice, its LabelDef
    val args = new ListBuffer[Ident] // is replaced with body itself
    var vs   = vss(bx).elements; while(vs.hasNext) {
      val v = vs.next
      val substv = subst(v)
      assert(substv ne null, "subst("+v+") is null"+cunit.toString) // if sharing takes place, then 'binding elsewhere' is not allowed
      args += substv
    }
    val label = labels(bx)
    label.tpe match {
      case MethodType(fmls,_) => 
        if (fmls.length != args.length) { // sanity check
          cunit.error(targets(bx).pos, "consistency problem in target generation ! I have args "+args+" and need to jump to a label with fmls "+fmls)
          throw FatalError("consistency problem")
        }
        for((f,a) <- fmls.zip(args.toList)) {
          if (!(a.tpe <:< f)) {
            cunit.error(targets(bx).pos, "consistency problem ! "+a.tpe+" "+f)
            throw FatalError("consistency problem")
          }
        }
    }
    val body = targets(bx)
    if (body.isInstanceOf[Throw] || body.isInstanceOf[Literal]) {
      val vdefs = new ListBuffer[Tree]
      val it = vss(bx).elements; while(it.hasNext) {
        val v = it.next
        val substv = subst(v)
        if (substv ne null) { // might be bound elsewhere ( see `x @ unapply' )
          vdefs  += typedValDef(v, substv)
        } 
      }
      return squeezedBlock(vdefs.toList, body.duplicate setType resultType)
    }


    return Apply(mkIdent(label),args.toList)
  }

  /** the injection here handles alternatives and unapply type tests */
  final def make(temp:List[Symbol], row1:List[Row])(implicit theOwner: Symbol): Rep = {
    var unchanged: Boolean = true
    val row = row1 flatMap { 
      xx => 
        def isAlternative(p: Tree): Boolean = p match { 
          case Bind(_,p)       => isAlternative(p)
          case Alternative(ps) => true 
          case _               => false
        }
        def getAlternativeBranches(p:Tree): List[Tree] = {
          def get_BIND(pctx:Tree => Tree, p:Tree):List[Tree] = p match { 
            case b @ Bind(n,p)   => get_BIND({ x:Tree => pctx(copy.Bind(b, n, x) setType x.tpe) }, p)
            case Alternative(ps) => ps map pctx
          }
          get_BIND({x=>x}, p)
        }
        val Row(opatso, subst, g, bx) = xx
        var opats = opatso
        var pats:List[Tree] = Nil
        var indexOfAlternative = -1
        var j = 0; while(opats ne Nil) {
          var opat = opats.head // original pattern
          val (vars, strippedPat) = strip(opat)
          val vs = vars.toList
          (strippedPat: @unchecked) match {

            case p @ Alternative(ps) => 
              DBG("Alternative")
              if (indexOfAlternative == -1) { 
                unchanged = false
                indexOfAlternative = j 
              }
              pats = opat :: pats
            
            case typat @ Typed(p,tpt) if strip2(p).isInstanceOf[UnApply]=> 
              DBG("Typed")
              pats = (if (temp(j).tpe <:< tpt.tpe) makeBind(vs, p) else opat)::pats
            
            case Ident(nme.WILDCARD) | EmptyTree | _:Literal | _:Typed =>
              DBG("Ident(_)|EmptyTree")
              pats = opat :: pats

            case o @ Ident(n) => // n != nme.WILDCARD 
              DBG("Ident")
              val tpe = 
                if (!o.symbol.isValue) {
                  singleType(o.tpe.prefix, o.symbol)
                } else {
                  singleType(NoPrefix, o.symbol) // equals-check
                  // call the above `stpe'. Then we could also return