##// END OF EJS Templates
jro_apps » redmine
RSS
Improved Issue#all_dependent_issues (#14015)....
Jean-Philippe Lang -
r11597:78dc37d8af13
parent child
Show More
Side by Side Unified
Context file:
r11597:78dc37d8af13 Loading diff...:
Show file before | Show file after | Hide comments
@@ -855,17 +855,109 class Issue < ActiveRecord::Base
855
855
856 # Returns all the other issues that depend on the issue
856 # Returns all the other issues that depend on the issue
857 def all_dependent_issues(except=[])
857 def all_dependent_issues(except=[])
858 except << self
858
859 # The algorithm as a modified bread first search (bfs)
860
861 # The found dependencies
859 dependencies = []
862 dependencies = []
860 dependencies += relations_from.map(&:issue_to)
863
861 dependencies += children unless leaf?
864 # The visited flag for every node (issue) used by the breadth first search
862 dependencies.compact!
865 eNOT_DISCOVERED = 0 # The issue is "new" to the algorithm, it has not seen it before.
866
867 ePROCESS_ALL = 1 # The issue is added to the queue. Process both children and relations of
868 # the issue when it is processed.
869
870 ePROCESS_RELATIONS_ONLY = 2 # The issue was added to the queue and will be output as dependent issue,
871 # but its children will not be added to the queue when it is processed.
872
873 eRELATIONS_PROCESSED = 3 # The related issues, the parent issue and the issue itself have been added to
874 # the queue, but its children have not been added.
875
876 ePROCESS_CHILDREN_ONLY = 4 # The relations and the parent of the issue have been added to the queue, but
877 # the children still need to be processed.
878
879 eALL_PROCESSED = 5 # The issue and all its children, its parent and its related issues have been
880 # added as dependent issues. It needs no further processing.
881
882 issueStatus = Hash.new(eNOT_DISCOVERED)
883
884 # The queue
885 queue = []
886
887 # Initialize the bfs, add start node (self) to the queue
888 queue << self
889 issueStatus[self] = ePROCESS_ALL
890
891 while (!queue.empty?) do
892
893 currentIssue = queue.shift
894 currentIssueStatus = issueStatus[currentIssue]
895
896 dependencies << currentIssue
897
898 # Add parent to queue, if not already in it.
899 parent = currentIssue.parent
900 parentStatus = issueStatus[parent]
901
902 if parent && (parentStatus == eNOT_DISCOVERED) && !except.include?(parent) then
903
904 queue << parent
905 issueStatus[parent] = ePROCESS_RELATIONS_ONLY
906
907 end
908
909 # Add children to queue, but only if they are not already in it and
910 # the children of the current node need to be processed.
911 if currentIssue.children && (currentIssueStatus == ePROCESS_CHILDREN_ONLY || currentIssueStatus == ePROCESS_ALL) then
912
913 currentIssue.children.each do |child|
914
915 if (issueStatus[child] == eNOT_DISCOVERED) && !except.include?(child)
916 queue << child
917 issueStatus[child] = ePROCESS_ALL
918
919 elsif (issueStatus[child] == eRELATIONS_PROCESSED) && !except.include?(child)
920 queue << child
921 issueStatus[child] = ePROCESS_CHILDREN_ONLY
922
923 elsif (issueStatus[child] == ePROCESS_RELATIONS_ONLY) && !except.include?(child)
924 queue << child
925 issueStatus[child] = ePROCESS_ALL
926 end
927 end
928 end
929
930 # Add related issues to the queue, if they are not already in it.
931 currentIssue.relations_from.map(&:issue_to).each do |relatedIssue|
932
933 if (issueStatus[relatedIssue] == eNOT_DISCOVERED) && !except.include?(relatedIssue) then
934 queue << relatedIssue
935 issueStatus[relatedIssue] = ePROCESS_ALL
936
937 elsif (issueStatus[relatedIssue] == eRELATIONS_PROCESSED) && !except.include?(relatedIssue) then
938 queue << relatedIssue
939 issueStatus[relatedIssue] = ePROCESS_CHILDREN_ONLY
940
941 elsif (issueStatus[relatedIssue] == ePROCESS_RELATIONS_ONLY) && !except.include?(relatedIssue) then
942 queue << relatedIssue
943 issueStatus[relatedIssue] = ePROCESS_ALL
944 end
945 end
946
947 # Set new status for current issue
948 if (currentIssueStatus == ePROCESS_ALL) || (currentIssueStatus == ePROCESS_CHILDREN_ONLY) then
949 issueStatus[currentIssue] = eALL_PROCESSED
950
951 elsif (currentIssueStatus == ePROCESS_RELATIONS_ONLY) then
952 issueStatus[currentIssue] = eRELATIONS_PROCESSED
953 end
954
955 end # while
956
957 # Remove the issues from the "except" parameter from the result array
863 dependencies -= except
958 dependencies -= except
864 dependencies += dependencies.map {|issue| issue.all_dependent_issues(except)}.flatten
959 dependencies.delete(self)
865 if parent
960
866 dependencies << parent
867 dependencies += parent.all_dependent_issues(except + parent.descendants)
868 end
869 dependencies
961 dependencies
870 end
962 end
871
963
Show file before | Show file after | Hide comments
@@ -1795,6 +1795,136 class IssueTest < ActiveSupport::TestCase
1795 assert_equal [2, 3, 8], Issue.find(1).all_dependent_issues.collect(&:id).sort
1795 assert_equal [2, 3, 8], Issue.find(1).all_dependent_issues.collect(&:id).sort
1796 end
1796 end
1797
1797
1798 def test_all_dependent_issues_with_subtask
1799 IssueRelation.delete_all
1800
1801 project = Project.generate!(:name => "testproject")
1802
1803 parentIssue = Issue.generate!(:project => project)
1804 childIssue1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue.id)
1805 childIssue2 = Issue.generate!(:project => project, :parent_issue_id => parentIssue.id)
1806
1807 assert_equal [childIssue1.id, childIssue2.id].sort, parentIssue.all_dependent_issues.collect(&:id).uniq.sort
1808 end
1809
1810 def test_all_dependent_issues_does_not_include_self
1811 IssueRelation.delete_all
1812
1813 project = Project.generate!(:name => "testproject")
1814
1815 parentIssue = Issue.generate!(:project => project)
1816 childIssue = Issue.generate!(:project => project, :parent_issue_id => parentIssue.id)
1817
1818 assert_equal [childIssue.id], parentIssue.all_dependent_issues.collect(&:id)
1819 end
1820
1821 def test_all_dependent_issues_with_parenttask_and_sibling
1822 IssueRelation.delete_all
1823
1824 project = Project.generate!(:name => "testproject")
1825
1826 parentIssue = Issue.generate!(:project => project)
1827 childIssue1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue.id)
1828 childIssue2 = Issue.generate!(:project => project, :parent_issue_id => parentIssue.id)
1829
1830 assert_equal [parentIssue.id].sort, childIssue1.all_dependent_issues.collect(&:id)
1831 end
1832
1833 def test_all_dependent_issues_with_relation_to_leaf_in_other_tree
1834 IssueRelation.delete_all
1835
1836 project = Project.generate!(:name => "testproject")
1837
1838 parentIssue1 = Issue.generate!(:project => project)
1839 childIssue1_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue1.id)
1840 childIssue1_2 = Issue.generate!(:project => project, :parent_issue_id => parentIssue1.id)
1841
1842 parentIssue2 = Issue.generate!(:project => project)
1843 childIssue2_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue2.id)
1844 childIssue2_2 = Issue.generate!(:project => project, :parent_issue_id => parentIssue2.id)
1845
1846
1847 assert IssueRelation.create(:issue_from => parentIssue1,
1848 :issue_to => childIssue2_2,
1849 :relation_type => IssueRelation::TYPE_BLOCKS)
1850
1851 assert_equal [childIssue1_1.id, childIssue1_2.id, parentIssue2.id, childIssue2_2.id].sort,
1852 parentIssue1.all_dependent_issues.collect(&:id).uniq.sort
1853 end
1854
1855 def test_all_dependent_issues_with_relation_to_parent_in_other_tree
1856 IssueRelation.delete_all
1857
1858 project = Project.generate!(:name => "testproject")
1859
1860 parentIssue1 = Issue.generate!(:project => project)
1861 childIssue1_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue1.id)
1862 childIssue1_2 = Issue.generate!(:project => project, :parent_issue_id => parentIssue1.id)
1863
1864 parentIssue2 = Issue.generate!(:project => project)
1865 childIssue2_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue2.id)
1866 childIssue2_2 = Issue.generate!(:project => project, :parent_issue_id => parentIssue2.id)
1867
1868
1869 assert IssueRelation.create(:issue_from => parentIssue1,
1870 :issue_to => parentIssue2,
1871 :relation_type => IssueRelation::TYPE_BLOCKS)
1872
1873 assert_equal [childIssue1_1.id, childIssue1_2.id, parentIssue2.id, childIssue2_1.id, childIssue2_2.id].sort,
1874 parentIssue1.all_dependent_issues.collect(&:id).uniq.sort
1875 end
1876
1877 def test_all_dependent_issues_with_transitive_relation
1878 IssueRelation.delete_all
1879
1880 project = Project.generate!(:name => "testproject")
1881
1882 parentIssue1 = Issue.generate!(:project => project)
1883 childIssue1_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue1.id)
1884
1885 parentIssue2 = Issue.generate!(:project => project)
1886 childIssue2_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue2.id)
1887
1888 independentIssue = Issue.generate!(:project => project)
1889
1890 assert IssueRelation.create(:issue_from => parentIssue1,
1891 :issue_to => childIssue2_1,
1892 :relation_type => IssueRelation::TYPE_RELATES)
1893
1894 assert IssueRelation.create(:issue_from => childIssue2_1,
1895 :issue_to => independentIssue,
1896 :relation_type => IssueRelation::TYPE_RELATES)
1897
1898 assert_equal [childIssue1_1.id, parentIssue2.id, childIssue2_1.id, independentIssue.id].sort,
1899 parentIssue1.all_dependent_issues.collect(&:id).uniq.sort
1900 end
1901
1902 def test_all_dependent_issues_with_transitive_relation2
1903 IssueRelation.delete_all
1904
1905 project = Project.generate!(:name => "testproject")
1906
1907 parentIssue1 = Issue.generate!(:project => project)
1908 childIssue1_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue1.id)
1909
1910 parentIssue2 = Issue.generate!(:project => project)
1911 childIssue2_1 = Issue.generate!(:project => project, :parent_issue_id => parentIssue2.id)
1912
1913 independentIssue = Issue.generate!(:project => project)
1914
1915 assert IssueRelation.create(:issue_from => parentIssue1,
1916 :issue_to => independentIssue,
1917 :relation_type => IssueRelation::TYPE_RELATES)
1918
1919 assert IssueRelation.create(:issue_from => independentIssue,
1920 :issue_to => childIssue2_1,
1921 :relation_type => IssueRelation::TYPE_RELATES)
1922
1923 assert_equal [childIssue1_1.id, parentIssue2.id, childIssue2_1.id, independentIssue.id].sort,
1924 parentIssue1.all_dependent_issues.collect(&:id).uniq.sort
1925
1926 end
1927
1798 def test_all_dependent_issues_with_persistent_circular_dependency
1928 def test_all_dependent_issues_with_persistent_circular_dependency
1799 IssueRelation.delete_all
1929 IssueRelation.delete_all
1800 assert IssueRelation.create!(:issue_from => Issue.find(1),
1930 assert IssueRelation.create!(:issue_from => Issue.find(1),
General Comments 0
You need to be logged in to leave comments. Login now