Key-bracket grammar: modification-timestamp marker foo[t1~] for added-at-or-after binding

[jtnelson]

Summary

I propose extending the key-bracket binding grammar so that a key can bind not to the value that existed at a timestamp, but to the values that were added relative to a timestamp. The headline construct is foo[t1~]: it binds foo to the values whose add occurred at or after t1. This is a new, addition-relative semantic that the current single-instant bracket form (foo[t]) cannot express. Note that the existing bracket form foo[t] is a strict single-instant read (the value as it existed at the instant t, per CCL_REFERENCE.md sections 8.1 and 8.4); CCL has no range or at-or-after form today, so the addition window is genuinely new ground.

This primitive exists to power a stale-lock / lease detection pattern. A separate cinchapi-server data-sync service runs as load-balanced Kubernetes pods that scale up and down, with no external coordinator. Connector configuration (sources, credentials, schedule, and a lock field) lives in a shared Concourse instance. Each instance loops: it atomically claims the first available connection (lock unset, or lock stale because the holder died), records the lock, runs the sync, then releases the lock. Because a pod can die mid-sync and never release its lock, a lock must be treated as expired when its value was added longer ago than a timeout window. The expiry decision happens at query time rather than by mutating stored state, so the language needs a way to ask "which records have a lock value that was added within the last N minutes." locked[<now-minus-timeout>~] expresses exactly the freshness half of that question: it binds locked to lock values added at or after the cutoff, so a record whose only lock value was added before the cutoff (a dead holder's stale lock) binds to nothing and is therefore claimable.

This ticket is the grammar / AST / parse side only in ccl. Evaluation of the binding against stored data is a separate concern in Concourse (see Scope and dependencies).

Proposed API / Syntax

I propose two bracket markers, both grammar-side:

foo[t1~] (addition-after, the novel form). It binds the key to the values whose add occurred in the half-open interval [t1, now): start-inclusive at t1, end-exclusive at the present moment. A value added exactly at t1 is included. A value added before t1, even if it is still present, is not included. This is what makes the form distinct from a point-in-time read: the existing foo[t] form binds the single value present at the instant t regardless of when it was added, whereas foo[t1~] binds the set of values on the basis of each value's add-event timestamp. The form is also distinct from any future addition-agnostic "still present at or after t1" range semantic (see the note on sibling work below): such a range would bind anything still present in the window regardless of add time, while foo[t1~] keys strictly off the add event, so a value added before t1 that survives past it is excluded.

foo[~t1] (addition-before, optional). It would bind the key to the values whose add occurred in [beginning-of-time, t1): end-exclusive at t1. I recommend not implementing this as an independent semantic. A value that was added before t1 is, by definition, a value that existed before t1, and the converse holds as well, so addition-before would compute the identical set to an existence-before range form. The recommendation is therefore to either omit ~t1 from the first cut entirely (and add it later only if a caller wants the addition-flavored spelling) or, if a sibling existence-before range construct lands, implement foo[~t1] as a parse-time alias that produces the same AST as that construct. The asymmetry is the whole point: t1~ earns its own node because it is genuinely new; ~t1 does not.

Precise semantics and edge cases:

• Interval convention. t1~ is [t1, now). This matches the half-open [start, end) convention used elsewhere for time windows. The start bound is inclusive; the implicit now end bound is exclusive.
• Null / empty binding. When no value satisfies the binding (no add event in the window), the key binds to nothing. The grammar/AST layer does not itself decide what the downstream result is; it only records the binding. The stale-lock use case selects the claimable record with foo[t1~] = null, where = null is Concourse's null value sentinel (cinchapi/concourse#791). That value-sentinel matching is the evaluator's contract (Concourse), not this ticket's; this ticket assumes it exists.
• Ordering. The binding is set-valued; it imposes no ordering on the matched values.
• Atomicity / contention. None at this layer. This is pure parsing. The atomic claim-the-lock behavior is built by the caller on top of Concourse's existing transaction primitives; the grammar only supplies the query shape.
• At most one bracket parameter per key. The existing invariant holds unchanged: a key carries at most one bracket-timestamp parameter, and a modification marker is that one parameter. foo[t1~][t2], foo[t1~]*[t2], and similar doubles are rejected at parse time, exactly as the instant form already rejects foo[t1][t2].
• Canonical serialization. A modification binding round-trips through a stable canonical string. I propose key[<micros>~] for the after form and key[~<micros>] for the before form (when not aliased away), with the timestamp rendered as raw microseconds and any at/on/during keyword canonicalized out, mirroring how the instant form serializes foo[at 123] as foo[123]. Re-parsing the canonical string MUST yield an equal AST. This is a cross-repo contract: Concourse's Keys.parse(String) (in concourse-driver-java, com.cinchapi.concourse.validate.Keys) re-parses key strings, so the emitted form has to be one Keys.parse accepts and classifies as parameterized.
• Command acceptance. A modification binding is a read-time parameter and is therefore rejected on the same commands that already reject the instant bracket: writes (add, set, remove, clear, link, unlink, reconcile, verify_and_swap, verify_or_set, find_or_add, revert) and the range-history reads (audit, chronicle, diff). For a first cut I recommend wiring acceptance through the same path the instant form uses so that point reads (select, get, find, browse, navigate, calculate, search, verify, order by) accept it. Whether every one of those reads has a meaningful evaluation of an addition window is a downstream question; the parse-side contract is simply that the marker is accepted where the instant bracket is accepted and rejected where it is rejected.

Examples

Connector lock / lease (the motivating case):

locked[<now-minus-timeout>~] = null

binds locked to lock values added within the timeout window; a record whose only lock value was added before the cutoff binds to nothing, so the predicate selects it as claimable. (The literal <now-minus-timeout> is whatever timestamp value the caller computes: a microsecond epoch, or a natural-language phrase like "5 minutes ago".)

Direct comparison of the new form against the existing instant form:

find locked[1700000000~] = "pod-A"   -- locked values ADDED at or after t, equal to pod-A
find locked[1700000000] = "pod-A"    -- locked value that EXISTED at the instant t, equal to pod-A

Illustrating the distinctness from a point-in-time read (the reason t1~ is its own node): a value added at t0 < t1 and never removed is the value foo[t1] would return (it existed at t1), but it is not matched by foo[t1~], because its add event predates t1.

The before form, if spelled at all, is equivalent to an existence-before range:

foo[~1700000000]   -- added before t; identical set to an existence-before range form

Implementation pointers

All line references are against the current tree; I have read each one.

Grammar file. The grammar is grammar/grammar.jjt (note: not src/main/grammar). Regenerate the parser with ./javacc-parser-generator.sh after editing; the generated sources land under com.cinchapi.ccl.generated.

Two bracket-content parsers must stay in lockstep. There are two independent places that interpret the characters between [ and ], and a modification marker has to be handled in both:

1. The parser-path production BracketedTimestamp() at grammar.jjt:771-780. Today it consumes an optional at/on/during keyword then a run of value tokens and returns a TimestampSymbol. This is reached from Key() (grammar.jjt:543-574), where the optional ( <OPEN_BRACKET> ts=BracketedTimestamp() <CLOSE_BRACKET> )? wraps a leaf into a TemporalKeySymbol or folds a timestamp onto a navigation stop via NavigationKeySymbol.withTimestampOnLastStop.
2. The lexer/navigation-path parser NavigationKeyStop.parseBracketContent at NavigationKeyStop.java:208-230. When a bracket sits inside a dotted path (e.g. a[t1~].foo), the whole token is captured by the lexer as a PERIOD_SEPARATED_STRING / NAVIGATION_SCOPE_OPEN via the opaque <#KEY_BRACKET> char class (grammar.jjt:310), and the bracket content is later split out and parsed here by hand.

The central hazard: ~ is already a token. SEARCH_MATCH : "search_match" | "contains" | "~" at grammar.jjt:281, and ~'s exclude counterpart is the !~ alternative of SEARCH_EXCLUDE : "search_exclude" | "not_contains" | "!~" at grammar.jjt:283. The two parsers behave asymmetrically with respect to ~, and this is the main source of subtle bugs:

• Parser path (flat leaf and scope prefix). Inside the bracket, a ~ is lexed as a SEARCH_MATCH token. The value-token list in BracketedTimestamp() (grammar.jjt:778) does not include SEARCH_MATCH, so foo[t1~] will not parse as written without explicit handling. The two viable approaches are (a) special-case the SEARCH_MATCH / SEARCH_EXCLUDE token inside the bracket production so a trailing or leading ~ is recognized as the modification marker rather than a search operator, or (b) introduce a dedicated bracket-only token for the marker. Approach (a) keeps the token set small but means the bracket production has to distinguish marker-position ~ from any other use; approach (b) is cleaner to reason about but adds a token. Either way the change is local to bracket context, so the global meaning of ~ as a search operator outside brackets is untouched.
• Lexer path (navigation stop). Here ~ never becomes a SEARCH_MATCH token at all: it is just an opaque character inside <#KEY_BRACKET> (which excludes only [, ], and line breaks), so a[t1~].foo already lexes. The work is entirely in NavigationKeyStop.parseBracketContent (NavigationKeyStop.java:208-230), which must detect a leading/trailing ~ in the trimmed content and produce the modification node instead of a plain TimestampSymbol.

Call this asymmetry out in any implementation: a test that passes on the navigation path can still fail on the flat-leaf path, and vice versa, because the ~ reaches the two parsers as different things.

AST. Add a sibling symbol modeled on TemporalKeySymbol (TemporalKeySymbol.java) and TimestampSymbol (TimestampSymbol.java), for example a ModificationKeySymbol that wraps a KeyTokenSymbol, carries a TimestampSymbol, and carries a direction (after for t1~, before for ~t1). A two-constant enum for the direction follows the existing DirectionSymbol precedent (DirectionSymbol.java, an enum implements Symbol with ASCENDING, DESCENDING). Mirror the structural constraints TemporalKeySymbol already enforces in its constructor (TemporalKeySymbol.java:61-74): reject wrapping a NavigationKeySymbol (navigation bindings live on the stop) and reject wrapping an already-parameterized key (the one-parameter invariant). Override isParameterized() to return true, baseKey() to delegate to the wrapped key, and stripParameters() to return the wrapped key, matching TemporalKeySymbol.java:108-121. Give it a canonical toString() of key[<micros>~] / key[~<micros>] that re-parses identically; TemporalKeySymbol.toString() at TemporalKeySymbol.java:103-106 is the template (it emits key[<micros>]).

For navigation, the binding rides on the stop, not on a wrapper. NavigationKeyStop (NavigationKeyStop.java) currently holds only a nullable TimestampSymbol; it needs to also carry the direction so segment() (NavigationKeyStop.java:364-375) can render key[<micros>~] and so parse / parseBracketContent can round-trip it. The canonical join in NavigationKeySymbol.joinStops / components() / baseKey() (NavigationKeySymbol.java:120-129, 199-225) then reflects the marker automatically because they delegate to the stop's segment() / baseSegment().

Parameter hooks. Key() (grammar.jjt:543-574) is where a flat leaf or a trailing navigation bracket is turned into the right symbol; extend the post-bracket action to construct the modification node when the marker is present. NavigationKeySymbol.parseScopePrefix (NavigationKeySymbol.java:47-75) builds the scope-prefix symbol from a stop and must produce the modification node for a single bracketed stop, the same way it currently produces a TemporalKeySymbol.

Visitor: no change. The binding lives entirely inside the key symbol, so the grammar visitor does not need a new visit method.

Builder API: none. The binding rides in the key string, e.g. .key("foo[t1~]"); there is no new fluent method to add.

Command acceptance. Acceptance and rejection flow through KeyTokenSymbol.requireNotParameterized (KeyTokenSymbol.java:34-57), which throws when isParameterized() is true. Because the new node returns isParameterized() == true, the existing rejection sites for writes and range-history reads (the KeyTokenSymbol.requireNotParameterized(key, "...") calls scattered through the command productions) reject it for free. The thrown IllegalArgumentException surfaces to callers as a SyntaxException because CompilerJavaCC wraps any parse-time exception in a PropagatedSyntaxException (a SyntaxException subclass that carries the cause message), so the observable behavior is a SyntaxException whose message names the offending command, consistent with CCL_REFERENCE.md section 8.2. No new rejection wiring is needed; the work is confirming, by test, that they do.

Performance

Parsing cost is unchanged in order of growth. Recognizing the marker is a constant-time check on the trimmed bracket content (NavigationKeyStop.parseBracketContent) or one extra token alternative in the bracket production; both are O(1) per bracket, and a key has at most one bracket. There is no new allocation in the hot path beyond the single AST node that the instant form already allocates. The round-trip path (Compiler.tokenize then Symbol::toString) gains no extra passes.

This ticket adds no evaluation, so it introduces no scan behavior of its own. I should record the downstream expectation for whoever implements evaluation in Concourse: an addition-window binding is answerable from the per-key write history (the add events and their timestamps), so it should resolve via the same historical index machinery the instant bracket already uses rather than by materializing present state and post-filtering. The stale-lock query is meant to run on every claim attempt across many pods, so the evaluation must be index-driven and must not degrade to a full record scan or to O(values squared) comparison of add events; that constraint belongs to the Concourse evaluation ticket but is stated here so it is not lost.

Testing

This repo writes tests but does not run them (the suite needs a live server). Reproduction and behavior tests still belong in the ticket and should be authored alongside the change, tests first.

Follow the existing patterns:

• grammar/TemporalKeySymbolTest.java is the model for unit-testing the new symbol directly: constructor rejection of null key and null timestamp, rejection of wrapping a NavigationKeySymbol and of wrapping an already-parameterized key, accessor identity, equals / hashCode across matching and differing key / timestamp / direction, inequality against a plain KeySymbol, and toString() producing the canonical key[<micros>~]. Add direction to every relevant case (two bindings that differ only in direction must not be equal).
• BracketTimestampMatrixTest.java (the Bracket-timestamp syntax for key annotations #58 matrix) is the model for parse-shape and round-trip coverage. Add rows for: flat leaf after-marker (foo[t1~] = "X"), flat leaf before-marker if implemented, navigation stop markers on the first stop, the leaf stop, and a mid-chain stop (a[t1~].foo, a.foo[t1~], a[t1~].b.foo), a marker coexisting with the transitive marker in canonical order (a[t1~]*.foo), scope-prefix marker (A[t1~].(foo = "X")), keyword-equivalence inside the marker if the keyword is permitted (foo[at t1~] equals foo[t1~]), rejection of doubles (foo[t1~][t2], children[t1~]*[t2]), and rejection of the non-canonical asterisk-then-bracket order. Critically, include both the flat-leaf path and the navigation path for the after-marker, because of the parser-vs-lexer ~ asymmetry described above: a single shared helper is not enough, the two paths must each be asserted. Reuse the file's assertRoundTrip helper (it does Compiler.tokenize(parse(ccl)) joined by Symbol::toString, re-parses, and asserts AST equality) for every new shape so the canonical serialization contract is enforced.
• BracketTimestampCommandTest.java is the model for command acceptance and rejection. Add accepted-on-reads cases (select, get, find, browse, navigate, calculate, search, verify, order by) and rejected-on-writes / rejected-on-range-history cases (the same command set that testAddRejectsBracketKey and the audit/chronicle/diff cases already cover), asserting the SyntaxException message names the offending command, exactly as assertCommandRejected does today.
• Use the project's randomized timestamp generators where a concrete value is not load-bearing, and use a fixed value with an issue link where a specific instant matters, per the repo convention. Every @Test needs the four-section Goal / Start state / Workflow / Expected Javadoc.
• Update CCL_REFERENCE.md section 8 (the bracket-annotation reference) to document the modification marker: add a subsection under 8.4 describing t1~ semantics, the half-open [t1, now) window, the distinctness from the single-instant foo[t] form, and the recommendation that ~t1 aliases into (or defers to) an existence-before range form should one exist.

Scope and dependencies

In scope (first cut): the foo[t1~] after-marker on flat leaf keys, navigation stops, and scope prefixes; the AST node and its canonical round-tripping toString(); acceptance on point reads and rejection on writes and range-history reads via the existing parameterized-key gate; grammar regeneration; the test additions above; the reference-doc update.

Optional in this cut: the ~t1 before-marker. The recommendation is to omit it, or to alias it to an existence-before range form if one exists, since it is semantically redundant; do not build an independent before-evaluation node.

Out of scope: evaluation of the binding against stored data, any builder API, any visitor change, and any change to the meaning of ~ outside of bracket context.

Cross-repo dependencies. This is the parse-side half of a two-repo change. The evaluation half lives in Concourse, where the addition-window binding is resolved against per-key write history; that work also owns the observable null-or-empty result contract the stale-lock query depends on, and it consumes the canonical key string through Keys.parse in concourse-driver-java (com.cinchapi.concourse.validate.Keys). Because of that consumption, the canonical toString() chosen here is a contract Concourse re-parses, so it must be settled in this ticket and not changed later. Version coupling: ship this in a ccl release first (the working base version in .version is 4.1.0, ahead of the 4.0.0 Concourse currently pins), then Concourse bumps its pinned ccl dependency in concourse-driver-java/build.gradle (currently version: '4.0.0' on line 21) before the Concourse evaluation work lands.

A note on sibling work: the body above refers to a hypothetical existence-before range construct (a foo[...t]-style range form) as the natural home for ~t1 to alias into. No such range construct exists in the current grammar or reference today; it is proposed sibling work, a separate ticket, and is not assumed to be merged. The foo[t1~] after-marker in this ticket stands on its own and does not depend on that work landing.

Related

Part of the connector data-sync locking initiative (cinchapi-server).

• Server-side evaluation of this grammar: cinchapi/concourse#790.
• Sibling grammar work: Temporal range key-bracket binding: foo[t1...t2], foo[...t2], foo[t1...] (grammar/AST/parse only) #74 (temporal-range binding).