#!/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

  if !tokens.empty? && tokens[0].str == ","
    input_mode = :raw_mode
    tokens.shift
  elsif !tokens.empty? && tokens[-1].str == "'"
    input_mode = :raw_line_mode
    tokens.pop
  else
    input_mode = :auto_parse_mode
  end

  [tokens, input_mode]
end

# error.rb #####################################################################
$warnings = {}

def warn(msg, from=nil)
  warning = to_location(from) + msg

  # don't do the same warning more than once (since code is parsed multiple times to handle auto input cases in engine/hs code gen
  return if $warnings[warning]
  $warnings[warning] = true

  error_output "WARNING: ".red + warning + "\n"
end

def draw_fns(tokens, nodes)
  positions = []
  code = ""
  tokens.each.with_index{|token|
    positions << (code.size + token.str.size/2)
    code << token.str + " "
  }

  diagram = code.size.times.map{ " "*code.size }
  token_pos = -> t { positions[tokens.index{|token| token.equal?(t) }] }
  nodes.each{|node|
    next if !node.token
    op = lookup_op(node.token.str)
    pos = token_pos[node.token]
    if node.type == :UnmatchedEndBracket || op && op.block && !node.impl
      diagram[0][token_pos[node.token]] = "?"
    elsif op && op.block
      if node.impl
        end_pos = token_pos[nodes[node.impl].token]
        ((end_pos - pos) / 2).times{|i|
          diagram[i][pos+i] = "\\"
          diagram[i][end_pos-i-1] = "/"
        }
      end
    end
  }

  code + "\n" + diagram.take_while{|line|line.strip != ""} * "\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 %p" % 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.4"

# 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 == 0 ? 0 : 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| a.value == 0 ? 0 : b.value == 0 ? a.value : a.value%b.value }
mk_op("^ pow", "int int -> int", '2 3^ -> 8'){|a, b| pow(a, b) }
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| product(a) }

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 don\'t 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("'", 'char literal or <a href="io.html#rawmodes">raw line mode</a>', "'a -> 'a'")
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|
  b.value == 0 ? [a, Null] : 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) }
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.const, a) }
mk_op("h powOf2", "int -> int", "8h -> 256"){|a| pow(2.const, a) }

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}, encoding=#{Encoding.default_external}\""){ str_to_lazy_list(Version + ", ruby#{RUBY_VERSION}, encoding=#{Encoding.default_external}") }
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)

