<commit_before>////////////////////////////////////////////////////////////////////////////////
// Resolver
////////////////////////////////////////////////////////////////////////////////

// XXX the whole resolver heavily relies on these statements to be true:
// - every unit version ever used was added to the resolver with addUnitVersion
// - every constraint ever used was instantiated with getConstraint
// - every constraint was added exactly once
// - every unit version was added exactly once
// - if two unit versions are the same, their refs point at the same object
// - if two constraints are the same, their refs point at the same object
ConstraintSolver.Resolver = function () {
  var self = this;

  // Maps unit name string to an array of version definitions
  self.unitsVersions = {};

  // Refs to all constraints. Mapping String -> instance
  self._constraints = {};
};

ConstraintSolver.Resolver.prototype.addUnitVersion = function (unitVersion) {
  var self = this;

  check(unitVersion, ConstraintSolver.UnitVersion);

  if (! _.has(self.unitsVersions, unitVersion.name))
    self.unitsVersions[unitVersion.name] = [];

  self.unitsVersions[unitVersion.name].push(unitVersion);
};

// name - String - "someUnit"
// versionConstraint - String - "=1.2.3" or "2.1.0"
ConstraintSolver.Resolver.prototype.getConstraint =
  function (name, versionConstraint) {
  var self = this;

  check(name, String);
  check(versionConstraint, String);

  var idString = JSON.stringify([name, versionConstraint]);

  if (_.has(self._constraints, idString))
    return self._constraints[idString];

  return self._constraints[idString] =
    new ConstraintSolver.Constraint(name, versionConstraint);
};

ConstraintSolver.Resolver.prototype.resolve =
  function (dependencies, constraints, choices, options) {
  var self = this;

  constraints = constraints || [];
  choices = choices || [];
  options = options || {};

  dependencies = _.uniq(dependencies);
  constraints = _.uniq(constraints);

  var exactDepsConstraints = _.filter(constraints, function (c) {
    return c.exact && _.contains(dependencies, c.name);
  });

  var exactDepsVersions = _.map(exactDepsConstraints, function (c) {
    return c.getSatisfyingUnitVersion(self);
  });

  var exactDepsNames = _.pluck(exactDepsVersions, "name");

  // Pick these versions as we have no choice but take them.
  choices = _.union(choices, exactDepsVersions);

  // Remove them from dependencies.
  dependencies = _.difference(dependencies, exactDepsNames);

  // Take exact dependencies and propagate them.
  _.each(exactDepsVersions, function (uv) {
    var propagatedExactTransDeps = self._propagateExactTransDeps(uv);
    dependencies = _.union(dependencies, propagatedExactTransDeps.dependencies);
    constraints = _.union(constraints, propagatedExactTransDeps.constraints);
    choices = _.union(choices, propagatedExactTransDeps.choices);
  });

  var result = self._resolve(dependencies, constraints, choices, options);

  if (! result.success)
    throw new Error(result.failureMsg);

  return result.choices;
};

// dependencies: [String] - remaining dependencies
// constraints: [ConstraintSolver.Constraint] - constraints to satisfy
// choices: [ConstraintSolver.UnitVersion] - current fixed set of choices
//
// returns {
//   success: Boolean,
//   failureMsg: String,
//   choices: [ConstraintSolver.UnitVersion]
// }
//
// NOTE: assumes that exact dependencies are already propagated
ConstraintSolver.Resolver.prototype._resolve =
  function (dependencies, constraints, choices, options) {
  var self = this;

  if (! choicesDontValidateConstraints(choices, constraints))
    return { success: false,
             failureMsg: "initial choices are validating constraints" };

  if (_.isEmpty(dependencies) || options.stopAfterFirstPropagation)
    return { success: true, choices: choices };

  var candidateName = dependencies[0];
  dependencies = dependencies.slice(1);

  var candidateVersions =
    _.filter(self.unitsVersions[candidateName], function (uv) {
      return unitVersionDoesntValidateConstraints(uv, constraints);
    });

  if (_.isEmpty(candidateVersions))
    return { success: false,
             failureMsg: "package constraint cannot be satisfied -- "
                         + candidateName };

  var winningChoices = null;
  _.each(candidateVersions, function (uv) {
    var nDependencies = _.clone(dependencies);
    var nConstraints = _.clone(constraints);
    var nChoices = _.clone(choices);

    nChoices.push(uv);
    var propagatedExactTransDeps =
      self._propagateExactTransDeps(uv);

    nDependencies = _.union(nDependencies, propagatedExactTransDeps.dependencies);
    nConstraints = _.union(nConstraints, propagatedExactTransDeps.constraints);
    nChoices = _.union(nChoices, propagatedExactTransDeps.choices);

    var result = self._resolve(nDependencies, nConstraints, nChoices, options);

    if (result.success) {
      winningChoices = result.choices;
      return false;
    }
  });

  if (winningChoices)
    return { success: true, choices: winningChoices };
  return { success: false,
           failureMsg: "cannot find a satisfying version for package "
                       + candidateName };
};

