GitHub user okram opened a pull request:

https://github.com/apache/tinkerpop/pull/434

TINKERPOP-1456 & TINKERPOP-1412: SubgraphStrategy updates and more!

https://issues.apache.org/jira/browse/TINKERPOP-1456
https://issues.apache.org/jira/browse/TINKERPOP-1412

There is alot of good work here.

`SubgraphStrategy` now supports vertex property filtering. Added `InlineFilterStrategy` which analyzes the child traversals of `TraversalFilterStep` and `AndStep` and if they are composed of all `FilterSteps`, then it inlines the child traversal into the parent traversal. This is huge, cause it means there is a better chance of getting vertex-centric index and graph-centric index provider optimizations to pull in filters accordingly for push-down predicates. From there I added lots of test to `SubgraphStrategyXXXTest` and updated the reference documentation with some better uses of `SubgraphStrategy`. Also, I made it so `AbstractLambdaTraversals` can be "bypasses" (necessary for various strategy introspection/mutation scenarios). `ConnectiveSteps` (and/or) extends `FilterStep` (should have the whole time). Added the concept that hiddel labels on steps are purged at execution time. Much like hidden labels in structure are not visible, did the same here in traversal. This makes life alot easier when dealing with multi-nested strategies.

Here is the CHANGELOG.

```

• Added `TraversalHelper.applySingleLevelStrategies()` which will apply a subset of strategies but not walk the child tree.
• Added the concept that hidden labels using during traversal compilation are removed at the end during `StandardVerificationStrategy`. (breaking)
• Added `InlineFilterStrategy` which will determine if a `TraversalFilterStep` or `AndStep` children are filters and if so, inline them.
• Removed `IdentityRemovalStrategy` from the default listing as its not worth the clock cycles.
• Removed the "!" symbol in `NotStep.toString()` as it is confusing and the `NotStep`-name is sufficient.
• Fixed a bug in `TraversalVertexProgram` (OLAP) around ordering and connectives (i.e. `and()` and `or()`).
• Added `AbstractGremlinProcessTest.checkOrderedResults()` to make testing ordered results easier.
• `AbstractLambdaTraversal` now supports a `bypassTraversal` where it is possible for strategies to redefine such lambda traversals.
• Added an internal utility `ClassFilterStep` which determines if the traverser object's class is an instance of the provided class.
• `ConnectiveStep` extends `FilterStep` and thus, is more appropriately categorized in the step hierarchy.
• `PropertyMapStep` supports a provided traversal for accessing the properties of the element.
• `SubgraphStrategy` now supports vertex property filtering.
  ```

VOTE +1

You can merge this pull request into a Git repository by running:

$ git pull https://github.com/apache/tinkerpop TINKERPOP-1456

Alternatively you can review and apply these changes as the patch at:

https://github.com/apache/tinkerpop/pull/434.patch

To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:

This closes #434

commit 4f723eed82294b95f8409db5cc890f9f41ed84ae
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-19T19:52:33Z

Added support for SubgraphStrategy.vertexProperties(). Added some test cases to verify proper functioning. Also, cleaned up Stream-stuff in SubgraphStrategy. Going to do some more cleanup there to make things clean and efficient.

commit d2ae1aaa8bce78d260e53dc4ecc047c78f905b16
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-20T16:04:56Z

AbstractLambdaTraversals now support a bypassTraversal which allows strategies to easily change the semantics of the lambda traversal. Found a bug in TraversalVertexProgram around order() and the use of ConnectiveSteps. Added more tests to SubgraphStrategyProcessTest to test vertex properties and ordering. Added checkOrderedResult() to AbstractGremlinProcessTest which makes it easy to check ordered streams. Updated OrderTest to use this model – much simpler.

commit 5fc2163df107ddae830bd68f7a3926d4fcea8211
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-20T21:05:12Z

SubgraphStrategy no longer filter()-wraps criteria if the criteria is a chain of filters or connectives. This ensures that has() folds to VertexStep and VertexEdgeSteps – by most providers.

commit beaf5208ddafd90277e9c5b0f28074cf0b8cb6d4
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-21T17:48:33Z

added ClassFilterStep which checks the class type of a traverser object. this is an internal utility class not exposed at the GraphTraversal level.

