ip_addr_regexp_to_subnet.rb

#!/usr/bin/env ruby

require "json"
require "ipaddress"

patterns = [
  "10\\.([0-9]|[1-9][0-9]|1([0-9][0-9])|2([0-4][0-9]|5[0-5]))\\.([0-9]|[1-9][0-9]|1([0-9][0-9])|2([0-4][0-9]|5[0-5]))\\.([0-9]|[1-9][0-9]|1([0-9][0-9])|2([0-4][0-9]|5[0-5]))",
  "172\\.(1[6-9]|2[0-9]|3[0-1])\\.([0-9]|[1-9][0-9]|1([0-9][0-9])|2([0-4][0-9]|5[0-5]))\\.([0-9]|[1-9][0-9]|1([0-9][0-9])|2([0-4][0-9]|5[0-5]))",
  "192\\.168\\.([0-9]|[1-9][0-9]|1([0-9][0-9])|2([0-4][0-9]|5[0-5]))\\.([0-9]|[1-9][0-9]|1([0-9][0-9])|2([0-4][0-9]|5[0-5]))",
]

paren_re = /(?<paren>\((?<inner_paren>[^()]*\g<paren>*[^()]*)\))/

balance_paren_re = /\A[^()]*(?<paren>\([^()]*\g<paren>*[^()]*\))*[^()]*\z/

queue_case_flattening = [] # patterns including cases ("|") and range ("[a-b]")
queue_range_flattening = [] # patterns including range ("[a-b]")

patterns.each {|x| queue_case_flattening.push(x) }
# queue_case_flattening.push(patterns[0])

until queue_case_flattening.empty?
  to_flatten = queue_case_flattening.pop

  unless paren_re === to_flatten
    queue_range_flattening << to_flatten
    next
  end

  md = to_flatten.gsub(paren_re) {|x| x.include?("|") ? x : x }.match(paren_re)

  md[:inner_paren].
    split("|").
    inject([]) do |res, case_str|
      if res.empty? || balance_paren_re === res.last
        res << case_str
      else
        res[-1] += "|" + case_str
      end

      res
    end.
    each do |case_str|
      queue_case_flattening.push(md.pre_match + case_str + md.post_match)
    end
end

# naive

# range_re = /\[(?<begin>\d)-(?<end>\d)\]/

# until queue_range_flattening.empty?
#   to_flatten = queue_range_flattening.pop

#   unless range_re === to_flatten
#     p IPAddress(to_flatten)
#     addresses << IPAddress(to_flatten)
#     next
#   end

#   md = to_flatten.match(range_re)

#   range = (md[:begin].to_i)..(md[:end].to_i)

#   range.each do |x|
#     queue_range_flattening.push(md.pre_match + x.to_s + md.post_match)
#   end
# end

# "[0-1][2-3]" => [[0, 1], [2, 3]]
def parse_regexp_ranges(re_str)
  raise unless re_str.is_a? String

  re = /\[(\d)-(\d)\]|(\d)/
  ret = []

  re_str.scan(re).each do |matched|
    raise unless (!matched[2].nil?) || (!matched[0].nil? && !matched[1].nil?)

    unless matched[2].nil?
      # a digit in [2]
      ret << matched[2].to_i
    else
      # a range from [0..1]
      ret << matched[0..1].map(&:to_i)
    end
  end

  ret
end


# "[0-1][2-3]" => [[0, 1], [2, 3]]
raise if parse_regexp_ranges("[0-1][2-3]") != [[0, 1], [2, 3]]


# [[0, 2], [0, 9]] => [[[0, 2], [0, 9]]]
# [[0, 2], [0, 8]] => [[0, [0, 8]], [1, [0, 8]], [2, [0, 8]]]
# [[0, 1], [1, 2], [0, 3]] => [[0, 1, [0, 3]], [0, 2, [0, 3]], [1, 1, [0, 3]], [1, 2, [0, 3]]]
def divide_ranges(ranges)
  ret = []
  *rest_ranges, range = ranges

  tail_zero_to_nine_count = 0

  # pop [0, 9] from tail as many as possible
  while range == [0, 9]
    tail_zero_to_nine_count += 1

    *rest_ranges, range = rest_ranges
  end

  ret = [[[0, 9]] * tail_zero_to_nine_count]

  ret = [[range] + ret[0]] unless range.nil?

  # p ret

  until rest_ranges.empty?
    *rest_ranges, (min, max) = rest_ranges
    max = min if max.nil?
    ret = (min..max).map do |x|
      ret.map {|r| [x] + r }
    end.flatten(1)
  end

  ret
end

