From 7f7c7761961fb7632b9cbf039f979fae0b3af677 Mon Sep 17 00:00:00 2001 From: Austin Clements Date: Fri, 6 Jul 2012 16:52:25 +2000 Subject: [PATCH] [PATCH v2 7/9] emacs: Implement an incremental JSON parser --- ac/669200d495b82f56b245d728a89b81fbbfd85e | 314 ++++++++++++++++++++++ 1 file changed, 314 insertions(+) create mode 100644 ac/669200d495b82f56b245d728a89b81fbbfd85e diff --git a/ac/669200d495b82f56b245d728a89b81fbbfd85e b/ac/669200d495b82f56b245d728a89b81fbbfd85e new file mode 100644 index 000000000..5daad9d02 --- /dev/null +++ b/ac/669200d495b82f56b245d728a89b81fbbfd85e @@ -0,0 +1,314 @@ +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 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 + -- 2.26.2