0 | ||| Core data types and functions for working with immutable and
  1 | ||| mutable (linear) arrays.
  2 | module Data.Array.Core
  3 |
  4 | import Data.Array.Index
  5 | import Data.Buffer
  6 | import Data.Linear
  7 | import Data.Linear.Token
  8 | import Data.Fin
  9 | import Data.Nat
 10 |
 11 | import Data.Buffer.Core as BC
 12 |
 13 | import Syntax.T1
 14 |
 15 | %default total
 16 |
 17 | %hide BC.get
 18 | %hide BC.icopy
 19 | %hide BC.copy
 20 |
 21 | --------------------------------------------------------------------------------
 22 | --          Raw Primitives
 23 | --------------------------------------------------------------------------------
 24 |
 25 | export
 26 | %foreign "scheme:(lambda (x) (make-vector x))"
 27 |          "javascript:lambda:(n,w) => new Array(Number(n))"
 28 | prim__emptyArray : Integer -> PrimIO AnyPtr
 29 |
 30 | export
 31 | %foreign "scheme:(lambda (x i) (make-vector x i))"
 32 |          "javascript:lambda:(bi,x,w) => Array(Number(bi)).fill(x)"
 33 | prim__newArray : Integer -> AnyPtr -> PrimIO AnyPtr
 34 |
 35 | export
 36 | %foreign "scheme:(lambda (x i) (vector-ref x i))"
 37 |          "javascript:lambda:(x,bi) => x[Number(bi)]"
 38 | prim__arrayGet : AnyPtr -> Integer -> AnyPtr
 39 |
 40 | -- This is an optimized version of `prim_arrayGet` that allows us to read
 41 | -- at an offset. On Chez, we can use the faster fixnum addition here,
 42 | -- which can lead to a performance boost.
 43 | %foreign "scheme:(lambda (b a o) (vector-ref b (+ a o)))"
 44 |          "scheme,chez:(lambda (b a o) (vector-ref b (fx+ a o)))"
 45 |          "javascript:lambda:(buf,at,offset)=>buf[Number(offset) + Number(at)]"
 46 | prim__arrayGetOffset : AnyPtr -> (at, offset : Integer) -> AnyPtr
 47 |
 48 | export
 49 | %foreign "scheme:(lambda (x i w) (vector-set! x i w))"
 50 |          "javascript:lambda:(x,bi,w) => {const i = Number(bi); x[i] = w}"
 51 | prim__arraySet : AnyPtr -> Integer -> (val : AnyPtr) -> PrimIO ()
 52 |
 53 | export
 54 | %foreign "scheme:(lambda (a x i v w) (if (vector-cas! x i v w) 1 0))"
 55 |          "javascript:lambda:(a,x,bi,v,w) => {const i = Number(bi); if (x[i] === v) {x[i] = w; return 1;} else {return 0;}}"
 56 | prim__casSet : AnyPtr -> Integer -> (prev,val : a) -> Bits8
 57 |
 58 | export
 59 | %foreign "scheme: (lambda (b1 o1 len b2 o2) (letrec ((go (lambda (i) (when (< i len) (begin (vector-set! b2 (+ o2 i) (vector-ref b1 (+ o1 i))) (go (+ 1 i))))))) (go 0)))"
 60 |          "scheme,chez: (lambda (b1 o1 len b2 o2) (letrec ((go (lambda (i) (when (< i len) (begin (vector-set! b2 (fx+ o2 i) (vector-ref b1 (fx+ o1 i))) (go (fx+ 1 i))))))) (go 0)))"
 61 |          "javascript:lambda:(b1,bo1,blen,b2,bo2,t)=> {const o1 = Number(bo1); const len = Number(blen); const o2 = Number(bo2); for (let i = 0; i < len; i++) {b2[o2+i] = b1[o1+i];}; return t}"
 62 | prim__copyArray : (src : AnyPtr) -> (srcOffset, len : Integer) ->
 63 |                   (dst : AnyPtr) -> (dstOffset : Integer) -> PrimIO ()
 64 |
 65 | export
 66 | %foreign "scheme: (lambda (b1 o1 len b2 o2) (letrec ((go (lambda (i) (when (< i len) (begin (vector-set! b2 (+ o2 i) (bytevector-u8-ref b1 (+ o1 i))) (go (+ 1 i))))))) (go 0)))"
 67 |          "scheme,chez: (lambda (b1 o1 len b2 o2) (letrec ((go (lambda (i) (when (< i len) (begin (vector-set! b2 (fx+ o2 i) (bytevector-u8-ref b1 (fx+ o1 i))) (go (fx+ 1 i))))))) (go 0)))"
 68 |          "javascript:lambda:(b1,bo1,blen,b2,bo2,t)=> {const o1 = Number(bo1); const len = Number(blen); const o2 = Number(bo2); for (let i = 0; i < len; i++) {b2[o2+i] = b1[o1+i];}; return t}"
 69 | prim__bufToArr : (src : Buffer) -> (srcOffset, len : Integer) ->
 70 |                  (dst : AnyPtr) -> (dstOffset : Integer) -> PrimIO ()
 71 |
 72 | export
 73 | %foreign "scheme: (lambda (b1 o1 len b2 o2) (letrec ((go (lambda (i) (when (< i len) (begin (bytevector-u8-set! b2 (+ o2 i) (vector-ref b1 (+ o1 i))) (go (+ 1 i))))))) (go 0)))"
 74 |          "scheme,chez: (lambda (b1 o1 len b2 o2) (letrec ((go (lambda (i) (when (< i len) (begin (bytevector-u8-set! b2 (fx+ o2 i) (vector-ref b1 (fx+ o1 i))) (go (fx+ 1 i))))))) (go 0)))"
 75 |          "javascript:lambda:(b1,bo1,blen,b2,bo2,t)=> {const o1 = Number(bo1); const len = Number(blen); const o2 = Number(bo2); for (let i = 0; i < len; i++) {b2[o2+i] = b1[o1+i];}; return t}"
 76 | prim__arrToBuf : (src : AnyPtr) -> (srcOffset, len : Integer) ->
 77 |                  (dst : Buffer) -> (dstOffset : Integer) -> PrimIO ()
 78 |
 79 | export
 80 | %foreign "javascript:lambda:(x,t)=> x.length"
 81 | prim__jsArrLength : AnyPtr -> PrimIO Bits32
 82 |
 83 | --------------------------------------------------------------------------------
 84 | --          Immutable Arrays
 85 | --------------------------------------------------------------------------------
 86 |
 87 | ||| An immutable array of size `n` holding values of type `a`.
 88 | export
 89 | record IArray (n : Nat) (a : Type) where
 90 |   constructor IA
 91 |   arr : AnyPtr
 92 |
 93 | ||| Safely access a value in an array at the given position.
 94 | export %inline
 95 | at : IArray n a -> Fin n -> a
 96 | at (IA ad) m = believe_me $ prim__arrayGet ad (cast $ finToNat m)
 97 |
 98 | ||| Safely use a byte as an index into an array.
 99 | export %inline
