diff mbox

[v3,for-2.5,09/12] qjson: Convert to parser to recursive descent

Message ID 1448486613-17634-10-git-send-email-armbru@redhat.com
State New
Headers show

Commit Message

Markus Armbruster Nov. 25, 2015, 9:23 p.m. UTC 
We backtrack in parse_value(), even though JSON is LL(1) and thus can
be parsed by straightforward recursive descent.  Do exactly that.

Based on an almost-correct patch from Paolo Bonzini.

Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
 qobject/json-parser.c | 165 ++++++++++++++------------------------------------
 1 file changed, 47 insertions(+), 118 deletions(-)

Comments

Eric Blake Nov. 25, 2015, 10:22 p.m. UTC | #1 
On 11/25/2015 02:23 PM, Markus Armbruster wrote:
> We backtrack in parse_value(), even though JSON is LL(1) and thus can
> be parsed by straightforward recursive descent.  Do exactly that.
> 
> Based on an almost-correct patch from Paolo Bonzini.
> 
> Signed-off-by: Markus Armbruster <armbru@redhat.com>
> ---
>  qobject/json-parser.c | 165 ++++++++++++++------------------------------------
>  1 file changed, 47 insertions(+), 118 deletions(-)
> 

>  static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
>  {
> -    QObject *obj;
> +    QObject *token;
>  
> -    obj = parse_object(ctxt, ap);
> -    if (obj == NULL) {
> -        obj = parse_array(ctxt, ap);
> -    }
> -    if (obj == NULL) {
> -        obj = parse_escape(ctxt, ap);
> -    }
> -    if (obj == NULL) {
> -        obj = parse_keyword(ctxt);
> -    } 
> -    if (obj == NULL) {
> -        obj = parse_literal(ctxt);
> +    token = parser_context_peek_token(ctxt);
> +    if (token == NULL) {
> +        parse_error(ctxt, NULL, "premature EOI");

Should we spell that out as 'end of input'?

But that's cosmetic, and doesn't affect correctness of the conversion.

Reviewed-by: Eric Blake <eblake@redhat.com>
Markus Armbruster Nov. 26, 2015, 8:37 a.m. UTC | #2 
Eric Blake <eblake@redhat.com> writes:

> On 11/25/2015 02:23 PM, Markus Armbruster wrote:
>> We backtrack in parse_value(), even though JSON is LL(1) and thus can
>> be parsed by straightforward recursive descent.  Do exactly that.
>> 
>> Based on an almost-correct patch from Paolo Bonzini.
>> 
>> Signed-off-by: Markus Armbruster <armbru@redhat.com>
>> ---
>>  qobject/json-parser.c | 165 ++++++++++++++------------------------------------
>>  1 file changed, 47 insertions(+), 118 deletions(-)
>> 
>
>>  static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
>>  {
>> -    QObject *obj;
>> +    QObject *token;
>>  
>> -    obj = parse_object(ctxt, ap);
>> -    if (obj == NULL) {
>> -        obj = parse_array(ctxt, ap);
>> -    }
>> -    if (obj == NULL) {
>> -        obj = parse_escape(ctxt, ap);
>> -    }
>> -    if (obj == NULL) {
>> -        obj = parse_keyword(ctxt);
>> -    } 
>> -    if (obj == NULL) {
>> -        obj = parse_literal(ctxt);
>> +    token = parser_context_peek_token(ctxt);
>> +    if (token == NULL) {
>> +        parse_error(ctxt, NULL, "premature EOI");
>
> Should we spell that out as 'end of input'?
>
> But that's cosmetic, and doesn't affect correctness of the conversion.

Doesn't matter, because we generally throw away these error messages,
then make up a useless one *boggle*.  Once that's fixed, the
parse_error() could use some love.

> Reviewed-by: Eric Blake <eblake@redhat.com>

Thanks!
Markus Armbruster Nov. 26, 2015, 9:07 a.m. UTC | #3 
Markus Armbruster <armbru@redhat.com> writes:

> We backtrack in parse_value(), even though JSON is LL(1) and thus can
> be parsed by straightforward recursive descent.  Do exactly that.
>
> Based on an almost-correct patch from Paolo Bonzini.
>
> Signed-off-by: Markus Armbruster <armbru@redhat.com>

Missing a
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

Fixed in my tree.
diff mbox

Patch

diff --git a/qobject/json-parser.c b/qobject/json-parser.c
index b57cac7..60dd624 100644
--- a/qobject/json-parser.c
+++ b/qobject/json-parser.c
@@ -265,23 +265,6 @@  static QObject *parser_context_peek_token(JSONParserContext *ctxt)
     return token;
 }
 
-static JSONParserContext parser_context_save(JSONParserContext *ctxt)
-{
-    JSONParserContext saved_ctxt = {0};
-    saved_ctxt.tokens.pos = ctxt->tokens.pos;
-    saved_ctxt.tokens.count = ctxt->tokens.count;
-    saved_ctxt.tokens.buf = ctxt->tokens.buf;
-    return saved_ctxt;
-}
-
-static void parser_context_restore(JSONParserContext *ctxt,
-                                   JSONParserContext saved_ctxt)
-{
-    ctxt->tokens.pos = saved_ctxt.tokens.pos;
-    ctxt->tokens.count = saved_ctxt.tokens.count;
-    ctxt->tokens.buf = saved_ctxt.tokens.buf;
-}
-
 static void tokens_append_from_iter(QObject *obj, void *opaque)
 {
     JSONParserContext *ctxt = opaque;
@@ -333,7 +316,6 @@  static void parser_context_free(JSONParserContext *ctxt)
 static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
 {
     QObject *key = NULL, *token = NULL, *value, *peek;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
     peek = parser_context_peek_token(ctxt);
     if (peek == NULL) {
@@ -371,7 +353,6 @@  static int parse_pair(JSONParserContext *ctxt, QDict *dict, va_list *ap)
     return 0;
 
 out:
-    parser_context_restore(ctxt, saved_ctxt);
     qobject_decref(key);
 
     return -1;
@@ -381,16 +362,9 @@  static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
 {
     QDict *dict = NULL;
     QObject *token, *peek;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_LCURLY) {
-        goto out;
-    }
+    assert(token && token_get_type(token) == JSON_LCURLY);
 
     dict = qdict_new();
 
@@ -434,7 +408,6 @@  static QObject *parse_object(JSONParserContext *ctxt, va_list *ap)
     return QOBJECT(dict);
 
 out:
-    parser_context_restore(ctxt, saved_ctxt);
     QDECREF(dict);
     return NULL;
 }
@@ -443,16 +416,9 @@  static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
 {
     QList *list = NULL;
     QObject *token, *peek;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_LSQUARE) {
-        goto out;
-    }
+    assert(token && token_get_type(token) == JSON_LSQUARE);
 
     list = qlist_new();
 
@@ -506,109 +472,72 @@  static QObject *parse_array(JSONParserContext *ctxt, va_list *ap)
     return QOBJECT(list);
 
 out:
-    parser_context_restore(ctxt, saved_ctxt);
     QDECREF(list);
     return NULL;
 }
 
 static QObject *parse_keyword(JSONParserContext *ctxt)
 {
-    QObject *token, *ret;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    QObject *token;
     const char *val;
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_KEYWORD) {
-        goto out;
-    }
-
+    assert(token && token_get_type(token) == JSON_KEYWORD);
     val = token_get_value(token);
 
     if (!strcmp(val, "true")) {
-        ret = QOBJECT(qbool_from_bool(true));
+        return QOBJECT(qbool_from_bool(true));
     } else if (!strcmp(val, "false")) {
-        ret = QOBJECT(qbool_from_bool(false));
+        return QOBJECT(qbool_from_bool(false));
     } else if (!strcmp(val, "null")) {
-        ret = qnull();
-    } else {
-        parse_error(ctxt, token, "invalid keyword '%s'", val);
-        goto out;
+        return qnull();
     }
-
-    return ret;
-
-out: 
-    parser_context_restore(ctxt, saved_ctxt);
-
+    parse_error(ctxt, token, "invalid keyword '%s'", val);
     return NULL;
 }
 
 static QObject *parse_escape(JSONParserContext *ctxt, va_list *ap)
 {
-    QObject *token = NULL, *obj;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    QObject *token;
     const char *val;
 
     if (ap == NULL) {
-        goto out;
+        return NULL;
     }
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
-
-    if (token_get_type(token) != JSON_ESCAPE) {
-        goto out;
-    }
-
+    assert(token && token_get_type(token) == JSON_ESCAPE);
     val = token_get_value(token);
 
     if (!strcmp(val, "%p")) {
-        obj = va_arg(*ap, QObject *);
+        return va_arg(*ap, QObject *);
     } else if (!strcmp(val, "%i")) {
-        obj = QOBJECT(qbool_from_bool(va_arg(*ap, int)));
+        return QOBJECT(qbool_from_bool(va_arg(*ap, int)));
     } else if (!strcmp(val, "%d")) {
-        obj = QOBJECT(qint_from_int(va_arg(*ap, int)));
+        return QOBJECT(qint_from_int(va_arg(*ap, int)));
     } else if (!strcmp(val, "%ld")) {
-        obj = QOBJECT(qint_from_int(va_arg(*ap, long)));
+        return QOBJECT(qint_from_int(va_arg(*ap, long)));
     } else if (!strcmp(val, "%lld") ||
                !strcmp(val, "%I64d")) {
-        obj = QOBJECT(qint_from_int(va_arg(*ap, long long)));
+        return QOBJECT(qint_from_int(va_arg(*ap, long long)));
     } else if (!strcmp(val, "%s")) {
-        obj = QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
+        return QOBJECT(qstring_from_str(va_arg(*ap, const char *)));
     } else if (!strcmp(val, "%f")) {
-        obj = QOBJECT(qfloat_from_double(va_arg(*ap, double)));
-    } else {
-        goto out;
+        return QOBJECT(qfloat_from_double(va_arg(*ap, double)));
     }
-
-    return obj;
-
-out:
-    parser_context_restore(ctxt, saved_ctxt);
-
     return NULL;
 }
 
 static QObject *parse_literal(JSONParserContext *ctxt)
 {
-    QObject *token, *obj;
-    JSONParserContext saved_ctxt = parser_context_save(ctxt);
+    QObject *token;
 
     token = parser_context_pop_token(ctxt);
-    if (token == NULL) {
-        goto out;
-    }
+    assert(token);
 
     switch (token_get_type(token)) {
     case JSON_STRING:
-        obj = QOBJECT(qstring_from_escaped_str(ctxt, token));
-        break;
+        return QOBJECT(qstring_from_escaped_str(ctxt, token));
     case JSON_INTEGER: {
         /* A possibility exists that this is a whole-valued float where the
          * fractional part was left out due to being 0 (.0). It's not a big
@@ -627,46 +556,46 @@  static QObject *parse_literal(JSONParserContext *ctxt)
         errno = 0; /* strtoll doesn't set errno on success */
         value = strtoll(token_get_value(token), NULL, 10);
         if (errno != ERANGE) {
-            obj = QOBJECT(qint_from_int(value));
-            break;
+            return QOBJECT(qint_from_int(value));
         }
         /* fall through to JSON_FLOAT */
     }
     case JSON_FLOAT:
         /* FIXME dependent on locale */
-        obj = QOBJECT(qfloat_from_double(strtod(token_get_value(token), NULL)));
-        break;
+        return QOBJECT(qfloat_from_double(strtod(token_get_value(token),
+                                                 NULL)));
     default:
-        goto out;
+        abort();
     }
-
-    return obj;
-
-out:
-    parser_context_restore(ctxt, saved_ctxt);
-
-    return NULL;
 }
 
 static QObject *parse_value(JSONParserContext *ctxt, va_list *ap)
 {
-    QObject *obj;
+    QObject *token;
 
-    obj = parse_object(ctxt, ap);
-    if (obj == NULL) {
-        obj = parse_array(ctxt, ap);
-    }
-    if (obj == NULL) {
-        obj = parse_escape(ctxt, ap);
-    }
-    if (obj == NULL) {
-        obj = parse_keyword(ctxt);
-    } 
-    if (obj == NULL) {
-        obj = parse_literal(ctxt);
+    token = parser_context_peek_token(ctxt);
+    if (token == NULL) {
+        parse_error(ctxt, NULL, "premature EOI");
+        return NULL;
     }
 
-    return obj;
+    switch (token_get_type(token)) {
+    case JSON_LCURLY:
+        return parse_object(ctxt, ap);
+    case JSON_LSQUARE:
+        return parse_array(ctxt, ap);
+    case JSON_ESCAPE:
+        return parse_escape(ctxt, ap);
+    case JSON_INTEGER:
+    case JSON_FLOAT:
+    case JSON_STRING:
+        return parse_literal(ctxt);
+    case JSON_KEYWORD:
+        return parse_keyword(ctxt);
+    default:
+        parse_error(ctxt, token, "expecting value");
+        return NULL;
+    }
 }
 
 QObject *json_parser_parse(QList *tokens, va_list *ap)