project_matrix.go

package model

import (
	"bytes"
	"encoding/json"
	"fmt"

	"github.com/evergreen-ci/evergreen/util"
	"github.com/evergreen-ci/utility"
	"github.com/pkg/errors"
)

// This file contains the code for matrix generation.
// Project matrices are a shortcut for defining many variants
// by combining multiple axes. A full explanation of the matrix format
// is available at https://github.com/evergreen-ci/evergreen/wiki/Project-Files#matrix-variant-definition.
//
// On a high level, matrix variant construction takes the following steps:
//   1. Matrix definitions are read as part of a project's `buildvariants` field
//  and moved into a separate "matrices" slice.
//   2. A tag selector evaluator is constructed for evaluating axis selectors
//   3. The matrix and axis definitions are passed to buildMatrixVariants, which
//  creates all combinations of matrix cells and removes excluded ones.
//   4. During the generation of a single cell, we merge all axis values for the cell
//  together to create a fully filled-in variant. Matrix rules concerning non-task settings
//  are evaluated as well. Rules `add_tasks` and `remove_tasks` are stored in the variant
//  for later evaluation.
//   5. Created variants are appended back to the project's list of buildvariants.
//   6. During evaluateBuildVariants in project_parser.go, rules are executed.

// matrix defines a set of variants programmatically by
// combining a series of axis values and rules.
type matrix struct {
	Id          string            `yaml:"matrix_name,omitempty" bson:"matrix_name,omitempty"`
	Spec        matrixDefinition  `yaml:"matrix_spec,omitempty" bson:"matrix_spec,omitempty"`
	Exclude     matrixDefinitions `yaml:"exclude_spec,omitempty" bson:"exclude,omitempty"`
	DisplayName string            `yaml:"display_name,omitempty" bson:"display_name,omitempty"`
	Tags        parserStringSlice `yaml:"tags,omitempty" bson:"tags,omitempty"`
	Modules     parserStringSlice `yaml:"modules,omitempty" bson:"modules,omitempty"`
	BatchTime   *int              `yaml:"batchtime,omitempty" bson:"batch_time,omitempty"`
	Stepback    *bool             `yaml:"stepback,omitempty" bson:"stepback,omitempty"`
	RunOn       parserStringSlice `yaml:"run_on,omitempty" bson:"run_on,omitempty"`
	Tasks       parserBVTaskUnits `yaml:"tasks,omitempty" bson:"tasks,omitempty"`
	Rules       []matrixRule      `yaml:"rules,omitempty" bson:"rules,omitempty"`
}

// matrixAxis represents one axis of a matrix definition.
type matrixAxis struct {
	Id          string      `yaml:"id,omitempty" bson:"id,omitempty"`
	DisplayName string      `yaml:"display_name,omitempty" bson:"display_name,omitempty"`
	Values      []axisValue `yaml:"values,omitempty" bson:"values,omitempty"`
}

// find returns the axisValue with the given name.
func (ma matrixAxis) find(id string) (axisValue, error) {
	for _, v := range ma.Values {
		if v.Id == id {
			return v, nil
		}
	}
	return axisValue{}, errors.Errorf("axis '%v' does not contain value '%v'", ma.Id, id)
}

// axisValues make up the "points" along a matrix axis. Values are
// combined during matrix evaluation to produce new variants.
type axisValue struct {
	Id          string            `yaml:"id,omitempty" bson:"id,omitempty"`
	DisplayName string            `yaml:"display_name,omitempty" bson:"display_name,omitempty"`
	Variables   util.Expansions   `yaml:"variables,omitempty" bson:"variables,omitempty"`
	RunOn       parserStringSlice `yaml:"run_on,omitempty" bson:"run_on,omitempty"`
	Tags        parserStringSlice `yaml:"tags,omitempty" bson:"tags,omitempty"`
	Modules     parserStringSlice `yaml:"modules,omitempty" bson:"modules,omitempty"`
	BatchTime   *int              `yaml:"batchtime,omitempty" bson:"batchtime,omitempty"`
	Stepback    *bool             `yaml:"stepback,omitempty" bson:"stepback,omitempty"`
}

// helper methods for tag selectors
func (av *axisValue) name() string   { return av.Id }
func (av *axisValue) tags() []string { return av.Tags }

// matrixValue represents a "cell" of a matrix
type matrixValue map[string]string

// String returns the matrixValue in simple JSON format
func (mv matrixValue) String() string {
	asJSON, err := json.Marshal(&mv)
	if err != nil {
		return fmt.Sprintf("%#v", mv)
	}
	return string(asJSON)
}

