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  	 */
 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  	 */
 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  
 86  	void Add(Opcode op)
 87  	{
 88  		Add(op, null);
 89  	}
 90  
 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  	 */
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  	 */
113  	internal void CSPick(int depth)
114  	{
115  		int x = cfStack[cfPtr - depth];
116  		CSPush(x);
117  	}
118  
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  
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
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  	 */
380  	internal void AgainIfNot()
381  	{
382  		int x = CSPopDest();
383  		Add(new OpcodeJumpIfNot(x - code.Count - 1));
384  	}
385  }