001 package org.kuali.rice.krms.util;
002
003 import org.kuali.rice.krms.api.repository.LogicalOperator;
004 import org.kuali.rice.krms.dto.PropositionEditor;
005 import org.kuali.rice.krms.dto.RuleEditor;
006
007 import java.util.ArrayList;
008 import java.util.List;
009 import java.util.Stack;
010
011 public class RuleLogicExpressionParser {
012
013 private String expression;
014
015 private List<ExpressionToken> tokenList;
016
017 private void checkExpressionSet() {
018 if (tokenList == null || expression == null) {
019 throw new java.lang.IllegalStateException("setExpression must be called first");
020 }
021 }
022
023 public void checkMissingRCs(List<PropositionEditor> missingProps, List<PropositionEditor> props) {
024 checkExpressionSet();
025
026 List<String> conditionValues = new ArrayList<String>();
027 for (ExpressionToken token : tokenList) {
028 if (token.type == ExpressionToken.Condition) {
029 conditionValues.add(token.value);
030 }
031 }
032
033 if (props != null && props.isEmpty()) {
034 for (PropositionEditor p : props) {
035 boolean foundId = false;
036 if (!conditionValues.isEmpty()) {
037 for (String conditionValue : conditionValues) {
038 if (conditionValue != null && conditionValue.equalsIgnoreCase(p.getCompoundOpCode())) {
039 foundId = true;
040 break;
041 }
042 }
043 }
044 if (!foundId) {
045 missingProps.add(p);
046 }
047 }
048 }
049 }
050
051 public boolean validateExpression(List<String> errorMessages, List<String> propsAlpha) {
052 checkExpressionSet();
053 return doValidateExpression(errorMessages, tokenList, propsAlpha);
054 }
055
056 private boolean doValidateExpression(List<String> errorMessages, final List<ExpressionToken> tokens, List<String> propsAlpha) {
057 boolean valid = true;
058 List<String> seenConditonValues = new ArrayList<String>();
059 // allow empty expression. ie. user wants the entire rule deleted.
060 if (tokens.size() == 0) {
061 return true;
062 }
063
064 if ((tokens.get(0).type == ExpressionToken.StartParenthesis
065 || tokens.get(0).type == ExpressionToken.Condition) == false) {
066 errorMessages.add("must start with ( or condition");
067 return false;
068 }
069 if ((tokenList.get(1).type == ExpressionToken.StartParenthesis) == false) {
070 errorMessages.add("parent compound proposition cannot be changed");
071 return false;
072 }
073 int lastIndex = tokens.size() - 1;
074 if ((tokens.get(lastIndex).type == ExpressionToken.EndParenthesis || tokens.get(lastIndex).type == ExpressionToken.Condition) == false) {
075 errorMessages.add("must end with ) or condition");
076 return false;
077 }
078 if (countToken(tokens, ExpressionToken.StartParenthesis) != countToken(tokens, ExpressionToken.EndParenthesis)) {
079 errorMessages.add("() not in pair");
080 return false;
081 }
082 if (!validateAndOr(errorMessages,tokens)){
083 return false;
084 }
085 // condition cannot duplicate
086 for (int i = 0; i < tokens.size(); i++) {
087 ExpressionToken token = tokens.get(i);
088 if (token.type == ExpressionToken.And) {
089 if (!checkAnd(errorMessages, tokens, i)) {
090 return false;
091 }
092 } else if (token.type == ExpressionToken.Or) {
093 if (!checkOr(errorMessages, tokens, i)) {
094 return false;
095 }
096 } else if (token.type == ExpressionToken.StartParenthesis) {
097 if (!checkStartParenthesis(errorMessages, tokens, i)) {
098 return false;
099 }
100 } else if (token.type == ExpressionToken.EndParenthesis) {
101 if (!checkEndParenthesis(errorMessages, tokens, i)) {
102 return false;
103 }
104 } else if (token.type == ExpressionToken.Condition) {
105 if (seenConditonValues.contains(token.value)) {
106 errorMessages.add("Condition " + token.value + " is duplicated.");
107 return false;
108 } else {
109 seenConditonValues.add(token.value);
110 }
111 if (!checkCondition(errorMessages, tokens, i, propsAlpha)) {
112 return false;
113 }
114 }
115 }
116 return valid;
117 }
118
119 private boolean validateAndOr(List<String> errorMessages, List<ExpressionToken> nodeList) {
120 Stack<ExpressionToken> operatorStack = new Stack<ExpressionToken>();
121
122 for (ExpressionToken token : nodeList) {
123 if (token.type == ExpressionToken.Condition) {
124 //do nothing
125 } else if (token.type == ExpressionToken.EndParenthesis) {
126 ExpressionToken operator = operatorStack.pop();
127
128 //Check if first type is a OR or a AND
129 if (operator.type != ExpressionToken.StartParenthesis){
130
131 //Check if all other types are the same as the first type.
132 while (operatorStack.peek().type != ExpressionToken.StartParenthesis) {
133 ExpressionToken next = operatorStack.pop();
134 if (next.type != operator.type){
135 errorMessages.add("Operators within parenthesis must be the same type.");
136 return false;
137 }
138 }
139
140 operatorStack.pop();// pop the (
141 }
142 } else {
143 operatorStack.push(token);
144 }
145 }
146
147 return true;
148 }
149
150 private int countToken(List<ExpressionToken> tokenList, int type) {
151 int count = 0;
152 for (ExpressionToken t : tokenList) {
153 if (t.type == type) {
154 count++;
155 }
156 }
157 return count;
158 }
159
160 private boolean checkAnd(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
161 ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
162 tokenList.get(currentIndex - 1);
163 ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
164 tokenList.get(currentIndex + 1);
165 boolean validToken = true;
166 if (prevToken != null && (prevToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.EndParenthesis) == false) {
167 errorMessages.add("only ) and condition could sit before and");
168 validToken = false;
169 }
170 if (nextToken != null && (nextToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.StartParenthesis) == false) {
171 errorMessages.add("only ( and condition could sit after and");
172 validToken = false;
173 }
174 return validToken;
175 }
176
177 private boolean checkOr(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
178 ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
179 tokenList.get(currentIndex - 1);
180 ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
181 tokenList.get(currentIndex + 1);
182 boolean validToken = true;
183 if (prevToken != null && (prevToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.EndParenthesis) == false) {
184 errorMessages.add("only ) and condition could sit before or");
185 validToken = false;
186 }
187 if (nextToken != null && (nextToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.StartParenthesis) == false) {
188 errorMessages.add("only ( and condition could sit after or");
189 validToken = false;
190 }
191 return validToken;
192 }
193
194 private boolean checkStartParenthesis(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
195 ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
196 tokenList.get(currentIndex - 1);
197 ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
198 tokenList.get(currentIndex + 1);
199 boolean validToken = true;
200 if (prevToken != null && (prevToken.type == ExpressionToken.Condition) == false) {
201 errorMessages.add("cannot alter compound proposition");
202 validToken = false;
203 }
204 if (nextToken != null && (nextToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.StartParenthesis) == false) {
205 errorMessages.add("only ( and condition could sit after (");
206 validToken = false;
207 }
208 if (prevToken != null && (prevToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.StartParenthesis) == false) {
209 errorMessages.add("cannot alter compound proposition");
210 validToken = false;
211 }
212 return validToken;
213 }
214
215 private boolean checkEndParenthesis(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
216 ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
217 tokenList.get(currentIndex - 1);
218 ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
219 tokenList.get(currentIndex + 1);
220 boolean validToken = true;
221 if (prevToken != null && (prevToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.EndParenthesis) == false) {
222 errorMessages.add("only condition and ) could sit before )");
223 validToken = false;
224 }
225 if (nextToken != null && (nextToken.type == ExpressionToken.Or || nextToken.type == ExpressionToken.And || nextToken.type == ExpressionToken.EndParenthesis) == false) {
226 errorMessages.add("only ), and, or could sit after )");
227 validToken = false;
228 }
229 return validToken;
230 }
231
232 private boolean checkCondition(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex,
233 List<String> propsAlpha) {
234 ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
235 tokenList.get(currentIndex - 1);
236 ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
237 tokenList.get(currentIndex + 1);
238 boolean validToken = true;
239 if (prevToken != null && (prevToken.type == ExpressionToken.And || prevToken.type == ExpressionToken.Or || prevToken.type == ExpressionToken.StartParenthesis) == false) {
240 errorMessages.add("only and, or could sit before condition");
241 validToken = false;
242 }
243 if (nextToken != null && (nextToken.type == ExpressionToken.Or || nextToken.type == ExpressionToken.And || nextToken.type == ExpressionToken.EndParenthesis || nextToken.type == ExpressionToken.StartParenthesis) == false) {
244 errorMessages.add("only (, ), and, or could sit after condition");
245 validToken = false;
246 }
247 ExpressionToken conditionToken = tokenList.get(currentIndex);
248 String conditionLetter = conditionToken.value;
249 boolean validConditonLetter = false;
250 if (propsAlpha != null) {
251 for (String propAlpha : propsAlpha) {
252 if (propAlpha != null &&
253 propAlpha.equalsIgnoreCase(conditionLetter)) {
254 validConditonLetter = true;
255 }
256 }
257 }
258 if (!validConditonLetter) {
259 errorMessages.add(conditionLetter + " is not a valid conditon");
260 validToken = false;
261 }
262 return validToken;
263 }
264
265 private List<ExpressionToken> getTokenList(List<String> tokenValueList) {
266 List<ExpressionToken> tokenList = new ArrayList<ExpressionToken>();
267 for (String value : tokenValueList) {
268 if (value.isEmpty()) {
269 continue;
270 }
271 if ("(".equals(value)) {
272 ExpressionToken t = new ExpressionToken();
273 t.type = ExpressionToken.StartParenthesis;
274 tokenList.add(t);
275 } else if (")".equals(value)) {
276 ExpressionToken t = new ExpressionToken();
277 t.type = ExpressionToken.EndParenthesis;
278 tokenList.add(t);
279
280 } else if ("and".equals(value)) {
281 ExpressionToken t = new ExpressionToken();
282 t.type = ExpressionToken.And;
283 tokenList.add(t);
284
285 } else if ("or".equals(value)) {
286 ExpressionToken t = new ExpressionToken();
287 t.type = ExpressionToken.Or;
288 tokenList.add(t);
289
290 } else {
291 ExpressionToken t = new ExpressionToken();
292 t.type = ExpressionToken.Condition;
293 t.value = value;
294 tokenList.add(t);
295
296 }
297 }
298 return tokenList;
299 }
300
301 private List<String> getTokenValue(String expression) {
302 expression = expression.toLowerCase();
303 List<String> tokenValueList = new ArrayList<String>();
304 StringBuffer tokenValue = new StringBuffer();
305 for (int i = 0; i < expression.length(); i++) {
306
307 char ch = expression.charAt(i);
308 if (Character.isSpaceChar(ch)) {
309 tokenValueList.add(tokenValue.toString());
310 tokenValue = new StringBuffer();
311 } else if (ch == '(' || ch == ')') {
312 tokenValueList.add(tokenValue.toString());
313 tokenValue = new StringBuffer();
314 tokenValueList.add(String.valueOf(ch));
315 } else {
316 tokenValue.append(ch);
317 }
318 }
319 tokenValueList.add(tokenValue.toString());
320 return tokenValueList;
321 }
322
323 public void setExpression(String expression) {
324 this.expression = expression;
325 List<String> tokenValueList = getTokenValue(expression);
326 this.tokenList = getTokenList(tokenValueList);
327 }
328
329 public String getExpression() {
330 return expression;
331 }
332
333 public List<ExpressionToken> getTokenList() {
334 return tokenList;
335 }
336
337 public PropositionEditor parseExpressionIntoRule(RuleEditor ruleEditor) {
338
339 PropositionEditor oldEditor = (PropositionEditor) ruleEditor.getProposition();
340 List<PropositionEditor> rcs = this.getPropositions(new ArrayList<PropositionEditor>(), oldEditor);
341
342 List<ExpressionToken> rpnList = getRPN(tokenList);
343 return ruleFromRPN(rpnList, rcs);
344 }
345
346 private List<PropositionEditor> getPropositions(List<PropositionEditor> propositions, PropositionEditor propositionEditor) {
347 propositions.add(propositionEditor);
348 if (propositionEditor.getCompoundComponents() != null) {
349 for (PropositionEditor child : propositionEditor.getCompoundEditors()) {
350 this.getPropositions(propositions, child);
351 }
352 }
353 return propositions;
354 }
355
356 /**
357 * If higher push to stack, else pop till less than or equal, add to list push to stack if ( push to stack if ) pop to
358 * list till (.
359 * <p/>
360 * http://en.wikipedia.org/wiki/Reverse_Polish_notation
361 */
362 private List<ExpressionToken> getRPN(List<ExpressionToken> nodeList) {
363 List<ExpressionToken> rpnList = new ArrayList<ExpressionToken>();
364 Stack<ExpressionToken> operatorStack = new Stack<ExpressionToken>();
365
366 for (ExpressionToken token : nodeList) {
367 if (token.type == ExpressionToken.Condition) {
368 rpnList.add(token);
369 } else if (token.type == ExpressionToken.EndParenthesis) {
370 while (operatorStack.peek().type != ExpressionToken.StartParenthesis) {
371 rpnList.add(operatorStack.pop());
372 }
373 operatorStack.pop();// pop the (
374 } else {
375 operatorStack.push(token);
376 }
377 }
378
379 //Add remaining operators to rpnlist
380 while (operatorStack.isEmpty() == false){
381 rpnList.add(operatorStack.pop());
382 }
383
384 return rpnList;
385 }
386
387 /**
388 * Build the binary tree from list of tokens
389 */
390 private PropositionEditor ruleFromRPN(List<ExpressionToken> rpnList, List<PropositionEditor> rcs) {
391 //if rule is empty
392 if (rpnList.size() == 0) {
393 return new PropositionEditor();
394 }
395
396 Stack<PropositionEditor> conditionStack = new Stack<PropositionEditor>();
397 Stack<PropositionEditor> simpleProps = new Stack<PropositionEditor>();
398 for (ExpressionToken token : rpnList) {
399 if (token.type == ExpressionToken.Condition) {
400 PropositionEditor rc = lookupPropositionEditor(rcs, token.value);
401 if (rc.getPropositionTypeCode().equals("C")){
402 rc.setCompoundEditors(new ArrayList<PropositionEditor>());
403 }
404 conditionStack.push(rc);
405 } else {
406 if(simpleProps.empty()){
407 simpleProps.push(conditionStack.pop());
408 }
409 simpleProps.push(conditionStack.pop());
410 if(conditionStack.peek().getPropositionTypeCode().equals("C")) {
411 PropositionEditor compound = conditionStack.pop();
412 if (token.type == ExpressionToken.And){
413 PropositionTreeUtil.setTypeForCompoundOpCode(compound, LogicalOperator.AND.getCode());
414 } else if (token.type == ExpressionToken.Or) {
415 PropositionTreeUtil.setTypeForCompoundOpCode(compound, LogicalOperator.OR.getCode());
416 }
417 while (!simpleProps.empty()) {
418 compound.getCompoundEditors().add(simpleProps.pop());
419 }
420 conditionStack.push(compound);
421 }
422 }
423 }
424
425 return conditionStack.pop();
426 }
427
428 private PropositionEditor lookupPropositionEditor(List<PropositionEditor> rcs, String key) {
429 if (rcs != null) {
430 for (PropositionEditor rc : rcs) {
431 if (rc.getKey().equalsIgnoreCase(key)) {
432 return rc;
433 }
434 }
435 }
436 return null;
437 }
438 }