如何避免多次递归中的堆栈溢出异常?

huangapple go评论78阅读模式
英文:

How to avoid stackoverflow exception in multiple recursion?

问题

我正在尝试创建自定义的 OpenApiSchema 生成器。

它的工作原理如下:

这是一个示例 API:

[ApiCommands]                 
abstract public class Commands
{
    [ApiArgument( typeof( SubjectsListArguments ), isOptional: true )]
    [ApiReturn( typeof( SubjectsListResponse ) )]
    [Title]
    [Description]
    public const string SubjectsList = "subjects_list";
}

所以 ApiArgument 和 ApiReturn 代表 DTOs。我需要做的就是根据这个模型创建 OpenApiSchema。让我们看看获取 IDictionary<string, OpenApiSchema> 的代码:

private IDictionary<string, OpenApiSchema> GenerateProperties(Type arguments)
{                                                                              
    var properties = new Dictionary<string, OpenApiSchema>();                  
                                                                              
    GeneratePropertiesRecursive(arguments, properties);                      
                                                                               
    return properties;                                                         
}                                                                              
private void GeneratePropertiesRecursive(                                                                        
    Type type,                                                                                                   
    IDictionary<string, OpenApiSchema> properties)                                                              
{                                                                                                                 
    if (type == null) return;                                                                                                  

    var propertyInfos = type.GetProperties();                                                                    

    foreach (var propertyInfo in propertyInfos)                                                                
    {                                                                                                            
        var attributeValue = propertyInfo                                                                        
            .GetCustomAttribute<JsonPropertyAttribute>();                                                        

        if (attributeValue == null)                                                                            
            continue;                                                                                            

        var propertyName = attributeValue.PropertyName;                                                          
        var propertyType = propertyInfo.PropertyType;                                                            

        var propertySchema = new OpenApiSchema();                                                                

        if (propertyType.IsClass && !_excludedTypes.Contains(propertyType))                                                        
        {                                                                                                        
            if (ImplementsEnumerableTypes(propertyType, out var genericTypes))                               
            {                                                                                                    
                var itemsSchema = new OpenApiSchema();                                                           
                                                                                                                 
                foreach (var genericType in genericTypes)                                                      
                {                                                                                                
                    if (_excludedTypes.Contains(genericType))                                                  
                    {                                                                                            
                        itemsSchema = genericType.MapTypeToOpenApiType(propertySchema);                        
                        break;                                                                                   
                    }                                                                                            
                                                                                                                 
                    GeneratePropertiesRecursive(genericType, itemsSchema.Properties);                          
                }                                                                                                
                                                                                                                 
                propertySchema.Type = "array";                                                                   
                propertySchema.Items = itemsSchema;                                                              
                                                                                                                 
                properties.Add(propertyName, propertySchema);                                                  
                continue;                                                                                        
            }                                                                                                    
                                                                                                                 
            GeneratePropertiesRecursive(propertyType, propertySchema.Properties);                              
        }                                                                                                        
                                                                                                                 
        if (propertyType.IsGenericType && propertyType.GetGenericTypeDefinition() == typeof(OptionalValue<>))    
        {                                                                                                        
            var genericType = propertyType.GetGenericArguments()[0];                                           
                                                                                                                 
            GeneratePropertiesRecursive(genericType, propertySchema.Properties);                               
                                                                                                                 
            propertyType = genericType;                                                                          
        }                                                                                                        
                                                                                                                 
        if (IsNullableType(propertyType, out var nullableType))                                              
            propertyType = nullableType;                                                                         
                                                                                                                 
        if (propertyType.IsEnum)                                                                                
        {                                                                                                        
            var types = propertyType.GetOpenApiTypesFromEnumPropertyType();                                      
                                                                                                                 
            propertySchema.Type = "string";                                                                      
            propertySchema.Enum = types;                                                                         
                                                                                                                 
            properties.Add( propertyName, propertySchema );                                                      
            continue;                                                                                            
        }                                                                                                        
                                                                                                                 
        propertySchema = propertyType.MapTypeToOpenApiType(propertySchema);                                    
                                                                                                                 
        properties.Add(propertyName, propertySchema);                                                          
    }                                                                                                            
}

