class Bundler::PubGrub::VersionSolver

def resolve_conflict(incompatibility)
  logger.info { "conflict: #{incompatibility}" }
  new_incompatibility = nil
  while !incompatibility.failure?
    most_recent_term = nil
    most_recent_satisfier = nil
    difference = nil
    previous_level = 1
    incompatibility.terms.each do |term|
      satisfier = solution.satisfier(term)
      if most_recent_satisfier.nil?
        most_recent_term = term
        most_recent_satisfier = satisfier
      elsif most_recent_satisfier.index < satisfier.index
        previous_level = [previous_level, most_recent_satisfier.decision_level].max
        most_recent_term = term
        most_recent_satisfier = satisfier
        difference = nil
      else
        previous_level = [previous_level, satisfier.decision_level].max
      end
      if most_recent_term == term
        difference = most_recent_satisfier.term.difference(most_recent_term)
        if difference.empty?
          difference = nil
        else
          difference_satisfier = solution.satisfier(difference.inverse)
          previous_level = [previous_level, difference_satisfier.decision_level].max
        end
      end
    end
    if previous_level < most_recent_satisfier.decision_level ||
        most_recent_satisfier.decision?
      logger.info { "backtracking to #{previous_level}" }
      solution.backtrack(previous_level)
      if new_incompatibility
        add_incompatibility(new_incompatibility)
      end
      return incompatibility
    end
    new_terms = []
    new_terms += incompatibility.terms - [most_recent_term]
    new_terms += most_recent_satisfier.cause.terms.reject { |term|
      term.package == most_recent_satisfier.term.package
    }
    if difference
      new_terms << difference.invert
    end
    new_incompatibility = Incompatibility.new(new_terms, cause: Incompatibility::ConflictCause.new(incompatibility, most_recent_satisfier.cause))
    if incompatibility.to_s == new_incompatibility.to_s
      logger.info { "!! failed to resolve conflicts, this shouldn't have happened" }
      break
    end
    incompatibility = new_incompatibility
    partially = difference ? " partially" : ""
    logger.info { "! #{most_recent_term} is#{partially} satisfied by #{most_recent_satisfier.term}" }
    logger.info { "! which is caused by #{most_recent_satisfier.cause}" }
    logger.info { "! thus #{incompatibility}" }
  end
  raise SolveFailure.new(incompatibility)
end