You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@rya.apache.org by ca...@apache.org on 2018/01/09 21:48:31 UTC
[14/50] [abbrv] incubator-rya git commit: RYA-377 Abstract Join into
api.function
RYA-377 Abstract Join into api.function
Moved Join interfaces out of fluo
Refactored fluo to use the new interfaces
Copied visibility flattening code from accumulo
Project: http://git-wip-us.apache.org/repos/asf/incubator-rya/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-rya/commit/0ad2c511
Tree: http://git-wip-us.apache.org/repos/asf/incubator-rya/tree/0ad2c511
Diff: http://git-wip-us.apache.org/repos/asf/incubator-rya/diff/0ad2c511
Branch: refs/heads/master
Commit: 0ad2c511b107cbdba6445693e72fb6f7c700b431
Parents: 516e890
Author: Andrew Smith <sm...@gmail.com>
Authored: Tue Nov 7 12:56:39 2017 -0500
Committer: caleb <ca...@parsons.com>
Committed: Tue Jan 9 15:13:00 2018 -0500
----------------------------------------------------------------------
common/pom.xml | 1 +
common/rya.api.function/pom.xml | 56 ++
.../rya/api/function/join/IterativeJoin.java | 49 ++
.../api/function/join/LazyJoiningIterator.java | 110 ++++
.../rya/api/function/join/LeftOuterJoin.java | 71 +++
.../rya/api/function/join/NaturalJoin.java | 62 +++
.../api/function/join/IterativeJoinTest.java | 85 +++
.../api/function/join/LeftOuterJoinTest.java | 179 ++++++
.../rya/api/function/join/NaturalJoinTest.java | 169 ++++++
common/rya.api.model/pom.xml | 5 +-
.../api/model/visibility/ArrayByteSequence.java | 143 +++++
.../api/model/visibility/Authorizations.java | 77 +++
.../model/visibility/BadArgumentException.java | 42 ++
.../rya/api/model/visibility/ByteSequence.java | 114 ++++
.../api/model/visibility/ColumnVisibility.java | 551 +++++++++++++++++++
.../model/visibility/FastByteComparison.java | 240 ++++++++
.../model/visibility/VisibilitySimplifier.java | 89 +++
.../model/visibility/WritableComparator.java | 53 ++
.../visibility/VisibilitySimplifierTest.java | 91 +++
extras/rya.pcj.fluo/pcj.fluo.app/pom.xml | 5 +
.../pcj/fluo/app/JoinResultUpdater.java | 244 ++------
.../app/batch/JoinBatchBindingSetUpdater.java | 44 +-
.../fluo/app/batch/JoinBatchInformation.java | 34 +-
.../JoinBatchInformationTypeAdapter.java | 42 +-
.../pcj/fluo/app/export/ExporterManager.java | 66 +--
.../pcj/fluo/app/IterativeJoinTest.java | 88 ---
.../pcj/fluo/app/LeftOuterJoinTest.java | 181 ------
.../indexing/pcj/fluo/app/NaturalJoinTest.java | 171 ------
.../BatchInformationSerializerTest.java | 2 +-
.../indexing/pcj/fluo/integration/BatchIT.java | 2 +-
pom.xml | 5 +
31 files changed, 2327 insertions(+), 744 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/pom.xml
----------------------------------------------------------------------
diff --git a/common/pom.xml b/common/pom.xml
index 8106cf5..3767caa 100644
--- a/common/pom.xml
+++ b/common/pom.xml
@@ -35,6 +35,7 @@ under the License.
<modules>
<module>rya.api</module>
<module>rya.api.model</module>
+ <module>rya.api.function</module>
<module>rya.provenance</module>
</modules>
</project>
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/pom.xml
----------------------------------------------------------------------
diff --git a/common/rya.api.function/pom.xml b/common/rya.api.function/pom.xml
new file mode 100644
index 0000000..f05dd6f
--- /dev/null
+++ b/common/rya.api.function/pom.xml
@@ -0,0 +1,56 @@
+<?xml version="1.0" encoding="UTF-8"?>
+
+<!--
+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.
+-->
+
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <parent>
+ <groupId>org.apache.rya</groupId>
+ <artifactId>rya.common</artifactId>
+ <version>3.2.12-incubating-SNAPSHOT</version>
+ </parent>
+
+ <artifactId>rya.api.function</artifactId>
+ <name>Apache Rya Common API - Functions</name>
+
+ <dependencies>
+ <dependency>
+ <groupId>org.apache.rya</groupId>
+ <artifactId>rya.api.model</artifactId>
+ </dependency>
+
+ <!-- Third Party Dependencies -->
+ <dependency>
+ <groupId>com.google.guava</groupId>
+ <artifactId>guava</artifactId>
+ </dependency>
+
+ <dependency>
+ <groupId>com.github.stephenc.findbugs</groupId>
+ <artifactId>findbugs-annotations</artifactId>
+ </dependency>
+
+ <dependency>
+ <groupId>junit</groupId>
+ <artifactId>junit</artifactId>
+ <scope>test</scope>
+ </dependency>
+ </dependencies>
+</project>
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/IterativeJoin.java
----------------------------------------------------------------------
diff --git a/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/IterativeJoin.java b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/IterativeJoin.java
new file mode 100644
index 0000000..d667fc9
--- /dev/null
+++ b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/IterativeJoin.java
@@ -0,0 +1,49 @@
+/*
+ * 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.rya.api.function.join;
+
+import java.util.Iterator;
+
+import org.apache.rya.api.model.VisibilityBindingSet;
+
+/**
+ * Defines each of the cases that may generate new join results when iteratively computing a query's join node.
+ */
+public interface IterativeJoin {
+
+ /**
+ * Invoked when a new {@link VisibilityBindingSet} is emitted from the left child
+ * node of the join.
+ *
+ * @param newLeftResult - A new VisibilityBindingSet that has been emitted from the left child node.
+ * @param rightResults - The right child node's binding sets that will be joined with the new left result. (not null)
+ * @return The new BindingSet results for the join.
+ */
+ public Iterator<VisibilityBindingSet> newLeftResult(VisibilityBindingSet newLeftResult, Iterator<VisibilityBindingSet> rightResults);
+
+ /**
+ * Invoked when a new {@link VisibilityBindingSet} is emitted from the right child
+ * node of the join.
+ *
+ * @param leftResults - The left child node's binding sets that will be joined with the new right result.
+ * @param newRightResult - A new BindingSet that has been emitted from the right child node.
+ * @return The new BindingSet results for the join.
+ */
+ public Iterator<VisibilityBindingSet> newRightResult(Iterator<VisibilityBindingSet> leftResults, VisibilityBindingSet newRightResult);
+}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LazyJoiningIterator.java
----------------------------------------------------------------------
diff --git a/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LazyJoiningIterator.java b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LazyJoiningIterator.java
new file mode 100644
index 0000000..b504a7e
--- /dev/null
+++ b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LazyJoiningIterator.java
@@ -0,0 +1,110 @@
+/*
+ * 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.rya.api.function.join;
+
+import static java.util.Objects.requireNonNull;
+
+import java.util.Iterator;
+
+import org.apache.rya.api.model.VisibilityBindingSet;
+import org.apache.rya.api.model.visibility.VisibilitySimplifier;
+import org.openrdf.query.Binding;
+import org.openrdf.query.BindingSet;
+import org.openrdf.query.impl.MapBindingSet;
+
+import edu.umd.cs.findbugs.annotations.DefaultAnnotation;
+import edu.umd.cs.findbugs.annotations.NonNull;
+
+/**
+ * Joins a {@link BindingSet} (which is new to the left or right side of a join)
+ * to all binding sets on the other side that join with it.
+ * <p>
+ * This is done lazily so that you don't have to load all of the BindingSets
+ * into memory at once.
+ */
+@DefaultAnnotation(NonNull.class)
+public final class LazyJoiningIterator implements Iterator<VisibilityBindingSet> {
+ private final Side newResultSide;
+ private final VisibilityBindingSet newResult;
+ private final Iterator<VisibilityBindingSet> joinedResults;
+
+ /**
+ * Constructs an instance of {@link LazyJoiningIterator}.
+ *
+ * @param newResultSide - Indicates which side of the join the
+ * {@code newResult} arrived on. (not null)
+ * @param newResult - A binding set that will be joined with some other
+ * binding sets. (not null)
+ * @param joinedResults - The binding sets that will be joined with
+ * {@code newResult}. (not null)
+ */
+ public LazyJoiningIterator(final Side newResultSide, final VisibilityBindingSet newResult,
+ final Iterator<VisibilityBindingSet> joinedResults) {
+ this.newResultSide = requireNonNull(newResultSide);
+ this.newResult = requireNonNull(newResult);
+ this.joinedResults = requireNonNull(joinedResults);
+ }
+
+ @Override
+ public boolean hasNext() {
+ return joinedResults.hasNext();
+ }
+
+ @Override
+ public VisibilityBindingSet next() {
+ final MapBindingSet bs = new MapBindingSet();
+
+ for (final Binding binding : newResult) {
+ bs.addBinding(binding);
+ }
+
+ final VisibilityBindingSet joinResult = joinedResults.next();
+ for (final Binding binding : joinResult) {
+ bs.addBinding(binding);
+ }
+
+ // We want to make sure the visibilities are always written the same way,
+ // so figure out which are on the left side and which are on the right side.
+ final String leftVisi;
+ final String rightVisi;
+ if (newResultSide == Side.LEFT) {
+ leftVisi = newResult.getVisibility();
+ rightVisi = joinResult.getVisibility();
+ } else {
+ leftVisi = joinResult.getVisibility();
+ rightVisi = newResult.getVisibility();
+ }
+
+ final String visibility = VisibilitySimplifier.unionAndSimplify(leftVisi, rightVisi);
+
+ return new VisibilityBindingSet(bs, visibility);
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("remove() is unsupported.");
+ }
+
+ /**
+ * The different sides a new binding set may appear on.
+ */
+ public static enum Side {
+ LEFT, RIGHT;
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LeftOuterJoin.java
----------------------------------------------------------------------
diff --git a/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LeftOuterJoin.java b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LeftOuterJoin.java
new file mode 100644
index 0000000..79af26c
--- /dev/null
+++ b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/LeftOuterJoin.java
@@ -0,0 +1,71 @@
+/*
+ * 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.rya.api.function.join;
+
+import static java.util.Objects.requireNonNull;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.apache.rya.api.function.join.LazyJoiningIterator.Side;
+import org.apache.rya.api.model.VisibilityBindingSet;
+import org.openrdf.query.BindingSet;
+
+import edu.umd.cs.findbugs.annotations.DefaultAnnotation;
+import edu.umd.cs.findbugs.annotations.NonNull;
+
+/**
+ * Implements an {@link IterativeJoin} that uses the Left Outer Join
+ * algorithm defined by Relational Algebra.
+ * <p>
+ * This is how you add optional information to a {@link BindingSet}. Left
+ * binding sets are emitted even if they do not join with anything on the right.
+ * However, right binding sets must be joined with a left binding set.
+ */
+@DefaultAnnotation(NonNull.class)
+public final class LeftOuterJoin implements IterativeJoin {
+ @Override
+ public Iterator<VisibilityBindingSet> newLeftResult(final VisibilityBindingSet newLeftResult, final Iterator<VisibilityBindingSet> rightResults) {
+ requireNonNull(newLeftResult);
+ requireNonNull(rightResults);
+
+ // If the required portion does not join with any optional portions,
+ // then emit a BindingSet that matches the new left result.
+ if(!rightResults.hasNext()) {
+ final List<VisibilityBindingSet> leftResultList = new ArrayList<>();
+ leftResultList.add(newLeftResult);
+ return leftResultList.iterator();
+ }
+
+ // Otherwise, return an iterator that holds the new required result
+ // joined with the right results.
+ return new LazyJoiningIterator(Side.LEFT, newLeftResult, rightResults);
+ }
+
+ @Override
+ public Iterator<VisibilityBindingSet> newRightResult(final Iterator<VisibilityBindingSet> leftResults, final VisibilityBindingSet newRightResult) {
+ requireNonNull(leftResults);
+ requireNonNull(newRightResult);
+
+ // The right result is optional, so if it does not join with anything
+ // on the left, then do not emit anything.
+ return new LazyJoiningIterator(Side.RIGHT, newRightResult, leftResults);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/NaturalJoin.java
----------------------------------------------------------------------
diff --git a/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/NaturalJoin.java b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/NaturalJoin.java
new file mode 100644
index 0000000..2db6ba4
--- /dev/null
+++ b/common/rya.api.function/src/main/java/org/apache/rya/api/function/join/NaturalJoin.java
@@ -0,0 +1,62 @@
+/*
+ * 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.rya.api.function.join;
+
+import static java.util.Objects.requireNonNull;
+
+import java.util.Iterator;
+
+import org.apache.rya.api.function.join.LazyJoiningIterator.Side;
+import org.apache.rya.api.model.VisibilityBindingSet;
+
+import edu.umd.cs.findbugs.annotations.DefaultAnnotation;
+import edu.umd.cs.findbugs.annotations.NonNull;
+
+/**
+ * Implements an {@link IterativeJoin} that uses the Natural Join algorithm
+ * defined by Relational Algebra.
+ * <p>
+ * This is how you combine {@code BindnigSet}s that may have common Binding
+ * names. When two Binding Sets are joined, any bindings that appear in both
+ * binding sets are only included once.
+ */
+@DefaultAnnotation(NonNull.class)
+public class NaturalJoin implements IterativeJoin {
+ @Override
+ public Iterator<VisibilityBindingSet> newLeftResult(final VisibilityBindingSet newLeftResult,
+ final Iterator<VisibilityBindingSet> rightResults) {
+ requireNonNull(newLeftResult);
+ requireNonNull(rightResults);
+
+ // Both sides are required, so if there are no right results, then do
+ // not emit anything.
+ return new LazyJoiningIterator(Side.LEFT, newLeftResult, rightResults);
+ }
+
+ @Override
+ public Iterator<VisibilityBindingSet> newRightResult(final Iterator<VisibilityBindingSet> leftResults,
+ final VisibilityBindingSet newRightResult) {
+ requireNonNull(leftResults);
+ requireNonNull(newRightResult);
+
+ // Both sides are required, so if there are no left reuslts, then do not
+ // emit anything.
+ return new LazyJoiningIterator(Side.RIGHT, newRightResult, leftResults);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/IterativeJoinTest.java
----------------------------------------------------------------------
diff --git a/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/IterativeJoinTest.java b/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/IterativeJoinTest.java
new file mode 100644
index 0000000..5d357c3
--- /dev/null
+++ b/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/IterativeJoinTest.java
@@ -0,0 +1,85 @@
+/*
+ * 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.rya.api.function.join;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+
+import org.apache.rya.api.model.VisibilityBindingSet;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+import org.openrdf.model.ValueFactory;
+import org.openrdf.model.impl.ValueFactoryImpl;
+import org.openrdf.query.impl.MapBindingSet;
+
+/**
+ * Tests the methods of {@link IterativeJoin}.
+ */
+@RunWith(Parameterized.class)
+public class IterativeJoinTest {
+
+ @Parameters
+ public static Collection<Object[]> data() {
+ return Arrays.asList(new Object[][] {
+ {new NaturalJoin()},
+ {new LeftOuterJoin()}
+ });
+ }
+
+ @Parameter
+ public IterativeJoin join;
+
+ /**
+ * This test ensures the same binding sets are created as the result of a
+ * {@link IterativeJoin} regardless of which side the notification is triggered on.
+ */
+ @Test
+ public void naturalJoin_sideDoesNotMatter() {
+ // Create the binding sets that will be joined.
+ final ValueFactory vf = new ValueFactoryImpl();
+
+ final MapBindingSet bs1 = new MapBindingSet();
+ bs1.addBinding("id", vf.createLiteral("some_uid"));
+ bs1.addBinding("name", vf.createLiteral("Alice"));
+ final VisibilityBindingSet vbs1 = new VisibilityBindingSet(bs1, "a");
+
+ final MapBindingSet bs2 = new MapBindingSet();
+ bs2.addBinding("id", vf.createLiteral("some_uid"));
+ bs2.addBinding("hair", vf.createLiteral("brown"));
+ final VisibilityBindingSet vbs2 = new VisibilityBindingSet(bs2, "b");
+
+ // new vbs1 shows up on the left, matches vbs2 on the right
+ final Iterator<VisibilityBindingSet> newLeftIt = join.newLeftResult(vbs1, Collections.singleton(vbs2).iterator());
+ final VisibilityBindingSet newLeftResult = newLeftIt.next();
+
+ // new vbs2 shows up on the right, matches vbs1 on the left
+ final Iterator<VisibilityBindingSet> newRightIt = join.newRightResult(Collections.singleton(vbs1).iterator(), vbs2);
+ final VisibilityBindingSet newRightResult = newRightIt.next();
+
+ // Ensure those two results are the same.
+ assertEquals(newLeftResult, newRightResult);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/LeftOuterJoinTest.java
----------------------------------------------------------------------
diff --git a/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/LeftOuterJoinTest.java b/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/LeftOuterJoinTest.java
new file mode 100644
index 0000000..7d17e22
--- /dev/null
+++ b/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/LeftOuterJoinTest.java
@@ -0,0 +1,179 @@
+/*
+ * 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.rya.api.function.join;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+import org.apache.rya.api.model.VisibilityBindingSet;
+import org.junit.Test;
+import org.openrdf.model.ValueFactory;
+import org.openrdf.model.impl.ValueFactoryImpl;
+import org.openrdf.query.BindingSet;
+import org.openrdf.query.impl.MapBindingSet;
+
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+
+/**
+ * Tests the methods of {@link LeftOuterJoin}.
+ */
+public class LeftOuterJoinTest {
+
+ private final ValueFactory vf = new ValueFactoryImpl();
+
+ @Test
+ public void newLeftResult_noRightMatches() {
+ final IterativeJoin leftOuterJoin = new LeftOuterJoin();
+
+ // There is a new left result.
+ final MapBindingSet mapLeftResult = new MapBindingSet();
+ mapLeftResult.addBinding("name", vf.createLiteral("Bob"));
+ final VisibilityBindingSet newLeftResult = new VisibilityBindingSet(mapLeftResult);
+
+ // There are no right results that join with the left result.
+ final Iterator<VisibilityBindingSet> rightResults= new ArrayList<VisibilityBindingSet>().iterator();
+
+ // Therefore, the left result is a new join result.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = leftOuterJoin.newLeftResult(newLeftResult, rightResults);
+
+ final Set<BindingSet> newJoinResults = new HashSet<>();
+ while(newJoinResultsIt.hasNext()) {
+ newJoinResults.add( newJoinResultsIt.next() );
+ }
+
+ final Set<BindingSet> expected = Sets.<BindingSet>newHashSet( newLeftResult );
+
+ assertEquals(expected, newJoinResults);
+ }
+
+ @Test
+ public void newLeftResult_joinsWithRightResults() {
+ final IterativeJoin leftOuterJoin = new LeftOuterJoin();
+
+ // There is a new left result.
+ final MapBindingSet mapLeftResult = new MapBindingSet();
+ mapLeftResult.addBinding("name", vf.createLiteral("Bob"));
+ mapLeftResult.addBinding("height", vf.createLiteral("5'9\""));
+ final VisibilityBindingSet newLeftResult = new VisibilityBindingSet(mapLeftResult);
+
+ // There are a few right results that join with the left result.
+ final MapBindingSet nameAge = new MapBindingSet();
+ nameAge.addBinding("name", vf.createLiteral("Bob"));
+ nameAge.addBinding("age", vf.createLiteral(56));
+ final VisibilityBindingSet visiAge = new VisibilityBindingSet(nameAge);
+
+ final MapBindingSet nameHair = new MapBindingSet();
+ nameHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHair.addBinding("hairColor", vf.createLiteral("Brown"));
+ final VisibilityBindingSet visiHair = new VisibilityBindingSet(nameHair);
+
+ final Iterator<VisibilityBindingSet> rightResults = Lists.<VisibilityBindingSet>newArrayList(visiAge, visiHair).iterator();
+
+ // Therefore, there are a few new join results that mix the two together.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = leftOuterJoin.newLeftResult(newLeftResult, rightResults);
+
+ final Set<BindingSet> newJoinResults = new HashSet<>();
+ while(newJoinResultsIt.hasNext()) {
+ newJoinResults.add( newJoinResultsIt.next() );
+ }
+
+ final Set<BindingSet> expected = Sets.<BindingSet>newHashSet();
+ final MapBindingSet nameHeightAge = new MapBindingSet();
+ nameHeightAge.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightAge.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightAge.addBinding("age", vf.createLiteral(56));
+ expected.add(new VisibilityBindingSet(nameHeightAge));
+
+ final MapBindingSet nameHeightHair = new MapBindingSet();
+ nameHeightHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightHair.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightHair.addBinding("hairColor", vf.createLiteral("Brown"));
+ expected.add(new VisibilityBindingSet(nameHeightHair));
+
+ assertEquals(expected, newJoinResults);
+ }
+
+ @Test
+ public void newRightResult_noLeftMatches() {
+ final IterativeJoin leftOuterJoin = new LeftOuterJoin();
+
+ // There are no left results.
+ final Iterator<VisibilityBindingSet> leftResults= new ArrayList<VisibilityBindingSet>().iterator();
+
+ // There is a new right result.
+ final MapBindingSet newRightResult = new MapBindingSet();
+ newRightResult.addBinding("name", vf.createLiteral("Bob"));
+
+ // Therefore, there are no new join results.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = leftOuterJoin.newRightResult(leftResults, new VisibilityBindingSet(newRightResult));
+ assertFalse( newJoinResultsIt.hasNext() );
+ }
+
+ @Test
+ public void newRightResult_joinsWithLeftResults() {
+ final IterativeJoin leftOuterJoin = new LeftOuterJoin();
+
+ // There are a few left results that join with the new right result.
+ final MapBindingSet nameAge = new MapBindingSet();
+ nameAge.addBinding("name", vf.createLiteral("Bob"));
+ nameAge.addBinding("age", vf.createLiteral(56));
+
+ final MapBindingSet nameHair = new MapBindingSet();
+ nameHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHair.addBinding("hairColor", vf.createLiteral("Brown"));
+
+ final Iterator<VisibilityBindingSet> leftResults = Lists.<VisibilityBindingSet>newArrayList(
+ new VisibilityBindingSet(nameAge),
+ new VisibilityBindingSet(nameHair)).iterator();
+
+ // There is a new right result.
+ final MapBindingSet newRightResult = new MapBindingSet();
+ newRightResult.addBinding("name", vf.createLiteral("Bob"));
+ newRightResult.addBinding("height", vf.createLiteral("5'9\""));
+
+ // Therefore, there are a few new join results that mix the two together.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = leftOuterJoin.newRightResult(leftResults, new VisibilityBindingSet(newRightResult));
+
+ final Set<BindingSet> newJoinResults = new HashSet<>();
+ while(newJoinResultsIt.hasNext()) {
+ newJoinResults.add( newJoinResultsIt.next() );
+ }
+
+ final Set<BindingSet> expected = Sets.<BindingSet>newHashSet();
+ final MapBindingSet nameHeightAge = new MapBindingSet();
+ nameHeightAge.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightAge.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightAge.addBinding("age", vf.createLiteral(56));
+ expected.add(new VisibilityBindingSet(nameHeightAge));
+
+ final MapBindingSet nameHeightHair = new MapBindingSet();
+ nameHeightHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightHair.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightHair.addBinding("hairColor", vf.createLiteral("Brown"));
+ expected.add(new VisibilityBindingSet(nameHeightHair));
+
+ assertEquals(expected, newJoinResults);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/NaturalJoinTest.java
----------------------------------------------------------------------
diff --git a/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/NaturalJoinTest.java b/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/NaturalJoinTest.java
new file mode 100644
index 0000000..dd3b7e6
--- /dev/null
+++ b/common/rya.api.function/src/main/test/org/apache/rya/api/function/join/NaturalJoinTest.java
@@ -0,0 +1,169 @@
+/*
+ * 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.rya.api.function.join;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+
+import org.apache.rya.api.model.VisibilityBindingSet;
+import org.junit.Test;
+import org.openrdf.model.ValueFactory;
+import org.openrdf.model.impl.ValueFactoryImpl;
+import org.openrdf.query.BindingSet;
+import org.openrdf.query.impl.MapBindingSet;
+
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+
+/**
+ * Tests the methods of {@link NaturalJoin}.
+ */
+public class NaturalJoinTest {
+
+ private final ValueFactory vf = new ValueFactoryImpl();
+
+ @Test
+ public void newLeftResult_noRightMatches() {
+ final IterativeJoin naturalJoin = new NaturalJoin();
+
+ // There is a new left result.
+ final MapBindingSet newLeftResult = new MapBindingSet();
+ newLeftResult.addBinding("name", vf.createLiteral("Bob"));
+
+ // There are no right results that join with the left result.
+ final Iterator<VisibilityBindingSet> rightResults= new ArrayList<VisibilityBindingSet>().iterator();
+
+ // Therefore, the left result is a new join result.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = naturalJoin.newLeftResult(new VisibilityBindingSet(newLeftResult), rightResults);
+ assertFalse( newJoinResultsIt.hasNext() );
+ }
+
+ @Test
+ public void newLeftResult_joinsWithRightResults() {
+ final IterativeJoin naturalJoin = new NaturalJoin();
+
+ // There is a new left result.
+ final MapBindingSet newLeftResult = new MapBindingSet();
+ newLeftResult.addBinding("name", vf.createLiteral("Bob"));
+ newLeftResult.addBinding("height", vf.createLiteral("5'9\""));
+
+ // There are a few right results that join with the left result.
+ final MapBindingSet nameAge = new MapBindingSet();
+ nameAge.addBinding("name", vf.createLiteral("Bob"));
+ nameAge.addBinding("age", vf.createLiteral(56));
+
+ final MapBindingSet nameHair = new MapBindingSet();
+ nameHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHair.addBinding("hairColor", vf.createLiteral("Brown"));
+
+ final Iterator<VisibilityBindingSet> rightResults = Lists.<VisibilityBindingSet>newArrayList(
+ new VisibilityBindingSet(nameAge),
+ new VisibilityBindingSet(nameHair)).iterator();
+
+ // Therefore, there are a few new join results that mix the two together.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = naturalJoin.newLeftResult(new VisibilityBindingSet(newLeftResult), rightResults);
+
+ final Set<BindingSet> newJoinResults = new HashSet<>();
+ while(newJoinResultsIt.hasNext()) {
+ newJoinResults.add( newJoinResultsIt.next() );
+ }
+
+ final Set<BindingSet> expected = Sets.<BindingSet>newHashSet();
+ final MapBindingSet nameHeightAge = new MapBindingSet();
+ nameHeightAge.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightAge.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightAge.addBinding("age", vf.createLiteral(56));
+ expected.add(new VisibilityBindingSet(nameHeightAge));
+
+ final MapBindingSet nameHeightHair = new MapBindingSet();
+ nameHeightHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightHair.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightHair.addBinding("hairColor", vf.createLiteral("Brown"));
+ expected.add(new VisibilityBindingSet(nameHeightHair));
+
+ assertEquals(expected, newJoinResults);
+ }
+
+ @Test
+ public void newRightResult_noLeftMatches() {
+ final IterativeJoin naturalJoin = new NaturalJoin();
+
+ // There are no left results.
+ final Iterator<VisibilityBindingSet> leftResults= new ArrayList<VisibilityBindingSet>().iterator();
+
+ // There is a new right result.
+ final MapBindingSet newRightResult = new MapBindingSet();
+ newRightResult.addBinding("name", vf.createLiteral("Bob"));
+
+ // Therefore, there are no new join results.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = naturalJoin.newRightResult(leftResults, new VisibilityBindingSet(newRightResult));
+ assertFalse( newJoinResultsIt.hasNext() );
+ }
+
+ @Test
+ public void newRightResult_joinsWithLeftResults() {
+ final IterativeJoin naturalJoin = new NaturalJoin();
+
+ // There are a few left results that join with the new right result.
+ final MapBindingSet nameAge = new MapBindingSet();
+ nameAge.addBinding("name", vf.createLiteral("Bob"));
+ nameAge.addBinding("age", vf.createLiteral(56));
+
+ final MapBindingSet nameHair = new MapBindingSet();
+ nameHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHair.addBinding("hairColor", vf.createLiteral("Brown"));
+
+ final Iterator<VisibilityBindingSet> leftResults = Lists.<VisibilityBindingSet>newArrayList(
+ new VisibilityBindingSet(nameAge),
+ new VisibilityBindingSet(nameHair)).iterator();
+
+ // There is a new right result.
+ final MapBindingSet newRightResult = new MapBindingSet();
+ newRightResult.addBinding("name", vf.createLiteral("Bob"));
+ newRightResult.addBinding("height", vf.createLiteral("5'9\""));
+
+ // Therefore, there are a few new join results that mix the two together.
+ final Iterator<VisibilityBindingSet> newJoinResultsIt = naturalJoin.newRightResult(leftResults, new VisibilityBindingSet(newRightResult));
+
+ final Set<BindingSet> newJoinResults = new HashSet<>();
+ while(newJoinResultsIt.hasNext()) {
+ newJoinResults.add( newJoinResultsIt.next() );
+ }
+
+ final Set<BindingSet> expected = Sets.<BindingSet>newHashSet();
+ final MapBindingSet nameHeightAge = new MapBindingSet();
+ nameHeightAge.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightAge.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightAge.addBinding("age", vf.createLiteral(56));
+ expected.add(new VisibilityBindingSet(nameHeightAge));
+
+ final MapBindingSet nameHeightHair = new MapBindingSet();
+ nameHeightHair.addBinding("name", vf.createLiteral("Bob"));
+ nameHeightHair.addBinding("height", vf.createLiteral("5'9\""));
+ nameHeightHair.addBinding("hairColor", vf.createLiteral("Brown"));
+ expected.add(new VisibilityBindingSet(nameHeightHair));
+
+ assertEquals(expected, newJoinResults);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.model/pom.xml
----------------------------------------------------------------------
diff --git a/common/rya.api.model/pom.xml b/common/rya.api.model/pom.xml
index ce77134..13893c6 100644
--- a/common/rya.api.model/pom.xml
+++ b/common/rya.api.model/pom.xml
@@ -39,7 +39,10 @@ under the License.
<groupId>org.openrdf.sesame</groupId>
<artifactId>sesame-query</artifactId>
</dependency>
-
+ <dependency>
+ <groupId>com.google.guava</groupId>
+ <artifactId>guava</artifactId>
+ </dependency>
<dependency>
<groupId>com.github.stephenc.findbugs</groupId>
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ArrayByteSequence.java
----------------------------------------------------------------------
diff --git a/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ArrayByteSequence.java b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ArrayByteSequence.java
new file mode 100644
index 0000000..f0f5eb6
--- /dev/null
+++ b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ArrayByteSequence.java
@@ -0,0 +1,143 @@
+/*
+ * 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.rya.api.model.visibility;
+
+import static com.google.common.base.Charsets.UTF_8;
+
+import java.io.Serializable;
+import java.nio.ByteBuffer;
+
+/**
+ * XXX
+ * This class has been copied over because Rya has decided to use the Accumulo
+ * implementation of visibilities to control who is able to access what data
+ * within a Rya instance. Until we implement an Accumulo agnostic method for
+ * handling those visibility expressions, we have chosen to pull the Accumulo
+ * code into our API.
+ *
+ * Copied from accumulo's org.apache.accumulo.core.data.ArrayByteSequence
+ * <dependancy>
+ * <groupId>org.apache.accumulo</groupId>
+ * <artifactId>accumulo-core</artifactId>
+ * <version>1.6.4</version>
+ * </dependancy>
+ */
+public class ArrayByteSequence extends ByteSequence implements Serializable {
+
+ private static final long serialVersionUID = 1L;
+
+ protected byte data[];
+ protected int offset;
+ protected int length;
+
+ public ArrayByteSequence(final byte data[]) {
+ this.data = data;
+ offset = 0;
+ length = data.length;
+ }
+
+ public ArrayByteSequence(final byte data[], final int offset, final int length) {
+
+ if (offset < 0 || offset > data.length || length < 0 || offset + length > data.length) {
+ throw new IllegalArgumentException(" Bad offset and/or length data.length = " + data.length + " offset = "
+ + offset + " length = " + length);
+ }
+
+ this.data = data;
+ this.offset = offset;
+ this.length = length;
+
+ }
+
+ public ArrayByteSequence(final String s) {
+ this(s.getBytes(UTF_8));
+ }
+
+ public ArrayByteSequence(final ByteBuffer buffer) {
+ length = buffer.remaining();
+
+ if (buffer.hasArray()) {
+ data = buffer.array();
+ offset = buffer.position();
+ } else {
+ data = new byte[length];
+ offset = 0;
+ buffer.get(data);
+ }
+ }
+
+ @Override
+ public byte byteAt(final int i) {
+
+ if (i < 0) {
+ throw new IllegalArgumentException("i < 0, " + i);
+ }
+
+ if (i >= length) {
+ throw new IllegalArgumentException("i >= length, " + i + " >= " + length);
+ }
+
+ return data[offset + i];
+ }
+
+ @Override
+ public byte[] getBackingArray() {
+ return data;
+ }
+
+ @Override
+ public boolean isBackedByArray() {
+ return true;
+ }
+
+ @Override
+ public int length() {
+ return length;
+ }
+
+ @Override
+ public int offset() {
+ return offset;
+ }
+
+ @Override
+ public ByteSequence subSequence(final int start, final int end) {
+
+ if (start > end || start < 0 || end > length) {
+ throw new IllegalArgumentException(
+ "Bad start and/end start = " + start + " end=" + end + " offset=" + offset + " length=" + length);
+ }
+
+ return new ArrayByteSequence(data, offset + start, end - start);
+ }
+
+ @Override
+ public byte[] toArray() {
+ if (offset == 0 && length == data.length) {
+ return data;
+ }
+
+ final byte[] copy = new byte[length];
+ System.arraycopy(data, offset, copy, 0, length);
+ return copy;
+ }
+
+ @Override
+ public String toString() {
+ return new String(data, offset, length, UTF_8);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/Authorizations.java
----------------------------------------------------------------------
diff --git a/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/Authorizations.java b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/Authorizations.java
new file mode 100644
index 0000000..70d4601
--- /dev/null
+++ b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/Authorizations.java
@@ -0,0 +1,77 @@
+/*
+ * 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.rya.api.model.visibility;
+
+import java.io.Serializable;
+
+/**
+ * A collection of authorization strings.
+ *
+ * XXX
+ * This class has been copied over because Rya has decided to use the Accumulo
+ * implementation of visibilities to control who is able to access what data
+ * within a Rya instance. Until we implement an Accumulo agnostic method for
+ * handling those visibility expressions, we have chosen to pull the Accumulo
+ * code into our API.
+ *
+ * Copied from accumulo's org.apache.accumulo.core.security.ByteSequence
+ * <dependancy>
+ * <groupId>org.apache.accumulo</groupId>
+ * <artifactId>accumulo-core</artifactId>
+ * <version>1.6.4</version>
+ * </dependancy>
+ */
+public class Authorizations implements Serializable {
+ private static final long serialVersionUID = 1L;
+
+ private static final boolean[] validAuthChars = new boolean[256];
+
+ /**
+ * A special header string used when serializing instances of this class.
+ *
+ * @see #serialize()
+ */
+ public static final String HEADER = "!AUTH1:";
+
+ static {
+ for (int i = 0; i < 256; i++) {
+ validAuthChars[i] = false;
+ }
+
+ for (int i = 'a'; i <= 'z'; i++) {
+ validAuthChars[i] = true;
+ }
+
+ for (int i = 'A'; i <= 'Z'; i++) {
+ validAuthChars[i] = true;
+ }
+
+ for (int i = '0'; i <= '9'; i++) {
+ validAuthChars[i] = true;
+ }
+
+ validAuthChars['_'] = true;
+ validAuthChars['-'] = true;
+ validAuthChars[':'] = true;
+ validAuthChars['.'] = true;
+ validAuthChars['/'] = true;
+ }
+
+ static final boolean isValidAuthChar(final byte b) {
+ return validAuthChars[0xff & b];
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/BadArgumentException.java
----------------------------------------------------------------------
diff --git a/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/BadArgumentException.java b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/BadArgumentException.java
new file mode 100644
index 0000000..de40b5e
--- /dev/null
+++ b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/BadArgumentException.java
@@ -0,0 +1,42 @@
+/*
+ * 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.rya.api.model.visibility;
+
+import java.util.regex.PatternSyntaxException;
+
+/**
+ * XXX
+ * This class has been copied over because Rya has decided to use the Accumulo
+ * implementation of visibilities to control who is able to access what data
+ * within a Rya instance. Until we implement an Accumulo agnostic method for
+ * handling those visibility expressions, we have chosen to pull the Accumulo
+ * code into our API.
+ *
+ * Copied from accumulo's org.apache.accumulo.core.util.BadArgumentException
+ * <dependancy>
+ * <groupId>org.apache.accumulo</groupId>
+ * <artifactId>accumulo-core</artifactId>
+ * <version>1.6.4</version>
+ * </dependancy>
+ */
+public final class BadArgumentException extends PatternSyntaxException {
+ private static final long serialVersionUID = 1L;
+
+ public BadArgumentException(final String desc, final String badarg, final int index) {
+ super(desc, badarg, index);
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ByteSequence.java
----------------------------------------------------------------------
diff --git a/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ByteSequence.java b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ByteSequence.java
new file mode 100644
index 0000000..ad1aa54
--- /dev/null
+++ b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ByteSequence.java
@@ -0,0 +1,114 @@
+/*
+ * 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.rya.api.model.visibility;
+
+/**
+ * XXX
+ * This class has been copied over because Rya has decided to use the Accumulo
+ * implementation of visibilities to control who is able to access what data
+ * within a Rya instance. Until we implement an Accumulo agnostic method for
+ * handling those visibility expressions, we have chosen to pull the Accumulo
+ * code into our API.
+ *
+ * Copied from accumulo's org.apache.accumulo.core.data.ByteSequence
+ * <dependancy>
+ * <groupId>org.apache.accumulo</groupId>
+ * <artifactId>accumulo-core</artifactId>
+ * <version>1.6.4</version>
+ * </dependancy>
+ */
+public abstract class ByteSequence implements Comparable<ByteSequence> {
+
+ public abstract byte byteAt(int i);
+
+ public abstract int length();
+
+ public abstract ByteSequence subSequence(int start, int end);
+
+ // may copy data
+ public abstract byte[] toArray();
+
+ public abstract boolean isBackedByArray();
+
+ public abstract byte[] getBackingArray();
+
+ public abstract int offset();
+
+ public static int compareBytes(final ByteSequence bs1, final ByteSequence bs2) {
+
+ final int minLen = Math.min(bs1.length(), bs2.length());
+
+ for (int i = 0; i < minLen; i++) {
+ final int a = bs1.byteAt(i) & 0xff;
+ final int b = bs2.byteAt(i) & 0xff;
+
+ if (a != b) {
+ return a - b;
+ }
+ }
+
+ return bs1.length() - bs2.length();
+ }
+
+ @Override
+ public int compareTo(final ByteSequence obs) {
+ if (isBackedByArray() && obs.isBackedByArray()) {
+ return WritableComparator.compareBytes(getBackingArray(), offset(), length(), obs.getBackingArray(),
+ obs.offset(), obs.length());
+ }
+
+ return compareBytes(this, obs);
+ }
+
+ @Override
+ public boolean equals(final Object o) {
+ if (o instanceof ByteSequence) {
+ final ByteSequence obs = (ByteSequence) o;
+
+ if (this == o) {
+ return true;
+ }
+
+ if (length() != obs.length()) {
+ return false;
+ }
+
+ return compareTo(obs) == 0;
+ }
+
+ return false;
+
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 1;
+ if (isBackedByArray()) {
+ final byte[] data = getBackingArray();
+ final int end = offset() + length();
+ for (int i = offset(); i < end; i++) {
+ hash = 31 * hash + data[i];
+ }
+ } else {
+ for (int i = 0; i < length(); i++) {
+ hash = 31 * hash + byteAt(i);
+ }
+ }
+ return hash;
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ColumnVisibility.java
----------------------------------------------------------------------
diff --git a/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ColumnVisibility.java b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ColumnVisibility.java
new file mode 100644
index 0000000..052de45
--- /dev/null
+++ b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/ColumnVisibility.java
@@ -0,0 +1,551 @@
+/*
+ * 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.rya.api.model.visibility;
+
+import static com.google.common.base.Charsets.UTF_8;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+import java.util.TreeSet;
+
+/**
+ * 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.
+ *
+ * <P>
+ * 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>
+ * In addition to the base set of visibilities, any character can be used in the
+ * expression if it is quoted. If the quoted term contains '"' or '\', then
+ * escape the character with '\'. The {@link #quote(String)} method can be used
+ * to properly quote and escape terms automatically. The following is an example
+ * of a quoted term:
+ *
+ * <pre>
+ * "A#C"<span />&<span />B
+ * </pre>
+ *
+ * XXX
+ * This class has been copied over because Rya has decided to use the Accumulo
+ * implementation of visibilities to control who is able to access what data
+ * within a Rya instance. Until we implement an Accumulo agnostic method for
+ * handling those visibility expressions, we have chosen to pull the Accumulo
+ * code into our API.
+ *
+ * Copied from accumulo's org.apache.accumulo.core.security.ColumnVisibility
+ * <dependancy>
+ * <groupId>org.apache.accumulo</groupId>
+ * <artifactId>accumulo-core</artifactId>
+ * <version>1.6.4</version>
+ * </dependancy>
+ */
+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;
+ }
+
+ /**
+ * The node types in a parse tree for a visibility expression.
+ */
+ public static enum NodeType {
+ EMPTY, TERM, OR, AND,
+ }
+
+ /**
+ * All empty nodes are equal and represent the same value.
+ */
+ private static final Node EMPTY_NODE = new Node(NodeType.EMPTY, 0);
+
+ /**
+ * A node in the parse tree for a visibility expression.
+ */
+ public static class Node {
+ /**
+ * An empty list of nodes.
+ */
+ public final static List<Node> EMPTY = Collections.emptyList();
+ NodeType type;
+ int start;
+ int end;
+ List<Node> children = EMPTY;
+
+ public Node(final NodeType type, final int start) {
+ this.type = type;
+ this.start = start;
+ end = start + 1;
+ }
+
+ public Node(final int start, final int end) {
+ type = NodeType.TERM;
+ this.start = start;
+ this.end = end;
+ }
+
+ public void add(final 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(final byte expression[]) {
+ if (type != NodeType.TERM) {
+ throw new RuntimeException();
+ }
+
+ if (expression[start] == '"') {
+ // its a quoted term
+ final int qStart = start + 1;
+ final int qEnd = end - 1;
+
+ return new ArrayByteSequence(expression, qStart, qEnd - qStart);
+ }
+ return new ArrayByteSequence(expression, start, end - start);
+ }
+ }
+
+ /**
+ * A node comparator. Nodes sort according to node type, terms sort
+ * lexicographically. AND and OR nodes sort by number of children, or if the
+ * same by corresponding children.
+ */
+ public static class NodeComparator implements Comparator<Node>, Serializable {
+
+ private static final long serialVersionUID = 1L;
+ byte[] text;
+
+ /**
+ * Creates a new comparator.
+ *
+ * @param text expression string, encoded in UTF-8
+ */
+ public NodeComparator(final byte[] text) {
+ this.text = text;
+ }
+
+ @Override
+ public int compare(final Node a, final 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.
+ */
+ public static Node normalize(final Node root, final 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
+ public static Node normalize(final Node root, final byte[] expression, final NodeComparator comparator) {
+ if (root.type != NodeType.TERM) {
+ final TreeSet<Node> rolledUp = new TreeSet<Node>(comparator);
+ final java.util.Iterator<Node> itr = root.children.iterator();
+ while (itr.hasNext()) {
+ final 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.
+ */
+ public static void stringify(final Node root, final byte[] expression, final StringBuilder out) {
+ if (root.type == NodeType.TERM) {
+ out.append(new String(expression, root.start, root.end - root.start, UTF_8));
+ } else {
+ String sep = "";
+ for (final Node c : root.children) {
+ out.append(sep);
+ final 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 this evaluator's expression.
+ *
+ * @return normalized expression in byte[] form
+ */
+ public byte[] flatten() {
+ final Node normRoot = normalize(node, expression);
+ final StringBuilder builder = new StringBuilder(expression.length);
+ stringify(normRoot, expression, builder);
+ return builder.toString().getBytes(UTF_8);
+ }
+
+ private static class ColumnVisibilityParser {
+ private int index = 0;
+ private int parens = 0;
+
+ public ColumnVisibilityParser() {
+ }
+
+ Node parse(final byte[] expression) {
+ if (expression.length > 0) {
+ final Node node = parse_(expression);
+ if (node == null) {
+ throw new BadArgumentException("operator or missing parens", new String(expression, UTF_8),
+ index - 1);
+ }
+ if (parens != 0) {
+ throw new BadArgumentException("parenthesis mis-match", new String(expression, UTF_8), index - 1);
+ }
+ return node;
+ }
+ return null;
+ }
+
+ Node processTerm(final int start, final int end, final Node expr, final byte[] expression) {
+ if (start != end) {
+ if (expr != null) {
+ throw new BadArgumentException("expression needs | or &", new String(expression, UTF_8), start);
+ }
+ return new Node(start, end);
+ }
+ if (expr == null) {
+ throw new BadArgumentException("empty term", new String(expression, UTF_8), start);
+ }
+ return expr;
+ }
+
+ Node parse_(final byte[] expression) {
+ Node result = null;
+ Node expr = null;
+ final int wholeTermStart = index;
+ int subtermStart = index;
+ boolean subtermComplete = false;
+
+ while (index < expression.length) {
+ switch (expression[index++]) {
+ case '&': {
+ expr = processTerm(subtermStart, index - 1, expr, expression);
+ if (result != null) {
+ if (!result.type.equals(NodeType.AND)) {
+ throw new BadArgumentException("cannot mix & and |", new String(expression, UTF_8),
+ index - 1);
+ }
+ } else {
+ result = new Node(NodeType.AND, wholeTermStart);
+ }
+ result.add(expr);
+ expr = null;
+ subtermStart = index;
+ subtermComplete = false;
+ break;
+ }
+ case '|': {
+ expr = processTerm(subtermStart, index - 1, expr, expression);
+ if (result != null) {
+ if (!result.type.equals(NodeType.OR)) {
+ throw new BadArgumentException("cannot mix | and &", new String(expression, UTF_8), index - 1);
+ }
+ } else {
+ result = new Node(NodeType.OR, wholeTermStart);
+ }
+ result.add(expr);
+ expr = null;
+ subtermStart = index;
+ subtermComplete = false;
+ break;
+ }
+ case '(': {
+ parens++;
+ if (subtermStart != index - 1 || expr != null) {
+ throw new BadArgumentException("expression needs & or |", new String(expression, UTF_8),
+ index - 1);
+ }
+ expr = parse_(expression);
+ subtermStart = index;
+ subtermComplete = false;
+ break;
+ }
+ case ')': {
+ parens--;
+ final Node child = processTerm(subtermStart, index - 1, expr, expression);
+ if (child == null && result == null) {
+ throw new BadArgumentException("empty expression not allowed",
+ new String(expression, UTF_8), index);
+ }
+ if (result == null) {
+ return child;
+ }
+ if (result.type == child.type) {
+ for (final Node c : child.children) {
+ result.add(c);
+ }
+ } else {
+ result.add(child);
+ }
+ result.end = index - 1;
+ return result;
+ }
+ case '"': {
+ if (subtermStart != index - 1) {
+ throw new BadArgumentException("expression needs & or |", new String(expression, UTF_8),
+ 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, UTF_8), index - 1);
+ }
+ }
+ index++;
+ }
+
+ if (index == expression.length) {
+ throw new BadArgumentException("unclosed quote", new String(expression, UTF_8),
+ subtermStart);
+ }
+
+ if (subtermStart + 1 == index) {
+ throw new BadArgumentException("empty term", new String(expression, UTF_8), subtermStart);
+ }
+
+ index++;
+
+ subtermComplete = true;
+
+ break;
+ }
+ default: {
+ if (subtermComplete) {
+ throw new BadArgumentException("expression needs & or |", new String(expression, UTF_8),
+ index - 1);
+ }
+
+ final byte c = expression[index - 1];
+ if (!Authorizations.isValidAuthChar(c)) {
+ throw new BadArgumentException("bad character (" + c + ")", new String(expression, UTF_8),
+ index - 1);
+ }
+ }
+ }
+ }
+ final Node child = processTerm(subtermStart, index, expr, expression);
+ if (result != null) {
+ result.add(child);
+ result.end = index;
+ } else {
+ result = child;
+ }
+ if (result.type != NodeType.TERM) {
+ if (result.children.size() < 2) {
+ throw new BadArgumentException("missing term", new String(expression, UTF_8), index);
+ }
+ }
+ return result;
+ }
+ }
+
+ private void validate(final byte[] expression) {
+ if (expression != null && expression.length > 0) {
+ final ColumnVisibilityParser p = new ColumnVisibilityParser();
+ node = p.parse(expression);
+ } else {
+ node = EMPTY_NODE;
+ }
+ this.expression = expression;
+ }
+
+ /**
+ * Creates an 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() {
+ this(new byte[] {});
+ }
+
+ /**
+ * Creates a column visibility for a Mutation.
+ *
+ * @param expression An expression of the rights needed to see this
+ * mutation. The expression syntax is defined at the class-level
+ * documentation
+ */
+ public ColumnVisibility(final String expression) {
+ this(expression.getBytes(UTF_8));
+ }
+
+ /**
+ * Creates a column visibility for a Mutation from a string already encoded
+ * in UTF-8 bytes.
+ *
+ * @param expression visibility expression, encoded as UTF-8 bytes
+ * @see #ColumnVisibility(String)
+ */
+ public ColumnVisibility(final byte[] expression) {
+ validate(expression);
+ }
+
+ @Override
+ public String toString() {
+ return "[" + new String(expression, UTF_8) + "]";
+ }
+
+ /**
+ * See {@link #equals(ColumnVisibility)}
+ */
+ @Override
+ public boolean equals(final 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.
+ *
+ * @param otherLe other column visibility
+ * @return true if this visibility equals the other via string comparison
+ */
+ public boolean equals(final ColumnVisibility otherLe) {
+ return Arrays.equals(expression, otherLe.expression);
+ }
+
+ @Override
+ public int hashCode() {
+ return Arrays.hashCode(expression);
+ }
+
+ /**
+ * Gets the parse tree for this column visibility.
+ *
+ * @return parse tree node
+ */
+ public Node getParseTree() {
+ return node;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-rya/blob/0ad2c511/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/FastByteComparison.java
----------------------------------------------------------------------
diff --git a/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/FastByteComparison.java b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/FastByteComparison.java
new file mode 100644
index 0000000..220661e
--- /dev/null
+++ b/common/rya.api.model/src/main/java/org/apache/rya/api/model/visibility/FastByteComparison.java
@@ -0,0 +1,240 @@
+/**
+ * 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.rya.api.model.visibility;
+
+import java.lang.reflect.Field;
+import java.nio.ByteOrder;
+import java.security.AccessController;
+import java.security.PrivilegedAction;
+
+import com.google.common.primitives.Longs;
+import com.google.common.primitives.UnsignedBytes;
+
+import sun.misc.Unsafe;
+
+/**
+ * Utility code to do optimized byte-array comparison. This is borrowed and
+ * slightly modified from Guava's {@link UnsignedBytes} class to be able to
+ * compare arrays that start at non-zero offsets.
+ *
+ * XXX
+ * This class has been copied over because Rya has decided to use the Accumulo
+ * implementation of visibilities to control who is able to access what data
+ * within a Rya instance. Until we implement an Accumulo agnostic method for
+ * handling those visibility expressions, we have chosen to pull the Accumulo
+ * code into our API.
+ *
+ * Copied from accumulo's org.apache.hadoop.io.FastByteComparisons
+ * <dependancy>
+ * <groupId>org.apache.hadoop</groupId>
+ * <artifactId>hadoop-commons</artifactId>
+ * <version>2.5</version>
+ * </dependancy>
+ */
+abstract class FastByteComparisons {
+
+ /**
+ * Lexicographically compare two byte arrays.
+ */
+ public static int compareTo(final byte[] b1, final int s1, final int l1, final byte[] b2, final int s2,
+ final int l2) {
+ return LexicographicalComparerHolder.BEST_COMPARER.compareTo(b1, s1, l1, b2, s2, l2);
+ }
+
+ private interface Comparer<T> {
+ abstract public int compareTo(T buffer1, int offset1, int length1, T buffer2, int offset2, int length2);
+ }
+
+ private static Comparer<byte[]> lexicographicalComparerJavaImpl() {
+ return LexicographicalComparerHolder.PureJavaComparer.INSTANCE;
+ }
+
+ /**
+ * Provides a lexicographical comparer implementation; either a Java
+ * implementation or a faster implementation based on {@link Unsafe}.
+ *
+ * <p>
+ * Uses reflection to gracefully fall back to the Java implementation if
+ * {@code Unsafe} isn't available.
+ */
+ private static class LexicographicalComparerHolder {
+ static final String UNSAFE_COMPARER_NAME = LexicographicalComparerHolder.class.getName() + "$UnsafeComparer";
+
+ static final Comparer<byte[]> BEST_COMPARER = getBestComparer();
+
+ /**
+ * Returns the Unsafe-using Comparer, or falls back to the pure-Java
+ * implementation if unable to do so.
+ */
+ static Comparer<byte[]> getBestComparer() {
+ try {
+ final Class<?> theClass = Class.forName(UNSAFE_COMPARER_NAME);
+
+ // yes, UnsafeComparer does implement Comparer<byte[]>
+ @SuppressWarnings("unchecked")
+ final Comparer<byte[]> comparer = (Comparer<byte[]>) theClass.getEnumConstants()[0];
+ return comparer;
+ } catch (final Throwable t) { // ensure we really catch *everything*
+ return lexicographicalComparerJavaImpl();
+ }
+ }
+
+ private enum PureJavaComparer implements Comparer<byte[]> {
+ INSTANCE;
+
+ @Override
+ public int compareTo(final byte[] buffer1, final int offset1, final int length1, final byte[] buffer2,
+ final int offset2, final int length2) {
+ // Short circuit equal case
+ if (buffer1 == buffer2 && offset1 == offset2 && length1 == length2) {
+ return 0;
+ }
+ // Bring WritableComparator code local
+ final int end1 = offset1 + length1;
+ final int end2 = offset2 + length2;
+ for (int i = offset1, j = offset2; i < end1 && j < end2; i++, j++) {
+ final int a = buffer1[i] & 0xff;
+ final int b = buffer2[j] & 0xff;
+ if (a != b) {
+ return a - b;
+ }
+ }
+ return length1 - length2;
+ }
+ }
+
+ @SuppressWarnings("unused") // used via reflection
+ private enum UnsafeComparer implements Comparer<byte[]> {
+ INSTANCE;
+
+ static final Unsafe theUnsafe;
+
+ /** The offset to the first element in a byte array. */
+ static final int BYTE_ARRAY_BASE_OFFSET;
+
+ static {
+ theUnsafe = (Unsafe) AccessController.doPrivileged(new PrivilegedAction<Object>() {
+ @Override
+ public Object run() {
+ try {
+ final Field f = Unsafe.class.getDeclaredField("theUnsafe");
+ f.setAccessible(true);
+ return f.get(null);
+ } catch (final NoSuchFieldException e) {
+ // It doesn't matter what we throw;
+ // it's swallowed in getBestComparer().
+ throw new Error();
+ } catch (final IllegalAccessException e) {
+ throw new Error();
+ }
+ }
+ });
+
+ BYTE_ARRAY_BASE_OFFSET = theUnsafe.arrayBaseOffset(byte[].class);
+
+ // sanity check - this should never fail
+ if (theUnsafe.arrayIndexScale(byte[].class) != 1) {
+ throw new AssertionError();
+ }
+ }
+
+ static final boolean littleEndian = ByteOrder.nativeOrder().equals(ByteOrder.LITTLE_ENDIAN);
+
+ /**
+ * Returns true if x1 is less than x2, when both values are treated
+ * as unsigned.
+ */
+ static boolean lessThanUnsigned(final long x1, final long x2) {
+ return x1 + Long.MIN_VALUE < x2 + Long.MIN_VALUE;
+ }
+
+ /**
+ * Lexicographically compare two arrays.
+ *
+ * @param buffer1 left operand
+ * @param buffer2 right operand
+ * @param offset1 Where to start comparing in the left buffer
+ * @param offset2 Where to start comparing in the right buffer
+ * @param length1 How much to compare from the left buffer
+ * @param length2 How much to compare from the right buffer
+ * @return 0 if equal, < 0 if left is less than right, etc.
+ */
+ @Override
+ public int compareTo(final byte[] buffer1, final int offset1, final int length1, final byte[] buffer2,
+ final int offset2, final int length2) {
+ // Short circuit equal case
+ if (buffer1 == buffer2 && offset1 == offset2 && length1 == length2) {
+ return 0;
+ }
+ final int minLength = Math.min(length1, length2);
+ final int minWords = minLength / Longs.BYTES;
+ final int offset1Adj = offset1 + BYTE_ARRAY_BASE_OFFSET;
+ final int offset2Adj = offset2 + BYTE_ARRAY_BASE_OFFSET;
+
+ /*
+ * Compare 8 bytes at a time. Benchmarking shows comparing 8
+ * bytes at a time is no slower than comparing 4 bytes at a time
+ * even on 32-bit. On the other hand, it is substantially faster
+ * on 64-bit.
+ */
+ for (int i = 0; i < minWords * Longs.BYTES; i += Longs.BYTES) {
+ final long lw = theUnsafe.getLong(buffer1, offset1Adj + (long) i);
+ final long rw = theUnsafe.getLong(buffer2, offset2Adj + (long) i);
+ final long diff = lw ^ rw;
+
+ if (diff != 0) {
+ if (!littleEndian) {
+ return lessThanUnsigned(lw, rw) ? -1 : 1;
+ }
+
+ // Use binary search
+ int n = 0;
+ int y;
+ int x = (int) diff;
+ if (x == 0) {
+ x = (int) (diff >>> 32);
+ n = 32;
+ }
+
+ y = x << 16;
+ if (y == 0) {
+ n += 16;
+ } else {
+ x = y;
+ }
+
+ y = x << 8;
+ if (y == 0) {
+ n += 8;
+ }
+ return (int) ((lw >>> n & 0xFFL) - (rw >>> n & 0xFFL));
+ }
+ }
+
+ // The epilogue to cover the last (minLength % 8) elements.
+ for (int i = minWords * Longs.BYTES; i < minLength; i++) {
+ final int result = UnsignedBytes.compare(buffer1[offset1 + i], buffer2[offset2 + i]);
+ if (result != 0) {
+ return result;
+ }
+ }
+ return length1 - length2;
+ }
+ }
+ }
+}
\ No newline at end of file