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.List;
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  
28  @InterfaceAudience.Private
29  public class ExpressionExpander {
30  
31    public ExpressionNode expand(ExpressionNode src) {
32      if (!src.isSingleNode()) {
33        NonLeafExpressionNode nlExp = (NonLeafExpressionNode) src;
34        List<ExpressionNode> childExps = nlExp.getChildExps();
35        Operator outerOp = nlExp.getOperator();
36        if (isToBeExpanded(childExps)) {
37          // Any of the child exp is a non leaf exp with & or | operator
38          NonLeafExpressionNode newNode = new NonLeafExpressionNode(nlExp.getOperator());
39          for (ExpressionNode exp : childExps) {
40            if (exp.isSingleNode()) {
41              newNode.addChildExp(exp);
42            } else {
43              newNode.addChildExp(expand(exp));
44            }
45          }
46          nlExp = expandNonLeaf(newNode, outerOp);
47        }
48        return nlExp;
49      }
50      if (src instanceof NonLeafExpressionNode
51          && ((NonLeafExpressionNode) src).getOperator() == Operator.NOT) {
52        // Negate the exp
53        return negate((NonLeafExpressionNode) src);
54      }
55      return src;
56    }
57  
58    private ExpressionNode negate(NonLeafExpressionNode nlExp) {
59      ExpressionNode notChild = nlExp.getChildExps().get(0);
60      if (notChild instanceof LeafExpressionNode) {
61        return nlExp;
62      }
63      NonLeafExpressionNode nlNotChild = (NonLeafExpressionNode) notChild;
64      if (nlNotChild.getOperator() == Operator.NOT) {
65        // negate the negate
66        return nlNotChild.getChildExps().get(0);
67      }
68      Operator negateOp = nlNotChild.getOperator() == Operator.AND ? Operator.OR : Operator.AND;
69      NonLeafExpressionNode newNode = new NonLeafExpressionNode(negateOp);
70      for (ExpressionNode expNode : nlNotChild.getChildExps()) {
71        NonLeafExpressionNode negateNode = new NonLeafExpressionNode(Operator.NOT);
72        negateNode.addChildExp(expNode.deepClone());
73        newNode.addChildExp(expand(negateNode));
74      }
75      return newNode;
76    }
77  
78    private boolean isToBeExpanded(List<ExpressionNode> childExps) {
79      for (ExpressionNode exp : childExps) {
80        if (!exp.isSingleNode()) {
81          return true;
82        }
83      }
84      return false;
85    }
86  
87    private NonLeafExpressionNode expandNonLeaf(NonLeafExpressionNode newNode, Operator outerOp) {
88      // Now go for the merge or expansion across brackets
89      List<ExpressionNode> newChildExps = newNode.getChildExps();
90      assert newChildExps.size() == 2;
91      ExpressionNode leftChild = newChildExps.get(0);
92      ExpressionNode rightChild = newChildExps.get(1);
93      if (rightChild.isSingleNode()) {
94        // Merge the single right node into the left side
95        assert leftChild instanceof NonLeafExpressionNode;
96        newNode = mergeChildNodes(newNode, outerOp, rightChild, (NonLeafExpressionNode) leftChild);
97      } else if (leftChild.isSingleNode()) {
98        // Merge the single left node into the right side
99        assert rightChild instanceof NonLeafExpressionNode;
100       newNode = mergeChildNodes(newNode, outerOp, leftChild, (NonLeafExpressionNode) rightChild);
101     } else {
102       // Both the child exp nodes are non single.
103       NonLeafExpressionNode leftChildNLE = (NonLeafExpressionNode) leftChild;
104       NonLeafExpressionNode rightChildNLE = (NonLeafExpressionNode) rightChild;
105       if (outerOp == leftChildNLE.getOperator() && outerOp == rightChildNLE.getOperator()) {
106         // Merge
107         NonLeafExpressionNode leftChildNLEClone = leftChildNLE.deepClone();
108         leftChildNLEClone.addChildExps(rightChildNLE.getChildExps());
109         newNode = leftChildNLEClone;
110       } else {
111         // (a | b) & (c & d) ...
112         if (outerOp == Operator.OR) {
113           // (a | b) | (c & d)
114           if (leftChildNLE.getOperator() == Operator.OR
115               && rightChildNLE.getOperator() == Operator.AND) {
116             leftChildNLE.addChildExp(rightChildNLE);
117             newNode = leftChildNLE;
118           } else if (leftChildNLE.getOperator() == Operator.AND
119               && rightChildNLE.getOperator() == Operator.OR) {
120             // (a & b) | (c | d)
121             rightChildNLE.addChildExp(leftChildNLE);
122             newNode = rightChildNLE;
123           }
124           // (a & b) | (c & d)
125           // This case no need to do any thing
126         } else {
127           // outer op is &
128           // (a | b) & (c & d) => (a & c & d) | (b & c & d)
129           if (leftChildNLE.getOperator() == Operator.OR
130               && rightChildNLE.getOperator() == Operator.AND) {
131             newNode = new NonLeafExpressionNode(Operator.OR);
132             for (ExpressionNode exp : leftChildNLE.getChildExps()) {
133               NonLeafExpressionNode rightChildNLEClone = rightChildNLE.deepClone();
134               rightChildNLEClone.addChildExp(exp);
135               newNode.addChildExp(rightChildNLEClone);
136             }
137           } else if (leftChildNLE.getOperator() == Operator.AND
138               && rightChildNLE.getOperator() == Operator.OR) {
139             // (a & b) & (c | d) => (a & b & c) | (a & b & d)
140             newNode = new NonLeafExpressionNode(Operator.OR);
141             for (ExpressionNode exp : rightChildNLE.getChildExps()) {
142               NonLeafExpressionNode leftChildNLEClone = leftChildNLE.deepClone();
143               leftChildNLEClone.addChildExp(exp);
144               newNode.addChildExp(leftChildNLEClone);
145             }
146           } else {
147             // (a | b) & (c | d) => (a & c) | (a & d) | (b & c) | (b & d)
148             newNode = new NonLeafExpressionNode(Operator.OR);
149             for (ExpressionNode leftExp : leftChildNLE.getChildExps()) {
150               for (ExpressionNode rightExp : rightChildNLE.getChildExps()) {
151                 NonLeafExpressionNode newChild = new NonLeafExpressionNode(Operator.AND);
152                 newChild.addChildExp(leftExp.deepClone());
153                 newChild.addChildExp(rightExp.deepClone());
154                 newNode.addChildExp(newChild);
155               }
156             }
157           }
158         }
159       }
160     }
161     return newNode;
162   }
163 
164   private NonLeafExpressionNode mergeChildNodes(NonLeafExpressionNode newOuterNode,
165       Operator outerOp, ExpressionNode lChild, NonLeafExpressionNode nlChild) {
166     // Merge the single right/left node into the other side
167     if (nlChild.getOperator() == outerOp) {
168       NonLeafExpressionNode leftChildNLEClone = nlChild.deepClone();
169       leftChildNLEClone.addChildExp(lChild);
170       newOuterNode = leftChildNLEClone;
171     } else if (outerOp == Operator.AND) {
172       assert nlChild.getOperator() == Operator.OR;
173       // outerOp is & here. We need to expand the node here
174       // (a | b) & c -> (a & c) | (b & c)
175       // OR
176       // c & (a | b) -> (c & a) | (c & b)
177       newOuterNode = new NonLeafExpressionNode(Operator.OR);
178       for (ExpressionNode exp : nlChild.getChildExps()) {
179         newOuterNode.addChildExp(new NonLeafExpressionNode(Operator.AND, exp, lChild));
180       }
181     }
182     return newOuterNode;
183   }
184 }