Class ActionMap < Object

# File tool/transcode-tblgen.rb, line 191
def self.build_tree(rects)
  expand(rects) {|prefix, actions|
    unambiguous_action(actions)
  }
end

# File tool/transcode-tblgen.rb, line 319
def self.each_firstbyte_range(prefix, region_rects)
  index_from = TMPHASH

  region_ary = []
  region_rects.each {|min, max, action|
    raise ArgumentError, "ambiguous pattern: #{prefix}" if min.empty?
    min_firstbyte = min[0,2].to_i(16)
    min_rest = min[2..-1]
    max_firstbyte = max[0,2].to_i(16)
    max_rest = max[2..-1]
    region_ary << [min_firstbyte, max_firstbyte, [min_rest, max_rest, action]]
    index_from[min_firstbyte] = true
    index_from[max_firstbyte+1] = true
  }

  byte_from = Array.new(index_from.size)
  bytes = index_from.keys
  bytes.sort!
  bytes.reverse!
  bytes.each_with_index {|byte, i|
    index_from[byte] = i
    byte_from[i] = byte
  }

  region_rects_ary = Array.new(index_from.size) { [] }
  region_ary.each {|min_firstbyte, max_firstbyte, rest_elt|
    index_from[min_firstbyte].downto(index_from[max_firstbyte+1]+1) {|i|
      region_rects_ary[i] << rest_elt
    }
  }

  index_from.clear

  r_rects = region_rects_ary.pop
  region_byte = byte_from.pop
  prev_r_start = region_byte
  prev_r_rects = []
  while r_rects && (s_rect = @singleton_rects.last) && (seq = s_rect[0]).start_with?(prefix)
    singleton_byte = seq[prefix.length, 2].to_i(16)
    min_byte = singleton_byte < region_byte ? singleton_byte : region_byte
    if prev_r_start < min_byte && !prev_r_rects.empty?
      yield prev_r_start, min_byte-1, prev_r_rects
    end
    if region_byte < singleton_byte
      prev_r_start = region_byte
      prev_r_rects = r_rects
      r_rects = region_rects_ary.pop
      region_byte = byte_from.pop
    elsif region_byte > singleton_byte
      yield singleton_byte, singleton_byte, prev_r_rects
      prev_r_start = singleton_byte+1
    else # region_byte == singleton_byte
      prev_r_start = region_byte+1
      prev_r_rects = r_rects
      r_rects = region_rects_ary.pop
      region_byte = byte_from.pop
      yield singleton_byte, singleton_byte, prev_r_rects
    end
  end

  while r_rects
    if prev_r_start < region_byte && !prev_r_rects.empty?
      yield prev_r_start, region_byte-1, prev_r_rects
    end
    prev_r_start = region_byte
    prev_r_rects = r_rects
    r_rects = region_rects_ary.pop
    region_byte = byte_from.pop
  end

  while (s_rect = @singleton_rects.last) && (seq = s_rect[0]).start_with?(prefix)
    singleton_byte = seq[prefix.length, 2].to_i(16)
    yield singleton_byte, singleton_byte, []
  end
end

# File tool/transcode-tblgen.rb, line 267
def self.expand(rects, &block)
  #numsing = numreg = 0
  #rects.each {|min, max, action| if min == max then numsing += 1 else numreg += 1 end }
  #puts "#{numsing} singleton mappings and #{numreg} region mappings."
  singleton_rects = []
  region_rects = []
  rects.each {|rect|
    min, max, action = rect
    if min == max
      singleton_rects << rect
    else
      region_rects << rect
    end
  }
  @singleton_rects = singleton_rects.sort_by {|min, max, action| min }
  @singleton_rects.reverse!
  ret = expand_rec("", region_rects, &block)
  @singleton_rects = nil
  ret
end

