bc/867cf1028adc5b18bbb1802593719702f5a367

   1 Return-Path: <m.walters@qmul.ac.uk>\r
   2 X-Original-To: notmuch@notmuchmail.org\r
   3 Delivered-To: notmuch@notmuchmail.org\r
   4 Received: from localhost (localhost [127.0.0.1])\r
   5         by olra.theworths.org (Postfix) with ESMTP id 974E4431FB6\r
   6         for <notmuch@notmuchmail.org>; Thu,  5 Jul 2012 01:30:22 -0700 (PDT)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -1.098\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-1.098 tagged_above=-999 required=5\r
  12         tests=[DKIM_ADSP_CUSTOM_MED=0.001, FREEMAIL_FROM=0.001,\r
  13         NML_ADSP_CUSTOM_MED=1.2, RCVD_IN_DNSWL_MED=-2.3] autolearn=disabled\r
  14 Received: from olra.theworths.org ([127.0.0.1])\r
  15         by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
  16         with ESMTP id wlj16INpiuJE for <notmuch@notmuchmail.org>;\r
  17         Thu,  5 Jul 2012 01:30:21 -0700 (PDT)\r
  18 Received: from mail2.qmul.ac.uk (mail2.qmul.ac.uk [138.37.6.6])\r
  19         (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))\r
  20         (No client certificate requested)\r
  21         by olra.theworths.org (Postfix) with ESMTPS id 20E47431FAE\r
  22         for <notmuch@notmuchmail.org>; Thu,  5 Jul 2012 01:30:21 -0700 (PDT)\r
  23 Received: from smtp.qmul.ac.uk ([138.37.6.40])\r
  24         by mail2.qmul.ac.uk with esmtp (Exim 4.71)\r
  25         (envelope-from <m.walters@qmul.ac.uk>)\r
  26         id 1SmhS1-0007XL-NO; Thu, 05 Jul 2012 09:30:16 +0100\r
  27 Received: from 94-192-233-223.zone6.bethere.co.uk ([94.192.233.223]\r
  28         helo=localhost)\r
  29         by smtp.qmul.ac.uk with esmtpsa (TLSv1:AES128-SHA:128) (Exim 4.69)\r
  30         (envelope-from <m.walters@qmul.ac.uk>)\r
  31         id 1SmhS1-0002uJ-6j; Thu, 05 Jul 2012 09:30:13 +0100\r
  32 From: Mark Walters <markwalters1009@gmail.com>\r
  33 To: Austin Clements <amdragon@MIT.EDU>, notmuch@notmuchmail.org\r
  34 Subject: Re: [PATCH 7/8] emacs: Implement an incremental JSON parser\r
  35 In-Reply-To: <1341354059-29396-8-git-send-email-amdragon@mit.edu>\r
  36 References: <1341354059-29396-1-git-send-email-amdragon@mit.edu>\r
  37         <1341354059-29396-8-git-send-email-amdragon@mit.edu>\r
  38 User-Agent: Notmuch/0.13.2+70~gb6a56e7 (http://notmuchmail.org) Emacs/23.4.1\r
  39         (x86_64-pc-linux-gnu)\r
  40 Date: Thu, 05 Jul 2012 09:30:09 +0100\r
  41 Message-ID: <873956fw4u.fsf@qmul.ac.uk>\r
  42 MIME-Version: 1.0\r
  43 Content-Type: text/plain; charset=us-ascii\r
  44 X-Sender-Host-Address: 94.192.233.223\r
  45 X-QM-SPAM-Info: Sender has good ham record.  :)\r
  46 X-QM-Body-MD5: 961ee8e9e28306f3ed16f58e7506782e (of first 20000 bytes)\r
  47 X-SpamAssassin-Score: -1.8\r
  48 X-SpamAssassin-SpamBar: -\r
  49 X-SpamAssassin-Report: The QM spam filters have analysed this message to\r
  50         determine if it is\r
  51         spam. We require at least 5.0 points to mark a message as spam.\r
  52         This message scored -1.8 points.\r
  53         Summary of the scoring: \r
  54         * -2.3 RCVD_IN_DNSWL_MED RBL: Sender listed at http://www.dnswl.org/,\r
  55         *      medium trust\r
  56         *      [138.37.6.40 listed in list.dnswl.org]\r
  57         * 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail\r
  58         provider *      (markwalters1009[at]gmail.com)\r
  59         * -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay\r
  60         *      domain\r
  61         *  0.5 AWL AWL: From: address is in the auto white-list\r
  62 X-QM-Scan-Virus: ClamAV says the message is clean\r
  63 Cc: tomi.ollila@iki.fi\r
  64 X-BeenThere: notmuch@notmuchmail.org\r
  65 X-Mailman-Version: 2.1.13\r
  66 Precedence: list\r
  67 List-Id: "Use and development of the notmuch mail system."\r
  68         <notmuch.notmuchmail.org>\r
  69 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  70         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  71 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  72 List-Post: <mailto:notmuch@notmuchmail.org>\r
  73 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  74 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  75         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  76 X-List-Received-Date: Thu, 05 Jul 2012 08:30:22 -0000\r
  77 \r
  78 On Tue, 03 Jul 2012, Austin Clements <amdragon@MIT.EDU> wrote:\r
  79 > This parser is designed to read streaming JSON whose structure is\r
  80 > known to the caller.  Like a typical JSON parsing interface, it\r
  81 > provides a function to read a complete JSON value from the input.\r
  82 > However, it extends this with an additional function that\r
  83 > requires the next value in the input to be a compound value and\r
  84 > descends into it, allowing its elements to be read one at a time\r
  85 > or further descended into.  Both functions can return 'retry to\r
  86 > indicate that not enough input is available.\r
  87 >\r
  88 > The parser supports efficient partial parsing, so there's no need to\r
  89 > frame the input for correctness or performance.\r
  90 >\r
  91 > Currently only descending into JSON lists is supported because that's\r
  92 > all we need, but support for descending into JSON objects can be added\r
  93 > in the future.\r
  94 > ---\r
  95 >  emacs/notmuch-lib.el |  183 ++++++++++++++++++++++++++++++++++++++++++++++++++\r
  96 >  1 file changed, 183 insertions(+)\r
  97 >\r
  98 > diff --git a/emacs/notmuch-lib.el b/emacs/notmuch-lib.el\r
  99 > index c829df3..f7cda33 100644\r
 100 > --- a/emacs/notmuch-lib.el\r
 101 > +++ b/emacs/notmuch-lib.el\r
 102 > @@ -23,6 +23,7 @@\r
 103 >  \r
 104 >  (require 'mm-view)\r
 105 >  (require 'mm-decode)\r
 106 > +(require 'json)\r
 107 >  (eval-when-compile (require 'cl))\r
 108 >  \r
 109 >  (defvar notmuch-command "notmuch"\r
 110 > @@ -296,6 +297,188 @@ was called."\r
 111 >  (defvar notmuch-show-process-crypto nil)\r
 112 >  (make-variable-buffer-local 'notmuch-show-process-crypto)\r
 113 >  \r
 114 > +;; Incremental JSON parsing\r
 115 > +\r
 116 > +(defun notmuch-json-create-parser (buffer)\r
 117 > +  "Return a streaming JSON parser that consumes input from BUFFER.\r
 118 > +\r
 119 > +This parser is designed to read streaming JSON whose structure is\r
 120 > +known to the caller.  Like a typical JSON parsing interface, it\r
 121 > +provides a function to read a complete JSON value from the input.\r
 122 > +However, it extends this with an additional function that\r
 123 > +requires the next value in the input to be a compound value and\r
 124 > +descends into it, allowing its elements to be read one at a time\r
 125 > +or further descended into.  Both functions can return 'retry to\r
 126 > +indicate that not enough input is available.\r
 127 > +\r
 128 > +The parser always consumes input from BUFFER's point.  Hence, the\r
 129 > +caller is allowed to delete and data before point and may\r
 130 > +resynchronize after an error by moving point."\r
 131 > +\r
 132 > +  (list buffer\r
 133 > +     ;; Terminator stack: a stack of characters that indicate the\r
 134 > +     ;; end of the compound values enclosing point\r
 135 > +     '()\r
 136 > +     ;; Next: One of\r
 137 > +     ;; * 'expect-value if the next token must be a value, but a\r
 138 > +     ;;   value has not yet been reached\r
 139 > +     ;; * 'value if point is at the beginning of a value\r
 140 > +     ;; * 'expect-comma if the next token must be a comma\r
 141 > +     'expect-value\r
 142 > +     ;; Allow terminator: non-nil if the next token may be a\r
 143 > +     ;; terminator\r
 144 > +     nil\r
 145 > +     ;; Partial parse position: If state is 'value, a marker for\r
 146 > +     ;; the position of the partial parser or nil if no partial\r
 147 > +     ;; parsing has happened yet\r
 148 > +     nil\r
 149 > +     ;; Partial parse state: If state is 'value, the current\r
 150 > +     ;; `parse-partial-sexp' state\r
 151 > +     nil))\r
 152 > +\r
 153 > +(defmacro notmuch-json-buffer (jp) `(first ,jp))\r
 154 > +(defmacro notmuch-json-term-stack (jp) `(second ,jp))\r
 155 > +(defmacro notmuch-json-next (jp) `(third ,jp))\r
 156 > +(defmacro notmuch-json-allow-term (jp) `(fourth ,jp))\r
 157 > +(defmacro notmuch-json-partial-pos (jp) `(fifth ,jp))\r
 158 > +(defmacro notmuch-json-partial-state (jp) `(sixth ,jp))\r
 159 > +\r
 160 > +(defvar notmuch-json-syntax-table\r
 161 > +  (let ((table (make-syntax-table)))\r
 162 > +    ;; The standard syntax table is what we need except that "." needs\r
 163 > +    ;; to have word syntax instead of punctuation syntax.\r
 164 > +    (modify-syntax-entry ?. "w" table)\r
 165 > +    table)\r
 166 > +  "Syntax table used for incremental JSON parsing.")\r
 167 > +\r
 168 > +(defun notmuch-json-scan-to-value (jp)\r
 169 > +  ;; Helper function that consumes separators, terminators, and\r
 170 > +  ;; whitespace from point.  Returns nil if it successfully reached\r
 171 > +  ;; the beginning of a value, 'end if it consumed a terminator, or\r
 172 > +  ;; 'retry if not enough input was available to reach a value.  Upon\r
 173 > +  ;; nil return, (notmuch-json-next jp) is always 'value.\r
 174 > +\r
 175 > +  (if (eq (notmuch-json-next jp) 'value)\r
 176 > +      ;; We're already at a value\r
 177 > +      nil\r
 178 > +    ;; Drive the state toward 'expect-value\r
 179 > +    (skip-chars-forward " \t\r\n")\r
 180 > +    (or (when (eobp) 'retry)\r
 181 > +     ;; Test for the terminator for the current compound\r
 182 > +     (when (and (notmuch-json-allow-term jp)\r
 183 > +                (eq (char-after) (car (notmuch-json-term-stack jp))))\r
 184 > +       ;; Consume it and expect a comma or terminator next\r
 185 > +       (forward-char)\r
 186 > +       (setf (notmuch-json-term-stack jp) (cdr (notmuch-json-term-stack jp))\r
 187 > +             (notmuch-json-next jp) 'expect-comma\r
 188 > +             (notmuch-json-allow-term jp) t)\r
 189 > +       'end)\r
 190 > +     ;; Test for a separator\r
 191 > +     (when (eq (notmuch-json-next jp) 'expect-comma)\r
 192 > +       (when (/= (char-after) ?,)\r
 193 > +         (signal 'json-readtable-error (list "expected ','")))\r
 194 > +       ;; Consume it, switch to 'expect-value, and disallow a\r
 195 > +       ;; terminator\r
 196 > +       (forward-char)\r
 197 > +       (skip-chars-forward " \t\r\n")\r
 198 > +       (setf (notmuch-json-next jp) 'expect-value\r
 199 > +             (notmuch-json-allow-term jp) nil)\r
 200 > +       ;; We moved point, so test for eobp again and fall through\r
 201 > +       ;; to the next test if there's more input\r
 202 > +       (when (eobp) 'retry))\r
 203 > +     ;; Next must be 'expect-value and we know this isn't\r
 204 > +     ;; whitespace, EOB, or a terminator, so point must be on a\r
 205 > +     ;; value\r
 206 > +     (progn\r
 207 > +       (assert (eq (notmuch-json-next jp) 'expect-value))\r
 208 > +       (setf (notmuch-json-next jp) 'value)\r
 209 > +       nil))))\r
 210 > +\r
 211 > +(defun notmuch-json-begin-compound (jp)\r
 212 > +  "Parse the beginning of a compound value and traverse inside it.\r
 213 > +\r
 214 > +Returns 'retry if there is insufficient input to parse the\r
 215 > +beginning of the compound.  If this is able to parse the\r
 216 > +beginning of a compound, it returns t and later calls to\r
 217 > +`notmuch-json-read' will return the compound's elements.\r
 218 > +\r
 219 > +Entering JSON objects is current unimplemented."\r
 220 > +\r
 221 > +  (with-current-buffer (notmuch-json-buffer jp)\r
 222 > +    ;; Disallow terminators\r
 223 > +    (setf (notmuch-json-allow-term jp) nil)\r
 224 > +    (or (notmuch-json-scan-to-value jp)\r
 225 > +     (if (/= (char-after) ?\[)\r
 226 > +         (signal 'json-readtable-error (list "expected '['"))\r
 227 > +       (forward-char)\r
 228 > +       (push ?\] (notmuch-json-term-stack jp))\r
 229 > +       ;; Expect a value or terminator next\r
 230 > +       (setf (notmuch-json-next jp) 'expect-value\r
 231 > +             (notmuch-json-allow-term jp) t)\r
 232 > +       t))))\r
 233 > +\r
 234 > +(defun notmuch-json-read (jp)\r
 235 > +  "Parse the value at point in JP's buffer.\r
 236 > +\r
 237 > +Returns 'retry if there is insufficient input to parse a complete\r
 238 > +JSON value.  If the parser is currently inside a compound value\r
 239 > +and the next token ends the list or object, returns 'end.\r
 240 > +Otherwise, returns the value."\r
 241 \r
 242 \r
 243 This looks excellent! My only comment is that I think it would be\r
 244 helpful it the above comment and the one for notmuch-json-begin-compound\r
 245 said what happens to point when they get called.\r
 246 \r
 247 Also, I think in practice a lot of the parsing is done by json.el (that\r
 248 you use this to enter one level of the hierarchy and then use this to\r
 249 ensure that json.el only gets complete objects to parse) so I assume\r
 250 this means that your much faster replacement for json.el could be\r
 251 slotted in? It might be worth mentioning that in the commit message.\r
 252 \r
 253 Best wishes\r
 254 \r
 255 Mark\r
 256 \r
 257 > +\r
 258 > +  (with-current-buffer (notmuch-json-buffer jp)\r
 259 > +    (or\r
 260 > +     ;; Get to a value state\r
 261 > +     (notmuch-json-scan-to-value jp)\r
 262 > +\r
 263 > +     ;; Can we parse a complete value?\r
 264 > +     (let ((complete\r
 265 > +         (if (looking-at "[-+0-9tfn]")\r
 266 > +             ;; This is a number or a keyword, so the partial\r
 267 > +             ;; parser isn't going to help us because a truncated\r
 268 > +             ;; number or keyword looks like a complete symbol to\r
 269 > +             ;; it.  Look for something that clearly ends it.\r
 270 > +             (save-excursion\r
 271 > +               (skip-chars-forward "^]},: \t\r\n")\r
 272 > +               (not (eobp)))\r
 273 > +\r
 274 > +           ;; We're looking at a string, object, or array, which we\r
 275 > +           ;; can partial parse.  If we just reached the value, set\r
 276 > +           ;; up the partial parser.\r
 277 > +           (when (null (notmuch-json-partial-state jp))\r
 278 > +             (setf (notmuch-json-partial-pos jp) (point-marker)))\r
 279 > +\r
 280 > +           ;; Extend the partial parse until we either reach EOB or\r
 281 > +           ;; get the whole value\r
 282 > +           (save-excursion\r
 283 > +             (let ((pstate\r
 284 > +                    (with-syntax-table notmuch-json-syntax-table\r
 285 > +                      (parse-partial-sexp\r
 286 > +                       (notmuch-json-partial-pos jp) (point-max) 0 nil\r
 287 > +                       (notmuch-json-partial-state jp)))))\r
 288 > +               ;; A complete value is available if we've reached\r
 289 > +               ;; depth 0 or less and encountered a complete\r
 290 > +               ;; subexpression.\r
 291 > +               (if (and (<= (first pstate) 0) (third pstate))\r
 292 > +                   t\r
 293 > +                 ;; Not complete.  Update the partial parser state\r
 294 > +                 (setf (notmuch-json-partial-pos jp) (point-marker)\r
 295 > +                       (notmuch-json-partial-state jp) pstate)\r
 296 > +                 nil))))))\r
 297 > +\r
 298 > +       (if (not complete)\r
 299 > +        'retry\r
 300 > +      ;; We have a value.  Reset the partial parse state and expect\r
 301 > +      ;; a comma or terminator after the value.\r
 302 > +      (setf (notmuch-json-next jp) 'expect-comma\r
 303 > +            (notmuch-json-allow-term jp) t\r
 304 > +            (notmuch-json-partial-pos jp) nil\r
 305 > +            (notmuch-json-partial-state jp) nil)\r
 306 > +      ;; Parse the value\r
 307 > +      (let* ((json-object-type 'plist)\r
 308 > +             (json-array-type 'list)\r
 309 > +             (json-false nil))\r
 310 > +        (json-read)))))))\r
 311 > +\r
 312 >  (provide 'notmuch-lib)\r
 313 >  \r
 314 >  ;; Local Variables:\r
 315 > -- \r
 316 > 1.7.10\r
 317 >\r
 318 > _______________________________________________\r
 319 > notmuch mailing list\r
 320 > notmuch@notmuchmail.org\r
 321 > http://notmuchmail.org/mailman/listinfo/notmuch\r