thread_references_state.rs

Overview

This file manages the state and logic related to cross-thread block references within a distributed or concurrent system. It tracks which blocks from various threads are referenced, updates these references, and determines if a given set of explicit block references can be validly incorporated into the current state. The file handles maintaining the latest known references per thread, walking back through block histories to resolve references, and moving references forward in the state. It is central to ensuring thread-safe consistency and correctness in scenarios where blocks from multiple threads inter-reference.

Data Structures and Types

ReferencedBlock

Represents a reference to a specific block within a thread.

• Fields:

  • block_thread_identifier: ThreadIdentifier — Identifier of the thread that owns the referenced block.

  • block_identifier: BlockIdentifier — Unique identifier of the referenced block.

  • block_seq_no: BlockSeqNo — Sequence number of the block within its thread.

• Traits: Implements Clone, Serialize, Deserialize, Debug, Eq, and PartialEq.

• Conversions:

  • Implements From<(ThreadIdentifier, BlockIdentifier, BlockSeqNo)> to create a ReferencedBlock from a tuple of those values.

• Usage Example:

  let ref_block = ReferencedBlock::from((thread_id, block_id, seq_no));
  

ThreadReferencesState

Tracks the current known references to blocks across all active threads.

• Fields:

  • all_thread_refs: HashMap<ThreadIdentifier, ReferencedBlock> — Maps each thread to its latest referenced block.

• Notes:

  • ThreadIdentifier is duplicated both as the key and inside the value to handle threads that have started but have no first block referenced yet.

  • Does not store references to dead threads.

  • Intended to be possibly converted to load-on-demand for performance.

• Traits: Implements TypedBuilder, Clone, Serialize, Deserialize, and Debug.

ResultingState

Represents the outcome of a reference query, detailing which blocks are explicitly and implicitly referenced.

• Fields:

  • implicitly_referenced_blocks: Vec<BlockIdentifier> — Blocks referenced indirectly (not explicitly requested).

  • explicitly_referenced_blocks: Vec<BlockIdentifier> — Blocks explicitly referenced in the query.

• Traits: Implements Debug.

CanRefQueryResult

Indicates whether a set of explicit block references can be accepted.

• Variants:

  • No — The references cannot be accepted.

  • Yes(ResultingState) — The references can be accepted, along with the resulting state.

• Traits: Implements Debug.

Methods of ThreadReferencesState

all_thread_refs(&self) -> &HashMap<ThreadIdentifier, ReferencedBlock>

Returns a reference to the internal map of all thread references.

• Returns: Reference to HashMap<ThreadIdentifier, ReferencedBlock>

• Usage: To inspect current known references.

update(&mut self, thread: ThreadIdentifier, referenced_block: impl Into<ReferencedBlock>)

Updates the reference for a specific thread to a new referenced block.

• Parameters:

  • thread: ThreadIdentifier — The thread whose reference is to be updated.

  • referenced_block: impl Into<ReferencedBlock> — The new referenced block.

• Behavior: Inserts or updates the entry in all_thread_refs.

can_reference<F>(&self, explicit_references: Vec<BlockIdentifier>, get_ref_data: F) -> anyhow::Result<CanRefQueryResult>

Determines if the given explicit block references can be incorporated into the current state.

• Parameters:

  • explicit_references: Vec<BlockIdentifier> — The blocks explicitly referenced.

  • get_ref_data: F — A closure that takes a &BlockIdentifier and returns anyhow::Result<CrossThreadRefData>. Used to resolve block data.

• Returns: anyhow::Result<CanRefQueryResult>

• Process:

  • If no explicit references, returns Yes with empty result.

  • Creates a working copy (tails) of current thread refs.

  • Uses a queue (stack) to walk back through block histories starting from explicit references.

  • For each block in the history:

    • Converts block to ReferencedBlock.

    • Updates tails if the block's sequence number is more recent.

    • Tracks explicitly and implicitly referenced blocks.

  • Returns Yes with a ResultingState containing both explicit and implicit references.

• Implementation Details:

  • Uses walk_back_into_history helper function to traverse parent blocks.

  • Maintains sets to avoid duplicate references.

  • Uses tracing instrumentation for debugging.

• Usage Example:

  let result = thread_refs_state.can_reference(explicit_blocks, |block_id| {
      fetch_cross_thread_ref_data(block_id)
  })?;
  match result {
      CanRefQueryResult::Yes(state) => { /* process state */ }
      CanRefQueryResult::No => { /* handle rejection */ }
  }
  

move_refs<F>(&mut self, refs: Vec<BlockIdentifier>, get_ref_data: F) -> anyhow::Result<Vec<CrossThreadRefData>>

Moves the references forward in the state using a set of block identifiers.

• Parameters:

  • refs: Vec<BlockIdentifier> — The blocks to move references for.

  • get_ref_data: F — Closure to obtain CrossThreadRefData for each block.

• Returns: anyhow::Result<Vec<CrossThreadRefData>> — The cross-thread data for all moved references.

• Process:

  • Calls can_reference to validate references.

  • If valid:

    • Combines explicit and implicit references.

    • Adds "phantom" references for blocks that spawn new threads to ensure those threads have initial references.

    • Updates all_thread_refs with new references after keeping only the latest tails using keep_tails.

    • Returns detailed data for the moved references.

  • If invalid, returns an error.

