pijul_org / pijul

Getting rid of error chain (because of Tokio issues)

By blabla on October 2, 2018
This patch is not signed.
8M8raKtuUe4LEuHj179y12BsmcLs71zkcingTsaydRYZoqQc6T8qrWeQFnnjjmXqXnvBk3VoNWMwD7QoWVNAYLoM
This patch is in the following branches:
latest
master
testing
58
59

hex = "0.3"
tempdir = "0.3"
error-chain = "0.12"

1
2
3
4
5
6



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

146
147
                Error::BranchNameAlreadyExists(new_name.to_string()),
use hex;
use rand;
use sanakirja;
use sanakirja::Representable;
pub use sanakirja::Transaction;
use std;
use {ErrorKind, Result};
use {ErrorKind, Result};
use {ErrorKind, Result};
use std::path::Path;
use {Error, Result};

pub use self::patch_id::*;

fn from_hex(hex: &str, s: &mut [u8]) -> bool {
    let hex = hex.as_bytes();
    if hex.len() <= 2 * s.len() {
        let mut i = 0;
        while i < hex.len() {
            let h = hex[i].to_ascii_lowercase();
            if h >= b'0' && h <= b'9' {
                s[i / 2] = s[i / 2] << 4 | (h - b'0')
            } else if h >= b'a' && h <= b'f' {
                s[i / 2] = s[i / 2] << 4 | (h - b'a' + 10)
            } else {
                return false;
            }
            i += 1
        }
        if i & 1 == 1 {
            s[i / 2] = s[i / 2] << 4
        }
        true
    } else {
        false
    }
}
mod edge;
mod file_header;
mod file_id;
mod hash;
mod inode;
mod key;
mod patch_id;
mod small_string;

pub use self::edge::*;
pub use self::file_header::*;
pub use self::file_id::*;
pub use self::hash::*;
pub use self::inode::*;
pub use self::key::*;
pub use self::small_string::*;

pub type NodesDb = sanakirja::Db<self::key::Key<PatchId>, self::edge::Edge>;

/// The type of patch application numbers.
pub type ApplyTimestamp = u64;

/// The u64 is the epoch time in seconds when this patch was applied
/// to the repository.
type PatchSet = sanakirja::Db<self::patch_id::PatchId, ApplyTimestamp>;

type RevPatchSet = sanakirja::Db<ApplyTimestamp, self::patch_id::PatchId>;

pub struct Dbs {
    /// A map of the files in the working copy.
    tree: sanakirja::Db<self::file_id::UnsafeFileId, self::inode::Inode>,
    /// The reverse of tree.
    revtree: sanakirja::Db<self::inode::Inode, self::file_id::UnsafeFileId>,
    /// A map from inodes (in tree) to keys in branches.
    inodes: sanakirja::Db<self::inode::Inode, self::file_header::FileHeader>,
    /// The reverse of inodes, minus the header.
    revinodes: sanakirja::Db<self::key::Key<PatchId>, self::inode::Inode>,
    /// Text contents of keys.
    contents: sanakirja::Db<self::key::Key<PatchId>, sanakirja::value::UnsafeValue>,
    /// A map from external patch hashes to internal ids.
    internal: sanakirja::Db<self::hash::UnsafeHash, self::patch_id::PatchId>,
    /// The reverse of internal.
    external: sanakirja::Db<self::patch_id::PatchId, self::hash::UnsafeHash>,
    /// A reverse map of patch dependencies, i.e. (k,v) is in this map
    /// means that v depends on k.
    revdep: sanakirja::Db<self::patch_id::PatchId, self::patch_id::PatchId>,
    /// A map from branch names to graphs.
    branches:
        sanakirja::Db<self::small_string::UnsafeSmallStr, (NodesDb, PatchSet, RevPatchSet, u64)>,
    /// A map of edges to patches that remove them.
    cemetery: sanakirja::Db<(self::key::Key<PatchId>, self::edge::Edge), self::patch_id::PatchId>,
    /// Dependencies
    dep: sanakirja::Db<self::patch_id::PatchId, self::patch_id::PatchId>,
    /// Files touched by patches.
    touched_files: sanakirja::Db<self::key::Key<PatchId>, self::patch_id::PatchId>,
    /// Partial checkouts: branch -> partial
    partials: sanakirja::Db<self::small_string::UnsafeSmallStr, self::key::Key<PatchId>>,
}

/// Common type for both mutable transactions (`MutTxn`) and immutable
/// transaction (`Txn`). All of `Txn`'s methods are also `MutTxn`'s
/// methods.
pub struct GenericTxn<T, R> {
    #[doc(hidden)]
    pub txn: T,
    #[doc(hidden)]
    pub rng: R,
    #[doc(hidden)]
    pub dbs: Dbs,
}

/// A mutable transaction on a repository.
pub type MutTxn<'env, R> = GenericTxn<sanakirja::MutTxn<'env, ()>, R>;
/// An immutable transaction on a repository.
pub type Txn<'env> = GenericTxn<sanakirja::Txn<'env>, ()>;

/// The default name of a branch, for users who start working before
/// choosing branch names (or like the default name, "master").
pub const DEFAULT_BRANCH: &'static str = "master";

/// A repository. All operations on repositories must be done via transactions.
pub struct Repository {
    pub env: sanakirja::Env,
}

#[derive(Debug, PartialEq, Clone, Copy)]
pub enum Root {
    Tree,
    RevTree,
    Inodes,
    RevInodes,
    Contents,
    Internal,
    External,
    RevDep,
    Branches,
    Cemetery,
    TouchedFiles,
    Dep,
    RevTouchedFiles,
    Partials,
}

