[Qemu-devel] [PATCH v2 0/3] json lexer tests and removal of lookahead

[Qemu-devel] [PATCH v2 0/3] json lexer tests and removal of lookahead

[Paolo Bonzini]

This is the same as the patches I sent last Friday, but split better
and without the extraneous change to the seabios submodule.

v1->v2: rearranged patches more coherently

Paolo Bonzini (3):
  add some tests for invalid JSON
  implement optional lookahead in json lexer
  remove unnecessary lookaheads

 check-qjson.c |   98 ++++++++++++++++++++++++++++++++++++++++++++++++++++-
 json-lexer.c  |  106 +++++++++++++++++++++++++++-----------------------------
 2 files changed, 148 insertions(+), 56 deletions(-)

[Qemu-devel] [PATCH v2 1/3] add some tests for invalid JSON

[Paolo Bonzini]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 check-qjson.c |   98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 97 insertions(+), 1 deletions(-)

diff --git a/check-qjson.c b/check-qjson.c
index 109e777..a04e334 100644
--- a/check-qjson.c
+++ b/check-qjson.c
@@ -628,11 +628,90 @@ START_TEST(simple_varargs)
 }
 END_TEST
 
+START_TEST(empty_input)
+{
+    QObject *obj = qobject_from_json("");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_string)
+{
+    QObject *obj = qobject_from_json("\"abc");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_sq_string)
+{
+    QObject *obj = qobject_from_json("'abc");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_escape)
+{
+    QObject *obj = qobject_from_json("\"abc\\\"");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_array)
+{
+    QObject *obj = qobject_from_json("[32");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_array_comma)
+{
+    QObject *obj = qobject_from_json("[32,");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(invalid_array_comma)
+{
+    QObject *obj = qobject_from_json("[32,}");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_dict)
+{
+    QObject *obj = qobject_from_json("{'abc':32");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_dict_comma)
+{
+    QObject *obj = qobject_from_json("{'abc':32,");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+#if 0
+START_TEST(invalid_dict_comma)
+{
+    QObject *obj = qobject_from_json("{'abc':32,}");
+    fail_unless(obj == NULL);
+}
+END_TEST
+
+START_TEST(unterminated_literal)
+{
+    QObject *obj = qobject_from_json("nul");
+    fail_unless(obj == NULL);
+}
+END_TEST
+#endif
+
 static Suite *qjson_suite(void)
 {
     Suite *suite;
     TCase *string_literals, *number_literals, *keyword_literals;
-    TCase *dicts, *lists, *whitespace, *varargs;
+    TCase *dicts, *lists, *whitespace, *varargs, *errors;
 
     string_literals = tcase_create("String Literals");
     tcase_add_test(string_literals, simple_string);
@@ -658,6 +737,22 @@ static Suite *qjson_suite(void)
     varargs = tcase_create("Varargs");
     tcase_add_test(varargs, simple_varargs);
 
+    errors = tcase_create("Invalid JSON");
+    tcase_add_test(errors, empty_input);
+    tcase_add_test(errors, unterminated_string);
+    tcase_add_test(errors, unterminated_escape);
+    tcase_add_test(errors, unterminated_sq_string);
+    tcase_add_test(errors, unterminated_array);
+    tcase_add_test(errors, unterminated_array_comma);
+    tcase_add_test(errors, invalid_array_comma);
+    tcase_add_test(errors, unterminated_dict);
+    tcase_add_test(errors, unterminated_dict_comma);
+#if 0
+    /* FIXME: this print parse error messages on stderr.  */
+    tcase_add_test(errors, invalid_dict_comma);
+    tcase_add_test(errors, unterminated_literal);
+#endif
+
     suite = suite_create("QJSON test-suite");
     suite_add_tcase(suite, string_literals);
     suite_add_tcase(suite, number_literals);
@@ -666,6 +761,7 @@ static Suite *qjson_suite(void)
     suite_add_tcase(suite, lists);
     suite_add_tcase(suite, whitespace);
     suite_add_tcase(suite, varargs);
+    suite_add_tcase(suite, errors);
 
     return suite;
 }
-- 
1.6.6.1

Re: [Qemu-devel] [PATCH v2 1/3] add some tests for invalid JSON

[Anthony Liguori]

On 05/24/2010 02:39 AM, Paolo Bonzini wrote:
> Signed-off-by: Paolo Bonzini<pbonzini@redhat.com>
>    

I think this series conflicts a bit with Luiz's series which I just 
pushed.  Could you rebase against the latest?

Regards,

Anthony Liguori

> ---
>   check-qjson.c |   98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
>   1 files changed, 97 insertions(+), 1 deletions(-)
>
> diff --git a/check-qjson.c b/check-qjson.c
> index 109e777..a04e334 100644
> --- a/check-qjson.c
> +++ b/check-qjson.c
> @@ -628,11 +628,90 @@ START_TEST(simple_varargs)
>   }
>   END_TEST
>
> +START_TEST(empty_input)
> +{
> +    QObject *obj = qobject_from_json("");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_string)
> +{
> +    QObject *obj = qobject_from_json("\"abc");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_sq_string)
> +{
> +    QObject *obj = qobject_from_json("'abc");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_escape)
> +{
> +    QObject *obj = qobject_from_json("\"abc\\\"");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_array)
> +{
> +    QObject *obj = qobject_from_json("[32");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_array_comma)
> +{
> +    QObject *obj = qobject_from_json("[32,");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(invalid_array_comma)
> +{
> +    QObject *obj = qobject_from_json("[32,}");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_dict)
> +{
> +    QObject *obj = qobject_from_json("{'abc':32");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_dict_comma)
> +{
> +    QObject *obj = qobject_from_json("{'abc':32,");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +#if 0
> +START_TEST(invalid_dict_comma)
> +{
> +    QObject *obj = qobject_from_json("{'abc':32,}");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +
> +START_TEST(unterminated_literal)
> +{
> +    QObject *obj = qobject_from_json("nul");
> +    fail_unless(obj == NULL);
> +}
> +END_TEST
> +#endif
> +
>   static Suite *qjson_suite(void)
>   {
>       Suite *suite;
>       TCase *string_literals, *number_literals, *keyword_literals;
> -    TCase *dicts, *lists, *whitespace, *varargs;
> +    TCase *dicts, *lists, *whitespace, *varargs, *errors;
>
>       string_literals = tcase_create("String Literals");
>       tcase_add_test(string_literals, simple_string);
> @@ -658,6 +737,22 @@ static Suite *qjson_suite(void)
>       varargs = tcase_create("Varargs");
>       tcase_add_test(varargs, simple_varargs);
>
> +    errors = tcase_create("Invalid JSON");
> +    tcase_add_test(errors, empty_input);
> +    tcase_add_test(errors, unterminated_string);
> +    tcase_add_test(errors, unterminated_escape);
> +    tcase_add_test(errors, unterminated_sq_string);
> +    tcase_add_test(errors, unterminated_array);
> +    tcase_add_test(errors, unterminated_array_comma);
> +    tcase_add_test(errors, invalid_array_comma);
> +    tcase_add_test(errors, unterminated_dict);
> +    tcase_add_test(errors, unterminated_dict_comma);
> +#if 0
> +    /* FIXME: this print parse error messages on stderr.  */
> +    tcase_add_test(errors, invalid_dict_comma);
> +    tcase_add_test(errors, unterminated_literal);
> +#endif
> +
>       suite = suite_create("QJSON test-suite");
>       suite_add_tcase(suite, string_literals);
>       suite_add_tcase(suite, number_literals);
> @@ -666,6 +761,7 @@ static Suite *qjson_suite(void)
>       suite_add_tcase(suite, lists);
>       suite_add_tcase(suite, whitespace);
>       suite_add_tcase(suite, varargs);
> +    suite_add_tcase(suite, errors);
>
>       return suite;
>   }
>    

Re: [Qemu-devel] [PATCH v2 1/3] add some tests for invalid JSON

[Paolo Bonzini]

On 05/24/2010 10:17 PM, Anthony Liguori wrote:
> On 05/24/2010 02:39 AM, Paolo Bonzini wrote:
>> Signed-off-by: Paolo Bonzini<pbonzini@redhat.com>
>
> I think this series conflicts a bit with Luiz's series which I just
> pushed. Could you rebase against the latest?

You didn't apply this one yet, at least I don't see it on qemu.git

commit e546343ee0f3f904529d32c1a9a60f5baa181852
Author: Luiz Capitulino <lcapitulino@redhat.com>
Date:   Wed May 19 18:15:32 2010 -0300

     json-lexer: Drop 'buf'

     QString supports adding a single char, 'buf' is unneeded.

     Signed-off-by: Luiz Capitulino <lcapitulino@redhat.com>

I based my series on top of Luiz's, so it should apply.  The above is 
the only commit that is actually required.  I can ping the series once 
Luiz's patches are applied, so you can disregard it in the meanwhile.

Paolo

Re: [Qemu-devel] [PATCH v2 1/3] add some tests for invalid JSON

[Anthony Liguori]

On 05/25/2010 02:28 AM, Paolo Bonzini wrote:
> On 05/24/2010 10:17 PM, Anthony Liguori wrote:
>> On 05/24/2010 02:39 AM, Paolo Bonzini wrote:
>>> Signed-off-by: Paolo Bonzini<pbonzini@redhat.com>
>>
>> I think this series conflicts a bit with Luiz's series which I just
>> pushed. Could you rebase against the latest?
>
> You didn't apply this one yet, at least I don't see it on qemu.git
>
> commit e546343ee0f3f904529d32c1a9a60f5baa181852
> Author: Luiz Capitulino <lcapitulino@redhat.com>
> Date:   Wed May 19 18:15:32 2010 -0300
>
>     json-lexer: Drop 'buf'
>
>     QString supports adding a single char, 'buf' is unneeded.
>
>     Signed-off-by: Luiz Capitulino <lcapitulino@redhat.com>
>
> I based my series on top of Luiz's, so it should apply.

Yeah, I confused myself into thinking that Luiz's series was more 
contentious than it is.  Nevermind, your patches are fine on top of his.

Regards,

Anthony Liguori

> The above is the only commit that is actually required.  I can ping 
> the series once Luiz's patches are applied, so you can disregard it in 
> the meanwhile.
>
> Paolo

[Qemu-devel] [PATCH v2 2/3] implement optional lookahead in json lexer

[Paolo Bonzini]

Not requiring one extra character when lookahead is not necessary
ensures that clients behave properly even if they, for example,
send QMP requests without a trailing newline.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 json-lexer.c |   58 +++++++++++++++++++++++++++++++++++-----------------------
 1 files changed, 35 insertions(+), 23 deletions(-)

diff --git a/json-lexer.c b/json-lexer.c
index d1d8033..41b37f4 100644
--- a/json-lexer.c
+++ b/json-lexer.c
@@ -65,6 +65,12 @@ enum json_lexer_state {
 
 #define TERMINAL(state) [0 ... 0x7F] = (state)
 
+/* Return whether TERMINAL is a terminal state and the transition to it
+   from OLD_STATE required lookahead.  This happens whenever the table
+   below uses the TERMINAL macro.  */
+#define TERMINAL_NEEDED_LOOKAHEAD(old_state, terminal) \
+            (json_lexer[(old_state)][0] == (terminal))
+
 static const uint8_t json_lexer[][256] =  {
     [IN_DONE_STRING] = {
         TERMINAL(JSON_STRING),
@@ -279,35 +285,41 @@ void json_lexer_init(JSONLexer *lexer, JSONLexerEmitter func)
 
 static int json_lexer_feed_char(JSONLexer *lexer, char ch)
 {
+    int char_consumed, new_state;
+
     lexer->x++;
     if (ch == '\n') {
         lexer->x = 0;
         lexer->y++;
     }
 
-    lexer->state = json_lexer[lexer->state][(uint8_t)ch];
-
-    switch (lexer->state) {
-    case JSON_OPERATOR:
-    case JSON_ESCAPE:
-    case JSON_INTEGER:
-    case JSON_FLOAT:
-    case JSON_KEYWORD:
-    case JSON_STRING:
-        lexer->emit(lexer, lexer->token, lexer->state, lexer->x, lexer->y);
-    case JSON_SKIP:
-        lexer->state = json_lexer[IN_START][(uint8_t)ch];
-        QDECREF(lexer->token);
-        lexer->token = qstring_new();
-        break;
-    case ERROR:
-        return -EINVAL;
-    default:
-        break;
-    }
-
-    qstring_append_chr(lexer->token, ch);
+    do {
+        new_state = json_lexer[lexer->state][(uint8_t)ch];
+        char_consumed = !TERMINAL_NEEDED_LOOKAHEAD(lexer->state, new_state);
+        if (char_consumed) {
+            qstring_append_chr(lexer->token, ch);
+        }
 
+        switch (new_state) {
+        case JSON_OPERATOR:
+        case JSON_ESCAPE:
+        case JSON_INTEGER:
+        case JSON_FLOAT:
+        case JSON_KEYWORD:
+        case JSON_STRING:
+            lexer->emit(lexer, lexer->token, new_state, lexer->x, lexer->y);
+        case JSON_SKIP:
+            QDECREF(lexer->token);
+            lexer->token = qstring_new();
+            new_state = IN_START;
+            break;
+        case ERROR:
+            return -EINVAL;
+        default:
+            break;
+        }
+        lexer->state = new_state;
+    } while (!char_consumed);
     return 0;
 }
 
@@ -329,7 +341,7 @@ int json_lexer_feed(JSONLexer *lexer, const char *buffer, size_t size)
 
 int json_lexer_flush(JSONLexer *lexer)
 {
-    return json_lexer_feed_char(lexer, 0);
+    return lexer->state == IN_START ? 0 : json_lexer_feed_char(lexer, 0);
 }
 
 void json_lexer_destroy(JSONLexer *lexer)
-- 
1.6.6.1

[Qemu-devel] [PATCH v2 3/3] remove unnecessary lookaheads

[Paolo Bonzini]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 json-lexer.c |   48 ++++++++++++++++--------------------------------
 1 files changed, 16 insertions(+), 32 deletions(-)

diff --git a/json-lexer.c b/json-lexer.c
index 41b37f4..ec96fb4 100644
--- a/json-lexer.c
+++ b/json-lexer.c
@@ -29,7 +29,6 @@
 
 enum json_lexer_state {
     ERROR = 0,
-    IN_DONE_STRING,
     IN_DQ_UCODE3,
     IN_DQ_UCODE2,
     IN_DQ_UCODE1,
@@ -57,9 +56,7 @@ enum json_lexer_state {
     IN_ESCAPE_I,
     IN_ESCAPE_I6,
     IN_ESCAPE_I64,
-    IN_ESCAPE_DONE,
     IN_WHITESPACE,
-    IN_OPERATOR_DONE,
     IN_START,
 };
 
@@ -72,10 +69,6 @@ enum json_lexer_state {
             (json_lexer[(old_state)][0] == (terminal))
 
 static const uint8_t json_lexer[][256] =  {
-    [IN_DONE_STRING] = {
-        TERMINAL(JSON_STRING),
-    },
-
     /* double quote string */
     [IN_DQ_UCODE3] = {
         ['0' ... '9'] = IN_DQ_STRING,
@@ -110,7 +103,7 @@ static const uint8_t json_lexer[][256] =  {
     [IN_DQ_STRING] = {
         [1 ... 0xFF] = IN_DQ_STRING,
         ['\\'] = IN_DQ_STRING_ESCAPE,
-        ['"'] = IN_DONE_STRING,
+        ['"'] = JSON_STRING,
     },
 
     /* single quote string */
@@ -147,7 +140,7 @@ static const uint8_t json_lexer[][256] =  {
     [IN_SQ_STRING] = {
         [1 ... 0xFF] = IN_SQ_STRING,
         ['\\'] = IN_SQ_STRING_ESCAPE,
-        ['\''] = IN_DONE_STRING,
+        ['\''] = JSON_STRING,
     },
 
     /* Zero */
@@ -213,27 +206,18 @@ static const uint8_t json_lexer[][256] =  {
         ['\n'] = IN_WHITESPACE,
     },        
 
-    /* operator */
-    [IN_OPERATOR_DONE] = {
-        TERMINAL(JSON_OPERATOR),
-    },
-
     /* escape */
-    [IN_ESCAPE_DONE] = {
-        TERMINAL(JSON_ESCAPE),
-    },
-
     [IN_ESCAPE_LL] = {
-        ['d'] = IN_ESCAPE_DONE,
+        ['d'] = JSON_ESCAPE,
     },
 
     [IN_ESCAPE_L] = {
-        ['d'] = IN_ESCAPE_DONE,
+        ['d'] = JSON_ESCAPE,
         ['l'] = IN_ESCAPE_LL,
     },
 
     [IN_ESCAPE_I64] = {
-        ['d'] = IN_ESCAPE_DONE,
+        ['d'] = JSON_ESCAPE,
     },
 
     [IN_ESCAPE_I6] = {
@@ -245,11 +229,11 @@ static const uint8_t json_lexer[][256] =  {
     },
 
     [IN_ESCAPE] = {
-        ['d'] = IN_ESCAPE_DONE,
-        ['i'] = IN_ESCAPE_DONE,
-        ['p'] = IN_ESCAPE_DONE,
-        ['s'] = IN_ESCAPE_DONE,
-        ['f'] = IN_ESCAPE_DONE,
+        ['d'] = JSON_ESCAPE,
+        ['i'] = JSON_ESCAPE,
+        ['p'] = JSON_ESCAPE,
+        ['s'] = JSON_ESCAPE,
+        ['f'] = JSON_ESCAPE,
         ['l'] = IN_ESCAPE_L,
         ['I'] = IN_ESCAPE_I,
     },
@@ -261,12 +245,12 @@ static const uint8_t json_lexer[][256] =  {
         ['0'] = IN_ZERO,
         ['1' ... '9'] = IN_NONZERO_NUMBER,
         ['-'] = IN_NEG_NONZERO_NUMBER,
-        ['{'] = IN_OPERATOR_DONE,
-        ['}'] = IN_OPERATOR_DONE,
-        ['['] = IN_OPERATOR_DONE,
-        [']'] = IN_OPERATOR_DONE,
-        [','] = IN_OPERATOR_DONE,
-        [':'] = IN_OPERATOR_DONE,
+        ['{'] = JSON_OPERATOR,
+        ['}'] = JSON_OPERATOR,
+        ['['] = JSON_OPERATOR,
+        [']'] = JSON_OPERATOR,
+        [','] = JSON_OPERATOR,
+        [':'] = JSON_OPERATOR,
         ['a' ... 'z'] = IN_KEYWORD,
         ['%'] = IN_ESCAPE,
         [' '] = IN_WHITESPACE,
-- 
1.6.6.1