1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.hadoop.hbase.security.visibility;
19
20 import java.util.ArrayList;
21 import java.util.List;
22 import java.util.Stack;
23
24 import org.apache.hadoop.hbase.classification.InterfaceAudience;
25 import org.apache.hadoop.hbase.security.visibility.expression.ExpressionNode;
26 import org.apache.hadoop.hbase.security.visibility.expression.LeafExpressionNode;
27 import org.apache.hadoop.hbase.security.visibility.expression.NonLeafExpressionNode;
28 import org.apache.hadoop.hbase.security.visibility.expression.Operator;
29 import org.apache.hadoop.hbase.util.Bytes;
30
31 @InterfaceAudience.Private
32 public class ExpressionParser {
33
34 private static final char CLOSE_PARAN = ')';
35 private static final char OPEN_PARAN = '(';
36 private static final char OR = '|';
37 private static final char AND = '&';
38 private static final char NOT = '!';
39 private static final char SPACE = ' ';
40 private static final char DOUBLE_QUOTES = '"';
41 public ExpressionNode parse(String expS) throws ParseException {
42 expS = expS.trim();
43 Stack<ExpressionNode> expStack = new Stack<ExpressionNode>();
44 int index = 0;
45 byte[] exp = Bytes.toBytes(expS);
46 int endPos = exp.length;
47 while (index < endPos) {
48 byte b = exp[index];
49 switch (b) {
50 case OPEN_PARAN:
51 processOpenParan(expStack, expS, index);
52 index = skipSpaces(exp, index);
53 break;
54 case CLOSE_PARAN:
55 processCloseParan(expStack, expS, index);
56 index = skipSpaces(exp, index);
57 break;
58 case AND:
59 case OR:
60 processANDorOROp(getOperator(b), expStack, expS, index);
61 index = skipSpaces(exp, index);
62 break;
63 case NOT:
64 processNOTOp(expStack, expS, index);
65 break;
66 case DOUBLE_QUOTES:
67 int labelOffset = ++index;
68
69
70
71 List<Byte> list = new ArrayList<Byte>();
72 while (index < endPos && !endDoubleQuotesFound(exp[index])) {
73 if (exp[index] == '\\') {
74 index++;
75 if (exp[index] != '\\' && exp[index] != '"')
76 throw new ParseException("invalid escaping with quotes " + expS + " at column : "
77 + index);
78 }
79 list.add(exp[index]);
80 index++;
81 }
82
83 if(index == endPos) {
84 throw new ParseException("No terminating quotes " + expS + " at column : " + index);
85 }
86
87
88
89 byte[] array = com.google.common.primitives.Bytes.toArray(list);
90 String leafExp = Bytes.toString(array).trim();
91 if (leafExp.isEmpty()) {
92 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
93 }
94 processLabelExpNode(new LeafExpressionNode(leafExp), expStack, expS, index);
95 index = skipSpaces(exp, index);
96 break;
97 default:
98 labelOffset = index;
99 do {
100 if (!VisibilityLabelsValidator.isValidAuthChar(exp[index])) {
101 throw new ParseException("Error parsing expression "
102 + expS + " at column : " + index);
103 }
104 index++;
105 } while (index < endPos && !isEndOfLabel(exp[index]));
106 leafExp = new String(exp, labelOffset, index - labelOffset).trim();
107 if (leafExp.isEmpty()) {
108 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
109 }
110 processLabelExpNode(new LeafExpressionNode(leafExp), expStack, expS, index);
111
112 index--;
113 index = skipSpaces(exp, index);
114 }
115 index++;
116 }
117 if (expStack.size() != 1) {
118 throw new ParseException("Error parsing expression " + expS);
119 }
120 ExpressionNode top = expStack.pop();
121 if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
122 throw new ParseException("Error parsing expression " + expS);
123 }
124 if (top instanceof NonLeafExpressionNode) {
125 NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
126 if (nlTop.getOperator() == Operator.NOT) {
127 if (nlTop.getChildExps().size() != 1) {
128 throw new ParseException("Error parsing expression " + expS);
129 }
130 } else if (nlTop.getChildExps().size() != 2) {
131 throw new ParseException("Error parsing expression " + expS);
132 }
133 }
134 return top;
135 }
136
137 private int skipSpaces(byte[] exp, int index) {
138 while (index < exp.length -1 && exp[index+1] == SPACE) {
139 index++;
140 }
141 return index;
142 }
143
144 private void processCloseParan(Stack<ExpressionNode> expStack, String expS, int index)
145 throws ParseException {
146 if (expStack.size() < 2) {
147
148
149 throw new ParseException();
150 } else {
151 ExpressionNode top = expStack.pop();
152 ExpressionNode secondTop = expStack.pop();
153
154
155 if (top == LeafExpressionNode.OPEN_PARAN_NODE
156 || secondTop != LeafExpressionNode.OPEN_PARAN_NODE) {
157 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
158 }
159
160
161
162
163 if (top instanceof NonLeafExpressionNode) {
164 NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
165 if ((nlTop.getOperator() == Operator.NOT && nlTop.getChildExps().size() != 1)
166 || (nlTop.getOperator() != Operator.NOT && nlTop.getChildExps().size() != 2)) {
167 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
168 }
169 }
170
171
172
173
174
175 if (!expStack.isEmpty()) {
176 ExpressionNode thirdTop = expStack.peek();
177 if (thirdTop instanceof NonLeafExpressionNode) {
178 NonLeafExpressionNode nlThirdTop = (NonLeafExpressionNode) expStack.pop();
179 nlThirdTop.addChildExp(top);
180 if (nlThirdTop.getOperator() == Operator.NOT) {
181
182
183
184 if (!expStack.isEmpty()) {
185 ExpressionNode fourthTop = expStack.peek();
186 if (fourthTop instanceof NonLeafExpressionNode) {
187
188 NonLeafExpressionNode nlFourthTop = (NonLeafExpressionNode) fourthTop;
189 assert nlFourthTop.getOperator() != Operator.NOT;
190
191 assert nlFourthTop.getChildExps().size() == 1;
192 nlFourthTop.addChildExp(nlThirdTop);
193 return;
194 }
195 }
196 }
197 top = nlThirdTop;
198 }
199 }
200 expStack.push(top);
201 }
202 }
203
204 private void processOpenParan(Stack<ExpressionNode> expStack, String expS, int index)
205 throws ParseException {
206 if (!expStack.isEmpty()) {
207 ExpressionNode top = expStack.peek();
208
209 if (top instanceof LeafExpressionNode && top != LeafExpressionNode.OPEN_PARAN_NODE) {
210 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
211 } else if (top instanceof NonLeafExpressionNode) {
212
213
214
215
216
217 NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
218 if ((nlTop.getOperator() == Operator.NOT && nlTop.getChildExps().size() != 0)
219 || (nlTop.getOperator() != Operator.NOT && nlTop.getChildExps().size() != 1)) {
220 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
221 }
222 }
223 }
224 expStack.push(LeafExpressionNode.OPEN_PARAN_NODE);
225 }
226
227 private void processLabelExpNode(LeafExpressionNode node, Stack<ExpressionNode> expStack,
228 String expS, int index) throws ParseException {
229 if (expStack.isEmpty()) {
230 expStack.push(node);
231 } else {
232 ExpressionNode top = expStack.peek();
233 if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
234 expStack.push(node);
235 } else if (top instanceof NonLeafExpressionNode) {
236 NonLeafExpressionNode nlTop = (NonLeafExpressionNode) expStack.pop();
237 nlTop.addChildExp(node);
238 if (nlTop.getOperator() == Operator.NOT && !expStack.isEmpty()) {
239 ExpressionNode secondTop = expStack.peek();
240 if (secondTop == LeafExpressionNode.OPEN_PARAN_NODE) {
241 expStack.push(nlTop);
242 } else if (secondTop instanceof NonLeafExpressionNode) {
243 ((NonLeafExpressionNode) secondTop).addChildExp(nlTop);
244 }
245 } else {
246 expStack.push(nlTop);
247 }
248 } else {
249 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
250 }
251 }
252 }
253
254 private void processANDorOROp(Operator op, Stack<ExpressionNode> expStack, String expS, int index)
255 throws ParseException {
256 if (expStack.isEmpty()) {
257 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
258 }
259 ExpressionNode top = expStack.pop();
260 if (top.isSingleNode()) {
261 if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
262 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
263 }
264 expStack.push(new NonLeafExpressionNode(op, top));
265 } else {
266 NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
267 if (nlTop.getChildExps().size() != 2) {
268 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
269 }
270 expStack.push(new NonLeafExpressionNode(op, nlTop));
271 }
272 }
273
274 private void processNOTOp(Stack<ExpressionNode> expStack, String expS, int index)
275 throws ParseException {
276
277
278
279 if (!expStack.isEmpty()) {
280 ExpressionNode top = expStack.peek();
281 if (top.isSingleNode() && top != LeafExpressionNode.OPEN_PARAN_NODE) {
282 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
283 }
284 if (!top.isSingleNode() && ((NonLeafExpressionNode) top).getChildExps().size() != 1) {
285 throw new ParseException("Error parsing expression " + expS + " at column : " + index);
286 }
287 }
288 expStack.push(new NonLeafExpressionNode(Operator.NOT));
289 }
290
291 private static boolean endDoubleQuotesFound(byte b) {
292 return (b == DOUBLE_QUOTES);
293 }
294 private static boolean isEndOfLabel(byte b) {
295 return (b == OPEN_PARAN || b == CLOSE_PARAN || b == OR || b == AND ||
296 b == NOT || b == SPACE);
297 }
298
299 private static Operator getOperator(byte op) {
300 switch (op) {
301 case AND:
302 return Operator.AND;
303 case OR:
304 return Operator.OR;
305 case NOT:
306 return Operator.NOT;
307 }
308 return null;
309 }
310 }