src/edu/berkeley/fleet/assembler/Parser.java

   1 package edu.berkeley.fleet.assembler;
   2
   3 import edu.berkeley.fleet.api.*;
   4
   5 import edu.berkeley.sbp.*;
   6 import edu.berkeley.sbp.chr.*;
   7 import edu.berkeley.sbp.misc.*;
   8 import edu.berkeley.sbp.meta.*;
   9 import edu.berkeley.sbp.bind.*;
  10 import edu.berkeley.sbp.util.*;
  11 import java.util.*;
  12 import java.io.*;
  13
  14 /**
  15  *  @author Adam Megacz <megacz@cs.berkeley.edu>
  16  */
  17 public class Parser {
  18
  19     Parser(Fleet fleet) {
  20         expect = new ArrayList<Long>();
  21         this.fleet = fleet;
  22     }
  23
  24     //////////////////////////////////////////////////////////////////////////////
  25
  26     private Fleet fleet;
  27     private ArrayList<String> imports = new ArrayList<String>();
  28
  29     private HashMap<String,Ship> shipMap = new HashMap<String,Ship>();
  30
  31     // codebags in numerical order
  32     private ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
  33     private HashMap<String,CodeBag> codeBagsByName = new HashMap<String,CodeBag>();
  34
  35     private CodeBag getCodeBag(String name) {
  36         CodeBag cb = codeBagsByName.get(name);
  37         if (cb!=null) return cb;
  38         return new CodeBag(name);
  39     }
  40
  41     Tree<String> parse(Reader r) throws Exception {
  42         InputStream grammarStream =
  43             Parser.class.getClassLoader().getResourceAsStream("edu/berkeley/fleet/assembler/fleet.g");
  44         CharParser metaGrammarParser   = new CharParser(MetaGrammar.newInstance());
  45         Tree<String> parsedGrammar     = metaGrammarParser.parse(new CharInput(grammarStream)).expand1();
  46         Union   grammar                = Grammar.create(parsedGrammar, "s", new Grammar.Bindings() { });
  47         CharParser  parser             = new CharParser(grammar);
  48         Tree tree = parser.parse(new CharInput(r)).expand1();
  49         return tree;
  50     }
  51
  52     public void parse(Reader r, OutputStream out) throws Exception {
  53
  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         CountingOutputStream cos   = new CountingOutputStream(baos);
  66         DataOutputStream dos       = new DataOutputStream(cos);
  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;//cos.getCount();
  72             for(Instruction inst : c) {
  73                 fleet.writeInstruction(dos, inst);
  74                 count++;
  75             }
  76         }
  77
  78         // now write for real
  79         cos = new CountingOutputStream(out);
  80         dos = new DataOutputStream(cos);
  81         count = 0;
  82         for(int i=0; i<codeBags.size(); i++) {
  83             CodeBag c = codeBags.get(i);
  84             dos.flush();
  85             for(Instruction inst : c) {
  86                 if (inst instanceof Instruction.Literal.CodeBagDescriptor) {
  87                     dos.flush();
  88                     cos.getCount();
  89                     Instruction.Literal.CodeBagDescriptor old = (Instruction.Literal.CodeBagDescriptor)inst;
  90                     int offset = codeBagMap[(int)old.offset] - count;
  91                     inst = new Instruction.Literal.CodeBagDescriptor(old.dest,
  92                                                                      offset,
  93                                                                      codeBags.get((int)old.offset).size());
  94                 }
  95                 fleet.writeInstruction(dos, inst);
  96                 count++;
  97             }
  98         }
  99         dos.flush();
 100         cos.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(Long.parseLong(string(t.child(0))));
 144
 145         } else if (head.equals("Memory")) {
 146             if (((edu.berkeley.fleet.interpreter.Interpreter)fleet).mem.length != 0)
 147                 throw new RuntimeException("multiple memory directives found");
 148             Tree<String> m = t.child(0);
 149             int[] mem = new int[m.size()];
 150             for(int i=0; i<mem.length; i++)
 151                 mem[i] = Integer.parseInt(string(m.child(i)));
 152             ((edu.berkeley.fleet.interpreter.Interpreter)fleet).mem = mem;
 153         }
 154     }
 155
 156     String string(Tree<String> t) {
 157         String ret = "";
 158         if (t.head() != null) ret += t.head();
 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     BenkoBox portReference(Tree<String> t) {
 169         if (!"Port".equals(t.head())) return null;
 170         String shipName = name(t.child(0));
 171         String portName = name(t.child(1));
 172         Ship ship = shipMap.get(shipName);
 173         if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
 174         for(BenkoBox b : ship.getBenkoBoxes())
 175             if (b.getName().equals(portName))
 176                 return b;
 177         throw new RuntimeException("no such benkobox \""+portName+"\" on ships of type \""+ship.getType()+"\"");
 178     }
 179
 180     private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
 181
 182     Ship allocateShip(String shipType) {
 183         int allocated = 0;
 184         if (numAllocated.get(shipType) != null)
 185             allocated = numAllocated.get(shipType);
 186         numAllocated.put(shipType, allocated+1);
 187         for(Iterator<Ship> it = fleet.iterator();
 188             it.hasNext();
 189             ) {
 190             Ship s = it.next();
 191             if (s.getType().equals(shipType)) {
 192                 if (allocated == 0) return s;
 193                 allocated--;
 194             }
 195         }
 196         throw new RuntimeException("no more ships of type \""+shipType+"\"");
 197     }
 198
 199     void fillCodeBag(Tree<String> t, CodeBag cb) {
 200         if (t.head()==null) return;
 201         else if (t.head().equals("NamedCodeBag")) {
 202             CodeBag cb2 = getCodeBag(name(t.child(0)));
 203             for(Tree<String> statement : t.child(1))
 204                 fillCodeBag(statement, cb2);
 205
 206         } else if (t.head().equals("Literal")) {
 207             int literal = Integer.parseInt(string(t.child(0)));
 208             BenkoBox benkobox = portReference(t.child(1));
 209             cb.add(new Instruction.Literal.Absolute(benkobox, literal));
 210
 211         } else if (t.head().equals("CodeBagDescriptor")) {
 212             String refname = name(t.child(0).child(0));
 213             CodeBag cb2 = getCodeBag(refname);
 214             BenkoBox benkobox = portReference(t.child(1));
 215             cb.add(new Instruction.Literal.CodeBagDescriptor(benkobox, cb2.getFakeAddress(), 0));
 216
 217         } else if (t.head().equals("Fiber")) {
 218             BenkoBox benkobox = portReference(t.child(0));
 219
 220             OUTER: for(Tree tt : t.child(1)) {
 221                 int count = 1;
 222                 Tree ttx = null;
 223                 boolean recycle = false;
 224                 ttx = tt.child(1);
 225                 if (tt.size() > 1 && tt.child(0).size()>0) {
 226                     tt = tt.child(0).child(0);
 227                     if (tt.head().equals("BrackStar")) {
 228                         count = 0;
 229                         recycle = false;
 230                     } else if (tt.head().equals("ParenStar")) {
 231                         count = 0;
 232                         recycle = true;
 233                     } else if (tt.head().equals("Brack")) {
 234                         count = Integer.parseInt(string(tt.child(0)));
 235                         recycle = false;
 236                     } else if (tt.head().equals("Paren")) {
 237                         count = Integer.parseInt(string(tt.child(0)));
 238                         recycle = true;
 239                     }
 240                 }
 241                 boolean tokenIn = false;
 242                 boolean dataIn = false;
 243                 boolean latch = false;
 244                 boolean dataOut = false;
 245                 boolean tokenOut = false;
 246                 BenkoBox dest = null;
 247                 for(int i=0; i<ttx.size(); i++) {
 248                     Tree ttt = ttx.child(i);
 249                     if      ("Wait".equals(ttt.head()))    { tokenIn = true; }
 250                     else if ("Nop".equals(ttt.head()))     { }
 251                     else if ("KillStar".equals(ttt.head()))    {
 252                         cb.add(new Instruction.Kill(benkobox, count, true));
 253                         continue OUTER;
 254                     } else if ("Kill".equals(ttt.head()))    {
 255                         cb.add(new Instruction.Kill(benkobox, count, false));
 256                         continue OUTER;
 257                     }
 258                     else if ("Discard".equals(ttt.head())) { dataIn = true; latch = false; }
 259                     else if ("Take".equals(ttt.head()))    { dataIn = true; latch = true; }
 260                     else if ("SendTo".equals(ttt.head()))  { dataOut = true; dest = portReference(ttt.child(0)); }
 261                     else if ("Deliver".equals(ttt.head())) { dataOut = true;  }
 262                     else if ("Ack".equals(ttt.head()))     { tokenOut = true; dest = portReference(ttt.child(0)); }
 263                 }
 264                 cb.add(new Instruction.Executable(benkobox,
 265                                                   dest, count, tokenIn, dataIn,
 266                                                   latch, dataOut, tokenOut, recycle));
 267             }
 268         }
 269     }
 270
 271     private static class CountingOutputStream extends FilterOutputStream {
 272         public CountingOutputStream(OutputStream os) { super(os); }
 273         int count = 0;
 274         public int getCount() { return count; }
 275         public void write(int b) throws IOException {
 276             super.write(b);
 277             count++;
 278         }
 279         public void write(byte[] b, int off, int len) throws IOException {
 280             super.write(b, off, len);
 281             count += len;
 282         }
 283     }
 284
 285     private class CodeBag extends ArrayList<Instruction> {
 286         public int address = -1;
 287         public CodeBag() { codeBags.add(this); }
 288         public CodeBag(String name) { this(); codeBagsByName.put(name, this); }
 289         public long getFakeAddress() { return codeBags.indexOf(this); }
 290         public boolean equals(Object o) { return this==o; }
 291     }
 292
 293     // hideous hack
 294     public static ArrayList<Long> expect;
 295
 296 }