Best Way to Rescursively Search JSON?

[meowitzher]

I am currently working on a system to load assets listed inside of JSON files dynamically, which ideally does not know the overall structure of the JSON it receives. I'd like to recursively look through all levels of the JSON data to look for a specific key ("Asset") and perform the necessary loading based on the value.

For example:

main.json:

"Assets":
[    
{ 
    "Asset":
    {
        "File": "assets/music/Music.wav",
        "Name": "Music",
        "Type": 3
    }
},
{
    "Asset":
    {
        "File": "assets/images/Image.png",
        "Name": "Success",
        "Type": 1
    }
}
],
"Layer":
{
    "Asset":
    {
        "File": "assets/data/sub.json",
        "Name": "File",
        "Type": 0
    }
}

sub.json:

"Layer":
{
    "Asset":
    {
        "File": "assets/data/Sound1.wav",
        "Name": "Sound1",
        "Type": 2,
        "Asset":
        {
            "File": "assets/sound/Sound2.wav",
            "Name": "Sound2",
            "Type": 2
        }
    }
}

I have the capability to load other JSON files and process them once they are found, but finding all of the "Asset" keys is proving difficult.

Ideally there would be some way to search through the JSON so that each of the JSON objects with key "Asset" could be found regardless of if it is inside an array or a subobject of a larger object. In general, the inner structure is known, i.e. every "Asset" object will have a "File", "Name", and "Type", but the outer structure is unknown: i.e., ["Assets"][0], ["Assets"][1], ["Layer"]["Asset"], etc. will not work.

I've tried using the items loop, but it only seems to get the keys at the top level. Is there an alternative which is recursive and iterates through all levels, or a convenient way to "join" the JSON in a way that flattens out the levels and allows items to access them?

While efficiency is a bonus, I am not imagining the need for this to scale too large, so solutions which are slow yet easy to implement are welcomed! If there is nothing currently in the syntax for this, then I can imagine a way to do it, but I'd rather not reinvent the wheel if I can avoid it.

[falbrechtskirchinger]

There's nothing in the API to do this for you. You'll have to iterate through objects/arrays yourself.

There is basic_json::flatten() but that wouldn't help you. Your example would look like this:

{
    "/Assets/0/Asset/File": "assets/music/Music.wav",
    "/Assets/0/Asset/Name": "Music",
    "/Assets/0/Asset/Type": 3,
    "/Assets/1/Asset/File": "assets/images/Image.png",
    "/Assets/1/Asset/Name": "Success",
    "/Assets/1/Asset/Type": 1,
    "/Layer/Asset/File": "assets/data/sub.json",
    "/Layer/Asset/Name": "File",
    "/Layer/Asset/Type": 0
}

[meowitzher]

Thanks for this! While the solution provided by nlohmann works for my purposes, I do think this could be useful as well, though.

Once it is flattened, it shouldn't be too hard to iterate through the new object searching for keys which contain "/Asset" immediately before their final "/" and to react appropriately. Not sure if it'd be more or less performant than a full recursive search, but something to try out if performance becomes an issue.

[falbrechtskirchinger]

I can't imagine a scenario where flatten() would perform better. I'd also recommend an iterative approach over a recursive one but that really depends on wether you might process malicious input. Here's some code I'm using adapted to your scenario:

std::vector<json *> stack{&root};
std::vector<json *> assets;
while(!stack.empty()) {
    auto &j = *stack.back();
    stack.pop_back();

    if(j.is_object()) {
        for(auto it : j.items()) {
            if(it.value().is_object() && it.key() == "Asset")
                assets.push_back(&it.value());
            else if(it.value().is_structured())
                stack.push_back(&it.value());
        }
    }
    else if(j.is_array()) {
        for(auto &el : j) {
            if(el.is_structured())
                stack.push_back(&el);
        }
    }
}

[nlohmann]

You can do something like this:

#include <nlohmann/json.hpp>
#include <iostream>

using json = nlohmann::json;

template<class UnaryFunction>
void recursive_iterate(const json& j, UnaryFunction f)
{
    for(auto it = j.begin(); it != j.end(); ++it)
    {
        if (it->is_structured())
        {
            recursive_iterate(*it, f);
        }
        else
        {
            f(it);
        }
    }
}

int main()
{
    json j = R"({
    "Assets": [
        {
            "Asset": {
                "File": "assets/music/Music.wav",
                "Name": "Music",
                "Type": 3
            }
        },
        {
            "Asset": {
                "File": "assets/images/Image.png",
                "Name": "Success",
                "Type": 1
            }
        }
    ],
    "Layer": {
        "Asset": {
            "File": "assets/data/sub.json",
            "Name": "File",
            "Type": 0
        }
    }
}
)"_json;

    recursive_iterate(j, [](json::const_iterator it){
        std::cout << it.key() << " : " << it.value() << std::endl;
    });
}

Output:

File : "assets/music/Music.wav"
Name : "Music"
Type : 3
File : "assets/images/Image.png"
Name : "Success"
Type : 1
File : "assets/data/sub.json"
Name : "File"
Type : 0

recursive_iterate just goes through the DOM of your JSON, and the passed lambda is called on every key-value pair.

