doctrine · greg0ire · Aug 1, 2023 · Mar 23, 2023 · Mar 23, 2023 · Apr 24, 2023
diff --git a/UPGRADE.md b/UPGRADE.md
@@ -1,5 +1,12 @@
 # Upgrade to 2.16
 
+## Deprecated `\Doctrine\ORM\Internal\CommitOrderCalculator` and related classes
+
+With changes made to the commit order computation, the internal classes
+`\Doctrine\ORM\Internal\CommitOrderCalculator`, `\Doctrine\ORM\Internal\CommitOrder\Edge`,
+`\Doctrine\ORM\Internal\CommitOrder\Vertex` and `\Doctrine\ORM\Internal\CommitOrder\VertexState`
+have been deprecated and will be removed in ORM 3.0.
+
 ## Deprecated returning post insert IDs from `EntityPersister::executeInserts()`
 
 Persisters implementing `\Doctrine\ORM\Persisters\Entity\EntityPersister` should no longer

diff --git a/docs/en/reference/events.rst b/docs/en/reference/events.rst
@@ -707,8 +707,8 @@ not directly mapped by Doctrine.
    ``UPDATE`` statement.
 -  The ``postPersist`` event occurs for an entity after
    the entity has been made persistent. It will be invoked after the
-   database insert operations. Generated primary key values are
-   available in the postPersist event.
+   database insert operation for that entity. A generated primary key value for
+   the entity will be available in the postPersist event.
 -  The ``postRemove`` event occurs for an entity after the
    entity has been deleted. It will be invoked after the database
    delete operations. It is not called for a DQL ``DELETE`` statement.

diff --git a/lib/Doctrine/ORM/Cache/Persister/Entity/AbstractEntityPersister.php b/lib/Doctrine/ORM/Cache/Persister/Entity/AbstractEntityPersister.php
@@ -23,6 +23,7 @@
 use Doctrine\ORM\Persisters\Entity\EntityPersister;
 use Doctrine\ORM\UnitOfWork;
 
+use function array_merge;
 use function assert;
 use function serialize;
 use function sha1;
@@ -314,7 +315,13 @@ public function getOwningTable($fieldName)
      */
     public function executeInserts()
     {
-        $this->queuedCache['insert'] = $this->persister->getInserts();
+        // The commit order/foreign key relationships may make it necessary that multiple calls to executeInsert()
+        // are performed, so collect all the new entities.
+        $newInserts = $this->persister->getInserts();
+
+        if ($newInserts) {
+            $this->queuedCache['insert'] = array_merge($this->queuedCache['insert'] ?? [], $newInserts);
+        }
 
         return $this->persister->executeInserts();
     }

diff --git a/lib/Doctrine/ORM/Internal/CommitOrder/Edge.php b/lib/Doctrine/ORM/Internal/CommitOrder/Edge.php
@@ -4,7 +4,12 @@
 
 namespace Doctrine\ORM\Internal\CommitOrder;
 