ConstraintSolver.Resolver.prototype._propagateExactTransDeps = function (uv) {
  var self = this;

  var exactTransitiveDepsVersions = uv.exactTransitiveDependenciesVersions(self);
  var inexactTransitiveDeps = uv.inexactTransitiveDependencies(self);
  var transitiveContraints = _.chain(exactTransitiveDepsVersions)
                              .map(function (uv) {
                                return uv.constraints;
                              }).flatten().uniq();

  // Since exact transitive deps are put into choices, there is no need to keep
  // them in dependencies. So only inexact deps are put to dependencies.
  return {
    dependencies: inexactTransitiveDeps,
    constraints: transitiveContraints,
    choices: exactTransitiveDepsVersions
  };
};

var unitVersionDoesntValidateConstraints = function (uv, constraints) {
  return _.all(constraints, function (c) {
    return c.name !== uv.name || c.isSatisfied(uv);
  });
};

var choicesDontValidateConstraints = function (choices, constraints) {
  return _.all(choices, function (uv) {
    return unitVersionDoesntValidateConstraints(uv, constraints);
  });
};

////////////////////////////////////////////////////////////////////////////////
// UnitVersion
////////////////////////////////////////////////////////////////////////////////<commit_msg>Finish chaining. Exclude the choices from dependencies list<commit_after>////////////////////////////////////////////////////////////////////////////////
// Resolver
////////////////////////////////////////////////////////////////////////////////

// XXX the whole resolver heavily relies on these statements to be true:
// - every unit version ever used was added to the resolver with addUnitVersion
// - every constraint ever used was instantiated with getConstraint
// - every constraint was added exactly once
// - every unit version was added exactly once
// - if two unit versions are the same, their refs point at the same object
// - if two constraints are the same, their refs point at the same object
ConstraintSolver.Resolver = function () {
  var self = this;

  // Maps unit name string to an array of version definitions
  self.unitsVersions = {};

  // Refs to all constraints. Mapping String -> instance
  self._constraints = {};
};

ConstraintSolver.Resolver.prototype.addUnitVersion = function (unitVersion) {
  var self = this;

  check(unitVersion, ConstraintSolver.UnitVersion);

  if (! _.has(self.unitsVersions, unitVersion.name))
    self.unitsVersions[unitVersion.name] = [];

  self.unitsVersions[unitVersion.name].push(unitVersion);
};

// name - String - "someUnit"
// versionConstraint - String - "=1.2.3" or "2.1.0"
ConstraintSolver.Resolver.prototype.getConstraint =
  function (name, versionConstraint) {
  var self = this;

  check(name, String);
  check(versionConstraint, String);

  var idString = JSON.stringify([name, versionConstraint]);

  if (_.has(self._constraints, idString))
    return self._constraints[idString];

  return self._constraints[idString] =
    new ConstraintSolver.Constraint(name, versionConstraint);
};

ConstraintSolver.Resolver.prototype.resolve =
  function (dependencies, constraints, choices, options) {
  var self = this;

  constraints = constraints || [];
  choices = choices || [];
  options = options || {};

  dependencies = _.uniq(dependencies);
  constraints = _.uniq(constraints);

  var exactDepsConstraints = _.filter(constraints, function (c) {
    return c.exact && _.contains(dependencies, c.name);
  });

  var exactDepsVersions = _.map(exactDepsConstraints, function (c) {
    return c.getSatisfyingUnitVersion(self);
  });

  var exactDepsNames = _.pluck(exactDepsVersions, "name");

  // Pick these versions as we have no choice but take them.
  choices = _.union(choices, exactDepsVersions);

  // Remove them from dependencies.
  dependencies = _.difference(dependencies, exactDepsNames);

  // Take exact dependencies and propagate them.
  _.each(exactDepsVersions, function (uv) {
    var propagatedExactTransDeps = self._propagateExactTransDeps(uv);
    dependencies = _.union(dependencies, propagatedExactTransDeps.dependencies);
    constraints = _.union(constraints, propagatedExactTransDeps.constraints);
    choices = _.union(choices, propagatedExactTransDeps.choices);
  });

  var result = self._resolve(dependencies, constraints, choices, options);

  if (! result.success)
    throw new Error(result.failureMsg);

  return result.choices;
};