100 | atByte : IArray 256 a -> Bits8 -> a
101 | atByte (IA ad) m = believe_me $ prim__arrayGet ad (cast m)
102 |
103 | ||| Safely access a value in an array at the given position
104 | ||| and offset.
105 | export %inline
106 | atOffset : IArray n a -> Fin m -> (off : Nat) -> (0 p : LTE (off+m) n) => a
107 | atOffset (IA ad) m off =
108 |   believe_me $ prim__arrayGetOffset ad (cast $ finToNat m) (cast off)
109 |
110 | ||| We can wrap a prefix of an array in O(1) simply by giving it
111 | ||| a new size index.
112 | |||
113 | ||| Note: If you only need a small portion of a potentially large
114 | |||       array the rest of which you no longer need, consider to
115 | |||       release the large array from memory by invoking `force`.
116 | export
117 | take : (0 m : Nat) -> IArray n a -> {auto 0 lte : LTE m n} -> IArray m a
118 | take _ (IA arr) = IA arr
119 |
120 | ||| Extracts the wrapped `AnyPtr` value of an immutable array.
121 | |||
122 | ||| This can be used to pass the array in a foreign function call.
123 | ||| Client code is responsible to make sure the array is not
124 | ||| mutated in its raw form.
125 | export %inline
126 | unsafeToPtr : IArray n a -> AnyPtr
127 | unsafeToPtr (IA p) = p
128 |
129 | --------------------------------------------------------------------------------
130 | --          Mutable Arrays
131 | --------------------------------------------------------------------------------
132 |
133 | ||| A mutable array.
134 | export
135 | data MArray : (s : Type) -> (n : Nat) -> (a : Type) -> Type where
136 |   MA : (arr : AnyPtr) -> MArray s n a
137 |
138 | ||| Convenience alias for `MArray' RIO`.
139 | public export
140 | 0 IOArray : Nat -> Type -> Type
141 | IOArray = MArray World
142 |
143 | ||| Extracts the wrapped `AnyPtr` value of a mutable array.
144 | |||
145 | ||| This can be used to pass the array in a foreign function call.
146 | ||| Client code is responsible to make sure the array is not
147 | ||| mutated in its raw form.
148 | export %inline
149 | unsafeMToPtr : MArray s n a -> AnyPtr
150 | unsafeMToPtr (MA p) = p
151 |
152 | --------------------------------------------------------------------------------
153 | -- Utilities
154 | --------------------------------------------------------------------------------
155 |
156 | ||| Fills a new mutable bound to linear computation `s`.
157 | export %inline
158 | marray1 : (n : Nat) -> a -> F1 s (MArray s n a)
159 | marray1 n v t =
160 |   let p # t := ffi (prim__newArray (cast n) (believe_me v)) t in MA p # t
161 |
162 | ||| Fills a new mutable array in `IO`.
163 | export %inline
164 | marray : Lift1 s f => (n : Nat) -> a -> f (MArray s n a)
165 | marray n v = lift1 (marray1 n v)
166 |
167 | export %inline
168 | unsafeMArray1 : (n : Nat) -> F1 s (MArray s n a)
169 | unsafeMArray1 n t =
170 |   let p # t := ffi (prim__emptyArray (cast n)) t in MA p # t
171 |
172 | ||| Allocates a new, empty, mutable array in `IO`.
173 | export %inline
174 | unsafeMArray : Lift1 s f => (n : Nat) -> f (MArray s n a)
175 | unsafeMArray n = lift1 (unsafeMArray1 n)
176 |
177 | ||| Safely write a value to a mutable array.
178 | export %inline
179 | set : (r : MArray s n a) -> Fin n -> a -> F1' s
180 | set (MA arr) ix v = ffi (prim__arraySet arr (cast $ finToNat ix) (believe_me v))
181 |
182 | ||| Safely write a value to a mutable array.
183 | export %inline
184 | setBits8 : (r : MArray s 256 a) -> Bits8 -> a -> F1' s
185 | setBits8 (MA arr) ix v = ffi (prim__arraySet arr (cast ix) (believe_me v))
186 |
187 | ||| Safely read a value from a mutable array.
188 | |||
189 | ||| This returns the values thus read with unrestricted quantity, paired
190 | ||| with a new linear token of quantity one to be further used in the
191 | ||| linear context.
192 | export %inline
193 | get : (r : MArray s n a) -> Fin n -> F1 s a
194 | get (MA arr) ix t = believe_me (prim__arrayGet arr (cast $ finToNat ix)) # t
195 |
196 | ||| Safely read a value from a mutable array.
197 | |||
198 | ||| This returns the values thus read with unrestricted quantity, paired
199 | ||| with a new linear token of quantity one to be further used in the
200 | ||| linear context.
201 | export %inline
202 | getBits8 : (r : MArray s 256 a) -> Bits8 -> F1 s a
203 | getBits8 (MA arr) ix t = believe_me (prim__arrayGet arr (cast ix)) # t
204 |
205 | ||| Safely modify a value in a mutable array.
206 | export %inline
207 | modify : (r : MArray s n a) -> Fin n -> (a -> a) -> F1' s
208 | modify r ix f t = let v # t1 := get r ix t in set r ix (f v) t1
209 |
210 | ||| Atomically writes `val` at the given position of the mutable array
211 | ||| if its current value is equal to `pre`.
212 | |||
213 | ||| This is supported and has been tested on the Chez and Racket backends.
214 | ||| It trivially works on the JavaScript backends, which are single-threaded
215 | ||| anyway.
216 | export %inline
217 | casset : (r : MArray s n a) -> Fin n -> (pre,val : a) -> F1 s Bool
218 | casset (MA arr) x pre val t =
219 |   case prim__casSet arr (cast $ finToNat x) pre val of
220 |     0 => False # t
221 |     _ => True # t
222 |
223 | ||| Atomically overwrites at the given position of the mutable array.
224 | |||
225 | ||| This is supported and has been tested on the Chez and Racket backends.
226 | ||| It trivially works on the JavaScript backends, which are single-threaded
227 | ||| anyway.
228 | export %inline
229 | casswap : (r : MArray s n a) -> Fin n -> a -> F1' s
230 | casswap r x v t = assert_total (loop t)
231 |   where
232 |     covering loop : F1' s
233 |     loop t =
234 |       let cur # t  := get r x t
235 |           True # t := casset r x cur v t | _ # t => loop t
236 |        in () # t
237 |
238 | ||| Atomic modification of an array position using a CAS-loop internally.
239 | |||
240 | ||| This is supported and has been tested on the Chez and Racket backends.
241 | ||| It trivially works on the JavaScript backends, which are single-threaded
242 | ||| anyway.
243 | export
244 | casupdate : (r : MArray s n a) -> Fin n -> (a -> (a,b)) -> F1 s b
245 | casupdate r x f t = assert_total (loop t)
246 |   where
247 |     covering loop : F1 s b
248 |     loop t =
249 |       let cur # t  := get r x t
250 |           (new,v)  := f cur
251 |           True # t := casset r x cur new t | _ # t => loop t
252 |        in v # t
253 |
254 | ||| Atomic modification of an array position reference using a CAS-loop
255 | ||| internally.
256 | |||
257 | ||| This is supported and has been tested on the Chez and Racket backends.
258 | ||| It trivially works on the JavaScript backends, which are single-threaded
259 | ||| anyway.
260 | export
261 | casmodify : (r : MArray s n a) -> Fin n -> (a -> a) -> F1' s
262 | casmodify r x f t = assert_total (loop t)
263 |   where
264 |     covering loop : F1' s
265 |     loop t =
266 |       let cur  # t := get r x t
267 |           True # t := casset r x cur (f cur) t | _ # t => loop t
268 |        in () # t
269 |
270 | ||| Wraps a mutable array in a shorter one.
271 | export %inline
272 | mtake : MArray s n a -> (0 m : Nat) -> (0 lte : LTE m n) => F1 s (MArray s m a)
273 | mtake (MA arr) _ t = MA arr # t
274 |
275 | export %noinline
276 | copy :
277 |      MArray s m a
278 |   -> (srcOffset,dstOffset : Nat)
279 |   -> (len : Nat)
280 |   -> {auto 0 p1 : LTE (srcOffset + len) m}
281 |   -> {auto 0 p2 : LTE (dstOffset + len) n}
282 |   -> (r         : MArray s n a)
283 |   -> F1' s
284 | copy (MA src) srcOffset dstOffset len (MA dst) =
285 |   ffi (prim__copyArray src (cast srcOffset) (cast len) dst (cast dstOffset))
286 |
287 | export %inline
288 | icopy :
289 |      IArray m a
290 |   -> (srcOffset,dstOffset : Nat)
291 |   -> (len : Nat)
292 |   -> {auto 0 p1 : LTE (srcOffset + len) m}
293 |   -> {auto 0 p2 : LTE (dstOffset + len) n}
294 |   -> (r         : MArray s n a)
295 |   -> F1' s
296 | icopy (IA src) = copy {m} (MA src)
297 |
298 | export %noinline
299 | copyToBuf :
300 |      MArray s m Bits8
301 |   -> (srcOffset,dstOffset : Nat)
302 |   -> (len : Nat)
303 |   -> {auto 0 p1 : LTE (srcOffset + len) m}
304 |   -> {auto 0 p2 : LTE (dstOffset + len) n}
305 |   -> (r         : MBuffer s n)
306 |   -> F1' s
307 | copyToBuf (MA src) srcOffset dstOffset len dst =
308 |   ffi (prim__arrToBuf src (cast srcOffset) (cast len) (unsafeFromMBuffer dst) (cast dstOffset))
309 |
310 | export %inline
311 | icopyToBuf :
312 |      IArray m Bits8
313 |   -> (srcOffset,dstOffset : Nat)
314 |   -> (len : Nat)
315 |   -> {auto 0 p1 : LTE (srcOffset + len) m}
316 |   -> {auto 0 p2 : LTE (dstOffset + len) n}
317 |   -> (r         : MBuffer s n)
318 |   -> F1' s
319 | icopyToBuf (IA src) = copyToBuf {m} (MA src)
320 |
321 | export %noinline
322 | copyToArray :
323 |      MBuffer s m
324 |   -> (srcOffset,dstOffset : Nat)
325 |   -> (len : Nat)
326 |   -> {auto 0 p1 : LTE (srcOffset + len) m}
327 |   -> {auto 0 p2 : LTE (dstOffset + len) n}
328 |   -> (r         : MArray s n Bits8)
329 |   -> F1' s
330 | copyToArray src srcOffset dstOffset len (MA dst) =
331 |   ffi (prim__bufToArr (unsafeFromMBuffer src) (cast srcOffset) (cast len) dst (cast dstOffset))
332 |
333 | export %inline
334 | icopyToArray :
335 |      IBuffer m
336 |   -> (srcOffset,dstOffset : Nat)
337 |   -> (len : Nat)
338 |   -> {auto 0 p1 : LTE (srcOffset + len) m}
339 |   -> {auto 0 p2 : LTE (dstOffset + len) n}
340 |   -> (r         : MArray s n Bits8)
341 |   -> F1' s
342 | icopyToArray buf = copyToArray {m} (unsafeMBuffer $ unsafeGetBuffer buf)
343 |
344 | ||| Copy the content of an immutable array to a new mutable array.
345 | export
346 | thaw : {n : _} -> IArray n a -> F1 s (MArray s n a)
347 | thaw src t =
348 |     let r # t := unsafeMArray1 n t
349 |         _ # t := icopy src 0 0 n @{reflexive} @{reflexive} r t
350 |      in r # t
351 |
352 | ||| Make the content of an immutable array accessible as a mutable array.
353 | |||
354 | ||| This is obviously unsafe. Don't use if you don't know exactly what you
355 | ||| are doing.
356 | export
357 | unsafeThaw : IArray n a -> MArray s n a
358 | unsafeThaw (IA arr) = MA arr
359 |
360 | --------------------------------------------------------------------------------
361 | -- Allocating Arrays
362 | --------------------------------------------------------------------------------
363 |
364 | public export
365 | 0 WithMArray : Nat -> (a,b : Type) -> Type
366 | WithMArray n a b = forall s . (r : MArray s n a) -> F1 s b
367 |
368 | ||| Allocate and use a mutable array in a linear context.
369 | export
370 | alloc : (n : Nat) -> a -> (fun : WithMArray n a b) -> b
371 | alloc n v f = run1 $ \t => let r # t2 := marray1 n v t in f r t2
372 |
373 | ||| Like `create` but the initially created array will not hold any
374 | ||| sensible data.
375 | |||
376 | ||| Use with care: Client code is responsible to properly initialize
377 | ||| the array with data. This is usefule for creating arrays of unknown
378 | ||| size, when it is not immediately clear, whether it will hold any
379 | ||| data at all.
380 | |||
381 | ||| See for instance the implementation of `filter` or `mapMaybe`.
382 | export
383 | unsafeAlloc : (n : Nat) -> (fun : WithMArray n a b) -> b
384 | unsafeAlloc n f = run1 $ \t => let r # t2 := unsafeMArray1 n t in f r t2
385 |
386 | ||| Wrap a mutable array in an immutable array, which can then be freely shared.
387 | |||
388 | ||| It is not possible the extract and share the underlying `ArrayData`
389 | ||| wrapped in an `IArray`, so we don't have to be afraid of shared mutable
390 | ||| state: The interface of `IArray` does not support to further mutate
391 | ||| the wrapped array.
392 | |||
393 | ||| It is safe to only use a prefix of a properly constructed array,
394 | ||| therefore we are free to give the resulting array a smaller size.
395 | ||| Most of the time, we'd like to use the whole array, in which case
396 | ||| we can just use `unsafeFreeze`.
397 | |||
398 | ||| Note: For reasons of efficiency, this does not copy the mutable array,
399 | |||       and therefore, it must no longer be modified after calling
400 | |||       this function.
401 | export %inline
402 | unsafeFreezeLTE :
403 |      {auto 0 _ : LTE m n}
404 |   -> (r        : MArray s n a)
405 |   -> (0 m : Nat)
406 |   -> F1 s (IArray m a)
407 | unsafeFreezeLTE (MA arr) _ t = IA arr # t
408 |
409 | ||| Wrap a mutable array in an immutable array, which can then be freely shared.
410 | |||
411 | ||| Note: For reasons of efficiency, this does not copy the mutable array,
412 | |||       and therefore, it must no longer be modified after calling
413 | |||       this function.
414 | export %inline
415 | unsafeFreeze : (r : MArray s n a) -> F1 s (IArray n a)
416 | unsafeFreeze r = unsafeFreezeLTE @{reflexive} r n
417 |
418 | ||| Copy a prefix of a mutable array into an immutable array.
419 | export
420 | freezeLTE : MArray s n a -> (m : Nat) -> (0 p : LTE m n) => F1 s (IArray m a)
421 | freezeLTE src m t =
422 |   let r@(MA buf) # t := unsafeMArray1 m t
423 |       _          # t := copy src 0 0 m @{p} @{reflexive} r t
424 |    in IA buf     # t
425 |
426 | ||| Copy a mutable buffer into an `IBuffer`.
427 | export %inline
428 | freeze : {n : _} -> MArray s n a -> F1 s (IArray n a)
429 | freeze src = freezeLTE src n @{reflexive}
430 |
431 | --------------------------------------------------------------------------------
432 | --          Array Conversions
433 | --------------------------------------------------------------------------------
434 |
435 | ||| Copies an immutable array of bytes to a immutable buffer.
436 | export
437 | toIBuffer : {n : _} -> IArray n Bits8 -> IBuffer n
438 | toIBuffer arr =
439 |   alloc n $ \buf,t =>
440 |    let _ # t := icopyToBuf arr 0 0 n buf t
441 |     in unsafeFreeze buf t
442 |
443 | ||| Copies an immtuable buffer to an immutable array of bytes.
444 | export
445 | toIArray : {n : _} -> IBuffer n -> IArray n Bits8
446 | toIArray buf =
447 |   alloc n (the Bits8 0) $ \arr,t =>
448 |    let _ # t := icopyToArray buf 0 0 n arr t
449 |     in unsafeFreeze arr t
450 |
451 | --------------------------------------------------------------------------------
452 | -- Arrays from the FFI
453 | --------------------------------------------------------------------------------
454 |
455 | ||| Utility for wrapping an array result from the FFI in a proper
456 | ||| Idris array.
457 | |||
458 | ||| Since we are wrapping a raw pointer, this is obviously an unsafe
459 | ||| operation and client code is responsible to make sure that the pointer
460 | ||| actually corresponds to a JS array or array-like.
461 | export
462 | unsafeJSMArrayOf1 : (0 a : Type) -> AnyPtr -> F1 s (n ** MArray s n a)
463 | unsafeJSMArrayOf1 a ptr t =
464 |  let len # t := ffi (prim__jsArrLength ptr) t
465 |   in (cast len ** MA ptr# t
466 |
467 | ||| Like `unsafeJSMArrayOf1` but runs in an `IO` monad.
468 | export %inline
469 | unsafeJSMArrayOf : HasIO io => (0 a : Type) -> AnyPtr -> io (n ** IOArray n a)
470 | unsafeJSMArrayOf a ptr = runIO (unsafeJSMArrayOf1 a ptr)
471 |