class RenderCache

class RenderCache implements RenderCacheInterface {
    
    /**
     * The request stack.
     *
     * @var \Symfony\Component\HttpFoundation\RequestStack
     */
    protected $requestStack;
    
    /**
     * The cache factory.
     *
     * @var \Drupal\Core\Cache\CacheFactoryInterface
     */
    protected $cacheFactory;
    
    /**
     * The cache contexts manager.
     *
     * @var \Drupal\Core\Cache\Context\CacheContextsManager
     */
    protected $cacheContextsManager;
    
    /**
     * Constructs a new RenderCache object.
     *
     * @param \Symfony\Component\HttpFoundation\RequestStack $request_stack
     *   The request stack.
     * @param \Drupal\Core\Cache\CacheFactoryInterface $cache_factory
     *   The cache factory.
     * @param \Drupal\Core\Cache\Context\CacheContextsManager $cache_contexts_manager
     *   The cache contexts manager.
     */
    public function __construct(RequestStack $request_stack, CacheFactoryInterface $cache_factory, CacheContextsManager $cache_contexts_manager) {
        $this->requestStack = $request_stack;
        $this->cacheFactory = $cache_factory;
        $this->cacheContextsManager = $cache_contexts_manager;
    }
    
    /**
     * {@inheritdoc}
     */
    public function get(array $elements) {
        // Form submissions rely on the form being built during the POST request,
        // and render caching of forms prevents this from happening.
        // @todo remove the isMethodCacheable() check when
        //       https://www.drupal.org/node/2367555 lands.
        if (!$this->requestStack
            ->getCurrentRequest()
            ->isMethodCacheable() || !($cid = $this->createCacheID($elements))) {
            return FALSE;
        }
        $bin = isset($elements['#cache']['bin']) ? $elements['#cache']['bin'] : 'render';
        if (!empty($cid) && ($cache_bin = $this->cacheFactory
            ->get($bin)) && ($cache = $cache_bin->get($cid))) {
            $cached_element = $cache->data;
            // Two-tier caching: redirect to actual (post-bubbling) cache item.
            // @see \Drupal\Core\Render\RendererInterface::render()
            // @see ::set()
            if (isset($cached_element['#cache_redirect'])) {
                return $this->get($cached_element);
            }
            // Return the cached element.
            return $cached_element;
        }
        return FALSE;
    }
    
