From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: "Basil L. Contovounesios" via "Bug reports for GNU Emacs, the Swiss army knife of text editors" Newsgroups: gmane.emacs.bugs Subject: bug#49848: 27.2.50; map-merge plist return alist Date: Wed, 04 Aug 2021 01:41:35 +0100 Message-ID: <877dh282io.fsf@tcd.ie> References: <87o8ae71yv.fsf@hm.sivalik.com> <877dh2qjf1.fsf@web.de> Reply-To: "Basil L. Contovounesios" Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="27356"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: rajeev.jnk@sivalik.com, 49848@debbugs.gnu.org To: Michael Heerdegen Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Wed Aug 04 02:42:10 2021 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mB4z4-0006wl-AE for geb-bug-gnu-emacs@m.gmane-mx.org; Wed, 04 Aug 2021 02:42:10 +0200 Original-Received: from localhost ([::1]:40564 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mB4z3-0006ov-Ax for geb-bug-gnu-emacs@m.gmane-mx.org; Tue, 03 Aug 2021 20:42:09 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:52512) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mB4yw-0006oL-2p for bug-gnu-emacs@gnu.org; Tue, 03 Aug 2021 20:42:02 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:58535) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mB4yv-00055n-SH for bug-gnu-emacs@gnu.org; Tue, 03 Aug 2021 20:42:01 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mB4yv-00052U-QH for bug-gnu-emacs@gnu.org; Tue, 03 Aug 2021 20:42:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: "Basil L. Contovounesios" Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Wed, 04 Aug 2021 00:42:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 49848 X-GNU-PR-Package: emacs Original-Received: via spool by 49848-submit@debbugs.gnu.org id=B49848.162803770619339 (code B ref 49848); Wed, 04 Aug 2021 00:42:01 +0000 Original-Received: (at 49848) by debbugs.gnu.org; 4 Aug 2021 00:41:46 +0000 Original-Received: from localhost ([127.0.0.1]:41846 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mB4yg-00051q-5b for submit@debbugs.gnu.org; Tue, 03 Aug 2021 20:41:46 -0400 Original-Received: from mail-wr1-f53.google.com ([209.85.221.53]:37386) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mB4yd-00051X-FT for 49848@debbugs.gnu.org; Tue, 03 Aug 2021 20:41:44 -0400 Original-Received: by mail-wr1-f53.google.com with SMTP id d8so312436wrm.4 for <49848@debbugs.gnu.org>; Tue, 03 Aug 2021 17:41:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tcd.ie; s=google21; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=a7KDONsbEurde18nvMofrxChiH33Ab1kElxCE27557E=; b=FBANyiVBQlN/MyAxPX4HP3wgF6MWTDDiavG/IWBYdysjXoZo7hT6KY3Bv/qDtFJw96 U/rzcgb0775qxly5uishSIGYkP6PdI6AC2NMqiIUP1q3JuzZdhexYsJ/1yV5g8MyjPQ4 8NvMEqLXBxYIzKVgM/Fzf9YkzhD8qVnR+2QnKPnz7anhvgfQzGH/bARl8+h8w2qcvNdU mQxTmoTWm4JT7EYT+SbVeMTybxNqjWRT+hPukCuuttS1GX4ZppIb0oyli8O7nkkHjVJE mhhaF7+yurIcgQnEznNaRfS28SynUPX+Is4Tub02HnUNUHFitMaNE3DtKINPYonUAkBt eMNA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version; bh=a7KDONsbEurde18nvMofrxChiH33Ab1kElxCE27557E=; b=OE9etbF/jJUwZU+MrHq91j9RBvh1zEbSZExtN6FbIxsszQ/oHwSm3ODvSZbF02isOK 92x728uZnCyzjA4ARzrbXx3EwAePDDLUVbpDcfD/dTpfhidwmkTkAAUjF4B4p8FYEpBt M084tfUEUeSow+PiHpTB3eLVfx7mOY5dxaTglvBeH/XUdIhqi7PKuACAnjrSfKvjaPLh YeeKeqDHrhfjxdeqGgg54R+zulazjgTFMFluhfHUK4eutR+UCX+qVGi364YPeknE2aiS R1lVpMKiWp/i4o6w5uMC4AjbxIrALTmZ00DpNW5MUk3MPLwor/j1HX+ci/QyUuegEH8h odPA== X-Gm-Message-State: AOAM533ycp8MK9AJa81jnGTBG8MEC8mVOip5yYQQ/+FSuI6xJfUKBwJz jAV+U1I0BYwhSX0WEYIa9GT44A== X-Google-Smtp-Source: ABdhPJztJyoCeltQMFQVjngENxfL/kHu6uB2va/kSguxFiK98lYQwXG1/jreG0e7GNdzlfgxvEPChw== X-Received: by 2002:a5d:4207:: with SMTP id n7mr25636363wrq.326.1628037697463; Tue, 03 Aug 2021 17:41:37 -0700 (PDT) Original-Received: from localhost ([2a02:8084:20e2:c380:d15:339e:aa10:60f1]) by smtp.gmail.com with ESMTPSA id v15sm524850wmj.11.2021.08.03.17.41.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 03 Aug 2021 17:41:36 -0700 (PDT) In-Reply-To: <877dh2qjf1.fsf@web.de> (Michael Heerdegen's message of "Tue, 03 Aug 2021 23:59:14 +0200") X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list 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-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:211109 Archived-At: --=-=-= Content-Type: text/plain tags 49848 + patch quit Michael Heerdegen writes: > Rajeev N via "Bug reports for GNU Emacs, the Swiss army knife of text > editors" writes: > >> (map-merge 'plist nil '(:a 1)) >> expected: '(:a 1) >> got: '((:a . 1)) > > I can reproduce this behavior and consider it a bug. > > The implementation of `map-merge' starts with an empty plist "RESULT" > (i.e., nil) and fills it like > > (map-do (lambda (key value) > (setf (map-elt result key) value)) > (pop maps)) > > The setter of `map-elt' treats nil as empty alist (at the end, this is > decided by `map--plist-p' which doesn't consider nil a plist). > > So the underlying problem is more general, maybe this is not the only > issue this ambiguity causes. There's not much we can do about the inherent ambiguity between empty alists and plists, short of introducing other functions alongside map-elt/map-put! that take an explicit type. But then the justification for using map.el functions is kind of lost. In the specific case of merging maps into a desired type, we can simply be more careful in such ambiguous cases. The attached patch does that, while also avoiding the quadratic lookup behaviour for lists. While there, I noticed more discrepancies, however. map-merge-with promises to call its function argument whenever multiple keys are eql, but that does not always correspond with map-merge, i.e. sometimes non-eql keys are merged: (progn (require 'map) (map-merge-with 'list (lambda (a b) (message ">>> %s %s" a b) b) `((,(string ?a) . 1)) `((,(string ?a) . 2)))) In Emacs 26, it returns (("a" . 2) ("a" . 1)) without printing. In Emacs 27 and 28, it returns (("a" . 2)) without printing. Do we consider this a regression in Emacs 27 and try to fix it in 28 (keeping in mind that map.el is also a GNU ELPA package)? Or do we drop the eql guarantee in the docstring, and call the function argument whenever two keys are merged, as in the attached patch? I think the latter option may facilitate the equal-ity consistency being discussed in https://bug.gnu.org/47368. WDYT? Thanks, -- Basil --=-=-= Content-Type: text/x-diff Content-Disposition: attachment; filename=0001-Fix-merging-of-ambiguous-nil-maps.patch >From 2b81b9d1d19d33d8cef68e0968e79f637aa32b6e Mon Sep 17 00:00:00 2001 From: "Basil L. Contovounesios" Date: Wed, 4 Aug 2021 00:48:50 +0100 Subject: [PATCH] Fix merging of ambiguous nil maps * lisp/emacs-lisp/map.el (map--merge): New merging subroutine that uses a hash table in place of lists, for both efficiency and avoiding ambiguities (bug#49848). (map-merge): Rewrite in terms of map--merge. (map-merge-with): Ditto. This ensures that FUNCTION is called whenever two keys are merged, even if they are not eql (which could happen until now). It also makes map-merge-with consistent with map-merge, thus achieving greater overall predictability. * etc/NEWS: Announce this weakening of guarantees. * test/lisp/emacs-lisp/map-tests.el (test-map-merge) (test-map-merge-with): Don't depend on specific orderings. Test that nil is correctly merged into a plist. --- etc/NEWS | 8 +++++ lisp/emacs-lisp/map.el | 58 +++++++++++++++++++------------ test/lisp/emacs-lisp/map-tests.el | 24 ++++++++----- 3 files changed, 60 insertions(+), 30 deletions(-) diff --git a/etc/NEWS b/etc/NEWS index 86aeea69ca..d5d0645697 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -1600,6 +1600,14 @@ This is a slightly deeper copy than the previous 'copy-sequence'. --- *** The function 'map-contains-key' now supports plists. +--- +*** More consistent duplicate key handling in 'map-merge-with'. +Until now, 'map-merge-with' promised to call its function argument +whenever multiple maps contained 'eql' keys. However, this did not +always coincide with the keys that were actually merged, which could +be 'equal' instead. The function argument is now called whenever keys +are merged, for greater consistency with 'map-merge' and 'map-elt'. + ** Package --- diff --git a/lisp/emacs-lisp/map.el b/lisp/emacs-lisp/map.el index c59342875d..a920d606ac 100644 --- a/lisp/emacs-lisp/map.el +++ b/lisp/emacs-lisp/map.el @@ -371,37 +371,51 @@ map-every-p map) t)) +(defun map--merge (merge type &rest maps) + "Merge into a map of TYPE all the key/value pairs in MAPS. +MERGE is a function that takes the target MAP, a KEY, and a +VALUE, merges KEY and VALUE into MAP, and returns the result. +MAP may be of a type other than TYPE." + ;; Use a hash table internally if `type' is a list. This avoids + ;; both quadratic lookup behavior and the type ambiguity of nil. + (let* ((tolist (memq type '(list alist plist))) + (result (map-into (pop maps) + ;; Use same testfn as `map-elt' gv setter. + (cond ((eq type 'plist) '(hash-table :test eq)) + (tolist '(hash-table :test equal)) + (type))))) + (dolist (map maps) + (map-do (lambda (key value) + (setq result (funcall merge result key value))) + map)) + ;; Convert internal representation to desired type. + (if tolist (map-into result type) result))) + (defun map-merge (type &rest maps) "Merge into a map of TYPE all the key/value pairs in MAPS. See `map-into' for all supported values of TYPE." - (let ((result (map-into (pop maps) type))) - (while maps - ;; FIXME: When `type' is `list', we get an O(N^2) behavior. - ;; For small tables, this is fine, but for large tables, we - ;; should probably use a hash-table internally which we convert - ;; to an alist in the end. - (map-do (lambda (key value) - (setf (map-elt result key) value)) - (pop maps))) - result)) + (apply #'map--merge + (lambda (result key value) + (setf (map-elt result key) value) + result) + type maps)) (defun map-merge-with (type function &rest maps) "Merge into a map of TYPE all the key/value pairs in MAPS. -When two maps contain the same (`eql') key, call FUNCTION on the two +When two maps contain the same key, call FUNCTION on the two values and use the value returned by it. Each of MAPS can be an alist, plist, hash-table, or array. See `map-into' for all supported values of TYPE." - (let ((result (map-into (pop maps) type)) - (not-found (list nil))) - (while maps - (map-do (lambda (key value) - (cl-callf (lambda (old) - (if (eql old not-found) - value - (funcall function old value))) - (map-elt result key not-found))) - (pop maps))) - result)) + (let ((not-found (list nil))) + (apply #'map--merge + (lambda (result key value) + (cl-callf (lambda (old) + (if (eql old not-found) + value + (funcall function old value))) + (map-elt result key not-found)) + result) + type maps))) (cl-defgeneric map-into (map type) "Convert MAP into a map of TYPE.") diff --git a/test/lisp/emacs-lisp/map-tests.el b/test/lisp/emacs-lisp/map-tests.el index a04c6bef02..658ed2e711 100644 --- a/test/lisp/emacs-lisp/map-tests.el +++ b/test/lisp/emacs-lisp/map-tests.el @@ -446,16 +446,24 @@ test-map-let (ert-deftest test-map-merge () "Test `map-merge'." - (should (equal (map-merge 'list '(a 1) '((b . 2) (c . 3)) - #s(hash-table data (c 4))) - '((c . 4) (b . 2) (a . 1))))) + (should (equal (sort (map-merge 'list '(a 1) '((b . 2) (c . 3)) + #s(hash-table data (c 4))) + (lambda (x y) (string< (car x) (car y)))) + '((a . 1) (b . 2) (c . 4)))) + (should (equal (map-merge 'list () '(:a 1)) '((:a . 1)))) + (should (equal (map-merge 'alist () '(:a 1)) '((:a . 1)))) + (should (equal (map-merge 'plist () '(:a 1)) '(:a 1)))) (ert-deftest test-map-merge-with () - (should (equal (map-merge-with 'list #'+ - '((1 . 2)) - '((1 . 3) (2 . 4)) - '((1 . 1) (2 . 5) (3 . 0))) - '((3 . 0) (2 . 9) (1 . 6))))) + (should (equal (sort (map-merge-with 'list #'+ + '((1 . 2)) + '((1 . 3) (2 . 4)) + '((1 . 1) (2 . 5) (3 . 0))) + #'car-less-than-car) + '((1 . 6) (2 . 9) (3 . 0)))) + (should (equal (map-merge-with 'list #'+ () '(:a 1)) '((:a . 1)))) + (should (equal (map-merge-with 'alist #'+ () '(:a 1)) '((:a . 1)))) + (should (equal (map-merge-with 'plist #'+ () '(:a 1)) '(:a 1)))) (ert-deftest test-map-merge-empty () "Test merging of empty maps." -- 2.30.2 --=-=-=--