1 package edu.berkeley.fleet.assembler;
3 import edu.berkeley.fleet.api.*;
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.*;
15 * @author Adam Megacz <megacz@cs.berkeley.edu>
23 //////////////////////////////////////////////////////////////////////////////
26 private ArrayList<String> imports = new ArrayList<String>();
28 private HashMap<String,Ship> shipMap = new HashMap<String,Ship>();
30 // codebags in numerical order
31 private ArrayList<CodeBag> codeBags = new ArrayList<CodeBag>();
32 private HashMap<String,CodeBag> codeBagsByName = new HashMap<String,CodeBag>();
34 Tree<String> parse(Reader r) throws Exception {
35 InputStream grammarStream =
36 Parser.class.getClassLoader().getResourceAsStream("edu/berkeley/fleet/parser/fleet.g");
37 CharParser metaGrammarParser = new CharParser(MetaGrammar.newInstance());
38 Tree<String> parsedGrammar = metaGrammarParser.parse(new CharInput(grammarStream)).expand1();
39 Union grammar = Grammar.create(parsedGrammar, "s", new Grammar.Bindings() { });
40 CharParser parser = new CharParser(grammar);
41 Tree tree = parser.parse(new CharInput(r)).expand1();
45 public void parse(Reader r, OutputStream out) throws Exception {
47 // this needs to be "code bag zero"
48 CodeBag baseCodeBag = new CodeBag();
49 CodeBag rootCodeBag = new CodeBag();
50 baseCodeBag.add(new Instruction.Literal.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1));
51 walk((Tree<String>)parse(r), rootCodeBag);
53 // map from arbitrary identifiers to actual addresses
54 int[] codeBagMap = new int[codeBags.size()];
55 ByteArrayOutputStream baos = new ByteArrayOutputStream();
56 CountingOutputStream cos = new CountingOutputStream(baos);
57 DataOutputStream dos = new DataOutputStream(cos);
58 for(int i=0; i<codeBags.size(); i++) {
59 CodeBag c = codeBags.get(i);
61 codeBagMap[i] = cos.getCount();
62 for(Instruction inst : c)
63 fleet.writeInstruction(dos, inst);
67 dos = new DataOutputStream(out);
68 cos = new CountingOutputStream(dos);
69 for(int i=0; i<codeBags.size(); i++) {
70 CodeBag c = codeBags.get(i);
72 for(Instruction inst : c) {
73 if (inst instanceof Instruction.Literal.CodeBagDescriptor) {
76 Instruction.Literal.CodeBagDescriptor old = (Instruction.Literal.CodeBagDescriptor)inst;
77 int offset = fleet.computeOffset(cos.getCount(), codeBagMap[(int)old.offset]);
78 inst = new Instruction.Literal.CodeBagDescriptor(old.dest,
80 codeBags.get((int)old.offset).size());
82 fleet.writeInstruction(dos, inst);
88 public void parse(Reader r, ArrayList<Instruction> out) throws Exception {
89 // this needs to be "code bag zero"
90 CodeBag baseCodeBag = new CodeBag();
91 CodeBag rootCodeBag = new CodeBag();
92 Instruction inst0 = new Instruction.Literal.CodeBagDescriptor(null, rootCodeBag.getFakeAddress(), 1);
93 baseCodeBag.add(inst0);
94 walk((Tree<String>)parse(r), rootCodeBag);
96 // map from arbitrary identifiers to actual addresses
97 int[] codeBagMap = new int[codeBags.size()];
98 ArrayList<Instruction> temp = new ArrayList<Instruction>();
99 for(int i=0; i<codeBags.size(); i++) {
100 codeBagMap[i] = temp.size();
101 for(Instruction inst : codeBags.get(i))
105 // now write for real
106 for(int i=0; i<codeBags.size(); i++) {
107 CodeBag c = codeBags.get(i);
108 for(Instruction inst : c) {
109 if (inst instanceof Instruction.Literal.CodeBagDescriptor) {
110 Instruction.Literal.CodeBagDescriptor old = (Instruction.Literal.CodeBagDescriptor)inst;
111 int offset = fleet.computeOffset(out.size(), codeBagMap[(int)old.offset]);
112 inst = new Instruction.Literal.CodeBagDescriptor(old.dest,
114 codeBags.get((int)old.offset).size());
121 /** in the first pass, codebags are assigned "addresses" in arbitrary order */
122 void walk(Tree<String> t, CodeBag cb) {
124 String head = t.head();
126 } else if (head.equals("Program")) {
127 for(Tree<String> tc : t.child(0))
130 for(Tree<String> statement : t.child(1))
131 fillCodeBag(statement, cb);
133 } else if (head.equals("Import")) {
134 imports.add(string(t.child(0)));
136 } else if (head.equals("Ship")) {
137 String name = name(t.child(0));
138 String type = string(t.child(1));
140 if (fleet instanceof edu.berkeley.fleet.interpreter.Interpreter) {
141 edu.berkeley.fleet.interpreter.Interpreter interpreter =
142 ((edu.berkeley.fleet.interpreter.Interpreter)fleet);
143 String classname = type;
144 boolean good = false;
145 for(String s : imports)
146 if ((ship = interpreter.tryCreate(s+"."+classname, name)) != null)
149 throw new RuntimeException("couldn't find a ship called \""+classname+"\"");
151 ship = allocateShip(type);
153 shipMap.put(name, ship);
155 } else if (head.equals("Include")) {
157 walk(parse(new InputStreamReader(new FileInputStream(string(t.child(0))))), cb);
158 } catch (Exception e) {
159 throw new RuntimeException(e);
162 } else if (head.equals("Memory")) {
163 if (((edu.berkeley.fleet.interpreter.Interpreter)fleet).mem.length != 0)
164 throw new RuntimeException("multiple memory directives found");
165 Tree<String> m = t.child(0);
166 int[] mem = new int[m.size()];
167 for(int i=0; i<mem.length; i++)
168 mem[i] = Integer.parseInt(string(m.child(i)));
169 ((edu.berkeley.fleet.interpreter.Interpreter)fleet).mem = mem;
173 String string(Tree<String> t) {
175 if (t.head() != null) ret += t.head();
176 for(Tree<String> c : t)
181 String name(Tree<String> t) {
182 return string(t.child(0))+string(t.child(1));
185 BenkoBox portReference(Tree<String> t) {
186 if (!"Port".equals(t.head())) return null;
187 String shipName = name(t.child(0));
188 String portName = name(t.child(1));
189 Ship ship = shipMap.get(shipName);
190 if (ship==null) throw new RuntimeException("no such ship \""+shipName+"\"");
191 for(BenkoBox b : ship.getBenkoBoxes())
192 if (b.getName().equals(portName))
194 throw new RuntimeException("no such benkobox \""+portName+"\" on ships of type \""+ship.getType()+"\"");
197 private HashMap<String,Integer> numAllocated = new HashMap<String,Integer>();
198 Ship allocateShip(String shipType) {
200 if (numAllocated.get(shipType) != null)
201 allocated = numAllocated.get(shipType);
202 numAllocated.put(shipType, allocated+1);
203 for(Iterator<Ship> it = fleet.iterator();
207 if (s.getType().equals(shipType)) {
208 if (allocated == 0) return s;
212 throw new RuntimeException("no more ships of type \""+shipType+"\"");
215 void fillCodeBag(Tree<String> t, CodeBag cb) {
216 if (t.head()==null) return;
217 else if (t.head().equals("NamedCodeBag")) {
218 CodeBag cb2 = new CodeBag(name(t.child(0)));
219 for(Tree<String> statement : t.child(1))
220 fillCodeBag(statement, cb2);
222 } else if (t.head().equals("Literal")) {
223 int literal = Integer.parseInt(string(t.child(0)));
224 BenkoBox benkobox = portReference(t.child(1));
225 cb.add(new Instruction.Literal.Absolute(benkobox, literal));
227 } else if (t.head().equals("Fiber")) {
228 BenkoBox benkobox = portReference(t.child(0));
230 OUTER: for(Tree tt : t.child(1)) {
233 boolean recycle = false;
237 if (tt.size() > 0 && tt.child(0).size()>0) {
239 if (tt.child(0).size() == 0) count=1;
240 else if (tt.child(0).size() > 0 && "Star".equals(tt.child(0).child(0).head())) count=0;
241 else count = Integer.parseInt(string(tt.child(0)));
242 if (tt.size() > 1 && tt.child(1).size() > 0)
246 boolean tokenIn = false;
247 boolean dataIn = false;
248 boolean latch = false;
249 boolean dataOut = false;
250 boolean tokenOut = false;
251 BenkoBox dest = null;
252 for(int i=0; i<ttx.size(); i++) {
253 Tree ttt = ttx.child(i);
254 if ("Wait".equals(ttt.head())) { tokenIn = true; }
255 else if ("Nop".equals(ttt.head())) { }
256 else if ("Kill".equals(ttt.head())) {
257 cb.add(new Instruction.Kill(benkobox, count));
260 else if ("Discard".equals(ttt.head())) { dataIn = true; latch = false; }
261 else if ("Take".equals(ttt.head())) { dataIn = true; latch = true; }
262 else if ("SendTo".equals(ttt.head())) { dataOut = true; dest = portReference(ttt.child(0)); }
263 else if ("Deliver".equals(ttt.head())) { dataOut = true; }
264 else if ("Ack".equals(ttt.head())) { tokenOut = true; dest = portReference(ttt.child(0)); }
266 cb.add(new Instruction.Executable(benkobox,
267 dest, count, tokenIn, dataIn,
268 latch, dataOut, tokenOut, recycle));
273 private static class CountingOutputStream extends FilterOutputStream {
274 public CountingOutputStream(OutputStream os) { super(os); }
276 public int getCount() { return count; }
277 public void write(int b) throws IOException {
281 public void write(byte[] b, int off, int len) throws IOException {
282 super.write(b, off, len);
287 private class CodeBag extends ArrayList<Instruction> {
288 public int address = -1;
289 public CodeBag() { codeBags.add(this); }
290 public CodeBag(String name) { this(); codeBagsByName.put(name, this); }
291 public long getFakeAddress() { return codeBags.indexOf(this); }
292 public boolean equals(Object o) { return this==o; }