Add support for Slices #849

philberty · 2022-01-04T11:52:48Z

We need to support slices to be able to compile the goal test case #682

see:

https://doc.rust-lang.org/book/ch04-03-slices.html
https://github.com/bminor/binutils-gdb/blob/79541a6d9220e800ebc5278594105982d6e1d80c/gdb/rust-lang.c#L157-L166
https://github.com/bminor/binutils-gdb/blob/79541a6d9220e800ebc5278594105982d6e1d80c/gdb/rust-lang.c#L299-L312

let a = [1, 2, 3, 4, 5];

let slice = &a[1..3];

951: Add name resolution to slices r=philberty a=philberty This is the first part to support slices where we complete the name resolution of the SliceType with its element as well as the range expressions used in construction. This patch also includes separation of the implementation from the headers to try and incrementally improve build speed. Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

974: Add support for ranges and index lang items along with the TyTy::SliceType r=philberty a=philberty This PR contains more code to begin supporting Slices which requires support for more intrinsic, range and index lang items. More work is needed to support slices such as the const_ptr lang item and the offset intrinsic but this is a big PR already and adds support for more lang items along the way. Fixes #975 Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

1003: Add more intrinsics and refactor how we implement them r=philberty a=philberty This patch series implements: 1. offset 2. size_of 3. unreachable 4. abort It removes the GCC wrapper mappings to make them much easier to implement. It also demonstrates in single commits the implementation of each of these intrinsic to make it easy to follow in how we implement them. Addresses #658 #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

1007: Add missing canonicalization of slices and raw pointer types r=philberty a=philberty This is part of my patch series for slices. This adds the missing visitors for name canonicalization. More information in the patch, once we get slice support in we need to start taking advantage of `@dkm's` HIR visitor refactoring to avoid these issues with missing visitors making simple bugs hard to track down. Fixes #1005 1008: Add const_ptr lang item mappings r=philberty a=philberty In order to support slices, we need to be able to parse and contain mappings for the const_ptr lang item. We do not need to do any special handling of this lang item yet but this adds the mappings so when we hit it we do not output an unknown lang item error. Addresses #849 1009: Add missing type resolution to slices and arrays r=philberty a=philberty This adds in the missing type resolution for slices and generic slices and arrays. Since Arrays and Slices are both covariant types just like references and pointers for example they need to handle recursive substitutions where their element type might be a generic type that can bind substitution parameters such as functions and ADT's. Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

1008: Add const_ptr lang item mappings r=philberty a=philberty In order to support slices, we need to be able to parse and contain mappings for the const_ptr lang item. We do not need to do any special handling of this lang item yet but this adds the mappings so when we hit it we do not output an unknown lang item error. Addresses #849 1009: Add missing type resolution to slices and arrays r=philberty a=philberty This adds in the missing type resolution for slices and generic slices and arrays. Since Arrays and Slices are both covariant types just like references and pointers for example they need to handle recursive substitutions where their element type might be a generic type that can bind substitution parameters such as functions and ADT's. Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

This type must respect the layout of the FatPtr type in libcore. Rust implements slices using Rustc types in libcore and uses a neat trick. The slice is generated into the FatPtr which contains the pointer and length of the slice. This is then placed into a union called Repr which has 3 variants a mutable and immutable pointer to the FatPtr and a final variant which is the raw FatPtr. This means we can use unsafe access to the union to gain a pointer to the FatPtr. Addresses #849

Addresses #849

1016: Add missing HIR lowering for SliceTypes r=philberty a=philberty Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

This type must respect the layout of the FatPtr type in libcore. Rust implements slices using Rustc types in libcore and uses a neat trick. The slice is generated into the FatPtr which contains the pointer and length of the slice. This is then placed into a union called Repr which has 3 variants a mutable and immutable pointer to the FatPtr and a final variant which is the raw FatPtr. This means we can use unsafe access to the union to gain a pointer to the FatPtr. Addresses #849

