Source code

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, List<String> keyList) {
051        checkExpressionSet();
052        return doValidateExpression(errorMessages, tokenList, keyList);
053    }
054
055    private boolean doValidateExpression(List<String> errorMessages, final List<ExpressionToken> tokens, List<String> keyList) {
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, 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                //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        }
146        if (!operatorStack.isEmpty()) {
147            ExpressionToken operator = operatorStack.pop();
148            //Check if all other types are the same as the first type.
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     * Method to rebuild the tree based on the set token list that was built from given expression.
313     *
314     * @param ruleEditor
315     * @param viewHelper
316     * @return PropositionEditor
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        //Return null if stack is empty, all propositions deleted from logic expression.
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     * This is a recursive method that loop thru the proposition tree to add all simple proposition in a map so that
365     * they can easily be retrieved by their keys when we rebuild the proposition tree.
366     * <p/>
367     * It also creates a queue with all the existing compound propositions so that the root proposition could be
368     * retrieved first.
369     *
370     * @param simplePropositions
371     * @param compoundPropositions
372     * @param propositionEditor
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     * Build the proposition tree from the token stack in reverse order. If the token is a end parenthesis,
389     * recursively call this method again to resolve the inner group (compound proposition). When the next token
390     * is a start parenthesis, return the group.     *
391     *
392     * @param tokenStack
393     * @param simplePropositions
394     * @param compoundPropositions
395     * @param rule
396     * @return
397     */
398    public PropositionEditor ruleFromStack(Stack<ExpressionToken> tokenStack, Map<String, PropositionEditor> simplePropositions,
399                                           Queue<PropositionEditor> compoundPropositions, RuleEditor rule, RuleViewHelperService viewHelper) {
400
401        //Check for single statement.
402        if(tokenStack.size()==1){
403            ExpressionToken token = tokenStack.pop();
404            return simplePropositions.remove(token.getValue().toUpperCase());
405        }
406
407        //Get the first compound from the queue, if nothing left create new one.
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        //Loop thru tokens and recreate the proposition tree.
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}