From 0b2f65aa6c6b3bb3e7628720893fb8116fdc8f71 Mon Sep 17 00:00:00 2001 From: Burak Emir Date: Sun, 16 Sep 2007 02:39:52 +0000 Subject: fixed seq matching bug + reorganized test cases --- .../tools/nsc/matching/ParallelMatching.scala | 55 ++++--- .../scala/tools/nsc/matching/PatternMatchers.scala | 8 +- .../scala/tools/nsc/matching/TransMatcher.scala | 2 +- test/files/run/patmatnew.scala | 157 +++++++++++++++++++- test/files/run/regularpatmatnew.check | 0 test/files/run/regularpatmatnew.scala | 158 --------------------- 6 files changed, 196 insertions(+), 184 deletions(-) delete mode 100644 test/files/run/regularpatmatnew.check delete mode 100644 test/files/run/regularpatmatnew.scala diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala index 06b9077168..5c0e05ebfc 100644 --- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala +++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala @@ -75,11 +75,7 @@ trait ParallelMatching { false } } - /* - //DBG("/// MixtureRule("+scrutinee.name+":"+scrutinee.tpe+","+column+", rep = ") - //DBG(rest.toString) - //DBG(")///") - */ + if(isEqualsPattern(column.head.tpe)) { DBG("\n%%% MixEquals"); return new MixEquals(scrutinee, column, rest) } @@ -527,13 +523,23 @@ trait ParallelMatching { 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 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 // (*) + case _ => + false + } // context (to be used in IF), success and failure Rep - final def getTransition(implicit theOwner: Symbol): (Tree => Tree => Tree, Rep, 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) @@ -558,15 +564,15 @@ trait ParallelMatching { val p = strip2(ys.head) childpats += p val temp = newVar(p.pos, elementType) - DBG("new temp:"+temp+":"+temp.tpe) - DBG("seqelem:"+seqElement(treeAsSeq.duplicate, ix)) + //DBG("new temp:"+temp+":"+temp.tpe) + //DBG("seqelem:"+seqElement(treeAsSeq.duplicate, ix)) 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-1>0) seqDrop(treeAsSeq.duplicate, ix-1) else mkIdent(scrutinee)}) + bindings += typedValDef(tail, {if(ix-1>0) seqDrop(treeAsSeq.duplicate, ix) else mkIdent(scrutinee)}) val nrows = new ListBuffer[Row] @@ -576,7 +582,7 @@ trait ParallelMatching { (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)) + 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) @@ -585,7 +591,7 @@ trait ParallelMatching { rw = rw.tail } - val succRep = rep.make( vs.toList ::: tail :: rest.temp, nrows.toList) + val succRep = makeSuccRep(vs.toList, tail, nrows.toList) val failRep = rep.make( scrutinee :: rest.temp, frows.toList) @@ -616,6 +622,8 @@ trait ParallelMatching { final def tree(implicit theOwner: Symbol, failTree: Tree) = { val (cx,srep,frep) = this.getTransition + //DBG("MSSf:"+srep.toString) + //DBG("MSSs:"+frep.toString) val succ = repToTree(srep) val fail = repToTree(frep) cx(succ)(fail) @@ -626,14 +634,25 @@ trait ParallelMatching { 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) => Some(xs ::: List(EmptyTree)) - case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 == minlen) => Some(removeStar(xs)) - case EmptyTree | Ident(nme.WILDCARD) => Some(getDummies(minlen+1)) - case _ => None + 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 - protected override def getCond(tree:Tree, lengthArg:Int) = seqLongerThan(tree.duplicate, column.head.tpe, lengthArg - 1) + override protected def getCond(tree:Tree, lengthArg:Int) = seqLongerThan(tree.duplicate, column.head.tpe, lengthArg - 1) } @@ -1027,7 +1046,7 @@ trait ParallelMatching { //Console.println(jumpT) return jump } - DBG("requestbody("+bx+", "+subst+") isReached(bx)?"+isReached(bx)+" labels:"); + //DBG("requestbody("+bx+", "+subst+") isReached(bx)?"+isReached(bx)+" labels:"); //{for(s<-labels) Console.print({if(s ne null) {s} else "_"}+",")} //DBG("vss(bx) = "+vss(bx)) if(!isReached(bx)) { // first time this bx is requested diff --git a/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala index 60b9183b74..780cc46b8c 100644 --- a/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala +++ b/src/compiler/scala/tools/nsc/matching/PatternMatchers.scala @@ -18,6 +18,7 @@ trait PatternMatchers { self: transform.ExplicitOuter with PatternNodes with Par import typer.typed import symtab.Flags +/* abstract class CantHandle // extends Exception object CantHandleSeq extends CantHandle object CantHandleUnapply extends CantHandle @@ -27,7 +28,7 @@ trait PatternMatchers { self: transform.ExplicitOuter with PatternNodes with Par object CantHandleGuard extends CantHandle object CantOptimize extends CantHandle //object CantHandleLiteral extends Exception - +*/ var nPatterns = 0 var nParallel = 0 @@ -121,6 +122,7 @@ trait PatternMatchers { self: transform.ExplicitOuter with PatternNodes with Par var dfatree: Tree = null /** enters a sequence of cases into the pattern matcher */ +/* def construct(cases: List[Tree]): Unit = { nPatterns = nPatterns + 1 @@ -171,7 +173,7 @@ trait PatternMatchers { self: transform.ExplicitOuter with PatternNodes with Par constructIncremental(cases) } - +*/ def constructParallel(cases: List[Tree]): Any = { //var cases1 = cases; while(cases1 ne Nil) { // val c = cases1.head.asInstanceOf[CaseDef] @@ -216,7 +218,7 @@ trait PatternMatchers { self: transform.ExplicitOuter with PatternNodes with Par // return e // fallback //non-fallback: - case e: CantHandle => rep.cleanup(); return e + //case e: CantHandle => rep.cleanup(); return e case e => e.printStackTrace(); throw new FatalError(e.getMessage()) } } diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala index 29c156a537..8d099455a6 100644 --- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala +++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala @@ -240,7 +240,7 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with CodeFa } else { val pm = new PatternMatcher() pm.initialize(sel, doCheckExhaustive, owner, handleOuter) - pm.construct(cases) + pm.constructParallel(cases) //if (global.log()) { // global.log("internal pattern matching structure"); // pm.print(); diff --git a/test/files/run/patmatnew.scala b/test/files/run/patmatnew.scala index a61e9eb797..dc8e21701a 100644 --- a/test/files/run/patmatnew.scala +++ b/test/files/run/patmatnew.scala @@ -29,9 +29,17 @@ object Test extends TestConsoleMain { SeqUnapply, applyFromJcl, new Test717, - new TestGuards, + TestGuards, TestEqualsPatternOpt, - new TestStream, + TestSequence01, + TestSequence02, + TestSequence03, + TestSequence04, + TestSequence05, + TestSequence06, + TestSequence07, + TestSequence08, + TestStream, new Test903, new Test1163_Order, new TestUnbox, @@ -126,7 +134,7 @@ object Test extends TestConsoleMain { } } - class TestGuards extends TestCase("multiple guards for same pattern") with Shmeez { + object TestGuards extends TestCase("multiple guards for same pattern") with Shmeez { val tree:Tree = Beez(2) override def runTest = { val res = tree match { @@ -153,7 +161,148 @@ object Test extends TestConsoleMain { } } - class TestStream extends TestCase("unapply for Streams") { + object TestSequence01 extends TestCase("uno (all ignoring patterns on List)") { + def doMatch(xs: List[String]): String = xs match { + case List(_*) => "ok" + } + override def runTest() { + val list1 = List() + assertEquals(doMatch(list1), "ok") + val list2 = List("1","2","3") + assertEquals(doMatch(list2), "ok") + } + } + + + object TestSequence02 extends TestCase("due (all ignoring patterns on Seq)") { + def doMatch(l: Seq[String]): String = l match { + case Seq(_*) => "ok" + } + override def runTest() { + val list1 = List() + assertEquals(doMatch(list1), "ok") + val list2 = List("1", "2", "3") + assertEquals(doMatch(list2), "ok") + val array3 = Array[String]() + assertEquals(doMatch(array3), "ok") + val array4 = Array[String]("ga", "gu") + assertEquals(doMatch(array4), "ok") + } + } + + object TestSequence03 extends TestCase("tre (right-ignoring patterns on List, defaults)") { + def doMatch(xs: List[String]): String = xs match { + case List(_,_,_,_*) => "ok" + case _ => "not ok" + } + override def runTest() { + val list1 = List() + assertEquals(doMatch(list1), "not ok") + val list2 = List("1","2","3") + assertEquals(doMatch(list2), "ok") + val list3 = List("1","2","3","4") + assertEquals(doMatch(list3), "ok") + } + } + + + object TestSequence04 extends TestCase("quattro (all- and right-ignoring pattern on case class w/ seq param)") { + case class Foo(i: Int, chars: Char*) + + override def runTest() = { + val a = Foo(0, 'a') match { + case Foo(i, c, chars @ _*) => c + case _ => null + } + assertEquals(a, 'a') + + val b = Foo(0, 'a') match { + case Foo(i, chars @ _*) => 'b' + case _ => null + } + assertEquals(b, 'b') + } + } + + object TestSequence05 extends TestCase("cinque (sealed case class with ignoring seq patterns)") { + sealed abstract class Con; + + case class Foo() extends Con + case class Bar(xs:Con*) extends Con + + override def runTest() { + val res = (Bar(Foo()):Con) match { + case Bar(xs@_*) => xs // this should be optimized away to a pattern Bar(xs) + case _ => Nil + } + assertEquals("res instance"+res.isInstanceOf[Seq[Con] forSome { type Con }]+" res(0)="+res(0), true, res.isInstanceOf[Seq[Foo] forSome { type Foo}] && res(0) == Foo() ) + } + } + + object TestSequence06 extends TestCase("sei (not regular) fancy guards / bug#644 ") { + + case class A(i: Any) + + def doMatch(x: Any, bla: int) = x match { + case x:A if (bla==1) => 0 + case A(1) => 1 + case A(A(1)) => 2 + } + + override def runTest() { + assertEquals(doMatch(A(null),1), 0) + assertEquals(doMatch(A(1),2), 1) + assertEquals(doMatch(A(A(1)),2), 2) + } + + } + + object TestSequence07 extends TestCase("sette List of chars") { + def doMatch1(xs: List[char]) = xs match { + case List(x, y, _*) => x::y::Nil + } + def doMatch2(xs:List[char]) = xs match { + case List(x, y, z, w) => List(z,w) + } + //def doMatch3(xs:List[char]) = xs match { + // case List(_*, z, w) => w::Nil + //} + def doMatch4(xs:Seq[Char]) = xs match { + case Seq(x, y, _*) => x::y::Nil + case Seq(x, y, z, w) => List(z,w) // redundant! + } + def doMatch5(xs:Seq[Char]) = xs match { + case Seq(x, y, 'c', w @ _*) => x::y::Nil + case Seq(x, y, z @ _*) => z + } + def doMatch6(xs:Seq[Char]) = xs match { + case Seq(x, 'b') => x::'b'::Nil + case Seq(x, y, z @ _*) => z.toList + } + + override def runTest() { + assertEquals(List('a','b'), doMatch1(List('a','b','c','d'))) + assertEquals(List('c','d'), doMatch2(List('a','b','c','d'))) + //assertEquals(doMatch3(List('a','b','c','d')), List('d')) + assertEquals(List('a','b'), doMatch4(List('a','b','c','d'))) + assertEquals(List('a','b'), doMatch5(List('a','b','c','d'))) + assertEquals(List('c','d'), doMatch6(List('a','b','c','d'))) + } + } + + object TestSequence08 extends TestCase("backquoted identifiers in pattern") { + override def runTest() { + val xs = List(2, 3) + val ys = List(1, 2, 3) match { + case x :: `xs` => xs + case _ => Nil + } + assertEquals(xs, ys) + } + } + + + object TestStream extends TestCase("unapply for Streams") { def sum(stream: Stream[int]): int = stream match { case Stream.empty => 0 diff --git a/test/files/run/regularpatmatnew.check b/test/files/run/regularpatmatnew.check deleted file mode 100644 index e69de29bb2..0000000000 diff --git a/test/files/run/regularpatmatnew.scala b/test/files/run/regularpatmatnew.scala deleted file mode 100644 index c610b80444..0000000000 --- a/test/files/run/regularpatmatnew.scala +++ /dev/null @@ -1,158 +0,0 @@ -object Test { - import scala.testing.SUnit._ - - def main(args: Array[String]) { - val tr = new TestResult - new TestSuite( - - new Test01, - new Test02, - new Test03, - new Test04, - new Test05, - new Test06, - new Test07, - new Test08 - - ).run(tr) - - for (val f <- tr.failures()) println(f) - } - - class Test01 extends TestCase("uno (all ignoring patterns on List)") { - def doMatch(xs: List[String]): String = xs match { - case List(_*) => "ok" - } - override def runTest() { - val list1 = List() - assertEquals(doMatch(list1), "ok") - val list2 = List("1","2","3") - assertEquals(doMatch(list2), "ok") - } - } - - /* these are not allowed, for strange reasons I will never figure out - - def doMatch(l:Seq[String]):String = l match { - case List(_*) => "ok" - case _ => "not ok" - } - - def doMatch(l:Seq[String]):String = l match { - case Array(_*) => "ok" - case _ => "not ok" - } - */ - - class Test02 extends TestCase("due (all ignoring patterns on Seq)") { - def doMatch(l: Seq[String]): String = l match { - case Seq(_*) => "ok" - } - override def runTest() { - val list1 = List() - assertEquals(doMatch(list1), "ok") - val list2 = List("1", "2", "3") - assertEquals(doMatch(list2), "ok") - val array3 = Array[String]() - assertEquals(doMatch(array3), "ok") - val array4 = Array[String]("ga", "gu") - assertEquals(doMatch(array4), "ok") - } - } - - class Test03 extends TestCase("tre (right-ignoring patterns on List, defaults)") { - def doMatch(xs: List[String]): String = xs match { - case List(_,_,_,_*) => "ok" - case _ => "not ok" - } - override def runTest() { - val list1 = List() - assertEquals(doMatch(list1), "not ok") - val list2 = List("1","2","3") - assertEquals(doMatch(list2), "ok") - val list3 = List("1","2","3","4") - assertEquals(doMatch(list3), "ok") - } - } - - - class Test04 extends TestCase("quattro (all- and right-ignoring pattern on case class w/ seq param)") { - case class Foo(i: Int, chars: Char*) - - override def runTest() = { - val a = Foo(0, 'a') match { - case Foo(i, c, chars @ _*) => c - case _ => null - } - assertEquals(a, 'a') - - val b = Foo(0, 'a') match { - case Foo(i, chars @ _*) => 'b' - case _ => null - } - assertEquals(b, 'b') - } - } - - class Test05 extends TestCase("cinque (sealed case class with ignoring seq patterns)") { - sealed abstract class Con; - - case class Foo() extends Con - case class Bar(xs:Con*) extends Con - - override def runTest() { - val res = (Bar(Foo()):Con) match { - case Bar(xs@_*) => xs // this should be optimized away to a pattern Bar(xs) - case _ => Nil - } - assertEquals("res instance"+res.isInstanceOf[Seq[Con] forSome { type Con }]+" res(0)="+res(0), true, res.isInstanceOf[Seq[Foo] forSome { type Foo}] && res(0) == Foo() ) - } - } - - class Test06 extends TestCase("sei (not regular) fancy guards / bug#644 ") { - - case class A(i: Any) - - def doMatch(x: Any, bla: int) = x match { - case x:A if (bla==1) => 0 - case A(1) => 1 - case A(A(1)) => 2 - } - - override def runTest() { - assertEquals(doMatch(A(null),1), 0) - assertEquals(doMatch(A(1),2), 1) - assertEquals(doMatch(A(A(1)),2), 2) - } - - } - - class Test07 extends TestCase("sette List of chars") { - def doMatch1(xs: List[char]) = xs match { - case List(x, y, _*) => x::y::Nil - } - def doMatch2(xs:List[char]) = xs match { - case List(x, y, z, w) => List(z,w) - } - //def doMatch3(xs:List[char]) = xs match { - // case List(_*, z, w) => w::Nil - //} - override def runTest() { - assertEquals(doMatch1(List('a','b','c','d')), List('a','b')) - assertEquals(doMatch2(List('a','b','c','d')), List('c','d')) - //assertEquals(doMatch3(List('a','b','c','d')), List('d')) - } - } - - class Test08 extends TestCase("backquoted identifiers in pattern") { - override def runTest() { - val xs = List(2, 3) - val ys = List(1, 2, 3) match { - case x :: `xs` => xs - case _ => Nil - } - assertEquals(xs, ys) - } - } - -} -- cgit v1.2.3