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