collections标准库源码学习

class OrderedDict(dict):
    def __init__(self, *args, **kwds):
        """ 这里虽然提供了 `kwds` ，但是不建议传入多个命名参数 
        因为这些参数的顺序是随意的，不是按照你传入的顺序来的 
        """
        if len(args) > 1:
            raise TypeError('expected at most 1 arguments, got %d' % len(args))
        try:
            self.__root
        except AttributeError:
            # 哨兵元素 
            self.__root = root = []
            # 双端循环链表 
            root[:] = [root, root, None]
            self.__map = {}
        self.__update(*args, **kwds)

    def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
        'od.__setitem__(i, y) <==> od[i]=y'
        if key not in self:
            # 向链表中插入新的 Key 节点 
            # self.__map 中添加 Key 和 Key 节点的映射关系 
            root = self.__root
            last = root[0]
            last[1] = root[0] = self.__map[key] = [last, root, key]
        # 使用继承的 dict 功能来保存 Key 和对应 Value 的映射关系 
        return dict_setitem(self, key, value)

    def __delitem__(self, key, dict_delitem=dict.__delitem__):
        'od.__delitem__(y) <==> del od[y]'
        dict_delitem(self, key)
        # 先从映射关系中根据 Key 找到 Key 节点 , 然后再删除双端循环列表对应的 Key 节点 
        link_prev, link_next, _ = self.__map.pop(key)
        link_prev[1] = link_next                        # update link_prev[NEXT]
        link_next[0] = link_prev                        # update link_next[PREV]

    def __iter__(self):
        'od.__iter__() <==> iter(od)'
        # Traverse the linked list in order.
        root = self.__root
        curr = root[1]                                  # start at the first node
        while curr is not root:
            yield curr[2]                               # yield the curr[KEY]
            curr = curr[1]                              # move to next node

    def __reversed__(self):
        'od.__reversed__() <==> reversed(od)'
        # Traverse the linked list in reverse order.
        root = self.__root
        curr = root[0]                                  # start at the last node
        while curr is not root:
            yield curr[2]                               # yield the curr[KEY]
            curr = curr[0]                              # move to previous node

    def clear(self):
        'od.clear() -> None.  Remove all items from od.'
        root = self.__root
        root[:] = [root, root, None]
        self.__map.clear()
        dict.clear(self)

    # 以下的操作方法 , 都不依赖于对链表和 self.__map 的操作了 
    # 可以说上面那些方法是底层 API, 下面的是高层 API
    # 这些方法的代码也不全部列出来的，都比较简单 
    ... ...

    update = MutableMapping.update

    # 再命名一个 `__update` 是专门给 __init__ 用的 
    # 不然，用户继承该类并重载了 __update，就对该类产生了破坏 
    __update = update

    # 该 Object 实例在 Python 中是独一无二的 
    __marker = object()

    ... ...

    def __reduce__(self):
         可以让 Pickle 进行序列化和反序列化 
        items = [[k, self[k]] for k in self]
        inst_dict = vars(self).copy()
        for k in vars(OrderedDict()):
            inst_dict.pop(k, None)
        if inst_dict:
            return (self.__class__, (items,), inst_dict)
        return self.__class__, (items,)

        ... ...

class DoubleLink(object):
    """ 双端循环链表 """
    def __init__(self):
        super(DoubleLink, self).__init__()
        self.__root = root = []
        root[:] = [root, root, None]
        self.__map = {}

    def add(self, key):
        # 每次都是在哨兵节点的前面插入一个新的节点 
        # 每次插入的节点逻辑上为最后一个节点 
        root = self.__root
        last = root[0]
        last[1] = root[0] = self.__map[key] = [last, root, key]

    def delete(self, value):
        prev, next, _ = self.__map.pop(key)
        prev[1] = next
        next[0] = prev

    def __iter__(self):
        root = self.__root # 哨兵节点不用参与遍历 
        curr = root[1]                                  # start at the first node
        while curr is not root:
            yield curr[2]                               # yield the curr[KEY]
            curr = curr[1]                              # move to next node

    def __reversed__(self):
        root = self.__root # 哨兵节点不用参与遍历 
        curr = root[0]                                  # start at the last node
        while curr is not root:
            yield curr[2]                               # yield the curr[KEY]
            curr = curr[0]                              # move to previous node

    def clear(self):
        root = self.__root
        # 这一行 , 猛一看还以为写错了 
        # 后来仔细想了一下 , [root, root, None] 中的 root 其实是一个引用 ( 引用本身不保存任何值 , 相当于指针 )
        # 当赋值给 root[:] 时 , 直接清除了 root 中原来保存的值 
        # 直接变成 [root 引用 , root 引用 , None]
        root[:] = [root, root, None]
        self.__map.clear()

