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}