py_dict.js

;(function($B){

/*
Implementation of Python dictionaries

We can't use Javascript's Map here, because the behaviour is not exactly the
same (eg with keys that are instances of classes with a __hash__ method...)
and because Map is much slower than regular Javascript objects.

A Python dictionary is implemented as a Javascript objects with these
attributes:
. $version: an integer with an initial value of 0, incremented at each
  insertion
. $numeric_dict: for keys of type int
. $string_dict and $str_hash: for keys of type str
. $object_dict: for keys of other types

The value associated to a key in $numeric_dict and $string_dict is a pair
[value, rank] where "value" is the value associated with the key and "rank"
is the value of the dict attribute $version when the pair is inserted. This
is required to keep track of the insertion order, mandatory since Python 3.7.

For keys that are not str or int, their hash value is computed. Since several
keys with the same hash can be stored in a dictionary, $object_dict[hash] is a
list of [key, [value, rank]] lists.
*/

var _b_ = $B.builtins

var str_hash = _b_.str.__hash__,
    $N = _b_.None

var set_ops = ["eq", "le", "lt", "ge", "gt",
    "sub", "rsub", "and", "or", "xor"]

// methods to compare non set-like views
function is_sublist(t1, t2){
    // Return true if all elements of t1 are in t2
    for(var i = 0, ilen = t1.length; i < ilen; i++){
        var x = t1[i],
            flag = false
        for(var j = 0, jlen = t2.length; j < jlen; j++){
            if($B.rich_comp("__eq__", x, t2[j])){
                t2.splice(j, 1)
                flag = true
                break
            }
        }
        if(! flag){
            return false
        }
    }
    return true
}

dict_view_op = {
    __eq__: function(t1, t2){
        return t1.length == t2.length && is_sublist(t1, t2)
    },
    __ne__: function(t1, t2){
        return ! dict_view_op.__eq__(t1, t2)
    },
    __lt__: function(t1, t2){
        return t1.length < t2.length && is_sublist(t1, t2)
    },
    __gt__: function(t1, t2){
        return dict_view_op.__lt__(t2, t1)
    },
    __le__: function(t1, t2){
        return t1.length <= t2.length && is_sublist(t1, t2)
    },
    __ge__: function(t1, t2){
        return dict_view_op.__le__(t2, t1)
    },
    __and__: function(t1, t2){
        var items = []
        for(var i = 0, ilen = t1.length; i < ilen; i++){
            var x = t1[i]
                flag = false
            for(var j = 0, jlen = t2.length; j < jlen; j++){
                if($B.rich_comp("__eq__", x, t2[j])){
                    t2.splice(j, 1)
                    items.push(x)
                    break
                }
            }
        }
        return items
    },
    __or__: function(t1, t2){
        var items = t1
        for(var j = 0, jlen = t2.length; j < jlen; j++){
            var y = t2[j],
                flag = false
            for(var i = 0, ilen = t1.length; i < ilen; i++){
                if($B.rich_comp("__eq__", y, t1[i])){
                    t2.splice(j, 1)
                    flag = true
                    break
                }
            }
            if(! flag){
                items.push(y)
            }
        }
        return items
    }

}

$B.make_view = function(name){
    var klass = $B.make_class(name, function(d, items, set_like){
        return {
            __class__: klass,
            __dict__: $B.empty_dict(),
            counter: -1,
            dict: d,
            items: items,
            len: items.length,
            set_like: set_like
        }
    })

    for(var i = 0, len = set_ops.length; i < len; i++){
        var op = "__" + set_ops[i] + "__"
        klass[op] = (function(op){
            return function(self, other){
                // compare set of items to other
                if(self.set_like){
                    return _b_.set[op](_b_.set.$factory(self),
                        _b_.set.$factory(other))
                }else{
                    // Non-set like views can only be compared to
                    // instances of the same class
                    if(other.__class__ !== klass){
                        return false
                    }
                    var other_items = _b_.list.$factory(other)
                    return dict_view_op[op](self.items, other_items)
                }
            }
        })(op)
    }

    klass.__iter__ = function(self){
        var it = klass.$iterator.$factory(self.items)
        it.test_change = function(){
            return self.dict.$version != self.dict_version
        }
        return it
    }

    klass.__len__ = function(self){
        return self.len
    }

    klass.__repr__ = function(self){
        return klass.$infos.__name__ + '(' + _b_.repr(self.items) + ')'
    }

    $B.set_func_names(klass, "builtins")
    return klass
}

var dict = {
    __class__: _b_.type,
    __mro__: [_b_.object],
    $infos: {
        __module__: "builtins",
        __name__: "dict"
    },
    $is_class: true,
    $native: true,
    $match_mapping_pattern: true // for pattern matching (PEP 634)
}

dict.$to_obj = function(d){
    // Function applied to dictionary that only have string keys,
    // return a Javascript objects with the kays mapped to the value,
    // excluding the insertion rank
    var res = {}
    for(var key in d.$string_dict){
        res[key] = d.$string_dict[key][0]
    }
    return res
}

function to_list(d, ix){
    var items = [],
        item

    if(d.$jsobj){
        items = []
        for(var attr in d.$jsobj){
            if((! attr.startsWith("$")) &&
                    ((! d.$exclude) || ! d.$exclude(attr))){
                var val = d.$jsobj[attr]
                if(val === undefined){val = _b_.NotImplemented}
                else if(val === null){val = $N}
                items.push([attr, val])
            }
        }
    }else if(_b_.isinstance(d, _b_.dict)){
        for(var k in d.$numeric_dict){
            items.push([parseFloat(k), d.$numeric_dict[k]])
        }

        for(var k in d.$string_dict){
            items.push([k, d.$string_dict[k]])
        }

        for(var k in d.$object_dict){
            d.$object_dict[k].forEach(function(item){
                items.push(item)
            })
        }

        // sort by insertion order
        items.sort(function(a, b){
            return a[1][1] - b[1][1]
        })
        items = items.map(function(item){return [item[0], item[1][0]]})
    }
    if(ix !== undefined){
        res = items.map(function(item){return item[ix]})
        return res
    }else{
        items.__class__ = _b_.tuple
        return items.map(function(item){
            item.__class__ = _b_.tuple; return item}
        )
    }
}

$B.dict_to_list = to_list // used in py_types.js

var $copy_dict = function(left, right){
    var _l = to_list(right),
        si = dict.$setitem
    right.$version = right.$version || 0
    var right_version = right.$version || 0
    for(var i = 0, len = _l.length; i < len; i++){
        si(left, _l[i][0], _l[i][1])
        if(right.$version != right_version){
            throw _b_.RuntimeError.$factory("dict mutated during update")
        }
    }
}

function rank(self, hash, key){
    // Search if object key, with hash = hash(key), is in
    // self.$object_dict
    var pairs = self.$object_dict[hash]
    if(pairs !== undefined){
        for(var i = 0, len = pairs.length; i < len; i++){
            if($B.rich_comp("__eq__", key, pairs[i][0])){
                return i
            }
        }
    }
    return -1
}

dict.__bool__ = function () {
    var $ = $B.args("__bool__", 1, {self: null}, ["self"],
        arguments, {}, null, null)
    return dict.__len__($.self) > 0
}

dict.__class_getitem__ = function(cls, item){
    // PEP 585
    // Set as a classmethod at the end of this script, after $B.set_func_names()
    if(! Array.isArray(item)){
        item = [item]
    }
    return $B.GenericAlias.$factory(cls, item)
}

dict.__contains__ = function(){
    var $ = $B.args("__contains__", 2, {self: null, key: null},
        ["self", "key"], arguments, {}, null, null),
        self = $.self,
        key = $.key

    if(self.$jsobj){
        return self.$jsobj[key] !== undefined
    }

    switch(typeof key) {
        case "string":
            return self.$string_dict.hasOwnProperty(key)
        case "number":
            return self.$numeric_dict[key] !== undefined
    }

    var hash = _b_.hash(key)
    if(self.$str_hash[hash] !== undefined &&
            $B.rich_comp("__eq__", key, self.$str_hash[hash])){
        return true
    }
    if(self.$numeric_dict[hash] !== undefined &&
            $B.rich_comp("__eq__", key, hash)){
        return true
    }
    return rank(self, hash, key) > -1
}

dict.__delitem__ = function(){

    var $ = $B.args("__eq__", 2, {self: null, arg: null},
        ["self", "arg"], arguments, {}, null, null),
        self = $.self,
        arg = $.arg

    if(self.$jsobj){
        if(self.$jsobj[arg] === undefined){throw _b_.KeyError.$factory(arg)}
        delete self.$jsobj[arg]
        return $N
    }
    switch(typeof arg){
        case "string":
            if(self.$string_dict[arg] === undefined){
                throw _b_.KeyError.$factory(_b_.str.$factory(arg))
            }
            delete self.$string_dict[arg]
            delete self.$str_hash[str_hash(arg)]
            self.$version++
            return $N
        case "number":
            if(self.$numeric_dict[arg] === undefined){
                throw _b_.KeyError.$factory(_b_.str.$factory(arg))
            }
            delete self.$numeric_dict[arg]
            self.$version++
            return $N
    }
    // go with defaults

    var hash = _b_.hash(arg),
        ix

    if((ix = rank(self, hash, arg)) > -1){
        self.$object_dict[hash].splice(ix, 1)
    }else{
        throw _b_.KeyError.$factory(_b_.str.$factory(arg))
    }

    self.$version++
    return $N
}

dict.__eq__ = function(){
    var $ = $B.args("__eq__", 2, {self: null, other: null},
        ["self", "other"], arguments, {}, null, null),
        self = $.self,
        other = $.other

    if(! _b_.isinstance(other, dict)){return false}

    if(self.$jsobj){self = jsobj2dict(self.$jsobj)}
    if(other.$jsobj){other = jsobj2dict(other.$jsobj)}
    if(dict.__len__(self) != dict.__len__(other)){
        return false
    }

    if(self.$string_dict.length != other.$string_dict.length){
        return false
    }

    for(var k in self.$numeric_dict){
        if(other.$numeric_dict.hasOwnProperty(k)){
            if(!$B.rich_comp("__eq__", other.$numeric_dict[k][0],
                    self.$numeric_dict[k][0])){
                return false
            }
        }else if(other.$object_dict.hasOwnProperty(k)){
            var pairs = other.$object_dict[k],
                flag = false
            for(var i = 0, len = pairs.length; i < len; i++){
                if($B.rich_comp("__eq__", k, pairs[i][0]) &&
                        $B.rich_comp("__eq__", self.$numeric_dict[k],
                        pairs[i][1])){
                    flag = true
                    break
                }
            }
            if(! flag){return false}
        }else{
            return false
        }
    }
    for(var k in self.$string_dict){
        if(!other.$string_dict.hasOwnProperty(k) ||
                !$B.rich_comp("__eq__", other.$string_dict[k][0],
                    self.$string_dict[k][0])){
            return false
        }
    }
    for(var hash in self.$object_dict){
        var pairs = self.$object_dict[hash]
        // Get all (key, value) pairs in other that have the same hash
        var other_pairs = []
        if(other.$numeric_dict[hash] !== undefined){
            other_pairs.push([hash, other.$numeric_dict[hash]])
        }
        if(other.$object_dict[hash] !== undefined){
            other_pairs = other_pairs.concat(other.$object_dict[hash])
        }
        if(other_pairs.length == 0){
            return false
        }
        for(var i = 0, len_i = pairs.length; i < len_i; i++){
            var flag = false
            var key = pairs[i][0],
                value = pairs[i][1][0]
            for(var j = 0, len_j = other_pairs.length; j < len_j; j++){
                if($B.rich_comp("__eq__", key, other_pairs[j][0]) &&
                        $B.rich_comp("__eq__", value, other_pairs[j][1][0])){
                    flag = true
                    break
                }
            }
            if(! flag){
                return false
            }
        }
    }
    return true
}

dict.__getitem__ = function(){
    var $ = $B.args("__getitem__", 2, {self: null, arg: null},
        ["self", "arg"], arguments, {}, null, null),
        self = $.self,
        arg = $.arg
    return dict.$getitem(self, arg)
}

dict.$getitem = function(self, arg, ignore_missing){
    // ignore_missing is set in dict.get and dict.setdefault
    if(self.$jsobj){
        if(self.$exclude && self.$exclude(arg)){
            throw _b_.KeyError.$factory(arg)
        }
        if(self.$jsobj[arg] === undefined){
            if(self.$jsobj.hasOwnProperty &&
                    self.$jsobj.hasOwnProperty(arg)){
                return $B.Undefined
            }
            throw _b_.KeyError.$factory(arg)
        }
        return self.$jsobj[arg]
    }

    switch(typeof arg){
        case "string":
            if(self.$string_dict.hasOwnProperty(arg)){
                return self.$string_dict[arg][0]
            }
            break
        case "number":
            if(self.$numeric_dict[arg] !== undefined){
                return self.$numeric_dict[arg][0]
            }
            break
    }

    // since the key is more complex use 'default' method of getting item

    var hash = _b_.hash(arg),
        _eq = function(other){return $B.rich_comp("__eq__", arg, other)}

    if(typeof arg == "object"){
        arg.$hash = hash // cache for setdefault
    }
    var sk = self.$str_hash[hash]
    if(sk !== undefined && _eq(sk)){
        return self.$string_dict[sk][0]
    }
    if(self.$numeric_dict[hash] !== undefined && _eq(hash)){
         return self.$numeric_dict[hash][0]
    }
    if(_b_.isinstance(arg, _b_.str)){
        // string subclass
        if(self.$string_dict.hasOwnProperty(arg.valueOf())){
            return self.$string_dict[arg.valueOf()][0]
        }
    }

    var ix = rank(self, hash, arg)
    if(ix > -1){
        return self.$object_dict[hash][ix][1][0]
    }

    if(! ignore_missing){
        if(self.__class__ !== dict && ! ignore_missing){
            try{
                var missing_method = $B.$getattr(self.__class__,
                    "__missing__", _b_.None)
            }catch(err){
                console.log(err)

            }
            if(missing_method !== _b_.None){
                return missing_method(self, arg)
            }
        }
    }
    throw _b_.KeyError.$factory(arg)
}

dict.__hash__ = _b_.None

function init_from_list(self, args){
    var i = -1,
        stop = args.length - 1,
        si = dict.__setitem__
    while(i++ < stop){
        var item = args[i]
        if(item.length != 2){
            throw _b_.ValueError.$factory("dictionary " +
                `update sequence element #${i} has length 1; 2 is required`)
        }
        switch(typeof item[0]) {
            case 'string':
                self.$string_dict[item[0]] = [item[1], self.$order++]
                self.$str_hash[str_hash(item[0])] = item[0]
                self.$version++
                break
            case 'number':
                if(item[0] != 0 && item[0] != 1){
                    self.$numeric_dict[item[0]] = [item[1], self.$order++]
                    self.$version++
                    break
                }
            default:
                si(self, item[0], item[1])
                break
        }
    }
}

dict.__init__ = function(self, first, second){
    if(first === undefined){
        return $N
    }
    if(second === undefined){
        if(first.$nat != 'kw' && $B.get_class(first) === $B.JSObj){
            for(var key in first){
                self.$string_dict[key] = [first[key], self.$order++]
            }
            return _b_.None
        }else if(first.$jsobj){
            self.$jsobj = {}
            for(var attr in first.$jsobj){
                self.$jsobj[attr] = first.$jsobj[attr]
            }
            return $N
        }else if(Array.isArray(first)){
            init_from_list(self, first)
            return $N
        }
    }

    var $ = $B.args("dict", 1, {self:null}, ["self"],
        arguments, {}, "first", "second")
    var args = $.first
    if(args.length > 1){
        throw _b_.TypeError.$factory("dict expected at most 1 argument" +
            ", got 2")
    }else if(args.length == 1){
        args = args[0]
        if(args.__class__ === dict){
            ['$string_dict', '$str_hash', '$numeric_dict', '$object_dict'].
                forEach(function(d){
                    for(key in args[d]){self[d][key] = args[d][key]}
                })
        }else if(_b_.isinstance(args, dict)){
            $copy_dict(self, args)
        }else{
            var keys = $B.$getattr(args, "keys", null)
            if(keys !== null){
                var gi = $B.$getattr(args, "__getitem__", null)
                if(gi !== null){
                    // has keys and __getitem__ : it's a mapping, iterate on
                    // keys and values
                    gi = $B.$call(gi)
                    var kiter = _b_.iter($B.$call(keys)())
                    while(true){
                        try{
                            var key = _b_.next(kiter),
                                value = gi(key)
                                dict.__setitem__(self, key, value)
                        }catch(err){
                            if(err.__class__ === _b_.StopIteration){
                                break
                            }
                            throw err
                        }
                    }
                    return $N
                }
            }
            if(! Array.isArray(args)){
                args = _b_.list.$factory(args)
            }
            // Form "dict([[key1, value1], [key2,value2], ...])"
            init_from_list(self, args)
        }
    }
    var kw = $.second.$string_dict
    for(var attr in kw){
        switch(typeof attr){
            case "string":
                self.$string_dict[attr] = [kw[attr][0], self.$order++]
                self.$str_hash[str_hash(attr)] = attr
                break
            case "number":
                self.$numeric_dict[attr] = [kw[attr][0], self.$order++]
                break
            default:
                si(self, attr, kw[attr][0])
                break
        }
    }
    return $N
}

dict.__iter__ = function(self){
    return _b_.iter(dict.keys(self))
}

dict.__ior__ = function(self, other){
    // PEP 584
    dict.update(self, other)
    return self
}

dict.__len__ = function(self) {
    var _count = 0

    if(self.$jsobj){
        for(var attr in self.$jsobj){
            if(attr.charAt(0) != "$" &&
                    ((! self.$exclude) || ! self.$exclude(attr))){
                _count++
            }
        }
        return _count
    }

    for(var k in self.$numeric_dict){_count++}
    for(var k in self.$string_dict){_count++}
    for(var hash in self.$object_dict){
        _count += self.$object_dict[hash].length
    }

    return _count
}

dict.__ne__ = function(self, other){
    return ! dict.__eq__(self, other)
}

dict.__new__ = function(cls){
    if(cls === undefined){
        throw _b_.TypeError.$factory("int.__new__(): not enough arguments")
    }
    var instance = {
        __class__: cls,
        $numeric_dict : {},
        $object_dict : {},
        $string_dict : {},
        $str_hash: {},
        $version: 0,
        $order: 0
    }
    if(cls !== dict){
        instance.__dict__ = $B.empty_dict()
    }
    return instance
}

dict.__or__ = function(self, other){
    // PEP 584
    if(! _b_.isinstance(other, dict)){
        return _b_.NotImplemented
    }
    var res = dict.copy(self)
    dict.update(res, other)
    return res
}

function __newobj__(){
    // __newobj__ is called with a generator as only argument
    var $ = $B.args('__newobj__', 0, {}, [], arguments, {}, 'args', null),
        args = $.args
    var res = $B.empty_dict()
    res.__class__ = args[0]
    return res
}

dict.__reduce_ex__ = function(self, protocol){
    return $B.fast_tuple([
        __newobj__,
        $B.fast_tuple([self.__class__]),
        _b_.None,
        _b_.None,
        dict.items(self)])
}

dict.__repr__ = function(self){
    $B.builtins_repr_check(dict, arguments) // in brython_builtins.js
    if(self.$jsobj){ // wrapper around Javascript object
        return dict.__repr__(jsobj2dict(self.$jsobj, self.$exclude))
    }
    if($B.repr.enter(self)){
        return "{...}"
    }
    var res = [],
        items = to_list(self)
    items.forEach(function(item){
        try{
            res.push(_b_.repr(item[0]) + ": " + _b_.repr(item[1]))
        }catch(err){
            throw err
        }
    })
    $B.repr.leave(self)
    return "{" + res.join(", ") + "}"
}

dict.__ror__ = function(self, other){
    // PEP 584
    if(! _b_.isinstance(other, dict)){
        return _b_.NotImplemented
    }
    var res = dict.copy(other)
    dict.update(res, self)
    return res
}

dict.__setitem__ = function(self, key, value){
    var $ = $B.args("__setitem__", 3, {self: null, key: null, value: null},
        ["self", "key", "value"], arguments, {}, null, null)
    return dict.$setitem($.self, $.key, $.value)
}

dict.$setitem = function(self, key, value, $hash){
    // Set a dictionary item mapping key and value.
    //
    // If key is a string, set:
    // - $string_dict[key] = [value, order] where "order" is an auto-increment
    //   unique id to keep track of insertion order
    // - $str_hash[hash(key)] to key
    //
    // If key is a number, set $numeric_dict[key] = value
    //
    // If key is another object, compute its hash value:
    // - if the hash is a key of $str_hash, and key == $str_hash[hash],
    //   replace $string_dict[$str_hash[hash]] by value
    // - if the hash is a key of $numeric_dict, and hash == key, replace
    //   $numeric_dict[hash] by value
    // - if the hash is a key of $object_dict: $object_dict[hash] is a list
    //   of [k, v] pairs. If key is equal to one of the "k", replace the
    //   matching v by value. Otherwise, add [key, value] to the list
    // - else set $object_dict[hash] = [[key, value]]
    //
    // In all cases, increment attribute $version, used to detect dictionary
    // changes during an iteration.
    //
    // Parameter $hash is only set if this method is called by setdefault.
    // In this case the hash of key has already been computed and we
    // know that the key is not present in the dictionary, so it's no
    // use computing hash(key) again, nor testing equality of keys
    if(self.$jsobj){
        if(self.$from_js){
            // dictionary created by method to_dict of JSObj instances
            value = $B.pyobj2jsobj(value)
        }
        if(self.$jsobj.__class__ === _b_.type){
            self.$jsobj[key] = value
            if(key == "__init__" || key == "__new__"){
                // If class attribute __init__ or __new__ are reset,
                // the factory function has to change
                self.$jsobj.$factory = $B.$instance_creator(self.$jsobj)
            }
        }else{
            self.$jsobj[key] = value
        }
        return $N
    }
    if(key instanceof String){
        key = key.valueOf()
    }

    switch(typeof key){
        case "string":
            if(self.$string_dict === undefined){
                console.log("pas de string dict", self, key, value)
            }
            if(self.$string_dict.hasOwnProperty(key)){
                self.$string_dict[key][0] = value
            }else{
                self.$string_dict[key] = [value, self.$order++]
                self.$str_hash[str_hash(key)] = key
                self.$version++
            }
            return $N
        case "number":
            if(self.$numeric_dict[key] !== undefined){
                // existing key: preserve order
                self.$numeric_dict[key][0] = value
            }else{
                // special case for 0 and 1 if True or False are keys
                var done = false
                if((key == 0 || key == 1) &&
                        self.$object_dict[key] !== undefined){
                    for(const item of self.$object_dict[key]){
                        if((key == 0 && item[0] === false) ||
                                (key == 1 && item[0] === true)){
                            // replace value
                            item[1][0] = value
                            done = true
                        }
                    }
                }
                if(! done){
                    // new key
                    self.$numeric_dict[key] = [value, self.$order++]
                }
                self.$version++
            }
            return $N
        case "boolean":
            // true replaces 1 and false replaces 0
            var num = key ? 1 : 0
            if(self.$numeric_dict[num] !== undefined){
                var order = self.$numeric_dict[num][1] // preserve order
                self.$numeric_dict[num] = [value, order]
                return
            }
            if(self.$object_dict[num] !== undefined){
                self.$object_dict[num].push([key, [value, self.$order++]])
            }else{
                self.$object_dict[num] = [[key, [value, self.$order++]]]
            }
    }

    // if we got here the key is more complex, use default method

    var hash = $hash === undefined ? _b_.hash(key) : $hash,
        _eq = function(other){return $B.rich_comp("__eq__", key, other)}

    if(self.$numeric_dict[hash] !== undefined && _eq(hash)){
        self.$numeric_dict[hash] = [value, self.$numeric_dict[hash][1]]
        self.$version++
        return $N
    }
    var sk = self.$str_hash[hash]
    if(sk !== undefined && _eq(sk)){
        self.$string_dict[sk] = [value, self.$string_dict[sk][1]]
        self.$version++
        return $N
    }

    // If $setitem is called from setdefault, don't test equality of key
    // with any object
    if($hash){
        if(self.$object_dict[$hash] !== undefined){
            self.$object_dict[$hash].push([key, [value, self.$order++]])
        }else{
            self.$object_dict[$hash] = [[key, [value, self.$order++]]]
        }
        self.$version++
        return $N
    }
    var ix = rank(self, hash, key)
    if(ix > -1){
        // reset value
        self.$object_dict[hash][ix][1] = [value,
            self.$object_dict[hash][ix][1][1]]
        return $N
    }else if(self.$object_dict.hasOwnProperty(hash)){
        self.$object_dict[hash].push([key, [value, self.$order++]])
    }else{
        self.$object_dict[hash] = [[key, [value, self.$order++]]]
    }
    self.$version++
    return $N
}

// add "reflected" methods
$B.make_rmethods(dict)

dict.clear = function(){
    // Remove all items from the dictionary.
    var $ = $B.args("clear", 1, {self: null}, ["self"], arguments, {},
        null, null),
        self = $.self

    self.$numeric_dict = {}
    self.$string_dict = {}
    self.$str_hash = {}
    self.$object_dict = {}

    if(self.$jsobj){
        for(var attr in self.$jsobj){
            if(attr.charAt(0) !== "$" && attr !== "__class__"){
                delete self.$jsobj[attr]
            }
        }
    }
    self.$version++
    self.$order = 0
    return $N
}

dict.copy = function(self){
    // Return a shallow copy of the dictionary
    var $ = $B.args("copy", 1, {self: null},["self"], arguments,{},
        null, null),
        self = $.self,
        res = $B.empty_dict()
    $copy_dict(res, self)
    return res
}

dict.fromkeys = function(){

    var $ = $B.args("fromkeys", 3, {cls: null, keys: null, value: null},
        ["cls", "keys", "value"], arguments, {value: _b_.None}, null, null),
        keys = $.keys,
        value = $.value

    // class method
    var klass = $.cls,
        res = $B.$call(klass)(),
        keys_iter = $B.$iter(keys)

    while(1){
        try{
            var key = _b_.next(keys_iter)
            if(klass === dict){dict.$setitem(res, key, value)}
            else{$B.$getattr(res, "__setitem__")(key, value)}
        }catch(err){
            if($B.is_exc(err, [_b_.StopIteration])){
                return res
            }
            throw err
        }
    }
}

dict.get = function(){
    var $ = $B.args("get", 3, {self: null, key: null, _default: null},
        ["self", "key", "_default"], arguments, {_default: $N}, null, null)

    try{
        // call $getitem with ignore_missign set to true
        return dict.$getitem($.self, $.key, true)
    }catch(err){
        if(_b_.isinstance(err, _b_.KeyError)){return $._default}
        else{throw err}
    }
}

var dict_items = $B.make_view("dict_items", true)
dict_items.$iterator = $B.make_iterator_class("dict_itemiterator")

dict.items = function(self){
    var $ = $B.args('items', 1, {self: null}, ['self'], arguments,
                    {}, null, null)
    var items = to_list(self),
        set_like = true
    // Check if all values are hashable
    for(var i = 0, len = items.length; i < len; i++){
        try{
            _b_.hash(items[i][1])
        }catch(err){
            set_like = false
            break
        }
    }
    var values = to_list(self)
    var it = dict_items.$factory(self, values, set_like)
    it.dict_version = self.$version
    return it
}


var dict_keys = $B.make_view("dict_keys")
dict_keys.$iterator = $B.make_iterator_class("dict_keyiterator")

dict.keys = function(self){
    var $ = $B.args('keys', 1, {self: null}, ['self'], arguments,
                    {}, null, null)
    var it = dict_keys.$factory(self, to_list(self, 0), true)
    it.dict_version = self.$version
    return it
}

dict.pop = function(){

    var missing = {},
        $ = $B.args("pop", 3, {self: null, key: null, _default: null},
        ["self", "key", "_default"], arguments, {_default: missing}, null, null),
        self = $.self,
        key = $.key,
        _default = $._default

    try{
        var res = dict.__getitem__(self, key)
        dict.__delitem__(self, key)
        return res
    }catch(err){
        if(err.__class__ === _b_.KeyError){
            if(_default !== missing){return _default}
            throw err
        }
        throw err
    }
}

dict.popitem = function(self){
    try{
        var itm = _b_.next(_b_.iter(dict.items(self)))
        dict.__delitem__(self, itm[0])
        return _b_.tuple.$factory(itm)
    }catch(err) {
        if (err.__class__ == _b_.StopIteration) {
            throw _b_.KeyError.$factory("'popitem(): dictionary is empty'")
        }
    }
}

dict.setdefault = function(){

    var $ = $B.args("setdefault", 3, {self: null, key: null, _default: null},
            ["self", "key", "_default"], arguments, {_default: $N}, null, null),
        self = $.self,
        key = $.key,
        _default = $._default
    try{
        // Pass 3rd argument to dict.$getitem to avoid using __missing__
        // Cf. issue #1598
        return dict.$getitem(self, key, true)
    }catch(err){
        if(err.__class__ !== _b_.KeyError){
            throw err
        }
        if(_default === undefined){_default = $N}
        var hash = key.$hash
        key.$hash = undefined
        dict.$setitem(self, key, _default, hash)
        return _default
    }
}

dict.update = function(self){

    var $ = $B.args("update", 1, {"self": null}, ["self"], arguments,
            {}, "args", "kw"),
        self = $.self,
        args = $.args,
        kw = $.kw
    if(args.length > 0){
        var o = args[0]
        if(_b_.isinstance(o, dict)){
            if(o.$jsobj){
                o = jsobj2dict(o.$jsobj)
            }
            $copy_dict(self, o)
        }else if(_b_.hasattr(o, "keys")){
            var _keys = _b_.list.$factory($B.$call($B.$getattr(o, "keys"))())
            for(var i = 0, len = _keys.length; i < len; i++){
                var _value = $B.$getattr(o, "__getitem__")(_keys[i])
                dict.$setitem(self, _keys[i], _value)
            }
        }else{
            var it = _b_.iter(o),
                i = 0
            while(true){
                try{
                    var item = _b_.next(it)
                }catch(err){
                    if(err.__class__ === _b_.StopIteration){break}
                    throw err
                }
                try{
                    key_value = _b_.list.$factory(item)
                }catch(err){
                    throw _b_.TypeError.$factory("cannot convert dictionary" +
                        " update sequence element #" + i + " to a sequence")
                }
                if(key_value.length !== 2){
                    throw _b_.ValueError.$factory("dictionary update " +
                        "sequence element #" + i + " has length " +
                        key_value.length + "; 2 is required")
                }
                dict.$setitem(self, key_value[0], key_value[1])
                i++
            }
        }
    }
    $copy_dict(self, kw)
    self.$version++
    return $N
}

var dict_values = $B.make_view("dict_values")
dict_values.$iterator = $B.make_iterator_class("dict_valueiterator")

dict.values = function(self){
    var $ = $B.args('values', 1, {self: null}, ['self'], arguments,
                    {}, null, null)
    var values = to_list(self, 1)
    var it = dict_values.$factory(self, values, false)
    it.dict_version = self.$version
    return it
}

dict.$factory = function(){
    var res = dict.__new__(dict)
    var args = [res]
    for(var i = 0, len = arguments.length; i < len ; i++){
        args.push(arguments[i])
    }
    dict.__init__.apply(null, args)
    return res
}

_b_.dict = dict

$B.set_func_names(dict, "builtins")

dict.__class_getitem__ = _b_.classmethod.$factory(dict.__class_getitem__)

$B.empty_dict = function(){
    return {
        __class__: dict,
        $numeric_dict : {},
        $object_dict : {},
        $string_dict : {},
        $str_hash: {},
        $version: 0,
        $order: 0
    }
}

// This must be done after set_func_names, otherwise dict.fromkeys doesn't
// have the attribute $infos
dict.fromkeys = _b_.classmethod.$factory(dict.fromkeys)

$B.getset_descriptor = $B.make_class("getset_descriptor",
    function(klass, attr){
        return {
            __class__: $B.getset_descriptor,
            __doc__: _b_.None,
            cls: klass,
            attr: attr
        }
    }
)

$B.getset_descriptor.__repr__ = $B.getset_descriptor.__str__ = function(self){
    return `<attribute '${self.attr}' of '${self.cls.$infos.__name__}' objects>`
}

$B.set_func_names($B.getset_descriptor, "builtins")

// Class for attribute __dict__ of classes
var mappingproxy = $B.mappingproxy = $B.make_class("mappingproxy",
    function(obj){
        if(_b_.isinstance(obj, dict)){
            // obj is a dictionary, with $string_dict table such that
            // obj.$string_dict[key] = [value, rank]
            // Transform it into an object with attribute $jsobj such that
            // res.$jsobj[key] = value
            var res = $B.obj_dict(dict.$to_obj(obj))
        }else{
            var res = $B.obj_dict(obj)
        }
        res.__class__ = mappingproxy
        return res
    }
)

mappingproxy.$match_mapping_pattern = true // for pattern matching (PEP 634)

mappingproxy.__repr__ = function(){
    return '<mappingproxy object>'
}

mappingproxy.__setitem__ = function(){
    throw _b_.TypeError.$factory("'mappingproxy' object does not support " +
        "item assignment")
}

for(var attr in dict){
    if(mappingproxy[attr] !== undefined ||
            ["__class__", "__mro__", "__new__", "__init__", "__delitem__",
                "clear", "fromkeys", "pop", "popitem", "setdefault",
                "update"].indexOf(attr) > -1){
        continue
    }
    if(typeof dict[attr] == "function"){
        mappingproxy[attr] = (function(key){
            return function(){
                return dict[key].apply(null, arguments)
            }
        })(attr)
    }else{
        mappingproxy[attr] = dict[attr]
    }
}

$B.set_func_names(mappingproxy, "builtins")

function jsobj2dict(x, exclude){
    exclude = exclude || function(){return false}
    var d = $B.empty_dict()
    for(var attr in x){
        if(attr.charAt(0) != "$" && ! exclude(attr)){
            if(x[attr] === null){
                d.$string_dict[attr] = [_b_.None, d.$order++]
            }else if(x[attr] === undefined){
                continue
            }else if(x[attr].$jsobj === x){
                d.$string_dict[attr] = [d, d.$order++]
            }else{
                d.$string_dict[attr] = [$B.$JS2Py(x[attr]), d.$order++]
            }
        }
    }
    return d
}

$B.obj_dict = function(obj, exclude){
    var klass = obj.__class__ || $B.get_class(obj)
    if(klass !== undefined && klass.$native){
        throw $B.attr_error("__dict__", obj)
    }
    var res = $B.empty_dict()
    res.$jsobj = obj
    res.$exclude = exclude || function(){return false}
    return res
}

// Wrapper around a JS object to handle it as a Python dictionary.
// Some keys of the original object can be ignored by passing
// the filtering function exclude().
// Supports adding new keys.

var jsobj_as_pydict = $B.jsobj_as_pydict = $B.make_class('jsobj_as_pydict',
    function(jsobj, exclude){
        return {
            __class__: jsobj_as_pydict,
            obj: jsobj,
            exclude: exclude ? exclude : function(){return false},
            new_keys: []
        }
    }
)

jsobj_as_pydict.__contains__ = function(self, key){
    if(self.new_keys.indexOf(key) > -1){
        return true
    }
    return ! (self.exclude(key) || self.obj[key] === undefined)
}

jsobj_as_pydict.__delitem__ = function(self, key){
    jsobj_as_pydict.__getitem__(self, key) // raises KeyError if not present
    delete self.obj[key]
    var ix = self.new_keys.indexOf(key)
    if(ix > -1){
        self.new_keys.splice(ix, 1)
    }
}

jsobj_as_pydict.__eq__ = function(self, other){
    if(other.__class__ !== jsobj_as_pydict){
        return _b_.NotImplemented
    }
    // create true Python dicts with the items in self and other
    var self1 = $B.empty_dict()
        other1 = $B.empty_dict()

    dict.__init__(self1, jsobj_as_pydict.items(self))
    dict.__init__(other1, jsobj_as_pydict.items(other))

    // Compare true Python dicts
    return dict.__eq__(self1, other1)
}

jsobj_as_pydict.__getitem__ = function(self, key){
    if(jsobj_as_pydict.__contains__(self, key)){
        return self.obj[key]
    }
    throw _b_.KeyError.$factory(key)
}

jsobj_as_pydict.__iter__ = function(self){
    return _b_.iter(jsobj_as_pydict.keys(self))
}

jsobj_as_pydict.__len__ = function(self){
    var len = 0
    for(var key in self.obj){
        if(! self.exclude(key)){
            len++
        }
    }
    return len + self.new_keys.length
}

jsobj_as_pydict.__repr__ = function(self){
    if($B.repr.enter(self)){
        return "{...}"
    }
    var res = [],
        items = _b_.list.$factory(jsobj_as_pydict.items(self))
    for(var item of items){
        res.push(_b_.repr(item[0]) + ": " + _b_.repr(item[1]))
    }
    $B.repr.leave(self)
    return "{" + res.join(", ") + "}"
}

jsobj_as_pydict.__setitem__ = function(self, key, value){
    if(self.exclude(key) && self.new_keys.indexOf(key) == -1){
        self.new_keys.push(key)
    }
    self.obj[key] = value
}

jsobj_as_pydict.get = function(self, key, _default){
    _default = _default === undefined ? _b_.None : _default
    if(self.exclude(key) || self.obj[key] === undefined){
        return _default
    }
    return self.obj[key]
}

jsobj_as_pydict.items = function(self){
    var items = []
    for(var key in self.obj){
        if(self.exclude(key) && self.new_keys.indexOf(key) == -1){
            continue
        }
        items.push($B.fast_tuple([key, self.obj[key]]))
    }
    var set_like = true
    // Check if all values are hashable
    for(var item of items){
        try{
            _b_.hash(item[1])
        }catch(err){
            set_like = false
            break
        }
    }
    var it = dict_items.$factory(self, items, set_like)
    it.dict_version = self.$version
    return it
}

jsobj_as_pydict.keys = function(self){
    var lst = []
    for(var key in self.obj){
        if(self.exclude(key) && self.new_keys.indexOf(key) == -1){
            continue
        }
        lst.push(key)
    }
    var it = dict_keys.$factory(self, lst, true)
    it.dict_version = self.$version
    return it
}

jsobj_as_pydict.values = function(self){
    var values = []
    for(var key in self.obj){
        if(self.exclude(key) && self.new_keys.indexOf(key) == -1){
            continue
        }
        values.push(self.obj[key])
    }
    var it = dict_values.$factory(self, values, false)
    it.dict_version = self.$version
    return it
}

$B.set_func_names(jsobj_as_pydict, 'builtins')

})(__BRYTHON__)