diff options
10 files changed, 209 insertions, 82 deletions
diff --git a/config/list/scalac.lst b/config/list/scalac.lst index e44d00b002..a79a2fc7d9 100644 --- a/config/list/scalac.lst +++ b/config/list/scalac.lst @@ -189,9 +189,10 @@ transformer/TransMatch.scala transformer/TransMatchPhase.scala transformer/UnCurry.scala transformer/UnCurryPhase.scala -#transformer/matching/FullRegularTranslator.scala -#transformer/matching/GrammarTool.scala +transformer/matching/FullRegularTranslator.scala +transformer/matching/GrammarTool.scala transformer/matching/MutableGrammar.scala +transformer/matching/NonTermFactory.scala transformer/matching/PatternExp.scala transformer/matching/PatternTest.scala #transformer/matching/PatternInfo.scala diff --git a/sources/scala/runtime/matching/NonTerm.scala b/sources/scala/runtime/matching/NonTerm.scala index 7d03e52b9c..44831d3dd8 100644 --- a/sources/scala/runtime/matching/NonTerm.scala +++ b/sources/scala/runtime/matching/NonTerm.scala @@ -50,39 +50,3 @@ object EMPTYHEDGE extends HedgeNT( 0, true ) ; object ANYHEDGE extends HedgeNT( 1, true ) ; object ANYTREE extends TreeNT( 1 ); -/** factory for nonterminals. maintains list of initial nonterminals - */ -class NonTermFactory { - - var treeInitials:immutable.Set[TreeNT] = new immutable.TreeSet[TreeNT](); - var hedgeInitials:immutable.Set[HedgeNT] = new immutable.TreeSet[HedgeNT](); - - private var treeCounter = 2; - private var hedgCounter = 2; - - def HedgeNT: HedgeNT = { - val x = new HedgeNT( hedgCounter ); - hedgCounter = hedgCounter + 1; - x - } - - def TreeNT( vs:immutable.Set[Int] ): TreeNT = { - val x = new TreeNT( treeCounter ); - x.vset = vs; - treeCounter = treeCounter + 1; - x - } - - def initialHedgeNT = { - val h = HedgeNT; - hedgeInitials = hedgeInitials + h; - h - } - - def initialTreeNT = { - val t = TreeNT( immutable.ListSet.Empty[Int] ); - treeInitials = treeInitials + t; - t - } - -} diff --git a/sources/scala/runtime/matching/PatternGrammar.scala b/sources/scala/runtime/matching/PatternGrammar.scala index 3541e212c4..07bdf8633e 100644 --- a/sources/scala/runtime/matching/PatternGrammar.scala +++ b/sources/scala/runtime/matching/PatternGrammar.scala @@ -15,4 +15,5 @@ abstract class PatternGrammar extends scala.util.grammar.ImmutableTreeHedgeGramm def test(test:Int, inp:Any): Boolean; def isSequenceType: Boolean = { treeInitials.toSet(true).isEmpty }; + } diff --git a/sources/scala/tools/scalac/transformer/TransMatch.scala b/sources/scala/tools/scalac/transformer/TransMatch.scala index 9775c0b659..ae76507081 100644 --- a/sources/scala/tools/scalac/transformer/TransMatch.scala +++ b/sources/scala/tools/scalac/transformer/TransMatch.scala @@ -29,8 +29,8 @@ import scalac.transformer.matching.AlgebraicMatcher ; package scala.tools.scalac.transformer { -//import matching.FullRegularTranslator ; -//import matching.GrammarTool ; //DEBUG +import matching.FullRegularTranslator ; +import matching.GrammarTool ; //DEBUG class TransMatch( global:scalac_Global ) extends scalac_transformer_OwnerTransformer( global ) { @@ -95,20 +95,20 @@ class TransMatch( global:scalac_Global ) //val bsf = new scala.util.automaton.BerrySethi[ matching.PatternTest ]( pe ); def transform( root:Tree, cases:Array[Tree$CaseDef], restpe:Type ):Tree = { - /* + if( global.newMatch ) { val fm = new FullRegularTranslator( global ); val gram = fm.MakeGrammar( scala.Iterator.fromArray( cases ) ); Console.println("writing out the grammar to /tmp/encodedGrammar.bin"); - val f = new FileOutputStream(new File("/tmp/encodedGrammar.bin")); - f.write( gram.encode ); - f.close(); + //val f = new FileOutputStream(new File("/tmp/encodedGrammar.bin")); + //f.write( gram.encode ); + //f.close(); // val gram = Predef.decode( Predef.Array[] ); - Console.println( GrammarTool.toString( gram )); + Console.println( GrammarTool.encode( gram )); throw new ApplicationError("not impl."); }; - */ + var containsReg = false; var i = 0; while (i < cases.length) { diff --git a/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala b/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala index e30b7baa7f..e5ce6b867d 100644 --- a/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala +++ b/sources/scala/tools/scalac/transformer/matching/FullRegularTranslator.scala @@ -77,18 +77,20 @@ class FullRegularTranslator(global: scalac_Global) { /** * precondition: p.length > 0 */ - def MakeGrammar( it:Iterator[Tree$CaseDef] ):Grammar = { + def MakeGrammar( it:Iterator[Tree$CaseDef] ):PatternGrammar = { + DEBUGPRINT("MakeGrammar"); var k = 0; cur = InitialGrammar.make; while( it.hasNext ) translate( pe.fromTree(it.next.pat), { k = k + 1; k } ); + DEBUGPRINT(cur.toString()); cur.toGrammar; } /** p must be a pattern */ protected def translate( p:RegExp, k:Int ):unit = { - + DEBUGPRINT("translate"); this.varCounter = 0; this.isSequenceType = isSequenceValued( p ); if( this.isSequenceType ) { @@ -105,13 +107,13 @@ class FullRegularTranslator(global: scalac_Global) { if( global.debug ) { for( val rule <- cur.treeRules ) { - global.log( rule.toString() ); + DEBUGPRINT( rule.toString() ); } for( val rule <- cur.hedgeRules ) { - global.log( rule.toString() ); + DEBUGPRINT( rule.toString() ); } - global.log("=== Now Removing Chain Rules ==="); - } ; + DEBUGPRINT("=== Now Removing Chain Rules ==="); + }; RemoveChainRules; @@ -252,6 +254,9 @@ Afterwards: Chain rules need not be applied anymore. They only exist with */ def MakeHedgeRule( in:HedgeNT, nt:HedgeNT, vset:immutable.Set[Int], pat:RegExp):unit = pat match { + + case Eps => + cur.hedgeRules += new HedgeChainRule( in, nt ); /* case Point() => cur.hedgeRules += new HedgeChainRule(in, iteration); @@ -301,8 +306,11 @@ Afterwards: Chain rules need not be applied anymore. They only exist with if (isSequenceValued( p )) { MakeHedgeRule( in, nt, vset + newVar( vble ), p ); } else { + Console.println(p); + Console.println(isSequenceValued( p )); try { val trNT = cur.make.TreeNT( vset ); + Console.println("made treeNT:"+trNT); MakeTreeRule( trNT, vset, pat ); cur.hedgeRules += new HedgeRule( in, trNT, nt ); } catch { @@ -311,8 +319,11 @@ Afterwards: Chain rules need not be applied anymore. They only exist with } } case _ => + Console.println(pat); + Console.println(isSequenceValued( pat )); try { val trNT = cur.make.TreeNT( vset ); + Console.println("made treeNT:"+trNT); MakeTreeRule( trNT, vset, pat ); cur.hedgeRules += new HedgeRule( in, trNT, nt ); } catch { @@ -329,9 +340,10 @@ Afterwards: Chain rules need not be applied anymore. They only exist with case Wildcard => // WildcardTree() // case Tree$Ident( Names.PATTERN_WILDCARD ) => - if( vset.isEmpty ) + if( vset.isEmpty ) { + DEBUGPRINT("WILDCARD! discarding "+in); throw new WildcardException(); // OPTIMIZATION to collapse _ rules - else + } else cur.treeRules += new AnyTreeRule( in ); // WildcardNode( x @ _* ) case Node(WildcardTest, sequ) => diff --git a/sources/scala/tools/scalac/transformer/matching/GrammarTool.scala b/sources/scala/tools/scalac/transformer/matching/GrammarTool.scala index b32004644e..3ecdc398fe 100644 --- a/sources/scala/tools/scalac/transformer/matching/GrammarTool.scala +++ b/sources/scala/tools/scalac/transformer/matching/GrammarTool.scala @@ -1,12 +1,60 @@ package scala.tools.scalac.transformer.matching ; -import scala.runtime.matching.Grammar ; +import scala.runtime.matching.PatternGrammar; //Grammar ; //import scalac.ast.{ Tree, TreeGen }; //import scalac.util.Name; object GrammarTool { + def encode(gram: PatternGrammar): String = { + val sb = new StringBuffer(); + def writeInt(i: Int) = { + sb.append(i); + sb.append('#'); + } + def writeIntArray(arr:Array[Int]) = { + sb.append(arr.length); + sb.append('#'); + var i = 0; + while(i < arr.length) { + sb.append(arr(i)); + sb.append('#'); + } + } + + writeInt( gram.nTreeNT ); // nTreeNT + writeInt( gram.nHedgeNT ); // nHedgeNT + writeIntArray(gram.treeInitials.toArray); // treeInitials + writeIntArray(gram.hedgeInitials.toArray); // hedgeInitials + writeIntArray(gram.isNullable.toArray); // isNullable + // treeTransitions + sb.append(gram.treeTransitions.length); + sb.append('#'); + var i = 0; + while(i < gram.treeTransitions.length) { + val set = gram.treeTransitions(i).elements; + while( set.hasNext ) { + sb.append(','); + sb.append(set.next); + } + sb.append('#'); + } + // hedgeTransitions + sb.append(gram.hedgeTransitions.length); + sb.append('#'); + i = 0; + while(i < gram.hedgeTransitions.length) { + val set = gram.hedgeTransitions(i).elements; + while( set.hasNext ) { + sb.append(','); + sb.append(set.next); + } + sb.append('#'); + } + sb.toString(); + } +/* def toString(gram: Grammar) = { "new Grammar("+gram.treeTransitions+",\n"+gram.hedgeTransitions+",\n"+{ var k = 1; @@ -18,7 +66,7 @@ object GrammarTool { sb.toString() }+")\n"; } - +*/ /* private val _Grammar = Name.fromString("Grammar"); private val _runtime = Name.fromString("runtime"); diff --git a/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala b/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala index 7f8b75e122..5829c2410d 100644 --- a/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala +++ b/sources/scala/tools/scalac/transformer/matching/MutableGrammar.scala @@ -23,7 +23,7 @@ object InitialGrammar { initialHedgeRules, vars, tests, - new NonTermFactory + new NonTermFactory( ANYTREE.i+1, ANYHEDGE.i+1 ) ); z.varMap = new mutable.HashMap[Symbol, Int](); z.invTest = new mutable.HashMap[PatternTest, Int](); @@ -89,42 +89,93 @@ case class MutableGrammar( treeRules:mutable.Set[TRule], */ def toGrammar: PatternGrammar = { val rbsNullable = new mutable.BitSet(); + var tnt = 0; + var renumber = new immutable.TreeMap[Int,Int]; + var invnum = new immutable.TreeMap[Int,Int]; val _treeTransitions:Array[immutable.Set[TreeRHS]] = { val theTreeTransitionsMap: immutable.TreeMap[Int,immutable.Set[TreeRHS]] = { - var tmp = - immutable.TreeMap.Empty[Int,immutable.Set[TreeRHS]]; - treeRules.foreach { treeRule => treeRule match { - case AnyTreeRule( t ) => tmp = add( t.i, AnyTreeRHS, tmp ); - //case AnyNodeRule( t, _ ) => tmp = add( t.i, treeRule, tmp ) // ??!!!!!!!!!!!!!!!!!!!!!! - case TreeRule( t, i, h ) => tmp = add( t.i, LabelledRHS(TestLabel(i),h.i), tmp ) - }}; + var tmp = immutable.TreeMap.Empty[Int,immutable.Set[TreeRHS]]; + val it = treeRules.elements; + while(it.hasNext) { + val tr = it.next; + //Console.print(tr.toString()+" ###"); + tr match { + case AnyTreeRule( t ) => + tmp = add( tnt, AnyTreeRHS, tmp ); + //Console.println(tnt); + //Console.println(tmp); + renumber = renumber.update(t.i, tnt); + invnum = invnum.update(tnt, t.i); + tnt = tnt+1; + case AnyNodeRule( t, _ ) => + Console.println("?!?! "+t); + // ?! + throw new RuntimeException("cannot handle!"); + case TreeRule( t, i, h ) => + tmp = add( tnt, LabelledRHS(TestLabel(i),h.i), tmp ); + + //Console.println(tnt); + //Console.println(tmp); + renumber = renumber.update(t.i, tnt); + invnum = invnum.update(tnt, t.i); + tnt = tnt+1; + } + } tmp }; + //Console.println("map size"+theTreeTransitionsMap.size); + //Console.println("mumap size"+treeRules.size); val arr = new Array[immutable.Set[TreeRHS]]( theTreeTransitionsMap.size ); val it = theTreeTransitionsMap.keys; while( it.hasNext ) { val k = it.next; + //Console.println(k+" which is t"+invnum(k)); arr.update( k, theTreeTransitionsMap( k )); } arr } + //Console.println("renumer T "+renumber); + //Console.println("DONE with trees"); val _nTreeNT = _treeTransitions.length; - + var renumberH = new immutable.TreeMap[Int,Int].update(0,0); + val it = hedgeRules.elements; + var hnt = 1; + while(it.hasNext) + it.next match { + case HedgeRule( h, t, h2 ) => + if(!renumberH.contains(h.i)) { + renumberH = renumberH.update(h.i,hnt); + hnt = hnt + 1; + } + if(!renumberH.contains(h2.i)) { + renumberH = renumberH.update(h2.i,hnt); + hnt = hnt + 1; + } + } + //Console.println("hedge renum"); + //Console.println(renumberH); val _hedgeTransitions: Array[immutable.Set[HedgeRHS]] = { val theHedgeTransitionsMap: immutable.TreeMap[Int,immutable.Set[HedgeRHS]] = { var tmp = - immutable.TreeMap.Empty[Int,immutable.Set[HedgeRHS]]; - hedgeRules.foreach { hedgeRule => hedgeRule match { + immutable.TreeMap.Empty[Int,immutable.Set[HedgeRHS]] + // to maintain assumption that every hedge nt is present + .update(0, immutable.ListSet.Empty[HedgeRHS]); + + val it2 = hedgeRules.elements; + while(it2.hasNext) { + val hedgeRule = it2.next; + hedgeRule match { case HedgeRule( h, t, h2 ) => - rbsNullable.ensureSize( h2.i ); - rbsNullable.set( h2.i, h2.nullable ); - tmp = add( h.i, ConsRHS(t.i,h2.i), tmp ); - case HedgeChainRule( h, _ ) => throw new RuntimeException(); - //tmp = add( h.i, hedgeRule, tmp ); + //Console.println(hedgeRule); + //Console.println("h"+h.i+" ===> "+renumberH(h.i)); + rbsNullable.ensureSize( renumberH(h2.i) ); + rbsNullable.set( renumberH(h2.i), h2.nullable ); + tmp = add( renumberH(h.i), ConsRHS(renumber(t.i),renumberH(h2.i)), tmp ); + Console.println("tmp = "+tmp); }}; - // to maintain assumption that every hedge nt is present - tmp.update( 0, immutable.ListSet.Empty[HedgeRHS] ); + tmp }; + Console.println("hello, "+theHedgeTransitionsMap); val arr = new Array[immutable.Set[HedgeRHS]]( theHedgeTransitionsMap.size ); val it = theHedgeTransitionsMap.keys; while( it.hasNext ) { @@ -133,13 +184,16 @@ case class MutableGrammar( treeRules:mutable.Set[TRule], } arr } + //Console.println("DONE with hedges"); val _nHedgeNT = _hedgeTransitions.length ; + Console.println("caseVars: "+caseVars); val _vars = new Array[Int]( caseVars.size ); - val it = caseVars.keys; - while( it.hasNext ) { - val k = it.next; - _vars.update( k, caseVars( k )); + val it3 = caseVars.keys; + while( it3.hasNext ) { + val k = it3.next; + Console.println("caseVar: "+k); + _vars.update( k-1, caseVars( k )); } val _treeInitials = { diff --git a/sources/scala/tools/scalac/transformer/matching/NonTermFactory.scala b/sources/scala/tools/scalac/transformer/matching/NonTermFactory.scala new file mode 100644 index 0000000000..50197b162e --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/NonTermFactory.scala @@ -0,0 +1,41 @@ +package scala.tools.scalac.transformer.matching; + +import scala.runtime.matching.{TreeNT, HedgeNT}; +import scala.collection.immutable; + +/** factory for nonterminals. maintains list of initial nonterminals + */ +class NonTermFactory(treeInit: Int, hedgeInit: Int) { + + var treeInitials:immutable.Set[TreeNT] = new immutable.TreeSet[TreeNT](); + var hedgeInitials:immutable.Set[HedgeNT] = new immutable.TreeSet[HedgeNT](); + + private var treeCounter = treeInit; + private var hedgCounter = hedgeInit; + + def HedgeNT: HedgeNT = { + val x = new HedgeNT( hedgCounter ); + hedgCounter = hedgCounter + 1; + x + } + + def TreeNT( vs:immutable.Set[Int] ): TreeNT = { + val x = new TreeNT( treeCounter ); + x.vset = vs; + treeCounter = treeCounter + 1; + x + } + + def initialHedgeNT = { + val h = HedgeNT; + hedgeInitials = hedgeInitials + h; + h + } + + def initialTreeNT = { + val t = TreeNT( immutable.ListSet.Empty[Int] ); + treeInitials = treeInitials + t; + t + } + +} diff --git a/sources/scala/tools/scalac/transformer/matching/PatternExp.scala b/sources/scala/tools/scalac/transformer/matching/PatternExp.scala index 1862bca49b..d05413b799 100644 --- a/sources/scala/tools/scalac/transformer/matching/PatternExp.scala +++ b/sources/scala/tools/scalac/transformer/matching/PatternExp.scala @@ -28,17 +28,17 @@ package scala.tools.scalac.transformer.matching { Alt( fromTrees(choices):_* ) case Apply(s:Ident, args) if (s.symbol() == defs.PATTERN_WILDCARD) => - Node(WildcardTest, Sequ(fromTrees( args ):_*)) + Node(WildcardTest, mkSequ(fromTrees( args ):_*)) case x @ Apply(_, args) => if (isSeqApply( x )) // List(1,2,3) - Node(TypeTest( x.getType() ), Sequ(fromTrees( args ):_*)) + Node(TypeTest( x.getType() ), mkSequ(fromTrees( args ):_*)) else if (isObjectRef( x )) // uncurry: foo.bar => foo.bar() Node(EqualsValue( t ), Eps); else // case class constructor - Node(Constructor( t.getType() ), Sequ(fromTrees( args ):_*)); + Node(Constructor( t.getType() ), mkSequ(fromTrees( args ):_*)); case Bind(n: Name, t:Tree) => if( TreeInfo.isNameOfStarPattern( n ) ) @@ -60,7 +60,7 @@ package scala.tools.scalac.transformer.matching { Node(EqualsValue( t ), Star(Wildcard)) case Sequence( trees ) => - Sequ(fromTrees( trees ):_*); + mkSequ(fromTrees( trees ):_*); case Typed(_,_) => Node(TypeTest( t.getType() ), Eps) diff --git a/sources/scala/util/regexp/Base.scala b/sources/scala/util/regexp/Base.scala index 376130759e..58d80927f6 100644 --- a/sources/scala/util/regexp/Base.scala +++ b/sources/scala/util/regexp/Base.scala @@ -52,4 +52,10 @@ trait Base { def r = r1; } + final def mkSequ(rs: regexp*): RegExp = + if(!rs.elements.hasNext) + Eps + else + Sequ(rs:_*); + } |