encoding/json: provide tokenizer

[gopherbot]

by krolaw:

This would be useful when parsing (really) large JSON documents in low memory
environments.

At the moment one would need to write their own comma and key handling code.  Since this
is available in the encoding/xml package (through RawToken),  it would be consistent to
have similar functionality in the json package.

Thanks.

[rsc]

Comment 1:

I agree that it might be nice in some cases. One reason there's one in xml and not json
is that tokenizing json is nearly trivial; not so of xml.
It's a bit too late to design new APIs for Go 1.2. Perhaps for Go 1.3.

Labels changed: added priority-later, go1.3, removed priority-triage, go1.2maybe.

Status changed to Accepted.

[robpike]

Comment 2:

Labels changed: removed go1.3.

[rsc]

Comment 3:

Labels changed: added go1.3maybe.

[rsc]

Comment 4:

Labels changed: added release-none, removed go1.3maybe.

[rsc]

Comment 5:

Labels changed: added repo-main.

[extemporalgenome]

Comment 6:

I'm certainly interested in this for a number of my projects. Existing 3rd party JSON
scanning packages often are just clones of encoding/json with the scanner exported; to
avoid code duplication in programs needing a scanner, it's better to use the 3rd party
lib for (un)marshaling as well, though that lib may or may not be maintained (and often
isn't).

[nitingupta910]

I'm parsing wikidata dump (http://dumps.wikimedia.org/other/wikidata/) which is in JSON format (~36GB) and is a single giant array containing objects:

[
    { "id":"Q1", "type":"item", ...},
    { "id":"Q8", "type":"item", ...},

    (millions of such objects)
]

With the current json Decoder interface it seems impossible to parse this JSON without reading in whole file in memory. So, exposing tokenizer would be really helpful.

[aclements]

I'd like to suggest an alternate, higher-level API for streaming JSON decoding.

Tokenizers and the existing "whole value" API are two opposite extremes on a spectrum. Many applications that require streaming decoding need incremental parsing at the upper levels of the JSON structure, but closer to the leaves simply need to get (potentially compound) values. At these lower levels, a tokenizer interface simply gets in the way. For example, in @nitingupta910's Wikipedia example, it's necessary to incrementally parse the top-level array, but for each element of the array it's far more convenient to use the regular JSON parser to get whole objects than to piece them together from the token stream.

Hence, my suggestion is to view the JSON data as a tree and expose a caller-driven in-order traversal of this tree. At any point in the traversal, the caller can ask for the entire subtree as a decoded JSON value, or it can descend or ascend the tree as appropriate. This is not entirely unlike a tokenizer, except that it's hierarchical (not linear), the caller can switch into and out of the full JSON decoder as convenient (rather than being trapped in one world or the other), and it abstracts the details of syntax such as separating commas and balancing brackets and braces.

This can all be done as a natural extension to the existing Decoder. The Decode method already reads just the next value and stops (even if there's more data in the Reader). All we would need are methods for descending into compound values, ascending after the last member of a compound value, and reporting where we are in the in-order traversal. Something like:

// Enter descends into the next compound JSON value in its input.
//
// If the next value is an array, subsequent calls to Decode will
// return the elements of that array in order. If the next value is an
// object, subsequent calls to Decode will return the key/value pairs
// of that object, alternating between returning the key and the value
// associated with that key. If the next value is any other type,
// Enter returns TraversalError.
func (*Decoder) Enter() error

// Exit ascends from the current compound JSON value in its input.
//
// The decoder must be at the end of an array or object that was
// previously Entered; otherwise, Exit returns TraversalError.
func (*Decoder) Exit() error

// Peek returns the type of the next value in the input. It may read
// from the input in order to determine the type of the value.
//
// If the next value is a non-compound value, Peek returns TypeNumber,
// TypeString, TypeBoolean, or TypeNull. If the next value is a
// compound value, Peek returns TypeArray or TypeObject. If the
// decoder has Entered an array and there are no more values in the
// array, Peek returns EndArray. Likewise, if the decoder has Entered
// an object and there are no more key/value pairs in the object, Peek
// returns EndObject. If there are no more values, Peek returns an
// io.EOF error.
func (*Decoder) Peek() (ValueType, error)

For example, using this interface, @nitingupta910's example could be parsed with the following code (eliding error handling):

d.Enter()
for {
    if typ, _ := d.Peek(); type == EndArray {
        break
    }
    d.Decode(&object)
    process(object)
}
d.Exit()

[peterwald]

Good idea @aclements. I like the idea of unifying the Decoder and Tokenizer such that you can switch seamlessly back and forth between whichever level of abstraction is desired at the time.

[keks]

@peterwald: You said you wanted to add a tokenizer for 1.5 and it's nearly finished. Did you implement a traditional tokenizer or @aclements proposal? I couldn't find your code on github or gerrit.

[peterwald]

@keks Basically both. The scanner that's currently in the encoding/json package needs work. State is spread throughout the scanner and the decoder, and in places, the decoder actually does some of it's own scanning. In some places, scanning is done multiple times using different scanner instances, etc...

I ended up having to rewrite portions of the scanner, so that's why it's taking me a while to make sure everything is well tested and structured. I wrote an underlying scanner that's simpler, then layered the Decoder on top of that, and added a higher-level api similar to what @aclements proposed. In addition, I have a "walker" helper class, that allows you to scan ahead to a particular node (using the underlying tokenizer) and then Decode or read tokens as needed. All of this is done using a forward only streaming model, so it should be very memory efficient regardless of the size of the document.

I have not pushed the code to Gerrit yet. I don't know what the policy is on getting unfinished code out for review, but I wanted to make sure it was pretty well complete.

I am working to push it before the end of the week.