alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use std::collections::BTreeMap;
2
3use gix::bstr::{BStr, ByteSlice as _};
4use gix::date::Time;
5use knot_git::Repo;
6use knot_runtime::{Signature, Signer};
7use knot_types::{ActorId, ChangeId, CobId, Oid, RefName, TypeName, UnixSeconds};
8
9use crate::change::{Change, CobHome, Payload};
10use crate::error::CobError;
11use crate::graph::ChangeGraph;
12use crate::object::HistoryModel;
13
14const COBS_PREFIX: &str = "refs/cobs/";
15const CHECKPOINTS_PREFIX: &str = "refs/cob-checkpoints/";
16const TYPE_HEADER: &str = "cob-type";
17const SIG_HEADER: &str = "cob-sig";
18const AUTHOR_HEADER: &str = "cob-author";
19const PAYLOAD_BLOB: &str = "payload";
20pub(crate) const MAX_GRAPH_CHANGES: usize = 100_000;
21const REBUILD_CHANGE_BYTES: u64 = 2560;
22const REBUILD_FOLD_DIVISOR: u64 = 4;
23// two bazillion
24const REBUILD_UNMEASURED_CHANGES: usize = 2_000_000;
25
26pub(crate) fn rebuild_change_limit_for(available: Option<knot_resource::AvailableBytes>) -> usize {
27 let derived = match available {
28 Some(available) => {
29 usize::try_from(available.get() / REBUILD_FOLD_DIVISOR / REBUILD_CHANGE_BYTES)
30 .unwrap_or(usize::MAX)
31 }
32 None => REBUILD_UNMEASURED_CHANGES,
33 };
34 derived.max(MAX_GRAPH_CHANGES)
35}
36
37pub(crate) fn rebuild_graph_limit() -> usize {
38 rebuild_change_limit_for(knot_resource::available_bytes())
39}
40
41pub(crate) fn cob_ref_name(type_name: &TypeName, object: CobId) -> Result<RefName, CobError> {
42 let raw = format!(
43 "{COBS_PREFIX}{}/{}",
44 type_name.as_str(),
45 object.oid().to_hex()
46 );
47 RefName::new(raw.as_str()).map_err(|_| CobError::RefName(raw))
48}
49
50pub(crate) fn checkpoint_ref_name(
51 type_name: &TypeName,
52 object: CobId,
53) -> Result<RefName, CobError> {
54 let raw = format!(
55 "{CHECKPOINTS_PREFIX}{}/{}",
56 type_name.as_str(),
57 object.oid().to_hex()
58 );
59 RefName::new(raw.as_str()).map_err(|_| CobError::RefName(raw))
60}
61
62pub fn parse_cob_ref(refname: &str) -> Option<(TypeName, CobId)> {
63 let (nsid, oid) = refname.strip_prefix(COBS_PREFIX)?.rsplit_once('/')?;
64 let type_name = TypeName::new(nsid).ok()?;
65 let object = Oid::from_hex(oid).ok().map(CobId::new)?;
66 Some((type_name, object))
67}
68
69pub(crate) fn resolve_tip(
70 repo: &Repo,
71 type_name: &TypeName,
72 object: CobId,
73) -> Result<Option<Oid>, CobError> {
74 let name = cob_ref_name(type_name, object)?;
75 Ok(repo.find_ref(&name)?)
76}
77
78pub(crate) fn list_objects(repo: &Repo, type_name: &TypeName) -> Result<Vec<CobId>, CobError> {
79 let prefix = format!("{COBS_PREFIX}{}/", type_name.as_str());
80 Ok(repo
81 .references()?
82 .into_iter()
83 .filter_map(|record| {
84 let rest = record.name.as_str().strip_prefix(&prefix)?;
85 Oid::from_hex(rest).ok().map(CobId::new)
86 })
87 .collect())
88}
89
90#[allow(clippy::too_many_arguments)]
91pub(crate) fn write_change(
92 home: &CobHome,
93 repo: &Repo,
94 type_name: &TypeName,
95 payload: &[u8],
96 parents: &[ChangeId],
97 object: Option<CobId>,
98 signer: &dyn Signer,
99 timestamp: UnixSeconds,
100) -> Result<ChangeId, CobError> {
101 let git = repo.git();
102 let payload_oid = git
103 .write_blob(payload)
104 .map_err(|error| CobError::Write(error.to_string()))?
105 .detach();
106 let revision = git
107 .write_object(build_tree(payload_oid))
108 .map_err(|error| CobError::Write(error.to_string()))?
109 .detach();
110 let author = ActorId::from_secp256k1(signer.public_key().as_bytes());
111 let revision_oid = Oid::from(revision);
112 let binding = crate::change::object_binding(parents, object);
113 let signing = crate::change::signing_bytes(
114 home,
115 revision_oid,
116 parents,
117 type_name,
118 &author,
119 timestamp,
120 binding,
121 );
122 let signature = signer.sign(&signing);
123 if !crate::change::verify_signature(
124 home,
125 revision_oid,
126 parents,
127 type_name,
128 &author,
129 timestamp,
130 object,
131 signature.as_bytes(),
132 ) {
133 return Err(CobError::SelfCheck(type_name.clone()));
134 }
135 let commit = gix::objs::Commit {
136 tree: revision,
137 parents: parents
138 .iter()
139 .map(|parent| parent.oid().object_id())
140 .collect(),
141 author: knot_identity(timestamp),
142 committer: knot_identity(timestamp),
143 encoding: None,
144 message: Vec::new().into(),
145 extra_headers: vec![
146 (TYPE_HEADER.into(), type_name.as_str().into()),
147 (AUTHOR_HEADER.into(), author.as_str().into()),
148 (
149 SIG_HEADER.into(),
150 knot_types::lowercase_hex(signature.as_bytes()).into(),
151 ),
152 ],
153 };
154 let id = git
155 .write_object(commit)
156 .map_err(|error| CobError::Write(error.to_string()))?
157 .detach();
158 Ok(ChangeId::new(Oid::from(id)))
159}
160
161pub(crate) fn load_graph(
162 repo: &Repo,
163 type_name: &TypeName,
164 object: CobId,
165 history: HistoryModel,
166 limit: usize,
167) -> Result<(ChangeGraph, ChangeId), CobError> {
168 let tip = resolve_tip(repo, type_name, object)?.ok_or(CobError::NoSuchObject(object))?;
169 let changes = collect(repo, ChangeId::new(tip), object, limit, None)?;
170 check_full_shape(&changes, object, history)?;
171 Ok((ChangeGraph::new(object, changes), ChangeId::new(tip)))
172}
173
174pub(crate) fn check_full_shape(
175 changes: &BTreeMap<ChangeId, Change>,
176 object: CobId,
177 history: HistoryModel,
178) -> Result<(), CobError> {
179 let root_id = ChangeId::new(object.oid());
180 let root = changes.get(&root_id).ok_or(CobError::DetachedTip(object))?;
181 if !root.parents.is_empty() {
182 return Err(CobError::RootNotGenesis(object));
183 }
184 if let Some(stray) = changes
185 .values()
186 .find(|change| change.id != root_id && change.parents.is_empty())
187 {
188 return Err(CobError::MultipleRoots {
189 object,
190 stray: stray.id,
191 });
192 }
193 check_no_forbidden_merge(changes, object, history)
194}
195
196pub(crate) fn check_delta_shape(
197 changes: &BTreeMap<ChangeId, Change>,
198 object: CobId,
199 since: ChangeId,
200 history: HistoryModel,
201) -> Result<(), CobError> {
202 check_no_forbidden_merge(changes, object, history)?;
203 let descends = changes
204 .values()
205 .any(|change| change.parents.contains(&since));
206 if !changes.is_empty() && !descends {
207 return Err(CobError::DivergedTip { object, since });
208 }
209 Ok(())
210}
211
212fn check_no_forbidden_merge(
213 changes: &BTreeMap<ChangeId, Change>,
214 object: CobId,
215 history: HistoryModel,
216) -> Result<(), CobError> {
217 let forbidden_merge = (history == HistoryModel::Linear)
218 .then(|| changes.values().find(|change| change.parents.len() > 1))
219 .flatten();
220 match forbidden_merge {
221 Some(merge) => Err(CobError::ForkedHistory {
222 object,
223 change: merge.id,
224 }),
225 None => Ok(()),
226 }
227}
228
229pub(crate) fn collect(
230 repo: &Repo,
231 tip: ChangeId,
232 object: CobId,
233 limit: usize,
234 stop: Option<ChangeId>,
235) -> Result<BTreeMap<ChangeId, Change>, CobError> {
236 let mut frontier = vec![tip];
237 let mut seen: BTreeMap<ChangeId, Change> = BTreeMap::new();
238 let mut overflowed = false;
239 let walk = {
240 let mut step = || -> Option<Result<(), CobError>> {
241 let head = frontier.pop()?;
242 if Some(head) == stop || seen.contains_key(&head) {
243 return Some(Ok(()));
244 }
245 if seen.len() >= limit {
246 overflowed = true;
247 return None;
248 }
249 match read_change(repo, head) {
250 Ok(change) => {
251 frontier.extend(change.parents.iter().copied());
252 seen.insert(head, change);
253 Some(Ok(()))
254 }
255 Err(error) => Some(Err(error)),
256 }
257 };
258 std::iter::from_fn(&mut step).try_for_each(|outcome| outcome)
259 };
260 walk?;
261 if overflowed {
262 return Err(CobError::HistoryTooLong(object));
263 }
264 Ok(seen)
265}
266
267pub(crate) fn read_change(repo: &Repo, id: ChangeId) -> Result<Change, CobError> {
268 let oid = id.oid();
269 let malformed = |reason: String| CobError::MalformedChange { oid, reason };
270 #[cfg(feature = "instrument")]
271 crate::instrument::record_read();
272 let data = repo
273 .git()
274 .find_object(oid.object_id())
275 .map_err(|error| malformed(error.to_string()))?
276 .detach()
277 .data;
278 let commit = gix::objs::CommitRef::from_bytes(&data, repo.git().object_hash())
279 .map_err(|error| malformed(error.to_string()))?;
280 let revision = Oid::from(commit.tree());
281 let parents = commit
282 .parents()
283 .map(|parent| ChangeId::new(Oid::from(parent)))
284 .collect();
285 let timestamp = UnixSeconds::new(
286 commit
287 .time()
288 .map_err(|error| malformed(error.to_string()))?
289 .seconds,
290 );
291 let type_raw = commit
292 .extra_headers()
293 .find(TYPE_HEADER)
294 .ok_or_else(|| malformed("missing cob-type header".into()))?;
295 let type_name = TypeName::new(
296 type_raw
297 .to_str()
298 .map_err(|error| malformed(error.to_string()))?,
299 )
300 .map_err(|error| malformed(error.to_string()))?;
301 let author_raw = commit
302 .extra_headers()
303 .find(AUTHOR_HEADER)
304 .ok_or_else(|| malformed("missing cob-author header".into()))?;
305 let author = ActorId::new(
306 author_raw
307 .to_str()
308 .map_err(|error| malformed(error.to_string()))?,
309 )
310 .map_err(|error| malformed(error.to_string()))?;
311 let signature = commit
312 .extra_headers()
313 .find(SIG_HEADER)
314 .ok_or_else(|| malformed("missing cob-sig header".into()))
315 .and_then(|raw| {
316 knot_types::decode_hex(raw).ok_or_else(|| malformed("cob-sig isn't valid hex".into()))
317 })?;
318 let payload = read_payload(repo, revision)?;
319 Ok(Change {
320 id,
321 revision,
322 parents,
323 type_name,
324 author,
325 signature: Signature::from_bytes(signature),
326 payload: Payload::new(payload),
327 timestamp,
328 })
329}
330
331fn read_payload(repo: &Repo, revision: Oid) -> Result<Vec<u8>, CobError> {
332 let malformed = |reason: String| CobError::MalformedChange {
333 oid: revision,
334 reason,
335 };
336 #[cfg(feature = "instrument")]
337 crate::instrument::record_read();
338 let data = repo
339 .git()
340 .find_object(revision.object_id())
341 .map_err(|error| malformed(error.to_string()))?
342 .detach()
343 .data;
344 let tree = gix::objs::TreeRef::from_bytes(&data, repo.git().object_hash())
345 .map_err(|error| malformed(error.to_string()))?;
346 let payload_oid =
347 entry_oid(&tree, PAYLOAD_BLOB).ok_or_else(|| malformed("missing payload blob".into()))?;
348 let payload = repo
349 .git()
350 .find_object(payload_oid)
351 .map_err(|error| malformed(error.to_string()))?
352 .detach()
353 .data;
354 Ok(payload)
355}
356
357fn entry_oid(tree: &gix::objs::TreeRef<'_>, name: &str) -> Option<gix::ObjectId> {
358 tree.entries
359 .iter()
360 .find(|entry| entry.filename == BStr::new(name))
361 .map(|entry| entry.oid.to_owned())
362}
363
364fn build_tree(payload_oid: gix::ObjectId) -> gix::objs::Tree {
365 gix::objs::Tree {
366 entries: vec![blob_entry(PAYLOAD_BLOB, payload_oid)],
367 }
368}
369
370fn blob_entry(name: &str, oid: gix::ObjectId) -> gix::objs::tree::Entry {
371 gix::objs::tree::Entry {
372 mode: gix::objs::tree::EntryKind::Blob.into(),
373 filename: name.into(),
374 oid,
375 }
376}
377
378fn knot_identity(time: UnixSeconds) -> gix::actor::Signature {
379 gix::actor::Signature {
380 name: "knot".into(),
381 email: "noreply@knot".into(),
382 time: Time::new(time.get(), 0),
383 }
384}