Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3311ea8

Browse files
committed
Introduce a non-recursive JSON parser
This parser uses an explicit prediction stack, unlike the presentrecursive descent parser where the parser state is represented on thecall stack. This difference makes the new parser suitable for use inincremental parsing of huge JSON documents that cannot be convenientlyhandled piece-wise by the recursive descent parser. One potential usefor this will be in parsing large backup manifests associated withincremental backups.Because this parser is somewhat slower than the recursive descentparser, it is not replacing that parser, but is an additional parseravailable to callers.For testing purposes, if the build is done with -DFORCE_JSON_PSTACK, allJSON parsing is done with the non-recursive parser, in which case onlytrivial regression differences in error messages should be observed.Author: Andrew DunstanReviewed-By: Jacob ChampionDiscussion:https://postgr.es/m/7b0a51d6-0d9d-7366-3a1a-f74397a02f55@dunslane.net
1 parent585df02 commit3311ea8

File tree

16 files changed

+21563
-9
lines changed

16 files changed

+21563
-9
lines changed

‎src/common/jsonapi.c

Lines changed: 945 additions & 9 deletions
Large diffs are not rendered by default.

‎src/include/common/jsonapi.h

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,9 @@ typedef enum JsonTokenType
3636
typedefenumJsonParseErrorType
3737
{
3838
JSON_SUCCESS,
39+
JSON_INCOMPLETE,
40+
JSON_INVALID_LEXER_TYPE,
41+
JSON_NESTING_TOO_DEEP,
3942
JSON_ESCAPING_INVALID,
4043
JSON_ESCAPING_REQUIRED,
4144
JSON_EXPECTED_ARRAY_FIRST,
@@ -57,6 +60,9 @@ typedef enum JsonParseErrorType
5760
JSON_SEM_ACTION_FAILED,/* error should already be reported */
5861
}JsonParseErrorType;
5962

63+
/* Parser state private to jsonapi.c */
64+
typedefstructJsonParserStackJsonParserStack;
65+
typedefstructJsonIncrementalStateJsonIncrementalState;
6066

6167
/*
6268
* All the fields in this structure should be treated as read-only.
@@ -71,6 +77,11 @@ typedef enum JsonParseErrorType
7177
* AFTER the end of the token, i.e. where there would be a nul byte
7278
* if we were using nul-terminated strings.
7379
*
80+
* The prev_token_terminator field should not be used when incremental is
81+
* true, as the previous token might have started in a previous piece of input,
82+
* and thus it can't be used in any pointer arithmetic or other operations in
83+
* conjunction with token_start.
84+
*
7485
* JSONLEX_FREE_STRUCT/STRVAL are used to drive freeJsonLexContext.
7586
*/
7687
#defineJSONLEX_FREE_STRUCT(1 << 0)
@@ -83,11 +94,14 @@ typedef struct JsonLexContext
8394
char*token_start;
8495
char*token_terminator;
8596
char*prev_token_terminator;
97+
boolincremental;
8698
JsonTokenTypetoken_type;
8799
intlex_level;
88100
bits32flags;
89101
intline_number;/* line number, starting from 1 */
90102
char*line_start;/* where that line starts within input */
103+
JsonParserStack*pstack;
104+
JsonIncrementalState*inc_state;
91105
StringInfostrval;
92106
StringInfoerrormsg;
93107
}JsonLexContext;
@@ -141,6 +155,12 @@ typedef struct JsonSemAction
141155
externJsonParseErrorTypepg_parse_json(JsonLexContext*lex,
142156
JsonSemAction*sem);
143157

158+
externJsonParseErrorTypepg_parse_json_incremental(JsonLexContext*lex,
159+
JsonSemAction*sem,
160+
char*json,
161+
intlen,
162+
boolis_last);
163+
144164
/* the null action object used for pure validation */
145165
externPGDLLIMPORTJsonSemActionnullSemAction;
146166

