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