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 * The implementation for interpreted words.
30 */
31
32class WordInterpreted : Word {
33
34	/*
35	 * Get the number of local variables for this word.
36	 */
37	internal int NumLocals {
38		get; private set;
39	}
40
41	/*
42	 * Get the sequence of opcodes for this word.
43	 */
44	internal Opcode[] Code {
45		get; private set;
46	}
47
48	string[] toResolve;
49
50	internal WordInterpreted(T0Comp owner, string name,
51		int numLocals, Opcode[] code, string[] toResolve)
52		: base(owner, name)
53	{
54		this.Code = code;
55		this.toResolve = toResolve;
56		NumLocals = numLocals;
57	}
58
59	internal override void Resolve()
60	{
61		if (toResolve == null) {
62			return;
63		}
64		for (int i = 0; i < toResolve.Length; i ++) {
65			string tt = toResolve[i];
66			if (tt == null) {
67				continue;
68			}
69			Code[i].ResolveTarget(TC.Lookup(tt));
70		}
71		toResolve = null;
72	}
73
74	internal override void Run(CPU cpu)
75	{
76		Resolve();
77		cpu.Enter(Code, NumLocals);
78	}
79
80	internal override List<Word> GetReferences()
81	{
82		Resolve();
83		List<Word> r = new List<Word>();
84		foreach (Opcode op in Code) {
85			Word w = op.GetReference(TC);
86			if (w != null) {
87				r.Add(w);
88			}
89		}
90		return r;
91	}
92
93	internal override List<ConstData> GetDataBlocks()
94	{
95		Resolve();
96		List<ConstData> r = new List<ConstData>();
97		foreach (Opcode op in Code) {
98			ConstData cd = op.GetDataBlock(TC);
99			if (cd != null) {
100				r.Add(cd);
101			}
102		}
103		return r;
104	}
105
106	internal override void GenerateCodeElements(List<CodeElement> dst)
107	{
108		Resolve();
109		int n = Code.Length;
110		CodeElement[] gcode = new CodeElement[n];
111		for (int i = 0; i < n; i ++) {
112			gcode[i] = Code[i].ToCodeElement();
113		}
114		for (int i = 0; i < n; i ++) {
115			Code[i].FixUp(gcode, i);
116		}
117		dst.Add(new CodeElementUInt((uint)NumLocals));
118		for (int i = 0; i < n; i ++) {
119			dst.Add(gcode[i]);
120		}
121	}
122
123	int flowAnalysis;
124	int maxDataStack;
125	int maxReturnStack;
126
127	bool MergeSA(int[] sa, int j, int c)
128	{
129		if (sa[j] == Int32.MinValue) {
130			sa[j] = c;
131			return true;
132		} else if (sa[j] != c) {
133			throw new Exception(string.Format(
134				"In word '{0}', offset {1}:"
135				+ " stack action mismatch ({2} / {3})",
136				Name, j, sa[j], c));
137		} else {
138			return false;
139		}
140	}
141
142	internal override void AnalyseFlow()
143	{
144		switch (flowAnalysis) {
145		case 0:
146			break;
147		case 1:
148			return;
149		default:
150			throw new Exception("recursive call detected in '"
151				+ Name + "'");
152		}
153		flowAnalysis = 2;
154		int n = Code.Length;
155		int[] sa = new int[n];
156		for (int i = 0; i < n; i ++) {
157			sa[i] = Int32.MinValue;
158		}
159		sa[0] = 0;
160		int[] toExplore = new int[n];
161		int tX = 0, tY = 0;
162		int off = 0;
163
164		int exitSA = Int32.MinValue;
165		int mds = 0;
166		int mrs = 0;
167
168		int maxDepth = 0;
169
170		for (;;) {
171			Opcode op = Code[off];
172			bool mft = op.MayFallThrough;
173			int c = sa[off];
174			int a;
175			if (op is OpcodeCall) {
176				Word w = op.GetReference(TC);
177				w.AnalyseFlow();
178				SType se = w.StackEffect;
179				if (!se.IsKnown) {
180					throw new Exception(string.Format(
181						"call from '{0}' to '{1}'"
182						+ " with unknown stack effect",
183						Name, w.Name));
184				}
185				if (se.NoExit) {
186					mft = false;
187					a = 0;
188				} else {
189					a = se.DataOut - se.DataIn;
190				}
191				mds = Math.Max(mds, c + w.MaxDataStack);
192				mrs = Math.Max(mrs, w.MaxReturnStack);
193				maxDepth = Math.Min(maxDepth, c - se.DataIn);
194			} else if (op is OpcodeRet) {
195				if (exitSA == Int32.MinValue) {
196					exitSA = c;
197				} else if (exitSA != c) {
198					throw new Exception(string.Format(
199						"'{0}': exit stack action"
200						+ " mismatch: {1} / {2}"
201						+ " (offset {3})",
202						Name, exitSA, c, off));
203				}
204				a = 0;
205			} else {
206				a = op.StackAction;
207				mds = Math.Max(mds, c + a);
208			}
209			c += a;
210			maxDepth = Math.Min(maxDepth, c);
211
212			int j = op.JumpDisp;
213			if (j != 0) {
214				j += off + 1;
215				toExplore[tY ++] = j;
216				MergeSA(sa, j, c);
217			}
218			off ++;
219			if (!mft || !MergeSA(sa, off, c)) {
220				if (tX < tY) {
221					off = toExplore[tX ++];
222				} else {
223					break;
224				}
225			}
226		}
227
228		maxDataStack = mds;
229		maxReturnStack = 1 + NumLocals + mrs;
230
231		/*
232		 * TODO: see about this warning. Usage of a 'fail'
233		 * word (that does not exit) within a 'case..endcase'
234		 * structure will make an unreachable opcode. In a future
235		 * version we might want to automatically remove dead
236		 * opcodes.
237		for (int i = 0; i < n; i ++) {
238			if (sa[i] == Int32.MinValue) {
239				Console.WriteLine("warning: word '{0}',"
240					+ " offset {1}: unreachable opcode",
241					Name, i);
242				continue;
243			}
244		}
245		 */
246
247		SType computed;
248		if (exitSA == Int32.MinValue) {
249			computed = new SType(-maxDepth, -1);
250		} else {
251			computed = new SType(-maxDepth, -maxDepth + exitSA);
252		}
253
254		if (StackEffect.IsKnown) {
255			if (!computed.IsSubOf(StackEffect)) {
256				throw new Exception(string.Format(
257					"word '{0}':"
258					+ " computed stack effect {1}"
259					+ " does not match declared {2}",
260					Name, computed.ToString(),
261					StackEffect.ToString()));
262			}
263		} else {
264			StackEffect = computed;
265		}
266
267		flowAnalysis = 1;
268	}
269
270	internal override int MaxDataStack {
271		get {
272			AnalyseFlow();
273			return maxDataStack;
274		}
275	}
276
277	internal override int MaxReturnStack {
278		get {
279			AnalyseFlow();
280			return maxReturnStack;
281		}
282	}
283}
284