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