Permalink
Feb 1, 2020
Jul 21, 2020
Dec 28, 2020
Dec 28, 2020
Dec 28, 2020
May 17, 2019
Feb 1, 2020
Jan 15, 2018
Apr 3, 2019
Apr 3, 2019
Feb 1, 2020
Apr 3, 2019
Dec 13, 2018
Oct 5, 2020
Nov 6, 2019
Dec 10, 2018
Dec 10, 2018
Mar 7, 2018
Feb 26, 2018
Feb 1, 2020
Dec 10, 2018
Jan 29, 2021
Dec 28, 2020
Dec 10, 2018
Jan 29, 2021
Jul 30, 2020
Jul 14, 2020
Jul 31, 2018
Jul 31, 2018
Dec 10, 2018
Nov 2, 2018
Jul 31, 2018
Jun 11, 2020
Dec 10, 2018
Jun 11, 2020
Apr 18, 2020
Jun 11, 2020
May 27, 2018
Apr 18, 2020
Feb 1, 2020
Feb 3, 2018
Feb 1, 2020
Jul 4, 2020
Jul 4, 2020
Jul 30, 2020
Jul 30, 2020
Mar 7, 2018
Mar 7, 2018
Nov 9, 2015
May 17, 2019
Feb 26, 2018
Jul 21, 2020
Dec 28, 2020
Feb 26, 2018
Dec 28, 2020
Dec 13, 2018
Mar 7, 2018
Jan 29, 2021
Mar 7, 2018
Feb 26, 2018
Apr 14, 2019
Dec 13, 2018
May 17, 2019
Feb 26, 2018
Dec 28, 2020
Dec 1, 2018
Jun 29, 2020
Jun 28, 2018
May 16, 2020
May 16, 2020
Feb 1, 2020
Mar 7, 2018
Aug 2, 2018
Mar 16, 2021
Newer
100644
1239 lines (1118 sloc)
36.4 KB
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
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
}
125
for(var i = 0, len = set_ops.length; i < len; i++){
126
var op = "__" + set_ops[i] + "__"
127
klass[op] = (function(op){
128
return function(self, other){
129
// compare set of items to other
130
if(self.set_like){
131
return _b_.set[op](_b_.set.$factory(self),
132
_b_.set.$factory(other))
133
}else{
134
// Non-set like views can only be compared to
135
// instances of the same class
136
if(other.__class__ !== klass){
137
return false
139
var other_items = _b_.list.$factory(other)
140
return dict_view_op[op](self.items, other_items)
148
it.test_change = function(){
149
return self.dict.$version != self.dict_version
150
}
158
klass.__repr__ = function(self){
159
return klass.$infos.__name__ + '(' + _b_.repr(self.items) + ')'
160
}
161
178
dict.$to_obj = function(d){
179
// Function applied to dictionary that only have string keys,
180
// return a Javascript objects with the kays mapped to the value,
181
// excluding the insertion rank
182
var res = {}
183
for(var key in d.$string_dict){
184
res[key] = d.$string_dict[key][0]
185
}
186
return res
187
}
188
198
if(val === undefined){val = _b_.NotImplemented}
199
else if(val === null){val = $N}
204
for(var k in d.$numeric_dict){
205
items.push([parseFloat(k), d.$numeric_dict[k]])
206
}
212
for(var k in d.$object_dict){
213
d.$object_dict[k].forEach(function(item){
214
items.push(item)
215
})
216
}
218
// sort by insertion order
219
items.sort(function(a, b){
220
return a[1][1] - b[1][1]
221
})
222
items = items.map(function(item){return [item[0], item[1][0]]})
227
}else{
228
items.__class__ = _b_.tuple
229
return items.map(function(item){
230
item.__class__ = _b_.tuple; return item}
231
)
232
}
243
si(left, _l[i][0], _l[i][1])
244
if(right.$version != right_version){
245
throw _b_.RuntimeError.$factory("dict mutated during update")
246
}
247
}
250
function rank(self, hash, key){
251
// Search if object key, with hash = hash(key), is in
252
// self.$object_dict
253
var pairs = self.$object_dict[hash]
254
if(pairs !== undefined){
255
for(var i = 0, len = pairs.length; i < len; i++){
256
if($B.rich_comp("__eq__", key, pairs[i][0])){
257
return i
258
}
259
}
260
}
261
return -1
262
}
263
270
dict.__class_getitem__ = function(cls, item){
271
// PEP 585
272
// Set as a classmethod at the end of this script, after $B.set_func_names()
273
if(! Array.isArray(item)){
274
item = [item]
275
}
276
return $B.GenericAlias.$factory(cls, item)
277
}
278
281
var $ = $B.args("__contains__", 2, {self: null, key: null},
282
["self", "key"], arguments, {}, null, null),
285
if(self.$is_namespace){key = $B.to_alias(key)} // issue 1244
286
287
if(self.$jsobj){
288
return self.$jsobj[key] !== undefined
289
}
295
return self.$numeric_dict[key] !== undefined
296
}
297
298
var hash = _b_.hash(key)
299
if(self.$str_hash[hash] !== undefined &&
300
$B.rich_comp("__eq__", key, self.$str_hash[hash])){return true}
301
if(self.$numeric_dict[hash] !== undefined &&
302
$B.rich_comp("__eq__", key, hash)){return true}
303
return rank(self, hash, key) > -1
308
var $ = $B.args("__eq__", 2, {self: null, arg: null},
309
["self", "arg"], arguments, {}, null, null),
318
switch(typeof arg){
319
case "string":
320
if(self.$string_dict[arg] === undefined){
340
if((ix = rank(self, hash, arg)) > -1){
341
self.$object_dict[hash].splice(ix, 1)
342
}else{
351
var $ = $B.args("__eq__", 2, {self: null, other: null},
352
["self", "other"], arguments, {}, null, null),
358
if(self.$jsobj){self = jsobj2dict(self.$jsobj)}
359
if(other.$jsobj){other = jsobj2dict(other.$jsobj)}
370
if(!$B.rich_comp("__eq__", other.$numeric_dict[k][0],
371
self.$numeric_dict[k][0])){
375
var pairs = other.$object_dict[k],
376
flag = false
377
for(var i = 0, len = pairs.length; i < len; i++){
378
if($B.rich_comp("__eq__", k, pairs[i][0]) &&
379
$B.rich_comp("__eq__", self.$numeric_dict[k],
380
pairs[i][1])){
381
flag = true
382
break
383
}
398
var pairs = self.$object_dict[hash]
399
// Get all (key, value) pairs in other that have the same hash
400
var other_pairs = []
401
if(other.$numeric_dict[hash] !== undefined){
402
other_pairs.push([hash, other.$numeric_dict[hash]])
403
}
405
other_pairs = other_pairs.concat(other.$object_dict[hash])
406
}
407
if(other_pairs.length == 0){
408
return false
409
}
410
for(var i = 0, len_i = pairs.length; i < len_i; i++){
411
var flag = false
412
var key = pairs[i][0],
414
for(var j = 0, len_j = other_pairs.length; j < len_j; j++){
415
if($B.rich_comp("__eq__", key, other_pairs[j][0]) &&
430
var $ = $B.args("__getitem__", 2, {self: null, arg: null},
431
["self", "arg"], arguments, {}, null, null),
439
dict.$getitem = function(self, arg, ignore_missing){
440
// ignore_missing is only set in dict.setdefault
453
var x = self.$string_dict[arg]
454
if(x !== undefined){
455
$B.string_count++
456
return x[0]
464
break
465
}
466
467
// since the key is more complex use 'default' method of getting item
468
493
if(! ignore_missing){
494
if(self.__class__ !== dict && ! ignore_missing){
495
try{
496
var missing_method = getattr(self.__class__, "__missing__",
497
_b_.None)
498
}catch(err){
499
console.log(err)
518
if(item.length != 2){
519
throw _b_.ValueError.$factory("dictionary " +
520
`update sequence element #${i} has length 1; 2 is required`)
521
}
529
if(item[0] != 0 && item[0] != 1){
530
self.$numeric_dict[item[0]] = [item[1], self.$order++]
531
self.$version++
532
break
533
}
546
for(var key in first){
547
self.$string_dict[key] = [first[key], self.$order++]
548
}
549
return _b_.None
550
}else if(first.$jsobj){
551
self.$jsobj = {}
552
for(var attr in first.$jsobj){
553
self.$jsobj[attr] = first.$jsobj[attr]
563
arguments, {}, "first", "second")
564
var args = $.first
565
if(args.length > 1){
566
throw _b_.TypeError.$factory("dict expected at most 1 argument" +
567
", got 2")
568
}else if(args.length == 1){
569
args = args[0]
570
if(args.__class__ === dict){
571
['$string_dict', '$str_hash', '$numeric_dict', '$object_dict'].
572
forEach(function(d){
573
for(key in args[d]){self[d][key] = args[d][key]}
574
})
578
var keys = $B.$getattr(args, "keys", null)
579
if(keys !== null){
580
var gi = $B.$getattr(args, "__getitem__", null)
581
if(gi !== null){
582
// has keys and __getitem__ : it's a mapping, iterate on
583
// keys and values
584
gi = $B.$call(gi)
585
var kiter = _b_.iter($B.$call(keys)())
586
while(true){
587
try{
588
var key = _b_.next(kiter),
589
value = gi(key)
590
dict.__setitem__(self, key, value)
591
}catch(err){
592
if(err.__class__ === _b_.StopIteration){
593
break
594
}
595
throw err
596
}
597
}
598
return $N
599
}
600
}
601
if(! Array.isArray(args)){
602
args = _b_.list.$factory(args)
603
}
604
// Form "dict([[key1, value1], [key2,value2], ...])"
630
dict.__ior__ = function(self, other){
631
// PEP 584
632
dict.update(self, other)
633
return self
634
}
635
644
for(var k in self.$numeric_dict){_count++}
645
for(var k in self.$string_dict){_count++}
646
for(var hash in self.$object_dict){
647
_count += self.$object_dict[hash].length
648
}
674
dict.__or__ = function(self, other){
675
// PEP 584
676
if(! _b_.isinstance(other, dict)){
677
return _b_.NotImplemented
678
}
679
var res = dict.copy(self)
680
dict.update(res, other)
681
return res
682
}
683
684
function __newobj__(){
685
// __newobj__ is called with a generator as only argument
686
var $ = $B.args('__newobj__', 0, {}, [], arguments, {}, 'args', null),
687
args = $.args
688
var res = $B.empty_dict()
689
res.__class__ = args[0]
690
return res
691
}
692
693
dict.__reduce_ex__ = function(self, protocol){
694
return $B.fast_tuple([
695
__newobj__,
696
$B.fast_tuple([self.__class__]),
697
_b_.None,
698
_b_.None,
699
dict.items(self)])
700
}
701
713
try{
714
res.push(repr(item[0]) + ": " + repr(item[1]))
715
}catch(err){
716
throw err
717
}
723
dict.__ror__ = function(self, other){
724
// PEP 584
725
if(! _b_.isinstance(other, dict)){
726
return _b_.NotImplemented
727
}
728
var res = dict.copy(other)
729
dict.update(res, self)
730
return res
731
}
732
735
["self", "key", "value"], arguments, {}, null, null)
736
return dict.$setitem($.self, $.key, $.value)
737
}
742
// If key is a string, set:
743
// - $string_dict[key] = [value, order] where "order" is an auto-increment
744
// unique id to keep track of insertion order
745
// - $str_hash[hash(key)] to key
746
//
747
// If key is a number, set $numeric_dict[key] = value
748
//
749
// If key is another object, compute its hash value:
750
// - if the hash is a key of $str_hash, and key == $str_hash[hash],
751
// replace $string_dict[$str_hash[hash]] by value
752
// - if the hash is a key of $numeric_dict, and hash == key, replace
753
// $numeric_dict[hash] by value
754
// - if the hash is a key of $object_dict: $object_dict[hash] is a list
755
// of [k, v] pairs. If key is equal to one of the "k", replace the
756
// matching v by value. Otherwise, add [key, value] to the list
757
// - else set $object_dict[hash] = [[key, value]]
758
//
759
// In all cases, increment attribute $version, used to detect dictionary
762
// Parameter $hash is only set if this method is called by setdefault.
763
// In this case the hash of key has already been computed and we
764
// know that the key is not present in the dictionary, so it's no
765
// use computing hash(key) again, nor testing equality of keys
774
// If class attribute __init__ or __new__ are reset,
775
// the factory function has to change
776
self.$jsobj.$factory = $B.$instance_creator(self.$jsobj)
777
}
778
}else{
786
if(self.$string_dict === undefined){
787
console.log("pas de string dict", self, key, value)
788
}
789
if(self.$string_dict[key] !== undefined){
790
self.$string_dict[key][0] = value
791
}else{
792
self.$string_dict[key] = [value, self.$order++]
793
self.$str_hash[str_hash(key)] = key
794
self.$version++
795
}
798
if(self.$numeric_dict[key] !== undefined){
799
// existing key: preserve order
800
self.$numeric_dict[key][0] = value
801
}else{
802
// special case for 0 and 1 if True or False are keys
803
var done = false
804
if((key == 0 || key == 1) &&
805
self.$object_dict[key] !== undefined){
806
for(const item of self.$object_dict[key]){
807
if((key == 0 && item[0] === false) ||
808
(key == 1 && item[0] === true)){
809
// replace value
810
item[1][0] = value
811
done = true
812
}
813
}
814
}
815
if(! done){
816
// new key
817
self.$numeric_dict[key] = [value, self.$order++]
818
}
822
case "boolean":
823
// true replaces 1 and false replaces 0
824
var num = key ? 1 : 0
825
if(self.$numeric_dict[num] !== undefined){
826
var order = self.$numeric_dict[num][1] // preserve order
827
self.$numeric_dict[num] = [value, order]
828
return
829
}
830
if(self.$object_dict[num] !== undefined){
831
self.$object_dict[num].push([key, [value, self.$order++]])
832
}else{
833
self.$object_dict[num] = [[key, [value, self.$order++]]]
834
}
854
// If $setitem is called from setdefault, don't test equality of key
855
// with any object
856
if($hash){
857
if(self.$object_dict[$hash] !== undefined){
861
}
862
self.$version++
863
return $N
864
}
865
var ix = rank(self, hash, key)
866
if(ix > -1){
867
// reset value
918
var $ = $B.args("fromkeys", 3, {cls: null, keys: null, value: null},
919
["cls", "keys", "value"], arguments, {value: _b_.None}, null, null),
931
if(klass === dict){dict.$setitem(res, key, value)}
932
else{$B.$getattr(res, "__setitem__")(key, value)}
943
var $ = $B.args("get", 3, {self: null, key: null, _default: null},
944
["self", "key", "_default"], arguments, {_default: $N}, null, null)
947
catch(err){
948
if(_b_.isinstance(err, _b_.KeyError)){return $._default}
949
else{throw err}
950
}
951
}
952
953
var dict_items = $B.make_view("dict_items", true)
954
dict_items.$iterator = $B.make_iterator_class("dict_itemiterator")
958
var _len = arguments.length - 1,
959
_msg = "items() takes no arguments (" + _len + " given)"
962
var items = to_list(self),
963
set_like = true
964
// Check if all values are hashable
965
for(var i = 0, len = items.length; i < len; i++){
966
try{
967
_b_.hash(items[i][1])
968
}catch(err){
969
set_like = false
970
break
971
}
972
}
973
var values = to_list(self)
974
var it = dict_items.$factory(self, values, set_like)
975
it.dict_version = self.$version
985
var _len = arguments.length - 1,
986
_msg = "keys() takes no arguments (" + _len + " given)"
989
var it = dict_keys.$factory(self, to_list(self, 0), true)
990
it.dict_version = self.$version
996
var missing = {},
997
$ = $B.args("pop", 3, {self: null, key: null, _default: null},
998
["self", "key", "_default"], arguments, {_default: missing}, null, null),
1030
var $ = $B.args("setdefault", 3, {self: null, key: null, _default: null},
1031
["self", "key", "_default"], arguments, {_default: $N}, null, null),
1035
try{
1036
// Pass 3rd argument to dict.$getitem to avoid using __missing__
1037
// Cf. issue #1598
1038
return dict.$getitem(self, key, true)
1039
}catch(err){
1044
var hash = key.$hash
1045
key.$hash = undefined
1046
dict.$setitem(self, key, _default, hash)
1053
var $ = $B.args("update", 1, {"self": null}, ["self"], arguments,
1054
{}, "args", "kw"),
1055
self = $.self,
1056
args = $.args,
1057
kw = $.kw
1058
if(args.length > 0){
1059
var o = args[0]
1066
var _keys = _b_.list.$factory($B.$call($B.$getattr(o, "keys"))())
1067
for(var i = 0, len = _keys.length; i < len; i++){
1069
dict.$setitem(self, _keys[i], _value)
1070
}
1071
}else{
1072
var it = _b_.iter(o),
1073
i = 0
1074
while(true){
1075
try{
1076
var item = _b_.next(it)
1077
}catch(err){
1078
if(err.__class__ === _b_.StopIteration){break}
1079
throw err
1080
}
1081
try{
1082
key_value = _b_.list.$factory(item)
1083
}catch(err){
1084
throw _b_.TypeError.$factory("cannot convert dictionary" +
1085
" update sequence element #" + i + " to a sequence")
1086
}
1087
if(key_value.length !== 2){
1088
throw _b_.ValueError.$factory("dictionary update " +
1089
"sequence element #" + i + " has length " +
1090
key_value.length + "; 2 is required")
1091
}
1092
dict.$setitem(self, key_value[0], key_value[1])
1093
i++
1102
var dict_values = $B.make_view("dict_values")
1103
dict_values.$iterator = $B.make_iterator_class("dict_valueiterator")
1107
var _len = arguments.length - 1,
1108
_msg = "values() takes no arguments (" + _len + " given)"
1112
var it = dict_values.$factory(self, values, false)
1113
it.dict_version = self.$version
1119
var args = [res]
1120
for(var i = 0, len = arguments.length; i < len ; i++){
1121
args.push(arguments[i])
1122
}
1123
dict.__init__.apply(null, args)
1133
$B.empty_dict = function(){
1134
return {
1135
__class__: dict,
1136
$numeric_dict : {},
1137
$object_dict : {},
1138
$string_dict : {},
1139
$str_hash: {},
1145
// This must be done after set_func_names, otherwise dict.fromkeys doesn't
1146
// have the attribute $infos
1147
dict.fromkeys = _b_.classmethod.$factory(dict.fromkeys)
1148
1149
$B.getset_descriptor = $B.make_class("getset_descriptor",
1150
function(klass, attr){
1151
return {
1152
__class__: $B.getset_descriptor,
1154
cls: klass,
1155
attr: attr
1156
}
1157
}
1158
)
1159
1160
$B.getset_descriptor.__repr__ = $B.getset_descriptor.__str__ = function(self){
1161
return `<attribute '${self.attr}' of '${self.cls.$infos.__name__}' objects>`
1162
}
1163
1164
$B.set_func_names($B.getset_descriptor, "builtins")
1165
1170
// obj is a dictionary, with $string_dict table such that
1171
// obj.$string_dict[key] = [value, rank]
1172
// Transform it into an object with attribute $jsobj such that
1173
// res.$jsobj[key] = value
1174
var res = $B.obj_dict(dict.$to_obj(obj))
1186
throw _b_.TypeError.$factory("'mappingproxy' object does not support " +
1187
"item assignment")
1190
for(var attr in dict){
1191
if(mappingproxy[attr] !== undefined ||
1192
["__class__", "__mro__", "__new__", "__init__", "__delitem__",
1193
"clear", "fromkeys", "pop", "popitem", "setdefault",
1194
"update"].indexOf(attr) > -1){
1195
continue
1196
}
1197
if(typeof dict[attr] == "function"){
1198
mappingproxy[attr] = (function(key){
1199
return function(){
1200
return dict[key].apply(null, arguments)
1201
}
1202
})(attr)
1203
}else{
1204
mappingproxy[attr] = dict[attr]
1205
}
1206
}
1207
1231
throw _b_.AttributeError.$factory("'" + $B.class_name(obj) +
1232
"' object has no attribute '__dict__'")}