From: "Basil L. Contovounesios" via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>
To: Michael Heerdegen <michael_heerdegen@web.de>
Cc: rajeev.jnk@sivalik.com, 49848@debbugs.gnu.org
Subject: bug#49848: 27.2.50; map-merge plist return alist
Date: Wed, 04 Aug 2021 01:41:35 +0100 [thread overview]
Message-ID: <877dh282io.fsf@tcd.ie> (raw)
In-Reply-To: <877dh2qjf1.fsf@web.de> (Michael Heerdegen's message of "Tue, 03 Aug 2021 23:59:14 +0200")
[-- Attachment #1: Type: text/plain, Size: 2199 bytes --]
tags 49848 + patch
quit
Michael Heerdegen <michael_heerdegen@web.de> writes:
> Rajeev N via "Bug reports for GNU Emacs, the Swiss army knife of text
> editors" <bug-gnu-emacs@gnu.org> 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
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-merging-of-ambiguous-nil-maps.patch --]
[-- Type: text/x-diff, Size: 6818 bytes --]
From 2b81b9d1d19d33d8cef68e0968e79f637aa32b6e Mon Sep 17 00:00:00 2001
From: "Basil L. Contovounesios" <contovob@tcd.ie>
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
next prev parent reply other threads:[~2021-08-04 0:41 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-08-03 19:38 bug#49848: 27.2.50; map-merge plist return alist Rajeev N via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-08-03 21:59 ` Michael Heerdegen
2021-08-03 22:45 ` Rajeev N via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-08-04 0:41 ` Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors [this message]
2021-08-04 0:45 ` Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-08-04 7:47 ` Lars Ingebrigtsen
2021-08-05 2:47 ` Michael Heerdegen
2021-08-05 2:55 ` Michael Heerdegen
2021-08-05 10:48 ` Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-08-14 10:35 ` Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=877dh282io.fsf@tcd.ie \
--to=bug-gnu-emacs@gnu.org \
--cc=49848@debbugs.gnu.org \
--cc=contovob@tcd.ie \
--cc=michael_heerdegen@web.de \
--cc=rajeev.jnk@sivalik.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).