#!/usr/bin/env ruby
# Copyright (c) 2024 Darren Smith. All rights reserved.
# 
# BSD 3 License
# 
# Redistribution and use in source and binary forms are permitted provided that
# the above copyright notice and this paragraph are duplicated in all such forms
# and that any documentation, advertising materials, and other materials related
# to such distribution and use acknowledge that the software was developed by
# Darren Smith. The name of Darren Smith may not be used to endorse or promote
# products derived from this software without specific prior written permission.
# THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
# WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

# lex.rb #######################################################################
class Token < Struct.new(
  :str, :type, :char_no, :line_no,
  :surrounded_by_whitespace, # for split ids warning
  :sets_var, # for drawing AST
  :data_impl, # proc that returns data value for data tokens
  :matching_bracket,
  :duped_value, # for dup tokens it points to virtual corresponding token,
                 # for that virtual token, it points to AST node position
  :implicit_used)
  def split
    trailing_commas = str[/,*$/]
    str_base = $`
    c = char_no
    results = str_base.scan(/[^1-9]|[0-9]+/).map{|s|
      t = Token.new(s, s=~/[0-9]/ ? :int : :id, c, line_no)
      c += s.size
      t
    }
    if !trailing_commas.empty?
      if results[-1].str =~ /[a-zA-Z]/
        results[-1].str += trailing_commas
      else
        results << Token.new(trailing_commas, :commas, c, line_no)
      end
    end

    results
  end
end
AllSymbols='@!?`~#%^&*-_=+[]|;<>.,()\'"{}$/\\:'.chars.map{|c|Regexp.escape c}

