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