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         baseCodeBag.add(new Instruction.Literal.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1));
  58         walk((Tree<String>)parse(r), rootCodeBag);
  59         if (fleet instanceof edu.berkeley.fleet.slipway.Slipway)
  60             ((edu.berkeley.fleet.slipway.Slipway)fleet).dumpFabric(true);
  61
  62         // map from arbitrary identifiers to actual addresses
  63         int[] codeBagMap = new int[codeBags.size()];
  64         ByteArrayOutputStream baos = new ByteArrayOutputStream();
  65         DataOutputStream dos       = new DataOutputStream(baos);
  66         int count = 0;
  67         for(int i=0; i<codeBags.size(); i++) {
  68             CodeBag c = codeBags.get(i);
  69             dos.flush();
  70             codeBagMap[i] = count;
  71             for(Instruction inst : c) {
  72                 fleet.writeInstruction(dos, inst);
  73                 count++;
  74             }
  75         }
  76
  77         // now write for real
  78         dos = new DataOutputStream(out);
  79         count = 0;
  80         for(int i=0; i<codeBags.size(); i++) {
  81             CodeBag c = codeBags.get(i);
  82             dos.flush();
  83             for(Instruction inst : c) {
  84                 if (inst instanceof Instruction.Literal.CodeBagDescriptor) {
  85                     dos.flush();
  86                     Instruction.Literal.CodeBagDescriptor old = (Instruction.Literal.CodeBagDescriptor)inst;
  87                     int offset = codeBagMap[(int)old.offset] - count;
  88                     inst = new Instruction.Literal.CodeBagDescriptor(old.dest,
  89                                                                      offset,
  90                                                                      codeBags.get((int)old.offset).size());
  91                 }
  92                 fleet.writeInstruction(dos, inst);
  93                 count++;
  94             }
  95         }
  96         dos.flush();
  97         out.flush();
  98         out.close();
  99     }
 100
 101     /** in the first pass, codebags are assigned "addresses" in arbitrary order */
 102     void walk(Tree<String> t, CodeBag cb) {
 103
 104         String head = t.head();
 105         if (head==null) {
 106         } else if (head.equals("Program")) {
 107             for(Tree<String> tc : t.child(0))
 108                 walk(tc, cb);
 109             if (t.size()>1)
 110                 for(Tree<String> statement : t.child(1))
 111                     fillCodeBag(statement, cb);
 112
 113         } else if (head.equals("Import")) {
 114             // ignored
 115
 116         } else if (head.equals("Ship")) {
 117             String name = name(t.child(0));
 118             String type = string(t.child(1));
 119             Ship ship = null;
 120
 121             if (fleet instanceof Fleet.WithDynamicShips) {
 122                 Fleet.WithDynamicShips dyn = ((Fleet.WithDynamicShips)fleet);
 123                 ship = dyn.createShip(type, name);
 124                 if (ship==null)
 125                     throw new RuntimeException("couldn't find a ship called \""+type+"\"");
 126             } else {
 127                 ship = allocateShip(type);
 128             }
 129             shipMap.put(name, ship);
 130
 131         } else if (head.equals("Include")) {
 132             try {
 133                 walk(parse(new InputStreamReader(new FileInputStream(string(t.child(0))))), cb);
 134             } catch (Exception e) {
 135                 throw new RuntimeException(e);
 136             }
 137
 138         } else if (head.equals("Expect")) {
 139             expect.add(Long.parseLong(string(t.child(0))));
 140
 141         }
 142     }
 143
 144     String string(Tree<String> t) {
 145         String ret = "";
 146         if (t.head() != null) ret += t.head();
 147         for(Tree<String> c : t)
 148             ret += string(c);
 149         return ret;
 150     }
 151
 152     String name(Tree<String> t) {
 153         return string(t.child(0))+string(t.child(1));
 154     }
 155
 156     Destination portReference(Tree<String> t) {
 157         if (!"Port".equals(t.head()) && !"SubPort".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head())) return null;
 158         String shipName = name(t.child(0));
 159         String portName = name(t.child(1));
 160         String subPort = t.size()<3 ? null : name(t.child(2));
 161         Ship ship = shipMap.get(shipName);
 162         if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
 163         Destination ret = null;
 164         BenkoBox bb = null;
 165         for(BenkoBox b : ship.getBenkoBoxes())
 166             if (b.getName().equals(portName)) {
 167                 bb = b;
 168             }
 169         if (bb==null)
 170             throw new RuntimeException("no such benkobox \""+portName+"\"");
 171         if (subPort==null) subPort="";
 172         for(Destination d : bb.getDestinations())
 173             if (d.getDestinationName().equals(subPort))
 174                 return d;
 175         if (ret==null)
 176             throw new RuntimeException("no such benkobox \""+portName+"\" on ships of type \""+ship.getType()+"\"");
 177         return ret;
 178     }
 179
 180     BenkoBox benkoBox(Tree<String> t) {
 181         if (!"Port".equals(t.head()) && !"SubPort".equals(t.head()) && !"ShipSpecificLiteral".equals(t.head())) return null;
 182         String shipName = name(t.child(0));
 183         String portName = name(t.child(1));
 184         Ship ship = shipMap.get(shipName);
 185         if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
 186         BenkoBox bb = null;
 187         for(BenkoBox b : ship.getBenkoBoxes())
 188             if (b.getName().equals(portName))
 189                 return b;
 190         throw new RuntimeException("no such benkobox \""+portName+"\"");
 191     }
 192
 193     private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
 194
 195     Ship allocateShip(String shipType) {
 196         int allocated = 0;
 197         if (numAllocated.get(shipType) != null)
 198             allocated = numAllocated.get(shipType);
 199         numAllocated.put(shipType, allocated+1);
 200         for(Iterator<Ship> it = fleet.iterator();
 201             it.hasNext();
 202             ) {
 203             Ship s = it.next();
 204             if (s.getType().equals(shipType)) {
 205                 if (allocated == 0) return s;
 206                 allocated--;
 207             }
 208         }
 209         throw new RuntimeException("no more ships of type \""+shipType+"\"");
 210     }
 211
 212     void fillCodeBag(Tree<String> t, CodeBag cb) {
 213         if (t.head()==null) return;
 214         else if (t.head().equals("NamedCodeBag")) {
 215             CodeBag cb2 = getCodeBag(name(t.child(0)));
 216             for(Tree<String> statement : t.child(1))
 217                 fillCodeBag(statement, cb2);
 218
 219         } else if (t.head().equals("ShipSpecificLiteral")) {
 220             String shipType = name(t.child(0).child(0));
 221             String portName = name(t.child(0).child(1));
 222             Ship chosenship = null;
 223             for(Ship ship : fleet) {
 224                 if (ship.getType().equals(shipType)) {
 225                     chosenship = ship;
 226                     break;
 227                 }
 228             }
 229             long literal = chosenship.resolveLiteral(portName);
 230             cb.add(new Instruction.Literal.Absolute(portReference(t.child(1)), literal));
 231
 232         } else if (t.head().equals("Literal")) {
 233             long literal = Long.parseLong(string(t.child(0)));
 234             cb.add(new Instruction.Literal.Absolute(portReference(t.child(1)), literal));
 235
 236         } else if (t.head().equals("CodeBagDescriptor")) {
 237             String refname = name(t.child(0).child(0));
 238             CodeBag cb2 = getCodeBag(refname);
 239             cb.add(new Instruction.Literal.CodeBagDescriptor(portReference(t.child(1)), cb2.getFakeAddress(), 0));
 240
 241         } else if (t.head().equals("Fiber")) {
 242             BenkoBox benkobox = (BenkoBox)benkoBox(t.child(0));
 243
 244             OUTER: for(Tree tt : t.child(1)) {
 245                 int count = 1;
 246                 Tree ttx = null;
 247                 boolean recycle = false;
 248                 ttx = tt.child(1);
 249                 if (tt.size() > 1 && tt.child(0).size()>0) {
 250                     tt = tt.child(0).child(0);
 251                     if (tt.head().equals("BrackStar")) {
 252                         count = 0;
 253                         recycle = false;
 254                     } else if (tt.head().equals("ParenStar")) {
 255                         count = 0;
 256                         recycle = true;
 257                     } else if (tt.head().equals("Brack")) {
 258                         count = Integer.parseInt(string(tt.child(0)));
 259                         recycle = false;
 260                     } else if (tt.head().equals("Paren")) {
 261                         count = Integer.parseInt(string(tt.child(0)));
 262                         recycle = true;
 263                     }
 264                 }
 265                 boolean tokenIn = false;
 266                 boolean dataIn = false;
 267                 boolean latch = false;
 268                 boolean dataOut = false;
 269                 boolean tokenOut = false;
 270                 Destination dest = null;
 271                 for(int i=0; i<ttx.size(); i++) {
 272                     Tree ttt = ttx.child(i);
 273                     if      ("Wait".equals(ttt.head()))    { tokenIn = true; }
 274                     else if ("Nop".equals(ttt.head()))     { }
 275                     else if ("KillStar".equals(ttt.head()))    {
 276                         cb.add(new Instruction.Kill(benkobox, count, true));
 277                         continue OUTER;
 278                     } else if ("Kill".equals(ttt.head()))    {
 279                         cb.add(new Instruction.Kill(benkobox, count, false));
 280                         continue OUTER;
 281                     }
 282                     else if ("Discard".equals(ttt.head())) { dataIn = true; latch = false; }
 283                     else if ("Take".equals(ttt.head()))    { dataIn = true; latch = true; }
 284                     else if ("SendTo".equals(ttt.head()))  { dataOut = true; dest = portReference(ttt.child(0)); }
 285                     else if ("Deliver".equals(ttt.head())) { dataOut = true;  }
 286                     else if ("Ack".equals(ttt.head()))     { tokenOut = true; dest = portReference(ttt.child(0)); }
 287                 }
 288                 cb.add(new Instruction.Executable(benkobox,
 289                                                   dest, count, tokenIn, dataIn,
 290                                                   latch, dataOut, tokenOut, recycle));
 291             }
 292         }
 293     }
 294
 295     private class CodeBag extends ArrayList<Instruction> {
 296         public long address = -1;
 297         public CodeBag() { codeBags.add(this); }
 298         public CodeBag(String name) { this(); codeBagsByName.put(name, this); }
 299         public long getFakeAddress() { return codeBags.indexOf(this); }
 300         public boolean equals(Object o) { return this==o; }
 301     }
 302
 303     // hideous hack
 304     public static ArrayList<Long> expect;
 305
 306 }