# File tool/transcode-tblgen.rb, line 289
def self.expand_rec(prefix, region_rects, &block)
  return region_rects if region_rects.empty? && !((s_rect = @singleton_rects.last) && s_rect[0].start_with?(prefix))
  if region_rects.empty? ? s_rect[0].length == prefix.length : region_rects[0][0].empty?
    h = TMPHASH
    while (s_rect = @singleton_rects.last) && s_rect[0].start_with?(prefix)
      min, max, action = @singleton_rects.pop
      raise ArgumentError, "ambiguous pattern: #{prefix}" if min.length != prefix.length
      h[action] = true
    end
    region_rects.each {|min, max, action|
      raise ArgumentError, "ambiguous pattern: #{prefix}" if !min.empty?
      h[action] = true
    }
    tree = Action.new(block.call(prefix, h.keys))
    h.clear
  else
    tree = []
    each_firstbyte_range(prefix, region_rects) {|byte_min, byte_max, r_rects2|
      if byte_min == byte_max
        prefix2 = prefix + "%02X" % byte_min
      else
        prefix2 = prefix + "{%02X-%02X}" % [byte_min, byte_max]
      end
      child_tree = expand_rec(prefix2, r_rects2, &block)
      tree << Branch.new(byte_min, byte_max, child_tree)
    }
  end
  return tree
end

# File tool/transcode-tblgen.rb, line 224
def self.merge(*mappings, &block)
  merge_rects(*mappings.map {|m| parse_to_rects(m) }, &block)
end

# File tool/transcode-tblgen.rb, line 228
def self.merge2(map1, map2, &block)
  rects1 = parse_to_rects(map1)
  rects2 = parse_to_rects(map2)

  actions = []
  all_rects = []

  rects1.each {|rect|
    min, max, action = rect
    rect[2] = actions.length
    actions << action
    all_rects << rect
  }

  boundary = actions.length

  rects2.each {|rect|
    min, max, action = rect
    rect[2] = actions.length
    actions << action
    all_rects << rect
  }

  tree = expand(all_rects) {|prefix, as0|
    as1 = []
    as2 = []
    as0.each {|i|
      if i < boundary
        as1 << actions[i]
      else
        as2 << actions[i]
      end
    }
    yield(prefix, as1, as2)
  }

  self.new(tree)
end

# File tool/transcode-tblgen.rb, line 203
def self.merge_rects(*rects_list)
  if rects_list.length < 2
    raise ArgumentError, "not enough arguments"
  end

  all_rects = []
  rects_list.each_with_index {|rects, i|
    all_rects.concat rects.map {|min, max, action| [min, max, [i, action]] }
  }

  tree = expand(all_rects) {|prefix, actions|
    args = Array.new(rects_list.length) { [] }
    actions.each {|i, action|
      args[i] << action
    }
    yield(prefix, *args)
  }

  self.new(tree)
end

# File tool/transcode-tblgen.rb, line 395
def initialize(tree)
  @tree = tree
end

# File tool/transcode-tblgen.rb, line 197
def self.parse(mapping)
  rects = parse_to_rects(mapping)
  tree = build_tree(rects)
  self.new(tree)
end

