1use std::collections::{BTreeMap, BTreeSet};
2use std::fmt;
3use std::ops::RangeBounds;
4use std::str::FromStr;
5
6use serde::{Deserialize, Deserializer, Serialize};
7use xxhash_rust::xxh64::xxh64;
8
9use crate::address::{AddressRange, AddressSpace, AddressValue};
10
11const BASE32: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
12
13#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Serialize)]
19#[serde(transparent)]
20pub struct NoteId(String);
21
22impl NoteId {
23 pub const ENCODED_LEN: usize = 26;
24
25 pub fn allocate(previous_tip: Option<&Self>, content: &str) -> Self {
27 let depth = previous_tip.map(Self::depth).unwrap_or(0).saturating_add(1);
28 let hash = hash_payload(previous_tip, content);
29 Self::from_parts(depth, hash)
30 }
31
32 pub fn tip<'a>(ids: impl IntoIterator<Item = &'a Self>) -> Option<Self> {
34 ids.into_iter().max().cloned()
35 }
36
37 pub fn as_str(&self) -> &str {
38 &self.0
39 }
40
41 pub fn depth(&self) -> u64 {
42 decode(self.as_str()).0
43 }
44
45 pub fn hash(&self) -> u64 {
46 decode(self.as_str()).1
47 }
48
49 fn from_parts(depth: u64, hash: u64) -> Self {
50 let value = ((depth as u128) << 64) | (hash as u128);
51 Self(encode(value))
52 }
53}
54
55impl<'de> Deserialize<'de> for NoteId {
56 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
57 where
58 D: Deserializer<'de>,
59 {
60 let value = String::deserialize(deserializer)?;
61 Self::from_str(&value).map_err(serde::de::Error::custom)
62 }
63}
64
65impl fmt::Debug for NoteId {
66 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
67 f.debug_tuple("NoteId").field(&self.0).finish()
68 }
69}
70
71impl fmt::Display for NoteId {
72 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
73 f.write_str(&self.0)
74 }
75}
76
77impl FromStr for NoteId {
78 type Err = NoteIdError;
79
80 fn from_str(value: &str) -> Result<Self, Self::Err> {
81 if value.is_empty() || value.len() > Self::ENCODED_LEN {
82 return Err(NoteIdError::InvalidLength);
83 }
84 let (depth, hash) = try_decode(value)?;
85 Ok(Self::from_parts(depth, hash))
86 }
87}
88
89impl AsRef<str> for NoteId {
90 fn as_ref(&self) -> &str {
91 self.as_str()
92 }
93}
94
95#[derive(Debug, Clone, Copy, PartialEq, Eq)]
96pub enum NoteIdError {
97 InvalidLength,
98 InvalidCharacter,
99}
100
101impl fmt::Display for NoteIdError {
102 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
103 match self {
104 Self::InvalidLength => write!(
105 f,
106 "note id must be 1..={} base32 characters",
107 NoteId::ENCODED_LEN
108 ),
109 Self::InvalidCharacter => write!(f, "note id contains invalid base32 character"),
110 }
111 }
112}
113
114impl std::error::Error for NoteIdError {}
115
116#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Serialize, Deserialize)]
118#[serde(transparent)]
119pub struct NotePath(String);
120
121impl NotePath {
122 pub fn parse(path: &str) -> Result<Self, NotePathError> {
123 if path.is_empty() {
124 return Err(NotePathError::Empty);
125 }
126 if path.starts_with('.') || path.ends_with('.') || path.contains("..") {
127 return Err(NotePathError::Invalid);
128 }
129 for segment in path.split('.') {
130 if segment.is_empty() {
131 return Err(NotePathError::Invalid);
132 }
133 }
134 Ok(Self(path.to_string()))
135 }
136
137 pub fn as_str(&self) -> &str {
138 &self.0
139 }
140
141 pub fn segments(&self) -> impl Iterator<Item = &str> {
142 self.0.split('.')
143 }
144}
145
146impl fmt::Display for NotePath {
147 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
148 f.write_str(&self.0)
149 }
150}
151
152impl FromStr for NotePath {
153 type Err = NotePathError;
154
155 fn from_str(value: &str) -> Result<Self, Self::Err> {
156 Self::parse(value)
157 }
158}
159
160#[derive(Debug, Clone, Copy, PartialEq, Eq)]
161pub enum NotePathError {
162 Empty,
163 Invalid,
164}
165
166impl fmt::Display for NotePathError {
167 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
168 match self {
169 Self::Empty => write!(f, "note path must not be empty"),
170 Self::Invalid => write!(f, "note path must be dot-separated segments"),
171 }
172 }
173}
174
175impl std::error::Error for NotePathError {}
176
177#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
178pub enum NoteField {
179 String(String),
180 List(Vec<String>),
181}
182
183#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
186pub struct Note {
187 pub id: NoteId,
188 pub content: String,
189 pub tags: BTreeSet<String>,
190 pub fields: BTreeMap<String, NoteField>,
191 pub links: BTreeSet<NoteId>,
192}
193
194impl Note {
195 pub fn new(previous_tip: Option<&NoteId>, content: impl Into<String>) -> Self {
196 let content = content.into();
197 let id = NoteId::allocate(previous_tip, &content);
198 Self {
199 id,
200 content,
201 tags: BTreeSet::new(),
202 fields: BTreeMap::new(),
203 links: BTreeSet::new(),
204 }
205 }
206
207 pub fn with_metadata(
208 previous_tip: Option<&NoteId>,
209 content: impl Into<String>,
210 tags: BTreeSet<String>,
211 fields: BTreeMap<String, NoteField>,
212 links: BTreeSet<NoteId>,
213 ) -> Self {
214 let mut note = Self::new(previous_tip, content);
215 note.tags = tags;
216 note.fields = fields;
217 note.links = links;
218 note
219 }
220
221 pub fn set_content(&mut self, content: impl Into<String>) {
222 self.content = content.into();
223 }
224}
225
226#[derive(Debug, Default, Clone, PartialEq, Eq)]
228pub struct Notes {
229 by_id: BTreeMap<NoteId, Note>,
230}
231
232impl Notes {
233 pub fn insert(&mut self, note: Note) -> Option<Note> {
234 self.by_id.insert(note.id.clone(), note)
235 }
236
237 pub fn remove(&mut self, id: &NoteId) -> Option<Note> {
238 self.by_id.remove(id)
239 }
240
241 pub fn get(&self, id: &NoteId) -> Option<&Note> {
242 self.by_id.get(id)
243 }
244
245 pub fn tip(&self) -> Option<NoteId> {
246 self.by_id.keys().next_back().cloned()
247 }
248
249 pub fn create(&mut self, content: impl Into<String>) -> Note {
251 let note = Note::new(self.tip().as_ref(), content);
252 assert!(
253 self.by_id.insert(note.id.clone(), note.clone()).is_none(),
254 "duplicate note id"
255 );
256 note
257 }
258
259 pub fn iter(&self) -> impl Iterator<Item = (&NoteId, &Note)> {
260 self.by_id.iter()
261 }
262
263 pub fn len(&self) -> usize {
264 self.by_id.len()
265 }
266
267 pub fn is_empty(&self) -> bool {
268 self.by_id.is_empty()
269 }
270}
271
272#[derive(Debug, Default, Clone, PartialEq, Eq)]
274pub struct NoteAddressIndex {
275 positions: rangemap::RangeMap<AddressValue, Vec<NoteId>>,
276 ranges: BTreeMap<NoteId, AddressRange>,
277}
278
279impl NoteAddressIndex {
280 pub fn insert(&mut self, range: AddressRange, id: NoteId) {
281 if let Some(old_range) = self.ranges.remove(&id) {
282 self.remove_id_from_positions(old_range, &id);
283 }
284 self.ranges.insert(id.clone(), range);
285 self.add_id_to_positions(range, id);
286 }
287
288 pub fn remove(&mut self, id: &NoteId) -> Option<AddressRange> {
289 let range = self.ranges.remove(id)?;
290 self.remove_id_from_positions(range, id);
291 Some(range)
292 }
293
294 pub fn range(&self, id: &NoteId) -> Option<AddressRange> {
295 self.ranges.get(id).copied()
296 }
297
298 pub fn overlapping<'a>(&'a self, range: AddressRange, notes: &'a Notes) -> Vec<&'a Note> {
299 self.positions
300 .overlapping(range.start..range.end)
301 .flat_map(|(_, ids)| ids.iter())
302 .filter_map(|id| notes.get(id))
303 .collect()
304 }
305
306 pub fn inside<'a>(&'a self, range: AddressRange, notes: &'a Notes) -> Vec<&'a Note> {
307 self.positions
308 .overlapping(range.start..range.end)
309 .flat_map(|(indexed, ids)| {
310 if range.start <= indexed.start && indexed.end <= range.end {
311 ids.iter()
312 } else {
313 [].iter()
314 }
315 })
316 .filter_map(|id| notes.get(id))
317 .collect()
318 }
319
320 fn add_id_to_positions(&mut self, range: AddressRange, id: NoteId) {
321 let mut ids = self.ids_at_exact_range(range);
322 if !ids.contains(&id) {
323 ids.push(id);
324 }
325 self.positions.remove(range.start..range.end);
326 self.positions.insert(range.start..range.end, ids);
327 }
328
329 fn remove_id_from_positions(&mut self, range: AddressRange, id: &NoteId) {
330 let ids: Vec<NoteId> = self
331 .ids_at_exact_range(range)
332 .into_iter()
333 .filter(|existing| existing != id)
334 .collect();
335 self.positions.remove(range.start..range.end);
336 if !ids.is_empty() {
337 self.positions.insert(range.start..range.end, ids);
338 }
339 }
340
341 fn ids_at_exact_range(&self, range: AddressRange) -> Vec<NoteId> {
342 self.positions
343 .overlapping(range.start..range.end)
344 .find(|(indexed, _)| indexed.start == range.start && indexed.end == range.end)
345 .map(|(_, ids)| ids.clone())
346 .unwrap_or_default()
347 }
348}
349
350#[derive(Debug, Default, Clone, PartialEq, Eq)]
352pub struct NoteGlobalIndex {
353 paths: BTreeMap<NotePath, NoteId>,
354 by_id: BTreeMap<NoteId, NotePath>,
355}
356
357impl NoteGlobalIndex {
358 pub fn insert(&mut self, path: NotePath, id: NoteId) {
359 if let Some(old_path) = self.by_id.remove(&id) {
360 self.paths.remove(&old_path);
361 }
362 if let Some(old_id) = self.paths.remove(&path) {
363 self.by_id.remove(&old_id);
364 }
365 self.paths.insert(path.clone(), id.clone());
366 self.by_id.insert(id, path);
367 }
368
369 pub fn remove(&mut self, id: &NoteId) -> Option<NotePath> {
370 let path = self.by_id.remove(id)?;
371 self.paths.remove(&path);
372 Some(path)
373 }
374
375 pub fn path(&self, id: &NoteId) -> Option<&NotePath> {
376 self.by_id.get(id)
377 }
378
379 pub fn get<'a>(&'a self, path: &NotePath, notes: &'a Notes) -> Option<&'a Note> {
380 let id = self.paths.get(path)?;
381 notes.get(id)
382 }
383}
384
385#[derive(Debug, Default, Clone, PartialEq, Eq)]
387pub struct NoteDb {
388 pub notes: Notes,
389 pub global: NoteGlobalIndex,
390 address: BTreeMap<AddressSpace, NoteAddressIndex>,
391}
392
393impl NoteDb {
394 pub fn tip(&self) -> Option<NoteId> {
395 self.notes.tip()
396 }
397
398 pub fn create(&mut self, content: impl Into<String>) -> Note {
399 self.notes.create(content)
400 }
401
402 pub fn get(&self, id: &NoteId) -> Option<&Note> {
403 self.notes.get(id)
404 }
405
406 pub fn get_by_path(&self, path: &NotePath) -> Option<&Note> {
407 self.global.get(path, &self.notes)
408 }
409
410 pub fn address_index(&self, space: AddressSpace) -> Option<&NoteAddressIndex> {
411 self.address.get(&space)
412 }
413
414 pub fn set_address(&mut self, space: AddressSpace, range: AddressRange, note: Note) {
415 let id = note.id.clone();
416 self.notes.insert(note);
417 self.address.entry(space).or_default().insert(range, id);
418 }
419
420 pub fn set_global(&mut self, path: NotePath, note: Note) {
421 let id = note.id.clone();
422 self.notes.insert(note);
423 self.global.insert(path, id);
424 }
425
426 pub fn clear(&mut self, id: &NoteId) -> Option<Note> {
427 let note = self.notes.remove(id)?;
428 self.global.remove(id);
429 for index in self.address.values_mut() {
430 index.remove(id);
431 }
432 Some(note)
433 }
434
435 pub fn clear_address(&mut self, id: &NoteId) -> Option<(AddressSpace, AddressRange, Note)> {
436 let mut located = None;
437 for (&space, index) in &mut self.address {
438 if let Some(range) = index.remove(id) {
439 located = Some((space, range));
440 break;
441 }
442 }
443 let (space, range) = located?;
444 let note = self.notes.remove(id)?;
445 self.global.remove(id);
446 Some((space, range, note))
447 }
448
449 pub fn note_range(&self, space: AddressSpace, id: &NoteId) -> Option<AddressRange> {
450 self.address.get(&space)?.range(id)
451 }
452
453 pub fn get_notes_overlapping(
454 &self,
455 space: AddressSpace,
456 range: impl RangeBounds<AddressValue>,
457 ) -> Vec<&Note> {
458 let range = AddressRange::from(range);
459 self.address
460 .get(&space)
461 .map(|index| index.overlapping(range, &self.notes))
462 .unwrap_or_default()
463 }
464
465 pub fn get_notes_inside(
466 &self,
467 space: AddressSpace,
468 range: impl RangeBounds<AddressValue>,
469 ) -> Vec<&Note> {
470 let range = AddressRange::from(range);
471 self.address
472 .get(&space)
473 .map(|index| index.inside(range, &self.notes))
474 .unwrap_or_default()
475 }
476}
477
478fn hash_payload(previous_tip: Option<&NoteId>, content: &str) -> u64 {
479 match previous_tip {
480 None => xxh64(content.as_bytes(), 0),
481 Some(tip) => {
482 let tip_bytes = tip.as_str().as_bytes();
483 let content_bytes = content.as_bytes();
484 let mut combined = Vec::with_capacity(2 + tip_bytes.len() + 2 + content_bytes.len());
485 combined.extend_from_slice(&(tip_bytes.len() as u16).to_le_bytes());
486 combined.extend_from_slice(tip_bytes);
487 combined.extend_from_slice(&(content_bytes.len() as u16).to_le_bytes());
488 combined.extend_from_slice(content_bytes);
489 xxh64(&combined, 0)
490 }
491 }
492}
493
494fn encode(mut value: u128) -> String {
495 let mut buf = [0u8; NoteId::ENCODED_LEN];
496 for slot in buf.iter_mut().rev() {
497 *slot = BASE32[(value & 0x1F) as usize];
498 value >>= 5;
499 }
500 String::from_utf8(buf.to_vec()).expect("base32 alphabet is ascii")
501}
502
503fn decode(value: &str) -> (u64, u64) {
504 try_decode(value).expect("note id is canonical fixed-width")
505}
506
507fn try_decode(value: &str) -> Result<(u64, u64), NoteIdError> {
508 if value.is_empty() || value.len() > NoteId::ENCODED_LEN {
509 return Err(NoteIdError::InvalidLength);
510 }
511 let padded = format!(
512 "{:0>width$}",
513 value.to_ascii_uppercase(),
514 width = NoteId::ENCODED_LEN
515 );
516 let bytes = padded.as_bytes();
517 let msb = decode_base32(bytes[0]).ok_or(NoteIdError::InvalidCharacter)? as u128;
518 if msb > 0x7 {
519 return Err(NoteIdError::InvalidCharacter);
520 }
521 let mut lower = 0u128;
522 for (i, &byte) in bytes[1..].iter().enumerate() {
523 let digit = decode_base32(byte).ok_or(NoteIdError::InvalidCharacter)? as u128;
524 let shift = 5 * (bytes.len() - 2 - i);
525 lower |= digit << shift;
526 }
527 let bits = (msb << 125) | lower;
528 Ok(((bits >> 64) as u64, bits as u64))
529}
530
531fn decode_base32(byte: u8) -> Option<u8> {
532 match byte {
533 b'0'..=b'9' => Some(byte - b'0'),
534 b'A'..=b'H' => Some(byte - b'A' + 10),
535 b'J' | b'K' => Some(byte - b'A' + 10 - 1),
536 b'M' | b'N' => Some(byte - b'A' + 10 - 2),
537 b'P'..=b'T' => Some(byte - b'A' + 10 - 3),
538 b'V'..=b'Z' => Some(byte - b'A' + 10 - 4),
539 b'a'..=b'h' => Some(byte - b'a' + 10),
540 b'j' | b'k' => Some(byte - b'a' + 10 - 1),
541 b'm' | b'n' => Some(byte - b'a' + 10 - 2),
542 b'p'..=b't' => Some(byte - b'a' + 10 - 3),
543 b'v'..=b'z' => Some(byte - b'a' + 10 - 4),
544 _ => None,
545 }
546}
547
548#[cfg(test)]
549mod tests {
550 use super::*;
551
552 #[test]
553 fn ids_are_fixed_width() {
554 let id = NoteId::allocate(None, "hello");
555 assert_eq!(id.as_str().len(), NoteId::ENCODED_LEN);
556 }
557
558 #[test]
559 fn ids_sort_in_lamport_order() {
560 let first = Note::new(None, "alpha");
561 let second = Note::new(Some(&first.id), "beta");
562 let third = Note::new(Some(&second.id), "gamma");
563
564 assert!(first.id < second.id);
565 assert!(second.id < third.id);
566 assert_eq!(
567 NoteId::tip([&first.id, &second.id, &third.id]),
568 Some(third.id.clone())
569 );
570 }
571
572 #[test]
573 fn ids_sort_lexicographically_as_strings() {
574 let first = Note::new(None, "alpha");
575 let second = Note::new(Some(&first.id), "beta");
576 let third = Note::new(Some(&second.id), "gamma");
577
578 let mut sorted = [
579 first.id.to_string(),
580 second.id.to_string(),
581 third.id.to_string(),
582 ];
583 sorted.sort();
584 assert_eq!(
585 sorted,
586 [
587 first.id.to_string(),
588 second.id.to_string(),
589 third.id.to_string()
590 ]
591 );
592 assert_eq!(sorted.last().unwrap(), &third.id.to_string());
593 }
594
595 #[test]
596 fn concurrent_notes_from_same_tip_differ_by_hash() {
597 let first = Note::new(None, "shared tip");
598 let left = Note::new(Some(&first.id), "branch a");
599 let right = Note::new(Some(&first.id), "branch b");
600
601 assert_eq!(left.id.depth(), right.id.depth());
602 assert_ne!(left.id, right.id);
603 assert_ne!(left.id.hash(), right.id.hash());
604 }
605
606 #[test]
607 fn create_advances_tip() {
608 let mut notes = Notes::default();
609 let first = notes.create("one");
610 let second = notes.create("two");
611 assert_ne!(first.id, second.id);
612 assert_eq!(notes.tip(), Some(second.id));
613 }
614
615 #[test]
616 fn editing_content_does_not_change_id() {
617 let mut note = Note::new(None, "original");
618 let id = note.id.clone();
619 note.set_content("edited body");
620 note.tags.insert("todo".into());
621 assert_eq!(note.id, id);
622 }
623
624 #[test]
625 fn golden_replay_is_deterministic() {
626 let steps = ["map rom", "disassemble reset vector", "label main"];
627 let mut tip = None;
628 let mut ids = Vec::new();
629
630 for content in steps {
631 let note = Note::new(tip.as_ref(), content);
632 ids.push(note.id.to_string());
633 tip = Some(note.id);
634 }
635
636 assert_eq!(
637 ids,
638 [
639 "0000000000000G6MX6SW56W8JJ",
640 "00000000000016Q7FK68C75XDV",
641 "0000000000001PH81Q8ZKYJY1J",
642 ]
643 );
644 }
645
646 #[test]
647 fn encode_decode_roundtrip_values() {
648 for depth in [1u64, 2, 100, u64::MAX] {
649 for hash in [0u64, 1, 12345, u64::MAX] {
650 let value = ((depth as u128) << 64) | (hash as u128);
651 let encoded = encode(value);
652 let (decoded_depth, decoded_hash) = try_decode(&encoded).unwrap();
653 assert_eq!(decoded_depth, depth, "depth for {encoded}");
654 assert_eq!(decoded_hash, hash, "hash for {encoded}");
655 assert_eq!(
656 encode(((decoded_depth as u128) << 64) | (decoded_hash as u128)),
657 encoded,
658 "re-encode for {encoded}"
659 );
660 }
661 }
662 }
663
664 #[test]
665 fn roundtrip_base32_encoding() {
666 let id = NoteId::allocate(None, "hello");
667 assert_eq!(id.as_str().len(), NoteId::ENCODED_LEN);
668 let parsed = id.as_str().parse::<NoteId>().unwrap();
669 assert_eq!(parsed, id);
670 assert_eq!(parsed.depth(), id.depth());
671 assert_eq!(parsed.hash(), id.hash());
672 }
673
674 #[test]
675 fn deserialize_canonicalizes_input() {
676 let id = NoteId::allocate(None, "hello");
677 let trimmed = id.as_str().trim_start_matches('0');
678 let parsed = trimmed.parse::<NoteId>().unwrap();
679 assert_eq!(parsed, id);
680 }
681
682 #[test]
683 fn two_notes_at_same_address_are_both_retrievable() {
684 let mut db = NoteDb::default();
685 let range = AddressRange::from(0..4);
686 let human = db.create("human note on ISR");
687 let llm = db.create("llm note on ISR");
688 db.set_address(AddressSpace::Code, range, human.clone());
689 db.set_address(AddressSpace::Code, range, llm.clone());
690
691 let found = db.get_notes_inside(AddressSpace::Code, 0..4);
692 assert_eq!(found.len(), 2);
693 let ids: BTreeSet<_> = found.iter().map(|note| ¬e.id).collect();
694 assert!(ids.contains(&human.id));
695 assert!(ids.contains(&llm.id));
696 }
697
698 #[test]
699 fn note_db_shares_namespace_between_indexes() {
700 let mut db = NoteDb::default();
701 let note = db.create("global and local");
702 let id = note.id.clone();
703 db.global
704 .insert(NotePath::parse("project.vt420").unwrap(), id.clone());
705 db.address
706 .entry(AddressSpace::Code)
707 .or_default()
708 .insert(AddressRange::from(0..4), id.clone());
709
710 assert_eq!(db.get(&id).unwrap().content, "global and local");
711 assert_eq!(
712 db.get_by_path(&NotePath::parse("project.vt420").unwrap())
713 .unwrap()
714 .id,
715 id
716 );
717 assert_eq!(db.get_notes_inside(AddressSpace::Code, 0..4).len(), 1);
718
719 db.clear(&id);
720 assert!(db.notes.is_empty());
721 assert!(
722 db.get_by_path(&NotePath::parse("project.vt420").unwrap())
723 .is_none()
724 );
725 assert!(
726 db.get_notes_overlapping(AddressSpace::Code, 0..4)
727 .is_empty()
728 );
729 }
730}