From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Simen =?UTF-8?Q?Heggest=C3=B8yl?= Newsgroups: gmane.emacs.bugs Subject: bug#21616: [PATCH] Enable sorting of JSON object keys when encoding Date: Wed, 11 Nov 2015 19:59:33 +0100 Message-ID: <1447268373.11049.0@smtp.gmail.com> References: <87twq6e986.fsf@gmail.com> <563FE255.5080506@yandex.ru> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-X111p62ssqJCQOySR+V0" X-Trace: ger.gmane.org 1447268428 23575 80.91.229.3 (11 Nov 2015 19:00:28 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 11 Nov 2015 19:00:28 +0000 (UTC) Cc: 21616@debbugs.gnu.org To: Dmitry Gutov Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Wed Nov 11 20:00:17 2015 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Zwacy-0002gS-SZ for geb-bug-gnu-emacs@m.gmane.org; Wed, 11 Nov 2015 20:00:17 +0100 Original-Received: from localhost ([::1]:42473 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Zwacy-0008PY-CH for geb-bug-gnu-emacs@m.gmane.org; Wed, 11 Nov 2015 14:00:16 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58929) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Zwacr-0008JD-N1 for bug-gnu-emacs@gnu.org; Wed, 11 Nov 2015 14:00:11 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Zwacn-0003aI-Jn for bug-gnu-emacs@gnu.org; Wed, 11 Nov 2015 14:00:09 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:42839) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Zwacn-0003ZK-Gv for bug-gnu-emacs@gnu.org; Wed, 11 Nov 2015 14:00:05 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1Zwacm-00031Z-I8 for bug-gnu-emacs@gnu.org; Wed, 11 Nov 2015 14:00:04 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Simen =?UTF-8?Q?Heggest=C3=B8yl?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 11 Nov 2015 19:00:04 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 21616 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch Original-Received: via spool by 21616-submit@debbugs.gnu.org id=B21616.144726840011592 (code B ref 21616); Wed, 11 Nov 2015 19:00:04 +0000 Original-Received: (at 21616) by debbugs.gnu.org; 11 Nov 2015 19:00:00 +0000 Original-Received: from localhost ([127.0.0.1]:33547 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Zwach-00030t-Kk for submit@debbugs.gnu.org; Wed, 11 Nov 2015 14:00:00 -0500 Original-Received: from mail-lb0-f179.google.com ([209.85.217.179]:36792) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1ZwacM-00030R-EU for 21616@debbugs.gnu.org; Wed, 11 Nov 2015 13:59:58 -0500 Original-Received: by lbblt2 with SMTP id lt2so22181262lbb.3 for <21616@debbugs.gnu.org>; Wed, 11 Nov 2015 10:59:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:subject:to:cc:message-id:in-reply-to:references :mime-version:content-type; bh=/jEzkzok/W0dkb10TRFV2x/yarnluKvyMBEKwi8X5zo=; b=lSb0aYeR+cxsenBV8IXFGUoAY9xeVF1UsdMBOG4mSwff1c/2X3ktYfSCnKCnzeOvoj Vb3VvIe+qFBFe2P0EFn4GLxH2j8zf9PrhIp32JF0uPxlFs2jxkJd9rv/w5ghPp/BYt9k 2y5du9VPXoi1xsbAQJykIxHmwOxBV8OT6AyUDdi77hqABvGJCF4qpzBVAFRgeZx7cwZB pjPdOhs63VOUL006cvcrrZ98oUTBUUBNaGq3r4fXE1lHKBYRpvPnz2eIZB+1DRtwEY6b 3HmbwCp3iqlr0DEjzte3TW9MzuVSTD6aJ8b0DGZ1u5HKRWlWkVS1gCZvgfugEsjaMtZd Bk/g== X-Received: by 10.112.198.234 with SMTP id jf10mr4968385lbc.49.1447268377072; Wed, 11 Nov 2015 10:59:37 -0800 (PST) Original-Received: from [192.168.100.7] (cm-84.210.143.4.getinternet.no. [84.210.143.4]) by smtp.gmail.com with ESMTPSA id m80sm1682794lfm.15.2015.11.11.10.59.35 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 11 Nov 2015 10:59:36 -0800 (PST) In-Reply-To: <563FE255.5080506@yandex.ru> X-Mailer: geary/0.10.0 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:108630 Archived-At: --=-X111p62ssqJCQOySR+V0 Content-Type: multipart/alternative; boundary="=-0g6Te+qRbGj0MEFpYXmf" --=-0g6Te+qRbGj0MEFpYXmf Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable Hello, Dmitry. On Mon, Nov 9, 2015 at 1:01 AM, Dmitry Gutov wrote: > Call it json-[encode-]key-sort-predicate, maybe? Indeed, "predicate" seems more appropriate. I'll change the name. > The unification part makes me concerned, again, from the performance=20 > standpoint. Did you do any measuring here? I didn't before now, but as you feared, the performance became measurably worse when encoding plists and hash-tables. I performed some benchmarks on the same 560K JSON file as before (http://folk.uio.no/simenheg/huge.json), with the following results: With json-object-type set to hash-table: Before the patch: (benchmark-run 100 (json-encode huge)) =E2=87=92 (17.396825399 800 7.954568797999999) After the patch: (benchmark-run 100 (json-encode huge)) =E2=87=92 (19.338006244000002 700 9.664285849000013) With json-object-type set to plist: Before the patch: (benchmark-run 100 (json-encode huge)) =E2=87=92 (15.152158676 1101 7.109026906) After the patch: (benchmark-run 100 (json-encode huge)) =E2=87=92 (18.122579887 777 8.46547749400001) How about keeping the old encoding code as the default, and only do the {hash-table, plist} =E2=86=92 alist transform when the output is to be sort= ed? That keeps new code to a minimum, and the they would need to be transformed to an intermediate structure to be sorted anyway. A patch implementing this suggestion is attached. Here are the same benchmarks with the new patch applied: With json-object-type set to hash-table: (benchmark-run 100 (json-encode huge)) =E2=87=92 (17.229601604 750 8.015517397999995) With json-object-type set to plist: (benchmark-run 100 (json-encode huge)) =E2=87=92 (14.363185863 1101 6.992225689000007) -- Simen = --=-0g6Te+qRbGj0MEFpYXmf Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable
Hello, Dmitry.

