001package org.kuali.rice.krms.util;
002
003import org.kuali.rice.krms.api.repository.LogicalOperator;
004import org.kuali.rice.krms.dto.PropositionEditor;
005import org.kuali.rice.krms.dto.RuleEditor;
006
007import java.util.ArrayList;
008import java.util.List;
009import java.util.Stack;
010
011public class RuleLogicExpressionParser {
012
013    private String expression;
014
015    private List<ExpressionToken> tokenList;
016
017    private void checkExpressionSet() {
018        if (tokenList == null || expression == null) {
019            throw new java.lang.IllegalStateException("setExpression must be called first");
020        }
021    }
022
023    public void checkMissingRCs(List<PropositionEditor> missingProps, List<PropositionEditor> props) {
024        checkExpressionSet();
025
026        List<String> conditionValues = new ArrayList<String>();
027        for (ExpressionToken token : tokenList) {
028            if (token.type == ExpressionToken.Condition) {
029                conditionValues.add(token.value);
030            }
031        }
032
033        if (props != null && props.isEmpty()) {
034            for (PropositionEditor p : props) {
035                boolean foundId = false;
036                if (!conditionValues.isEmpty()) {
037                    for (String conditionValue : conditionValues) {
038                        if (conditionValue != null && conditionValue.equalsIgnoreCase(p.getCompoundOpCode())) {
039                            foundId = true;
040                            break;
041                        }
042                    }
043                }
044                if (!foundId) {
045                    missingProps.add(p);
046                }
047            }
048        }
049    }
050
051    public boolean validateExpression(List<String> errorMessages, List<String> propsAlpha) {
052        checkExpressionSet();
053        return doValidateExpression(errorMessages, tokenList, propsAlpha);
054    }
055
056    private boolean doValidateExpression(List<String> errorMessages, final List<ExpressionToken> tokens, List<String> propsAlpha) {
057        boolean valid = true;
058        List<String> seenConditonValues = new ArrayList<String>();
059        // allow empty expression. ie. user wants the entire rule deleted.
060        if (tokens.size() == 0) {
061            return true;
062        }
063
064        if ((tokens.get(0).type == ExpressionToken.StartParenthesis
065                || tokens.get(0).type == ExpressionToken.Condition) == false) {
066            errorMessages.add("must start with ( or condition");
067            return false;
068        }
069        if ((tokenList.get(1).type == ExpressionToken.StartParenthesis) == false) {
070            errorMessages.add("parent compound proposition cannot be changed");
071            return false;
072        }
073        int lastIndex = tokens.size() - 1;
074        if ((tokens.get(lastIndex).type == ExpressionToken.EndParenthesis || tokens.get(lastIndex).type == ExpressionToken.Condition) == false) {
075            errorMessages.add("must end with ) or condition");
076            return false;
077        }
078        if (countToken(tokens, ExpressionToken.StartParenthesis) != countToken(tokens, ExpressionToken.EndParenthesis)) {
079            errorMessages.add("() not in pair");
080            return false;
081        }
082        if (!validateAndOr(errorMessages,tokens)){
083            return false;
084        }
085        // condition cannot duplicate
086        for (int i = 0; i < tokens.size(); i++) {
087            ExpressionToken token = tokens.get(i);
088            if (token.type == ExpressionToken.And) {
089                if (!checkAnd(errorMessages, tokens, i)) {
090                    return false;
091                }
092            } else if (token.type == ExpressionToken.Or) {
093                if (!checkOr(errorMessages, tokens, i)) {
094                    return false;
095                }
096            } else if (token.type == ExpressionToken.StartParenthesis) {
097                if (!checkStartParenthesis(errorMessages, tokens, i)) {
098                    return false;
099                }
100            } else if (token.type == ExpressionToken.EndParenthesis) {
101                if (!checkEndParenthesis(errorMessages, tokens, i)) {
102                    return false;
103                }
104            } else if (token.type == ExpressionToken.Condition) {
105                if (seenConditonValues.contains(token.value)) {
106                    errorMessages.add("Condition " + token.value + " is duplicated.");
107                    return false;
108                } else {
109                    seenConditonValues.add(token.value);
110                }
111                if (!checkCondition(errorMessages, tokens, i, propsAlpha)) {
112                    return false;
113                }
114            }
115        }
116        return valid;
117    }
118
119    private boolean validateAndOr(List<String> errorMessages, List<ExpressionToken> nodeList) {
120        Stack<ExpressionToken> operatorStack = new Stack<ExpressionToken>();
121
122        for (ExpressionToken token : nodeList) {
123            if (token.type == ExpressionToken.Condition) {
124                //do nothing
125            } else if (token.type == ExpressionToken.EndParenthesis) {
126                ExpressionToken operator = operatorStack.pop();
127
128                //Check if first type is a OR or a AND
129                if (operator.type != ExpressionToken.StartParenthesis){
130
131                    //Check if all other types are the same as the first type.
132                    while (operatorStack.peek().type != ExpressionToken.StartParenthesis) {
133                        ExpressionToken next = operatorStack.pop();
134                        if (next.type != operator.type){
135                            errorMessages.add("Operators within parenthesis must be the same type.");
136                            return false;
137                        }
138                    }
139
140                    operatorStack.pop();// pop the (
141                }
142            } else {
143                operatorStack.push(token);
144            }
145        }
146
147        return true;
148    }
149
150    private int countToken(List<ExpressionToken> tokenList, int type) {
151        int count = 0;
152        for (ExpressionToken t : tokenList) {
153            if (t.type == type) {
154                count++;
155            }
156        }
157        return count;
158    }
159
160    private boolean checkAnd(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
161        ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
162                tokenList.get(currentIndex - 1);
163        ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
164                tokenList.get(currentIndex + 1);
165        boolean validToken = true;
166        if (prevToken != null && (prevToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.EndParenthesis) == false) {
167            errorMessages.add("only ) and condition could sit before and");
168            validToken = false;
169        }
170        if (nextToken != null && (nextToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.StartParenthesis) == false) {
171            errorMessages.add("only ( and condition could sit after and");
172            validToken = false;
173        }
174        return validToken;
175    }
176
177    private boolean checkOr(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
178        ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
179                tokenList.get(currentIndex - 1);
180        ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
181                tokenList.get(currentIndex + 1);
182        boolean validToken = true;
183        if (prevToken != null && (prevToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.EndParenthesis) == false) {
184            errorMessages.add("only ) and condition could sit before or");
185            validToken = false;
186        }
187        if (nextToken != null && (nextToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.StartParenthesis) == false) {
188            errorMessages.add("only ( and condition could sit after or");
189            validToken = false;
190        }
191        return validToken;
192    }
193
194    private boolean checkStartParenthesis(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
195        ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
196                tokenList.get(currentIndex - 1);
197        ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
198                tokenList.get(currentIndex + 1);
199        boolean validToken = true;
200        if (prevToken != null && (prevToken.type == ExpressionToken.Condition) == false) {
201            errorMessages.add("cannot alter compound proposition");
202            validToken = false;
203        }
204        if (nextToken != null && (nextToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.StartParenthesis) == false) {
205            errorMessages.add("only ( and condition could sit after (");
206            validToken = false;
207        }
208        if (prevToken != null && (prevToken.type == ExpressionToken.Condition || nextToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.StartParenthesis) == false) {
209            errorMessages.add("cannot alter compound proposition");
210            validToken = false;
211        }
212        return validToken;
213    }
214
215    private boolean checkEndParenthesis(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex) {
216        ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
217                tokenList.get(currentIndex - 1);
218        ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
219                tokenList.get(currentIndex + 1);
220        boolean validToken = true;
221        if (prevToken != null && (prevToken.type == ExpressionToken.Condition || prevToken.type == ExpressionToken.EndParenthesis) == false) {
222            errorMessages.add("only condition and ) could sit before )");
223            validToken = false;
224        }
225        if (nextToken != null && (nextToken.type == ExpressionToken.Or || nextToken.type == ExpressionToken.And || nextToken.type == ExpressionToken.EndParenthesis) == false) {
226            errorMessages.add("only ), and, or could sit after )");
227            validToken = false;
228        }
229        return validToken;
230    }
231
232    private boolean checkCondition(List<String> errorMessages, List<ExpressionToken> tokenList, int currentIndex,
233                                   List<String> propsAlpha) {
234        ExpressionToken prevToken = (tokenList == null || currentIndex - 1 < 0) ? null :
235                tokenList.get(currentIndex - 1);
236        ExpressionToken nextToken = (tokenList == null || currentIndex + 1 >= tokenList.size()) ? null :
237                tokenList.get(currentIndex + 1);
238        boolean validToken = true;
239        if (prevToken != null && (prevToken.type == ExpressionToken.And || prevToken.type == ExpressionToken.Or || prevToken.type == ExpressionToken.StartParenthesis) == false) {
240            errorMessages.add("only and, or could sit before condition");
241            validToken = false;
242        }
243        if (nextToken != null && (nextToken.type == ExpressionToken.Or || nextToken.type == ExpressionToken.And || nextToken.type == ExpressionToken.EndParenthesis || nextToken.type == ExpressionToken.StartParenthesis) == false) {
244            errorMessages.add("only (, ), and, or could sit after condition");
245            validToken = false;
246        }
247        ExpressionToken conditionToken = tokenList.get(currentIndex);
248        String conditionLetter = conditionToken.value;
249        boolean validConditonLetter = false;
250        if (propsAlpha != null) {
251            for (String propAlpha : propsAlpha) {
252                if (propAlpha != null &&
253                        propAlpha.equalsIgnoreCase(conditionLetter)) {
254                    validConditonLetter = true;
255                }
256            }
257        }
258        if (!validConditonLetter) {
259            errorMessages.add(conditionLetter + " is not a valid conditon");
260            validToken = false;
261        }
262        return validToken;
263    }
264
265    private List<ExpressionToken> getTokenList(List<String> tokenValueList) {
266        List<ExpressionToken> tokenList = new ArrayList<ExpressionToken>();
267        for (String value : tokenValueList) {
268            if (value.isEmpty()) {
269                continue;
270            }
271            if ("(".equals(value)) {
272                ExpressionToken t = new ExpressionToken();
273                t.type = ExpressionToken.StartParenthesis;
274                tokenList.add(t);
275            } else if (")".equals(value)) {
276                ExpressionToken t = new ExpressionToken();
277                t.type = ExpressionToken.EndParenthesis;
278                tokenList.add(t);
279
280            } else if ("and".equals(value)) {
281                ExpressionToken t = new ExpressionToken();
282                t.type = ExpressionToken.And;
283                tokenList.add(t);
284
285            } else if ("or".equals(value)) {
286                ExpressionToken t = new ExpressionToken();
287                t.type = ExpressionToken.Or;
288                tokenList.add(t);
289
290            } else {
291                ExpressionToken t = new ExpressionToken();
292                t.type = ExpressionToken.Condition;
293                t.value = value;
294                tokenList.add(t);
295
296            }
297        }
298        return tokenList;
299    }
300
301    private List<String> getTokenValue(String expression) {
302        expression = expression.toLowerCase();
303        List<String> tokenValueList = new ArrayList<String>();
304        StringBuffer tokenValue = new StringBuffer();
305        for (int i = 0; i < expression.length(); i++) {
306
307            char ch = expression.charAt(i);
308            if (Character.isSpaceChar(ch)) {
309                tokenValueList.add(tokenValue.toString());
310                tokenValue = new StringBuffer();
311            } else if (ch == '(' || ch == ')') {
312                tokenValueList.add(tokenValue.toString());
313                tokenValue = new StringBuffer();
314                tokenValueList.add(String.valueOf(ch));
315            } else {
316                tokenValue.append(ch);
317            }
318        }
319        tokenValueList.add(tokenValue.toString());
320        return tokenValueList;
321    }
322
323    public void setExpression(String expression) {
324        this.expression = expression;
325        List<String> tokenValueList = getTokenValue(expression);
326        this.tokenList = getTokenList(tokenValueList);
327    }
328
329    public String getExpression() {
330        return expression;
331    }
332
333    public List<ExpressionToken> getTokenList() {
334        return tokenList;
335    }
336
337    public PropositionEditor parseExpressionIntoRule(RuleEditor ruleEditor) {
338
339        PropositionEditor oldEditor = (PropositionEditor) ruleEditor.getProposition();
340        List<PropositionEditor> rcs = this.getPropositions(new ArrayList<PropositionEditor>(), oldEditor);
341
342        List<ExpressionToken> rpnList = getRPN(tokenList);
343        return ruleFromRPN(rpnList, rcs);
344    }
345
346    private List<PropositionEditor> getPropositions(List<PropositionEditor> propositions, PropositionEditor propositionEditor) {
347        propositions.add(propositionEditor);
348        if (propositionEditor.getCompoundComponents() != null) {
349            for (PropositionEditor child : propositionEditor.getCompoundEditors()) {
350                this.getPropositions(propositions, child);
351            }
352        }
353        return propositions;
354    }
355
356    /**
357     * If higher push to stack, else pop till less than or equal, add to list push to stack if ( push to stack if ) pop to
358     * list till (.
359     * <p/>
360     * http://en.wikipedia.org/wiki/Reverse_Polish_notation
361     */
362    private List<ExpressionToken> getRPN(List<ExpressionToken> nodeList) {
363        List<ExpressionToken> rpnList = new ArrayList<ExpressionToken>();
364        Stack<ExpressionToken> operatorStack = new Stack<ExpressionToken>();
365
366        for (ExpressionToken token : nodeList) {
367            if (token.type == ExpressionToken.Condition) {
368                rpnList.add(token);
369            } else if (token.type == ExpressionToken.EndParenthesis) {
370                while (operatorStack.peek().type != ExpressionToken.StartParenthesis) {
371                    rpnList.add(operatorStack.pop());
372                }
373                operatorStack.pop();// pop the (
374            } else {
375                operatorStack.push(token);
376            }
377        }
378
379        //Add remaining operators to rpnlist
380        while (operatorStack.isEmpty() == false){
381            rpnList.add(operatorStack.pop());
382        }
383
384        return rpnList;
385    }
386
387    /**
388     * Build the binary tree from list of tokens
389     */
390    private PropositionEditor ruleFromRPN(List<ExpressionToken> rpnList, List<PropositionEditor> rcs) {
391        //if rule is empty
392        if (rpnList.size() == 0) {
393            return new PropositionEditor();
394        }
395
396        Stack<PropositionEditor> conditionStack = new Stack<PropositionEditor>();
397        Stack<PropositionEditor> simpleProps = new Stack<PropositionEditor>();
398        for (ExpressionToken token : rpnList) {
399            if (token.type == ExpressionToken.Condition) {
400                PropositionEditor rc = lookupPropositionEditor(rcs, token.value);
401                if (rc.getPropositionTypeCode().equals("C")){
402                    rc.setCompoundEditors(new ArrayList<PropositionEditor>());
403                }
404                conditionStack.push(rc);
405            } else {
406                if(simpleProps.empty()){
407                    simpleProps.push(conditionStack.pop());
408                }
409                simpleProps.push(conditionStack.pop());
410                if(conditionStack.peek().getPropositionTypeCode().equals("C")) {
411                    PropositionEditor compound = conditionStack.pop();
412                    if (token.type == ExpressionToken.And){
413                        PropositionTreeUtil.setTypeForCompoundOpCode(compound, LogicalOperator.AND.getCode());
414                    } else if (token.type == ExpressionToken.Or) {
415                        PropositionTreeUtil.setTypeForCompoundOpCode(compound, LogicalOperator.OR.getCode());
416                    }
417                    while (!simpleProps.empty()) {
418                        compound.getCompoundEditors().add(simpleProps.pop());
419                    }
420                    conditionStack.push(compound);
421                }
422            }
423        }
424
425        return conditionStack.pop();
426    }
427
428    private PropositionEditor lookupPropositionEditor(List<PropositionEditor> rcs, String key) {
429        if (rcs != null) {
430            for (PropositionEditor rc : rcs) {
431                if (rc.getKey().equalsIgnoreCase(key)) {
432                    return rc;
433                }
434            }
435        }
436        return null;
437    }
438}