sort_type.luau

-- The equality operator `==` is really strict with unions and intersections,
-- where the order of their components needs to be the same.
type function sort_type(input: type)
    local input_tag = input.tag

    if input_tag == "union" or input_tag == "intersection" then
        local components = input:components()

        table.sort(components, function(a: type, b: type): boolean
            local a_tag, b_tag = a.tag, b.tag

            return 
                if a_tag ~= b_tag then a_tag < b_tag
                elseif a_tag == "table" or a_tag == "union" or a_tag == "intersection" then Stringify(a) > Stringify(b)
                elseif a_tag ~= "singleton" then false
                else (a:value() :: any) < (b:value() :: any)
        end)

        for idx, component in components do
            components[idx] = sort_type(component)
        end

        return (if input_tag == "union" then union_from_components else intersection_from_components)(components)

    elseif input_tag == "table" then
        for key, value in input:properties() do
            local value_read, value_write = value.read, value.write

            if value_read == value_write then
                input:setproperty(key, sort_type(value_read))
            else
                input:setreadproperty(key, sort_type(value_read))
                input:setwriteproperty(key, sort_type(value_write))
            end
        end

        local indexer = input:indexer()
        if indexer then
            input:setindexer(sort_type(indexer.index), sort_type(indexer.readresult))
        end

        return input

    elseif input_tag == "negation" then
        return types.negationof(sort_type(input:inner()))

    else
        return input
    end
end

type function stringify_table(
    input: typeof(types.singleton(nil)), nestedness: number,
    pre_padding: string?, post_padding: string?
)
    local properties = input:properties()
    local indexer = input:indexer()

    if table_is_empty(properties, indexer) then return "{ }" end

    local next_nestedness = nestedness + 1

    local outer_padding = string.rep("   ", nestedness - 1)
    local padding = outer_padding .. "    "

    local stringified = `{pre_padding or outer_padding}\{`

    -- Sorts the table keys so its stringified representation 
    -- to ensure stringification is deterministic.
    local keys = {}
    for key in properties do table.insert(keys, key) end
    table.sort(keys, function(a, b) return tostring(a) > tostring(b) end)

    for _, key in keys do
        local value = properties[key]

        local key_value = if key.tag == "singleton" then key:value() else input

        local stringified_key =
            if type(key_value) == "string" then key_value
            else `[{stringify_main(key, next_nestedness, "", padding)}]`

        local value_read, value_write = value.read, value.write

        if value_read == value_write then
            stringified ..= `\n{padding}{stringified_key}: {stringify_main(value_read, next_nestedness)}`

        else
            if value_read then
                stringified ..= `\n{padding}read {stringified_key}: {stringify_main(value_read, next_nestedness)}`
            end
            if value_write then
                stringified ..= `\n{padding}write {stringified_key}: {stringify_main(value_write, next_nestedness)}`
            end
        end
    end

    if indexer then
        local indexer_index = indexer.index
        local indexer_index_value = if indexer_index.tag == "singleton" then indexer_index:value() else input

        local stringified_indexer_index =
            if type(indexer_index_value) == "string" then indexer_index_value
            else `[{stringify_main(indexer_index, next_nestedness, "", padding)}]`

        stringified ..= `\n{padding}{stringified_indexer_index}: {stringify_main(indexer.readresult, next_nestedness)}`
    end

    return stringified .. `\n{post_padding or outer_padding}}`
end

type function stringify_components(
    components: { [number]: type },
    concatenator: string
)
    for idx, component in components do
        local component_tag = component.tag

        if component_tag == "union" then
            components[idx] = `({stringify_components(component:components(), " | ")})` :: any

        elseif component_tag == "intersection" then
            components[idx] = `({stringify_components(component:components(), " & ")})` :: any

        else
            components[idx] = stringify_main(component, 1)
        end
    end

    return table.concat(components, concatenator)
end

type function stringify_function(input: typeof(types.newfunction()))
    local args = input:parameters()
    local args_head, args_tail = args.head, args.tail

    local stringified_args: string
    if args_head then
        stringified_args = ""

        local args_head_len = #args_head
        for idx = 1, args_head_len - 1 do
            stringified_args ..= `{Stringify(args_head[idx])}, `
        end
        stringified_args ..= `{Stringify(args_head[args_head_len])}`

        if args_tail then
            local args_tail_tag = args_tail.tag
            if args_tail_tag == "union" or args_tail_tag == "intersection" then
                stringified_args ..= `, ...({Stringify(args_tail)}))`
            else
                stringified_args ..= `, ...{Stringify(args_tail)})`
            end
        end
    elseif args_tail then
        local args_tail_tag = args_tail.tag
        if args_tail_tag == "union" or args_tail_tag == "intersection" then
            stringified_args = `...({Stringify(args_tail)})`
        else
            stringified_args = `...{Stringify(args_tail)}`
        end
    end

    local returns = input:returns()
    local returns_head, returns_tail = returns.head, returns.tail

    local returns_head_len: number
    local stringified_returns: string
    if returns_head then
        stringified_returns = ""

        returns_head_len = #returns_head
        for idx = 1, returns_head_len - 1 do
            stringified_returns ..= `{Stringify(returns_head[idx])}, `
        end
        stringified_returns ..= `{Stringify(returns_head[returns_head_len])}`

        if returns_tail then
            local returns_tail_tag = returns_tail.tag
            if returns_tail_tag == "union" or returns_tail_tag == "intersection" then
                stringified_returns ..= `, ...({Stringify(returns_tail)}))`
            else
                stringified_returns ..= `, ...{Stringify(returns_tail)})`
            end
        end

    elseif returns_tail then
        local returns_tail_tag = returns_tail.tag
        if returns_tail_tag == "union" or returns_tail_tag == "intersection" then
            stringified_returns = `...({Stringify(returns_tail)})`
        else
            stringified_returns = `...{Stringify(returns_tail)}`
        end
    end

    local stringified_returns = 
        if returns_tail or (returns_head and returns_head_len >= 2) then `({stringified_returns})`
        else stringified_returns

    return `({stringified_args}) -> {stringified_returns}`
end

type function stringify_main(
    input: type, nestedness: number,
    pre_padding: string?, post_padding: string?
)
    local input_tag = input.tag

    if input_tag == "negation" then
        local input_inner = input:inner()
        local input_inner_tag = input_inner.tag
        return
            if (
                input_inner_tag == "union" or input_inner_tag == "intersection"
            ) then `~({stringify_main(input:inner(), nestedness)})`
            else `~{stringify_main(input:inner(), nestedness)}`
    end

    if input_tag == "union" then return stringify_components(input:components(), " | ")
    elseif input_tag == "intersection" then return stringify_components(input:components(), " & ")
    elseif input_tag == "table" then return stringify_table(input, nestedness, pre_padding, post_padding)
    elseif input_tag == "function" then return stringify_function(input)
    elseif input_tag == "unknown" then return "unknown"
    elseif input_tag == "never" then return "never"
    elseif input_tag == "any" then return "any"
    elseif input_tag == "boolean" then return "boolean"
    elseif input_tag == "number" then return "number"
    elseif input_tag == "string" then return "string" end

    local input = if input_tag == "singleton" then input:value() else input
    local input_type = type(input)
    
    return
        if input_type == "string" then `"{input}"`
        else tostring(input) 
end