👨🏼‍⚖️ 🍆 🍏 如何爬树 ⛴️ 🤳🏿 🤤

更确切地说，如何摆脱困境。但是首先是第一件事。本文与PVS-Studio的常规文章格式有点不同。我们经常写有关检查其他项目的文章，但几乎从来没有打开我们内部厨房的门。现在该进行修复了，并讨论了如何从内部构建分析仪。更确切地说，关于其最重要的部分-语法树。本文将重点介绍与C和C ++语言有关的PVS-Studio部分。

第一件事

语法树是任何编译器的核心部分。一种或另一种方式是，代码需要以一种便于程序处理的形式呈现，而恰巧这种树形结构最适合于此。在这里，我将不做任何理论上的论述-足以说这棵树很好地反映了代码中表达式和块的层次结构，并且同时仅包含工作所需的数据。

编译器与静态分析器有什么关系？事实是这两个工具有很多共同点。在解析代码的初始阶段，它们执行相同的工作。首先，将代码分为令牌流，该令牌流被馈送到解析器。然后，在语法和语义分析过程中，令牌被组织成一棵树，然后沿着管道进一步发送。在此阶段，编译器可以在生成二进制代码之前执行中间优化，静态分析器开始绕过节点并启动各种检查。

在带有树的PVS-Studio分析仪中，发生了几件事：

. , , , using typedef, . , . ;
. , ;
, , , ;
. ( ). . , nullptr , , . ;
. , . , .

如果您对如何进行分析的细节感兴趣，我建议您阅读文章“ PVS-Studio代码分析器中用于查找错误和潜在漏洞的技术 ”。清单中的一些要点将在此处进行详细检查。

我们将更详细地查看分析器内部的树发生什么情况以及它的外观。在简要介绍完之后，是时候深入了解问题了。

怎么运行的

从历史上看，PVS-Studio使用二叉树表示代码。每个人都熟悉这种经典的数据结构-我们有一个通常引用两个孩子的节点。不应该具有后代的节点，我将称为终端，其他所有终端都称为非终端。非终结符在某些情况下可能没有子节点，但与终结符的主要区别在于从根本上允许后代。终端节点（或叶子）缺乏引用父节点以外的东西的能力。

PVS-Studio中使用的结构与经典的二叉树略有不同-为方便起见，这是必需的。终端节点通常对应于关键字，变量名，文字等。非终结符-各种类型的表达式，代码块，列表等，是树的组成元素。

从编译器的角度来看，这里的一切都很标准，我建议对这种类型的经典书籍-Dragon Book感兴趣的每个人。

我们正在前进。让我们看一个简单的代码示例，以及分析器如何看待它。此外，我们的内部树可视化实用程序将提供许多图片。

实际上，有一个例子：

int f(int a, int b)
{
  return a + b;
}

解析器处理后的此简单功能如下所示（非终端节点以黄色突出显示）：

这种观点各有利弊，我认为后者要多一些。但是，让我们看看那棵树。立即保留一点冗余，例如，因为它包含标点和括号。从编译的角度来看，这是不必要的垃圾，但是对于某些诊断规则，分析器有时需要这些信息。换句话说，分析器不使用抽象语法树（AST），而是使用解析树（DT）。

这棵树从左到右，从上到下生长。左子节点始终包含有意义的内容，例如声明符。如果您向右看，我们会看到标有NonLeaf字样的中间非终端。仅需要它们，以便树保留其结构。为了分析的需要，这样的节点不承担任何信息负载。

虽然我们会对树的左侧部分感兴趣。这是一个更大的特写：

此广告功能。PtreeDeclarator父节点是一个对象，您可以通过该对象访问带有函数名称及其参数的节点。它还存储类型系统的编码签名。在我看来，这张图片看起来很直观，而且很容易将树的元素与代码进行比较。

看起来很简单，对吧？

为了清楚起见，让我们举一个简单的例子。假设我们有调用函数f的代码：

f(42, 23);

树中的函数调用将如下所示：

结构非常相似，仅在这里我们看到函数调用而不是其声明。现在假设我们想遍历所有参数并对每个参数进行一些处理。这是一个真正的任务，通常可以在分析器代码中找到。显然，一切都不仅限于参数，而且必须对不同类型的节点进行排序，但是现在我们将考虑这个特定示例。

