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