View Javadoc

1   /*
2    * #%L
3    * prolobjectlink-jpi-jtrolog
4    * %%
5    * Copyright (C) 2012 - 2018 WorkLogic Project
6    * %%
7    * This program is free software: you can redistribute it and/or modify
8    * it under the terms of the GNU Lesser General Public License as
9    * published by the Free Software Foundation, either version 2.1 of the
10   * License, or (at your option) any later version.
11   * 
12   * This program is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   * GNU General Lesser Public License for more details.
16   * 
17   * You should have received a copy of the GNU General Lesser Public
18   * License along with this program.  If not, see
19   * <http://www.gnu.org/licenses/lgpl-2.1.html>.
20   * #L%
21   */
22  package jTrolog.engine;
23  
24  import jTrolog.errors.PrologException;
25  import jTrolog.terms.*;
26  import jTrolog.terms.Number;
27  import jTrolog.parser.Parser;
28  import jTrolog.lib.BuiltIn;
29  
30  import java.util.*;
31  
32  /**
33   * @author janerist@stud.ntnu.no
34   * @author ivar.orstavik@hist.no
35   */
36  @SuppressWarnings({ "rawtypes" })
37  class Engine {
38  
39  	public static final int EVAL = 0;
40  	public static final int RULE = 1;
41  	public static final int BACK = 2;
42  	public static final int TRUE = 3;
43  	public static final int TRUE_ALL = 4;
44  	public static final int FALSE = 5;
45  
46  	private Prolog prolog;
47  	BindingsTable bt;
48  
49  	private int stackPos;
50  	private ChoicePoint[] stack;
51  	public static final int STARTUP_STACK_SIZE = 64;
52  	private int initState;
53  	private ChoicePoint query;
54  
55  	Engine(Prolog manager, final Struct[] queryBody) throws Throwable {
56  		prolog = manager;
57  		bt = new BindingsTable();
58  		stack = new ChoicePoint[STARTUP_STACK_SIZE];
59  		for (int i = 0; i < stack.length; i++)
60  			stack[i] = new ChoicePoint();
61  		stackPos = -1;
62  		query = new ChoicePoint();
63  		query.setBody(queryBody, 0);
64  		initState = addToStack(query.getTODO(), 0, query);
65  	}
66  
67  	BindingsTable runFirst() throws Throwable {
68  		return run(initState);
69  	}
70  
71  	/**
72  	 * Core of engine. Finite State Machine
73  	 * 
74  	 * @param state
75  	 *            to start from
76  	 * @return either a Number or a BindingsTable
77  	 * @throws Throwable
78  	 *             Exceptions that may occur running primitive predicates.
79  	 */
80  	BindingsTable run(int state) throws Throwable {
81  		while (true) {
82  			switch (state) {
83  			case EVAL:
84  				state = eval();
85  				break;
86  			case RULE:
87  				state = ruleSelect();
88  				break;
89  			case BACK:
90  				state = back();
91  				break;
92  			case TRUE:
93  				state = truue();
94  				break;
95  			case TRUE_ALL:
96  				return bt;
97  			default:
98  				return null;
99  			}
100 		}
101 	}
102 
103 	private int truue() throws Throwable {
104 		for (ChoicePoint cp = stack[stackPos]; cp != null; cp = cp.parent) {
105 			if (cp.hasTODO())
106 				// TRO complex - here, if the last rule to be added is the same
107 				// rule as topOfStack which has no more TODOs or alternatives,
108 				// then it should be possible to reuse topOfStack. this requires
109 				// some heavy lifting adjusting the gc system
110 				return addToStack(cp.getTODO(), cp.bodyCtx, cp);
111 		}
112 		return TRUE_ALL;
113 	}
114 
115 	private int back() {
116 		for (; stackPos >= 0; stackPos--) {
117 			bt.collectGarbage(stackPos);
118 			ChoicePoint topOfStack = stack[stackPos];
119 			if (topOfStack.hasAlternatives())
120 				return RULE;
121 			topOfStack.fail();
122 		}
123 		return FALSE;
124 	}
125 
126 	private int eval() throws Throwable {
127 		ChoicePoint cp = stack[stackPos];
128 		return Prolog.evalPrimitive(cp.prim, bt.resolveArgs(cp.head, cp.headCtx)) ? TRUE : BACK;
129 	}
130 
131 	private int ruleSelect() throws Throwable {
132 		ChoicePoint topOfStack = stack[stackPos];
133 		while (topOfStack.hasAlternatives()) {
134 			Clause next = topOfStack.nextAlternative();
135 			int newCtx = bt.getUniqueExecutionCtxID();
136 			if (bt.unifyBranch(topOfStack.head, next.head, topOfStack.headCtx, newCtx)) {
137 				topOfStack.setBody(next.tail, newCtx);
138 				// TRO very simple - here, if the last rule to be added is the
139 				// same rule as topOfStack which has no more TODOs or
140 				// alternatives, then it should be possible to reuse topOfStack.
141 
142 				// return addToStack(topOfStack.getTODO(), newCtx, topOfStack);
143 
144 				// This is a contribution to
145 				// fix bug AIOB Exception raise
146 				// in old code when invoke
147 				// topOfStack.getTODO()
148 				// without previous index check
149 				if (topOfStack.hasTODO()) {
150 					return addToStack(topOfStack.getTODO(), newCtx, topOfStack);
151 				}
152 				return TRUE;
153 			}
154 			bt.collectGarbageSmall();
155 		}
156 		return BACK;
157 	}
158 
159 	/**
160 	 * removes comma and cut. Comma => the struct is set as elements in a list,
161 	 * commas are split up as elements in this list and commas removed Cut =>
162 	 * run separate method Primitive => evaluated else Rule => rules added, sent
163 	 * to RULE
164 	 */
165 	private int addToStack(Struct head, int headCtx, ChoicePoint parent) throws PrologException {
166 		++stackPos;
167 		if (stackPos == stack.length)
168 			doubleStackSize();
169 		bt.setCurrentExecCtx(stackPos);
170 		ChoicePoint topOfStack = stack[stackPos];
171 		topOfStack.set(head, headCtx, parent);
172 
173 		if (head.predicateIndicator == Parser.callSignature) {
174 			int ctx = headCtx;
175 			Term callArg = bt.resolveFaster(head.getArg(0), ctx);
176 			if (bt.secondOutOfFasterResolve != Integer.MAX_VALUE)
177 				ctx = bt.secondOutOfFasterResolve;
178 			if (callArg instanceof Number)
179 				throw new PrologException("type_error(callable, " + callArg + ")");
180 			if (callArg instanceof Var)
181 				throw new PrologException("instantiation_error");
182 			topOfStack.setBody(BuiltIn.convertTermToClauseBody2(callArg), ctx);
183 			return addToStack(topOfStack.getTODO(), ctx, topOfStack);
184 		}
185 		if (head.predicateIndicator == Parser.cutSignature)
186 			return cut(parent.cutParent);
187 
188 		topOfStack.prim = prolog.getPrimitive(head);
189 		if (topOfStack.prim != null)
190 			return EVAL;
191 		List rules = prolog.find(head.predicateIndicator);
192 		topOfStack.setRules(rules);
193 		return RULE;
194 	}
195 
196 	/**
197 	 * clear all ; and , backtracking alternatives up to and including the first
198 	 * point in the stack that is not , or ; or !.
199 	 */
200 	private int cut(final ChoicePoint cutParent) {
201 		for (Iterator it = stackIterator(); it.hasNext();) {
202 			ChoicePoint next = (ChoicePoint) it.next();
203 			next.cutAlternatives();
204 			if (next == cutParent)
205 				return TRUE;
206 		}
207 		return TRUE;
208 	}
209 
210 	boolean hasAlternatives() {
211 		for (Iterator it = stackIterator(); it.hasNext();) {
212 			if (((ChoicePoint) it.next()).hasAlternatives())
213 				return true;
214 		}
215 		return false;
216 	}
217 
218 	private void doubleStackSize() {
219 		final int newSize = stack.length * 2;
220 		ChoicePoint[] newArray = new ChoicePoint[newSize];
221 		System.arraycopy(stack, 0, newArray, 0, stack.length);
222 		for (int i = stack.length; i < newSize; i++)
223 			newArray[i] = new ChoicePoint();
224 		stack = newArray;
225 		bt.expandLinkTable(newSize);
226 	}
227 
228 	StackIterator stackIterator() {
229 		return new StackIterator(stackPos, stack);
230 	}
231 
232 	private static class StackIterator implements Iterator {
233 		int pos;
234 		ChoicePoint[] stack;
235 
236 		public StackIterator(int start, ChoicePoint[] stack) {
237 			this.pos = start;
238 			this.stack = stack;
239 		}
240 
241 		public boolean hasNext() {
242 			return pos >= 0;
243 		}
244 
245 		public Object next() {
246 			return stack[pos--];
247 		}
248 
249 		public void remove() {
250 			throw new RuntimeException("can't remove while iterating the stack in the engine");
251 		}
252 	}
253 
254 	public String toString() {
255 		StringBuffer s = new StringBuffer();
256 		for (StackIterator it = stackIterator(); it.hasNext();) {
257 			s.append(it.next().toString() + " \n \n");
258 			s.append(gc_data(it.pos + 1));
259 		}
260 		s.append(query);
261 		return s.toString();
262 	}
263 
264 	private String gc_data(int pos) {
265 		String s = "";
266 		int[][] gc_data = bt.getKeysForCp(pos);
267 		for (int i = 0; i < gc_data.length; i++) {
268 			int[] varNr_Ctx = gc_data[i];
269 			int vNr = varNr_Ctx[0];
270 			int vCtx = varNr_Ctx[1];
271 			if (vNr == 0)
272 				continue;
273 			Var vFake = new Var("V", vNr);
274 			s += vFake + "_" + vNr + "<" + vCtx + "> : ";
275 			Term link = bt.resolveFaster(vFake, vCtx);
276 			if (bt.secondOutOfFasterResolve != Integer.MAX_VALUE)
277 				s += link + "<" + bt.secondOutOfFasterResolve + ">\n";
278 			else
279 				s += "what?!\n";
280 		}
281 		return s;
282 	}
283 }