001/*
002 * (C) Copyright 2006-2011 Nuxeo SA (http://nuxeo.com/) and others.
003 *
004 * Licensed under the Apache 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.apache.org/licenses/LICENSE-2.0
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 *
016 * Contributors:
017 *     bstefanescu
018 *
019 * $Id$
020 */
021
022package org.nuxeo.ecm.webengine.security;
023
024import java.text.ParseException;
025import java.util.ArrayList;
026import java.util.Arrays;
027import java.util.Iterator;
028import java.util.LinkedList;
029import java.util.List;
030import java.util.StringTokenizer;
031
032/**
033 * @author <a href="mailto:bs@nuxeo.com">Bogdan Stefanescu</a>
034 */
035public class PostfixExpression implements Iterable<PostfixExpression.Token> {
036
037    public static final int ARG = 0;
038
039    public static final int NOT = 1;
040
041    public static final int AND = 2;
042
043    public static final int OR = 3;
044
045    public static final int PARA = 4;
046
047    public static final int LPARA = 5;
048
049    public static final int RPARA = 6;
050
051    protected Token[] expr;
052
053    public PostfixExpression(String expr) throws ParseException {
054        parse(expr);
055    }
056
057    public Token[] getExpression() {
058        return expr;
059    }
060
061    public Iterator<Token> iterator() {
062        return Arrays.asList(expr).iterator();
063    }
064
065    private static void pushOp(Token tok, OpStack stack, List<Token> result) {
066        if (!stack.isEmpty() && stack.top().type <= tok.type) {
067            result.add(stack.pop());
068        }
069        stack.push(tok);
070    }
071
072    public Object visit(Visitor visitor) {
073        LinkedList<Object> stack = new LinkedList<Object>();
074        for (Token token : expr) {
075            if (token.type == ARG) {
076                stack.add(visitor.createParameter(token));
077            } else {
078                Object lparam;
079                Object rparam = null;
080                int arity = token.type > NOT ? 2 : 1;
081                if (arity == 1) {
082                    lparam = stack.removeLast();
083                } else {// arity == 2
084                    rparam = stack.removeLast();
085                    lparam = stack.removeLast();
086                }
087                stack.add(visitor.createOperation(token, lparam, rparam));
088            }
089        }
090        return stack.getLast();
091    }
092
093    @Override
094    public String toString() {
095        StringBuilder sb = new StringBuilder();
096        for (Token token : expr) {
097            sb.append(token.name).append(" ");
098        }
099        return sb.toString();
100    }
101
102    public interface Visitor {
103        Object createParameter(Token token);
104
105        Object createOperation(Token token, Object lparam, Object rparam);
106    }
107
108    public static class Token {
109        public final int type;
110
111        public final String name;
112
113        public Token(int type, String name) {
114            this.type = type;
115            this.name = name;
116        }
117
118        @Override
119        public String toString() {
120            return name;
121        }
122    }
123
124    public static class OpStack extends LinkedList<Token> {
125        private static final long serialVersionUID = 1L;
126
127        public final void push(Token token) {
128            add(token);
129        }
130
131        public final Token pop() {
132            return removeLast();
133        }
134
135        public final Token top() {
136            return getLast();
137        }
138    }
139
140    protected void parse(String expr) throws ParseException {
141        OpStack stack = new OpStack();
142        List<Token> result = new ArrayList<Token>();
143        StringTokenizer tok = new StringTokenizer(expr, " \t\n\r\f()", true);
144        while (tok.hasMoreTokens()) {
145            String token = tok.nextToken();
146            char c = token.charAt(0);
147            switch (c) {
148            case ' ':
149            case '\t':
150            case '\r':
151            case '\n':
152            case '\f':
153                break;
154            case '(':
155                stack.push(new Token(LPARA, "("));
156                break;
157            case ')':
158                while (!stack.isEmpty() && stack.top().type != LPARA) {
159                    result.add(stack.pop());
160                }
161                if (stack.isEmpty()) {
162                    throw new ParseException("Not matching LPARA '(' found ", -1);
163                }
164                stack.pop(); // remove LPARA from stack
165                break;
166            default:
167                if ("OR".equals(token)) {
168                    pushOp(new Token(OR, "OR"), stack, result);
169                } else if ("AND".equals(token)) {
170                    pushOp(new Token(AND, "AND"), stack, result);
171                } else if ("NOT".equals(token)) {
172                    pushOp(new Token(NOT, "NOT"), stack, result);
173                } else {
174                    result.add(new Token(ARG, token));
175                }
176            }
177        }
178        while (!stack.isEmpty()) {
179            result.add(stack.pop());
180        }
181        this.expr = result.toArray(new Token[result.size()]);
182    }
183
184}