Recursive Tree Traversal

[springcomp]

Please, consider adding features to do arbitrarily deep searches, much like the xpath query  //my-element/my-other-element.

[icaine]

+1
Use case 1: sometimes i do analyses of json schemas and i want to see values for a given key/select no matter how deep they are...
Use case 2: there is a value under unique key but deep in the structure so writing exact (long) path is annoying while the performance isn't an issue..

[springcomp]

I have drafted a very ugly working prototype for a new descendant-expression:

Recursive Traversal

JEP
Author	Maxime Labelle
Status	draft
Created	24-06-2023

Abstract

Motivation

Specification

A new descendant-expression will be added as an alternative to the expression grammar rule:

descendant = ".." identifier
descendant-expression = ( expression ) 1*( descendant )

expression =/ descendant-expression

A descendant-expression is a projection that returns an array with all the elements of the JSON input with the specified name.

Examples

Given the following JSON input:

{
  "name": "first",
  "top": { "name": "second" },
  "nested": {
    "name": [
      1, "string", false,
      { "name": "third" }
    ]
  }
}

The following expressions are possible:

Expression	Result
..name	["first","second",[1,"string",false,{"name":"third"}],"third"]
..name.length(@)	[5, 6, 4, 5]
..name..name	["third"]

Compliance Tests

This JEP standardizes a syntax that was formely not valid. For this reason, one of the syntax.json compliance tests must be changed or removed altogether:

    {
      "expression": ".foo",
      "error": "syntax"
    },
    {
      "expression": "foo..bar",
-     "error": "syntax"
+     "result": null
    },

A new file descendant.json will be added to the compliance test suite.

[kit494way]

I understand that the expression does not guarantee to return values in a specific order, is it right?

[kit494way]

Should we support ..[?value > `1`]?

descendant = ".." ( identifier / bracket-specifier )

[springcomp]

I understand that the expression does not guarantee to return values in a specific order, is it right?

Indeed nothing in JMESPath guarantees specific order.
That’s actually an open point.

As supporting filter-expression I think that’s a great idea.
As currently proposed, the descendant-expression is a projection and would not work with filters out of the box.

In fact the more I think of this, the more I think it should not return a projection, but an array instead.
Otherwise, you need to stop the projection to support something like this:

"..locations[]|[?state=='WA']"

[tschmidtb51]

@springcomp Sorry if I'm missing anything here but I wasn't able to figure that out quickly: What is the current status on that resp. what is missing to get this implemented? I would really like to be able to use that feature. (We would need that for a JSON with a recursive structure of unknown (but not unlimited) depth.)

[springcomp]

@tschmidtb51 thanks for your feedback.

I need to revisit the spec as it currently is written in terms of being a projection (a collection onto which downstream expressions are projected) rather that an array which is a single element onto which downstream expressions are executed.

As is needed for every proposal, I need to revisit a sample implementation as a proof of concept to dig deeper into the impact such proposal has.

[springcomp]

New updated draft proposal 👇

[springcomp]

Maybe we need a more general recursive-projection postfix operator.
Something like expression .. or expression[**].

Consider the following JSON input object:

{
  "name": "first",
  "top": { "name": "second" },
  "nested": {
    "name": [
      1, "string", false,
      { "name": "third" }
    ]
  }
}

The expression [**] would return:

[
  {
    "name": "first",
    "top": { "name": "second" },
    "nested": {
      "name": [
        1, "string", false,
        { "name": "third" }
      ]
    }
  },
  "first",
  { "name": "second" },
  "second",
  {
    "name": [
      1, "string", false,
      { "name": "third" }
    ]
  },
  [
    1, "string", false,
    { "name": "third" }
  ],
  1,
  "string",
  false,
  { "name": "third" },
  "third"
]

Then, expressions like:

Expression	Result
[**].name	[ "first", "second", [ 1, "string", false, { "name": "third" } ], "third" ]
[**].name | [**].name	["third"]

So it seems to be more general while giving the same power.
However, we would need to stop the projection to support chaining expressions on the resulting array.

[springcomp]

Warning: we need to account for type errors during recursive evaluation.

[springcomp]

Recursive Traversal

JEP
Author	Maxime Labelle
Status	draft
Created	13-05-2025

Abstract

Motivation

Specification

A new descendant-expression will be added as an alternative to the expression grammar rule:

recursive-traversal = ".."
descendant-expression =  recursive-traversal expression
descendant-expression =/ expression descendant-expression

expression =/ descendant-expression

A descendant-expression is an expression that is recursively executed on each element from the input using a depth-first traversal.
The results of the evaluation are collected into a resulting array.

When evaluated on a scalar, a descendant-expression is equivalent to evaluating the raw expression.

When evaluated on an array, a descendant-expression considers all items from the array, and evaluates the raw expression on each of them. As each item from the array is evaluated, the descendant-expression is evaluated, recursively, on the result of that evaluation.

When evaluated on an object, a descendant-expression considers all the values from the input object and evaluates the raw expression on each of them. As each value is evaluated, the descendant-expression is evaluated, recursively, on the result of that evaluation.

At each step, the results of the evaluations are collected, while null values are discarded.

Examples

Given the following JSON input:

{
  "name": "first",
  "top": { "name": "second" },
  "nested": {
    "name": [
      1, "string", false,
      { "name": "third" }
    ]
  }
}

The following expressions are possible:

Expression	Result
..name	["first","second",[1,"string",false,{"name":"third"}],"third"]
..name..name	["third"]

Evaluation

To better understand how a descendant-expression is evaluated, consider the first expression from the table above:

• ..name

First, the name identifier is evaluated on the entire input JSON object, resulting in "first".
Then, the descendant-expression is evaluated on each value from the input JSON object. Thus:

• `"first"`.name => null (that result is discarded).
• `{ "name": "second" }`.name => "second".
• `"second"`.name => null (that result is discarded).
• `{ "name": [ 1, "string", false, { "name": "third" } ] }`.name => [ 1, "string", false, { "name": "third" } ]
• `1`.name => null (that result is discarded).
• `"string"`.name => null (that result is discarded).
• `false`.name => null (that result is discarded).
• `{ "name": "third" }`.name => "third".

Finally, the results are collected into the resulting array:

• [ "first", "second", [ 1, "string", false, { "name": "third" } ], "third" ]

Compliance Tests

This JEP standardizes a syntax that was formely not valid. For this reason, one of the syntax.json compliance tests must be changed or removed altogether:

    {
      "expression": ".foo",
      "error": "syntax"
    },
    {
      "expression": "foo..bar",
-     "error": "syntax"
+     "result": null
    },

A new file descendant.json will be added to the compliance test suite.