假设我们只有一个指向父FUNCALL节点的指针。从任何非终端，我们都可以获取左右子节点。每个类型都是已知的。我们知道了树的结构，因此我们可以立即到达参数列表所在的节点-这是NonLeaf，终端在该节点中成长，如图42所示。。我们事先不知道参数的数量，列表中有逗号，在这种情况下我们绝对不感兴趣。

我们将如何做？继续阅读。

自行车工厂

遍历一棵树似乎很简单。您只需要编写一个可以执行此操作的函数，然后在任何地方使用它即可。可以通过lambda作为参数来处理每个元素。如果不是有一些细微差别，那的确会是这样。

首先，每次绕树都必须有所不同。处理每个节点的逻辑以及处理整个列表的逻辑是不同的。假设，在一种情况下，我们要遍历列表参数，然后将每个参数传递给某个函数进行处理。在另一种情况下，我们要选择并返回一个满足某些要求的参数。或过滤列表，并从列表中丢弃所有无关的元素。

其次，有时您需要知道当前元素的索引。例如，我们只想处理前两个参数并停止。

第三，让我们脱离函数示例。说我们有这样的代码：

int f(int a, int b)
{
  int c = a + b;
  c *= 2;
  if (c < 42) return c;
  return 42;
}

我知道这段代码很愚蠢，但是现在让我们集中讨论树的外观。我们已经看过函数声明，在这里我们需要它的主体：

这种情况就像一个参数列表，但是您可能会注意到一些区别。再看上一部分的图片。

你注意到了吗？

没错，此列表中没有逗号，这意味着您可以连续处理它，而不必担心跳过分隔符。

总共，我们至少有两种情况：

分隔列表。
完整列表。

现在，让我们看看这一切在分析器代码中是如何发生的。这是遍历参数列表的示例。这是翻译器中功能之一的简化版本。

void ProcessArguments(Ptree* arglist)
{
  if (!arglist) return;

  Ptree* args = Second(arglist);
  while (args)
  {
    Ptree* p = args->Car();
    if (!Eq(p, ','))
    {
      ProcessArg(p);
    }

    args = args->Cdr();
  }
}

如果每次看到类似的代码，我的收入都为一美元，那我已经很富有了。

让我们看看这里发生了什么。我必须马上说，这是很早的代码，甚至是C ++ 11之前的代码，更不用说更现代的标准了。可以说，我专门寻找古代文明时代的片段。

因此，首先，此函数接受括号中的参数列表作为输入。像这样：

（42，23）

在这里调用Second函数来获取括号的内容。她所做的只是在二叉树中向右移动一次，然后向左移动一次。接下来，循环按顺序获取元素：42，然后是逗号，然后是23，在下一步中是args指针变为零，因为我们到达了分支的末尾。当然，该循环会跳过无趣的逗号。

在许多地方，尤其是在旧代码中，可以找到逻辑稍有变化的类似功能。

另一个例子。我怎么知道某个代码块中是否有对某个函数的调用？像那样：

bool IsFunctionCalled(const Ptree* body, std::string_view name)
{
  if (!arglist) return;

  const Ptree* statements = body;
  while (statements)
  {
    const Ptree* cur = statements->Car();
    if (IsA(cur, ntExprStatement) && IsA(cur->Car(), ntFuncallExpr))
    {
      const Ptree* funcName = First(cur->Car());
      if (Eq(funcName, name))
        return true;
    }

    statements = statements->Cdr();
  }
  return false;
}

注意。细心的读者可能会注意到。他多大了？有std :: string_view伸出来。一切都很简单，即使最古老的代码也将逐渐重构，并且这种类型的东西将逐渐消失。

在这里使用更优雅的东西会很好，对吗？好吧，例如，标准的find_if算法。那里的算法是什么，即使是基于正常范围的算法也将大大提高可读性并促进此类代码的支持。

让我们尝试实现这一目标。

把树放在盒子里

我们的目标是使树的行为类似于STL容器。而且，我们不必关心列表的内部结构，我们想要在节点上进行统一迭代，例如，如下所示：