// dependencies: [String] - remaining dependencies
// constraints: [ConstraintSolver.Constraint] - constraints to satisfy
// choices: [ConstraintSolver.UnitVersion] - current fixed set of choices
//
// returns {
//   success: Boolean,
//   failureMsg: String,
//   choices: [ConstraintSolver.UnitVersion]
// }
//
// NOTE: assumes that exact dependencies are already propagated
ConstraintSolver.Resolver.prototype._resolve =
  function (dependencies, constraints, choices, options) {
  var self = this;

  if (! choicesDontValidateConstraints(choices, constraints))
    return { success: false,
             failureMsg: "initial choices are validating constraints" };

  if (_.isEmpty(dependencies) || options.stopAfterFirstPropagation)
    return { success: true, choices: choices };

  var candidateName = dependencies[0];
  dependencies = dependencies.slice(1);

  var candidateVersions =
    _.filter(self.unitsVersions[candidateName], function (uv) {
      return unitVersionDoesntValidateConstraints(uv, constraints);
    });

  if (_.isEmpty(candidateVersions))
    return { success: false,
             failureMsg: "package constraint cannot be satisfied -- "
                         + candidateName };

  var winningChoices = null;
  _.each(candidateVersions, function (uv) {
    var nDependencies = _.clone(dependencies);
    var nConstraints = _.clone(constraints);
    var nChoices = _.clone(choices);

    nChoices.push(uv);
    var propagatedExactTransDeps =
      self._propagateExactTransDeps(uv);

    nDependencies = _.union(nDependencies, propagatedExactTransDeps.dependencies);
    nConstraints = _.union(nConstraints, propagatedExactTransDeps.constraints);
    nChoices = _.union(nChoices, propagatedExactTransDeps.choices);
    nDependencies = _.difference(nDependencies, _.pluck(nChoices, 'name'));

    var result = self._resolve(nDependencies, nConstraints, nChoices, options);

    if (result.success) {
      winningChoices = result.choices;
      return false;
    }
  });

  if (winningChoices)
    return { success: true, choices: winningChoices };
  return { success: false,
           failureMsg: "cannot find a satisfying version for package "
                       + candidateName };
};

ConstraintSolver.Resolver.prototype._propagateExactTransDeps = function (uv) {
  var self = this;

  var exactTransitiveDepsVersions = uv.exactTransitiveDependenciesVersions(self);
  var inexactTransitiveDeps = uv.inexactTransitiveDependencies(self);
  var transitiveContraints = _.chain(exactTransitiveDepsVersions)
                              .map(function (uv) {
                                return uv.constraints;
                              }).flatten().uniq().value();

  // Since exact transitive deps are put into choices, there is no need to keep
  // them in dependencies. So only inexact deps are put to dependencies.
  return {
    dependencies: inexactTransitiveDeps,
    constraints: transitiveContraints,
    choices: exactTransitiveDepsVersions
  };
};

var unitVersionDoesntValidateConstraints = function (uv, constraints) {
  return _.all(constraints, function (c) {
    return c.name !== uv.name || c.isSatisfied(uv);
  });
};

var choicesDontValidateConstraints = function (choices, constraints) {
  return _.all(choices, function (uv) {
    return unitVersionDoesntValidateConstraints(uv, constraints);
  });
};

////////////////////////////////////////////////////////////////////////////////
// UnitVersion
////////////////////////////////////////////////////////////////////////////////
{'fraction_non_alphanumeric': 0.14704548889224725, 'fraction_numerical': 0.0012090071029167296, 'mean_word_length': 3.0511172329354146, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, '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': '7574205', 'n_tokens_mistral': 3586, 'n_tokens_neox': 3416, 'n_words': 935}