001/*
002 * (C) Copyright 2006-2011 Nuxeo SAS (http://nuxeo.com/) and contributors.
003 *
004 * All rights reserved. This program and the accompanying materials
005 * are made available under the terms of the GNU Lesser General Public License
006 * (LGPL) version 2.1 which accompanies this distribution, and is available at
007 * http://www.gnu.org/licenses/lgpl.html
008 *
009 * This library is distributed in the hope that it will be useful,
010 * but WITHOUT ANY WARRANTY; without even the implied warranty of
011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012 * Lesser General Public License for more details.
013 *
014 * Contributors:
015 *     bstefanescu
016 *
017 * $Id$
018 */
019
020package org.nuxeo.ecm.webengine.security;
021
022import java.text.ParseException;
023import java.util.ArrayList;
024import java.util.Arrays;
025import java.util.Iterator;
026import java.util.LinkedList;
027import java.util.List;
028import java.util.StringTokenizer;
029
030/**
031 * @author <a href="mailto:bs@nuxeo.com">Bogdan Stefanescu</a>
032 */
033public class PostfixExpression implements Iterable<PostfixExpression.Token> {
034
035    public static final int ARG = 0;
036
037    public static final int NOT = 1;
038
039    public static final int AND = 2;
040
041    public static final int OR = 3;
042
043    public static final int PARA = 4;
044
045    public static final int LPARA = 5;
046
047    public static final int RPARA = 6;
048
049    protected Token[] expr;
050
051    public PostfixExpression(String expr) throws ParseException {
052        parse(expr);
053    }
054
055    public Token[] getExpression() {
056        return expr;
057    }
058
059    public Iterator<Token> iterator() {
060        return Arrays.asList(expr).iterator();
061    }
062
063    private static void pushOp(Token tok, OpStack stack, List<Token> result) {
064        if (!stack.isEmpty() && stack.top().type <= tok.type) {
065            result.add(stack.pop());
066        }
067        stack.push(tok);
068    }
069
070    public Object visit(Visitor visitor) {
071        LinkedList<Object> stack = new LinkedList<Object>();
072        for (Token token : expr) {
073            if (token.type == ARG) {
074                stack.add(visitor.createParameter(token));
075            } else {
076                Object lparam;
077                Object rparam = null;
078                int arity = token.type > NOT ? 2 : 1;
079                if (arity == 1) {
080                    lparam = stack.removeLast();
081                } else {// arity == 2
082                    rparam = stack.removeLast();
083                    lparam = stack.removeLast();
084                }
085                stack.add(visitor.createOperation(token, lparam, rparam));
086            }
087        }
088        return stack.getLast();
089    }
090
091    @Override
092    public String toString() {
093        StringBuilder sb = new StringBuilder();
094        for (Token token : expr) {
095            sb.append(token.name).append(" ");
096        }
097        return sb.toString();
098    }
099
100    public interface Visitor {
101        Object createParameter(Token token);
102
103        Object createOperation(Token token, Object lparam, Object rparam);
104    }
105
106    public static class Token {
107        public final int type;
108
109        public final String name;
110
111        public Token(int type, String name) {
112            this.type = type;
113            this.name = name;
114        }
115
116        @Override
117        public String toString() {
118            return name;
119        }
120    }
121
122    public static class OpStack extends LinkedList<Token> {
123        private static final long serialVersionUID = 1L;
124
125        public final void push(Token token) {
126            add(token);
127        }
128
129        public final Token pop() {
130            return removeLast();
131        }
132
133        public final Token top() {
134            return getLast();
135        }
136    }
137
138    protected void parse(String expr) throws ParseException {
139        OpStack stack = new OpStack();
140        List<Token> result = new ArrayList<Token>();
141        StringTokenizer tok = new StringTokenizer(expr, " \t\n\r\f()", true);
142        while (tok.hasMoreTokens()) {
143            String token = tok.nextToken();
144            char c = token.charAt(0);
145            switch (c) {
146            case ' ':
147            case '\t':
148            case '\r':
149            case '\n':
150            case '\f':
151                break;
152            case '(':
153                stack.push(new Token(LPARA, "("));
154                break;
155            case ')':
156                while (!stack.isEmpty() && stack.top().type != LPARA) {
157                    result.add(stack.pop());
158                }
159                if (stack.isEmpty()) {
160                    throw new ParseException("Not matching LPARA '(' found ", -1);
161                }
162                stack.pop(); // remove LPARA from stack
163                break;
164            default:
165                if ("OR".equals(token)) {
166                    pushOp(new Token(OR, "OR"), stack, result);
167                } else if ("AND".equals(token)) {
168                    pushOp(new Token(AND, "AND"), stack, result);
169                } else if ("NOT".equals(token)) {
170                    pushOp(new Token(NOT, "NOT"), stack, result);
171                } else {
172                    result.add(new Token(ARG, token));
173                }
174            }
175        }
176        while (!stack.isEmpty()) {
177            result.add(stack.pop());
178        }
179        this.expr = result.toArray(new Token[result.size()]);
180    }
181
182}