Skip to content

Lineage

matchlab.lineage

Lineage algorithms over a plan tree.

Steps hold references to their inputs only (step.parents). There is no registry and no downstream pointer. "The DAG" is therefore whatever is reachable upstream from the node you are holding, and every graph operation is a pure function of a root node.

Nodes are deduplicated by object identity, not by name or config. A node feeding two branches is one object and is visited once (structural sharing), while two structurally identical but distinct nodes are two plan entries.

draw also owns the vocabulary for how a step is doing, meaning StepStatus and StepState, because the tree is where that vocabulary is read. matchlab.progress drives it during a collection. Nothing here executes anything.

Classes:

  • StepStatus –

    Where a step has got to in a collection.

  • StepState –

    A step's status, and how long it has been in it.

Functions:

  • walk –

    Return root and every transitive input, in topological order.

  • number –

    Map each step in root's plan to the position it is known by.

  • draw –

    root's sub-plan as an indented tree. See render, which this joins up.

  • render –

    Render root's sub-plan as an indented tree, inputs nested beneath consumers.

StepStatus

Bases: StrEnum


              flowchart TD
              matchlab.lineage.StepStatus[StepStatus]

              

              click matchlab.lineage.StepStatus href "" "matchlab.lineage.StepStatus"

Where a step has got to in a collection.

CACHED, DONE and REFRESHED all mean the artifact is available. They differ in why.

DONE and REFRESHED both paid for the artifact. A DONE step ran because something it depends on moved. A REFRESHED step ran because it cannot be cached at all, and it will run again next time.

Attributes:

PENDING class-attribute instance-attribute 

PENDING = 'pending'

RUNNING class-attribute instance-attribute 

RUNNING = 'running'

DONE class-attribute instance-attribute 

DONE = 'done'

CACHED class-attribute instance-attribute 

CACHED = 'cached'

REFRESHED class-attribute instance-attribute 

REFRESHED = 'refreshed'

FAILED class-attribute instance-attribute 

FAILED = 'failed'

marker property 

marker: str

A single-width glyph for this status.

Deliberately geometric rather than emoji: emoji are double-width in some terminals and single in others, which knocks a tree's guide lines out of alignment line by line.

style property 

style: str

A Rich style for this status, used when drawing with markup.

StepState

Bases: BaseModel


              flowchart TD
              matchlab.lineage.StepState[StepState]

              

              click matchlab.lineage.StepState href "" "matchlab.lineage.StepState"

A step's status, and how long it has been in it.

Methods:

  • annotation –

    The trailing detail shown after a step in a drawing, possibly empty.

Attributes:

model_config class-attribute instance-attribute 

model_config = ConfigDict(frozen=True)

status instance-attribute 

status: StepStatus

elapsed class-attribute instance-attribute 

elapsed: float | None = None

annotation 

annotation() -> str

The trailing detail shown after a step in a drawing, possibly empty.

A time is shown only where it was spent. A cached step reads cached alone, because 0.0s next to it says nothing.

walk 

walk(root: Step) -> list[Step]

Return root and every transitive input, in topological order.

Upstream steps always precede the steps that consume them, so executing the returned list in order satisfies every dependency. Implemented as an iterative depth-first post-order over the parent references.

number 

number(root: Step) -> dict[int, int]

Map each step in root's plan to the position it is known by.

A step is referred to by position, in logs, in draw(), and in a document. The position belongs to the walk rather than to the step: the same node numbers differently in walk(deduped) and walk(companies), so nothing is written back onto the steps. Callers that need one hold this mapping, as draw does and as matchlab.progress.Progress does for the walk collect gave it.

Returns:

  • dict[int, int] –

    Step identity to position, in walk order.

draw 

draw(root: Step, state: Mapping[int, StepState] | None = None, *, markup: bool = False) -> str

root's sub-plan as an indented tree. See render, which this joins up.

render 

render(root: Step, state: Mapping[int, StepState] | None = None, *, markup: bool = False) -> tuple[list[str], dict[int, int]]

Render root's sub-plan as an indented tree, inputs nested beneath consumers.

Each node carries its position, the index collect runs it at, and the index it occupies in this plan's document. The index is the cross-reference, where step 7 is the node drawn as [7]. Positions come from walk, not from the order these lines happen to be printed in, since a tree nests consumers above their inputs while a walk lists inputs first.

Parameters:

  • root

    (Step) –

    The step to draw, along with everything upstream of it.

  • state

    (Mapping[int, StepState] | None, default: None ) –

    Per-step status, keyed by id(step) as number is. Steps missing from the mapping are drawn as PENDING. When omitted, each step is drawn from its own is_collected flag instead, a static view of a plan you hold.

  • markup

    (bool, default: False ) –

    Emit Rich markup, styling each marker and annotation by status. Off by default, so the return value stays printable anywhere.

Returns:

  • list[str] –

    The lines, one per node plus one per repeat reference, and the row each step

  • dict[int, int] –

    is first drawn on, keyed by id(step) as number is. The rows are what let a

  • tuple[list[str], dict[int, int]] –

    caller show part of a tree and still know where it is: matchlab.progress

  • tuple[list[str], dict[int, int]] –

    windows a plan too tall for the terminal around the row that is running.

A node feeding several branches is expanded where it is first met and marked ↑ everywhere after, rather than having its whole subtree redrawn each time. Positions are what make that readable. ↑ [12] names the node you already have, and without it the drawing contradicts the structural sharing it is meant to show. The 24-step plan in examples/companies draws 187 lines expanded, and 39 like this.