17
$\begingroup$

Too long? Go to Problems section

Background

I like to learn by doing small, sometimes artificial, projects. Among other things I had 'parsers', and 'stream methods / streams in MMA' on my to learn list.

So I decided to join it and learn that by building a streaming api for JSON files. We will get to what that means.

I did some research and I think I know what I need to do but I don't see how this can be done in reasonable manner in Mathematica.

What I want to build

Shortly, such api/parser advances step by step (if told to) through a stream and produces events on which user can do something. Events are specific for a parser/format, so in JSON case they can be 'objectBeginning', 'objectEnd', 'keyName', 'stringValue', 'trueValue' etc.

Simple use case, again shortly, 'parse untill you find a keyName "metadata", read value, close stream'.

The point is, all that is done without reading whole JSON into memory.

Read more in:

https://javaee.github.io/jsonp/

https://javadoc.io/doc/javax.json/javax.json-api/1.1

http://www.saxproject.org/event.html

How I want to build that

I decided to start by more or less imitate javax.json mentioned above.

So there should be a next[stream_] method which should succesively return events:

The parser can generate the following events: START_OBJECT, END_OBJECT, START_ARRAY, END_ARRAY, KEY_NAME, VALUE_STRING, VALUE_NUMBER, VALUE_TRUE, VALUE_FALSE, and VALUE_NULL.

The exact form does not matter because I failed to even Read it properly :)

Problems

After reading about Read, DefineInputStringMethod (tutorial/StreamMethods) and friends, I came to a conclusion that this framework is not suited for this or I just can't grasp it, thus the question, I want to understand :)

  • I don't know how to efficiently implement Read e.g. a STRINGValue

    which should return content separated by quotes ("string") but we have to keep in mind that it can contain escaped quotes. ("str \" ing")

    E.g.:

     Read[StringToStream["\"start \\\"end\""], Word, WordSeparators -> {"\""}]
    

    "start \" (terminated too quickly)

    One could go with ReadString

      ReadString[StringToStream["\"start \\\"end\""], Except["\\"] ~~ "\""]
    

    "\"start \\"en"

    but we lose the last character, represented by Except, as separators are not part of objects. So we need to go back for it. You can already suspect you are doing something wrong when such basic operation gets so messy.

    I don't even proceed with this because we need Skip methods and there is no SkipString to support this type.

    Escaped tokens/separators seem to be a core of this problem, otherwise e.g. TRUEValue can be implemented by putting "true" inside TokenWords options.

  • Speed

    While memory is what we care about, we can't spend 2 minutes on parsing/skipping 10MB of JSON. And you can't Compile, even procedural style, code with While Read etc. So it is too high level to be efficient.

    I could solve STRINGValue problem by reading Character by Character, handling escaped quotes and all that but this will take forever.

  • DefineInputStreamMethod

    I don't really see how this could help, it rather seems to provide an api to 'preprocess' streams. Unless I'm mistaken it does not have tools to add new types, easily emmit events or speed up parsing process but taking it 'deeper'.

    Let me know if I am wrong.

Questions

I guess this boils down to what is a reasonable way to do this?