    /**
     * {@inheritdoc}
     */
    public function set(array &$elements, array $pre_bubbling_elements) {
        // Form submissions rely on the form being built during the POST request,
        // and render caching of forms prevents this from happening.
        // @todo remove the isMethodCacheable() check when
        //       https://www.drupal.org/node/2367555 lands.
        if (!$this->requestStack
            ->getCurrentRequest()
            ->isMethodCacheable() || !($cid = $this->createCacheID($elements))) {
            return FALSE;
        }
        $data = $this->getCacheableRenderArray($elements);
        $bin = isset($elements['#cache']['bin']) ? $elements['#cache']['bin'] : 'render';
        $cache = $this->cacheFactory
            ->get($bin);
        // Calculate the pre-bubbling CID.
        $pre_bubbling_cid = $this->createCacheID($pre_bubbling_elements);
        // Two-tier caching: detect different CID post-bubbling, create redirect,
        // update redirect if different set of cache contexts.
        // @see \Drupal\Core\Render\RendererInterface::render()
        // @see ::get()
        if ($pre_bubbling_cid && $pre_bubbling_cid !== $cid) {
            // The cache redirection strategy we're implementing here is pretty
            // simple in concept. Suppose we have the following render structure:
            // - A (pre-bubbling, specifies #cache['keys'] = ['foo'])
            // -- B (specifies #cache['contexts'] = ['b'])
            //
            // At the time that we're evaluating whether A's rendering can be
            // retrieved from cache, we won't know the contexts required by its
            // children (the children might not even be built yet), so cacheGet()
            // will only be able to get what is cached for a $cid of 'foo'. But at
            // the time we're writing to that cache, we do know all the contexts that
            // were specified by all children, so what we need is a way to
            // persist that information between the cache write and the next cache
            // read. So, what we can do is store the following into 'foo':
            // [
            //   '#cache_redirect' => TRUE,
            //   '#cache' => [
            //     ...
            //     'contexts' => ['b'],
            //   ],
            // ]
            //
            // This efficiently lets cacheGet() redirect to a $cid that includes all
            // of the required contexts. The strategy is on-demand: in the case where
            // there aren't any additional contexts required by children that aren't
            // already included in the parent's pre-bubbled #cache information, no
            // cache redirection is needed.
            //
            // When implementing this redirection strategy, special care is needed to
            // resolve potential cache ping-pong problems. For example, consider the
            // following render structure:
            // - A (pre-bubbling, specifies #cache['keys'] = ['foo'])
            // -- B (pre-bubbling, specifies #cache['contexts'] = ['b'])
            // --- C (pre-bubbling, specifies #cache['contexts'] = ['c'])
            // --- D (pre-bubbling, specifies #cache['contexts'] = ['d'])
            //
            // Additionally, suppose that:
            // - C only exists for a 'b' context value of 'b1'
            // - D only exists for a 'b' context value of 'b2'
            // This is an acceptable variation, since B specifies that its contents
            // vary on context 'b'.
            //
            // A naive implementation of cache redirection would result in the
            // following:
            // - When a request is processed where context 'b' = 'b1', what would be
            //   cached for a $pre_bubbling_cid of 'foo' is:
            //   [
            //     '#cache_redirect' => TRUE,
            //     '#cache' => [
            //       ...
            //       'contexts' => ['b', 'c'],
            //     ],
            //   ]
            // - When a request is processed where context 'b' = 'b2', we would
            //   retrieve the above from cache, but when following that redirection,
            //   get a cache miss, since we're processing a 'b' context value that
            //   has not yet been cached. Given the cache miss, we would continue
            //   with rendering the structure, perform the required context bubbling
            //   and then overwrite the above item with:
            //   [
            //     '#cache_redirect' => TRUE,
            //     '#cache' => [
            //       ...
            //       'contexts' => ['b', 'd'],
            //     ],
            //   ]
            // - Now, if a request comes in where context 'b' = 'b1' again, the above
            //   would redirect to a cache key that doesn't exist, since we have not
            //   yet cached an item that includes 'b'='b1' and something for 'd'. So
            //   we would process this request as a cache miss, at the end of which,
            //   we would overwrite the above item back to:
            //   [
            //     '#cache_redirect' => TRUE,
            //     '#cache' => [
            //       ...
            //       'contexts' => ['b', 'c'],
            //     ],
            //   ]
            // - The above would always result in accurate renderings, but would
            //   result in poor performance as we keep processing requests as cache
            //   misses even though the target of the redirection is cached, and
            //   it's only the redirection element itself that is creating the
            //   ping-pong problem.
            //
            // A way to resolve the ping-pong problem is to eventually reach a cache
            // state where the redirection element includes all of the contexts used
            // throughout all requests:
            // [
            //   '#cache_redirect' => TRUE,
            //   '#cache' => [
            //     ...
            //     'contexts' => ['b', 'c', 'd'],
            //   ],
            // ]
            //
            // We can't reach that state right away, since we don't know what the
            // result of future requests will be, but we can incrementally move
            // towards that state by progressively merging the 'contexts' value
            // across requests. That's the strategy employed below and tested in
            // \Drupal\Tests\Core\Render\RendererBubblingTest::testConditionalCacheContextBubblingSelfHealing().
            // Get the cacheability of this element according to the current (stored)
            // redirecting cache item, if any.
            $redirect_cacheability = new CacheableMetadata();
            if ($stored_cache_redirect = $cache->get($pre_bubbling_cid)) {
                $redirect_cacheability = CacheableMetadata::createFromRenderArray($stored_cache_redirect->data);
            }
            // Calculate the union of the cacheability for this request and the
            // current (stored) redirecting cache item. We need:
            // - the union of cache contexts, because that is how we know which cache
            //   item to redirect to;
            // - the union of cache tags, because that is how we know when the cache
            //   redirect cache item itself is invalidated;
            // - the union of max ages, because that is how we know when the cache
            //   redirect cache item itself becomes stale. (Without this, we might end
            //   up toggling between a permanently and a briefly cacheable cache
            //   redirect, because the last update's max-age would always "win".)
            $redirect_cacheability_updated = CacheableMetadata::createFromRenderArray($data)->merge($redirect_cacheability);
            // Stored cache contexts incomplete: this request causes cache contexts to
            // be added to the redirecting cache item.
            if (array_diff($redirect_cacheability_updated->getCacheContexts(), $redirect_cacheability->getCacheContexts())) {
                $redirect_data = [
                    '#cache_redirect' => TRUE,
                    '#cache' => [
                        // The cache keys of the current element; this remains the same
                        // across requests.
'keys' => $elements['#cache']['keys'],
                        // The union of the current element's and stored cache contexts.
'contexts' => $redirect_cacheability_updated->getCacheContexts(),
                        // The union of the current element's and stored cache tags.
'tags' => $redirect_cacheability_updated->getCacheTags(),
                        // The union of the current element's and stored cache max-ages.
'max-age' => $redirect_cacheability_updated->getCacheMaxAge(),
                        // The same cache bin as the one for the actual render cache items.
'bin' => $bin,
                    ],
                ];
                $cache->set($pre_bubbling_cid, $redirect_data, $this->maxAgeToExpire($redirect_cacheability_updated->getCacheMaxAge()), Cache::mergeTags($redirect_data['#cache']['tags'], [
                    'rendered',
                ]));
            }
            // Current cache contexts incomplete: this request only uses a subset of
            // the cache contexts stored in the redirecting cache item. Vary by these
            // additional (conditional) cache contexts as well, otherwise the
            // redirecting cache item would be pointing to a cache item that can never
            // exist.
            if (array_diff($redirect_cacheability_updated->getCacheContexts(), $data['#cache']['contexts'])) {
                // Recalculate the cache ID.
                $recalculated_cid_pseudo_element = [
                    '#cache' => [
                        'keys' => $elements['#cache']['keys'],
                        'contexts' => $redirect_cacheability_updated->getCacheContexts(),
                    ],
                ];
                $cid = $this->createCacheID($recalculated_cid_pseudo_element);
                // Ensure the about-to-be-cached data uses the merged cache contexts.
                $data['#cache']['contexts'] = $redirect_cacheability_updated->getCacheContexts();
            }
        }
        $cache->set($cid, $data, $this->maxAgeToExpire($elements['#cache']['max-age']), Cache::mergeTags($data['#cache']['tags'], [
            'rendered',
        ]));
    }
    
