001/**
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.security.visibility;
019
020import java.nio.charset.StandardCharsets;
021import java.util.ArrayList;
022import java.util.List;
023import java.util.Stack;
024
025import org.apache.yetus.audience.InterfaceAudience;
026import org.apache.hadoop.hbase.security.visibility.expression.ExpressionNode;
027import org.apache.hadoop.hbase.security.visibility.expression.LeafExpressionNode;
028import org.apache.hadoop.hbase.security.visibility.expression.NonLeafExpressionNode;
029import org.apache.hadoop.hbase.security.visibility.expression.Operator;
030import org.apache.hadoop.hbase.util.Bytes;
031
032@InterfaceAudience.Private
033public class ExpressionParser {
034
035  private static final char CLOSE_PARAN = ')';
036  private static final char OPEN_PARAN = '(';
037  private static final char OR = '|';
038  private static final char AND = '&';
039  private static final char NOT = '!';
040  private static final char SPACE = ' ';
041  private static final char DOUBLE_QUOTES = '"';
042  public ExpressionNode parse(String expS) throws ParseException {
043    expS = expS.trim();
044    Stack<ExpressionNode> expStack = new Stack<>();
045    int index = 0;
046    byte[] exp = Bytes.toBytes(expS);
047    int endPos = exp.length;
048    while (index < endPos) {
049      byte b = exp[index];
050      switch (b) {
051        case OPEN_PARAN:
052          processOpenParan(expStack, expS, index);
053          index = skipSpaces(exp, index);
054          break;
055        case CLOSE_PARAN:
056          processCloseParan(expStack, expS, index);
057          index = skipSpaces(exp, index);
058          break;
059        case AND:
060        case OR:
061          processANDorOROp(getOperator(b), expStack, expS, index);
062          index = skipSpaces(exp, index);
063          break;
064        case NOT:
065          processNOTOp(expStack, expS, index);
066          break;
067        case DOUBLE_QUOTES:
068          int labelOffset = ++index;
069          // We have to rewrite the expression within double quotes as incase of expressions 
070          // with escape characters we may have to avoid them as the original expression did
071          // not have them
072          List<Byte> list = new ArrayList<>();
073          while (index < endPos && !endDoubleQuotesFound(exp[index])) {
074            if (exp[index] == '\\') {
075              index++;
076              if (exp[index] != '\\' && exp[index] != '"')
077                throw new ParseException("invalid escaping with quotes " + expS + " at column : "
078                    + index);
079            }
080            list.add(exp[index]);
081            index++;
082          }
083          // The expression has come to the end. still no double quotes found 
084          if(index == endPos) {
085            throw new ParseException("No terminating quotes " + expS + " at column : " + index);
086          }
087          // This could be costly. but do we have any alternative?
088          // If we don't do this way then we may have to handle while checking the authorizations.
089          // Better to do it here.
090          byte[] array = org.apache.hbase.thirdparty.com.google.common.primitives.Bytes.toArray(list);
091          String leafExp = Bytes.toString(array).trim();
092          if (leafExp.isEmpty()) {
093            throw new ParseException("Error parsing expression " + expS + " at column : " + index);
094          }
095          processLabelExpNode(new LeafExpressionNode(leafExp), expStack, expS, index);
096          index = skipSpaces(exp, index);
097          break;
098        default:
099          labelOffset = index;
100          do {
101            if (!VisibilityLabelsValidator.isValidAuthChar(exp[index])) {
102              throw new ParseException("Error parsing expression " 
103                 + expS + " at column : " + index);
104            }
105            index++;
106          } while (index < endPos && !isEndOfLabel(exp[index]));
107          leafExp =
108              new String(exp, labelOffset, index - labelOffset, StandardCharsets.UTF_8).trim();
109          if (leafExp.isEmpty()) {
110            throw new ParseException("Error parsing expression " + expS + " at column : " + index);
111          }
112          processLabelExpNode(new LeafExpressionNode(leafExp), expStack, expS, index);
113          // We already crossed the label node index. So need to reduce 1 here.
114          index--;
115          index = skipSpaces(exp, index);
116      }
117      index++;
118    }
119    if (expStack.size() != 1) {
120      throw new ParseException("Error parsing expression " + expS);
121    }
122    ExpressionNode top = expStack.pop();
123    if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
124      throw new ParseException("Error parsing expression " + expS);
125    }
126    if (top instanceof NonLeafExpressionNode) {
127      NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
128      if (nlTop.getOperator() == Operator.NOT) {
129        if (nlTop.getChildExps().size() != 1) {
130          throw new ParseException("Error parsing expression " + expS);
131        }
132      } else if (nlTop.getChildExps().size() != 2) {
133        throw new ParseException("Error parsing expression " + expS);
134      }
135    }
136    return top;
137  }
138
139  private int skipSpaces(byte[] exp, int index) {
140    while (index < exp.length -1 && exp[index+1] == SPACE) {
141      index++;
142    }
143    return index;
144  }
145
146  private void processCloseParan(Stack<ExpressionNode> expStack, String expS, int index)
147      throws ParseException {
148    if (expStack.size() < 2) {
149      // When ) comes we expect atleast a ( node and another leaf/non leaf node
150      // in stack.
151      throw new ParseException();
152    } else {
153      ExpressionNode top = expStack.pop();
154      ExpressionNode secondTop = expStack.pop();
155      // The second top must be a ( node and top should not be a ). Top can be
156      // any thing else
157      if (top == LeafExpressionNode.OPEN_PARAN_NODE
158          || secondTop != LeafExpressionNode.OPEN_PARAN_NODE) {
159        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
160      }
161      // a&(b|) is not valid.
162      // The top can be a ! node but with exactly child nodes. !).. is invalid
163      // Other NonLeafExpressionNode , then there should be exactly 2 child.
164      // (a&) is not valid.
165      if (top instanceof NonLeafExpressionNode) {
166        NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
167        if ((nlTop.getOperator() == Operator.NOT && nlTop.getChildExps().size() != 1)
168            || (nlTop.getOperator() != Operator.NOT && nlTop.getChildExps().size() != 2)) {
169          throw new ParseException("Error parsing expression " + expS + " at column : " + index);
170        }
171      }
172      // When (a|b)&(c|d) comes while processing the second ) there will be
173      // already (a|b)& node
174      // avail in the stack. The top will be c|d node. We need to take it out
175      // and combine as one
176      // node.
177      if (!expStack.isEmpty()) {
178        ExpressionNode thirdTop = expStack.peek();
179        if (thirdTop instanceof NonLeafExpressionNode) {
180          NonLeafExpressionNode nlThirdTop = (NonLeafExpressionNode) expStack.pop();
181          nlThirdTop.addChildExp(top);
182          if (nlThirdTop.getOperator() == Operator.NOT) {
183            // It is a NOT node. So there may be a NonLeafExpressionNode below
184            // it to which the
185            // completed NOT can be added now.
186            if (!expStack.isEmpty()) {
187              ExpressionNode fourthTop = expStack.peek();
188              if (fourthTop instanceof NonLeafExpressionNode) {
189                // Its Operator will be OR or AND
190                NonLeafExpressionNode nlFourthTop = (NonLeafExpressionNode) fourthTop;
191                assert nlFourthTop.getOperator() != Operator.NOT;
192                // Also for sure its number of children will be 1
193                assert nlFourthTop.getChildExps().size() == 1;
194                nlFourthTop.addChildExp(nlThirdTop);
195                return;// This case no need to add back the nlThirdTop.
196              }
197            }
198          }
199          top = nlThirdTop;
200        }
201      }
202      expStack.push(top);
203    }
204  }
205
206  private void processOpenParan(Stack<ExpressionNode> expStack, String expS, int index)
207      throws ParseException {
208    if (!expStack.isEmpty()) {
209      ExpressionNode top = expStack.peek();
210      // Top can not be a Label Node. a(.. is not valid. but ((a.. is fine.
211      if (top instanceof LeafExpressionNode && top != LeafExpressionNode.OPEN_PARAN_NODE) {
212        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
213      } else if (top instanceof NonLeafExpressionNode) {
214        // Top is non leaf.
215        // It can be ! node but with out any child nodes. !a(.. is invalid
216        // Other NonLeafExpressionNode , then there should be exactly 1 child.
217        // a&b( is not valid.
218        // a&( is valid though. Also !( is valid
219        NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
220        if ((nlTop.getOperator() == Operator.NOT && nlTop.getChildExps().size() != 0)
221            || (nlTop.getOperator() != Operator.NOT && nlTop.getChildExps().size() != 1)) {
222          throw new ParseException("Error parsing expression " + expS + " at column : " + index);
223        }
224      }
225    }
226    expStack.push(LeafExpressionNode.OPEN_PARAN_NODE);
227  }
228
229  private void processLabelExpNode(LeafExpressionNode node, Stack<ExpressionNode> expStack,
230      String expS, int index) throws ParseException {
231    if (expStack.isEmpty()) {
232      expStack.push(node);
233    } else {
234      ExpressionNode top = expStack.peek();
235      if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
236        expStack.push(node);
237      } else if (top instanceof NonLeafExpressionNode) {
238        NonLeafExpressionNode nlTop = (NonLeafExpressionNode) expStack.pop();
239        nlTop.addChildExp(node);
240        if (nlTop.getOperator() == Operator.NOT && !expStack.isEmpty()) {
241          ExpressionNode secondTop = expStack.peek();
242          if (secondTop == LeafExpressionNode.OPEN_PARAN_NODE) {
243            expStack.push(nlTop);
244          } else if (secondTop instanceof NonLeafExpressionNode) {
245            ((NonLeafExpressionNode) secondTop).addChildExp(nlTop);
246          }
247        } else {
248          expStack.push(nlTop);
249        }
250      } else {
251        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
252      }
253    }
254  }
255
256  private void processANDorOROp(Operator op, Stack<ExpressionNode> expStack, String expS, int index)
257      throws ParseException {
258    if (expStack.isEmpty()) {
259      throw new ParseException("Error parsing expression " + expS + " at column : " + index);
260    }
261    ExpressionNode top = expStack.pop();
262    if (top.isSingleNode()) {
263      if (top == LeafExpressionNode.OPEN_PARAN_NODE) {
264        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
265      }
266      expStack.push(new NonLeafExpressionNode(op, top));
267    } else {
268      NonLeafExpressionNode nlTop = (NonLeafExpressionNode) top;
269      if (nlTop.getChildExps().size() != 2) {
270        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
271      }
272      expStack.push(new NonLeafExpressionNode(op, nlTop));
273    }
274  }
275
276  private void processNOTOp(Stack<ExpressionNode> expStack, String expS, int index)
277      throws ParseException {
278    // When ! comes, the stack can be empty or top ( or top can be some exp like
279    // a&
280    // !!.., a!, a&b!, !a! are invalid
281    if (!expStack.isEmpty()) {
282      ExpressionNode top = expStack.peek();
283      if (top.isSingleNode() && top != LeafExpressionNode.OPEN_PARAN_NODE) {
284        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
285      }
286      if (!top.isSingleNode() && ((NonLeafExpressionNode) top).getChildExps().size() != 1) {
287        throw new ParseException("Error parsing expression " + expS + " at column : " + index);
288      }
289    }
290    expStack.push(new NonLeafExpressionNode(Operator.NOT));
291  }
292
293  private static boolean endDoubleQuotesFound(byte b) {
294    return (b == DOUBLE_QUOTES);
295  }
296  private static boolean isEndOfLabel(byte b) {
297    return (b == OPEN_PARAN || b == CLOSE_PARAN || b == OR || b == AND || 
298        b == NOT || b == SPACE);
299  }
300
301  private static Operator getOperator(byte op) {
302    switch (op) {
303    case AND:
304      return Operator.AND;
305    case OR:
306      return Operator.OR;
307    case NOT:
308      return Operator.NOT;
309    }
310    return null;
311  }
312}