// matrixDefinition is a map of axis name -> axis value representing
// an n-dimensional matrix configuration.
type matrixDefinition map[string]parserStringSlice

// String returns the matrixDefinition in simple JSON format
func (mdef matrixDefinition) String() string {
	asJSON, err := json.Marshal(&mdef)
	if err != nil {
		return fmt.Sprintf("%#v", mdef)
	}
	return string(asJSON)
}

// allCells returns every value (cell) within the matrix definition.
// IMPORTANT: this logic assume that all selectors have been evaluated
// and no duplicates exist.
func (mdef matrixDefinition) allCells() ([]matrixValue, error) {
	// this should never happen, we handle empty defs but just for sanity
	if len(mdef) == 0 {
		return nil, nil
	}
	// You can think of the logic below as traversing an n-dimensional matrix,
	// emulating an n-dimensional for-loop using a set of counters (like an old-school
	// golf counter).  We're doing this iteratively to avoid the overhead and sloppy code
	// required to constantly copy and merge maps that using recursion would require.
	type axisCache struct {
		Id    string
		Vals  []string
		Count int
	}
	axes := []axisCache{}
	for axis, values := range mdef {
		if len(values) == 0 {
			return nil, errors.Errorf("axis '%s' has empty values list", axis)
		}
		axes = append(axes, axisCache{Id: axis, Vals: values})
	}
	carryOne := false
	cells := []matrixValue{}
	for {
		c := matrixValue{}
		for i := range axes {
			if carryOne {
				carryOne = false
				axes[i].Count = (axes[i].Count + 1) % len(axes[i].Vals)
				if axes[i].Count == 0 { // we overflowed--time to carry the one
					carryOne = true
				}
			}
			// set the current axis/value pair for the new cell
			c[axes[i].Id] = axes[i].Vals[axes[i].Count]
		}
		// if carryOne is still true, that means the final bucket overflowed--we've finished.
		if carryOne {
			break
		}
		cells = append(cells, c)
		// add one to the leftmost bucket on the next loop
		carryOne = true
	}
	return cells, nil
}

// evaluatedCopy returns a copy of the definition with its tag selectors evaluated.
func (mdef matrixDefinition) evaluatedCopy(ase *axisSelectorEvaluator) (matrixDefinition, []error) {
	var errs []error
	cpy := matrixDefinition{}
	for axis, vals := range mdef {
		evaluated, evalErrs := evaluateAxisTags(ase, axis, vals)
		if len(evalErrs) > 0 {
			errs = append(errs, evalErrs...)
			continue
		}
		cpy[axis] = evaluated
	}
	return cpy, errs
}

// contains returns whether a value is contained by a definition.
// Note that a value that doesn't contain every matrix axis will still
// be evaluated based on the axes that exist.
func (mdef matrixDefinition) contains(mv matrixValue) bool {
	for k, v := range mv {
		axis, ok := mdef[k]
		if !ok {
			return false
		}
		if !utility.StringSliceContains(axis, v) {
			return false
		}
	}
	return true
}

// matrixDefinitions is a helper type for parsing either a single definition
// or a slice of definitions from YAML.
type matrixDefinitions []matrixDefinition

// UnmarshalYAML allows the YAML parser to read both a single def or
// an array of them into a slice.
func (mds *matrixDefinitions) UnmarshalYAML(unmarshal func(interface{}) error) error {
	var single matrixDefinition
	if err := unmarshal(&single); err == nil {
		*mds = matrixDefinitions{single}
		return nil
	}
	var slice []matrixDefinition
	if err := unmarshal(&slice); err != nil {
		return err
	}
	*mds = slice
	return nil
}

// contain returns true if *any* of the definitions contain the given value.
func (mds matrixDefinitions) contain(v matrixValue) bool {
	for _, m := range mds {
		if m.contains(v) {
			return true
		}
	}
	return false
}

// evaluatedCopies is like evaluatedCopy, but for multiple definitions.
func (mds matrixDefinitions) evaluatedCopies(ase *axisSelectorEvaluator) (matrixDefinitions, []error) {
	var out matrixDefinitions
	var errs []error
	for _, md := range mds {
		evaluated, evalErrs := md.evaluatedCopy(ase)
		errs = append(errs, evalErrs...)
		out = append(out, evaluated)
	}
	return out, errs
}

