parallelmatching.scala

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

/* NSC -- new Scala compiler
 * Copyright 2005-2007 LAMP/EPFL
 * Copyright 2007 Google Inc. All Rights Reserved.
 * Author: [e-mail] (Burak Emir)
 */
// $Id: ParallelMatching.scala 14626 2008-04-10 23:11:00Z emir $

package scala.tools.nsc.matching

import scala.tools.nsc.util.Position
import collection.mutable.ListBuffer

/** Translation of match expressions.
 *
 *  `p':  pattern
 *  `g':  guard
 *  `bx': body index
 *
 *   internal representation is (temp:List[Symbol], row:List[Row])
 *
 *         tmp1      tmp_n
 *    Row( p_11  ...  p_1n   g_1  b_1 ) + subst
 *
 *    Row( p_m1  ...  p_mn   g_m  b_m ) + subst
 *
 */
trait ParallelMatching  {
  self: transform.ExplicitOuter with PatternNodes with CodeFactory =>

  import global._
  import typer.typed
  import symtab.Flags

  // used as argument to `EqualsPatternClass'
  case class PseudoType(o: Tree) extends SimpleTypeProxy {
    override def underlying: Type = o.tpe
  }

  /** picks which rewrite rule to apply
   *  @precondition: column does not contain alternatives (ensured by initRep)
   */
  def MixtureRule(scrutinee: Symbol, column: List[Tree], rest: Rep)(implicit rep: RepFactory): RuleApplication = {
    
    def isSimpleSwitch: Boolean = {
      (isSameType(scrutinee.tpe.widen, definitions.IntClass.tpe) ||
       isSameType(scrutinee.tpe.widen, definitions.CharClass.tpe)) && {
         var xs = column; while(!xs.isEmpty) { // forall
           val h = xs.head
           if (strip2(h).isInstanceOf[Literal] || isDefaultPattern(h))
             xs = xs.tail 
           else 
             return false
         }
         return true
       }}
    
    // an unapply for which we don't need a type test
    def isUnapplyHead(): Boolean = column.head match {
      case __UnApply(_,argtpe,_) => scrutinee.tpe <:< argtpe
      case _                   => false
    }

    // true if pattern type is direct subtype of scrutinee (can't use just <:< cause have to take variance into account)
    def directSubtype(ptpe: Type) =
      (ptpe.parents.exists { x => ((x.typeSymbol eq scrutinee.tpe.typeSymbol) && (x <:< scrutinee.tpe))});
    
    // true if each pattern type is case and direct subtype of scrutinee
    def isFlatCases(col:List[Tree]): Boolean = (col eq Nil) || {
      strip2(col.head) match {
        case a @ Apply(fn,_) => 
          isCaseClass(a.tpe) && directSubtype( a.tpe ) && isFlatCases(col.tail)
        case t @ Typed(_,tpt) =>
          isCaseClass(tpt.tpe) && directSubtype( t.tpe ) && isFlatCases(col.tail)
        case Ident(nme.WILDCARD) =>
          isFlatCases(col.tail) // treat col.tail specially?
        case p =>
          false
      }
    }
    if (isEqualsPattern(column.head.tpe)) {
      return new MixEquals(scrutinee, column, rest)
    }
    if (column.head.isInstanceOf[ArrayValue]) { 
      val av = column.head.asInstanceOf[ArrayValue]
      return if (!isRightIgnoring(av)) 
               new MixSequence(scrutinee, column, rest)
             else 
               new MixSequenceStar(scrutinee, column, rest)
    }
    if (isSimpleSwitch) { 
      return new MixLiterals(scrutinee, column, rest)
    }
    if (settings_casetags && (column.length > 1) && isFlatCases(column)) {
      return new MixCases(scrutinee, column, rest)
    }
    if (isUnapplyHead()) {
      return new MixUnapply(scrutinee, column, rest)
    }
    return new MixTypes(scrutinee, column, rest)
  }

  sealed abstract class RuleApplication(rep: RepFactory) {
    def scrutinee:Symbol

    // used in MixEquals and MixSequence
    final protected def repWithoutHead(col: List[Tree],rest: Rep)(implicit theOwner: Symbol): Rep = {
      var fcol  = col.tail
      var frow  = rest.row.tail
      val nfailrow = new ListBuffer[Row]
      while(fcol ne Nil) {
        val p = fcol.head
        frow.head match {
          case Row(pats, binds, g, bx) => nfailrow += Row(p::pats, binds, g, bx)
        }
        fcol = fcol.tail
        frow = frow.tail
      }
      rep.make(scrutinee::rest.temp, nfailrow.toList)
    }

    /** translate outcome of the rule application into code (possible involving recursive application of rewriting) */
    def tree(implicit theOwner: Symbol, failTree: Tree): Tree 
  }

