git.iko.soy/rowtype-yoga/purescript-arraybuffer-builder
on e322220 help sign in
rowtype-yoga/purescript-arraybuffer-builder/src/Data/ArrayBuffer/Builder.purs
398 lines 15 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.
7module Data.ArrayBuffer.Builder
8( PutM
9, Put
10, execPutM
11, execPut
12, putArrayBuffer
13, putUint8
14, putInt8
15, putUint16be
16, putUint16le
17, putInt16be
18, putInt16le
19, putUint32be
20, putUint32le
21, putInt32be
22, putInt32le
23, putFloat32be
24, putFloat32le
25, putFloat64be
26, putFloat64le
27, Builder
28, (<>>)
29, execBuilder
30, singleton
31, snoc
32, encodeUint8
33, encodeInt8
34, encodeUint16be
35, encodeUint16le
36, encodeInt16be
37, encodeInt16le
38, encodeUint32be
39, encodeUint32le
40, encodeInt32be
41, encodeInt32le
42, encodeFloat32be
43, encodeFloat32le
44, encodeFloat64be
45, encodeFloat64le
47where
49import Prelude
51import Control.Monad.Writer.Trans (WriterT, execWriterT, tell)
52import Data.ArrayBuffer.ArrayBuffer as AB
53import Data.ArrayBuffer.DataView as DV
54import Data.ArrayBuffer.Typed as AT
55import Data.ArrayBuffer.Types (ArrayBuffer, Uint8Array)
56import Data.Float32 (Float32)
57import Data.Maybe (Maybe(..))
58import Data.UInt (UInt)
59import Effect (Effect)
60import Effect.Class (class MonadEffect, liftEffect)
62-- | The `PutM` monad is a Writer transformer monad which
63-- | [gives us access to do-notation](https://wiki.haskell.org/Do_notation_considered_harmful#Library_design)
64-- | for building `ArrayBuffer`s.
65type PutM = WriterT Builder
67-- | `Put` monad is the non-transformer version of `PutM`.
68type Put = PutM Effect
70-- | Monoidal builder for `ArrayBuffer`s.
71-- |
72-- | ### Left-associative `<>>` append operator
73-- |
74-- | __TL;DR__ You probably don't want to use the `Builder` monoid directly
75-- | in your code, it’s better to use the `PutM` monad with do-notation instead.
76-- |
77-- | The `Builder` monoid in this library is efficient when we `snoc` single
78-- | items onto the end of it, or when we only `cons` single items to the
79-- | beginning, but it can be less efficient when we are mixing `cons` and
80-- | `snoc`.
81-- | This matters when we're appending three or more `Builder`s
82-- | in one associative expression, because the
83-- | `Semigroup` append operator `<>` is right-associative.
84-- |
85-- | To solve this, we provide an operator `<>>` for appending `Builders`.
86-- | `<>>` is exactly the same as `<>`, but left-associative.
87-- | This only matters when we're chaining together three
88-- | or more `Builder`s in a single associative expression.
89-- | Instead of
90-- | ```
91-- | builder₁ <> builder₂ <> builder₃
92-- | ```
93-- | we should always prefer to
94-- | write
95-- | ```
96-- | builder₁ <>> builder₂ <>> builder₃
97-- | ```
98-- | so that we get the efficient
99-- | `snoc`ing of `Builder`s.
100-- |
101-- | If we build our `ArrayBuffer`s with the `PutM` monad instead of appending by
102-- | using the `Semigroup` instance of `Builder`, then we always get the efficient
103-- | `snoc` case.
104-- |
105data Builder
106 = Node Builder ArrayBuffer Builder
107 | Null
109instance semigroupBuilder :: Semigroup Builder where
110 append Null Null = Null
111 append l Null = l
112 append Null r = r
113 append l (Node Null rx rr) = Node l rx rr -- this is the snoc case
114 append (Node ll lx Null) r = Node ll lx r -- found the rightmost Null
115 -- of the left tree
116 append (Node ll lx lr) r = Node ll lx $ append lr r -- search down the right
117 -- side of the left tree
118 -- to find the rightmost
119 -- Null
121infixl 5 append as <>>
123instance monoidBuilder :: Monoid Builder where
124 mempty = Null
126-- | `Builder` is not an instance of `Foldable` because `Builder` is monomorphic.
127foldl :: forall b. (b -> ArrayBuffer -> b) -> b -> Builder -> b
128foldl f a Null = a
129foldl f a (Node l x r) = foldl f (f (foldl f a l) x) r
131-- | Monomorphic foldM copied from
132-- | [`Data.Foldable.foldM`](https://pursuit.purescript.org/packages/purescript-foldable-traversable/4.1.1/docs/Data.Foldable#v:foldM)
133foldM :: forall b m. (Monad m) => (b -> ArrayBuffer -> m b) -> b -> Builder -> m b
134foldM f a0 = foldl (\ma b -> ma >>= flip f b) (pure a0)
136-- | Construct a `Builder` with a single `ArrayBuffer`. *O(1)*
137singleton :: ArrayBuffer -> Builder
138singleton buf = Node Null buf Null
140-- | Add an `ArrayBuffer` to the end of the `Builder`. *O(1)*
141snoc :: Builder -> ArrayBuffer -> Builder
142snoc bs x = Node bs x Null
144-- | Build a single `ArrayBuffer` from a `Builder`. *O(n)*
145execBuilder :: forall m. (MonadEffect m) => Builder -> m ArrayBuffer
146execBuilder bldr = do
147 let buflen = foldl (\b a -> b + AB.byteLength a) 0 bldr
148 -- Allocate the final ArrayBuffer
149 buf <- liftEffect $ AB.empty buflen
150 -- Then copy each ArrayBuffer into the final ArrayBuffer.
151 -- To memcpy from one ArrayBuffer to another, apparently we have to first view
152 -- both ArrayBuffers as ArrayView (Typed Array).
153 newview <- liftEffect (AT.whole buf :: Effect Uint8Array)
154 _ <- foldM
155 ( \offset a -> do
156 aview <- liftEffect (AT.whole a :: Effect Uint8Array)
157 _ <- liftEffect $ AT.setTyped newview (Just offset) aview
158 pure $ offset + AB.byteLength a
159 ) 0 bldr
160 pure buf
162-- | Build an `ArrayBuffer` with do-notation in any `MonadEffect`. *O(n)*
163execPutM :: forall m. (MonadEffect m) => PutM m Unit -> m ArrayBuffer
164execPutM = execBuilder <=< execWriterT
166-- | Build an `ArrayBuffer` with do-notation. *O(n)*
167execPut :: Put Unit -> Effect ArrayBuffer
168execPut = execPutM
170-- | Append an `ArrayBuffer` to the builder.
171putArrayBuffer :: forall m. (MonadEffect m) => ArrayBuffer -> PutM m Unit
172putArrayBuffer = tell <<< singleton
174-- | Serialize an 8-bit unsigned integer (byte) into a new `ArrayBuffer`.
175encodeUint8 :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
176encodeUint8 x = do
177 buf <- liftEffect $ AB.empty 1
178 _ <- liftEffect $ DV.setUint8 (DV.whole buf) 0 x
179 pure buf
181-- | Append an 8-bit unsigned integer (byte) to the builder.
182putUint8 :: forall m. (MonadEffect m) => UInt -> PutM m Unit
183putUint8 = putArrayBuffer <=< encodeUint8
185-- | Serialize an 8-bit two’s-complement signed integer (char) into a new `ArrayBuffer`.
186encodeInt8 :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
187encodeInt8 x = do
188 buf <- liftEffect $ AB.empty 1
189 _ <- liftEffect $ DV.setInt8 (DV.whole buf) 0 x
190 pure buf
192-- | Append an 8-bit two’s-complement signed integer (char) to the builder.
193putInt8 :: forall m. (MonadEffect m) => Int -> PutM m Unit
194putInt8 = putArrayBuffer <=< encodeInt8
196-- | Serialize a 16-bit big-endian unsigned integer into a new `ArrayBuffer`.
197encodeUint16be :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
198encodeUint16be x = do
199 buf <- liftEffect $ AB.empty 2
200 _ <- liftEffect $ DV.setUint16be (DV.whole buf) 0 x
201 pure buf
203-- | Append a 16-bit big-endian unsigned integer to the builder.
204putUint16be :: forall m. (MonadEffect m) => UInt -> PutM m Unit
205putUint16be = putArrayBuffer <=< encodeUint16be
207-- | Serialize a 16-bit little-endian unsigned integer into a new `ArrayBuffer`.
208encodeUint16le :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
209encodeUint16le x = do
210 buf <- liftEffect $ AB.empty 2
211 _ <- liftEffect $ DV.setUint16le (DV.whole buf) 0 x
212 pure buf
214-- | Append a 16-bit little-endian unsigned integer to the builder.
215putUint16le :: forall m. (MonadEffect m) => UInt -> PutM m Unit
216putUint16le = putArrayBuffer <=< encodeUint16le
218-- | Serialize a 16-bit big-endian two’s-complement signed integer into a new `ArrayBuffer`.
219encodeInt16be :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
220encodeInt16be x = do
221 buf <- liftEffect $ AB.empty 2
222 _ <- liftEffect $ DV.setInt16be (DV.whole buf) 0 x
223 pure buf
225-- | Append a 16-bit big-endian two’s-complement signed integer to the builder.
226putInt16be :: forall m. (MonadEffect m) => Int -> PutM m Unit
227putInt16be = putArrayBuffer <=< encodeInt16be
229-- | Serialize a 16-bit little-endian two’s-complement signed integer into a new `ArrayBuffer`.
230encodeInt16le :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
231encodeInt16le x = do
232 buf <- liftEffect $ AB.empty 2
233 _ <- liftEffect $ DV.setInt16le (DV.whole buf) 0 x
234 pure buf
236-- | Append a 16-bit little-endian two’s-complement signed integer to the builder.
237putInt16le :: forall m. (MonadEffect m) => Int -> PutM m Unit
238putInt16le = putArrayBuffer <=< encodeInt16le
240-- | Serialize a 32-bit big-endian unsigned integer into a new `ArrayBuffer`.
241encodeUint32be :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
242encodeUint32be x = do
243 buf <- liftEffect $ AB.empty 4
244 _ <- liftEffect $ DV.setUint32be (DV.whole buf) 0 x
245 pure buf
247-- | Append a 32-bit big-endian unsigned integer to the builder.
248putUint32be :: forall m. (MonadEffect m) => UInt -> PutM m Unit
249putUint32be = putArrayBuffer <=< encodeUint32be
251-- | Serialize a 32-bit little-endian unsigned integer into a new `ArrayBuffer`.
252encodeUint32le :: forall m. (MonadEffect m) => UInt -> m ArrayBuffer
253encodeUint32le x = do
254 buf <- liftEffect $ AB.empty 4
255 _ <- liftEffect $ DV.setUint32le (DV.whole buf) 0 x
256 pure buf
258-- | Append a 32-bit little-endian unsigned integer to the builder.
259putUint32le :: forall m. (MonadEffect m) => UInt -> PutM m Unit
260putUint32le = putArrayBuffer <=< encodeUint32le
262-- | Serialize a 32-bit big-endian two’s-complement signed integer into a new `ArrayBuffer`.
263encodeInt32be :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
264encodeInt32be x = do
265 buf <- liftEffect $ AB.empty 4
266 _ <- liftEffect $ DV.setInt32be (DV.whole buf) 0 x
267 pure buf
269-- | Append a 32-bit big-endian two’s-complement signed integer to the builder.
270putInt32be :: forall m. (MonadEffect m) => Int -> PutM m Unit
271putInt32be = putArrayBuffer <=< encodeInt32be
273-- | Serialize a 32-bit little-endian two’s-complement signed integer into a new `ArrayBuffer`.
274encodeInt32le :: forall m. (MonadEffect m) => Int -> m ArrayBuffer
275encodeInt32le x = do
276 buf <- liftEffect $ AB.empty 4
277 _ <- liftEffect $ DV.setInt32le (DV.whole buf) 0 x
278 pure buf
280-- | Append a 32-bit little-endian two’s-complement signed integer to the builder.
281putInt32le :: forall m. (MonadEffect m) => Int -> PutM m Unit
282putInt32le = putArrayBuffer <=< encodeInt32le
284-- | Serialize a 32-bit big-endian IEEE single-precision float into a new `ArrayBuffer`.
285encodeFloat32be :: forall m. (MonadEffect m) => Float32 -> m ArrayBuffer
286encodeFloat32be x = do
287 buf <- liftEffect $ AB.empty 4
288 _ <- liftEffect $ DV.setFloat32be (DV.whole buf) 0 x
289 pure buf
291-- | Append a 32-bit big-endian IEEE single-precision float to the builder.
292putFloat32be :: forall m. (MonadEffect m) => Float32 -> PutM m Unit
293putFloat32be = putArrayBuffer <=< encodeFloat32be
295-- | Serialize a 32-bit little-endian IEEE single-precision float into a new `ArrayBuffer`.
296encodeFloat32le :: forall m. (MonadEffect m) => Float32 -> m ArrayBuffer
297encodeFloat32le x = do
298 buf <- liftEffect $ AB.empty 4
299 _ <- liftEffect $ DV.setFloat32le (DV.whole buf) 0 x
300 pure buf
302-- | Append a 32-bit little-endian IEEE single-precision float to the builder.
303putFloat32le :: forall m. (MonadEffect m) => Float32 -> PutM m Unit
304putFloat32le = putArrayBuffer <=< encodeFloat32le
306-- | Serialize a 64-bit big-endian IEEE double-precision float into a new `ArrayBuffer`.
307encodeFloat64be :: forall m. (MonadEffect m) => Number -> m ArrayBuffer
308encodeFloat64be x = do
309 buf <- liftEffect $ AB.empty 8
310 _ <- liftEffect $ DV.setFloat64be (DV.whole buf) 0 x
311 pure buf
313-- | Append a 64-bit big-endian IEEE double-precision float to the builder.
314putFloat64be :: forall m. (MonadEffect m) => Number -> PutM m Unit
315putFloat64be = putArrayBuffer <=< encodeFloat64be
317-- | Serialize a 64-bit little-endian IEEE double-precision float into a new `ArrayBuffer`.
318encodeFloat64le :: forall m. (MonadEffect m) => Number -> m ArrayBuffer
319encodeFloat64le x = do
320 buf <- liftEffect $ AB.empty 8
321 _ <- liftEffect $ DV.setFloat64le (DV.whole buf) 0 x
322 pure buf
324-- | Append a 64-bit little-endian IEEE double-precision float to the builder.
325putFloat64le :: forall m. (MonadEffect m) => Number -> PutM m Unit
326putFloat64le = putArrayBuffer <=< encodeFloat64le
329-- ## Implementation Details
330--
331-- We want our `Builder` to be a data structure with
332-- * *O(1)* monoid append
333-- * *O(n)* fold
334--
335-- Our `Builder` implementation is an unbalanced binary tree.
336--
337-- For monoid `append`, what we actually get is *O(1)* when either the
338-- left or right tree is a singleton. If that's not true, then in the
339-- unlikely worst case `append` might be *O(n)*.
340--
341-- `Builder` is optimized what we consider to be normal usage, that is,
342-- `snoc`ing singleton elements to the end of the `Builder`.
343--
344-- If a Builder is built entirely by `snoc`ing, it will look like a
345-- left-only binary tree, a.k.a. a linked list.
346--
347-- ```
348-- ④
349-- ╱
350-- ③
351-- ╱
352-- ②
353-- ╱
354-- ①
355-- ```
356--
357-- If two of these `snoc`-built trees are `append`ed, then the new tree
358-- will look like
359--
360-- ```
361-- ④
362-- ╱ ╲
363-- ③ ⑧
364-- ╱ ╱
365-- ② ⑦
366-- ╱ ╱
367-- ① ⑥
368-- ╱
369-- ⑤
370-- ```
371--
372-- This is all similar to
373-- [__bytestring-tree-builder__](https://hackage.haskell.org/package/bytestring-tree-builder)
374-- , except that the
375-- [`Tree`](https://hackage.haskell.org/package/bytestring-tree-builder-0.2.7.3/docs/src/ByteString.TreeBuilder.Tree.html#Tree)
376-- structure in __bytestring-tree-builder__ only carries values in its
377-- leaves, which is how it achieves *O(1)* appending, at the cost of
378-- a higher coefficient time factor on the fold.
379--
380-- We hope that this implementation is fairly fast, but we
381-- haven't chosen this implementation because it's fast, we've chosen
382-- this implementation because it's simple.
383-- If someone wants to create a fast Purescript ArrayBuffer serialization
384-- library, then they can benchmark against this one to prove that the new
385-- one is fast.
386--
387-- One relatively cheap and simple performance improvement for this library would be to
388-- remove the Null constructor of `Builder` and instead use Javascript nulls.
389--
390-- In the longer term, it might make sense to try to change the Builder so
391-- that it works like the
392-- https://hackage.haskell.org/package/bytestring/docs/Data-ByteString-Builder.html
393--
394-- Here are some benchmarks of different Haskell ByteString builders
395-- https://github.com/haskell-perf/strict-bytestring-builders
396--
397-- We've tried to design the API for this library with minimal assumptions,
398-- so that if we want to change the Builder implementation later then we can.