regexp lib, nodeSeq, attrSeq changes, test case...

regexp lib, nodeSeq, attrSeq changes, test cases updated

14 files changed, 151 insertions, 80 deletions

diff --git a/config/list/library.lst b/config/list/library.lst
index 4f769b4f68..98488d7fdf 100644
--- a/config/list/library.lst
+++ b/config/list/library.lst
@@ -155,11 +155,14 @@ runtime/matching/Rule.scala
 
 testing/UnitTest.scala
 
-util/regexp/Alphabet.scala
+util/alphabet/Alphabet.scala
+util/automata/NondetWordAutom.scala
+util/automata/BaseBerrySethi.scala
+util/automata/WordBerrySethi.scala
 util/regexp/Base.scala
 util/regexp/WordExp.scala
 util/regexp/PointedHedgeExp.scala
-util/regexp/SyntaxErrorException.scala
+util/regexp/SyntaxError.scala
 
 xml/Attribute.scala
 xml/AttributeSeq.scala
diff --git a/config/list/scalac.lst b/config/list/scalac.lst
index 4d471125a4..daebc89131 100644
--- a/config/list/scalac.lst
+++ b/config/list/scalac.lst
@@ -28,6 +28,7 @@ transformer/UnCurryPhase.scala
 transformer/matching/FullRegularTranslator.scala 
 transformer/matching/GrammarPrinter.scala 
 transformer/matching/MutableGrammar.scala 
+transformer/matching/PatternExp.scala 
 transformer/matching/PatternTest.scala 
 transformer/matching/PatternInfo.scala 
 
diff --git a/sources/scala/tools/scalac/transformer/TransMatch.scala b/sources/scala/tools/scalac/transformer/TransMatch.scala
index 8ee50d5493..c70faaeebc 100644
--- a/sources/scala/tools/scalac/transformer/TransMatch.scala
+++ b/sources/scala/tools/scalac/transformer/TransMatch.scala
@@ -92,11 +92,21 @@ 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 ));
+
+      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;
diff --git a/sources/scala/tools/scalac/transformer/matching/PatternTest.scala b/sources/scala/tools/scalac/transformer/matching/PatternTest.scala
index c93468eed0..a88f21e239 100644
--- a/sources/scala/tools/scalac/transformer/matching/PatternTest.scala
+++ b/sources/scala/tools/scalac/transformer/matching/PatternTest.scala
@@ -1,12 +1,19 @@
-package scala.tools.scalac.transformer.matching ;
+import scalac.ast.Tree ;
+import scalac.atree.AConstant ;
+import scalac.symtab.Type ;
+import scala.util.alphabet.Alphabet;
 
