1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.kuali.rice.krms.util;
17
18 import org.kuali.rice.krms.api.repository.LogicalOperator;
19 import org.kuali.rice.krms.api.repository.proposition.PropositionType;
20 import org.kuali.rice.krms.dto.PropositionEditor;
21 import org.kuali.rice.krms.dto.RuleEditor;
22 import org.kuali.rice.krms.service.RuleViewHelperService;
23
24 import java.util.ArrayList;
25 import java.util.LinkedHashMap;
26 import java.util.LinkedList;
27 import java.util.List;
28 import java.util.Map;
29 import java.util.Queue;
30 import java.util.Stack;
31
32
33
34
35
36
37 public class RuleLogicExpressionParser {
38
39 private String expression;
40 private boolean isOtiose;
41
42 private List<ExpressionToken> tokenList;
43
44 private void checkExpressionSet() {
45 if (tokenList == null || expression == null) {
46 throw new java.lang.IllegalStateException("setExpression must be called first");
47 }
48 }
49
50 public boolean validateExpression(List<String> errorMessages, List<String> keyList) {
51 checkExpressionSet();
52 return doValidateExpression(errorMessages, tokenList, keyList);
53 }
54
55 private boolean doValidateExpression(List<String> errorMessages, final List<ExpressionToken> tokens, List<String> keyList) {
56 boolean valid = true;
57 List<String> seenConditonValues = new ArrayList<String>();
58
59
60 if (tokens.size() > 0) {
61
62 int firstToken = 0;
63 int firstTokenType = tokens.get(firstToken).getType();
64 if ((firstTokenType != ExpressionToken.PARENTHESIS_START)
65 && (firstTokenType != ExpressionToken.CONDITION)) {
66 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_LOGIC_EXPRESSION_START);
67 return false;
68 }
69 } else {
70 return true;
71 }
72 if (countToken(tokens, ExpressionToken.PARENTHESIS_START) != countToken(tokens, ExpressionToken.PARENTHESIS_END)) {
73 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PARENTHESIS_NOT_PAIR);
74 return false;
75 }
76 if (!validateAndOr(errorMessages, tokens)) {
77 return false;
78 }
79
80 for (int i = 0; i < tokens.size(); i++) {
81 ExpressionToken token = tokens.get(i);
82
83 ExpressionToken prevToken = i - 1 < 0 ? null : tokens.get(i - 1);
84 ExpressionToken nextToken = i + 1 >= tokens.size() ? null : tokens.get(i + 1);
85
86 if (token.getType() == ExpressionToken.OPERATOR_AND) {
87 if (!checkAnd(errorMessages, prevToken, nextToken)) {
88 return false;
89 }
90 } else if (token.getType() == ExpressionToken.OPERATOR_OR) {
91 if (!checkOr(errorMessages, prevToken, nextToken)) {
92 return false;
93 }
94 } else if (token.getType() == ExpressionToken.PARENTHESIS_START) {
95 if (!checkStartParenthesis(errorMessages, nextToken)) {
96 return false;
97 }
98 } else if (token.getType() == ExpressionToken.PARENTHESIS_END) {
99 if (!checkEndParenthesis(errorMessages, prevToken, nextToken)) {
100 return false;
101 }
102 } else if (token.getType() == ExpressionToken.CONDITION) {
103 if (seenConditonValues.contains(token.getValue())) {
104 errorMessages.add("Condition " + token.getValue() + " is duplicated.");
105 return false;
106 } else {
107 seenConditonValues.add(token.getValue());
108 }
109 if (!checkCondition(errorMessages, prevToken, nextToken, i, keyList)) {
110 return false;
111 }
112 }
113 }
114 return valid;
115 }
116
117 private boolean validateAndOr(List<String> errorMessages, List<ExpressionToken> nodeList) {
118 Stack<ExpressionToken> operatorStack = new Stack<ExpressionToken>();
119
120 for (ExpressionToken token : nodeList) {
121 if (token.getType() == ExpressionToken.PARENTHESIS_END) {
122 ExpressionToken operator = operatorStack.pop();
123
124
125 if (operator.getType() != ExpressionToken.PARENTHESIS_START) {
126
127
128 while (operatorStack.peek().getType() != ExpressionToken.PARENTHESIS_START) {
129 ExpressionToken next = operatorStack.pop();
130 if (next.getType() != operator.getType()) {
131 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_OPERATOR_TYPE);
132 return false;
133 }
134 }
135
136 operatorStack.pop();
137 }
138 } else if (token.getType() != ExpressionToken.CONDITION) {
139 operatorStack.push(token);
140 }
141 }
142 if (!operatorStack.isEmpty()) {
143 ExpressionToken operator = operatorStack.pop();
144
145 while (!operatorStack.isEmpty()) {
146 ExpressionToken next = operatorStack.pop();
147 if (next.getType() != operator.getType()) {
148 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_OPERATOR_TYPE);
149 return false;
150 }
151 }
152 }
153
154 return true;
155 }
156
157 private int countToken(List<ExpressionToken> tokenList, int type) {
158 int count = 0;
159 for (ExpressionToken t : tokenList) {
160 if (t.getType() == type) {
161 count++;
162 }
163 }
164 return count;
165 }
166
167 private boolean checkAnd(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken) {
168 boolean validToken = true;
169 if ((prevToken != null) && (prevToken.getType() != ExpressionToken.CONDITION) && (prevToken.getType() != ExpressionToken.PARENTHESIS_END)) {
170 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PRECEDE_OPERATOR);
171 validToken = false;
172 }
173 if ((nextToken != null) && (nextToken.getType() != ExpressionToken.CONDITION) && (nextToken.getType() != ExpressionToken.PARENTHESIS_START)) {
174 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_OPERATOR);
175 validToken = false;
176 }
177 return validToken;
178 }
179
180 private boolean checkOr(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken) {
181 boolean validToken = true;
182 if ((prevToken != null) && (prevToken.getType() != ExpressionToken.CONDITION) && (prevToken.getType() != ExpressionToken.PARENTHESIS_END)) {
183 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PRECEDE_OR);
184 validToken = false;
185 }
186 if ((nextToken != null) && (nextToken.getType() != ExpressionToken.CONDITION) && (nextToken.getType() != ExpressionToken.PARENTHESIS_START)) {
187 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_OR);
188 validToken = false;
189 }
190 return validToken;
191 }
192
193 private boolean checkStartParenthesis(List<String> errorMessages, ExpressionToken nextToken) {
194 boolean validToken = true;
195 if ((nextToken != null) && (nextToken.getType() != ExpressionToken.CONDITION) && (nextToken.getType() != ExpressionToken.PARENTHESIS_START)) {
196 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_START_PARENTHESIS);
197 validToken = false;
198 }
199 return validToken;
200 }
201
202 private boolean checkEndParenthesis(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken) {
203 boolean validToken = true;
204 if ((prevToken != null) && (prevToken.getType() != ExpressionToken.CONDITION) && (prevToken.getType() == ExpressionToken.PARENTHESIS_END)) {
205 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PRECEDE_END_PARENTHESIS);
206 validToken = false;
207 }
208 if ((nextToken != null) && (!ExpressionToken.isOperator(nextToken.getType())) && (nextToken.getType() != ExpressionToken.PARENTHESIS_END)) {
209 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_END_PARENTHESIS);
210 validToken = false;
211 }
212 return validToken;
213 }
214
215 private boolean checkCondition(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken, int currentIndex,
216 List<String> keyList) {
217 boolean validToken = true;
218 if ((prevToken != null) && (!ExpressionToken.isOperator(prevToken.getType())) && (prevToken.getType() != ExpressionToken.PARENTHESIS_START)) {
219 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PRECEDE_CONDITION);
220 validToken = false;
221 }
222 if ((nextToken != null) && (!ExpressionToken.isOperator(nextToken.getType())) && (nextToken.getType() != ExpressionToken.PARENTHESIS_END) && (nextToken.getType() != ExpressionToken.PARENTHESIS_START)) {
223 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_CONDITION);
224 validToken = false;
225 }
226
227 ExpressionToken conditionToken = tokenList.get(currentIndex);
228 if((!keyList.contains(conditionToken.getValue().toLowerCase())) && (!keyList.contains(conditionToken.getValue().toUpperCase()))){
229 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_INVALID_CONDITION);
230 validToken = false;
231 }
232
233 return validToken;
234 }
235
236 private List<ExpressionToken> getTokenList(List<String> tokenValueList) {
237 List<ExpressionToken> returnList = new ArrayList<ExpressionToken>();
238 for (String value : tokenValueList) {
239 if (value.isEmpty()) {
240 continue;
241 }
242 if ("(".equals(value)) {
243 ExpressionToken t = new ExpressionToken();
244 t.setType(ExpressionToken.PARENTHESIS_START);
245 returnList.add(t);
246 } else if (")".equals(value)) {
247 ExpressionToken t = new ExpressionToken();
248 t.setType(ExpressionToken.PARENTHESIS_END);
249 returnList.add(t);
250
251 } else if ("and".equals(value)) {
252 ExpressionToken t = new ExpressionToken();
253 t.setType(ExpressionToken.OPERATOR_AND);
254 returnList.add(t);
255
256 } else if ("or".equals(value)) {
257 ExpressionToken t = new ExpressionToken();
258 t.setType(ExpressionToken.OPERATOR_OR);
259 returnList.add(t);
260
261 } else {
262 ExpressionToken t = new ExpressionToken();
263 t.setType(ExpressionToken.CONDITION);
264 t.setValue(value);
265 returnList.add(t);
266
267 }
268 }
269 return returnList;
270 }
271
272 private List<String> getTokenValue(String expression) {
273 List<String> tokenValueList = new ArrayList<String>();
274 StringBuilder tokenValue = new StringBuilder();
275 for (int i = 0; i < expression.length(); i++) {
276
277 char ch = expression.charAt(i);
278 if (Character.isSpaceChar(ch)) {
279 tokenValueList.add(tokenValue.toString());
280 tokenValue = new StringBuilder();
281 } else if (ch == '(' || ch == ')') {
282 tokenValueList.add(tokenValue.toString());
283 tokenValue = new StringBuilder();
284 tokenValueList.add(String.valueOf(ch));
285 } else {
286 tokenValue.append(ch);
287 }
288 }
289 tokenValueList.add(tokenValue.toString());
290 return tokenValueList;
291 }
292
293 public void setExpression(String expression) {
294 this.expression = expression;
295 List<String> tokenValueList = getTokenValue(expression.toLowerCase());
296 this.tokenList = getTokenList(tokenValueList);
297 }
298
299 public String getExpression() {
300 return expression;
301 }
302
303 public List<ExpressionToken> getTokenList() {
304 return tokenList;
305 }
306
307
308
309
310
311
312
313
314 public PropositionEditor parseExpressionIntoRule(RuleEditor ruleEditor, RuleViewHelperService viewHelper) {
315
316 Stack<ExpressionToken> tokenStack = new Stack<ExpressionToken>();
317 int index = 0;
318 isOtiose = false;
319 for (ExpressionToken token : tokenList) {
320 if (isOtioseCompound(token, tokenList, index)) {
321 index++;
322 continue;
323 }
324
325 tokenStack.push(token);
326 index++;
327 }
328
329
330 if (tokenStack.isEmpty()) {
331 return null;
332 }
333
334
335 if(tokenStack.isEmpty()){
336 return null;
337 }
338
339 Map<String, PropositionEditor> simplePropositions = new LinkedHashMap<String, PropositionEditor>();
340 Queue<PropositionEditor> compoundPropositions = new LinkedList<PropositionEditor>();
341 this.setupPropositions(simplePropositions, compoundPropositions, ruleEditor.getPropositionEditor());
342
343 return ruleFromStack(tokenStack, simplePropositions, compoundPropositions, ruleEditor, viewHelper);
344 }
345
346 private boolean isOtioseCompound(ExpressionToken token, List<ExpressionToken> tokenList, int index) {
347
348 if (token.getType() == ExpressionToken.PARENTHESIS_END && isOtiose) {
349 isOtiose = false;
350 return true;
351 }
352
353 if (token.getType() == ExpressionToken.PARENTHESIS_START) {
354 if (tokenList.size() > index + 2) {
355 if (tokenList.get(index + 1).getType() == ExpressionToken.CONDITION && tokenList.get(index + 2).getType() == ExpressionToken.PARENTHESIS_END) {
356 isOtiose = true;
357 return true;
358 }
359 }
360 }
361 return false;
362 }
363
364
365
366
367
368
369
370
371
372
373
374
375 private void setupPropositions(Map<String, PropositionEditor> simplePropositions, Queue<PropositionEditor> compoundPropositions, PropositionEditor propositionEditor) {
376 if (propositionEditor.getPropositionTypeCode().equals(PropositionType.SIMPLE.getCode())) {
377 simplePropositions.put(propositionEditor.getKey(), propositionEditor);
378 } else {
379 compoundPropositions.add(propositionEditor);
380 for (PropositionEditor child : propositionEditor.getCompoundEditors()) {
381 this.setupPropositions(simplePropositions, compoundPropositions, child);
382 }
383 propositionEditor.setCompoundEditors(new ArrayList<PropositionEditor>());
384 }
385
386 }
387
388
389
390
391
392
393
394
395
396
397
398
399 public PropositionEditor ruleFromStack(Stack<ExpressionToken> tokenStack, Map<String, PropositionEditor> simplePropositions,
400 Queue<PropositionEditor> compoundPropositions, RuleEditor rule, RuleViewHelperService viewHelper) {
401
402
403 if (tokenStack.size() == 1) {
404 ExpressionToken token = tokenStack.pop();
405 return simplePropositions.remove(token.getValue().toUpperCase());
406 }
407
408
409 if(tokenStack.size()==1){
410 ExpressionToken token = tokenStack.pop();
411 return simplePropositions.remove(token.getValue().toUpperCase());
412 }
413
414
415 PropositionEditor currentCompound = null;
416 if (compoundPropositions.peek() == null) {
417 currentCompound = new PropositionEditor();
418 currentCompound.setPropositionTypeCode(PropositionType.COMPOUND.getCode());
419 currentCompound.setRuleId(rule.getId());
420 currentCompound.setKey((String) rule.getCompoundKeys().next());
421 currentCompound.setCompoundEditors(new ArrayList<PropositionEditor>());
422 } else {
423 currentCompound = compoundPropositions.remove();
424 }
425
426
427 while (!tokenStack.empty()) {
428 ExpressionToken token = tokenStack.pop();
429 if (token.getType() == ExpressionToken.PARENTHESIS_END) {
430 PropositionEditor compound = ruleFromStack(tokenStack, simplePropositions, compoundPropositions, rule, viewHelper);
431 currentCompound.getCompoundEditors().add(0, compound);
432 } else if (token.getType() == ExpressionToken.PARENTHESIS_START) {
433 return currentCompound;
434 } else if (token.getType() == ExpressionToken.CONDITION) {
435 currentCompound.getCompoundEditors().add(0, simplePropositions.remove(token.getValue().toUpperCase()));
436 } else if (token.getType() == ExpressionToken.OPERATOR_AND) {
437 viewHelper.setTypeForCompoundOpCode(currentCompound, LogicalOperator.AND.getCode());
438 } else if (token.getType() == ExpressionToken.OPERATOR_OR) {
439 viewHelper.setTypeForCompoundOpCode(currentCompound, LogicalOperator.OR.getCode());
440 }
441 }
442
443 return currentCompound;
444 }
445
446 }