rewrite-merge-base.cs

        public int RemoveRedundant(ref Stored<Commit>[] array)
        {
            var cnt = array.Length;
            var work = new Stored<Commit>[cnt];
            var redundant = new bool[cnt];
            var filledIndex = new int[cnt - 1];
            int i, j, filled;

            for (i = 0; i < cnt; i++)
            {
                var minGeneration = array[i].Value.Generation;

                if (redundant[i])
                    continue;
                for (j = filled = 0; j < cnt; j++)
                {
                    if (i == j || redundant[j])
                    {
                        continue;
                    }

                    filledIndex[filled] = j;
                    work[filled++] = array[j];

                    if (array[j].Value.Generation < minGeneration)
                        minGeneration = array[j].Value.Generation;
                }

                var (_, flags) = PaintDownToCommon(array[i], work, minGeneration);

                if ((flags[array[i].Hash] & Parent2) != 0)
                {
                    redundant[i] = true;
                }

                for (j = 0; j < filled; j++)
                {
                    if ((flags[work[j].Hash] & Parent1) != 0)
                    {
                        redundant[filledIndex[j]] = true;
                    }
                }
            }
            for (i = filled = 0; i < cnt; i++)
                if (!redundant[i])
                    array[filled++] = work[i];
            for (j = filled, i = 0; i < cnt; i++)
                if (redundant[i])
                    array[j++] = work[i];
            return filled;
        }

        public List<Stored<Commit>> GetMergeBasesMany0(Stored<Commit> one, List<Stored<Commit>> twos)
        {
            var result = MergeBasesMany(one, twos).ToList();

            foreach (var two in twos)
            {
                if (one == two)
                    return result;
            }

            if (result.Count > 1)
            {
                return result;
            }

            var rslt = result.ToArray();

            RemoveRedundant(ref rslt);
            result = rslt.ToList();
            return result;
        }

        public List<Stored<Commit>> GetMergeBases(Stored<Commit> one, Stored<Commit> two)
        {
            return GetMergeBasesMany0(one, new[] {two}.ToList());
        }

        /*
         * This algorithm is a rewrite of the get_octopus_merge_bases function in git.
         * https://github.com/git/git/blob/ed843436dd4924c10669820cc73daf50f0b4dabd/commit.c#L930
         */
        public List<Stored<Commit>> GetOctopusMergeBases(List<Stored<Commit>> commits)
        {
            var resultList = new List<Stored<Commit>>();
            if (!commits.Any()) return resultList;

            foreach (var commit in commits)
            {
                List<Stored<Commit>> newCommits = null;
                LinkedList<Stored<Commit>> end = null;
                foreach (var result in resultList)
                {
                    var bases = new List<Stored<Commit>>();

                    bases = GetMergeBases(commit, result);

                    if (newCommits == null)
                    {
                        newCommits = bases;
                    }
                    else
                    {
                        end.
                    }
                }
            }
        }


        /*
         * This algorithm is a rewrite of the merge_bases_many function in git.
         * https://github.com/git/git/blob/ed843436dd4924c10669820cc73daf50f0b4dabd/commit.c#L898
         */
        public IEnumerable<Stored<Commit>> MergeBasesMany(Stored<Commit> self, ICollection<Stored<Commit>> others)
        {
            if (others.Any(other => self == other))
            {
                return new[] {self};
            }

            var (commits, flags) = PaintDownToCommon(self, others, 0);

            return commits.Where(commit => (flags[commit.Hash] & Stale) == 0).ToList();
        }

        /*
         * This algorithm is a rewrite of the paint_down_to_common function in git.
         * https://github.com/git/git/blob/ed843436dd4924c10669820cc73daf50f0b4dabd/commit.c#L837
         */
        public PaintingResult PaintDownToCommon(Stored<Commit> one, ICollection<Stored<Commit>> twos, int minGeneration)
        {
            if (one == null) throw new ArgumentNullException(nameof(one));

            var priorityQueue = new SortedSet<Stored<Commit>>(new GenTimeCommitComparer());
            var result = new List<Stored<Commit>>();
            var flagsOf = new Dictionary<string, CommitWalkFlags>();

            var queueHasNonStale = fun(() => priorityQueue.Any(x => !flagsOf[x.Hash].HasFlag(Stale)));

            var lastGen = int.MaxValue;

            flagsOf[one.Hash] |= Parent1;

            var storedCommitOne = _storage.Fetch<Commit>(one.Hash)
                .IfNone(() => throw new Exception("Commit not found"));

            if (!twos.Any())
            {
                result.Add(storedCommitOne);
                return new PaintingResult(result, flagsOf);
            }

            priorityQueue.Add(storedCommitOne);

            foreach (var two in twos)
            {
                flagsOf[two.Hash] |= Parent2;

                var storedCommitTwo = _storage.Fetch<Commit>(two.Hash)
                    .IfNone(() => throw new Exception("Commit not found"));

                priorityQueue.Add(storedCommitTwo);
            }

            while (queueHasNonStale())
            {
                var (hash, commit) = priorityQueue.Head();

                if (commit.Generation > lastGen)
                {
                    throw new Exception($"Bad generation skip {commit.Generation} > {lastGen} at {hash}");
                }
                lastGen = commit.Generation;

                if (commit.Generation < minGeneration)
                {
                    break;
                }

                var flags = flagsOf[hash] & (Parent1 | Parent2 | Stale);
                if (flags == (Parent1 | Parent2))
                {
                    if ((flagsOf[hash] & Result) == 0)
                    {
                        flagsOf[hash] |= Result;
                        result.Add((hash, commit));
                    }
                    flags |= Stale;
                }

                var parents = commit.Parents().ToSeq();
                while (parents.Any())
                {
                    var item = parents.Head;
                    parents = parents.Tail;

                    if ((flagsOf[item] & flags) == flags)
                    {
                        continue;
                    }

                    var parent = _storage.Fetch<Commit>(item)
                        .IfNone(() => throw new Exception("Commit not found"));
                    flagsOf[parent.Hash] |= flags;
                    priorityQueue.Add(parent);
                }
            }

            return new PaintingResult(result, flagsOf);
        }