diff --git a/docs/cli.rst b/docs/cli.rst index 654111f..0826a01 100644 --- a/docs/cli.rst +++ b/docs/cli.rst @@ -1,6 +1,6 @@ Command-line interface ====================== .. click:: swh.model.cli:identify - :prog: swh identify - :show-nested: + :prog: swh identify + :show-nested: diff --git a/docs/persistent-identifiers.rst b/docs/persistent-identifiers.rst index 2f20cf1..2cb27e5 100644 --- a/docs/persistent-identifiers.rst +++ b/docs/persistent-identifiers.rst @@ -1,389 +1,385 @@ .. _persistent-identifiers: ================================================= SoftWare Heritage persistent IDentifiers (SWHIDs) ================================================= **version 1.5, last modified 2020-05-14** .. contents:: :local: :depth: 2 Overview ======== You can point to objects present in the `Software Heritage `_ `archive `_ by the means of **SoftWare Heritage persistent IDentifiers**, or **SWHIDs** for short, that are guaranteed to remain stable (persistent) over time. Their syntax, meaning, and usage is described below. Note that they are identifiers and not URLs, even though URL-based `resolvers`_ for SWHIDs are also available. A SWHID consists of two separate parts, a mandatory *core identifier* that can point to any software artifact (or "object") available in the Software Heritage archive, and an optional list of *qualifiers* that allows to specify the context where the object is meant to be seen and point to a subpart of the object itself. Objects come in different types: * contents * directories * revisions * releases * snapshots Each object is identified by an intrinsic, type-specific object identifier that is embedded in its SWHID as described below. The intrinsic identifiers embedded in SWHIDs are strong cryptographic hashes computed on the entire set of object properties. Together, these identifiers form a `Merkle structure `_, specifically a Merkle `DAG `_. See the :ref:`Software Heritage data model ` for an overview of object types and how they are linked together. See :py:mod:`swh.model.identifiers` for details on how the intrinsic identifiers embedded in SWHIDs are computed. The optional qualifiers are of two kinds: * **context qualifiers:** carry information about the context where a given object is meant to be seen. This is particularly important, as the same object can be reached in the Merkle graph following different *paths* starting from different nodes (or *anchors*), and it may have been retrieved from different *origins*, that may evolve between different *visits* * **fragment qualifiers:** allow to pinpoint specific subparts of an object Syntax ====== Syntactically, SWHIDs are generated by the ```` entry point in the following grammar: .. code-block:: bnf ::= [ ] ; ::= "swh" ":" ":" ":" ; ::= "1" ; ::= "snp" (* snapshot *) | "rel" (* release *) | "rev" (* revision *) | "dir" (* directory *) | "cnt" (* content *) ; ::= 40 * ; (* intrinsic object id, as hex-encoded SHA1 *) ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; ::= | "a" | "b" | "c" | "d" | "e" | "f" ; := ";" [ ] ; ::= | ; ::= | | | ; ::= "origin" "=" ; ::= "visit" "=" ; ::= "anchor" "=" ; ::= "path" "=" ; ::= "lines" "=" ["-" ] ; ::= + ; ::= (* RFC 3987 IRI *) ::= (* RFC 3987 absolute path *) Where: - ```` is an ```` from `RFC 3987`_, and - ```` is a `RFC 3987`_ IRI in either case all occurrences of ``;`` (and ``%``, as required by the RFC) have been percent-encoded (as ``%3B`` and ``%25`` respectively). Other characters *can* be percent-encoded, e.g., to improve readability and/or embeddability of SWHID in other contexts. .. _RFC 3987: https://tools.ietf.org/html/rfc3987 Semantics ========= Core identifiers ---------------- ``:`` is used as separator between the logical parts of core identifiers. The ``swh`` prefix makes explicit that these identifiers are related to *SoftWare Heritage*. ``1`` (````) is the current version of this identifier *scheme*. Future editions will use higher version numbers, possibly breaking backward compatibility, but without breaking the resolvability of SWHIDs that conform to previous versions of the scheme. A SWHID points to a single object, whose type is explicitly captured by ````: * ``snp`` to **snapshots**, * ``rel`` to **releases**, * ``rev`` to **revisions**, * ``dir`` to **directories**, * ``cnt`` to **contents**. The actual object pointed to is identified by the intrinsic identifier ````, which is a hex-encoded (using lowercase ASCII characters) SHA1 computed on the content and metadata of the object itself, as follows: * for **snapshots**, intrinsic identifiers are computed as per :py:func:`swh.model.identifiers.snapshot_identifier` * for **releases**, as per :py:func:`swh.model.identifiers.release_identifier` that produces the same result as a git release hash * for **revisions**, as per :py:func:`swh.model.identifiers.revision_identifier` that produces the same result as a git commit hash * for **directories**, per :py:func:`swh.model.identifiers.directory_identifier` that produces the same result as a git tree hash * for **contents**, the intrinsic identifier is the ``sha1_git`` hash returned by :py:func:`swh.model.identifiers.content_identifier`, i.e., the SHA1 of a byte sequence obtained by juxtaposing the ASCII string ``"blob"`` (without quotes), a space, the length of the content as decimal digits, a NULL byte, and the actual content of the file. Qualifiers ---------- ``;`` is used as separator between the core identifier and the optional qualifiers, as well as between qualifiers. Each qualifier is specified as a key/value pair, using ``=`` as a separator. The following *context qualifiers* are available: * **origin:** the *software origin* where an object has been found or observed in the wild, as an URI; * **visit:** the core identifier of a *snapshot* corresponding to a specific *visit* of a repository containing the designated object; * **anchor:** a *designated node* in the Merkle DAG relative to which a *path to the object* is specified, as the core identifier of a directory, a revision, a release or a snapshot; * **path:** the *absolute file path*, from the *root directory* associated to the *anchor node*, to the object; when the anchor denotes a directory or a revision, and almost always when it's a release, the root directory is uniquely determined; when the anchor denotes a snapshot, the root directory is the one pointed to by ``HEAD`` (possibly indirectly), and undefined if such a reference is missing; The following *fragment qualifier* is available: * **lines:** *line number(s)* of interest, usually within a content object We recommend to equip identifiers meant to be shared with as many qualifiers as possible. While qualifiers may be listed in any order, it is good practice to present them in the order given above, i.e., ``origin``, ``visit``, ``anchor``, ``path``, ``lines``. Redundant information should be omitted: for example, if the *visit* is present, and the *path* is relative to the snapshot indicated there, then the *anchor* qualifier is superfluous; similarly, if the *path* is empty, it may be omitted. Interoperability ================ URI scheme ---------- The ``swh`` URI scheme is registered at IANA for SWHIDs. The present documents constitutes the scheme specification for such URI scheme. Git compatibility ----------------- SWHIDs for contents, directories, revisions, and releases are, at present, compatible with the `Git `_ way of `computing identifiers `_ for its objects. The ```` part of a SWHID for a content object is the Git blob identifier of any file with the same content; for a revision it is the Git commit identifier for the same revision, etc. This is not the case for snapshot identifiers, as Git does not have a corresponding object type. Note that Git compatibility is incidental and is not guaranteed to be maintained in future versions of this scheme (or Git). Examples ======== Core identifiers ---------------- * ``swh:1:cnt:94a9ed024d3859793618152ea559a168bbcbb5e2`` points to the content of a file containing the full text of the GPL3 license * ``swh:1:dir:d198bc9d7a6bcf6db04f476d29314f157507d505`` points to a directory containing the source code of the Darktable photography application as it was at some point on 4 May 2017 * ``swh:1:rev:309cf2674ee7a0749978cf8265ab91a60aea0f7d`` points to a commit in the development history of Darktable, dated 16 January 2017, that added undo/redo supports for masks * ``swh:1:rel:22ece559cc7cc2364edc5e5593d63ae8bd229f9f`` points to Darktable release 2.3.0, dated 24 December 2016 * ``swh:1:snp:c7c108084bc0bf3d81436bf980b46e98bd338453`` points to a snapshot of the entire Darktable Git repository taken on 4 May 2017 from GitHub Identifiers with qualifiers --------------------------- * The following `SWHID - `_ + `__ denotes the lines 9 to 15 of a file content that can be found at absolute path ``/Examples/SimpleFarm/simplefarm.ml`` from the root directory of the revision ``swh:1:rev:2db189928c94d62a3b4757b3eec68f0a4d4113f0`` that is contained in the snapshot ``swh:1:snp:d7f1b9eb7ccb596c2622c4780febaa02549830f9`` taken from the origin - ``https://gitorious.org/ocamlp3l/ocamlp3l_cvs.git``: + ``https://gitorious.org/ocamlp3l/ocamlp3l_cvs.git``:: -.. code-block:: url - - swh:1:cnt:4d99d2d18326621ccdd70f5ea66c2e2ac236ad8b; - origin=https://gitorious.org/ocamlp3l/ocamlp3l_cvs.git; - visit=swh:1:snp:d7f1b9eb7ccb596c2622c4780febaa02549830f9; - anchor=swh:1:rev:2db189928c94d62a3b4757b3eec68f0a4d4113f0; - path=/Examples/SimpleFarm/simplefarm.ml; - lines=9-15 + swh:1:cnt:4d99d2d18326621ccdd70f5ea66c2e2ac236ad8b; + origin=https://gitorious.org/ocamlp3l/ocamlp3l_cvs.git; + visit=swh:1:snp:d7f1b9eb7ccb596c2622c4780febaa02549830f9; + anchor=swh:1:rev:2db189928c94d62a3b4757b3eec68f0a4d4113f0; + path=/Examples/SimpleFarm/simplefarm.ml; + lines=9-15 * Here is an example of a `SWHID - `_ - with a file path that requires percent-escaping: - -.. code-block:: url - - swh:1:cnt:f10371aa7b8ccabca8479196d6cd640676fd4a04; - origin=https://github.com/web-platform-tests/wpt; - visit=swh:1:snp:b37d435721bbd450624165f334724e3585346499; - anchor=swh:1:rev:259d0612af038d14f2cd889a14a3adb6c9e96d96; - path=/html/semantics/document-metadata/the-meta-element/pragma-directives/attr-meta-http-equiv-refresh/support/x%3Burl=foo/ + `__ + with a file path that requires percent-escaping:: + + swh:1:cnt:f10371aa7b8ccabca8479196d6cd640676fd4a04; + origin=https://github.com/web-platform-tests/wpt; + visit=swh:1:snp:b37d435721bbd450624165f334724e3585346499; + anchor=swh:1:rev:259d0612af038d14f2cd889a14a3adb6c9e96d96; + path=/html/semantics/document-metadata/the-meta-element/pragma-directives/attr-meta-http-equiv-refresh/support/x%3Burl=foo/ Implementation ============== Computing --------- An important property of any SWHID is that its core identifier is *intrinsic*: it can be *computed from the object itself*, without having to rely on any third party. An implementation of SWHID that allows to do so locally is the `swh identify `_ tool, available from the `swh.model `_ Python package under the GPL license. This package can be installed via the ``pip`` package manager with the one liner ``pip3 install swh.model[cli]`` on any machine with Python (at least version 3.7) and ``pip`` installed (on a Debian or Ubuntu system a simple ``apt install python3 python3-pip`` will suffice, see `the general instructions `_ for other platforms). SWHIDs are also automatically computed by Software Heritage for all archived objects as part of its archival activity, and can be looked up via the project `Web interface `_. This has various practical implications: * when a software artifact is obtained from Software Heritage by resolving a SWHID, it is straightforward to verify that it is exactly the intended one: just compute the core identifier from the artefact itself, and check that it is the same as the core identifier part of the SHWID * the core identifier of a software artifact can be computed *before* its archival on Software Heritage Resolvers --------- Software Heritage resolver ~~~~~~~~~~~~~~~~~~~~~~~~~~ SWHIDs can be resolved using the Software Heritage `Web interface `_. In particular, the **root endpoint** ``/`` can be given a SWHID and will lead to the browsing page of the corresponding object, like this: ``https://archive.softwareheritage.org/``. A **dedicated** ``/resolve`` **endpoint** of the Software Heritage `Web API `_ is also available to programmatically resolve SWHIDs; see: :http:get:`/api/1/resolve/(swhid)/`. Examples: * ``_ * ``_ * ``_ * ``_ * ``_ * ``_ * ``_ Third-party resolvers ~~~~~~~~~~~~~~~~~~~~~ The following **third party resolvers** support SWHID resolution: * `Identifiers.org `_; see: ``_ (registry identifier `MIR:00000655 `_). * `Name-to-Thing (N2T) `_ Note that resolution via Identifiers.org currently only supports *core identifiers* due to `syntactic incompatibilities with qualifiers `_. Examples: * ``_ * ``_ * ``_ * ``_ * ``_ * ``_ * ``_ References ========== * Roberto Di Cosmo, Morane Gruenpeter, Stefano Zacchiroli. `Identifiers for Digital Objects: the Case of Software Source Code Preservation `_. In Proceedings of `iPRES 2018 `_: 15th International Conference on Digital Preservation, Boston, MA, USA, September 2018, 9 pages. * Roberto Di Cosmo, Morane Gruenpeter, Stefano Zacchiroli. `Referencing Source Code Artifacts: a Separate Concern in Software Citation `_. In Computing in Science and Engineering, volume 22, issue 2, pages 33-43. ISSN 1521-9615, IEEE. March 2020. diff --git a/swh/model/cli.py b/swh/model/cli.py index effdf8a..091f8ab 100644 --- a/swh/model/cli.py +++ b/swh/model/cli.py @@ -1,293 +1,293 @@ # Copyright (C) 2018-2020 The Software Heritage developers # See the AUTHORS file at the top-level directory of this distribution # License: GNU General Public License version 3, or any later version # See top-level LICENSE file for more information import os import sys from typing import Dict, List, Optional # WARNING: do not import unnecessary things here to keep cli startup time under # control try: import click except ImportError: print( "Cannot run swh-identify; the Click package is not installed." "Please install 'swh.model[cli]' for full functionality.", file=sys.stderr, ) exit(1) try: from swh.core.cli import swh as swh_cli_group except ImportError: # stub so that swh-identify can be used when swh-core isn't installed swh_cli_group = click # type: ignore from swh.model.identifiers import CoreSWHID, ObjectType CONTEXT_SETTINGS = dict(help_option_names=["-h", "--help"]) # Mapping between dulwich types and Software Heritage ones. Used by snapshot ID # computation. _DULWICH_TYPES = { b"blob": "content", b"tree": "directory", b"commit": "revision", b"tag": "release", } class CoreSWHIDParamType(click.ParamType): """Click argument that accepts a core SWHID and returns them as :class:`swh.model.identifiers.CoreSWHID` instances """ name = "SWHID" def convert(self, value, param, ctx) -> CoreSWHID: from swh.model.exceptions import ValidationError try: return CoreSWHID.from_string(value) except ValidationError as e: self.fail(f'"{value}" is not a valid core SWHID: {e}', param, ctx) def swhid_of_file(path) -> CoreSWHID: from swh.model.from_disk import Content from swh.model.hashutil import hash_to_bytes object = Content.from_file(path=path).get_data() return CoreSWHID( object_type=ObjectType.CONTENT, object_id=hash_to_bytes(object["sha1_git"]) ) def swhid_of_file_content(data) -> CoreSWHID: from swh.model.from_disk import Content from swh.model.hashutil import hash_to_bytes object = Content.from_bytes(mode=644, data=data).get_data() return CoreSWHID( object_type=ObjectType.CONTENT, object_id=hash_to_bytes(object["sha1_git"]) ) def swhid_of_dir(path: bytes, exclude_patterns: List[bytes] = None) -> CoreSWHID: from swh.model.from_disk import ( Directory, accept_all_directories, ignore_directories_patterns, ) from swh.model.hashutil import hash_to_bytes dir_filter = ( ignore_directories_patterns(path, exclude_patterns) if exclude_patterns else accept_all_directories ) object = Directory.from_disk(path=path, dir_filter=dir_filter).get_data() return CoreSWHID( object_type=ObjectType.DIRECTORY, object_id=hash_to_bytes(object["id"]) ) def swhid_of_origin(url): from swh.model.hashutil import hash_to_bytes from swh.model.identifiers import ( ExtendedObjectType, ExtendedSWHID, origin_identifier, ) return ExtendedSWHID( object_type=ExtendedObjectType.ORIGIN, object_id=hash_to_bytes(origin_identifier({"url": url})), ) def swhid_of_git_repo(path) -> CoreSWHID: try: import dulwich.repo except ImportError: raise click.ClickException( "Cannot compute snapshot identifier; the Dulwich package is not installed. " "Please install 'swh.model[cli]' for full functionality.", ) from swh.model import hashutil from swh.model.identifiers import snapshot_identifier repo = dulwich.repo.Repo(path) branches: Dict[bytes, Optional[Dict]] = {} for ref, target in repo.refs.as_dict().items(): obj = repo[target] if obj: branches[ref] = { "target": hashutil.bytehex_to_hash(target), "target_type": _DULWICH_TYPES[obj.type_name], } else: branches[ref] = None for ref, target in repo.refs.get_symrefs().items(): branches[ref] = { "target": target, "target_type": "alias", } snapshot = {"branches": branches} return CoreSWHID( object_type=ObjectType.SNAPSHOT, object_id=hashutil.hash_to_bytes(snapshot_identifier(snapshot)), ) def identify_object(obj_type, follow_symlinks, exclude_patterns, obj) -> str: from urllib.parse import urlparse if obj_type == "auto": if obj == "-" or os.path.isfile(obj): obj_type = "content" elif os.path.isdir(obj): obj_type = "directory" else: try: # URL parsing if urlparse(obj).scheme: obj_type = "origin" else: raise ValueError except ValueError: raise click.BadParameter("cannot detect object type for %s" % obj) if obj == "-": content = sys.stdin.buffer.read() swhid = str(swhid_of_file_content(content)) elif obj_type in ["content", "directory"]: path = obj.encode(sys.getfilesystemencoding()) if follow_symlinks and os.path.islink(obj): path = os.path.realpath(obj) if obj_type == "content": swhid = str(swhid_of_file(path)) elif obj_type == "directory": swhid = str( swhid_of_dir(path, [pattern.encode() for pattern in exclude_patterns]) ) elif obj_type == "origin": swhid = str(swhid_of_origin(obj)) elif obj_type == "snapshot": swhid = str(swhid_of_git_repo(obj)) else: # shouldn't happen, due to option validation raise click.BadParameter("invalid object type: " + obj_type) # note: we return original obj instead of path here, to preserve user-given # file name in output return swhid @swh_cli_group.command(context_settings=CONTEXT_SETTINGS) @click.option( "--dereference/--no-dereference", "follow_symlinks", default=True, help="follow (or not) symlinks for OBJECTS passed as arguments " + "(default: follow)", ) @click.option( "--filename/--no-filename", "show_filename", default=True, help="show/hide file name (default: show)", ) @click.option( "--type", "-t", "obj_type", default="auto", type=click.Choice(["auto", "content", "directory", "origin", "snapshot"]), help="type of object to identify (default: auto)", ) @click.option( "--exclude", "-x", "exclude_patterns", metavar="PATTERN", multiple=True, help="Exclude directories using glob patterns \ - (e.g., '*.git' to exclude all .git directories)", + (e.g., ``*.git`` to exclude all .git directories)", ) @click.option( "--verify", "-v", metavar="SWHID", type=CoreSWHIDParamType(), help="reference identifier to be compared with computed one", ) @click.argument("objects", nargs=-1, required=True) def identify( obj_type, verify, show_filename, follow_symlinks, objects, exclude_patterns, ): """Compute the Software Heritage persistent identifier (SWHID) for the given source code object(s). For more details about SWHIDs see: \b https://docs.softwareheritage.org/devel/swh-model/persistent-identifiers.html Tip: you can pass "-" to identify the content of standard input. \b - Examples: + Examples:: \b $ swh identify fork.c kmod.c sched/deadline.c swh:1:cnt:2e391c754ae730bd2d8520c2ab497c403220c6e3 fork.c swh:1:cnt:0277d1216f80ae1adeed84a686ed34c9b2931fc2 kmod.c swh:1:cnt:57b939c81bce5d06fa587df8915f05affbe22b82 sched/deadline.c \b $ swh identify --no-filename /usr/src/linux/kernel/ swh:1:dir:f9f858a48d663b3809c9e2f336412717496202ab \b $ git clone --mirror https://forge.softwareheritage.org/source/helloworld.git $ swh identify --type snapshot helloworld.git/ swh:1:snp:510aa88bdc517345d258c1fc2babcd0e1f905e93 helloworld.git """ # NoQA # overlong lines in shell examples are fine from functools import partial if verify and len(objects) != 1: raise click.BadParameter("verification requires a single object") results = zip( objects, map( partial(identify_object, obj_type, follow_symlinks, exclude_patterns), objects, ), ) if verify: swhid = next(results)[1] if str(verify) == swhid: click.echo("SWHID match: %s" % swhid) sys.exit(0) else: click.echo("SWHID mismatch: %s != %s" % (verify, swhid)) sys.exit(1) else: for (obj, swhid) in results: msg = swhid if show_filename: msg = "%s\t%s" % (swhid, os.fsdecode(obj)) click.echo(msg) if __name__ == "__main__": identify() diff --git a/swh/model/identifiers.py b/swh/model/identifiers.py index 563da9e..daa92e7 100644 --- a/swh/model/identifiers.py +++ b/swh/model/identifiers.py @@ -1,1241 +1,1239 @@ # Copyright (C) 2015-2021 The Software Heritage developers # See the AUTHORS file at the top-level directory of this distribution # License: GNU General Public License version 3, or any later version # See top-level LICENSE file for more information from __future__ import annotations import binascii import datetime import enum from functools import lru_cache import hashlib import re from typing import ( Any, Dict, Generic, Iterable, List, Optional, Tuple, Type, TypeVar, Union, ) import urllib.parse import attr from attrs_strict import type_validator from .exceptions import ValidationError from .hashutil import MultiHash, hash_git_data, hash_to_bytes, hash_to_hex class ObjectType(enum.Enum): """Possible object types of a QualifiedSWHID or CoreSWHID. The values of each variant is what is used in the SWHID's string representation.""" SNAPSHOT = "snp" REVISION = "rev" RELEASE = "rel" DIRECTORY = "dir" CONTENT = "cnt" class ExtendedObjectType(enum.Enum): """Possible object types of an ExtendedSWHID. - The variants are a superset of :cls:`ObjectType`'s""" + The variants are a superset of :class:`ObjectType`'s""" SNAPSHOT = "snp" REVISION = "rev" RELEASE = "rel" DIRECTORY = "dir" CONTENT = "cnt" ORIGIN = "ori" RAW_EXTRINSIC_METADATA = "emd" # The following are deprecated aliases of the variants defined in ObjectType # while transitioning from SWHID to QualifiedSWHID ORIGIN = "origin" SNAPSHOT = "snapshot" REVISION = "revision" RELEASE = "release" DIRECTORY = "directory" CONTENT = "content" RAW_EXTRINSIC_METADATA = "raw_extrinsic_metadata" SWHID_NAMESPACE = "swh" SWHID_VERSION = 1 SWHID_TYPES = ["snp", "rel", "rev", "dir", "cnt"] EXTENDED_SWHID_TYPES = SWHID_TYPES + ["ori", "emd"] SWHID_SEP = ":" SWHID_CTXT_SEP = ";" SWHID_QUALIFIERS = {"origin", "anchor", "visit", "path", "lines"} SWHID_RE_RAW = ( f"(?P{SWHID_NAMESPACE})" f"{SWHID_SEP}(?P{SWHID_VERSION})" f"{SWHID_SEP}(?P{'|'.join(EXTENDED_SWHID_TYPES)})" f"{SWHID_SEP}(?P[0-9a-f]{{40}})" f"({SWHID_CTXT_SEP}(?P\\S+))?" ) SWHID_RE = re.compile(SWHID_RE_RAW) @lru_cache() def identifier_to_bytes(identifier): """Convert a text identifier to bytes. Args: identifier: an identifier, either a 40-char hexadecimal string or a bytes object of length 20 Returns: The length 20 bytestring corresponding to the given identifier Raises: ValueError: if the identifier is of an unexpected type or length. """ if isinstance(identifier, bytes): if len(identifier) != 20: raise ValueError( "Wrong length for bytes identifier %s, expected 20" % len(identifier) ) return identifier if isinstance(identifier, str): if len(identifier) != 40: raise ValueError( "Wrong length for str identifier %s, expected 40" % len(identifier) ) return bytes.fromhex(identifier) raise ValueError( "Wrong type for identifier %s, expected bytes or str" % identifier.__class__.__name__ ) @lru_cache() def identifier_to_str(identifier): """Convert an identifier to an hexadecimal string. Args: identifier: an identifier, either a 40-char hexadecimal string or a bytes object of length 20 Returns: The length 40 string corresponding to the given identifier, hex encoded Raises: ValueError: if the identifier is of an unexpected type or length. """ if isinstance(identifier, str): if len(identifier) != 40: raise ValueError( "Wrong length for str identifier %s, expected 40" % len(identifier) ) return identifier if isinstance(identifier, bytes): if len(identifier) != 20: raise ValueError( "Wrong length for bytes identifier %s, expected 20" % len(identifier) ) return binascii.hexlify(identifier).decode() raise ValueError( "Wrong type for identifier %s, expected bytes or str" % identifier.__class__.__name__ ) def content_identifier(content): """Return the intrinsic identifier for a content. A content's identifier is the sha1, sha1_git and sha256 checksums of its data. Args: content: a content conforming to the Software Heritage schema Returns: A dictionary with all the hashes for the data Raises: KeyError: if the content doesn't have a data member. """ return MultiHash.from_data(content["data"]).digest() def directory_entry_sort_key(entry): """The sorting key for tree entries""" if entry["type"] == "dir": return entry["name"] + b"/" else: return entry["name"] @lru_cache() def _perms_to_bytes(perms): """Convert the perms value to its bytes representation""" oc = oct(perms)[2:] return oc.encode("ascii") def escape_newlines(snippet): """Escape the newlines present in snippet according to git rules. New lines in git manifests are escaped by indenting the next line by one space. """ if b"\n" in snippet: return b"\n ".join(snippet.split(b"\n")) else: return snippet def directory_identifier(directory): """Return the intrinsic identifier for a directory. A directory's identifier is the tree sha1 à la git of a directory listing, using the following algorithm, which is equivalent to the git algorithm for trees: 1. Entries of the directory are sorted using the name (or the name with '/' appended for directory entries) as key, in bytes order. 2. For each entry of the directory, the following bytes are output: - the octal representation of the permissions for the entry (stored in the 'perms' member), which is a representation of the entry type: - b'100644' (int 33188) for files - b'100755' (int 33261) for executable files - b'120000' (int 40960) for symbolic links - b'40000' (int 16384) for directories - b'160000' (int 57344) for references to revisions - an ascii space (b'\x20') - the entry's name (as raw bytes), stored in the 'name' member - a null byte (b'\x00') - the 20 byte long identifier of the object pointed at by the entry, stored in the 'target' member: - for files or executable files: their blob sha1_git - for symbolic links: the blob sha1_git of a file containing the link destination - for directories: their intrinsic identifier - for revisions: their intrinsic identifier (Note that there is no separator between entries) """ components = [] for entry in sorted(directory["entries"], key=directory_entry_sort_key): components.extend( [ _perms_to_bytes(entry["perms"]), b"\x20", entry["name"], b"\x00", identifier_to_bytes(entry["target"]), ] ) return identifier_to_str(hash_git_data(b"".join(components), "tree")) def format_date(date): """Convert a date object into an UTC timestamp encoded as ascii bytes. Git stores timestamps as an integer number of seconds since the UNIX epoch. However, Software Heritage stores timestamps as an integer number of microseconds (postgres type "datetime with timezone"). Therefore, we print timestamps with no microseconds as integers, and timestamps with microseconds as floating point values. We elide the trailing zeroes from microsecond values, to "future-proof" our representation if we ever need more precision in timestamps. """ if not isinstance(date, dict): raise ValueError("format_date only supports dicts, %r received" % date) seconds = date.get("seconds", 0) microseconds = date.get("microseconds", 0) if not microseconds: return str(seconds).encode() else: float_value = "%d.%06d" % (seconds, microseconds) return float_value.rstrip("0").encode() @lru_cache() def format_offset(offset, negative_utc=None): """Convert an integer number of minutes into an offset representation. The offset representation is [+-]hhmm where: - hh is the number of hours; - mm is the number of minutes. A null offset is represented as +0000. """ if offset < 0 or offset == 0 and negative_utc: sign = "-" else: sign = "+" hours = abs(offset) // 60 minutes = abs(offset) % 60 t = "%s%02d%02d" % (sign, hours, minutes) return t.encode() def normalize_timestamp(time_representation): """Normalize a time representation for processing by Software Heritage This function supports a numeric timestamp (representing a number of seconds since the UNIX epoch, 1970-01-01 at 00:00 UTC), a :obj:`datetime.datetime` object (with timezone information), or a normalized Software Heritage time representation (idempotency). Args: time_representation: the representation of a timestamp Returns: dict: a normalized dictionary with three keys: - timestamp: a dict with two optional keys: - seconds: the integral number of seconds since the UNIX epoch - microseconds: the integral number of microseconds - offset: the timezone offset as a number of minutes relative to UTC - negative_utc: a boolean representing whether the offset is -0000 when offset = 0. """ if time_representation is None: return None negative_utc = False if isinstance(time_representation, dict): ts = time_representation["timestamp"] if isinstance(ts, dict): seconds = ts.get("seconds", 0) microseconds = ts.get("microseconds", 0) elif isinstance(ts, int): seconds = ts microseconds = 0 else: raise ValueError( "normalize_timestamp received non-integer timestamp member:" " %r" % ts ) offset = time_representation["offset"] if "negative_utc" in time_representation: negative_utc = time_representation["negative_utc"] if negative_utc is None: negative_utc = False elif isinstance(time_representation, datetime.datetime): seconds = int(time_representation.timestamp()) microseconds = time_representation.microsecond utcoffset = time_representation.utcoffset() if utcoffset is None: raise ValueError( "normalize_timestamp received datetime without timezone: %s" % time_representation ) # utcoffset is an integer number of minutes seconds_offset = utcoffset.total_seconds() offset = int(seconds_offset) // 60 elif isinstance(time_representation, int): seconds = time_representation microseconds = 0 offset = 0 else: raise ValueError( "normalize_timestamp received non-integer timestamp:" " %r" % time_representation ) return { "timestamp": {"seconds": seconds, "microseconds": microseconds,}, "offset": offset, "negative_utc": negative_utc, } def format_author(author): """Format the specification of an author. An author is either a byte string (passed unchanged), or a dict with three keys, fullname, name and email. If the fullname exists, return it; if it doesn't, we construct a fullname using the following heuristics: if the name value is None, we return the email in angle brackets, else, we return the name, a space, and the email in angle brackets. """ if isinstance(author, bytes) or author is None: return author if "fullname" in author: return author["fullname"] ret = [] if author["name"] is not None: ret.append(author["name"]) if author["email"] is not None: ret.append(b"".join([b"<", author["email"], b">"])) return b" ".join(ret) def format_manifest( headers: Iterable[Tuple[bytes, bytes]], message: Optional[bytes] = None, ) -> bytes: """Format a manifest comprised of a sequence of `headers` and an optional `message`. The manifest format, compatible with the git format for tag and commit objects, is as follows: - for each `key`, `value` in `headers`, emit: - the `key`, literally - an ascii space (``\\x20``) - the `value`, with newlines escaped using :func:`escape_newlines`, - an ascii newline (``\\x0a``) - if the `message` is not None, emit: - an ascii newline (``\\x0a``) - the `message`, literally Args: headers: a sequence of key/value headers stored in the manifest; message: an optional message used to trail the manifest. Returns: the formatted manifest as bytes """ entries: List[bytes] = [] for key, value in headers: entries.extend((key, b" ", escape_newlines(value), b"\n")) if message is not None: entries.extend((b"\n", message)) return b"".join(entries) def hash_manifest( type: str, headers: Iterable[Tuple[bytes, bytes]], message: Optional[bytes] = None, ): """Hash the manifest of an object of type `type`, comprised of a sequence of `headers` and an optional `message`. Before hashing, the manifest is serialized with the :func:`format_manifest` function. We then use the git "salted sha1" (:func:`swh.model.hashutil.hash_git_data`) with the given `type` to hash the manifest. Args: type: the type of object for which we're computing a manifest (e.g. "tag", "commit", ...) headers: a sequence of key/value headers stored in the manifest; message: an optional message used to trail the manifest. """ manifest = format_manifest(headers, message) return hash_git_data(manifest, type) def format_author_data(author, date_offset) -> bytes: """Format authorship data according to git standards. Git authorship data has two components: - an author specification, usually a name and email, but in practice an arbitrary bytestring - optionally, a timestamp with a UTC offset specification The authorship data is formatted thus:: `name and email`[ `timestamp` `utc_offset`] The timestamp is encoded as a (decimal) number of seconds since the UNIX epoch (1970-01-01 at 00:00 UTC). As an extension to the git format, we support fractional timestamps, using a dot as the separator for the decimal part. The utc offset is a number of minutes encoded as '[+-]HHMM'. Note that some tools can pass a negative offset corresponding to the UTC timezone ('-0000'), which is valid and is encoded as such. Args: author: an author specification (dict with two bytes values: name and email, or byte value) date_offset: a normalized date/time representation as returned by :func:`normalize_timestamp`. Returns: the byte string containing the authorship data """ ret = [format_author(author)] date_offset = normalize_timestamp(date_offset) if date_offset is not None: date_f = format_date(date_offset["timestamp"]) offset_f = format_offset(date_offset["offset"], date_offset["negative_utc"]) ret.extend([b" ", date_f, b" ", offset_f]) return b"".join(ret) def revision_identifier(revision): """Return the intrinsic identifier for a revision. The fields used for the revision identifier computation are: - directory - parents - author - author_date - committer - committer_date - extra_headers or metadata -> extra_headers - message A revision's identifier is the 'git'-checksum of a commit manifest constructed as follows (newlines are a single ASCII newline character):: tree [for each parent in parents] parent [end for each parents] author committer [for each key, value in extra_headers] [end for each extra_headers] The directory identifier is the ascii representation of its hexadecimal encoding. Author and committer are formatted with the :func:`format_author` function. Dates are formatted with the :func:`format_offset` function. Extra headers are an ordered list of [key, value] pairs. Keys are strings and get encoded to utf-8 for identifier computation. Values are either byte strings, unicode strings (that get encoded to utf-8), or integers (that get encoded to their utf-8 decimal representation). Multiline extra header values are escaped by indenting the continuation lines with one ascii space. If the message is None, the manifest ends with the last header. Else, the message is appended to the headers after an empty line. The checksum of the full manifest is computed using the 'commit' git object type. """ headers = [(b"tree", identifier_to_str(revision["directory"]).encode())] for parent in revision["parents"]: if parent: headers.append((b"parent", identifier_to_str(parent).encode())) headers.append( (b"author", format_author_data(revision["author"], revision["date"])) ) headers.append( ( b"committer", format_author_data(revision["committer"], revision["committer_date"]), ) ) # Handle extra headers metadata = revision.get("metadata") or {} extra_headers = revision.get("extra_headers", ()) if not extra_headers and "extra_headers" in metadata: extra_headers = metadata["extra_headers"] headers.extend(extra_headers) return identifier_to_str(hash_manifest("commit", headers, revision["message"])) def target_type_to_git(target_type): """Convert a software heritage target type to a git object type""" return { "content": b"blob", "directory": b"tree", "revision": b"commit", "release": b"tag", "snapshot": b"refs", }[target_type] def release_identifier(release): """Return the intrinsic identifier for a release.""" headers = [ (b"object", identifier_to_str(release["target"]).encode()), (b"type", target_type_to_git(release["target_type"])), (b"tag", release["name"]), ] if "author" in release and release["author"]: headers.append( (b"tagger", format_author_data(release["author"], release["date"])) ) return identifier_to_str(hash_manifest("tag", headers, release["message"])) def snapshot_identifier(snapshot, *, ignore_unresolved=False): """Return the intrinsic identifier for a snapshot. Snapshots are a set of named branches, which are pointers to objects at any level of the Software Heritage DAG. As well as pointing to other objects in the Software Heritage DAG, branches can also be *alias*es, in which case their target is the name of another branch in the same snapshot, or *dangling*, in which case the target is unknown (and represented by the ``None`` value). A snapshot identifier is a salted sha1 (using the git hashing algorithm with the ``snapshot`` object type) of a manifest following the algorithm: 1. Branches are sorted using the name as key, in bytes order. 2. For each branch, the following bytes are output: - the type of the branch target: - ``content``, ``directory``, ``revision``, ``release`` or ``snapshot`` for the corresponding entries in the DAG; - ``alias`` for branches referencing another branch; - ``dangling`` for dangling branches - an ascii space (``\\x20``) - the branch name (as raw bytes) - a null byte (``\\x00``) - the length of the target identifier, as an ascii-encoded decimal number (``20`` for current intrinsic identifiers, ``0`` for dangling branches, the length of the target branch name for branch aliases) - a colon (``:``) - the identifier of the target object pointed at by the branch, stored in the 'target' member: - for contents: their *sha1_git* - for directories, revisions, releases or snapshots: their intrinsic identifier - for branch aliases, the name of the target branch (as raw bytes) - for dangling branches, the empty string Note that, akin to directory manifests, there is no separator between entries. Because of symbolic branches, identifiers are of arbitrary length but are length-encoded to avoid ambiguity. Args: snapshot (dict): the snapshot of which to compute the identifier. A single entry is needed, ``'branches'``, which is itself a :class:`dict` mapping each branch to its target ignore_unresolved (bool): if `True`, ignore unresolved branch aliases. Returns: str: the intrinsic identifier for `snapshot` """ unresolved = [] lines = [] for name, target in sorted(snapshot["branches"].items()): if not target: target_type = b"dangling" target_id = b"" elif target["target_type"] == "alias": target_type = b"alias" target_id = target["target"] if target_id not in snapshot["branches"] or target_id == name: unresolved.append((name, target_id)) else: target_type = target["target_type"].encode() target_id = identifier_to_bytes(target["target"]) lines.extend( [ target_type, b"\x20", name, b"\x00", ("%d:" % len(target_id)).encode(), target_id, ] ) if unresolved and not ignore_unresolved: raise ValueError( "Branch aliases unresolved: %s" % ", ".join("%s -> %s" % x for x in unresolved), unresolved, ) return identifier_to_str(hash_git_data(b"".join(lines), "snapshot")) def origin_identifier(origin): """Return the intrinsic identifier for an origin. An origin's identifier is the sha1 checksum of the entire origin URL """ return hashlib.sha1(origin["url"].encode("utf-8")).hexdigest() def raw_extrinsic_metadata_identifier(metadata: Dict[str, Any]) -> str: """Return the intrinsic identifier for a RawExtrinsicMetadata object. A raw_extrinsic_metadata identifier is a salted sha1 (using the git hashing algorithm with the ``raw_extrinsic_metadata`` object type) of - a manifest following the format: - - ``` - target $ExtendedSwhid - discovery_date $Timestamp - authority $StrWithoutSpaces $IRI - fetcher $Str $Version - format $StrWithoutSpaces - origin $IRI <- optional - visit $IntInDecimal <- optional - snapshot $CoreSwhid <- optional - release $CoreSwhid <- optional - revision $CoreSwhid <- optional - path $Bytes <- optional - directory $CoreSwhid <- optional - - $MetadataBytes - ``` + a manifest following the format:: + + target $ExtendedSwhid + discovery_date $Timestamp + authority $StrWithoutSpaces $IRI + fetcher $Str $Version + format $StrWithoutSpaces + origin $IRI <- optional + visit $IntInDecimal <- optional + snapshot $CoreSwhid <- optional + release $CoreSwhid <- optional + revision $CoreSwhid <- optional + path $Bytes <- optional + directory $CoreSwhid <- optional + + $MetadataBytes $IRI must be RFC 3987 IRIs (so they may contain newlines, that are escaped as described below) $StrWithoutSpaces and $Version are ASCII strings, and may not contain spaces. $Str is an UTF-8 string. $CoreSwhid are core SWHIDs, as defined in :ref:`persistent-identifiers`. $ExtendedSwhid is a core SWHID, with extra types allowed ('ori' for origins and 'emd' for raw extrinsic metadata) $Timestamp is a decimal representation of the rounded-down integer number of seconds since the UNIX epoch (1970-01-01 00:00:00 UTC), with no leading '0' (unless the timestamp value is zero) and no timezone. It may be negative by prefixing it with a '-', which must not be followed by a '0'. Newlines in $Bytes, $Str, and $Iri are escaped as with other git fields, ie. by adding a space after them. Returns: - str: the intrinsic identifier for `metadata` + str: the intrinsic identifier for ``metadata`` """ # equivalent to using math.floor(dt.timestamp()) to round down, # as int(dt.timestamp()) rounds toward zero, # which would map two seconds on the 0 timestamp. # # This should never be an issue in practice as Software Heritage didn't # start collecting metadata before 2015. timestamp = ( metadata["discovery_date"] .astimezone(datetime.timezone.utc) .replace(microsecond=0) .timestamp() ) assert timestamp.is_integer() headers = [ (b"target", str(metadata["target"]).encode()), (b"discovery_date", str(int(timestamp)).encode("ascii")), ( b"authority", f"{metadata['authority']['type']} {metadata['authority']['url']}".encode(), ), ( b"fetcher", f"{metadata['fetcher']['name']} {metadata['fetcher']['version']}".encode(), ), (b"format", metadata["format"].encode()), ] for key in ( "origin", "visit", "snapshot", "release", "revision", "path", "directory", ): if metadata.get(key) is not None: value: bytes if key == "path": value = metadata[key] else: value = str(metadata[key]).encode() headers.append((key.encode("ascii"), value)) return identifier_to_str( hash_manifest("raw_extrinsic_metadata", headers, metadata["metadata"]) ) def extid_identifier(extid: Dict[str, Any]) -> str: """Return the intrinsic identifier for an ExtID object. An ExtID identifier is a salted sha1 (using the git hashing algorithm with the ``extid`` object type) of a manifest following the format: ``` extid_type $StrWithoutSpaces extid $Bytes target $CoreSwhid ``` $StrWithoutSpaces is an ASCII string, and may not contain spaces. Newlines in $Bytes are escaped as with other git fields, ie. by adding a space after them. Returns: str: the intrinsic identifier for `extid` """ headers = [ (b"extid_type", extid["extid_type"].encode("ascii")), (b"extid", extid["extid"]), (b"target", str(extid["target"]).encode("ascii")), ] return identifier_to_str(hash_manifest("extid", headers)) # type of the "object_type" attribute of the SWHID class; either # ObjectType or ExtendedObjectType _TObjectType = TypeVar("_TObjectType", ObjectType, ExtendedObjectType) # the SWHID class itself (this is used so that X.from_string() can return X # for all X subclass of _BaseSWHID) _TSWHID = TypeVar("_TSWHID", bound="_BaseSWHID") @attr.s(frozen=True, kw_only=True) class _BaseSWHID(Generic[_TObjectType]): """Common base class for CoreSWHID, QualifiedSWHID, and ExtendedSWHID. This is an "abstract" class and should not be instantiated directly; it only exists to deduplicate code between these three SWHID classes.""" namespace = attr.ib(type=str, default=SWHID_NAMESPACE) """the namespace of the identifier, defaults to ``swh``""" scheme_version = attr.ib(type=int, default=SWHID_VERSION) """the scheme version of the identifier, defaults to 1""" # overridden by subclasses object_type: _TObjectType """the type of object the identifier points to""" object_id = attr.ib(type=bytes, validator=type_validator()) """object's identifier""" @namespace.validator def check_namespace(self, attribute, value): if value != SWHID_NAMESPACE: raise ValidationError( "Invalid SWHID: invalid namespace: %(namespace)s", params={"namespace": value}, ) @scheme_version.validator def check_scheme_version(self, attribute, value): if value != SWHID_VERSION: raise ValidationError( "Invalid SWHID: invalid version: %(version)s", params={"version": value} ) @object_id.validator def check_object_id(self, attribute, value): if len(value) != 20: raise ValidationError( "Invalid SWHID: invalid checksum: %(object_id)s", params={"object_id": hash_to_hex(value)}, ) def __str__(self) -> str: return SWHID_SEP.join( [ self.namespace, str(self.scheme_version), self.object_type.value, hash_to_hex(self.object_id), ] ) @classmethod def from_string(cls: Type[_TSWHID], s: str) -> _TSWHID: parts = _parse_swhid(s) if parts.pop("qualifiers"): raise ValidationError(f"{cls.__name__} does not support qualifiers.") try: return cls(**parts) except ValueError as e: raise ValidationError( "ValueError: %(args)s", params={"args": e.args} ) from None @attr.s(frozen=True, kw_only=True) class CoreSWHID(_BaseSWHID[ObjectType]): """ Dataclass holding the relevant info associated to a SoftWare Heritage persistent IDentifier (SWHID). Unlike `QualifiedSWHID`, it is restricted to core SWHIDs, ie. SWHIDs with no qualifiers. Raises: swh.model.exceptions.ValidationError: In case of invalid object type or id To get the raw SWHID string from an instance of this class, use the :func:`str` function: >>> swhid = CoreSWHID( ... object_type=ObjectType.CONTENT, ... object_id=bytes.fromhex('8ff44f081d43176474b267de5451f2c2e88089d0'), ... ) >>> str(swhid) 'swh:1:cnt:8ff44f081d43176474b267de5451f2c2e88089d0' And vice-versa with :meth:`CoreSWHID.from_string`: >>> swhid == CoreSWHID.from_string( ... "swh:1:cnt:8ff44f081d43176474b267de5451f2c2e88089d0" ... ) True """ object_type = attr.ib( type=ObjectType, validator=type_validator(), converter=ObjectType ) """the type of object the identifier points to""" def to_extended(self) -> ExtendedSWHID: """Converts this CoreSWHID into an ExtendedSWHID. As ExtendedSWHID is a superset of CoreSWHID, this is lossless.""" return ExtendedSWHID( namespace=self.namespace, scheme_version=self.scheme_version, object_type=ExtendedObjectType(self.object_type.value), object_id=self.object_id, ) def _parse_core_swhid(swhid: Union[str, CoreSWHID, None]) -> Optional[CoreSWHID]: if swhid is None or isinstance(swhid, CoreSWHID): return swhid else: return CoreSWHID.from_string(swhid) def _parse_lines_qualifier( lines: Union[str, Tuple[int, Optional[int]], None] ) -> Optional[Tuple[int, Optional[int]]]: try: if lines is None or isinstance(lines, tuple): return lines elif "-" in lines: (from_, to) = lines.split("-", 2) return (int(from_), int(to)) else: return (int(lines), None) except ValueError: raise ValidationError( "Invalid format for the lines qualifier: %(lines)s", params={"lines": lines} ) def _parse_path_qualifier(path: Union[str, bytes, None]) -> Optional[bytes]: if path is None or isinstance(path, bytes): return path else: return urllib.parse.unquote_to_bytes(path) @attr.s(frozen=True, kw_only=True) class QualifiedSWHID(_BaseSWHID[ObjectType]): """ Dataclass holding the relevant info associated to a SoftWare Heritage persistent IDentifier (SWHID) Raises: swh.model.exceptions.ValidationError: In case of invalid object type or id To get the raw SWHID string from an instance of this class, use the :func:`str` function: >>> swhid = QualifiedSWHID( ... object_type=ObjectType.CONTENT, ... object_id=bytes.fromhex('8ff44f081d43176474b267de5451f2c2e88089d0'), ... lines=(5, 10), ... ) >>> str(swhid) 'swh:1:cnt:8ff44f081d43176474b267de5451f2c2e88089d0;lines=5-10' And vice-versa with :meth:`QualifiedSWHID.from_string`: >>> swhid == QualifiedSWHID.from_string( ... "swh:1:cnt:8ff44f081d43176474b267de5451f2c2e88089d0;lines=5-10" ... ) True """ object_type = attr.ib( type=ObjectType, validator=type_validator(), converter=ObjectType ) """the type of object the identifier points to""" # qualifiers: origin = attr.ib(type=Optional[str], default=None, validator=type_validator()) """the software origin where an object has been found or observed in the wild, as an URI""" visit = attr.ib(type=Optional[CoreSWHID], default=None, converter=_parse_core_swhid) """the core identifier of a snapshot corresponding to a specific visit of a repository containing the designated object""" anchor = attr.ib( type=Optional[CoreSWHID], default=None, validator=type_validator(), converter=_parse_core_swhid, ) """a designated node in the Merkle DAG relative to which a path to the object is specified, as the core identifier of a directory, a revision, a release, or a snapshot""" path = attr.ib( type=Optional[bytes], default=None, validator=type_validator(), converter=_parse_path_qualifier, ) """the absolute file path, from the root directory associated to the anchor node, to the object; when the anchor denotes a directory or a revision, and almost always when it’s a release, the root directory is uniquely determined; when the anchor denotes a snapshot, the root directory is the one pointed to by HEAD (possibly indirectly), and undefined if such a reference is missing""" lines = attr.ib( type=Optional[Tuple[int, Optional[int]]], default=None, validator=type_validator(), converter=_parse_lines_qualifier, ) """lines: line number(s) of interest, usually within a content object""" @visit.validator def check_visit(self, attribute, value): if value and value.object_type != ObjectType.SNAPSHOT: raise ValidationError( "The 'visit' qualifier must be a 'snp' SWHID, not '%(type)s'", params={"type": value.object_type.value}, ) @anchor.validator def check_anchor(self, attribute, value): if value and value.object_type not in ( ObjectType.DIRECTORY, ObjectType.REVISION, ObjectType.RELEASE, ObjectType.SNAPSHOT, ): raise ValidationError( "The 'visit' qualifier must be a 'dir', 'rev', 'rel', or 'snp' SWHID, " "not '%s(type)s'", params={"type": value.object_type.value}, ) def qualifiers(self) -> Dict[str, str]: origin = self.origin if origin: unescaped_origin = origin origin = origin.replace(";", "%3B") assert urllib.parse.unquote_to_bytes( origin ) == urllib.parse.unquote_to_bytes( unescaped_origin ), "Escaping ';' in the origin qualifier corrupted the origin URL." d: Dict[str, Optional[str]] = { "origin": origin, "visit": str(self.visit) if self.visit else None, "anchor": str(self.anchor) if self.anchor else None, "path": ( urllib.parse.quote_from_bytes(self.path) if self.path is not None else None ), "lines": ( "-".join(str(line) for line in self.lines if line is not None) if self.lines else None ), } return {k: v for (k, v) in d.items() if v is not None} def __str__(self) -> str: swhid = SWHID_SEP.join( [ self.namespace, str(self.scheme_version), self.object_type.value, hash_to_hex(self.object_id), ] ) qualifiers = self.qualifiers() if qualifiers: for k, v in qualifiers.items(): swhid += "%s%s=%s" % (SWHID_CTXT_SEP, k, v) return swhid @classmethod def from_string(cls, s: str) -> QualifiedSWHID: parts = _parse_swhid(s) qualifiers = parts.pop("qualifiers") invalid_qualifiers = set(qualifiers) - SWHID_QUALIFIERS if invalid_qualifiers: raise ValidationError( "Invalid qualifier(s): %(qualifiers)s", params={"qualifiers": ", ".join(invalid_qualifiers)}, ) try: return QualifiedSWHID(**parts, **qualifiers) except ValueError as e: raise ValidationError( "ValueError: %(args)s", params={"args": e.args} ) from None @attr.s(frozen=True, kw_only=True) class ExtendedSWHID(_BaseSWHID[ExtendedObjectType]): """ Dataclass holding the relevant info associated to a SoftWare Heritage persistent IDentifier (SWHID). It extends `CoreSWHID`, by allowing non-standard object types; and should only be used internally to Software Heritage. Raises: swh.model.exceptions.ValidationError: In case of invalid object type or id To get the raw SWHID string from an instance of this class, use the :func:`str` function: >>> swhid = ExtendedSWHID( ... object_type=ExtendedObjectType.CONTENT, ... object_id=bytes.fromhex('8ff44f081d43176474b267de5451f2c2e88089d0'), ... ) >>> str(swhid) 'swh:1:cnt:8ff44f081d43176474b267de5451f2c2e88089d0' And vice-versa with :meth:`CoreSWHID.from_string`: >>> swhid == ExtendedSWHID.from_string( ... "swh:1:cnt:8ff44f081d43176474b267de5451f2c2e88089d0" ... ) True """ object_type = attr.ib( type=ExtendedObjectType, validator=type_validator(), converter=ExtendedObjectType, ) """the type of object the identifier points to""" def _parse_swhid(swhid: str) -> Dict[str, Any]: """Parse a Software Heritage identifier (SWHID) from string (see: :ref:`persistent-identifiers`.) This is for internal use; use :meth:`CoreSWHID.from_string`, :meth:`QualifiedSWHID.from_string`, or :meth:`ExtendedSWHID.from_string` instead, as they perform validation and build a dataclass. Args: swhid (str): A persistent identifier Raises: swh.model.exceptions.ValidationError: if passed string is not a valid SWHID """ m = SWHID_RE.fullmatch(swhid) if not m: raise ValidationError( "Invalid SWHID: invalid syntax: %(swhid)s", params={"swhid": swhid} ) parts: Dict[str, Any] = m.groupdict() qualifiers_raw = parts["qualifiers"] parts["qualifiers"] = {} if qualifiers_raw: for qualifier in qualifiers_raw.split(SWHID_CTXT_SEP): try: k, v = qualifier.split("=", maxsplit=1) parts["qualifiers"][k] = v except ValueError: raise ValidationError( "Invalid SWHID: invalid qualifier: %(qualifier)s", params={"qualifier": qualifier}, ) parts["scheme_version"] = int(parts["scheme_version"]) parts["object_id"] = hash_to_bytes(parts["object_id"]) return parts diff --git a/swh/model/merkle.py b/swh/model/merkle.py index e84ef9d..098c872 100644 --- a/swh/model/merkle.py +++ b/swh/model/merkle.py @@ -1,311 +1,313 @@ # Copyright (C) 2017-2020 The Software Heritage developers # See the AUTHORS file at the top-level directory of this distribution # License: GNU General Public License version 3, or any later version # See top-level LICENSE file for more information """Merkle tree data structure""" import abc from collections.abc import Mapping -from typing import Iterator, List, Set +from typing import Dict, Iterator, List, Set def deep_update(left, right): """Recursively update the left mapping with deeply nested values from the right mapping. This function is useful to merge the results of several calls to :func:`MerkleNode.collect`. Arguments: left: a mapping (modified by the update operation) right: a mapping Returns: the left mapping, updated with nested values from the right mapping Example: >>> a = { ... 'key1': { ... 'key2': { ... 'key3': 'value1/2/3', ... }, ... }, ... } >>> deep_update(a, { ... 'key1': { ... 'key2': { ... 'key4': 'value1/2/4', ... }, ... }, ... }) == { ... 'key1': { ... 'key2': { ... 'key3': 'value1/2/3', ... 'key4': 'value1/2/4', ... }, ... }, ... } True >>> deep_update(a, { ... 'key1': { ... 'key2': { ... 'key3': 'newvalue1/2/3', ... }, ... }, ... }) == { ... 'key1': { ... 'key2': { ... 'key3': 'newvalue1/2/3', ... 'key4': 'value1/2/4', ... }, ... }, ... } True """ for key, rvalue in right.items(): if isinstance(rvalue, Mapping): new_lvalue = deep_update(left.get(key, {}), rvalue) left[key] = new_lvalue else: left[key] = rvalue return left class MerkleNode(dict, metaclass=abc.ABCMeta): """Representation of a node in a Merkle Tree. A (generalized) `Merkle Tree`_ is a tree in which every node is labeled with a hash of its own data and the hash of its children. .. _Merkle Tree: https://en.wikipedia.org/wiki/Merkle_tree In pseudocode:: node.hash = hash(node.data + sum(child.hash for child in node.children)) This class efficiently implements the Merkle Tree data structure on top of a Python :class:`dict`, minimizing hash computations and new data collections when updating nodes. Node data is stored in the :attr:`data` attribute, while (named) children are stored as items of the underlying dictionary. Addition, update and removal of objects are instrumented to automatically 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 objects can be collected. The collection of updated data from the tree is implemented through the :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"] - """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): super().__init__() self.parents = [] self.data = data self.__hash = None self.collected = False def __eq__(self, other): return ( isinstance(other, MerkleNode) and super().__eq__(other) and self.data == other.data ) def __ne__(self, other): return not self.__eq__(other) def invalidate_hash(self): """Invalidate the cached hash of the current node.""" if not self.__hash: return self.__hash = None self.collected = False for parent in self.parents: parent.invalidate_hash() def update_hash(self, *, force=False): """Recursively compute the hash of the current node. Args: force (bool): invalidate the cache and force the computation for this node and all children. """ if self.__hash and not force: return self.__hash if force: self.invalidate_hash() for child in self.values(): child.update_hash(force=force) self.__hash = self.compute_hash() return self.__hash @property def hash(self): """The hash of the current node, as calculated by :func:`compute_hash`. """ return self.update_hash() @abc.abstractmethod def compute_hash(self): """Compute the hash of the current node. The hash should depend on the data of the node, as well as on hashes of the children nodes. """ raise NotImplementedError("Must implement compute_hash method") def __setitem__(self, name, new_child): """Add a child, invalidating the current hash""" self.invalidate_hash() super().__setitem__(name, new_child) new_child.parents.append(self) def __delitem__(self, name): """Remove a child, invalidating the current hash""" if name in self: self.invalidate_hash() self[name].parents.remove(self) super().__delitem__(name) else: raise KeyError(name) def update(self, new_children): """Add several named children from a dictionary""" if not new_children: return self.invalidate_hash() for name, new_child in new_children.items(): new_child.parents.append(self) if name in self: self[name].parents.remove(self) super().update(new_children) def get_data(self, **kwargs): """Retrieve and format the collected data for the current node, for use by :func:`collect`. Can be overridden, for instance when you want the collected data to contain information about the child nodes. Arguments: kwargs: allow subclasses to alter behaviour depending on how :func:`collect` is called. Returns: data formatted for :func:`collect` """ return self.data def collect_node(self, **kwargs): """Collect the data for the current node, for use by :func:`collect`. Arguments: kwargs: passed as-is to :func:`get_data`. Returns: A :class:`dict` compatible with :func:`collect`. """ if not self.collected: self.collected = True return {self.object_type: {self.hash: self.get_data(**kwargs)}} else: return {} def collect(self, **kwargs): """Collect the data for all nodes in the subtree rooted at `self`. The data is deduplicated by type and by hash. Arguments: kwargs: passed as-is to :func:`get_data`. Returns: A :class:`dict` with the following structure:: { 'typeA': { node1.hash: node1.get_data(), node2.hash: node2.get_data(), }, 'typeB': { node3.hash: node3.get_data(), ... }, ... } """ ret = self.collect_node(**kwargs) for child in self.values(): deep_update(ret, child.collect(**kwargs)) return ret def reset_collect(self): """Recursively unmark collected nodes in the subtree rooted at `self`. This lets the caller use :func:`collect` again. """ self.collected = False for child in self.values(): child.reset_collect() def iter_tree(self) -> Iterator["MerkleNode"]: """Yields all children nodes, recursively. Common nodes are deduplicated. """ yield from self._iter_tree(set()) def _iter_tree(self, seen: Set[bytes]) -> Iterator["MerkleNode"]: if self.hash not in seen: seen.add(self.hash) yield self for child in self.values(): yield from child._iter_tree(seen=seen) class MerkleLeaf(MerkleNode): """A leaf to a Merkle tree. A Merkle leaf is simply a Merkle node with children disabled. """ __slots__ = [] # type: List[str] def __setitem__(self, name, child): raise ValueError("%s is a leaf" % self.__class__.__name__) def __getitem__(self, name): raise ValueError("%s is a leaf" % self.__class__.__name__) def __delitem__(self, name): raise ValueError("%s is a leaf" % self.__class__.__name__) def update(self, new_children): """Children update operation. Disabled for leaves.""" raise ValueError("%s is a leaf" % self.__class__.__name__)