Sack and Operators

TinkerPop's Operator is a binary function over two values. One token drives four features: the sack (a value that travels with a traverser: withSack(init, Operator), sack(Operator)), and two reducers (fold(seed, Operator) and withSideEffect(key, init, Operator)). This page is the complete reference: the operators first, then the sack, the merge operator, withBulk(false), the reducers, and finally every deviation from TinkerPop in one list.

Operators

Eleven tokens, written Operator.sum or Operator::sum in the Rhai DSL (there are no bare constants: sum() and max() are steps). In Rust the token is graphersal::prelude::Operator and Operator::apply(&left, &right) applies it to two property values.

Every failure is a ValueError::OperatorFailed with a kind (Overflow, DivisionByZero, IncompatibleOperands); its help() names the casts as_number(), as_bool() and as_string().

Examples (each runs in graphersal; inject with withSack shows an operator on its own):

g.withSack(2).inject(5).sack(Operator.mult).sack()       // 10
g.withSack(2).inject(5).sack(Operator.minus).sack()      // -3
g.withSack(7).inject(2).sack(Operator.div).sack()        // 3     (int / int truncates)
g.withSack(7.0).inject(2).sack(Operator.div).sack()      // 3.5
g.withSack(3).inject(9).sack(Operator.max).sack()        // 9
g.withSack("b").inject("a").sack(Operator.min).sack()    // a
g.withSack(true).inject(false).sack(Operator.and).sack() // false
g.withSack([1,2]).inject(3).sack(Operator.addAll).sack() // [1, 2, 3]
g.withSack(#{a: 1}).inject(#{b: 2}).sack(Operator.addAll).sack()   // {a: 1, b: 2}
g.withSack(1).inject(2).sack(Operator.assign).sack()     // 2
g.withSack(9223372036854775807).inject(1).sack(Operator.sum).sack()
// error: Operator 'sum' overflowed the int64 range combining 9223372036854775807 (int64) with 1 (int64)

Null rule: for sum, minus, mult and div a null operand makes the result the left operand (sum(null, 1) is null, sum(1, null) is 1); min/max and and/or return the other operand (two nulls give null); assign returns the right operand even when it is null. This is TinkerPop's NumberHelper rule, kept on purpose.

Sack

A sack is a value that travels with a traverser, separate from the value the traverser currently holds.

g.withSack(5).V().sack()                 // 5, six times
g.withSack(0.0).inject(1).sack()         // 0.0
g.V().sack()                             // null, six times: no withSack, no sack
g.withSack(7).V().values("age").sack()   // 7 each: the value changes, the sack stays

• withSack(initial) (with_sack in Rust and as a snake_case alias in Rhai) is an option of the traversal source, like withSideEffect. The initial value may be a number, string, boolean, UUID, list or map. As in Gremlin, both exist only on g: written inside a child traversal (local(__.withSack(1).sack())) they fail before execution with SourceStepInChild, whose help shows the fix (g.withSack(1).V().local(__.sack())).
• sack() replaces the traverser's value with its sack. Without withSack the sack is null.
• Who gets the initial sack. A traverser generated by a start step (V(), E(), inject(), a first addV()) or by a reducing barrier (count(), sum(), fold(), group(), cap(), ...) starts with the initial sack, so g.withSack(9).V().count().sack() is 9. A traverser derived from another one (every out(), has(), values(), unfold() and so on) keeps the sack of its parent, and a child traversal sees the sack of the traverser it runs for (where(__.sack().is(P.eq(5))), order().by(__.sack()), local(__.sack())). A by() that projects an object taken from the traverser (path().by(..), select("a").by(..), tree().by(..), math(..).by(..) over a named variable, where(P).by(..)) starts a fresh traverser for that object, which has the initial sack: this is what TinkerPop does (TraversalUtil.produce(object, traversal)).
• Sacks are immutable values. Nothing changes a sack in place; an update (sack(Operator)) gives that one traverser a new value. A traverser stores only a four byte handle into a per-execution table, so carrying a sack costs nothing for queries that do not use one (the traverser stays 80 bytes) and equal scalar sacks share one stored copy (about 48 bytes per distinct scalar, 32 bytes per container). 1 and 1.0 are different values; 0.0 and -0.0 too.
• Merging. Traversers merge at a barrier(), in a repeat() frontier and at the optimizer's lazy_barrier() only when their sacks are equal (same stored value). Different sacks never merge. A list or map sack is stored once per update and therefore only merges with copies of the very same stored value. The results never depend on merging (see Bulk and barriers).

Updating a sack

sack(Operator) replaces the traverser's sack with operator(sack, operand). The operand is what a following by() resolves for the traverser, or the traverser's own value without a by().

g.withSack(0).V().outE().sack(Operator.sum).by("weight").inV().sack()   // running total of edge weights
g.withSack("hello").V().outE().sack(Operator.assign).by(T.label).inV().sack()
g.withSack(2).V().sack(Operator.div).by(__.constant(4.0)).sack()        // 0.5, six times
g.withSack(1).inject(2).sack(Operator.sum).sack()                       // 3: no by(), the value is the operand

• by() rules. A property key, T.id/T.label, or a traversal; a traversal contributes its first result (write by(__.values("x").sum()) to combine several) and runs with the traverser's sack. A by() that resolves nothing (a missing property, an empty traversal) is unproductive: the traverser is dropped, so g.V().sack(Operator.assign).by("age").sack() has four results, not six. A second by() is an InvalidModulator error ("Sack step can only have one by modulator").
• The path and bulk are untouched. The step does not add a path position (sack() does), and a traverser that stands for several equal ones is updated once, all copies share the new sack. A child traversal's own sack(Operator) never flows back to the parent: where(__.sack(Operator.sum).by(__.constant(5))) leaves the outer sack alone, local(__.sack(Operator.sum)...) carries the update out because local hands the child's traverser on.
• Which sack a child sees. A child that receives the traverser itself (project().by(__.sack()), order().by(__.sack())) sees its updated sack. A by() that projects an object taken from the traverser (path().by(__.sack()), select("a").by(..)) starts a fresh traverser, which has the initial sack, so g.withSack(1).V().sack(Operator.sum).by(__.constant(1)).path().by(__.sack()) yields 1, not 2. TinkerPop does the same.
• Null sack. The NumberHelper rule applies: sum of a null sack is null (a null left operand wins), assign works on it.
• Only an Operator. sack(BiFunction) lambdas are not supported; g.V().sack(5) fails with a message that names sack(Operator.sum).

normSack

barrier(Barrier.normSack) (or Barrier::normSack) merges the stream like barrier() and then scales every numeric sack so that the sacks add up to one: total = 0.0 + sum(sack * bulk), sack = sack / total (sack * bulk / total next to a merge operator), always a float64. g.withSack(1.0).V().out().barrier(Barrier.normSack).sack() gives six times 1/6. A null sack is skipped and stays null; a sack that is neither a number nor null fails with OperatorFailed. A zero total divides by zero in IEEE arithmetic (no error). The consumer runs even with bulk.merge=false and on a stream of one traverser (it gives 1.0).

Merge operator

g.withSack(initial, Operator.sum) (Rust with_sack_merge(initial, Operator::Sum)) sets the merge operator. It is not a split operator: in TinkerPop the two-argument form takes a BinaryOperator that combines the sacks of traversers that merge, and a split needs a UnaryOperator lambda, which is not supported (a non-Operator second argument fails with a message that says so, and so does the three-argument form).

With a merge operator, merging becomes part of the result. Traversers that are equal (same object, same path) merge whatever their sacks are; the merged sack is operator(first, next) in encounter order, and the bulks add up:

g.withSack(1, Operator.sum).V().out().barrier().sack()               // 3, 3, 3, 1, 1, 1: lop merges three traversers
g.withSack(1, Operator.assign).V().out().barrier().sack()            // the last sack wins

A merge that fails (sum over string sacks) is an error of the barrier step. Plans that record full paths (path(), simplePath(), a read as() label) and plans that mutate never merge, so the operator never combines there; containers (arrays, maps) never merge either.

barrier(Barrier.normSack) next to a merge operator uses TinkerPop's numerator: total = sum(sack * bulk) and sack = sack * bulk / total (see normSack). Without a merge operator the numerator is sack.

withBulk(false)

g.withBulk(false) (Rust with_bulk(false), also with_bulk) sets the option bulk.one (TinkerPop's ONE_BULK requirement). It does not switch merging off: an explicit barrier() still collapses equal traversers, but the merged traverser keeps bulk 1, so the duplicate is emitted once:

g.V().out().barrier().count()                       // 6
g.withBulk(false).V().out().barrier().count()       // 4: lop, vadas, josh, ripple
g.withBulk(false).withSack(1, Operator.sum).V().out().barrier().sack()   // 3, 1, 1, 1

Under bulk.one a traverser that carries a sack and has no merge operator never merges (TinkerPop carriesUnmergeableSack), so g.withBulk(false).withSack(0).V().out().barrier() has six results. withBulk(true) clears the option. This is the one place where merging is visible on purpose.

Automatic merging and sacks

With a merge operator or bulk.one the automatic merge points are switched off for the whole execution, so the result does not depend on where the optimizer happens to put a lazy_barrier(). The lazy_barrier rule still inserts its steps (the profile shows the row with Out == In). A loop body that wants merging writes it:

g.withSack(1, Operator.sum).V().repeat(__.out().barrier()).times(3).sack()

Without the barrier() the loop does not merge and a dense graph runs into the path explosion; the help of the timeout and loop-limit errors says so.

bulk.merge=false keeps its diagnostic meaning (no merging anywhere, including the explicit barrier). For a plan with a merge operator that changes the result: g.with("bulk.merge", false).withSack(1, Operator.sum).V().out().barrier().sack() gives six times 1.

Reducer operators

fold(seed, Operator)

fold(seed, Operator) keeps one accumulator, starting at seed, and applies acc = operator(acc, value) to every value of the stream in order. It emits one traverser holding the accumulator (with the initial sack, like every reducing barrier). An empty stream gives the seed. A traverser that stands for n equal ones (after a merge) applies the operator n times, within bulk.max_expansion: there is no acc + value * n shortcut, so minus and div stay exact and the result never depends on merging.

g.V().values("age").fold(0, Operator.sum)                  // 123
g.V().hasLabel("none").values("age").fold(0, Operator.sum) // 0, the seed
g.V().values("age").fold(100, Operator.minus)              // -23, in stream order
g.V().values("age").fold([], Operator.addAll)              // [29, 27, 32, 35]
g.inject(#{a: 1}, #{b: 2}, #{b: 4}).fold(#{}, Operator.addAll)   // {a: 1, b: 4}
g.V().constant(false).fold(true, Operator.and)             // false
g.withSack(3).V().values("age").fold(0, Operator.sum).sack()     // 3

The seed decides the kind (0 for sum, 1 for mult, true for and, [] or #{} for addAll). A seed the operator cannot combine with (fold("", Operator.sum) over names) is an OperatorFailed error. Rust: fold_with(seed, Operator::Sum) on the source, AnonymousTraversal and __. The profile row is fold(0, Operator.sum). A second argument that is not an Operator (a BiFunction lambda) is an error that names fold(0, Operator.sum).

withSideEffect(key, initial, Operator)

A side effect declared with an operator is a reduced value: aggregate(key) and store(key) combine what they collect into it with the operator instead of appending to a list, and cap(key), select(key) and where(P.lt(key)) read the accumulated value.

g.withSideEffect("a", 1, Operator.sum).V().aggregate("a").by("age").cap("a")      // 124
g.withSideEffect("a", 100, Operator.min).V().aggregate("a").by("age").cap("a")    // 27
g.withSideEffect("a", [1,2,3], Operator.addAll).V().aggregate("a").by("age").cap("a")
                                                       // [1, 2, 3, 29, 27, 32, 35]
g.withSideEffect("a", 0, Operator.assign).V().aggregate("a").by("age").cap("a")   // [29, 27, 32, 35]
g.withSideEffect("a", 7, Operator.sum).V().hasLabel("none").aggregate("a").cap("a")   // 7: nothing collected

The rule. One execution of aggregate() (the whole stream of the step, or a single traverser inside a local() child) collects the values v1..vk in stream order (bulk expanded, by() applied, unproductive ones skipped). Then:

• assign and addAll receive the values as one list: operator(value, [v1..vk]). assign keeps the list ([29, 27, 32, 35]; inside local() there is one execution per vertex, so the last one wins: [35]), addAll concatenates it;
• every other operator folds the values one by one: operator(operator(value, v1), v2). This is what the expectations for sum, minus, mult, div, min, max, and and or need (124, 0, 1753920, 1, 27, 35).

store(key) is lazy and applies the rule after every element (one value per execution), so assign leaves a one-element list. An execution that collects nothing leaves the value unchanged. Bulk is invisible: a traverser of bulk n contributes n values. An array seed together with an operator is a reduced value, not a list. A reduced value is neither a list nor a set bucket: within("a") over it tests the items when it holds a list and the value when it holds a scalar. Rust: with_side_effect_reduced(name, initial, Operator).

Where the rule comes from. TinkerPop 3.7.2 (AggregateGlobalStep, DefaultTraversalSideEffects.add, Operator$1, read with javap -c on gremlin-core-3.7.2.jar) hands the reducer one BulkSet per step execution, so sum(1, BulkSet) is a ClassCastException there and cannot give 124. The suite pins 3.8.2 and its source is not available offline, so the 24 sideEffect/Aggregate.feature scenarios with an Operator decide the rule (all 24 pass): the global and the local form of sum, minus, mult, div, min and max (seeds 1 and 100), and, or, addAll and assign. Global assign returns the four rows 29, 27, 32, 35, so the reducer must see the whole collection and not one element per call; every numeric and boolean operator needs the element-by-element result (minus: 123 - 29 - 27 - 32 - 35 = 0, div: 876960 / 29 / 27 / 32 / 35 = 1). The local scenarios cannot tell a scalar 35 from a one-element list [35] (iterated next spreads a collection into rows), so the special case "a single value is applied as a scalar", which an earlier design considered, is not used: one uniform rule keeps the type of the result independent of how many traversers reach the step.

Deviations from TinkerPop

Every deliberate difference in one list (the same rows are in the developer table tinkerpop_deviations.md).

Operators

• Integer overflow is an error. TinkerPop widens int to long and long to BigInteger; Graphersal has int64 and float64 only, so sum, minus, mult and div (i64::MIN / -1) fail with OperatorFailed instead of promoting. Floats follow IEEE (1.79e308 + 1.79e308 is Infinity). The integer widths of the feature files collapse to int64.
• sumLong does not wrap around (TinkerPop 3.7.2 does); it fails on overflow and on a non-int64 operand.
• div of two integers truncates toward zero like Java; a zero integer divisor is an error, a float divisor gives inf/NaN.
• addAll with a scalar appends it (3.8.2 feature files; 3.7.2 throws for a non-collection).
• Only the Operator and Barrier tokens. No lambdas: sack(BiFunction), fold(seed, BiFunction), withSideEffect(key, init, BinaryOperator), barrier(Consumer), and no Supplier initial value (withSack { [:] }). There is no split operator (withSack(init, UnaryOperator)); a container sack is shared by handle, which is safe because sack values are never modified in place.
• The null rule is TinkerPop's (see Operators), not an error.

Sack

• A vertex or edge is not a valid sack value or operand (withSack(vertex), sack(assign) of an element, an element in normSack): a cast or OperatorFailed error whose help names by(T.id). TinkerPop accepts any object.
• BigInteger/BigDecimal sacks (withSack(BigInteger ...)) are not supported; that scenario stays a translator gap.
• A traversal in sack(op).by(..) contributes its first result; write by(__.values("x").sum()) to combine.
• Equal sacks merge at automatic merge points when there is no merge operator (TinkerPop never merges sacked traversers); the result multiset is identical after bulk expansion.
• normSack numerator. Without a merge operator the sack is divided by total = sum(sack * bulk) (not sack * bulk / total), so merging never changes the answer; next to withSack(initial, Operator) the formula is TinkerPop's.
• Memory. About 48 bytes per distinct scalar sack and 32 bytes per container update; SackArenaExhausted at about 4 billion values (compaction at barriers is a follow-up).

Merging

• Only an explicit barrier() merges next to a merge operator or withBulk(false). TinkerPop's LazyBarrierStrategy also inserts barriers when a sack exists, so its merged sacks depend on where it puts them. Here the repeat frontier and lazy_barrier() pass through; write repeat(__.out().barrier()).
• bulk.merge=false also disables the explicit barrier, so it changes the result of a merge-operator plan.
• withBulk(false) is the option bulk.one: merging collapses duplicates and keeps bulk 1 (TinkerPop's ONE_BULK); it is not "no merging".
• Containers and Full-path traversers never merge, so a merge operator cannot combine them (path equality is by handle; content-based path equality is a follow-up).

Reducers

• The aggregate/store reducer rule (one list for assign and addAll, an element-by-element fold for every other operator, the same for any batch size) is inferred from the 3.8.2 feature files because 3.7.2 cannot run sum there (see Reducer operators).
• fold(seed, Operator) applies the operator n times for bulk n (no shortcut), within bulk.max_expansion.

Math

• sin in the last scenario of map/Math.feature differs from Java in the last digit (Rust libm), see the deviations table.

Sources: the semantics were read from the Operator, NumberHelper, SackFunctions, SackValueStep, TraverserSet, AggregateGlobalStep and DefaultTraversalSideEffects classes of gremlin-core-3.7.2.jar (javap -c) and checked against the vendored 3.8.2 feature files, which win on any conflict.