void DoSomethingWithTree(const Ptree* tree)
{
  ....
  for (auto cur : someTreeContainer)
  {
    ....
  }
}

如您所见，这里有一个称为someTreeContainer的特定实体，我们尚不知道。这样的容器至少应具有返回迭代器的begin和end方法。说到迭代器，它们的行为也应该像标准迭代器一样。让我们从他们开始。

在最简单的情况下，迭代器如下所示：

template <typename Node_t,
          std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>>
class PtreeIterator
{
public:
  using value_type = Node_t;
  using dereference_type = value_type;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer   = std::add_pointer_t<value_type>;
  using difference_type =
    decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

public:
  PtreeIterator(Node_t* node) noexcept : m_node{ node } {}
  ....

  PtreeIterator& operator++() noexcept
  {
    m_node = Rest(m_node);
    return *this;
  }
  dereference_type operator*() const noexcept
  {
    return static_cast<dereference_type>(First(m_node));
  }

private:
  Node_t* m_node = nullptr;
};

为了不使代码混乱，我删除了一些细节。这里的关键点是取消引用和递增。需要模板，以便迭代器可以处理常量和非常量数据。

现在，我们将写一个放置树节点的容器。这是最简单的选择：

template <typename Node_t>
class PtreeContainer
{
public:
  using Iterator = PtreeIterator<Node_t>;
  using value_type = typename Iterator::dereference_type;
  using size_type  = size_t;
  using difference_type =
        typename Iterator::difference_type;

public:
  PtreeContainer(Node_t* nodes) :
    m_nodes{ nodes }
  {
    if (IsLeaf(m_nodes))
    {
      m_nodes = nullptr;
    }
  }

  ....

  Iterator begin() const noexcept
  { 
    return m_nodes;
  }
  Iterator end() const noexcept
  { 
    return nullptr; 
  }
  bool empty() const noexcept
  {
    return begin() == end();
  }

private:
  Node_t* m_nodes = nullptr;
};

我们已经完成，我们可以分散，谢谢您的关注。

不，等一下。不可能那么简单，对吧？让我们回到两个列表选项-带和不带分隔符。在这里，当增加时，我们仅取树的右节点，因此不能解决问题。如果我们只想处理数据，我们仍然需要跳过逗号。

没问题，我们只需向迭代器添加一个额外的模板参数即可。像这样说：

enum class PtreeIteratorTag : uint8_t
{
  Statement,
  List
};

template <typename Node_t, PtreeIteratorTag tag,
  std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0>
class PtreeIterator { .... };

这将如何帮助我们？初级。我们将逐步检查此参数并相应地执行操作。幸运的是，在C ++ 17中，我们可以在编译阶段使用if constexpr构造解决此问题：

PtreeIterator& operator++() noexcept
{
  if constexpr (tag == PtreeIteratorTag::Statement)
  {
    m_node = Rest(m_node);
  }
  else
  {
    m_node = RestRest(m_node);
  }
  return *this;
}

更好，现在我们可以选择一个迭代器来满足我们的需求。容器怎么办？例如，您可以这样：

template <typename Node_t, PtreeIteratorTag tag>
class PtreeContainer
{
public:
  using Iterator = PtreeIterator<Node_t, tag>;
  ....
};

现在，我们确定完成了吗？其实不是。

但这还不是全部

让我们看一下这段代码：

void ProcessEnum(Ptree* argList, Ptree* enumPtree)
{
  const ptrdiff_t argListLen = Length(argList);
  if (argListLen < 0) return;

  for (ptrdiff_t i = 0; i < argListLen; ++i)
  {
    std::string name;
    Ptree* elem;

    const EGetEnumElement r = GetEnumElementInfo(enumPtree, i, elem, name);
    ....
  }
}

我真的不太喜欢这段代码，从带计数器的循环开始，到以GetEnumElementInfo函数看起来非常可疑为结尾。现在它对我们来说仍然是一个黑匣子，但是我们可以假定它按索引取出枚举元素，并通过输出参数在树中返回其名称和节点。返回值也有点奇怪。让我们完全摆脱它-对于我们的列表迭代器来说是一项理想的工作：

void ProcessEnum(const Ptree* argList)
{
  for (auto elem : PtreeContainer<const Ptree, PtreeIteratorTag::List>(argList))
  {
    auto name = PtreeToString(elem);
    ....
  }
}

不错。仅此代码无法编译。为什么？因为我们删除的索引用于GetEnumElementInfo调用下方的循环主体中。在这里我不会确切地说出它的用法，因为它现在并不重要。只需说一个索引就足够了。

好吧，让我们添加一个变量并弄乱我们漂亮的代码：

void ProcessEnum(const Ptree* argList)
{
  size_t i = 0;
  for (auto elem : PtreeContainer<const Ptree, PtreeIteratorTag::List>(argList))
  {
    auto name = PtreeToString(elem);
    ....
    UseIndexSomehow(i++);
  }
}

仍然是一个可行的选择，但我个人对此有以下反应：

好吧，让我们尝试解决这个问题。我们需要可以自动计数元素的东西。添加带有计数器的迭代器。为了简洁起见，我再次跳过了其他详细信息：

template <typename Node_t, PtreeIteratorTag tag,
  std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>>
class PtreeCountingIterator
{
public:
  using size_type = size_t;
  using value_type = Node_t;
  using dereference_type = std::pair<value_type, size_type>;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

public:
  PtreeCountingIterator(Node_t* node) noexcept : m_node{ node } {}
  ....

  PtreeCountingIterator& operator++() noexcept
  {
    if constexpr (tag == PtreeIteratorTag::Statement)
    {
      m_node = Rest(m_node);
    }
    else
    {
      m_node = RestRest(m_node);
    }

    ++m_counter;
    return *this;
  }

  dereference_type operator*() const noexcept
  {
    return { static_cast<value_type>(First(m_node)), counter() };
  }

private:
  Node_t* m_node = nullptr;
  size_type m_counter = 0;
};

现在我们可以编写这样的代码了，对吧？

void ProcessEnum(const Ptree* argList)
{
  for (auto [elem, i] :
            PtreeCountedContainer<const Ptree, PtreeIteratorTag::List>(argList))
  {
    auto name = PtreeToString(elem);
    ....
    UseIndexSomehow(i);
  }
}

总的来说，我们确实可以，但是有一个问题。如果看一下这段代码，您可能会注意到我们引入了另一个实体-名为PtreeCountedContainer的实体。情况似乎越来越复杂。我真的不想摆弄不同类型的容器，并且鉴于它们的内部相同，所以手本身就可以拿到Occam的剃刀。

我们将必须使用迭代器作为容器的模板参数，但稍后会介绍更多。

动物园类型

一分钟分散计数器和迭代器的种类。为了实现节点的通用旁路，我们忘记了最重要的事情-树本身。

看一下这段代码：

int a, b, c = 0, d;

我们在树中看到的是：

现在让我们遍历声明器的列表，但是首先，我将告诉您有关树的其他信息。在此之前的所有时间里，我们一直在处理指向Ptree类的指针。这是继承所有其他类型节点的基类。通过它们的界面，我们可以获得更多信息。特别是，图片中最上面的节点可以在不使用诸如First和Second之类的实用函数的情况下向我们返回声明器列表。另外，我们不需要底层方法Car和Cdr（向Lisp语言的爱好者问好）。这非常好，因为在诊断中我们可以忽略树的实现。我认为每个人都同意当前的抽象非常糟糕。

这是所有声明符的绕过的样子：

void ProcessDecl(const PtreeDeclarator* decl) { .... }

void ProcessDeclarators(const PtreeDeclaration* declaration)
{
  for (auto decl : declaration->GetDeclarators())
  {
    ProcessDecl(static_cast<const PtreeDeclarator*>(decl));
  }
}

GetDeclarators 方法返回一个可迭代的容器。在这种情况下，其类型为PtreeContainer <const Ptree，PtreeIteratorTag :: List>。

使用此代码，如果不进行强制转换，一切都会很好。事实是ProcessDecl函数想要一个指向从Ptree派生的类的指针，但是我们的迭代器对此一无所知。我想摆脱手动转换类型的需要。

似乎是时候再次更改迭代器并添加强制转换功能了。

