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

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