##// END OF EJS Templates
upstream » mercurial-mirror
RSS

Clone from https://www.mercurial-scm.org/repo/hg-all

copies-rust: track "overwrites" directly within CopySource...
marmoute -
r47315:0d840b9d default
parent child Browse files
Show More
Show file before | Show file after | Hide comments
@@ -1,924 +1,949 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 im_rc::ordmap::DiffItem;
6 use im_rc::ordmap::DiffItem;
7 use im_rc::ordmap::Entry;
7 use im_rc::ordmap::Entry;
8 use im_rc::ordmap::OrdMap;
8 use im_rc::ordmap::OrdMap;
9
9
10 use std::cmp::Ordering;
10 use std::cmp::Ordering;
11 use std::collections::HashMap;
11 use std::collections::HashMap;
12 use std::collections::HashSet;
12 use std::convert::TryInto;
13 use std::convert::TryInto;
13
14
14 pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
15 pub type PathCopies = HashMap<HgPathBuf, HgPathBuf>;
15
16
16 type PathToken = usize;
17 type PathToken = usize;
17
18
18 #[derive(Clone, Debug, PartialEq)]
19 #[derive(Clone, Debug, PartialEq)]
19 struct CopySource {
20 struct CopySource {
20 /// revision at which the copy information was added
21 /// revision at which the copy information was added
21 rev: Revision,
22 rev: Revision,
22 /// the copy source, (Set to None in case of deletion of the associated
23 /// the copy source, (Set to None in case of deletion of the associated
23 /// key)
24 /// key)
24 path: Option<PathToken>,
25 path: Option<PathToken>,
26 /// a set of previous `CopySource.rev` value directly or indirectly
27 /// overwritten by this one.
28 overwritten: HashSet<Revision>,
25 }
29 }
26
30
27 impl CopySource {
31 impl CopySource {
28 /// create a new CopySource
32 /// create a new CopySource
29 ///
33 ///
30 /// Use this when no previous copy source existed.
34 /// Use this when no previous copy source existed.
31 fn new(rev: Revision, path: Option<PathToken>) -> Self {
35 fn new(rev: Revision, path: Option<PathToken>) -> Self {
32 Self { rev, path }
36 Self {
37 rev,
38 path,
39 overwritten: HashSet::new(),
40 }
33 }
41 }
34
42
35 /// create a new CopySource from merging two others
43 /// create a new CopySource from merging two others
36 ///
44 ///
37 /// Use this when merging two InternalPathCopies requires active merging of
45 /// Use this when merging two InternalPathCopies requires active merging of
38 /// some entries.
46 /// some entries.
39 fn new_from_merge(rev: Revision, winner: &Self, loser: &Self) -> Self {
47 fn new_from_merge(rev: Revision, winner: &Self, loser: &Self) -> Self {
48 let mut overwritten = HashSet::new();
49 overwritten.extend(winner.overwritten.iter().copied());
50 overwritten.extend(loser.overwritten.iter().copied());
51 overwritten.insert(winner.rev);
52 overwritten.insert(loser.rev);
40 Self {
53 Self {
41 rev,
54 rev,
42 path: winner.path,
55 path: winner.path,
56 overwritten: overwritten,
43 }
57 }
44 }
58 }
45
59
46 /// Update the value of a pre-existing CopySource
60 /// Update the value of a pre-existing CopySource
47 ///
61 ///
48 /// Use this when recording copy information from parent → child edges
62 /// Use this when recording copy information from parent → child edges
49 fn overwrite(&mut self, rev: Revision, path: Option<PathToken>) {
63 fn overwrite(&mut self, rev: Revision, path: Option<PathToken>) {
64 self.overwritten.insert(self.rev);
50 self.rev = rev;
65 self.rev = rev;
51 self.path = path;
66 self.path = path;
52 }
67 }
53
68
54 /// Mark pre-existing copy information as "dropped" by a file deletion
69 /// Mark pre-existing copy information as "dropped" by a file deletion
55 ///
70 ///
56 /// Use this when recording copy information from parent → child edges
71 /// Use this when recording copy information from parent → child edges
57 fn mark_delete(&mut self, rev: Revision) {
72 fn mark_delete(&mut self, rev: Revision) {
73 self.overwritten.insert(self.rev);
58 self.rev = rev;
74 self.rev = rev;
59 self.path = None;
75 self.path = None;
60 }
76 }
77
78 fn is_overwritten_by(&self, other: &Self) -> bool {
79 other.overwritten.contains(&self.rev)
80 }
61 }
81 }
62
82
63 /// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)
83 /// maps CopyDestination to Copy Source (+ a "timestamp" for the operation)
64 type InternalPathCopies = OrdMap<PathToken, CopySource>;
84 type InternalPathCopies = OrdMap<PathToken, CopySource>;
65
85
66 /// hold parent 1, parent 2 and relevant files actions.
86 /// hold parent 1, parent 2 and relevant files actions.
67 pub type RevInfo<'a> = (Revision, Revision, ChangedFiles<'a>);
87 pub type RevInfo<'a> = (Revision, Revision, ChangedFiles<'a>);
68
88
69 /// represent the files affected by a changesets
89 /// represent the files affected by a changesets
70 ///
90 ///
71 /// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
91 /// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
72 /// all the data categories tracked by it.
92 /// all the data categories tracked by it.
73 /// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
93 /// This hold a subset of mercurial.metadata.ChangingFiles as we do not need
74 /// all the data categories tracked by it.
94 /// all the data categories tracked by it.
75 pub struct ChangedFiles<'a> {
95 pub struct ChangedFiles<'a> {
76 nb_items: u32,
96 nb_items: u32,
77 index: &'a [u8],
97 index: &'a [u8],
78 data: &'a [u8],
98 data: &'a [u8],
79 }
99 }
80
100
81 /// Represent active changes that affect the copy tracing.
101 /// Represent active changes that affect the copy tracing.
82 enum Action<'a> {
102 enum Action<'a> {
83 /// The parent ? children edge is removing a file
103 /// The parent ? children edge is removing a file
84 ///
104 ///
85 /// (actually, this could be the edge from the other parent, but it does
105 /// (actually, this could be the edge from the other parent, but it does
86 /// not matters)
106 /// not matters)
87 Removed(&'a HgPath),
107 Removed(&'a HgPath),
88 /// The parent ? children edge introduce copy information between (dest,
108 /// The parent ? children edge introduce copy information between (dest,
89 /// source)
109 /// source)
90 Copied(&'a HgPath, &'a HgPath),
110 Copied(&'a HgPath, &'a HgPath),
91 }
111 }
92
112
93 /// This express the possible "special" case we can get in a merge
113 /// This express the possible "special" case we can get in a merge
94 ///
114 ///
95 /// See mercurial/metadata.py for details on these values.
115 /// See mercurial/metadata.py for details on these values.
96 #[derive(PartialEq)]
116 #[derive(PartialEq)]
97 enum MergeCase {
117 enum MergeCase {
98 /// Merged: file had history on both side that needed to be merged
118 /// Merged: file had history on both side that needed to be merged
99 Merged,
119 Merged,
100 /// Salvaged: file was candidate for deletion, but survived the merge
120 /// Salvaged: file was candidate for deletion, but survived the merge
101 Salvaged,
121 Salvaged,
102 /// Normal: Not one of the two cases above
122 /// Normal: Not one of the two cases above
103 Normal,
123 Normal,
104 }
124 }
105
125
106 type FileChange<'a> = (u8, &'a HgPath, &'a HgPath);
126 type FileChange<'a> = (u8, &'a HgPath, &'a HgPath);
107
127
108 const EMPTY: &[u8] = b"";
128 const EMPTY: &[u8] = b"";
109 const COPY_MASK: u8 = 3;
129 const COPY_MASK: u8 = 3;
110 const P1_COPY: u8 = 2;
130 const P1_COPY: u8 = 2;
111 const P2_COPY: u8 = 3;
131 const P2_COPY: u8 = 3;
112 const ACTION_MASK: u8 = 28;
132 const ACTION_MASK: u8 = 28;
113 const REMOVED: u8 = 12;
133 const REMOVED: u8 = 12;
114 const MERGED: u8 = 8;
134 const MERGED: u8 = 8;
115 const SALVAGED: u8 = 16;
135 const SALVAGED: u8 = 16;
116
136
117 impl<'a> ChangedFiles<'a> {
137 impl<'a> ChangedFiles<'a> {
118 const INDEX_START: usize = 4;
138 const INDEX_START: usize = 4;
119 const ENTRY_SIZE: u32 = 9;
139 const ENTRY_SIZE: u32 = 9;
120 const FILENAME_START: u32 = 1;
140 const FILENAME_START: u32 = 1;
121 const COPY_SOURCE_START: u32 = 5;
141 const COPY_SOURCE_START: u32 = 5;
122
142
123 pub fn new(data: &'a [u8]) -> Self {
143 pub fn new(data: &'a [u8]) -> Self {
124 assert!(
144 assert!(
125 data.len() >= 4,
145 data.len() >= 4,
126 "data size ({}) is too small to contain the header (4)",
146 "data size ({}) is too small to contain the header (4)",
127 data.len()
147 data.len()
128 );
148 );
129 let nb_items_raw: [u8; 4] = (&data[0..=3])
149 let nb_items_raw: [u8; 4] = (&data[0..=3])
130 .try_into()
150 .try_into()
131 .expect("failed to turn 4 bytes into 4 bytes");
151 .expect("failed to turn 4 bytes into 4 bytes");
132 let nb_items = u32::from_be_bytes(nb_items_raw);
152 let nb_items = u32::from_be_bytes(nb_items_raw);
133
153
134 let index_size = (nb_items * Self::ENTRY_SIZE) as usize;
154 let index_size = (nb_items * Self::ENTRY_SIZE) as usize;
135 let index_end = Self::INDEX_START + index_size;
155 let index_end = Self::INDEX_START + index_size;
136
156
137 assert!(
157 assert!(
138 data.len() >= index_end,
158 data.len() >= index_end,
139 "data size ({}) is too small to fit the index_data ({})",
159 "data size ({}) is too small to fit the index_data ({})",
140 data.len(),
160 data.len(),
141 index_end
161 index_end
142 );
162 );
143
163
144 let ret = ChangedFiles {
164 let ret = ChangedFiles {
145 nb_items,
165 nb_items,
146 index: &data[Self::INDEX_START..index_end],
166 index: &data[Self::INDEX_START..index_end],
147 data: &data[index_end..],
167 data: &data[index_end..],
148 };
168 };
149 let max_data = ret.filename_end(nb_items - 1) as usize;
169 let max_data = ret.filename_end(nb_items - 1) as usize;
150 assert!(
170 assert!(
151 ret.data.len() >= max_data,
171 ret.data.len() >= max_data,
152 "data size ({}) is too small to fit all data ({})",
172 "data size ({}) is too small to fit all data ({})",
153 data.len(),
173 data.len(),
154 index_end + max_data
174 index_end + max_data
155 );
175 );
156 ret
176 ret
157 }
177 }
158
178
159 pub fn new_empty() -> Self {
179 pub fn new_empty() -> Self {
160 ChangedFiles {
180 ChangedFiles {
161 nb_items: 0,
181 nb_items: 0,
162 index: EMPTY,
182 index: EMPTY,
163 data: EMPTY,
183 data: EMPTY,
164 }
184 }
165 }
185 }
166
186
167 /// internal function to return an individual entry at a given index
187 /// internal function to return an individual entry at a given index
168 fn entry(&'a self, idx: u32) -> FileChange<'a> {
188 fn entry(&'a self, idx: u32) -> FileChange<'a> {
169 if idx >= self.nb_items {
189 if idx >= self.nb_items {
170 panic!(
190 panic!(
171 "index for entry is higher that the number of file {} >= {}",
191 "index for entry is higher that the number of file {} >= {}",
172 idx, self.nb_items
192 idx, self.nb_items
173 )
193 )
174 }
194 }
175 let flags = self.flags(idx);
195 let flags = self.flags(idx);
176 let filename = self.filename(idx);
196 let filename = self.filename(idx);
177 let copy_idx = self.copy_idx(idx);
197 let copy_idx = self.copy_idx(idx);
178 let copy_source = self.filename(copy_idx);
198 let copy_source = self.filename(copy_idx);
179 (flags, filename, copy_source)
199 (flags, filename, copy_source)
180 }
200 }
181
201
182 /// internal function to return the filename of the entry at a given index
202 /// internal function to return the filename of the entry at a given index
183 fn filename(&self, idx: u32) -> &HgPath {
203 fn filename(&self, idx: u32) -> &HgPath {
184 let filename_start;
204 let filename_start;
185 if idx == 0 {
205 if idx == 0 {
186 filename_start = 0;
206 filename_start = 0;
187 } else {
207 } else {
188 filename_start = self.filename_end(idx - 1)
208 filename_start = self.filename_end(idx - 1)
189 }
209 }
190 let filename_end = self.filename_end(idx);
210 let filename_end = self.filename_end(idx);
191 let filename_start = filename_start as usize;
211 let filename_start = filename_start as usize;
192 let filename_end = filename_end as usize;
212 let filename_end = filename_end as usize;
193 HgPath::new(&self.data[filename_start..filename_end])
213 HgPath::new(&self.data[filename_start..filename_end])
194 }
214 }
195
215
196 /// internal function to return the flag field of the entry at a given
216 /// internal function to return the flag field of the entry at a given
197 /// index
217 /// index
198 fn flags(&self, idx: u32) -> u8 {
218 fn flags(&self, idx: u32) -> u8 {
199 let idx = idx as usize;
219 let idx = idx as usize;
200 self.index[idx * (Self::ENTRY_SIZE as usize)]
220 self.index[idx * (Self::ENTRY_SIZE as usize)]
201 }
221 }
202
222
203 /// internal function to return the end of a filename part at a given index
223 /// internal function to return the end of a filename part at a given index
204 fn filename_end(&self, idx: u32) -> u32 {
224 fn filename_end(&self, idx: u32) -> u32 {
205 let start = (idx * Self::ENTRY_SIZE) + Self::FILENAME_START;
225 let start = (idx * Self::ENTRY_SIZE) + Self::FILENAME_START;
206 let end = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
226 let end = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
207 let start = start as usize;
227 let start = start as usize;
208 let end = end as usize;
228 let end = end as usize;
209 let raw = (&self.index[start..end])
229 let raw = (&self.index[start..end])
210 .try_into()
230 .try_into()
211 .expect("failed to turn 4 bytes into 4 bytes");
231 .expect("failed to turn 4 bytes into 4 bytes");
212 u32::from_be_bytes(raw)
232 u32::from_be_bytes(raw)
213 }
233 }
214
234
215 /// internal function to return index of the copy source of the entry at a
235 /// internal function to return index of the copy source of the entry at a
216 /// given index
236 /// given index
217 fn copy_idx(&self, idx: u32) -> u32 {
237 fn copy_idx(&self, idx: u32) -> u32 {
218 let start = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
238 let start = (idx * Self::ENTRY_SIZE) + Self::COPY_SOURCE_START;
219 let end = (idx + 1) * Self::ENTRY_SIZE;
239 let end = (idx + 1) * Self::ENTRY_SIZE;
220 let start = start as usize;
240 let start = start as usize;
221 let end = end as usize;
241 let end = end as usize;
222 let raw = (&self.index[start..end])
242 let raw = (&self.index[start..end])
223 .try_into()
243 .try_into()
224 .expect("failed to turn 4 bytes into 4 bytes");
244 .expect("failed to turn 4 bytes into 4 bytes");
225 u32::from_be_bytes(raw)
245 u32::from_be_bytes(raw)
226 }
246 }
227
247
228 /// Return an iterator over all the `Action` in this instance.
248 /// Return an iterator over all the `Action` in this instance.
229 fn iter_actions(&self, parent: Parent) -> ActionsIterator {
249 fn iter_actions(&self, parent: Parent) -> ActionsIterator {
230 ActionsIterator {
250 ActionsIterator {
231 changes: &self,
251 changes: &self,
232 parent: parent,
252 parent: parent,
233 current: 0,
253 current: 0,
234 }
254 }
235 }
255 }
236
256
237 /// return the MergeCase value associated with a filename
257 /// return the MergeCase value associated with a filename
238 fn get_merge_case(&self, path: &HgPath) -> MergeCase {
258 fn get_merge_case(&self, path: &HgPath) -> MergeCase {
239 if self.nb_items == 0 {
259 if self.nb_items == 0 {
240 return MergeCase::Normal;
260 return MergeCase::Normal;
241 }
261 }
242 let mut low_part = 0;
262 let mut low_part = 0;
243 let mut high_part = self.nb_items;
263 let mut high_part = self.nb_items;
244
264
245 while low_part < high_part {
265 while low_part < high_part {
246 let cursor = (low_part + high_part - 1) / 2;
266 let cursor = (low_part + high_part - 1) / 2;
247 let (flags, filename, _source) = self.entry(cursor);
267 let (flags, filename, _source) = self.entry(cursor);
248 match path.cmp(filename) {
268 match path.cmp(filename) {
249 Ordering::Less => low_part = cursor + 1,
269 Ordering::Less => low_part = cursor + 1,
250 Ordering::Greater => high_part = cursor,
270 Ordering::Greater => high_part = cursor,
251 Ordering::Equal => {
271 Ordering::Equal => {
252 return match flags & ACTION_MASK {
272 return match flags & ACTION_MASK {
253 MERGED => MergeCase::Merged,
273 MERGED => MergeCase::Merged,
254 SALVAGED => MergeCase::Salvaged,
274 SALVAGED => MergeCase::Salvaged,
255 _ => MergeCase::Normal,
275 _ => MergeCase::Normal,
256 };
276 };
257 }
277 }
258 }
278 }
259 }
279 }
260 MergeCase::Normal
280 MergeCase::Normal
261 }
281 }
262 }
282 }
263
283
264 /// A struct responsible for answering "is X ancestors of Y" quickly
284 /// A struct responsible for answering "is X ancestors of Y" quickly
265 ///
285 ///
266 /// The structure will delegate ancestors call to a callback, and cache the
286 /// The structure will delegate ancestors call to a callback, and cache the
267 /// result.
287 /// result.
268 #[derive(Debug)]
288 #[derive(Debug)]
269 struct AncestorOracle<'a, A: Fn(Revision, Revision) -> bool> {
289 struct AncestorOracle<'a, A: Fn(Revision, Revision) -> bool> {
270 inner: &'a A,
290 inner: &'a A,
271 pairs: HashMap<(Revision, Revision), bool>,
291 pairs: HashMap<(Revision, Revision), bool>,
272 }
292 }
273
293
274 impl<'a, A: Fn(Revision, Revision) -> bool> AncestorOracle<'a, A> {
294 impl<'a, A: Fn(Revision, Revision) -> bool> AncestorOracle<'a, A> {
275 fn new(func: &'a A) -> Self {
295 fn new(func: &'a A) -> Self {
276 Self {
296 Self {
277 inner: func,
297 inner: func,
278 pairs: HashMap::default(),
298 pairs: HashMap::default(),
279 }
299 }
280 }
300 }
281
301
282 fn record_overwrite(&mut self, anc: Revision, desc: Revision) {
302 fn record_overwrite(&mut self, anc: Revision, desc: Revision) {
283 self.pairs.insert((anc, desc), true);
303 self.pairs.insert((anc, desc), true);
284 }
304 }
285
305
286 /// returns `true` if `anc` is an ancestors of `desc`, `false` otherwise
306 /// returns `true` if `anc` is an ancestors of `desc`, `false` otherwise
287 fn is_overwrite(&mut self, anc: Revision, desc: Revision) -> bool {
307 fn is_overwrite(&mut self, anc: Revision, desc: Revision) -> bool {
288 if anc > desc {
308 if anc > desc {
289 false
309 false
290 } else if anc == desc {
310 } else if anc == desc {
291 true
311 true
292 } else {
312 } else {
293 if let Some(b) = self.pairs.get(&(anc, desc)) {
313 if let Some(b) = self.pairs.get(&(anc, desc)) {
294 *b
314 *b
295 } else {
315 } else {
296 let b = (self.inner)(anc, desc);
316 let b = (self.inner)(anc, desc);
297 self.pairs.insert((anc, desc), b);
317 self.pairs.insert((anc, desc), b);
298 b
318 b
299 }
319 }
300 }
320 }
301 }
321 }
302 }
322 }
303
323
304 struct ActionsIterator<'a> {
324 struct ActionsIterator<'a> {
305 changes: &'a ChangedFiles<'a>,
325 changes: &'a ChangedFiles<'a>,
306 parent: Parent,
326 parent: Parent,
307 current: u32,
327 current: u32,
308 }
328 }
309
329
310 impl<'a> Iterator for ActionsIterator<'a> {
330 impl<'a> Iterator for ActionsIterator<'a> {
311 type Item = Action<'a>;
331 type Item = Action<'a>;
312
332
313 fn next(&mut self) -> Option<Action<'a>> {
333 fn next(&mut self) -> Option<Action<'a>> {
314 let copy_flag = match self.parent {
334 let copy_flag = match self.parent {
315 Parent::FirstParent => P1_COPY,
335 Parent::FirstParent => P1_COPY,
316 Parent::SecondParent => P2_COPY,
336 Parent::SecondParent => P2_COPY,
317 };
337 };
318 while self.current < self.changes.nb_items {
338 while self.current < self.changes.nb_items {
319 let (flags, file, source) = self.changes.entry(self.current);
339 let (flags, file, source) = self.changes.entry(self.current);
320 self.current += 1;
340 self.current += 1;
321 if (flags & ACTION_MASK) == REMOVED {
341 if (flags & ACTION_MASK) == REMOVED {
322 return Some(Action::Removed(file));
342 return Some(Action::Removed(file));
323 }
343 }
324 let copy = flags & COPY_MASK;
344 let copy = flags & COPY_MASK;
325 if copy == copy_flag {
345 if copy == copy_flag {
326 return Some(Action::Copied(file, source));
346 return Some(Action::Copied(file, source));
327 }
347 }
328 }
348 }
329 return None;
349 return None;
330 }
350 }
331 }
351 }
332
352
333 /// A small struct whose purpose is to ensure lifetime of bytes referenced in
353 /// A small struct whose purpose is to ensure lifetime of bytes referenced in
334 /// ChangedFiles
354 /// ChangedFiles
335 ///
355 ///
336 /// It is passed to the RevInfoMaker callback who can assign any necessary
356 /// It is passed to the RevInfoMaker callback who can assign any necessary
337 /// content to the `data` attribute. The copy tracing code is responsible for
357 /// content to the `data` attribute. The copy tracing code is responsible for
338 /// keeping the DataHolder alive at least as long as the ChangedFiles object.
358 /// keeping the DataHolder alive at least as long as the ChangedFiles object.
339 pub struct DataHolder<D> {
359 pub struct DataHolder<D> {
340 /// RevInfoMaker callback should assign data referenced by the
360 /// RevInfoMaker callback should assign data referenced by the
341 /// ChangedFiles struct it return to this attribute. The DataHolder
361 /// ChangedFiles struct it return to this attribute. The DataHolder
342 /// lifetime will be at least as long as the ChangedFiles one.
362 /// lifetime will be at least as long as the ChangedFiles one.
343 pub data: Option<D>,
363 pub data: Option<D>,
344 }
364 }
345
365
346 pub type RevInfoMaker<'a, D> =
366 pub type RevInfoMaker<'a, D> =
347 Box<dyn for<'r> Fn(Revision, &'r mut DataHolder<D>) -> RevInfo<'r> + 'a>;
367 Box<dyn for<'r> Fn(Revision, &'r mut DataHolder<D>) -> RevInfo<'r> + 'a>;
348
368
349 /// enum used to carry information about the parent → child currently processed
369 /// enum used to carry information about the parent → child currently processed
350 #[derive(Copy, Clone, Debug)]
370 #[derive(Copy, Clone, Debug)]
351 enum Parent {
371 enum Parent {
352 /// The `p1(x) → x` edge
372 /// The `p1(x) → x` edge
353 FirstParent,
373 FirstParent,
354 /// The `p2(x) → x` edge
374 /// The `p2(x) → x` edge
355 SecondParent,
375 SecondParent,
356 }
376 }
357
377
358 /// A small "tokenizer" responsible of turning full HgPath into lighter
378 /// A small "tokenizer" responsible of turning full HgPath into lighter
359 /// PathToken
379 /// PathToken
360 ///
380 ///
361 /// Dealing with small object, like integer is much faster, so HgPath input are
381 /// Dealing with small object, like integer is much faster, so HgPath input are
362 /// turned into integer "PathToken" and converted back in the end.
382 /// turned into integer "PathToken" and converted back in the end.
363 #[derive(Clone, Debug, Default)]
383 #[derive(Clone, Debug, Default)]
364 struct TwoWayPathMap {
384 struct TwoWayPathMap {
365 token: HashMap<HgPathBuf, PathToken>,
385 token: HashMap<HgPathBuf, PathToken>,
366 path: Vec<HgPathBuf>,
386 path: Vec<HgPathBuf>,
367 }
387 }
368
388
369 impl TwoWayPathMap {
389 impl TwoWayPathMap {
370 fn tokenize(&mut self, path: &HgPath) -> PathToken {
390 fn tokenize(&mut self, path: &HgPath) -> PathToken {
371 match self.token.get(path) {
391 match self.token.get(path) {
372 Some(a) => *a,
392 Some(a) => *a,
373 None => {
393 None => {
374 let a = self.token.len();
394 let a = self.token.len();
375 let buf = path.to_owned();
395 let buf = path.to_owned();
376 self.path.push(buf.clone());
396 self.path.push(buf.clone());
377 self.token.insert(buf, a);
397 self.token.insert(buf, a);
378 a
398 a
379 }
399 }
380 }
400 }
381 }
401 }
382
402
383 fn untokenize(&self, token: PathToken) -> &HgPathBuf {
403 fn untokenize(&self, token: PathToken) -> &HgPathBuf {
384 assert!(token < self.path.len(), format!("Unknown token: {}", token));
404 assert!(token < self.path.len(), format!("Unknown token: {}", token));
385 &self.path[token]
405 &self.path[token]
386 }
406 }
387 }
407 }
388
408
389 /// Same as mercurial.copies._combine_changeset_copies, but in Rust.
409 /// Same as mercurial.copies._combine_changeset_copies, but in Rust.
390 ///
410 ///
391 /// Arguments are:
411 /// Arguments are:
392 ///
412 ///
393 /// revs: all revisions to be considered
413 /// revs: all revisions to be considered
394 /// children: a {parent ? [childrens]} mapping
414 /// children: a {parent ? [childrens]} mapping
395 /// target_rev: the final revision we are combining copies to
415 /// target_rev: the final revision we are combining copies to
396 /// rev_info(rev): callback to get revision information:
416 /// rev_info(rev): callback to get revision information:
397 /// * first parent
417 /// * first parent
398 /// * second parent
418 /// * second parent
399 /// * ChangedFiles
419 /// * ChangedFiles
400 /// isancestors(low_rev, high_rev): callback to check if a revision is an
420 /// isancestors(low_rev, high_rev): callback to check if a revision is an
401 /// ancestor of another
421 /// ancestor of another
402 pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool, D>(
422 pub fn combine_changeset_copies<A: Fn(Revision, Revision) -> bool, D>(
403 revs: Vec<Revision>,
423 revs: Vec<Revision>,
404 mut children_count: HashMap<Revision, usize>,
424 mut children_count: HashMap<Revision, usize>,
405 target_rev: Revision,
425 target_rev: Revision,
406 rev_info: RevInfoMaker<D>,
426 rev_info: RevInfoMaker<D>,
407 is_ancestor: &A,
427 is_ancestor: &A,
408 ) -> PathCopies {
428 ) -> PathCopies {
409 let mut all_copies = HashMap::new();
429 let mut all_copies = HashMap::new();
410 let mut oracle = AncestorOracle::new(is_ancestor);
430 let mut oracle = AncestorOracle::new(is_ancestor);
411
431
412 let mut path_map = TwoWayPathMap::default();
432 let mut path_map = TwoWayPathMap::default();
413
433
414 for rev in revs {
434 for rev in revs {
415 let mut d: DataHolder<D> = DataHolder { data: None };
435 let mut d: DataHolder<D> = DataHolder { data: None };
416 let (p1, p2, changes) = rev_info(rev, &mut d);
436 let (p1, p2, changes) = rev_info(rev, &mut d);
417
437
418 // We will chain the copies information accumulated for the parent with
438 // We will chain the copies information accumulated for the parent with
419 // the individual copies information the curent revision. Creating a
439 // the individual copies information the curent revision. Creating a
420 // new TimeStampedPath for each `rev` → `children` vertex.
440 // new TimeStampedPath for each `rev` → `children` vertex.
421 let mut copies: Option<InternalPathCopies> = None;
441 let mut copies: Option<InternalPathCopies> = None;
422 if p1 != NULL_REVISION {
442 if p1 != NULL_REVISION {
423 // Retrieve data computed in a previous iteration
443 // Retrieve data computed in a previous iteration
424 let parent_copies = get_and_clean_parent_copies(
444 let parent_copies = get_and_clean_parent_copies(
425 &mut all_copies,
445 &mut all_copies,
426 &mut children_count,
446 &mut children_count,
427 p1,
447 p1,
428 );
448 );
429 if let Some(parent_copies) = parent_copies {
449 if let Some(parent_copies) = parent_copies {
430 // combine it with data for that revision
450 // combine it with data for that revision
431 let vertex_copies = add_from_changes(
451 let vertex_copies = add_from_changes(
432 &mut path_map,
452 &mut path_map,
433 &mut oracle,
453 &mut oracle,
434 &parent_copies,
454 &parent_copies,
435 &changes,
455 &changes,
436 Parent::FirstParent,
456 Parent::FirstParent,
437 rev,
457 rev,
438 );
458 );
439 // keep that data around for potential later combination
459 // keep that data around for potential later combination
440 copies = Some(vertex_copies);
460 copies = Some(vertex_copies);
441 }
461 }
442 }
462 }
443 if p2 != NULL_REVISION {
463 if p2 != NULL_REVISION {
444 // Retrieve data computed in a previous iteration
464 // Retrieve data computed in a previous iteration
445 let parent_copies = get_and_clean_parent_copies(
465 let parent_copies = get_and_clean_parent_copies(
446 &mut all_copies,
466 &mut all_copies,
447 &mut children_count,
467 &mut children_count,
448 p2,
468 p2,
449 );
469 );
450 if let Some(parent_copies) = parent_copies {
470 if let Some(parent_copies) = parent_copies {
451 // combine it with data for that revision
471 // combine it with data for that revision
452 let vertex_copies = add_from_changes(
472 let vertex_copies = add_from_changes(
453 &mut path_map,
473 &mut path_map,
454 &mut oracle,
474 &mut oracle,
455 &parent_copies,
475 &parent_copies,
456 &changes,
476 &changes,
457 Parent::SecondParent,
477 Parent::SecondParent,
458 rev,
478 rev,
459 );
479 );
460
480
461 copies = match copies {
481 copies = match copies {
462 None => Some(vertex_copies),
482 None => Some(vertex_copies),
463 // Merge has two parents needs to combines their copy
483 // Merge has two parents needs to combines their copy
464 // information.
484 // information.
465 //
485 //
466 // If we got data from both parents, We need to combine
486 // If we got data from both parents, We need to combine
467 // them.
487 // them.
468 Some(copies) => Some(merge_copies_dict(
488 Some(copies) => Some(merge_copies_dict(
469 &path_map,
489 &path_map,
470 rev,
490 rev,
471 vertex_copies,
491 vertex_copies,
472 copies,
492 copies,
473 &changes,
493 &changes,
474 &mut oracle,
494 &mut oracle,
475 )),
495 )),
476 };
496 };
477 }
497 }
478 }
498 }
479 match copies {
499 match copies {
480 Some(copies) => {
500 Some(copies) => {
481 all_copies.insert(rev, copies);
501 all_copies.insert(rev, copies);
482 }
502 }
483 _ => {}
503 _ => {}
484 }
504 }
485 }
505 }
486
506
487 // Drop internal information (like the timestamp) and return the final
507 // Drop internal information (like the timestamp) and return the final
488 // mapping.
508 // mapping.
489 let tt_result = all_copies
509 let tt_result = all_copies
490 .remove(&target_rev)
510 .remove(&target_rev)
491 .expect("target revision was not processed");
511 .expect("target revision was not processed");
492 let mut result = PathCopies::default();
512 let mut result = PathCopies::default();
493 for (dest, tt_source) in tt_result {
513 for (dest, tt_source) in tt_result {
494 if let Some(path) = tt_source.path {
514 if let Some(path) = tt_source.path {
495 let path_dest = path_map.untokenize(dest).to_owned();
515 let path_dest = path_map.untokenize(dest).to_owned();
496 let path_path = path_map.untokenize(path).to_owned();
516 let path_path = path_map.untokenize(path).to_owned();
497 result.insert(path_dest, path_path);
517 result.insert(path_dest, path_path);
498 }
518 }
499 }
519 }
500 result
520 result
501 }
521 }
502
522
503 /// fetch previous computed information
523 /// fetch previous computed information
504 ///
524 ///
505 /// If no other children are expected to need this information, we drop it from
525 /// If no other children are expected to need this information, we drop it from
506 /// the cache.
526 /// the cache.
507 ///
527 ///
508 /// If parent is not part of the set we are expected to walk, return None.
528 /// If parent is not part of the set we are expected to walk, return None.
509 fn get_and_clean_parent_copies(
529 fn get_and_clean_parent_copies(
510 all_copies: &mut HashMap<Revision, InternalPathCopies>,
530 all_copies: &mut HashMap<Revision, InternalPathCopies>,
511 children_count: &mut HashMap<Revision, usize>,
531 children_count: &mut HashMap<Revision, usize>,
512 parent_rev: Revision,
532 parent_rev: Revision,
513 ) -> Option<InternalPathCopies> {
533 ) -> Option<InternalPathCopies> {
514 let count = children_count.get_mut(&parent_rev)?;
534 let count = children_count.get_mut(&parent_rev)?;
515 *count -= 1;
535 *count -= 1;
516 if *count == 0 {
536 if *count == 0 {
517 match all_copies.remove(&parent_rev) {
537 match all_copies.remove(&parent_rev) {
518 Some(c) => Some(c),
538 Some(c) => Some(c),
519 None => Some(InternalPathCopies::default()),
539 None => Some(InternalPathCopies::default()),
520 }
540 }
521 } else {
541 } else {
522 match all_copies.get(&parent_rev) {
542 match all_copies.get(&parent_rev) {
523 Some(c) => Some(c.clone()),
543 Some(c) => Some(c.clone()),
524 None => Some(InternalPathCopies::default()),
544 None => Some(InternalPathCopies::default()),
525 }
545 }
526 }
546 }
527 }
547 }
528
548
529 /// Combine ChangedFiles with some existing PathCopies information and return
549 /// Combine ChangedFiles with some existing PathCopies information and return
530 /// the result
550 /// the result
531 fn add_from_changes<A: Fn(Revision, Revision) -> bool>(
551 fn add_from_changes<A: Fn(Revision, Revision) -> bool>(
532 path_map: &mut TwoWayPathMap,
552 path_map: &mut TwoWayPathMap,
533 oracle: &mut AncestorOracle<A>,
553 oracle: &mut AncestorOracle<A>,
534 base_copies: &InternalPathCopies,
554 base_copies: &InternalPathCopies,
535 changes: &ChangedFiles,
555 changes: &ChangedFiles,
536 parent: Parent,
556 parent: Parent,
537 current_rev: Revision,
557 current_rev: Revision,
538 ) -> InternalPathCopies {
558 ) -> InternalPathCopies {
539 let mut copies = base_copies.clone();
559 let mut copies = base_copies.clone();
540 for action in changes.iter_actions(parent) {
560 for action in changes.iter_actions(parent) {
541 match action {
561 match action {
542 Action::Copied(path_dest, path_source) => {
562 Action::Copied(path_dest, path_source) => {
543 let dest = path_map.tokenize(path_dest);
563 let dest = path_map.tokenize(path_dest);
544 let source = path_map.tokenize(path_source);
564 let source = path_map.tokenize(path_source);
545 let entry;
565 let entry;
546 if let Some(v) = base_copies.get(&source) {
566 if let Some(v) = base_copies.get(&source) {
547 entry = match &v.path {
567 entry = match &v.path {
548 Some(path) => Some((*(path)).to_owned()),
568 Some(path) => Some((*(path)).to_owned()),
549 None => Some(source.to_owned()),
569 None => Some(source.to_owned()),
550 }
570 }
551 } else {
571 } else {
552 entry = Some(source.to_owned());
572 entry = Some(source.to_owned());
553 }
573 }
554 // Each new entry is introduced by the children, we
574 // Each new entry is introduced by the children, we
555 // record this information as we will need it to take
575 // record this information as we will need it to take
556 // the right decision when merging conflicting copy
576 // the right decision when merging conflicting copy
557 // information. See merge_copies_dict for details.
577 // information. See merge_copies_dict for details.
558 match copies.entry(dest) {
578 match copies.entry(dest) {
559 Entry::Vacant(slot) => {
579 Entry::Vacant(slot) => {
560 let ttpc = CopySource::new(current_rev, entry);
580 let ttpc = CopySource::new(current_rev, entry);
561 slot.insert(ttpc);
581 slot.insert(ttpc);
562 }
582 }
563 Entry::Occupied(mut slot) => {
583 Entry::Occupied(mut slot) => {
564 let ttpc = slot.get_mut();
584 let ttpc = slot.get_mut();
565 oracle.record_overwrite(ttpc.rev, current_rev);
585 oracle.record_overwrite(ttpc.rev, current_rev);
566 ttpc.overwrite(current_rev, entry);
586 ttpc.overwrite(current_rev, entry);
567 }
587 }
568 }
588 }
569 }
589 }
570 Action::Removed(deleted_path) => {
590 Action::Removed(deleted_path) => {
571 // We must drop copy information for removed file.
591 // We must drop copy information for removed file.
572 //
592 //
573 // We need to explicitly record them as dropped to
593 // We need to explicitly record them as dropped to
574 // propagate this information when merging two
594 // propagate this information when merging two
575 // InternalPathCopies object.
595 // InternalPathCopies object.
576 let deleted = path_map.tokenize(deleted_path);
596 let deleted = path_map.tokenize(deleted_path);
577 copies.entry(deleted).and_modify(|old| {
597 copies.entry(deleted).and_modify(|old| {
578 oracle.record_overwrite(old.rev, current_rev);
598 oracle.record_overwrite(old.rev, current_rev);
579 old.mark_delete(current_rev);
599 old.mark_delete(current_rev);
580 });
600 });
581 }
601 }
582 }
602 }
583 }
603 }
584 copies
604 copies
585 }
605 }
586
606
587 /// merge two copies-mapping together, minor and major
607 /// merge two copies-mapping together, minor and major
588 ///
608 ///
589 /// In case of conflict, value from "major" will be picked, unless in some
609 /// In case of conflict, value from "major" will be picked, unless in some
590 /// cases. See inline documentation for details.
610 /// cases. See inline documentation for details.
591 fn merge_copies_dict<A: Fn(Revision, Revision) -> bool>(
611 fn merge_copies_dict<A: Fn(Revision, Revision) -> bool>(
592 path_map: &TwoWayPathMap,
612 path_map: &TwoWayPathMap,
593 current_merge: Revision,
613 current_merge: Revision,
594 mut minor: InternalPathCopies,
614 mut minor: InternalPathCopies,
595 mut major: InternalPathCopies,
615 mut major: InternalPathCopies,
596 changes: &ChangedFiles,
616 changes: &ChangedFiles,
597 oracle: &mut AncestorOracle<A>,
617 oracle: &mut AncestorOracle<A>,
598 ) -> InternalPathCopies {
618 ) -> InternalPathCopies {
599 // This closure exist as temporary help while multiple developper are
619 // This closure exist as temporary help while multiple developper are
600 // actively working on this code. Feel free to re-inline it once this
620 // actively working on this code. Feel free to re-inline it once this
601 // code is more settled.
621 // code is more settled.
602 let cmp_value = |oracle: &mut AncestorOracle<A>,
622 let cmp_value = |oracle: &mut AncestorOracle<A>,
603 dest: &PathToken,
623 dest: &PathToken,
604 src_minor: &CopySource,
624 src_minor: &CopySource,
605 src_major: &CopySource| {
625 src_major: &CopySource| {
606 compare_value(
626 compare_value(
607 path_map,
627 path_map,
608 current_merge,
628 current_merge,
609 changes,
629 changes,
610 oracle,
630 oracle,
611 dest,
631 dest,
612 src_minor,
632 src_minor,
613 src_major,
633 src_major,
614 )
634 )
615 };
635 };
616 if minor.is_empty() {
636 if minor.is_empty() {
617 major
637 major
618 } else if major.is_empty() {
638 } else if major.is_empty() {
619 minor
639 minor
620 } else if minor.len() * 2 < major.len() {
640 } else if minor.len() * 2 < major.len() {
621 // Lets says we are merging two InternalPathCopies instance A and B.
641 // Lets says we are merging two InternalPathCopies instance A and B.
622 //
642 //
623 // If A contains N items, the merge result will never contains more
643 // If A contains N items, the merge result will never contains more
624 // than N values differents than the one in A
644 // than N values differents than the one in A
625 //
645 //
626 // If B contains M items, with M > N, the merge result will always
646 // If B contains M items, with M > N, the merge result will always
627 // result in a minimum of M - N value differents than the on in
647 // result in a minimum of M - N value differents than the on in
628 // A
648 // A
629 //
649 //
630 // As a result, if N < (M-N), we know that simply iterating over A will
650 // As a result, if N < (M-N), we know that simply iterating over A will
631 // yield less difference than iterating over the difference
651 // yield less difference than iterating over the difference
632 // between A and B.
652 // between A and B.
633 //
653 //
634 // This help performance a lot in case were a tiny
654 // This help performance a lot in case were a tiny
635 // InternalPathCopies is merged with a much larger one.
655 // InternalPathCopies is merged with a much larger one.
636 for (dest, src_minor) in minor {
656 for (dest, src_minor) in minor {
637 let src_major = major.get(&dest);
657 let src_major = major.get(&dest);
638 match src_major {
658 match src_major {
639 None => {
659 None => {
640 major.insert(dest, src_minor);
660 major.insert(dest, src_minor);
641 }
661 }
642 Some(src_major) => {
662 Some(src_major) => {
643 let (pick, overwrite) =
663 let (pick, overwrite) =
644 cmp_value(oracle, &dest, &src_minor, src_major);
664 cmp_value(oracle, &dest, &src_minor, src_major);
645 if overwrite {
665 if overwrite {
646 oracle.record_overwrite(src_minor.rev, current_merge);
666 oracle.record_overwrite(src_minor.rev, current_merge);
647 oracle.record_overwrite(src_major.rev, current_merge);
667 oracle.record_overwrite(src_major.rev, current_merge);
648 let src = match pick {
668 let src = match pick {
649 MergePick::Major => CopySource::new_from_merge(
669 MergePick::Major => CopySource::new_from_merge(
650 current_merge,
670 current_merge,
651 src_major,
671 src_major,
652 &src_minor,
672 &src_minor,
653 ),
673 ),
654 MergePick::Minor => CopySource::new_from_merge(
674 MergePick::Minor => CopySource::new_from_merge(
655 current_merge,
675 current_merge,
656 &src_minor,
676 &src_minor,
657 src_major,
677 src_major,
658 ),
678 ),
659 MergePick::Any => CopySource::new_from_merge(
679 MergePick::Any => CopySource::new_from_merge(
660 current_merge,
680 current_merge,
661 src_major,
681 src_major,
662 &src_minor,
682 &src_minor,
663 ),
683 ),
664 };
684 };
665 major.insert(dest, src);
685 major.insert(dest, src);
666 } else {
686 } else {
667 match pick {
687 match pick {
668 MergePick::Any | MergePick::Major => None,
688 MergePick::Any | MergePick::Major => None,
669 MergePick::Minor => major.insert(dest, src_minor),
689 MergePick::Minor => major.insert(dest, src_minor),
670 };
690 };
671 }
691 }
672 }
692 }
673 };
693 };
674 }
694 }
675 major
695 major
676 } else if major.len() * 2 < minor.len() {
696 } else if major.len() * 2 < minor.len() {
677 // This use the same rational than the previous block.
697 // This use the same rational than the previous block.
678 // (Check previous block documentation for details.)
698 // (Check previous block documentation for details.)
679 for (dest, src_major) in major {
699 for (dest, src_major) in major {
680 let src_minor = minor.get(&dest);
700 let src_minor = minor.get(&dest);
681 match src_minor {
701 match src_minor {
682 None => {
702 None => {
683 minor.insert(dest, src_major);
703 minor.insert(dest, src_major);
684 }
704 }
685 Some(src_minor) => {
705 Some(src_minor) => {
686 let (pick, overwrite) =
706 let (pick, overwrite) =
687 cmp_value(oracle, &dest, src_minor, &src_major);
707 cmp_value(oracle, &dest, src_minor, &src_major);
688 if overwrite {
708 if overwrite {
689 oracle.record_overwrite(src_minor.rev, current_merge);
709 oracle.record_overwrite(src_minor.rev, current_merge);
690 oracle.record_overwrite(src_major.rev, current_merge);
710 oracle.record_overwrite(src_major.rev, current_merge);
691 let src = match pick {
711 let src = match pick {
692 MergePick::Major => CopySource::new_from_merge(
712 MergePick::Major => CopySource::new_from_merge(
693 current_merge,
713 current_merge,
694 &src_major,
714 &src_major,
695 src_minor,
715 src_minor,
696 ),
716 ),
697 MergePick::Minor => CopySource::new_from_merge(
717 MergePick::Minor => CopySource::new_from_merge(
698 current_merge,
718 current_merge,
699 src_minor,
719 src_minor,
700 &src_major,
720 &src_major,
701 ),
721 ),
702 MergePick::Any => CopySource::new_from_merge(
722 MergePick::Any => CopySource::new_from_merge(
703 current_merge,
723 current_merge,
704 &src_major,
724 &src_major,
705 src_minor,
725 src_minor,
706 ),
726 ),
707 };
727 };
708 minor.insert(dest, src);
728 minor.insert(dest, src);
709 } else {
729 } else {
710 match pick {
730 match pick {
711 MergePick::Any | MergePick::Minor => None,
731 MergePick::Any | MergePick::Minor => None,
712 MergePick::Major => minor.insert(dest, src_major),
732 MergePick::Major => minor.insert(dest, src_major),
713 };
733 };
714 }
734 }
715 }
735 }
716 };
736 };
717 }
737 }
718 minor
738 minor
719 } else {
739 } else {
720 let mut override_minor = Vec::new();
740 let mut override_minor = Vec::new();
721 let mut override_major = Vec::new();
741 let mut override_major = Vec::new();
722
742
723 let mut to_major = |k: &PathToken, v: &CopySource| {
743 let mut to_major = |k: &PathToken, v: &CopySource| {
724 override_major.push((k.clone(), v.clone()))
744 override_major.push((k.clone(), v.clone()))
725 };
745 };
726 let mut to_minor = |k: &PathToken, v: &CopySource| {
746 let mut to_minor = |k: &PathToken, v: &CopySource| {
727 override_minor.push((k.clone(), v.clone()))
747 override_minor.push((k.clone(), v.clone()))
728 };
748 };
729
749
730 // The diff function leverage detection of the identical subpart if
750 // The diff function leverage detection of the identical subpart if
731 // minor and major has some common ancestors. This make it very
751 // minor and major has some common ancestors. This make it very
732 // fast is most case.
752 // fast is most case.
733 //
753 //
734 // In case where the two map are vastly different in size, the current
754 // In case where the two map are vastly different in size, the current
735 // approach is still slowish because the iteration will iterate over
755 // approach is still slowish because the iteration will iterate over
736 // all the "exclusive" content of the larger on. This situation can be
756 // all the "exclusive" content of the larger on. This situation can be
737 // frequent when the subgraph of revision we are processing has a lot
757 // frequent when the subgraph of revision we are processing has a lot
738 // of roots. Each roots adding they own fully new map to the mix (and
758 // of roots. Each roots adding they own fully new map to the mix (and
739 // likely a small map, if the path from the root to the "main path" is
759 // likely a small map, if the path from the root to the "main path" is
740 // small.
760 // small.
741 //
761 //
742 // We could do better by detecting such situation and processing them
762 // We could do better by detecting such situation and processing them
743 // differently.
763 // differently.
744 for d in minor.diff(&major) {
764 for d in minor.diff(&major) {
745 match d {
765 match d {
746 DiffItem::Add(k, v) => to_minor(k, v),
766 DiffItem::Add(k, v) => to_minor(k, v),
747 DiffItem::Remove(k, v) => to_major(k, v),
767 DiffItem::Remove(k, v) => to_major(k, v),
748 DiffItem::Update { old, new } => {
768 DiffItem::Update { old, new } => {
749 let (dest, src_major) = new;
769 let (dest, src_major) = new;
750 let (_, src_minor) = old;
770 let (_, src_minor) = old;
751 let (pick, overwrite) =
771 let (pick, overwrite) =
752 cmp_value(oracle, dest, src_minor, src_major);
772 cmp_value(oracle, dest, src_minor, src_major);
753 if overwrite {
773 if overwrite {
754 oracle.record_overwrite(src_minor.rev, current_merge);
774 oracle.record_overwrite(src_minor.rev, current_merge);
755 oracle.record_overwrite(src_major.rev, current_merge);
775 oracle.record_overwrite(src_major.rev, current_merge);
756 let src = match pick {
776 let src = match pick {
757 MergePick::Major => CopySource::new_from_merge(
777 MergePick::Major => CopySource::new_from_merge(
758 current_merge,
778 current_merge,
759 src_major,
779 src_major,
760 src_minor,
780 src_minor,
761 ),
781 ),
762 MergePick::Minor => CopySource::new_from_merge(
782 MergePick::Minor => CopySource::new_from_merge(
763 current_merge,
783 current_merge,
764 src_minor,
784 src_minor,
765 src_major,
785 src_major,
766 ),
786 ),
767 MergePick::Any => CopySource::new_from_merge(
787 MergePick::Any => CopySource::new_from_merge(
768 current_merge,
788 current_merge,
769 src_major,
789 src_major,
770 src_minor,
790 src_minor,
771 ),
791 ),
772 };
792 };
773 to_minor(dest, &src);
793 to_minor(dest, &src);
774 to_major(dest, &src);
794 to_major(dest, &src);
775 } else {
795 } else {
776 match pick {
796 match pick {
777 MergePick::Major => to_minor(dest, src_major),
797 MergePick::Major => to_minor(dest, src_major),
778 MergePick::Minor => to_major(dest, src_minor),
798 MergePick::Minor => to_major(dest, src_minor),
779 // If the two entry are identical, no need to do
799 // If the two entry are identical, no need to do
780 // anything (but diff should not have yield them)
800 // anything (but diff should not have yield them)
781 MergePick::Any => unreachable!(),
801 MergePick::Any => unreachable!(),
782 }
802 }
783 }
803 }
784 }
804 }
785 };
805 };
786 }
806 }
787
807
788 let updates;
808 let updates;
789 let mut result;
809 let mut result;
790 if override_major.is_empty() {
810 if override_major.is_empty() {
791 result = major
811 result = major
792 } else if override_minor.is_empty() {
812 } else if override_minor.is_empty() {
793 result = minor
813 result = minor
794 } else {
814 } else {
795 if override_minor.len() < override_major.len() {
815 if override_minor.len() < override_major.len() {
796 updates = override_minor;
816 updates = override_minor;
797 result = minor;
817 result = minor;
798 } else {
818 } else {
799 updates = override_major;
819 updates = override_major;
800 result = major;
820 result = major;
801 }
821 }
802 for (k, v) in updates {
822 for (k, v) in updates {
803 result.insert(k, v);
823 result.insert(k, v);
804 }
824 }
805 }
825 }
806 result
826 result
807 }
827 }
808 }
828 }
809
829
810 /// represent the side that should prevail when merging two
830 /// represent the side that should prevail when merging two
811 /// InternalPathCopies
831 /// InternalPathCopies
812 enum MergePick {
832 enum MergePick {
813 /// The "major" (p1) side prevails
833 /// The "major" (p1) side prevails
814 Major,
834 Major,
815 /// The "minor" (p2) side prevails
835 /// The "minor" (p2) side prevails
816 Minor,
836 Minor,
817 /// Any side could be used (because they are the same)
837 /// Any side could be used (because they are the same)
818 Any,
838 Any,
819 }
839 }
820
840
821 /// decide which side prevails in case of conflicting values
841 /// decide which side prevails in case of conflicting values
822 #[allow(clippy::if_same_then_else)]
842 #[allow(clippy::if_same_then_else)]
823 fn compare_value<A: Fn(Revision, Revision) -> bool>(
843 fn compare_value<A: Fn(Revision, Revision) -> bool>(
824 path_map: &TwoWayPathMap,
844 path_map: &TwoWayPathMap,
825 current_merge: Revision,
845 current_merge: Revision,
826 changes: &ChangedFiles,
846 changes: &ChangedFiles,
827 oracle: &mut AncestorOracle<A>,
847 oracle: &mut AncestorOracle<A>,
828 dest: &PathToken,
848 dest: &PathToken,
829 src_minor: &CopySource,
849 src_minor: &CopySource,
830 src_major: &CopySource,
850 src_major: &CopySource,
831 ) -> (MergePick, bool) {
851 ) -> (MergePick, bool) {
832 if src_major.rev == current_merge {
852 if src_major.rev == current_merge {
833 if src_minor.rev == current_merge {
853 if src_minor.rev == current_merge {
834 if src_major.path.is_none() {
854 if src_major.path.is_none() {
835 // We cannot get different copy information for both p1 and p2
855 // We cannot get different copy information for both p1 and p2
836 // from the same revision. Unless this was a
856 // from the same revision. Unless this was a
837 // deletion
857 // deletion.
838 (MergePick::Any, false)
858 //
859 // However the deletion might come over different data on each
860 // branch.
861 let need_over = src_major.overwritten != src_minor.overwritten;
862 (MergePick::Any, need_over)
839 } else {
863 } else {
840 unreachable!();
864 unreachable!();
841 }
865 }
842 } else {
866 } else {
843 // The last value comes the current merge, this value -will- win
867 // The last value comes the current merge, this value -will- win
844 // eventually.
868 // eventually.
845 (MergePick::Major, true)
869 (MergePick::Major, true)
846 }
870 }
847 } else if src_minor.rev == current_merge {
871 } else if src_minor.rev == current_merge {
848 // The last value comes the current merge, this value -will- win
872 // The last value comes the current merge, this value -will- win
849 // eventually.
873 // eventually.
850 (MergePick::Minor, true)
874 (MergePick::Minor, true)
851 } else if src_major.path == src_minor.path {
875 } else if src_major.path == src_minor.path {
852 // we have the same value, but from other source;
876 // we have the same value, but from other source;
853 if src_major.rev == src_minor.rev {
877 if src_major.rev == src_minor.rev {
854 // If the two entry are identical, they are both valid
878 // If the two entry are identical, they are both valid
879 debug_assert!(src_minor.overwritten == src_minor.overwritten);
855 (MergePick::Any, false)
880 (MergePick::Any, false)
856 } else if oracle.is_overwrite(src_major.rev, src_minor.rev) {
881 } else if src_major.is_overwritten_by(src_minor) {
857 (MergePick::Minor, false)
882 (MergePick::Minor, false)
858 } else if oracle.is_overwrite(src_minor.rev, src_major.rev) {
883 } else if src_minor.is_overwritten_by(src_major) {
859 (MergePick::Major, false)
884 (MergePick::Major, false)
860 } else {
885 } else {
861 (MergePick::Any, true)
886 (MergePick::Any, true)
862 }
887 }
863 } else if src_major.rev == src_minor.rev {
888 } else if src_major.rev == src_minor.rev {
864 // We cannot get copy information for both p1 and p2 in the
889 // We cannot get copy information for both p1 and p2 in the
865 // same rev. So this is the same value.
890 // same rev. So this is the same value.
866 unreachable!(
891 unreachable!(
867 "conflicting information from p1 and p2 in the same revision"
892 "conflicting information from p1 and p2 in the same revision"
868 );
893 );
869 } else {
894 } else {
870 let dest_path = path_map.untokenize(*dest);
895 let dest_path = path_map.untokenize(*dest);
871 let action = changes.get_merge_case(dest_path);
896 let action = changes.get_merge_case(dest_path);
872 if src_minor.path.is_some()
897 if src_minor.path.is_some()
873 && src_major.path.is_none()
898 && src_major.path.is_none()
874 && action == MergeCase::Salvaged
899 && action == MergeCase::Salvaged
875 {
900 {
876 // If the file is "deleted" in the major side but was
901 // If the file is "deleted" in the major side but was
877 // salvaged by the merge, we keep the minor side alive
902 // salvaged by the merge, we keep the minor side alive
878 (MergePick::Minor, true)
903 (MergePick::Minor, true)
879 } else if src_major.path.is_some()
904 } else if src_major.path.is_some()
880 && src_minor.path.is_none()
905 && src_minor.path.is_none()
881 && action == MergeCase::Salvaged
906 && action == MergeCase::Salvaged
882 {
907 {
883 // If the file is "deleted" in the minor side but was
908 // If the file is "deleted" in the minor side but was
884 // salvaged by the merge, unconditionnaly preserve the
909 // salvaged by the merge, unconditionnaly preserve the
885 // major side.
910 // major side.
886 (MergePick::Major, true)
911 (MergePick::Major, true)
887 } else if oracle.is_overwrite(src_minor.rev, src_major.rev) {
912 } else if src_minor.is_overwritten_by(src_major) {
888 // The information from the minor version are strictly older than
913 // The information from the minor version are strictly older than
889 // the major version
914 // the major version
890 if action == MergeCase::Merged {
915 if action == MergeCase::Merged {
891 // If the file was actively merged, its means some non-copy
916 // If the file was actively merged, its means some non-copy
892 // activity happened on the other branch. It
917 // activity happened on the other branch. It
893 // mean the older copy information are still relevant.
918 // mean the older copy information are still relevant.
894 //
919 //
895 // The major side wins such conflict.
920 // The major side wins such conflict.
896 (MergePick::Major, true)
921 (MergePick::Major, true)
897 } else {
922 } else {
898 // No activity on the minor branch, pick the newer one.
923 // No activity on the minor branch, pick the newer one.
899 (MergePick::Major, false)
924 (MergePick::Major, false)
900 }
925 }
901 } else if oracle.is_overwrite(src_major.rev, src_minor.rev) {
926 } else if src_major.is_overwritten_by(src_minor) {
902 if action == MergeCase::Merged {
927 if action == MergeCase::Merged {
903 // If the file was actively merged, its means some non-copy
928 // If the file was actively merged, its means some non-copy
904 // activity happened on the other branch. It
929 // activity happened on the other branch. It
905 // mean the older copy information are still relevant.
930 // mean the older copy information are still relevant.
906 //
931 //
907 // The major side wins such conflict.
932 // The major side wins such conflict.
908 (MergePick::Major, true)
933 (MergePick::Major, true)
909 } else {
934 } else {
910 // No activity on the minor branch, pick the newer one.
935 // No activity on the minor branch, pick the newer one.
911 (MergePick::Minor, false)
936 (MergePick::Minor, false)
912 }
937 }
913 } else if src_minor.path.is_none() {
938 } else if src_minor.path.is_none() {
914 // the minor side has no relevant information, pick the alive one
939 // the minor side has no relevant information, pick the alive one
915 (MergePick::Major, true)
940 (MergePick::Major, true)
916 } else if src_major.path.is_none() {
941 } else if src_major.path.is_none() {
917 // the major side has no relevant information, pick the alive one
942 // the major side has no relevant information, pick the alive one
918 (MergePick::Minor, true)
943 (MergePick::Minor, true)
919 } else {
944 } else {
920 // by default the major side wins
945 // by default the major side wins
921 (MergePick::Major, true)
946 (MergePick::Major, true)
922 }
947 }
923 }
948 }
924 }
949 }
General Comments 0
You need to be logged in to leave comments. Login now