template <typename Node_t, typename Deref_t, PtreeIteratorTag tag,
  std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int>>
class PtreeIterator
{
public:
  using value_type = Deref_t;
  using dereference_type = value_type;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;
  ....
}

为了避免每次都手动编写所有这些模板参数，我们为所有情况添加了一些别名：

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

这样更好现在，如果不需要等级，则只能指定第一个模板参数，也不能用tag参数的值阻塞头部。

但是如何处理容器？让我提醒您，我们只想拥有一个适用于任何迭代器的通用类。现在有很多不同的组合，我们需要简化。像这样：

也就是说，我们希望单个容器类能够支持所有类型的迭代器，并能够告诉它们在取消引用时返回哪种类型。然后，在代码中，我们仅创建所需的容器并开始使用它，而无需考虑我们需要哪些迭代器。

我们将在下一部分中研究这个问题。

图案魔术

所以这是我们需要的：

一个可以与任何迭代器通用的容器。
一个迭代器，它取决于节点列表，可以与每个元素一起使用，也可以与一个元素一起使用。
相同的迭代器，但带有计数器。
如果另外指定了类型，则两个迭代器都应能够在取消引用时进行转换。

首先，我们需要通过模板参数以某种方式将容器类型绑定到迭代器类型。这是发生了什么：

template <template <typename, typename> typename FwdIt,
          typename Node_t,
          typename Deref_t = std::add_pointer_t<Node_t>>
class PtreeContainer
{
public:
  using Iterator = FwdIt<Node_t, Deref_t>;
  using value_type = typename Iterator::dereference_type;
  using size_type  = size_t;
  using difference_type = typename Iterator::difference_type;

public:
  PtreeContainer(Node_t* nodes) :
    m_nodes{ nodes }
  {
    if (IsLeaf(m_nodes))
    {
      m_nodes = nullptr;
    }
  }

  ....
  Iterator begin() const noexcept
  { 
    return m_nodes;
  }
  Iterator end() const noexcept
  { 
    return nullptr; 
  }
  bool empty() const noexcept
  {
    return begin() == end();
  }
  ....

private:
  Node_t* m_nodes = nullptr;
};

另外，您可以向容器添加更多方法。例如，这是我们找出元素数量的方法：

difference_type count() const noexcept
{
  return std::distance(begin(), end());
}

或这里是索引运算符：

value_type operator[](size_type index) const noexcept
{
  size_type i = 0;
  for (auto it = begin(); it != end(); ++it)
  {
    if (i++ == index)
    {
      return *it;
    }
  }

  return value_type{};
}

显然，由于它们的线性复杂性，您需要谨慎处理这些方法，但是有时它们很有用。

为了易于使用，请添加别名：

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementList =
PtreeContainer<PtreeStatementIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeItemList =
PtreeContainer<PtreeListIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedStatementList =
PtreeContainer<PtreeStatementCountingIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedItemList =
PtreeContainer<PtreeListCountingIterator, Node_t, Deref_t>;

现在，我们可以轻松创建容器。假设，在已经提到的PtreeDeclaration类中，我们想从GetDeclarators方法中获取一个容器，该容器的迭代器跳过分隔符，而其中没有计数器，并且在取消引用时，它将返回PtreeDeclarator类型的值。这是这样一个容器的声明：

using DeclList =
      Iterators::PtreeItemList<Ptree, PtreeDeclarator*>;
using ConstDeclList =
      Iterators::PtreeItemList<const Ptree, const PtreeDeclarator*>;
             :
void ProcessDecl(const PtreeDeclarator* decl) { .... }

void ProcessDeclarators(const PtreeDeclaration* declaration)
{
  for (auto decl : declaration->GetDeclarators())
  {
    ProcessDecl(decl);
  }
}

最后，由于别名的类型推断将仅在C ++ 20中出现，为了更方便地在代码中创建容器，我们添加了以下功能：

template <typename Node_t>
PtreeStatementList<Node_t> MakeStatementList(Node_t* node)
{
  return { node };
}

template <typename Node_t>
PtreeItemList<Node_t> MakeItemList(Node_t* node)
{
  return { node };
}

template <typename Node_t>
PtreeCountedStatementList<Node_t> MakeCountedStatementList(Node_t* node)
{
  return { node };
}

