parallelmatching.scala

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

      }
    }/*end block*/

    final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = {
      val (branches, defaultV, defaultRepOpt) = this.getTransition // tag body pairs
      val cases = branches map { 
        case (tag, r) => 
          val r2 = rep.make(r.temp, r.row map { case Row(pat, bnd, g, bx) => Row(pat, bindVars(tag, bnd), g, bx) })
          val t2 = repToTree(r2)
          CaseDef(Literal(tag), EmptyTree, t2)
      }
      var ndefault = if (defaultRepOpt.isEmpty) failTree else repToTree(defaultRepOpt.get)
      if (cases.length == 1) {
        val CaseDef(lit,_,body) = cases.head
        If(Equals(mkIdent(this.scrutinee),lit), body, ndefault)
      } else {
        val defCase = CaseDef(mk_(definitions.IntClass.tpe), EmptyTree, ndefault)


        return if (isSameType(this.scrutinee.tpe.widen, definitions.CharClass.tpe))
                  Match(Select(mkIdent(this.scrutinee), nme.toInt), cases ::: defCase :: Nil)
               else
                  Match(mkIdent(this.scrutinee), cases ::: defCase :: Nil)
      }
    }
  }
  
  /** mixture rule for unapply pattern
   */
  class MixUnapply(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) {

    def newVarCapture(pos:Position,tpe:Type)(implicit theOwner:Symbol) = {
      val v = newVar(pos,tpe)
      if (scrutinee.hasFlag(symtab.Flags.TRANS_FLAG))
        v.setFlag(symtab.Flags.TRANS_FLAG) // propagate "unchecked"
      v
    }

    private def bindToScrutinee(x:Symbol) = typedValDef(x,mkIdent(scrutinee))

    val (vs,unapp) = strip(column.head)

    /** returns (unapply-call, success-rep, optional fail-rep*/
    final def getTransition(implicit theOwner: Symbol): (Tree, List[Tree], Rep, Option[Rep]) = {
      unapp match {
        case ua @ UnApply(app @ Apply(fn, appargs), args) => 
          object sameUnapplyCall {
            def unapply(t:Tree) = t match {
              case UnApply(Apply(fn1,_), differentArgs) if (fn.symbol == fn1.symbol) && fn.equalsStructure(fn1) =>
                Some(differentArgs)
              case _ => 
                None
            }
          }
          val ures = newVarCapture(ua.pos, app.tpe)
          val arg0 = mkIdent(scrutinee)
          val rhs = Apply(fn, arg0 :: appargs.tail) setType ures.tpe
          val uacall = typedValDef(ures, rhs) 
        
          val nrowsOther = column.tail.zip(rest.row.tail) flatMap { 
            case (pat, Row(ps, subst, g, bx)) => 
              strip2(pat) match { 
                case sameUnapplyCall(_) => Nil
                case _                  => List(Row(pat::ps, subst, g, bx))
              }}
          val nrepFail = if (nrowsOther.isEmpty) 
                           None 
                         else 
                           Some(rep.make(scrutinee::rest.temp, nrowsOther))
          args.length match {
            case 0  => // special case for unapply(), app.tpe is boolean
              val ntemps = scrutinee :: rest.temp
              val nrows  = column.zip(rest.row) map { 
                case (pat, Row(ps, subst, g, bx)) => 
                  strip2(pat) match { 
                    case sameUnapplyCall(args) =>
                      val nsubst = subst.add(strip1(pat).elements, scrutinee)  
                      Row(EmptyTree::ps, nsubst, g, bx)
                    case _ => 
                      Row(     pat ::ps, subst, g, bx)
                  }}
            (uacall, Nil, rep.make(ntemps, nrows), nrepFail)
 
            case  1 => // special case for unapply(p), app.tpe is Option[T]
              val vtpe = app.tpe.typeArgs(0)
              val vsym = newVarCapture(ua.pos, vtpe)
              val ntemps = vsym :: scrutinee :: rest.temp
              val nrows = column.zip(rest.row) map { 
                case (pat, Row(ps, subst, g, bx)) => 
                  strip2(pat) match { 
                    case sameUnapplyCall(args) =>
                      val nsubst = subst.add(strip1(pat).elements, scrutinee)
                      Row(args(0)   :: EmptyTree :: ps, nsubst, g, bx)
                    case _ => 
                      Row(EmptyTree ::  pat      :: ps, subst, g, bx)
                  }}
              val vdef = typedValDef(vsym, Select(mkIdent(ures), nme.get))
              (uacall, List(vdef), rep.make(ntemps, nrows), nrepFail)

            case _ => // app.tpe is Option[? <: ProductN[T1,...,Tn]]
              val uresGet = newVarCapture(ua.pos, app.tpe.typeArgs(0))
              val vdefs = new ListBuffer[Tree]
              vdefs += typedValDef(uresGet, Select(mkIdent(ures), nme.get))
              var ts = definitions.getProductArgs(uresGet.tpe).get
              var i = 1;
              val vsyms = new ListBuffer[Symbol]
              while(ts ne Nil) {
                val vtpe = ts.head
                val vchild = newVarCapture(ua.pos, vtpe)
                val accSym = definitions.productProj(uresGet, i)
                val rhs = typed(Apply(Select(mkIdent(uresGet), accSym), List()))
                vdefs += typedValDef(vchild, rhs)
                vsyms += vchild
                ts = ts.tail
                i += 1
              } 
              val ntemps  = vsyms.toList ::: scrutinee :: rest.temp
              val dummies = getDummies(i - 1)
              val nrows = column.zip(rest.row) map { 
                case (pat, Row(ps, subst, g, bx)) => 
                  strip2(pat) match { 
                    case sameUnapplyCall(args) =>
                      val nsubst = subst.add(strip1(pat).elements, scrutinee)
                      Row(   args::: EmptyTree ::ps, nsubst, g, bx)
                    case _ =>
                      Row(dummies:::     pat   ::ps, subst, g, bx)
                  }}

              (uacall, vdefs.toList, rep.make(ntemps, nrows), nrepFail)
          }}
    } /* def getTransition(...) */

    final def tree(implicit theOwner: Symbol, failTree: Tree) = {
      val (uacall , vdefs,srep,frep) = this.getTransition
      val succ = repToTree(srep)
      val fail = if (frep.isEmpty) failTree else repToTree(frep.get)
      val cond = 
        if (uacall.symbol.tpe.typeSymbol eq definitions.BooleanClass)
          typed{ mkIdent(uacall.symbol) }
        else 
          emptynessCheck(uacall.symbol)
      typed { squeezedBlock(List(rep.handleOuter(uacall)), If(cond,squeezedBlock(vdefs,succ),fail)) }
    }
  }

  /** handle sequence pattern and ArrayValue (but not star patterns)
   */
  sealed class MixSequence(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) {

    private val sequenceType = scrutinee.tpe.widen.baseType(definitions.SeqClass)
    private val elementType  = getElemType_Sequence(scrutinee.tpe)
    
    final def removeStar(xs:List[Tree]):List[Tree] = 
      xs.take(xs.length-1) ::: makeBind(strip1(xs.last).toList, mk_(sequenceType)) :: Nil
    
    protected def getSubPatterns(len:Int, x:Tree):Option[List[Tree]] = x match {
      case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length == len)   => Some(xs ::: List(EmptyTree))
      case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length == len+1) => Some(removeStar(xs)) // (*) 
      case EmptyTree | Ident(nme.WILDCARD)                                       => Some(getDummies(len+1))
      case _                                                                     => None
    }

    protected def makeSuccRep(vs:List[Symbol], tail:Symbol, nrows:List[Row])(implicit theOwner: Symbol) =
      rep.make( vs ::: tail :: rest.temp, nrows.toList)
    
    /** returns true if x is more general than y */
    protected def subsumes(x:Tree, y:Tree): Boolean = (x,y) match {
      case (av @ ArrayValue(_,xs), bv @ ArrayValue(_,ys)) => 
        isRightIgnoring(av) && !isRightIgnoring(bv) && xs.length == ys.length+1                   // see (*) 
      case _ => 
        false
    }
    // context (to be used in IF), success and failure Rep 
    def getTransition(implicit theOwner: Symbol): (Tree => Tree => Tree, Rep, Rep) = { 

      assert(isSubType(scrutinee.tpe, column.head.tpe), "problem "+scrutinee.tpe+" not <: "+column.head.tpe)

      val treeAsSeq = 
        if (!isSubType(scrutinee.tpe, column.head.tpe))
          typed(gen.mkAsInstanceOf(mkIdent(scrutinee), column.head.tpe, true))
        else
          mkIdent(scrutinee)
    
      column.head match {
        case av @ ArrayValue(_, xs) =>

          var childpats = new ListBuffer[Tree]
          var bindings  = new ListBuffer[Tree]
          var vs        = new ListBuffer[Symbol]
          var ix = 0

        // build new temps on which we will match subpatterns

        // if is right ignoring, don't want last one
          var ys = if (isRightIgnoring(av)) xs.take(xs.length-1) else xs; 
          while(ys ne Nil) {
            val p = strip2(ys.head)
            childpats += p
            val temp = newVar(p.pos, elementType)
            vs += temp
            bindings += typedValDef(temp, seqElement(treeAsSeq.duplicate, ix))
            ix += 1
            ys = ys.tail
          }
          val tail = newVar(scrutinee.pos, sequenceType)
          bindings += typedValDef(tail, {if (ix > 0) seqDrop(treeAsSeq.duplicate, ix) else mkIdent(scrutinee)})


          val nrows = new ListBuffer[Row]
          val frows = new ListBuffer[Row]
          var cs = column; var rw = rest.row; while (cs ne Nil)  {
            (getSubPatterns(ix, cs.head),rw.head) match { 
              case (Some(ps), Row(pats,subst,g,b)) => 
                nrows += Row(     ps ::: pats, subst, g, b)
                if (isDefaultPattern(cs.head) || subsumes(cs.head, av))
                  frows += Row( cs.head :: pats, subst, g, b)
              case (  None , Row(pats,subst,g,b) ) =>
                frows += Row( cs.head :: pats, subst, g, b)
            }
            cs = cs.tail
            rw = rw.tail
          }

          val succRep = makeSuccRep(vs.toList, tail, nrows.toList)
          val failRep = rep.make(          scrutinee :: rest.temp, frows.toList)
          // fixed length
          val cond = getCond(treeAsSeq, xs.length)
          return ({thenp:Tree => {elsep:Tree => 
            If(cond, squeezedBlock(bindings.toList, thenp), elsep)}}, succRep, failRep)
      }
    }

    // lengthArg is exact length
    protected def getCond(tree:Tree, lengthArg:Int) = seqHasLength(tree.duplicate, column.head.tpe, lengthArg)

    final def tree(implicit theOwner: Symbol, failTree: Tree) = {
      val (cx,srep,frep) = this.getTransition
      val succ = repToTree(srep)
      val fail = repToTree(frep)
      cx(succ)(fail)
    }    
  }

  /** handle sequence pattern and ArrayValue (but not star patterns)
   */
  final class MixSequenceStar(scrutinee:Symbol, column:List[Tree], rest:Rep)(implicit rep:RepFactory) extends MixSequence(scrutinee,column,rest) {
    // in principle, we could optimize more, but variable binding gets complicated (@todo use finite state methods instead)
    override def getSubPatterns(minlen:Int, x:Tree) = x match {
      case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length   == minlen) =>  // Seq(p1,...,pN)
        Some(xs ::: gen.mkAttributedRef(definitions.NilModule)  :: EmptyTree :: Nil)
      case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 == minlen) =>  // Seq(p1,...,pN,_*)
        Some(                                   removeStar(xs) ::: EmptyTree :: Nil)
      case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1  < minlen) =>  // Seq(p1..,pJ,_*)   J < N
        Some(                                  getDummies(minlen + 1) ::: x :: Nil)
      case EmptyTree | Ident(nme.WILDCARD)      => 
        Some(                                  getDummies(minlen + 1          + 1))
      case _                                    => 
        None

    }

    override protected def makeSuccRep(vs:List[Symbol], tail:Symbol, nrows:List[Row])(implicit theOwner: Symbol) =
      rep.make( vs ::: tail :: scrutinee :: rest.temp, nrows)

    // lengthArg is minimal length
    override protected def getCond(tree:Tree, lengthArg:Int) = seqLongerThan(tree.duplicate, column.head.tpe, lengthArg - 1)
  }

  
  // @todo: equals test for same constant
  class MixEquals(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) {
    /** condition (to be used in IF), success and failure Rep */
    final def getTransition(implicit theOwner: Symbol): (Tree, Rep, Symbol, Rep) = {
      val nmatrix = rest
      val vlue = (column.head.tpe: @unchecked) match {
        case TypeRef(_,_,List(SingleType(pre,sym))) => 
          gen.mkAttributedRef(pre,sym)
        case TypeRef(_,_,List(PseudoType(o))) => 
          o.duplicate
      }
      assert(vlue.tpe ne null, "value tpe is null")
      val vs = strip1(column.head)
      val nsuccFst = rest.row.head match { case Row(pats,bnd,g,b) => Row(EmptyTree::pats, bnd.add(vs.elements, scrutinee),g,b) }
      val fLabel = theOwner.newLabel(scrutinee.pos, cunit.fresh.newName("failCont%")) // warning, untyped
      val sx     = rep.shortCut(fLabel) // register shortcut
      val nsuccRow = nsuccFst :: Row(getDummies( 1 /*scrutinee*/ + rest.temp.length), NoBinding, EmptyTree, sx) :: Nil

      // todo: optimize if no guard, and no further tests
      val nsucc = rep.make(scrutinee :: rest.temp, nsuccRow)
      val nfail = repWithoutHead(column, rest)
      return (typed{ Equals(mkIdent(scrutinee) setType scrutinee.tpe, vlue) }, nsucc, fLabel, nfail) 
    }

    final def tree(implicit theOwner: Symbol, failTree: Tree) = {
      val (cond, srep, fLabel, frep) = this.getTransition
      val cond2 = typed { rep.handleOuter(cond) }
      val fail = typed { repToTree(frep) }
      fLabel setInfo (new MethodType(Nil, fail.tpe))
      val succ = repToTree(srep)
      try {
        typed{ If(cond2, succ, LabelDef(fLabel, Nil, fail)) }
      } catch {
        case e =>
          Console.println("failed to type-check If")
          Console.println("cond2: "+cond2)
          throw e
      }
    }
  }

  /** mixture rule for type tests
  **/
  class MixTypes(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) {
    
    var casted: Symbol = null
    var moreSpecific: List[Tree] = Nil
    var subsumed:  List[(Int,List[Tree])] = Nil  // row index and subpatterns
    var remaining: List[(Int,Tree)] = Nil  // row index and pattern

    val isExhaustive = !scrutinee.tpe.typeSymbol.hasFlag(symtab.Flags.SEALED) || {
      val tpes = column.map {x => x.tpe.typeSymbol}
      scrutinee.tpe.typeSymbol.children.forall { sym => tpes.contains(sym) }
    }

    private val headPatternType     = strip2(column.head) match {
      case p @ (_:Ident | _:Select) => singleType(p.symbol.tpe.prefix, p.symbol) //should be singleton object
      case __UnApply(_,argtpe,_)    => argtpe
      case _                        => column.head.tpe
    }

    private val isCaseHead = isCaseClass(headPatternType)
    private val dummies = if (!isCaseHead) Nil else getDummies(headPatternType.typeSymbol.caseFieldAccessors.length)
  
    private def subpatterns(pat:Tree): List[Tree] = {
      pat match {
        case Bind(_,p)                                                          => 
          subpatterns(p)
        case app @ Apply(fn, pats) if isCaseClass(app.tpe) && fn.isType => 
          if (isCaseHead) pats else dummies
        case Apply(fn,xs) => assert((xs.isEmpty) && (!fn.isType), "strange Apply"); dummies // named constant
        case _: UnApply                                                         => 
          dummies
        case pat                                                                => 
          dummies
      }
    }

    /** an approximation of _tp1 <:< tp2 that ignores _ types. this code is wrong,
     *  ideally there is a better way to do it, and ideally defined in Types.scala
     */
    def subsumes_erased(_tp1:Type, tp2:Type) = {
      val tp1 = patternType_wrtEquals(_tp1)