module Gitlab module Triage module ExpandCondition module Sequence module Expansion PATTERN = /\{(\d+)\.\.(\d+)\}/ # This method will take a list of strings, which contains the # sequence pattern, and expand them into each possible matches. # For example, suppose the input is: # # * a:{0..1} # * b:{2..3} # * c # # The result would be: # # * * a:0 # * b:2 # * c # * * a:0 # * b:3 # * c # * * a:1 # * b:2 # * c # * * a:1 # * b:3 # * c # # We get this by picking the 1st number from the 1st string, # which is 0 from "a:{0..1}", and the 1st number from the # 2nd string, which is 2 from "b:{2..3}", and since the 3rd # string is just a fixed string, we just pick it. # # This way we have the first possible match, that is: # # * a:0 # * b:2 # * c # # Then we repeat the process by picking the next number for the # next possible match, starting from the least significant # string, which is c, but there's nothing more to pick. Then we # go to the next one, which will be the 2nd string: "b:{2..3}", # and we pick the 2nd number for it: 3. Since we have a new pick, # we have a new possible match: # # * a:0 # * b:3 # * c # # Again we repeat the process, and 2nd string doesn't have more # choices therefore we need to go to the 1st string now. When # this happens, we'll need to reset the picks from the previous # string, thus 2nd string will go back to 2. The next number for # the 1st string is 1, and then we form the new match: # # * a:1 # * b:2 # * c # # The next step will be the last match by picking the next number # from the 2nd string again: 3, and we get: # # * a:1 # * b:3 # * c # # The method will stop here because it had walked through all the # possible combinations. The total number of results is the product # of numbers of sequences. # # Note that a string can contain multiple sequences, and it will # also walk through them one by one. For example, given: # # * a:{0..1}:{2..3} # * c # # We'll get: # # * * a:0:2 # * c # * * a:0:3 # * c # * * a:1:2 # * c # * * a:1:3 # * c def self.perform(strings) expanded_strings = strings.map(&method(:expand_sequences)) product_of_all(expanded_strings) end # This method returns the product of list of lists. For example, # giving it [%w[a:0 a:1], %w[b:2 b:3], %w[c]] will return: # # [%w[a:0 b:2 c], %w[a:0 b:3 c], %w[a:1 b:2 c], %w[a:1 b:3 c]] def self.product_of_all(expanded_strings) expanded_strings.first.product(*expanded_strings.drop(1)) end # This method expands the string from the sequences. For example, # giving it "a:{0..1}:{2..3}" will return: # # %w[ # a:0:2 # a:0:3 # a:1:2 # a:1:3 # ] def self.expand_sequences(string) expand(string, scan_sequences(string)) end # This method extracts the sequences from the string. For example, # giving it "a:{0..1}:{2..3}" will return: # # [0..1, 2..3] def self.scan_sequences(string) string.scan(PATTERN).map do |(lower, upper)| Integer(lower)..Integer(upper) end end # This recursive method does the heavy lifting. It substitutes the # sequence patterns in a string with a picked number from the # sequence, and collect all the results. Here's an example: # # expand("a:{0..1}:{2..3}", [0..1, 2..3]) # # This means that we want to pick the numbers from the sequences, # and fill them back to the string containing the pattern in the # respective order. We don't care which pattern it is because # the order should have spoken for it. The result will be: # # %w[ # a:0:2 # a:0:3 # a:1:2 # a:1:3 # ] # # We start by picking the first sequence, which is 0..1 here. We # want all the possible picks, thus we flat_map on it, substituting # the first pattern with the picked number. This means we get: # # "a:0:{2..3}" # # For the first iteration. Before we jump to the next pick from the # sequence, we recursively do this again on the current string, # which only has one sequence pattern left. It will be called like: # # expand("a:0:{2..3}", [2..3]) # # Because we also dropped the first sequence we have already used. # On the next recursive call, we don't have any sequences left, # therefore we just return the current string: "a:0:2". # # Flattening the recursion, it might look like this: # # (0..1).flat_map do |x| # (2..3).flat_map do |y| # "a:{0..1}:{2..3}".sub(PATTERN, x.to_s).sub(PATTERN, y.to_s) # end # end # # So here we could clearly see that we go deep first, substituting # the least significant pattern first, and then go back to the # previous one, until there's nothing more to pick. def self.expand(string, sequences) if sequences.empty? [string] else remainings = sequences.drop(1) sequences.first.flat_map do |number| expand(string.sub(PATTERN, number.to_s), remainings) end end end end end end end end