diff options
author | buraq <buraq@epfl.ch> | 2005-01-24 16:34:05 +0000 |
---|---|---|
committer | buraq <buraq@epfl.ch> | 2005-01-24 16:34:05 +0000 |
commit | f9ccc8451786eaea50cf0bd641d2f784ea6b2048 (patch) | |
tree | b1c0ca2e809099d4141d50132cba8514c638f42d | |
parent | da9f329d8423214b004e023cdccd3eca75c48f8a (diff) | |
download | scala-f9ccc8451786eaea50cf0bd641d2f784ea6b2048.tar.gz scala-f9ccc8451786eaea50cf0bd641d2f784ea6b2048.tar.bz2 scala-f9ccc8451786eaea50cf0bd641d2f784ea6b2048.zip |
t's NEW
-rw-r--r-- | sources/scala/tools/scalac/transformer/matching/PatternMatcher.scala | 907 |
1 files changed, 907 insertions, 0 deletions
diff --git a/sources/scala/tools/scalac/transformer/matching/PatternMatcher.scala b/sources/scala/tools/scalac/transformer/matching/PatternMatcher.scala new file mode 100644 index 0000000000..9f39197d65 --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/PatternMatcher.scala @@ -0,0 +1,907 @@ +/* ____ ____ ____ ____ ______ *\ +** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala ** +** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002, LAMP/EPFL ** +** /_____/\____/\___/\____/____/ ** +** ** +** $Id$ +\* */ + + +import scala.tools.util.Position; +import scalac._; +import scalac.ast._; +import scalac.atree.AConstant; +import scalac.util._; +import scalac.symtab._; +import scalac.transformer.matching.CodeFactory; +import scalac.transformer.matching.PatternNodeCreator; +import scalac.transformer.matching.PatternNode; +import scalac.transformer.matching.CaseEnv; +import scalac.transformer.matching.PatternTool; +import PatternNode._; +import Tree._; + +package scala.tools.scalac.transformer.matching { + +class PatternMatcher(unit: CompilationUnit) extends PatternTool(unit) { + + protected var optimize = true; + protected var delegateSequenceMatching = false; + protected var doBinding = true; + + /** the owner of the pattern matching expression + */ + protected var owner:Symbol = _ ; + + /** the selector expression + */ + protected var selector: Tree = _; + + /** the root of the pattern node structure + */ + protected var root: PatternNode = _; + + /** the symbol of the result variable + */ + protected var resultVar: Symbol = _; + + /** methods to generate scala code + */ + protected var cf: CodeFactory = _; + + /** methods to create pattern nodes + */ + protected var mk: PatternNodeCreator = _; + + /** init method, also needed in subclass AlgebraicMatcher + */ + def initialize(selector: Tree, owner: Symbol, resultType: Type , doBinding: Boolean ): Unit = { + this.mk = new PatternNodeCreator(unit, owner); + this.cf = new CodeFactory(unit, selector.pos); + this.root = mk.ConstrPat(selector.pos, selector.getType().widen()); + this.root.and = mk.Header(selector.pos, + selector.getType().widen(), + gen.Ident(selector.pos, root.symbol())); + this.resultVar = owner.newVariable(selector.pos, + Modifiers.MUTABLE, + Names.result); + this.resultVar.setType(resultType); + this.owner = owner; + this.selector = selector; + this.optimize = this.optimize & (unit.global.target == Global.TARGET_JVM); + this.doBinding = doBinding; + } + + /** pretty printer + */ + def print(): Unit = { + print(root.and, ""); + } + + def print(patNode: PatternNode, indent: String ): Unit = { + + def newIndent(s: String) = { + val removeBar: Boolean = (null == patNode.or); + val sb = new StringBuffer(); + sb.append(indent); + if (removeBar) + sb.setCharAt(indent.length() - 1, ' '); + var i = 0; while(i < s.length()) { + sb.append(' '); + i = i + 1 + } + sb.toString() + } + + if (patNode == null) + System.out.println(indent + "NULL"); + else + patNode.match { + + case Header(selector, next) => + Console.println(indent + "HEADER(" + patNode.getType() + + ", " + selector + ")"); + print(patNode.or, indent + "|"); + if (next != null) + print(next, indent); + + case ConstrPat(casted) => + val s = "-- " + patNode.getType().symbol().name + + "(" + patNode.getType() + ", " + casted + ") -> "; + val nindent = newIndent(s); + Console.println(nindent + s); + print(patNode.and, nindent); + if (patNode.or != null) + print(patNode.or, indent); + + case SequencePat( casted, plen ) => + val s = "-- " + patNode.getType().symbol().name + "(" + + patNode.getType() + + ", " + casted + ", " + plen + ") -> "; + val nindent = newIndent(s); + Console.println(indent + s); + print(patNode.and, nindent); + if (patNode.or != null) + print(patNode.or, indent); + + case DefaultPat() => + Console.println(indent + "-- _ -> "); + print(patNode.and, indent.substring(0, indent.length() - 1) + + " "); + if (patNode.or != null) + print(patNode.or, indent); + + case ConstantPat(value) => + val s = "-- CONST(" + value + ") -> "; + val nindent = newIndent(s); + Console.println(indent + s); + print(patNode.and, nindent); + if (patNode.or != null) + print(patNode.or, indent); + + case VariablePat(tree) => + val s = "-- STABLEID(" + tree + ": " + patNode.getType() + ") -> "; + val nindent = newIndent(s); + Console.println(indent + s); + print(patNode.and, nindent); + if (patNode.or != null) + print(patNode.or, indent); + + case AltPat(header) => + Console.println(indent + "-- ALTERNATIVES:"); + print(header, indent + " * "); + print(patNode.and, indent + " * -> "); + if (patNode.or != null) + print(patNode.or, indent); + + case Body(_, guards, stats) => + if ((guards.length == 0) && (stats.length == 0)) + Console.println(indent + "true"); + else + Console.println(indent + "BODY(" + stats.length + ")"); + + } + } + + /** enters a sequence of cases into the pattern matcher + */ + def construct(cases: Array[Tree]): Unit = { + var i = 0; while(i < cases.length) { + enter(cases(i)); + i = i + 1 + } + } + + /** enter a single case into the pattern matcher + */ + protected def enter(caseDef: Tree): Unit = { + caseDef match { + case CaseDef(pat, guard, body) => + val env = new CaseEnv(owner, unit); + // PatternNode matched = match(pat, root); + val target = enter1(pat, -1, root, root.symbol(), env); + // if (target.and != null) + // unit.error(pat.pos, "duplicate case"); + if (null == target.and) + target.and = mk.Body(caseDef.pos, env.boundVars(), guard, body); + else if (target.and.isInstanceOf[Body]) + updateBody(target.and.asInstanceOf[Body], env.boundVars(), guard, body); + else + unit.error(pat.pos, "duplicate case"); + } + } + + protected def updateBody(tree: Body, bound: Array[ValDef], guard: Tree , body: Tree): Unit = { + if (tree.guard(tree.guard.length - 1) == Tree.Empty) { + //unit.error(body.pos, "unreachable code"); + } else { + val bd = new Array[Array[ValDef]](tree.bound.length + 1); + val ng = new Array[Tree](tree.guard.length + 1); + val nb = new Array[Tree](tree.body.length + 1); + System.arraycopy(tree.bound, 0, bd, 0, tree.bound.length); + System.arraycopy(tree.guard, 0, ng, 0, tree.guard.length); + System.arraycopy(tree.body, 0, nb, 0, tree.body.length); + bd(bd.length - 1) = bound; + ng(ng.length - 1) = guard; + nb(nb.length - 1) = body; + tree.bound = bd; + tree.guard = ng; + tree.body = nb; + } + } + + protected def patternArgs(tree: Tree):Array[Tree] = { + tree.match { + case Bind(_, pat) => + patternArgs(pat); + case Apply(_, args) => + if ( isSeqApply(tree.asInstanceOf[Apply]) && !delegateSequenceMatching) + args(0) match { + case Sequence(ts) => + ts; + case _ => + args; + } + else args + case Sequence(ts) => + if (!delegateSequenceMatching) + ts; + else + Tree.EMPTY_ARRAY; + case _ => + Tree.EMPTY_ARRAY; + } + } + + protected def isSeqApply( tree: Tree.Apply ): Boolean = { + if(( tree.args.length == 1 ) + && (tree.getType().symbol().flags & Modifiers.CASE) == 0) + tree.args(0).match { + case Sequence( _ ) => + true; + case _ => + false; + } + else + false; + } + + protected def patternNode(tree:Tree , header:Header , env: CaseEnv ): PatternNode = { + //Console.println("patternNode("+tree+","+header+")"); + tree.match { + case Bind(name, Typed(Ident(Names.PATTERN_WILDCARD), tpe)) => // x@_:Type + if(header.getType().isSubType(tpe.getType())) { + val node = mk.DefaultPat(tree.pos, tpe.getType()); + env.newBoundVar( tree.symbol(), tree.getType(), header.selector ); + node; + } else { + val node = mk.ConstrPat(tree.pos, tpe.getType()); + env.newBoundVar( tree.symbol(), tree.getType(), gen.Ident(tree.pos, node.casted)); + node; + } + case Bind(name, Ident(Names.PATTERN_WILDCARD)) => // x @ _ + val node = mk.DefaultPat(tree.pos, header.getType()); + if ((env != null) && (tree.symbol() != defs.PATTERN_WILDCARD)) + env.newBoundVar( tree.symbol(), tree.getType(), header.selector); + node; + case Bind(name, pat) => + val node = patternNode(pat, header, env); + if ((env != null) && (tree.symbol() != defs.PATTERN_WILDCARD)) { + val casted = node.symbol(); + val theValue = if (casted == Symbol.NONE) header.selector else gen.Ident(tree.pos, casted); + env.newBoundVar(tree.symbol(), tree.getType(), theValue); + } + node; + case t @ Apply(fn, args) => // pattern with args + if(isSeqApply(t)) { + if (!delegateSequenceMatching) { + args(0).match { + case Sequence(ts)=> + mk.SequencePat(tree.pos, tree.getType(), ts.length); + } + } else { + val res = mk.ConstrPat(tree.pos, tree.getType()); + res.and = mk.Header(tree.pos, header.getType(), header.selector); + res.and.and = mk.SeqContainerPat(tree.pos, tree.getType(), args(0)); + res; + } + } else if ((fn.symbol() != null) && + fn.symbol().isStable() && + !(fn.symbol().isModule() && + ((fn.symbol().flags & Modifiers.CASE) != 0))) { + mk.VariablePat(tree.pos, tree); + } + else + mk.ConstrPat(tree.pos, tree.getType()); + + case t @ Typed(ident, tpe) => // variable pattern + val doTest = header.getType().isSubType(tpe.getType()); + val node = { + if(doTest) + mk.DefaultPat(tree.pos, tpe.getType()) + else + mk.ConstrPat(tree.pos, tpe.getType()); + } + if ((null != env) && (ident.symbol() != defs.PATTERN_WILDCARD)) + node.match { + case ConstrPat(casted) => + env.newBoundVar(t.expr.symbol(), + tpe.getType(), + gen.Ident(tree.pos, casted)); + case _ => + env.newBoundVar(t.expr.symbol(), + tpe.getType(), + {if(doTest) header.selector else gen.Ident(tree.pos, node.asInstanceOf[ConstrPat].casted)}); + } + node; + + case Ident(name) => // pattern without args or variable + if (tree.symbol() == defs.PATTERN_WILDCARD) + mk.DefaultPat(tree.pos, header.getType()); + else if (tree.symbol().isPrimaryConstructor()) { + throw new ApplicationError("this may not happen"); // Burak + } else if (name.isVariable()) {// Burak + throw new ApplicationError("this may not happen"); // Burak + } else + mk.VariablePat(tree.pos, tree); + + case Select(_, name) => // variable + if (tree.symbol().isPrimaryConstructor()) + mk.ConstrPat(tree.pos, tree.getType()); + else + mk.VariablePat(tree.pos, tree); + + case Literal(value) => + mk.ConstantPat(tree.pos, tree.getType(), value); + + case Sequence(ts) => + if ( !delegateSequenceMatching ) { + mk.SequencePat(tree.pos, tree.getType(), ts.length); + } else { + mk.SeqContainerPat(tree.pos, tree.getType(), tree); + } + case Alternative(ts) => + if(ts.length < 2) + throw new ApplicationError("ill-formed Alternative"); + val subroot = mk.ConstrPat(header.pos, header.getType()); + subroot.and = mk.Header(header.pos, header.getType(), header.selector.duplicate()); + val subenv = new CaseEnv(owner, unit); + var i = 0; while(i < ts.length) { + val target = enter1(ts(i), -1, subroot, subroot.symbol(), subenv); + target.and = mk.Body(tree.pos); + i = i + 1 + } + mk.AltPat(tree.pos, subroot.and.asInstanceOf[Header]); + + case _ => + throw new ApplicationError("unit = " + unit + "; tree = "+tree); + } + } + + protected def enter(pat: Tree, index: Int, target: PatternNode, casted: Symbol, env: CaseEnv ): PatternNode = { + target.match { + case ConstrPat(newCasted) => + enter1(pat, index, target, newCasted, env); + case SequencePat(newCasted, len) => + enter1(pat, index, target, newCasted, env); + case _ => + enter1(pat, index, target, casted, env); + } + } + + private def newHeader(pos: Int, casted: Symbol, index: Int): Header = { + val ident = gen.Ident( pos, casted ); + if (casted.pos == Position.FIRSTPOS) { + val t = gen.mkApply_V( + gen.Select( ident, defs.FUNCTION_APPLY( 1 )), + Predef.Array[Tree]( gen.mkIntLit( pos, index ) )); + val seqType = t.getType(); + mk.Header( pos, seqType, t ); + } else { + val ts = casted.getType().symbol().asInstanceOf[ClassSymbol] + .caseFieldAccessor(index); + val accType = casted.getType().memberType(ts); + val accTree = gen.Select( ident, ts); + accType.match { + // scala case accessor + case Type.MethodType(_, _) => + mk.Header(pos, accType.resultType(), gen.mkApply__(accTree)); + // jaco case accessor + case _ => + mk.Header(pos, accType, accTree); + } + } + } + + /** main enter function + * + * invariant: ( curHeader == (Header)target.and ) holds + */ + protected def enter1(pat: Tree, index: Int, target: PatternNode, casted: Symbol, env: CaseEnv): PatternNode = { + //System.err.println("enter(" + pat + ", " + index + ", " + target + ", " + casted + ")"); + val patArgs = patternArgs(pat); // get pattern arguments + var curHeader = target.and.asInstanceOf[Header]; // advance one step in intermediate representation + if (curHeader == null) { // check if we have to add a new header + //assert index >= 0 : casted; + if( index < 0 ) throw new ApplicationError("error entering:"+casted); + target.and = {curHeader = newHeader(pat.pos, casted, index); curHeader}; + curHeader.or = patternNode(pat, curHeader, env); + enter(patArgs, curHeader.or, casted, env); + } else { + // find most recent header + while (curHeader.next != null) + curHeader = curHeader.next; + // create node + var patNode = patternNode(pat, curHeader, env); + var next: PatternNode = curHeader; + // add branch to curHeader, but reuse tests if possible + while (true) { + if (next.isSameAs(patNode)) { // test for patNode already present --> reuse + // substitute... !!! + patNode.match { + case ConstrPat(ocasted) => + env.substitute(ocasted, gen.Ident(patNode.pos, + next.asInstanceOf[ConstrPat].casted)); + case _ => + } + return enter(patArgs, next, casted, env); + } else if (next.isDefaultPat() || // default case reached, or + ((next.or == null) && // no more alternatives and + (patNode.isDefaultPat() || next.subsumes(patNode)))) { + // new node is default or subsumed + var header = mk.Header(patNode.pos, + curHeader.getType(), + curHeader.selector); + curHeader.next = header; + header.or = patNode; + return enter(patArgs, + patNode, + casted, + env); + } + else if (next.or == null) { + return enter(patArgs, {next.or = patNode; patNode}, casted, env); // add new branch + } else + next = next.or; + } + throw new ApplicationError("must not happen"); + null // never reached + } + } + + /** calls enter for an array of patterns, see enter + */ + protected def enter(pats:Array[Tree], target1: PatternNode , casted1: Symbol , env: CaseEnv): PatternNode = { + var target = target1; + var casted = casted1; + target.match { + case ConstrPat(newCasted) => + casted = newCasted; + case SequencePat(newCasted, len) => + casted = newCasted; + case _ => + } + var i = 0; while(i < pats.length) { + target = enter1(pats(i), i, target, casted, env); + i = i + 1 + } + target; + } + + protected def nCaseComponents(tree: Tree): int = { + tree.match { + case Apply(fn, _) => + val tpe = tree.getType().symbol().primaryConstructor().getType(); + //Console.println("~~~ " + tree.type() + ", " + tree.type().symbol().primaryConstructor()); + tpe.match { + // I'm not sure if this is a good idea, but obviously, currently all case classes + // without constructor arguments have type NoType + case Type.NoType => + throw new ApplicationError("this cannot happen"); + 0 + case Type.MethodType(args, _) => + args.length; + case Type.PolyType(tvars, Type.MethodType(args, _)) => + args.length; + case Type.PolyType(tvars, _) => + 0; + case _ => + throw new ApplicationError("not yet implemented;" + + "pattern matching for " + tree + ": " + tpe); + } + } + return 0; + } + + + //////////// generator methods + + def toTree(): Tree = { + if (optimize && isSimpleIntSwitch()) + intSwitchToTree(); + else if (false && optimize && isSimpleSwitch()) + switchToTree(); + else { + //print(); + generalSwitchToTree(); + } + } + + case class Break(res:Boolean) extends java.lang.Throwable; + case class Break2() extends java.lang.Throwable; + + protected def isSimpleSwitch(): Boolean = { + print(); + var patNode = root.and; + while (patNode != null) { + var node = patNode; + while (({node = node.or; node}) != null) { + node.match { + case VariablePat(tree) => + Console.println(((tree.symbol().flags & Modifiers.CASE) != 0)); + case ConstrPat(_) => + Console.println(node.getType().toString() + " / " + ((node.getType().symbol().flags & Modifiers.CASE) != 0)); + var inner = node.and; + def funct(inner: PatternNode): Boolean = { + //outer: while (true) { + inner.match { + case Header(_, next) => + if (next != null) + throw Break(false); + funct(inner.or) + + case DefaultPat() => + funct(inner.and); + + case Body(bound, guard, _) => + if ((guard.length > 1) || + (guard(0) != Tree.Empty)) + throw Break(false); + + throw Break2() // break outer + case _ => + Console.println(inner); + throw Break(false); + } + } + var res = false; + var set = false; + try { + funct(inner) + } catch { + case Break(res1) => + res = res1; + set = true; + case Break2() => + } + if(set) return res; + case _ => + return false; + } + } + patNode = patNode.next(); + } + return true; + } + + protected def isSimpleIntSwitch(): Boolean = { + if (selector.getType().widen().isSameAs(defs.int_TYPE())) { + var patNode = root.and; + while (patNode != null) { + var node = patNode; + while (({node = node.or; node}) != null) { + node.match { + case ConstantPat(_) => ; + case _ => + return false; + } + node.and.match { + case Body(bound, guard, _) => + if ((guard.length > 1) || + (guard(0) != Tree.Empty) || + (bound(0).length > 0)) + return false; + case _ => + return false; + } + } + patNode = patNode.next(); + } + return true; + } else + return false; + } + + class TagBodyPair(tag1: Int, body1: Tree, next1:TagBodyPair ) { + + var tag: int = tag1; + var body: Tree = body1; + var next: TagBodyPair = next1; + + def length(): Int = { + if (null == next) 1 else (next.length() + 1); + } + } + + /* static */ + def insert( tag:int, body:Tree, current:TagBodyPair ): TagBodyPair = { + if (current == null) + return new TagBodyPair(tag, body, null); + else if (tag > current.tag) + return new TagBodyPair(current.tag, current.body, insert(tag, body, current.next)); + else + return new TagBodyPair(tag, body, current); + } + + protected def numCases(patNode1: PatternNode): Int = { + var patNode = patNode1; + var n = 0; + while (({patNode = patNode.or; patNode}) != null) + patNode.match { + case DefaultPat() => ; + case _ => + n = n + 1; + } + n; + } + + protected def defaultBody(patNode1: PatternNode, otherwise: Tree ): Tree = { + var patNode = patNode1; + while (patNode != null) { + var node = patNode; + while (({node = node.or; node}) != null) + node.match { + case DefaultPat() => + return bodyToTree(node.and); + } + patNode = patNode.next(); + } + otherwise; + } + + /** This method translates pattern matching expressions that match + * on integers on the top level. + */ + def intSwitchToTree(): Tree = { + //print(); + val ncases = numCases(root.and); + val matchError = cf.ThrowMatchError(selector.pos, resultVar.getType()); + // without a case, we return a match error if there is no default case + if (ncases == 0) + return defaultBody(root.and, matchError); + // for one case we use a normal if-then-else instruction + else if (ncases == 1) { + root.and.or.match { + case ConstantPat(value) => + return gen.If(cf.Equals(selector, + gen.Literal(root.and.or.pos, value)), + bodyToTree(root.and.or.and), + defaultBody(root.and, matchError)); + case _ => + return generalSwitchToTree(); + } + } + // + // if we have more than 2 cases than use a switch statement + root.and.match { + case Header(_, next) => + var mappings: TagBodyPair = null; + var defaultBody = matchError; + var patNode = root.and; + while (patNode != null) { + var node = patNode.or; + while (node != null) { + node.match { + case DefaultPat() => + if (defaultBody != null) + throw new ApplicationError(); + defaultBody = bodyToTree(node.and); + node = node.or; + + case ConstantPat(AConstant.INT(value))=> + mappings = insert( + value, + bodyToTree(node.and), + mappings); + node = node.or; + + case _ => + throw new ApplicationError(node.toString()); + } + } + patNode = patNode.next(); + } + if (mappings == null) { + return gen.Switch(selector, new Array[int](0), new Array[Tree](0), defaultBody, resultVar.getType()); + } else { + var n = mappings.length(); + val tags = new Array[Int](n); + val bodies = new Array[Tree](n); + n = 0; + while (mappings != null) { + tags(n) = mappings.tag; + bodies(n) = mappings.body; + n = n + 1; + mappings = mappings.next; + } + return gen.Switch(selector, tags, bodies, defaultBody, resultVar.getType()); + } + case _ => + throw new ApplicationError(); + } + } + + protected def bodyToTree(node: PatternNode): Tree = { + node.match { + case Body(_, _, body) => + return body(0); + case _ => + throw new ApplicationError(); + } + } + + def switchToTree(): Tree = { + throw new Error(); + } + + def generalSwitchToTree(): Tree = { + val ts = Predef.Array[Tree] ( + gen.ValDef(root.symbol(), selector), + gen.ValDef(resultVar, gen.mkDefaultValue(selector.pos, resultVar.getType()))); + val res = gen.If( + selector.pos, + toTree(root.and), + gen.Ident(selector.pos, resultVar), + cf.ThrowMatchError(selector.pos, resultVar.getType(), gen.Ident(selector.pos, root.symbol()))); + return gen.mkBlock(selector.pos, ts, res); + } + + /*protected*/ def toTree(node1: PatternNode): Tree = { + var node = node1; + var res = gen.mkBooleanLit(node.pos, false); + while (node != null) + node.match { + case Header(selector, next) => + //res = cf.And(mkNegate(res), toTree(node.or, selector)); + //Console.println("HEADER TYPE = " + selector.type); + if (optimize(node.getType(), node.or)) + res = cf.Or(res, toOptTree(node.or, selector)); + else + res = cf.Or(res, toTree(node.or, selector)); + node = next; + + case Body(bound1, guard, body) => + var bound = bound1; + if ((bound.length == 0) && + (guard.length == 0) && + (body.length == 0)) { + return gen.mkBooleanLit(node.pos, true); // cf.Or(res, gen.mkBooleanLit(node.pos, true)); + } else if (!doBinding) + bound = Predef.Array[Array[ValDef]]( Predef.Array[ValDef]() ); + var i = guard.length - 1; while(i >= 0) { + val ts = bound(i).asInstanceOf[Array[Tree]]; + var res0 = gen.mkBlock(gen.Assign(gen.Ident(body(i).pos, resultVar), + body(i)), + gen.mkBooleanLit(body(i).pos, true)); + if (guard(i) != Tree.Empty) + res0 = cf.And(guard(i), res0); + res = cf.Or(gen.mkBlock(body(i).pos, ts, res0), res); + i = i - 1 + } + return res; + case _ => + throw new ApplicationError(); + } + return res; + } + + protected def optimize(selType:Type, alternatives1: PatternNode ): boolean = { + var alternatives = alternatives1; + if (!optimize || !selType.isSubType(defs.SCALAOBJECT_TYPE())) + return false; + var cases = 0; + while (alternatives != null) { + alternatives match { + case ConstrPat(_) => + if (alternatives.getType().symbol().isCaseClass()) + cases = cases +1; + else + return false; + + case DefaultPat() => + ; + case _ => + return false; + } + alternatives = alternatives.or; + } + return cases > 2; + } + + class TagNodePair(tag1: int, node1: PatternNode, next1: TagNodePair) { + var tag: int = tag1; + var node: PatternNode = node1; + var next: TagNodePair = next1; + + def length(): Int = { + return if (null == next) 1 else (next.length() + 1); + } + } + + def insert(tag: Int, node: PatternNode, current: TagNodePair): TagNodePair = { + if (current == null) + return new TagNodePair(tag, node, null); + else if (tag > current.tag) + return new TagNodePair(current.tag, current.node, insert(tag, node, current.next)); + else if (tag == current.tag) { + val old = current.node; + ({current.node = node; node}).or = old; + return current; + } else + return new TagNodePair(tag, node, current); + } + + def insertNode(tag:int , node:PatternNode , current:TagNodePair ): TagNodePair = { + val newnode = node.dup(); + newnode.or = null; + return insert(tag, newnode, current); + } + + protected def toOptTree(node1: PatternNode, selector: Tree): Tree = { + var node = node1; + //System.err.println("pm.toOptTree called"+node); + var cases: TagNodePair = null; + var defaultCase: PatternNode = null; + while (node != null) + node.match { + case ConstrPat(casted) => + cases = insertNode(node.getType().symbol().tag(), node, cases); + node = node.or; + + case DefaultPat() => + defaultCase = node; + node = node.or; + + case _ => + throw new ApplicationError(); + } + var n = cases.length(); + val tags = new Array[int](n); + val bodies = new Array[Tree](n); + n = 0; + while (null != cases) { + tags(n) = cases.tag; + bodies(n) = toTree(cases.node, selector); + n = n + 1; + cases = cases.next; + } + return gen.Switch(gen.mkApply__(gen.Select(selector.duplicate(), defs.SCALAOBJECT_TAG())), + tags, + bodies, + { if (defaultCase == null) gen.mkBooleanLit(selector.pos, false) else toTree(defaultCase.and) }, + defs.boolean_TYPE()); + } + + protected def toTree(node:PatternNode , selector:Tree ): Tree = { + //System.err.println("pm.toTree("+node+","+selector+")"); + if (node == null) + return gen.mkBooleanLit(selector.pos, false); + else + node.match { + case DefaultPat() => + return toTree(node.and); + + case ConstrPat(casted) => + return gen.If(gen.mkIsInstanceOf(selector.duplicate(), node.getType()), + gen.mkBlock(gen.ValDef(casted, + gen.mkAsInstanceOf(selector.duplicate(), node.getType())), + toTree(node.and)), + toTree(node.or, selector.duplicate())); + case SequencePat(casted, len) => + return gen.If(cf.And(gen.mkIsInstanceOf(selector.duplicate(), node.getType()), + cf.Equals(gen.mkApply__(gen.Select(gen.mkAsInstanceOf(selector.duplicate(), node.getType()), + defs.SEQ_LENGTH())), + gen.mkIntLit(selector.pos, len))), + gen.mkBlock(gen.ValDef(casted, + gen.mkAsInstanceOf(selector.duplicate(), node.getType())), + toTree(node.and)), + toTree(node.or, selector.duplicate())); + case ConstantPat(value) => + return gen.If(cf.Equals(selector.duplicate(), + gen.Literal(selector.pos, value)), + toTree(node.and), + toTree(node.or, selector.duplicate())); + case VariablePat(tree) => + return gen.If(cf.Equals(selector.duplicate(), tree), + toTree(node.and), + toTree(node.or, selector.duplicate())); + case AltPat(header) => + return gen.If(toTree(header), + toTree(node.and), + toTree(node.or, selector.duplicate())); + case _ => + throw new ApplicationError(); + } + } +} +} |