Merge branch '1.4.5-SNAPSHOT' into 1.5.1-SNAPSHOT
Project: http://git-wip-us.apache.org/repos/asf/accumulo/repo Commit: http://git-wip-us.apache.org/repos/asf/accumulo/commit/8b5f2611 Tree: http://git-wip-us.apache.org/repos/asf/accumulo/tree/8b5f2611 Diff: http://git-wip-us.apache.org/repos/asf/accumulo/diff/8b5f2611 Branch: refs/heads/master Commit: 8b5f261160f9e9c786d2d6ae61eddcebede34c81 Parents: 7f403df d059d00 Author: Mike Drob <md...@mdrob.com> Authored: Mon Nov 11 14:42:02 2013 -0500 Committer: Mike Drob <md...@mdrob.com> Committed: Mon Nov 11 14:42:22 2013 -0500 ---------------------------------------------------------------------- .../accumulo/core/security/ColumnVisibility.java | 13 +++++++++++-- .../accumulo/core/security/ColumnVisibilityTest.java | 7 +++++++ 2 files changed, 18 insertions(+), 2 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/accumulo/blob/8b5f2611/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java ---------------------------------------------------------------------- diff --cc core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java index fe8128e,0000000..7d7daa2 mode 100644,000000..100644 --- a/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java +++ b/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java @@@ -1,499 -1,0 +1,508 @@@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.accumulo.core.security; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; +import java.util.TreeSet; + +import org.apache.accumulo.core.Constants; +import org.apache.accumulo.core.data.ArrayByteSequence; +import org.apache.accumulo.core.data.ByteSequence; +import org.apache.accumulo.core.util.BadArgumentException; +import org.apache.accumulo.core.util.TextUtil; +import org.apache.hadoop.io.Text; +import org.apache.hadoop.io.WritableComparator; + +/** + * Validate the column visibility is a valid expression and set the visibility for a Mutation. See {@link ColumnVisibility#ColumnVisibility(byte[])} for the + * definition of an expression. + */ +public class ColumnVisibility { + + Node node = null; + private byte[] expression; + + /** + * Accessor for the underlying byte string. + * + * @return byte array representation of a visibility expression + */ + public byte[] getExpression() { + return expression; + } + + public static enum NodeType { - TERM, OR, AND, ++ EMPTY, TERM, OR, AND, + } ++ ++ /** ++ * All empty nodes are equal and represent the same value. ++ */ ++ private static final Node EMPTY_NODE = new Node(NodeType.EMPTY); + + public static class Node { + public final static List<Node> EMPTY = Collections.emptyList(); + NodeType type; + int start = 0; + int end = 0; + List<Node> children = EMPTY; + + public Node(NodeType type) { + this.type = type; + } + + public Node(int start, int end) { + this.type = NodeType.TERM; + this.start = start; + this.end = end; + } + + public void add(Node child) { + if (children == EMPTY) + children = new ArrayList<Node>(); + + children.add(child); + } + + public NodeType getType() { + return type; + } + + public List<Node> getChildren() { + return children; + } + + public int getTermStart() { + return start; + } + + public int getTermEnd() { + return end; + } + + public ByteSequence getTerm(byte expression[]) { + if (type != NodeType.TERM) + throw new RuntimeException(); + + if (expression[start] == '"') { + // its a quoted term + int qStart = start + 1; + int qEnd = end - 1; + + return new ArrayByteSequence(expression, qStart, qEnd - qStart); + } + return new ArrayByteSequence(expression, start, end - start); + } + } + + public static class NodeComparator implements Comparator<Node> { + + byte[] text; + + public NodeComparator(byte[] text) { + this.text = text; + } + + @Override + public int compare(Node a, Node b) { + int diff = a.type.ordinal() - b.type.ordinal(); + if (diff != 0) + return diff; + switch (a.type) { ++ case EMPTY: ++ return 0; // All empty nodes are the same + case TERM: + return WritableComparator.compareBytes(text, a.start, a.end - a.start, text, b.start, b.end - b.start); + case OR: + case AND: + diff = a.children.size() - b.children.size(); + if (diff != 0) + return diff; + for (int i = 0; i < a.children.size(); i++) { + diff = compare(a.children.get(i), b.children.get(i)); + if (diff != 0) + return diff; + } + } + return 0; + } + } + + /* + * Convience method that delegates to normalize with a new NodeComparator constructed using the supplied expression. + */ + private static Node normalize(Node root, byte[] expression) { + return normalize(root, expression, new NodeComparator(expression)); + } + + // @formatter:off + /* + * Walks an expression's AST in order to: + * 1) roll up expressions with the same operant (`a&(b&c) becomes a&b&c`) + * 2) sorts labels lexicographically (permutations of `a&b&c` are re-ordered to appear as `a&b&c`) + * 3) dedupes labels (`a&b&a` becomes `a&b`) + */ + // @formatter:on + private static Node normalize(Node root, byte[] expression, NodeComparator comparator) { + if (root.type != NodeType.TERM) { + TreeSet<Node> rolledUp = new TreeSet<Node>(comparator); + java.util.Iterator<Node> itr = root.children.iterator(); + while (itr.hasNext()) { + Node c = normalize(itr.next(), expression, comparator); + if (c.type == root.type) { + rolledUp.addAll(c.children); + itr.remove(); + } + } + rolledUp.addAll(root.children); + root.children.clear(); + root.children.addAll(rolledUp); + + // need to promote a child if it's an only child + if (root.children.size() == 1) { + return root.children.get(0); + } + } + + return root; + } + + /* + * Walks an expression's AST and appends a string representation to a supplied StringBuilder. This method adds parens where necessary. + */ + private static void stringify(Node root, byte[] expression, StringBuilder out) { + if (root.type == NodeType.TERM) { + out.append(new String(expression, root.start, root.end - root.start)); + } else { + String sep = ""; + for (Node c : root.children) { + out.append(sep); + boolean parens = (c.type != NodeType.TERM && root.type != c.type); + if (parens) + out.append("("); + stringify(c, expression, out); + if (parens) + out.append(")"); + sep = root.type == NodeType.AND ? "&" : "|"; + } + } + } + + /** + * Generates a byte[] that represents a normalized, but logically equivalent, form of the supplied expression. + * + * @return normalized expression in byte[] form + */ + public byte[] flatten() { + Node normRoot = normalize(node, expression); + StringBuilder builder = new StringBuilder(expression.length); + stringify(normRoot, expression, builder); + return builder.toString().getBytes(); + } + + private static class ColumnVisibilityParser { + private int index = 0; + private int parens = 0; + + public ColumnVisibilityParser() {} + + Node parse(byte[] expression) { + if (expression.length > 0) { + Node node = parse_(expression); + if (node == null) { + throw new BadArgumentException("operator or missing parens", new String(expression), index - 1); + } + if (parens != 0) { + throw new BadArgumentException("parenthesis mis-match", new String(expression), index - 1); + } + return node; + } + return null; + } + + Node processTerm(int start, int end, Node expr, byte[] expression) { + if (start != end) { + if (expr != null) + throw new BadArgumentException("expression needs | or &", new String(expression), start); + return new Node(start, end); + } + if (expr == null) + throw new BadArgumentException("empty term", new String(expression), start); + return expr; + } + + Node parse_(byte[] expression) { + Node result = null; + Node expr = null; + int termStart = index; + boolean termComplete = false; + + while (index < expression.length) { + switch (expression[index++]) { + case '&': { + expr = processTerm(termStart, index - 1, expr, expression); + if (result != null) { + if (!result.type.equals(NodeType.AND)) + throw new BadArgumentException("cannot mix & and |", new String(expression), index - 1); + } else { + result = new Node(NodeType.AND); + } + result.add(expr); + expr = null; + termStart = index; + termComplete = false; + break; + } + case '|': { + expr = processTerm(termStart, index - 1, expr, expression); + if (result != null) { + if (!result.type.equals(NodeType.OR)) + throw new BadArgumentException("cannot mix | and &", new String(expression), index - 1); + } else { + result = new Node(NodeType.OR); + } + result.add(expr); + expr = null; + termStart = index; + termComplete = false; + break; + } + case '(': { + parens++; + if (termStart != index - 1 || expr != null) + throw new BadArgumentException("expression needs & or |", new String(expression), index - 1); + expr = parse_(expression); + termStart = index; + termComplete = false; + break; + } + case ')': { + parens--; + Node child = processTerm(termStart, index - 1, expr, expression); + if (child == null && result == null) + throw new BadArgumentException("empty expression not allowed", new String(expression), index); + if (result == null) + return child; + if (result.type == child.type) + for (Node c : child.children) + result.add(c); + else + result.add(child); + result.end = index - 1; + return result; + } + case '"': { + if (termStart != index - 1) + throw new BadArgumentException("expression needs & or |", new String(expression), index - 1); + + while (index < expression.length && expression[index] != '"') { + if (expression[index] == '\\') { + index++; + if (expression[index] != '\\' && expression[index] != '"') + throw new BadArgumentException("invalid escaping within quotes", new String(expression), index - 1); + } + index++; + } + + if (index == expression.length) + throw new BadArgumentException("unclosed quote", new String(expression), termStart); + + if (termStart + 1 == index) + throw new BadArgumentException("empty term", new String(expression), termStart); + + index++; + + termComplete = true; + + break; + } + default: { + if (termComplete) + throw new BadArgumentException("expression needs & or |", new String(expression), index - 1); + + byte c = expression[index - 1]; + if (!Authorizations.isValidAuthChar(c)) + throw new BadArgumentException("bad character (" + c + ")", new String(expression), index - 1); + } + } + } + Node child = processTerm(termStart, index, expr, expression); + if (result != null) + result.add(child); + else + result = child; + if (result.type != NodeType.TERM) + if (result.children.size() < 2) + throw new BadArgumentException("missing term", new String(expression), index); + return result; + } + } + + private void validate(byte[] expression) { + if (expression != null && expression.length > 0) { + ColumnVisibilityParser p = new ColumnVisibilityParser(); + node = p.parse(expression); ++ } else { ++ node = EMPTY_NODE; + } + this.expression = expression; + } + + /** + * Empty visibility. Normally, elements with empty visibility can be seen by everyone. Though, one could change this behavior with filters. + * + * @see #ColumnVisibility(String) + */ + public ColumnVisibility() { - expression = new byte[0]; ++ this(new byte[] {}); + } + + /** + * Set the column visibility for a Mutation. + * + * @param expression + * An expression of the rights needed to see this mutation. The expression is a sequence of characters from the set [A-Za-z0-9_-] along with the + * binary operators "&" and "|" indicating that both operands are necessary, or the either is necessary. The following are valid expressions for + * visibility: + * + * <pre> + * A + * A|B + * (A|B)&(C|D) + * orange|(red&yellow) + * + * </pre> + * + * <P> + * The following are not valid expressions for visibility: + * + * <pre> + * A|B&C + * A=B + * A|B| + * A&|B + * () + * ) + * dog|!cat + * </pre> + * + * <P> + * You can use any character you like in your column visibility expression with quoting. If your quoted term contains '"' or '\' then escape + * them with '\'. The {@link #quote(String)} method will properly quote and escape terms for you. + * + * <pre> + * "A#C"<span />&<span />B + * </pre> + * + */ + public ColumnVisibility(String expression) { + this(expression.getBytes(Constants.UTF8)); + } + + /** + * A convenience method for constructing from a string already encoded in UTF-8 bytes and contained in a {@link Text} object. + * + * @see #ColumnVisibility(String) + */ + public ColumnVisibility(Text expression) { + this(TextUtil.getBytes(expression)); + } + + /** + * A convenience method for constructing from a string already encoded in UTF-8 bytes. + * + * @see #ColumnVisibility(String) + */ + public ColumnVisibility(byte[] expression) { + validate(expression); + } + + @Override + public String toString() { + return "[" + new String(expression, Constants.UTF8) + "]"; + } + + /** + * See {@link #equals(ColumnVisibility)} + */ + @Override + public boolean equals(Object obj) { + if (obj instanceof ColumnVisibility) + return equals((ColumnVisibility) obj); + return false; + } + + /** + * Compares two ColumnVisibilities for string equivalence, not as a meaningful comparison of terms and conditions. + */ + public boolean equals(ColumnVisibility otherLe) { + return Arrays.equals(expression, otherLe.expression); + } + + @Override + public int hashCode() { + return Arrays.hashCode(expression); + } + + public Node getParseTree() { + return node; + } + + /** + * Use to properly quote terms in a column visibility expression. If no quoting is needed, then nothing is done. + * + * <p> + * Examples of using quote : + * + * <pre> + * import static org.apache.accumulo.core.security.ColumnVisibility.quote; + * . + * . + * . + * ColumnVisibility cv = new ColumnVisibility(quote("A#C") + "&" + quote("FOO")); + * </pre> + * + */ + public static String quote(String term) { + return new String(quote(term.getBytes(Constants.UTF8)), Constants.UTF8); + } + + /** + * A convenience method to quote terms which are already encoded as UTF-8 bytes. + * + * @see #quote(String) + */ + public static byte[] quote(byte[] term) { + boolean needsQuote = false; + + for (int i = 0; i < term.length; i++) { + if (!Authorizations.isValidAuthChar(term[i])) { + needsQuote = true; + break; + } + } + + if (!needsQuote) + return term; + + return VisibilityEvaluator.escape(term, true); + } +} http://git-wip-us.apache.org/repos/asf/accumulo/blob/8b5f2611/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java ---------------------------------------------------------------------- diff --cc core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java index 97b5265,0000000..6c4e814 mode 100644,000000..100644 --- a/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java +++ b/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java @@@ -1,148 -1,0 +1,155 @@@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.accumulo.core.security; + +import static org.apache.accumulo.core.security.ColumnVisibility.quote; +import static org.junit.Assert.assertArrayEquals; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +import org.junit.Test; + +public class ColumnVisibilityTest { + + private void shouldThrow(String... strings) { + for (String s : strings) + try { + new ColumnVisibility(s.getBytes()); + fail("Should throw: " + s); + } catch (IllegalArgumentException e) { + // expected + } + } + + private void shouldNotThrow(String... strings) { + for (String s : strings) { + new ColumnVisibility(s.getBytes()); + } + } + + @Test + public void testEmpty() { + // empty visibility is valid + new ColumnVisibility(); + new ColumnVisibility(new byte[0]); + } + + @Test ++ public void testEmptyFlatten() { ++ // empty visibility is valid ++ new ColumnVisibility().flatten(); ++ new ColumnVisibility("").flatten(); ++ } ++ ++ @Test + public void testSimple() { + shouldNotThrow("test", "(one)"); + } + + @Test + public void testCompound() { + shouldNotThrow("a|b", "a&b", "ab&bc"); + shouldNotThrow("A&B&C&D&E", "A|B|C|D|E", "(A|B|C)", "(A)|B|(C)", "A&(B)&(C)", "A&B&(L)"); + shouldNotThrow("_&-&:"); + } + + @Test + public void testBadCharacters() { + shouldThrow("=", "*", "^", "%", "@"); + shouldThrow("a*b"); + } + + public void normalized(String... values) { + for (int i = 0; i < values.length; i += 2) { + ColumnVisibility cv = new ColumnVisibility(values[i].getBytes()); + assertArrayEquals(cv.flatten(), values[i + 1].getBytes()); + } + } + + @Test + public void testComplexCompound() { + shouldNotThrow("(a|b)&(x|y)"); + shouldNotThrow("a&(x|y)", "(a|b)&(x|y)", "A&(L|M)", "B&(L|M)", "A&B&(L|M)"); + shouldNotThrow("A&FOO&(L|M)", "(A|B)&FOO&(L|M)", "A&B&(L|M|FOO)", "((A|B|C)|foo)&bar"); + shouldNotThrow("(one&two)|(foo&bar)", "(one|foo)&three", "one|foo|bar", "(one|foo)|bar", "((one|foo)|bar)&two"); + } + + @Test + public void testNormalization() { + normalized("a", "a", "(a)", "a", "b|a", "a|b", "(b)|a", "a|b", "(b|(a|c))&x", "x&(a|b|c)", "(((a)))", "a"); + final String normForm = "a&b&c"; + normalized("b&c&a", normForm, "c&b&a", normForm, "a&(b&c)", normForm, "(a&c)&b", normForm); + + // this an expression that's basically `expr | expr` + normalized("(d&c&b&a)|(b&c&a&d)", "a&b&c&d"); + } + + @Test + public void testDanglingOperators() { + shouldThrow("a|b&"); + shouldThrow("(|a)"); + shouldThrow("|"); + shouldThrow("a|", "|a", "|", "&"); + shouldThrow("&(five)", "|(five)", "(five)&", "five|", "a|(b)&", "(&five)", "(five|)"); + } + + @Test + public void testMissingSeparators() { + shouldThrow("one(five)", "(five)one", "(one)(two)", "a|(b(c))"); + } + + @Test + public void testMismatchedParentheses() { + shouldThrow("(", ")", "(a&b", "b|a)", "A|B)"); + } + + @Test + public void testMixedOperators() { + shouldThrow("(A&B)|(C&D)&(E)"); + shouldThrow("a|b&c", "A&B&C|D", "(A&B)|(C&D)&(E)"); + } + + @Test + public void testQuotes() { + shouldThrow("\"\""); + shouldThrow("\"A\"A"); + shouldThrow("\"A\"\"B\""); + shouldThrow("(A)\"B\""); + shouldThrow("\"A\"(B)"); + shouldThrow("\"A"); + shouldThrow("\""); + shouldThrow("\"B"); + shouldThrow("A&\"B"); + shouldThrow("A&\"B\\'"); + + shouldNotThrow("\"A\""); + shouldNotThrow("(\"A\")"); + shouldNotThrow("A&\"B.D\""); + shouldNotThrow("A&\"B\\\\D\""); + shouldNotThrow("A&\"B\\\"D\""); + } + + @Test + public void testToString() { + ColumnVisibility cv = new ColumnVisibility(quote("a")); + assertEquals("[a]", cv.toString()); + + // multi-byte + cv = new ColumnVisibility(quote("äº")); + assertEquals("[\"äº\"]", cv.toString()); + } +}
