001/** 002 * Copyright 2005-2013 The Kuali Foundation 003 * 004 * Licensed under the Educational Community License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.opensource.org/licenses/ecl2.php 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016package org.kuali.rice.krms.util; 017 018import org.kuali.rice.krms.api.repository.LogicalOperator; 019import org.kuali.rice.krms.api.repository.proposition.PropositionType; 020import org.kuali.rice.krms.dto.PropositionEditor; 021import org.kuali.rice.krms.dto.RuleEditor; 022import org.kuali.rice.krms.service.RuleViewHelperService; 023 024import java.util.ArrayList; 025import java.util.LinkedHashMap; 026import java.util.LinkedList; 027import java.util.List; 028import java.util.Map; 029import java.util.Queue; 030import java.util.Stack; 031 032/** 033 * This is a helper class that validates logical expressions and rebuild a tree based on a valid expression. 034 * 035 * @author Kuali Student Team 036 */ 037public class RuleLogicExpressionParser { 038 039 private String expression; 040 private boolean isOtiose; 041 042 private List<ExpressionToken> tokenList; 043 044 private void checkExpressionSet() { 045 if (tokenList == null || expression == null) { 046 throw new java.lang.IllegalStateException("setExpression must be called first"); 047 } 048 } 049 050 public boolean validateExpression(List<String> errorMessages) { 051 checkExpressionSet(); 052 return doValidateExpression(errorMessages, tokenList); 053 } 054 055 private boolean doValidateExpression(List<String> errorMessages, final List<ExpressionToken> tokens) { 056 boolean valid = true; 057 List<String> seenConditonValues = new ArrayList<String>(); 058 059 // allow empty expression. ie. user wants the entire rule deleted. 060 if (tokens.size() > 0) { 061 //Code Changed for JIRA-9075 - SONAR Critical issues - Use get(0) with caution - 5 062 int firstToken = 0; 063 int firstTokenType = tokens.get(firstToken).getType(); 064 if ((firstTokenType != ExpressionToken.PARENTHESIS_START) 065 && (firstTokenType != ExpressionToken.CONDITION)) { 066 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_LOGIC_EXPRESSION_START); 067 return false; 068 } 069 } else { 070 return true; 071 } 072 if (countToken(tokens, ExpressionToken.PARENTHESIS_START) != countToken(tokens, ExpressionToken.PARENTHESIS_END)) { 073 errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PARENTHESIS_NOT_PAIR); 074 return false; 075 } 076 if (!validateAndOr(errorMessages, tokens)) { 077 return false; 078 } 079 // condition cannot duplicate 080 for (int i = 0; i < tokens.size(); i++) { 081 ExpressionToken token = tokens.get(i); 082 083 ExpressionToken prevToken = null; 084 ExpressionToken nextToken = null; 085 if (tokens != null) { 086 prevToken = i - 1 < 0 ? null : tokens.get(i - 1); 087 nextToken = i + 1 >= tokens.size() ? null : tokens.get(i + 1); 088 } 089 090 if (token.getType() == ExpressionToken.OPERATOR_AND) { 091 if (!checkAnd(errorMessages, prevToken, nextToken)) { 092 return false; 093 } 094 } else if (token.getType() == ExpressionToken.OPERATOR_OR) { 095 if (!checkOr(errorMessages, prevToken, nextToken)) { 096 return false; 097 } 098 } else if (token.getType() == ExpressionToken.PARENTHESIS_START) { 099 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 //Check if first type is a OR or a AND 129 if (operator.getType() != ExpressionToken.PARENTHESIS_START) { 130 131 //Check if all other types are the same as the first type. 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();// pop the ( 141 } 142 } else if (token.getType() != ExpressionToken.CONDITION) { 143 operatorStack.push(token); 144 } 145 } if (!operatorStack.isEmpty()) { 146 ExpressionToken operator = operatorStack.pop(); 147 //Check if all other types are the same as the first type. 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 * Method to rebuild the tree based on the set token list that was built from given expression. 304 * 305 * @param ruleEditor 306 * @param viewHelper 307 * @return PropositionEditor 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 * This is a recursive method that loop thru the proposition tree to add all simple proposition in a map so that 351 * they can easily be retrieved by their keys when we rebuild the proposition tree. 352 * <p/> 353 * It also creates a queue with all the existing compound propositions so that the root proposition could be 354 * retrieved first. 355 * 356 * @param simplePropositions 357 * @param compoundPropositions 358 * @param propositionEditor 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 * Build the proposition tree from the token stack in reverse order. If the token is a end parenthesis, 375 * recursively call this method again to resolve the inner group (compound proposition). When the next token 376 * is a start parenthesis, return the group. * 377 * 378 * @param tokenStack 379 * @param simplePropositions 380 * @param compoundPropositions 381 * @param rule 382 * @return 383 */ 384 public PropositionEditor ruleFromStack(Stack<ExpressionToken> tokenStack, Map<String, PropositionEditor> simplePropositions, 385 Queue<PropositionEditor> compoundPropositions, RuleEditor rule, RuleViewHelperService viewHelper) { 386 387 //Get the first compound from the queue, if nothing left create new one. 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 //Loop thru tokens and recreate the proposition tree. 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}