src/proxy/http2/unit_tests/test_Http2DependencyTree.cc

/** @file

    Unit tests for Http2DependencyTree

    @section license License

    Licensed to the Apache Software Foundation (ASF) under one
    or more contributor license agreements.  See the NOTICE file
    distributed with this work for additional information
    regarding copyright ownership.  The ASF licenses this file
    to you under the Apache License, Version 2.0 (the
    "License"); you may not use this file except in compliance
    with the License.  You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
*/
#include <catch2/catch_test_macros.hpp>

#include <iostream>
#include <cstring>
#include <sstream>

#include "proxy/http2/Http2DependencyTree.h"

using namespace std;

using Tree = Http2DependencyTree::Tree<std::string *>;
using Node = Http2DependencyTree::Node;

/**
 * Exclusive Dependency Creation
 *
 *       A            A
 *      / \    =>     |
 *     B   C          D
 *                   / \
 *                  B   C
 */
TEST_CASE("Http2DependencyTree_1", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D");

  tree->add(0, 1, 0, false, &b);
  tree->add(0, 3, 0, false, &c);

  Node *node_a = tree->find(0);
  Node *node_b = tree->find(1);
  Node *node_c = tree->find(3);

  REQUIRE(node_b->parent == node_a);
  REQUIRE(node_c->parent == node_a);

  // Add node with exclusive flag
  tree->add(0, 5, 0, true, &d);

  Node *node_d = tree->find(5);

  REQUIRE(node_d->parent == node_a);
  REQUIRE(node_b->parent == node_d);
  REQUIRE(node_c->parent == node_d);
}

/**
 * Reprioritization (non-exclusive)
 *
 *    x                x
 *    |                |
 *    A                D
 *   / \              / \
 *  B   C     ==>    F   A
 *     / \              / \
 *    D   E            B   C
 *    |                    |
 *    F                    E
 */
TEST_CASE("Http2DependencyTree_2", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F");

  tree->add(0, 1, 0, false, &a);
  tree->add(1, 3, 0, false, &b);
  tree->add(1, 5, 0, false, &c);
  tree->add(5, 7, 0, false, &d);
  tree->add(5, 9, 0, false, &e);
  tree->add(7, 11, 0, false, &f);

  tree->reprioritize(1, 7, false);

  Node *node_x = tree->find(0);
  Node *node_a = tree->find(1);
  Node *node_d = tree->find(7);
  Node *node_f = tree->find(11);

  REQUIRE(node_a->parent == node_d);
  REQUIRE(node_d->parent == node_x);
  REQUIRE(node_f->parent == node_d);
}

/**
 * Reprioritization (exclusive)
 *
 *    x              x
 *    |              |
 *    A              D
 *   / \             |
 *  B   C     ==>    A
 *     / \          /|\
 *    D   E        B C F
 *    |              |
 *    F              E
 */
TEST_CASE("Http2DependencyTree_3", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F");

  tree->add(0, 1, 0, false, &a);
  tree->add(1, 3, 0, false, &b);
  tree->add(1, 5, 0, false, &c);
  tree->add(5, 7, 0, false, &d);
  tree->add(5, 9, 0, false, &e);
  tree->add(7, 11, 0, false, &f);

  tree->reprioritize(1, 7, true);

  Node *node_x = tree->find(0);
  Node *node_a = tree->find(1);
  Node *node_d = tree->find(7);
  Node *node_f = tree->find(11);

  REQUIRE(node_a->parent == node_d);
  REQUIRE(node_d->parent == node_x);
  REQUIRE(node_f->parent == node_a);
}

/**
 * Only One Node Tree
 *      ROOT
 *      /
 *    A(1)
 */
TEST_CASE("Http2DependencyTree_4", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A");
  tree->add(0, 1, 0, false, &a);

  Node *node_a = tree->find(1);

  REQUIRE(tree->top() == nullptr);

  tree->activate(node_a);
  REQUIRE(tree->top() == node_a);

  tree->deactivate(node_a, 0);
  REQUIRE(tree->top() == nullptr);
}

/**
 * Simple Tree
 *      ROOT
 *      /
 *    A(3)
 *   /
 * B(5)
 *
 */
