class BookManager

class BookManager implements BookManagerInterface {
  use StringTranslationTrait;

  /**
   * Defines the maximum supported depth of the book tree.
   */
  const BOOK_MAX_DEPTH = 9;

  /**
   * Entity type manager.
   *
   * @var \Drupal\Core\Entity\EntityTypeManagerInterface
   */
  protected $entityTypeManager;

  /**
   * Config Factory Service Object.
   *
   * @var \Drupal\Core\Config\ConfigFactoryInterface
   */
  protected $configFactory;

  /**
   * Books Array.
   *
   * @var array
   */
  protected $books;

  /**
   * Book outline storage.
   *
   * @var \Drupal\book\BookOutlineStorageInterface
   */
  protected $bookOutlineStorage;

  /**
   * Stores flattened book trees.
   *
   * @var array
   */
  protected $bookTreeFlattened;

  /**
   * The renderer.
   *
   * @var \Drupal\Core\Render\RendererInterface
   */
  protected $renderer;

  /**
   * The entity repository service.
   *
   * @var \Drupal\Core\Entity\EntityRepositoryInterface
   */
  protected $entityRepository;

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

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

  /**
   * The book memory cache service.
   *
   * @var \Drupal\Core\Cache\CacheBackendInterface
   */
  protected $memoryCache;

  /**
   * Constructs a BookManager object.
   *
   * @param \Drupal\Core\Entity\EntityTypeManagerInterface $entity_type_manager
   *   The entity type manager.
   * @param \Drupal\Core\StringTranslation\TranslationInterface $translation
   *   The string translation service.
   * @param \Drupal\Core\Config\ConfigFactoryInterface $config_factory
   *   The config factory.
   * @param \Drupal\book\BookOutlineStorageInterface $book_outline_storage
   *   The book outline storage.
   * @param \Drupal\Core\Render\RendererInterface $renderer
   *   The renderer.
   * @param \Drupal\Core\Language\LanguageManagerInterface $language_manager
   *   The language manager.
   * @param \Drupal\Core\Entity\EntityRepositoryInterface $entity_repository
   *   The entity repository service.
   * @param \Drupal\Core\Cache\CacheBackendInterface $backend_chained_cache
   *   The book chained backend cache service.
   * @param \Drupal\Core\Cache\CacheBackendInterface $memory_cache
   *   The book memory cache service.
   */
  public function __construct(EntityTypeManagerInterface $entity_type_manager, TranslationInterface $translation, ConfigFactoryInterface $config_factory, BookOutlineStorageInterface $book_outline_storage, RendererInterface $renderer, LanguageManagerInterface $language_manager, EntityRepositoryInterface $entity_repository, CacheBackendInterface $backend_chained_cache, CacheBackendInterface $memory_cache) {
    $this->entityTypeManager = $entity_type_manager;
    $this->stringTranslation = $translation;
    $this->configFactory = $config_factory;
    $this->bookOutlineStorage = $book_outline_storage;
    $this->renderer = $renderer;
    $this->languageManager = $language_manager;
    $this->entityRepository = $entity_repository;
    $this->backendChainedCache = $backend_chained_cache;
    $this->memoryCache = $memory_cache;
  }

  /**
   * {@inheritdoc}
   */
  public function getAllBooks() {
    if (!isset($this->books)) {
      $this
        ->loadBooks();
    }
    return $this->books;
  }

  /**
   * Loads Books Array.
   */
  protected function loadBooks() {
    $this->books = [];
    $nids = $this->bookOutlineStorage
      ->getBooks();
    if ($nids) {
      $book_links = $this->bookOutlineStorage
        ->loadMultiple($nids);

      // Load nodes with proper translation.
      $nodes = $this->entityTypeManager
        ->getStorage('node')
        ->loadMultiple($nids);
      $nodes = array_map([
        $this->entityRepository,
        'getTranslationFromContext',
      ], $nodes);

      // @todo Sort by weight and translated title.
      // @todo use route name for links, not system path.
      foreach ($book_links as $link) {
        $nid = $link['nid'];
        if (isset($nodes[$nid]) && $nodes[$nid]
          ->access('view')) {
          $link['url'] = $nodes[$nid]
            ->toUrl();
          $link['title'] = $nodes[$nid]
            ->label();
          $link['type'] = $nodes[$nid]
            ->bundle();
          $this->books[$link['bid']] = $link;
        }
      }
    }
  }

  /**
   * {@inheritdoc}
   */
  public function getLinkDefaults($nid) {
    return [
      'original_bid' => 0,
      'nid' => $nid,
      'bid' => 0,
      'pid' => 0,
      'has_children' => 0,
      'weight' => 0,
      'options' => [],
    ];
  }

  /**
   * {@inheritdoc}
   */
  public function getParentDepthLimit(array $book_link) {
    return static::BOOK_MAX_DEPTH - 1 - ($book_link['bid'] && $book_link['has_children'] ? $this
      ->findChildrenRelativeDepth($book_link) : 0);
  }

