<commit_before>package vsolver

import (
	"container/heap"
	"fmt"
	"log"
	"math/rand"
	"strconv"
	"strings"

	"github.com/armon/go-radix"
	"github.com/hashicorp/go-immutable-radix"
)

var (
	// With a random revision and no name, collisions are unlikely
	nilpa = ProjectAtom{
		Version: Revision(strconv.FormatInt(rand.Int63(), 36)),
	}
)

// SolveOpts holds options that govern solving behavior, and the proper inputs
// to the solving process.
type SolveOpts struct {
	// The path to the root of the project on which the solver is working.
	Root string

	// The 'name' of the project. Required. This should (must?) correspond to subpath of
	// Root that exists under a GOPATH.
	N ProjectName

	// The root manifest. Required. This contains all the dependencies, constraints, and
	// other controls available to the root project.
	M Manifest

	// The root lock. Optional. Generally, this lock is the output of a previous solve run.
	//
	// If provided, the solver will attempt to preserve the versions specified
	// in the lock, unless ToChange or ChangeAll settings indicate otherwise.
	L Lock

	// Downgrade indicates whether the solver will attempt to upgrade (false) or
	// downgrade (true) projects that are not locked, or are marked for change.
	//
	// Upgrading is, by far, the most typical case. The field is named
	// 'Downgrade' so that the bool's zero value corresponds to that most
	// typical case.
	Downgrade bool

	// ChangeAll indicates that all projects should be changed - that is, any
	// versions specified in the root lock file should be ignored.
	ChangeAll bool

	// ToChange is a list of project names that should be changed - that is, any
	// versions specified for those projects in the root lock file should be
	// ignored.
	//
	// Passing ChangeAll has subtly different behavior from enumerating all
	// projects into ToChange. In general, ToChange should *only* be used if the
	// user expressly requested an upgrade for a specific project.
	ToChange []ProjectName

	// Trace controls whether the solver will generate informative trace output
	// as it moves through the solving process.
	Trace bool

	// TraceLogger is the logger to use for generating trace output. If Trace is
	// true but no logger is provided, solving will result in an error.
	TraceLogger *log.Logger
}

// solver is a CDCL-style SAT solver with satisfiability conditions hardcoded to
// the needs of the Go package management problem space.
type solver struct {
	// The current number of attempts made over the course of this solve. This
	// number increments each time the algorithm completes a backtrack and
	// starts moving forward again.
	attempts int

	// SolveOpts are the configuration options provided to the solver. The
	// solver will abort early if certain options are not appropriately set.
	o SolveOpts

	// Logger used exclusively for trace output, if the trace option is set.
	tl *log.Logger

	// A bridge to the standard SourceManager. The adapter does some local
	// caching of pre-sorted version lists, as well as translation between the
	// full-on ProjectIdentifiers that the solver deals with and the simplified
	// names a SourceManager operates on.
	b sourceBridge

	// The list of projects currently "selected" - that is, they have passed all
	// satisfiability checks, and are part of the current solution.
	//
	// The *selection type is mostly just a dumb data container; the solver
	// itself is responsible for maintaining that invariant.
	sel *selection

	// The current list of projects that we need to incorporate into the solution in
	// order for the solution to be complete. This list is implemented as a
	// priority queue that places projects least likely to induce errors at the
	// front, in order to minimize the amount of backtracking required to find a
	// solution.
	//
	// Entries are added to and removed from this list by the solver at the same
	// time that the selected queue is updated, either with an addition or
	// removal.
	unsel *unselected

	// A list of all the currently active versionQueues in the solver. The set
	// of projects represented here corresponds closely to what's in s.sel,
	// although s.sel will always contain the root project, and s.versions never
	// will.
	versions []*versionQueue

	// A map of the ProjectName (local names) that should be allowed to change
	chng map[ProjectName]struct{}

	// A map of the ProjectName (local names) that are currently selected, and
	// the network name to which they currently correspond.
	names map[ProjectName]string

	// A map of the names listed in the root's lock.
	rlm map[ProjectIdentifier]LockedProject

	// A normalized, copied version of the root manifest.
	rm Manifest

	// A radix tree representing the immediate externally reachable packages, as
	// determined by static analysis of the root project.
	xt *iradix.Tree
}

// Solve attempts to find a dependency solution for the given project, as
// represented by the provided SolveOpts.
//
// This is the entry point to the main vsolver workhorse.
func Solve(o SolveOpts, sm SourceManager) (Result, error) {
	s, err := prepareSolver(o, sm)
	if err != nil {
		return nil, err
	}

	return s.run()
}