# File tool/transcode-tblgen.rb, line 115
def self.parse_to_rects(mapping)
  rects = []
  n = 0
  mapping.each {|pat, action|
    pat = pat.to_s
    if /\A\s*\(empset\)\s*\z/ =~ pat
      next
    elsif /\A\s*\(empstr\)\s*\z/ =~ pat
      rects << ['', '', action]
      n += 1
    elsif /\A\s*(#{HEX2}+)\s*\z/o =~ pat
      hex = $1.upcase
      rects << [hex, hex, action]
    elsif /\A\s*((#{HEX2}|\{#{HEX2}(?:-#{HEX2})?(,#{HEX2}(?:-#{HEX2})?)*\})+(\s+|\z))*\z/o =~ pat
      pat = pat.upcase
      pat.scan(/\S+/) {
        pat1 = $&
        ranges_list = []
        pat1.scan(/#{HEX2}|\{([^\}]*)\}/o) {
          ranges_list << []
          if !$1
            ranges_list.last << [$&,$&]
          else
            set = {}
            $1.scan(/(#{HEX2})(?:-(#{HEX2}))?/o) {
              if !$2
                c = $1.to_i(16)
                set[c] = true
              else
                b = $1.to_i(16)
                e = $2.to_i(16)
                b.upto(e) {|c| set[c] = true }
              end
            }
            i = nil
            0.upto(256) {|j|
              if set[j]
                if !i
                  i = j
                end
                if !set[j+1]
                  ranges_list.last << ["%02X" % i, "%02X" % j]
                  i = nil
                end
              end
            }
          end
        }
        first_ranges = ranges_list.shift
        first_ranges.product(*ranges_list).each {|range_list|
          min = range_list.map {|x, y| x }.join
          max = range_list.map {|x, y| y }.join
          rects << [min, max, action]
        }
      }
    else
      raise ArgumentError, "invalid pattern: #{pat.inspect}"
    end
  }
  rects
end

# File tool/transcode-tblgen.rb, line 177
def self.unambiguous_action(actions0)
  actions = actions0.uniq
  if actions.length == 1
    actions[0]
  else
    actions.delete(:nomap0)
    if actions.length == 1
      actions[0]
    else
      raise ArgumentError, "ambiguous actions: #{actions0.inspect}"
    end
  end
end

# File tool/transcode-tblgen.rb, line 420
def empty_action
  if @tree.kind_of? Action
    @tree.value
  else
    nil
  end
end

# File tool/transcode-tblgen.rb, line 516
def format_infos(infos)
  infos = infos.map {|info| generate_info(info) }
  maxlen = infos.map {|info| info.length }.max
  columns = maxlen <= 16 ? 4 : 2
  code = ""
  0.step(infos.length-1, columns) {|i|
    code << "    "
    is = infos[i,columns]
    is.each {|info|
      code << sprintf(" %#{maxlen}s,", info)
    }
    code << "\n"
  }
  code
end

# File tool/transcode-tblgen.rb, line 431
def format_offsets(min, max, offsets)
  offsets = offsets[min..max]
  code = "%d, %d,\n" % [min, max]
  0.step(offsets.length-1,16) {|i|
    code << "    "
    code << offsets[i,8].map {|off| "%3d," % off.to_s }.join('')
    if i+8 < offsets.length
      code << "  "
      code << offsets[i+8,8].map {|off| "%3d," % off.to_s }.join('')
    end
    code << "\n"
  }
  code
end

# File tool/transcode-tblgen.rb, line 464
def gen_str(bytes)
  if n = StrMemo[bytes]
    n
  else
    len = bytes.length/2
    size = @bytes_code.length
    n = str_name(bytes)
    @bytes_code.insert_at_last(1 + len,
      "\#define #{n} makeSTR1(#{size})\n" +
      "    makeSTR1LEN(#{len})," + bytes.gsub(/../, ' 0x\&,') + "\n\n")
    n
  end
end

# File tool/transcode-tblgen.rb, line 478
def generate_info(info)
  case info
  when :nomap, :nomap0
    # :nomap0 is low priority.  it never collides.
    "NOMAP"
  when :undef
    "UNDEF"
  when :invalid
    "INVALID"
  when :func_ii
    "FUNii"
  when :func_si
    "FUNsi"
  when :func_io
    "FUNio"
  when :func_so
    "FUNso"
  when /\A(#{HEX2})\z/o
    "o1(0x#$1)"
  when /\A(#{HEX2})(#{HEX2})\z/o
    "o2(0x#$1,0x#$2)"
  when /\A(#{HEX2})(#{HEX2})(#{HEX2})\z/o
    "o3(0x#$1,0x#$2,0x#$3)"
  when /funsio\((\d+)\)/
    "funsio(#{$1})"
  when /\A(#{HEX2})(3[0-9])(#{HEX2})(3[0-9])\z/o
    "g4(0x#$1,0x#$2,0x#$3,0x#$4)"
  when /\A(f[0-7])(#{HEX2})(#{HEX2})(#{HEX2})\z/o
    "o4(0x#$1,0x#$2,0x#$3,0x#$4)"
  when /\A(#{HEX2}){4,259}\z/o
    gen_str(info.upcase)
  when /\A\/\*BYTE_LOOKUP\*\// # pointer to BYTE_LOOKUP structure
    $'.to_s
  else
    raise "unexpected action: #{info.inspect}"
  end
end

# File tool/transcode-tblgen.rb, line 532
  def generate_lookup_node(name, table)
    bytes_code = @bytes_code
    words_code = @words_code
    offsets = []
    infos = []
    infomap = {}
    min = max = nil
    table.each_with_index {|action, byte|
      action ||= :invalid
      if action != :invalid
        min = byte if !min
        max = byte
      end
      unless o = infomap[action]
        infomap[action] = o = infos.length
        infos[o] = action
      end
      offsets[byte] = o
    }
    infomap.clear
    if !min
      min = max = 0
    end

    offsets_key = [min, max, offsets[min..max]]
    if n = OffsetsMemo[offsets_key]
      offsets_name = n
    else
      offsets_name = "#{name}_offsets"
      OffsetsMemo[offsets_key] = offsets_name
      size = bytes_code.length
      bytes_code.insert_at_last(2+max-min+1,
        "\#define #{offsets_name} #{size}\n" +
        format_offsets(min,max,offsets) + "\n")
    end

    if n = InfosMemo[infos]
      infos_name = n
    else
      infos_name = "#{name}_infos"
      InfosMemo[infos] = infos_name

      size = words_code.length
      words_code.insert_at_last(infos.length,
        "\#define #{infos_name} WORDINDEX2INFO(#{size})\n" +
        format_infos(infos) + "\n")
    end

    size = words_code.length
    words_code.insert_at_last(NUM_ELEM_BYTELOOKUP,
      "\#define #{name} WORDINDEX2INFO(#{size})\n" +
      "    #{offsets_name},
    #{infos_name},
" + "\n")
  end

# File tool/transcode-tblgen.rb, line 592
def generate_node(name_hint=nil)
  if n = PreMemo[@tree]
    return n
  end

  table = Array.new(0x100, :invalid)
  @tree.each {|branch|
    byte_min, byte_max, child_tree = branch.byte_min, branch.byte_max, branch.child_tree
    rest = ActionMap.new(child_tree)
    if a = rest.empty_action
      table.fill(a, byte_min..byte_max)
    else
      name_hint2 = nil
      if name_hint
        name_hint2 = "#{name_hint}_#{byte_min == byte_max ? '%02X' % byte_min : '%02Xto%02X' % [byte_min, byte_max]}"
      end
      v = "/*BYTE_LOOKUP*/" + rest.gennode(@bytes_code, @words_code, name_hint2)
      table.fill(v, byte_min..byte_max)
    end
  }

  if !name_hint
    name_hint = "fun_" + NextName
    NextName.succ!
  end

  PreMemo[@tree] = name_hint

  generate_lookup_node(name_hint, table)
  name_hint
end

# File tool/transcode-tblgen.rb, line 624
def gennode(bytes_code, words_code, name_hint=nil)
  @bytes_code = bytes_code
  @words_code = words_code
  name = generate_node(name_hint)
  @bytes_code = nil
  @words_code = nil
  return name
end

# File tool/transcode-tblgen.rb, line 399
def inspect
  "\#<#{self.class}:" +
  @tree.inspect +
  ">"
end

# File tool/transcode-tblgen.rb, line 416
def max_input_length
  max_input_length_rec(@tree)
end

# File tool/transcode-tblgen.rb, line 405
def max_input_length_rec(tree)
  case tree
  when Action
    0
  else
    tree.map {|branch|
      max_input_length_rec(branch.child_tree)
    }.max + 1
  end
end

# File tool/transcode-tblgen.rb, line 450
def str_name(bytes)
  size = @bytes_code.length
  rawbytes = [bytes].pack("H*")

  n = nil
  if !n && !(suf = rawbytes.gsub(/[^A-Za-z0-9_]/, '')).empty? && !UsedName[nn = "str1_" + suf] then n = nn end
  if !n && !UsedName[nn = "str1_" + bytes] then n = nn end
  n ||= "str1s_#{size}"

  StrMemo[bytes] = n
  UsedName[n] = true
  n
end