bug: generic structs where generic is bounded to some trait fails on type deduction to compile when implemented #2995

taco-paco · 2023-05-01T09:15:23Z

Bug Report

Cairo version:

1.0.0-alpha.7

Current behavior:

If as in code below one doesn't provide TCopy and GCopy as here ... of Copy<B<T, G>> compiler will crash trying to deduce possible implementations of Copy trait
Generic structs where generic is bounded to some trait fails to compile when one wants to implement any trait.

Expected behavior:

Compiles succesfully. Also would be great to implement following rust's RFC.

Steps to reproduce:

Compile code below.

Related code:

trait Trait<T> {}

struct B<T, G, impl GTriat: Trait<G>> {
    t: T,
    g: G,
}

impl BCopy<T, G, impl GTriat: Trait<G>> of Copy<B<T, G>>;

initially stubmled upon trying to compile this:

struct A<T> {
    a: T, 
}

impl ACopy<T, impl TCopy: Copy<T>> of Copy<A<T>>;
impl ADrop<T, impl TDrop: Drop<T>> of Drop<A<T>>;

#[derive(Copy)]
struct C {
    c: felt252
}

struct B<T, G, impl GCopy: Copy<G>, impl TCopy: Copy<T>> {
    b: T,
    g: G,
}

impl BCopy<T, G, impl GCopy: Copy<G>, impl TCopy: Copy<T>> of Copy<B<T, G>>;

Other information:

thread 'main' panicked at 'Internal error, cycle detected:

DatabaseKeyIndex { group_index: 4, query_index: 74, key_index: 0 }
DatabaseKeyIndex { group_index: 4, query_index: 84, key_index: 0 }
DatabaseKeyIndex { group_index: 4, query_index: 78, key_index: 0 }
', /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:48
stack backtrace:
   0: rust_begin_unwind
             at /rustc/9eb3afe9ebe9c7d2b84b71002d44f4a0edac95e0/library/std/src/panicking.rs:575:5
   1: core::panicking::panic_fmt
             at /rustc/9eb3afe9ebe9c7d2b84b71002d44f4a0edac95e0/library/core/src/panicking.rs:64:14
   2: core::panicking::panic_display
             at /rustc/9eb3afe9ebe9c7d2b84b71002d44f4a0edac95e0/library/core/src/panicking.rs:147:5
   3: salsa::QueryTable<Q>::get::{{closure}}
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:48
   4: core::result::Result<T,E>::unwrap_or_else
             at /rustc/9eb3afe9ebe9c7d2b84b71002d44f4a0edac95e0/library/core/src/result.rs:1503:23
   5: salsa::QueryTable<Q>::get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:9
   6: <DB as cairo_lang_semantic::db::SemanticGroup>::impl_def_concrete_trait::__shim
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
   7: <DB as cairo_lang_semantic::db::SemanticGroup>::impl_def_concrete_trait
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
   8: cairo_lang_semantic::items::imp::UninferredImpl::concrete_trait
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/items/imp.rs:713:49
   9: cairo_lang_semantic::items::imp::module_impl_ids_for_trait_info
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/items/imp.rs:620:33
  10: <cairo_lang_semantic::db::ModuleImplIdsForTraitInfoQuery as salsa::plumbing::QueryFunction>::execute
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:414:21
  11: salsa::derived::slot::Slot<Q,MP>::read_upgrade::{{closure}}
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:218:13
  12: salsa::runtime::Runtime::execute_query_implementation
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/runtime.rs:330:21
  13: salsa::derived::slot::Slot<Q,MP>::read_upgrade
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:215:26
  14: salsa::derived::slot::Slot<Q,MP>::read
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:148:9
  15: <salsa::derived::DerivedStorage<Q,MP> as salsa::plumbing::QueryStorageOps<Q>>::try_fetch
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived.rs:170:13
  16: salsa::QueryTable<Q>::try_get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:494:9
  17: salsa::QueryTable<Q>::get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:9
  18: <DB as cairo_lang_semantic::db::SemanticGroup>::module_impl_ids_for_trait_info::__shim
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  19: <DB as cairo_lang_semantic::db::SemanticGroup>::module_impl_ids_for_trait_info
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  20: cairo_lang_semantic::items::imp::find_impls_at_module
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/items/imp.rs:675:28
  21: cairo_lang_semantic::items::imp::find_possible_impls_at_context
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/items/imp.rs:760:16
  22: cairo_lang_semantic::expr::inference::Inference::try_to_resume_impl_var
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/expr/inference.rs:957:26
  23: cairo_lang_semantic::expr::inference::Inference::relax_impl_var
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/expr/inference.rs:987:9
  24: cairo_lang_semantic::expr::inference::Inference::new_impl_var
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/expr/inference.rs:248:9
  25: cairo_lang_semantic::expr::inference::Inference::infer_generic_arg
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/expr/inference.rs:867:69
  26: cairo_lang_semantic::resolve::Resolver::resolve_generic_arg
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:772:24
  27: cairo_lang_semantic::resolve::Resolver::resolve_generic_args
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:749:31
  28: cairo_lang_semantic::resolve::Resolver::specialize_type
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:707:13
  29: cairo_lang_semantic::resolve::Resolver::specialize_generic_module_item
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:481:44
  30: cairo_lang_semantic::resolve::Resolver::resolve_next_concrete
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:370:20
  31: cairo_lang_semantic::resolve::Resolver::resolve_concrete_path
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:196:20
  32: cairo_lang_semantic::types::maybe_resolve_type
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/types.rs:288:19
  33: cairo_lang_semantic::types::resolve_type
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/types.rs:276:5
  34: cairo_lang_semantic::resolve::Resolver::resolve_generic_arg
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:786:26
  35: cairo_lang_semantic::resolve::Resolver::resolve_generic_args
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:749:31
  36: cairo_lang_semantic::resolve::Resolver::specialize_trait
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:645:13
  37: cairo_lang_semantic::resolve::Resolver::specialize_generic_module_item
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:525:45
  38: cairo_lang_semantic::resolve::Resolver::resolve_next_concrete
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:370:20
  39: cairo_lang_semantic::resolve::Resolver::resolve_concrete_path
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/resolve/mod.rs:196:20
  40: cairo_lang_semantic::items::imp::priv_impl_declaration_data_inner
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/items/imp.rs:273:9
  41: cairo_lang_semantic::items::imp::priv_impl_declaration_data
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/items/imp.rs:239:5
  42: <cairo_lang_semantic::db::PrivImplDeclarationDataQuery as salsa::plumbing::QueryFunction>::execute
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:361:21
  43: salsa::derived::slot::Slot<Q,MP>::read_upgrade::{{closure}}
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:218:13
  44: salsa::runtime::Runtime::execute_query_implementation
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/runtime.rs:330:21
  45: salsa::derived::slot::Slot<Q,MP>::read_upgrade
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:215:26
  46: salsa::derived::slot::Slot<Q,MP>::read
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:148:9
  47: <salsa::derived::DerivedStorage<Q,MP> as salsa::plumbing::QueryStorageOps<Q>>::try_fetch
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived.rs:170:13
  48: salsa::QueryTable<Q>::try_get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:494:9
  49: salsa::QueryTable<Q>::get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:9
  50: <DB as cairo_lang_semantic::db::SemanticGroup>::priv_impl_declaration_data::__shim
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  51: <DB as cairo_lang_semantic::db::SemanticGroup>::priv_impl_declaration_data
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  52: cairo_lang_semantic::items::imp::impl_semantic_declaration_diagnostics
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/items/imp.rs:176:5
  53: <cairo_lang_semantic::db::ImplSemanticDeclarationDiagnosticsQuery as salsa::plumbing::QueryFunction>::execute
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:368:21
  54: salsa::derived::slot::Slot<Q,MP>::read_upgrade::{{closure}}
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:218:13
  55: salsa::runtime::Runtime::execute_query_implementation
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/runtime.rs:330:21
  56: salsa::derived::slot::Slot<Q,MP>::read_upgrade
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:215:26
  57: salsa::derived::slot::Slot<Q,MP>::read
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:148:9
  58: <salsa::derived::DerivedStorage<Q,MP> as salsa::plumbing::QueryStorageOps<Q>>::try_fetch
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived.rs:170:13
  59: salsa::QueryTable<Q>::try_get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:494:9
  60: salsa::QueryTable<Q>::get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:9
  61: <DB as cairo_lang_semantic::db::SemanticGroup>::impl_semantic_declaration_diagnostics::__shim
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  62: <DB as cairo_lang_semantic::db::SemanticGroup>::impl_semantic_declaration_diagnostics
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  63: cairo_lang_semantic::db::module_semantic_diagnostics
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:863:36
  64: <cairo_lang_semantic::db::ModuleSemanticDiagnosticsQuery as salsa::plumbing::QueryFunction>::execute
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:761:8
  65: salsa::derived::slot::Slot<Q,MP>::read_upgrade::{{closure}}
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:218:13
  66: salsa::runtime::Runtime::execute_query_implementation
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/runtime.rs:330:21
  67: salsa::derived::slot::Slot<Q,MP>::read_upgrade
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:215:26
  68: salsa::derived::slot::Slot<Q,MP>::read
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived/slot.rs:148:9
  69: <salsa::derived::DerivedStorage<Q,MP> as salsa::plumbing::QueryStorageOps<Q>>::try_fetch
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/derived.rs:170:13
  70: salsa::QueryTable<Q>::try_get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:494:9
  71: salsa::QueryTable<Q>::get
             at /Users/edwin/.cargo/registry/src/github.jparrowsec.cn-1ecc6299db9ec823/salsa-0.16.1/src/lib.rs:490:9
  72: <DB as cairo_lang_semantic::db::SemanticGroup>::module_semantic_diagnostics::__shim
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  73: <DB as cairo_lang_semantic::db::SemanticGroup>::module_semantic_diagnostics
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-semantic/src/db.rs:51:1
  74: cairo_lang_compiler::diagnostics::DiagnosticsReporter::check
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-compiler/src/diagnostics.rs:113:35
  75: cairo_run::main
             at /Users/edwin/Documents/projects/cairo/cairo/crates/cairo-lang-runner/src/cli.rs:43:8
  76: core::ops::function::FnOnce::call_once
             at /rustc/9eb3afe9ebe9c7d2b84b71002d44f4a0edac95e0/library/core/src/ops/function.rs:250:5

