Защитный код для предотвращения бесконечной рекурсии в родительской / дочерней иерархии - PullRequest
Новая
       4

Защитный код для предотвращения бесконечной рекурсии в родительской / дочерней иерархии

0 голосов
/ 04 октября 2018

Учитывая Объект как таковой 

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());     
}

как можно быть Оборонительный о такого рода сценарии.

Этот код в его нынешнем виде создает переполнение стека, бесконечную рекурсию или ошибку превышения памяти .

На веб-сайте (IIS) это приводило к сбою рабочих процессов w3 и, в конечном итоге, к закрытию пула приложений (Rapid-Fail Protection)

Приведенный выше код является ориентировочным только для воспроизведенияэта проблема.В реальном сценарии структура исходит из базы данных с 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 скрипка здесь

Ответы [ 3 ]

0 голосов
/ 04 октября 2018

Одним из способов будет включение коллекции посещенных узлов в рекурсивный вызов.Если посещено до того, как вы в цикле. 

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();
}
0 голосов
/ 04 октября 2018

Если вы можете а) исключить возможность получения циклических ссылок и б) гарантировать, что все дети уже известны о том, когда этот родительский объект создан, это прекрасная возможность сделать детей коллекцией неизменной это устанавливается только через конструктор.

Это дает вам класс, который, как вы знаете, по структурной рекурсии не может содержать никаких циклов, независимо от того, насколько велика общая структура.Что-то вроде: 

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();
    }   
}

Теперь, конечно, те условия, которые я изложил выше, довольно большие, если "s", поэтому вам нужно подумать, подходит ли вам это.

0 голосов
/ 04 октября 2018

Вы можете развернуть древовидную структуру, поместив каждый элемент в стек или очередь и вытолкнув туда элементы, пока в коллекции есть элементы.В цикле while вы помещаете потомков каждого элемента в очередь.

Если вам нужен уровень элемента в дереве, который вам нужен, вы можете использовать вспомогательный объект, который хранит его.

Редактировать:

При развертывании дерева вы можете поместитькаждый элемент в новом списке и используйте его для справки по круговым задачам.

...