1034 Ok(reachable) |
1034 Ok(reachable) |
1035 } |
1035 } |
1036 |
1036 |
1037 /// Given a (possibly overlapping) set of revs, return all the |
1037 /// Given a (possibly overlapping) set of revs, return all the |
1038 /// common ancestors heads: `heads(::args[0] and ::a[1] and ...)` |
1038 /// common ancestors heads: `heads(::args[0] and ::a[1] and ...)` |
1039 pub fn common_ancestor_heads(&self, _revisions: &[Revision]) { |
1039 pub fn common_ancestor_heads( |
1040 todo!() |
1040 &self, |
|
1041 revisions: &[Revision], |
|
1042 ) -> Result<Vec<Revision>, GraphError> { |
|
1043 // given that revisions is expected to be small, we find this shortcut |
|
1044 // potentially acceptable, especially given that `hg-cpython` could |
|
1045 // very much bypass this, constructing a vector of unique values from |
|
1046 // the onset. |
|
1047 let as_set: HashSet<Revision> = revisions.iter().copied().collect(); |
|
1048 // Besides deduplicating, the C version also implements the shortcut |
|
1049 // for `NULL_REVISION`: |
|
1050 if as_set.contains(&NULL_REVISION) { |
|
1051 return Ok(vec![]); |
|
1052 } |
|
1053 |
|
1054 let revisions: Vec<Revision> = as_set.into_iter().collect(); |
|
1055 |
|
1056 if revisions.len() <= 63 { |
|
1057 self.find_gca_candidates::<u64>(&revisions) |
|
1058 } else { |
|
1059 self.find_gca_candidates::<NonStaticPoisonableBitSet>(&revisions) |
|
1060 } |
|
1061 } |
|
1062 |
|
1063 pub fn ancestors( |
|
1064 &self, |
|
1065 revisions: &[Revision], |
|
1066 ) -> Result<Vec<Revision>, GraphError> { |
|
1067 self.find_deepest_revs(&self.common_ancestor_heads(revisions)?) |
1041 } |
1068 } |
1042 |
1069 |
1043 /// Given a disjoint set of revs, return all candidates for the |
1070 /// Given a disjoint set of revs, return all candidates for the |
1044 /// greatest common ancestor. In revset notation, this is the set |
1071 /// greatest common ancestor. In revset notation, this is the set |
1045 /// `heads(::a and ::b and ...)` |
1072 /// `heads(::a and ::b and ...)` |
1046 #[allow(dead_code)] |
|
1047 fn find_gca_candidates<BS: PoisonableBitSet + Clone>( |
1073 fn find_gca_candidates<BS: PoisonableBitSet + Clone>( |
1048 &self, |
1074 &self, |
1049 revs: &[Revision], |
1075 revs: &[Revision], |
1050 ) -> Result<Vec<Revision>, GraphError> { |
1076 ) -> Result<Vec<Revision>, GraphError> { |
1051 if revs.is_empty() { |
1077 if revs.is_empty() { |
1145 Ok(candidates) |
1171 Ok(candidates) |
1146 } |
1172 } |
1147 |
1173 |
1148 /// Given a disjoint set of revs, return the subset with the longest path |
1174 /// Given a disjoint set of revs, return the subset with the longest path |
1149 /// to the root. |
1175 /// to the root. |
1150 #[allow(dead_code)] |
|
1151 fn find_deepest_revs( |
1176 fn find_deepest_revs( |
1152 &self, |
1177 &self, |
1153 revs: &[Revision], |
1178 revs: &[Revision], |
1154 ) -> Result<Vec<Revision>, GraphError> { |
1179 ) -> Result<Vec<Revision>, GraphError> { |
1155 // TODO replace this all with just comparing rank? |
1180 // TODO replace this all with just comparing rank? |