From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Daniel Mendler via "Emacs development discussions." Newsgroups: gmane.emacs.devel Subject: Re: Add a function for building sort predicates Date: Thu, 01 Feb 2024 18:19:47 +0100 Message-ID: <87eddw9k5o.fsf@daniel-mendler.de> References: <87msskw1u8.fsf@web.de> Reply-To: Daniel Mendler Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="20367"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Emacs Development To: Michael Heerdegen Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Feb 01 18:20:24 2024 Return-path: Envelope-to: ged-emacs-devel@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 1rVajf-00056m-Gr for ged-emacs-devel@m.gmane-mx.org; Thu, 01 Feb 2024 18:20:23 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rVajF-0001Ue-7F; Thu, 01 Feb 2024 12:19:57 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rVajD-0001UD-5c for emacs-devel@gnu.org; Thu, 01 Feb 2024 12:19:55 -0500 Original-Received: from server.qxqx.de ([2a01:4f8:c012:9177::1] helo=mail.qxqx.de) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1rVaj9-000470-NE for emacs-devel@gnu.org; Thu, 01 Feb 2024 12:19:54 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=daniel-mendler.de; s=key; h=Content-Type:MIME-Version:Message-ID:Date: References:In-Reply-To:Subject:Cc:To:From:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=k4/0Bxn+MgwG6pXyXSoAynTswADpG4CNUofCuRARbu0=; b=EgjZcf2fAd+P+4Q1ci4YhkcB1G D3oyOoVXf1jC2gjvqvm7mIJ53Q0/gpemDShrxp9zE3EuIg83dsnH6tdMMXfwytcNz/145i2Lo4dQ0 L9iFSoNQhRLxrLz38DA1MsUCk+Q7SGCsK9zkWQH99dFOcAzlEKkcEY6ftewv7m9ljJtk=; In-Reply-To: <87msskw1u8.fsf@web.de> (Michael Heerdegen's message of "Thu, 01 Feb 2024 18:06:55 +0100") Received-SPF: pass client-ip=2a01:4f8:c012:9177::1; envelope-from=mail@daniel-mendler.de; helo=mail.qxqx.de X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:315706 Archived-At: Michael Heerdegen writes: > Hello, > > I looked at how "package.el" defines the sort predicates for the used > tabulated list view - for example, `package-menu--status-predicate': > > #+begin_src emacs-lisp > (defun package-menu--status-predicate (A B) > "Predicate to sort \"*Packages*\" buffer by the status column. > This is used for `tabulated-list-format' in `package-menu-mode'." > (let ((sA (aref (cadr A) 2)) > (sB (aref (cadr B) 2))) > (cond ((string= sA sB) > (package-menu--name-predicate A B)) > ((string= sA "new") t) > ((string= sB "new") nil) > ((string-prefix-p "avail" sA) > (if (string-prefix-p "avail" sB) > (package-menu--name-predicate A B) > t)) > ((string-prefix-p "avail" sB) nil) > ((string= sA "installed") t) > ((string= sB "installed") nil) > ((string= sA "dependency") t) > ((string= sB "dependency") nil) > ((string= sA "source") t) > ((string= sB "source") nil) > ((string= sA "unsigned") t) > ... > (t (string< sA sB))))) > #+end_src > > > This is hard to read and maintain, 0% user configurable, and it's not > easy to add additional "layers", like, "sort packages with equal states > first by archive name, and only then by name". > > I want to suggest to add a function for defining sort predicates for > cases like these (especially having tabulated-list-mode in mind, but not > only - sorting is a common task). > > Here is what I would imagine: > > #+begin_src emacs-lisp > ;; -*- lexical-binding: t -*- > > (defun make-sort-pred (rules) > "Return a sort predicate according to the sort RULES. > The returned predicate will accept two arguments A and B. When > called, it will try RULES in order to decide whether A < B and > return non-nil in that case and nil when B <= A. When no rule can > decide whether A < B, the predicate will also return nil. > > RULES is a list of sort specifications using one of the formats > explained below. > > The allowed formats of the specification lists in RULES are: > > -- (KEYFUN PRED) > > This is like > > (lambda (a b) > (funcall PRED (funcall KEYFUN a) > (funcall KEYFUN b))) > > -- (KEYFUN EQUAL-TEST . KEYLIST) > > This spec allows to specify the order of keys explicitly when the > number of possible keys is small by specifying an accordingly > ordered KEYLIST directly. > > A test using this rule form will first call KEYFUN with the > arguments A and B to get K-A and K-B. Then, using the equality > test EQUAL-TEST, it is tested to which of the elements in KEYLIST > K-A and K-B are equal. It is decided whether A < B using the > natural order of the KEYLIST elements. Keys not found in KEYLIST > are treated it as if coming after all of its elements. Elements > for that KEYFUN yields `equal' values are considered > indistinguishable. > > -- (KEYFUN EQUAL-TEST GET-KEYLIST) > > This works exactly like the above spec - the only difference is > that GET-KEYLIST is either a symbol whose `symbol-value' will be > consulted, or a function accepting zero arguments to obtain the > KEYLIST to use, at run-time. In the latter case the function > should be accordingly cheap when called and avoid unnecessary > consing. > > > Example 1: Sort a list like this: > > ((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3) > (\"c\" 1) (\"a\" 2) (\"b\" 2)) > > first by the first element, then by the second: > > (sort \\='((\"c\" 2) (\"a\" 3) (\"b\" 1) (\"b\" 3) (\"c\" 3) > (\"c\" 1) (\"a\" 2) (\"b\" 2)) > (make-sort-pred `((,#'car ,#'string<) > (,#'cadr ,#'<)))) > > Example 2: Create a sort predicate suitable for sorting the list > of packages for M-x list-packages. We want to have all \"new\" > packages listed first, then all obsolete packages, according to > the following list: > > (defvar my-package-menu--status-sorting-order > \\='(\"new\" \"obsolete\" \"held\" \"external\" ...)) > > Package in the same category should be sorted by archive in a certain > order, and last by name: > > (defalias \\='my-package-menu--status-predicate > (make-sort-pred > `((,(lambda (x) (aref (cadr x) 2)) > ,#'string= my-package-menu--status-sorting-order) > (,(lambda (x) (package-desc-archive (car x))) > ,#'equal \"gnu\" \"nongnu\" \"melpa\" nil) > (,#'identity ,#'package-menu--name-predicate))))" > > (let ((result (make-symbol "result"))) > (cl-flet ((compare-with (test a b) > (cond > ((funcall test a b) (throw result t)) > ((funcall test b a) (throw result nil))))) > (let ((rules > ;; translate RULES to test functions > (mapcar > (pcase-lambda (`(,keyfun . ,rule)) > (if (cdr rule) > (let* ((test (car rule)) > (testfun (lambda (x y) > (funcall test y (funcall keyfun x)))) > (keys (cdr rule)) > (ckeys (car keys))) > (cl-flet ((keys (cond ((cdr keys) (lambda () keys)) > ((symbolp ckeys) > (lambda () (symbol-value ckeys))) > (t (lambda () (funcall ckeys)))))) > (lambda (a b) > (cl-block nil > (let ((keys (keys))) > (while keys > (let ((key (pop keys))) > (cond ((funcall testfun a key) > (if (funcall testfun b key) > (cl-return) > (throw result t))) > ((funcall testfun b key) > (throw result nil)))))))))) > (lambda (a b) > (compare-with > (car rule) > (funcall keyfun a) (funcall keyfun b))))) > rules))) > > (lambda (a b) > (catch result > ;; any rule throws 'result' when a (dolist (rule rules) (funcall rule a b)) > ;; no rule was able to decide - return nil for stable sorting > nil)))))) > #+end_src > > Running time is comparable witho the existing code. > > Would we want to add something like this? And to which library? I > would like to prepare a patch. That's a useful addition. Did you consider creating a macro, which will lead to a more efficient predicate, or is `make-sort-pred' intended to be used in scenarios with customizable predicate rules, such that the rules have to be processed at runtime? Daniel