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}