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 ("loop".equals(tt.head()))    {
 270                     cb.add(new Instruction.Counter(pump, Instruction.Counter.LOOP_COUNTER, Instruction.Counter.DATA_LATCH));
 271                     continue;
 272                 } else if ("load".equals(tt.head()) && "loop".equals(tt.child(0).head()))    {
 273                     cb.add(new Instruction.Counter(pump, Instruction.Counter.DATA_LATCH, Instruction.Counter.LOOP_COUNTER));
 274                     continue;
 275                 } else if ("load".equals(tt.head()) && "repeat".equals(tt.child(0).head()))    {
 276                     cb.add(new Instruction.Counter(pump, Instruction.Counter.DATA_LATCH, Instruction.Counter.REPEAT_COUNTER));
 277                     continue;
 278                 } else if ("with".equals(tt.head()) && "loop".equals(tt.child(0).head()))    {
 279                     cb.add(new Instruction.Counter(pump, (int)number(tt.child(1)), Instruction.Counter.LOOP_COUNTER));
 280                     continue;
 281                 } else if ("with".equals(tt.head()) && "repeat".equals(tt.child(0).head()))    {
 282                     cb.add(new Instruction.Counter(pump, (int)number(tt.child(1)), Instruction.Counter.REPEAT_COUNTER));
 283                     continue;
 284                 } else if ("massacre".equals(tt.head())) {
 285                     cb.add(new Instruction.Massacre(pump));
 286                     continue;
 287                 } else if ("decrement".equals(tt.head())) {
 288                     cb.add(new Instruction.DecrLoop(pump));
 289                     continue;
 290                 } else if ("literal".equals(tt.head())) {
 291                     long literal = 0;
 292                     if (tt.child(0).head().equals("CodeBagBody")) {
 293                         Tree<String> tq = tt;
 294                         CodeBag cb2 = getCodeBag("anon"+(anoncount++));
 295                         for(Tree<String> statement : tq.child(0))
 296                             fillCodeBag(statement, cb2);
 297                         cb.add(new Instruction.CodeBagDescriptor(pump, cb2.getFakeAddress(), 0));
 298                         continue OUTER;
 299                     } else if (tt.child(0).head().equals("Name")) {
 300                         String refname = name(tt.child(0));
 301                         CodeBag cb2 = getCodeBag(refname);
 302                         cb.add(new Instruction.CodeBagDescriptor(pump, cb2.getFakeAddress(), 0));
 303                         continue OUTER;
 304                     } else if (tt.child(0).head().equals("[")) {
 305                         literal = parseSSL(tt.child(0));
 306                     } else {
 307                         literal = number(tt.child(0));
 308                     }
 309                     count = 1;
 310                     if ("int".equals(tt.child(1).head())) {
 311                         count = (int)number(tt.child(1));
 312                     } else if ("forever".equals(tt.child(1).head())) {
 313                         count = 0;
 314                     }
 315                     cb.add(new Instruction.LocalLiteral(pump, getField(36, 19, literal), count, true));
 316                     cb.add(new Instruction.LocalLiteral(pump, getField(18,  0, literal), count, false));
 317                     continue;
 318                 }
 319                 Tree ttx = null;
 320                 boolean requeue = false;
 321                 ttx = tt.child(1).head().equals("Commands") ? tt.child(1) : tt;
 322                 if ("int".equals(tt.child(2).head())) {
 323                     count = (int)number(tt.child(2));
 324                     requeue = true;
 325                 } else if ("forever".equals(tt.child(2).head())) {
 326                     count = 0;
 327                     requeue = true;
 328                 }
 329                 tt = tt.child(0);
 330                 if (tt.head().equals("[*]")) {
 331                     count = 0;
 332                     requeue = false;
 333                 } else if (tt.head().equals("int")) {
 334                     count = (int)number(tt);
 335                     requeue = false;
 336                 }
 337                 boolean tokenIn = false;
 338                 boolean dataIn = false;
 339                 boolean latch = false;
 340                 boolean dataOut = false;
 341                 boolean tokenOut = false;
 342                 boolean dataOutDest = false;
 343                 boolean localLiteral = false;
 344                 boolean ignoreUntilLast = false;
 345                 long literal = 0;
 346                 Destination dest = null;
 347                 for(int i=0; i<ttx.size(); i++) {
 348                     Tree ttt = ttx.child(i);
 349                     if      ("wait".equals(ttt.head()))    { tokenIn = true; }
 350                     else if ("nop".equals(ttt.head()))     { }
 351                     else if ("kill".equals(ttt.head()))    {
 352                         cb.add(new Instruction.Kill(pump, count));
 353                         continue OUTER;
 354                     }
 355                     else if ("discard".equals(ttt.head())) { dataIn = true; latch = false; }
 356                     else if ("take".equals(ttt.head()))    { dataIn = true; latch = true; }
 357                     else if ("recieve".equals(ttt.head()))    { dataIn = true; latch = true; }
 358                     else if ("send".equals(ttt.head()))  { dataOutDest = true; }
 359                     else if ("sendto".equals(ttt.head()))  { dataOut = true; dest = portReference(ttt.child(0)); }
 360                     else if ("deliver".equals(ttt.head())) { dataOut = true;  }
 361                     else if ("notify".equals(ttt.head()))     { tokenOut = true; dest = portReference(ttt.child(0)); }
 362                     else if ("notifyLast".equals(ttt.head()))     { tokenOut = true; ignoreUntilLast = true; dest = portReference(ttt.child(0)); }
 363                 }
 364                     cb.add(new Instruction.Move(pump,
 365                                                 dest, count, tokenIn, dataIn,
 366                                                 latch, dataOutDest, dataOut, tokenOut, requeue, ignoreUntilLast));
 367             }
 368         }
 369     }
 370
 371     private class CodeBag extends ArrayList<Instruction> {
 372         public long address = -1;
 373         public final String name;
 374         public CodeBag() { codeBags.add(this); this.name = "root"; }
 375         public CodeBag(String name) { codeBags.add(this); codeBagsByName.put(name, this); this.name = name; }
 376         public long getFakeAddress() { return codeBags.indexOf(this); }
 377         public boolean equals(Object o) { return this==o; }
 378     }
 379
 380     // hideous hack
 381     public static ArrayList<Long> expect;
 382     public static boolean         skip;
 383
 384     private static long number(Tree t) {
 385         String ret = "";
 386         for(Object c : t.child(2)) ret += ((Tree)c).head();
 387         boolean negative = "-".equals(t.child(0).head());
 388         ret = ret.trim();
 389         long val = 0;
 390         if      ("0x".equals(t.child(1).head())) val = Long.parseLong(ret, 16);
 391         else if ("0b".equals(t.child(1).head())) val = Long.parseLong(ret, 2);
 392         else                                     val = Long.parseLong(ret);
 393         if (negative) val = -1L * val;
 394         return val;
 395     }
 396 }