class RouteProvider

class RouteProvider implements CacheableRouteProviderInterface, PreloadableRouteProviderInterface, EventSubscriberInterface {

  /**
   * The database connection from which to read route information.
   *
   * @var \Drupal\Core\Database\Connection
   */
  protected $connection;

  /**
   * The name of the SQL table from which to read the routes.
   *
   * @var string
   */
  protected $tableName;

  /**
   * The state.
   *
   * @var \Drupal\Core\State\StateInterface
   */
  protected $state;

  /**
   * A cache of already-loaded routes, keyed by route name.
   *
   * @var \Symfony\Component\Routing\Route[]
   */
  protected $routes = [];

  /**
   * A cache of already-loaded serialized routes, keyed by route name.
   *
   * @var string[]
   */
  protected $serializedRoutes = [];

  /**
   * The current path.
   *
   * @var \Drupal\Core\Path\CurrentPathStack
   */
  protected $currentPath;

  /**
   * The cache backend.
   *
   * @var \Drupal\Core\Cache\CacheBackendInterface
   */
  protected $cache;

  /**
   * The cache tag invalidator.
   *
   * @var \Drupal\Core\Cache\CacheTagsInvalidatorInterface
   */
  protected $cacheTagInvalidator;

  /**
   * A path processor manager for resolving the system path.
   *
   * @var \Drupal\Core\PathProcessor\InboundPathProcessorInterface
   */
  protected $pathProcessor;

  /**
   * The language manager.
   *
   * @var \Drupal\Core\Language\LanguageManagerInterface
   */
  protected $languageManager;

  /**
   * Cache ID prefix used to load routes.
   */
  const ROUTE_LOAD_CID_PREFIX = 'route_provider.route_load:';

  /**
   * An array of cache key parts to be used for the route match cache.
   *
   * @var string[]
   */
  protected $extraCacheKeyParts = [];

  /**
   * Constructs a new PathMatcher.
   *
   * @param \Drupal\Core\Database\Connection $connection
   *   A database connection object.
   * @param \Drupal\Core\State\StateInterface $state
   *   The state.
   * @param \Drupal\Core\Path\CurrentPathStack $current_path
   *   The current path.
   * @param \Drupal\Core\Cache\CacheBackendInterface $cache_backend
   *   The cache backend.
   * @param \Drupal\Core\PathProcessor\InboundPathProcessorInterface $path_processor
   *   The path processor.
   * @param \Drupal\Core\Cache\CacheTagsInvalidatorInterface $cache_tag_invalidator
   *   The cache tag invalidator.
   * @param string $table
   *   (Optional) The table in the database to use for matching. Defaults to 'router'
   * @param \Drupal\Core\Language\LanguageManagerInterface $language_manager
   *   (Optional) The language manager.
   */
  public function __construct(Connection $connection, StateInterface $state, CurrentPathStack $current_path, CacheBackendInterface $cache_backend, InboundPathProcessorInterface $path_processor, CacheTagsInvalidatorInterface $cache_tag_invalidator, $table = 'router', LanguageManagerInterface $language_manager = NULL) {
    $this->connection = $connection;
    $this->state = $state;
    $this->currentPath = $current_path;
    $this->cache = $cache_backend;
    $this->cacheTagInvalidator = $cache_tag_invalidator;
    $this->pathProcessor = $path_processor;
    $this->tableName = $table;
    $this->languageManager = $language_manager ?: \Drupal::languageManager();
  }

  /**
   * Finds routes that may potentially match the request.
   *
   * This may return a mixed list of class instances, but all routes returned
   * must extend the core symfony route. The classes may also implement
   * RouteObjectInterface to link to a content document.
   *
   * This method may not throw an exception based on implementation specific
   * restrictions on the URL. That case is considered a not found - returning
   * an empty array. Exceptions are only used to abort the whole request in
   * case something is seriously broken, like the storage backend being down.
   *
   * Note that implementations may not implement an optimal matching
   * algorithm, simply a reasonable first pass.  That allows for potentially
   * very large route sets to be filtered down to likely candidates, which
   * may then be filtered in memory more completely.
   *
   * @param \Symfony\Component\HttpFoundation\Request $request
   *   A request against which to match.
   *
   * @return \Symfony\Component\Routing\RouteCollection
   *   RouteCollection with all URLs that could potentially match $request.
   *   Empty collection if nothing can match. The collection will be sorted from
   *   highest to lowest fit (match of path parts) and then in ascending order
   *   by route name for routes with the same fit.
   */
  public function getRouteCollectionForRequest(Request $request) {

    // Cache both the system path as well as route parameters and matching
    // routes.
    $cid = $this
      ->getRouteCollectionCacheId($request);
    if ($cached = $this->cache
      ->get($cid)) {
      $this->currentPath
        ->setPath($cached->data['path'], $request);
      $request->query
        ->replace($cached->data['query']);
      return $cached->data['routes'];
    }
    else {

      // Just trim on the right side.
      $path = $request
        ->getPathInfo();
      $path = $path === '/' ? $path : rtrim($request
        ->getPathInfo(), '/');
      $path = $this->pathProcessor
        ->processInbound($path, $request);
      $this->currentPath
        ->setPath($path, $request);

      // Incoming path processors may also set query parameters.
      $query_parameters = $request->query
        ->all();
      $routes = $this
        ->getRoutesByPath(rtrim($path, '/'));
      $cache_value = [
        'path' => $path,
        'query' => $query_parameters,
        'routes' => $routes,
      ];
      $this->cache
        ->set($cid, $cache_value, CacheBackendInterface::CACHE_PERMANENT, [
        'route_match',
      ]);
      return $routes;
    }
  }

