* lisp/emacs-lisp/package.el (package--remove-hidden): Fix logic
[emacs.git] / lisp / gnus / registry.el
Commit [+]AuthorDateLineData
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +00001;;; registry.el --- Track and remember data items by various fields
2
1599688e Stefan Monnier2015-01-07 23:11:58 -05003;; Copyright (C) 2011-2015 Free Software Foundation, Inc.
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +00004
5;; Author: Teodor Zlatanov <tzz@lifelogs.com>
6;; Keywords: data
7
f872186f
GM
Glenn Morris2011-04-05 19:01:39 -07008;; This file is part of GNU Emacs.
9
10;; GNU Emacs is free software: you can redistribute it and/or modify
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +000011;; it under the terms of the GNU General Public License as published by
12;; the Free Software Foundation, either version 3 of the License, or
13;; (at your option) any later version.
14
f872186f Glenn Morris2011-04-05 19:01:39 -070015;; GNU Emacs is distributed in the hope that it will be useful,
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +000016;; but WITHOUT ANY WARRANTY; without even the implied warranty of
17;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18;; GNU General Public License for more details.
19
20;; You should have received a copy of the GNU General Public License
f872186f Glenn Morris2011-04-05 19:01:39 -070021;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +000022
23;;; Commentary:
24
25;; This library provides a general-purpose EIEIO-based registry
26;; database with persistence, initialized with these fields:
27
d20acfe0 Eric Abrahamsen2014-12-18 11:22:02 +000028;; version: a float
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +000029
83299b94 Katsumi Yamaoka2014-12-18 22:50:29 +000030;; max-size: an integer, default most-positive-fixnum
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +000031
d20acfe0 Eric Abrahamsen2014-12-18 11:22:02 +000032;; prune-factor: a float between 0 and 1, default 0.1
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +000033
34;; precious: a list of symbols
35
36;; tracked: a list of symbols
37
38;; tracker: a hashtable tuned for 100 symbols to track (you should
39;; only access this with the :lookup2-function and the
40;; :lookup2+-function)
41
42;; data: a hashtable with default size 10K and resize threshold 2.0
43;; (this reflects the expected usage so override it if you know better)
44
45;; ...plus methods to do all the work: `registry-search',
46;; `registry-lookup', `registry-lookup-secondary',
47;; `registry-lookup-secondary-value', `registry-insert',
48;; `registry-delete', `registry-prune', `registry-size' which see
49
50;; and with the following properties:
51
52;; Every piece of data has a unique ID and some general-purpose fields
53;; (F1=D1, F2=D2, F3=(a b c)...) expressed as an alist, e.g.
54
55;; ((F1 D1) (F2 D2) (F3 a b c))
56
57;; Note that whether a field has one or many pieces of data, the data
58;; is always a list of values.
59
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +000060;; The user decides which fields are "precious", F2 for example. When
61;; the registry is pruned, any entries without the F2 field will be
62;; removed until the size is :max-size * :prune-factor _less_ than the
63;; maximum database size. No entries with the F2 field will be removed
64;; at PRUNE TIME, which means it may not be possible to prune back all
65;; the way to the target size.
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +000066
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +000067;; When an entry is inserted, the registry will reject new entries if
68;; they bring it over the :max-size limit, even if they have the F2
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +000069;; field.
70
71;; The user decides which fields are "tracked", F1 for example. Any
72;; new entry is then indexed by all the tracked fields so it can be
73;; quickly looked up that way. The data is always a list (see example
74;; above) and each list element is indexed.
75
76;; Precious and tracked field names must be symbols. All other
77;; fields can be any other Emacs Lisp types.
78
79;;; Code:
80
f8fc0578
SM
Stefan Monnier2011-04-10 22:18:19 -030081(eval-when-compile (require 'cl))
82
6651c015
KY
Katsumi Yamaoka2012-07-02 00:48:41 +000083(require 'eieio)
84(require 'eieio-base)
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +000085
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +000086;; The version number needs to be kept outside of the class definition
87;; itself. The persistent-save process does *not* write to file any
88;; slot values that are equal to the default :initform value. If a
89;; database object is at the most recent version, therefore, its
90;; version number will not be written to file. That makes it
91;; difficult to know when a database needs to be upgraded.
92(defvar registry-db-version 0.2
93 "The current version of the registry format.")
94
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +000095(defclass registry-db (eieio-persistent)
96 ((version :initarg :version
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +000097 :initform nil
98 :type (or null float)
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +000099 :documentation "The registry version.")
d20acfe0 Eric Abrahamsen2014-12-18 11:22:02 +0000100 (max-size :initarg :max-size
b90f502c
SM
Stefan Monnier2015-03-11 11:00:25 -0400101 ;; EIEIO's :initform is not 100% compatible with CLOS in
102 ;; that if the form is an atom, it assumes it's constant
103 ;; value rather than an expression, so in order to get the value
104 ;; of `most-positive-fixnum', we need to use an
105 ;; expression that's not just a symbol.
106 :initform (symbol-value 'most-positive-fixnum)
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +0000107 :type integer
108 :custom integer
d20acfe0 Eric Abrahamsen2014-12-18 11:22:02 +0000109 :documentation "The maximum number of registry entries.")
652aa465
TZ
Teodor Zlatanov2011-05-13 04:12:37 +0000110 (prune-factor
111 :initarg :prune-factor
112 :initform 0.1
113 :type float
114 :custom float
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +0000115 :documentation "Prune to \(:max-size * :prune-factor\) less
116 than the :max-size limit. Should be a float between 0 and 1.")
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +0000117 (tracked :initarg :tracked
118 :initform nil
119 :type t
120 :documentation "The tracked (indexed) fields, a list of symbols.")
121 (precious :initarg :precious
122 :initform nil
123 :type t
124 :documentation "The precious fields, a list of symbols.")
125 (tracker :initarg :tracker
126 :type hash-table
127 :documentation "The field tracking hashtable.")
128 (data :initarg :data
129 :type hash-table
130 :documentation "The data hashtable.")))
131
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +0000132(defmethod initialize-instance :BEFORE ((this registry-db) slots)
133 "Check whether a registry object needs to be upgraded."
134 ;; Hardcoded upgrade routines. Version 0.1 to 0.2 requires the
135 ;; :max-soft slot to disappear, and the :max-hard slot to be renamed
136 ;; :max-size.
137 (let ((current-version
138 (and (plist-member slots :version)
139 (plist-get slots :version))))
140 (when (or (null current-version)
141 (eql current-version 0.1))
142 (setq slots
143 (plist-put slots :max-size (plist-get slots :max-hard)))
144 (setq slots
145 (plist-put slots :version registry-db-version))
146 (cl-remf slots :max-hard)
147 (cl-remf slots :max-soft))))
148
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200149(defmethod initialize-instance :AFTER ((this registry-db) slots)
150 "Set value of data slot of THIS after initialization."
151 (with-slots (data tracker) this
152 (unless (member :data slots)
153 (setq data
154 (make-hash-table :size 10000 :rehash-size 2.0 :test 'equal)))
155 (unless (member :tracker slots)
156 (setq tracker (make-hash-table :size 100 :rehash-size 2.0)))))
157
158(defmethod registry-lookup ((db registry-db) keys)
159 "Search for KEYS in the registry-db THIS.
58179cce Juanma Barranquero2011-11-16 13:34:47 +0100160Returns an alist of the key followed by the entry in a list, not a cons cell."
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500161 (let ((data (oref db data)))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200162 (delq nil
163 (mapcar
164 (lambda (k)
165 (when (gethash k data)
166 (list k (gethash k data))))
167 keys))))
168
169(defmethod registry-lookup-breaks-before-lexbind ((db registry-db) keys)
170 "Search for KEYS in the registry-db THIS.
58179cce Juanma Barranquero2011-11-16 13:34:47 +0100171Returns an alist of the key followed by the entry in a list, not a cons cell."
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500172 (let ((data (oref db data)))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200173 (delq nil
174 (loop for key in keys
175 when (gethash key data)
176 collect (list key (gethash key data))))))
177
178(defmethod registry-lookup-secondary ((db registry-db) tracksym
179 &optional create)
180 "Search for TRACKSYM in the registry-db THIS.
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +0000181When CREATE is not nil, create the secondary index hashtable if needed."
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200182 (let ((h (gethash tracksym (oref db :tracker))))
183 (if h
184 h
185 (when create
186 (puthash tracksym
187 (make-hash-table :size 800 :rehash-size 2.0 :test 'equal)
6e1fac9b
EA
Eric Abrahamsen2015-03-21 23:59:30 +0000188 (oref db tracker))
189 (gethash tracksym (oref db tracker))))))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200190
191(defmethod registry-lookup-secondary-value ((db registry-db) tracksym val
192 &optional set)
193 "Search for TRACKSYM with value VAL in the registry-db THIS.
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +0000194When SET is not nil, set it for VAL (use t for an empty list)."
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200195 ;; either we're asked for creation or there should be an existing index
196 (when (or set (registry-lookup-secondary db tracksym))
197 ;; set the entry if requested,
198 (when set
199 (puthash val (if (eq t set) '() set)
200 (registry-lookup-secondary db tracksym t)))
201 (gethash val (registry-lookup-secondary db tracksym))))
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +0000202
203(defun registry--match (mode entry check-list)
204 ;; for all members
205 (when check-list
206 (let ((key (nth 0 (nth 0 check-list)))
207 (vals (cdr-safe (nth 0 check-list)))
208 found)
209 (while (and key vals (not found))
210 (setq found (case mode
211 (:member
212 (member (car-safe vals) (cdr-safe (assoc key entry))))
213 (:regex
214 (string-match (car vals)
215 (mapconcat
216 'prin1-to-string
217 (cdr-safe (assoc key entry))
218 "\0"))))
219 vals (cdr-safe vals)))
220 (or found
221 (registry--match mode entry (cdr-safe check-list))))))
222
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200223(defmethod registry-search ((db registry-db) &rest spec)
224 "Search for SPEC across the registry-db THIS.
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +0000225For example calling with :member '(a 1 2) will match entry '((a 3 1)).
226Calling with :all t (any non-nil value) will match all.
227Calling with :regex '\(a \"h.llo\") will match entry '((a \"hullo\" \"bye\").
228The test order is to check :all first, then :member, then :regex."
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200229 (when db
230 (let ((all (plist-get spec :all))
231 (member (plist-get spec :member))
232 (regex (plist-get spec :regex)))
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500233 (loop for k being the hash-keys of (oref db data)
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200234 using (hash-values v)
235 when (or
236 ;; :all non-nil returns all
237 all
238 ;; member matching
239 (and member (registry--match :member v member))
240 ;; regex matching
241 (and regex (registry--match :regex v regex)))
242 collect k))))
243
244(defmethod registry-delete ((db registry-db) keys assert &rest spec)
245 "Delete KEYS from the registry-db THIS.
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +0000246If KEYS is nil, use SPEC to do a search.
247Updates the secondary ('tracked') indices as well.
248With assert non-nil, errors out if the key does not exist already."
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500249 (let* ((data (oref db data))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200250 (keys (or keys
251 (apply 'registry-search db spec)))
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500252 (tracked (oref db tracked)))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200253
254 (dolist (key keys)
255 (let ((entry (gethash key data)))
256 (when assert
257 (assert entry nil
8abee653 Paul Eggert2013-07-15 21:39:23 -0700258 "Key %s does not exist in database" key))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200259 ;; clean entry from the secondary indices
260 (dolist (tr tracked)
261 ;; is this tracked symbol indexed?
262 (when (registry-lookup-secondary db tr)
263 ;; for every value in the entry under that key...
264 (dolist (val (cdr-safe (assq tr entry)))
265 (let* ((value-keys (registry-lookup-secondary-value
266 db tr val)))
267 (when (member key value-keys)
268 ;; override the previous value
269 (registry-lookup-secondary-value
270 db tr val
271 ;; with the indexed keys MINUS the current key
272 ;; (we pass t when the list is empty)
273 (or (delete key value-keys) t)))))))
274 (remhash key data)))
275 keys))
276
277(defmethod registry-size ((db registry-db))
278 "Returns the size of the registry-db object THIS.
35e2b6ab
SM
Stefan Monnier2015-03-06 23:50:32 -0500279This is the key count of the `data' slot."
280 (hash-table-count (oref db data)))
c7641e3c Glenn Morris2013-05-22 22:05:27 -0700281
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200282(defmethod registry-full ((db registry-db))
283 "Checks if registry-db THIS is full."
284 (>= (registry-size db)
6e1fac9b Eric Abrahamsen2015-03-21 23:59:30 +0000285 (oref db max-size)))
81d7704c Teodor Zlatanov2011-05-09 22:27:17 +0000286
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200287(defmethod registry-insert ((db registry-db) key entry)
288 "Insert ENTRY under KEY into the registry-db THIS.
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +0000289Updates the secondary ('tracked') indices as well.
290Errors out if the key exists already."
291
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500292 (assert (not (gethash key (oref db data))) nil
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200293 "Key already exists in database")
294
295 (assert (not (registry-full db))
296 nil
d20acfe0 Eric Abrahamsen2014-12-18 11:22:02 +0000297 "registry max-size limit reached")
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200298
299 ;; store the entry
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500300 (puthash key entry (oref db data))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200301
302 ;; store the secondary indices
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500303 (dolist (tr (oref db tracked))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200304 ;; for every value in the entry under that key...
305 (dolist (val (cdr-safe (assq tr entry)))
306 (let* ((value-keys (registry-lookup-secondary-value db tr val)))
307 (pushnew key value-keys :test 'equal)
308 (registry-lookup-secondary-value db tr val value-keys))))
309 entry)
310
311(defmethod registry-reindex ((db registry-db))
312 "Rebuild the secondary indices of registry-db THIS."
313 (let ((count 0)
35e2b6ab
SM
Stefan Monnier2015-03-06 23:50:32 -0500314 (expected (* (length (oref db tracked)) (registry-size db))))
315 (dolist (tr (oref db tracked))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200316 (let (values)
317 (maphash
318 (lambda (key v)
319 (incf count)
320 (when (and (< 0 expected)
321 (= 0 (mod count 1000)))
322 (message "reindexing: %d of %d (%.2f%%)"
323 count expected (/ (* 100 count) expected)))
324 (dolist (val (cdr-safe (assq tr v)))
325 (let* ((value-keys (registry-lookup-secondary-value db tr val)))
326 (push key value-keys)
327 (registry-lookup-secondary-value db tr val value-keys))))
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500328 (oref db data))))))
f38a45fa David Engster2013-06-02 16:16:31 +0200329
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +0000330(defmethod registry-prune ((db registry-db) &optional sortfunc)
331 "Prunes the registry-db object DB.
332
333Attempts to prune the number of entries down to \(*
334:max-size :prune-factor\) less than the max-size limit, so
335pruning doesn't need to happen on every save. Removes only
336entries without the :precious keys, so it may not be possible to
337reach the target limit.
338
339Entries to be pruned are first sorted using SORTFUNC. Entries
340from the front of the list are deleted first.
341
342Returns the number of deleted entries."
343 (let ((size (registry-size db))
5ba4fbd9
EA
Eric Abrahamsen2015-04-01 04:55:34 +0000344 (target-size
345 (floor (- (oref db max-size)
346 (* (oref db max-size)
347 (oref db prune-factor)))))
d20acfe0 Eric Abrahamsen2014-12-18 11:22:02 +0000348 candidates)
5ba4fbd9 Eric Abrahamsen2015-04-01 04:55:34 +0000349 (if (registry-full db)
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +0000350 (progn
351 (setq candidates
352 (registry-collect-prune-candidates
353 db (- size target-size) sortfunc))
354 (length (registry-delete db candidates nil)))
355 0)))
356
357(defmethod registry-collect-prune-candidates ((db registry-db) limit sortfunc)
358 "Collects pruning candidates from the registry-db object DB.
359
360Proposes only entries without the :precious keys, and attempts to
361return LIMIT such candidates. If SORTFUNC is provided, sort
362entries first and return candidates from beginning of list."
6e1fac9b Eric Abrahamsen2015-03-21 23:59:30 +0000363 (let* ((precious (oref db precious))
f38a45fa
DE
David Engster2013-06-02 16:16:31 +0200364 (precious-p (lambda (entry-key)
365 (cdr (memq (car entry-key) precious))))
35e2b6ab Stefan Monnier2015-03-06 23:50:32 -0500366 (data (oref db data))
d20acfe0
EA
Eric Abrahamsen2014-12-18 11:22:02 +0000367 (candidates (cl-loop for k being the hash-keys of data
368 using (hash-values v)
369 when (notany precious-p v)
370 collect (cons k v))))
371 ;; We want the full entries for sorting, but should only return a
372 ;; list of entry keys.
373 (when sortfunc
374 (setq candidates (sort candidates sortfunc)))
b8ea3aa9 Eric Abrahamsen2015-03-20 10:49:06 +0000375 (cl-subseq (mapcar #'car candidates) 0 (min limit (length candidates)))))
ccd58722 Ted Zlatanov2011-04-05 23:37:02 +0000376
ccd58722
TZ
Ted Zlatanov2011-04-05 23:37:02 +0000377(provide 'registry)
378;;; registry.el ends here