-abstract class PatternTest ;
+package scala.tools.scalac.transformer.matching {
 
-/** test for patterns _:T      */
-case class TypeTest extends PatternTest ;
+  abstract class PatternTest extends Alphabet ;
 
-/** test for patterns A(...)   */
-case class CaseTest extends PatternTest ;
+  case class  Constructor( tpe:Type ) extends PatternTest ;
+  case object WildCard                extends PatternTest;
 
-/** test for constant patterns */
-case class EqTest extends PatternTest ;
+  abstract class LeafTest extends PatternTest ;
+
+  case class EqualsConstant( const:AConstant ) extends LeafTest ;
+  case class EqualsValue( value:Tree )         extends LeafTest ;
+  case class TypeTest( tpe:Type )        extends LeafTest;
+
+}
diff --git a/sources/scala/util/alphabet/Alphabet.scala b/sources/scala/util/alphabet/Alphabet.scala
new file mode 100644
index 0000000000..57d10b6a7f
--- /dev/null
+++ b/sources/scala/util/alphabet/Alphabet.scala
@@ -0,0 +1,3 @@
+package scala.util.alphabet ;
+
+trait Alphabet ;
diff --git a/sources/scala/util/regexp/Base.scala b/sources/scala/util/regexp/Base.scala
index 9ebd148498..4b4ed2cd65 100644
--- a/sources/scala/util/regexp/Base.scala
+++ b/sources/scala/util/regexp/Base.scala
@@ -8,26 +8,47 @@ trait Base {
 
   type regexp <: RegExp;
 
-  abstract class RegExp;
+  abstract class RegExp {
+    val isNullable:Boolean;
+  }
 
   /** Alt( R,R,R* ) */
   case class  Alt(rs: regexp*)  extends RegExp {
 
     // check rs \in R,R,R*
+    if({ val it = rs.elements; !it.hasNext || {it.next; !it.hasNext }})
+      throw new SyntaxError("need at least 2 branches in Alt");
+
+    final val isNullable = {
+      val it = rs.elements;
+      while( it.hasNext && it.next.isNullable ) {}
+      !it.hasNext
+    }
+  }
+  case class  Sequ(rs: regexp*) extends RegExp {
+    // check rs \in R,R*
+    if({ val it = rs.elements; !it.hasNext })
+      throw new SyntaxError("need at least 1 item in Sequ");
+
+    final val isNullable = {
+      val it = rs.elements;
+      while( it.hasNext && !it.next.isNullable ) {}
+      it.hasNext
+    }
+  }
 
-    if({ var i = 0;
-        val it = rs.elements;
-        while( it.hasNext ) {it.next; i=i+1};
-        i} < 2)
-      throw new SyntaxErrorExpression("need at least 2 branches in alt")
+  case class  Star(r: regexp)   extends RegExp {
+    final val isNullable = true;
   }
-  case class  Sequ(rs: regexp*) extends RegExp ;
-  case class  Star(r: regexp)   extends RegExp ;
   case object Eps               extends RegExp {
+    final val isNullable = true;
     override def toString() = "Eps";
   }
 
   /** this class can be used to add meta information to regexps */
-  class Meta( r:regexp )       extends RegExp ;
+  class Meta( r1:regexp )       extends RegExp {
+    final val isNullable = r1.isNullable;
+    def r = r1;
+  }
 
 }
diff --git a/sources/scala/util/regexp/PointedHedgeExp.scala b/sources/scala/util/regexp/PointedHedgeExp.scala
index 593155af39..0c1ce64f8f 100644
--- a/sources/scala/util/regexp/PointedHedgeExp.scala
+++ b/sources/scala/util/regexp/PointedHedgeExp.scala
@@ -2,16 +2,26 @@
 
 package scala.util.regexp ;
 
-/** pointed regular hedge expressions, a useful subclass of full rhe */
+import scala.util.alphabet.Alphabet ;
+
+/** pointed regular hedge expressions, a useful subclass of
+ *  regular hedge expressions.
+ */
 trait PointedHedgeExp[ A <: Alphabet ] extends Base {
 
   type label = A;
 
   type regexp <: RegExp;
 
-  case class  Node(label: A, r: regexp)       extends RegExp ;
-  case class  TopIter(r1: regexp, r2: regexp) extends RegExp ;
+  case class  Node(label: A, r: regexp)       extends RegExp {
+    final val isNullable = false;
+  }
+  case class  TopIter(r1: regexp, r2: regexp) extends RegExp {
+    final val isNullable = r1.isNullable && r2.isNullable; //?
+  }
 
-  case object Point extends RegExp ;
+  case object Point extends RegExp {
+    final val isNullable = false;
+  }
 
 }
diff --git a/sources/scala/util/regexp/WordExp.scala b/sources/scala/util/regexp/WordExp.scala
index d01792aef5..875dd292a1 100644
--- a/sources/scala/util/regexp/WordExp.scala
+++ b/sources/scala/util/regexp/WordExp.scala
@@ -2,6 +2,8 @@
 
 package scala.util.regexp ;
 
+import scala.util.alphabet.Alphabet ;
+
 /** regular word expressions. use them with an alphabet: <pre>
 abstract class IntLabels extends Alphabet;
 object IntWordExp extends WordExp[IntLabels] {
@@ -9,11 +11,10 @@ object IntWordExp extends WordExp[IntLabels] {
 };
  * </pre>
  */
-
 trait WordExp[ A <: Alphabet ] extends Base {
 
-  type label = A;
-
-  case class Letter(a: label)    extends RegExp;
+  case class Letter(a: A)    extends RegExp {
+    final val isNullable = false;
+  }
 
 }