(taken from https://stackoverflow.com/questions/45934851/c-nlohmann-json-how-to-iterate-find-a-nested-object/46630394?noredirect=1#comment113675135_46630394)

[gregmarr]

So I probably can't store a result pointing to json objects that could be modified or even deleted.

I think this is probably your issue, you're trying to store iterators for later use. I wouldn't recommend that. Can you do the operation immediately rather than storing the operation? If not, then your best bet is probably to store json_pointers instead. As long as you are only referring to object keys, and not array indices, they should still be stable as you operate on them.

[VolkerBartheld]

Yes, I need the matches for later use. However they don't necessarily need to be modifiable. In the end, I came up with

#include <assert.h>
#include <string>
#include <algorithm>
#include <list>
#include <nlohmann/json.hpp>
#include <boost/algorithm/string.hpp>

typedef std::list<nlohmann::detail::iteration_proxy_value < nlohmann::detail::iter_impl < const nlohmann::json >>> tMatches;
typedef std::list<nlohmann::json::value_t> tValueTypes;

void Recurse(const nlohmann::json& j, tMatches& Matches, const std::string& Key = "", const bool& MatchCase = true, const tValueTypes& ValueTypes = tValueTypes(), const unsigned int& RecursionMaxDepth = UINT_MAX, unsigned int RecursionDepth = 0)
{
    for (auto& el : j.items())
    {
        bool bKeyMatch = true;
        if (Key.size())
        {
            if (MatchCase) bKeyMatch = Key == el.key();
            else bKeyMatch = boost::iequals(Key, el.key());
        }
        bool bTypeMatch = true;
        if (ValueTypes.size()) bTypeMatch = ValueTypes.end() != std::find(ValueTypes.begin(), ValueTypes.end(), el.value().type());
        if (bKeyMatch && bTypeMatch) Matches.push_back(el);

        if (RecursionDepth >= RecursionMaxDepth) continue;
        if (nlohmann::json::value_t::object == el.value().type()) Recurse(el.value(), Matches, Key, MatchCase, ValueTypes, RecursionMaxDepth, RecursionDepth + 1);
    }
}

void main(void)
{
    nlohmann::json j;
    nlohmann::json j1 = { {"foo", 1}, {"bool", true}, {"float", 123.456},  {"string", "some string"} }, j2;
    j2["subgroup"] = j1;
    j["group1"] = j1;
    j["group2"] = j2;
    j["string"] = "All your base are belong to us";
    j["array"] = { 1, 2, 3, 4, 5 };
    j["foo"] = 42;

    tMatches m;

    // Search all numbers with key "foo", infinite depth.
    Recurse(j, m, "foo", true, { nlohmann::json::value_t::number_unsigned, nlohmann::json::value_t::number_integer, nlohmann::json::value_t::number_float });
    assert(3 == m.size());

    // Only search from within "group1" for numbers with key "foo".
    m.clear();
    Recurse(j["group1"], m, "foo", true, { nlohmann::json::value_t::number_unsigned, nlohmann::json::value_t::number_integer, nlohmann::json::value_t::number_float });
    assert(1 == m.size());
    assert(m.begin()->key() == "foo");
    assert(m.begin()->value().is_number_integer());
    assert(m.begin()->value() == 1);

    // Top level case insensitive search for key "STRING".
    m.clear();
    Recurse(j, m, "STRING", false, tValueTypes(), 0);
    assert(1 == m.size());
    assert(m.begin()->key() == "string");
    assert(m.begin()->value().is_string());
    assert(m.begin()->value() == "All your base are belong to us");

    // Find all existing groups in the top level.
    m.clear();
    Recurse(j, m, "", true, { nlohmann::json::value_t::object }, 0);
    std::string s;
    assert(2 == m.size());
    assert(m.begin()->key() == "group1");
    assert((++m.begin())->key() == "group2");
}

which might be a littly clumsy but seems to do the job. If anyone has something that works better in this context, I'll be happy to see code samples. Thanks to all who have added the contributions and ideas so far. Highly appreciated.

[falbrechtskirchinger]

I don't recommend using the detail namespace. I promise this is going to break soon (maybe 3.11.3).

If you don't need iterators you could store a std::pair<std::string, json *> (or std::pair<std::string, std::reference_wrapper<json>>).
Then use either Matches.emplace_back(el.key(), &el.value()) or Matches.emplace_back(el.key(), std::ref(el.value())).

[VolkerBartheld]

@falbrechtskirchinger : Thanks for the update. Had to add a const (no biggie, no intention to change the values inside the json object) but then worked like a charm:

typedef std::list<std::pair<std::string, std::reference_wrapper<const nlohmann::json>>> tMatches;
typedef std::list<nlohmann::json::value_t> tValueTypes;

void JsonContainer::RecurseFind(const nlohmann::json& j, tMatches& Matches, const std::string& Key, const bool& MatchCase, const tValueTypes& ValueTypes, const unsigned int& RecursionMaxDepth, unsigned int RecursionDepth)
{
    for (auto& el : j.items())
    {
        bool bKeyMatch = true;
        if (Key.size())
        {
            if (MatchCase) bKeyMatch = Key == el.key();
            else bKeyMatch = boost::iequals(Key, el.key());
        }
        bool bTypeMatch = true;
        if (ValueTypes.size()) bTypeMatch = ValueTypes.end() != std::find(ValueTypes.begin(), ValueTypes.end(), el.value().type());
        if (bKeyMatch && bTypeMatch) Matches.emplace_back(el.key(), std::ref(el.value()));

        if (RecursionDepth >= RecursionMaxDepth) continue;
        if (nlohmann::json::value_t::object == el.value().type()) RecurseFind(el.value(), Matches, Key, MatchCase, ValueTypes, RecursionMaxDepth, RecursionDepth + 1);
    }
}

[falbrechtskirchinger]

In that case, you might want to use std::cref() as well.