summaryrefslogtreecommitdiff
path: root/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala
diff options
context:
space:
mode:
Diffstat (limited to 'src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala')
-rw-r--r--src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala522
1 files changed, 522 insertions, 0 deletions
diff --git a/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala b/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala
new file mode 100644
index 0000000000..cd1d8b576e
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/matching/NondetWordAutoms.scala
@@ -0,0 +1,522 @@
+package scala.tools.nsc.matching ;
+import java.util._ ;
+
+trait NondetWordAutoms {
+/** a nondeterministic word automaton.
+ * states are represented (implicitly) as Integer objects.
+ */
+class NondetWordAutom {
+ // BEGIN stuff from FiniteAutom
+
+ //final static Integer FINTAG = new Integer(0);
+
+ /** number of states */
+ var nstates: int =_;
+
+ /** the 'alphabet' */
+ var labels: HashSet = _;
+
+ /** the set of final states, here as a TreeMap */
+ var finals: TreeMap = _;
+
+ /** dfa: HashMap trans: Object -> Integer
+ * nfa: HashMap trans: Object -> Vector [ Integer ]
+ *
+ * nfa: Integer ->(Object -> Vector [ Int ])
+ * [q] |->( a |-> { q' | (q,a,q') in \deltaright } )
+ *
+ * dfa: Integer ->(Object -> Int)
+ * [q] |->( a |-> q' | \deltaright(q,a) = q' } )
+ */
+
+ var _deltaq:Array[HashMap] = _;
+
+ var _defaultq:Array[Vector] = _; // this gives the default transitions
+
+ //public HashMap deltaq[];
+
+ // --- accessor methods
+
+ /** returns number of states
+ def nstates(): int = {
+ return nstates;
+ }
+ */
+
+ /** returns the labels
+ def labels(): HashSet = {
+ return _labels;
+ }
+ */
+
+ /** returns the transitions
+ */
+ def deltaq( state: int ):HashMap = {
+ return _deltaq( state );
+ }
+
+ /** returns the transitions
+ */
+ def deltaq( state: Integer ): HashMap = {
+ return _deltaq( state.intValue() );
+ }
+
+ /** returns the transitions
+ */
+ def defaultq( state: int ): Vector = {
+ return _defaultq( state );
+ }
+
+ /** returns the transitions
+ */
+ def defaultq( state:Integer ): Vector = {
+ return _defaultq( state.intValue() );
+ }
+
+
+ /** returns true if the state is final
+ */
+ def isFinal( state:int ): boolean = {
+ return ((finals != null)
+ && (finals.get( new Integer( state )) != null));
+ }
+
+ /** returns true if the state is final
+ */
+ def isFinal( state:Integer ): boolean = {
+ return ((finals != null) && finals.containsKey( state ));
+ }
+
+ /** returns true if the state is final
+ */
+ def finalTag( state: Integer ): Integer = {
+ return finals.get( state ).asInstanceOf[Integer];
+ }
+
+
+ def finalTag( state:int ): Integer = {
+ return finals.get( new Integer (state )).asInstanceOf[Integer];
+ }
+
+ /** returns true if the set of states contains at least one final state
+ */
+ def containsFinal( Q:TreeSet ): boolean = {
+ var it = Q.iterator();
+ while(it.hasNext()) {
+ if( isFinal( it.next().asInstanceOf[Integer]))
+ return true;
+ }
+ return false;
+ }
+
+
+ /** returns true if there are no finite states
+ */
+ def isEmpty(): boolean = finals.isEmpty();
+
+ // END stuff from FiniteAutom
+
+
+ // inherited from FiniteAutom
+
+ // set of *distinct* objects that may label transitions
+ // see Object.hashCode() to see why this works
+
+ //HashSet labels;
+ //TreeMap finals;
+
+ var initials: TreeSet = _; // ? need this ?
+ // ---
+
+ // Object deltaq -->
+ // HashMap deltaq[]; // this gives the transitions of q;
+
+ var leftTrans: boolean = _;
+ var rightTrans: boolean = _;
+
+ /** if true, this automaton behaves as a special left transducer.
+ * if a run succeeds, the result is not "true" but the entire
+ * run of the automaton as a sequence of (label,state) - pairs.
+ * used for binding variables.
+ */
+ def producesRun(): boolean = {
+ return leftTrans;
+ }
+
+ def consumesRun(): boolean = {
+ return rightTrans;
+ }
+
+ def initial( i: Integer ): boolean = {
+ return initials.contains( i );
+ }
+ var qbinders: Array[Vector] = _;
+
+ /** returns all states accessible from Qsrc via label.
+ * used by class DetWordAutomaton.
+ */
+ def getSide ( Qsrc:TreeSet , label:Object ): TreeSet = {
+ //Console.println("NWA::getSide(Qsrc="+Qsrc);
+ val Qdest = new TreeSet();
+ var it = Qsrc.iterator();
+ while(it.hasNext()) {// state
+ val q = it.next().asInstanceOf[Integer].intValue();
+ val ps = deltaq( q ).get( label ).asInstanceOf[Vector];
+ //Console.println("deltaq(q) = "+deltaq(q));
+ //Console.println("_deltaq(q) = "+_deltaq(q));
+ //Console.println("ps = "+ps);
+ if( null != ps ) {
+ Qdest.addAll( ps );
+ }
+ //Console.println("defq = "+_defaultq( q ));
+ Qdest.addAll( _defaultq( q ) );
+ }
+ //Console.println("DONE-NWA::getSide");
+ return Qdest;
+ }
+
+ /** returns the transitions
+ */
+ def defaultq( P1: Set ): Object = {
+ val defTarget = new TreeSet();
+ var p1 = P1.iterator();
+ while(p1.hasNext()) {
+ val q1 = p1.next().asInstanceOf[Integer].intValue();
+ //System.out.println(" q1:"+q1+ " defa: "+defaultq( q1 ));
+ defTarget.addAll( _defaultq( q1 ) );
+ }
+ return defTarget;
+ }
+
+
+ /** first match policy: among several final states, the smallest one is
+ * chosen. used by class DetWordAutomaton
+ */
+ def finalTag( Q:Set ): Integer = {
+
+ var min = Integer.MAX_VALUE ;
+ var it = Q.iterator();
+ while(it.hasNext()) {
+ val state = it.next().asInstanceOf[Integer];
+ val tag = finals.get( state ).asInstanceOf[Integer];
+ if( tag != null ) {
+ if( tag.intValue() < min )
+ min = tag.intValue();
+ }
+ }
+
+ if ( min == Integer.MAX_VALUE )
+ scala.Predef.error( "there should be a final state ");
+
+ return new Integer( min );
+ }
+
+ /*
+ void tmap(int offs, TreeMap t) = {
+ TreeMap nt = new TreeMap();
+ for(Iterator it = t.keySet().iterator(); it.hasNext(); ) = {
+ Integer key = (Integer) it.next();
+ Integer newkey = new Integer( key.intValue() + offs );
+ Integer val = (Integer) t.get( key );
+ Integer newval = new Integer( val.intValue() + offs );
+
+ nt.put( newkey, newval );
+ }
+ return nt;
+ }
+ */
+ // hashmaps, treemaps
+ def mapmap(src:Map, offset:int , dest:Map , mapkeys:boolean , mapvals:boolean ): Map = {
+ var it = src.keySet().iterator();
+ while(it.hasNext()) {
+ var key = it.next();
+ var value = src.get( key );
+ if( mapkeys ) key = new Integer( key.asInstanceOf[Integer].intValue()
+ + offset );
+ if( mapvals ) value = vmap( offset, value.asInstanceOf[Vector] ) ;
+ /* new Integer( ((Integer)val).intValue()
+ + offset );
+ */
+ dest.put( key, value );
+ }
+ return dest;
+ }
+
+ def vmap(offs:int , v:Vector ): Vector = {
+ if( v == null )
+ return null;
+ var res = new Vector( v.size() );
+ var it = v.iterator();
+ while(it.hasNext()) {
+ val item = it.next().asInstanceOf[Integer];
+ res.add( new Integer( item.intValue() + offs ));
+ }
+ return res;
+
+ }
+
+ /*
+ void relocate_defaultq( int offs, Vector _defaultq[] ) = {
+ for( int i = 0; i < this.nstates; i++ ) = {
+ _defaultq[ i + offset ] = vmap( offset, ((Vector[])defaultq)[ i ]);
+ }
+ }
+ */
+
+ /** copies the values in the fields of this object into the
+ * arguments, possibly adding an offset.
+ */
+ def relocate( offset:int, _finals:TreeMap, _deltaq1:Array[HashMap], _defaultq1:Array[Vector], _qbinders1:Array[Vector] ): Unit = {
+
+ mapmap( finals, offset, _finals, true, false);
+ var i = 0;
+ while(i < this.nstates) {
+
+ _deltaq1 ( i + offset ) =
+ mapmap( deltaq( i ), offset, new HashMap(), false, true).asInstanceOf[HashMap];
+
+ _defaultq1( i + offset ) = vmap( offset, this.defaultq( i ) );
+ i = i + 1;
+ }
+ if ((_qbinders1 != null) &&( qbinders != null )) {
+ i = 0;
+ while(i < this.nstates ) {
+ //System.out.println("hallo"+qbinders);
+ //System.out.println("qbinders[ i ] :"+qbinders[ i ]);
+ //assert _qbinders != null;
+ //System.out.println("_qbinders :"+_qbinders);
+
+ _qbinders1( i + offset ) = qbinders( i );
+ i = i + 1
+ }
+ }
+ }
+
+
+ /** if there is more than one initial state, a new initial state
+ * is created, with index 0
+ */
+ def normalize( initials:TreeSet , reloc:boolean ): Unit = {
+ //if( initials.size() == 1 )
+ // return;
+
+ var idelta = new HashMap();
+ var idefault = new TreeSet();
+
+ var q0 = new Integer( 0 );
+
+ var it = initials.iterator();
+ while(it.hasNext()) {
+
+ val ostate = it.next().asInstanceOf[Integer];
+
+ val finTag = finals.get( ostate ).asInstanceOf[Integer] ;
+ if(( finTag != null ) && ( finals.get( q0 ) == null))
+ finals.put( q0, finTag );
+
+
+ var tmp = deltaq( ostate );
+
+ if( reloc )
+ tmp = mapmap( tmp, 1, new HashMap(), false, true ).asInstanceOf[HashMap];
+
+ val labs = tmp.keySet().iterator();
+ while(labs.hasNext()) {
+ val lab = labs.next();
+ var itarget = idelta.get( lab ).asInstanceOf[Vector];
+ if( null == itarget )
+ idelta.put( lab, {itarget = new Vector(); itarget});
+ val otarget = tmp.get( lab ).asInstanceOf[Vector];
+ itarget.addAll( otarget );
+ }
+ //System.out.println( "normalize:defaultq[ "+ostate+" ] "+((Vector[]) defaultq) [ ostate.intValue() ]);
+ if( defaultq( ostate ) != null )
+ idefault.addAll( defaultq( ostate ) );
+ }
+
+ if( reloc ) {
+ val m = 1 + this.nstates;
+ val _finals = new TreeMap();
+ val _deltaq = new Array[HashMap]( m );
+ val _defaultq = new Array[Vector]( m );
+ var _qbinders: Array[Vector] = null;
+
+ if( qbinders != null )
+ _qbinders = new Array[Vector]( m );
+
+ relocate( 1, _finals, _deltaq, _defaultq, _qbinders );
+
+ this.nstates = m;
+ this.finals = _finals;
+ this._deltaq = _deltaq;
+ this._defaultq = _defaultq;
+ this.qbinders = _qbinders;
+ }
+
+ this._deltaq ( 0 ) = idelta;
+ //System.out.println("normalize:deltaq[ 0 ]"+ idelta );
+ this._defaultq( 0 ) = new Vector( idefault );
+
+ //System.out.println("normalize:defaultq[ 0 ]"+ idefault );
+
+ this.initials = new TreeSet();
+ this.initials.add( q0 );
+ }
+
+
+ /** called from Berry-Sethi construction.
+ */
+
+ def this(nstates:int, _labels:HashSet, initials: TreeSet, finals:TreeMap, deltaq:Array[HashMap], defaultq:Array[Vector], qbinders:Object ) = {
+ this();
+ //Console.println("NWA::this(. . . . )");
+ this.nstates = nstates;
+ this.labels = _labels;
+ this.initials = initials;
+ this.finals = finals;
+ this._deltaq = deltaq;
+ this._defaultq = defaultq;
+ this.qbinders = qbinders.asInstanceOf[Array[Vector]];
+ //print();
+ //System.exit(0);
+ }
+
+
+
+ var offset:Array[int] = _; // only used if constructed from multiple
+
+ def collectLabels( nfa:Array[NondetWordAutom ] ): Unit = {
+ this.labels = new HashSet();
+ var i = 0;
+ while(i < nfa.length) {
+ this.labels.addAll( nfa( i ).labels );
+ i = i + 1
+ }
+ }
+
+ def collectOffsets( nfa:Array[NondetWordAutom] ): Unit = {
+ this.offset = new Array[int]( nfa.length + 1 );
+ offset( 0 ) = 1; // we have a new initial state
+ var i = 0;
+ while(i < nfa.length ) {
+ offset( i + 1 ) = nfa( i ).nstates + offset( i );
+ i = i + 1
+ }
+ }
+
+ /** collapses several normalized NondetWordAutom objects into one.
+ */
+
+ def this( nfa: Array[NondetWordAutom] ) = {
+ this();
+ //Console.println("NWA::this(.)");
+
+ //this.m
+ val m = nfa.length;
+ //System.out.println("enter NondetWordSwitch, "
+ // +"combining " + m + " automata");
+
+ collectLabels( nfa );
+ collectOffsets( nfa );
+
+ //Console.println(" X 1");
+
+
+ this.nstates = offset( nfa.length ); //m - 1 ] + nfa[ m - 1 ].nstates;
+
+
+ this.finals = new TreeMap();
+
+ this.qbinders = new Array[Vector]( nstates );
+
+ // new initial state gets all transitions from all initial states
+
+ this._deltaq = new Array[HashMap]( nstates );
+ this._defaultq = new Array[Vector]( nstates );
+ //Console.println(" X 2");
+
+ //TreeSet defaultqSet = new TreeSet();
+ _deltaq( 0 ) = new HashMap(); // 0 = our new initial state
+
+ val initials = new TreeSet();
+
+ var i = 0;
+ while(i < m) {
+ //System.out.println("i (current NFA):"+i);
+
+ val n = nfa( i );
+
+ val offs = offset( i );
+
+ initials.add( new Integer( offs ));
+
+ n.relocate( offs,
+ this.finals,
+ this._deltaq,
+ this._defaultq,
+ this.qbinders );
+ i = i + 1;
+ }
+
+ normalize( initials, false );
+ //Console.println("Leave-NWA::this(.)");
+ }
+
+
+
+
+ def print(): Unit = {
+
+ Console.print("NFA on labels "+ this.labels);
+
+ if( offset != null ) {
+ Console.print("offset");
+ var k = 0;
+ while(k < offset.length) {
+ if( k > 0)
+ Console.print(", ");
+ Console.print(offset(k));
+ k = k + 1;
+ }
+ }
+ Console.println;
+
+ Console.print("max state number :" + (nstates - 1) );
+
+ Console.println("initials" + initials);
+
+ Console.println("finals" + finals);
+
+ var i = 0;
+ while(i < nstates) {
+ Console.print("state: " + i);
+ if( finals.containsKey( new Integer( i )) ){
+ Console.print("*"); //final
+ }
+ Console.print(" transitions: {");
+ var arrows:HashMap = deltaq( i );
+
+ var it = arrows.keySet().iterator();
+ while(it.hasNext()) {
+ val label = it.next();
+ val targets = arrows.get( label ).asInstanceOf[Vector];
+ val jt = targets.iterator();
+ while(jt.hasNext()) {
+ val p = jt.next().asInstanceOf[Integer];
+ Console.print("("+label+","+p+")");
+ }
+ }
+
+ Console.print("} ");
+ Console.print(" default transitions: "+_defaultq( i ));
+ if( null != qbinders )
+ Console.println(" binders "+qbinders( i ));
+ Console.println;
+ i = i + 1;
+ }
+ }
+
+
+}
+
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-18 15:14:40 +0000