    /**
     * Maps a #cache[max-age] value to an "expire" value for the Cache API.
     *
     * @param int $max_age
     *   A #cache[max-age] value.
     *
     * @return int
     *   A corresponding "expire" value.
     *
     * @see \Drupal\Core\Cache\CacheBackendInterface::set()
     */
    protected function maxAgeToExpire($max_age) {
        return $max_age === Cache::PERMANENT ? Cache::PERMANENT : (int) $this->requestStack
            ->getMasterRequest()->server
            ->get('REQUEST_TIME') + $max_age;
    }
    
    /**
     * Creates the cache ID for a renderable element.
     *
     * Creates the cache ID string based on #cache['keys'] + #cache['contexts'].
     *
     * @param array &$elements
     *   A renderable array.
     *
     * @return string
     *   The cache ID string, or FALSE if the element may not be cached.
     */
    protected function createCacheID(array &$elements) {
        // If the maximum age is zero, then caching is effectively prohibited.
        if (isset($elements['#cache']['max-age']) && $elements['#cache']['max-age'] === 0) {
            return FALSE;
        }
        if (isset($elements['#cache']['keys'])) {
            $cid_parts = $elements['#cache']['keys'];
            if (!empty($elements['#cache']['contexts'])) {
                $context_cache_keys = $this->cacheContextsManager
                    ->convertTokensToKeys($elements['#cache']['contexts']);
                $cid_parts = array_merge($cid_parts, $context_cache_keys->getKeys());
                CacheableMetadata::createFromRenderArray($elements)->merge($context_cache_keys)
                    ->applyTo($elements);
            }
            return implode(':', $cid_parts);
        }
        return FALSE;
    }
    
    /**
     * {@inheritdoc}
     */
    public function getCacheableRenderArray(array $elements) {
        $data = [
            '#markup' => $elements['#markup'],
            '#attached' => $elements['#attached'],
            '#cache' => [
                'contexts' => $elements['#cache']['contexts'],
                'tags' => $elements['#cache']['tags'],
                'max-age' => $elements['#cache']['max-age'],
            ],
        ];
        // Preserve cacheable items if specified. If we are preserving any cacheable
        // children of the element, we assume we are only interested in their
        // individual markup and not the parent's one, thus we empty it to minimize
        // the cache entry size.
        if (!empty($elements['#cache_properties']) && is_array($elements['#cache_properties'])) {
            $data['#cache_properties'] = $elements['#cache_properties'];
            // Extract all the cacheable items from the element using cache
            // properties.
            $cacheable_items = array_intersect_key($elements, array_flip($elements['#cache_properties']));
            $cacheable_children = Element::children($cacheable_items);
            if ($cacheable_children) {
                $data['#markup'] = '';
                // Cache only cacheable children's markup.
                foreach ($cacheable_children as $key) {
                    // We can assume that #markup is safe at this point.
                    $cacheable_items[$key] = [
                        '#markup' => Markup::create($cacheable_items[$key]['#markup']),
                    ];
                }
            }
            $data += $cacheable_items;
        }
        $data['#markup'] = Markup::create($data['#markup']);
        return $data;
    }

}