  /**
   * Find the route using the provided route name.
   *
   * @param string $name
   *   The route name to fetch
   *
   * @return \Symfony\Component\Routing\Route
   *   The found route.
   *
   * @throws \Symfony\Component\Routing\Exception\RouteNotFoundException
   *   Thrown if there is no route with that name in this repository.
   */
  public function getRouteByName($name) {
    $routes = $this
      ->getRoutesByNames([
      $name,
    ]);
    if (empty($routes)) {
      throw new RouteNotFoundException(sprintf('Route "%s" does not exist.', $name));
    }
    return reset($routes);
  }

  /**
   * {@inheritdoc}
   */
  public function preLoadRoutes($names) {
    if (empty($names)) {
      throw new \InvalidArgumentException('You must specify the route names to load');
    }
    $routes_to_load = array_diff($names, array_keys($this->routes), array_keys($this->serializedRoutes));
    if ($routes_to_load) {
      $cid = static::ROUTE_LOAD_CID_PREFIX . hash('sha512', serialize($routes_to_load));
      if ($cache = $this->cache
        ->get($cid)) {
        $routes = $cache->data;
      }
      else {
        try {
          $result = $this->connection
            ->query('SELECT [name], [route] FROM {' . $this->connection
            ->escapeTable($this->tableName) . '} WHERE [name] IN ( :names[] )', [
            ':names[]' => $routes_to_load,
          ]);
          $routes = $result
            ->fetchAllKeyed();
          $this->cache
            ->set($cid, $routes, Cache::PERMANENT, [
            'routes',
          ]);
        } catch (\Exception $e) {
          $routes = [];
        }
      }
      $this->serializedRoutes += $routes;
    }
  }

  /**
   * {@inheritdoc}
   */
  public function getRoutesByNames($names) {
    $this
      ->preLoadRoutes($names);
    foreach ($names as $name) {

      // The specified route name might not exist or might be serialized.
      if (!isset($this->routes[$name]) && isset($this->serializedRoutes[$name])) {
        $this->routes[$name] = unserialize($this->serializedRoutes[$name]);
        unset($this->serializedRoutes[$name]);
      }
    }
    return array_intersect_key($this->routes, array_flip($names));
  }

  /**
   * Returns an array of path pattern outlines that could match the path parts.
   *
   * @param array $parts
   *   The parts of the path for which we want candidates.
   *
   * @return array
   *   An array of outlines that could match the specified path parts.
   */
  protected function getCandidateOutlines(array $parts) {
    $number_parts = count($parts);
    $ancestors = [];
    $length = $number_parts - 1;
    $end = (1 << $number_parts) - 1;

    // The highest possible mask is a 1 bit for every part of the path. We will
    // check every value down from there to generate a possible outline.
    if ($number_parts == 1) {
      $masks = [
        1,
      ];
    }
    elseif ($number_parts <= 3 && $number_parts > 0) {

      // Optimization - don't query the state system for short paths. This also
      // insulates against the state entry for masks going missing for common
      // user-facing paths since we generate all values without checking state.
      $masks = range($end, 1);
    }
    elseif ($number_parts <= 0) {

      // No path can match, short-circuit the process.
      $masks = [];
    }
    else {

      // Get the actual patterns that exist out of state.
      $masks = (array) $this->state
        ->get('routing.menu_masks.' . $this->tableName, []);
    }

    // Only examine patterns that actually exist as router items (the masks).
    foreach ($masks as $i) {
      if ($i > $end) {

        // Only look at masks that are not longer than the path of interest.
        continue;
      }
      elseif ($i < 1 << $length) {

        // We have exhausted the masks of a given length, so decrease the length.
        --$length;
      }
      $current = '';
      for ($j = $length; $j >= 0; $j--) {

        // Check the bit on the $j offset.
        if ($i & 1 << $j) {

          // Bit one means the original value.
          $current .= $parts[$length - $j];
        }
        else {

          // Bit zero means wildcard.
          $current .= '%';
        }

        // Unless we are at offset 0, add a slash.
        if ($j) {
          $current .= '/';
        }
      }
      $ancestors[] = '/' . $current;
    }
    return $ancestors;
  }

  /**
   * {@inheritdoc}
   */
  public function getRoutesByPattern($pattern) {
    $path = RouteCompiler::getPatternOutline($pattern);
    return $this
      ->getRoutesByPath($path);
  }

