bit_string.concat

6 files changed, 182 insertions, 72 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index c32a2ff..83a9665 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -2,6 +2,7 @@
 
 ## Unreleased
 
+- The `bit_string` module gains the `concat` function.
 - The `os` module has been moved to the `gleam_os` library.
 - The `rescue` function has been removed from the `function` library in favour
   of target specific versions in Erlang and JavaScript specific libraries.
diff --git a/src/gleam/bit_builder.gleam b/src/gleam/bit_builder.gleam
index f74f517..926e542 100644
--- a/src/gleam/bit_builder.gleam
+++ b/src/gleam/bit_builder.gleam
@@ -1,6 +1,7 @@
-if erlang {
-  import gleam/string_builder.{StringBuilder}
+import gleam/string_builder.{StringBuilder}
+import gleam/bit_string
 
+if erlang {
   /// BitBuilder is a type used for efficiently concatenating bits to create bit
   /// strings.
   ///
@@ -14,89 +15,157 @@ if erlang {
   /// bit string using the `to_bit_string` function.
   ///
   pub external type BitBuilder
+}
 
-  /// Prepends a bit string to the start of a builder.
-  ///
-  /// Runs in constant time.
+if javascript {
+  /// BitBuilder is a type used for efficiently concatenating bits to create bit
+  /// strings.
   ///
-  pub fn prepend(to: BitBuilder, prefix: BitString) -> BitBuilder {
-    append_builder(from_bit_string(prefix), to)
-  }
-
-  /// Appends a bit string to the end of a builder.
+  /// If we append one bit string to another the bit strings must be copied to a
+  /// new location in memory so that they can sit together. This behaviour
+  /// enables efficient reading of the string but copying can be expensive,
+  /// especially if we want to join many bit strings together.
   ///
-  /// Runs in constant time.
+  /// BitBuilder is different in that it can be joined together in constant
+  /// time using minimal memory, and then can be efficiently converted to a
+  /// bit string using the `to_bit_string` function.
   ///
-  pub fn append(to: BitBuilder, suffix: BitString) -> BitBuilder {
-    append_builder(to, from_bit_string(suffix))
+  pub opaque type BitBuilder {
+    Leaf(BitString)
+    Branch(List(BitBuilder))
   }
+}
 
-  /// Prepends a builder onto the start of another.
-  ///
-  /// Runs in constant time.
-  ///
-  pub fn prepend_builder(to: BitBuilder, prefix: BitBuilder) -> BitBuilder {
-    append_builder(prefix, to)
-  }
+/// Prepends a bit string to the start of a builder.
+///
+/// Runs in constant time.
+///
+pub fn prepend(to: BitBuilder, prefix: BitString) -> BitBuilder {
+  append_builder(from_bit_string(prefix), to)
+}
 
-  /// Appends a builder onto the end of another.
-  ///
-  /// Runs in constant time.
-  ///
-  pub external fn append_builder(
+/// Appends a bit string to the end of a builder.
+///
+/// Runs in constant time.
+///
+pub fn append(to: BitBuilder, suffix: BitString) -> BitBuilder {
+  append_builder(to, from_bit_string(suffix))
+}
+
+/// Prepends a builder onto the start of another.
+///
+/// Runs in constant time.
+///
+pub fn prepend_builder(to: BitBuilder, prefix: BitBuilder) -> BitBuilder {
+  append_builder(prefix, to)
+}
+
+/// Appends a builder onto the end of another.
+///
+/// Runs in constant time.
+///
+pub fn append_builder(
+  to first: BitBuilder,
+  suffix second: BitBuilder,
+) -> BitBuilder {
+  do_append_builder(first, second)
+}
+
+if erlang {
+  external fn do_append_builder(
     to: BitBuilder,
     suffix: BitBuilder,
   ) -> BitBuilder =
     "gleam_stdlib" "iodata_append"
+}
 
-  /// Prepends a string onto the start of a builder.
-  ///
-  /// Runs in constant time.
-  ///
-  pub fn prepend_string(to: BitBuilder, prefix: String) -> BitBuilder {
-    append_builder(from_string(prefix), to)
+if javascript {
+  fn do_append_builder(first: BitBuilder, second: BitBuilder) -> BitBuilder {
+    Branch([first, second])
   }
+}
 
-  /// Appends a string onto the end of a builder.
-  ///
-  /// Runs in constant time.
-  ///
-  pub fn append_string(to: BitBuilder, suffix: String) -> BitBuilder {
-    append_builder(to, from_string(suffix))
-  }
+/// Prepends a string onto the start of a builder.
+///
+/// Runs in constant time.
+///
+pub fn prepend_string(to: BitBuilder, prefix: String) -> BitBuilder {
+  append_builder(from_string(prefix), to)
+}
 
-  /// Joins a list of builders into a single builders.
-  ///
-  /// Runs in constant time.
-  ///
-  pub external fn concat(List(BitBuilder)) -> BitBuilder =
+/// Appends a string onto the end of a builder.
+///
+/// Runs in constant time.
+///
+pub fn append_string(to: BitBuilder, suffix: String) -> BitBuilder {
+  append_builder(to, from_string(suffix))
+}
+
+/// Joins a list of builders into a single builders.
+///
+/// Runs in constant time.
+///
+pub fn concat(builders: List(BitBuilder)) -> BitBuilder {
+  do_concat(builders)
+}
+
+if erlang {
+  external fn do_concat(List(BitBuilder)) -> BitBuilder =
     "gleam_stdlib" "identity"
+}
 
-  /// Creates a new builder from a string.
-  ///
-  /// Runs in constant time.
-  ///
-  pub external fn from_string(String) -> BitBuilder =
-    "gleam_stdlib" "wrap_list"
+if javascript {
+  fn do_concat(builders: List(BitBuilder)) -> BitBuilder {
+    Branch(builders)
+  }
+}
 
+/// Creates a new builder from a string.
+///
+/// Runs in constant time when running on Erlang.
+/// Runs in linear time otherwise.
+///
+pub fn from_string(string: String) -> BitBuilder {
+  string
+  |> bit_string.from_string
+  |> from_bit_string
+}
+
+if erlang {
   /// Creates a new builder from a string builder.
   ///
   /// Runs in constant time.
   ///
   pub external fn from_string_builder(StringBuilder) -> BitBuilder =
     "gleam_stdlib" "identity"
+}
 
-  /// Creates a new builder from a bit string.
-  ///
-  /// Runs in constant time.
-  ///
-  pub external fn from_bit_string(BitString) -> BitBuilder =
+/// Creates a new builder from a bit string.
+///
+/// Runs in constant time.
+///
+pub fn from_bit_string(bits: BitString) -> BitBuilder {
+  do_from_bit_string(bits)
+}
+
+if erlang {
+  external fn do_from_bit_string(BitString) -> BitBuilder =
     "gleam_stdlib" "wrap_list"
+}
 
+if javascript {
+  fn do_from_bit_string(bits: BitString) -> BitBuilder {
+    Leaf(bits)
+  }
+}
+
+if erlang {
   /// Turns an builder into a bit string.
   ///
-  /// This function is implemented natively by the virtual machine and is highly
-  /// optimised.
+  /// Runs in linear time.
+  ///
+  /// When running on Erlang this function is implemented natively by the
+  /// virtual machine and is highly optimised.
   ///
   pub external fn to_bit_string(BitBuilder) -> BitString =
     "erlang" "list_to_bitstring"
diff --git a/src/gleam/bit_string.gleam b/src/gleam/bit_string.gleam
index 1d203dc..6605ce9 100644
--- a/src/gleam/bit_string.gleam
+++ b/src/gleam/bit_string.gleam
@@ -42,17 +42,7 @@ if javascript {
 ///    from_string("butterfly")
 ///
 pub fn append(to first: BitString, suffix second: BitString) -> BitString {
-  do_append(first, second)
-}
-
-if erlang {
-  external fn do_append(BitString, BitString) -> BitString =
-    "gleam_stdlib" "bit_string_append"
-}
-
-if javascript {
-  external fn do_append(BitString, BitString) -> BitString =
-    "../gleam_stdlib.js" "bit_string_append"
+  concat([first, second])
 }
 
 if erlang {
@@ -119,3 +109,24 @@ if javascript {
   external fn do_to_string(BitString) -> Result(String, Nil) =
     "../gleam_stdlib.js" "bit_string_to_string"
 }
+
+/// Creates a new bit string by joining multiple binaries.
+///
+/// ## Examples
+///
+///    > concat([from_string("butter"), from_string("fly")])
+///    from_string("butterfly")
+///
+pub fn concat(bit_strings: List(BitString)) -> BitString {
+  do_concat(bit_strings)
+}
+
+if erlang {
+  external fn do_concat(List(BitString)) -> BitString =
+    "gleam_stdlib" "bit_string_concat"
+}
+
+if javascript {
+  external fn do_concat(List(BitString)) -> BitString =
+    "../gleam_stdlib.js" "bit_string_concat"
+}
diff --git a/src/gleam_stdlib.erl b/src/gleam_stdlib.erl
index fc1d17e..c3aa317 100644
--- a/src/gleam_stdlib.erl
+++ b/src/gleam_stdlib.erl
@@ -9,9 +9,9 @@
          string_ends_with/2, string_pad/4, decode_tuple2/1, decode_tuple3/1,
          decode_tuple4/1, decode_tuple5/1, decode_tuple6/1, decode_map/1,
          bit_string_int_to_u32/1, bit_string_int_from_u32/1, decode_result/1,
-         bit_string_append/2, bit_string_part_/3, decode_bit_string/1,
-         compile_regex/2, regex_match/2, regex_split/2, regex_scan/2,
-         base_decode64/1, wrap_list/1]).
+         bit_string_part_/3, decode_bit_string/1, compile_regex/2,
+         regex_match/2, regex_split/2, regex_scan/2, base_decode64/1,
+         wrap_list/1, bit_string_concat/1]).
 
 should_equal(Actual, Expected) -> 
     ?assertEqual(Expected, Actual),
@@ -171,8 +171,8 @@ string_pop_grapheme(String) ->
         _ -> {error, nil}
     end.
 
-bit_string_append(First, Second) ->
-    <<First/bitstring, Second/bitstring>>.
+bit_string_concat(BitStrings) ->
+    iolist_to_binary(BitStrings).
 
 bit_string_part_(Bin, Pos, Len) ->
     try {ok, binary:part(Bin, Pos, Len)}
diff --git a/src/gleam_stdlib.js b/src/gleam_stdlib.js
index 479b8a9..b63a4ea 100644
--- a/src/gleam_stdlib.js
+++ b/src/gleam_stdlib.js
@@ -189,6 +189,25 @@ export function bit_string_append(first, second) {
   return array;
 }
 
+function reduce_list(list, acc, f) {
+  let [current, next] = list;
+  while (next) {
+    acc = f(acc, current);
+    [current, next] = next;
+  }
+  return acc;
+}
+
+export function bit_string_concat(bit_strings) {
+  let size = reduce_list(bit_strings, 0, (size, b) => b.byteLength + size);
+  let array = new Uint8Array(size);
+  reduce_list(bit_strings, 0, (index, bit_string) => {
+    array.set(bit_string, index);
+    return index + bit_string.byteLength;
+  });
+  return array;
+}
+
 export function log(term) {
   console.log(term);
 }
diff --git a/test/gleam/bit_string_test.gleam b/test/gleam/bit_string_test.gleam
index 199e1cb..e86dd5d 100644
--- a/test/gleam/bit_string_test.gleam
+++ b/test/gleam/bit_string_test.gleam
@@ -23,6 +23,16 @@ pub fn append_test() {
   |> should.equal(<<1, 2, 3, 4>>)
 }
 
+pub fn concat_test() {
+  [<<1, 2>>]
+  |> bit_string.concat
+  |> should.equal(<<1, 2>>)
+
+  [<<1, 2>>, <<3>>, <<4>>]
+  |> bit_string.concat
+  |> should.equal(<<1, 2, 3, 4>>)
+}
+
 if erlang {
   pub fn part_test() {
     bit_string.from_string("hello")