TEST_CASE("Http2DependencyTree_5", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C");

  tree->add(0, 3, 15, false, &a);
  tree->add(3, 5, 15, false, &b);

  Node *node_a = tree->find(3);
  Node *node_b = tree->find(5);

  REQUIRE(tree->top() == nullptr);

  tree->activate(node_a);
  tree->activate(node_b);
  REQUIRE(tree->top() == node_a);

  tree->deactivate(node_a, 0);
  REQUIRE(tree->top() == node_b);
}

/**
 * Basic Tree
 *      ROOT
 *      /  \
 *    A(3)  D(9)
 *   /  \
 * B(5) C(7)
 *
 */
TEST_CASE("Http2DependencyTree_6", "[http2][Http2DependencyTree]")
{
  auto tree = std::make_unique<Tree>(100);

  string a("A"), b("B"), c("C"), d("D");

  // NOTE, weight is actual weight - 1
  tree->add(0, 3, 20, false, &a); // node_a is unused
  Node *node_b = tree->add(3, 5, 10, false, &b);
  Node *node_c = tree->add(3, 7, 10, false, &c);
  Node *node_d = tree->add(0, 9, 20, false, &d);

  // Activate B, C and D
  tree->activate(node_b);
  tree->activate(node_c);
  tree->activate(node_d);

  ostringstream oss;

  for (int i = 0; i < 90; ++i) {
    Node *node = tree->top();
    oss << static_cast<string *>(node->t)->c_str();
    tree->update(node, 100);
  }

  const string expect = "BDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBDCDBD";
  REQUIRE(oss.str() == expect);
}

/**
 * Tree of Chrome 50
 *
 *       ROOT
 *     /   |       \
 *   A(3) B(5) ... I(19)
 *
 */
TEST_CASE("Http2DependencyTree_Chrome_50", "[http2][Http2DependencyTree]")
{
  auto tree = std::make_unique<Tree>(100);

  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"), g("G"), h("H"), i("I");

  Node *node_a = tree->add(0, 3, 255, false, &a);
  Node *node_b = tree->add(0, 5, 255, false, &b);
  Node *node_c = tree->add(0, 7, 255, false, &c);
  Node *node_d = tree->add(0, 9, 182, false, &d);
  Node *node_e = tree->add(0, 11, 182, false, &e);
  Node *node_f = tree->add(0, 13, 182, false, &f);
  Node *node_g = tree->add(0, 15, 146, false, &g);
  Node *node_h = tree->add(0, 17, 146, false, &h);
  Node *node_i = tree->add(0, 19, 146, false, &i);

  // Activate nodes from A to I
  tree->activate(node_a);
  tree->activate(node_b);
  tree->activate(node_c);
  tree->activate(node_d);
  tree->activate(node_e);
  tree->activate(node_f);
  tree->activate(node_g);
  tree->activate(node_h);
  tree->activate(node_i);

  ostringstream oss;

  for (int index = 0; index < 108; ++index) {
    Node *node = tree->top();
    oss << static_cast<string *>(node->t)->c_str();

    tree->update(node, 16375);
  }

  const string expect =
    "ABCDEFGHIABCDEFGHIABCDEFABCGHIABCDEFABCGHIDEFABCGHIDEFABCABCDEFGHIABCDEFABCGHIABCDEFABCGHIDEFABCGHIDEFABCABC";

  REQUIRE(oss.str() == expect);
}

/**
 * Tree of Chrome 51
 *
 *   ROOT
 *    |
 *   A(3)
 *    |
 *   B(5)
 *    .
 *    .
 *    .
 *   I(19)
 *
 */
TEST_CASE("Http2DependencyTree_Chrome_51", "[http2][Http2DependencyTree]")
{
  auto tree = std::make_unique<Tree>(100);

  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F"), g("G"), h("H"), i("I");

  Node *node_a = tree->add(0, 3, 255, false, &a);
  Node *node_b = tree->add(3, 5, 255, false, &b);
  Node *node_c = tree->add(5, 7, 255, false, &c);
  Node *node_d = tree->add(7, 9, 182, false, &d);
  Node *node_e = tree->add(9, 11, 182, false, &e);
  Node *node_f = tree->add(11, 13, 182, false, &f);
  Node *node_g = tree->add(13, 15, 146, false, &g);
  Node *node_h = tree->add(15, 17, 146, false, &h);
  Node *node_i = tree->add(17, 19, 146, false, &i);

  // Activate nodes A, C, E, G, and I
  tree->activate(node_a);
  tree->activate(node_c);
  tree->activate(node_e);
  tree->activate(node_g);
  tree->activate(node_i);

  ostringstream oss;

  for (int index = 0; index < 9; ++index) {
    Node *node = tree->top();
    if (node != nullptr) {
      oss << static_cast<string *>(node->t)->c_str();

      tree->deactivate(node, 16384);
      tree->remove(node);
    }
  }

  // Activate nodes B, D, F, and H
  tree->activate(node_b);
  tree->activate(node_d);
  tree->activate(node_f);
  tree->activate(node_h);

  for (int index = 0; index < 9; ++index) {
    Node *node = tree->top();
    if (node != nullptr) {
      oss << static_cast<string *>(node->t)->c_str();

      tree->deactivate(node, 16384);
      tree->remove(node);
    }
  }

  const string expect = "ACEGIBDFH";

  REQUIRE(oss.str() == expect);
}