  /**
   * Determine the relative depth of the children of a given book link.
   *
   * @param array $book_link
   *   The book link.
   *
   * @return int
   *   The difference between the max depth in the book tree and the depth of
   *   the passed book link.
   */
  protected function findChildrenRelativeDepth(array $book_link) {
    $max_depth = $this->bookOutlineStorage
      ->getChildRelativeDepth($book_link, static::BOOK_MAX_DEPTH);
    return $max_depth > $book_link['depth'] ? $max_depth - $book_link['depth'] : 0;
  }

  /**
   * {@inheritdoc}
   */
  public function addFormElements(array $form, FormStateInterface $form_state, NodeInterface $node, AccountInterface $account, $collapsed = TRUE) {

    // If the form is being processed during the Ajax callback of our book bid
    // dropdown, then $form_state will hold the value that was selected.
    if ($form_state
      ->hasValue('book')) {
      $node->book = $form_state
        ->getValue('book');
    }
    $form['book'] = [
      '#type' => 'details',
      '#title' => $this
        ->t('Book outline'),
      '#weight' => 10,
      '#open' => !$collapsed,
      '#group' => 'advanced',
      '#attributes' => [
        'class' => [
          'book-outline-form',
        ],
      ],
      '#attached' => [
        'library' => [
          'book/drupal.book',
        ],
      ],
      '#tree' => TRUE,
    ];
    foreach ([
      'nid',
      'has_children',
      'original_bid',
      'parent_depth_limit',
    ] as $key) {
      $form['book'][$key] = [
        '#type' => 'value',
        '#value' => $node->book[$key],
      ];
    }
    $form['book']['pid'] = $this
      ->addParentSelectFormElements($node->book);

    // @see \Drupal\book\Form\BookAdminEditForm::bookAdminTableTree(). The
    // weight may be larger than 15.
    $form['book']['weight'] = [
      '#type' => 'weight',
      '#title' => $this
        ->t('Weight'),
      '#default_value' => $node->book['weight'],
      '#delta' => max(15, abs($node->book['weight'])),
      '#weight' => 5,
      '#description' => $this
        ->t('Pages at a given level are ordered first by weight and then by title.'),
    ];
    $options = [];
    $nid = !$node
      ->isNew() ? $node
      ->id() : 'new';
    if ($node
      ->id() && $nid == $node->book['original_bid'] && $node->book['parent_depth_limit'] == 0) {

      // This is the top level node in a maximum depth book and thus cannot be
      // moved.
      $options[$node
        ->id()] = $node
        ->label();
    }
    else {
      foreach ($this
        ->getAllBooks() as $book) {
        $options[$book['nid']] = $book['title'];
      }
    }
    if ($account
      ->hasPermission('create new books') && ($nid == 'new' || $nid != $node->book['original_bid'])) {

      // The node can become a new book, if it is not one already.
      $options = [
        $nid => $this
          ->t('- Create a new book -'),
      ] + $options;
    }
    if (!$node->book['bid'] || $nid === 'new' || $node->book['original_bid'] === 0) {

      // The node is not currently in the hierarchy.
      $options = [
        0 => $this
          ->t('- None -'),
      ] + $options;
    }

    // Add a drop-down to select the destination book.
    $form['book']['bid'] = [
      '#type' => 'select',
      '#title' => $this
        ->t('Book'),
      '#default_value' => $node->book['bid'],
      '#options' => $options,
      '#access' => (bool) $options,
      '#description' => $this
        ->t('Your page will be a part of the selected book.'),
      '#weight' => -5,
      '#attributes' => [
        'class' => [
          'book-title-select',
        ],
      ],
      '#ajax' => [
        'callback' => 'book_form_update',
        'wrapper' => 'edit-book-plid-wrapper',
        'effect' => 'fade',
        'speed' => 'fast',
      ],
    ];
    return $form;
  }

  /**
   * {@inheritdoc}
   */
  public function checkNodeIsRemovable(NodeInterface $node) {
    return !empty($node->book['bid']) && ($node->book['bid'] != $node
      ->id() || !$node->book['has_children']);
  }

  /**
   * {@inheritdoc}
   */
  public function updateOutline(NodeInterface $node) {
    if (empty($node->book['bid'])) {
      return FALSE;
    }
    if (!empty($node->book['bid'])) {
      if ($node->book['bid'] == 'new') {

        // New nodes that are their own book.
        $node->book['bid'] = $node
          ->id();
      }
      elseif (!isset($node->book['original_bid'])) {
        $node->book['original_bid'] = $node->book['bid'];
      }
    }

    // Ensure we create a new book link if either the node itself is new, or the
    // bid was selected the first time, so that the original_bid is still empty.
    $new = empty($node->book['nid']) || empty($node->book['original_bid']);
    $node->book['nid'] = $node
      ->id();

    // Create a new book from a node.
    if ($node->book['bid'] == $node
      ->id()) {
      $node->book['pid'] = 0;
    }
    elseif ($node->book['pid'] < 0) {

      // -1 is the default value in BookManager::addParentSelectFormElements().
      // The node save should have set the bid equal to the node ID, but
      // handle it here if it did not.
      $node->book['pid'] = $node->book['bid'];
    }

    // Prevent changes to the book outline if the node being saved is not the
    // default revision.
    $updated = FALSE;
    if (!$new) {
      $original = $this
        ->loadBookLink($node
        ->id(), FALSE);
      if ($node->book['bid'] != $original['bid'] || $node->book['pid'] != $original['pid'] || $node->book['weight'] != $original['weight']) {
        $updated = TRUE;
      }
    }
    if (($new || $updated) && !$node
      ->isDefaultRevision()) {
      return FALSE;
    }
    return $this
      ->saveBookLink($node->book, $new);
  }

