Change the choice point stack to be a linked list

Since frames are allocated based on the size of the registers need
to be saved, there is already an object allocation occurring as each
frame is pushed. Move the stack storage into a linked list allows
the stack to efficiently grow dynamically in size to whatever size
is required by the program.

3 files changed, 136 insertions, 161 deletions

diff --git a/src/lang/CPFStack.java b/src/lang/ChoicePointFrame.java
index 4433263..e921072 100644
--- a/src/lang/CPFStack.java
+++ b/src/lang/ChoicePointFrame.java
@@ -1,21 +1,25 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+
 package com.googlecode.prolog_cafe.lang;
-import java.io.Serializable;
+
 /**
- * Choice point frame.<br>
+ * Choice point frame.
  *
  * @author Mutsunori Banbara (banbara@kobe-u.ac.jp)
  * @author Naoyuki Tamura (tamura@kobe-u.ac.jp)
  * @version 1.0
  */
-class CPFEntry implements Serializable {
-    public long timeStamp;
-    public Operation cont;  // continuation goal
-    public Operation bp;    // next clause
-    public int tr;          // trail pointer
-    public int b0;          // cut point
-
-    static CPFEntry S0(Operation cont) {
-      CPFEntry r = new CPFEntry();
+class ChoicePointFrame {
+    ChoicePointFrame prior;
+
+    long timeStamp;
+    Operation cont;  // continuation goal
+    Operation bp;    // next clause
+    int tr;          // trail pointer
+    int b0;          // cut point
+
+    static ChoicePointFrame S0(Operation cont) {
+      ChoicePointFrame r = new ChoicePointFrame();
       r.cont = cont;
       return r;
     }
@@ -25,15 +29,15 @@ class CPFEntry implements Serializable {
     }
 
     public String toString() {
-	String t = " time:" + timeStamp + "\n" ;
-	t = t + " cont:" + cont + "\n";
-	t = t + " bp:" + bp + "\n";
-	t = t + " tr:" + tr + "\n";
-	t = t + " b0:" + b0 + "\n";
-	return t;
+      String t = " time:" + timeStamp + "\n" ;
+      t = t + " cont:" + cont + "\n";
+      t = t + " bp:" + bp + "\n";
+      t = t + " tr:" + tr + "\n";
+      t = t + " b0:" + b0 + "\n";
+      return t;
     }
 
-    static final class S1 extends CPFEntry {
+    static final class S1 extends ChoicePointFrame {
       private Term areg1;
 
       S1(Prolog engine) {
@@ -47,7 +51,7 @@ class CPFEntry implements Serializable {
       }
     }
 
-    static final class S2 extends CPFEntry {
+    static final class S2 extends ChoicePointFrame {
       private Term areg1, areg2;
 
       S2(Prolog engine) {
@@ -63,7 +67,7 @@ class CPFEntry implements Serializable {
       }
     }
 
-    static final class S3 extends CPFEntry {
+    static final class S3 extends ChoicePointFrame {
       private Term areg1, areg2, areg3;
 
       S3(Prolog engine) {
@@ -81,7 +85,7 @@ class CPFEntry implements Serializable {
       }
     }
 
-    static final class S4 extends CPFEntry {
+    static final class S4 extends ChoicePointFrame {
       private Term areg1, areg2, areg3, areg4;
 
       S4(Prolog engine) {
@@ -101,7 +105,7 @@ class CPFEntry implements Serializable {
       }
     }
 
-    static final class S5 extends CPFEntry {
+    static final class S5 extends ChoicePointFrame {
       private Term areg1, areg2, areg3, areg4, areg5;
 
       S5(Prolog engine) {
@@ -123,7 +127,7 @@ class CPFEntry implements Serializable {
       }
     }
 
-    static final class S6 extends CPFEntry {
+    static final class S6 extends ChoicePointFrame {
       private Term areg1, areg2, areg3, areg4, areg5, areg6;
 
       S6(Prolog engine) {
@@ -147,7 +151,7 @@ class CPFEntry implements Serializable {
       }
     }
 
-    static final class S7 extends CPFEntry {
+    static final class S7 extends ChoicePointFrame {
       private Term areg1, areg2, areg3, areg4, areg5, areg6, areg7;
 
       S7(Prolog engine) {
@@ -173,7 +177,7 @@ class CPFEntry implements Serializable {
       }
     }
 
-    static class S8 extends CPFEntry {
+    static class S8 extends ChoicePointFrame {
       private Term areg1, areg2, areg3, areg4, areg5, areg6, areg7, areg8;
 
       S8(Prolog engine) {
@@ -216,120 +220,3 @@ class CPFEntry implements Serializable {
       }
     }
 }
-
-/**
- * Choice point frame stack.<br>
- * The <code>CPFStack</code> class represents a stack
- * of choice point frames.<br>
- * Each choice point frame has the following fields:
- * <ul>
- * <li><em>arguments</em>
- * <li><em>continuation goal</em>
- * <li><em>next clause</em>
- * <li><em>trail pointer</em>
- * <li><em>cut point</em>
- * <li><em>time stamp</em>
- * </ul>
- *
- * @author Mutsunori Banbara (banbara@kobe-u.ac.jp)
- * @author Naoyuki Tamura (tamura@kobe-u.ac.jp)
- * @version 1.0
- */
-public class CPFStack implements Serializable {
-    /** Maximum size of enties. Initial size is <code>20000</code>. */
-    protected int maxContents = 20000;
-
-    /** An array of choice point frames. */
-    protected CPFEntry[] buffer;
-
-    /** the top index of this <code>CPFStack</code>. */
-    protected int top;
-
-    /** Holds the Prolog engine that this <code>CPFStack</code> belongs to. */
-    protected Prolog engine;
-	
-    /** Constructs a new choice point frame stack. */
-    public CPFStack(Prolog _engine) {
-	engine = _engine;
-	buffer = new CPFEntry[maxContents];
-	top = -1;
-    }
-
-    /** Constructs a new choice point frame stack with the given size. */
-    public CPFStack(Prolog _engine, int n) {
-	engine = _engine;
-	maxContents = n;
-	buffer = new CPFEntry[maxContents];
-	top = -1;
-    }
-
-    /** Create a new choice point frame.
-     * @param entry <em>entry to save</em>
-     */
-    void push(CPFEntry entry){
-	try {
-	    buffer[++top] = entry;
-	} catch (ArrayIndexOutOfBoundsException e) {
-	    System.out.println("{expanding choice point stack...}");
-	    int len = buffer.length;
-	    CPFEntry[] new_buffer = new CPFEntry[len+10000];
-	    for(int i=0; i<len; i++) {
-		new_buffer[i] = buffer[i];
-	    }
-	    buffer = new_buffer;
-	    buffer[top] = entry;
-	    maxContents = len+10000;
-	}
-    }
-
-    /** Discards all choice points. */
-    public void deleteAll() { 
-	while (! empty()) {
-	    buffer[top--] = null;
-	}
-    }
-
-    /** Discards all choice points after the value of <code>i</code>. */
-    public void cut(int i) {
-	while (top > i) {
-	    buffer[top--] = null;
-	}
-    }
-
-    /** Discards the top of choice points. */
-    public void delete() { buffer[top--] = null; }
-
-    /** Discards all choice points. */
-    public void init() { deleteAll(); }
-
-    /** Tests if this stack has no entry. */
-    public boolean empty() { return top == -1; }
-
-    /** Returns the value of <code>top</code>. 
-     * @see #top
-     */
-    public int top() { return top; }
-
-    /** Returns the value of <code>maxContents</code>. 
-     * @see #maxContents
-     */
-    public int max() { return maxContents; }
-
-    CPFEntry topEntry() { return buffer[top]; }
-    void restore() { buffer[top].restore(engine); }
-
-    /** Returns the <em>time stamp</em> of current choice point frame. */
-    public long getTimeStamp() { return buffer[top].timeStamp; }
-    
-    /** Shows the contents of this <code>CPFStack</code>. */
-    public void show() {
-	if (empty()) {
-	    System.out.println("{choice point stack is empty!}");
-	    return;
-	}
-	for (int i=0; i<=top; i++) {
-	    System.out.print("stack[" + i + "]: ");
-	    System.out.println(buffer[i]);
-	}
-    }
-}
diff --git a/src/lang/ChoicePointStack.java b/src/lang/ChoicePointStack.java
new file mode 100644
index 0000000..9989cf0
--- /dev/null
+++ b/src/lang/ChoicePointStack.java
@@ -0,0 +1,88 @@
+package com.googlecode.prolog_cafe.lang;
+
+/**
+ * Choice point frame stack.<br>
+ * The <code>CPFStack</code> class represents a stack of choice point frames.<br>
+ * Each choice point frame has the following fields:
+ * <ul>
+ * <li><em>arguments</em>
+ * <li><em>continuation goal</em>
+ * <li><em>next clause</em>
+ * <li><em>trail pointer</em>
+ * <li><em>cut point</em>
+ * <li><em>time stamp</em>
+ * </ul>
+ *
+ * @author Mutsunori Banbara (banbara@kobe-u.ac.jp)
+ * @author Naoyuki Tamura (tamura@kobe-u.ac.jp)
+ * @version 1.0
+ */
+public final class ChoicePointStack {
+  /** Top of the stack. */
+  ChoicePointFrame top;
+
+  /**
+   * Current level/depth of the stack.
+   * <p>
+   * This matches the length of the chain stored in {@link #top}.
+   */
+  private int level = -1;
+
+  /**
+   * Create a new choice point frame.
+   *
+   * @param entry <em>entry to save</em>
+   */
+  void push(ChoicePointFrame entry) {
+    entry.prior = top;
+    top = entry;
+    level++;
+  }
+
+  /** Discards all choice points after the value of <code>i</code>. */
+  public void cut(int i) {
+    while (level > i) {
+      top = top.prior;
+      level--;
+    }
+  }
+
+  /** Discards the top of choice points. */
+  void delete() {
+    top = top.prior;
+    level--;
+  }
+
+  /** Discards all choice points. */
+  void init() {
+    top = null;
+    level = -1;
+  }
+
+  /** Get the current top of the stack. */
+  public int top() {
+    return level;
+  }
+
+  /** Get the maximum number of choice points permitted on the stack. */
+  public int max() {
+    // Since the stack is represented as a linked list, there is no limit.
+    return Integer.MAX_VALUE;
+  }
+
+  /** Returns the <em>time stamp</em> of current choice point frame. */
+  public long getTimeStamp() {
+    return top.timeStamp;
+  }
+
+  /** Shows the contents of this <code>CPFStack</code>. */
+  public void show() {
+    if (top == null) {
+      System.out.println("{choice point stack is empty!}");
+      return;
+    }
+    for (ChoicePointFrame e = top; e != null; e = e.prior) {
+      System.out.println(e);
+    }
+  }
+}
diff --git a/src/lang/Prolog.java b/src/lang/Prolog.java
index e3ccad1..bb90140 100644
--- a/src/lang/Prolog.java
+++ b/src/lang/Prolog.java
@@ -17,7 +17,7 @@ public class Prolog implements Serializable {
     /** Continuation goal register */
     public Operation cont;
     /** Choice point frame stack */
-    public CPFStack stack;
+    public final ChoicePointStack stack;
     /** Trail stack */
     public Trail trail;
     /** Cut pointer */
@@ -112,7 +112,7 @@ public class Prolog implements Serializable {
     public Prolog(PrologControl c) { 
 	control    = c;
 	cont       = null;
-	stack      = new CPFStack(this);
+	stack      = new ChoicePointStack();
 	trail      = new Trail(this);
     }
 
@@ -166,7 +166,7 @@ public class Prolog implements Serializable {
 	CPFTimeStamp = Long.MIN_VALUE;
 
 	// Creates an initial choice point frame.
-	CPFEntry initialFrame = CPFEntry.S0(null);
+	ChoicePointFrame initialFrame = ChoicePointFrame.S0(null);
 	initialFrame.b0 = B0;
 	initialFrame.bp = Failure.FAILURE;
 	initialFrame.tr = trail.top();
@@ -192,7 +192,7 @@ public class Prolog implements Serializable {
 	currentOutput = userOutput;
     }
 
-    /** Sets the top of choice porint stack to <code>B0</code> (cut pointer). */
+    /** Sets B0 to the top of the choice point stack.. */
     public void setB0()    { B0 = stack.top(); }
 
     /** Discards all choice points after the value of <code>i</code>. */
@@ -255,7 +255,7 @@ public class Prolog implements Serializable {
      * and returns the backtrak point in current choice point.
      */
     public Operation fail() {
-	CPFEntry top = stack.topEntry();
+	ChoicePointFrame top = stack.top;
 	B0 = top.b0;     // restore B0
 	return top.bp;   // execute next clause
     }
@@ -327,24 +327,24 @@ public class Prolog implements Serializable {
 
     /** Restores the argument registers and continuation goal register from the current choice point frame. */
     public void restore() {
-      stack.restore();
+      stack.top.restore(this);
     }
 
     /** Creates a new choice point frame. */
-    public Operation jtry0(Operation p, Operation next) { return finishjtry(p, next, CPFEntry.S0(cont)); }
-    public Operation jtry1(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S1(this)); }
-    public Operation jtry2(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S2(this)); }
-    public Operation jtry3(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S3(this)); }
-    public Operation jtry4(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S4(this)); }
-    public Operation jtry5(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S5(this)); }
-    public Operation jtry6(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S6(this)); }
-    public Operation jtry7(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S7(this)); }
-    public Operation jtry8(Operation p, Operation next) { return finishjtry(p, next, new CPFEntry.S8(this)); }
+    public Operation jtry0(Operation p, Operation next) { return finishjtry(p, next, ChoicePointFrame.S0(cont)); }
+    public Operation jtry1(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S1(this)); }
+    public Operation jtry2(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S2(this)); }
+    public Operation jtry3(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S3(this)); }
+    public Operation jtry4(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S4(this)); }
+    public Operation jtry5(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S5(this)); }
+    public Operation jtry6(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S6(this)); }
+    public Operation jtry7(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S7(this)); }
+    public Operation jtry8(Operation p, Operation next) { return finishjtry(p, next, new ChoicePointFrame.S8(this)); }
     public Operation jtry(int arity, Operation p, Operation next) {
-	return finishjtry(p, next, new CPFEntry.S9(arity, this));
+	return finishjtry(p, next, new ChoicePointFrame.S9(arity, this));
     }
 
-    private Operation finishjtry(Operation p, Operation next, CPFEntry entry) {
+    private Operation finishjtry(Operation p, Operation next, ChoicePointFrame entry) {
       entry.b0 = B0;
       entry.bp = next;
       entry.tr = trail.top();
@@ -360,7 +360,7 @@ public class Prolog implements Serializable {
      */
     public Operation retry(Operation p, Operation next) {
 	restore();
-	CPFEntry top = stack.topEntry();
+	ChoicePointFrame top = stack.top;
 	trail.unwind(top.tr);
 	top.bp = next;
 	return p;
@@ -372,7 +372,7 @@ public class Prolog implements Serializable {
      */
     public Operation trust(Operation p) {
 	restore();
-	trail.unwind(stack.topEntry().tr);
+	trail.unwind(stack.top.tr);
 	stack.delete();
 	return p;
     }