Why is there a "must" for returning the string on the heap? Can't it be solved in the language to use the static string up to the point the reallocation is needed?
Rust has builtin types &'static str for strings that live for the entire runtime of the program and ~str for strings that live in dynamically managed heap memory (from the more general ~T for T that live there with T=str). If the function always returns a static string it can return the former type and won't need a ~ or any allocations for that.
If you need something more dynamic... you could have a user-defined type that can hold either and remembers whether it's responsible for freeing the memory, but that doesn't fall out of the builtin types naturally.
As far as I understand, the effective overhead of "free" can be practically zero if the compile-time construction of the static strings would contain some "nothing to deallocate here" info versus any info which anyway has to be run-time maintained to anything that is really allocated. Any non-trivial allocator has a bunch of checks to do (e.g. different-sized small objects are typically allocated in separate blocks, differently to the big allocations etc).
As soon as your language doesn't use C-like zero-terminated characters but anything with more information, it's trivial to avoid these unnecessary copy-to-heap-just-to-use-and-deallocate steps.
As other have said: it can be solved in the library by defining a string type with the appropriate semantics (e.g. the MaybeOwned[1] type they refer to).