  case class ErrorRule(implicit rep:RepFactory) extends RuleApplication(rep) {
    def scrutinee:Symbol = throw new RuntimeException("this never happens")
    final def tree(implicit theOwner: Symbol, failTree: Tree) = failTree
  }

  /**  {case ... if guard => bx} else {guardedRest} */
  case class VariableRule(subst:Binding, guard: Tree, guardedRest:Rep, bx: Int)(implicit rep:RepFactory) extends RuleApplication(rep) {
    def scrutinee:Symbol = throw new RuntimeException("this never happens")
    final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = {
      val body = typed { rep.requestBody(bx, subst) }
      if (guard eq EmptyTree) 
        return body
      val vdefs = targetParams(subst)
      val typedElse = repToTree(guardedRest)
      val typedIf = typed { If(guard.duplicate, body, typedElse) }

      typer.typed { squeezedBlock(vdefs, typedIf) }
    }
  } 

  /** superclass of mixture rules for case classes and literals (both translated to switch on an integer)
   */
  abstract class CaseRuleApplication(rep:RepFactory) extends RuleApplication(rep) {
    def column: List[Tree]
    def rest:Rep

    // e.g. (1,1) (1,3) (42,2) for column {case ..1.. => ;; case ..42..=> ;; case ..1.. => }
    protected var defaults: List[Int]    = Nil
    var defaultV: collection.immutable.Set[Symbol] = emptySymbolSet
    
    var theDefaultRows: List[Row] = null
    def getDefaultRows: List[Row] = {
      if (theDefaultRows ne null)
        return theDefaultRows
      var res:List[Row] = Nil
      var ds = defaults; while(ds ne Nil) {
        res = grabRow(ds.head) :: res
        ds = ds.tail
      }
      theDefaultRows = res
      res
    }

    // sorted e.g. case _ => 7,5,1
    protected def insertDefault(tag: Int,vs:Set[Symbol]) { 
      defaultV = defaultV ++ vs
      defaults = insertSorted(tag, defaults)
    }
    protected def haveDefault: Boolean = !defaults.isEmpty    

    var tagIndexPairs: TagIndexPair = null
    
    protected def grabTemps: List[Symbol] = rest.temp
    protected def grabRow(index:Int): Row = rest.row(index) match {
      case r @ Row(pats, s, g, bx) => if (defaultV.isEmpty) r else {
        val vs = strip1(column(index))  // get vars
        val nbindings = s.add(vs.elements,scrutinee)
        Row(pats, nbindings, g, bx)
      }
    }

    /** inserts row indices using in to list of tagindexpairs*/
    protected def tagIndicesToReps(implicit theOwner: Symbol) = {
      val defaultRows = getDefaultRows
      var trs: List[(Int,Rep)] = Nil
      var old = tagIndexPairs
      while (tagIndexPairs ne null) { // collect all with same tag
        val tag = tagIndexPairs.tag
        var tagRows = this.grabRow(tagIndexPairs.index)::Nil
        tagIndexPairs = tagIndexPairs.next
        while ((tagIndexPairs ne null) && tagIndexPairs.tag == tag) {
          tagRows = this.grabRow(tagIndexPairs.index)::tagRows
          tagIndexPairs = tagIndexPairs.next
        }
        trs = (tag, rep.make(this.grabTemps, tagRows ::: defaultRows)) :: trs
      }
      tagIndexPairs = old
      trs
    }

    protected def defaultsToRep(implicit theOwner: Symbol) = rep.make(rest.temp, getDefaultRows)

    protected def insertTagIndexPair(tag: Int, index: Int) { tagIndexPairs = TagIndexPair.insert(tagIndexPairs, tag, index) }

    /** returns 
     *  @return list of continuations, 
     *  @return variables bound to default continuation,  
     *  @return optionally, a default continuation,  
     **/
    def getTransition(implicit theOwner: Symbol): (List[(Int,Rep)],Set[Symbol],Option[Rep]) = 
      (tagIndicesToReps, defaultV, {if (haveDefault) Some(defaultsToRep) else None})
  }

  /** mixture rule for flat case class (using tags)
   *  this rule gets translated to a switch of _.$tag()
  **/
  class MixCases(val scrutinee:Symbol, val column:List[Tree], val rest:Rep)(implicit rep:RepFactory) extends CaseRuleApplication(rep) {

    /** insert row indices into list of tagindexpairs */
    {
      var xs = column; var i  = 0; while(xs ne Nil) { // forall
        val p = strip2(xs.head)
        if (isDefaultPattern(p)) 
          insertDefault(i, strip1(xs.head))
        else 
          insertTagIndexPair(getCaseTag(p.tpe), i)
        i += 1
        xs = xs.tail
      }
    }

    override def grabTemps = scrutinee::rest.temp

    override def grabRow(index:Int) = rest.row(tagIndexPairs.index) match {
      case Row(pats, s, g, bx) => 
        val nbindings = s.add(strip1(column(index)).elements, scrutinee)
        Row(column(tagIndexPairs.index)::pats, nbindings, g, bx)
    }

    final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = {
      val (branches, defaultV, default) = getTransition // tag body pairs

      var ndefault = if (default.isEmpty) failTree else repToTree(default.get)
      var cases = branches map { 
        case (tag, r) => 
          CaseDef(Literal(tag), 
                  EmptyTree, 
                  {
                    val pat  = this.column(this.tagIndexPairs.find(tag));
                    val ptpe = pat.tpe
                    if (this.scrutinee.tpe.typeSymbol.hasFlag(symtab.Flags.SEALED) && strip2(pat).isInstanceOf[Apply]) {
                      //cast 
                      val vtmp = newVar(pat.pos, ptpe)
                      squeezedBlock(
                        List(typedValDef(vtmp, gen.mkAsInstanceOf(mkIdent(this.scrutinee), ptpe))),
                        repToTree(rep.make(vtmp :: r.temp.tail, r.row))
                      )
                    } else repToTree(r)
                  }
                )}
      
      // make first case a default case.
      if (this.scrutinee.tpe.typeSymbol.hasFlag(symtab.Flags.SEALED) && defaultV.isEmpty) {
        ndefault = cases.head.body
        cases = cases.tail
      }
      
      cases.length match {
        case 0 => ndefault
        case 1 => val CaseDef(lit,_,body) = cases.head
                  If(Equals(Select(mkIdent(this.scrutinee), nme.tag), lit), body, ndefault) 
        case _ => val defCase = CaseDef(mk_(definitions.IntClass.tpe), EmptyTree, ndefault)
                  Match(Select(mkIdent(this.scrutinee),nme.tag), cases :::  defCase :: Nil)
      }
    }
  }

  /** mixture rule for literals
   */
  class MixLiterals(val scrutinee:Symbol, val column:List[Tree], val rest:Rep)(implicit rep:RepFactory) extends CaseRuleApplication(rep) {

    private var defaultIndexSet: Set64 = if (column.length < 64) new Set64 else null
    
    override def insertDefault(tag: Int, vs: Set[Symbol]): Unit = 
      if (defaultIndexSet eq null) super.insertDefault(tag,vs)
      else {
        defaultIndexSet |= tag
        defaultV = defaultV ++ vs
      }

    protected override def haveDefault: Boolean = 
      if (defaultIndexSet eq null) super.haveDefault else (defaultIndexSet.underlying != 0)

    override def getDefaultRows: List[Row] = {
      if (theDefaultRows ne null)
        return theDefaultRows
      
      if (defaultIndexSet eq null) 
        super.getDefaultRows
      else {
        var ix = 63
        var res:List[Row] = Nil
        while((ix >= 0) && !defaultIndexSet.contains(ix)) { ix = ix - 1 } 
        while(ix >= 0) {
          res = grabRow(ix) :: res
          ix = ix - 1
          while((ix >= 0) && !defaultIndexSet.contains(ix)) { ix = ix - 1 } 
        }
        theDefaultRows = res
        res
      }
    }

    var varMap: List[(Int,List[Symbol])] = Nil

    private def sanity(pos:Position, tag: Int, pvars:List[Symbol]) {
      varMap = (tag,pvars)::varMap
    } 
    //lazy
    private def bindVars(Tag:Int, orig: Binding): Binding  = {
      def myBindVars(rest:List[(Int,List[Symbol])], bnd: Binding): Binding  = rest match {
        case Nil => bnd
        case (Tag,vs)::xs => myBindVars(xs, bnd.add(vs.elements, scrutinee))
        case (_,  vs)::xs => myBindVars(xs, bnd)
      }
      myBindVars(varMap, orig)
    }

    /*block*/{ 
      var xs = column
      var i  = 0;
      var last = -1;
      while(xs ne Nil) { // forall
        if (last != -1) {
          cunit.error(xs.head.pos, "unreachable code")
        }
        strip(xs.head) match {
          case (pvars, p @ Literal(Constant(c:Int)))  => sanity(p.pos,     c  , definedVars(xs.head)); insertTagIndexPair(c,i)
          case (pvars, p @ Literal(Constant(c:Char))) => sanity(p.pos, c.toInt, definedVars(xs.head)); insertTagIndexPair(c.toInt,i)
          case (pvars, p )     if isDefaultPattern(p) => insertDefault(i,pvars)
          case (pvars, p )     if isDefaultPattern(p) => 
            if (rest.row(i).guard == EmptyTree) {
              last = i;
            } 
            insertDefault(i,pvars)
        }
        i += 1
        xs = xs.tail