Initial

5 files changed, 454 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..169c30a
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,4 @@
+/target
+**/*.rs.bk
+graph.dot
+graph.png
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..cbd2474
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,193 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+[[package]]
+name = "autocfg"
+version = "0.1.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "bitflags"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "cc"
+version = "1.0.40"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "cfg-if"
+version = "0.1.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "git-graph"
+version = "0.1.0"
+dependencies = [
+ "git2 0.10.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "git2"
+version = "0.10.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "bitflags 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.62 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libgit2-sys 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)",
+ "openssl-probe 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "openssl-sys 0.9.49 (registry+https://github.com/rust-lang/crates.io-index)",
+ "url 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "idna"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "matches 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
+ "unicode-bidi 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)",
+ "unicode-normalization 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "libc"
+version = "0.2.62"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "libgit2-sys"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cc 1.0.40 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.62 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libssh2-sys 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libz-sys 1.0.25 (registry+https://github.com/rust-lang/crates.io-index)",
+ "openssl-sys 0.9.49 (registry+https://github.com/rust-lang/crates.io-index)",
+ "pkg-config 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "libssh2-sys"
+version = "0.2.11"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cc 1.0.40 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.62 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libz-sys 1.0.25 (registry+https://github.com/rust-lang/crates.io-index)",
+ "openssl-sys 0.9.49 (registry+https://github.com/rust-lang/crates.io-index)",
+ "pkg-config 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)",
+ "vcpkg 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "libz-sys"
+version = "1.0.25"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cc 1.0.40 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.62 (registry+https://github.com/rust-lang/crates.io-index)",
+ "pkg-config 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)",
+ "vcpkg 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "log"
+version = "0.4.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "cfg-if 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "matches"
+version = "0.1.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "openssl-probe"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "openssl-sys"
+version = "0.9.49"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
+ "cc 1.0.40 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.62 (registry+https://github.com/rust-lang/crates.io-index)",
+ "pkg-config 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)",
+ "vcpkg 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "percent-encoding"
+version = "2.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "pkg-config"
+version = "0.3.15"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "smallvec"
+version = "0.6.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
+name = "unicode-bidi"
+version = "0.3.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "matches 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "unicode-normalization"
+version = "0.1.8"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "smallvec 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "url"
+version = "2.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "idna 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "matches 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)",
+ "percent-encoding 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "vcpkg"
+version = "0.2.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[metadata]
+"checksum autocfg 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "b671c8fb71b457dd4ae18c4ba1e59aa81793daacc361d82fcd410cef0d491875"
+"checksum bitflags 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3d155346769a6855b86399e9bc3814ab343cd3d62c7e985113d46a0ec3c281fd"
+"checksum cc 1.0.40 (registry+https://github.com/rust-lang/crates.io-index)" = "b548a4ee81fccb95919d4e22cfea83c7693ebfd78f0495493178db20b3139da7"
+"checksum cfg-if 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)" = "b486ce3ccf7ffd79fdeb678eac06a9e6c09fc88d33836340becb8fffe87c5e33"
+"checksum git2 0.10.0 (registry+https://github.com/rust-lang/crates.io-index)" = "327d698f86a7ebdfeb86a4238ccdb004828939d3a3555b6ead679541d14e36c0"
+"checksum idna 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "02e2673c30ee86b5b96a9cb52ad15718aa1f966f5ab9ad54a8b95d5ca33120a9"
+"checksum libc 0.2.62 (registry+https://github.com/rust-lang/crates.io-index)" = "34fcd2c08d2f832f376f4173a231990fa5aef4e99fb569867318a227ef4c06ba"
+"checksum libgit2-sys 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8c2078aec6f4b16d1b89f6a72e4f6eb1e75ffa85312023291e89c6d3087bc8fb"
+"checksum libssh2-sys 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)" = "126a1f4078368b163bfdee65fbab072af08a1b374a5551b21e87ade27b1fbf9d"
+"checksum libz-sys 1.0.25 (registry+https://github.com/rust-lang/crates.io-index)" = "2eb5e43362e38e2bca2fd5f5134c4d4564a23a5c28e9b95411652021a8675ebe"
+"checksum log 0.4.8 (registry+https://github.com/rust-lang/crates.io-index)" = "14b6052be84e6b71ab17edffc2eeabf5c2c3ae1fdb464aae35ac50c67a44e1f7"
+"checksum matches 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)" = "7ffc5c5338469d4d3ea17d269fa8ea3512ad247247c30bd2df69e68309ed0a08"
+"checksum openssl-probe 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "77af24da69f9d9341038eba93a073b1fdaaa1b788221b00a69bce9e762cb32de"
+"checksum openssl-sys 0.9.49 (registry+https://github.com/rust-lang/crates.io-index)" = "f4fad9e54bd23bd4cbbe48fdc08a1b8091707ac869ef8508edea2fec77dcc884"
+"checksum percent-encoding 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d4fd5641d01c8f18a23da7b6fe29298ff4b55afcccdf78973b24cf3175fee32e"
+"checksum pkg-config 0.3.15 (registry+https://github.com/rust-lang/crates.io-index)" = "a7c1d2cfa5a714db3b5f24f0915e74fcdf91d09d496ba61329705dda7774d2af"
+"checksum smallvec 0.6.10 (registry+https://github.com/rust-lang/crates.io-index)" = "ab606a9c5e214920bb66c458cd7be8ef094f813f20fe77a54cc7dbfff220d4b7"
+"checksum unicode-bidi 0.3.4 (registry+https://github.com/rust-lang/crates.io-index)" = "49f2bd0c6468a8230e1db229cff8029217cf623c767ea5d60bfbd42729ea54d5"
+"checksum unicode-normalization 0.1.8 (registry+https://github.com/rust-lang/crates.io-index)" = "141339a08b982d942be2ca06ff8b076563cbe223d1befd5450716790d44e2426"
+"checksum url 2.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "75b414f6c464c879d7f9babf951f23bc3743fb7313c081b2e6ca719067ea9d61"
+"checksum vcpkg 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "33dd455d0f96e90a75803cfeb7f948768c08d70a6de9a8d2362461935698bf95"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..fcde037
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "git-graph"
+version = "0.1.0"
+authors = ["tomsmeding <tom.smeding@gmail.com>"]
+edition = "2018"
+
+[dependencies]
+git2 = "^0.10.0"
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(())
+}