11
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ So you're basically running a git log --follow | wc -l for every file in your working tree? That seems like a good way to kill time :) \$\endgroup\$ – Vogel612 Sep 5 '18 at 10:04
  • \$\begingroup\$ Basically @Vogel612, except —follow only works on a single file (according to the docs). My goal is to get the commit count for every file in the repository to identify “hot spots” to target for testing/refactoring. \$\endgroup\$ – RubberDuck Sep 5 '18 at 10:21
  • \$\begingroup\$ I wanted to play around with this but the only part I cannot figure out is the PathCount that is missing. Could you add this class or tell me where I can find it? \$\endgroup\$ – t3chb0t Nov 4 '18 at 16:22
  • 1
    \$\begingroup\$ Sure @t3chb0t. It’s just an immutable class with a couple properties. github.com/rubberduck203/GitNStats/blob/master/src/… \$\endgroup\$ – RubberDuck Nov 4 '18 at 16:28
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You’re imperative version is equivalent to the mutable version of my code using a fold. That confirms for me that simpler is better (until such a time I would need to parallelize, which would still be difficult because of the need to process in order). Thanks! \$\endgroup\$ – RubberDuck Sep 5 '18 at 16:19
  • \$\begingroup\$ @RubberDuck Absolutely. Even if you wanted to parallelize, it wouldn't be all that tough, because you can partition the input into smaller sets, do the groupings, then aggregate the groupings with a separate function at the end. The nice thing about this is it's fully atomic, with any of the versions: you can take all the PathCount results and GroupBy again to aggregate them. \$\endgroup\$ – 410_Gone Sep 5 '18 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.