You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@accumulo.apache.org by md...@apache.org on 2013/11/11 20:49:53 UTC
[05/10] git commit: Merge branch '1.4.5-SNAPSHOT' into 1.5.1-SNAPSHOT
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/1.6.0-SNAPSHOT
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());
+ }
+}