From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by olra.theworths.org (Postfix) with ESMTP id AFE68431FC3 for ; Thu, 5 Jul 2012 13:52:48 -0700 (PDT) X-Virus-Scanned: Debian amavisd-new at olra.theworths.org X-Spam-Flag: NO X-Spam-Score: -0.7 X-Spam-Level: X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5 tests=[RCVD_IN_DNSWL_LOW=-0.7] 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 LPWVmsQDGSvx for ; Thu, 5 Jul 2012 13:52:46 -0700 (PDT) Received: from dmz-mailsec-scanner-7.mit.edu (DMZ-MAILSEC-SCANNER-7.MIT.EDU [18.7.68.36]) by olra.theworths.org (Postfix) with ESMTP id 5A0B6431FBF for ; Thu, 5 Jul 2012 13:52:43 -0700 (PDT) X-AuditID: 12074424-b7f2a6d0000008bf-2c-4ff5fe9a66df Received: from mailhub-auth-4.mit.edu ( [18.7.62.39]) by dmz-mailsec-scanner-7.mit.edu (Symantec Messaging Gateway) with SMTP id 76.5B.02239.A9EF5FF4; Thu, 5 Jul 2012 16:52:42 -0400 (EDT) Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by mailhub-auth-4.mit.edu (8.13.8/8.9.2) with ESMTP id q65Kqgse019983; Thu, 5 Jul 2012 16:52:42 -0400 Received: from drake.dyndns.org (26-4-182.dynamic.csail.mit.edu [18.26.4.182]) (authenticated bits=0) (User authenticated as amdragon@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id q65KqbrC027240 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT); Thu, 5 Jul 2012 16:52:40 -0400 (EDT) Received: from amthrax by drake.dyndns.org with local (Exim 4.77) (envelope-from ) id 1Smt2T-0004Xn-Lh; Thu, 05 Jul 2012 16:52:37 -0400 From: Austin Clements To: notmuch@notmuchmail.org Subject: [PATCH v2 7/9] emacs: Implement an incremental JSON parser Date: Thu, 5 Jul 2012 16:52:25 -0400 Message-Id: <1341521547-15502-8-git-send-email-amdragon@mit.edu> X-Mailer: git-send-email 1.7.10 In-Reply-To: <1341521547-15502-1-git-send-email-amdragon@mit.edu> References: <1341354059-29396-1-git-send-email-amdragon@mit.edu> <1341521547-15502-1-git-send-email-amdragon@mit.edu> X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrOIsWRmVeSWpSXmKPExsUixG6nrjvr31d/g9N/1SxWz+WxuH5zJrPF m5XzWB2YPXbOusvucfjrQhaPZ6tuMQcwR3HZpKTmZJalFunbJXBlLO78ylqwyaPi584HjA2M vZZdjJwcEgImElv2LmCBsMUkLtxbz9bFyMUhJLCPUeLb7afsEM56RolVy4+yQDgnmSRerj4G lZnLKLHr73OwfjYBDYlt+5czgtgiAtISO+/OZgWxmQXiJLZM+Q8WFxZwlji76QBYnEVAVWL9 mRYmEJtXwEGibcF8dog75CWe3u9jA7E5BRwlLkxcDNYrJFAu8WfJP5YJjPwLGBlWMcqm5Fbp 5iZm5hSnJusWJyfm5aUW6Zrr5WaW6KWmlG5iBIeXi8oOxuZDSocYBTgYlXh4DXO/+AuxJpYV V+YeYpTkYFIS5W38/dVfiC8pP6UyI7E4I76oNCe1+BCjBAezkghvbwZQjjclsbIqtSgfJiXN waIkzns95aa/kEB6YklqdmpqQWoRTFaGg0NJgvfpX6BGwaLU9NSKtMycEoQ0EwcnyHAeoOEv QGp4iwsSc4sz0yHypxgVpYBGgyQEQBIZpXlwvbD4f8UoDvSKMO8nkCoeYOqA634FNJgJaHDe 4k8gg0sSEVJSDYyRU7r1XbUXCLGu3Hd67TozlbSNEkLWeTt6Y/Z+Up7z9NC7PX9uaH3YfFgj 9OHXN7vatu7Z9WxCjnd/6Uy955d73kx4+/DKB53ZYe8LPSwjN9gc/NjasG6F3ffdoUtFzH7r z+Bb993ObvahzRK/dHZyZzhdTFz8df5f5ZBt9heDjnhzbao0/ajIrMRSnJFoqMVcVJwIAPyt WdjaAgAA 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 20:52:49 -0000 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. The bulk of the parsing is still done by Emacs' json.el, so any improvements or optimizations to that will benefit the incremental parser as well. 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 | 196 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 196 insertions(+) diff --git a/emacs/notmuch-lib.el b/emacs/notmuch-lib.el index c829df3..9e04d97 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,201 @@ 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 moves point past the token that opens +the compound and returns t. 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, moves point to just past the end of the value and +returns the value." + + (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))))))) + +(defun notmuch-json-eof (jp) + "Signal a json-error if there is more input in JP's buffer. + +Moves point to the beginning of any trailing garbage or to the +end of the buffer if there is no trailing garbage." + + (with-current-buffer (notmuch-json-buffer jp) + (skip-chars-forward " \t\r\n") + (unless (eobp) + (signal 'json-error (list "Trailing garbage following JSON data"))))) + (provide 'notmuch-lib) ;; Local Variables: -- 1.7.10