You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by co...@apache.org on 2026/09/15 17:11:02 UTC
(tinkerpop) branch TINKERPOP-3256 created (now 55a54a1eb9)
This is an automated email from the ASF dual-hosted git repository.
Cole-Greer pushed a change to branch TINKERPOP-3256
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
at 55a54a1eb9 Add variable-length path patterns to TinkerGQL
This branch includes the following new commits:
new 55a54a1eb9 Add variable-length path patterns to TinkerGQL
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(tinkerpop) 01/01: Add variable-length path patterns to TinkerGQL
Posted by co...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
Cole-Greer pushed a commit to branch TINKERPOP-3256
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit 55a54a1eb9be313697aae656a21f0d1ff5f32eec
Author: Cole Greer <co...@colegreer.ca>
AuthorDate: Tue Sep 15 10:04:17 2026 -0700
Add variable-length path patterns to TinkerGQL
Implement ISO GQL quantified-relationship syntax (a)-[r:label]->{m,n}(b)
in the TinkerGQL MATCH string form, with the {m}, {m,}, and + quantifier
forms, across directed, reverse, and undirected edges. Matching uses TRAIL
semantics (no repeated edge within a walk) and emits at every depth in the
range; the edge variable binds to the ordered List of traversed edges.
Grammar, model, planner, and the native DFS executor are extended for the
new syntax, with conformance scenarios, reference docs, and a CHANGELOG
entry.
Known limitations (documented): quantified edges are forward-expansion only
(a quantified edge closing a pattern cycle raises an error), zero-length
forms (*, {0,n}, {,n}) are not yet supported, and edge uniqueness is
enforced per-walk rather than across the whole match.
Assisted-by: Kiro:claude-opus-5
---
CHANGELOG.asciidoc | 3 +-
docs/src/reference/the-traversal.asciidoc | 81 ++++-
gql-gremlin/src/main/antlr4/GQL.g4 | 66 +++-
.../tinkerpop/gremlin/gql/DefaultGqlExecutor.java | 185 ++++++++--
.../tinkerpop/gremlin/gql/DefaultGqlPlanner.java | 74 ++--
.../tinkerpop/gremlin/gql/ExtensionStep.java | 71 +++-
.../apache/tinkerpop/gremlin/gql/GqlExecutor.java | 37 +-
.../apache/tinkerpop/gremlin/gql/GqlMatchStep.java | 35 +-
.../org/apache/tinkerpop/gremlin/gql/GqlRow.java | 56 +++
.../apache/tinkerpop/gremlin/gql/MatchState.java | 76 ++++
.../apache/tinkerpop/gremlin/gql/QueryEdge.java | 62 +++-
.../apache/tinkerpop/gremlin/gql/QueryGraph.java | 112 +++++-
.../tinkerpop/gremlin/gql/GqlGrammarTest.java | 45 +++
.../tinkerpop/gremlin/gql/QueryGraphTest.java | 139 ++++++++
.../gremlin-javascript/test/cucumber/gremlin.js | 7 +
.../gremlin/language/translator/translations.json | 191 ++++++++++
.../gremlin/test/features/map/MatchString.feature | 144 ++++++++
.../gremlin/gql/DefaultGqlExecutorTest.java | 388 +++++++++++++++++++--
.../gremlin/gql/DefaultGqlPlannerTest.java | 150 ++++++++
.../traversal/step/map/GqlMatchStepTest.java | 257 ++++++++++++++
20 files changed, 2036 insertions(+), 143 deletions(-)
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 0bbee74517..a49c6d9c36 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -125,7 +125,8 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
* Deprecated the traversal-based `match(Traversal[])` in favor of the new string-based API.
* Added the `gql-gremlin` module containing the TinkerGQL engine, a `MATCH`-pattern executor implementing a deliberate minimal subset of ISO GQL, usable by any graph provider.
* Added `Graph.countVerticesByLabel(String)`, `Graph.countEdgesByLabel(String)`, and the `Graph.Index` nested interface as performance-hint extension points for the TinkerGQL engine.
-* Added GQL support to TinkerGraph with `gql-gremlin`,
+* Added GQL support to TinkerGraph with `gql-gremlin`.
+* Added variable-length path patterns to TinkerGQL via the quantified-relationship form `(a)-[r:label]->{m,n}(b)` (also `{m}`, `{m,}`, and `+`), across directed, reverse, and undirected edges.
[[release-4-0-0-beta-2]]
=== TinkerPop 4.0.0-beta.2 (April 1, 2026)
diff --git a/docs/src/reference/the-traversal.asciidoc b/docs/src/reference/the-traversal.asciidoc
index 20f4888d7b..ff76be1b6a 100644
--- a/docs/src/reference/the-traversal.asciidoc
+++ b/docs/src/reference/the-traversal.asciidoc
@@ -3232,7 +3232,7 @@ provider-specific. See <<tinkergql>> below for the complete TinkerGQL syntax ref
TinkerGQL is the name for the `MATCH` dialect shipped in TinkerPop's optional `gql-gremlin` module.
It is a deliberate, minimal subset of link:https://www.iso.org/standard/76120.html[ISO GQL] `MATCH` syntax:
just enough to express graph pattern matching queries, with the more complex ISO GQL features, like `WHERE`,
-`RETURN`, variable-length paths, and aggregation functions, intentionally excluded. This keeps the grammar
+`RETURN`, and aggregation functions, intentionally excluded. This keeps the grammar
tight, the implementation portable, and the semantics unambiguous.
Any graph system provider may adopt TinkerGQL by depending on the `gql-gremlin` module. TinkerGraph
@@ -3450,6 +3450,83 @@ performs an index-backed seed lookup rather than a full scan. Whether `Graph.Ind
structure depends on the graph system; see <<tinkerpop-providers-tinkergql,the provider documentation>> and
your specific graph system's documentation for details.
+[[tinkergql-variable-length]]
+===== Variable-Length Path Patterns
+
+A relationship pattern can be quantified so that it matches a variable-length walk of repeated edges of the same
+shape rather than a single hop. The quantifier is written immediately after the closing arrow of the
+relationship, in the abbreviated form `(a)-[r:LABEL]->{q}(b)`. Four quantifier forms are supported, each with a
+lower bound of at least one:
+
+[width="100%",cols="2,4",options="header"]
+|=========================================================
+|Quantifier |Meaning
+|`{m,n}` |Between `m` and `n` repetitions, inclusive
+|`{m}` |Exactly `m` repetitions
+|`{m,}` |At least `m` repetitions, unbounded above
+|`+` |One or more repetitions, equivalent to `{1,}`
+|=========================================================
+
+Quantification is available on all three edge directions. The examples below use the modern toy graph, where the
+`knows` relationship forms only single-hop paths, so a bounded quantifier there resolves to the same immediate
+neighbours as an unquantified edge:
+
+[gremlin-groovy,modern]
+----
+g.match("MATCH (a:person)-[:knows]->{1,2}(b:person)").
+ select("a", "b").by("name")
+----
+
+The reverse form `<-[r:LABEL]-{q}` walks incoming edges, and the undirected form `-[r:LABEL]-{q}` walks edges in
+either direction:
+
+[gremlin-groovy,modern]
+----
+g.match("MATCH (b:person)<-[:knows]-{1}(a:person)").
+ select("a", "b").by("name")
+----
+
+*Semantics*
+
+A quantified relationship expands from its already-bound endpoint outward, one hop at a time, up to the maximum
+repetition count. Three properties define the result set. First, expansion follows *trail* semantics: within a
+single walk no edge is traversed more than once, which guarantees termination even in the presence of cycles.
+Vertices, by contrast, may repeat when reached through distinct edges. Second, expansion *emits at each depth*
+within the quantifier range. A walk that reaches a valid target at every depth from the lower bound to the upper
+bound produces one result row per depth, not only at the final depth. Third, the edge variable `r` binds as an
+ordered `List<Edge>`, a *group variable* holding every edge traversed on that walk, in walk order. A result
+row's list has one element for a depth-one match, two for a depth-two match, and so on.
+
+The following illustrates these semantics over a linear chain `a-[route]->b-[route]->c-[route]->d`, which the
+modern graph does not contain. A `{1,3}` quantifier anchored at `a` emits `b` at depth one, `c` at depth two, and
+`d` at depth three, with `r` accumulating the traversed edges at each depth:
+
+[source,text]
+----
+MATCH (a:airport {code: 'AAA'})-[r:route]->{1,3}(x:airport)
+
+// three result rows, one per depth:
+// x = BBB, r = [AAA->BBB]
+// x = CCC, r = [AAA->BBB, BBB->CCC]
+// x = DDD, r = [AAA->BBB, BBB->CCC, CCC->DDD]
+----
+
+A lower bound greater than one suppresses the shallower depths. Over the same chain, `{2,}` emits only `c` and `d`,
+while `+` (equivalent to `{1,}`) emits `b`, `c`, and `d`.
+
+*Limitations*
+
+Quantified relationships in the current release carry three restrictions:
+
+. *Forward expansion only.* A quantified edge expands outward from one bound endpoint to reach the other. A
+quantified edge whose endpoints are both already bound elsewhere in the pattern, one that closes a
+pattern cycle, is not yet supported and raises an error at plan time. Only unquantified edges may close a cycle.
+. *No zero-length forms.* Every quantifier must have a lower bound of at least one. The zero-length forms `*`,
+`{0,n}`, and `{,n}` are not yet supported and are rejected when the query is parsed or planned.
+. *Per-walk edge uniqueness only.* The trail (no-repeated-edge) guarantee applies within a single quantified
+walk. Edge uniqueness across an entire multi-pattern match is not enforced, so an edge traversed inside a
+quantified walk may also appear in another part of the same match.
+
===== Unsupported Features
TinkerGQL is a minimal subset of ISO GQL. The following ISO GQL `MATCH` features are not yet implemented:
@@ -3460,7 +3537,7 @@ TinkerGQL is a minimal subset of ISO GQL. The following ISO GQL `MATCH` features
|`WHERE` clause |Post-match filtering is not supported inside the `MATCH` string. Use Gremlin's `where()` step after `match()` instead.
|`RETURN` clause |Projection inside the `MATCH` string is not supported. Use `select()` after `match()` to project named variables.
|Inequality / range predicates |Only equality tests (`{key: value}`) are supported. Expressions like `n.age > 30` are not part of the grammar.
-|Variable-length paths |Quantified path patterns such as `(a)-[:KNOWS*1..3]->(b)` are not supported.
+|Zero-length and cyclic quantified paths |Quantified path patterns with a lower bound of at least one (`{m,n}`, `{m}`, `{m,}`, `+`) are supported (see <<tinkergql-variable-length>>). Zero-length forms (`*`, `{0,n}`, `{,n}`) and a quantified edge that closes a pattern cycle are not yet supported.
|Multiple labels per element |`(n:Person:Employee)` — more than one label per node pattern — is not supported.
|`OPTIONAL MATCH` |Optional pattern matching (outer joins) is not supported.
|Aggregation functions |`COUNT`, `SUM`, `AVG`, and similar functions are not part of the grammar.
diff --git a/gql-gremlin/src/main/antlr4/GQL.g4 b/gql-gremlin/src/main/antlr4/GQL.g4
index d60ac9d8a7..c23052789d 100644
--- a/gql-gremlin/src/main/antlr4/GQL.g4
+++ b/gql-gremlin/src/main/antlr4/GQL.g4
@@ -27,6 +27,9 @@
* - Directed edges: -[e:Label]-> or -[:Label]-> or -[e]-> or -[]->
* - Reverse directed edges: <-[e:Label]- or <-[:Label]- or <-[e]- or <-[]-
* - Undirected edges: -[e:Label]- or -[:Label]- or -[e]- or -[]-
+ * - Quantified relationships (trailing postfix, ISO GQL abbreviation form):
+ * -[:KNOWS]->{1,3} <-[:KNOWS]-{2,} -[:KNOWS]-{2}
+ * also {m}, {m,}, {,n}, * and + (e.g. -[:KNOWS]->{,3}, -[:KNOWS]->*)
* - Multiple comma-separated path patterns in a single MATCH clause
* - Inline property filters on nodes: (n:Label {key: 'value', count: 42i, flag: true, x: $param})
*
@@ -41,7 +44,7 @@
* Special: NaN, Infinity, +Infinity, -Infinity
* Params: $name (resolved from the params map at execution time)
*
- * Out of scope: WHERE clause, RETURN, path quantifiers.
+ * Out of scope: WHERE clause, RETURN.
*/
grammar GQL;
@@ -172,30 +175,71 @@ edgePattern
;
/**
- * Directed edge: -[var?:Label?]->
+ * Directed edge: -[var?:Label?]-> with an optional trailing quantifier
*
- * Example: -[e:KNOWS]->
+ * Examples: -[e:KNOWS]-> -[:KNOWS]->{1,3} -[:KNOWS]->*
*/
directedEdge
- : DASH LBRACKET elementPatternFiller RBRACKET ARROW
+ : DASH LBRACKET elementPatternFiller RBRACKET ARROW quantifier?
;
/**
- * Reverse directed edge: <-[var?:Label?]-
+ * Reverse directed edge: <-[var?:Label?]- with an optional trailing quantifier
*
- * Example: <-[e:KNOWS]-
+ * Examples: <-[e:KNOWS]- <-[:KNOWS]-{2,}
*/
reverseDirectedEdge
- : LARROW LBRACKET elementPatternFiller RBRACKET DASH
+ : LARROW LBRACKET elementPatternFiller RBRACKET DASH quantifier?
;
/**
- * Undirected edge: -[var?:Label?]-
+ * Undirected edge: -[var?:Label?]- with an optional trailing quantifier
*
- * Example: -[e:KNOWS]-
+ * Examples: -[e:KNOWS]- -[:KNOWS]-{2}
*/
undirectedEdge
- : DASH LBRACKET elementPatternFiller RBRACKET DASH
+ : DASH LBRACKET elementPatternFiller RBRACKET DASH quantifier?
+ ;
+
+/**
+ * A trailing quantifier on a relationship, in the ISO GQL quantified-relationship
+ * abbreviation form (a)-[r]->{q}(b). Grammar accepts all structural forms; semantic
+ * rules (zero lower bound, max < min) are enforced in downstream tasks, not here.
+ *
+ * Forms:
+ * {m,n} fixed lower and upper bound
+ * {m} exactly m
+ * {m,} at least m
+ * {,n} at most n
+ * * zero or more
+ * + one or more
+ *
+ * Bounds go through the dedicated unsignedInteger production rather than referencing a
+ * numeric token directly, keeping the intended "bare, unsigned, unsuffixed" contract in
+ * one place for downstream validation.
+ */
+quantifier
+ : LBRACE unsignedInteger COMMA unsignedInteger RBRACE // {m,n}
+ | LBRACE unsignedInteger RBRACE // {m}
+ | LBRACE unsignedInteger COMMA RBRACE // {m,}
+ | LBRACE COMMA unsignedInteger RBRACE // {,n}
+ | STAR // *
+ | PLUS // +
+ ;
+
+/**
+ * An unsigned-integer quantifier bound.
+ *
+ * A dedicated UNSIGNED_INTEGER lexer token (bare digits, no sign, no type suffix) would be
+ * the natural backing here, but a bare {@code [0-9]+} token is unreachable: for a bare digit
+ * sequence it ties with INTEGER_LITERAL, which must win so that property-filter values keep
+ * their INTEGER_LITERAL token type (QueryGraph relies on it, and is out of scope for this
+ * task). The bound therefore accepts INTEGER_LITERAL; a leading sign or type suffix is not
+ * meaningful for a bound and is left to downstream validation, alongside the zero-lower-bound
+ * and max < min checks.
+ */
+unsignedInteger
+ : INTEGER_LITERAL
;
/**
@@ -247,6 +291,8 @@ DASH : '-' ;
COLON : ':' ;
COMMA : ',' ;
DOLLAR : '$' ;
+STAR : '*' ;
+PLUS : '+' ;
/**
* Signed infinity: +Infinity or -Infinity.
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutor.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutor.java
index 57fd759ba4..aa5e4e0889 100644
--- a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutor.java
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutor.java
@@ -44,9 +44,10 @@ import java.util.Set;
* via {@link Graph.Index} when available), filtered by the seed label and seed property
* predicates. Each matching vertex is bound to the seed variable and used as the
* starting point for DFS extension.</li>
- * <li><strong>DFS extension</strong> — {@link #extend} is called recursively with a shared
- * {@code Element[]} binding array. Steps are selected from the remaining list using DAG
- * eligibility (anchor variable already bound), with BFS order as the tiebreaker.</li>
+ * <li><strong>DFS extension</strong>: {@link #extend} is called recursively with a shared
+ * {@link MatchState} holding the current partial match. Steps are selected from the
+ * remaining list using DAG eligibility (anchor variable already bound), with BFS order as
+ * the tiebreaker.</li>
* <li><strong>Lazy delivery</strong> — {@link #execute} returns an {@code Iterator} that
* advances the DFS one seed vertex at a time.</li>
* </ol>
@@ -68,38 +69,41 @@ public final class DefaultGqlExecutor implements GqlExecutor {
* Returns a lazy {@link Iterator} of result rows using an empty params map.
*/
@Override
- public Iterator<Element[]> execute(final GqlMatchPlan plan) {
+ public Iterator<GqlRow> execute(final GqlMatchPlan plan) {
return execute(plan, Collections.emptyMap());
}
/**
- * Returns a lazy {@link Iterator} of result rows. Each row is an {@code Element[]} whose
- * indices correspond to the variable index defined in the {@link GqlMatchPlan}.
+ * Returns a lazy {@link Iterator} of result rows. Each {@link GqlRow} carries a scalar
+ * {@code Element[]} ({@code row.scalars}) whose indices correspond to the variable index
+ * defined in the {@link GqlMatchPlan}, plus a side-channel map ({@code row.groups}) from
+ * variable index to the ordered {@code List<Edge>} bound to a quantified group edge variable.
*/
@Override
- public Iterator<Element[]> execute(final GqlMatchPlan plan, final Map<String, Object> params) {
+ public Iterator<GqlRow> execute(final GqlMatchPlan plan, final Map<String, Object> params) {
if (plan.getSeedVariable() == null) {
return Collections.emptyIterator();
}
final Iterator<Vertex> seedVertices = seedIterator(plan.getSeedLabel(),
plan.getSeedPredicates(), params);
- final ArrayDeque<Element[]> buffer = new ArrayDeque<>();
+ final ArrayDeque<GqlRow> buffer = new ArrayDeque<>();
- return new Iterator<Element[]>() {
+ return new Iterator<GqlRow>() {
@Override
public boolean hasNext() {
while (buffer.isEmpty() && seedVertices.hasNext()) {
final Vertex seed = seedVertices.next();
- final Element[] bindings = new Element[plan.getVariableCount()];
- bindings[plan.getSeedVariableIndex()] = seed;
- extend(bindings, plan, params, new ArrayList<>(plan.getSteps()), buffer);
+ final MatchState state = new MatchState(plan.getVariableCount());
+ state.setScalar(plan.getSeedVariableIndex(), seed);
+ extend(state, plan, params,
+ new ArrayList<>(plan.getSteps()), buffer);
}
return !buffer.isEmpty();
}
@Override
- public Element[] next() {
+ public GqlRow next() {
if (!hasNext()) throw new NoSuchElementException();
return buffer.poll();
}
@@ -196,13 +200,15 @@ public final class DefaultGqlExecutor implements GqlExecutor {
/**
* Recursively extends the current partial match using DAG-aware step selection and
- * array-based bindings with in-place backtracking.
+ * array-based bindings with in-place backtracking. The current match is carried in a single
+ * {@link MatchState}, which keeps scalar variable bindings in a flat array and group
+ * edge-variable bindings in a side map.
*/
- private void extend(final Element[] bindings, final GqlMatchPlan plan,
- final Map<String, Object> params,
- final List<ExtensionStep> remaining, final ArrayDeque<Element[]> results) {
+ private void extend(final MatchState state,
+ final GqlMatchPlan plan, final Map<String, Object> params,
+ final List<ExtensionStep> remaining, final ArrayDeque<GqlRow> results) {
if (remaining.isEmpty()) {
- results.add(bindings.clone());
+ results.add(state.snapshot());
return;
}
@@ -213,7 +219,7 @@ public final class DefaultGqlExecutor implements GqlExecutor {
long chosenCost = Long.MAX_VALUE;
for (int i = 0; i < remaining.size(); i++) {
final ExtensionStep candidate = remaining.get(i);
- if (bindings[plan.getIndex(candidate.getAnchorVariable())] == null) continue;
+ if (state.getScalar(plan.getIndex(candidate.getAnchorVariable())) == null) continue;
final double ratio = candidate.selectivityRatio();
final long cost = candidate.getEstimatedCost();
if (chosenIdx < 0
@@ -231,7 +237,18 @@ public final class DefaultGqlExecutor implements GqlExecutor {
final ExtensionStep step = remaining.remove(chosenIdx);
step.recordAttempt();
- final Vertex anchor = (Vertex) bindings[plan.getIndex(step.getAnchorVariable())];
+ final Vertex anchor = (Vertex) state.getScalar(plan.getIndex(step.getAnchorVariable()));
+
+ // Quantified (variable-length) step: expand as a bounded/unbounded multi-hop walk with
+ // per-walk TRAIL edge-uniqueness and emit-at-each-depth. See extendQuantified(...).
+ if (step.isQuantified()) {
+ final int qEdgeIdx = step.getEdgeVariable() != null ? plan.getIndex(step.getEdgeVariable()) : -1;
+ final int qTargetIdx = step.getTargetVariable() != null ? plan.getIndex(step.getTargetVariable()) : -1;
+ extendQuantified(state, plan, params, remaining, results, step, anchor,
+ qEdgeIdx, qTargetIdx, new ArrayDeque<>(), new HashSet<>(), 0);
+ remaining.add(chosenIdx, step);
+ return;
+ }
final Iterator<Edge> candidates = step.getEdgeLabel() != null
? anchor.edges(step.getDirection(), step.getEdgeLabel())
@@ -240,6 +257,10 @@ public final class DefaultGqlExecutor implements GqlExecutor {
final int edgeIdx = step.getEdgeVariable() != null ? plan.getIndex(step.getEdgeVariable()) : -1;
final int targetIdx = step.getTargetVariable() != null ? plan.getIndex(step.getTargetVariable()) : -1;
+ // A group edge variable always surfaces as a List<Edge>, so it is written through the
+ // group channel and never participates in the scalar edge-reuse join below.
+ final boolean edgeIsGroup = step.isEdgeVariableGroup() && edgeIdx >= 0;
+
final Set<Vertex> seenAnonymousTargets = edgeIdx < 0 ? new HashSet<>() : null;
while (candidates.hasNext()) {
@@ -248,7 +269,7 @@ public final class DefaultGqlExecutor implements GqlExecutor {
if (!matchesPredicates(edge, step.getEdgePredicates(), params))
continue;
- if (edgeIdx >= 0 && bindings[edgeIdx] != null && !bindings[edgeIdx].equals(edge))
+ if (!edgeIsGroup && edgeIdx >= 0 && state.getScalar(edgeIdx) != null && !state.getScalar(edgeIdx).equals(edge))
continue;
final Vertex target = targetVertex(anchor, edge, step.getDirection());
@@ -259,36 +280,132 @@ public final class DefaultGqlExecutor implements GqlExecutor {
if (!matchesPredicates(target, step.getTargetPredicates(), params))
continue;
- final boolean writeEdge = edgeIdx >= 0 && bindings[edgeIdx] == null;
+ final boolean writeEdge = !edgeIsGroup && edgeIdx >= 0 && state.getScalar(edgeIdx) == null;
- if (targetIdx >= 0 && bindings[targetIdx] != null) {
- if (!bindings[targetIdx].equals(target)) continue;
+ if (targetIdx >= 0 && state.getScalar(targetIdx) != null) {
+ if (!state.getScalar(targetIdx).equals(target)) continue;
- if (writeEdge) {
- bindings[edgeIdx] = edge;
+ if (edgeIsGroup) {
+ state.putGroup(edgeIdx, java.util.List.of(edge));
step.recordHit();
- extend(bindings, plan, params, remaining, results);
- bindings[edgeIdx] = null;
+ extend(state, plan, params, remaining, results);
+ state.removeGroup(edgeIdx);
+ } else if (writeEdge) {
+ state.setScalar(edgeIdx, edge);
+ step.recordHit();
+ extend(state, plan, params, remaining, results);
+ state.clearScalar(edgeIdx);
} else {
step.recordHit();
- extend(bindings, plan, params, remaining, results);
+ extend(state, plan, params, remaining, results);
if (edgeIdx < 0) break;
}
} else {
if (seenAnonymousTargets != null && !seenAnonymousTargets.add(target)) continue;
- if (writeEdge) bindings[edgeIdx] = edge;
- if (targetIdx >= 0) bindings[targetIdx] = target;
+ if (edgeIsGroup) state.putGroup(edgeIdx, java.util.List.of(edge));
+ else if (writeEdge) state.setScalar(edgeIdx, edge);
+ if (targetIdx >= 0) state.setScalar(targetIdx, target);
step.recordHit();
- extend(bindings, plan, params, remaining, results);
- if (writeEdge) bindings[edgeIdx] = null;
- if (targetIdx >= 0) bindings[targetIdx] = null;
+ extend(state, plan, params, remaining, results);
+ if (edgeIsGroup) state.removeGroup(edgeIdx);
+ else if (writeEdge) state.clearScalar(edgeIdx);
+ if (targetIdx >= 0) state.clearScalar(targetIdx);
}
}
remaining.add(chosenIdx, step);
}
+ /**
+ * Expands a quantified (variable-length) {@link ExtensionStep} from {@code anchor} as a
+ * depth-first walk, emitting a match at every depth in {@code [minHops, maxHops]}.
+ *
+ * <p>The walk enforces per-walk TRAIL edge-uniqueness: an edge is never traversed twice
+ * within the same walk (tracked in {@code visitedEdges}, with {@code path} preserving order).
+ * Vertices are deliberately not gated, so they may repeat via distinct edges such as parallel
+ * edges, triangles, and self-loops. Because edges cannot repeat, an unbounded walk always
+ * terminates on a finite graph, so no depth cap is needed.</p>
+ *
+ * <p>The group edge list is carried in the {@link MatchState} side map keyed by
+ * {@code edgeIdx} rather than in the scalar array, so the scalar bindings stay homogeneous.
+ * Its save/restore mirrors the scalar save/restore so backtracking never leaks a walk's edge
+ * list into a sibling branch.</p>
+ *
+ * @param depth number of edges already on {@code path} (walk depth of {@code current})
+ */
+ private void extendQuantified(final MatchState state,
+ final GqlMatchPlan plan, final Map<String, Object> params,
+ final List<ExtensionStep> remaining, final ArrayDeque<GqlRow> results,
+ final ExtensionStep step, final Vertex current,
+ final int edgeIdx, final int targetIdx,
+ final ArrayDeque<Edge> path, final Set<Edge> visitedEdges,
+ final int depth) {
+ final int minHops = step.getMinHops();
+ final int maxHops = step.getMaxHops();
+
+ final Iterator<Edge> candidates = step.getEdgeLabel() != null
+ ? current.edges(step.getDirection(), step.getEdgeLabel())
+ : current.edges(step.getDirection());
+
+ while (candidates.hasNext()) {
+ final Edge edge = candidates.next();
+
+ // TRAIL edge-uniqueness (walk-local): never traverse the same edge twice.
+ if (visitedEdges.contains(edge))
+ continue;
+
+ if (!matchesPredicates(edge, step.getEdgePredicates(), params))
+ continue;
+
+ final Vertex next = targetVertex(current, edge, step.getDirection());
+
+ path.addLast(edge);
+ visitedEdges.add(edge);
+ final int newDepth = depth + 1;
+
+ // Emit at this depth when it is within [minHops, maxHops] and the target constraints
+ // on `next` pass. Emit-at-each-depth: a single branch may emit at multiple depths.
+ if (newDepth >= minHops
+ && (step.getTargetLabel() == null || step.getTargetLabel().equals(next.label()))
+ && matchesPredicates(next, step.getTargetPredicates(), params)) {
+
+ final boolean targetPrebound = targetIdx >= 0 && state.getScalar(targetIdx) != null;
+ if (!targetPrebound || state.getScalar(targetIdx).equals(next)) {
+ final Element savedTarget = targetIdx >= 0 ? state.getScalar(targetIdx) : null;
+
+ if (targetIdx >= 0) state.setScalar(targetIdx, next);
+
+ // Group edge variable: carry the ordered walk edges in the side map, not in
+ // the scalar array. Skip entirely for an anonymous quantified edge.
+ final boolean writeGroup = edgeIdx >= 0;
+ final List<Edge> savedGroup = writeGroup ? state.getGroup(edgeIdx) : null;
+ if (writeGroup) state.putGroup(edgeIdx, List.copyOf(path));
+
+ step.recordHit();
+ extend(state, plan, params, remaining, results);
+
+ if (writeGroup) {
+ if (savedGroup != null) state.putGroup(edgeIdx, savedGroup);
+ else state.removeGroup(edgeIdx);
+ }
+ if (targetIdx >= 0) state.setScalar(targetIdx, savedTarget);
+ }
+ }
+
+ // Descend one hop deeper when below the (possibly unbounded) upper bound. A shorter
+ // path that failed the target constraint may still be a prefix of a longer match.
+ if (maxHops == ExtensionStep.UNBOUNDED || newDepth < maxHops) {
+ extendQuantified(state, plan, params, remaining, results, step, next,
+ edgeIdx, targetIdx, path, visitedEdges, newDepth);
+ }
+
+ // Backtrack the walk.
+ visitedEdges.remove(edge);
+ path.removeLast();
+ }
+ }
+
// -------------------------------------------------------------------------
// Predicate evaluation
// -------------------------------------------------------------------------
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlanner.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlanner.java
index e85986ad24..ef847ab6ea 100644
--- a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlanner.java
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlanner.java
@@ -211,6 +211,9 @@ public final class DefaultGqlPlanner implements GqlPlanner {
*
* <p>Back edges (both endpoints already visited) are still emitted as steps so the
* executor can verify the join constraint against the already-bound variable.
+ *
+ * <p>Quantified edges are forward-only: a quantified edge classified as a back edge
+ * (closing a pattern cycle) raises an {@link IllegalArgumentException}.
*/
private List<ExtensionStep> buildSteps(final QueryGraph queryGraph,
final QueryVertex seed,
@@ -256,42 +259,52 @@ public final class DefaultGqlPlanner implements GqlPlanner {
anchor = current;
targetNode = current;
stepDir = edge.getDirection();
- } else if (isSource) {
- final QueryVertex other = edge.getTarget();
- if (!visitOrder.containsKey(other)) {
- // Forward edge: current → other
- anchor = current;
- targetNode = other;
- stepDir = edge.getDirection();
- } else {
- // Back edge: pick the earlier-visited node as anchor
- if (currentOrder <= visitOrder.get(other)) {
+ } else {
+ final QueryVertex other = isSource ? edge.getTarget() : edge.getSource();
+ final boolean isBackEdge = visitOrder.containsKey(other);
+
+ // Back-edge guard: quantified edges are forward-only. A quantified edge that
+ // closes a pattern cycle (both endpoints already visited) is not yet supported.
+ if (isBackEdge && edge.isQuantified()) {
+ throw new IllegalArgumentException(
+ "quantified edges closing a pattern cycle are not yet supported");
+ }
+
+ if (isSource) {
+ if (!isBackEdge) {
+ // Forward edge: current → other
anchor = current;
targetNode = other;
stepDir = edge.getDirection();
} else {
- anchor = other;
- targetNode = current;
- stepDir = flip(edge.getDirection());
+ // Back edge: pick the earlier-visited node as anchor
+ if (currentOrder <= visitOrder.get(other)) {
+ anchor = current;
+ targetNode = other;
+ stepDir = edge.getDirection();
+ } else {
+ anchor = other;
+ targetNode = current;
+ stepDir = flip(edge.getDirection());
+ }
}
- }
- } else { // isTarget
- final QueryVertex other = edge.getSource();
- if (!visitOrder.containsKey(other)) {
- // Forward edge (reversed): current ← other → emit as current traverses back
- anchor = current;
- targetNode = other;
- stepDir = flip(edge.getDirection());
- } else {
- // Back edge: pick the earlier-visited node as anchor
- if (visitOrder.get(other) <= currentOrder) {
- anchor = other;
- targetNode = current;
- stepDir = edge.getDirection();
- } else {
+ } else { // isTarget
+ if (!isBackEdge) {
+ // Forward edge (reversed): current ← other → emit as current traverses back
anchor = current;
targetNode = other;
stepDir = flip(edge.getDirection());
+ } else {
+ // Back edge: pick the earlier-visited node as anchor
+ if (visitOrder.get(other) <= currentOrder) {
+ anchor = other;
+ targetNode = current;
+ stepDir = edge.getDirection();
+ } else {
+ anchor = current;
+ targetNode = other;
+ stepDir = flip(edge.getDirection());
+ }
}
}
}
@@ -305,7 +318,10 @@ public final class DefaultGqlPlanner implements GqlPlanner {
targetNode.getLabel(),
effectiveVars.get(targetNode),
targetNode.getPredicates(),
- estimateStepCost(edge, targetNode)));
+ estimateStepCost(edge, targetNode),
+ edge.getMinHops(),
+ edge.getMaxHops(),
+ edge.isEdgeVariableGroup()));
if (!visitOrder.containsKey(targetNode)) {
visitOrder.put(targetNode, visitCounter++);
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/ExtensionStep.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/ExtensionStep.java
index 91b454164c..aed5bb75aa 100644
--- a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/ExtensionStep.java
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/ExtensionStep.java
@@ -58,6 +58,13 @@ import java.util.concurrent.atomic.AtomicLong;
*/
public final class ExtensionStep {
+ /**
+ * Sentinel {@link #getMaxHops()} value denoting an open-ended upper bound, used for the
+ * {@code {m,}} and {@code +} quantifier forms. Mirrors {@link QueryEdge#UNBOUNDED} so plan
+ * and model layers agree on the open-ended sentinel.
+ */
+ public static final int UNBOUNDED = QueryEdge.UNBOUNDED;
+
private final String anchorVariable;
private final String edgeLabel;
private final Direction direction;
@@ -67,6 +74,9 @@ public final class ExtensionStep {
private final String targetVariable;
private final List<PropertyPredicate> targetPredicates;
private final long estimatedCost;
+ private final int minHops;
+ private final int maxHops;
+ private final boolean edgeVariableIsGroup;
private final AtomicLong attempts = new AtomicLong(0);
private final AtomicLong hits = new AtomicLong(0);
@@ -76,7 +86,9 @@ public final class ExtensionStep {
final List<PropertyPredicate> edgePredicates,
final String targetLabel, final String targetVariable,
final List<PropertyPredicate> targetPredicates,
- final long estimatedCost) {
+ final long estimatedCost,
+ final int minHops, final int maxHops,
+ final boolean edgeVariableIsGroup) {
if (anchorVariable == null) throw new IllegalArgumentException("anchorVariable must not be null");
this.anchorVariable = anchorVariable;
this.edgeLabel = edgeLabel;
@@ -91,6 +103,19 @@ public final class ExtensionStep {
? Collections.emptyList()
: Collections.unmodifiableList(new ArrayList<>(targetPredicates));
this.estimatedCost = estimatedCost;
+ this.minHops = minHops;
+ this.maxHops = maxHops;
+ this.edgeVariableIsGroup = edgeVariableIsGroup;
+ }
+
+ public ExtensionStep(final String anchorVariable, final String edgeLabel,
+ final Direction direction, final String edgeVariable,
+ final List<PropertyPredicate> edgePredicates,
+ final String targetLabel, final String targetVariable,
+ final List<PropertyPredicate> targetPredicates,
+ final long estimatedCost) {
+ this(anchorVariable, edgeLabel, direction, edgeVariable, edgePredicates,
+ targetLabel, targetVariable, targetPredicates, estimatedCost, 1, 1, false);
}
public ExtensionStep(final String anchorVariable, final String edgeLabel,
@@ -99,7 +124,7 @@ public final class ExtensionStep {
final List<PropertyPredicate> targetPredicates,
final long estimatedCost) {
this(anchorVariable, edgeLabel, direction, edgeVariable, Collections.emptyList(),
- targetLabel, targetVariable, targetPredicates, estimatedCost);
+ targetLabel, targetVariable, targetPredicates, estimatedCost, 1, 1, false);
}
public ExtensionStep(final String anchorVariable, final String edgeLabel,
@@ -107,14 +132,14 @@ public final class ExtensionStep {
final String targetLabel, final String targetVariable,
final List<PropertyPredicate> targetPredicates) {
this(anchorVariable, edgeLabel, direction, edgeVariable, Collections.emptyList(),
- targetLabel, targetVariable, targetPredicates, Long.MAX_VALUE);
+ targetLabel, targetVariable, targetPredicates, Long.MAX_VALUE, 1, 1, false);
}
public ExtensionStep(final String anchorVariable, final String edgeLabel,
final Direction direction, final String edgeVariable,
final String targetLabel, final String targetVariable) {
this(anchorVariable, edgeLabel, direction, edgeVariable, Collections.emptyList(),
- targetLabel, targetVariable, Collections.emptyList(), Long.MAX_VALUE);
+ targetLabel, targetVariable, Collections.emptyList(), Long.MAX_VALUE, 1, 1, false);
}
/** The variable name of the already-bound vertex used as the starting point for this step. */
@@ -171,6 +196,40 @@ public final class ExtensionStep {
return estimatedCost;
}
+ /**
+ * Returns the minimum number of hops this step traverses. For a plain, non-quantified
+ * single-hop step this is {@code 1}.
+ */
+ public int getMinHops() {
+ return minHops;
+ }
+
+ /**
+ * Returns the maximum number of hops this step traverses, or {@link #UNBOUNDED} for the
+ * open-ended quantifier forms ({@code {m,}} and {@code +}). For a plain, non-quantified
+ * single-hop step this is {@code 1}.
+ */
+ public int getMaxHops() {
+ return maxHops;
+ }
+
+ /**
+ * Returns {@code true} if this step carries a variable-length quantifier (e.g. {@code {1,3}},
+ * {@code +}, {@code {2,}}), as opposed to a plain single hop. Derived from the hop bounds:
+ * a step is quantified unless {@code minHops == 1 && maxHops == 1}.
+ */
+ public boolean isQuantified() {
+ return !(minHops == 1 && maxHops == 1);
+ }
+
+ /**
+ * Returns {@code true} if this step's edge variable is a group variable, modelled as a
+ * per-variable flag. For non-quantified steps this is {@code false}.
+ */
+ public boolean isEdgeVariableGroup() {
+ return edgeVariableIsGroup;
+ }
+
// -------------------------------------------------------------------------
// Adaptive runtime counters
// -------------------------------------------------------------------------
@@ -202,6 +261,10 @@ public final class ExtensionStep {
", dir=" + direction +
", target=" + (targetVariable != null ? targetVariable : "_") +
(targetLabel != null ? ":" + targetLabel : "") +
+ (isQuantified()
+ ? ", hops={" + minHops + "," + (maxHops == UNBOUNDED ? "" : maxHops) + "}" +
+ (edgeVariableIsGroup ? ", group" : "")
+ : "") +
(targetPredicates.isEmpty() ? "" : ", filters=" + targetPredicates) + "}";
}
}
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlExecutor.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlExecutor.java
index 3c465cb2b4..abfdfe0e37 100644
--- a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlExecutor.java
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlExecutor.java
@@ -18,33 +18,19 @@
*/
package org.apache.tinkerpop.gremlin.gql;
-import org.apache.tinkerpop.gremlin.structure.Element;
-
import java.util.Iterator;
import java.util.Map;
/**
- * Executes a {@link GqlMatchPlan} against a graph and returns result rows.
- *
- * <p>Each result row is an {@code Element[]} whose indices correspond to the variable indices
- * defined in the plan; use {@link GqlMatchPlan#getVariables()} to map indices back to variable
- * names. The seed variable is always at index 0.</p>
- *
- * <p>{@link DefaultGqlExecutor} is the reference implementation. It iterates seed vertices via
- * a full scan or an index lookup when
- * {@link org.apache.tinkerpop.gremlin.structure.Graph.Index} is available, then performs DFS
- * backtracking over the plan's extension steps using the TinkerPop
- * {@link org.apache.tinkerpop.gremlin.structure.Graph} API ({@code Vertex.edges()},
- * {@code Edge.inVertex()}, etc.).</p>
+ * Executes a {@link GqlMatchPlan} against a graph and returns a lazy iterator of {@link GqlRow}
+ * result rows. {@link DefaultGqlExecutor} is the reference implementation.
*
* <h3>When to implement this interface</h3>
*
* <p>This is the primary customization point for providers with a native query or traversal
- * engine. Such a provider can keep {@link DefaultGqlPlanner} — getting free GQL MATCH parsing
- * and cardinality-guided join ordering driven by the {@code countVerticesByLabel},
- * {@code countEdgesByLabel}, and {@link org.apache.tinkerpop.gremlin.structure.Graph.Index}
- * overrides already on the graph — and replace only the executor to translate the resulting
- * {@link GqlMatchPlan} into native operations instead of iterating {@code Graph.vertices()}.</p>
+ * engine. Such a provider can keep {@link DefaultGqlPlanner}, getting GQL MATCH parsing and
+ * cardinality-guided join ordering for free, and replace only the executor to translate the
+ * {@link GqlMatchPlan} into native operations.</p>
*
* <p>The contract for implementors:</p>
* <ul>
@@ -52,9 +38,8 @@ import java.util.Map;
* <li>For each seed, extend the partial match through the plan's
* {@link GqlMatchPlan#getSteps() extension steps} in an order that keeps every step's
* anchor variable bound before that step executes.</li>
- * <li>Emit one {@code Element[]} per complete match, with each slot filled according to
- * {@link GqlMatchPlan#getVariables()}, seed variable at index 0.</li>
- * <li>Return results lazily — do not materialise the full result set in memory.</li>
+ * <li>Emit one {@link GqlRow} per complete match, populated as described on {@link GqlRow}.</li>
+ * <li>Return results lazily rather than materialising the full result set in memory.</li>
* </ul>
*/
public interface GqlExecutor {
@@ -63,9 +48,9 @@ public interface GqlExecutor {
* Executes the plan with no parameter bindings.
*
* @param plan the compiled execution plan
- * @return a lazy iterator of binding arrays
+ * @return a lazy iterator of result rows
*/
- Iterator<Element[]> execute(GqlMatchPlan plan);
+ Iterator<GqlRow> execute(GqlMatchPlan plan);
/**
* Executes the plan with the given parameter bindings.
@@ -73,7 +58,7 @@ public interface GqlExecutor {
* @param plan the compiled execution plan
* @param params parameter bindings for {@code $name} references in property predicates;
* may be empty if the query contains no parameter references
- * @return a lazy iterator of binding arrays
+ * @return a lazy iterator of result rows
*/
- Iterator<Element[]> execute(GqlMatchPlan plan, Map<String, Object> params);
+ Iterator<GqlRow> execute(GqlMatchPlan plan, Map<String, Object> params);
}
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlMatchStep.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlMatchStep.java
index 137039c756..72d66a6433 100644
--- a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlMatchStep.java
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlMatchStep.java
@@ -23,12 +23,14 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.DeclarativeMatchStep;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import org.apache.tinkerpop.gremlin.process.traversal.util.FastNoSuchElementException;
+import org.apache.tinkerpop.gremlin.structure.Edge;
import org.apache.tinkerpop.gremlin.structure.Element;
import org.apache.tinkerpop.gremlin.structure.Graph;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
+import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
@@ -65,7 +67,7 @@ public final class GqlMatchStep<S> extends DeclarativeMatchStep<S> {
private GqlExecutor executor;
private GqlMatchPlan plan;
// Lazy row source: one iterator per spawn execution or per incoming mid-traversal traverser.
- private Iterator<Element[]> rowIterator = null;
+ private Iterator<GqlRow> rowIterator = null;
// For mid-traversal: the upstream traverser whose rows rowIterator is currently serving.
private Traverser.Admin<S> currentStart = null;
private boolean done = false;
@@ -184,7 +186,7 @@ public final class GqlMatchStep<S> extends DeclarativeMatchStep<S> {
}
@SuppressWarnings({"unchecked", "rawtypes"})
- private Traverser.Admin<Map<String, Object>> rowToSpawnTraverser(final Element[] row, final GqlMatchPlan plan) {
+ private Traverser.Admin<Map<String, Object>> rowToSpawnTraverser(final GqlRow row, final GqlMatchPlan plan) {
final Traverser.Admin<Map<String, Object>> traverser =
this.getTraversal().getTraverserGenerator().generate(Collections.emptyMap(), (Step) this, 1L);
bindRow(row, plan, (Traverser.Admin) traverser);
@@ -192,7 +194,7 @@ public final class GqlMatchStep<S> extends DeclarativeMatchStep<S> {
}
@SuppressWarnings({"unchecked", "rawtypes"})
- private Traverser.Admin<Map<String, Object>> rowToSplitTraverser(final Element[] row, final GqlMatchPlan plan,
+ private Traverser.Admin<Map<String, Object>> rowToSplitTraverser(final GqlRow row, final GqlMatchPlan plan,
final Traverser.Admin<S> start) {
final Traverser.Admin<Map<String, Object>> split =
(Traverser.Admin<Map<String, Object>>) start.split(Collections.emptyMap(), (Step) this);
@@ -201,17 +203,32 @@ public final class GqlMatchStep<S> extends DeclarativeMatchStep<S> {
}
@SuppressWarnings({"unchecked", "rawtypes"})
- private void bindRow(final Element[] row, final GqlMatchPlan plan,
+ private void bindRow(final GqlRow row, final GqlMatchPlan plan,
final Traverser.Admin traverser) {
+ // Surface both binding channels the executor produces:
+ // - row.scalars[i] : a single graph Element for a scalar variable, or null.
+ // - row.groups.get(i) : the ordered List<Edge> for a group edge variable.
+ // A given variable index is EITHER a scalar or a group for one match, never both. Every
+ // bound named variable is written to two channels that select() can read, using the SAME
+ // value instance so they always agree: the emitted binding Map (the traverser's final
+ // current object) and the traverser path label of that name. A group edge variable
+ // resolves to the whole List<Edge> from row.groups in both channels; a scalar variable
+ // resolves to a single Element from row.scalars.
+ final Element[] scalars = row.scalars;
+ final Map<Integer, List<Edge>> groups = row.groups;
final String[] variables = plan.getVariables();
final Map<String, Object> bindings = new LinkedHashMap<>();
for (int i = 0; i < variables.length; i++) {
final String var = variables[i];
- if (!var.startsWith(GqlMatchPlan.ANON_VAR_PREFIX) && row[i] != null) {
- traverser.set(row[i]);
- traverser.addLabels(Collections.singleton(var));
- bindings.put(var, row[i]);
- }
+ if (var.startsWith(GqlMatchPlan.ANON_VAR_PREFIX))
+ continue;
+ // Group list takes precedence for its index; otherwise fall back to the scalar slot.
+ final Object value = groups.containsKey(i) ? groups.get(i) : scalars[i];
+ if (value == null)
+ continue;
+ traverser.set(value);
+ traverser.addLabels(Collections.singleton(var));
+ bindings.put(var, value);
}
traverser.set(bindings);
}
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlRow.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlRow.java
new file mode 100644
index 0000000000..6f0aa62171
--- /dev/null
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/GqlRow.java
@@ -0,0 +1,56 @@
+/*
+ * 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.gql;
+
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Element;
+
+import java.util.List;
+import java.util.Map;
+
+/**
+ * An immutable result row produced by a {@link GqlExecutor}. It carries two parallel channels
+ * keyed by the variable index defined in the {@link GqlMatchPlan}:
+ *
+ * <ul>
+ * <li>{@link #scalars}: the flat {@code Element[]} of scalar bindings. Each slot holds a single
+ * graph {@link Element} (or {@code null} when the variable is unbound). Group (list)
+ * variables are carried separately, so this array holds only real graph elements.</li>
+ * <li>{@link #groups}: a side map from variable index to the ordered {@code List<Edge>} bound
+ * to a group edge variable produced by a quantified (variable-length) relationship pattern.
+ * Non-quantified matches carry an empty map.</li>
+ * </ul>
+ *
+ * <p>Keeping group lists out of the scalar array lets the executor keep a homogeneous
+ * {@code Element[]} with simple backtracking while still surfacing variable-length walks as
+ * selectable {@code List<Edge>} values.</p>
+ */
+final class GqlRow {
+
+ /** Scalar bindings by variable index; each slot is a single graph {@link Element} or {@code null}. */
+ final Element[] scalars;
+
+ /** Group edge-variable bindings by variable index; empty for non-quantified matches. */
+ final Map<Integer, List<Edge>> groups;
+
+ GqlRow(final Element[] scalars, final Map<Integer, List<Edge>> groups) {
+ this.scalars = scalars;
+ this.groups = groups;
+ }
+}
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/MatchState.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/MatchState.java
new file mode 100644
index 0000000000..0a00e098b5
--- /dev/null
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/MatchState.java
@@ -0,0 +1,76 @@
+/*
+ * 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.gql;
+
+import org.apache.tinkerpop.gremlin.structure.Edge;
+import org.apache.tinkerpop.gremlin.structure.Element;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Holds the current partial match during DFS backtracking: scalar variable bindings in a flat
+ * array and group (list) edge-variable bindings in a side map, both keyed by the plan's variable
+ * index. {@link #snapshot()} produces an immutable {@link GqlRow} for emission.
+ */
+final class MatchState {
+
+ private final Element[] scalars;
+ private final Map<Integer, List<Edge>> groups;
+
+ MatchState(final int variableCount) {
+ this.scalars = new Element[variableCount];
+ this.groups = new HashMap<>();
+ }
+
+ Element getScalar(final int i) {
+ return scalars[i];
+ }
+
+ void setScalar(final int i, final Element e) {
+ scalars[i] = e;
+ }
+
+ void clearScalar(final int i) {
+ scalars[i] = null;
+ }
+
+ List<Edge> getGroup(final int i) {
+ return groups.get(i);
+ }
+
+ void putGroup(final int i, final List<Edge> edges) {
+ groups.put(i, edges);
+ }
+
+ void removeGroup(final int i) {
+ groups.remove(i);
+ }
+
+ /**
+ * Returns an immutable {@link GqlRow} snapshot of this state. The scalar array is cloned and
+ * the group side map is copied so later backtracking mutations do not alias the emitted row.
+ */
+ GqlRow snapshot() {
+ return new GqlRow(scalars.clone(),
+ groups.isEmpty() ? Collections.emptyMap() : Map.copyOf(groups));
+ }
+}
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryEdge.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryEdge.java
index 161a55f76a..2e0f9a850e 100644
--- a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryEdge.java
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryEdge.java
@@ -38,16 +38,26 @@ import java.util.List;
*/
public final class QueryEdge {
+ /**
+ * Sentinel {@link #getMaxHops()} value denoting an open-ended upper bound, used for the
+ * {@code {m,}} and {@code +} quantifier forms (i.e. "at least {@code minHops}, no ceiling").
+ */
+ public static final int UNBOUNDED = Integer.MAX_VALUE;
+
private final String variable;
private final String label;
private final Direction direction;
private final QueryVertex source;
private final QueryVertex target;
private final List<PropertyPredicate> predicates;
+ private final int minHops;
+ private final int maxHops;
+ private final boolean edgeVariableIsGroup;
public QueryEdge(final String variable, final String label, final Direction direction,
final QueryVertex source, final QueryVertex target,
- final List<PropertyPredicate> predicates) {
+ final List<PropertyPredicate> predicates,
+ final int minHops, final int maxHops, final boolean edgeVariableIsGroup) {
this.variable = variable;
this.label = label;
this.direction = direction;
@@ -56,11 +66,21 @@ public final class QueryEdge {
this.predicates = predicates.isEmpty()
? Collections.emptyList()
: Collections.unmodifiableList(new ArrayList<>(predicates));
+ this.minHops = minHops;
+ this.maxHops = maxHops;
+ this.edgeVariableIsGroup = edgeVariableIsGroup;
+ }
+
+ public QueryEdge(final String variable, final String label, final Direction direction,
+ final QueryVertex source, final QueryVertex target,
+ final List<PropertyPredicate> predicates) {
+ // Non-quantified edge: exactly one hop, edge variable is not a group variable.
+ this(variable, label, direction, source, target, predicates, 1, 1, false);
}
public QueryEdge(final String variable, final String label, final Direction direction,
final QueryVertex source, final QueryVertex target) {
- this(variable, label, direction, source, target, Collections.emptyList());
+ this(variable, label, direction, source, target, Collections.emptyList(), 1, 1, false);
}
/**
@@ -106,6 +126,39 @@ public final class QueryEdge {
return predicates;
}
+ /**
+ * Returns the minimum number of hops this edge pattern matches. For a plain, non-quantified
+ * edge this is {@code 1}.
+ */
+ public int getMinHops() {
+ return minHops;
+ }
+
+ /**
+ * Returns the maximum number of hops this edge pattern matches, or {@link #UNBOUNDED} for the
+ * open-ended forms ({@code {m,}} and {@code +}). For a plain, non-quantified edge this is {@code 1}.
+ */
+ public int getMaxHops() {
+ return maxHops;
+ }
+
+ /**
+ * Returns {@code true} if this edge carries a variable-length quantifier (e.g. {@code {1,3}},
+ * {@code +}, {@code {2,}}), as opposed to a plain single-hop edge.
+ */
+ public boolean isQuantified() {
+ return !(minHops == 1 && maxHops == 1);
+ }
+
+ /**
+ * Returns {@code true} if this edge's variable is a group variable, modelled as a per-variable
+ * flag. The edge variable becomes a group variable exactly when the edge is quantified and has
+ * a (non-{@code null}) variable name.
+ */
+ public boolean isEdgeVariableGroup() {
+ return edgeVariableIsGroup;
+ }
+
@Override
public String toString() {
final StringBuilder sb = new StringBuilder();
@@ -123,6 +176,11 @@ public final class QueryEdge {
} else {
sb.append("]-");
}
+ if (isQuantified()) {
+ sb.append('{').append(minHops).append(',');
+ if (maxHops != UNBOUNDED) sb.append(maxHops);
+ sb.append('}');
+ }
sb.append(target);
return sb.toString();
}
diff --git a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryGraph.java b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryGraph.java
index d9323ee5dc..a81ac1851b 100644
--- a/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryGraph.java
+++ b/gql-gremlin/src/main/java/org/apache/tinkerpop/gremlin/gql/QueryGraph.java
@@ -26,8 +26,6 @@ import org.antlr.v4.runtime.Recognizer;
import org.antlr.v4.runtime.atn.PredictionMode;
import org.antlr.v4.runtime.misc.ParseCancellationException;
import org.apache.tinkerpop.gremlin.structure.Direction;
-import org.apache.tinkerpop.gremlin.gql.GQLLexer;
-import org.apache.tinkerpop.gremlin.gql.GQLParser;
import java.math.BigDecimal;
import java.math.BigInteger;
@@ -162,7 +160,14 @@ public final class QueryGraph {
final Direction dir = extractDirection(edgeCtx);
final List<PropertyPredicate> edgePredicates = extractEdgePredicates(edgeCtx);
- edges.add(new QueryEdge(edgeVar, edgeLabel, dir, current, next, edgePredicates));
+ final GQLParser.QuantifierContext quantifierCtx = getQuantifier(edgeCtx);
+ final int[] bounds = extractQuantifier(quantifierCtx);
+ // The edge variable becomes a group variable exactly when the edge is quantified
+ // and carries a (non-null) variable name.
+ final boolean edgeVariableIsGroup = quantifierCtx != null && edgeVar != null;
+
+ edges.add(new QueryEdge(edgeVar, edgeLabel, dir, current, next, edgePredicates,
+ bounds[0], bounds[1], edgeVariableIsGroup));
current = next;
}
}
@@ -380,6 +385,107 @@ public final class QueryGraph {
return null;
}
+ /**
+ * Reaches the trailing quantifier off whichever edge subtype is present, mirroring
+ * {@link #getEdgeFiller}'s dispatch. Returns {@code null} when the edge has no quantifier.
+ */
+ private static GQLParser.QuantifierContext getQuantifier(final GQLParser.EdgePatternContext ctx) {
+ if (ctx.reverseDirectedEdge() != null) return ctx.reverseDirectedEdge().quantifier();
+ if (ctx.directedEdge() != null) return ctx.directedEdge().quantifier();
+ if (ctx.undirectedEdge() != null) return ctx.undirectedEdge().quantifier();
+ return null;
+ }
+
+ /**
+ * Interprets a parsed {@code quantifier} context into its {@code [minHops, maxHops]} bounds,
+ * validating the semantic rules that the grammar deliberately does not enforce.
+ *
+ * <p>Grammar forms: {@code {m,n}}->[m,n]; {@code {m}}->[m,m]; {@code {m,}}->[m,UNBOUNDED];
+ * {@code {,n}}->[0,n]; {@code *}->[0,UNBOUNDED]; {@code +}->[1,UNBOUNDED]. An absent quantifier
+ * ({@code null} context) is a plain single-hop edge -> [1,1].
+ *
+ * <p>Rejected here:
+ * <ul>
+ * <li>{@code max < min}, which is never valid.</li>
+ * <li>A bound whose token text is not a bare non-negative decimal, such as a leading sign or
+ * a numeric type suffix (both admitted by the INTEGER_LITERAL backing), which is never
+ * valid.</li>
+ * <li>A zero lower bound ({@code {0,..}}, {@code {,n}}, {@code *}), which is valid GQL but not
+ * yet supported and rejected with a distinct "not yet supported" message.</li>
+ * </ul>
+ */
+ private static int[] extractQuantifier(final GQLParser.QuantifierContext ctx) {
+ if (ctx == null) return new int[]{1, 1};
+
+ final int min;
+ final int max;
+ if (ctx.STAR() != null) {
+ min = 0;
+ max = QueryEdge.UNBOUNDED;
+ } else if (ctx.PLUS() != null) {
+ min = 1;
+ max = QueryEdge.UNBOUNDED;
+ } else {
+ final List<GQLParser.UnsignedIntegerContext> bounds = ctx.unsignedInteger();
+ final boolean hasComma = ctx.COMMA() != null;
+ if (bounds.size() == 2) {
+ // {m,n}
+ min = parseBound(bounds.get(0));
+ max = parseBound(bounds.get(1));
+ } else if (!hasComma) {
+ // {m}
+ min = parseBound(bounds.get(0));
+ max = min;
+ } else {
+ // Either {m,} or {,n}; distinguish by whether the bound precedes the comma.
+ final GQLParser.UnsignedIntegerContext bound = bounds.get(0);
+ final boolean boundBeforeComma =
+ bound.getStop().getTokenIndex() < ctx.COMMA().getSymbol().getTokenIndex();
+ if (boundBeforeComma) {
+ // {m,}
+ min = parseBound(bound);
+ max = QueryEdge.UNBOUNDED;
+ } else {
+ // {,n}
+ min = 0;
+ max = parseBound(bound);
+ }
+ }
+ }
+
+ // (a) never valid: max < min.
+ if (max < min)
+ throw new IllegalArgumentException(
+ "invalid quantifier bounds: upper bound (" + renderBound(max)
+ + ") is less than lower bound (" + min + ")");
+
+ // (c) deferred: zero lower bound (min == 0), i.e. *, {0,n}, {,n}. Valid GQL, not yet supported.
+ if (min == 0)
+ throw new IllegalArgumentException(
+ "zero-length paths (min bound 0, including * and {0,n}/{,n}) are not yet supported");
+
+ return new int[]{min, max};
+ }
+
+ /**
+ * Parses a single quantifier bound, rejecting anything that is not a bare non-negative decimal.
+ * The bound is backed by INTEGER_LITERAL, which also admits a leading sign and a numeric type
+ * suffix (e.g. {@code -1}, {@code 3i}); those are never valid as a quantifier bound and are
+ * rejected on the raw token text before {@link Integer#parseInt}.
+ */
+ private static int parseBound(final GQLParser.UnsignedIntegerContext ctx) {
+ final String text = ctx.getText();
+ if (!text.matches("[0-9]+"))
+ throw new IllegalArgumentException(
+ "invalid quantifier bound '" + text
+ + "': bounds must be bare non-negative integers (no sign or type suffix)");
+ return Integer.parseInt(text);
+ }
+
+ private static String renderBound(final int bound) {
+ return bound == QueryEdge.UNBOUNDED ? "unbounded" : Integer.toString(bound);
+ }
+
@Override
public String toString() {
return "QueryGraph{nodes=" + nodes + ", edges=" + edges + "}";
diff --git a/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/GqlGrammarTest.java b/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/GqlGrammarTest.java
index a7f50e327b..4df839be06 100644
--- a/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/GqlGrammarTest.java
+++ b/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/GqlGrammarTest.java
@@ -186,6 +186,39 @@ public class GqlGrammarTest {
{"MATCH (n {limit: Infinity})"},
{"MATCH (n {limit: +Infinity})"},
{"MATCH (n {limit: -Infinity})"},
+
+ // ── Quantified relationships: directed edges -[...]->{q} ──────────────
+ {"MATCH (a)-[:KNOWS]->{1,3}(b)"},
+ {"MATCH (a)-[:KNOWS]->{2,}(b)"},
+ {"MATCH (a)-[:KNOWS]->{,3}(b)"},
+ {"MATCH (a)-[:KNOWS]->{2}(b)"},
+ {"MATCH (a)-[:KNOWS]->*(b)"},
+ {"MATCH (a)-[:KNOWS]->+(b)"},
+ // Zero lower bound parses structurally (semantic check deferred downstream)
+ {"MATCH (a)-[:KNOWS]->{0,3}(b)"},
+ // max < min parses structurally (semantic validation is handled by QueryGraph, not the grammar)
+ {"MATCH (a)-[:KNOWS]->{3,1}(b)"},
+
+ // ── Quantified relationships: reverse directed edges <-[...]-{q} ───────
+ {"MATCH (a)<-[:KNOWS]-{1,3}(b)"},
+ {"MATCH (a)<-[:KNOWS]-{2,}(b)"},
+ {"MATCH (a)<-[:KNOWS]-{,3}(b)"},
+ {"MATCH (a)<-[:KNOWS]-{2}(b)"},
+ {"MATCH (a)<-[:KNOWS]-*(b)"},
+ {"MATCH (a)<-[:KNOWS]-+(b)"},
+
+ // ── Quantified relationships: undirected edges -[...]-{q} ─────────────
+ {"MATCH (a)-[:KNOWS]-{1,3}(b)"},
+ {"MATCH (a)-[:KNOWS]-{2,}(b)"},
+ {"MATCH (a)-[:KNOWS]-{,3}(b)"},
+ {"MATCH (a)-[:KNOWS]-{2}(b)"},
+ {"MATCH (a)-[:KNOWS]-*(b)"},
+ {"MATCH (a)-[:KNOWS]-+(b)"},
+
+ // ── Quantified relationships: with edge variable + label ──────────────
+ {"MATCH (a)-[r:KNOWS]->{1,3}(b)"},
+ {"MATCH (a)-[r]->{2,}(b)"},
+ {"MATCH (a:Person)-[r:KNOWS]->{1,3}(b:Person)"},
});
}
@@ -231,6 +264,18 @@ public class GqlGrammarTest {
assertThrows(ParseCancellationException.class, () -> parse("MATCH (n"));
}
+ @Test
+ public void shouldRejectEmptyQuantifier() {
+ // {} has no bound and is structurally invalid
+ assertThrows(ParseCancellationException.class, () -> parse("MATCH (a)-[:KNOWS]->{}(b)"));
+ }
+
+ @Test
+ public void shouldRejectMalformedQuantifier() {
+ // a bare comma with no bounds is not a valid quantifier
+ assertThrows(ParseCancellationException.class, () -> parse("MATCH (a)-[:KNOWS]->{,}(b)"));
+ }
+
private void parse(final String input) {
final GQLLexer lexer = new GQLLexer(CharStreams.fromString(input));
lexer.removeErrorListeners();
diff --git a/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/QueryGraphTest.java b/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/QueryGraphTest.java
index afd47a21f9..089d22fded 100644
--- a/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/QueryGraphTest.java
+++ b/gql-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/QueryGraphTest.java
@@ -361,4 +361,143 @@ public class QueryGraphTest {
assertTrue("message should include character position",
msg.contains("character position at"));
}
+
+ /**
+ * Asserts a semantic (model-build) error whose wrapped message contains {@code expectedFragment}.
+ * These are thrown as {@link IllegalArgumentException} during parse-tree walking and are wrapped
+ * with the standard "Failed to parse GQL MATCH expression" prefix. Unlike pure syntax
+ * errors, they carry no ANTLR "character position" text.
+ */
+ private static void assertSemanticError(final String gql, final String expectedFragment) {
+ final IllegalArgumentException ex = assertThrows(IllegalArgumentException.class,
+ () -> QueryGraph.parse(gql));
+ final String msg = ex.getMessage();
+ assertTrue("message '" + msg + "' should contain: " + expectedFragment,
+ msg.contains(expectedFragment));
+ }
+
+ // -------------------------------------------------------------------------
+ // Variable-length quantifier parsing (TINKERPOP-3256)
+ // -------------------------------------------------------------------------
+
+ @Test
+ public void testQuantifiedRangeOutEdge() {
+ final QueryGraph g = QueryGraph.parse("MATCH (a)-[r:KNOWS]->{1,3}(b)");
+ assertEquals(1, g.getEdges().size());
+ final QueryEdge e = g.getEdges().get(0);
+ assertEquals(1, e.getMinHops());
+ assertEquals(3, e.getMaxHops());
+ assertTrue(e.isQuantified());
+ assertTrue(e.isEdgeVariableGroup());
+ assertEquals(Direction.OUT, e.getDirection());
+ assertEquals("a", e.getSource().getVariable());
+ assertEquals("b", e.getTarget().getVariable());
+ assertEquals("KNOWS", e.getLabel());
+ assertEquals("r", e.getVariable());
+ }
+
+ @Test
+ public void testQuantifiedExact() {
+ final QueryGraph g = QueryGraph.parse("MATCH (a)-[:KNOWS]->{2}(b)");
+ final QueryEdge e = g.getEdges().get(0);
+ assertEquals(2, e.getMinHops());
+ assertEquals(2, e.getMaxHops());
+ assertTrue(e.isQuantified());
+ }
+
+ @Test
+ public void testQuantifiedPlus() {
+ final QueryGraph g = QueryGraph.parse("MATCH (a)-[:KNOWS]->+(b)");
+ final QueryEdge e = g.getEdges().get(0);
+ assertEquals(1, e.getMinHops());
+ assertEquals(QueryEdge.UNBOUNDED, e.getMaxHops());
+ assertTrue(e.isQuantified());
+ }
+
+ @Test
+ public void testQuantifiedAtLeast() {
+ final QueryGraph g = QueryGraph.parse("MATCH (a)-[:KNOWS]->{2,}(b)");
+ final QueryEdge e = g.getEdges().get(0);
+ assertEquals(2, e.getMinHops());
+ assertEquals(QueryEdge.UNBOUNDED, e.getMaxHops());
+ assertTrue(e.isQuantified());
+ }
+
+ @Test
+ public void testQuantifiedReverseDirection() {
+ final QueryGraph g = QueryGraph.parse("MATCH (a)<-[r:KNOWS]-{1,3}(b)");
+ final QueryEdge e = g.getEdges().get(0);
+ assertEquals(Direction.IN, e.getDirection());
+ assertEquals(1, e.getMinHops());
+ assertEquals(3, e.getMaxHops());
+ assertTrue(e.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testQuantifiedUndirected() {
+ final QueryGraph g = QueryGraph.parse("MATCH (a)-[r:KNOWS]-{2}(b)");
+ final QueryEdge e = g.getEdges().get(0);
+ assertEquals(Direction.BOTH, e.getDirection());
+ assertEquals(2, e.getMinHops());
+ assertEquals(2, e.getMaxHops());
+ assertTrue(e.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testQuantifiedAnonymousEdgeIsNotGroupVariable() {
+ // Quantified but no variable name -> not a group variable.
+ final QueryGraph g = QueryGraph.parse("MATCH (a)-[:KNOWS]->{1,3}(b)");
+ final QueryEdge e = g.getEdges().get(0);
+ assertTrue(e.isQuantified());
+ assertTrue("anonymous quantified edge must not be a group variable", !e.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testNonQuantifiedEdgeDefaults() {
+ // Regression guard: a plain edge is exactly one hop and not a group variable.
+ final QueryGraph g = QueryGraph.parse("MATCH (a)-[:KNOWS]->(b)");
+ final QueryEdge e = g.getEdges().get(0);
+ assertEquals(1, e.getMinHops());
+ assertEquals(1, e.getMaxHops());
+ assertTrue("plain edge must not be quantified", !e.isQuantified());
+ assertTrue("plain edge must not be a group variable", !e.isEdgeVariableGroup());
+ }
+
+ // -------------------------------------------------------------------------
+ // Quantifier semantic validation (never-valid forms)
+ // -------------------------------------------------------------------------
+
+ @Test
+ public void testQuantifierMaxLessThanMinThrows() {
+ assertSemanticError("MATCH (a)-[:KNOWS]->{3,1}(b)", "less than lower bound");
+ }
+
+ @Test
+ public void testQuantifierSignedBoundThrows() {
+ assertSemanticError("MATCH (a)-[:KNOWS]->{-1,3}(b)", "bare non-negative integers");
+ }
+
+ @Test
+ public void testQuantifierTypeSuffixBoundThrows() {
+ assertSemanticError("MATCH (a)-[:KNOWS]->{3i}(b)", "bare non-negative integers");
+ }
+
+ // -------------------------------------------------------------------------
+ // Quantifier zero-lower-bound deferral (valid GQL, not yet supported)
+ // -------------------------------------------------------------------------
+
+ @Test
+ public void testQuantifierZeroLowerBoundRangeThrows() {
+ assertSemanticError("MATCH (a)-[:KNOWS]->{0,3}(b)", "not yet supported");
+ }
+
+ @Test
+ public void testQuantifierUpperOnlyThrows() {
+ assertSemanticError("MATCH (a)-[:KNOWS]->{,3}(b)", "not yet supported");
+ }
+
+ @Test
+ public void testQuantifierStarThrows() {
+ assertSemanticError("MATCH (a)-[:KNOWS]->*(b)", "not yet supported");
+ }
}
diff --git a/gremlin-js/gremlin-javascript/test/cucumber/gremlin.js b/gremlin-js/gremlin-javascript/test/cucumber/gremlin.js
index 69d1632c39..e5d6ab438a 100644
--- a/gremlin-js/gremlin-javascript/test/cucumber/gremlin.js
+++ b/gremlin-js/gremlin-javascript/test/cucumber/gremlin.js
@@ -1461,6 +1461,13 @@ const gremlins = {
g_match_multiPattern_bridgeVariable_selectXa_b_sX_byXnameX: [function({g}) { return g.match("MATCH (a:person)-[:knows]->(b:person), (b:person)-[:created]->(s:software)").select("a", "b", "s").by("name") }],
g_match_personXknowsXeVar_weight_1X_person_selectXa_e_bX: [function({g}) { return g.match("MATCH (a:person)-[e:knows {weight: 1.0}]->(b:person)").select("a", "e", "b") }],
g_match_anyXknowsX_any_selectXaX_byXnameX_concatXconstant_selectXbX_byXnameXX: [function({g}) { return g.match("MATCH (a)-[:knows]->(b)").select("a").by("name").concat(__.constant(" knows "), __.select("b").by("name")) }],
+ g_match_personXknows_1_2X_person_selectXa_bX_byXnameX: [function({g}) { return g.match("MATCH (a:person)-[:knows]->{1,2}(b:person)").select("a", "b").by("name") }],
+ g_match_chainXroute_1_2X_selectXbX_byXcodeX: [function({g}) { return g.addV("airport").property("code", "AAA").as("a").addV("airport").property("code", "BBB").as("b").addV("airport").property("code", "CCC").as("c").addV("airport").property("code", "DDD").as("d").addE("route").from_("a").to("b").addE("route").from_("b").to("c").addE("route").from_("c").to("d") }, function({g}) { return g.match("MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)").select("b").by("code") }],
+ g_match_chainXroute_2_X_selectXbX_byXcodeX: [function({g}) { return g.addV("airport").property("code", "AAA").as("a").addV("airport").property("code", "BBB").as("b").addV("airport").property("code", "CCC").as("c").addV("airport").property("code", "DDD").as("d").addE("route").from_("a").to("b").addE("route").from_("b").to("c").addE("route").from_("c").to("d") }, function({g}) { return g.match("MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)").select("b").by("code") }],
+ g_match_chainXroute_plusX_selectXbX_byXcodeX: [function({g}) { return g.addV("airport").property("code", "AAA").as("a").addV("airport").property("code", "BBB").as("b").addV("airport").property("code", "CCC").as("c").addV("airport").property("code", "DDD").as("d").addE("route").from_("a").to("b").addE("route").from_("b").to("c").addE("route").from_("c").to("d") }, function({g}) { return g.match("MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)").select("b").by("code") }],
+ g_match_chainXreverseRoute_1_2X_selectXbX_byXcodeX: [function({g}) { return g.addV("airport").property("code", "AAA").as("a").addV("airport").property("code", "BBB").as("b").addV("airport").property("code", "CCC").as("c").addV("airport").property("code", "DDD").as("d").addE("route").from_("a").to("b").addE("route").from_("b").to("c").addE("route").from_("c").to("d") }, function({g}) { return g.match("MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)").select("b").by("code") }],
+ g_match_chainXundirectedRoute_1X_selectXbX_byXcodeX: [function({g}) { return g.addV("airport").property("code", "AAA").as("a").addV("airport").property("code", "BBB").as("b").addV("airport").property("code", "CCC").as("c").addV("airport").property("code", "DDD").as("d").addE("route").from_("a").to("b").addE("route").from_("b").to("c").addE("route").from_("c").to("d") }, function({g}) { return g.match("MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)").select("b").by("code") }],
+ g_match_chainXroute_2X_selectXrX: [function({g}) { return g.addV("airport").property("name", "AAA").as("a").addV("airport").property("name", "BBB").as("b").addV("airport").property("name", "CCC").as("c").addV("airport").property("name", "DDD").as("d").addE("route").from_("a").to("b").addE("route").from_("b").to("c").addE("route").from_("c").to("d") }, function({g}) { return g.match("MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)").select("r") }],
g_V_outE_mathX0_minus_itX_byXweightX: [function({g}) { return g.V().outE().math("0-_").by("weight") }],
g_V_hasXageX_valueMap_mathXit_plus_itXbyXselectXageX_unfoldXX: [function({g}) { return g.V().has("age").valueMap().math("_+_").by(__.select("age").unfold()) }],
g_V_asXaX_outXknowsX_asXbX_mathXa_plus_bX_byXageX: [function({g}) { return g.V().as("a").out("knows").as("b").math("a + b").by("age") }],
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json
index efd55f89ad..e72363d8d4 100644
--- a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/language/translator/translations.json
@@ -28182,6 +28182,197 @@
}
]
},
+ {
+ "scenario": "g_match_personXknows_1_2X_person_selectXa_bX_byXnameX",
+ "traversals": [
+ {
+ "original": "g.match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").select(\"a\",\"b\").by(\"name\")",
+ "language": "g.match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").select(\"a\", \"b\").by(\"name\")",
+ "canonical": "g.match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").select(\"a\", \"b\").by(\"name\")",
+ "anonymized": "g.match(string0).select(string1, string2).by(string3)",
+ "dotnet": "g.Match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").Select<object>(\"a\", \"b\").By(\"name\")",
+ "go": "g.Match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").Select(\"a\", \"b\").By(\"name\")",
+ "groovy": "g.match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").select(\"a\", \"b\").by(\"name\")",
+ "java": "g.match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").select(\"a\", \"b\").by(\"name\")",
+ "javascript": "g.match(\"MATCH (a:person)-[:knows]->{1,2}(b:person)\").select(\"a\", \"b\").by(\"name\")",
+ "python": "g.match('MATCH (a:person)-[:knows]->{1,2}(b:person)').select('a', 'b').by('name')"
+ }
+ ]
+ },
+ {
+ "scenario": "g_match_chainXroute_1_2X_selectXbX_byXcodeX",
+ "traversals": [
+ {
+ "original": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "language": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "canonical": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "anonymized": "g.addV(string0).property(string1, string2).as(string3).addV(string0).property(string1, string4).as(string5).addV(string0).property(string1, string6).as(string7).addV(string0).property(string1, string8).as(string9).addE(string10).from(string3).to(string5).addE(string10).from(string5).to(string7).addE(string10).from(string7).to(string9)",
+ "dotnet": "g.AddV((string) \"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV((string) \"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV((string) \"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV((string) \"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE((string) \"route\").From(\"a\").To(\"b\").AddE((string) \"route\").From(\"b\").To(\"c\").AddE((string) \"route\").From(\"c\").To(\"d\")",
+ "go": "g.AddV(\"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV(\"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV(\"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV(\"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE(\"route\").From(\"a\").To(\"b\").AddE(\"route\").From(\"b\").To(\"c\").AddE(\"route\").From(\"c\").To(\"d\")",
+ "groovy": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "java": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "javascript": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from_(\"a\").to(\"b\").addE(\"route\").from_(\"b\").to(\"c\").addE(\"route\").from_(\"c\").to(\"d\")",
+ "python": "g.add_v('airport').property('code', 'AAA').as_('a').add_v('airport').property('code', 'BBB').as_('b').add_v('airport').property('code', 'CCC').as_('c').add_v('airport').property('code', 'DDD').as_('d').add_e('route').from_('a').to('b').add_e('route').from_('b').to('c').add_e('route').from_('c').to('d')"
+ },
+ {
+ "original": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "language": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "canonical": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "anonymized": "g.match(string0).select(string1).by(string2)",
+ "dotnet": "g.Match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").Select<object>(\"b\").By(\"code\")",
+ "go": "g.Match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").Select(\"b\").By(\"code\")",
+ "groovy": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "java": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "javascript": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "python": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)\").select('b').by('code')"
+ }
+ ]
+ },
+ {
+ "scenario": "g_match_chainXroute_2_X_selectXbX_byXcodeX",
+ "traversals": [
+ {
+ "original": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "language": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "canonical": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "anonymized": "g.addV(string0).property(string1, string2).as(string3).addV(string0).property(string1, string4).as(string5).addV(string0).property(string1, string6).as(string7).addV(string0).property(string1, string8).as(string9).addE(string10).from(string3).to(string5).addE(string10).from(string5).to(string7).addE(string10).from(string7).to(string9)",
+ "dotnet": "g.AddV((string) \"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV((string) \"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV((string) \"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV((string) \"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE((string) \"route\").From(\"a\").To(\"b\").AddE((string) \"route\").From(\"b\").To(\"c\").AddE((string) \"route\").From(\"c\").To(\"d\")",
+ "go": "g.AddV(\"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV(\"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV(\"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV(\"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE(\"route\").From(\"a\").To(\"b\").AddE(\"route\").From(\"b\").To(\"c\").AddE(\"route\").From(\"c\").To(\"d\")",
+ "groovy": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "java": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "javascript": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from_(\"a\").to(\"b\").addE(\"route\").from_(\"b\").to(\"c\").addE(\"route\").from_(\"c\").to(\"d\")",
+ "python": "g.add_v('airport').property('code', 'AAA').as_('a').add_v('airport').property('code', 'BBB').as_('b').add_v('airport').property('code', 'CCC').as_('c').add_v('airport').property('code', 'DDD').as_('d').add_e('route').from_('a').to('b').add_e('route').from_('b').to('c').add_e('route').from_('c').to('d')"
+ },
+ {
+ "original": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").select(\"b\").by(\"code\")",
+ "language": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").select(\"b\").by(\"code\")",
+ "canonical": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").select(\"b\").by(\"code\")",
+ "anonymized": "g.match(string0).select(string1).by(string2)",
+ "dotnet": "g.Match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").Select<object>(\"b\").By(\"code\")",
+ "go": "g.Match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").Select(\"b\").By(\"code\")",
+ "groovy": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").select(\"b\").by(\"code\")",
+ "java": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").select(\"b\").by(\"code\")",
+ "javascript": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").select(\"b\").by(\"code\")",
+ "python": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)\").select('b').by('code')"
+ }
+ ]
+ },
+ {
+ "scenario": "g_match_chainXroute_plusX_selectXbX_byXcodeX",
+ "traversals": [
+ {
+ "original": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "language": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "canonical": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "anonymized": "g.addV(string0).property(string1, string2).as(string3).addV(string0).property(string1, string4).as(string5).addV(string0).property(string1, string6).as(string7).addV(string0).property(string1, string8).as(string9).addE(string10).from(string3).to(string5).addE(string10).from(string5).to(string7).addE(string10).from(string7).to(string9)",
+ "dotnet": "g.AddV((string) \"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV((string) \"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV((string) \"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV((string) \"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE((string) \"route\").From(\"a\").To(\"b\").AddE((string) \"route\").From(\"b\").To(\"c\").AddE((string) \"route\").From(\"c\").To(\"d\")",
+ "go": "g.AddV(\"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV(\"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV(\"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV(\"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE(\"route\").From(\"a\").To(\"b\").AddE(\"route\").From(\"b\").To(\"c\").AddE(\"route\").From(\"c\").To(\"d\")",
+ "groovy": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "java": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "javascript": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from_(\"a\").to(\"b\").addE(\"route\").from_(\"b\").to(\"c\").addE(\"route\").from_(\"c\").to(\"d\")",
+ "python": "g.add_v('airport').property('code', 'AAA').as_('a').add_v('airport').property('code', 'BBB').as_('b').add_v('airport').property('code', 'CCC').as_('c').add_v('airport').property('code', 'DDD').as_('d').add_e('route').from_('a').to('b').add_e('route').from_('b').to('c').add_e('route').from_('c').to('d')"
+ },
+ {
+ "original": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").select(\"b\").by(\"code\")",
+ "language": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").select(\"b\").by(\"code\")",
+ "canonical": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").select(\"b\").by(\"code\")",
+ "anonymized": "g.match(string0).select(string1).by(string2)",
+ "dotnet": "g.Match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").Select<object>(\"b\").By(\"code\")",
+ "go": "g.Match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").Select(\"b\").By(\"code\")",
+ "groovy": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").select(\"b\").by(\"code\")",
+ "java": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").select(\"b\").by(\"code\")",
+ "javascript": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").select(\"b\").by(\"code\")",
+ "python": "g.match(\"MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)\").select('b').by('code')"
+ }
+ ]
+ },
+ {
+ "scenario": "g_match_chainXreverseRoute_1_2X_selectXbX_byXcodeX",
+ "traversals": [
+ {
+ "original": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "language": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "canonical": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "anonymized": "g.addV(string0).property(string1, string2).as(string3).addV(string0).property(string1, string4).as(string5).addV(string0).property(string1, string6).as(string7).addV(string0).property(string1, string8).as(string9).addE(string10).from(string3).to(string5).addE(string10).from(string5).to(string7).addE(string10).from(string7).to(string9)",
+ "dotnet": "g.AddV((string) \"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV((string) \"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV((string) \"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV((string) \"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE((string) \"route\").From(\"a\").To(\"b\").AddE((string) \"route\").From(\"b\").To(\"c\").AddE((string) \"route\").From(\"c\").To(\"d\")",
+ "go": "g.AddV(\"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV(\"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV(\"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV(\"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE(\"route\").From(\"a\").To(\"b\").AddE(\"route\").From(\"b\").To(\"c\").AddE(\"route\").From(\"c\").To(\"d\")",
+ "groovy": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "java": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "javascript": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from_(\"a\").to(\"b\").addE(\"route\").from_(\"b\").to(\"c\").addE(\"route\").from_(\"c\").to(\"d\")",
+ "python": "g.add_v('airport').property('code', 'AAA').as_('a').add_v('airport').property('code', 'BBB').as_('b').add_v('airport').property('code', 'CCC').as_('c').add_v('airport').property('code', 'DDD').as_('d').add_e('route').from_('a').to('b').add_e('route').from_('b').to('c').add_e('route').from_('c').to('d')"
+ },
+ {
+ "original": "g.match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "language": "g.match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "canonical": "g.match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "anonymized": "g.match(string0).select(string1).by(string2)",
+ "dotnet": "g.Match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").Select<object>(\"b\").By(\"code\")",
+ "go": "g.Match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").Select(\"b\").By(\"code\")",
+ "groovy": "g.match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "java": "g.match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "javascript": "g.match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").select(\"b\").by(\"code\")",
+ "python": "g.match(\"MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)\").select('b').by('code')"
+ }
+ ]
+ },
+ {
+ "scenario": "g_match_chainXundirectedRoute_1X_selectXbX_byXcodeX",
+ "traversals": [
+ {
+ "original": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "language": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "canonical": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "anonymized": "g.addV(string0).property(string1, string2).as(string3).addV(string0).property(string1, string4).as(string5).addV(string0).property(string1, string6).as(string7).addV(string0).property(string1, string8).as(string9).addE(string10).from(string3).to(string5).addE(string10).from(string5).to(string7).addE(string10).from(string7).to(string9)",
+ "dotnet": "g.AddV((string) \"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV((string) \"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV((string) \"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV((string) \"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE((string) \"route\").From(\"a\").To(\"b\").AddE((string) \"route\").From(\"b\").To(\"c\").AddE((string) \"route\").From(\"c\").To(\"d\")",
+ "go": "g.AddV(\"airport\").Property(\"code\", \"AAA\").As(\"a\").AddV(\"airport\").Property(\"code\", \"BBB\").As(\"b\").AddV(\"airport\").Property(\"code\", \"CCC\").As(\"c\").AddV(\"airport\").Property(\"code\", \"DDD\").As(\"d\").AddE(\"route\").From(\"a\").To(\"b\").AddE(\"route\").From(\"b\").To(\"c\").AddE(\"route\").From(\"c\").To(\"d\")",
+ "groovy": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "java": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "javascript": "g.addV(\"airport\").property(\"code\", \"AAA\").as(\"a\").addV(\"airport\").property(\"code\", \"BBB\").as(\"b\").addV(\"airport\").property(\"code\", \"CCC\").as(\"c\").addV(\"airport\").property(\"code\", \"DDD\").as(\"d\").addE(\"route\").from_(\"a\").to(\"b\").addE(\"route\").from_(\"b\").to(\"c\").addE(\"route\").from_(\"c\").to(\"d\")",
+ "python": "g.add_v('airport').property('code', 'AAA').as_('a').add_v('airport').property('code', 'BBB').as_('b').add_v('airport').property('code', 'CCC').as_('c').add_v('airport').property('code', 'DDD').as_('d').add_e('route').from_('a').to('b').add_e('route').from_('b').to('c').add_e('route').from_('c').to('d')"
+ },
+ {
+ "original": "g.match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").select(\"b\").by(\"code\")",
+ "language": "g.match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").select(\"b\").by(\"code\")",
+ "canonical": "g.match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").select(\"b\").by(\"code\")",
+ "anonymized": "g.match(string0).select(string1).by(string2)",
+ "dotnet": "g.Match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").Select<object>(\"b\").By(\"code\")",
+ "go": "g.Match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").Select(\"b\").By(\"code\")",
+ "groovy": "g.match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").select(\"b\").by(\"code\")",
+ "java": "g.match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").select(\"b\").by(\"code\")",
+ "javascript": "g.match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").select(\"b\").by(\"code\")",
+ "python": "g.match(\"MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)\").select('b').by('code')"
+ }
+ ]
+ },
+ {
+ "scenario": "g_match_chainXroute_2X_selectXrX",
+ "traversals": [
+ {
+ "original": "g.addV(\"airport\").property(\"name\", \"AAA\").as(\"a\").addV(\"airport\").property(\"name\", \"BBB\").as(\"b\").addV(\"airport\").property(\"name\", \"CCC\").as(\"c\").addV(\"airport\").property(\"name\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "language": "g.addV(\"airport\").property(\"name\", \"AAA\").as(\"a\").addV(\"airport\").property(\"name\", \"BBB\").as(\"b\").addV(\"airport\").property(\"name\", \"CCC\").as(\"c\").addV(\"airport\").property(\"name\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "canonical": "g.addV(\"airport\").property(\"name\", \"AAA\").as(\"a\").addV(\"airport\").property(\"name\", \"BBB\").as(\"b\").addV(\"airport\").property(\"name\", \"CCC\").as(\"c\").addV(\"airport\").property(\"name\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "anonymized": "g.addV(string0).property(string1, string2).as(string3).addV(string0).property(string1, string4).as(string5).addV(string0).property(string1, string6).as(string7).addV(string0).property(string1, string8).as(string9).addE(string10).from(string3).to(string5).addE(string10).from(string5).to(string7).addE(string10).from(string7).to(string9)",
+ "dotnet": "g.AddV((string) \"airport\").Property(\"name\", \"AAA\").As(\"a\").AddV((string) \"airport\").Property(\"name\", \"BBB\").As(\"b\").AddV((string) \"airport\").Property(\"name\", \"CCC\").As(\"c\").AddV((string) \"airport\").Property(\"name\", \"DDD\").As(\"d\").AddE((string) \"route\").From(\"a\").To(\"b\").AddE((string) \"route\").From(\"b\").To(\"c\").AddE((string) \"route\").From(\"c\").To(\"d\")",
+ "go": "g.AddV(\"airport\").Property(\"name\", \"AAA\").As(\"a\").AddV(\"airport\").Property(\"name\", \"BBB\").As(\"b\").AddV(\"airport\").Property(\"name\", \"CCC\").As(\"c\").AddV(\"airport\").Property(\"name\", \"DDD\").As(\"d\").AddE(\"route\").From(\"a\").To(\"b\").AddE(\"route\").From(\"b\").To(\"c\").AddE(\"route\").From(\"c\").To(\"d\")",
+ "groovy": "g.addV(\"airport\").property(\"name\", \"AAA\").as(\"a\").addV(\"airport\").property(\"name\", \"BBB\").as(\"b\").addV(\"airport\").property(\"name\", \"CCC\").as(\"c\").addV(\"airport\").property(\"name\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "java": "g.addV(\"airport\").property(\"name\", \"AAA\").as(\"a\").addV(\"airport\").property(\"name\", \"BBB\").as(\"b\").addV(\"airport\").property(\"name\", \"CCC\").as(\"c\").addV(\"airport\").property(\"name\", \"DDD\").as(\"d\").addE(\"route\").from(\"a\").to(\"b\").addE(\"route\").from(\"b\").to(\"c\").addE(\"route\").from(\"c\").to(\"d\")",
+ "javascript": "g.addV(\"airport\").property(\"name\", \"AAA\").as(\"a\").addV(\"airport\").property(\"name\", \"BBB\").as(\"b\").addV(\"airport\").property(\"name\", \"CCC\").as(\"c\").addV(\"airport\").property(\"name\", \"DDD\").as(\"d\").addE(\"route\").from_(\"a\").to(\"b\").addE(\"route\").from_(\"b\").to(\"c\").addE(\"route\").from_(\"c\").to(\"d\")",
+ "python": "g.add_v('airport').property('name', 'AAA').as_('a').add_v('airport').property('name', 'BBB').as_('b').add_v('airport').property('name', 'CCC').as_('c').add_v('airport').property('name', 'DDD').as_('d').add_e('route').from_('a').to('b').add_e('route').from_('b').to('c').add_e('route').from_('c').to('d')"
+ },
+ {
+ "original": "g.match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").select(\"r\")",
+ "language": "g.match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").select(\"r\")",
+ "canonical": "g.match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").select(\"r\")",
+ "anonymized": "g.match(string0).select(string1)",
+ "dotnet": "g.Match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").Select<object>(\"r\")",
+ "go": "g.Match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").Select(\"r\")",
+ "groovy": "g.match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").select(\"r\")",
+ "java": "g.match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").select(\"r\")",
+ "javascript": "g.match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").select(\"r\")",
+ "python": "g.match(\"MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)\").select('r')"
+ }
+ ]
+ },
{
"scenario": "g_V_outE_mathX0_minus_itX_byXweightX",
"traversals": [
diff --git a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MatchString.feature b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MatchString.feature
index 0a0d978be5..a88b13b719 100644
--- a/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MatchString.feature
+++ b/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features/map/MatchString.feature
@@ -320,3 +320,147 @@ Feature: Step - match() (String form)
| result |
| marko knows vadas |
| marko knows josh |
+
+ Scenario: g_match_personXknows_1_2X_person_selectXa_bX_byXnameX
+ Given the modern graph
+ And the traversal of
+ """
+ g.match("MATCH (a:person)-[:knows]->{1,2}(b:person)").select("a","b").by("name")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | m[{"a":"marko","b":"vadas"}] |
+ | m[{"a":"marko","b":"josh"}] |
+
+ Scenario: g_match_chainXroute_1_2X_selectXbX_byXcodeX
+ Given the empty graph
+ And the graph initializer of
+ """
+ g.addV("airport").property("code", "AAA").as("a").
+ addV("airport").property("code", "BBB").as("b").
+ addV("airport").property("code", "CCC").as("c").
+ addV("airport").property("code", "DDD").as("d").
+ addE("route").from("a").to("b").
+ addE("route").from("b").to("c").
+ addE("route").from("c").to("d")
+ """
+ And the traversal of
+ """
+ g.match("MATCH (a:airport {code: 'AAA'})-[:route]->{1,2}(b:airport)").select("b").by("code")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | BBB |
+ | CCC |
+
+ Scenario: g_match_chainXroute_2_X_selectXbX_byXcodeX
+ Given the empty graph
+ And the graph initializer of
+ """
+ g.addV("airport").property("code", "AAA").as("a").
+ addV("airport").property("code", "BBB").as("b").
+ addV("airport").property("code", "CCC").as("c").
+ addV("airport").property("code", "DDD").as("d").
+ addE("route").from("a").to("b").
+ addE("route").from("b").to("c").
+ addE("route").from("c").to("d")
+ """
+ And the traversal of
+ """
+ g.match("MATCH (a:airport {code: 'AAA'})-[:route]->{2,}(b:airport)").select("b").by("code")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | CCC |
+ | DDD |
+
+ Scenario: g_match_chainXroute_plusX_selectXbX_byXcodeX
+ Given the empty graph
+ And the graph initializer of
+ """
+ g.addV("airport").property("code", "AAA").as("a").
+ addV("airport").property("code", "BBB").as("b").
+ addV("airport").property("code", "CCC").as("c").
+ addV("airport").property("code", "DDD").as("d").
+ addE("route").from("a").to("b").
+ addE("route").from("b").to("c").
+ addE("route").from("c").to("d")
+ """
+ And the traversal of
+ """
+ g.match("MATCH (a:airport {code: 'AAA'})-[:route]->+(b:airport)").select("b").by("code")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | BBB |
+ | CCC |
+ | DDD |
+
+ Scenario: g_match_chainXreverseRoute_1_2X_selectXbX_byXcodeX
+ Given the empty graph
+ And the graph initializer of
+ """
+ g.addV("airport").property("code", "AAA").as("a").
+ addV("airport").property("code", "BBB").as("b").
+ addV("airport").property("code", "CCC").as("c").
+ addV("airport").property("code", "DDD").as("d").
+ addE("route").from("a").to("b").
+ addE("route").from("b").to("c").
+ addE("route").from("c").to("d")
+ """
+ And the traversal of
+ """
+ g.match("MATCH (a:airport {code: 'CCC'})<-[:route]-{1,2}(b:airport)").select("b").by("code")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | BBB |
+ | AAA |
+
+ Scenario: g_match_chainXundirectedRoute_1X_selectXbX_byXcodeX
+ Given the empty graph
+ And the graph initializer of
+ """
+ g.addV("airport").property("code", "AAA").as("a").
+ addV("airport").property("code", "BBB").as("b").
+ addV("airport").property("code", "CCC").as("c").
+ addV("airport").property("code", "DDD").as("d").
+ addE("route").from("a").to("b").
+ addE("route").from("b").to("c").
+ addE("route").from("c").to("d")
+ """
+ And the traversal of
+ """
+ g.match("MATCH (a:airport {code: 'BBB'})-[:route]-{1}(b:airport)").select("b").by("code")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | AAA |
+ | CCC |
+
+ Scenario: g_match_chainXroute_2X_selectXrX
+ Given the empty graph
+ And the graph initializer of
+ """
+ g.addV("airport").property("name", "AAA").as("a").
+ addV("airport").property("name", "BBB").as("b").
+ addV("airport").property("name", "CCC").as("c").
+ addV("airport").property("name", "DDD").as("d").
+ addE("route").from("a").to("b").
+ addE("route").from("b").to("c").
+ addE("route").from("c").to("d")
+ """
+ And the traversal of
+ """
+ g.match("MATCH (a:airport {name: 'AAA'})-[r:route]->{2}(b:airport)").select("r")
+ """
+ When iterated to list
+ Then the result should be unordered
+ | result |
+ | l[e[AAA-route->BBB],e[BBB-route->CCC]] |
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutorTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutorTest.java
index 3e4443ff1a..ddf14a6e95 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutorTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlExecutorTest.java
@@ -69,20 +69,36 @@ public class DefaultGqlExecutorTest {
// -------------------------------------------------------------------------
/**
- * Drains the lazy result iterator into a list of named-variable maps, mirroring the
+ * A materialised result row. It <em>is</em> a {@code Map<String,Element>} of the row's scalar
+ * bindings (variable name → graph element), so all existing scalar assertions
+ * ({@code row.get("a")}, {@code row.containsKey(...)}) work unchanged. In addition it carries
+ * the quantified group edge bindings (variable name → ordered {@code List<Edge>}) surfaced
+ * from {@link GqlRow#groups} via the plan's variable indices.
+ */
+ private static final class Row extends LinkedHashMap<String, Element> {
+ final Map<String, List<Edge>> groups = new LinkedHashMap<>();
+ }
+
+ /**
+ * Drains the lazy result iterator into a list of {@link Row} maps, mirroring the
* old List<Map> API so that existing assertions can be reused without change.
- * Entries whose variable name starts with {@code $anon} are excluded (anonymous nodes).
+ * Scalar entries whose variable name starts with {@code $anon} are excluded (anonymous
+ * nodes); group edge lists are keyed back to their variable name via the plan index.
*/
- private List<Map<String, Element>> materialize(final Iterator<Element[]> iter,
+ private List<Map<String, Element>> materialize(final Iterator<GqlRow> iter,
final GqlMatchPlan plan) {
final String[] variables = plan.getVariables();
final List<Map<String, Element>> rows = new ArrayList<>();
while (iter.hasNext()) {
- final Element[] row = iter.next();
- final Map<String, Element> map = new LinkedHashMap<>();
+ final GqlRow gqlRow = iter.next();
+ final Element[] scalars = gqlRow.scalars;
+ final Row map = new Row();
for (int i = 0; i < variables.length; i++) {
- if (!variables[i].startsWith("$anon") && row[i] != null)
- map.put(variables[i], row[i]);
+ if (!variables[i].startsWith("$anon") && scalars[i] != null)
+ map.put(variables[i], scalars[i]);
+ }
+ for (final Map.Entry<Integer, List<Edge>> e : gqlRow.groups.entrySet()) {
+ map.groups.put(variables[e.getKey()], e.getValue());
}
rows.add(map);
}
@@ -982,11 +998,11 @@ public class DefaultGqlExecutorTest {
final GqlMatchPlan plan = planner.plan(
"MATCH (a:Person)-[e:KNOWS {weight: 0.5}]->(b:Person)");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan).forEachRemaining(results::add);
assertEquals("Only the edge with weight=0.5 should match", 1, results.size());
- final Element[] row = results.get(0);
+ final Element[] row = results.get(0).scalars;
final int eIdx = plan.getIndex("e");
assertEquals(lowWeight, row[eIdx]);
}
@@ -1001,7 +1017,7 @@ public class DefaultGqlExecutorTest {
final GqlMatchPlan plan = planner.plan(
"MATCH (a:Person)-[e:KNOWS {weight: 0.1}]->(b:Person)");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan).forEachRemaining(results::add);
assertTrue("Filter matching no edge should return no results", results.isEmpty());
@@ -1020,12 +1036,12 @@ public class DefaultGqlExecutorTest {
final GqlMatchPlan plan = planner.plan(
"MATCH (a:Person)-[e:KNOWS {weight: $w}]->(b:Person)");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan, Collections.singletonMap("w", 2.0)).forEachRemaining(results::add);
assertEquals(1, results.size());
final int eIdx = plan.getIndex("e");
- assertEquals(heavy, results.get(0)[eIdx]);
+ assertEquals(heavy, results.get(0).scalars[eIdx]);
}
@Test
@@ -1039,7 +1055,7 @@ public class DefaultGqlExecutorTest {
final GqlMatchPlan plan = planner.plan(
"MATCH (a:Person)-[:KNOWS]->(b:Person)");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan).forEachRemaining(results::add);
assertEquals("Without an edge filter both edges match", 2, results.size());
@@ -1060,12 +1076,12 @@ public class DefaultGqlExecutorTest {
x.addEdge("LOOP", y); // non-loop — must not match MATCH (a)-[r:LOOP]->(a)
final GqlMatchPlan plan = planner.plan("MATCH (a:Node)-[r:LOOP]->(a:Node)");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan).forEachRemaining(results::add);
assertEquals("Only the self-loop satisfies the equality constraint on 'a'", 1, results.size());
final int rIdx = plan.getIndex("r");
- assertEquals(selfLoop, results.get(0)[rIdx]);
+ assertEquals(selfLoop, results.get(0).scalars[rIdx]);
}
@Test
@@ -1080,7 +1096,7 @@ public class DefaultGqlExecutorTest {
b.addEdge("E", c);
final GqlMatchPlan plan = planner.plan("MATCH (a:N)-[r:E]->(b:N), (b)-[r:E]->(c:N)");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan).forEachRemaining(results::add);
assertTrue("No single edge can connect a→b and b→c simultaneously", results.isEmpty());
@@ -1107,16 +1123,16 @@ public class DefaultGqlExecutorTest {
graph.addVertex("Person");
graph.addVertex("Person");
final GqlMatchPlan plan = planner.plan("MATCH (n:Person)");
- final Iterator<Element[]> iter = executor.execute(plan);
+ final Iterator<GqlRow> iter = executor.execute(plan);
- final Element[] first = iter.next();
+ final Element[] first = iter.next().scalars;
final Element first0 = first[0];
// Corrupt the first row's array
first[0] = null;
// Second row must be unaffected
assertTrue(iter.hasNext());
- final Element[] second = iter.next();
+ final Element[] second = iter.next().scalars;
assertNotNull(second[0]);
assertNotSame(first, second);
}
@@ -1133,7 +1149,7 @@ public class DefaultGqlExecutorTest {
v.property(VertexProperty.Cardinality.list, "lang", "groovy");
final GqlMatchPlan plan = planner.plan("MATCH (s:Software {lang: 'groovy'})");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan).forEachRemaining(results::add);
assertEquals("vertex with 'groovy' among its lang values must match", 1, results.size());
@@ -1147,7 +1163,7 @@ public class DefaultGqlExecutorTest {
v.property(VertexProperty.Cardinality.list, "lang", "groovy");
final GqlMatchPlan plan = planner.plan("MATCH (s:Software {lang: 'python'})");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan).forEachRemaining(results::add);
assertTrue("vertex without 'python' in its lang values must not match", results.isEmpty());
@@ -1169,7 +1185,7 @@ public class DefaultGqlExecutorTest {
v.property(VertexProperty.Cardinality.list, "tag", null);
final GqlMatchPlan plan = nullPlanner.plan("MATCH (n:Item {tag: null})");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
nullExecutor.execute(plan).forEachRemaining(results::add);
assertEquals("vertex with null among its tag values must match {tag: null}", 1, results.size());
@@ -1186,9 +1202,335 @@ public class DefaultGqlExecutorTest {
v.property(VertexProperty.Cardinality.list, "lang", "groovy");
final GqlMatchPlan plan = planner.plan("MATCH (s:Software {lang: $lang})");
- final List<Element[]> results = new ArrayList<>();
+ final List<GqlRow> results = new ArrayList<>();
executor.execute(plan, Collections.singletonMap("lang", "groovy")).forEachRemaining(results::add);
assertEquals("param predicate must match against any value in a list-cardinality property", 1, results.size());
}
+
+ // -------------------------------------------------------------------------
+ // Quantified (variable-length) relationship patterns
+ //
+ // Semantics under test:
+ // * per-walk TRAIL edge-uniqueness (an edge is used at most once per walk),
+ // * NO vertex gating (vertices may repeat via distinct edges),
+ // * emit-at-each-depth in [minHops, maxHops],
+ // * the edge variable is a group variable bound as an ordered List<Edge>.
+ // -------------------------------------------------------------------------
+
+ /** Extracts the ordered edge list bound to a quantified group edge variable in a result row. */
+ private List<Edge> edgeList(final Map<String, Element> row, final String var) {
+ assertTrue("group edge variable must be surfaced via the row's group side map",
+ row instanceof Row);
+ final List<Edge> edges = ((Row) row).groups.get(var);
+ assertNotNull("expected a bound group edge variable '" + var + "'", edges);
+ return edges;
+ }
+
+ /** Groups result rows by the target vertex bound to {@code var}. */
+ private Map<Element, List<Map<String, Element>>> byTarget(final List<Map<String, Element>> rows,
+ final String var) {
+ final Map<Element, List<Map<String, Element>>> grouped = new LinkedHashMap<>();
+ for (final Map<String, Element> row : rows)
+ grouped.computeIfAbsent(row.get(var), k -> new ArrayList<>()).add(row);
+ return grouped;
+ }
+
+ @Test
+ public void testQuantifiedEmitsAtEachDepthWithEdgeLists() {
+ // a-KNOWS->b-KNOWS->c-KNOWS->d ; {1,3} from a emits b,c,d with the exact edge list per depth.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ final Vertex d = graph.addVertex("Person");
+ final Edge e1 = a.addEdge("KNOWS", b);
+ final Edge e2 = b.addEdge("KNOWS", c);
+ final Edge e3 = c.addEdge("KNOWS", d);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{1,3}(x:Person)");
+
+ assertEquals(3, results.size());
+ final Map<Element, List<Map<String, Element>>> byX = byTarget(results, "x");
+ assertEquals(java.util.Arrays.asList(e1), edgeList(byX.get(b).get(0), "r"));
+ assertEquals(java.util.Arrays.asList(e1, e2), edgeList(byX.get(c).get(0), "r"));
+ assertEquals(java.util.Arrays.asList(e1, e2, e3), edgeList(byX.get(d).get(0), "r"));
+ }
+
+ @Test
+ public void testQuantifiedLowerBoundGreaterThanOne() {
+ // {2,3} from a emits only c and d (not b).
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ final Vertex d = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+ b.addEdge("KNOWS", c);
+ c.addEdge("KNOWS", d);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{2,3}(x:Person)");
+
+ final Map<Element, List<Map<String, Element>>> byX = byTarget(results, "x");
+ assertEquals(2, results.size());
+ assertFalse(byX.containsKey(b));
+ assertTrue(byX.containsKey(c));
+ assertTrue(byX.containsKey(d));
+ }
+
+ @Test
+ public void testQuantifiedExactBound() {
+ // {2} exactly: only depth-2 target c.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ final Vertex d = graph.addVertex("Person");
+ final Edge e1 = a.addEdge("KNOWS", b);
+ final Edge e2 = b.addEdge("KNOWS", c);
+ c.addEdge("KNOWS", d);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{2}(x:Person)");
+
+ assertEquals(1, results.size());
+ assertEquals(c, results.get(0).get("x"));
+ assertEquals(java.util.Arrays.asList(e1, e2), edgeList(results.get(0), "r"));
+ }
+
+ @Test
+ public void testQuantifiedUnboundedOverChain() {
+ // {2,} over a 3-edge chain emits c and d only.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ final Vertex d = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+ b.addEdge("KNOWS", c);
+ c.addEdge("KNOWS", d);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{2,}(x:Person)");
+
+ final Map<Element, List<Map<String, Element>>> byX = byTarget(results, "x");
+ assertEquals(2, results.size());
+ assertTrue(byX.containsKey(c));
+ assertTrue(byX.containsKey(d));
+ }
+
+ @Test
+ public void testQuantifiedPlusOverChain() {
+ // + (one or more) over a 3-edge chain emits b, c, d.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ final Vertex d = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+ b.addEdge("KNOWS", c);
+ c.addEdge("KNOWS", d);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->+(x:Person)");
+
+ assertEquals(3, results.size());
+ final Map<Element, List<Map<String, Element>>> byX = byTarget(results, "x");
+ assertTrue(byX.containsKey(b));
+ assertTrue(byX.containsKey(c));
+ assertTrue(byX.containsKey(d));
+ }
+
+ @Test
+ public void testQuantifiedUnboundedTerminatesOnCycle() {
+ // Cycle a->b->c->a. TRAIL edge-uniqueness makes an unbounded walk terminate.
+ // From a with + the distinct trails are: a->b (b), a->b->c (c), a->b->c->a (a).
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+ b.addEdge("KNOWS", c);
+ c.addEdge("KNOWS", a);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->+(x:Person)");
+
+ // Exactly three trails from a; the deepest one returns to a (vertex repeats, edges do not).
+ assertEquals(3, results.size());
+ final List<Element> targets = results.stream().map(r -> r.get("x")).collect(Collectors.toList());
+ assertTrue(targets.contains(a));
+ assertTrue(targets.contains(b));
+ assertTrue(targets.contains(c));
+ // The length-3 trail ends back at a and uses all 3 distinct edges.
+ final Map<Element, List<Map<String, Element>>> byX = byTarget(results, "x");
+ assertEquals(3, edgeList(byX.get(a).get(0), "r").size());
+ }
+
+ @Test
+ public void testQuantifiedReverseDirection() {
+ // <-[r:KNOWS]-{1,2} from d walks against KNOWS edges: d<-c<-b (a-b-c-d chain).
+ final Vertex a = graph.addVertex("Person");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ final Vertex d = graph.addVertex("Person");
+ d.property("n", "d");
+ a.addEdge("KNOWS", b);
+ b.addEdge("KNOWS", c);
+ c.addEdge("KNOWS", d);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (d:Person {n: 'd'})<-[r:KNOWS]-{1,2}(x:Person)");
+
+ final Map<Element, List<Map<String, Element>>> byX = byTarget(results, "x");
+ assertEquals(2, results.size());
+ assertTrue(byX.containsKey(c)); // depth 1
+ assertTrue(byX.containsKey(b)); // depth 2
+ assertFalse(byX.containsKey(a));
+ }
+
+ @Test
+ public void testQuantifiedUndirectedSingleEdgeDoesNotOscillate() {
+ // Undirected -[r:KNOWS]-{1,2} over a single edge a-b must NOT oscillate:
+ // the one edge is consumed once, so from a only b is reachable (depth 1), never back to a.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]-{1,2}(x:Person)");
+
+ assertEquals(1, results.size());
+ assertEquals(b, results.get(0).get("x"));
+ assertEquals(1, edgeList(results.get(0), "r").size());
+ }
+
+ @Test
+ public void testQuantifiedUndirectedParallelEdgesUseBothTrails() {
+ // Two parallel KNOWS edges a=>b. Undirected {1,2} from a:
+ // depth1: a-b via e1, a-b via e2 (two rows, target b)
+ // depth2: a-b-a via {e1,e2} and via {e2,e1} (two rows, target a); vertex a repeats
+ // through a distinct second edge, which TRAIL permits.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+ a.addEdge("KNOWS", b);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]-{1,2}(x:Person)");
+
+ final Map<Element, List<Map<String, Element>>> byX = byTarget(results, "x");
+ assertEquals(2, byX.get(b).size()); // two depth-1 trails, one per parallel edge
+ assertEquals(2, byX.get(a).size()); // two depth-2 trails back to a using both edges
+ assertEquals(4, results.size());
+ // Every depth-2 trail uses two distinct edges.
+ for (final Map<String, Element> row : byX.get(a)) {
+ final List<Edge> edges = edgeList(row, "r");
+ assertEquals(2, edges.size());
+ assertNotEquals(edges.get(0), edges.get(1));
+ }
+ }
+
+ @Test
+ public void testQuantifiedSelfLoop() {
+ // Self-loop a-KNOWS->a. {1,2} handles the self-loop as a valid length-1 trail without
+ // infinite looping: the single self-edge is consumed once.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Edge self = a.addEdge("KNOWS", a);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{1,2}(x:Person)");
+
+ assertEquals(1, results.size());
+ assertEquals(a, results.get(0).get("x"));
+ assertEquals(java.util.Arrays.asList(self), edgeList(results.get(0), "r"));
+ }
+
+ @Test
+ public void testExactlyOneHopQuantifierBindsGroupEdgeList() {
+ // A {1,1} quantified edge variable is still a group variable: it surfaces r as a
+ // one-element List<Edge> through the group channel, honoring the length-independent
+ // group-list contract (see GqlMatchStepTest
+ // testExactlyOneHopQuantifierSurfacesSingletonEdgeListInBothChannels).
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Edge e1 = a.addEdge("KNOWS", b);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{1,1}(x:Person)");
+
+ assertEquals(1, results.size());
+ assertEquals(b, results.get(0).get("x"));
+ assertEquals(java.util.List.of(e1), edgeList(results.get(0), "r"));
+ }
+
+ @Test
+ public void testQuantifiedNoMatchWhenTargetLabelUnsatisfied() {
+ // No path reaches a Company via KNOWS, so 0 rows.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{1,3}(x:Company)");
+
+ assertTrue(results.isEmpty());
+ }
+
+ @Test
+ public void testQuantifiedNoMatchWhenMinBoundExceedsAvailablePath() {
+ // Only a 1-edge path exists; {2,3} yields nothing.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{2,3}(x:Person)");
+
+ assertTrue(results.isEmpty());
+ }
+
+ @Test
+ public void testQuantifiedTargetPropertyPredicateFiltersEmits() {
+ // a-KNOWS->b-KNOWS->c ; only c has flag=true, so {1,2} with target filter emits just c.
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ c.property("flag", true);
+ final Edge e1 = a.addEdge("KNOWS", b);
+ final Edge e2 = b.addEdge("KNOWS", c);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{1,2}(x:Person {flag: true})");
+
+ assertEquals(1, results.size());
+ assertEquals(c, results.get(0).get("x"));
+ assertEquals(java.util.Arrays.asList(e1, e2), edgeList(results.get(0), "r"));
+ }
+
+ @Test
+ public void testQuantifiedEdgeLabelConstrainsWalk() {
+ // a-KNOWS->b, b-LIKES->c. {1,2} over KNOWS may only reach b (the LIKES edge is excluded).
+ final Vertex a = graph.addVertex("Person");
+ a.property("n", "a");
+ final Vertex b = graph.addVertex("Person");
+ final Vertex c = graph.addVertex("Person");
+ a.addEdge("KNOWS", b);
+ b.addEdge("LIKES", c);
+
+ final List<Map<String, Element>> results =
+ execute("MATCH (a:Person {n: 'a'})-[r:KNOWS]->{1,2}(x:Person)");
+
+ assertEquals(1, results.size());
+ assertEquals(b, results.get(0).get("x"));
+ }
}
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlannerTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlannerTest.java
index b308782b9a..6f15114db8 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlannerTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/gql/DefaultGqlPlannerTest.java
@@ -448,4 +448,154 @@ public class DefaultGqlPlannerTest {
"MATCH (a:Person)-[:KNOWS]->(b:Person), (b)-[:WORKS_AT]->(c:Company)");
assertNotNull(plan);
}
+
+ // -------------------------------------------------------------------------
+ // Variable-length quantifiers
+ // -------------------------------------------------------------------------
+
+ @Test
+ public void testQuantifiedRangeForwardEdgeCompilesToStep() {
+ // Seed at (c:Company) (fewer), so the step traverses IN from Company back to Person.
+ graph.addVertex("Person");
+ graph.addVertex("Person");
+ graph.addVertex("Company");
+
+ final GqlMatchPlan plan = planner.compile(
+ QueryGraph.parse("MATCH (a:Person)-[r:KNOWS]->{1,3}(c:Company)"));
+
+ assertEquals(1, plan.getSteps().size());
+ final ExtensionStep step = plan.getSteps().get(0);
+ assertEquals("KNOWS", step.getEdgeLabel());
+ assertEquals("c", step.getAnchorVariable());
+ assertEquals("a", step.getTargetVariable());
+ // Company is the source-side target of an OUT edge, so traversing from Company is IN.
+ assertEquals(Direction.IN, step.getDirection());
+ assertEquals(1, step.getMinHops());
+ assertEquals(3, step.getMaxHops());
+ assertTrue(step.isQuantified());
+ assertTrue("named quantified edge is a group variable", step.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testQuantifiedExactForwardEdge() {
+ // {2} => min==max==2. Equal cardinality, first node (a) is seed => OUT forward step.
+ graph.addVertex("Person");
+ graph.addVertex("Person");
+
+ final GqlMatchPlan plan = planner.compile(
+ QueryGraph.parse("MATCH (a:Person)-[:KNOWS]->{2}(b:Person)"));
+
+ assertEquals(1, plan.getSteps().size());
+ final ExtensionStep step = plan.getSteps().get(0);
+ assertEquals("a", step.getAnchorVariable());
+ assertEquals("b", step.getTargetVariable());
+ assertEquals(Direction.OUT, step.getDirection());
+ assertEquals(2, step.getMinHops());
+ assertEquals(2, step.getMaxHops());
+ assertTrue(step.isQuantified());
+ // Anonymous edge variable => not a group variable.
+ assertFalse("anonymous quantified edge must not be a group variable", step.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testQuantifiedPlusForwardEdgeIsUnbounded() {
+ // '+' => min==1, max==UNBOUNDED.
+ graph.addVertex("Person");
+ graph.addVertex("Person");
+
+ final GqlMatchPlan plan = planner.compile(
+ QueryGraph.parse("MATCH (a:Person)-[r:KNOWS]->+(b:Person)"));
+
+ final ExtensionStep step = plan.getSteps().get(0);
+ assertEquals(1, step.getMinHops());
+ assertEquals(ExtensionStep.UNBOUNDED, step.getMaxHops());
+ assertTrue(step.isQuantified());
+ assertTrue(step.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testQuantifiedAtLeastForwardEdgeIsUnbounded() {
+ // {2,} => min==2, max==UNBOUNDED.
+ graph.addVertex("Person");
+ graph.addVertex("Person");
+
+ final GqlMatchPlan plan = planner.compile(
+ QueryGraph.parse("MATCH (a:Person)-[:KNOWS]->{2,}(b:Person)"));
+
+ final ExtensionStep step = plan.getSteps().get(0);
+ assertEquals(2, step.getMinHops());
+ assertEquals(ExtensionStep.UNBOUNDED, step.getMaxHops());
+ assertTrue(step.isQuantified());
+ }
+
+ @Test
+ public void testQuantifiedReverseDirectionEdge() {
+ // <-[..]-{1,3} => IN direction on the QueryEdge. Equal cardinality => seed = a.
+ graph.addVertex("Person");
+ graph.addVertex("Person");
+
+ final GqlMatchPlan plan = planner.compile(
+ QueryGraph.parse("MATCH (a:Person)<-[r:KNOWS]-{1,3}(b:Person)"));
+
+ final ExtensionStep step = plan.getSteps().get(0);
+ assertEquals("a", step.getAnchorVariable());
+ assertEquals("b", step.getTargetVariable());
+ // a is the source of an IN edge; traversing forward from a stays IN.
+ assertEquals(Direction.IN, step.getDirection());
+ assertEquals(1, step.getMinHops());
+ assertEquals(3, step.getMaxHops());
+ assertTrue(step.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testQuantifiedUndirectedEdge() {
+ // -[..]-{2} => BOTH direction.
+ graph.addVertex("Person");
+ graph.addVertex("Person");
+
+ final GqlMatchPlan plan = planner.compile(
+ QueryGraph.parse("MATCH (a:Person)-[r:KNOWS]-{2}(b:Person)"));
+
+ final ExtensionStep step = plan.getSteps().get(0);
+ assertEquals(Direction.BOTH, step.getDirection());
+ assertEquals(2, step.getMinHops());
+ assertEquals(2, step.getMaxHops());
+ assertTrue(step.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testNonQuantifiedEdgeDefaultsRegressionGuard() {
+ // A plain edge must compile to a single-hop, non-group step.
+ graph.addVertex("Person");
+ graph.addVertex("Person");
+
+ final GqlMatchPlan plan = planner.compile(
+ QueryGraph.parse("MATCH (a:Person)-[r:KNOWS]->(b:Person)"));
+
+ final ExtensionStep step = plan.getSteps().get(0);
+ assertEquals(1, step.getMinHops());
+ assertEquals(1, step.getMaxHops());
+ assertFalse("plain edge must not be quantified", step.isQuantified());
+ assertFalse("plain edge must not be a group variable", step.isEdgeVariableGroup());
+ }
+
+ @Test
+ public void testQuantifiedBackEdgeClosingCycleThrows() {
+ // Triangle a-b-c. With equal cardinality the seed is a. BFS from a processes both
+ // edges touching a (AB forward -> visits b, CA forward -> visits c). The remaining
+ // edge BC is then discovered with both endpoints already visited, so it is classified
+ // as a BACK edge. Quantifying BC forces the forward-only guard to fire.
+ graph.addVertex("A");
+ graph.addVertex("B");
+ graph.addVertex("C");
+
+ try {
+ planner.compile(QueryGraph.parse(
+ "MATCH (a:A)-[:AB]->(b:B)-[:BC]->{1,3}(c:C)-[:CA]->(a:A)"));
+ fail("expected IllegalArgumentException for quantified back edge closing a cycle");
+ } catch (final IllegalArgumentException ex) {
+ assertTrue("message should explain the forward-only limitation: " + ex.getMessage(),
+ ex.getMessage().contains("quantified edges closing a pattern cycle are not yet supported"));
+ }
+ }
}
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/map/GqlMatchStepTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/map/GqlMatchStepTest.java
index 27343cfa3f..d1108ef9b3 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/map/GqlMatchStepTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/traversal/step/map/GqlMatchStepTest.java
@@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSo
import org.apache.tinkerpop.gremlin.process.traversal.step.map.DeclarativeMatchStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.structure.Edge;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import org.apache.tinkerpop.gremlin.tinkergraph.structure.TinkerFactory;
import org.apache.tinkerpop.gremlin.tinkergraph.structure.TinkerGraph;
@@ -482,6 +483,262 @@ public class GqlMatchStepTest {
assertNotEquals(results.get(0).get("a"), results.get(0).get("b"));
}
+ // -------------------------------------------------------------------------
+ // Quantified (variable-length) relationship patterns
+ //
+ // A quantified group edge variable r must surface as a List<Edge> through BOTH channels
+ // select() can read, and the two channels must agree:
+ // (1) the emitted binding Map (match()'s current object), and
+ // (2) the traverser path label of the same name.
+ // No Pop-based single-edge behaviour: r is the whole ordered edge list. Scalar endpoints
+ // (s, d) remain single vertices.
+ // -------------------------------------------------------------------------
+
+ /**
+ * Builds an inline person chain s -[knows]-> m -[knows]-> ... over {@code n} vertices,
+ * returning the edges in walk order. Element 0 is the first hop out of {@code s}.
+ */
+ /**
+ * Builds an inline person chain head -[knows]-> m1 -[knows]-> ... over {@code hops} edges,
+ * returning the edges in walk order (element 0 is the first hop out of the head). The head
+ * vertex carries {@code name='head'} so a query can anchor the source and isolate the
+ * emit-at-each-depth rows of a single walk (an unanchored {@code (s:person)} source would
+ * additionally start walks from every interior vertex).
+ */
+ private List<Edge> buildKnowsChain(final int hops) {
+ Vertex prev = graph.addVertex("person");
+ prev.property("name", "head");
+ final java.util.List<Edge> edges = new java.util.ArrayList<>();
+ for (int i = 0; i < hops; i++) {
+ final Vertex next = graph.addVertex("person");
+ edges.add(prev.addEdge("knows", next));
+ prev = next;
+ }
+ return edges;
+ }
+
+ private static final String CHAIN_QUERY =
+ "MATCH (s:person {name: 'head'})-[r:knows]->{1,3}(d:person)";
+
+ @SuppressWarnings("unchecked")
+ private static List<Edge> asEdgeList(final Object value) {
+ assertTrue("quantified group edge variable must surface as a List, got: " +
+ (value == null ? "null" : value.getClass().getName()),
+ value instanceof List);
+ return (List<Edge>) value;
+ }
+
+ @Test
+ public void testQuantifiedGroupEdgeVariableSurfacesAsEdgeListInMapChannel() {
+ // head -[knows]-> m1 -[knows]-> m2 -[knows]-> m3 ; {1,3} from head emits at each depth.
+ final List<Edge> chain = buildKnowsChain(3); // e0, e1, e2
+
+ final List<Object> rValues = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .<Object>select("r")
+ .toList();
+
+ // emit-at-each-depth: three rows (depths 1, 2, 3).
+ assertEquals(3, rValues.size());
+
+ final java.util.Set<List<Edge>> edgeLists = rValues.stream()
+ .map(GqlMatchStepTest::asEdgeList)
+ .collect(Collectors.toSet());
+
+ assertTrue("depth-1 edge list [e0]",
+ edgeLists.contains(Collections.singletonList(chain.get(0))));
+ assertTrue("depth-2 edge list [e0, e1]",
+ edgeLists.contains(java.util.Arrays.asList(chain.get(0), chain.get(1))));
+ assertTrue("depth-3 edge list [e0, e1, e2]",
+ edgeLists.contains(java.util.Arrays.asList(chain.get(0), chain.get(1), chain.get(2))));
+ }
+
+ @Test
+ public void testQuantifiedGroupEdgeVariableAgreesAcrossMapAndPathLabelChannels() {
+ // Map channel: select("r") reads the map's "r" value.
+ // Path-label channel: constant("x") replaces the current object, forcing select("r")
+ // to resolve "r" from path history. Both must yield the SAME List<Edge> per match.
+ buildKnowsChain(3);
+
+ final List<Object> viaMap = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .<Object>select("r")
+ .toList();
+
+ final List<Object> viaPathLabel = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .constant("x")
+ .<Object>select("r")
+ .toList();
+
+ assertEquals(3, viaMap.size());
+ assertEquals(3, viaPathLabel.size());
+
+ // The two channels must agree row-for-row (matches are produced in the same order).
+ final List<List<Edge>> mapLists = viaMap.stream()
+ .map(GqlMatchStepTest::asEdgeList).collect(Collectors.toList());
+ final List<List<Edge>> pathLists = viaPathLabel.stream()
+ .map(GqlMatchStepTest::asEdgeList).collect(Collectors.toList());
+
+ assertEquals("map and path-label channels must agree on the edge lists",
+ mapLists, pathLists);
+ }
+
+ @Test
+ public void testQuantifiedScalarEndpointsRemainSingleVertices() {
+ buildKnowsChain(3);
+
+ final List<Object> sValues = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .<Object>select("s")
+ .toList();
+ final List<Object> dValues = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .<Object>select("d")
+ .toList();
+
+ assertEquals(3, sValues.size());
+ assertEquals(3, dValues.size());
+ // Endpoints are single vertices, never lists.
+ sValues.forEach(v -> assertTrue("s must be a single Vertex, not a list", v instanceof Vertex));
+ dValues.forEach(v -> assertTrue("d must be a single Vertex, not a list", v instanceof Vertex));
+ }
+
+ @Test
+ public void testNonQuantifiedEdgeVariableRemainsScalar() {
+ // A fully non-quantified query binds r to a single Edge, not a list.
+ final Vertex a = graph.addVertex("person");
+ final Vertex b = graph.addVertex("person");
+ final Edge e = a.addEdge("knows", b);
+
+ final List<Object> rValues = g.<Integer>inject(1)
+ .match("MATCH (s:person)-[r:knows]->(d:person)")
+ .<Object>select("r")
+ .toList();
+
+ assertEquals(1, rValues.size());
+ assertEquals(e, rValues.get(0));
+ assertFalse("non-quantified edge variable must not be a list", rValues.get(0) instanceof List);
+ }
+
+ @Test
+ public void testQuantifiedMultiSelectReturnsScalarEndpointsAndListEdgeVariable() {
+ final List<Edge> chain = buildKnowsChain(3);
+
+ @SuppressWarnings("unchecked")
+ final List<Map<String, Object>> results =
+ (List<Map<String, Object>>) (List<?>) g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .select("s", "r", "d")
+ .toList();
+
+ assertEquals(3, results.size());
+ for (final Map<String, Object> row : results) {
+ assertTrue("s is a single Vertex", row.get("s") instanceof Vertex);
+ assertTrue("d is a single Vertex", row.get("d") instanceof Vertex);
+ final List<Edge> edges = asEdgeList(row.get("r"));
+ assertFalse("r edge list must not be empty", edges.isEmpty());
+ // The walk starts at s and ends at d; consistency: first edge leaves s, last reaches d.
+ assertEquals("first edge must originate from s", row.get("s"), edges.get(0).outVertex());
+ assertEquals("last edge must arrive at d",
+ row.get("d"), edges.get(edges.size() - 1).inVertex());
+ }
+
+ // Exactly one row reaches the deepest target with the full 3-edge list.
+ final long fullDepthRows = results.stream()
+ .filter(r -> asEdgeList(r.get("r")).size() == chain.size())
+ .count();
+ assertEquals(1, fullDepthRows);
+ }
+
+ // -------------------------------------------------------------------------
+ // Length-1 (depth-1) group list consistency
+ //
+ // A quantified group edge variable r must be a List<Edge> for EVERY matched length,
+ // including a single-hop (depth-1) match, never a bare Edge. This holds whether the
+ // depth-1 row comes from a range quantifier that matched one hop ({1,3} on a one-hop graph)
+ // or from a degenerate exact quantifier ({1,1}). Both result channels (the emitted binding
+ // Map and the traverser path label) must agree and both must yield the one-element List.
+ // -------------------------------------------------------------------------
+
+ private static final String EXACT1_QUERY =
+ "MATCH (s:person {name: 'head'})-[r:knows]->{1,1}(d:person)";
+
+ @Test
+ public void testExactlyOneHopQuantifierSurfacesSingletonEdgeListInBothChannels() {
+ // {1,1}: the executor runs this as a plain single hop, but the edge variable still
+ // carries a quantifier and is therefore a group variable, so it must be a List, not an Edge.
+ final List<Edge> chain = buildKnowsChain(1); // single edge e0
+
+ final List<Object> viaMap = g.<Integer>inject(1)
+ .match(EXACT1_QUERY)
+ .<Object>select("r")
+ .toList();
+ final List<Object> viaPathLabel = g.<Integer>inject(1)
+ .match(EXACT1_QUERY)
+ .constant("x")
+ .<Object>select("r")
+ .toList();
+
+ assertEquals(1, viaMap.size());
+ assertEquals(1, viaPathLabel.size());
+
+ final List<Edge> mapList = asEdgeList(viaMap.get(0));
+ final List<Edge> pathList = asEdgeList(viaPathLabel.get(0));
+
+ assertEquals("map channel: singleton edge list", Collections.singletonList(chain.get(0)), mapList);
+ assertEquals("path channel: singleton edge list", Collections.singletonList(chain.get(0)), pathList);
+ assertEquals("map and path-label channels must agree", mapList, pathList);
+ }
+
+ @Test
+ public void testRangeQuantifierMatchingSingleHopSurfacesSingletonEdgeListInBothChannels() {
+ // {1,3} against a graph offering only one hop => exactly one depth-1 row. The group
+ // variable must be a one-element List<Edge>, consistent with the {1,1} case and with
+ // the depth-1 row of a longer chain.
+ final List<Edge> chain = buildKnowsChain(1);
+
+ final List<Object> viaMap = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .<Object>select("r")
+ .toList();
+ final List<Object> viaPathLabel = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .constant("x")
+ .<Object>select("r")
+ .toList();
+
+ assertEquals(1, viaMap.size());
+ assertEquals(1, viaPathLabel.size());
+
+ final List<Edge> mapList = asEdgeList(viaMap.get(0));
+ final List<Edge> pathList = asEdgeList(viaPathLabel.get(0));
+
+ assertEquals(Collections.singletonList(chain.get(0)), mapList);
+ assertEquals(Collections.singletonList(chain.get(0)), pathList);
+ assertEquals(mapList, pathList);
+ }
+
+ @Test
+ public void testDepth1RowOfLongerChainIsSingletonEdgeListInPathChannel() {
+ // The depth-1 emission of a {1,3} walk over a 3-hop chain must also be a one-element
+ // List in the path channel (regression guard for the length-dependent-type bug).
+ final List<Edge> chain = buildKnowsChain(3);
+
+ final List<Object> viaPathLabel = g.<Integer>inject(1)
+ .match(CHAIN_QUERY)
+ .constant("x")
+ .<Object>select("r")
+ .toList();
+
+ assertEquals(3, viaPathLabel.size());
+ final java.util.Set<List<Edge>> pathLists = viaPathLabel.stream()
+ .map(GqlMatchStepTest::asEdgeList)
+ .collect(Collectors.toSet());
+ assertTrue("depth-1 singleton edge list [e0] in path channel",
+ pathLists.contains(Collections.singletonList(chain.get(0))));
+ }
+
// -------------------------------------------------------------------------
// Path-label pre-binding guard
// -------------------------------------------------------------------------