src/edu/berkeley/fleet/assembler/Parser.java

   1 package edu.berkeley.fleet.assembler;
   2
   3 import edu.berkeley.fleet.api.*;
   4
   5 import edu.berkeley.sbp.*;
   6 import edu.berkeley.sbp.chr.*;
   7 import edu.berkeley.sbp.misc.*;
   8 import edu.berkeley.sbp.meta.*;
   9 import edu.berkeley.sbp.bind.*;
  10 import edu.berkeley.sbp.util.*;
  11 import java.util.*;
  12 import java.io.*;
  13
  14 /**
  15  *  @author Adam Megacz <megacz@cs.berkeley.edu>
  16  */
  17 class Parser {
  18
  19     Parser(Fleet fleet) {
  20         this.fleet = fleet;
  21     }
  22
  23     //////////////////////////////////////////////////////////////////////////////
  24
  25     private Fleet fleet;
  26     private ArrayList<String> imports = new ArrayList<String>();
  27
  28     private HashMap<String,Ship> shipMap = new HashMap<String,Ship>();
  29
  30     // codebags in numerical order
  31     private ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
  32     private HashMap<String,CodeBag> codeBagsByName = new HashMap<String,CodeBag>();
  33
  34     Tree<String> parse(Reader r) throws Exception {
  35         InputStream grammarStream =
  36             Parser.class.getClassLoader().getResourceAsStream("edu/berkeley/fleet/parser/fleet.g");
  37         CharParser metaGrammarParser   = new CharParser(MetaGrammar.newInstance());
  38         Tree<String> parsedGrammar = metaGrammarParser.parse(new CharInput(grammarStream)).expand1();
  39         Union   grammar            = Grammar.create(parsedGrammar, "s", new Grammar.Bindings() { });
  40         CharParser  parser             = new CharParser(grammar);
  41         Tree tree = parser.parse(new CharInput(r)).expand1();
  42         return tree;
  43     }
  44
  45     public void parse(Reader r, OutputStream out) throws Exception {
  46
  47         // this needs to be "code bag zero"
  48         CodeBag baseCodeBag = new CodeBag();
  49         CodeBag rootCodeBag = new CodeBag();
  50         baseCodeBag.add(new Instruction.Literal.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1));
  51         walk((Tree<String>)parse(r), rootCodeBag);
  52
  53         // map from arbitrary identifiers to actual addresses
  54         int[] codeBagMap = new int[codeBags.size()];
  55         ByteArrayOutputStream baos = new ByteArrayOutputStream();
  56         CountingOutputStream cos   = new CountingOutputStream(baos);
  57         DataOutputStream dos       = new DataOutputStream(cos);
  58         for(int i=0; i<codeBags.size(); i++) {
  59             CodeBag c = codeBags.get(i);
  60             dos.flush();
  61             codeBagMap[i] = cos.getCount();
  62             for(Instruction inst : c)
  63                 fleet.writeInstruction(dos, inst);
  64         }
  65
  66         // now write for real
  67         dos = new DataOutputStream(out);
  68         cos = new CountingOutputStream(dos);
  69         for(int i=0; i<codeBags.size(); i++) {
  70             CodeBag c = codeBags.get(i);
  71             dos.flush();
  72             for(Instruction inst : c) {
  73                 if (inst instanceof Instruction.Literal.CodeBagDescriptor) {
  74                     dos.flush();
  75                     cos.getCount();
  76                     Instruction.Literal.CodeBagDescriptor old = (Instruction.Literal.CodeBagDescriptor)inst;
  77                     int offset = fleet.computeOffset(cos.getCount(), codeBagMap[(int)old.offset]);
  78                     inst = new Instruction.Literal.CodeBagDescriptor(old.dest,
  79                                                                      offset,
  80                                                                      codeBags.get((int)old.offset).size());
  81                 }
  82                 fleet.writeInstruction(dos, inst);
  83             }
  84         }
  85         dos.flush();
  86     }
  87
  88     public void parse(Reader r, ArrayList<Instruction> out) throws Exception {
  89         // this needs to be "code bag zero"
  90         CodeBag baseCodeBag = new CodeBag();
  91         CodeBag rootCodeBag = new CodeBag();
  92         Instruction inst0 = new Instruction.Literal.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1);
  93         baseCodeBag.add(inst0);
  94         walk((Tree<String>)parse(r), rootCodeBag);
  95
  96         // map from arbitrary identifiers to actual addresses
  97         int[] codeBagMap = new int[codeBags.size()];
  98         ArrayList<Instruction> temp = new ArrayList<Instruction>();
  99         for(int i=0; i<codeBags.size(); i++) {
 100             codeBagMap[i] = temp.size();
 101             for(Instruction inst : codeBags.get(i))
 102                 temp.add(inst);
 103         }
 104
 105         // now write for real
 106         for(int i=0; i<codeBags.size(); i++) {
 107             CodeBag c = codeBags.get(i);
 108             for(Instruction inst : c) {
 109                 if (inst instanceof Instruction.Literal.CodeBagDescriptor) {
 110                     Instruction.Literal.CodeBagDescriptor old = (Instruction.Literal.CodeBagDescriptor)inst;
 111                     int offset = fleet.computeOffset(out.size(), codeBagMap[(int)old.offset]);
 112                     inst = new Instruction.Literal.CodeBagDescriptor(old.dest,
 113                                                                      offset,
 114                                                                      codeBags.get((int)old.offset).size());
 115                 }
 116                 out.add(inst);
 117             }
 118         }
 119     }
 120
 121     /** in the first pass, codebags are assigned "addresses" in arbitrary order */
 122     void walk(Tree<String> t, CodeBag cb) {
 123
 124         String head = t.head();
 125         if (head==null) {
 126         } else if (head.equals("Program")) {
 127             for(Tree<String> tc : t.child(0))
 128                 walk(tc, cb);
 129             if (t.size()>1)
 130                 for(Tree<String> statement : t.child(1))
 131                     fillCodeBag(statement, cb);
 132
 133         } else if (head.equals("Import")) {
 134             imports.add(string(t.child(0)));
 135
 136         } else if (head.equals("Ship")) {
 137             String name = name(t.child(0));
 138             String type = string(t.child(1));
 139             Ship ship = null;
 140             if (fleet instanceof edu.berkeley.fleet.interpreter.Interpreter) {
 141                 edu.berkeley.fleet.interpreter.Interpreter interpreter =
 142                     ((edu.berkeley.fleet.interpreter.Interpreter)fleet);
 143                 String classname = type;
 144                 boolean good = false;
 145                 for(String s : imports)
 146                     if ((ship = interpreter.tryCreate(s+"."+classname, name)) != null)
 147                         break;
 148                 if (ship==null)
 149                     throw new RuntimeException("couldn't find a ship called \""+classname+"\"");
 150             } else {
 151                 ship = allocateShip(type);
 152             }
 153             shipMap.put(name, ship);
 154
 155         } else if (head.equals("Include")) {
 156             try {
 157                 walk(parse(new InputStreamReader(new FileInputStream(string(t.child(0))))), cb);
 158             } catch (Exception e) {
 159                 throw new RuntimeException(e);
 160             }
 161
 162         } else if (head.equals("Memory")) {
 163             if (((edu.berkeley.fleet.interpreter.Interpreter)fleet).mem.length != 0)
 164                 throw new RuntimeException("multiple memory directives found");
 165             Tree<String> m = t.child(0);
 166             int[] mem = new int[m.size()];
 167             for(int i=0; i<mem.length; i++)
 168                 mem[i] = Integer.parseInt(string(m.child(i)));
 169             ((edu.berkeley.fleet.interpreter.Interpreter)fleet).mem = mem;
 170         }
 171     }
 172
 173     String string(Tree<String> t) {
 174         String ret = "";
 175         if (t.head() != null) ret += t.head();
 176         for(Tree<String> c : t)
 177             ret += string(c);
 178         return ret;
 179     }
 180
 181     String name(Tree<String> t) {
 182         return string(t.child(0))+string(t.child(1));
 183     }
 184
 185     BenkoBox portReference(Tree<String> t) {
 186         if (!"Port".equals(t.head())) return null;
 187         String shipName = name(t.child(0));
 188         String portName = name(t.child(1));
 189         Ship ship = shipMap.get(shipName);
 190         if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
 191         for(BenkoBox b : ship.getBenkoBoxes())
 192             if (b.getName().equals(portName))
 193                 return b;
 194         throw new RuntimeException("no such benkobox \""+portName+"\" on ships of type \""+ship.getType()+"\"");
 195     }
 196
 197     private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
 198     Ship allocateShip(String shipType) {
 199         int allocated = 0;
 200         if (numAllocated.get(shipType) != null)
 201             allocated = numAllocated.get(shipType);
 202         numAllocated.put(shipType, allocated+1);
 203         for(Iterator<Ship> it = fleet.iterator();
 204             it.hasNext();
 205             ) {
 206             Ship s = it.next();
 207             if (s.getType().equals(shipType)) {
 208                 if (allocated == 0) return s;
 209                 allocated--;
 210             }
 211         }
 212         throw new RuntimeException("no more ships of type \""+shipType+"\"");
 213     }
 214
 215     void fillCodeBag(Tree<String> t, CodeBag cb) {
 216         if (t.head()==null) return;
 217         else if (t.head().equals("NamedCodeBag")) {
 218             CodeBag cb2 = new CodeBag(name(t.child(0)));
 219             for(Tree<String> statement : t.child(1))
 220                 fillCodeBag(statement, cb2);
 221
 222         } else if (t.head().equals("Literal")) {
 223             int literal = Integer.parseInt(string(t.child(0)));
 224             BenkoBox benkobox = portReference(t.child(1));
 225             cb.add(new Instruction.Literal.Absolute(benkobox, literal));
 226
 227         } else if (t.head().equals("Fiber")) {
 228             BenkoBox benkobox = portReference(t.child(0));
 229
 230             OUTER: for(Tree tt : t.child(1)) {
 231                 int count = 1;
 232                 Tree ttx = null;
 233                 boolean recycle = false;
 234                 ttx = tt.child(1);
 235                 if (tt.size() > 1) {
 236                     tt = tt.child(0);
 237                     if (tt.size() > 0 && tt.child(0).size()>0) {
 238                         tt = tt.child(0);
 239                         if (tt.child(0).size() == 0) count=1;
 240                         else if (tt.child(0).size() > 0 && "Star".equals(tt.child(0).child(0).head())) count=0;
 241                         else count = Integer.parseInt(string(tt.child(0)));
 242                         if (tt.size() > 1 && tt.child(1).size() > 0)
 243                             recycle = true;
 244                     }
 245                 }
 246                 boolean tokenIn = false;
 247                 boolean dataIn = false;
 248                 boolean latch = false;
 249                 boolean dataOut = false;
 250                 boolean tokenOut = false;
 251                 BenkoBox dest = null;
 252                 for(int i=0; i<ttx.size(); i++) {
 253                     Tree ttt = ttx.child(i);
 254                     if      ("Wait".equals(ttt.head()))    { tokenIn = true; }
 255                     else if ("Nop".equals(ttt.head()))     { }
 256                     else if ("Kill".equals(ttt.head()))    {
 257                         cb.add(new Instruction.Kill(benkobox, count));
 258                         continue OUTER;
 259                     }
 260                     else if ("Discard".equals(ttt.head())) { dataIn = true; latch = false; }
 261                     else if ("Take".equals(ttt.head()))    { dataIn = true; latch = true; }
 262                     else if ("SendTo".equals(ttt.head()))  { dataOut = true; dest = portReference(ttt.child(0)); }
 263                     else if ("Deliver".equals(ttt.head())) { dataOut = true;  }
 264                     else if ("Ack".equals(ttt.head()))     { tokenOut = true; dest = portReference(ttt.child(0)); }
 265                 }
 266                 cb.add(new Instruction.Executable(benkobox,
 267                                                   dest, count, tokenIn, dataIn,
 268                                                   latch, dataOut, tokenOut, recycle));
 269             }
 270         }
 271     }
 272
 273     private static class CountingOutputStream extends FilterOutputStream {
 274         public CountingOutputStream(OutputStream os) { super(os); }
 275         int count = 0;
 276         public int getCount() { return count; }
 277         public void write(int b) throws IOException {
 278             super.write(b);
 279             count++;
 280         }
 281         public void write(byte[] b, int off, int len) throws IOException {
 282             super.write(b, off, len);
 283             count += len;
 284         }
 285     }
 286
 287     private class CodeBag extends ArrayList<Instruction> {
 288         public int address = -1;
 289         public CodeBag() { codeBags.add(this); }
 290         public CodeBag(String name) { this(); codeBagsByName.put(name, this); }
 291         public long getFakeAddress() { return codeBags.indexOf(this); }
 292         public boolean equals(Object o) { return this==o; }
 293     }
 294
 295 }