class OrderedDict(dict):
    def __init__(self, *args, **kwds):
        if len(args) > 1:
            raise TypeError('expected at most 1 arguments, got %d' % len(args))
        self.__dl = DoubleLink()
        self.__update(*args, **kwds)

    def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
        if key not in self:
            self.__dl.add(key)
        return dict_setitem(self, key, value)

    def __delitem__(self, key, dict_delitem=dict.__delitem__):
        'od.__delitem__(y) <==> del od[y]'
        dict_delitem(self, key)
        self.__dl.delete(key)

    __iter__ = self.__dl.__iter__

    __reversed__ = self.__dl.__reversed__

    def clear(self):
        self.__dl.clear()
        dict.clear(self)

    ... ...

_class_template = '''\
class {typename}(tuple): # 这里的 tuple 很奇怪，为什么不用 _tuple
    '{typename}({arg_list})'

    # 避免自动从 tuple 继承 __dict__， 减少内存消耗 
    __slots__ = ()

    _fields = {field_names!r}

    def __new__(_cls, {arg_list}):
        'Create new instance of {typename}({arg_list})'
        return _tuple.__new__(_cls, ({arg_list}))

    @classmethod
    def _make(cls, iterable, new=tuple.__new__, len=len): # 这里的 tuple 也是 
        'Make a new {typename} object from a sequence or iterable'
        result = new(cls, iterable)
        if len(result) != {num_fields:d}:
            raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result))
        return result

    def __repr__(self):
        'Return a nicely formatted representation string'
        return '{typename}({repr_fmt})' % self

    def _asdict(self):
        'Return a new OrderedDict which maps field names to their values'
        return OrderedDict(zip(self._fields, self))

    def _replace(_self, **kwds):
        'Return a new {typename} object replacing specified fields with new values'
        result = _self._make(map(kwds.pop, {field_names!r}, _self))
        if kwds:
            raise ValueError('Got unexpected field names: %r' % kwds.keys())
        return result

    def __getnewargs__(self):
        'Return self as a plain tuple.  Used by copy and pickle.'
        return tuple(self)

    __dict__ = _property(_asdict)

    def __getstate__(self):
        'Exclude the OrderedDict from pickling'
        pass

{field_defs}
'''

_repr_template = '{name}=%r'

_field_template = '''\
    {name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}')
'''

