vendor/doctrine/orm/lib/Doctrine/ORM/Internal/CommitOrderCalculator.php

   1 <?php
   2 /*
   3  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   4  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   5  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   6  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   7  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   8  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   9  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  10  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  11  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  12  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  13  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  14  *
  15  * This software consists of voluntary contributions made by many individuals
  16  * and is licensed under the MIT license. For more information, see
  17  * <http://www.doctrine-project.org>.
  18  */
  19
  20 namespace Doctrine\ORM\Internal;
  21
  22 /**
  23  * The CommitOrderCalculator is used by the UnitOfWork to sort out the
  24  * correct order in which changes to entities need to be persisted.
  25  *
  26  * @since       2.0
  27  * @author      Roman Borschel <roman@code-factory.org>
  28  * @author      Guilherme Blanco <guilhermeblanco@hotmail.com>
  29  */
  30 class CommitOrderCalculator
  31 {
  32     const NOT_VISITED = 1;
  33     const IN_PROGRESS = 2;
  34     const VISITED = 3;
  35
  36     private $_nodeStates = array();
  37     private $_classes = array(); // The nodes to sort
  38     private $_relatedClasses = array();
  39     private $_sorted = array();
  40
  41     /**
  42      * Clears the current graph.
  43      *
  44      * @return void
  45      */
  46     public function clear()
  47     {
  48         $this->_classes =
  49         $this->_relatedClasses = array();
  50     }
  51
  52     /**
  53      * Gets a valid commit order for all current nodes.
  54      *
  55      * Uses a depth-first search (DFS) to traverse the graph.
  56      * The desired topological sorting is the reverse postorder of these searches.
  57      *
  58      * @return array The list of ordered classes.
  59      */
  60     public function getCommitOrder()
  61     {
  62         // Check whether we need to do anything. 0 or 1 node is easy.
  63         $nodeCount = count($this->_classes);
  64
  65         if ($nodeCount <= 1) {
  66             return ($nodeCount == 1) ? array_values($this->_classes) : array();
  67         }
  68
  69         // Init
  70         foreach ($this->_classes as $node) {
  71             $this->_nodeStates[$node->name] = self::NOT_VISITED;
  72         }
  73
  74         // Go
  75         foreach ($this->_classes as $node) {
  76             if ($this->_nodeStates[$node->name] == self::NOT_VISITED) {
  77                 $this->_visitNode($node);
  78             }
  79         }
  80
  81         $sorted = array_reverse($this->_sorted);
  82
  83         $this->_sorted = $this->_nodeStates = array();
  84
  85         return $sorted;
  86     }
  87
  88     private function _visitNode($node)
  89     {
  90         $this->_nodeStates[$node->name] = self::IN_PROGRESS;
  91
  92         if (isset($this->_relatedClasses[$node->name])) {
  93             foreach ($this->_relatedClasses[$node->name] as $relatedNode) {
  94                 if ($this->_nodeStates[$relatedNode->name] == self::NOT_VISITED) {
  95                     $this->_visitNode($relatedNode);
  96                 }
  97             }
  98         }
  99
 100         $this->_nodeStates[$node->name] = self::VISITED;
 101         $this->_sorted[] = $node;
 102     }
 103
 104     public function addDependency($fromClass, $toClass)
 105     {
 106         $this->_relatedClasses[$fromClass->name][] = $toClass;
 107     }
 108
 109     public function hasClass($className)
 110     {
 111         return isset($this->_classes[$className]);
 112     }
 113
 114     public function addClass($class)
 115     {
 116         $this->_classes[$class->name] = $class;
 117     }
 118 }