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    @Override
062    public Iterator<Token> iterator() {
063        return Arrays.asList(expr).iterator();
064    }
065
066    private static void pushOp(Token tok, OpStack stack, List<Token> result) {
067        if (!stack.isEmpty() && stack.top().type <= tok.type) {
068            result.add(stack.pop());
069        }
070        stack.push(tok);
071    }
072
073    public Object visit(Visitor visitor) {
074        LinkedList<Object> stack = new LinkedList<>();
075        for (Token token : expr) {
076            if (token.type == ARG) {
077                stack.add(visitor.createParameter(token));
078            } else {
079                Object lparam;
080                Object rparam = null;
081                int arity = token.type > NOT ? 2 : 1;
082                if (arity == 1) {
083                    lparam = stack.removeLast();
084                } else {// arity == 2
085                    rparam = stack.removeLast();
086                    lparam = stack.removeLast();
087                }
088                stack.add(visitor.createOperation(token, lparam, rparam));
089            }
090        }
091        return stack.getLast();
092    }
093
094    @Override
095    public String toString() {
096        StringBuilder sb = new StringBuilder();
097        for (Token token : expr) {
098            sb.append(token.name).append(" ");
099        }
100        return sb.toString();
101    }
102
103    public interface Visitor {
104        Object createParameter(Token token);
105
106        Object createOperation(Token token, Object lparam, Object rparam);
107    }
108
109    public static class Token {
110        public final int type;
111
112        public final String name;
113
114        public Token(int type, String name) {
115            this.type = type;
116            this.name = name;
117        }
118
119        @Override
120        public String toString() {
121            return name;
122        }
123    }
124
125    public static class OpStack extends LinkedList<Token> {
126        private static final long serialVersionUID = 1L;
127
128        @Override
129        public final void push(Token token) {
130            add(token);
131        }
132
133        @Override
134        public final Token pop() {
135            return removeLast();
136        }
137
138        public final Token top() {
139            return getLast();
140        }
141    }
142
143    protected void parse(String expr) throws ParseException {
144        OpStack stack = new OpStack();
145        List<Token> result = new ArrayList<>();
146        StringTokenizer tok = new StringTokenizer(expr, " \t\n\r\f()", true);
147        while (tok.hasMoreTokens()) {
148            String token = tok.nextToken();
149            char c = token.charAt(0);
150            switch (c) {
151            case ' ':
152            case '\t':
153            case '\r':
154            case '\n':
155            case '\f':
156                break;
157            case '(':
158                stack.push(new Token(LPARA, "("));
159                break;
160            case ')':
161                while (!stack.isEmpty() && stack.top().type != LPARA) {
162                    result.add(stack.pop());
163                }
164                if (stack.isEmpty()) {
165                    throw new ParseException("Not matching LPARA '(' found ", -1);
166                }
167                stack.pop(); // remove LPARA from stack
168                break;
169            default:
170                if ("OR".equals(token)) {
171                    pushOp(new Token(OR, "OR"), stack, result);
172                } else if ("AND".equals(token)) {
173                    pushOp(new Token(AND, "AND"), stack, result);
174                } else if ("NOT".equals(token)) {
175                    pushOp(new Token(NOT, "NOT"), stack, result);
176                } else {
177                    result.add(new Token(ARG, token));
178                }
179            }
180        }
181        while (!stack.isEmpty()) {
182            result.add(stack.pop());
183        }
184        this.expr = result.toArray(new Token[result.size()]);
185    }
186
187}