1use crate::RangeOption;
12use crate::directory::directory_partition::DirectoryPartition;
13use crate::directory::directory_subspace::DirectorySubspace;
14use crate::directory::error::DirectoryError;
15use crate::directory::node::Node;
16use crate::directory::{Directory, DirectoryOutput, compare_slice, strinc};
17use crate::future::FdbSlice;
18use crate::tuple::hca::HighContentionAllocator;
19use crate::tuple::{Element, Subspace, TuplePack};
20use crate::{FdbResult, Transaction};
21use async_recursion::async_recursion;
22use async_trait::async_trait;
23use futures::TryStreamExt;
24use std::cmp::Ordering;
25use std::ops::Deref;
26use std::sync::Arc;
27
28pub(crate) const DEFAULT_SUB_DIRS: i64 = 0;
29const MAJOR_VERSION: u32 = 1;
30const MINOR_VERSION: u32 = 0;
31const PATCH_VERSION: u32 = 0;
32pub(crate) const DEFAULT_NODE_PREFIX: &[u8] = b"\xFE";
33const DEFAULT_HCA_PREFIX: &[u8] = b"hca";
34pub(crate) const PARTITION_LAYER: &[u8] = b"partition";
35pub(crate) const LAYER_SUFFIX: &[u8] = b"layer";
36
37#[derive(Clone)]
42pub struct DirectoryLayer {
43 pub(crate) inner: Arc<DirectoryLayerInner>,
44}
45
46impl std::fmt::Debug for DirectoryLayer {
47 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48 self.inner.fmt(f)
49 }
50}
51
52#[derive(Debug)]
53pub struct DirectoryLayerInner {
54 pub(crate) root_node: Subspace,
55 pub(crate) node_subspace: Subspace,
56 pub(crate) content_subspace: Subspace,
57 pub(crate) allocator: HighContentionAllocator,
58 pub(crate) allow_manual_prefixes: bool,
59
60 pub(crate) path: Vec<String>,
61}
62
63impl Deref for DirectoryLayer {
64 type Target = DirectoryLayerInner;
65
66 fn deref(&self) -> &Self::Target {
67 &self.inner
68 }
69}
70
71impl Default for DirectoryLayer {
72 fn default() -> Self {
78 Self::new(
79 Subspace::from_bytes(DEFAULT_NODE_PREFIX),
80 Subspace::all(),
81 false,
82 )
83 }
84}
85
86impl DirectoryLayer {
87 pub fn new(
88 node_subspace: Subspace,
89 content_subspace: Subspace,
90 allow_manual_prefixes: bool,
91 ) -> Self {
92 let root_node = node_subspace.subspace(&node_subspace.bytes());
93 let allocator = HighContentionAllocator::new(root_node.subspace(&DEFAULT_HCA_PREFIX));
94
95 DirectoryLayer {
96 inner: Arc::new(DirectoryLayerInner {
97 root_node,
98 node_subspace,
99 content_subspace,
100 allocator,
101 allow_manual_prefixes,
102 path: vec![],
103 }),
104 }
105 }
106
107 pub(crate) fn new_with_path(
108 node_subspace: Subspace,
109 content_subspace: Subspace,
110 allow_manual_prefixes: bool,
111 path: &[String],
112 ) -> Self {
113 let root_node = node_subspace.subspace(&node_subspace.bytes());
114 let allocator = HighContentionAllocator::new(root_node.subspace(&DEFAULT_HCA_PREFIX));
115
116 DirectoryLayer {
117 inner: Arc::new(DirectoryLayerInner {
118 root_node,
119 node_subspace,
120 content_subspace,
121 allocator,
122 allow_manual_prefixes,
123 path: Vec::from(path),
124 }),
125 }
126 }
127
128 pub fn get_path(&self) -> &[String] {
129 self.path.as_slice()
130 }
131
132 fn node_with_optional_prefix(&self, prefix: Option<FdbSlice>) -> Option<Subspace> {
133 prefix.map(|fdb_slice| self.node_with_prefix(&fdb_slice.deref()))
134 }
135
136 fn node_with_prefix<T: TuplePack>(&self, prefix: &T) -> Subspace {
137 self.inner.node_subspace.subspace(prefix)
138 }
139
140 async fn find(
141 &self,
142 trx: &Transaction,
143 path: &[String],
144 ) -> Result<Option<Node>, DirectoryError> {
145 let mut current_path = vec![];
146 let mut node_subspace = self.root_node.clone();
147 let mut layer = vec![];
148 let mut loaded = false;
149
150 for path_name in path.iter() {
152 current_path.push(path_name.clone());
153 let key = node_subspace.subspace(&(DEFAULT_SUB_DIRS, path_name.to_owned()));
154
155 let fdb_slice_value = trx.get(key.bytes(), false).await?;
157
158 loaded = true;
159 node_subspace = match self.node_with_optional_prefix(fdb_slice_value) {
160 None => return Ok(None),
161 Some(subspace) => subspace,
162 };
163
164 layer = Node::load_metadata(trx, &node_subspace).await?;
165 if layer.as_slice().eq(PARTITION_LAYER) {
166 break;
167 }
168 }
169
170 if !loaded {
171 layer = Node::load_metadata(trx, &node_subspace).await?;
172 }
173
174 Ok(Some(Node {
175 subspace: node_subspace,
176 current_path,
177 target_path: Vec::from(path),
178 directory_layer: self.clone(),
179 layer,
180 }))
181 }
182
183 fn to_absolute_path(&self, sub_path: &[String]) -> Vec<String> {
184 let mut path: Vec<String> = Vec::with_capacity(self.path.len() + sub_path.len());
185
186 path.extend_from_slice(&self.path);
187 path.extend_from_slice(sub_path);
188
189 path
190 }
191
192 pub(crate) fn contents_of_node(
193 &self,
194 subspace: &Subspace,
195 path: &[String],
196 layer: &[u8],
197 ) -> Result<DirectoryOutput, DirectoryError> {
198 let prefix: Vec<u8> = self.node_subspace.unpack(subspace.bytes())?;
199
200 if layer.eq(PARTITION_LAYER) {
201 Ok(DirectoryOutput::DirectoryPartition(
202 DirectoryPartition::new(&self.to_absolute_path(path), prefix, self.clone()),
203 ))
204 } else {
205 Ok(DirectoryOutput::DirectorySubspace(DirectorySubspace::new(
206 &self.to_absolute_path(path),
207 prefix,
208 self,
209 layer.to_owned(),
210 )))
211 }
212 }
213
214 #[async_recursion]
216 async fn create_or_open_internal(
217 &self,
218 trx: &Transaction,
219 path: &[String],
220 prefix: Option<&'async_recursion [u8]>,
221 layer: Option<&'async_recursion [u8]>,
222 allow_create: bool,
223 allow_open: bool,
224 ) -> Result<DirectoryOutput, DirectoryError> {
225 self.check_version(trx, false).await?;
226
227 if prefix.is_some() && !self.allow_manual_prefixes {
228 if self.path.is_empty() {
229 return Err(DirectoryError::PrefixNotAllowed);
230 }
231
232 return Err(DirectoryError::CannotPrefixInPartition);
233 }
234
235 if path.is_empty() {
236 return Err(DirectoryError::NoPathProvided);
237 }
238
239 if let Some(node) = self.find(trx, path).await? {
240 if node.is_in_partition(false) {
241 let sub_path = node.get_partition_subpath();
242 match node.get_contents()? {
243 DirectoryOutput::DirectorySubspace(_) => unreachable!("already in partition"),
244 DirectoryOutput::DirectoryPartition(directory_partition) => {
245 let dir_space = directory_partition
246 .directory_subspace
247 .directory_layer
248 .create_or_open_internal(
249 trx,
250 &sub_path,
251 prefix,
252 layer,
253 allow_create,
254 allow_open,
255 )
256 .await?;
257 Ok(dir_space)
258 }
259 }
260 } else {
261 self.open_internal(layer, &node, allow_open).await
262 }
263 } else {
264 self.create_internal(trx, path, layer, prefix, allow_create)
265 .await
266 }
267 }
268
269 async fn open_internal(
270 &self,
271 layer: Option<&[u8]>,
272 node: &Node,
273 allow_open: bool,
274 ) -> Result<DirectoryOutput, DirectoryError> {
275 if !allow_open {
276 return Err(DirectoryError::DirAlreadyExists);
277 }
278
279 match layer {
280 None => {}
281 Some(layer) if !layer.is_empty() => match compare_slice(layer, &node.layer) {
282 Ordering::Equal => {}
283 _ => {
284 return Err(DirectoryError::IncompatibleLayer);
285 }
286 },
287 Some(_) => {}
288 }
289
290 node.get_contents()
291 }
292
293 async fn create_internal(
294 &self,
295 trx: &Transaction,
296 path: &[String],
297 layer: Option<&[u8]>,
298 prefix: Option<&[u8]>,
299 allow_create: bool,
300 ) -> Result<DirectoryOutput, DirectoryError> {
301 let path_last = path.last().ok_or(DirectoryError::NoPathProvided)?;
302
303 if !allow_create {
304 return Err(DirectoryError::DirectoryDoesNotExists);
305 }
306
307 let layer = layer.unwrap_or_default();
308
309 self.check_version(trx, true).await?;
310 let new_prefix = self.get_prefix(trx, prefix).await?;
311
312 let is_prefix_free = self
313 .is_prefix_free(trx, new_prefix.as_slice(), prefix.is_none())
314 .await?;
315
316 if !is_prefix_free {
317 return Err(DirectoryError::DirectoryPrefixInUse);
318 }
319
320 let parent_node = self.get_parent_node(trx, path).await?;
321 let node = self.node_with_prefix(&new_prefix);
322
323 let key = parent_node.subspace(&(DEFAULT_SUB_DIRS, path_last));
324 let key_layer = node.pack(&LAYER_SUFFIX);
325
326 trx.set(key.bytes(), &new_prefix);
327 trx.set(&key_layer, layer);
328
329 self.contents_of_node(&node, path, layer)
330 }
331
332 async fn get_parent_node(
333 &self,
334 trx: &Transaction,
335 path: &[String],
336 ) -> Result<Subspace, DirectoryError> {
337 match path.split_last() {
338 None => Ok(self.root_node.clone()),
339 Some((_, remains)) => {
340 if remains.is_empty() {
341 return Ok(self.root_node.clone());
342 }
343 let parent = self
344 .create_or_open_internal(trx, remains, None, None, true, true)
345 .await?;
346
347 Ok(self.node_with_prefix(&parent.bytes()?))
348 }
349 }
350 }
351
352 async fn is_prefix_free(
353 &self,
354 trx: &Transaction,
355 prefix: &[u8],
356 snapshot: bool,
357 ) -> Result<bool, DirectoryError> {
358 if prefix.is_empty() {
359 return Ok(false);
360 }
361
362 let node = self.node_containing_key(trx, prefix, snapshot).await?;
363
364 if node.is_some() {
365 return Ok(false);
366 }
367
368 let mut range_option = RangeOption::from((
369 self.node_subspace.pack(&prefix),
370 self.node_subspace.pack(&strinc(prefix.to_vec())),
371 ));
372 range_option.limit = Some(1);
373
374 let result = trx
375 .get_ranges_keyvalues(range_option, snapshot)
376 .try_next()
377 .await?;
378
379 Ok(result.is_none())
380 }
381
382 async fn node_containing_key(
383 &self,
384 trx: &Transaction,
385 key: &[u8],
386 snapshot: bool,
387 ) -> Result<Option<Subspace>, DirectoryError> {
388 if key.starts_with(self.node_subspace.bytes()) {
389 return Ok(Some(self.root_node.clone()));
390 }
391
392 let mut key_after = key.to_vec();
393 key_after.push(0);
395
396 let range_end = self.node_subspace.pack(&key_after);
397
398 let mut range_option = RangeOption::from((self.node_subspace.range().0, range_end));
399 range_option.reverse = true;
400 range_option.limit = Some(1);
401
402 let fdb_value = trx
404 .get_ranges_keyvalues(range_option, snapshot)
405 .try_next()
406 .await?;
407
408 if let Some(fdb_key_value) = fdb_value {
409 let previous_prefix: Vec<Element> = self.node_subspace.unpack(fdb_key_value.key())?;
410
411 if let Some(Element::Bytes(previous_prefix)) = previous_prefix.first()
412 && key.starts_with(previous_prefix)
413 {
414 return Ok(Some(self.node_with_prefix(previous_prefix)));
415 };
416 }
417 Ok(None)
418 }
419
420 async fn get_prefix(
421 &self,
422 trx: &Transaction,
423 prefix: Option<&[u8]>,
424 ) -> Result<Vec<u8>, DirectoryError> {
425 match prefix {
426 None => {
427 let allocator = self.allocator.allocate(trx).await?;
429 let subspace = self.content_subspace.subspace(&allocator);
430
431 let mut range_option = RangeOption::from((
434 subspace.bytes().to_vec(),
435 strinc(subspace.bytes().to_vec()),
436 ));
437 range_option.limit = Some(1);
438
439 let result = trx
440 .get_ranges_keyvalues(range_option, false)
441 .try_next()
442 .await?;
443
444 if result.is_some() {
445 return Err(DirectoryError::PrefixNotEmpty);
446 }
447
448 Ok(subspace.into_bytes())
449 }
450 Some(v) => Ok(v.to_vec()),
451 }
452 }
453
454 async fn check_version(
456 &self,
457 trx: &Transaction,
458 allow_creation: bool,
459 ) -> Result<(), DirectoryError> {
460 let version = self.get_version_value(trx).await?;
461 match version {
462 None => {
463 if allow_creation {
464 self.initialize_directory(trx).await
465 } else {
466 Ok(())
467 }
468 }
469 Some(versions) => {
470 if versions.len() < 12 {
471 return Err(DirectoryError::Version(
472 "incorrect version length".to_string(),
473 ));
474 }
475 let mut arr = [0u8; 4];
476 arr.copy_from_slice(&versions[0..4]);
477 let major: u32 = u32::from_le_bytes(arr);
478
479 arr.copy_from_slice(&versions[4..8]);
480 let minor: u32 = u32::from_le_bytes(arr);
481
482 arr.copy_from_slice(&versions[8..12]);
483 let patch: u32 = u32::from_le_bytes(arr);
484
485 if major > MAJOR_VERSION {
486 let msg = format!(
487 "cannot load directory with version {major}.{minor}.{patch} using directory layer {MAJOR_VERSION}.{MINOR_VERSION}.{PATCH_VERSION}"
488 );
489 return Err(DirectoryError::Version(msg));
490 }
491
492 if minor > MINOR_VERSION && allow_creation {
493 let msg = format!(
494 "directory with version {major}.{minor}.{patch} is read-only when opened using directory layer {MAJOR_VERSION}.{MINOR_VERSION}.{PATCH_VERSION}"
495 );
496 return Err(DirectoryError::Version(msg));
497 }
498
499 Ok(())
500 }
501 }
502 }
503
504 async fn initialize_directory(&self, trx: &Transaction) -> Result<(), DirectoryError> {
506 let mut value = vec![];
507 value.extend(&MAJOR_VERSION.to_le_bytes());
508 value.extend(&MINOR_VERSION.to_le_bytes());
509 value.extend(&PATCH_VERSION.to_le_bytes());
510 let version_subspace: &[u8] = b"version";
511 let directory_version_key = self.root_node.subspace(&version_subspace);
512 trx.set(directory_version_key.bytes(), &value);
513
514 Ok(())
515 }
516
517 async fn get_version_value(&self, trx: &Transaction) -> FdbResult<Option<FdbSlice>> {
518 let version_subspace: &[u8] = b"version";
519 let version_key = self.root_node.subspace(&version_subspace);
520
521 trx.get(version_key.bytes(), false).await
522 }
523
524 async fn exists_internal(
525 &self,
526 trx: &Transaction,
527 path: &[String],
528 ) -> Result<bool, DirectoryError> {
529 self.check_version(trx, false).await?;
530
531 match self.find(trx, path).await? {
532 None => Ok(false),
533 Some(node) if node.is_in_partition(false) => {
534 node.get_contents()?
535 .exists(trx, &node.get_partition_subpath())
536 .await
537 }
538 Some(_node) => Ok(true),
539 }
540 }
541
542 async fn list_internal(
543 &self,
544 trx: &Transaction,
545 path: &[String],
546 ) -> Result<Vec<String>, DirectoryError> {
547 self.check_version(trx, false).await?;
548
549 let node = self
550 .find(trx, path)
551 .await?
552 .ok_or(DirectoryError::PathDoesNotExists)?;
553 if node.is_in_partition(true) {
554 match node.get_contents()? {
555 DirectoryOutput::DirectorySubspace(_) => unreachable!("already in partition"),
556 DirectoryOutput::DirectoryPartition(directory_partition) => {
557 return directory_partition
558 .directory_subspace
559 .directory_layer
560 .list(trx, &node.get_partition_subpath())
561 .await;
562 }
563 };
564 }
565
566 node.list_sub_folders(trx).await
567 }
568
569 async fn move_to_internal(
570 &self,
571 trx: &Transaction,
572 old_path: &[String],
573 new_path: &[String],
574 ) -> Result<DirectoryOutput, DirectoryError> {
575 self.check_version(trx, true).await?;
576
577 if old_path.len() <= new_path.len()
578 && compare_slice(old_path, &new_path[..old_path.len()]) == Ordering::Equal
579 {
580 return Err(DirectoryError::CannotMoveBetweenSubdirectory);
581 }
582
583 let old_node = self.find(trx, old_path).await?;
584 let new_node = self.find(trx, new_path).await?;
585
586 let old_node = match old_node {
587 None => return Err(DirectoryError::PathDoesNotExists),
588 Some(n) => n,
589 };
590 let old_node_exists_in_partition = old_node.is_in_partition(false);
591
592 match new_node {
593 None => {
594 if old_node_exists_in_partition {
595 return Err(DirectoryError::CannotMoveBetweenPartition);
596 }
597 }
598 Some(new_node) => {
599 let new_node_exists_in_partition = new_node.is_in_partition(false);
600 if old_node_exists_in_partition || new_node_exists_in_partition {
601 if !old_node_exists_in_partition
602 || !new_node_exists_in_partition
603 || !old_node.current_path.eq(&new_node.current_path)
604 {
605 return Err(DirectoryError::CannotMoveBetweenPartition);
606 }
607
608 return new_node
609 .get_contents()?
610 .move_to(
611 trx,
612 &old_node.get_partition_subpath(),
613 &new_node.get_partition_subpath(),
614 )
615 .await;
616 }
617 return Err(DirectoryError::DirAlreadyExists);
618 }
619 }
620
621 let (new_path_last, parent_path) = new_path
622 .split_last()
623 .ok_or(DirectoryError::DirAlreadyExists)?;
624
625 let parent_node = self
626 .find(trx, parent_path)
627 .await?
628 .ok_or(DirectoryError::ParentDirDoesNotExists)?;
629
630 let key = parent_node
631 .subspace
632 .subspace(&(DEFAULT_SUB_DIRS, new_path_last));
633 let value: Vec<u8> = self.node_subspace.unpack(old_node.subspace.bytes())?;
634 trx.set(key.bytes(), &value);
635
636 self.remove_from_parent(trx, old_path).await?;
637
638 self.contents_of_node(&old_node.subspace, new_path, &old_node.layer)
639 }
640
641 async fn remove_from_parent(
642 &self,
643 trx: &Transaction,
644 path: &[String],
645 ) -> Result<(), DirectoryError> {
646 let (last_element, parent_path) = path
647 .split_last()
648 .ok_or(DirectoryError::BadDestinationDirectory)?;
649
650 match self.find(trx, parent_path).await? {
651 None => {}
652 Some(parent_node) => {
653 let key = parent_node.subspace.pack(&(DEFAULT_SUB_DIRS, last_element));
654 trx.clear(&key);
655 }
656 }
657
658 Ok(())
659 }
660
661 #[async_recursion]
662 async fn remove_internal(
663 &self,
664 trx: &Transaction,
665 path: &[String],
666 fail_on_nonexistent: bool,
667 ) -> Result<bool, DirectoryError> {
668 self.check_version(trx, true).await?;
669
670 if path.is_empty() {
671 return Err(DirectoryError::CannotModifyRootDirectory);
672 }
673
674 let node = match self.find(trx, path).await? {
675 Some(node) => node,
676 None if fail_on_nonexistent => return Err(DirectoryError::DirectoryDoesNotExists),
677 None => return Ok(false),
678 };
679
680 if node.is_in_partition(false) {
681 match node.get_contents()? {
682 DirectoryOutput::DirectorySubspace(_) => {
683 unreachable!("already directory partition")
684 }
685 DirectoryOutput::DirectoryPartition(d) => {
686 return d
687 .directory_subspace
688 .directory_layer
689 .remove_internal(trx, &node.get_partition_subpath(), fail_on_nonexistent)
690 .await;
691 }
692 }
693 }
694
695 self.remove_recursive(trx, &node.subspace).await?;
696 self.remove_from_parent(trx, path).await?;
697
698 Ok(true)
699 }
700
701 #[async_recursion]
702 async fn remove_recursive(
703 &self,
704 trx: &Transaction,
705 node_sub: &Subspace,
706 ) -> Result<(), DirectoryError> {
707 let sub_dir = node_sub.subspace(&DEFAULT_SUB_DIRS);
708 let range_option = RangeOption::from(&sub_dir);
709
710 let mut stream = std::pin::pin!(trx.get_ranges_keyvalues(range_option, false));
711 while let Some(row_key) = stream.try_next().await? {
712 let sub_node = self.node_with_prefix(&row_key.value());
713 self.remove_recursive(trx, &sub_node).await?;
714 }
715
716 let node_prefix: Vec<u8> = self.node_subspace.unpack(node_sub.bytes())?;
717
718 trx.clear_range(&node_prefix, &strinc(node_prefix.to_owned()));
719 trx.clear_subspace_range(node_sub);
720
721 Ok(())
722 }
723}
724
725#[async_trait]
726impl Directory for DirectoryLayer {
727 async fn create_or_open(
728 &self,
729 txn: &Transaction,
730 path: &[String],
731 prefix: Option<&[u8]>,
732 layer: Option<&[u8]>,
733 ) -> Result<DirectoryOutput, DirectoryError> {
734 self.create_or_open_internal(txn, path, prefix, layer, true, true)
735 .await
736 }
737
738 async fn create(
739 &self,
740 txn: &Transaction,
741 path: &[String],
742 prefix: Option<&[u8]>,
743 layer: Option<&[u8]>,
744 ) -> Result<DirectoryOutput, DirectoryError> {
745 self.create_or_open_internal(txn, path, prefix, layer, true, false)
746 .await
747 }
748
749 async fn open(
750 &self,
751 txn: &Transaction,
752 path: &[String],
753 layer: Option<&[u8]>,
754 ) -> Result<DirectoryOutput, DirectoryError> {
755 self.create_or_open_internal(txn, path, None, layer, false, true)
756 .await
757 }
758
759 async fn exists(&self, trx: &Transaction, path: &[String]) -> Result<bool, DirectoryError> {
760 self.exists_internal(trx, path).await
761 }
762
763 async fn move_directory(
764 &self,
765 _trx: &Transaction,
766 _new_path: &[String],
767 ) -> Result<DirectoryOutput, DirectoryError> {
768 Err(DirectoryError::CannotMoveRootDirectory)
769 }
770
771 async fn move_to(
777 &self,
778 trx: &Transaction,
779 old_path: &[String],
780 new_path: &[String],
781 ) -> Result<DirectoryOutput, DirectoryError> {
782 self.move_to_internal(trx, old_path, new_path).await
783 }
784
785 async fn remove(&self, trx: &Transaction, path: &[String]) -> Result<bool, DirectoryError> {
786 self.remove_internal(trx, path, true).await
787 }
788
789 async fn remove_if_exists(
790 &self,
791 trx: &Transaction,
792 path: &[String],
793 ) -> Result<bool, DirectoryError> {
794 self.remove_internal(trx, path, false).await
795 }
796
797 async fn list(
798 &self,
799 trx: &Transaction,
800 path: &[String],
801 ) -> Result<Vec<String>, DirectoryError> {
802 self.list_internal(trx, path).await
803 }
804}