raise "#{divide_ranges([[0, 2], [0, 9]])} != [[[0, 2], [0, 9]]]" if divide_ranges([[0, 2], [0, 9]]) != [[[0, 2], [0, 9]]]
raise "#{divide_ranges([[0, 2], [0, 8]])} != [[0, [0, 8]], [1, [0, 8]], [2, [0, 8]]]" if divide_ranges([[0, 2], [0, 8]]) != [[0, [0, 8]], [1, [0, 8]], [2, [0, 8]]]
raise "#{divide_ranges([[0, 1], [1, 2], [0, 3]])} != [[0, 1, [0, 3]], [0, 2, [0, 3]], [1, 1, [0, 3]], [1, 2, [0, 3]]]" if divide_ranges([[0, 1], [1, 2], [0, 3]]) != [[0, 1, [0, 3]], [0, 2, [0, 3]], [1, 1, [0, 3]], [1, 2, [0, 3]]]

# [[0, 4], [0, 9]] => [0, 49]
# [3, [0, 9]] => [30, 39]
def minmax_from_range(ranges)
  raise ranges.inspect unless ranges.is_a? Array

  *rest_ranges, range = ranges

  raise "passed not single ranges" if range != [0, 9] && !rest_ranges.all?{|x| x.is_a? Integer }

  min_ret, max_ret = range
  max_ret = min_ret if max_ret.nil? # passed range of a single number

  base = 10
  until rest_ranges.empty?
    *rest_ranges, (min, max) = rest_ranges
    max = min if max.nil?

    min_ret += min * base
    max_ret += max * base
    base *= 10
  end

  [min_ret, max_ret]
end

raise "#{minmax_from_range([[0, 4], [0, 9]])} != [0, 49]" if minmax_from_range([[0, 4], [0, 9]]) != [0, 49]
raise "#{minmax_from_range([3, [0, 9]])} != [30, 39]" if minmax_from_range([3, [0, 9]]) != [30, 39]

queue_range_flattening = queue_range_flattening.map do |re_str|
  octets = re_str.split(".")

  # loop-able if rest octet's range is 0..255
  octets.map do |octet|
    ranges = octet.
      yield_self{|x| parse_regexp_ranges(x) }.
      yield_self{|rs| divide_ranges(rs) }.
      map {|r| minmax_from_range(r) }

    raise NotImplementedError if ranges.count != 1

    ranges.first
  end
end

# checks if the merging two ranges might make possible one network address
# [[10, 10], [1, 1], [1, 1], [0, 9]], [[10, 10], [1, 1], [1, 1], [10, 99]] => true
# [[10, 10], [1, 1], [1, 1], [200, 249]], [[10, 10], [1, 1], [1, 1], [250, 255]] => true
# [[1, 1], [1, 1], [1, 1], [0, 255]], [[1, 1], [1, 1], [2, 2], [0, 255]] => true
# below one is mergeable but not make one network address (1.1.1.1/24 + 1.1.1.2/25 can't merge one network address)
# [[1, 1], [1, 1], [1, 1], [0, 255]], [[1, 1], [1, 1], [2, 2], [0, 128]] => false
def range_mergeable?(a, b)
  raise unless (a.is_a?(Array) && b.is_a?(Array) && a.size == b.size)

  return true if a == b

  *a_head, a_tail = a
  *b_head, b_tail = b
  # p a_head: a_head, a_tail: a_tail, b_head: b_head, b_tail: b_tail

  if a_tail == b_tail
    if a_tail == [0, 255]
      range_mergeable?(a_head, b_head)
    else
      a_head == b_head
    end
  else
    a_head == b_head && ((a_tail[1] + 1) == b_tail[0] || (b_tail[1] + 1) == a_tail[0])
  end
end

raise if range_mergeable?([[10, 10], [1, 1], [1, 1], [0, 9]], [[10, 10], [1, 1], [1, 1], [10, 99]]) != true
raise if range_mergeable?([[10, 10], [1, 1], [1, 1], [200, 249]], [[10, 10], [1, 1], [1, 1], [250, 255]]) != true
raise if range_mergeable?([[1, 1], [1, 1], [1, 1], [0, 255]], [[1, 1], [1, 1], [2, 2], [0, 255]]) != true
raise if range_mergeable?([[1, 1], [1, 1], [1, 1], [0, 255]], [[1, 1], [1, 1], [2, 2], [0, 128]]) != false


