1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.kuali.student.common.ui.client.widgets.rules;
17
18 import java.util.ArrayList;
19 import java.util.List;
20 import java.util.Stack;
21
22 import org.kuali.student.common.ui.client.widgets.table.Node;
23 import org.kuali.student.core.statement.dto.StatementInfo;
24 import org.kuali.student.core.statement.dto.StatementOperatorTypeKey;
25
26 import com.google.gwt.core.client.GWT;
27
28 public class RuleExpressionParser {
29
30 private String expression;
31 private List<Token> tokenList;
32
33 private void checkExpressionSet() {
34 if (tokenList == null || expression == null) {
35 throw new java.lang.IllegalStateException("setExpression must be called first");
36 }
37 }
38
39 public void checkMissingRCs(List<ReqComponentVO> missingRCs, List<ReqComponentVO> rcs) {
40 checkExpressionSet();
41
42 List<String> conditionValues = new ArrayList<String>();
43 for (Token token : tokenList) {
44 if (token.type == Token.Condition) {
45 conditionValues.add(token.value);
46 }
47 }
48
49 if (rcs != null && !rcs.isEmpty()) {
50 for (ReqComponentVO rc : rcs) {
51 boolean foundId = false;
52 if (!conditionValues.isEmpty()) {
53 for (String conditionValue : conditionValues) {
54 if (conditionValue != null && conditionValue.equalsIgnoreCase(rc.getGuiReferenceLabelId())) {
55 foundId = true;
56 break;
57 }
58 }
59 }
60 if (!foundId) {
61 missingRCs.add(rc);
62 }
63 }
64 }
65 }
66
67 public boolean validateExpression(List<String> errorMessages, List<ReqComponentVO> validRCs) {
68 checkExpressionSet();
69 return doValidateExpression(errorMessages, tokenList, validRCs);
70 }
71
72 private boolean doValidateExpression(List<String> errorMessages, final List<Token> tokens, List<ReqComponentVO> validRCs) {
73 boolean valid = true;
74 List<String> seenConditonValues = new ArrayList<String>();
75
76 if (tokens.size() == 0) {
77 return true;
78 }
79
80 if ((tokens.get(0).type == Token.StartParenthesis
81 || tokens.get(0).type == Token.Condition) == false) {
82 errorMessages.add("must start with ( or condition");
83 return false;
84 }
85 int lastIndex = tokens.size() - 1;
86 if ((tokens.get(lastIndex).type == Token.EndParenthesis || tokens.get(lastIndex).type == Token.Condition) == false) {
87 errorMessages.add("must end with ) or condition");
88 return false;
89 }
90 if (countToken(tokens, Token.StartParenthesis) != countToken(tokens, Token.EndParenthesis)) {
91 errorMessages.add("() not in pair");
92 return false;
93 }
94
95 for (int i = 0; i < tokens.size(); i++) {
96 Token token = tokens.get(i);
97 if (token.type == Token.And) {
98 if (!checkAnd(errorMessages, tokens, i)) {
99 return false;
100 }
101 } else if (token.type == Token.Or) {
102 if (!checkOr(errorMessages, tokens, i)) {
103 return false;
104 }
105 } else if (token.type == Token.StartParenthesis) {
106 if (!checkStartParenthesis(errorMessages, tokens, i)) {
107 return false;
108 }
109 } else if (token.type == Token.EndParenthesis) {
110 if (!checkEndParenthesis(errorMessages, tokens, i)) {
111 return false;
112 }
113 } else if (token.type == Token.Condition) {
114 if (seenConditonValues.contains(token.value)) {
115 errorMessages.add("Condition " + token.value + " is duplicated.");
116 continue;
117 } else {
118 seenConditonValues.add(token.value);
119 }
120 if (!checkCondition(errorMessages, tokens, i, validRCs)) {
121 continue;
122 }
123 }
124 }
125 return valid;
126 }
127
128 private int countToken(List<Token> tokenList, int type) {
129 int count = 0;
130 for (Token t : tokenList) {
131 if (t.type == type) {
132 count++;
133 }
134 }
135 return count;
136 }
137
138 private boolean checkAnd(List<String> errorMessages, List<Token> tokenList, int currentIndex) {
139 Token prevToken = (tokenList == null || currentIndex - 1 < 0)? null :
140 tokenList.get(currentIndex - 1);
141 Token nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size())? null :
142 tokenList.get(currentIndex + 1);
143 boolean validToken = true;
144 if (prevToken != null && (prevToken.type == Token.Condition || prevToken.type == Token.EndParenthesis) == false) {
145 errorMessages.add("only ) and condition could sit before and");
146 validToken = false;
147 }
148 if (nextToken != null && (nextToken.type == Token.Condition || nextToken.type == Token.StartParenthesis) == false) {
149 errorMessages.add("only ( and condition could sit after and");
150 validToken = false;
151 }
152 return validToken;
153 }
154
155 private boolean checkOr(List<String> errorMessages, List<Token> tokenList, int currentIndex) {
156 Token prevToken = (tokenList == null || currentIndex - 1 < 0)? null :
157 tokenList.get(currentIndex - 1);
158 Token nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size())? null :
159 tokenList.get(currentIndex + 1);
160 boolean validToken = true;
161 if (prevToken != null && (prevToken.type == Token.Condition || prevToken.type == Token.EndParenthesis) == false) {
162 errorMessages.add("only ) and condition could sit before or");
163 validToken = false;
164 }
165 if (nextToken != null && (nextToken.type == Token.Condition || nextToken.type == Token.StartParenthesis) == false) {
166 errorMessages.add("only ( and condition could sit after or");
167 validToken = false;
168 }
169 return validToken;
170 }
171
172 private boolean checkStartParenthesis(List<String> errorMessages, List<Token> tokenList, int currentIndex) {
173 Token prevToken = (tokenList == null || currentIndex - 1 < 0)? null :
174 tokenList.get(currentIndex - 1);
175 Token nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size())? null :
176 tokenList.get(currentIndex + 1);
177 boolean validToken = true;
178 if (prevToken != null && (prevToken.type == Token.And || prevToken.type == Token.Or || prevToken.type == Token.StartParenthesis) == false) {
179 errorMessages.add("only and, or, ( could sit before (");
180 validToken = false;
181 }
182 if (nextToken != null && (nextToken.type == Token.Condition || nextToken.type == Token.StartParenthesis) == false) {
183 errorMessages.add("only ( and condition could sit after (");
184 validToken = false;
185 }
186 return validToken;
187 }
188
189 private boolean checkEndParenthesis(List<String> errorMessages, List<Token> tokenList, int currentIndex) {
190 Token prevToken = (tokenList == null || currentIndex - 1 < 0)? null :
191 tokenList.get(currentIndex - 1);
192 Token nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size())? null :
193 tokenList.get(currentIndex + 1);
194 boolean validToken = true;
195 if (prevToken != null && (prevToken.type == Token.Condition || prevToken.type == Token.EndParenthesis) == false) {
196 errorMessages.add("only condition and ) could sit before )");
197 validToken = false;
198 }
199 if (nextToken != null && (nextToken.type == Token.Or || nextToken.type == Token.And || nextToken.type == Token.EndParenthesis) == false) {
200 errorMessages.add("only ), and, or could sit after )");
201 validToken = false;
202 }
203 return validToken;
204 }
205
206 private boolean checkCondition(List<String> errorMessages, List<Token> tokenList, int currentIndex,
207 List<ReqComponentVO> validRCs) {
208 Token prevToken = (tokenList == null || currentIndex - 1 < 0)? null :
209 tokenList.get(currentIndex - 1);
210 Token nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size())? null :
211 tokenList.get(currentIndex + 1);
212 boolean validToken = true;
213 if (prevToken != null && (prevToken.type == Token.And || prevToken.type == Token.Or || prevToken.type == Token.StartParenthesis) == false) {
214 errorMessages.add("only and, or could sit before condition");
215 validToken = false;
216 }
217 if (nextToken != null && (nextToken.type == Token.Or || nextToken.type == Token.And || nextToken.type == Token.EndParenthesis) == false) {
218 errorMessages.add("only ), and, or could sit after condition");
219 validToken = false;
220 }
221 Token conditionToken = tokenList.get(currentIndex);
222 String conditionLetter = conditionToken.value;
223 boolean validConditonLetter = false;
224 if (validRCs != null) {
225 for (ReqComponentVO rc : validRCs) {
226 if (rc.getGuiReferenceLabelId() != null &&
227 rc.getGuiReferenceLabelId().equalsIgnoreCase(conditionLetter)) {
228 validConditonLetter = true;
229 }
230 }
231 }
232 if (!validConditonLetter) {
233 errorMessages.add(conditionLetter + " is not a valid conditon");
234 validToken = false;
235 }
236 return validToken;
237 }
238
239 public Node parseExpressionIntoTree(String expression, StatementVO statementVO, String statementType) {
240 Node tree = null;
241 if (expression != null && expression.trim().length() > 0) {
242 StatementVO parsedS = parseExpressionIntoStatementVO(expression, statementVO, statementType);
243 if (parsedS != null) {
244 tree = parsedS.getTree();
245 }
246 }
247 return tree;
248 }
249
250 public StatementVO parseExpressionIntoStatementVO(String expression, StatementVO statementVO, String statementType) {
251 StatementVO parsedS = null;
252
253 if (expression.trim().isEmpty()) {
254 statementVO.clearStatementAndReqComponents();
255 return statementVO;
256 }
257
258 List<ReqComponentVO> rcs = statementVO.getAllReqComponentVOs();
259 try {
260 List<String> tokenValueList = getTokenValue(expression);
261 List<Token> tokenList = getTokenList(tokenValueList);
262 if (!doValidateExpression(new ArrayList<String>(), tokenList, rcs)) return null;
263 List<Node<Token>> nodeList = toNodeList(tokenList);
264 List<Node<Token>> rpnList = getRPN(nodeList);
265 parsedS = statementVOFromRPN(rpnList, rcs, statementType);
266
267 if (parsedS != null) {
268 parsedS.simplify();
269 }
270 } catch (Exception error) {
271 GWT.log("Exception parsing",error);
272 }
273 return parsedS;
274 }
275
276 private ReqComponentVO lookupReqComponent(List<ReqComponentVO> rcs, String guiKey) {
277 ReqComponentVO result = null;
278 if (rcs != null) {
279 for (ReqComponentVO rc : rcs) {
280 if (rc.getGuiReferenceLabelId() != null && rc.getGuiReferenceLabelId().equalsIgnoreCase(guiKey)) {
281 result = rc;
282 break;
283 }
284 }
285 }
286 return result;
287 }
288
289
290 private StatementVO statementVOFromRPN(List<Node<Token>> rpnList, List<ReqComponentVO> rcs, String statementType) {
291 StatementVO statementVO;
292
293
294 if (rpnList.size() == 0) {
295 return new StatementVO();
296 }
297
298 Stack<Node<? extends Token>> conditionStack = new Stack<Node<? extends Token>>();
299 for (Node<Token> node : rpnList) {
300 if (node.getUserObject().type == Token.Condition) {
301 ReqComponentVO rc = null;
302 Node<ReqComponentVO> rcNode = null;
303 rc = lookupReqComponent(rcs, node.getUserObject().value);
304 if (rc != null) {
305 rcNode = new Node<ReqComponentVO>();
306 rcNode.setUserObject(rc);
307 }
308 conditionStack.push(rcNode);
309 } else if (node.getUserObject().type == Token.And || node.getUserObject().type == Token.Or) {
310 StatementVO subS = new StatementVO();
311 subS.setTokenOperator(true);
312 StatementOperatorTypeKey op = null;
313 if (node.getUserObject().type == Token.And) {
314 op = StatementOperatorTypeKey.AND;
315 } else if (node.getUserObject().type == Token.Or) {
316 op = StatementOperatorTypeKey.OR;
317 }
318 StatementInfo statementInfo = new StatementInfo();
319 statementInfo.setOperator(op);
320 statementInfo.setType(statementType);
321 subS.setStatementInfo(statementInfo);
322 Token right = conditionStack.pop().getUserObject();
323 Token left = conditionStack.pop().getUserObject();
324 List<ReqComponentVO> nodeRcs = new ArrayList<ReqComponentVO>();
325 if (left instanceof ReqComponentVO) {
326 nodeRcs.add((ReqComponentVO) left);
327 }
328 if (right instanceof ReqComponentVO) {
329 nodeRcs.add((ReqComponentVO) right);
330 }
331
332
333 if (nodeRcs != null && nodeRcs.size() == 2) {
334 subS.addReqComponentVOs(nodeRcs);
335 } else {
336 if (left instanceof ReqComponentVO) {
337 subS.addStatementVO(wrapReqComponent(op, (ReqComponentVO)left, statementType));
338 } else {
339 subS.addStatementVO((StatementVO)left);
340 }
341 if (right instanceof ReqComponentVO) {
342 subS.addStatementVO(wrapReqComponent(op, (ReqComponentVO)right, statementType));
343 } else {
344 subS.addStatementVO((StatementVO)right);
345 }
346 }
347
348 Node<StatementVO> nodeS = new Node<StatementVO>();
349 nodeS.setUserObject(subS);
350 conditionStack.push(nodeS);
351 }
352 }
353
354 if (conditionStack.peek().getUserObject() instanceof ReqComponentVO) {
355 statementVO = wrapReqComponent(StatementOperatorTypeKey.AND,
356 (ReqComponentVO)conditionStack.pop().getUserObject(), statementType);
357 } else {
358 statementVO = (StatementVO)conditionStack.pop().getUserObject();
359 }
360 statementVO.getStatementInfo().setType(statementType);
361
362 return statementVO;
363 }
364
365 private StatementVO wrapReqComponent(StatementOperatorTypeKey op, ReqComponentVO rc, String statementType) {
366 StatementVO wrapS = new StatementVO();
367 StatementInfo wrapStatementInfo = new StatementInfo();
368 wrapStatementInfo.setOperator(op);
369 wrapStatementInfo.setType(statementType);
370 wrapS.setStatementInfo(wrapStatementInfo);
371 wrapS.addReqComponentVO(rc);
372 return wrapS;
373 }
374
375
376
377
378
379
380
381
382 private List<Node<Token>> getRPN(List<Node<Token>> nodeList) {
383 List<Node<Token>> rpnList = new ArrayList<Node<Token>>();
384 Stack<Node<Token>> operatorStack = new Stack<Node<Token>>();
385
386 for (Node<Token> node : nodeList) {
387 if (node.getUserObject().type == Token.Condition) {
388 rpnList.add(node);
389
390 } else if (node.getUserObject().type == Token.And) {
391 operatorStack.push(node);
392 } else if (node.getUserObject().type == Token.StartParenthesis) {
393 operatorStack.push(node);
394 } else if (node.getUserObject().type == Token.Or) {
395
396 if (operatorStack.isEmpty() == false && operatorStack.peek().getUserObject().type == Token.And) {
397 do {
398 rpnList.add(operatorStack.pop());
399 } while (operatorStack.isEmpty() == false && operatorStack.peek().getUserObject().type == Token.And);
400 }
401
402 operatorStack.push(node);
403 } else if (node.getUserObject().type == Token.EndParenthesis) {
404 while (operatorStack.peek().getUserObject().type != Token.StartParenthesis) {
405 rpnList.add(operatorStack.pop());
406 }
407 operatorStack.pop();
408 }
409 }
410 if (operatorStack.isEmpty() == false) {
411 do {
412 rpnList.add(operatorStack.pop());
413 } while (operatorStack.isEmpty() == false);
414 }
415 return rpnList;
416 }
417
418 private List<Node<Token>> toNodeList(List<Token> tokenList) {
419 List<Node<Token>> nodeList = new ArrayList<Node<Token>>();
420 for (Token token : tokenList) {
421 Node<Token> node = new Node<Token>();
422 node.setUserObject(token);
423 nodeList.add(node);
424 }
425 return nodeList;
426 }
427
428 private List<Token> getTokenList(List<String> tokenValueList) {
429 List<Token> tokenList = new ArrayList<Token>();
430 for (String value : tokenValueList) {
431 if (value.isEmpty()) {
432 continue;
433 }
434 if ("(".equals(value)) {
435 Token t = new Token();
436 t.type = Token.StartParenthesis;
437 tokenList.add(t);
438 } else if (")".equals(value)) {
439 Token t = new Token();
440 t.type = Token.EndParenthesis;
441 tokenList.add(t);
442
443 } else if ("and".equals(value)) {
444 Token t = new Token();
445 t.type = Token.And;
446 tokenList.add(t);
447
448 } else if ("or".equals(value)) {
449 Token t = new Token();
450 t.type = Token.Or;
451 tokenList.add(t);
452
453 } else {
454 Token t = new Token();
455 t.type = Token.Condition;
456 t.value = value;
457 tokenList.add(t);
458
459 }
460 }
461 return tokenList;
462 }
463
464 private List<String> getTokenValue(String expression) {
465 expression = expression.toLowerCase();
466 List<String> tokenValueList = new ArrayList<String>();
467 StringBuffer tokenValue = new StringBuffer();
468 for (int i = 0; i < expression.length(); i++) {
469
470 char ch = expression.charAt(i);
471 if (ch == ' ') {
472 tokenValueList.add(tokenValue.toString());
473 tokenValue = new StringBuffer();
474 } else if (ch == '(' || ch == ')') {
475 tokenValueList.add(tokenValue.toString());
476 tokenValue = new StringBuffer();
477 tokenValueList.add(String.valueOf(ch));
478 } else {
479 tokenValue.append(ch);
480 }
481 }
482 tokenValueList.add(tokenValue.toString());
483 return tokenValueList;
484 }
485
486 public void setExpression(String expression) {
487 this.expression = expression;
488 List<String> tokenValueList = getTokenValue(expression);
489 this.tokenList = getTokenList(tokenValueList);
490 }
491
492 public String getExpression() {
493 return expression;
494 }
495
496 }