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 <smith...@gmail.com> Authored: Tue Nov 7 12:56:39 2017 -0500 Committer: caleb <caleb.me...@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
