# File lib/chef/cookbook_version_selector.rb, line 84
    def self.constrain(all_cookbooks, recipe_constraints)
      dep_graph = create_dependency_graph_from_cookbooks(all_cookbooks)

      # extract cookbook names from (possibly) fully-qualified recipe names
      cookbook_constraints = recipe_constraints.map do |recipe_spec|
        cookbook_name = (recipe_spec[:name][/^(.+)::/, 1] || recipe_spec[:name])
        DepSelector::SolutionConstraint.new(dep_graph.package(cookbook_name),
                                            recipe_spec[:version_constraint])
      end

      # Pass in the list of all available cookbooks (packages) so that
      # DepSelector can distinguish between "no version available for
      # cookbook X" and "no such cookbook X" when an environment
      # filters out all versions for a given cookbook.
      all_packages = all_cookbooks.inject([]) do |acc, (cookbook_name, cookbook_versions)|
        acc << dep_graph.package(cookbook_name)
        acc
      end

      # find a valid assignment of CoookbookVersions. If no valid
      # assignment exists, indicate which run_list_item causes the
      # unsatisfiability and try to hint at what might be wrong.
      soln =
        begin
          DepSelector::Selector.new(dep_graph).find_solution(cookbook_constraints, all_packages)
        rescue DepSelector::Exceptions::InvalidSolutionConstraints => e
          non_existent_cookbooks = e.non_existent_packages.map {|constraint| constraint.package.name}
          cookbooks_with_no_matching_versions = e.constrained_to_no_versions.map {|constraint| constraint.package.name}

          # Spend a whole lot of effort for pluralizing and
          # prettifying the message.
          message = ""
          if non_existent_cookbooks.length > 0
            message += "no such " + (non_existent_cookbooks.length > 1 ? "cookbooks" : "cookbook")
            message += " #{non_existent_cookbooks.join(", ")}"
          end

          if cookbooks_with_no_matching_versions.length > 0
            if message.length > 0
              message += "; "
            end

            message += "no versions match the constraints on " + (cookbooks_with_no_matching_versions.length > 1 ? "cookbooks" : "cookbook")
            message += " #{cookbooks_with_no_matching_versions.join(", ")}"
          end

          message = "Run list contains invalid items: #{message}."

          raise Chef::Exceptions::CookbookVersionSelection::InvalidRunListItems.new(message, non_existent_cookbooks, cookbooks_with_no_matching_versions)
        rescue DepSelector::Exceptions::NoSolutionExists => e
          raise Chef::Exceptions::CookbookVersionSelection::UnsatisfiableRunListItem.new(filter_dep_selector_message(e.message), e.unsatisfiable_solution_constraint, e.disabled_non_existent_packages, e.disabled_most_constrained_packages)
        end


      # map assignment back to CookbookVersion objects
      selected_cookbooks = {}
      soln.each_pair do |cb_name, cb_version|
        # TODO [cw, 2011/2/10]: related to the TODO in
        # create_dependency_graph_from_cookbooks, cbv.version
        # currently returns a String, so we must compare to
        # cb_version.to_s, since it's a for-real Version object.
        selected_cookbooks[cb_name] = all_cookbooks[cb_name].find{|cbv| cbv.version == cb_version.to_s}
      end
      selected_cookbooks
    end