pijul_core/pristine/
mod.rs

1use crate::change::*;
2use crate::small_string::*;
3use crate::{HashMap, HashSet};
4pub use ::sanakirja::L64;
5use parking_lot::{Mutex, RwLock};
6use std::io::Write;
7use std::sync::{Arc, LazyLock};
8
9mod change_id;
10pub use change_id::*;
11mod vertex;
12pub use vertex::*;
13mod edge;
14pub use edge::*;
15mod hash;
16pub use hash::*;
17mod inode;
18pub use inode::*;
19mod inode_metadata;
20pub use inode_metadata::*;
21mod path_id;
22pub use path_id::*;
23mod merkle;
24pub use merkle::*;
25
26#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
27#[repr(C)]
28pub struct SerializedRemote {
29    remote: L64,
30    rev: L64,
31    states: L64,
32    id_rev: L64,
33    tags: L64,
34    path: SmallStr,
35}
36
37#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)]
38#[repr(C)]
39pub struct SerializedChannel {
40    graph: L64,
41    changes: L64,
42    revchanges: L64,
43    states: L64,
44    tags: L64,
45    apply_counter: L64,
46    last_modified: L64,
47    id: RemoteId,
48}
49
50#[derive(Debug, Clone, Copy, PartialOrd, Ord, PartialEq, Eq)]
51#[repr(C)]
52pub struct Pair<A, B> {
53    pub a: A,
54    pub b: B,
55}
56
57pub(crate) static BASE32: LazyLock<data_encoding::Encoding> = LazyLock::new(|| {
58    let mut spec = data_encoding::Specification::new();
59    spec.symbols.push_str("ABCDEFGHIJKLMNOPQRSTUVWXYZ234567");
60    spec.translate.from = "abcdefghijklmnopqrstuvwxyz".to_string();
61    spec.translate.to = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".to_string();
62    spec.encoding().unwrap()
63});
64
65pub trait Base32: Sized {
66    fn to_base32(&self) -> String;
67    fn from_base32(b: &[u8]) -> Option<Self>;
68}
69
70pub mod sanakirja;
71
72pub type ApplyTimestamp = u64;
73
74pub struct ChannelRef<T: ChannelTxnT> {
75    pub(crate) r: Arc<RwLock<T::Channel>>,
76}
77
78impl<T: ChannelTxnT> ChannelRef<T> {
79    pub fn new(t: T::Channel) -> Self {
80        ChannelRef {
81            r: Arc::new(RwLock::new(t)),
82        }
83    }
84}
85
86pub struct ArcTxn<T>(pub Arc<RwLock<T>>);
87
88impl<T> ArcTxn<T> {
89    pub fn new(t: T) -> Self {
90        ArcTxn(Arc::new(RwLock::new(t)))
91    }
92}
93
94impl<T> Clone for ArcTxn<T> {
95    fn clone(&self) -> Self {
96        ArcTxn(self.0.clone())
97    }
98}
99
100impl<T: MutTxnT> ArcTxn<T> {
101    pub fn commit(self) -> Result<(), T::GraphError> {
102        match Arc::try_unwrap(self.0) {
103            Ok(txn) => txn.into_inner().commit(),
104            _ => {
105                panic!("Tried to commit an ArcTxn without dropping its references")
106            }
107        }
108    }
109}
110
111impl<T> std::ops::Deref for ArcTxn<T> {
112    type Target = RwLock<T>;
113    fn deref(&self) -> &Self::Target {
114        &self.0
115    }
116}
117
118#[derive(Debug, Error)]
119#[error("Mutex poison error")]
120pub struct PoisonError {}
121
122impl<T: ChannelTxnT> ChannelRef<T> {
123    pub fn read<'a>(&'a self) -> parking_lot::RwLockReadGuard<'a, T::Channel> {
124        self.r.read()
125    }
126    pub fn write<'a>(&'a self) -> parking_lot::RwLockWriteGuard<'a, T::Channel> {
127        self.r.write()
128    }
129}
130
131impl<T: ChannelTxnT> Clone for ChannelRef<T> {
132    fn clone(&self) -> Self {
133        ChannelRef { r: self.r.clone() }
134    }
135}
136
137impl<T: TxnT> RemoteRef<T> {
138    pub fn id(&self) -> &RemoteId {
139        &self.id
140    }
141
142    pub fn lock<'a>(&'a self) -> parking_lot::MutexGuard<'a, Remote<T>> {
143        self.db.lock()
144    }
145
146    pub fn id_revision(&self) -> u64 {
147        self.lock().id_rev.into()
148    }
149
150    pub fn set_id_revision(&self, rev: u64) {
151        self.lock().id_rev = rev.into()
152    }
153}
154
155pub struct Remote<T: TxnT> {
156    pub remote: T::Remote,
157    pub rev: T::Revremote,
158    pub states: T::Remotestates,
159    pub id_rev: L64,
160    pub tags: T::Tags,
161    pub path: SmallString,
162}
163
164pub struct RemoteRef<T: TxnT> {
165    db: Arc<Mutex<Remote<T>>>,
166    id: RemoteId,
167}
168
169impl<T: TxnT> Clone for RemoteRef<T> {
170    fn clone(&self) -> Self {
171        RemoteRef {
172            db: self.db.clone(),
173            id: self.id,
174        }
175    }
176}
177
178#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
179pub struct RemoteId(pub(crate) [u8; 16]);
180
181impl RemoteId {
182    pub fn nil() -> Self {
183        RemoteId([0; 16])
184    }
185    pub fn from_bytes(b: &[u8]) -> Option<Self> {
186        Some(RemoteId(b.try_into().ok()?))
187    }
188    pub fn as_bytes(&self) -> &[u8; 16] {
189        &self.0
190    }
191
192    pub fn from_base32(b: &[u8]) -> Option<Self> {
193        let mut bb = RemoteId([0; 16]);
194        if b.len() != BASE32.encode_len(16) {
195            return None;
196        }
197        if BASE32.decode_mut(b, &mut bb.0).is_ok() {
198            Some(bb)
199        } else {
200            None
201        }
202    }
203}
204
205impl std::fmt::Display for RemoteId {
206    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
207        write!(fmt, "{}", BASE32.encode(&self.0))
208    }
209}
210
211impl std::fmt::Debug for RemoteId {
212    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
213        write!(fmt, "{}", BASE32.encode(&self.0))
214    }
215}
216
217#[derive(Debug, Error)]
218pub enum HashPrefixError<T: std::error::Error + 'static> {
219    #[error("Failed to parse hash prefix: {0}")]
220    Parse(String),
221    #[error("Ambiguous hash prefix: {0}")]
222    Ambiguous(String),
223    #[error("Change not found: {0}")]
224    NotFound(String),
225    #[error(transparent)]
226    Txn(T),
227}
228
229#[derive(Debug, Error)]
230pub enum ForkError<T: std::error::Error + 'static> {
231    #[error("Channel name already exists: {0}")]
232    ChannelNameExists(String),
233    #[error(transparent)]
234    Txn(T),
235}
236
237#[derive(Debug, Error)]
238#[error(transparent)]
239pub struct TxnErr<E: std::error::Error + std::fmt::Debug + 'static>(pub E);
240
241#[derive(Debug, Error)]
242pub enum GetExternalError<E: std::error::Error + 'static> {
243    #[error("ChangeId not found in external table")]
244    NotFound,
245    #[error(transparent)]
246    Txn(E),
247}
248
249pub trait ResultOptionalExt<T, E: std::error::Error + std::fmt::Debug + 'static>: Sized {
250    fn optional(self) -> Result<Option<T>, TxnErr<E>>;
251}
252
253impl<T, E: std::error::Error + std::fmt::Debug + 'static> ResultOptionalExt<T, E>
254    for Result<T, GetExternalError<E>>
255{
256    fn optional(self) -> Result<Option<T>, TxnErr<E>> {
257        match self {
258            Ok(v) => Ok(Some(v)),
259            Err(GetExternalError::NotFound) => Ok(None),
260            Err(GetExternalError::Txn(e)) => Err(TxnErr(e)),
261        }
262    }
263}
264
265pub trait GraphTxnT: Sized {
266    type GraphError: std::error::Error + std::fmt::Debug + Send + Sync + 'static;
267    table!(graph);
268    get!(graph, Vertex<ChangeId>, SerializedEdge, GraphError);
269    /// Returns the external hash of an internal change identifier, if
270    /// the change is known.
271    fn get_external(
272        &self,
273        p: &ChangeId,
274    ) -> Result<&SerializedHash, GetExternalError<Self::GraphError>>;
275
276    /// Returns the internal change identifier of change with external
277    /// hash `hash`, if the change is known.
278    fn get_internal(
279        &self,
280        p: &SerializedHash,
281    ) -> Result<Option<&ChangeId>, TxnErr<Self::GraphError>>;
282
283    type Adj;
284    fn init_adj(
285        &self,
286        g: &Self::Graph,
287        v: Vertex<ChangeId>,
288        dest: Position<ChangeId>,
289        min: EdgeFlags,
290        max: EdgeFlags,
291    ) -> Result<Self::Adj, TxnErr<Self::GraphError>>;
292    fn next_adj<'a>(
293        &'a self,
294        g: &Self::Graph,
295        a: &mut Self::Adj,
296    ) -> Option<Result<&'a SerializedEdge, TxnErr<Self::GraphError>>>;
297
298    fn find_block<'a>(
299        &'a self,
300        graph: &Self::Graph,
301        p: Position<ChangeId>,
302    ) -> Result<&'a Vertex<ChangeId>, BlockError<Self::GraphError>>;
303
304    fn find_block_end<'a>(
305        &'a self,
306        graph: &Self::Graph,
307        p: Position<ChangeId>,
308    ) -> Result<&'a Vertex<ChangeId>, BlockError<Self::GraphError>>;
309}
310
311#[allow(clippy::type_complexity)]
312pub trait ChannelTxnT: GraphTxnT {
313    type Channel: Sync + Send;
314
315    fn name<'a>(&self, channel: &'a Self::Channel) -> &'a str;
316    fn id<'a>(&self, c: &'a Self::Channel) -> Option<&'a RemoteId>;
317    fn graph<'a>(&self, channel: &'a Self::Channel) -> &'a Self::Graph;
318    fn apply_counter(&self, channel: &Self::Channel) -> u64;
319    fn last_modified(&self, channel: &Self::Channel) -> u64;
320    fn changes<'a>(&self, channel: &'a Self::Channel) -> &'a Self::Changeset;
321    fn rev_changes<'a>(&self, channel: &'a Self::Channel) -> &'a Self::RevChangeset;
322    fn tags<'a>(&self, channel: &'a Self::Channel) -> &'a Self::Tags;
323    fn states<'a>(&self, channel: &'a Self::Channel) -> &'a Self::States;
324
325    type Changeset;
326    type RevChangeset;
327    fn get_changeset(
328        &self,
329        channel: &Self::Changeset,
330        c: &ChangeId,
331    ) -> Result<Option<&L64>, TxnErr<Self::GraphError>>;
332    fn get_revchangeset(
333        &self,
334        channel: &Self::RevChangeset,
335        c: &L64,
336    ) -> Result<Option<&Pair<ChangeId, SerializedMerkle>>, TxnErr<Self::GraphError>>;
337
338    type ChangesetCursor;
339
340    fn cursor_changeset<'txn>(
341        &'txn self,
342        channel: &Self::Changeset,
343        pos: Option<ChangeId>,
344    ) -> Result<
345        crate::pristine::Cursor<Self, &'txn Self, Self::ChangesetCursor, ChangeId, L64>,
346        TxnErr<Self::GraphError>,
347    >;
348    fn cursor_changeset_next(
349        &self,
350        cursor: &mut Self::ChangesetCursor,
351    ) -> Result<Option<(&ChangeId, &L64)>, TxnErr<Self::GraphError>>;
352
353    fn cursor_changeset_prev(
354        &self,
355        cursor: &mut Self::ChangesetCursor,
356    ) -> Result<Option<(&ChangeId, &L64)>, TxnErr<Self::GraphError>>;
357
358    type RevchangesetCursor;
359    fn cursor_revchangeset_ref<RT: std::ops::Deref<Target = Self>>(
360        txn: RT,
361        channel: &Self::RevChangeset,
362        pos: Option<L64>,
363    ) -> Result<
364        Cursor<Self, RT, Self::RevchangesetCursor, L64, Pair<ChangeId, SerializedMerkle>>,
365        TxnErr<Self::GraphError>,
366    >;
367    fn rev_cursor_revchangeset<'txn>(
368        &'txn self,
369        channel: &Self::RevChangeset,
370        pos: Option<L64>,
371    ) -> Result<
372        RevCursor<
373            Self,
374            &'txn Self,
375            Self::RevchangesetCursor,
376            L64,
377            Pair<ChangeId, SerializedMerkle>,
378        >,
379        TxnErr<Self::GraphError>,
380    >;
381    fn cursor_revchangeset_next(
382        &self,
383        cursor: &mut Self::RevchangesetCursor,
384    ) -> Result<Option<(&L64, &Pair<ChangeId, SerializedMerkle>)>, TxnErr<Self::GraphError>>;
385
386    fn cursor_revchangeset_prev(
387        &self,
388        cursor: &mut Self::RevchangesetCursor,
389    ) -> Result<Option<(&L64, &Pair<ChangeId, SerializedMerkle>)>, TxnErr<Self::GraphError>>;
390
391    type States;
392    fn channel_has_state(
393        &self,
394        channel: &Self::States,
395        hash: &SerializedMerkle,
396    ) -> Result<Option<L64>, TxnErr<Self::GraphError>>;
397
398    type Tags;
399    fn is_tagged(&self, tags: &Self::Tags, t: u64) -> Result<bool, TxnErr<Self::GraphError>>;
400
401    type TagsCursor;
402    fn cursor_tags<'txn>(
403        &'txn self,
404        channel: &Self::Tags,
405        pos: Option<L64>,
406    ) -> Result<
407        crate::pristine::Cursor<
408            Self,
409            &'txn Self,
410            Self::TagsCursor,
411            L64,
412            Pair<SerializedMerkle, SerializedMerkle>,
413        >,
414        TxnErr<Self::GraphError>,
415    >;
416
417    fn cursor_tags_next(
418        &self,
419        cursor: &mut Self::TagsCursor,
420    ) -> Result<Option<(&L64, &Pair<SerializedMerkle, SerializedMerkle>)>, TxnErr<Self::GraphError>>;
421
422    fn cursor_tags_prev(
423        &self,
424        cursor: &mut Self::TagsCursor,
425    ) -> Result<Option<(&L64, &Pair<SerializedMerkle, SerializedMerkle>)>, TxnErr<Self::GraphError>>;
426
427    fn iter_tags(
428        &self,
429        channel: &Self::Tags,
430        from: u64,
431    ) -> Result<
432        Cursor<Self, &Self, Self::TagsCursor, L64, Pair<SerializedMerkle, SerializedMerkle>>,
433        TxnErr<Self::GraphError>,
434    >;
435
436    fn rev_iter_tags(
437        &self,
438        channel: &Self::Tags,
439        from: Option<u64>,
440    ) -> Result<
441        RevCursor<Self, &Self, Self::TagsCursor, L64, Pair<SerializedMerkle, SerializedMerkle>>,
442        TxnErr<Self::GraphError>,
443    >;
444}
445
446#[allow(clippy::type_complexity)]
447pub trait GraphIter: GraphTxnT {
448    type GraphCursor;
449    fn graph_cursor(
450        &self,
451        g: &Self::Graph,
452        s: Option<&Vertex<ChangeId>>,
453    ) -> Result<Self::GraphCursor, TxnErr<Self::GraphError>>;
454    fn next_graph<'txn>(
455        &'txn self,
456        g: &Self::Graph,
457        a: &mut Self::GraphCursor,
458    ) -> Option<Result<(&'txn Vertex<ChangeId>, &'txn SerializedEdge), TxnErr<Self::GraphError>>>;
459
460    fn iter_graph<'a>(
461        &'a self,
462        g: &'a Self::Graph,
463        s: Option<&Vertex<ChangeId>>,
464    ) -> Result<GraphIterator<'a, Self>, TxnErr<Self::GraphError>> {
465        Ok(GraphIterator {
466            cursor: self.graph_cursor(g, s)?,
467            txn: self,
468            g,
469        })
470    }
471}
472
473pub struct GraphIterator<'a, T: GraphIter> {
474    txn: &'a T,
475    g: &'a T::Graph,
476    cursor: T::GraphCursor,
477}
478
479impl<'a, T: GraphIter> Iterator for GraphIterator<'a, T> {
480    type Item = Result<(&'a Vertex<ChangeId>, &'a SerializedEdge), TxnErr<T::GraphError>>;
481    fn next(&mut self) -> Option<Self::Item> {
482        self.txn.next_graph(self.g, &mut self.cursor)
483    }
484}
485
486#[derive(Debug, Error)]
487pub enum BlockError<T: std::error::Error + 'static> {
488    #[error(transparent)]
489    Txn(T),
490    #[error("Block error: {:?}", block)]
491    Block { block: Position<ChangeId> },
492}
493
494impl<T: std::error::Error + 'static> std::convert::From<TxnErr<T>> for BlockError<T> {
495    fn from(e: TxnErr<T>) -> Self {
496        BlockError::Txn(e.0)
497    }
498}
499
500#[allow(clippy::type_complexity)]
501pub trait DepsTxnT: Sized {
502    type DepsError: std::error::Error + Send + Sync + 'static;
503    table!(revdep);
504    table!(dep);
505    table_get!(dep, ChangeId, ChangeId, DepsError);
506    cursor_ref!(dep, ChangeId, ChangeId, DepsError);
507    table_get!(revdep, ChangeId, ChangeId, DepsError);
508    fn iter_revdep(
509        &self,
510        p: &ChangeId,
511    ) -> Result<Cursor<Self, &Self, Self::DepCursor, ChangeId, ChangeId>, TxnErr<Self::DepsError>>;
512    fn iter_dep(
513        &self,
514        p: &ChangeId,
515    ) -> Result<Cursor<Self, &Self, Self::DepCursor, ChangeId, ChangeId>, TxnErr<Self::DepsError>>;
516    fn iter_dep_ref<RT: std::ops::Deref<Target = Self> + Clone>(
517        txn: RT,
518        p: &ChangeId,
519    ) -> Result<Cursor<Self, RT, Self::DepCursor, ChangeId, ChangeId>, TxnErr<Self::DepsError>>;
520    fn iter_touched(
521        &self,
522        p: &Position<ChangeId>,
523    ) -> Result<
524        Cursor<Self, &Self, Self::Touched_filesCursor, Position<ChangeId>, ChangeId>,
525        TxnErr<Self::DepsError>,
526    >;
527    fn iter_rev_touched(
528        &self,
529        p: &ChangeId,
530    ) -> Result<
531        Cursor<Self, &Self, Self::Rev_touched_filesCursor, ChangeId, Position<ChangeId>>,
532        TxnErr<Self::DepsError>,
533    >;
534    table!(touched_files);
535    table!(rev_touched_files);
536    table_get!(touched_files, Position<ChangeId>, ChangeId, DepsError);
537    table_get!(rev_touched_files, ChangeId, Position<ChangeId>, DepsError);
538    iter!(touched_files, Position<ChangeId>, ChangeId, DepsError);
539    iter!(rev_touched_files, ChangeId, Position<ChangeId>, DepsError);
540}
541
542#[derive(Debug, Error)]
543#[error(transparent)]
544pub struct TreeErr<E: std::error::Error + std::fmt::Debug + 'static>(pub E);
545
546#[allow(clippy::type_complexity)]
547pub trait TreeTxnT: Sized {
548    type TreeError: std::error::Error + std::fmt::Debug + Send + Sync + 'static;
549    table!(tree);
550    table_get!(tree, PathId, Inode, TreeError, TreeErr);
551    iter!(tree, PathId, Inode, TreeError, TreeErr);
552
553    table!(revtree);
554    table_get!(revtree, Inode, PathId, TreeError, TreeErr);
555    iter!(revtree, Inode, PathId, TreeError, TreeErr);
556
557    table!(inodes);
558    table!(revinodes);
559    table_get!(inodes, Inode, Position<ChangeId>, TreeError, TreeErr);
560    table_get!(revinodes, Position<ChangeId>, Inode, TreeError, TreeErr);
561
562    table!(partials);
563    cursor!(partials, SmallStr, Position<ChangeId>, TreeError, TreeErr);
564    cursor!(inodes, Inode, Position<ChangeId>, TreeError, TreeErr);
565    fn iter_inodes(
566        &self,
567    ) -> Result<
568        Cursor<Self, &Self, Self::InodesCursor, Inode, Position<ChangeId>>,
569        TreeErr<Self::TreeError>,
570    >;
571
572    // #[cfg(debug_assertions)]
573    cursor!(revinodes, Position<ChangeId>, Inode, TreeError, TreeErr);
574    // #[cfg(debug_assertions)]
575    fn iter_revinodes(
576        &self,
577    ) -> Result<
578        Cursor<Self, &Self, Self::RevinodesCursor, Position<ChangeId>, Inode>,
579        TreeErr<Self::TreeError>,
580    >;
581    fn iter_partials<'txn>(
582        &'txn self,
583        channel: &crate::small_string::SmallStr,
584    ) -> Result<
585        Cursor<Self, &'txn Self, Self::PartialsCursor, SmallStr, Position<ChangeId>>,
586        TreeErr<Self::TreeError>,
587    >;
588}
589
590/// The trait of immutable transactions.
591#[allow(clippy::type_complexity)]
592pub trait TxnT:
593    GraphTxnT
594    + ChannelTxnT
595    + DepsTxnT<DepsError = <Self as GraphTxnT>::GraphError>
596    + TreeTxnT<TreeError = <Self as GraphTxnT>::GraphError>
597{
598    table!(channels);
599    cursor!(channels, SmallStr, SerializedChannel);
600
601    fn hash_from_prefix(
602        &self,
603        prefix: &str,
604    ) -> Result<(Hash, ChangeId), HashPrefixError<Self::GraphError>>;
605
606    fn state_from_prefix(
607        &self,
608        channel: &Self::States,
609        s: &str,
610    ) -> Result<(Merkle, L64), HashPrefixError<Self::GraphError>>;
611
612    fn hash_from_prefix_remote(
613        &self,
614        remote: &RemoteRef<Self>,
615        prefix: &str,
616    ) -> Result<Hash, HashPrefixError<Self::GraphError>>;
617
618    fn load_channel(
619        &self,
620        name: SmallString,
621    ) -> Result<Option<ChannelRef<Self>>, TxnErr<Self::GraphError>>;
622
623    fn load_remote(
624        &self,
625        name: &RemoteId,
626    ) -> Result<Option<RemoteRef<Self>>, TxnErr<Self::GraphError>>;
627
628    /// Iterate a function over all channels. The loop stops the first
629    /// time `f` returns `false`.
630    fn channels(&self, start: &SmallStr)
631    -> Result<Vec<ChannelRef<Self>>, TxnErr<Self::GraphError>>;
632
633    fn iter_remotes<'txn>(
634        &'txn self,
635        start: &RemoteId,
636    ) -> Result<RemotesIterator<'txn, Self>, TxnErr<Self::GraphError>>;
637
638    table!(remotes);
639    cursor!(remotes, RemoteId, SerializedRemote);
640    table!(remote);
641    table!(remotetags);
642    table!(revremote);
643    table!(remotestates);
644    cursor!(remote, L64, Pair<SerializedHash, SerializedMerkle>);
645    rev_cursor!(remote, L64, Pair<SerializedHash, SerializedMerkle>);
646
647    fn iter_remote<'txn>(
648        &'txn self,
649        remote: &Self::Remote,
650        k: u64,
651    ) -> Result<
652        Cursor<Self, &'txn Self, Self::RemoteCursor, L64, Pair<SerializedHash, SerializedMerkle>>,
653        TxnErr<Self::GraphError>,
654    >;
655
656    fn iter_rev_remote<'txn>(
657        &'txn self,
658        remote: &Self::Remote,
659        k: Option<L64>,
660    ) -> Result<
661        RevCursor<
662            Self,
663            &'txn Self,
664            Self::RemoteCursor,
665            L64,
666            Pair<SerializedHash, SerializedMerkle>,
667        >,
668        TxnErr<Self::GraphError>,
669    >;
670
671    fn get_remote(
672        &mut self,
673        name: RemoteId,
674    ) -> Result<Option<RemoteRef<Self>>, TxnErr<Self::GraphError>>;
675
676    fn last_remote(
677        &self,
678        remote: &Self::Remote,
679    ) -> Result<Option<(u64, &Pair<SerializedHash, SerializedMerkle>)>, TxnErr<Self::GraphError>>;
680
681    fn last_remote_tag(
682        &self,
683        remote: &Self::Tags,
684    ) -> Result<Option<(u64, &SerializedMerkle, &SerializedMerkle)>, TxnErr<Self::GraphError>>;
685
686    /// Find the last state greater than or equal to n.
687    fn get_remote_state(
688        &self,
689        remote: &Self::Remote,
690        n: u64,
691    ) -> Result<Option<(u64, &Pair<SerializedHash, SerializedMerkle>)>, TxnErr<Self::GraphError>>;
692
693    /// Find the last tag less than or equal to n (opposite of get_remote_state).
694    fn get_remote_tag(
695        &self,
696        remote: &Self::Tags,
697        n: u64,
698    ) -> Result<Option<(u64, &Pair<SerializedMerkle, SerializedMerkle>)>, TxnErr<Self::GraphError>>;
699
700    fn remote_has_change(
701        &self,
702        remote: &RemoteRef<Self>,
703        hash: &SerializedHash,
704    ) -> Result<bool, TxnErr<Self::GraphError>>;
705    fn remote_has_state(
706        &self,
707        remote: &RemoteRef<Self>,
708        hash: &SerializedMerkle,
709    ) -> Result<Option<u64>, TxnErr<Self::GraphError>>;
710
711    fn current_channel(&self) -> Result<&str, Self::GraphError>;
712}
713
714#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
715#[repr(C)]
716pub struct SerializedPublicKey {
717    algorithm: u8,
718    key: [u8; 32],
719}
720
721/// Iterate the graph between `(key, min_flag)` and `(key,
722/// max_flag)`, where both bounds are included.
723pub fn iter_adjacent<'txn, T: GraphTxnT>(
724    txn: &'txn T,
725    graph: &'txn T::Graph,
726    key: Vertex<ChangeId>,
727    min_flag: EdgeFlags,
728    max_flag: EdgeFlags,
729) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
730    Ok(AdjacentIterator {
731        it: txn.init_adj(graph, key, Position::ROOT, min_flag, max_flag)?,
732        graph,
733        txn,
734    })
735}
736
737pub(crate) fn iter_alive_children<'txn, T: GraphTxnT>(
738    txn: &'txn T,
739    graph: &'txn T::Graph,
740    key: Vertex<ChangeId>,
741) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
742    iter_adjacent(
743        txn,
744        graph,
745        key,
746        EdgeFlags::empty(),
747        EdgeFlags::alive_children(),
748    )
749}
750
751pub(crate) fn iter_deleted_parents<'txn, T: GraphTxnT>(
752    txn: &'txn T,
753    graph: &'txn T::Graph,
754    key: Vertex<ChangeId>,
755) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
756    iter_adjacent(
757        txn,
758        graph,
759        key,
760        EdgeFlags::DELETED | EdgeFlags::PARENT,
761        EdgeFlags::all(),
762    )
763}
764
765pub fn iter_adj_all<'txn, T: GraphTxnT>(
766    txn: &'txn T,
767    graph: &'txn T::Graph,
768    key: Vertex<ChangeId>,
769) -> Result<AdjacentIterator<'txn, T>, TxnErr<T::GraphError>> {
770    iter_adjacent(txn, graph, key, EdgeFlags::empty(), EdgeFlags::all())
771}
772
773pub(crate) fn tree_path<T: TreeTxnT>(
774    txn: &T,
775    v: &Position<ChangeId>,
776) -> Result<Option<String>, TreeErr<T::TreeError>> {
777    if let Some(mut inode) = txn.get_revinodes(v, None)? {
778        let mut components = Vec::new();
779        while !inode.is_root() {
780            if let Some(next) = txn.get_revtree(inode, None)? {
781                components.push(next.basename.as_str().to_string());
782                inode = &next.parent_inode;
783            } else {
784                assert!(components.is_empty());
785                return Ok(None);
786            }
787        }
788        if let Some(mut result) = components.pop() {
789            while let Some(c) = components.pop() {
790                result = result + "/" + c.as_str()
791            }
792            return Ok(Some(result));
793        }
794    }
795    Ok(None)
796}
797
798pub(crate) fn internal<T: GraphTxnT>(
799    txn: &T,
800    h: &Option<Hash>,
801    p: ChangeId,
802) -> Result<Option<ChangeId>, TxnErr<T::GraphError>> {
803    match *h {
804        Some(Hash::None) => Ok(Some(ChangeId::ROOT)),
805        Some(ref h) => Ok(txn.get_internal(&h.into())?.copied()),
806        None => Ok(Some(p)),
807    }
808}
809
810#[derive(Error, Debug)]
811pub enum InconsistentChange<T: std::error::Error + 'static> {
812    #[error("Undeclared dependency")]
813    UndeclaredDep,
814    #[error(transparent)]
815    Txn(T),
816}
817
818impl<T: std::error::Error + 'static> std::convert::From<TxnErr<T>> for InconsistentChange<T> {
819    fn from(e: TxnErr<T>) -> Self {
820        InconsistentChange::Txn(e.0)
821    }
822}
823
824pub fn internal_pos<T: GraphTxnT>(
825    txn: &T,
826    pos: &Position<Option<Hash>>,
827    change_id: ChangeId,
828) -> Result<Position<ChangeId>, InconsistentChange<T::GraphError>> {
829    let change = if let Some(p) = pos.change {
830        if let Some(&p) = txn.get_internal(&p.into())? {
831            p
832        } else {
833            return Err(InconsistentChange::UndeclaredDep);
834        }
835    } else {
836        change_id
837    };
838
839    Ok(Position {
840        change,
841        pos: pos.pos,
842    })
843}
844
845pub fn internal_vertex<T: GraphTxnT>(
846    txn: &T,
847    v: &Vertex<Option<Hash>>,
848    change_id: ChangeId,
849) -> Result<Vertex<ChangeId>, InconsistentChange<T::GraphError>> {
850    let change = if let Some(p) = v.change {
851        if let Some(&p) = txn.get_internal(&p.into())? {
852            p
853        } else {
854            return Err(InconsistentChange::UndeclaredDep);
855        }
856    } else {
857        change_id
858    };
859
860    Ok(Vertex {
861        change,
862        start: v.start,
863        end: v.end,
864    })
865}
866
867#[allow(clippy::type_complexity)]
868pub fn changeid_log<'db, 'txn: 'db, T: ChannelTxnT>(
869    txn: &'txn T,
870    channel: &'db T::Channel,
871    from: L64,
872) -> Result<
873    Cursor<T, &'txn T, T::RevchangesetCursor, L64, Pair<ChangeId, SerializedMerkle>>,
874    TxnErr<T::GraphError>,
875> {
876    T::cursor_revchangeset_ref(txn, txn.rev_changes(channel), Some(from))
877}
878
879pub fn current_state<'db, 'txn: 'db, T: ChannelTxnT>(
880    txn: &'txn T,
881    channel: &'db T::Channel,
882) -> Result<Merkle, TxnErr<T::GraphError>> {
883    match txn
884        .rev_cursor_revchangeset(txn.rev_changes(channel), None)?
885        .next()
886    {
887        Some(e) => Ok((&(e?.1).b).into()),
888        _ => Ok(Merkle::zero()),
889    }
890}
891
892#[allow(clippy::type_complexity)]
893pub(crate) fn changeid_rev_log<'db, 'txn: 'db, T: ChannelTxnT>(
894    txn: &'txn T,
895    channel: &'db T::Channel,
896    from: Option<L64>,
897) -> Result<
898    RevCursor<T, &'txn T, T::RevchangesetCursor, L64, Pair<ChangeId, SerializedMerkle>>,
899    TxnErr<T::GraphError>,
900> {
901    txn.rev_cursor_revchangeset(txn.rev_changes(channel), from)
902}
903
904pub(crate) fn log_for_path<
905    'txn,
906    'channel,
907    T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>,
908>(
909    txn: &'txn T,
910    channel: &'channel T::Channel,
911    key: Position<ChangeId>,
912    from_timestamp: u64,
913) -> Result<PathChangeset<'channel, 'txn, T>, TxnErr<T::GraphError>> {
914    Ok(PathChangeset {
915        iter: T::cursor_revchangeset_ref(
916            txn,
917            txn.rev_changes(channel),
918            Some(from_timestamp.into()),
919        )?,
920        txn,
921        channel,
922        key,
923    })
924}
925
926pub(crate) fn rev_log_for_path<
927    'txn,
928    'channel,
929    T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>,
930>(
931    txn: &'txn T,
932    channel: &'channel T::Channel,
933    key: Position<ChangeId>,
934    from_timestamp: u64,
935) -> Result<RevPathChangeset<'channel, 'txn, T>, TxnErr<T::GraphError>> {
936    Ok(RevPathChangeset {
937        iter: txn.rev_cursor_revchangeset(txn.rev_changes(channel), Some(from_timestamp.into()))?,
938        txn,
939        channel,
940        key,
941    })
942}
943
944/// Is there an alive/pseudo edge from `a` to `b`.
945pub(crate) fn test_edge<T: GraphTxnT>(
946    txn: &T,
947    channel: &T::Graph,
948    a: Position<ChangeId>,
949    b: Position<ChangeId>,
950    min: EdgeFlags,
951    max: EdgeFlags,
952) -> Result<bool, TxnErr<T::GraphError>> {
953    debug!("is_connected {:?} {:?}", a, b);
954    let mut adj = txn.init_adj(channel, a.inode_vertex(), b, min, max)?;
955    match txn.next_adj(channel, &mut adj) {
956        Some(Ok(dest)) => Ok(dest.dest() == b),
957        Some(Err(e)) => Err(e),
958        None => Ok(false),
959    }
960}
961
962/// Is there an alive/pseudo edge to `a`.
963pub(crate) fn is_alive<T: GraphTxnT>(
964    txn: &T,
965    channel: &T::Graph,
966    a: &Vertex<ChangeId>,
967) -> Result<bool, TxnErr<T::GraphError>> {
968    if a.is_root() {
969        return Ok(true);
970    }
971    for e in iter_adjacent(
972        txn,
973        channel,
974        *a,
975        EdgeFlags::PARENT,
976        EdgeFlags::all() - EdgeFlags::DELETED,
977    )? {
978        let e = e?;
979        if !e.flag().contains(EdgeFlags::PSEUDO)
980            && (e.flag().contains(EdgeFlags::BLOCK) || a.is_empty())
981        {
982            return Ok(true);
983        }
984    }
985    Ok(false)
986}
987
988pub fn make_changeid<T: GraphTxnT>(txn: &T, h: &Hash) -> Result<ChangeId, TxnErr<T::GraphError>> {
989    if let Some(h_) = txn.get_internal(&h.into())? {
990        debug!("make_changeid, found = {:?} {:?}", h, h_);
991        return Ok(*h_);
992    }
993    use byteorder::{ByteOrder, LittleEndian};
994    let mut p = match h {
995        Hash::None => return Ok(ChangeId::ROOT),
996        Hash::Blake3(s) => LittleEndian::read_u64(&s[..]),
997        #[cfg(feature = "git2")]
998        Hash::GitSha1(s) => LittleEndian::read_u64(&s[..]),
999        #[cfg(feature = "git2")]
1000        Hash::GitSha2(s) => LittleEndian::read_u64(&s[..]),
1001    };
1002    let mut pp = ChangeId(L64(p));
1003    while let Some(ext) = txn.get_external(&pp).optional()? {
1004        debug!("ext = {:?}", ext);
1005        p = u64::from_le(p) + 1;
1006        pp = ChangeId(L64(p.to_le()));
1007    }
1008    Ok(pp)
1009}
1010
1011// #[cfg(debug_assertions)]
1012pub fn debug_tree<P: AsRef<std::path::Path>, T: TreeTxnT>(
1013    txn: &T,
1014    file: P,
1015) -> Result<(), std::io::Error> {
1016    let root = OwnedPathId {
1017        parent_inode: Inode::ROOT,
1018        basename: SmallString::default(),
1019    };
1020    let mut f = std::fs::File::create(file)?;
1021    for t in txn.iter_tree(&root, None).unwrap() {
1022        writeln!(f, "{:?}", t.unwrap())?
1023    }
1024    Ok(())
1025}
1026
1027// #[cfg(debug_assertions)]
1028pub fn debug_tree_print<T: TreeTxnT>(txn: &T) {
1029    let root = OwnedPathId {
1030        parent_inode: Inode::ROOT,
1031        basename: SmallString::default(),
1032    };
1033    for t in txn.iter_tree(&root, None).unwrap() {
1034        debug!("{:?}", t.unwrap())
1035    }
1036}
1037
1038// #[cfg(debug_assertions)]
1039pub fn debug_remotes<T: TxnT>(txn: &T) {
1040    for t in txn.iter_remotes(&RemoteId([0; 16])).unwrap() {
1041        let rem = t.unwrap();
1042        debug!("{:?}", rem.id());
1043        for x in txn.iter_remote(&rem.lock().remote, 0).unwrap() {
1044            debug!("    {:?}", x.unwrap());
1045        }
1046    }
1047}
1048
1049/// Write the graph of a channel to file `f` in graphviz
1050/// format. **Warning:** this can be really large on old channels.
1051// #[cfg(debug_assertions)]
1052pub fn debug_to_file<P: AsRef<std::path::Path>, T: GraphIter + ChannelTxnT>(
1053    txn: &T,
1054    channel: &ChannelRef<T>,
1055    f: P,
1056) -> Result<bool, std::io::Error> {
1057    info!("debug {:?}", f.as_ref());
1058    let mut f = std::fs::File::create(f)?;
1059    let channel = channel.r.read();
1060    let done = debug(txn, txn.graph(&*channel), &mut f)?;
1061    f.flush()?;
1062    info!("done debugging {:?}", done);
1063    Ok(done)
1064}
1065
1066// #[cfg(debug_assertions)]
1067pub fn debug_revtree<P: AsRef<std::path::Path>, T: TreeTxnT>(
1068    txn: &T,
1069    file: P,
1070) -> Result<(), std::io::Error> {
1071    let mut f = std::fs::File::create(file)?;
1072    for t in txn.iter_revtree(&Inode::ROOT, None).unwrap() {
1073        writeln!(f, "{:?}", t.unwrap())?
1074    }
1075    Ok(())
1076}
1077
1078// #[cfg(debug_assertions)]
1079pub fn debug_revtree_print<T: TreeTxnT>(txn: &T) {
1080    for t in txn.iter_revtree(&Inode::ROOT, None).unwrap() {
1081        debug!("{:?}", t.unwrap())
1082    }
1083}
1084
1085// #[cfg(debug_assertions)]
1086pub fn debug_inodes<T: TreeTxnT>(txn: &T) {
1087    debug!("debug_inodes");
1088    for t in txn.iter_inodes().unwrap() {
1089        debug!("debug_inodes = {:?}", t.unwrap())
1090    }
1091    debug!("/debug_inodes");
1092}
1093
1094// #[cfg(debug_assertions)]
1095pub fn debug_revinodes<T: TreeTxnT>(txn: &T) {
1096    debug!("debug_revinodes");
1097    for t in txn.iter_revinodes().unwrap() {
1098        debug!("debug_revinodes = {:?}", t.unwrap())
1099    }
1100    debug!("/debug_revinodes");
1101}
1102
1103pub fn debug_dep<T: DepsTxnT>(txn: &T) {
1104    debug!("debug_dep");
1105    for t in txn.iter_dep(&ChangeId::ROOT).unwrap() {
1106        debug!("debug_dep = {:?}", t.unwrap())
1107    }
1108    debug!("/debug_dep");
1109}
1110
1111pub fn debug_revdep<T: DepsTxnT>(txn: &T) {
1112    debug!("debug_revdep");
1113    for t in txn.iter_revdep(&ChangeId::ROOT).unwrap() {
1114        debug!("debug_revdep = {:?}", t.unwrap())
1115    }
1116    debug!("/debug_revdep");
1117}
1118
1119/// Write the graph of a channel to write `W` in graphviz
1120/// format. **Warning:** this can be really large on old channels.
1121// #[cfg(debug_assertions)]
1122pub fn debug<W: Write, T: GraphIter + GraphTxnT>(
1123    txn: &T,
1124    channel: &T::Graph,
1125    mut f: W,
1126) -> Result<bool, std::io::Error> {
1127    let mut cursor = txn.graph_cursor(channel, None).unwrap();
1128    writeln!(f, "digraph {{")?;
1129    let mut keys = std::collections::HashSet::new();
1130    let mut at_least_one = false;
1131    while let Some(x) = txn.next_graph(channel, &mut cursor) {
1132        let (k, v) = x.unwrap();
1133        at_least_one = true;
1134        debug!("debug {:?} {:?}", k, v);
1135        if keys.insert(k) {
1136            debug_vertex(txn, &mut f, *k)?
1137        }
1138        debug_edge(txn, channel, &mut f, *k, *v)?
1139    }
1140    writeln!(f, "}}")?;
1141    Ok(at_least_one)
1142}
1143#[allow(clippy::type_complexity)]
1144pub fn check_alive<T: ChannelTxnT + GraphIter>(
1145    txn: &T,
1146    channel: &T::Graph,
1147) -> (
1148    HashMap<Vertex<ChangeId>, Option<Vertex<ChangeId>>>,
1149    Vec<(Vertex<ChangeId>, Option<Vertex<ChangeId>>)>,
1150) {
1151    // Find the reachable with a DFS.
1152    let mut reachable = HashSet::default();
1153    let mut stack = vec![Vertex::ROOT];
1154    while let Some(v) = stack.pop() {
1155        if !reachable.insert(v) {
1156            continue;
1157        }
1158        for e in iter_adjacent(
1159            txn,
1160            channel,
1161            v,
1162            EdgeFlags::empty(),
1163            EdgeFlags::all() - EdgeFlags::DELETED - EdgeFlags::PARENT,
1164        )
1165        .unwrap()
1166        {
1167            let e = e.unwrap();
1168            stack.push(*txn.find_block(channel, e.dest()).unwrap());
1169        }
1170    }
1171    debug!("reachable = {:#?}", reachable);
1172
1173    // Find the alive
1174    let mut alive_unreachable = HashMap::default();
1175    let mut cursor = txn.graph_cursor(channel, None).unwrap();
1176
1177    let mut visited = HashSet::default();
1178    let mut k0 = Vertex::ROOT;
1179    let mut k0_has_pseudo_parents = false;
1180    let mut k0_has_regular_parents = false;
1181    let mut reachable_pseudo = Vec::new();
1182    while let Some(x) = txn.next_graph(channel, &mut cursor) {
1183        let (&k, &v) = x.unwrap();
1184        debug!("check_alive, k = {:?}, v = {:?}", k, v);
1185        if k0 != k {
1186            if k0_has_pseudo_parents && !k0_has_regular_parents {
1187                reachable_pseudo.push((
1188                    k0,
1189                    find_file(txn, channel, k0, &mut stack, &mut visited).unwrap(),
1190                ))
1191            }
1192            k0 = k;
1193            k0_has_pseudo_parents = false;
1194            k0_has_regular_parents = false;
1195        }
1196        if v.flag().contains(EdgeFlags::PARENT)
1197            && !v.flag().contains(EdgeFlags::FOLDER)
1198            && !v.flag().contains(EdgeFlags::DELETED)
1199        {
1200            if v.flag().contains(EdgeFlags::PSEUDO) {
1201                k0_has_pseudo_parents = true
1202            } else {
1203                k0_has_regular_parents = true
1204            }
1205        }
1206
1207        if v.flag().contains(EdgeFlags::PARENT)
1208            && (v.flag().contains(EdgeFlags::BLOCK) || k.is_empty())
1209            && !v.flag().contains(EdgeFlags::DELETED)
1210            && !reachable.contains(&k)
1211        {
1212            let file = find_file(txn, channel, k, &mut stack, &mut visited).unwrap();
1213            alive_unreachable.insert(k, file);
1214        }
1215    }
1216    if !k0.is_root() && k0_has_pseudo_parents && !k0_has_regular_parents {
1217        reachable_pseudo.push((
1218            k0,
1219            find_file(txn, channel, k0, &mut stack, &mut visited).unwrap(),
1220        ));
1221    }
1222
1223    (alive_unreachable, reachable_pseudo)
1224}
1225
1226fn find_file<T: GraphTxnT>(
1227    txn: &T,
1228    channel: &T::Graph,
1229    k: Vertex<ChangeId>,
1230    stack: &mut Vec<Vertex<ChangeId>>,
1231    visited: &mut HashSet<Vertex<ChangeId>>,
1232) -> Result<Option<Vertex<ChangeId>>, TxnErr<T::GraphError>> {
1233    let mut file = None;
1234    stack.clear();
1235    stack.push(k);
1236    visited.clear();
1237    'outer: while let Some(kk) = stack.pop() {
1238        if !visited.insert(kk) {
1239            continue;
1240        }
1241        for e in iter_adjacent(txn, channel, kk, EdgeFlags::PARENT, EdgeFlags::all())? {
1242            let e = e?;
1243            if e.flag().contains(EdgeFlags::PARENT) {
1244                if e.flag().contains(EdgeFlags::FOLDER) {
1245                    file = Some(kk);
1246                    break 'outer;
1247                }
1248                stack.push(*txn.find_block_end(channel, e.dest()).unwrap());
1249            }
1250        }
1251    }
1252    Ok(file)
1253}
1254
1255pub fn debug_root<W: Write, T: GraphTxnT>(
1256    txn: &T,
1257    channel: &T::Graph,
1258    root: Vertex<ChangeId>,
1259    mut f: W,
1260    down: bool,
1261) -> Result<(), std::io::Error> {
1262    writeln!(f, "digraph {{")?;
1263    let mut visited = HashSet::default();
1264    let mut stack = vec![root];
1265    while let Some(v) = stack.pop() {
1266        if !visited.insert(v) {
1267            continue;
1268        }
1269        debug_vertex(txn, &mut f, v)?;
1270        assert!(txn.get_external(&v.change).optional().unwrap().is_some());
1271        let stack_len = stack.len();
1272        for e in iter_adj_all(txn, channel, v).unwrap() {
1273            let e = e.unwrap();
1274            assert!(
1275                txn.get_external(&e.introduced_by())
1276                    .optional()
1277                    .unwrap()
1278                    .is_some()
1279            );
1280            assert!(
1281                txn.get_external(&e.dest().change)
1282                    .optional()
1283                    .unwrap()
1284                    .is_some()
1285            );
1286            if e.flag().contains(EdgeFlags::PARENT) != down {
1287                debug_edge(txn, channel, &mut f, v, *e)?;
1288                let v = if e.flag().contains(EdgeFlags::PARENT) {
1289                    txn.find_block_end(channel, e.dest()).unwrap()
1290                } else {
1291                    txn.find_block(channel, e.dest()).unwrap()
1292                };
1293                stack.push(*v);
1294            }
1295        }
1296        stack[stack_len..].reverse()
1297    }
1298    writeln!(f, "}}")?;
1299    Ok(())
1300}
1301
1302fn debug_vertex<W: std::io::Write, T: GraphTxnT>(
1303    txn: &T,
1304    mut f: W,
1305    k: Vertex<ChangeId>,
1306) -> Result<(), std::io::Error> {
1307    let label = if let Ok(Some(h)) = txn.get_external(&k.change).optional() {
1308        match h.into() {
1309            Hash::GitSha1(s) => data_encoding::HEXLOWER.encode(&s[..4]),
1310            Hash::GitSha2(s) => data_encoding::HEXLOWER.encode(&s[..4]),
1311            _ => k.change.to_base32(),
1312        }
1313    } else {
1314        k.change.to_base32()
1315    };
1316    writeln!(
1317        f,
1318        "node_{}_{}_{}[label=\"{label} [{};{}[\"];",
1319        k.change.to_base32(),
1320        k.start.0,
1321        k.end.0,
1322        k.start.0,
1323        k.end.0,
1324    )
1325}
1326
1327fn debug_edge<T: GraphTxnT, W: std::io::Write>(
1328    txn: &T,
1329    channel: &T::Graph,
1330    mut f: W,
1331    k: Vertex<ChangeId>,
1332    v: SerializedEdge,
1333) -> Result<(), std::io::Error> {
1334    let style = if v.flag().contains(EdgeFlags::DELETED) {
1335        ", style=dashed"
1336    } else if v.flag().contains(EdgeFlags::PSEUDO) {
1337        ", style=dotted"
1338    } else {
1339        ""
1340    };
1341    let color = if v.flag().contains(EdgeFlags::PARENT) {
1342        if v.flag().contains(EdgeFlags::FOLDER) {
1343            "orange"
1344        } else {
1345            "red"
1346        }
1347    } else if v.flag().contains(EdgeFlags::FOLDER) {
1348        "royalblue"
1349    } else {
1350        "forestgreen"
1351    };
1352
1353    if v.flag().contains(EdgeFlags::PARENT) {
1354        let dest = if v.dest().change.is_root() {
1355            Vertex::ROOT
1356        } else {
1357            match txn.find_block_end(channel, v.dest()) {
1358                Ok(&dest) => dest,
1359                _ => {
1360                    return Ok(());
1361                }
1362            }
1363        };
1364        writeln!(
1365            f,
1366            "node_{}_{}_{} -> node_{}_{}_{} [label=\"{}{}{}\", color=\"{}\"{}];",
1367            k.change.to_base32(),
1368            k.start.0,
1369            k.end.0,
1370            dest.change.to_base32(),
1371            dest.start.0,
1372            dest.end.0,
1373            if v.flag().contains(EdgeFlags::BLOCK) {
1374                "["
1375            } else {
1376                ""
1377            },
1378            v.introduced_by().to_base32(),
1379            if v.flag().contains(EdgeFlags::BLOCK) {
1380                "]"
1381            } else {
1382                ""
1383            },
1384            color,
1385            style
1386        )?;
1387    } else {
1388        match txn.find_block(channel, v.dest()) {
1389            Ok(dest) => {
1390                writeln!(
1391                    f,
1392                    "node_{}_{}_{} -> node_{}_{}_{} [label=\"{}{}{}\", color=\"{}\"{}];",
1393                    k.change.to_base32(),
1394                    k.start.0,
1395                    k.end.0,
1396                    dest.change.to_base32(),
1397                    dest.start.0,
1398                    dest.end.0,
1399                    if v.flag().contains(EdgeFlags::BLOCK) {
1400                        "["
1401                    } else {
1402                        ""
1403                    },
1404                    v.introduced_by().to_base32(),
1405                    if v.flag().contains(EdgeFlags::BLOCK) {
1406                        "]"
1407                    } else {
1408                        ""
1409                    },
1410                    color,
1411                    style
1412                )?;
1413            }
1414            _ => {
1415                writeln!(
1416                    f,
1417                    "node_{}_{}_{} -> node_{}_{} [label=\"{}{}{}\", color=\"{}\"{}];",
1418                    k.change.to_base32(),
1419                    k.start.0,
1420                    k.end.0,
1421                    v.dest().change.to_base32(),
1422                    v.dest().pos.0,
1423                    if v.flag().contains(EdgeFlags::BLOCK) {
1424                        "["
1425                    } else {
1426                        ""
1427                    },
1428                    v.introduced_by().to_base32(),
1429                    if v.flag().contains(EdgeFlags::BLOCK) {
1430                        "]"
1431                    } else {
1432                        ""
1433                    },
1434                    color,
1435                    style
1436                )?;
1437            }
1438        }
1439    }
1440    Ok(())
1441}
1442
1443/// A cursor over a table, initialised at a certain value.
1444pub struct Cursor<T: Sized, RT: std::ops::Deref<Target = T>, Cursor, K: ?Sized, V: ?Sized> {
1445    pub cursor: Cursor,
1446    pub txn: RT,
1447    pub t: std::marker::PhantomData<T>,
1448    pub k: std::marker::PhantomData<K>,
1449    pub v: std::marker::PhantomData<V>,
1450}
1451
1452pub struct RevCursor<T: Sized, RT: std::ops::Deref<Target = T>, Cursor, K: ?Sized, V: ?Sized> {
1453    pub cursor: Cursor,
1454    pub txn: RT,
1455    pub t: std::marker::PhantomData<T>,
1456    pub k: std::marker::PhantomData<K>,
1457    pub v: std::marker::PhantomData<V>,
1458}
1459
1460initialized_cursor!(changeset, ChangeId, L64, ChannelTxnT, GraphError);
1461initialized_cursor!(
1462    revchangeset,
1463    L64,
1464    Pair<ChangeId, SerializedMerkle>,
1465    ChannelTxnT,
1466    GraphError
1467);
1468initialized_rev_cursor!(
1469    revchangeset,
1470    L64,
1471    Pair<ChangeId, SerializedMerkle>,
1472    ChannelTxnT,
1473    GraphError
1474);
1475initialized_cursor!(tags, L64, Pair<SerializedMerkle, SerializedMerkle>, ChannelTxnT, GraphError);
1476initialized_rev_cursor!(tags, L64, Pair<SerializedMerkle, SerializedMerkle>, ChannelTxnT, GraphError);
1477initialized_cursor!(tree, PathId, Inode, TreeTxnT, TreeError, TreeErr);
1478initialized_cursor!(revtree, Inode, PathId, TreeTxnT, TreeError, TreeErr);
1479initialized_cursor!(dep, ChangeId, ChangeId, DepsTxnT, DepsError);
1480initialized_cursor!(
1481    partials,
1482    SmallStr,
1483    Position<ChangeId>,
1484    TreeTxnT,
1485    TreeError,
1486    TreeErr
1487);
1488initialized_cursor!(
1489    rev_touched_files,
1490    ChangeId,
1491    Position<ChangeId>,
1492    DepsTxnT,
1493    DepsError
1494);
1495initialized_cursor!(
1496    touched_files,
1497    Position<ChangeId>,
1498    ChangeId,
1499    DepsTxnT,
1500    DepsError
1501);
1502initialized_cursor!(remote, L64, Pair<SerializedHash, SerializedMerkle>);
1503initialized_rev_cursor!(remote, L64, Pair<SerializedHash, SerializedMerkle>);
1504initialized_cursor!(
1505    inodes,
1506    Inode,
1507    Position<ChangeId>,
1508    TreeTxnT,
1509    TreeError,
1510    TreeErr
1511);
1512initialized_cursor!(
1513    revinodes,
1514    Position<ChangeId>,
1515    Inode,
1516    TreeTxnT,
1517    TreeError,
1518    TreeErr
1519);
1520
1521/// An iterator for nodes adjacent to `key` through an edge with flags smaller than `max_flag`.
1522pub struct AdjacentIterator<'txn, T: GraphTxnT> {
1523    it: T::Adj,
1524    graph: &'txn T::Graph,
1525    txn: &'txn T,
1526}
1527
1528impl<'txn, T: GraphTxnT> Iterator for AdjacentIterator<'txn, T> {
1529    type Item = Result<&'txn SerializedEdge, TxnErr<T::GraphError>>;
1530    fn next(&mut self) -> Option<Self::Item> {
1531        self.txn.next_adj(self.graph, &mut self.it)
1532    }
1533}
1534
1535pub struct PathChangeset<'channel, 'txn: 'channel, T: ChannelTxnT + DepsTxnT> {
1536    txn: &'txn T,
1537    channel: &'channel T::Channel,
1538    iter: Cursor<T, &'txn T, T::RevchangesetCursor, L64, Pair<ChangeId, SerializedMerkle>>,
1539    key: Position<ChangeId>,
1540}
1541
1542pub struct RevPathChangeset<'channel, 'txn: 'channel, T: ChannelTxnT + DepsTxnT> {
1543    txn: &'txn T,
1544    channel: &'channel T::Channel,
1545    iter: RevCursor<T, &'txn T, T::RevchangesetCursor, L64, Pair<ChangeId, SerializedMerkle>>,
1546    key: Position<ChangeId>,
1547}
1548
1549impl<'channel, 'txn: 'channel, T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>>
1550    Iterator for PathChangeset<'channel, 'txn, T>
1551{
1552    type Item = Result<Hash, TxnErr<T::GraphError>>;
1553    fn next(&mut self) -> Option<Self::Item> {
1554        for x in self.iter.by_ref() {
1555            let changeid = match x {
1556                Ok(x) => (x.1).a,
1557                Err(e) => return Some(Err(e)),
1558            };
1559            let iter = match self.txn.iter_rev_touched_files(&changeid, None) {
1560                Ok(iter) => iter,
1561                Err(e) => return Some(Err(e)),
1562            };
1563            for x in iter {
1564                let (p, touched) = match x {
1565                    Ok(x) => x,
1566                    Err(e) => return Some(Err(e)),
1567                };
1568                if *p > changeid {
1569                    break;
1570                } else if *p < changeid {
1571                    continue;
1572                }
1573                match is_ancestor_of(self.txn, self.txn.graph(self.channel), self.key, *touched) {
1574                    Ok(true) => {
1575                        return self
1576                            .txn
1577                            .get_external(&changeid)
1578                            .optional()
1579                            .transpose()
1580                            .map(|x| x.map(|x| x.into()));
1581                    }
1582                    Err(e) => return Some(Err(e)),
1583                    Ok(false) => {}
1584                }
1585            }
1586        }
1587        None
1588    }
1589}
1590
1591impl<'channel, 'txn: 'channel, T: ChannelTxnT + DepsTxnT<DepsError = <T as GraphTxnT>::GraphError>>
1592    Iterator for RevPathChangeset<'channel, 'txn, T>
1593{
1594    type Item = Result<Hash, TxnErr<T::GraphError>>;
1595    fn next(&mut self) -> Option<Self::Item> {
1596        loop {
1597            let changeid = match self.iter.next()? {
1598                Err(e) => return Some(Err(e)),
1599                Ok((_, p)) => p.a,
1600            };
1601            let iter = match self.txn.iter_rev_touched_files(&changeid, None) {
1602                Ok(iter) => iter,
1603                Err(e) => return Some(Err(e)),
1604            };
1605            for x in iter {
1606                let (p, touched) = match x {
1607                    Ok(x) => x,
1608                    Err(e) => return Some(Err(e)),
1609                };
1610                if *p > changeid {
1611                    break;
1612                } else if *p < changeid {
1613                    continue;
1614                }
1615                match is_ancestor_of(self.txn, self.txn.graph(self.channel), self.key, *touched) {
1616                    Ok(true) => {
1617                        return self
1618                            .txn
1619                            .get_external(&changeid)
1620                            .optional()
1621                            .transpose()
1622                            .map(|x| x.map(From::from));
1623                    }
1624                    Err(e) => return Some(Err(e)),
1625                    Ok(false) => {}
1626                }
1627            }
1628        }
1629    }
1630}
1631
1632fn is_ancestor_of<T: GraphTxnT>(
1633    txn: &T,
1634    channel: &T::Graph,
1635    a: Position<ChangeId>,
1636    b: Position<ChangeId>,
1637) -> Result<bool, TxnErr<T::GraphError>> {
1638    let mut stack = vec![b];
1639    let mut visited = std::collections::HashSet::new();
1640    debug!("a = {:?}", a);
1641    while let Some(b) = stack.pop() {
1642        debug!("pop {:?}", b);
1643        if a == b {
1644            return Ok(true);
1645        }
1646        if !visited.insert(b) {
1647            continue;
1648        }
1649        for p in iter_adjacent(
1650            txn,
1651            channel,
1652            b.inode_vertex(),
1653            EdgeFlags::FOLDER | EdgeFlags::PARENT,
1654            EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::PSEUDO,
1655        )? {
1656            let p = p?;
1657            // Ok, since `p` is in the channel.
1658            let parent = txn.find_block_end(channel, p.dest()).unwrap();
1659            for pp in iter_adjacent(
1660                txn,
1661                channel,
1662                *parent,
1663                EdgeFlags::FOLDER | EdgeFlags::PARENT,
1664                EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::PSEUDO,
1665            )? {
1666                let pp = pp?;
1667                if pp.dest() == a {
1668                    return Ok(true);
1669                }
1670                stack.push(pp.dest())
1671            }
1672        }
1673    }
1674    Ok(false)
1675}
1676
1677pub struct ChannelIterator<'txn, T: TxnT> {
1678    txn: &'txn T,
1679    cursor: T::ChannelsCursor,
1680}
1681
1682impl<'txn, T: TxnT> Iterator for ChannelIterator<'txn, T> {
1683    type Item = Result<(&'txn SmallStr, ChannelRef<T>), TxnErr<T::GraphError>>;
1684    fn next(&mut self) -> Option<Self::Item> {
1685        // Option<(SmallString, (u64, u64, u64, u64, u64, u64))>
1686        match self.txn.cursor_channels_next(&mut self.cursor) {
1687            Err(e) => Some(Err(e)),
1688            Ok(Some((name, _))) => {
1689                Some(Ok((name, self.txn.load_channel(name.to_owned()).unwrap()?)))
1690            }
1691            Ok(None) => None,
1692        }
1693    }
1694}
1695
1696pub struct RemotesIterator<'txn, T: TxnT> {
1697    txn: &'txn T,
1698    cursor: T::RemotesCursor,
1699}
1700
1701impl<'txn, T: TxnT> Iterator for RemotesIterator<'txn, T> {
1702    type Item = Result<RemoteRef<T>, TxnErr<T::GraphError>>;
1703    fn next(&mut self) -> Option<Self::Item> {
1704        match self.txn.cursor_remotes_next(&mut self.cursor) {
1705            Ok(Some((name, _))) => self.txn.load_remote(name).transpose(),
1706            Ok(None) => None,
1707            Err(e) => Some(Err(e)),
1708        }
1709    }
1710}
1711
1712pub trait GraphMutTxnT: GraphTxnT {
1713    put_del!(internal, SerializedHash, ChangeId, GraphError);
1714    put_del!(external, ChangeId, SerializedHash, GraphError);
1715
1716    /// Insert a key and a value to a graph. Returns `false` if and only if `(k, v)` was already in the graph, in which case no insertion happened.
1717    fn put_graph(
1718        &mut self,
1719        channel: &mut Self::Graph,
1720        k: &Vertex<ChangeId>,
1721        v: &SerializedEdge,
1722    ) -> Result<bool, TxnErr<Self::GraphError>>;
1723
1724    /// Delete a key and a value from a graph. Returns `true` if and only if `(k, v)` was in the graph.
1725    fn del_graph(
1726        &mut self,
1727        channel: &mut Self::Graph,
1728        k: &Vertex<ChangeId>,
1729        v: Option<&SerializedEdge>,
1730    ) -> Result<bool, TxnErr<Self::GraphError>>;
1731
1732    fn debug(&mut self, channel: &mut Self::Graph, extra: &str);
1733
1734    /// Split a key `[a, b[` at position `pos`, yielding two keys `[a,
1735    /// pos[` and `[pos, b[` linked by an edge.
1736    fn split_block(
1737        &mut self,
1738        graph: &mut Self::Graph,
1739        key: &Vertex<ChangeId>,
1740        pos: ChangePosition,
1741        buf: &mut Vec<SerializedEdge>,
1742    ) -> Result<(), TxnErr<Self::GraphError>>;
1743}
1744
1745pub trait ChannelMutTxnT: ChannelTxnT + GraphMutTxnT {
1746    fn graph_mut(channel: &mut Self::Channel) -> &mut Self::Graph;
1747    fn touch_channel(&mut self, channel: &mut Self::Channel, t: Option<u64>);
1748
1749    /// Add a change and a timestamp to a change table. Returns `None` if and only if `(p, t)` was already in the change table, in which case no insertion happened. Returns the new state else.
1750    fn put_changes(
1751        &mut self,
1752        channel: &mut Self::Channel,
1753        p: ChangeId,
1754        t: ApplyTimestamp,
1755        h: &Hash,
1756    ) -> Result<Option<Merkle>, TxnErr<Self::GraphError>>;
1757
1758    /// Delete a change from a change table. Returns `true` if and only if `(p, t)` was in the change table.
1759    fn del_changes(
1760        &mut self,
1761        channel: &mut Self::Channel,
1762        p: ChangeId,
1763        t: ApplyTimestamp,
1764    ) -> Result<bool, TxnErr<Self::GraphError>>;
1765
1766    fn put_tags(
1767        &mut self,
1768        channel: &mut Self::Tags,
1769        n: u64,
1770        m: &Merkle,
1771    ) -> Result<(), TxnErr<Self::GraphError>>;
1772
1773    fn tags_mut<'a>(&mut self, channel: &'a mut Self::Channel) -> &'a mut Self::Tags;
1774
1775    fn del_tags(
1776        &mut self,
1777        channel: &mut Self::Tags,
1778        n: u64,
1779    ) -> Result<(), TxnErr<Self::GraphError>>;
1780
1781    /// Move the change at `old_pos` to `new_pos`, shifting all changes
1782    /// in `[new_pos, old_pos-1]` up by one and recomputing the Merkle
1783    /// chain from `new_pos` onwards.
1784    ///
1785    /// Precondition: `new_pos <= old_pos`, no tags in `[new_pos, old_pos]`.
1786    fn move_change(
1787        &mut self,
1788        channel: &mut Self::Channel,
1789        change_id: ChangeId,
1790        old_pos: ApplyTimestamp,
1791        new_pos: ApplyTimestamp,
1792    ) -> Result<(), TxnErr<Self::GraphError>>;
1793}
1794
1795pub trait DepsMutTxnT: DepsTxnT {
1796    put_del!(dep, ChangeId, ChangeId, DepsError);
1797    put_del!(revdep, ChangeId, ChangeId, DepsError);
1798    put_del!(touched_files, Position<ChangeId>, ChangeId, DepsError);
1799    put_del!(rev_touched_files, ChangeId, Position<ChangeId>, DepsError);
1800}
1801
1802pub trait TreeMutTxnT: TreeTxnT {
1803    put_del!(inodes, Inode, Position<ChangeId>, TreeError, TreeErr);
1804    put_del!(revinodes, Position<ChangeId>, Inode, TreeError, TreeErr);
1805    put_del!(tree, PathId, Inode, TreeError, TreeErr);
1806    put_del!(revtree, Inode, PathId, TreeError, TreeErr);
1807    fn put_partials(
1808        &mut self,
1809        k: &SmallStr,
1810        e: Position<ChangeId>,
1811    ) -> Result<bool, TreeErr<Self::TreeError>>;
1812
1813    fn del_partials(
1814        &mut self,
1815        k: &SmallStr,
1816        e: Option<Position<ChangeId>>,
1817    ) -> Result<bool, TreeErr<Self::TreeError>>;
1818}
1819
1820/// The trait of immutable transactions.
1821pub trait MutTxnT:
1822    GraphMutTxnT
1823    + ChannelMutTxnT
1824    + DepsMutTxnT<DepsError = <Self as GraphTxnT>::GraphError>
1825    + TreeMutTxnT<TreeError = <Self as GraphTxnT>::GraphError>
1826    + TxnT
1827{
1828    /// Open a channel, creating it if it is missing. The return type
1829    /// is a `Rc<RefCell<…>>` in order to avoid:
1830    /// - opening the same channel twice. Since a channel contains pointers, that could potentially lead to double-borrow issues. We absolutely have to check that at runtime (hence the `RefCell`).
1831    /// - writing the channel to disk (if the backend is written on the disk) for every minor operation on the channel.
1832    ///
1833    /// Additionally, the `Rc` is used to:
1834    /// - avoid having to commit channels explicitly (channels are
1835    ///   committed automatically upon committing the transaction), and
1836    /// - to return a value that doesn't borrow the transaction, so
1837    ///   that the channel can actually be used in a mutable transaction.
1838    fn open_or_create_channel(
1839        &mut self,
1840        name: &SmallStr,
1841    ) -> Result<ChannelRef<Self>, Self::GraphError>;
1842
1843    fn fork(
1844        &mut self,
1845        channel: &ChannelRef<Self>,
1846        name: &SmallStr,
1847    ) -> Result<ChannelRef<Self>, ForkError<Self::GraphError>>;
1848
1849    fn rename_channel(
1850        &mut self,
1851        channel: &mut ChannelRef<Self>,
1852        name: &SmallStr,
1853    ) -> Result<(), ForkError<Self::GraphError>>;
1854
1855    fn drop_channel(&mut self, name: &SmallStr) -> Result<bool, Self::GraphError>;
1856
1857    /// Commit this transaction.
1858    fn commit(self) -> Result<(), Self::GraphError>;
1859
1860    fn open_or_create_remote(
1861        &mut self,
1862        id: RemoteId,
1863        path: &SmallStr,
1864    ) -> Result<RemoteRef<Self>, Self::GraphError>;
1865
1866    fn put_remote(
1867        &mut self,
1868        remote: &mut RemoteRef<Self>,
1869        k: u64,
1870        v: (Hash, Merkle),
1871    ) -> Result<bool, TxnErr<Self::GraphError>>;
1872
1873    fn del_remote(
1874        &mut self,
1875        remote: &mut RemoteRef<Self>,
1876        k: u64,
1877    ) -> Result<bool, TxnErr<Self::GraphError>>;
1878
1879    fn drop_remote(&mut self, remote: RemoteRef<Self>) -> Result<bool, Self::GraphError>;
1880
1881    fn drop_named_remote(&mut self, id: RemoteId) -> Result<bool, Self::GraphError>;
1882
1883    fn set_current_channel(&mut self, cur: &str) -> Result<(), Self::GraphError>;
1884}
1885
1886pub fn put_inodes_with_rev<T: TreeMutTxnT>(
1887    txn: &mut T,
1888    inode: &Inode,
1889    position: &Position<ChangeId>,
1890) -> Result<(), TreeErr<T::TreeError>> {
1891    txn.put_inodes(inode, position)?;
1892    txn.put_revinodes(position, inode)?;
1893    Ok(())
1894}
1895
1896pub fn del_inodes_with_rev<T: TreeMutTxnT>(
1897    txn: &mut T,
1898    inode: &Inode,
1899    position: &Position<ChangeId>,
1900) -> Result<bool, TreeErr<T::TreeError>> {
1901    if txn.del_inodes(inode, Some(position))? {
1902        assert!(txn.del_revinodes(position, Some(inode))?);
1903        Ok(true)
1904    } else {
1905        Ok(false)
1906    }
1907}
1908
1909pub fn put_tree_with_rev<T: TreeMutTxnT>(
1910    txn: &mut T,
1911    file_id: &PathId,
1912    inode: &Inode,
1913) -> Result<(), TreeErr<T::TreeError>> {
1914    if txn.put_tree(file_id, inode)? {
1915        txn.put_revtree(inode, file_id)?;
1916    }
1917    Ok(())
1918}
1919
1920pub fn del_tree_with_rev<T: TreeMutTxnT>(
1921    txn: &mut T,
1922    file_id: &PathId,
1923    inode: &Inode,
1924) -> Result<bool, TreeErr<T::TreeError>> {
1925    if txn.del_tree(file_id, Some(inode))? {
1926        if !file_id.basename.is_empty() {
1927            if !txn.del_revtree(inode, Some(file_id))? {
1928                panic!("del_tree_with_rev: {:?} {:?}", inode, file_id);
1929            }
1930        }
1931        Ok(true)
1932    } else {
1933        Ok(false)
1934    }
1935}
1936
1937pub fn del_graph_with_rev<T: GraphMutTxnT>(
1938    txn: &mut T,
1939    graph: &mut T::Graph,
1940    mut flag: EdgeFlags,
1941    mut k0: Vertex<ChangeId>,
1942    mut k1: Vertex<ChangeId>,
1943    introduced_by: ChangeId,
1944) -> Result<bool, TxnErr<T::GraphError>> {
1945    if flag.contains(EdgeFlags::PARENT) {
1946        std::mem::swap(&mut k0, &mut k1);
1947        flag -= EdgeFlags::PARENT
1948    }
1949    debug!("del_graph_with_rev {:?} {:?} {:?}", flag, k0, k1);
1950    let v0 = SerializedEdge::new(flag, k1.change, k1.start, introduced_by);
1951    let a = txn.del_graph(graph, &k0, Some(&v0))?;
1952    let v1 = SerializedEdge::new(flag | EdgeFlags::PARENT, k0.change, k0.end, introduced_by);
1953    let b = txn.del_graph(graph, &k1, Some(&v1))?;
1954    Ok(a && b)
1955}
1956
1957pub fn put_graph_with_rev<T: GraphMutTxnT>(
1958    txn: &mut T,
1959    graph: &mut T::Graph,
1960    flag: EdgeFlags,
1961    k0: Vertex<ChangeId>,
1962    k1: Vertex<ChangeId>,
1963    introduced_by: ChangeId,
1964) -> Result<bool, TxnErr<T::GraphError>> {
1965    debug_assert!(!flag.contains(EdgeFlags::PARENT));
1966    if k0.change == k1.change {
1967        assert_ne!(k0.start_pos(), k1.start_pos());
1968    }
1969    if introduced_by == ChangeId::ROOT {
1970        assert!(flag.contains(EdgeFlags::PSEUDO));
1971    }
1972
1973    debug!("put_graph_with_rev {:?} {:?} {:?}", k0, k1, flag);
1974    let a = txn.put_graph(
1975        graph,
1976        &k0,
1977        &SerializedEdge::new(flag, k1.change, k1.start, introduced_by),
1978    )?;
1979    let b = txn.put_graph(
1980        graph,
1981        &k1,
1982        &SerializedEdge::new(flag | EdgeFlags::PARENT, k0.change, k0.end, introduced_by),
1983    )?;
1984    assert!(!(a ^ b));
1985
1986    Ok(a && b)
1987}
1988
1989pub(crate) fn register_change<
1990    T: GraphMutTxnT + DepsMutTxnT<DepsError = <T as GraphTxnT>::GraphError>,
1991>(
1992    txn: &mut T,
1993    internal: &ChangeId,
1994    hash: &Hash,
1995    change: &Change,
1996) -> Result<(), TxnErr<T::GraphError>> {
1997    debug!("registering change {:?}", hash);
1998    let shash = hash.into();
1999    txn.put_external(internal, &shash)?;
2000    txn.put_internal(&shash, internal)?;
2001    for dep in change.dependencies.iter() {
2002        debug!("dep = {:?}", dep);
2003        let dep_internal = *txn.get_internal(&dep.into())?.unwrap();
2004        debug!("{:?} depends on {:?}", internal, dep_internal);
2005        txn.put_revdep(&dep_internal, internal)?;
2006        txn.put_dep(internal, &dep_internal)?;
2007    }
2008    for hunk in change.changes.iter().flat_map(|r| r.iter()) {
2009        let (inode, pos) = match *hunk {
2010            Atom::NewVertex(NewVertex {
2011                ref inode,
2012                ref flag,
2013                ref start,
2014                ref end,
2015                ..
2016            }) => {
2017                if flag.contains(EdgeFlags::FOLDER) && start == end {
2018                    (inode, Some(*start))
2019                } else {
2020                    (inode, None)
2021                }
2022            }
2023            Atom::EdgeMap(EdgeMap { ref inode, .. }) => (inode, None),
2024        };
2025        let change = if let Some(c) = inode.change {
2026            txn.get_internal(&c.into())?.unwrap_or(internal)
2027        } else {
2028            internal
2029        };
2030        let inode = Position {
2031            change: *change,
2032            pos: inode.pos,
2033        };
2034        debug!("touched: {:?} {:?}", inode, internal);
2035        txn.put_touched_files(&inode, internal)?;
2036        txn.put_rev_touched_files(internal, &inode)?;
2037        if let Some(pos) = pos {
2038            let inode = Position {
2039                change: *internal,
2040                pos,
2041            };
2042            txn.put_touched_files(&inode, internal)?;
2043            txn.put_rev_touched_files(internal, &inode)?;
2044        }
2045    }
2046    Ok(())
2047}
2048
2049fn first_state_after<T: ChannelTxnT>(
2050    txn: &T,
2051    c: &T::Channel,
2052    pos: u64,
2053) -> Result<Option<(u64, SerializedMerkle)>, TxnErr<T::GraphError>> {
2054    for x in T::cursor_revchangeset_ref(txn, txn.rev_changes(c), Some(pos.into()))? {
2055        let (&n, m) = x?;
2056        let n: u64 = n.into();
2057        if n >= pos {
2058            return Ok(Some((n, m.b)));
2059        }
2060    }
2061    Ok(None)
2062}
2063
2064fn last_state<T: ChannelTxnT>(
2065    txn: &T,
2066    c: &T::Channel,
2067) -> Result<Option<(u64, SerializedMerkle)>, TxnErr<T::GraphError>> {
2068    match txn
2069        .rev_cursor_revchangeset(txn.rev_changes(c), None)?
2070        .next()
2071    {
2072        Some(e) => {
2073            let (&b, state) = e?;
2074            let b: u64 = b.into();
2075            Ok(Some((b, state.b)))
2076        }
2077        _ => Ok(None),
2078    }
2079}
2080
2081/// Find the last state of c1 that is also in c0.
2082pub fn last_common_state<T: ChannelTxnT>(
2083    txn: &T,
2084    c0: &T::Channel,
2085    c1: &T::Channel,
2086) -> Result<(u64, u64, SerializedMerkle), TxnErr<T::GraphError>> {
2087    let mut a = 0;
2088    let (mut b, mut state) = if let Some(x) = last_state(txn, c1)? {
2089        x
2090    } else {
2091        return Ok((0, 0, Merkle::zero().into()));
2092    };
2093    if let Some(aa) = txn.channel_has_state(txn.states(c0), &state)? {
2094        return Ok((aa.into(), b, state));
2095    }
2096    let mut aa = 0;
2097    let mut a_was_found = false;
2098    while a < b {
2099        let mid = (a + b) / 2;
2100        let (_, s) = first_state_after(txn, c1, mid)?.unwrap();
2101        state = s;
2102        if let Some(aa_) = txn.channel_has_state(txn.states(c0), &state)? {
2103            aa = aa_.into();
2104            a_was_found = true;
2105            if a == mid {
2106                break;
2107            } else {
2108                a = mid
2109            }
2110        } else {
2111            b = mid
2112        }
2113    }
2114    if a_was_found {
2115        Ok((aa, a, state))
2116    } else {
2117        Ok((0, 0, Merkle::zero().into()))
2118    }
2119}
2120
2121/// Check that each inode in the inodes table maps to an alive vertex,
2122/// and that each inode in the tree table is reachable by only one
2123/// path.
2124pub fn check_tree_inodes<T: GraphTxnT + TreeTxnT>(txn: &T, channel: &T::Graph) {
2125    // Sanity check
2126    for x in txn.iter_inodes().unwrap() {
2127        let (inode, vertex) = x.unwrap();
2128        let mut inode_ = *inode;
2129        while !inode_.is_root() {
2130            if let Some(next) = txn.get_revtree(&inode_, None).unwrap() {
2131                inode_ = next.parent_inode;
2132            } else {
2133                panic!("inode = {:?}, inode_ = {:?}", inode, inode_);
2134            }
2135        }
2136        if !is_alive(txn, channel, &vertex.inode_vertex()).unwrap() {
2137            for e in iter_adj_all(txn, channel, vertex.inode_vertex()).unwrap() {
2138                error!("{:?} {:?} {:?}", inode, vertex, e.unwrap())
2139            }
2140            panic!(
2141                "inode {:?}, vertex {:?}, is not alive, {:?}",
2142                inode,
2143                vertex,
2144                tree_path(txn, vertex)
2145            )
2146        }
2147    }
2148    let mut h = HashMap::default();
2149    let id0 = OwnedPathId {
2150        parent_inode: Inode::ROOT,
2151        basename: crate::small_string::SmallString::new(),
2152    };
2153    for x in txn.iter_tree(&id0, None).unwrap() {
2154        let (id, inode) = x.unwrap();
2155        if let Some(inode_) = h.insert(id.to_owned(), inode) {
2156            panic!("id {:?} maps to two inodes: {:?} {:?}", id, inode, inode_);
2157        }
2158    }
2159}
2160
2161/// Check that each alive vertex in the graph is reachable, and vice-versa.
2162pub fn check_alive_debug<T: GraphIter + ChannelTxnT, C: crate::changestore::ChangeStore>(
2163    changes: &C,
2164    txn: &T,
2165    channel: &T::Channel,
2166    line: u32,
2167) -> Result<(), std::io::Error> {
2168    let (alive, reachable) = crate::pristine::check_alive(txn, txn.graph(channel));
2169    let mut h = HashSet::default();
2170    if !alive.is_empty() {
2171        for (k, file) in alive.iter() {
2172            debug!("alive = {:?}, file = {:?}", k, file);
2173            h.insert(file);
2174        }
2175    }
2176    if !reachable.is_empty() {
2177        for (k, file) in reachable.iter() {
2178            debug!("reachable = {:?}, file = {:?}", k, file);
2179            h.insert(file);
2180        }
2181    }
2182    for file in h.iter() {
2183        let file_ = file.unwrap().start_pos();
2184
2185        let path = crate::fs::find_path(changes, txn, channel, true, file_)
2186            .unwrap()
2187            .unwrap();
2188        let path = path.path.join("_");
2189        let name = format!(
2190            "debug_{:?}_{}_{}",
2191            path,
2192            file_.change.to_base32(),
2193            file_.pos.0
2194        );
2195        let mut f = std::fs::File::create(&name)?;
2196        let graph = crate::alive::retrieve::retrieve(txn, txn.graph(channel), file_, true).unwrap();
2197        graph.debug(changes, txn, txn.graph(channel), false, false, &mut f)?;
2198
2199        let mut f = std::fs::File::create(format!("{}_all", name))?;
2200        debug_root(txn, txn.graph(channel), file.unwrap(), &mut f, true)?;
2201    }
2202    if !h.is_empty() {
2203        if !alive.is_empty() {
2204            panic!("alive call line {}: {:?}", line, alive);
2205        } else {
2206            panic!("reachable: {:?}", reachable);
2207        }
2208    }
2209    Ok(())
2210}
pijul_core/pristine/mod.rs

pijul_core/pristine/
mod.rs