diff --git a/sources/scala/xml/AttributeSeq.scala b/sources/scala/xml/AttributeSeq.scala
index aa0cf3e069..9f2c0b09d4 100644
--- a/sources/scala/xml/AttributeSeq.scala
+++ b/sources/scala/xml/AttributeSeq.scala
@@ -13,17 +13,17 @@ import scala.collection.mutable.HashMap ;
 import scala.collection.immutable.TreeSet ;
 
 object AttributeSeq {
-  final val Empty = new AttributeSeq();
+  final val Empty = new AttributeSeq { final def sortedSeq = new TreeSet[Attribute] }
 
   final def fromHashMap(as:HashMap[Pair[String,String],String]) = {
-    new AttributeSeq( {
+    AttributeSeq.fromAttrs( {
       for( val a <- as.keys.toList )
       yield Attribute(a._1,a._2.intern(), as(a))
     }:_* )
   }
 
   final def fromHashMap(ns:String, as:HashMap[Pair[String,String],String]) = {
-    new AttributeSeq( {
+    AttributeSeq.fromAttrs( {
       for( val a <- as.keys.toList )
       yield {
         val res =
@@ -35,7 +35,15 @@ object AttributeSeq {
       }
     }:_*)
   }
-
+  final def fromAttrs(as: Attribute*) = {
+    var ts = new TreeSet[Attribute];
+    for( val a <- as ) {
+      if( a.key != "xmlns" ) {
+        ts = ts + a ;
+      }
+    }
+    new AttributeSeq { final def sortedSeq = ts };
+  }
 }
 
 /** Sorted linear list of XML attributes.
@@ -43,21 +51,16 @@ object AttributeSeq {
  *  like xmlns or xmlns:pref
  *  @author  Burak Emir
  */
-class AttributeSeq( as:Attribute* ) with Seq[Attribute] {
+abstract class AttributeSeq with Seq[Attribute] {
 
-  private var treeSet:TreeSet[Attribute] = new TreeSet[Attribute];
+  def sortedSeq:TreeSet[Attribute];
 
-  for( val a <- as ) {
-    if( a.key != "xmlns" ) {
-      treeSet = treeSet + a ;
-    }
-  }
-  final def length = treeSet.size;
-  final def elements = treeSet.elements;
-  final def apply(i:Int) = treeSet.elements.drop(i).next;
+  final def length = sortedSeq.size;
+  final def elements = sortedSeq.elements;
+  final def apply(i:Int) = sortedSeq.elements.drop(i).next;
 
   def lookup(ns:String, key:String):Option[Attribute] = {
-    val it = treeSet.elements;
+    val it = sortedSeq.elements;
     while( it.hasNext ) {
       val a = it.next;
       if( a.key > key ) return None
@@ -75,12 +78,12 @@ class AttributeSeq( as:Attribute* ) with Seq[Attribute] {
    *  @return a new symbol with updated attributes
    */
   final def %(attrs: Attribute*) =
-    new AttributeSeq((elements.toList ::: attrs.elements.toList):_*);
+    AttributeSeq.fromAttrs((elements.toList ::: attrs.elements.toList):_*);
 
   final def map(f: Attribute => Attribute): AttributeSeq = {
-    new AttributeSeq( elements.map( f ).toList:_* )
+    AttributeSeq.fromAttrs( elements.map( f ).toList:_* )
   }
 
-  override def hashCode():Int = treeSet.hashCode();
+  override def hashCode():Int = sortedSeq.hashCode();
 }
 
diff --git a/sources/scala/xml/Elem.scala b/sources/scala/xml/Elem.scala
index 4150eb922d..e6482e3cce 100644
--- a/sources/scala/xml/Elem.scala
+++ b/sources/scala/xml/Elem.scala
@@ -41,19 +41,21 @@ case class Elem( namespace$$:String, label$$: String, attributes: AttributeSeq,
    *  @param attrs
    *  @return a new symbol with updated attributes
    */
-  final def %(attrs: Seq[Attribute]): Elem = {
-    val aseq = new AttributeSeq((attributes.toList ::: attrs.toList):_*);
-    Elem(namespace, label, aseq, child:_*)
-  }
+  final def %(attrs: Seq[Attribute]): Elem =
+    Elem(namespace,
+         label,
+         AttributeSeq.fromAttrs((attributes.toList ::: attrs.toList):_*),
+         child:_*) ;
 
   /** Return a new symbol with updated attribute
    *
    *  @param attr
    *  @return a new symbol with updated attribute
    */
-  final def %(attr: Attribute): Elem = {
-    val aseq = new AttributeSeq((attributes.toList ::: attr :: Nil):_*);
-    Elem(namespace, label, aseq, child:_*)
-  }
+  final def %(attr: Attribute): Elem =
+    Elem(namespace,
+         label,
+         AttributeSeq.fromAttrs((attributes.toList ::: attr :: Nil):_*),
+         child:_*) ;
 
 }
diff --git a/sources/scala/xml/Node.scala b/sources/scala/xml/Node.scala
index 639c145122..37e344661f 100644
--- a/sources/scala/xml/Node.scala
+++ b/sources/scala/xml/Node.scala
@@ -24,7 +24,18 @@ object Node {
 /** Trait for representing XML using nodes of a labelled tree.
  *  This trait contains an implementation of a subset of XPath for navigation.
  */
-trait Node {
+trait Node extends NodeSeq {
+
+  final def theSeq = this :: Nil;
+  /*
+  final def length = 1;
+  final def elements = new Iterator[Node] {
+    var notAccessed = true;
+    final def hasNext = notAccessed;
+    final def next = {notAccessed = false; Node.this}
+  }
+  final def apply(i: Int) = if( i==0 ) this else error("singleton sequence");
+  */
 
   /** used internally. Text = -1 PI = -2 Comment = -3 CDATA = -4 EntityRef = -5 */
   def typeTag$:Int = 0;
@@ -76,26 +87,21 @@ trait Node {
  /** projection function. Similar to XPath, use this \ 'foo to get a list
    *  of all children of this node that are labelled with "foo".
    *  The document order is preserved.
-   */
-    def \( that:String ): NodeSeq = {
-      new NodeSeq({
-        that match {
-
-          case "_" => child.toList;
-          case _ =>
-            var res:List[Node] = Nil;
-            for( val x <- child.elements; x.label == that ) {
-              res = x::res;
-            }
-            res.reverse
+    def \( that:String ): NodeSeq = that match {
+
+      case "_" => new NodeSeq { val theSeq = child; }
+      case _   =>
+        var res:List[Node] = Nil;
+        for( val x <- child.elements; x.label == that ) {
+          res = x::res;
         }
-      });
+        new NodeSeq { val theSeq = res.reverse }
     }
+   */
 
  /** projection function. Similar to XPath, use this \\ 'foo to filter
    *  all nodes labelled with "foo" from the descendant_or_self axis.
    *  The document order is preserved.
-   */
   def \\( that:String ): NodeSeq = {
     val z = this.descendant_or_self;
     new NodeSeq(
@@ -104,6 +110,7 @@ trait Node {
         case _ => z.filter( x => x.label == that );
       })
   }
+   */
 
   override def hashCode() = Utility.hashCode(namespace, label, attribute.toList.hashCode(), child);
   /** string representation of this node */
diff --git a/sources/scala/xml/NodeSeq.scala b/sources/scala/xml/NodeSeq.scala
index 5b5941b4ed..f8982bc3d9 100644
--- a/sources/scala/xml/NodeSeq.scala
+++ b/sources/scala/xml/NodeSeq.scala
@@ -10,8 +10,9 @@
 package scala.xml ;
 
 /** a wrapper around Seq[Node] that adds XPath and comprehension methods */
-class NodeSeq( theSeq:Seq[Node] ) extends Seq[Node] {
+abstract class NodeSeq extends Seq[Node] {
 
+  def theSeq: Seq[Node];
   def length = theSeq.length;
   def elements = theSeq.elements ;
   def apply( i:int ) = theSeq.apply( i );
@@ -27,12 +28,12 @@ class NodeSeq( theSeq:Seq[Node] ) extends Seq[Node] {
    *  of all elements of this sequence that are labelled with "foo".
    *  Use \ "_" as a wildcard. The document order is preserved.
    */
-  def \ (that: String):NodeSeq = that match {
+  def \(that: String):NodeSeq = that match {
     case "_" => for( val x <- this;
-                     val y <- new NodeSeq( x.child ) )
+                     val y <- new NodeSeq { val theSeq = x.child; })
                 yield y
     case _   => for( val x <- this;
-                     val y <- new NodeSeq( x.child );
+                     val y <- new NodeSeq { val theSeq = x.child; };
                      y.label == that )
                 yield { y }
   }
@@ -44,15 +45,15 @@ class NodeSeq( theSeq:Seq[Node] ) extends Seq[Node] {
 
   def \\ ( that:String ):NodeSeq = that match {
       case "_" => for( val x <- this;
-                       val y <- new NodeSeq( x.descendant_or_self ))
+                       val y <- new NodeSeq { val theSeq = x.descendant_or_self })
                   yield { y }
       case _ => for( val x <- this;
-                     val y <- new NodeSeq( x.descendant_or_self );
+                     val y <- new NodeSeq { val theSeq =  x.descendant_or_self  };
                      y.label == that)
                   yield { y }
   }
 
-  override def toString() = theSeq.elements.foldLeft ("") {
+  override def toString():String = theSeq.elements.foldLeft ("") {
     (s:String,x:Node) => s + x.toString()
   }
 
@@ -63,15 +64,15 @@ class NodeSeq( theSeq:Seq[Node] ) extends Seq[Node] {
   }
 
   def map( f:Node => Node ):NodeSeq = {
-    new NodeSeq( asList map f )
+    new NodeSeq{ final def theSeq = NodeSeq.this.asList map f }
   }
 
   def flatMap( f:Node => NodeSeq ):NodeSeq = {
-    new NodeSeq( asList flatMap { x => f(x).asList })
+    new NodeSeq{ final def theSeq = NodeSeq.this.asList flatMap { x => f(x).asList }}
   }
 
   def filter( f:Node => boolean ):NodeSeq = {
-    new NodeSeq( asList filter f )
+    new NodeSeq{ val theSeq = NodeSeq.this.asList filter f  }
   }
 
 }
diff --git a/sources/scala/xml/dtd/ContentModel.scala b/sources/scala/xml/dtd/ContentModel.scala
index 0659c68541..2f9cc60080 100644
--- a/sources/scala/xml/dtd/ContentModel.scala
+++ b/sources/scala/xml/dtd/ContentModel.scala
@@ -1,6 +1,6 @@
 package scala.xml.dtd ;
 
-abstract class ElemNames          extends scala.util.regexp.Alphabet;
+abstract class ElemNames          extends scala.util.alphabet.Alphabet;
 case class ElemName(name: String) extends ElemNames {
   override def toString() = "ElemName(\""+name+"\")";
 }
@@ -9,10 +9,12 @@ object ContentModel extends scala.util.regexp.WordExp[ElemNames] {
   type regexp = RegExp;
 
   case object PCDATA_ extends RegExp {
+    final val isNullable = false;
     override def toString() = "PCDATA_";
   }
 
   case object ANY_    extends RegExp {
+    final val isNullable = true;
     override def toString() = "ANY_";
   }
 
diff --git a/sources/scala/xml/dtd/Validation.scala b/sources/scala/xml/dtd/Validation.scala
index 0055b0844c..604debd988 100644
--- a/sources/scala/xml/dtd/Validation.scala
+++ b/sources/scala/xml/dtd/Validation.scala
@@ -129,6 +129,6 @@ class AttributeValidator( namespace$$:String, attrSpec1: Seq[dtd.AttrDecl]) {
         allKeys -= a.key;
       MakeValidationException.fromMissingAttribute( allKeys )
     }
-    new AttributeSeq( (attribsTemplate:::attribs):_* )
+    AttributeSeq.fromAttrs( (attribsTemplate:::attribs):_* )
   }
 }