std.json: Add support for recursive objects to std.json.parse #9307

greenfork · 2021-07-05T13:14:29Z

Inferred errors don't work for recursive function calls, so we add an explicit error set.

parseInternal recurses in several places, current error catches this:

Line 1768 in b7da1b2

const v = try parseInternal(ptrInfo.child, tok, tokens, options);

daurnimator · 2021-07-05T13:16:25Z

lib/std/json.zig

+    UnexpectedToken,
+    UnexpectedValue,
+    UnknownField,
+} || SkipValueError || TokenStream.Error || error{OutOfMemory} || std.fmt.ParseIntError;


ParseInternalError intentionally doesn't have a specified error set, as different errors are only possible/reachable with certain types passed.
e.g. OutOfMemory cannot be hit when T isn't a pointer type.

If anything, you need a function ParseInternalError(comptime T: type); in future (once comptime field support improves) that may also need to take a options: ParseOptions.

Okay, I tried to do your suggested approach. Now I don't know how to avoid infinite recursion. In the test I wrote it goes like this:

Check union errors, e.g. check all union fields

i64 - no errors, next

Array - check child field type

Child field type is union, check all union fields

...

I can't check whether it is going to be a recursion because I need to retrieve a parent of my parent, the sequence is Union -> Array -> Union. And of course more complex scenarios are possible.

there lies the rub.

That's why the compiler couldn't figure it out either :P

The json parser accepting pointer types opens it up for infinite recursion; and currently this can lead to unbounded stack usage! Given the future goals of zig include limiting unbounded stack usage, perhaps the solution is to remove pointers to ~~complex objects from the accepted input of json.parse.~~

Edit: alternative idea: what if ParseOptions had a field blackListedTypes that would cause a @compileError; then when recursing, add the current type to the black listed types?

Sorry, I don't think I understand your suggestion. Do you suggest to raise a compile error whenever there's a recursive type definition we are trying to parse? This is the exact reason for this PR, I want to be able to parse into recursive definitions. Maybe I misunderstand something.

Also, can I do it like this? commit Don't analyze already inferred types

By the way, maybe I wasn't clear enough. By "infinite recursion" I meant that compiler produces an error that eval quota is overreached (@setEvalBranchQuota), it already saves from infinite recursion scenario.

daurnimator

Well done! looks like you found a way to make it work; no API objections from me now :)

Though I'm not sure about some of the style, or if the pattern of inferred_types will make the stage1 compiler cry.

Will leave it for others to review.

daurnimator · 2021-07-07T11:30:19Z

lib/std/json.zig

@@ -1530,7 +1532,81 @@ test "skipValue" {
    }
 }

-fn parseInternal(comptime T: type, token: Token, tokens: *TokenStream, options: ParseOptions) !T {
+fn ParseInternalError(comptime T: type, inferred_types: []const type) type {


I think inferred_types should be comptime?

Vexu

This could also be made public as ParseError so that users can get the error set without using @typeInfo.

Vexu · 2021-07-07T11:50:55Z

lib/std/json.zig

@@ -1530,7 +1532,81 @@ test "skipValue" {
    }
 }

-fn parseInternal(comptime T: type, token: Token, tokens: *TokenStream, options: ParseOptions) !T {
+fn ParseInternalError(comptime T: type, inferred_types: []const type) type {


Function call memoization should do the same as your inferred_types check (and perform better). Did you have some issues with it that led to this? If so it should be documented here.

See the above comment thread: something like this is required to not blow up on recursion.

If I understood correctly, then yes, recursion is the reason. I can provide a function with a single argument though if this is the desired signature by moving this code to ParseInternalErrorImpl and doing something like this:

fn ParseInternalError(comptime T: type) type { const parse_internal_inferred_types = [_]type{}; return ParseInternalErrorImpl(T, &parse_internal_inferred_types); }

Oh right, because the call hasn't completed yet, missed that.

That helper would work as the ParseError I mentioned in the other comment.

I'm not sure I completely understood your comment but implementation should be fine.

Vexu · 2021-07-07T11:52:40Z

lib/std/json.zig

+    token: Token,
+    tokens: *TokenStream,
+    options: ParseOptions,
+) ParseInternalError(T, std.mem.span(&parse_internal_inferred_types))!T {


span isn't doing anything here, &parse_internal_inferred_types should already coerce properly.

Vexu · 2021-07-07T11:53:47Z

lib/std/json.zig

@@ -2457,11 +2574,11 @@ pub fn unescapeValidString(output: []u8, input: []const u8) !void {
            } else |err| {
                // it might be a surrogate pair
                if (err != error.Utf8CannotEncodeSurrogateHalf) {
-                    return error.InvalidUnicodeHexSymbol;
+                    return UnescapeValidStringError.InvalidUnicodeHexSymbol;


Suggested change

return UnescapeValidStringError.InvalidUnicodeHexSymbol;

return error.InvalidUnicodeHexSymbol;

These are semantically equivalent and currently using the error.Foo syntax is preferred.

daurnimator reviewed Jul 5, 2021

View reviewed changes

daurnimator added the standard library This issue involves writing Zig code for the standard library. label Jul 5, 2021

greenfork force-pushed the support-json-recursive-objects branch from 2c4ea04 to da436f7 Compare July 5, 2021 15:35

daurnimator reviewed Jul 7, 2021

View reviewed changes

Vexu requested changes Jul 7, 2021

View reviewed changes

greenfork requested a review from Vexu July 8, 2021 05:26

Dmitry Matveyev added 9 commits July 25, 2021 11:34

Add support for recursive objects to std.json.parse

d0afa71

Remove previously defined error set

e9b4b27

Try with function which returns an error set

10fbcbb

Don't analyze already inferred types

9363fa4

Add comptime to inferred_type parameter

a1c2386

Make ParseInternalError to accept only a single argument

d290dd8

Add public ParseError for parse function

0162a5b

Use error.Foo syntax for errors instead of a named error set

2702862

Better formatting

59468d5

greenfork force-pushed the support-json-recursive-objects branch from a9e6f16 to 59468d5 Compare July 25, 2021 14:35

Update to latest code changes

b58e3bf

Vexu merged commit b2e970d into ziglang:master Aug 20, 2021

greenfork deleted the support-json-recursive-objects branch December 21, 2021 01:41

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

std.json: Add support for recursive objects to std.json.parse #9307

std.json: Add support for recursive objects to std.json.parse #9307

greenfork commented Jul 5, 2021 •

edited

daurnimator Jul 5, 2021 •

edited

greenfork Jul 5, 2021

daurnimator Jul 5, 2021 •

edited

greenfork Jul 5, 2021

greenfork Jul 5, 2021

daurnimator left a comment

daurnimator Jul 7, 2021

Vexu left a comment

Vexu Jul 7, 2021

daurnimator Jul 7, 2021

greenfork Jul 7, 2021

Vexu Jul 7, 2021

greenfork Jul 8, 2021

Vexu Jul 7, 2021

Vexu Jul 7, 2021

	return UnescapeValidStringError.InvalidUnicodeHexSymbol;
	return error.InvalidUnicodeHexSymbol;

std.json: Add support for recursive objects to std.json.parse #9307

std.json: Add support for recursive objects to std.json.parse #9307

Conversation

greenfork commented Jul 5, 2021 • edited

daurnimator Jul 5, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

daurnimator Jul 5, 2021 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

daurnimator left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Vexu left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

greenfork commented Jul 5, 2021 •

edited

daurnimator Jul 5, 2021 •

edited

daurnimator Jul 5, 2021 •

edited