Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.
TypeScript agentaiai-agentsall-in-onecrmcrm-systememaillinearmcpmessagingnotesnotionofficerustslackslack-alternativestartupstartup-toolstypescriptworkspace
//! Blocks: paragraphs, tables and their rows and cells, content controls.
//!
//! A story (the body, a header, a footnote) is a tree of blocks addressed by
//! stable ids. Each block keeps its own element's attributes and property
//! elements as XML, and children are ordered by fractional position keys, so
//! the same tree maps directly onto the collaborative maps: concurrent edits
//! to different blocks never conflict, and inserting a paragraph never
//! renumbers its neighbours.
use super::content::Content;
use crate::hash::FxMap;
use pptx_engine::collab::order;
use serde::{Deserialize, Serialize};
use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
static VERSION: AtomicU64 = AtomicU64::new(1);
/// A version number no other change in this process has used, so a block's
/// (id, version) identifies its content across stories and document copies.
pub fn next_version() -> u64 {
VERSION.fetch_add(1, Ordering::Relaxed)
}
/// Identifies a block, stable across edits, saves and peers.
#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct BlockId(Arc<str>);
impl Serialize for BlockId {
fn serialize<S: serde::Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
s.serialize_str(&self.0)
}
}
impl<'de> Deserialize<'de> for BlockId {
fn deserialize<D: serde::Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
let s = String::deserialize(d)?;
Ok(BlockId(s.into()))
}
}
impl BlockId {
/// Wraps an id string.
pub fn new(id: &str) -> Self {
Self(id.into())
}
/// The id as a string.
pub fn as_str(&self) -> &str {
&self.0
}
}
impl std::fmt::Debug for BlockId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "#{}", self.0)
}
}
impl std::fmt::Display for BlockId {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.0)
}
}
/// What a block is.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub enum BlockKind {
/// `w:p`; `props` is its `w:pPr`, `content` its runs.
#[serde(rename = "p")]
Paragraph,
/// `w:tbl`; `props` is `w:tblPr` and `w:tblGrid`.
#[serde(rename = "tbl")]
Table,
/// `w:tr`; `props` is `w:tblPrEx` and `w:trPr`.
#[serde(rename = "tr")]
Row,
/// `w:tc`; `props` is `w:tcPr`.
#[serde(rename = "tc")]
Cell,
/// A block-level element wrapping blocks (`w:sdt`, `w:customXml`);
/// `props` is JSON `[open, close]` markup around the children.
#[serde(rename = "sdt")]
Container,
/// Any other block-level element, kept verbatim in `props`.
#[serde(rename = "x")]
Opaque,
}
impl BlockKind {
/// The short code used in collaborative entries.
pub fn code(self) -> &'static str {
match self {
BlockKind::Paragraph => "p",
BlockKind::Table => "tbl",
BlockKind::Row => "tr",
BlockKind::Cell => "tc",
BlockKind::Container => "sdt",
BlockKind::Opaque => "x",
}
}
/// Parses a short code.
pub fn from_code(code: &str) -> Option<Self> {
Some(match code {
"p" => BlockKind::Paragraph,
"tbl" => BlockKind::Table,
"tr" => BlockKind::Row,
"tc" => BlockKind::Cell,
"sdt" => BlockKind::Container,
"x" => BlockKind::Opaque,
_ => return None,
})
}
}
/// One block.
#[derive(Clone, Debug)]
pub struct Block {
/// Stable id.
pub id: BlockId,
/// Kind.
pub kind: BlockKind,
/// The containing block (`None` = the story itself).
pub parent: Option<BlockId>,
/// Fractional position among its siblings.
pub order: String,
/// Attributes of the block's element as written (with a leading space).
pub attrs: String,
/// Property elements (or the whole element for opaque blocks), as XML.
pub props: String,
/// Runs of a paragraph.
pub content: Content,
/// Bumped on every change; layout caches key on it.
pub version: u64,
}
impl Block {
/// A new block.
pub fn new(id: BlockId, kind: BlockKind, parent: Option<BlockId>, order: String) -> Self {
Self {
id,
kind,
parent,
order,
attrs: String::new(),
props: String::new(),
content: Content::new(),
version: 0,
}
}
/// The open/close markup of a container.
pub fn container_markup(&self) -> (String, String) {
serde_json::from_str::<(String, String)>(&self.props).unwrap_or_default()
}
}
/// A tree of blocks.
#[derive(Clone, Debug, Default)]
pub struct Story {
blocks: FxMap<BlockId, Block>,
/// Children of each parent (`None` = top level), sorted by (order, id).
children: FxMap<Option<BlockId>, Vec<BlockId>>,
/// Changes on every change (a [`next_version`] value).
revision: u64,
/// Changes when blocks are added, removed or moved (not when their
/// content or properties change).
structure: u64,
}
static NO_CHILDREN: Vec<BlockId> = Vec::new();
impl Story {
/// An empty story.
pub fn new() -> Self {
Self::default()
}
/// Changes on every change to the story.
pub fn revision(&self) -> u64 {
self.revision
}
/// Changes when blocks are added, removed or moved: what depends only on
/// the order of blocks (not their text) keys on it.
pub fn structure(&self) -> u64 {
self.structure
}
/// Number of blocks.
pub fn len(&self) -> usize {
self.blocks.len()
}
/// Whether the story has no blocks.
pub fn is_empty(&self) -> bool {
self.blocks.is_empty()
}
/// A block.
pub fn get(&self, id: &BlockId) -> Option<&Block> {
self.blocks.get(id)
}
/// A block, for changing. Bumps its version.
pub fn get_mut(&mut self, id: &BlockId) -> Option<&mut Block> {
let version = next_version();
self.revision = version;
let block = self.blocks.get_mut(id)?;
block.version = version;
Some(block)
}
/// Whether the block exists.
pub fn contains(&self, id: &BlockId) -> bool {
self.blocks.contains_key(id)
}
/// Every block, in no particular order.
pub fn blocks(&self) -> impl Iterator<Item = &Block> {
self.blocks.values()
}
/// Children of `parent` (`None` = top level), in order.
pub fn children(&self, parent: Option<&BlockId>) -> &[BlockId] {
self.children.get(&parent.cloned()).unwrap_or(&NO_CHILDREN)
}
fn sort_children(&mut self, parent: Option<&BlockId>) {
let blocks = &self.blocks;
if let Some(list) = self.children.get_mut(&parent.cloned()) {
list.sort_by(|a, b| {
let (ka, kb) = (
blocks.get(a).map_or("", |x| x.order.as_str()),
blocks.get(b).map_or("", |x| x.order.as_str()),
);
ka.cmp(kb).then_with(|| a.cmp(b))
});
}
}
/// Where a block with this position key and id goes among `list`
/// (sorted by key, then id).
fn slot(blocks: &FxMap<BlockId, Block>, list: &[BlockId], order: &str, id: &BlockId) -> usize {
list.partition_point(|c| {
let key = blocks.get(c).map_or("", |x| x.order.as_str());
(key, c) < (order, id)
})
}
/// Adds or replaces a block, keeping its parent's children ordered.
/// Placing it costs a binary search, so reading a long document's
/// blocks one by one stays linear.
pub fn insert(&mut self, mut block: Block) {
self.revision = next_version();
block.version = self.revision;
let id = block.id.clone();
let same_place = self
.blocks
.get(&id)
.is_some_and(|old| old.parent == block.parent && old.order == block.order);
if same_place {
// Content or properties only: the block keeps its place.
self.blocks.insert(id, block);
return;
}
self.structure = self.revision;
// Take it out of the list it is in now.
if let Some(old) = self.blocks.get(&id) {
let blocks = &self.blocks;
if let Some(list) = self.children.get_mut(&old.parent) {
let at = Self::slot(blocks, list, &old.order, &id);
if list.get(at) == Some(&id) {
list.remove(at);
} else {
list.retain(|c| *c != id);
}
}
}
let parent = block.parent.clone();
let order = block.order.clone();
self.blocks.insert(id.clone(), block);
let blocks = &self.blocks;
let list = self.children.entry(parent).or_default();
let at = Self::slot(blocks, list, &order, &id);
list.insert(at, id);
}
/// Changes a block's position key (and parent).
pub fn move_block(&mut self, id: &BlockId, parent: Option<BlockId>, order: String) {
let Some(mut block) = self.blocks.get(id).cloned() else {
return;
};
block.parent = parent;
block.order = order;
self.insert(block);
}
/// Removes a block and everything inside it; returns the removed ids.
pub fn remove(&mut self, id: &BlockId) -> Vec<BlockId> {
let mut removed = Vec::new();
let mut stack = vec![id.clone()];
while let Some(at) = stack.pop() {
if let Some(kids) = self.children.remove(&Some(at.clone())) {
stack.extend(kids);
}
if let Some(b) = self.blocks.remove(&at) {
if let Some(list) = self.children.get_mut(&b.parent) {
list.retain(|c| *c != at);
}
removed.push(at);
}
}
self.revision = next_version();
self.structure = self.revision;
removed
}
/// Removes one block, keeping its children (which become orphans until
/// re-parented or removed).
pub fn remove_one(&mut self, id: &BlockId) -> Option<Block> {
let b = self.blocks.remove(id)?;
if let Some(list) = self.children.get_mut(&b.parent) {
list.retain(|c| c != id);
}
self.revision = next_version();
self.structure = self.revision;
Some(b)
}
/// Visits blocks depth-first in document order.
pub fn walk(&self, mut f: impl FnMut(&Block, usize)) {
fn go(
story: &Story,
parent: Option<&BlockId>,
depth: usize,
f: &mut dyn FnMut(&Block, usize),
) {
for id in story.children(parent) {
if let Some(b) = story.blocks.get(id) {
f(b, depth);
go(story, Some(id), depth + 1, f);
}
}
}
go(self, None, 0, &mut f);
}
/// Visits a block and everything inside it, depth-first in order.
pub fn walk_from(&self, id: &BlockId, f: &mut dyn FnMut(&Block)) {
let Some(b) = self.blocks.get(id) else {
return;
};
f(b);
for c in self.children(Some(id)) {
self.walk_from(c, f);
}
}
/// Paragraph ids in document order (including those inside tables).
pub fn paragraphs(&self) -> Vec<BlockId> {
let mut out = Vec::new();
self.walk(|b, _| {
if b.kind == BlockKind::Paragraph {
out.push(b.id.clone());
}
});
out
}
/// The chain of ancestors of a block, nearest first.
pub fn ancestors(&self, id: &BlockId) -> Vec<BlockId> {
let mut out = Vec::new();
let mut at = self.blocks.get(id).and_then(|b| b.parent.clone());
while let Some(p) = at {
at = self.blocks.get(&p).and_then(|b| b.parent.clone());
out.push(p);
}
out
}
/// The position key for a new child of `parent` placed after `after`
/// (`None` = first) and before the sibling that follows it.
pub fn key_after(&self, parent: Option<&BlockId>, after: Option<&BlockId>) -> String {
let kids = self.children(parent);
let index = match after {
Some(a) => kids
.iter()
.position(|k| k == a)
.map_or(kids.len(), |i| i + 1),
None => 0,
};
let low = index
.checked_sub(1)
.and_then(|i| kids.get(i))
.and_then(|k| self.blocks.get(k))
.map(|b| b.order.as_str());
let high = kids
.get(index)
.and_then(|k| self.blocks.get(k))
.map(|b| b.order.as_str());
order::key_between(low, high)
}
/// The position key for a new child of `parent` placed just before
/// `before`.
pub fn key_before(&self, parent: Option<&BlockId>, before: &BlockId) -> String {
let kids = self.children(parent);
let index = kids.iter().position(|k| k == before).unwrap_or(0);
let low = index
.checked_sub(1)
.and_then(|i| kids.get(i))
.and_then(|k| self.blocks.get(k))
.map(|b| b.order.as_str());
let high = kids
.get(index)
.and_then(|k| self.blocks.get(k))
.map(|b| b.order.as_str());
order::key_between(low, high)
}
/// Re-sorts every children list (after bulk changes to order keys).
pub fn resort(&mut self) {
let parents: Vec<Option<BlockId>> = self.children.keys().cloned().collect();
for p in parents {
self.sort_children(p.as_ref());
}
}
/// Blocks whose parent is missing (left behind by concurrent deletes).
pub fn orphans(&self) -> Vec<BlockId> {
self.blocks
.values()
.filter(|b| {
b.parent
.as_ref()
.is_some_and(|p| !self.blocks.contains_key(p))
})
.map(|b| b.id.clone())
.collect()
}
}
/// Generates block ids: sequential for documents opened locally, random
/// (per-peer seeded) for collaborative ones so concurrent inserts never collide.
#[derive(Debug)]
pub struct IdGen {
next: u64,
random: Option<Arc<pptx_engine::opc::IdSource>>,
/// Put before sequential ids (stories outside the body).
prefix: Option<Box<str>>,
}
impl IdGen {
/// Sequential ids starting at 1.
pub fn sequential() -> Self {
Self {
next: 1,
random: None,
prefix: None,
}
}
/// Sequential ids after a prefix: stable for a story read from the same
/// XML, and distinct from every other story's.
pub fn prefixed(prefix: &str) -> Self {
Self {
next: 1,
random: None,
prefix: Some(prefix.into()),
}
}
/// Random ids from a seeded source.
pub fn random(seed: u64) -> Self {
Self {
next: 1,
random: Some(Arc::new(pptx_engine::opc::IdSource::new(seed))),
prefix: None,
}
}
/// Whether ids are random.
pub fn is_random(&self) -> bool {
self.random.is_some()
}
/// The random source, if any.
pub fn source(&self) -> Option<&Arc<pptx_engine::opc::IdSource>> {
self.random.as_ref()
}
/// The next id.
pub fn next_id(&mut self) -> BlockId {
match &self.random {
Some(r) => BlockId::new(&radix36(r.next_in(1 << 40..1 << 52))),
None => {
let n = self.next;
self.next += 1;
match &self.prefix {
Some(p) => BlockId::new(&format!("{p}{}", radix36(n))),
None => BlockId::new(&radix36(n)),
}
}
}
}
}
fn radix36(mut n: u64) -> String {
const DIGITS: &[u8] = b"0123456789abcdefghijklmnopqrstuvwxyz";
let mut out = Vec::new();
loop {
out.push(DIGITS[(n % 36) as usize]);
n /= 36;
if n == 0 {
break;
}
}
out.reverse();
String::from_utf8(out).unwrap_or_default()
}
/// Spreads `count` fresh position keys evenly.
pub fn initial_keys(count: usize) -> Vec<String> {
order::keys_between(None, None, count)
}
#[cfg(test)]
mod test;