src/edu/berkeley/sbp/Forest.java

   1 package edu.berkeley.sbp;
   2 import edu.berkeley.sbp.*;
   3 import edu.berkeley.sbp.Sequence.Position;
   4 import edu.berkeley.sbp.util.*;
   5 import java.io.*;
   6 import java.util.*;
   7 import java.lang.reflect.*;
   8
   9 /** an efficient representation of a collection of trees (Tomita's shared packed parse forest) */
  10 public abstract class Forest<T> /*extends PrintableTree<Forest.MyBody<T>>*/
  11     implements Visitable<Forest.Body<T>>,
  12                IntegerMappable,
  13                GraphViz.ToGraphViz {
  14
  15     private static int master_idx = 0;
  16     private final int idx = master_idx++;
  17     public int toInt() { return idx; }
  18
  19     public abstract void expand(TaskList tl, HashSet<Tree<T>> ht);
  20     public abstract void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target);
  21
  22     public static class TaskList extends ArrayList<TaskList.Task> {
  23         public interface Task {
  24             public void perform();
  25         }
  26         public class ExpandTask implements Task {
  27             private Forest f;
  28             private HashSet hs;
  29             public ExpandTask(Forest f, HashSet hs) { this.f = f; this.hs = hs; }
  30             public void perform() { f.expand(TaskList.this, hs); }
  31         }
  32         public class GatherTask implements Task {
  33             private Forest f;
  34             private HashSet[] ht;
  35             private HashSet hs;
  36             public GatherTask(Forest f, HashSet<Tree<?>>[] ht, HashSet<Tree<?>> hs) { this.f = f; this.hs = hs; this.ht = ht;}
  37             public void perform() { f.gather(TaskList.this, ht, hs); }
  38         }
  39         public void expand(Forest f, HashSet hs) {
  40             add(new ExpandTask(f, hs));
  41         }
  42         public void gather(Forest f, HashSet[] ht, HashSet hs) {
  43             add(new GatherTask(f, ht, hs));
  44         }
  45         public void run() {
  46             while(true) {
  47                 if (isEmpty()) return;
  48                 Task task = get(size()-1);
  49                 remove(size()-1);
  50                 task.perform();
  51             }
  52         }
  53     }
  54
  55     /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
  56     public final Tree<T> expand1() throws Ambiguous, ParseFailed {
  57         try {
  58             Iterator<Tree<T>> it = expand(true).iterator();
  59             if (!it.hasNext()) throw new ParseFailed();
  60             return it.next();
  61         } catch (InnerAmbiguous ia) { throw new Ambiguous(ia.f); }
  62     }
  63
  64     /** expand this forest into a set of trees */
  65     public HashSet<Tree<T>> expand(boolean toss) {
  66         TaskList tl = new TaskList();
  67         HashSet<Tree<T>> ret = new HashSet<Tree<T>>();
  68         tl.expand(this, ret);
  69         tl.run();
  70
  71         if (toss && ret.size() > 1) throw new InnerAmbiguous(this);
  72         return ret;
  73     }
  74
  75     private static class InnerAmbiguous extends RuntimeException {
  76         public final Forest<?> f;
  77         public InnerAmbiguous(Forest<?> f) { this.f = f; }
  78     }
  79
  80     static        <T> Forest<T> singleton(Input.Region loc, Position p) {
  81         return create(loc, null, new Forest[] { }, false, true, p); }
  82     static        <T> Forest<T> singleton(Input.Region loc, Forest<T> body, Position p) { return body; }
  83     static        <T> Forest<T> leaf(Input.Region loc, T tag, Position p) { return create(loc, tag, null, false, false, p); }
  84     public static <T> Forest<T> create(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap, boolean singleton, Position p) {
  85         return new MyBody<T>(loc, tag, tokens, unwrap, singleton, p);
  86     }
  87     // Body //////////////////////////////////////////////////////////////////////////////
  88
  89     public /*protected*/ static interface Body<T> extends GraphViz.ToGraphViz {
  90         void expand(int i, TreeBuilder<T> h);
  91     }
  92     public abstract void edges(GraphViz.Node n);
  93     public boolean ambiguous() { return false; }
  94     public /*protected*/ static class MyBody<T> extends Forest<T> implements Body<T> /* extends PrintableTree<Forest<T>> implements */ {
  95
  96         public boolean isTransparent() { return false; }
  97         public boolean isHidden() { return false; }
  98         public GraphViz.Node toGraphViz(GraphViz gv) {
  99             if (gv.hasNode(this)) return gv.createNode(this);
 100             GraphViz.Node n = gv.createNode(this);
 101             n.label = headToString()==null?"":headToString();
 102             n.directed = true;
 103             n.comment = reduction==null?null:reduction+"";
 104             edges(n);
 105             return n;
 106         }
 107         boolean edges = false;
 108         public void edges(GraphViz.Node n) {
 109             if (edges) return;
 110             edges = true;
 111             for(int i=0; i<tokens.length; i++) {
 112                 if (i==tokens.length-1 && unwrap && !tokens[i].ambiguous()) {
 113                     tokens[i].edges(n);
 114                 } else {
 115                     n.edge(tokens[i], null);
 116                 }
 117             }
 118         }
 119
 120         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 121             ivbc.invoke(this, b, c);
 122         }
 123
 124         private final Input.Region    location;
 125         private final T                 tag;
 126         private final Forest<T>[]       tokens;
 127         private final boolean           unwrap;
 128         private final boolean           singleton;
 129         private final Sequence.Position reduction;
 130
 131         private MyBody(Input.Region loc, T tag, Forest<T>[] tokens, boolean unwrap, boolean singleton, Position reduction) {
 132             this.location = loc;
 133             this.tag = tag;
 134             this.tokens = tokens==null ? emptyForestArray : new Forest[tokens.length];
 135             if (tokens != null) System.arraycopy(tokens, 0, this.tokens, 0, tokens.length);
 136             if (tokens != null) for(int i=0; i<tokens.length; i++) if (tokens[i]==null) throw new Error(i+"");
 137             this.unwrap = unwrap;
 138             this.singleton = singleton;
 139             this.reduction = reduction;
 140         }
 141         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 142             gather(tl, ht, target, new Tree[ht.length], 0);
 143         }
 144         private void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target, Tree[] trees, int i) {
 145             if (i==ht.length) {
 146                 target.add(new Tree<T>(location, tag, trees));
 147                 return;
 148             }
 149             for(Tree<T> tree : ht[i]) {
 150                 if (unwrap && i==trees.length-1) {
 151                     // I think this is wrong
 152                     Tree[] trees2 = new Tree[trees.length - 1 + tree.numChildren()];
 153                     System.arraycopy(trees, 0, trees2, 0, trees.length-1);
 154                     for(int j=0; j<tree.numChildren(); j++)
 155                         trees2[trees.length-1+j] = tree.child(j);
 156                     target.add(new Tree<T>(location, tag, trees2));
 157                 } else {
 158                     trees[i] = tree;
 159                     gather(tl, ht, target, trees, i+1);
 160                     trees[i] = null;
 161                 }
 162             }
 163         }
 164         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 165             if (singleton) {
 166                 tokens[0].expand(tl, ht);
 167                 return;
 168             }
 169             HashSet<Tree<T>>[] children = new HashSet[tokens.length];
 170             tl.gather(this, children, ht);
 171             for(int i=0; i<children.length; i++) {
 172                 children[i] = new HashSet<Tree<T>>();
 173                 tl.expand(tokens[i], children[i]);
 174             }
 175         }
 176
 177         public void expand(final int i, final TreeBuilder<T> h) {
 178             if (singleton) {
 179                 tokens[0].visit(h, null, i);
 180                 return;
 181             }
 182             if (i==0) h.start(tag, location);
 183
 184             if (i==tokens.length) {
 185                 h.finish(tag, location);
 186
 187             } else if (unwrap && i==tokens.length-1) {
 188                 if (tokens[i] != null)
 189                     tokens[i].visit(h, null, 0);
 190
 191             } else {
 192                 tokens[i].visit(new TreeBuilder<T>(h.toss) {
 193                     public void start(T head, Input.Region loc) { }
 194                     public void addTree(Tree<T> t) { toks.add(t); }
 195                     public void finish(T head, Input.Region loc) {
 196                         int old = h.toks.size();
 197                         h.addTree(new Tree<T>(loc, head, toks.toArray(tree_hint)));
 198                         expand(i+1, h);
 199                         while(h.toks.size() > old) h.toks.remove(h.toks.size()-1);
 200                     }
 201                 }, null, null);
 202             }
 203         }
 204
 205         protected String  headToString()         { return tag==null?null:tag.toString(); }
 206         protected String  headToJava()           { return "null"; }
 207         protected String  left()                 { return "{"; }
 208         protected String  right()                { return "}"; }
 209         protected boolean ignoreSingleton()      { return false; }
 210     }
 211
 212
 213     // Ref //////////////////////////////////////////////////////////////////////////////
 214
 215     /**
 216      *  This class represents a partially complete collection of
 217      *  forests to be viewed as a forest at some later date; once
 218      *  viewed, it becomes immutable
 219      */
 220     static class Ref<T> extends Forest<T> {
 221         public void expand(TaskList tl, HashSet<Tree<T>> ht) {
 222             for (Forest<T> f : hp) f.expand(tl, ht);
 223         }
 224         public void gather(TaskList tl, HashSet<Tree<T>>[] ht, HashSet<Tree<T>> target) {
 225             throw new Error();
 226         }
 227         public HashSet<GSS.Phase.Node> parents = new HashSet<GSS.Phase.Node>();
 228         public boolean contains(Forest f) {
 229             return hp.contains(f);
 230         }
 231         public boolean ambiguous() {
 232             if (hp.size()==0) return false;
 233             if (hp.size()==1) return hp.iterator().next().ambiguous();
 234             return true;
 235         }
 236         private FastSet<Forest<T>> hp = new FastSet<Forest<T>>();
 237         public Ref() { }
 238         public int toInt() {
 239             if (hp.size()==1) return hp.iterator().next().toInt();
 240             return super.toInt();
 241         }
 242         public void merge(Forest p) { if (p!=this) hp.add(p, true); }
 243
 244         public boolean isTransparent() { return hp.size()==1; }
 245         public boolean isHidden() { return hp.size()==0; }
 246         public void edges(GraphViz.Node n) {
 247             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 248             for(Forest f : hp) f.edges(n);
 249         }
 250         public GraphViz.Node toGraphViz(GraphViz gv) {
 251             //if (hp.size()==0) return null;
 252             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 253             if (gv.hasNode(this)) return gv.createNode(this);
 254             GraphViz.Node n = gv.createNode(this);
 255             n.label = "?";
 256             n.color = "red";
 257             for(Forest f : hp) n.edge(f, null);
 258             return n;
 259         }
 260
 261         public <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c) {
 262             if (hp==null) return;
 263             for(Forest<T> f : hp)
 264                 f.visit(ivbc, b, c);
 265         }
 266         public Forest resolve() { return this; }
 267     }
 268
 269     public abstract <B,C> void visit(Invokable<Forest.Body<T>,B,C> ivbc, B b, C c);
 270
 271     // Statics //////////////////////////////////////////////////////////////////////////////
 272
 273     private static Tree[] tree_hint = new Tree[0];
 274     private static String[] string_hint = new String[0];
 275     private static final Forest[] emptyForestArray = new Forest[0];
 276
 277     protected String  headToString()    { return null; }
 278     protected String  headToJava()      { return "null"; }
 279     protected String  left()            { return "<?"; }
 280     protected String  right()           { return "?>"; }
 281     protected boolean ignoreSingleton() { return true; }
 282 }