// prepare reads from the SolveOpts and prepare the solver to run.
func prepareSolver(opts SolveOpts, sm SourceManager) (*solver, error) {
	// local overrides would need to be handled first.
	// TODO local overrides! heh

	if opts.M == nil {
		return nil, BadOptsFailure("Opts must include a manifest.")
	}
	if opts.Root == "" {
		return nil, BadOptsFailure("Opts must specify a non-empty string for the project root directory.")
	}
	if opts.N == "" {
		return nil, BadOptsFailure("Opts must include a project name.")
	}
	if opts.Trace && opts.TraceLogger == nil {
		return nil, BadOptsFailure("Trace requested, but no logger provided.")
	}

	s := &solver{
		o:  opts,
		b:  newBridge(sm, opts.Downgrade),
		tl: opts.TraceLogger,
	}

	// Initialize maps
	s.chng = make(map[ProjectName]struct{})
	s.rlm = make(map[ProjectIdentifier]LockedProject)
	s.names = make(map[ProjectName]string)

	// Initialize queues
	s.sel = &selection{
		deps: make(map[ProjectIdentifier][]Dependency),
		sm:   s.b,
	}
	s.unsel = &unselected{
		sl:  make([]ProjectIdentifier, 0),
		cmp: s.unselectedComparator,
	}

	return s, nil
}

// run executes the solver and creates an appropriate result.
func (s *solver) run() (Result, error) {
	// Ensure the root is in good, working order before doing anything else
	err := s.b.verifyRoot(s.o.Root)
	if err != nil {
		return nil, err
	}

	// Prep safe, normalized versions of root manifest and lock data
	s.rm = prepManifest(s.o.M)

	if s.o.L != nil {
		for _, lp := range s.o.L.Projects() {
			s.rlm[lp.Ident().normalize()] = lp
		}
	}

	for _, v := range s.o.ToChange {
		s.chng[v] = struct{}{}
	}

	// Prime the queues with the root project
	err = s.selectRoot()
	if err != nil {
		// TODO this properly with errs, yar
		panic("couldn't select root, yikes")
	}

	// Log initial step
	s.logSolve()
	pa, err := s.solve()

	// Solver finished with an err; return that and we're done
	if err != nil {
		return nil, err
	}

	// Solved successfully, create and return a result
	r := result{
		att: s.attempts,
		hd:  s.o.HashInputs(),
	}

	// Convert ProjectAtoms into LockedProjects
	r.p = make([]LockedProject, len(pa))
	for k, p := range pa {
		r.p[k] = pa2lp(p)
	}

	return r, nil
}

// solve is the top-level loop for the SAT solving process.
func (s *solver) solve() ([]ProjectAtom, error) {
	// Main solving loop
	for {
		id, has := s.nextUnselected()

		if !has {
			// no more packages to select - we're done. bail out
			break
		}

		s.logStart(id)
		queue, err := s.createVersionQueue(id)

		if err != nil {
			// Err means a failure somewhere down the line; try backtracking.
			if s.backtrack() {
				// backtracking succeeded, move to the next unselected id
				continue
			}
			return nil, err
		}

		if queue.current() == nil {
			panic("canary - queue is empty, but flow indicates success")
		}

		s.selectVersion(ProjectAtom{
			Ident:   queue.id,
			Version: queue.current(),
		})
		s.versions = append(s.versions, queue)
		s.logSolve()
	}

	// Getting this far means we successfully found a solution
	var projs []ProjectAtom
	// Skip the first project - it's always the root, and we don't want to
	// include that in the results.
	for _, p := range s.sel.projects[1:] {
		projs = append(projs, p)
	}
	return projs, nil
}

// selectRoot is a specialized selectAtomWithPackages, used solely to initially
// populate the queues at the beginning of a solve run.
func (s *solver) selectRoot() error {
	pa := ProjectAtom{
		Ident: ProjectIdentifier{
			LocalName: s.o.N,
		},
		// This is a hack so that the root project doesn't have a nil version.
		// It's sort of OK because the root never makes it out into the results.
		// We may need a more elegant solution if we discover other side
		// effects, though.
		Version: Revision(""),
	}

	// Push the root project onto the queue.
	// TODO maybe it'd just be better to skip this?
	s.sel.projects = append(s.sel.projects, pa)

	// If we're looking for root's deps, get it from opts and local root
	// analysis, rather than having the sm do it
	mdeps := append(s.rm.GetDependencies(), s.rm.GetDevDependencies()...)

	reach, err := s.b.computeRootReach(s.o.Root)
	if err != nil {
		return err
	}

	deps, err := intersectConstraintsWithImports(mdeps, reach)
	if err != nil {
		// TODO this could well happen; handle it with a more graceful error
		panic(fmt.Sprintf("shouldn't be possible %s", err))
	}

	for _, dep := range deps {
		s.sel.pushDep(Dependency{Depender: pa, Dep: dep})
		// Add all to unselected queue
		s.names[dep.Ident.LocalName] = dep.Ident.netName()
		heap.Push(s.unsel, dep.Ident)
	}

	return nil
}

