new grouper

AssetGraph.php

<?php

/**
 * @file
 * Contains \Drupal\Core\Asset\AssetGraph.
 */

namespace Drupal\Core\Asset;
use Gliph\Graph\DirectedAdjacencyGraph;

/**
 * An extension of the DirectedAdjacencyGraph concept designed specifically for
 * Drupal's asset management use case.
 *
 * Drupal allows for two types of sequencing declarations:
 *
 *   - Dependencies, which guarantee that dependent asset must be present and
 *     that it must precede the asset declaring it as a dependency.
 *   - Ordering, which can guarantee that asset A will be either preceded or
 *     succeeded by asset B, but does NOT guarantee that B will be present.
 *
 * The impact of a dependency can be calculated myopically (without knowledge of
 * the full set), as a dependency inherently guarantees the presence of the
 * other vertex in the set.
 *
 * For ordering, however, the full set must be inspected to determine whether or
 * not the other asset is already present. If it is, a directed edge can be
 * declared; if it is not.
 *
 * This class eases the process of determining what to do with ordering
 * declarations by implementing a more sophisticated addVertex() mechanism,
 * which incrementally sets up (and triggers) watches for any ordering
 * declarations that have not yet been realized.
 */
class AssetGraph extends DirectedAdjacencyGraph {
  public function addVertex($vertex) {
    parent::addVertex($vertex); // TODO: Change the autogenerated stub
  }
}

CssCollectionGrouperNouveaux.php

<?php

/**
 * @file
 * Contains \Drupal\Core\Asset\CssCollectionGrouperNouveaux.
 */

namespace Drupal\Core\Asset;
use Gliph\Traversal\DepthFirst;
use Gliph\Visitor\DepthFirstBasicVisitor;
use Drupal\Core\Asset\AssetGraph;

/**
 * Groups CSS assets.
 */
class CssCollectionGrouperNouveaux implements AssetCollectionGrouperInterface {

  /**
   * @var AssetLibraryRepository
   */
  protected $repository;

  /**
   * An array of optimal groups for the assets currently being processed.
   *
   * This is ephemeral state; it is only stored as an object property in order
   * to avoid doing certain processing twice.
   *
   * @var array
   */
  protected $optimal;

  /**
   * @var \SplObjectStorage;
   */
  protected $optimal_lookup;

  public function __construct(AssetLibraryRepository $repository) {
    $this->repository = $repository;
  }

  /**
   * Groups a collection of assets into logical groups of asset collections.
   *
   * @param array $assets
   *   An asset collection.
   *
   * @return array
   *   A sorted array of asset groups.
   */
  public function group(array $assets) {
    $tsl = $this->getOptimalTSL($assets);

    // TODO replace with CssCollection
    // TODO ordering suddenly matters here...problem?
    $processed = array();
    $last_key = FALSE;
    foreach ($tsl as $asset) {
      $key = $this->optimal_lookup->contains($asset) ? $this->optimal_lookup[$asset] : FALSE;

      if ($key !== $last_key) {
        $processed[] = $aggregate = new CssAggregateAsset(); // TODO implement CSSAggregateAsset
      }

      $aggregate->add($asset);
    }

    return $processed;
  }

  /**
   * Gets a topologically sorted list that is optimal for grouping.
   *
   * @param array $assets
   *
   * @return array
   *   A linear list of assets that will enable optimal groupings.
   *
   * @throws \LogicException
   */
  protected function getOptimalTSL(array $assets) {
    // We need to define the optimum minimal group set, given metadata
    // boundaries across which aggregates cannot be safely made.
    $this->optimal = array();

    // Also create an SplObjectStorage to act as a lookup table on an asset to
    // its group, if any.
    $this->optimal_lookup = new \SplObjectStorage();

    // Finally, create a specialized directed adjacency list that will capture
    // sequencing information.
    $graph = new AssetGraph();

    foreach ($assets as $asset) {
      $graph->addVertex($asset);

      foreach ($this->repository->resolveDependencies($asset) as $dependency) {
        $graph->addDirectedEdge($asset, $dependency);
      }

      $k = $this->getGroupKey($asset);

      if ($k === FALSE) {
        // Record no optimality information for ungroupable assets; they will
        // be visited normally and rearranged as needed.
        continue;
      }

      if (!isset($this->optimal[$k])) {
        // Create an SplObjectStorage to represent each set of assets that would
        // optimally be grouped together.
        $this->optimal[$k] = new \SplObjectStorage();
      }
      $this->optimal[$k]->attach($asset, $k);
      $this->optimal_lookup->attach($asset, $this->optimal[$k]);
    }

    // First, transpose the graph in order to get an appropriate answer
    $transpose = $graph->transpose();
    // Next, check for cycles
    if ($cycles = $transpose->getCycles()) {
      throw new \LogicException(sprintf('Found %d cycles in CSS asset collection.', count($cycles)));
    }

    // Create a queue of start vertices to prime the traversal.
    $queue = $this->createSourceQueue($graph, $transpose);

    // Now, create the visitor and walk the graph to get an optimal TSL.
    $visitor = new OptimallyGroupedTSLVisitor($this->optimal, $this->optimal_lookup);
    DepthFirst::traverse($transpose, $visitor, $queue);

    return $visitor->getTSL();
  }

