relicence under MirOS Licence, granted by private deal with the CTO
[shellsnippets/shellsnippets.git] / mksh / assockit.ksh
1 # $MirOS: contrib/hosted/tg/assockit.ksh,v 1.7 2015/11/29 20:24:19 tg Exp $
2 # -*- mode: sh -*-
3 #-
4 # Copyright © 2011, 2013, 2015
5 #       mirabilos <m@mirbsd.org>
6 #
7 # Provided that these terms and disclaimer and all copyright notices
8 # are retained or reproduced in an accompanying document, permission
9 # is granted to deal in this work without restriction, including un‐
10 # limited rights to use, publicly perform, distribute, sell, modify,
11 # merge, give away, or sublicence.
12 #
13 # This work is provided “AS IS” and WITHOUT WARRANTY of any kind, to
14 # the utmost extent permitted by applicable law, neither express nor
15 # implied; without malicious intent or gross negligence. In no event
16 # may a licensor, author or contributor be held liable for indirect,
17 # direct, other damage, loss, or other issues arising in any way out
18 # of dealing in the work, even if advised of the possibility of such
19 # damage or existence of a defect, except proven that it results out
20 # of said person’s immediate fault when using the work as intended.
21 #-
22 # Associative, multi-dimensional arrays in Pure mksh™ (no exec!)
23 #-
24 # An item in an assockit array has the following properties:
25 # – the base-identifier of the shell array it’s in
26 # – the index into the shell array it’s in
27 # – an entry called flags
28 #   • data type: ASSO_{VAL,STR,INT,REAL,BOOL,NULL,AIDX,AASS}
29 # – an entry called key
30 # – an entry called value, unless NULL/AIDX/AASS
31 # Shell array paths are constructed like this:
32 # { 'foo': [ { 'baz': 123 } ] } named 'test' becomes:
33 # ‣ root-level lookup
34 #   – Asso__f[16#AE0C1A48] = ASSO_AASS | ASSO_ISSET|ASSO_ALLOC
35 #   – Asso__k[16#AE0C1A48] = 'test' (hash: AE0C1A48)
36 # ‣ Asso_AE0C1A48 = top-level
37 #   – Asso_AE0C1A48_f[16#BF959A6E] = ASSO_AIDX | ASSO_ISSET|ASSO_ALLOC
38 #   – Asso_AE0C1A48_k[16#BF959A6E] = 'foo' (hash: BF959A6E)
39 # ‣ Asso_AE0C1A48BF959A6E = next-level
40 #   – Asso_AE0C1A48BF959A6E_f[0] = ASSO_AASS | ASSO_ISSET|ASSO_ALLOC
41 #   – Asso_AE0C1A48BF959A6E_k[0] = 0
42 # ‣ Asso_AE0C1A48BF959A6E00000000 = last-level (below FOO)
43 #   – FOO_f[16#57F1BA9A] = ASSO_INT | ASSO_ISSET|ASSO_ALLOC
44 #   – FOO_k[16#57F1BA9A] = 'baz' (hash: 57F1BA9A)
45 #   – FOO_v[16#57F1BA9A] = 123
46 # When assigning a value, by default, the type of the
47 # intermediates is set to ASSO_AASS unless it already
48 # is ASSO_AIDX; the type of the terminals is ASSO_VAL
49 # unless it’s ASSO_{STR,INT,REAL,BOOL,NULL} before.
50
51 # check prerequisites
52 asso_x=${KSH_VERSION#????MIRBSD KSH R}
53 asso_x=${asso_x%% *}
54 if [[ $asso_x != +([0-9]) ]] || (( asso_x < 40 )); then
55         print -u2 'assockit.ksh: need at least mksh R40'
56         exit 1
57 fi
58
59 # set up variables
60 typeset -Uui16 -Z11 asso_h=0 asso_f=0 asso_k=0
61 typeset asso_b=""
62 set -A asso_y
63 set -A Asso__f
64 set -A Asso__k
65
66 # define constants
67 typeset -Uui16 -Z11 -r ASSO_VAL=2#000           # type: any Korn Shell scalar
68 typeset -Uui16 -Z11 -r ASSO_STR=2#001           # type: string
69 typeset -Uui16 -Z11 -r ASSO_INT=2#010           # type: integral
70 typeset -Uui16 -Z11 -r ASSO_REAL=2#011          # type: JSON float (string)
71 typeset -Uui16 -Z11 -r ASSO_BOOL=2#100          # type: JSON "true" / "false"
72 typeset -Uui16 -Z11 -r ASSO_NULL=2#101          # type: JSON "null"
73 typeset -Uui16 -Z11 -r ASSO_AIDX=2#110          # type: indexed array
74 typeset -Uui16 -Z11 -r ASSO_AASS=2#111          # type: associative array
75 typeset -Uui16 -Z11 -r ASSO_MASK_ARR=2#110      # bitmask for array type
76 typeset -Uui16 -Z11 -r ASSO_MASK_TYPE=2#111     # bitmask for type
77 typeset -Uui16 -Z11 -r ASSO_ISSET=16#40000000   # element is set
78 typeset -Uui16 -Z11 -r ASSO_ALLOC=16#80000000   # ksh element is set
79
80 # notes:
81 # – the code assumes ASSO_VAL=0 < all scalar types with value \
82 #   < ASSO_NULL < all array types
83
84 # public functions
85
86 # set a value
87 # example: asso_setv 123 'test' 'foo' 0 'baz'
88 function asso_setv {
89         if (( $# < 2 )); then
90                 print -u2 'assockit.ksh: syntax: asso_setv value key [key ...]'
91                 return 2
92         fi
93         local _v=$1 _f _i
94         shift
95
96         # look up the item, creating paths as needed
97         asso__lookup 1 "$@"
98         # if it’s an array, free that recursively
99         if (( ((_f = asso_f) & ASSO_MASK_ARR) == ASSO_MASK_ARR )); then
100                 asso__r_free 1
101                 (( _f &= ~ASSO_MASK_TYPE ))
102         fi
103         # if it’s got a type, check for a match
104         if (( _i = (_f & ASSO_MASK_TYPE) )); then
105                 asso__typeck $_i "$_v" || (( _f &= ~ASSO_MASK_TYPE ))
106         fi
107         # set the new flags and value
108         asso__r_setfv $_f "$_v"
109 }
110
111 # get the flags of an item, or return 1 if not set
112 # result is in the global variable asso_f
113 function asso_isset {
114         if (( $# < 1 )); then
115                 print -u2 'assockit.ksh: syntax: asso_isset key [key ...]'
116                 return 2
117         fi
118
119         asso__lookup 0 "$@"
120 }
121
122 # get the type of an item (return 1 if unset, 2 if error)
123 # example: x=$(asso_gett 'test' 'foo' 0 'baz') => $((ASSO_VAL))
124 function asso_gett {
125         asso_isset "$@" || return
126         print -n -- $((asso_f & ASSO_MASK_TYPE))
127 }
128
129 # get the value of an item (return 1 if unset, 2 if error)
130 # example: x=$(asso_getv 'test' 'foo' 0 'baz') => 123
131 function asso_getv {
132         asso_loadv "$@" || return
133         print -nr -- "$asso_x"
134 }
135
136 # get the value of an item, but result is in the global variable asso_x
137 function asso_loadv {
138         if (( $# < 1 )); then
139                 print -u2 'assockit.ksh: syntax: asso_loadv key [key ...]'
140                 return 2
141         fi
142
143         asso__lookup 2 "$@" || return 1
144         if (( (asso_f & ASSO_MASK_TYPE) < ASSO_NULL )); then
145                 nameref _Av=${asso_b}_v
146                 asso_x=${_Av[asso_k]}
147         else
148                 asso_x=""
149         fi
150 }
151
152 # get all set keys of an item of array type (return 1 if no array)
153 # result is in the global variable asso_y
154 function asso_loadk {
155         if (( $# < 1 )); then
156                 print -u2 'assockit.ksh: syntax: asso_loadk key [key ...]'
157                 return 2
158         fi
159
160         set -A asso_y
161         asso__lookup 0 "$@" || return 1
162         (( (asso_f & ASSO_MASK_ARR) == ASSO_MASK_ARR )) || return 1
163         nameref _keys=${asso_b}${asso_k#16#}_k
164         set -sA asso_y -- "${_keys[@]}"
165 }
166
167 # set a string value
168 # example: asso_sets 'abc' 'test' 'foo' 0 'baz'
169 function asso_sets {
170         if (( $# < 2 )); then
171                 print -u2 'assockit.ksh: syntax: asso_sets value key [key ...]'
172                 return 2
173         fi
174
175         asso__settv $ASSO_STR "$@"
176 }
177
178 # set an integral value
179 # example: asso_seti 123 'test' 'foo' 0 'baz'
180 function asso_seti {
181         if (( $# < 2 )); then
182                 print -u2 'assockit.ksh: syntax: asso_seti value key [key ...]'
183                 return 2
184         fi
185
186         if ! asso__typeck $ASSO_INT "$1"; then
187                 print -u2 "assockit.ksh: not an integer: '$1'"
188                 return 1
189         fi
190         asso__settv $ASSO_INT "$@"
191 }
192
193 # set a floating point (real) value
194 # example: asso_setr -123.45e+67 'test' 'foo' 0 'baz'
195 function asso_setr {
196         if (( $# < 2 )); then
197                 print -u2 'assockit.ksh: syntax: asso_setr value key [key ...]'
198                 return 2
199         fi
200
201         if ! asso__typeck $ASSO_REAL "$1"; then
202                 print -u2 "assockit.ksh: not a real: '$1'"
203                 return 1
204         fi
205         asso__settv $ASSO_REAL "$@"
206 }
207
208 # set a boolean value
209 # example: asso_setb t 'test' 'foo' 0 'baz'
210 function asso_setb {
211         if (( $# < 2 )); then
212                 print -u2 'assockit.ksh: syntax: asso_setb value key [key ...]'
213                 return 2
214         fi
215
216         if ! asso__typeck $ASSO_BOOL "$1"; then
217                 print -u2 "assockit.ksh: not a truth value: '$1'"
218                 return 1
219         fi
220         asso__settv $ASSO_BOOL "$@"
221 }
222
223 # set value to null
224 # example: asso_setnull 'test' 'foo' 0 'baz'
225 function asso_setnull {
226         if (( $# < 1 )); then
227                 print -u2 'assockit.ksh: syntax: asso_setnull key [key ...]'
228                 return 2
229         fi
230
231         asso__settv $ASSO_NULL 0 "$@"
232 }
233
234 # set type and scalar value
235 # example: asso_settv $ASSO_INT 123 'test' 'foo' 0 'baz'
236 function asso_settv {
237         if (( $# < 3 )) || ! asso__intck "$1" || \
238             (( $1 != ($1 & ASSO_MASK_TYPE) )); then
239                 print -u2 'assockit.ksh: syntax: asso_settv type value key...'
240                 return 2
241         fi
242
243         if ! asso__typeck $1 "$2"; then
244                 print -u2 "assockit.ksh: wrong type scalar: '$2'"
245                 return 1
246         fi
247         asso__settv "$@"
248 }
249
250 # unset value
251 # example: asso_unset 'test' 'foo' 0 'baz'
252 function asso_unset {
253         if (( $# < 1 )); then
254                 print -u2 'assockit.ksh: syntax: asso_unset key [key ...]'
255                 return 2
256         fi
257
258         # look up the item, not creating paths
259         if asso__lookup 0 "$@"; then
260                 # free the item recursively
261                 asso__r_free 0
262         fi
263         return 0
264 }
265
266 # make an entry into an indexed array
267 # from scalar => data into [0]
268 # from associative array => data lost
269 function asso_setidx {
270         if (( $# < 1 )); then
271                 print -u2 'assockit.ksh: syntax: asso_setidx key [key ...]'
272                 return 2
273         fi
274
275         local _f _v
276
277         asso__lookup 1 "$@"
278         if (( ((_f = asso_f) & ASSO_MASK_ARR) != ASSO_MASK_ARR )); then
279                 nameref _Av=${asso_b}_v
280                 _v=${_Av[asso_k]}
281         elif (( (_f & ASSO_MASK_TYPE) == ASSO_AIDX )); then
282                 return 0
283         fi
284         asso__r_free 1
285         asso__r_setf $ASSO_AIDX
286         if (( (_f & ASSO_MASK_ARR) != ASSO_MASK_ARR )); then
287                 asso__lookup 1 "$@" 0
288                 asso__r_setfv $_f "$_v"
289         fi
290 }
291
292 # make an entry into an associative array
293 # from scalar => data lost
294 # from indexed array => data converted
295 function asso_setasso {
296         if (( $# < 1 )); then
297                 print -u2 'assockit.ksh: syntax: asso_setasso key [key ...]'
298                 return 2
299         fi
300
301         local _f
302
303         asso__lookup 1 "$@"
304         if (( ((_f = asso_f) & ASSO_MASK_ARR) != ASSO_MASK_ARR )); then
305                 asso__r_free 1
306                 asso__r_setf $ASSO_AASS
307         elif (( (_f & ASSO_MASK_TYPE) == ASSO_AIDX )); then
308                 asso__r_idx2ass
309         fi
310         return 0
311 }
312
313 # private functions
314
315 # set type and scalar value, unchecked
316 function asso__settv {
317         local _t=$1 _v=$2 _f
318         shift; shift
319
320         # look up the item, creating paths as needed
321         asso__lookup 1 "$@"
322         # if it’s an array, free that recursively
323         if (( ((_f = asso_f) & ASSO_MASK_ARR) == ASSO_MASK_ARR )); then
324                 asso__r_free 1
325         fi
326         (( _f = (_f & ~ASSO_MASK_TYPE) | _t ))
327         # set the new flags and value
328         asso__r_setfv $_f "$_v"
329 }
330
331 # check if this is a numeric (integral) value (0=ok 1=error)
332 function asso__intck {
333         local _v=$1
334
335         [[ $_v = ?(+([0-9])'#')+([0-9a-zA-Z]) ]] || return 2
336         { : $((_v)) ; } 2>&-
337 }
338
339 # map a boolean value (0=false 1=true 2=error)
340 function asso__boolmap {
341         local _v=$1
342
343         if asso__intck "$_v"; then
344                 (( _v == 0 ))
345                 return
346         fi
347         case $_v {
348         ([Tt]?([Rr][Uu][Ee])|[Yy]?([Ee][Ss])|[Oo][NnKk])
349                 return 1 ;;
350         ([Ff]?([Aa][Ll][Ss][Ee])|[Nn]?([Oo])|[Oo][Ff][Ff])
351                 return 0 ;;
352         }
353         return 2
354 }
355
356 # check if the type matches the value (0=ok 1=error)
357 function asso__typeck {
358         if (( $# != 2 )); then
359                 print -u2 'assockit.ksh: syntax: asso__typeck type value'
360                 return 2
361         fi
362         local _t=$1 _v=$2
363         (( _t == ASSO_VAL || _t == ASSO_STR || _t == ASSO_NULL )) && return 0
364         if (( _t == ASSO_INT )); then
365                 asso__intck "$_v"
366                 return
367         fi
368         if (( _t == ASSO_BOOL )); then
369                 asso__boolmap "$_v"
370                 (( $? < 2 ))
371                 return
372         fi
373         (( (_t & ASSO_MASK_ARR) == ASSO_MASK_ARR )) && return 1
374         # ASSO_REAL
375         [[ $_v = ?(-)@(0|[1-9]*([0-9]))?(.+([0-9]))?([Ee]?([+-])+([0-9])) ]]
376 }
377
378 # look up an item ($1 &1: create paths as necessary; &2: only scalar values)
379 function asso__lookup {
380         local _c=$1 _k _n _r
381         shift
382
383         _n=Asso_
384         _r=0
385         asso_f=$ASSO_AASS
386         for _k in "$@"; do
387                 if (( _r || (asso_f & ASSO_MASK_ARR) != ASSO_MASK_ARR )); then
388                         (( _r )) || asso__r_free 1
389                         asso__r_setf $ASSO_AASS
390                 elif (( (asso_f & ASSO_MASK_TYPE) == ASSO_AIDX )); then
391                         asso__intck "$_k" || asso__r_idx2ass
392                 fi
393                 asso_b=$_n
394                 asso__lookup_once "$_k"
395                 if (( _r = $? )); then
396                         # not found. not create?
397                         (( _c & 1 )) || return 1
398                         asso__r_setk "$_k"
399                 fi
400                 _n=$_n${asso_k#16#}
401         done
402         (( _c & 2 )) || return 0
403         # assume $1==3 does not happen
404         while (( (asso_f & ASSO_MASK_ARR) == ASSO_MASK_ARR )); do
405                 asso_b=$_n
406                 asso__lookup_once 0 || return 1
407                 _n=$_n${asso_k#16#}
408         done
409 }
410
411 # set flags for asso_b[asso_k] and update asso_f
412 function asso__r_setf {
413         nameref _Af=${asso_b}_f
414
415         asso_f=$(($1 | ASSO_ISSET | ASSO_ALLOC))
416         _Af[asso_k]=$asso_f
417 }
418
419 # set flags and value for asso_b[asso_k] and update asso_f
420 function asso__r_setfv {
421         nameref _Af=${asso_b}_f
422         nameref _Av=${asso_b}_v
423
424         _Av[asso_k]=$2
425         asso_f=$(($1 | ASSO_ISSET | ASSO_ALLOC))
426         _Af[asso_k]=$asso_f
427 }
428
429 # set key for not yet existing asso_b[asso_k] and update asso_f
430 function asso__r_setk {
431         nameref _Af=${asso_b}_f
432         nameref _Ak=${asso_b}_k
433
434         _Ak[asso_k]=$1
435         asso_f=$((ASSO_ALLOC))
436         _Af[asso_k]=$asso_f
437 }
438
439 # in asso_b of type asso_f look up element $1
440 # set its asso_f and asso_k or return 1 when not found
441 function asso__lookup_once {
442         local _e=$1 _seth=0
443         nameref _Af=${asso_b}_f
444         nameref _Ak=${asso_b}_k
445
446         if (( (asso_f & ASSO_MASK_TYPE) == ASSO_AIDX )); then
447                 asso_k=$((_e))
448         else
449                 asso_k=16#${_e@#}
450                 while :; do
451                         asso_f=${_Af[asso_k]}
452                         (( asso_f & ASSO_ALLOC )) || break
453                         if (( !(asso_f & ASSO_ISSET) )); then
454                                 if (( !_seth )); then
455                                         # save index
456                                         asso_h=$asso_k
457                                         _seth=1
458                                 fi
459                                 (( --asso_k ))
460                                 continue
461                         fi
462                         [[ ${_Ak[asso_k]} = "$_e" ]] && break
463                         # iterate
464                         (( --asso_k ))
465                 done
466         fi
467         asso_f=${_Af[asso_k]}
468         # found?
469         (( asso_f & ASSO_ISSET )) && return 0
470         # not found.
471         if (( _seth )); then
472                 # when allocating, use this one instead
473                 asso_k=$asso_h
474         fi
475         return 1
476 }
477
478 # free the currently selected asso_b[asso_k] recursively
479 function asso__r_free {
480         local _keepkey=$1
481         nameref _Af=${asso_b}_f
482
483         asso_f=${_Af[asso_k]}
484         (( asso_f & ASSO_ALLOC )) || return
485         if (( asso_f & ASSO_ISSET )); then
486                 if (( (asso_f & ASSO_MASK_ARR) == ASSO_MASK_ARR )); then
487                         local _ob=$asso_b _ok=$asso_k
488                         asso_b=$asso_b${asso_k#16#}
489                         nameref _s=${asso_b}_f
490                         for asso_k in "${!_s[@]}"; do
491                                 asso__r_free
492                         done
493                         eval unset ${asso_b}_f ${asso_b}_k ${asso_b}_v
494                         asso_b=$_ob asso_k=$_ok
495                 fi
496                 eval unset $asso_b'_v[asso_k]'
497                 (( _keepkey )) || eval unset $asso_b'_k[asso_k]'
498         fi
499         asso_f=$((ASSO_ALLOC))
500         _Af[asso_k]=$asso_f
501 }
502
503 # make indexed asso_b[asso_k] into associative array
504 function asso__r_idx2ass {
505         print -u2 'assockit.ksh: warning: asso__r_idx2ass not implemented'
506         print -u2 'assockit.ksh: warning: data will be lost'
507         asso__r_free
508         asso__r_setf $ASSO_AASS
509 }