path: root/src/main.rs

use std::io::{self, Result, Write};
use std::collections::{HashSet, HashMap};
use crate::errors::*;

mod errors;

fn sortuniq<T: Ord>(mut vec: Vec<T>) -> Vec<T> {
    if vec.len() == 0 {
        return vec;
    }

    vec.sort();

    let mut last_added_at = 0;
    for i in 1..vec.len() {
        if vec[i] != vec[last_added_at] {
            vec.swap(i, last_added_at + 1);
            last_added_at += 1;
        }
    }

    assert!(last_added_at + 1 <= vec.len());
    vec.resize_with(last_added_at + 1, || panic!(""));
    vec
}

#[allow(dead_code)]
fn deduplicate<T: std::hash::Hash + Eq + Copy>(mut vec: Vec<T>) -> Vec<T> {
    if vec.len() == 0 {
        return vec;
    }

    let mut seen = HashSet::new();
    seen.insert(vec[0]);

    let mut last_added_at = 0;
    for i in 1..vec.len() {
        if !seen.contains(&vec[i]) {
            seen.insert(vec[i]);
            vec.swap(i, last_added_at + 1);
            last_added_at += 1;
        }
    }

    assert!(last_added_at + 1 <= vec.len());
    vec.resize_with(last_added_at + 1, || panic!(""));
    vec
}

struct RefInfo<'repo> {
    reference: git2::Reference<'repo>,
    commit: git2::Commit<'repo>,
}

#[derive(Debug, Clone)]
enum HistoryNode {
    Genesis(git2::Oid),
    Merge(git2::Oid, Vec<usize>),
    Reference(git2::Oid, Vec<usize>),
}

impl HistoryNode {
    fn oid(&self) -> git2::Oid {
        match self {
            &HistoryNode::Genesis(oid) => oid,
            &HistoryNode::Merge(oid, _) => oid,
            &HistoryNode::Reference(oid, _) => oid,
        }
    }
}

struct HistoryCache<F: Fn(&git2::Oid) -> bool> {
    nodes: Vec<HistoryNode>,
    cache: HashMap<git2::Oid, usize>,
    is_reference: F,
}

impl<F: Fn(&git2::Oid) -> bool> HistoryCache<F> {
    fn new(is_reference: F) -> Self {
        HistoryCache {
            nodes: Vec::new(),
            cache: HashMap::new(),
            is_reference
        }
    }

    fn node_for(&self, key: usize) -> Option<&HistoryNode> {
        self.nodes.get(key)
    }

    fn build_history(&mut self, commit: &git2::Commit) -> usize {
        let oid = commit.id();

        if let Some(&key) = self.cache.get(&oid) {
            return key;
        }

        // eprintln!("build_history: inspecting {} {}", &oid.to_string()[0..8], commit.summary().expect("no summary?"));

        let parents = commit.parents().collect::<Vec<_>>();
        macro_rules! build_recursive {
            () => {{
                let list = parents.iter().map(|c| self.build_history(c)).collect::<Vec<_>>();
                let list = self.simplify_merge(&list);
                sortuniq(list)
            }}
        }

        let key = self.nodes.len();
        self.nodes.push(HistoryNode::Genesis(git2::Oid::zero()));  // reserve the place

        let node = if (self.is_reference)(&oid) {
            HistoryNode::Reference(oid, build_recursive!())
        } else if parents.len() == 1 {
            return self.build_history(&parents[0]);
        } else if parents.len() == 0 {
            HistoryNode::Genesis(oid)
        } else {
            HistoryNode::Merge(oid, build_recursive!())
        };

        self.nodes[key] = node;
        self.cache.insert(oid, key);
        key
    }

    fn simplify_merge(&self, parents: &Vec<usize>) -> Vec<usize> {
        let mut result: Vec<usize> = Vec::new();

        for &parent in parents {
            match &self.nodes[parent] {
                HistoryNode::Genesis(_) => result.push(parent),
                HistoryNode::Reference(_, _) => result.push(parent),
                HistoryNode::Merge(_, ps) => result.append(&mut self.simplify_merge(ps)),
            }
        }

        result
    }
}

fn write_dot<W: Write, F: Fn(&git2::Oid) -> bool>(stream: &mut W, history: &mut HistoryCache<F>, seen: &mut HashSet<usize>, refmap: &HashMap<git2::Oid, RefInfo>, key: usize) -> Result<()> {
    if !seen.insert(key) {
        return Ok(());
    }

    let next_keys;

    match history.node_for(key).unwrap() {
        HistoryNode::Genesis(oid) => {
            writeln!(stream, "\t\"{}\" [label=\"G\"];", oid)?;
            next_keys = Vec::new();
        },
        HistoryNode::Reference(oid, parents) => {
            writeln!(stream, "\t\"{}\" [label=\"{}\"];", oid, refmap.get(oid).unwrap().reference.shorthand().expect("Reference name not valid utf8"))?;
            // writeln!(stream, "\t\"{}\" [label=\"R\"];", oid)?;
            for &parent in parents {
                let node = history.node_for(parent).unwrap();
                writeln!(stream, "\t\"{}\" -> \"{}\";", node.oid(), oid)?;
            }
            next_keys = parents.clone();
        },
        HistoryNode::Merge(oid, parents) => {
            writeln!(stream, "\t\"{}\" [label=\"\"];", oid)?;
            for &parent in parents {
                let node = history.node_for(parent).unwrap();
                writeln!(stream, "\t\"{}\" -> \"{}\";", node.oid(), oid)?;
            }
            next_keys = parents.clone();
        },
    }

    for key in next_keys {
        write_dot(stream, history, seen, refmap, key)?;
    }

    Ok(())
}

fn main() -> Result<()> {
    let args = std::env::args().collect::<Vec<_>>();
    if args.len() != 2 {
        eprintln!("Usage: {} <repo-dir>", args[0]);
        std::process::exit(1);
    }

    let repo = git2::Repository::open(&args[1]).to_io_result()?;

    let mut refmap: HashMap<git2::Oid, RefInfo> = HashMap::new();

    for reference in repo.references().to_io_result()? {
        let reference = reference.to_io_result()?;
        if reference.is_tag() || reference.is_remote() {
            let reference = reference.resolve().to_io_result()?;
            match reference.peel_to_commit() {
                Ok(commit) => {
                    let oid = reference.target().expect("Resolved reference is not a direct reference?");
                    refmap.insert(oid, RefInfo { reference, commit });
                    // println!("{} {}",
                    //          reference.name().expect("Invalid utf8 in reference name"),
                    //          commit.id());
                }
                Err(_) => {},
            }
        }
    }

    let mut history_cache = HistoryCache::new(|oid| refmap.contains_key(oid));

    for (_oid, info) in &refmap {
        let _key = history_cache.build_history(&info.commit);
        // println!("{}: {:?}", oid, history_cache.node_for(key));
    }

    let mut keys_done = HashSet::new();
    println!("digraph G {{");
    println!("\trankdir=\"BT\";");
    // println!("\tnode [shape=point]");
    println!("\tedge [arrowhead=none]");
    println!("\tsep=\"+100\";");
    for (_oid, info) in &refmap {
        let key = history_cache.build_history(&info.commit);
        write_dot(&mut io::stdout(), &mut history_cache, &mut keys_done, &refmap, key)?;
    }
    println!("}}");

    Ok(())
}