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