Merge branch 'tree'

* tree: (22 commits)
  remove dead code
  add some convenient methods for avoiding array allocations
  hide join_constraints inside the JoinDependency object
  speed up match?
  expose the root node and call it
  just skip the join if it's already there
  speed up finding existing nodes
  make node search more efficient
  remove == so we can see where walking up parents occurs
  push parent up to the superclass
  convert JoinBase to a tree and remove the Node class
  names are guaranteed to be symbols
  eliminate function that is only used in one place
  we will always detect the same node, so just pass the node in
  we do not need to to_s the name all the time
  parent is guaranteed to be the same
  reduce number of comparisons and array allocations
  rename the variable to make more sense with a tree
  walk the tree rather than generating a hash and walking it
  do not convert the tree to a list just for the first node
  ...

5 files changed, 105 insertions, 109 deletions

diff --git a/activerecord/lib/active_record/associations/join_dependency.rb b/activerecord/lib/active_record/associations/join_dependency.rb
index f12d5c49b5..2fdb1970e1 100644
--- a/activerecord/lib/active_record/associations/join_dependency.rb
+++ b/activerecord/lib/active_record/associations/join_dependency.rb
@@ -4,7 +4,7 @@ module ActiveRecord
       autoload :JoinBase,        'active_record/associations/join_dependency/join_base'
       autoload :JoinAssociation, 'active_record/associations/join_dependency/join_association'
 
-      attr_reader :join_parts, :alias_tracker, :base_klass
+      attr_reader :alias_tracker, :base_klass, :join_root
 
       def self.make_tree(associations)
         hash = {}
@@ -54,43 +54,43 @@ module ActiveRecord
       def initialize(base, associations, joins)
         @base_klass    = base
         @table_joins   = joins
-        @join_parts    = [JoinBase.new(base)]
+        @join_root    = JoinBase.new(base)
         @alias_tracker = AliasTracker.new(base.connection, joins)
         @alias_tracker.aliased_name_for(base.table_name) # Updates the count for base.table_name to 1
         tree = self.class.make_tree associations
-        build tree, join_parts.last, Arel::InnerJoin
+        build tree, @join_root, Arel::InnerJoin
       end
 
       def graft(*associations)
