svn commit: r1412448 - in /accumulo/trunk/core/src: main/java/org/apache/accumulo/core/security/ColumnVisibility.java test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java

[uj...@apache.org]

Author: ujustgotbilld
Date: Thu Nov 22 08:38:46 2012
New Revision: 1412448

URL: http://svn.apache.org/viewvc?rev=1412448&view=rev
Log:
ACCUMULO-871

Updated the ColumnVisibility class to be more aggressive and consistent when flattening/normalizing expressions. Labels are dedupe'd and sorted and equivalent subtrees are pruned.


Modified:
    accumulo/trunk/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java
    accumulo/trunk/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java

Modified: accumulo/trunk/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java
URL: http://svn.apache.org/viewvc/accumulo/trunk/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java?rev=1412448&r1=1412447&r2=1412448&view=diff
==============================================================================
--- accumulo/trunk/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java (original)
+++ accumulo/trunk/core/src/main/java/org/apache/accumulo/core/security/ColumnVisibility.java Thu Nov 22 08:38:46 2012
@@ -22,6 +22,7 @@ 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.data.ArrayByteSequence;
 import org.apache.accumulo.core.data.ByteSequence;
@@ -137,31 +138,77 @@ public class ColumnVisibility {
       return 0;
     }
   }
-  
-  static private void flatten(Node root, byte[] expression, StringBuilder out) {
-    if (root.type == NodeType.TERM)
+
+  /* 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));
+  } 
+
+  /* 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`)
+   */
+  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 = "";
-      Collections.sort(root.children, new NodeComparator(expression));
       for (Node c : root.children) {
         out.append(sep);
         boolean parens = (c.type != NodeType.TERM && root.type != c.type);
         if (parens)
           out.append("(");
-        flatten(c, expression, out);
+        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() {
-    StringBuilder builder = new StringBuilder();
-    flatten(node, expression, builder);
+    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;

Modified: accumulo/trunk/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java
URL: http://svn.apache.org/viewvc/accumulo/trunk/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java?rev=1412448&r1=1412447&r2=1412448&view=diff
==============================================================================
--- accumulo/trunk/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java (original)
+++ accumulo/trunk/core/src/test/java/org/apache/accumulo/core/security/ColumnVisibilityTest.java Thu Nov 22 08:38:46 2012
@@ -82,6 +82,11 @@ public class ColumnVisibilityTest {
   @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