4 files changed, 575 insertions, 0 deletions
diff --git a/third_party/gerrit-queue/gerrit/changeset.go b/third_party/gerrit-queue/gerrit/changeset.go
new file mode 100644
index 000000000000..f71032a567cb
--- /dev/null
+++ b/third_party/gerrit-queue/gerrit/changeset.go
@@ -0,0 +1,117 @@
+package gerrit
+
+import (
+	"bytes"
+	"fmt"
+
+	goGerrit "github.com/andygrunwald/go-gerrit"
+	"github.com/apex/log"
+)
+
+// Changeset represents a single changeset
+// Relationships between different changesets are described in Series
+type Changeset struct {
+	changeInfo      *goGerrit.ChangeInfo
+	ChangeID        string
+	Number          int
+	Verified        int
+	CodeReviewed    int
+	Autosubmit      int
+	Submittable     bool
+	CommitID        string
+	ParentCommitIDs []string
+	OwnerName       string
+	Subject         string
+}
+
+// MakeChangeset creates a new Changeset object out of a goGerrit.ChangeInfo object
+func MakeChangeset(changeInfo *goGerrit.ChangeInfo) *Changeset {
+	return &Changeset{
+		changeInfo:      changeInfo,
+		ChangeID:        changeInfo.ChangeID,
+		Number:          changeInfo.Number,
+		Verified:        labelInfoToInt(changeInfo.Labels["Verified"]),
+		CodeReviewed:    labelInfoToInt(changeInfo.Labels["Code-Review"]),
+		Autosubmit:      labelInfoToInt(changeInfo.Labels["Autosubmit"]),
+		Submittable:     changeInfo.Submittable,
+		CommitID:        changeInfo.CurrentRevision, // yes, this IS the commit ID.
+		ParentCommitIDs: getParentCommitIDs(changeInfo),
+		OwnerName:       changeInfo.Owner.Name,
+		Subject:         changeInfo.Subject,
+	}
+}
+
+// IsAutosubmit returns true if the changeset is intended to be
+// automatically submitted by gerrit-queue.
+//
+// This is determined by the Change Owner setting +1 on the
+// "Autosubmit" label.
+func (c *Changeset) IsAutosubmit() bool {
+	return c.Autosubmit == 1
+}
+
+// IsVerified returns true if the changeset passed CI,
+// that's when somebody left the Approved (+1) on the "Verified" label
+func (c *Changeset) IsVerified() bool {
+	return c.Verified == 1
+}
+
+// IsCodeReviewed returns true if the changeset passed code review,
+// that's when somebody left the Recommended (+2) on the "Code-Review" label
+func (c *Changeset) IsCodeReviewed() bool {
+	return c.CodeReviewed == 2
+}
+
+func (c *Changeset) String() string {
+	var b bytes.Buffer
+	b.WriteString("Changeset")
+	b.WriteString(fmt.Sprintf("(commitID: %.7s, author: %s, subject: %s, submittable: %v)",
+		c.CommitID, c.OwnerName, c.Subject, c.Submittable))
+	return b.String()
+}
+
+// FilterChangesets filters a list of Changeset by a given filter function
+func FilterChangesets(changesets []*Changeset, f func(*Changeset) bool) []*Changeset {
+	newChangesets := make([]*Changeset, 0)
+	for _, changeset := range changesets {
+		if f(changeset) {
+			newChangesets = append(newChangesets, changeset)
+		} else {
+			log.WithField("changeset", changeset.String()).Debug("dropped by filter")
+		}
+	}
+	return newChangesets
+}
+
+// labelInfoToInt converts a goGerrit.LabelInfo to -2…+2 int
+func labelInfoToInt(labelInfo goGerrit.LabelInfo) int {
+	if labelInfo.Recommended.AccountID != 0 {
+		return 2
+	}
+	if labelInfo.Approved.AccountID != 0 {
+		return 1
+	}
+	if labelInfo.Disliked.AccountID != 0 {
+		return -1
+	}
+	if labelInfo.Rejected.AccountID != 0 {
+		return -2
+	}
+	return 0
+}
+
+// getParentCommitIDs returns the parent commit IDs of the goGerrit.ChangeInfo
+// There is usually only one parent commit ID, except for merge commits.
+func getParentCommitIDs(changeInfo *goGerrit.ChangeInfo) []string {
+	// obtain the RevisionInfo object
+	revisionInfo := changeInfo.Revisions[changeInfo.CurrentRevision]
+
+	// obtain the Commit object
+	commit := revisionInfo.Commit
+
+	commitIDs := make([]string, len(commit.Parents))
+	for i, commit := range commit.Parents {
+		commitIDs[i] = commit.Commit
+	}
+	return commitIDs
+}
diff --git a/third_party/gerrit-queue/gerrit/client.go b/third_party/gerrit-queue/gerrit/client.go
new file mode 100644
index 000000000000..314f97281c7e
--- /dev/null
+++ b/third_party/gerrit-queue/gerrit/client.go
@@ -0,0 +1,220 @@
+package gerrit
+
+import (
+	"fmt"
+
+	goGerrit "github.com/andygrunwald/go-gerrit"
+	"github.com/apex/log"
+
+	"net/url"
+)
+
+// passed to gerrit when retrieving changesets
+var additionalFields = []string{
+	"LABELS",
+	"CURRENT_REVISION",
+	"CURRENT_COMMIT",
+	"DETAILED_ACCOUNTS",
+	"SUBMITTABLE",
+}
+
+// IClient defines the gerrit.Client interface
+type IClient interface {
+	Refresh() error
+	GetHEAD() string
+	GetBaseURL() string
+	GetChangesetURL(changeset *Changeset) string
+	SubmitChangeset(changeset *Changeset) (*Changeset, error)
+	RebaseChangeset(changeset *Changeset, ref string) (*Changeset, error)
+	ChangesetIsRebasedOnHEAD(changeset *Changeset) bool
+	SerieIsRebasedOnHEAD(serie *Serie) bool
+	FilterSeries(filter func(s *Serie) bool) []*Serie
+	FindSerie(filter func(s *Serie) bool) *Serie
+}
+
+var _ IClient = &Client{}
+
+// Client provides some ways to interact with a gerrit instance
+type Client struct {
+	client      *goGerrit.Client
+	logger      *log.Logger
+	baseURL     string
+	projectName string
+	branchName  string
+	series      []*Serie
+	head        string
+}
+
+// NewClient initializes a new gerrit client
+func NewClient(logger *log.Logger, URL, username, password, projectName, branchName string) (*Client, error) {
+	urlParsed, err := url.Parse(URL)
+	if err != nil {
+		return nil, err
+	}
+	urlParsed.User = url.UserPassword(username, password)
+
+	goGerritClient, err := goGerrit.NewClient(urlParsed.String(), nil)
+	if err != nil {
+		return nil, err
+	}
+	return &Client{
+		client:      goGerritClient,
+		baseURL:     URL,
+		logger:      logger,
+		projectName: projectName,
+		branchName:  branchName,
+	}, nil
+}
+
+// refreshHEAD queries the commit ID of the selected project and branch
+func (c *Client) refreshHEAD() (string, error) {
+	branchInfo, _, err := c.client.Projects.GetBranch(c.projectName, c.branchName)
+	if err != nil {
+		return "", err
+	}
+	return branchInfo.Revision, nil
+}
+
+// GetHEAD returns the internally stored HEAD
+func (c *Client) GetHEAD() string {
+	return c.head
+}
+
+// Refresh causes the client to refresh internal view of gerrit
+func (c *Client) Refresh() error {
+	c.logger.Debug("refreshing from gerrit")
+	HEAD, err := c.refreshHEAD()
+	if err != nil {
+		return err
+	}
+	c.head = HEAD
+
+	var queryString = fmt.Sprintf("status:open project:%s branch:%s", c.projectName, c.branchName)
+	c.logger.Debugf("fetching changesets: %s", queryString)
+	changesets, err := c.fetchChangesets(queryString)
+	if err != nil {
+		return err
+	}
+
+	c.logger.Infof("assembling series…")
+	series, err := AssembleSeries(changesets, c.logger)
+	if err != nil {
+		return err
+	}
+	series = SortSeries(series)
+	c.series = series
+	return nil
+}
+
+// fetchChangesets fetches a list of changesets matching a passed query string
+func (c *Client) fetchChangesets(queryString string) (changesets []*Changeset, Error error) {
+	opt := &goGerrit.QueryChangeOptions{}
+	opt.Query = []string{
+		queryString,
+	}
+	opt.AdditionalFields = additionalFields
+	changes, _, err := c.client.Changes.QueryChanges(opt)
+	if err != nil {
+		return nil, err
+	}
+
+	changesets = make([]*Changeset, 0)
+	for _, change := range *changes {
+		changesets = append(changesets, MakeChangeset(&change))
+	}
+
+	return changesets, nil
+}
+
+// fetchChangeset downloads an existing Changeset from gerrit, by its ID
+// Gerrit's API is a bit sparse, and only returns what you explicitly ask it
+// This is used to refresh an existing changeset with more data.
+func (c *Client) fetchChangeset(changeID string) (*Changeset, error) {
+	opt := goGerrit.ChangeOptions{}
+	opt.AdditionalFields = []string{"LABELS", "DETAILED_ACCOUNTS"}
+	changeInfo, _, err := c.client.Changes.GetChange(changeID, &opt)
+	if err != nil {
+		return nil, err
+	}
+	return MakeChangeset(changeInfo), nil
+}
+
+// SubmitChangeset submits a given changeset, and returns a changeset afterwards.
+func (c *Client) SubmitChangeset(changeset *Changeset) (*Changeset, error) {
+	changeInfo, _, err := c.client.Changes.SubmitChange(changeset.ChangeID, &goGerrit.SubmitInput{})
+	if err != nil {
+		return nil, err
+	}
+	c.head = changeInfo.CurrentRevision
+	return c.fetchChangeset(changeInfo.ChangeID)
+}
+
+// RebaseChangeset rebases a given changeset on top of a given ref
+func (c *Client) RebaseChangeset(changeset *Changeset, ref string) (*Changeset, error) {
+	changeInfo, _, err := c.client.Changes.RebaseChange(changeset.ChangeID, &goGerrit.RebaseInput{
+		Base: ref,
+	})
+	if err != nil {
+		return changeset, err
+	}
+	return c.fetchChangeset(changeInfo.ChangeID)
+}
+
+// GetBaseURL returns the gerrit base URL
+func (c *Client) GetBaseURL() string {
+	return c.baseURL
+}
+
+// GetProjectName returns the configured gerrit project name
+func (c *Client) GetProjectName() string {
+	return c.projectName
+}
+
+// GetBranchName returns the configured gerrit branch name
+func (c *Client) GetBranchName() string {
+	return c.branchName
+}
+
+// GetChangesetURL returns the URL to view a given changeset
+func (c *Client) GetChangesetURL(changeset *Changeset) string {
+	return fmt.Sprintf("%s/c/%s/+/%d", c.GetBaseURL(), c.projectName, changeset.Number)
+}
+
+// ChangesetIsRebasedOnHEAD returns true if the changeset is rebased on the current HEAD
+func (c *Client) ChangesetIsRebasedOnHEAD(changeset *Changeset) bool {
+	if len(changeset.ParentCommitIDs) != 1 {
+		return false
+	}
+	return changeset.ParentCommitIDs[0] == c.head
+}
+
+// SerieIsRebasedOnHEAD returns true if the whole series is rebased on the current HEAD
+// this is already the case if the first changeset in the series is rebased on the current HEAD
+func (c *Client) SerieIsRebasedOnHEAD(serie *Serie) bool {
+	// an empty serie should not exist
+	if len(serie.ChangeSets) == 0 {
+		return false
+	}
+	return c.ChangesetIsRebasedOnHEAD(serie.ChangeSets[0])
+}
+
+// FilterSeries returns a subset of all Series, passing the given filter function
+func (c *Client) FilterSeries(filter func(s *Serie) bool) []*Serie {
+	matchedSeries := []*Serie{}
+	for _, serie := range c.series {
+		if filter(serie) {
+			matchedSeries = append(matchedSeries, serie)
+		}
+	}
+	return matchedSeries
+}
+
+// FindSerie returns the first serie that matches the filter, or nil if none was found
+func (c *Client) FindSerie(filter func(s *Serie) bool) *Serie {
+	for _, serie := range c.series {
+		if filter(serie) {
+			return serie
+		}
+	}
+	return nil
+}
diff --git a/third_party/gerrit-queue/gerrit/serie.go b/third_party/gerrit-queue/gerrit/serie.go
new file mode 100644
index 000000000000..788cf46f4ea6
--- /dev/null
+++ b/third_party/gerrit-queue/gerrit/serie.go
@@ -0,0 +1,112 @@
+package gerrit
+
+import (
+	"fmt"
+	"strings"
+
+	"github.com/apex/log"
+)
+
+// Serie represents a list of successive changesets with an unbroken parent -> child relation,
+// starting from the parent.
+type Serie struct {
+	ChangeSets []*Changeset
+}
+
+// GetParentCommitIDs returns the parent commit IDs
+func (s *Serie) GetParentCommitIDs() ([]string, error) {
+	if len(s.ChangeSets) == 0 {
+		return nil, fmt.Errorf("Can't return parent on a serie with zero ChangeSets")
+	}
+	return s.ChangeSets[0].ParentCommitIDs, nil
+}
+
+// GetLeafCommitID returns the commit id of the last commit in ChangeSets
+func (s *Serie) GetLeafCommitID() (string, error) {
+	if len(s.ChangeSets) == 0 {
+		return "", fmt.Errorf("Can't return leaf on a serie with zero ChangeSets")
+	}
+	return s.ChangeSets[len(s.ChangeSets)-1].CommitID, nil
+}
+
+// CheckIntegrity checks that the series contains a properly ordered and connected chain of commits
+func (s *Serie) CheckIntegrity() error {
+	logger := log.WithField("serie", s)
+	// an empty serie is invalid
+	if len(s.ChangeSets) == 0 {
+		return fmt.Errorf("An empty serie is invalid")
+	}
+
+	previousCommitID := ""
+	for i, changeset := range s.ChangeSets {
+		// we can't really check the parent of the first commit
+		// so skip verifying that one
+		logger.WithFields(log.Fields{
+			"changeset":        changeset.String(),
+			"previousCommitID": fmt.Sprintf("%.7s", previousCommitID),
+		}).Debug(" - verifying changeset")
+
+		parentCommitIDs := changeset.ParentCommitIDs
+		if len(parentCommitIDs) == 0 {
+			return fmt.Errorf("Changesets without any parent are not supported")
+		}
+		// we don't check parents of the first changeset in a series
+		if i != 0 {
+			if len(parentCommitIDs) != 1 {
+				return fmt.Errorf("Merge commits in the middle of a series are not supported (only at the beginning)")
+			}
+			if parentCommitIDs[0] != previousCommitID {
+				return fmt.Errorf("changesets parent commit id doesn't match previous commit id")
+			}
+		}
+		// update previous commit id for the next loop iteration
+		previousCommitID = changeset.CommitID
+	}
+	return nil
+}
+
+// FilterAllChangesets applies a filter function on all of the changesets in the series.
+// returns true if it returns true for all changesets, false otherwise
+func (s *Serie) FilterAllChangesets(f func(c *Changeset) bool) bool {
+	for _, changeset := range s.ChangeSets {
+		if f(changeset) == false {
+			return false
+		}
+	}
+	return true
+}
+
+func (s *Serie) String() string {
+	var sb strings.Builder
+	sb.WriteString(fmt.Sprintf("Serie[%d]", len(s.ChangeSets)))
+	if len(s.ChangeSets) == 0 {
+		sb.WriteString("()\n")
+		return sb.String()
+	}
+	parentCommitIDs, err := s.GetParentCommitIDs()
+	if err == nil {
+		if len(parentCommitIDs) == 1 {
+			sb.WriteString(fmt.Sprintf("(parent: %.7s)", parentCommitIDs[0]))
+		} else {
+			sb.WriteString("(merge: ")
+
+			for i, parentCommitID := range parentCommitIDs {
+				sb.WriteString(fmt.Sprintf("%.7s", parentCommitID))
+				if i < len(parentCommitIDs) {
+					sb.WriteString(", ")
+				}
+			}
+
+			sb.WriteString(")")
+
+		}
+	}
+	sb.WriteString(fmt.Sprintf("(%.7s..%.7s)",
+		s.ChangeSets[0].CommitID,
+		s.ChangeSets[len(s.ChangeSets)-1].CommitID))
+	return sb.String()
+}
+
+func shortCommitID(commitID string) string {
+	return commitID[:6]
+}
diff --git a/third_party/gerrit-queue/gerrit/series.go b/third_party/gerrit-queue/gerrit/series.go
new file mode 100644
index 000000000000..295193ee9503
--- /dev/null
+++ b/third_party/gerrit-queue/gerrit/series.go
@@ -0,0 +1,126 @@
+package gerrit
+
+import (
+	"sort"
+
+	"github.com/apex/log"
+)
+
+// AssembleSeries consumes a list of `Changeset`, and groups them together to series
+//
+// We initially put every Changeset in its own Serie
+//
+// As we have no control over the order of the passed changesets,
+// we maintain a lookup table, mapLeafToSerie,
+// which allows to lookup a serie by its leaf commit id
+// We concat series in a fixpoint approach
+// because both appending and prepending is much more complex.
+// Concatenation moves changesets of the later changeset in the previous one
+// in a cleanup phase, we remove orphaned series (those without any changesets inside)
+// afterwards, we do an integrity check, just to be on the safe side.
+func AssembleSeries(changesets []*Changeset, logger *log.Logger) ([]*Serie, error) {
+	series := make([]*Serie, 0)
+	mapLeafToSerie := make(map[string]*Serie, 0)
+
+	for _, changeset := range changesets {
+		l := logger.WithField("changeset", changeset.String())
+
+		l.Debug("creating initial serie")
+		serie := &Serie{
+			ChangeSets: []*Changeset{changeset},
+		}
+		series = append(series, serie)
+		mapLeafToSerie[changeset.CommitID] = serie
+	}
+
+	// Combine series using a fixpoint approach, with a max iteration count.
+	logger.Debug("glueing together phase")
+	for i := 1; i < 100; i++ {
+		didUpdate := false
+		logger.Debugf("at iteration %d", i)
+		for j, serie := range series {
+			l := logger.WithFields(log.Fields{
+				"i":     i,
+				"j":     j,
+				"serie": serie.String(),
+			})
+			parentCommitIDs, err := serie.GetParentCommitIDs()
+			if err != nil {
+				return series, err
+			}
+			if len(parentCommitIDs) != 1 {
+				// We can't append merge commits to other series
+				l.Infof("No single parent, skipping.")
+				continue
+			}
+			parentCommitID := parentCommitIDs[0]
+			l.Debug("Looking for a predecessor.")
+			// if there's another serie that has this parent as a leaf, glue together
+			if otherSerie, ok := mapLeafToSerie[parentCommitID]; ok {
+				if otherSerie == serie {
+					continue
+				}
+				l = l.WithField("otherSerie", otherSerie)
+
+				myLeafCommitID, err := serie.GetLeafCommitID()
+				if err != nil {
+					return series, err
+				}
+
+				// append our changesets to the other serie
+				l.Debug("Splicing together.")
+				otherSerie.ChangeSets = append(otherSerie.ChangeSets, serie.ChangeSets...)
+
+				delete(mapLeafToSerie, parentCommitID)
+				mapLeafToSerie[myLeafCommitID] = otherSerie
+
+				// orphan our serie
+				serie.ChangeSets = []*Changeset{}
+				// remove the orphaned serie from the lookup table
+				delete(mapLeafToSerie, myLeafCommitID)
+
+				didUpdate = true
+			} else {
+				l.Debug("Not found.")
+			}
+		}
+		series = removeOrphanedSeries(series)
+		if !didUpdate {
+			logger.Infof("converged after %d iterations", i)
+			break
+		}
+	}
+
+	// Check integrity, just to be on the safe side.
+	for _, serie := range series {
+		l := logger.WithField("serie", serie.String())
+		l.Debugf("checking integrity")
+		err := serie.CheckIntegrity()
+		if err != nil {
+			l.Errorf("checking integrity failed: %s", err)
+		}
+	}
+	return series, nil
+}
+
+// removeOrphanedSeries removes all empty series (that contain zero changesets)
+func removeOrphanedSeries(series []*Serie) []*Serie {
+	newSeries := []*Serie{}
+	for _, serie := range series {
+		if len(serie.ChangeSets) != 0 {
+			newSeries = append(newSeries, serie)
+		}
+	}
+	return newSeries
+}
+
+// SortSeries sorts a list of series by the number of changesets in each serie, descending
+func SortSeries(series []*Serie) []*Serie {
+	newSeries := make([]*Serie, len(series))
+	copy(newSeries, series)
+	sort.Slice(newSeries, func(i, j int) bool {
+		// the weight depends on the amount of changesets series changeset size
+		return len(series[i].ChangeSets) > len(series[j].ChangeSets)
+	})
+	return newSeries
+}