Tree::genOrderCheckInfiniteLoop() - Code Metrics - bulton-fr/dependency-tree - Measure and Improve Code Quality continuously with Scrutinizer

Tree::genOrderCheckInfiniteLoop() B
last analyzed 2018-08-21 14:53 UTC

↳ Parent: Tree

Complexity

Conditions	8
Paths	16

Size

Total Lines	39
Code Lines	23

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	8
eloc	23
nc	16
nop	1
dl	0
loc	39
rs	8.4444
c	0
b	0
f	0

<?php

namespace bultonFr\DependencyTree;

use \Exception;

class Tree
{
    /**
     * @var array $dependenciesInfos : List of dependency with there infos;
     */
    protected $dependenciesInfos = [];
    
    /**
     * @var array $listDepends : List the depends of each dependancy
     */
    protected $listDepends = [];
    
    /**
     * @var array $dependenciesPositions : List of position in the tree for
     *                                      each dependancy
     */
    protected $dependenciesPositions = [];
    
    /**
     * @var array $tree : The generate tree
     */
    protected $tree = [];
    
    /**
     * @var \stdClass $genOrderSecurityLoop : Informations about dependency
     *  during the generateOrder.
     *  It's a security against infinite loop.
     */
    protected $genOrderSecurityLoop;

    /**
     * Add a dependency to system
     * 
     * @param string $name         : Dependency's name
     * @param int    $order        : Order to load dependency
     * @param array  $dependencies : All dependencies for this dependency
     * 
     * @throws Exception : If dependency already declared
     * 
     * @return Tree : Current instance
     */
    public function addDependency($name, $order = 0, $dependencies = [])
    {
        //Check if dependency is already declared.
        if (isset($this->dependenciesInfos[$name])) {
            throw new Exception('Dependency '.$name.' already declared.');
        }
        
        if (!is_array($dependencies)) {

            throw new Exception('Dependencies must be passed in a array.');
        }

        $dependencyInfos        = new \stdClass;
        $dependencyInfos->order = $order;
        $dependencyInfos->dependencies = $dependencies;

        $this->dependenciesInfos[$name] = $dependencyInfos;
        
        //Create the key for list of depends if she doesn't exist
        if (!isset($this->listDepends[$name])) {
            $this->listDepends[$name] = [];
        }
        
        //Generate the list of depends
        if ($dependencies !== []) {
            foreach ($dependencies as $dependencyName) {
                if(!isset($this->listDepends[$dependencyName])) {
                    $this->listDepends[$dependencyName] = [];
                }
                
                $this->listDepends[$dependencyName][] = $name;
            }
        }
        
        return $this;
    }

    /**
     * Generate the tree
     * 
     * @return array
     */
    public function generateTree()
    {
        //Read all depencies declared and positioned each dependency on
        //the tree with they order value
        foreach ($this->dependenciesInfos as $name => $dependency) {
            $order = $dependency->order;
            
            //If the line for this order not exist
            if (!isset($this->tree[$order])) {
                $this->tree[$order] = [];
            }
            
            //Add to the tree and save the current position
            $this->tree[$order][]               = $name;
            $this->dependenciesPositions[$name] = [$order];
        }
        
        //Read the tree and check depends of each package.
        //Move some package in the tree if need for depends.
        foreach ($this->tree as $dependencies) {
            foreach ($dependencies as $dependencyName) {
                $this->checkDepend($dependencyName);
            }
        }
        
        //Sort by key. Some keys should be unorganized
        ksort($this->tree);
        
        return $this->tree;
    }

