8000 Improve performances in CircualReference detection · symfony/symfony@c6ac7d7 · GitHub
[go: up one dir, main page]
Skip to content

Commit c6ac7d7

Browse files
jderussejderusse
committed
Improve performances in CircualReference detection
1 parent 13af58c commit c6ac7d7

File tree

1 file changed

+45
-36
lines changed

1 file changed

+45
-36
lines changed

‎src/Symfony/Component/DependencyInjection/Dumper/PhpDumper.php

Lines changed: 45 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -195,6 +195,7 @@ public function dump(array $options = [])
195195
$this->singleUsePrivateIds[$id] = $id;
196196
}
197197
}
198+
198199
$this->container->getCompiler()->getServiceReferenceGraph()->clear();
199200
$checkedNodes = [];
200201
$this->singleUsePrivateIds = array_diff_key($this->singleUsePrivateIds, $this->circularReferences);
@@ -409,58 +410,66 @@ private function getProxyDumper(): ProxyDumper
409410
return $this->proxyDumper;
410411
}
411412

412-
private function analyzeCircularReferences(string $sourceId, array $edges, array &$checkedNodes, array &$currentPath = [], bool $byConstructor = true)
413+
private function analyzeCircularReferences(string $sourceId, array $edges, array &$checkedNodes, bool $byConstructor = true)
413414
{
414-
$checkedNodes[$sourceId] = true;
415-
$currentPath[$sourceId] = $byConstructor;
415+
$newNodes = [];
416+
$this->collectReferences($sourceId, $edges, $checkedNodes, $newNodes);
417+
$this->flattendNewReferences($checkedNodes, $newNodes);
418+
419+
foreach ($newNodes as $newNodeId => $_) {
420+
if (isset($checkedNodes[$newNodeId][$newNodeId])) {
421+
$this->addCircularReferences($newNodeId, $checkedNodes[$newNodeId][$newNodeId][0], $byConstructor && $checkedNodes[$newNodeId][$newNodeId][1]);
422+
}
423+
}
424+
}
416425

426+
private function collectReferences(string $sourceId, array $edges, array &$checkedNodes, array &$newNodes)
427+
{
428+
$checkedNodes[$sourceId] = [];
429+
$newNodes[$sourceId] = [];
417430
foreach ($edges as $edge) {
418431
$node = $edge->getDestNode();
419432
$id = $node->getId();
420-
421433
if (!$node->getValue() instanceof Definition || $sourceId === $id || $edge->isLazy() || $edge->isWeak()) {
422-
// no-op
423-
} elseif (isset($currentPath[$id])) {
424-
$this->addCircularReferences($id, $currentPath, $edge->isReferencedByConstructor());
425-
} elseif (!isset($checkedNodes[$id])) {
426-
$this->analyzeCircularReferences($id, $node->getOutEdges(), $checkedNodes, $currentPath, $edge->isReferencedByConstructor());
427-
} elseif (isset($this->circularReferences[$id])) {
428-
$this->connectCircularReferences($id, $currentPath, $edge->isReferencedByConstructor());
434+
continue;
429435
}
430-
}
431-
unset($currentPath[$sourceId]);
432-
}
433436

434-
private function connectCircularReferences(string $sourceId, array &$currentPath, bool $byConstructor, array &$subPath = [])
435-
{
436-
$currentPath[$sourceId] = $subPath[$sourceId] = $byConstructor;
437+
if (!isset($checkedNodes[$id])) {
438+
$this->collectReferences($id, $node->getOutEdges(), $checkedNodes, $newNodes);
439+
}
437440

438-
foreach ($this->circularReferences[$sourceId] as $id => $byConstructor) {
439-
if (isset($currentPath[$id])) {
440-
$this->addCircularReferences($id, $currentPath, $byConstructor);
441-
} elseif (!isset($subPath[$id]) && isset($this->circularReferences[$id])) {
442-
$this->connectCircularReferences($id, $currentPath, $byConstructor, $subPath);
441+
$checkedNodes[$sourceId][$id] = [[], $edge->isReferencedByConstructor()];
442+
if (isset($newNodes[$id])) {
443+
$newNodes[$id][$sourceId] = true;
443444
}
444445
}
445-
unset($currentPath[$sourceId], $subPath[$sourceId]);
446446
}
447447

448-
private function addCircularReferences(string $id, array $currentPath, bool $byConstructor)
448+
private function flattendNewReferences(array &$checkedNodes, array $newNodes)
449449
{
450-
$currentPath[$id] = $byConstructor;
451-
$circularRefs = [];
452-
453-
foreach (array_reverse($currentPath) as $parentId => $v) {
454-
$byConstructor = $byConstructor && $v;
455-
$circularRefs[] = $parentId;
456-
457-
if ($parentId === $id) {
458-
break;
450+
$nodesToFlatten = array_keys($newNodes);
451+
do {
452+
$changedNodes = [];
453+
foreach ($nodesToFlatten as $newNodeId) {
454+
$deps = &$checkedNodes[$newNodeId];
455+
foreach ($deps as $id => [$path, $depsByConstructor]) {
456+
foreach ($checkedNodes[$id] as $depsId => [$subPath, $subDepsByConstructor]) {
457+
if (!isset($deps[$depsId]) || ($depsByConstructor && $subDepsByConstructor && !$deps[$depsId][1])) {
458+
$deps[$depsId] = [array_merge([$id], $subPath), $depsByConstructor && $subDepsByConstructor];
459+
$changedNodes += $newNodes[$newNodeId] ?? [];
460+
}
461+
}
462+
}
459463
}
460-
}
464+
$nodesToFlatten = array_keys($changedNodes);
465+
} while (!empty($nodesToFlatten));
466+
}
461467

462-
$currentId = $id;
463-
foreach ($circularRefs as $parentId) {
468+
private function addCircularReferences(string $sourceId, array $currentPath, bool $byConstructor)
469+
{
470+
$currentId = $sourceId;
471+
array_unshift($currentPath, $currentId);
472+
foreach (array_reverse($currentPath) as $parentId) {
464473
if (empty($this->circularReferences[$parentId][$currentId])) {
465474
$this->circularReferences[$parentId][$currentId] = $byConstructor;
466475
}

0 commit comments

Comments
 (0)
0