  /**
   * Gets the grouping key for the provided asset.
   *
   * @param $asset
   *
   * @return bool|string
   * @throws \UnexpectedValueException
   */
  protected function getGroupKey($asset) {
    // The browsers for which the CSS item needs to be loaded is part of the
    // information that determines when a new group is needed, but the order
    // of keys in the array doesn't matter, and we don't want a new group if
    // all that's different is that order.
    ksort($asset['browsers']);

    if ($asset instanceof StylesheetFileAsset) {
      // Compose a string key out of the set of relevant properties.
      // TODO - currently ignoring group, which is used in the current implementation. wishful thinking? maybe, maybe not.
      // TODO media has been pulled out - needs to be handled by the aggregator, wrapping css in media queries
      $k = $asset->isPreprocessable()
        ? implode(':', array('file', $asset['every_page'], implode('', $asset['browsers'])))
        : FALSE;

      return $k;
    }
    else if ($asset instanceof StylesheetStringAsset) {
      // String items are always grouped.
      // TODO use the term 'inline' here? do "string" and "inline" necessarily mean the same?
      $k = implode(':', 'string', implode('', $asset['browsers']));

      return $k;
    }
    else if ($asset instanceof StylesheetExternalAsset) {
      // Never group external assets.
      $k = FALSE;

      return $k;
    }
    else {
      throw new \UnexpectedValueException(sprintf('Unknown CSS asset type "%s" somehow made it into the CSS collection during grouping.', get_class($asset)));
    }
  }

  /**
   * Creates a queue of starting vertices that will facilitate an ideal TSL.
   *
   * @param AssetGraph $graph
   * @param AssetGraph $transpose
   *
   * @return \SplQueue $queue
   *   A queue of vertices
   */
  protected function createSourceQueue(AssetGraph $graph, AssetGraph $transpose) {
    $reach_visitor = new DepthFirstBasicVisitor();

    // Find source vertices (outdegree 0) in the original graph
    $sources = DepthFirst::find_sources($graph, $reach_visitor);

    // Traverse the transposed graph to get reachability data on each vertex
    DepthFirst::traverse($transpose, $reach_visitor, clone $sources);

    // Sort vertices via a PriorityQueue based on total reach
    $pq = new \SplPriorityQueue();
    foreach ($sources as $vertex) {
      $pq->insert($vertex, count($reach_visitor->getReachable($vertex)));
    }

    // Dump the priority queue into a normal queue
    // TODO maybe gliph should support pq/heaps as a queue type on which to operate?
    $queue = new \SplQueue();
    foreach ($pq as $vertex) {
      $queue->push($vertex);
    }

    return $queue;
  }

}

OptimallyGroupedTSLVisitor.php

<?php

/**
 * @file
 * Contains \Drupal\Core\Asset\OptimallyGroupedTSLVisitor.
 */

namespace Drupal\Core\Asset;
use Gliph\Visitor\DepthFirstVisitorInterface;

/**
 * DepthFirst visitor intended for use with a asset data that will select the
 * optimal valid TSL, given a preferred grouping of vertices.
 */
class OptimallyGroupedTSLVisitor implements DepthFirstVisitorInterface {

  /**
   * @var array
   */
  protected $tsl;

  /**
   * @var array
   */
  protected $groups;

  /**
   * @var \SplObjectStorage
   */
  protected $vertexMap;

  /**
   * Creates a new optimality visitor.
   *
   * @param array $groups
   *   An array of SplObjectStorage, the contents of each representing an
   *   optimal grouping.
   *
   * @param \SplObjectStorage $vertex_map
   *   A map of vertices to the group in which they reside, if any.
   */
  public function __construct($groups, \SplObjectStorage $vertex_map) {
    $this->tsl = array();
    $this->groups = $groups;
    $this->vertexMap = $vertex_map;
  }

  /**
   * {@inheritdoc}
   */
  public function onInitializeVertex($vertex, $source, \SplQueue $queue) {}

  /**
   * {@inheritdoc}
   */
  public function onBackEdge($vertex, \Closure $visit) {
    // TODO: Implement onBackEdge() method.
  }

  /**
   * {@inheritdoc}
   */
  public function onStartVertex($vertex, \Closure $visit) {
    $this->active->attach($vertex);

    // If there's a record in the vertex map, it means this vertex has an
    // optimal group. Remove it from that group, as it being here means it's
    // been visited.
    if ($this->vertexMap->contains($vertex)) {
      $this->vertexMap[$vertex]->detach($vertex);
    }
  }

  /**
   * {@inheritdoc}
   */
  public function onExamineEdge($from, $to, \Closure $visit) {}

  /**
   * Here be the unicorns.
   *
   * Once the depth-first traversal is done for a vertex, rather than
   * simply pushing it onto the TSL and moving on (as in a basic depth-first
   * traversal), if the finished vertex is a member of an optimality group, then
   * visit all other (unvisited) members of that optimality group.
   *
   * This ensures the final TSL has the tightest possible adherence to the
   * defined optimal groupings while still respecting the DAG.
   *
   */
  public function onFinishVertex($vertex, \Closure $visit) {
    // TODO this still isn't quite optimal; it can split groups unnecessarily. tweak a little more.
    // TODO explore risk of hitting the 100 call stack limit
    if ($this->vertexMap->contains($vertex)) {
      foreach ($this->vertexMap[$vertex] as $vertex) {
        $visit($vertex);
      }
    }
    $this->tsl[] = $vertex;
  }

  /**
   * Returns the TSL produced by a depth-first traversal.
   *
   * @return array
   *   A topologically sorted list of vertices.
   */
  public function getTSL() {
    return $this->tsl;
  }
}