diff options
11 files changed, 238 insertions, 127 deletions
diff --git a/config/list/library.lst b/config/list/library.lst index c9f5e625f7..169271cc04 100644 --- a/config/list/library.lst +++ b/config/list/library.lst @@ -64,6 +64,7 @@ collection/Map.scala collection/MapProxy.scala collection/Set.scala collection/SetProxy.scala +collection/BitSet.scala collection/mutable/ArrayBuffer.scala collection/mutable/Buffer.scala @@ -146,21 +147,30 @@ runtime/RunTime.java runtime/ScalaRunTime.scala runtime/matching/Address.scala -runtime/matching/Context.scala -runtime/matching/Grammar.scala -runtime/matching/Match.scala -runtime/matching/Matcher.scala -runtime/matching/NonTerm.scala -runtime/matching/Pebble.scala -runtime/matching/Rule.scala +#runtime/matching/Context.scala +#runtime/matching/Grammar.scala +#runtime/matching/Match.scala +#runtime/matching/Matcher.scala +#runtime/matching/NonTerm.scala +runtime/matching/PatternGrammar.scala +#runtime/matching/Pebble.scala +#runtime/matching/Rule.scala testing/UnitTest.scala util/alphabet/Alphabet.scala +util/alphabet/AlphabetPlusWildcard.scala +util/alphabet/IntAlphabet.scala +util/alphabet/WildcardLabel.scala +#util/automata/NondetTreeHedgeAutom.scala util/automata/NondetWordAutom.scala util/automata/BaseBerrySethi.scala util/automata/WordBerrySethi.scala +util/grammar/TreeHedgeGrammar.scala +util/grammar/ImmutableTreeHedgeGrammar.scala +util/grammar/MutableTreeHedgeGrammar.scala util/regexp/Base.scala +util/regexp/WildcardBase.scala util/regexp/WordExp.scala util/regexp/PointedHedgeExp.scala util/regexp/SyntaxError.scala diff --git a/config/list/scalac.lst b/config/list/scalac.lst index daebc89131..71c7cfaba8 100644 --- a/config/list/scalac.lst +++ b/config/list/scalac.lst @@ -25,12 +25,12 @@ transformer/TransMatch.scala transformer/TransMatchPhase.scala transformer/UnCurry.scala transformer/UnCurryPhase.scala -transformer/matching/FullRegularTranslator.scala -transformer/matching/GrammarPrinter.scala -transformer/matching/MutableGrammar.scala +#transformer/matching/FullRegularTranslator.scala +#transformer/matching/GrammarTool.scala +#transformer/matching/MutableGrammar.scala transformer/matching/PatternExp.scala transformer/matching/PatternTest.scala -transformer/matching/PatternInfo.scala +#transformer/matching/PatternInfo.scala typechecker/Analyzer.scala typechecker/AnalyzerPhase.scala diff --git a/sources/scala/collection/BitSet.scala b/sources/scala/collection/BitSet.scala new file mode 100644 index 0000000000..7612335e6d --- /dev/null +++ b/sources/scala/collection/BitSet.scala @@ -0,0 +1,34 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2004, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection ; + +/** An immutable bitset view on a byte array. Instances can conveniently be + * created from instances of mutable.ResizableBitSet + * n: number of relevant bits + * ba: array of bytes of length n>>>3 + * copy: if yes, then ba is copied and updates will not affect this bitset + * @author Burak Emir + */ +abstract class BitSet with Function1[Int,Boolean] { + + /** number of bits in this bitset */ + def size: Int; + + /** returns true if bit i is set */ + def apply(i: Int):Boolean; + + /** returns an iterator over the truth values of all bits */ + final def booleanElements:Iterator[Boolean] = new Iterator[Boolean] { + var i = 0; + def hasNext: Boolean = i < size; + def next: Boolean = { i = i + 1; apply(i-1) } + } + +} diff --git a/sources/scala/collection/immutable/BitSet.scala b/sources/scala/collection/immutable/BitSet.scala new file mode 100644 index 0000000000..3bc0cb3c8e --- /dev/null +++ b/sources/scala/collection/immutable/BitSet.scala @@ -0,0 +1,40 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2004, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection.immutable ; + +/** An immutable bitset view on a byte array. Instances can conveniently be + * created from instances of mutable.ResizableBitSet + * n: number of relevant bits + * ba: array of bytes of length n>>>3 + * copy: if yes, then ba is copied and updates will not affect this bitset + * @author Burak Emir + */ +class BitSet(n:Int, ba: Array[Byte], copy:Boolean) extends scala.collection.BitSet { + + val size = n; + val array:Array[Byte] = + if( copy ) { + val arr = new Array[Byte](ba.length); + java.lang.System.arraycopy( ba, 0, arr, 0, ba.length ); + arr + } else ba; + + def this(rbs: scala.collection.mutable.ResizableBitSet) = { + this(rbs.size, rbs.toByteArray, false); + } + + /** returns true if bit i is set */ + def apply(i: Int):Boolean = { + val j = (i >>> 3); + val mask = (1 << (i & 0x07)); + (array(j) & mask) != 0; + } + +} diff --git a/sources/scala/collection/mutable/ResizableBitSet.scala b/sources/scala/collection/mutable/ResizableBitSet.scala index dee4de2505..a8379bd6c6 100644 --- a/sources/scala/collection/mutable/ResizableBitSet.scala +++ b/sources/scala/collection/mutable/ResizableBitSet.scala @@ -13,7 +13,7 @@ package scala.collection.mutable ; * @author Burak Emir * @param initSize: initial size in nbits */ -class ResizableBitSet(initSize: Int) with Iterable[Boolean] { +class ResizableBitSet(initSize: Int) extends scala.collection.BitSet { /** default constructor, initial size of 16 bits */ def this() = this( 16 ); @@ -34,12 +34,18 @@ class ResizableBitSet(initSize: Int) with Iterable[Boolean] { def get(j:Int, mask:Int):Boolean = { (array(j) & mask) != 0; } + + def freeze: Array[Byte] = { + val arr = new Array[Byte]( array.length ); + java.lang.System.arraycopy(array, 0, arr, 0, arr.length); + arr + } } protected val internal = new ByteArray(); /** size of this bitset in nbytes */ - protected var size: Int = 0; + var size: Int = 0; /** size of this bitset in nbits */ def ensureSize(nbits: Int): Unit = { @@ -47,21 +53,6 @@ class ResizableBitSet(initSize: Int) with Iterable[Boolean] { size = nbits; } - /** Returns the length of this resizable bitset in nbytes */ - def length: Int = size; - - /** Returns a new iterator over all elements of this resizable array. */ - def elements: Iterator[Boolean] = new Iterator[Boolean] { - var i = 0; - def hasNext: Boolean = i < length; - def next: Boolean = { - val j = i >>> 3; - val mask = (1 << (i & 0x07)); - i = i + 1; - internal.get(j,mask) - } - } - final def set(i: Int, b: Boolean): Unit = if( b ) set(i) else clear(i); final def set(i: Int): Unit = { @@ -76,9 +67,11 @@ class ResizableBitSet(initSize: Int) with Iterable[Boolean] { internal.and(j, ~mask); } - def get(i: Int):Boolean = { + def apply(i: Int):Boolean = { val j = (i >>> 3); val mask = (1 << (i & 0x07)); internal.get(j, mask); } + + def toByteArray: Array[Byte] = internal.freeze; } diff --git a/sources/scala/tools/scalac/transformer/TransMatch.scala b/sources/scala/tools/scalac/transformer/TransMatch.scala index c70faaeebc..9775c0b659 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.GrammarPrinter ; //DEBUG +//import matching.FullRegularTranslator ; +//import matching.GrammarTool ; //DEBUG class TransMatch( global:scalac_Global ) extends scalac_transformer_OwnerTransformer( global ) { @@ -92,23 +92,23 @@ class TransMatch( global:scalac_Global ) } - val pe = new matching.PatternExp( global.definitions ); //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( GrammarPrinter.toString( gram )); + 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 gram = Predef.decode( Predef.Array[] ); + Console.println( GrammarTool.toString( gram )); - for( val p <- cases ) { - val aPe = pe.fromTree( p.pat ) ; - Console.println( aPe ); - //val na = bsf.automatonFrom( aPe ) ; - //Console.println( na ); - } throw new ApplicationError("not impl."); }; + */ var containsReg = false; var i = 0; while (i < cases.length) { diff --git a/sources/scala/tools/scalac/transformer/matching/GrammarPrinter.scala b/sources/scala/tools/scalac/transformer/matching/GrammarPrinter.scala deleted file mode 100644 index 117f262590..0000000000 --- a/sources/scala/tools/scalac/transformer/matching/GrammarPrinter.scala +++ /dev/null @@ -1,17 +0,0 @@ -package scala.tools.scalac.transformer.matching ; - -import scala.runtime.matching.Grammar ; - -object GrammarPrinter { - def toString( gram:Grammar ) = { - "Grammar("+gram.treeTransitions+",\n"+gram.hedgeTransitions+",\n"+{ - var k = 1; - val sb = new java.lang.StringBuffer(); - for( val y <- Iterator.fromArray( gram.vars ) ) { - sb.append("case "+k+": max var ="+y); - k = k + 1; - } - sb.toString() - }+")\n"; - } -} diff --git a/sources/scala/tools/scalac/transformer/matching/GrammarTool.scala b/sources/scala/tools/scalac/transformer/matching/GrammarTool.scala new file mode 100644 index 0000000000..b32004644e --- /dev/null +++ b/sources/scala/tools/scalac/transformer/matching/GrammarTool.scala @@ -0,0 +1,57 @@ +package scala.tools.scalac.transformer.matching ; + +import scala.runtime.matching.Grammar ; + +//import scalac.ast.{ Tree, TreeGen }; +//import scalac.util.Name; + +object GrammarTool { + + def toString(gram: Grammar) = { + "new Grammar("+gram.treeTransitions+",\n"+gram.hedgeTransitions+",\n"+{ + var k = 1; + val sb = new java.lang.StringBuffer(); + for( val y <- Iterator.fromArray( gram.vars ) ) { + sb.append("case "+k+": max var ="+y); + k = k + 1; + } + sb.toString() + }+")\n"; + } + + /* + private val _Grammar = Name.fromString("Grammar"); + private val _runtime = Name.fromString("runtime"); + private val _matching = Name.fromString("matching"); + + // convenience methods + private def _scala(pos: int, name: Name) = + make.Select( pos, make.Ident( pos, Names.scala ), name); + + private def _scala_runtime(pos: int, name: Name) = + make.Select( pos, _scala( pos, _xml ), name ); + + private def _scala_runtime_matching( pos: int ) = { + make.Select( pos, _scala_xml( pos, _runtime ), name ); + + private def _scala_runtime_matching_Grammar( pos: int ) = + make.Select( pos, _scala_xml_matching( pos, _Grammar ), name ); + + + def toTree(gram: Grammar) = { + + gen.New( + gen.mkApplyTV( + gen.mkPrimaryConstructorGlobalRef( + pos, + defs.TUPLE_CLASS[2]), + new Type[] { left.getType(), right.getType() }, + new Tree[] { left, right } + ) + ); + + } + make.New(pos, init); + } + */ +} diff --git a/sources/scala/tools/scalac/transformer/matching/PatternExp.scala b/sources/scala/tools/scalac/transformer/matching/PatternExp.scala index a1d0bce8a4..1862bca49b 100644 --- a/sources/scala/tools/scalac/transformer/matching/PatternExp.scala +++ b/sources/scala/tools/scalac/transformer/matching/PatternExp.scala @@ -5,15 +5,13 @@ import scalac.util.Name ; package scala.tools.scalac.transformer.matching { - import scala.util.regexp.PointedHedgeExp; + import scala.util.regexp.{ PointedHedgeExp, WildcardBase }; - class PatternExp(defs: Definitions) extends PointedHedgeExp[PatternTest] { + class PatternExp(defs: Definitions) + extends PointedHedgeExp[PatternTest] with WildcardBase { type regexp = RegExp ; case class Binding(vble:Symbol, re:regexp) extends Meta( re ) ; - case object WildcardNode extends RegExp { - final val isNullable = false; - } def fromTrees( ts:Array[Tree] ):Seq[RegExp] = { var nts: List[RegExp] = Nil; @@ -26,14 +24,17 @@ package scala.tools.scalac.transformer.matching { def fromTree( t:Tree ):RegExp = { import Tree._ ; t match { - case Alternative(choices:Array[Tree] ) => + case Alternative(choices:Array[Tree]) => Alt( fromTrees(choices):_* ) + case Apply(s:Ident, args) if (s.symbol() == defs.PATTERN_WILDCARD) => + Node(WildcardTest, Sequ(fromTrees( args ):_*)) + case x @ Apply(_, args) => - if(isSeqApply( x )) // List(1,2,3) + if (isSeqApply( x )) // List(1,2,3) Node(TypeTest( x.getType() ), Sequ(fromTrees( args ):_*)) - else if( isObjectRef( x ) ) // uncurry: foo.bar => foo.bar() + else if (isObjectRef( x )) // uncurry: foo.bar => foo.bar() Node(EqualsValue( t ), Eps); else // case class constructor @@ -45,21 +46,25 @@ package scala.tools.scalac.transformer.matching { else Binding( t.symbol(), fromTree( t )) + case Literal( c ) => + Node(EqualsValue( t ), Star(Wildcard)) + case Ident( n:Name ) => if( t.symbol() == defs.PATTERN_WILDCARD ) - WildcardNode + Wildcard else if( TreeInfo.isNameOfStarPattern( n ) ) Eps; - else Node(EqualsValue( t ), Eps) + else Node(EqualsValue( t ), Star(Wildcard)) case Select(_,_) => - Node(EqualsValue( t ), Eps) + Node(EqualsValue( t ), Star(Wildcard)) case Sequence( trees ) => Sequ(fromTrees( trees ):_*); case Typed(_,_) => Node(TypeTest( t.getType() ), Eps) + } } @@ -77,5 +82,49 @@ package scala.tools.scalac.transformer.matching { && ( tree.args.length == 1 ) && tree.args(0).isInstanceOf[Tree.Sequence] } + + final def isSequenceValued( p:RegExp ):Boolean = p match { + case x:Alt => + val it = x.rs.elements; + while (it.hasNext) + if (isSequenceValued( it.next )) + return true; + return false; + case Binding(_,r) => isSequenceValued( r ) + case Eps => true; + case _:Node => false; + case _:Sequ => true; + case TopIter(l, r) => isSequenceValued( l )||isSequenceValued( r ); + case Point => false; + case Wildcard => false; + } + + /** returns width */ + private def getLowerBoundWidth( it:Iterator[RegExp] ):Int = { + if( !it.hasNext ) 0 else { + var wid = minimalWidth( it.next ); + for( val h <- it ) { + val hw = minimalWidth( h ); + if( hw < wid ) { + wid = hw + } + } + wid + } + } + + /** @todo translate this from ems pattern + */ + def minimalWidth( pat:RegExp ):Int = pat match { + case x:Alt => getLowerBoundWidth( x.rs.elements ); + case _:Node => 1 + case x:Sequ => + x.rs.elements.foldLeft (0) { + (s:int,x:RegExp) => s + minimalWidth( x ) + } + case Binding( _, r ) => minimalWidth( r ); + case _ => 0 + + } } } diff --git a/sources/scala/tools/scalac/transformer/matching/PatternInfo.scala b/sources/scala/tools/scalac/transformer/matching/PatternInfo.scala index db6a6cd352..e69de29bb2 100644 --- a/sources/scala/tools/scalac/transformer/matching/PatternInfo.scala +++ b/sources/scala/tools/scalac/transformer/matching/PatternInfo.scala @@ -1,53 +0,0 @@ - -import scalac.ast._ ; -import scalac.util.Names ; - -package scala.tools.scalac.transformer.matching { - - /** some properties of pattern */ - object PatternInfo { - - - /** returns width */ - private def getLowerBoundWidth( it:Iterator[Tree] ):Int = { - if( !it.hasNext ) 0 else { - var wid = minimalWidth( it.next ); - for( val h <- it ) { - val hw = minimalWidth( h ); - if( hw < wid ) { - wid = hw - } - } - wid - } - } - - /** @todo translate this from ems pattern - */ - def minimalWidth( pat:Tree ):Int = pat match { - case Tree$Alternative( choices ) => 1 // bogus - - // WildcardTree pattern _ - case Tree$Ident( Names.PATTERN_WILDCARD ) => 1 - - // Node pattern t ( ps ) // works also for WildcardNode pattern - case Tree$Apply( _, _ ) => 1 - - // p | ... | p - case Tree$Alternative( ps ) => - getLowerBoundWidth( Iterator.fromArray( ps ) ); - - // p1...pN - case Tree$Sequence( ps ) => - Iterator.fromArray( ps ).foldLeft (0) { - (s:int,x:Tree) => s + minimalWidth( x ) - } - - case Tree$Bind( n, p ) => 1 - - case _ => 0 - - } - } - -} diff --git a/sources/scala/tools/scalac/transformer/matching/PatternTest.scala b/sources/scala/tools/scalac/transformer/matching/PatternTest.scala index a88f21e239..d2a2f31252 100644 --- a/sources/scala/tools/scalac/transformer/matching/PatternTest.scala +++ b/sources/scala/tools/scalac/transformer/matching/PatternTest.scala @@ -1,19 +1,17 @@ import scalac.ast.Tree ; import scalac.atree.AConstant ; import scalac.symtab.Type ; -import scala.util.alphabet.Alphabet; +import scala.util.alphabet.{ AlphabetPlusWildcard, WildcardLabel }; package scala.tools.scalac.transformer.matching { - abstract class PatternTest extends Alphabet ; + abstract class PatternTest extends AlphabetPlusWildcard ; case class Constructor( tpe:Type ) extends PatternTest ; - case object WildCard extends PatternTest; + case class EqualsValue( value:Tree ) extends PatternTest; + case class TypeTest( tpe:Type ) extends PatternTest; - abstract class LeafTest extends PatternTest ; + case object WildcardTest extends PatternTest with WildcardLabel; - case class EqualsConstant( const:AConstant ) extends LeafTest ; - case class EqualsValue( value:Tree ) extends LeafTest ; - case class TypeTest( tpe:Type ) extends LeafTest; } |