CommitOrderCalculator::visit() - Code Metrics - Inspection of "commit order must consider non-nullability of join..." - doctrine/orm - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — 2.6 (#7180)

by Ben

created 2018-04-14 16:35 UTC

CommitOrderCalculator::visit() C

↳ Parent: CommitOrderCalculator

Complexity

Conditions	8
Paths	12

Size

Total Lines	30
Code Lines	17

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	16
CRAP Score	8.0877

Importance

Changes

Metric	Value
cc	8
eloc	17
nc	12
nop	1
dl	0
loc	30
ccs	16
cts	18
cp	0.8889
crap	8.0877
rs	5.3846
c	0
b	0
f	0

<?php

/*
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This software consists of voluntary contributions made by many individuals
 * and is licensed under the MIT license. For more information, see
 * <http://www.doctrine-project.org>.
 */

namespace Doctrine\ORM\Internal;

/**
 * CommitOrderCalculator implements topological sorting, which is an ordering
 * algorithm for directed graphs (DG) and/or directed acyclic graphs (DAG) by
 * 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).
 *
 * @since  2.0
 * @author Guilherme Blanco <[email protected]>
 * @author Roman Borschel <[email protected]>
 */
class CommitOrderCalculator
{
    const NOT_VISITED = 0;
    const IN_PROGRESS = 1;
    const VISITED     = 2;

    /**
     * Matrix of nodes (aka. vertex).
     * Keys are provided hashes and values are the node definition objects.
     *
     * The node state definition contains the following properties:
     *
     * - <b>state</b> (integer)
     * Whether the node is NOT_VISITED or IN_PROGRESS
     *
     * - <b>value</b> (object)
     * Actual node value
     *
     * - <b>dependencyList</b> (array<string>)
     * Map of node dependencies defined as hashes.
     *
     * @var array<\stdClass>
     */
    private $nodeList = [];

    /**
     * Volatile variable holding calculated nodes during sorting process.
     *
     * @var array
     */
    private $sortedNodeList = [];

    /**
     * Checks for node (vertex) existence in graph.
     *
     * @param string $hash
     *
     * @return boolean
     */
    public function hasNode($hash)
    {
        return isset($this->nodeList[$hash]);
    }

    /**
     * Adds a new node (vertex) to the graph, assigning its hash and value.
     *
     * @param string $hash
     * @param object $node
     *
     * @return void
     */
    public function addNode($hash, $node)
    {
        $vertex = new \stdClass();

        $vertex->hash           = $hash;
        $vertex->state          = self::NOT_VISITED;
        $vertex->value          = $node;
        $vertex->dependencyList = [];

        $this->nodeList[$hash] = $vertex;
    }

    /**
     * Adds a new dependency (edge) to the graph using their hashes.
     *
     * @param string  $fromHash
     * @param string  $toHash
     * @param integer $weight
     *
     * @return void
     */
    public function addDependency($fromHash, $toHash, $weight)
    {
        if (isset($this->nodeList[$toHash]->dependencyList[$fromHash])) {
            $cycleWeight = $this->nodeList[$toHash]->dependencyList[$fromHash]->weight;
            if ($cycleWeight > $weight) {
                return;
            }
            if ($cycleWeight < $weight) {
                unset($this->nodeList[$toHash]->dependencyList[$fromHash]);
            }
        }

        $vertex = $this->nodeList[$fromHash];
        $edge   = new \stdClass();

        $edge->from   = $fromHash;
        $edge->to     = $toHash;
        $edge->weight = $weight;

        $vertex->dependencyList[$toHash] = $edge;
    }

    /**
     * Return a valid order list of all current nodes.
     * The desired topological sorting is the reverse post order of these searches.
     *
     * {@internal Highly performance-sensitive method.}
     *
     * @return array
     */
    public function sort()
    {
        foreach ($this->nodeList as $vertex) {
            if ($vertex->state !== self::NOT_VISITED) {
                continue;
            }

            $this->visit($vertex);
        }

        $sortedList = $this->sortedNodeList;

        $this->nodeList       = [];
        $this->sortedNodeList = [];

        return array_reverse($sortedList);
    }

    /**
     * Visit a given node definition for reordering.
     *
     * {@internal Highly performance-sensitive method.}
     *
     * @param \stdClass $vertex
     */
    private function visit($vertex)
    {
        $vertex->state = self::IN_PROGRESS;

        foreach ($vertex->dependencyList as $edge) {
            $adjacentVertex = $this->nodeList[$edge->to];

            switch ($adjacentVertex->state) {
                case self::VISITED:
                    // Do nothing, since node was already visited
                    break;

                case self::IN_PROGRESS:
                    if (isset($adjacentVertex->dependencyList[$vertex->hash]) &&
                        $adjacentVertex->dependencyList[$vertex->hash]->weight < $edge->weight) {
                        $adjacentVertex->state = self::VISITED;

                        $this->sortedNodeList[] = $adjacentVertex->value;
                    }
                    break;

                case self::NOT_VISITED:
                    $this->visit($adjacentVertex);
            }
        }

        if ($vertex->state !== self::VISITED) {
            $vertex->state = self::VISITED;

            $this->sortedNodeList[] = $vertex->value;
        }
    }
}


1		<?php
2
3		/*
4		* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
5		* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
6		* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
7		* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
8		* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
9		* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
10		* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
11		* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
12		* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
13		* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
14		* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
15		*
16		* This software consists of voluntary contributions made by many individuals
17		* and is licensed under the MIT license. For more information, see
18		* <http://www.doctrine-project.org>.
19		*/
20
21		namespace Doctrine\ORM\Internal;
22
23		/**
24		* CommitOrderCalculator implements topological sorting, which is an ordering
25		* algorithm for directed graphs (DG) and/or directed acyclic graphs (DAG) by
26		* using a depth-first searching (DFS) to traverse the graph built in memory.
27		* This algorithm have a linear running time based on nodes (V) and dependency
28		* between the nodes (E), resulting in a computational complexity of O(V + E).
29		*
30		* @since 2.0
31		* @author Guilherme Blanco <[email protected]>
32		* @author Roman Borschel <[email protected]>
33		*/
34		class CommitOrderCalculator
35		{
36		const NOT_VISITED = 0;
37		const IN_PROGRESS = 1;
38		const VISITED = 2;
39
40		/**
41		* Matrix of nodes (aka. vertex).
42		* Keys are provided hashes and values are the node definition objects.
43		*
44		* The node state definition contains the following properties:
45		*
46		* - <b>state</b> (integer)
47		* Whether the node is NOT_VISITED or IN_PROGRESS
48		*
49		* - <b>value</b> (object)
50		* Actual node value
51		*
52		* - <b>dependencyList</b> (array<string>)
53		* Map of node dependencies defined as hashes.
54		*
55		* @var array<\stdClass>
56		*/
57		private $nodeList = [];
58
59		/**
60		* Volatile variable holding calculated nodes during sorting process.
61		*
62		* @var array
63		*/
64		private $sortedNodeList = [];
65
66		/**
67		* Checks for node (vertex) existence in graph.
68		*
69		* @param string $hash
70		*
71		* @return boolean
72		*/
73	1075	public function hasNode($hash)
74		{
75	1075	return isset($this->nodeList[$hash]);
76		}
77
78		/**
79		* Adds a new node (vertex) to the graph, assigning its hash and value.
80		*
81		* @param string $hash
82		* @param object $node
83		*
84		* @return void
85		*/
86	1079	public function addNode($hash, $node)
87		{
88	1079	$vertex = new \stdClass();
89
90	1079	$vertex->hash = $hash;
91	1079	$vertex->state = self::NOT_VISITED;
92	1079	$vertex->value = $node;
93	1079	$vertex->dependencyList = [];
94
95	1079	$this->nodeList[$hash] = $vertex;
96	1079	}
97
98		/**
99		* Adds a new dependency (edge) to the graph using their hashes.
100		*
101		* @param string $fromHash
102		* @param string $toHash
103		* @param integer $weight
104		*
105		* @return void
106		*/
107	888	public function addDependency($fromHash, $toHash, $weight)
108		{
109	888	if (isset($this->nodeList[$toHash]->dependencyList[$fromHash])) {
110	236	$cycleWeight = $this->nodeList[$toHash]->dependencyList[$fromHash]->weight;
111	236	if ($cycleWeight > $weight) {
112	77	return;
113		}
114	233	if ($cycleWeight < $weight) {
115	212	unset($this->nodeList[$toHash]->dependencyList[$fromHash]);
116		}
117		}
118
119	888	$vertex = $this->nodeList[$fromHash];
120	888	$edge = new \stdClass();
121
122	888	$edge->from = $fromHash;
123	888	$edge->to = $toHash;
124	888	$edge->weight = $weight;
125
126	888	$vertex->dependencyList[$toHash] = $edge;
127	888	}
128
129		/**
130		* Return a valid order list of all current nodes.
131		* The desired topological sorting is the reverse post order of these searches.
132		*
133		* {@internal Highly performance-sensitive method.}
134		*
135		* @return array
136		*/
137	1079	public function sort()
138		{
139	1079	foreach ($this->nodeList as $vertex) {
140	1079	if ($vertex->state !== self::NOT_VISITED) {
141	550	continue;
142		}
143
144	1079	$this->visit($vertex);
145		}
146
147	1079	$sortedList = $this->sortedNodeList;
148
149	1079	$this->nodeList = [];
150	1079	$this->sortedNodeList = [];
151
152	1079	return array_reverse($sortedList);
153		}
154
155		/**
156		* Visit a given node definition for reordering.
157		*
158		* {@internal Highly performance-sensitive method.}
159		*
160		* @param \stdClass $vertex
161		*/
162	1079	private function visit($vertex)
163		{
164	1079	$vertex->state = self::IN_PROGRESS;
165
166	1079	foreach ($vertex->dependencyList as $edge) {
167	888	$adjacentVertex = $this->nodeList[$edge->to];
168
169	888	switch ($adjacentVertex->state) {
170	888	case self::VISITED:
171		// Do nothing, since node was already visited
172	768	break;
173
174	590	case self::IN_PROGRESS:
175	280	if (isset($adjacentVertex->dependencyList[$vertex->hash]) &&
176	280	$adjacentVertex->dependencyList[$vertex->hash]->weight < $edge->weight) {
177		$adjacentVertex->state = self::VISITED;
178
179		$this->sortedNodeList[] = $adjacentVertex->value;
180		}
181	280	break;
182
183	550	case self::NOT_VISITED:
184	888	$this->visit($adjacentVertex);
185		}
186		}
187
188	1079	if ($vertex->state !== self::VISITED) {
189	1079	$vertex->state = self::VISITED;
190
191	1079	$this->sortedNodeList[] = $vertex->value;
192		}
193	1079	}
194		}
195

doctrine / orm

Pull Request — 2.6 (#7180)

CommitOrderCalculator::visit() C

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like