英文:
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);
}
}
我有三个问题:
- 我可以多次生成一个类型的 OpenApiSchema,我无法控制这个,并且不知道如何解决它。
- DTO 中可能存在循环引用,这会导致堆栈溢出异常。例如:我们有
SubjectDto
和DepartmentDto
。SubjectDto
引用了DepartmentDto
,而DepartmentDto
又引用了SubjectDto
。 - 这段代码真的很难阅读。
此外,我们可以添加引用:
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 = "subjects_list";
}
So ApiArgument, ApiReturn represent DTOs. All I need is to create OpenApiSchema by this model. Let's see code for getting 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);
}
}
I have three problems:
- I can generate OpenApiSchema for one type several times, I don't control this, and I don't understand how to do it..
- We can have cycle in dto, thats why stackoverflow exception. For example: we have
SubjectDto
andDepartmentDto
.SubjectDto
has reference toDepartmentDto
andDepartmentDto
has reference toSubjectDto
- It is really hard to read....
Also we can add references:
Schema = new OpenApiSchema
{
Reference = new OpenApiReference
{
Id = $"{name}_response",
Type = ReferenceType.Schema
}
}
答案1
得分: 4
我可以帮助你解决第二个问题,从而解决第三个问题...
通常,你可以通过使用一个“栈”或一个“队列”(根据你希望算法是宽度优先还是深度优先选择其中一个)来展开递归方法:
- 将第一个调用递归方法的参数放入栈/队列中。
- 在一个循环中调用你的方法,该循环弹出“第一组”参数。
- 不要再次递归调用方法,而是将参数推入栈/队列,以便下一次循环可以弹出它们。
- 循环,直到没有更多的迭代需要执行。
这种方法仍然可能导致内存问题,特别是在foreach
内部进行推入操作,但比将一个全新的框架推入“栈”要高效得多。
示例:
class RecursiveStructure
{
public required string Name { get; init; }
public required IEnumerable<RecursiveStructure> Children { get; init; }
}
void MethodRecursion(RecursiveStructure data)
{
Console.WriteLine($"MR {data.Name}");
foreach (var child in data.Children)
MethodRecursion(child);
}
void QueueRecursion(RecursiveStructure data)
{
var queue = new Queue<RecursiveStructure>();
queue.Enqueue(data);
while (queue.TryDequeue(out var current))
{
Console.WriteLine($"QR {current.Name}");
foreach (var child in current.Children)
queue.Enqueue(child);
}
}
void StackRecursion(RecursiveStructure data)
{
var stack = new Stack<RecursiveStructure>();
stack.Push(data);
while (stack.TryPop(out var current))
{
Console.WriteLine($"SR {current.Name}");
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):
- Put the parameters for your first call to the recursive method on the stack/queue
- Call your method inside a loop which pops the "first" set of parameters
- Instead of recursively calling back into the method, push the parameters onto the stack/queue for the next iteration of the loop to pop
- 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<RecursiveStructure> Children { get; init; }
}
void MethodRecursion(RecursiveStructure data)
{
Console.WriteLine($"MR {data.Name}");
foreach (var child in data.Children)
MethodRecursion(child);
}
void QueueRecursion(RecursiveStructure data)
{
var queue = new Queue<RecursiveStructure>();
queue.Enqueue(data);
while (queue.TryDequeue(out var current))
{
Console.WriteLine($"QR {current.Name}");
foreach (var child in current.Children)
queue.Enqueue(child);
}
}
void StackRecursion(RecursiveStructure data)
{
var stack = new Stack<RecursiveStructure>();
stack.Push(data);
while (stack.TryPop(out var current))
{
Console.WriteLine($"SR {current.Name}");
foreach (var child in current.Children.Reverse()) // NB we need to reverse child order or they'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:
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论