I propose this version, which does not impose any limit on Sys.max_string_length:

let concat sep l =
  match l with
  | [] -> ""
  | hd :: tl ->
      let len = ref (length hd) in
      let sep_len = length sep in
      List.iter
        (fun s ->
          let old_len = !len in
          len := old_len + sep_len + length s;
          if !len < old_len then invalid_arg "String.concat" (* overflow *)
        )
        tl;
      if !len > Sys.max_string_length then invalid_arg "String.concat";
      let r = B.create !len in
      unsafe_blit hd 0 r 0 (length hd);
      let pos = ref(length hd) in
      List.iter
        (fun s ->
          unsafe_blit sep 0 r !pos sep_len;
          pos := !pos + sep_len;
          unsafe_blit s 0 r !pos (length s);
          pos := !pos + length s)
        tl;
      Bytes.unsafe_to_string r

Also, you should add @yallop's example (from #805) to the test suite and add a Changes entry.

@damiendoligez: I think your version is fine. I'll just point out that it's still a bit longer (and slower, and IMO more complex) than my original, once the one step unrolling and the auxiliary exception are removed:

let check_pos v = if v < 0 then invalid_arg "String.concat" else v

let rec sum_lengths acc seplen = function
  | [] -> acc
  | [x] -> length x + acc
  | hd :: tl -> sum_lengths (check_pos (length hd + seplen + acc)) seplen tl

let rec concat sep l =
  match l with
  | [] -> ""
  | hd :: tl ->
    let sep_len = length sep in
    let r = B.create (sum_lengths 0 sep_len l) in
    unsafe_blit hd 0 r 0 (length hd);
    let pos = ref(length hd) in
    List.iter
      (fun s ->
        unsafe_blit sep 0 r !pos sep_len;
        pos := !pos + sep_len;
        unsafe_blit s 0 r !pos (length s);
        pos := !pos + length s)
      tl;
    Bytes.unsafe_to_string r

(mostly untested)

To be fair, I do still have the assumption that max_string_length is less than half max_int. But that assumption is thoroughly baked into the runtime and standard library so I'm not especially troubled by it.

[Edit: now tested.]

I've switch to @damiendoligez 's version.

that assumption is thoroughly baked into the runtime and standard library so I'm not especially troubled by it.

JS backends have their own runtime, so this should be fine. Do you see other places in the stdlib which makes this assumption?

Do you see other places in the stdlib which makes this assumption?

Yes, but I don't think that this is the place for that discussion. If it's a problem then it's a problem for the js backends, and not for any of the proposed implementations of concat.

If the stdlib depends on a undocumented invariant of our runtime system which is potentially broken by alternative runtimes, it is certainly a problem on OCaml's side and once we are aware of this problem, we should not introduce more of it. I'd be fine documenting that max_string_length < max_int / 2 if there is a strong reason to require it, but it seems just better and more friendly to maintainers of alternative runtimes to lift this assumption assuming it is not too difficult to do so.

If the stdlib depends on a undocumented invariant of our runtime system which is potentially broken by alternative runtimes, it is certainly a problem on OCaml's side and once we are aware of this problem, we should not introduce more of it.

Have you changed your mind about this since opening this issue?

Have you changed your mind about this since opening this issue?

No, I said it was probably harmless, but if it is easy enough to fix without obvious drawbacks, it's worth doing it.

Here's another implementation, which is

