View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
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          // We already crossed the label node index. So need to reduce 1 here.
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       // When ) comes we expect atleast a ( node and another leaf/non leaf node
115       // in stack.
116       throw new ParseException();
117     } else {
118       ExpressionNode top = expStack.pop();
119       ExpressionNode secondTop = expStack.pop();
120       // The second top must be a ( node and top should not be a ). Top can be
121       // any thing else
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       // a&(b|) is not valid.
127       // The top can be a ! node but with exactly child nodes. !).. is invalid
128       // Other NonLeafExpressionNode , then there should be exactly 2 child.
129       // (a&) is not valid.
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       // When (a|b)&(c|d) comes while processing the second ) there will be
138       // already (a|b)& node
139       // avail in the stack. The top will be c|d node. We need to take it out
140       // and combine as one
141       // node.
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             // It is a NOT node. So there may be a NonLeafExpressionNode below
149             // it to which the
150             // completed NOT can be added now.
151             if (!expStack.isEmpty()) {
152               ExpressionNode fourthTop = expStack.peek();
153               if (fourthTop instanceof NonLeafExpressionNode) {
154                 // Its Operator will be OR or AND
155                 NonLeafExpressionNode nlFourthTop = (NonLeafExpressionNode) fourthTop;
156                 assert nlFourthTop.getOperator() != Operator.NOT;
157                 // Also for sure its number of children will be 1
158                 assert nlFourthTop.getChildExps().size() == 1;
159                 nlFourthTop.addChildExp(nlThirdTop);
160                 return;// This case no need to add back the nlThirdTop.
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       // Top can not be a Label Node. a(.. is not valid. but ((a.. is fine.
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         // Top is non leaf.
180         // It can be ! node but with out any child nodes. !a(.. is invalid
181         // Other NonLeafExpressionNode , then there should be exactly 1 child.
182         // a&b( is not valid.
183         // a&( is valid though. Also !( is valid
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     // When ! comes, the stack can be empty or top ( or top can be some exp like
244     // a&
245     // !!.., a!, a&b!, !a! are invalid
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 }