1use std::{
36 collections::BTreeSet,
37 ffi::OsStr,
38 fmt,
39 os::unix::ffi::OsStrExt as _,
40 path::{Path, PathBuf},
41};
42
43use minicbor::{Decode, Decoder, Encode, Encoder, bytes::ByteArray, decode, encode};
44
45use crate::{
46 explanation::{BuildId, Verdict},
47 step::{ContentHash, path_bytes, path_list},
48};
49
50#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
52pub enum Family {
53 Meta,
55 Step,
57 Position,
59 Task,
61 Writer,
63 Order,
65}
66
67impl Family {
68 pub const ALL: [Self; 6] = [
70 Self::Meta,
71 Self::Step,
72 Self::Position,
73 Self::Task,
74 Self::Writer,
75 Self::Order,
76 ];
77
78 #[must_use]
80 pub const fn prefix(self) -> &'static [u8] {
81 match self {
82 Self::Meta => b"meta/",
83 Self::Step => b"step/",
84 Self::Position => b"position/",
85 Self::Task => b"task/",
86 Self::Writer => b"writer/",
87 Self::Order => b"order/",
88 }
89 }
90
91 #[must_use]
93 pub const fn name(self) -> &'static str {
94 match self {
95 Self::Meta => "database fact",
96 Self::Step => "step record",
97 Self::Position => "step position",
98 Self::Task => "task record",
99 Self::Writer => "last writer",
100 Self::Order => "learned order",
101 }
102 }
103}
104
105impl fmt::Display for Family {
106 fn fmt(
107 &self,
108 f: &mut fmt::Formatter<'_>,
109 ) -> fmt::Result {
110 f.write_str(self.name())
111 }
112}
113
114pub trait RecordKey: Sized {
116 fn encode_key(
118 &self,
119 out: &mut Vec<u8>,
120 );
121
122 fn decode_key(bytes: &[u8]) -> Option<Self>;
124}
125
126pub trait Record: Encode<()> + for<'b> Decode<'b, ()> {
128 type Key: RecordKey;
130
131 const FAMILY: Family;
133}
134
135#[must_use]
137pub fn database_key<R: Record>(key: &R::Key) -> Vec<u8> {
138 let mut out = R::FAMILY.prefix().to_vec();
139 key.encode_key(&mut out);
140 out
141}
142
143#[must_use]
147pub fn path_prefix(dir: &Path) -> Vec<u8> {
148 let mut out = dir.as_os_str().as_bytes().to_vec();
149 if out.last() != Some(&b'/') {
150 out.push(b'/');
151 }
152 out
153}
154
155#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
157pub struct StepKey(pub [u8; 32]);
158
159impl RecordKey for StepKey {
160 fn encode_key(
161 &self,
162 out: &mut Vec<u8>,
163 ) {
164 out.extend_from_slice(&self.0);
165 }
166
167 fn decode_key(bytes: &[u8]) -> Option<Self> {
168 bytes.try_into().ok().map(Self)
169 }
170}
171
172impl<C> Encode<C> for StepKey {
173 fn encode<W: encode::Write>(
174 &self,
175 e: &mut Encoder<W>,
176 _ctx: &mut C,
177 ) -> Result<(), encode::Error<W::Error>> {
178 e.bytes(&self.0)?.ok()
179 }
180}
181
182impl<'b, C> Decode<'b, C> for StepKey {
183 fn decode(
184 d: &mut Decoder<'b>,
185 ctx: &mut C,
186 ) -> Result<Self, decode::Error> {
187 ByteArray::<32>::decode(d, ctx).map(|bytes| Self(bytes.into()))
188 }
189}
190
191#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
194pub struct TaskId {
195 pub file: PathBuf,
197 pub index: u32,
199}
200
201impl TaskId {
202 #[must_use]
204 pub fn key_prefix(&self) -> Vec<u8> {
205 let mut out = Vec::new();
206 self.encode_key(&mut out);
207 out
208 }
209}
210
211impl RecordKey for TaskId {
212 fn encode_key(
213 &self,
214 out: &mut Vec<u8>,
215 ) {
216 out.extend_from_slice(self.file.as_os_str().as_bytes());
217 out.push(0);
218 out.extend_from_slice(&self.index.to_be_bytes());
219 }
220
221 fn decode_key(bytes: &[u8]) -> Option<Self> {
222 let (path, index) = bytes.split_last_chunk::<4>()?;
223 let (separator, path) = path.split_last()?;
224 if *separator != 0 || path.contains(&0) {
225 return None;
226 }
227 Some(Self {
228 file: PathBuf::from(OsStr::from_bytes(path)),
229 index: u32::from_be_bytes(*index),
230 })
231 }
232}
233
234impl<C> Encode<C> for TaskId {
235 fn encode<W: encode::Write>(
236 &self,
237 e: &mut Encoder<W>,
238 _ctx: &mut C,
239 ) -> Result<(), encode::Error<W::Error>> {
240 e.array(2)?
241 .bytes(self.file.as_os_str().as_bytes())?
242 .u32(self.index)?
243 .ok()
244 }
245}
246
247impl<'b, C> Decode<'b, C> for TaskId {
248 fn decode(
249 d: &mut Decoder<'b>,
250 _ctx: &mut C,
251 ) -> Result<Self, decode::Error> {
252 if d.array()? != Some(2) {
253 return Err(decode::Error::message("a task ID is an array of two items"));
254 }
255 let file = PathBuf::from(OsStr::from_bytes(d.bytes()?));
256 let index = d.u32()?;
257 Ok(Self { file, index })
258 }
259}
260
261#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
263pub struct PositionKey {
264 pub task: TaskId,
266 pub position: u32,
268}
269
270impl RecordKey for PositionKey {
271 fn encode_key(
272 &self,
273 out: &mut Vec<u8>,
274 ) {
275 self.task.encode_key(out);
276 out.extend_from_slice(&self.position.to_be_bytes());
277 }
278
279 fn decode_key(bytes: &[u8]) -> Option<Self> {
280 let (task, position) = bytes.split_last_chunk::<4>()?;
281 Some(Self {
282 task: TaskId::decode_key(task)?,
283 position: u32::from_be_bytes(*position),
284 })
285 }
286}
287
288#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
290pub struct PathKey(pub PathBuf);
291
292impl RecordKey for PathKey {
293 fn encode_key(
294 &self,
295 out: &mut Vec<u8>,
296 ) {
297 out.extend_from_slice(self.0.as_os_str().as_bytes());
298 }
299
300 fn decode_key(bytes: &[u8]) -> Option<Self> {
301 Some(Self(PathBuf::from(OsStr::from_bytes(bytes))))
302 }
303}
304
305#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
308pub struct SchemaKey;
309
310impl SchemaKey {
311 const BYTES: &'static [u8] = b"schema-version";
313}
314
315impl RecordKey for SchemaKey {
316 fn encode_key(
317 &self,
318 out: &mut Vec<u8>,
319 ) {
320 out.extend_from_slice(Self::BYTES);
321 }
322
323 fn decode_key(bytes: &[u8]) -> Option<Self> {
324 (bytes == Self::BYTES).then_some(Self)
325 }
326}
327
328#[derive(Debug, Clone, Copy, PartialEq, Eq, Encode, Decode)]
330pub struct SchemaVersion {
331 #[n(0)]
333 pub version: u32,
334}
335
336impl Record for SchemaVersion {
337 type Key = SchemaKey;
338
339 const FAMILY: Family = Family::Meta;
340}
341
342#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
346pub struct StepPosition {
347 #[n(0)]
349 pub step: StepKey,
350 #[n(1)]
352 pub build: BuildId,
353 #[n(2)]
356 pub verdict: Verdict,
357 #[cbor(n(3), with = "path_list")]
361 pub carried: Vec<PathBuf>,
362}
363
364impl Record for StepPosition {
365 type Key = PositionKey;
366
367 const FAMILY: Family = Family::Position;
368}
369
370#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
372pub struct ModuleHash {
373 #[cbor(n(0), with = "path_bytes")]
375 pub path: PathBuf,
376 #[n(1)]
378 pub hash: ContentHash,
379}
380
381#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
384pub struct TaskRecord {
385 #[cbor(n(0), with = "minicbor::bytes")]
387 pub program_hash: [u8; 32],
388 #[n(1)]
390 pub succeeded: bool,
391 #[n(2)]
393 pub build: BuildId,
394 #[n(3)]
396 pub steps: u32,
397 #[n(4)]
399 pub line: u32,
400 #[n(5)]
402 pub heading: Option<String>,
403 #[n(6)]
405 pub targets: Vec<String>,
406 #[n(7)]
408 pub block: ContentHash,
409 #[n(8)]
411 pub modules: Vec<ModuleHash>,
412}
413
414impl Record for TaskRecord {
415 type Key = TaskId;
416
417 const FAMILY: Family = Family::Task;
418}
419
420#[derive(Debug, Clone, Copy, PartialEq, Eq, Encode, Decode)]
422pub enum WrittenBy {
423 #[n(0)]
425 Step {
426 #[n(0)]
428 step: StepKey,
429 #[n(1)]
431 position: u32,
432 },
433 #[n(1)]
435 Program,
436}
437
438#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
440pub struct LastWriter {
441 #[n(0)]
443 pub task: TaskId,
444 #[n(1)]
446 pub by: WrittenBy,
447 #[n(2)]
449 pub build: BuildId,
450 #[n(3)]
455 pub written_at_nanos: u64,
456}
457
458impl Record for LastWriter {
459 type Key = PathKey;
460
461 const FAMILY: Family = Family::Writer;
462}
463
464#[derive(Debug, Clone, PartialEq, Eq, Encode, Decode)]
466pub struct LearnedOrder {
467 #[n(0)]
469 pub producers: BTreeSet<TaskId>,
470}
471
472impl Record for LearnedOrder {
473 type Key = TaskId;
474
475 const FAMILY: Family = Family::Order;
476}
477
478#[cfg(test)]
480#[allow(
481 clippy::disallowed_macros,
482 clippy::disallowed_methods,
483 reason = "test code: the tests assert and lock"
484)]
485mod tests {
486 use super::*;
487
488 fn task(
490 dir: &str,
491 index: u32,
492 ) -> TaskId {
493 TaskId {
494 file: PathBuf::from(format!("/work/{dir}/kizz.md")),
495 index,
496 }
497 }
498
499 #[test]
500 fn no_family_prefix_is_a_prefix_of_another() {
501 for one in Family::ALL {
502 for other in Family::ALL {
503 if one != other {
504 assert!(
505 !other.prefix().starts_with(one.prefix()),
506 "{one} and {other}"
507 );
508 }
509 }
510 }
511 }
512
513 #[test]
514 fn keys_round_trip() {
515 let step = StepKey([7; 32]);
516 let mut bytes = Vec::new();
517 step.encode_key(&mut bytes);
518 assert_eq!(StepKey::decode_key(&bytes), Some(step));
519 assert_eq!(StepKey::decode_key(&bytes[1..]), None);
520
521 let id = task("a b", 3);
522 assert_eq!(TaskId::decode_key(&id.key_prefix()), Some(id.clone()));
523 assert_eq!(TaskId::decode_key(b"/x"), None);
524
525 let position = PositionKey {
526 task: id,
527 position: 9,
528 };
529 let mut bytes = Vec::new();
530 position.encode_key(&mut bytes);
531 assert_eq!(PositionKey::decode_key(&bytes), Some(position));
532
533 let path = PathKey(PathBuf::from("/work/out.bin"));
534 let mut bytes = Vec::new();
535 path.encode_key(&mut bytes);
536 assert_eq!(PathKey::decode_key(&bytes), Some(path));
537
538 let mut bytes = Vec::new();
539 SchemaKey.encode_key(&mut bytes);
540 assert_eq!(SchemaKey::decode_key(&bytes), Some(SchemaKey));
541 assert_eq!(SchemaKey::decode_key(b"other"), None);
542 }
543
544 #[test]
545 fn database_keys_start_with_the_family_prefix() {
546 assert_eq!(
547 database_key::<SchemaVersion>(&SchemaKey),
548 b"meta/schema-version"
549 );
550 let key = database_key::<TaskRecord>(&task("a", 1));
551 assert_eq!(key, b"task//work/a/kizz.md\0\0\0\0\x01");
552 }
553
554 #[test]
555 fn task_keys_sort_by_path_then_index_then_position() {
556 let key = |dir: &str, index: u32, position: u32| {
557 database_key::<StepPosition>(&PositionKey {
558 task: task(dir, index),
559 position,
560 })
561 };
562 let mut keys = vec![
563 key("b", 0, 0),
564 key("a", 1, 0),
565 key("a", 0, 256),
566 key("a", 0, 1),
567 key("a", 256, 0),
568 ];
569 keys.sort();
570 assert_eq!(keys, vec![
571 key("a", 0, 1),
572 key("a", 0, 256),
573 key("a", 1, 0),
574 key("a", 256, 0),
575 key("b", 0, 0),
576 ]);
577 }
578
579 #[test]
580 fn path_prefix_selects_only_paths_under_the_directory() {
581 let prefix = path_prefix(Path::new("/work/a"));
582 assert_eq!(prefix, b"/work/a/");
583 assert_eq!(path_prefix(Path::new("/work/a/")), b"/work/a/");
584 assert_eq!(path_prefix(Path::new("/")), b"/");
585 assert!(task("a", 0).key_prefix().starts_with(&prefix));
586 assert!(!task("ab", 0).key_prefix().starts_with(&prefix));
587 }
588
589 fn encode_stably<R: Record + PartialEq + fmt::Debug>(record: &R) -> Vec<u8> {
592 let first = minicbor::to_vec(record).unwrap();
593 let second = minicbor::to_vec(record).unwrap();
594 assert_eq!(first, second);
595 assert_eq!(&minicbor::decode::<R>(&first).unwrap(), record);
596 first
597 }
598
599 #[test]
600 fn records_encode_deterministically_and_round_trip() {
601 let version = encode_stably(&SchemaVersion { version: 1 });
602 assert_eq!(version, [0x81, 0x01]);
604
605 let position = encode_stably(&StepPosition {
606 step: StepKey([1; 32]),
607 build: BuildId(5),
608 verdict: Verdict::Cached,
609 carried: vec![PathBuf::from("/work/a/out")],
610 });
611 assert_eq!(position.get(..3), Some(&[0x84, 0x58, 0x20][..]));
613
614 encode_stably(&TaskRecord {
615 program_hash: [2; 32],
616 succeeded: true,
617 build: BuildId(5),
618 steps: 2,
619 line: 3,
620 heading: Some("Build".to_owned()),
621 targets: vec!["ci".to_owned()],
622 block: ContentHash([4; 32]),
623 modules: vec![ModuleHash {
624 path: PathBuf::from("/work/lib.star"),
625 hash: ContentHash([5; 32]),
626 }],
627 });
628 let step_writer = encode_stably(&LastWriter {
629 task: task("a", 0),
630 by: WrittenBy::Step {
631 step: StepKey([3; 32]),
632 position: 1,
633 },
634 build: BuildId(5),
635 written_at_nanos: 6,
636 });
637 let program_writer = encode_stably(&LastWriter {
638 task: task("a", 0),
639 by: WrittenBy::Program,
640 build: BuildId(5),
641 written_at_nanos: 6,
642 });
643 assert_eq!(step_writer.first(), Some(&0x84));
646 assert_eq!(program_writer.first(), Some(&0x84));
647 assert_ne!(step_writer, program_writer);
648 assert_ne!(
649 minicbor::decode::<LastWriter>(&step_writer).unwrap().by,
650 WrittenBy::Program
651 );
652 assert_eq!(
653 minicbor::decode::<LastWriter>(&program_writer).unwrap().by,
654 WrittenBy::Program
655 );
656 }
657
658 #[test]
659 fn sets_encode_sorted_whatever_the_insertion_order() {
660 let forward = LearnedOrder {
661 producers: [task("a", 0), task("b", 0), task("c", 1)].into(),
662 };
663 let backward = LearnedOrder {
664 producers: [task("c", 1), task("b", 0), task("a", 0)].into(),
665 };
666 assert_eq!(encode_stably(&forward), encode_stably(&backward));
667 }
668}