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
25using System;
26using 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
37class 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}
386