  /**
   * Get all routes which match a certain pattern.
   *
   * @param string $path
   *   The route pattern to search for.
   *
   * @return \Symfony\Component\Routing\RouteCollection
   *   Returns a route collection of matching routes. The collection may be
   *   empty and will be sorted from highest to lowest fit (match of path parts)
   *   and then in ascending order by route name for routes with the same fit.
   */
  protected function getRoutesByPath($path) {

    // Split the path up on the slashes, ignoring multiple slashes in a row
    // or leading or trailing slashes. Convert to lower case here so we can
    // have a case-insensitive match from the incoming path to the lower case
    // pattern outlines from \Drupal\Core\Routing\RouteCompiler::compile().
    // @see \Drupal\Core\Routing\CompiledRoute::__construct()
    $parts = preg_split('@/+@', mb_strtolower($path), -1, PREG_SPLIT_NO_EMPTY);
    $collection = new RouteCollection();
    $ancestors = $this
      ->getCandidateOutlines($parts);
    if (empty($ancestors)) {
      return $collection;
    }

    // The >= check on number_parts allows us to match routes with optional
    // trailing wildcard parts as long as the pattern matches, since we
    // dump the route pattern without those optional parts.
    try {
      $routes = $this->connection
        ->query("SELECT [name], [route], [fit] FROM {" . $this->connection
        ->escapeTable($this->tableName) . "} WHERE [pattern_outline] IN ( :patterns[] ) AND [number_parts] >= :count_parts", [
        ':patterns[]' => $ancestors,
        ':count_parts' => count($parts),
      ])
        ->fetchAll(\PDO::FETCH_ASSOC);
    } catch (\Exception $e) {
      $routes = [];
    }

    // We sort by fit and name in PHP to avoid a SQL filesort and avoid any
    // difference in the sorting behavior of SQL back-ends.
    usort($routes, [
      $this,
      'routeProviderRouteCompare',
    ]);
    foreach ($routes as $row) {
      $collection
        ->add($row['name'], unserialize($row['route']));
    }
    return $collection;
  }

  /**
   * Comparison function for usort on routes.
   */
  protected function routeProviderRouteCompare(array $a, array $b) {
    if ($a['fit'] == $b['fit']) {
      return strcmp($a['name'], $b['name']);
    }

    // Reverse sort from highest to lowest fit. PHP should cast to int, but
    // the explicit cast makes this sort more robust against unexpected input.
    return (int) $b['fit'] <=> (int) $a['fit'];
  }

  /**
   * {@inheritdoc}
   */
  public function getAllRoutes() {
    $select = $this->connection
      ->select($this->tableName, 'router')
      ->fields('router', [
      'name',
      'route',
    ]);
    $routes = $select
      ->execute()
      ->fetchAllKeyed();
    $result = [];
    foreach ($routes as $name => $route) {
      $result[$name] = unserialize($route);
    }
    $array_object = new \ArrayObject($result);
    return $array_object
      ->getIterator();
  }

  /**
   * {@inheritdoc}
   */
  public function reset() {
    $this->routes = [];
    $this->serializedRoutes = [];
    $this->cacheTagInvalidator
      ->invalidateTags([
      'routes',
    ]);
  }

  /**
   * {@inheritdoc}
   */
  public static function getSubscribedEvents() : array {
    $events[RoutingEvents::FINISHED][] = [
      'reset',
    ];
    return $events;
  }

  /**
   * {@inheritdoc}
   */
  public function addExtraCacheKeyPart($cache_key_provider, $cache_key_part) {
    $this->extraCacheKeyParts[$cache_key_provider] = $cache_key_part;
  }

  /**
   * Returns the cache ID for the route collection cache.
   *
   * @param \Symfony\Component\HttpFoundation\Request $request
   *   The request object.
   *
   * @return string
   *   The cache ID.
   */
  protected function getRouteCollectionCacheId(Request $request) {

    // Include the current language code in the cache identifier as
    // the language information can be elsewhere than in the path, for example
    // based on the domain.
    $this
      ->addExtraCacheKeyPart('language', $this
      ->getCurrentLanguageCacheIdPart());

    // Sort the cache key parts by their provider in order to have predictable
    // cache keys.
    ksort($this->extraCacheKeyParts);
    $key_parts = [];
    foreach ($this->extraCacheKeyParts as $provider => $key_part) {
      $key_parts[] = '[' . $provider . ']=' . $key_part;
    }
    return 'route:' . implode(':', $key_parts) . ':' . $request
      ->getPathInfo() . ':' . $request
      ->getQueryString();
  }

  /**
   * Returns the language identifier for the route collection cache.
   *
   * @return string
   *   The language identifier.
   */
  protected function getCurrentLanguageCacheIdPart() {

    // This must be in sync with the language logic in
    // \Drupal\path_alias\PathProcessor\AliasPathProcessor::processInbound() and
    // \Drupal\path_alias\AliasManager::getPathByAlias().
    // @todo Update this if necessary in https://www.drupal.org/node/1125428.
    return $this->languageManager
      ->getCurrentLanguage(LanguageInterface::TYPE_URL)
      ->getId();
  }

}