template <typename Node_t>
PtreeCountedItemList<Node_t> MakeCountedItemList(Node_t* node)
{
  return { node };
}

回忆起enum的功能。现在我们可以这样写：

void ProcessEnum(const Ptree* argList)
{
  for (auto [elem, i] : MakeCountedItemList(argList))
  {
    auto name = PtreeToString(elem);
    ....
    UseIndexSomehow(i);
  }
}

与原始版本相比，在我看来，它已经变得更好：

void ProcessEnum(Ptree* argList, Ptree* enumPtree)
{
  const ptrdiff_t argListLen = Length(argList);
  if (argListLen < 0) return;

  for (ptrdiff_t i = 0; i < argListLen; ++i)
  {
    std::string name;
    Ptree* elem;

    const EGetEnumElement r = GetEnumElementInfo(enumPtree, i, elem, name);
    ....
    UseIndexSomehow(i);
  }
}

就这样，伙计们

这就是我的全部，谢谢您的关注。我希望您发现了一些有趣甚至有用的东西。

根据文章的内容，似乎我在骂我们的分析器代码，并想说那里的一切都不好。这不是真的。像任何具有历史意义的项目一样，我们的分析仪充满了过去时代遗留下来的地质沉积物。考虑到我们刚刚发掘，从地下挖出了古代文明的文物，并进行了修复，使它们在架子上看起来不错。

压力

这里将有很多代码。我怀疑是否在这里包含迭代器的实现，最后我决定包括在内，以便不遗漏任何东西。如果您对阅读代码不感兴趣，在这里我将对您说再见。其余的我希望您有模板的愉快时光。

编码

常规迭代器

template <typename Node_t, typename Deref_t, PtreeIteratorTag tag,
std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0>
class PtreeIterator
{
public:
  using value_type = Deref_t;
  using dereference_type = value_type;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

public:
  PtreeIterator(Node_t* node) noexcept : m_node{ node } {}
  PtreeIterator() = delete;
  PtreeIterator(const PtreeIterator&) = default;
  PtreeIterator& operator=(const PtreeIterator&) = default;
  PtreeIterator(PtreeIterator&&) = default;
  PtreeIterator& operator=(PtreeIterator&&) = default;

  bool operator==(const PtreeIterator & other) const noexcept
  {
    return m_node == other.m_node;
  }
  bool operator!=(const PtreeIterator & other) const noexcept
  {
    return !(*this == other);
  }
  PtreeIterator& operator++() noexcept
  {
    if constexpr (tag == PtreeIteratorTag::Statement)
    {
      m_node = Rest(m_node);
    }
    else
    {
      m_node = RestRest(m_node);
    }
    return *this;
  }
  PtreeIterator operator++(int) noexcept
  {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  dereference_type operator*() const noexcept
  {
    return static_cast<dereference_type>(First(m_node));
  }
  pointer operator->() const noexcept
  {
    return &(**this);
  }

  Node_t* get() const noexcept
  {
    return m_node;
  }

private:
  Node_t* m_node = nullptr;
};

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListIterator =
PtreeIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

带计数器的迭代器

template <typename Node_t, typename Deref_t, PtreeIteratorTag tag,
std::enable_if_t<std::is_base_of_v<Node_t, Ptree>, int> = 0>
class PtreeCountingIterator
{
public:
  using size_type = size_t;
  using value_type = Deref_t;
  using dereference_type = std::pair<value_type, size_type>;
  using reference = std::add_lvalue_reference_t<value_type>;
  using pointer = std::add_pointer_t<value_type>;
  using difference_type =
        decltype(std::declval<pointer>() - std::declval<pointer>());
  using iterator_category = std::forward_iterator_tag;

 public:
  PtreeCountingIterator(Node_t* node) noexcept : m_node{ node } {}
  PtreeCountingIterator() = delete;
  PtreeCountingIterator(const PtreeCountingIterator&) = default;
  PtreeCountingIterator& operator=(const PtreeCountingIterator&) = default;
  PtreeCountingIterator(PtreeCountingIterator&&) = default;
  PtreeCountingIterator& operator=(PtreeCountingIterator&&) = default;