category("internal ops")
mk_op("implicit", "a", vectorize: false)
mk_op("$", "a", vectorize: false)
mk_op("superpad", "[a] -> [a]", promote: false){ raise }
mk_op("_id", "a -> a", vectorize: false){ raise }

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, input_present, 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's 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?
          push[AST.new(t, [], :ArgNode, all_lbs[-1])]
        elsif input_present.value
          nodes << mk_input_node
          push[AST.new(t, [], :ArgNode, nodes.size - 1)]
        else
          push[AST.new(t, [], :ImplicitValue)]
        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, root)
  known_non_matchers = {}

  # repeat this handling one `>,` at a time
  loop {
    loop_ops = [] # list of loop op inds (left to right)
    end_ops = [] # list of end brackets (left to right)
    loop_options = [] # list of end bracket inds loop op of same ind could match (right to left)
    end_options = [] # left to right

    get_loop_ops = -> node, end_options {
      is_unmatched_end_op = nodes[node].type == :UnmatchedEndBracket && !known_non_matchers[node]
      sub_end_options = is_unmatched_end_op ? end_options + [node] : end_options
      nodes[node].args.each{|i| get_loop_ops[i, sub_end_options] }
      if nodes[node].type == :LoopOp && !nodes[node].token.matching_bracket
        loop_ops << node
        loop_options << end_options
      elsif is_unmatched_end_op
        end_ops << node
      end
    }
    get_loop_ops[root, []]
    end_ops.each{|end_op|
      end_options << loop_ops.values_at(*loop_options.size.times.select{|i| loop_options[i].include?(end_op) })
    }

    end_matches = {} # end bracket ind -> loop ind
    loop_matches = {} # loop ind -> end bracket ind

    # greedy first pass to figure out which loop ops are matched (minimal match length though)
    # this guarantees maximum number of matches found
    (loop_ops.size-1).downto(0){|i|
      loop_op = loop_ops[i]
      option = loop_options[i].reverse.find{|e| !end_matches[e] }
      if option
        end_matches[option] = loop_op
        loop_matches[loop_op] = option
      end
    }

    progress = true
    while progress
      progress = false
      # extend each loop op match to a further end bracket when possible
      # does not cause crossings because it starts with leftmost loop op,
      # if a later loop op could extend crossing and earlier one, the earlier one would already have since it is known to have closed between two two points
      loop_ops.size.times{|i|
        loop_op = loop_ops[i]
        option = loop_options[i].find{|e| !end_matches[e] }
        if option && option > loop_matches[loop_op]
          progress = true
          end_matches.delete(loop_matches[loop_op])
          end_matches[option] = loop_op
          loop_matches[loop_op] = option
        end
      }

      # extend each end bracket to match an earlier loop op where possible
      # does not cause crossings because it starts with rightmost end bracket
      end_ops.size.times.reverse_each{|i|
        end_op = end_ops[i]
        option = end_options[i].find{|b| !loop_matches[b] }
        if option && option < end_matches[end_op]
          progress = true
          loop_matches.delete(end_matches[end_op])
          loop_matches[option] = end_op
          end_matches[end_op] = option
        end
      }
    end

    last_unmatched_comma_end_bracket = end_ops.reverse.find{|end_ind|
      end_op = nodes[end_ind]
      end_op.type == :UnmatchedEndBracket && end_op.token.str[","] && !known_non_matchers[end_ind]
    }
    if last_unmatched_comma_end_bracket
      end_node = nodes[last_unmatched_comma_end_bracket]
      comma_count = end_node.token.str.count(",")
      current_match = end_matches[last_unmatched_comma_end_bracket]
      if !current_match
        raise IogiiError.new "found >, but this end bracket already didn't match a loop op so that `,` is unnecessary", end_node
      end
      end_op = end_ops.index(last_unmatched_comma_end_bracket)
      new_options = end_options[end_op][end_options[end_op].index(current_match) + 1..-1]
      if comma_count > new_options.size # set implicit
        known_non_matchers[last_unmatched_comma_end_bracket] = true
      else # move match
        new_match = new_options[comma_count-1]
        end_node.type = :MatchedEndBracket
        end_node.token.matching_bracket = nodes[new_match].token
        nodes[new_match].token.matching_bracket = end_node.token
      end
    else # no more comma end brackets to handle, this is final matching configuration
      loop_matches.each{|loop_ind,end_ind|
        nodes[end_ind].type = :MatchedEndBracket
        nodes[end_ind].token.matching_bracket = nodes[loop_ind].token
        nodes[loop_ind].token.matching_bracket = nodes[end_ind].token
      }
      break
    end
  }
end

def parse_main(tokens, input_present)
  registers = get_var_ids_set(tokens)
  tokens = split_ids(tokens, registers)
  tokens = tokenize_data(tokens, registers)
  nodes, stack, deleted, nimplicits, lbs = build_tree(tokens, registers, input_present)
  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(input_present.value ? "input" : "implicit", :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, input_present)
  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, input_present, last_unmatched)

  if last_unmatched
    # this is a bit hacky, but do it again since last_unmatched is an index to the ast which can change from when it was calculated. example program that requires this:
    # i>e>5>
    last_unmatched = nodes.reverse_each.find{|n| n.type == :UnmatchedEndBracket }
    nodes, stack, deleted, nimplicits, lbs = build_tree(tokens, registers, input_present, last_unmatched)
  end

  raise IogiiError.new("unterminated function (stack is never rid of extra values again, functions can only return one value)\n" + draw_fns(tokens, nodes), 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" + draw_fns(tokens, nodes), 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.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)

      rep_zip_level = [e, 0].max # max is because could be < 0 for special reps
      arg_ranks[ind] += [nreps, 0].max

      nreps.times{|time|
        ir2_nodes << IR2.new(Ops["repeat"].ways[0], [a], rep_zip_level, t, r+time+1)
        a = ir2_nodes.size - 1
      }
      a
    }

    # use identity op to promote type of nil when needed (this lets the engine know correct arg ranks for truthy/default values) (ruby lazylib cheats and uses dynamic rank)
    if way.vectorize # no cases of non vectorizing args taking [a] type
      op_rank = way.mod

      used_ranks = arg_ranks.zip(way.arg_ranks).map{|arg_rank, op_arg_rank|
        arg_rank - zip_level - ~op_arg_rank
      }

      used_ranks.zip(way.arg_types, way.arg_ranks, arg_types, arg_ranks, 0..).each{|used_rank, op_arg_type, op_arg_rank, arg_type, arg_rank, i|
        next if concrete_rank(op_arg_type)
        next if used_rank >= op_rank
        if arg_type == EmptyType
          ir2_nodes << IR2.new(Ops["_id"].ways[0], [args[i]], 0, EmptyType,
            ~op_arg_rank + op_rank + zip_level)
          args[i] = ir2_nodes.size - 1
        else
          # this is ok actually since it will happy due to adjust_ab_types (but empty type is never deficient so never adjusted)
#           raise "internal type error, deficient non empty type"
        end
      }
    end

    # 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
      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(ir3)
  promises = ir3.map{|node|
    arg_types = node.args.map{|a|ir3[a].type}

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

    promise{
      args = node.args.map{|a| promises[a] }
      if node.way.name == "_id"
        args[0].value
      else
        zipn(node.zip_level, args, impl)
      end
    }
  }
  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 product(a, ans=1)
  if a.empty
    ans
  elsif a.value[0].value == 0
    0
  else
    product(a.value[1], a.value[0].value*ans)
  end
