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