From 549b3b0919f28f843dc2a40b1e71c98a87c8652f Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Sun, 25 Aug 2019 14:19:13 +0200 Subject: Initial --- .gitignore | 4 ++ Cargo.lock | 193 +++++++++++++++++++++++++++++++++++++++++++++++++ Cargo.toml | 8 +++ src/errors.rs | 21 ++++++ src/main.rs | 228 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 454 insertions(+) create mode 100644 .gitignore create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 src/errors.rs create mode 100644 src/main.rs 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 "] +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 { + fn to_io_result(self) -> io::Result; +} + +impl ToIOResult for std::result::Result { + fn to_io_result(self) -> io::Result { + 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(mut vec: Vec) -> Vec { + 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(mut vec: Vec) -> Vec { + 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), + Reference(git2::Oid, Vec), +} + +impl HistoryNode { + fn oid(&self) -> git2::Oid { + match self { + &HistoryNode::Genesis(oid) => oid, + &HistoryNode::Merge(oid, _) => oid, + &HistoryNode::Reference(oid, _) => oid, + } + } +} + +struct HistoryCache bool> { + nodes: Vec, + cache: HashMap, + is_reference: F, +} + +impl bool> HistoryCache { + 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::>(); + macro_rules! build_recursive { + () => {{ + let list = parents.iter().map(|c| self.build_history(c)).collect::>(); + 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) -> Vec { + let mut result: Vec = 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 bool>(stream: &mut W, history: &mut HistoryCache, seen: &mut HashSet, refmap: &HashMap, 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::>(); + if args.len() != 2 { + eprintln!("Usage: {} ", args[0]); + std::process::exit(1); + } + + let repo = git2::Repository::open(&args[1]).to_io_result()?; + + let mut refmap: HashMap = 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(()) +} -- cgit v1.2.3