jujutsu_lib/
index_store.rs

1// Copyright 2021 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::collections::{HashMap, HashSet};
16use std::fs::File;
17use std::io;
18use std::io::{Read, Write};
19use std::path::PathBuf;
20use std::sync::Arc;
21
22use itertools::Itertools;
23use tempfile::NamedTempFile;
24
25use crate::backend::CommitId;
26use crate::commit::Commit;
27use crate::dag_walk;
28use crate::file_util::persist_content_addressed_temp_file;
29use crate::index::{Index, IndexLoadError, MutableIndex, ReadonlyIndex};
30use crate::op_store::OperationId;
31use crate::operation::Operation;
32use crate::store::Store;
33
34pub struct IndexStore {
35    dir: PathBuf,
36}
37
38impl IndexStore {
39    pub fn init(dir: PathBuf) -> Self {
40        std::fs::create_dir(dir.join("operations")).unwrap();
41        IndexStore { dir }
42    }
43
44    pub fn reinit(&self) {
45        std::fs::remove_dir_all(self.dir.join("operations")).unwrap();
46        IndexStore::init(self.dir.clone());
47    }
48
49    pub fn load(dir: PathBuf) -> IndexStore {
50        IndexStore { dir }
51    }
52
53    pub fn get_index_at_op(&self, op: &Operation, store: &Arc<Store>) -> Arc<ReadonlyIndex> {
54        let op_id_hex = op.id().hex();
55        let op_id_file = self.dir.join("operations").join(op_id_hex);
56        if op_id_file.exists() {
57            match self.load_index_at_operation(
58                store.commit_id_length(),
59                store.change_id_length(),
60                op.id(),
61            ) {
62                Err(IndexLoadError::IndexCorrupt(_)) => {
63                    // If the index was corrupt (maybe it was written in a different format),
64                    // we just reindex.
65                    // TODO: Move this message to a callback or something.
66                    println!("The index was corrupt (maybe the format has changed). Reindexing...");
67                    std::fs::remove_dir_all(self.dir.join("operations")).unwrap();
68                    std::fs::create_dir(self.dir.join("operations")).unwrap();
69                    self.index_at_operation(store, op).unwrap()
70                }
71                result => result.unwrap(),
72            }
73        } else {
74            self.index_at_operation(store, op).unwrap()
75        }
76    }
77
78    pub fn write_index(&self, index: MutableIndex) -> io::Result<Arc<ReadonlyIndex>> {
79        index.save_in(self.dir.clone())
80    }
81
82    fn load_index_at_operation(
83        &self,
84        commit_id_length: usize,
85        change_id_length: usize,
86        op_id: &OperationId,
87    ) -> Result<Arc<ReadonlyIndex>, IndexLoadError> {
88        let op_id_file = self.dir.join("operations").join(op_id.hex());
89        let mut buf = vec![];
90        File::open(op_id_file)
91            .unwrap()
92            .read_to_end(&mut buf)
93            .unwrap();
94        let index_file_id_hex = String::from_utf8(buf).unwrap();
95        let index_file_path = self.dir.join(&index_file_id_hex);
96        let mut index_file = File::open(index_file_path).unwrap();
97        ReadonlyIndex::load_from(
98            &mut index_file,
99            self.dir.clone(),
100            index_file_id_hex,
101            commit_id_length,
102            change_id_length,
103        )
104    }
105
106    fn index_at_operation(
107        &self,
108        store: &Arc<Store>,
109        operation: &Operation,
110    ) -> io::Result<Arc<ReadonlyIndex>> {
111        let view = operation.view();
112        let operations_dir = self.dir.join("operations");
113        let commit_id_length = store.commit_id_length();
114        let change_id_length = store.change_id_length();
115        let mut new_heads = view.heads().clone();
116        let mut parent_op_id: Option<OperationId> = None;
117        for op in dag_walk::bfs(
118            vec![operation.clone()],
119            Box::new(|op: &Operation| op.id().clone()),
120            Box::new(|op: &Operation| op.parents()),
121        ) {
122            if operations_dir.join(op.id().hex()).is_file() {
123                if parent_op_id.is_none() {
124                    parent_op_id = Some(op.id().clone())
125                }
126            } else {
127                for head in op.view().heads() {
128                    new_heads.insert(head.clone());
129                }
130            }
131        }
132        let mut data;
133        let maybe_parent_file;
134        match parent_op_id {
135            None => {
136                maybe_parent_file = None;
137                data = MutableIndex::full(commit_id_length, change_id_length);
138            }
139            Some(parent_op_id) => {
140                let parent_file = self
141                    .load_index_at_operation(commit_id_length, change_id_length, &parent_op_id)
142                    .unwrap();
143                maybe_parent_file = Some(parent_file.clone());
144                data = MutableIndex::incremental(parent_file)
145            }
146        }
147
148        let mut heads = new_heads.into_iter().collect_vec();
149        heads.sort();
150        let commits = topo_order_earlier_first(store, heads, maybe_parent_file);
151
152        for commit in &commits {
153            data.add_commit(commit);
154        }
155
156        let index_file = data.save_in(self.dir.clone())?;
157
158        self.associate_file_with_operation(&index_file, operation.id())?;
159
160        Ok(index_file)
161    }
162
163    /// Records a link from the given operation to the this index version.
164    pub fn associate_file_with_operation(
165        &self,
166        index: &ReadonlyIndex,
167        op_id: &OperationId,
168    ) -> io::Result<()> {
169        let mut temp_file = NamedTempFile::new_in(&self.dir)?;
170        let file = temp_file.as_file_mut();
171        file.write_all(index.name().as_bytes())?;
172        persist_content_addressed_temp_file(
173            temp_file,
174            self.dir.join("operations").join(op_id.hex()),
175        )?;
176        Ok(())
177    }
178}
179
180// Returns the ancestors of heads with parents and predecessors come before the
181// commit itself
182fn topo_order_earlier_first(
183    store: &Arc<Store>,
184    heads: Vec<CommitId>,
185    parent_file: Option<Arc<ReadonlyIndex>>,
186) -> Vec<Commit> {
187    // First create a list of all commits in topological order with
188    // children/successors first (reverse of what we want)
189    let mut work = vec![];
190    for head in &heads {
191        work.push(store.get_commit(head).unwrap());
192    }
193    let mut commits = vec![];
194    let mut visited = HashSet::new();
195    let mut in_parent_file = HashSet::new();
196    let parent_file_source = parent_file.as_ref().map(|file| file.as_ref());
197    while let Some(commit) = work.pop() {
198        if parent_file_source.map_or(false, |index| index.has_id(commit.id())) {
199            in_parent_file.insert(commit.id().clone());
200            continue;
201        } else if !visited.insert(commit.id().clone()) {
202            continue;
203        }
204
205        work.extend(commit.parents());
206        work.extend(commit.predecessors());
207        commits.push(commit);
208    }
209    drop(visited);
210
211    // Now create the topological order with earlier commits first. If we run into
212    // any commits whose parents/predecessors have not all been indexed, put
213    // them in the map of waiting commit (keyed by the commit they're waiting
214    // for). Note that the order in the graph doesn't really have to be
215    // topological, but it seems like a useful property to have.
216
217    // Commits waiting for their parents/predecessors to be added
218    let mut waiting = HashMap::new();
219
220    let mut result = vec![];
221    let mut visited = in_parent_file;
222    while let Some(commit) = commits.pop() {
223        let mut waiting_for_earlier_commit = false;
224        for earlier in commit
225            .parent_ids()
226            .iter()
227            .chain(commit.predecessor_ids().iter())
228        {
229            if !visited.contains(earlier) {
230                waiting
231                    .entry(earlier.clone())
232                    .or_insert_with(Vec::new)
233                    .push(commit.clone());
234                waiting_for_earlier_commit = true;
235                break;
236            }
237        }
238        if !waiting_for_earlier_commit {
239            visited.insert(commit.id().clone());
240            if let Some(dependents) = waiting.remove(commit.id()) {
241                commits.extend(dependents);
242            }
243            result.push(commit);
244        }
245    }
246    assert!(waiting.is_empty());
247    result
248}
jujutsu_lib/index_store.rs

jujutsu_lib/
index_store.rs
