Class: Gitlab::Utils::TraversalIdCompactor

Inherits:
Object
  • Object
show all
Defined in:
lib/gitlab/utils/traversal_id_compactor.rb

Constant Summary collapse

CompactionLimitCannotBeAchievedError = 
Class.new(StandardError)
RedundantCompactionEntry = 
Class.new(StandardError)
UnexpectedCompactionEntry = 
Class.new(StandardError)

Class Method Summary collapse

Class Method Details

.compact(traversal_ids, limit) ⇒ Object

The compact method calls the compact_once method until the size of the final array is less than the limit. It then returns the compacted list of traversal_ids If it cannot achieve the limit it raises a CompactionLimitCannotBeAchievedError.



36
37
38
39
40
41
 
# File 'lib/gitlab/utils/traversal_id_compactor.rb', line 36

def compact(traversal_ids, limit)
  traversal_ids = traversal_ids.sort_by { |arr| [-arr.length, arr] }
  traversal_ids = compact_once(traversal_ids) while traversal_ids.size > limit

  traversal_ids
end

.compact_once(traversal_ids) ⇒ Object

The compact_once method finds the most common namespace and compacts all children into an entry for that namespace. It then returns the compacted list of traversal_ids.



46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/gitlab/utils/traversal_id_compactor.rb', line 46

def compact_once(traversal_ids)
  most_common_namespace_path = find_most_common_namespace_path(traversal_ids)

  compacted_traversal_ids = traversal_ids.map do |traversal_id|
    if starts_with?(traversal_id, most_common_namespace_path)
      most_common_namespace_path
    else
      traversal_id
    end
  end

  compacted_traversal_ids.uniq
end

.validate!(origin_project_traversal_ids, compacted_traversal_ids) ⇒ Object

The validate method performs two checks on the compacted_traversal_ids

1. If there are redundant traversal_ids, for example [1,2,3,4] and [1,2,3]
2. If there are unexpected entries, meaning a traversal_id not present in the origin_project_traversal_ids

If either case is found, it will raise an error Otherwise, it will return true



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/gitlab/utils/traversal_id_compactor.rb', line 66

def validate!(origin_project_traversal_ids, compacted_traversal_ids)
  compacted_traversal_ids.each do |compacted_path|
    # Fail if there are unexpected entries
    raise UnexpectedCompactionEntry unless origin_project_traversal_ids.find do |original_path|
      starts_with?(original_path, compacted_path)
    end

    # Fail if there are redundant entries
    compacted_traversal_ids.each do |inner_compacted_path|
      next if inner_compacted_path == compacted_path

      raise RedundantCompactionEntry if starts_with?(inner_compacted_path, compacted_path)
    end
  end

  true
end