/**
 * Removing Node from tree 1
 *
 *    ROOT
 *     |
 *    A(3)
 *   /  \
 * B(5) C(7)
 *
 */
TEST_CASE("Http2DependencyTree_remove_1", "[http2][Http2DependencyTree]")
{
  auto tree = std::make_unique<Tree>(100);

  string a("A"), b("B"), c("C");

  // NOTE, weight is actual weight - 1
  Node *node_a = tree->add(0, 3, 30, false, &a);
  Node *node_b = tree->add(3, 5, 20, false, &b);
  Node *node_c = tree->add(3, 7, 10, false, &c);

  // Activate A, B, and C
  tree->activate(node_a);
  tree->activate(node_b);
  tree->activate(node_c);

  Node *top_node = nullptr;

  // Deactivate A and try to remove
  top_node = tree->top();
  REQUIRE(top_node == node_a);
  tree->deactivate(node_a, 16);
  tree->remove(node_a);
  REQUIRE(tree->find(3) == nullptr);

  // Deactivate B and try to remove
  top_node = tree->top();
  REQUIRE(top_node == node_b);
  tree->deactivate(node_b, 16);
  tree->remove(node_b);
  REQUIRE(tree->find(5) == nullptr);

  // Deactivate C and try to remove
  top_node = tree->top();
  REQUIRE(top_node == node_c);
  tree->deactivate(node_c, 16);
  tree->remove(node_c);
  REQUIRE(tree->find(7) == nullptr);
}

/**
 * Removing Node from tree 2
 *
 *    ROOT
 *     |
 *    A(3)
 *     |
 *    B(5)
 *     |
 *    C(7)
 */
TEST_CASE("Http2DependencyTree_remove_2", "[http2][Http2DependencyTree]")
{
  auto tree = std::make_unique<Tree>(100);

  string a("A"), b("B"), c("C");

  // NOTE, weight is actual weight - 1
  Node *node_a = tree->add(0, 3, 20, false, &a);
  Node *node_b = tree->add(3, 5, 10, false, &b);
  Node *node_c = tree->add(5, 7, 10, false, &c);

  // Activate, deactivate, and remove C
  tree->activate(node_c);
  REQUIRE(tree->top() == node_c);
  tree->deactivate(node_c, 16384);
  tree->remove(node_c);

  // Activate, deactivate, and remove A
  tree->activate(node_a);
  REQUIRE(tree->top() == node_a);
  tree->deactivate(node_a, 16384);
  tree->remove(node_a);

  // Activate, deactivate, and remove B
  tree->activate(node_b);
  REQUIRE(tree->top() == node_b);
  tree->deactivate(node_b, 16384);
  tree->remove(node_b);

  REQUIRE(tree->top() == nullptr);
  REQUIRE(tree->find(3) == nullptr);
  REQUIRE(tree->find(5) == nullptr);
  REQUIRE(tree->find(7) == nullptr);
}

/**
 * Exclusive Dependency Creation
 *
 *       A            A
 *      / \    =>     |
 *     B   C          D
 *                   / \
 *                  B   C
 */
TEST_CASE("Http2DependencyTree_exclusive_node", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D");

  Node *B = tree->add(0, 1, 0, false, &b);
  tree->add(0, 3, 0, false, &c);

  tree->activate(B);
  // Add node with exclusive flag
  tree->add(0, 5, 0, true, &d);

  tree->deactivate(B, 0);
  tree->remove(B);

  REQUIRE(tree->top() == nullptr);
}