end

def pow(a,b)
  # manually implement this op so that it is consistent and doesn't return rationals / overflow
  return 1 if b.value == 0
  a,b = a.value,b.value
  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

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)
  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)
  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.value+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.const)
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

# to_engine.rb #################################################################
def to_value(a)
  return "(S #{a.value})" unless Array===a.value
  sofar="(L ["
  first=true
  until a.empty
    sofar << "," if !first
    first = false
    sofar << to_value(a.value[0])
    a = a.value[1]
  end
  sofar << "])"
  sofar
end

def outputn s
  output s
  output "\n" if s[-1] != "\n"
end

def to_engine(source, pp_sep)
  outputn to_eager_str(Ops["version"].ways[0].impl.call)

  _, input_mode = lex(source)

  case input_mode
  when :raw_mode
    possible_input_formats = ["a",["a","b"]]
    finish = "rawInputSelector"
    input = "rawInput"
  when :raw_line_mode
    possible_input_formats = ["a\nb",["a\nb","a\nb"]]
    finish = "rawLineInputSelector"
    input = "rawLineInput"
  else
    if !does_source_use_input(source)
      possible_input_formats = [""]
      finish = nil
      input = "undefined"
    else
      possible_input_formats = ["1","1 1","1 1\n1",["1 1\n1","1 1\n1"],"a","a\nb",["a\nb","a\nb"],""]
      finish = "autoInputSelector"
      input = "input"
    end
  end

  output_inds = []
  offset = 0
  possible_input_formats.each.with_index{|fake_input, i|
    begin
      ir3, ir3_ind = gen_graph(source, fake_input, pp_sep: pp_sep)
      to_engine_main(ir3,offset,input)
      output_inds << ir3_ind + offset
      offset += ir3.size
    rescue IogiiError => e
      outputn "Data #{to_value(str_to_lazy_list(e.message).const)} \"[char]\""
      outputn "Op \"error\" [#{offset}] 0 \"int\""
      output_inds << offset + 1
      offset += 2
    end
  }

  outputn "Op #{finish.inspect} #{output_inds.inspect} 0 \"\"" if finish

end

def to_engine_main(ir3, offset, input)
  ir3.each{|node|
    if node.way.name == "data"
      outputn "Data #{to_value(node.way.impl.call.const)} #{type_and_rank_to_str(node.type,node.rank).inspect}"
    else
      name = node.way.name
      name = input if name == "input"

      outputn "Op #{name.inspect} #{node.args.map{|i|i+offset}.inspect} #{node.zip_level} #{type_and_rank_to_str(node.type,node.rank).inspect}"
    end
  }
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

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

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

TestUnicodeChar = [1000].pack('U')
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 = Encoding::ISO8859_1
  def int_to_char(i)
    (i%256).chr
  end
end

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

  if input_mode == :auto_parse_mode
    inputs = promise { read_inputs(input) }
    input_present = promise { !!inputs.value }
  else
    input_present = promise { true }
  end

  ast, ast_inds, registers = *parse_main(tokens, promise{ $input_checked = true; input_present.value })

  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.value)
      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,engine,ast_cb: nil,ir_cb: nil)
  pp_sep = pp ? "\n" : nil
  if engine
    to_engine(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 use the engine 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 = ["-p", "--pretty_print"].any?{|option| ARGV.delete(option) }
engine = ["-e", "--engine"].any?{|option| ARGV.delete(option) }

def usage
  raise IogiiError.new "usage: ruby #$0 -v,--version | [-p,--pretty_print] [-e,--engine] <filename.iog> [-- rawargs*]"
end

begin
  usage if ARGV.size == 0

  unknown_options = ARGV.select{|a| a[0] == "-" }
  if !unknown_options.empty?
    STDERR.puts "unknown options: " + unknown_options*" "
    usage
  end

  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, engine)
rescue IogiiError => e
  STDERR.puts e.message
  exit(1)
rescue => e
  STDERR.puts "This is an internal iogii error, please report it!\n".red
  raise e
end