Certain merges can lead to ignored commits during evaluation

[bluekeyes]

We recently found an internal PR where someone had effectively merged a branch with itself. When processing approvals for the PR, the sortCommits function

policy-bot/policy/approval/approve.go

Lines 449 to 468 in 55d042d

	func sortCommits(commits []*pull.Commit, head string) []*pull.Commit {
	commitsBySHA := make(map[string]*pull.Commit)
	for _, c := range commits {
	commitsBySHA[c.SHA] = c
	}
	ordered := make([]*pull.Commit, 0, len(commits))
	for {
	c, ok := commitsBySHA[head]
	if !ok {
	break
	}
	ordered = append(ordered, c)
	if len(c.Parents) == 0 {
	break
	}
	head = c.Parents[0]
	}
	return ordered
	}

orders commits by their parents, only using the first parent of each commit. Any commits not in that first parent chain are discarded from the result. This works if the second parent is always another branch, but if both parents are present on the PR branch, only exploring the first path can discard commits.

The result was that a user who should have been a contributor was able to approve the PR, because their commits were only reachable through the second parent of a merge commit.

I think we need to update sortCommits to make sure the result always contains every commit in the input. However, I'm not sure yet how to order commits in this situation (e.g. should we evaluate parents depth-first or breadth-first?). This sorting function was introduced as part of #602, so we'll need to make sure than any ordering is valid for the invalidate_on_push option.