这种无限循环是否有明显的原因？

Question

我正在写一个 AST 和节点 class。

基本上，AST 有一个节点向量，'Nodes'。这个向量中的每个 Node 项都可以在名为 'Children' 的 Node 向量中拥有自己的子项，每个子项都意味着另一个 Node 对象也可以有自己的子项，等等。

我正在编写 AST 的简单可打印版本，读取所有节点并使用相应的填充（空格或任何其他字符串或字符）打印它们，例如：

NODE_EXPR
         NODE_INT_LIT
         NODE_OPERATOR_PLUS
         NODE_INT_LIT

NODE_IF_STMT
            NODE_EXPR
                     NODE_INT_LIT
                     NODE_OPERATOR_TRUTH_EQ
                     NODE_INT_LIT
            NODE_BODY
                     NODE_KYWD_RETURN

等只是一个基本的分支结构。

现在，刚刚使用 ast.addNode(someNodeObjectByValue); 添加到某些 AST 的节点将使它的父节点（指向 AST 中节点的指针）等于 nullptr，因为它的父节点是 AST 本身。而使用重载 ast.addNode(someNodeObjectByValue, pointerToParentNode); 添加的节点显然会使提供的节点成为新添加的节点的父节点。

问题代码

下面的代码就是问题所在。一旦完成，它应该将正在使用的临时节点引用设置为其父节点，以便下一次迭代可以运行，并且最终应该 "break"，当当前节点对象没有父节点时。

string Node::getPadding(string padding) {
size_t len = 0;
Node* child = this;

    while (child->hasParent()) {
        len += child->Parent->getNodeNodeTypeString().length();
        child = child->Parent;
        //keeps looping :/
    }
    return StringManip::repeatString(padding, len);
}

我知道这很愚蠢，请索取任何代码（整个代码很短 *.cpp，但我不想不必要地包括在内。

编辑：整个（很短）*/cpp

//**C AST
void AST::addNode(Node node) {
    node._nodeID = NodeCount();
    node.Parent = nullptr;
    node.ParentAST = this;
    Nodes.push_back(node);
}
void AST::addNode(Node node, size_t parentNode) {
    node._nodeID = NodeCount();
    node.ParentAST = this;
    node.Parent = getNodeWithID(parentNode);
    node.Parent->Children.push_back(node);
}
Node* AST::getNodeWithID(size_t id) {
    for (size_t i = 0; i < Nodes.size(); i++)
        if (Nodes[i].NodeID() == id) return &Nodes[i];

}
void AST::popEndNode() {
    Nodes.pop_back();
}
void AST::deleteNode(size_t nodeID) {
    Nodes.erase(Nodes.begin() + nodeID);
}
size_t AST::NodeCount() {
    return Nodes.size();
}


//**C Node
string Node::getNodeNodeTypeString() {
    switch (NodeType) {
        ...
    case NodeType::TOKENTYPE_INT_LIT:
        return "TOKENTYPE_INT_LIT";
    break;
        ...
    default:
        return "UNKOWN_TOKEN_TYPE";
    }
}
bool Node::hasChildren() {
    return (Children.size() != 0);
}
size_t Node::childCount() {
    return Children.size();
}

string Node::getPadding(string padding) {
   //^^^
}
bool Node::hasParent() {
    return (Parent != nullptr);
}
size_t Node::NodeID() {
    return _nodeID;
}

Answer 1

我稍微重写了类，我会把它留在这里以防其他人遇到任何问题。

AST.h

enum TokenType { 
...  
STRING_LIT,
INT_LIT
...
}
struct AST;
struct Node {
    TokenType Type;
    string Data;
    size_t ID;
    AST* ParentAST;
    size_t ParentID;
    vector<Node>* Children();
    bool hasParent();
    bool hasChildren();
    string tokenTypeString();
    size_t getPaddingLen();
};
struct AST {
    vector<Node> Nodes;
    void addNode(Node node);
    void addNode(Node node, size_t parent);
    Node& getNodeWithID(size_t nodeID);
    void printAST();
};

AST.cpp

#ifndef _AST_H
#include "AST.h"
#endif

//**C AST
void AST::addNode(Node node) {
    //Edit node data and add to AST
    node.ID = Nodes.size() + 1;
    node.ParentAST = this;
    node.ParentID = NULL;
    Nodes.push_back(node);
}
void AST::addNode(Node node, size_t parent) {
    //Edit node data and add to parent node
    node.ID = Nodes.size() + 1;
    node.ParentAST = this;
    (parent != NULL) ? node.ParentID = parent : node.ParentID = NULL;
    Nodes.push_back(node);
}
Node& AST::getNodeWithID(size_t nodeID) {
    //Search for node with specified ID in Nodes
    for (size_t i = 0; i < Nodes.size(); i++) {
        if (Nodes[i].ID == nodeID) return Nodes[i];
    }
}
void AST::printAST() {
    //Return if there are no nodes
    if (Nodes.size() == 0) return;
    for (size_t i = 0; i < Nodes.size(); i++){
        cout << StringManip::repeatString(".", Nodes[i].getPaddingLen()) << Nodes[i].tokenTypeString() << "\n";
    }
}

//**C Node
vector<Node>* Node::Children() {
    vector<Node>* ret = new vector<Node>;
    for (size_t i = 0; i < ParentAST->Nodes.size(); i++)
        if (ParentAST->Nodes[i].ParentID == /*this->*/ID)
            ret->push_back(ParentAST->Nodes[i]);
    return ret;
}
bool Node::hasParent() {
    return (ParentID != NULL);
}
bool Node::hasChildren() {
    return (Children()->size() != 0);
}
string Node::tokenTypeString() {
    //Return string based on which TokenType the node has
    switch (Type) {
        ...
    case TokenType::STRING_LIT:
        return "STRING_LIT";
        break;
        ...
    default:
        return "UNKNOWN_TOKEN";
    }
}
size_t Node::getPaddingLen() {
    size_t ret = 0;
    Node* curr_node = this;
    while (curr_node->hasParent()) {
        //Add the length of the type string to the returned value
        ret += ParentAST->getNodeWithID(curr_node->ParentID).tokenTypeString().length();
        //Set curr_node to its parent
        curr_node = &ParentAST->getNodeWithID(curr_node->ParentID);
    }
    return ret;
}

和一个简单的（无意义的）实现

AST ast;
Node node;

node.Type = TokenType::INT_LIT;
node.Data = "76534";
ast.addNode(node);
node.Type = TokenType::STRING_LIT;
node.Data = "hello world";
ast.addNode(node, 1);
node.Type = TokenType::STRING_LIT;
node.Data = "another string";
ast.addNode(node, 2);
node.Type = TokenType::INT_LIT;
node.Data = "9777";
ast.addNode(node);

ast.printAST();

这种无限循环是否有明显的原因？

Is there an obvious reason this loops endlessly?

c++

parsing

pointers

abstract-syntax-tree

nodes

问题代码