123456789_123456789_123456789_123456789_123456789_

Class: RSpec::Matchers::BuiltIn::ContainExactly::PairingsMaximizer Private

Do not use. This class is for internal use only.
Relationships & Source Files
Namespace Children
Classes:
Solution
Inherits: Object
Defined in: rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb

Overview

Once we started supporting composing matchers, the algorithm for this matcher got much more complicated. Consider this expression:

expect(["fool", "food"]).to contain_exactly(/foo/, /fool/)

This should pass (because we can pair /fool/ with “fool” and /foo/ with “food”), but the original algorithm used by this matcher would pair the first elements it could (/foo/ with “fool”), which would leave /fool/ and “food” unmatched. When we have an expected element which is a matcher that matches a superset of actual items compared to another expected element matcher, we need to consider every possible pairing.

This class is designed to maximize the number of actual/expected pairings – or, conversely, to minimize the number of unpaired items. It’s essentially a brute force solution, but with a few heuristics applied to reduce the size of the problem space:

* Any items which match none of the items in the other list are immediately
  placed into the {unmatched_expected_indexes} or {unmatched_actual_indexes} array.
  The extra items and missing items in the matcher failure message are derived
  from these arrays.
* Any items which reciprocally match only each other are paired up and not
  considered further.

What’s left is only the items which match multiple items from the other list (or vice versa). From here, it performs a brute-force depth-first search, looking for a solution which pairs all elements in both lists, or, barring that, that produces the fewest unmatched items.

Constant Summary

Class Method Summary

Instance Attribute Summary

Instance Method Summary

Instance Attribute Details

#actual_to_expected_matched_indexes (readonly)

[ GitHub ] 

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 223



attr_reader :expected_to_actual_matched_indexes, :actual_to_expected_matched_indexes, :solution


  








  

    #expected_to_actual_matched_indexes   (readonly)
  

  [ GitHub ]


  

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 223



attr_reader :expected_to_actual_matched_indexes, :actual_to_expected_matched_indexes, :solution


  








  

    #solution   (readonly)
  

  [ GitHub ]


  

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 223



attr_reader :expected_to_actual_matched_indexes, :actual_to_expected_matched_indexes, :solution


  







Instance Method Details



  

    #apply_pairing_to(indeterminates, original_matches, other_list_index)   (private)
  

  [ GitHub ]


  

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 301



def apply_pairing_to(indeterminates, original_matches, other_list_index)
  indeterminates.inject({}) do |accum, index|
    accum[index] = original_matches[index] - [other_list_index]
    accum
  end
end


  








  

    #best_solution_for_pairing(expected_index, actual_index)   (private)
  

  [ GitHub ]


  

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 285



def best_solution_for_pairing(expected_index, actual_index)
  modified_expecteds = apply_pairing_to(
    solution.indeterminate_expected_indexes,
    expected_to_actual_matched_indexes, actual_index)

  modified_expecteds.delete(expected_index)

  modified_actuals = apply_pairing_to(
    solution.indeterminate_actual_indexes,
    actual_to_expected_matched_indexes, expected_index)

  modified_actuals.delete(actual_index)

  solution + self.class.new(modified_expecteds, modified_actuals).find_best_solution
end


  








  

    #categorize_indexes(indexes_to_categorize, other_indexes)   (private)
  

  [ GitHub ]


  

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 265



def categorize_indexes(indexes_to_categorize, other_indexes)
  unmatched     = []
  indeterminate = []

  indexes_to_categorize.each_pair do |index, matches|
    if matches.empty?
      unmatched << index
    elsif !reciprocal_single_match?(matches, index, other_indexes)
      indeterminate << index
    end
  end

  return unmatched, indeterminate
end


  








  

    #find_best_solution  
  

  [ GitHub ]


  

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 239



def find_best_solution
  return solution if solution.candidate?
  best_solution_so_far = NullSolution

  expected_index = solution.indeterminate_expected_indexes.first
  actuals = expected_to_actual_matched_indexes[expected_index]

  actuals.each do |actual_index|
    solution = best_solution_for_pairing(expected_index, actual_index)
    return solution if solution.ideal?
    best_solution_so_far = solution if best_solution_so_far.worse_than?(solution)
  end

  best_solution_so_far
end


  








  

    #reciprocal_single_match?(matches, index, other_list)  ⇒ Boolean  (private)
  



  

    
  





  


  [ GitHub ]


  

  


# File 'rspec-expectations/lib/rspec/matchers/built_in/contain_exactly.rb', line 280



def reciprocal_single_match?(matches, index, other_list)
  return false unless matches.one?
  other_list[matches.first] == [index]
end