use std::cmp::min;
use std::collections::{BTreeMap, HashMap, HashSet};
use crate::index::{IndexEntry, IndexPosition};
use crate::nightly_shims::BTreeMapExt;
use crate::revset::RevsetIterator;
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub struct RevsetGraphEdge {
pub target: IndexPosition,
pub edge_type: RevsetGraphEdgeType,
}
impl RevsetGraphEdge {
pub fn missing(target: IndexPosition) -> Self {
Self {
target,
edge_type: RevsetGraphEdgeType::Missing,
}
}
pub fn direct(target: IndexPosition) -> Self {
Self {
target,
edge_type: RevsetGraphEdgeType::Direct,
}
}
pub fn indirect(target: IndexPosition) -> Self {
Self {
target,
edge_type: RevsetGraphEdgeType::Indirect,
}
}
}
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub enum RevsetGraphEdgeType {
Missing,
Direct,
Indirect,
}
pub struct RevsetGraphIterator<'revset, 'repo> {
input_set_iter: RevsetIterator<'revset, 'repo>,
look_ahead: BTreeMap<IndexPosition, IndexEntry<'repo>>,
min_position: IndexPosition,
edges: BTreeMap<IndexPosition, HashSet<RevsetGraphEdge>>,
skip_transitive_edges: bool,
}
impl<'revset, 'repo> RevsetGraphIterator<'revset, 'repo> {
pub fn new(iter: RevsetIterator<'revset, 'repo>) -> RevsetGraphIterator<'revset, 'repo> {
RevsetGraphIterator {
input_set_iter: iter,
look_ahead: Default::default(),
min_position: IndexPosition::MAX,
edges: Default::default(),
skip_transitive_edges: true,
}
}
pub fn set_skip_transitive_edges(mut self, skip_transitive_edges: bool) -> Self {
self.skip_transitive_edges = skip_transitive_edges;
self
}
pub fn reversed(self) -> ReverseRevsetGraphIterator<'repo> {
ReverseRevsetGraphIterator::new(self)
}
fn next_index_entry(&mut self) -> Option<IndexEntry<'repo>> {
if let Some(index_entry) = self.look_ahead.pop_last_value() {
return Some(index_entry);
}
self.input_set_iter.next()
}
fn edges_from_internal_commit(
&mut self,
index_entry: &IndexEntry<'repo>,
) -> HashSet<RevsetGraphEdge> {
if let Some(edges) = self.edges.get(&index_entry.position()) {
return edges.clone();
}
let mut edges = HashSet::new();
for parent in index_entry.parents() {
let parent_position = parent.position();
self.consume_to(parent_position);
if self.look_ahead.contains_key(&parent_position) {
edges.insert(RevsetGraphEdge::direct(parent_position));
} else {
let parent_edges = self.edges_from_external_commit(parent);
if parent_edges
.iter()
.all(|edge| edge.edge_type == RevsetGraphEdgeType::Missing)
{
edges.insert(RevsetGraphEdge::missing(parent_position));
} else {
edges.extend(parent_edges);
}
}
}
self.edges.insert(index_entry.position(), edges.clone());
edges
}
fn edges_from_external_commit(
&mut self,
index_entry: IndexEntry<'repo>,
) -> HashSet<RevsetGraphEdge> {
let position = index_entry.position();
let mut stack = vec![index_entry];
while let Some(entry) = stack.last() {
let position = entry.position();
let mut edges = HashSet::new();
let mut parents_complete = true;
for parent in entry.parents() {
let parent_position = parent.position();
self.consume_to(parent_position);
if self.look_ahead.contains_key(&parent_position) {
edges.insert(RevsetGraphEdge::indirect(parent_position));
} else if let Some(parent_edges) = self.edges.get(&parent_position) {
if parent_edges
.iter()
.all(|edge| edge.edge_type == RevsetGraphEdgeType::Missing)
{
edges.insert(RevsetGraphEdge::missing(parent_position));
} else {
edges.extend(parent_edges.iter().cloned());
}
} else if parent_position < self.min_position {
edges.insert(RevsetGraphEdge::missing(parent_position));
} else {
stack.push(parent);
parents_complete = false;
}
}
if parents_complete {
stack.pop().unwrap();
self.edges.insert(position, edges);
}
}
self.edges.get(&position).unwrap().clone()
}
fn remove_transitive_edges(
&mut self,
edges: HashSet<RevsetGraphEdge>,
) -> HashSet<RevsetGraphEdge> {
if !edges
.iter()
.any(|edge| edge.edge_type == RevsetGraphEdgeType::Indirect)
{
return edges;
}
let mut min_generation = u32::MAX;
let mut initial_targets = HashSet::new();
let mut work = vec![];
for edge in &edges {
initial_targets.insert(edge.target);
if edge.edge_type != RevsetGraphEdgeType::Missing {
let entry = self.look_ahead.get(&edge.target).unwrap().clone();
min_generation = min(min_generation, entry.generation_number());
work.extend(self.edges_from_internal_commit(&entry));
}
}
let mut unwanted = HashSet::new();
while let Some(edge) = work.pop() {
if edge.edge_type == RevsetGraphEdgeType::Missing || edge.target < self.min_position {
continue;
}
if !unwanted.insert(edge.target) {
continue;
}
if initial_targets.contains(&edge.target) {
continue;
}
let entry = self.look_ahead.get(&edge.target).unwrap().clone();
if entry.generation_number() < min_generation {
continue;
}
work.extend(self.edges_from_internal_commit(&entry));
}
edges
.into_iter()
.filter(|edge| !unwanted.contains(&edge.target))
.collect()
}
fn consume_to(&mut self, pos: IndexPosition) {
while pos < self.min_position {
if let Some(next_entry) = self.input_set_iter.next() {
let next_position = next_entry.position();
self.look_ahead.insert(next_position, next_entry);
self.min_position = next_position;
} else {
break;
}
}
}
}
impl<'revset, 'repo> Iterator for RevsetGraphIterator<'revset, 'repo> {
type Item = (IndexEntry<'repo>, Vec<RevsetGraphEdge>);
fn next(&mut self) -> Option<Self::Item> {
let index_entry = self.next_index_entry()?;
let mut edges = self.edges_from_internal_commit(&index_entry);
if self.skip_transitive_edges {
edges = self.remove_transitive_edges(edges);
}
let mut edges: Vec<_> = edges.into_iter().collect();
edges.sort_by(|edge1, edge2| edge2.target.cmp(&edge1.target));
Some((index_entry, edges))
}
}
pub struct ReverseRevsetGraphIterator<'repo> {
items: Vec<(IndexEntry<'repo>, Vec<RevsetGraphEdge>)>,
}
impl<'repo> ReverseRevsetGraphIterator<'repo> {
fn new<'revset>(input: RevsetGraphIterator<'revset, 'repo>) -> Self {
let mut entries = vec![];
let mut reverse_edges: HashMap<IndexPosition, Vec<RevsetGraphEdge>> = HashMap::new();
for (entry, edges) in input {
for RevsetGraphEdge { target, edge_type } in edges {
reverse_edges
.entry(target)
.or_default()
.push(RevsetGraphEdge {
target: entry.position(),
edge_type,
})
}
entries.push(entry);
}
let mut items = vec![];
for entry in entries.into_iter() {
let edges = reverse_edges
.get(&entry.position())
.cloned()
.unwrap_or_default();
items.push((entry, edges));
}
Self { items }
}
}
impl<'repo> Iterator for ReverseRevsetGraphIterator<'repo> {
type Item = (IndexEntry<'repo>, Vec<RevsetGraphEdge>);
fn next(&mut self) -> Option<Self::Item> {
self.items.pop()
}
}