##// END OF EJS Templates
copies-rust: rewrite ChangedFiles binary parsing...
Simon Sapin -
r47413:f977a065 default
parent child Browse files
Show More
@@ -1,761 +1,673 b''
1 use crate::utils::hg_path::HgPath;
1 use crate::utils::hg_path::HgPath;
2 use crate::utils::hg_path::HgPathBuf;
2 use crate::utils::hg_path::HgPathBuf;
3 use crate::Revision;
3 use crate::Revision;
4 use crate::NULL_REVISION;
4 use crate::NULL_REVISION;
5
5
6 use bytes_cast::{unaligned, BytesCast};
6 use im_rc::ordmap::Entry;
7 use im_rc::ordmap::Entry;
7 use im_rc::ordmap::OrdMap;
8 use im_rc::ordmap::OrdMap;
8 use im_rc::OrdSet;
9 use im_rc::OrdSet;
9
10
10 use std::cmp::Ordering;
11 use std::cmp::Ordering;
11 use std::collections::HashMap;
12 use std::collections::HashMap;
12 use std::convert::TryInto;
13
13
14 pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
14 pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
15
15
16 type PathToken = usize;
16 type PathToken = usize;
17
17
18 #[derive(Clone, Debug)]
18 #[derive(Clone, Debug)]
19 struct CopySource {
19 struct CopySource {
20 /// revision at which the copy information was added
20 /// revision at which the copy information was added
21 rev: Revision,
21 rev: Revision,
22 /// the copy source, (Set to None in case of deletion of the associated
22 /// the copy source, (Set to None in case of deletion of the associated
23 /// key)
23 /// key)
24 path: Option<PathToken>,
24 path: Option<PathToken>,
25 /// a set of previous `CopySource.rev` value directly or indirectly
25 /// a set of previous `CopySource.rev` value directly or indirectly
26 /// overwritten by this one.
26 /// overwritten by this one.
27 overwritten: OrdSet<Revision>,
27 overwritten: OrdSet<Revision>,
28 }
28 }
29
29
30 impl CopySource {
30 impl CopySource {
31 /// create a new CopySource
31 /// create a new CopySource
32 ///
32 ///
33 /// Use this when no previous copy source existed.
33 /// Use this when no previous copy source existed.
34 fn new(rev: Revision, path: Option<PathToken>) -> Self {
34 fn new(rev: Revision, path: Option<PathToken>) -> Self {
35 Self {
35 Self {
36 rev,
36 rev,
37 path,
37 path,
38 overwritten: OrdSet::new(),
38 overwritten: OrdSet::new(),
39 }
39 }
40 }
40 }
41
41
42 /// create a new CopySource from merging two others
42 /// create a new CopySource from merging two others
43 ///
43 ///
44 /// Use this when merging two InternalPathCopies requires active merging of
44 /// Use this when merging two InternalPathCopies requires active merging of
45 /// some entries.
45 /// some entries.
46 fn new_from_merge(rev: Revision, winner: &Self, loser: &Self) -> Self {
46 fn new_from_merge(rev: Revision, winner: &Self, loser: &Self) -> Self {
47 let mut overwritten = OrdSet::new();
47 let mut overwritten = OrdSet::new();
48 overwritten.extend(winner.overwritten.iter().copied());
48 overwritten.extend(winner.overwritten.iter().copied());
49 overwritten.extend(loser.overwritten.iter().copied());
49 overwritten.extend(loser.overwritten.iter().copied());
50 overwritten.insert(winner.rev);
50 overwritten.insert(winner.rev);
51 overwritten.insert(loser.rev);
51 overwritten.insert(loser.rev);
52 Self {
52 Self {
53 rev,
53 rev,
54 path: winner.path,
54 path: winner.path,
55 overwritten: overwritten,
55 overwritten: overwritten,
56 }
56 }
57 }
57 }
58
58
59 /// Update the value of a pre-existing CopySource
59 /// Update the value of a pre-existing CopySource
60 ///
60 ///
61 /// Use this when recording copy information from parent β†’ child edges
61 /// Use this when recording copy information from parent β†’ child edges
62 fn overwrite(&mut self, rev: Revision, path: Option<PathToken>) {
62 fn overwrite(&mut self, rev: Revision, path: Option<PathToken>) {
63 self.overwritten.insert(self.rev);
63 self.overwritten.insert(self.rev);
64 self.rev = rev;
64 self.rev = rev;
65 self.path = path;
65 self.path = path;
66 }
66 }
67
67
68 /// Mark pre-existing copy information as "dropped" by a file deletion
68 /// Mark pre-existing copy information as "dropped" by a file deletion
69 ///
69 ///
70 /// Use this when recording copy information from parent β†’ child edges
70 /// Use this when recording copy information from parent β†’ child edges
71 fn mark_delete(&mut self, rev: Revision) {
71 fn mark_delete(&mut self, rev: Revision) {
72 self.overwritten.insert(self.rev);
72 self.overwritten.insert(self.rev);
73 self.rev = rev;
73 self.rev = rev;
74 self.path = None;
74 self.path = None;
75 }
75 }
76
76
77 /// Mark pre-existing copy information as "dropped" by a file deletion
77 /// Mark pre-existing copy information as "dropped" by a file deletion
78 ///
78 ///
79 /// Use this when recording copy information from parent β†’ child edges
79 /// Use this when recording copy information from parent β†’ child edges
80 fn mark_delete_with_pair(&mut self, rev: Revision, other: &Self) {
80 fn mark_delete_with_pair(&mut self, rev: Revision, other: &Self) {
81 self.overwritten.insert(self.rev);
81 self.overwritten.insert(self.rev);
82 if other.rev != rev {
82 if other.rev != rev {
83 self.overwritten.insert(other.rev);
83 self.overwritten.insert(other.rev);
84 }
84 }
85 self.overwritten.extend(other.overwritten.iter().copied());
85 self.overwritten.extend(other.overwritten.iter().copied());
86 self.rev = rev;
86 self.rev = rev;
87 self.path = None;
87 self.path = None;
88 }
88 }
89
89
90 fn is_overwritten_by(&self, other: &Self) -> bool {
90 fn is_overwritten_by(&self, other: &Self) -> bool {
91 other.overwritten.contains(&self.rev)
91 other.overwritten.contains(&self.rev)
92 }
92 }
93 }
93 }
94
94
95 // For the same "dest", content generated for a given revision will always be
95 // For the same "dest", content generated for a given revision will always be
96 // the same.
96 // the same.
97 impl PartialEq for CopySource {
97 impl PartialEq for CopySource {
98 fn eq(&self, other: &Self) -> bool {
98 fn eq(&self, other: &Self) -> bool {
99 #[cfg(debug_assertions)]
99 #[cfg(debug_assertions)]
100 {
100 {
101 if self.rev == other.rev {
101 if self.rev == other.rev {
102 debug_assert!(self.path == other.path);
102 debug_assert!(self.path == other.path);
103 debug_assert!(self.overwritten == other.overwritten);
103 debug_assert!(self.overwritten == other.overwritten);
104 }
104 }
105 }
105 }
106 self.rev == other.rev
106 self.rev == other.rev
107 }
107 }
108 }
108 }
109
109
110 /// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)
110 /// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)
111 type InternalPathCopies = OrdMap<PathToken, CopySource>;
111 type InternalPathCopies = OrdMap<PathToken, CopySource>;
112
112
113 /// represent the files affected by a changesets
114 ///
115 /// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
116 /// all the data categories tracked by it.
117 /// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
118 /// all the data categories tracked by it.
119 pub struct ChangedFiles<'a> {
120 nb_items: u32,
121 index: &'a [u8],
122 data: &'a [u8],
123 }
124
125 /// Represent active changes that affect the copy tracing.
113 /// Represent active changes that affect the copy tracing.
126 enum Action<'a> {
114 enum Action<'a> {
127 /// The parent ? children edge is removing a file
115 /// The parent ? children edge is removing a file
128 ///
116 ///
129 /// (actually, this could be the edge from the other parent, but it does
117 /// (actually, this could be the edge from the other parent, but it does
130 /// not matters)
118 /// not matters)
131 Removed(&'a HgPath),
119 Removed(&'a HgPath),
132 /// The parent ? children edge introduce copy information between (dest,
120 /// The parent ? children edge introduce copy information between (dest,
133 /// source)
121 /// source)
134 CopiedFromP1(&'a HgPath, &'a HgPath),
122 CopiedFromP1(&'a HgPath, &'a HgPath),
135 CopiedFromP2(&'a HgPath, &'a HgPath),
123 CopiedFromP2(&'a HgPath, &'a HgPath),
136 }
124 }
137
125
138 /// This express the possible "special" case we can get in a merge
126 /// This express the possible "special" case we can get in a merge
139 ///
127 ///
140 /// See mercurial/metadata.py for details on these values.
128 /// See mercurial/metadata.py for details on these values.
141 #[derive(PartialEq)]
129 #[derive(PartialEq)]
142 enum MergeCase {
130 enum MergeCase {
143 /// Merged: file had history on both side that needed to be merged
131 /// Merged: file had history on both side that needed to be merged
144 Merged,
132 Merged,
145 /// Salvaged: file was candidate for deletion, but survived the merge
133 /// Salvaged: file was candidate for deletion, but survived the merge
146 Salvaged,
134 Salvaged,
147 /// Normal: Not one of the two cases above
135 /// Normal: Not one of the two cases above
148 Normal,
136 Normal,
149 }
137 }
150
138
151 type FileChange<'a> = (u8, &'a HgPath, &'a HgPath);
152
153 const EMPTY: &[u8] = b"";
154 const COPY_MASK: u8 = 3;
139 const COPY_MASK: u8 = 3;
155 const P1_COPY: u8 = 2;
140 const P1_COPY: u8 = 2;
156 const P2_COPY: u8 = 3;
141 const P2_COPY: u8 = 3;
157 const ACTION_MASK: u8 = 28;
142 const ACTION_MASK: u8 = 28;
158 const REMOVED: u8 = 12;
143 const REMOVED: u8 = 12;
159 const MERGED: u8 = 8;
144 const MERGED: u8 = 8;
160 const SALVAGED: u8 = 16;
145 const SALVAGED: u8 = 16;
161
146
162 impl<'a> ChangedFiles<'a> {
147 #[derive(BytesCast)]
163 const INDEX_START: usize = 4;
148 #[repr(C)]
164 const ENTRY_SIZE: u32 = 9;
149 struct ChangedFilesIndexEntry {
165 const FILENAME_START: u32 = 1;
150 flags: u8,
166 const COPY_SOURCE_START: u32 = 5;
167
151
168 pub fn new(data: &'a [u8]) -> Self {
152 /// Only the end position is stored. The start is at the end of the
169 assert!(
153 /// previous entry.
170 data.len() >= 4,
154 destination_path_end_position: unaligned::U32Be,
171 "data size ({}) is too small to contain the header (4)",
172 data.len()
173 );
174 let nb_items_raw: [u8; 4] = (&data[0..=3])
175 .try_into()
176 .expect("failed to turn 4 bytes into 4 bytes");
177 let nb_items = u32::from_be_bytes(nb_items_raw);
178
155
179 let index_size = (nb_items * Self::ENTRY_SIZE) as usize;
156 source_index_entry_position: unaligned::U32Be,
180 let index_end = Self::INDEX_START + index_size;
157 }
158
159 fn _static_assert_size_of() {
160 let _ = std::mem::transmute::<ChangedFilesIndexEntry, [u8; 9]>;
161 }
181
162
182 assert!(
163 /// Represents the files affected by a changeset.
183 data.len() >= index_end,
164 ///
184 "data size ({}) is too small to fit the index_data ({})",
165 /// This holds a subset of `mercurial.metadata.ChangingFiles` as we do not need
185 data.len(),
166 /// all the data categories tracked by it.
186 index_end
167 pub struct ChangedFiles<'a> {
187 );
168 index: &'a [ChangedFilesIndexEntry],
169 paths: &'a [u8],
170 }
188
171
189 let ret = ChangedFiles {
172 impl<'a> ChangedFiles<'a> {
190 nb_items,
173 pub fn new(data: &'a [u8]) -> Self {
191 index: &data[Self::INDEX_START..index_end],
174 let (header, rest) = unaligned::U32Be::from_bytes(data).unwrap();
192 data: &data[index_end..],
175 let nb_index_entries = header.get() as usize;
193 };
176 let (index, paths) =
194 let max_data = ret.filename_end(nb_items - 1) as usize;
177 ChangedFilesIndexEntry::slice_from_bytes(rest, nb_index_entries)
195 assert!(
178 .unwrap();
196 ret.data.len() >= max_data,
179 Self { index, paths }
197 "data size ({}) is too small to fit all data ({})",
198 data.len(),
199 index_end + max_data
200 );
201 ret
202 }
180 }
203
181
204 pub fn new_empty() -> Self {
182 pub fn new_empty() -> Self {
205 ChangedFiles {
183 ChangedFiles {
206 nb_items: 0,
184 index: &[],
207 index: EMPTY,
185 paths: &[],
208 data: EMPTY,
209 }
186 }
210 }
187 }
211
188
212 /// internal function to return an individual entry at a given index
189 /// Internal function to return the filename of the entry at a given index
213 fn entry(&'a self, idx: u32) -> FileChange<'a> {
190 fn path(&self, idx: usize) -> &HgPath {
214 if idx >= self.nb_items {
191 let start = if idx == 0 {
215 panic!(
192 0
216 "index for entry is higher that the number of file {} >= {}",
217 idx, self.nb_items
218 )
219 }
220 let flags = self.flags(idx);
221 let filename = self.filename(idx);
222 let copy_idx = self.copy_idx(idx);
223 let copy_source = self.filename(copy_idx);
224 (flags, filename, copy_source)
225 }
226
227 /// internal function to return the filename of the entry at a given index
228 fn filename(&self, idx: u32) -> &HgPath {
229 let filename_start;
230 if idx == 0 {
231 filename_start = 0;
232 } else {
193 } else {
233 filename_start = self.filename_end(idx - 1)
194 self.index[idx - 1].destination_path_end_position.get() as usize
234 }
195 };
235 let filename_end = self.filename_end(idx);
196 let end = self.index[idx].destination_path_end_position.get() as usize;
236 let filename_start = filename_start as usize;
197 HgPath::new(&self.paths[start..end])
237 let filename_end = filename_end as usize;
238 HgPath::new(&self.data[filename_start..filename_end])
239 }
240
241 /// internal function to return the flag field of the entry at a given
242 /// index
243 fn flags(&self, idx: u32) -> u8 {
244 let idx = idx as usize;
245 self.index[idx * (Self::ENTRY_SIZE as usize)]
246 }
247
248 /// internal function to return the end of a filename part at a given index
249 fn filename_end(&self, idx: u32) -> u32 {
250 let start = (idx * Self::ENTRY_SIZE) + Self::FILENAME_START;
251 let end = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
252 let start = start as usize;
253 let end = end as usize;
254 let raw = (&self.index[start..end])
255 .try_into()
256 .expect("failed to turn 4 bytes into 4 bytes");
257 u32::from_be_bytes(raw)
258 }
259
260 /// internal function to return index of the copy source of the entry at a
261 /// given index
262 fn copy_idx(&self, idx: u32) -> u32 {
263 let start = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
264 let end = (idx + 1) * Self::ENTRY_SIZE;
265 let start = start as usize;
266 let end = end as usize;
267 let raw = (&self.index[start..end])
268 .try_into()
269 .expect("failed to turn 4 bytes into 4 bytes");
270 u32::from_be_bytes(raw)
271 }
198 }
272
199
273 /// Return an iterator over all the `Action` in this instance.
200 /// Return an iterator over all the `Action` in this instance.
274 fn iter_actions(&self) -> ActionsIterator {
201 fn iter_actions(&self) -> impl Iterator<Item = Action> {
275 ActionsIterator {
202 self.index.iter().enumerate().flat_map(move |(idx, entry)| {
276 changes: &self,
203 let path = self.path(idx);
277 current: 0,
204 if (entry.flags & ACTION_MASK) == REMOVED {
278 }
205 Some(Action::Removed(path))
206 } else if (entry.flags & COPY_MASK) == P1_COPY {
207 let source_idx =
208 entry.source_index_entry_position.get() as usize;
209 Some(Action::CopiedFromP1(path, self.path(source_idx)))
210 } else if (entry.flags & COPY_MASK) == P2_COPY {
211 let source_idx =
212 entry.source_index_entry_position.get() as usize;
213 Some(Action::CopiedFromP2(path, self.path(source_idx)))
214 } else {
215 None
216 }
217 })
279 }
218 }
280
219
281 /// return the MergeCase value associated with a filename
220 /// return the MergeCase value associated with a filename
282 fn get_merge_case(&self, path: &HgPath) -> MergeCase {
221 fn get_merge_case(&self, path: &HgPath) -> MergeCase {
283 if self.nb_items == 0 {
222 if self.index.is_empty() {
284 return MergeCase::Normal;
223 return MergeCase::Normal;
285 }
224 }
286 let mut low_part = 0;
225 let mut low_part = 0;
287 let mut high_part = self.nb_items;
226 let mut high_part = self.index.len();
288
227
289 while low_part < high_part {
228 while low_part < high_part {
290 let cursor = (low_part + high_part - 1) / 2;
229 let cursor = (low_part + high_part - 1) / 2;
291 let (flags, filename, _source) = self.entry(cursor);
230 match path.cmp(self.path(cursor)) {
292 match path.cmp(filename) {
293 Ordering::Less => low_part = cursor + 1,
231 Ordering::Less => low_part = cursor + 1,
294 Ordering::Greater => high_part = cursor,
232 Ordering::Greater => high_part = cursor,
295 Ordering::Equal => {
233 Ordering::Equal => {
296 return match flags & ACTION_MASK {
234 return match self.index[cursor].flags & ACTION_MASK {
297 MERGED => MergeCase::Merged,
235 MERGED => MergeCase::Merged,
298 SALVAGED => MergeCase::Salvaged,
236 SALVAGED => MergeCase::Salvaged,
299 _ => MergeCase::Normal,
237 _ => MergeCase::Normal,
300 };
238 };
301 }
239 }
302 }
240 }
303 }
241 }
304 MergeCase::Normal
242 MergeCase::Normal
305 }
243 }
306 }
244 }
307
245
308 struct ActionsIterator<'a> {
309 changes: &'a ChangedFiles<'a>,
310 current: u32,
311 }
312
313 impl<'a> Iterator for ActionsIterator<'a> {
314 type Item = Action<'a>;
315
316 fn next(&mut self) -> Option<Action<'a>> {
317 while self.current < self.changes.nb_items {
318 let (flags, file, source) = self.changes.entry(self.current);
319 self.current += 1;
320 if (flags & ACTION_MASK) == REMOVED {
321 return Some(Action::Removed(file));
322 }
323 let copy = flags & COPY_MASK;
324 if copy == P1_COPY {
325 return Some(Action::CopiedFromP1(file, source));
326 } else if copy == P2_COPY {
327 return Some(Action::CopiedFromP2(file, source));
328 }
329 }
330 return None;
331 }
332 }
333
334 /// A small "tokenizer" responsible of turning full HgPath into lighter
246 /// A small "tokenizer" responsible of turning full HgPath into lighter
335 /// PathToken
247 /// PathToken
336 ///
248 ///
337 /// Dealing with small object, like integer is much faster, so HgPath input are
249 /// Dealing with small object, like integer is much faster, so HgPath input are
338 /// turned into integer "PathToken" and converted back in the end.
250 /// turned into integer "PathToken" and converted back in the end.
339 #[derive(Clone, Debug, Default)]
251 #[derive(Clone, Debug, Default)]
340 struct TwoWayPathMap {
252 struct TwoWayPathMap {
341 token: HashMap<HgPathBuf, PathToken>,
253 token: HashMap<HgPathBuf, PathToken>,
342 path: Vec<HgPathBuf>,
254 path: Vec<HgPathBuf>,
343 }
255 }
344
256
345 impl TwoWayPathMap {
257 impl TwoWayPathMap {
346 fn tokenize(&mut self, path: &HgPath) -> PathToken {
258 fn tokenize(&mut self, path: &HgPath) -> PathToken {
347 match self.token.get(path) {
259 match self.token.get(path) {
348 Some(a) => *a,
260 Some(a) => *a,
349 None => {
261 None => {
350 let a = self.token.len();
262 let a = self.token.len();
351 let buf = path.to_owned();
263 let buf = path.to_owned();
352 self.path.push(buf.clone());
264 self.path.push(buf.clone());
353 self.token.insert(buf, a);
265 self.token.insert(buf, a);
354 a
266 a
355 }
267 }
356 }
268 }
357 }
269 }
358
270
359 fn untokenize(&self, token: PathToken) -> &HgPathBuf {
271 fn untokenize(&self, token: PathToken) -> &HgPathBuf {
360 assert!(token < self.path.len(), "Unknown token: {}", token);
272 assert!(token < self.path.len(), "Unknown token: {}", token);
361 &self.path[token]
273 &self.path[token]
362 }
274 }
363 }
275 }
364
276
365 /// Same as mercurial.copies._combine_changeset_copies, but in Rust.
277 /// Same as mercurial.copies._combine_changeset_copies, but in Rust.
366 pub struct CombineChangesetCopies {
278 pub struct CombineChangesetCopies {
367 all_copies: HashMap<Revision, InternalPathCopies>,
279 all_copies: HashMap<Revision, InternalPathCopies>,
368 path_map: TwoWayPathMap,
280 path_map: TwoWayPathMap,
369 children_count: HashMap<Revision, usize>,
281 children_count: HashMap<Revision, usize>,
370 }
282 }
371
283
372 impl CombineChangesetCopies {
284 impl CombineChangesetCopies {
373 pub fn new(children_count: HashMap<Revision, usize>) -> Self {
285 pub fn new(children_count: HashMap<Revision, usize>) -> Self {
374 Self {
286 Self {
375 all_copies: HashMap::new(),
287 all_copies: HashMap::new(),
376 path_map: TwoWayPathMap::default(),
288 path_map: TwoWayPathMap::default(),
377 children_count,
289 children_count,
378 }
290 }
379 }
291 }
380
292
381 /// Combined the given `changes` data specific to `rev` with the data
293 /// Combined the given `changes` data specific to `rev` with the data
382 /// previously given for its parents (and transitively, its ancestors).
294 /// previously given for its parents (and transitively, its ancestors).
383 pub fn add_revision(
295 pub fn add_revision(
384 &mut self,
296 &mut self,
385 rev: Revision,
297 rev: Revision,
386 p1: Revision,
298 p1: Revision,
387 p2: Revision,
299 p2: Revision,
388 changes: ChangedFiles<'_>,
300 changes: ChangedFiles<'_>,
389 ) {
301 ) {
390 self.add_revision_inner(rev, p1, p2, changes.iter_actions(), |path| {
302 self.add_revision_inner(rev, p1, p2, changes.iter_actions(), |path| {
391 changes.get_merge_case(path)
303 changes.get_merge_case(path)
392 })
304 })
393 }
305 }
394
306
395 /// Separated out from `add_revsion` so that unit tests can call this
307 /// Separated out from `add_revsion` so that unit tests can call this
396 /// without synthetizing a `ChangedFiles` in binary format.
308 /// without synthetizing a `ChangedFiles` in binary format.
397 fn add_revision_inner<'a>(
309 fn add_revision_inner<'a>(
398 &mut self,
310 &mut self,
399 rev: Revision,
311 rev: Revision,
400 p1: Revision,
312 p1: Revision,
401 p2: Revision,
313 p2: Revision,
402 copy_actions: impl Iterator<Item = Action<'a>>,
314 copy_actions: impl Iterator<Item = Action<'a>>,
403 get_merge_case: impl Fn(&HgPath) -> MergeCase + Copy,
315 get_merge_case: impl Fn(&HgPath) -> MergeCase + Copy,
404 ) {
316 ) {
405 // Retrieve data computed in a previous iteration
317 // Retrieve data computed in a previous iteration
406 let p1_copies = match p1 {
318 let p1_copies = match p1 {
407 NULL_REVISION => None,
319 NULL_REVISION => None,
408 _ => get_and_clean_parent_copies(
320 _ => get_and_clean_parent_copies(
409 &mut self.all_copies,
321 &mut self.all_copies,
410 &mut self.children_count,
322 &mut self.children_count,
411 p1,
323 p1,
412 ), // will be None if the vertex is not to be traversed
324 ), // will be None if the vertex is not to be traversed
413 };
325 };
414 let p2_copies = match p2 {
326 let p2_copies = match p2 {
415 NULL_REVISION => None,
327 NULL_REVISION => None,
416 _ => get_and_clean_parent_copies(
328 _ => get_and_clean_parent_copies(
417 &mut self.all_copies,
329 &mut self.all_copies,
418 &mut self.children_count,
330 &mut self.children_count,
419 p2,
331 p2,
420 ), // will be None if the vertex is not to be traversed
332 ), // will be None if the vertex is not to be traversed
421 };
333 };
422 // combine it with data for that revision
334 // combine it with data for that revision
423 let (p1_copies, p2_copies) = chain_changes(
335 let (p1_copies, p2_copies) = chain_changes(
424 &mut self.path_map,
336 &mut self.path_map,
425 p1_copies,
337 p1_copies,
426 p2_copies,
338 p2_copies,
427 copy_actions,
339 copy_actions,
428 rev,
340 rev,
429 );
341 );
430 let copies = match (p1_copies, p2_copies) {
342 let copies = match (p1_copies, p2_copies) {
431 (None, None) => None,
343 (None, None) => None,
432 (c, None) => c,
344 (c, None) => c,
433 (None, c) => c,
345 (None, c) => c,
434 (Some(p1_copies), Some(p2_copies)) => Some(merge_copies_dict(
346 (Some(p1_copies), Some(p2_copies)) => Some(merge_copies_dict(
435 &self.path_map,
347 &self.path_map,
436 rev,
348 rev,
437 p2_copies,
349 p2_copies,
438 p1_copies,
350 p1_copies,
439 get_merge_case,
351 get_merge_case,
440 )),
352 )),
441 };
353 };
442 if let Some(c) = copies {
354 if let Some(c) = copies {
443 self.all_copies.insert(rev, c);
355 self.all_copies.insert(rev, c);
444 }
356 }
445 }
357 }
446
358
447 /// Drop intermediate data (such as which revision a copy was from) and
359 /// Drop intermediate data (such as which revision a copy was from) and
448 /// return the final mapping.
360 /// return the final mapping.
449 pub fn finish(mut self, target_rev: Revision) -> PathCopies {
361 pub fn finish(mut self, target_rev: Revision) -> PathCopies {
450 let tt_result = self
362 let tt_result = self
451 .all_copies
363 .all_copies
452 .remove(&target_rev)
364 .remove(&target_rev)
453 .expect("target revision was not processed");
365 .expect("target revision was not processed");
454 let mut result = PathCopies::default();
366 let mut result = PathCopies::default();
455 for (dest, tt_source) in tt_result {
367 for (dest, tt_source) in tt_result {
456 if let Some(path) = tt_source.path {
368 if let Some(path) = tt_source.path {
457 let path_dest = self.path_map.untokenize(dest).to_owned();
369 let path_dest = self.path_map.untokenize(dest).to_owned();
458 let path_path = self.path_map.untokenize(path).to_owned();
370 let path_path = self.path_map.untokenize(path).to_owned();
459 result.insert(path_dest, path_path);
371 result.insert(path_dest, path_path);
460 }
372 }
461 }
373 }
462 result
374 result
463 }
375 }
464 }
376 }
465
377
466 /// fetch previous computed information
378 /// fetch previous computed information
467 ///
379 ///
468 /// If no other children are expected to need this information, we drop it from
380 /// If no other children are expected to need this information, we drop it from
469 /// the cache.
381 /// the cache.
470 ///
382 ///
471 /// If parent is not part of the set we are expected to walk, return None.
383 /// If parent is not part of the set we are expected to walk, return None.
472 fn get_and_clean_parent_copies(
384 fn get_and_clean_parent_copies(
473 all_copies: &mut HashMap<Revision, InternalPathCopies>,
385 all_copies: &mut HashMap<Revision, InternalPathCopies>,
474 children_count: &mut HashMap<Revision, usize>,
386 children_count: &mut HashMap<Revision, usize>,
475 parent_rev: Revision,
387 parent_rev: Revision,
476 ) -> Option<InternalPathCopies> {
388 ) -> Option<InternalPathCopies> {
477 let count = children_count.get_mut(&parent_rev)?;
389 let count = children_count.get_mut(&parent_rev)?;
478 *count -= 1;
390 *count -= 1;
479 if *count == 0 {
391 if *count == 0 {
480 match all_copies.remove(&parent_rev) {
392 match all_copies.remove(&parent_rev) {
481 Some(c) => Some(c),
393 Some(c) => Some(c),
482 None => Some(InternalPathCopies::default()),
394 None => Some(InternalPathCopies::default()),
483 }
395 }
484 } else {
396 } else {
485 match all_copies.get(&parent_rev) {
397 match all_copies.get(&parent_rev) {
486 Some(c) => Some(c.clone()),
398 Some(c) => Some(c.clone()),
487 None => Some(InternalPathCopies::default()),
399 None => Some(InternalPathCopies::default()),
488 }
400 }
489 }
401 }
490 }
402 }
491
403
492 /// Combine ChangedFiles with some existing PathCopies information and return
404 /// Combine ChangedFiles with some existing PathCopies information and return
493 /// the result
405 /// the result
494 fn chain_changes<'a>(
406 fn chain_changes<'a>(
495 path_map: &mut TwoWayPathMap,
407 path_map: &mut TwoWayPathMap,
496 base_p1_copies: Option<InternalPathCopies>,
408 base_p1_copies: Option<InternalPathCopies>,
497 base_p2_copies: Option<InternalPathCopies>,
409 base_p2_copies: Option<InternalPathCopies>,
498 copy_actions: impl Iterator<Item = Action<'a>>,
410 copy_actions: impl Iterator<Item = Action<'a>>,
499 current_rev: Revision,
411 current_rev: Revision,
500 ) -> (Option<InternalPathCopies>, Option<InternalPathCopies>) {
412 ) -> (Option<InternalPathCopies>, Option<InternalPathCopies>) {
501 // Fast path the "nothing to do" case.
413 // Fast path the "nothing to do" case.
502 if let (None, None) = (&base_p1_copies, &base_p2_copies) {
414 if let (None, None) = (&base_p1_copies, &base_p2_copies) {
503 return (None, None);
415 return (None, None);
504 }
416 }
505
417
506 let mut p1_copies = base_p1_copies.clone();
418 let mut p1_copies = base_p1_copies.clone();
507 let mut p2_copies = base_p2_copies.clone();
419 let mut p2_copies = base_p2_copies.clone();
508 for action in copy_actions {
420 for action in copy_actions {
509 match action {
421 match action {
510 Action::CopiedFromP1(path_dest, path_source) => {
422 Action::CopiedFromP1(path_dest, path_source) => {
511 match &mut p1_copies {
423 match &mut p1_copies {
512 None => (), // This is not a vertex we should proceed.
424 None => (), // This is not a vertex we should proceed.
513 Some(copies) => add_one_copy(
425 Some(copies) => add_one_copy(
514 current_rev,
426 current_rev,
515 path_map,
427 path_map,
516 copies,
428 copies,
517 base_p1_copies.as_ref().unwrap(),
429 base_p1_copies.as_ref().unwrap(),
518 path_dest,
430 path_dest,
519 path_source,
431 path_source,
520 ),
432 ),
521 }
433 }
522 }
434 }
523 Action::CopiedFromP2(path_dest, path_source) => {
435 Action::CopiedFromP2(path_dest, path_source) => {
524 match &mut p2_copies {
436 match &mut p2_copies {
525 None => (), // This is not a vertex we should proceed.
437 None => (), // This is not a vertex we should proceed.
526 Some(copies) => add_one_copy(
438 Some(copies) => add_one_copy(
527 current_rev,
439 current_rev,
528 path_map,
440 path_map,
529 copies,
441 copies,
530 base_p2_copies.as_ref().unwrap(),
442 base_p2_copies.as_ref().unwrap(),
531 path_dest,
443 path_dest,
532 path_source,
444 path_source,
533 ),
445 ),
534 }
446 }
535 }
447 }
536 Action::Removed(deleted_path) => {
448 Action::Removed(deleted_path) => {
537 // We must drop copy information for removed file.
449 // We must drop copy information for removed file.
538 //
450 //
539 // We need to explicitly record them as dropped to
451 // We need to explicitly record them as dropped to
540 // propagate this information when merging two
452 // propagate this information when merging two
541 // InternalPathCopies object.
453 // InternalPathCopies object.
542 let deleted = path_map.tokenize(deleted_path);
454 let deleted = path_map.tokenize(deleted_path);
543
455
544 let p1_entry = match &mut p1_copies {
456 let p1_entry = match &mut p1_copies {
545 None => None,
457 None => None,
546 Some(copies) => match copies.entry(deleted) {
458 Some(copies) => match copies.entry(deleted) {
547 Entry::Occupied(e) => Some(e),
459 Entry::Occupied(e) => Some(e),
548 Entry::Vacant(_) => None,
460 Entry::Vacant(_) => None,
549 },
461 },
550 };
462 };
551 let p2_entry = match &mut p2_copies {
463 let p2_entry = match &mut p2_copies {
552 None => None,
464 None => None,
553 Some(copies) => match copies.entry(deleted) {
465 Some(copies) => match copies.entry(deleted) {
554 Entry::Occupied(e) => Some(e),
466 Entry::Occupied(e) => Some(e),
555 Entry::Vacant(_) => None,
467 Entry::Vacant(_) => None,
556 },
468 },
557 };
469 };
558
470
559 match (p1_entry, p2_entry) {
471 match (p1_entry, p2_entry) {
560 (None, None) => (),
472 (None, None) => (),
561 (Some(mut e), None) => {
473 (Some(mut e), None) => {
562 e.get_mut().mark_delete(current_rev)
474 e.get_mut().mark_delete(current_rev)
563 }
475 }
564 (None, Some(mut e)) => {
476 (None, Some(mut e)) => {
565 e.get_mut().mark_delete(current_rev)
477 e.get_mut().mark_delete(current_rev)
566 }
478 }
567 (Some(mut e1), Some(mut e2)) => {
479 (Some(mut e1), Some(mut e2)) => {
568 let cs1 = e1.get_mut();
480 let cs1 = e1.get_mut();
569 let cs2 = e2.get();
481 let cs2 = e2.get();
570 if cs1 == cs2 {
482 if cs1 == cs2 {
571 cs1.mark_delete(current_rev);
483 cs1.mark_delete(current_rev);
572 } else {
484 } else {
573 cs1.mark_delete_with_pair(current_rev, &cs2);
485 cs1.mark_delete_with_pair(current_rev, &cs2);
574 }
486 }
575 e2.insert(cs1.clone());
487 e2.insert(cs1.clone());
576 }
488 }
577 }
489 }
578 }
490 }
579 }
491 }
580 }
492 }
581 (p1_copies, p2_copies)
493 (p1_copies, p2_copies)
582 }
494 }
583
495
584 // insert one new copy information in an InternalPathCopies
496 // insert one new copy information in an InternalPathCopies
585 //
497 //
586 // This deal with chaining and overwrite.
498 // This deal with chaining and overwrite.
587 fn add_one_copy(
499 fn add_one_copy(
588 current_rev: Revision,
500 current_rev: Revision,
589 path_map: &mut TwoWayPathMap,
501 path_map: &mut TwoWayPathMap,
590 copies: &mut InternalPathCopies,
502 copies: &mut InternalPathCopies,
591 base_copies: &InternalPathCopies,
503 base_copies: &InternalPathCopies,
592 path_dest: &HgPath,
504 path_dest: &HgPath,
593 path_source: &HgPath,
505 path_source: &HgPath,
594 ) {
506 ) {
595 let dest = path_map.tokenize(path_dest);
507 let dest = path_map.tokenize(path_dest);
596 let source = path_map.tokenize(path_source);
508 let source = path_map.tokenize(path_source);
597 let entry;
509 let entry;
598 if let Some(v) = base_copies.get(&source) {
510 if let Some(v) = base_copies.get(&source) {
599 entry = match &v.path {
511 entry = match &v.path {
600 Some(path) => Some((*(path)).to_owned()),
512 Some(path) => Some((*(path)).to_owned()),
601 None => Some(source.to_owned()),
513 None => Some(source.to_owned()),
602 }
514 }
603 } else {
515 } else {
604 entry = Some(source.to_owned());
516 entry = Some(source.to_owned());
605 }
517 }
606 // Each new entry is introduced by the children, we
518 // Each new entry is introduced by the children, we
607 // record this information as we will need it to take
519 // record this information as we will need it to take
608 // the right decision when merging conflicting copy
520 // the right decision when merging conflicting copy
609 // information. See merge_copies_dict for details.
521 // information. See merge_copies_dict for details.
610 match copies.entry(dest) {
522 match copies.entry(dest) {
611 Entry::Vacant(slot) => {
523 Entry::Vacant(slot) => {
612 let ttpc = CopySource::new(current_rev, entry);
524 let ttpc = CopySource::new(current_rev, entry);
613 slot.insert(ttpc);
525 slot.insert(ttpc);
614 }
526 }
615 Entry::Occupied(mut slot) => {
527 Entry::Occupied(mut slot) => {
616 let ttpc = slot.get_mut();
528 let ttpc = slot.get_mut();
617 ttpc.overwrite(current_rev, entry);
529 ttpc.overwrite(current_rev, entry);
618 }
530 }
619 }
531 }
620 }
532 }
621
533
622 /// merge two copies-mapping together, minor and major
534 /// merge two copies-mapping together, minor and major
623 ///
535 ///
624 /// In case of conflict, value from "major" will be picked, unless in some
536 /// In case of conflict, value from "major" will be picked, unless in some
625 /// cases. See inline documentation for details.
537 /// cases. See inline documentation for details.
626 fn merge_copies_dict(
538 fn merge_copies_dict(
627 path_map: &TwoWayPathMap,
539 path_map: &TwoWayPathMap,
628 current_merge: Revision,
540 current_merge: Revision,
629 minor: InternalPathCopies,
541 minor: InternalPathCopies,
630 major: InternalPathCopies,
542 major: InternalPathCopies,
631 get_merge_case: impl Fn(&HgPath) -> MergeCase + Copy,
543 get_merge_case: impl Fn(&HgPath) -> MergeCase + Copy,
632 ) -> InternalPathCopies {
544 ) -> InternalPathCopies {
633 use crate::utils::{ordmap_union_with_merge, MergeResult};
545 use crate::utils::{ordmap_union_with_merge, MergeResult};
634
546
635 ordmap_union_with_merge(minor, major, |&dest, src_minor, src_major| {
547 ordmap_union_with_merge(minor, major, |&dest, src_minor, src_major| {
636 let (pick, overwrite) = compare_value(
548 let (pick, overwrite) = compare_value(
637 current_merge,
549 current_merge,
638 || get_merge_case(path_map.untokenize(dest)),
550 || get_merge_case(path_map.untokenize(dest)),
639 src_minor,
551 src_minor,
640 src_major,
552 src_major,
641 );
553 );
642 if overwrite {
554 if overwrite {
643 let (winner, loser) = match pick {
555 let (winner, loser) = match pick {
644 MergePick::Major | MergePick::Any => (src_major, src_minor),
556 MergePick::Major | MergePick::Any => (src_major, src_minor),
645 MergePick::Minor => (src_minor, src_major),
557 MergePick::Minor => (src_minor, src_major),
646 };
558 };
647 MergeResult::UseNewValue(CopySource::new_from_merge(
559 MergeResult::UseNewValue(CopySource::new_from_merge(
648 current_merge,
560 current_merge,
649 winner,
561 winner,
650 loser,
562 loser,
651 ))
563 ))
652 } else {
564 } else {
653 match pick {
565 match pick {
654 MergePick::Any | MergePick::Major => {
566 MergePick::Any | MergePick::Major => {
655 MergeResult::UseRightValue
567 MergeResult::UseRightValue
656 }
568 }
657 MergePick::Minor => MergeResult::UseLeftValue,
569 MergePick::Minor => MergeResult::UseLeftValue,
658 }
570 }
659 }
571 }
660 })
572 })
661 }
573 }
662
574
663 /// represent the side that should prevail when merging two
575 /// represent the side that should prevail when merging two
664 /// InternalPathCopies
576 /// InternalPathCopies
665 #[derive(Debug, PartialEq)]
577 #[derive(Debug, PartialEq)]
666 enum MergePick {
578 enum MergePick {
667 /// The "major" (p1) side prevails
579 /// The "major" (p1) side prevails
668 Major,
580 Major,
669 /// The "minor" (p2) side prevails
581 /// The "minor" (p2) side prevails
670 Minor,
582 Minor,
671 /// Any side could be used (because they are the same)
583 /// Any side could be used (because they are the same)
672 Any,
584 Any,
673 }
585 }
674
586
675 /// decide which side prevails in case of conflicting values
587 /// decide which side prevails in case of conflicting values
676 #[allow(clippy::if_same_then_else)]
588 #[allow(clippy::if_same_then_else)]
677 fn compare_value(
589 fn compare_value(
678 current_merge: Revision,
590 current_merge: Revision,
679 merge_case_for_dest: impl Fn() -> MergeCase,
591 merge_case_for_dest: impl Fn() -> MergeCase,
680 src_minor: &CopySource,
592 src_minor: &CopySource,
681 src_major: &CopySource,
593 src_major: &CopySource,
682 ) -> (MergePick, bool) {
594 ) -> (MergePick, bool) {
683 if src_major == src_minor {
595 if src_major == src_minor {
684 (MergePick::Any, false)
596 (MergePick::Any, false)
685 } else if src_major.rev == current_merge {
597 } else if src_major.rev == current_merge {
686 // minor is different according to per minor == major check earlier
598 // minor is different according to per minor == major check earlier
687 debug_assert!(src_minor.rev != current_merge);
599 debug_assert!(src_minor.rev != current_merge);
688
600
689 // The last value comes the current merge, this value -will- win
601 // The last value comes the current merge, this value -will- win
690 // eventually.
602 // eventually.
691 (MergePick::Major, true)
603 (MergePick::Major, true)
692 } else if src_minor.rev == current_merge {
604 } else if src_minor.rev == current_merge {
693 // The last value comes the current merge, this value -will- win
605 // The last value comes the current merge, this value -will- win
694 // eventually.
606 // eventually.
695 (MergePick::Minor, true)
607 (MergePick::Minor, true)
696 } else if src_major.path == src_minor.path {
608 } else if src_major.path == src_minor.path {
697 debug_assert!(src_major.rev != src_major.rev);
609 debug_assert!(src_major.rev != src_major.rev);
698 // we have the same value, but from other source;
610 // we have the same value, but from other source;
699 if src_major.is_overwritten_by(src_minor) {
611 if src_major.is_overwritten_by(src_minor) {
700 (MergePick::Minor, false)
612 (MergePick::Minor, false)
701 } else if src_minor.is_overwritten_by(src_major) {
613 } else if src_minor.is_overwritten_by(src_major) {
702 (MergePick::Major, false)
614 (MergePick::Major, false)
703 } else {
615 } else {
704 (MergePick::Any, true)
616 (MergePick::Any, true)
705 }
617 }
706 } else {
618 } else {
707 debug_assert!(src_major.rev != src_major.rev);
619 debug_assert!(src_major.rev != src_major.rev);
708 let action = merge_case_for_dest();
620 let action = merge_case_for_dest();
709 if src_minor.path.is_some()
621 if src_minor.path.is_some()
710 && src_major.path.is_none()
622 && src_major.path.is_none()
711 && action == MergeCase::Salvaged
623 && action == MergeCase::Salvaged
712 {
624 {
713 // If the file is "deleted" in the major side but was
625 // If the file is "deleted" in the major side but was
714 // salvaged by the merge, we keep the minor side alive
626 // salvaged by the merge, we keep the minor side alive
715 (MergePick::Minor, true)
627 (MergePick::Minor, true)
716 } else if src_major.path.is_some()
628 } else if src_major.path.is_some()
717 && src_minor.path.is_none()
629 && src_minor.path.is_none()
718 && action == MergeCase::Salvaged
630 && action == MergeCase::Salvaged
719 {
631 {
720 // If the file is "deleted" in the minor side but was
632 // If the file is "deleted" in the minor side but was
721 // salvaged by the merge, unconditionnaly preserve the
633 // salvaged by the merge, unconditionnaly preserve the
722 // major side.
634 // major side.
723 (MergePick::Major, true)
635 (MergePick::Major, true)
724 } else if src_minor.is_overwritten_by(src_major) {
636 } else if src_minor.is_overwritten_by(src_major) {
725 // The information from the minor version are strictly older than
637 // The information from the minor version are strictly older than
726 // the major version
638 // the major version
727 if action == MergeCase::Merged {
639 if action == MergeCase::Merged {
728 // If the file was actively merged, its means some non-copy
640 // If the file was actively merged, its means some non-copy
729 // activity happened on the other branch. It
641 // activity happened on the other branch. It
730 // mean the older copy information are still relevant.
642 // mean the older copy information are still relevant.
731 //
643 //
732 // The major side wins such conflict.
644 // The major side wins such conflict.
733 (MergePick::Major, true)
645 (MergePick::Major, true)
734 } else {
646 } else {
735 // No activity on the minor branch, pick the newer one.
647 // No activity on the minor branch, pick the newer one.
736 (MergePick::Major, false)
648 (MergePick::Major, false)
737 }
649 }
738 } else if src_major.is_overwritten_by(src_minor) {
650 } else if src_major.is_overwritten_by(src_minor) {
739 if action == MergeCase::Merged {
651 if action == MergeCase::Merged {
740 // If the file was actively merged, its means some non-copy
652 // If the file was actively merged, its means some non-copy
741 // activity happened on the other branch. It
653 // activity happened on the other branch. It
742 // mean the older copy information are still relevant.
654 // mean the older copy information are still relevant.
743 //
655 //
744 // The major side wins such conflict.
656 // The major side wins such conflict.
745 (MergePick::Major, true)
657 (MergePick::Major, true)
746 } else {
658 } else {
747 // No activity on the minor branch, pick the newer one.
659 // No activity on the minor branch, pick the newer one.
748 (MergePick::Minor, false)
660 (MergePick::Minor, false)
749 }
661 }
750 } else if src_minor.path.is_none() {
662 } else if src_minor.path.is_none() {
751 // the minor side has no relevant information, pick the alive one
663 // the minor side has no relevant information, pick the alive one
752 (MergePick::Major, true)
664 (MergePick::Major, true)
753 } else if src_major.path.is_none() {
665 } else if src_major.path.is_none() {
754 // the major side has no relevant information, pick the alive one
666 // the major side has no relevant information, pick the alive one
755 (MergePick::Minor, true)
667 (MergePick::Minor, true)
756 } else {
668 } else {
757 // by default the major side wins
669 // by default the major side wins
758 (MergePick::Major, true)
670 (MergePick::Major, true)
759 }
671 }
760 }
672 }
761 }
673 }
General Comments 0
You need to be logged in to leave comments. Login now