1015: Add code generation for the slice type r=philberty a=philberty This type must respect the layout of the FatPtr type in libcore. Rust implements slices using Rustc types in libcore and uses a neat trick. Addresses #849 1018: builtin-macros: Add more documentation for defining builtins r=CohenArthur a=CohenArthur `@mvvsmk` you might find this a little more clear. Sorry about the confusion! Co-authored-by: Philip Herron <philip.herron@embecosm.com> Co-authored-by: Arthur Cohen <arthur.cohen@embecosm.com>

1030: Rewrite our unconstrained type-param error checking r=philberty a=philberty This is a series of patches that were all required to fix this issue. We now take advantage of our substitutions abstractions and traits so that our TypeBoundPredicate's which form the basis of our HRTB code I think this class is almost akin to rustc existential-trait-references. This now reuses the same code path to give us the same error checking for generics as we get with ADT's, functions etc. With this refactoring in place we can then reuse the abstractions to map the ID's from the used arguments in the type-bound-predicate, the impl block type substation mappings and the self type itself. There are quite a few cases to handle and our testsuite picked up all the regressions so no behaviour of our existing test-cases have changed now. See each commit for more detailed information. Fixes #1019 Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

1022: attribute expansion: Fix spurious stripping of tail expression r=CohenArthur a=CohenArthur This commit fixes the issue reported in #391, but highlights another one, which will be reported. Closes #391 1033: Fix bad copy-paste in can equal interface for pointer types r=philberty a=philberty When we perform method resolution we check if the self arguments can be matched. Here the bug was that pointer types had a bad vistitor and only could ever match reference types which is wrong and was a copy paste error. Fixes #1031 Addresses #849 Co-authored-by: Arthur Cohen <arthur.cohen@embecosm.com> Co-authored-by: Philip Herron <philip.herron@embecosm.com>

1037: Support placeholders becoming slices r=philberty a=philberty When we setup trait-impls the type-alias are allowed to become any type this interface was missing a visitor. We also need to support constraining type-parameters behind slices. The get_root interface is currently unsafe, it needs a flag for allowing unsized and for keeping a map of adjustments along the way. This will be added down the line when we support unsized method resolution. Fixes #1034 Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

In order to support slices, we end up with an operator overload call of: ``` impl<T, I> Index<I> for [T] where I: SliceIndex<[T]>, { type Output = I::Output; fn index(&self, index: I) -> &I::Output { index.index(self) } } ``` So this means the self in this case is an array[T,capacity] and the index parameter is of type Range<usize>. In order to actually call this method which has a self parameter of [T] we need to be able to 'unsize' the array into a slice. Addresses #849

1045: Add initial support for unsized method resolution r=philberty a=philberty In order to support slices, we end up with an operator overload call of: ``` impl<T, I> Index<I> for [T] where I: SliceIndex<[T]>, { type Output = I::Output; fn index(&self, index: I) -> &I::Output { index.index(self) } } ``` So this means the self, in this case, is an array[T,capacity] and the index parameter is of type Range<usize>. In order to actually call this method which has a self parameter of [T] we need to be able to 'unsize' the array into a slice. Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

The legacy mangling scheme needs to convert the canonical path containing * for pointers and the [] brackets representing slices into: * = $BP$ [ = $u5b$ ] = $u5d$ These symbols are not allowed in asm symbols. Addresses #849

This was a typo when unsized method resolution was added, where the adjustment was wrongly marked as an indirection. The enum is required so that the code generation adjustment takes place. Addresses #849

The legacy mangling scheme needs to convert the canonical path containing * for pointers and the [] brackets representing slices into: * = $BP$ [ = $u5b$ ] = $u5d$ These symbols are not allowed in asm symbols. Addresses #849

TODO Fixes #849

