///|
// Return the batch block that can supply this exact clock. State-vector
// watermarks cannot answer this question for sparse histories.
fn dependency_provider(batch : Array[RawItem], id : Id) -> Int32? {
let index = for lo = 0, hi = batch.length(); lo < hi; {
let mid = lo + (hi - lo) / 2
let raw = batch[mid]
if raw.id.client > id.client ||
(raw.id.client == id.client && raw.id.clock <= id.clock) {
continue mid + 1, hi
} else {
continue lo, mid
}
} nobreak {
lo - 1
}
guard index >= 0 else { return None }
let raw = batch[index]
if raw.id.client == id.client &&
id.clock < raw.id.clock + raw.content.length().reinterpret_as_uint() {
Some(index)
} else {
None
}
}
///|
// Only retry a blocked item when its missing clock becomes available. The
// (round, position) queue preserves the former fixed-point scan order, including
// observable map/weak/subdocument side effects, without visiting blocked items
// on every round. Negative keys turn the max-priority queue into a min queue.
// Return attempts for deterministic complexity regression tests.
fn Doc::integrate_pending(self : Doc) -> Int32 {
let batch = normalize_items(self.pending)
let done = Array::make(batch.length(), false)
let blocked = []
let mut attempts = 0
// A normal ordered batch integrates in one pass. A still-blocked backlog
// also needs no dependency index until some missing clock becomes available.
for index, raw in batch {
attempts += 1
match self.integrate_dependency(raw) {
None => done[index] = true
Some(id) => blocked.push((id, index))
}
}
if !blocked.any(fn(entry) { self.find(entry.0) is Some(_) }) {
self.pending.clear()
for (_, index) in blocked {
self.pending.push(batch[index])
}
return attempts
}
let ready = @priority_queue.PriorityQueue([])
let waiting : Map[Int32, Array[(Id, Int32)]] = Map([])
for (id, index) in blocked {
if self.find(id) is Some(_) {
ready.push((-1, -index))
} else if dependency_provider(batch, id) is Some(provider) {
waiting.get_or_init(provider, fn() { [] }).push((id, index))
}
}
while ready.pop() is Some((negative_round, negative_index)) {
let index = -negative_index
attempts += 1
match self.integrate_dependency(batch[index]) {
None => done[index] = true
Some(id) =>
if dependency_provider(batch, id) is Some(provider) {
let entries = waiting.get_or_init(provider, fn() { [] })
entries.push((id, index))
}
}
// A partially integrated raw block can already supply a waiting clock.
// Wake those dependents even when a later slice remains blocked.
if waiting.get(index) is Some(entries) {
waiting.remove(index)
let remaining = []
for (id, dependent) in entries {
if self.find(id) is Some(_) {
let round = negative_round - (if dependent <= index { 1 } else { 0 })
ready.push((round, -dependent))
} else {
remaining.push((id, dependent))
}
}
if !remaining.is_empty() {
waiting[index] = remaining
}
}
}
self.pending.clear()
for index, raw in batch {
if !done[index] {
self.pending.push(raw)
}
}
attempts
}