Initial

2 files changed, 249 insertions, 0 deletions

diff --git a/src/errors.rs b/src/errors.rs
new file mode 100644
index 0000000..bfb5606
--- /dev/null
+++ b/src/errors.rs
@@ -0,0 +1,21 @@
+use std::io;
+
+pub trait ToIOError {
+    fn to_io_error(self) -> io::Error;
+}
+
+impl ToIOError for git2::Error {
+    fn to_io_error(self) -> io::Error {
+        io::Error::new(io::ErrorKind::Other, self)
+    }
+}
+
+pub trait ToIOResult<T> {
+    fn to_io_result(self) -> io::Result<T>;
+}
+
+impl<T, E: ToIOError> ToIOResult<T> for std::result::Result<T, E> {
+    fn to_io_result(self) -> io::Result<T> {
+        self.map_err(|e| e.to_io_error())
+    }
+}
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..e7d70b3
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,228 @@
+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(())
+}