[GRAPH-001] Follows: Link Introspection & Outgoing Link Enumeration

[jtnelson]

Phase: 1 (Foundation)

Summary

Add follows() as the outgoing-link complement to the existing trace() operation. Today, trace(record) answers "who links TO this record?" but there is no symmetric operation to answer "what does this record link TO?" without selecting all keys and manually filtering for Link-typed values. follows() closes this gap and establishes the foundation for all subsequent graph features.

Additionally, add link-type introspection capabilities so users can discover what "relationship types" (keys containing Link values) exist in the data, and enable cross-key link traversal (follow ALL outgoing links regardless of key name).

Motivation

• Symmetry: trace() provides incoming links; follows() provides outgoing links. Every graph database offers both directions.
• Foundation: Path-finding, subgraph extraction, and graph aggregations all need efficient outgoing-link enumeration as a primitive.
• Discoverability: Users currently cannot ask "what relationship types does record X participate in?" without selecting all data and inspecting types manually.
• Cross-key traversal: Navigation today requires specifying exact key names (navigate("friends.name", record)). There is no way to say "follow all links from this record regardless of key."

New API Methods

follows(long record) -> Map<String, Set<Long>>

Returns all outgoing links from record, grouped by key.

// Example: record 1 has:
//   friends -> [@2, @3]
//   employer -> [@100]
//   name -> "Alice"  (not a link, excluded)
follows(1)
// => {"friends": {2, 3}, "employer": {100}}

Symmetric to trace():

• trace(record) = incoming links (who links to me, by key)
• follows(record) = outgoing links (who I link to, by key)

Full Method Family

// Single record
Map<String, Set<Long>> follows(long record);
Map<String, Set<Long>> follows(long record, Timestamp timestamp);

// Multiple records
Map<Long, Map<String, Set<Long>>> follows(Collection<Long> records);
Map<Long, Map<String, Set<Long>>> follows(Collection<Long> records, Timestamp timestamp);

// Criteria-based
Map<Long, Map<String, Set<Long>>> follows(Criteria criteria);
Map<Long, Map<String, Set<Long>>> follows(Criteria criteria, Timestamp timestamp);
Map<Long, Map<String, Set<Long>>> follows(String ccl);
Map<Long, Map<String, Set<Long>>> follows(String ccl, Timestamp timestamp);

Implementation Strategy

Server-Side (Operations.java)

public static Map<String, Set<Long>> followsRecordAtomic(
        long record, long timestamp, AtomicOperation atomic) {
    Map<String, Set<TObject>> data = timestamp == Time.NONE
            ? atomic.select(record)
            : atomic.select(record, timestamp);
    Map<String, Set<Long>> outgoing = Maps.newLinkedHashMap();
    data.forEach((key, values) -> {
        Set<Long> destinations = values.stream()
                .filter(v -> v.getType() == Type.LINK)
                .map(Convert::thriftToJava)
                .map(Link.class::cast)
                .map(Link::longValue)
                .collect(Collectors.toCollection(LinkedHashSet::new));
        if(!destinations.isEmpty()) {
            outgoing.put(key, destinations);
        }
    });
    return outgoing;
}

Efficient because it only reads one record's data (unlike trace which currently scans ALL records).

CCL Grammar Changes (ccl project)

• New Token: FOLLOWS keyword in grammar.jjt
• New Production: FollowsCommand() -- follows <record> [at <timestamp>] and follows where <criteria>
• New Symbol: FollowsSymbol.java in ccl/src/.../grammar/command/
• Update: Command() router production

Thrift API Changes

• 12 new method signatures in concourse.thrift (followsRecord, followsRecordTime, followsRecordTimestr, followsRecords, followsRecordsTime, followsRecordsTimestr, followsCcl, followsCclTime, followsCclTimestr, followsCriteria, followsCriteriaTime, followsCriteriaTimestr)
• New FOLLOWS = 22 in TCommandVerb enum (data.thrift)

Touch Surfaces

Layer	File(s)	Change
Thrift IDL	interface/concourse.thrift	Add 12 follows* method signatures
Thrift IDL	interface/data.thrift	Add FOLLOWS to TCommandVerb
Thrift codegen	Run utils/compile-thrift-*	Regenerate Java, Python, PHP, Ruby stubs
Server	ConcourseServer.java	Implement 12 follows* handler methods
Server ops	Operations.java	Add followsRecordAtomic, followsRecordsAtomic
Server dispatch	TCommandDispatcher.java	Add FOLLOWS verb mapping
Driver	Concourse.java	Add abstract follows methods (12 overloads)
Driver impl	ConcourseThriftDriver.java	Implement follows methods via Thrift client
CCL grammar	ccl/grammar/grammar.jjt	Add FOLLOWS token, FollowsCommand() production
CCL symbols	ccl/src/.../command/	Add FollowsSymbol.java
CCL compiler	ccl/src/.../CompilerJavaCC.java	Handle FollowsSymbol in visitor
CaSH shell	ShellEngine.java	Add follows command dispatch
CaSH shell	ApiMethodCatalog.java	Register follows methods
CaSH shell	CompletionService.java	Add follows to completions
Plugin API	StatefulConcourseService.java, ConcourseRuntime.java	Add follows* methods
All drivers	Python, PHP, Ruby	Add follows methods
Integration tests	concourse-integration-tests/	Add FollowsTest.java
Documentation	docs/guide/src/graph.md, docs/shell/follows.md	Document follows
Changelog	CHANGELOG.md	Entry under 1.0.0 (TBD)

Testing Plan

Integration Tests (FollowsTest.java)

• testFollowsReturnsSingleOutgoingLink
• testFollowsReturnsMultipleLinksOnSameKey
• testFollowsReturnsLinksAcrossMultipleKeys
• testFollowsExcludesNonLinkValues
• testFollowsReturnsEmptyMapForRecordWithNoLinks
• testFollowsAtTimestampReflectsHistoricalState
• testFollowsMultipleRecords
• testFollowsWithCriteria
• testFollowsWithCcl
• testFollowsIsSymmetricWithTrace
• testFollowsWithinTransaction

Dependencies

• Blocks: GRAPH-003 (Path-Finding), GRAPH-004 (Subgraph Extraction), GRAPH-005 (Graph Aggregations)
• Related: GRAPH-002 (Graph Indexing) -- follows() works without a graph index but would be accelerated by one

Acceptance Criteria

• follows(record) returns all outgoing links grouped by key
• follows is the exact symmetric complement of trace
• All timestamp variants work correctly
• CCL command follows 1 works in CaSH
• CCL command follows where name = "Alice" works in CaSH
• Tab completion works for follows in CaSH
• All integration tests pass
• All drivers (Java, Python, PHP, Ruby) expose the method
• Changelog updated
• User guide updated

Complexity: Medium

Full spec: docs/specs/graph/GRAPH-001-follows.md