Keywords for describing array patterns; "concat", "someOf", array repetition/kleene star

[awwright]

Most regular/context-free grammars that are a subset of JSON documents have an equivalent representation in JSON Schema. However there's some kinds of JSON arrays that can be specified with a regular expression, but that has no JSON Schema equivalent. For example, an array whose items are an odd number of positive integers, then a boolean:

/^\[[1-9][0-9]*, ([1-9][0-9]*, [1-9][0-9]*, )* (true|false)\]$/

(Some whitespace/decimal forms supported in JSON is removed here for brevity; it is more complicated, but suffice to say it exists.)

In order to be able to convert between a regular/context-free language and JSON Schema, there needs to be some keywords that can implement the "array" counterparts to regular expressions in strings:

• "concat", to concatenate multiple grammars together, specified by an array of subschemas.
• "someOf", to describe alternation (validates if one or more of the subschemas is valid).
• "repeatMin"/"repeatMax", to describe repetition and the Kleene star.

I was trying to spec out a hierarchy of JSON Schema features (mostly by processing & memory complexity), and I realized array items with regular patterns was missing from the O(n) complexity class.

The lack of feedback relating to this sort of thing suggests this would have limited usefulness as a core requirement, but I'd like to describe it here for completeness. The only instance I can think of are arrays where even items represent a name, and odd items represent the value. Node.js describes raw HTTP headers this way.

[handrews]

The only instance I can think of are arrays where even items represent a name, and odd items represent the value. Node.js describes raw HTTP headers this way.

Some web frameworks use arrays like this to specify query strings with duplicate key names.

Do these keywords require some sort of new underlying JSON Schema feature? If not, would this be a better fit in the vocabularies repo?

[awwright]

Some web frameworks use arrays like this to specify query strings with duplicate key names.

Yeah, another good example. Sometimes it's just less verbose to do an array with odd/even pairings rather than an array of vector arrays.

Do these keywords require some sort of new underlying JSON Schema feature? If not, would this be a better fit in the vocabularies repo?

The "concat" keyword does not fit well in with how most implementations perform validation, and most implementations will probably implement a naive backtracking algorithm in O(n^2) time or worse, even though it can be done in O(n) with much pre-computation. The others should be fairly easy:

