diff options
author | Aaron Patterson <aaron.patterson@gmail.com> | 2013-10-09 14:38:14 -0700 |
---|---|---|
committer | Aaron Patterson <aaron.patterson@gmail.com> | 2013-10-09 14:38:14 -0700 |
commit | e73fbdf804633f8e151a33e681f370dfa0fbb3a0 (patch) | |
tree | fd599a06ab11047b8aa385bb8622dd75661007e0 /activerecord/lib/active_record/associations | |
parent | 9b15db51b78028bfecdb85595624de4b838adbd1 (diff) | |
download | rails-e73fbdf804633f8e151a33e681f370dfa0fbb3a0.tar.gz rails-e73fbdf804633f8e151a33e681f370dfa0fbb3a0.tar.bz2 rails-e73fbdf804633f8e151a33e681f370dfa0fbb3a0.zip |
make node search more efficient
Rather than search every node in the tree, comparing that node and all
of its parents every time, start at the root from both sides and work
our way down the tree
Diffstat (limited to 'activerecord/lib/active_record/associations')
4 files changed, 43 insertions, 3 deletions
diff --git a/activerecord/lib/active_record/associations/join_dependency.rb b/activerecord/lib/active_record/associations/join_dependency.rb index 871ca1c91d..fe0066bbe1 100644 --- a/activerecord/lib/active_record/associations/join_dependency.rb +++ b/activerecord/lib/active_record/associations/join_dependency.rb @@ -71,7 +71,7 @@ module ActiveRecord associations.reject { |association| join_assocs.detect { |a| node_cmp association, a } }.each { |association| - join_node = find_parent_node(association.parent) || @join_root + join_node = find_node(association.parent) || @join_root type = association.join_type find_or_build_scalar association.reflection, join_node, type } @@ -121,11 +121,28 @@ module ActiveRecord private - def find_parent_node(parent) - @join_root.find { |join_part| node_cmp parent, join_part } + def find_node(target_node) + stack = target_node.parents << target_node + + left = [@join_root] + right = stack.shift + + loop { + match = left.find { |l| l.match? right } + + if match + return match if stack.empty? + + left = match.children + right = stack.shift + else + return nil + end + } end def node_cmp(parent, join_part) + return true if parent == join_part return unless parent.class == join_part.class case parent 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 3f9afa8992..6dd0e04d4d 100644 --- a/activerecord/lib/active_record/associations/join_dependency/join_association.rb +++ b/activerecord/lib/active_record/associations/join_dependency/join_association.rb @@ -33,6 +33,10 @@ module ActiveRecord def parent_table_name; parent.table_name; end alias :alias_suffix :parent_table_name + def match?(other) + super && reflection == other.reflection + end + def join_constraints joins = [] tables = @tables.dup 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 d3bc3dd1ad..48de12bcd5 100644 --- a/activerecord/lib/active_record/associations/join_dependency/join_base.rb +++ b/activerecord/lib/active_record/associations/join_dependency/join_base.rb @@ -8,6 +8,11 @@ module ActiveRecord super(klass, nil) end + def match?(other) + return true if self == other + super && base_klass == other.base_klass + end + def aliased_prefix "t0" end 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 b8ce8ff46d..27304acceb 100644 --- a/activerecord/lib/active_record/associations/join_dependency/join_part.rb +++ b/activerecord/lib/active_record/associations/join_dependency/join_part.rb @@ -33,6 +33,20 @@ module ActiveRecord reflection.name end + 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| |