Skip to main content

cord_rs/
lib.rs

1//! A rope-like byte sequence with O(log n) append, prepend and slicing, O(1)
2//! cloning, and a 16 byte footprint with 15 bytes of inline storage.
3//!
4//! # When to use a `Cord`
5//!
6//! A [`Cord`] is designed for large byte sequences that change over their
7//! lifetime or are shared across API boundaries: wire-format messages that
8//! get headers prepended or payloads appended, buffers assembled from many
9//! pieces, or data that is sliced and passed around without copying. For
10//! small, contiguous, rarely modified data prefer `Vec<u8>` or
11//! `bytes::Bytes`.
12//!
13//! # Example
14//!
15//! ```
16//! use cord_rs::{Cord, CordBuffer};
17//!
18//! // Small values live inline; no allocation.
19//! let mut cord = Cord::from("hello");
20//! assert_eq!(cord.len(), 5);
21//!
22//! // Append and prepend from byte- and string-like sources.
23//! cord.append(" world");
24//! cord.prepend(">> ");
25//! // This small slice is copied inline; larger slices share backing storage.
26//! let world = cord.slice(9..);
27//! assert_eq!(world, "world");
28//!
29//! // Large owned buffers are adopted rather than copied.
30//! cord.append(vec![b'!'; 4096]);
31//! assert_eq!(cord.len(), 3 + 11 + 4096);
32//!
33//! // Zero-copy building through `CordBuffer`.
34//! let mut buffer = CordBuffer::with_capacity(32);
35//! buffer.put_slice(b" tail");
36//! cord.append(buffer);
37//!
38//! // Iterate chunks for efficient processing, or bytes for convenience.
39//! let total: usize = cord.chunks().map(<[u8]>::len).sum();
40//! assert_eq!(total, cord.len());
41//! assert!(cord.ends_with(" tail"));
42//! ```
43//!
44//! # Representation
45//!
46//! A `Cord` is 16 bytes: either up to 15 bytes of inline data, or a pointer
47//! to a reference counted tree. Trees are B-trees of up to 6 edges per node
48//! whose leaves reference immutable *flat* buffers (allocated in size classes
49//! from 32 bytes to 4 KiB by default, or up to 64 KiB when built through
50//! [`CordBuffer::with_capacity_and_block_size`], see its docs for the sizing
51//! trade-offs), *external* buffers owned by user values (`Vec<u8>`,
52//! `Arc<[u8]>`, custom [`Cord::from_owner`] values, ...), or *substrings* of
53//! those. Buffers referenced by a single cord are grown in place; buffers
54//! shared between cords are never modified.
55//!
56//! # Features
57//!
58//! * `std` (default) — `std::io` integration: `Read`/`BufRead`/`Seek` on
59//!   [`Cursor`](crate::iter::Cursor), and `Write` on [`Cord`] and
60//!   `CordBuffer`. Building with `default-features = false` gives a crate using
61//!   `no_std` and `alloc` (with any global allocator); everything else —
62//!   including `core::fmt::Write` for [`Cord`] — stays available. `no_std`
63//!   targets need 32-bit and pointer-width atomics (`target_has_atomic = "32"`
64//!   and `"ptr"`).
65//! * `bytes` — `bytes::Buf` for [`Cord`] and [`Cursor`](crate::iter::Cursor),
66//!   `bytes::BufMut` for `CordWriter` and `CordBuffer`, and zero-copy
67//!   conversions with `bytes::Bytes`. With both `bytes` and `std` enabled,
68//!   `CordWriter` also implements `std::io::Write`.
69//! * `serde` — `Serialize` / `Deserialize` for [`Cord`] as a byte sequence.
70//!
71#![no_std]
72#![cfg_attr(docsrs, feature(doc_cfg))]
73
74#[cfg(not(all(target_has_atomic = "32", target_has_atomic = "ptr")))]
75compile_error!(
76    "cord-rs requires 32-bit and pointer-width atomics (`target_has_atomic = \"32\"` and \"ptr\")"
77);
78
79extern crate alloc;
80#[cfg(feature = "std")]
81extern crate std;
82
83mod buffer;
84mod cord;
85mod inline_data;
86#[cfg(feature = "std")]
87#[cfg_attr(docsrs, doc(cfg(feature = "std")))]
88mod io;
89pub mod iter;
90mod rep;
91mod source;
92
93#[cfg(feature = "bytes")]
94#[cfg_attr(docsrs, doc(cfg(feature = "bytes")))]
95mod bytes_impl;
96#[cfg(feature = "serde")]
97#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
98mod serde_impl;
99
100/// Compiles and runs every code block in `README.md` as a doctest, so the
101/// README cannot drift from the API. The README's examples are std-flavoured
102/// (`read_into_cord` and `parse_frame` use `std::io::Read`), so this only
103/// runs with the `std` feature enabled.
104#[cfg(all(doctest, feature = "std"))]
105#[doc = include_str!("../README.md")]
106struct ReadmeDoctests;
107
108pub use buffer::CordBuffer;
109pub use cord::{Cord, MemoryAccounting};
110pub use source::{CordIndex, CordLike, CordSource};
111
112#[cfg(feature = "bytes")]
113#[cfg_attr(docsrs, doc(cfg(feature = "bytes")))]
114pub use bytes_impl::CordWriter;
115
116/// Compile-time guard against silently losing `Send`/`Sync` on the crate's
117/// public types. `Cord` and `CordBuffer` assert both explicitly (see their
118/// `unsafe impl` blocks); `Chunks`/`Cursor`/`Bytes` (and, with the `bytes`
119/// feature, `CordWriter`) get them for free by auto-derivation from their
120/// fields — in particular `rep::RepRef`'s own `unsafe impl` — so a future
121/// field change that broke that derivation would otherwise compile clean
122/// with no other signal anywhere. Calling `assert_send_sync::<T>()` from a
123/// `const` item forces the compiler to resolve `T: Send + Sync` for that
124/// exact `T` right here, at definition time — no value of the type, or any
125/// other call site, is needed. The same silent-loss argument applies to the
126/// unwind-safety auto traits: `Vec<u8>` and `bytes::Bytes` are both
127/// `UnwindSafe + RefUnwindSafe`, so a raw-pointer field change here could
128/// just as quietly drop `Cord` out of them with no other signal.
129const fn assert_send_sync<T: ?Sized + Send + Sync>() {}
130
131const _: () = {
132    assert_send_sync::<Cord>();
133    assert_send_sync::<CordBuffer>();
134    assert_send_sync::<crate::iter::Chunks<'_>>();
135    assert_send_sync::<crate::iter::Cursor<'_>>();
136    assert_send_sync::<crate::iter::Bytes<'_>>();
137};
138
139#[cfg(feature = "bytes")]
140const _: () = assert_send_sync::<CordWriter<'_>>();
141
142/// Compile-time guard against silently losing unwind-safety on the crate's
143/// public types (see [`assert_send_sync`] for why this needs a `const` call
144/// rather than relying on the auto trait alone). `CordWriter` is deliberately
145/// excluded: it holds a `&mut Cord`, so it is correctly `!UnwindSafe`, the
146/// same way `std::io::BufWriter<&mut W>` is.
147const fn assert_unwind_safe<T: ?Sized + core::panic::UnwindSafe + core::panic::RefUnwindSafe>() {}
148
149const _: () = {
150    assert_unwind_safe::<Cord>();
151    assert_unwind_safe::<CordBuffer>();
152    assert_unwind_safe::<crate::iter::Chunks<'_>>();
153    assert_unwind_safe::<crate::iter::Cursor<'_>>();
154    assert_unwind_safe::<crate::iter::Bytes<'_>>();
155};
156
157/// Internal inspection hooks for tests and benchmarks. Exempt from semver
158/// guarantees: this module exists solely for the crate's own tests and
159/// benchmarks and may change or disappear without notice, regardless of
160/// crate version.
161#[doc(hidden)]
162pub mod __internal {
163    use core::ptr::NonNull;
164
165    use alloc::format;
166    use alloc::string::String;
167
168    use crate::Cord;
169    use crate::rep::btree::{CordRepBtree, as_btree};
170    use crate::rep::{self, OwnedRep, RepPtr, RepRef, RepView};
171
172    /// Maximum inline size of a `Cord`.
173    pub const MAX_INLINE: usize = rep::MAX_INLINE;
174    /// Maximum payload of a default flat.
175    pub const MAX_FLAT_LENGTH: usize = rep::flat::MAX_FLAT_LENGTH;
176    /// Minimum payload of a flat.
177    pub const MIN_FLAT_LENGTH: usize = rep::flat::MIN_FLAT_LENGTH;
178    /// Overhead of a flat allocation.
179    pub const FLAT_OVERHEAD: usize = rep::flat::FLAT_OVERHEAD;
180    /// Cords at most this size are copied rather than shared.
181    pub const MAX_BYTES_TO_COPY: usize = rep::MAX_BYTES_TO_COPY;
182    /// Maximum btree node fan-out.
183    pub const BTREE_MAX_CAPACITY: usize = rep::btree::MAX_CAPACITY;
184
185    /// Whether `cord` holds a tree (as opposed to inline data).
186    #[must_use]
187    pub fn is_tree(cord: &Cord) -> bool {
188        cord.is_tree()
189    }
190
191    /// Wraps `cord`'s root tree pointer, if any, as a borrowed [`RepRef`].
192    fn root(cord: &Cord) -> Option<RepRef<'_>> {
193        cord.tree_ref()
194    }
195
196    /// Whether `cord` holds a btree.
197    #[must_use]
198    pub fn is_btree(cord: &Cord) -> bool {
199        root(cord).is_some_and(RepRef::is_btree)
200    }
201
202    /// Whether `cord` holds a single flat node.
203    #[must_use]
204    pub fn is_flat(cord: &Cord) -> bool {
205        root(cord).is_some_and(RepRef::is_flat)
206    }
207
208    /// Whether `cord` holds a single external node.
209    #[must_use]
210    pub fn is_external(cord: &Cord) -> bool {
211        root(cord).is_some_and(RepRef::is_external)
212    }
213
214    /// Whether `cord` holds a single substring node.
215    #[must_use]
216    pub fn is_substring(cord: &Cord) -> bool {
217        root(cord).is_some_and(RepRef::is_substring)
218    }
219
220    /// Height of the btree, if any.
221    #[must_use]
222    pub fn btree_height(cord: &Cord) -> Option<usize> {
223        root(cord).and_then(|rep| match rep.view() {
224            RepView::Btree(tree) => Some(tree.height()),
225            _ => None,
226        })
227    }
228
229    /// Reference count of the root node (0 if inline).
230    #[must_use]
231    pub fn root_refcount(cord: &Cord) -> usize {
232        root(cord).map_or(0, RepRef::ref_get)
233    }
234
235    /// Validates the tree structure, returning an error message on failure.
236    pub fn validate(cord: &Cord) -> Result<(), String> {
237        let Some(tree) = cord.tree() else { return Ok(()) };
238        // SAFETY: the tree is live.
239        unsafe {
240            if tree.is_btree() {
241                CordRepBtree::check_valid(as_btree(tree), false)
242            } else if rep::is_data_edge(tree) {
243                Ok(())
244            } else {
245                Err(format!("unexpected root node type {}", tree.tag()))
246            }
247        }
248    }
249
250    /// Dumps the tree structure.
251    #[must_use]
252    pub fn dump(cord: &Cord, include_contents: bool) -> String {
253        let mut out = String::new();
254        match cord.tree() {
255            None => out.push_str("(inline)\n"),
256            // SAFETY: the tree is live.
257            Some(tree) => unsafe {
258                let _ = CordRepBtree::dump(NonNull::new(tree), "", include_contents, &mut out);
259            },
260        }
261        out
262    }
263
264    /// Forces exhaustive validation in debug assertions.
265    pub fn set_exhaustive_validation(enabled: bool) {
266        rep::btree::set_exhaustive_validation(enabled);
267    }
268
269    /// Size of a btree node.
270    pub const BTREE_NODE_SIZE: usize = core::mem::size_of::<CordRepBtree>();
271    /// Size of a substring node.
272    pub const SUBSTRING_NODE_SIZE: usize = core::mem::size_of::<rep::CordRepSubstring>();
273    /// Size accounted for an external node (excluding the referenced data).
274    pub const EXTERNAL_NODE_SIZE: usize = rep::external::EXTERNAL_REP_SIZE;
275
276    /// Creates a cord holding `data` in a single external node regardless of
277    /// its size. An empty `data` yields an empty cord.
278    #[must_use]
279    pub fn make_external(data: &[u8]) -> Cord {
280        if data.is_empty() {
281            return Cord::new();
282        }
283        // SAFETY: a fresh, non-empty external rep.
284        let owned =
285            unsafe { OwnedRep::from_raw(rep::external::CordRepExternal::create_global(data.to_vec())) };
286        Cord::from_owned_rep(owned)
287    }
288
289    /// Creates a cord holding a substring node over the flat or external node
290    /// of `src`. Requires `src` to hold a single flat or external node and
291    /// `0 < len < src.len()`.
292    ///
293    /// # Panics
294    ///
295    /// Panics if `src` is inline, if `src`'s tree is not a single flat or
296    /// external node, if `offset > src.len()`, if `len == 0`, if
297    /// `offset + len > src.len()`, or if `len >= src.len()` — i.e. unless
298    /// `offset`/`len` describe a non-empty, strict sub-range of `src`. The
299    /// checks are unconditional: this is the safe boundary over a rep-layer
300    /// constructor that only `debug_assert!`s its preconditions.
301    #[must_use]
302    pub fn make_substring(src: &Cord, offset: usize, len: usize) -> Cord {
303        let tree = src.tree().expect("make_substring: src must not be inline");
304        // SAFETY: `tree` is `src`'s live tree pointer for as long as `src` is
305        // borrowed, so reading its tag and length is sound.
306        let tree_len = unsafe {
307            assert!(
308                tree.is_flat() || tree.is_external(),
309                "make_substring: src must be a flat or external node"
310            );
311            tree.length()
312        };
313        assert!(
314            offset <= tree_len,
315            "make_substring: offset {offset} out of range for src of length {tree_len}"
316        );
317        assert!(len > 0, "make_substring: len must be non-zero");
318        assert!(
319            len <= tree_len - offset,
320            "make_substring: len {len} out of range for src of length {tree_len} at offset {offset}"
321        );
322        assert!(len < tree_len, "make_substring: len {len} must be less than src's length {tree_len}");
323        // SAFETY: `create` adopts the added reference; preconditions checked
324        // above.
325        let owned = unsafe {
326            let rep = rep::CordRepSubstring::create(rep::ref_rep(tree), offset, len);
327            OwnedRep::from_raw(rep.cast())
328        };
329        Cord::from_owned_rep(owned)
330    }
331
332    /// The allocated size of the flat node held by `cord`, if it holds one.
333    #[must_use]
334    pub fn flat_allocated_size(cord: &Cord) -> Option<usize> {
335        root(cord).and_then(|rep| match rep.view() {
336            RepView::Flat(flat) => Some(flat.allocated_size()),
337            _ => None,
338        })
339    }
340}