    /**
     * Check if all depends is correctly spoted in the tree
     * 
     * @param string $dependencyName : The name of the dependency for which
     *                                  check depends
     * 
     * @return void
     */
    protected function checkDepend($dependencyName)
    {
        $listDepends     = $this->listDepends[$dependencyName];
        $dependencyInfos = $this->dependenciesInfos[$dependencyName];
        $order           = $dependencyInfos->order;

        //No depends :)
        if ($listDepends === []) {
            return;
        }

        //Read all depends and check if they correctly spoted.
        //If not, call the method to move the depend read.
        foreach ($listDepends as $dependencyName) {

            $dependencyPos   = $this->dependenciesPositions[$dependencyName];
            $dependencyOrder = $dependencyPos[0];

            if ($dependencyOrder < $order) {
                $this->moveDepend($dependencyName, $order);
            }
        }
    }

    /**
     * Move a depend to a new position in the tree
     * 
     * @param string $dependencyName : The dependency name
     * @param int    $newOrder       : The new position in the tree
     * 
     * @return void
     */
    protected function moveDepend($dependencyName, $newOrder)
    {
        //Get old position in the tree for this dependency
        $dependencyInfos = $this->dependenciesInfos[$dependencyName];
        $oldOrder        = $dependencyInfos->order;

        //If the new position not already exist in the tree
        if (!isset($this->tree[$newOrder])) {
            $this->tree[$newOrder] = [];
        }

        //Add dependency to this new position
        $this->tree[$newOrder][] = $dependencyName;

        //Search the key corresponding to the old position in the array tree
        $oldKey = array_search($dependencyName, $this->tree[$oldOrder]);
        //Remove dependency from this old position
        unset($this->tree[$oldOrder][$oldKey]);

        //Call checkDepend for check all depends of this dependency
        $this->checkDepend($dependencyName);
    }
    
    /**
     * Generate the order position from the depends of each dependencies
     * 
     * First we generate a reversed tree from depends
     * Reverse the tree for have a tree in the correct depends order
     * And update the order value of each dependency with the tree of depends
     * 
     * @return void
     */
    public function generateOrderFromDependencies()
    {
        $this->initGenOrderSecurityLoop(0);
        $this->tree = [[]]; //generate a empty tree
        
        //Read all depends of each dependencies
        foreach ($this->listDepends as $dependencyName => $depends) {
        
            //If the dependency in the depend's list is declared on this tree.
            if (!isset($this->dependenciesInfos[$dependencyName])) {
                continue;
            }
            
            //If the package have depends, we continue
            if ($depends !== []) {
                continue;
            }
            
            //Add the dependency to the first line of tree
            $this->tree[0][$dependencyName] = $dependencyName;
            
            //And generate the order for this depends
            $this->genOrderSecurityLoopAddDepend($dependencyName, 0);
            $this->generateOrderForADependency($dependencyName, 0);
        }
        
        //Here, $this->tree have a reversed array of depends
        //So we reverse the array to have the array of depends
        //in the correct order
        $this->tree = array_reverse($this->tree);
        
        //Some line could be empty because the dependency is in another tree
        //So we define the order manually.
        $treeOrder = 0;
        
        //Read the tree for update the order of each dependency
        foreach ($this->tree as $dependencies) {
            if ($dependencies === []) {
                continue;
            }
            
            foreach ($dependencies as $dependencyName) {
                $dependencyInfos = &$this->dependenciesInfos[$dependencyName];
                
                //If the order has not be already updated
                if ($dependencyInfos->order > -1) {
                    continue;
                }
                
                $dependencyInfos->order = $treeOrder;
            }
            
            $treeOrder++;
        }
        
        //Reinit the tree for use the main system of tree generator.
        $this->tree = [];
    }
    
    /**
     * Define the order of all the dependencies of dependency
     * 
     * @param string $dependencyName : The name of dependency for which we
     *                                  read the dependencies
     * @param int    $currentOrder   : The current order of the dependency
     * 
     * @return void
     */
    protected function generateOrderForADependency($dependencyName, $currentOrder)
    {
        $depends = $this->dependenciesInfos[$dependencyName]->dependencies;
        if ($depends === []) {
            return;
        }
        
        $order = $currentOrder+1;
        if (!isset($this->tree[$order])) {
            $this->tree[$order] = [];
        }
        
        foreach ($depends as $dependName) {
            //If the dependency of the dependency is in a other tree
            if (!isset($this->dependenciesInfos[$dependName])) {
                continue;
            }
            
            //Infinite dependency loop security
            $this->checkReinitGenOrderSecurityLoop($order);
            $this->genOrderCheckInfiniteLoop($dependName);
            $this->tree[$order][$dependName] = $dependName;
            
            $this->genOrderSecurityLoopAddDepend($dependName, $order);
            $this->generateOrderForADependency(
                $dependName,
                $order
            );
        }
    }
    
