matching stuff

7 files changed, 631 insertions, 0 deletions

diff --git a/sources/scala/runtime/matching/Address.scala b/sources/scala/runtime/matching/Address.scala
new file mode 100644
index 0000000000..2691d27801
--- /dev/null
+++ b/sources/scala/runtime/matching/Address.scala
@@ -0,0 +1,27 @@
+package scala.runtime.matching ;
+
+object Address {
+  def empty = new Address();
+}
+
+/** Address holds the path in reverse Dewey notation
+*/
+class Address( l:Int* ) with Ordered[Address] {
+
+  private val list:List[Int] = l.toList;
+
+  def compareTo [b >: Address <% Ordered[b]](y: b): int = y match {
+    case o:Address => List.view(list.reverse) compareTo o.list.reverse;
+    case _ => -(y compareTo this)
+  }
+
+  def down: Address = new Address( ( 1 :: list ):_* );
+
+  /** precond: p is nonempty */
+  def right: Address = list.match {
+    case List( i, rest@_* ) => new Address( ((i+1) :: rest ):_* )
+  }
+
+  override def toString() = list.mkString("Address(",".",")");
+
+}
diff --git a/sources/scala/runtime/matching/Context.scala b/sources/scala/runtime/matching/Context.scala
new file mode 100644
index 0000000000..b50ce8c0a5
--- /dev/null
+++ b/sources/scala/runtime/matching/Context.scala
@@ -0,0 +1,219 @@
+package scala.runtime.matching ;
+/** contexts fully determined which derivation was used along a path,
+*   thereby allowing to select the proceed the %next% derivations.
+*
+*   we use here that derivations are ordered.
+*/
+abstract class PathContext with Ordered[PathContext] {
+  val len = 0;
+  def isCompatible( other:PathContext ):boolean ;
+  def ~( other:PathContext ):boolean ;
+  def prune( len:int ):PathContext = this;
+  def address:List[Int] = 0::Nil;
+  def toString1():String = "";
+
+  def compareTo [b >: PathContext <% Ordered[b]](that: b): int = that match {
+    case t:PathContext =>
+      if( rctx_inf(this,t) )
+        -1
+      else if( rctx_eq(this,t) )
+        0
+      else
+        1;
+    case _ => -(that compareTo this)
+  }
+
+
+
+  final def rctx_inf( x:PathContext, y:PathContext ):boolean = x match {
+    case EmptyContext => y match {
+      case EmptyContext => false;
+      case _ => true;
+    }
+    case RuleContext(r1, up1) => y match {
+      case RuleContext(r2,up2) =>
+        ((r1 == r2 ) && rctx_inf(up1, up2))
+        || ( r1 < r2 )
+      case _ => false;
+    }
+  }
+
+  final def rctx_eq( x:PathContext, y:PathContext ) = x == y;
+}
+/** use HedgeNT H */
+/*
+case class HedgeContext( H:HedgeNT, outer:PathContext ) extends PathContext {
+  override def toString():String = outer.toString()+":"+H.toString();
+def isCompatible( other:PathContext ):boolean   = error("don't call me");
+def ~( other:PathContext )   = error("don't call me");
+}
+*/
+/** use TreeNT T */
+/*
+case class TreeContext( T:TreeNT, up:PathContext ) extends PathContext {
+  override def toString():String = up.toString()+":"+T.toString();
+def isCompatible( other:PathContext ):boolean = error("don't call me");
+def ~( other:PathContext )  = error("don't call me");
+};
+*/
+/** the root context */
+case object EmptyContext extends PathContext {
+  override def toString1() = "()";
+  override def toString():String = "()";
+  def isCompatible( other:PathContext ):boolean = true;
+  override def ~( other:PathContext ) = true;
+}
+
+/* inv: up is RuleContext || EmptyContext */
+case class RuleContext( r:Rule, up:PathContext ) extends PathContext {
+
+  override def toString1():String = { up.toString1()+";"+r.toString() }
+
+  override def toString():String = toString1()+"["+address.reverse+"]";
+  override val len = up.len + 1;
+
+  def down(li:List[Int]):List[Int] = 0::li;
+
+  def right(li:List[Int]):List[Int] = li match {
+    case i::is => i+1::is
+  }
+
+  override def address:List[Int] = r match {
+    case HedgeRule( _, _ ) => right( up.address );
+    case AnyNodeRule( _, _ ) => down( up.address );
+    case TreeRule( _, _ ) =>  down( up.address );
+    case AnyTreeRule( _ ) =>  down( up.address );
+  }
+
+  /* if have common prefix */
+  override def isCompatible( other:PathContext ):boolean = {
+    Console.println( "isCompatible called\nthis:"+this+" len="+this.len+"\nother"+other+" len = "+other.len);
+    val q = {
+      if( this.len > other.len ) {
+        Console.println("this.prune(otherlen) = "+ this.prune( other.len ));
+
+        val tmp = this.prune( other.len );
+        ( tmp == other )||( tmp ~ other )
+
+      } else if( this.len < other.len ) {
+        val tmp = other.prune( this.len );
+        Console.println("other.prune(thislen) = "+ tmp);
+        ( this == tmp )||( this ~ tmp );
+      } else
+        (this == other )|| this ~ other
+      // ^ for x @ y @ p
+    };
+    Console.println("result: "+q);
+    q
+  }
+
+  override def ~( other:PathContext ) = {
+    def matchesH( H:HedgeNT, r2:Rule ) = r2 match {
+      case HedgeRule( H, _ ) => true
+      case _ => false;
+    };
+    def matchesT( T:TreeNT, r2:Rule ) = r2 match {
+      case TreeRule( T, _ ) => true
+      case AnyTreeRule( T ) => true
+      case AnyNodeRule( T, _ ) => true
+      case _ => false;
+    };
+    (other match {
+      case RuleContext( r2, up2 ) =>
+      ( (up == up2) && (this.up match {
+
+        case RuleContext(HedgeRule(h, Pair(t1,h1)),_) =>
+          ( matchesT( t1, this.r ) && matchesH( h1, r2 ) )
+          ||( matchesT( t1, r2 ) && matchesH( h1, this.r ) )
+
+        case _ => false;
+
+      })  || up ~ up2 )
+
+        case EmptyContext => true;/*other match {
+          case EmptyContext => true;
+          case _ => false;
+        }*/
+    })
+  }
+
+  override def prune( len:int ):PathContext = {
+    if( this.len > len ) up.prune( len ) else this;
+  }
+}
+
+/*
+def ctx_inf( x:PathContext, y:PathContext ):boolean = {
+  x match {
+    case EmptyContext => y match {
+      case EmptyContext => false;
+case _ => true;
+    }
+case HedgeContext( h:HedgeNT, out:PathContext ) => y match {
+  case HedgeContext( h2:HedgeNT, out2:PathContext ) =>
+    (ctx_eq(out,out2) &&( h.i < h2.i )) || ctx_inf( out,out2 )
+case _ => false
+}
+case TreeContext( t:TreeNT, up:PathContext ) => y match {
+  case TreeContext( t2:TreeNT, up2:PathContext ) =>
+    (ctx_eq(up,up2) && (t.i < t2.i)) || ctx_inf( up, up2 )
+case _ => true
+}
+  }
+}
+
+def ctx_eq( x:PathContext, y:PathContext ):boolean = {
+  x match {
+    case EmptyContext => y match {
+      case EmptyContext => true;
+case _ => true;
+    }
+case HedgeContext( h:HedgeNT, out:PathContext ) => y match {
+  case HedgeContext( h2:HedgeNT, out2:PathContext ) =>
+    ctx_eq(out,out2) &&( h.i == h2.i )
+case _ => false
+}
+case TreeContext( t:TreeNT, up:PathContext ) => y match {
+  case TreeContext( t2:TreeNT, up2:PathContext ) =>
+    ctx_eq(up,up2) && (t.i == t2.i)
+case _ => false
+}
+  }
+}
+*/
+//val contextOrder = new Order[PathContext]( ctx_inf, ctx_eq ) ;
+
+//  val ruleContextOrder = new Order[PathContext]( rctx_inf, rctx_eq ) ;
+
+
+/* matcher needs this operations
+isApplicableTree(1):
+  given string s, and set of TreeNTs A, return a A'(\subseteq A) and a set B'
+  such that for every t' in A' grammar has a rule t' -> s < h' >
+
+maybe grammar is a map Str -> Pow(P x Q) rather than P -> Str x Q or
+array P x Str_Index -> Q (use hashmap for strings that appear in a pattern!)
+(P = treents, Q = hedgeNTs) and a map Q x P -> Q rather than Q -> P x Q
+
+isApplicableTree(2):
+  given a set B'' ( subseteq B' ) of hedgeNTs, and s and A' like above,
+  return A''(\subseteq A') with those rules that have nonterminals from B''.
+
+see above
+
+isApplicableHedge(1)
+  get epsilon closure of hedgeNTs (followChainRules) ?? needed ??
+
+isApplicableHedge(2)
+  given set B of hedgeNTs h, return a set A of treeNTs t such that
+  there is rule h -> ( t , _ )
+
+isApplicableHedge(3)
+  given set B and set A'(subseteq A), return a set C of hedgeNTs h2 such that
+  there is rule h -> ( t' , h2 )
+
+isApplicableHedge(4)
+  given set C' (\subseteq C)  extract B' (subseteq B) such that there is
+  rule h' -> ( _ , h2' )
+
+*/
diff --git a/sources/scala/runtime/matching/Grammar.scala b/sources/scala/runtime/matching/Grammar.scala
new file mode 100644
index 0000000000..69a7c10a27
--- /dev/null
+++ b/sources/scala/runtime/matching/Grammar.scala
@@ -0,0 +1,90 @@
+package scala.runtime.matching ;
+
+import scala.collection.Set;
+import scala.collection.Map ;
+import scala.collection.immutable;
+import scala.collection.mutable;
+
+//val ruleOrder = new Order( rule_smaller, rule_eq );
+
+case class PatternGrammar( treeRules:Set[Rule],
+                           treeTransitions:Map[Int,Set[Rule]],
+                           hedgeRules:Set[Rule],
+                           hedgeTransitions:Map[Int,Set[Rule]],
+                           thVars:mutable.Map[Int,List[Int]],
+                           typeMapping:immutable.Map[Int,String/*Type*/],
+                           make:NonTermFactory) {
+
+  val isSequenceType = false;
+
+  /** this mapping is only for debugging purposes. Given a variable index,
+   ** it prints out the string representation of this variable
+   */
+  val debugVarMapping:mutable.Map[Int,String] =
+    new mutable.HashMap[Int,String]();
+
+  def hedgeRulesToString:String = {
+    hedgeRules.foldLeft ("") {
+      (s:String,r:Rule) => s + (r match {
+        case HedgeRule( h, _ ) if ( make.hedgeInitials contains h ) => "*"
+        case _ => " "
+      }) + r.toString() + "\n"
+    } ;
+  }
+
+  def treeRulesToString:String = {
+    treeRules.foldLeft ("") {
+      (s:String,r:Rule) => s + r.toString() + "\n"
+    } ;
+  }
+
+  def toString:String = {
+    val sb = new StringBuffer();
+    sb.append( { if( treeRules.isEmpty )
+      "Set of rules is EMPTY.\n" else treeRulesToString });
+    sb.append( { if( hedgeRules.isEmpty )
+      "Set of rules is EMPTY.\n" else hedgeRulesToString });
+    /*
+    sb.append( { if( bindMap.isEmpty )
+      "Binding mapping is EMPTY.\n" else mapsToString });
+    */
+    sb.append( "hedgeInitials:"+make.hedgeInitials );
+    sb.append( "treeInitials:"+make.treeInitials );
+    sb.append( "\ntreeTransitions:"+treeTransitions );
+    sb.append( "\nhedgeTransitions:"+hedgeTransitions );
+    sb.append( "\nvariables :"+( thVars( 0 ).map { debugVarMapping }) );
+    sb.append( "\ntypeMapping :"+ typeMapping.toString() );
+    sb.toString()
+  }
+}
+
+
+
+/*
+def followChainRules( nset:Set[HedgeNT],
+                     gram:Set[Rule] ):immutable.Set[HedgeNT] = {
+                       //Console.println("followChainRules");
+  var dirty = false;
+var newnset = immutable.ListSet.Empty[HedgeNT].incl( nset );
+for( val nt <- nset ) {
+  for( val rule <- gram ) {
+    val NT = nt;
+rule match {
+  case HedgeChainRule( NT, h ) => {
+    if( !newnset.contains( h ) ) {
+      dirty = true;
+newnset = newnset + h;
+    }
+  }
+          case _ =>
+}
+  }
+}
+if( dirty ) {
+  followChainRules( newnset, gram );
+} else {
+  //Console.println("followChainRules output" + newnset);
+  newnset
+}
+                     }
+*/
diff --git a/sources/scala/runtime/matching/Match.scala b/sources/scala/runtime/matching/Match.scala
new file mode 100644
index 0000000000..6674c3157a
--- /dev/null
+++ b/sources/scala/runtime/matching/Match.scala
@@ -0,0 +1,105 @@
+package scala.runtime.matching ;
+
+import scala.collection.Map ;
+import scala.collection.immutable ;
+import scala.xml.Node ;
+
+object Match {
+
+  def res2string(res:immutable.Map[ Int, PathContext ]):String = {
+    val sb = new StringBuffer();
+    sb.append( "binding {\n" );
+    for( val vble <- res.keys ) {
+      val pc = res.get( vble ).get;
+      sb.append( "  " );
+      sb.append( vble );
+      sb.append( " <- " );
+      sb.append( pc.address.reverse );
+      sb.append( '\n' );
+    }
+    sb.append( "}\n" );
+    sb.toString();
+  }
+
+  /* pm: remaining pebbles
+  */
+  def printSol( vble:Int,
+                b2:PathContext,
+                vctx:immutable.Set[PathContext],
+                pm:immutable.Map[ Int, immutable.Set[PathContext] ],
+                result:immutable.Map[ Int, PathContext] ):unit = {
+    Console.println("printSol("+vble+","+vctx+","+pm+","+result+")");
+    for( val b <- vctx.elements; {if( b2!=null ) b.isCompatible( b2 ) else true}) {
+      val nres = result.update( vble, b );
+      if( pm.isEmpty ) {
+        Console.println( nres );
+        Console.println( res2string(nres) );
+      } else for( val nextVar <- pm.keys;
+                 val nextCtx <- pm.get( nextVar )) {
+                   printSol( nextVar, b, nextCtx, pm - nextVar, nres )
+                 }
+    }
+  }
+
+
+  def decode( pebblesMap:immutable.Map[ Int, immutable.Set[PathContext] ] ) = {
+
+    val it = pebblesMap.keys;
+    if( it.hasNext ) {
+      val first = it.next ;
+      val fctx = pebblesMap.get( first ).get;
+      printSol( first,
+               null,
+               fctx,
+               pebblesMap - first,
+               new immutable.TreeMap[Int,PathContext] )
+    }
+  }
+
+}
+
+
+class Match( k:Int,it:Iterator[Seq[scala.xml.Node]] ) {
+
+  def equals( o:Object ) = o match {
+    case that:Match =>
+    ( this.index == that.index )&&( this.iter.toList == that.iter.toList )
+    case _ => false;
+  }
+
+  val index = k;
+  val iter = it;
+
+  /** this method is destructive
+  **/
+  def toString_DEBUG( vx2str:Int => String ) = {
+    if( !iter.hasNext ) {
+      "<empty binding>"
+    } else {
+      val sb = new StringBuffer("<match> with binding");
+      var vx = 0;
+      while( iter.hasNext ) {
+        sb.append( vx2str( vx ) + " <- " + iter.next.toString + "\n" );
+      }
+      sb.toString();
+    }
+  }
+
+  /** this method is destructive
+  **/
+  def same( that:Match ) = {
+    ( this.index == that.index )&&( this.iter.toList == that.iter.toList )
+  }
+
+  /** this method is destructive
+  **/
+  override def toString() = {
+    val sb = new StringBuffer("Match("+index);
+    while( iter.hasNext ) {
+      sb.append( "," );
+      sb.append( iter.next.toString() );
+    }
+    sb.append(")");
+    sb.toString();
+  }
+}
diff --git a/sources/scala/runtime/matching/NonTerm.scala b/sources/scala/runtime/matching/NonTerm.scala
new file mode 100644
index 0000000000..1f79ae7a79
--- /dev/null
+++ b/sources/scala/runtime/matching/NonTerm.scala
@@ -0,0 +1,75 @@
+package scala.runtime.matching ;
+
+import scala.collection.immutable ;
+
+abstract class NonTerm  {
+
+  override def toString() = this match {
+    case TreeNT( i ) => "t"+i;
+    case HedgeNT( i ) => "h"+i;
+  }
+}
+
+case class TreeNT(i:int) extends NonTerm with Ordered[TreeNT] {
+  def compareTo [b >: TreeNT <% Ordered[b]](y: b): int = y match {
+    case TreeNT( y1 ) => i compareTo y1;
+    case _ => -(y compareTo this)
+  }
+  var vset:immutable.Set[Int] = immutable.ListSet.Empty ;
+};
+case class HedgeNT(i:int) extends NonTerm with Ordered[HedgeNT] {
+  def compareTo [b >: HedgeNT <% Ordered[b]](y: b): int = y match {
+    case HedgeNT( y1 ) => i compareTo y1;
+    case _ => -(y compareTo this)
+  }
+  var nullable:boolean = false;
+  //val vset:immutable.Set[Int] = immutable.ListSet.Empty ;
+};
+
+object EmptySeqNT extends HedgeNT(0) {
+  override val nullable = true;
+  };
+object AnyHedgeNT extends HedgeNT(1); // for the "anytree-rule": (A,("",AnyTreeNT))
+object ANYTREE extends TreeNT(1);
+// for the "anynode-rule": (A,("",HedgeNT B))
+
+class NonTermFactory {
+
+  var treeInitials:immutable.Set[TreeNT] = new immutable.TreeSet[TreeNT]();
+  var hedgeInitials:immutable.Set[HedgeNT] = new immutable.TreeSet[HedgeNT]();
+
+  //private var counter = 4;
+  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 ) {
+      override var vset = vs;
+    };
+    */
+    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/Pebble.scala b/sources/scala/runtime/matching/Pebble.scala
new file mode 100644
index 0000000000..42f7c01c78
--- /dev/null
+++ b/sources/scala/runtime/matching/Pebble.scala
@@ -0,0 +1,14 @@
+package scala.runtime.matching ;
+
+case class Pebble(vx:Int,p:Address) with Ordered[Pebble] {
+
+  def compareTo[ b >: Pebble <% Ordered[b] ]( y:b ) = y match {
+    case Pebble( vx2, p2 ) =>
+      if( vx == vx2 )
+        p compareTo p2
+      else
+        vx compareTo vx2
+    case _ => -( y compareTo this )
+  }
+
+}
diff --git a/sources/scala/runtime/matching/Rule.scala b/sources/scala/runtime/matching/Rule.scala
new file mode 100644
index 0000000000..1ac1991022
--- /dev/null
+++ b/sources/scala/runtime/matching/Rule.scala
@@ -0,0 +1,101 @@
+package scala.runtime.matching ;
+
+/* hedge grammar rules */
+abstract class Rule with Ordered[Rule] {
+
+  def compareTo [b >: Rule <% Ordered[b]](that: b): int = that match {
+    case r:Rule =>
+      if( rule_smaller( this, r ) )
+        -1
+      else if( rule_eq( this, r ) )
+        0
+      else
+        1
+    case _ => -(that compareTo this)
+  }
+
+  final def rule_smaller( r1:Rule, r2:Rule ):boolean = r1 match {
+    case HedgeRule( h1, Pair(_, hh1) ) => r2 match {
+      case HedgeRule( h2, Pair(_,hh2) ) =>
+        ((h1 == h2)&&( hh1.i < hh2.i )) || h1.i < h2.i;
+      case HedgeChainRule( h2, hh2 ) =>
+        ((h1 == h2)&&( hh1.i < hh2.i )) || h1.i < h2.i;
+      case _ => false;
+    }
+    case HedgeChainRule( h1, hh1 ) => r2 match {
+      case HedgeRule( h2, Pair(_,hh2) ) =>
+        ((h1 == h2)&&( hh1.i < hh2.i )) || h1.i < h2.i;
+      case HedgeChainRule( h2, hh2 ) =>
+        ((h1 == h2)&&( hh1.i < hh2.i )) || h1.i < h2.i;
+      case _ => false;
+    }
+    case TreeRule( t1, Pair(_,hh1) ) => r2 match {
+      case TreeRule( t2, Pair(_,hh2) ) =>
+        ((t1 == t2 )&&(hh1.i < hh2.i )) || t1.i < t2.i;
+      case AnyTreeRule( t2 ) => false;
+      case AnyNodeRule( t2, hh2 ) =>
+        ((t1 == t2 )&&(hh1.i < hh2.i )) || t1.i < t2.i;
+      case _ => true;
+    }
+    case AnyTreeRule( t1 ) => r2 match {
+      case TreeRule( _, _  ) => true;
+      case AnyTreeRule( t2 ) => t1.i < t2.i;
+      case AnyNodeRule( t2, _ ) => true
+      case _ => true;
+    }
+    case AnyNodeRule( t1, hh1 ) => r2 match {
+      case TreeRule( t2, Pair(_, hh2) ) =>
+        ((t1 == t2 )&&(hh1.i < hh2.i )) || t1.i < t2.i;
+      case AnyTreeRule( t2 ) => false;
+      case AnyNodeRule( t2, hh2 ) =>
+        ((t1 == t2 )&&(hh1.i < hh2.i )) || t1.i < t2.i;
+      case _ => true;
+    }
+  };
+  final def rule_eq( r1:Rule, r2:Rule ):boolean = r1 == r2;
+
+
+  override def toString() = this match {
+    case HedgeChainRule( n, m ) =>
+      n.toString()+" ::= "+m.toString();
+
+    case TreeRule( n, Pair( label, n2 ) ) =>
+      n.toString()+{ if( !n.vset.isEmpty ) n.vset.toString() else "" }+
+    " ::= "+label+"( "+n2.toString()+{if( n2.nullable ) "~" else ""}+" )";
+
+    case AnyTreeRule( n ) =>
+      n.toString()+{ if( !n.vset.isEmpty ) n.vset.toString() else "" }+
+    " ::= _ ";
+
+    case AnyNodeRule( n, h ) =>
+      n.toString()+{ if( !n.vset.isEmpty ) n.vset.toString() else "" }+
+    " ::= _ ( "+h.toString()+" )";
+
+    case HedgeRule( n, Pair( t, h ) ) =>
+      n.toString()+{
+        if( n.nullable ) "~" else " "
+      }+" ::= "+{
+        if( t == ANYTREE ) "_" else t.toString()
+      }+" "+h.toString();
+
+  }
+}
+/*
+a tree rule is of the from  A -> s(B)
+where A,B are TreeNTs and s is an identifier (string).
+
+If s is the empty string, then the node label is arbitrary
+If HedgeNT is AnyHedgeNT, then the tree is arbitrary
+*/
+case class HedgeChainRule( n: HedgeNT, rhs: HedgeNT ) extends Rule;
+case class TreeRule( n:TreeNT, rhs:Pair[Int,HedgeNT] ) extends Rule {
+  def this(i:int, s:Int, n:int ) = {
+    this( new TreeNT(i), new Pair(s, new HedgeNT(n)));
+  }
+};
+case class AnyTreeRule( n:TreeNT ) extends Rule {
+}
+case class AnyNodeRule( n:TreeNT, h:HedgeNT ) extends Rule {
+}
+case class HedgeRule( n:HedgeNT, rhs:Pair[TreeNT,HedgeNT] ) extends Rule;
+