Permalink
Sep 5, 2014
Feb 1, 2020
Sep 5, 2014
Jul 21, 2020
Dec 28, 2020
Dec 28, 2020
Dec 28, 2020
May 17, 2019
Sep 5, 2014
Feb 1, 2020
Jan 15, 2018
Apr 3, 2019
Apr 3, 2019
Feb 1, 2020
Apr 3, 2019
Dec 13, 2018
Dec 21, 2018
Oct 5, 2020
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 28, 2020
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
Dec 28, 2020
Feb 26, 2018
Dec 28, 2020
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
Dec 28, 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 (1092 sloc)
35.4 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
}
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
175
}
176
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
303
}
304
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{
347
}
348
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]) &&
426
}
427
429
var $ = $B.args("__getitem__", 2, {self: null, arg: null},
430
["self", "arg"], arguments, {}, null, null),
451
var x = self.$string_dict[arg]
452
if(x !== undefined){
453
$B.string_count++
454
return x[0]
462
break
463
}
464
465
// since the key is more complex use 'default' method of getting item
466
504
}
505
507
521
if(item[0] != 0 && item[0] != 1){
522
self.$numeric_dict[item[0]] = [item[1], self.$order++]
523
self.$version++
524
break
525
}
538
for(var key in first){
539
self.$string_dict[key] = [first[key], self.$order++]
540
}
541
return _b_.None
542
}else if(first.$jsobj){
543
self.$jsobj = {}
544
for(var attr in first.$jsobj){
545
self.$jsobj[attr] = first.$jsobj[attr]
551
}
555
arguments, {}, "first", "second")
556
var args = $.first
557
if(args.length > 1){
558
throw _b_.TypeError.$factory("dict expected at most 1 argument" +
559
", got 2")
560
}else if(args.length == 1){
561
args = args[0]
562
if(args.__class__ === dict){
563
['$string_dict', '$str_hash', '$numeric_dict', '$object_dict'].
564
forEach(function(d){
565
for(key in args[d]){self[d][key] = args[d][key]}
566
})
570
var keys = $B.$getattr(args, "keys", null)
571
if(keys !== null){
572
var gi = $B.$getattr(args, "__getitem__", null)
573
if(gi !== null){
574
// has keys and __getitem__ : it's a mapping, iterate on
575
// keys and values
576
gi = $B.$call(gi)
577
var kiter = _b_.iter($B.$call(keys)())
578
while(true){
579
try{
580
var key = _b_.next(kiter),
581
value = gi(key)
582
dict.__setitem__(self, key, value)
583
}catch(err){
584
if(err.__class__ === _b_.StopIteration){
585
break
586
}
587
throw err
588
}
589
}
590
return $N
591
}
592
}
593
if(! Array.isArray(args)){
594
args = _b_.list.$factory(args)
595
}
596
// Form "dict([[key1, value1], [key2,value2], ...])"
598
}
616
}
617
620
}
621
622
dict.__ior__ = function(self, other){
623
// PEP 584
624
dict.update(self, other)
625
return self
626
}
627
636
for(var k in self.$numeric_dict){_count++}
637
for(var k in self.$string_dict){_count++}
638
for(var hash in self.$object_dict){
639
_count += self.$object_dict[hash].length
640
}
644
646
666
dict.__or__ = function(self, other){
667
// PEP 584
668
if(! _b_.isinstance(other, dict)){
669
return _b_.NotImplemented
670
}
671
var res = dict.copy(self)
672
dict.update(res, other)
673
return res
674
}
675
686
try{
687
res.push(repr(item[0]) + ": " + repr(item[1]))
688
}catch(err){
689
throw err
690
}
694
}
695
696
dict.__ror__ = function(self, other){
697
// PEP 584
698
if(! _b_.isinstance(other, dict)){
699
return _b_.NotImplemented
700
}
701
var res = dict.copy(other)
702
dict.update(res, self)
703
return res
704
}
705
708
["self", "key", "value"], arguments, {}, null, null)
709
return dict.$setitem($.self, $.key, $.value)
710
}
715
// If key is a string, set:
716
// - $string_dict[key] = [value, order] where "order" is an auto-increment
717
// unique id to keep track of insertion order
718
// - $str_hash[hash(key)] to key
719
//
720
// If key is a number, set $numeric_dict[key] = value
721
//
722
// If key is another object, compute its hash value:
723
// - if the hash is a key of $str_hash, and key == $str_hash[hash],
724
// replace $string_dict[$str_hash[hash]] by value
725
// - if the hash is a key of $numeric_dict, and hash == key, replace
726
// $numeric_dict[hash] by value
727
// - if the hash is a key of $object_dict: $object_dict[hash] is a list
728
// of [k, v] pairs. If key is equal to one of the "k", replace the
729
// matching v by value. Otherwise, add [key, value] to the list
730
// - else set $object_dict[hash] = [[key, value]]
731
//
732
// In all cases, increment attribute $version, used to detect dictionary
735
// Parameter $hash is only set if this method is called by setdefault.
736
// In this case the hash of key has already been computed and we
737
// know that the key is not present in the dictionary, so it's no
738
// use computing hash(key) again, nor testing equality of keys
747
// If class attribute __init__ or __new__ are reset,
748
// the factory function has to change
749
self.$jsobj.$factory = $B.$instance_creator(self.$jsobj)
750
}
751
}else{
759
if(self.$string_dict === undefined){
760
console.log("pas de string dict", self, key, value)
761
}
762
if(self.$string_dict[key] !== undefined){
763
self.$string_dict[key][0] = value
764
}else{
765
self.$string_dict[key] = [value, self.$order++]
766
self.$str_hash[str_hash(key)] = key
767
self.$version++
768
}
771
if(self.$numeric_dict[key] !== undefined){
772
// existing key: preserve order
773
self.$numeric_dict[key][0] = value
774
}else{
775
// special case for 0 and 1 if True or False are keys
776
var done = false
777
if((key == 0 || key == 1) &&
778
self.$object_dict[key] !== undefined){
779
for(const item of self.$object_dict[key]){
780
if((key == 0 && item[0] === false) ||
781
(key == 1 && item[0] === true)){
782
// replace value
783
item[1][0] = value
784
done = true
785
}
786
}
787
}
788
if(! done){
789
// new key
790
self.$numeric_dict[key] = [value, self.$order++]
791
}
795
case "boolean":
796
// true replaces 1 and false replaces 0
797
var num = key ? 1 : 0
798
if(self.$numeric_dict[num] !== undefined){
799
var order = self.$numeric_dict[num][1] // preserve order
800
self.$numeric_dict[num] = [value, order]
801
return
802
}
803
if(self.$object_dict[num] !== undefined){
804
self.$object_dict[num].push([key, [value, self.$order++]])
805
}else{
806
self.$object_dict[num] = [[key, [value, self.$order++]]]
807
}
827
// If $setitem is called from setdefault, don't test equality of key
828
// with any object
829
if($hash){
830
if(self.$object_dict[$hash] !== undefined){
834
}
835
self.$version++
836
return $N
837
}
838
var ix = rank(self, hash, key)
839
if(ix > -1){
840
// reset value
851
}
852
856
857
// add "reflected" methods
859
861
// Remove all items from the dictionary.
881
}
882
884
// Return a shallow copy of the dictionary
890
return res
891
}
892
895
var $ = $B.args("fromkeys", 3, {cls: null, keys: null, value: null},
896
["cls", "keys", "value"], arguments, {value: _b_.None}, null, null),
900
// class method
905
while(1){
906
try{
907
var key = _b_.next(keys_iter)
908
if(klass === dict){dict.$setitem(res, key, value)}
909
else{$B.$getattr(res, "__setitem__")(key, value)}
910
}catch(err){
912
return res
913
}
914
throw err
915
}
916
}
917
}
918
920
var $ = $B.args("get", 3, {self: null, key: null, _default: null},
921
["self", "key", "_default"], arguments, {_default: $N}, null, null)
924
catch(err){
925
if(_b_.isinstance(err, _b_.KeyError)){return $._default}
926
else{throw err}
927
}
928
}
929
930
var dict_items = $B.make_view("dict_items", true)
931
dict_items.$iterator = $B.make_iterator_class("dict_itemiterator")
935
var _len = arguments.length - 1,
936
_msg = "items() takes no arguments (" + _len + " given)"
939
var items = to_list(self),
940
set_like = true
941
// Check if all values are hashable
942
for(var i = 0, len = items.length; i < len; i++){
943
try{
944
_b_.hash(items[i][1])
945
}catch(err){
946
set_like = false
947
break
948
}
949
}
950
var values = to_list(self)
951
var it = dict_items.$factory(self, values, set_like)
952
it.dict_version = self.$version
962
var _len = arguments.length - 1,
963
_msg = "keys() takes no arguments (" + _len + " given)"
966
var it = dict_keys.$factory(self, to_list(self, 0), true)
967
it.dict_version = self.$version
973
var missing = {},
974
$ = $B.args("pop", 3, {self: null, key: null, _default: null},
975
["self", "key", "_default"], arguments, {_default: missing}, null, null),
980
try{
983
return res
984
}catch(err){
987
throw err
988
}
989
throw err
990
}
991
}
992
1003
}
1004
1007
var $ = $B.args("setdefault", 3, {self: null, key: null, _default: null},
1008
["self", "key", "_default"], arguments, {_default: $N}, null, null),
1014
catch(err){
1019
var hash = key.$hash
1020
key.$hash = undefined
1021
dict.$setitem(self, key, _default, hash)
1022
return _default
1023
}
1024
}
1025
1028
var $ = $B.args("update", 1, {"self": null}, ["self"], arguments,
1029
{}, "args", "kw"),
1030
self = $.self,
1031
args = $.args,
1032
kw = $.kw
1033
if(args.length > 0){
1034
var o = args[0]
1041
var _keys = _b_.list.$factory($B.$call($B.$getattr(o, "keys"))())
1042
for(var i = 0, len = _keys.length; i < len; i++){
1044
dict.$setitem(self, _keys[i], _value)
1045
}
1046
}else{
1047
var it = _b_.iter(o),
1048
i = 0
1049
while(true){
1050
try{
1051
var item = _b_.next(it)
1052
}catch(err){
1053
if(err.__class__ === _b_.StopIteration){break}
1054
throw err
1055
}
1056
try{
1057
key_value = _b_.list.$factory(item)
1058
}catch(err){
1059
throw _b_.TypeError.$factory("cannot convert dictionary" +
1060
" update sequence element #" + i + " to a sequence")
1061
}
1062
if(key_value.length !== 2){
1063
throw _b_.ValueError.$factory("dictionary update " +
1064
"sequence element #" + i + " has length " +
1065
key_value.length + "; 2 is required")
1066
}
1067
dict.$setitem(self, key_value[0], key_value[1])
1068
i++
1071
}
1075
}
1076
1077
var dict_values = $B.make_view("dict_values")
1078
dict_values.$iterator = $B.make_iterator_class("dict_valueiterator")
1082
var _len = arguments.length - 1,
1083
_msg = "values() takes no arguments (" + _len + " given)"
1087
var it = dict_values.$factory(self, values, false)
1088
it.dict_version = self.$version
1094
var args = [res]
1095
for(var i = 0, len = arguments.length; i < len ; i++){
1096
args.push(arguments[i])
1097
}
1098
dict.__init__.apply(null, args)
1099
return res
1100
}
1102
_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__)