Changeset View
Changeset View
Standalone View
Standalone View
swh/model/merkle.py
# Copyright (C) 2017 The Software Heritage developers | # Copyright (C) 2017 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 | ||||
import collections | import collections | ||||
from typing import List, Optional | |||||
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 84 Lines • ▼ Show 20 Lines | class MerkleNode(dict, metaclass=abc.ABCMeta): | ||||
Attributes: | Attributes: | ||||
data (dict): data associated to the current node | data (dict): data associated to the current node | ||||
parents (list): known parents of the current node | parents (list): known parents of the current node | ||||
collected (bool): whether the current node has been collected | collected (bool): whether the current node has been collected | ||||
""" | """ | ||||
__slots__ = ['parents', 'data', '__hash', 'collected'] | __slots__ = ['parents', 'data', '__hash', 'collected'] | ||||
type = None | type = None # type: Optional[str] # TODO: make this an enum | ||||
vlorentz: we may want to make this an enum | |||||
Done Inline Actionsagreed, but not in this diff, right? I've added an inline TODO now though. zack: agreed, but not in this diff, right?
I've added an inline TODO now though. | |||||
"""Type of the current node (used as a classifier for :func:`collect`)""" | """Type of the current node (used as a classifier for :func:`collect`)""" | ||||
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 145 Lines • ▼ Show 20 Lines | def reset_collect(self): | ||||
child.reset_collect() | child.reset_collect() | ||||
class MerkleLeaf(MerkleNode): | class MerkleLeaf(MerkleNode): | ||||
"""A leaf to a Merkle tree. | """A leaf to a Merkle tree. | ||||
A Merkle leaf is simply a Merkle node with children disabled. | A Merkle leaf is simply a Merkle node with children disabled. | ||||
""" | """ | ||||
__slots__ = [] | __slots__ = [] # type: List[str] | ||||
def __setitem__(self, name, child): | def __setitem__(self, name, child): | ||||
raise ValueError('%s is a leaf' % self.__class__.__name__) | raise ValueError('%s is a leaf' % self.__class__.__name__) | ||||
def __getitem__(self, name): | def __getitem__(self, name): | ||||
raise ValueError('%s is a leaf' % self.__class__.__name__) | raise ValueError('%s is a leaf' % self.__class__.__name__) | ||||
def __delitem__(self, name): | def __delitem__(self, name): | ||||
raise ValueError('%s is a leaf' % self.__class__.__name__) | raise ValueError('%s is a leaf' % self.__class__.__name__) | ||||
def update(self, new_children): | def update(self, new_children): | ||||
"""Children update operation. Disabled for leaves.""" | """Children update operation. Disabled for leaves.""" | ||||
raise ValueError('%s is a leaf' % self.__class__.__name__) | raise ValueError('%s is a leaf' % self.__class__.__name__) |
we may want to make this an enum