src/edu/berkeley/sbp/Forest.java

   1 // Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp;
   4 import edu.berkeley.sbp.util.*;
   5 import java.io.*;
   6 import java.util.*;
   7
   8 /**
   9  *   <font color=blue>
  10  *   An efficient representation of a collection of trees (Tomita's
  11  *   shared packed parse forest).
  12  *   </font>
  13  */
  14 public abstract class Forest<NodeType> implements GraphViz.ToGraphViz {
  15
  16     /** assume that this forest contains exactly one tree and return it; otherwise throw an exception */
  17     public abstract Tree<NodeType> expand1() throws Ambiguous;
  18
  19     /** expand this forest into a set of trees */
  20     public Iterable<Tree<NodeType>> expand() {
  21         HashSet<Tree<NodeType>> ht = new HashSet<Tree<NodeType>>();
  22         expand(ht, new HashSet<Forest<NodeType>>(), null);
  23         return ht;
  24     }
  25
  26     /** returns the input Region which this Forest was parsed from */
  27     public abstract Input.Region getRegion();
  28
  29     // Package-Private //////////////////////////////////////////////////////////////////////////////
  30
  31     static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children,
  32                                               boolean lift) {
  33         if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen");
  34         return new One<NodeType>(region, head, children, lift);
  35     }
  36
  37     static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children,
  38                                               boolean lift, boolean liftLeft) {
  39         if (region == null) throw new RuntimeException("invoked Forest.create(region=null) -- this should never happen");
  40         return new One<NodeType>(region, head, children, lift, liftLeft);
  41     }
  42
  43     /** create a new forest */
  44     public static <NodeType> Forest<NodeType> create(Input.Region region, NodeType head, Forest<NodeType>[] children) {
  45         return Forest.create(region, head, children, false); }
  46
  47     abstract void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus);
  48     abstract void gather(HashSet<Forest<NodeType>> ignore);
  49     abstract void edges(GraphViz.Node n);
  50     boolean ambiguous() { return false; }
  51
  52     // One //////////////////////////////////////////////////////////////////////////////
  53
  54     /** A "single" forest with a head and child subforests */
  55     private static class One<NodeType> extends Forest<NodeType> {
  56
  57         private final Input.Region      location;
  58         private final NodeType                head;
  59         private final Forest<NodeType>[]       children;
  60
  61         /** if true, the last child's children are considered children of this node */
  62         private final boolean           lift;
  63         private final boolean           liftLeft;
  64
  65         public Input.Region getRegion() { return location; }
  66
  67         private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean lift) {
  68             this(loc, head, children, lift, false);
  69         }
  70         private One(Input.Region loc, NodeType head, Forest<NodeType>[] children, boolean lift, boolean liftLeft) {
  71             this.location = loc;
  72             this.head = head;
  73             if (head==null) throw new RuntimeException("invoked Forest.create(,null,,,) -- this should never happen");
  74             this.children = children==null ? emptyForestArray : new Forest[children.length];
  75             if (children != null) System.arraycopy(children, 0, this.children, 0, children.length);
  76             if (children != null) for(int i=0; i<children.length; i++) if (children[i]==null) throw new Error(i+"");
  77             this.lift = lift;
  78             this.liftLeft = liftLeft;
  79         }
  80
  81         public Tree<NodeType> expand1() throws Ambiguous {
  82             Tree<NodeType>[] ret = new Tree[children.length];
  83             for(int i=0; i<children.length; i++) ret[i] = children[i].expand1();
  84             return new Tree<NodeType>(location, head, ret, lift, liftLeft);
  85         }
  86
  87         void gather(HashSet<Forest<NodeType>> hf) {
  88             hf.add(this);
  89             for(Forest<NodeType> f : children) f.gather(hf);
  90         }
  91         void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus) {
  92             if (ignore.contains(this)) { ht.add(bogus); return; }
  93             expand(0, new Tree[children.length], ht, ignore, bogus);
  94         }
  95         private void expand(final int i, Tree<NodeType>[] ta, HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore,
  96                             Tree<NodeType> bogus) {
  97             if (i==children.length) {
  98                 ht.add(new Tree<NodeType>(location, head, ta, lift, liftLeft));
  99             } else {
 100                 HashSet<Tree<NodeType>> ht2 = new HashSet<Tree<NodeType>>();
 101                 children[i].expand(ht2, ignore, bogus);
 102                 for(Tree<NodeType> tc : ht2) {
 103                     ta[i] = tc;
 104                     expand(i+1, ta, ht, ignore, bogus);
 105                     ta[i] = null;
 106                 }
 107             }
 108         }
 109
 110         // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
 111
 112         public boolean isTransparent() { return false; }
 113         public boolean isHidden() { return false; }
 114         public GraphViz.Node toGraphViz(GraphViz gv) {
 115             if (gv.hasNode(this)) return gv.createNode(this);
 116             GraphViz.Node n = gv.createNode(this);
 117             n.label = headToString()==null?"":headToString();
 118             n.directed = true;
 119             edges(n);
 120             return n;
 121         }
 122         boolean edges = false; // FIXME ??
 123         public void edges(GraphViz.Node n) {
 124             if (edges) return;
 125             edges = true;
 126             for(int i=0; i<children.length; i++) {
 127                 if (i==children.length-1 && lift && !children[i].ambiguous()) {
 128                     children[i].edges(n);
 129                 } else {
 130                     n.edge(children[i], null);
 131                 }
 132             }
 133         }
 134
 135         protected String  headToString()         { return head==null?null:head.toString(); }
 136         protected String  headToJava()           { return "null"; }
 137         protected String  left()                 { return "{"; }
 138         protected String  right()                { return "}"; }
 139         protected boolean ignoreSingleton()      { return false; }
 140     }
 141
 142
 143     // Many //////////////////////////////////////////////////////////////////////////////
 144
 145     /** An "ambiguity node"; this is immutable once it has been "looked at" */
 146     static class Many<NodeType> extends Forest<NodeType> {
 147
 148         private FastSet<Forest<NodeType>> hp = new FastSet<Forest<NodeType>>();
 149         private boolean touched = false;
 150
 151         public Many() { }
 152
 153         public Input.Region getRegion() { return hp.iterator().next().getRegion(); } // all should be identical
 154
 155         public Tree<NodeType> expand1() throws Ambiguous {
 156             touched();
 157             if (hp.size() > 1) {
 158                 HashSet<Forest<NodeType>> hf0 = new HashSet<Forest<NodeType>>();
 159                 Iterator<Forest<NodeType>> ih = hp.iterator();
 160                 ih.next().gather(hf0);
 161                 for(Forest<NodeType> f : hp) {
 162                     HashSet<Forest<NodeType>> hf1 = new HashSet<Forest<NodeType>>();
 163                     f.gather(hf1);
 164                     hf0.retainAll(hf1);
 165                 }
 166                 HashSet<Tree<NodeType>> ht = new HashSet<Tree<NodeType>>();
 167                 expand(ht, hf0, new Tree(null, "*"));
 168                 throw new Ambiguous((Forest<?>)this,
 169                                     (HashSet<Tree<?>>)(Object)ht);
 170             }
 171             return hp.iterator().next().expand1();
 172         }
 173
 174         void gather(HashSet<Forest<NodeType>> ht) {
 175             touched();
 176
 177             // FIXME: do something more sensible here
 178             if (ht.contains(this)) {
 179                 System.err.println("WARNING: grammar produced a circular forest\n" + this);
 180                 //throw new Error("grammar produced a circular forest:\n" + this);
 181                 return;
 182             }
 183
 184             ht.add(this);
 185             for(Forest<NodeType> f : hp) f.gather(ht);
 186         }
 187
 188         private void touched() {
 189             if (touched) return;
 190             touched = true;
 191             /*
 192             FastSet<Forest<NodeType>> f2 = new FastSet<Forest<NodeType>>();
 193             for(Forest f : hp)
 194                 if (f instanceof Forest.One) f2.add(f);
 195                 else for(Forest ff : ((Forest.Many<NodeType>)f))
 196                     f2.add(ff);
 197             hp = f2;
 198             */
 199         }
 200         public boolean contains(Forest f) {
 201             touched();
 202             return hp.contains(f);
 203         }
 204         public void merge(Forest p) {
 205             if (touched) throw new RuntimeException("attempt to merge() on a Forest.Many that has already been examined");
 206             if (p==this) throw new RuntimeException("attempt to merge() a Forest.Many to itself!");
 207             hp.add(p, true);
 208         }
 209         boolean ambiguous() {
 210             touched();
 211             if (hp.size()==0) return false;
 212             if (hp.size()==1) return hp.iterator().next().ambiguous();
 213             return true;
 214         }
 215
 216         void expand(HashSet<Tree<NodeType>> ht, HashSet<Forest<NodeType>> ignore, Tree<NodeType> bogus) {
 217             touched();
 218             if (ignore.contains(this)) { ht.add(bogus); return; }
 219             for (Forest<NodeType> f : hp) f.expand(ht, ignore, bogus);
 220         }
 221
 222
 223         // GraphViz, ToInt //////////////////////////////////////////////////////////////////////////////
 224
 225         public boolean isTransparent() { return hp.size()==1; }
 226         public boolean isHidden() { return hp.size()==0; }
 227         public void edges(GraphViz.Node n) {
 228             if (hp.size()==1) { hp.iterator().next().edges(n); return; }
 229             for(Forest f : hp) f.edges(n);
 230         }
 231         public GraphViz.Node toGraphViz(GraphViz gv) {
 232             if (hp.size()==1) return hp.iterator().next().toGraphViz(gv);
 233             if (gv.hasNode(this)) return gv.createNode(this);
 234             GraphViz.Node n = gv.createNode(this);
 235             n.label = "?";
 236             n.color = "red";
 237             for(Forest f : hp) n.edge(f, null);
 238             return n;
 239         }
 240     }
 241
 242     // Statics //////////////////////////////////////////////////////////////////////////////
 243
 244     private static Tree[] tree_hint = new Tree[0];
 245     private static String[] string_hint = new String[0];
 246     private static final Forest[] emptyForestArray = new Forest[0];
 247
 248     protected String  headToString()    { return null; }
 249     protected String  headToJava()      { return "null"; }
 250     protected String  left()            { return "<?"; }
 251     protected String  right()           { return "?>"; }
 252     protected boolean ignoreSingleton() { return true; }
 253 }