Mutable strings and Racket interop

[samth]

Rhombus now expects strings to be immutable rather pervasively. This is partly because String only matches Racket's immutable strings, even more so because a Map with the default hashing compares mutable and immutable strings differently. Unfortunately that has significant conflicts with runtime features that produce strings, like regular expressions and IO. So, for example this doesn't work (using @samdphillips rhombus/compat library):

import: rhombus/compat/port
import: lib("racket/base.rkt") as racket
let stdin :: InputPort = racket.#{current-input-port}()
let keys = {"sam": 5}
let input = keys[stdin.readline()]

No matter what you type in, it will never match the key. Similar problems arise with regular expression splitting of strings, and with other core Racket operations that produce strings.

I can think of a few approaches to take here (of course there could be some I haven't thought of):

1. Write Rhombus wrappers around the IO and regexp (and other) APIs, which convert from mutable to immutable strings. Using unsafe-string->immutable-string! can make this pretty fast, but it adds overhead to many Rhombus APIs.
2. Change the underlying primitives to produce immutable strings, and add wrappers on the Racket side. There are some compatibility concerns here about Racket programs that use the lower-level modules, plus the same drawbacks of wrappers for the Racket side, but it makes Rhombus faster.
3. Add flags throughout the various low-level APIs to specify which version to use (or duplicate the low-level APIs, which probably just pushes the flags further down). Avoids wrappers but makes the runtime code uglier and potentially slower.
4. Change the Racket APIs to just produce immutable strings. This has many virtues, and would have been the right choice at the start, but is backwards-incompatible on the Racket side.
5. Just let the above program be wrong once it's using the relevant Rhombus APIs. I think this is a non-starter.

I don't have a strong sense of what's best here, or whether there's a better choice that I haven't thought of yet, but it seems important to start thinking about this.

[samth]

As an aside, there should probably be a clearer printing of mutable strings than #'{"xxx"} since that reads as an immutable string.

[jackfirth]

My vote here is for option 2. It's backwards compatible while retaining the smallest legacy code and API surface possible. And I can add Resyntax rules to push people towards using immutable strings, so they don't have to remember to use the flags.

[AlexKnauth]

I'd go for option 1. Even for large strings, unsafe-string->immutable-string! should be a constant-time operation which will only slow down Rhombus operations relative to Racket a little. While option 2 would seem to require copying immutable strings into newly allocated mutable ones, a linear time operation in the length of the string, more time and space cost with option 2 for Racket than what option 1 would lose for Rhombus.

[mflatt]

I am also for option 1 generally, adding immutable-string variants of primitives to Racket as needed for performance.

[samth]

My biggest concern would be functions that produce data structures with strings in them, and that thus have to be traversed, such as regexp-match.

[mflatt]

I agree that those will require even more work. The regexp-match function in particular seems like something that should have a different API in Rhombus (e.g., based on names for submatches).

[jackfirth]

We could go with a hybrid between 1 and 2, where we don't add a flag to APIs that return strings directly but do add them to APIs that return strings inside structures.

[AlexKnauth]

That would be a hybrid between 1 and 3, but yeah, that makes sense.

[jackfirth]

I was thinking add a flag to the surface API, make the core API return immutable by default, and make the surface API copy to mutable if the flag isn't used.

[jackfirth]

Option 1 isn't safe if any of the mutable strings on the racket side get reused. Do we know for a fact that doesn't happen in any string APIs? I know that (string-append) (with no arguments) returns the same mutable empty string every time.

[mflatt]

Because current APIs return mutable strings, they generally have to produce fresh strings every time, and so unsafe-string->immutable-string! will be ok. But certainly unsafe-string->immutable-string! will have to be used with some care, and string->immutable-string may be fast enough to make it the right choice in most cases.

[AlexKnauth]

The shared mutable empty string case is a problem on the BC side:

$ ./racket/bin/racketbc
Welcome to Racket v8.8.0.9 [bc].
> (require rackunit racket/unsafe/ops)
> (void (unsafe-string->immutable-string! (string-append)))
> (check-false (immutable? (string-append)))
--------------------
FAILURE [,bt for context]
name:       check-false
location:   string:1:0
params:     '(#t)
--------------------

This test passes on CS but fails on BC.

[mflatt]

That seems like bad behavior by BC, and probably unsafe-string->immutable-string! needs to change to cooperate with string-append.

[mflatt]

(Or maybe unsafe-string->immutable-string! should generally not mutate an empty string in BC, since other functions may has a similar optimization.)

[jackfirth]

It definitely shouldn't, since there's an advantage to ensuring there's only one immutable empty string instance in the runtime.

[sorawee]

Racket switched lists from mutable to immutable. I see no reason why we can't do the same for strings, considering that the list change presumably was larger and affected more programs.

[jackfirth]

Those aren't quite breakages though, just usages of mutable strings. A breakage would be a program that relies on something like string-append currently returning a mutable string. Code that starts from scratch with make-string would be fine.

[AlexKnauth]

I had been thinking the 3 operations that would make sense to still return mutable strings would be string-copy, make-string, and build-string. But not all code will use one of those 3 operations before mutation. Some I see use list->string, read-line, read, (one used (apply string (string->list s)) with a comment saying it was to copy it into a mutable string, why not use string-copy there?).

I notice even those have something in common. All of them except string-copy do not take another string as input. With that as a guideline maybe the set of operations returning mutable strings should be expanded to:

• make-string
• string
• string-copy
• list->string
• build-string
• read, read-line, read-string, file->string, port->string, and so on
• get-output-string, call-with-output-string, and so on
• number->string, real->decimal-string
• format, ~a, ~s, ~v, ~r, and the rest of the formatting functions
• bytes->string/utf-8, bytes->string/locale, bytes->string/latin-1
• symbol->string
• keyword->string
• other various ->string conversion functions

Perhaps the only functions that would be changed to produce immutable strings would be functional string operations that take strings a produce strings based on those, in which case maybe they should simply preserve immutability when their inputs are immutable, and produce mutable strings when one of their inputs is mutable.

[AlexKnauth]

Although, here's an example of string-set! being used on a string produced by string-join: FPBench/src/core2cakeml.rkt:21

The strings inside the list passed to string-join are produced by string and format, so it seems good if those produce mutable strings and string-join only produces immutable if its inputs are immutable.

Edit: another example of string-set! being used on a string produced by string-append: sxml/sxml/ssax/input-parse.rkt:161. Again the strings inside string-append are produced by make-string, so it's good if string-append only produces immutable if its inputs are immutable.

[AlexKnauth]

I found an example that wouldn't be solved by making string-append etc. only produce immutable on immutable inputs in the Racket repo itself: racket/racket/src/schemify/infer-name.rkt:67.

(define (source->string src)
  (define str (if (string? src) src (path->string src)))
  (define short-str
    (cond
      [((string-length str) . < . 20) (string-copy str)]
      [else (string-append "..." (substring str (- (string-length str) 19)))]))
  (for ([i (in-range (string-length short-str))])
    (when (char=? #\\ (string-ref short-str i))
      (string-set! short-str i #\/)))
  short-str)

Assuming source->string can take an immutable string as input, when that string is long (length 20 or more) it uses string-append and substring with immutable string arguments, and then it expects the result to be mutable.

Edit: I found another example that wouldn't be solved by that: FARGish/cp1/scheme-experiments/m1.rkt:83. This program uses string-append with one argument, expecting that to convert a possibly-immutable string to a mutable string.

[samth]

While it might be easier to change multiple things all at once, having string-append and substring produce mutable strings too would not be a big issue from the Rhombus perspective. The important things to change are the places strings are produced in the runtime, as I said initially.

[mfelleisen]

“800” — that’s a small number. I expected more.

[gus-massa]

I'd like that only string-copy and make-string. I'm even not sure about build-string. It's extreme and it may be a backward compatibility nightmare.

Two ideas, I'm not sure about them:

1. Drop any guaranty about eq-ness of immutable strings, so the functions can return a fresh immutable string, or an old one. Even string->immutable-string is not guaranteed to return the same string when the argument is immutable, it may be an interned immutable string, or just an immutable string with the same content that the compiler/optimizer has available for some weird reason. The only guaranty is that string->immutable-string will not do something stupid and allocate a new string when the argument is an immutable string. Somewhat like flonums. [I think this is a good idea. It is just a warning in the docs, and remove any guarantee about reuse that is there.]

2. Under the hood, the result of all internal functions are fresh mutable strings, and the compiler adds string->immutable-string to transform the result into an immutable string. But the compiler/optimizer is aware of the freshness of the strings, and can transform the string->immutable-string into unsafe-string->immutable-string! and remove string-copy and apply other local optimizations. [It needs a very smart compiler. I think it's possible, but writing the code is always more difficult than talking. Also, it needs some tricks to reuse immutable strings when possible.]

[AlexKnauth]

Inspired by the discussion on normalizing-annotations / impersonator-annotations vs flat-annotations, here's what it would currently look like in terms of impersonator contracts:

(define (string->immutable-string-proj blame)
  (λ (s neg-party)
    (cond
      [(string? s) (string->immutable-string s)]
      [else
       (raise-blame-error blame #:missing-party neg-party s
                          '(expected "string?" given: "~e")
                          s)])))

(define ->immutable-string/c
  (make-contract
   #:name '->immutable-string/c
   #:first-order string?
   #:late-neg-projection string->immutable-string-proj))

With the ->immutable-string/c contract used in ways like this in a wrapper over existing racket functions that produce mutable strings, to traverse output and convert them to immutable ones:

(define/contract regexp-match/immutable
  (-> regexp?
      string?
      (or/c #f
            (cons/c ->immutable-string/c (listof (or/c ->immutable-string/c #f)))))
  regexp-match)

(define/contract regexp-match*/immutable
  (->* [regexp?
        string?]
       [#:match-select (or/c (list? . -> . (or/c any/c list?)) #f)]
       (listof (or/c ->immutable-string/c (listof (or/c #f ->immutable-string/c)))))
  regexp-match*)