[pre-RFC] Allowing string literals to be either &'static str or String, similar to numeric literals

1

This thread reminded me that we haven’t had a serious discussion of the string literal to String problem in a while, and I haven’t seen anyone propose this particular solution yet.

Summary

String literals can be either &'static str or String. Type deduction attempts to pin down which type each literal should be, and if it can’t then it falls back on assuming &'static str.

This is similar to how numeric literals can be any numeric type, but fall back to i32.

Motivation

Basically, having to write these .to_string()s is really annoying:

fn foo(v: &Vec<String>) {
    println!("foo: {:?}", v);
}

fn main() {
    let v = vec!["x".to_string(), "y".to_string(), "z".to_string()];
    foo(&v);
}

They probably also confuse beginners, and force beginners to confront the nuances of the various string types earlier than perhaps they should. And they’re an annoying distraction to everyone who already knows the difference between &'static str and String.

One obvious solution is introducing implicit conversions from &'static str to String, but that would be very undesirable for a language like Rust that cares about performance as well as ergonomics.

Detailed Design

The same as numeric literals, except we have only two types that we want string literals to be: &'static str and String.

That means the following code should just work:

fn foo(v: &Vec<String>) {
    println!("foo: {:?}", v);
}
fn bar(v: &Vec<&'static str>) {
    println!("bar: {:?}", v);
}

fn main() {
    let v1 = vec!["x", "y", "z"]; // v1 is a Vec<String>
    foo(&v1);
    let v2 = vec!["x", "y", "z"]; // v2 is a Vec<&'static str>
    bar(&v2);
}

When there is no explicit type available, we fall back to &'static str, so code like this which works today will continue to work:

fn foo<T>(v: &Vec<T>) where T: std::fmt::Debug {
    println!("foo: {:?}", v);
}

fn main() {
    let v = vec!["x", "y", "z"]; // v continues to be a Vec<&'static str>
    foo(&v);
}

This proposal emphatically does not include any auto-ref, auto-deref or implicit conversions. The only impact is that some string literals would be treated as “String literals” instead of “&'static str” literals, and only in cases where the code wouldn’t compile otherwise.

How We Teach This

We have to teach Rust users about &str, &'static str and String at some point no matter what. The biggest impact of this change on teaching is that we don’t have to immediately delve into that subject or unsatisfyingly handwave it away the first time we show a program with a string literal in it.

Drawbacks

The type of a string literal would become context-dependent, which could be considered confusing. Whether that’s more confusing than the status quo is debatable.

Today, no type deduction is required on string literals. Introducing type deduction here may create cases of “inference breakage”.

Alternatives

Explicit prefixes, suffixes, operators, methods with shorter names than to_string(), or alternate quotation marks. I’m grouping all of these together because they’re all various kinds of explicit annotation. Because I believe this frustration is unique to string literals, it’s usually very easy to infer when those literals have to be Strings, and &'static str is an obvious choice for the default string literal type (more obvious than i32 was for numeric literals imo), I see no reason to require an annotation at all.

As previously mentioned, implicit conversions are another option.

Doing nothing is always an option.

Unresolved Questions

How much, if any, code would experience “inference breakage” under this change? (I couldn’t think of anything but I’m sure one of you can)

Are there any other “string types” we might want string literals to be deduced to?

8 Likes
2

How would this work with static and const declarations, where to_string isn’t currently allowed?

3