func (s *solver) getImportsAndConstraintsOf(pa ProjectAtom) ([]completeDep, error) {
	var err error

	if s.rm.Name() == pa.Ident.LocalName {
		panic("Should never need to recheck imports/constraints from root during solve")
	}

	// Otherwise, work through the source manager to get project info and
	// static analysis information.
	info, err := s.b.getProjectInfo(pa)
	if err != nil {
		return nil, err
	}

	deps := info.GetDependencies()
	// TODO add overrides here...if we impl the concept (which we should)

	allex, err := s.b.externalReach(pa.Ident, pa.Version)
	if err != nil {
		return nil, err
	}

	// TODO impl this
	curp := s.sel.getSelectedPackagesIn(pa.Ident)
	// Use a map to dedupe the unique external packages
	exmap := make(map[string]struct{})
	for _, pkg := range curp {
		if expkgs, exists := allex[pkg]; !exists {
			// It should be impossible for there to be a selected package
			// that's not in the external reach map; such a condition should
			// have been caught earlier during satisfiability checks. So,
			// explicitly panic here (rather than implicitly when we try to
			// retrieve a nonexistent map entry) as a canary.
			panic("canary - selection contains an atom with pkgs that apparently don't actually exist")
		} else {
			for _, ex := range expkgs {
				exmap[ex] = struct{}{}
			}
		}
	}

	reach := make([]string, len(exmap))
	k := 0
	for pkg := range exmap {
		reach[k] = pkg
		k++
	}

	return intersectConstraintsWithImports(deps, reach)
}
<commit_msg>Small nit fixups<commit_after>package vsolver

import (
	"container/heap"
	"fmt"
	"log"
	"math/rand"
	"strconv"
	"strings"

	"github.com/armon/go-radix"
	"github.com/hashicorp/go-immutable-radix"
)

var (
	// With a random revision and no name, collisions are unlikely
	nilpa = ProjectAtom{
		Version: Revision(strconv.FormatInt(rand.Int63(), 36)),
	}
)

// SolveOpts holds options that govern solving behavior, and the proper inputs
// to the solving process.
type SolveOpts struct {
	// The path to the root of the project on which the solver is working.
	Root string

	// The 'name' of the project. Required. This should (must?) correspond to subpath of
	// Root that exists under a GOPATH.
	N ProjectName

	// The root manifest. Required. This contains all the dependencies, constraints, and
	// other controls available to the root project.
	M Manifest

	// The root lock. Optional. Generally, this lock is the output of a previous solve run.
	//
	// If provided, the solver will attempt to preserve the versions specified
	// in the lock, unless ToChange or ChangeAll settings indicate otherwise.
	L Lock

	// Downgrade indicates whether the solver will attempt to upgrade (false) or
	// downgrade (true) projects that are not locked, or are marked for change.
	//
	// Upgrading is, by far, the most typical case. The field is named
	// 'Downgrade' so that the bool's zero value corresponds to that most
	// typical case.
	Downgrade bool

	// ChangeAll indicates that all projects should be changed - that is, any
	// versions specified in the root lock file should be ignored.
	ChangeAll bool

	// ToChange is a list of project names that should be changed - that is, any
	// versions specified for those projects in the root lock file should be
	// ignored.
	//
	// Passing ChangeAll has subtly different behavior from enumerating all
	// projects into ToChange. In general, ToChange should *only* be used if the
	// user expressly requested an upgrade for a specific project.
	ToChange []ProjectName

	// Trace controls whether the solver will generate informative trace output
	// as it moves through the solving process.
	Trace bool

	// TraceLogger is the logger to use for generating trace output. If Trace is
	// true but no logger is provided, solving will result in an error.
	TraceLogger *log.Logger
}