I'd also appreciate comments on:

  • If my approach is correct:

    • How to add low level types support for Read

    • How to write fast Read based procedures (ReadList and friends can't be used as we don't see the content in advance

  • And if not

    • Is there a more idiomatic approach?

    • If there is not, why? Isn't that something fundamental for a language?

    • Am I right thinking that linking external libraries only make sense if they support all features you need, otherwise building on top will lead to problems outlined in Problems/speed?


Keywords:

event based parser, SAX, SAX2, streaming interface, push parser

Related:

BASIC CONCEPTS OF READ

Wrapping a C library with a streaming interface

$\endgroup$
  • $\begingroup$ My best suggestion would be to build a back-end Association to cache data about, e.g. whether you've got unmatched braces, and use some combination of Read up to various potential tokens, to build a string that can be tested against with a compiled regex and to parse it out like that. Then provide events for when these patterns match. It'd be a bit tedious, but I can see it working with okay performance. $\endgroup$ – b3m2a1 Oct 17 '17 at 6:54
  • $\begingroup$ @b3m2a1 if I get it right that only makes sense if you plan to parse/work with a specific file more than once, right? For one time data extraction it is not very useful. $\endgroup$ – Kuba Oct 18 '17 at 8:29
  • $\begingroup$ I wasn't actually necessarily proposing extracting the data. I was picturing parsing some JSON or XML block, where you need to know what part of the block you're in, hence tracking like quantities of open and close brackets. Then I figured read up until you hit any of "{"|"}"|"\""|":" and check to see if you have a complete token or block or whatever, and continue on like that. That's basically the lexing side of things. Then your parser would apply rules to those tokens / blocks. I haven't thought through all of the performance considerations of this strategy though. It might be unworkable. $\endgroup$ – b3m2a1 Oct 18 '17 at 8:35
  • $\begingroup$ @b3m2a1 So you suggest the logic for the lexer, I think this is not the issue here. Also, notice that all those tokens can be escaped by being in a string so more (not very) sophisticated state tracking is needed and the point of the question is, it seems there are no tools for that. $\endgroup$ – Kuba Oct 18 '17 at 8:41
  • $\begingroup$ Yeah my backend suggestion was basically to handle all of those escapes and such complications. I agree there are no good tools for it, but I'd argue it's always a bit of a pain to do these kinds of things, based on work I've done in python with DSLs and mini-interpreters. Leonid's streaming work might provide a good backbone for future support of this type of feature, but who knows how far in the future that'd be. $\endgroup$ – b3m2a1 Oct 18 '17 at 8:46
8
+50
$\begingroup$

Note:

If you want this type of parser added for JSON, I think WRI could do it easily. They already have Developer`ReadRawJSONStream so I think adding some event-based parsing to that wouldn't be too much to ask


This has been kicking around my for the past few days, so here's a quick example of what I discussed in my comment. It is by no means complete, but it's a start.

We'll simply define a bunch of different tokens to look for and handle each of them differently and then layer a reader on top of that. Here's the core code for that:

jStreamReader[stream : _String | _File | _InputStream] :=
 Module[{
   jStreamReader,
   jStreamData
   },
  jStreamReader~ClearAttributes~Temporary;
  jStreamData~ClearAttributes~Temporary;
  jStreamData =
   <|
    "InString" -> False,
    "BlockDepth" -> <|Association -> 0, List -> 0, 
      CompoundExpression -> 0|>,
    "BlockStack" -> {},
    "Cache" -> Internal`Bag[],
    "CacheStack" -> {},
    "CachePush" ->
     Function[
      Internal`StuffBag[jStreamData["Cache"], #]
      ],
    "CacheRecurse" ->
     Function[
      jStreamData["CacheStack"] = {jStreamData["CacheStack"], 
        jStreamData["Cache"]};
      jStreamData["Cache"] = Internal`Bag[];
      ],
    "CacheReset" ->
     Function[
      With[{c = jStreamData["CacheStack"]},
       jStreamData["CacheStack"] = c[[1]];
       jStreamData["Cache"] = c[[2]];
       ]
      ],
    "CachePart" ->
     Function[
      Internal`BagPart[jStreamData["Cache"], #]
      ],
    "CacheClear" ->
     Function[
      jStreamData["Cache"] = Internal`Bag[];
      ],
    "CacheDump" ->
     Function[
      With[{data = Internal`BagPart[jStreamData["Cache"], All]},
       jStreamData["Cache"] = Internal`Bag[];
       data
       ]
      ],
    "Stream" ->
     Replace[stream, {
       _File | _String?FileExistsQ :> OpenRead[stream],
       _String :> StringToStream[stream]
       }]
    |>;
  jStreamReader["HeldSymbol"] = Hold[jStreamData];
  jStreamReader["Symbol"] := Unevaluated[jStreamData];
  jStreamReader["Data"] := jStreamData;
  jStreamReader["Next"] := jStreamReadToken[jStreamReader];
  jStreamReader[s__] := jStreamData[s];
  jStreamReader /: Set[jStreamReader[p___], v_] :=

   jStreamData[p] = v;
  jStreamReader /: ReadString[jStreamReader, a___] :=

   ReadString[jStreamData["Stream"], a];
  jStreamReader /: Read[jStreamReader, a___] :=

   Read[jStreamData["Stream"], a];
  jStreamReader /: ReadList[jStreamReader, a___] :=

   ReadList[jStreamData["Stream"], a];
  jStreamReader /: StreamPosition[jStreamReader] :=

   StreamPosition@jStreamData["Stream"];
  jStreamReader /: SetStreamPosition[jStreamReader, p_] :=

   SetStreamPosition[jStreamData["Stream"], p];
  jStreamReader /: Close[jStreamReader] :=
   (
    Close@jStreamData["Stream"];
    jStreamData // Remove
    );
  jStreamReader
  ]
$jStreamBracketTokenIndicators =
  {"{", "}", "[", "]", "(", ")"};
$jStreamChunkTokenIndicators =
  {",", ":"};
$jStreamStringTokenIndicators =
  {"\""};
$jStreamInStringTokenIndicators =
  {"\\\"", "\""};
$jStreamPossibleTokenIndicators =
  Alternatives @@ Join[
    $jStreamStringTokenIndicators,
    $jStreamBracketTokenIndicators,
    $jStreamChunkTokenIndicators
    ];
$jStreamInStringTokenIndicators =
  Alternatives @@ $jStreamInStringTokenIndicators;
$jStreamBracketTokenIndicators =
  Alternatives @@ $jStreamBracketTokenIndicators;
$jStreamBracketMap = <|
   "{" -> {Opening, Association},
   "}" -> {Closing, Association},
   "[" -> {Opening, List},
   "]" -> {Closing, List},
   "(" -> {Opening, CompoundExpression},
   ")" -> {Closing, CompoundExpression}
   |>;
jStreamReadToSep[reader_] :=
  Module[{
    sp = StreamPosition@reader,
    strm = reader["Stream"],
    ret,
    sep
    },
   ret =
    With[{test = Read[strm, Character]},
     If[test === EndOfFile, Throw[EndOfFile]];
     SetStreamPosition[strm, sp];
     If[reader["InString"],
      If[StringMatchQ[test, $jStreamInStringTokenIndicators] ||

          StringMatchQ[
         test <> "\"", $jStreamInStringTokenIndicators],
       "",
       ReadString[strm, $jStreamInStringTokenIndicators]
       ],
      If[StringMatchQ[test, $jStreamPossibleTokenIndicators],
       "",
       ReadString[strm, $jStreamPossibleTokenIndicators]
       ]
      ]
     ];
   sep =
    If[reader["InString"],
     With[{ec = Read[reader, Character]},
      If[ec === "\\", ec <> Read[reader, Character], ec]
      ],
     Read[reader, Character]
     ];
   If[StringMatchQ[sep, $jStreamBracketTokenIndicators] && 
     StringLength@StringTrim[ret] > 0,
    SetStreamPosition[reader, StreamPosition[reader] - 1];
    sep = ""
    ];
   {ret, sep, sp}
   ];
jStreamHandleSepData[reader_, {ret_, sep_, sp_}] :=

  With[{sepData = $jStreamBracketMap[sep]},
   Which[
    sep === "",
    {ret, sep, Value, Expression},
    sep === ":",
    {ret, sep, Key, None},
    sep === ",",
    {ret, sep, Value, Expression},
    sep === "\"" && reader["InString"],
    reader["InString"] = False;
    {ret, sep, None, String},
    sep === "\"",
    reader["InString"] = True;
    {ret, sep, None, Continue},
    sep === "\\\"",
    {ret, sep, None, Continue},
    sepData[[1]] === Closing,
    If[reader["BlockStack"][[-1]] == sepData[[2]],
     reader["BlockDepth", sepData[[2]]] =
      Max@{reader["BlockDepth", sepData[[2]]] - 1, 0};
     reader["BlockStack"] = Drop[reader["BlockStack"], -1]
     ];
    {ret, sep, sepData, Expression},
    sepData[[1]] === Opening,
    reader["BlockDepth", sepData[[2]]] =
     Max@{reader["BlockDepth", sepData[[2]]] - 1, 0};
    reader["BlockStack"] =
     Append[reader["BlockStack"], sepData[[2]]];
    {ret, sep, sepData, None},
    True,
    {ret, sep, sepData, Expression}
    ]
   ];
jStreamReadTokenSegments[reader_] :=
 Block[{segs},
  segs = {None, 
    jStreamHandleSepData[reader, jStreamReadToSep[reader]]};
  While[segs[[-1, -1]] === Continue,
   segs = {segs, 
     jStreamHandleSepData[reader, jStreamReadToSep[reader]]}
   ];
  Cases[segs, {_String, _String, __}, \[Infinity]]
  ]
jStreamBuildToken[segs_] :=
 {
  Switch[segs[[-1, -1]],
   None, Null,
   String,
   {
    ToExpression@StringJoin@segs[[All, ;; 2]],
    String
    },
   _,
   {
    Replace[StringTrim@StringJoin@segs[[-1, 1]], {
      "null" -> Null,
      e_ :> ToExpression@e
      }],
    segs[[-1, -1]]
    }
   ],
  Replace[segs[[-1, -2]], {
    {o_, "{}"} :> {o, Association},
    {o_, "[]"} :> {o, List},
    {o_, "()"} :> CompoundExpression
    }]
  }
jStreamReadToken[reader_] :=

  Catch@jStreamBuildToken@jStreamReadTokenSegments[reader];

This generates a reader symbol that tracks the data in a mutable way, allowing it to act like a prettied-up stream in many ways.

Here's support for reading JSON data types:

(*Different types of read processors *)

jStreamRead[reader_, Key] :=
  Replace[jStreamReadToken[reader], {
    {Null, Key} :>
     Replace[reader["CacheDump"][][[-1, 1]],
      {a_, String | Expression} :> a
      ],
    EndOfFile :> EndOfFile,
    e_ :>
     (
      reader["CachePush"][e];
      jStreamRead[reader, Key]
      )
    }];
jStreamRead[reader_, Association] :=

  Replace[jStreamReadToken[reader], {
    {_, {Closing, Association}} :>

     Association@Cases[reader["CacheDump"][], _Rule],
    {Null, Key} :>
     (
      reader["CachePush"][
       reader["CachePart"][-1][[1, 1]] ->
        (
         reader["CacheRecurse"][];
         ((reader["CacheReset"][]; #) &@jStreamRead[reader, Value])
         )
       ];
      jStreamRead[reader, Association]
      ),
    EndOfFile :> EndOfFile,
    e_ :>
     (
      reader["CachePush"][e];
      jStreamRead[reader, Association]
      )
    }];
jStreamRead[reader_, List] :=
  Replace[jStreamReadToken[reader], {
    {_, {Closing, List}} :>
     reader["CacheDump"][],
    {{v_, _}, None | Value} :>
     (
      reader["CachePush"][v];
      jStreamRead[reader, CompoundExpression]
      ),
    {Null, {Opening, t_}} :>
     (
      reader["CachePush"][
       jStreamRead[reader, t]
       ];
      jStreamRead[reader, CompoundExpression]
      ),
    EndOfFile :> EndOfFile
    }];
jStreamRead[reader_, CompoundExpression] :=

  Replace[jStreamReadToken[reader], {
    {_, {Closing, CompoundExpression}} :>
     $wrapper @@ 
      reader["CacheDump"],
    {Null, {Opening, t_}} :> jStreamRead[reader, t],
    {{v_, _}, None | Value} :>
     (
      reader["CachePush"][v];
      jStreamRead[reader, CompoundExpression]
      ),
    {Null, {Opening, t_}} :>
     (
      reader["CachePush"][
       jStreamRead[reader, t]
       ];
      jStreamRead[reader, CompoundExpression]
      ),
    EndOfFile :> EndOfFile
    }];
jStreamRead[reader_, Value] :=
  Replace[jStreamReadToken[reader], {
    {{a_, _}, None | Value} :>
     a,
    {Null, {Opening, t_}} :> jStreamRead[reader, t],
    EndOfFile :> EndOfFile,
    e_ :>
     (
      reader["CacheAdd"][e];
      jStreamRead[reader, Value]
      )
    }];
jStreamRead[reader_, KeyValuePattern] :=

  jStreamRead[reader, Key] ->
   jStreamRead[reader, Value];
jStreamRead[reader_, Automatic] :=

  Replace[jStreamReadToken[reader], {
    {Null, {Opening, t_}} :> jStreamRead[reader, t],
    {{a_, _}, None | Value} :>
     a
    }];
jStreamRead[reader_, "Token"] :=
  jStreamReadToken[reader];

We'll then layer a more convenient interface on top of that:

JSONStream[strm : _String | _File | _InputStream] :=

  JSONStream[jStreamReader[strm]];
JSONStreamRead[JSONStream[s_Symbol], type_: "Token"] :=

  Replace[jStreamRead[s, type],
   EndOfFile | (_ -> EndOfFile) :> JSONStreamClose[JSONStream[s]]
   ];
JSONStreamClose[JSONStream[s_Symbol]] :=
  (
   Close@s;
   Remove[s];
   EndOfFile
   );
JSONStream /: Read[JSONStream[s_Symbol], type___] :=

  JSONStreamRead[JSONStream[s], type];
JSONStream /: Close[JSONStream[s_Symbol]] :=

  JSONStreamClose[JSONStream[s]];
Format[JSONStream[
   s_Symbol?(MatchQ[#["Data"]["Stream"], _InputStream] &)]] :=

 With[{is = s["Data"]["Stream"]},
  RawBoxes@
   BoxForm`ArrangeSummaryBox[
    "JSONStream",
    JSONStream[s],
    BoxForm`GenericIcon[InputStream],
    {
     BoxForm`SummaryItem[{"Name: ", 
       Replace[is[[1]], f_String :> FileNameTake@f]}],
     BoxForm`SummaryItem[{"Unique ID: ", is[[2]]}]
     },
    {
     BoxForm`SummaryItem[{"Open: ",
        Dynamic[Options[is] =!= {},
        UpdateInterval -> 1
        ]
       }]
     },
    StandardForm
    ]
  ]

Finally generate a JSON sample and we can start reading tokens:

$jsSample =
  "\n" <>
   ExportString[
    Prepend[ExampleData[{"Dataset", "Planets"}],
     "\"EscapedName\"" -> <|"asd" -> "whee", "number" -> 10|>
     ],
    "JSON"
    ];

json = JSONStream[$jsSample]

json example

Then here's what Read looks like on it:

Read@json

{Null, {Opening, Association}}

Table[Read@json, 10]

Table[Read@json, 10]

{{{"\"EscapedName\"", String}, None}, {Null, 
  Key}, {Null, {Opening, Association}}, {{"asd", String}, 
  None}, {Null, Key}, {{"whee", String}, None}, {{Null, Expression}, 
  Value}, {{"number", String}, None}, {Null, Key}, {{10, Expression}, 
  Value}}

Here's using the data type support:

Table[Read[json, KeyValuePattern], 3] // AbsoluteTiming

{0.015792, {"Mercury" -> <|"Mass" -> "330104000000000000000000. kg", 
    "Radius" -> "2439.7 km", "Moons" -> <||>|>, 
  "Venus" -> <|"Mass" -> "4867320000000000000000000. kg", 
    "Radius" -> "6051.9 km", "Moons" -> <||>|>, 
  "Earth" -> <|"Mass" -> "5972198600000000000000000. kg", 
    "Radius" -> "6367.44466 km", 
    "Moons" -> <|"Moon" -> <|"Mass" -> "73459000000000000000000. kg", 
        "Radius" -> "1737.5 km"|>|>|>}}

Currently we have Key, Value, KeyValuePattern, Association, List, and "Token" as supported types

I think this would qualify as a proof-of-concept

Here's a package form of it: JSONStream

$\endgroup$
  • $\begingroup$ So can you build an importer based on this which would take json file and extract specific value without reading everything into memory? $\endgroup$ – Kuba Oct 20 '17 at 11:18
  • $\begingroup$ @Kuba I think it could be configured to do so, although as I noted it’s incomplete, so it’ll take a bit more work before it’s truly done. A major caveat is that it’s only working token-by-token, so if you want to extract individual values rather than going through iteratively, I’ll need to write a function to skip to before the desired token before we start iteratively reading. $\endgroup$ – b3m2a1 Oct 20 '17 at 14:22
  • $\begingroup$ This of course does more than I had motivation to do but I am afraid this does not address any of problems I outlined. It does not seem too handle tokens escaped in string and if you add skip method and interatively parse characters it will become slow. I hope I'm wrong but that is why I didn't proceed with code as I was anticipating a dead end. $\endgroup$ – Kuba Oct 20 '17 at 16:48
  • $\begingroup$ Not handling escapes was just a minor bug (it was written to do so). That I can patch quickly. Getting better event handling (e.g. Key with associated key value) is a bit tougher, but it could be implemented pretty naturally out this, given the OO way the stream data is handled. The hard part, I think, will be finding the appropriate stream position for a given chunk of data, but I think I can manage that. $\endgroup$ – b3m2a1 Oct 20 '17 at 17:36
  • $\begingroup$ @Kuba I still don't have jump-to-value, but I do have better type support now. $\endgroup$ – b3m2a1 Oct 20 '17 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.