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.util.List;
021
022import org.apache.yetus.audience.InterfaceAudience;
023import org.apache.hadoop.hbase.security.visibility.expression.ExpressionNode;
024import org.apache.hadoop.hbase.security.visibility.expression.LeafExpressionNode;
025import org.apache.hadoop.hbase.security.visibility.expression.NonLeafExpressionNode;
026import org.apache.hadoop.hbase.security.visibility.expression.Operator;
027
028@InterfaceAudience.Private
029public class ExpressionExpander {
030
031  public ExpressionNode expand(ExpressionNode src) {
032    if (!src.isSingleNode()) {
033      NonLeafExpressionNode nlExp = (NonLeafExpressionNode) src;
034      List<ExpressionNode> childExps = nlExp.getChildExps();
035      Operator outerOp = nlExp.getOperator();
036      if (isToBeExpanded(childExps)) {
037        // Any of the child exp is a non leaf exp with & or | operator
038        NonLeafExpressionNode newNode = new NonLeafExpressionNode(nlExp.getOperator());
039        for (ExpressionNode exp : childExps) {
040          if (exp.isSingleNode()) {
041            newNode.addChildExp(exp);
042          } else {
043            newNode.addChildExp(expand(exp));
044          }
045        }
046        nlExp = expandNonLeaf(newNode, outerOp);
047      }
048      return nlExp;
049    }
050    if (src instanceof NonLeafExpressionNode
051        && ((NonLeafExpressionNode) src).getOperator() == Operator.NOT) {
052      // Negate the exp
053      return negate((NonLeafExpressionNode) src);
054    }
055    return src;
056  }
057
058  private ExpressionNode negate(NonLeafExpressionNode nlExp) {
059    ExpressionNode notChild = nlExp.getChildExps().get(0);
060    if (notChild instanceof LeafExpressionNode) {
061      return nlExp;
062    }
063    NonLeafExpressionNode nlNotChild = (NonLeafExpressionNode) notChild;
064    if (nlNotChild.getOperator() == Operator.NOT) {
065      // negate the negate
066      return nlNotChild.getChildExps().get(0);
067    }
068    Operator negateOp = nlNotChild.getOperator() == Operator.AND ? Operator.OR : Operator.AND;
069    NonLeafExpressionNode newNode = new NonLeafExpressionNode(negateOp);
070    for (ExpressionNode expNode : nlNotChild.getChildExps()) {
071      NonLeafExpressionNode negateNode = new NonLeafExpressionNode(Operator.NOT);
072      negateNode.addChildExp(expNode.deepClone());
073      newNode.addChildExp(expand(negateNode));
074    }
075    return newNode;
076  }
077
078  private boolean isToBeExpanded(List<ExpressionNode> childExps) {
079    for (ExpressionNode exp : childExps) {
080      if (!exp.isSingleNode()) {
081        return true;
082      }
083    }
084    return false;
085  }
086
087  private NonLeafExpressionNode expandNonLeaf(NonLeafExpressionNode newNode, Operator outerOp) {
088    // Now go for the merge or expansion across brackets
089    List<ExpressionNode> newChildExps = newNode.getChildExps();
090    assert newChildExps.size() == 2;
091    ExpressionNode leftChild = newChildExps.get(0);
092    ExpressionNode rightChild = newChildExps.get(1);
093    if (rightChild.isSingleNode()) {
094      // Merge the single right node into the left side
095      assert leftChild instanceof NonLeafExpressionNode;
096      newNode = mergeChildNodes(newNode, outerOp, rightChild, (NonLeafExpressionNode) leftChild);
097    } else if (leftChild.isSingleNode()) {
098      // Merge the single left node into the right side
099      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}