Skip to content

classBackwardSlicer

packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:30

final class BackwardSlicer

Restricted visibility: declared "@visibility root". Code outside that scope must not name this declaration.

Walks back from a call to the start of its body, keeping only what its argument depends on.

The walk starts with the names the argument reads and goes back statement by statement. An assignment to one of those names is kept as a step, and the names its right-hand side reads are looked for instead. A branch that assigns none of them is stepped over whole; one that does splits the path into one path per arm, which is what keeps the values an arm assigns together. A loop becomes one path per number of passes, up to the budget's limit. What comes out at the start of the body is the set of paths, each with the steps that lead from there to the call and the names still left to find.

Constants§

public const MAX_PATHS = 24

How many paths are kept apart before the rest are gathered into one.

Methods§

public function __construct(
    SourceTree $tree,
    EvaluationBudget $budget,
    ?FreeNames $names = null,
    ?ModifiedNames $modified = null,
)

Wires the slicer to the source it walks and the budget it spends.

Parameters

`$tree`	`SourceTree`
`$budget`	`EvaluationBudget`
`$names`	`?FreeNames`
`$modified`	`?ModifiedNames`

Calls 5

public function sliceFrom(Node $point, array<string, true> $needs): list<Arrival>

Every path from the start of the body to the point, with what each still needs.

Parameters

`$point`	`Node`
`$needs`	`array<string, true>`	The names the value at the point reads

Returns

list<Arrival>

Test cases 3

Called from 3

Calls 5

static-call Pending::needing() line 77
method-call SourceTree::anchorOf() line 78
method-call BackwardSlicer::leave() line 80
new Arrival line 83
method-call BackwardSlicer::before() line 83

public function sliceFromEnd(FunctionLike $body, array<string, true> $needs): list<Arrival>

Every path from the start of a body to its end, with what each still needs.

Parameters

`$body`	`FunctionLike`
`$needs`	`array<string, true>`	The names read at the end of the body

Returns

list<Arrival>

Test cases 1

BackwardSlicerTest::testSliceFromEndWalksBackFromTheEndOfABody calls

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Deriver::solveAtExits() packages/sql-catalog/src/Core/Analysis/Derivation/Deriver.php:137

Calls 6

function-call array_values line 94
method-call FunctionLike::getStmts() line 94
method-call BackwardSlicer::leave() line 96
method-call BackwardSlicer::walkList() line 96
function-call count line 96
static-call Pending::needing() line 96

public function before(Stmt $statement, list<Pending> $paths): list<Arrival>

The paths walked back over everything before a statement, and on out of its list.

Parameters

`$statement`	`Stmt`
`$paths`	`list<Pending>`

Returns

list<Arrival>

Test cases 2

Called from 5

Calls 5

method-call SourceTree::locate() line 107
method-call BackwardSlicer::arrive() line 109
method-call SourceTree::bodyOf() line 109
method-call BackwardSlicer::leave() line 113
method-call BackwardSlicer::walkList() line 113

public function leave(?Node $owner, list<Pending> $paths): list<Arrival>

The paths carried out of the start of a statement list, into whatever owns it.

Parameters

`$owner`	`?Node`
`$paths`	`list<Pending>`

Returns

list<Arrival>

Test cases 2

Called from 4

Calls 10

method-call BackwardSlicer::arrive() line 125
method-call BackwardSlicer::leaveClosure() line 131
method-call LoopPasses::isLoop() line 133
method-call LoopPasses::leaveBody() line 134
method-call BackwardSlicer::before() line 139
method-call BackwardSlicer::walkList() line 139
function-call array_values line 139
function-call count line 139
method-call BackwardSlicer::owningStatement() line 142
method-call SourceTree::bodyOf() line 144

public function owningStatement(Node $owner): ?Stmt

The statement an arm or a block belongs to, which is where the walk goes on from.

Parameters

$owner Node

Returns

?Stmt

Test cases 1

BackwardSlicerTest::testOwningStatementIsTheStatementAnArmBelongsTo calls

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Slice\BackwardSlicer::leave() packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:142

Calls 1

method-call Node::getAttribute() line 154

public function leaveClosure(
    Closure|ArrowFunction $closure,
    list<Pending> $paths,
): list<Arrival>

The paths carried out of a closure into the body it is written in.

What the closure takes from outside — its use list, or for an arrow function every name that is not one of its parameters — is looked for where the closure is written. Its parameters, and any name it reads without defining, are its own: a step says so, and the walk does not look for them outside.

Parameters

`$closure`	`Closure\|ArrowFunction`
`$paths`	`list<Pending>`

Returns

list<Arrival>

Test cases 1

BackwardSlicerTest::testLeaveClosureTakesOnlyTheUseListFromOutside calls

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Slice\BackwardSlicer::leave() packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:131

Calls 8

method-call BackwardSlicer::outside() line 178
function-call array_keys line 179
function-call array_diff_key line 179
new SliceStep line 180
method-call SourceTree::anchorOf() line 182
method-call BackwardSlicer::leave() line 184
method-call BackwardSlicer::arrive() line 187
method-call BackwardSlicer::before() line 187

public function outside(
    Closure|ArrowFunction $closure,
    array<string, true> $needs,
): array<string, true>

The names among those needed that a closure takes from where it is written.

Parameters

`$closure`	`Closure\|ArrowFunction`
`$needs`	`array<string, true>`

