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/07/09 22:08:13 UTC
(tinkerpop) branch master updated: TINKERPOP-2063 Add `Tree` support to the GLVs (Python, .NET, Go, JavaScript) (#3495)
This is an automated email from the ASF dual-hosted git repository.
Cole-Greer pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
The following commit(s) were added to refs/heads/master by this push:
new cccf932d17 TINKERPOP-2063 Add `Tree` support to the GLVs (Python, .NET, Go, JavaScript) (#3495)
cccf932d17 is described below
commit cccf932d179d7aafcb51e1d503ae91a1fe2b8e5a
Author: Guian Gumpac <gu...@gmail.com>
AuthorDate: Thu Jul 9 15:08:08 2026 -0700
TINKERPOP-2063 Add `Tree` support to the GLVs (Python, .NET, Go, JavaScript) (#3495)
https://issues.apache.org/jira/browse/TINKERPOP-2063
This commit brings a matching native `Tree` type to all Gremlin Language Variants so that a server-produced
`tree()` result deserializes into a first-class object with the same read/navigation
API instead of an untyped map (or, in JavaScript, a serializer stub that threw).
The work is deserialization + read-navigation focused: trees are computed on the
server and streamed to the client, so each GLV gains (1) a native `Tree` type and
(2) a GraphBinary `0x2b` (de)serializer. A symmetric serialize path is included for
round-trip/test symmetry.
## What changed per variant
- gremlin-python: `Tree` class in `structure/graph.py`; `TreeIO` in `graphbinaryV4.py`
(auto-registered for `0x2b`); removed the `@StepTree` feature-test skip.
- gremlin-dotnet: `Structure/Tree.cs` and `GraphBinary4/Types/TreeSerializer.cs`;
registered `DataType.Tree`; implemented the Gherkin tree-structure assertion; removed
the `@StepTree` skip.
- gremlin-go: `driver/tree.go` plus `treeType` (`0x2b`), `readTree`/`treeWriter`, and
registration; removed the `~@StepTree` cucumber tag.
- gremlin-javascript: `Tree` class in `structure/graph.ts`; `TreeSerializer.js`
replacing the previous stub; exported `Tree`; removed the named tree ignores.
## Testing
- Per-GLV unit tests covering the full read API, structural equality, GraphBinary
round-trips (nested, empty, null-key), duplicate-sibling-key collapse, element-key
equality (by id and concrete type), `childAt` on a missing key, `addTree` null
rejection, `splitParents` edge cases, and `getLeafTrees`.
- Per-GLV integration tests run `g.V(1).out().out().tree()` against the modern graph
and navigate the native result.
- The shared Gherkin `tree()` feature scenarios were un-skipped in each GLV and assert
tree structure through the read API.
## Notes
- Scope is the GLVs; the Java core change shipped in #3448.
- `Tree` results travel server -> client; the serialize path exists for symmetry and
round-trip tests rather than a common workflow.
Assisted-by: Kiro: Claude Opus 4.8
---
CHANGELOG.asciidoc | 1 +
.../Structure/IO/GraphBinary4/DataType.cs | 3 +-
.../IO/GraphBinary4/TypeSerializerRegistry.cs | 2 +
.../IO/GraphBinary4/Types/TreeSerializer.cs | 75 ++
gremlin-dotnet/src/Gremlin.Net/Structure/Tree.cs | 456 +++++++++++++
.../Gherkin/CommonSteps.cs | 93 +++
.../Gherkin/GherkinTestRunner.cs | 6 -
.../Gherkin/IgnoreException.cs | 5 -
.../Traversal/DriverRemoteConnection/TreeTests.cs | 83 +++
.../Structure/IO/GraphBinary4/Model.cs | 14 +-
.../Structure/IO/GraphBinary4/RoundTripTests.cs | 19 +
.../IO/GraphBinary4/TreeSerializerTests.cs | 149 ++++
.../Gremlin.Net.UnitTest/Structure/TreeTests.cs | 334 +++++++++
gremlin-go/driver/cucumber/cucumberSteps_test.go | 120 +++-
gremlin-go/driver/graphBinaryDeserializer.go | 26 +
gremlin-go/driver/graphBinarySerializer.go | 33 +
gremlin-go/driver/serializer.go | 1 +
gremlin-go/driver/tree.go | 361 ++++++++++
gremlin-go/driver/tree_integration_test.go | 103 +++
gremlin-go/driver/tree_test.go | 751 +++++++++++++++++++++
gremlin-js/gremlin-javascript/lib/index.ts | 1 +
.../gremlin-javascript/lib/structure/graph.ts | 302 +++++++++
.../lib/structure/io/binary/GraphBinary.js | 7 +-
.../structure/io/binary/internals/AnySerializer.js | 1 +
.../io/binary/internals/TreeSerializer.js | 146 ++++
.../test/cucumber/feature-steps.js | 89 ++-
.../test/integration/tree-test.js | 64 ++
.../test/unit/graphbinary/model-test.js | 18 +-
.../test/unit/graphbinary/model.js | 10 +-
.../test/unit/graphbinary/tree-serializer-test.js | 296 ++++++++
.../main/python/gremlin_python/structure/graph.py | 229 +++++++
.../gremlin_python/structure/io/graphbinaryV4.py | 40 +-
.../src/main/python/tests/feature/feature_steps.py | 75 +-
.../driver/test_driver_remote_connection.py | 45 ++
.../main/python/tests/unit/structure/io/model.py | 10 +-
.../unit/structure/io/test_graphbinaryv4model.py | 14 +
.../main/python/tests/unit/structure/test_tree.py | 329 +++++++++
37 files changed, 4264 insertions(+), 47 deletions(-)
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index 6ec129d4df..9df6d199c4 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -25,6 +25,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
[[release-4-0-0]]
=== TinkerPop 4.0.0 (Release Date: NOT OFFICIALLY RELEASED YET)
+* Added GraphBinary `Tree` (`0x2b`) serialization and deserialization with a native tree-shaped API to `gremlin-python`, `gremlin-dotnet`, `gremlin-go`, and `gremlin-javascript`.
* Raised the minimum Java version to 17 for building and running *(breaking)*.
* Enabled building and running with Java 21 and Java 25.
* Bumped Groovy to 4.0.32, Hadoop to 3.4.3, Spark to 4.1.2 (Scala 2.13), and Netty to 4.2.7 to support Java 25.
diff --git a/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/DataType.cs b/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/DataType.cs
index bc48d9edf4..3fa501de3a 100644
--- a/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/DataType.cs
+++ b/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/DataType.cs
@@ -55,8 +55,7 @@ namespace Gremlin.Net.Structure.IO.GraphBinary4
public static readonly DataType Binary = new DataType(0x25);
public static readonly DataType Short = new DataType(0x26);
public static readonly DataType Boolean = new DataType(0x27);
- // Not yet implemented
- // public static readonly DataType Tree = new DataType(0x2B);
+ public static readonly DataType Tree = new DataType(0x2B);
public static readonly DataType Merge = new DataType(0x2E);
public static readonly DataType CompositePDT = new DataType(0xF0);
public static readonly DataType PrimitivePDT = new DataType(0xF1);
diff --git a/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/TypeSerializerRegistry.cs b/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/TypeSerializerRegistry.cs
index 459391c411..87937145c2 100644
--- a/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/TypeSerializerRegistry.cs
+++ b/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/TypeSerializerRegistry.cs
@@ -50,6 +50,7 @@ namespace Gremlin.Net.Structure.IO.GraphBinary4
{typeof(Edge), new EdgeSerializer()},
{typeof(Graph), new GraphSerializer()},
{typeof(Path), new PathSerializer()},
+ {typeof(Tree), new TreeSerializer()},
{typeof(Property), new PropertySerializer()},
{typeof(Vertex), new VertexSerializer()},
{typeof(VertexProperty), new VertexPropertySerializer()},
@@ -85,6 +86,7 @@ namespace Gremlin.Net.Structure.IO.GraphBinary4
{DataType.Edge, new EdgeSerializer()},
{DataType.Graph, new GraphSerializer()},
{DataType.Path, new PathSerializer()},
+ {DataType.Tree, new TreeSerializer()},
{DataType.Property, new PropertySerializer()},
{DataType.Vertex, new VertexSerializer()},
{DataType.VertexProperty, new VertexPropertySerializer()},
diff --git a/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/Types/TreeSerializer.cs b/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/Types/TreeSerializer.cs
new file mode 100644
index 0000000000..0a7b98f6d0
--- /dev/null
+++ b/gremlin-dotnet/src/Gremlin.Net/Structure/IO/GraphBinary4/Types/TreeSerializer.cs
@@ -0,0 +1,75 @@
+#region License
+
+/*
+ * 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.
+ */
+
+#endregion
+
+using System.IO;
+using System.Threading;
+using System.Threading.Tasks;
+
+namespace Gremlin.Net.Structure.IO.GraphBinary4.Types
+{
+ /// <summary>
+ /// A <see cref="Tree"/> serializer.
+ /// </summary>
+ public class TreeSerializer : SimpleTypeSerializer<Tree>
+ {
+ /// <summary>
+ /// Initializes a new instance of the <see cref="TreeSerializer" /> class.
+ /// </summary>
+ public TreeSerializer() : base(DataType.Tree)
+ {
+ }
+
+ /// <inheritdoc />
+ protected override async Task WriteValueAsync(Tree value, Stream stream, GraphBinaryWriter writer,
+ CancellationToken cancellationToken = default)
+ {
+ var rootNodes = value.RootNodes();
+ await writer.WriteNonNullableValueAsync(rootNodes.Count, stream, cancellationToken).ConfigureAwait(false);
+
+ foreach (var key in rootNodes)
+ {
+ // key is written fully-qualified (may be null); child is written as a bare value (no
+ // type code or value flag, never null).
+ await writer.WriteAsync(key, stream, cancellationToken).ConfigureAwait(false);
+ await writer.WriteNonNullableValueAsync(value.ChildAt(key), stream, cancellationToken)
+ .ConfigureAwait(false);
+ }
+ }
+
+ /// <inheritdoc />
+ protected override async Task<Tree> ReadValueAsync(Stream stream, GraphBinaryReader reader,
+ CancellationToken cancellationToken = default)
+ {
+ var length = await stream.ReadIntAsync(cancellationToken).ConfigureAwait(false);
+ var result = new Tree();
+ for (var i = 0; i < length; i++)
+ {
+ var key = await reader.ReadAsync(stream, cancellationToken).ConfigureAwait(false);
+ var child = (Tree) await reader.ReadNonNullableValueAsync<Tree>(stream, cancellationToken)
+ .ConfigureAwait(false);
+ result.GetOrCreateChild(key).AddTree(child);
+ }
+ return result;
+ }
+ }
+}
diff --git a/gremlin-dotnet/src/Gremlin.Net/Structure/Tree.cs b/gremlin-dotnet/src/Gremlin.Net/Structure/Tree.cs
new file mode 100644
index 0000000000..98f2b39d58
--- /dev/null
+++ b/gremlin-dotnet/src/Gremlin.Net/Structure/Tree.cs
@@ -0,0 +1,456 @@
+#region License
+
+/*
+ * 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.
+ */
+
+#endregion
+
+using System;
+using System.Collections.Generic;
+using System.Text;
+
+namespace Gremlin.Net.Structure
+{
+ /// <summary>
+ /// A tree data structure with a tree-shaped public API.
+ /// </summary>
+ /// <remarks>
+ /// Iteration order over the nodes at a given level follows insertion order. Because children are keyed by node
+ /// value, sibling branches that resolve to the same value are represented as a single node; callers that require
+ /// every path to be preserved should use <see cref="Path" /> instead.
+ /// <para>
+ /// Children are stored in an ordered list of (key, child) entries rather than a dictionary so that
+ /// <c>null</c> keys are permitted and key comparisons use value-equality via <see cref="object.Equals(object)" />.
+ /// </para>
+ /// </remarks>
+ public class Tree : IEquatable<Tree>
+ {
+ private readonly List<KeyValuePair<object?, Tree>> _entries = new List<KeyValuePair<object?, Tree>>();
+
+ /// <summary>
+ /// Initializes a new empty instance of the <see cref="Tree" /> class.
+ /// </summary>
+ public Tree()
+ {
+ }
+
+ private int IndexOfKey(object? key)
+ {
+ for (var i = 0; i < _entries.Count; i++)
+ {
+ if (Equals(_entries[i].Key, key))
+ {
+ return i;
+ }
+ }
+
+ return -1;
+ }
+
+ // ------------------------------------------------------------------
+ // navigation
+ // ------------------------------------------------------------------
+
+ /// <summary>
+ /// Returns the keys at the root of this tree in insertion order.
+ /// </summary>
+ public IReadOnlyList<object?> RootNodes()
+ {
+ var keys = new List<object?>(_entries.Count);
+ foreach (var entry in _entries)
+ {
+ keys.Add(entry.Key);
+ }
+
+ return keys;
+ }
+
+ /// <summary>
+ /// Returns the child subtree for the given key.
+ /// </summary>
+ /// <param name="key">The key whose child subtree should be returned.</param>
+ /// <returns>The child <see cref="Tree" /> for the given key.</returns>
+ /// <exception cref="KeyNotFoundException">Thrown if no child exists for the given key.</exception>
+ public Tree ChildAt(object? key)
+ {
+ var index = IndexOfKey(key);
+ if (index < 0)
+ {
+ throw new KeyNotFoundException($"Tree has no child for key: {key}");
+ }
+
+ return _entries[index].Value;
+ }
+
+ /// <summary>
+ /// Returns <c>true</c> if the given key is an immediate child of this tree.
+ /// </summary>
+ /// <param name="key">The key to look for.</param>
+ public bool HasChild(object? key)
+ {
+ return IndexOfKey(key) >= 0;
+ }
+
+ /// <summary>
+ /// Returns <c>true</c> if the given value appears as a key anywhere in this tree (recursive).
+ /// </summary>
+ /// <param name="value">The value to search for.</param>
+ public bool Contains(object? value)
+ {
+ foreach (var entry in _entries)
+ {
+ if (Equals(entry.Key, value))
+ {
+ return true;
+ }
+
+ if (entry.Value.Contains(value))
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ /// <summary>
+ /// Recursively searches the tree for the first subtree rooted at <paramref name="key" /> and returns it.
+ /// Direct children are visited before recursing.
+ /// </summary>
+ /// <param name="key">The key to search for.</param>
+ /// <returns>The first matching subtree, or <c>null</c> if no match is found.</returns>
+ public Tree? FindSubtree(object? key)
+ {
+ var index = IndexOfKey(key);
+ if (index >= 0)
+ {
+ return _entries[index].Value;
+ }
+
+ foreach (var entry in _entries)
+ {
+ var found = entry.Value.FindSubtree(key);
+ if (found != null)
+ {
+ return found;
+ }
+ }
+
+ return null;
+ }
+
+ /// <summary>
+ /// Returns the existing child for <paramref name="key" />, or inserts and returns a new empty
+ /// <see cref="Tree" /> if absent.
+ /// </summary>
+ /// <param name="key">The key whose child should be returned or created.</param>
+ public Tree GetOrCreateChild(object? key)
+ {
+ var index = IndexOfKey(key);
+ if (index >= 0)
+ {
+ return _entries[index].Value;
+ }
+
+ var child = new Tree();
+ _entries.Add(new KeyValuePair<object?, Tree>(key, child));
+ return child;
+ }
+
+ // ------------------------------------------------------------------
+ // structural
+ // ------------------------------------------------------------------
+
+ /// <summary>
+ /// Returns <c>true</c> if this tree has no children. An empty tree is considered a leaf.
+ /// </summary>
+ public bool IsLeaf()
+ {
+ return _entries.Count == 0;
+ }
+
+ /// <summary>
+ /// Returns the total number of nodes (keys) in the tree, counted recursively.
+ /// </summary>
+ public int NodeCount()
+ {
+ var count = _entries.Count;
+ foreach (var entry in _entries)
+ {
+ count += entry.Value.NodeCount();
+ }
+
+ return count;
+ }
+
+ /// <summary>
+ /// Returns the keys at the given depth. Depth <c>0</c> returns the root keys. Negative depths or depths
+ /// beyond the tree's height return an empty list.
+ /// </summary>
+ /// <param name="depth">The depth, where <c>0</c> is the root.</param>
+ public IReadOnlyList<object?> GetNodesAtDepth(int depth)
+ {
+ var list = new List<object?>();
+ foreach (var tree in GetTreesAtDepth(depth))
+ {
+ foreach (var entry in tree._entries)
+ {
+ list.Add(entry.Key);
+ }
+ }
+
+ return list;
+ }
+
+ /// <summary>
+ /// Returns the trees at the given depth. Depth <c>0</c> returns a singleton list containing this tree.
+ /// Depths beyond the tree's height (or negative depths) return an empty list.
+ /// </summary>
+ /// <param name="depth">The depth, where <c>0</c> is the root.</param>
+ public IReadOnlyList<Tree> GetTreesAtDepth(int depth)
+ {
+ if (depth < 0)
+ {
+ return new List<Tree>(0);
+ }
+
+ var currentDepth = new List<Tree> { this };
+ for (var i = 0; i < depth; i++)
+ {
+ var next = new List<Tree>();
+ foreach (var tree in currentDepth)
+ {
+ foreach (var entry in tree._entries)
+ {
+ next.Add(entry.Value);
+ }
+ }
+
+ if (next.Count == 0)
+ {
+ return new List<Tree>(0);
+ }
+
+ currentDepth = next;
+ }
+
+ return currentDepth;
+ }
+
+ /// <summary>
+ /// Returns all keys whose subtrees are leaves.
+ /// </summary>
+ public IReadOnlyList<object?> GetLeafNodes()
+ {
+ var leaves = new List<object?>();
+ CollectLeafKeys(leaves);
+ return leaves;
+ }
+
+ private void CollectLeafKeys(List<object?> output)
+ {
+ foreach (var entry in _entries)
+ {
+ if (entry.Value.IsLeaf())
+ {
+ output.Add(entry.Key);
+ }
+ else
+ {
+ entry.Value.CollectLeafKeys(output);
+ }
+ }
+ }
+
+ /// <summary>
+ /// Returns single-key trees representing each leaf key in this tree, preserving the original
+ /// key-to-empty-subtree mapping.
+ /// </summary>
+ public IReadOnlyList<Tree> GetLeafTrees()
+ {
+ var leaves = new List<Tree>();
+ CollectLeafTrees(leaves);
+ return leaves;
+ }
+
+ private void CollectLeafTrees(List<Tree> output)
+ {
+ foreach (var entry in _entries)
+ {
+ if (entry.Value.IsLeaf())
+ {
+ var leaf = new Tree();
+ leaf._entries.Add(new KeyValuePair<object?, Tree>(entry.Key, entry.Value));
+ output.Add(leaf);
+ }
+ else
+ {
+ entry.Value.CollectLeafTrees(output);
+ }
+ }
+ }
+
+ // ------------------------------------------------------------------
+ // composition
+ // ------------------------------------------------------------------
+
+ /// <summary>
+ /// Recursively merges <paramref name="other" /> into this tree. For overlapping keys, child subtrees are
+ /// merged in turn. For keys present only in <paramref name="other" />, the corresponding subtree is adopted
+ /// directly.
+ /// </summary>
+ /// <param name="other">The tree to merge into this one.</param>
+ /// <exception cref="ArgumentNullException">Thrown if <paramref name="other" /> is <c>null</c>.</exception>
+ public void AddTree(Tree other)
+ {
+ if (other == null) throw new ArgumentNullException(nameof(other));
+
+ foreach (var entry in other._entries)
+ {
+ var index = IndexOfKey(entry.Key);
+ if (index >= 0)
+ {
+ _entries[index].Value.AddTree(entry.Value);
+ }
+ else
+ {
+ _entries.Add(new KeyValuePair<object?, Tree>(entry.Key, entry.Value));
+ }
+ }
+ }
+
+ /// <summary>
+ /// Splits this tree into one tree per root key. If the tree has a single root, returns a singleton list
+ /// containing this tree.
+ /// </summary>
+ public IReadOnlyList<Tree> SplitParents()
+ {
+ if (_entries.Count == 1)
+ {
+ return new List<Tree> { this };
+ }
+
+ var parents = new List<Tree>();
+ foreach (var entry in _entries)
+ {
+ var parentTree = new Tree();
+ parentTree._entries.Add(new KeyValuePair<object?, Tree>(entry.Key, entry.Value));
+ parents.Add(parentTree);
+ }
+
+ return parents;
+ }
+
+ // ------------------------------------------------------------------
+ // output
+ // ------------------------------------------------------------------
+
+ /// <summary>
+ /// Produces a formatted string representation of the tree structure using a <c>|--</c> ASCII style.
+ /// Each level is indented by three spaces relative to its parent, and there is no trailing newline.
+ /// </summary>
+ public string PrettyPrint()
+ {
+ const string lineSeparator = "\n";
+ var builder = new StringBuilder();
+ PrettyPrint(builder, "", lineSeparator);
+ var pretty = builder.ToString();
+ return pretty.Length == 0
+ ? pretty
+ : pretty.Substring(0, pretty.Length - lineSeparator.Length);
+ }
+
+ private void PrettyPrint(StringBuilder builder, string prefix, string lineSeparator)
+ {
+ foreach (var entry in _entries)
+ {
+ builder.Append(prefix).Append("|--").Append(entry.Key);
+ builder.Append(lineSeparator);
+ entry.Value.PrettyPrint(builder, prefix + " ", lineSeparator);
+ }
+ }
+
+ // ------------------------------------------------------------------
+ // identity
+ // ------------------------------------------------------------------
+
+ /// <summary>
+ /// Structural recursive equality. Order across siblings is irrelevant; two trees are equal if they have the
+ /// same set of keys and each key's subtree is recursively equal.
+ /// </summary>
+ /// <param name="other">The other tree to compare against.</param>
+ public bool Equals(Tree? other)
+ {
+ if (ReferenceEquals(null, other)) return false;
+ if (ReferenceEquals(this, other)) return true;
+ if (_entries.Count != other._entries.Count) return false;
+
+ foreach (var entry in _entries)
+ {
+ var index = other.IndexOfKey(entry.Key);
+ if (index < 0) return false;
+ if (!entry.Value.Equals(other._entries[index].Value)) return false;
+ }
+
+ return true;
+ }
+
+ /// <inheritdoc />
+ public override bool Equals(object? obj)
+ {
+ if (ReferenceEquals(null, obj)) return false;
+ if (ReferenceEquals(this, obj)) return true;
+ if (obj.GetType() != GetType()) return false;
+ return Equals((Tree) obj);
+ }
+
+ /// <inheritdoc />
+ public override int GetHashCode()
+ {
+ // Order-independent combination of root keys so that equal trees (which ignore sibling order) produce
+ // equal hash codes. Subtrees are intentionally not folded in to keep this cheap while remaining
+ // content-aware via the root keys.
+ unchecked
+ {
+ var hashCode = 0;
+ foreach (var entry in _entries)
+ {
+ hashCode += entry.Key?.GetHashCode() ?? 0;
+ }
+
+ return hashCode;
+ }
+ }
+
+ /// <inheritdoc />
+ public override string ToString()
+ {
+ var builder = new StringBuilder();
+ builder.Append('{');
+ for (var i = 0; i < _entries.Count; i++)
+ {
+ if (i > 0) builder.Append(", ");
+ builder.Append(_entries[i].Key).Append('=').Append(_entries[i].Value);
+ }
+
+ builder.Append('}');
+ return builder.ToString();
+ }
+ }
+}
diff --git a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/CommonSteps.cs b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/CommonSteps.cs
index 1864149b39..ee68a72a1c 100644
--- a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/CommonSteps.cs
+++ b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/CommonSteps.cs
@@ -239,6 +239,11 @@ namespace Gremlin.Net.IntegrationTest.Gherkin
// single-element array so assertions like AssertSubgraphStructure can find it.
_result = new object?[] { graphResult };
return;
+ case Tree treeResult:
+ // Tree should be treated as a single result so AssertTreeStructure can inspect it;
+ // wrap it in a single-element array rather than letting a later case flatten it.
+ _result = new object?[] { treeResult };
+ return;
case IEnumerable enumerableResult:
_result = enumerableResult.Cast<object>().ToArray();
return;
@@ -314,7 +319,95 @@ namespace Gremlin.Net.IntegrationTest.Gherkin
[Then("the result should be a tree with a structure of")]
public void AssertTreeStructure(string expectedTree)
{
+ AssertThatNoErrorWasThrown();
+
+ // The traversal yields a single Tree as the only result.
+ Assert.NotNull(_result);
+ var tree = Assert.IsType<Tree>(_result![0]);
+
+ // an empty doc string represents an empty tree
+ var roots = ParseTree(expectedTree);
+
+ // validate that the tree matches the parsed expected structure
+ Assert.Equal(roots.Count, tree.RootNodes().Count);
+ foreach (var root in roots)
+ {
+ Assert.True(tree.HasChild(root.Value), $"Tree not matching at {root.Value}");
+ ValidateTreeStructure(tree.ChildAt(root.Value), root);
+ }
+ }
+ private static void ValidateTreeStructure(Tree actualTree, TreeNode expectedNode)
+ {
+ Assert.Equal(expectedNode.Children.Count, actualTree.RootNodes().Count);
+ foreach (var child in expectedNode.Children)
+ {
+ Assert.True(actualTree.HasChild(child.Value), $"Tree not matching at {child.Value}");
+ ValidateTreeStructure(actualTree.ChildAt(child.Value), child);
+ }
+ }
+
+ /// <summary>
+ /// Parses the ascii-tree structure as taken from the Gherkin feature file. Mirrors the Java
+ /// <c>StepDefinition.parseTree</c>: a line's depth is the number of leading spaces divided by three,
+ /// and the node value is the line with the leading <c>|--</c> marker stripped and trimmed.
+ /// </summary>
+ private List<TreeNode> ParseTree(string asciiTree)
+ {
+ var roots = new List<TreeNode>();
+ if (string.IsNullOrEmpty(asciiTree)) return roots;
+
+ var lines = Regex.Split(asciiTree, "\r\n|\r|\n");
+ var levelMap = new Dictionary<int, TreeNode>();
+
+ foreach (var line in lines)
+ {
+ if (line.Length == 0) continue;
+
+ var level = CountLeadingTreeLevels(line);
+ var value = line.Replace("|--", "").Trim();
+
+ var node = new TreeNode(ParseValue(value, _graphName!));
+ if (level == 0)
+ {
+ roots.Add(node);
+ }
+ else
+ {
+ levelMap[level - 1].Children.Add(node);
+ }
+
+ levelMap[level] = node;
+ }
+
+ return roots;
+ }
+
+ private static int CountLeadingTreeLevels(string line)
+ {
+ var count = 0;
+ foreach (var c in line)
+ {
+ if (c == ' ') count++;
+ else break;
+ }
+
+ return count / 3; // 3 spaces per level
+ }
+
+ /// <summary>
+ /// An internal tree-structure that holds the expected tree defined in the gherkin feature files.
+ /// </summary>
+ private sealed class TreeNode
+ {
+ public object? Value { get; }
+ public List<TreeNode> Children { get; }
+
+ public TreeNode(object? value)
+ {
+ Value = value;
+ Children = new List<TreeNode>();
+ }
}
[Then("the result should be a subgraph with the following")]
diff --git a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs
index 91ea4bbb8f..2b8839e435 100644
--- a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs
+++ b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/GherkinTestRunner.cs
@@ -117,12 +117,6 @@ namespace Gremlin.Net.IntegrationTest.Gherkin
continue;
}
- if (scenario.Tags.Concat(feature.Tags).Any(t => t.Name == "@StepTree"))
- {
- failedSteps.Add(scenario.Steps.First(), new IgnoreException(IgnoreReason.TreeStepNotSupported));
- continue;
- }
-
if (scenario.Tags.Concat(feature.Tags).Any(t => t.Name == "@StepWrite"))
{
failedSteps.Add(scenario.Steps.First(), new IgnoreException(IgnoreReason.WriteStepTestingNotSupported));
diff --git a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs
index 7001391004..5a78e80bd0 100644
--- a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs
+++ b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Gherkin/IgnoreException.cs
@@ -62,11 +62,6 @@ namespace Gremlin.Net.IntegrationTest.Gherkin
/// </summary>
NullPropertyValuesNotSupportedOnTestGraph,
- /// <summary>
- /// tree() is not supported yet
- /// </summary>
- TreeStepNotSupported,
-
/// <summary>
/// write() is not supported yet for testing
/// </summary>
diff --git a/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Process/Traversal/DriverRemoteConnection/TreeTests.cs b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Process/Traversal/DriverRemoteConnection/TreeTests.cs
new file mode 100644
index 0000000000..598a5e9932
--- /dev/null
+++ b/gremlin-dotnet/test/Gremlin.Net.IntegrationTest/Process/Traversal/DriverRemoteConnection/TreeTests.cs
@@ -0,0 +1,83 @@
+#region License
+
+/*
+ * 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.
+ */
+
+#endregion
+
+using Gremlin.Net.Process.Traversal;
+using Gremlin.Net.Structure;
+using Xunit;
+
+namespace Gremlin.Net.IntegrationTest.Process.Traversal.DriverRemoteConnection
+{
+ [Collection("GremlinServerTests")]
+ public class TreeTests
+ {
+ private readonly RemoteConnectionFactory _connectionFactory = new RemoteConnectionFactory();
+
+ [Fact]
+ public void g_VX1X_Out_Out_Tree_ByName()
+ {
+ var g = AnonymousTraversalSource.Traversal().With(_connectionFactory.CreateRemoteConnection());
+
+ var tree = (Tree) g.V(1).Out().Out().Tree<object>().By("name").Next()!;
+
+ // marko is the single root
+ var rootNodes = tree.RootNodes();
+ Assert.Single(rootNodes);
+ Assert.Contains("marko", rootNodes);
+
+ // marko -> josh -> {lop, ripple} : marko, josh, lop, ripple
+ Assert.Equal(4, tree.NodeCount());
+
+ // depth 0 is the root
+ Assert.Equal(new object?[] { "marko" }, tree.GetNodesAtDepth(0));
+
+ // depth 2 holds the software vertices reachable via two out() steps
+ var depthTwo = tree.GetNodesAtDepth(2);
+ Assert.Contains("lop", depthTwo);
+ Assert.Contains("ripple", depthTwo);
+
+ // leaves are the software vertices
+ var leaves = tree.GetLeafNodes();
+ Assert.Contains("lop", leaves);
+ Assert.Contains("ripple", leaves);
+
+ Assert.False(tree.IsLeaf());
+
+ // marko -> josh -> {lop, ripple}; lop/ripple are siblings with unspecified order
+ const string optionA = "|--marko\n |--josh\n |--lop\n |--ripple";
+ const string optionB = "|--marko\n |--josh\n |--ripple\n |--lop";
+ var pretty = tree.PrettyPrint();
+ Assert.True(pretty == optionA || pretty == optionB, $"Unexpected prettyPrint output:\n{pretty}");
+ }
+
+ [Fact]
+ public void g_VX1X_Out_Out_Tree_Vertices()
+ {
+ var g = AnonymousTraversalSource.Traversal().With(_connectionFactory.CreateRemoteConnection());
+
+ var tree = (Tree) g.V(1).Out().Out().Tree<object>().Next()!;
+
+ Assert.Equal(4, tree.NodeCount());
+ Assert.Single(tree.RootNodes());
+ }
+ }
+}
diff --git a/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/Model.cs b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/Model.cs
index d749d6624e..bc92428e9d 100644
--- a/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/Model.cs
+++ b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/Model.cs
@@ -34,7 +34,6 @@ namespace Gremlin.Net.UnitTest.Structure.IO.GraphBinary4
///
/// The following models aren't supported:
/// tinker-graph Graph type not implemented
- /// traversal-tree Tree type not implemented
/// max-offsetdatetime DateTimeOffset.MaxValue exceeds serialization range
/// min-offsetdatetime DateTimeOffset.MinValue exceeds serialization range
/// forever-duration TimeSpan cannot represent Duration.FOREVER
@@ -63,6 +62,14 @@ namespace Gremlin.Net.UnitTest.Structure.IO.GraphBinary4
new dynamic[] { StartTime1997, EndTime2001 });
private static readonly VertexProperty NameMarko = new(0, "name", "marko", null);
+ // tree for g.V(10).out().tree(): v[10] -> v[11]
+ private static Tree BuildTraversalTree()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild(new Vertex(10, "software")).GetOrCreateChild(new Vertex(11, "software"));
+ return tree;
+ }
+
public static Dictionary<string, object?> Entries { get; } = new()
{
// BigInteger
@@ -153,6 +160,11 @@ namespace Gremlin.Net.UnitTest.Structure.IO.GraphBinary4
new List<ISet<string>> { new HashSet<string>(), new HashSet<string>(), new HashSet<string>() },
new List<object?> { new Vertex(1, "person"), new Vertex(10, "software"), new Vertex(11, "software") }),
["empty-path"] = new Path(new List<ISet<string>>(), new List<object?>()),
+
+ // Tree
+ ["traversal-tree"] = BuildTraversalTree(),
+ ["empty-tree"] = new Tree(),
+
["prop-path"] = new Path(
new List<ISet<string>> { new HashSet<string>(), new HashSet<string>(), new HashSet<string>() },
new List<object?>
diff --git a/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/RoundTripTests.cs b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/RoundTripTests.cs
index c270105fa2..8622316b49 100644
--- a/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/RoundTripTests.cs
+++ b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/RoundTripTests.cs
@@ -308,6 +308,25 @@ namespace Gremlin.Net.UnitTest.Structure.IO.GraphBinary4
[Fact]
public Task TestPropPath() => RunWriteRead("prop-path"); // properties aren't serialized
+ // Tree tests
+ [Fact]
+ public Task TestTraversalTree() => RunWriteRead("traversal-tree"); // vertex properties aren't serialized
+
+ [Fact]
+ public Task TestEmptyTree() => TestEmptyTreeRoundTrip();
+
+ private async Task TestEmptyTreeRoundTrip()
+ {
+ // no .gbin resource exists for an empty tree, so exercise an in-memory round trip
+ var empty = (Gremlin.Net.Structure.Tree)Model.Entries["empty-tree"]!;
+ using var writeStream = new MemoryStream();
+ await Writer.WriteAsync(empty, writeStream);
+ using var readStream = new MemoryStream(writeStream.ToArray());
+ var roundTripped = await Reader.ReadAsync(readStream);
+ Assert.Equal(empty, roundTripped);
+ Assert.True(((Gremlin.Net.Structure.Tree)roundTripped!).IsLeaf());
+ }
+
// Property tests
[Fact]
public Task TestEdgeProperty() => Run("edge-property");
diff --git a/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/TreeSerializerTests.cs b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/TreeSerializerTests.cs
new file mode 100644
index 0000000000..3cd7c07f89
--- /dev/null
+++ b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/IO/GraphBinary4/TreeSerializerTests.cs
@@ -0,0 +1,149 @@
+#region License
+
+/*
+ * 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.
+ */
+
+#endregion
+
+using System.Buffers.Binary;
+using System.IO;
+using System.Text;
+using System.Threading.Tasks;
+using Gremlin.Net.Structure;
+using Gremlin.Net.Structure.IO.GraphBinary4;
+using Xunit;
+
+namespace Gremlin.Net.UnitTest.Structure.IO.GraphBinary4
+{
+ public class TreeSerializerTests
+ {
+ [Fact]
+ public async Task ShouldRoundTripNestedTree()
+ {
+ // marko -> {lop, josh -> {ripple, lop}}
+ var tree = new Tree();
+ var marko = tree.GetOrCreateChild("marko");
+ marko.GetOrCreateChild("lop");
+ var josh = marko.GetOrCreateChild("josh");
+ josh.GetOrCreateChild("ripple");
+ josh.GetOrCreateChild("lop");
+
+ var deserialized = await RoundTrip(tree);
+
+ Assert.Equal(tree, deserialized);
+ Assert.True(deserialized.HasChild("marko"));
+ var rMarko = deserialized.ChildAt("marko");
+ Assert.True(rMarko.HasChild("lop"));
+ Assert.True(rMarko.HasChild("josh"));
+ var rJosh = rMarko.ChildAt("josh");
+ Assert.True(rJosh.HasChild("ripple"));
+ Assert.True(rJosh.HasChild("lop"));
+ Assert.True(rJosh.ChildAt("ripple").IsLeaf());
+ }
+
+ [Fact]
+ public async Task ShouldRoundTripEmptyTree()
+ {
+ var tree = new Tree();
+
+ var deserialized = await RoundTrip(tree);
+
+ Assert.True(deserialized.IsLeaf());
+ Assert.Equal(tree, deserialized);
+ }
+
+ [Fact]
+ public async Task ShouldRoundTripTreeWithNullKey()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild(null).GetOrCreateChild("child");
+
+ var deserialized = await RoundTrip(tree);
+
+ Assert.True(deserialized.HasChild(null));
+ Assert.True(deserialized.ChildAt(null).HasChild("child"));
+ Assert.Equal(tree, deserialized);
+ }
+
+ [Fact]
+ public void PrettyPrintShouldMatchCanonicalStyle()
+ {
+ var tree = new Tree();
+ var marko = tree.GetOrCreateChild("marko");
+ marko.GetOrCreateChild("lop");
+ var josh = marko.GetOrCreateChild("josh");
+ josh.GetOrCreateChild("ripple");
+
+ var expected = "|--marko\n |--lop\n |--josh\n |--ripple";
+ Assert.Equal(expected, tree.PrettyPrint());
+ }
+
+ [Fact]
+ public async Task ShouldMergeDuplicateSiblingKeys()
+ {
+ using var stream = new MemoryStream();
+ // Tree type-code + non-null value flag.
+ stream.WriteByte(DataType.Tree.TypeCode);
+ stream.WriteByte(0x00);
+ // Root tree with the same key written twice; each child is a leaf.
+ WriteInt32(stream, 2);
+ WriteFullyQualifiedString(stream, "dup");
+ WriteInt32(stream, 0); // bare leaf child
+ WriteFullyQualifiedString(stream, "dup");
+ WriteInt32(stream, 0); // bare leaf child
+ stream.Position = 0;
+
+ var reader = new GraphBinaryReader();
+ var result = await reader.ReadAsync(stream);
+
+ var tree = Assert.IsType<Tree>(result);
+ // The duplicate sibling keys collapse into a single merged entry.
+ Assert.Single(tree.RootNodes());
+ Assert.True(tree.HasChild("dup"));
+ }
+
+ private static void WriteFullyQualifiedString(Stream stream, string value)
+ {
+ stream.WriteByte(DataType.String.TypeCode);
+ stream.WriteByte(0x00); // value flag: not null
+ var bytes = Encoding.UTF8.GetBytes(value);
+ WriteInt32(stream, bytes.Length);
+ stream.Write(bytes, 0, bytes.Length);
+ }
+
+ private static void WriteInt32(Stream stream, int value)
+ {
+ var bytes = new byte[4];
+ BinaryPrimitives.WriteInt32BigEndian(bytes, value);
+ stream.Write(bytes, 0, 4);
+ }
+
+ private static async Task<Tree> RoundTrip(Tree tree)
+ {
+ var writer = new GraphBinaryWriter();
+ var reader = new GraphBinaryReader();
+ using var stream = new MemoryStream();
+ await writer.WriteAsync(tree, stream);
+ stream.Position = 0;
+ var result = await reader.ReadAsync(stream);
+ Assert.NotNull(result);
+ return Assert.IsType<Tree>(result);
+ }
+ }
+}
diff --git a/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/TreeTests.cs b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/TreeTests.cs
new file mode 100644
index 0000000000..25f486f198
--- /dev/null
+++ b/gremlin-dotnet/test/Gremlin.Net.UnitTest/Structure/TreeTests.cs
@@ -0,0 +1,334 @@
+#region License
+
+/*
+ * 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.
+ */
+
+#endregion
+
+using System;
+using System.Linq;
+using Gremlin.Net.Structure;
+using Xunit;
+
+namespace Gremlin.Net.UnitTest.Structure
+{
+ public class TreeTests
+ {
+ // Builds: marko -> {lop, josh -> {ripple, lop}}
+ private static Tree BuildSampleTree()
+ {
+ var tree = new Tree();
+ var marko = tree.GetOrCreateChild("marko");
+ marko.GetOrCreateChild("lop");
+ var josh = marko.GetOrCreateChild("josh");
+ josh.GetOrCreateChild("ripple");
+ josh.GetOrCreateChild("lop");
+ return tree;
+ }
+
+ [Fact]
+ public void RootNodesShouldReturnKeysInInsertionOrder()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild("a");
+ tree.GetOrCreateChild("b");
+ tree.GetOrCreateChild("c");
+
+ Assert.Equal(new object?[] { "a", "b", "c" }, tree.RootNodes());
+ }
+
+ [Fact]
+ public void NodeCountShouldCountAllKeysRecursively()
+ {
+ // marko, lop, josh, ripple, lop => 5 keys total
+ Assert.Equal(5, BuildSampleTree().NodeCount());
+ Assert.Equal(0, new Tree().NodeCount());
+ }
+
+ [Fact]
+ public void GetNodesAtDepthShouldReturnKeysForEachLevel()
+ {
+ var tree = BuildSampleTree();
+
+ Assert.Equal(new object?[] { "marko" }, tree.GetNodesAtDepth(0));
+
+ var depth1 = tree.GetNodesAtDepth(1);
+ Assert.Equal(new object?[] { "lop", "josh" }, depth1);
+
+ var depth2 = tree.GetNodesAtDepth(2);
+ Assert.Equal(new object?[] { "ripple", "lop" }, depth2);
+ }
+
+ [Fact]
+ public void GetNodesAtDepthShouldReturnEmptyForNegativeOrOutOfRangeDepth()
+ {
+ var tree = BuildSampleTree();
+
+ Assert.Empty(tree.GetNodesAtDepth(-1));
+ Assert.Empty(tree.GetNodesAtDepth(3));
+ Assert.Empty(tree.GetNodesAtDepth(99));
+ }
+
+ [Fact]
+ public void GetTreesAtDepthShouldReturnSubtreesForEachLevel()
+ {
+ var tree = BuildSampleTree();
+
+ var depth0 = tree.GetTreesAtDepth(0);
+ Assert.Single(depth0);
+ Assert.Same(tree, depth0[0]);
+
+ // depth 1 holds the marko subtree
+ var depth1 = tree.GetTreesAtDepth(1);
+ Assert.Single(depth1);
+ Assert.True(depth1[0].HasChild("lop"));
+ Assert.True(depth1[0].HasChild("josh"));
+
+ // depth 2 holds the lop (leaf) and josh subtrees
+ var depth2 = tree.GetTreesAtDepth(2);
+ Assert.Equal(2, depth2.Count);
+
+ Assert.Empty(tree.GetTreesAtDepth(-1));
+ Assert.Empty(tree.GetTreesAtDepth(5));
+ }
+
+ [Fact]
+ public void GetLeafNodesShouldReturnKeysWithEmptySubtrees()
+ {
+ var tree = BuildSampleTree();
+
+ // leaves: lop (under marko), ripple and lop (under josh)
+ Assert.Equal(new object?[] { "lop", "ripple", "lop" }, tree.GetLeafNodes());
+ }
+
+ [Fact]
+ public void GetLeafTreesShouldReturnSingleKeyTreesForEachLeaf()
+ {
+ var tree = BuildSampleTree();
+
+ var leafTrees = tree.GetLeafTrees();
+ Assert.Equal(3, leafTrees.Count);
+ foreach (var leafTree in leafTrees)
+ {
+ Assert.Single(leafTree.RootNodes());
+ }
+
+ Assert.Equal(new object?[] { "lop", "ripple", "lop" },
+ leafTrees.SelectMany(t => t.RootNodes()).ToArray());
+ }
+
+ [Fact]
+ public void SplitParentsShouldReturnOneTreePerRootKey()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild("a").GetOrCreateChild("a1");
+ tree.GetOrCreateChild("b");
+
+ var parents = tree.SplitParents();
+ Assert.Equal(2, parents.Count);
+ Assert.True(parents[0].HasChild("a"));
+ Assert.True(parents[1].HasChild("b"));
+ Assert.True(parents[0].ChildAt("a").HasChild("a1"));
+ }
+
+ [Fact]
+ public void SplitParentsShouldReturnSelfForSingleRoot()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild("only");
+
+ var parents = tree.SplitParents();
+ Assert.Single(parents);
+ Assert.Same(tree, parents[0]);
+ }
+
+ [Fact]
+ public void AddTreeShouldMergeOverlappingKeysRecursively()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild("marko").GetOrCreateChild("lop");
+
+ var other = new Tree();
+ var otherMarko = other.GetOrCreateChild("marko");
+ otherMarko.GetOrCreateChild("josh");
+ other.GetOrCreateChild("vadas");
+
+ tree.AddTree(other);
+
+ // marko branch merged, vadas branch adopted
+ Assert.Equal(new object?[] { "marko", "vadas" }, tree.RootNodes());
+ var merged = tree.ChildAt("marko");
+ Assert.True(merged.HasChild("lop"));
+ Assert.True(merged.HasChild("josh"));
+ }
+
+ [Fact]
+ public void AddTreeShouldThrowOnNull()
+ {
+ var tree = new Tree();
+ Assert.Throws<ArgumentNullException>(() => tree.AddTree(null!));
+ }
+
+ [Fact]
+ public void ContainsShouldFindValuesRecursively()
+ {
+ var tree = BuildSampleTree();
+
+ Assert.True(tree.Contains("marko"));
+ Assert.True(tree.Contains("ripple"));
+ Assert.True(tree.Contains("lop"));
+ Assert.False(tree.Contains("peter"));
+ }
+
+ [Fact]
+ public void FindSubtreeShouldReturnFirstMatchingSubtree()
+ {
+ var tree = BuildSampleTree();
+
+ var joshSubtree = tree.FindSubtree("josh");
+ Assert.NotNull(joshSubtree);
+ Assert.True(joshSubtree!.HasChild("ripple"));
+ Assert.True(joshSubtree.HasChild("lop"));
+
+ // a leaf key resolves to an empty subtree
+ var rippleSubtree = tree.FindSubtree("ripple");
+ Assert.NotNull(rippleSubtree);
+ Assert.True(rippleSubtree!.IsLeaf());
+
+ Assert.Null(tree.FindSubtree("absent"));
+ }
+
+ [Fact]
+ public void EqualsShouldBeOrderInsensitiveAcrossSiblings()
+ {
+ var t1 = new Tree();
+ t1.GetOrCreateChild("a").GetOrCreateChild("b");
+ t1.GetOrCreateChild("c");
+
+ var t2 = new Tree();
+ // reversed sibling insertion order
+ t2.GetOrCreateChild("c");
+ t2.GetOrCreateChild("a").GetOrCreateChild("b");
+
+ Assert.True(t1.Equals(t2));
+ Assert.True(t2.Equals(t1));
+ Assert.Equal(t1, t2);
+ }
+
+ [Fact]
+ public void EqualsShouldReturnFalseForNull()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild("a");
+
+ Assert.False(tree.Equals(null));
+ Assert.False(tree.Equals((object?) null));
+ }
+
+ [Fact]
+ public void EqualsShouldReturnTrueForSameReference()
+ {
+ var tree = BuildSampleTree();
+
+ Assert.True(tree.Equals(tree));
+ Assert.True(tree.Equals((object) tree));
+ }
+
+ [Fact]
+ public void EqualsShouldReturnFalseForDifferentEntryCount()
+ {
+ var t1 = new Tree();
+ t1.GetOrCreateChild("a");
+ t1.GetOrCreateChild("b");
+
+ var t2 = new Tree();
+ t2.GetOrCreateChild("a");
+
+ Assert.False(t1.Equals(t2));
+ }
+
+ [Fact]
+ public void EqualsShouldReturnFalseForDifferingSubtree()
+ {
+ var t1 = new Tree();
+ t1.GetOrCreateChild("a").GetOrCreateChild("b");
+
+ var t2 = new Tree();
+ t2.GetOrCreateChild("a").GetOrCreateChild("x");
+
+ Assert.False(t1.Equals(t2));
+ }
+
+ [Fact]
+ public void EqualsObjectOverrideShouldReturnFalseForOtherTypes()
+ {
+ var tree = new Tree();
+ tree.GetOrCreateChild("a");
+
+ Assert.False(tree.Equals("not a tree"));
+ Assert.False(tree.Equals(42));
+ }
+
+ [Fact]
+ public void EmptyTreesShouldBeEqual()
+ {
+ Assert.True(new Tree().Equals(new Tree()));
+ Assert.Equal(new Tree(), new Tree());
+ }
+
+ [Fact]
+ public void GetHashCodeShouldBeEqualForEqualTrees()
+ {
+ var t1 = new Tree();
+ t1.GetOrCreateChild("a").GetOrCreateChild("b");
+ t1.GetOrCreateChild("c");
+
+ var t2 = new Tree();
+ // reversed sibling order, structurally equal
+ t2.GetOrCreateChild("c");
+ t2.GetOrCreateChild("a").GetOrCreateChild("b");
+
+ Assert.True(t1.Equals(t2));
+ Assert.Equal(t1.GetHashCode(), t2.GetHashCode());
+ }
+
+ [Fact]
+ public void GetHashCodeShouldBeStableAcrossCalls()
+ {
+ var tree = BuildSampleTree();
+
+ Assert.Equal(tree.GetHashCode(), tree.GetHashCode());
+ }
+
+ [Fact]
+ public void GetHashCodeShouldHandleNullKey()
+ {
+ // GetHashCode folds in entry.Key?.GetHashCode() ?? 0, so a null key
+ // must not throw.
+ var tree = new Tree();
+ tree.GetOrCreateChild(null).GetOrCreateChild("child");
+
+ var hash = tree.GetHashCode();
+
+ var other = new Tree();
+ other.GetOrCreateChild(null).GetOrCreateChild("child");
+ Assert.Equal(hash, other.GetHashCode());
+ }
+ }
+}
diff --git a/gremlin-go/driver/cucumber/cucumberSteps_test.go b/gremlin-go/driver/cucumber/cucumberSteps_test.go
index ee0d420ef0..47203b9b13 100644
--- a/gremlin-go/driver/cucumber/cucumberSteps_test.go
+++ b/gremlin-go/driver/cucumber/cucumberSteps_test.go
@@ -576,6 +576,123 @@ func (tg *tinkerPopGraph) theResultShouldBeEmpty() error {
return nil
}
+// treeNode is one node of the expected tree structure parsed from a Gherkin
+// ascii-tree docstring: a parsed key value and its child nodes in document order.
+type treeNode struct {
+ value interface{}
+ children []*treeNode
+}
+
+// parseTree builds the expected tree from a Gherkin ascii-tree docstring and
+// returns its root nodes. Each line's depth is its leading-space count divided
+// by three; the node value is the line with the leading "|--" removed, trimmed,
+// and passed through parseValue. A node at depth 0 is a root, otherwise it is
+// appended to the most recent node at the depth above it. An empty docstring
+// yields no roots (an empty tree).
+func (tg *tinkerPopGraph) parseTree(asciiTree string) []*treeNode {
+ var roots []*treeNode
+ if len(asciiTree) == 0 {
+ return roots
+ }
+
+ lines := regexp.MustCompile(`\r\n|\r|\n`).Split(asciiTree, -1)
+ levelMap := map[int]*treeNode{}
+
+ for _, line := range lines {
+ if len(line) == 0 {
+ continue
+ }
+
+ leadingSpaces := 0
+ for _, c := range line {
+ if c == ' ' {
+ leadingSpaces++
+ } else {
+ break
+ }
+ }
+ level := leadingSpaces / 3 // 3 spaces per level
+ rawValue := strings.TrimSpace(strings.Replace(line, "|--", "", 1))
+
+ node := &treeNode{value: parseValue(rawValue, tg.graphName)}
+ if level == 0 {
+ roots = append(roots, node)
+ } else {
+ parent := levelMap[level-1]
+ parent.children = append(parent.children, node)
+ }
+ levelMap[level] = node
+ }
+
+ return roots
+}
+
+// validateTreeStructure recursively asserts that actualTree matches the parsed
+// expectedNode: the child count must match and every expected child must be
+// present and recursively match.
+func validateTreeStructure(actualTree *gremlingo.Tree, expectedNode *treeNode) error {
+ if len(actualTree.RootNodes()) != len(expectedNode.children) {
+ return fmt.Errorf("tree child count does not match at %v: expected %d, got %d",
+ expectedNode.value, len(expectedNode.children), len(actualTree.RootNodes()))
+ }
+ for _, child := range expectedNode.children {
+ if !actualTree.HasChild(child.value) {
+ return fmt.Errorf("tree not matching at %v", child.value)
+ }
+ sub, err := actualTree.ChildAt(child.value)
+ if err != nil {
+ return err
+ }
+ if err := validateTreeStructure(sub, child); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
+// Asserts the most recent result is a *gremlingo.Tree matching the ascii-tree
+// docstring, validated recursively.
+func (tg *tinkerPopGraph) theResultShouldBeATreeWithAStructureOf(expectedTree *godog.DocString) error {
+ if len(tg.result) == 0 {
+ return errors.New("no result to assert against")
+ }
+
+ // The traversal yields a single Tree (via "iterated next").
+ res, ok := tg.result[0].(*gremlingo.Result)
+ if !ok {
+ return fmt.Errorf("expected first result to be *gremlingo.Result, got %T", tg.result[0])
+ }
+ tree, ok := res.GetInterface().(*gremlingo.Tree)
+ if !ok {
+ return fmt.Errorf("expected the result to be a *gremlingo.Tree, got %T", res.GetInterface())
+ }
+
+ var content string
+ if expectedTree != nil {
+ content = expectedTree.Content
+ }
+ // an empty docstring represents an empty tree
+ roots := tg.parseTree(content)
+
+ if len(tree.RootNodes()) != len(roots) {
+ return fmt.Errorf("tree root node count does not match expected structure: expected %d, got %d",
+ len(roots), len(tree.RootNodes()))
+ }
+ for _, root := range roots {
+ if !tree.HasChild(root.value) {
+ return fmt.Errorf("tree not matching at %v", root.value)
+ }
+ sub, err := tree.ChildAt(root.value)
+ if err != nil {
+ return err
+ }
+ if err := validateTreeStructure(sub, root); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
// theResultShouldBeASubgraphWithTheFollowing asserts that the most recent
// traversal result is a *gremlingo.Graph data container whose Vertices or
// Edges map (selected by the data-table header) matches the expected rows.
@@ -1100,6 +1217,7 @@ func InitializeScenario(ctx *godog.ScenarioContext) {
ctx.Step(`^the graph should return (\d+) for count of "(.+)"$`, tg.theGraphShouldReturnForCountOf)
ctx.Step(`^the result should be empty$`, tg.theResultShouldBeEmpty)
ctx.Step(`^the result should be a subgraph with the following$`, tg.theResultShouldBeASubgraphWithTheFollowing)
+ ctx.Step(`^the result should be a tree with a structure of$`, tg.theResultShouldBeATreeWithAStructureOf)
ctx.Step(`^the result should be (o\w+)$`, tg.theResultShouldBe)
ctx.Step(`^the result should be (u\w+)$`, tg.theResultShouldBe)
ctx.Step(`^the result should have a count of (\d+)$`, tg.theResultShouldHaveACountOf)
@@ -1135,7 +1253,7 @@ func TestCucumberFeatures(t *testing.T) {
TestSuiteInitializer: InitializeTestSuite,
ScenarioInitializer: InitializeScenario,
Options: &godog.Options{
- Tags: "~@GraphComputerOnly && ~@AllowNullPropertyValues && ~@StepTree && ~@StepWrite && ~@DataChar",
+ Tags: "~@GraphComputerOnly && ~@AllowNullPropertyValues && ~@StepWrite && ~@DataChar",
Format: "pretty",
Paths: []string{getEnvOrDefaultString("CUCUMBER_FEATURE_FOLDER", "../../../gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/test/features")},
TestingT: t, // Testing instance that will run subtests.
diff --git a/gremlin-go/driver/graphBinaryDeserializer.go b/gremlin-go/driver/graphBinaryDeserializer.go
index 863053ab37..2295edce37 100644
--- a/gremlin-go/driver/graphBinaryDeserializer.go
+++ b/gremlin-go/driver/graphBinaryDeserializer.go
@@ -254,6 +254,8 @@ func (d *GraphBinaryDeserializer) readValue(dt dataType, flag byte) (interface{}
return d.readGraph()
case pathType:
return d.readPath()
+ case treeType:
+ return d.readTree()
case propertyType:
return d.readProperty()
case vertexPropertyType:
@@ -644,6 +646,30 @@ func (d *GraphBinaryDeserializer) readPath() (*Path, error) {
return path, nil
}
+func (d *GraphBinaryDeserializer) readTree() (interface{}, error) {
+ return d.readTreeValue()
+}
+
+func (d *GraphBinaryDeserializer) readTreeValue() (*Tree, error) {
+ length, err := d.readInt32()
+ if err != nil {
+ return nil, err
+ }
+ tree := &Tree{}
+ for i := int32(0); i < length; i++ {
+ key, err := d.ReadFullyQualified()
+ if err != nil {
+ return nil, err
+ }
+ child, err := d.readTreeValue()
+ if err != nil {
+ return nil, err
+ }
+ tree.GetOrCreateChild(key).AddTree(child)
+ }
+ return tree, nil
+}
+
func (d *GraphBinaryDeserializer) readProperty() (*Property, error) {
key, err := d.readString()
if err != nil {
diff --git a/gremlin-go/driver/graphBinarySerializer.go b/gremlin-go/driver/graphBinarySerializer.go
index 07b717efa2..591a8e2864 100644
--- a/gremlin-go/driver/graphBinarySerializer.go
+++ b/gremlin-go/driver/graphBinarySerializer.go
@@ -61,6 +61,7 @@ const (
byteBuffer dataType = 0x25
shortType dataType = 0x26
booleanType dataType = 0x27
+ treeType dataType = 0x2b
mergeType dataType = 0x2e
durationType dataType = 0x81
compositePDTType dataType = 0xf0
@@ -364,6 +365,36 @@ func pathWriter(value interface{}, w io.Writer, typeSerializer *graphBinaryTypeS
return typeSerializer.write(p.Objects, w)
}
+// Format: {length}{entry_0}...{entry_n}
+// Per entry: {key}{child}
+// - key: fully-qualified ({type_code}{type_info}{value_flag}{value}); may be null.
+// - child: a bare (value-only) child Tree, i.e. its own {length}{entries...}
+// with no type_code/value_flag, written recursively. A leaf is length 0.
+// Each key is written fully-qualified and each child as a bare value (no
+// type_code/value_flag); this matches readTree/readTreeValue in
+// graphBinaryDeserializer.go.
+func treeWriter(value interface{}, w io.Writer, typeSerializer *graphBinaryTypeSerializer) error {
+ t := value.(*Tree)
+ if err := binary.Write(w, binary.BigEndian, int32(len(t.entries))); err != nil {
+ return err
+ }
+ for _, e := range t.entries {
+ // key fully-qualified (may be null)
+ if err := typeSerializer.write(e.key, w); err != nil {
+ return err
+ }
+ // child written as a bare value (never null; an empty subtree is length 0)
+ child := e.value
+ if child == nil {
+ child = &Tree{}
+ }
+ if err := treeWriter(child, w, typeSerializer); err != nil {
+ return err
+ }
+ }
+ return nil
+}
+
// Format: {vertex_count}{vertices...}{edge_count}{edges...}
// Per vertex: {id}{labels:list<string>}{vp_count}{vps...}
// Per vp: {id}{labels:list<string>}{value}{parent=null}{meta_props:list<property>}
@@ -603,6 +634,8 @@ func (serializer *graphBinaryTypeSerializer) getType(val interface{}) (dataType,
return vertexPropertyType, nil
case *Path:
return pathType, nil
+ case *Tree:
+ return treeType, nil
case Set:
return setType, nil
case time.Time:
diff --git a/gremlin-go/driver/serializer.go b/gremlin-go/driver/serializer.go
index 726adce6ce..73a9b6d705 100644
--- a/gremlin-go/driver/serializer.go
+++ b/gremlin-go/driver/serializer.go
@@ -199,6 +199,7 @@ func initSerializers() {
propertyType: propertyWriter,
vertexPropertyType: vertexPropertyWriter,
pathType: pathWriter,
+ treeType: treeWriter,
graphType: graphWriter,
datetimeType: dateTimeWriter,
durationType: durationWriter,
diff --git a/gremlin-go/driver/tree.go b/gremlin-go/driver/tree.go
new file mode 100644
index 0000000000..235b19e8ab
--- /dev/null
+++ b/gremlin-go/driver/tree.go
@@ -0,0 +1,361 @@
+/*
+Licensed to the Apache Software Foundation (ASF) under one
+or more contributor license agreements. See the NOTICE file
+distributed with this work for additional information
+regarding copyright ownership. The ASF licenses this file
+to you under the Apache License, Version 2.0 (the
+"License"); you may not use this file except in compliance
+with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing,
+software distributed under the License is distributed on an
+"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+KIND, either express or implied. See the License for the
+specific language governing permissions and limitations
+under the License.
+*/
+
+package gremlingo
+
+import (
+ "fmt"
+ "reflect"
+ "strings"
+)
+
+// treeEntry is a single key/subtree pair within a Tree. The value is the child
+// subtree rooted at key.
+type treeEntry struct {
+ key interface{}
+ value *Tree
+}
+
+// Tree is a tree data structure with a tree-shaped public API.
+//
+// Children are kept in an ordered slice of treeEntry, preserving insertion
+// order and allowing arbitrary (including non-comparable) keys. Graph element
+// keys compare by id and concrete type; all others compare by value.
+type Tree struct {
+ entries []treeEntry
+}
+
+// keyEquals compares two tree keys by value. Graph element keys compare by id
+// and concrete type; all other keys, including nil and composite types,
+// compare with reflect.DeepEqual.
+func keyEquals(a, b interface{}) bool {
+ if a == nil || b == nil {
+ return a == nil && b == nil
+ }
+ // Graph elements (Vertex, Edge, VertexProperty) compare by id and concrete
+ // type, rather than by every struct field as reflect.DeepEqual would (which
+ // would treat two elements with the same id but different property snapshots
+ // as unequal).
+ if aId, ok := elementId(a); ok {
+ bId, ok2 := elementId(b)
+ if !ok2 || reflect.TypeOf(a) != reflect.TypeOf(b) {
+ return false
+ }
+ return reflect.DeepEqual(aId, bId)
+ }
+ // Non-element keys (scalars, composite types, nil) compare by value.
+ return reflect.DeepEqual(a, b)
+}
+
+// elementId returns the id of a graph element key and true, or (nil, false) if
+// the key is not a graph element. Both pointer and value forms are handled. A
+// nil element pointer is treated as a non-element (nil, false) to avoid a
+// typed-nil dereference panic.
+func elementId(v interface{}) (interface{}, bool) {
+ switch e := v.(type) {
+ case *Vertex:
+ if e == nil {
+ return nil, false
+ }
+ return e.Id, true
+ case *Edge:
+ if e == nil {
+ return nil, false
+ }
+ return e.Id, true
+ case *VertexProperty:
+ if e == nil {
+ return nil, false
+ }
+ return e.Id, true
+ case Vertex:
+ return e.Id, true
+ case Edge:
+ return e.Id, true
+ case VertexProperty:
+ return e.Id, true
+ }
+ return nil, false
+}
+
+// RootNodes returns the keys at the root of this tree, in insertion order.
+func (t *Tree) RootNodes() []interface{} {
+ keys := make([]interface{}, 0, len(t.entries))
+ for _, e := range t.entries {
+ keys = append(keys, e.key)
+ }
+ return keys
+}
+
+// ChildAt returns the child subtree for the given key. It returns an error if
+// no child exists for the given key.
+func (t *Tree) ChildAt(key interface{}) (*Tree, error) {
+ for _, e := range t.entries {
+ if keyEquals(e.key, key) {
+ return e.value, nil
+ }
+ }
+ return nil, fmt.Errorf("tree has no child for key: %v", key)
+}
+
+// HasChild returns true if the given key is an immediate child of this tree.
+func (t *Tree) HasChild(key interface{}) bool {
+ for _, e := range t.entries {
+ if keyEquals(e.key, key) {
+ return true
+ }
+ }
+ return false
+}
+
+// Equals reports whether two trees are structurally equal, ignoring the order
+// in which sibling children were inserted. Two nil trees are equal; a nil tree
+// is never equal to a non-nil tree. Trees are equal when they have the same
+// number of entries and, for every entry in t, there is a key-matching entry in
+// other (compared with keyEquals) whose subtree is recursively Equals.
+func (t *Tree) Equals(other *Tree) bool {
+ if t == nil || other == nil {
+ return t == nil && other == nil
+ }
+ if len(t.entries) != len(other.entries) {
+ return false
+ }
+ for _, e := range t.entries {
+ matched := false
+ for _, o := range other.entries {
+ if keyEquals(e.key, o.key) {
+ if e.value.Equals(o.value) {
+ matched = true
+ }
+ break
+ }
+ }
+ if !matched {
+ return false
+ }
+ }
+ return true
+}
+
+// Contains returns true if the given value appears as a key anywhere in this
+// tree (recursive).
+func (t *Tree) Contains(value interface{}) bool {
+ for _, e := range t.entries {
+ if keyEquals(e.key, value) {
+ return true
+ }
+ }
+ for _, e := range t.entries {
+ if e.value != nil && e.value.Contains(value) {
+ return true
+ }
+ }
+ return false
+}
+
+// FindSubtree recursively searches the tree for the first subtree rooted at key
+// and returns it, or nil if absent. Direct children are visited before
+// recursing.
+func (t *Tree) FindSubtree(key interface{}) *Tree {
+ for _, e := range t.entries {
+ if keyEquals(e.key, key) {
+ return e.value
+ }
+ }
+ for _, e := range t.entries {
+ if e.value != nil {
+ if found := e.value.FindSubtree(key); found != nil {
+ return found
+ }
+ }
+ }
+ return nil
+}
+
+// GetOrCreateChild returns the existing child for key, or inserts and returns a
+// new empty Tree if absent.
+func (t *Tree) GetOrCreateChild(key interface{}) *Tree {
+ for _, e := range t.entries {
+ if keyEquals(e.key, key) {
+ return e.value
+ }
+ }
+ child := &Tree{}
+ t.entries = append(t.entries, treeEntry{key: key, value: child})
+ return child
+}
+
+// IsLeaf returns true if this tree has no children. An empty tree is considered
+// a leaf.
+func (t *Tree) IsLeaf() bool {
+ return len(t.entries) == 0
+}
+
+// NodeCount returns the total number of nodes (keys) in the tree, counted
+// recursively.
+func (t *Tree) NodeCount() int {
+ count := len(t.entries)
+ for _, e := range t.entries {
+ if e.value != nil {
+ count += e.value.NodeCount()
+ }
+ }
+ return count
+}
+
+// GetNodesAtDepth returns the keys at the given depth. Depth 0 returns the root
+// keys. Negative depths or depths beyond the tree's height return an empty
+// slice.
+func (t *Tree) GetNodesAtDepth(depth int) []interface{} {
+ list := make([]interface{}, 0)
+ for _, tree := range t.GetTreesAtDepth(depth) {
+ list = append(list, tree.RootNodes()...)
+ }
+ return list
+}
+
+// GetTreesAtDepth returns the trees at the given depth. Depth 0 returns a
+// singleton slice containing this tree. Negative depths or depths beyond the
+// tree's height return an empty slice.
+func (t *Tree) GetTreesAtDepth(depth int) []*Tree {
+ if depth < 0 {
+ return []*Tree{}
+ }
+ currentDepth := []*Tree{t}
+ for i := 0; i < depth; i++ {
+ next := make([]*Tree, 0)
+ for _, tree := range currentDepth {
+ for _, e := range tree.entries {
+ next = append(next, e.value)
+ }
+ }
+ if len(next) == 0 {
+ return []*Tree{}
+ }
+ currentDepth = next
+ }
+ return currentDepth
+}
+
+// GetLeafNodes returns all keys whose subtrees are leaves.
+func (t *Tree) GetLeafNodes() []interface{} {
+ leaves := make([]interface{}, 0)
+ t.collectLeafKeys(&leaves)
+ return leaves
+}
+
+func (t *Tree) collectLeafKeys(out *[]interface{}) {
+ for _, e := range t.entries {
+ if e.value == nil || e.value.IsLeaf() {
+ *out = append(*out, e.key)
+ } else {
+ e.value.collectLeafKeys(out)
+ }
+ }
+}
+
+// GetLeafTrees returns single-key trees representing each leaf key in this tree,
+// preserving the original key-to-empty-subtree mapping.
+func (t *Tree) GetLeafTrees() []*Tree {
+ leaves := make([]*Tree, 0)
+ t.collectLeafTrees(&leaves)
+ return leaves
+}
+
+func (t *Tree) collectLeafTrees(out *[]*Tree) {
+ for _, e := range t.entries {
+ if e.value == nil || e.value.IsLeaf() {
+ leaf := &Tree{}
+ leaf.entries = append(leaf.entries, treeEntry{key: e.key, value: e.value})
+ *out = append(*out, leaf)
+ } else {
+ e.value.collectLeafTrees(out)
+ }
+ }
+}
+
+// AddTree recursively merges other into this tree. For overlapping keys, child
+// subtrees are merged in turn. For keys present only in other, the corresponding
+// subtree reference is adopted directly. A nil argument is invalid and causes a
+// nil-pointer panic.
+func (t *Tree) AddTree(other *Tree) {
+ for _, e := range other.entries {
+ if t.HasChild(e.key) {
+ child, _ := t.ChildAt(e.key)
+ child.AddTree(e.value)
+ } else {
+ t.entries = append(t.entries, treeEntry{key: e.key, value: e.value})
+ }
+ }
+}
+
+// SplitParents splits this tree into one tree per root key. If the tree has a
+// single root, returns a singleton slice containing this tree.
+func (t *Tree) SplitParents() []*Tree {
+ if len(t.entries) == 1 {
+ return []*Tree{t}
+ }
+ parents := make([]*Tree, 0, len(t.entries))
+ for _, e := range t.entries {
+ parentTree := &Tree{}
+ parentTree.entries = append(parentTree.entries, treeEntry{key: e.key, value: e.value})
+ parents = append(parents, parentTree)
+ }
+ return parents
+}
+
+// PrettyPrint produces a formatted string representation of the tree structure
+// using a |-- ASCII style, with a 3-space indent per level and no trailing
+// newline.
+func (t *Tree) PrettyPrint() string {
+ var builder strings.Builder
+ t.prettyPrint(&builder, "")
+ pretty := builder.String()
+ if pretty == "" {
+ return pretty
+ }
+ return strings.TrimSuffix(pretty, "\n")
+}
+
+func (t *Tree) prettyPrint(builder *strings.Builder, prefix string) {
+ for _, e := range t.entries {
+ builder.WriteString(prefix)
+ builder.WriteString("|--")
+ builder.WriteString(fmt.Sprintf("%v", e.key))
+ builder.WriteString("\n")
+ if e.value != nil {
+ e.value.prettyPrint(builder, prefix+" ")
+ }
+ }
+}
+
+// String returns the string representation of the tree.
+func (t *Tree) String() string {
+ parts := make([]string, 0, len(t.entries))
+ for _, e := range t.entries {
+ var sub string
+ if e.value != nil {
+ sub = e.value.String()
+ } else {
+ sub = "{}"
+ }
+ parts = append(parts, fmt.Sprintf("%v=%s", e.key, sub))
+ }
+ return "{" + strings.Join(parts, ", ") + "}"
+}
diff --git a/gremlin-go/driver/tree_integration_test.go b/gremlin-go/driver/tree_integration_test.go
new file mode 100644
index 0000000000..147e74878a
--- /dev/null
+++ b/gremlin-go/driver/tree_integration_test.go
@@ -0,0 +1,103 @@
+/*
+Licensed to the Apache Software Foundation (ASF) under one
+or more contributor license agreements. See the NOTICE file
+distributed with this work for additional information
+regarding copyright ownership. The ASF licenses this file
+to you under the Apache License, Version 2.0 (the
+"License"); you may not use this file except in compliance
+with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing,
+software distributed under the License is distributed on an
+"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+KIND, either express or implied. See the License for the
+specific language governing permissions and limitations
+under the License.
+*/
+
+package gremlingo
+
+import (
+ "crypto/tls"
+ "testing"
+
+ "github.com/stretchr/testify/assert"
+)
+
+// TestTreeIntegration runs tree() against the modern graph on a live server and
+// then navigates the returned native *Tree with its read API. This exercises
+// the user-facing tree-shaped API that the shared gherkin feature scenarios
+// cannot express.
+//
+// g.V(1).Out().Out().Tree().By("name") over the modern graph yields the paths
+// marko -> josh -> lop and marko -> josh -> ripple, so the resulting tree is:
+//
+// marko
+// josh
+// lop
+// ripple
+func TestTreeIntegration(t *testing.T) {
+ testNoAuthUrl := getEnvOrDefaultString("GREMLIN_SERVER_URL", noAuthUrl)
+ skipTestsIfNotEnabled(t, integrationTestSuiteName, getEnvOrDefaultBool("RUN_INTEGRATION_TESTS", true))
+
+ g := getModernGraph(t, testNoAuthUrl, &tls.Config{})
+ defer g.remoteConnection.Close()
+
+ results, err := g.V(1).Out().Out().Tree().By("name").ToList()
+ assert.NoError(t, err)
+ assert.Len(t, results, 1)
+
+ // ToList unrolls Traverser bulk wrapping via nextValue, so the result item
+ // is the bare *Tree value (no manual Traverser unwrap required).
+ tree, ok := results[0].GetInterface().(*Tree)
+ assert.True(t, ok, "expected *Tree, got %T", results[0].GetInterface())
+ assert.NotNil(t, tree)
+
+ // Single root: marko.
+ roots := tree.RootNodes()
+ assert.Len(t, roots, 1)
+ assert.Equal(t, "marko", roots[0])
+
+ // The marko subtree has a single child: josh.
+ markoSubtree, err := tree.ChildAt("marko")
+ assert.NoError(t, err)
+ assert.NotNil(t, markoSubtree)
+ markoChildren := markoSubtree.RootNodes()
+ assert.Len(t, markoChildren, 1)
+ assert.Equal(t, "josh", markoChildren[0])
+
+ // ChildAt for a missing key returns an error.
+ _, err = tree.ChildAt("nonexistent")
+ assert.Error(t, err)
+
+ // Total node count: marko + josh + lop + ripple.
+ assert.Equal(t, 4, tree.NodeCount())
+
+ // Depth 0 is the root (marko); depth 2 holds josh's children (lop, ripple).
+ depth0 := tree.GetNodesAtDepth(0)
+ assert.Len(t, depth0, 1)
+ assert.Contains(t, depth0, "marko")
+
+ depth2 := tree.GetNodesAtDepth(2)
+ assert.Len(t, depth2, 2)
+ assert.Contains(t, depth2, "lop")
+ assert.Contains(t, depth2, "ripple")
+
+ // Leaves: lop and ripple (order-insensitive for siblings).
+ leaves := tree.GetLeafNodes()
+ assert.Len(t, leaves, 2)
+ assert.Contains(t, leaves, "lop")
+ assert.Contains(t, leaves, "ripple")
+
+ // A non-empty tree is not a leaf.
+ assert.False(t, tree.IsLeaf())
+
+ // PrettyPrint renders the whole tree in the |-- ASCII style. lop and ripple
+ // are siblings at depth 2 with unspecified order, so accept either ordering.
+ optionA := "|--marko\n |--josh\n |--lop\n |--ripple"
+ optionB := "|--marko\n |--josh\n |--ripple\n |--lop"
+ pretty := tree.PrettyPrint()
+ assert.Contains(t, []string{optionA, optionB}, pretty)
+}
diff --git a/gremlin-go/driver/tree_test.go b/gremlin-go/driver/tree_test.go
new file mode 100644
index 0000000000..41b9766b2b
--- /dev/null
+++ b/gremlin-go/driver/tree_test.go
@@ -0,0 +1,751 @@
+/*
+Licensed to the Apache Software Foundation (ASF) under one
+or more contributor license agreements. See the NOTICE file
+distributed with this work for additional information
+regarding copyright ownership. The ASF licenses this file
+to you under the Apache License, Version 2.0 (the
+"License"); you may not use this file except in compliance
+with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing,
+software distributed under the License is distributed on an
+"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+KIND, either express or implied. See the License for the
+specific language governing permissions and limitations
+under the License.
+*/
+
+package gremlingo
+
+import (
+ "bytes"
+ "encoding/binary"
+ "reflect"
+ "testing"
+
+ "golang.org/x/text/language"
+)
+
+// buildSampleTree constructs:
+//
+// a
+// |--b
+// |--c
+// d
+// |--e
+func buildSampleTree() *Tree {
+ tree := &Tree{}
+ a := tree.GetOrCreateChild("a")
+ b := a.GetOrCreateChild("b")
+ b.GetOrCreateChild("c")
+ d := tree.GetOrCreateChild("d")
+ d.GetOrCreateChild("e")
+ return tree
+}
+
+func TestTreeReadAPI(t *testing.T) {
+ tree := buildSampleTree()
+
+ // RootNodes preserves insertion order.
+ roots := tree.RootNodes()
+ if !reflect.DeepEqual(roots, []interface{}{"a", "d"}) {
+ t.Fatalf("RootNodes = %v, want [a d]", roots)
+ }
+
+ // NodeCount recursive: a,b,c,d,e = 5
+ if c := tree.NodeCount(); c != 5 {
+ t.Fatalf("NodeCount = %d, want 5", c)
+ }
+
+ // ChildAt present and absent.
+ childA, err := tree.ChildAt("a")
+ if err != nil {
+ t.Fatalf("ChildAt(a) returned error: %v", err)
+ }
+ if !childA.HasChild("b") {
+ t.Fatalf("expected a to have child b")
+ }
+ if _, err := tree.ChildAt("zzz"); err == nil {
+ t.Fatalf("ChildAt(zzz) expected error, got nil")
+ }
+
+ // HasChild
+ if !tree.HasChild("a") || tree.HasChild("c") {
+ t.Fatalf("HasChild mismatch")
+ }
+
+ // Contains (recursive)
+ if !tree.Contains("c") || !tree.Contains("e") {
+ t.Fatalf("Contains should find deep keys")
+ }
+ if tree.Contains("missing") {
+ t.Fatalf("Contains should not find missing key")
+ }
+
+ // FindSubtree
+ if sub := tree.FindSubtree("b"); sub == nil || !sub.HasChild("c") {
+ t.Fatalf("FindSubtree(b) failed")
+ }
+ if sub := tree.FindSubtree("missing"); sub != nil {
+ t.Fatalf("FindSubtree(missing) should be nil")
+ }
+
+ // IsLeaf
+ cTree := tree.FindSubtree("c")
+ if cTree == nil || !cTree.IsLeaf() {
+ t.Fatalf("c should be a leaf")
+ }
+
+ // GetNodesAtDepth
+ if d0 := tree.GetNodesAtDepth(0); !reflect.DeepEqual(d0, []interface{}{"a", "d"}) {
+ t.Fatalf("GetNodesAtDepth(0) = %v, want [a d]", d0)
+ }
+ if d1 := tree.GetNodesAtDepth(1); !reflect.DeepEqual(d1, []interface{}{"b", "e"}) {
+ t.Fatalf("GetNodesAtDepth(1) = %v, want [b e]", d1)
+ }
+ if d2 := tree.GetNodesAtDepth(2); !reflect.DeepEqual(d2, []interface{}{"c"}) {
+ t.Fatalf("GetNodesAtDepth(2) = %v, want [c]", d2)
+ }
+ if dn := tree.GetNodesAtDepth(-1); len(dn) != 0 {
+ t.Fatalf("GetNodesAtDepth(-1) should be empty")
+ }
+ if dbeyond := tree.GetNodesAtDepth(5); len(dbeyond) != 0 {
+ t.Fatalf("GetNodesAtDepth(beyond) should be empty")
+ }
+
+ // GetTreesAtDepth(0) -> [self]
+ if ts := tree.GetTreesAtDepth(0); len(ts) != 1 || ts[0] != tree {
+ t.Fatalf("GetTreesAtDepth(0) should return [self]")
+ }
+
+ // GetLeafNodes
+ leaves := tree.GetLeafNodes()
+ if !reflect.DeepEqual(leaves, []interface{}{"c", "e"}) {
+ t.Fatalf("GetLeafNodes = %v, want [c e]", leaves)
+ }
+
+ // GetLeafTrees
+ leafTrees := tree.GetLeafTrees()
+ if len(leafTrees) != 2 {
+ t.Fatalf("GetLeafTrees len = %d, want 2", len(leafTrees))
+ }
+
+ // SplitParents
+ parents := tree.SplitParents()
+ if len(parents) != 2 {
+ t.Fatalf("SplitParents len = %d, want 2", len(parents))
+ }
+}
+
+func TestTreePrettyPrint(t *testing.T) {
+ tree := buildSampleTree()
+ got := tree.PrettyPrint()
+ want := "|--a\n |--b\n |--c\n|--d\n |--e"
+ if got != want {
+ t.Fatalf("PrettyPrint =\n%q\nwant\n%q", got, want)
+ }
+}
+
+func TestTreeAddTreeMerge(t *testing.T) {
+ t1 := &Tree{}
+ t1.GetOrCreateChild("a").GetOrCreateChild("b")
+
+ t2 := &Tree{}
+ t2.GetOrCreateChild("a").GetOrCreateChild("c")
+ t2.GetOrCreateChild("d")
+
+ t1.AddTree(t2)
+
+ a, err := t1.ChildAt("a")
+ if err != nil {
+ t.Fatalf("ChildAt(a) error: %v", err)
+ }
+ if !a.HasChild("b") || !a.HasChild("c") {
+ t.Fatalf("merged a should have both b and c")
+ }
+ if !t1.HasChild("d") {
+ t.Fatalf("merged tree should have adopted d")
+ }
+}
+
+// writeBareTree encodes a Tree as a bare GraphBinary tree value (int32 length +
+// fully-qualified string keys + bare child trees), matching the wire format
+// consumed by readTreeValue. Keys are written as fully-qualified strings.
+func writeBareTree(buf *bytes.Buffer, tree *Tree) {
+ lenBytes := make([]byte, 4)
+ binary.BigEndian.PutUint32(lenBytes, uint32(len(tree.entries)))
+ buf.Write(lenBytes)
+ for _, e := range tree.entries {
+ // fully-qualified string key: type-id, flag, length, bytes
+ buf.WriteByte(byte(stringType))
+ buf.WriteByte(0x00) // not null
+ key := e.key.(string)
+ klen := make([]byte, 4)
+ binary.BigEndian.PutUint32(klen, uint32(len(key)))
+ buf.Write(klen)
+ buf.WriteString(key)
+ // bare child tree
+ writeBareTree(buf, e.value)
+ }
+}
+
+func TestTreeDeserializerRoundTrip(t *testing.T) {
+ original := buildSampleTree()
+
+ var buf bytes.Buffer
+ writeBareTree(&buf, original)
+
+ d := NewGraphBinaryDeserializer(&buf)
+ result, err := d.readTree()
+ if err != nil {
+ t.Fatalf("readTree error: %v", err)
+ }
+ got, ok := result.(*Tree)
+ if !ok {
+ t.Fatalf("readTree returned %T, want *Tree", result)
+ }
+
+ if got.NodeCount() != original.NodeCount() {
+ t.Fatalf("round-trip NodeCount = %d, want %d", got.NodeCount(), original.NodeCount())
+ }
+ if got.PrettyPrint() != original.PrettyPrint() {
+ t.Fatalf("round-trip PrettyPrint mismatch:\ngot:\n%s\nwant:\n%s", got.PrettyPrint(), original.PrettyPrint())
+ }
+ childA, err := got.ChildAt("a")
+ if err != nil || !childA.HasChild("b") {
+ t.Fatalf("round-trip ChildAt(a) failed: %v", err)
+ }
+}
+
+// newTestTreeSerializer builds a graphBinaryTypeSerializer suitable for unit
+// tests, mirroring the construction in graphBinarySerializer_test.go.
+func newTestTreeSerializer() *graphBinaryTypeSerializer {
+ return &graphBinaryTypeSerializer{newLogHandler(&defaultLogger{}, Error, language.English)}
+}
+
+// TestTreeWriterRoundTrip exercises the real write path: it serializes a *Tree
+// fully-qualified via the type serializer (which dispatches through getType ->
+// treeType -> treeWriter) and reads it back with ReadFullyQualified, asserting
+// the round-trip preserves structure. This replaces reliance on the hand-rolled
+// writeBareTree byte helper for verifying the writer.
+func TestTreeWriterRoundTrip(t *testing.T) {
+ original := buildSampleTree()
+
+ serializer := newTestTreeSerializer()
+
+ // getType must resolve *Tree to treeType and a registered writer.
+ dt, err := serializer.getType(original)
+ if err != nil {
+ t.Fatalf("getType(*Tree) error: %v", err)
+ }
+ if dt != treeType {
+ t.Fatalf("getType(*Tree) = %v, want treeType (0x2b)", dt)
+ }
+
+ var buf bytes.Buffer
+ if err := serializer.write(original, &buf); err != nil {
+ t.Fatalf("write(*Tree) error: %v", err)
+ }
+
+ // Read back fully-qualified: the leading type-id (0x2b) and value flag must
+ // dispatch through the treeType case.
+ d := NewGraphBinaryDeserializer(bytes.NewReader(buf.Bytes()))
+ result, err := d.ReadFullyQualified()
+ if err != nil {
+ t.Fatalf("ReadFullyQualified error: %v", err)
+ }
+ got, ok := result.(*Tree)
+ if !ok {
+ t.Fatalf("ReadFullyQualified returned %T, want *Tree", result)
+ }
+
+ if !got.Equals(original) {
+ t.Fatalf("write/read round-trip mismatch:\ngot:\n%s\nwant:\n%s", got.PrettyPrint(), original.PrettyPrint())
+ }
+ if got.NodeCount() != original.NodeCount() {
+ t.Fatalf("round-trip NodeCount = %d, want %d", got.NodeCount(), original.NodeCount())
+ }
+}
+
+// TestTreeWriterEmptyRoundTrip verifies an empty tree survives the real
+// write/read path as a leaf.
+func TestTreeWriterEmptyRoundTrip(t *testing.T) {
+ original := &Tree{}
+ serializer := newTestTreeSerializer()
+
+ var buf bytes.Buffer
+ if err := serializer.write(original, &buf); err != nil {
+ t.Fatalf("write(empty *Tree) error: %v", err)
+ }
+
+ d := NewGraphBinaryDeserializer(bytes.NewReader(buf.Bytes()))
+ result, err := d.ReadFullyQualified()
+ if err != nil {
+ t.Fatalf("ReadFullyQualified error: %v", err)
+ }
+ got, ok := result.(*Tree)
+ if !ok {
+ t.Fatalf("ReadFullyQualified returned %T, want *Tree", result)
+ }
+ if !got.IsLeaf() {
+ t.Fatalf("empty tree write/read round-trip should be a leaf")
+ }
+ if !got.Equals(original) {
+ t.Fatalf("empty tree write/read round-trip should Equals the original")
+ }
+}
+
+// TestTreeWriterNullKeyRoundTrip verifies the writer emits a nil key as a
+// fully-qualified null and that it survives the real write/read path with its
+// subtree intact (keys may be null; children are never null).
+func TestTreeWriterNullKeyRoundTrip(t *testing.T) {
+ original := &Tree{}
+ original.GetOrCreateChild(nil).GetOrCreateChild("child")
+
+ serializer := newTestTreeSerializer()
+
+ var buf bytes.Buffer
+ if err := serializer.write(original, &buf); err != nil {
+ t.Fatalf("write(*Tree with nil key) error: %v", err)
+ }
+
+ d := NewGraphBinaryDeserializer(bytes.NewReader(buf.Bytes()))
+ result, err := d.ReadFullyQualified()
+ if err != nil {
+ t.Fatalf("ReadFullyQualified error: %v", err)
+ }
+ got, ok := result.(*Tree)
+ if !ok {
+ t.Fatalf("ReadFullyQualified returned %T, want *Tree", result)
+ }
+ if !got.HasChild(nil) {
+ t.Fatalf("round-trip tree should retain the nil key")
+ }
+ sub, err := got.ChildAt(nil)
+ if err != nil {
+ t.Fatalf("ChildAt(nil) error: %v", err)
+ }
+ if !sub.HasChild("child") {
+ t.Fatalf("nil key subtree should contain 'child'")
+ }
+ if !got.Equals(original) {
+ t.Fatalf("nil key write/read round-trip should Equals the original")
+ }
+}
+
+// TestTreeWriterMatchesBareHelper verifies the production writer produces the
+// same child-tree byte layout as the hand-rolled writeBareTree helper (the
+// writer additionally prefixes the fully-qualified Tree type-id and value flag).
+// This pins the writer to the documented wire format consumed by readTreeValue.
+func TestTreeWriterMatchesBareHelper(t *testing.T) {
+ original := buildSampleTree()
+ serializer := newTestTreeSerializer()
+
+ var fq bytes.Buffer
+ if err := serializer.write(original, &fq); err != nil {
+ t.Fatalf("write(*Tree) error: %v", err)
+ }
+
+ // Expected: {type-id 0x2b}{value flag 0x00}{bare tree bytes}.
+ var expected bytes.Buffer
+ expected.Write(treeType.getCodeBytes())
+ expected.WriteByte(0x00)
+ writeBareTree(&expected, original)
+
+ if !bytes.Equal(fq.Bytes(), expected.Bytes()) {
+ t.Fatalf("writer bytes mismatch:\ngot: %x\nwant: %x", fq.Bytes(), expected.Bytes())
+ }
+}
+
+// TestTreeElementKeyEquality verifies that graph element keys are deduplicated
+// by id and concrete type, independent of other element fields.
+func TestTreeElementKeyEquality(t *testing.T) {
+ // Same id, differing label/properties -> one node.
+ tree := &Tree{}
+ tree.GetOrCreateChild(&Vertex{Element: Element{Id: 1, Label: "a"}})
+ tree.GetOrCreateChild(&Vertex{Element: Element{Id: 1, Label: "b", Properties: "different"}})
+ if got := len(tree.RootNodes()); got != 1 {
+ t.Fatalf("same-id keys: RootNodes len = %d, want 1", got)
+ }
+ if got := tree.NodeCount(); got != 1 {
+ t.Fatalf("same-id keys: NodeCount = %d, want 1", got)
+ }
+ if !tree.HasChild(&Vertex{Element: Element{Id: 1}}) {
+ t.Fatalf("same-id keys: HasChild(Vertex Id:1) should be true")
+ }
+
+ // Differing ids -> two nodes.
+ tree2 := &Tree{}
+ tree2.GetOrCreateChild(&Vertex{Element: Element{Id: 1, Label: "a"}})
+ tree2.GetOrCreateChild(&Vertex{Element: Element{Id: 2, Label: "a"}})
+ if got := len(tree2.RootNodes()); got != 2 {
+ t.Fatalf("differing-id keys: RootNodes len = %d, want 2", got)
+ }
+
+ // Type mismatch (same id) -> two nodes; keys are not equal.
+ tree3 := &Tree{}
+ tree3.GetOrCreateChild(&Vertex{Element: Element{Id: 1}})
+ tree3.GetOrCreateChild(&Edge{Element: Element{Id: 1}})
+ if got := len(tree3.RootNodes()); got != 2 {
+ t.Fatalf("type-mismatch keys: RootNodes len = %d, want 2", got)
+ }
+ if tree3.HasChild(&Edge{Element: Element{Id: 1}}) != true {
+ t.Fatalf("type-mismatch keys: Edge Id:1 should be present")
+ }
+ if !keyEquals(&Vertex{Element: Element{Id: 1}}, &Vertex{Element: Element{Id: 1}}) {
+ t.Fatalf("keyEquals(Vertex Id:1, Vertex Id:1) should be true")
+ }
+ if keyEquals(&Vertex{Element: Element{Id: 1}}, &Edge{Element: Element{Id: 1}}) {
+ t.Fatalf("keyEquals(Vertex Id:1, Edge Id:1) should be false (type mismatch)")
+ }
+}
+
+// TestTreeElementKeyNilPointer verifies that a typed-nil element pointer key
+// does not panic and is treated as a non-element value key.
+func TestTreeElementKeyNilPointer(t *testing.T) {
+ var nilV *Vertex
+ if _, ok := elementId(nilV); ok {
+ t.Fatalf("elementId(nil *Vertex) should return ok=false")
+ }
+ // Must not panic.
+ if keyEquals(nilV, nilV) != true {
+ t.Fatalf("keyEquals(nil *Vertex, nil *Vertex) should be true")
+ }
+ if keyEquals(nilV, &Vertex{Element: Element{Id: 1}}) {
+ t.Fatalf("keyEquals(nil *Vertex, Vertex Id:1) should be false")
+ }
+}
+
+// TestTreeEquals verifies order-insensitive structural equality.
+func TestTreeEquals(t *testing.T) {
+ // nil handling.
+ var n1, n2 *Tree
+ if !n1.Equals(n2) {
+ t.Fatalf("nil.Equals(nil) should be true")
+ }
+ if (&Tree{}).Equals(nil) {
+ t.Fatalf("empty.Equals(nil) should be false")
+ }
+ if n1.Equals(&Tree{}) {
+ t.Fatalf("nil.Equals(empty) should be false")
+ }
+
+ // Equal trees regardless of sibling insertion order.
+ t1 := &Tree{}
+ t1.GetOrCreateChild("a").GetOrCreateChild("b")
+ t1.GetOrCreateChild("c")
+
+ t2 := &Tree{}
+ t2.GetOrCreateChild("c")
+ t2.GetOrCreateChild("a").GetOrCreateChild("b")
+
+ if !t1.Equals(t2) {
+ t.Fatalf("trees with same structure (different sibling order) should be Equals")
+ }
+ if !t2.Equals(t1) {
+ t.Fatalf("Equals should be symmetric")
+ }
+
+ // Structurally different trees are not equal.
+ t3 := &Tree{}
+ t3.GetOrCreateChild("a").GetOrCreateChild("x")
+ t3.GetOrCreateChild("c")
+ if t1.Equals(t3) {
+ t.Fatalf("trees differing in a subtree key should not be Equals")
+ }
+
+ // Different number of entries.
+ t4 := &Tree{}
+ t4.GetOrCreateChild("a").GetOrCreateChild("b")
+ if t1.Equals(t4) {
+ t.Fatalf("trees with differing entry counts should not be Equals")
+ }
+
+ // Empty trees are equal.
+ if !(&Tree{}).Equals(&Tree{}) {
+ t.Fatalf("two empty trees should be Equals")
+ }
+}
+
+// TestTreeDeserializerEmptyTree verifies an empty tree round-trips through the
+// bare GraphBinary tree wire format.
+func TestTreeDeserializerEmptyTree(t *testing.T) {
+ original := &Tree{}
+
+ var buf bytes.Buffer
+ writeBareTree(&buf, original)
+
+ d := NewGraphBinaryDeserializer(&buf)
+ result, err := d.readTree()
+ if err != nil {
+ t.Fatalf("readTree error: %v", err)
+ }
+ got, ok := result.(*Tree)
+ if !ok {
+ t.Fatalf("readTree returned %T, want *Tree", result)
+ }
+ if !got.IsLeaf() {
+ t.Fatalf("empty tree round-trip should be a leaf")
+ }
+ if got.NodeCount() != 0 {
+ t.Fatalf("empty tree round-trip NodeCount = %d, want 0", got.NodeCount())
+ }
+ if !got.Equals(original) {
+ t.Fatalf("empty tree round-trip should Equals the original")
+ }
+}
+
+// ---- Deserialization tests (dedup, null-key round-trip) ----
+
+// putInt32 appends a big-endian int32 to buf, matching the bare GraphBinary
+// length encoding.
+func putInt32(buf *bytes.Buffer, n int32) {
+ b := make([]byte, 4)
+ binary.BigEndian.PutUint32(b, uint32(n))
+ buf.Write(b)
+}
+
+// writeFQString writes a fully-qualified GraphBinary string: {type-id}{null
+// flag}{int32 length}{bytes}.
+func writeFQString(buf *bytes.Buffer, s string) {
+ buf.WriteByte(byte(stringType))
+ buf.WriteByte(0x00) // not null
+ putInt32(buf, int32(len(s)))
+ buf.WriteString(s)
+}
+
+// writeFQNull writes a fully-qualified GraphBinary null: {type-id=nullType}
+// {null flag=0x01}. Unlike the string-cast helpers it does not coerce the key
+// to a string, so it round-trips an actual nil key.
+func writeFQNull(buf *bytes.Buffer) {
+ buf.WriteByte(byte(nullType))
+ buf.WriteByte(0x01)
+}
+
+// TestTreeDeserializerDuplicateSiblingKey verifies that a bare stream whose root
+// key appears twice with distinct children collapses into a single merged root
+// entry containing both children, matching the JS/Python/.NET GLVs.
+func TestTreeDeserializerDuplicateSiblingKey(t *testing.T) {
+ var buf bytes.Buffer
+ // length=2
+ putInt32(&buf, 2)
+ // entry 1: key="dup", child={ "a" -> {} }
+ writeFQString(&buf, "dup")
+ putInt32(&buf, 1)
+ writeFQString(&buf, "a")
+ putInt32(&buf, 0)
+ // entry 2: key="dup", child={ "b" -> {} }
+ writeFQString(&buf, "dup")
+ putInt32(&buf, 1)
+ writeFQString(&buf, "b")
+ putInt32(&buf, 0)
+
+ d := NewGraphBinaryDeserializer(&buf)
+ result, err := d.readTree()
+ if err != nil {
+ t.Fatalf("readTree error: %v", err)
+ }
+ got := result.(*Tree)
+ if len(got.entries) != 1 {
+ t.Fatalf("duplicate sibling keys should collapse to 1 entry, got %d", len(got.entries))
+ }
+ if !reflect.DeepEqual(got.RootNodes(), []interface{}{"dup"}) {
+ t.Fatalf("root nodes = %v, want [dup]", got.RootNodes())
+ }
+ merged, err := got.ChildAt("dup")
+ if err != nil {
+ t.Fatalf("ChildAt(dup) error: %v", err)
+ }
+ if !merged.HasChild("a") || !merged.HasChild("b") {
+ t.Fatalf("merged subtree should contain both a and b, got %v", merged.RootNodes())
+ }
+}
+
+// TestTreeDeserializerNullKeyRoundTrip verifies that a nil key (encoded as a
+// fully-qualified null, not coerced to a string) survives deserialization with
+// its subtree intact.
+func TestTreeDeserializerNullKeyRoundTrip(t *testing.T) {
+ var buf bytes.Buffer
+ // root: one entry whose key is a fully-qualified null and whose child has
+ // key "child".
+ putInt32(&buf, 1)
+ writeFQNull(&buf)
+ putInt32(&buf, 1)
+ writeFQString(&buf, "child")
+ putInt32(&buf, 0)
+
+ d := NewGraphBinaryDeserializer(&buf)
+ result, err := d.readTree()
+ if err != nil {
+ t.Fatalf("readTree error: %v", err)
+ }
+ got := result.(*Tree)
+ if !got.HasChild(nil) {
+ t.Fatalf("deserialized tree should have a nil key child")
+ }
+ sub, err := got.ChildAt(nil)
+ if err != nil {
+ t.Fatalf("ChildAt(nil) error: %v", err)
+ }
+ if !sub.HasChild("child") {
+ t.Fatalf("nil key subtree should contain 'child'")
+ }
+}
+
+// TestTreeEqualsElementKeys verifies that structural equality treats graph
+// element keys by id and concrete type (via keyEquals), independent of sibling
+// insertion order and other element fields.
+func TestTreeEqualsElementKeys(t *testing.T) {
+ t1 := &Tree{}
+ t1.GetOrCreateChild(&Vertex{Element: Element{Id: 1, Label: "a"}}).
+ GetOrCreateChild(&Vertex{Element: Element{Id: 2}})
+ t1.GetOrCreateChild(&Edge{Element: Element{Id: 3}})
+
+ // Same ids/types, different labels and reversed sibling order -> Equals.
+ t2 := &Tree{}
+ t2.GetOrCreateChild(&Edge{Element: Element{Id: 3, Label: "x"}})
+ t2.GetOrCreateChild(&Vertex{Element: Element{Id: 1, Label: "b"}}).
+ GetOrCreateChild(&Vertex{Element: Element{Id: 2, Label: "c"}})
+ if !t1.Equals(t2) {
+ t.Fatalf("trees with element keys equal by id/type should be Equals")
+ }
+
+ // Differing id in a subtree -> not Equals.
+ t3 := &Tree{}
+ t3.GetOrCreateChild(&Vertex{Element: Element{Id: 1}}).
+ GetOrCreateChild(&Vertex{Element: Element{Id: 99}})
+ t3.GetOrCreateChild(&Edge{Element: Element{Id: 3}})
+ if t1.Equals(t3) {
+ t.Fatalf("trees differing in an element subtree key id should not be Equals")
+ }
+
+ // Type mismatch at root (Vertex vs Edge, same id) -> not Equals.
+ t4 := &Tree{}
+ t4.GetOrCreateChild(&Edge{Element: Element{Id: 1}}).
+ GetOrCreateChild(&Vertex{Element: Element{Id: 2}})
+ t4.GetOrCreateChild(&Edge{Element: Element{Id: 3}})
+ if t1.Equals(t4) {
+ t.Fatalf("trees differing in element key concrete type should not be Equals")
+ }
+}
+
+// ---- Common-standard cases shared across all four GLVs ----
+
+// TestTreeAddTreeNilPanics verifies that AddTree(nil) is rejected: a nil
+// argument is invalid and dereferencing it (ranging over other.entries) causes
+// a nil-pointer panic, matching the addTree(null) rejection asserted by the
+// other GLVs.
+func TestTreeAddTreeNilPanics(t *testing.T) {
+ tree := buildSampleTree()
+
+ defer func() {
+ if r := recover(); r == nil {
+ t.Fatalf("AddTree(nil) should panic, but it did not")
+ }
+ }()
+
+ tree.AddTree(nil)
+}
+
+// TestTreeSplitParentsSingleRoot verifies that splitting a single-root tree
+// returns a singleton slice whose one element equals the original tree.
+func TestTreeSplitParentsSingleRoot(t *testing.T) {
+ tree := &Tree{}
+ tree.GetOrCreateChild("a").GetOrCreateChild("b")
+
+ parents := tree.SplitParents()
+ if len(parents) != 1 {
+ t.Fatalf("SplitParents() on single-root tree len = %d, want 1", len(parents))
+ }
+ if !parents[0].Equals(tree) {
+ t.Fatalf("SplitParents() single result should Equals the original tree")
+ }
+}
+
+// TestTreeSplitParentsMultiRootAndEmpty verifies that a multi-root tree splits
+// into N single-key trees (each retaining its original subtree), and that an
+// empty tree's SplitParents() returns an empty slice.
+func TestTreeSplitParentsMultiRootAndEmpty(t *testing.T) {
+ // Multi-root: a -> b, c, d. Expect 3 single-key trees.
+ tree := &Tree{}
+ tree.GetOrCreateChild("a").GetOrCreateChild("b")
+ tree.GetOrCreateChild("c")
+ tree.GetOrCreateChild("d")
+
+ parents := tree.SplitParents()
+ if len(parents) != 3 {
+ t.Fatalf("SplitParents() multi-root len = %d, want 3", len(parents))
+ }
+ gotRoots := make([]interface{}, 0, len(parents))
+ for _, p := range parents {
+ if len(p.RootNodes()) != 1 {
+ t.Fatalf("each split tree should have exactly 1 root, got %v", p.RootNodes())
+ }
+ gotRoots = append(gotRoots, p.RootNodes()[0])
+ }
+ if !reflect.DeepEqual(gotRoots, []interface{}{"a", "c", "d"}) {
+ t.Fatalf("split root keys = %v, want [a c d]", gotRoots)
+ }
+ // The "a" split should retain its original "b" subtree.
+ aSplit := parents[0]
+ aChild, err := aSplit.ChildAt("a")
+ if err != nil || !aChild.HasChild("b") {
+ t.Fatalf("split 'a' tree should retain child 'b': err=%v", err)
+ }
+
+ // Empty tree -> empty split.
+ empty := &Tree{}
+ if got := empty.SplitParents(); len(got) != 0 {
+ t.Fatalf("SplitParents() on empty tree len = %d, want 0", len(got))
+ }
+}
+
+// TestTreeGetLeafTrees verifies that GetLeafTrees returns one single-key tree
+// per leaf, and that each returned tree has exactly one root node which is a
+// leaf key of the original tree.
+func TestTreeGetLeafTrees(t *testing.T) {
+ tree := buildSampleTree() // leaves: c, e
+
+ leafTrees := tree.GetLeafTrees()
+ if len(leafTrees) != 2 {
+ t.Fatalf("GetLeafTrees len = %d, want 2", len(leafTrees))
+ }
+
+ gotLeaves := make([]interface{}, 0, len(leafTrees))
+ for _, lt := range leafTrees {
+ roots := lt.RootNodes()
+ if len(roots) != 1 {
+ t.Fatalf("each leaf tree should have exactly 1 root node, got %v", roots)
+ }
+ // The single root must itself be a leaf in the returned tree.
+ if !lt.IsLeaf() {
+ sub, err := lt.ChildAt(roots[0])
+ if err != nil {
+ t.Fatalf("leaf tree ChildAt(%v) error: %v", roots[0], err)
+ }
+ if !sub.IsLeaf() {
+ t.Fatalf("leaf tree key %v should map to a leaf subtree", roots[0])
+ }
+ }
+ gotLeaves = append(gotLeaves, roots[0])
+ }
+ if !reflect.DeepEqual(gotLeaves, []interface{}{"c", "e"}) {
+ t.Fatalf("GetLeafTrees root keys = %v, want [c e]", gotLeaves)
+ }
+}
+
+// TestTreeChildAtMissingKey verifies the Go idiom for a missing key: ChildAt
+// returns a non-nil error and a nil tree.
+func TestTreeChildAtMissingKey(t *testing.T) {
+ tree := buildSampleTree()
+
+ child, err := tree.ChildAt("missing")
+ if err == nil {
+ t.Fatalf("ChildAt(missing) should return a non-nil error")
+ }
+ if child != nil {
+ t.Fatalf("ChildAt(missing) should return a nil tree, got %v", child)
+ }
+}
diff --git a/gremlin-js/gremlin-javascript/lib/index.ts b/gremlin-js/gremlin-javascript/lib/index.ts
index 69bc83cfbb..56994fe3cf 100644
--- a/gremlin-js/gremlin-javascript/lib/index.ts
+++ b/gremlin-js/gremlin-javascript/lib/index.ts
@@ -88,6 +88,7 @@ export const structure = {
Edge: graph.Edge,
Graph: graph.Graph,
Path: graph.Path,
+ Tree: graph.Tree,
Property: graph.Property,
PrimitivePDT: graph.PrimitivePDT,
CompositePDT: graph.CompositePDT,
diff --git a/gremlin-js/gremlin-javascript/lib/structure/graph.ts b/gremlin-js/gremlin-javascript/lib/structure/graph.ts
index 41d2947b72..0af2fc74b4 100644
--- a/gremlin-js/gremlin-javascript/lib/structure/graph.ts
+++ b/gremlin-js/gremlin-javascript/lib/structure/graph.ts
@@ -151,6 +151,289 @@ export class Property<T = any> {
}
}
+/**
+ * A tree data structure with a tree-shaped public API.
+ *
+ * Children are kept in a private, ordered array of {key, value} entries (not a
+ * native {@link Map}, whose reference-identity keys would break value-equality).
+ * Access is only through the read API; lookups use {@link treeKeysEqual}, which
+ * compares keys by value and treats null/undefined as a distinct key.
+ */
+export class Tree {
+ #entries: Array<{ key: any; value: Tree }>;
+
+ constructor(...rootValues: any[]) {
+ this.#entries = [];
+ for (const value of rootValues) {
+ this.#entries.push({ key: value, value: new Tree() });
+ }
+ }
+
+ /**
+ * Locates the entry whose key is structurally equal to the given key.
+ * @returns the matching entry, or undefined if none exists.
+ */
+ private _findEntry(key: any): { key: any; value: Tree } | undefined {
+ for (const entry of this.#entries) {
+ if (treeKeysEqual(entry.key, key)) {
+ return entry;
+ }
+ }
+ return undefined;
+ }
+
+ /**
+ * Returns the keys at the root of this tree.
+ */
+ rootNodes(): any[] {
+ return this.#entries.map((e) => e.key);
+ }
+
+ /**
+ * Returns the child subtree for the given key.
+ * @throws {Error} if no child exists for the given key.
+ */
+ childAt(key: any): Tree {
+ const entry = this._findEntry(key);
+ if (entry === undefined) {
+ throw new Error(`Tree has no child for key: ${key}`);
+ }
+ return entry.value;
+ }
+
+ /**
+ * Returns true if the given key is an immediate child of this tree.
+ */
+ hasChild(key: any): boolean {
+ return this._findEntry(key) !== undefined;
+ }
+
+ /**
+ * Returns true if the given value appears as a key anywhere in this tree (recursive).
+ */
+ contains(value: any): boolean {
+ for (const entry of this.#entries) {
+ if (treeKeysEqual(entry.key, value)) {
+ return true;
+ }
+ }
+ for (const entry of this.#entries) {
+ if (entry.value.contains(value)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Recursively searches the tree for the first subtree rooted at key.
+ * @returns the matching subtree, or undefined if absent.
+ */
+ findSubtree(key: any): Tree | undefined {
+ const entry = this._findEntry(key);
+ if (entry !== undefined) {
+ return entry.value;
+ }
+ for (const e of this.#entries) {
+ const found = e.value.findSubtree(key);
+ if (found !== undefined) {
+ return found;
+ }
+ }
+ return undefined;
+ }
+
+ /**
+ * Returns the existing child for key, or inserts and returns a new empty Tree if absent.
+ */
+ getOrCreateChild(key: any): Tree {
+ const entry = this._findEntry(key);
+ if (entry !== undefined) {
+ return entry.value;
+ }
+ const child = new Tree();
+ this.#entries.push({ key, value: child });
+ return child;
+ }
+
+ /**
+ * Returns true if this tree has no children. An empty tree is considered a leaf.
+ */
+ isLeaf(): boolean {
+ return this.#entries.length === 0;
+ }
+
+ /**
+ * Returns the total number of nodes (keys) in the tree, counted recursively.
+ */
+ nodeCount(): number {
+ let count = this.#entries.length;
+ for (const entry of this.#entries) {
+ count += entry.value.nodeCount();
+ }
+ return count;
+ }
+
+ /**
+ * Returns the keys at the given depth. Depth 0 returns the root keys.
+ * Negative depths or depths beyond the tree's height return an empty array.
+ */
+ getNodesAtDepth(depth: number): any[] {
+ const list: any[] = [];
+ for (const t of this.getTreesAtDepth(depth)) {
+ for (const entry of t.#entries) {
+ list.push(entry.key);
+ }
+ }
+ return list;
+ }
+
+ /**
+ * Returns the trees at the given depth. Depth 0 returns a singleton list containing this tree.
+ * Negative depths or depths beyond the tree's height return an empty array.
+ */
+ getTreesAtDepth(depth: number): Tree[] {
+ if (depth < 0) {
+ return [];
+ }
+ let currentDepth: Tree[] = [this];
+ for (let i = 0; i < depth; i++) {
+ const next: Tree[] = [];
+ for (const t of currentDepth) {
+ for (const entry of t.#entries) {
+ next.push(entry.value);
+ }
+ }
+ if (next.length === 0) {
+ return [];
+ }
+ currentDepth = next;
+ }
+ return currentDepth;
+ }
+
+ /**
+ * Returns all keys whose subtrees are leaves.
+ */
+ getLeafNodes(): any[] {
+ const leaves: any[] = [];
+ this._collectLeafKeys(leaves);
+ return leaves;
+ }
+
+ private _collectLeafKeys(out: any[]): void {
+ for (const entry of this.#entries) {
+ if (entry.value.isLeaf()) {
+ out.push(entry.key);
+ } else {
+ entry.value._collectLeafKeys(out);
+ }
+ }
+ }
+
+ /**
+ * Returns single-key trees representing each leaf key in this tree, preserving the original
+ * key-to-empty-subtree mapping.
+ */
+ getLeafTrees(): Tree[] {
+ const leaves: Tree[] = [];
+ this._collectLeafTrees(leaves);
+ return leaves;
+ }
+
+ private _collectLeafTrees(out: Tree[]): void {
+ for (const entry of this.#entries) {
+ if (entry.value.isLeaf()) {
+ const leaf = new Tree();
+ leaf.#entries.push({ key: entry.key, value: entry.value });
+ out.push(leaf);
+ } else {
+ entry.value._collectLeafTrees(out);
+ }
+ }
+ }
+
+ /**
+ * Recursively merges other into this tree. For overlapping keys, child subtrees are merged in turn.
+ * For keys present only in other, the corresponding subtree reference is adopted directly.
+ */
+ addTree(other: Tree): void {
+ for (const entry of other.#entries) {
+ const existing = this._findEntry(entry.key);
+ if (existing !== undefined) {
+ existing.value.addTree(entry.value);
+ } else {
+ this.#entries.push({ key: entry.key, value: entry.value });
+ }
+ }
+ }
+
+ /**
+ * Splits this tree into one tree per root key. If the tree has a single root, returns a singleton list
+ * containing this tree.
+ */
+ splitParents(): Tree[] {
+ if (this.#entries.length === 1) {
+ return [this];
+ }
+ const parents: Tree[] = [];
+ for (const entry of this.#entries) {
+ const parentTree = new Tree();
+ parentTree.#entries.push({ key: entry.key, value: entry.value });
+ parents.push(parentTree);
+ }
+ return parents;
+ }
+
+ /**
+ * Produces a formatted string representation of the tree structure using a |-- ASCII style,
+ * Uses a |-- ASCII style with a 3-space indent per level and no trailing newline.
+ */
+ prettyPrint(): string {
+ const lines: string[] = [];
+ this._prettyPrint(lines, '');
+ return lines.join('\n');
+ }
+
+ private _prettyPrint(lines: string[], prefix: string): void {
+ for (const entry of this.#entries) {
+ lines.push(`${prefix}|--${entry.key}`);
+ entry.value._prettyPrint(lines, `${prefix} `);
+ }
+ }
+
+ /**
+ * Structural recursive equality. Order across siblings is irrelevant; two trees are equal if they have the
+ * same set of keys and each key's subtree is recursively equal.
+ */
+ equals(other: any): boolean {
+ if (this === other) {
+ return true;
+ }
+ if (!(other instanceof Tree)) {
+ return false;
+ }
+ if (this.#entries.length !== other.#entries.length) {
+ return false;
+ }
+ for (const entry of this.#entries) {
+ const match = other._findEntry(entry.key);
+ if (match === undefined) {
+ return false;
+ }
+ if (!entry.value.equals(match.value)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ toString(): string {
+ const parts = this.#entries.map((e) => `${e.key}=${e.value.toString()}`);
+ return `{${parts.join(', ')}}`;
+ }
+}
+
/**
* Represents a walk through a graph as defined by a traversal.
*/
@@ -175,6 +458,25 @@ export class Path {
}
}
+/**
+ * Null-safe structural key comparison for Tree keys, built on {@link areEqual}.
+ * areEqual dereferences obj.equals, so null/undefined keys are handled here first.
+ * Element keys also require matching concrete type (the shared {@link Element.equals}
+ * compares by id only), so a Vertex and an Edge with the same id stay distinct keys.
+ */
+function treeKeysEqual(a: any, b: any): boolean {
+ if (a === b) {
+ return true;
+ }
+ if (a === null || a === undefined || b === null || b === undefined) {
+ return false;
+ }
+ if (a instanceof Element && b instanceof Element && a.constructor !== b.constructor) {
+ return false;
+ }
+ return areEqual(a, b);
+}
+
function areEqual(obj1: any, obj2: any) {
if (obj1 === obj2) {
return true;
diff --git a/gremlin-js/gremlin-javascript/lib/structure/io/binary/GraphBinary.js b/gremlin-js/gremlin-javascript/lib/structure/io/binary/GraphBinary.js
index 188c44be7c..0e151b5a4b 100644
--- a/gremlin-js/gremlin-javascript/lib/structure/io/binary/GraphBinary.js
+++ b/gremlin-js/gremlin-javascript/lib/structure/io/binary/GraphBinary.js
@@ -30,7 +30,6 @@
* TODO: it has the following open topics:
* Core Data Types support:
* - [] 0x22: BigDecimal
- * - [] 0x2b: Tree
* Extended Types support:
* - [] 0x80: Char
* - [] 0x81: Duration
@@ -53,6 +52,7 @@ import SetSerializer from './internals/SetSerializer.js';
import UuidSerializer from './internals/UuidSerializer.js';
import EdgeSerializer from './internals/EdgeSerializer.js';
import PathSerializer from './internals/PathSerializer.js';
+import TreeSerializer from './internals/TreeSerializer.js';
import PropertySerializer from './internals/PropertySerializer.js';
import VertexSerializer from './internals/VertexSerializer.js';
import VertexPropertySerializer from './internals/VertexPropertySerializer.js';
@@ -109,9 +109,7 @@ function createIoc(anySerializerOptions) {
ioc.enumSerializer = new EnumSerializer(ioc);
ioc.compositePDTSerializer = new CompositePDTSerializer(ioc);
ioc.primitivePDTSerializer = new PrimitivePDTSerializer(ioc);
-
- // Register stub serializers for unimplemented v4 types
- new StubSerializer(ioc, ioc.DataType.TREE, 'Tree');
+ ioc.treeSerializer = new TreeSerializer(ioc);
ioc.pdtRegistry = null;
@@ -179,6 +177,7 @@ export const {
enumSerializer,
compositePDTSerializer,
primitivePDTSerializer,
+ treeSerializer,
numberSerializationStrategy,
anySerializer,
graphBinaryReader,
diff --git a/gremlin-js/gremlin-javascript/lib/structure/io/binary/internals/AnySerializer.js b/gremlin-js/gremlin-javascript/lib/structure/io/binary/internals/AnySerializer.js
index e4010789bc..c26290c73b 100644
--- a/gremlin-js/gremlin-javascript/lib/structure/io/binary/internals/AnySerializer.js
+++ b/gremlin-js/gremlin-javascript/lib/structure/io/binary/internals/AnySerializer.js
@@ -46,6 +46,7 @@ export default class AnySerializer {
ioc.binarySerializer,
ioc.primitivePDTSerializer,
ioc.compositePDTSerializer,
+ ioc.treeSerializer,
ioc.mapSerializer,
];
}
diff --git a/gremlin-js/gremlin-javascript/lib/structure/io/binary/internals/TreeSerializer.js b/gremlin-js/gremlin-javascript/lib/structure/io/binary/internals/TreeSerializer.js
new file mode 100644
index 0000000000..fbb9174be2
--- /dev/null
+++ b/gremlin-js/gremlin-javascript/lib/structure/io/binary/internals/TreeSerializer.js
@@ -0,0 +1,146 @@
+/*
+ * 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.
+ */
+
+import { Buffer } from 'buffer';
+import { Tree } from '../../../graph.js';
+
+/**
+ * GraphBinary serializer for the Tree type (0x2b).
+ *
+ * Wire format (authoritative from Java TreeSerializer):
+ * value = {int length} then length x ( {fully-qualified key} {bare child Tree} )
+ * A child Tree is written bare: just {int length}{entries...}, with no type-id
+ * and no value-flag, recursively. A leaf is length 0. The child is never null,
+ * but a key may be null.
+ */
+export default class TreeSerializer {
+ constructor(ioc) {
+ this.ioc = ioc;
+ this.ioc.serializers[ioc.DataType.TREE] = this;
+ }
+
+ canBeUsedFor(value) {
+ return value instanceof Tree;
+ }
+
+ serialize(item, fullyQualifiedFormat = true) {
+ if (item === undefined || item === null) {
+ if (fullyQualifiedFormat) {
+ return Buffer.from([this.ioc.DataType.TREE, 0x01]);
+ }
+ // bare null -> empty tree (length 0)
+ return this.ioc.intSerializer.serialize(0, false);
+ }
+
+ const bufs = [];
+ if (fullyQualifiedFormat) {
+ bufs.push(Buffer.from([this.ioc.DataType.TREE, 0x00]));
+ }
+ bufs.push(this._serializeValue(item));
+ return Buffer.concat(bufs);
+ }
+
+ /**
+ * Serializes the bare value of a Tree: {int length} then, for each root key, a
+ * fully-qualified key followed by a bare child Tree (recursive).
+ *
+ * Uses only the public read API ({@link Tree#rootNodes} / {@link Tree#childAt})
+ * so it never touches the Tree's private backing. Keys returned by rootNodes()
+ * are already deduped, so each is written exactly once.
+ * @param {Tree} tree
+ * @returns {Buffer}
+ */
+ _serializeValue(tree) {
+ const keys = tree.rootNodes();
+ let length = keys.length;
+ if (length < 0) {
+ length = 0;
+ } else if (length > this.ioc.intSerializer.INT32_MAX) {
+ length = this.ioc.intSerializer.INT32_MAX;
+ }
+
+ const bufs = [this.ioc.intSerializer.serialize(length, false)];
+ for (let i = 0; i < length; i++) {
+ const key = keys[i];
+ // fully-qualified key
+ bufs.push(this.ioc.anySerializer.serialize(key));
+ // bare child tree (no type_code, no value_flag)
+ bufs.push(this._serializeValue(tree.childAt(key)));
+ }
+ return Buffer.concat(bufs);
+ }
+
+ /**
+ * Async deserialization of tree value bytes from a StreamReader.
+ * @param {StreamReader} reader
+ * @param {number} valueFlag
+ * @param {number} typeCode
+ * @returns {Promise<Tree>}
+ */
+ async deserializeValue(reader, valueFlag, typeCode) {
+ return await this._readTreeValue(reader);
+ }
+
+ /**
+ * Reads a bare tree value: {int length} then length x ( fully-qualified key,
+ * bare child tree ). The child recursion reads bare values (no type_code,
+ * no value_flag).
+ *
+ * Duplicate sibling keys are collapsed via {@link Tree#getOrCreateChild} +
+ * {@link Tree#addTree} (a server emitting
+ * the same sibling key twice yields a single merged entry, not duplicates).
+ * @param {StreamReader} reader
+ * @returns {Promise<Tree>}
+ */
+ async _readTreeValue(reader) {
+ const length = await this.ioc.intSerializer.deserializeBare(reader);
+
+ const tree = new Tree();
+ for (let i = 0; i < length; i++) {
+ // {fully-qualified key} - read with type_code + value_flag.
+ const key = await this.ioc.anySerializer.deserialize(reader);
+ // {bare child tree} - never null, no type_code / value_flag
+ const child = await this._readTreeValue(reader);
+ // Merge into any existing entry for this key so duplicate sibling keys
+ // collapse into a single entry.
+ tree.getOrCreateChild(key).addTree(child);
+ }
+ return tree;
+ }
+
+ /**
+ * Async fully-qualified deserialization from a StreamReader.
+ * @param {StreamReader} reader
+ * @returns {Promise<Tree|null>}
+ */
+ async deserialize(reader) {
+ const type_code = await reader.readUInt8();
+ if (type_code !== this.ioc.DataType.TREE) {
+ throw new Error(`TreeSerializer: unexpected {type_code}=0x${type_code.toString(16)}`);
+ }
+ const value_flag = await reader.readUInt8();
+ if (value_flag === 0x01) {
+ return null;
+ }
+ if (value_flag !== 0x00) {
+ throw new Error(`TreeSerializer: unexpected {value_flag}=0x${value_flag.toString(16)}`);
+ }
+ return this.deserializeValue(reader, value_flag, type_code);
+ }
+}
diff --git a/gremlin-js/gremlin-javascript/test/cucumber/feature-steps.js b/gremlin-js/gremlin-javascript/test/cucumber/feature-steps.js
index 7982d31c3d..1c3ecf8d9f 100644
--- a/gremlin-js/gremlin-javascript/test/cucumber/feature-steps.js
+++ b/gremlin-js/gremlin-javascript/test/cucumber/feature-steps.js
@@ -29,7 +29,7 @@ import { use, expect } from 'chai';
use(chaiString);
import { inspect, format, inherits } from 'util';
import { gremlin } from './gremlin.js';
-import { Path, Vertex, Edge, Property, Graph } from '../../lib/structure/graph.js';
+import { Path, Vertex, Edge, Property, Graph, Tree } from '../../lib/structure/graph.js';
import { statics } from '../../lib/process/graph-traversal.js';
import { t, P, direction, merge, barrier, cardinality, column, order, TextP, IO, pick, pop, scope, operator, withOptions } from '../../lib/process/traversal.js';
import { toLong } from '../../lib/utils.js';
@@ -75,25 +75,11 @@ const ignoreReason = {
nullKeysInMapNotSupportedWell: "Javascript does not nicely support 'null' as a key in Map instances",
floatingPointIssues: "Javascript floating point numbers not working in this case",
uuidSerializationIssues: "Javascript does not serialize to a UUID object, which complicates test assertions",
- treeStepNotSupported: "Javascript does not yet support tree()",
needsFurtherInvestigation: '',
};
// An associative array for ignored feature tests containing the scenario name as key
const ignoredScenarios = {
- // javascript doesn't have tree() step yet
- 'g_VX1X_out_out_tree_byXnameX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_out_out_tree': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_V_out_tree_byXageX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_out_out_treeXaX_byXnameX_both_both_capXaX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_out_out_treeXaX_both_both_capXaX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_out_out_tree_byXlabelX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_out_out_treeXaX_byXlabelX_both_both_capXaX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_out_out_out_tree': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_outE_inV_bothE_otherV_tree': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_VX1X_outE_inV_bothE_otherV_tree_byXnameX_byXlabelX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_V_out_treeXaX_selectXaX_countXlocalX': new IgnoreError(ignoreReason.treeStepNotSupported),
- 'g_V_out_order_byXnameX_localXtreeXaX_selectXaX_countXlocalXX': new IgnoreError(ignoreReason.treeStepNotSupported),
// floating point issues
'g_withSackXBigInteger_TEN_powX1000X_assignX_V_localXoutXknowsX_barrierXnormSackXX_inXknowsX_barrier_sack': new IgnoreError(ignoreReason.floatingPointIssues),
'g_withSackX2X_V_sackXdivX_byXconstantX4_0XX_sack': new IgnoreError(ignoreReason.floatingPointIssues),
@@ -304,10 +290,79 @@ Then('the result should be a subgraph with the following', function (resultTable
}
});
-Then('the result should be a tree with a structure of', _ => {
- // tree is not supported yet in javascript
+Then('the result should be a tree with a structure of', function (expectedTree) {
+ expect(this.result).to.not.be.a.instanceof(Error);
+
+ // The traversal yields a single Tree (via "iterated next"), stored directly on this.result.
+ const tree = this.result;
+ expect(tree).to.be.a.instanceof(Tree, 'expected the result to be a Tree');
+
+ // an empty doc string represents an empty tree
+ const roots = parseTree.call(this, expectedTree);
+
+ // validate that the tree matches the parsed expected structure
+ expect(tree.rootNodes().length).to.equal(roots.length,
+ 'tree root node count does not match expected structure');
+ for (const root of roots) {
+ expect(tree.hasChild(root.value)).to.equal(true,
+ format('tree not matching at %s', inspect(root.value)));
+ validateTreeStructure.call(this, tree.childAt(root.value), root);
+ }
});
+function validateTreeStructure(actualTree, expectedNode) {
+ expect(actualTree.rootNodes().length).to.equal(expectedNode.children.length,
+ format('tree child count does not match at %s', inspect(expectedNode.value)));
+ for (const child of expectedNode.children) {
+ expect(actualTree.hasChild(child.value)).to.equal(true,
+ format('tree not matching at %s', inspect(child.value)));
+ validateTreeStructure.call(this, actualTree.childAt(child.value), child);
+ }
+}
+
+// Parses the ascii-tree structure as taken from the Gherkin feature file. Mirrors the Java
+// StepDefinition.parseTree (and the .NET CommonSteps.ParseTree): a line's depth is the number of
+// leading spaces divided by three, and the node value is the line with the leading "|--" marker
+// stripped and trimmed, then run through parseValue.
+function parseTree(asciiTree) {
+ const roots = [];
+ if (asciiTree === undefined || asciiTree === null || asciiTree.length === 0) {
+ return roots;
+ }
+
+ const lines = asciiTree.split(/\r\n|\r|\n/);
+ const levelMap = {};
+
+ for (const line of lines) {
+ if (line.length === 0) {
+ continue;
+ }
+
+ let leadingSpaces = 0;
+ for (const c of line) {
+ if (c === ' ') {
+ leadingSpaces++;
+ } else {
+ break;
+ }
+ }
+ const level = Math.floor(leadingSpaces / 3); // 3 spaces per level
+ const rawValue = line.replace('|--', '').trim();
+
+ const node = { value: parseValue.call(this, rawValue), children: [] };
+ if (level === 0) {
+ roots.push(node);
+ } else {
+ levelMap[level - 1].children.push(node);
+ }
+
+ levelMap[level] = node;
+ }
+
+ return roots;
+}
+
+
Then(/^the graph should return (\d+) for count of "(.+)"$/, function (stringCount, traversalText) {
expect(this.result).to.not.be.a.instanceof(Error);
diff --git a/gremlin-js/gremlin-javascript/test/integration/tree-test.js b/gremlin-js/gremlin-javascript/test/integration/tree-test.js
new file mode 100644
index 0000000000..6ac6208e18
--- /dev/null
+++ b/gremlin-js/gremlin-javascript/test/integration/tree-test.js
@@ -0,0 +1,64 @@
+/*
+ * 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.
+ */
+
+import assert from 'assert';
+import { Tree } from '../../lib/structure/graph.js';
+import anon from '../../lib/process/anonymous-traversal.js';
+import { getConnection } from '../helper.js';
+
+let connection;
+
+describe('Tree', function () {
+ before(function () {
+ connection = getConnection('gmodern');
+ return connection.open();
+ });
+ after(function () {
+ return connection.close();
+ });
+
+ it('should return a navigable Tree from tree()', async function () {
+ const g = anon.traversal().with_(connection);
+ const item = await g.V(1).out().out().tree().by('name').next();
+ const tree = item.value;
+ assert.ok(tree instanceof Tree);
+ // read API (camelCase) confirmed against lib/structure/graph.ts
+ assert.strictEqual(tree.rootNodes().length, 1);
+ assert.strictEqual(tree.nodeCount(), 4); // marko/josh/lop/ripple
+ assert.deepStrictEqual(tree.getNodesAtDepth(0), ['marko']);
+ // siblings order-insensitive:
+ assert.deepStrictEqual(tree.getNodesAtDepth(2).sort(), ['lop', 'ripple']);
+ assert.deepStrictEqual(tree.getLeafNodes().sort(), ['lop', 'ripple']);
+ assert.strictEqual(tree.isLeaf(), false);
+ // whole-output equality; lop/ripple siblings at depth 2 have unspecified order
+ const optionA = '|--marko\n |--josh\n |--lop\n |--ripple';
+ const optionB = '|--marko\n |--josh\n |--ripple\n |--lop';
+ const pretty = tree.prettyPrint();
+ assert.ok(pretty === optionA || pretty === optionB, `Unexpected prettyPrint output:\n${pretty}`);
+ });
+
+ it('should return a vertex-keyed Tree by default', async function () {
+ const g = anon.traversal().with_(connection);
+ const item = await g.V(1).out().out().tree().next();
+ const tree = item.value;
+ assert.ok(tree instanceof Tree);
+ assert.strictEqual(tree.nodeCount(), 4);
+ assert.strictEqual(tree.rootNodes().length, 1);
+ });
+});
diff --git a/gremlin-js/gremlin-javascript/test/unit/graphbinary/model-test.js b/gremlin-js/gremlin-javascript/test/unit/graphbinary/model-test.js
index 28be83f886..bca8a47d7a 100644
--- a/gremlin-js/gremlin-javascript/test/unit/graphbinary/model-test.js
+++ b/gremlin-js/gremlin-javascript/test/unit/graphbinary/model-test.js
@@ -240,6 +240,21 @@ describe('GraphBinary v4 Model Tests', () => {
runWriteRead('set-cardinality-vertexproperty', setCardinalityComparator);
runWriteRead('traversal-vertex');
+ // Tree
+ runWriteRead('traversal-tree'); // vertex properties aren't serialized
+
+ // empty-tree has no .gbin resource, so exercise an in-memory round trip
+ describe('empty-tree', () => {
+ it('in-memory round trip', async () => {
+ const empty = model['empty-tree'];
+ const roundTripped = await anySerializer.deserialize(
+ StreamReader.fromBuffer(anySerializer.serialize(empty)),
+ );
+ assert.deepStrictEqual(roundTripped, empty);
+ assert.isTrue(roundTripped.isLeaf());
+ });
+ });
+
// runRead mode (5 entries)
runRead('neg-zero-float', negZeroComparator);
runRead('max-offsetdatetime', invalidDateComparator);
@@ -247,10 +262,9 @@ describe('GraphBinary v4 Model Tests', () => {
runRead('prop-path');
runRead('var-type-map');
- // skip mode (8 entries)
+ // skip mode (7 entries)
skip('single-byte-char', 'Char type (0x80) not implemented');
skip('multi-byte-char', 'Char type (0x80) not implemented');
- skip('traversal-tree', 'Tree type not implemented');
skip('tinker-graph', 'Graph type not implemented');
skip('pos-bigdecimal', 'BigDecimal type not implemented');
skip('neg-bigdecimal', 'BigDecimal type not implemented');
diff --git a/gremlin-js/gremlin-javascript/test/unit/graphbinary/model.js b/gremlin-js/gremlin-javascript/test/unit/graphbinary/model.js
index b064273aa8..63aa9dbfb3 100644
--- a/gremlin-js/gremlin-javascript/test/unit/graphbinary/model.js
+++ b/gremlin-js/gremlin-javascript/test/unit/graphbinary/model.js
@@ -17,13 +17,12 @@
* under the License.
*/
-import { Vertex, Edge, Property, VertexProperty, Path } from '../../../lib/structure/graph.js';
+import { Vertex, Edge, Property, VertexProperty, Path, Tree } from '../../../lib/structure/graph.js';
import { direction, t } from '../../../lib/process/traversal.js';
/*
* Unsupported types (no map entries, .gbin files exist but types not implemented):
* - single-byte-char, multi-byte-char (Char 0x80 not implemented)
- * - traversal-tree (Tree type not implemented)
* - tinker-graph (Graph type not implemented)
* - pos-bigdecimal, neg-bigdecimal (BigDecimal type not implemented)
* - forever-duration, zero-duration (Duration type not implemented)
@@ -120,6 +119,13 @@ model['traversal-path'] = new Path(
);
model['empty-path'] = new Path([], []);
+// Tree values
+// tree for g.V(10).out().tree(): v[10] -> v[11]
+const traversalTree = new Tree();
+traversalTree.getOrCreateChild(new Vertex(10, 'software')).getOrCreateChild(new Vertex(11, 'software'));
+model['traversal-tree'] = traversalTree;
+model['empty-tree'] = new Tree();
+
// Complex path with nested properties
const propPathVertex = new Vertex(1, 'person', [
new VertexProperty(0, 'name', 'marko'),
diff --git a/gremlin-js/gremlin-javascript/test/unit/graphbinary/tree-serializer-test.js b/gremlin-js/gremlin-javascript/test/unit/graphbinary/tree-serializer-test.js
new file mode 100644
index 0000000000..ad21a7a916
--- /dev/null
+++ b/gremlin-js/gremlin-javascript/test/unit/graphbinary/tree-serializer-test.js
@@ -0,0 +1,296 @@
+/*
+ * 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.
+ */
+
+import { assert } from 'chai';
+import { Buffer } from 'buffer';
+import ioc from '../../../lib/structure/io/binary/GraphBinary.js';
+import StreamReader from '../../../lib/structure/io/binary/internals/StreamReader.js';
+import { Tree, Vertex, Edge } from '../../../lib/structure/graph.js';
+
+/**
+ * Round-trip tests for the GraphBinary Tree (0x2b) serializer: serialize a Tree
+ * with the sync serializer and deserialize it with the async StreamReader path,
+ * then assert structure and exercise the read API.
+ */
+describe('GraphBinary TreeSerializer (0x2b)', () => {
+ async function roundTrip(value) {
+ const buf = ioc.treeSerializer.serialize(value);
+ const reader = StreamReader.fromBuffer(buf);
+ return ioc.anySerializer.deserialize(reader);
+ }
+
+ // Build a tree:
+ // a -> { b -> { d }, c }
+ // e
+ function buildTree() {
+ const tree = new Tree();
+ const a = tree.getOrCreateChild('a');
+ const b = a.getOrCreateChild('b');
+ b.getOrCreateChild('d');
+ a.getOrCreateChild('c');
+ tree.getOrCreateChild('e');
+ return tree;
+ }
+
+ it('round-trips an empty (leaf) tree', async () => {
+ const result = await roundTrip(new Tree());
+ assert.instanceOf(result, Tree);
+ assert.isTrue(result.isLeaf());
+ assert.deepEqual(result.rootNodes(), []);
+ });
+
+ it('round-trips a nested tree preserving structure', async () => {
+ const original = buildTree();
+ const result = await roundTrip(original);
+
+ assert.instanceOf(result, Tree);
+ assert.isTrue(result.equals(original));
+ assert.deepEqual(result.rootNodes(), ['a', 'e']);
+ });
+
+ it('exposes the full read API on the deserialized tree', async () => {
+ const result = await roundTrip(buildTree());
+
+ // navigation
+ assert.isTrue(result.hasChild('a'));
+ assert.isFalse(result.hasChild('z'));
+ assert.instanceOf(result.childAt('a'), Tree);
+ assert.throws(() => result.childAt('z'));
+
+ // contains is recursive
+ assert.isTrue(result.contains('d'));
+ assert.isFalse(result.contains('missing'));
+
+ // findSubtree is recursive
+ const subD = result.findSubtree('d');
+ assert.instanceOf(subD, Tree);
+ assert.isTrue(subD.isLeaf());
+ assert.isUndefined(result.findSubtree('missing'));
+
+ // structural counts
+ assert.equal(result.nodeCount(), 5); // a, b, d, c, e
+ assert.deepEqual(result.getNodesAtDepth(0), ['a', 'e']);
+ assert.deepEqual(result.getNodesAtDepth(1).sort(), ['b', 'c']);
+ assert.deepEqual(result.getNodesAtDepth(2), ['d']);
+ assert.deepEqual(result.getNodesAtDepth(99), []);
+ assert.deepEqual(result.getNodesAtDepth(-1), []);
+
+ assert.equal(result.getTreesAtDepth(0).length, 1);
+ assert.strictEqual(result.getTreesAtDepth(0)[0], result);
+
+ // leaves
+ assert.deepEqual(result.getLeafNodes().sort(), ['c', 'd', 'e']);
+ assert.equal(result.getLeafTrees().length, 3);
+
+ // splitParents: two roots -> two single-root trees
+ const parents = result.splitParents();
+ assert.equal(parents.length, 2);
+ });
+
+ it('prettyPrint matches the canonical |-- style with no trailing newline', async () => {
+ const result = await roundTrip(buildTree());
+ const expected = ['|--a', ' |--b', ' |--d', ' |--c', '|--e'].join('\n');
+ assert.equal(result.prettyPrint(), expected);
+ });
+
+ it('uses value-equality (not reference) for keys', async () => {
+ // Two structurally-equal array keys should resolve to the same child.
+ const tree = new Tree();
+ tree.getOrCreateChild([1, 2]).getOrCreateChild('leaf');
+ const child = tree.getOrCreateChild([1, 2]); // same value, different reference
+ assert.equal(tree.rootNodes().length, 1);
+ assert.isTrue(child.hasChild('leaf'));
+ });
+
+ it('Tree.equals is order-insensitive and structural (standalone)', () => {
+ // Build two trees with the same structure but sibling keys inserted in a
+ // different order; structural equality must ignore order.
+ // a -> { b }, c
+ const t1 = new Tree();
+ t1.getOrCreateChild('a').getOrCreateChild('b');
+ t1.getOrCreateChild('c');
+
+ const t2 = new Tree();
+ t2.getOrCreateChild('c');
+ t2.getOrCreateChild('a').getOrCreateChild('b');
+
+ assert.isTrue(t1.equals(t2), 'same structure, reversed sibling order should be equal');
+ assert.isTrue(t2.equals(t1), 'equals should be symmetric');
+ assert.isTrue(t1.equals(t1), 'a tree equals itself');
+
+ // Empty trees are equal.
+ assert.isTrue(new Tree().equals(new Tree()));
+
+ // Differing subtree structure -> not equal (key 'x' instead of 'b').
+ const tDiff = new Tree();
+ tDiff.getOrCreateChild('a').getOrCreateChild('x');
+ tDiff.getOrCreateChild('c');
+ assert.isFalse(t1.equals(tDiff), 'differing subtree key should not be equal');
+
+ // Differing entry count -> not equal (missing root 'c').
+ const tFewer = new Tree();
+ tFewer.getOrCreateChild('a').getOrCreateChild('b');
+ assert.isFalse(t1.equals(tFewer), 'differing entry count should not be equal');
+
+ // Non-Tree argument -> not equal (and must not throw).
+ assert.isFalse(t1.equals(null));
+ assert.isFalse(t1.equals(undefined));
+ assert.isFalse(t1.equals({}));
+ assert.isFalse(t1.equals('a'));
+ });
+
+ it('serializes null as a fully-qualified null and deserializes to null', async () => {
+ const result = await roundTrip(null);
+ assert.isNull(result);
+ });
+
+ it('round-trips a null KEY (not a null tree) preserving its subtree', async () => {
+ // A null key is a legitimate, distinct key. Nest a child under it and
+ // confirm the null key and its subtree survive a GraphBinary round trip.
+ const tree = new Tree();
+ tree.getOrCreateChild(null).getOrCreateChild('child');
+
+ const result = await roundTrip(tree);
+ assert.instanceOf(result, Tree);
+ assert.isTrue(result.hasChild(null));
+ assert.isTrue(result.childAt(null).hasChild('child'));
+ });
+
+ it('collapses duplicate sibling keys into a single entry on deserialize', async () => { // Hand-craft wire bytes for a tree whose root has the SAME key twice, each
+ // carrying a distinct child. A compliant server would never do this, but a
+ // hostile/buggy one might; the deserializer must merge them into one entry
+ // (matching the Go/Python/.NET GLVs) rather than producing duplicates.
+ // length=2
+ // key='dup', child={ 'a' -> {} }
+ // key='dup', child={ 'b' -> {} }
+ const int32 = (n) => ioc.intSerializer.serialize(n, false);
+ const childTree = (...keys) => {
+ const bufs = [int32(keys.length)];
+ for (const k of keys) {
+ bufs.push(ioc.anySerializer.serialize(k)); // fully-qualified key
+ bufs.push(int32(0)); // bare empty child tree
+ }
+ return Buffer.concat(bufs);
+ };
+
+ const value = Buffer.concat([
+ int32(2),
+ ioc.anySerializer.serialize('dup'),
+ childTree('a'),
+ ioc.anySerializer.serialize('dup'),
+ childTree('b'),
+ ]);
+ // Prepend the fully-qualified Tree header: {type_code=0x2b}{value_flag=0x00}.
+ const buf = Buffer.concat([Buffer.from([ioc.DataType.TREE, 0x00]), value]);
+
+ const reader = StreamReader.fromBuffer(buf);
+ const result = await ioc.anySerializer.deserialize(reader);
+
+ assert.instanceOf(result, Tree);
+ // The two 'dup' siblings collapse into a single root entry...
+ assert.deepEqual(result.rootNodes(), ['dup']);
+ assert.equal(result.rootNodes().length, 1);
+ // ...whose subtree is the merge of both children.
+ const merged = result.childAt('dup');
+ assert.isTrue(merged.hasChild('a'));
+ assert.isTrue(merged.hasChild('b'));
+ });
+
+ // -------------------------------------------------------------------------
+ // Explicit Tree read-API cases, mirroring the common standard exercised by
+ // the Java/.NET/Go/Python GLV Tree tests. These were previously bundled into
+ // 'exposes the full read API' or absent entirely.
+ // -------------------------------------------------------------------------
+
+ it('dedups element keys by id AND concrete type', () => {
+ // Two vertices with the same id collapse to one root entry, even when their
+ // labels differ - element identity is id-based, not label-based.
+ const sameId = new Tree();
+ sameId.getOrCreateChild(new Vertex(1, 'person'));
+ sameId.getOrCreateChild(new Vertex(1, 'software'));
+ assert.equal(sameId.rootNodes().length, 1, 'Vertex(1) twice -> single entry');
+
+ // Two vertices with distinct ids are distinct keys.
+ const diffId = new Tree();
+ diffId.getOrCreateChild(new Vertex(1, 'person'));
+ diffId.getOrCreateChild(new Vertex(2, 'person'));
+ assert.equal(diffId.rootNodes().length, 2, 'Vertex(1) and Vertex(2) -> two entries');
+
+ // A Vertex and an Edge sharing the same id are distinct keys: element key
+ // equality is concrete-type aware (verifies the treeKeysEqual Part A fix).
+ const mixed = new Tree();
+ mixed.getOrCreateChild(new Vertex(1, 'person'));
+ mixed.getOrCreateChild(new Edge(1, new Vertex(2, 'person'), 'knows', new Vertex(3, 'person')));
+ assert.equal(mixed.rootNodes().length, 2, 'Vertex(1) and Edge(1) are different concrete types -> two entries');
+ });
+
+ it('childAt throws for a missing key', () => {
+ const tree = new Tree();
+ tree.getOrCreateChild('present');
+ assert.throws(() => tree.childAt('missing'), Error);
+ });
+
+ it('addTree(null) throws', () => {
+ const tree = new Tree();
+ // Merging a null/undefined tree dereferences other.#entries and must throw.
+ assert.throws(() => tree.addTree(null));
+ assert.throws(() => tree.addTree(undefined));
+ });
+
+ it('splitParents returns one tree per root (single, multi, empty)', () => {
+ // Single root -> singleton list containing the tree itself.
+ const single = new Tree();
+ single.getOrCreateChild('a').getOrCreateChild('b');
+ const singleParents = single.splitParents();
+ assert.equal(singleParents.length, 1);
+ assert.strictEqual(singleParents[0], single);
+
+ // Multiple roots -> one single-root tree per root key.
+ const multi = new Tree();
+ multi.getOrCreateChild('a');
+ multi.getOrCreateChild('b');
+ multi.getOrCreateChild('c');
+ const multiParents = multi.splitParents();
+ assert.equal(multiParents.length, 3);
+ for (const p of multiParents) {
+ assert.equal(p.rootNodes().length, 1);
+ }
+
+ // Empty tree -> empty list.
+ assert.deepEqual(new Tree().splitParents(), []);
+ });
+
+ it('getLeafTrees returns one single-key tree per leaf', () => {
+ // Tree: a -> { b -> { d }, c }, e => leaves are d, c, e.
+ const tree = new Tree();
+ const a = tree.getOrCreateChild('a');
+ a.getOrCreateChild('b').getOrCreateChild('d');
+ a.getOrCreateChild('c');
+ tree.getOrCreateChild('e');
+
+ const leafTrees = tree.getLeafTrees();
+ assert.equal(leafTrees.length, 3, 'one tree per leaf key');
+ for (const lt of leafTrees) {
+ assert.instanceOf(lt, Tree);
+ assert.equal(lt.rootNodes().length, 1, 'each leaf tree holds a single key');
+ }
+ const leafKeys = leafTrees.map((lt) => lt.rootNodes()[0]).sort();
+ assert.deepEqual(leafKeys, ['c', 'd', 'e']);
+ });
+});
diff --git a/gremlin-python/src/main/python/gremlin_python/structure/graph.py b/gremlin-python/src/main/python/gremlin_python/structure/graph.py
index c8e528966d..43fc77671c 100644
--- a/gremlin-python/src/main/python/gremlin_python/structure/graph.py
+++ b/gremlin-python/src/main/python/gremlin_python/structure/graph.py
@@ -339,3 +339,232 @@ def provider_defined(name=None, included_fields=None, excluded_fields=None):
_pdt_decorated_types[cls._pdt_name] = cls
return cls
return decorator
+
+
+class Tree(object):
+ """
+ A tree data structure with a tree-shaped public API.
+
+ Children are backed by an ordered list of ``(key, subtree)`` entries,
+ preserving insertion order and using value-equality (``==``) for key lookup
+ so keys need not be hashable. ``None`` keys are supported.
+ """
+
+ def __init__(self, entries=None):
+ # internal ordered list of [key, subtree] pairs
+ self._entries = []
+ if entries is not None:
+ for key, child in entries:
+ if not isinstance(child, Tree):
+ raise TypeError("Tree entries must map a key to a Tree, got: " + repr(child))
+ self._entries.append([key, child])
+
+ # ------------------------------------------------------------------
+ # internal helpers
+ # ------------------------------------------------------------------
+
+ def _find_entry(self, key):
+ for entry in self._entries:
+ if entry[0] == key:
+ return entry
+ return None
+
+ # ------------------------------------------------------------------
+ # navigation
+ # ------------------------------------------------------------------
+
+ def root_nodes(self):
+ """Returns the list of keys at the root of this tree, in insertion order."""
+ return [entry[0] for entry in self._entries]
+
+ def child_at(self, key):
+ """
+ Returns the child subtree for the given key.
+
+ :raises KeyError: if no immediate child exists for the given key
+ """
+ entry = self._find_entry(key)
+ if entry is None:
+ raise KeyError("Tree has no child for key: " + str(key))
+ return entry[1]
+
+ def has_child(self, key):
+ """Returns True if the given key is an immediate child of this tree."""
+ return self._find_entry(key) is not None
+
+ def contains(self, value):
+ """Returns True if the given value appears as a key anywhere in this tree (recursive)."""
+ for key, child in self._entries:
+ if key == value or child.contains(value):
+ return True
+ return False
+
+ def find_subtree(self, key):
+ """
+ Recursively searches the tree for the first subtree rooted at ``key`` and
+ returns it, or ``None`` if not found. Direct children are visited before
+ recursing.
+ """
+ for k, child in self._entries:
+ if k == key:
+ return child
+ for _, child in self._entries:
+ found = child.find_subtree(key)
+ if found is not None:
+ return found
+ return None
+
+ def get_or_create_child(self, key):
+ """Returns the existing child for ``key``, or inserts and returns a new empty Tree if absent."""
+ entry = self._find_entry(key)
+ if entry is None:
+ child = Tree()
+ self._entries.append([key, child])
+ return child
+ return entry[1]
+
+ # ------------------------------------------------------------------
+ # structural
+ # ------------------------------------------------------------------
+
+ def is_leaf(self):
+ """Returns True if this tree has no children. An empty tree is considered a leaf."""
+ return len(self._entries) == 0
+
+ def node_count(self):
+ """Returns the total number of nodes (keys) in the tree, counted recursively."""
+ count = len(self._entries)
+ for _, child in self._entries:
+ count += child.node_count()
+ return count
+
+ def get_nodes_at_depth(self, depth):
+ """
+ Returns the keys at the given depth. Depth 0 returns the root keys.
+
+ Negative depths and depths beyond the tree's height return an empty list.
+ """
+ nodes = []
+ for tree in self.get_trees_at_depth(depth):
+ nodes.extend(tree.root_nodes())
+ return nodes
+
+ def get_trees_at_depth(self, depth):
+ """
+ Returns the trees at the given depth. Depth 0 returns a singleton list
+ containing this tree. Negative depths and depths beyond the tree's
+ height return an empty list.
+ """
+ if depth < 0:
+ return []
+ current = [self]
+ for _ in range(depth):
+ nxt = []
+ for tree in current:
+ nxt.extend(entry[1] for entry in tree._entries)
+ if not nxt:
+ return []
+ current = nxt
+ return current
+
+ def get_leaf_nodes(self):
+ """Returns all keys whose subtrees are leaves (recursive)."""
+ leaves = []
+ self._collect_leaf_keys(leaves)
+ return leaves
+
+ def _collect_leaf_keys(self, out):
+ for key, child in self._entries:
+ if child.is_leaf():
+ out.append(key)
+ else:
+ child._collect_leaf_keys(out)
+
+ def get_leaf_trees(self):
+ """Returns single-key trees representing each leaf key in this tree (recursive)."""
+ leaves = []
+ self._collect_leaf_trees(leaves)
+ return leaves
+
+ def _collect_leaf_trees(self, out):
+ for key, child in self._entries:
+ if child.is_leaf():
+ out.append(Tree([(key, child)]))
+ else:
+ child._collect_leaf_trees(out)
+
+ # ------------------------------------------------------------------
+ # composition
+ # ------------------------------------------------------------------
+
+ def add_tree(self, other):
+ """
+ Recursively merges ``other`` into this tree. For overlapping keys (by
+ value-equality) child subtrees are merged in turn. For keys present only
+ in ``other`` the corresponding subtree reference is adopted directly.
+ """
+ for key, child in other._entries:
+ entry = self._find_entry(key)
+ if entry is None:
+ self._entries.append([key, child])
+ else:
+ entry[1].add_tree(child)
+
+ def split_parents(self):
+ """
+ Splits this tree into one tree per root key. If the tree has a single
+ root, returns a singleton list containing this tree.
+ """
+ if len(self._entries) == 1:
+ return [self]
+ return [Tree([(key, child)]) for key, child in self._entries]
+
+ # ------------------------------------------------------------------
+ # output
+ # ------------------------------------------------------------------
+
+ def pretty_print(self):
+ """
+ Produces a formatted string representation of the tree structure using a
+ ``|--`` ASCII style, matching Java's ``Tree.prettyPrint``.
+
+ Each level is indented by 3 spaces relative to its parent. The returned
+ string has no trailing newline.
+ """
+ lines = []
+ self._pretty_print(lines, "")
+ return "\n".join(lines)
+
+ def _pretty_print(self, lines, prefix):
+ for key, child in self._entries:
+ lines.append(prefix + "|--" + str(key))
+ child._pretty_print(lines, prefix + " ")
+
+ # ------------------------------------------------------------------
+ # identity
+ # ------------------------------------------------------------------
+
+ def __eq__(self, other):
+ if not isinstance(other, Tree):
+ return NotImplemented
+ if len(self._entries) != len(other._entries):
+ return False
+ for key, child in self._entries:
+ matched = False
+ for okey, ochild in other._entries:
+ if okey == key:
+ if ochild != child:
+ return False
+ matched = True
+ break
+ if not matched:
+ return False
+ return True
+
+ def __hash__(self):
+ # structurally-equal trees share the same number of root entries, so this
+ # is consistent with __eq__ while remaining valid for unhashable keys.
+ return hash(len(self._entries))
+
+ def __repr__(self):
+ return "{" + ", ".join(str(key) + "=" + repr(child) for key, child in self._entries) + "}"
diff --git a/gremlin-python/src/main/python/gremlin_python/structure/io/graphbinaryV4.py b/gremlin-python/src/main/python/gremlin_python/structure/io/graphbinaryV4.py
index 887941db15..73605e0bb3 100644
--- a/gremlin-python/src/main/python/gremlin_python/structure/io/graphbinaryV4.py
+++ b/gremlin-python/src/main/python/gremlin_python/structure/io/graphbinaryV4.py
@@ -31,7 +31,7 @@ from gremlin_python.process.traversal import Direction, T, Merge
from gremlin_python.statics import FloatType, BigDecimal, ShortType, IntType, LongType, BigIntType, \
DictType, SetType, SingleByte, SingleChar
from gremlin_python.structure.graph import Graph, Edge, Property, Vertex, VertexProperty, Path, CompositePDT, \
- PrimitivePDT, _pdt_decorated_types
+ PrimitivePDT, Tree, _pdt_decorated_types
from gremlin_python.structure.io.util import HashableDict, SymbolUtil, Marker
log = logging.getLogger(__name__)
@@ -70,7 +70,7 @@ class DataType(Enum):
binary = 0x25
short = 0x26
boolean = 0x27
- tree = 0x2b # not supported - no tree object in Python yet
+ tree = 0x2b
char = 0x80
duration = 0x81
composite_pdt = 0xf0
@@ -656,6 +656,42 @@ class PathIO(_GraphBinaryTypeIO):
return cls.is_null(buff, reader, lambda b, r: Path(r.read_object(b), r.read_object(b)), nullable)
+class TreeIO(_GraphBinaryTypeIO):
+
+ python_type = Tree
+ graphbinary_type = DataType.tree
+
+ @classmethod
+ def dictify(cls, obj, writer, to_extend, as_value=False, nullable=True):
+ # when as_value (a nested/bare child tree) prefix_bytes writes nothing:
+ # no type-id and no null flag. As a root value it writes {type-id}{null flag}.
+ cls.prefix_bytes(cls.graphbinary_type, as_value, nullable, to_extend)
+ root_nodes = obj.root_nodes()
+ to_extend.extend(int32_pack(len(root_nodes)))
+ for key in root_nodes:
+ child = obj.child_at(key)
+ # key is written fully-qualified (its own type-id + null flag + value)
+ writer.to_dict(key, to_extend)
+ # child is written as a BARE tree value: no type-id, no null flag
+ cls.dictify(child, writer, to_extend, as_value=True, nullable=False)
+ return to_extend
+
+ @classmethod
+ def objectify(cls, buff, reader, nullable=True):
+ return cls.is_null(buff, reader, cls._read_tree, nullable)
+
+ @classmethod
+ def _read_tree(cls, b, r):
+ size = cls.read_int(b)
+ tree = Tree()
+ while size > 0:
+ key = r.read_object(b)
+ child = cls.objectify(b, r, False)
+ tree.get_or_create_child(key).add_tree(child)
+ size = size - 1
+ return tree
+
+
class PropertyIO(_GraphBinaryTypeIO):
python_type = Property
diff --git a/gremlin-python/src/main/python/tests/feature/feature_steps.py b/gremlin-python/src/main/python/tests/feature/feature_steps.py
index f40c3fa91e..30958e1821 100644
--- a/gremlin-python/src/main/python/tests/feature/feature_steps.py
+++ b/gremlin-python/src/main/python/tests/feature/feature_steps.py
@@ -24,7 +24,7 @@ import json
import re
import uuid
from gremlin_python.statics import long, bigdecimal, SingleChar
-from gremlin_python.structure.graph import Path, Vertex, Graph, Edge, VertexProperty, Property
+from gremlin_python.structure.graph import Path, Vertex, Graph, Edge, VertexProperty, Property, Tree
from gremlin_python.process.anonymous_traversal import traversal
from gremlin_python.process.graph_traversal import __
from gremlin_python.process.traversal import Barrier, Cardinality, P, TextP, Pop, Scope, Column, Order, Direction, T, \
@@ -81,8 +81,6 @@ def choose_graph(step, graph_name):
if not step.context.ignore:
step.context.ignore = "AllowNullPropertyValues" in tagset
- if not step.context.ignore:
- step.context.ignore = "StepTree" in tagset
if not step.context.ignore:
step.context.ignore = "StepWrite" in tagset
@@ -285,6 +283,77 @@ def assert_subgraph(step):
assert_that(actual.inV.id, equal_to(expected.inV.id))
+class _TreeNode(object):
+ """One node of an expected tree parsed from a Gherkin ascii-tree docstring:
+ a parsed key value with its ordered children."""
+
+ def __init__(self, value):
+ self.value = value
+ self.children = []
+
+
+def _parse_tree(ascii_tree, ctx):
+ """Parses an ascii-tree docstring into root nodes. A line's depth is its
+ leading-space count divided by three; the node value is the line with the
+ leading ``|--`` stripped, trimmed, and passed through ``_convert``. An empty
+ docstring yields no roots."""
+ roots = []
+ if not ascii_tree:
+ return roots
+
+ level_map = {}
+ for line in re.split(r"\r\n|\r|\n", ascii_tree):
+ if len(line) == 0:
+ continue
+
+ leading_spaces = len(line) - len(line.lstrip(" "))
+ level = leading_spaces // 3 # 3 spaces per level
+ raw_value = line.replace("|--", "", 1).strip()
+
+ node = _TreeNode(_convert(raw_value, ctx))
+ if level == 0:
+ roots.append(node)
+ else:
+ level_map[level - 1].children.append(node)
+ level_map[level] = node
+
+ return roots
+
+
+def _validate_tree_structure(actual_tree, expected_node):
+ """Recursively asserts that ``actual_tree`` matches ``expected_node``: the
+ child count must match and every expected child must be present and
+ recursively match."""
+ assert_that(len(actual_tree.root_nodes()), equal_to(len(expected_node.children)),
+ "tree child count does not match at " + str(expected_node.value))
+ for child in expected_node.children:
+ assert_that(actual_tree.has_child(child.value), equal_to(True),
+ "tree not matching at " + str(child.value))
+ _validate_tree_structure(actual_tree.child_at(child.value), child)
+
+
+@then("the result should be a tree with a structure of")
+def assert_tree_structure(step):
+ if step.context.ignore:
+ return
+
+ assert_that(step.context.failed, equal_to(False), step.context.failed_message)
+
+ # The traversal yields a single Tree (via "iterated next").
+ tree = step.context.result[0]
+ assert_that(tree, instance_of(Tree))
+
+ # an empty docstring represents an empty tree
+ roots = _parse_tree(step.text, step.context)
+
+ assert_that(len(tree.root_nodes()), equal_to(len(roots)),
+ "tree root node count does not match expected structure")
+ for root in roots:
+ assert_that(tree.has_child(root.value), equal_to(True),
+ "tree not matching at " + str(root.value))
+ _validate_tree_structure(tree.child_at(root.value), root)
+
+
@then("the graph should return {count:d} for count of {traversal_string:QuotedString}")
def assert_side_effects(step, count, traversal_string):
if step.context.ignore:
diff --git a/gremlin-python/src/main/python/tests/integration/driver/test_driver_remote_connection.py b/gremlin-python/src/main/python/tests/integration/driver/test_driver_remote_connection.py
index 94e3cb0941..ac85211483 100644
--- a/gremlin-python/src/main/python/tests/integration/driver/test_driver_remote_connection.py
+++ b/gremlin-python/src/main/python/tests/integration/driver/test_driver_remote_connection.py
@@ -162,6 +162,51 @@ class TestDriverRemoteConnection(object):
assert isinstance(e, Edge)
assert e.label == 'knows'
+ def test_tree(self, remote_connection):
+ from gremlin_python.structure.graph import Tree
+ g = traversal().with_(remote_connection)
+ # modern graph: marko -> josh -> lop/ripple, depth 2
+ tree = g.V(1).out().out().tree().by('name').next()
+ assert isinstance(tree, Tree)
+
+ # root level: only marko
+ assert tree.root_nodes() == ['marko']
+
+ # marko's child subtree is rooted at josh
+ marko_subtree = tree.child_at('marko')
+ assert marko_subtree.root_nodes() == ['josh']
+
+ # total key count across marko/josh/lop/ripple
+ assert tree.node_count() == 4
+
+ # depth navigation
+ assert tree.get_nodes_at_depth(0) == ['marko']
+ depth_two = tree.get_nodes_at_depth(2)
+ assert set(depth_two) == {'lop', 'ripple'}
+
+ # leaf nodes are lop and ripple (order-insensitive)
+ assert set(tree.get_leaf_nodes()) == {'lop', 'ripple'}
+
+ # root tree is not a leaf
+ assert tree.is_leaf() is False
+
+ # pretty print produces the ASCII tree style
+ printed = tree.pretty_print()
+ assert isinstance(printed, str)
+ # lop and ripple are siblings at depth 2 with unspecified order
+ option_a = "|--marko\n |--josh\n |--lop\n |--ripple"
+ option_b = "|--marko\n |--josh\n |--ripple\n |--lop"
+ assert tree.pretty_print() in (option_a, option_b)
+
+ def test_tree_with_vertices(self, remote_connection):
+ from gremlin_python.structure.graph import Tree
+ g = traversal().with_(remote_connection)
+ # no by(): keys are the vertices themselves (the default user-facing shape)
+ tree = g.V(1).out().out().tree().next()
+ assert isinstance(tree, Tree)
+ assert tree.node_count() == 4
+ assert len(tree.root_nodes()) == 1
+
def test_set_with_unhashable_elements(self, remote_connection):
g = traversal().withRemote(remote_connection)
# g.V().valueMap().dedup(Scope.local) returns a Set of Map results which previously
diff --git a/gremlin-python/src/main/python/tests/unit/structure/io/model.py b/gremlin-python/src/main/python/tests/unit/structure/io/model.py
index f6100cc128..dae5c04297 100644
--- a/gremlin-python/src/main/python/tests/unit/structure/io/model.py
+++ b/gremlin-python/src/main/python/tests/unit/structure/io/model.py
@@ -20,7 +20,7 @@ under the License.
import datetime
import uuid
from gremlin_python.statics import short, long, bigint, BigDecimal, SingleByte
-from gremlin_python.structure.graph import Vertex, Edge, Property, VertexProperty, Path
+from gremlin_python.structure.graph import Vertex, Edge, Property, VertexProperty, Path, Tree
from gremlin_python.process.traversal import Direction, Traverser, T
"""
@@ -37,7 +37,6 @@ nan-float single precision float not supported in Python
pos-inf-float single precision float not supported in Python
neg-inf-float single precision float not supported in Python
neg-zero-float single precision float not supported in Python
-traversal-tree Tree type not implemented
"""
model = {}
@@ -99,6 +98,13 @@ model["traversal-path"] = Path(
[Vertex(1, "person"), Vertex(10, "software"), Vertex(11, "software")]
)
model["empty-path"] = Path([], [])
+
+# tree for g.V(10).out().tree(): v[10] -> v[11]
+_traversal_tree = Tree()
+_traversal_tree.get_or_create_child(Vertex(10, "software")).get_or_create_child(Vertex(11, "software"))
+model["traversal-tree"] = _traversal_tree
+model["empty-tree"] = Tree()
+
model["prop-path"] = Path(
[set(), set(), set()],
[
diff --git a/gremlin-python/src/main/python/tests/unit/structure/io/test_graphbinaryv4model.py b/gremlin-python/src/main/python/tests/unit/structure/io/test_graphbinaryv4model.py
index 84598218d4..4ebc739584 100644
--- a/gremlin-python/src/main/python/tests/unit/structure/io/test_graphbinaryv4model.py
+++ b/gremlin-python/src/main/python/tests/unit/structure/io/test_graphbinaryv4model.py
@@ -158,6 +158,20 @@ def test_traversal_path():
def test_empty_path():
run("empty-path")
+def test_traversal_tree():
+ # gremlin-python doesn't serialize vertex properties, so the read tree's
+ # vertices have no properties; vertex equality is by id so the model matches.
+ run_writeread("traversal-tree")
+
+def test_empty_tree():
+ # no .gbin resource exists for an empty tree, so exercise an in-memory round trip
+ from gremlin_python.structure.graph import Tree
+ empty = model["empty-tree"]
+ round_tripped = reader.read_object(writer.write_object(empty))
+ assert isinstance(round_tripped, Tree)
+ assert empty == round_tripped
+ assert round_tripped.is_leaf()
+
def test_prop_path():
# gremlin-python doesn't serialize properties
run_writeread("prop-path")
diff --git a/gremlin-python/src/main/python/tests/unit/structure/test_tree.py b/gremlin-python/src/main/python/tests/unit/structure/test_tree.py
new file mode 100644
index 0000000000..22bcd1b1b4
--- /dev/null
+++ b/gremlin-python/src/main/python/tests/unit/structure/test_tree.py
@@ -0,0 +1,329 @@
+"""
+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.
+"""
+import pytest
+
+from gremlin_python.structure.graph import Tree
+from gremlin_python.structure.io.graphbinaryV4 import GraphBinaryWriter, GraphBinaryReader
+
+writer = GraphBinaryWriter()
+reader = GraphBinaryReader()
+
+
+def build_tree():
+ """
+ Builds the following tree in-memory (mirrors Go's TestTreeReadAPI fixture):
+
+ a
+ |-- b
+ | |-- d
+ | |-- e
+ |-- c
+ | |-- f
+ """
+ tree = Tree()
+ a = tree.get_or_create_child("a")
+ b = a.get_or_create_child("b")
+ b.get_or_create_child("d")
+ b.get_or_create_child("e")
+ c = a.get_or_create_child("c")
+ c.get_or_create_child("f")
+ return tree
+
+
+def test_root_nodes():
+ tree = build_tree()
+ assert tree.root_nodes() == ["a"]
+ assert tree.child_at("a").root_nodes() == ["b", "c"]
+
+
+def test_child_at():
+ tree = build_tree()
+ a = tree.child_at("a")
+ assert isinstance(a, Tree)
+ assert a.root_nodes() == ["b", "c"]
+
+
+def test_child_at_missing_key_raises():
+ tree = build_tree()
+ with pytest.raises(KeyError):
+ tree.child_at("does-not-exist")
+
+
+def test_has_child():
+ tree = build_tree()
+ assert tree.has_child("a") is True
+ assert tree.has_child("b") is False
+ assert tree.child_at("a").has_child("b") is True
+ assert tree.child_at("a").has_child("z") is False
+
+
+def test_contains():
+ tree = build_tree()
+ assert tree.contains("a") is True
+ assert tree.contains("d") is True
+ assert tree.contains("f") is True
+ assert tree.contains("z") is False
+
+
+def test_find_subtree():
+ tree = build_tree()
+ b = tree.find_subtree("b")
+ assert b is not None
+ assert b.root_nodes() == ["d", "e"]
+ assert tree.find_subtree("f").is_leaf()
+ assert tree.find_subtree("z") is None
+
+
+def test_get_or_create_child():
+ tree = Tree()
+ first = tree.get_or_create_child("k")
+ assert isinstance(first, Tree)
+ # returns the existing child on re-request rather than replacing it
+ first.get_or_create_child("nested")
+ second = tree.get_or_create_child("k")
+ assert second is first
+ assert second.has_child("nested")
+ assert tree.root_nodes() == ["k"]
+
+
+def test_is_leaf():
+ tree = build_tree()
+ assert tree.is_leaf() is False
+ assert tree.find_subtree("d").is_leaf() is True
+ assert Tree().is_leaf() is True
+
+
+def test_node_count():
+ tree = build_tree()
+ # a, b, c, d, e, f
+ assert tree.node_count() == 6
+ assert Tree().node_count() == 0
+
+
+def test_get_nodes_at_depth():
+ tree = build_tree()
+ assert tree.get_nodes_at_depth(0) == ["a"]
+ assert tree.get_nodes_at_depth(1) == ["b", "c"]
+ assert tree.get_nodes_at_depth(2) == ["d", "e", "f"]
+ # out of range
+ assert tree.get_nodes_at_depth(3) == []
+ # negative
+ assert tree.get_nodes_at_depth(-1) == []
+
+
+def test_get_trees_at_depth():
+ tree = build_tree()
+ depth0 = tree.get_trees_at_depth(0)
+ assert depth0 == [tree]
+ depth1 = tree.get_trees_at_depth(1)
+ assert len(depth1) == 1
+ assert depth1[0].root_nodes() == ["b", "c"]
+ depth2 = tree.get_trees_at_depth(2)
+ roots = []
+ for t in depth2:
+ roots.extend(t.root_nodes())
+ assert roots == ["d", "e", "f"]
+ # depth 3 is the (empty) subtrees hanging off the leaf nodes d, e, f: they
+ # exist as empty trees, so no nodes but three empty trees are returned.
+ depth3 = tree.get_trees_at_depth(3)
+ assert len(depth3) == 3
+ assert all(t.is_leaf() for t in depth3)
+ # depth 4 is genuinely beyond the tree's height -> empty list
+ assert tree.get_trees_at_depth(4) == []
+ assert tree.get_trees_at_depth(-1) == []
+
+
+def test_get_leaf_nodes():
+ tree = build_tree()
+ assert tree.get_leaf_nodes() == ["d", "e", "f"]
+
+
+def test_get_leaf_trees():
+ tree = build_tree()
+ leaf_trees = tree.get_leaf_trees()
+ roots = [t.root_nodes()[0] for t in leaf_trees]
+ assert roots == ["d", "e", "f"]
+ for t in leaf_trees:
+ assert len(t.root_nodes()) == 1
+ assert t.child_at(t.root_nodes()[0]).is_leaf()
+
+
+def test_add_tree_merge():
+ base = Tree()
+ a = base.get_or_create_child("a")
+ a.get_or_create_child("b")
+
+ other = Tree()
+ oa = other.get_or_create_child("a")
+ oa.get_or_create_child("c")
+ other.get_or_create_child("x")
+
+ base.add_tree(other)
+
+ assert base.root_nodes() == ["a", "x"]
+ # overlapping key 'a' has both 'b' (original) and 'c' (merged in)
+ assert base.child_at("a").root_nodes() == ["b", "c"]
+ # key present only in other adopted directly
+ assert base.has_child("x")
+
+
+def test_split_parents_multiple():
+ tree = Tree()
+ tree.get_or_create_child("a").get_or_create_child("a1")
+ tree.get_or_create_child("b").get_or_create_child("b1")
+
+ parts = tree.split_parents()
+ assert len(parts) == 2
+ assert parts[0].root_nodes() == ["a"]
+ assert parts[0].child_at("a").root_nodes() == ["a1"]
+ assert parts[1].root_nodes() == ["b"]
+
+
+def test_split_parents_single():
+ tree = build_tree()
+ parts = tree.split_parents()
+ assert parts == [tree]
+
+
+def test_add_tree_none_raises():
+ # Merging a None tree is invalid: add_tree dereferences other._entries,
+ # which raises on a None argument (AttributeError/TypeError).
+ tree = build_tree()
+ with pytest.raises((AttributeError, TypeError)):
+ tree.add_tree(None)
+
+
+def test_element_keys_dedup_by_id_and_type():
+ from gremlin_python.structure.graph import Vertex, Edge
+
+ # Same id, differing label/properties -> same Element (Element.__eq__ is
+ # isinstance(self.__class__) and id == id), so the key collapses.
+ same_id = Tree()
+ same_id.get_or_create_child(Vertex(1, "person"))
+ same_id.get_or_create_child(Vertex(1, "software"))
+ assert len(same_id.root_nodes()) == 1
+
+ # Differing ids -> two distinct keys.
+ diff_id = Tree()
+ diff_id.get_or_create_child(Vertex(1))
+ diff_id.get_or_create_child(Vertex(2))
+ assert len(diff_id.root_nodes()) == 2
+
+ # Same id but different concrete type (Vertex vs Edge) -> two distinct keys.
+ diff_type = Tree()
+ diff_type.get_or_create_child(Vertex(1))
+ diff_type.get_or_create_child(Edge(1, Vertex(2), "knows", Vertex(3)))
+ assert len(diff_type.root_nodes()) == 2
+
+
+def test_hash_consistent_with_eq():
+ # Equal trees must have equal hashes. Python's Tree.__hash__ is based on the
+ # root entry count, which structurally-equal trees share.
+ t1 = build_tree()
+ t2 = build_tree()
+ assert t1 == t2
+ assert hash(t1) == hash(t2)
+
+
+def test_pretty_print():
+ tree = build_tree()
+ expected = "\n".join([
+ "|--a",
+ " |--b",
+ " |--d",
+ " |--e",
+ " |--c",
+ " |--f",
+ ])
+ assert tree.pretty_print() == expected
+ # no trailing newline
+ assert not tree.pretty_print().endswith("\n")
+
+
+def test_eq_order_insensitivity():
+ t1 = Tree()
+ r1 = t1.get_or_create_child("root")
+ r1.get_or_create_child("a")
+ r1.get_or_create_child("b")
+
+ t2 = Tree()
+ r2 = t2.get_or_create_child("root")
+ # insert in reversed sibling order
+ r2.get_or_create_child("b")
+ r2.get_or_create_child("a")
+
+ assert t1 == t2
+ assert not (t1 != t2)
+
+
+def test_eq_differing_structure():
+ t1 = build_tree()
+ t2 = build_tree()
+ assert t1 == t2
+ t2.child_at("a").get_or_create_child("extra")
+ assert t1 != t2
+
+
+def test_null_key_round_trip():
+ tree = Tree()
+ tree.get_or_create_child(None).get_or_create_child("child")
+
+ round_tripped = reader.read_object(writer.write_object(tree))
+
+ assert isinstance(round_tripped, Tree)
+ assert round_tripped.has_child(None)
+ assert round_tripped.child_at(None).has_child("child")
+ assert round_tripped == tree
+
+
+# ---- Deserialization tests (duplicate-sibling-key dedup) ----
+
+import io
+
+from gremlin_python.structure.io.graphbinaryV4 import DataType, TreeIO, int32_pack
+
+
+def _fq_string(s):
+ """Fully-qualified GraphBinary string: {type-id}{null flag}{int32 len}{bytes}."""
+ b = bytearray([DataType.string.value, 0x00])
+ encoded = s.encode("utf-8")
+ b.extend(int32_pack(len(encoded)))
+ b.extend(encoded)
+ return b
+
+
+def test_deserializer_duplicate_sibling_key():
+ # length=2; key='dup' appears twice with distinct children -> one merged entry.
+ b = bytearray(int32_pack(2))
+ # entry 1: key='dup', child={ 'a' -> {} }
+ b.extend(_fq_string("dup"))
+ b.extend(int32_pack(1))
+ b.extend(_fq_string("a"))
+ b.extend(int32_pack(0))
+ # entry 2: key='dup', child={ 'b' -> {} }
+ b.extend(_fq_string("dup"))
+ b.extend(int32_pack(1))
+ b.extend(_fq_string("b"))
+ b.extend(int32_pack(0))
+
+ tree = TreeIO._read_tree(io.BytesIO(bytes(b)), reader)
+ assert tree.root_nodes() == ["dup"]
+ merged = tree.child_at("dup")
+ assert merged.has_child("a")
+ assert merged.has_child("b")