我有三个问题:

  1. 我可以多次生成一个类型的 OpenApiSchema,我无法控制这个,并且不知道如何解决它。
  2. DTO 中可能存在循环引用,这会导致堆栈溢出异常。例如:我们有 SubjectDtoDepartmentDtoSubjectDto 引用了 DepartmentDto,而 DepartmentDto 又引用了 SubjectDto
  3. 这段代码真的很难阅读。

此外,我们可以添加引用:

Schema = new OpenApiSchema
{
   Reference = new OpenApiReference
   {
       Id = $"{name}_response",
       Type = ReferenceType.Schema
   }
}
英文:

I'm trying to make custom OpenApiSchema generator.

How it works:

This is example api:

[ApiCommands]                 
abstract public class Commands
{
[ApiArgument( typeof( SubjectsListArguments ), isOptional: true )]
[ApiReturn( typeof( SubjectsListResponse ) )]                     
[Title]                                                           
[Description]                                                     
public const string SubjectsList = &quot;subjects_list&quot;;               
}

So ApiArgument, ApiReturn represent DTOs. All I need is to create OpenApiSchema by this model. Let's see code for getting IDictionary&lt;string, OpenApiSchema&gt;:

private IDictionary&lt;string, OpenApiSchema&gt; GenerateProperties(Type arguments)
{                                                                              
var properties = new Dictionary&lt;string, OpenApiSchema&gt;();                  
GeneratePropertiesRecursive(arguments, properties);                      
return properties;                                                         
}                                                                              
private void GeneratePropertiesRecursive(                                                                        
Type type,                                                                                                   
IDictionary&lt;string, OpenApiSchema&gt; properties)                                                              
{                                                                                                                
if (type == null) return;                                                                                                  
var propertyInfos = type.GetProperties();                                                                    
foreach (var propertyInfo in propertyInfos)                                                                
{                                                                                                            
var attributeValue = propertyInfo                                                                        
.GetCustomAttribute&lt;JsonPropertyAttribute&gt;();                                                        
if (attributeValue == null)                                                                            
continue;                                                                                            
var propertyName = attributeValue.PropertyName;                                                          
var propertyType = propertyInfo.PropertyType;                                                            
var propertySchema = new OpenApiSchema();                                                                
if (propertyType.IsClass &amp;&amp; !_excludedTypes.Contains(propertyType))                                                        
{                                                                                                        
if (ImplementsEnumerableTypes(propertyType, out var genericTypes))                               
{                                                                                                    
var itemsSchema = new OpenApiSchema();                                                           
foreach (var genericType in genericTypes)                                                      
{                                                                                                
if (_excludedTypes.Contains(genericType))                                                
{                                                                                            
itemsSchema = genericType.MapTypeToOpenApiType(propertySchema);                        
break;                                                                                   
}                                                                                            
GeneratePropertiesRecursive(genericType, itemsSchema.Properties);                          
}                                                                                                
propertySchema.Type = &quot;array&quot;;                                                                   
propertySchema.Items = itemsSchema;                                                              
properties.Add(propertyName, propertySchema);                                                  
continue;                                                                                        
}                                                                                                    
GeneratePropertiesRecursive(propertyType, propertySchema.Properties);                              
}                                                                                                        
if (propertyType.IsGenericType &amp;&amp; propertyType.GetGenericTypeDefinition() == typeof(OptionalValue&lt;&gt;))    
{                                                                                                        
var genericType = propertyType.GetGenericArguments()[0];                                           
GeneratePropertiesRecursive(genericType, propertySchema.Properties);                               
propertyType = genericType;                                                                          
}                                                                                                        
if (IsNullableType(propertyType, out var nullableType))                                              
propertyType = nullableType;                                                                         
if (propertyType.IsEnum)                                                                                
{                                                                                                        
var types = propertyType.GetOpenApiTypesFromEnumPropertyType();                                      
propertySchema.Type = &quot;string&quot;;                                                                      
propertySchema.Enum = types;                                                                         
properties.Add( propertyName, propertySchema );                                                      
continue;                                                                                            
}                                                                                                        
propertySchema = propertyType.MapTypeToOpenApiType(propertySchema);                                    
properties.Add(propertyName, propertySchema);                                                          
}                                                                                                            
}

I have three problems:

  1. I can generate OpenApiSchema for one type several times, I don't control this, and I don't understand how to do it..
  2. We can have cycle in dto, thats why stackoverflow exception. For example: we have SubjectDto and DepartmentDto. SubjectDto has reference to DepartmentDto and DepartmentDto has reference to SubjectDto
  3. It is really hard to read....

Also we can add references:

Schema = new OpenApiSchema
{
Reference = new OpenApiReference
{
Id = $&quot;{name}_response&quot;,
Type = ReferenceType.Schema
}
}

答案1

得分: 4

我可以帮助你解决第二个问题,从而解决第三个问题...

通常,你可以通过使用一个“栈”或一个“队列”(根据你希望算法是宽度优先还是深度优先选择其中一个)来展开递归方法:

  1. 将第一个调用递归方法的参数放入栈/队列中。
  2. 在一个循环中调用你的方法,该循环弹出“第一组”参数。
  3. 不要再次递归调用方法,而是将参数推入栈/队列,以便下一次循环可以弹出它们。
  4. 循环,直到没有更多的迭代需要执行。

这种方法仍然可能导致内存问题,特别是在foreach内部进行推入操作,但比将一个全新的框架推入“栈”要高效得多。

示例:

class RecursiveStructure
{
	public required string Name { get; init; }
	public required IEnumerable&lt;RecursiveStructure&gt; Children { get; init; }	 
}

void MethodRecursion(RecursiveStructure data)
{
	Console.WriteLine($&quot;MR {data.Name}&quot;);
	foreach (var child in data.Children)
		MethodRecursion(child);
}

void QueueRecursion(RecursiveStructure data)
{
	var queue = new Queue&lt;RecursiveStructure&gt;();
	queue.Enqueue(data);
	while (queue.TryDequeue(out var current))
	{
		Console.WriteLine($&quot;QR {current.Name}&quot;);
		foreach (var child in current.Children)
			queue.Enqueue(child);
	}
}

void StackRecursion(RecursiveStructure data)
{
	var stack = new Stack&lt;RecursiveStructure&gt;();
	stack.Push(data);
	while (stack.TryPop(out var current))
	{
		Console.WriteLine($&quot;SR {current.Name}&quot;);
		foreach (var child in current.Children.Reverse()) // 请注意,我们需要反转子项的顺序,否则它们将被反向弹出
			stack.Push(child);
	}
}

请注意,“栈”和“方法递归”方法会产生相同的深度优先输出,而“队列”方法会产生宽度优先输出。

以下是一些基于上述示例的示例代码链接:

英文:

I can help with your second problem and, by extension, your third...

Generally you can flatten a recursive method by using a Stack or a Queue (choose one depending on whether you'd rather your algorithm be width-first or depth-first, see below):

  1. Put the parameters for your first call to the recursive method on the stack/queue
  2. Call your method inside a loop which pops the "first" set of parameters
  3. Instead of recursively calling back into the method, push the parameters onto the stack/queue for the next iteration of the loop to pop
  4. Loop until there is no more iterations to perform

This approach may still lead to memory issues, especially where pushing inside a foreach, but will be much more efficient than pushing a whole new frame onto The Stack.

Example:

class RecursiveStructure
{
	public required string Name { get; init; }
	public required IEnumerable&lt;RecursiveStructure&gt; Children { get; init; }	 
}

void MethodRecursion(RecursiveStructure data)
{
	Console.WriteLine($&quot;MR {data.Name}&quot;);
	foreach (var child in data.Children)
		MethodRecursion(child);
}

void QueueRecursion(RecursiveStructure data)
{
	var queue = new Queue&lt;RecursiveStructure&gt;();
	queue.Enqueue(data);
	while (queue.TryDequeue(out var current))
	{
		Console.WriteLine($&quot;QR {current.Name}&quot;);
		foreach (var child in current.Children)
			queue.Enqueue(child);
	}
}

void StackRecursion(RecursiveStructure data)
{
	var stack = new Stack&lt;RecursiveStructure&gt;();
	stack.Push(data);
	while (stack.TryPop(out var current))
	{
		Console.WriteLine($&quot;SR {current.Name}&quot;);
		foreach (var child in current.Children.Reverse()) // NB we need to reverse child order or they&#39;ll be popped backwards
			stack.Push(child);
	}
}

Note that the Stack and Method recursion approaches lead to the same depth-first output, while the Queue approach leads to a width-first output.

Here's some fiddles you can play with based on the above example:

huangapple
  • 本文由 发表于 2023年7月13日 16:53:42
  • 转载请务必保留本文链接:https://go.coder-hub.com/76677568.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定