-        join_assocs = join_associations
-        base        = join_base
-
-        associations.reject { |association|
-          join_assocs.detect { |a| association == a }
-        }.each { |association|
-          join_part = find_parent_part(association.parent) || base
-          type      = association.join_type
-          find_or_build_scalar association.reflection, join_part, type
+        associations.reject { |join_node|
+          find_node join_node
+        }.each { |join_node|
+          parent     = find_node(join_node.parent) || join_root
+          reflection = join_node.reflection
+          type       = join_node.join_type
+
+          next if parent.children.find { |j| j.reflection == reflection }
+          build_scalar reflection, parent, type
         }
         self
       end
 
-      def join_associations
-        join_parts.drop 1
-      end
-
       def reflections
-        join_associations.map(&:reflection)
+        join_root.drop(1).map!(&:reflection)
       end
 
       def join_relation(relation)
-        join_associations.inject(relation) do |rel,association|
+        join_root.inject(relation) do |rel,association|
           association.join_relation(rel)
         end
       end
 
+      def join_constraints
+        join_root.flat_map(&:join_constraints)
+      end
+
       def columns
-        join_parts.collect { |join_part|
+        join_root.collect { |join_part|
           table = join_part.aliased_table
           join_part.column_names_with_alias.collect{ |column_name, aliased_name|
             table[column_name].as Arel.sql(aliased_name)
@@ -99,16 +99,16 @@ module ActiveRecord
       end
 
       def instantiate(result_set)
-        primary_key = join_base.aliased_primary_key
+        primary_key = join_root.aliased_primary_key
         parents = {}
 
         type_caster = result_set.column_type primary_key
-        assoc = associations
+        assoc = join_root.children
 
         records = result_set.map { |row_hash|
           primary_id = type_caster.type_cast row_hash[primary_key]
-          parent = parents[primary_id] ||= join_base.instantiate(row_hash)
-          construct(parent, assoc, join_associations, row_hash, result_set)
+          parent = parents[primary_id] ||= join_root.instantiate(row_hash)
+          construct(parent, assoc, row_hash, result_set)
           parent
         }.uniq
 
@@ -118,30 +118,29 @@ module ActiveRecord
 
       private
 
-      def associations
-        join_associations.each_with_object({}) do |assoc, tree|
-          cache_joined_association assoc, tree
-        end
-      end
+      def find_node(target_node)
+        stack = target_node.parents << target_node
+
+        left  = [join_root]
+        right = stack.shift
 
-      def find_parent_part(parent)
-        join_parts.detect do |join_part|
-          case parent
-          when JoinBase
-            parent.base_klass == join_part.base_klass
+        loop {
+          match = left.find { |l| l.match? right }
+
+          if match
+            return match if stack.empty?
+
+            left  = match.children
+            right = stack.shift
           else
-            parent == join_part
+            return nil
           end
-        end
-      end
-
-      def join_base
-        join_parts.first
+        }
       end
 
       def remove_duplicate_results!(base, records, associations)
-        associations.each_key do |name|
-          reflection = base.reflect_on_association(name)
+        associations.each do |node|
+          reflection = base.reflect_on_association(node.name)
           remove_uniq_by_reflection(reflection, records)
 
           parent_records = []
@@ -156,26 +155,13 @@ module ActiveRecord
           end
 
           unless parent_records.empty?
-            remove_duplicate_results!(reflection.klass, parent_records, associations[name])
+            remove_duplicate_results!(reflection.klass, parent_records, node.children)
           end
         end
       end
 
-      def cache_joined_association(association, tree)
-        associations = []
-        parent = association.parent
-        while parent != join_base
-          associations.unshift(parent.reflection.name)
-          parent = parent.parent
-        end
-        ref = associations.inject(tree) do |cache,key|
-          cache[key]
-        end
-        ref[association.reflection.name] ||= {}
-      end
-
       def find_reflection(klass, name)
-        klass.reflect_on_association(name.intern) or
+        klass.reflect_on_association(name) or
           raise ConfigurationError, "Association named '#{ name }' was not found on #{ klass.name }; perhaps you misspelled it?"
       end
 
@@ -183,23 +169,14 @@ module ActiveRecord
         associations.each do |name, right|
           reflection = find_reflection parent.base_klass, name
           join_association = build_join_association reflection, parent, join_type
-          @join_parts << join_association
+          parent.children << join_association
           build right, join_association, join_type
         end
       end
 
-      def find_or_build_scalar(reflection, parent, join_type)
-        unless join_association = find_join_association(reflection, parent)
-          join_association = build_join_association(reflection, parent, join_type)
-          @join_parts << join_association
-        end
-        join_association
-      end
-
-      def find_join_association(reflection, parent)
-        join_associations.detect { |j|
-          j.reflection == reflection && j.parent == parent
-        }
+      def build_scalar(reflection, parent, join_type)
+        join_association = build_join_association(reflection, parent, join_type)
+        parent.children << join_association
       end
 
       def remove_uniq_by_reflection(reflection, records)
@@ -215,30 +192,16 @@ module ActiveRecord
           raise EagerLoadPolymorphicError.new(reflection)
         end
 
-        JoinAssociation.new(reflection, join_parts.length, parent, join_type, alias_tracker)
+        JoinAssociation.new(reflection, join_root.to_a.length, parent, join_type, alias_tracker)
       end
 
-      def construct(parent, associations, join_parts, row, rs)
-        associations.sort_by { |k,_| k.to_s }.each do |association_name, assoc|
-          association = construct_scalar(parent, association_name, join_parts, row, rs)
-          construct(association, assoc, join_parts, row, rs) if association
+      def construct(parent, nodes, row, rs)
+        nodes.sort_by { |k| k.name }.each do |node|
+          association = construct_association(parent, node, row, rs)
+          construct(association, node.children, row, rs) if association
         end
       end
 
-      def construct_scalar(parent, associations, join_parts, row, rs)
-        name = associations.to_s
-
-        join_part = join_parts.detect { |j|
-          j.reflection.name.to_s == name &&
-            j.parent_table_name == parent.class.table_name
-        }
-
-        raise(ConfigurationError, "No such association") unless join_part
-
-        join_parts.delete(join_part)
-        construct_association(parent, join_part, row, rs)
-      end
-
       def construct_association(record, join_part, row, rs)
         caster = rs.column_type(join_part.parent.aliased_primary_key)
         row_id = caster.type_cast row[join_part.parent.aliased_primary_key]
diff --git a/activerecord/lib/active_record/associations/join_dependency/join_association.rb b/activerecord/lib/active_record/associations/join_dependency/join_association.rb
index f6a04ef9f1..fe915c7730 100644
--- a/activerecord/lib/active_record/associations/join_dependency/join_association.rb
+++ b/activerecord/lib/active_record/associations/join_dependency/join_association.rb
@@ -9,10 +9,6 @@ module ActiveRecord
         # The reflection of the association represented
         attr_reader :reflection
 
-        # A JoinBase instance representing the active record we are joining onto.
-        # (So in Author.has_many :posts, the Author would be that base record.)
-        attr_reader :parent
-
         # What type of join will be generated, either Arel::InnerJoin (default) or Arel::OuterJoin
         attr_accessor :join_type
 
@@ -25,11 +21,10 @@ module ActiveRecord
         delegate :options, :through_reflection, :source_reflection, :chain, :to => :reflection
 
         def initialize(reflection, index, parent, join_type, alias_tracker)
-          super(reflection.klass)
+          super(reflection.klass, parent)
 
           @reflection      = reflection
           @alias_tracker   = alias_tracker
-          @parent          = parent
           @join_type       = join_type
           @aliased_prefix  = "t#{ index }"
           @tables          = construct_tables.reverse
@@ -38,10 +33,9 @@ module ActiveRecord
         def parent_table_name; parent.table_name; end
         alias :alias_suffix :parent_table_name
 
-        def ==(other)
-          other.class == self.class &&
-            other.reflection == reflection &&
-            other.parent == parent
+        def match?(other)
+          return true if self == other
+          super && reflection == other.reflection
         end
 
         def join_constraints
diff --git a/activerecord/lib/active_record/associations/join_dependency/join_base.rb b/activerecord/lib/active_record/associations/join_dependency/join_base.rb
index c689d06594..48de12bcd5 100644
--- a/activerecord/lib/active_record/associations/join_dependency/join_base.rb
+++ b/activerecord/lib/active_record/associations/join_dependency/join_base.rb
@@ -4,9 +4,13 @@ module ActiveRecord
   module Associations
     class JoinDependency # :nodoc:
       class JoinBase < JoinPart # :nodoc:
-        def ==(other)
-          other.class == self.class &&
-            other.base_klass == base_klass
+        def initialize(klass)
+          super(klass, nil)
+        end
+
+        def match?(other)
+          return true if self == other
+          super && base_klass == other.base_klass
         end
 
         def aliased_prefix
diff --git a/activerecord/lib/active_record/associations/join_dependency/join_part.rb b/activerecord/lib/active_record/associations/join_dependency/join_part.rb
index 2b6034ca9d..d536eaf613 100644
--- a/activerecord/lib/active_record/associations/join_dependency/join_part.rb
+++ b/activerecord/lib/active_record/associations/join_dependency/join_part.rb
@@ -8,25 +8,61 @@ module ActiveRecord
       # operations (for example a has_and_belongs_to_many JoinAssociation would result in
       # two; one for the join table and one for the target table).
       class JoinPart # :nodoc:
+        include Enumerable
+
+        # A JoinBase instance representing the active record we are joining onto.
+        # (So in Author.has_many :posts, the Author would be that base record.)
+        attr_reader :parent
+
         # The Active Record class which this join part is associated 'about'; for a JoinBase
         # this is the actual base model, for a JoinAssociation this is the target model of the
         # association.
-        attr_reader :base_klass
+        attr_reader :base_klass, :children
 
         delegate :table_name, :column_names, :primary_key, :arel_engine, :to => :base_klass
 
-        def initialize(base_klass)
+        def initialize(base_klass, parent)
           @base_klass = base_klass
+          @parent = parent
           @cached_record = {}
           @column_names_with_alias = nil
+          @children = []
         end
 
-        def aliased_table
-          Arel::Nodes::TableAlias.new table, aliased_table_name
+        def join_constraints; []; end
+        def join_relation(rel); rel; end
+
+        def name
+          reflection.name
         end
 
-        def ==(other)
-          raise NotImplementedError
+        def match?(other)
+          self.class == other.class
+        end
+
+        def parents
+          parents = []
+          node = parent
+          while node
+            parents.unshift node
+            node = node.parent
+          end
+          parents
+        end
+
+        def each
+          yield self
+          iter = lambda { |list|
+            list.each { |item|
+              yield item
+              iter.call item.children
+            }
+          }
+          iter.call children
+        end
+
+        def aliased_table
+          Arel::Nodes::TableAlias.new table, aliased_table_name
         end
 
         # An Arel::Table for the active_record
diff --git a/activerecord/lib/active_record/relation/query_methods.rb b/activerecord/lib/active_record/relation/query_methods.rb
index 9fcb6db726..e1efc6a189 100644
--- a/activerecord/lib/active_record/relation/query_methods.rb
+++ b/activerecord/lib/active_record/relation/query_methods.rb
@@ -952,8 +952,7 @@ module ActiveRecord
 
       join_dependency.graft(*stashed_association_joins)
 
-      joins = join_dependency.join_associations.map!(&:join_constraints)
-      joins.flatten!
+      joins = join_dependency.join_constraints
 
       joins.each { |join| manager.from(join) }