weak dicts
[software/python-on-guile.git] / modules / language / python / dict.scm
1 (define-module (language python dict)
2 #:use-module (language python list)
3 #:use-module (language python try)
4 #:use-module (language python hash)
5 #:use-module (language python yield)
6 #:use-module (language python def)
7 #:use-module (language python for)
8 #:use-module (language python exceptions)
9 #:use-module (language python persist)
10 #:use-module (ice-9 match)
11 #:use-module (ice-9 control)
12 #:use-module (oop goops)
13 #:use-module (oop pf-objects)
14 #:export (make-py-hashtable <py-hashtable>
15 py-copy py-fromkeys py-get py-has_key py-items py-iteritems
16 py-iterkeys py-itervalues py-keys py-values
17 py-popitem py-setdefault py-update py-clear
18 py-hash-ref dict pyhash-listing
19 weak-key-dict weak-value-dict
20 ))
21
22 (define-syntax-rule (aif it p x y) (let ((it p)) (if it x y)))
23
24 (define (h x n) (modulo (py-hash x) n))
25 (define (py-assoc k l)
26 (if (pair? l)
27 (if (equal? (caar l) k)
28 (car l)
29 (py-assoc k (cdr l)))
30 #f))
31
32 (define (py-hash-ref . l)
33 (apply hashx-ref h py-assoc l))
34 (define (py-hash-set! . l)
35 (apply hashx-set! h py-assoc l))
36 (define (py-hash-remove! . l)
37 (apply hashx-remove! h py-assoc l))
38
39 (set! (@@ (language python def) hset!) py-hash-set!)
40
41 (define H (hash 1333674836 complexity))
42
43 (define-class <py-hashtable> () t h n)
44
45 (name-object <py-hashtable>)
46
47 (cpit <py-hashtable>
48 (o (lambda (o h n a)
49 (slot-set! o 'h h)
50 (slot-set! o 'n n)
51 (slot-set! o 't
52 (let ((t (make-hash-table)))
53 (let lp ((a a))
54 (if (pair? a)
55 (begin
56 (py-hash-set! t (caar a) (cdar a))
57 (lp (cdr a)))))
58 t)))
59 (let ((t (slot-ref o 't)))
60 (list
61 (slot-ref o 'h)
62 (slot-ref o 'n)
63 (hash-fold (lambda (k v s) (cons (cons k v) s)) '() t)))))
64
65 (define (make-py-hashtable)
66 (let* ((o (make <py-hashtable>))
67 (t (make-hash-table))
68 (h H))
69 (slot-set! o 't t)
70 (slot-set! o 'h h)
71 (slot-set! o 'n 0)
72 o))
73
74 (define (make-py-weak-key-hashtable)
75 (let* ((o (make <py-hashtable>))
76 (t (make-weak-key-hash-table))
77 (h H))
78 (slot-set! o 't t)
79 (slot-set! o 'h h)
80 (slot-set! o 'n 0)
81 o))
82
83 (define (make-py-weak-value-hashtable)
84 (let* ((o (make <py-hashtable>))
85 (t (make-weak-value-hash-table))
86 (h H))
87 (slot-set! o 't t)
88 (slot-set! o 'h h)
89 (slot-set! o 'n 0)
90 o))
91
92 (define miss (list 'miss))
93 (define-method (pylist-ref (o <hashtable>) x)
94 (let ((r (py-hash-ref o x miss)))
95 (if (eq? r miss)
96 (raise KeyError x)
97 r)))
98
99 (define-method (pylist-ref (o <py-hashtable>) x)
100 (let ((r (py-hash-ref (slot-ref o 't) x miss)))
101 (if (eq? r miss)
102 (raise KeyError x)
103 r)))
104
105 (define-method (pylist-delete! (o <hashtable>) k)
106 (pyhash-rem! o k))
107
108 (define-method (pylist-delete! (o <py-hashtable>) k)
109 (pyhash-rem! o k))
110
111 (define-method (py-hash (o <hashtable>))
112 (hash-fold
113 (lambda (k v s)
114 (logxor
115 (xy (py-hash k) (py-hash v))
116 s))
117 0 o))
118
119 (define-method (py-hash (o <py-hashtable>))
120 (slot-ref o 'h))
121
122 (define-method (len (o <hashtable>))
123 (hash-fold (lambda (k v s) (+ s 1)) 0 o))
124
125 (define-method (len (o <py-hashtable>))
126 (slot-ref o 'n))
127
128 (define-method (pylist-pop! (o <hashtable>) k . l)
129 (match l
130 ((v)
131 (let ((ret (py-hash-ref o k v)))
132 (py-hash-remove! o k)
133 ret))
134 (()
135 (let ((ret (hash-ref o k miss)))
136 (if (eq? ret miss)
137 (raise KeyError k)
138 (begin
139 (hash-remove! o k)
140 ret))))))
141
142 (define-method (pyhash-rem! (o <hashtable>) k)
143 (py-hash-remove! o k)
144 (values))
145
146 (define-method (pyhash-rem! (o <py-hashtable>) k)
147 (let ((t (slot-ref o 't))
148 (n (slot-ref o 'n))
149 (h (slot-ref o 'h)))
150 (let ((ret (py-hash-ref t k miss)))
151 (if (eq? ret miss)
152 (values)
153 (begin
154 (py-hash-remove! t k)
155 (slot-set! o 'n (- n 1))
156 (slot-set! o 'h (logxor h (xy (py-hash k) (py-hash ret))))
157 (values))))))
158
159 (define-method (pylist-pop! (o <py-hashtable>) k . l)
160 (let ((t (slot-ref o 't)))
161 (match l
162 ((v)
163 (let ((ret (py-hash-ref t k miss)))
164 (if (eq? ret miss)
165 v
166 (begin
167 (pyhash-rem! o k)
168 ret))))
169 (()
170 (let ((ret (hash-ref o k miss)))
171 (if (eq? ret miss)
172 (raise KeyError k)
173 (begin
174 (pyhash-rem! o k)
175 ret)))))))
176
177 (define-method (pylist-set! (o <hashtable>) key val)
178 (py-hash-set! o key val)
179 (values))
180
181 (define-method (pylist-set! (o <py-hashtable>) key val)
182 (let ((t (slot-ref o 't))
183 (n (slot-ref o 'n))
184 (h (slot-ref o 'h)))
185 (let ((ret (py-hash-ref t key miss)))
186 (if (eq? ret miss)
187 (begin
188 (py-hash-set! t key val)
189 (slot-set! o 'n (+ n 1))
190 (slot-set! o 'h (logxor (xy (py-hash key) (py-hash val)) h)))
191 (begin
192 (py-hash-set! t key val)
193 (slot-set! o 'h
194 (logxor (xy (py-hash key) (py-hash val))
195 (logxor
196 (xy (py-hash key) (py-hash ret))
197 h)))))))
198 (values))
199
200 (define-syntax define-py
201 (syntax-rules ()
202 ((_ (nm n o l ...) (class code ...) ...)
203 (begin
204 (define-method (nm (o class) l ...) code ...)
205 ...
206 (define-method (nm (o <p>) l ...)
207 (aif it (ref o 'n)
208 (it l ...)
209 (next-method)))))
210 ((_ (nm n o l ... . u) (class code ...) ...)
211 (begin
212 (define-method (nm (o class) l ... . u) code ...)
213 ...
214 (define-method (nm (o <p>) l ... . u)
215 (aif it (ref o 'n)
216 (apply it l ... u)
217 (next-method)))))))
218
219
220
221 (define-py (py-copy copy o)
222 (<hashtable>
223 (hash-fold
224 (lambda (k v h)
225 (py-hash-set! h k v)
226 h)
227 (make-hash-table)
228 o))
229
230 (<py-hashtable>
231 (let ((r (make <py-hashtable>)))
232 (slot-set! r 'h (slot-ref o 'h))
233 (slot-set! r 'n (slot-ref o 'n))
234 (slot-set! r 't (py-copy (slot-ref o 't)))
235 r)))
236
237 (define-py (py-fromkeys fromkeys o . l)
238 (<hashtable>
239 (let ((newval (match l
240 (() None)
241 ((v) v))))
242 (hash-fold
243 (lambda (k v h)
244 (py-hash-set! h k newval)
245 h)
246 (make-hash-table)
247 o)))
248
249 (<py-hashtable>
250 (let ((newval (match l
251 (() None)
252 ((v) v))))
253 (hash-fold
254 (lambda (k v h)
255 (pylist-set! h k newval)
256 h)
257 (make-py-hashtable)
258 (slot-ref o 't)))))
259
260 (define-py (py-get get o k . l)
261 (<hashtable>
262 (let ((elseval (match l
263 (() None)
264 ((v) v))))
265 (let ((ret (py-hash-ref o k miss)))
266 (if (eq? ret miss)
267 elseval
268 ret))))
269
270 (<py-hashtable>
271 (let ((elseval (match l
272 (() None)
273 ((v) v))))
274 (let ((ret (py-hash-ref (slot-ref o 't) k miss)))
275 (if (eq? ret miss)
276 elseval
277 ret)))))
278
279 (define-py (py-has_key has_key o k . l)
280 (<hashtable>
281 (let ((elseval (match l
282 (() None)
283 ((v) v))))
284 (let ((ret (py-hash-ref o k miss)))
285 (if (eq? ret miss)
286 #f
287 #t))))
288
289 (<py-hashtable>
290 (let ((elseval (match l
291 (() None)
292 ((v) v))))
293 (let ((ret (py-hash-ref (slot-ref o 't) k miss)))
294 (if (eq? ret miss)
295 #f
296 #t)))))
297
298 (define-py (py-items items o)
299 (<hashtable>
300 (to-pylist
301 (hash-fold
302 (lambda (k v l)
303 (cons (list k v) l))
304 '() o)))
305
306 (<py-hashtable>
307 (to-pylist
308 (hash-fold
309 (lambda (k v l)
310 (cons (list k v) l))
311 '() (slot-ref o 't)))))
312
313 (define-generator (hash-item-gen yield hash-table)
314 (let lp ((l (hash-fold cons* '() hash-table)))
315 (match l
316 ((k v . l)
317 (yield k v)
318 (lp l))
319 (()
320 #t))))
321
322 (define-generator (hash-values-gen yield hash-table)
323 (let lp ((l (hash-fold cons* '() hash-table)))
324 (match l
325 ((k v . l)
326 (yield v)
327 (lp l))
328 (()
329 #t))))
330
331 (define-generator (hash-keys-gen yield hash-table)
332 (let lp ((l (hash-fold cons* '() hash-table)))
333 (match l
334 ((k v . l)
335 (yield k)
336 (lp l))
337 (()
338 #t))))
339
340 (define-py (py-iteritems iteritems o)
341 (<hashtable>
342 (hash-item-gen o))
343
344 (<py-hashtable>
345 (hash-item-gen (slot-ref o 't))))
346
347 (define-py (py-iterkeys iterkeys o)
348 (<hashtable>
349 (hash-keys-gen o))
350
351 (<py-hashtable>
352 (hash-keys-gen (slot-ref o 't))))
353
354 (define-py (py-itervalues itervalues o)
355 (<hashtable>
356 (hash-values-gen o))
357
358 (<py-hashtable>
359 (hash-values-gen (slot-ref o 't))))
360
361 (define-py (py-keys keys o)
362 (<hashtable>
363 (to-pylist
364 (hash-fold
365 (lambda (k v l) (cons k l))
366 '()
367 o)))
368
369 (<py-hashtable>
370 (to-pylist
371 (hash-fold
372 (lambda (k v l) (cons k l))
373 '()
374 (slot-ref o 't)))))
375
376 (define-py (py-values values o)
377 (<hashtable>
378 (to-pylist
379 (hash-fold
380 (lambda (k v l) (cons v l))
381 '()
382 o)))
383
384 (<py-hashtable>
385 (to-pylist
386 (hash-fold
387 (lambda (k v l) (cons v l))
388 '()
389 (slot-ref o 't)))))
390
391 (define-py (py-popitem popitem o)
392 (<hashtable>
393 (let ((k.v (let/ec ret
394 (hash-for-each
395 (lambda (k v)
396 (ret (cons k v)))
397 o)
398 #f)))
399 (if k.v
400 (begin (pyhash-rem! o (car k.v)) k.v)
401 (raise KeyError "No elements in hash"))))
402
403 (<py-hashtable>
404 (let ((k.v (let/ec ret
405 (hash-for-each
406 (lambda (k v)
407 (ret (cons k v)))
408 (slot-ref o 't))
409 #f)))
410 (if k.v
411 (begin (pyhash-rem! o (car k.v)) k.v)
412 (raise KeyError "No elements in hash")))))
413
414 (define-py (py-setdefault setdefault o k . l)
415 (<hashtable>
416 (pylist-set! o k (apply py-get o k l)))
417 (<py-hashtable>
418 (pylist-set! o k (apply py-get o k l))))
419
420 (define update
421 (lam (o (* L) (** K))
422 (match L
423 ((L)
424 (for ((k v : L)) ()
425 (pylist-set! o k v)))
426 (_ #f))
427 (for ((k v : K)) ()
428 (pylist-set! o k v))))
429
430 (define-py (py-update update o . l)
431 (<hashtable>
432 (apply update o l))
433 (<py-hashtable>
434 (apply update o l)))
435
436 (define-py (py-clear clear o)
437 (<hashtable>
438 (hash-clear! o))
439 (<py-hashtable>
440 (let ((t (slot-ref o 't)))
441 (hash-clear! t)
442 (slot-set! o 'n 0)
443 (slot-set! o 'h H)
444 (values))))
445
446 #|
447 'viewitems'
448 'viewkeys'
449 'viewvalues'
450 |#
451
452 (define-syntax-rule (top <)
453 (begin
454 (define-method (< (o1 <hashtable>) (o2 <hashtable>))
455 (< (len o1) (len o2)))
456 (define-method (< (o1 <hashtable>) (o2 <py-hashtable>))
457 (< (len o1) (len o2)))
458 (define-method (< (o1 <py-hashtable>) (o2 <hashtable>))
459 (< (len o1) (len o2)))
460 (define-method (< (o1 <py-hashtable>) (o2 <py-hashtable>))
461 (< (len o1) (len o2)))))
462
463 (top <)
464 (top >)
465 (top <=)
466 (top >=)
467
468 (define (fold f s l)
469 (if (pair? l)
470 (f (car l) (fold f s (cdr l)))
471 s))
472
473 (define-method (write (o <py-hashtable>) . l)
474 (define port (match l (() #f) ((p) p)))
475 (define li (hash-fold cons* '() (slot-ref o 't)))
476 (if (null? li)
477 (format port "{}")
478 (format port "{~a: ~a~{, ~a: ~a~}}" (car li) (cadr li) (cddr li))))
479
480 (define-method (py-equal? (o1 <py-hashtable>) (o2 <py-hashtable>))
481 (and
482 (equal? (slot-ref o1 'n) (slot-ref o2 'n))
483 (equal? (slot-ref o1 'h) (slot-ref o2 'h))
484 (e? (slot-ref o1 't) (slot-ref o2 't))))
485
486 (define (e? t1 t2)
487 (let/ec ret
488 (hash-fold
489 (lambda (k v s)
490 (let ((r (py-hash-ref t2 k miss)))
491 (if (eq? r miss)
492 (ret #f)
493 (if (equal? r v)
494 #t
495 (ret #f)))))
496 #t
497 t1)))
498
499
500 (define-class <hashiter> () l)
501 (name-object <hashiter>)
502 (cpit <hashiter> (o (lambda (o l) (slot-set! o 'l l))
503 (list (slot-ref o 'l))))
504
505
506 (define-method (wrap-in (t <hashtable>))
507 (let ((o (make <hashiter>)))
508 (slot-set! o 'l (to-list (py-items t)))
509 o))
510
511 (define-method (wrap-in (t <py-hashtable>))
512 (let ((o (make <hashiter>)))
513 (slot-set! o 'l (to-list (py-items t)))
514 o))
515
516 (define-method (next (o <hashiter>))
517 (let ((l (slot-ref o 'l)))
518 (if (pair? l)
519 (let ((k (caar l))
520 (v (cadar l))
521 (l (cdr l)))
522 (slot-set! o 'l l)
523 (values k v))
524 (throw StopIteration))))
525
526
527 (define-method (in key (o <hashtable>))
528 (py-has_key o key))
529
530 (define-method (in key (o <py-hashtable>))
531 (py-has_key o key))
532
533 (define-python-class dict (<py-hashtable>)
534 (define __init__
535 (letrec ((__init__
536 (case-lambda
537 ((self)
538 (let ((r (make-py-hashtable)))
539 (slot-set! self 't (slot-ref r 't))
540 (slot-set! self 'h (slot-ref r 'h))
541 (slot-set! self 'n (slot-ref r 'n))))
542 ((self x)
543 (__init__ self)
544 (if (is-a? x <py-hashtable>)
545 (hash-for-each
546 (lambda (k v)
547 (pylist-set! self k v))
548 (slot-ref x 't)))))))
549 __init__)))
550 (name-object dict)
551
552 (define-python-class weak-key-dict (<py-hashtable>)
553 (define __init__
554 (letrec ((__init__
555 (case-lambda
556 ((self)
557 (let ((r (make-py-weak-key-hashtable)))
558 (slot-set! self 't (slot-ref r 't))
559 (slot-set! self 'h (slot-ref r 'h))
560 (slot-set! self 'n (slot-ref r 'n))))
561 ((self x)
562 (__init__ self)
563 (if (is-a? x <py-hashtable>)
564 (hash-for-each
565 (lambda (k v)
566 (pylist-set! self k v))
567 (slot-ref x 't)))))))
568 __init__)))
569 (name-object weak-key-dict)
570
571 (define-python-class weak-value-dict (<py-hashtable>)
572 (define __init__
573 (letrec ((__init__
574 (case-lambda
575 ((self)
576 (let ((r (make-py-weak-value-hashtable)))
577 (slot-set! self 't (slot-ref r 't))
578 (slot-set! self 'h (slot-ref r 'h))
579 (slot-set! self 'n (slot-ref r 'n))))
580 ((self x)
581 (__init__ self)
582 (if (is-a? x <py-hashtable>)
583 (hash-for-each
584 (lambda (k v)
585 (pylist-set! self k v))
586 (slot-ref x 't)))))))
587 __init__)))
588
589 (name-object weak-value-dict)
590
591 (define (pyhash-listing)
592 (let ((l (to-pylist
593 (map symbol->string
594 '(__class__ __cmp__ __contains__ __delattr__
595 __delitem__ __doc__ __eq__ __format__
596 __ge__ __getattribute__ __getitem__
597 __gt__ __hash__ __init__ __iter__
598 __le__ __len__ __lt__ __ne__ __new__
599 __reduce__ __reduce_ex__ __repr__
600 __setattr__ __setitem__ __sizeof__
601 __str__ __subclasshook__
602 clear copy fromkeys get has_key
603 items iteritems iterkeys itervalues
604 keys pop popitem setdefault update
605 values viewitems viewkeys viewvalues)))))
606 (pylist-sort! l)
607 l))
608
609
610 (define-method (py-class (o <hashtable>)) dict)
611 (define-method (py-class (o <py-hashtable>)) dict)