Is building an event-based parser possible/reasonable in Mathematica (WL)?

Question

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

Answer 1

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]

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