Proper recursive expansion of requirements with filtering

Expand requirements recursively while applying the same optional? and
recommended? filters that dependencies are run through. Options
generated by requirements are now checked against the correct list of
requirements, eliminating the temporary "best guess" logic in the
installer.

5 files changed, 59 insertions, 16 deletions

diff --git a/Library/Homebrew/formula.rb b/Library/Homebrew/formula.rb
index 1c551aa25..8c68ad568 100644
--- a/Library/Homebrew/formula.rb
+++ b/Library/Homebrew/formula.rb
@@ -7,7 +7,6 @@ require 'patches'
 require 'compilers'
 require 'build_environment'
 require 'build_options'
-require 'extend/set'
 
 
 class Formula
@@ -489,10 +488,8 @@ class Formula
   end
 
   # The full set of Requirements for this formula's dependency tree.
-  def recursive_requirements
-    reqs = ComparableSet.new
-    recursive_dependencies.each { |d| reqs.merge d.to_formula.requirements }
-    reqs.merge requirements
+  def recursive_requirements(&block)
+    Requirement.expand(self, &block)
   end
 
   def to_hash
diff --git a/Library/Homebrew/formula_installer.rb b/Library/Homebrew/formula_installer.rb
index 84a4a2cf5..ab021af0d 100644
--- a/Library/Homebrew/formula_installer.rb
+++ b/Library/Homebrew/formula_installer.rb
@@ -105,18 +105,14 @@ class FormulaInstaller
 
   def check_requirements
     unsatisfied = ARGV.filter_for_dependencies do
-      f.recursive_requirements.select do |req|
-        if req.satisfied?
-          false
+      f.recursive_requirements do |dependent, req|
+        if req.optional? || req.recommended?
+          Requirement.prune unless dependent.build.with?(req.name)
         elsif req.build?
-          not pour_bottle?
-        elsif req.optional? || req.recommended?
-          f.recursive_dependencies.map(&:to_formula).any? do |dep|
-            dep.build.with?(req.name)
-          end || f.build.with?(req.name)
-        else
-          true
+          Requirement.prune unless install_bottle?(dependent)
         end
+
+        Requirement.prune if req.satisfied?
       end
     end
 
diff --git a/Library/Homebrew/requirement.rb b/Library/Homebrew/requirement.rb
index 9b7d2ed8a..d93d412f4 100644
--- a/Library/Homebrew/requirement.rb
+++ b/Library/Homebrew/requirement.rb
@@ -106,4 +106,54 @@ class Requirement
       end
     end
   end
+
+  # Expand the requirements of dependent recursively, optionally yielding
+  # [dependent, req] pairs to allow callers to apply arbitrary filters to
+  # the list.
+  # The default filter, which is applied when a block is not given, omits
+  # optionals and recommendeds based on what the dependent has asked for.
+  def self.expand(dependent, &block)
+    reqs = ComparableSet.new
+
+    formulae = dependent.recursive_dependencies.map(&:to_formula)
+    formulae.unshift(dependent)
+
+    formulae.map(&:requirements).each do |requirements|
+      requirements.each do |req|
+        prune = catch(:prune) do
+          if block_given?
+            yield dependent, req
+          elsif req.optional? || req.recommended?
+            Requirement.prune unless dependent.build.with?(req.name)
+          end
+        end
+
+        next if prune
+
+        reqs << req
+      end
+    end
+
+    # We special case handling of X11Dependency and its subclasses to
+    # ensure the correct dependencies are present in the final list.
+    # If an X11Dependency is present after filtering, we eliminate
+    # all X11Dependency::Proxy objects from the list. If there aren't
+    # any X11Dependency objects, then we eliminate all but one of the
+    # proxy objects.
+    proxy = unless reqs.any? { |r| r.instance_of?(X11Dependency) }
+      reqs.find { |r| r.kind_of?(X11Dependency::Proxy) }
+    end
+
+    reqs.reject! do |r|
+      r.kind_of?(X11Dependency::Proxy)
+    end
+
+    reqs << proxy unless proxy.nil?
+    reqs
+  end
+
+  # Used to prune requirements when calling expand with a block.
+  def self.prune
+    throw(:prune, true)
+  end
 end
diff --git a/Library/Homebrew/requirements.rb b/Library/Homebrew/requirements.rb
index 1ef11dd5f..7538079b0 100644
--- a/Library/Homebrew/requirements.rb
+++ b/Library/Homebrew/requirements.rb
@@ -1,4 +1,5 @@
 require 'requirement'
+require 'extend/set'
 
 # A dependency on a language-specific module.
 class LanguageModuleDependency < Requirement
diff --git a/Library/Homebrew/test/test_x11_deps.rb b/Library/Homebrew/test/test_x11_deps.rb
index c455d03d3..433a2a1ab 100644
--- a/Library/Homebrew/test/test_x11_deps.rb
+++ b/Library/Homebrew/test/test_x11_deps.rb
@@ -1,6 +1,5 @@
 require 'testing_env'
 require 'requirements'
-require 'extend/set'
 
 class X11DependencyTests < Test::Unit::TestCase
   def test_eql_instances_are_eql