projects
/
sbp.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (from parent 1:
14b3d2e
)
rename Node->StateNode
author
adam
<adam@megacz.com>
Mon, 5 Nov 2007 02:39:15 +0000
(21:39 -0500)
committer
adam
<adam@megacz.com>
Mon, 5 Nov 2007 02:39:15 +0000
(21:39 -0500)
darcs-hash:
20071105023915
-5007d-
a1bdc50cb5c65bb1ca10dd55f93c4aef2ad01f82
.gz
src/edu/berkeley/sbp/Forest.java
patch
|
blob
|
history
src/edu/berkeley/sbp/GSS.java
patch
|
blob
|
history
src/edu/berkeley/sbp/ParseFailed.java
patch
|
blob
|
history
src/edu/berkeley/sbp/Parser.java
patch
|
blob
|
history
src/edu/berkeley/sbp/Reduction.java
patch
|
blob
|
history
src/edu/berkeley/sbp/Result.java
patch
|
blob
|
history
src/edu/berkeley/sbp/StateNode.java
[moved from
src/edu/berkeley/sbp/Node.java
with 90% similarity]
patch
|
blob
|
history
src/edu/berkeley/sbp/util/GraphViz.java
patch
|
blob
|
history
src/edu/berkeley/sbp/util/PrintableTree.java
patch
|
blob
|
history
diff --git
a/src/edu/berkeley/sbp/Forest.java
b/src/edu/berkeley/sbp/Forest.java
index
e39a8f6
..
636ad4f
100644
(file)
--- a/
src/edu/berkeley/sbp/Forest.java
+++ b/
src/edu/berkeley/sbp/Forest.java
@@
-37,7
+37,7
@@
public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
abstract void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus);
abstract void gather(HashSet<Forest<NodeType>> ignore);
abstract void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus);
abstract void gather(HashSet<Forest<NodeType>> ignore);
- abstract void edges(GraphViz.Node n);
+ abstract void edges(GraphViz.StateNode n);
boolean ambiguous() { return false; }
// One //////////////////////////////////////////////////////////////////////////////
boolean ambiguous() { return false; }
// One //////////////////////////////////////////////////////////////////////////////
@@
-97,16
+97,16
@@
public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
public boolean isTransparent() { return false; }
public boolean isHidden() { return false; }
public boolean isTransparent() { return false; }
public boolean isHidden() { return false; }
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = headToString()==null?"":headToString();
n.directed = true;
edges(n);
return n;
}
boolean edges = false; // FIXME ??
n.label = headToString()==null?"":headToString();
n.directed = true;
edges(n);
return n;
}
boolean edges = false; // FIXME ??
- public void edges(GraphViz.Node n) {
+ public void edges(GraphViz.StateNode n) {
if (edges) return;
edges = true;
for(int i=0; i<children.length; i++) {
if (edges) return;
edges = true;
for(int i=0; i<children.length; i++) {
@@
-210,14
+210,14
@@
public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
public boolean isTransparent() { return hp.size()==1; }
public boolean isHidden() { return hp.size()==0; }
public boolean isTransparent() { return hp.size()==1; }
public boolean isHidden() { return hp.size()==0; }
- public void edges(GraphViz.Node n) {
+ public void edges(GraphViz.StateNode n) {
if (hp.size()==1) { hp.iterator().next().edges(n); return; }
for(Forest f : hp) f.edges(n);
}
if (hp.size()==1) { hp.iterator().next().edges(n); return; }
for(Forest f : hp) f.edges(n);
}
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
if (gv.hasNode(this)) return gv.createNode(this);
if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = "?";
n.color = "red";
for(Forest f : hp) n.edge(f, null);
n.label = "?";
n.color = "red";
for(Forest f : hp) n.edge(f, null);
diff --git
a/src/edu/berkeley/sbp/GSS.java
b/src/edu/berkeley/sbp/GSS.java
index
7626b4e
..
db833b9
100644
(file)
--- a/
src/edu/berkeley/sbp/GSS.java
+++ b/
src/edu/berkeley/sbp/GSS.java
@@
-27,7
+27,7
@@
class GSS {
int numReductions = 0;
/** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
int numReductions = 0;
/** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
- class Phase<Tok> implements Invokable<State, Node, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
+ class Phase<Tok> implements Invokable<State, StateNode, Forest>, IntegerMappable, GraphViz.ToGraphViz, Iterable<StateNode> {
// FIXME: right now, these are the performance bottleneck
private HashMapBag<Integer,Integer> performed = new HashMapBag<Integer,Integer>();
// FIXME: right now, these are the performance bottleneck
private HashMapBag<Integer,Integer> performed = new HashMapBag<Integer,Integer>();
@@
-42,7
+42,7
@@
class GSS {
reductionQueue.add(r);
}
reductionQueue.add(r);
}
- public void invoke(State st, Node pred, Forest f) {
+ public void invoke(State st, StateNode pred, Forest f) {
parser.spin();
good |= next.newNode(f, null, pred, st, false);
}
parser.spin();
good |= next.newNode(f, null, pred, st, false);
}
@@
-50,7
+50,7
@@
class GSS {
/** the token immediately after this phase */
final Tok token;
final int pos;
/** the token immediately after this phase */
final Tok token;
final int pos;
- public IntPairMap<Node> hash = new IntPairMap<Node>(); /* ALLOC */
+ public IntPairMap<StateNode> hash = new IntPairMap<StateNode>(); /* ALLOC */
private boolean good = false;
private Phase next = null;
private Phase prev;
private boolean good = false;
private Phase next = null;
private Phase prev;
@@
-125,13
+125,13
@@
class GSS {
this.next = next;
// this massively improves GC performance
if (prev != null) {
this.next = next;
// this massively improves GC performance
if (prev != null) {
- IntPairMap<Node> h = prev.hash;
+ IntPairMap<StateNode> h = prev.hash;
prev.hash = null;
prev.performed = null;
prev.hash = null;
prev.performed = null;
- for(Node n : h) n.check();
+ for(StateNode n : h) n.check();
}
numOldNodes = hash.size();
}
numOldNodes = hash.size();
- for(Node n : hash.values()) {
+ for(StateNode n : hash.values()) {
if (token == null && n.state().isAccepting()) {
if (finalResult==null) finalResult = new Forest.Many();
for(Result r : n)
if (token == null && n.state().isAccepting()) {
if (finalResult==null) finalResult = new Forest.Many();
for(Result r : n)
@@
-160,14
+160,14
@@
class GSS {
if (token==null && finalResult==null)
ParseFailed.error("unexpected end of file", this, null,
getLocation().createRegion(getLocation()));
if (token==null && finalResult==null)
ParseFailed.error("unexpected end of file", this, null,
getLocation().createRegion(getLocation()));
- for(Node n : hash) n.check();
+ for(StateNode n : hash) n.check();
}
Input.Region getRegionFromThisToNext() {
return getLocation().createRegion(getNextLocation());
}
}
Input.Region getRegionFromThisToNext() {
return getLocation().createRegion(getNextLocation());
}
- void newNodeFromReduction(Forest f, Pos reduction, Node pred) {
+ void newNodeFromReduction(Forest f, Pos reduction, StateNode pred) {
int pos = pred.phase().pos;
for(int s : reduction.hates())
if (performed.contains(pos, s))
int pos = pred.phase().pos;
for(int s : reduction.hates())
if (performed.contains(pos, s))
@@
-189,8
+189,8
@@
class GSS {
* @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
* @param start the earliest part of the input contributing to this node (used to make merging decisions)
*/
* @param fromEmptyReduction true iff this node is being created as a result of a reduction of length zero (see GRMLR paper)
* @param start the earliest part of the input contributing to this node (used to make merging decisions)
*/
- private boolean newNode(Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) {
- Node p = pred==null ? null : hash.get(state, pred.phase());
+ private boolean newNode(Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
+ StateNode p = pred==null ? null : hash.get(state, pred.phase());
if (p != null) {
p.addResult(f, reduction, pred);
return !state.doomed();
if (p != null) {
p.addResult(f, reduction, pred);
return !state.doomed();
@@
-201,7
+201,7
@@
class GSS {
if (token==null) break;
if (!state.canReduce(token)) return false;
} while(false);
if (token==null) break;
if (!state.canReduce(token)) return false;
} while(false);
- Node n = new Node(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC
+ StateNode n = new StateNode(Phase.this, f, reduction, pred, state, fromEmptyReduction); // ALLOC
/** FIXME: this null-result can be used to notice bogus/dead states */
for(Object s : state.conjunctStates)
newNode(null, null, n, (State)s, fromEmptyReduction);
/** FIXME: this null-result can be used to notice bogus/dead states */
for(Object s : state.conjunctStates)
newNode(null, null, n, (State)s, fromEmptyReduction);
@@
-212,12
+212,12
@@
class GSS {
public int size() { return hash==null ? 0 : hash.size(); }
public int pos() { return pos; }
public Tok getToken() { return token; }
public int size() { return hash==null ? 0 : hash.size(); }
public int pos() { return pos; }
public Tok getToken() { return token; }
- public Iterator<Node> iterator() { return hash.iterator(); }
+ public Iterator<StateNode> iterator() { return hash.iterator(); }
public GSS getGSS() { return GSS.this; }
// GraphViz //////////////////////////////////////////////////////////////////////////////
public GSS getGSS() { return GSS.this; }
// GraphViz //////////////////////////////////////////////////////////////////////////////
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
GraphViz.Group g = gv.createGroup(this);
g.label = "Phase " + pos;
if (gv.hasNode(this)) return gv.createNode(this);
GraphViz.Group g = gv.createGroup(this);
g.label = "Phase " + pos;
@@
-233,7
+233,7
@@
class GSS {
PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
GraphViz gv = new GraphViz();
for(Object n : this)
PrintWriter p = new PrintWriter(new OutputStreamWriter(fos));
GraphViz gv = new GraphViz();
for(Object n : this)
- ((Node)n).toGraphViz(gv);
+ ((StateNode)n).toGraphViz(gv);
gv.dump(p);
p.flush();
p.close();
gv.dump(p);
p.flush();
p.close();
diff --git
a/src/edu/berkeley/sbp/ParseFailed.java
b/src/edu/berkeley/sbp/ParseFailed.java
index
7a3416e
..
872ffac
100644
(file)
--- a/
src/edu/berkeley/sbp/ParseFailed.java
+++ b/
src/edu/berkeley/sbp/ParseFailed.java
@@
-5,7
+5,7
@@
import edu.berkeley.sbp.*;
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.GSS.Phase;
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.GSS.Phase;
-import edu.berkeley.sbp.Node;
+import edu.berkeley.sbp.StateNode;
import edu.berkeley.sbp.util.*;
import java.io.*;
import java.util.*;
import edu.berkeley.sbp.util.*;
import java.io.*;
import java.util.*;
@@
-47,23
+47,23
@@
public class ParseFailed extends Exception {
return (c >= 'A' && c <= 'Z');
}
return (c >= 'A' && c <= 'Z');
}
- static <Tok> void barf(HashMap<Element,Input.Location> sb, Node n, int indent, boolean skip, int count, Input.Location loc) {
+ static <Tok> void barf(HashMap<Element,Input.Location> sb, StateNode n, int indent, boolean skip, int count, Input.Location loc) {
if (count <= 0) {
barf(sb, n, indent, skip, loc);
} else {
/*
FIXME: removed
if (count <= 0) {
barf(sb, n, indent, skip, loc);
} else {
/*
FIXME: removed
- for(Node nn : (Iterable<Node>)n.parents())
+ for(StateNode nn : (Iterable<StateNode>)n.parents())
barf(sb, nn, indent, skip, count-1, n.phase().getLocation());
*/
}
}
barf(sb, nn, indent, skip, count-1, n.phase().getLocation());
*/
}
}
- static <Tok> void barf(HashMap<Element,Input.Location> sb, Node n, int indent, boolean skip, Input.Location loc) {
+ static <Tok> void barf(HashMap<Element,Input.Location> sb, StateNode n, int indent, boolean skip, Input.Location loc) {
if (touched.contains(n)) return;
touched.add(n);
String s = "";
for(int i=0; i< indent; i++) s += " ";
if (touched.contains(n)) return;
touched.add(n);
String s = "";
for(int i=0; i< indent; i++) s += " ";
- Node parent = n;
+ StateNode parent = n;
boolean done = false;
boolean alldone = false;
boolean go = false;
boolean done = false;
boolean alldone = false;
boolean go = false;
@@
-102,8
+102,8
@@
public class ParseFailed extends Exception {
// FIXME
// FIXME
- private static HashSet<Node> touched = new HashSet<Node>();
- static <Tok> void complain(Node n, HashMap<String,HashSet<String>> errors, boolean force, int indent) {
+ private static HashSet<StateNode> touched = new HashSet<StateNode>();
+ static <Tok> void complain(StateNode n, HashMap<String,HashSet<String>> errors, boolean force, int indent) {
if (touched.contains(n)) return;
touched.add(n);
for(Pos p : (Iterable<Pos>)n.state()) {
if (touched.contains(n)) return;
touched.add(n);
for(Pos p : (Iterable<Pos>)n.state()) {
@@
-112,7
+112,7
@@
public class ParseFailed extends Exception {
!important(p)) {
/*
FIXME: removed
!important(p)) {
/*
FIXME: removed
- for(Node n2 : n.parents())
+ for(StateNode n2 : n.parents())
complain(n2, errors, force
//| p.isFirst()
, indent);
complain(n2, errors, force
//| p.isFirst()
, indent);
@@
-150,7
+150,7
@@
public class ParseFailed extends Exception {
}
private static void error(String message,
Object token,
}
private static void error(String message,
Object token,
- Iterable<Node> nodes,
+ Iterable<StateNode> nodes,
Input.Region region,
Input input,
GSS gss) throws ParseFailed{
Input.Region region,
Input input,
GSS gss) throws ParseFailed{
@@
-184,7
+184,7
@@
public class ParseFailed extends Exception {
*/
}
HashMap<Element,Input.Location> hm = new HashMap<Element,Input.Location>();
*/
}
HashMap<Element,Input.Location> hm = new HashMap<Element,Input.Location>();
- for(Node no : nodes)
+ for(StateNode no : nodes)
barf(hm, no, 0, false, region.getStart());
ret.append("\n expected: ");
Set<Element> hs = hm.keySet();
barf(hm, no, 0, false, region.getStart());
ret.append("\n expected: ");
Set<Element> hs = hm.keySet();
@@
-207,7
+207,7
@@
public class ParseFailed extends Exception {
/*
ret.append("\n The author of SBP apologizes for the these nearly-useless error messages:\n\n");
HashMap<String,HashSet<String>> errors = new HashMap<String,HashSet<String>>();
/*
ret.append("\n The author of SBP apologizes for the these nearly-useless error messages:\n\n");
HashMap<String,HashSet<String>> errors = new HashMap<String,HashSet<String>>();
- for(Node n : nodes) {
+ for(StateNode n : nodes) {
//System.out.println(n.state);
complain(n, errors, false, 0);
}
//System.out.println(n.state);
complain(n, errors, false, 0);
}
diff --git
a/src/edu/berkeley/sbp/Parser.java
b/src/edu/berkeley/sbp/Parser.java
index
95e3ba5
..
e5cd67c
100644
(file)
--- a/
src/edu/berkeley/sbp/Parser.java
+++ b/
src/edu/berkeley/sbp/Parser.java
@@
-296,7
+296,7
@@
public abstract class Parser<Token, NodeType> implements Serializable {
* possible from it
*
* A state corresponds to a set of Sequence.Pos's. Each
* possible from it
*
* A state corresponds to a set of Sequence.Pos's. Each
- * Node in the GSS has a State; the Node represents a set of
+ * StateNode in the GSS has a State; the StateNode represents a set of
* possible parses, one for each Pos in the State.
*
* Every state is either "doomed" or "normal". If a Pos
* possible parses, one for each Pos in the State.
*
* Every state is either "doomed" or "normal". If a Pos
@@
-311,10
+311,10
@@
public abstract class Parser<Token, NodeType> implements Serializable {
* Nodes with non-doomed states represent nodes which
* contribute to actual valid parses. Nodes with doomed
* States exist for no other purpose than to enable/disable
* Nodes with non-doomed states represent nodes which
* contribute to actual valid parses. Nodes with doomed
* States exist for no other purpose than to enable/disable
- * some future reduction from a non-doomed Node. Because of
+ * some future reduction from a non-doomed StateNode. Because of
* this, we "garbage-collect" Nodes with doomed states if
* there are no more non-doomed Nodes which they could
* this, we "garbage-collect" Nodes with doomed states if
* there are no more non-doomed Nodes which they could
- * affect (see Result, Reduction, and Node for details).
+ * affect (see Result, Reduction, and StateNode for details).
*
* Without this optimization, many seemingly-innocuous uses
* of positive and negative conjuncts can trigger O(n^2)
*
* Without this optimization, many seemingly-innocuous uses
* of positive and negative conjuncts can trigger O(n^2)
@@
-347,14
+347,14
@@
public abstract class Parser<Token, NodeType> implements Serializable {
Iterable<Pos> positions() { return hs; }
boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
Iterable<Pos> positions() { return hs; }
boolean canShift(Token t) { return oshifts!=null && oshifts.contains(t); }
- void invokeShifts(Token t, GSS.Phase phase, Node pred, Forest f) { oshifts.invoke(t, phase, pred, f); }
+ void invokeShifts(Token t, GSS.Phase phase, StateNode pred, Forest f) { oshifts.invoke(t, phase, pred, f); }
boolean canReduce(Token t) {
return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
boolean canReduce(Token t) {
return oreductions != null && (t==null ? eofReductions.size()>0 : oreductions.contains(t)); }
- void invokeEpsilonReductions(Token t, Node node) {
+ void invokeEpsilonReductions(Token t, StateNode node) {
if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null);
else oreductions.invoke(t, node, null, null);
}
if (t==null) for(Pos r : eofReductions) node.invoke(r, null, null);
else oreductions.invoke(t, node, null, null);
}
- void invokeReductions(Token t, Node node, Result b) {
+ void invokeReductions(Token t, StateNode node, Result b) {
if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null);
else oreductions.invoke(t, node, b, null);
}
if (t==null) for(Pos r : eofReductions) node.invoke(r, b, null);
else oreductions.invoke(t, node, b, null);
}
diff --git
a/src/edu/berkeley/sbp/Reduction.java
b/src/edu/berkeley/sbp/Reduction.java
index
222a168
..
0266782
100644
(file)
--- a/
src/edu/berkeley/sbp/Reduction.java
+++ b/
src/edu/berkeley/sbp/Reduction.java
@@
-9,9
+9,9
@@
final class Reduction implements Comparable<Reduction> {
private Pos reduction;
private GSS.Phase phase;
private Forest forest;
private Pos reduction;
private GSS.Phase phase;
private Forest forest;
- private Node pred;
+ private StateNode pred;
- public Reduction(Node pred, Pos reduction, Forest forest, GSS.Phase target) {
+ public Reduction(StateNode pred, Pos reduction, Forest forest, GSS.Phase target) {
this.reduction = reduction;
this.forest = forest;
this.phase = target;
this.reduction = reduction;
this.forest = forest;
this.phase = target;
diff --git
a/src/edu/berkeley/sbp/Result.java
b/src/edu/berkeley/sbp/Result.java
index
c91ab76
..
dfe12bb
100644
(file)
--- a/
src/edu/berkeley/sbp/Result.java
+++ b/
src/edu/berkeley/sbp/Result.java
@@
-6,20
+6,21
@@
import edu.berkeley.sbp.Sequence.Pos;
import edu.berkeley.sbp.Sequence.Pos;
import java.util.*;
import edu.berkeley.sbp.Sequence.Pos;
import java.util.*;
-final class Result implements GraphViz.ToGraphViz {
+final class Result
+ implements GraphViz.ToGraphViz {
private Forest.Many f = new Forest.Many();
private Forest.Many f = new Forest.Many();
- //private HashSet<Node> predecessors = new HashSet<Node>();
- //private HashSet<Node> successors = new HashSet<Node>();
- private FastSet<Node> predecessors = new FastSet<Node>();
- private FastSet<Node> successors = new FastSet<Node>();
+ //private HashSet<StateNode> predecessors = new HashSet<StateNode>();
+ //private HashSet<StateNode> successors = new HashSet<StateNode>();
+ private FastSet<StateNode> predecessors = new FastSet<StateNode>();
+ private FastSet<StateNode> successors = new FastSet<StateNode>();
private boolean destroyed = false;
private boolean primordeal;
private int usedByNonDoomedNode = 0;
private Pos reduction;
private GSS.Phase predPhase;
private boolean destroyed = false;
private boolean primordeal;
private int usedByNonDoomedNode = 0;
private Pos reduction;
private GSS.Phase predPhase;
- public boolean predecessorsContains(Node n) {
+ public boolean predecessorsContains(StateNode n) {
return predecessors.contains(n);
}
public Pos reduction() { return reduction; }
return predecessors.contains(n);
}
public Pos reduction() { return reduction; }
@@
-37,14
+38,14
@@
final class Result implements GraphViz.ToGraphViz {
public GSS.Phase phase() { return predPhase; }
public Forest getForest() { return f; }
public GSS.Phase phase() { return predPhase; }
public Forest getForest() { return f; }
- public Iterable<Node> getPreds() { return predecessors; }
- public void addSucc(Node succ) {
+ public Iterable<StateNode> getPreds() { return predecessors; }
+ public void addSucc(StateNode succ) {
if (successors.contains(succ)) return;
successors.add(succ);
usedByNonDoomedNode += succ.state().doomed ? 0 : 1;
if (predecessors.size() > 1) throw new Error();
}
if (successors.contains(succ)) return;
successors.add(succ);
usedByNonDoomedNode += succ.state().doomed ? 0 : 1;
if (predecessors.size() > 1) throw new Error();
}
- public void removeSucc(Node succ) {
+ public void removeSucc(StateNode succ) {
if (!successors.contains(succ)) return;
successors.remove(succ);
usedByNonDoomedNode -= succ.state().doomed ? 0 : 1;
if (!successors.contains(succ)) return;
successors.remove(succ);
usedByNonDoomedNode -= succ.state().doomed ? 0 : 1;
@@
-65,14
+66,14
@@
final class Result implements GraphViz.ToGraphViz {
if (primordeal) return; // never destroy the "primordeal" result
destroyed = true;
while(predecessors.size() > 0)
if (primordeal) return; // never destroy the "primordeal" result
destroyed = true;
while(predecessors.size() > 0)
- for(Node pred : predecessors) {
+ for(StateNode pred : predecessors) {
removePred(pred);
pred.removeSucc(this);
break;
}
predecessors = null;
while(successors.size() > 0)
removePred(pred);
pred.removeSucc(this);
break;
}
predecessors = null;
while(successors.size() > 0)
- for(Node succ : successors) {
+ for(StateNode succ : successors) {
removeSucc(succ);
succ.removeResult(this);
break;
removeSucc(succ);
succ.removeResult(this);
break;
@@
-80,13
+81,13
@@
final class Result implements GraphViz.ToGraphViz {
successors = null;
}
successors = null;
}
- public void removePred(Node pred) {
+ public void removePred(StateNode pred) {
if (!predecessors.contains(pred)) return;
predecessors.remove(pred);
check();
}
if (!predecessors.contains(pred)) return;
predecessors.remove(pred);
check();
}
- public void addPred(Node pred) {
+ public void addPred(StateNode pred) {
if (predPhase==null) predPhase = pred.phase();
if (predPhase != pred.phase()) throw new Error();
predecessors.add(pred);
if (predPhase==null) predPhase = pred.phase();
if (predPhase != pred.phase()) throw new Error();
predecessors.add(pred);
@@
-98,7
+99,7
@@
final class Result implements GraphViz.ToGraphViz {
this(null, null, null);
this.primordeal = true;
}
this(null, null, null);
this.primordeal = true;
}
- public Result(Forest f, Pos reduction, Node pred) {
+ public Result(Forest f, Pos reduction, StateNode pred) {
this.f.merge(f);
this.reduction = reduction;
if (pred != null) addPred(pred);
this.f.merge(f);
this.reduction = reduction;
if (pred != null) addPred(pred);
@@
-106,9
+107,9
@@
final class Result implements GraphViz.ToGraphViz {
// GraphViz //////////////////////////////////////////////////////////////////////////////
// GraphViz //////////////////////////////////////////////////////////////////////////////
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = ""+f;
n.shape = "rectangle";
//if (pred()!=null) n.edge(pred, "");
n.label = ""+f;
n.shape = "rectangle";
//if (pred()!=null) n.edge(pred, "");
diff --git
a/src/edu/berkeley/sbp/Node.java
b/src/edu/berkeley/sbp/StateNode.java
similarity index 90%
rename from
src/edu/berkeley/sbp/Node.java
rename to
src/edu/berkeley/sbp/StateNode.java
index
8353384
..
8fb1fd7
100644
(file)
--- a/
src/edu/berkeley/sbp/Node.java
+++ b/
src/edu/berkeley/sbp/StateNode.java
@@
-11,13
+11,13
@@
import java.util.*;
import java.lang.reflect.*;
/** a node in the GSS */
import java.lang.reflect.*;
/** a node in the GSS */
-final class Node
+final class StateNode
implements Invokable<Pos, Result, Object>,
IntegerMappable,
GraphViz.ToGraphViz,
Iterable<Result> {
implements Invokable<Pos, Result, Object>,
IntegerMappable,
GraphViz.ToGraphViz,
Iterable<Result> {
- /** which GSS.Phase this Node belongs to */
+ /** which GSS.Phase this StateNode belongs to */
public GSS.Phase phase() { return phase; }
public Iterator<Result> iterator() { return results.iterator(); }
public Parser.Table.State state() { return state; }
public GSS.Phase phase() { return phase; }
public Iterator<Result> iterator() { return results.iterator(); }
public Parser.Table.State state() { return state; }
@@
-85,11
+85,11
@@
final class Node
private void reduce(Pos r, int pos, GSS.Phase target, Result only) {
for(Result res : results)
if (only == null || res == only)
private void reduce(Pos r, int pos, GSS.Phase target, Result only) {
for(Result res : results)
if (only == null || res == only)
- for(Node pred : res.getPreds())
+ for(StateNode pred : res.getPreds())
reduce2(r, pos, target, pred, res.getForest());
}
reduce2(r, pos, target, pred, res.getForest());
}
- void reduce2(Pos r, int pos, GSS.Phase target, Node pred, Forest f) {
+ void reduce2(Pos r, int pos, GSS.Phase target, StateNode pred, Forest f) {
Forest[] holder = r.holder;
Forest old = pos >= holder.length ? null : holder[pos];
if (pos < holder.length) holder[pos] = f;
Forest[] holder = r.holder;
Forest old = pos >= holder.length ? null : holder[pos];
if (pos < holder.length) holder[pos] = f;
@@
-101,10
+101,10
@@
final class Node
if (pos < holder.length) holder[pos] = old;
}
if (pos < holder.length) holder[pos] = old;
}
- Node(GSS.Phase phase, Forest f, Pos reduction, Node pred, State state, boolean fromEmptyReduction) {
+ StateNode(GSS.Phase phase, Forest f, Pos reduction, StateNode pred, State state, boolean fromEmptyReduction) {
this(phase, new Result(f, reduction, pred), state, fromEmptyReduction);
}
this(phase, new Result(f, reduction, pred), state, fromEmptyReduction);
}
- Node(GSS.Phase phase, Result pred, State state, boolean fromEmptyReduction) {
+ StateNode(GSS.Phase phase, Result pred, State state, boolean fromEmptyReduction) {
this.phase = phase;
this.state = state;
this.fromEmptyReduction = fromEmptyReduction;
this.phase = phase;
this.state = state;
this.fromEmptyReduction = fromEmptyReduction;
@@
-133,7
+133,7
@@
final class Node
public void addSucc(Result succ) {
successors.add(succ);
}
public void addSucc(Result succ) {
successors.add(succ);
}
- public void addResult(Forest f, Pos reduction, Node pred) {
+ public void addResult(Forest f, Pos reduction, StateNode pred) {
for(Result r : results)
if (r.predecessorsContains(pred)) {
r.merge(f);
for(Result r : results)
if (r.predecessorsContains(pred)) {
r.merge(f);
@@
-147,10
+147,10
@@
final class Node
// GraphViz //////////////////////////////////////////////////////////////////////////////
// GraphViz //////////////////////////////////////////////////////////////////////////////
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (results.size()==0) return null;
if (gv.hasNode(this)) return gv.createNode(this);
if (results.size()==0) return null;
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = "state["+state.toInt()+"]";
n.shape = "rectangle";
boolean haspreds = false;
n.label = "state["+state.toInt()+"]";
n.shape = "rectangle";
boolean haspreds = false;
diff --git
a/src/edu/berkeley/sbp/util/GraphViz.java
b/src/edu/berkeley/sbp/util/GraphViz.java
index
44b47fc
..
1d85e11
100644
(file)
--- a/
src/edu/berkeley/sbp/util/GraphViz.java
+++ b/
src/edu/berkeley/sbp/util/GraphViz.java
@@
-10,18
+10,18
@@
import java.lang.ref.*;
public class GraphViz {
public class GraphViz {
- IdentityHashMap<ToGraphViz,Node> ihm = new IdentityHashMap<ToGraphViz,Node>();
- HashMap<Node,Group> groups = new HashMap<Node,Group>();
+ IdentityHashMap<ToGraphViz,StateNode> ihm = new IdentityHashMap<ToGraphViz,StateNode>();
+ HashMap<StateNode,Group> groups = new HashMap<StateNode,Group>();
- public class Group extends Node {
+ public class Group extends StateNode {
private final int idx = master_idx++;
public boolean cluster = false;
public boolean primary = true;
public Group() { }
private final int idx = master_idx++;
public boolean cluster = false;
public boolean primary = true;
public Group() { }
- public void add(Node n) { groups.put(n, this); }
+ public void add(StateNode n) { groups.put(n, this); }
public String name() { return cluster?("cluster_"+idx):("subgraph_"+idx); }
public boolean simple() { return false; }
public String name() { return cluster?("cluster_"+idx):("subgraph_"+idx); }
public boolean simple() { return false; }
- public void dump(PrintWriter pw, IdentityHashMap<Node,Node> done) {
+ public void dump(PrintWriter pw, IdentityHashMap<StateNode,StateNode> done) {
Group g = this;
if (done.get(g)!=null) return;
done.put(g,g);
Group g = this;
if (done.get(g)!=null) return;
done.put(g,g);
@@
-29,7
+29,7
@@
public class GraphViz {
pw.println(" label=\""+StringUtil.escapify(label.toString(), "\\\"\r\n")+"\";\n");
pw.println(" color="+g.color+";\n");
pw.println(" shape="+g.shape+";\n");
pw.println(" label=\""+StringUtil.escapify(label.toString(), "\\\"\r\n")+"\";\n");
pw.println(" color="+g.color+";\n");
pw.println(" shape="+g.shape+";\n");
- for(Node n : groups.keySet())
+ for(StateNode n : groups.keySet())
if (groups.get(n)==g)
n.dump(pw, done);
pw.println(" }\n");
if (groups.get(n)==g)
n.dump(pw, done);
pw.println(" }\n");
@@
-38,7
+38,7
@@
public class GraphViz {
private static int master_idx=0;
private static int master_idx=0;
- public class Node {
+ public class StateNode {
private final int idx = master_idx++;
public String label;
public String comment;
private final int idx = master_idx++;
public String label;
public String comment;
@@
-46,11
+46,11
@@
public class GraphViz {
public String color="black";
public String fill="white";
public String shape="ellipse";
public String color="black";
public String fill="white";
public String shape="ellipse";
- public ArrayList<Node> edges = new ArrayList<Node>();
+ public ArrayList<StateNode> edges = new ArrayList<StateNode>();
public ArrayList<Object> labels = new ArrayList<Object>();
public ArrayList<Object> labels = new ArrayList<Object>();
- public ArrayList<Node> inbound = new ArrayList<Node>();
+ public ArrayList<StateNode> inbound = new ArrayList<StateNode>();
public void edge(ToGraphViz o, Object label) {
public void edge(ToGraphViz o, Object label) {
- Node n = o.toGraphViz(GraphViz.this);
+ StateNode n = o.toGraphViz(GraphViz.this);
if (n==null) return;
edges.add(n);
labels.add(label);
if (n==null) return;
edges.add(n);
labels.add(label);
@@
-69,7
+69,7
@@
public class GraphViz {
public void edges(PrintWriter pw) {
if (simple()) return;
for(int i=0; i<edges.size(); i++) {
public void edges(PrintWriter pw) {
if (simple()) return;
for(int i=0; i<edges.size(); i++) {
- Node n = edges.get(i);
+ StateNode n = edges.get(i);
Object label = labels.get(i);
pw.println(" "+name()+" -> " + n.name() + " [color="+color+" "
+(label==null?"":("label=\""+StringUtil.escapify(label.toString(), "\\\"\r\n")+"\""))+ "];\n");
Object label = labels.get(i);
pw.println(" "+name()+" -> " + n.name() + " [color="+color+" "
+(label==null?"":("label=\""+StringUtil.escapify(label.toString(), "\\\"\r\n")+"\""))+ "];\n");
@@
-80,17
+80,17
@@
public class GraphViz {
boolean simple = true;
if (label!=null && !label.equals("")) simple = false;
if (simple)
boolean simple = true;
if (label!=null && !label.equals("")) simple = false;
if (simple)
- for(Node n : edges)
+ for(StateNode n : edges)
//if (n.numEdges()>0) { simple = false; break; }
if (n.inbound.size() > 1) { simple = false; break; }
return simple;
}
//if (n.numEdges()>0) { simple = false; break; }
if (n.inbound.size() > 1) { simple = false; break; }
return simple;
}
- public void dump(PrintWriter pw, IdentityHashMap<Node,Node> done) {
+ public void dump(PrintWriter pw, IdentityHashMap<StateNode,StateNode> done) {
if (done.get(this)!=null) return;
done.put(this, this);
if (inbound.size() > 0) {
boolean good = false;
if (done.get(this)!=null) return;
done.put(this, this);
if (inbound.size() > 0) {
boolean good = false;
- for(Node n : inbound)
+ for(StateNode n : inbound)
if (!n.simple())
{ good = true; break; }
if (!good) return;
if (!n.simple())
{ good = true; break; }
if (!good) return;
@@
-102,12
+102,12
@@
public class GraphViz {
pw.print(" shape=record ");
pw.print(" label=\"");
boolean complex = false;
pw.print(" shape=record ");
pw.print(" label=\"");
boolean complex = false;
- for(Node n : edges)
+ for(StateNode n : edges)
if (n.edges.size()>0)
complex = true;
if (!complex) pw.print("{");
boolean first = true;
if (n.edges.size()>0)
complex = true;
if (!complex) pw.print("{");
boolean first = true;
- for(Node n : edges) {
+ for(StateNode n : edges) {
if (!first) pw.print("|");
first = false;
pw.print("<node_"+n.idx+">");
if (!first) pw.print("|");
first = false;
pw.print("<node_"+n.idx+">");
@@
-130,10
+130,10
@@
public class GraphViz {
return ihm.get(o)!=null;
}
return ihm.get(o)!=null;
}
- public Node createNode(ToGraphViz o) {
- Node n = ihm.get(o);
+ public StateNode createNode(ToGraphViz o) {
+ StateNode n = ihm.get(o);
if (n!=null) return n;
if (n!=null) return n;
- n = new Node();
+ n = new StateNode();
ihm.put(o, n);
return n;
}
ihm.put(o, n);
return n;
}
@@
-147,7
+147,7
@@
public class GraphViz {
}
public static interface ToGraphViz {
}
public static interface ToGraphViz {
- Node toGraphViz(GraphViz gv);
+ StateNode toGraphViz(GraphViz gv);
boolean isTransparent();
boolean isHidden();
}
boolean isTransparent();
boolean isHidden();
}
@@
-158,17
+158,17
@@
public class GraphViz {
public void dump(OutputStream os) { dump(new PrintWriter(new OutputStreamWriter(os))); }
public void dump(PrintWriter pw) {
public void dump(OutputStream os) { dump(new PrintWriter(new OutputStreamWriter(os))); }
public void dump(PrintWriter pw) {
- IdentityHashMap<Node,Node> done = new IdentityHashMap<Node,Node>();
+ IdentityHashMap<StateNode,StateNode> done = new IdentityHashMap<StateNode,StateNode>();
pw.println("digraph G { rankdir=LR; ordering=out; compound=true; \n");
for(Group g : groups.values())
if (g.primary)
g.dump(pw, done);
pw.println("digraph G { rankdir=LR; ordering=out; compound=true; \n");
for(Group g : groups.values())
if (g.primary)
g.dump(pw, done);
- for(Node n : ihm.values()) {
+ for(StateNode n : ihm.values()) {
if (done.get(n)!=null) continue;
if (n instanceof Group) continue;
n.dump(pw, done);
}
if (done.get(n)!=null) continue;
if (n instanceof Group) continue;
n.dump(pw, done);
}
- for(Node n : ihm.values()) n.edges(pw);
+ for(StateNode n : ihm.values()) n.edges(pw);
pw.println("}\n");
pw.flush();
}
pw.println("}\n");
pw.flush();
}
diff --git
a/src/edu/berkeley/sbp/util/PrintableTree.java
b/src/edu/berkeley/sbp/util/PrintableTree.java
index
ba26a58
..
802296d
100644
(file)
--- a/
src/edu/berkeley/sbp/util/PrintableTree.java
+++ b/
src/edu/berkeley/sbp/util/PrintableTree.java
@@
-87,9
+87,9
@@
public abstract class PrintableTree<T extends PrintableTree> implements Iterable
// this is here to keep it out of the javadoc for Tree<T>
// this is here to keep it out of the javadoc for Tree<T>
- public GraphViz.Node toGraphViz(GraphViz gv) {
+ public GraphViz.StateNode toGraphViz(GraphViz gv) {
if (gv.hasNode(this)) return gv.createNode(this);
if (gv.hasNode(this)) return gv.createNode(this);
- GraphViz.Node n = gv.createNode(this);
+ GraphViz.StateNode n = gv.createNode(this);
n.label = head()==null ? "" : head().toString();
for(T t : this) n.edge(t, null);
return n;
n.label = head()==null ? "" : head().toString();
for(T t : this) n.edge(t, null);
return n;