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