• smaller (16 non-blank lines)
• simpler (no references, only one conditional, besides patterns) and
• faster (25% faster than the stdlib on @alainfrisch's benchmark)

than any of the other implementations so far:

let check_pos v = if v < 0 then invalid_arg "String.concat" else v

let rec sum_lengths acc seplen = function
  | [] -> acc
  | [x] -> length x + acc
  | hd :: tl -> sum_lengths (check_pos (length hd + seplen + acc)) seplen tl

let rec unsafe_blits dst pos sep seplen = function
    [] -> dst
  | [x] ->
    unsafe_blit x 0 dst pos (length x); dst
  | hd :: tl ->
    unsafe_blit hd 0 dst pos (length hd);
    unsafe_blit sep 0 dst (pos + length hd) seplen;
    unsafe_blits dst (pos + length hd + seplen) sep seplen tl

let concat sep l =
  let sep_len = length sep in
  unsafe_blits (B.create (sum_lengths 0 sep_len l)) 0 sep sep_len l

I've added the test and an entry in Changes.

FWIW, I like @yallop's latest proposal, modulo that it'd be better to lift the assumption on max_string_length, considering that it's not more complex (let l = length hd + seplen +acc in if l < acc then invalid_arg ... else l).

FWIW, I like @yallop's latest proposal

Thank you. That's the nicest thing anyone's said about my code in at least the last 62 comments.

modulo that it'd be better to lift the assumption on max_string_length

I'm happy to do that.

Here's a version that doesn't make assumptions about max_string_length:

let ensure_ge x y = if x >= y then x else invalid_arg "String.concat"

let rec sum_lengths acc seplen = function
  | [] -> acc
  | hd :: [] -> length hd + acc
  | hd :: tl -> sum_lengths (ensure_ge (length hd + seplen + acc) acc) seplen tl

let rec unsafe_blits dst pos sep seplen = function
    [] -> dst
  | hd :: [] ->
    unsafe_blit hd 0 dst pos (length hd); dst
  | hd :: tl ->
    unsafe_blit hd 0 dst pos (length hd);
    unsafe_blit sep 0 dst (pos + length hd) seplen;
    unsafe_blits dst (pos + length hd + seplen) sep seplen tl

let concat sep l =
  let seplen = length sep in
  unsafe_blits (B.create (sum_lengths 0 seplen l)) 0 sep seplen l |> bts

We can still get an invalid_arg with a string different from String.concat is the total length is greater than max_string_length (but without int overflow). I think this might be worth fixing by checking explicitly the resulting size. Also, an int overflow could still occur on the final length hd + acc.

I've pushed a version close to @yallop's latest proposal, adding an explicit check against max_string_length, protecting the final sum against int overflow, and adding a fast path for the case where the list is empty (avoiding allocation in that case).

@alainfrisch I think the cases you mention are handled by B.create.

What do you mean? Today, Bytes.create 0 != Bytes.create 0. And clearly, it raises Invalid_argument "String.create", not Invalid_argument "Bytes.concat".

(If/when strings were/are really immutable, one could also optimize the case of a list with a single element in String.concat.)

What do you mean?

If sum_length overflows B.create will raise.

I prefer the code as it was, without assert false, physical equality, if/else branches, code duplication, etc.

Checking for overflow multiple times (before and within create) should be avoided. It would be better to have create take the name of the calling function as an additional parameter.

Here's a version that incorporates @alainfrisch's two proposed improvements (optimization of the empty list case and more consistent error reporting):

let ensure_ge x y = if x >= y then x else invalid_arg "String.concat"

let rec sum_lengths acc seplen = function
  | [] -> acc
  | hd :: [] -> length hd + acc
  | hd :: tl -> sum_lengths (ensure_ge (length hd + seplen + acc) acc) seplen tl

let rec unsafe_blits dst pos sep seplen = function
    [] -> dst
  | hd :: [] ->
    unsafe_blit hd 0 dst pos (length hd); dst
  | hd :: tl ->
    unsafe_blit hd 0 dst pos (length hd);
    unsafe_blit sep 0 dst (pos + length hd) seplen;
    unsafe_blits dst (pos + length hd + seplen) sep seplen tl

let concat sep = function
    [] -> ""
  | l -> let seplen = length sep in bts @@
          unsafe_blits 
            (B.create ~caller:"String.concat" (sum_lengths 0 seplen l))
            0 sep seplen l

Bytes.create will also need to be changed to accept an optional ?caller argument. Actually, it would be a useful improvement to the standard library as a whole if internal functions that raised exceptions were to take an optional argument with the name of the caller. There are several places where the name of an internal function currently appears in an exception argument, and it's an easy fix.

I really like @yallop's latest version: it's fast and readable, quite perfect.

But I would remove the ?caller argument:

• Bytes.create is not just an internal function: it has a public interface, so changing it is a rather big deal.
• I don't think having the wrong message in Invalid_argument is such a big problem: the users have tools (backtraces and debuggers) to figure out where it really comes from.

While I agree that it might be a good idea to add a ?caller argument to a bunch of stdlib functions, I think it's a topic for another PR (and long discussion about the relative speed of double-checking, passing an optional argument, and setting up an exception handler in various back-ends). In this one we should concentrate on fixing the bug at hand.

Also, I want to cherry-pick this PR into 4.04 but I won't do it with the change to Bytes.create.

@damiendoligez: I'm fine with removing ?caller (and will consider proposing some variant of it in a separate PR). Is there anything you need from me to make cherry-picking into 4.04 easier?

@yallop I assume opening a PR with your latest version - ?caller would be needed...

See #833.

This is superseded by #833, right? Can we close it?