  /**
   * {@inheritdoc}
   */
  public function getBookParents(array $item, array $parent = []) {
    $book = [];
    if ($item['pid'] == 0) {
      $book['p1'] = $item['nid'];
      for ($i = 2; $i <= static::BOOK_MAX_DEPTH; $i++) {
        $parent_property = "p{$i}";
        $book[$parent_property] = 0;
      }
      $book['depth'] = 1;
    }
    else {
      $i = 1;
      $book['depth'] = $parent['depth'] + 1;
      while ($i < $book['depth']) {
        $p = 'p' . $i++;
        $book[$p] = $parent[$p];
      }
      $p = 'p' . $i++;

      // The parent (p1 - p9) corresponding to the depth always equals the nid.
      $book[$p] = $item['nid'];
      while ($i <= static::BOOK_MAX_DEPTH) {
        $p = 'p' . $i++;
        $book[$p] = 0;
      }
    }
    return $book;
  }

  /**
   * Builds the parent selection form element for the node form or outline tab.
   *
   * This function is also called when generating a new set of options during
   * the Ajax callback, so an array is returned that can be used to replace an
   * existing form element.
   *
   * @param array $book_link
   *   A fully loaded book link that is part of the book hierarchy.
   *
   * @return array
   *   A parent selection form element.
   */
  protected function addParentSelectFormElements(array $book_link) {
    $config = $this->configFactory
      ->get('book.settings');
    if ($config
      ->get('override_parent_selector')) {
      return [];
    }

    // Offer a message or a drop-down to choose a different parent page.
    $form = [
      '#type' => 'hidden',
      '#value' => -1,
      '#prefix' => '<div id="edit-book-plid-wrapper">',
      '#suffix' => '</div>',
    ];
    if ($book_link['nid'] === $book_link['bid']) {

      // This is a book - at the top level.
      if ($book_link['original_bid'] === $book_link['bid']) {
        $form['#prefix'] .= '<em>' . $this
          ->t('This is the top-level page in this book.') . '</em>';
      }
      else {
        $form['#prefix'] .= '<em>' . $this
          ->t('This will be the top-level page in this book.') . '</em>';
      }
    }
    elseif (!$book_link['bid']) {
      $form['#prefix'] .= '<em>' . $this
        ->t('No book selected.') . '</em>';
    }
    else {
      $form = [
        '#type' => 'select',
        '#title' => $this
          ->t('Parent item'),
        '#default_value' => $book_link['pid'],
        '#description' => $this
          ->t('The parent page in the book. The maximum depth for a book and all child pages is @maxdepth. Some pages in the selected book may not be available as parents if selecting them would exceed this limit.', [
          '@maxdepth' => static::BOOK_MAX_DEPTH,
        ]),
        '#options' => $this
          ->getTableOfContents($book_link['bid'], $book_link['parent_depth_limit'], [
          $book_link['nid'],
        ]),
        '#attributes' => [
          'class' => [
            'book-title-select',
          ],
        ],
        '#prefix' => '<div id="edit-book-plid-wrapper">',
        '#suffix' => '</div>',
      ];
    }
    $this->renderer
      ->addCacheableDependency($form, $config);
    return $form;
  }

  /**
   * Recursively processes and formats book links for getTableOfContents().
   *
   * This helper function recursively modifies the table of contents array for
   * each item in the book tree, ignoring items in the exclude array or at a
   * depth greater than the limit. Truncates titles over thirty characters and
   * appends an indentation string incremented by depth.
   *
   * @param array $tree
   *   The data structure of the book's outline tree. Includes hidden links.
   * @param string $indent
   *   A string appended to each node title. Increments by '--' per depth
   *   level.
   * @param array $toc
   *   Reference to the table of contents array. This is modified in place, so
   *   the function does not have a return value.
   * @param array $exclude
   *   Optional array of Node ID values. Any link whose node ID is in this
   *   array will be excluded (along with its children).
   * @param int $depth_limit
   *   Any link deeper than this value will be excluded (along with its
   *   children).
   */
  protected function recurseTableOfContents(array $tree, $indent, array &$toc, array $exclude, $depth_limit) {
    $nids = [];
    foreach ($tree as $data) {
      if ($data['link']['depth'] > $depth_limit) {

        // Don't iterate through any links on this level.
        return;
      }
      if (!in_array($data['link']['nid'], $exclude)) {
        $nids[] = $data['link']['nid'];
      }
    }

    // Load nodes with proper translation.
    $nodes = $this->entityTypeManager
      ->getStorage('node')
      ->loadMultiple($nids);
    $nodes = array_map([
      $this->entityRepository,
      'getTranslationFromContext',
    ], $nodes);
    foreach ($tree as $data) {
      $nid = $data['link']['nid'];

      // Check for excluded or missing node.
      if (empty($nodes[$nid])) {
        continue;
      }
      $toc[$nid] = $indent . ' ' . Unicode::truncate($nodes[$nid]
        ->label(), 30, TRUE, TRUE);
      if ($data['below']) {
        $this
          ->recurseTableOfContents($data['below'], $indent . '--', $toc, $exclude, $depth_limit);
      }
    }
  }

