| /* |
| 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 gremlingo |
| |
| const ( |
| baseNamespace = "org.apache.tinkerpop.gremlin.process.traversal.strategy." |
| decorationNamespace = baseNamespace + "decoration." |
| finalizationNamespace = baseNamespace + "finalization." |
| optimizationNamespace = baseNamespace + "optimization." |
| verificationNamespace = baseNamespace + "verification." |
| computerDecorationNamespace = "org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.decoration." |
| ) |
| |
| type TraversalStrategy interface { |
| } |
| |
| type traversalStrategy struct { |
| name string |
| configuration map[string]interface{} |
| apply func(g GraphTraversal) |
| } |
| |
| // Decoration strategies |
| |
| // ConnectiveStrategy rewrites the binary conjunction form of a.And().b into a AndStep of |
| // And(a,b) (likewise for OrStep). |
| func ConnectiveStrategy() TraversalStrategy { |
| return &traversalStrategy{name: decorationNamespace + "ConnectiveStrategy"} |
| } |
| |
| // ElementIdStrategy provides a degree of control over element identifier assignment as some Graphs don't provide |
| // that feature. This strategy provides for identifier assignment by enabling users to utilize Vertex and Edge indices |
| // under the hood, thus simulating that capability. |
| // By default, when an identifier is not supplied by the user, newly generated identifiers are UUID objects. |
| func ElementIdStrategy() TraversalStrategy { |
| return &traversalStrategy{name: decorationNamespace + "ElementIdStrategy"} |
| } |
| |
| func HaltedTraverserStrategy(config HaltedTraverserStrategyConfig) TraversalStrategy { |
| configMap := make(map[string]interface{}) |
| if config.HaltedTraverserFactoryName != "" { |
| configMap["haltedTraverserFactory"] = config.HaltedTraverserFactoryName |
| } |
| return &traversalStrategy{name: decorationNamespace + "HaltedTraverserStrategy", configuration: configMap} |
| } |
| |
| // HaltedTraverserStrategyConfig provides configuration options for HaltedTraverserStrategy. |
| // Zeroed (unset) values are ignored. |
| type HaltedTraverserStrategyConfig struct { |
| HaltedTraverserFactoryName string |
| } |
| |
| // OptionsStrategy will not alter the Traversal. It is only a holder for configuration options associated with the |
| // Traversal meant to be accessed by steps or other classes that might have some interaction with it. It is |
| // essentially a way for users to provide Traversal level configuration options that can be used in various ways |
| // by different Graph providers. |
| func OptionsStrategy(options map[string]interface{}) TraversalStrategy { |
| return &traversalStrategy{name: decorationNamespace + "OptionsStrategy", configuration: options} |
| } |
| |
| // PartitionStrategy partitions the Vertices, Edges and Vertex properties of a Graph into String named |
| // partitions (i.e. buckets, subgraphs, etc.). It blinds a Traversal from "seeing" specified areas of |
| // the graph. The Traversal will ignore all Graph elements not in those "read" partitions. |
| func PartitionStrategy(config PartitionStrategyConfig) TraversalStrategy { |
| configMap := map[string]interface{}{"includeMetaProperties": config.IncludeMetaProperties} |
| if config.PartitionKey != "" { |
| configMap["partitionKey"] = config.PartitionKey |
| } |
| if config.WritePartition != "" { |
| configMap["writePartition"] = config.WritePartition |
| } |
| if len(config.ReadPartitions.ToSlice()) != 0 { |
| configMap["readPartitions"] = config.ReadPartitions |
| } |
| return &traversalStrategy{name: decorationNamespace + "PartitionStrategy", configuration: configMap} |
| } |
| |
| // PartitionStrategyConfig provides configuration options for PartitionStrategy. |
| // Zeroed (unset) values are ignored except IncludeMetaProperties. |
| type PartitionStrategyConfig struct { |
| PartitionKey string |
| WritePartition string |
| ReadPartitions Set |
| IncludeMetaProperties bool |
| } |
| |
| // SeedStrategy resets the specified Seed value for Seedable steps, which in turn will produce deterministic |
| // results from those steps. It is important to note that when using this strategy that it only guarantees |
| // deterministic results from a step but not from an entire Traversal. For example, if a Graph does no guarantee |
| // iteration order for g.V() then repeated runs of g.V().Coin(0.5) with this strategy will return the same number |
| // of results but not necessarily the same ones. The same problem can occur in OLAP-based Taversals where |
| // iteration order is not explicitly guaranteed. The only way to ensure completely deterministic results in that |
| // sense is to apply some form of order() in these cases. |
| func SeedStrategy(config SeedStrategyConfig) TraversalStrategy { |
| configMap := map[string]interface{}{"seed": config.Seed} |
| return &traversalStrategy{name: decorationNamespace + "SeedStrategy", configuration: configMap} |
| } |
| |
| // SeedStrategyConfig provides configuration options for SeedStrategy. Zeroed (unset) values are used. |
| type SeedStrategyConfig struct { |
| Seed int64 |
| } |
| |
| // SubgraphStrategy provides a way to limit the view of a Traversal. By providing Traversal representations that |
| // represent a form of filtering criterion for Vertices and/or Edges, this strategy will inject that criterion into |
| // the appropriate places of a Traversal thus restricting what it Traverses and returns. |
| func SubgraphStrategy(config SubgraphStrategyConfig) TraversalStrategy { |
| configMap := make(map[string]interface{}) |
| if config.Vertices != nil { |
| configMap["vertices"] = config.Vertices |
| } |
| if config.Edges != nil { |
| configMap["edges"] = config.Edges |
| } |
| if config.VertexProperties != nil { |
| configMap["vertexProperties"] = config.VertexProperties |
| } |
| if config.CheckAdjacentVertices != nil { |
| configMap["checkAdjacentVertices"] = config.CheckAdjacentVertices.(bool) |
| } |
| return &traversalStrategy{name: decorationNamespace + "SubgraphStrategy", configuration: configMap} |
| } |
| |
| // SubgraphStrategyConfig provides configuration options for SubgraphStrategy. Zeroed (unset) values are ignored. |
| type SubgraphStrategyConfig struct { |
| Vertices *GraphTraversal |
| Edges *GraphTraversal |
| VertexProperties *GraphTraversal |
| CheckAdjacentVertices interface{} |
| } |
| |
| func VertexProgramStrategy(config VertexProgramStrategyConfig) TraversalStrategy { |
| configMap := make(map[string]interface{}) |
| if config.GraphComputer != "" { |
| configMap["graphComputer"] = config.GraphComputer |
| } |
| if config.Workers != 0 { |
| configMap["workers"] = config.Workers |
| } |
| if config.Persist != "" { |
| configMap["persist"] = config.Persist |
| } |
| if config.Result != "" { |
| configMap["result"] = config.Result |
| } |
| if config.Vertices != nil { |
| configMap["vertices"] = config.Vertices |
| } |
| if config.Edges != nil { |
| configMap["edges"] = config.Edges |
| } |
| for k, v := range config.Configuration { |
| configMap[k] = v |
| } |
| return &traversalStrategy{name: computerDecorationNamespace + "VertexProgramStrategy", configuration: configMap} |
| } |
| |
| // VertexProgramStrategyConfig provides configuration options for VertexProgramStrategy. |
| // Zeroed (unset) values are ignored. |
| type VertexProgramStrategyConfig struct { |
| GraphComputer string |
| Workers int |
| Persist string |
| Result string |
| Vertices *GraphTraversal |
| Edges *GraphTraversal |
| Configuration map[string]interface{} |
| } |
| |
| // Finalization strategies |
| |
| func MatchAlgorithmStrategy(config MatchAlgorithmStrategyConfig) TraversalStrategy { |
| configMap := make(map[string]interface{}) |
| if config.MatchAlgorithm != "" { |
| configMap["matchAlgorithm"] = config.MatchAlgorithm |
| } |
| return &traversalStrategy{name: finalizationNamespace + "MatchAlgorithmStrategy", configuration: configMap} |
| } |
| |
| // MatchAlgorithmStrategyConfig provides configuration options for MatchAlgorithmStrategy. |
| // Zeroed (unset) values are ignored. |
| type MatchAlgorithmStrategyConfig struct { |
| MatchAlgorithm string |
| } |
| |
| // Verification strategies |
| |
| // EdgeLabelVerificationStrategy does not allow Edge traversal steps to have no label specified. |
| // Providing one or more labels is considered to be a best practice, however, TinkerPop will not force |
| // the specification of Edge labels; instead, providers or users will have to enable this strategy explicitly. |
| func EdgeLabelVerificationStrategy(config EdgeLabelVerificationStrategyConfig) TraversalStrategy { |
| configMap := map[string]interface{}{ |
| "logWarning": config.LogWarning, |
| "throwException": config.ThrowExcecption, |
| } |
| |
| return &traversalStrategy{name: verificationNamespace + "EdgeLabelVerificationStrategy", configuration: configMap} |
| } |
| |
| // EdgeLabelVerificationStrategyConfig provides configuration options for EdgeLabelVerificationStrategy. |
| // Zeroed (unset) values are used. |
| type EdgeLabelVerificationStrategyConfig struct { |
| LogWarning bool |
| ThrowExcecption bool |
| } |
| |
| // LambdaRestrictionStrategy does not allow lambdas to be used in a Traversal. The contents of a lambda |
| // cannot be analyzed/optimized and thus, reduces the ability of other traversalStrategy instances to reason |
| // about the traversal. This strategy is not activated by default. However, graph system providers may choose |
| // to make this a default strategy in order to ensure their respective strategies are better able to operate. |
| func LambdaRestrictionStrategy() TraversalStrategy { |
| return &traversalStrategy{name: verificationNamespace + "LambdaRestrictionStrategy"} |
| } |
| |
| // ReadOnlyStrategy detects steps marked with Mutating and returns an error if one is found. |
| func ReadOnlyStrategy() TraversalStrategy { |
| return &traversalStrategy{name: verificationNamespace + "ReadOnlyStrategy"} |
| } |
| |
| // ReservedKeysVerificationStrategy detects property keys that should not be used by the traversal. |
| // A term may be reserved by a particular graph implementation or as a convention given best practices. |
| func ReservedKeysVerificationStrategy(config ReservedKeysVerificationStrategyConfig) TraversalStrategy { |
| configMap := map[string]interface{}{ |
| "logWarning": config.LogWarning, |
| "throwException": config.ThrowException, |
| } |
| if len(config.Keys) != 0 { |
| configMap["keys"] = config.Keys |
| } |
| return &traversalStrategy{name: verificationNamespace + "ReservedKeysVerificationStrategy", configuration: configMap} |
| } |
| |
| // ReservedKeysVerificationStrategyConfig provides configuration options for ReservedKeysVerificationStrategy. |
| // Zeroed (unset) values are used except Keys. |
| type ReservedKeysVerificationStrategyConfig struct { |
| LogWarning bool |
| ThrowException bool |
| Keys []string |
| } |
| |
| // Optimization strategies |
| |
| // AdjacentToIncidentStrategy looks for Vertex- and value-emitting steps followed by a CountGlobalStep and replaces |
| // the pattern with an Edge- or Property-emitting step followed by a CountGlobalStep. Furthermore, if a vertex- |
| // or value-emitting step is the last step in a .Has(traversal), .And(traversal, ...) or .Or(traversal, ...) |
| // child traversal, it is replaced by an appropriate Edge- or Property-emitting step. |
| // Performing this replacement removes situations where the more expensive trip to an adjacent Graph Element (e.g. |
| // the Vertex on the other side of an Edge) can be satisfied by trips to incident Graph Elements (e.g. just the Edge |
| // itself). |
| func AdjacentToIncidentStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "AdjacentToIncidentStrategy"} |
| } |
| |
| // ByModulatorOptimizationStrategy looks for standard traversals in By-modulators and replaces them with more |
| // optimized traversals (e.g. TokenTraversal) if possible. |
| func ByModulatorOptimizationStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "ByModulatorOptimizationStrategy"} |
| } |
| |
| // CountStrategy optimizes any occurrence of CountGlobalStep followed by an IsStep The idea is to limit |
| // the number of incoming elements in a way that it's enough for the IsStep to decide whether it evaluates |
| // true or false. If the traversal already contains a user supplied limit, the strategy won't modify it. |
| func CountStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "CountStrategy"} |
| } |
| |
| // EarlyLimitStrategy looks for RangeGlobalSteps that can be moved further left in the traversal and thus be applied |
| // earlier. It will also try to merge multiple RangeGlobalSteps into one. |
| // If the logical consequence of one or multiple RangeGlobalSteps is an empty result, the strategy will remove |
| // as many steps as possible and add a NoneStep instead. |
| func EarlyLimitStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "EarlyLimitStrategy"} |
| } |
| |
| // FilterRankingStrategy reorders filter- and order-steps according to their rank. Step ranks are defined within |
| // the strategy and indicate when it is reasonable for a step to move in front of another. It will also do its best to |
| // push step labels as far "right" as possible in order to keep Traversers as small and bulkable as possible prior to |
| // the absolute need for Path-labeling. |
| func FilterRankingStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "FilterRankingStrategy"} |
| } |
| |
| // IdentityRemovalStrategy looks for IdentityStep instances and removes them. |
| // If the identity step is labeled, its labels are added to the previous step. |
| // If the identity step is labeled and it's the first step in the traversal, it stays. |
| func IdentityRemovalStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "IdentityRemovalStrategy"} |
| } |
| |
| // IncidentToAdjacentStrategy looks for .OutE().InV(), .InE().OutV() and .BothE().OtherV() |
| // and replaces these step sequences with .Out(), .In() or .Both() respectively. |
| // The strategy won't modify the traversal if: |
| // |
| // the Edge step is labeled |
| // the traversal contains a Path step |
| // the traversal contains a Lambda step |
| func IncidentToAdjacentStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "IncidentToAdjacentStrategy"} |
| } |
| |
| // InlineFilterStrategy analyzes filter-steps with child traversals that themselves are pure filters. If |
| // the child traversals are pure filters then the wrapping parent filter is not needed and thus, the children |
| // can be "inlined". Normalizing pure filters with inlining reduces the number of variations of a filter that |
| // a graph provider may need to reason about when writing their own strategies. As a result, this strategy helps |
| // increase the likelihood that a provider's filtering optimization will succeed at re-writing the traversal. |
| func InlineFilterStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "InlineFilterStrategy"} |
| } |
| |
| // LazyBarrierStrategy is an OLTP-only strategy that automatically inserts a NoOpBarrierStep after every |
| // FlatMapStep if neither Path-tracking nor partial Path-tracking is required, and the next step is not the |
| // traversal's last step or a barrier. NoOpBarrierSteps allow Traversers to be bulked, thus this strategy |
| // is meant to reduce memory requirements and improve the overall query performance. |
| func LazyBarrierStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "LazyBarrierStrategy"} |
| } |
| |
| // MatchPredicateStrategy will fold any post-Where() step that maintains a traversal constraint into |
| // Match(). MatchStep is intelligent with traversal constraint applications and thus, can more |
| // efficiently use the constraint of WhereTraversalStep or WherePredicateStep. |
| func MatchPredicateStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "MatchPredicateStrategy"} |
| } |
| |
| // OrderLimitStrategy is an OLAP strategy that folds a RangeGlobalStep into a preceding |
| // OrderGlobalStep. This helps to eliminate traversers early in the traversal and can |
| // significantly reduce the amount of memory required by the OLAP execution engine. |
| func OrderLimitStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "OrderLimitStrategy"} |
| } |
| |
| // PathProcessorStrategy is an OLAP strategy that does its best to turn non-local children in Where() |
| // and Select() into local children by inlining components of the non-local child. In this way, |
| // PathProcessorStrategy helps to ensure that more traversals meet the local child constraint imposed |
| // on OLAP traversals. |
| func PathProcessorStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "PathProcessorStrategy"} |
| } |
| |
| // PathRetractionStrategy will remove Paths from the Traversers and increase the likelihood of bulking |
| // as Path data is not required after Select('b'). |
| func PathRetractionStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "PathRetractionStrategy"} |
| } |
| |
| // ProductiveByStrategy takes an argument of By() and wraps it CoalesceStep so that the result is either |
| // the initial Traversal argument or null. In this way, the By() is always "productive". This strategy |
| // is an "optimization" but it is perhaps more of a "decoration", but it should follow |
| // ByModulatorOptimizationStrategy which features optimizations relevant to this one. |
| func ProductiveByStrategy(config ProductiveByStrategyConfig) TraversalStrategy { |
| configMap := make(map[string]interface{}) |
| configMap["productiveKeys"] = config.ProductiveKeys |
| |
| return &traversalStrategy{name: optimizationNamespace + "ProductiveByStrategy", configuration: configMap} |
| } |
| |
| // ProductiveByStrategyConfig provides configuration options for ProductiveByStrategy. |
| // Zeroed (unset) values are used. |
| type ProductiveByStrategyConfig struct { |
| ProductiveKeys []string |
| } |
| |
| // RepeatUnrollStrategy is an OLTP-only strategy that unrolls any RepeatStep if it uses a constant |
| // number of loops (Times(x)) and doesn't emit intermittent elements. If any of the following 3 steps appears |
| // within the Repeat-traversal, the strategy will not be applied: |
| // |
| // DedupGlobalStep |
| // LoopsStep |
| // LambdaHolder |
| func RepeatUnrollStrategy() TraversalStrategy { |
| return &traversalStrategy{name: optimizationNamespace + "RepeatUnrollStrategy"} |
| } |
| |
| // RemoteStrategy reconstructs a Traversal by appending a RemoteStep to its end. That step will submit the Traversal to |
| // a RemoteConnection instance which will typically send it to a remote server for execution and return results. |
| func RemoteStrategy(connection DriverRemoteConnection) TraversalStrategy { |
| a := func(g GraphTraversal) { |
| result, err := g.GetResultSet() |
| if err != nil || result != nil { |
| return |
| } |
| |
| rs, err := connection.submitBytecode(g.Bytecode) |
| if err != nil { |
| return |
| } |
| g.results = rs |
| } |
| |
| return &traversalStrategy{name: "RemoteStrategy", apply: a} |
| } |