// solver is a CDCL-style SAT solver with satisfiability conditions hardcoded to
// the needs of the Go package management problem space.
type solver struct {
	// The current number of attempts made over the course of this solve. This
	// number increments each time the algorithm completes a backtrack and
	// starts moving forward again.
	attempts int

	// SolveOpts are the configuration options provided to the solver. The
	// solver will abort early if certain options are not appropriately set.
	o SolveOpts

	// Logger used exclusively for trace output, if the trace option is set.
	tl *log.Logger

	// A bridge to the standard SourceManager. The adapter does some local
	// caching of pre-sorted version lists, as well as translation between the
	// full-on ProjectIdentifiers that the solver deals with and the simplified
	// names a SourceManager operates on.
	b sourceBridge

	// The list of projects currently "selected" - that is, they have passed all
	// satisfiability checks, and are part of the current solution.
	//
	// The *selection type is mostly just a dumb data container; the solver
	// itself is responsible for maintaining that invariant.
	sel *selection

	// The current list of projects that we need to incorporate into the solution in
	// order for the solution to be complete. This list is implemented as a
	// priority queue that places projects least likely to induce errors at the
	// front, in order to minimize the amount of backtracking required to find a
	// solution.
	//
	// Entries are added to and removed from this list by the solver at the same
	// time that the selected queue is updated, either with an addition or
	// removal.
	unsel *unselected

	// A list of all the currently active versionQueues in the solver. The set
	// of projects represented here corresponds closely to what's in s.sel,
	// although s.sel will always contain the root project, and s.versions never
	// will.
	versions []*versionQueue

	// A map of the ProjectName (local names) that should be allowed to change
	chng map[ProjectName]struct{}

	// A map of the ProjectName (local names) that are currently selected, and
	// the network name to which they currently correspond.
	names map[ProjectName]string

	// A map of the names listed in the root's lock.
	rlm map[ProjectIdentifier]LockedProject

	// A normalized, copied version of the root manifest.
	rm Manifest

	// A radix tree representing the immediate externally reachable packages, as
	// determined by static analysis of the root project.
	xt *iradix.Tree
}

// Solve attempts to find a dependency solution for the given project, as
// represented by the provided SolveOpts.
//
// This is the entry point to the main vsolver workhorse.
func Solve(o SolveOpts, sm SourceManager) (Result, error) {
	s, err := prepareSolver(o, sm)
	if err != nil {
		return nil, err
	}

	return s.run()
}

// prepare reads from the SolveOpts and prepare the solver to run.
func prepareSolver(opts SolveOpts, sm SourceManager) (*solver, error) {
	// local overrides would need to be handled first.
	// TODO local overrides! heh

	if opts.M == nil {
		return nil, BadOptsFailure("Opts must include a manifest.")
	}
	if opts.Root == "" {
		return nil, BadOptsFailure("Opts must specify a non-empty string for the project root directory.")
	}
	if opts.N == "" {
		return nil, BadOptsFailure("Opts must include a project name.")
	}
	if opts.Trace && opts.TraceLogger == nil {
		return nil, BadOptsFailure("Trace requested, but no logger provided.")
	}

	s := &solver{
		o:  opts,
		b:  newBridge(sm, opts.Downgrade),
		tl: opts.TraceLogger,
	}

	// Initialize maps
	s.chng = make(map[ProjectName]struct{})
	s.rlm = make(map[ProjectIdentifier]LockedProject)
	s.names = make(map[ProjectName]string)

	// Initialize queues
	s.sel = &selection{
		deps: make(map[ProjectIdentifier][]Dependency),
		sm:   s.b,
	}
	s.unsel = &unselected{
		sl:  make([]ProjectIdentifier, 0),
		cmp: s.unselectedComparator,
	}

	return s, nil
}

// run executes the solver and creates an appropriate result.
func (s *solver) run() (Result, error) {
	// Ensure the root is in good, working order before doing anything else
	err := s.b.verifyRoot(s.o.Root)
	if err != nil {
		return nil, err
	}

	// Prep safe, normalized versions of root manifest and lock data
	s.rm = prepManifest(s.o.M)

	if s.o.L != nil {
		for _, lp := range s.o.L.Projects() {
			s.rlm[lp.Ident().normalize()] = lp
		}
	}

	for _, v := range s.o.ToChange {
		s.chng[v] = struct{}{}
	}

	// Prime the queues with the root project
	err = s.selectRoot()
	if err != nil {
		// TODO this properly with errs, yar
		panic("couldn't select root, yikes")
	}

	// Log initial step
	s.logSolve()
	pa, err := s.solve()

	// Solver finished with an err; return that and we're done
	if err != nil {
		return nil, err
	}

	// Solved successfully, create and return a result
	r := result{
		att: s.attempts,
		hd:  s.o.HashInputs(),
	}

	// Convert ProjectAtoms into LockedProjects
	r.p = make([]LockedProject, len(pa))
	for k, p := range pa {
		r.p[k] = pa2lp(p)
	}

	return r, nil
}