The text was updated successfully, but these errors were encountered:

spapinistarkware · 2023-05-02T10:56:06Z

It fails on a cycle by any chance?
This has been known for a while, and it's because the semantic model of the generic params is on the encompassing item...
Need to do some separation there..

taco-paco · 2023-05-02T10:58:30Z

It fails on a cycle by any chance?

Yes. My bad forgot to attach stacktrace

taco-paco · 2023-05-02T14:00:57Z

Stacktrace attached

taco-paco · 2023-05-15T04:18:19Z

@spapinistarkware would like to take this issue.
Fix idea would be adding a declaration for impl like it is done for functions currently. That's why this code doesn't cycle because generic parameters inside priv_free_function_body_data fetched from priv_free_function_declaration_data. So idea is to have the same for impl. So ImplDeclaration: "impl" & "path::with::possible::generics<...>"
This will fix all issues with cycle on type deduction, cycling in impl aliases + cycle in impl + will have a basement for feature of impl without traits

fn trtr<T, G, impl GTrait: Trait<G>, impl TDrop: Drop<T>, impl GDrop: Drop<G>>(t: T, g: G) {

}

fn asd<T, G, impl GTrait: Trait<G>, impl TDrop: Drop<T>, impl GDrop: Drop<G>>(t: T, g: G) {
    asd::<T, G, GTrait, TDrop, GDrop>(t, g);
}

spapinistarkware · 2023-05-15T05:04:25Z

@gilbens-starkware is working on this.
The solution he is doing is making a separate query for the semantic model of a generic param, that doesn't depend on the item semantic model.

Separating impl to declaration is less good IMO, since you can also have the cycle in the generics themeselves.

taco-paco · 2023-05-15T05:20:09Z

Hmm, yeah, I think your solution is better. But would you say that having ItemImplDeclaration is unnecessary at this point? I think it would be consistent with functions model + would be an entry point for all ItemImpl, ItemImplAlias and ItemImplAnonymous(impl without trait)

spapinistarkware · 2023-05-15T05:22:49Z

Im general, the declaration separation is important in order to make other functions still compile even if the body of this item doesn't.
That means the a declaration is everything another item needs to know about this one.
Thus, the declaration of an impl is "impl Name of ConcreteTrait". So, there is already a separation of this in the code.

taco-paco · 2023-05-15T05:25:48Z

Makes sense

gilbens-starkware · 2023-07-16T11:30:44Z

Solved in #3360.

taco-paco added the bug Something isn't working label May 1, 2023

This was referenced May 4, 2023

bug: impl alias leads to a cycle and compiler crash #3037

Closed

Advanced Cairo: Supertraits - Require a functionnality in another trait cairo-book/cairo-book#121

Closed

taco-paco changed the title ~~bug: generic structs where generic is bounded to some trait fails to compile when implemented~~ bug: generic structs where generic is bounded to some trait fails on type deduction to compile when implemented May 12, 2023

taco-paco mentioned this issue May 12, 2023

bug: generic structs where generic is bounded to some trait fails with cycle if implementations specified #3133

Closed

gilbens-starkware closed this as completed Jul 16, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

bug: generic structs where generic is bounded to some trait fails on type deduction to compile when implemented #2995

bug: generic structs where generic is bounded to some trait fails on type deduction to compile when implemented #2995

taco-paco commented May 1, 2023 •

edited

Loading

spapinistarkware commented May 2, 2023

taco-paco commented May 2, 2023 •

edited

Loading

taco-paco commented May 2, 2023

taco-paco commented May 15, 2023 •

edited

Loading

spapinistarkware commented May 15, 2023

taco-paco commented May 15, 2023 •

edited

Loading

spapinistarkware commented May 15, 2023

taco-paco commented May 15, 2023

gilbens-starkware commented Jul 16, 2023

bug: generic structs where generic is bounded to some trait fails on type deduction to compile when implemented #2995

bug: generic structs where generic is bounded to some trait fails on type deduction to compile when implemented #2995

Comments

taco-paco commented May 1, 2023 • edited Loading

Bug Report

spapinistarkware commented May 2, 2023

taco-paco commented May 2, 2023 • edited Loading

taco-paco commented May 2, 2023

taco-paco commented May 15, 2023 • edited Loading

spapinistarkware commented May 15, 2023

taco-paco commented May 15, 2023 • edited Loading

spapinistarkware commented May 15, 2023

taco-paco commented May 15, 2023

gilbens-starkware commented Jul 16, 2023

taco-paco commented May 1, 2023 •

edited

Loading

taco-paco commented May 2, 2023 •

edited

Loading

taco-paco commented May 15, 2023 •

edited

Loading

taco-paco commented May 15, 2023 •

edited

Loading