trait OpenDb: Transaction {
    fn open_db<K: Representable, V: Representable>(
        &mut self,
        num: Root,
    ) -> Result<sanakirja::Db<K, V>> {
        if let Some(db) = self.root(num as usize) {
            Ok(db)
        } else {
            Err(ErrorKind::NoDb(num).into())
            Err(Error::NoDb(num))
        }

1
2
3
4
5
6

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378

379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444

445
446
        Err(Error::FileNotInRepo(path.to_path_buf()))
//! Manipulating the internal representation of files and directories
//! tracked by Pijul (i.e. adding files, removing files, getting file
//! names…).

use backend;
use backend::*;
use {ErrorKind, Result};
use {Error, Result};
use fs_representation::{RepoPath, in_repo_root};

use rand;
use std;
use std::collections::BTreeMap;
use std::iter::Iterator;
use std::path::{Path, PathBuf};

impl<'env, R: rand::Rng> MutTxn<'env, R> {
    pub fn mark_inode_moved(&mut self, inode: Inode) {
        let mut header = None;
        if let Some(h) = self.get_inodes(inode) {
            header = Some(h.clone())
        }
        if let Some(mut h) = header {
            h.status = FileStatus::Moved;
            self.replace_inodes(inode, h).unwrap();
        }
    }

    /// Create an inode that doesn't exist in the repository, but
    /// doesn't put it into the repository.
    pub fn create_new_inode(&self) -> Inode {
        let mut already_taken = true;
        let mut inode: Inode = ROOT_INODE.clone();
        while already_taken {
            for i in inode.iter_mut() {
                *i = rand::random()
            }
            already_taken = self.get_revtree(inode).is_some();
        }
        inode
    }

    /// Record the information that `parent_inode` is now a parent of
    /// file `filename`, and `filename` has inode `child_inode`.
    fn make_new_child(
        &mut self,
        parent_inode: Inode,
        filename: &str,
        is_dir: bool,
        child_inode: Option<Inode>,
    ) -> Result<Inode> {
        let parent_id = OwnedFileId {
            parent_inode: parent_inode.clone(),
            basename: SmallString::from_str(filename),
        };
        if filename == ".pijul" {
            return Err(Error::CannotAddDotPijul);
        }
        if let Some(inode) = self.get_tree(&parent_id.as_file_id()) {
            // If we already have the file, make sure the file status
            // is Ok (i.e. not zombie, not deleted).
            let mut header = if let Some(header) = self.get_inodes(inode) {
                header.to_owned()
            } else {
                return Err(ErrorKind::AlreadyAdded.into());
                return Err(Error::AlreadyAdded);
            };
            if let FileStatus::Ok = header.status {
            } else {
                header.status = FileStatus::Ok;
                self.replace_inodes(inode, header)?;
            }
            Ok(inode)
        } else {
            // Else, add a new file.

            let child_inode = match child_inode {
                None => self.create_new_inode(),
                Some(i) => i.clone(),
            };
            self.put_tree(&parent_id.as_file_id(), child_inode)?;
            self.put_revtree(child_inode, &parent_id.as_file_id())?;

            if is_dir {
                // If this new file is a directory, add a name-less
                // file id without a reverse in revtree.
                let dir_id = OwnedFileId {
                    parent_inode: child_inode.clone(),
                    basename: SmallString::from_str(""),
                };
                self.put_tree(&dir_id.as_file_id(), child_inode)?;
            };
            Ok(child_inode)
        }
    }

    pub fn add_inode<P: AsRef<Path>>(
        &mut self,
        inode: Option<Inode>,
        path: &RepoPath<P>,
        is_dir: bool,
    ) -> Result<()> {
        if let Some(parent) = path.parent() {
            let (mut current_inode, unrecorded_path) =
                self.closest_in_repo_ancestor(&parent).unwrap();

            for c in unrecorded_path {
                current_inode =
                    self.make_new_child(current_inode, c.as_os_str().to_str().unwrap(), true, None)?
            }

            self.make_new_child(
                current_inode,
                path.file_name().unwrap().to_str().unwrap(),
                is_dir,
                inode,
            )?;
        }
        Ok(())
    }

    pub fn inode_is_ancestor_of(&self, a: Inode, mut b: Inode) -> bool {
        loop {
            if a == b {
                return true;
            }
            if let Some(b_parent) = self.get_revtree(b) {
                b = b_parent.parent_inode
            } else {
                return false;
            }
        }
    }

    pub fn move_file(
        &mut self,
        origin: &RepoPath<impl AsRef<Path>>,
        destination: &RepoPath<impl AsRef<Path>>,
        is_dir: bool,
    ) -> Result<()> {
        debug!("move_file: {},{}", origin.display(), destination.display());
        if let Some(parent) = origin.parent() {
            let fileref = OwnedFileId {
                parent_inode: self.find_inode(&parent)?,
                basename: SmallString::from_str(origin.file_name().unwrap().to_str().unwrap()),
            };

            if let Some(inode) = self.get_tree(&fileref.as_file_id()).map(|i| i.clone()) {
                // Now the last inode is in "*inode"
                debug!("txn.del fileref={:?}", fileref);
                self.del_tree(&fileref.as_file_id(), None)?;
                self.del_revtree(inode, None)?;

                debug!("inode={} destination={}", inode.to_hex(), destination.display());
                self.add_inode(Some(inode), destination, is_dir)?;
                self.mark_inode_moved(inode);

                return Ok(());
            }
        }
        Err(ErrorKind::FileNotInRepo(path.to_path_buf()).into())
        Err(Error::FileNotInRepo(origin.to_path_buf()))
    }

    // Deletes a directory, given by its inode, recursively.
    pub fn rec_delete(&mut self, key: Inode) -> Result<bool> {
        debug!("rec_delete, key={:?}", key.to_hex());
        let file_id = OwnedFileId {
            parent_inode: key.clone(),
            basename: SmallString::from_str(""),
        };

        let children: Vec<(_, Inode)> = self
            .iter_tree(Some((&file_id.as_file_id(), None)))
            .take_while(|&(ref k, _)| key == k.parent_inode)
            .filter(|&(ref k, _)| !k.basename.is_empty())
            .map(|(k, v)| (k.to_owned(), v.to_owned()))
            .collect();

        let mut has_recorded_descendants = false;
        for (_, b) in children {
            debug!("deleting from tree {:?}", b);
            has_recorded_descendants |= self.rec_delete(b)?;
        }

        // Now that the directory is empty, mark the corresponding node as deleted (flag '2').
        if let Some(mut header) = self.get_inodes(key).map(|h| h.clone()) {
            // If this is was recorded, mark deleted.
            debug!("key {:?}, header = {:?}", key, header);
            header.status = FileStatus::Deleted;
            self.replace_inodes(key, header)?;
            debug!("after = {:?}", self.get_inodes(key).map(|h| h.clone()));
        } else if !has_recorded_descendants {
            // Else, simply delete from the tree.
            let parent = self.get_revtree(key).unwrap().to_owned();
            debug!("key = {:?}, parent = {:?}", key, parent);
            self.del_tree(&parent.as_file_id(), None)?;
            self.del_revtree(key, None)?;
        }
        Ok(has_recorded_descendants)
    }

    /// Removes a file from the repository.
    pub fn remove_file(&mut self, path: &RepoPath<impl AsRef<Path>>)
                       -> Result<()> {
        debug!("remove_file");
        let inode = self.find_inode(path)?;
        debug!("rec_delete");
        self.rec_delete(inode)?;
        debug!("/rec_delete");
        Ok(())
    }
}

impl<A: Transaction, R> backend::GenericTxn<A, R> {
    /// Traverses the `tree` base recursively, collecting all descendants of `key`.
    fn collect(
        &self,
        key: Inode,
        current_path: &RepoPath<impl AsRef<Path>>,
        basename: &str,
        files: &mut Vec<RepoPath<PathBuf>>,
    ) -> Result<()> {
        debug!("collecting {:?},{:?}", key, basename);
        let add = match self.get_inodes(key) {
            Some(inode) => {
                debug!("node = {:?}", inode);
                inode.status != FileStatus::Deleted
            }
            None => true,
        };
        if add {
            debug!("basename = {:?}", basename);
            
            let next_pb = current_path.join(Path::new(basename));
            if basename.len() > 0 {
                files.push(next_pb.clone())
            }

            debug!("starting iterator, key={:?}", key);
            let fileid = OwnedFileId {
                parent_inode: key.clone(),
                basename: SmallString::from_str(""),
            };
            for (k, v) in self
                .iter_tree(Some((&fileid.as_file_id(), None)))
                .take_while(|&(ref k, _)| k.parent_inode == key)
            {
                debug!("iter: {:?} {:?}", k, v);
                if k.basename.len() > 0 {
                    self.collect(v.to_owned(), &next_pb, k.basename.as_str(), files)?;
                }
            }
            debug!("ending iterator {:?}", {
                let v: Vec<_> = self.iter_tree(Some((&fileid.as_file_id(), None))).collect();
                v
            });
        }
        Ok(())
    }

    /// Returns a vector containing all files in the repository.
    pub fn list_files(&self, inode: Inode) -> Result<Vec<RepoPath<PathBuf>>> {
        debug!("list_files {:?}", inode);
        let mut files = Vec::new();
        self.collect(inode, &in_repo_root(), "", &mut files)?;
        Ok(files)
    }

    /// Returns a list of files under the given inode.
    pub fn list_files_under_inode(
        &self,
        inode: Inode,
    ) -> Vec<(SmallString, Option<Key<PatchId>>, Inode)> {
        let mut result = Vec::new();

        let file_id = OwnedFileId {
            parent_inode: inode,
            basename: SmallString::from_str(""),
        };
        for (k, v) in self
            .iter_tree(Some((&file_id.as_file_id(), None)))
            .take_while(|&(ref k, _)| k.parent_inode == inode)
        {
            let header = self.get_inodes(k.parent_inode).map(|x| x.clone());
            // add: checking that this file has neither been moved nor deleted.
            println!("============= {:?} {:?}", k, v);
            let add = match header {
                Some(ref h) => h.status == FileStatus::Ok,
                None => true,
            };
            if add && k.basename.len() > 0 {
                result.push((
                    k.basename.to_owned(),
                    header.map(|h| h.key.clone()),
                    v.clone(),
                ))
            }
        }

        result
    }

    /// Returns a list of files under the given inode.
    pub fn list_files_under_node(
        &self,
        branch: &Branch,
        key: Key<PatchId>,
    ) -> BTreeMap<Key<PatchId>, Vec<(FileMetadata, &str)>> {
        let mut result = BTreeMap::new();

        let e = Edge::zero(EdgeFlags::FOLDER_EDGE);
        for (_, child) in self
            .iter_nodes(branch, Some((key, Some(e))))
            .take_while(|&(k, ref v)| {
                k == key && v.flag <= EdgeFlags::FOLDER_EDGE | EdgeFlags::PSEUDO_EDGE
            })
        {
            let name = self.get_contents(child.dest).unwrap();
            // This is supposed to be a small string anyway.
            let (perms, basename) = name.as_slice().split_at(2);
            let perms = FileMetadata::from_contents(perms);
            let basename = std::str::from_utf8(basename).unwrap();

            for (_, grandchild) in self
                .iter_nodes(branch, Some((child.dest, Some(e))))
                .take_while(|&(k, ref v)| {
                    k == child.dest && v.flag <= EdgeFlags::FOLDER_EDGE | EdgeFlags::PSEUDO_EDGE
                })
            {
                let names = result.entry(grandchild.dest.to_owned()).or_insert(vec![]);
                names.push((perms, basename))
            }
        }
        result
    }

    pub fn is_directory(&self, inode: &Inode) -> bool {
        let file_id = OwnedFileId {
            parent_inode: inode.clone(),
            basename: SmallString::from_str(""),
        };
        inode == &ROOT_INODE || self.get_tree(&file_id.as_file_id()).is_some()
    }

    /// Splits a path into (1) the deepest inode from the root that is
    /// an ancestor of the path or the path itself and (2) the
    /// remainder of this path
    fn closest_in_repo_ancestor<'a>(
        &self,
        path: &'a RepoPath<impl AsRef<Path>>
    ) -> Result<(Inode, std::iter::Peekable<std::path::Components<'a>>)> {
        let mut components = path.components().peekable();
        let mut fileid = OwnedFileId {
            parent_inode: ROOT_INODE,
            basename: SmallString::from_str(""),
        };

        loop {
            if let Some(c) = components.peek() {
                fileid.basename = SmallString::from_str(c.as_os_str().to_str().unwrap());
                if let Some(v) = self.get_tree(&fileid.as_file_id()) {
                    fileid.parent_inode = v.clone()
                } else {
                    break;
                }
            } else {
                break;
            }
            components.next();
        }
        Ok((fileid.parent_inode.clone(), components))
    }

    /// Find the inode corresponding to that path, or return an error if there's no such inode.
    pub fn find_inode(&self, path: &RepoPath<impl AsRef<Path>>)
                      -> Result<Inode> {
        let (inode, mut remaining_path_components) = self.closest_in_repo_ancestor(path)?;
        if remaining_path_components.next().is_none() {
            Ok(inode)
        } else {
            Err(ErrorKind::FileNotInRepo(path.to_path_buf()).into())
            Err(Error::FileNotInRepo(path.to_path_buf()))
        }
    }

    pub fn file_names(
        &self,
        branch: &Branch,
        key: Key<PatchId>,
    ) -> Vec<(Key<PatchId>, FileMetadata, &str)> {
        let mut result = Vec::new();
        let e = Edge::zero(EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE);

        debug!("file_names, key {:?}", key);
        for (_, parent) in self
            .iter_nodes(branch, Some((key, Some(e))))
            .take_while(|&(k, _)| k == key)
            .filter(|&(_, ref v)| {
                v.flag
                    .contains(EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE)
            })
        {
            debug!("file_names, parent {:?}", parent);
            match self.get_contents(parent.dest) {
                Some(ref name) if name.len() >= 2 => {
                    // This is supposed to be a small string anyway.
                    let (perms, basename) = name.as_slice().split_at(2);
                    let perms = FileMetadata::from_contents(perms);
                    let basename = std::str::from_utf8(basename).unwrap();

                    for (_, grandparent) in self
                        .iter_nodes(branch, Some((parent.dest, Some(e))))
                        .take_while(|&(k, _)| k == parent.dest)
                        .filter(|&(_, ref v)| {
                            v.flag
                                .contains(EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE)
                        })
                    {
                        result.push((grandparent.dest.to_owned(), perms, basename));
                        break;
                    }
                }
                _ => error!("Key: {:?}, file {}, line {}", key, file!(), line!()),
            }
        }
        result
    }

    pub fn prefix_keys(&self, branch: &Branch, path: &RepoPath<impl AsRef<Path>>)
                       -> Result<Vec<Key<PatchId>>> {
        let mut result = Vec::new();
        let e = Edge::zero(EdgeFlags::FOLDER_EDGE);

        let mut current_key = ROOT_KEY;

        for comp in path.components() {
            let mut is_first = true;
            let cur = current_key;
            for (_, child) in self
                .iter_nodes(branch, Some((current_key, Some(e))))
                .take_while(|&(k, _)| k == cur)
                .filter(|&(_, ref v)| v.flag.contains(EdgeFlags::FOLDER_EDGE))
            {
                let contents = self.get_contents(child.dest).unwrap();
                if contents.into_cow().split_at(2).1
                    == comp.as_os_str().to_str().expect("file encoding problem").as_bytes() {
                    if !is_first {
                        return Err(ErrorKind::FileNameCount(current_key).into());
                        return Err(Error::FileNameCount(current_key));
                    }









1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60











61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
























97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206


207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235


238


241
242

244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295

296
297
    Keys(thrussh_keys::Error),
    }
}

impl std::convert::From<thrussh_keys::Error> for Error {
    fn from(e: thrussh_keys::Error) -> Self {
        Error::Keys(e)
        write!(fmt, "{:?}", self)
            Error::Keys(ref e) => e.description(),
//! This crate contains the core API to access Pijul repositories.
//!
//! The key object is a `Repository`, on which `Txn` (immutable
//! transactions) and `MutTxn` (mutable transactions) can be started,
//! to perform a variety of operations.
//!
//! Another important object is a `Patch`, which encodes two different pieces of information:
//!
//! - Information about deleted and inserted lines between two versions of a file.
//!
//! - Information about file moves, additions and deletions.
//!
//! The standard layout of a repository is defined in module
//! `fs_representation`, and mainly consists of a directory called
//! `.pijul` at the root of the repository, containing:
//!
//! - a directory called `pristine`, containing a Sanakirja database
//! storing most of the repository information.
//!
//! - a directory called `patches`, actually containing the patches,
//! where each patch is a gzipped compression of the bincode encoding
//! of the `patch::Patch` type.
//!
//! At the moment, users of this library, such as the Pijul
//! command-line tool, may use other files in the `.pijul` directory,
//! such as user preferences, or information about remote branches and
//! repositories.
#![recursion_limit = "128"]
#[macro_use]
extern crate bitflags;
extern crate chrono;
#[macro_use]
extern crate log;

extern crate base64;
extern crate bincode;
extern crate bs58;
extern crate byteorder;
#[macro_use]
extern crate error_chain;
extern crate flate2;
extern crate hex;
extern crate ignore;
extern crate openssl;
extern crate rand;
extern crate sanakirja;
extern crate serde;
#[macro_use]
extern crate serde_derive;
extern crate diffs;
extern crate failure;
extern crate sequoia_openpgp;
extern crate serde_json;
extern crate tempdir;
extern crate toml;

pub use sanakirja::Transaction;
use std::collections::HashSet;
use std::io::Write;
use std::path::Path;
use std::path::PathBuf;

error_chain! {
    foreign_links {
        IO(std::io::Error);
        Sanakirja(sanakirja::Error);
        Bincode(bincode::Error);
        Utf8(std::str::Utf8Error);
        Serde(serde_json::Error);
        OpenSSL(openssl::error::Error);
        OpenSSLStack(openssl::error::ErrorStack);
        Keys(thrussh_keys::Error);
        Base58Decode(bs58::decode::DecodeError);
#[derive(Debug)]
pub enum Error {
    IO(std::io::Error),
    Sanakirja(sanakirja::Error),
    Bincode(bincode::Error),
    Utf8(std::str::Utf8Error),
    Serde(serde_json::Error),
    OpenSSL(openssl::error::Error),
    OpenSSLStack(openssl::error::ErrorStack),
    Base58Decode(bs58::decode::DecodeError),
    Failure(failure::Error),
    AlreadyAdded,
    FileNotInRepo(PathBuf),
    NoDb(backend::Root),
    WrongHash,
    EOF,
    WrongPatchSignature,
    BranchNameAlreadyExists(String),
    WrongFileHeader(Key<PatchId>),
    FileNameCount(Key<PatchId>),
    MissingDependency(Hash),
    PatchNotOnBranch(PatchId),
    CannotAddDotPijul,
    KeyIsEncrypted,
}

impl std::convert::From<std::io::Error> for Error {
    fn from(e: std::io::Error) -> Self {
        Error::IO(e)
    }
}

impl std::convert::From<failure::Error> for Error {
    fn from(e: failure::Error) -> Self {
        Error::Failure(e)
    }
    errors {
        AlreadyAdded {}
        FileNotInRepo(path: PathBuf) {
            description("File not tracked")
                display("File {:?} not tracked", path.display())
        }
        NoDb(root: backend::Root) {}
        WrongHash {}
        EOF {}
        WrongPatchSignature {
            description("Wrong patch signature")
                display("Wrong patch signature")
        }
        BranchNameAlreadyExists(name: String) {
            description("Branch name already exists")
                display("Branch name {:?} already exists", name)
        }
        WrongFileHeader(node: Key<PatchId>) {
            description("Wrong file header (possible branch corruption)")
                display("Wrong file header (possible branch corruption): {:?}", node)
        }
        FileNameCount(node: Key<PatchId>) {
            description("A file name doesn't have exactly one child")
                display("A file name doesn't have exactly one child: {:?}", node)
}

impl std::convert::From<sanakirja::Error> for Error {
    fn from(e: sanakirja::Error) -> Self {
        Error::Sanakirja(e)
    }
}

impl std::convert::From<bincode::Error> for Error {
    fn from(e: bincode::Error) -> Self {
        Error::Bincode(e)
    }
}

impl std::convert::From<serde_json::Error> for Error {
    fn from(e: serde_json::Error) -> Self {
        Error::Serde(e)
    }
}

impl std::convert::From<std::str::Utf8Error> for Error {
    fn from(e: std::str::Utf8Error) -> Self {
        Error::Utf8(e)
    }
}

impl std::convert::From<openssl::error::ErrorStack> for Error {
    fn from(e: openssl::error::ErrorStack) -> Self {
        Error::OpenSSLStack(e)
    }
}

impl std::convert::From<bs58::decode::DecodeError> for Error {
    fn from(e: bs58::decode::DecodeError) -> Self {
        Error::Base58Decode(e)
    }
}

pub type Result<A> = std::result::Result<A, Error>;

impl std::fmt::Display for Error {
    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
        match *self {
            Error::IO(ref e) => e.fmt(fmt),
            Error::Sanakirja(ref e) => e.fmt(fmt),
            Error::Bincode(ref e) => e.fmt(fmt),
            Error::Utf8(ref e) => e.fmt(fmt),
            Error::Serde(ref e) => e.fmt(fmt),
            Error::OpenSSL(ref e) => e.fmt(fmt),
            Error::OpenSSLStack(ref e) => e.fmt(fmt),
            Error::Base58Decode(ref e) => e.fmt(fmt),
            Error::Failure(ref e) => e.fmt(fmt),
            Error::AlreadyAdded => write!(fmt, "Already added"),
            Error::FileNotInRepo(ref file) => write!(fmt, "File {:?} not tracked", file),
            Error::NoDb(ref e) => write!(fmt, "Table missing: {:?}", e),
            Error::WrongHash => write!(fmt, "Wrong hash"),
            Error::EOF => write!(fmt, "EOF"),
            Error::WrongPatchSignature => write!(fmt, "Wrong patch signature"),
            Error::BranchNameAlreadyExists(ref name) => {
                write!(fmt, "Branch {:?} already exists", name)
            }
            Error::WrongFileHeader(ref h) => write!(
                fmt,
                "Wrong file header (possible branch corruption): {:?}",
                h
            ),
            Error::FileNameCount(ref f) => {
                write!(fmt, "Name {:?} doesn't have exactly one child", f)
            }
            Error::MissingDependency(ref f) => write!(fmt, "Missing dependency: {:?}", f),
            Error::PatchNotOnBranch(ref f) => {
                write!(fmt, "The patch is not on this branch {:?}", f)
            }
            Error::CannotAddDotPijul => write!(fmt, "Cannot add a file or directory name .pijul"),
            Error::KeyIsEncrypted => write!(fmt, "Key is encrypted"),
        }
    }
}

impl std::error::Error for Error {
    fn description(&self) -> &str {
        match *self {
            Error::IO(ref e) => e.description(),
            Error::Sanakirja(ref e) => e.description(),
            Error::Bincode(ref e) => e.description(),
            Error::Utf8(ref e) => e.description(),
            Error::Serde(ref e) => e.description(),
            Error::OpenSSL(ref e) => e.description(),
            Error::OpenSSLStack(ref e) => e.description(),
            Error::Base58Decode(ref e) => e.description(),
            Error::Failure(ref e) => e.name().unwrap_or("Unknown Failure"),
            Error::AlreadyAdded => "Already added",
            Error::FileNotInRepo(_) => "File not tracked",
            Error::NoDb(_) => "One of the tables is missing",
            Error::WrongHash => "Wrong hash",
            Error::EOF => "EOF",
            Error::WrongPatchSignature => "Wrong patch signature",
            Error::BranchNameAlreadyExists(_) => "Branch name already exists",
            Error::WrongFileHeader(_) => "Wrong file header (possible branch corruption)",
            Error::FileNameCount(_) => "A file name doesn't have exactly one child",
            Error::MissingDependency(_) => "Missing dependency",
            Error::PatchNotOnBranch(_) => "The patch is not on this branch",
            Error::CannotAddDotPijul => "Cannot add a file or directory name .pijul",
            Error::KeyIsEncrypted => "Key is encrypted",
        }
    }
}

impl Error {
    pub fn lacks_space(&self) -> bool {
        match self.0 {
            ErrorKind::Sanakirja(sanakirja::Error::NotEnoughSpace) => true,
        match *self {
            Error::Sanakirja(sanakirja::Error::NotEnoughSpace) => true,
            _ => false,
        }
    }
}

#[macro_use]
mod backend;
mod file_operations;
pub mod fs_representation;

pub mod patch;
pub mod status;

pub mod apply;
mod conflict;
mod diff;
pub mod graph;
mod output;
mod record;
mod unrecord;

pub use backend::{
    ApplyTimestamp, Branch, Edge, EdgeFlags, FileId, FileMetadata, FileStatus, GenericTxn, Hash,
    HashRef, Inode, Key, LineId, MutTxn, OwnedFileId, PatchId, Repository, SmallStr, SmallString,
    Txn, DEFAULT_BRANCH, ROOT_INODE, ROOT_KEY,
};


>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
use fs_representation::{RepoRoot, ID_LENGTH};

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

================================
pub use fs_representation::{RepoRoot, RepoPath};
use fs_representation::{ID_LENGTH};

<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
pub use output::{ConflictingFile, Prefixes, ToPrefixes};
pub use patch::{Patch, PatchHeader};
use rand::distributions::Alphanumeric;
use rand::Rng;
pub use record::{InodeUpdate, RecordState};
pub use sanakirja::value::Value;
use std::io::Read;

pub use diff::Algorithm as DiffAlgorithm;

impl<'env, T: rand::Rng> backend::MutTxn<'env, T> {
    pub fn output_changes_file<P: AsRef<Path>>(
        &mut self,
        branch: &Branch,
        fs_repo: &RepoRoot<P>,
    ) -> Result<()> {
        let changes_file = fs_repo.branch_changes_file(branch.name.as_str());
        let mut branch_id: Vec<u8> = vec![b'\n'; ID_LENGTH + 1];
        {
            if let Ok(mut file) = std::fs::File::open(&changes_file) {
                file.read_exact(&mut branch_id)?;
            }
        }
        let mut branch_id = if let Ok(s) = String::from_utf8(branch_id) {
            s
        } else {
            "\n".to_string()
        };
        if branch_id.as_bytes()[0] == b'\n' {
            branch_id.truncate(0);
            let mut rng = rand::thread_rng();
            branch_id.extend(rng.sample_iter(&Alphanumeric).take(ID_LENGTH));
            branch_id.push('\n');
        }

        let mut file = std::fs::File::create(&changes_file)?;
        file.write_all(&branch_id.as_bytes())?;
        for (s, hash) in self.iter_applied(&branch, None) {
            let hash_ext = self.get_external(hash).unwrap();
            writeln!(file, "{}:{}", hash_ext.to_base58(), s)?
        }
        Ok(())
    }

    pub fn branch_patches(&mut self, branch: &Branch) -> HashSet<(backend::Hash, ApplyTimestamp)> {
        self.iter_patches(branch, None)
            .map(|(patch, time)| (self.external_hash(patch).to_owned(), time))
            .collect()
    }

    pub fn fork(&mut self, branch: &Branch, new_name: &str) -> Result<Branch> {
        if branch.name.as_str() == new_name {
            Err(ErrorKind::BranchNameAlreadyExists(new_name.to_string()).into())
            Err(Error::BranchNameAlreadyExists(new_name.to_string()))
        } else {

1
2
3
4
5

6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106


107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

136
137
use {Error, Result};
use backend::*;
use graph;
use patch::*;
use rand;
use record::InodeUpdate;
use {ErrorKind, Result};
use std;
use std::borrow::Cow;
use std::collections::{HashMap, HashSet};
use std::fs;
use std::path::{Path, PathBuf};
use tempdir;
use {Error, Result};

use super::fs_representation::{RepoRoot, RepoPath, in_repo_root};

#[cfg(not(windows))]
use std::os::unix::fs::PermissionsExt;

#[cfg(not(windows))]
fn set_permissions(name: &Path, permissions: u16) -> Result<()> {
    let metadata = std::fs::metadata(&name)?;
    let mut current = metadata.permissions();
    debug!(
        "setting mode for {:?} to {:?} (currently {:?})",
        name, permissions, current
    );
    current.set_mode(permissions as u32);
    std::fs::set_permissions(name, current)?;
    Ok(())
}

#[cfg(windows)]
fn set_permissions(_name: &Path, _permissions: u16) -> Result<()> {
    Ok(())
}

#[derive(Debug)]
struct OutputItem {
    parent: Inode,
    meta: FileMetadata,
    key: Key<PatchId>,
    inode: Option<Inode>,
    is_zombie: bool,
    related: Related,
}

#[derive(Debug, PartialEq, Eq)]
pub enum Related {
    No,
    Ancestor,
    Exact,
}

pub struct ConflictingFile {
    pub inode: Inode,
    pub n_conflicts: usize,
    pub path: RepoPath<PathBuf>,
}

fn is_related(prefixes: &Prefixes, key: Key<PatchId>) -> Related {
    if prefixes.0.is_empty() {
        return Related::Exact;
    }
    for pref in prefixes.0.iter() {
        let mut is_first = true;
        for &p in pref {
            if p == key {
                if is_first {
                    return Related::Exact;
                } else {
                    return Related::Ancestor;
                }
            }
            is_first = false
        }
    }
    Related::No
}

impl<'env, T: rand::Rng> MutTxn<'env, T> {
    // Climb up the tree (using revtree).
    fn filename_of_inode(&self, inode: Inode, working_copy: &Path) -> Option<PathBuf> {
        let mut components = Vec::new();
        let mut current = inode;
        loop {
            match self.get_revtree(current) {
                Some(v) => {
                    components.push(v.basename.to_owned());
                    current = v.parent_inode.clone();
                    if current == ROOT_INODE {
                        break;
                    }
                }
                None => {
                    debug!("filename_of_inode: not in tree");
                    return None;
                }
            }
        }
        let mut working_copy = working_copy.to_path_buf();
        for c in components.iter().rev() {
            working_copy.push(c.as_small_str().as_str());
        }
        Some(working_copy)
    }

    
    
    /// Collect all the children of key `key` into `files`.
    fn collect_children(
        &mut self,
        branch: &Branch,
        path: RepoPath<&Path>,
        key: Key<PatchId>,
        inode: Inode,
        base_path: &RepoPath<impl AsRef<Path> + std::fmt::Debug>,
        prefixes: &Prefixes,
        files: &mut HashMap<RepoPath<PathBuf>, HashMap<Key<PatchId>, OutputItem>>,
    ) -> Result<()> {
        debug!("collect_children {:?}", base_path);
        let f = EdgeFlags::FOLDER_EDGE | EdgeFlags::PSEUDO_EDGE | EdgeFlags::EPSILON_EDGE;
        for b in self.iter_adjacent(&branch, key, EdgeFlags::empty(), f) {
            debug!("b={:?}", b);
            let cont_b = self.get_contents(b.dest).unwrap();
            let (_, b_key) = self
                .iter_nodes(
                    &branch,
                    Some((b.dest, Some(Edge::zero(EdgeFlags::FOLDER_EDGE)))),
                )
                .next()
                .unwrap();
            let b_inode = self.get_revinodes(b_key.dest);

            // This is supposed to be a small string, so we can do
            // as_slice.
            if cont_b.as_slice().len() < 2 {
                error!("cont_b {:?} b.dest {:?}", cont_b, b.dest);
                return Err(ErrorKind::WrongFileHeader(b.dest).into());
                return Err(Error::WrongFileHeader(b.dest));
            }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440

441
442
443

444
445
446
447
448

449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476

477
478
            return Err(Error::WrongPatchSignature);
//! Definition of patches, and a number of methods.
use chrono;
use chrono::{DateTime, Utc};
use flate2;
use std::collections::HashSet;
use std::fs::{File, OpenOptions};
use std::io::{BufRead, Read, Write};
use std::path::Path;
use std::path::PathBuf;
use std::rc::Rc;
use std::str::from_utf8;
pub type Flag = u8;
use bincode::{deserialize, deserialize_from, serialize};
use sequoia_openpgp::constants::DataFormat;
use sequoia_openpgp::crypto;
use sequoia_openpgp::serialize::stream::{LiteralWriter, Message, Signer};

use {Error, Result};
use super::fs_representation::RepoPath;

mod pretty;

bitflags! {
    #[derive(Serialize, Deserialize)]
    pub struct PatchFlags: u32 {
        const TAG = 1;
    }
}

/// A patch without its signature suffix.
#[derive(Debug, Serialize, Deserialize, Clone)]
pub struct UnsignedPatch {
    /// Header part, containing the metadata.
    pub header: PatchHeader,
    /// The dependencies of this patch.
    pub dependencies: HashSet<Hash>,
    /// The actual contents of the patch.
    pub changes: Vec<Change<ChangeContext<Hash>>>,
}

/// The definition of a patch.
#[derive(Debug, Serialize, Deserialize, Clone)]
pub enum Patch {
    Unsigned0,
    Signed0,
    Unsigned(UnsignedPatch),
}

impl Patch {
    /// The contents of this patch.
    pub fn changes(&self) -> &[Change<ChangeContext<Hash>>] {
        match *self {
            Patch::Signed0 | Patch::Unsigned0 => {
                panic!("refusing to interact with old patch version")
            }
            Patch::Unsigned(ref patch) => &patch.changes,
        }
    }

    pub fn changes_mut(&mut self) -> &mut Vec<Change<ChangeContext<Hash>>> {
        match *self {
            Patch::Signed0 | Patch::Unsigned0 => {
                panic!("refusing to interact with old patch version")
            }
            Patch::Unsigned(ref mut patch) => &mut patch.changes,
        }
    }
    /// The dependencies of this patch.
    pub fn dependencies(&self) -> &HashSet<Hash> {
        match *self {
            Patch::Signed0 | Patch::Unsigned0 => {
                panic!("refusing to interact with old patch version")
            }
            Patch::Unsigned(ref patch) => &patch.dependencies,
        }
    }
    pub fn dependencies_mut(&mut self) -> &mut HashSet<Hash> {
        match *self {
            Patch::Signed0 | Patch::Unsigned0 => {
                panic!("refusing to interact with old patch version")
            }
            Patch::Unsigned(ref mut patch) => &mut patch.dependencies,
        }
    }
    /// The header of this patch.
    pub fn header(&self) -> &PatchHeader {
        match *self {
            Patch::Signed0 | Patch::Unsigned0 => {
                panic!("refusing to interact with old patch version")
            }
            Patch::Unsigned(ref patch) => &patch.header,
        }
    }
    pub fn header_mut(&mut self) -> &mut PatchHeader {
        match *self {
            Patch::Signed0 | Patch::Unsigned0 => {
                panic!("refusing to interact with old patch version")
            }
            Patch::Unsigned(ref mut patch) => &mut patch.header,
        }
    }

    /// Reads everything in this patch, but the actual contents.
    pub fn read_dependencies<R: Read>(mut r: R) -> Result<Vec<Hash>> {
        let version: u32 = deserialize_from(&mut r)?;
        assert_eq!(version, 2);
        let _header: PatchHeader = deserialize_from(&mut r)?;
        debug!("version: {:?}", version);
        Ok(deserialize_from(&mut r)?)
    }
}

/// The header of a patch contains all the metadata about a patch
/// (but not the actual contents of a patch).
#[derive(Debug, Serialize, Deserialize, Clone)]
pub struct PatchHeader {
    pub authors: Vec<String>,
    pub name: String,
    pub description: Option<String>,
    pub timestamp: DateTime<Utc>,
    pub flag: PatchFlags,
}

use std::ops::{Deref, DerefMut};
impl Deref for Patch {
    type Target = PatchHeader;
    fn deref(&self) -> &Self::Target {
        self.header()
    }
}
impl DerefMut for Patch {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.header_mut()
    }
}

/// Options are for when this edge is between vertices introduced by
/// the current patch.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct NewEdge {
    pub from: Key<Option<Hash>>,
    pub to: Key<Option<Hash>>,
    pub introduced_by: Option<Hash>,
}

pub type ChangeContext<H> = Vec<Key<Option<H>>>;

#[derive(Debug, Clone, Serialize, Deserialize)]
pub enum Change<Context> {
    NewNodes {
        up_context: Context,
        down_context: Context,
        flag: EdgeFlags,
        line_num: LineId,
        nodes: Vec<Vec<u8>>,
        inode: Key<Option<Hash>>,
    },
    NewEdges {
        previous: EdgeFlags,
        flag: EdgeFlags,
        edges: Vec<NewEdge>,
        inode: Key<Option<Hash>>,
    },
}

impl PatchHeader {
    /// Reads everything in this patch, but the actual contents.
    pub fn from_reader_nochanges<R: Read>(mut r: R) -> Result<PatchHeader> {
        let version: u32 = deserialize_from(&mut r)?;
        debug!("version: {:?}", version);
        Ok(deserialize_from(&mut r)?)
    }
}

/// A record is a group of changes pertaining to a file or region of a
/// file.  They are going to be offered together, since displaying one
/// of the changes may be affected by the other (eg, if a file is
/// being moved, we need to display the correct name when asking about
/// modifications within that file).
#[derive(Debug)]
pub enum Record<Context> {
    FileMove {
        new_name: RepoPath<PathBuf>,
        del: Change<Context>,
        add: Change<Context>,
    },
    FileDel {
        name: RepoPath<PathBuf>,
        del: Change<Context>,
        contents: Option<Change<Context>>,
    },
    FileAdd {
        name: RepoPath<PathBuf>,
        add: Change<Context>,
        contents: Option<Change<Context>>,
    },
    Change {
        file: Rc<RepoPath<PathBuf>>,
        change: Change<Context>,
        replacement: Option<Change<Context>>,
        old_line: usize,
        new_line: usize,
    },
}

pub struct RecordIter<R, C> {
    rec: Option<R>,
    extra: Option<C>,
}

impl<Context> IntoIterator for Record<Context> {
    type IntoIter = RecordIter<Record<Context>, Change<Context>>;
    type Item = Change<Context>;
    fn into_iter(self) -> Self::IntoIter {
        RecordIter {
            rec: Some(self),
            extra: None,
        }
    }
}

impl<Context> Record<Context> {
    pub fn iter(&self) -> RecordIter<&Record<Context>, &Change<Context>> {
        RecordIter {
            rec: Some(self),
            extra: None,
        }
    }
}

impl<Context> Iterator for RecordIter<Record<Context>, Change<Context>> {
    type Item = Change<Context>;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(extra) = self.extra.take() {
            return Some(extra);
        } else if let Some(rec) = self.rec.take() {
            match rec {
                Record::FileMove { del, add, .. } => {
                    self.extra = Some(add);
                    return Some(del);
                }
                Record::FileDel { del, contents, .. } => {
                    self.extra = contents;
                    return Some(del);
                }
                Record::FileAdd { add, contents, .. } => {
                    self.extra = contents;
                    return Some(add);
                }
                Record::Change {
                    change,
                    replacement,
                    ..
                } => {
                    if let Some(r) = replacement {
                        self.extra = Some(r)
                    }
                    return Some(change);
                }
            }
        } else {
            return None;
        }
    }
}

impl<'a, Context> Iterator for RecordIter<&'a Record<Context>, &'a Change<Context>> {
    type Item = &'a Change<Context>;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(extra) = self.extra.take() {
            return Some(extra);
        } else if let Some(rec) = self.rec.take() {
            match *rec {
                Record::FileMove {
                    ref del, ref add, ..
                } => {
                    self.extra = Some(add);
                    return Some(del);
                }
                Record::FileDel {
                    ref del,
                    ref contents,
                    ..
                } => {
                    self.extra = contents.as_ref();
                    return Some(del);
                }
                Record::FileAdd {
                    ref add,
                    ref contents,
                    ..
                } => {
                    self.extra = contents.as_ref();
                    return Some(add);
                }
                Record::Change {
                    replacement: ref r,
                    change: ref c,
                    ..
                } => {
                    if let Some(ref r) = r {
                        self.extra = Some(r)
                    }
                    return Some(c);
                }
            }
        } else {
            return None;
        }
    }
}

impl UnsignedPatch {
    pub fn empty() -> Self {
        UnsignedPatch {
            header: PatchHeader {
                authors: vec![],
                name: "".to_string(),
                description: None,
                timestamp: chrono::Utc::now(),
                flag: PatchFlags::empty(),
            },
            dependencies: HashSet::new(),
            changes: vec![],
        }
    }
    pub fn leave_unsigned(self) -> Patch {
        Patch::Unsigned(self)
    }

    fn is_tag(&self) -> bool {
        self.header.flag.contains(PatchFlags::TAG)
    }

    pub fn inverse(&self, hash: &Hash, changes: &mut Vec<Change<ChangeContext<Hash>>>) {
        for ch in self.changes.iter() {
            debug!("inverse {:?}", ch);
            match *ch {
                Change::NewNodes {
                    ref up_context,
                    flag,
                    line_num,
                    ref nodes,
                    ref inode,
                    ..
                } => {
                    let edges = up_context
                        .iter()
                        .map(|up| NewEdge {
                            from: Key {
                                patch: match up.patch {
                                    Some(ref h) => Some(h.clone()),
                                    None => Some(hash.clone()),
                                },
                                line: up.line,
                            },
                            to: Key {
                                patch: Some(hash.clone()),
                                line: line_num,
                            },
                            introduced_by: Some(hash.clone()),
                        })
                        .chain((1..nodes.len()).map(|i| NewEdge {
                            from: Key {
                                patch: Some(hash.clone()),
                                line: line_num + (i - 1),
                            },
                            to: Key {
                                patch: Some(hash.clone()),
                                line: line_num + i,
                            },
                            introduced_by: Some(hash.clone()),
                        }))
                        .collect();
                    changes.push(Change::NewEdges {
                        edges,
                        inode: inode.clone(),
                        previous: flag,
                        flag: flag ^ EdgeFlags::DELETED_EDGE,
                    })
                }
                Change::NewEdges {
                    previous,
                    flag,
                    ref edges,
                    ref inode,
                } => changes.push(Change::NewEdges {
                    previous: flag,
                    flag: previous,
                    inode: inode.clone(),
                    edges: edges
                        .iter()
                        .map(|e| NewEdge {
                            from: e.from.clone(),
                            to: e.to.clone(),
                            introduced_by: Some(hash.clone()),
                        })
                        .collect(),
                }),
            }
        }
    }
}

impl Patch {
    /// An approximate upper bound of the number of extra bytes in the
    /// database this patch might require. This depends a lot on the
    /// patch and the database, so it might be wrong.
    pub fn size_upper_bound(&self) -> usize {
        // General overhead for applying a patch; 8 pages.
        let mut size: usize = 1 << 15;
        for c in self.changes().iter() {
            match *c {
                Change::NewNodes { ref nodes, .. } => {
                    size += nodes.iter().map(|x| x.len()).sum::<usize>();
                    size += nodes.len() * 2048 // + half a page
                }
                Change::NewEdges { ref edges, .. } => size += edges.len() * 2048,
            }
        }
        size
    }

    pub fn is_tag(&self) -> bool {
        match *self {
            Patch::Unsigned(ref patch) => patch.is_tag(),
            _ => false,
        }
    }

    /// Read one patch from a gzip-compressed `BufRead`. If several
    /// patches are available in the same `BufRead`, this method can
    /// be called again.
    pub fn from_reader_compressed<R: BufRead>(r: &mut R) -> Result<(Hash, Vec<u8>, Patch)> {
        let mut rr = flate2::bufread::GzDecoder::new(r);
        let filename = {
            let filename = if let Some(header) = rr.header() {
                if let Some(filename) = header.filename() {
                    from_utf8(filename)?
                } else {
                    return Err(ErrorKind::EOF.into());
                    return Err(Error::EOF);
                }
            } else {
                return Err(ErrorKind::EOF.into());
                return Err(Error::EOF);
            };
            if let Some(h) = Hash::from_base58(filename) {
                h
            } else {
                return Err(ErrorKind::WrongHash.into());
                return Err(Error::WrongHash);
            }
        };

        let mut buf = Vec::new();
        rr.read_to_end(&mut buf)?;

        // Checking the hash.
        let patch: Patch = deserialize(&buf[..])?;
        patch.check_hash(&buf, &filename)?;

        Ok((filename, buf, patch))
    }

    fn check_hash(&self, buf: &[u8], filename: &Hash) -> Result<()> {
        let buf = match *self {
            Patch::Signed0 | Patch::Unsigned0 => {
                panic!("refusing to interact with old patch version")
            }
            Patch::Unsigned(_) => buf,
        };
        let hash = Hash::of_slice(buf)?;
        match (filename, &hash) {
            (&Hash::Sha512(ref filename), &Hash::Sha512(ref hash))
                if &filename.0[..] == &hash.0[..] =>
            {
                Ok(())
            }
            _ => Err(ErrorKind::WrongHash.into()),
            _ => Err(Error::WrongHash),
        }
2
3

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840

841
842
843

844
845
use graph;
use patch::*;
use {ErrorKind, Result};
use {Error, Result};

use diff;
use rand;
use std;
use std::collections::HashSet;
use std::fs::metadata;
use std::io::BufRead;
use std::io::Read;
#[cfg(not(windows))]
use std::os::unix::fs::PermissionsExt;
use std::path::{Path, PathBuf};
use std::rc::Rc;

use fs_representation::{RepoRoot, RepoPath};

#[cfg(not(windows))]
fn permissions(attr: &std::fs::Metadata) -> Option<usize> {
    Some(attr.permissions().mode() as usize)
}
#[cfg(windows)]
fn permissions(_: &std::fs::Metadata) -> Option<usize> {
    None
}

fn file_metadata(path: &Path) -> Result<FileMetadata> {
    let attr = metadata(&path)?;
    let permissions = permissions(&attr).unwrap_or(0o755);
    debug!("permissions = {:?}", permissions);
    Ok(FileMetadata::new(permissions & 0o777, attr.is_dir()))
}

impl<U: Transaction, R> GenericTxn<U, R> {
    pub fn globalize_change(
        &self,
        change: Change<ChangeContext<PatchId>>,
    ) -> Change<ChangeContext<Hash>> {
        match change {
            Change::NewNodes {
                up_context,
                down_context,
                flag,
                line_num,
                nodes,
                inode,
            } => Change::NewNodes {
                up_context: up_context
                    .iter()
                    .map(|&k| self.external_key_opt(k))
                    .collect(),
                down_context: down_context
                    .iter()
                    .map(|&k| self.external_key_opt(k))
                    .collect(),
                flag,
                line_num,
                nodes,
                inode,
            },
            Change::NewEdges {
                previous,
                flag,
                edges,
                inode,
            } => Change::NewEdges {
                previous,
                flag,
                edges,
                inode,
            },
        }
    }
    pub fn globalize_record(
        &self,
        change: Record<ChangeContext<PatchId>>,
    ) -> Record<ChangeContext<Hash>> {
        match change {
            Record::FileMove { new_name, del, add } => Record::FileMove {
                new_name,
                del: self.globalize_change(del),
                add: self.globalize_change(add),
            },
            Record::FileDel {
                name,
                del,
                contents,
            } => Record::FileDel {
                name,
                del: self.globalize_change(del),
                contents: contents.map(|del| self.globalize_change(del)),
            },
            Record::FileAdd {
                name,
                add,
                contents,
            } => Record::FileAdd {
                name,
                add: self.globalize_change(add),
                contents: contents.map(|add| self.globalize_change(add)),
            },
            Record::Change {
                file,
                change,
                replacement,
                old_line,
                new_line,
            } => Record::Change {
                file,
                change: self.globalize_change(change),
                replacement: replacement.map(|x| self.globalize_change(x)),
                old_line,
                new_line,
            },
        }
    }
}

pub struct RecordState {
    line_num: LineId,
    updatables: HashSet<InodeUpdate>,
    actions: Vec<Record<ChangeContext<PatchId>>>,
    redundant: Vec<(Key<PatchId>, Edge)>,
}

/// An account of the files that have been added, moved or deleted, as
/// returned by record, and used by apply (when applying a patch
/// created locally) to update the trees and inodes databases.
#[derive(Debug, Hash, PartialEq, Eq)]
pub enum InodeUpdate {
    Add {
        /// `LineId` in the new patch.
        line: LineId,
        /// `FileMetadata` in the updated file.
        meta: FileMetadata,
        /// `Inode` added by this file addition.
        inode: Inode,
    },
    Moved {
        /// `Inode` of the moved file.
        inode: Inode,
        metadata: FileMetadata,
    },
    Deleted {
        /// `Inode` of the deleted file.
        inode: Inode,
    },
}

#[derive(Debug)]
pub enum WorkingFileStatus {
    Moved {
        from: FileMetadata,
        to: FileMetadata,
    },
    Deleted,
    Ok,
    Zombie,
}

pub(crate) fn is_text(x: &[u8]) -> bool {
    x.iter().take(8000).all(|&c| c != 0)
}

impl<'env, R: rand::Rng> MutTxn<'env, R> {
    /// Create appropriate NewNodes for adding a file.
    fn record_file_addition(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        st: &mut RecordState,
        current_inode: Inode,
        parent_node: Key<Option<PatchId>>,
        realpath: &mut RepoPath<std::path::PathBuf>,
        basename: &str,
    ) -> Result<Option<LineId>> {
        let name_line_num = st.line_num.clone();
        let blank_line_num = st.line_num + 1;
        st.line_num += 2;

        debug!("metadata for {:?}", realpath);
        let path = &repo_root.absolutize(realpath);
        let meta = match file_metadata(&path) {
            Ok(metadata) => metadata,
            Err(e) => return Err(e),
        };
        debug!("meta = {:?}", meta.is_dir());

        let mut name = Vec::with_capacity(basename.len() + 2);
        name.write_metadata(meta).unwrap(); // 2 bytes.
        name.extend(basename.as_bytes());

        let mut nodes = Vec::new();

        st.updatables.insert(InodeUpdate::Add {
            line: blank_line_num.clone(),
            meta: meta,
            inode: current_inode.clone(),
        });
        let up_context_ext = Key {
            patch: if parent_node.line.is_root() {
                Some(Hash::None)
            } else if let Some(patch_id) = parent_node.patch {
                Some(self.external_hash(patch_id).to_owned())
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        let up_context = Key {
            patch: if parent_node.line.is_root() {
                Some(ROOT_PATCH_ID)
            } else if let Some(patch_id) = parent_node.patch {
                Some(patch_id)
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        st.actions.push(Record::FileAdd {
            name: realpath.to_owned(),
            add: Change::NewNodes {
                up_context: vec![up_context],
                line_num: name_line_num,
                down_context: vec![],
                nodes: vec![name, vec![]],
                flag: EdgeFlags::FOLDER_EDGE,
                inode: up_context_ext.clone(),
            },
            contents: None,
        });
        // Reading the file
        if !meta.is_dir() {
            nodes.clear();

            let mut node = Vec::new();
            {
                let mut f = std::fs::File::open(path.as_path())?;
                f.read_to_end(&mut node)?;
            }

            let up_context = Key {
                patch: None,
                line: blank_line_num.clone(),
            };
            let up_context_ext = Key {
                patch: None,
                line: blank_line_num.clone(),
            };
            if is_text(&node) {
                let mut line = Vec::new();
                let mut f = &node[..];
                loop {
                    match f.read_until('\n' as u8, &mut line) {
                        Ok(l) => {
                            if l > 0 {
                                nodes.push(line.clone());
                                line.clear()
                            } else {
                                break;
                            }
                        }
                        Err(_) => break,
                    }
                }
                let len = nodes.len();
                if !nodes.is_empty() {
                    if let Some(Record::FileAdd {
                        ref mut contents, ..
                    }) = st.actions.last_mut()
                    {
                        *contents = Some(Change::NewNodes {
                            up_context: vec![up_context],
                            line_num: st.line_num,
                            down_context: vec![],
                            nodes: nodes,
                            flag: EdgeFlags::empty(),
                            inode: up_context_ext,
                        });
                    }
                }
                st.line_num += len;
            } else if let Some(Record::FileAdd {
                ref mut contents, ..
            }) = st.actions.last_mut()
            {
                *contents = Some(Change::NewNodes {
                    up_context: vec![up_context],
                    line_num: st.line_num,
                    down_context: vec![],
                    nodes: vec![node],
                    flag: EdgeFlags::empty(),
                    inode: up_context_ext,
                });
                st.line_num += 1;
            }
            Ok(None)
        } else {
            Ok(Some(blank_line_num))
        }
    }

    /// Diff for binary files, doesn't bother splitting the file in
    /// lines. This is wasteful, but doesn't break the format, and
    /// doesn't create conflicts inside binary files.
    fn diff_with_binary(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        algorithm: diff::Algorithm,
        inode: Key<Option<Hash>>,
        branch: &Branch,
        st: &mut RecordState,
        ret: &mut graph::Graph,
        path: Rc<RepoPath<PathBuf>>,
    ) -> Result<()> {
        let mut lines_b = Vec::new();
        {
            debug!("opening file for diff: {:?}", path);
            let mut f = std::fs::File::open(repo_root.absolutize(&path))?;
            f.read_to_end(&mut lines_b)?;
        }

        self.diff(
            algorithm,
            inode,
            branch,
            path,
            &mut st.line_num,
            &mut st.actions,
            &mut st.redundant,
            ret,
            &lines_b,
        )
    }

    fn record_moved_file(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        diff_algorithm: diff::Algorithm,
        branch: &Branch,
        realpath: &mut RepoPath<std::path::PathBuf>,
        st: &mut RecordState,
        parent_node: Key<Option<PatchId>>,
        current_node: Key<PatchId>,
        basename: &str,
        new_meta: FileMetadata,
        old_meta: FileMetadata,
    ) -> Result<()> {
        debug!("record_moved_file: parent_node={:?}", parent_node);
        // Delete all former names.
        let mut edges = Vec::new();
        // Now take all grandparents of l2, delete them.

        let mut name = Vec::with_capacity(basename.len() + 2);
        name.write_metadata(new_meta).unwrap();
        name.extend(basename.as_bytes());
        for parent in self.iter_parents(branch, current_node, EdgeFlags::FOLDER_EDGE) {
            debug!("iter_parents: {:?}", parent);
            let previous_name: &[u8] = match self.get_contents(parent.dest) {
                None => &[],
                Some(n) => n.as_slice(),
            };
            let name_changed =
                (&previous_name[2..] != &name[2..]) || (new_meta != old_meta && cfg!(not(windows)));

            for grandparent in self.iter_parents(branch, parent.dest, EdgeFlags::FOLDER_EDGE) {
                debug!("iter_parents: grandparent = {:?}", grandparent);
                let grandparent_changed = if let Some(ref parent_node_patch) = parent_node.patch {
                    *parent_node_patch != grandparent.dest.patch
                        || parent_node.line != grandparent.dest.line
                } else {
                    true
                };
                if grandparent_changed || name_changed {
                    edges.push(NewEdge {
                        from: Key {
                            line: parent.dest.line.clone(),
                            patch: Some(self.external_hash(parent.dest.patch).to_owned()),
                        },
                        to: Key {
                            line: grandparent.dest.line.clone(),
                            patch: Some(self.external_hash(grandparent.dest.patch).to_owned()),
                        },
                        introduced_by: Some(
                            self.external_hash(grandparent.introduced_by).to_owned(),
                        ),
                    })
                }
            }
        }
        debug!("edges:{:?}", edges);
        let up_context_ext = Key {
            patch: if parent_node.line.is_root() {
                Some(Hash::None)
            } else if let Some(parent_patch) = parent_node.patch {
                Some(self.external_hash(parent_patch).to_owned())
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        let up_context = Key {
            patch: if parent_node.line.is_root() {
                Some(ROOT_PATCH_ID)
            } else if let Some(parent_patch) = parent_node.patch {
                Some(parent_patch)
            } else {
                None
            },
            line: parent_node.line.clone(),
        };
        if !edges.is_empty() {
            // If this file's name or meta info has changed.
            st.actions.push(Record::FileMove {
                new_name: realpath.to_owned(),
                del: Change::NewEdges {
                    edges: edges,
                    previous: EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE,
                    flag: EdgeFlags::DELETED_EDGE | EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE,
                    inode: up_context_ext.clone(),
                },
                add: Change::NewNodes {
                    up_context: vec![up_context],
                    line_num: st.line_num,
                    down_context: vec![Key {
                        patch: Some(current_node.patch),
                        line: current_node.line.clone(),
                    }],
                    nodes: vec![name],
                    flag: EdgeFlags::FOLDER_EDGE,
                    inode: up_context_ext.clone(),
                },
            });
            st.line_num += 1;
        }
        if !old_meta.is_dir() {
            info!("retrieving");
            let mut ret = self.retrieve(branch, current_node);
            debug!("diff");
            let patch_ext = self.get_external(current_node.patch).unwrap();
            self.diff_with_binary(
                repo_root,
                diff_algorithm,
                Key {
                    patch: Some(patch_ext.to_owned()),
                    line: current_node.line,
                },
                branch,
                st,
                &mut ret,
                Rc::new(realpath.clone()),
            )?;
        };
        Ok(())
    }

    fn record_deleted_file(
        &self,
        st: &mut RecordState,
        branch: &Branch,
        realpath: &RepoPath<impl AsRef<Path>>,
        current_node: Key<PatchId>,
    ) -> Result<()> {
        debug!("record_deleted_file");
        let mut edges = Vec::new();
        let mut previous = EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE;
        // Now take all grandparents of the current node, delete them.
        for parent in self.iter_parents(branch, current_node, EdgeFlags::FOLDER_EDGE) {
            for grandparent in self.iter_parents(branch, parent.dest, EdgeFlags::FOLDER_EDGE) {
                edges.push(NewEdge {
                    from: self.external_key(&parent.dest).unwrap(),
                    to: self.external_key(&grandparent.dest).unwrap(),
                    introduced_by: Some(self.external_hash(grandparent.introduced_by).to_owned()),
                });
                previous = grandparent.flag;
            }
        }
        // If the file is a directory, delete recursively
        let mut file_edges = vec![];
        {
            debug!("del={:?}", current_node);
            let ret = self.retrieve(branch, current_node);
            debug!("ret {:?}", ret);
            for l in ret.lines.iter() {
                if l.key != ROOT_KEY {
                    let ext_key = self.external_key(&l.key).unwrap();
                    debug!("ext_key={:?}", ext_key);
                    for v in self.iter_parents(branch, l.key, EdgeFlags::empty()) {
                        debug!("v={:?}", v);
                        file_edges.push(NewEdge {
                            from: ext_key.clone(),
                            to: self.external_key(&v.dest).unwrap(),
                            introduced_by: Some(self.external_hash(v.introduced_by).to_owned()),
                        });
                        if let Some(inode) = self.get_revinodes(v.dest) {
                            st.updatables.insert(InodeUpdate::Deleted {
                                inode: inode.to_owned(),
                            });
                        }
                    }
                    for v in self.iter_parents(branch, l.key, EdgeFlags::FOLDER_EDGE) {
                        debug!("v={:?}", v);
                        edges.push(NewEdge {
                            from: ext_key.clone(),
                            to: self.external_key(&v.dest).unwrap(),
                            introduced_by: Some(self.external_hash(v.introduced_by).to_owned()),
                        });
                    }
                }
            }
        }

        if !edges.is_empty() {
            st.actions.push(Record::FileDel {
                name: realpath.to_owned(),
                del: Change::NewEdges {
                    edges: edges,
                    previous,
                    flag: EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                    inode: self.external_key(&current_node).unwrap(),
                },
                contents: if file_edges.is_empty() {
                    None
                } else {
                    Some(Change::NewEdges {
                        edges: file_edges,
                        previous: EdgeFlags::PARENT_EDGE,
                        flag: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                        inode: self.external_key(&current_node).unwrap(),
                    })
                },
            });
        }
        Ok(())
    }

    fn record_children(
        &self,
        repo_root:  &RepoRoot<impl AsRef<Path>>,
        diff_algorithm: diff::Algorithm,
        branch: &Branch,
        st: &mut RecordState,
        path: &mut RepoPath<std::path::PathBuf>,
        current_node: Key<Option<PatchId>>,
        current_inode: Inode,
        obsolete_inodes: &mut Vec<Inode>,
    ) -> Result<()> {
        debug!("children of current_inode {}", current_inode.to_hex());
        let file_id = OwnedFileId {
            parent_inode: current_inode.clone(),
            basename: SmallString::from_str(""),
        };
        debug!("iterating tree, starting from {:?}", file_id.as_file_id());
        for (k, v) in self
            .iter_tree(Some((&file_id.as_file_id(), None)))
            .take_while(|&(ref k, _)| k.parent_inode == current_inode)
        {
            debug!("calling record_all recursively, {}", line!());

            if k.basename.len() > 0 {
                // If this is an actual file and not just the "."
                self.record_inode(
                    repo_root,
                    diff_algorithm,
                    branch,
                    st,
                    current_node.clone(), // parent
                    v,                    // current_inode
                    path,
                    obsolete_inodes,
                    k.basename.as_str(),
                )?
            }
        }
        Ok(())
    }

    /// If `inode` is a file known to the current branch, return
    /// whether it's been moved, deleted, or its "status" (including
    /// permissions) has been changed.
    ///
    /// Returns `None` if `inode` is not known to the current branch.
    fn inode_status(&self,
                    repo_root: &RepoRoot<impl AsRef<Path>>,
                    inode: Inode,
                    path: &RepoPath<impl AsRef<Path>>)
                    -> (Option<(WorkingFileStatus, FileHeader)>) {
        match self.get_inodes(inode) {
            Some(file_header) => {
                let old_meta = file_header.metadata;
                let new_meta = file_metadata(&repo_root.absolutize(path)).ok();
                
                debug!("current_node={:?}", file_header);
                debug!("old_attr={:?},int_attr={:?}", old_meta, new_meta);

                let status = match (new_meta, file_header.status) {
                    (Some(new_meta), FileStatus::Moved) => WorkingFileStatus::Moved {
                        from: old_meta,
                        to: new_meta,
                    },
                    (Some(new_meta), _) if old_meta != new_meta => WorkingFileStatus::Moved {
                        from: old_meta,
                        to: new_meta,
                    },
                    (None, _) | (_, FileStatus::Deleted) => WorkingFileStatus::Deleted,
                    (Some(_), FileStatus::Ok) => WorkingFileStatus::Ok,
                    (Some(_), FileStatus::Zombie) => WorkingFileStatus::Zombie,
                };
                Some((status, file_header.clone()))
            }
            None => None,
        }
    }

    fn record_inode(
        &self,
        repo_root: &RepoRoot<impl AsRef<Path>>,
        diff_algorithm: diff::Algorithm,
        branch: &Branch,
        st: &mut RecordState,
        parent_node: Key<Option<PatchId>>,
        current_inode: Inode,
        realpath: &mut RepoPath<std::path::PathBuf>,
        obsolete_inodes: &mut Vec<Inode>,
        basename: &str,
    ) -> Result<()> {
        realpath.push(basename);
        debug!("realpath: {:?}", realpath);
        debug!("inode: {:?}", current_inode);
        debug!("header: {:?}", self.get_inodes(current_inode));
        let status_header = self.inode_status(repo_root, current_inode, realpath);
        debug!("status_header: {:?}", status_header);
        let mut current_key = match &status_header {
            &Some((_, ref file_header)) => Some(Key {
                patch: Some(file_header.key.patch.clone()),
                line: file_header.key.line.clone(),
            }),
            &None => None,
        };

        match status_header {
            Some((
                WorkingFileStatus::Moved {
                    from: old_meta,
                    to: new_meta,
                },
                file_header,
            )) => {
                st.updatables.insert(InodeUpdate::Moved {
                    inode: current_inode.clone(),
                    metadata: new_meta,
                });
                self.record_moved_file(
                    repo_root,
                    diff_algorithm,
                    branch,
                    realpath,
                    st,
                    parent_node,
                    file_header.key,
                    basename,
                    new_meta,
                    old_meta,
                )?
            }
            Some((WorkingFileStatus::Deleted, file_header)) => {
                st.updatables.insert(InodeUpdate::Deleted {
                    inode: current_inode.clone(),
                });
                self.record_deleted_file(st, branch, realpath, file_header.key)?;
                // If we are deleting a directory, don't recurse,
                // because record_deleted_file already did it.
                realpath.pop();
                return Ok(());
            }
            Some((WorkingFileStatus::Ok, file_header)) => {
                if !file_header.metadata.is_dir() {
                    let mut ret = self.retrieve(branch, file_header.key);
                    debug!("now calling diff {:?}", file_header.key);
                    let inode = Key {
                        patch: Some(self.external_hash(file_header.key.patch).to_owned()),
                        line: file_header.key.line,
                    };
                    self.confirm_path(st, branch, realpath, file_header.key)?;
                    self.diff_with_binary(
                        repo_root,
                        diff_algorithm,
                        inode,
                        branch,
                        st,
                        &mut ret,
                        Rc::new(realpath.clone()),
                    )?;
                } else {
                    // Confirm
                    self.confirm_path(st, branch, &realpath, file_header.key)?;
                }
            }
            Some((WorkingFileStatus::Zombie, _)) => {
                // This file is a zombie, but the user has not
                // specified anything to do with this file, so leave
                // it alone.
            }
            None => {
                if let Ok(new_key) =
                    self.record_file_addition(repo_root, st, current_inode, parent_node,
                                              realpath, basename)
                {
                    current_key = new_key.map(|next| Key {
                        patch: None,
                        line: next,
                    })
                } else {
                    obsolete_inodes.push(current_inode)
                }
            }
        }

        let current_key = current_key;
        debug!("current_node={:?}", current_key);
        if let Some(current_node) = current_key {
            self.record_children(
                repo_root,
                diff_algorithm,
                branch,
                st,
                realpath,
                current_node,
                current_inode,
                obsolete_inodes,
            )?;
        };
        realpath.pop();
        Ok(())
    }

    fn external_newedge(
        &self,
        from: Key<PatchId>,
        to: Key<PatchId>,
        introduced_by: PatchId,
    ) -> NewEdge {
        NewEdge {
            from: Key {
                patch: Some(self.external_hash(from.patch).to_owned()),
                line: from.line,
            },
            to: Key {
                patch: Some(self.external_hash(to.patch).to_owned()),
                line: to.line,
            },
            introduced_by: Some(self.external_hash(introduced_by).to_owned()),
        }
    }

    /// `key` must be a non-root inode key.
    fn confirm_path(
        &self,
        st: &mut RecordState,
        branch: &Branch,
        realpath: &RepoPath<impl AsRef<Path>>,
        key: Key<PatchId>,
    ) -> Result<()> {
        debug!("confirm_path");
        let f = EdgeFlags::PARENT_EDGE | EdgeFlags::FOLDER_EDGE | EdgeFlags::DELETED_EDGE;
        // Are there deleted parent edges?
        let mut edges = Vec::new();
        for v in self.iter_adjacent(branch, key, f, f) {
            debug!("confirm {:?}", v.dest);
            edges.push(self.external_newedge(key, v.dest, v.introduced_by));
            for v_ in self.iter_adjacent(branch, v.dest, f, f) {
                debug!("confirm 2 {:?}", v_.dest);
                edges.push(self.external_newedge(v.dest, v_.dest, v_.introduced_by));
            }
        }

        if !edges.is_empty() {
            let inode = Key {
                patch: Some(self.external_hash(key.patch).to_owned()),
                line: key.line.clone(),
            };
            st.actions.push(Record::FileAdd {
                name: realpath.to_owned(),
                add: Change::NewEdges {
                    edges,
                    previous: EdgeFlags::FOLDER_EDGE
                        | EdgeFlags::PARENT_EDGE
                        | EdgeFlags::DELETED_EDGE,
                    flag: EdgeFlags::FOLDER_EDGE | EdgeFlags::PARENT_EDGE,
                    inode,
                },
                contents: None,
            });
        }
        debug!("/confirm_path");

        Ok(())
    }
}

impl RecordState {
    pub fn new() -> Self {
        RecordState {
            line_num: LineId::new() + 1,
            actions: Vec::new(),
            updatables: HashSet::new(),
            redundant: Vec::new(),
        }
    }

    pub fn finish(self) -> (Vec<Record<ChangeContext<PatchId>>>, HashSet<InodeUpdate>) {
        (self.actions, self.updatables)
    }
}

impl<'env, T: rand::Rng> MutTxn<'env, T> {
    pub fn record(
        &mut self,
        diff_algorithm: diff::Algorithm,
        state: &mut RecordState,
        branch: &Branch,
        working_copy: &RepoRoot<impl AsRef<Path>>,
        prefix: &RepoPath<impl AsRef<Path>>,
    ) -> Result<()> {
        let mut obsolete_inodes = Vec::new();

        match prefix.split() {
            Some ((parent_path, basename)) =>
            {
                let inode = self.find_inode(prefix)?;
                // Key needs to be the parent's node.
                let key: Key<PatchId> = {
                    // find this inode's parent.
                    if let Some(parent) = self.get_revtree(inode) {
                        if parent.parent_inode.is_root() {
                            ROOT_KEY
                        } else if let Some(key) = self.get_inodes(parent.parent_inode) {
                            key.key
                        } else {
                            return Err(ErrorKind::FileNotInRepo(prefix.to_path_buf()).into());
                            return Err(Error::FileNotInRepo(prefix.to_path_buf()));
                        }
                    } else {
                        return Err(ErrorKind::FileNotInRepo(prefix.to_path_buf()).into());
                        return Err(Error::FileNotInRepo(prefix.to_path_buf()));
                    }