Counting times a file was committed to Git

Question

A long time ago I implemented some code to walk the git commit graph. I recently updated the accompanying analytics part of the code base to follow file moves/renames in order to get a more accurate count of the number of times a particular file was committed.

Here's the original implementation of the commit count function. It naively stops tracking the number of commits after a file was renamed.(Not for review, just here for historical context.)

public static IEnumerable<PathCount> CountFileChanges(IEnumerable<(Commit, TreeEntryChanges)> diffs)
{
    return diffs
        .GroupBy<(Commit Commit, TreeEntryChanges Diff), string>(c => c.Diff.Path)
        .Select(x => new PathCount(x.Key, x.Count()))
        .OrderByDescending(s => s.Count);
}

This is my first implementation that correctly aggregates the commit counts for a file, regardless of renames.

using System;
using System.Collections.Generic;
using System.Linq;
using LibGit2Sharp;

namespace GitNStats.Core
{
    public delegate bool DiffFilterPredicate((Commit Commit, TreeEntryChanges TreeEntryChanges) diff);

    public static class Analysis
    {
        public static IEnumerable<PathCount> CountFileChanges(IEnumerable<(Commit, TreeEntryChanges)> diffs)
        {
            return diffs.Aggregate<(Commit Commit, TreeEntryChanges Diff), Dictionary<string, int>>(
                new Dictionary<string, int>(), //filename, count
                (acc, x) => {
                    /* OldPath == NewPath when file was created or removed,
                        so this it's okay to just always use OldPath */
                    acc[x.Diff.Path] = acc.GetOrDefault(x.Diff.OldPath, 0) + 1;

                    if (x.Diff.Status == ChangeKind.Renamed) {
                        acc.Remove(x.Diff.OldPath);
                    }

                    return acc;
                }
            )
            .Select(x => new PathCount(x.Key, x.Value))
            .OrderByDescending(s => s.Count);
        }
    }

    static class DictionaryExtensions
    {
        public static V GetOrDefault<K,V>(this Dictionary<K,V> dictionary, K key, V defaultValue)
        {
            return dictionary.TryGetValue(key, out V value) ? value : defaultValue;
        }
    }
}

I was unhappy with this because I'm directly modifying the state of the accumulator in the fold (Aggregate) operation, so I implemented the immutable version below.

public static IEnumerable<PathCount> CountFileChanges(IEnumerable<(Commit, TreeEntryChanges)> diffs)
{
    // Union must take an IEnumerable
    IEnumerable<KeyValuePair<K, V>> KeyValuePairEnumerable<K, V>(K key, V value) => 
        Enumerable.Repeat(new KeyValuePair<K, V>(key, value), 1);

    IEnumerable<KeyValuePair<string, int>> IncrementedPathCount(Dictionary<string, int> pathcounts, string currentPath, string lastPath) =>
        KeyValuePairEnumerable(currentPath, pathcounts.GetOrDefault(lastPath, 0) + 1);

    bool NotRenamed(KeyValuePair<string, int> kv, TreeEntryChanges diff) => 
        diff.Status != ChangeKind.Renamed || (diff.Status == ChangeKind.Renamed && kv.Key != diff.OldPath);

    return diffs.Aggregate<(Commit Commit, TreeEntryChanges Diff), Dictionary<string, int>>(
        new Dictionary<string, int>(), //filename, count
        (acc, x) =>
            acc.Where(kv => kv.Key != x.Diff.Path)                              //All records except the current one
                .Union(IncrementedPathCount(acc, x.Diff.Path, x.Diff.OldPath))  //Plus the current one, renamed if applicable
                .Where(kv => NotRenamed(kv, x.Diff))                            //Strip away obsolete file names
                .ToDictionary(kv => kv.Key, kv => kv.Value)

    )
    .Select(x => new PathCount(x.Key, x.Value))
    .OrderByDescending(s => s.Count);
}

But I honestly don't know if the second, more functional implementation is any better. It is now immutable, but I think I might have just muddied the waters and made the code harder to follow. The first version was stateful, but perhaps more simple and easy to follow. Thoughts?

Answer 1

I was going to say that this shouldn't be done in C#, but then after some thought last night, I came up with a really dirty idea.

You're basically trying to get the count of things that happened with a file, right? So if it was renamed, that's a thing, if it was created/removed, that's a thing, modified = a thing, etc.

In that case, we're basically just treating renamed as a special case.

First off: why do this functionally? This is actually a great place for a Dictionary and an imperative loop. Throw all of this away, and think about the problem more simply.

You want to count changes to each file, where Rename counts for both the old and new file, so to do so, we can really make life a lot easier by treating it as a quick loop over the dataset (I have no clue if this compiles, but I hope it demonstrates what I mean):

var result = new Dictionary<string, int>();
void addKey(string k, int v) =>
    result.ContainsKey(k) ? result[k] += v : result.Add(k, v);
foreach (var diff in diffs)
{
    addKey(diff.Path, 1);
    if (diff.Status == ChangeKind.Renamed)
    {
        addKey(diff.OldPath, 1);
    }
}
return result.Select(x => new PathCount(x.Key, x.Value)).OrderByDescending(s => s.Count);

Writing it functionally like you have just conflates it to a complex piece of code that, really, could be a lot simpler. In this case, imperative programming helps us out.

If you wanted to do it functionally, I'd do something like this in F#:

diffs
|> Seq.map (fun diff ->
    match diff.Status with
    | ChangeKind.Renamed -> [diff.OldPath; diff.Path]
    | _ -> [diff.Path])
|> Seq.concat
|> Seq.groupBy id
|> Seq.map (PathCount) // should be equivalent to Seq.map (fun (k, c) -> PathCount(k, c))
|> Seq.orderByDescending (fun s -> s.Count) // note that we're currently discussing a language design
                                            // change to make property access in Lambda's shorter,
                                            // but this is the most concise we can do at the moment

You could also fold (why bother?, again, keep it simple):

diffs
|> Seq.fold (fun acc diff ->
    match diff.Status with
    | ChangeKind.Renamed -> diff.OldPath :: (diff.Path :: acc)
    | _ -> diff.Path :: acc) []
|> Seq.groupBy id
|> Seq.map (PathCount) // should be equivalent to Seq.map (fun (k, c) -> PathCount(k, c))
|> Seq.orderByDescending (fun s -> s.Count)

While technically shorter, I wouldn't do this because it makes things less readable.