  /**
   * {@inheritdoc}
   */
  public function getTableOfContents($bid, $depth_limit, array $exclude = []) {
    $tree = $this
      ->bookTreeAllData($bid);
    $toc = [];
    $this
      ->recurseTableOfContents($tree, '', $toc, $exclude, $depth_limit);
    return $toc;
  }

  /**
   * {@inheritdoc}
   */
  public function deleteFromBook($nid) {
    $original = $this
      ->loadBookLink($nid, FALSE);
    $this->bookOutlineStorage
      ->delete($nid);
    if ($nid == $original['bid']) {

      // Handle deletion of a top-level post.
      $result = $this->bookOutlineStorage
        ->loadBookChildren($nid);
      $children = $this->entityTypeManager
        ->getStorage('node')
        ->loadMultiple(array_keys($result));
      foreach ($children as $child) {
        $child->book['bid'] = $child
          ->id();
        $this
          ->updateOutline($child);
      }
    }
    $this
      ->updateOriginalParent($original);
    $this->books = NULL;
    Cache::invalidateTags([
      'bid:' . $original['bid'],
    ]);
  }

  /**
   * {@inheritdoc}
   */
  public function bookTreeAllData($bid, $link = NULL, $max_depth = NULL) {

    // Use $nid as flag for whether the data being loaded is for the whole tree.
    $nid = $link['nid'] ?? 0;
    $langcode = $this->languageManager
      ->getCurrentLanguage(LanguageInterface::TYPE_CONTENT)
      ->getId();

    // Create a cache ID for the given $nid, $link, $langcode and $max_depth.
    $cid = implode(':', [
      'book-links',
      $bid,
      $nid,
      $langcode,
      (int) $max_depth,
    ]);

    // Get it from cache, if available.
    if ($cache = $this->memoryCache
      ->get($cid)) {
      return $cache->data;
    }

    // If the tree data was not in the static cache, build $tree_parameters.
    $tree_parameters = [
      'min_depth' => 1,
      'max_depth' => $max_depth,
    ];
    if ($nid) {
      $active_trail = $this
        ->getActiveTrailIds($bid, $link);
      $tree_parameters['expanded'] = $active_trail;
      $tree_parameters['active_trail'] = $active_trail;
      $tree_parameters['active_trail'][] = $nid;
    }

    // Build the tree using the parameters.
    $tree_build = $this
      ->bookTreeBuild($bid, $tree_parameters);

    // Cache the tree build in memory.
    $this->memoryCache
      ->set($cid, $tree_build);
    return $tree_build;
  }

  /**
   * {@inheritdoc}
   */
  public function getActiveTrailIds($bid, $link) {

    // The tree is for a single item, so we need to match the values in its
    // p columns and 0 (the top level) with the plid values of other links.
    $active_trail = [
      0,
    ];
    for ($i = 1; $i < static::BOOK_MAX_DEPTH; $i++) {
      if (!empty($link["p{$i}"])) {
        $active_trail[] = $link["p{$i}"];
      }
    }
    return $active_trail;
  }

  /**
   * {@inheritdoc}
   */
  public function bookTreeOutput(array $tree) {
    $items = $this
      ->buildItems($tree);
    $build = [];
    if ($items) {

      // Make sure Drupal\Core\Render\Element::children() does not re-order the
      // links.
      $build['#sorted'] = TRUE;

      // Get the book id from the last link.
      $item = end($items);

      // Add the theme wrapper for outer markup.
      // Allow menu-specific theme overrides.
      $build['#theme'] = 'book_tree__book_toc_' . $item['original_link']['bid'];
      $build['#items'] = $items;

      // Set cache tag.
      $build['#cache']['tags'][] = 'config:system.book.' . $item['original_link']['bid'];
    }
    return $build;
  }

  /**
   * Builds the #items property for a book tree's renderable array.
   *
   * Helper function for ::bookTreeOutput().
   *
   * @param array $tree
   *   A data structure representing the tree.
   *
   * @return array
   *   The value to use for the #items property of a renderable menu.
   */
  protected function buildItems(array $tree) {
    $items = [];
    foreach ($tree as $data) {
      $element = [];

      // Generally we only deal with visible links, but just in case.
      if (!$data['link']['access']) {
        continue;
      }

      // Set a class for the <li> tag. Since $data['below'] may contain local
      // tasks, only set 'expanded' to true if the link also has children within
      // the current book.
      $element['is_expanded'] = FALSE;
      $element['is_collapsed'] = FALSE;
      if ($data['link']['has_children'] && $data['below']) {
        $element['is_expanded'] = TRUE;
      }
      elseif ($data['link']['has_children']) {
        $element['is_collapsed'] = TRUE;
      }

      // Set a helper variable to indicate whether the link is in the active
      // trail.
      $element['in_active_trail'] = FALSE;
      if ($data['link']['in_active_trail']) {
        $element['in_active_trail'] = TRUE;
      }

      // Allow book-specific theme overrides.
      $element['attributes'] = new Attribute();
      $element['title'] = $data['link']['title'];
      $element['url'] = Url::fromUri('entity:node/' . $data['link']['nid'], [
        'language' => $this->languageManager
          ->getCurrentLanguage(LanguageInterface::TYPE_CONTENT),
      ]);
      $element['localized_options'] = !empty($data['link']['localized_options']) ? $data['link']['localized_options'] : [];
      $element['localized_options']['set_active_class'] = TRUE;
      $element['below'] = $data['below'] ? $this
        ->buildItems($data['below']) : [];
      $element['original_link'] = $data['link'];

      // Index using the link's unique nid.
      $items[$data['link']['nid']] = $element;
    }
    return $items;
  }

  /**
   * Builds a book tree, translates links, and checks access.
   *
   * @param int $bid
   *   The Book ID to find links for.
   * @param array $parameters
   *   (optional) An associative array of build parameters. Possible keys:
   *   - expanded: An array of parent link IDs to return only book links that
   *     are children of one of the parent link IDs in this list. If empty,
   *     the whole outline is built, unless 'only_active_trail' is TRUE.
   *   - active_trail: An array of node IDs, representing the currently active
   *     book link.
   *   - only_active_trail: Whether to only return links that are in the active
   *     trail. This option is ignored if 'expanded' is non-empty.
   *   - min_depth: The minimum depth of book links in the resulting tree.
   *     Defaults to 1, which is to build the whole tree for the book.
   *   - max_depth: The maximum depth of book links in the resulting tree.
   *   - conditions: An associative array of custom database select query
   *     condition key/value pairs; see
   *     \Drupal\book\BookOutlineStorage::getBookMenuTree() for the actual
   *     query.
   *
   * @return array
   *   A fully built book tree.
   */
  protected function bookTreeBuild($bid, array $parameters = []) {

    // Build the book tree.
    $data = $this
      ->doBookTreeBuild($bid, $parameters);

    // Check access for the current user to each item in the tree.
    $this
      ->bookTreeCheckAccess($data['tree'], $data['node_links']);
    return $data['tree'];
  }

  /**
   * Builds a book tree.
   *
   * This function may be used build the data for a menu tree only, for example
   * to further massage the data manually before further processing happens.
   * _menu_tree_check_access() needs to be invoked afterwards.
   *
   * @param int $bid
   *   The book ID to find links for.
   * @param array $parameters
   *   (optional) An associative array of build parameters. Possible keys:
   *   - expanded: An array of parent link IDs to return only book links that
   *     are children of one of the parent link IDs in this list. If empty,
   *     the whole outline is built, unless 'only_active_trail' is TRUE.
   *   - active_trail: An array of node IDs, representing the currently active
   *     book link.
   *   - only_active_trail: Whether to only return links that are in the active
   *     trail. This option is ignored if 'expanded' is non-empty.
   *   - min_depth: The minimum depth of book links in the resulting tree.
   *     Defaults to 1, which is to build the whole tree for the book.
   *   - max_depth: The maximum depth of book links in the resulting tree.
   *   - conditions: An associative array of custom database select query
   *     condition key/value pairs; see
   *     \Drupal\book\BookOutlineStorage::getBookMenuTree() for the actual
   *     query.
   *
   * @return array
   *   An array with links representing the tree structure of the book.
   *
   * @see \Drupal\book\BookOutlineStorageInterface::getBookMenuTree()
   */
  protected function doBookTreeBuild($bid, array $parameters = []) {

    // Build the cache id; sort parents to prevent duplicate storage and remove
    // default parameter values.
    if (isset($parameters['expanded'])) {
      sort($parameters['expanded']);
    }
    $langcode = $this->languageManager
      ->getCurrentLanguage(LanguageInterface::TYPE_CONTENT)
      ->getId();
    $cid = implode(':', [
      'book-links',
      $bid,
      'tree-data',
      $langcode,
      hash('sha256', serialize($parameters)),
    ]);

    // Get it from cache, if available.
    if ($cache = $this->backendChainedCache
      ->get($cid)) {
      return $cache->data;
    }
    $min_depth = $parameters['min_depth'] ?? 1;
    $result = $this->bookOutlineStorage
      ->getBookMenuTree($bid, $parameters, $min_depth, static::BOOK_MAX_DEPTH);

    // Build an ordered array of links using the query result object.
    $links = [];
    foreach ($result as $link) {
      $link = (array) $link;
      $links[$link['nid']] = $link;
    }
    $active_trail = $parameters['active_trail'] ?? [];
    $data['tree'] = $this
      ->buildBookOutlineData($links, $active_trail, $min_depth);
    $data['node_links'] = [];
    $this
      ->bookTreeCollectNodeLinks($data['tree'], $data['node_links']);

    // Cache tree data.
    $this->backendChainedCache
      ->set($cid, $data, Cache::PERMANENT, [
      'bid:' . $bid,
    ]);
    return $data;
  }

  /**
   * {@inheritdoc}
   */
  public function bookTreeCollectNodeLinks(&$tree, &$node_links) {

    // All book links are nodes.
    // @todo clean this up.
    foreach ($tree as $key => $v) {
      $nid = $v['link']['nid'];
      $node_links[$nid][$tree[$key]['link']['nid']] =& $tree[$key]['link'];
      $tree[$key]['link']['access'] = FALSE;
      if ($tree[$key]['below']) {
        $this
          ->bookTreeCollectNodeLinks($tree[$key]['below'], $node_links);
      }
    }
  }

  /**
   * {@inheritdoc}
   */
  public function bookTreeGetFlat(array $book_link) {
    if (!isset($this->bookTreeFlattened[$book_link['nid']])) {

      // Call $this->bookTreeAllData() to take advantage of caching.
      $tree = $this
        ->bookTreeAllData($book_link['bid'], $book_link, $book_link['depth'] + 1);
      $this->bookTreeFlattened[$book_link['nid']] = [];
      $this
        ->flatBookTree($tree, $this->bookTreeFlattened[$book_link['nid']]);
    }
    return $this->bookTreeFlattened[$book_link['nid']];
  }

  /**
   * Recursively converts a tree of menu links to a flat array.
   *
   * @param array $tree
   *   A tree of menu links in an array.
   * @param array $flat
   *   A flat array of the menu links from $tree, passed by reference.
   *
   * @see static::bookTreeGetFlat()
   */
  protected function flatBookTree(array $tree, array &$flat) {
    foreach ($tree as $data) {
      $flat[$data['link']['nid']] = $data['link'];
      if ($data['below']) {
        $this
          ->flatBookTree($data['below'], $flat);
      }
    }
  }

  /**
   * {@inheritdoc}
   */
  public function loadBookLink($nid, $translate = TRUE) {
    $links = $this
      ->loadBookLinks([
      $nid,
    ], $translate);
    return $links[$nid] ?? FALSE;
  }

  /**
   * {@inheritdoc}
   */
  public function loadBookLinks($nids, $translate = TRUE) {
    $result = $this->bookOutlineStorage
      ->loadMultiple($nids, $translate);
    $links = [];
    foreach ($result as $link) {
      if ($translate) {
        $this
          ->bookLinkTranslate($link);
      }
      $links[$link['nid']] = $link;
    }
    return $links;
  }

  /**
   * {@inheritdoc}
   */
  public function saveBookLink(array $link, $new) {

    // Keep track of Book IDs for cache clear.
    $affected_bids[$link['bid']] = $link['bid'];
    $link += $this
      ->getLinkDefaults($link['nid']);
    if ($new) {

      // Insert new.
      $parents = $this
        ->getBookParents($link, (array) $this
        ->loadBookLink($link['pid'], FALSE));
      $this->bookOutlineStorage
        ->insert($link, $parents);

      // Update the has_children status of the parent.
      $this
        ->updateParent($link);
    }
    else {
      $original = $this
        ->loadBookLink($link['nid'], FALSE);

      // Using the Book ID as the key keeps this unique.
      $affected_bids[$original['bid']] = $original['bid'];

      // Handle links that are moving.
      if ($link['bid'] != $original['bid'] || $link['pid'] != $original['pid']) {

        // Update the bid for this page and all children.
        if ($link['pid'] == 0) {
          $link['depth'] = 1;
          $parent = [];
        }
        elseif (($parent_link = $this
          ->loadBookLink($link['pid'], FALSE)) && $parent_link['bid'] != $link['bid']) {
          $link['pid'] = $link['bid'];
          $parent = $this
            ->loadBookLink($link['pid'], FALSE);
          $link['depth'] = $parent['depth'] + 1;
        }
        else {
          $parent = $this
            ->loadBookLink($link['pid'], FALSE);
          $link['depth'] = $parent['depth'] + 1;
        }
        $this
          ->setParents($link, $parent);
        $this
          ->moveChildren($link, $original);

        // Update the has_children status of the original parent.
        $this
          ->updateOriginalParent($original);

        // Update the has_children status of the new parent.
        $this
          ->updateParent($link);
      }

      // Update the weight and pid.
      $this->bookOutlineStorage
        ->update($link['nid'], [
        'weight' => $link['weight'],
        'pid' => $link['pid'],
        'bid' => $link['bid'],
      ]);
    }
    $cache_tags = [];
    foreach ($affected_bids as $bid) {
      $cache_tags[] = 'bid:' . $bid;
    }
    Cache::invalidateTags($cache_tags);
    return $link;
  }