    /**
     * Add a dependency into list used by security infinite depend loop.
     * 
     * @param string $dependencyName Dependency name
     * @param int    $order          The current order of the dependency
     * 
     * @return void
     */
    protected function genOrderSecurityLoopAddDepend($dependencyName, $order)
    {
        $this->checkReinitGenOrderSecurityLoop($order);
        
        $this->genOrderSecurityLoop->order  = $order;
        $this->genOrderSecurityLoop->list[] = (object) [
            'dependName' => $dependencyName,
            'dependList' => []
        ];
    }
    
    /**
     * Check if we reinitialize the list used against dependency infinite loop
     * 
     * @param int $order The current order of the dependency
     * 
     * @return void
     */
    protected function checkReinitGenOrderSecurityLoop($order)
    {
        if ($order <= $this->genOrderSecurityLoop->order) {
            $this->initGenOrderSecurityLoop($order);
        }
    }
    
    /**
     * (re)Initialize the list used against dependency infinite loop
     * 
     * @param int $order The current order of the dependency
     * 
     * @return void
     */
    protected function initGenOrderSecurityLoop($order)
    {
        $this->genOrderSecurityLoop = (object) [
            'order' => $order,
            'list'  => []
        ];
    }
    
    /**
     * Check if we allow to moved a dependency in the tree to protect
     * against infine loop.
     * It's for the case where a dependency is moved to be loaded before an
     * another, but this another dependency depend on the first package
     * who asked to be moved.
     * So the system try to moved packages at the infine. We protect this.
     * 
     * @see Issue #4 on the github repo.
     * 
     * @param string $checkDependName : The name of dependency
     * 
     * @return void
     * 
     * @throws Exception The infinite loop security.
     */
    protected function genOrderCheckInfiniteLoop($checkDependName)
    {
        $runException = false;
        foreach ($this->genOrderSecurityLoop->list as &$checkInfos) {
            if ($checkInfos->dependList === []) {
                $checkInfos->dependList[] = $checkDependName;
                continue;
            }
            
            if (
                $checkInfos->dependList !== []
                && $checkInfos->dependName !== $checkDependName
            ) {
                $checkInfos->dependList[] = $checkDependName;
                continue;
            }
            
            $runException = true;
            break;
        }
        
        if ($runException === false) {
            unset($checkInfos); //Kill ref
            return;
        }
        
        //Package is already moved for the original dependency : Loop error
        $loopInfos = '';
        foreach ($checkInfos->dependList as $packageName) {

            if ($loopInfos !== '') {
                $loopInfos .= ', ';
            }
            
            $loopInfos .= $packageName;
        }
        
        throw new Exception(
            'Infinite depends loop find for package '.$checkInfos->dependName
            .' - Loop info : '.$loopInfos
        );
    }
}


