bug#49848: 27.2.50; map-merge plist return alist

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]

(map-merge 'plist nil '(:a 1))
expected: '(:a 1)
got: '((:a . 1))

Also, tested on master.


In GNU Emacs 27.2.50 (build 5, x86_64-pc-linux-gnu, GTK+ Version 3.24.24, cairo version 1.16.0)
 of 2021-07-14 built on hp
Repository revision: 7ac411ae2ce91572a2bdb8eaa1ee6ceccf162e35
Repository branch: emacs-27
Windowing system distributor 'The X.Org Foundation', version 11.0.12011000
System Description: Debian GNU/Linux 11 (bullseye)

Recent messages:
(No files need saving)
Opening connection to imap.sivalik.com via tls...
Opening connection to imap.sivalik.com...done
Opening connection to imap.gmail.com via tls...
Opening connection to imap.gmail.com...done
nnimap rajeev.sivalik splitting mail...done
nnimap binita.gmail splitting mail...done
nnimap read 0k from imap.gmail.com
Hiding all blocks...done
Making completion list...

Configured using:
 'configure --with-mailutils --with-cairo
 --prefix=/home/rajeev/tmp/build/em/o/emacs-27'

Configured features:
XPM JPEG TIFF GIF PNG RSVG CAIRO SOUND GPM DBUS GSETTINGS GLIB NOTIFY
INOTIFY ACL LIBSELINUX GNUTLS LIBXML2 FREETYPE HARFBUZZ M17N_FLT
LIBOTF ZLIB TOOLKIT_SCROLL_BARS GTK3 X11 XDBE XIM MODULES THREADS
LIBSYSTEMD JSON PDUMPER LCMS2 GMP

Important settings:
  value of $LC_TIME: en_GB.UTF-8
  value of $LANG: en_US.UTF-8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix

Major mode: Messages

Minor modes in effect:
  global-so-long-mode: t
  global-auto-revert-mode: t
  shell-dirtrack-mode: t
  midnight-mode: t
  display-time-mode: t
  tooltip-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  buffer-read-only: t
  transient-mark-mode: t

Load-path shadows:
/home/rajeev/.config/emacs/elpa/map-3.0/map hides /home/rajeev/tmp/build/em/o/emacs-27/share/emacs/27.2.50/lisp/emacs-lisp/map

Features:
(shadow sort emacsbug utf-7 nnml js cc-mode cc-fonts cc-guess cc-menus
cc-cmds cc-styles cc-align cc-engine cc-vars cc-defs smerge-mode diff
vc-bzr vc-src vc-sccs vc-svn vc-cvs vc-rcs vc-dir ewoc vc
vc-dispatcher mm-archive network-stream url-cache edmacro kmacro
server cursor-sensor time-stamp bbdb-gnus nnfolder xt-mouse which-func
imenu timeclock spam spam-stat gnus-uu yenc semantic/util-modes
semantic/util semantic semantic/tag semantic/lex semantic/fw
mode-local cedet org-indent reveal mailalias bbdb-message mail-extr
ol-eww eww mm-url thingatpt url-queue ol-rmail ol-mhe ol-irc ol-info
ol-gnus nnir ol-docview doc-view jka-compr image-mode exif ol-bibtex
bibtex ol-bbdb ol-w3m icomplete so-long cl-extra autorevert filenotify
bbdb-anniv tramp tramp-loaddefs trampver tramp-integration files-x
tramp-compat shell ls-lisp printing ps-print ps-print-loaddefs ps-def
lpr web-server web-server-status-codes el/web midnight el/cron
backtrace help-mode qp el/wthr el/av el/hass el/fin el/remote
el/script type-break cal-iso org-id lunar solar cal-dst holidays
hol-loaddefs el/calc olc el/loc term disp-table ehelp dirtrack
hideshow dbus parsec gnutls gnus-delay gnus-draft gnus-agent gnus-srvr
gnus-score score-mode nnvirtual nntp gnus-cache gnus-msg nndraft nnmh
gnus-icalendar org-capture gnus-art mm-uu mml2015 mm-view mml-smime
smime dig icalendar sieve sieve-mode sieve-manage sasl sasl-anonymous
sasl-login sasl-plain sendmail time ox-odt rng-loc rng-uri rng-parse
rng-match rng-dt rng-util rng-pttrn nxml-parse nxml-ns nxml-enc xmltok
nxml-util ox-latex ox-icalendar ox-html table ox-ascii ox-publish ox
org-element avl-tree generator org-agenda org-refile org-crypt org ob
ob-tangle ob-ref ob-lob ob-table ob-exp org-macro org-footnote org-src
ob-comint org-pcomplete pcomplete comint ansi-color ring org-list
org-faces org-entities noutline outline org-version ob-emacs-lisp
ob-core ob-eval org-table ol org-keys org-compat advice org-macs
org-loaddefs find-func gnus-sum shr svg xml dom gnus-group gnus-undo
gnus-start gnus-cloud nnimap nnmail mail-source utf7 netrc nnoo
parse-time iso8601 gnus-spec gnus-int gnus-range message dired
dired-loaddefs format-spec rfc822 mml mml-sec epa derived mm-decode
mm-bodies mm-encode gmm-utils mailheader gnus-win gnus pp vc-git
diff-mode easy-mmode cus-edit cus-start cus-load nnheader gnus-util
rmail rmail-loaddefs text-property-search time-date mail-utils
wid-edit el/org el/doc el/mail oauth2 url-http url url-proxy
url-privacy url-expand url-methods url-history mailcap url-auth
mail-parse rfc2231 rfc2047 rfc2045 mm-util ietf-drums mail-prsvr
url-cookie url-domsuf url-util url-gw nsm rmc puny plstore epg
epg-config el/tools el/shell el/webdr el/xmpp el/diary timer-list
bbdb-mua el/timer el/util bbdb-com crm mailabbrev bbdb bbdb-site
timezone el/bbdb appt diary-lib diary-loaddefs cal-menu calendar
cal-loaddefs el/init wombat-theme info package easymenu browse-url
url-handlers url-parse auth-source cl-seq eieio eieio-core cl-macs
eieio-loaddefs password-cache json subr-x map url-vars seq byte-opt gv
bytecomp byte-compile cconv cl-loaddefs cl-lib tooltip eldoc electric
uniquify ediff-hook vc-hooks lisp-float-type mwheel term/x-win x-win
term/common-win x-dnd tool-bar dnd fontset image regexp-opt fringe
tabulated-list replace newcomment text-mode elisp-mode lisp-mode
prog-mode register page tab-bar menu-bar rfn-eshadow isearch timer
select scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame minibuffer cl-generic cham georgian utf-8-lang
misc-lang vietnamese tibetan thai tai-viet lao korean japanese
eucjp-ms cp51932 hebrew greek romanian slovak czech european ethiopic
indian cyrillic chinese composite charscript charprop case-table
epa-hook jka-cmpr-hook help simple abbrev obarray cl-preloaded nadvice
loaddefs button faces cus-face macroexp files text-properties overlay
sha1 md5 base64 format env code-pages mule custom widget
hashtable-print-readable backquote threads dbusbind inotify lcms2
dynamic-setting system-font-setting font-render-setting cairo
move-toolbar gtk x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 431082 34150)
 (symbols 48 37600 22)
 (strings 32 143406 6634)
 (string-bytes 1 4765442)
 (vectors 16 62178)
 (vector-slots 8 735772 48862)
 (floats 8 1187 1245)
 (intervals 56 2500 618)
 (buffers 1000 78))