// solve is the top-level loop for the SAT solving process.
func (s *solver) solve() ([]ProjectAtom, error) {
	// Main solving loop
	for {
		id, has := s.nextUnselected()

		if !has {
			// no more packages to select - we're done. bail out
			break
		}

		s.logStart(id)
		queue, err := s.createVersionQueue(id)

		if err != nil {
			// Err means a failure somewhere down the line; try backtracking.
			if s.backtrack() {
				// backtracking succeeded, move to the next unselected id
				continue
			}
			return nil, err
		}

		if queue.current() == nil {
			panic("canary - queue is empty, but flow indicates success")
		}

		s.selectVersion(ProjectAtom{
			Ident:   queue.id,
			Version: queue.current(),
		})
		s.versions = append(s.versions, queue)
		s.logSolve()
	}

	// Getting this far means we successfully found a solution
	var projs []ProjectAtom
	// Skip the first project - it's always the root, and we don't want to
	// include that in the results.
	for _, p := range s.sel.projects[1:] {
		projs = append(projs, p)
	}
	return projs, nil
}

// selectRoot is a specialized selectAtomWithPackages, used solely to initially
// populate the queues at the beginning of a solve run.
func (s *solver) selectRoot() error {
	pa := ProjectAtom{
		Ident: ProjectIdentifier{
			LocalName: s.o.N,
		},
		// This is a hack so that the root project doesn't have a nil version.
		// It's sort of OK because the root never makes it out into the results.
		// We may need a more elegant solution if we discover other side
		// effects, though.
		Version: Revision(""),
	}

	// Push the root project onto the queue.
	// TODO maybe it'd just be better to skip this?
	s.sel.projects = append(s.sel.projects, pa)

	// If we're looking for root's deps, get it from opts and local root
	// analysis, rather than having the sm do it
	mdeps := append(s.rm.GetDependencies(), s.rm.GetDevDependencies()...)

	reach, err := s.b.computeRootReach(s.o.Root)
	if err != nil {
		return err
	}

	deps, err := intersectConstraintsWithImports(mdeps, reach)
	if err != nil {
		// TODO this could well happen; handle it with a more graceful error
		panic(fmt.Sprintf("shouldn't be possible %s", err))
	}

	for _, dep := range deps {
		s.sel.pushDep(Dependency{Depender: pa, Dep: dep})
		// Add all to unselected queue
		s.names[dep.Ident.LocalName] = dep.Ident.netName()
		heap.Push(s.unsel, dep.Ident)
	}

	return nil
}

func (s *solver) getImportsAndConstraintsOf(pa ProjectAtom) ([]completeDep, error) {
	var err error

	if s.rm.Name() == pa.Ident.LocalName {
		panic("Should never need to recheck imports/constraints from root during solve")
	}

	// Work through the source manager to get project info and static analysis
	// information.
	info, err := s.b.getProjectInfo(pa)
	if err != nil {
		return nil, err
	}

	allex, err := s.b.externalReach(pa.Ident, pa.Version)
	if err != nil {
		return nil, err
	}

	curp := s.sel.getSelectedPackagesIn(pa.Ident)
	// Use a map to dedupe the unique external packages
	exmap := make(map[string]struct{})
	for pkg := range curp {
		if expkgs, exists := allex[pkg]; !exists {
			// It should be impossible for there to be a selected package
			// that's not in the external reach map; such a condition should
			// have been caught earlier during satisfiability checks. So,
			// explicitly panic here (rather than implicitly when we try to
			// retrieve a nonexistent map entry) as a canary.
			panic("canary - selection contains an atom with pkgs that apparently don't actually exist")
		} else {
			for _, ex := range expkgs {
				exmap[ex] = struct{}{}
			}
		}
	}

	reach := make([]string, len(exmap))
	k := 0
	for pkg := range exmap {
		reach[k] = pkg
		k++
	}

	deps := info.GetDependencies()
	// TODO add overrides here...if we impl the concept (which we should)

	return intersectConstraintsWithImports(deps, reach)
}

{'fraction_non_alphanumeric': 0.09586850288760551, 'fraction_numerical': 0.0007107952021323857, 'mean_word_length': 3.3091500765696784, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1481533', 'n_tokens_mistral': 7175, 'n_tokens_neox': 6720, 'n_words': 2902}