@@ -176,6 +196,16 @@ extern JsonLexContext *makeJsonLexContextCstringLen(JsonLexContext *lex,
176196
intlen,
177197
intencoding,
178198
boolneed_escapes);
199+
200+
/*
201+
* make a JsonLexContext suitable for incremental parsing.
202+
* the string chunks will be handed to pg_parse_json_incremental,
203+
* so there's no need for them here.
204+
*/
205+
externJsonLexContext*makeJsonLexContextIncremental(JsonLexContext*lex,
206+
intencoding,
207+
boolneed_escapes);
208+
179209
externvoidfreeJsonLexContext(JsonLexContext*lex);
180210

181211
/* lex one token */

‎src/include/pg_config_manual.h

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -240,6 +240,13 @@
240240
*------------------------------------------------------------------------
241241
*/
242242

243+
/*
244+
* Force use of the non-recursive JSON parser in all cases. This is useful
245+
* to validate the working of the parser, and the regression tests should
246+
* pass except for some different error messages about the stack limit.
247+
*/
248+
/* #define FORCE_JSON_PSTACK */
249+
243250
/*
244251
* Include Valgrind "client requests", mostly in the memory allocator, so
245252
* Valgrind understands PostgreSQL memory contexts. This permits detecting

‎src/test/modules/Makefile

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ SUBDIRS = \
2222
test_extensions\
2323
test_ginpostinglist\
2424
test_integerset\
25+
test_json_parser\
2526
test_lfind\
2627
test_misc\
2728
test_oat_hooks\

‎src/test/modules/meson.build

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ subdir('test_dsm_registry')
2121
subdir('test_extensions')
2222
subdir('test_ginpostinglist')
2323
subdir('test_integerset')
24+
subdir('test_json_parser')
2425
subdir('test_lfind')
2526
subdir('test_misc')
2627
subdir('test_oat_hooks')
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
2+
PGFILEDESC = "standalone json parser tester"
3+
PGAPPICON = win32
4+
5+
TAP_TESTS = 1
6+
7+
OBJS = test_json_parser_incremental.o test_json_parser_perf.o
8+
9+
ifdefUSE_PGXS
10+
PG_CONFIG = pg_config
11+
PGXS :=$(shell$(PG_CONFIG) --pgxs)
12+
include$(PGXS)
13+
else
14+
subdir = src/test/modules/test_json_parser
15+
top_builddir = ../../../..
16+
include$(top_builddir)/src/Makefile.global
17+
include$(top_srcdir)/contrib/contrib-global.mk
18+
endif
19+
20+
all: test_json_parser_incremental$(X) test_json_parser_perf$(X)
21+
22+
%.o:$(top_srcdir)/$(subdir)/%.c
23+
24+
PARSER_LIBS =$(top_builddir)/src/common/libpgcommon.a$(top_builddir)/src/port/libpgport.a
25+
26+
test_json_parser_incremental$(X): test_json_parser_incremental.o$(PARSER_LIBS)
27+
$(CC)$(CFLAGS)$^ -o$@
28+
29+
test_json_parser_perf$(X): test_json_parser_perf.o$(PARSER_LIBS)
30+
$(CC)$(CFLAGS)$^ -o$@
31+
32+
speed-check: test_json_parser_perf$(X)
33+
@echo Standard parser:
34+
time ./test_json_parser_perf 10000$(top_srcdir)/$(subdir)/tiny.json
35+
@echo Incremental parser:
36+
time ./test_json_parser_perf -i 10000$(top_srcdir)/$(subdir)/tiny.json
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
Module `test_json_parser`
2+
=========================
3+
4+
This module contains two programs for testing the json parsers.
5+
6+
- `test_json_parser_incremental` is for testing the incremental parser, It
7+
reads in a file and pases it in very small chunks (60 bytes at a time) to
8+
the incremental parser. It's not meant to be a speed test but to test the
9+
accuracy of the incremental parser. It takes one argument: the name of the
10+
input file.
11+
- `test_json_parser_perf` is for speed testing both the standard
12+
recursive descent parser and the non-recursive incremental
13+
parser. If given the `-i` flag it uses the non-recursive parser,
14+
otherwise the stardard parser. The remaining flags are the number of
15+
parsing iterations and the file containing the input. Even when
16+
using the non-recursive parser, the input is passed to the parser in a
17+
single chunk. The results are thus comparable to those of the
18+
standard parser.
19+
20+
The easiest way to use these is to run `make check` and `make speed-check`
21+
22+
The sample input file is a small extract from a list of `delicious`
23+
bookmarks taken some years ago, all wrapped in a single json
24+
array. 10,000 iterations of parsing this file gives a reasonable
25+
benchmark, and that is what the `speed-check` target does.
Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
# Copyright (c) 2024, PostgreSQL Global Development Group
2+
3+
test_json_parser_incremental_sources=files(
4+
'test_json_parser_incremental.c',
5+
)
6+
7+
if host_system=='windows'
8+
test_json_parser_incremental_sources+= rc_bin_gen.process(win32ver_rc,extra_args: [
9+
'--NAME','test_json_parser_incremental',
10+
'--FILEDESC','standalone json parser tester',
11+
])
12+
endif
13+
14+
test_json_parser_incremental=executable('test_json_parser_incremental',
15+
test_json_parser_incremental_sources,
16+
dependencies: [frontend_code],
17+
kwargs: default_bin_args+ {
18+
'install':false,
19+
},
20+
)
21+
22+
test_json_parser_perf_sources=files(
23+
'test_json_parser_perf.c',
24+
)
25+
26+
if host_system=='windows'
27+
test_json_parser_perf_sources+= rc_bin_gen.process(win32ver_rc,extra_args: [
28+
'--NAME','test_json_parser_perf',
29+
'--FILEDESC','standalone json parser tester',
30+
])
31+
endif
32+
33+
test_json_parser_perf=executable('test_json_parser_perf',
34+
test_json_parser_perf_sources,
35+
dependencies: [frontend_code],
36+
kwargs: default_bin_args+ {
37+
'install':false,
38+
},
39+
)
40+
41+
tests+= {
42+
'name':'test_json_parser',
43+
'sd':meson.current_source_dir(),
44+
'bd':meson.current_build_dir(),
45+
'tap': {
46+
'tests': [
47+
't/001_test_json_parser_incremental.pl',
48+
't/002_inline.pl',
49+
't/003_test_semantic.pl'
50+
],
51+
},
52+
}
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
2+
use strict;
3+
use warnings;
4+
5+
use PostgreSQL::Test::Utils;
6+
use Test::More;
7+
use FindBin;
8+
9+
use File::Tempqw(tempfile);
10+
11+
my$test_file ="$FindBin::RealBin/../tiny.json";
12+
13+
my$exe ="test_json_parser_incremental";
14+
15+
for (my$size = 64;$size > 0;$size--)
16+
{
17+
my ($stdout,$stderr) = run_command( [$exe,"-c",$size,$test_file] );
18+
19+
like($stdout,qr/SUCCESS/,"chunk size$size: test succeeds");
20+
is($stderr,"","chunk size$size: no error output");
21+
}
22+
23+
done_testing();
Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
use strict;
2+
use warnings;
3+
4+
use PostgreSQL::Test::Utils;
5+
use Test::More;
6+
7+
use File::Tempqw(tempfile);
8+
9+
subtest
10+
{
11+
local$Test::Builder::Level =$Test::Builder::Level + 1;
12+
13+
my ($name,$json,%params) =@_;
14+
my$exe ="test_json_parser_incremental";
15+
my$chunk =length($json);
16+
17+
if ($chunk > 64)
18+
{
19+
$chunk = 64;
20+
}
21+
22+
my ($fh,$fname) = tempfile(UNLINK=> 1);
23+
print$fh"$json";
24+
close($fh);
25+
26+
foreachmy$size (reverse(1..$chunk))
27+
{
28+
my ($stdout,$stderr) = run_command( [$exe,"-c",$size,$fname] );
29+
30+
if (defined($params{error}))
31+
{
32+
unlike($stdout,qr/SUCCESS/,"$name, chunk size$size: test fails");
33+
like($stderr,$params{error},"$name, chunk size$size: correct error output");
34+
}
35+
else
36+
{
37+
like($stdout,qr/SUCCESS/,"$name, chunk size$size: test succeeds");
38+
is($stderr,"","$name, chunk size$size: no error output");
39+
}
40+
}
41+
}
42+
43+
test("number","12345");
44+
test("string",'"hello"');
45+
test("false","false");
46+
test("true","true");
47+
test("null","null");
48+
test("empty object","{}");
49+
test("empty array","[]");
50+
test("array with number","[12345]");
51+
test("array with numbers","[12345,67890]");
52+
test("array with null","[null]");
53+
test("array with string",'["hello"]');
54+
test("array with boolean",'[false]');
55+
test("single pair",'{"key": "value"}');
56+
test("heavily nested array","["x3200 ."]"x3200);
57+
test("serial escapes",'"\\\\\\\\\\\\\\\\"');
58+
test("interrupted escapes",'"\\\\\\"\\\\\\\\\\"\\\\"');
59+
test("whitespace",' ""');
60+
61+
test("unclosed empty object","{",error=>qr/input string ended unexpectedly/);
62+
test("bad key","{{",error=>qr/Expected string or "}", but found "\{"/);
63+
test("bad key","{{}",error=>qr/Expected string or "}", but found "\{"/);
64+
test("numeric key","{1234: 2}",error=>qr/Expected string or "}", but found "1234"/);
65+
test("second numeric key",'{"a": "a", 1234: 2}',error=>qr/Expected string, but found "1234"/);
66+
test("unclosed object with pair",'{"key": "value"',error=>qr/input string ended unexpectedly/);
67+
test("missing key value",'{"key": }',error=>qr/Expected JSON value, but found "}"/);
68+
test("missing colon",'{"key" 12345}',error=>qr/Expected ":", but found "12345"/);
69+
test("missing comma",'{"key": 12345 12345}',error=>qr/Expected "," or "}", but found "12345"/);
70+
test("overnested array","["x6401,error=>qr/maximum permitted depth is 6400/);
71+
test("overclosed array","[]]",error=>qr/Expected end of input, but found "]"/);
72+
test("unexpected token in array","[ }}} ]",error=>qr/Expected array element or "]", but found "}"/);
73+
test("junk punctuation","[ ||| ]",error=>qr/Token "|" is invalid/);
74+
test("missing comma in array","[123 123]",error=>qr/Expected "," or "]", but found "123"/);
75+
test("misspelled boolean","tru",error=>qr/Token "tru" is invalid/);
76+
test("misspelled boolean in array","[tru]",error=>qr/Token "tru" is invalid/);
77+
test("smashed top-level scalar","12zz",error=>qr/Token "12zz" is invalid/);
78+
test("smashed scalar in array","[12zz]",error=>qr/Token "12zz" is invalid/);
79+
test("unknown escape sequence",'"hello\vworld"',error=>qr/Escape sequence "\\v" is invalid/);
80+
test("unescaped control","\"hello\tworld\"",error=>qr/Character with value 0x09 must be escaped/);
81+
test("incorrect escape count",'"\\\\\\\\\\\\\\"',error=>qr/Token ""\\\\\\\\\\\\\\"" is invalid/);
82+
83+
done_testing();
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
use strict;
2+
use warnings;
3+
4+
use PostgreSQL::Test::Utils;
5+
use Test::More;
6+
use FindBin;
7+
8+
use File::Tempqw(tempfile);
9+
10+
my$test_file ="$FindBin::RealBin/../tiny.json";
11+
my$test_out ="$FindBin::RealBin/../tiny.out";
12+
13+
my$exe ="test_json_parser_incremental";
14+
15+
my ($stdout,$stderr) = run_command( [$exe,"-s",$test_file] );
16+
17+
is($stderr,"","no error output");
18+
19+
my ($fh,$fname) = tempfile();
20+
21+
print$fh$stdout,"\n";
22+
23+
close($fh);
24+
25+
($stdout,$stderr) = run_command(["diff","-u",$fname,$test_out]);
26+
27+
is($stdout,"","no output diff");
28+
is($stderr,"","no diff error");
29+
30+
done_testing();
31+
32+
33+
34+
35+
36+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp