mksh/assockit.ksh

   1 # $MirOS: contrib/hosted/tg/assockit.ksh,v 1.4 2013/04/26 17:20:33 tg Exp $
   2 #-
   3 # Copyright © 2011, 2013
   4 #       Thorsten “mirabilos” Glaser <tg@mirbsd.org>
   5 # Copyright © 2013
   6 #       Thorsten Glaser <t.glaser@tarent.de>
   7 #
   8 # Provided that these terms and disclaimer and all copyright notices
   9 # are retained or reproduced in an accompanying document, permission
  10 # is granted to deal in this work without restriction, including un‐
  11 # limited rights to use, publicly perform, distribute, sell, modify,
  12 # merge, give away, or sublicence.
  13 #
  14 # This work is provided “AS IS” and WITHOUT WARRANTY of any kind, to
  15 # the utmost extent permitted by applicable law, neither express nor
  16 # implied; without malicious intent or gross negligence. In no event
  17 # may a licensor, author or contributor be held liable for indirect,
  18 # direct, other damage, loss, or other issues arising in any way out
  19 # of dealing in the work, even if advised of the possibility of such
  20 # damage or existence of a defect, except proven that it results out
  21 # of said person’s immediate fault when using the work as intended.
  22 #-
  23 # Associative, multi-dimensional arrays in Pure mksh™ (no exec!)
  24 #-
  25 # An item in an assockit array has the following properties:
  26 # – the base-identifier of the shell array it’s in
  27 # – the index into the shell array it’s in
  28 # – an entry called flags
  29 #   • data type: ASSO_{VAL,STR,INT,REAL,BOOL,NULL,AIDX,AASS}
  30 # – an entry called key
  31 # – an entry called value, unless NULL/AIDX/AASS
  32 # Shell array paths are constructed like this:
  33 # { 'foo': [ { 'baz': 123 } ] } named 'test' becomes:
  34 # ‣ root-level lookup
  35 #   – Asso__f[16#AE0C1A48] = ASSO_AASS | ASSO_ISSET|ASSO_ALLOC
  36 #   – Asso__k[16#AE0C1A48] = 'test' (hash: AE0C1A48)
  37 # ‣ Asso_AE0C1A48 = top-level
  38 #   – Asso_AE0C1A48_f[16#BF959A6E] = ASSO_AIDX | ASSO_ISSET|ASSO_ALLOC
  39 #   – Asso_AE0C1A48_k[16#BF959A6E] = 'foo' (hash: BF959A6E)
  40 # ‣ Asso_AE0C1A48BF959A6E = next-level
  41 #   – Asso_AE0C1A48BF959A6E_f[0] = ASSO_AASS | ASSO_ISSET|ASSO_ALLOC
  42 #   – Asso_AE0C1A48BF959A6E_k[0] = 0
  43 # ‣ Asso_AE0C1A48BF959A6E00000000 = last-level (below FOO)
  44 #   – FOO_f[16#57F1BA9A] = ASSO_INT | ASSO_ISSET|ASSO_ALLOC
  45 #   – FOO_k[16#57F1BA9A] = 'baz' (hash: 57F1BA9A)
  46 #   – FOO_v[16#57F1BA9A] = 123
  47 # When assigning a value, by default, the type of the
  48 # intermediates is set to ASSO_AASS unless it already
  49 # is ASSO_AIDX; the type of the terminals is ASSO_VAL
  50 # unless it’s ASSO_{STR,INT,REAL,BOOL,NULL} before.
  51
  52 # check prerequisites
  53 asso_x=${KSH_VERSION#????MIRBSD KSH R}
  54 asso_x=${asso_x%% *}
  55 if [[ $asso_x != +([0-9]) ]] || (( asso_x < 40 )); then
  56         print -u2 'assockit.ksh: need at least mksh R40'
  57         exit 1
  58 fi
  59
  60 # set up variables
  61 typeset -Uui16 -Z11 asso_h=0 asso_f=0 asso_k=0
  62 typeset asso_b=""
  63 set -A asso_y
  64 set -A Asso__f
  65 set -A Asso__k
  66
  67 # define constants
  68 typeset -Uui16 -Z11 -r ASSO_VAL=2#000           # type: any Korn Shell scalar
  69 typeset -Uui16 -Z11 -r ASSO_STR=2#001           # type: string
  70 typeset -Uui16 -Z11 -r ASSO_INT=2#010           # type: integral
  71 typeset -Uui16 -Z11 -r ASSO_REAL=2#011          # type: JSON float (string)
  72 typeset -Uui16 -Z11 -r ASSO_BOOL=2#100          # type: JSON "true" / "false"
  73 typeset -Uui16 -Z11 -r ASSO_NULL=2#101          # type: JSON "null"
  74 typeset -Uui16 -Z11 -r ASSO_AIDX=2#110          # type: indexed array
  75 typeset -Uui16 -Z11 -r ASSO_AASS=2#111          # type: associative array
  76 typeset -Uui16 -Z11 -r ASSO_MASK_ARR=2#110      # bitmask for array type
  77 typeset -Uui16 -Z11 -r ASSO_MASK_TYPE=2#111     # bitmask for type
  78 typeset -Uui16 -Z11 -r ASSO_ISSET=16#40000000   # element is set
  79 typeset -Uui16 -Z11 -r ASSO_ALLOC=16#80000000   # ksh element is set
  80
  81 # notes:
  82 # – the code assumes ASSO_VAL=0 < all scalar types with value \
  83 #   < ASSO_NULL < all array types
  84
  85 # public functions
  86
  87 # set a value
  88 # example: asso_setv 123 'test' 'foo' 0 'baz'
  89 function asso_setv {
  90         if (( $# < 2 )); then
  91                 print -u2 'assockit.ksh: syntax: asso_setv value key [key ...]'
  92                 return 2
  93         fi
  94         local _v=$1 _f _i
  95         shift
  96
  97         # look up the item, creating paths as needed
  98         asso__lookup 1 "$@"
  99         # if it’s an array, free that recursively
 100         if (( (_f = asso_f) & ASSO_MASK_ARR )); then
 101                 asso__r_free 1
 102                 (( _f &= ~ASSO_MASK_TYPE ))
 103         fi
 104         # if it’s got a type, check for a match
 105         if (( _i = (_f & ASSO_MASK_TYPE) )); then
 106                 asso__typeck $_i "$_v" || (( _f &= ~ASSO_MASK_TYPE ))
 107         fi
 108         # set the new flags and value
 109         asso__r_setfv $_f "$_v"
 110 }
 111
 112 # get the flags of an item, or return 1 if not set
 113 # result is in the global variable asso_f
 114 function asso_isset {
 115         if (( $# < 1 )); then
 116                 print -u2 'assockit.ksh: syntax: asso_isset key [key ...]'
 117                 return 2
 118         fi
 119
 120         asso__lookup 0 "$@"
 121 }
 122
 123 # get the type of an item (return 1 if unset, 2 if error)
 124 # example: x=$(asso_gett 'test' 'foo' 0 'baz') => $((ASSO_VAL))
 125 function asso_gett {
 126         asso_isset "$@" || return
 127         print -n -- $((asso_f & ASSO_MASK_TYPE))
 128 }
 129
 130 # get the value of an item (return 1 if unset, 2 if error)
 131 # example: x=$(asso_getv 'test' 'foo' 0 'baz') => 123
 132 function asso_getv {
 133         asso_loadv "$@" || return
 134         print -nr -- "$asso_x"
 135 }
 136
 137 # get the value of an item, but result is in the global variable asso_x
 138 function asso_loadv {
 139         if (( $# < 1 )); then
 140                 print -u2 'assockit.ksh: syntax: asso_loadv key [key ...]'
 141                 return 2
 142         fi
 143
 144         asso__lookup 0 "$@" || return 1
 145         if (( (asso_f & ASSO_MASK_TYPE) < ASSO_NULL )); then
 146                 nameref _Av=${asso_b}_v
 147                 asso_x=${_Av[asso_k]}
 148         else
 149                 asso_x=""
 150         fi
 151 }
 152
 153 # get all set keys of an item of array type (return 1 if no array)
 154 # result is in the global variable asso_y
 155 function asso_loadk {
 156         if (( $# < 1 )); then
 157                 print -u2 'assockit.ksh: syntax: asso_loadk key [key ...]'
 158                 return 2
 159         fi
 160
 161         asso__lookup 0 "$@" || return 1
 162         (( asso_f & ASSO_MASK_ARR )) || return 1
 163         nameref _keys=${asso_b}${asso_k#16#}_k
 164         set -A 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) )); 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) )); 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) )); 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 )); 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 )) && 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)
 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) )); 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 )) || return 1
 398                         asso__r_setk "$_k"
 399                 fi
 400                 _n=$_n${asso_k#16#}
 401         done
 402         return 0
 403 }
 404
 405 # set flags for asso_b[asso_k] and update asso_f
 406 function asso__r_setf {
 407         nameref _Af=${asso_b}_f
 408
 409         asso_f=$(($1 | ASSO_ISSET | ASSO_ALLOC))
 410         _Af[asso_k]=$asso_f
 411 }
 412
 413 # set flags and value for asso_b[asso_k] and update asso_f
 414 function asso__r_setfv {
 415         nameref _Af=${asso_b}_f
 416         nameref _Av=${asso_b}_v
 417
 418         _Av[asso_k]=$2
 419         asso_f=$(($1 | ASSO_ISSET | ASSO_ALLOC))
 420         _Af[asso_k]=$asso_f
 421 }
 422
 423 # set key for not yet existing asso_b[asso_k] and update asso_f
 424 function asso__r_setk {
 425         nameref _Af=${asso_b}_f
 426         nameref _Ak=${asso_b}_k
 427
 428         _Ak[asso_k]=$1
 429         asso_f=$((ASSO_ALLOC))
 430         _Af[asso_k]=$asso_f
 431 }
 432
 433 # in asso_b of type asso_f look up element $1
 434 # set its asso_f and asso_k or return 1 when not found
 435 function asso__lookup_once {
 436         local _e=$1 _seth=0
 437         nameref _Af=${asso_b}_f
 438         nameref _Ak=${asso_b}_k
 439
 440         if (( (asso_f & ASSO_MASK_TYPE) == ASSO_AIDX )); then
 441                 asso_k=$((_e))
 442         else
 443                 asso_k=16#${_e@#}
 444 #               asso_k=$(somehash "$_e")
 445                 while :; do
 446                         asso_f=${_Af[asso_k]}
 447                         (( asso_f & ASSO_ALLOC )) || break
 448                         if (( !(asso_f & ASSO_ISSET) )); then
 449                                 if (( !_seth )); then
 450                                         # save index
 451                                         asso_h=$asso_k
 452                                         _seth=1
 453                                 fi
 454                                 (( --asso_k ))
 455                                 continue
 456                         fi
 457                         [[ ${_Ak[asso_k]} = "$_e" ]] && break
 458                         # iterate
 459                         (( --asso_k ))
 460                 done
 461         fi
 462         asso_f=${_Af[asso_k]}
 463         # found?
 464         (( asso_f & ASSO_ISSET )) && return 0
 465         # not found.
 466         if (( _seth )); then
 467                 # when allocating, use this one instead
 468                 asso_k=$asso_h
 469         fi
 470         return 1
 471 }
 472
 473 # free the currently selected asso_b[asso_k] recursively
 474 function asso__r_free {
 475         local _keepkey=$1
 476         nameref _Af=${asso_b}_f
 477
 478         asso_f=${_Af[asso_k]}
 479         (( asso_f & ASSO_ALLOC )) || return
 480         if (( asso_f & ASSO_ISSET )); then
 481                 if (( asso_f & ASSO_MASK_ARR )); then
 482                         local _ob=$asso_b _ok=$asso_k
 483                         asso_b=$asso_b${asso_k#16#}
 484                         nameref _s=${asso_b}_f
 485                         for asso_k in "${!_s[@]}"; do
 486                                 asso__r_free
 487                         done
 488                         eval unset ${asso_b}_f ${asso_b}_k ${asso_b}_v
 489                         asso_b=$_ob asso_k=$_ok
 490                 fi
 491                 eval unset $asso_b'_v[asso_k]'
 492                 (( _keepkey )) || eval unset $asso_b'_k[asso_k]'
 493         fi
 494         asso_f=$((ASSO_ALLOC))
 495         _Af[asso_k]=$asso_f
 496 }
 497
 498 # make indexed asso_b[asso_k] into associative array
 499 function asso__r_idx2ass {
 500         print -u2 'assockit.ksh: warning: asso__r_idx2ass not implemented'
 501         print -u2 'assockit.ksh: warning: data will be lost'
 502         asso__r_free
 503         asso__r_setf $ASSO_AASS
 504 }