/** test for reprioritize with active node
 *
 *     root                  root                   root
 *    /    \                /    \   (remove A)    /    \
 *   A      B   =======>   C      B   =======>    C      B
 *           \            /
 *            C          A
 *
 */
TEST_CASE("Http2DependencyTree_reprioritize", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C");

  Node *A = tree->add(0, 7, 70, false, &a);
  Node *B = tree->add(0, 3, 10, false, &b);
  Node *C = tree->add(3, 5, 30, false, &c);

  tree->activate(A);
  tree->activate(B);
  tree->activate(C);

  tree->reprioritize(A, 5, false);

  tree->deactivate(A, 0);
  tree->remove(A);

  REQUIRE(tree->top()->t != nullptr);
}

/**
 * Reprioritization (exclusive)
 *
 *    x              x
 *    |              |
 *    A              D
 *   / \             |
 *  B   C     ==>    A
 *     / \          /|\
 *    D   E        B C F
 *    |              |
 *    F              E
 */
TEST_CASE("Http2DependencyTree_reprioritize_2", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F");

  tree->add(0, 1, 0, false, &a);
  tree->add(1, 3, 0, false, &b);
  tree->add(1, 5, 0, false, &c);
  tree->add(5, 7, 0, false, &d);
  tree->add(5, 9, 0, false, &e);
  tree->add(7, 11, 0, false, &f);

  Node *node_x = tree->find(0);
  Node *node_a = tree->find(1);
  Node *node_b = tree->find(3);
  Node *node_d = tree->find(7);

  tree->activate(node_b);
  REQUIRE(node_x->queue->in(node_a->entry.get()));

  tree->reprioritize(1, 7, true);

  REQUIRE(!node_x->queue->in(node_a->entry.get()));
  REQUIRE(node_x->queue->in(node_d->entry.get()));
  REQUIRE(node_d->queue->in(node_a->entry.get()));
}

/**
 * Reprioritization (exclusive)
 *
 *    x              x
 *    |              |
 *    A              D
 *   / \             |
 *  B   C     ==>    A
 *     / \          /|\
 *    D   E        B C F
 *    |              |
 *    F              E
 */
TEST_CASE("Http2DependencyTree_reprioritize_3", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F");

  tree->add(0, 1, 0, false, &a);
  tree->add(1, 3, 0, false, &b);
  tree->add(1, 5, 0, false, &c);
  tree->add(5, 7, 0, false, &d);
  tree->add(5, 9, 0, false, &e);
  tree->add(7, 11, 0, false, &f);

  Node *node_x = tree->find(0);
  Node *node_a = tree->find(1);
  Node *node_c = tree->find(5);
  Node *node_d = tree->find(7);
  Node *node_f = tree->find(11);

  tree->activate(node_f);
  tree->reprioritize(1, 7, true);

  REQUIRE(node_a->queue->in(node_f->entry.get()));
  REQUIRE(node_d->queue->in(node_a->entry.get()));
  REQUIRE(node_x->queue->in(node_d->entry.get()));
  REQUIRE(!node_a->queue->in(node_c->entry.get()));
  REQUIRE(node_c->queue->empty());
}

/**
 * https://github.com/apache/trafficserver/issues/4057
 * Reprioritization to root
 *
 *    x                x
 *    |               / \
 *    A              A   D
 *   / \            / \  |
 *  B   C     ==>  B   C F
 *     / \             |
 *    D   E            E
 *    |
 *    F
 */
TEST_CASE("Http2DependencyTree_reprioritize_4", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F");

  tree->add(0, 1, 0, false, &a);
  tree->add(1, 3, 0, false, &b);
  tree->add(1, 5, 0, false, &c);
  tree->add(5, 7, 0, false, &d);
  tree->add(5, 9, 0, false, &e);
  tree->add(7, 11, 0, false, &f);

  Node *node_x = tree->find(0);
  Node *node_a = tree->find(1);
  Node *node_c = tree->find(5);
  Node *node_d = tree->find(7);
  Node *node_f = tree->find(11);

  tree->activate(node_f);
  tree->reprioritize(7, 0, false);

  REQUIRE(!node_a->queue->in(node_f->entry.get()));
  REQUIRE(node_d->queue->in(node_f->entry.get()));
  REQUIRE(node_x->queue->in(node_d->entry.get()));
  REQUIRE(!node_a->queue->in(node_c->entry.get()));
  REQUIRE(node_c->queue->empty());
}

