comparison rust/hg-core/src/revlog/nodemap.rs @ 50419:3894763d92f8

rustdoc: nodemap doc refreshing

Not pretending to be comprehensive.

- correcting some inconsistencies
- adding a few missing doc-comments
- adding more cross references (in some cases it's right beside
  the current documentation item, but it will nevertheless also
  be useful, because `rustdoc` will warn us if inconsistencies
  arise).

50418:f2deaca3450e

use std::ops::Index;

#[derive(Debug, PartialEq)]
pub enum NodeMapError {
    /// A `NodePrefix` matches several [`Revision`]s.
    MultipleResults,
    /// A `Revision` stored in the nodemap could not be found in the index
    RevisionNotInIndex(Revision),
}

/// Mapping system from Mercurial nodes to revision numbers.
///
/// ## `RevlogIndex` and `NodeMap`
///
/// One way to think about their relationship is that
/// the `NodeMap` is a prefix-oriented reverse index of the `Node` information
/// carried by a [`RevlogIndex`].
///
/// Many of the methods in this trait take a `RevlogIndex` argument
/// which is used for validation of their results. This index must naturally
/// be the one the `NodeMap` is about, and it must be consistent.
///
/// Notably, the `NodeMap` must not store
/// information about more `Revision` values than there are in the index.
/// In these methods, an encountered `Revision` is not in the index, a
/// [`RevisionNotInIndex`] error is returned.
///
/// In insert operations, the rule is thus that the `NodeMap` must always
/// be updated after the `RevlogIndex`
/// be updated first, and the `NodeMap` second.
///
/// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex
/// [`RevlogIndex`]: ../trait.RevlogIndex.html
pub trait NodeMap {
    /// Find the unique `Revision` having the given `Node`
    ///
    /// If no Revision matches the given `Node`, `Ok(None)` is returned.
    fn find_node(

        &self,
        idx: &impl RevlogIndex,
        node_prefix: NodePrefix,
    ) -> Result<Option<usize>, NodeMapError>;

    /// Same as `unique_prefix_len_bin`, with a full `Node` as input
    fn unique_prefix_len_node(
        &self,
        idx: &impl RevlogIndex,
        node: &Node,
    ) -> Result<Option<usize>, NodeMapError> {

            Element::Rev(rev) => -rev - 2,
        })
    }
}

/// A logical block of the `NodeTree`, packed with a fixed size.
///
/// These are always used in container types implementing `Index<Block>`,
/// such as `&Block`
///
/// As an array of integers, its ith element encodes that the

/// rather than 0 and the [`Revision`] range upper limit of -2 instead of -1.
///
/// Another related difference is that `NULL_REVISION` (-1) is not
/// represented at all, because we want an immutable empty nodetree
/// to be valid.

const ELEMENTS_PER_BLOCK: usize = 16; // number of different values in a nybble

#[derive(Copy, Clone, BytesCast, PartialEq)]
#[repr(transparent)]
pub struct Block([RawElement; ELEMENTS_PER_BLOCK]);

impl Block {

/// A mutable 16-radix tree with the root block logically at the end
///
/// Because of the append only nature of our node trees, we need to
/// keep the original untouched and store new blocks separately.
///
/// The mutable root `Block` is kept apart so that we don't have to rebump
/// it on each insertion.
pub struct NodeTree {
    readonly: Box<dyn Deref<Target = [Block]> + Send>,
    growable: Vec<Block>,
    root: Block,

            &self.growable[i - ro_len]
        }
    }
}

/// Return `None` unless the `Node` for `rev` has given prefix in `index`.
fn has_prefix_or_none(
    idx: &impl RevlogIndex,
    prefix: NodePrefix,
    rev: Revision,
) -> Result<Option<Revision>, NodeMapError> {

            }
        })
}

/// validate that the candidate's node starts indeed with given prefix,
/// and treat ambiguities related to `NULL_REVISION`.
///
/// From the data in the NodeTree, one can only conclude that some
/// revision is the only one for a *subprefix* of the one being looked up.
fn validate_candidate(
    idx: &impl RevlogIndex,

        }
    }

    /// Create from an opaque bunch of bytes
    ///
    /// The created `NodeTreeBytes` from `buffer`,
    /// of which exactly `amount` bytes are used.
    ///
    /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects.
    /// - `offset` allows for the final file format to include fixed data
    ///   (generation number, behavioural flags)
    /// - `amount` is expressed in bytes, and is not automatically derived from
    ///   `bytes`, so that a caller that manages them atomically can perform
    ///   temporary disk serializations and still rollback easily if needed.
    ///   First use-case for this would be to support Mercurial shell hooks.
    ///