  /**
   * Moves children from the original parent to the updated link.
   *
   * @param array $link
   *   The link being saved.
   * @param array $original
   *   The original parent of $link.
   */
  protected function moveChildren(array $link, array $original) {
    $p = 'p1';
    $expressions = [];
    for ($i = 1; $i <= $link['depth']; $p = 'p' . ++$i) {
      $expressions[] = [
        $p,
        ":p_{$i}",
        [
          ":p_{$i}" => $link[$p],
        ],
      ];
    }
    $j = $original['depth'] + 1;
    while ($i <= static::BOOK_MAX_DEPTH && $j <= static::BOOK_MAX_DEPTH) {
      $expressions[] = [
        'p' . $i++,
        'p' . $j++,
        [],
      ];
    }
    while ($i <= static::BOOK_MAX_DEPTH) {
      $expressions[] = [
        'p' . $i++,
        0,
        [],
      ];
    }
    $shift = $link['depth'] - $original['depth'];
    if ($shift > 0) {

      // The order of expressions must be reversed so the new values don't
      // overwrite the old ones before they can be used because "Single-table
      // UPDATE assignments are generally evaluated from left to right".
      // @see http://dev.mysql.com/doc/refman/5.0/en/update.html
      $expressions = array_reverse($expressions);
    }
    $this->bookOutlineStorage
      ->updateMovedChildren($link['bid'], $original, $expressions, $shift);
  }

  /**
   * Sets the has_children flag of the parent of the node.
   *
   * This method is mostly called when a book link is moved/created etc. So we
   * want to update the has_children flag of the new parent book link.
   *
   * @param array $link
   *   The book link, data reflecting its new position, whose new parent we want
   *   to update.
   *
   * @return bool
   *   TRUE if the update was successful (either there is no parent to update,
   *   or the parent was updated successfully), FALSE on failure.
   */
  protected function updateParent(array $link) {
    if ($link['pid'] == 0) {

      // Nothing to update.
      return TRUE;
    }
    return $this->bookOutlineStorage
      ->update($link['pid'], [
      'has_children' => 1,
    ]);
  }

  /**
   * Updates the has_children flag of the parent of the original node.
   *
   * This method is called when a book link is moved or deleted. So we want to
   * update the has_children flag of the parent node.
   *
   * @param array $original
   *   The original link whose parent we want to update.
   *
   * @return bool
   *   TRUE if the update was successful (either there was no original parent to
   *   update, or the original parent was updated successfully), FALSE on
   *   failure.
   */
  protected function updateOriginalParent(array $original) {
    if ($original['pid'] == 0) {

      // There were no parents of this link. Nothing to update.
      return TRUE;
    }

    // Check if $original had at least one child.
    $original_number_of_children = $this->bookOutlineStorage
      ->countOriginalLinkChildren($original);
    $parent_has_children = (bool) $original_number_of_children ? 1 : 0;

    // Update the parent. If the original link did not have children, then the
    // parent now does not have children. If the original had children, then the
    // the parent has children now (still).
    return $this->bookOutlineStorage
      ->update($original['pid'], [
      'has_children' => $parent_has_children,
    ]);
  }

  /**
   * Sets the p1 through p9 properties for a book link being saved.
   *
   * @param array $link
   *   The book link to update, passed by reference.
   * @param array $parent
   *   The parent values to set.
   */
  protected function setParents(array &$link, array $parent) {
    $i = 1;
    while ($i < $link['depth']) {
      $p = 'p' . $i++;
      $link[$p] = $parent[$p];
    }
    $p = 'p' . $i++;

    // The parent (p1 - p9) corresponding to the depth always equals the nid.
    $link[$p] = $link['nid'];
    while ($i <= static::BOOK_MAX_DEPTH) {
      $p = 'p' . $i++;
      $link[$p] = 0;
    }
  }

  /**
   * {@inheritdoc}
   */
  public function bookTreeCheckAccess(&$tree, $node_links = []) {
    if ($node_links) {

      // @todo Extract that into its own method.
      $nids = array_keys($node_links);

      // @todo This should be actually filtering on the desired node status
      //   field language and just fall back to the default language.
      $book_links = $this->bookOutlineStorage
        ->loadMultiple($nids);
      foreach ($book_links as $book_link) {
        $nid = $book_link['nid'];
        foreach ($node_links[$nid] as $menu_link_id => $link) {
          $node_links[$nid][$menu_link_id]['access'] = TRUE;
        }
      }
    }
    $this
      ->doBookTreeCheckAccess($tree);
  }

  /**
   * Sorts the menu tree and recursively checks access for each item.
   *
   * @param array $tree
   *   The book tree to operate on.
   */
  protected function doBookTreeCheckAccess(&$tree) {
    $new_tree = [];
    foreach ($tree as $key => $v) {
      $item =& $tree[$key]['link'];
      $this
        ->bookLinkTranslate($item);
      if ($item['access']) {
        if ($tree[$key]['below']) {
          $this
            ->doBookTreeCheckAccess($tree[$key]['below']);
        }

        // The weights are made a uniform 5 digits by adding 50000 as an offset.
        // After calling $this->bookLinkTranslate(), $item['title'] has the
        // translated title. Adding the nid to the end of the index insures that
        // it is unique.
        $new_tree[50000 + $item['weight'] . ' ' . $item['title'] . ' ' . $item['nid']] = $tree[$key];
      }
    }

    // Sort siblings in the tree based on the weights and localized titles.
    ksort($new_tree);
    $tree = $new_tree;
  }

