1 /* 2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org> 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining 5 * a copy of this software and associated documentation files (the 6 * "Software"), to deal in the Software without restriction, including 7 * without limitation the rights to use, copy, modify, merge, publish, 8 * distribute, sublicense, and/or sell copies of the Software, and to 9 * permit persons to whom the Software is furnished to do so, subject to 10 * the following conditions: 11 * 12 * The above copyright notice and this permission notice shall be 13 * included in all copies or substantial portions of the Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 */ 24 25 using System; 26 using System.Collections.Generic; 27 28 /* 29 * A WordBuilder instance organizes construction of a new interpreted word. 30 * 31 * Opcodes are accumulated with specific methods. A control-flow stack 32 * is maintained to resolve jumps. 33 * 34 * Each instance shall be used for only one word. 35 */ 36 37 class WordBuilder { 38 39 T0Comp TC; 40 string name; 41 int[] cfStack; 42 int cfPtr; 43 List<Opcode> code; 44 List<string> toResolve; 45 Dictionary<string, int> locals; 46 bool jumpToLast; 47 48 internal SType StackEffect { 49 get; set; 50 } 51 52 /* 53 * Create a new instance, with the specified word name. 54 */ WordBuilder(T0Comp TC, string name)55 internal WordBuilder(T0Comp TC, string name) 56 { 57 this.TC = TC; 58 this.name = name; 59 cfStack = new int[16]; 60 cfPtr = -1; 61 code = new List<Opcode>(); 62 toResolve = new List<string>(); 63 locals = new Dictionary<string, int>(); 64 jumpToLast = true; 65 StackEffect = SType.UNKNOWN; 66 } 67 68 /* 69 * Build the word. The control-flow stack must be empty. A 'ret' 70 * opcode is automatically appended if required. 71 */ Build()72 internal Word Build() 73 { 74 if (cfPtr != -1) { 75 throw new Exception("control-flow stack is not empty"); 76 } 77 if (jumpToLast || code[code.Count - 1].MayFallThrough) { 78 Ret(); 79 } 80 Word w = new WordInterpreted(TC, name, locals.Count, 81 code.ToArray(), toResolve.ToArray()); 82 w.StackEffect = StackEffect; 83 return w; 84 } 85 Add(Opcode op)86 void Add(Opcode op) 87 { 88 Add(op, null); 89 } 90 Add(Opcode op, string refName)91 void Add(Opcode op, string refName) 92 { 93 code.Add(op); 94 toResolve.Add(refName); 95 jumpToLast = false; 96 } 97 98 /* 99 * Rotate the control-flow stack at depth 'depth'. 100 */ CSRoll(int depth)101 internal void CSRoll(int depth) 102 { 103 int x = cfStack[cfPtr - depth]; 104 Array.Copy(cfStack, cfPtr - (depth - 1), 105 cfStack, cfPtr - depth, depth); 106 cfStack[cfPtr] = x; 107 } 108 109 /* 110 * Make a copy of the control-flow element at depth 'depth', and 111 * push it on top of the control-flow stack. 112 */ CSPick(int depth)113 internal void CSPick(int depth) 114 { 115 int x = cfStack[cfPtr - depth]; 116 CSPush(x); 117 } 118 CSPush(int x)119 void CSPush(int x) 120 { 121 int len = cfStack.Length; 122 if (++ cfPtr == len) { 123 int[] ncf = new int[len << 1]; 124 Array.Copy(cfStack, 0, ncf, 0, len); 125 cfStack = ncf; 126 } 127 cfStack[cfPtr] = x; 128 } 129 CSPop()130 int CSPop() 131 { 132 return cfStack[cfPtr --]; 133 } 134 135 /* 136 * Push an origin on the control-flow stack, corresponding to the 137 * next opcode to add. 138 */ CSPushOrig()139 internal void CSPushOrig() 140 { 141 CSPush(code.Count); 142 } 143 144 /* 145 * Push a destination on the control-flow stack, corresponding to 146 * the next opcode to add. 147 */ CSPushDest()148 internal void CSPushDest() 149 { 150 CSPush(-code.Count - 1); 151 } 152 153 /* 154 * Pop an origin from the control-flow stack. An exception is 155 * thrown if the value is not an origin. 156 */ CSPopOrig()157 internal int CSPopOrig() 158 { 159 int x = CSPop(); 160 if (x < 0) { 161 throw new Exception("not an origin"); 162 } 163 return x; 164 } 165 166 /* 167 * Pop a destination from the control-flow stack. An exception is 168 * thrown if the value is not a destination. 169 */ CSPopDest()170 internal int CSPopDest() 171 { 172 int x = CSPop(); 173 if (x >= 0) { 174 throw new Exception("not a destination"); 175 } 176 return -x - 1; 177 } 178 179 /* 180 * Add a "push literal" opcode. 181 */ Literal(TValue v)182 internal void Literal(TValue v) 183 { 184 Add(new OpcodeConst(v)); 185 } 186 187 /* 188 * Compile a "call" by name. This method implements the support 189 * for local variables: 190 * 191 * - If the target is '>' followed by a local variable name, then 192 * a "put local" opcode is added. 193 * 194 * - Otherwise, if the target is a local variable name, then a 195 * "get local" opcode is added. 196 * 197 * - Otherwise, a call to the named word is added. The target name 198 * will be resolved later on (typically, when the word containing 199 * the call opcode is first invoked, or when C code is generated). 200 */ Call(string target)201 internal void Call(string target) 202 { 203 string lname; 204 bool write; 205 if (target.StartsWith(">")) { 206 lname = target.Substring(1); 207 write = true; 208 } else { 209 lname = target; 210 write = false; 211 } 212 int lnum; 213 if (locals.TryGetValue(lname, out lnum)) { 214 if (write) { 215 Add(new OpcodePutLocal(lnum)); 216 } else { 217 Add(new OpcodeGetLocal(lnum)); 218 } 219 } else { 220 Add(new OpcodeCall(), target); 221 } 222 } 223 224 /* 225 * Add a "call" opcode to the designated word. 226 */ CallExt(Word wtarget)227 internal void CallExt(Word wtarget) 228 { 229 Add(new OpcodeCall(wtarget), null); 230 } 231 232 /* 233 * Add a "call" opcode to a word which is not currently resolved. 234 * This method ignores local variables. 235 */ CallExt(string target)236 internal void CallExt(string target) 237 { 238 Add(new OpcodeCall(), target); 239 } 240 241 /* 242 * Add a "get local" opcode; the provided local name must already 243 * be defined. 244 */ GetLocal(string name)245 internal void GetLocal(string name) 246 { 247 int lnum; 248 if (locals.TryGetValue(name, out lnum)) { 249 Add(new OpcodeGetLocal(lnum)); 250 } else { 251 throw new Exception("no such local: " + name); 252 } 253 } 254 255 /* 256 * Add a "put local" opcode; the provided local name must already 257 * be defined. 258 */ PutLocal(string name)259 internal void PutLocal(string name) 260 { 261 int lnum; 262 if (locals.TryGetValue(name, out lnum)) { 263 Add(new OpcodePutLocal(lnum)); 264 } else { 265 throw new Exception("no such local: " + name); 266 } 267 } 268 269 /* 270 * Define a new local name. 271 */ DefLocal(string lname)272 internal void DefLocal(string lname) 273 { 274 if (locals.ContainsKey(lname)) { 275 throw new Exception(String.Format( 276 "local already defined: {0}", lname)); 277 } 278 locals[lname] = locals.Count; 279 } 280 281 /* 282 * Add a "call" opcode whose target is an XT value (which may be 283 * resolved or as yet unresolved). 284 */ Call(TPointerXT xt)285 internal void Call(TPointerXT xt) 286 { 287 if (xt.Target == null) { 288 Add(new OpcodeCall(), xt.Name); 289 } else { 290 Add(new OpcodeCall(xt.Target)); 291 } 292 } 293 294 /* 295 * Add a "ret" opcode. 296 */ Ret()297 internal void Ret() 298 { 299 Add(new OpcodeRet()); 300 } 301 302 /* 303 * Add a forward unconditional jump. The new opcode address is 304 * pushed on the control-flow stack as an origin. 305 */ Ahead()306 internal void Ahead() 307 { 308 CSPushOrig(); 309 Add(new OpcodeJumpUncond()); 310 } 311 312 /* 313 * Add a forward conditional jump, which will be taken at runtime 314 * if the top-of-stack value is 'true'. The new opcode address is 315 * pushed on the control-flow stack as an origin. 316 */ AheadIf()317 internal void AheadIf() 318 { 319 CSPushOrig(); 320 Add(new OpcodeJumpIf()); 321 } 322 323 /* 324 * Add a forward conditional jump, which will be taken at runtime 325 * if the top-of-stack value is 'false'. The new opcode address is 326 * pushed on the control-flow stack as an origin. 327 */ AheadIfNot()328 internal void AheadIfNot() 329 { 330 CSPushOrig(); 331 Add(new OpcodeJumpIfNot()); 332 } 333 334 /* 335 * Resolve a previous forward jump to the current code address. 336 * The top of control-flow stack is popped and must be an origin. 337 */ Then()338 internal void Then() 339 { 340 int x = CSPopOrig(); 341 code[x].ResolveJump(code.Count - x - 1); 342 jumpToLast = true; 343 } 344 345 /* 346 * Push the current code address on the control-flow stack as a 347 * destination, to be used by an ulterior backward jump. 348 */ Begin()349 internal void Begin() 350 { 351 CSPushDest(); 352 } 353 354 /* 355 * Add a backward unconditional jump. The jump target is popped 356 * from the control-flow stack as a destination. 357 */ Again()358 internal void Again() 359 { 360 int x = CSPopDest(); 361 Add(new OpcodeJumpUncond(x - code.Count - 1)); 362 } 363 364 /* 365 * Add a backward conditional jump, which will be taken at runtime 366 * if the top-of-stack value is 'true'. The jump target is popped 367 * from the control-flow stack as a destination. 368 */ AgainIf()369 internal void AgainIf() 370 { 371 int x = CSPopDest(); 372 Add(new OpcodeJumpIf(x - code.Count - 1)); 373 } 374 375 /* 376 * Add a backward conditional jump, which will be taken at runtime 377 * if the top-of-stack value is 'false'. The jump target is popped 378 * from the control-flow stack as a destination. 379 */ AgainIfNot()380 internal void AgainIfNot() 381 { 382 int x = CSPopDest(); 383 Add(new OpcodeJumpIfNot(x - code.Count - 1)); 384 } 385 } 386