Public Member Functions
array	orderByDependencies (array $items, $beforeKey='before', $afterKey='after')

array< array-key, buildDependencyGraph(array $dependencies, $beforeKey='before', $afterKey='after') { $dependencies=$this->	prepareDependencies ($dependencies, $beforeKey, $afterKey)

mixed[]	calculateOrder (array $dependencyGraph)

array	findRootIds (array $dependencyGraph)

Public Attributes
	$identifiers = array_keys($dependencies)

	$dependencyGraph = array_fill_keys($identifiers, array_fill_keys($identifiers, false))

foreach($identifiers as $id) foreach($identifiers as $id) return	$dependencyGraph

Protected Member Functions
int	getIncomingEdgeCount (array $dependencyGraph, $identifier)

array	findPathInGraph (array $graph, $from, $to)

array	prepareDependencies (array $dependencies, $beforeKey='before', $afterKey='after')

Detailed Description

This class provides functionality to build an ordered list from a set of dependencies.

We use an adjacency matrix for the dependency graph (DAG)

Example structure of the DAG is: A => (A => FALSE, B => TRUE, C => FALSE) B => (A => FALSE, B => FALSE, C => FALSE) C => (A => TRUE, B => FALSE, C => FALSE)

A depends on B, C depends on A, B is independent

Definition at line 31 of file DependencyOrderingService.php.

Member Function Documentation

◆ calculateOrder()

mixed [] TYPO3\CMS\Core\Service\DependencyOrderingService::calculateOrder ( array $dependencyGraph )

Calculate an ordered list for a dependencyGraph

Parameters

bool[][] $dependencyGraph

Returns: ‪mixed[] Sorted array of keys of $dependencies

Exceptions

Definition at line 140 of file DependencyOrderingService.php.

References TYPO3\CMS\Core\Service\DependencyOrderingService\$dependencyGraph, TYPO3\CMS\Core\Service\DependencyOrderingService\findRootIds(), and TYPO3\CMS\Core\Service\DependencyOrderingService\getIncomingEdgeCount().

Referenced by TYPO3\CMS\Core\Service\DependencyOrderingService\orderByDependencies().

◆ findPathInGraph()

array TYPO3\CMS\Core\Service\DependencyOrderingService::findPathInGraph	(	array	$graph,
			$from,
			$to
	)

protected

Find any path in the graph from given start node to destination node

Parameters

array	$graph	‪Directed graph
string	$from	‪Start node
string	$to	‪Destination node

Returns: ‪array Nodes of the found path; empty if no path is found

Definition at line 245 of file DependencyOrderingService.php.

◆ findRootIds()

array TYPO3\CMS\Core\Service\DependencyOrderingService::findRootIds ( array $dependencyGraph )

Find all root nodes of a graph

Root nodes are those, where nothing else depends on (they can be the last in the loading order). If there are no dependencies at all, all nodes are root nodes.

Parameters

bool[][] $dependencyGraph

Returns: ‪array List of identifiers which are root nodes

Definition at line 225 of file DependencyOrderingService.php.

References TYPO3\CMS\Core\Service\DependencyOrderingService\$dependencyGraph, and TYPO3\CMS\Core\Service\DependencyOrderingService\getIncomingEdgeCount().

Referenced by TYPO3\CMS\Core\Service\DependencyOrderingService\calculateOrder().

◆ getIncomingEdgeCount()

int TYPO3\CMS\Core\Service\DependencyOrderingService::getIncomingEdgeCount	(	array	$dependencyGraph,
			$identifier
	)

protected

Get the number of incoming edges in the dependency graph for given identifier

Parameters

string $identifier

Returns: ‪int

Definition at line 205 of file DependencyOrderingService.php.

References TYPO3\CMS\Core\Service\DependencyOrderingService\$dependencyGraph, and TYPO3\CMS\Webhooks\Message\$identifier.

Referenced by TYPO3\CMS\Core\Service\DependencyOrderingService\calculateOrder(), and TYPO3\CMS\Core\Service\DependencyOrderingService\findRootIds().

◆ orderByDependencies()

array TYPO3\CMS\Core\Service\DependencyOrderingService::orderByDependencies	(	array	$items,
			$beforeKey = `'before'`,
			$afterKey = `'after'`
	)

Order items by specified dependencies before/after

The dependencies of an items are specified as: 'someItemKey' => [ 'before' => ['someItemKeyA', 'someItemKeyB'] 'after' => ['someItemKeyC'] ]

If your items use different keys for specifying the relations, you can define the appropriate keys by setting the $beforeKey and $afterKey parameters accordingly.

Parameters

array	$items
string	$beforeKey	‪The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
string	$afterKey	‪The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'

Returns: ‪array

Exceptions

Definition at line 51 of file DependencyOrderingService.php.

References TYPO3\CMS\Core\Service\DependencyOrderingService\calculateOrder().

Referenced by TYPO3\CMS\Core\Resource\Processing\ProcessorRegistry\__construct().

◆ prepareDependencies() [1/2]

array<array-key, buildDependencyGraph(array $dependencies, $beforeKey = 'before', $afterKey = 'after') { $dependencies = $this-> TYPO3\CMS\Core\Service\DependencyOrderingService::prepareDependencies	(	$dependencies,
		$beforeKey,
		$afterKey
	)

Builds the dependency graph for the given dependencies

The dependencies have to specified in the following structure:

$dependencies = [
  'someKey' => [
     'before' => ['someKeyA', 'someKeyB']
     'after' => ['someKeyC']
  ]
]

We interpret a dependency like

'A' => [
  'before' => ['B'],
  'after' => ['C', 'D']
]

as

‪A depends on C
‪A depends on D
‪B depends on A

Parameters

array	$dependencies
string	$beforeKey	‪The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
string	$afterKey	‪The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'

Returns: ‪array<array-key, array<array-key, bool>> The dependency graph

◆ prepareDependencies() [2/2]

array TYPO3\CMS\Core\Service\DependencyOrderingService::prepareDependencies	(	array	$dependencies,
			$beforeKey = `'before'`,
			$afterKey = `'after'`
	)

protected

Prepare dependencies

Ensure that all discovered identifiers are added to the dependency list so we can reliably use the identifiers to build the matrix. Additionally fix all invalid or missing before/after arrays

Parameters

array	$dependencies
string	$beforeKey	‪The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
string	$afterKey	‪The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'