From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Drew Adams Newsgroups: gmane.emacs.bugs Subject: bug#28753: 25.3; Functions to get alist from hash table and vice versa Date: Sat, 30 Dec 2017 16:01:24 -0800 (PST) Message-ID: <94d02ad7-d069-4195-b84a-13229dfa3e9a@default> References: <54ecd1bb-0c84-4b0a-b19e-3a89cbe832bc@default> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: blaine.gmane.org 1514678417 11821 195.159.176.226 (31 Dec 2017 00:00:17 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 31 Dec 2017 00:00:17 +0000 (UTC) Cc: 28753@debbugs.gnu.org To: Philipp Stephani Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Dec 31 01:00:13 2017 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eVR2u-0002Xm-SO for geb-bug-gnu-emacs@m.gmane.org; Sun, 31 Dec 2017 01:00:09 +0100 Original-Received: from localhost ([::1]:45516 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eVR4t-0005Ks-Rx for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Dec 2017 19:02:11 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58922) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1eVR4n-0005Kk-6d for bug-gnu-emacs@gnu.org; Sat, 30 Dec 2017 19:02:06 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1eVR4k-0002Qk-30 for bug-gnu-emacs@gnu.org; Sat, 30 Dec 2017 19:02:05 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:49559) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1eVR4j-0002Pn-Sc for bug-gnu-emacs@gnu.org; Sat, 30 Dec 2017 19:02:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1eVR4j-0006J9-Ix for bug-gnu-emacs@gnu.org; Sat, 30 Dec 2017 19:02:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Drew Adams Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 31 Dec 2017 00:02:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 28753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 28753-submit@debbugs.gnu.org id=B28753.151467850023304 (code B ref 28753); Sun, 31 Dec 2017 00:02:01 +0000 Original-Received: (at 28753) by debbugs.gnu.org; 31 Dec 2017 00:01:40 +0000 Original-Received: from localhost ([127.0.0.1]:58240 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eVR4N-00063Q-Q1 for submit@debbugs.gnu.org; Sat, 30 Dec 2017 19:01:40 -0500 Original-Received: from userp2130.oracle.com ([156.151.31.86]:35672) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eVR4L-0005wt-QJ for 28753@debbugs.gnu.org; Sat, 30 Dec 2017 19:01:38 -0500 Original-Received: from pps.filterd (userp2130.oracle.com [127.0.0.1]) by userp2130.oracle.com (8.16.0.21/8.16.0.21) with SMTP id vBUNvYSp013540; Sun, 31 Dec 2017 00:01:32 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=mime-version : message-id : date : from : sender : to : cc : subject : references : in-reply-to : content-type : content-transfer-encoding; s=corp-2017-10-26; bh=sCjrNRsrDeXdcCU0xHWzynTdpYCWTo9znx6IknWgcKo=; b=uUspqpwxl6GwrUR7t53sDhSERe7305Zd2crL/Qm617yeqHRiNRsRuhP91O54jvp65ivQ T+rXzvALOxXWtHo2P6oV+Z+nxi6geFH0ORifTlQtVWv9xH1T8U5EuAUGQws/bxdqxVTK J6AlPN3dVOQzckCf2lgC0h5qmuY+8FZjDkptC7bhj2HOvskJAMTjcKSINXklxFXstrlx GkvJ6zWcoszGxDxNdDL4zxXdbdPUD5qU4AvUWh+9YmuEN17im5JtQ8WcgpBM4O37wLSF 9cra0acoAyLfrEGie/PM9DHcHkSMDfMryu3+KB6jMkLcxfO182W5uI4KD6fu+3ooJU9o CA== Original-Received: from userv0022.oracle.com (userv0022.oracle.com [156.151.31.74]) by userp2130.oracle.com with ESMTP id 2f628490nr-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Sun, 31 Dec 2017 00:01:31 +0000 Original-Received: from aserv0121.oracle.com (aserv0121.oracle.com [141.146.126.235]) by userv0022.oracle.com (8.14.4/8.14.4) with ESMTP id vBV01UrG015948 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Sun, 31 Dec 2017 00:01:31 GMT Original-Received: from abhmp0008.oracle.com (abhmp0008.oracle.com [141.146.116.14]) by aserv0121.oracle.com (8.14.4/8.13.8) with ESMTP id vBV01UmC032290; Sun, 31 Dec 2017 00:01:30 GMT X-Message-Flag: In-Reply-To: X-Priority: 3 X-Mailer: Oracle Beehive Extensions for Outlook 2.0.1.9.1 (1003210) [OL 16.0.4627.0 (x86)] X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=8760 signatures=668650 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1711220000 definitions=main-1712300351 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] 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" Xref: news.gmane.org gmane.emacs.bugs:141636 Archived-At: > > (when (or use-last-p=C2=A0 (not (gethash key ht))) > > This doesn't work if the value is nil.=20 I guess you mean that it doesn't DTRT if the cdr of an alist entry is `nil' - e.g. (foo) aka (foo . nil). > You need to use an uninterned symbol or some other unique object, e.g. > (eq (gethash key ht #1=3D'#:void) #1#) OK. Dunno which is clearer or whether there is some performance difference, but I would probably just bind a var to a unique cons, e.g. (cons 1 1), outside the `dolist'. E.g.: (let ((ht (make-hash-table :test test :weakness weakness :size size :rehash-size rehash-size :rehash-threshold rehash-threshold)) (uniq-cons (cons 1 1)) key val) (dolist (key.val alist) (setq key (car key.val) val (cdr key.val)) (when (or use-last-p (not (eq (gethash key ht uniq-cons)))) (puthash key val ht))) ht)) (With your approach of using an uninterned symbol, wouldn't you want to do the same thing: bind a var to it outside the `dolist', or would that make no real difference?) =C2=A0 > I'd personally make use-last-p another keyword argument, though. I don't have a strong objection, but why? > > (defun hash-table-to-alist (hash-table) > >=C2=A0 "Create and return an alist created from HASH-TABLE. > > The order of alist entries is the same as the order of hash-table > > entries (which normally is the order in which the entries were added > > to the table)." > >=C2=A0 (let ((al=C2=A0 ())) > >=C2=A0 =C2=A0 (maphash (lambda (key val) (push (cons key val) al)) hash-= table) > >=C2=A0 =C2=A0 (nreverse al))) > > Hmm, is the order guaranteed? I haven't found anything in the > Emacs Lisp manual about this, so maybe just leave out the > parenthetical remark or say that the order is unspecified? Good question! But it's not just the parenthetical part. If we couldn't say anything about the traversal order of `maphash' then the whole sentence would need to go. FWIW, I think it's pretty important. Order is quite important for alists, generally. Is there some reason we should not be able to count on this `maphash' behavior? That's the behavior I saw, AFAICT, but I didn't test much. I don't know whether it is guaranteed, but this use case involving conversion to alist looks like a good argument for some guarantee wrt order. I see that in Common Lisp nothing is said about the traversal by `maphash' over the hash table. This is all that is said: "For each entry in hash-table, maphash calls function on two arguments: the key of the entry and the value of the entry; maphash then returns nil. If entries are added to or deleted from the hash table while a maphash is in progress, the results are unpredictable, with one exception: if the function calls remhash to remove the entry currently being processed by the function, or performs a setf of gethash on that entry to change the associated value, then those operations will have the intended effect." - https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node155.html (Emacs doc should also probably say at least something about what happens when entries are added/removed during a `maphash' application.) If Emacs decides not to guarantee the order seen now, which I think is the order I described in the doc string above, then we would need to remove that sentence. That would be too bad for users of function `hash-table-to-alist', but at least they would, at least so far (and AFAICT), get that behavior, which is likely to be expected by them even if it is not documented. Another possibility (?): Allow _optional_ creation of a hash table that does preserve such ordering (even if just by recording order of entry and making that available to `maphash'). E.g., add a keyword arg for `make-hash-table' that does just that. Even if it turned out that this consistently or occasionally detracted from performance, it could be a useful option. Conversion to an alist would be a case in point.