Replaces awesome_nested_set gem with a simple and more robust implementation of nested sets.

The concurrency tests added in this commit trigger dead locks and/or nested set inconsistency with awesome_nested_set.

git-svn-id: http://svn.redmine.org/redmine/trunk@13841 e93f8b46-1217-0410-a6f0-8f06a7374b81

3 files changed, 470 insertions, 0 deletions

diff --git a/lib/redmine/nested_set/issue_nested_set.rb b/lib/redmine/nested_set/issue_nested_set.rb
new file mode 100644
index 000000000..dac340ba3
--- /dev/null
+++ b/lib/redmine/nested_set/issue_nested_set.rb
@@ -0,0 +1,195 @@
+# Redmine - project management software
+# Copyright (C) 2006-2014  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+module Redmine
+  module NestedSet
+    module IssueNestedSet
+      def self.included(base)
+        base.class_eval do
+          belongs_to :parent, :class_name => self.name
+
+          before_create :add_to_nested_set, :if => lambda {|issue| issue.parent.present?}
+          after_create :add_as_root, :if => lambda {|issue| issue.parent.blank?}
+          before_update :handle_parent_change, :if => lambda {|issue| issue.parent_id_changed?}
+          before_destroy :destroy_children
+        end
+        base.extend ClassMethods
+        base.send :include, Redmine::NestedSet::Traversing
+      end
+
+      private
+
+      def target_lft
+        scope_for_max_rgt = self.class.where(:root_id => root_id).where(:parent_id => parent_id)
+        if id
+          #scope_for_max_rgt = scope_for_max_rgt.where("id < ?", id)
+        end
+        max_rgt = scope_for_max_rgt.maximum(:rgt)
+        if max_rgt
+          max_rgt + 1
+        elsif parent
+          parent.lft + 1
+        else
+          1
+        end
+      end
+
+      def add_to_nested_set(lock=true)
+        lock_nested_set if lock
+        parent.send :reload_nested_set_values
+        self.root_id = parent.root_id
+        self.lft = target_lft
+        self.rgt = lft + 1
+        self.class.where(:root_id => root_id).where("lft >= ? OR rgt >= ?", lft, lft).update_all([
+          "lft = CASE WHEN lft >= :lft THEN lft + 2 ELSE lft END, " +
+          "rgt = CASE WHEN rgt >= :lft THEN rgt + 2 ELSE rgt END",
+          {:lft => lft}
+        ])
+      end
+
+      def add_as_root
+        self.root_id = id
+        self.lft = 1
+        self.rgt = 2
+        self.class.where(:id => id).update_all(:root_id => root_id, :lft => lft, :rgt => rgt)
+      end
+
+      def handle_parent_change
+        lock_nested_set
+        reload_nested_set_values
+        if parent_id_was
+          remove_from_nested_set
+        end
+        if parent
+          move_to_nested_set
+        end
+        reload_nested_set_values
+      end
+
+      def move_to_nested_set
+        if parent
+          previous_root_id = root_id
+          self.root_id = parent.root_id
+          
+          lft_after_move = target_lft
+          self.class.where(:root_id => parent.root_id).update_all([
+            "lft = CASE WHEN lft >= :lft THEN lft + :shift ELSE lft END, " +
+            "rgt = CASE WHEN rgt >= :lft THEN rgt + :shift ELSE rgt END",
+            {:lft => lft_after_move, :shift => (rgt - lft + 1)}
+          ])
+    
+          self.class.where(:root_id => previous_root_id).update_all([
+            "root_id = :root_id, lft = lft + :shift, rgt = rgt + :shift",
+            {:root_id => parent.root_id, :shift => lft_after_move - lft}
+          ])
+    
+          self.lft, self.rgt = lft_after_move, (rgt - lft + lft_after_move)
+          parent.send :reload_nested_set_values
+        end
+      end
+
+      def remove_from_nested_set
+        self.class.where(:root_id => root_id).where("lft >= ? AND rgt <= ?", lft, rgt).
+          update_all(["root_id = :id, lft = lft - :shift, rgt = rgt - :shift", {:id => id, :shift => lft - 1}])
+    
+        self.class.where(:root_id => root_id).update_all([
+          "lft = CASE WHEN lft >= :lft THEN lft - :shift ELSE lft END, " +
+          "rgt = CASE WHEN rgt >= :lft THEN rgt - :shift ELSE rgt END",
+          {:lft => lft, :shift => rgt - lft + 1}
+        ])
+        self.root_id = id
+        self.lft, self.rgt = 1, (rgt - lft + 1)
+      end
+
+      def destroy_children
+        unless @without_nested_set_update
+          lock_nested_set
+          reload_nested_set_values
+        end
+        children.each {|c| c.send :destroy_without_nested_set_update}
+        reload
+        unless @without_nested_set_update
+          self.class.where(:root_id => root_id).where("lft > ? OR rgt > ?", lft, lft).update_all([
+            "lft = CASE WHEN lft > :lft THEN lft - :shift ELSE lft END, " +
+            "rgt = CASE WHEN rgt > :lft THEN rgt - :shift ELSE rgt END",
+            {:lft => lft, :shift => rgt - lft + 1}
+          ])
+        end
+      end
+
+      def destroy_without_nested_set_update
+        @without_nested_set_update = true
+        destroy
+      end
+
+      def reload_nested_set_values
+        self.root_id, self.lft, self.rgt = self.class.where(:id => id).pluck(:root_id, :lft, :rgt).first
+      end
+
+      def save_nested_set_values
+        self.class.where(:id => id).update_all(:root_id => root_id, :lft => lft, :rgt => rgt)
+      end
+
+      def move_possible?(issue)
+        !is_or_is_ancestor_of?(issue)
+      end
+
+      def lock_nested_set
+        lock = true
+        if self.class.connection.adapter_name =~ /sqlserver/i
+          lock = "WITH (ROWLOCK HOLDLOCK UPDLOCK)"
+        end
+        sets_to_lock = [id, parent_id].compact
+        self.class.reorder(:id).where("root_id IN (SELECT root_id FROM #{self.class.table_name} WHERE id IN (?))", sets_to_lock).lock(lock).ids
+      end
+
+      def nested_set_scope
+        self.class.order(:lft).where(:root_id => root_id)
+      end
+
+      def same_nested_set_scope?(issue)
+        root_id == issue.root_id
+      end
+
+      module ClassMethods
+        def rebuild_tree!
+          transaction do
+            reorder(:id).lock.ids
+            update_all(:root_id => nil, :lft => nil, :rgt => nil)
+            where(:parent_id => nil).update_all(["root_id = id, lft = ?, rgt = ?", 1, 2])
+            roots_with_children = joins("JOIN #{table_name} parent ON parent.id = #{table_name}.parent_id AND parent.id = parent.root_id").uniq.pluck("parent.id")
+            roots_with_children.each do |root_id|
+              rebuild_nodes(root_id)
+            end
+          end
+        end
+
+        private
+
+        def rebuild_nodes(parent_id = nil)
+          nodes = where(:parent_id => parent_id, :rgt => nil, :lft => nil).order(:id).to_a
+
+          nodes.each do |node|
+            node.send :add_to_nested_set, false
+            node.send :save_nested_set_values
+            rebuild_nodes node.id
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/redmine/nested_set/project_nested_set.rb b/lib/redmine/nested_set/project_nested_set.rb
new file mode 100644
index 000000000..699927508
--- /dev/null
+++ b/lib/redmine/nested_set/project_nested_set.rb
@@ -0,0 +1,159 @@
+# Redmine - project management software
+# Copyright (C) 2006-2014  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+module Redmine
+  module NestedSet
+    module ProjectNestedSet
+      def self.included(base)
+        base.class_eval do
+          belongs_to :parent, :class_name => self.name
+
+          before_create :add_to_nested_set
+          before_update :move_in_nested_set, :if => lambda {|project| project.parent_id_changed? || project.name_changed?}
+          before_destroy :destroy_children
+        end
+        base.extend ClassMethods
+        base.send :include, Redmine::NestedSet::Traversing
+      end
+
+      private
+
+      def target_lft
+        siblings_rgt = self.class.where(:parent_id => parent_id).where("name < ?", name).maximum(:rgt)
+        if siblings_rgt
+          siblings_rgt + 1
+        elsif parent_id
+          parent_lft = self.class.where(:id => parent_id).pluck(:lft).first
+          raise "Project id=#{id} with parent_id=#{parent_id}: parent missing or without 'lft' value" unless parent_lft
+          parent_lft + 1
+        else
+          1
+        end
+      end
+
+      def add_to_nested_set(lock=true)
+        lock_nested_set if lock
+        self.lft = target_lft
+        self.rgt = lft + 1
+        self.class.where("lft >= ? OR rgt >= ?", lft, lft).update_all([
+          "lft = CASE WHEN lft >= :lft THEN lft + 2 ELSE lft END, " +
+          "rgt = CASE WHEN rgt >= :lft THEN rgt + 2 ELSE rgt END",
+          {:lft => lft}
+        ])
+      end
+
+      def move_in_nested_set
+        lock_nested_set
+        reload_nested_set_values
+        a = lft
+        b = rgt
+        c = target_lft
+        unless c == a
+          if c > a
+            # Moving to the right
+            d = c - (b - a + 1)
+            scope = self.class.where(["lft BETWEEN :a AND :c - 1 OR rgt BETWEEN :a AND :c - 1", {:a => a, :c => c}])
+            scope.update_all([
+              "lft = CASE WHEN lft BETWEEN :a AND :b THEN lft + (:d - :a) WHEN lft BETWEEN :b + 1 AND :c - 1 THEN lft - (:b - :a + 1) ELSE lft END, " +
+              "rgt = CASE WHEN rgt BETWEEN :a AND :b THEN rgt + (:d - :a) WHEN rgt BETWEEN :b + 1 AND :c - 1 THEN rgt - (:b - :a + 1) ELSE rgt END",
+              {:a => a, :b => b, :c => c, :d => d}
+            ])
+          elsif c < a
+            # Moving to the left
+            scope = self.class.where("lft BETWEEN :c AND :b OR rgt BETWEEN :c AND :b", {:a => a, :b => b, :c => c})
+            scope.update_all([
+              "lft = CASE WHEN lft BETWEEN :a AND :b THEN lft - (:a - :c) WHEN lft BETWEEN :c AND :a - 1 THEN lft + (:b - :a + 1) ELSE lft END, " +
+              "rgt = CASE WHEN rgt BETWEEN :a AND :b THEN rgt - (:a - :c) WHEN rgt BETWEEN :c AND :a - 1 THEN rgt + (:b - :a + 1) ELSE rgt END",
+              {:a => a, :b => b, :c => c, :d => d}
+            ])
+          end
+          reload_nested_set_values
+        end
+      end
+
+      def destroy_children
+        unless @without_nested_set_update
+          lock_nested_set
+          reload_nested_set_values
+        end
+        children.each {|c| c.send :destroy_without_nested_set_update}
+        unless @without_nested_set_update
+          self.class.where("lft > ? OR rgt > ?", lft, lft).update_all([
+            "lft = CASE WHEN lft > :lft THEN lft - :shift ELSE lft END, " +
+            "rgt = CASE WHEN rgt > :lft THEN rgt - :shift ELSE rgt END",
+            {:lft => lft, :shift => rgt - lft + 1}
+          ])
+        end
+      end
+
+      def destroy_without_nested_set_update
+        @without_nested_set_update = true
+        destroy
+      end
+
+      def reload_nested_set_values
+        self.lft, self.rgt = Project.where(:id => id).pluck(:lft, :rgt).first
+      end
+
+      def save_nested_set_values
+        self.class.where(:id => id).update_all(:lft => lft, :rgt => rgt)
+      end
+
+      def move_possible?(project)
+        !is_or_is_ancestor_of?(project)
+      end
+
+      def lock_nested_set
+        lock = true
+        if self.class.connection.adapter_name =~ /sqlserver/i
+          lock = "WITH (ROWLOCK HOLDLOCK UPDLOCK)"
+        end
+        self.class.order(:id).lock(lock).ids
+      end
+
+      def nested_set_scope
+        self.class.order(:lft)
+      end
+
+      def same_nested_set_scope?(project)
+        true
+      end
+
+      module ClassMethods
+        def rebuild_tree!
+          transaction do
+            reorder(:id).lock.ids
+            update_all(:lft => nil, :rgt => nil)
+            rebuild_nodes
+          end
+        end
+
+        private
+
+        def rebuild_nodes(parent_id = nil)
+          nodes = Project.where(:parent_id => parent_id).where(:rgt => nil, :lft => nil).reorder(:name)
+
+          nodes.each do |node|
+            node.send :add_to_nested_set, false
+            node.send :save_nested_set_values
+            rebuild_nodes node.id
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/redmine/nested_set/traversing.rb b/lib/redmine/nested_set/traversing.rb
new file mode 100644
index 000000000..f1684c00b
--- /dev/null
+++ b/lib/redmine/nested_set/traversing.rb
@@ -0,0 +1,116 @@
+# Redmine - project management software
+# Copyright (C) 2006-2014  Jean-Philippe Lang
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+module Redmine
+  module NestedSet
+    module Traversing
+      def self.included(base)
+        base.class_eval do
+          scope :roots, lambda {where :parent_id => nil}
+          scope :leaves, lambda {where "#{table_name}.rgt - #{table_name}.lft = ?", 1}
+        end
+      end
+
+      # Returns true if the element has no parent
+      def root?
+        parent_id.nil?
+      end
+
+      # Returns true if the element has a parent
+      def child?
+        !root?
+      end
+
+      # Returns true if the element has no children
+      def leaf?
+        new_record? || (rgt - lft == 1)
+      end
+
+      # Returns the root element (ancestor with no parent)
+      def root
+        self_and_ancestors.first
+      end
+
+      # Returns the children
+      def children
+        if id.nil?
+          nested_set_scope.none
+        else
+          self.class.order(:lft).where(:parent_id => id)
+        end
+      end
+
+      # Returns the descendants that have no children
+      def leaves
+        descendants.where("#{self.class.table_name}.rgt - #{self.class.table_name}.lft = ?", 1)
+      end
+
+      # Returns the siblings
+      def siblings
+        nested_set_scope.where(:parent_id => parent_id).where("id <> ?", id)
+      end
+
+      # Returns the ancestors
+      def ancestors
+        if root?
+          nested_set_scope.none
+        else
+          nested_set_scope.where("#{self.class.table_name}.lft < ? AND #{self.class.table_name}.rgt > ?", lft, rgt)
+        end
+      end
+
+      # Returns the element and its ancestors
+      def self_and_ancestors
+        nested_set_scope.where("#{self.class.table_name}.lft <= ? AND #{self.class.table_name}.rgt >= ?", lft, rgt)
+      end
+
+      # Returns true if the element is an ancestor of other
+      def is_ancestor_of?(other)
+        same_nested_set_scope?(other) && other.lft > lft && other.rgt < rgt
+      end
+
+      # Returns true if the element equals other or is an ancestor of other
+      def is_or_is_ancestor_of?(other)
+        other == self || is_ancestor_of?(other)
+      end
+
+      # Returns the descendants
+      def descendants
+        if leaf?
+          nested_set_scope.none
+        else
+          nested_set_scope.where("#{self.class.table_name}.lft > ? AND #{self.class.table_name}.rgt < ?", lft, rgt)
+        end
+      end
+
+      # Returns the element and its descendants
+      def self_and_descendants
+        nested_set_scope.where("#{self.class.table_name}.lft >= ? AND #{self.class.table_name}.rgt <= ?", lft, rgt)
+      end
+
+      # Returns true if the element is a descendant of other
+      def is_descendant_of?(other)
+        same_nested_set_scope?(other) && other.lft < lft && other.rgt > rgt
+      end
+
+      # Returns true if the element equals other or is a descendant of other
+      def is_or_is_descendant_of?(other)
+        other == self || is_descendant_of?(other)
+      end
+    end
+  end
+end