1			<?php
2
3			namespace bultonFr\DependencyTree;
4
5			use \Exception;
6
7			class Tree
8			{
9			/**
10			* @var array $dependenciesInfos : List of dependency with there infos;
11			*/
12			protected $dependenciesInfos = [];
13
14			/**
15			* @var array $listDepends : List the depends of each dependancy
16			*/
17			protected $listDepends = [];
18
19			/**
20			* @var array $dependenciesPositions : List of position in the tree for
21			* each dependancy
22			*/
23			protected $dependenciesPositions = [];
24
25			/**
26			* @var array $tree : The generate tree
27			*/
28			protected $tree = [];
29
30			/**
31			* @var \stdClass $genOrderSecurityLoop : Informations about dependency
32			* during the generateOrder.
33			* It's a security against infinite loop.
34			*/
35			protected $genOrderSecurityLoop;
36
37			/**
38			* Add a dependency to system
39			*
40			* @param string $name : Dependency's name
41			* @param int $order : Order to load dependency
42			* @param array $dependencies : All dependencies for this dependency
43			*
44			* @throws Exception : If dependency already declared
45			*
46			* @return Tree : Current instance
47			*/
48			public function addDependency($name, $order = 0, $dependencies = [])
49			{
50			//Check if dependency is already declared.
51			if (isset($this->dependenciesInfos[$name])) {
52			throw new Exception('Dependency '.$name.' already declared.');
53			}
54
55			if (!is_array($dependencies)) {
			0 ignored issues – show introduced 2018-08-13 14:48 UTC by Report Bug Copy Issue Report The condition `is_array($dependencies)` is always `true`. Loading history...
56			throw new Exception('Dependencies must be passed in a array.');
57			}
58
59			$dependencyInfos = new \stdClass;
60			$dependencyInfos->order = $order;
61			$dependencyInfos->dependencies = $dependencies;
62
63			$this->dependenciesInfos[$name] = $dependencyInfos;
64
65			//Create the key for list of depends if she doesn't exist
66			if (!isset($this->listDepends[$name])) {
67			$this->listDepends[$name] = [];
68			}
69
70			//Generate the list of depends
71			if ($dependencies !== []) {
72			foreach ($dependencies as $dependencyName) {
73			if(!isset($this->listDepends[$dependencyName])) {
74			$this->listDepends[$dependencyName] = [];
75			}
76
77			$this->listDepends[$dependencyName][] = $name;
78			}
79			}
80
81			return $this;
82			}
83
84			/**
85			* Generate the tree
86			*
87			* @return array
88			*/
89			public function generateTree()
90			{
91			//Read all depencies declared and positioned each dependency on
92			//the tree with they order value
93			foreach ($this->dependenciesInfos as $name => $dependency) {
94			$order = $dependency->order;
95
96			//If the line for this order not exist
97			if (!isset($this->tree[$order])) {
98			$this->tree[$order] = [];
99			}
100
101			//Add to the tree and save the current position
102			$this->tree[$order][] = $name;
103			$this->dependenciesPositions[$name] = [$order];
104			}
105
106			//Read the tree and check depends of each package.
107			//Move some package in the tree if need for depends.
108			foreach ($this->tree as $dependencies) {
109			foreach ($dependencies as $dependencyName) {
110			$this->checkDepend($dependencyName);
111			}
112			}
113
114			//Sort by key. Some keys should be unorganized
115			ksort($this->tree);
116
117			return $this->tree;
118			}
119
120			/**
121			* Check if all depends is correctly spoted in the tree
122			*
123			* @param string $dependencyName : The name of the dependency for which
124			* check depends
125			*
126			* @return void
127			*/
128			protected function checkDepend($dependencyName)
129			{
130			$listDepends = $this->listDepends[$dependencyName];
131			$dependencyInfos = $this->dependenciesInfos[$dependencyName];
132			$order = $dependencyInfos->order;
133
134			//No depends :)
135			if ($listDepends === []) {
136			return;
137			}
138
139			//Read all depends and check if they correctly spoted.
140			//If not, call the method to move the depend read.
141			foreach ($listDepends as $dependencyName) {
			0 ignored issues – show introduced 2018-08-13 14:48 UTC by Report Bug Copy Issue Report `$dependencyName` is overwriting one of the parameters of this function. Loading history...
142			$dependencyPos = $this->dependenciesPositions[$dependencyName];
143			$dependencyOrder = $dependencyPos[0];
144
145			if ($dependencyOrder < $order) {
146			$this->moveDepend($dependencyName, $order);
147			}
148			}
149			}
150
151			/**
152			* Move a depend to a new position in the tree
153			*
154			* @param string $dependencyName : The dependency name
155			* @param int $newOrder : The new position in the tree
156			*
157			* @return void
158			*/
159			protected function moveDepend($dependencyName, $newOrder)
160			{
161			//Get old position in the tree for this dependency
162			$dependencyInfos = $this->dependenciesInfos[$dependencyName];
163			$oldOrder = $dependencyInfos->order;
164
165			//If the new position not already exist in the tree
166			if (!isset($this->tree[$newOrder])) {
167			$this->tree[$newOrder] = [];
168			}
169
170			//Add dependency to this new position
171			$this->tree[$newOrder][] = $dependencyName;
172
173			//Search the key corresponding to the old position in the array tree
174			$oldKey = array_search($dependencyName, $this->tree[$oldOrder]);
175			//Remove dependency from this old position
176			unset($this->tree[$oldOrder][$oldKey]);
177
178			//Call checkDepend for check all depends of this dependency
179			$this->checkDepend($dependencyName);
180			}
181
182			/**
183			* Generate the order position from the depends of each dependencies
184			*
185			* First we generate a reversed tree from depends
186			* Reverse the tree for have a tree in the correct depends order
187			* And update the order value of each dependency with the tree of depends
188			*
189			* @return void
190			*/
191			public function generateOrderFromDependencies()
192			{
193			$this->initGenOrderSecurityLoop(0);
194			$this->tree = [[]]; //generate a empty tree
195
196			//Read all depends of each dependencies
197			foreach ($this->listDepends as $dependencyName => $depends) {
198
199			//If the dependency in the depend's list is declared on this tree.
200			if (!isset($this->dependenciesInfos[$dependencyName])) {
201			continue;
202			}
203
204			//If the package have depends, we continue
205			if ($depends !== []) {
206			continue;
207			}
208
209			//Add the dependency to the first line of tree
210			$this->tree[0][$dependencyName] = $dependencyName;
211
212			//And generate the order for this depends
213			$this->genOrderSecurityLoopAddDepend($dependencyName, 0);
214			$this->generateOrderForADependency($dependencyName, 0);
215			}
216
217			//Here, $this->tree have a reversed array of depends
218			//So we reverse the array to have the array of depends
219			//in the correct order
220			$this->tree = array_reverse($this->tree);
221
222			//Some line could be empty because the dependency is in another tree
223			//So we define the order manually.
224			$treeOrder = 0;
225
226			//Read the tree for update the order of each dependency
227			foreach ($this->tree as $dependencies) {
228			if ($dependencies === []) {
229			continue;
230			}
231
232			foreach ($dependencies as $dependencyName) {
233			$dependencyInfos = &$this->dependenciesInfos[$dependencyName];
234
235			//If the order has not be already updated
236			if ($dependencyInfos->order > -1) {
237			continue;
238			}
239
240			$dependencyInfos->order = $treeOrder;
241			}
242
243			$treeOrder++;
244			}
245
246			//Reinit the tree for use the main system of tree generator.
247			$this->tree = [];
248			}
249
250			/**
251			* Define the order of all the dependencies of dependency
252			*
253			* @param string $dependencyName : The name of dependency for which we
254			* read the dependencies
255			* @param int $currentOrder : The current order of the dependency
256			*
257			* @return void
258			*/
259			protected function generateOrderForADependency($dependencyName, $currentOrder)
260			{
261			$depends = $this->dependenciesInfos[$dependencyName]->dependencies;
262			if ($depends === []) {
263			return;
264			}
265
266			$order = $currentOrder+1;
267			if (!isset($this->tree[$order])) {
268			$this->tree[$order] = [];
269			}
270
271			foreach ($depends as $dependName) {
272			//If the dependency of the dependency is in a other tree
273			if (!isset($this->dependenciesInfos[$dependName])) {
274			continue;
275			}
276
277			//Infinite dependency loop security
278			$this->checkReinitGenOrderSecurityLoop($order);
279			$this->genOrderCheckInfiniteLoop($dependName);
280			$this->tree[$order][$dependName] = $dependName;
281
282			$this->genOrderSecurityLoopAddDepend($dependName, $order);
283			$this->generateOrderForADependency(
284			$dependName,
285			$order
286			);
287			}
288			}
289
290			/**
291			* Add a dependency into list used by security infinite depend loop.
292			*
293			* @param string $dependencyName Dependency name
294			* @param int $order The current order of the dependency
295			*
296			* @return void
297			*/
298			protected function genOrderSecurityLoopAddDepend($dependencyName, $order)
299			{
300			$this->checkReinitGenOrderSecurityLoop($order);
301
302			$this->genOrderSecurityLoop->order = $order;
303			$this->genOrderSecurityLoop->list[] = (object) [
304			'dependName' => $dependencyName,
305			'dependList' => []
306			];
307			}
308
309			/**
310			* Check if we reinitialize the list used against dependency infinite loop
311			*
312			* @param int $order The current order of the dependency
313			*
314			* @return void
315			*/
316			protected function checkReinitGenOrderSecurityLoop($order)
317			{
318			if ($order <= $this->genOrderSecurityLoop->order) {
319			$this->initGenOrderSecurityLoop($order);
320			}
321			}
322
323			/**
324			* (re)Initialize the list used against dependency infinite loop
325			*
326			* @param int $order The current order of the dependency
327			*
328			* @return void
329			*/
330			protected function initGenOrderSecurityLoop($order)
331			{
332			$this->genOrderSecurityLoop = (object) [
333			'order' => $order,
334			'list' => []
335			];
336			}
337
338			/**
339			* Check if we allow to moved a dependency in the tree to protect
340			* against infine loop.
341			* It's for the case where a dependency is moved to be loaded before an
342			* another, but this another dependency depend on the first package
343			* who asked to be moved.
344			* So the system try to moved packages at the infine. We protect this.
345			*
346			* @see Issue #4 on the github repo.
347			*
348			* @param string $checkDependName : The name of dependency
349			*
350			* @return void
351			*
352			* @throws Exception The infinite loop security.
353			*/
354			protected function genOrderCheckInfiniteLoop($checkDependName)
355			{
356			$runException = false;
357			foreach ($this->genOrderSecurityLoop->list as &$checkInfos) {
358			if ($checkInfos->dependList === []) {
359			$checkInfos->dependList[] = $checkDependName;
360			continue;
361			}
362
363			if (
364			$checkInfos->dependList !== []
365			&& $checkInfos->dependName !== $checkDependName
366			) {
367			$checkInfos->dependList[] = $checkDependName;
368			continue;
369			}
370
371			$runException = true;
372			break;
373			}
374
375			if ($runException === false) {
376			unset($checkInfos); //Kill ref
377			return;
378			}
379
380			//Package is already moved for the original dependency : Loop error
381			$loopInfos = '';
382			foreach ($checkInfos->dependList as $packageName) {
			0 ignored issues – show Comprehensibility Best Practice introduced 2018-08-13 14:48 UTC by Report Bug Copy Issue Report The variable `$checkInfos` seems to be defined by a `foreach` iteration on line `357`. Are you sure the iterator is never empty, otherwise this variable is not defined? Loading history...
383			if ($loopInfos !== '') {
384			$loopInfos .= ', ';
385			}
386
387			$loopInfos .= $packageName;
388			}
389
390			throw new Exception(
391			'Infinite depends loop find for package '.$checkInfos->dependName
392			.' - Loop info : '.$loopInfos
393			);
394			}
395			}
396

bulton-fr / dependency-tree

Tree::genOrderCheckInfiniteLoop() B last analyzed 2018-08-21 14:53 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

Tree::genOrderCheckInfiniteLoop() B
last analyzed 2018-08-21 14:53 UTC