/**
 * https://github.com/apache/trafficserver/issues/4057
 * Reprioritization to unrelated node
 *
 *    x                x
 *    |                |
 *    A                A
 *   / \              / \
 *  B   C     ==>    B   C
 *     / \           |   |
 *    D   E          D   E
 *    |              |
 *    F              F
 */
TEST_CASE("Http2DependencyTree_reprioritize_5", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E"), f("F");

  tree->add(0, 1, 0, false, &a);
  tree->add(1, 3, 0, false, &b);
  tree->add(1, 5, 0, false, &c);
  tree->add(5, 7, 0, false, &d);
  tree->add(5, 9, 0, false, &e);
  tree->add(7, 11, 0, false, &f);

  Node *node_x = tree->find(0);
  Node *node_a = tree->find(1);
  Node *node_b = tree->find(3);
  Node *node_c = tree->find(5);
  Node *node_d = tree->find(7);
  Node *node_f = tree->find(11);

  tree->activate(node_f);
  tree->reprioritize(7, 3, false);

  REQUIRE(node_a->queue->in(node_b->entry.get()));
  REQUIRE(node_b->queue->in(node_d->entry.get()));
  REQUIRE(!node_c->queue->in(node_d->entry.get()));
  REQUIRE(node_x->queue->in(node_a->entry.get()));
  REQUIRE(!node_a->queue->in(node_c->entry.get()));
  REQUIRE(node_c->queue->empty());
}

/** test for https://github.com/apache/trafficserver/issues/2268
 *
 *    root            root                  root
 *    /     =====>   /    \     =======>   /    \
 *   A              A      shadow         A      shadow
 *                          \                    \
 *                           B                    B
 *                                                 \
 *                                                  C
 *
 *              root                      root
 *             /    \                    /
 *  ======>   A      shadow   =======>  A
 *                    \
 *                     C
 */
TEST_CASE("Http2DependencyTree_insert_with_empty_parent", "[http2][Http2DependencyTree]")
{
  auto tree = std::make_unique<Tree>(100);

  string a("A"), b("B"), c("C");
  tree->add(0, 3, 20, false, &a);

  Node *b_n = tree->add(9, 7, 30, true, &b);

  REQUIRE(b_n->parent->id == 9);
  REQUIRE(tree->find(9) == nullptr);
  REQUIRE(tree->find_shadow(9)->is_shadow() == true);

  Node *c_n = tree->add(7, 11, 30, false, &c);
  tree->remove(b_n);

  REQUIRE(c_n->parent->id == 9);
  REQUIRE(tree->find(7) == nullptr);
  REQUIRE(tree->find_shadow(9)->is_shadow() == true);

  tree->remove(c_n);
  REQUIRE(tree->find_shadow(9) == nullptr);
}

/** test for https://github.com/apache/trafficserver/issues/2268
 *
 *    root            root                  root                root
 *    /     =====>   /    \     =======>   /    \   =======>   /    \
 *   A              A      shadow         A      B            A      B
 *                          \                     \
 *                           B                     shadow
 */
TEST_CASE("Http2DependencyTree_shadow_reprioritize", "[http2][Http2DependencyTree]")
{
  auto tree = std::make_unique<Tree>(100);

  string a("A"), b("B");
  tree->add(0, 3, 20, false, &a);
  tree->add(9, 7, 30, true, &b);

  Node *s_n = tree->find_shadow(9);
  REQUIRE(s_n != nullptr);
  REQUIRE(s_n->is_shadow() == true);

  tree->reprioritize(s_n, 7, false);
  REQUIRE(tree->find_shadow(9) == nullptr);
}

/** Test for https://github.com/apache/trafficserver/pull/4212
 *
 * Add child to parent that has already completed.
 *
 * root        root        root        root       root
 *  |           |           |           |          |
 *  A   ====>   A   ====>   A   ====>   A  ====>   A
 *  |                       |                      |
 *  B                       C                      E
 *                          |
 *                          D
 */