// evaluateAxisTags returns an evaluated list of axis value ids with tag selectors evaluated.
func evaluateAxisTags(ase *axisSelectorEvaluator, axis string, selectors []string) ([]string, []error) {
	var errs []error
	all := map[string]struct{}{}
	for _, s := range selectors {
		ids, err := ase.evalSelector(axis, ParseSelector(s))
		if err != nil {
			errs = append(errs, err)
			continue
		}
		for _, id := range ids {
			all[id] = struct{}{}
		}
	}
	out := []string{}
	for id := range all {
		out = append(out, id)
	}
	return out, errs
}

func GetVariantsWithMatrices(ase *axisSelectorEvaluator, axes []matrixAxis, bvs []parserBV) ([]parserBV, []error) {
	if ase == nil {
		ase = NewAxisSelectorEvaluator(axes)
	}
	regularBVs, matrices := sieveMatrixVariants(bvs)
	matrixBVs, errs := buildMatrixVariants(axes, ase, matrices)
	return append(regularBVs, matrixBVs...), errs
}

// buildMatrixVariants takes in a list of axis definitions, an axisSelectorEvaluator, and a slice of
// matrix definitions. It returns a slice of parserBuildVariants constructed according to
// our matrix specification.
func buildMatrixVariants(axes []matrixAxis, ase *axisSelectorEvaluator, matrices []matrix) (
	[]parserBV, []error) {
	var errs []error
	// for each matrix, build out its declarations
	matrixVariants := []parserBV{}
	for i, m := range matrices {
		// for each axis value, iterate through possible inputs
		evaluatedSpec, evalErrs := m.Spec.evaluatedCopy(ase)
		if len(evalErrs) > 0 {
			errs = append(errs, evalErrs...)
			continue
		}
		evaluatedExcludes, evalErrs := m.Exclude.evaluatedCopies(ase)
		if len(evalErrs) > 0 {
			errs = append(errs, evalErrs...)
			continue
		}
		unpruned, err := evaluatedSpec.allCells()
		if err != nil {
			// If allCells fails we should exit immediately
			return nil, []error{err}
		}
		pruned := []parserBV{}
		for _, cell := range unpruned {
			// create the variant if it isn't excluded
			if !evaluatedExcludes.contain(cell) {
				v, err := buildMatrixVariant(axes, cell, &matrices[i], ase)
				if err != nil {
					errs = append(errs, errors.Wrapf(err, "building cell '%v' for matrix '%s'", cell, m.Id))
					continue
				}
				pruned = append(pruned, *v)
			}
		}
		// safety check to make sure the exclude field is actually working
		if len(m.Exclude) > 0 && len(unpruned) == len(pruned) {
			errs = append(errs, errors.Errorf("exclude field did not exclude anything for matrix '%s'", m.Id))
		}
		matrixVariants = append(matrixVariants, pruned...)
	}
	return matrixVariants, errs
}