On Mon, Nov 9, 2015 at 1:01 AM, Dmi= try Gutov <dgutov@yandex.ru> wrote:
Call it json-[encode-]key-sort-predicate, maybe?

Indeed, "predicate" seems more appro= priate. I'll change the name.

The unification part makes = me concerned, again, from the performance standpoint. Did you do any measur= ing here?

I didn't before now, but as you f= eared, the performance became
measurably worse when encoding plis= ts and hash-tables.

I performed some benchmarks on= the same 560K JSON file as before
(http://folk.uio.no/simenheg/huge.json), with the f= ollowing results:

With json-object-type set to has= h-table:

  Before the patch:
 = (benchmark-run 100 (json-encode huge))
      &nbs= p;=E2=87=92 (17.396825399 800 7.954568797999999)

&= nbsp; After the patch:
  (benchmark-run 100 (json-encode hug= e))
       =E2=87=92 (19.338006244000002 700 = 9.664285849000013)

With json-object-type set to pl= ist:

  Before the patch:
  (be= nchmark-run 100 (json-encode huge))
       = =E2=87=92 (15.152158676 1101 7.109026906)

  A= fter the patch:
  (benchmark-run 100 (json-encode huge))
       =E2=87=92 (18.122579887 777 8.46547749400= 001)

How about keeping the old encoding code as th= e default, and only do the
{hash-table, plist} =E2=86=92 alist tr= ansform when the output is to be sorted?
That keeps new code to a= minimum, and the they would need to be
transformed to an interme= diate structure to be sorted anyway.

A patch imple= menting this suggestion is attached. Here are the same
benchmarks= with the new patch applied:

With json-object-type= set to hash-table:

  (benchmark-run 100 (jso= n-encode huge))
       =E2=87=92 (17.22960160= 4 750 8.015517397999995)

With json-object-type set= to plist:

  (benchmark-run 100 (json-encode = huge))
       =E2=87=92 (14.363185863 1101 6.= 992225689000007)

-- Simen
= --=-0g6Te+qRbGj0MEFpYXmf-- --=-X111p62ssqJCQOySR+V0 Content-Type: text/x-patch Content-Disposition: attachment; filename=0001-Enable-sorting-of-JSON-object-keys-when-encoding.patch >From 07ae7e0e3aa2db77a6bd2a9c97ebd34367c76972 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Simen=20Heggest=C3=B8yl?= Date: Sun, 4 Oct 2015 12:21:57 +0200 Subject: [PATCH] Enable sorting of JSON object keys when encoding * lisp/json.el (json-encoding-object-sort-predicate): New variable for specifying a sorting predicate for JSON objects during encoding. (json--plist-to-alist): New utility function. (json-encode-hash-table): Re-use `json-encode-alist' when object keys are to be sorted. (json-encode-alist): Sort output by `json-encoding-object-sort-predicate, when set. (json-encode-plist): Re-use `json-encode-alist' when object keys are to be sorted. (json-pretty-print-buffer-ordered): New command to pretty print the buffer with object keys sorted alphabetically. (json-pretty-print-ordered): New command to pretty print the region with object keys sorted alphabetically. * test/automated/json-tests.el (test-json-plist-to-alist) (test-json-encode-plist, test-json-encode-hash-table) (test-json-encode-alist-with-sort-predicate) (test-json-encode-plist-with-sort-predicate): New tests. * etc/NEWS: Add an entry for the new commands. --- etc/NEWS | 4 ++ lisp/json.el | 117 ++++++++++++++++++++++++++++--------------- test/automated/json-tests.el | 29 +++++++++++ 3 files changed, 111 insertions(+), 39 deletions(-) diff --git a/etc/NEWS b/etc/NEWS index f3df92e..46910b0 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -332,6 +332,10 @@ unlike `bookmark-set' which silently updates an existing bookmark. --- *** `json-pretty-print' and `json-pretty-print-buffer' now maintain the ordering of object keys by default. +--- +*** New commands `json-pretty-print-ordered' and +`json-pretty-print-buffer-ordered' pretty prints JSON objects with +object keys sorted alphabetically. ** You can recompute the VC state of a file buffer with `M-x vc-refresh-state' ** Prog mode has some support for multi-mode indentation. diff --git a/lisp/json.el b/lisp/json.el index 97cf993..0214a3e 100644 --- a/lisp/json.el +++ b/lisp/json.el @@ -52,6 +52,8 @@ ;;; Code: +(require 'map) + ;; Parameters (defvar json-object-type 'alist @@ -111,6 +113,13 @@ json-encoding-lisp-style-closings "If non-nil, ] and } closings will be formatted lisp-style, without indentation.") +(defvar json-encoding-object-sort-predicate nil + "Sorting predicate for JSON object keys during encoding. +If nil, no sorting is performed. Else, JSON object keys are +ordered by the specified sort predicate during encoding. For +instance, setting this to `string<' will have JSON object keys +ordered alphabetically.") + (defvar json-pre-element-read-function nil "Function called (if non-nil) by `json-read-array' and `json-read-object' right before reading a JSON array or object, @@ -159,6 +168,15 @@ json--plist-reverse (push prop res))) res)) +(defun json--plist-to-alist (plist) + "Return an alist of the property-value pairs in PLIST." + (let (res) + (while plist + (let ((prop (pop plist)) + (val (pop plist))) + (push (cons prop val) res))) + (nreverse res))) + (defmacro json--with-indentation (body) `(let ((json--encoding-current-indentation (if json-encoding-pretty-print @@ -492,32 +510,39 @@ json-read-object (defun json-encode-hash-table (hash-table) "Return a JSON representation of HASH-TABLE." - (format "{%s%s}" - (json-join - (let (r) - (json--with-indentation - (maphash - (lambda (k v) - (push (format - (if json-encoding-pretty-print - "%s%s: %s" - "%s%s:%s") - json--encoding-current-indentation - (json-encode-key k) - (json-encode v)) - r)) - hash-table)) - r) - json-encoding-separator) - (if (or (not json-encoding-pretty-print) - json-encoding-lisp-style-closings) - "" - json--encoding-current-indentation))) + (if json-encoding-object-sort-predicate + (json-encode-alist (map-into hash-table 'list)) + (format "{%s%s}" + (json-join + (let (r) + (json--with-indentation + (maphash + (lambda (k v) + (push (format + (if json-encoding-pretty-print + "%s%s: %s" + "%s%s:%s") + json--encoding-current-indentation + (json-encode-key k) + (json-encode v)) + r)) + hash-table)) + r) + json-encoding-separator) + (if (or (not json-encoding-pretty-print) + json-encoding-lisp-style-closings) + "" + json--encoding-current-indentation)))) ;; List encoding (including alists and plists) (defun json-encode-alist (alist) "Return a JSON representation of ALIST." + (when json-encoding-object-sort-predicate + (setq alist + (sort alist (lambda (a b) + (funcall json-encoding-object-sort-predicate + (car a) (car b)))))) (format "{%s%s}" (json-join (json--with-indentation @@ -537,25 +562,27 @@ json-encode-alist (defun json-encode-plist (plist) "Return a JSON representation of PLIST." - (let (result) - (json--with-indentation - (while plist - (push (concat - json--encoding-current-indentation - (json-encode-key (car plist)) - (if json-encoding-pretty-print - ": " - ":") - (json-encode (cadr plist))) - result) - (setq plist (cddr plist)))) - (concat "{" - (json-join (nreverse result) json-encoding-separator) - (if (and json-encoding-pretty-print - (not json-encoding-lisp-style-closings)) + (if json-encoding-object-sort-predicate + (json-encode-alist (json--plist-to-alist plist)) + (let (result) + (json--with-indentation + (while plist + (push (concat json--encoding-current-indentation - "") - "}"))) + (json-encode-key (car plist)) + (if json-encoding-pretty-print + ": " + ":") + (json-encode (cadr plist))) + result) + (setq plist (cddr plist)))) + (concat "{" + (json-join (nreverse result) json-encoding-separator) + (if (and json-encoding-pretty-print + (not json-encoding-lisp-style-closings)) + json--encoding-current-indentation + "") + "}")))) (defun json-encode-list (list) "Return a JSON representation of LIST. @@ -698,6 +725,18 @@ json-pretty-print (txt (delete-and-extract-region begin end))) (insert (json-encode (json-read-from-string txt)))))) +(defun json-pretty-print-buffer-ordered () + "Pretty-print current buffer with object keys ordered." + (interactive) + (let ((json-encoding-object-sort-predicate 'string<)) + (json-pretty-print-buffer))) + +(defun json-pretty-print-ordered (begin end) + "Pretty-print the region with object keys ordered." + (interactive "r") + (let ((json-encoding-object-sort-predicate 'string<)) + (json-pretty-print begin end))) + (provide 'json) ;;; json.el ends here diff --git a/test/automated/json-tests.el b/test/automated/json-tests.el index fa1f548..8f0cd6f 100644 --- a/test/automated/json-tests.el +++ b/test/automated/json-tests.el @@ -28,11 +28,40 @@ (should (equal (json--plist-reverse '(:a 1 :b 2 :c 3)) '(:c 3 :b 2 :a 1)))) +(ert-deftest test-json-plist-to-alist () + (should (equal (json--plist-to-alist '()) '())) + (should (equal (json--plist-to-alist '(:a 1)) '((:a . 1)))) + (should (equal (json--plist-to-alist '(:a 1 :b 2 :c 3)) + '((:a . 1) (:b . 2) (:c . 3))))) + +(ert-deftest test-json-encode-plist () + (let ((plist '(:a 1 :b 2))) + (should (equal (json-encode plist) "{\"a\":1,\"b\":2}")))) + (ert-deftest json-encode-simple-alist () (should (equal (json-encode '((a . 1) (b . 2))) "{\"a\":1,\"b\":2}"))) +(ert-deftest test-json-encode-hash-table () + (let ((hash-table (make-hash-table)) + (json-encoding-object-sort-predicate 'string<)) + (puthash :a 1 hash-table) + (puthash :b 2 hash-table) + (puthash :c 3 hash-table) + (should (equal (json-encode hash-table) + "{\"a\":1,\"b\":2,\"c\":3}")))) + +(ert-deftest test-json-encode-alist-with-sort-predicate () + (let ((alist '((:c . 3) (:a . 1) (:b . 2))) + (json-encoding-object-sort-predicate 'string<)) + (should (equal (json-encode alist) "{\"a\":1,\"b\":2,\"c\":3}")))) + +(ert-deftest test-json-encode-plist-with-sort-predicate () + (let ((plist '(:c 3 :a 1 :b 2)) + (json-encoding-object-sort-predicate 'string<)) + (should (equal (json-encode plist) "{\"a\":1,\"b\":2,\"c\":3}")))) + (ert-deftest json-read-simple-alist () (let ((json-object-type 'alist)) (should (equal (json-read-from-string "{\"a\": 1, \"b\": 2}") -- 2.6.2 --=-X111p62ssqJCQOySR+V0--