public int waits = 0;
HashMapBag<Integer,Sequence> inhibited = new HashMapBag<Integer,Sequence>();
+ HashMapBag<Integer,Sequence> assumed = new HashMapBag<Integer,Sequence>();
HashMapBag<Sequence,Phase.Waiting> waiting = new HashMapBag<Sequence,Phase.Waiting>();
HashMapBag<Integer,Sequence> performed = new HashMapBag<Integer,Sequence>();
+ HashSet<Phase.Waiting> tail = new HashSet<Phase.Waiting>();
/** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
public class Phase implements Invokable<State, Forest, GSS.Phase.Node> {
this.token = token;
this.location = location;
inhibited.clear();
+ assumed.clear();
reset();
}
public void reset() {
+ tail.clear();
waiting.clear();
performed.clear();
hash = new HashMap<Long,Phase.Node>();
* @param start the earliest part of the input contributing to this node (used to make merging decisions)
*/
public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
- return newNode(parent, pending, state, fromEmptyReduction, null); }
- public boolean newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
+ Node p = hash.get(code(state, parent==null?null:parent.phase()));
+ if (p != null) return newNode2(p, parent, pending, state, fromEmptyReduction);
+ else return newNode3(parent, pending, state, fromEmptyReduction);
+ }
+ public void newNode(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
int pos = parent==null?0:parent.phase()==null?0:parent.phase().pos;
+ Sequence owner = reduction==null ? null : reduction.position.owner();
if (reduction!=null) {
- if (inhibited.contains(pos, reduction.position.owner())) return false;
- if (reduction.position.owner().needs != null) {
- for(Sequence s : reduction.position.owner().needs) {
+ if (inhibited.contains(pos, owner)) return;
+ /*
+ if (assumed.contains(pos, owner)) {
+ tail.add(new Waiting(parent, pending, state, fromEmptyReduction, reduction));
+ return;
+ }
+ */
+ if (owner.needs != null)
+ for(Sequence s : owner.needs)
if (!performed.contains(pos, s)) {
waiting.add(s, new Waiting(parent, pending, state, fromEmptyReduction, reduction));
- return false;
+ return;
}
- }
- }
- if ((reduction.position.owner().needed != null && reduction.position.owner().needed.size()>0) ||
- (reduction.position.owner().hated != null && reduction.position.owner().hated.size()>0) ||
- (reduction.position.owner().hates != null && reduction.position.owner().hates.size()>0))
- performed.add(pos, reduction.position.owner());
+ if ((owner.needed != null && owner.needed.size()>0) ||
+ (owner.hated != null && owner.hated.size()>0) ||
+ (owner.hates != null && owner.hates.size()>0))
+ performed.add(pos, owner);
}
- Node p = hash.get(code(state, parent==null?null:parent.phase()));
- boolean ret;
+ if (!owner.lame)
+ newNode(parent, pending, state, fromEmptyReduction);
if (reduction!=null) inhibit(reduction, parent==null?0:parent.phase().pos);
- if (p != null) ret = newNode2(p, parent, pending, state, fromEmptyReduction, reduction);
- else ret = newNode3(parent, pending, state, fromEmptyReduction, reduction);
if (reduction != null) {
boolean redo = true;
while(redo) {
redo = false;
- for(Waiting w : waiting.getAll(reduction.position.owner())) {
+ for(Waiting w : waiting.getAll(owner)) {
if (w.parent==parent || (parent!=null&&w.parent!=null&&w.parent.phase()==parent.phase())) {
- waiting.remove(reduction.position.owner(), w);
+ waiting.remove(owner, w);
w.perform();
redo = true;
break;
}
}
}
- return ret;
}
- private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
+ private boolean newNode2(Node p, Node parent, Forest pending, State state, boolean fromEmptyReduction) {
p.holder.merge(pending);
if (p.parents().contains(parent)) return true;
- //if (p.fe && p.phase() != parent.phase()) throw new Error("yep yep");
- //if (!p.fe && p.phase() == parent.phase()) throw new Error("yep yep2");
p.parents().add(parent, true);
if (p!=parent && !fromEmptyReduction) p.queueReductions(parent);
return true;
}
- private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction, Reduction reduction) {
+ private boolean newNode3(Node parent, Forest pending, State state, boolean fromEmptyReduction) {
do {
if (token != null && state.canShift(token)) break;
if (state.isAccepting()) break;
return true;
}
+ public void uninhibit(int p, Sequence s) {
+ if (s.hated!=null)
+ for(Sequence s2 : s.hated)
+ inhibited.remove(p, s2);
+ }
+
public void inhibit(Reduction r, int p) {
if (r.position.owner().hated == null) return;
// remember that dead states are still allowed to shift -- just not allowed to reduce
+ boolean reset = false;
for(Sequence seq : r.position.owner().hated) {
if (performed.contains(p,seq)) {
- inhibited.clear();
+ uninhibit(p, seq);
+ //System.out.println("\nresetting due to " + r.position.owner() + " killing " + seq);
+ //inhibited.clear();
inhibited.add(p, seq);
+ //assumed = inhibited;
+ //inhibited = new HashMapBag<Integer,Sequence>();
+ reset = true;
resets++;
throw new Reset();
}
reducing_list[i] = null;
n.queueReductions();
}
+ //for(Waiting w : tail)
+ //w.perform();
} catch (Reset r) {
reset();
reduce();
Forest res = null;
boolean ok = false;
for(Phase.Node n : hash.values()) {
- if (n.holder==null) continue;
- n.holder.resolve();
+ //if (n.holder().empty() && pos>0) continue;
if (token == null && n.state.isAccepting()) {
if (finalResult==null) finalResult = new Forest.Ref();
finalResult.merge(n.holder);
}
- if (!n.holder.valid()) continue;
if (token == null) continue;
n.state.invokeShifts(token, this, result, n);
}
this.reduction = reduction;
}
public void perform() {
- System.out.println("performing: " + reduction.position);
+ //System.out.println("performing: " + reduction.position);
newNode(parent, pending, state, fromEmptyReduction, reduction);
}
}
private Node(Node parent, Forest pending, State state, boolean fe) {
this.fe = fe;
this.state = state;
- for(Position p : state) {
- if (p.owner().needs!=null)
- for(Sequence s : p.owner().needs) {
- //dead = true;
- //redo = false;
- }
- }
+ this.holder().merge(pending);
+ //if (holder().empty()) throw new Error(holder()+"");
Phase start = parent==null ? null : parent.phase();
- if (pending != null) this.holder().merge(pending);
if (parent != null) parents().add(parent, true);
if (Phase.this.hash.get(code(state, start)) != null) throw new Error("severe problem!");
Phase.this.hash.put(code(state, start), this);
Phase.this.numNodes++;
- if (parent==null) holder().valid = true; // hack to make sure that the "base" node is always considered valid
}
}