// buildMatrixVariant does the heavy lifting of building a matrix variant based on axis information.
// We do this by iterating over all axes and merging the axis value's settings when applicable. Expansions
// are evaluated during this process. Rules are parsed and added to the resulting parserBV for later
// execution.
func buildMatrixVariant(axes []matrixAxis, mv matrixValue, m *matrix, ase *axisSelectorEvaluator) (*parserBV, error) {
	v := parserBV{
		MatrixVal:  mv,
		MatrixId:   m.Id,
		Stepback:   m.Stepback,
		BatchTime:  m.BatchTime,
		Modules:    m.Modules,
		RunOn:      m.RunOn,
		Expansions: *util.NewExpansions(mv),
	}
	// we declare a separate expansion map for evaluating the display name
	displayNameExp := util.Expansions{}

	// build up the variant id while iterating through axis values
	idBuf := bytes.Buffer{}
	idBuf.WriteString(m.Id)
	idBuf.WriteString("__")

	// track how many axes we cover, so we know the value is only using real axes
	usedAxes := 0

	// we must iterate over axis definitions to have a consistent ordering for our axis priority
	for _, a := range axes {
		// skip any axes that aren't used in the variant's definition
		if _, ok := mv[a.Id]; !ok {
			continue
		}
		usedAxes++
		axisVal, err := a.find(mv[a.Id])
		if err != nil {
			return nil, err
		}
		if err := v.mergeAxisValue(axisVal); err != nil {
			return nil, errors.Wrapf(err, "processing value '%s' for axis '%s'", axisVal.Id, a.Id)
		}
		// for display names, fall back to the axis values id so we have *something*
		if axisVal.DisplayName != "" {
			displayNameExp.Put(a.Id, axisVal.DisplayName)
		} else {
			displayNameExp.Put(a.Id, axisVal.Id)
		}

		// append to the variant's name
		idBuf.WriteString(a.Id)
		idBuf.WriteRune('~')
		idBuf.WriteString(axisVal.Id)
		if usedAxes < len(mv) {
			idBuf.WriteRune('_')
		}
	}
	if usedAxes != len(mv) {
		// we could make this error more helpful at the expense of extra complexity
		return nil, errors.Errorf("cell %v uses undefined axes", mv)
	}
	v.Name = idBuf.String()
	disp, err := displayNameExp.ExpandString(m.DisplayName)
	if err != nil {
		return nil, errors.Wrap(err, "processing display name")
	}
	v.DisplayName = disp

	// add final matrix-level tags and tasks
	if err := v.mergeAxisValue(axisValue{Tags: m.Tags}); err != nil {
		return nil, errors.Wrap(err, "processing matrix tags")
	}
	for _, t := range m.Tasks {
		expTask, err := expandParserBVTask(t, v.Expansions)
		if err != nil {
			return nil, errors.Wrapf(err, "processing task %s", t.Name)
		}
		v.Tasks = append(v.Tasks, expTask)
	}

	// evaluate rules for matching matrix values
	for i, rule := range m.Rules {
		r, err := expandRule(rule, v.Expansions)
		if err != nil {
			return nil, errors.Wrapf(err, "processing rule[%d]", i)
		}
		matchers, errs := r.If.evaluatedCopies(ase) // we could cache this
		if len(errs) > 0 {
			return nil, errors.Errorf("evaluating rules for matrix '%s': %v", m.Id, errs)
		}
		if matchers.contain(mv) {
			if r.Then.Set != nil {
				if err := v.mergeAxisValue(*r.Then.Set); err != nil {
					return nil, errors.Wrapf(err, "evaluating '%s' rule %d", m.Id, i)
				}
			}
			// we append add/remove task rules internally and execute them
			// during task evaluation, when other tasks are being evaluated.
			if len(r.Then.RemoveTasks) > 0 || len(r.Then.AddTasks) > 0 {
				v.MatrixRules = append(v.MatrixRules, r.Then)
			}
		}
	}
	return &v, nil
}

// matrixRule allows users to manipulate arbitrary matrix values using selectors.
type matrixRule struct {
	If   matrixDefinitions `yaml:"if" bson:"if,omitempty"`
	Then ruleAction        `yaml:"then" bson:"then,omitempty"`
}

// ruleAction is used to define what work must be done when
// "matrixRule.If" is satisfied.
type ruleAction struct {
	Set         *axisValue        `yaml:"set" bson:"set,omitempty"`
	RemoveTasks parserStringSlice `yaml:"remove_tasks" bson:"remove_tasks,omitempty"`
	AddTasks    parserBVTaskUnits `yaml:"add_tasks" bson:"add_tasks,omitempty"`
}

// mergeAxisValue overwrites a parserBV's fields based on settings
// in the axis value. Matrix expansions are evaluated as this process occurs.
// Returns any errors evaluating expansions.
func (pbv *parserBV) mergeAxisValue(av axisValue) error {
	// expand the variant's expansions (woah, dude) and update them
	if len(av.Variables) > 0 {
		expanded, err := expandExpansions(av.Variables, pbv.Expansions)
		if err != nil {
			return errors.Wrap(err, "expanding variables")
		}
		pbv.Expansions.Update(expanded)
	}
	// merge tags, removing dupes
	if len(av.Tags) > 0 {
		expanded, err := expandStrings(av.Tags, pbv.Expansions)
		if err != nil {
			return errors.Wrap(err, "expanding tags")
		}
		pbv.Tags = utility.UniqueStrings(append(pbv.Tags, expanded...))
	}
	// overwrite run_on
	var err error
	if len(av.RunOn) > 0 {
		pbv.RunOn, err = expandStrings(av.RunOn, pbv.Expansions)
		if err != nil {
			return errors.Wrap(err, "expanding run_on")
		}
	}
	// overwrite modules
	if len(av.Modules) > 0 {
		pbv.Modules, err = expandStrings(av.Modules, pbv.Expansions)
		if err != nil {
			return errors.Wrap(err, "expanding modules")
		}
	}
	if av.Stepback != nil {
		pbv.Stepback = av.Stepback
	}
	if av.BatchTime != nil {
		pbv.BatchTime = av.BatchTime
	}
	return nil
}

// expandStrings expands a slice of strings.
func expandStrings(strings []string, exp util.Expansions) ([]string, error) {
	var expanded []string
	for _, s := range strings {
		newS, err := exp.ExpandString(s)
		if err != nil {
			return nil, errors.WithStack(err)
		}
		expanded = append(expanded, newS)
	}
	return expanded, nil
}

