src/edu/berkeley/sbp/Walk.java

   1 package edu.berkeley.sbp;
   2 import edu.berkeley.sbp.*;
   3 import edu.berkeley.sbp.util.*;
   4 import edu.berkeley.sbp.Sequence.Position;
   5 import java.io.*;
   6 import java.util.*;
   7 import java.lang.reflect.*;
   8 import java.lang.ref.*;
   9
  10 /** a traversal of the grammar performed by mapping from Elements to a lattice and computing the resulting LUB */
  11 abstract class Walk<T> {
  12     protected HashSet<Element> acc = new HashSet<Element>();
  13     protected abstract T bottom(Element e);
  14
  15     protected final Cache c;
  16     public Walk() { this(null); }
  17     public Walk(Cache c) { this.c = c; }
  18
  19     public  T sequence(Sequence s) {
  20         T ret = bottom(s);
  21         for(Position p = s.firstp(); p!=null && !p.isLast(); p = p.next())
  22             ret = sequence(s, ret, walk(p.element()));
  23         return ret;
  24     }
  25
  26     public      T walkAtom(Atom r) { return walk(r); }
  27     public      T union(Union u, T a, T b) { return  bottom(u); }
  28     public      T sequence(Sequence s, T a, T b) { return  bottom(s); }
  29     protected   T walk(Element e) {
  30         if (acc.contains(e)) return bottom(e);
  31         acc.add(e);
  32         return walk2(e);
  33     }
  34
  35     protected T walk2(Element e) {
  36         if      (e instanceof Atom)     return walkAtom((Atom)e);
  37         else if (e instanceof Sequence) return sequence((Sequence)e);
  38         else if (e instanceof Union) {
  39             T ret = bottom(e);
  40             for(Sequence s : (Union)e) {
  41                 ret = union((Union)e, ret, walk(s));
  42                 // FIXME
  43                 for(Sequence ss : s.needs()) ret = union((Union)e, ret, walk(ss));
  44                 for(Sequence ss : s.hates()) ret = union((Union)e, ret, walk(ss));
  45             }
  46             return ret;
  47         } else {
  48             throw new Error("unknown element of class " + e.getClass().getName() + ": " + e);
  49         }
  50     }
  51
  52     static class YieldSet extends Walk<HashSet<Element>> {
  53         private final Element e;
  54         public final HashSet<Element> walk() { return walk(e); }
  55         public YieldSet(Element e, Cache c)  { super(c); this.e = e; }
  56         public HashSet<Element> bottom(Element e)     { return acc; }
  57         public HashSet<Element> sequence(Sequence seq) { return bottom(seq); }
  58         public HashSet<Element> walkAtom(Atom r) {
  59             c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r));
  60             return super.walkAtom(r);
  61         }
  62     }
  63
  64
  65     // Boolean //////////////////////////////////////////////////////////////////////////////
  66
  67     static class PossiblyEpsilon extends Walk<Boolean> {
  68         public Boolean walkAtom(Atom r) { return false; }
  69         public Boolean sequence(Sequence s, Boolean a, Boolean b)  { return new Boolean(a && b); }
  70         public Boolean union(Union u, Boolean a, Boolean b)     { return new Boolean(a || b); }
  71         public Boolean bottom(Element e)    { return (e instanceof Union) ? false : true; }
  72         private HashMap<Element,Boolean> hm = new HashMap<Element,Boolean>();
  73         protected Boolean walk(Element e) {
  74             if (hm.get(e) != null) return hm.get(e);
  75             hm.put(e, false);
  76             Boolean ret = walk2(e);
  77             hm.put(e, ret);
  78             return ret;
  79         }
  80     }
  81
  82
  83     // Input-Set //////////////////////////////////////////////////////////////////////////////
  84
  85     static abstract class WalkTokenSet<Tok extends Input> extends Walk<Topology<Tok>> {
  86         public Topology<Tok> cs;
  87         public WalkTokenSet(Topology<Tok> cs)          { this.cs = cs; }
  88         public WalkTokenSet(Topology<Tok> cs, Cache c) { super(c); this.cs = cs; }
  89         public Topology<Tok> bottom(Element e)         { return cs; }
  90         public Topology<Tok> walkAtom(Atom r)          { cs = cs.union(r); return cs; }
  91     }
  92
  93     static class First<Tok extends Input> extends WalkTokenSet<Tok> {
  94         public First(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
  95         public Topology<Tok> sequence(Sequence seq) {
  96             for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
  97                 walk(p.element());
  98                 if (!c.possiblyEpsilon(p.element())) break;
  99             }
 100             return cs;
 101         }
 102     }
 103
 104     static class Follow<Tok extends Input> extends WalkTokenSet<Tok> {
 105         private final Element me;
 106         private final HashSet<Element> all;
 107         private boolean eof = false;
 108         public boolean includesEof() { return eof; }
 109         public Follow(Topology<Tok> cs, Element me, HashSet<Element> all, Cache c)  { super(cs, c); this.me = me; this.all = all; }
 110         public Topology<Tok> bottom(Element e)                       { return cs; }
 111         public Topology<Tok> sequence(Sequence seq)                  { return cs; }
 112         public Topology<Tok> walkAtom(Atom r) { return walk((Element)r); }
 113         public Topology<Tok> walk(Element e) {
 114             if (acc.contains(e)) return bottom(e);
 115             acc.add(e);
 116
 117             if (c != null) {
 118                 Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
 119                 if (cached != null) {
 120                     cs = cs.union(cached);
 121                     eof |= c.eof.get(e);
 122                     return cs;
 123                 }
 124             }
 125
 126             Topology<Tok> cso = cs;
 127             boolean eofo = eof;
 128             eof = c.eof.get(e) != null && c.eof.get(e).booleanValue();
 129             cs = cso.empty();
 130
 131             for(Element x : all) {
 132                 boolean matched = false;
 133                 if (!(x instanceof Sequence)) continue;
 134                 Sequence a = (Sequence)x;
 135                 Position mp = null;
 136                 for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) {
 137                     if (matched) cs = cs.union(c.first(pos.element(), cs.empty()));
 138                     if (pos.isLast()) { matched = (matched && c.possiblyEpsilon(pos.element())); continue; }
 139                     boolean good = false;
 140                     if (e instanceof Atom) {
 141                         Topology top = c.atoms.get(pos.element());
 142                         if (top==null) continue;
 143                         if (!(top.containsAll(((Atom)e)))) continue;
 144                     } else {
 145                         if (c.ys.contains(pos.element(),e)) good = true;
 146                     }
 147                     if (good) {
 148                         mp = pos;
 149                         matched = true;
 150                     }
 151                 }
 152                 if (matched) walk(a);
 153             }
 154
 155             if (e instanceof Sequence) {
 156                 Sequence s = (Sequence)e;
 157                 if (s.follow() != null) cs = cs.intersect(s.follow());
 158             }
 159
 160             if (c != null && e==me) {
 161                 c.follow.put(e, cs);
 162                 c.eof.put(e, eof);
 163             }
 164
 165             cso = cso.union(cs);
 166             cs = cso;
 167             eofo |= eof;
 168             eof = eofo;
 169
 170             return cs;
 171         }
 172     }
 173
 174     static class Cache {
 175         public final HashMap<Element,Boolean> possiblyEpsilon = new HashMap<Element,Boolean>();
 176         public HashMap<Element,Boolean> eof = new HashMap<Element,Boolean>();
 177         public HashMap<Element,Topology> follow = new HashMap<Element,Topology>();
 178         public HashMapBag<Element,Element>  ys = new HashMapBag<Element,Element>();
 179         public HashMap<Element,Topology> atoms = new HashMap<Element,Topology>();
 180         public <Tok extends Input> Topology<Tok> first(Element e, Topology<Tok> empty) {
 181             return new Walk.First<Tok>(empty, this).walk(e);
 182         }
 183         final boolean possiblyEpsilon(Element e) {
 184             Walk.Cache cache = this;
 185             Boolean ret = possiblyEpsilon.get(e);
 186             if (ret != null) return ret.booleanValue();
 187             ret = new Walk.PossiblyEpsilon().walk(e) ? Boolean.TRUE : Boolean.FALSE;
 188             possiblyEpsilon.put(e, ret);
 189             return ret;
 190         }
 191     }
 192 }