For now I’d punt on static/const, i.e. not change the behavior there at all, because making “const Strings” happen is part of a much bigger question about how CTFE should allow “compile-time heap” memory to “escape to runtime” (see https://public.etherpad-mozilla.org/p/rust-compiler-design-sprint-paris-2017-miri for the compiler team brainstorming on that topic). The answer to that question will probably be the same for all containers, not just String.

tl;dr: For my proposal, “const/static String literals” would definitely be a future extension.

4

There’s a very similar proposal I was told last year that I think no one has just gotten around to writing up. The big difference is that an immutable string literal String would still be allocation free.

My understanding of the idea is that we could coerce &'static str to String with a capacity = 0. Any attempt to extend that string would cause a reallocation into the heap, just by the nature of the definition of String.

(It has also occurred to me that by the same logic we could coerce an &'a str to an &'a String & these concepts apply just as well to [T]/Vec<T>; the only reason we can’t get rid of strs and slices entirely is &'a mut [T], which doesn’t let you extend the buffer’s length.)

5 Likes
5

Note that having Strings point to static data would require deref_mut to do an allocation. By itself, this could lead to surprising behavior and could break code that expects pointers to remain stable (mainly unsafe code, but also safe code that checks for pointer equality), but I think the performance benefit is worth those costs. However, I think it would be unnecessarily surprising if deref_mut caused capacity() to change, and capacity() < len() doesn’t really make that much sense to start with (for one thing, it would cause the common s.capacity() - s.len() to overflow). So I think static Strings should just have capacity() == len(), and add a separate method to check for static-ness.

But there’s also a performance cost to making every deref_mut check whether an allocation is needed. Indeed, the original pull request to add Cow had a DerefMut implementation, but it was removed in favor of making things explicit. And this proposal would effectively turn String into Cow<'static, str> - albeit hopefully with a more efficient implementation. (The proposal also adds a very small cost to capacity() or another accessor, since there would have to be a hidden is-static bit, probably in the capacity field, which the method would have to mask away. This would be avoided if capacity() returns 0, but as I said, that’d be surprising, and this cost probably isn’t worth worrying about.)

On the flipside, since String is a Vec<u8> anyway, we could extend this to all Vec<T> and let array literals resolve to Vec. That too would be a nice ergonomic boost.

An alternative would be to keep String as-is but allow string literals to resolve to Cow<'static, str>. I’m not sure that actually improves ergonomics, though…

6 Likes
6

Optimizing away the allocation on immutable String literals is worth looking into, but ending up with String acting like Cow<> or lying about its capacity would be pretty big downsides, and they feel a lot like putting the cart before the horse since the goal here is to make string literals simpler. It might be best to leave that for a second iteration (or third, since we’re already punting on const/static), and tell people who really need the “immutable String optimization” to just use Cow explicitly.

Another option would be making Cow<'static, str> a third type that literals can turn into. This only helps if you’ve “opted in” to it by actually saying Cow in your code somewhere, but it’s an option. Right now I have no idea if I’m for or against it.

5 Likes
7

In addition to deref_mut, some other methods that currently don’t allocate need to start checking for static-ness allocate (if static): At least drain, remove, into_boxed_str, pop, possibly others.

Using capacity() == len() for has the disadvantage that it needs an additional bit of information somewhere (as that is a valid state for normal heap-allocated strings), and unless we find an unused bit in the existing representation (at the peril of slowing down common accesses because the bit needs to be masked out), alignment constraints will mean this bumps String from 3 usizes to 4 usizes.

1 Like
8

Yes, there are unused bits: two of them, in the capacity and length fields, because allocation sizes are restricted to fit in a signed integer. Alternatively, static data could be stored with the internal capacity field equal to 0, and have capacity() check for that.

1 Like
9

Thanks for these really insightful comments. I'm definitely not the originator of the idea (I feel like it was secondhand by the time it got to me) so I can't comment further.

I agree it wouldn't help much. One ergonomics/learnability advantage is that &'static str becomes a legacy type for the most part - things like const FOO: String would work fine; you get the intuitive type you want it to be.

If we want a version of String that doesn't have these properties in the standard library, I'd be more in favor of creating a new StrBuf type, possibly with more "StringBuilder" style APIs (that is, an emphasis on mutation, probably with a chaining API). But I'd rather see something like that grow on crates.io and only be moved into std if it proved necessary; I suspect that most applications aren't going to notice the overhead.

10

Random idea I just had, rather than hardcoding this for &'static str/String it could be nice to allow this to work for arbitrary types. This could be done via some sort of const fn once we have something like that, there could then be a sugar for strings to call this function instead of having to type it out explicitly.

Imagine we had something like

trait ConstFromString {
    /// Panics if parsing fails, unless we have some other way to
    /// pass errors back from const functions
    const fn const_from_string(s: &'static str) -> Self;
}

Then the sugar could be something like

let s: String = p"hello world";

which would desugar to

let s: String = ConstFromString::const_from_string("hello world");

This trait could then be implemented by other types that make sense to create as compile time constants, newtypes around &str/String, regexes, urls, etc.

11

Sigils?

12

You can't. An &'a str is 2 words, and an &'a String is a pointer to 3 words.

13

How about a new string literal that allows interpolation and produces String?

let name = "Bob";
// dedicated syntax
let sentence = `Hello, {name}!`;
// or a new kind of macro
let sentence = str! "Hello, {name}!";
println! "Hello, {name}!";

Edit: looks like somebody beat me to it in another thread :joy:

That can be rewritten as

["x","y","z"].iter().map(String::from).collect()
// or even
"xyz".chars().map(String::from).collect()
14

I understand what you’re trying to fix here but magically promoting stuff to the heap isn’t the rust way. Also, special casing String to allow static backing data is even more magical as it could break assumptions whenever an operation would hit the allocator or not.

2 Likes
15

As fas I can tell, every solution tries to solve the problem that you have to manually type .to_string() sometimes. How about a solution where we literally make this explicit call implicit? Nothing more and nothing less. With this solution it would be possible to mark the

impl<'a> From<&'a str> for String

impl somehow (for example by adding #[implicit_call]) and the compiler would simply insert the proper into() calls where necessary. This solution has nothing to do with strings and does not require new syntax. It would work for all marked types. The only drawback I see is that it could be easily abused. Also, I know nothing about compiler internals, maybe it is too much magic:)

Edit: Also, it could be possible to simply disable/enable all automatic conversion traits by some compiler attribute for a given crate/file/block/whatever as necessary, if someone wants to be extra careful or extra lazy.

16

Any backwards-compatible solution will require typing something in some cases, because if you're calling fn foo<T>(x:T) with a literal, it needs to continue to infer T == &'static str. Making the From call implicit would allow let x: String = "bar";, but that's not meaningfully less typing than let x = "bar".to_string();, IMHO. (And implicit allocation from any &'a str is scary to me.)

Since we have b"bar" and br#""bar""#, maybe the easiest version (back-compat, no inference changes, explicit about allocating, no pervasive costs) of this is just s"bar" and sr#""bar""#? (Like "bar"s in C++14.) Or maybe a more general letter (m for mutable? a for allocating? o for owning?) so that ab"bar" is a Vec<u8> too...

2 Likes
17

So here’s some details since there seems to be some confusion of how this would work:

For now I will just assume there’s a String::from_literal constructor and we’re just interested in supporting this as a manual optimization. The merits and details of any coercion are orthogonal.

These are what I consider the major benefits:

  • improved performance for some code
  • a path forward to coercions for improved ergonomics

These are what I consider the major concerns:

  • breaking the pointer-stability assumptions of tricky unsafe code
  • introducing latency in critical sections of code
  • how to expose capacity in these semantics
  • whether Vec should also support this optimization
  • wanting to introduce Cow/Rc-like APIs so people can probe the state

But before I dig into those, we need to understand the implementation.

Implementation

String is currently a wrapper around a Vec<u8> (ptr, len, cap), and this detail is exposed at the API-level by as_mut_vec. Because they’re defined in the same library, String can mess around with Vec’s fields all it wants, and we can just make sure Vec handles it correctly.

&str is a “fat pointer” (ptr, len).

To store a String literal in itself, String will set Vec’s (RawVec’s) cap field to 0.

RawVec already has to check for cap = 0 in its Drop implementation, so this will incur no overhead there. Vec may need to add its own cap = 0 check if we want to make Vec itself Cow to avoid dropping the contents. However this will easily be optimized into the same branch RawVec has, at no cost (RawVec needs to keep the branch for its other consumers).

Many Vec APIs already check for len == cap for if they should reallocate. This should be changed to len >= cap, which will incur no overhead.

However the reallocation code currently won’t do the right thing. double will need to be updated to take a used_cap argument, and check for it in the already existing cap = 0 branch. This will be basically free, since it will be adding a branch to an already-cold path.

The reserve functions will also need to update their fast-path branches. This is relatively sensitive since reserve evaporating has historically been very important for optimizing iterator loops into memcopies. I’m cautiously optimistic since it will just be changing cap - len >= requested_extra into something like cap != 0 && cap - len >= requested_extra, which is hopefully “obvious” to the optimizer due to cap increasing by a usize.

This leaves the mutating operations which don’t increase capacity, like pop and DerefMut<[T]>. These need new checks for cap=0 to do the right thing. Currently they guard on len. We can either implement this logic at the level of Vec, so that it becomes Cow<'static, [T]>, or we can implement this logic at the level of String. The latter will probably be more error-prone, but is easier to justify (see other sections for discussion).

So pretty much all cost will be concentrated in extra branches in functions like pop. No special bitflags are needed. 0 cap is already a sentinel in Vec.

Performance

There are a few places where this optimization has an opportunity for significant performance wins. If code doesn’t fall into these cases, then it’s mostly just moving the cost of allocating a fresh string a bit further down the road.

  • Bundling allocations. String::from("hello").push_str("!!!") will perform two allocations today (if you want to argue for LLVM optimizing this away, imagine the two ops are far away). With this optimization it will only need to be one allocation, as the COW operation will know that it also needs some slack space for the “!!!”. String::from("hello").clear() will be able to do zero allocations. String::from("hello").truncate(1) will still do 1 allocation as it does today, but can save a bunch of copying, and use a smaller allocation.

  • Code that requests Strings because it needs to store the data longterm, but doesn’t actually mutate them. This code could be changed to use Box<str> without any issue. However requiring Box<str> can itself be a performance issue, as in the cases where one actually needs to dynamically construct a String, one might (probably?) have some slack space in the allocation, and that means reallocating to construct a Box<str>. Cow<'static str> could also be used for this case; see below.

  • Code that requests Strings, but usually doesn’t need to mutate them. This code could be changed to use Cow<'static, str>. However Cow being a general construct can’t do interesting type-specific optimizations. In particular, every access will need to branch on “str or String” (although this is a particularly cacheable/optimizeable branch). Building this logic into String will eliminate an extra branch for almost every operation (as it will be unnecessary, or folded into an existing check).

The operations that would probably need a new branch are:

  • as_mut_vec
  • remove
  • drain (when it isn’t equivalent to truncate()/clear())

(edit: some things were removed here, operations like truncate/pop/clear are actually fine)

Related to &mut str:

  • as_mut_str
  • DerefMut::deref_mut
  • make_lowercase_ascii
  • make_uppercase_ascii
  • IndexMut::*

Clone::clone would probably gain an extra branch as a performance optimization (no-op if cap = 0).

My general rule of thumb here is that it’s basically fine to add a predictable branch before an O(n) operation, but sketchy to add one to an O(1) operation (as it may be tossed in a tight loop). So basically only pop , truncate, and clear qualify, but truncate and clear aren’t things you would do in a tight loop. So basically only pop is even kind-of concerning.

In general there aren’t many operations you can perform on a String in place, because basically every unicode operation can lead to a change in byte-wise length. &mut str is basically “hello yes I would like to do ASCII things”.

By contrast, &mut [T] is a really useful type, and I’d be very concerned to make the Vec -> &mut [T] transformation expensive.

Pointer Stability

The “operations which will need a branch” are also those that will now be able to trigger a reallocation, which couldn’t before. Any unsafe code which was relying on this not happening will be broken if it’s passed a String containing a string literal.

It’s not clear to me if our documentation actually guarantees we never shrink allocations when items are removed, but it’s certainly a design decision we’ve long held while implementing the Rust standard library. Certainly I wouldn’t be surprised to see e.g. Servo relying on it.

@Kimundi’s StableAddress trait currently assumes all bets are off if you take a mutable reference, so that’s encouraging.

@arielb1’s DerefPure trait will be pseudo-violate by this – DerefMut will be observably pure on its own, but Deref followed by DerefMut is observably impure.

Pointer stability is the aspect that worries me the most. I could be convinced it’s not a big deal, though.

Latency Concerns

Some operations which are supposed to be O(1) will suddenly sometimes be O(n). This implies an O(n) operation was turned into an O(1) somewhere else, but it can sometimes matter where the expensive operation was. For instance, if the expensive operation suddenly starts happening in a latency-sensitive section of code, that’s a problem.

I’m pretty ambivalent about this. If someone Really Really cares they can do some dummy operation that triggers a COW. If this is significantly desirable we can provide an operation that for doing precisely this (I think reserve(0) will probably always work).

Exposing Capacity

The trickiest piece of implementation appears to be exposing capacity in a way that:

  • does the right thing if you use it to calculate the size of target buffers (cap = len)
  • does the right thing when fed into things like from_raw_parts (cap = 0)

edit: please see discussion below, this is the most difficult constraint, and may be intractable.

These appear to be fundamentally conflicting goals. I’m inclined to say that the first use-case is probably doing something wrong, and can be broken with abandon (in which case, we simply expose the capacity as stored – 0).

Our reserve APIs to take additional space, and not absolute space. This is because the overwhelming use-case is vec.reserve(size_of_thing_i_want_to_insert). So there’s no reason to include capacity in such a calculation.

If you want to know how big of a buffer you need to reserve for the contents of a buffer, you should be using len, and not capacity.

In the remaining cases, I expect cap = 0 will probably just do the right thing, in that it will tell you that you need a new buffer? I’m a bit concerned about underflow bugs.

If you reject this and want cap = len, then we need to add a into_raw_parts API that does cap = 0, and tell everyone using from_raw_parts to be sure they got cap from into_raw_parts. That’s a bit of a mess, IMO.

Should Vec Do It Too?

As noted in previous sections; the increased utility of O(1) operations on Vec makes me less comfortable with Vec itself supporting this operations. That’s about it.

Should String Provide is_unique/make_unique?

I’m too tired from writing this. Whatever.

17 Likes
18

@phaux It’s not clear to me why “interpolated string literals” should only produce String and not &'static str (when given const/static arguments of course). I think features like interpolation probably ought to remain orthogonal to how literal typing works.

@arthurprs I agree that “special-casing String to allow static backing data” is way too magical, not to mention totally unnecessary for solving the original problem. But in the interests of moving the conversation forward, which of the alternative solutions do you prefer? New syntax for “owned string literals”? A macro with a very short name? Doing nothing at all?

@elszben The immediate problem is that with a proposal that broad, you need far stronger motivation than what we have in this thread. I want the vast majority of potentially-expensive methods like .to_string() and .into() to be explicit most of the time (especially since .into() could mean practically anything), and don’t know of any compelling reason why that principle should be changed. And that’s before we get to any of the tricky questions about how this would actually work with generics and inference and the other implicit conversions that Rust does do today.

@Nemo157 “User-defined literals” (as C++ calls this feature) are something I’d probably support if designed well and given enough compelling examples, but I see it as solving a different set of problems. What makes to_string() on literals annoying to me isn’t the number of characters to type, it’s that we have to provide any kind of explicit annotation at all when it’s perfectly obvious to the type system that this string literal has to be a String instead of a &'static str, but it still makes me do one extra round of see error message -> edit code -> recompile before letting me see useful output again. To me user-defined literals are most compelling for libraries dealing with types like dates, times, SQL queries, etc. which won’t get dedicated literal syntax in the core language, but can reasonably be represented by a single string or number.

(I haven’t read gankro’s new post yet, but since I already typed up all this and that’s gonna take a while to digest I’ll just post this now)

19

I don’t imagine String is currently a lang item? (and this proposal seems to me like the sort of thing that would require it to become one)

(note: I am referring to the OP’s proposal, not the static string optimization)

1 Like
20

@Gankra Good post.

Regarding capacity: Searching the standard library, I find:

  • foo.capacity() - foo.len() on Vec<u8> in two places (libstd/sys/windows/pipe.rs, libstd/sys_common/io.rs), both as part of unsafe code that passes the uninitialized portion of the Vec to OS read functions;
  • foo.capacity() == foo.len() on Vec<u8> in the same libstd/sys/windows/pipe.rs, and on Vec<T> in libcollections/vec.rs. (In the latter case, capacity ≠ len is taken to mean that an element can be appended without reallocating.)

If capacity() returns 0, the first will overflow, and the second will allow out-of-bounds writes – both really bad. Of course, the stdlib itself can be changed, but external code may include similar logic. So I think capacity() returning 0 is unviable at least for Vec, and probably for String as well.

(But then, I agree that supporting statics in Vec is a bad idea anyway because of the cost on deref_mut; I didn’t think of doing it only for String.)

Also, nit: I don’t think any of pop, truncate, or clear would need to special-case static strings, unless you’re really concerned about capacity() staying the same; the static pointer is still valid with a reduced length.

4 Likes