diff options
author | Burak Emir <emir@epfl.ch> | 2007-09-26 22:06:56 +0000 |
---|---|---|
committer | Burak Emir <emir@epfl.ch> | 2007-09-26 22:06:56 +0000 |
commit | 67717605c87e854e576489f66cfc150f5eb785f0 (patch) | |
tree | b93d5c707477bce8b9cb2eb0561a2cc5ce2729bd /src | |
parent | 34f6ea9cab4723231d9382b92ea165e007bbdb48 (diff) | |
download | scala-67717605c87e854e576489f66cfc150f5eb785f0.tar.gz scala-67717605c87e854e576489f66cfc150f5eb785f0.tar.bz2 scala-67717605c87e854e576489f66cfc150f5eb785f0.zip |
optimizing irrefutable tuple matches and remove...
optimizing irrefutable tuple matches and removed -Ymatch-algo
Diffstat (limited to 'src')
4 files changed, 103 insertions, 89 deletions
diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala index 52258b3ae6..9aadc00fc5 100644 --- a/src/compiler/scala/tools/nsc/Settings.scala +++ b/src/compiler/scala/tools/nsc/Settings.scala @@ -143,7 +143,6 @@ class Settings(error: String => Unit) { val Xlinearizer = ChoiceSetting ("-Ylinearizer", "Linearizer to use", List("normal", "dfs", "rpo", "dump"), "rpo") val log = PhasesSetting ("-Ylog", "Log operations in") val logAll = BooleanSetting ("-Ylog-all", "Log all operations").hideToIDE - val Xmatchalgo = ChoiceSetting ("-Ymatch-algo", "which match algorithm to use", List("both","par","incr"), "both") val noimports = BooleanSetting ("-Yno-imports", "Compile without any implicit imports") val nopredefs = BooleanSetting ("-Yno-predefs", "Compile without any implicit predefined values") val script = StringSetting ("-Xscript", "object", "compile as a script, wrapping the code into object.main()", "").hideToIDE diff --git a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala index 48d8297d5d..163c6743f3 100644 --- a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala +++ b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala @@ -79,8 +79,9 @@ trait CodeFactory { // --------- these are new - +/* final def renamingBind(defaultv: Set[Symbol], scrut: Symbol, ndefault: Tree) = { + Console.println("renamingbind "+defaultv+" "+scrut+" "+ndefault) if (!defaultv.isEmpty) { var dv: List[Symbol] = Nil var to: List[Symbol] = Nil @@ -92,7 +93,7 @@ trait CodeFactory { tss.traverse(ndefault) } } - +*/ final def emptynessCheck(vsym: Symbol) = { if (vsym.tpe.typeSymbol == definitions.SomeClass) // is Some[_] Literal(Constant(true)) diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala index 581d1e1332..b65b614de1 100644 --- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala +++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala @@ -85,7 +85,7 @@ trait ParallelMatching { if(!isRightIgnoring(av)) { DBG("\n%%% MixSequence"); return new MixSequence(scrutinee, column, rest) } else { DBG("\n%%% MixSequenceStar"); return new MixSequenceStar(scrutinee, column, rest) } } - if(isSimpleSwitch) { //DBG("\n%%% MixLiterals") + if(isSimpleSwitch) { DBG("\n%%% MixLiterals") return new MixLiterals(scrutinee, column, rest) } @@ -273,7 +273,7 @@ trait ParallelMatching { } )} - renamingBind(defaultV, this.scrutinee, ndefault) // each v in defaultV gets bound to scrutinee + //?renamingBind(defaultV, this.scrutinee, ndefault) // each v in defaultV gets bound to scrutinee // make first case a default case. if(this.scrutinee.tpe.typeSymbol.hasFlag(symtab.Flags.SEALED) && defaultV.isEmpty) { @@ -382,14 +382,14 @@ trait ParallelMatching { final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = { val (branches, defaultV, defaultRepOpt) = this.getTransition // tag body pairs - //DBG("[[mix literal transition: branches \n"+(branches.mkString("","\n",""))+"\ndefaults:"+defaultV+"\n"+defaultRepOpt+"\n]]") + DBG("[[mix literal transition: branches \n"+(branches.mkString("","\n",""))+"\ndefaults:"+defaultV+"\n"+defaultRepOpt+"\n]]") val cases = branches map { case (tag, r) => - CaseDef(Literal(tag), EmptyTree, repToTree(rep.make(r.temp, r.row map { case Row(pat,bnd,g,bx) => Row(pat,bindVars(tag,bnd),g,bx) }))) + 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) - - renamingBind(defaultV, this.scrutinee, ndefault) // each v in defaultV gets bound to scrutinee if(cases.length == 1) { val CaseDef(lit,_,body) = cases.head If(Equals(mkIdent(this.scrutinee),lit), body, ndefault) @@ -430,14 +430,14 @@ trait ParallelMatching { val ures = newVarCapture(ua.pos, app.tpe) val n = args.length val uacall = typedValDef(ures, Apply(fn, mkIdent(scrutinee) :: appargs.tail)) - //Console.println("uacall:"+uacall) + //DBG("uacall:"+uacall) val nrowsOther = column.tail.zip(rest.row.tail) flatMap { case (pat, Row(ps, subst, g, bx)) => strip2(pat) match { case UnApply(app @ Apply(fn1,_),args) if fn.symbol==fn1.symbol => Nil case _ => List(Row(pat::ps, subst, g, bx)) }} val nrepFail = if(nrowsOther.isEmpty) None else Some(rep.make(scrutinee::rest.temp, nrowsOther)) - //Console.println("active = "+column.head+" / nrepFail = "+nrepFail) + //DBG("active = "+column.head+" / nrepFail = "+nrepFail) n match { case 0 => //special case for unapply(), app.tpe is boolean val ntemps = scrutinee :: rest.temp @@ -470,7 +470,7 @@ trait ParallelMatching { vdefs += typedValDef(uresGet, Select(mkIdent(ures), nme.get)) var ts = definitions.getProductArgs(uresGet.tpe).get var i = 1; - //Console.println("typeargs"+ts) + //DBG("typeargs"+ts) val vsyms = new ListBuffer[Symbol] while(ts ne Nil) { val vtpe = ts.head @@ -684,7 +684,7 @@ trait ParallelMatching { final def tree(implicit theOwner: Symbol, failTree: Tree) = { val (cond, srep, fLabel, frep) = this.getTransition - //Console.println("MixEquals::tree -- cond "+cond) + //DBG("MixEquals::tree -- cond "+cond) val cond2 = typed { rep.handleOuter(cond) } //DBG("MixEquals, srep = "+srep) //DBG("MixEquals, frep = "+frep) @@ -714,7 +714,7 @@ trait ParallelMatching { val isExhaustive = !scrutinee.tpe.typeSymbol.hasFlag(symtab.Flags.SEALED) || { //DEBUG("check exha for column "+column) - val tpes = column.map {x => /*Console.println("--x:"+x+":"+x.tpe); */ x.tpe.typeSymbol} + val tpes = column.map {x => x.tpe.typeSymbol} scrutinee.tpe.typeSymbol.children.forall { sym => tpes.contains(sym) } } @@ -985,13 +985,13 @@ trait ParallelMatching { case blck @ Block(vdefs, ld @ LabelDef(name,params,body)) => val bx = labelIndex(ld.symbol) if((bx >= 0) && !isReachedTwice(bx)) { - //Console.println("removing labeldef! ") - //Console.println("ld.symbol = "+ld.symbol) - //Console.println("bx = "+bx) - //Console.println("rtwice? "+isReachedTwice(bx)) - //Console.println("reached = "+reached) - squeezedBlock(vdefs,body) - } + /*Console.println("removing labeldef! ") + Console.println("ld.symbol = "+ld.symbol) + Console.println("bx = "+bx) + Console.println("rtwice? "+isReachedTwice(bx)) + Console.println("reached = "+reached) */ + squeezedBlock(vdefs,body) + } else blck @@ -1451,11 +1451,8 @@ trait ParallelMatching { /** creates initial clause matrix */ - final def initRep(selector: Tree, cases: List[Tree], checkExhaustive: Boolean, rep:RepFactory)(implicit theOwner: Symbol) = { - val root = newVar(selector.pos, selector.tpe) + final def initRep(roots: List[Symbol], cases: List[Tree], rep:RepFactory)(implicit theOwner: Symbol) = { // communicate whether exhaustiveness-checking is enabled via some flag - if (!checkExhaustive) - root.setFlag(symtab.Flags.TRANS_FLAG) var bx = 0; val targets = new ListBuffer[Tree] val vss = new ListBuffer[SymList] @@ -1467,12 +1464,18 @@ trait ParallelMatching { //Console.println("dv ::"+definedVars(pat)) vss += definedVars(pat) targets += b - row += Row(List(pat), NoBinding, g, bx) + if(roots.length > 1) pat match { + case Apply(fn, pargs) => + row += Row(pargs, NoBinding, g, bx) + case Ident(nme.WILDCARD) => + row += Row(getDummies(roots.length), NoBinding, g, bx) + } else + row += Row(List(pat), NoBinding, g, bx) bx += 1 cs = cs.tail } //Console.println("leaving initRep") - /*val res = */rep.make(List(root), row.toList, targets.toList, vss.toList) + /*val res = */rep.make(roots, row.toList, targets.toList, vss.toList) //Console.println("left initRep") //res } diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala index 8d34031136..2a244f028d 100644 --- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala +++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala @@ -31,32 +31,8 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with Parall // cache these final val settings_debug = settings.debug.value final val settings_squeeze = settings.Xsqueeze.value == "on" - final val settings_useParallel = settings.Xmatchalgo.value != "incr" - final val settings_useIncr = settings.Xmatchalgo.value != "par" final val settings_casetags = settings.Xcasetags.value == "on" - /** returns true if apply is a "sequence apply". analyzer inserts Sequence nodes if something is a - * - * - last update: discussion with Martin 2005-02-18 - * - * - if true, tree.fn must be ignored. The analyzer ensures that the selector will be a subtype - * of fn; it thus assigns the expected type from the context (which is surely a subtype, - * but may have different flags etc. - * - * - so should be - * (( tree.args.length == 1 ) && tree.args(0).isInstanceOf[Sequence]) - * but fails - */ - final def isSeqApply(tree: Apply): Boolean = { - tree match { - case Apply(_, List(ArrayValue(_,_))) => (tree.tpe.typeSymbol.flags & Flags.CASE) == 0 - case _ => false; - } - } - - /** - */ - final def hasRegularPattern(pats1: List[Tree]): Boolean = { var pats = pats1; while(pats ne Nil) { if(isRegularPattern(pats.head)) { return true; } else { pats = pats.tail } @@ -135,8 +111,16 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with Parall case UnApply(fn, args) => copy.UnApply(pat, fn, args map { isRegular1 }) - // a pattern of the form List(foo@_*) - case app @ Apply(fn, List(pat2@ ArrayValue( tt, List(b @ Bind(id, Star(wc @ Ident(nme.WILDCARD))))))) if isSeqApply(app) => + /* a pattern of the form List(foo@_*), also called "sequence apply". + * + * - last update: discussion with Martin 2005-02-18 + * + * - tree.fn must be ignored. The analyzer ensures that the selector will be a subtype + * of fn; it thus assigns the expected type from the context (which is surely a subtype, + * but may have different flags etc. + */ + case app @ Apply(fn, List(pat2@ ArrayValue( tt, List(b @ Bind(id, Star(wc @ Ident(nme.WILDCARD))))))) if + (app.tpe.typeSymbol.flags & Flags.CASE) == 0 => //Console.println("OPTIMIZING") //Console.println(pat) //Console.println(pat.tpe) @@ -241,48 +225,76 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with Parall //sel EmptyTree } else { + implicit val theOwner = owner + if (settings_debug) { + Console.println("****") + Console.println("**** initalize, selector = "+selector+" selector.tpe = "+selector.tpe) + Console.println("**** doCheckExhaustive == "+doCheckExhaustive) + } + implicit val rep = new RepFactory(handleOuter) + try { + + val tmps = new ListBuffer[Symbol] + val vds = new ListBuffer[Tree] + var root:Symbol = newVar(selector.pos, selector.tpe) + if (!doCheckExhaustive) + root.setFlag(symtab.Flags.TRANS_FLAG) + + var vdef:Tree = typed{ValDef(root, selector)} + var theFailTree:Tree = ThrowMatchError(selector.pos, mkIdent(root)) + + if(definitions.isTupleType(selector.tpe)) selector match { + case app @ Apply(fn, args) + if (fn.symbol eq selector.tpe.decls.lookup(nme.CONSTRUCTOR)) && + (cases forall { x => x match { + case CaseDef(Apply(fn, pargs),_,_) => true ; + case CaseDef(Ident(nme.WILDCARD),_,_) => true ; + case _ => false + }}) => + var i = 0 + var as = args + while(as ne Nil) { + val ti = as.head + val v = newVar(ti.pos, cunit.fresh.newName("tp"), selector.tpe.typeArgs(i)) + if (!doCheckExhaustive) + v.setFlag(symtab.Flags.TRANS_FLAG) + vds += typedValDef(v, ti) + tmps += v + i = i + 1 + as = as.tail + } + theFailTree = ThrowMatchError(selector.pos, copy.Apply(app, fn, tmps.toList map mkIdent)) + case _ => + tmps += root + vds += vdef + } else { + tmps += root + vds += vdef + } + val irep = initRep(tmps.toList, cases, rep) + implicit val fail: Tree = theFailTree -// - - implicit val theOwner = owner - if (settings_debug) { - Console.println("****") - Console.println("**** initalize, selector = "+selector+" selector.tpe = "+selector.tpe) - Console.println("**** doCheckExhaustive == "+doCheckExhaustive) - } - - implicit val rep = new RepFactory(handleOuter) - try { - val irep = initRep(selector, cases, doCheckExhaustive, rep) - val root = irep.temp.head - - implicit val fail: Tree = ThrowMatchError(selector.pos, mkIdent(root)) - val vdef = typed{ValDef(root, selector)} - - val mch = typed{repToTree(irep)} - var dfatree = typed{squeezedBlock(List(vdef), mch)} + val mch = typed{ repToTree(irep)} + var dfatree = typed{squeezedBlock(vds.toList, mch)} - //DEBUG("**** finished\n"+dfatree.toString) - var bx = 0; var cs = cases; while(cs ne Nil) { - if(!rep.isReached(bx)) { - cunit.error(cs.head.asInstanceOf[CaseDef].body.pos, "unreachable code") + //DEBUG("**** finished\n"+dfatree.toString) + var bx = 0; var cs = cases; while(cs ne Nil) { + if(!rep.isReached(bx)) { + cunit.error(cs.head.asInstanceOf[CaseDef].body.pos, "unreachable code") + } + cs = cs.tail + bx += 1 } - cs = cs.tail - bx += 1 + dfatree = rep.cleanup(dfatree) + resetTrav.traverse(dfatree) + return dfatree + } catch { + case e => e.printStackTrace(); throw new FatalError(e.getMessage()) } - dfatree = rep.cleanup(dfatree) - resetTrav.traverse(dfatree) - - //constructParallel(cases) // ZZZ - return dfatree - } catch { - case e => e.printStackTrace(); throw new FatalError(e.getMessage()) - } - } - } + } object resetTrav extends Traverser { override def traverse(x:Tree): unit = x match { @@ -296,5 +308,4 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with Parall } } - } |