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.util.*;
   8 import java.util.*;
   9 import java.io.*;
  10
  11 /**
  12  *  @author Adam Megacz <megacz@cs.berkeley.edu>
  13  */
  14 public class Parser {
  15
  16     Parser(Fleet fleet) {
  17         expect = new ArrayList<Long>();
  18         this.fleet = fleet;
  19     }
  20
  21     //////////////////////////////////////////////////////////////////////////////
  22
  23     private Fleet fleet;
  24     private ArrayList<String> imports = new ArrayList<String>();
  25
  26     private HashMap<String,Ship> shipMap = new HashMap<String,Ship>();
  27
  28     // codebags in numerical order
  29     private ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
  30     private HashMap<String,CodeBag> codeBagsByName = new HashMap<String,CodeBag>();
  31
  32     private CodeBag getCodeBag(String name) {
  33         CodeBag cb = codeBagsByName.get(name);
  34         if (cb!=null) return cb;
  35         return new CodeBag(name);
  36     }
  37
  38     private static Union grammar;
  39     private static synchronized Union getGrammar() throws Exception {
  40         if (grammar != null) return grammar;
  41         InputStream grammarStream =
  42             Parser.class.getClassLoader().getResourceAsStream("edu/berkeley/fleet/assembler/fleet.g");
  43         CharParser metaGrammarParser   = new CharParser(MetaGrammar.newInstance());
  44         Tree<String> parsedGrammar     = metaGrammarParser.parse(new CharInput(grammarStream)).expand1();
  45         grammar                        = GrammarAST.buildFromAST(parsedGrammar, "s", new File[0]);
  46         return grammar;
  47     }
  48
  49     Tree<String> parse(Reader r) throws Exception {
  50         return new CharParser(getGrammar()).parse(new CharInput(r)).expand1();
  51     }
  52
  53     public void parse(Reader r, OutputStream out) throws Exception {
  54         // this needs to be "code bag zero"
  55         CodeBag baseCodeBag = new CodeBag();
  56         CodeBag rootCodeBag = new CodeBag();
  57         skip = false;
  58         baseCodeBag.add(new Instruction.Literal.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1));
  59         walk((Tree<String>)parse(r), rootCodeBag);
  60         if (fleet instanceof edu.berkeley.fleet.fpga.Fpga)
  61             ((edu.berkeley.fleet.fpga.Fpga)fleet).dumpFabric(true);
  62
  63         // map from arbitrary identifiers to actual addresses
  64         int[] codeBagMap = new int[codeBags.size()];
  65         ByteArrayOutputStream baos = new ByteArrayOutputStream();
  66         DataOutputStream dos       = new DataOutputStream(baos);
  67         int count = 0;
  68         for(int i=0; i<codeBags.size(); i++) {
  69             CodeBag c = codeBags.get(i);
  70             dos.flush();
  71             codeBagMap[i] = count;
  72             for(Instruction inst : c) {
  73                 fleet.writeInstruction(dos, inst);
  74                 count++;
  75             }
  76         }
  77
  78         // now write for real
  79         dos = new DataOutputStream(out);
  80         count = 0;
  81         for(int i=0; i<codeBags.size(); i++) {
  82             CodeBag c = codeBags.get(i);
  83             dos.flush();
  84             for(Instruction inst : c) {
  85                 if (inst instanceof Instruction.Literal.CodeBagDescriptor) {
  86                     dos.flush();
  87                     Instruction.Literal.CodeBagDescriptor old = (Instruction.Literal.CodeBagDescriptor)inst;
  88                     int offset = codeBagMap[(int)old.offset];// - count;
  89                     inst = new Instruction.Literal.CodeBagDescriptor(old.pump,
  90                                                                      offset,
  91                                                                      codeBags.get((int)old.offset).size());
  92                     //System.out.println("cbd: " + offset + " " + codeBags.get((int)old.offset).size() + " " + codeBags.get((int)old.offset).name + " " + codeBags.get((int)old.offset));
  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         } else if (head.equals("Skip")) {
 143             skip = true;
 144
 145         }
 146     }
 147
 148     String string(Tree<String> t) {
 149         String ret = "";
 150         if (t.head() != null) ret += t.head();
 151         for(Tree<String> c : t)
 152             ret += string(c);
 153         return ret;
 154     }
 155
 156     String name(Tree<String> t) {
 157         return string(t.child(0))+string(t.child(1));
 158     }
 159
 160     Destination portReference(Tree<String> t) {
 161         if (!"Port".equals(t.head()) && !"SubPort".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head())) return null;
 162         String shipName = name(t.child(0));
 163         String portName = name(t.child(1));
 164         String subPort = t.size()<3 ? null : name(t.child(2));
 165         Ship ship = shipMap.get(shipName);
 166         if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
 167         Destination ret = null;
 168         Pump bb = null;
 169         for(Pump b : ship.getPumps())
 170             if (b.getName().equals(portName)) {
 171                 bb = b;
 172             }
 173         if (bb==null)
 174             throw new RuntimeException("no such pump \""+portName+"\"");
 175         if (subPort==null) subPort="";
 176         for(Destination d : bb.getDestinations())
 177             if (d.getDestinationName().equals(subPort))
 178                 return d;
 179         if (ret==null)
 180             throw new RuntimeException("no such pump \""+portName+"\" on ships of type \""+ship.getType()+"\"");
 181         return ret;
 182     }
 183
 184     Pump pump(Tree<String> t) {
 185         if (!"Port".equals(t.head()) && !"SubPort".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head()))
 186             throw new RuntimeException(t+"");
 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         Pump bb = null;
 192         for(Pump b : ship.getPumps())
 193             if (b.getName().equals(portName))
 194                 return b;
 195         throw new RuntimeException("no such pump \""+portName+"\"");
 196     }
 197
 198     private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
 199
 200     Ship allocateShip(String shipType) {
 201         int allocated = 0;
 202         if (numAllocated.get(shipType) != null)
 203             allocated = numAllocated.get(shipType);
 204         numAllocated.put(shipType, allocated+1);
 205         for(Iterator<Ship> it = fleet.iterator();
 206             it.hasNext();
 207             ) {
 208             Ship s = it.next();
 209             if (s.getType().equals(shipType)) {
 210                 if (allocated == 0) return s;
 211                 allocated--;
 212             }
 213         }
 214         throw new RuntimeException("no more ships of type \""+shipType+"\"");
 215     }
 216
 217     private long parseSSL(Tree t) {
 218         String shipType = name(t.child(0));
 219         String portName = name(t.child(1));
 220         Ship chosenship = null;
 221         for(Ship ship : fleet) {
 222             if (ship.getType().equals(shipType)) {
 223                 chosenship = ship;
 224                 break;
 225             }
 226         }
 227         Pump chosenport = chosenship.getPump(portName);
 228         Tree specs = t.child(2);
 229         long literal = 0;
 230         for(int i=0; i<specs.size(); i++) {
 231             Tree tt = specs.child(i);
 232             literal |= chosenport.resolveLiteral(string(tt));
 233         }
 234         return literal;
 235     }
 236
 237     void fillCodeBag(Tree<String> t, CodeBag cb) {
 238         if (t.head()==null) return;
 239         else if (t.head().equals("NamedCodeBag")) {
 240             CodeBag cb2 = getCodeBag(name(t.child(0)));
 241             for(Tree<String> statement : t.child(1))
 242                 fillCodeBag(statement, cb2);
 243
 244         } else if (t.head().equals("Fiber")) {
 245             Pump pump = (Pump)pump(t.child(0));
 246
 247             OUTER: for(Tree tt : t.child(1)) {
 248                 int count = 1;
 249                 Tree ttx = null;
 250                 boolean requeue = false;
 251                 ttx = tt.child(1);
 252                 if (tt.size() > 1 && tt.child(0).size()>0) {
 253                     tt = tt.child(0).child(0);
 254                     if (tt.head().equals("BrackStar")) {
 255                         count = 0;
 256                         requeue = false;
 257                     } else if (tt.head().equals("ParenStar")) {
 258                         count = 0;
 259                         requeue = true;
 260                     } else if (tt.head().equals("Brack")) {
 261                         count = Integer.parseInt(string(tt.child(0)));
 262                         requeue = false;
 263                     } else if (tt.head().equals("Paren")) {
 264                         count = Integer.parseInt(string(tt.child(0)));
 265                         requeue = true;
 266                     }
 267                 }
 268                 boolean tokenIn = false;
 269                 boolean dataIn = false;
 270                 boolean latch = false;
 271                 boolean dataOut = false;
 272                 boolean tokenOut = false;
 273                 boolean dataOutDest = false;
 274                 boolean localLiteral = false;
 275                 long literal = 0;
 276                 Destination dest = null;
 277                 for(int i=0; i<ttx.size(); i++) {
 278                     Tree ttt = ttx.child(i);
 279                     if      ("Wait".equals(ttt.head()))    { tokenIn = true; }
 280                     else if ("Nop".equals(ttt.head()))     { }
 281                     else if ("KillStar".equals(ttt.head()))    {
 282                         cb.add(new Instruction.Kill(pump, count, true));
 283                         continue OUTER;
 284                     } else if ("Kill".equals(ttt.head()))    {
 285                         cb.add(new Instruction.Kill(pump, count, false));
 286                         continue OUTER;
 287                     }
 288                     else if ("Discard".equals(ttt.head())) { dataIn = true; latch = false; }
 289                     else if ("Take".equals(ttt.head()))    { dataIn = true; latch = true; }
 290                     else if ("SendTo".equals(ttt.head()))  { dataOut = true; dest = portReference(ttt.child(0)); }
 291                     else if ("LocalLiteral".equals(ttt.head()))  { localLiteral = true; literal = Long.parseLong(string(ttt.child(0))); }
 292                     else if ("LocalLiteralCodeBag".equals(ttt.head()))  {
 293                         String refname = name(ttt.child(0).child(0));
 294                         CodeBag cb2 = getCodeBag(refname);
 295                         cb.add(new Instruction.Literal.CodeBagDescriptor(pump, cb2.getFakeAddress(), 0));
 296                         continue OUTER;
 297                     } else if ("LocalLiteralConst".equals(ttt.head()))  {
 298                         localLiteral = true;
 299                         literal = parseSSL(ttt.child(0));
 300                     }
 301                     else if ("DataOutDest".equals(ttt.head()))  { dataOutDest = true; }
 302                     else if ("Deliver".equals(ttt.head())) { dataOut = true;  }
 303                     else if ("Ack".equals(ttt.head()))     { tokenOut = true; dest = portReference(ttt.child(0)); }
 304                 }
 305                 if (localLiteral)
 306                     cb.add(new Instruction.LocalLiteral(pump, literal));
 307                 else
 308                     cb.add(new Instruction.Executable(pump,
 309                                                       dest, count, tokenIn, dataIn,
 310                                                       latch, dataOutDest, dataOut, tokenOut, requeue));
 311             }
 312         }
 313     }
 314
 315     private class CodeBag extends ArrayList<Instruction> {
 316         public long address = -1;
 317         public final String name;
 318         public CodeBag() { codeBags.add(this); this.name = "root"; }
 319         public CodeBag(String name) { codeBags.add(this); codeBagsByName.put(name, this); this.name = name; }
 320         public long getFakeAddress() { return codeBags.indexOf(this); }
 321         public boolean equals(Object o) { return this==o; }
 322     }
 323
 324     // hideous hack
 325     public static ArrayList<Long> expect;
 326     public static boolean         skip;
 327
 328 }