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) {
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}