• Implementation Details:

  • Contains logic to maintain references to thread split blocks even if no subsequent block is referenced.

  • Includes a placeholder for handling thread merges if enabled via feature flags.

  • Uses keep_tails to ensure only the most recent reference per thread is kept.

• Usage Example:

  let moved_data = thread_refs_state.move_refs(block_ids, |block_id| {
      fetch_cross_thread_ref_data(block_id)
  })?;
  

Helper Functions

walk_back_into_history<F>(cursor: &BlockIdentifier, read: F, cutoff: &HashMap<ThreadIdentifier, ReferencedBlock>) -> anyhow::Result<Vec<CrossThreadRefData>>

Walks backward through the block history starting from cursor until reaching a cutoff block per thread.

• Parameters:

  • cursor: &BlockIdentifier — Starting block identifier.

  • read: F — Closure to read block data (CrossThreadRefData) given a block identifier.

  • cutoff: &HashMap<ThreadIdentifier, ReferencedBlock> — Cutoff points per thread.

• Returns: anyhow::Result<Vec<CrossThreadRefData>> — The trail of blocks walked through.

• Process:

  • Starts at the given block and moves to its parent recursively.

  • Stops when reaching a block with sequence number less or equal to the cutoff for its thread.

  • Includes error checks to ensure consistency.

• Usage: Used internally by can_reference to gather full reference trails.

keep_tails(referenced_blocks: &mut Vec<(ThreadIdentifier, BlockIdentifier, BlockSeqNo)>)

Filters a list of referenced blocks to keep only the latest (tail) block per thread.

• Parameters:

  • referenced_blocks: &mut Vec<(ThreadIdentifier, BlockIdentifier, BlockSeqNo)> — The mutable list of references to process.

• Behavior:

  • Iterates over all references.

  • Keeps only the entry with the highest sequence number per thread.

  • Overwrites the input vector with the filtered tails.

• Usage: Used internally by move_refs to maintain the most recent references.

Implementation Details and Algorithms

• The core algorithm revolves around maintaining and updating the state of references to blocks across threads to ensure consistency.

• The can_reference method performs a breadth-first traversal (using VecDeque) and backward history walk (via walk_back_into_history) to resolve all implicit references starting from explicitly referenced blocks.

• Reference updates only occur if the new block has a higher sequence number than the currently known reference for a thread.

• The move_refs method ensures thread split blocks are preserved even if no later blocks are referenced by adding "phantoms."

• The state avoids retaining references to dead threads.

• The use of HashSet collections prevents duplication of references and efficiently tracks explicit vs implicit references.

• Instrumentation via tracing macros supports detailed runtime diagnostics.

Interaction with Other System Components

• Relies on types from crate::repository and crate::types:

  • CrossThreadRefData — Represents block data including cross-thread references.

  • BlockIdentifier, BlockSeqNo, ThreadIdentifier — Types representing unique IDs and sequence numbers.

• The closure parameter get_ref_data in methods allows integration with external data sources or repositories to fetch block metadata dynamically.

• Updates to all_thread_refs affect the global view of thread reference state, which presumably influences consensus, validation, or fork choice logic elsewhere in the system.

Visual Diagram: Class and Function Structure

classDiagram
class ReferencedBlock {
+block_thread_identifier: ThreadIdentifier
+block_identifier: BlockIdentifier
+block_seq_no: BlockSeqNo
+from(tuple): Self
}
class ThreadReferencesState {
-all_thread_refs: HashMap<ThreadIdentifier, ReferencedBlock>
+all_thread_refs(): &HashMap<ThreadIdentifier, ReferencedBlock>
+update(thread: ThreadIdentifier, referenced_block: Into<ReferencedBlock>)
+can_reference(explicit_refs: Vec<BlockIdentifier>, get_ref_data: F) -> anyhow::Result<CanRefQueryResult>
+move_refs(refs: Vec<BlockIdentifier>, get_ref_data: F) -> anyhow::Result<Vec<CrossThreadRefData>>
}
class ResultingState {
+implicitly_referenced_blocks: Vec<BlockIdentifier>
+explicitly_referenced_blocks: Vec<BlockIdentifier>
}
class CanRefQueryResult {
<<enumeration>>
+No
+Yes(ResultingState)
}
class walk_back_into_history {
+walk_back_into_history(cursor: &BlockIdentifier, read: F, cutoff: &HashMap) -> anyhow::Result<Vec<CrossThreadRefData>>
}
class keep_tails {
+keep_tails(referenced_blocks: &mut Vec<(ThreadIdentifier, BlockIdentifier, BlockSeqNo)>)
}
ThreadReferencesState --> ReferencedBlock : uses
ThreadReferencesState --> ResultingState : returns
ThreadReferencesState --> CanRefQueryResult : returns
ThreadReferencesState ..> walk_back_into_history : calls
ThreadReferencesState ..> keep_tails : calls

This diagram shows the main structs and enums, their key methods and fields, and the relationships between them. The utility functions walk_back_into_history and keep_tails are used internally by ThreadReferencesState.