diff --git a/core/lib/Drupal/Core/Asset/AssetBag.php b/core/lib/Drupal/Core/Asset/AssetBag.php index 61a6bb7..c202288 100644 --- a/core/lib/Drupal/Core/Asset/AssetBag.php +++ b/core/lib/Drupal/Core/Asset/AssetBag.php @@ -11,6 +11,8 @@ use Drupal\Core\Asset\AssetBagInterface; use Symfony\Component\DependencyInjection\ContainerInterface; +use Graph\Component\Graph\DirectedAcyclicGraph; + /** * The default AssetBag, used to declare assets needed for a response. */ @@ -168,12 +170,34 @@ class AssetBag implements AssetBagInterface { $this->sorted['js'] = $this->sorted['css'] = array(); + $this->sorted['js'] = $this->_sort($this->getUnsortedJs()); + $this->sorted['css'] = $this->_sort($this->getUnsortedCss()); + $all = array(); $this->needsSorting = FALSE; } + protected function _sort($items) { + $g = new DirectedAcyclicGraph(); + foreach ($items as $item) { + $from_id = spl_object_hash($item); + $g->addNode($from_id, $item); + $deps = $js->getDependencies(); + foreach ($deps as $dep) { + $to_id = spl_object_hash($dep); + $g->addNode($to_id, $dep); + $g->addLink($from_id, $to_id); + } + } + $tsl = $g->getTSL(); + $result = arrau(); + foreach($tsl as $id) { + $result[] = $g->getNodeData($id); + } + return $result; + } /** * Returns all assets contained in this object. diff --git a/core/vendor/graph/graph/LICENSE.txt b/core/vendor/graph/graph/LICENSE.txt new file mode 100644 index 0000000..acb6082 --- /dev/null +++ b/core/vendor/graph/graph/LICENSE.txt @@ -0,0 +1,31 @@ +Copyright (c) 2009-2013 by the Graph Team, see AUTHORS for more details. + +Some rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following + disclaimer in the documentation and/or other materials provided + with the distribution. + + * The names of the contributors may not be used to endorse or + promote products derived from this software without specific + prior written permission. + +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. diff --git a/core/vendor/graph/graph/README.md b/core/vendor/graph/graph/README.md new file mode 100644 index 0000000..7a8c448 --- /dev/null +++ b/core/vendor/graph/graph/README.md @@ -0,0 +1,4 @@ +graph +===== + +PHP Graph classes \ No newline at end of file diff --git a/core/vendor/graph/graph/lib/Graph/DirectedAcyclicGraph.class.php b/core/vendor/graph/graph/lib/Graph/DirectedAcyclicGraph.class.php new file mode 100644 index 0000000..567ceea --- /dev/null +++ b/core/vendor/graph/graph/lib/Graph/DirectedAcyclicGraph.class.php @@ -0,0 +1,107 @@ +subGraph(array($to_id)); + $p = $sub->getParticipants(); + if (in_array($from_id, $p)) { + throw new \Exception("Cannot add Cycle '$from_id' -> '$to_id' to " . $this); + } + else { + parent::addLink($from_id, $to_id); + } + } + + /** + * Converts a DirectedGraph into a DirectedAcyclicGraph. + * + * A DirectedGraph can be converted into a DirectedAcyclicGraph when + * is does not contain any cycle. + * + * @param \GraphAPI\Component\Graph\DirectedGraph $g + * @param type $ignore_exception + * @throws \GraphAPI\Component\Graph\Exception + */ + static function fromDirectedGraph(DirectedGraph $g, $ignore_exception = FALSE) { + $d = new DirectedAcyclicGraph(); + foreach ($g->getNodeIds() as $id) { + $links = $g->getLinks($id); + foreach ($links as $link) { + try { + $d->addLink($id, $link); + } + catch (\Exception $exc) { + if (!$ignore_exception) { + throw $exc; + } + } + } + } + return $d; + } + + /** + * Calculates the Topological Sorted List. + * + * A Topological Sorted List is a Depth First Search (DFS) ordered + * list of participants. + * + * TODO: Do we need this method for DirectedGraph? + * If there are cycles/loops then the algorithme does not loop forever. + * But the TSL is not really a TSL. + * + * The algorithme is based on the Iterator example from + * the book Higher Order Perl where a recusive function + * can be rewritten into a loop. + * + * @param array $ids + * List of nodes interested in. + * @return array + * The TSL ordered list of participants + */ + public function getTSL($ids = array()) { + $g = $this->subGraph($ids); + // By adding a root the DFS is more cleaner/predictable for tests + $root = $g->getId(); + $g->addRoot($root); + $agenda = array($root); + + $visited = array(); + $tsl = array(); + while ($inspect = array_pop($agenda)) { + if (!isset($visited[$inspect])) { + $visited[$inspect] = TRUE; + $links = $g->getLinks($inspect); + if (!empty($links)) { + array_push($agenda, $inspect); + foreach ($links as $id) { + if (!isset($visited[$id])) { + $agenda[] = $id; + } + } + } + else { + // We are done with this node. + $tsl[] = $inspect; + } + } + else { + // Already inspected so spit it out. + $tsl[] = $inspect; + } + } + return array_diff($tsl, array($root)); + } + +} diff --git a/core/vendor/graph/graph/lib/Graph/DirectedGraph.class.php b/core/vendor/graph/graph/lib/Graph/DirectedGraph.class.php new file mode 100644 index 0000000..4245ddb --- /dev/null +++ b/core/vendor/graph/graph/lib/Graph/DirectedGraph.class.php @@ -0,0 +1,72 @@ +_list) as $from_id) { + $g->addNode($from_id); + foreach ($this->getLinks($from_id) as $to_id) { + $g->addLink($to_id, $from_id); + } + } + return $g; + } + + /** + * A subgraph is calculated based on the participants collected based on the given node ids. + * + * @param array $ids + * The nodes interested in. + * @return DirectedGraph + * The subgraph with all participants + */ + public function subGraph($ids = array()) { + $g = new DirectedGraph(); + $participants = $this->getParticipants($ids); + foreach ($participants as $id) { + $g->addNode($id); + // Only participating links are added. + $links = $this->getLinks($id); + if (is_array($links)) { + $g->addLinks($id, array_intersect($participants, $links)); + } + } + return $g; + } + + /** + * Implementation of uni directed link between two nodes + * + * @see addLink() + * + * @param string $from_id + * @param string $to_id + */ + protected function _addLink($from_id, $to_id, $data, $key) { + $this->_list[$from_id][Graph::GRAPH_LINKS][$to_id][$key]['_id'] = $to_id; + $this->_setLinkData($from_id, $to_id, $data, $key); + } + + protected function _setLinkData($from_id, $to_id, $data, $key) { + $this->_list[$from_id][Graph::GRAPH_LINKS][$to_id][$key][GRAPH::GRAPH_DATA] = $data; + } + +} diff --git a/core/vendor/graph/graph/lib/Graph/Graph.class.php b/core/vendor/graph/graph/lib/Graph/Graph.class.php new file mode 100644 index 0000000..b54064d --- /dev/null +++ b/core/vendor/graph/graph/lib/Graph/Graph.class.php @@ -0,0 +1,326 @@ +_data; + } + + public function setData($data) { + $this->_data = $data; + } + + /** + * Adds id to the list of nodes. + * + * The data is only added when the node was non-existing yet. + * + * @param String $id + * The Id of the node to add. + * @return Graph + */ + public function addNode($id, $data = NULL) { + if (!isset($this->_list[$id])) { + $this->_list[$id] = array(); + $this->_list[$id][Graph::GRAPH_LINKS] = array(); + $this->_list[$id][Graph::GRAPH_DATA] = $data; + } + return $this; + } + + /** + * Deletes a node from the graph + * + * @param type $id + * @return Graph + */ + public function deleteNode($id) { + if (isset($this->_list[$id])) { + unset($this->_list[$id]); + foreach ($this->getNodeIds() as $nid) { + unset($this->_list[$nid][Graph::GRAPH_LINKS][$id]); + } + } + return $this; + } + + public function hasNode($id) { + return isset($this->_list[$id]); + } + + /** + * Returns the IDs of the added nodes. + * + * @return array with IDs as values + */ + public function getNodeIds() { + return array_keys($this->_list); + } + + public function getNodeData($id) { + return $this->_list[$id][Graph::GRAPH_DATA]; + } + + public function setNodeData($id, $data) { + $this->_list[$id][Graph::GRAPH_DATA] = $data; + } + + /** + * Adds a link between two node ids. + * + * We allow for multigraph vertices or multiple links between 2 nodes + * + * @param String $from_id + * The start point of the link. + * @param String $to_id + * The end point of the link. + * @param any $data + * Can hold anything. Note this get's duplicate unless it's a reference. + * @param string $key + * Unique key to identify this particular link relation. + * @return Graph + */ + public function addLink($from_id, $to_id, $data = NULL, $key = GRAPH::GRAPH_LINK_NO_KEY) { + $this->addNode($from_id); + $this->addNode($to_id); + $this->_addLink($from_id, $to_id, $data, $key); + return $this; + } + + /** + * Returns the array keys of the multigraph between given node ids. + * + * @param string $from_id + * @param string $to_id + * @return array + */ + public function getLinkIds($from_id, $to_id) { + $result = $this->getLinks($from_id); + if (is_array($result) && isset($this->_list[$from_id][Graph::GRAPH_LINKS][$to_id])) { + return array_keys($this->_list[$from_id][Graph::GRAPH_LINKS][$to_id]); + } + } + + /** + * Returns the data element of the given node ids and link id. + * + * @param string $from_id + * @param string $to_id + * @param string $key + * + * @return any + */ + public function getLinkData($from_id, $to_id, $key = GRAPH::GRAPH_LINK_NO_KEY) { + return $this->_list[$from_id][Graph::GRAPH_LINKS][$to_id][$key][GRAPH::GRAPH_DATA]; + } + + public function setLinkData($from_id, $to_id, $data, $key = GRAPH::GRAPH_LINK_NO_KEY) { + $this->_setLinkData($from_id, $to_id, $data, $key); + } + + /** + * Adds a list of links to a node. + * + * This is a utility function ignoring data or multilinks. + * + * @param string $from_id + * @param array $to_ids + * + * @return $this + */ + public function addLinks($from_id, $to_ids) { + foreach ($to_ids as $to_id) { + $this->addLink($from_id, $to_id); + } + return $this; + } + + /** + * Returns all links from the give node id. + * + * @param string $from_id + * @return array of node ids leaving the given node id. + */ + public function getLinks($id) { + if (isset($this->_list[$id])) { + return array_keys($this->_list[$id][Graph::GRAPH_LINKS]); + } + } + + /** + * Gives all participants related to the given node(s). + * + * @param array $list + * The list of Ids interested in. + * @return array + * All Ids related to the given list. + */ + public function getParticipants($list = array()) { + if (empty($list)) { + return $this->getNodeIds(); + } + $visited = array(); + $agenda = array_values($list); + while ($id = array_shift($agenda)) { + if (!$this->hasNode($id)) { + continue; + } + // Prevent infinite looping + if (!isset($visited[$id])) { + $visited[$id] = TRUE; + $links = $this->getLinks($id); + if (is_array($links)) { + $agenda = array_merge($agenda, $links); + } + } + } + return array_keys($visited); + } + + public function isCircularMember($id) { + $route = $this->getParticipants(array($id)); + foreach ($route as $visited_id) { + $links = $this->getLinks($visited_id); + if (is_array($links) && in_array($id, $links)) { + return TRUE; + } + } + return FALSE; + } + + /** + * Adds a root to the graph connecting islands or loops + * + * A graph may have disconnected sub graphs or be one big loop. So there is + * no single entry point into the graph. + * + * @param type $root_id + */ + public function addRoot($root_id) { + $p = $this->getParts(); + foreach ($p as $nid) { + $this->addLink($root_id, $nid); + } + return $this; + } + + /** + * A Graph is split when having disconnected subgraphs. + * + * @return type + */ + public function isSplit() { + return count($this->getParts()) > 1; + } + + /** + * Gets list or IDs one for each subgraph. + * + * @return type + */ + public function getParts() { + $nids = $this->getNodeIds(); + $parts = array(); + while (!empty($nids)) { + $nid = array_shift($nids); + $p = $this->getParticipants(array($nid)); + $nids = array_diff($nids, $p); + $parts = array_diff($parts, $p); + $parts[] = $nid; + } + return $parts; + } + + /** + * Get a simple representation of the graph as a string. + * + * This contains a(b,c) like fragments indicating a connects to b and c. + * + * @return string + */ + public function __toString() { + $result = array(); + foreach (array_keys($this->_list) as $id) { + $row = $id . '('; + $links = $this->getLinks($id); + if (is_array($links)) { + $row .= join(',', $links); + } + $row .= ')'; + $result[] = $row; + } + return join(",", $result); + } + + /** + * Implementation of bidirection links between the given node ids. + * + * A Graph is bidirectional so we need to store the link twice. + * + * @param string $from_id + * @param string $to_id + * @param any $data + * Can hold anything. Note this get's duplicate unless it's a reference. + * @param string $key + * Unique key to identify this particular link relation. + */ + protected function _addLink($from_id, $to_id, $data, $key) { + $this->_list[$from_id][Graph::GRAPH_LINKS][$to_id][$key]['_id'] = $to_id; + $this->_list[$to_id][Graph::GRAPH_LINKS][$from_id][$key]['_id'] = $from_id; + $this->_setLinkData($from_id, $to_id, $data, $key); + } + + protected function _setLinkData($from_id, $to_id, $data, $key) { + $this->_list[$from_id][Graph::GRAPH_LINKS][$to_id][$key][GRAPH::GRAPH_DATA] = $data; + $this->_list[$to_id][Graph::GRAPH_LINKS][$from_id][$key][GRAPH::GRAPH_DATA] = $data; + } + + protected function getId() { + return spl_object_hash($this); + } +}