View Javadoc

1   /**
2    * Copyright 2010 The Kuali Foundation Licensed under the
3    * Educational Community License, Version 2.0 (the "License"); you may
4    * not use this file except in compliance with the License. You may
5    * obtain a copy of the License at
6    *
7    * http://www.osedu.org/licenses/ECL-2.0
8    *
9    * Unless required by applicable law or agreed to in writing,
10   * software distributed under the License is distributed on an "AS IS"
11   * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
12   * or implied. See the License for the specific language governing
13   * permissions and limitations under the License.
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          // allow empty expression. ie. user wants the entire rule deleted.
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          // condition cannot duplicate
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; //return false;
117                 } else {
118                     seenConditonValues.add(token.value);
119                 }
120                 if (!checkCondition(errorMessages, tokens, i, validRCs)) {
121                     continue; //return false;
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     /** Build the binary tree from list of tokens*/
290     private StatementVO statementVOFromRPN(List<Node<Token>> rpnList, List<ReqComponentVO> rcs, String statementType) {
291         StatementVO statementVO;        
292 
293         //if rule is empty
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                 // if both left and right nodes are rcs add them into the list of rcs in subS
332                 // otherwise wrap the one that is a RC and add the left and right tokens as statementVO into subS
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      * 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
377      * list till (.
378      * 
379      * http://en.wikipedia.org/wiki/Reverse_Polish_notation
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();// pop the (
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 }