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.List;
21
22 import org.apache.hadoop.hbase.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
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
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
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
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
95 assert leftChild instanceof NonLeafExpressionNode;
96 newNode = mergeChildNodes(newNode, outerOp, rightChild, (NonLeafExpressionNode) leftChild);
97 } else if (leftChild.isSingleNode()) {
98
99 assert rightChild instanceof NonLeafExpressionNode;
100 newNode = mergeChildNodes(newNode, outerOp, leftChild, (NonLeafExpressionNode) rightChild);
101 } else {
102
103 NonLeafExpressionNode leftChildNLE = (NonLeafExpressionNode) leftChild;
104 NonLeafExpressionNode rightChildNLE = (NonLeafExpressionNode) rightChild;
105 if (outerOp == leftChildNLE.getOperator() && outerOp == rightChildNLE.getOperator()) {
106
107 NonLeafExpressionNode leftChildNLEClone = leftChildNLE.deepClone();
108 leftChildNLEClone.addChildExps(rightChildNLE.getChildExps());
109 newNode = leftChildNLEClone;
110 } else {
111
112 if (outerOp == Operator.OR) {
113
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
121 rightChildNLE.addChildExp(leftChildNLE);
122 newNode = rightChildNLE;
123 }
124
125
126 } else {
127
128
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
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
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
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
174
175
176
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 }