def namedtuple(typename, field_names, verbose=False, rename=False):
    # filed_names 支持两种形式：
    # 1. 以，号或者空白字符分割的字符串 , "x, y, z", "x y z" ... ...
    # 2. 生成器 
    if isinstance(field_names, basestring):
        field_names = field_names.replace(',', ' ').split()
    field_names = map(str, field_names)
    # 有些字段重名 /Python 关键字 / 命名不规范等等，需要重新命名 
    # 打开 rename 参数，就会对这些情况进行重新命名 
    # 多用于自动生成 namedtuple 的情况，比如自从从数据库中获取数据 
    if rename:
        seen = set()
        for index, name in enumerate(field_names):
            if (not all(c.isalnum() or c=='_' for c in name)
                or _iskeyword(name)
                or not name
                or name[0].isdigit()
                or name.startswith('_')
                or name in seen):
                field_names[index] = '_%d' % index
            seen.add(name)
    # 还是对字段名进行合法性校验 
    for name in [typename] + field_names:
        if not all(c.isalnum() or c=='_' for c in name):
            raise ValueError('Type names and field names can only contain '
                             'alphanumeric characters and underscores: %r' % name)
        if _iskeyword(name):
            raise ValueError('Type names and field names cannot be a '
                             'keyword: %r' % name)
        if name[0].isdigit():
            raise ValueError('Type names and field names cannot start with '
                             'a number: %r' % name)
    seen = set()
    for name in field_names:
        if name.startswith('_') and not rename:
            raise ValueError('Field names cannot start with an underscore: '
                             '%r' % name)
        if name in seen:
            raise ValueError('Encountered duplicate field name: %r' % name)
        seen.add(name)

    # 生成类的定义 
    class_definition = _class_template.format(
        typename = typename,
        field_names = tuple(field_names),
        num_fields = len(field_names),
        arg_list = repr(tuple(field_names)).replace("'", "")[1:-1],
        repr_fmt = ', '.join(_repr_template.format(name=name)
                             for name in field_names),
        field_defs = '\n'.join(_field_template.format(index=index, name=name)
                               for index, name in enumerate(field_names))
    )
    if verbose: # 用于调试 
        print class_definition

    # Execute the template string in a temporary namespace and support
    # tracing utilities by setting a value for frame.f_globals['__name__']
    # 在一个新的命名空间里创建 namedtuple，应该是为了安全考虑 
    namespace = dict(
        _itemgetter=_itemgetter,
        __name__='namedtuple_%s' % typename, # 指定 namedtuple.__module__ 的值 
        OrderedDict=OrderedDict,
        _property=property,
        _tuple=tuple,
    )
    try:
        exec class_definition in namespace
    except SyntaxError as e:
        raise SyntaxError(e.message + ':\n' + class_definition)
    result = namespace[typename]

    # _sys._getframe(1): 获取创建 namedtuple 的栈帧 
    # 并将该栈帧的名称赋值指给该 namedtuple 的 __module__，
    # 让 pickle 模块在序列化时能找到该 namedtuple 所在的模块 
    # Jython 未定义 sys._getframe，
    # IronPython 虽然定义了 sys._getframe 但是参数只能为 0（即当前栈帧）
    try:
        result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__')
    except (AttributeError, ValueError):
        pass

    return result

class Counter(dict):
    def __init__(self, iterable=None, **kwds):
        super(Counter, self).__init__()
        self.update(iterable, **kwds)

    def __missing__(self, key):
        """ 如果 Counter()[key] 中的 key 不存在，则返回 0"""
        return 0

    def most_common(self, n=None):
        """ 列出最多的键值对，n 参数指定列出最多的前几个键值对 """
        if n is None:
            return sorted(self.iteritems(), key=_itemgetter(1), reverse=True)
        return _heapq.nlargest(n, self.iteritems(), key=_itemgetter(1))

    def elements(self):
        """ 列出多重集合中的所有元素，重复的元素会输出多个 """
        return _chain.from_iterable(_starmap(_repeat, self.iteritems()))

    @classmethod
    def fromkeys(cls, iterable, v=None):
        # 由于从 dict 继承过来，但是 Counter 又不支持该操作，就直接重载抛出异常 
        raise NotImplementedError(
            'Counter.fromkeys() is undefined.  Use Counter(iterable) instead.')

    def update(self, iterable=None, **kwds):
        """ 类似于 dict.update，没什么好讲的 """
        ... ...

    def subtract(self, iterable=None, **kwds):
        """ 也类似于 dcit.update, 不过操作的逻辑是相反的 """
        ... ...

    def copy(self):
        """ 复制出自己一份，也是 dict 本身就有的方法，重载一下 """
        'Return a shallow copy.'
        return self.__class__(self)

    def __reduce__(self):
        """ 能够让 pickle 进行序列化和反序列化 """
        return self.__class__, (dict(self),)

    def __delitem__(self, elem):
        if elem in self: # 如果 Key 值不存在，不需要抛出异常 
            super(Counter, self).__delitem__(elem)

    def __repr__(self):
        ... ...

    # 重载 Counter 的运行操作，支持相加、相减、交集、并集 
    # 代码就不列出来了 
    ... ...