Recursive schema composition

[handrews]

TL;DR:

Re-using recursive schemas is a challenge.

• $recurse is a specialized version of $ref with a context-dependent target
• The target is the root schema of the document where schema processing began
• Processing can be either static schema walking or dynamic evaluation with an instance
• The value of $recurse is always true (discussed in the "alternatives" section)
• This is based on a keyword we have long used in Doca

Example

APPARENTLY MANDATORY DISCLAIMER: This is a minimal contrived example, please do not point out all of the ways in which it is unrealistic or fails to be a convincing use case because you can refactor it. It's just showing the mechanism.

foo-schema:

{
    "$id": "http://example.com/foo-schema",
    "properties": {
        "type": "object",
        "foo": {"$recurse": true}
    }
}

bar-schema:

{
    "$id": "http://example.com/bar-schema",
    "allOf": [{"$ref": "http://example.com/foo"}],
    "required": ["bar"],
    "properties": {"bar": {"type": "boolean"}}
}

The instance:

{
    "bar": true,
    "foo": {
        "bar": false,
        "foo": {
            "foo": {}
        }
    }
}

is valid against the first schema, but not the second.

It is valid against foo-schema because the "$recurse": true is in foo-schema, which is the same document that we started processing. Therefore it behaves exactly like "$ref": "#". The recursive "foo" works as you'd expect with "$ref": "#", and foo-schema doesn't care about "bar" being there (additional properties are not forbidden).

However, it is not valid against bar-schema because in that case, the "$recurse": true in foo-schema behaves like "$ref": "http://example.com/bar-schema", as bar-schema is the document that we started processing. Taking this step by step from the top down:

• Processing the root of the instance, we have the "bar" property required by bar-schema; we got this directly from the root schema of bar-schema, without $recurse being involved
• Looking inside "foo", processing follows the allOf and $ref to foo-schema. The top-level instance is an object, so we pass the type constraint
• Still processing foo-schema, for the contents of the "foo" property, we have "$recurse": true. Since we started processing with bar-schema, this is the equivalent of "$ref": "bar-schema"
• So now we apply bar-schema to the contents of foo. This works fine: there is a boolean "bar", and we follow allOf and $ref back to foo-schema, and pass the `"type": "object" constraint
• Now, once again, we look at "$recurse": true to go into the next level "foo", and once again this is treated as "$ref": "bar-schema"
• Now validation fails, because the innermost "foo" does not have the required "bar" property.

Use cases

The primary use case for this meta-schemas. For example, the hyper-schema meta-schema has to re-define all of the applicator keywords from the core and validation meta-schema. And if something wanted to extend hyper-schema, not only would they have to re-declare all of the core applicators a third time, but also re-declare all of the LDO keywords that use "$ref": "#".

As we make more vocabularies and encourage more extensions, this rapidly becomes untenable.

I will show what the hyper-schema meta-schema would look like with $recurse in a subsequent comment.

There are some other use cases in hypermedia with common response formats, but they are all simpler than the meta-schema use case.

Alternatives

Doca's cfRecurse

This is a simplified version of an extension keyword, cfRecurse, used with Doca. That keyword takes a JSON Pointer (not a URI fragment) that is evaluated with respect to the post-$ref-resolution in-memory data structure. [EDIT: Although don't try it right now, it's broken, long story that is totally irrelevant to the proposal.]

If that has you scratching your head, that's part of why I'm not proposing cfRecurse's exact behavior.

In fact, Doca only supports "" (the root JSON Pointer) as a cfRecurse value, and no one has ever asked for any other path. The use case really just comes up for us with pure recursion.

Specifying any other pointer requires knowing the structure of the in-memory document. And when the whole point is that you don't know what your original root schema (where processing began) will be until runtime, you cannot know that structure.

One could treat the JSON Pointer as an interface constraint- "this schema may only be used with an initial document that has a /definitions/foo schema", but that is a lot of complexity for something that has never come up in practice.

For this reason, $recurse does not take a meaningful value. I chose true because false or null would be counter-intuitive (you'd expect those values to not do things), and a number, string, array, or object would be much more subject to error or misinterpretation.

Parametrized schemas

#322 proposes a general schema parametrization feature, which could possibly be used to implement this feature. It would look something like:

Parameterized schema for oneOf:

{
    "$id": "http://example.com/oneof",
    "properties": {
        "oneOf": {
            "items": {"$ref": {"$param": "rootPointer"}}
        }
    }
}

Using the parametrized schema:

{
    "$id": "http://example.com/caller",
    "allOf": [
        {
            "$ref": "http://example.com/oneof",
            "$params": {
                "rootPointer": "http://example.com/caller"
            }
        }
    ],
    ...
}

See #322 for an explanation of how this works.

I'd rather not open the schema parametrization can of worms right now. $recurse is a much simpler and easy to implement proposal and meets the core need for meta-schema extensibility. It does not preclude implementing schema parametrization, either in a later draft or as an extension vocabulary of some sort (it makes an interesting test case for vocabulary support, actually).

Summary

• extending recursive schemas is a fundamental use case of JSON Schema as seen in meta-schemas, which happens to require knowledge of where runtime processing started
• referring to something inside a schema document determined at runtime adds a lot of complexity and has no apparent use case (neither from Doca nor from any issue I've ever seen here), so let's not do it

Runtime resolution (whether $recurse or parametrized schemas) is sufficiently new and powerful that I feel we should lock it down to the simplest case with a clear need. We can always extend it later, but it's hard to pull these things back.

[handrews]

Note that $recurse would have the same behavior with respect to adjacent keywords as $ref, and the same conceptual model. So delegation (#514) and allowing adjacent keywords by AND-ing results (#523).

[handrews]

If we were to replace all occurrences of {"$ref": "#"} in the core and validation meta-schema with {"$recurse": true}, then we could re-write the hyper-schema meta-schema as follows:

{
    "$schema": "http://json-schema.org/draft-07/hyper-schema#",
    "$id": "http://json-schema.org/draft-07/hyper-schema#",
    "title": "JSON Hyper-Schema",
    "allOf": [ { "$ref": "http://json-schema.org/draft-07/schema#" } ],
    "properties": {
        "base": {
            "type": "string",
            "format": "uri-template"
        },
        "links": {
            "type": "array",
            "items": {
                "$ref": "http://json-schema.org/draft-07/links#"
            }
        }
    },
    "links": [
        {
            "rel": "self",
            "href": "{+%24id}"
        }
    ]
}

This is 24 lines. The current file is 69 lines, and every time we add, remove, or change an applicator those other lines need to be updated.

---

If we also replaced {"$ref": "http://json-schema.org/draft-07/hyper-schema#"} with {"$recurse": true} in the Link Description Object schema, then adding a schema keyword "abc" and an LDO keyword "xyz" would look like this:

{
    "$id": "http://example.com/abcxyz",
    "$schema": "http://json-schema.org/draft-07/hyper-schema#",
    "allOf": [ {"$schema": "http://json-schema.org/draft-07/hyper-schema#" } ],
    "properties": {
        "abc": {...},
        "links": {
            "items": {
                "properties": {
                    "xyz": {...}
                }
            }
        }
    }
}

Without $recurse, an extension schema like this would need to both re-re-declare all of the core applicators, and re-declare all four schema fields in the link object.

And of course, if "abc" and "xyz" are schema fields, then without $recurse, any extension of the extension would need to do all of that re-declaration, plus re-declaring "abc" and "xyz".

etc. etc. etc.

[Relequestual]

I think I understand this, but let me check.
The proposed $recurse keyword behaves as if it were a $ref where the ref is the root document that has included the schema by use of other $refs, right?

So the two schemas are the equivilent of:

{
  "$id": "http://example.com/bar-schema",
  "allOf": [{
    "properties": {
        "type": "object",
        "foo": {"$ref": "#""}
    }
  }],
  "required": ["bar"],
  "properties": {"bar": {"type": "boolean"}}
}

However because bar-schema has an $id in your example, inlining it wouldn't work, as the base URI for $refs within that schema are re-set to that schema, right?

[handrews]

@Relequestual yes that is the equivalent of bar-schema (with foo-schema more or less inlined).

However, the presence or absence of $id doesn't matter. bar-schema and foo-schema have separate base URIs even without $id in either of them. Per RFC 3986, the base URI is the URI from which the document was retrieved (which would be a file:// URI if read from the local filesystem) or if none can be determined, an application-dependent fabricated URI:

If none of the conditions described above apply, then the base URI is
defined by the context of the application. As this definition is
necessarily application-dependent, failing to define a base URI by
using one of the other methods may result in the same content being
interpreted differently by different types of applications.

So even if you are just creating and working with these in-memory, they implicitly have different base URIs so "$ref": "#" in one can only ever refer to its own root. You cannot simulate the cross-file behavior of "$recurse" with "$ref".

[Relequestual]

Right, but my point was, if I took the two schemas and made one, which would have the equivilent behaviour, then that would be it. WHICH looks like I've dereferenced the ref, but not included the $id.

It's not suggesting an alternative, but more that's what this feature is aiming to achive.

[handrews]

but not included the $id.

Right- I was responding to your

However because bar-schema has an $id in your example, inlining it wouldn't work

which to me implies that it would have worked without an $id, and it doesn't (to inline a schema without an explicit $id, you MUST assign it an $id in the inlined version). I'm being pedantic about this because so many people are confused about $id and how it fits with $ref.

[handrews]

Note that I've updated the "Alternatives" section in the initial comment with a discussion of #322 (parametrized/higher-order/templatized schemas) as a possible alternative solution.

[awwright]

It looks like the problem statement is We want to be able to extend a some schema, and have recursive references refer back to the extended version.

So what if I'm writing a JSON document, and I want a JSON Schema to be one of the values?

{
  type: "object",
  properties: {
    "name": { type: "string" },
    "label": { type: "string" },
    "range": { $ref: "http://json-schema.org/draft-07/hyper-schema#" }
  }
}

[awwright]

Perhaps there can be an argument that specifies substitutions to make when evaluating sub-schemas: "in sub-schemas, when it refers to <http://json-schema.org/draft-07/schema#>, actually use <http://json-schema.org/draft-07/hyper-schema#>"

[handrews]

@awwright please don't change the problem statement. Or if you must, please explain why your problem statement is better to solve than the one I am stating.

Otherwise the answer to "what if I want to do something different than what this issue is talking about" is "file an issue for that and we'll talk about it."

Perhaps there can be an argument that specifies substitutions to make when evaluating sub-schemas: "in sub-schemas, when it refers to http://json-schema.org/draft-07/schema#, actually use http://json-schema.org/draft-07/hyper-schema#"

Why would I need to do that? I am following your oft-cited principle of least power, and proposing a feature that solves the use case that I see coming up a lot. And not anything beyond that. I do not need fully templated schemas, nor have I heard a huge clamoring of demand for them. I referenced an issue above about that topic as one of the alternatives, so I am aware of the possibility.

We do, however have a real problem around extending recursive schemas. I am not aware of any way to solve the vocabulary problem effectively without being able to easily extend recursive schemas. And there is a lot of demand for multiple vocabulary support.

So. I'm trying to solve recursive schema extension. Please do not derail my issue without an extremely compelling justification for why we should abandon this problem in favor of yours.

[handrews]

@awwright I can see how your use case makes sense on its own, but I don't think it's needed for this. Perhaps when I write it as a PR it will make sense to you, or it will flush out problems pointing in the direction of your proposal.

My feeling is that having an external thing that causes one URI to be treated as another is counter-intuitive. Part of the goal with $recurse is to have the keyword explicitly indicate that its value is dynamic. Whenever you see "$recurse": true, you know that the behavior depends on what file began processing. If there were a keyword that, alongside of $ref, substituted URIs within the $ref target, then that means that any reference could be redirected.

I think there is room for expansion in this direction if we want to do so, by changing $recurse in the future to have values other than true, such as URIs. That could work with a substitution keyword that can redirect URIs (or other strings) used as $recurse values, without changing the behavior of regular $refs at all. Or we could add a $recurseUri keyword.

Given all of that and the lack of further objections, and given that this is required for #561 vocabularies, which has received support over the past several months from various quarters, I'm marking this accepted and moving to PRs.

I do have to apologize for the rather harsh response before. While (as usual) it's no excuse, April was a very difficult month for me personally, for reasons that have since resolved. Hopefully I'll be able to stay a bit more even-keeled.

[awwright]

Fair enough, thanks!

I'll see about prototyping the proposal here and some alternatives.

[handrews]

So, @awwright spotted a fatal, glaring flaw in this proposal in #589 (comment), namely that embedding a schema with "$recurse": true in another schema, as opposed to extending it, causes everything to collapse horribly. The containing schema becomes the recursion entry point, so given:

{
    "$schema": "http://json-schema.org/draft-08/hyper-schema#",
    "type": "object",
    "properties": {
        "embedded": {"$ref": "http://json-schema.org/draft-08/hyper-schema#"}
    }
}

every "$recurse": true in the hyper-schema meta-schema becomes a reference to this object with a property "embedded" instead of to anything that even sort-of resembles the original hyper-schema meta-schema. I think he was actually getting at this in the comment earlier in this issue but I didn't notice enough of the context to spot the problem.

...and this is why we do reviews, folks! :-P

---

I'm going to write up a few proposals, each in its own comment. Feel free to thumbs-up the comment of whichever proposal(s) you like, particularly if you don't have any further comments on them. And of course further comments/proposals are also welcome.

The new proposals will obviously need to be a bit more complex. We should balance that complexity against the current error-prone, tedious process of re-declaring all references to the "base" schema in an extension that is required now. We want it to be as easy as possible to extend meta-schemas, but not at the expense of a feature that hardly anyone will understand. The current situation is verbose and annoying, but straightforward. It would still be possible to support modular vocabularies with the current approach. We'd just prefer it to be more elegant.

I have the following requirements for any solution:

• The target of $ref remains static. The URI reference as it appears is resolved against the base URI as modified by $id. Authors need to be able to continue to rely on that behavior.
• Dynamic reference targets are opt-in, by using a separate keyword or keywords from $ref.

I prefer to just solve the recursive extension problem, but that is because I believe it to be simpler. If it turns out that solving a more general form of dynamic reference targets has more or less the same complexity, and there are use cases for it, I am open to expanding the problem space (contrary to what I posted earlier in this issue).

[handrews]

So... I said I'd post some alternatives but it turns out they all get quite messy. I'm going to work more on the keyword behavioral classification (some of which appears in #602, with more to be filed) and annotation gathering process (#530) which will, I think, clarify some mechanisms that could make this work in a way people will find usable.

For now, I am going to close the PR unmerged, and continue with the vocabulary work (#561) without this. While I think $recurse or something similar will greatly improve the UX for writing meta-schemas with extension keywords, we can get by without it. The current situation is annoying, but not impossible. I'm leaving this in draft-08 as I hope to get back to it with a solution, but will bump it out if necessary.

[awwright]

In chat @handrews pointed out some weaknesses (it's confusing if you don't already know that this uses a URI Reference, or if you use a validator that automatically loads schemas from the filesystem), but for the record I'll post the idea I had:

"$alias" keyword, which accepts 2-3 arguments: (1) A schema to reference/apply; (2) a schema to extend/alias to another, which is usually the same as (1); and (3) the schema to apply instead.

Note this isn't terribly different than the merge/patch proposal, except less powerful, but much simpler.

Here's how hyper-schema could import and extend the validation meta-schema:

{
$ref: "http://json-schema.org/draft-07/schema",
$alias: { "http://json-schema.org/draft-07/schema": "http://json-schema.org/draft-07/hyper-schema" }
}

The argument could be reduced to an empty string since it's a URI reference:

{
$ref: "http://json-schema.org/draft-07/schema",
$alias: { "http://json-schema.org/draft-07/schema": "" }
}

Alternatively, define the keyword so that it does both:

{
$refAlias: { "http://json-schema.org/draft-07/schema": "" }
}

[handrews]

Thanks, @awwright! I've been thinking about this more since our discussion.

I feel that if we really want to go for the aliasing approach, we need to consider a generic syntax such as that proposed by #322 (parametrized/templatized/higher-order schemas). We might want to restrict where it can be used at least at first, but what I like about that proposal is that the thing being replaced needs to opt-in with $param.

What concerns me about the #322 proposal is that it raises a lot of questions about keywords needing to allow the $param object as a value, and how that works with values that are already objects allowing any keys, and how it changes the concept of a schema's identity. You also end up needing to pipe parameters through intermediate schemas, so your $params values need to support $param themselves. Which is not a horrible thing, but does demonstrate the complexity.

---

I'd like to try again to stay focused on the recursion case, as I still feel that it is better motivated. And I think that "this schema allows recursive extension" is less of a problem for managing schema identity than full-on parameterization. Although I don't have a clear argument for that so I might be wrong.

I think a double-opt-in approach is key: It needs to be clear which references are dynamic, and the dynamic target needs to be explicit rather than implicit. The latter point is where $recurse got into trouble. Since the dynamic target was implicitly the entry point schema, no matter how the schemas were structured, it would not work when embedded in another schema (such as links.json, the LDO meta-schema, when used on its own).

We can solve that with a keyword I'm calling $recursiveRoot, paired with $recursiveRef which is somewhat like $recurse except that it still takes a URI reference which it uses when no recursive root has been set.

Like $schema, $recursiveRoot is only respected in root schemas. Furthermore, when walking references to new documents, only the first $recursiveRoot encountered takes effect, pinning the target of all $recursiveRefs to point back to it, rather than to the reference provided as a value.

This provides the double opt-in:

• A recursive schema that may be extended must use $recursiveRef appropriately, which also indicates to readers of that schema that the URI reference value may or may not be the actual reference target at runtime.
• A schema referring to a recursive schema must use $recursiveRoot to get the recursive extension behavior. Otherwise, the embedding behavior (which is all we've had up until now so is the default) is what you get.

---

Rather than paste a bunch of examples in here, I have created PR #605 to show how schema.json, hyper-schema.json, links.json, and a hypothetical hyper-operations.json that further extends hyper-schema.json, work with these keywords. This covers several extension and embedding cases (I think all of them, but I might be missing something somewhere).

[handrews]

I think a better term to use here than "extending" is "refining". JSON Schema is a constraint system. The empty (meta-)schema allows everything. Using type, properties, etc. refines that unbounded set of possible instance documents (which are schemas in the case of meta-schemas) to a smaller set.

Hyper-Schema's meta-schema doesn't really add links and base as keywords. The core/validation meta-schema allows them with any value, and any semantics (this is how extension keywords work in general- the assumption is that some specific implementation can handle them).

The hyper-schema meta-schema refines the core/validation meta-schema by constraining those two keywords into a syntax that supports well-defined semantics.

This is a bit mind-bending at first, but I've found that when I can get it across, usually by starting from explaining the empty schema, a lot of things seem to click for people. We could explain this in detail with examples on the web site (not just for the $recursiveRef case, but in general), and hopefully start change people's assumptions about JSON Schema from being OO-ish to being what it really is.

[ghost]

Hyper-Schema's meta-schema doesn't really add links and base as keywords. The core/validation meta-schema allows them with any value, and any semantics (this is how extension keywords work in general- the assumption is that some specific implementation can handle them).

Very interesting. Given this, if I have some custom schema keywords should I bother creating my own meta-schema with all the complexity it entails? Or just informally document that we've added 2 keywords and explain what they mean?

Given that this issue is still open it appears that the easiest way to create a custom meta-schema is to
copy/paste/tweak the hyper-schema; using it as an example of how to provide semantics for new keywords.

[handrews]

@mgwelch at the moment, either option is fine. If you use a validator that pays attention to $schema and would be confused by a custom meta-schema, then it makes more sense to just informally document it. However, a custom meta-schema can be useful for ensuring that your new keywords are used correctly.

And yes, copy-pasting the hyper-schema meta-schema is the best option for now. This will improve in draft-08 (I just need to update those PRs with review feedback and do the other part with the $vocabularies keyword).

[ghost]

Thanks @handrews, I really appreciate the feedback. I think I will take a crack at the custom meta-schema but would appreciate a recommendation for a tool you use for validating schemas against custom meta-schemas. I find it hard to google for answers to anything involving meta-schemas.

[handrews]

@mgwelch most validators will work if you just pass the schema as the instance and the meta-schema as the schema. A few will handle meta-schemas specially (Ajv in JavaScript, for example).

[handrews]

PRs merged!

[ghost]

PRs merged!

Awesome! And this is a real live example?: https://github.com/json-schema-org/json-schema-spec/blob/master/hyper-schema.json

That's nice.

[handrews]

@mgwelch yup! And yes, it is! As we write fine-grained meta-schemas for vocabularies (assuming that goes the way I expect- you can see a bit of it in #671) you'll see us depend on the feature even more.

I don't know how much it will get used outside of that context, but it will be available in conforming validators, so I guess we'll find out :-)