1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414
//! Types related to an agents for chain activity
use std::iter::Peekable;
use std::ops::RangeInclusive;
use crate::activity::AgentActivityResponse;
use crate::activity::ChainItems;
use holo_hash::ActionHash;
use holo_hash::AgentPubKey;
use holo_hash::HasHash;
use holochain_serialized_bytes::prelude::*;
use holochain_zome_types::prelude::ChainStatus;
use holochain_zome_types::ActionHashed;
use holochain_zome_types::ChainFilter;
use holochain_zome_types::ChainFilters;
use holochain_zome_types::RegisterAgentActivity;
use holochain_zome_types::SignedActionHashed;
#[cfg(all(test, feature = "test_utils"))]
pub mod test;
/// Helpers for constructing AgentActivity
pub trait AgentActivityExt {
/// Create an empty chain status
fn empty<T>(agent: &AgentPubKey) -> AgentActivityResponse<T> {
AgentActivityResponse {
agent: agent.clone(),
valid_activity: ChainItems::NotRequested,
rejected_activity: ChainItems::NotRequested,
status: ChainStatus::Empty,
// TODO: Add the actual highest observed in a follow up PR
highest_observed: None,
}
}
}
impl AgentActivityExt for AgentActivityResponse {}
/// Abstraction over an item in a chain.
// Alternate implementations are only used for testing, so this should not
// add a large monomorphization overhead
pub trait ChainItem: Clone + PartialEq + Eq + std::fmt::Debug + Send + Sync {
/// The type used to represent a hash of this item
type Hash: Into<ActionHash>
+ Clone
+ PartialEq
+ Eq
+ Ord
+ std::hash::Hash
+ std::fmt::Debug
+ Send
+ Sync;
/// The sequence in the chain
fn seq(&self) -> u32;
/// The hash of this item
fn get_hash(&self) -> &Self::Hash;
/// The hash of the previous item
fn prev_hash(&self) -> Option<&Self::Hash>;
}
/// Alias for getting the associated hash type of a ChainItem
pub type ChainItemHash<I> = <I as ChainItem>::Hash;
impl ChainItem for ActionHashed {
type Hash = ActionHash;
fn seq(&self) -> u32 {
self.action_seq()
}
fn get_hash(&self) -> &Self::Hash {
self.as_hash()
}
fn prev_hash(&self) -> Option<&Self::Hash> {
self.prev_action()
}
}
impl ChainItem for SignedActionHashed {
type Hash = ActionHash;
fn seq(&self) -> u32 {
self.hashed.seq()
}
fn get_hash(&self) -> &Self::Hash {
self.hashed.get_hash()
}
fn prev_hash(&self) -> Option<&Self::Hash> {
self.hashed.prev_hash()
}
}
#[must_use = "Iterator doesn't do anything unless consumed."]
#[derive(Debug)]
/// Iterate over a source chain and apply the [`ChainFilter`] to each element.
/// This iterator will:
/// - Ignore any ops that are not a direct ancestor to the starting position.
/// - Stop at the first gap in the chain.
/// - Take no **more** then the [`take`]. It may return less.
/// - Stop at (including) the [`ActionHash`](holo_hash::ActionHash) in [`until`]. But not if this hash is not in the chain.
///
/// [`take`]: ChainFilter::take
/// [`until`]: ChainFilter::until
pub struct ChainFilterIter<I: AsRef<A>, A: ChainItem = SignedActionHashed> {
filter: ChainFilter<A::Hash>,
iter: Peekable<std::vec::IntoIter<I>>,
end: bool,
}
#[derive(Debug, Clone, PartialEq, Eq)]
/// A [`ChainFilter`] with the action sequences for the
/// starting position and any `until` hashes.
pub struct ChainFilterRange {
/// The filter for for this chain.
filter: ChainFilter,
/// The start of this range is the end of
/// the filter iterator.
/// The end of this range is the sequence of
/// the starting position hash.
range: RangeInclusive<u32>,
/// The start of the range's type.
chain_bottom_type: ChainBottomType,
}
#[derive(Debug, Clone, PartialEq, Eq)]
/// The type of chain item that forms the bottom of the chain.
enum ChainBottomType {
/// The bottom of the chain is genesis.
Genesis,
/// The bottom of the chain is the action where `take`
/// has reached zero.
Take,
/// The bottom of the chain is the action where an
/// `until` hash was found.
Until,
}
#[derive(Debug, Clone, PartialEq, Eq)]
/// Outcome of trying to find the action sequences in a filter.
pub enum Sequences {
/// Found all action sequences
Found(ChainFilterRange),
/// The chain top action was not found.
ChainTopNotFound(ActionHash),
/// The filter produces an empty range.
EmptyRange,
}
#[derive(Debug, Clone, PartialEq, Eq, SerializedBytes, Serialize, Deserialize)]
/// Response to a `must_get_agent_activity` call.
pub enum MustGetAgentActivityResponse {
/// The activity was found.
Activity(Vec<RegisterAgentActivity>),
/// The requested chain range was incomplete.
IncompleteChain,
/// The requested chain top was not found in the chain.
ChainTopNotFound(ActionHash),
/// The filter produces an empty range.
EmptyRange,
}
impl<I: AsRef<A>, A: ChainItem> ChainFilterIter<I, A> {
/// Create an iterator that filters an iterator of actions
/// with a [`ChainFilter`].
///
/// # Constraints
/// - If the iterator does not contain the filter's chain_top
/// then this will be an empty iterator.
pub fn new(filter: ChainFilter<A::Hash>, mut chain: Vec<I>) -> Self {
// Sort by descending.
chain.sort_unstable_by_key(|a| u32::MAX - a.as_ref().seq());
// Create a peekable iterator.
let mut iter = chain.into_iter().peekable();
// Discard any ops that are not the chain_top.
let i = iter.by_ref();
while let Some(op) = i.peek() {
if *op.as_ref().get_hash() == filter.chain_top {
break;
}
i.next();
}
Self {
filter,
iter,
end: false,
}
}
}
impl<I: AsRef<A>, A: ChainItem> Iterator for ChainFilterIter<I, A> {
type Item = I;
fn next(&mut self) -> Option<Self::Item> {
if self.end {
return None;
}
let op = self.iter.next()?;
let op = loop {
let parent = self.iter.peek();
// Check the next sequence number
match parent {
Some(parent) => {
let child_seq = op.as_ref().seq();
let parent_seq = parent.as_ref().seq();
match (child_seq.cmp(&parent_seq), op.as_ref().prev_hash()) {
(std::cmp::Ordering::Less, _) => {
// The chain is out of order so we must end here.
self.end = true;
break op;
}
(std::cmp::Ordering::Equal, _) => {
// There is a fork in the chain.
// Discard this parent.
self.iter.next();
// Try the next parent.
continue;
}
(std::cmp::Ordering::Greater, None) => {
// The chain is correct however there is no previous action for this child.
// The child can't be the first chain item and doesn't have a parent like:
// `child != 0 && child -> ()`.
// All we can do is end the iterator.
// I don't think this state is actually reachable
// because the only header that can have no previous action is the `Dna` and
// it is always zero.
return None;
}
(std::cmp::Ordering::Greater, _)
if parent_seq.checked_add(1)? != child_seq =>
{
// There is a gap in the chain so we must end here.
self.end = true;
break op;
}
(std::cmp::Ordering::Greater, Some(prev_hash))
if prev_hash != parent.as_ref().get_hash() =>
{
// Not the parent of this child.
// Discard this parent.
self.iter.next();
// Try the next parent.
continue;
}
(std::cmp::Ordering::Greater, Some(_)) => {
// Correct parent found.
break op;
}
}
}
None => break op,
}
};
match &mut self.filter.filters {
// Check if there is any left to take.
ChainFilters::Take(n) => *n = n.checked_sub(1)?,
// Check if the `until` hash has been found.
ChainFilters::Until(until_hashes) => {
if until_hashes.contains(op.as_ref().get_hash()) {
// If it has, include it and return on the next call to `next`.
self.end = true;
}
}
// Just keep going till genesis.
ChainFilters::ToGenesis => (),
// Both filters are active. Return on the first to be hit.
ChainFilters::Both(n, until_hashes) => {
*n = n.checked_sub(1)?;
if until_hashes.contains(op.as_ref().get_hash()) {
self.end = true;
}
}
}
Some(op)
}
}
impl Sequences {
/// Find the action sequences for all hashes in the filter.
pub fn find_sequences<F, E>(filter: ChainFilter, mut get_seq: F) -> Result<Self, E>
where
F: FnMut(&ActionHash) -> Result<Option<u32>, E>,
{
// Get the top of the chain action sequence.
// This is the highest sequence number and also the
// start of the iterator.
let chain_top = match get_seq(&filter.chain_top)? {
Some(seq) => seq,
None => return Ok(Self::ChainTopNotFound(filter.chain_top)),
};
// Track why the sequence start of the range was chosen.
let mut chain_bottom_type = ChainBottomType::Genesis;
// If their are any until hashes in the filter,
// then find the highest sequence of the set
// and find the distance from the position.
let distance = match filter.get_until() {
Some(until_hashes) => {
// Find the highest sequence of the until hashes.
let max = until_hashes
.iter()
.filter_map(|hash| {
match get_seq(hash) {
Ok(seq) => {
// Ignore any until hashes that could not be found.
let seq = seq?;
// Ignore any until hashes that are higher then a chain top.
(seq <= chain_top).then(|| Ok(seq))
}
Err(e) => Some(Err(e)),
}
})
.try_fold(0, |max, result| {
let seq = result?;
Ok(max.max(seq))
})?;
if max != 0 {
// If the max is not genesis then there is an
// until hash that was found.
chain_bottom_type = ChainBottomType::Until;
}
// The distance from the chain top till highest until hash.
// Note this cannot be an overflow due to the check above.
chain_top - max
}
// If there is no until hashes then the distance is the chain top
// till genesis (or just the chain top).
None => chain_top,
};
// Check if there is a take filter and if that
// will be reached before any until hashes or genesis.
let start = match filter.get_take() {
Some(take) => {
// A take of zero will produce an empty range.
if take == 0 {
return Ok(Self::EmptyRange);
} else if take <= distance {
// The take will be reached before genesis or until hashes.
chain_bottom_type = ChainBottomType::Take;
// Add one to include the "position" in the number of
// "take". This matches the rust iterator "take".
chain_top.saturating_sub(take).saturating_add(1)
} else {
// The range spans from the position for the distance
// that was determined earlier.
chain_top - distance
}
}
// The range spans from the position for the distance
// that was determined earlier.
None => chain_top - distance,
};
Ok(Self::Found(ChainFilterRange {
filter,
range: start..=chain_top,
chain_bottom_type,
}))
}
}
impl ChainFilterRange {
/// Get the range of action sequences for this filter.
pub fn range(&self) -> &RangeInclusive<u32> {
&self.range
}
/// Filter the chain items then check the invariants hold.
pub fn filter_then_check(
self,
chain: Vec<RegisterAgentActivity>,
) -> MustGetAgentActivityResponse {
let until_hashes = self.filter.get_until().cloned();
// Create the filter iterator and collect the filtered actions.
let out: Vec<_> = ChainFilterIter::new(self.filter, chain).collect();
// Check the invariants hold.
match out.last().zip(out.first()) {
// The actual results after the filter must match the range.
Some((lowest, highest))
if (lowest.action.action().action_seq()..=highest.action.action().action_seq())
== self.range =>
{
// If the range start was an until hash then the first action must
// actually be an action from the until set.
if let Some(hashes) = until_hashes {
if matches!(self.chain_bottom_type, ChainBottomType::Until)
&& !hashes.contains(lowest.action.action_address())
{
return MustGetAgentActivityResponse::IncompleteChain;
}
}
// The constraints are met the activity can be returned.
MustGetAgentActivityResponse::Activity(out)
}
// The constraints are not met so the chain is not complete.
_ => MustGetAgentActivityResponse::IncompleteChain,
}
}
}