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
1236 lines (1116 sloc)
36.3 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
177
dict.$to_obj = function(d){
178
// Function applied to dictionary that only have string keys,
179
// return a Javascript objects with the kays mapped to the value,
180
// excluding the insertion rank
181
var res = {}
182
for(var key in d.$string_dict){
183
res[key] = d.$string_dict[key][0]
184
}
185
return res
186
}
187
197
if(val === undefined){val = _b_.NotImplemented}
198
else if(val === null){val = $N}
203
for(var k in d.$numeric_dict){
204
items.push([parseFloat(k), d.$numeric_dict[k]])
205
}
211
for(var k in d.$object_dict){
212
d.$object_dict[k].forEach(function(item){
213
items.push(item)
214
})
215
}
217
// sort by insertion order
218
items.sort(function(a, b){
219
return a[1][1] - b[1][1]
220
})
221
items = items.map(function(item){return [item[0], item[1][0]]})
226
}else{
227
items.__class__ = _b_.tuple
228
return items.map(function(item){
229
item.__class__ = _b_.tuple; return item}
230
)
231
}
242
si(left, _l[i][0], _l[i][1])
243
if(right.$version != right_version){
244
throw _b_.RuntimeError.$factory("dict mutated during update")
245
}
246
}
249
function rank(self, hash, key){
250
// Search if object key, with hash = hash(key), is in
251
// self.$object_dict
252
var pairs = self.$object_dict[hash]
253
if(pairs !== undefined){
254
for(var i = 0, len = pairs.length; i < len; i++){
255
if($B.rich_comp("__eq__", key, pairs[i][0])){
256
return i
257
}
258
}
259
}
260
return -1
261
}
262
269
dict.__class_getitem__ = function(cls, item){
270
// PEP 585
271
// Set as a classmethod at the end of this script, after $B.set_func_names()
272
if(! Array.isArray(item)){
273
item = [item]
274
}
275
return $B.GenericAlias.$factory(cls, item)
276
}
277
280
var $ = $B.args("__contains__", 2, {self: null, key: null},
281
["self", "key"], arguments, {}, null, null),
284
if(self.$is_namespace){key = $B.to_alias(key)} // issue 1244
285
286
if(self.$jsobj){
287
return self.$jsobj[key] !== undefined
288
}
294
return self.$numeric_dict[key] !== undefined
295
}
296
297
var hash = _b_.hash(key)
298
if(self.$str_hash[hash] !== undefined &&
299
$B.rich_comp("__eq__", key, self.$str_hash[hash])){return true}
300
if(self.$numeric_dict[hash] !== undefined &&
301
$B.rich_comp("__eq__", key, hash)){return true}
302
return rank(self, hash, key) > -1
307
var $ = $B.args("__eq__", 2, {self: null, arg: null},
308
["self", "arg"], arguments, {}, null, null),
317
switch(typeof arg){
318
case "string":
319
if(self.$string_dict[arg] === undefined){
339
if((ix = rank(self, hash, arg)) > -1){
340
self.$object_dict[hash].splice(ix, 1)
341
}else{
350
var $ = $B.args("__eq__", 2, {self: null, other: null},
351
["self", "other"], arguments, {}, null, null),
357
if(self.$jsobj){self = jsobj2dict(self.$jsobj)}
358
if(other.$jsobj){other = jsobj2dict(other.$jsobj)}
369
if(!$B.rich_comp("__eq__", other.$numeric_dict[k][0],
370
self.$numeric_dict[k][0])){
374
var pairs = other.$object_dict[k],
375
flag = false
376
for(var i = 0, len = pairs.length; i < len; i++){
377
if($B.rich_comp("__eq__", k, pairs[i][0]) &&
378
$B.rich_comp("__eq__", self.$numeric_dict[k],
379
pairs[i][1])){
380
flag = true
381
break
382
}
397
var pairs = self.$object_dict[hash]
398
// Get all (key, value) pairs in other that have the same hash
399
var other_pairs = []
400
if(other.$numeric_dict[hash] !== undefined){
401
other_pairs.push([hash, other.$numeric_dict[hash]])
402
}
404
other_pairs = other_pairs.concat(other.$object_dict[hash])
405
}
406
if(other_pairs.length == 0){
407
return false
408
}
409
for(var i = 0, len_i = pairs.length; i < len_i; i++){
410
var flag = false
411
var key = pairs[i][0],
413
for(var j = 0, len_j = other_pairs.length; j < len_j; j++){
414
if($B.rich_comp("__eq__", key, other_pairs[j][0]) &&
429
var $ = $B.args("__getitem__", 2, {self: null, arg: null},
430
["self", "arg"], arguments, {}, null, null),
438
dict.$getitem = function(self, arg, ignore_missing){
439
// ignore_missing is only set in dict.setdefault
452
var x = self.$string_dict[arg]
453
if(x !== undefined){
454
$B.string_count++
455
return x[0]
463
break
464
}
465
466
// since the key is more complex use 'default' method of getting item
467
492
if(! ignore_missing){
493
if(self.__class__ !== dict && ! ignore_missing){
494
try{
495
var missing_method = getattr(self.__class__, "__missing__",
496
_b_.None)
497
}catch(err){
498
console.log(err)
517
if(item.length != 2){
518
throw _b_.ValueError.$factory("dictionary " +
519
`update sequence element #${i} has length 1; 2 is required`)
520
}
528
if(item[0] != 0 && item[0] != 1){
529
self.$numeric_dict[item[0]] = [item[1], self.$order++]
530
self.$version++
531
break
532
}
545
for(var key in first){
546
self.$string_dict[key] = [first[key], self.$order++]
547
}
548
return _b_.None
549
}else if(first.$jsobj){
550
self.$jsobj = {}
551
for(var attr in first.$jsobj){
552
self.$jsobj[attr] = first.$jsobj[attr]
562
arguments, {}, "first", "second")
563
var args = $.first
564
if(args.length > 1){
565
throw _b_.TypeError.$factory("dict expected at most 1 argument" +
566
", got 2")
567
}else if(args.length == 1){
568
args = args[0]
569
if(args.__class__ === dict){
570
['$string_dict', '$str_hash', '$numeric_dict', '$object_dict'].
571
forEach(function(d){
572
for(key in args[d]){self[d][key] = args[d][key]}
573
})
577
var keys = $B.$getattr(args, "keys", null)
578
if(keys !== null){
579
var gi = $B.$getattr(args, "__getitem__", null)
580
if(gi !== null){
581
// has keys and __getitem__ : it's a mapping, iterate on
582
// keys and values
583
gi = $B.$call(gi)
584
var kiter = _b_.iter($B.$call(keys)())
585
while(true){
586
try{
587
var key = _b_.next(kiter),
588
value = gi(key)
589
dict.__setitem__(self, key, value)
590
}catch(err){
591
if(err.__class__ === _b_.StopIteration){
592
break
593
}
594
throw err
595
}
596
}
597
return $N
598
}
599
}
600
if(! Array.isArray(args)){
601
args = _b_.list.$factory(args)
602
}
603
// Form "dict([[key1, value1], [key2,value2], ...])"
629
dict.__ior__ = function(self, other){
630
// PEP 584
631
dict.update(self, other)
632
return self
633
}
634
643
for(var k in self.$numeric_dict){_count++}
644
for(var k in self.$string_dict){_count++}
645
for(var hash in self.$object_dict){
646
_count += self.$object_dict[hash].length
647
}
673
dict.__or__ = function(self, other){
674
// PEP 584
675
if(! _b_.isinstance(other, dict)){
676
return _b_.NotImplemented
677
}
678
var res = dict.copy(self)
679
dict.update(res, other)
680
return res
681
}
682
683
function __newobj__(){
684
// __newobj__ is called with a generator as only argument
685
var $ = $B.args('__newobj__', 0, {}, [], arguments, {}, 'args', null),
686
args = $.args
687
var res = $B.empty_dict()
688
res.__class__ = args[0]
689
return res
690
}
691
692
dict.__reduce_ex__ = function(self, protocol){
693
return $B.fast_tuple([
694
__newobj__,
695
$B.fast_tuple([self.__class__]),
696
_b_.None,
697
_b_.None,
698
dict.items(self)])
699
}
700
712
try{
713
res.push(repr(item[0]) + ": " + repr(item[1]))
714
}catch(err){
715
throw err
716
}
722
dict.__ror__ = function(self, other){
723
// PEP 584
724
if(! _b_.isinstance(other, dict)){
725
return _b_.NotImplemented
726
}
727
var res = dict.copy(other)
728
dict.update(res, self)
729
return res
730
}
731
734
["self", "key", "value"], arguments, {}, null, null)
735
return dict.$setitem($.self, $.key, $.value)
736
}
741
// If key is a string, set:
742
// - $string_dict[key] = [value, order] where "order" is an auto-increment
743
// unique id to keep track of insertion order
744
// - $str_hash[hash(key)] to key
745
//
746
// If key is a number, set $numeric_dict[key] = value
747
//
748
// If key is another object, compute its hash value:
749
// - if the hash is a key of $str_hash, and key == $str_hash[hash],
750
// replace $string_dict[$str_hash[hash]] by value
751
// - if the hash is a key of $numeric_dict, and hash == key, replace
752
// $numeric_dict[hash] by value
753
// - if the hash is a key of $object_dict: $object_dict[hash] is a list
754
// of [k, v] pairs. If key is equal to one of the "k", replace the
755
// matching v by value. Otherwise, add [key, value] to the list
756
// - else set $object_dict[hash] = [[key, value]]
757
//
758
// In all cases, increment attribute $version, used to detect dictionary
761
// Parameter $hash is only set if this method is called by setdefault.
762
// In this case the hash of key has already been computed and we
763
// know that the key is not present in the dictionary, so it's no
764
// use computing hash(key) again, nor testing equality of keys
773
// If class attribute __init__ or __new__ are reset,
774
// the factory function has to change
775
self.$jsobj.$factory = $B.$instance_creator(self.$jsobj)
776
}
777
}else{
785
if(self.$string_dict === undefined){
786
console.log("pas de string dict", self, key, value)
787
}
788
if(self.$string_dict[key] !== undefined){
789
self.$string_dict[key][0] = value
790
}else{
791
self.$string_dict[key] = [value, self.$order++]
792
self.$str_hash[str_hash(key)] = key
793
self.$version++
794
}
797
if(self.$numeric_dict[key] !== undefined){
798
// existing key: preserve order
799
self.$numeric_dict[key][0] = value
800
}else{
801
// special case for 0 and 1 if True or False are keys
802
var done = false
803
if((key == 0 || key == 1) &&
804
self.$object_dict[key] !== undefined){
805
for(const item of self.$object_dict[key]){
806
if((key == 0 && item[0] === false) ||
807
(key == 1 && item[0] === true)){
808
// replace value
809
item[1][0] = value
810
done = true
811
}
812
}
813
}
814
if(! done){
815
// new key
816
self.$numeric_dict[key] = [value, self.$order++]
817
}
821
case "boolean":
822
// true replaces 1 and false replaces 0
823
var num = key ? 1 : 0
824
if(self.$numeric_dict[num] !== undefined){
825
var order = self.$numeric_dict[num][1] // preserve order
826
self.$numeric_dict[num] = [value, order]
827
return
828
}
829
if(self.$object_dict[num] !== undefined){
830
self.$object_dict[num].push([key, [value, self.$order++]])
831
}else{
832
self.$object_dict[num] = [[key, [value, self.$order++]]]
833
}
853
// If $setitem is called from setdefault, don't test equality of key
854
// with any object
855
if($hash){
856
if(self.$object_dict[$hash] !== undefined){
860
}
861
self.$version++
862
return $N
863
}
864
var ix = rank(self, hash, key)
865
if(ix > -1){
866
// reset value
917
var $ = $B.args("fromkeys", 3, {cls: null, keys: null, value: null},
918
["cls", "keys", "value"], arguments, {value: _b_.None}, null, null),
930
if(klass === dict){dict.$setitem(res, key, value)}
931
else{$B.$getattr(res, "__setitem__")(key, value)}
942
var $ = $B.args("get", 3, {self: null, key: null, _default: null},
943
["self", "key", "_default"], arguments, {_default: $N}, null, null)
946
catch(err){
947
if(_b_.isinstance(err, _b_.KeyError)){return $._default}
948
else{throw err}
949
}
950
}
951
952
var dict_items = $B.make_view("dict_items", true)
953
dict_items.$iterator = $B.make_iterator_class("dict_itemiterator")
957
var _len = arguments.length - 1,
958
_msg = "items() takes no arguments (" + _len + " given)"
961
var items = to_list(self),
962
set_like = true
963
// Check if all values are hashable
964
for(var i = 0, len = items.length; i < len; i++){
965
try{
966
_b_.hash(items[i][1])
967
}catch(err){
968
set_like = false
969
break
970
}
971
}
972
var values = to_list(self)
973
var it = dict_items.$factory(self, values, set_like)
974
it.dict_version = self.$version
984
var _len = arguments.length - 1,
985
_msg = "keys() takes no arguments (" + _len + " given)"
988
var it = dict_keys.$factory(self, to_list(self, 0), true)
989
it.dict_version = self.$version
995
var missing = {},
996
$ = $B.args("pop", 3, {self: null, key: null, _default: null},
997
["self", "key", "_default"], arguments, {_default: missing}, null, null),
1029
var $ = $B.args("setdefault", 3, {self: null, key: null, _default: null},
1030
["self", "key", "_default"], arguments, {_default: $N}, null, null),
1034
try{
1035
// Pass 3rd argument to dict.$getitem to avoid using __missing__
1036
// Cf. issue #1598
1037
return dict.$getitem(self, key, true)
1038
}catch(err){
1043
var hash = key.$hash
1044
key.$hash = undefined
1045
dict.$setitem(self, key, _default, hash)
1052
var $ = $B.args("update", 1, {"self": null}, ["self"], arguments,
1053
{}, "args", "kw"),
1054
self = $.self,
1055
args = $.args,
1056
kw = $.kw
1057
if(args.length > 0){
1058
var o = args[0]
1065
var _keys = _b_.list.$factory($B.$call($B.$getattr(o, "keys"))())
1066
for(var i = 0, len = _keys.length; i < len; i++){
1068
dict.$setitem(self, _keys[i], _value)
1069
}
1070
}else{
1071
var it = _b_.iter(o),
1072
i = 0
1073
while(true){
1074
try{
1075
var item = _b_.next(it)
1076
}catch(err){
1077
if(err.__class__ === _b_.StopIteration){break}
1078
throw err
1079
}
1080
try{
1081
key_value = _b_.list.$factory(item)
1082
}catch(err){
1083
throw _b_.TypeError.$factory("cannot convert dictionary" +
1084
" update sequence element #" + i + " to a sequence")
1085
}
1086
if(key_value.length !== 2){
1087
throw _b_.ValueError.$factory("dictionary update " +
1088
"sequence element #" + i + " has length " +
1089
key_value.length + "; 2 is required")
1090
}
1091
dict.$setitem(self, key_value[0], key_value[1])
1092
i++
1101
var dict_values = $B.make_view("dict_values")
1102
dict_values.$iterator = $B.make_iterator_class("dict_valueiterator")
1106
var _len = arguments.length - 1,
1107
_msg = "values() takes no arguments (" + _len + " given)"
1111
var it = dict_values.$factory(self, values, false)
1112
it.dict_version = self.$version
1118
var args = [res]
1119
for(var i = 0, len = arguments.length; i < len ; i++){
1120
args.push(arguments[i])
1121
}
1122
dict.__init__.apply(null, args)
1132
$B.empty_dict = function(){
1133
return {
1134
__class__: dict,
1135
$numeric_dict : {},
1136
$object_dict : {},
1137
$string_dict : {},
1138
$str_hash: {},
1144
// This must be done after set_func_names, otherwise dict.fromkeys doesn't
1145
// have the attribute $infos
1146
dict.fromkeys = _b_.classmethod.$factory(dict.fromkeys)
1147
1148
$B.getset_descriptor = $B.make_class("getset_descriptor",
1149
function(klass, attr){
1150
return {
1151
__class__: $B.getset_descriptor,
1153
cls: klass,
1154
attr: attr
1155
}
1156
}
1157
)
1158
1159
$B.getset_descriptor.__repr__ = $B.getset_descriptor.__str__ = function(self){
1160
return `<attribute '${self.attr}' of '${self.cls.$infos.__name__}' objects>`
1161
}
1162
1163
$B.set_func_names($B.getset_descriptor, "builtins")
1164
1169
// obj is a dictionary, with $string_dict table such that
1170
// obj.$string_dict[key] = [value, rank]
1171
// Transform it into an object with attribute $jsobj such that
1172
// res.$jsobj[key] = value
1173
var res = $B.obj_dict(dict.$to_obj(obj))
1183
throw _b_.TypeError.$factory("'mappingproxy' object does not support " +
1184
"item assignment")
1187
for(var attr in dict){
1188
if(mappingproxy[attr] !== undefined ||
1189
["__class__", "__mro__", "__new__", "__init__", "__delitem__",
1190
"clear", "fromkeys", "pop", "popitem", "setdefault",
1191
"update"].indexOf(attr) > -1){
1192
continue
1193
}
1194
if(typeof dict[attr] == "function"){
1195
mappingproxy[attr] = (function(key){
1196
return function(){
1197
return dict[key].apply(null, arguments)
1198
}
1199
})(attr)
1200
}else{
1201
mappingproxy[attr] = dict[attr]
1202
}
1203
}
1204
1228
throw _b_.AttributeError.$factory("'" + $B.class_name(obj) +
1229
"' object has no attribute '__dict__'")}