  /**
   * {@inheritdoc}
   */
  public function bookLinkTranslate(&$link) {

    // Check access via the api, since the query node_access tag doesn't check
    // for unpublished nodes.
    // @todo load the nodes en-mass rather than individually.
    // @see https://www.drupal.org/project/drupal/issues/2470896
    $node = $this->entityTypeManager
      ->getStorage('node')
      ->load($link['nid']);
    $link['access'] = $node && $node
      ->access('view');

    // For performance, don't localize a link the user can't access.
    if ($link['access']) {

      // The node label will be the value for the current language.
      $node = $this->entityRepository
        ->getTranslationFromContext($node);
      $link['title'] = $node
        ->label();
      $link['options'] = [];
    }
    return $link;
  }

  /**
   * Sorts and returns the built data representing a book tree.
   *
   * @param array $links
   *   A flat array of book links that are part of the book. Each array element
   *   is an associative array of information about the book link, containing
   *   the fields from the {book} table. This array must be ordered depth-first.
   * @param array $parents
   *   An array of the node ID values that are in the path from the current
   *   page to the root of the book tree.
   * @param int $depth
   *   The minimum depth to include in the returned book tree.
   *
   * @return array
   *   An array of book links in the form of a tree. Each item in the tree is an
   *   associative array containing:
   *   - link: The book link item from $links, with additional element
   *     'in_active_trail' (TRUE if the link ID was in $parents).
   *   - below: An array containing the sub-tree of this item, where each
   *     element is a tree item array with 'link' and 'below' elements. This
   *     array will be empty if the book link has no items in its sub-tree
   *     having a depth greater than or equal to $depth.
   */
  protected function buildBookOutlineData(array $links, array $parents = [], $depth = 1) {

    // Reverse the array so we can use the more efficient array_pop() function.
    $links = array_reverse($links);
    return $this
      ->buildBookOutlineRecursive($links, $parents, $depth);
  }

  /**
   * Builds the data representing a book tree.
   *
   * The function is a bit complex because the rendering of a link depends on
   * the next book link.
   *
   * @param array $links
   *   A flat array of book links that are part of the book. Each array element
   *   is an associative array of information about the book link, containing
   *   the fields from the {book} table. This array must be ordered depth-first.
   * @param array $parents
   *   An array of the node ID values that are in the path from the current page
   *   to the root of the book tree.
   * @param int $depth
   *   The minimum depth to include in the returned book tree.
   *
   * @return array
   *   Book tree.
   */
  protected function buildBookOutlineRecursive(&$links, $parents, $depth) {
    $tree = [];
    while ($item = array_pop($links)) {

      // We need to determine if we're on the path to root so we can later build
      // the correct active trail.
      $item['in_active_trail'] = in_array($item['nid'], $parents);

      // Add the current link to the tree.
      $tree[$item['nid']] = [
        'link' => $item,
        'below' => [],
      ];

      // Look ahead to the next link, but leave it on the array so it's
      // available to other recursive function calls if we return or build a
      // sub-tree.
      $next = end($links);

      // Check whether the next link is the first in a new sub-tree.
      if ($next && $next['depth'] > $depth) {

        // Recursively call buildBookOutlineRecursive to build the sub-tree.
        $tree[$item['nid']]['below'] = $this
          ->buildBookOutlineRecursive($links, $parents, $next['depth']);

        // Fetch next link after filling the sub-tree.
        $next = end($links);
      }

      // Determine if we should exit the loop and $request = return.
      if (!$next || $next['depth'] < $depth) {
        break;
      }
    }
    return $tree;
  }

  /**
   * {@inheritdoc}
   */
  public function bookSubtreeData($link) {

    // Generate a cache ID (cid) specific for this $link.
    $cid = "book-links:subtree-data:{$link['nid']}";

    // Get it from cache, if available.
    if ($cache = $this->backendChainedCache
      ->get($cid)) {
      return $cache->data;
    }
    $result = $this->bookOutlineStorage
      ->getBookSubtree($link, static::BOOK_MAX_DEPTH);
    $links = [];
    foreach ($result as $item) {
      $links[] = $item;
    }
    $data['tree'] = $this
      ->buildBookOutlineData($links, [], $link['depth']);
    $data['node_links'] = [];
    $this
      ->bookTreeCollectNodeLinks($data['tree'], $data['node_links']);

    // Check access for the current user to each item in the tree.
    $this
      ->bookTreeCheckAccess($data['tree'], $data['node_links']);

    // Cache subtree data.
    $this->backendChainedCache
      ->set($cid, $data['tree'], Cache::PERMANENT, [
      'bid:' . $link['bid'],
    ]);
    return $data['tree'];
  }

}