git.iko.soy/rowtype-yoga/purescript-arraybuffer-builder
on e2ff47a help sign in
rowtype-yoga/purescript-arraybuffer-builder/src/Data/ArrayBuffer/Builder.purs
443 lines 16 kB history raw
1-- | This module provides a `Builder` monoid and a `PutM` monad
2-- | for serializing `Data.ArrayBuffer.Types.ArrayBuffer`s.
3-- | See the package README for usage examples.
4-- |
5-- | Writing to an `ArrayBuffer` is an `Effect`ful activity, so most
6-- | functions in this module must be run in a `MonadEffect` context.
7-- |
8-- | For operations for working with `ArrayBuffer`, see
9-- | module
10-- | [`Data.ArrayBuffer.ArrayBuffer`](https://pursuit.purescript.org/packages/purescript-arraybuffer/docs/Data.ArrayBuffer.ArrayBuffer)
11-- | in package __purescript-arraybuffer__.
12module Data.ArrayBuffer.Builder
13( PutM
14, Put
15, execPutM
16, execPut
17, subBuilder
18, putArrayBuffer
19, putUint8
20, putInt8
21, putUint16be
22, putUint16le
23, putInt16be
24, putInt16le
25, putUint32be
26, putUint32le
27, putInt32be
28, putInt32le
29, putFloat32be
30, putFloat32le
31, putFloat64be
32, putFloat64le
33, Builder
34, (<>>)
35, execBuilder
36, length
37, singleton
38, cons
39, snoc
40, encodeUint8
41, encodeInt8
42, encodeUint16be
43, encodeUint16le
44, encodeInt16be
45, encodeInt16le
46, encodeUint32be
47, encodeUint32le
48, encodeInt32be
49, encodeInt32le
50, encodeFloat32be
51, encodeFloat32le
52, encodeFloat64be
53, encodeFloat64le
55where
57import Prelude
59import Control.Monad.Writer.Trans (WriterT, execWriterT, tell, lift)
60import Data.ArrayBuffer.ArrayBuffer as AB
61import Data.ArrayBuffer.DataView as DV
62import Data.ArrayBuffer.Typed as AT
63import Data.ArrayBuffer.Types (ArrayBuffer, Uint8Array)
64import Data.Float32 (Float32)
65import Data.Maybe (Maybe(..))
66import Data.UInt (UInt)
67import Effect (Effect)
68import Effect.Class (class MonadEffect, liftEffect)
70-- | The `PutM` monad is a `WriterT Builder` transformer monad which
71-- | gives us do-notation for the `Builder` monoid. The base monad must be
72-- | a `MonadEffect`.
73-- |
74-- | To append `Builder`s in this monad call `tell`, or any of the `put*`
75-- | functions in this module.
76type PutM = WriterT Builder
78-- | The `PutM` type reified to `Effect`, in other words `WriterT Builder Effect`.
79type Put = PutM Effect
81-- | Monoidal builder for `ArrayBuffer`s.
82-- |
83-- | ### Left-associative `<>>` append operator
84-- |
85-- | __TL;DR__ You probably don't want to use the `Builder` monoid directly
86-- | in your code, it’s better to use the `PutM` monad with do-notation instead.
87-- |
88-- | The `Builder` monoid in this library is efficient when we `snoc` single
89-- | items onto the end of it, or when we only `cons` single items to the
90-- | beginning, but it can be less efficient when we are mixing `cons` and
91-- | `snoc`.
92-- | This matters when we're appending three or more `Builder`s
93-- | in one associative expression, because the
94-- | `Semigroup` append operator `<>` is right-associative.
95-- |
96-- | To solve this, we provide an operator `<>>` for appending `Builders`.
97-- | `<>>` is exactly the same as `<>`, but left-associative.
98-- | This only matters when we're chaining together three
99-- | or more `Builder`s in a single associative expression.
100-- | Instead of
101-- | ```
102-- | builder₁ <> builder₂ <> builder₃
103-- | ```
104-- | we should always prefer to
105-- | write
106-- | ```
107-- | builder₁ <>> builder₂ <>> builder₃
108-- | ```
109-- | so that we get the efficient
110-- | `snoc`ing of `Builder`s.
111-- |
112-- | If we build our `ArrayBuffer`s with the `PutM` monad instead of appending by
113-- | using the `Semigroup` instance of `Builder`, then we always get the efficient
114-- | `snoc` case.
115-- |
116data Builder
117 = Node Builder ArrayBuffer Builder
118 | Null
120instance semigroupBuilder :: Semigroup Builder where
121 append Null Null = Null
122 append l Null = l
123 append Null r = r
124 append l (Node Null rx rr) = Node l rx rr -- this is the snoc case
125 append (Node ll lx Null) r = Node ll lx r -- found the rightmost Null
126 -- of the left tree
127 append (Node ll lx lr) r = Node ll lx $ append lr r -- search down the right
128 -- side of the left tree
129 -- to find the rightmost
130 -- Null
132infixl 5 append as <>>
134instance monoidBuilder :: Monoid Builder where
135 mempty = Null
137-- | `Builder` is not an instance of `Foldable` because `Builder` is monomorphic.
138foldl :: forall b. (b -> ArrayBuffer -> b) -> b -> Builder -> b
139foldl f a Null = a
140foldl f a (Node l x r) = foldl f (f (foldl f a l) x) r
142-- | Monomorphic foldM copied from
143-- | [`Data.Foldable.foldM`](https://pursuit.purescript.org/packages/purescript-foldable-traversable/4.1.1/docs/Data.Foldable#v:foldM)
144foldM :: forall b m. (Monad m) => (b -> ArrayBuffer -> m b) -> b -> Builder -> m b
145foldM f a0 = foldl (\ma b -> ma >>= flip f b) (pure a0)
147-- | Construct a `Builder` with a single `ArrayBuffer`. *O(1)*
148singleton :: ArrayBuffer -> Builder
149singleton buf = Node Null buf Null
151-- | Prepend an `ArrayBuffer` to the beginning of the `Builder`. *O(1)*
152cons :: ArrayBuffer -> Builder -> Builder
153cons x bs = Node Null x bs
155-- | Append an `ArrayBuffer` to the end of the `Builder`. *O(1)*
156snoc :: Builder -> ArrayBuffer -> Builder
157snoc bs x = Node bs x Null
159-- | Calculate the total byte length of the `Builder`. *O(n)*
160length :: Builder -> Int
161length bldr = foldl (\b a -> b + AB.byteLength a) 0 bldr
163-- | Build a single `ArrayBuffer` from a `Builder`. *O(n)*
164execBuilder :: forall m. (MonadEffect m) => Builder -> m ArrayBuffer
165execBuilder bldr = do
166 let buflen = foldl (\b a -> b + AB.byteLength a) 0 bldr
167 -- Allocate the final ArrayBuffer
168 buf <- liftEffect $ AB.empty buflen
169 -- Then copy each ArrayBuffer into the final ArrayBuffer.
170 -- To memcpy from one ArrayBuffer to another, apparently we have to first view
171 -- both ArrayBuffers as ArrayView (Typed Array).
172 newview <- liftEffect (AT.whole buf :: Effect Uint8Array)
173 _ <- foldM
174 ( \offset a -> do
175 aview <- liftEffect (AT.whole a :: Effect Uint8Array)
176 _ <- liftEffect $ AT.setTyped newview (Just offset) aview
177 pure $ offset + AB.byteLength a
178 ) 0 bldr
179 pure buf
181-- | Build an `ArrayBuffer` with do-notation in any `MonadEffect`. *O(n)*
182execPutM :: forall m. (MonadEffect m) => PutM m Unit -> m ArrayBuffer
183execPutM = execBuilder <=< execWriterT
185-- | Build an `ArrayBuffer` with do-notation. *O(n)*
186execPut :: Put Unit -> Effect ArrayBuffer
187execPut = execPutM
189-- | Build up a sub-`Builder` without `tell`ing it to the `Writer` yet.
190-- |
191-- | One case where we might want to call a `subBuilder` is when
192-- | serializing length-prefixed messages in some protocol. In that case,
193-- | we must serialize the message first, calculate the message length,
194-- | append the message length, and then append the message.
195-- |
196-- | In a `PutM` monad do-block, we can
197-- |
198-- |
199-- | ```
200-- | do
201-- | messageBuilder <- subBuilder $ do
202-- | putField1
203-- | putField2
204-- |
205-- | putInt32be $ length messageBuilder
206-- | tell messageBuilder
207-- | ```
208subBuilder :: forall m. (MonadEffect m) => PutM m Unit -> PutM m Builder
209subBuilder = lift <<< execWriterT
211-- | Append an `ArrayBuffer` to the builder.
212putArrayBuffer :: forall m. (MonadEffect m) => ArrayBuffer -> PutM m Unit
213putArrayBuffer = tell <<< singleton
215-- | Serialize an 8-bit unsigned integer (byte) into a new `ArrayBuffer`.
216encodeUint8 :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
217encodeUint8 x = do
218 buf <- liftEffect $ AB.empty 1
219 _ <- liftEffect $ DV.setUint8 (DV.whole buf) 0 x
220 pure buf
222-- | Append an 8-bit unsigned integer (byte) to the builder.
223putUint8 :: forall m. (MonadEffect m) => UInt -> PutM m Unit
224putUint8 = putArrayBuffer <=< encodeUint8
226-- | Serialize an 8-bit two’s-complement signed integer (char) into a new `ArrayBuffer`.
227encodeInt8 :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
228encodeInt8 x = do
229 buf <- liftEffect $ AB.empty 1
230 _ <- liftEffect $ DV.setInt8 (DV.whole buf) 0 x
231 pure buf
233-- | Append an 8-bit two’s-complement signed integer (char) to the builder.
234putInt8 :: forall m. (MonadEffect m) => Int -> PutM m Unit
235putInt8 = putArrayBuffer <=< encodeInt8
237-- | Serialize a 16-bit big-endian unsigned integer into a new `ArrayBuffer`.
238encodeUint16be :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
239encodeUint16be x = do
240 buf <- liftEffect $ AB.empty 2
241 _ <- liftEffect $ DV.setUint16be (DV.whole buf) 0 x
242 pure buf
244-- | Append a 16-bit big-endian unsigned integer to the builder.
245putUint16be :: forall m. (MonadEffect m) => UInt -> PutM m Unit
246putUint16be = putArrayBuffer <=< encodeUint16be
248-- | Serialize a 16-bit little-endian unsigned integer into a new `ArrayBuffer`.
249encodeUint16le :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
250encodeUint16le x = do
251 buf <- liftEffect $ AB.empty 2
252 _ <- liftEffect $ DV.setUint16le (DV.whole buf) 0 x
253 pure buf
255-- | Append a 16-bit little-endian unsigned integer to the builder.
256putUint16le :: forall m. (MonadEffect m) => UInt -> PutM m Unit
257putUint16le = putArrayBuffer <=< encodeUint16le
259-- | Serialize a 16-bit big-endian two’s-complement signed integer into a new `ArrayBuffer`.
260encodeInt16be :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
261encodeInt16be x = do
262 buf <- liftEffect $ AB.empty 2
263 _ <- liftEffect $ DV.setInt16be (DV.whole buf) 0 x
264 pure buf
266-- | Append a 16-bit big-endian two’s-complement signed integer to the builder.
267putInt16be :: forall m. (MonadEffect m) => Int -> PutM m Unit
268putInt16be = putArrayBuffer <=< encodeInt16be
270-- | Serialize a 16-bit little-endian two’s-complement signed integer into a new `ArrayBuffer`.
271encodeInt16le :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
272encodeInt16le x = do
273 buf <- liftEffect $ AB.empty 2
274 _ <- liftEffect $ DV.setInt16le (DV.whole buf) 0 x
275 pure buf
277-- | Append a 16-bit little-endian two’s-complement signed integer to the builder.
278putInt16le :: forall m. (MonadEffect m) => Int -> PutM m Unit
279putInt16le = putArrayBuffer <=< encodeInt16le
281-- | Serialize a 32-bit big-endian unsigned integer into a new `ArrayBuffer`.
282encodeUint32be :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
283encodeUint32be x = do
284 buf <- liftEffect $ AB.empty 4
285 _ <- liftEffect $ DV.setUint32be (DV.whole buf) 0 x
286 pure buf
288-- | Append a 32-bit big-endian unsigned integer to the builder.
289putUint32be :: forall m. (MonadEffect m) => UInt -> PutM m Unit
290putUint32be = putArrayBuffer <=< encodeUint32be
292-- | Serialize a 32-bit little-endian unsigned integer into a new `ArrayBuffer`.
293encodeUint32le :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
294encodeUint32le x = do
295 buf <- liftEffect $ AB.empty 4
296 _ <- liftEffect $ DV.setUint32le (DV.whole buf) 0 x
297 pure buf
299-- | Append a 32-bit little-endian unsigned integer to the builder.
300putUint32le :: forall m. (MonadEffect m) => UInt -> PutM m Unit
301putUint32le = putArrayBuffer <=< encodeUint32le
303-- | Serialize a 32-bit big-endian two’s-complement signed integer into a new `ArrayBuffer`.
304encodeInt32be :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
305encodeInt32be x = do
306 buf <- liftEffect $ AB.empty 4
307 _ <- liftEffect $ DV.setInt32be (DV.whole buf) 0 x
308 pure buf
310-- | Append a 32-bit big-endian two’s-complement signed integer to the builder.
311putInt32be :: forall m. (MonadEffect m) => Int -> PutM m Unit
312putInt32be = putArrayBuffer <=< encodeInt32be
314-- | Serialize a 32-bit little-endian two’s-complement signed integer into a new `ArrayBuffer`.
315encodeInt32le :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
316encodeInt32le x = do
317 buf <- liftEffect $ AB.empty 4
318 _ <- liftEffect $ DV.setInt32le (DV.whole buf) 0 x
319 pure buf
321-- | Append a 32-bit little-endian two’s-complement signed integer to the builder.
322putInt32le :: forall m. (MonadEffect m) => Int -> PutM m Unit
323putInt32le = putArrayBuffer <=< encodeInt32le
325-- | Serialize a 32-bit big-endian IEEE single-precision float into a new `ArrayBuffer`.
326encodeFloat32be :: forall m. (MonadEffect m) => Float32 -> m ArrayBuffer
327encodeFloat32be x = do
328 buf <- liftEffect $ AB.empty 4
329 _ <- liftEffect $ DV.setFloat32be (DV.whole buf) 0 x
330 pure buf
332-- | Append a 32-bit big-endian IEEE single-precision float to the builder.
333putFloat32be :: forall m. (MonadEffect m) => Float32 -> PutM m Unit
334putFloat32be = putArrayBuffer <=< encodeFloat32be
336-- | Serialize a 32-bit little-endian IEEE single-precision float into a new `ArrayBuffer`.
337encodeFloat32le :: forall m. (MonadEffect m) => Float32 -> m ArrayBuffer
338encodeFloat32le x = do
339 buf <- liftEffect $ AB.empty 4
340 _ <- liftEffect $ DV.setFloat32le (DV.whole buf) 0 x
341 pure buf
343-- | Append a 32-bit little-endian IEEE single-precision float to the builder.
344putFloat32le :: forall m. (MonadEffect m) => Float32 -> PutM m Unit
345putFloat32le = putArrayBuffer <=< encodeFloat32le
347-- | Serialize a 64-bit big-endian IEEE double-precision float into a new `ArrayBuffer`.
348encodeFloat64be :: forall m. (MonadEffect m) => Number -> m ArrayBuffer
349encodeFloat64be x = do
350 buf <- liftEffect $ AB.empty 8
351 _ <- liftEffect $ DV.setFloat64be (DV.whole buf) 0 x
352 pure buf
354-- | Append a 64-bit big-endian IEEE double-precision float to the builder.
355putFloat64be :: forall m. (MonadEffect m) => Number -> PutM m Unit
356putFloat64be = putArrayBuffer <=< encodeFloat64be
358-- | Serialize a 64-bit little-endian IEEE double-precision float into a new `ArrayBuffer`.
359encodeFloat64le :: forall m. (MonadEffect m) => Number -> m ArrayBuffer
360encodeFloat64le x = do
361 buf <- liftEffect $ AB.empty 8
362 _ <- liftEffect $ DV.setFloat64le (DV.whole buf) 0 x
363 pure buf
365-- | Append a 64-bit little-endian IEEE double-precision float to the builder.
366putFloat64le :: forall m. (MonadEffect m) => Number -> PutM m Unit
367putFloat64le = putArrayBuffer <=< encodeFloat64le
370-- ## Implementation Details
371--
372-- We want our `Builder` to be a data structure with
373-- * *O(1)* monoid append
374-- * *O(n)* fold
375--
376-- Our `Builder` implementation is an unbalanced binary tree.
377--
378-- For monoid `append`, what we actually get is *O(1)* when either the
379-- left or right tree is a singleton. If that's not true, then in the
380-- unlikely worst case `append` might be *O(n)*.
381--
382-- `Builder` is optimized what we consider to be normal usage, that is,
383-- `snoc`ing singleton elements to the end of the `Builder`.
384--
385-- If a Builder is built entirely by `snoc`ing, it will look like a
386-- left-only binary tree, a.k.a. a linked list.
387--
388-- ```
389-- ④
390-- ╱
391-- ③
392-- ╱
393-- ②
394-- ╱
395-- ①
396-- ```
397--
398-- If two of these `snoc`-built trees are `append`ed, then the new tree
399-- will look like
400--
401-- ```
402-- ④
403-- ╱ ╲
404-- ③ ⑧
405-- ╱ ╱
406-- ② ⑦
407-- ╱ ╱
408-- ① ⑥
409-- ╱
410-- ⑤
411-- ```
412--
413-- This is all similar to
414-- [__bytestring-tree-builder__](https://hackage.haskell.org/package/bytestring-tree-builder)
415-- , except that the
416-- [`Tree`](https://hackage.haskell.org/package/bytestring-tree-builder-0.2.7.3/docs/src/ByteString.TreeBuilder.Tree.html#Tree)
417-- structure in __bytestring-tree-builder__ only carries values in its
418-- leaves, which is how it achieves *O(1)* appending, at the cost of
419-- a higher coefficient time factor on the fold.
420--
421-- We hope that this implementation is fairly fast, but we
422-- haven't chosen this implementation because it's fast, we've chosen
423-- this implementation because it's simple.
424-- If someone wants to create a fast Purescript ArrayBuffer serialization
425-- library, then they can benchmark against this one to prove that the new
426-- one is fast.
427--
428-- One relatively cheap and simple performance improvement for this library would be to
429-- remove the Null constructor of `Builder` and instead use Javascript nulls.
430--
431-- In the longer term, it might make sense to try to change the Builder so
432-- that it works like the
433-- https://hackage.haskell.org/package/bytestring/docs/Data-ByteString-Builder.html
434--
435-- Here are some benchmarks of different Haskell ByteString builders
436-- https://github.com/haskell-perf/strict-bytestring-builders
437--
438-- We've tried to design the API for this library with minimal assumptions,
439-- so that if we want to change the Builder implementation later then we can.
440--
441-- Another way this could go:
442-- https://kodimensional.dev/posts/2019-03-25-comonadic-builders