bug#49848: 27.2.50; map-merge plist return alist

[Michael Heerdegen]

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.

Michael.

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]

I am using the following workaorund

  (advice-add 'map-merge :filter-args (lambda (r) (seq-filter #'identity r)))

bug#49848: 27.2.50; map-merge plist return alist

[Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors]

[-- 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

bug#49848: 27.2.50; map-merge plist return alist

[Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors]

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> I think the latter option may facilitate the equal-ity consistency
> being discussed in https://bug.gnu.org/47368.
                             ^^^
                             bugs

-- 
Basil

bug#49848: 27.2.50; map-merge plist return alist

[Lars Ingebrigtsen]

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> 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.

I think that's the correct (and indeed only) solution here when dealing
with alist/plist ambiguities (if we don't want to say explicitly for
every map* call what the type actually is meant to be).

> (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)?

I think the current result value is the one that makes sense...

> 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 that makes sense.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#49848: 27.2.50; map-merge plist return alist

[Michael Heerdegen]

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> 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.

Looks good and appropriate to me (I could not read very carefully,
though, I'm tired today and can have a second look tomorrow).

Should we handle the corner case when zero maps get merged?

> I think the latter option may facilitate the equal-ity consistency
> being discussed in https://bug.gnu.org/47368.
>
> WDYT?

Seems a good idea to me, too.


Thanks,

Michael.

bug#49848: 27.2.50; map-merge plist return alist

[Michael Heerdegen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Should we handle the corner case when zero maps get merged?

Hm, `pop' just returns a nil then, so that case doesn't even seem to
need special treatment.

Michael.

bug#49848: 27.2.50; map-merge plist return alist

[Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> "Basil L. Contovounesios" <contovob@tcd.ie> writes:
>
>> 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.
>
> Looks good and appropriate to me (I could not read very carefully,
> though, I'm tired today and can have a second look tomorrow).
>
> Should we handle the corner case when zero maps get merged?

That's already implied by the &rest args, and checked in
test-map-merge-empty.

>> I think the latter option may facilitate the equal-ity consistency
>> being discussed in https://bug.gnu.org/47368.
>>
>> WDYT?
>
> Seems a good idea to me, too.

Thanks.  Unless someone beats me to it or there are further comments,
I'll push the patch to Emacs 28 next week, and probably bump the Version
header too.

-- 
Basil

bug#49848: 27.2.50; map-merge plist return alist

[Basil L. Contovounesios via Bug reports for GNU Emacs, the Swiss army knife of text editors]

close 49848 28.1
quit

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> Unless someone beats me to it or there are further comments,
> I'll push the patch to Emacs 28 next week, and probably bump the Version
> header too.

Pushed and closing.

Fix merging of ambiguous nil maps
37d48edf6d 2021-08-14 11:24:54 +0100
https://git.sv.gnu.org/cgit/emacs.git/commit/?id=37d48edf6d406a4730caa0393f7695de2bfadfcc

Thanks,

-- 
Basil