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
  43                 // FIXME
  44                 for(Sequence ss : s.needs()) ret = union((Union)e, ret, walk(ss));
  45                 for(Sequence ss : s.hates()) ret = union((Union)e, ret, walk(ss));
  46             }
  47             return ret;
  48         } else {
  49             throw new Error("unknown element of class " + e.getClass().getName() + ": " + e);
  50         }
  51     }
  52
  53     static class YieldSet extends Walk<HashSet<Element>> {
  54         private final Element e;
  55         public final HashSet<Element> walk() { return walk(e); }
  56         public YieldSet(Element e, Cache c)  { super(c); this.e = e; }
  57         public HashSet<Element> bottom(Element e)     { return acc; }
  58         public HashSet<Element> sequence(Sequence seq) { return bottom(seq); }
  59         public HashSet<Element> walkAtom(Atom r) {
  60             c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r));
  61             return super.walkAtom(r);
  62         }
  63     }
  64
  65
  66     // Boolean //////////////////////////////////////////////////////////////////////////////
  67
  68     static class PossiblyEpsilon extends Walk<Boolean> {
  69         public Boolean walkAtom(Atom r) { return false; }
  70         public Boolean sequence(Sequence s, Boolean a, Boolean b)  { return new Boolean(a && b); }
  71         public Boolean union(Union u, Boolean a, Boolean b)     { return new Boolean(a || b); }
  72         public Boolean bottom(Element e)    { return (e instanceof Union) ? false : true; }
  73         private HashMap<Element,Boolean> hm = new HashMap<Element,Boolean>();
  74         protected Boolean walk(Element e) {
  75             if (hm.get(e) != null) return hm.get(e);
  76             hm.put(e, false);
  77             Boolean ret = walk2(e);
  78             hm.put(e, ret);
  79             return ret;
  80         }
  81     }
  82
  83
  84     // Input-Set //////////////////////////////////////////////////////////////////////////////
  85
  86     static abstract class WalkTokenSet<Tok extends Input> extends Walk<Topology<Tok>> {
  87         public Topology<Tok> cs;
  88         public WalkTokenSet(Topology<Tok> cs)          { this.cs = cs; }
  89         public WalkTokenSet(Topology<Tok> cs, Cache c) { super(c); this.cs = cs; }
  90         public Topology<Tok> bottom(Element e)         { return cs; }
  91         public Topology<Tok> walkAtom(Atom r)          { cs = cs.union(r); return cs; }
  92     }
  93
  94     static class First<Tok extends Input> extends WalkTokenSet<Tok> {
  95         public First(Topology<Tok> cs, Walk.Cache cache) { super(cs, cache); }
  96         public Topology<Tok> sequence(Sequence seq) {
  97             for(Position p = seq.firstp(); p!=null && !p.isLast(); p = p.next()) {
  98                 walk(p.element());
  99                 if (!c.possiblyEpsilon(p.element())) break;
 100             }
 101             return cs;
 102         }
 103     }
 104
 105     static class Follow<Tok extends Input> extends WalkTokenSet<Tok> {
 106         private final Element me;
 107         private final HashSet<Element> all;
 108         private boolean eof = false;
 109         public boolean includesEof() { return eof; }
 110         public Follow(Topology<Tok> cs, Element me, HashSet<Element> all, Cache c)  { super(cs, c); this.me = me; this.all = all; }
 111         public Topology<Tok> bottom(Element e)                       { return cs; }
 112         public Topology<Tok> sequence(Sequence seq)                  { return cs; }
 113         public Topology<Tok> walkAtom(Atom r) { return walk((Element)r); }
 114         public Topology<Tok> walk(Element e) {
 115             if (acc.contains(e)) return bottom(e);
 116             acc.add(e);
 117
 118             if (c != null) {
 119                 Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
 120                 if (cached != null) {
 121                     cs = cs.union(cached);
 122                     eof |= c.eof.get(e);
 123                     return cs;
 124                 }
 125             }
 126
 127             Topology<Tok> cso = cs;
 128             boolean eofo = eof;
 129             eof = c.eof.get(e) != null && c.eof.get(e).booleanValue();
 130             cs = cso.empty();
 131
 132             for(Element x : all) {
 133                 boolean matched = false;
 134                 if (!(x instanceof Sequence)) continue;
 135                 Sequence a = (Sequence)x;
 136                 Position mp = null;
 137                 for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) {
 138                     if (matched) cs = cs.union(c.first(pos.element(), cs.empty()));
 139                     if (pos.isLast()) { matched = (matched && c.possiblyEpsilon(pos.element())); continue; }
 140                     boolean good = false;
 141                     if (e instanceof Atom) {
 142                         Topology top = c.atoms.get(pos.element());
 143                         if (top==null) continue;
 144                         if (!(top.containsAll(((Atom)e)))) continue;
 145                     } else {
 146                         if (c.ys.contains(pos.element(),e)) good = true;
 147                     }
 148                     if (good) {
 149                         mp = pos;
 150                         matched = true;
 151                     }
 152                 }
 153                 if (matched) walk(a);
 154             }
 155
 156             if (e instanceof Sequence) {
 157                 Sequence s = (Sequence)e;
 158                 if (s.follow() != null) cs = cs.intersect(s.follow());
 159             }
 160
 161             if (c != null && e==me) {
 162                 c.follow.put(e, cs);
 163                 c.eof.put(e, eof);
 164             }
 165
 166             cso = cso.union(cs);
 167             cs = cso;
 168             eofo |= eof;
 169             eof = eofo;
 170
 171             return cs;
 172         }
 173     }
 174
 175     static class Cache {
 176         public final HashMap<Element,Boolean> possiblyEpsilon = new HashMap<Element,Boolean>();
 177         public HashMap<Element,Boolean> eof = new HashMap<Element,Boolean>();
 178         public HashMap<Element,Topology> follow = new HashMap<Element,Topology>();
 179         public HashMapBag<Element,Element>  ys = new HashMapBag<Element,Element>();
 180         public HashMap<Element,Topology> atoms = new HashMap<Element,Topology>();
 181         public <Tok extends Input> Topology<Tok> first(Element e, Topology<Tok> empty) {
 182             return new Walk.First<Tok>(empty, this).walk(e);
 183         }
 184         final boolean possiblyEpsilon(Element e) {
 185             Walk.Cache cache = this;
 186             Boolean ret = possiblyEpsilon.get(e);
 187             if (ret != null) return ret.booleanValue();
 188             ret = new Walk.PossiblyEpsilon().walk(e) ? Boolean.TRUE : Boolean.FALSE;
 189             possiblyEpsilon.put(e, ret);
 190             return ret;
 191         }
 192     }
 193 }