cgen error when trying to pass a generic three levels down

[alexferl]

Describe the bug

Getting a cgen error when trying to run the included code.

Expected Behavior

No cgen error, maybe a relevant error if the code is incorrect?

Current Behavior

v run main.v
cgen error: could not generate string method `main__Edge[int]_str` for type `main__Edge[int]`

Reproduction Steps

module main

struct Empty {}

type Tree[T] = Empty | Root[T]

struct Root[T] {
mut:
    root Node[T]
    size int
}

struct Node[T] {
// works if the following two lines are commented
mut:
    edges []Edge[T]
}

struct Edge[T] {}

fn new[T]() Tree[T] {
    return Tree[T](Root[T]{root: Node[T]{}})
}

fn main() {
    // these two lines works on their own and 
    // actually makes the bottom work if uncommented
    // mut t := Tree[int](Root[int]{root: Node[int]{}})
    // dump(t)

    mut t2 := new[int]()
    dump(t2)
}

Possible Solution

No response

Additional Information/Context

No response

V version

V 0.4.0 efcb15d

Environment details (OS name and version, etc.)

V full version: V 0.4.0 045adb6.efcb15d
OS: macos, macOS, 13.4.1, 22F82
Processor: 12 cpus, 64bit, little endian, Apple M2 Pro

getwd: /Users/alex/dev/radix2
vexe: /opt/homebrew/Cellar/vlang/0.4/libexec/v
vexe mtime: 2023-07-12 22:48:26

vroot: OK, value: /opt/homebrew/Cellar/vlang/0.4/libexec
VMODULES: OK, value: /Users/alex/.vmodules
VTMP: OK, value: /tmp/v_501

Git version: git version 2.39.2 (Apple Git-143)
Git vroot status: weekly.2023.28-13-gefcb15d0
.git/config present: true

CC version: Apple clang version 14.0.3 (clang-1403.0.22.14.1)
thirdparty/tcc status: thirdparty-macos-arm64 a668e5a0

[shove70]

simplify:

module main

struct Root[T] {
    edges []Edge[T]
}

struct Edge[T] {}

fn new[T]() Root[T] {
    return Root[T]{}
}

fn main() {
    t2 := new[int]()
    dump(t2)
}

$ v run a.v
cgen error: could not generate string method `main__Edge[int]_str` for type `main__Edge[int]`

[shove70]

@spytheman I need your assistance 😄

I have found a relatively serious problem, which may be just my cognitive error. However, based on the results of my analysis over the past two days, the problem should exist.

The problem occurs in the concretization of structures with generics:

1. TypeSymbols of generic structures such as ast.GenericInst, kind: .generic_inst are generated by the parser, but only for specific types that appear on the code's literally. For element types of array elements and maps, if no specific types appear on the code's literally, the parser will not generate TypeSymbols(ast.GenericInst, kind: .generic_inst)

2. The builder will concretize the GenericInsts in all TypeSymbols before starting the checker work, and only after completion will the checker start work

3. So when generic structures are used as array elements or map elements, their TypeSymbols will be lost unless specific types are used literally in the code.

Solving this problem can be complex:

1. There is a functional boundary between parsers and checkers, and we definitely cannot let parsers analyze specific types that have not appeared in the code literal

2. Before the checker starts working, thoroughly analyze all missing ast.GenericInst, kind: .generic_inst of the TypeSymbol, and needs to be completed, which requires a lot of work, equivalent to the checker working twice, involving modifications to the overall architecture of the compiler.

3. There is also a compromise and temporary solution: during the checker's work, the TypeSymbol of the generic structure is reset to ast.GenericInst, kind: .generic_inst and re concretized. However, this solution is clumsy and has a huge impact on performance.

This is a portion of the code that follows the third method, which has not been completed yet, but the following code can run successfully:

https://github.com/shove70/v/commit/b134065d738ded7899424bb630fdf327472c56ca (This is just my attempt and I am not planning to submit a PR on this issue at the moment)

module main

struct Root[T] {
    edges []Edge[T]
}

struct Edge[T] {}

fn new[T]() Root[T] {
    return Root[T]{}
}

fn main() {
    // mut t := Root[int]{}
    // dump(t)

    t2 := new[int]()
    dump(t2)    
}

[spytheman]

The builder will concretize the GenericInsts in all TypeSymbols before starting the checker work, and only after completion will the checker start work

That is wrong, the checker does everything, the builder has no business knowing about generics. The builder just orchestrates stages.

[shove70]

pub fn (mut b Builder) middle_stages() ! {
    util.timing_start('CHECK')

    util.timing_start('Checker.generic_insts_to_concrete')
    b.table.generic_insts_to_concrete()
    util.timing_measure('Checker.generic_insts_to_concrete')

    b.checker.check_files(b.parsed_files)
    util.timing_measure('CHECK')
    b.print_warnings_and_errors()
    if b.checker.should_abort {
        return error('too many errors/warnings/notices')
    }
    if b.pref.check_only {
        return error_with_code('stop_after_checker', 8001)
    }
    util.timing_start('TRANSFORM')
    b.transformer.transform_files(b.parsed_files)
    util.timing_measure('TRANSFORM')
    //
    b.table.complete_interface_check()
    if b.pref.skip_unused {
        markused.mark_used(mut b.table, b.pref, b.parsed_files)
    }
    if b.pref.show_callgraph {
        callgraph.show(mut b.table, b.pref, b.parsed_files)
    }
}

[shove70]

Perhaps the translation software cannot accurately express my intention. The key point is not how to expand, but that the parser has missed some TypeSymbols, resulting in the inability to fully expand. I also know that the work being carried out is done by the checker.

// generic struct instantiations to concrete types
pub fn (mut t Table) generic_insts_to_concrete() {

    // --->
    t.find_sym('main.Root[int]') or {
        sym_, idx_ := t.find_sym_and_type_idx('main.Root')
        if idx_ > 0 {
            new_idx := t.register_sym(ast.TypeSymbol{
                kind: .generic_inst
                name: '${sym_.name}[int]'
                cname: '${sym_.cname}_T_int'
                mod: sym_.mod
                info: ast.GenericInst{
                    parent_idx: idx_
                    concrete_types: [new_type(7)]
                }
            })
            println(new_idx)
        }
    }
    // ---> Here: Manually completed the TypeSymbol 'generic_inst' that was missed by the parser
    // The code reported by this issue can run normally

    for mut sym in t.type_symbols {
        if sym.kind == .generic_inst {
            info := sym.info as GenericInst
            parent := t.type_symbols[info.parent_idx]
            if parent.kind == .placeholder {
                sym.kind = .placeholder
                continue
            }
            match parent.info {
...

[shove70]

Manually completed the TypeSymbol kind: .generic_inst that was missed by the parser The code reported by this issue can run normally

[shove70]

module main

struct Root[T] {
    edges map[int]Edge[T]       // Here: Edge[T] is element of a map!
}

struct Edge[T] {
}

fn new[T]() Root[T] {
    return Root[T]{}
}

fn main() {
    t2 := new[int]()
    dump(t2)    
}

The conclusion of my tested yesterday was incorrect, so I redid it. It does present a problem when used as an element of maps. It seems that it will take some time to solve this problem