Changeset View
Changeset View
Standalone View
Standalone View
swh/model/merkle.py
# Copyright (C) 2017-2020 The Software Heritage developers | # Copyright (C) 2017-2020 The Software Heritage developers | ||||
# See the AUTHORS file at the top-level directory of this distribution | # See the AUTHORS file at the top-level directory of this distribution | ||||
# License: GNU General Public License version 3, or any later version | # License: GNU General Public License version 3, or any later version | ||||
# See top-level LICENSE file for more information | # See top-level LICENSE file for more information | ||||
"""Merkle tree data structure""" | """Merkle tree data structure""" | ||||
import abc | import abc | ||||
from collections.abc import Mapping | from collections.abc import Mapping | ||||
from typing import Iterator, List, Set | from typing import Dict, Iterator, List, Set | ||||
def deep_update(left, right): | def deep_update(left, right): | ||||
"""Recursively update the left mapping with deeply nested values from the right | """Recursively update the left mapping with deeply nested values from the right | ||||
mapping. | mapping. | ||||
This function is useful to merge the results of several calls to | This function is useful to merge the results of several calls to | ||||
:func:`MerkleNode.collect`. | :func:`MerkleNode.collect`. | ||||
▲ Show 20 Lines • Show All 77 Lines • ▼ Show 20 Lines | class MerkleNode(dict, metaclass=abc.ABCMeta): | ||||
Addition, update and removal of objects are instrumented to automatically | Addition, update and removal of objects are instrumented to automatically | ||||
invalidate the hashes of the current node as well as its registered | invalidate the hashes of the current node as well as its registered | ||||
parents; It also resets the collection status of the objects so the updated | parents; It also resets the collection status of the objects so the updated | ||||
objects can be collected. | objects can be collected. | ||||
The collection of updated data from the tree is implemented through the | The collection of updated data from the tree is implemented through the | ||||
:func:`collect` function and associated helpers. | :func:`collect` function and associated helpers. | ||||
Attributes: | |||||
data (dict): data associated to the current node | |||||
parents (list): known parents of the current node | |||||
collected (bool): whether the current node has been collected | |||||
""" | """ | ||||
__slots__ = ["parents", "data", "__hash", "collected"] | __slots__ = ["parents", "data", "__hash", "collected"] | ||||
"""Type of the current node (used as a classifier for :func:`collect`)""" | data: Dict | ||||
"""data associated to the current node""" | |||||
parents: List | |||||
"""known parents of the current node""" | |||||
collected: bool | |||||
"""whether the current node has been collected""" | |||||
def __init__(self, data=None): | def __init__(self, data=None): | ||||
super().__init__() | super().__init__() | ||||
self.parents = [] | self.parents = [] | ||||
self.data = data | self.data = data | ||||
self.__hash = None | self.__hash = None | ||||
self.collected = False | self.collected = False | ||||
▲ Show 20 Lines • Show All 190 Lines • Show Last 20 Lines |