Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Support vec![const { ... }; n] syntax for creating a Vec of non-Clone values #484

Open
EFanZh opened this issue Nov 15, 2024 · 19 comments
Open
Labels
api-change-proposal A proposal to add or alter unstable APIs in the standard libraries T-libs-api

Comments

@EFanZh
Copy link

EFanZh commented Nov 15, 2024

Proposal

Problem statement

For array types, I can use [const { ... }; N] syntax to create an array of const { ... }, even if it’s does not implement Clone. But I can’t do the same thing with Vec: vec![const { ... }; n] currently does not compile.

Motivating examples or use cases

Imagining implementing a DFS algorithm with an array to save the traversal states, I can write something like:

enum State {
    NotVisited,
    Visiting,
    Visited,
}

let states = std::iter::repeat_with(|| State::NotVisited).take(n).collect::<Vec<_>>();

But it could be more simple if I could just write:

let states = vec![const { State::NotVisited }; n];

Deriving Clone might not always be possible because the value type could be from a third party crate.

Solution sketch

Reimplement vec! macro so it supports the const { ... } syntax above.

Alternatives

Links and related work

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

  • We think this problem seems worth solving, and the standard library might be the right place to solve it.
  • We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

  • We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
  • We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.
@EFanZh EFanZh added api-change-proposal A proposal to add or alter unstable APIs in the standard libraries T-libs-api labels Nov 15, 2024
@dtolnay
Copy link
Member

dtolnay commented Nov 15, 2024

Seems like a good idea to me. I expect the implementation you have in mind involves expanding to <[_]>::into_vec(Box::new([const { expr }; N])) in the const case. I think that's fine to do but it won't benefit from the good suggestion that array syntax provides where it tells you to wrap your expression in an inline const block. Compare:

error[E0277]: the trait bound `State: Copy` is not satisfied
 --> src/main.rs:9:14
  |
9 |     let _ = [State::NotVisited; N];
  |              ^^^^^^^^^^^^^^^^^ the trait `Copy` is not implemented for `State`
  |
  = note: the `Copy` trait is required because this value will be copied for each element of the array
help: consider annotating `State` with `#[derive(Copy)]`
  |
2 + #[derive(Copy)]
3 | enum State {
  |
help: create an inline `const` block
  |
9 |     let _ = [const { State::NotVisited }; N];
  |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~

vs:

error[E0277]: the trait bound `State: Clone` is not satisfied
    --> src/main.rs:9:18
     |
9    |     let _ = vec![State::NotVisited; N];
     |             -----^^^^^^^^^^^^^^^^^----
     |             |    |
     |             |    the trait `Clone` is not implemented for `State`
     |             required by a bound introduced by this call
     |
note: required by a bound in `from_elem`
    --> $RUSTUP_HOME/toolchains/nightly-aarch64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/vec/mod.rs:3172:21
     |
3172 | pub fn from_elem<T: Clone>(elem: T, n: usize) -> Vec<T> {
     |                     ^^^^^ required by this bound in `from_elem`
help: consider annotating `State` with `#[derive(Clone)]`
     |
2    + #[derive(Clone)]
3    | enum State {
     |

So while I don't think the implementation of this needs to be blocked on a better diagnostic, I would encourage you to think about what it would take to hint for the user to write vec![const { expr }; N] when they wrote vec![expr; N] on a const non-Clone expr.

@dtolnay dtolnay added the ACP-accepted API Change Proposal is accepted (seconded with no objections) label Nov 15, 2024
@dtolnay dtolnay closed this as completed Nov 15, 2024
@EFanZh
Copy link
Author

EFanZh commented Nov 15, 2024

I don’t think the array syntax can be used to implement the vec! macro, since the array syntax requires the length being a const value, while the length used in vec! can be a runtime value.

@EFanZh EFanZh changed the title Support vec![const { expr }; N] syntax for creating a Vec of non-Clone values. Support vec![const { expr }; N] syntax for creating a Vec of non-Clone values Nov 15, 2024
@scottmcm
Copy link
Member

Should it maybe be Vec::repeat(n, || whatever) instead? (Or from_fn or something_with or whatever)

It feels like the const-ness here is mostly irrelevant to what this would do, and it'd be just as useful to have this for non-const computations.

@cuviper
Copy link
Member

cuviper commented Nov 15, 2024

Other examples where Clone may not be wanted or intended:

  • vec![Vec::with_capacity(cap); n]
  • vec![Arc::new(Mutex::new(x)); n]

@dtolnay
Copy link
Member

dtolnay commented Nov 15, 2024

I don’t think the array syntax can be used to implement the vec! macro, since the array syntax requires the length being a const value

Good call; I didn't consider non-const N — so this would only be serving as shorthand for iter::repeat_with(|| expr).take(N).collect::<Vec<_>>(). I agree with Scott that the const doesn't feel necessary or relevant in that case.

@dtolnay dtolnay removed the ACP-accepted API Change Proposal is accepted (seconded with no objections) label Nov 15, 2024
@dtolnay dtolnay reopened this Nov 15, 2024
@scottmcm
Copy link
Member

scottmcm commented Nov 15, 2024

@cuviper Good point! A particularly subtle one is vec![HashMap::new(); n], since that keeps them all from getting different randomstates, whereas repeat_with(HashMap::new).take(n).collect() will get n different randomstates.

@cuviper
Copy link
Member

cuviper commented Nov 15, 2024

We should also be careful about how this interacts with expr/expr_2021 changes:
https://doc.rust-lang.org/nightly/edition-guide/rust-2024/macro-fragment-specifiers.html

... but maybe that just means we would have to manually match the const before the more general expr.

@EFanZh
Copy link
Author

EFanZh commented Nov 16, 2024

Vec::repeat(n, || ...) doesn’t have to replace the vec![const { ... }; n] syntax.

  • It might be less surprising that the vec! macro behaves the same as the array literal syntax.
  • It might be easier for the compiler to optimize for the vec! version, because the constness is expressed explicitly. But for the function version, it will take some reasoning for the compiler to conclude that the function generates a constant value, and the compiler might not always be able to do so. One could try to write Vec::repeat(n, || const { ... }) and hope the compiler knows what to do, but it still depends on the optimization capability of the compiler. For example, in debug builds, the compiler might be unable to perform the optimization.

So, regardless of whether Vec::repeat(n, || ...) should be supported, it is still useful to support vec![const { ... }; n].

@joshtriplett
Copy link
Member

We talked about this in today's @rust-lang/libs-api meeting.

We were in favor of vec![...] to define a vector always accepting any syntax that can be used for [...] to define an array.

We also wondered whether this would Just Work when the standard library is converted to the 2024 edition and uses the 2024 expr in all macros.

@scottmcm
Copy link
Member

  • It might be easier for the compiler to optimize for the vec! version

I don't see how, because it's a dynamic length. The implementation is going to be repeat_with(f).take(n).collect() either way.

So I think that || const { … } would be just as fine and explicitly const.

  • It might be less surprising that the vec! macro behaves the same as the array literal syntax.

Except it can't, because [Foo::CONST; N] also works without Clone, and there's no way for the macro to detect that.

@EFanZh
Copy link
Author

EFanZh commented Nov 22, 2024

@scottmcm: This is what I have in mind:

macro_rules! vec {
    (const $elem:block; $n:expr) => {{
        let n: usize = $n;
        let mut result = Vec::with_capacity(n);

        for target in unsafe { result.spare_capacity_mut().get_unchecked_mut(..n) } {
            target.write(const $elem);
        }

        unsafe { result.set_len(n) };

        result
    }};
}

The value is guaranteed to be computed at compile time.

Also, vec![Foo::CONST; N] and vec![const { ... }; N] could have different semantics. If the type of Foo::CONST in vec![Foo::CONST; N] implements Clone, we may need to call Clone::clone in order to not break existing code; and we can guarantee that no Clone::clone is called with the vec![const { ... }; N] syntax.

Currently, we can’t differentiate implicit const expression (Foo::CONST) from a non-const expression, but that could be supported in the future through some compiler magic, possibly through a new fragment specifier const_expr:

macro_rules! vec {
    (const $elem:const_expr; $n:expr) => { ... };
}

I suggest we only support the explicit const expression syntax (const { ... }) now, and leave the implicit ones to the future, since it can be trivially converted to a explicit one by enclosing it with a const block.

For reference, here is a summary of the behaviors of different situations:

Type Constraint Array vec! Currently vec! Proposed vec! Possible Future
Clone only Not supported Clone Clone Clone
Clone + Copy memcpy Clone Clone Clone
implicit const only memcpy Not supported Not supported memcpy
implicit const + Clone memcpy Clone Clone Clone
implicit const + Clone + Copy memcpy Clone Clone Clone
explicit const only memcpy Not supported memcpy memcpy
explicit const + Clone memcpy Not supported memcpy memcpy
explicit const + Clone + Copy memcpy Not supported memcpy memcpy

@fmease
Copy link
Member

fmease commented Nov 24, 2024

This means vec![const { … }; n] and vec![(const { … }); n] will differ semantically (in all editions).

@EFanZh
Copy link
Author

EFanZh commented Nov 24, 2024

This means vec![const { … }; n] and vec![(const { … }); n] will differ semantically (in all editions).

The array syntax has a similar problem, although not exactly the same:

  • _ = [const { ... }; 0] does not call the destructor of the provided value.
  • _ = [( const { ... } ); 0] does not call the destructor of the provided value.
  • _ = [{ const { ... } }; 0] calls the destructor of the provided value.

See https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=de7aee11cb3719882d04d8f0767ecf81.

Now vec![(const { ... }); n] calls Clone::clone, if we choose to also make vec![const { ... }; n] behave the same, it will also have call Clone::clone. But not all const value types implement Clone, if we want to support non-Clone types, vec![const { ... }; n] needs to behave differently depending on whether the value type implements Clone. Personally, I consider one syntax with two different behaviors being worse than the behavior difference caused by adding a pair of parentheses. Also, if we choose to call Clone::clone function with vec![const { ... }; n], we lose the ability to create a Vec without calling the Clone::clone function if the value type implements Clone.

Another solution would be adding a new syntax or even a new macro that is dedicated to handing the const value case.

@EFanZh EFanZh changed the title Support vec![const { expr }; N] syntax for creating a Vec of non-Clone values Support vec![const { ... }; N] syntax for creating a Vec of non-Clone values Nov 24, 2024
@EFanZh EFanZh changed the title Support vec![const { ... }; N] syntax for creating a Vec of non-Clone values Support vec![const { ... }; n] syntax for creating a Vec of non-Clone values Nov 24, 2024
@kennytm
Copy link
Member

kennytm commented Nov 25, 2024

@EFanZh It is a known design that x and {x} behaves differently (esp. regarding borrow-check), but x and (x) always behaved the same until your proposed syntax.

@traviscross
Copy link

traviscross commented Nov 25, 2024

It is also the case that I'd in general expect mac!(const { $expr }) and const X: _ = $expr; mac!(X) to have the same behavior.

@fmease
Copy link
Member

fmease commented Nov 25, 2024

I wouldn't compare this to the [_; 0] situation, that's a separate issue.

But not all const value types implement Clone, […]

I do understand the problem this ACP is trying to solve, don't get me wrong.

Personally, I consider one syntax with two different behaviors being worse than the behavior difference caused by adding a pair of parentheses.

It's not (all) about the parentheses, it's about the fact that adding a const $elem:block match arm is surprising and hacky to be perfectly honest (yes, I'm aware of the macro thread_local, the precedent if you will). It leads to libstd accumulating special cases which in turn worsens the "predictability" and "teachability" of its APIs. Who is going to suspect that the const { … } in vec![const { … }; n] is not in fact the relatively recently stabilized const block but a DSL? What does this say about const blocks?

Moreover, I think the goal "[…] vec![...] to define a vector always accepting any syntax that can be used for [...] to define an array" (via) (which const $elem:block does fulfill) is missing a point. It's not only about the syntax, it's also about the semantics. Going forward with this change would lead to a more serious divergence in behavior between vec![…] and […]:

For array repeat literals [x; n], the rule is "inline x" if x is a const block const { … } (modulo parentheses) or a path to a free or associated constant, otherwise memcpy it. The const $elem:block approach misses paths for example! Consider the semantically valid expressions [C; N] and [S::C; N] where C and S::C are of a non-Copy type. It's not (all) about the parentheses.

Lastly, this change would render vec![x; n] and vec![$x; n] semantically distinct in Rust 2024 code and beyond (where $x is macro meta var matching fragment kind expr (not expr_2021)). Consider macro_rules! wrap { ($e:expr) => { vec![$e; 128] } }: Here, wrap!(const { 0 }) would no longer mean the same as vec![const { 0 }; 128]!

It's not (all) about the parentheses.

@programmerjake
Copy link
Member

programmerjake commented Nov 25, 2024

if we want [MY_NAMED_CONST; N] syntax to work with things other than arrays, maybe we need a built-in macro is_expr_copyable! that is true if the passed-in expression is a const block/item or is a type that implements Copy. (this isn't specialization, it only works on types where [v; 2] would work for an expression v with that type, so this generally requires a visible T: Copy bound.)

could then be defined like:

macro_rules! vec {
    ($($values:expr),* $(,)?) => {
        ...
    };
    ($value:expr; $len:expr) => {
        {
            let value = $value;
            let len = $len;
            unsafe { CloneOrCopy::<{ is_expr_copyable!($value) }>::repeat_vec(value, len) }
        }
    };
}

#[doc(hidden)]
pub struct CloneOrCopy<const IS_COPYABLE: bool>;

impl CloneOrCopy<false> {
    #[doc(hidden)]
    pub fn repeat_vec<T: Clone>(value: T, len: usize) -> Vec<T> {
        ...
    }
}

impl CloneOrCopy<true> {
    #[doc(hidden)]
    pub unsafe fn repeat_vec<T>(value: T, len: usize) -> Vec<T> {
        // TODO: handle value being all zero bytes, for using `alloc_zeroed`
        // TODO: handle stuff that turns into `memset`
        let mut retval = Vec::with_capacity(len);
        // drop value if len == 0 for things like:
        // struct MyStruct;
        // impl Drop for MyStruct {
        //     fn drop(&mut self) {
        //         println!("dropped");
        //     }
        // }
        // vec![MyStruct; 0] // should drop MyStruct once
        if len > 0 {
            let value = ManuallyDrop::new(value);
            for i in 0..len {
                unsafe { retval.push(ptr::read(&*value)) };
            }
        }
        retval
    }
}

@cuviper
Copy link
Member

cuviper commented Nov 25, 2024

I think it would be better to have an explicit syntax for "repeat this expression" (regardless of const) vs. the current cloning, whether that's another variation of vec! or a new macro or method -- assuming we can do better than iter::repeat_with.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
api-change-proposal A proposal to add or alter unstable APIs in the standard libraries T-libs-api
Projects
None yet
Development

No branches or pull requests

9 participants