Created
July 10, 2018 19:57
-
-
Save Ephasme/b463c6479f6211fa99d5889d7e389392 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment