proposal: a replacement for $dynamicRef and $dynamicAnchor

[rogpeppe]

[Edited to use $paramRef rather than $ref]

Motivation

This discussion was prompted by this Slack thread, which I somewhat repeat here for context.

Like many before me I'm sure, I've been trying to understand $dynamicRef and `$dynamicAnchor . I found this article illuminating: https://json-schema.org/blog/posts/dynamicref-and-generics

But that left me with some questions that I was struggling to resolve:
The article demonstrates how to represent a generic List<T> type, but it seems that it's not possible to represent the equivalent of List<List<T>> , because there's only one dynamic anchor with a given fragment name available in a given dynamic scope (the outermost one) but nesting the generic list needs two, each with a different value.

Related, but not quite the same, the spec says:

The base URI to which the resulting fragment is appended is the canonical URI of the schema resource containing the "$anchor" or "$dynamicAnchor" in question. As discussed in the previous section, this is either the nearest "$id" in the same or parent schema object, or the base URI for the document as determined according to RFC 3986.
However, the dynamic lookup ignores the absolute part of the URI, looking instead only for the fragment. That's this part:

If the initially resolved starting point URI includes a fragment that was created by the "$dynamicAnchor" keyword, the initial URI MUST be replaced by the URI (including the fragment) for the outermost schema resource in the dynamic scope (Section 7.1) that defines an identically named fragment with "$dynamicAnchor".¶

So the fact that $dynamicAnchor is defined with respect to a particular base URL is immaterial. But it also means that all dynamic anchors exist in the same global namespace, which could be a problem. As a trivial example, say, someone used the generic list definition above to define a list-of-string schema:

{
  "$id": "list-of-string",
  "$defs": {
    "typeParam": {
      "$dynamicAnchor": "T",
      "type": "string"
    }
  },
  "$ref": "https://test.example/generic-list"
}

Then we want to use that list-of-string schema as part of some other generic schema that also uses T for its dynamic anchor name:

{
  "$id": "object-of-list-of-string",
  "$defs": {
    "typeParam": {
      "$dynamicAnchor": "T",
      "$ref": "list-of-string"
    }
  },
  "$ref": "https://test.example/generic-object"
}

This doesn't work (code here doesn't support sharing), and there's no way to say "I want to define this dynamic anchor for a particular absolute URI" because $dynamicAnchor can only be used to create a name fragment, not a full URL.

One pertinent reply in the thread was this from @gregsdennis:

The thing you have to remember with these kinds of articles is JSON Schema isn't meant for data modelling, even though people use it for that all the time.
The original intent for $dynamic* (and $recursive* before it) was to allow extension of meta-schemas. It makes defining new keywords possible. Without it, you can't make keywords that expect the extended schema as values (so called "applicators", like properties).

This seems slightly at odds with the examples of the feature that have been provided in various places, notably Appendix C of the spec, also in the above mentioned blog article and in this StackOverflow reply, all of which describe what are essentially generic data structures.

This all made me think that perhaps the current design isn't ideal and could use an overhaul to make it more fit for general use and less vulnerable to unexpected behaviour: it works fine in the limited metaschema world, but I'm not entirely convinced it's a good design when considered in the wider schema context.

So here are some thoughts as to what such a new feature might look like. The goal here is to provide something that is:

• sufficient as a replacement for the current use of $dynamic* in the metaschema
• useful in a wide variety of situations
• has predictable and understandable behaviour
• can be implemented as a smooth upgrade from the current 2020-12 version.

Proposal

Note: this has been written down rather quickly by someone (me!) without a deep understanding of the spec and various real-world implementations, but hopefully might be good as a starting point.

Parameterized schemas with $params, $refParams and $paramRef

The $params keyword provides a way for a schema to allow other schemas to be provided to it as parameters. The value of $params MUST be an object. Each member of this object MUST be a valid JSON schema and declares a parameter that can be passed to the schema.

A parameter can be used by referring to it by name using the $paramRef keyword. The value of $paramRef MUST be a string. It refers to a parameter declared with nearest enclosing $params keyword. Informally, it validates if both the parameter schema (in $params) validates and the actual parameter bound to it with $refParams validate. More formally, if the schema declared in $params is P and the schema bound to the parameter is S, the results of $paramRef are results of:

{"allOf": [S, P]}

Parameters are passed by using the $refParams keyword. The value of $refParams MUST be an object. Each member of this object MUST be a valid JSON schema. If the $refParams keyword is present, the $ref keyword must also be present and the schema referred to MUST define parameters (with $params) with names that match the member names in the $refParams value. Each member of $refParams is bound to the correspondingly named member of $params in the referred-to schema.

For example, a simple schema to define a structure for adding metadata information to an object might be described as follows:

{
    "$id": "https://example.test/metadata",
    "type": "object",
    "$params": {
        "metadata": {
            "type": "object"
        }
    },
    "properties": {
        "_metadata": {
            "$paramRef": "metadata"
        }
    },
    "required": [
        "_metadata"
    ]
}

This might be used as follows:

{
    "$id": "https://example.test/metadata-user",
    "$ref": "https://example.test/metadata",
    "$refParams": {
        "metadata": {
            "properties": {
                "version": {
                    "type": "string"
                }
            },
            "additionalProperties": false
        }
    },
    "properties": {
        "foo": {
            "type": "number"
        }
    },
    "unevaluatedProperties": false
}

The above schema would validate against the following instance:

{
    "foo": 123,
    "_metadata": {
        "version": "v0.1.2"
    }
}

but would fail to validate the following instance because the _metadata field is required by the metadata schema:

{
    "foo": 123
}

It would also fail to validate against this instance, because the other property is not allowed by the metadata-user schema.

{
    "foo": 123,
    "_metadata": {
        "other": true
    }
}

Discussion

As written, $ref is used both to refer to a schema parameter and a regular schema. This allows schema parameters to be passed to schemas that are parameters themselves, which might be seen to be similar to higher-kinded polymorphism in some other languages, and might make validator implementation more complex. It might be better to use a different keyword to refer to a schema parameter, leaving $refParams to operate exclusively on $ref and ruling out this possibility. In this case, the value of the field could defined to be the name of the parameter only rather than a URI.

One omission here is the ability to specify whether any parameters are required. As written, all parameters are considered optional. This could potentially be remedied by providing a requiredParams field, or similar.

[jdesrosiers]

Thanks for writing this up. I would very much like to see a replacement for dynamic references that isn't dynamic. I think this is theoretically sound and solves the problems it needs to solve. Since the one thing this feature needs to do is support meta-schema composition for dialect construction, I wrote up a short example and it looks like it should work to me.

{
  "$id": "https://example.com/dialect",
  "$schema": "https://json-schema.org/next",
  "$vocabulary": {
    "https://example.com/vocab/A": true,
    "https://example.com/vocab/B": true
  },
  "type": ["object", "boolean"],
  "allOf": [
    {
      "$ref": "https://example.com/meta/A",
      "$refParams": {
        "meta": { "$ref": "#" }
      }
    },
    {
      "$ref": "https://example.com/meta/B",
      "$refParams": {
        "meta": { "$ref": "#" }
      }
    }
  ]
}

{
  "$id": "https://example.com/meta/A",
  "$schema": "https://json-schema.org/next",
  "$params": {
    "meta": {}
  },
  "properties": {
    "foo": {
      "type": "object",
      "patternProperties": {
        "": { "$ref": "#/$refParams/meta" }
      }
    }
  }
}

{
  "$id": "https://example.com/meta/B",
  "$schema": "https://json-schema.org/next",
  "$params": {
    "meta": {}
  },
  "properties": {
    "bar": {
      "type": "array",
      "items": { "$ref": "#/$refParams/meta" }
    }
  }
}

[gregsdennis]

{
  "$id": "https://example.com/meta/A",
  "$schema": "https://json-schema.org/next",
  "$refParams": {
    "meta": {}
  },
  "properties": {
    "foo": {
      "type": "object",
      "patternProperties": {
        "": { "$ref": "#/$refParams/meta" }
      }
    }
  }
}

I'm not conviced this will work. #/$refParams/meta when used in $ref always just resolves to an empty schema. There's no way to signal that the $refParams points to the https://example.com/dialect schema. You'd have to:

1. Parse the pointer into segments.
2. Identify that one of them is $refParams.
3. Follow the evaluation path up until you find the $refParams that resolves the remaining pointer segments that's closest to the point of entry. (It's still dynamic.)

I don't think parsing and interpreting the pointer segments is a good approach. $ref needs to stay dumb and simply resolve the pointer that it's given. I'm open to using a new keyword, but not to modifying $ref.

[rogpeppe]

Yes, you're probably right that it's better for $ref to stay dumb. That's the possibility I was alluding to with my "It might be better to use a different keyword to refer to a schema parameter, leaving $refParams to operate exclusively on $ref "

[rogpeppe]

I'll rephrase the proposal to use $paramRef instead of $ref.

[jdesrosiers]

Although I think this theoretically works, I'm holding back from getting too excited until it's implemented because that's usually when any issues come to light.

My main concern is that the $refParams concept seems to imply a reference that resolves to multiple locations. That would be a new concept in JSON Schema and consequently isn't likely to integrate nicely into most existing implementations. This would mean very slow adoption as maintainers have to rewrite core parts of their implementations.

However, it seems to me that the same goals could be achieved without this reference duality problem. The type constraint can be implemented using normal schema composition methods without needing to support reference duality and all that might imply.

In this example, I remove $refParams from the generic schema so I had to introduce some way to reference a parameter. I chose $paramRef. This simply references a value in the calling schema's $refParams.

{
  "$id": "https://example.com/generic-tree",
  "type": "array",
  "items": {
    "anyOf": [
      { "$paramRef": "branch" },
      {
        "type": ["string", "number", "boolean", "null"],
        "$paramRef": "leaf"
      }
    ]
  }
}

{
  "$id": "https://example.com/bounded-string-tree",
  "$ref": "https://example.com/generic-tree",
  "$refParams": {
    "branch": {
      "$ref": "#",
      "maxItems": 2
    },
    "leaf": { "type": "string" }
  }
}

Hopefully, that makes sense.

[rogpeppe]

FWIW the reason I like having $params as an explicit keyword is that it makes it very clear at the top level that these parameters are required - in a sense they declare the contract ("type", arguably) of the schema. Otherwise the only way for someone to know if a parameter is allowed is to search the schema body for $paramRef keywords. The explicit $params placeholder also provides a nice conventional place to document what the parameters are and what expectations are.

My main concern is that the $refParams concept seems to imply a reference that resolves to multiple locations.

FWIW I wouldn't say that it resolves to multiple locations per se. I'd say it resolves to a single schema that refers to both locations, which is a little different. Assuming a new keyword, (say $paramRef), the implementation is going to be different from $ref anyway, and I suspect this isn't going to be hard to do. I may well be proved wrong though!

[gregsdennis]

This makes more sense to me, but you still have to understand what's in scope to determine which param to resolve.

For example (and this is an analog of an existing $dynamicRef test), if we have the following schema:

{
  "$schema": "https://json-schema.org/draft/2020-12/schema",
  "$id": "https://test.json-schema.org/dynamic-ref-with-multiple-paths/main",
  "if": {
    "properties": {
      "kindOfList": { "const": "numbers" }
    },
    "required": ["kindOfList"]
  },
  "then": { "$ref": "numberList" },
  "else": { "$ref": "stringList" },

  "$defs": {
    "genericList": {
      "$id": "genericList",
      "properties": {
        "list": {
          "items": { "$paramsRef": "itemType" }
        }
      }
    },
    "numberList": {
      "$id": "numberList",
      "$refParams": {
        "itemType": {
          "type": "number"
        }
      },
      "$ref": "genericList"
    },
    "stringList": {
      "$id": "stringList",
      "$refParams": {
        "itemType": {
          "type": "string"
        }
      },
      "$ref": "genericList"
    }
  }
}

You have to know the dynamic scope / evaluation path to determine which itemType to resolve.

(As mentioned elsewhere, an implementation could "pass down" the params as it evaluates the $ref, but I would regard that an implementation decision, and I don't think we can specify it that way. JSON Schema is declarative, and this sort of "passing down" is an iterative concept.)

[rogpeppe]

FWIW I'd write that example like this:

{
    "$schema": "https://json-schema.org/draft/2020-12/schema",
    "$id": "https://test.json-schema.org/param-ref-with-multiple-paths/main",
    "if": {
        "properties": {
            "kindOfList": {
                "const": "numbers"
            }
        },
        "required": [
            "kindOfList"
        ]
    },
    "then": {
        "$ref": "numberList"
    },
    "else": {
        "$ref": "stringList"
    },
    "$defs": {
        "genericList": {
            "$id": "genericList",
            "$params": {
                "itemType": true
            },
            "properties": {
                "list": {
                    "items": {
                        "$paramRef": "#itemType"
                    }
                }
            }
        },
        "numberList": {
            "$id": "numberList",
            "$ref": "genericList",
            "$refParams": {
                "itemType": {
                    "type": "number"
                }
            }
        },
        "stringList": {
            "$id": "stringList",
            "$ref": "genericList",
            "$refParams": {
                "itemType": {
                    "type": "string"
                }
            }
        }
    }
}

The $paramRef keyword inside genericList refers to the itemType formal parameter as declared inside that
schema. The $refParams keyword inside stringList and numberList binds the specific itemType
schema to the actual schema value in each place.

(As mentioned elsewhere, an implementation could "pass down" the params as it evaluates the $ref, but I would regard that an implementation decision, and I don't think we can specify it that way. JSON Schema is declarative, and this sort of "passing down" is an iterative concept.)

FWIW I wouldn't describe it quite like that. I'd describe it as a binding, and this kind of binding is common to many kinds of language, including fully declarative languages (e.g. logic-based).

The specific analogy I'm thinking of for this feature is that of type parameters in a compiled statically typed language. To use a language I'm familiar with, Go, we can declare a function with a type parameter:

func genericFunction[T any](arrayOfT []T) {}

Then we can instantiate the function, binding an actual type to the formal type parameter declared in the function:

genericFunction[string]([]string{"a", "b"})
genericFunction[int]([]int{1, 2})

In Go, this feature is designed such that it's possible to statically analyse the program and generate
all possible instantiations of the generic function. That is, there is no runtime stack required - the compiler
can generate all the required code in advance.

I'd hope that the $refParam in JSON Schema feature could be similarly statically analysable. (it's not there yet!).

[gregsdennis]

I think my primary hesitation with this proposal in its current state is that it's being touted as a non-dynamic replacement for $dyammic*, but it's still very dependent on the dynamic scope. You have to know the evaluation path to be able to resolve the "params".

[jdesrosiers]

Sorry for disappearing from this discussion for a while.

I think the mechanism here is fundamentally different than dynamic scope

I was asked to explain this statement. I think we're using the term slightly differently. I think the concept of dynamic scope is more than just something that makes use of the evaluation path. I think the "first definition wins" behavior is inherent to the concept of dynamic scope. One way to implement this proposal is to use the evaluation path to look up the last immediate evaluation location to find the params. That may use the evaluation path, but I think that's a fundamentally different concept than the dynamic scope.

When I say I'd like to have an non-dynamic alternative to dynamic references, I'm not necessarily talking about the dynamic scope. I mean that I want references to be determinable without knowing the instance. Dependence on the instance is what makes the feature "dynamic". For example, I consider the unevaluated* keywords to also be dynamic. They don't use the evaluation path, but determining what is in the set of evaluated properties is dependent on the instance being evaluated. It can't be known at compile time. I'd like to see a non-dynamic alternative to these keywords as well. additionalProperties is similar, but it's static because I can compile an expression at compile time to test if a property is "additional" or not.

This proposal is "static" in that sense. You can determine how any reference will resolve prior to knowing what instances will be evaluated.

every $dynamicRef in a closed system of schemas has a known resolution target

That's an interesting point. It's not a great solution for several reasons, but it is possible to know how dynamic references will resolve at compile time. We're always working with a closed set of schemas at any one time, but that set can change. A limitation is that when one thing changes you need to recompile the whole set, not just the new/removed/altered schema. That might be a performance issue in some use cases, but I suspect very few would be affected.

The biggest issue for me with this approach is the complexity and difficulty of implementation of determining the reference resolution at compile time. The example @gregsdennis gave helps illustrates what I mean. Greg had to alter the schema to make this work. That means that we lose the ability to trace errors back to the schema they originated from. In the case of Greg's example, there's no longer a /x1 schema. Errors that should trace back to /x1 will be reported a being in /x2 at a location that doesn't exist in the schema the user gave the implementation. I can imagine workarounds to solve for this problem, but it introduces even more complexity.

Although it's possible to do a compile-time processing of dynamic references, I'd still call this a "dynamic" feature. Someone reading the schemas still needs to reason about the schema as if it's behaving dynamically even if the implementation has some clever trick to avoid needing an instance.

So, although I take Greg's point that there are static solutions to implementing dynamic references, I still think dynamic references are too complex to reason about and to implement and I'd like to see an alternative that addresses those concerns.

[rogpeppe]

[Edit: crossed-wires with @jdesrosiers post above, and run out of time to reply to that].

Here's your schema with only static refs

FWIW, I'm pretty sure that translation doesn't preserve the semantics of the original.
For example, it passes validation against:

{"branch1": {"branch2": {"branch2": 123}}}

which I've fairly sure it shouldn't (branch1 sets the outermost dynamic anchor b to {"type":"string"} which should then not allow that final number-typed field).

I'm not saying it's not possible to translate into a static schema (I'm fairly convinced that it is) but the translation is non-trivial... OK, consider me nerd-sniped :) I think a correct translation might look a bit more like this: https://gist.github.com/rogpeppe/46c905d4628bce2b12373b2a794b48c8, and I think that shows the basic technique we could use to translate any $dynamicRef system into a static one: essentially the first time we encounter a $dynamicAnchor, we "fork the universe" to translate every schema into one where the a $dynamicRef to that anchor refers to that first-encountered anchor definition. Here I've used a bX--- prefix to indicate which universe is which. AFAICS with more dynamic anchors, the overall system might expand exponentially.

But in performing this conversion, we've lost what makes this system powerful: its dynamic nature.

I'm pretty sure there are two meanings being used for the word "dynamic" here.

The meaning of "dynamic" as used in the spec seems to be that the treatment of the reference is dynamic with respect to the instance: different instances will cause the dynamic reference to refer to different anchors. AIUI this is why the spec says that a dynamicRef might "only be resolvable in the process of evaluating the schema with an instance". That's the meaning that I would tend to use too, FWIW.

I think that the meaning of the word as you're using it above is something like: if we extend a schema A with another schema B, A hasn't been written with B in mind, so from A's point of view, this extension is dynamic.

So, from the latter point of view, both $dynamic* and this proposal could both be considered "dynamic", although from the former point of view technically neither is (although the translation into static form is arguably less obvious with $dynamicRef, as it's not immediately obvious which definitions need to be copied/mutated).

The main difference between the two approaches is expressive power: as written, $dynamicRef does not allow the possibility of (for example) modelling List<List<T>>, whereas this proposal does.

I know you're thinking about it from a different perspective, one of functions and parameters, but that's not a mechanism that we can easily use when specifying this behavior because we don't have it already. We'd need to define it, and having functions (an iterative concept) in a declarative system feels really weird to me. I'd much prefer to specify it using mechanisms we already have, like dynamic scope.

FWIW I'm actually thinking of it terms of types and type parameters (generic types), which really don't seem like an iterative concept to me - types are declarative and the whole of JSON Schema arguably defines a type system.

Generic types are also well understood in terms of good engineering properties (ease of refactoring, lack of surprising behaviours, early warning of problems) - I believe use of dynamic scope is generally considered not as nice in that respect, and I'm fairly sure that if this proposal was implemented, there would be no need for the concept of dynamic scope at all.

[jdesrosiers]

the whole of JSON Schema arguably defines a type system

JSON Schema isn't designed to be a type system. It's designed to be a validation engine. JSON Schema has proven to be a very poor analog for a type system as many have tried to convert schemas to various type systems and found the concepts don't line up. That's not to say that we can't learn from and borrow from type system concepts, but I wanted to make sure that was understood.

[rogpeppe]

That's not to say that we can't learn from and borrow from type system concepts, but I wanted to make sure that was understood.

Yup, totally understood: if it can be considered to be type system (I think it can), I'm aware that it's definitely not a conventional type system... But that said, some concepts (e.g. lexical scope) do have currency across many different kinds of computer language, and I think it's worth not discounting the generic-type analogy. I think it's telling that approximately all of the examples I've seen in explanations of $dynamic* draw on that analogy too.

[gregsdennis]

(If anything, I think we're getting some really good blog post material out of this conversation!)

[rogpeppe]

Unbounded instantiation cycles

This is following up from the footnote in this comment.

Here's an example of a recursive schema that seems legitimate under this proposal:

{
    "$id": "/recursive",
    "$params": {
        "p": true
    },
    "$if": {
        "required": [
            "a"
        ]
    },
    "$then": {
        "$ref": "#",
        "$refParams": {
            "p": {
                "properties": {
                    "b": {
                        "$paramRef": "p"
                    }
                },
                "required": [
                    "b"
                ]
            }
        }
    },
    "$else": {
        "$paramRef": "p"
    }
}

This would validate against the instance

{"a": {"a": {"a": {"a": {"b": {"b": {"b": {"b": true}}}}}}}}

but fail against

{"a": {"a": {"a": {"a": {"b": {"b": {"b": true}}}}}}}

because there aren't enough b fields to match the number of as.

We can't tell how many schemas are going to be instantiated until the schema is actually checked against the instance. I think this is problematic: it means that the core of any evaluator has to retain the ability to instantiate new schemas, which limits the space of possible evaluator implementations. In particular, it's not possible to entirely translate the schema to another form that just does checking without instantiating new schemas.

I see this as closely related to a similar problem in compiled languages with generic types that monomorphise the types at compilation time. See this StackOverflow question for an example of the issue.

I think we should apply a similar restriction to this proposal: a recursive type definition that leads to arbitrary expansion of schemas should be disallowed, or at least documented to be undefined behaviour. That is, in principle it should be possible to statically transform a schema with $params, $refParams and $paramsRef into a schema without those keywords.

I outlined a sketch of a possible algorithm for doing that in the above comment.

I found one example (and explanation) of an algorithm for doing the cycle check in the Go compiler here. I believe it shouldn't be too tricky to implement such a check for JSON Schema.

I believe that the ability to do this transformation into a parameterless form would justify the description of this feature as a a non-dynamic replacement for $dynamic*.

[jdesrosiers]

I'm not following this yet, but it looks like you meant to wrap that then schema in "properties": { "a": ... }. Otherwise it's just an infinite reference loop that doesn't do anything.

[rogpeppe]

Yeah, that example was sketched too quickly and was wrong on multiple counts (not least of which was that it's spelled if not $if!).

Here's a more plausible example:

{
    "$ref": "/recursive",
    "$refParams": {
        "p": {
            "type": "boolean"
        }
    },
    "$defs": {
        "recursive": {
            "$id": "/recursive",
            "if": {
                "type": "object",
                "required": [
                    "a"
                ]
            },
            "then": {
                "properties": {
                    "a": {
                        "$ref": "#",
                        "$refParams": {
                            "type": "object",
                            "properties": {
                                "b": {
                                    "$paramRef": "p"
                                }
                            },
                            "required": [
                                "b"
                            ]
                        }
                    }
                }
            },
            "else": {
                "$paramRef": "p"
            }
        }
    }
}

To understand how this might be interpreted, we can apply a few parameter expansion steps by hand.
At each step, we take a $refParams, copy the schema referred to by its associated $ref into a schema with a new ID, replace any $paramRef keywords in that with the actual parameter passed, and finally remove the $refParams keyword and change the $ref to refer to the new ID. Any self reference must still refer to the original schema, not the newly instantiated schema.

So, repeatedly applying the above rules, we get the following results:

Step 1

{
    "$ref": "/recursive1",
    "$defs": {
        "recursive1": {
            "$id": "/recursive1",
            "if": {
                "type": "object",
                "required": [
                    "a"
                ]
            },
            "then": {
                "properties": {
                    "a": {
                        "$ref": "/recursive",
                        "$refParams": {
                            "type": "object",
                            "properties": {
                                "b": {
                                    "type": "boolean"
                                }
                            },
                            "required": [
                                "b"
                            ]
                        }
                    }
                }
            },
            "else": {
                "type": "boolean"
            }
        },
        "recursive": {
            "$id": "/recursive",
            "if": {
                "type": "object",
                "required": [
                    "a"
                ]
            },
            "then": {
                "properties": {
                    "a": {
                        "$ref": "/recursive",
                        "$refParams": {
                            "type": "object",
                            "properties": {
                                "b": {
                                    "$paramRef": "p"
                                }
                            },
                            "required": [
                                "b"
                            ]
                        }
                    }
                }
            },
            "else": {
                "$paramRef": "p"
            }
        }
    }
}

Step 2

{
    "$ref": "/recursive1",
    "$defs": {
        "recursive1": {
            "$id": "/recursive1",
            "if": {
                "type": "object",
                "required": [
                    "a"
                ]
            },
            "then": {
                "properties": {
                    "a": {
                        "$ref": "/recursive2"
                    }
                }
            },
            "else": {
                "type": "boolean"
            }
        },
        "recursive2": {
            "$id": "/recursive2",
            "if": {
                "type": "object",
                "required": [
                    "a"
                ]
            },
            "then": {
                "properties": {
                    "a": {
                        "$ref": "/recursive",
                        "$refParams": {
                            "type": "object",
                            "properties": {
                                "b": {
                                    "type": "object",
                                    "properties": {
                                        "b": {
                                            "type": "boolean"
                                        }
                                    },
                                    "required": [
                                        "b"
                                    ]
                                }
                            },
                            "required": [
                                "b"
                            ]
                        }
                    }
                }
            },
            "else": {
                "type": "object",
                "properties": {
                    "b": {
                        "type": "boolean"
                    }
                },
                "required": [
                    "b"
                ]
            }
        },
        "recursive": {
            "$id": "/recursive",
            "if": {
                "type": "object",
                "required": [
                    "a"
                ]
            },
            "then": {
                "properties": {
                    "a": {
                        "$ref": "#",
                        "$refParams": {
                            "type": "object",
                            "properties": {
                                "b": {
                                    "$paramRef": "p"
                                }
                            },
                            "required": [
                                "b"
                            ]
                        }
                    }
                }
            },
            "else": {
                "$paramRef": "p"
            }
        }
    }
}

Step 3

{ "$ref": "/recursive1", "$defs": { "recursive1": { "$id": "/recursive1", "if": { "type": "object", "required": [ "a" ] }, "then": { "properties": { "a": { "$ref": "/recursive2" } } }, "else": { "type": "boolean" } }, "recursive2": { "$id": "/recursive2", "if": { "type": "object", "required": [ "a" ] }, "then": { "properties": { "a": { "$ref": "/recursive3" } } }, "else": { "type": "object", "properties": { "b": { "type": "boolean" } }, "required": [ "b" ] } }, "recursive3": { "$id": "/recursive3", "if": { "type": "object", "required": [ "a" ] }, "then": { "properties": { "a": { "$ref": "/recursive", "$refParams": { "type": "object", "properties": { "b": { "type": "object", "properties": { "b": { "type": "object", "properties": { "b": { "type": "boolean" } }, "required": [ "b" ] } }, "required": [ "b" ] } }, "required": [ "b" ] } } } }, "else": { "type": "object", "properties": { "b": { "type": "object", "properties": { "b": { "type": "boolean" } }, "required": [ "b" ] } }, "required": [ "b" ] } }, "recursive": { "$id": "/recursive", "if": { "type": "object", "required": [ "a" ] }, "then": { "properties": { "a": { "$ref": "#", "$refParams": { "type": "object", "properties": { "b": { "$paramRef": "p" } }, "required": [ "b" ] } } } }, "else": { "$paramRef": "p" } } } }

If we take the last step and remove the if, replacing it with the else clause only, we can check the results, for a few values of N at any rate, and see that the following instances pass validation:

true
{"a": {"b": true}}
{"a": {"a": {"b": {"b": true}}}}

and the following instances fail:

{"a": true}
{"a": {"a": {"b": true}}}
{"a": {"b": {"b": true}}}

i.e. for N<3 at least, it's validating that the a and b counts are the same, demonstrating that if unbounded instantiation is allowed, it can parse a context-free grammar.

Hope that helps :)

[rogpeppe]

One thing I'll mention is that the problem here is arguably considerably simpler than the one the above-mentioned Go code solves, as mutual recursion is disallowed, so we need only disallow all mutual recursion and check that for self-recursion, any parameters are exactly those which were passed in. So I think this kind of capability can be avoided quite easily.

[jdesrosiers]

I understand the problem now. I previously thought this could be done without rewriting schemas, but now I'm not convinced that's going to be possible. This realization changes my opinion of this proposal. That's too complex even if the transformations are relatively simple. My biggest concern with that is the traceability problem I mentioned earlier.

Given this example, I'm no longer convinced that this proposal is any less complex than what we have now. It's slightly more expressive (List<List>) and slightly more intuitive (no dynamic scope), but it's mostly the same thing.

[rogpeppe]

Parameter references in formal parameters

Here's another edge case that needs to be considered: whether to allow parameter references inside parameter schemas themselves. An easy initial answer might be to forbid this, but it also might provide some useful expressive power, so worth not dismissing the possibility out of hand.

For example:

{
    "$id": "https://example.test",
    "$defs": {
        "example": {
            "$id": "/example",
            "$params": {
                "a": {
                    "items": {
                        "$paramRef": "b"
                    }
                },
                "b": true
            },
            "properties": {
                "foo": {
                    "$paramRef": "a"
                }
            }
        }
    },
    "$ref": "#/$defs/example",
    "$refParams": {
        "a": {
            "contains": {
                "required": [
                    "something"
                ]
            }
        },
        "b": {
            "type": "string"
        }
    }
}

[jdesrosiers]

I don't see any reason to forbid this. It seems useful. Besides, forbidding it doesn't sound like the easy answer to me. It sounds harder. I'd rather it works the same everywhere than to have to implement special cases.

[gregsdennis]

I agree. This seems valid. I think it's actually a natural consequence rather than a feature that would need to be explicitly supported.

[gregsdennis]

I've been thinking more about this proposal, and I think what it does at its core is replace the need to track $id URIs with simple key/schema pairs. So instead of requiring a $dynamicAnchor in a subschema somewhere in a resource, it provides a dedicated place ($params) where a named schema could be defined. Then instead of the reference needing to be a URI (which is confusing), it just references the name using $paramRef.

What this also means is that parameters are defined at the schema level instead of at the resource level. If you want branching behavior, you can do it all within the same resource. No more strategically defining $ids to get dynamic references to work right.

There are a couple behavioral things from the original proposal that I'd to align with $dynamic*, though.

1. Add a "first wins" behavior

$dynamicRef takes the first matching $dynamicAnchor that it finds along the evaluation path starting from the root. This means that if there are other matching $dynamicAnchors in the resources along the evaluation path, they are ignored; we always use the first one.

So in this case:

{
  "$params": {
    "foo": { "type": "integer" }
  },
  "type": "array",
  "items": {
    "type": "object",
    "$params": {
      "foo": { "type": "string" }
    },
    "properties": {
      "bar": { "$paramRef": "foo" }
    }
  }
}

The bar properties would need to be integers, not strings, because that's the first foo parameter that was encountered.

The original proposal stated:

It refers to a parameter declared with nearest enclosing $params keyword.

But this creates an "overriding" behavior which is contrary to how $dynamic* works. I don't think that jives with proposing this feature as a replacement for $dynamic*.

2. Parameter "popping" (like a stack)

As evaluation "backs out" of a schema resource, it drops any $dynamicAnchors that it found in that resource.

{
  "$id": "base",
  "$defs": {
    "ref-target": {
      "$id": "target",
      "$comment": "Both anyOf subschemas point here",
      "$dynamicRef": "#definition",
      "$defs": {
        "undefined": {
          "$comment": "This is required with 2020-12, but we're removing that requirement for future releases",
          "$dynamicAnchor": "definition",
          "not": true
        },
      }
    }
  },
  "anyOf": [
    {
      "$id": "first",
      "$ref": "target",
      "$defs": {
        "resolved-for-first": {
          "$dynamicAnchor": "definition",
          "type": "string"
        }
      }
    },
    {
      "$id": "second",
      "$ref": "target",
      "$defs": {
        "resolved-for-second": {
          "$dynamicAnchor": "definition",
          "type": "number"
        }
      }
    }
  ]
}

Assuming an iterative approach, when the evaluation path passes through /anyOf/0, the $dynamicRef resolves to first#/$defs/resolved-for-first. Then evaluation "backs out" of /anyOf/0 and continues to /anyOf/1. At this point, the $dynamicRef resolves to second#/$defs/resolved-for-second.

If we make $params / $paramRef replicate this behavior, we can rewrite the schema:

{
  "$defs": {
    "target": {
      "$comment": "Both anyOf subschemas point here",
      "$paramRef": "definition"
    }
  },
  "anyOf": [
    {
      "$ref": "#/$defs/target",
      "$params": {
        "definition": {
          "type": "string"
        }
      }
    },
    {
      "$ref": "base#/$defs/target",
      "$params": {
        "definition": {
          "type": "number"
        }
      }
    }
  ]
}

I think the primary thing that sticks out to me is that we've been able to remove the need to manage $id URIs. That alone simplifies this a lot.

---

With these two additions to the proposed behavior, I think we have a functional replacement for $dynamic*.