50419:3894763d92f8

use std::ops::Index;

#[derive(Debug, PartialEq)]
pub enum NodeMapError {
    /// A `NodePrefix` matches several [`Revision`]s.
    ///
    /// This can be returned by methods meant for (at most) one match.
    MultipleResults,
    /// A `Revision` stored in the nodemap could not be found in the index
    RevisionNotInIndex(Revision),
}

/// Mapping system from Mercurial nodes to revision numbers.
///
/// ## `RevlogIndex` and `NodeMap`
///
/// One way to think about their relationship is that
/// the `NodeMap` is a prefix-oriented reverse index of the [`Node`]
/// information carried by a [`RevlogIndex`].
///
/// Many of the methods in this trait take a `RevlogIndex` argument
/// which is used for validation of their results. This index must naturally
/// be the one the `NodeMap` is about, and it must be consistent.
///
/// Notably, the `NodeMap` must not store
/// information about more `Revision` values than there are in the index.
/// In these methods, an encountered `Revision` is not in the index, a
/// [RevisionNotInIndex](NodeMapError) error is returned.
///
/// In insert operations, the rule is thus that the `NodeMap` must always
/// be updated after the `RevlogIndex` it is about.
pub trait NodeMap {
    /// Find the unique `Revision` having the given `Node`
    ///
    /// If no Revision matches the given `Node`, `Ok(None)` is returned.
    fn find_node(

        &self,
        idx: &impl RevlogIndex,
        node_prefix: NodePrefix,
    ) -> Result<Option<usize>, NodeMapError>;

    /// Same as [unique_prefix_len_bin](Self::unique_prefix_len_bin), with
    /// a full [`Node`] as input
    fn unique_prefix_len_node(
        &self,
        idx: &impl RevlogIndex,
        node: &Node,
    ) -> Result<Option<usize>, NodeMapError> {

            Element::Rev(rev) => -rev - 2,
        })
    }
}

const ELEMENTS_PER_BLOCK: usize = 16; // number of different values in a nybble

/// A logical block of the [`NodeTree`], packed with a fixed size.
///
/// These are always used in container types implementing `Index<Block>`,
/// such as `&Block`
///
/// As an array of integers, its ith element encodes that the

/// rather than 0 and the [`Revision`] range upper limit of -2 instead of -1.
///
/// Another related difference is that `NULL_REVISION` (-1) is not
/// represented at all, because we want an immutable empty nodetree
/// to be valid.
#[derive(Copy, Clone, BytesCast, PartialEq)]
#[repr(transparent)]
pub struct Block([RawElement; ELEMENTS_PER_BLOCK]);

impl Block {

/// A mutable 16-radix tree with the root block logically at the end
///
/// Because of the append only nature of our node trees, we need to
/// keep the original untouched and store new blocks separately.
///
/// The mutable root [`Block`] is kept apart so that we don't have to rebump
/// it on each insertion.
pub struct NodeTree {
    readonly: Box<dyn Deref<Target = [Block]> + Send>,
    growable: Vec<Block>,
    root: Block,

            &self.growable[i - ro_len]
        }
    }
}

/// Return `None` unless the [`Node`] for `rev` has given prefix in `idx`.
fn has_prefix_or_none(
    idx: &impl RevlogIndex,
    prefix: NodePrefix,
    rev: Revision,
) -> Result<Option<Revision>, NodeMapError> {

            }
        })
}

/// validate that the candidate's node starts indeed with given prefix,
/// and treat ambiguities related to [`NULL_REVISION`].
///
/// From the data in the NodeTree, one can only conclude that some
/// revision is the only one for a *subprefix* of the one being looked up.
fn validate_candidate(
    idx: &impl RevlogIndex,

        }
    }

    /// Create from an opaque bunch of bytes
    ///
    /// The created [`NodeTreeBytes`] from `bytes`,
    /// of which exactly `amount` bytes are used.
    ///
    /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects.
    /// - `amount` is expressed in bytes, and is not automatically derived from
    ///   `bytes`, so that a caller that manages them atomically can perform
    ///   temporary disk serializations and still rollback easily if needed.
    ///   First use-case for this would be to support Mercurial shell hooks.
    ///