I think "someOf" or a similar feature has been requested multiple times (though I can't find any off-hand), and it's fundamentally the same thing as "oneOf".

And "repeatMax": null could represent the kleene star, i.e. allow the defined items to occur any number of times. This is trivially implemented as well. (Likewise repeatMin: 1, repeatMax: 4 could mean "at least one occurrence, max 4 repeats" of an odd/even pair of items, i.e. the array would have to have 2, 4, 6, or 8 items).

[handrews]

@awwright can you explain a bit more about how concat would work? I admit I'm having a bit of trouble wrapping my head around it. I think part of that is lack of clarity regarding "grammar" here - are you talking about these keywords taking strings in a new language of some sort? Rather than working by applying and combining schemas in some way? I realize we already support regular expressions, but they are ubiquitous across a wide range of programming languages.

[awwright]

@handrews It's essentially the same thing as concatenation of characters or groups in regular expressions:

(ab|cd|123)[0-9]e

There's three elements being concatenated together here (one alternation then two character classes, the second matches exactly one character)

It can get complicated when there's a repetition followed by an alternation:

^(abc)*(a|b|c)d$

If the first four characters of input is abca, you don't know if the fourth character matches the first group or the second, you have to follow both paths until one path matches or mismatches. You can skip the backtracking algorithm and execute this in O(n) time by computing the union of both paths.

So to write a schema with odd/even items that ends with a boolean, it might look like this:

{
type: "array",
concat: [
    { type: "array", prefixItems: [ {type:"string"}, {type:"integer"} ], minItems: 2, maxItems: 2, repeatMin: 0, repeatMax: null },
    { type: "array", additionalItems: { type: "boolean" }, minItems: 1, maxItems: 1 }
]
}

... there's different ways the "repeat" keywords could interact with other keywords, I haven't fully thought it out yet. Maybe they only apply to "concat" instead of any of the *items keywords.

[handrews]

@awwright thanks, I think I understand this now. Definitely interesting, and yes possibly involving an underlying change in JSON Schema capabilities.

In this example, concat is essentially behaving as a repeatable prefixItems. If the default behavior of concat were to repeat indefinitely, then just that alone would be fine (items is essentially a single element that repeats indefinitely, so that's well within normal capabilities). [EDIT: I misread the concat part and didn't realize how far the side scroll went, will update with a correct assessment later.]

However, keywords with a more complex impact on how an applicator applies and evaluates its schemas might require a more substantial change, so I'm in favor of keeping this issue in this repository while we consider that.

Ultimately I think this would fit better as an extension vocabulary than in the standard applicator vocabulary, but it's a really interesting idea for one!

[handrews]

I'm going to rewrite this with formatting I find easier to follow, and in YAML because I'm lazy.

type: array
concat:
  - type: array
    prefixItems:
      - type: string
      - type: integer
    minItems: 2
    maxItems: 2
    repeatMin: 0
    repeatMax: null
  - type: array
    additionalItems:
        type: boolean
    minItems: 1
    maxItems: 1

OK, looking at it like this, I see where the difficulties would be in the current model. Basically, it's the block of prefixItems/minItems/maxItems that you want to repeat. The type constraint and the repeatMin/repeatMax keywords are outside of the affected block.

I think this would need to be reworked a bit to make sure that any control keywords are outside of the schema object that they need to control. Which has its own wrinkles because you're trying to change the start point of prefixItems which contradicts its (current) specification. I'll have to think on this more. The concat part still seems straightforward enough to me.

[gregsdennis]

I agree with @handrews. I think what this needs is a new keyword for the repeating content.

I'd like to propose another new keyword to handle this: repeatedItems. It fits well with the repeatMin/Max as well. I'll stick with the YAML (🤢) because that's what's been used.

type: array
concat:
  - type: array
    repeatedItems:
      - type: string
      - type: integer
    repeatMin: 0
    repeatMax: null
  - type: array
    additionalItems:
        type: boolean
    minItems: 1
    maxItems: 1

(well... items, really, because additionalItems doesn't exist anymore)

Here, repeatedItems functions similarly to prefixItems except that it doesn't allow for follow-on items: it explicitly defines only those items which are to repeat. Using prefixItems entails some other complications, like the min/maxItems don't really apply like they normally would (they normally look at the whole array).

This also solves Henry's concern that repeatMin/Max should be defined outside of the bit that's being repeated. And it somewhat aligns with the contains keyword family.

---

The concat with an initial repeatedItems concerns me, however. With the schema above, how is [ "foo", 1, "bar", 2, true ] processed?

1. true doesn't match the repeatedItems, so I expect evaluation would stop for this? (Say, under the annotation model, it leaves an annotation of 3 to indicate the index of the last successfully evaluated item.)
2. Then the concat would need to forward that annotation (or otherwise communicate the result of the first subschema) into the second subschema so that items knows where to start evaluating.
3. The second subschema evaluates... what?

The second subschema, as written, evaluates the whole array, which in this case would fail. But the concat somehow changes how this subschema operates? Or maybe it uses the results from the first subschema to slice the array into a subarray that the second subschema evaluates? I'm not really sure what's expected to happen under the covers. Both of these approaches are departures from how schema evaluation is expected to work.

One way that I can see to resolve this is to just remove the concat and have it all as a single schema, then have items (and unevaluatedItems) also depend on the results of repeatedItems.

type: array
repeatedItems:
  - type: string
  - type: integer
repeatMin: 0
repeatMax: null
items:
    type: boolean
minItems: 1
maxItems: 1

This solves the items problem, but that min/maxItems is still out of place. Maybe you could use something like prefixItems with an items: false so that you could specify exactly what you're looking for in prefixItems and allow nothing else.

type: array
repeatedItems:
  - type: string
  - type: integer
repeatMin: 0
repeatMax: null
prefixItems:
    type: boolean
items: false

But then it's strange that "prefixItems" isn't specifying what comes first, and it removes a lot of flexibility... which leads back to using concat to specify composition.

[jdesrosiers]

I think this is a really exciting idea. Array validation is definitely a place were JSON Schema is lacking.

The lack of feedback relating to this sort of thing suggests this would have limited usefulness as a core requirement

I disagree. It's certainly not super common, but I've seen quite a few SO questions over the years where I've had to tell people that JSON Schema can't express the weird sequence they need to describe. If we can come up with a good way to improve that situation, I think it's very well worth considering for the spec.

I'd like to suggest something similar to what @gregsdennis proposed, but a little inverted. The repeatMin and repeatMax would be defined such that they work like minContains and maxContains. They would describe the number of sequential items matches in the array. Like prefixItems, any items after repeatMax go unevaluated.

I think that would allow concat to be implemented with no other additional keywords and would mostly fit into the current architecture. The only change would be that array keyword implementations would have to take a starting index as input in addition to the array being validated. I'd have to implement it to be sure, but I think that's the only issue.

It's worth noting that concat would be a dynamic keyword because it would rely on annotation results of the schemas it processes to know how many items were evaluated and where the starting index should be for the next schema in the sequence.

Here are some examples. Sorry, I'm sticking with JSON because I find YAML difficult to read.

^ab{0,3}c$

{
  "type": "array",
  "concat": [
    {
      "prefixItems": [{ "const": "a" }]
    },
    {
      "items": { "const": "b" }, 
      "repeatMin": 0,
      "repeatMax": 3
    },
    {
      "prefixItems": [{ "const": "c" }]
    },
    { "items": false }
  ]
}

We can also define repeatMax/repeatMin to work with concat as well as items to describe more complex repetitions. concat would repeat indefinitely by default (kleene star) like items and could be constrained by repeatMax/repeatMin.

^(ab){0,3}$

{
  "type": "array",
  "concat": [
    { "prefixItems": [{ "const": "a" }, { "const": "b" }] }
  ],
  "repeatMax": 3,
  "unevaluatedItems": false
}

concat can also be nested for even more complex sequences.

^a(b{1,2}c){0,2}$

{
  "type": "array",
  "concat": [
    { "prefixItems": [{ "const": "a" }] },
    {
      "concat": [
        {
          "items": { "const": "b" },
          "repeatMin": 1,
          "repeatMax": 2
        },
        { "prefixItems": [{ "const": "c" }] },
      ],
      "repeatMax": 2
    },
    { "items": false }
  ]
}

Alternation can be done with anyOf/oneOf, so there's not need for someOf.

^((a|b)c)*$

{
  "type": "array",
  "concat": [
    {
      "anyOf": [
        { "prefixItems": [{ "const": "a" }] },
        { "prefixItems": [{ "const": "b" }] }
      ]
    },
    { "prefixItems": [{ "const": "c" }] }
  ]
}

I don't want to get deep into arguing about keyword naming just yet, but I'd suggest minRepeat/maxRepeat instead of repeatMin/repeatMax to stick with current conventions for min/max keyword names. "Repeat" might not be the best word either. Maybe "matches"? I'd also suggest the name sequence instead of concat. There might be a better word than "sequence", but I think the concept of concatenating grammars will be confusing. It's also worth noting that this makes the naming of prefixItems a little awkward because the items it describes are not necessarily at the beginning of the array.

[gregsdennis]

I think this still breaks a basic tenet of how JSON Schema works: schema objects evaluate the instance independently.

For example, in the schemas above,

{ "prefixItems": [{ "const": "c" }] }

is itself dynamic because it doesn't know where to start and relies on the evaluations of previous subschemas for this information. (Note we do have keywords that rely on evaluations from other keywords, but we don't have that behavior in subschemas.)

For every other applicator that contains multiple subschemas, the schema objects operate completely independently of their siblings, thus each evaluates the entire (local) instance. concat, as proposed, breaks this idea.

This new behavior is a significant departure from the current operating model.

[handrews]

@gregsdennis yes, I agree. I think this could be addressed by creating a segmentItems to use in place of prefixItems, which would be similar but would not be restricted to the prefix. It might be possible to define interactions among keywords like segmentItems, minSegmentItems, maxSegmentItems, segmentStart, segmentRepeat, etc. that would keep this within the paradigm of determining an instance location and evaluating the schema against that location as independently as current keywords operate (which is not, strictly speaking, completely independently).

This is where I think it's important to not have "operator" keywords like minRepeat, etc. inside the schema on which they operate. That is a communication channel that does not fit the current paradigm.

However, adjacent keywords impacting each other is within the current paradigm. It's not immediately clear to me whether this introduces complexity beyond what our current paradigm supports. I think the key thing is to first see if we can keep this within the paradigm at all.

[jdesrosiers]

I think this still breaks a basic tenet of how JSON Schema works: schema objects evaluate the instance independently.

Oh, I agree that there is an element that doesn't fit the current architecture. Sorry if I didn't make that clear enough.

This new behavior is a significant departure from the current operating model.

I'd have to implement it to decide if I think it's a significant departure or something that could be relatively easily incorporated. I honestly don't have a solution in mind, so it very well could end up being a significant change.

This is where I think it's important to not have "operator" keywords like minRepeat, etc. inside the schema on which they operate. That is a communication channel that does not fit the current paradigm.

I don't know if this was specifically in response to my comments, but I think the way I defined minRepeat/maxRepeat fits the current paradigm just fine. It works exactly like minContains/maxContains. Managing the starting index should be the only thing that doesn't fit the model.

I think the key thing is to first see if we can keep this within the paradigm at all.

100% agree, but at this point I don't think it's going to be possible to support this kind of thing without breaking the mold somewhere. I think we'll have to come up with a few ideas, determine how they don't fit the model, determine how to model could be adjusted, and decide if the break is worth it. Of course, I'll be thrilled to be wrong if someone comes up with a solution that does fit the model.

[handrews]

I don't know if this was specifically in response to my comments, but I think the way I defined minRepeat/maxRepeat fits the current paradigm just fine. It works exactly like minContains/maxContains. Managing the starting index should be the only thing that doesn't fit the model.

The difference is that prefixItems defines its start index, and minItems and maxItems are defined over the whole array. We'd either have to change that (which I'd rather not do- it's nice to have simple, straightforward keywords for the more common case), or use a segmentItems, minSegment, and maxSegment that determine their start index and length of scope based on adjacent keywords.

It's only the interaction of either concat or minRepeat/maxRepeat with prefixItems/minItems/maxItems or other keywords that define their relationship to array item positions that is problematic.

Currently, the applicator behavior is defined in §7.5 as:

From [the root], keywords known as applicators are used to determine which additional schemas are applied. Such schemas may be applied in-place to the current location, or to a child location.

The schemas to be applied may be present as subschemas comprising all or part of the keyword's value. Alternatively, an applicator may refer to a schema elsewhere in the same schema document, or in a different one. The mechanism for identifying such referenced schemas is defined by the keyword.

So if a segmentItems keyword read its starting point and repeat conditions from adjacent keywords, that would probably fit within the current paradigm. We can think of current keywords like this:

• items reads its starting point from prefixItems and is repeated until the instance ends
• unevaluatedItems computes its starting point from adjacent and dynamic subscope prefixItems, items, unevaluatedItems and contains, and repeats until the end of the instance except that it skips indices after the starting point that were covered by contains

We do not have a direct precedent for a minSegment/maxSegment that would take a starting point from which to count, but that feels like it probably fits well enough.

concat might be more problematic, because it's fine for a keyword to determine its starting point based on adjacent or dynamic subscope information (as noted above, we already do this), but determining the starting point of an entire subschema based on the output of another subschema, and then determining the starting point of segmentItems, etc. relative to the point determined via concat... that's quite different. The segmentItems would require information from sibling schemas by way of the parent concat keyword, and that is not a communication path we currently allow.

We do have a dynamic parent lookup behavior that $dynamicRef uses, but that's a very different context, and does not encompass the behavior of routing information from one sibling subschema to another. Even if/then/else is still just communication between adjacent keywords, not adjacent schema objects.

[gregsdennis]

unevaluatedItems computes its starting point from adjacent and dynamic subscope

Scope! Yes! That's what feels weird.

Taking from @jdesrosiers example:

{
  "type": "array",
  "concat": [
    {
      "prefixItems": [{ "const": "a" }]
    },
    {
      "items": { "const": "b" }, 
      "repeatMin": 0,
      "repeatMax": 3
    },
    {
      "prefixItems": [{ "const": "c" }]
    },
    { "items": false }
  ]
}

In this schema, the scope (adjacent or dynamic) of /concat/2 is only itself. It can't see what its siblings do because those schemas are out of its scope.

[awwright]

Yeah, concat does use subschemas in a fundamentally different way than any other "applicator" keyword. It's not just testing subschemas against some single instance then aggregating the results: Here, the subschemas each affect each other.

Here's another way to think about concat: "concat" asserts that there is some way to split the instance apart into segments (into multiple arrays of any length), so that each segment validates against the corresponding subschema in concat.

Depending on what you know about the subschemas you can optimize this process, potentially as good as O(n), but worst case (when the subschemas are completely opaque), you'll need a recursive algorithm in O(n^m) time (instance length raised to the subschema count—yikes!).

[jdesrosiers]

Yeah, concat does use subschemas in a fundamentally different way than any other "applicator" keyword. It's not just testing subschemas against some single instance then aggregating the results: Here, the subschemas each affect each other.

Right. I think that's effectively what @handrews was trying to say, but I didn't entirely follow the argument. Usually a keyword that uses an annotation as input would look that annotation up first and then do it's work. It's unprecedented, but is it really significantly different if it looks up annotations while it's doing it's work after it processes each sub-schema?

That's the case of the sub-schemas passing the new starting point back to concat. I think that should be fine. The problem is concat passing the initial starting point to the sub-schemas. That communication can't be done through annotations as far as I can see. That's where the architectural break would be. @handrews, if that's what you were saying, then we're in agreement.

@handrews, I think what made it hard for me to follow your last comment was that you introduced some keywords and I wasn't clear how you intended them to be defined and used. Maybe you can provide an example.