commit b5ec675062ac3f1a7ea5f7af5ff12e51ffc94ead
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-21T20:11:47Z

PropertyMapStep now supports a propertyTraversal for accessing properties from the element. ConnectiveStrategy will concatenate two AND traversals if they are both filter based. SubgraphStrategy now handles valueMap() and propertyMap() correctly. Added TraversalHelper.isAllFilters() to check if a traversal is completely filter-based.

commit 226d7a90a01ef32c90aa29aaa4c54c2c846f8835
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-21T21:06:12Z

SubgraphStrategy is smart about trying to determine whether the property is a VertexProperty or a stanard Property. If the former, then no OrStep wrap is needed and the filter can be inlined and thus, likely that the graph database optimizers will use vertex-centric indices.

commit 0bbf6a3efb74dd4ea2e3e4384bd7ab3e22e9b9b3
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-21T21:08:39Z

a loop got fuggled.

commit 1f70b434b459c088c4be20d1bf9b126e31eda72c
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-21T21:18:48Z

added more test cases to SubgraphStrategyProcessTest and cleanedup SubgraphStrategy a bit.

commit 23a4e86b2992f507fdb1536060b9344c9a09d188
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-22T19:45:33Z

there is a bug in StarGraph property attachment/detachment that caused a contrived test case in SubgraphStrategyProcessTest to fail. I got the same effect with another traversal and have logged the StarGraph bug in JIRA.

commit 37f0606c29533555b699ea34c0a8aed402e2e0cb
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-23T18:11:46Z

added a better example to SugraphStategy in the reference docs. Also added an explain() so people can see whats going on.

commit dabeb02deb00b85d23ca8b70bfcf7f6ea8ec2ed1
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Date: 2016-09-23T22:03:37Z

added lots of good stuff that all revolves around SubgraphStategy. InlineFilterStrategy tries to inline filters. Epic. And/OrStep are now FilterSteps - epic. Lots of cleanup and simplification of SubgraphStrategy cause of it.

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

Integration tests ran overnight.

```
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 04:54 h
[INFO] Finished at: 2016-09-23T23:14:06-06:00
[INFO] Final Memory: 111M/1678M
[INFO] ------------------------------------------------------------------------
```

Github user spmallette commented on the issue:

https://github.com/apache/tinkerpop/pull/434

Haven't reviewed in detail - running some tests, but this feature could use an entry to the Upgrade Documentation.

Github user spmallette commented on a diff in the pull request:

https://github.com/apache/tinkerpop/pull/434#discussion_r80371392

— Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java —
@@ -0,0 +1,100 @@
+/*
+ * 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.tinkerpop.gremlin.process.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.optimization.GraphFilterStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.AndStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
— End diff –

What's the strategy do? Few lines of javadoc, please

Github user twilmes commented on the issue:

https://github.com/apache/tinkerpop/pull/434

This is a good batch of new work and updates. I was experimenting with the `SubgraphStrategy` and wonder if `explain()` should be surfacing the filter value when a `valueMap()` is used.

```
gremlin> graph = TinkerFactory.createTheCrew()
==>tinkergraph[vertices:6 edges:14]
gremlin> g = graph.traversal()
==>graphtraversalsource[tinkergraph[vertices:6 edges:14], standard]
gremlin> g = g.withStrategies(SubgraphStrategy.build().vertexProperties(hasLabel('name')).create())
==>graphtraversalsource[tinkergraph[vertices:6 edges:14], standard]
gremlin> g.V().valueMap()
==>[name:[marko]]
==>[name:[stephen]]
==>[name:[matthias]]
==>[name:[daniel]]
==>[name:[gremlin]]
==>[name:[tinkergraph]]
gremlin> g.V().valueMap().explain()
==>Traversal Explanation
=======================================================================================
Original Traversal [GraphStep(vertex,[]), PropertyMapStep(value)]

SubgraphStrategy [D] [GraphStep(vertex,[]), PropertyMapStep(value)]
ConnectiveStrategy [D] [GraphStep(vertex,[]), PropertyMapStep(value)]
RepeatUnrollStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
RangeByIsCountStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
InlineFilterStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
FilterRankingStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
MatchPredicateStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
PathRetractionStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
IncidentToAdjacentStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
AdjacentToIncidentStrategy [O] [GraphStep(vertex,[]), PropertyMapStep(value)]
TinkerGraphStepStrategy [P] [TinkerGraphStep(vertex,[]), PropertyMapStep(value)]
ProfileStrategy [F] [TinkerGraphStep(vertex,[]), PropertyMapStep(value)]
StandardVerificationStrategy [V] [TinkerGraphStep(vertex,[]), PropertyMapStep(value)]

Final Traversal [TinkerGraphStep(vertex,[]), PropertyMapStep(value)]
```

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

Added the `ProperyMapStep` propertyTraversal to the `toString()` if it exists.

```
gremlin> g.V().valueMap().explain()
==>Traversal Explanation
=================================================================================================================================================================================================================================================================
Original Traversal [GraphStep(vertex,[]), PropertyMapStep(value)]

SubgraphStrategy [D] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [TraversalFilterStep([HasStep([~label.eq(name)])])]]), TraversalFilterStep([HasStep([~label.eq(name)])])],value)]
ConnectiveStrategy [D] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [TraversalFilterStep([HasStep([~label.eq(name)])])]]), TraversalFilterStep([HasStep([~label.eq(name)])])],value)]
RangeByIsCountStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [TraversalFilterStep([HasStep([~label.eq(name)])])]]), TraversalFilterStep([HasStep([~label.eq(name)])])],value)]
RepeatUnrollStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [TraversalFilterStep([HasStep([~label.eq(name)])])]]), TraversalFilterStep([HasStep([~label.eq(name)])])],value)]
MatchPredicateStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [TraversalFilterStep([HasStep([~label.eq(name)])])]]), TraversalFilterStep([HasStep([~label.eq(name)])])],value)]
PathRetractionStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [TraversalFilterStep([HasStep([~label.eq(name)])])]]), TraversalFilterStep([HasStep([~label.eq(name)])])],value)]
InlineFilterStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]
FilterRankingStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]
IncidentToAdjacentStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]
AdjacentToIncidentStrategy [O] [GraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]
TinkerGraphStepStrategy [P] [TinkerGraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]
ProfileStrategy [F] [TinkerGraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]
StandardVerificationStrategy [V] [TinkerGraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]

Final Traversal [TinkerGraphStep(vertex,[]), PropertyMapStep([PropertiesStep(property), OrStep([[ClassFilterStep(VertexProperty)], [HasStep([~label.eq(name)])]]), HasStep([~label.eq(name)])],value)]
```

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

When this is merged to master, make a JIRA ticket for the `RepeatUnrollStrategy` bug fix (and then close it) as this was pretty severe bug and I suspect this was why numerous people had problems with `RepeatUnrollStrategy` when it came out in 3.2.1.

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

Added this JIRA which is fixed in this PR:

https://issues.apache.org/jira/browse/TINKERPOP-1472

Github user twilmes commented on the issue:

https://github.com/apache/tinkerpop/pull/434

`explain` update looks good, builds passed on my end too and good catch on the unrolling bugs.

VOTE: +1

Github user okram commented on a diff in the pull request:

https://github.com/apache/tinkerpop/pull/434#discussion_r80585995

— Diff: gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java —
@@ -0,0 +1,100 @@
+/*
+ * 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.tinkerpop.gremlin.process.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.optimization.GraphFilterStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
+import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.AndStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * @author Marko A. Rodriguez (http://markorodriguez.com)
— End diff –

Javadoc added.

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

Ran integration tests overnight again.

```
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 04:55 h
[INFO] Finished at: 2016-09-26T21:12:15-06:00
[INFO] Final Memory: 111M/1675M
[INFO] ------------------------------------------------------------------------
```

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

While hangin' on this branch. Simple fix for https://issues.apache.org/jira/browse/TINKERPOP-1423.

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

This branch also effects https://issues.apache.org/jira/browse/TINKERPOP-844... (but might not close it). Will add a comment to 844 when merge to master happens.

Github user spmallette commented on the issue:

https://github.com/apache/tinkerpop/pull/434

All tests pass with `docker/build.sh -t -n -i`

VOTE +1

Github user okram closed the pull request at:

https://github.com/apache/tinkerpop/pull/434

Github user okram commented on the issue:

https://github.com/apache/tinkerpop/pull/434

Merged.