TokenTypes = {
  :comment => /# .*|#\n/, # also match #\n since many editors remove trailing spaces on save
  :int => /0|[0-9]+/,
  :char => /'(\\n|\\0|\\x[0-9a-fA-F][0-9a-fA-F]|[\0-\x7F])?/m,
  :str => /"(\\.|[^"])*("b?)?/m,
  :space => /[ \t]/,
  :newline => /\r\n|\r|\n/,
  :id => /[^#{AllSymbols.join} \t\n\r0-9][^#{AllSymbols.join} \t\n\r]*,*/,
  :commas => /,+/,
  :sym => /.,*/,
}
NewlineRx = TokenTypes[:newline]

def lex(code, line_no=1)
	tokens = []
  char_no = 1
  prev = ""

  # only convert to utf8 as needed since there could be invalid uf8 chars inside a ""b string which would break regexes/etc.
  until code.empty?
    TokenTypes.each{|type, regex|
      if code.start_with? regex
        match = $&
        code = $'

        if match == "'" && !code.empty? # utf8 char
          char = code.dup.force_encoding(Encoding.default_external).chars[0].b
          match << char
          code[0,char.size] = ''
        end

        match.force_encoding(Encoding.default_external) unless type == :str && parse_str(match)[1] == '"b'
        begin
          match.codepoints
        rescue => e # e.g. invalid byte sequence in UTF-8
          if [:str,:char,:comment].include? type
            match = match.b
          else
            raise IogiiError.new e.message + " after token", tokens[-1]
          end
        end
        token=Token.new(match, type, char_no, line_no)
        token.surrounded_by_whitespace = [prev[-1], $'[0]].all?{|s| (s||" ") =~ /\s/ }
        line_no += match.scan(NewlineRx).size
        if match[NewlineRx]
          char_no = match.size-match.rindex(NewlineRx)
        else
          # FYI this counts tab as 1, could be misleading
          char_no += match.size
        end
        tokens << token if ![:space, :newline, :comment].include? type
        prev = match
        break
      end
    }
  end

  tokens
end

# error.rb #####################################################################
def warn(msg, from=nil)
  error_output "WARNING: ".red + to_location(from) + msg + "\n"
end

def to_location(from)
  token = case from
    when Token
      from
    when AST
      from.token
    when IR
      from.token
    when NilClass
      nil
    else
      raise "unknown location type %p " % from
    end

  if token
    "%s:%s (%s) " % [token.line_no||"?", token.char_no||"?", token.str]
  else
    ""
  end
end

class String
  def red
    "\e[31m#{self}\e[0m"
  end
end

class IogiiError < StandardError
  def initialize(message,from=nil)
    @message = message
    @from = from
  end
  def message
    "ERROR: ".red + to_location(@from) + @message
  end
end

# escape.rb ####################################################################
def inspect_char(char)
  return "'\"'" if char=='"'.ord # Don't escape this char (we would in a string)
  "'" + escape_str_char(char) + "'"
end

def escape_str_char(char)
  return "\\0" if char == "\0".ord
  return "\\n" if char == "\n".ord
  return "\\\\" if char == "\\".ord
  return "\\\"" if char == "\"".ord
  return char.to_i.chr if char >= " ".ord && char <= "~".ord # all ascii printables
  return "\\x0%s" % char.to_i.to_s(16) if char < 16 && char >= 0
  return "\\x%s" % (char%256).to_i.to_s(16) if char < 256 && char >= -2
  return "\\%d" % char
end

def parse_char(s)
  ans,offset=parse_str_char(s,0)
  raise "internal char error" if ans.size != 1 || offset != s.size
  ans[0].ord
end

def parse_str_char(s,i) # parse char in a string starting at position i
  if s[i]=="\\"
    if s.size <= i+1
      ["\\",i+1]
    elsif s[i+1] == "n"
      ["\n",i+2]
    elsif s[i+1] == "0"
      ["\0",i+2]
    elsif s[i+1] == "\\"
      ["\\",i+2]
    elsif s[i+1] == "\""
      ["\"",i+2]
    elsif s[i+1,3] =~ /x[0-9a-fA-F][0-9a-fA-F]/
      [s[i+2,2].to_i(16).chr,i+4]
    else
      ["\\",i+1]
    end
  else
    [s[i],i+1]
  end
end

def parse_str(s)
  i=1 # skip initial "
  r=""
  while i<s.size && s[i] != '"'
    c,i=parse_str_char(s,i)
    r<<c
  end
  [r, s[i..-1]]
end

# type.rb ######################################################################
# Prefixed so that they can be compared
EmptyType = :t0_empty # the type of an empty list, it can be anything
IntType = :t1_int
CharType = :t2_char
XSpec = :t3_s_x
ASpec = :t4_s_a
BSpec = :t5_s_b

def type_spec_parts(spec)
  spec.gsub("->"," ").split.map{|s|s[/[^*]+/] } # remove "*"s for quick ref low rank overloads
end

def concrete_rank(spec)
  !(spec == ASpec || spec == BSpec)
end

def concrete_type(spec)
  !(spec == ASpec || spec == BSpec || spec == XSpec)
end

def spec_rank(part)
  t = spec_type(part)
  r = part.scan(/\[|\{/).size
  concrete_rank(t) ? r : ~r
end

def spec_type(part)
  case part.tr('[]{}','')
  when "x"
    XSpec
  when "a"
    ASpec
  when "b"
    BSpec
  when "int"
    IntType
  when "char"
    CharType
  when "", "empty"
    EmptyType
  else raise "unknown arg type" % part
  end
end

def is_special_rep(part)
  part[0] == '{'
end

def type_to_str(sym)
  sym.to_s.sub(/^.*_/,'')
end

def type_and_rank_to_str(type,rank)
  r = "["*rank + type_to_str(type) + "]"*rank
  r == "[empty]" ? "[]" : r
end

def spec_matches(specs, args)
  a = same_spec(specs, args, ASpec).max
  b = same_spec(specs, args, BSpec).max
  specs = specs.map{|s| s == ASpec ? a : s == BSpec ? b : s }
  specs.zip(args).map{|s, a|
    case s
      when XSpec
        a == EmptyType ? :m1_defaults : :m0_matches
      when IntType
        case a
          when EmptyType; :m1_defaults
          when IntType; :m0_matches
          when CharType; :m4_no_match
        end
      when CharType
        case a
        when EmptyType; :m2_defaults_char
        when IntType; :m3_coerces
        when CharType; :m0_matches
        end
      when EmptyType
        :m0_matches
      else; raise s.to_s
    end
  }
end

def same_spec(specs, args, target)
  args.filter.with_index{|a,i| specs[i] == target }
end

def spec_to_ret(way, args)
  return IntType if OpsUsingZero.include?(way.name) && way.mod == 0 && args[0] == EmptyType

  if concrete_type(way.ret_type)
    way.ret_type
  else
    t = same_spec(way.arg_types, args,  way.ret_type).max || EmptyType
    way.ret_type == XSpec ? [t, IntType].max : t
  end
end

def coerce?(specs,args)
  specs.zip(args).map{|s,a|
    if s == CharType && a == IntType
      true
    else
      !concrete_type(s) && a == IntType && same_spec(specs, args, s).any?{|o| o == CharType }
    end
  }
end


# version.rb ###################################################################
Version = "1.1"

# ops.rb #######################################################################

class Op < Struct.new(:name, :parse_nargs, :block, :ways)
  def dup
    Op.new(name.dup, parse_nargs, block, ways.map(&:dup))
  end
  def dup_mod(mod)
    return self if mod <= 0
    r = dup
    r.ways.each{|w| w.mod += mod if w.can_mod? }
    r
  end
end

class Way < Struct.new(:name, :arg_ranks, :ret_rank, :arg_types, :ret_type, :mod, :vectorize, :promote, :special_reps, :impl)
  def mod_arg_ranks
    arg_ranks.map{|r| r < 0 ? ~r + mod : r }
  end
  def mod_ret_rank
    ret_rank < 0 ? ~ret_rank + mod : ret_rank
  end
  def dup
    Way.new(name, arg_ranks.dup, ret_rank, arg_types.dup, ret_type, mod, vectorize, promote, special_reps, impl)
  end
  def can_mod?
    (arg_ranks + [ret_rank]).any?{|r| r < 0 }
  end
end

def lookup_op(name)
  (0..).each{|mod|
    op = Ops[name]
    return nil if op && mod>0 && !op.ways.any?(&:vectorize)
    return op.dup_mod(mod) if op
    return nil if !name[/,$/]
    name = $`
  }
end

def new_op(name, type_sig, block: false, vectorize: true, promote: true, &impl)
  parts = type_spec_parts(type_sig)
  *arg_ranks, ret_rank = parts.map{|arg| spec_rank(arg) }
  *arg_types, ret_type = parts.map{|arg| spec_type(arg) }
  special_reps = parts[0...-1].map{|arg| is_special_rep(arg) }

  way = Way.new(name, arg_ranks, ret_rank, arg_types, ret_type, 0, vectorize, promote, special_reps, impl)
  Op.new(name, arg_ranks.size, block, [way])
end

Ops = {}
OpExamples = {}

if !defined? mk_op
  def mk_op(names, type_sig, example="", block: false, vectorize: true, promote: true, uses_zero: false, &impl)
    OpExamples[names] = example if example != ""
    names = names.split
    OpsUsingZero << names[-1] if uses_zero

    op = new_op(names[-1], type_sig, block: block, vectorize: vectorize, promote: promote, &impl)

    names.each{|name|
      if Ops[name]
        Ops[name].ways << op.ways[0]
      else
        Ops[name] = op.dup
      end
    }

    if op.ways[0].can_mod? && op.ways[0].vectorize
      mod_op = op.dup
      mod_op.ways[0].mod = 1

      names.each{|name|
        if name =~ /^[a-z]/
          name = name.sub(/^./){|first|first.upcase}
          if Ops[name]
            Ops[name].ways << mod_op.ways[0]
          else
            Ops[name] = mod_op.dup
          end
        end
      }
    end
  end

  def category(name); end
  def quickref_op(names, desc, example)
    OpExamples[names] = example if example != ""
  end
end

NotFirst = :not_first
OpsUsingZero = [] # (append to this where used)

category("numeric ops")
mk_op("+ add", "int x -> x", '1 2+ -> 3', &add=->a,b{ a.value+b.value })
mk_op("+ add", "char int -> char", "'a 1+ -> 'b'", &add)
mk_op("- sub", "x int -> x", '5 3- -> 2', &subt=->a,b{ a.value-b.value })
mk_op("* mult", "int int -> int", '2 3* -> 6'){|a, b| a.value*b.value }
mk_op("/ div", "int int -> int", '7 2/ -> 3'){|a, b| b.value == 0 ? 0 : a.value/b.value }
mk_op("% mod", "x int -> int", '7 2% -> 1'){|a, b| b.value == 0 ? 0 : a.value%b.value }
mk_op("^ pow", "int int -> int", '2 3^ -> 8'){|a, b| pow(a.value, b.value) }
mk_op("~ negate", "int -> int", '1~ -> -1'){|a| -a.value }
mk_op("( pred", "x -> x", '4( -> 3'){|a| a.value-1 }
mk_op(") succ", "x -> x", "'a) -> 'b'"){|a| a.value+1 }
mk_op("} countTo", "int -> [int]", "3} -> [1,2,3]"){|a| range(1,a.value+1) }
mk_op("{ wholes", "[int]", "{ -> [0,1,2,..."){ range_from(0) }
mk_op("_ sum", "[int] -> int", '1,2,3,4 _ -> 10', promote: false){|a| to_eager_list(a).sum }
mk_op(". prod", "[int] -> int", '1,2,3,4 . -> 24', promote: false){|a| to_eager_list(a).inject(1,&:*) }

category("char ops")
mk_op("^ charSubtraction", "char char -> int", "'b 'a ^ -> 1", &subt)
mk_op("~ read", "[char] -> int", '"23"~ -> 23'){|a| read_num(a)[0] }
mk_op("} readAll", "[char] -> [int]", '"1,2 3"} -> [1,2,3]'){|a| split_non_digits(a) }
mk_op(". ord", "char -> int", "'d. -> 100"){|a| a.value }
mk_op("., chr", "int -> char", "100., -> 'd'"){|a| a.value }
mk_op("` str", "int -> [char]", '5` -> "5"'){|a| str(a) }
mk_op("` strip", "[char] -> [char]", '" a b\n"` -> "a b"'){|a| strip(a,$at) }
mk_op("* replicate", "[char] int -> [char]", '"ab"3* -> "ababab"'){|a, b|
  concat(take(b.value,repeat(a).const).const) }
mk_op("* join", "[[char]] {[char]} -> [char]", '1,2,3 " "* -> "1 2 3"'){|a, b| join(a,b)}
mk_op("/ rightJustify", "[char] int -> [char]", '"hi" 3 / -> " hi"'){|a,b|
  append(take(b.value - len(a.value),repeat(32.const).const).const, a) }
mk_op("/ split", "[char] [char] -> [[char]]", '"a..b.c." "."/ -> ["a","b","c"]'){|a, b| s=cut(a,repeat(b).const).const; filter(s,s,nil) }
mk_op("_ words", "[char] -> [[char]]", '"ab c\n d" _ -> ["ab","c","d"]'){|a| x=promise{ group_while(a,a,CharType) }; filter(x,x,CharType) }
mk_op("% isCharClass", "char [char] -> int", '"Hello!" \'a % -> [0,1,1,1,1,0]'){|a,b| is_char_class(a,b) }

category("generic ops")
mk_op("a append", "[a] [a] -> [a]", '"ab" "cd"a -> "abcd"'){|a, b| append(a,b) }
mk_op("b backwards reverse", "[a] -> [a]", '"abc" b -> "cba"', promote: false){|a| reverse(a) }
mk_op("c cons", "[a] a -> [a]", '1,2 0c -> [0,1,2]'){|a, b| [b, a] }
mk_op("h head", "[a] -> a", '"abc"h -> \'a\'', promote: false, uses_zero: true){|a| z=zero($rank,$at); a.empty ? z : a.value[0].value }
mk_op("j just", "a -> [a]", "1j -> [1]"){|a|[a, [].const]}
mk_op("l last", "[a] -> a", '"abc"l -> \'c\'', promote: false, uses_zero: true){|a| z=zero($rank,$at); last(a, z.const) }
mk_op("n not", "a -> int", '0,1,2n -> [1,0,0]', promote: false){|a| truthy($at, a.value) ? 0 : 1 }
mk_op("o cons0 consDefault", "[a] -> [a]", '"abc"o -> " abc"', uses_zero: true){|a| [zero($rank,$at).const, a] }
mk_op("p pivot transpose", "[[a]] -> [[a]]", '"abc","def"p -> ["ad","be","cf"]', promote: false, uses_zero: true){|a| transpose(a, $at, $rank) }
mk_op("q equal", "a a -> int", "1,2,3 1q -> [1,0,0]"){|a,b| spaceship(a, b) == 0 ? 1 : 0 }
mk_op("r repeat", "a -> [a]", "1r -> [1,1,1,1,1,1..."){|a| repeat(a) }
mk_op("s size len", "[a] -> int", '"abc"s -> 3', promote: false){|a| len(a.value) }
mk_op("t tail", "[a] -> [a]", '"abc"t -> "bc"', promote: false){|a| a.empty ? [] : a.value[1].value }
mk_op("u unite concat", "[[a]] -> [a]", '"ab","cd","e"u -> "abcde"', promote: false){|a| concat(a) }
mk_op("v vet filter", "[a] [b] -> [a]", '"abcdef":2%v -> "ace"'){|a,b| filter(a,b,$bt) }
mk_op("w while takeWhile", "[a] [b] -> [a]", '"abc def":w -> "abc"'){|a,b| take_while(a,b,$bt) }
mk_op("(, min", "a a -> a", '4 5 (, -> 4'){|a,b| spaceship(a,b) <= 0 ? a.value : b.value }
mk_op("x max", "a a -> a", '"bc" "ad" x -> "bd"'){|a,b| spaceship(a,b) >= 0 ? a.value : b.value }
mk_op("y yesNo ifElse", "b a a -> a", '0 1 2 y -> 2', promote: NotFirst){|a,b,c| truthy($at, a.value) ? b.value : c.value }
mk_op("z zeroPad padDefault", "[a] -> [a]", '1,2,3 z -> [1,2,3,0,0,...', uses_zero: true){|a| padv(a, zero($rank,$at).const) }
mk_op("\\ setDiff", "[a] [a] -> [a]", '"abra" "ra"\\ -> "ba"'){|a,b| set_diff(a,b) }
mk_op("< lessThan", "a a -> int", '1,2,3 2< -> [1,0,0]'){|a,b| spaceship(a,b) == -1 ? 1 : 0 }
mk_op("& sortBy", "[a] [b] -> [a]", '"abc","d":len &, -> ["d","abc"]', promote: false){|a,b| sort_by(a,b) }
mk_op("| chunkWhen", "[a] [b] -> [[a]]", '"ab cd e":| -> ["ab ","cd ","e"]', promote: false){|a,b| chunk_while(a,b,$bt) } # promote false is for rank invariant (could actually be useful otherwise)
mk_op("@ indices", "[a] a -> [int]", '"abcdc" \'c @ -> [2,4]'){|a,b| indices(a,b) }
mk_op("? isFirst", "[a] -> [int]", '"aardvark"? -> [1,0,1,1,1,0,0,1]', promote: false){|a| isuniq(a) }
mk_op("[ init", "[a] -> [a]", '"abc" [ -> "ab"', promote: false){|a| init(a) }

category('<a href="ops.html#slicingops">slicing ops</a> (char instead of int is substring, uppercase = any)')
mk_op("d drop", "[a] int -> [a]", '"abcde" 2d -> "cde"'){|a, b| drop(b.value, a) }
mk_op("g get", "[a] int -> a", '"abcd" 2g -> \'c\'', uses_zero: true){|a, b| z=zero($rank,$at); a = drop(b.value, a); a==[] || b.value < 0 ? z : a[0].value }
mk_op("k keep take", "{a} int -> [a]", '"abcde" 2k -> "ab"'){|a, b| take(b.value, a) }
mk_op("# reshape", "[a] {int} -> [[a]]", '"abcdef" 2 # -> ["ab","cd","ef"]'){|a,b| reshape(a,b) }
mk_op("- cutAny", "[char] {[[char]]} -> [[char]]",'"a-b.c" ".","-" - -> ["a","b","c"]'){|a, b| cut_any(a,b) }
mk_op("+ scanAny", "[char] {[[char]]} -> [[char]]", '"a-b.c" ".","-" + -> ["-","."]'){|a, b| scan_any(a,b) }

category("folding ops") # (return type is type yielded)
mk_op("i iterate", "a -> [a]", '0 i 1,2,3+ -> [0,1,3,6]', block: true)
mk_op("e expand iterate0", "[a]", 'e 1,2,3+ -> [1,3,6]', block: true)
mk_op("f foldr", "a -> [a]", '0 f 1,2,3+ -> 6', block: true)
mk_op("m meld foldr0", "[a]", 'm 1,2,3+ -> 6', block: true)

category('<a href="syntax.html#otherwaystousevaluesmultipletimes">stack ops</a> (fns do match >)')
mk_op(": dup", "a -> a", "5: -> 5 5", vectorize: false)
mk_op("; mdup", "a -> a", "5;1- -> 4 5", block: true, vectorize: false)
mk_op("] peek", "a b -> b", "5 4 ] -> 5 4 5", vectorize: false)
mk_op("! mpeek", "a b -> b", "5 4 ! 1+ -> 6 4 5", block: true, vectorize: false)

category("special symbols")
quickref_op("$", "arg", "5;$+ -> 10 5")
quickref_op(">", '<a href="syntax.html#codeclassinlinegtcodematching">end loop</a> or set <a href="syntax.html#implicitvalues">implicit</a>', "e))> -> [2,4,6...")
quickref_op(",", '<a href="vectorization.html">unvec</a> or data format or <a href="IO.html#rawmodes">raw mode</a>', '"ab"j, -> ["ab"]')
quickref_op("=", "set next var", "5= A -> 5 5")

category('<a href="types.html#lowrankoverrides">low rank overloads</a><br> (number of *\'s = number of times you may vectorize arg before needing ",")')
mk_op("U uppercase", "char** -> char", "'a U -> 'A'"){|a| a=a.value; a>='a'.ord && a<='z'.ord ? a-32 : a }
mk_op("L lowercase", "char* -> char", "'A L -> 'a'"){|a| a=a.value; a>='A'.ord && a<='Z'.ord ? a+32 : a }
mk_op("p lines", "[char] -> [[char]]", '"ab\nc\n" p -> ["ab","c"]'){|a| lines(a) }
mk_op("P charClass", "[char]* -> [char]", '"x" P -> "abc...z"'){|a| concat(char_class(a).const) }
mk_op("P digits", "int** -> [int]", '123 P -> [1,2,3]'){|a| v=to_base(a.value,10); v.empty? ? [0.const, Null] : reverse(v.const) }
mk_op("U undigits", "[int]* -> int", '1,2,3 U -> 123', promote: false){|a| undigits(a) }
mk_op("L lenFrom0 abs", "int* -> int", '5~L -> 5'){|a| a.value.abs }
mk_op("D digitsBase toBase", "int* int -> [int]", '6 2 D -> [1,1,0]'){|a,b| reverse(to_base(a.value,b.value).const) }
mk_op("X exBase fromBase", "[int] int -> int", '1,1,0 2 X -> 6', promote: false){|a,b| from_base(a.value,b.value) }
mk_op("p bits", "int* -> [int]", "6 p -> [0,1,1]"){|a| to_base(a.value, 2) }
mk_op("B rangeFrom rangeBegin", "x* -> [x]", "2B -> [2,3,4,..."){|a| range_from(a.value) }
mk_op("T rangeTo", "x* -> [x]", "3T -> [0,1,2]"){|a| range(zero(0,$at),a.value) }
mk_op("u unsquare sqrt", "int* -> int", "9u -> 3"){|a| square_root(a.value, 2) }
mk_op("H powOf10", "int* -> int", "2H -> 100"){|a| pow(10, a.value) }
mk_op("h powOf2", "int -> int", "8h -> 256"){|a| pow(2, a.value) }

category("debugging ops")
mk_op("nil", "[a]", 'nil -> []'){ [] }
mk_op("pad", "[a] a -> [a]", '1,2 3 pad -> [1,2,3,3,3...'){|a, b| padv(a, b) }
mk_op("show", "a -> [char]", '1,2 show -> "[1,2]"', vectorize: false, &show=->a{ inspectv($at, $rank, a) })
mk_op("type", "a -> [char]", '1,2 type -> "[int]"', vectorize: false){|a| str_to_lazy_list(type_and_rank_to_str($at, $rank)) }
mk_op("version", "[char]", "version -> \"#{Version}, ruby#{RUBY_VERSION}\""){ str_to_lazy_list(Version + ", ruby#{RUBY_VERSION}") }
mk_op("del", "a -> ", '1 2 del -> 1', vectorize: false){|a| raise}
mk_op("let", "a -> ", "5 let a  a a+ -> 10", vectorize: false)
mk_op("set", "a -> a", "5 set a( a) -> 4 6", vectorize: false)
mk_op("input", "a", vectorize: false)
mk_op("implicit", "a", vectorize: false)

category("internal ops")
mk_op("$", "a", vectorize: false)
mk_op("superpad", "[a] -> [a]", promote: false){ raise }
mk_op("estr", "empty -> [char]"){|a| a.value } # empty type to str (for haskell type coercion)

mk_op("# cut splitKeepEmpties", "[char] {[char]} -> [[char]]",'"a..b.c." "."# -> ["a","","b","c",""]'){|a, b| cut(a,b) }
mk_op("d dropUntilAfterSubstring", "[char] [char] -> [char]", '"beatles" "at" d -> "les"'){|a, b|
  drop(substr_ind(a, b) + len(b.value), a) }
mk_op("k keepUntilSubstring", "[char] [char] -> [char]", '"beatles" "at" k -> "be"'){|a, b|
  take(substr_ind(a, b), a) }
mk_op("g getSubstring", "[char] [char] -> [char]", '"beatles" "at","z" g -> ["at",""]'){|a, b|
  take(len(b.value), promise{ drop(substr_ind(a, b), a) }) }
mk_op("D dropUntilAfterAnySubstring", "[char] [[char]] -> [char]", '"beatles" "z","at" D -> "les"'){|a, b|
  match_pos, match_val = *any_substr_ind(a, b)
  drop(match_pos + len(match_val.value), a) }
mk_op("K keepUntilAnySubstring", "[char] [[char]] -> [char]", '"beatles" "z","at" K -> "be"'){|a, b|
  match_pos, match_val = *any_substr_ind(a, b)
  take(match_pos, a) }
mk_op("G getAnySubstring", "[char] [[char]] -> [char]", '"beatles" "z","at" G -> "at"'){|a, b|
  match_pos, match_val = *any_substr_ind(a, b)
  take(len(match_val.value), promise{ drop(match_pos, a) }) }


category("intuitive special promotes (don't need to show them in quickref)")
mk_op("* join joinM", "[char] {[char]}-> [char]", '"123" \'a * -> "1a2a3"', promote: NotFirst){|a, b| join(map(a){|i| [i,Null] }.const,b)}

Unlines = Way.new("unlines", [2], [1], [CharType], CharType, 0, nil, nil, [false], ->a{
  concat(map(a){|e| append(e, [10.const, Null].const) }.const)
})
Unwords = Way.new("unwords", [2], [1], [CharType], CharType, 0, nil, nil, [false], ->a{
  join(a, repeat([32.const, Null].const).const)
})

# parse.rb #####################################################################

AST = Struct.new(:token, :args, :type, :impl, :label, :is_fold_op)

def split_ids(tokens, registers)
  tokens.map{|t|
    if t.type==:id && !lookup_op(t.str) && !registers[t.str]
      warn("splitting %p into chars because no op/var by that name, but it is surrounded by whitespace" % t.str, t) if t.surrounded_by_whitespace
      t.split
    else
      t
    end
  }.flatten
end

Keywords = ["set","let",">","=","del"]
def get_var_ids_set(tokens)
  names = {}
  tokens.size.times{|i|
    if tokens[i].str == "set" || tokens[i].str == "let"
      raise IogiiError.new "an id must follow `#{tokens[i].str}`", tokens[i] if !tokens[i+1] || Keywords.include?(tokens[i+1].str)
      names[tokens[i+1].str] = true
    end
  }

  nregisters = tokens.filter{|t|t.str == "="}.size
  used = [false]*26
  tokens.filter{|t|t.type == :id }.map(&:str).join.scan(/[A-Z]/){|s|
    used[s.ord-?A.ord] = true }
  starts = (1...26).filter{|i| used[i] && !used[i-1] }.unshift 0
  diffs = starts.map.with_index{|s,i| (starts[i+1]||26)-starts[i] }
  largest_diff_at = starts[diffs.index(diffs.max)]
  consec_used = used[largest_diff_at..-1].take_while{|i| i }.size
  auto_names = (0...nregisters).map{|x|
    (x + ?A.ord + largest_diff_at + [consec_used - nregisters,0].max).chr}

  auto_names.each{|s| names[s] = true }
  tokens.filter{|t|t.str == "="}.each.with_index{|t,i|
    name = auto_names[i]
    t.sets_var = name
    raise IogiiError.new"Out of letters for auto vars", t if name > ?Z
    raise IogiiError.new"Sets register '#{name}' but it is never used", t if !used[name.ord-?A.ord]
  }

  names
end

def is_datum(token)
  [:int,:char,:str].include?(token.type)
end

def parse_data(tokens, token_ind)
  i = token_ind - 1
  data_tokens = []
  prev = false
  while i < tokens.size
    if is_datum(tokens[i])
      break if prev
      if tokens.size > i+1 && tokens[i].type == :int && tokens[i+1].str[0] == "~" && tokens[i+1].str[-1] == ","
        data_tokens << tokens[i].dup
        data_tokens << tokens[i+1].dup
        data_tokens[-2].str = "-"+data_tokens[-2].str
        data_tokens[-1].str = data_tokens[-1].str[1..-1]
        data_tokens[-1].type == :commas
        i += 1
        prev = false
      else
        prev = true
        data_tokens << tokens[i]
      end
    else
      break if tokens[i].type != :commas
      prev = false
      data_tokens << tokens[i]
    end
    i += 1
  end
  tokens = data_tokens

  depth = tokens.reject{|t|is_datum(t)}.map{|t|t.str.size}.max||0
  token_type = nil
  tokens.select{|t|is_datum(t)}.each{|t|
    token_type ||= t.type
    token_type = :str if token_type != t.type
  }

  value = parse_list(tokens,depth,token_type)
  case token_type
  when :str
    type = CharType
    depth += 1
  when :char
    type = CharType
  when :int
    type = IntType
  else; raise
  end
  [new_op("data", type_and_rank_to_str(type,depth)){ value }, i]
end

def split_tokens(tokens, str)
  tokens.slice_when{|t| t.str == str }.
    map{|ts| ts.reject{|t| t.str == str } }
end

def parse_list(tokens,depth,to_type)
  if depth == 0
    raise IogiiError.new 'found ", ," invalid data format' if tokens.empty?
    parse_datum(tokens[0],to_type)
  else
    to_lazy_list(split_tokens(tokens, ","*depth).map{|ts|
      parse_list(ts, depth-1, to_type)
    })
  end
end

def parse_datum(token,to_type)
  case token.type
  when :int
    val = token.str.to_i
    to_type == :str ? str(val.const) : val
  when :str
    str,remainder = *parse_str(token.str)
    if remainder == '"b' && str.bytes.all?{|b| b < 128 }
      warn("You have used the raw byte mode on a string that does not contain any binary characters, if you wish to reverse the string instead then add a space before the `b`", token)
    end
    str_to_lazy_list(str)
  when :char
    raise IogiiError.new "empty char", token if token.str.size < 2
    x = parse_char(token.str[1..-1]).ord
    to_type == :str ? [x.const, Null] : x
  end
end

def tokenize_data(tokens, registers)
  new_tokens = []
  token_ind = 0
  loop {
    t = tokens[token_ind]
    token_ind += 1
    break if token_ind > tokens.size
    if registers[t.str] || !is_datum(t)
      new_tokens << t
    else
      orig_token_ind = token_ind
      orig_token = tokens[token_ind-1]
      data_impl, token_ind = *parse_data(tokens, token_ind)
      str = tokens[orig_token_ind-1...token_ind].map(&:str).join
      new_token = Token.new(str, :data, orig_token.char_no, orig_token.line_no)
      new_token.data_impl = data_impl
      new_tokens << new_token
    end
  }
  new_tokens
end

# todo, this is a more expensive of an operation than it needs to be
def is_ancestor(parent, child, nodes)
  return true if parent == child
  nodes[parent].args.any?{|arg| is_ancestor(arg, child, nodes) }
end

def route_to_ancestor(parent, child, nodes)
  return [parent] if parent == child
  nodes[parent].args.each{|arg|
    route = route_to_ancestor(arg, child, nodes)
    return route << parent if route
  }
  nil
end

def build_tree(tokens, registers, null_input, last_unmatched = nil)
  # it is important for each token to only be responsible for adding 1 value to the stack, that way rotating the main program can choose a break point at any point. That why adding multiple is accomplished by creating virtual tokens that are responsible for the other values.

  stack = []
  lbs = []
  loop_lbs = []
  all_lbs = []
  nodes = []
  deleted = []
  token_ind = 0
  nimplicits = 0
  t = blocks_can_close_now = nil
  original_last_unmatched = last_unmatched

  push = -> a { stack << nodes.size; nodes << a; a }
  pop = -> {
    if stack.empty?
      nimplicits += 1
      push[AST.new(t, [], :ImplicitValue)]
    end
    if nodes[stack.last].type == :ImplicitValue
      nodes[stack.last].impl = if last_unmatched
        # only set this on final pass, since one of those implicits could become input
        last_unmatched.token.implicit_used = true if original_last_unmatched
        last_unmatched.args[0]
      else
        all_lbs[-1]
      end
    end
    stack.pop
  }
  peek = -> { ans = pop[]; stack << ans; ans }
  # add a token for this so that it can be wrapped
  insert_duped = -> dup_ind,pos {
    t_dup = nodes[dup_ind].token
    if !t_dup.duped_value # (first pass doesn't have duped tokens yet)
      t_dup.duped_value = pos.map{|i|
        tokens[token_ind,0] = Token.new(i == 0 ? "duped_value" : "peek_placeholder", :"VirtualDuped#{i}")
      }
    end
    t_dup.duped_value.each{|v|v.duped_value = nodes[dup_ind] }
    blocks_can_close_now = false
  }

  loop {
    t = tokens[token_ind]
    token_ind += 1
    blocks_can_close_now = true
    if token_ind > tokens.size
      break
    elsif registers[t.str]
      push[AST.new(t, [], :VarNode)]
    elsif t.str && t.str[0] == ">"
      if t.matching_bracket
        lb = nodes.size.times.find{|node| nodes[node].token.equal?(t.matching_bracket) }
        all_lbs.delete(lb)
        push[AST.new(t, [pop[]], :MatchedEndBracket, lb)]
        nodes[lb].impl = nodes.size-1
      else
        push[last_unmatched = AST.new(t, [pop[]], :UnmatchedEndBracket)]
      end
    elsif t.str == "set" || t.str == "let"
      name = tokens[token_ind].str
      token_ind += 1
      registers[name] = peek[]
      push[AST.new(t, [pop[]], :IdentityNode, nil, "set #{name}")]
      deleted << pop[] if t.str == "let"
    elsif t.str == "del"
      deleted << pop[]
    elsif t.str == "="
      registers[t.sets_var] = peek[]
      push[AST.new(t, [pop[]], :IdentityNode, nil, "set #{t.sets_var}")]
    elsif t.type == :data
      push[AST.new(t, [], :DataNode)]
    elsif t.type == :commas
      raise IogiiError.new "commas must follow data or op that can vectorize", t
    elsif t.type == :VirtualDuped0 || t.type == :VirtualDuped1
      push[AST.new(t, [], t.type)]
    elsif t.type == :id || t.type == :sym
      op = lookup_op(t.str)
      raise IogiiError.new "unknown op", t if !op
      args = op.parse_nargs.times.map{ pop[] }.reverse
      if op.name == "dup"
        push[AST.new(t, args, :IdentityNode)]
        insert_duped[nodes.size-1,[0]]
      elsif op.name == "peek"
        push[AST.new(t, args, :IdentityNode)]
        insert_duped[nodes.size-1,[0,1]]
      elsif op.name == "$"
        if all_lbs.empty?
          if null_input.value
            push[AST.new(t, [], :ImplicitValue)]
          else
            nodes << mk_input_node
            push[AST.new(t, [], :ArgNode, nodes.size - 1)]
          end
        else
          push[AST.new(t, [], :ArgNode, all_lbs[-1])]
        end
      elsif op.name == "input"
        push[mk_input_node(t)]
      elsif op.name == "implicit"
        push[AST.new(t, [], :ImplicitValue)]
      elsif op.block
        if ['mdup', 'mpeek'].include?(op.name)
          push[AST.new(t, args, :MDupOp)]
          lbs << nodes.size - 1
          blocks_can_close_now = false
        else
          n = AST.new(t, args, :LoopOp)
          n.is_fold_op = ["foldr","foldr0"].include? op.name
          push[n]
          loop_lbs << nodes.size - 1 if !t.matching_bracket
        end
        all_lbs << nodes.size - 1
      else
        push[AST.new(t, args, :OpNode)]
      end
    else
      raise "unknown token type %p" % t.type.to_s
    end

    # implicitly close meta ops
    while blocks_can_close_now &&
        !lbs.empty? &&
        is_ancestor(peek[], lbs.last, nodes)
      lb = nodes[lb_ind = lbs.pop]
      all_lbs.delete(lb_ind)
      push[AST.new(t, [pop[]], :MatchedEndBracket, lb_ind)]
      lb.impl = nodes.size-1
      insert_duped[lb_ind,[0]] if ["mdup",";"].include?(lb.token.str)
      insert_duped[lb_ind,[0,1]] if ["mpeek","!"].include?(lb.token.str)
    end

    # implicitly close loops
    while blocks_can_close_now &&
        !loop_lbs.empty? &&
        peek[] != loop_lbs[-1] && # since loop ops don't stop blocks from closing, check to make sure there has been at least one op
        is_ancestor(peek[], loop_lbs.last, nodes)
      break if nodes[loop_lbs.last].is_fold_op && !route_to_ancestor(peek[], loop_lbs.last, nodes).any?{|n| nodes[n].args.size > 1 }
      lb = nodes[lb_ind = loop_lbs.pop]
      all_lbs.delete(lb_ind)
      push[AST.new(t, [pop[]], :MatchedEndBracket, lb_ind)]
      lb.impl = nodes.size-1
    end
  }

  # touch each element in stack to fill in implicit data
  stack = stack.size.times.map{ pop[] }.reverse

  [nodes, stack, deleted, nimplicits, all_lbs]
end

def mk_input_node(token = nil)
  $input_checked = true
  AST.new(token, [], :InputNode)
end

def match_brackets(nodes, node, rbs, rb_counts)
  if nodes[node].type == :UnmatchedEndBracket
    rbs << node
    rb_counts << nodes[node].token.str.count(",")
  end

  nodes[node].args.each{|arg| match_brackets(nodes, arg, rbs, rb_counts) }
  if nodes[node].type == :LoopOp
    i = 0
    while i < rbs.size && rb_counts[i] > 0
      rb_counts[i] -= 1
      i += 1
    end

    if i < rbs.size
      rb = rbs.delete_at(i)
      rb_counts.delete_at(i)
      nodes[rb].type = :MatchedEndBracket
      nodes[node].token.matching_bracket = nodes[rb].token
      nodes[rb].token.matching_bracket = nodes[node].token
    end
  end
  if rbs[-1] == node # unmatched
    rbs.pop
    rb_counts.pop
  end
end

def parse_main(tokens, input_present)
  registers = get_var_ids_set(tokens)
  tokens = split_ids(tokens, registers)
  tokens = tokenize_data(tokens, registers)
  null_input = promise{ $input_checked = true; !input_present }
  nodes, stack, deleted, nimplicits, lbs = build_tree(tokens, registers, null_input)
  if nimplicits > 0
    unfinished_extra = lbs.map{|lb|
      case nodes[lb].token.str
        when ";", "mdup"; 1
        when "!", "mpeek"; 2
        else; 0
      end
    }.sum
    # we don't need as many implicits since rotating will add extra duped values not yet present
    nimplicits = [nimplicits - unfinished_extra, 1].max
    nrot = [nimplicits - 1, stack.size - 1].min

    if stack.empty?
      last_token_ind = tokens.size
    else
      last_token = nodes[stack[~nrot]].token
      last_token_ind = tokens.rindex{|t|t.equal? last_token}
      last_token_ind += last_token.str == "let" || last_token.str == "set" ? 2 : 1
    end

    input = Token.new(null_input.value ? "implicit" : "input", :id)

    tokens = tokens[last_token_ind..-1] + [input] + tokens[0,last_token_ind]

    # build the tree after literally rotating the tokens, rather than manipulate the tree because the program rotation could have interupted functions which would not have been able to implicitly close
    nodes, stack, deleted, nimplicits, lbs = build_tree(tokens, registers, null_input)
  end

#     puts tokens.map(&:str)*" "
# puts
  (stack + deleted).each{|si| match_brackets(nodes, si, [], []) }

  last_unmatched = nodes.reverse_each.find{|n| n.type == :UnmatchedEndBracket }

  nodes, stack, deleted, nimplicits, lbs = build_tree(tokens, registers, null_input, last_unmatched)
  raise IogiiError.new("unterminated function", nodes[lbs[-1]]) if !lbs.empty?

  if last_unmatched
    nodes.each{|n|
      raise IogiiError.new "unmatched bracket // implicit value is set but not used", n if n.type == :UnmatchedEndBracket && !n.token.implicit_used
    }
  else
    nodes.filter{|n| n.type == :ImplicitValue }.each{|n|
      if n.impl == nil
        nodes << mk_input_node
        n.impl = nodes.size - 1
      end
    }
  end

  [nodes, main_inds=stack, registers]
end

# ir.rb ########################################################################
IR = Struct.new(:op, :args, :token, :virtual) # virtual is just used for op stats for now

def to_ir(ast_nodes, registers, ast_inds, input_op)
  nodes = []
  ast2ir = {}
  ast_nodes.size.times{|ast_ind| to_ir_h(ast_nodes, ast_ind, nodes, ast2ir, registers, input_op) }
  ast2ir.each{|k,v|
    been = {}
    while AstInd === v
      raise IogiiError.new "direct circular dependency", ast_nodes[v.ind] if been[v.ind]
      been[v.ind] = true
      ast2ir[k] = v = ast2ir[v.ind]
    end
  }
  ir_inds = ast_inds.map{|i| ast2ir[i] }
  nodes.each{|node| node.args = node.args.map{|a| IrInd===a ? a.ind : ast2ir[a] } }
  [nodes, ir_inds]
end

# ir args are assumed to be ast_inds unless this
IrInd = Struct.new(:ind); def ir_ind a; IrInd.new(a); end

# ast2ind is assumed to be ir inds unless this
AstInd = Struct.new(:ind)

def to_ir_h(ast_nodes, ast_ind, nodes, ast2ir, registers, input_op)
  ast_node = ast_nodes[ast_ind]
  case ast_node.type
    when :InputNode
      nodes << IR.new(input_op.value, [], ast_node.token)
      ast2ir[ast_ind] = nodes.size - 1
    when :VarNode
      ast2ir[ast_ind] = AstInd.new registers[ast_node.token.str]
    when :DataNode
      nodes << IR.new(ast_node.token.data_impl, [], ast_node.token)
      ast2ir[ast_ind] = nodes.size - 1
    when :VirtualDuped0
      ast2ir[ast_ind] = AstInd.new ast_node.token.duped_value.args[0]
    when :VirtualDuped1
      ast2ir[ast_ind] = AstInd.new ast_node.token.duped_value.args[1]
    when :ImplicitValue
      ast2ir[ast_ind] = AstInd.new(ast_node.args[0] || ast_node.impl)
    when :IdentityNode
      ast2ir[ast_ind] = AstInd.new ast_node.args[0]
    when :ArgNode
      ast2ir[ast_ind] = AstInd.new ast_node.impl
    when :OpNode
      op = lookup_op(ast_node.token.str)
      nodes << IR.new(op, ast_node.args, ast_node.token)
      ast2ir[ast_ind] = nodes.size - 1
    when :MatchedEndBracket
      # handled by matching left bracket of BlockAst
    when :UnmatchedEndBracket
      ast2ir[ast_ind] = AstInd.new ast_node.args[0]
    when :LoopOp, :MDupOp
      op = lookup_op(ast_node.token.str)
      mod = op.ways[0].mod
      args = ast_node.args
      token = ast_node.token
      block = ast_node.impl
      block_ret = ast_nodes[block].args[0]

      if op.name == "mdup"
        ast2ir[block] = AstInd.new block_ret
        ast2ir[ast_ind] = AstInd.new args[0]
      elsif op.name == "mpeek"
        ast2ir[block] = AstInd.new block_ret
        ast2ir[ast_ind] = AstInd.new args[0]
      elsif op.name == "iterate"
        nodes << IR.new(Ops["cons"].dup_mod(mod), [block_ret, args[0]], token, true)
        ast2ir[block] = nodes.size - 1
        nodes << IR.new(Ops["superpad"].dup_mod(mod), [ir_ind(nodes.size-1)], token, true)
        ast2ir[ast_ind] = nodes.size - 1
      elsif op.name == "iterate0"
        nodes << IR.new(Ops["consDefault"].dup_mod(mod), [block_ret], token, true)
        ast2ir[block] = AstInd.new block_ret
        nodes << IR.new(Ops["superpad"].dup_mod(mod), [ir_ind(nodes.size-1)], token, true)
        ast2ir[ast_ind] = nodes.size - 1
      elsif op.name == "foldr"
        nodes << IR.new(Ops["pad"].dup_mod(mod), [block_ret, args[0]], token, true)
        pad_ind = nodes.size - 1
        nodes << IR.new(Ops["superpad"].dup_mod(mod), [ir_ind(nodes.size-1)], token, true)

        nodes << IR.new(Ops["tail"].dup_mod(mod), [ir_ind(nodes.size-1)], token, true)
        ast2ir[ast_ind] = nodes.size - 1
        nodes << IR.new(Ops["head"].dup_mod(mod), [ir_ind(pad_ind)], token, true)
        ast2ir[block] = nodes.size - 1
      elsif op.name == "foldr0"
        nodes << IR.new(Ops["superpad"].dup_mod(mod), [block_ret], token, true)
        nodes << IR.new(Ops["padDefault"].dup_mod(mod), [ir_ind(nodes.size-1)], token, true)
        nodes << IR.new(Ops["tail"].dup_mod(mod), [ir_ind(nodes.size-1)], token, true)
        ast2ir[ast_ind] = nodes.size - 1
        nodes << IR.new(Ops["head"].dup_mod(mod), [block_ret], token, true)
        ast2ir[block] = nodes.size - 1
      else raise
      end
    else raise "unhandled node type %p" % ast_node.type
  end
end

# ir2.rb #######################################################################
# todo some of this logic is duplicated with infer - unify it

IR2 = Struct.new(:way, :args, :zip_level, :type, :rank)

# IR2 is a simpler graph representation of the program
def to_ir2(ir, ranks, types, ir1_inds)
  ir2ir2 = {}
  ir2_nodes = []
  ir.each.with_index{|node,i|
    arg_types = node.args.map{|a|types[a]}
    arg_ranks = node.args.map{|a|ranks[a]}
    way = find_valid_way(ir[i], arg_types, arg_ranks)

    coerces = coerce?(way.arg_types,arg_types)
    zip_level = zip_level(way, arg_ranks, arg_types)
    excess = excess_ranks(way, arg_ranks, arg_types)

    args = node.args.map{|a| ->{ ir2ir2[a] } }

    # implicit coerces
    args = args.zip(coerces, arg_ranks,0..).map{|a,c,r,i|
      if c
        arg_types[i] = CharType
        arg_ranks[i] += 1
        ir2_nodes << IR2.new(Ops["str"].ways[0], [a], r, CharType, r+1)
        ir2_nodes.size - 1
      else
        a
      end
    }

    # implicit promotes
    args = args.zip(excess,0..,arg_ranks, arg_types, way.special_reps).map{|a,e,ind,r,t,sr|
      npromotes = -e - (sr && e < 0 ? 1 : 0)
      arg_ranks[ind] += [npromotes, 0].max
      npromotes.times{|time|
        ir2_nodes << IR2.new(Ops["just"].ways[0], [a], 0, t, r+time+1)
        a = ir2_nodes.size - 1
      }
      a
    }

    # implicit repeats
    args = args.zip(excess,0..,arg_ranks, arg_types, way.special_reps).map{|a,e,ind,r,t,sr|
      nreps = zip_level - [e, 0].max + (sr && e < 0 ? 1 : 0)
      arg_ranks[ind] += [nreps, 0].max

      nreps.times{|time|
        rep_zip_level = [e, 0].max # max is because could be < 0 for RepSnd ops
        ir2_nodes << IR2.new(Ops["repeat"].ways[0], [a], rep_zip_level, t, r+time+1)
        a = ir2_nodes.size - 1
      }
      a
    }

    # superpad
    if way.name == "superpad"
      a = args[0]
      zip_level.times{|time|
        ir2_nodes << IR2.new(Ops["padDefault"].dup_mod(arg_ranks[0]-time-1).ways[0], [a], time, arg_types[0], arg_ranks[0])
        a = ir2_nodes.size - 1
      }
      ir2ir2[i] = a
    else
      # create node
      ir2_nodes << IR2.new(way, args, zip_level, types[i], ranks[i])
      ir2ir2[i] = ir2_nodes.size - 1
    end
  }
  ir2_nodes.each{|node| node.args.map!{|a| lookup_deferred_ind(a) } }
  print_inds = ir1_inds.map{|i| ir2ir2[i] }
  print_inds.map!{|a| lookup_deferred_ind(a) }

  [ir2_nodes, print_inds]
end

# generate implicit nodes that handle converting all outputs to a single string
def to_ir3(ir2, ir2_inds, pp_sep)
  ir3 = ir2.dup
  ir3 << IR2.new(Ops["nil"].ways[0], [], 0, CharType, 2)
  last_cons = ir3.size - 1
  if pp_sep
    ir3 << IR2.new(new_op("data", "[char]"){ str_to_lazy_list(pp_sep) }.ways[0], [], 0, CharType, 1)
    sep_ind = ir3.size - 1
  end

  ir2_inds.reverse_each{|i|
    if pp_sep
      ir3 << IR2.new(Ops["show"].ways[0], [i], 0, CharType, 1)
      ir3 << IR2.new(Ops["append"].ways[0], [ ir3.size - 1, sep_ind], 0, CharType, 1)
      i = ir3.size - 1
    else
      node = ir2[i]
      if node.type == IntType
        ir3 << node = IR2.new(Ops["str"].ways[0], [i], node.rank, CharType, node.rank+1)
        i = ir3.size-1
      elsif node.type == EmptyType
        # purely for Haskell type checker
        ir3 << node = IR2.new(Ops["estr"].ways[0], [i], node.rank, CharType, node.rank+1)
        i = ir3.size-1
      end
      if node.rank == 0
        ir3 << node = IR2.new(Ops["just"].ways[0], [i], 0, CharType, 1); i = ir3.size-1
      elsif node.rank > 2
        ir3 << node = IR2.new(Unwords, [i], node.rank-2, CharType, node.rank-1); i = ir3.size-1
      end
      while node.rank > 1
        ir3 << node = IR2.new(Unlines, [i], node.rank-2, CharType, node.rank-1); i = ir3.size-1
      end
    end
    ir3 << IR2.new(Ops["cons"].ways[0], [last_cons, i], 0, CharType, 2)
    last_cons = ir3.size-1
  }
  ir3 << IR2.new(Ops["concat"].ways[0], [last_cons], 0, CharType, 1)
  [ir3, ir3.size-1]
end

def lookup_deferred_ind(a)
  been = {}
  while Proc===a
    raise IogiiError.new "direct circular dependency" if been[a]
    been[a] = true
    a=a.call
  end
  a
end

# infer.rb #####################################################################
def solve_types(ir)
  queue = ir.size.times.to_a

  deps = ir.map{[]}
  queue.each{|i|ir[i].args.each{|a|deps[a]<<i}}
  deps.map!(&:uniq)

  types = ir.map{EmptyType}

  queue.each{|i|
    op = ir[i].op
    arg_types = ir[i].args.map{|a|types[a]}
    ways = select_ways_by_type(ir[i].op.ways, arg_types)
    ret_types = ways.map{|way| spec_to_ret(way, arg_types) }
    raise "ambiguous %s %p %p %d" % [op.name, arg_types, ret_types, ways.size] if ret_types.uniq.size > 1
    next if ret_types.empty?
    result_type = ret_types[0]
    if result_type > types[i]
      types[i] = result_type
      queue.concat(deps[i])
    elsif result_type < types[i]
      raise "type invariant has been violated"
    end
  }

  types
end

def select_ways_by_type(ways, arg_types)
  matchedness = ways.map{|way| spec_matches(way.arg_types, arg_types).sort.reverse }
  best_match = matchedness.min
  return [] if best_match[0] == :m4_no_match
  ways.filter.with_index{|way,i| matchedness[i] == best_match }
end

def find_way_by_rank(ways, arg_types, arg_ranks)
  x = ways.map{|way|
    excess = excess_ranks(way, arg_ranks, arg_types)
    [ excess.map{|e| [-e, 0].max }.sort.reverse, # only care about when rank too low
      excess.map{|e| [e, 0].max }.sort.reverse, # but still prefer no excessive rank (for low
      way.mod_arg_ranks.sort # finally look at spec ranks since empty type never has excess
    ]
  }
  xmin_at = (0...x.size).min_by{|i| x[i] }
  xmin = x[xmin_at]
  effects = (0...x.size).filter{|i| x[i] == xmin }.map{|i|
    way = ways[i]
    [way.impl, calc_ret_rank(way, arg_ranks, arg_types)] }
  raise "internal error, ambiguous op %p" % [ways.map(&:name)*" "] if effects.uniq.size > 1
  ways[xmin_at]
end

def find_way(node, ways, arg_types, arg_ranks)
  ways = select_ways_by_type(ways, arg_types)
  raise IogiiError.new "op is not defined for base types: " + arg_types.map{|t|type_to_str(t)}*" ", node if ways.empty?
  find_way_by_rank(ways, arg_types, arg_ranks)
end

def find_valid_way(node, arg_types, arg_ranks)
  way = find_way(node, node.op.ways, arg_types, arg_ranks)
  excess = excess_ranks(way, arg_ranks, arg_types)
  excess.each.with_index{|e,i|
    raise IogiiError.new "arg #{i+1} rank too low and op does not promote (see #{Site}types.html#promotion )", node if e < 0 && (!way.promote || way.promote == NotFirst && i==0)
  }
  raise IogiiError.new "arg ranks too low and Filter op cannot promote BOTH args, doing so would could create rank invariant violations", node if way.name == "filter" && way.mod > 0 && excess.all?{|e|e < 0}

  if !way.can_mod? && node.token && node.token.str[-1] == ","
    begin
      simpler_op = lookup_op(node.token.str[0...-1])
      simpler_way = find_way(node, simpler_op.ways, arg_types, arg_ranks) if simpler_op
    rescue IogiiError
    end
    raise IogiiError.new "extra , used", node if simpler_way == way
  end

  way
end

def solve_ranks(ir,types)
  queue = ir.size.times.to_a

  deps = ir.map{[]}
  queue.each{|i|ir[i].args.each{|a|deps[a]<<i}}
  deps.map!(&:uniq)

  ranks = ir.map{0}

  queue.each{|i|
    op = ir[i].op
    arg_types = ir[i].args.map{|a|types[a]}
    arg_ranks = ir[i].args.map{|a|ranks[a]}

    way = find_way(ir[i], ir[i].op.ways, arg_types, arg_ranks)

    result_rank = calc_ret_rank(way, arg_ranks, arg_types)
    if result_rank > 100 # todo distinguish between this and legitimate cases (which for all practical purposes will never exist)
      raise IogiiError.new "cannot construct the infinite type", ir[i]
    elsif result_rank > ranks[i]
      ranks[i] = result_rank
      queue.concat(deps[i])
    elsif result_rank < ranks[i]
      raise "rank invariant has been violated"
    end
  }
  ranks
end

def calc_ret_rank(way, arg_ranks, arg_types)
  zip_level(way, arg_ranks, arg_types) + adjust_ab_ranks(way, arg_ranks.zip(coerce?(way.arg_types,arg_types)).map{|r,c| r + (c ? 1 : 0) }, arg_types)[1]
end

def adjust_ab_ranks(way, arg_ranks, arg_types)
  return [way.mod_arg_ranks, way.mod_ret_rank] if !way.arg_types.include?(BSpec)

  zip_level = (arg_ranks.zip(arg_types, way.mod_arg_ranks).map{|r, t, o|
    e = r-o
    e = [0, e].max if t == EmptyType
    e
  } << 0).max

  lower_a = lower_b = nil
  way.arg_ranks.zip(way.arg_types, arg_ranks, arg_types){|sr,st,r,t|
    l = [~sr+zip_level+way.mod-r,way.mod].min
    if st == ASpec && t != EmptyType
      lower_a =  [lower_a || l, l].min
    elsif st == BSpec && t != EmptyType
      lower_b = [lower_b || l, l].min
    end
  }
  lower_a ||= 0
  lower_b ||= 0

  # this causes
  lower_b = 0 if lower_a > 0

  [way.mod_arg_ranks.zip(way.arg_types).map{|r,t|
    r - (t == ASpec ? lower_a : 0) - (t == BSpec ? lower_b : 0)
  },
  way.mod_ret_rank - (way.ret_type == ASpec ? lower_a : 0 ) - (way.ret_type  == BSpec ? lower_b : 0)]
end

def excess_ranks(way, ranks, types)
  ranks = ranks.zip(coerce?(way.arg_types,types)).map{|r,c| r + (c ? 1 : 0) }
  ranks.zip(types, adjust_ab_ranks(way, ranks, types)[0]).map{|r, t, o|
    e = r-o
    e = [0, e].min if !way.vectorize
    e = [0, e].max if t == EmptyType
    e
  }
end

def zip_level(way, ranks, types)
  (excess_ranks(way, ranks, types)<<0).max
end

# lazylib.rb ###################################################################
require "set"

def make_promises(ir2)
  promises = ir2.map{|node|
    arg_types = node.args.map{|a|ir2[a].type}

    impl = lambda{|*args|
      $rank = node.way.vectorize ? node.way.mod : ir2[node.args[0]].rank
      $at = arg_types[0]
      $bt = arg_types[1]
      node.way.impl[*args]
    }

    promise{
      args = node.args.map{|a| promises[a] }
      zipn(node.zip_level, args, impl)
    }
  }
  promises
end

class Promise
  def initialize(&block)
    @impl=block
  end
  def value
    @impl=@impl[] if Proc===@impl
    @impl
  end
  def empty
    value.empty?
  end
end

def promise(&b)
  Promise.new(&b)
end
class Object
  def const
    Promise.new{self}
  end
end

def zipn(n, a, f)
  return f[*a] if n <= 0 || a==[]
  return [] if a.any?{|i|i.empty}
  [promise{zipn(n-1, a.map{|i|i.value[0]}, f) },
   promise{zipn(n, a.map{|i|i.value[1]}, f) }]
end

def output(str)
   print(str)
end

def error_output(str)
   $stderr.write(str)
end

def repeat(a)
  (ret = [a]) << ret.const
end

def concat_map(v,rhs=Null,first=true,&b)
  if v.empty
    rhs.value
  else
    b[v.value[0],Promise.new{concat_map(v.value[1],rhs,false,&b)},first]
  end
end

def append(v,r)
  v.empty ? r.value : [v.value[0],promise{append(v.value[1], r)}]
end

def join(a,b)
  return [] if a.empty
  append(a.value[0],promise{
    if b.empty || a.value[1].empty
      []
    else
      append(b.value[0], promise{ join(a.value[1], b.value[1]) })
    end
  })
end

def starts_with(a,b) # assumed to be strs, returns remainder if match otherwise nil
  until b.empty
    return nil if a.empty || a.value[0].value != b.value[0].value
    a = a.value[1]
    b = b.value[1]
  end
  a
end

def cut(a,b) # fyi could be lazier since we know we return a list always
  return [a,Null] if a.empty || b.empty
  if (remainder=starts_with(a,b.value[0]))
    [Null,Promise.new{cut(remainder,b.value[1])}]
  else
    rhs=Promise.new{cut(a.value[1],b)}
    [promise{[a.value[0],Promise.new{rhs.value[0].value}]},promise{rhs.value[1].value}]
  end
end

def cut_any(a,b) # fyi could be lazier since we know we return a list always
  return [a,Null] if a.empty || b.empty
  bb = b.value[0]
  until bb.empty
    if remainder=starts_with(a,bb.value[0])
      return [Null,Promise.new{cut_any(remainder,b.value[1])}]
    end
    bb=bb.value[1]
  end
  rhs=Promise.new{cut_any(a.value[1],b)}
  [promise{[a.value[0],Promise.new{rhs.value[0].value}]},promise{rhs.value[1].value}]
end

def scan_any(a,b) # fyi could be lazier?
  until a.empty || b.empty
    bb = b.value[0]
    until bb.empty
      if remainder=starts_with(a,bb.value[0])
        return [bb.value[0], Promise.new{scan_any(remainder,b.value[1])}]
      end
      bb=bb.value[1]
    end
    a = a.value[1]
  end
  []
end

def substr_ind(a,b) # or len of a if not found
  i = 0
  until a.empty || starts_with(a,b)
    i += 1
    a = a.value[1]
  end
  i
end

def any_substr_ind(a,b) # or len of a if not found
  i = 0
  until a.empty
    bb = b
    until bb.empty
      return [i,bb.value[0]] if starts_with(a,bb.value[0])
      bb=bb.value[1]
    end
    i += 1
    a = a.value[1]
  end
  [i, Null]
end

def last(a, prev)
  until a.empty
    prev = a.value[0]
    a = a.value[1]
  end
  prev.value
end

def init(a)
  return [] if a.empty || a.value[1].empty
  [a.value[0], Promise.new{ init(a.value[1]) }]
end

FalseChars = {0=>1,9=>1,10=>1,11=>1,12=>1,13=>1,32=>1}
def truthy(type, value)
  return !value.empty? if Array === value
  case type
    when IntType
      return value != 0
    when CharType
      !FalseChars.include?(value)
    else raise
  end
end

def reverse(a)
  sofar=[]
  until a.empty
    sofar = [a.value[0],sofar.const]
    a = a.value[1]
  end
  sofar
end

def padv(a,b)
  [
    promise{ a.empty ? b.value : a.value[0].value },
    promise{ padv( promise{ a.empty ? [] : a.value[1].value }, b) }
  ]
end

def pow(a,b)
  # manually implement this op so that it is consistent and doesn't return rationals / overflow
  return 0 if b < 0 && a == 0
  neg_exponent = b < 0
  b = b.abs

  y = 1
  while b >= 1
    y *= a if b%2 == 1
    a *= a
    b /= 2
  end
  neg_exponent ? 1 / y : y
end

TestUnicodeChar = [1000].pack('U')
ByteEncoding = Encoding::ISO8859_1
begin
  TestUnicodeChar.encode(Encoding.default_external)
  def int_to_char(i)
    begin
      [i].pack("U")
    rescue
      raise IogiiError.new("char out of range %d" % i)
    end
  end
rescue Encoding::UndefinedConversionError # (e.g. is ASCII)
  # to work with values 128..255 which are invalid in regular ascii
  Encoding.default_internal = Encoding.default_external = ByteEncoding
  def int_to_char(i)
    (i%256).chr
  end
end

def prints(value)
  while !value.empty?
    v = value[0].value
    output int_to_char(v)
    value = value[1].value
  end
end

Null = [].const

def str_to_lazy_list(s,rhs=Null)
  to_lazy_list(s.chars.map(&:ord), rhs)
end

def to_lazy_list(l, rhs=Null, ind=0)
  ind >= l.size ? rhs.value : [l[ind].const, Promise.new{to_lazy_list(l, rhs, ind+1)}]
end

def to_lazy_list_rec(l, rhs=Null, ind=0)
  return str_to_lazy_list(l) if String === l
  return l if !(Array === l)
  ind >= l.size ? rhs.value : [to_lazy_list_rec(l[ind]).const, Promise.new{to_lazy_list_rec(l, rhs, ind+1)}]
end

def to_eager_str(v)
  to_eager_list(v.const).map{|i|int_to_char(i)}.join
end

def to_eager_list(a)
  sofar=[]
  until a.empty
    sofar << a.value[0].value
    a = a.value[1]
  end
  sofar
end

def to_eager_list_rec(a)
  return a.value unless Array===a.value
  sofar=[]
  until a.empty
    sofar << to_eager_list_rec(a.value[0])
    a = a.value[1]
  end
  sofar
end

def str(i) # todo why this and str_to_lazy_list ?
  to_lazy_list(i.value.to_s.bytes.to_a)
end

def is_digit(i)
  i>=48 && i<58
end

def split_non_digits(s)
  return [] if s.empty
  v,found,s2=read_num(s)
  return [] if !found
  [v.const,Promise.new{split_non_digits(s2)}]
end

def read_num(s)
  multiplier=1
  until s.empty || is_digit(s.value[0].value)
    if s.value[0].value == ?-.ord
      multiplier *= -1
    else
      multiplier = 1
    end
    s = s.value[1]
  end
  v = 0
  found_int = false
  until s.empty || !is_digit(s.value[0].value)
    found_int = true
    v = v*10+s.value[0].value-48
    s = s.value[1]
  end

  [multiplier * v, found_int, s]
end

def lines(s)
  return [] if s.empty

  after = Promise.new{lines(s.value[1])}
  if s.value[0].value == 10
    [Null, after]
  else
    [Promise.new{
      after.empty ? [s.value[0], Null] : [s.value[0], after.value[0]]
     },
     Promise.new{
      after.empty ? [] : after.value[1].value
     }]
   end
end

def take(n, a)
  return [] if n < 1 || a.empty
  [a.value[0], Promise.new{ take(n-1, a.value[1]) }]
end

def drop(n, a)
  while n>=1 && !a.empty
    n-=1
    a=a.value[1]
  end
  a.value
end

def indices(a, b, i=0)
  until a.empty
    return [i.const, promise{ indices(a.value[1],b,i+1) }] if spaceship(a.value[0],b) == 0
    i += 1
    a = a.value[1]
  end
  return []
end

def len(a)
  return 0 if a.empty?
  return 1+len(a[1].value)
end

def sort_by(a,b)
  fromby(sort(toby(a,b),true))
end

def toby(a,b)
  return Null if a.empty || b.empty
  Promise.new{ [[a.value[0], b.value[0]], toby(a.value[1], b.value[1])] }
end

def fromby(a)
  return [] if a == []
  [Promise.new{a[0][0].value}, Promise.new{fromby(a[1].value)}]
end

# It would be very interesting and useful to design a more lazy sorting algorithm
# so that you can select ith element in O(n) total time after sorting a list.
def sort(a,by=false)
  return [] if a.empty
  return a.value if a.value[1].empty
  n=len(a.value)
  left=take(n/2, a).const
  right=drop(n/2, a).const
  merge(sort(left,by),sort(right,by),by)
end

def merge(a,b,by)
  return b if a==[]
  return a if b==[]
  if (by ? spaceship(a[0][1], b[0][1]) : spaceship(a[0], b[0])) <= 0
    [a[0], Promise.new{merge(a[1].value,b,by)}]
  else
    [b[0], Promise.new{merge(a,b[1].value,by)}]
  end
end

def spaceship(a,b)
  if Array === a.value
    until a.empty && b.empty
      return -1 if a.empty
      return 1 if b.empty
      s0 = spaceship(a.value[0],b.value[0])
      return s0 if s0 != 0
      a = a.value[1]
      b = b.value[1]
    end
    return 0
  else
    a.value<=>b.value
  end
end

def inspectv(t,rank,value,rhs=Null)
  if t == CharType && rank == 1
    ['"'.ord.const, Promise.new{
      concat_map(value,Promise.new{str_to_lazy_list('"',rhs)}){|v,r,first|
       str_to_lazy_list(escape_str_char(v.value),r)
      }
    }]
  elsif rank > 0 #List
    ["[".ord.const, Promise.new{
      concat_map(value,Promise.new{str_to_lazy_list("]",rhs)}){|v,r,first|
        first ?
          inspectv(t,rank-1,v,r) :
          [','.ord.const,Promise.new{inspectv(t,rank-1,v,r)}]
      }
    }]
  elsif t == EmptyType
    value.value # take the value so it can throw
    raise
  elsif t == IntType
      str_to_lazy_list(value.value.to_s,rhs)
  elsif t == CharType
    str_to_lazy_list(inspect_char(value.value),rhs)
  else
    raise
  end
end

def filter(a,b,bt)
  until a.empty || b.empty
    if truthy(bt,b.value[0].value)
      return [a.value[0],Promise.new{ filter(a.value[1],b.value[1],bt) }]
    else
      a = a.value[1]
      b = b.value[1]
    end
  end
  []
end

def take_while(a,b,bt)
  return [] if a.empty || b.empty
  if truthy(bt,b.value[0].value)
   [a.value[0],Promise.new{ take_while(a.value[1],b.value[1],bt) }]
  else
    []
  end
end

def drop_until(a,b,bt)
  until a.empty || b.empty
    if truthy(bt,b.value[0].value)
      return a.value
    else
      a = a.value[1]
      b = b.value[1]
    end
  end
  []
end

def chunk_while(a,b,btype)
  return [Null, Null] if a.empty
  rest = promise { chunk_while(a.value[1], promise{ b.empty ? [] : b.value[1].value }, btype) }
  truthy = promise { b.empty || truthy(btype,b.value[0].value) }
  [promise{ [a.value[0], promise{ truthy.value ? rest.value[0].value : []}] },
   promise{ truthy.value ? rest.value[1].value : rest.value }]
end

def strip(a,at)
  lstrip = drop_until(a,a,at)
  b = reverse(lstrip.const).const
  reverse(drop_until(b,b,at).const)
end

# these aren't as lazy as possible, but it gets to use hashes
def isuniq(a,h=Hash.new(-1))
  return [] if a.empty
  [(h[to_eager_list_rec(a.value[0])]+=1) == 0 ? 1.const : 0.const, Promise.new{isuniq(a.value[1], h)}]
end

def set_diff(a,b)
  counts = Hash.new(0)
  to_eager_list_rec(b).each{|be| counts[be] += 1 }
  diff_helper(a, counts)
end

def diff_helper(a, counts)
  while !a.empty && counts[ae=to_eager_list_rec(a.value[0])] > 0
    a = a.value[1]
    counts[ae] -= 1
  end
  return [] if a.empty
  [a.value[0], Promise.new{ diff_helper(a.value[1], counts) }]
end

def range(a,b)
  return [] if a>=b
  [a.const, Promise.new{range(a+1,b)}]
end

def range_from(a)
  [a.const, Promise.new{range_from(a+1)}]
end

def group_while(a,b,btype)
  return [Null,Null] if a.empty || b.empty
  b0true = Promise.new{ truthy(btype,b.value[0].value)}
  rhs = Promise.new{ group_while(a.value[1],b.value[1],btype) }
  [
    Promise.new{
      if b0true.value
        [a.value[0], rhs.value[0]]
      else
        []
      end
    },
    Promise.new{
      if b0true.value
        rhs.value[1].value
      else
        rhs.value
      end
    }
  ]
end

def reshape(a, b)
  return [] if b.empty
  n = b.value[0].value
  return [] if n>0 && a.empty
  return [Null, promise{ reshape(a, b.value[1]) }] if n <= 0
  [promise{ take(n, a) },
   promise{
    d = drop(n-1, a)
    # took more than all, next is []
    d == [] ? [] : reshape(d[1], b.value[1])
   }
  ]
end

def map(a,&b)
  a.empty ? [] : [Promise.new{b[a.value[0]]}, Promise.new{map(a.value[1],&b)}]
end

def zero(rank,type=nil)
  return [] if rank > 0
  type == CharType ? 32 : 0
  # empty type also returns 0 and ops are constructed so that their type would also be int
end

def concat(a)
  concat_map(a){|i,r,first|append(i,r)}
end

def rstrip(a)
  return [] if a.empty
  rest = promise{ rstrip(a.value[1]) }
  return [] if a.value[0].empty && rest.empty
  [a.value[0], rest]
end

def inf_tails(a)
  ans=[a, promise{ map(ans.const){|e| map(e){|e2| e2.empty ? [] : e2.value[1].value }} }]
end

def transpose(a,at,rank)
  z = promise{ map(promise{ inf_tails(a) }){|e| rstrip(e) } }
  t = promise{ map(z){|e| map(e){|e2| e2.empty ? zero(rank,at) : e2.value[0].value } } }
  take_while(t,t,at)
end

def square_root(x,n)
  raise IogiiError.new "negative square root" if x < 0
  return 0 if x==0
  guess = x
  while (r=(x/guess+guess)/n) < guess
    guess = r
  end
  guess
end

CharClasses = [
  [*'0'..'9'],
  [*'a'..'z'],
  [*'A'..'Z'],
  [*' '..126.chr] - ([*'a'..'z'] + [*'A'..'Z'] + [*'0'..'9'] + [' ',"\n"]),
  ["\n",' '],
].map{|chars| chars.map(&:ord).to_set }

def char_class(a, used = [false] * CharClasses.size)
  return [] if a.empty
  i = (0...CharClasses.size).find{|i| CharClasses[i].include? a.value[0].value }
  if !i || used[i]
    char_class(a.value[1], used)
  else
    used[i] = true
    [ to_lazy_list([*CharClasses[i]].sort).const, promise{ char_class(a.value[1], used) } ]
  end
end

def is_char_class(a, b)
  clazz = CharClasses.find{|clazz| clazz.include?(a.value)  }
  return 0 if !clazz
  until b.empty
    return 1 if clazz.include?(b.value[0].value)
    b = b.value[1]
  end
  return 0
end

def to_base(a,b)
  raise IogiiError.new "base 0", nil if b==0
  to_base_h(a.abs,b,a<=>0)
end

def to_base_h(a,b,sign)
  return [] if a==0
  digit = a%b*sign
  [digit.const, Promise.new{to_base_h((a-digit*sign)/b,b,sign)}]
end

def from_base(a,b)
  x=0
  until a.empty?
    x=x*b+a[0].value
    a=a[1].value
  end
  x
end

def undigits(a)
  from_base(concat(map(a){|i|
    x = reverse(to_base(i.value,10).const)
    x.empty? ? [0.const, Null] : x
  }.const), 10)
end

def read_stdin(input)
  c=input.getc
  if c.nil?
    []
  else
    [c.ord.const, Promise.new{ read_stdin(input) }]
  end
end

# auto_parse.rb ################################################################

SepRx = /, | |,/
NumRx = /-*\d+/

# return list of inputs or false if auto parse empty (list is from args)
def read_inputs(input)
  input = to_eager_str(read_stdin(input)) if input.respond_to?(:getc)
  !input.empty? && ( Array === input ? input : [input] )
end

def parse_input(inputs)
  return [[], EmptyType, 1] if !inputs

  input_lines = inputs.map{|input| input.lines.map(&:chomp) }

  # is it just numbers?
  if input_lines.all?{|input| input.all?{|line| line =~ /^(#{NumRx}#{SepRx})*#{NumRx}?$/ && line.scan(NumRx).all?{|num| num == num.to_i.to_s } } } &&
      input_lines.flatten.any?{|line| line =~ NumRx }

    nums = input_lines.map{|input|
      input.map{|line|
        to_eager_list(split_non_digits(str_to_lazy_list(line).const).const)
      }
    }
    rank = 3

    if nums.all?{|arg| arg.all?{|line| line.size == 1 } }
      nums = nums.map{|arg| arg.map{|line| line[0] } }
      rank -= 1
    end

    if nums.all?{|arg| arg.size == 1}
      nums = nums.map{|arg| arg[0] }
      rank -= 1
    end

    if nums.size == 1
      nums = nums[0]
      rank -= 1
    end

    [to_lazy_list_rec(nums), IntType, rank]
  else # not numbers
    rank = 3
    if input_lines.all?{|arg| arg.size == 1}
      input_lines = input_lines.map{|arg| arg[0] }
      rank -= 1
    end

    if input_lines.size == 1
      input_lines = input_lines[0]
      rank -= 1
    end

    [to_lazy_list_rec(input_lines), CharType, rank]
  end
end

# hs.rb ########################################################################
# extend default rules are for: https://stackoverflow.com/questions/79516057/solving-ambiguous-type-variable-errors-without-adding-a-specific-type-annotation/79516109?noredirect=1#comment140231167_79516109
Header = %q({-# LANGUAGE ExtendedDefaultRules #-}

import System.IO
import Data.List
import Data.Char
import Data.String
import Data.Maybe
import System.Info
import qualified Data.Set as Set
import qualified Data.Map as Map
import System.Environment

myChr :: Integer -> Char
myChr i = chr $ fromIntegral i `mod` 256
myOrd :: Char -> Integer
myOrd c = fromIntegral $ ord c
bool2i :: Bool -> Integer
bool2i b = if b then 1 else 0
falseChars = Set.fromList [0,9,10,11,12,13,32]
truthyChar :: Integer -> Bool
truthyChar = not . (flip Set.member falseChars)
readAll :: String -> [Integer]
readAll xs =
  if num == [] then []
  else sign * (read num :: Integer) : readAll afterNum
  where
    (beforeNum,atNum) = span (not . isDigit) xs
    (num,afterNum) = span isDigit atNum
    negatives = takeWhile (== '-') (reverse beforeNum)
    sign = (-1) ^ length negatives

iogUnwords :: [[Integer]] -> [Integer]
iogUnwords = intercalate [32]
iogUnlines :: [[Integer]] -> [Integer]
iogUnlines = concatMap (++[10])
iogLines [] = [] -- copied from GHC but with integers instead of chars
iogLines s  = cons (case break (== 10) s of
              (l, s') -> (l, case s' of
                    []      -> []
                    _:s''   -> iogLines s''))
    where cons ~(h, t) =  h : t

iogError msg = error $ "\x1b[31mERROR: \x1b[0m" ++ msg

-- int ops
iogAdd = (+)
iogSub = (-)
iogCharSubtraction = (-)
iogMult = (*)
iogDiv a b = if b == 0 then 0 else a `div` b
iogMod a b = if b == 0 then 0 else a `mod` b
iogPow a b
  | b < 0 && a == 0 = 0
  | b < 0 = 1 `div` pow
  | otherwise = pow
  where pow = a^(abs b)
iogNegate x = -x
iogAbs = abs
iogCountTo x = [1..x]
iogWholes = [0..]
iogSum = sum :: [Integer] -> Integer
iogSucc = (+1)
iogPred x = x-1

-- char ops
iogCharRange a b = [a..b]
iogRead = iogHeadZero 0 . iogReadAll
iogReadAll x = readAll (map myChr x)
iogOrd = id
iogChr = id
iogStr = (map myOrd) . show :: Integer -> [Integer]
iogEstr :: a -> [Integer]
iogEstr a = a `seq` undefined
iogStrip = f . f where f = reverse . dropWhile (not . truthyChar) :: [Integer] -> [Integer]
iogReplicate a b = concat $ genericReplicate b a
iogJoin a b = if null a then [] else head a ++ concat (zipWith (++) b (tail a))
iogSplit a b = filter (not . null) $ iogSplitKeepEmpties a (repeat b)
iogSplitKeepEmpties a b
  | null a || null b = [a]
  | otherwise = maybe
    ((head a : head rhs) : tail rhs)
    (\remainder -> [] : iogSplitKeepEmpties remainder (tail b))
    (stripPrefix (head b) a)
  where
    rhs = iogSplitKeepEmpties (tail a) b

iogCutAny a b
  | null a || null b = [a]
  | otherwise = maybe
    ((head a : head rhs) : tail rhs)
    (\match -> [] : iogCutAny (drop (length match) a) (tail b))
    (find (flip isPrefixOf a) (head b))
  where
    rhs = iogCutAny (tail a) b

iogScanAny a b
  | null a || null b = []
  | otherwise = maybe
    (iogScanAny (tail a) b)
    (\match -> match : iogScanAny (drop (length match) a) (tail b))
    (find (flip isPrefixOf a) (head b))
  where

substrInd needle haystack = maybe (length haystack) id (findIndex (isPrefixOf needle) (tails haystack))
iogDropUntilAfterSubstring a b = drop (substrInd b a + length b) a
iogKeepUntilSubstring a b = take (substrInd b a) a
iogGetSubstring a b = take (length b) $ drop (substrInd b a) a

anySubstrInd _ [] = (0, [])
anySubstrInd needles haystack =
   case find (flip isPrefixOf haystack) needles of
      Just needle -> (0, needle)
      Nothing -> let (ind, match) = anySubstrInd needles (tail haystack) in
         (ind+1, match)
iogDropUntilAfterAnySubstring a b = drop (pos + length match) a where (pos, match) = anySubstrInd b a
iogKeepUntilAnySubstring a b = take pos a where (pos, match) = anySubstrInd b a
iogGetAnySubstring a b = take (length match) $ drop pos a where (pos, match) = anySubstrInd b a

charClasses = map (Set.fromList) charClassesLists
charClassesLists = map (map myOrd) [
    ['a'..'z'],
    ['A'..'Z'],
    ['0'..'9'],
    [' '..chr 126] \\\\ (['a'..'z']++['A'..'Z']++['0'..'9']++" \n"),
    " \n"
  ]

iogCharClass a = concat $ charClass a (replicate (length charClasses) False) where
  charClass [] _ = []
  charClass (a:as) used =
    let
      is = [i | i <- [0..length charClasses - 1], Set.member a (charClasses !! i)]
      i = head is
    in if null is || used !! i
       then charClass as used
       else (charClassesLists !! i) : charClass as (markUsed used i)
  markUsed used i = take i used ++ [True] ++ drop (i + 1) used
iogIsCharClass a b = case find (Set.member a) charClasses of
  Just clazz -> bool2i $ any (flip Set.member clazz) b
  Nothing -> 0

iogRightJustify a b = replicate (fromInteger b - length a) 32 ++ a

-- generic ops
iogTake = flip genericTake
iogDrop = flip genericDrop
iogJust = (:[])
iogCons = flip (:)
iogNil = []
iogAppend = (++)
iogReverse = reverse
iogNotTruthyA0 truthyFn x = 1 - bool2i (truthyFn x)
iogRepeat = repeat
iogTakeWhileTruthyB1 truthyFn a b = iogTakeWhileHelper a (map truthyFn b) where
  iogTakeWhileHelper [] _ = []
  iogTakeWhileHelper _ [] = []
  iogTakeWhileHelper (a:as) (b:bs)
      | b = a : iogTakeWhileHelper as bs
      | otherwise = []
iogGetZero zero a b = if b < 0 || null rest then zero else head rest
  where rest = genericDrop b a
iogHeadZero zero a = if null a then zero else head a
iogTail a = if null a then [] else tail a
iogInit a = if null a then [] else init a
iogLastZero zero a = if null a then zero else last a
iogConsDefaultZero zero a = zero : a

iogTransposeZero zero a = takeWhile (not . null)
  $ map (map $ iogHeadZero zero)
  $ map rstrip
  $ iterate (map iogTail) a
  where
    rstrip [] = []
    rstrip (h:t)
      | null h && null rest = []
      | otherwise = h : rest
      where rest = rstrip t

iogLen = genericLength
iogSortBy a b = map fst $ sortOn snd (zip a b)
iogConcat :: [[a]] -> [a]
iogConcat = concat
iogFilterTruthyB1 truthyFn = (catMaybes .) . zipWith (\ai bi->if truthyFn bi then Just ai else Nothing )

iogSetDiff :: Ord a => [a] -> [a] -> [a]
iogSetDiff xs ys = go xs $ foldr (\x -> Map.insertWith (+) x 1) Map.empty ys
  where
    go :: (Ord a) => [a] -> Map.Map a Int -> [a]
    go [] _ = []
    go (x:xs) m
      | Map.findWithDefault 0 x m > 0 = go xs (Map.adjust pred x m)
      | otherwise = x : go xs m

iogIfElseTruthyA0 truthyFn a b c = if truthyFn a then b else c
iogPadDefaultZero zero a = iogPad a zero
iogEqual a b = bool2i (a == b)
iogLessThan a b = bool2i (a < b)
iogIndices a b = map toInteger (elemIndices b a)

iogReshape a b
  | null b = []
  | n>0 && null a = []
  | n <= 0 = [] : (iogReshape a $ tail b)
  | otherwise = genericTake n a : if null d then [] else iogReshape (tail d) (tail b)
  where
    n = head b
    d = genericDrop (n-1) a

iogIsFirst :: Ord a => [a] -> [Integer]
iogIsFirst a = zipWith ((bool2i .) . (not .) . Set.member) a sets where
  sets = Set.empty : zipWith Set.insert a sets

iogChunkWhenTruthyB1 truhtyFn a b = chunkWhenHelper a (map truhtyFn b)
chunkWhenHelper a b
  | null a = [[]]
  | otherwise = (head a : if truthy then head rest else []) : (if truthy then tail rest else rest)
  where
    rest = chunkWhenHelper (tail a) (iogTail b)
    truthy = null b || head b

-- low rank overrides
iogUppercase a = if a >= myOrd('a') && a <= myOrd('z') then a-32 else a
iogLowercase a = if a >= myOrd('A') && a <= myOrd('Z') then a+32 else a
iogWords a = filter (not . null) $ map iogStrip $ chunkWhenHelper a (map truthyChar a)
iogDigits a = if a == 0 then [0] else iogToBase a 10
iogUndigits a = iogFromBase (concat (map iogDigits a)) 10

iogPowOf2 = (2^)
iogBits = toBase 2

iogToBase a b = reverse $ toBase b a
toBase b a = if b==0 then iogError "base 0" else toBaseHelper (abs a) where
  sign = if a > 0 then 1 else -1
  toBaseHelper a
    | a == 0 = []
    | otherwise = digit : toBaseHelper ((a-digit*sign)`div`b)
    where
      digit = (a `mod` b)*sign

iogFromBase a b = last results where
  results = 0 : zipWith (\x aa->x*b + aa) results a

iogRangeBegin a = [a..]
iogRangeToZero zero a = [zero..a-1]

iogSqrt x
  | x < 0 = iogError "negative square root"
  | x == 0 = 0
  | otherwise = sqrtGuess x x
sqrtGuess guess x = case ((x `div` guess) + guess) `div` 2 of
   r | r>=guess -> guess
     | otherwise -> sqrtGuess r x

iogMin a b = minimum [a,b]
iogMax a b = maximum [a,b]
iogPowOf10 = (10^)
iogProd = product :: [Integer] -> Integer

-- internal ops
iogPad :: [a] -> a -> [a]
iogPad a b = (if null a then b else head a) : iogPad (iogTail a) b
iogZeroZero zero a = zero
iogZeromZero = iogZeroZero

-- intuitive overloads
iogJoinM a = iogJoin (map iogJust a)

-- special ops
iogDel = undefined
iogVersion = map myOrd $ VERSION ++ ", " ++ compilerName ++ ": " ++ show compilerVersion
iogType ts a = map myOrd $ ts
iogShow coerceFn a = map myOrd $ show $ coerceFn a
iogInputEmpty = []

main=do
  hSetEncoding stdin char8
  hSetEncoding stdout char8
  hsArgs <- getArgs
  interact (iogMain hsArgs)

-- END HEADER --

)

Header.sub!("VERSION", to_eager_str(Ops["version"].ways[0].impl.call).inspect)
if Encoding.default_external != ByteEncoding
  Header.gsub!("`mod` 256","")
  Header.gsub!('hSetEncoding stdin char8','')
  Header.gsub!('hSetEncoding stdout char8','')
end

def to_hs_type(type, rank)
  (type == EmptyType ? "Ord a => " : "") +
    type_and_rank_to_str(type == EmptyType ? "a" : "Integer", rank)
end

ZipNames = ["", "map", "zipWith", "zipWith3"]
def to_hs_zips(n, nargs, op)
  n <= 0 ? op : "#{ZipNames[nargs]} (#{to_hs_zips(n-1, nargs, op)})"
end

def does_source_use_input(source)
  $input_checked = false
  begin
    gen_graph(source, "", ast_cb: ->_,_{ return $input_checked })
  rescue IogiiError => e
  end
  $input_checked
end

def generate_hs(source, pp_sep)
  output Header

  case input_mode(source)
  when :raw_mode
    output "iogMain hsArgs hsStdin = if null hsArgs then iogMainListChar iogRawStdin else iogMainListListChar iogRawArgs where
   iogRawArgs = map (map myOrd) hsArgs
   iogRawStdin = map myOrd hsStdin\n"
   possible_input_formats = ["a",["a","b"]]
  when :raw_line_mode
    output "iogMain hsArgs hsStdin = if null hsArgs then iogMainListListChar iogRawStdinLines else iogMainListListListChar iogRawArgLines where
   iogRawArgLines = map iogLines $ map (map myOrd) hsArgs
   iogRawStdinLines = iogLines $ map myOrd hsStdin\n"
   possible_input_formats = ["a\nb",["a\nb","a\nb"]]
  else
    if !does_source_use_input(source) # do this to avoid unnecessarily awaiting input that is never used
      output "iogMain hsArgs hsStdin = iogMainListEmpty [] where\n"
      possible_input_formats = [""]
    else
      output 'iogMain hsArgs hsStdin
  | null hsArgs && null stdinLines = iogMainListEmpty undefined
  | onlyNums = case nums of
    [a] -> intMatrixSelector a
    _ | all ((==1) . length) nums -> intMatrixSelector $ map head nums
      | all (all ((==1) . length)) nums -> intMatrixSelector $ map (map head) nums
      | otherwise -> iogMainListListListInt nums
  | otherwise = strMatrixSelector $ map (map (map myOrd)) inputs
  where
   stdinLines = lines hsStdin
   inputs = if null hsArgs then [stdinLines] else map lines hsArgs
   nums = map (map readAll) inputs
   nonNums = zipWith (\lines numsl -> zipWith iogSplitKeepEmpties lines (map (map show) numsl)) inputs nums

   isSep s = s == "," || s == ", " || s == " "
   numLine cut = head cut == "" && all isSep (tail (if null (last cut) && length cut > 1 then init cut else cut))
   onlyNums = not (null (concat $ concat nums)) && all (all numLine) nonNums

   intMatrixSelector [[a]] =  iogMainInt a
   intMatrixSelector [a] = iogMainListInt a
   intMatrixSelector a | all ((==1) . length) a = iogMainListInt (map head a)
   intMatrixSelector a = iogMainListListInt a

   strMatrixSelector [[a]] =  iogMainListChar a
   strMatrixSelector [a] = iogMainListListChar a
   strMatrixSelector a | all ((==1) . length) a = iogMainListListChar (map head a)
   strMatrixSelector a = iogMainListListListChar a
'
      possible_input_formats = ["1","1 1","1 1\n1",["1 1\n1","1 1\n1"],"a","a\nb",["a\nb","a\nb"],""]
    end
  end

  possible_input_formats.each.with_index{|fake_input, i|
    _, type, rank = parse_input(read_inputs(fake_input))
    main_name = "iogMain#{"List"*rank}#{type_to_str(type).capitalize}"
    begin
      ir3, ir3_ind = gen_graph(source, fake_input, pp_sep: pp_sep)
      output "#{main_name} iogInput =\n  let\n" % i
      to_hs_main(ir3,ir3_ind)
    rescue IogiiError => e
      output(("#{main_name} iogInput = error %p\n" % e.message).gsub("\\e","\\x1b"))
    end
  }
end

def to_hs_main(ir3, ir3_ind)
  ir3.each.with_index{|node,i|
    args = node.args.map{|a|"a#{a} "}.join
    if node.way.name == "data"
      op = to_eager_list_rec(node.way.impl.call.const).inspect
    else
      op = "iog#{node.way.name[0].capitalize+node.way.name[1..]}"
      # haskell op names proceed names with special forms to denote what additional information they need for polymorphism
      if Header =~ /#{op}Truthy(.)(\d)/
        arg = ir3[node.args[$1.ord - ?A.ord]]
        # here we calculate rank rather than use way.mod because ab type adjustments could change it
        truthyFn = if arg.rank - node.zip_level > $2.to_i || arg.type == EmptyType
            "(not . null)"
          elsif arg.type == IntType
            "(/= 0)"
          elsif arg.type == CharType
            "truthyChar"
          else
            # force the value (which is invalid) to be calculated and return a value of type bool
            "(flip seq (undefined::Bool))"
          end
        op = "#$& #{truthyFn}"
      elsif Header =~ /#{op}Zero/ # the zero arg is always the first one
        a = ir3[node.args[0]]
        zero = if node.way.mod > 0
            "[]"
          elsif a.type == CharType
            "32"
          else # int / empty
            "0"
          end
        op = "#$& #{zero}"
      elsif op == "iogType"
        arg = ir3[ir3[i].args[0]]
        op += " " + type_and_rank_to_str(arg.type, arg.rank).inspect
      elsif op == "iogShow"
        arg = ir3[ir3[i].args[0]]
        if arg.type == CharType
          op += " (" + to_hs_zips(arg.rank, 1, "myChr") + ")"
        elsif arg.type == EmptyType
            # force the value (which is invalid) to be calculated and return a value of type int (any type that can be shown would work)
          op += " (" + to_hs_zips(arg.rank, 1, "(flip seq (undefined::Int))") + ")"
        else
          op += " id"
        end
      end
    end

    output "    a#{i} :: #{to_hs_type(node.type, node.rank)}\n"
    output "    a#{i} = #{to_hs_zips(node.zip_level, node.args.size, op)} #{args}\n"
  }
  output "  in map myChr a#{ir3_ind}\n"
end

# run.rb #######################################################################

Site = "https://golfscript.com/iogii/"

def input_mode(source)
  return :raw_mode if source[0] == ","
  return :raw_line_mode if source[0] == " "
  return :auto_parse_mode
end

def gen_graph(source, input, pp_sep: nil, ast_cb: nil, ir_cb: nil)
  tokens = lex(source)

  input_mode = input_mode(source)
  if input_mode == :auto_parse_mode
    inputs = read_inputs(input)
    input_present = !!inputs
  else
    tokens.shift if source[0] != " "
    input_present = true
  end

  ast, ast_inds, registers = *parse_main(tokens, input_present)

  ast_cb[ast, ast_inds] if ast_cb

  input_op = promise { # don't eval this unless needed since awaits input
    if input_mode == :raw_mode
      if Array === input
        read_input = promise { to_lazy_list(input.map{|a| str_to_lazy_list(a) }) }
        new_op("input", "[[char]]"){ read_input.value }
      else
        read_input = promise { read_stdin(input) }
        new_op("input", "[char]"){ read_input.value }
      end
    elsif input_mode == :raw_line_mode
      if Array === input
        new_op("input", "[[[char]]]"){ to_lazy_list(input.map{|a| lines(str_to_lazy_list(a).const) } ) }
      else
        read_input = promise { lines( promise{ read_stdin(input) }) }
        new_op("input", "[[char]]"){ read_input.value }
      end
    else
      value, type, rank = parse_input(inputs)
      new_op(type == EmptyType ? "inputEmpty" : "input", type_and_rank_to_str(type, rank)){ value }
    end
  }

  ir, ir_inds = *to_ir(ast, registers, ast_inds, input_op)
  types=solve_types(ir)
  ranks=solve_ranks(ir, types)

  ir2,ir2_inds = to_ir2(ir, ranks, types, ir_inds)
  ir_cb[ir2, ir2_inds] if ir_cb
  ir3,ir3_ind = to_ir3(ir2, ir2_inds, pp_sep)
  return [ir3, ir3_ind]
end

def run_and_do_io(source,input,pp,hs,ast_cb: nil,ir_cb: nil)
  pp_sep = pp ? "\n" : nil
  if hs
    generate_hs(source, pp_sep)
  else
    ir3, ir3_ind = gen_graph(source, input, pp_sep: pp_sep, ast_cb: ast_cb, ir_cb: ir_cb)
    promises = make_promises(ir3)
    begin
      prints(promises[ir3_ind].value)
    rescue SystemStackError => e
      raise IogiiError.new "Stack Overflow\n(You can increase the limit with the shell command: export RUBY_THREAD_VM_STACK_SIZE=<size in bytes>\nor compile to haskell with -hs to remove the limit)."
    end
  end
end

# main.rb ######################################################################

if i=ARGV.index("--")
  input = ARGV[i+1..-1]
  ARGV[i..-1] = []
else
  input = STDIN
end

if ["-v", "--version"].any?{|option| ARGV.delete(option) }
  puts Version
  exit
end

pretty_print = ["-pp", "--pretty_print"].any?{|option| ARGV.delete(option) }
hs = ["-hs", "--hs"].any?{|option| ARGV.delete(option) }

begin
  raise IogiiError.new "usage: ruby #$0 -v,--version | [-p,--pretty_print] [-hs,--hs] <filename.iog> [-- rawargs*]" if ARGV.size == 0 || ARGV.any?{|a| a[0] == "-" }
  raise IogiiError.new "mustn't give more than one file arg" if ARGV.size > 1
  if ARGV.size == 1
    raise IogiiError.new "file does not exist: %p" % ARGV[0] if !File.file?(ARGV[0])
    program = IO.binread(ARGV[0])
  end
  run_and_do_io(program, input, pretty_print, hs)
rescue IogiiError => e
  STDERR.puts e.message
rescue => e
  STDERR.puts "This is an internal iogii error, please report it!\n".red
  raise e
end