| 1 | use crate::block::{Item, ItemContent, ItemPtr, Prelim}; |
| 2 | use crate::branch::BranchPtr; |
| 3 | use crate::moving::{Move, StickyIndex}; |
| 4 | use crate::transaction::{ReadTxn, TransactionMut}; |
| 5 | use crate::types::TypePtr; |
| 6 | use crate::{Assoc, Out, ID}; |
| 7 | |
| 8 | /// Struct used for iterating over the sequence of item's values with respect to a potential |
| 9 | /// [Move] markers that may change their order. |
| 10 | #[derive(Debug, Clone)] |
| 11 | pub(crate) struct BlockIter { |
| 12 | branch: BranchPtr, |
| 13 | index: u32, |
| 14 | rel: u32, |
| 15 | next_item: Option<ItemPtr>, |
| 16 | curr_move: Option<ItemPtr>, |
| 17 | curr_move_start: Option<ItemPtr>, |
| 18 | curr_move_end: Option<ItemPtr>, |
| 19 | moved_stack: Vec<StackItem>, |
| 20 | reached_end: bool, |
| 21 | } |
| 22 | |
| 23 | impl BlockIter { |
| 24 | pub fn new(branch: BranchPtr) -> Self { |
| 25 | let next_item = branch.start; |
| 26 | let reached_end = branch.start.is_none(); |
| 27 | BlockIter { |
| 28 | branch, |
| 29 | next_item, |
| 30 | reached_end, |
| 31 | curr_move: None, |
| 32 | curr_move_start: None, |
| 33 | curr_move_end: None, |
| 34 | index: 0, |
| 35 | rel: 0, |
| 36 | moved_stack: Vec::default(), |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | #[inline] |
| 41 | pub fn rel(&self) -> u32 { |
| 42 | self.rel |
| 43 | } |
| 44 | |
| 45 | #[inline] |
| 46 | pub fn finished(&self) -> bool { |
| 47 | (self.reached_end && self.curr_move.is_none()) || self.index == self.branch.content_len |
| 48 | } |
| 49 | |
| 50 | #[inline] |
| 51 | pub fn next_item(&self) -> Option<ItemPtr> { |
| 52 | self.next_item |
| 53 | } |
| 54 | |
| 55 | pub fn left(&self) -> Option<ItemPtr> { |
| 56 | if self.reached_end { |
| 57 | self.next_item |
| 58 | } else if let Some(item) = self.next_item.as_deref() { |
| 59 | item.left |
| 60 | } else { |
| 61 | None |
| 62 | } |
| 63 | } |
| 64 | |
| 65 | pub fn right(&self) -> Option<ItemPtr> { |
| 66 | if self.reached_end { |
| 67 | None |
| 68 | } else { |
| 69 | self.next_item |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | pub fn move_to(&mut self, index: u32, txn: &mut TransactionMut) { |
| 74 | if index > self.index { |
| 75 | if !self.try_forward(txn, index - self.index) { |
| 76 | panic!("Block iter couldn't move forward"); |
| 77 | } |
| 78 | } else if index < self.index { |
| 79 | self.backward(txn, self.index - index) |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | fn can_forward(&self, ptr: Option<ItemPtr>, len: u32) -> bool { |
| 84 | if !self.reached_end || self.curr_move.is_some() { |
| 85 | if len > 0 { |
| 86 | return true; |
| 87 | } else if let Some(item) = ptr.as_deref() { |
| 88 | return !item.is_countable() |
| 89 | || item.is_deleted() |
| 90 | || ptr == self.curr_move_end |
| 91 | || (self.reached_end && self.curr_move_end.is_none()) |
| 92 | || item.moved != self.curr_move; |
| 93 | } |
| 94 | } |
| 95 | |
| 96 | false |
| 97 | } |
| 98 | |
| 99 | pub fn forward<T: ReadTxn>(&mut self, txn: &T, len: u32) { |
| 100 | if !self.try_forward(txn, len) { |
| 101 | panic!("Length exceeded") |
| 102 | } |
| 103 | } |
| 104 | |
| 105 | pub fn try_forward<T: ReadTxn>(&mut self, txn: &T, mut len: u32) -> bool { |
| 106 | if len == 0 && self.next_item.is_none() { |
| 107 | return true; |
| 108 | } |
| 109 | |
| 110 | if self.index + len > self.branch.content_len() || self.next_item.is_none() { |
| 111 | return false; |
| 112 | } |
| 113 | |
| 114 | let mut item = self.next_item; |
| 115 | self.index += len; |
| 116 | if self.rel != 0 { |
| 117 | len += self.rel; |
| 118 | self.rel = 0; |
| 119 | } |
| 120 | |
| 121 | let encoding = txn.store().offset_kind; |
| 122 | while self.can_forward(item, len) { |
| 123 | if item == self.curr_move_end |
| 124 | || (self.reached_end && self.curr_move_end.is_none() && self.curr_move.is_some()) |
| 125 | { |
| 126 | item = self.curr_move; // we iterate to the right after the current condition |
| 127 | self.pop(txn); |
| 128 | } else if item.is_none() { |
| 129 | return false; |
| 130 | } else if let Some(i) = item.as_deref() { |
| 131 | if i.is_countable() && !i.is_deleted() && i.moved == self.curr_move && len > 0 { |
| 132 | let item_len = i.content_len(encoding); |
| 133 | if item_len > len { |
| 134 | self.rel = len; |
| 135 | len = 0; |
| 136 | break; |
| 137 | } else { |
| 138 | len -= item_len; |
| 139 | } |
| 140 | } else if let ItemContent::Move(m) = &i.content { |
| 141 | if i.moved == self.curr_move { |
| 142 | if let Some(ptr) = self.curr_move { |
| 143 | self.moved_stack.push(StackItem::new( |
| 144 | self.curr_move_start, |
| 145 | self.curr_move_end, |
| 146 | ptr, |
| 147 | )); |
| 148 | } |
| 149 | |
| 150 | let (start, end) = m.get_moved_coords(txn); |
| 151 | self.curr_move = item; |
| 152 | self.curr_move_start = start; |
| 153 | self.curr_move_end = end; |
| 154 | item = start; |
| 155 | continue; |
| 156 | } |
| 157 | } |
| 158 | } |
| 159 | |
| 160 | if self.reached_end { |
| 161 | return false; |
| 162 | } |
| 163 | |
| 164 | match item.as_deref() { |
| 165 | Some(i) if i.right.is_some() => item = i.right, |
| 166 | _ => self.reached_end = true, //TODO: we need to ensure to iterate further if this.currMoveEnd === null |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | self.index -= len; |
| 171 | self.next_item = item; |
| 172 | true |
| 173 | } |
| 174 | |
| 175 | fn reduce_moves(&mut self, txn: &mut TransactionMut) { |
| 176 | let mut item = self.next_item; |
| 177 | if item.is_some() { |
| 178 | while item == self.curr_move_start { |
| 179 | item = self.curr_move; |
| 180 | self.pop(txn); |
| 181 | } |
| 182 | self.next_item = item; |
| 183 | } |
| 184 | } |
| 185 | |
| 186 | pub fn backward<T: ReadTxn>(&mut self, txn: &mut T, mut len: u32) { |
| 187 | if self.index < len { |
| 188 | panic!("Length exceeded"); |
| 189 | } |
| 190 | self.index -= len; |
| 191 | let encoding = txn.store().offset_kind; |
| 192 | if self.reached_end { |
| 193 | if let Some(next_item) = self.next_item.as_deref() { |
| 194 | self.rel = if next_item.is_countable() && !next_item.is_deleted() { |
| 195 | next_item.content_len(encoding) |
| 196 | } else { |
| 197 | 0 |
| 198 | }; |
| 199 | } |
| 200 | } |
| 201 | if self.rel >= len { |
| 202 | self.rel -= len; |
| 203 | return; |
| 204 | } |
| 205 | let mut item = self.next_item; |
| 206 | if let Some(i) = item.as_deref() { |
| 207 | if let ItemContent::Move(_) = &i.content { |
| 208 | item = i.left; |
| 209 | } else { |
| 210 | len += if i.is_countable() && !i.is_deleted() && i.moved == self.curr_move { |
| 211 | i.content_len(encoding) |
| 212 | } else { |
| 213 | 0 |
| 214 | }; |
| 215 | len -= self.rel; |
| 216 | } |
| 217 | } |
| 218 | self.rel = 0; |
| 219 | while let Some(i) = item.as_deref() { |
| 220 | if len == 0 { |
| 221 | break; |
| 222 | } |
| 223 | |
| 224 | if i.is_countable() && !i.is_deleted() && i.moved == self.curr_move { |
| 225 | let item_len = i.content_len(encoding); |
| 226 | if len < item_len { |
| 227 | self.rel = item_len - len; |
| 228 | len = 0; |
| 229 | } else { |
| 230 | len -= item_len; |
| 231 | } |
| 232 | if len == 0 { |
| 233 | break; |
| 234 | } |
| 235 | } else if let ItemContent::Move(m) = &i.content { |
| 236 | if i.moved == self.curr_move { |
| 237 | if let Some(curr_move) = self.curr_move { |
| 238 | self.moved_stack.push(StackItem::new( |
| 239 | self.curr_move_start, |
| 240 | self.curr_move_end, |
| 241 | curr_move, |
| 242 | )); |
| 243 | } |
| 244 | let (start, end) = m.get_moved_coords(txn); |
| 245 | self.curr_move = item; |
| 246 | self.curr_move_start = start; |
| 247 | self.curr_move_end = end; |
| 248 | item = start; |
| 249 | continue; |
| 250 | } |
| 251 | } |
| 252 | |
| 253 | if item == self.curr_move_start { |
| 254 | item = self.curr_move; // we iterate to the left after the current condition |
| 255 | self.pop(txn); |
| 256 | } |
| 257 | |
| 258 | item = if let Some(i) = item.as_deref() { |
| 259 | i.left |
| 260 | } else { |
| 261 | None |
| 262 | }; |
| 263 | } |
| 264 | self.next_item = item; |
| 265 | } |
| 266 | |
| 267 | /// We keep the moved-stack across several transactions. Local or remote changes can invalidate |
| 268 | /// "moved coords" on the moved-stack. |
| 269 | /// |
| 270 | /// The reason for this is that if assoc < 0, then getMovedCoords will return the target.right |
| 271 | /// item. While the computed item is on the stack, it is possible that a user inserts something |
| 272 | /// between target and the item on the stack. Then we expect that the newly inserted item |
| 273 | /// is supposed to be on the new computed item. |
| 274 | fn pop<T: ReadTxn>(&mut self, txn: &T) { |
| 275 | let mut start = None; |
| 276 | let mut end = None; |
| 277 | let mut moved = None; |
| 278 | if let Some(stack_item) = self.moved_stack.pop() { |
| 279 | moved = Some(stack_item.moved_to); |
| 280 | start = stack_item.start; |
| 281 | end = stack_item.end; |
| 282 | |
| 283 | let moved_item = stack_item.moved_to; |
| 284 | if let ItemContent::Move(m) = &moved_item.content { |
| 285 | if m.start.assoc == Assoc::Before && (m.start.within_range(start)) |
| 286 | || (m.end.within_range(end)) |
| 287 | { |
| 288 | let (s, e) = m.get_moved_coords(txn); |
| 289 | start = s; |
| 290 | end = e; |
| 291 | } |
| 292 | } |
| 293 | } |
| 294 | self.curr_move = moved; |
| 295 | self.curr_move_start = start; |
| 296 | self.curr_move_end = end; |
| 297 | self.reached_end = false; |
| 298 | } |
| 299 | |
| 300 | pub fn delete(&mut self, txn: &mut TransactionMut, mut len: u32) { |
| 301 | let mut item = self.next_item; |
| 302 | if self.index + len > self.branch.content_len() { |
| 303 | panic!("Length exceeded"); |
| 304 | } |
| 305 | |
| 306 | let encoding = txn.store().offset_kind; |
| 307 | let mut i: &Item; |
| 308 | while len > 0 { |
| 309 | while let Some(block) = item.as_deref() { |
| 310 | i = block; |
| 311 | if !i.is_deleted() |
| 312 | && i.is_countable() |
| 313 | && !self.reached_end |
| 314 | && len > 0 |
| 315 | && i.moved == self.curr_move |
| 316 | && item != self.curr_move_end |
| 317 | { |
| 318 | if self.rel > 0 { |
| 319 | let mut id = i.id.clone(); |
| 320 | id.clock += self.rel; |
| 321 | let store = txn.store_mut(); |
| 322 | item = store |
| 323 | .blocks |
| 324 | .get_item_clean_start(&id) |
| 325 | .map(|s| store.materialize(s)); |
| 326 | i = item.as_deref().unwrap(); |
| 327 | self.rel = 0; |
| 328 | } |
| 329 | if len < i.content_len(encoding) { |
| 330 | let mut id = i.id.clone(); |
| 331 | id.clock += len; |
| 332 | let store = txn.store_mut(); |
| 333 | store |
| 334 | .blocks |
| 335 | .get_item_clean_start(&id) |
| 336 | .map(|s| store.materialize(s)); |
| 337 | } |
| 338 | len -= i.content_len(encoding); |
| 339 | txn.delete(item.unwrap()); |
| 340 | if i.right.is_some() { |
| 341 | item = i.right; |
| 342 | } else { |
| 343 | self.reached_end = true; |
| 344 | } |
| 345 | } else { |
| 346 | break; |
| 347 | } |
| 348 | } |
| 349 | if len > 0 { |
| 350 | self.next_item = item; |
| 351 | if self.try_forward(txn, 0) { |
| 352 | item = self.next_item; |
| 353 | } else { |
| 354 | panic!("Block iter couldn't move forward"); |
| 355 | } |
| 356 | } |
| 357 | } |
| 358 | self.next_item = item; |
| 359 | } |
| 360 | |
| 361 | pub(crate) fn slice<T: ReadTxn>(&mut self, txn: &T, buf: &mut [Out]) -> u32 { |
| 362 | let mut len = buf.len() as u32; |
| 363 | if self.index + len > self.branch.content_len() { |
| 364 | return 0; |
| 365 | } |
| 366 | self.index += len; |
| 367 | let mut next_item = self.next_item; |
| 368 | let encoding = txn.store().offset_kind; |
| 369 | let mut read = 0u32; |
| 370 | while len > 0 { |
| 371 | if !self.reached_end { |
| 372 | while let Some(item) = next_item { |
| 373 | if Some(item) != self.curr_move_end |
| 374 | && item.is_countable() |
| 375 | && !self.reached_end |
| 376 | && len > 0 |
| 377 | { |
| 378 | if !item.is_deleted() && item.moved == self.curr_move { |
| 379 | // we're iterating inside of a block |
| 380 | let r = item |
| 381 | .content |
| 382 | .read(self.rel as usize, &mut buf[read as usize..]) |
| 383 | as u32; |
| 384 | read += r; |
| 385 | len -= r; |
| 386 | if self.rel + r == item.content_len(encoding) { |
| 387 | self.rel = 0; |
| 388 | } else { |
| 389 | self.rel += r; |
| 390 | continue; // do not iterate to item.right |
| 391 | } |
| 392 | } |
| 393 | |
| 394 | if item.right.is_some() { |
| 395 | next_item = item.right; |
| 396 | } else { |
| 397 | self.reached_end = true; |
| 398 | } |
| 399 | } else { |
| 400 | break; |
| 401 | } |
| 402 | } |
| 403 | if (!self.reached_end || self.curr_move.is_some()) && len > 0 { |
| 404 | // always set nextItem before any method call |
| 405 | self.next_item = next_item; |
| 406 | if !self.try_forward(txn, 0) || self.next_item.is_none() { |
| 407 | return read; |
| 408 | } |
| 409 | next_item = self.next_item; |
| 410 | } |
| 411 | } else if self.curr_move.is_some() { |
| 412 | // reached end but move stack still has some items, |
| 413 | // so we try to pop move frames and move on the |
| 414 | // first non-null right neighbor of the popped move block |
| 415 | while let Some(mov) = self.curr_move.as_deref() { |
| 416 | next_item = mov.right; |
| 417 | self.pop(txn); |
| 418 | if next_item.is_some() { |
| 419 | self.reached_end = false; |
| 420 | break; |
| 421 | } |
| 422 | } |
| 423 | } else { |
| 424 | // reached end and move stack is empty |
| 425 | next_item = None; |
| 426 | break; |
| 427 | } |
| 428 | } |
| 429 | self.next_item = next_item; |
| 430 | self.index -= len; |
| 431 | read |
| 432 | } |
| 433 | |
| 434 | fn split_rel(&mut self, txn: &mut TransactionMut) { |
| 435 | if self.rel > 0 { |
| 436 | if let Some(ptr) = self.next_item { |
| 437 | let mut item_id = ptr.id().clone(); |
| 438 | item_id.clock += self.rel; |
| 439 | let store = txn.store_mut(); |
| 440 | self.next_item = store |
| 441 | .blocks |
| 442 | .get_item_clean_start(&item_id) |
| 443 | .map(|s| store.materialize(s)); |
| 444 | self.rel = 0; |
| 445 | } |
| 446 | } |
| 447 | } |
| 448 | |
| 449 | pub(crate) fn read_value<T: ReadTxn>(&mut self, txn: &T) -> Option<Out> { |
| 450 | let mut buf = [Out::default()]; |
| 451 | if self.slice(txn, &mut buf) != 0 { |
| 452 | Some(std::mem::replace(&mut buf[0], Out::default())) |
| 453 | } else { |
| 454 | None |
| 455 | } |
| 456 | } |
| 457 | |
| 458 | pub fn insert_contents<V: Prelim>( |
| 459 | &mut self, |
| 460 | txn: &mut TransactionMut, |
| 461 | value: V, |
| 462 | ) -> Option<ItemPtr> { |
| 463 | self.reduce_moves(txn); |
| 464 | self.split_rel(txn); |
| 465 | let id = { |
| 466 | let store = txn.store(); |
| 467 | let client_id = store.client_id; |
| 468 | let clock = store.blocks.get_clock(&client_id); |
| 469 | ID::new(client_id, clock) |
| 470 | }; |
| 471 | let parent = TypePtr::Branch(self.branch); |
| 472 | let right = self.right(); |
| 473 | let left = self.left(); |
| 474 | let (mut content, remainder) = value.into_content(txn); |
| 475 | let inner_ref = if let ItemContent::Type(inner_ref) = &mut content { |
| 476 | Some(BranchPtr::from(inner_ref)) |
| 477 | } else { |
| 478 | None |
| 479 | }; |
| 480 | let mut block = Item::new( |
| 481 | id, |
| 482 | left, |
| 483 | left.map(|ptr| ptr.last_id()), |
| 484 | right, |
| 485 | right.map(|r| *r.id()), |
| 486 | parent, |
| 487 | None, |
| 488 | content, |
| 489 | )?; |
| 490 | let mut block_ptr = ItemPtr::from(&mut block); |
| 491 | |
| 492 | block_ptr.integrate(txn, 0); |
| 493 | |
| 494 | txn.store_mut().blocks.push_block(block); |
| 495 | |
| 496 | if let Some(remainder) = remainder { |
| 497 | remainder.integrate(txn, inner_ref.unwrap().into()) |
| 498 | } |
| 499 | |
| 500 | if let Some(item) = right.as_deref() { |
| 501 | self.next_item = item.right; |
| 502 | } else { |
| 503 | self.next_item = left; |
| 504 | self.reached_end = true; |
| 505 | } |
| 506 | |
| 507 | Some(block_ptr) |
| 508 | } |
| 509 | |
| 510 | pub fn insert_move(&mut self, txn: &mut TransactionMut, start: StickyIndex, end: StickyIndex) { |
| 511 | self.insert_contents(txn, Move::new(start, end, -1)); |
| 512 | } |
| 513 | |
| 514 | pub fn values<'a, 'txn, T: ReadTxn>( |
| 515 | &'a mut self, |
| 516 | txn: &'txn mut TransactionMut<'txn>, |
| 517 | ) -> Values<'a, 'txn> { |
| 518 | Values::new(self, txn) |
| 519 | } |
| 520 | } |
| 521 | |
| 522 | pub struct Values<'a, 'txn> { |
| 523 | iter: &'a mut BlockIter, |
| 524 | txn: &'txn mut TransactionMut<'txn>, |
| 525 | } |
| 526 | |
| 527 | impl<'a, 'txn> Values<'a, 'txn> { |
| 528 | fn new(iter: &'a mut BlockIter, txn: &'txn mut TransactionMut<'txn>) -> Self { |
| 529 | Values { iter, txn } |
| 530 | } |
| 531 | } |
| 532 | |
| 533 | impl<'a, 'txn> Iterator for Values<'a, 'txn> { |
| 534 | type Item = Out; |
| 535 | |
| 536 | fn next(&mut self) -> Option<Self::Item> { |
| 537 | if self.iter.reached_end || self.iter.index == self.iter.branch.content_len() { |
| 538 | None |
| 539 | } else { |
| 540 | let mut buf = [Out::default()]; |
| 541 | if self.iter.slice(self.txn, &mut buf) != 0 { |
| 542 | Some(std::mem::replace(&mut buf[0], Out::default())) |
| 543 | } else { |
| 544 | None |
| 545 | } |
| 546 | } |
| 547 | } |
| 548 | } |
| 549 | |
| 550 | #[derive(Debug, Clone)] |
| 551 | struct StackItem { |
| 552 | start: Option<ItemPtr>, |
| 553 | end: Option<ItemPtr>, |
| 554 | moved_to: ItemPtr, |
| 555 | } |
| 556 | |
| 557 | impl StackItem { |
| 558 | fn new(start: Option<ItemPtr>, end: Option<ItemPtr>, moved_to: ItemPtr) -> Self { |
| 559 | StackItem { |
| 560 | start, |
| 561 | end, |
| 562 | moved_to, |
| 563 | } |
| 564 | } |
| 565 | } |
| 566 | |
amadan