1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
34
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
73
74
75
76
77
78
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
107
108
109
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
139
140
141
142
143
144
145
146
147
148
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
161
162
163
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
198
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 }