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(GrammarAST.getMetaGrammar());
  44         Tree<String> parsedGrammar     = metaGrammarParser.parse(new CharInput(grammarStream)).expand1();
  45         grammar                        = GrammarAST.buildFromAST(parsedGrammar, "s", new GrammarAST.ImportResolver() {
  46                 public InputStream getImportStream(String importname) { return null; }
  47             });
  48         return grammar;
  49     }
  50
  51     Tree<String> parse(Reader r) throws Exception {
  52         return new CharParser(getGrammar()).parse(new CharInput(r)).expand1();
  53     }
  54
  55     public void parse(Reader r, OutputStream out) throws Exception {
  56         // this needs to be "code bag zero"
  57         CodeBag baseCodeBag = new CodeBag();
  58         CodeBag rootCodeBag = new CodeBag();
  59         skip = false;
  60         baseCodeBag.add(new Instruction.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1));
  61         walk((Tree<String>)parse(r), rootCodeBag);
  62         if (fleet instanceof edu.berkeley.fleet.fpga.Fpga)
  63             ((edu.berkeley.fleet.fpga.Fpga)fleet).dumpFabric(true);
  64
  65         // map from arbitrary identifiers to actual addresses
  66         int[] codeBagMap = new int[codeBags.size()];
  67         ByteArrayOutputStream baos = new ByteArrayOutputStream();
  68         DataOutputStream dos       = new DataOutputStream(baos);
  69         int count = 0;
  70         for(int i=0; i<codeBags.size(); i++) {
  71             CodeBag c = codeBags.get(i);
  72             dos.flush();
  73             codeBagMap[i] = count;
  74             for(Instruction inst : c) {
  75                 fleet.writeInstruction(dos, inst);
  76                 count++;
  77             }
  78         }
  79
  80         // now write for real
  81         dos = new DataOutputStream(out);
  82         count = 0;
  83         for(int i=0; i<codeBags.size(); i++) {
  84             CodeBag c = codeBags.get(i);
  85             dos.flush();
  86             for(Instruction inst : c) {
  87                 if (inst instanceof Instruction.CodeBagDescriptor) {
  88                     dos.flush();
  89                     Instruction.CodeBagDescriptor old = (Instruction.CodeBagDescriptor)inst;
  90                     int offset = codeBagMap[(int)old.offset];// - count;
  91                     inst = new Instruction.CodeBagDescriptor(old.pump,
  92                                                                      offset,
  93                                                                      codeBags.get((int)old.offset).size());
  94                 }
  95                 fleet.writeInstruction(dos, inst);
  96                 count++;
  97             }
  98         }
  99         dos.flush();
 100         out.flush();
 101         out.close();
 102     }
 103
 104     /** in the first pass, codebags are assigned "addresses" in arbitrary order */
 105     void walk(Tree<String> t, CodeBag cb) {
 106
 107         String head = t.head();
 108         if (head==null) {
 109         } else if (head.equals("Program")) {
 110             for(Tree<String> tc : t.child(0))
 111                 walk(tc, cb);
 112             if (t.size()>1)
 113                 for(Tree<String> statement : t.child(1))
 114                     fillCodeBag(statement, cb);
 115
 116         } else if (head.equals("#import")) {
 117             // ignored
 118
 119         } else if (head.equals("#ship")) {
 120             String name = name(t.child(0));
 121             String type = string(t.child(1));
 122             Ship ship = null;
 123
 124             if (fleet instanceof Fleet.WithDynamicShips) {
 125                 Fleet.WithDynamicShips dyn = ((Fleet.WithDynamicShips)fleet);
 126                 ship = dyn.createShip(type, name);
 127                 if (ship==null)
 128                     throw new RuntimeException("couldn't find a ship called \""+type+"\"");
 129             } else {
 130                 ship = allocateShip(type);
 131             }
 132             shipMap.put(name, ship);
 133
 134         } else if (head.equals("#include")) {
 135             try {
 136                 walk(parse(new InputStreamReader(new FileInputStream(string(t.child(0))))), cb);
 137             } catch (Exception e) {
 138                 throw new RuntimeException(e);
 139             }
 140
 141         } else if (head.equals("#expect")) {
 142             expect.add(number(t.child(0)));
 143         } else if (head.equals("#skip")) {
 144             skip = true;
 145
 146         }
 147     }
 148
 149     String string(Tree<String> t) {
 150         String ret = "";
 151         if (t.head() != null) ret += t.head();
 152         for(Tree<String> c : t)
 153             ret += string(c);
 154         return ret;
 155     }
 156
 157     String stringBody(Tree<String> t) {
 158         String ret = "";
 159         for(Tree<String> c : t)
 160             ret += string(c);
 161         return ret;
 162     }
 163
 164     String name(Tree<String> t) {
 165         return string(t.child(0))+string(t.child(1));
 166     }
 167
 168     Destination portReference(Tree<String> t) {
 169         if (!"Pump".equals(t.head()) && !"Destination".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head())) return null;
 170         String shipName = name(t.child(0));
 171         String portName = name(t.child(1));
 172         String subPort = t.size()<3 ? null : name(t.child(2));
 173         Ship ship = shipMap.get(shipName);
 174         if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
 175         Destination ret = null;
 176         Pump bb = null;
 177         for(Pump b : ship.getPumps())
 178             if (b.getName().equals(portName)) {
 179                 bb = b;
 180             }
 181         if (bb==null)
 182             throw new RuntimeException("no such pump \""+portName+"\"");
 183         if (subPort==null) subPort="";
 184         for(Destination d : bb.getDestinations())
 185             if (d.getDestinationName().equals(subPort))
 186                 return d;
 187         if (ret==null)
 188             throw new RuntimeException("no such pump \""+portName+"\" on ships of type \""+ship.getType()+"\"");
 189         return ret;
 190     }
 191
 192     Pump pump(Tree<String> t) {
 193         if (!"Pump".equals(t.head()) && !"Destination".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head()))
 194             throw new RuntimeException(t+"");
 195         String shipName = name(t.child(0));
 196         String portName = name(t.child(1));
 197         Ship ship = shipMap.get(shipName);
 198         if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
 199         Pump bb = null;
 200         for(Pump b : ship.getPumps())
 201             if (b.getName().equals(portName))
 202                 return b;
 203         throw new RuntimeException("no such pump \""+portName+"\"");
 204     }
 205
 206     private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
 207
 208     Ship allocateShip(String shipType) {
 209         int allocated = 0;
 210         if (numAllocated.get(shipType) != null)
 211             allocated = numAllocated.get(shipType);
 212         numAllocated.put(shipType, allocated+1);
 213         for(Iterator<Ship> it = fleet.iterator();
 214             it.hasNext();
 215             ) {
 216             Ship s = it.next();
 217             if (s.getType().equals(shipType)) {
 218                 if (allocated == 0) return s;
 219                 allocated--;
 220             }
 221         }
 222         throw new RuntimeException("no more ships of type \""+shipType+"\"");
 223     }
 224
 225     private long parseSSL(Tree t) {
 226         String shipType = name(t.child(0));
 227         String portName = name(t.child(1));
 228         Ship chosenship = null;
 229         for(Ship ship : fleet) {
 230             if (ship.getType().equals(shipType)) {
 231                 chosenship = ship;
 232                 break;
 233             }
 234         }
 235         Pump chosenport = chosenship.getPump(portName);
 236         Tree specs = t.child(2);
 237         long literal = 0;
 238         for(int i=0; i<specs.size(); i++) {
 239             Tree tt = specs.child(i);
 240             literal |= chosenport.resolveLiteral(stringBody(tt));
 241         }
 242         return literal;
 243     }
 244
 245     private int anoncount = 1;
 246     void fillCodeBag(Tree<String> t, CodeBag cb) {
 247         if (t.head()==null) return;
 248         else if (t.head().equals("CodeBagDef")) {
 249             CodeBag cb2 = getCodeBag(name(t.child(0)));
 250             for(Tree<String> statement : t.child(1))
 251                 fillCodeBag(statement, cb2);
 252
 253         } else if (t.head().equals("Fiber")) {
 254             Pump pump = (Pump)pump(t.child(0));
 255
 256             OUTER: for(Tree tt : t.child(1)) {
 257                 int count = 1;
 258                 if ("unclog".equals(tt.head()))    {
 259                     cb.add(new Instruction.UnClog(pump));
 260                     continue;
 261                 } else if ("clog".equals(tt.head()))    {
 262                     cb.add(new Instruction.Clog(pump));
 263                     continue;
 264                 } else if ("kill".equals(tt.head()))    {
 265                     count = tt.size()==0 ? 1 : (int)number(tt.child(0));
 266                     cb.add(new Instruction.Kill(pump, count));
 267                     continue;
 268                 } else if ("massacre".equals(tt.head()))    {
 269                     cb.add(new Instruction.Massacre(pump));
 270                     continue;
 271                 } else if ("literal".equals(tt.head()))  {
 272                     long literal = 0;
 273                     if (tt.child(0).head().equals("CodeBagBody")) {
 274                         Tree<String> tq = tt;
 275                         CodeBag cb2 = getCodeBag("anon"+(anoncount++));
 276                         for(Tree<String> statement : tq.child(0))
 277                             fillCodeBag(statement, cb2);
 278                         cb.add(new Instruction.CodeBagDescriptor(pump, cb2.getFakeAddress(), 0));
 279                         continue OUTER;
 280                     } else if (tt.child(0).head().equals("Name")) {
 281                         String refname = name(tt.child(0));
 282                         CodeBag cb2 = getCodeBag(refname);
 283                         cb.add(new Instruction.CodeBagDescriptor(pump, cb2.getFakeAddress(), 0));
 284                         continue OUTER;
 285                     } else if (tt.child(0).head().equals("[")) {
 286                         literal = parseSSL(tt.child(0));
 287                     } else {
 288                         literal = number(tt.child(0));
 289                     }
 290                     count = 1;
 291                     if ("int".equals(tt.child(1).head())) {
 292                         count = (int)number(tt.child(1));
 293                     } else if ("forever".equals(tt.child(1).head())) {
 294                         count = 0;
 295                     }
 296                     cb.add(new Instruction.LocalLiteral(pump, literal, count));
 297                     continue;
 298                 }
 299                 Tree ttx = null;
 300                 boolean requeue = false;
 301                 ttx = tt.child(1).head().equals("Commands") ? tt.child(1) : tt;
 302                 if ("int".equals(tt.child(2).head())) {
 303                     count = (int)number(tt.child(2));
 304                     requeue = true;
 305                 } else if ("forever".equals(tt.child(2).head())) {
 306                     count = 0;
 307                     requeue = true;
 308                 }
 309                 tt = tt.child(0);
 310                 if (tt.head().equals("[*]")) {
 311                     count = 0;
 312                     requeue = false;
 313                 } else if (tt.head().equals("int")) {
 314                     count = (int)number(tt);
 315                     requeue = false;
 316                 }
 317                 boolean tokenIn = false;
 318                 boolean dataIn = false;
 319                 boolean latch = false;
 320                 boolean dataOut = false;
 321                 boolean tokenOut = false;
 322                 boolean dataOutDest = false;
 323                 boolean localLiteral = false;
 324                 boolean ignoreUntilLast = false;
 325                 long literal = 0;
 326                 Destination dest = null;
 327                 for(int i=0; i<ttx.size(); i++) {
 328                     Tree ttt = ttx.child(i);
 329                     if      ("wait".equals(ttt.head()))    { tokenIn = true; }
 330                     else if ("nop".equals(ttt.head()))     { }
 331                     else if ("kill".equals(ttt.head()))    {
 332                         cb.add(new Instruction.Kill(pump, count));
 333                         continue OUTER;
 334                     }
 335                     else if ("discard".equals(ttt.head())) { dataIn = true; latch = false; }
 336                     else if ("take".equals(ttt.head()))    { dataIn = true; latch = true; }
 337                     else if ("recieve".equals(ttt.head()))    { dataIn = true; latch = true; }
 338                     else if ("send".equals(ttt.head()))  { dataOutDest = true; }
 339                     else if ("sendto".equals(ttt.head()))  { dataOut = true; dest = portReference(ttt.child(0)); }
 340                     else if ("deliver".equals(ttt.head())) { dataOut = true;  }
 341                     else if ("notify".equals(ttt.head()))     { tokenOut = true; dest = portReference(ttt.child(0)); }
 342                     else if ("notifyLast".equals(ttt.head()))     { tokenOut = true; ignoreUntilLast = true; dest = portReference(ttt.child(0)); }
 343                 }
 344                     cb.add(new Instruction.Move(pump,
 345                                                 dest, count, tokenIn, dataIn,
 346                                                 latch, dataOutDest, dataOut, tokenOut, requeue, ignoreUntilLast));
 347             }
 348         }
 349     }
 350
 351     private class CodeBag extends ArrayList<Instruction> {
 352         public long address = -1;
 353         public final String name;
 354         public CodeBag() { codeBags.add(this); this.name = "root"; }
 355         public CodeBag(String name) { codeBags.add(this); codeBagsByName.put(name, this); this.name = name; }
 356         public long getFakeAddress() { return codeBags.indexOf(this); }
 357         public boolean equals(Object o) { return this==o; }
 358     }
 359
 360     // hideous hack
 361     public static ArrayList<Long> expect;
 362     public static boolean         skip;
 363
 364     private static long number(Tree t) {
 365         String ret = "";
 366         for(Object c : t.child(2)) ret += ((Tree)c).head();
 367         boolean negative = "-".equals(t.child(0).head());
 368         ret = ret.trim();
 369         long val = 0;
 370         if      ("0x".equals(t.child(1).head())) val = Long.parseLong(ret, 16);
 371         else if ("0b".equals(t.child(1).head())) val = Long.parseLong(ret, 2);
 372         else                                     val = Long.parseLong(ret);
 373         if (negative) val = -1L * val;
 374         return val;
 375     }
 376 }