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> propsAlpha) {
051        checkExpressionSet();
052        return doValidateExpression(errorMessages, tokenList, propsAlpha);
053    }
054
055    private boolean doValidateExpression(List<String> errorMessages, final List<ExpressionToken> tokens, List<String> propsAlpha) {
056        boolean valid = true;
057        List<String> seenConditonValues = new ArrayList<String>();
058        // allow empty expression. ie. user wants the entire rule deleted.
059        if (tokens.size() == 0) {
060            return true;
061        }
062
063        int firstTokenType = tokens.get(0).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        if (countToken(tokens, ExpressionToken.PARENTHESIS_START) != countToken(tokens, ExpressionToken.PARENTHESIS_END)) {
070            errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PARENTHESIS_NOT_PAIR);
071            return false;
072        }
073        if (!validateAndOr(errorMessages, tokens)) {
074            return false;
075        }
076        // condition cannot duplicate
077        for (int i = 0; i < tokens.size(); i++) {
078            ExpressionToken token = tokens.get(i);
079
080            ExpressionToken prevToken = null;
081            ExpressionToken nextToken = null;
082            if(tokens != null){
083                prevToken = i - 1 < 0 ? null : tokens.get(i - 1);
084                nextToken = i + 1 >= tokens.size() ? null : tokens.get(i + 1);
085            }
086
087            if (token.getType() == ExpressionToken.OPERATOR_AND) {
088                if (!checkAnd(errorMessages, prevToken, nextToken)) {
089                    return false;
090                }
091            } else if (token.getType() == ExpressionToken.OPERATOR_OR) {
092                if (!checkOr(errorMessages, prevToken, nextToken)) {
093                    return false;
094                }
095            } else if (token.getType() == ExpressionToken.PARENTHESIS_START) {
096                if (!checkStartParenthesis(errorMessages, prevToken, nextToken)) {
097                    return false;
098                }
099            } else if (token.getType() == ExpressionToken.PARENTHESIS_END) {
100                if (!checkEndParenthesis(errorMessages, prevToken, nextToken)) {
101                    return false;
102                }
103            } else if (token.getType() == ExpressionToken.CONDITION) {
104                if (seenConditonValues.contains(token.getValue())) {
105                    errorMessages.add("Condition " + token.getValue() + " is duplicated.");
106                    return false;
107                } else {
108                    seenConditonValues.add(token.getValue());
109                }
110                if (!checkCondition(errorMessages, prevToken, nextToken)) {
111                    return false;
112                }
113            }
114        }
115        return valid;
116    }
117
118    private boolean validateAndOr(List<String> errorMessages, List<ExpressionToken> nodeList) {
119        Stack<ExpressionToken> operatorStack = new Stack<ExpressionToken>();
120
121        for (ExpressionToken token : nodeList) {
122            if (token.getType() == ExpressionToken.PARENTHESIS_END) {
123                ExpressionToken operator = operatorStack.pop();
124
125                //Check if first type is a OR or a AND
126                if (operator.getType() != ExpressionToken.PARENTHESIS_START) {
127
128                    //Check if all other types are the same as the first type.
129                    while (operatorStack.peek().getType() != ExpressionToken.PARENTHESIS_START) {
130                        ExpressionToken next = operatorStack.pop();
131                        if (next.getType() != operator.getType()) {
132                            errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_OPERATOR_TYPE);
133                            return false;
134                        }
135                    }
136
137                    operatorStack.pop();// pop the (
138                }
139            } else if (token.getType() != ExpressionToken.CONDITION) {
140                operatorStack.push(token);
141            }
142        }
143
144        return true;
145    }
146
147    private int countToken(List<ExpressionToken> tokenList, int type) {
148        int count = 0;
149        for (ExpressionToken t : tokenList) {
150            if (t.getType() == type) {
151                count++;
152            }
153        }
154        return count;
155    }
156
157    private boolean checkAnd(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken) {
158        boolean validToken = true;
159        if ((prevToken != null) && (prevToken.getType() != ExpressionToken.CONDITION) && (prevToken.getType() != ExpressionToken.PARENTHESIS_END)) {
160                errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PRECEDE_OPERATOR);
161                validToken = false;
162        }
163        if ((nextToken != null) && (nextToken.getType() != ExpressionToken.CONDITION) && (nextToken.getType() != ExpressionToken.PARENTHESIS_START)) {
164            errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_OPERATOR);
165            validToken = false;
166        }
167        return validToken;
168    }
169
170    private boolean checkOr(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_OR);
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_OR);
178            validToken = false;
179        }
180        return validToken;
181    }
182
183    private boolean checkStartParenthesis(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken) {
184        boolean validToken = true;
185        if ((nextToken != null) && (nextToken.getType() != ExpressionToken.CONDITION) && (nextToken.getType() != ExpressionToken.PARENTHESIS_START)) {
186                errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_START_PARENTHESIS);
187                validToken = false;
188        }
189        return validToken;
190    }
191
192    private boolean checkEndParenthesis(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken) {
193        boolean validToken = true;
194        if ((prevToken != null) && (prevToken.getType() != ExpressionToken.CONDITION) && (prevToken.getType() == ExpressionToken.PARENTHESIS_END)) {
195            errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PRECEDE_END_PARENTHESIS);
196            validToken = false;
197        }
198        if ((nextToken != null) && (nextToken.getType() != ExpressionToken.OPERATOR_OR) && (nextToken.getType() != ExpressionToken.OPERATOR_AND) && (nextToken.getType() != ExpressionToken.PARENTHESIS_END)) {
199            errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_END_PARENTHESIS);
200            validToken = false;
201        }
202        return validToken;
203    }
204
205    private boolean checkCondition(List<String> errorMessages, ExpressionToken prevToken, ExpressionToken nextToken) {
206        boolean validToken = true;
207        if ((prevToken != null) && (prevToken.getType() != ExpressionToken.OPERATOR_AND) && (prevToken.getType() != ExpressionToken.OPERATOR_OR) && (prevToken.getType() != ExpressionToken.PARENTHESIS_START)) {
208            errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_PRECEDE_CONDITION);
209            validToken = false;
210        }
211        if ((nextToken != null) && (nextToken.getType() != ExpressionToken.OPERATOR_OR) && (nextToken.getType() != ExpressionToken.OPERATOR_AND) && (nextToken.getType() != ExpressionToken.PARENTHESIS_END) && (nextToken.getType() != ExpressionToken.PARENTHESIS_START)) {
212            errorMessages.add(KRMSConstants.KRMS_MSG_ERROR_FOLLOW_CONDITION);
213            validToken = false;
214        }
215        return validToken;
216    }
217
218    private List<ExpressionToken> getTokenList(List<String> tokenValueList) {
219        List<ExpressionToken> returnList = new ArrayList<ExpressionToken>();
220        for (String value : tokenValueList) {
221            if (value.isEmpty()) {
222                continue;
223            }
224            if ("(".equals(value)) {
225                ExpressionToken t = new ExpressionToken();
226                t.setType(ExpressionToken.PARENTHESIS_START);
227                returnList.add(t);
228            } else if (")".equals(value)) {
229                ExpressionToken t = new ExpressionToken();
230                t.setType(ExpressionToken.PARENTHESIS_END);
231                returnList.add(t);
232
233            } else if ("and".equals(value)) {
234                ExpressionToken t = new ExpressionToken();
235                t.setType(ExpressionToken.OPERATOR_AND);
236                returnList.add(t);
237
238            } else if ("or".equals(value)) {
239                ExpressionToken t = new ExpressionToken();
240                t.setType(ExpressionToken.OPERATOR_OR);
241                returnList.add(t);
242
243            } else {
244                ExpressionToken t = new ExpressionToken();
245                t.setType(ExpressionToken.CONDITION);
246                t.setValue(value);
247                returnList.add(t);
248
249            }
250        }
251        return returnList;
252    }
253
254    private List<String> getTokenValue(String expression) {
255        expression = expression.toLowerCase();
256        List<String> tokenValueList = new ArrayList<String>();
257        StringBuffer tokenValue = new StringBuffer();
258        for (int i = 0; i < expression.length(); i++) {
259
260            char ch = expression.charAt(i);
261            if (Character.isSpaceChar(ch)) {
262                tokenValueList.add(tokenValue.toString());
263                tokenValue = new StringBuffer();
264            } else if (ch == '(' || ch == ')') {
265                tokenValueList.add(tokenValue.toString());
266                tokenValue = new StringBuffer();
267                tokenValueList.add(String.valueOf(ch));
268            } else {
269                tokenValue.append(ch);
270            }
271        }
272        tokenValueList.add(tokenValue.toString());
273        return tokenValueList;
274    }
275
276    public void setExpression(String expression) {
277        this.expression = expression;
278        List<String> tokenValueList = getTokenValue(expression);
279        this.tokenList = getTokenList(tokenValueList);
280    }
281
282    public String getExpression() {
283        return expression;
284    }
285
286    public List<ExpressionToken> getTokenList() {
287        return tokenList;
288    }
289
290    /**
291     * Method to rebuild the tree based on the set token list that was built from given expression.
292     *
293     * @param ruleEditor
294     * @param viewHelper
295     * @return PropositionEditor
296     */
297    public PropositionEditor parseExpressionIntoRule(RuleEditor ruleEditor, RuleViewHelperService viewHelper) {
298
299        Stack<ExpressionToken> tokenStack = new Stack<ExpressionToken>();
300        int index = 0;
301        isOtiose = false;
302        for (ExpressionToken token : tokenList) {
303            if(isOtioseCompound(token, tokenList, index)) {
304                index++;
305                continue;
306            }
307
308            tokenStack.push(token);
309            index++;
310        }
311
312        Map<String, PropositionEditor> simplePropositions = new LinkedHashMap<String, PropositionEditor>();
313        Queue<PropositionEditor> compoundPropositions = new LinkedList<PropositionEditor>();
314        this.setupPropositions(simplePropositions, compoundPropositions, ruleEditor.getPropositionEditor());
315
316        return ruleFromStack(tokenStack, simplePropositions, compoundPropositions, ruleEditor, viewHelper);
317    }
318
319    private boolean isOtioseCompound(ExpressionToken token, List<ExpressionToken> tokenList, int index) {
320
321        if(token.getType() == ExpressionToken.PARENTHESIS_END && isOtiose) {
322            isOtiose = false;
323            return true;
324        }
325
326        if(token.getType() == ExpressionToken.PARENTHESIS_START) {
327            if(tokenList.size() > index + 2) {
328                if(tokenList.get(index+1).getType() == ExpressionToken.CONDITION && tokenList.get(index+2).getType() == ExpressionToken.PARENTHESIS_END) {
329                    isOtiose = true;
330                    return true;
331                }
332            }
333        }
334        return false;
335    }
336
337    /**
338     * This is a recursive method that loop thru the proposition tree to add all simple proposition in a map so that
339     * they can easily be retrieved by their keys when we rebuild the proposition tree.
340     *
341     * It also creates a queue with all the existing compound propositions so that the root proposition could be
342     * retrieved first.
343     *
344     * @param simplePropositions
345     * @param compoundPropositions
346     * @param propositionEditor
347     */
348    private void setupPropositions(Map<String, PropositionEditor> simplePropositions, Queue<PropositionEditor> compoundPropositions, PropositionEditor propositionEditor) {
349        if (propositionEditor.getPropositionTypeCode().equals(PropositionType.SIMPLE.getCode())) {
350            simplePropositions.put(propositionEditor.getKey(), propositionEditor);
351        } else {
352            compoundPropositions.add(propositionEditor);
353            for (PropositionEditor child : propositionEditor.getCompoundEditors()) {
354                this.setupPropositions(simplePropositions, compoundPropositions, child);
355            }
356            propositionEditor.setCompoundEditors(new ArrayList<PropositionEditor>());
357        }
358
359    }
360
361    /**
362     * Build the proposition tree from the token stack in reverse order. If the token is a end parenthesis,
363     * recursively call this method again to resolve the inner group (compound proposition). When the next token
364     * is a start parenthesis, return the group.     *
365     *
366     * @param tokenStack
367     * @param simplePropositions
368     * @param compoundPropositions
369     * @param rule
370     * @return
371     */
372    public PropositionEditor ruleFromStack(Stack<ExpressionToken> tokenStack, Map<String, PropositionEditor> simplePropositions,
373                                         Queue<PropositionEditor> compoundPropositions, RuleEditor rule, RuleViewHelperService viewHelper) {
374
375        //Get the first compound from the queue, if nothing left create new one.
376        PropositionEditor currentCompound = null;
377        if(compoundPropositions.peek()==null){
378            currentCompound = new PropositionEditor();
379            currentCompound.setPropositionTypeCode(PropositionType.COMPOUND.getCode());
380            currentCompound.setRuleId(rule.getId());
381            currentCompound.setKey((String) rule.getCompoundKeys().next());
382            currentCompound.setCompoundEditors(new ArrayList<PropositionEditor>());
383        } else {
384            currentCompound = compoundPropositions.remove();
385        }
386
387        //Loop thru tokens and recreate the proposition tree.
388        while (!tokenStack.empty()) {
389            ExpressionToken token = tokenStack.pop();
390            if(token.getType() == ExpressionToken.PARENTHESIS_END){
391                PropositionEditor compound = ruleFromStack(tokenStack, simplePropositions, compoundPropositions, rule, viewHelper);
392                currentCompound.getCompoundEditors().add(0,compound);
393            } else if (token.getType() == ExpressionToken.PARENTHESIS_START) {
394                return currentCompound;
395            } else if (token.getType() == ExpressionToken.CONDITION){
396                currentCompound.getCompoundEditors().add(0,simplePropositions.remove(token.getValue().toUpperCase()));
397            } else if (token.getType() == ExpressionToken.OPERATOR_AND){
398                viewHelper.setTypeForCompoundOpCode(currentCompound, LogicalOperator.AND.getCode());
399            } else if (token.getType() == ExpressionToken.OPERATOR_OR){
400                viewHelper.setTypeForCompoundOpCode(currentCompound, LogicalOperator.OR.getCode());
401            }
402        }
403
404        return currentCompound;
405    }
406
407}