Returns

array<string, true>

Test cases 1

BackwardSlicerTest::testOutsideIsWhatAClosureTakesFromWhereItIsWritten calls

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Slice\BackwardSlicer::leaveClosure() packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:178

Calls 4

function-call is_string line 200
function-call array_diff_key line 205
class-const FreeNames::THIS() line 207
function-call array_intersect_key line 214

public function arrive(?FunctionLike $body, list<Pending> $paths): list<Arrival>

The paths that reached the start of a body, as arrivals there.

Parameters

`$body`	`?FunctionLike`
`$paths`	`list<Pending>`

Returns

list<Arrival>

Test cases 1

BackwardSlicerTest::testArriveNamesTheNamedBodyAClosureIsWrittenIn calls

Called from 5

Calls 3

method-call SourceTree::bodyOf() line 227
function-call array_map line 230
new Arrival line 230

public function walkList(list<Stmt> $list, int $end, list<Pending> $paths): list<Pending>

The paths walked back over the statements of a list, from the given position to its start.

Parameters

`$list`	`list<Stmt>`
`$end`	`int`
`$paths`	`list<Pending>`

Returns

list<Pending>

Test cases 1

BackwardSlicerTest::testWalkListStopsOnceEveryPathIsDone calls

Called from 7

Calls 4

method-call BackwardSlicer::allDone() line 243
function-call array_merge line 248
method-call BackwardSlicer::over() line 248
method-call BackwardSlicer::bound() line 250

public function allDone(list<Pending> $paths): bool

Whether no path has anything left to find.

Parameters

$paths list<Pending>

Returns

bool

Test cases 1

BackwardSlicerTest::testAllDoneIsTrueOnlyWhenNoPathNeedsAnything calls

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Slice\BackwardSlicer::walkList() packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:243

public function over(Stmt $statement, Pending $path): list<Pending>

One path walked back over one statement.

Parameters

`$statement`	`Stmt`
`$path`	`Pending`

Returns

list<Pending>

Test cases 2

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Slice\BackwardSlicer::walkList() packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:248

Calls 15

method-call EvaluationBudget::spend() line 279
method-call Pending::exhaust() line 280
method-call ModifiedNames::touches() line 282
method-call AssignmentSteps::over() line 286
method-call ModifiedNames::tracksObjects() line 288
method-call AssignmentSteps::declaration() line 292
method-call BackwardSlicer::walkList() line 295
function-call array_values line 295
function-call count line 295
method-call LoopPasses::isLoop() line 297
method-call BackwardSlicer::branch() line 298
method-call LoopPasses::runs() line 298
method-call BranchArms::of() line 300
method-call BackwardSlicer::walkArms() line 304
function-call array_map line 306

public function walkArms(list<list<Stmt>> $arms, array<string, true> $needs): list<Pending>

Each arm walked back from its end, as paths that start where the branch finishes.

Parameters

`$arms`	`list<list<Stmt>>`
`$needs`	`array<string, true>`

Returns

list<Pending>

Test cases 1

BackwardSlicerTest::testWalkArmsWalksEachArmFromItsEnd calls

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Slice\BackwardSlicer::over() packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:304

Calls 4

function-call array_merge line 323
method-call BackwardSlicer::walkList() line 323
function-call count line 323
static-call Pending::needing() line 323

public function branch(Pending $path, list<Pending> $runs): list<Pending>

A path taken on over the runs a branch may have taken.

The runs become one step that holds them as alternatives, rather than one path each. Running the step still runs every arm on its own, so the values an arm assigns stay together; what is saved is walking the rest of the body once per arm, which for a body of ten consecutive conditionals would be a thousand walks.

Parameters

`$path`	`Pending`
`$runs`	`list<Pending>`	Paths that start where the branch finishes

Returns

list<Pending>

Test cases 1

BackwardSlicerTest::testBranchHoldsSeveralRunsAsOneStep calls

Called from 2

Calls 3

method-call Pending::then() line 347
function-call count line 347
static-call Pending::gather() line 347

public function bound(list<Pending> $paths): list<Pending>

The paths with repeats merged and the rest gathered once there are too many to keep apart.

Parameters

$paths list<Pending>

Returns

list<Pending>

Test cases 1

BackwardSlicerTest::testBoundMergesRepeatsAndGathersPathsBeyondTheLimit calls

Called from 1

method-call SqlCatalog\Core\Analysis\Derivation\Slice\BackwardSlicer::walkList() packages/sql-catalog/src/Core/Analysis/Derivation/Slice/BackwardSlicer.php:250

Calls 5

function-call array_values line 362
function-call count line 363
class-const BackwardSlicer::MAX_PATHS() line 363
function-call array_slice line 366
static-call Pending::gather() line 369

Private surface 7§

Implementation details, listed for orientation only.

private SourceTree $tree

private EvaluationBudget $budget

private FreeNames $names

private ModifiedNames $modified

private LoopPasses $loops

private BranchArms $arms

private AssignmentSteps $steps

Test cases 93§

Test cases that cover or call this symbol, from the coverage report and from the analyzed test sources.

Dedicated tests 19

Other tests reaching this symbol 74

Relations§

Instantiated in 1

new SqlCatalog\Core\Analysis\Interpreter::deriverFor() packages/sql-catalog/src/Core/Analysis/Interpreter.php:150

Method calls 7

Type declarations 7