1 files changed, 27 insertions, 0 deletions
diff --git a/app/models/namespaces/traversal/linear.rb b/app/models/namespaces/traversal/linear.rb
index 1963745cf4d..6320e0bc39d 100644
--- a/app/models/namespaces/traversal/linear.rb
+++ b/app/models/namespaces/traversal/linear.rb
@@ -49,6 +49,33 @@ module Namespaces
         before_commit :sync_traversal_ids, on: [:create], if: -> { sync_traversal_ids? }
       end
 
+      class_methods do
+        # This method looks into a list of namespaces trying to optimise a returned traversal_ids
+        # into a list of shortest prefixes, due to fact that the shortest prefixes include all childrens.
+        # Example:
+        # INPUT: [[4909902], [4909902,51065789], [4909902,51065793], [7135830], [15599674, 1], [15599674, 1, 3], [15599674, 2]]
+        # RESULT: [[4909902], [7135830], [15599674, 1], [15599674, 2]]
+        def shortest_traversal_ids_prefixes
+          raise ArgumentError, 'Feature not supported since the `:use_traversal_ids` is disabled' unless use_traversal_ids?
+
+          prefixes = []
+
+          # The array needs to be sorted (O(nlogn)) to ensure shortest elements are always first
+          # This allows to do O(n) search of shortest prefixes
+          all_traversal_ids = all.order('namespaces.traversal_ids').pluck('namespaces.traversal_ids')
+          last_prefix = [nil]
+
+          all_traversal_ids.each do |traversal_ids|
+            next if last_prefix == traversal_ids[0..(last_prefix.count - 1)]
+
+            last_prefix = traversal_ids
+            prefixes << traversal_ids
+          end
+
+          prefixes
+        end
+      end
+
       def sync_traversal_ids?
         Feature.enabled?(:sync_traversal_ids, root_ancestor, default_enabled: :yaml)
       end