Add a SAX parser

[nlohmann]

The library currently only supports DOM-like parsing. This does not scale when the input files are enormous (#927). I would like to discuss how a SAX-like parser could look like.

My proposal (heavily motivated by RapidJSON) is as follows:

struct SAX
{
    // a null value was read
    bool null();

    // a boolean value was read
    bool boolean(bool);

    // an integer number was read
    bool number_integer(number_integer_t);

    // an unsigned integer number was read
    bool number_unsigned(number_unsigned_t);

    // a floating-point number was read
    // the string parameter contains the raw number value
    bool number_float(number_float_t, const std::string&);

    // a string value was read
    bool string(const std::string&);

    // the beginning of an object was read
    // binary formats may report the number of elements
    bool start_object(std::size_t elements);

    // an object key was read
    bool key(const std::string&);

    // the end of an object was read
    bool end_object();

    // the beginning of an array was read
    // binary formats may report the number of elements
    bool start_array(std::size_t elements);

    // the end of an array was read
    bool end_array();

    // a binary value was read
    // examples are CBOR type 2 strings, MessagePack bin, and maybe UBJSON array<uint8t>
    bool binary(const std::vector<uint8_t>& vec);

    // a parse error occurred
    // the byte position and the last token are reported
    bool parse_error(int position, const std::string& last_token);
};

Some remarks:

• All functions return a bool: true if the parser should continue or false if the parser should stop processing the input.
• The proposal covers parsing of JSON, but also of CBOR, MessagePack, and UBJSON. Therefore, it contains extensions like array or object sizes as well as a binary type which do not occur when parsing JSON.
• The idea is that the user would implement the above struct (we need to discuss whether we make all functions virtual, define a default implementation, etc.) and pass it to new parse functions, e.g. void parse_json(SAX &sax); or void parse_ubjson(SAX &sax);.

What do you think?

[gregmarr]

The idea is that the user would implement the above struct (we need to discuss whether we make all functions virtual, define a default implementation, etc.) and pass it to new parse functions, e.g. void parse_json(SAX &sax); or void parse_ubjson(SAX &sax);.

For "define a default implementation", were you thinking that the library would include the struct declaration in the headers, and the implementation in a separate .cpp file that could be used or replaced as needed?

[nlohmann]

For "define a default implementation", were you thinking that the library would include the struct declaration in the headers, and the implementation in a separate .cpp file that could be used or replaced as needed?

I think I would rather say the library should define an interface that client code needs to implement.

[theodelrieu]

Maybe the "default implementation" could be a template argument of some sort, like adl_serializer currently is?

I have no experience with SAX at all but it could be a good occasion to continue the discussion which began in #605 and #774 with @vinniefalco.

[nlohmann]

I think "default implementation" makes little sense here, because it is an extension point for user code after all. Sorry for the confusion.

[theodelrieu]

So you could not use the SAX version without reimplementing the SAX struct?

[gregmarr]

I think pure virtuals would provide the most flexibility. That way a code base can have multiple objects that implement the SAX interface.

[nlohmann]

@theodelrieu Yes, the user code needs to implement the SAX interface and pass the object to the SAX parser.

[nlohmann]

I think an eof() event would be helpful to detect situations like false 10 which currently would just trigger boolean(false) and end. With an eof() event, one can detect that there is still some non-whitespace input.

[NickeZ]

I'm not sure where to write this, but I saw #601 #862 and thought that I would point out that there is a draft for typed arrays in cbor which might be interesting to implement. https://github.com/cbor-wg/array-tags

[dvhwgumby]

I am not a fan of this SAX struct approach (but I am not submitting a pull request so this is only my opinion). As a side point, in terms of C++ design I agree with gregmarr that pure virtuals would be a better approach.

I was using rapidjson and switched to this package because it's easier and more intuitive. (I have had to keep rapidJSON for our sax-based serializer/deserializer). I would hope any SAX implementation would keep the spirit of nlohmann/json.

As the 'S' in SAX is for ,,stream'', why not use the stream model which is more C++-isch anyway and fits what this package already does? That is, if the system encounters the key "foo" it could call std::istream& handle_key(std::istream& is, std::string const& key) (similar to the stream extraction operator -- but notice the second argument is ```const``) which could in most cases recursively call the appropriate stream functions, and set stream errors on failure. Also means I could read an array of object handles (which already have from_json handlers) in an intuitive way consistent with the non-SAX version (and consistent with reading objects from any other stream).

The downside of this, and all such parsers, is that handle_key has to know about every possible key, but the user can easily handle this by managing a list of expected keys and their handlers on the call stack.

For writing then you could perhaps do something like:

std::vector<things> the_things {thing_one, thing_two};
json_ostream["the_things"] << the_things;

OK, perhaps that's too much!

PS: I don't know what to call this package since its name is generic so that's why I say ,,this package'' or ,,nlohmann/json'' vs ,,rapidJSON''

[nlohmann]

Overview

So about the SAX parsing, or parsing in general:

The library currently supports any combination of the following items:

1. input: string, input stream, iterator range, container
2. strict parsing (parsing must end with EOF): yes/no
3. exceptions on parse error: yes/no
4. using a callback function to filter values: yes/no

In addition, we also have an acceptor which only returns a boolean to indicate whether the input was a valid JSON text (works with any of 1. and 2.).

SAX Parsing

The current take on a SAX parser can also be combined with 1., 2., and 3. I think, this not too far from the spirit of the library :-)

For testing purposes, I implemented a SAX parser which creates a basic_json value - so basically a "SAX-to-DOM" parser. Surprisingly (for me), its performance was at least as good as the original parser.

Planning

I am planning to replace the original parser (well, the part where no callback (4.) is used) with this SAX-DOM parser, and also use the SAX approach for the binary formats CBOR, MessagePack, and UBJSON. As a result, we would have SAX and DOM parsers for all formats without code duplication on the parser classes. Furthermore, I think we can also realize the acceptor with a SAX parser.

What do you think?

• @dvhwgumby Would this be a feasible approach for you? If not, could you please give more details for your proposed syntax?
• @dvhwgumby What do you propose instead of pure virtuals?
• @gregmarr What do you think of RapidJSON's approach to use templates like struct MyHandler : public BaseReaderHandler<UTF8<>, MyHandler>?

[gregmarr]

What do you think of RapidJSON's approach to use templates like struct MyHandler : public BaseReaderHandler<UTF8<>, MyHandler>?

One downside of this is that the parse() functions become templates. They have to take the handler using a template as the handlers don't share a common base class. It is a tradeoff between potential runtime performance improvements due to inlining vs virtual function calls compared to the code duplication that results from the multiple template instantiations. That's something that would have to be measured.

[dvhwgumby]

@nlohmann:

Would this be a feasible approach for you? If not, could you please give more details for your proposed syntax?
What do you propose instead of pure virtuals?

Consider the tiny save file below, extracted and simplified from our save format:

    {
        "marker_names": {
        "names": [
                  "Marker1",
                  "Marker2"
                  ],
          "objects": [
                      1,
                      2
                      ]
          }
      "markers": [
                  {
                    "index": 1,
                      "flags": 0,
                      "dependent_nodes": [
                                            1,
                                            4,
                                            5
                                            ]
                      },
                  {
                    "index": 2,
                      "flags": 0,
                      "dependent_nodes": [
                                            2,
                                            3
                                            ]
                      }
                  ],
    }

I imagine a SAX reader something like the following pseudocode. I assume the whole point of SAX parsing is that you want to read the JSON stream right into machine objects; if you wanted to read and query JSON objects you might as well just make a DOM. Note that my approach below supports this approach as well (which might make sense if you had several objects inside a large JSON) you would simply >> them into a json object, query it, discard it and then read the next, if any).

/// These read a uint64_t and look up (or create) a slot in a table:
void from_json(nlohmann::json const&, typename indexed_object<marker>::handle&);
void from_json(nlohmann::json const&, typename indexed_object<node>::handle&);

/// helper type for recognizing labels:
using label_handlers = std::map<std::string, std:function<void(nlohmann::sax_istream& is)>>;

load_marker_names(nlohmann::sax_istream& is) {
  std::vector<indexed_object<marker>::handle> handles;
  std::vector<std::string> names;
  label_handlers ls {{"names", [&](nlohmann::sax_istream& is) { is >> handles; }} , {"objects", [&](nlohmann::sax_istream& is) { is >> names; }}};
  while (auto l = get_label(is))
    ls[l](is);
  match_up_handles_and_names(handles, names);
}

load_marker_definitions(nlohmann::sax_istream& is) {...}

void load_save_object(nlohmann::sax_istream& is) {
  label_handlers ls {{"markers", load_marker_definitions}, {"marker_names", load_marker_names}};

  while (auto l = get_label(is))
    ls[l](is);
}

slurp_stream(std::istream& is) {
  nlohmann::sax_read_object(nlohmann::sax_istream(is), load_save_object);
}

[dvhwgumby]

By the way how should a SAX reader deal with JSON pointers? I don't use them so don't care much but any library should have support.

[nlohmann]

@dvhwgumby I personally do not think this approach is simpler, but YMMV. The code has little to do with what I think is SAX (btw: the "S" stands for "Simple"). I also do not understand why a parser would need to take care of JSON Pointers.

[dvhwgumby]

Thanks, that's my conceptual error: I had always thought of SAX as streaming because I only consider it for processing large data sets as they come in rather than using an (expensive) systolic process of read->extract->discard.

What I have never liked about RapidJSON is that I feel like I spend more time thinking about the syntax of the JSON and less about my own data. In your library it feels the other way around, so I get my job done faster and my code is clearer and easier to understand.

As for pointers: when you read the whole JSON into core before examining the data a pointer is easy to resolve and a library can just as well handle json_obj["foo"]["bar"] and json_obj["foo/bar"] automatically. But when streaming, a pointer can be a forward reference or backwards reference to something already read. Unless someone (user code? library code?) keeps track of this it's impossible to resolve. Personally I don't need this feature so I don't care much except that I hope any consideration of it does not complicate the non-pointer case.

[lambdafu]

Will outputting large json files in a streaming way also be part of this proposal?

[nlohmann]

In the sense that the file is not stored, but only events are emitted by the SAX parser: yes.

[nlohmann]

Brief update:

• We now have a SAX interface for JSON, CBOR, MessagePack, and UBJSON.
• We have an implementation of the SAX interface that creates a JSON value. In principle, a "SAX-to-DOM" parser. This is used for all input file formats. As a side effect, exceptions can be switched off, allowing a non-throwing parser for the binary formats (new feature, previously only for JSON).
• We also have an implementation of the SAX interface for an acceptor. This now allows to perform simple true/false syntax check for the binary formats (new feature, previously only for JSON).
• The JSON parser is now non-recursive - instead of using the call stack for structured values, a vector is used to keep track of the hierarchy. This brings a bit of performance, but also pushes the limit of maximal nesting, and should make a fixed depth possible (see Stack-overflow (OSS-Fuzz 4234) #832).

What is missing:

• The callback mechanism for the JSON parser has not been ported into the SAX world yet. I really would like to also have an implementation that uses the SAX interface to get rid of a lot of code that now only exists to support the callback.
• The interfaces need to be harmonized to accommodate the new features. This also includes another look at the input adapter interface (see Using input_adapter in a slightly unexpected way #834).
• I have some doubts whether it is a good idea to move the strings from the lexer to the string() and key() SAX events.

Any comments on this?

[theodelrieu]

About your last bullet point, I think you can simply use const std::string&, I don't see a use case for std::string&&. Could you point to a part of the code where there is one?

I haven't looked at the code yet, but does that interact well with from/to_json?

[nlohmann]

@theodelrieu I changed the interface. Now the lexer returns a reference. Then it is up to the consumer of the string to decide whether to copy or move.

It should not affect and from_json or to_json code - it is just the chain between lexer -> parser -> SAX events.

[theodelrieu]

I think that returning a non-const reference is quite dangerous.

However if you want to allow users to decide whether they want to move the string or not, one way is to overload on rvalue references:

const string_t& get_string() &
{
  return this->str;
}

string_t&& get_string() &&
{
  return std::move(this->str);
}

Then, to call the second overload:

auto str = std::move(lexer).get_string();

It might look Lovecraft-esque, but I think this is the most flexible and safe way.

[nlohmann]

When a string is parsed, the following steps are taken:

• The lexer reads a string literal, performs the required UTF-8 magic, and adds characters to the token_buffer.
• The lexer returns token_type::value_string to the parser.
• The parser calls get_string() and gets the reference of the lexer's token_buffer.
• When the lexer processes the next string or number literal (lexing number literals also need the string buffer to collect the digits), token_buffer.clear() is called.

From my understanding, calling clear() is not just handy to reset the buffer, but also required to make sure that token_buffer is in a valid state after moving. Did I miss something dangerous?

[maddanio]

confused that this is still open, isnt there a sax parser now?

[nlohmann]

It's only in the develop branch, but not yet released. The interface still might change, see #1153.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[gregmarr]

Still in progress, not stale.

[theodelrieu]

#1153 is to be reviewed, should be ok feature-wise

[nlohmann]

I shall try to look into the PR this weekend.

[nlohmann]

Thanks a lot everybody! After merging #1153, all that is left for the issue is some documentation. I shall work on this and then we should be ready for the next release.

[theodelrieu]

Quick nitpick on the release version, shouldn't it be a 3.2.0 instead?

[nlohmann]

(Spoiler alert: yes!)

[nlohmann]

I found a bug with the following example code:

#include <iostream>
#include <iomanip>
#include "json.hpp"

using json = nlohmann::json;

int main()
{
    // a JSON text
    auto text = R"(
    {
        "Image": {
            "Width":  800,
            "Height": 600,
            "Title":  "View from 15th Floor",
            "Thumbnail": {
                "Url":    "http://www.example.com/image/481989943",
                "Height": 125,
                "Width":  100
            },
            "Animated" : false,
            "IDs": [116, 943, 234, 38793]
        }
    }
    )";

    // define parser callback
    json::parser_callback_t cb = [](int depth, json::parse_event_t event, json & parsed)
    {
        // skip object elements with key "Thumbnail"
        if (event == json::parse_event_t::key and parsed == json("Thumbnail"))
        {
            return false;
        }
        else
        {
            return true;
        }
    };

    // parse (with callback) and serialize JSON
    json j_filtered = json::parse(text, cb);
    std::cout << std::setw(4) << j_filtered << '\n';
}

Skipping an object after parsing a key yields a situation where we have a null pointer on the reference stack. I need some time to fix this...

[nlohmann]

I fixed the issue described in #971 (comment) in e33b31e.