  bool operator==(const PtreeCountingIterator& other) const noexcept
  {
    return m_node == other.m_node;
  }
  bool operator!=(const PtreeCountingIterator& other) const noexcept
  {
    return !(*this == other);
  }
  PtreeCountingIterator& operator++() noexcept
  {
    if constexpr (tag == PtreeIteratorTag::Statement)
    {
      m_node = Rest(m_node);
    }
    else
    {
      m_node = RestRest(m_node);
    }

    ++m_counter;
    return *this;
  }
  PtreeCountingIterator operator++(int) noexcept
  {
    auto tmp = *this;
    ++(*this);
    return tmp;
  }
  dereference_type operator*() const noexcept
  {
    return { static_cast<value_type>(First(m_node)), counter() };
  }
  value_type operator->() const noexcept
  {
    return (**this).first;
  }

  size_type counter() const noexcept
  {
    return m_counter;
  }
  Node_t* get() const noexcept
  {
    return m_node;
  }

private:
  Node_t* m_node = nullptr;
  size_type m_counter = 0;
};

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::Statement>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeListCountingIterator =
PtreeCountingIterator<Node_t, Deref_t, PtreeIteratorTag::List>;

通用容器

template <template <typename, typename> typename FwdIt,
          typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
class PtreeContainer
{
public:
  using Iterator = FwdIt<Node_t, Deref_t>;
  using value_type = typename Iterator::dereference_type;
  using size_type  = size_t;
  using difference_type = typename Iterator::difference_type;

public:
  PtreeContainer(Node_t* nodes) :
    m_nodes{ nodes }
  {
    if (IsLeaf(m_nodes))
    {
      m_nodes = nullptr;
    }
  }

  PtreeContainer() = default;
  PtreeContainer(const PtreeContainer&) = default;
  PtreeContainer& operator=(const PtreeContainer&) = default;
  PtreeContainer(PtreeContainer&&) = default;
  PtreeContainer& operator=(PtreeContainer&&) = default;

  bool operator==(std::nullptr_t) const noexcept
  {
    return empty();
  }
  bool operator!=(std::nullptr_t) const noexcept
  {
    return !(*this == nullptr);
  }
  bool operator==(Node_t* node) const noexcept
  {
    return get() == node;
  }
  bool operator!=(Node_t* node) const noexcept
  {
    return !(*this == node);
  }
  bool operator==(PtreeContainer other) const noexcept
  {
    return get() == other.get();
  }
  bool operator!=(PtreeContainer other) const noexcept
  {
    return !(*this == other);
  }
  value_type operator[](size_type index) const noexcept
  {
    size_type i = 0;
    for (auto it = begin(); it != end(); ++it)
    {
      if (i++ == index)
      {
        return *it;
      }
    }

    return value_type{};
  }

  Iterator begin() const noexcept
  { 
    return m_nodes;
  }
  Iterator end() const noexcept
  { 
    return nullptr; 
  }
  bool empty() const noexcept
  {
    return begin() == end();
  }

  value_type front() const noexcept
  {
    return (*this)[0];
  }
  value_type back() const noexcept
  {
    value_type last{};
    for (auto cur : *this)
    {
      last = cur;
    }

    return last;
  }
  Node_t* get() const noexcept
  {
    return m_nodes;
  }

  difference_type count() const noexcept
  {
    return std::distance(begin(), end());
  }
  bool has_at_least(size_type n) const noexcept
  {
    size_type counter = 0;
    for (auto it = begin(); it != end(); ++it)
    {
      if (++counter == n)
      {
        return true;
      }
    }
    return false;
  }

private:
  Node_t* m_nodes = nullptr;
};

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeStatementList =
PtreeContainer<PtreeStatementIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeItemList =
PtreeContainer<PtreeListIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedStatementList =
PtreeContainer<PtreeStatementCountingIterator, Node_t, Deref_t>;

template <typename Node_t, typename Deref_t = std::add_pointer_t<Node_t>>
using PtreeCountedItemList =
PtreeContainer<PtreeListCountingIterator, Node_t, Deref_t>;

如果您想与讲英语的读者分享本文，请使用翻译链接：Yuri Minaev。如何爬树。

如何爬树