// expandExpansions expands expansion maps.
func expandExpansions(in, exp util.Expansions) (util.Expansions, error) {
	newExp := util.Expansions{}
	for k, v := range in {
		newK, err := exp.ExpandString(k)
		if err != nil {
			return nil, errors.WithStack(err)
		}
		newV, err := exp.ExpandString(v)
		if err != nil {
			return nil, errors.WithStack(err)
		}
		newExp[newK] = newV
	}
	return newExp, nil
}

// expandParserBVTask expands strings inside parserBVTs.
func expandParserBVTask(pbvt parserBVTaskUnit, exp util.Expansions) (parserBVTaskUnit, error) {
	var err error
	newTask := pbvt
	newTask.Name, err = exp.ExpandString(pbvt.Name)
	if err != nil {
		return parserBVTaskUnit{}, errors.Wrap(err, "expanding name")
	}
	newTask.RunOn, err = expandStrings(pbvt.RunOn, exp)
	if err != nil {
		return parserBVTaskUnit{}, errors.Wrap(err, "expanding run_on")
	}
	newTask.Distros, err = expandStrings(pbvt.Distros, exp)
	if err != nil {
		return parserBVTaskUnit{}, errors.Wrap(err, "expanding distros")
	}
	var newDeps parserDependencies
	for i, d := range pbvt.DependsOn {
		newDep := d
		newDep.Status, err = exp.ExpandString(d.Status)
		if err != nil {
			return parserBVTaskUnit{}, errors.Wrapf(err, "expanding depends_on[%d/%d].status", i, len(pbvt.DependsOn))
		}
		newDep.TaskSelector, err = expandTaskSelector(d.TaskSelector, exp)
		if err != nil {
			return parserBVTaskUnit{}, errors.Wrapf(err, "expanding depends_on[%d/%d]", i, len(pbvt.DependsOn))
		}
		newDeps = append(newDeps, newDep)
	}
	newTask.DependsOn = newDeps
	return newTask, nil
}

// expandTaskSelector expands strings inside task selectors.
func expandTaskSelector(ts taskSelector, exp util.Expansions) (taskSelector, error) {
	newTS := taskSelector{}
	newName, err := exp.ExpandString(ts.Name)
	if err != nil {
		return newTS, errors.Wrap(err, "expanding name")
	}
	newTS.Name = newName
	if v := ts.Variant; v != nil {
		if len(v.MatrixSelector) > 0 {
			newMS, err := expandMatrixDefinition(v.MatrixSelector, exp)
			if err != nil {
				return newTS, errors.Wrap(err, "expanding variant")
			}
			newTS.Variant = &variantSelector{
				MatrixSelector: newMS,
			}
		} else {
			selector, err := exp.ExpandString(v.StringSelector)
			if err != nil {
				return newTS, errors.Wrap(err, "expanding variant")
			}
			newTS.Variant = &variantSelector{
				StringSelector: selector,
			}
		}
	}
	return newTS, nil
}

// expandMatrixDefinition expands strings inside matrix definitions.
func expandMatrixDefinition(md matrixDefinition, exp util.Expansions) (matrixDefinition, error) {
	var err error
	newMS := matrixDefinition{}
	for axis, vals := range md {
		newMS[axis], err = expandStrings(vals, exp)
		if err != nil {
			return nil, errors.Wrap(err, "matrix selector")
		}
	}
	return newMS, nil
}

// expandRules expands strings inside of rules.
func expandRule(r matrixRule, exp util.Expansions) (matrixRule, error) {
	newR := matrixRule{}
	for _, md := range r.If {
		newIf, err := expandMatrixDefinition(md, exp)
		if err != nil {
			return newR, errors.Wrap(err, "if")
		}
		newR.If = append(newR.If, newIf)
	}
	for _, t := range r.Then.AddTasks {
		newTask, err := expandParserBVTask(t, exp)
		if err != nil {
			return newR, errors.Wrap(err, "add_tasks")
		}
		newR.Then.AddTasks = append(newR.Then.AddTasks, newTask)
	}
	if len(r.Then.RemoveTasks) > 0 {
		var err error
		newR.Then.RemoveTasks, err = expandStrings(r.Then.RemoveTasks, exp)
		if err != nil {
			return newR, errors.Wrap(err, "remove_tasks")
		}
	}

	// r.Then.Set will be expanded when mergeAxisValue is called
	// so we don't have to do it in this function
	newR.Then.Set = r.Then.Set

	return newR, nil
}