防御性编码以防止父/子层次结构中的无限递归

Question

给定这样的一个对象

public class Thing
{  
    public Thing() { this.children = new List<Thing>();}

    public int Id {get; set;}       
    public string Name {get; set;}      
    public List<Thing> children{ get; set;}

    public string ToString(int level = 0)
    {
        //Level is added purely to add a visual hierarchy
        var sb = new StringBuilder();
        sb.Append(new String('-',level));
        sb.AppendLine($"id:{Id} Name:{Name}");          
        foreach(var child in children)
        {
                sb.Append(child.ToString(level + 1));
        }       
        return sb.ToString();
    }   
}

如果以这种方式使用（滥用？），

public static void Main()
{
    var root = new Thing{Id = 1,Name = "Thing1"};       
    var thing2 = new Thing{Id = 2,Name = "Thing2"};             
    var thing3 = new Thing{Id = 3,Name = "Thing3"};     
    root.children.Add(thing2);
    thing2.children.Add(thing3);                         
    thing3.children.Add(root);  //problem is here       
    Console.WriteLine(root.ToString());     
}

如何在这种情况下采取防御性措施。

目前的代码会产生一个stackoverflow、无限递归或内存溢出错误。

在(IIS)网站中，这会导致w3工作进程崩溃，并最终使应用程序池关闭(快速故障保护)。

上面的代码仅表示重现问题所需。在实际情况中，结构来自具有Id和ParentId的数据库。

数据库表结构类似于：

CREATE TABLE Thing(
    Id INT NOT NULL PRIMARY KEY,
    Name NVARCHAR(255) NOT NULL,
    ParentThingId INT NULL //References self
)

问题在于用户创建的“事物”没有防止乱伦关系（即父母可以有子女（他们又可以有子女等等...最终指向父母）。可以在数据库中对其进行约束以防止事物不成为自己的父母（有意义），但是根据深度，这可能会变得很丑陋，并且有人认为可能需要循环引用（我们仍在讨论中...）

因此，可以说这些结构是循环的，但是如果您想在网页上呈现这种结构，例如在父/子菜单中作为<ul><li><a>标签之类的东西，如何在代码中积极处理此类用户生成的数据问题？

.NET fiddle here

- OJay

Answer 1

一种方法是在递归调用中包含一个已访问节点的集合。如果先前访问过，那么你就处于一个循环中。

public string ToString(int level = 0, HashSet<int> visited)
{
        foreach(var child in children)
        {
                if(visited.Add(child.Id))
                   sb.Append(child.ToString(level + 1, visited));
                else
                   //Handle the case when a cycle is detected.
        }       
        return sb.ToString();
}

- Magnus

Answer 2

如果您能够a）消除想要具有循环引用的可能性，并且b）保证在创建该父级时已经知道所有子级，则可以通过构造函数将子级设置为不可变集合，这是一个绝佳的机会。

这样，您就可以通过结构递归获得一个类，无论整个结构有多大，都知道它不包含任何循环。类似于：

public sealed class Thing
{  
    public Thing(IEnumerable<Thing> children) {
      this._children = children.ToList().AsReadOnly();
    }

    private readonly ReadOnlyCollection<Thing> _children;

    public int Id {get; set;}       
    public string Name {get; set;}      
    public IEnumerable<Thing> children {
       get {
         return _children;
       }
    }

    public string ToString(int level = 0)
    {
        //Level is added purely to add a visual hierarchy
        var sb = new StringBuilder();
        sb.Append(new String('-',level));
        sb.AppendLine($"id:{Id} Name:{Name}");          
        foreach(var child in children)
        {
                sb.Append(child.ToString(level + 1));
        }       
        return sb.ToString();
    }   
}

当然，我上面所述的那些条件都是很大的“如果”，因此你需要考虑它是否适合你。

- Damien_The_Unbeliever

---

你说：“有一些争论认为可能需要循环引用（我们仍在讨论中....）”，所以我想借此机会提供一个强有力的例子，展示如果你能决定不使用它们，将会有哪些机会可用。 - Damien_The_Unbeliever

Answer 3

您可以通过将每个元素放入堆栈或队列中并在集合有项目时弹出它们来展开树形结构。在 while 循环中，您将每个项的子项放入队列中。

如果您关心树中项目的级别，则需要使用存储该级别的辅助对象。

编辑：

在展开树时，您可以将每个项放入新列表中，并将其用作循环问题的参考。

- stephanV