-/** @internal */
+use Doctrine\Deprecations\Deprecation;
+
+/**
+ * @internal
+ * @deprecated
+ */
 final class Edge
 {
     /**
@@ -27,6 +32,13 @@ final class Edge
 
     public function __construct(string $from, string $to, int $weight)
     {
+        Deprecation::triggerIfCalledFromOutside(
+            'doctrine/orm',
+            'https://github.com/doctrine/orm/pull/10547',
+            'The %s class is deprecated and will be removed in ORM 3.0',
+            self::class
+        );
+
         $this->from   = $from;
         $this->to     = $to;
         $this->weight = $weight;

diff --git a/lib/Doctrine/ORM/Internal/CommitOrder/Vertex.php b/lib/Doctrine/ORM/Internal/CommitOrder/Vertex.php
@@ -4,9 +4,13 @@
 
 namespace Doctrine\ORM\Internal\CommitOrder;
 
+use Doctrine\Deprecations\Deprecation;
 use Doctrine\ORM\Mapping\ClassMetadata;
 
-/** @internal */
+/**
+ * @internal
+ * @deprecated
+ */
 final class Vertex
 {
     /**
@@ -32,6 +36,13 @@ final class Vertex
 
     public function __construct(string $hash, ClassMetadata $value)
     {
+        Deprecation::triggerIfCalledFromOutside(
+            'doctrine/orm',
+            'https://github.com/doctrine/orm/pull/10547',
+            'The %s class is deprecated and will be removed in ORM 3.0',
+            self::class
+        );
+
         $this->hash  = $hash;
         $this->value = $value;
     }

diff --git a/lib/Doctrine/ORM/Internal/CommitOrder/VertexState.php b/lib/Doctrine/ORM/Internal/CommitOrder/VertexState.php
@@ -4,7 +4,12 @@
 
 namespace Doctrine\ORM\Internal\CommitOrder;
 
-/** @internal */
+use Doctrine\Deprecations\Deprecation;
+
+/**
+ * @internal
+ * @deprecated
+ */
 final class VertexState
 {
     public const NOT_VISITED = 0;
@@ -13,5 +18,11 @@ final class VertexState
 
     private function __construct()
     {
+        Deprecation::triggerIfCalledFromOutside(
+            'doctrine/orm',
+            'https://github.com/doctrine/orm/pull/10547',
+            'The %s class is deprecated and will be removed in ORM 3.0',
+            self::class
+        );
     }
 }
diff --git a/lib/Doctrine/ORM/Internal/CommitOrderCalculator.php b/lib/Doctrine/ORM/Internal/CommitOrderCalculator.php
@@ -4,6 +4,7 @@
 
 namespace Doctrine\ORM\Internal;
 
+use Doctrine\Deprecations\Deprecation;
 use Doctrine\ORM\Internal\CommitOrder\Edge;
 use Doctrine\ORM\Internal\CommitOrder\Vertex;
 use Doctrine\ORM\Internal\CommitOrder\VertexState;
@@ -17,6 +18,8 @@
  * using a depth-first searching (DFS) to traverse the graph built in memory.
  * This algorithm have a linear running time based on nodes (V) and dependency
  * between the nodes (E), resulting in a computational complexity of O(V + E).
+ *
+ * @deprecated
  */
 class CommitOrderCalculator
 {
@@ -45,6 +48,16 @@ class CommitOrderCalculator
      */
     private $sortedNodeList = [];
 
+    public function __construct()
+    {
+        Deprecation::triggerIfCalledFromOutside(
+            'doctrine/orm',
+            'https://github.com/doctrine/orm/pull/10547',
+            'The %s class is deprecated and will be removed in ORM 3.0',
+            self::class
+        );
+    }
+
     /**
      * Checks for node (vertex) existence in graph.
      *

diff --git a/lib/Doctrine/ORM/Internal/TopologicalSort.php b/lib/Doctrine/ORM/Internal/TopologicalSort.php
@@ -0,0 +1,165 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Doctrine\ORM\Internal;
+
+use Doctrine\ORM\Internal\TopologicalSort\CycleDetectedException;
+
+use function array_keys;
+use function array_reverse;
+use function array_unshift;
+use function spl_object_id;
+
+/**
+ * TopologicalSort implements topological sorting, which is an ordering
+ * algorithm for directed graphs (DG) using a depth-first searching (DFS)
+ * to traverse the graph built in memory.
+ * This algorithm has a linear running time based on nodes (V) and edges
+ * between the nodes (E), resulting in a computational complexity of O(V + E).
+ *
+ * @internal
+ */
+final class TopologicalSort
+{
+    private const NOT_VISITED = 1;
+    private const IN_PROGRESS = 2;
+    private const VISITED     = 3;
+
+    /**
+     * Array of all nodes, indexed by object ids.
+     *
+     * @var array<int, object>
+     */
+    private $nodes = [];
+
+    /**
+     * DFS state for the different nodes, indexed by node object id and using one of
+     * this class' constants as value.
+     *
+     * @var array<int, self::*>
+     */
+    private $states = [];
+
+    /**
+     * Edges between the nodes. The first-level key is the object id of the outgoing
+     * node; the second array maps the destination node by object id as key. The final
+     * boolean value indicates whether the edge is optional or not.
+     *
+     * @var array<int, array<int, bool>>
+     */
+    private $edges = [];
+
+    /**
+     * Builds up the result during the DFS.
+     *
+     * @var list<object>
+     */
+    private $sortResult = [];
+
+    /** @param object $node */
+    public function addNode($node): void
+    {
+        $id                = spl_object_id($node);
+        $this->nodes[$id]  = $node;
+        $this->states[$id] = self::NOT_VISITED;
+        $this->edges[$id]  = [];
+    }
+
+    /** @param object $node */
+    public function hasNode($node): bool
+    {
+        return isset($this->nodes[spl_object_id($node)]);
+    }
+
+    /**
+     * Adds a new edge between two nodes to the graph
+     *
+     * @param object $from
+     * @param object $to
+     * @param bool   $optional This indicates whether the edge may be ignored during the topological sort if it is necessary to break cycles.
+     */
+    public function addEdge($from, $to, bool $optional): void
+    {
+        $fromId = spl_object_id($from);
+        $toId   = spl_object_id($to);
+
+        if (isset($this->edges[$fromId][$toId]) && $this->edges[$fromId][$toId] === false) {
+            return; // we already know about this dependency, and it is not optional
+        }
+
+        $this->edges[$fromId][$toId] = $optional;
+    }
+
+    /**
+     * Returns a topological sort of all nodes. When we have an edge A->B between two nodes
+     * A and B, then A will be listed before B in the result.
+     *
+     * @return list<object>
+     */
+    public function sort(): array
+    {
+        /*
+         * When possible, keep objects in the result in the same order in which they were added as nodes.
+         * Since nodes are unshifted into $this->>sortResult (see the visit() method), that means we
+         * need to work them in array_reverse order here.
+         */
+        foreach (array_reverse(array_keys($this->nodes)) as $oid) {
+            if ($this->states[$oid] === self::NOT_VISITED) {
+                $this->visit($oid);
+            }
+        }
+
+        return $this->sortResult;
+    }
+
+    private function visit(int $oid): void
+    {
+        if ($this->states[$oid] === self::IN_PROGRESS) {
+            // This node is already on the current DFS stack. We've found a cycle!
+            throw new CycleDetectedException($this->nodes[$oid]);
+        }
+
+        if ($this->states[$oid] === self::VISITED) {
+            // We've reached a node that we've already seen, including all
+            // other nodes that are reachable from here. We're done here, return.
+            return;
+        }
+
+        $this->states[$oid] = self::IN_PROGRESS;
+
+        // Continue the DFS downwards the edge list
+        foreach ($this->edges[$oid] as $adjacentId => $optional) {
+            try {
+                $this->visit($adjacentId);
+            } catch (CycleDetectedException $exception) {
+                if ($exception->isCycleCollected()) {
+                    // There is a complete cycle downstream of the current node. We cannot
+                    // do anything about that anymore.
+                    throw $exception;
+                }
+
+                if ($optional) {
+                    // The current edge is part of a cycle, but it is optional and the closest
+                    // such edge while backtracking. Break the cycle here by skipping the edge
+                    // and continuing with the next one.
+                    continue;
+                }
+
+                // We have found a cycle and cannot break it at $edge. Best we can do
+                // is to retreat from the current vertex, hoping that somewhere up the
+                // stack this can be salvaged.
+                $this->states[$oid] = self::NOT_VISITED;
+                $exception->addToCycle($this->nodes[$oid]);
+
+                throw $exception;
+            }
+        }
+
+        // We have traversed all edges and visited all other nodes reachable from here.
+        // So we're done with this vertex as well.
+
+        $this->states[$oid] = self::VISITED;
+        array_unshift($this->sortResult, $this->nodes[$oid]);
+    }
+}
diff --git a/lib/Doctrine/ORM/Internal/TopologicalSort/CycleDetectedException.php b/lib/Doctrine/ORM/Internal/TopologicalSort/CycleDetectedException.php
@@ -0,0 +1,55 @@
+<?php
+
+declare(strict_types=1);
+
+namespace Doctrine\ORM\Internal\TopologicalSort;
+
+use RuntimeException;
+
+use function array_unshift;
+
+class CycleDetectedException extends RuntimeException
+{
+    /** @var list<object> */
+    private $cycle;
+
+    /** @var object */
+    private $startNode;
+
+    /**
+     * Do we have the complete cycle collected?
+     *
+     * @var bool
+     */
+    private $cycleCollected = false;
+
+    /** @param object $startNode */
+    public function __construct($startNode)
+    {
+        parent::__construct('A cycle has been detected, so a topological sort is not possible. The getCycle() method provides the list of nodes that form the cycle.');
+
+        $this->startNode = $startNode;
+        $this->cycle     = [$startNode];
+    }
+
+    /** @return list<object> */
+    public function getCycle(): array
+    {
+        return $this->cycle;
+    }
+
+    /** @param object $node */
+    public function addToCycle($node): void
+    {
+        array_unshift($this->cycle, $node);
+
+        if ($node === $this->startNode) {
+            $this->cycleCollected = true;
+        }
+    }
+
+    public function isCycleCollected(): bool
+    {
+        return $this->cycleCollected;
+    }
+}