Permalink
Sep 5, 2014
Feb 1, 2020
Sep 5, 2014
Jul 21, 2020
Jul 21, 2020
May 17, 2019
Jul 21, 2020
May 17, 2019
May 17, 2019
May 17, 2019
May 17, 2019
Sep 5, 2014
Feb 1, 2020
Jan 15, 2018
Apr 3, 2019
Apr 3, 2019
Feb 1, 2020
Apr 3, 2019
Apr 3, 2019
Apr 3, 2019
Dec 13, 2018
Dec 21, 2018
Dec 21, 2018
Nov 6, 2019
Dec 21, 2018
Sep 5, 2014
Dec 10, 2018
Dec 10, 2018
Dec 21, 2018
Sep 5, 2014
Mar 7, 2018
Feb 26, 2018
Feb 1, 2020
Dec 21, 2018
Dec 21, 2018
Dec 21, 2018
Dec 21, 2018
Sep 5, 2014
Dec 10, 2018
Dec 10, 2018
Dec 10, 2018
Sep 5, 2014
Sep 5, 2014
Jul 30, 2020
Jul 14, 2020
Jul 31, 2018
Sep 5, 2014
Jul 31, 2018
Dec 10, 2018
Nov 2, 2018
Jul 31, 2018
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Jun 11, 2020
Dec 10, 2018
Dec 21, 2018
Sep 5, 2014
Sep 5, 2014
Jun 11, 2020
Apr 18, 2020
Sep 5, 2014
Jun 11, 2020
May 27, 2018
Apr 18, 2020
Feb 1, 2020
Dec 21, 2018
Feb 3, 2018
Feb 1, 2020
Jul 4, 2020
Jul 4, 2020
Jul 30, 2020
Jul 30, 2020
Dec 21, 2018
Dec 21, 2018
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Mar 7, 2018
Sep 5, 2014
Sep 5, 2014
Dec 21, 2018
Sep 5, 2014
Sep 5, 2014
Mar 7, 2018
Nov 9, 2015
May 17, 2019
Feb 26, 2018
Jul 21, 2020
Feb 26, 2018
Dec 13, 2018
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Sep 5, 2014
Mar 7, 2018
Sep 5, 2014
Dec 21, 2018
Sep 5, 2014
Mar 7, 2018
Feb 26, 2018
Apr 14, 2019
Dec 13, 2018
Sep 5, 2014
Sep 5, 2014
May 17, 2019
Feb 26, 2018
Jul 21, 2020
Dec 1, 2018
Sep 5, 2014
Sep 5, 2014
Jun 29, 2020
Jun 28, 2018
May 16, 2020
May 16, 2020
Feb 1, 2020
Mar 7, 2018
Aug 2, 2018
Feb 26, 2018
Sep 5, 2014
Newer
100644
1212 lines (1095 sloc)
35.9 KB
1
;(function($B){
2
3
/*
4
Implementation of Python dictionaries
5
6
We can't use Javascript's Map here, because the behaviour is not exactly the
7
same (eg with keys that are instances of classes with a __hash__ method...)
8
and because Map is much slower than regular Javascript objects.
9
10
A Python dictionary is implemented as a Javascript objects with these
11
attributes:
12
. $version: an integer with an initial value of 0, incremented at each
13
insertion
14
. $numeric_dict: for keys of type int
15
. $string_dict and $str_hash: for keys of type str
16
. $object_dict: for keys of other types
17
18
The value associated to a key in $numeric_dict and $string_dict is a pair
19
[value, rank] where "value" is the value associated with the key and "rank"
20
is the value of the dict attribute $version when the pair is inserted. This
21
is required to keep track of the insertion order, mandatory since Python 3.7.
22
23
For keys that are not str or int, their hash value is computed. Since several
33
34
var set_ops = ["eq", "le", "lt", "ge", "gt",
35
"sub", "rsub", "and", "or", "xor"]
36
37
// methods to compare non set-like views
38
function is_sublist(t1, t2){
39
// Return true if all elements of t1 are in t2
40
for(var i = 0, ilen = t1.length; i < ilen; i++){
41
var x = t1[i],
42
flag = false
43
for(var j = 0, jlen = t2.length; j < jlen; j++){
44
if($B.rich_comp("__eq__", x, t2[j])){
45
t2.splice(j, 1)
46
flag = true
47
break
48
}
49
}
50
if(! flag){
51
return false
52
}
53
}
54
return true
55
}
56
57
dict_view_op = {
58
__eq__: function(t1, t2){
59
return t1.length == t2.length && is_sublist(t1, t2)
60
},
61
__ne__: function(t1, t2){
62
return ! dict_view_op.__eq__(t1, t2)
63
},
64
__lt__: function(t1, t2){
65
return t1.length < t2.length && is_sublist(t1, t2)
66
},
67
__gt__: function(t1, t2){
68
return dict_view_op.__lt__(t2, t1)
69
},
70
__le__: function(t1, t2){
71
return t1.length <= t2.length && is_sublist(t1, t2)
72
},
73
__ge__: function(t1, t2){
74
return dict_view_op.__le__(t2, t1)
75
},
76
__and__: function(t1, t2){
77
var items = []
78
for(var i = 0, ilen = t1.length; i < ilen; i++){
79
var x = t1[i]
80
flag = false
81
for(var j = 0, jlen = t2.length; j < jlen; j++){
82
if($B.rich_comp("__eq__", x, t2[j])){
83
t2.splice(j, 1)
84
items.push(x)
85
break
86
}
87
}
88
}
89
return items
90
},
91
__or__: function(t1, t2){
92
var items = t1
93
for(var j = 0, jlen = t2.length; j < jlen; j++){
94
var y = t2[j],
95
flag = false
96
for(var i = 0, ilen = t1.length; i < ilen; i++){
97
if($B.rich_comp("__eq__", y, t1[i])){
98
t2.splice(j, 1)
99
flag = true
100
break
101
}
102
}
103
if(! flag){
104
items.push(y)
105
}
106
}
107
return items
108
}
110
}
111
112
$B.make_view = function(name){
113
var klass = $B.make_class(name, function(items, set_like){
121
}
122
})
123
124
for(var i = 0, len = set_ops.length; i < len; i++){
125
var op = "__" + set_ops[i] + "__"
126
klass[op] = (function(op){
127
return function(self, other){
128
// compare set of items to other
129
if(self.set_like){
130
return _b_.set[op](_b_.set.$factory(self),
131
_b_.set.$factory(other))
132
}else{
133
// Non-set like views can only be compared to
134
// instances of the same class
135
if(other.__class__ !== klass){
136
return false
137
}
138
var other_items = _b_.list.$factory(other)
139
return dict_view_op[op](self.items, other_items)
140
}
141
}
142
})(op)
143
}
144
klass.__iter__ = function(self){
145
var it = klass.$iterator.$factory(self.items)
146
it.len_func = self.len_func
147
return it
148
}
154
klass.__repr__ = function(self){
155
return klass.$infos.__name__ + '(' + _b_.repr(self.items) + ')'
156
}
157
159
return klass
160
}
161
162
// Special version of __next__ for iterators on dict keys / values / items.
163
// Checks that the dictionary size didn't change during iteration.
164
function dict_iterator_next(self){
165
if(self.len_func() != self.len){
167
}
168
self.counter++
169
if(self.counter < self.items.length){
170
return self.items[self.counter]
171
}
172
throw _b_.StopIteration.$factory("StopIteration")
173
}
174
184
}
185
186
dict.$to_obj = function(d){
187
// Function applied to dictionary that only have string keys,
188
// return a Javascript objects with the kays mapped to the value,
189
// excluding the insertion rank
190
var res = {}
191
for(var key in d.$string_dict){
192
res[key] = d.$string_dict[key][0]
193
}
194
return res
195
}
196
206
if(val === undefined){val = _b_.NotImplemented}
207
else if(val === null){val = $N}
212
for(var k in d.$numeric_dict){
213
items.push([parseFloat(k), d.$numeric_dict[k]])
214
}
218
for(var k in d.$object_dict){
219
d.$object_dict[k].forEach(function(item){
220
items.push(item)
221
})
222
}
223
// sort by insertion order
224
items.sort(function(a, b){
225
return a[1][1] - b[1][1]
226
})
227
items = items.map(function(item){return [item[0], item[1][0]]})
229
if(ix !== undefined){
230
return items.map(function(item){return item[ix]})
231
}else{
232
items.__class__ = _b_.tuple
233
return items.map(function(item){
234
item.__class__ = _b_.tuple; return item}
235
)
236
}
239
$B.dict_to_list = to_list // used in py_types.js
240
241
// Special version of __next__ for iterators on dict keys / values / items.
242
// Checks that the dictionary size didn't change during iteration.
243
function dict_iterator_next(self){
244
if(self.len_func() != self.len){
246
}
247
self.counter++
248
if(self.counter < self.items.length){
249
return self.items[self.counter]
260
si(left, _l[i][0], _l[i][1])
261
if(right.$version != right_version){
262
throw _b_.RuntimeError.$factory("dict mutated during update")
263
}
264
}
267
function rank(self, hash, key){
268
// Search if object key, with hash = hash(key), is in
269
// self.$object_dict
270
var pairs = self.$object_dict[hash]
271
if(pairs !== undefined){
272
for(var i = 0, len = pairs.length; i < len; i++){
273
if($B.rich_comp("__eq__", key, pairs[i][0])){
274
return i
275
}
276
}
277
}
278
return -1
279
}
280
289
var $ = $B.args("__contains__", 2, {self: null, key: null},
290
["self", "key"], arguments, {}, null, null),
293
if(self.$is_namespace){key = $B.to_alias(key)} // issue 1244
294
295
if(self.$jsobj){
296
return self.$jsobj[key] !== undefined
297
}
303
return self.$numeric_dict[key] !== undefined
304
}
305
306
var hash = _b_.hash(key)
307
if(self.$str_hash[hash] !== undefined &&
308
$B.rich_comp("__eq__", key, self.$str_hash[hash])){return true}
309
if(self.$numeric_dict[hash] !== undefined &&
310
$B.rich_comp("__eq__", key, hash)){return true}
311
return rank(self, hash, key) > -1
312
}
313
316
var $ = $B.args("__eq__", 2, {self: null, arg: null},
317
["self", "arg"], arguments, {}, null, null),
326
switch(typeof arg){
327
case "string":
328
if(self.$string_dict[arg] === undefined){
348
if((ix = rank(self, hash, arg)) > -1){
349
self.$object_dict[hash].splice(ix, 1)
350
}else{
356
}
357
359
var $ = $B.args("__eq__", 2, {self: null, other: null},
360
["self", "other"], arguments, {}, null, null),
366
if(self.$jsobj){self = jsobj2dict(self.$jsobj)}
367
if(other.$jsobj){other = jsobj2dict(other.$jsobj)}
378
if(!$B.rich_comp("__eq__", other.$numeric_dict[k][0],
379
self.$numeric_dict[k][0])){
383
var pairs = other.$object_dict[k],
384
flag = false
385
for(var i = 0, len = pairs.length; i < len; i++){
386
if($B.rich_comp("__eq__", k, pairs[i][0]) &&
387
$B.rich_comp("__eq__", self.$numeric_dict[k],
388
pairs[i][1])){
389
flag = true
390
break
391
}
406
var pairs = self.$object_dict[hash]
407
// Get all (key, value) pairs in other that have the same hash
408
var other_pairs = []
409
if(other.$numeric_dict[hash] !== undefined){
410
other_pairs.push([hash, other.$numeric_dict[hash]])
411
}
413
other_pairs = other_pairs.concat(other.$object_dict[hash])
414
}
415
if(other_pairs.length == 0){
416
return false
417
}
418
for(var i = 0, len_i = pairs.length; i < len_i; i++){
419
var flag = false
420
var key = pairs[i][0],
422
for(var j = 0, len_j = other_pairs.length; j < len_j; j++){
423
if($B.rich_comp("__eq__", key, other_pairs[j][0]) &&
435
}
436
438
var $ = $B.args("__getitem__", 2, {self: null, arg: null},
439
["self", "arg"], arguments, {}, null, null),
455
456
switch(typeof arg){
457
case "string":
458
if(self.$string_dict[arg] !== undefined){
466
break
467
}
468
469
// since the key is more complex use 'default' method of getting item
470
508
}
509
511
525
if(item[0] != 0 && item[0] != 1){
526
self.$numeric_dict[item[0]] = [item[1], self.$order++]
527
self.$version++
528
break
529
}
542
for(var key in first){
543
self.$string_dict[key] = [first[key], self.$order++]
544
}
545
return _b_.None
546
}else if(first.$jsobj){
547
self.$jsobj = {}
548
for(var attr in first.$jsobj){
549
self.$jsobj[attr] = first.$jsobj[attr]
555
}
559
arguments, {}, "first", "second")
560
var args = $.first
561
if(args.length > 1){
562
throw _b_.TypeError.$factory("dict expected at most 1 argument" +
563
", got 2")
564
}else if(args.length == 1){
565
args = args[0]
566
if(args.__class__ === dict){
567
['$string_dict', '$str_hash', '$numeric_dict', '$object_dict'].
568
forEach(function(d){
569
for(key in args[d]){self[d][key] = args[d][key]}
570
})
574
var keys = $B.$getattr(args, "keys", null)
575
if(keys !== null){
576
var gi = $B.$getattr(args, "__getitem__", null)
577
if(gi !== null){
578
// has keys and __getitem__ : it's a mapping, iterate on
579
// keys and values
580
gi = $B.$call(gi)
581
var kiter = _b_.iter($B.$call(keys)())
582
while(true){
583
try{
584
var key = _b_.next(kiter),
585
value = gi(key)
586
dict.__setitem__(self, key, value)
587
}catch(err){
588
if(err.__class__ === _b_.StopIteration){
589
break
590
}
591
throw err
592
}
593
}
594
return $N
595
}
596
}
597
if(! Array.isArray(args)){
598
args = _b_.list.$factory(args)
599
}
600
// Form "dict([[key1, value1], [key2,value2], ...])"
602
}
620
}
621
624
}
625
626
dict.__ior__ = function(self, other){
627
// PEP 584
628
dict.update(self, other)
629
return self
630
}
631
640
for(var k in self.$numeric_dict){_count++}
641
for(var k in self.$string_dict){_count++}
642
for(var hash in self.$object_dict){
643
_count += self.$object_dict[hash].length
644
}
648
650
670
dict.__or__ = function(self, other){
671
// PEP 584
672
if(! _b_.isinstance(other, dict)){
673
return _b_.NotImplemented
674
}
675
var res = dict.copy(self)
676
dict.update(res, other)
677
return res
678
}
679
690
try{
691
res.push(repr(item[0]) + ": " + repr(item[1]))
692
}catch(err){
693
throw err
694
}
698
}
699
700
dict.__ror__ = function(self, other){
701
// PEP 584
702
if(! _b_.isinstance(other, dict)){
703
return _b_.NotImplemented
704
}
705
var res = dict.copy(other)
706
dict.update(res, self)
707
return res
708
}
709
712
["self", "key", "value"], arguments, {}, null, null)
713
return dict.$setitem($.self, $.key, $.value)
714
}
719
// If key is a string, set:
720
// - $string_dict[key] = [value, order] where "order" is an auto-increment
721
// unique id to keep track of insertion order
722
// - $str_hash[hash(key)] to key
723
//
724
// If key is a number, set $numeric_dict[key] = value
725
//
726
// If key is another object, compute its hash value:
727
// - if the hash is a key of $str_hash, and key == $str_hash[hash],
728
// replace $string_dict[$str_hash[hash]] by value
729
// - if the hash is a key of $numeric_dict, and hash == key, replace
730
// $numeric_dict[hash] by value
731
// - if the hash is a key of $object_dict: $object_dict[hash] is a list
732
// of [k, v] pairs. If key is equal to one of the "k", replace the
733
// matching v by value. Otherwise, add [key, value] to the list
734
// - else set $object_dict[hash] = [[key, value]]
735
//
736
// In all cases, increment attribute $version, used to detect dictionary
739
// Parameter $hash is only set if this method is called by setdefault.
740
// In this case the hash of key has already been computed and we
741
// know that the key is not present in the dictionary, so it's no
742
// use computing hash(key) again, nor testing equality of keys
751
// If class attribute __init__ or __new__ are reset,
752
// the factory function has to change
753
self.$jsobj.$factory = $B.$instance_creator(self.$jsobj)
754
}
755
}else{
763
if(self.$string_dict === undefined){
764
console.log("pas de string dict", self, key, value)
765
}
766
if(self.$string_dict[key] !== undefined){
767
self.$string_dict[key][0] = value
768
}else{
769
self.$string_dict[key] = [value, self.$order++]
770
self.$str_hash[str_hash(key)] = key
771
self.$version++
772
}
775
if(self.$numeric_dict[key] !== undefined){
776
// existing key: preserve order
777
self.$numeric_dict[key][0] = value
778
}else{
779
// special case for 0 and 1 if True or False are keys
780
var done = false
781
if((key == 0 || key == 1) &&
782
self.$object_dict[key] !== undefined){
783
for(const item of self.$object_dict[key]){
784
if((key == 0 && item[0] === false) ||
785
(key == 1 && item[0] === true)){
786
// replace value
787
item[1][0] = value
788
done = true
789
}
790
}
791
}
792
if(! done){
793
// new key
794
self.$numeric_dict[key] = [value, self.$order++]
795
}
799
case "boolean":
800
// true replaces 1 and false replaces 0
801
var num = key ? 1 : 0
802
if(self.$numeric_dict[num] !== undefined){
803
var order = self.$numeric_dict[num][1] // preserve order
804
self.$numeric_dict[num] = [value, order]
805
return
806
}
807
if(self.$object_dict[num] !== undefined){
808
self.$object_dict[num].push([key, [value, self.$order++]])
809
}else{
810
self.$object_dict[num] = [[key, [value, self.$order++]]]
811
}
831
// If $setitem is called from setdefault, don't test equality of key
832
// with any object
833
if($hash){
834
if(self.$object_dict[$hash] !== undefined){
838
}
839
self.$version++
840
return $N
841
}
842
var ix = rank(self, hash, key)
843
if(ix > -1){
844
// reset value
855
}
856
860
861
// add "reflected" methods
863
865
// Remove all items from the dictionary.
885
}
886
888
// Return a shallow copy of the dictionary
894
return res
895
}
896
899
var $ = $B.args("fromkeys", 3, {cls: null, keys: null, value: null},
900
["cls", "keys", "value"], arguments, {value: _b_.None}, null, null),
904
// class method
909
while(1){
910
try{
911
var key = _b_.next(keys_iter)
912
if(klass === dict){dict.$setitem(res, key, value)}
913
else{$B.$getattr(res, "__setitem__")(key, value)}
914
}catch(err){
916
return res
917
}
918
throw err
919
}
920
}
921
}
922
924
var $ = $B.args("get", 3, {self: null, key: null, _default: null},
925
["self", "key", "_default"], arguments, {_default: $N}, null, null)
928
catch(err){
929
if(_b_.isinstance(err, _b_.KeyError)){return $._default}
930
else{throw err}
931
}
932
}
933
934
var dict_items = $B.make_view("dict_items", true)
935
dict_items.$iterator = $B.make_iterator_class("dict_itemiterator")
939
var _len = arguments.length - 1,
940
_msg = "items() takes no arguments (" + _len + " given)"
943
var items = to_list(self),
944
set_like = true
945
// Check if all values are hashable
946
for(var i = 0, len = items.length; i < len; i++){
947
try{
948
_b_.hash(items[i][1])
949
}catch(err){
950
set_like = false
951
break
952
}
953
}
954
var it = dict_items.$factory(to_list(self), set_like)
964
var _len = arguments.length - 1,
965
_msg = "keys() takes no arguments (" + _len + " given)"
975
var missing = {},
976
$ = $B.args("pop", 3, {self: null, key: null, _default: null},
977
["self", "key", "_default"], arguments, {_default: missing}, null, null),
982
try{
985
return res
986
}catch(err){
989
throw err
990
}
991
throw err
992
}
993
}
994
1005
}
1006
1009
var $ = $B.args("setdefault", 3, {self: null, key: null, _default: null},
1010
["self", "key", "_default"], arguments, {_default: $N}, null, null),
1016
catch(err){
1021
var hash = key.$hash
1022
key.$hash = undefined
1023
dict.$setitem(self, key, _default, hash)
1024
return _default
1025
}
1026
}
1027
1030
var $ = $B.args("update", 1, {"self": null}, ["self"], arguments,
1031
{}, "args", "kw"),
1032
self = $.self,
1033
args = $.args,
1034
kw = $.kw
1035
if(args.length > 0){
1036
var o = args[0]
1043
var _keys = _b_.list.$factory($B.$call($B.$getattr(o, "keys"))())
1044
for(var i = 0, len = _keys.length; i < len; i++){
1046
dict.$setitem(self, _keys[i], _value)
1047
}
1048
}else{
1049
var it = _b_.iter(o),
1050
i = 0
1051
while(true){
1052
try{
1053
var item = _b_.next(it)
1054
}catch(err){
1055
if(err.__class__ === _b_.StopIteration){break}
1056
throw err
1057
}
1058
try{
1059
key_value = _b_.list.$factory(item)
1060
}catch(err){
1061
throw _b_.TypeError.$factory("cannot convert dictionary" +
1062
" update sequence element #" + i + " to a sequence")
1063
}
1064
if(key_value.length !== 2){
1065
throw _b_.ValueError.$factory("dictionary update " +
1066
"sequence element #" + i + " has length " +
1067
key_value.length + "; 2 is required")
1068
}
1069
dict.$setitem(self, key_value[0], key_value[1])
1070
i++
1073
}
1077
}
1078
1079
var dict_values = $B.make_view("dict_values")
1080
dict_values.$iterator = $B.make_iterator_class("dict_valueiterator")
1084
var _len = arguments.length - 1,
1085
_msg = "values() takes no arguments (" + _len + " given)"
1088
var values = to_list(self, 1)
1089
var it = dict_values.$factory(to_list(self, 1), false)
1096
var args = [res]
1097
for(var i = 0, len = arguments.length; i < len ; i++){
1098
args.push(arguments[i])
1099
}
1100
dict.__init__.apply(null, args)
1101
return res
1102
}
1104
_b_.dict = dict
1108
$B.empty_dict = function(){
1109
return {
1110
__class__: dict,
1111
$numeric_dict : {},
1112
$object_dict : {},
1113
$string_dict : {},
1114
$str_hash: {},
1120
// This must be done after set_func_names, otherwise dict.fromkeys doesn't
1121
// have the attribute $infos
1122
dict.fromkeys = _b_.classmethod.$factory(dict.fromkeys)
1123
1124
$B.getset_descriptor = $B.make_class("getset_descriptor",
1125
function(klass, attr){
1126
return {
1127
__class__: $B.getset_descriptor,
1129
cls: klass,
1130
attr: attr
1131
}
1132
}
1133
)
1134
1135
$B.getset_descriptor.__repr__ = $B.getset_descriptor.__str__ = function(self){
1136
return `<attribute '${self.attr}' of '${self.cls.$infos.__name__}' objects>`
1137
}
1138
1139
$B.set_func_names($B.getset_descriptor, "builtins")
1140
1145
// obj is a dictionary, with $string_dict table such that
1146
// obj.$string_dict[key] = [value, rank]
1147
// Transform it into an object with attribute $jsobj such that
1148
// res.$jsobj[key] = value
1149
var res = $B.obj_dict(dict.$to_obj(obj))
1159
throw _b_.TypeError.$factory("'mappingproxy' object does not support " +
1160
"item assignment")
1163
for(var attr in dict){
1164
if(mappingproxy[attr] !== undefined ||
1165
["__class__", "__mro__", "__new__", "__init__", "__delitem__",
1166
"clear", "fromkeys", "pop", "popitem", "setdefault",
1167
"update"].indexOf(attr) > -1){
1168
continue
1169
}
1170
if(typeof dict[attr] == "function"){
1171
mappingproxy[attr] = (function(key){
1172
return function(){
1173
return dict[key].apply(null, arguments)
1174
}
1175
})(attr)
1176
}else{
1177
mappingproxy[attr] = dict[attr]
1178
}
1179
}
1180
1203
if(klass !== undefined && klass.$native){
1204
throw _b_.AttributeError.$factory(klass.__name__ +
1212
})(__BRYTHON__)