From 7265f070ae8998965e5001c42e33c09f9471de09 Mon Sep 17 00:00:00 2001 From: Mark Walters Date: Thu, 5 Jul 2012 09:30:09 +0100 Subject: [PATCH] Re: [PATCH 7/8] emacs: Implement an incremental JSON parser --- bc/867cf1028adc5b18bbb1802593719702f5a367 | 321 ++++++++++++++++++++++ 1 file changed, 321 insertions(+) create mode 100644 bc/867cf1028adc5b18bbb1802593719702f5a367 diff --git a/bc/867cf1028adc5b18bbb1802593719702f5a367 b/bc/867cf1028adc5b18bbb1802593719702f5a367 new file mode 100644 index 000000000..c2a9f5c16 --- /dev/null +++ b/bc/867cf1028adc5b18bbb1802593719702f5a367 @@ -0,0 +1,321 @@ +Return-Path: +X-Original-To: notmuch@notmuchmail.org +Delivered-To: notmuch@notmuchmail.org +Received: from localhost (localhost [127.0.0.1]) + by olra.theworths.org (Postfix) with ESMTP id 974E4431FB6 + for ; Thu, 5 Jul 2012 01:30:22 -0700 (PDT) +X-Virus-Scanned: Debian amavisd-new at olra.theworths.org +X-Spam-Flag: NO +X-Spam-Score: -1.098 +X-Spam-Level: +X-Spam-Status: No, score=-1.098 tagged_above=-999 required=5 + tests=[DKIM_ADSP_CUSTOM_MED=0.001, FREEMAIL_FROM=0.001, + NML_ADSP_CUSTOM_MED=1.2, RCVD_IN_DNSWL_MED=-2.3] autolearn=disabled +Received: from olra.theworths.org ([127.0.0.1]) + by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id wlj16INpiuJE for ; + Thu, 5 Jul 2012 01:30:21 -0700 (PDT) +Received: from mail2.qmul.ac.uk (mail2.qmul.ac.uk [138.37.6.6]) + (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) + (No client certificate requested) + by olra.theworths.org (Postfix) with ESMTPS id 20E47431FAE + for ; Thu, 5 Jul 2012 01:30:21 -0700 (PDT) +Received: from smtp.qmul.ac.uk ([138.37.6.40]) + by mail2.qmul.ac.uk with esmtp (Exim 4.71) + (envelope-from ) + id 1SmhS1-0007XL-NO; Thu, 05 Jul 2012 09:30:16 +0100 +Received: from 94-192-233-223.zone6.bethere.co.uk ([94.192.233.223] + helo=localhost) + by smtp.qmul.ac.uk with esmtpsa (TLSv1:AES128-SHA:128) (Exim 4.69) + (envelope-from ) + id 1SmhS1-0002uJ-6j; Thu, 05 Jul 2012 09:30:13 +0100 +From: Mark Walters +To: Austin Clements , notmuch@notmuchmail.org +Subject: Re: [PATCH 7/8] emacs: Implement an incremental JSON parser +In-Reply-To: <1341354059-29396-8-git-send-email-amdragon@mit.edu> +References: <1341354059-29396-1-git-send-email-amdragon@mit.edu> + <1341354059-29396-8-git-send-email-amdragon@mit.edu> +User-Agent: Notmuch/0.13.2+70~gb6a56e7 (http://notmuchmail.org) Emacs/23.4.1 + (x86_64-pc-linux-gnu) +Date: Thu, 05 Jul 2012 09:30:09 +0100 +Message-ID: <873956fw4u.fsf@qmul.ac.uk> +MIME-Version: 1.0 +Content-Type: text/plain; charset=us-ascii +X-Sender-Host-Address: 94.192.233.223 +X-QM-SPAM-Info: Sender has good ham record. :) +X-QM-Body-MD5: 961ee8e9e28306f3ed16f58e7506782e (of first 20000 bytes) +X-SpamAssassin-Score: -1.8 +X-SpamAssassin-SpamBar: - +X-SpamAssassin-Report: The QM spam filters have analysed this message to + determine if it is + spam. We require at least 5.0 points to mark a message as spam. + This message scored -1.8 points. + Summary of the scoring: + * -2.3 RCVD_IN_DNSWL_MED RBL: Sender listed at http://www.dnswl.org/, + * medium trust + * [138.37.6.40 listed in list.dnswl.org] + * 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail + provider * (markwalters1009[at]gmail.com) + * -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay + * domain + * 0.5 AWL AWL: From: address is in the auto white-list +X-QM-Scan-Virus: ClamAV says the message is clean +Cc: tomi.ollila@iki.fi +X-BeenThere: notmuch@notmuchmail.org +X-Mailman-Version: 2.1.13 +Precedence: list +List-Id: "Use and development of the notmuch mail system." + +List-Unsubscribe: , + +List-Archive: +List-Post: +List-Help: +List-Subscribe: , + +X-List-Received-Date: Thu, 05 Jul 2012 08:30:22 -0000 + +On Tue, 03 Jul 2012, Austin Clements wrote: +> This parser is designed to read streaming JSON whose structure is +> known to the caller. Like a typical JSON parsing interface, it +> provides a function to read a complete JSON value from the input. +> However, it extends this with an additional function that +> requires the next value in the input to be a compound value and +> descends into it, allowing its elements to be read one at a time +> or further descended into. Both functions can return 'retry to +> indicate that not enough input is available. +> +> The parser supports efficient partial parsing, so there's no need to +> frame the input for correctness or performance. +> +> Currently only descending into JSON lists is supported because that's +> all we need, but support for descending into JSON objects can be added +> in the future. +> --- +> emacs/notmuch-lib.el | 183 ++++++++++++++++++++++++++++++++++++++++++++++++++ +> 1 file changed, 183 insertions(+) +> +> diff --git a/emacs/notmuch-lib.el b/emacs/notmuch-lib.el +> index c829df3..f7cda33 100644 +> --- a/emacs/notmuch-lib.el +> +++ b/emacs/notmuch-lib.el +> @@ -23,6 +23,7 @@ +> +> (require 'mm-view) +> (require 'mm-decode) +> +(require 'json) +> (eval-when-compile (require 'cl)) +> +> (defvar notmuch-command "notmuch" +> @@ -296,6 +297,188 @@ was called." +> (defvar notmuch-show-process-crypto nil) +> (make-variable-buffer-local 'notmuch-show-process-crypto) +> +> +;; Incremental JSON parsing +> + +> +(defun notmuch-json-create-parser (buffer) +> + "Return a streaming JSON parser that consumes input from BUFFER. +> + +> +This parser is designed to read streaming JSON whose structure is +> +known to the caller. Like a typical JSON parsing interface, it +> +provides a function to read a complete JSON value from the input. +> +However, it extends this with an additional function that +> +requires the next value in the input to be a compound value and +> +descends into it, allowing its elements to be read one at a time +> +or further descended into. Both functions can return 'retry to +> +indicate that not enough input is available. +> + +> +The parser always consumes input from BUFFER's point. Hence, the +> +caller is allowed to delete and data before point and may +> +resynchronize after an error by moving point." +> + +> + (list buffer +> + ;; Terminator stack: a stack of characters that indicate the +> + ;; end of the compound values enclosing point +> + '() +> + ;; Next: One of +> + ;; * 'expect-value if the next token must be a value, but a +> + ;; value has not yet been reached +> + ;; * 'value if point is at the beginning of a value +> + ;; * 'expect-comma if the next token must be a comma +> + 'expect-value +> + ;; Allow terminator: non-nil if the next token may be a +> + ;; terminator +> + nil +> + ;; Partial parse position: If state is 'value, a marker for +> + ;; the position of the partial parser or nil if no partial +> + ;; parsing has happened yet +> + nil +> + ;; Partial parse state: If state is 'value, the current +> + ;; `parse-partial-sexp' state +> + nil)) +> + +> +(defmacro notmuch-json-buffer (jp) `(first ,jp)) +> +(defmacro notmuch-json-term-stack (jp) `(second ,jp)) +> +(defmacro notmuch-json-next (jp) `(third ,jp)) +> +(defmacro notmuch-json-allow-term (jp) `(fourth ,jp)) +> +(defmacro notmuch-json-partial-pos (jp) `(fifth ,jp)) +> +(defmacro notmuch-json-partial-state (jp) `(sixth ,jp)) +> + +> +(defvar notmuch-json-syntax-table +> + (let ((table (make-syntax-table))) +> + ;; The standard syntax table is what we need except that "." needs +> + ;; to have word syntax instead of punctuation syntax. +> + (modify-syntax-entry ?. "w" table) +> + table) +> + "Syntax table used for incremental JSON parsing.") +> + +> +(defun notmuch-json-scan-to-value (jp) +> + ;; Helper function that consumes separators, terminators, and +> + ;; whitespace from point. Returns nil if it successfully reached +> + ;; the beginning of a value, 'end if it consumed a terminator, or +> + ;; 'retry if not enough input was available to reach a value. Upon +> + ;; nil return, (notmuch-json-next jp) is always 'value. +> + +> + (if (eq (notmuch-json-next jp) 'value) +> + ;; We're already at a value +> + nil +> + ;; Drive the state toward 'expect-value +> + (skip-chars-forward " \t\r\n") +> + (or (when (eobp) 'retry) +> + ;; Test for the terminator for the current compound +> + (when (and (notmuch-json-allow-term jp) +> + (eq (char-after) (car (notmuch-json-term-stack jp)))) +> + ;; Consume it and expect a comma or terminator next +> + (forward-char) +> + (setf (notmuch-json-term-stack jp) (cdr (notmuch-json-term-stack jp)) +> + (notmuch-json-next jp) 'expect-comma +> + (notmuch-json-allow-term jp) t) +> + 'end) +> + ;; Test for a separator +> + (when (eq (notmuch-json-next jp) 'expect-comma) +> + (when (/= (char-after) ?,) +> + (signal 'json-readtable-error (list "expected ','"))) +> + ;; Consume it, switch to 'expect-value, and disallow a +> + ;; terminator +> + (forward-char) +> + (skip-chars-forward " \t\r\n") +> + (setf (notmuch-json-next jp) 'expect-value +> + (notmuch-json-allow-term jp) nil) +> + ;; We moved point, so test for eobp again and fall through +> + ;; to the next test if there's more input +> + (when (eobp) 'retry)) +> + ;; Next must be 'expect-value and we know this isn't +> + ;; whitespace, EOB, or a terminator, so point must be on a +> + ;; value +> + (progn +> + (assert (eq (notmuch-json-next jp) 'expect-value)) +> + (setf (notmuch-json-next jp) 'value) +> + nil)))) +> + +> +(defun notmuch-json-begin-compound (jp) +> + "Parse the beginning of a compound value and traverse inside it. +> + +> +Returns 'retry if there is insufficient input to parse the +> +beginning of the compound. If this is able to parse the +> +beginning of a compound, it returns t and later calls to +> +`notmuch-json-read' will return the compound's elements. +> + +> +Entering JSON objects is current unimplemented." +> + +> + (with-current-buffer (notmuch-json-buffer jp) +> + ;; Disallow terminators +> + (setf (notmuch-json-allow-term jp) nil) +> + (or (notmuch-json-scan-to-value jp) +> + (if (/= (char-after) ?\[) +> + (signal 'json-readtable-error (list "expected '['")) +> + (forward-char) +> + (push ?\] (notmuch-json-term-stack jp)) +> + ;; Expect a value or terminator next +> + (setf (notmuch-json-next jp) 'expect-value +> + (notmuch-json-allow-term jp) t) +> + t)))) +> + +> +(defun notmuch-json-read (jp) +> + "Parse the value at point in JP's buffer. +> + +> +Returns 'retry if there is insufficient input to parse a complete +> +JSON value. If the parser is currently inside a compound value +> +and the next token ends the list or object, returns 'end. +> +Otherwise, returns the value." + + +This looks excellent! My only comment is that I think it would be +helpful it the above comment and the one for notmuch-json-begin-compound +said what happens to point when they get called. + +Also, I think in practice a lot of the parsing is done by json.el (that +you use this to enter one level of the hierarchy and then use this to +ensure that json.el only gets complete objects to parse) so I assume +this means that your much faster replacement for json.el could be +slotted in? It might be worth mentioning that in the commit message. + +Best wishes + +Mark + +> + +> + (with-current-buffer (notmuch-json-buffer jp) +> + (or +> + ;; Get to a value state +> + (notmuch-json-scan-to-value jp) +> + +> + ;; Can we parse a complete value? +> + (let ((complete +> + (if (looking-at "[-+0-9tfn]") +> + ;; This is a number or a keyword, so the partial +> + ;; parser isn't going to help us because a truncated +> + ;; number or keyword looks like a complete symbol to +> + ;; it. Look for something that clearly ends it. +> + (save-excursion +> + (skip-chars-forward "^]},: \t\r\n") +> + (not (eobp))) +> + +> + ;; We're looking at a string, object, or array, which we +> + ;; can partial parse. If we just reached the value, set +> + ;; up the partial parser. +> + (when (null (notmuch-json-partial-state jp)) +> + (setf (notmuch-json-partial-pos jp) (point-marker))) +> + +> + ;; Extend the partial parse until we either reach EOB or +> + ;; get the whole value +> + (save-excursion +> + (let ((pstate +> + (with-syntax-table notmuch-json-syntax-table +> + (parse-partial-sexp +> + (notmuch-json-partial-pos jp) (point-max) 0 nil +> + (notmuch-json-partial-state jp))))) +> + ;; A complete value is available if we've reached +> + ;; depth 0 or less and encountered a complete +> + ;; subexpression. +> + (if (and (<= (first pstate) 0) (third pstate)) +> + t +> + ;; Not complete. Update the partial parser state +> + (setf (notmuch-json-partial-pos jp) (point-marker) +> + (notmuch-json-partial-state jp) pstate) +> + nil)))))) +> + +> + (if (not complete) +> + 'retry +> + ;; We have a value. Reset the partial parse state and expect +> + ;; a comma or terminator after the value. +> + (setf (notmuch-json-next jp) 'expect-comma +> + (notmuch-json-allow-term jp) t +> + (notmuch-json-partial-pos jp) nil +> + (notmuch-json-partial-state jp) nil) +> + ;; Parse the value +> + (let* ((json-object-type 'plist) +> + (json-array-type 'list) +> + (json-false nil)) +> + (json-read))))))) +> + +> (provide 'notmuch-lib) +> +> ;; Local Variables: +> -- +> 1.7.10 +> +> _______________________________________________ +> notmuch mailing list +> notmuch@notmuchmail.org +> http://notmuchmail.org/mailman/listinfo/notmuch -- 2.26.2