Skip to content

Commit b976a7c

Browse files
Merge pull request #169 from RonnyPfannschmidt/speedup-resolver-pure-python
Speed up reference resolution with pure Python optimizations
2 parents 0f417a7 + 41e6e4a commit b976a7c

13 files changed

Lines changed: 1068 additions & 261 deletions

‎changelog.d/124.feature.rst‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
Add ``--allow-recursion`` CLI flag to ``validate`` and ``compile`` commands,
2+
allowing specs with self-referencing ``$ref`` (e.g. recursive types like
3+
linked lists or trees) to be processed without raising ``ResolutionError``.

‎changelog.d/169.feature.rst‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
Speed up reference resolution with pure Python optimizations:
2+
structural sharing for O(N) chained ``$ref`` resolution (was O(N^2)),
3+
resolved-reference caching, optimized iterators and path functions,
4+
optional ``orjson`` fast deepcopy (``prance[fast]``),
5+
``keep_ref_on_recursion`` handler to preserve ``$ref`` on recursion,
6+
``materialize=True`` option for independent subtree copies,
7+
and a fix for ``path_get`` returning ``defaultvalue`` for falsy values.

‎prance/__init__.py‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -303,13 +303,14 @@ def _validate(self):
303303
forward_args = {
304304
k: v for (k, v) in self.options.items() if k in forward_arg_names
305305
}
306+
materialize = self.options.get("materialize", False)
306307
resolver = RefResolver(
307308
self.specification,
308309
self.url,
309310
reference_cache=self.__reference_cache,
310311
**forward_args,
311312
)
312-
resolver.resolve_references()
313+
resolver.resolve_references(materialize=materialize)
313314
self.specification = resolver.specs
314315

315316
# Now validate - the BaseParser knows the specifics

‎prance/cli.py‎

Lines changed: 26 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,14 @@ def __write_to_file(filename, specs): # noqa: N802
2424
fs.write_file(filename, contents)
2525

2626

27-
def __parser_for_url(url, resolve, backend, strict, encoding): # noqa: N802
27+
def __parser_for_url( # noqa: N802
28+
url: str,
29+
resolve: bool,
30+
backend: str,
31+
strict: bool,
32+
encoding: str | None,
33+
allow_recursion: bool = False,
34+
) -> tuple:
2835
"""Return a parser instance for the URL and the given parameters."""
2936
# Try the URL
3037
formatted = click.format_filename(url)
@@ -42,9 +49,15 @@ def __parser_for_url(url, resolve, backend, strict, encoding): # noqa: N802
4249
parser = None
4350
if resolve:
4451
click.echo(" -> Resolving external references.")
45-
parser = prance.ResolvingParser(
46-
url, lazy=True, backend=backend, strict=strict, encoding=encoding
52+
kwargs: dict = dict(
53+
lazy=True, backend=backend, strict=strict, encoding=encoding
4754
)
55+
if allow_recursion:
56+
from prance.util.resolver import keep_ref_on_recursion
57+
58+
kwargs["recursion_limit_handler"] = keep_ref_on_recursion
59+
click.echo(" -> Allowing recursive references (will be kept as $ref).")
60+
parser = prance.ResolvingParser(url, **kwargs)
4861
else:
4962
click.echo(" -> Not resolving external references.")
5063
parser = prance.BaseParser(
@@ -144,12 +157,19 @@ def command_invoke(ctx):
144157
help="If given, override file encoding detection and use the given "
145158
"encoding for all files. Does not work on remote URLs.",
146159
)
160+
@click.option(
161+
"--allow-recursion/--no-allow-recursion",
162+
default=False,
163+
help="When resolving, keep recursive $ref entries in place instead of "
164+
"raising an error. Useful for specs with self-referencing schemas.",
165+
)
147166
@click.pass_context
148-
def backend_options(ctx, resolve, backend, strict, encoding):
167+
def backend_options(ctx, resolve, backend, strict, encoding, allow_recursion):
149168
ctx.obj["resolve"] = resolve
150169
ctx.obj["backend"] = backend
151170
ctx.obj["strict"] = strict
152171
ctx.obj["encoding"] = encoding
172+
ctx.obj["allow_recursion"] = allow_recursion
153173

154174

155175
@backend_options.command()
@@ -203,6 +223,7 @@ def validate(ctx, output_file, urls):
203223
ctx.obj["backend"],
204224
ctx.obj["strict"],
205225
ctx.obj["encoding"],
226+
ctx.obj["allow_recursion"],
206227
)
207228

208229
# Try parsing
@@ -243,6 +264,7 @@ def compile(ctx, url_or_path, output_file):
243264
ctx.obj["backend"],
244265
ctx.obj["strict"],
245266
ctx.obj["encoding"],
267+
ctx.obj["allow_recursion"],
246268
)
247269

248270
# Try parsing

‎prance/util/iterators.py‎

Lines changed: 20 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -60,6 +60,9 @@ def reference_iterator(specs, path=()):
6060
"""
6161
Iterate through the given specs, returning only references.
6262
63+
Uses ``isinstance`` so that dict/list subclasses (e.g. ruamel.yaml's
64+
``CommentedMap``/``CommentedSeq``) are handled correctly.
65+
6366
The iterator returns three values:
6467
- The key, mimicking the behaviour of other iterators, although
6568
it will always equal '$ref'
@@ -72,12 +75,20 @@ def reference_iterator(specs, path=()):
7275
:return: An iterator over all references in the specs.
7376
:rtype: iterator
7477
"""
75-
# We need to iterate through the nested specification dict, so let's
76-
# start with an appropriate iterator. We can immediately optimize it by
77-
# only returning '$ref' items.
78-
for item_path, item in item_iterator(specs, path):
79-
if len(item_path) <= 0:
80-
continue
81-
key = item_path[-1]
82-
if key == "$ref":
83-
yield key, item, item_path[:-1]
78+
stack = [(path, specs)]
79+
while stack:
80+
current_path, value = stack.pop()
81+
if isinstance(value, dict):
82+
children = []
83+
for key, item in value.items():
84+
if key == "$ref":
85+
yield "$ref", item, current_path
86+
elif isinstance(item, (dict, list, tuple)):
87+
children.append((current_path + (key,), item))
88+
stack.extend(reversed(children))
89+
elif isinstance(value, (list, tuple)):
90+
children = []
91+
for idx, item in enumerate(value):
92+
if isinstance(item, (dict, list, tuple)):
93+
children.append((current_path + (idx,), item))
94+
stack.extend(reversed(children))

0 commit comments

Comments
 (0)