src/edu/berkeley/sbp/Walk.java

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