# [[10, 10], [1, 1], [1, 1], [0, 9]], [[10, 10], [1, 1], [1, 1], [10, 99]] => [[10, 10], [1, 1], [1, 1], [0, 99]]
# [[10, 10], [1, 1], [1, 1], [200, 249]], [[10, 10], [1, 1], [1, 1], [250, 255]] => [[10, 10], [1, 1], [1, 1], [200, 255]]
# [[1, 1], [1, 1], [1, 1], [0, 255]], [[1, 1], [1, 1], [2, 2], [0, 255]] => [[1, 1], [1, 1], [1, 2], [0, 255]]
def merge_range(a, b)
  raise unless (a.is_a?(Array) && b.is_a?(Array) && a.size == b.size)
  raise unless range_mergeable?(a, b)

  return a if a == b

  a_head, *a_rest = a
  b_head, *b_rest = b
  # p a_head: a_head, a_rest: a_rest, b_head: b_head, b_rest: b_rest

  if a_head == b_head
    [a_head] + merge_range(a_rest, b_rest)
  else
    raise "a_head: #{a_head}, a_rest: #{a_rest}, b_head: #{b_head}, b_rest: #{b_rest}" if a_rest.uniq != b_rest.uniq || !(a_rest.uniq == [[0, 255]] || a_rest.uniq == [])

    [[*a_head, *b_head].minmax] + a_rest
  end
end

raise "#{merge_range([[10, 10], [1, 1], [1, 1], [0, 9]], [[10, 10], [1, 1], [1, 1], [10, 99]])} != [[10, 10], [1, 1], [1, 1], [0, 99]]" if merge_range([[10, 10], [1, 1], [1, 1], [0, 9]], [[10, 10], [1, 1], [1, 1], [10, 99]]) != [[10, 10], [1, 1], [1, 1], [0, 99]]
raise "#{merge_range([[10, 10], [1, 1], [1, 1], [200, 249]], [[10, 10], [1, 1], [1, 1], [250, 255]])} != [[10, 10], [1, 1], [1, 1], [200, 255]]" if merge_range([[10, 10], [1, 1], [1, 1], [200, 249]], [[10, 10], [1, 1], [1, 1], [250, 255]]) != [[10, 10], [1, 1], [1, 1], [200, 255]]
raise "#{merge_range([[1, 1], [1, 1], [1, 1], [0, 255]], [[1, 1], [1, 1], [2, 2], [0, 255]])} != [[1, 1], [1, 1], [1, 2], [0, 255]]" if merge_range([[1, 1], [1, 1], [1, 1], [0, 255]], [[1, 1], [1, 1], [2, 2], [0, 255]]) != [[1, 1], [1, 1], [1, 2], [0, 255]]

# range_re = /(\[(?<begin>\d)-(?<end>\d)\])+/

5.times do
  middle_result = []
  until queue_range_flattening.empty?
    to_flatten = queue_range_flattening.pop

    rest_to_flatten = queue_range_flattening.pop

    # p before_merge: to_flatten

    while rest_to_flatten && range_mergeable?(to_flatten, rest_to_flatten)
      to_flatten = merge_range(to_flatten, rest_to_flatten)
      rest_to_flatten = queue_range_flattening.pop
    end

    queue_range_flattening.push(rest_to_flatten) if rest_to_flatten

    # p after_meger: to_flatten
    middle_result << to_flatten
  end

  # puts "---"
  queue_range_flattening = middle_result
end


addresses = [] # flattened ip addresses array

until queue_range_flattening.empty?
  to_flatten = queue_range_flattening.pop

  addr_tail = ""
  prefix_len = 32
  octet_range = to_flatten.pop

  while !to_flatten.empty? && octet_range == [0, 255]
    addr_tail += ".0"
    prefix_len -= 8

    octet_range = to_flatten.pop
  end

  raise unless to_flatten.all?{|x| x.size == 2 && x[0] == x[1] }

  ((octet_range.first)..(octet_range.last)).each do |octet|
    addr_head = to_flatten.map(&:first).join(".")
    addr_head += "." unless addr_head.empty?
    addresses << IPAddress("#{addr_head}#{octet}#{addr_tail}/#{prefix_len}")
  end
end

puts addresses.map(&:to_string)

puts "-- summarize --"

puts IPAddress::IPv4::summarize(*addresses).map(&:to_string)

# 192.168.0.0/16
# 172.16.0.0/16
# 172.17.0.0/16
# 172.18.0.0/16
# 172.19.0.0/16
# 172.20.0.0/16
# 172.21.0.0/16
# 172.22.0.0/16
# 172.23.0.0/16
# 172.24.0.0/16
# 172.25.0.0/16
# 172.26.0.0/16
# 172.27.0.0/16
# 172.28.0.0/16
# 172.29.0.0/16
# 172.30.0.0/16
# 172.31.0.0/16
# 10.0.0.0/8
# -- summarize --
# 10.0.0.0/8
# 172.16.0.0/12
# 192.168.0.0/16