This is unfortunatly a mega commit, in testing gccrs against the slice code which is highly generic stress tested our implementation of generics and poked the hole in or lack of support of generic higher ranked trait bounds and more specificily generic associated types. More refactoring is needed to eventually remove the setup_associated_types and replace it entirely with this new setup_associated_types2 which takes into account the trait bound receiver and its predicate. In order to support slices, the code in libcore defines an index lang item ```rust impl<T, I> Index<I> for [T] where I: SliceIndex<[T]>, { type Output = I::Output; fn index(&self, index: I) -> &I::Output { index.index(self) } } ``` This is the entry point where by the self here is a generic slice. So in our case we have: ```rust let a = [1, 2, 3, 4, 5]; let b = &a[1..3]; ``` 'a' is an array and b is our desired slice, so we must remember that from algebraic data type constructor. But our receiver is still an array, so in order to be able to call this index lang item we must 'unsize' our array (see #1045) this allows for method resolution to adjust an array into a FatPtr which is simply a struct containing reference to the array and the capacity (GCC MAX_DOMAIN) of the underlying array data type. So now we are able to infer the substituions for this index fn call to: ``` fn index(&self : [<integer>], index: Range<integer>) -> &I::Output->placeholder ``` The complex piece here is the Higher ranked trait bound: ``` where I: SliceIndex<[T]> ``` So in this method call no generic arguments are specified so we must try and infer the types. So during monomorphization the inference variables need to be recursively propogated into the higher ranked trait bound. So that the higher ranked trait bound looks like: ``` SliceIndex<[<integer>]> // like we seen earlier for the Self type ``` The monomorphization stage also needs to take into account the higher ranked trait bound's type which is 'I' and infered to be: Range<integer>. This is where specialization needs to occur. ```rust unsafe impl<T> SliceIndex<[T]> for Range<usize> { type Output = [T]; unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] { unsafe { let a: *const T = slice.as_ptr(); let b: *const T = a.add(self.start); slice_from_raw_parts(b, self.end - self.start) } } fn index(self, slice: &[T]) -> &[T] { unsafe { &*self.get_unchecked(slice) } } } ``` So now we need to compute the constrained type-parameters for this specialized impl block. And in this case is fairly simple: ``` impl<T> SliceIndex<[T]> for Range<usize> vs I: SliceIndex<[<integer>]> and Range<<integer>> ``` Here we need to compute that T is <integer>, which is required since associated type Output is used in our original method call and this is generic which requires us to set it up but both the Self type or the trait bound here in this impl block could be generic so special care needs to be taken to compute this safely. Once the constrained types are computer we can also unify the Self types which specializes our original Range<integer> type into the correct Range<usize> that this trait bound expects. We used a callback here when we reusively pass down the SubstitutionArgumentMappings when any Parameter type is substitued we get a callback to hold a set of mappings in a generic way what generic types are being substituted. From all of this work this stressed our generics implementation to breaking point due to the use of the generic trait bound which was not supported and it also exposed many bugs in our implementation. This is why I feel it is best to keep this a large patch as so much of this patch will cause regressions if we don't keep it together. One of the main changes we have made is how we handle parameters substitution for example we might have a generic such as '&Y' but this gets substituted with Y=T which is a new type parameter. Before we used to directly just change this from &Y to &T which is correct but this looses context from the generic argument bindings. So now we maintain the information that &Y changes to &(Y=T) so that we see Y was substutued with T so that subsequent substitutions or inferences can change Y=?T and correctly map &Y to &(Y=T) to &(Y=?T). The other major piece which was changed during this patch was how we perform the method resolution on higher ranked trait bound calls where we compute the specified bound possible candidates once so that in the case: ``` trait Bar { fn baz(&self) } fn <T:Bar> foo(a: &T) { a.baz() } ``` Here the type parameter T gets derefed to find the specified bound of Bar which contains the method baz. This means that we try calling baz with T vs &T which fails then we try the reference type T again. This results into two useless adjustments of indirection and referencing but GCC optimizes this away. Before this patch we computed the specified bound for each attempt which was wrong. Fixes #849

1100: Add known lang item const_slice_ptr mappings r=philberty a=philberty This will allow us to define the const_slice_ptr lang item attribute without erroring out as an unknown lang item. Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

1090: macros: add concat! macro r=philberty a=liushuyu - extracts parenthesis-matching logic into a function - adds `concat!` macro 1097: Support mangling *const ptr and slices like *const [T] r=philberty a=philberty The legacy mangling scheme needs to convert the canonical path containing * for pointers and the [] brackets representing slices into: * = $BP$ [ = $u5b$ ] = $u5d$ These symbols are not allowed in asm symbols. Addresses #849 1098: Ensure unsize method resolutions actually unsize r=philberty a=philberty This was a typo when unsized method resolution was added, where the adjustment was wrongly marked as an indirection. The enum is required so that the code generation adjustment takes place. Addresses #849 1099: Fix bad inherent overlap error r=philberty a=philberty When we examine HIR::ImplBlock's we determine if an impl might overlap another impl based on the Self type. So for example you might have a generic structure Foo<T>(T), and an associated impl block for Foo<i32>, but then go on to define an associated impl of Foo<T> the generic one will overlap any associated impl hiding the generic implementation. In this case we have two generic impl blocks *const [T] *const T This means the *const T might overlap with the slice one since it is generic. As bjorn3 pointed out in #1075 , the correct implementation is to observe that [T] is constrained by size but untill we have the auto trait of Sized we must example the two generic impls and just determine that they are not-equal so for now this is the best implementation we can do. Fixes #1075 1101: Add helper as_string for DefIds r=philberty a=philberty This just adds a useful helper to as_string DefId's directly Co-authored-by: liushuyu <liushuyu011@gmail.com> Co-authored-by: Philip Herron <philip.herron@embecosm.com>

This is unfortunatly a mega commit, in testing gccrs against the slice code which is highly generic stress tested our implementation of generics and poked the hole in or lack of support of generic higher ranked trait bounds and more specificily generic associated types. More refactoring is needed to eventually remove the setup_associated_types and replace it entirely with this new setup_associated_types2 which takes into account the trait bound receiver and its predicate. In order to support slices, the code in libcore defines an index lang item ```rust impl<T, I> Index<I> for [T] where I: SliceIndex<[T]>, { type Output = I::Output; fn index(&self, index: I) -> &I::Output { index.index(self) } } ``` This is the entry point where by the self here is a generic slice. So in our case we have: ```rust let a = [1, 2, 3, 4, 5]; let b = &a[1..3]; ``` 'a' is an array and b is our desired slice, so we must remember that from algebraic data type constructor. But our receiver is still an array, so in order to be able to call this index lang item we must 'unsize' our array (see #1045) this allows for method resolution to adjust an array into a FatPtr which is simply a struct containing reference to the array and the capacity (GCC MAX_DOMAIN) of the underlying array data type. So now we are able to infer the substituions for this index fn call to: ``` fn index(&self : [<integer>], index: Range<integer>) -> &I::Output->placeholder ``` The complex piece here is the Higher ranked trait bound: ``` where I: SliceIndex<[T]> ``` So in this method call no generic arguments are specified so we must try and infer the types. So during monomorphization the inference variables need to be recursively propogated into the higher ranked trait bound. So that the higher ranked trait bound looks like: ``` SliceIndex<[<integer>]> // like we seen earlier for the Self type ``` The monomorphization stage also needs to take into account the higher ranked trait bound's type which is 'I' and infered to be: Range<integer>. This is where specialization needs to occur. ```rust unsafe impl<T> SliceIndex<[T]> for Range<usize> { type Output = [T]; unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] { unsafe { let a: *const T = slice.as_ptr(); let b: *const T = a.add(self.start); slice_from_raw_parts(b, self.end - self.start) } } fn index(self, slice: &[T]) -> &[T] { unsafe { &*self.get_unchecked(slice) } } } ``` So now we need to compute the constrained type-parameters for this specialized impl block. And in this case is fairly simple: ``` impl<T> SliceIndex<[T]> for Range<usize> vs I: SliceIndex<[<integer>]> and Range<<integer>> ``` Here we need to compute that T is <integer>, which is required since associated type Output is used in our original method call and this is generic which requires us to set it up but both the Self type or the trait bound here in this impl block could be generic so special care needs to be taken to compute this safely. Once the constrained types are computer we can also unify the Self types which specializes our original Range<integer> type into the correct Range<usize> that this trait bound expects. We used a callback here when we reusively pass down the SubstitutionArgumentMappings when any Parameter type is substitued we get a callback to hold a set of mappings in a generic way what generic types are being substituted. From all of this work this stressed our generics implementation to breaking point due to the use of the generic trait bound which was not supported and it also exposed many bugs in our implementation. This is why I feel it is best to keep this a large patch as so much of this patch will cause regressions if we don't keep it together. One of the main changes we have made is how we handle parameters substitution for example we might have a generic such as '&Y' but this gets substituted with Y=T which is a new type parameter. Before we used to directly just change this from &Y to &T which is correct but this looses context from the generic argument bindings. So now we maintain the information that &Y changes to &(Y=T) so that we see Y was substutued with T so that subsequent substitutions or inferences can change Y=?T and correctly map &Y to &(Y=T) to &(Y=?T). The other major piece which was changed during this patch was how we perform the method resolution on higher ranked trait bound calls where we compute the specified bound possible candidates once so that in the case: ``` trait Bar { fn baz(&self) } fn <T:Bar> foo(a: &T) { a.baz() } ``` Here the type parameter T gets derefed to find the specified bound of Bar which contains the method baz. This means that we try calling baz with T vs &T which fails then we try the reference type T again. This results into two useless adjustments of indirection and referencing but GCC optimizes this away. Before this patch we computed the specified bound for each attempt which was wrong. Fixes #849

1086: Slice support r=philberty a=philberty Please see the commit a8de089 for a long explanation of what's going on in the patch. Unfortunately, I have not been able to split this patch up anymore since supporting slices exposed many bugs in the implementation of generics in general never main the missing support for generic associated types. Fixes #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

philberty added the enhancement label Jan 4, 2022

philberty added this to the Macro Expansion milestone Jan 4, 2022

philberty self-assigned this Jan 4, 2022

philberty mentioned this issue Jan 4, 2022

Goal Testcase #682

Open

51 tasks

philberty mentioned this issue Feb 18, 2022

Add name resolution to slices #951

Merged

philberty mentioned this issue Feb 24, 2022

Add support for ranges and index lang items along with the TyTy::SliceType #974

Merged

This was referenced Mar 10, 2022

Add more intrinsics and refactor how we implement them #1003

Merged

Add const_ptr lang item mappings #1008

Merged

Add missing type resolution to slices and arrays #1009

Merged

philberty mentioned this issue Mar 11, 2022

Add code generation for the slice type #1015

Merged

philberty added a commit that referenced this issue Mar 11, 2022

Add missing HIR lowering for SliceTypes

47ae663

Addresses #849

philberty mentioned this issue Mar 11, 2022

Add missing HIR lowering for SliceTypes #1016

Merged

bors bot added a commit that referenced this issue Mar 11, 2022

Merge #1016

e076823

1016: Add missing HIR lowering for SliceTypes r=philberty a=philberty Addresses #849 Co-authored-by: Philip Herron <philip.herron@embecosm.com>

This was referenced Mar 16, 2022

Rewrite our unconstrained type-param error checking #1030

Merged

Fix bad copy-paste in can equal interface for pointer types #1033

Merged

philberty mentioned this issue Mar 17, 2022

Support placeholders becoming slices #1037

Merged

philberty mentioned this issue Mar 21, 2022

Add initial support for unsized method resolution #1045

Merged

philberty removed this from the Macro Expansion milestone Mar 27, 2022

philberty mentioned this issue Apr 9, 2022

Support mangling *const ptr and slices like *const [T] #1097

Merged

This was referenced Apr 9, 2022

Ensure unsize method resolutions actually unsize #1098

Merged

Add known lang item const_slice_ptr mappings #1100

Merged

philberty added a commit that referenced this issue Apr 9, 2022

Support Slices from rustc libcore 1.49.0

065ffe6

TODO Fixes #849

philberty mentioned this issue Apr 9, 2022

Slice support #1086

Merged

bors bot closed this as completed in #1086 Apr 12, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add support for Slices #849

Add support for Slices #849

philberty commented Jan 4, 2022 •

edited

Loading

Add support for Slices #849

Add support for Slices #849

Comments

philberty commented Jan 4, 2022 • edited Loading

philberty commented Jan 4, 2022 •

edited

Loading