17#ifndef A11_FLOW_GRAPH_H_
18#define A11_FLOW_GRAPH_H_
27#include <absl/base/nullability.h>
28#include <absl/container/flat_hash_map.h>
29#include <absl/container/flat_hash_set.h>
30#include <absl/time/time.h>
31#include <absl/types/span.h>
45inline constexpr size_t kNone =
static_cast<size_t>(-1);
101 std::optional<syntax::TypeExpression>
type;
262 std::vector<std::pair<std::string, ExprId>>
headers;
266 absl::flat_hash_map<std::string, RefId>
ports;
343 std::vector<std::pair<BodyId, RefId>>
inputs;
350 return step.transfer !=
nullptr && !
step.transfer->sources.empty()
351 ? absl::MakeConstSpan(
step.transfer->sources)
352 : absl::MakeConstSpan(
357 return step.transfer !=
nullptr && !
step.transfer->destinations.empty()
358 ? absl::MakeConstSpan(
step.transfer->destinations)
359 : absl::MakeConstSpan(&
step.destination,
step.destination ==
kNone
377 std::vector<std::pair<const syntax::Node* absl_nonnull, RefId>>
bound;
441 absl::flat_hash_map<StepId, std::vector<RefId>>
held;
466 flow_->
bodies.push_back(std::move(body));
467 return flow_->
bodies.size() - 1;
482 return stage.
name ==
"first" && stage.
count == 1;
488 static const auto*
const kPerValue =
new absl::flat_hash_set<std::string>{
489 "map",
"at",
"truncate",
"text",
"json",
"packb",
"strformat",
"where",
490 "mime",
"distinct",
"first",
"last",
"drop",
"log",
"logf",
"scan",
493 "sort",
"timeout",
"pace",
"coerce",
"destructure"};
494 return kPerValue->contains(stage.
name);
525 ref.unary = !
ref.sources.empty();
526 for (
const RefId source :
ref.sources) {
545 flow_->
refs.push_back(std::move(
ref));
546 return flow_->
refs.size() - 1;
556 flow_->
bodies[body].steps.push_back(
id);
564 return flow_->
exprs.size() - 1;
Appends to a [FlowGraph] while the resolver walks a flow.
Definition graph.h:454
bool Carries(RefId ref) const
Whether the ref already in the graph carries at most one value.
Definition graph.h:471
StepId AddStep(Step step)
Append a step, and record it in the body it belongs to.
Definition graph.h:550
GraphBuilder(FlowGraph &flow)
Definition graph.h:456
static bool StagePreservesCount(const Stage &stage)
Whether a stage produces at most one output per input value.
Definition graph.h:487
ExprId AddExpr(Expr expr)
Definition graph.h:562
static bool StageMakesOne(const Stage &stage)
Whether a stage reduces its input to one value, including first 1.
Definition graph.h:476
Step & step(StepId id)
Definition graph.h:569
Ref & ref(RefId id)
Definition graph.h:567
Expr & expr(ExprId id)
Definition graph.h:571
RefId AddRef(Ref ref)
Appends a ref and derives cardinality from its kind and sources.
Definition graph.h:499
BodyId AddBody(std::string label, BodyId parent=kNone, StepId owner_step=kNone)
Definition graph.h:460
FlowGraph & flow()
Definition graph.h:458
constexpr size_t kNone
Sentinel for an absent graph ID.
Definition graph.h:45
absl::Span< const RefId > TransferTargets(const Step &step)
Definition graph.h:356
size_t BodyId
Definition graph.h:41
std::string_view StepKindName(StepKind kind)
Definition graph.cc:38
size_t RefId
Graph IDs are indices into the owning graph's vectors.
Definition graph.h:39
Analysis Analyse(const FlowGraph &flow, BodyId body)
Work out who reads and writes what in one body.
Definition graph.cc:398
absl::Span< const RefId > TransferSources(const Step &step)
Definition graph.h:349
size_t StepId
Definition graph.h:40
bool RecordsOutcome(StepKind kind)
Whether a step records its own outcome for a bound name.
Definition graph.h:216
RefKind
What a stream in the plan is.
Definition graph.h:48
@ kNodeId
A node's id, as one value – what a flow hands to an action that expects to be told where to write.
@ kMerge
Several streams read at once, as one stream of their values in the order they arrive: interleave(a,...
@ kBound
A stream the runtime binds per pass: a loop's value, its index, or a repeat's carry.
@ kZip
Several streams read in step, as one stream of tuples: zip(a, b).
@ kStatus
The outcome of a call, a node, a port or a barrier, as a status record.
@ kCallId
The ID assigned to a run or call, as one value.
@ kCallPort
A port of an action this flow calls: x.out.
@ kWinner
Zero-based index of the first subject to finish a wait first of.
@ kFlowPort
A declared port of this flow.
@ kHeader
One header of the call running this flow, as a single value.
@ kDerived
One stage applied to another stream.
@ kNode
A node of the flow's own: a stream it can write and read back.
@ kSink
A virtual continuation destination and its attached writer group.
@ kExpr
A stream of one value: an expression evaluated once.
size_t ExprId
Definition graph.h:42
StepKind
What a statement became.
Definition graph.h:192
@ kAbort
abort node ..: end a node with a failure rather than with an end.
@ kBlock
[try] { ... }: a body run as one step, whose outcome is its own.
@ kCapture
Remember a stream's first value for the loop that owns this body: what <- and an until condition comp...
PortDirection
Which side of the descriptor a port lands on, spelled as the plan spells it.
Definition syntax.h:624
const absl::flat_hash_set< std::string_view > & ReducingStages()
Stages that reduce a whole stream to one value.
StageArgument
What a stage takes after its name.
Definition vocabulary.h:43
@ kNone
Nothing: | collect, | count.
std::string label
Definition resolve.cc:800
graph::StepId step
The graph step it is, so <- and until can fill it in.
Definition resolve.cc:6485
const Scope * parent
Definition resolve.cc:829
std::string ref
Definition sqlite_chunk_store.cc:193
Reader and writer counts for the references owned by a body.
Definition graph.h:425
std::vector< RefId > nodes
The nodes of its own this body names, wherever it names them.
Definition graph.h:443
std::vector< RefId > refs
Every ref this body owns.
Definition graph.h:428
absl::flat_hash_map< RefId, int > writers
How many writers each written ref has.
Definition graph.h:437
absl::flat_hash_map< RefId, int > value_consumers
Consumers sharing each value cursor; retire it after the last consumer.
Definition graph.h:432
BodyId body
Definition graph.h:426
absl::flat_hash_map< StepId, std::vector< RefId > > held
Which destinations each step holds open until it finishes.
Definition graph.h:441
absl::flat_hash_set< RefId > materialise
Refs read inside a nested body.
Definition graph.h:435
std::vector< RefId > destinations
Every ref this body writes, whether or not anything reads it back.
Definition graph.h:439
absl::flat_hash_map< RefId, int > readers
How many readers each of them has.
Definition graph.h:430
A block of steps: a flow's top level, or a loop or branch body.
Definition graph.h:365
StepId owner_step
Definition graph.h:368
BodyId parent
Definition graph.h:367
std::vector< StepId > steps
Definition graph.h:369
std::string label
Definition graph.h:366
RefId source
Definition graph.h:381
RefId destination
Definition graph.h:382
const syntax::Builtin *absl_nonnull node
Definition graph.h:380
A resolved expression and its stream dependencies.
Definition graph.h:374
const syntax::Node *absl_nullable node
Definition graph.h:376
bool pipeline_owned
Definition graph.h:389
std::vector< ReferenceBinding > references
Definition graph.h:385
bool materialized
Definition graph.h:375
std::vector< std::pair< const syntax::Node *absl_nonnull, RefId > > bound
Definition graph.h:377
BodyId activation
Definition graph.h:388
std::vector< RefId > refs
The same refs, in the order they were first mentioned, for the analysis.
Definition graph.h:387
The executable graph of one flow.
Definition graph.h:394
std::vector< RefId > ValueRefs(RefId ref) const
The refs this one reads for their first value to produce itself.
Definition graph.cc:99
std::vector< RefId > ValueSources(StepId step) const
The refs a step reads for one value each.
Definition graph.cc:188
std::vector< RefId > StageDestinations(StepId step) const
Destinations written by stages a step reads, including failure streams.
Definition graph.cc:242
std::vector< Body > bodies
Definition graph.h:398
std::vector< Step > steps
Definition graph.h:397
std::string name
Definition graph.h:395
std::vector< Expr > exprs
Definition graph.h:399
std::vector< BodyId > NestedBodies(BodyId body) const
Every body inside this one, at any depth.
Definition graph.cc:286
BodyId root
The flow's top level.
Definition graph.h:401
std::vector< RefId > Destinations(StepId step) const
The refs a step writes, one entry per independent writer.
Definition graph.cc:216
std::vector< RefId > Upstreams(RefId ref) const
The refs this one reads as streams to produce itself.
Definition graph.cc:74
std::vector< RefId > Sources(StepId step) const
The refs a step reads as streams, one entry per independent read.
Definition graph.cc:151
std::vector< RefId > Observed(StepId step) const
Written refs a step only watches, without writing them itself.
Definition graph.cc:267
std::vector< Ref > refs
Definition graph.h:396
Resolved log or logf arguments for a statement or stage.
Definition graph.h:83
std::vector< ExprId > arguments
What to log, or what fills the format. Empty in a stage means it.
Definition graph.h:90
std::string level
The level, canonically spelled, or empty for the default.
Definition graph.h:85
std::string format
logf's format. Empty and has_format false for a log.
Definition graph.h:87
bool has_format
Definition graph.h:88
int line
Source line included in the log record.
Definition graph.h:92
One plan stream.
Definition graph.h:147
std::string label
How a reader would say it: search.hits | truncate 200.
Definition graph.h:151
BodyId owner
The body this belongs to, which is where it is materialised.
Definition graph.h:153
StepId subject_step
kStatus: the call or barrier it is the outcome of.
Definition graph.h:176
StepId bound_by
Definition graph.h:186
ExprId expr
kExpr: the expression evaluated once.
Definition graph.h:180
long long skip
Values skipped before fan-out; multiple skip n statements accumulate.
Definition graph.h:160
StepId phase_gate
Definition graph.h:148
RefId subject
kNodeId: the node. kStatus: the node or port it is the outcome of.
Definition graph.h:174
std::string header
kHeader: the header name, and the default when it was not sent.
Definition graph.h:178
StepId call
kCallPort: the call it belongs to.
Definition graph.h:169
Stage stage
Definition graph.h:183
std::vector< RefId > sources
kZip sources follow tuple order; kMerge follows arrival order.
Definition graph.h:188
ExprId id_expr
kNode: the id expression it attaches to, and the map it lands in.
Definition graph.h:171
std::string node_map
Definition graph.h:172
std::string name
kFlowPort, kCallPort, kNode: the port or node name.
Definition graph.h:163
bool unary
Whether the stream provably carries at most one value.
Definition graph.h:158
RefId source
kDerived: what it reads, and the stage applied to it.
Definition graph.h:182
bool writable
Whether this flow may write the stream.
Definition graph.h:155
RefKind kind
Definition graph.h:149
bool status_port
kFlowPort, kCallPort: write canonical status chunks here.
Definition graph.h:167
std::string role
kBound: which of a loop's streams this is – item, index, carry.
Definition graph.h:185
syntax::PortDirection direction
kFlowPort, kCallPort: which side it is on.
Definition graph.h:165
A resolved pipeline stage. kAt extracts a field from each stream value.
Definition graph.h:96
std::vector< std::string > destructured
Definition graph.h:122
ExprId expr
kExpression: the expression, with it bound.
Definition graph.h:109
vocabulary::StageArgument takes
Definition graph.h:102
bool indexed
Whether at was written as an index rather than a field name.
Definition graph.h:120
bool tolerant
try: tolerate an item's evaluation failure; context may retain it.
Definition graph.h:134
std::vector< std::optional< syntax::TypeExpression > > destructured_types
Definition graph.h:123
bool context_numbered
Definition graph.h:113
int parallel
parallel n: how many values this stage may work on at once.
Definition graph.h:138
ExprId parallel_expression
Definition graph.h:139
RefId destination
Destination context used by a terminal reference stage.
Definition graph.h:99
ExprId context_base
Definition graph.h:114
std::string text
kString/kOptionalString: the text. Also the field name for at.
Definition graph.h:106
ExprId context_after
Definition graph.h:112
bool optional
Definition graph.h:100
absl::Duration duration
kDuration: how long timeout waits for the next value, or pace leaves between two of them.
Definition graph.h:126
std::string name
Definition graph.h:97
RefId failures
try ... failures into ref: where a tolerated failure goes.
Definition graph.h:136
RefId stream
kStream: the stream then reads after this one.
Definition graph.h:116
std::string carried
Definition graph.h:131
syntax::Constant start
fold: initial value, carried name, and its expression reference.
Definition graph.h:130
long long index
Definition graph.h:121
bool descending
sort: whether the order is reversed.
Definition graph.h:128
long long count
kNumber: a constant count, or the runtime configuration when evaluated.
Definition graph.h:104
ExprId context_before
context: surrounding item counts, evaluated once at stage activation.
Definition graph.h:111
RefId carry
Definition graph.h:132
std::optional< syntax::TypeExpression > type
Definition graph.h:101
LogTail log
kLog/kLogFormat: what was written after the stage name.
Definition graph.h:118
bool ordered
Whether values leave in the order they arrived.
Definition graph.h:142
Outer values updated by a child body, with its per-body input versions.
Definition graph.h:341
std::vector< std::pair< BodyId, RefId > > inputs
Definition graph.h:343
RefId result
Definition graph.h:342
One resolved statement.
Definition graph.h:238
bool tee
Definition graph.h:260
std::optional< absl::Duration > timeout
Definition graph.h:257
StepId phase_gate
Definition graph.h:239
bool deferred
Definition graph.h:250
RefId item
kForEach: the value and the index each pass binds.
Definition graph.h:325
std::vector< std::pair< std::string, ExprId > > headers
Definition graph.h:262
std::vector< ExprId > expression_cleanups
Definition graph.h:286
ExprId condition
Definition graph.h:337
bool discard
kPipe: -> _, which reads the stream and keeps nothing.
Definition graph.h:285
std::shared_ptr< TransferPlan > transfer
Definition graph.h:273
RefId status
Its outcome, once something has asked for one.
Definition graph.h:268
ExprId message
Definition graph.h:313
std::string code_name
Canonical code written as a word, such as fail not_found "...".
Definition graph.h:316
std::string node_map
Definition graph.h:256
std::vector< RefId > subjects
kWait: the outcomes of a wait first of / wait all of, in the order they were written.
Definition graph.h:300
std::vector< StepId > preceding_steps
Definition graph.h:241
RefId index
Definition graph.h:326
std::vector< bool > subject_tolerant
Definition graph.h:301
StepKind kind
Definition graph.h:242
StepId deadline
Definition graph.h:258
std::optional< long long > count
kSkip: skip n port, which claims no reader slot – the count is applied where the stream is produced a...
Definition graph.h:289
std::vector< VariableUpdate > variable_updates
Definition graph.h:346
bool stop_when
Definition graph.h:338
syntax::Constant start
Definition graph.h:333
std::string slot
kCapture: which slot of the enclosing loop it fills.
Definition graph.h:291
bool race
kWait: whether the first subject to finish is enough.
Definition graph.h:303
StepId target
kCancel: the call to stop.
Definition graph.h:309
RefId sink
The observed continuation group produced by this operation, if any.
Definition graph.h:275
RefId winner
kWait: the value a race is – which subject won – for whoever reads it.
Definition graph.h:306
std::vector< StepId > after
What it waits for.
Definition graph.h:248
bool scope_barrier
Definition graph.h:240
RefId destination
Definition graph.h:272
ExprId parallel_expression
Definition graph.h:328
LogTail log
kLog: the level, the format and what fills it.
Definition graph.h:319
RefId carry_source
Definition graph.h:332
RefId source
kPipe reads and writes these refs. kCapture reads source.
Definition graph.h:271
absl::flat_hash_map< std::string, RefId > ports
Every port of this call that the flow wired up, by direction:name.
Definition graph.h:266
BodyId body
Definition graph.h:246
ExprId code
kFail.
Definition graph.h:312
StepId activation
Definition graph.h:251
syntax::Location location
Definition graph.h:249
StepId timeout_value
Definition graph.h:259
std::vector< std::string > forward
Definition graph.h:263
RefId outcome
kWait/kClose: the outcome read, and whether a bad one is this flow's business or the subject's.
Definition graph.h:295
std::string action
kCall.
Definition graph.h:254
RefId carry
kRepeat: what it carries, where the next pass's value comes from, and when it stops.
Definition graph.h:331
bool tolerant
Definition graph.h:261
int parallel
Definition graph.h:327
std::optional< int > max_iterations
max n, where one was written; nothing means the loop is bounded only by its condition.
Definition graph.h:336
ExprId action_id
Definition graph.h:264
std::string label
The name this step is known by: a bound name, or action/for/if with a #2 after it where one label is ...
Definition graph.h:245
std::string mode
Definition graph.h:255
std::vector< BodyId > bodies
kForEach, kRepeat, kIf: the bodies nested here, in reading order.
Definition graph.h:323
Sparse joins retain observable owned-call and expression cleanup boundaries.
Definition graph.h:223
RefId source
Definition graph.h:224
size_t target
Definition graph.h:225
bool expression
Definition graph.h:226
Extra transfer metadata is absent on ordinary single-arrow statements.
Definition graph.h:230
std::vector< RefId > destinations
Definition graph.h:232
std::vector< TransferJoin > joins
Definition graph.h:233
std::vector< RefId > sources
Definition graph.h:231
std::vector< StepId > destination_calls
Definition graph.h:234
name(arg, ...) – one of the language's fixed functions.
Definition syntax.h:278
A literal or folded literal expression, including nested lists and objects.
Definition syntax.h:62
The start token's byte span, line, and code-point column.
Definition syntax.h:39
Base of every syntax node: what it is, and where it started.
Definition syntax.h:179