From a51f26e6390d16134a30d647b21db41ddaa08710 Mon Sep 17 00:00:00 2001 From: Burak Emir Date: Fri, 24 Feb 2006 18:10:06 +0000 Subject: support for limited regexp pattern matching --- .../scala/tools/nsc/matching/CodeFactory.scala | 2 + .../scala/tools/nsc/matching/PatternMatchers.scala | 92 ++++++++++++++++++---- .../tools/nsc/matching/PatternNodeCreator.scala | 10 +++ .../scala/tools/nsc/matching/PatternNodes.scala | 6 +- .../scala/tools/nsc/matching/TransMatcher.scala | 48 ++++++++--- 5 files changed, 130 insertions(+), 28 deletions(-) diff --git a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala index 2f03283ed0..9ae5b5b98f 100644 --- a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala +++ b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala @@ -186,6 +186,8 @@ mixin class CodeFactory requires TransMatcher { */ def Equals(left: Tree , right: Tree ): Tree = Apply(Select(left, nme.EQEQ), List(right)); + def GreaterThan(left: Tree , right: Tree ): Tree = Apply(Select(left, nme.GT), List(right)); + //deprecated def ThrowMatchError(pos: Int, tpe: Type ) = atPos(pos) { diff --git a/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala index 565e80ea0d..d3d6b9e283 100644 --- a/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala +++ b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala @@ -44,7 +44,7 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An */ def initialize(selector: Tree, owner: Symbol, doBinding: Boolean): Unit = { - //Console.println("pm.initialize selector.tpe = "+selector.tpe); + //Konsole.println("pm.initialize selector.tpe = "+selector.tpe); /* this.mk = new PatternNodeCreator { @@ -61,14 +61,14 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An } */ this.root = pConstrPat(selector.pos, selector.tpe.widen); - //Console.println("selector.tpe "+selector.tpe); - //Console.println("selector.tpe.widen "+selector.tpe.widen); - //Console.println("root.symbol "+root.symbol); - //Console.println("root.symbol.tpe "+root.symbol.tpe); + //Konsole.println("selector.tpe "+selector.tpe); + //Konsole.println("selector.tpe.widen "+selector.tpe.widen); + //Konsole.println("root.symbol "+root.symbol); + //Konsole.println("root.symbol.tpe "+root.symbol.tpe); this.root.and = pHeader(selector.pos, selector.tpe.widen, Ident(root.symbol).setType(root.tpe)); - //Console.println("resultType = "+resultType); + //Konsole.println("resultType = "+resultType); this.owner = owner; this.selector = selector; @@ -133,8 +133,12 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An case Apply(_, args) => if ( isSeqApply(tree.asInstanceOf[Apply]) && !delegateSequenceMatching) args(0) match { - case ArrayValue(_, ts) => // test array values - ts; + case av @ ArrayValue(_, ts) => // test array values + if(isRightIgnoring(av)) { + ts.reverse.drop(1).reverse + } else { + ts; + } //case Sequence(ts) => // ts; case _ => @@ -173,6 +177,8 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An //res; } + //protected var lastSequencePat: PatternNode = null; // hack to optimize sequence matching + protected def patternNode(tree:Tree , header:Header , env: CaseEnv ): PatternNode = { //if(tree!=null) Console.println("patternNode("+tree+","+header+")"); //else scala.Predef.error("got null tree in patternNode"); @@ -217,13 +223,16 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An if (!delegateSequenceMatching) { args(0) match { // case Sequence(ts)=> - case ArrayValue(_, ts)=> - //Console.println("doing pSeqpat "); - val res = pSequencePat(tree.pos, tree.tpe, ts.length); - //Console.println("pSeqpat.casted = "+res.casted); - //Console.println("pSeqpat.casted.pos = "+res.casted.pos); - res - } + case av @ ArrayValue(_, ts)=> + if(isRightIgnoring(av)) { + val castedRest = ts.last match { + case b:Bind => b.symbol; + case _ => null + } + pRightIgnoringSequencePat(tree.pos, tree.tpe, castedRest, ts.length-1); + } else + pSequencePat(tree.pos, tree.tpe, ts.length); + } } else { //Console.println("delegating ... "); val res = pConstrPat(tree.pos, tree.tpe); @@ -326,7 +335,9 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An //case Sequence(ts) => case ArrayValue(_, ts) => if ( !delegateSequenceMatching ) { - pSequencePat(tree.pos, tree.tpe, ts.length); + //lastSequencePat = + pSequencePat(tree.pos, tree.tpe, ts.length); + //lastSequencePat } else { pSeqContainerPat(tree.pos, tree.tpe, tree); } @@ -342,7 +353,18 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An i = i + 1 } pAltPat(tree.pos, subroot.and.asInstanceOf[Header]); - +/* + case Star(Ident(nme.WILDCARD)) => + header.selector match { + case Apply(Select(t, apply), arg @ List(litconst)) => + Console.println(t) + Console.println(apply) + Console.println(litconst) + val tree = Apply(Select(Select(t, "toList"), "drop"), arg) + throw new OptimizeSequencePattern(tree); // ? has to be caught and rethrown by each bind + } + // bind the rest ///////////////////////////////////////////////////// +*/ case _ => if(tree == null) scala.Predef.error("unit = " + cunit + "; tree = null"); @@ -416,6 +438,7 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An 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 + //System.err.println("patArgs = "+patArgs); 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; @@ -475,6 +498,8 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An casted = newCasted; case SequencePat(newCasted, len) => casted = newCasted; + case RightIgnoringSequencePat(newCasted, _, len) => + casted = newCasted; case _ => } var i = 0; while(i < pats.length) { @@ -968,6 +993,39 @@ mixin class PatternMatchers requires (TransMatcher with PatternNodes) extends An gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true))), toTree(node.and))), toTree(node.or, selector.duplicate))); + + case RightIgnoringSequencePat(casted, castedRest, minlen) => + Or( + And( + And(gen.mkIsInstanceOf(selector.duplicate, node.getTpe()), + GreaterThan( + typed( + Apply( + Select( + gen.mkAsInstanceOf(selector.duplicate, + node.getTpe(), + true), + node.getTpe().member(nme.length) /*defs.Seq_length*/), + List()) + ), + typed( + Literal(Constant(minlen)) + ))), + Block( + List( + ValDef(casted, + gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true)), + ValDef(castedRest, + Apply( + Select( + Select( + gen.mkAsInstanceOf(selector.duplicate, node.getTpe(), true), + "toList"), + "drop"), + List(Literal(Constant(minlen)))))), + toTree(node.and))), + toTree(node.or, selector.duplicate)); + case ConstantPat(value) => //Console.println("selector = "+selector); //Console.println("selector.tpe = "+selector.tpe); diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala b/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala index 703763f1a7..6c38893a58 100644 --- a/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala +++ b/src/compiler/scala/tools/nsc/matching/PatternNodeCreator.scala @@ -21,6 +21,16 @@ mixin class PatternNodeCreator requires (TransMatcher with PatternNodes) { node; } + def pRightIgnoringSequencePat(pos: Int, tpe:Type, castedRest1: Symbol, minlen:int) = { + //assert (tpe != null); + val sym = newVar(Position.FIRSTPOS, tpe); + var castedRest = if(castedRest1 != null) castedRest1 else newVar(pos, tpe); + val node = new RightIgnoringSequencePat(sym, castedRest, minlen); + node.pos = pos; + node.tpe = tpe; + node; + } + def pSeqContainerPat(pos: int, tpe: Type, seqpat:Tree ) = { //assert (tpe != null); val sym = newVar(Position.NOPOS, tpe); diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala index e13db74083..39e9a0b9bb 100644 --- a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala +++ b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala @@ -189,6 +189,8 @@ mixin class PatternNodes requires TransMatcher { return "ConstrPat(" + casted + ")"; case SequencePat(casted, len) => return "SequencePat(" + casted + ", " + len + "...)"; + case RightIgnoringSequencePat(casted, castedRest, minlen) => + return "RightIgnoringSequencePat(" + casted + ", " + castedRest + ", "+ minlen + "...)"; case SeqContainerPat(casted, seqpat) => return "SeqContainerPat(" + casted + ", " + seqpat + ")"; case ConstantPat(value) => @@ -304,7 +306,9 @@ mixin class PatternNodes requires TransMatcher { case class ConstantPat(value: Any /*AConstant*/ ) extends PatternNode; case class VariablePat(tree: Tree ) extends PatternNode; case class AltPat(subheader: Header ) extends PatternNode; - case class SequencePat( casted: Symbol, len:int) extends PatternNode; // only used in PatternMatcher + case class SequencePat(casted: Symbol, len:int) extends PatternNode; // only used in PatternMatcher + + case class RightIgnoringSequencePat(casted: Symbol, castedRest: Symbol, minlen: int) extends PatternNode; //PM case class SeqContainerPat(casted: Symbol , seqpat: Tree ) extends PatternNode; // in AlgebraicMatcher /** the environment for a body of a case diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala index bca478b0dc..1d67cda80b 100644 --- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala +++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala @@ -11,6 +11,7 @@ abstract class TransMatcher extends transform.Transform with PatternNodes with CodeFactory with PatternMatchers +with NewMatchers with SequenceMatchers with AlgebraicMatchers with MatcherLabels @@ -127,6 +128,27 @@ with RightTracers { generatedVars; } + protected def isDefault(p: Tree): Boolean = p match { + case Bind(_,q) => isDefault(q); + case Ident(nme.WILDCARD) => true + case _ => false + }; + protected def isDefaultStar(p: Tree): Boolean = p match { + case Bind(_,q) => isDefaultStar(q); + case Star(Ident(nme.WILDCARD)) => true + case _ => false + }; + + // @todo: this should be isNotRegular :-/ premature opt src of all evil + // check special case Seq(_,...,_,_*) + protected def isRightIgnoring(p:ArrayValue): Boolean = p match { + case ArrayValue(s,trees) => + val it = trees.elements; + var c: Tree = null; + while(it.hasNext && {c = it.next; isDefault(c)}) {} + (!it.hasNext) && isDefaultStar(c) + } + class TransMatch extends Transformer { /** a casedef with sequence subpatterns like @@ -138,11 +160,11 @@ with RightTracers { * case .. () .. => val x = Nil; body */ def isRegular(pats:List[CaseDef]): Pair[List[CaseDef],Boolean] = { - var existsReg = false; - var isReg = false; + var existsReg = false; + var isReg = false; var nilVars:List[Symbol] = null; - def isRegular1(pat: Tree): Tree = pat match { + def isRegular1(pat: Tree): Tree = pat match { case Alternative(trees) => copy.Alternative(pat, trees map { isRegular1 }); @@ -160,7 +182,7 @@ with RightTracers { isReg = true; // cause there are ArrayValues now copy.Sequence(pat, trees map { isRegular1 }); - case ArrayValue( tt, List(b @ Bind(id, Star(wc @ Ident(nme.WILDCARD))))) => + case ArrayValue( tt, List(b @ Bind(id, Star(wc @ Ident(nme.WILDCARD))))) => //Console.println("OPTIMIZING"); //Console.println(pat); //Console.println(pat.tpe); @@ -172,9 +194,11 @@ with RightTracers { //Console.println(res); res - case ArrayValue( s, trees ) => - //Console.println("XXX ArrayValue, trees="+trees); - copy.ArrayValue( pat, s, (trees map { isRegular1 })); + case av @ ArrayValue( s, trees ) => + if(isRightIgnoring(av)) + pat + else + copy.ArrayValue( pat, s, (trees map { isRegular1 })); case Apply( fn, List(Sequence(List()))) => pat; @@ -217,11 +241,14 @@ with RightTracers { def handle(sel:Tree, ocases:List[CaseDef]): Tree = { - + // TEMPORARY + //new NewMatcher().toIR(sel, ocases) + // // 1. is there a regular pattern? val Pair(cases, containsReg) = isRegular(ocases); + // @todo: remove unused variables if(containsReg) { @@ -238,8 +265,9 @@ with RightTracers { }.construct( matcher, cases ); matcher.tree */ - System.out.println("" + sel + " match " + ocases); - scala.Predef.error("regular expressions not yet implemented"); + + System.out.println("" + sel + " match " + ocases); + scala.Predef.error("regular expressions not yet implemented"); } else { val pm = new PatternMatcher(); pm.initialize(sel, currentOwner, true ); -- cgit v1.2.3