TEST_CASE("Http2DependencyTree_delete_parent_before_child_arrives", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E");

  tree->add(0, 3, 20, false, &a);
  Node *node_b = tree->add(3, 5, 30, true, &b);

  tree->remove(node_b);

  // Tree should remember B, so C will be added to B's ancestor
  Node *node_c = tree->add(5, 7, 20, false, &c);
  REQUIRE(node_c->parent->id == 3);

  // See if it remembers two missing ancestors
  Node *node_d = tree->add(7, 9, 20, false, &d);

  tree->remove(node_c);
  tree->remove(node_d);

  Node *node_e = tree->add(9, 11, 30, false, &e);
  REQUIRE(node_e->parent->id == 3);
}

/** Test for https://github.com/apache/trafficserver/pull/4212
 *
 * Make sure priority nodes stick around
 *
 *        root                 root
 *       / | \                / | \
 *      P1 P2 P3   ====>     P1 P2 P3
 *      |  |  |                 |  |
 *      A  B  C                 B  C
 *         |                    |
 *         D                    D
 */
TEST_CASE("Http2DependencyTree_handle_priority_nodes", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C"), d("D"), e("E");

  // P1 node
  tree->add(0, 3, 20, false, nullptr);
  // P2 node
  tree->add(0, 5, 20, false, nullptr);
  // P3 node
  tree->add(0, 7, 20, false, nullptr);

  Node *node_a = tree->add(3, 9, 30, true, &a);
  Node *node_b = tree->add(5, 11, 30, true, &b);
  Node *node_c = tree->add(7, 13, 30, true, &c);
  Node *node_d = tree->add(11, 15, 30, true, &d);

  REQUIRE(node_a->parent->id == 3);
  REQUIRE(node_b->parent->id == 5);
  REQUIRE(node_c->parent->id == 7);
  REQUIRE(node_d->parent->id == 11);

  // Deleting the children should not make the priority node go away
  tree->remove(node_a);
  Node *node_p1 = tree->find(3);
  REQUIRE(node_p1 != nullptr);
}

/**
 * Shadow nodes should reprioritize when they vivify
 *
 *      root                root              root
 *      /  \                 |                 |
 *     A   Shadow  ====>     A          ====>  A
 *          |                |                 |
 *          B                C(was shadow)     C
 *                           |
 *                           B
 */
TEST_CASE("Http2DependencyTree_reprioritize_shadow_node", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C");

  tree->add(0, 3, 20, false, &a);
  // 7 should be created as a shadow node
  tree->add(7, 5, 20, false, &b);

  Node *b_n        = tree->find(5);
  Node *c_n        = tree->find(7);
  Node *c_shadow_n = tree->find_shadow(7);

  REQUIRE(b_n != nullptr);
  REQUIRE(b_n->parent->id == 7);
  REQUIRE(c_n == nullptr);
  REQUIRE(c_shadow_n != nullptr);
  REQUIRE(c_shadow_n->parent->id == 0);

  // Now populate the shadow
  tree->add(3, 7, 30, false, &c);
  c_n = tree->find(7);
  REQUIRE(c_n != nullptr);
  REQUIRE(c_n->parent->id);
  REQUIRE(c_n->weight == 30);

  // C should still exist when its child goes away
  tree->remove(b_n);
  c_n = tree->find(7);
  REQUIRE(c_n != nullptr);
}

TEST_CASE("Http2DependencyTree_missing_parent", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A"), b("B"), c("C");

  tree->add(0, 3, 20, false, &a);
  tree->add(5, 7, 30, true, &b);

  Node *c_n        = tree->find(5);
  Node *c_shadow_n = tree->find_shadow(5);
  REQUIRE(c_n == nullptr);
  REQUIRE(c_shadow_n != nullptr);
  REQUIRE(c_shadow_n->is_shadow() == true);

  tree->add(0, 5, 15, false, &c);

  c_n = tree->find(5);
  REQUIRE(c_n != nullptr);
  REQUIRE(c_n->is_shadow() == false);
  REQUIRE(c_n->point == 5);
  REQUIRE(c_n->weight == 15);
}

TEST_CASE("Http2DependencyTree_max_depth", "[http2][Http2DependencyTree]")
{
  auto   tree = std::make_unique<Tree>(100);
  string a("A");
  for (int i = 0; i < 100; ++i) {
    tree->add(i, i + 1, 16, false, &a);
  }
  Node *node = tree->find(100);
  Node *leaf = tree->find(99);
  REQUIRE(node->parent->id == 0);
  REQUIRE(leaf != nullptr);
  REQUIRE(leaf->parent->id != 0);
}