How can I recursively check an array of file include dependencies for other dependencies?

Question

To explain my question, let me first point to this array:

<?php
$_depends = array(
    '/Scripting/jquery.hyponiqs/jquery.dropdown.js' => array(
        "/Scripting/jquery.externals/jquery.resize.js",
        "/Scripting/jquery.externals/jquery.topzindex.js",
        "/Scripting/jquery.externals/jquery.timers.js",
        "/Scripting/jquery-ui.min.js",
        "/Scripting/jquery.hyponiqs/hyponiqs.core.js",
    ),
    '/Script/UI/Dialogs.js' => array(
        "/Scripting/jquery.externals/jquery.resize.js",
        "/Scripting/jquery.externals/jquery.topzindex.js"
    ),
    '/Script/Display/List.js' => array(
        "/Scripting/jquery.externals/jquery.timers.js"
    )
);
?>

Whenever a JavaScript file is included, it is checked against this array for dependencies. All the dependencies for each file are then added to the final $includes array. The problem comes when I add an include with dependencies and one of those dependencies also has its own dependencies, such as:

<?php
$_depends = array(
    '/Scripting/jquery.hyponiqs/jquery.dropdown.js' => array(
        "/Scripting/jquery.externals/jquery.resize.js",
        "/Scripting/jquery.externals/jquery.topzindex.js",
        "/Scripting/jquery.externals/jquery.timers.js",
        "/Scripting/jquery-ui.min.js",
        "/Scripting/jquery.hyponiqs/hyponiqs.core.js",
    ),
    '/Script/UI/Dialogs.js' => array(
        "/Scripting/jquery.externals/jquery.resize.js",
        "/Scripting/jquery.externals/jquery.topzindex.js"
    ),
    '/Script/Display/List.js' => array(
        "/Scripting/jquery.externals/jquery.timers.js"
    ),
    '/Script/UI/Calendar/Main.js' => array(
        "/Scripting/jquery-ui.min.js",
        "/Script/UI/Dialogs.js"
    )
);
?>

As you can see, the added '/Script/UI/Calendar/Main.js' depends on "/Script/UI/Dialogs.js" which has its own dependencies.

I know that I would have to recursively check the dependency array and final includes array, but I can't seem to wrap my head around the logic. A little help here might be nice.

UPDATE

I wrapped everything in a class to illustrate its purpose (although the actual class is much more complicated and has various other include-handling functionality:

<?php
class Script_Depends {
    private $_includes = array();

    private $_depends = array(
        '/Scripting/jquery.hyponiqs/jquery.dropdown.js' => array(
            "/Scripting/jquery.externals/jquery.resize.js",
            "/Scripting/jquery.externals/jquery.topzindex.js",
            "/Scripting/jquery.externals/jquery.timers.js",
            "/Scripting/jquery-ui.min.js",
            "/Scripting/jquery.hyponiqs/hyponiqs.core.js",
        ),
        '/Script/UI/Dialogs.js' => array(
            "/Scripting/jquery.externals/jquery.resize.js",
            "/Scripting/jquery.externals/jquery.topzindex.js"
        ),
        '/Script/Display/List.js' => array(
            "/Scripting/jquery.externals/jquery.timers.js"
        ),
        '/Script/UI/Calendar/Main.js' => array(
            "/Script/UI/Dialogs.js",
            "/Scripting/jquery-ui.min.js"
        )
    );

    public function includes($includes)
    {
        if (is_string($includes)) $includes = array($includes);

        foreach ($includes as $include) {
            if (isset($this->_depends[$include])) {
                $this->_includes = $this->includes($this->_depends[$include]);
                array_push($this->_includes, $include);
            }
            else {
                array_push($this->_includes, $include);
            }
        }

        $this->_includes = array_unique($this->_includes);

        return $this->_includes;
    }
}
?>

Answer 1

• Keep a stack, initially with your initial dependencies (stack)
• Keep an empty array with all the (transitive) dependencies (deps)
• While stack is not empty
  • pop the last element (el)
  • add el to deps
  • loop through the dependencies of el
    • if the dependency is in deps, do nothing
    • otherwise, push it to stack

Answer 2

The function you are looking for is called flatten. It takes a recursive list and returns all of the elements at every level.

There are some implementations in php in the comments here: http://php.net/manual/en/function.array-values.php

Here is an implementation in javascript: http://tech.karbassi.com/2009/12/17/pure-javascript-flatten-array/

Answer 3

Try this:

function getDependentFiles($file, $dependencies) {
    $fileIndex = array();
    $queue = array($file);
    while (count($queue)) {
        $f = array_shift($queue);
        if (!isset($fileIndex[$f])) {
            if (array_key_exists($f, $dependencies) && is_array($dependencies[$f])) {
                $queue = array_merge($queue, $dependencies[$f]);
            }
            $fileIndex[$f] = true;
        }
    }
    return array_keys($fileIndex);
}
var_dump(getDependentFiles('/Script/UI/Calendar/Main.js', $_depends));

This basically implements the algorithm described by Artefacto.

Answer 4

See if this does the trick -- a small mod to your function.

(BTW it is mind-bending because of your naming conventions: $includes, $include, $this->_includes and $this->includes()!! Suggest you use better names. I've renamed the function to calculate_includes, but you should clean up the others too.)

public function calculate_includes($includes) {

        foreach ((array)$includes as $include) {

            if(in_array($include, $this->_includes)) continue;

            if (isset($this->_depends[$include])) {
                $this->_includes = $this->calculate_includes($this->_depends[$include]);
            } else {
                array_push($this->_includes, $include);
            }
        }

        $this->_includes = array_unique($this->_includes);

        return $this->_includes;
    }