#!/bin/sh
# -*- indent-tabs-mode: nil; -*-
#:
#: A simple library to emulate simple arrays (one-dimensional) and alists
#: in a POSIX shell.
#:
#: :Author:    Franz Glasner
#: :Copyright: (c) 2024 Franz Glasner.
#:             All rights reserved.
#: :License:   BSD 3-Clause "New" or "Revised" License.
#:             See LICENSE for details.
#:             If you cannot find LICENSE see
#:             <https://opensource.org/licenses/BSD-3-Clause>
#: :ID:        @(#)@@SIMPLEVERSIONTAG@@
#:
#: This implementation is somewhat inspired by
#: https://unix.stackexchange.com/questions/137566/arrays-in-unix-bourne-shell
#:
#: Is implements one-dimensional array with one-based indexing.
#:
#: Hints and rules for arrays:
#:
#: - Every array has a NAME.
#: - One-based indexing is used.
#: - The array with name NAME is associated with a primary global or local
#:   shell variable with the same name. It contains a token TOKEN that is
#:   used in variable names that make up the backing store of the array.
#:   The value of this variable has the form ``_farr_A*_<TOKEN>``.
#: - Array elements for array NAME that has associated TOKEN are stored in
#:   global variables named ``_farr_A_<TOKEN>_<index-number>`` (values)
#:   and ``_farr_A_<TOKEN>__`` (length).
#: - An array name must conform to shell variable naming conventions.
#: - Currently the number of of elements of an array must be >= 0.
#: - Variable NAME can also be a local variable. In this case it MUST
#:   be initialized with an empty value first.
#: - Any unset global variables ``_farr_A_<TOKEN>__`` variable is a severe
#:   error normally and forces an immediate error ``exit``.
#:   Exceptions to this rule are documented.
#:
#:
#: This module also contains a very rough implementation of an alist
#: (aka dict, aka map).
#: This is implemented somewhat similar to arrays.
#:
#: Hints and rules for alists:
#:
#: - Every alist has a NAME.
#: - One-based indexing is used internally.
#: - The alist with name NAME is associated with a primary global or local
#:   shell variable with the same name. It contains a token TOKEN that is
#:   used in variable names that make up the backing stores of the alist.
#:   The value of this variable is of the form ``_farr_KV*_<TOKEN>``.
#: - The length of the alist is stored in a global ``_farr_KV_<token>__``.
#: - Every key-value pair is stored at an INDEX.
#: - Keys are stored in an associated global ``_farr_K_<TOKEN>_<INDEX>``.
#: - Values are stored in an associated global ``_farr_V_<TOKEN>_<INDEX>``.
#: - An alist name must conform to shell variable naming conventions.
#: - Currently the number of of elements of an alist must be >= 0.
#: - Variable NAME can also be a local variable. In this case it MUST
#:   be initialized with an empty value first.
#: - Any unset global variables ``_farr_KV_<TOKEN>__`` variable is a severe
#:   error normally and forces an immediate fatal error exit by calling
#:   ``exit``.
#: - The same is true if ``_farr_K_<TOKEN>_<INDEX>`` or
#:   ``_farr_V_<TOKEN>_<INDEX>`` is unexpectedly unset.
#:   Exceptions to this rule are documented.
#: - An alist preserves insertion order. Note that updating a key does not
#:   affect the order. Keys added after deletion are inserted at the end.
#: - Alists compare equal if and only if they have the same (key, value) pairs
#:   (regardless of ordering).
#:
#: Hints and rules for indexes:
#:
#:   For all functions these facts hold:
#:
#:   - Every object (array, alist) has a current length LEN.
#:   - Indexes range from 1 <= INDEX <= LEN.
#:   - Indexes 0, -1, -2 are evaluated to LEN + given index.
#:     So `0` indexes the last item, `-1` the second last and `-LEN+1` the
#:     first item.
#:   - All index (and length) values must be given as decimal numbers.
#:
#:   `null` (aka empty) and/or missing indexes are handled differently in
#:   the function context.
#:
#: Resource management:
#:
#:   Done by reference counting of arrays and alists. No borrowed references
#:   are ever returned. Every array and alist must be released using
#:   `farray_release` or `falist_release`.
#:
#: Important:
#:   All names that start with ``_farr_`` or ``__farr_`` are reserved
#:   for private use in this module.
#:   Do not use such names in your scripts.
#:
#:   Public functions start with ``farray_, ``falist_`` or ``fobject_``.
#:


_farr_array_token_prefix='_farr_A[?]:'
_farr_array_prefix=_farr_A_
_farr_alist_token_prefix='_farr_KV[?,?]:'
_farr_alist_prefix=_farr_KV_
_farr_alist_key_prefix=_farr_K_
_farr_alist_value_prefix=_farr_V_


#:
#: Internal error for fatal errors.
#:
#: Args:
#:   $@ (str): The error messages.
#:
_farr_fatal() {
    echo "ERROR:" "$@" 1>&2
    exit 70    # EX_SOFTWARE
}


:
#: Internal error for other error message.
#:
#: Args:
#:   $@ (str): The error messages.
#:
_farr_err() {
    echo "ERROR:" "$@" 1>&2
}


#:
#: Check whether given argument string is a decimal number string
#:
#: Args:
#:   $1: The string to be checked
#:
#: Returns:
#:   int: 0 (truish) if `$1` is a valid decimal number,
#:        1 (falsy) otherwise
#:
#: See Also:
#:   https://mywiki.wooledge.org/BashFAQ/054
#:
_farr_is_decimal_number() {
    case "$1" in
        '')
            # empty is not allowed
            return 1;;
        +|-)
            # just the sign is not allowed
            return 1;;
        *)
            # FALL THROUGH
            ;;
    esac
    # here we can trim the optional sign safely
    case "${1#[-+]}" in
        0*[!01234567]*)
            # non-octal
            return 1;;
        *[!0123456789]*)
            # non-decimal
            return 1;;
        *)
            return 0;;
    esac
}


#:
#: From an input index value compute an effective index value and store
#: it into a variable with a given name.
#:
#: Args:
#:   $1 (str): The name of a variable where to store the result
#:   $2 (int, null): The index value to check.
#:                   It must be a valid decimal number or the `null` value.
#:                   If the argument is `null` then ``$3 + 1`` is used as the
#:                   resulting effective index value. For this to work a
#:                   valid length must be given in `$3`.
#:                   If the argument is `<= 0` then -- if `$3` is given
#:                   the effective index is computed as ``$3 + $2``.
#:   $3 (int, optional): If given a length value that is used to compute
#:                       effective index values in some cases (`$2` is null or
#:                       `$2` <= 0).
#:
_farr_make_index() {
    local __farr_mi_varname __farr_mi_index __farr_mi_length

    __farr_mi_varname="$1"
    __farr_mi_index="$2"
    __farr_mi_length="${3-}"

    # If it is given and non-null it must be a valid decimal length number
    if [ -n "${__farr_mi_length}" ]; then
        _farr_is_decimal_number "${__farr_mi_length}" || _farr_fatal "given length is not a valid decimal number"
    fi

    if [ -z "${__farr_mi_index}" ]; then
        if [ -n "${__farr_mi_length}" ]; then
            eval "${__farr_mi_varname}"="\$((__farr_mi_length + 1))"
        else
            _farr_fatal "length not given: cannot autocompute index"
        fi
    else
        _farr_is_decimal_number "${__farr_mi_index}" || _farr_fatal "given index is not a valid decimal number"
        if [ "${__farr_mi_index}" -le 0 ]; then
            if [ -n "${__farr_mi_length}" ]; then
                eval "${__farr_mi_varname}"="\$((__farr_mi_length + __farr_mi_index))"
            else
                _farr_fatal "cannot compute effective index because no length is given"
            fi
        else
            eval "${__farr_mi_varname}"=\$\{__farr_mi_index\}
        fi
    fi
}


#:
#: Quote the given input using "Dollar-Single-Quotes" to be safely used in
#: evals.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding "Dollar-Single-Quotes"
#:   (e.g. $'...').
#:
#: Using "Dollar-Single-Quotes" is not strictly posixly correct. But
#: FreeBSD's :command:`/bin/sh` understands them.
#:
#: From FreeBSD's :manpage:`sh(1)`:
#:
#:   Dollar-Single Quotes
#:
#:     Enclosing characters between ``$'`` and ``'`` preserves the literal
#:     meaning of all characters except backslashes and single quotes.
#:
#:     A backslash introduces a C-style escape sequence.
#:     Most important here:
#:
#:       ``\\``
#:                Literal backslash
#:
#:       ``\'``
#:                Literal single-quote
#:
_farr_quote_for_eval_dsq() {
    printf "\$'%s'" "$(_farr_inner_quote_for_dsq "${1}")"
}


#:
#: Helper to quote for "Dollar-Single-Quotes".
#:
#: This function handles just the quoting mechanics. It does not surround
#: the result with any other string decoration.
#: See also `_farr_quote_for_eval_dsq`.
#:
_farr_inner_quote_for_dsq() {
    printf "%s" "${1}" \
        | LC_ALL=C /usr/bin/sed -e $'s/\\\\/\\\\\\\\/g' -e $'s/\'/\\\\\'/g'
    #                              escape a backslash      escape a single quote
    # '    # make Emacs happy for correct syntax highlighting
}


#:
#: Quote the given input string for eval.
#:
#: If the argument contains a ``'`` character then "Dollar-Single-Quotes"
#: are used; "Single-Quotes" otherwise.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding quotes.
#:
#:
_farr_quote_for_eval() {
    case "${1}" in
        *\'*)
            _farr_quote_for_eval_dsq "${1}"
            ;;
        *)
            printf "'%s'" "${1}"
            ;;
    esac
}


#:
#: Quote the given input using just POSIX correct "Single-Quotes" to be safely
#: used in evals.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding "Single-Quotes"
#:   (e.g. '...').
#:
#:
#: From FreeBSD's :manpage:`sh(1)`:
#:
#:   Single Quotes
#:
#:     Enclosing characters in single quotes preserves the literal
#:     meaning of all the characters (except single quotes, making it
#:     impossible to put single-quotes in a single-quoted string).
#:
_farr_quote_for_eval_sq() {
    printf "'%s'" "$(_farr_inner_quote_for_sq "${1}")"
}


#:
#: Helper to quote for "Single-Quotes".
#:
#: This function handles just the quoting mechanics. It does not surround
#: the result with any other string decoration.
#: See also `_farr_quote_for_eval_dsq`.
#:
_farr_inner_quote_for_sq() {
    printf "%s" "${1}" \
        | LC_ALL=C /usr/bin/sed -e $'s/\'/\'\\\\\\\'\'/g'
    #                             escape a single quote
    #                             (here double-escaped: for $'...' AND sed
    # '    # make Emacs happy for correct syntax highlighting
}


#:
#: Quote the given input string for eval and produce a strictly posixly correct
#: encoding.
#:
#: It does not use FreeBSD's ``$'...'`` shell feature.
#:
#: If the argument contains a ``'`` character then a proper "Single-Quotes"
#: combination is used.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding quotes.
#:
#:
_farr_quote_for_eval_strict() {
    case "${1}" in
        *\'*)
            _farr_quote_for_eval_sq "${1}"
            ;;
        *)
            printf "'%s'" "${1}"
            ;;
    esac
}


#:
#: Implementation of typing
#:
#: Args:
#:   $1 (str): The (variable) name of an object
#:
#: Output (stdout):
#:   - array: an array
#:   - alist: an alist
#:   - null: an empty thing
#:   - value: some other shell type (string, number, ...)
#:   - unknown: if the name in `$1` was not given
#:
#: Returns:
#:   int: 0 always
#:
fobject_type() {
    local __farr_type_name

    local __farr_type_token

    __farr_type_name="${1-}"
    if [ -n "${__farr_type_name}" ] ; then
        eval __farr_type_token=\"\$\{"${__farr_type_name}"+SET\}\"
        if [ "${__farr_type_token}" = 'SET' ] ; then
            if eval __farr_type_token=\"\$\{"${__farr_type_name}"\}\" ; then
                case "${__farr_type_token}" in
                    '')
                        printf '%s' 'null';;
                    "${_farr_array_token_prefix}"*)
                        printf '%s' 'array';;
                    "${_farr_alist_token_prefix}"*)
                        printf '%s' 'alist';;
                    *)
                        printf '%s' 'value';;
                esac
            else
                # error in evaluation
                printf '%s' 'error'
            fi
        else
            # unset
            printf '%s' 'unknown'
        fi
    else
        # no name given
        printf '%s' 'unknown'
    fi
    return 0
}


#:
#: Just an official alias for `fobject_type`
#:
farray_type() {
    fobject_type "$@"
}


#:
#: Test whether `$1` is an array.
#:
#: Args:
#:   $1 (str): The name of an object
#:
#: Returns:
#:   int: 0 if `$1` is an array, 1 otherwise
#:
farray_isarray() {
    [ "$(fobject_type "$@")" = 'array' ]
}


#:
#: Create a new array.
#:
#: It is assumed that the array does not exist already.
#:
#: Args:
#:   $1 (str): The name of the array.
#:             Must conform to shell variable naming conventions.
#:   $2... (optional): Initialization values that will be appended to the
#:                     freshly created array.
#:
#: Exit:
#:   Iff the array already exists in some fashion (token and/or storage).
#:
farray_create() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len

    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing farray name"
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    [ -n "${__farr_token}" ] && _farr_fatal "object \`${__farr_name}' already created (value \`${__farr_token}')"

    __farr_token="$(/usr/bin/hexdump -v -e '/1 "%02x"' -n 16 '/dev/urandom')"

    __farr_gvrname=${_farr_array_prefix}${__farr_token}

    # Check whether the variable already exists
    eval __farr_len=\$\{${__farr_gvrname}__+SET\}
    [ -n "${__farr_len}" ] && _farr_fatal "farray \`${__farr_name}' already exists: existing token \`${__farr_token}'"

    # Really create the storage by initializing its length ...
    eval ${__farr_gvrname}__=0
    # ... and its reference count
    eval ${__farr_gvrname}_C=1
    # And associate the token with the array name
    eval "${__farr_name}=\"\${_farr_array_token_prefix}\${__farr_token}\""

    #
    # When there are values to populate the array with.
    # Note that the array's name is not shifted away yet and must be taken
    # into account. It is also needed for `farray_append`.
    #
    if [ $# -gt 1 ]; then
	farray_append "$@"
    fi
}


#:
#: Internal helper to get all the metadata for an array.
#:
#: Args:
#:   $1 (str): The name of the array or a complete array value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_gvrname (str): The variable prefix for all items.
#:   __farr_len (int): The length of the array.
#:
#: Exit:
#:   Iff the array does not exist in some fashion (token and/or storage).
#:
_farr_array_get_meta() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            # ambiguous
            _farr_fatal "missing farray name or token value"
            ;;
        "${_farr_array_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_array_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_fatal "object \`${__farr_name}' not created properly: token empty"
                    ;;

                "${_farr_array_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_array_token_prefix}"}"
                    ;;
                *)
                    _farr_fatal "object \`${__farr_name}' is not an array"
                    ;;
            esac
            ;;
    esac
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\$\{${__farr_gvrname}__:+SET\}
    [ -z "${__farr_len}" ] && _farr_fatal "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no storage for token \`${__farr_token}'"
    eval __farr_tmp_refcount=\$\{${__farr_gvrname}_C:+SET\}
    [ -z "${__farr_tmp_refcount}" ] && _farr_fatal "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt for token \`${__farr_token}'"
    eval __farr_len=\"\$\{${__farr_gvrname}__\}\"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an array.
#:
#: Args:
#:   $1 (str): The name of the array or a complete array value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_gvrname (str): The variable prefix for all items.
#:   __farr_len (int): The length of the array
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing.
#:
_farr_array_tryget_meta() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_token=''
    __farr_gvrname=''
    __farr_len=''
    __farr_name="${1-}"

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            # ambiguous
            _farr_err "missing farray name or token value"
            return 1
            ;;
        "${_farr_array_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_array_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_err "object \`${__farr_name}' not created properly: token empty"
                    return 1
                    ;;

                "${_farr_array_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_array_token_prefix}"}"
                    ;;
                *)
                    _farr_err "object \`${__farr_name}' is not an array"
                    return 1
                    ;;
            esac
            ;;
    esac
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\$\{${__farr_gvrname}__:+SET\}
    if [ -z "${__farr_len}" ] ; then
        _farr_err "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no storage for token \`${__farr_token}'"
        return 1
    fi
    eval __farr_tmp_refcount=\$\{${__farr_gvrname}_C:+SET\}
    if [ -z "${__farr_tmp_refcount}" ] ; then
        _farr_err "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt for token \`${__farr_token}'"
        return 1
    fi
    eval __farr_len=\"\$\{${__farr_gvrname}__\}\"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an array.
#:
#: This function is similar to `_farr_array_tryget_meta` but normally fatal
#: errors are reported with a "normal" error return.
#:
#: All output variables are properly initialized to the `null` value.
#:
#: Args:
#:   $1 (str): The name of the array or a complete array value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_gvrname (str): The variable prefix for all items.
#:   __farr_len (int): The length of the array
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing or `$1` is not an array
#:
#: Important:
#:   No fatal error exits should happen.
#:
_farr_array_tryget_meta_nonfatal() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_token=''
    __farr_gvrname=''
    __farr_len=''
    __farr_name="${1-}"

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            # ambiguous
            return 1
            ;;
        "${_farr_array_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_array_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    return 1
                    ;;

                "${_farr_array_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_array_token_prefix}"}"
                    ;;
                *)
                    return 1
                    ;;
            esac
            ;;
    esac
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\$\{${__farr_gvrname}__:+SET\}
    [ -z "${__farr_len}" ] && return 1
    eval __farr_tmp_refcount=\$\{${__farr_gvrname}_C:+SET\}
    [ -z "${__farr_tmp_refcount}" ] && return 1
    eval __farr_len=\"\$\{${__farr_gvrname}__\}\"
    return 0
}


#:
#: Get the length of an array and put it into a variable
#:
#: Args:
#:   $1 (str): The name of the variable to put the length into.
#:   $2 (str): The name of the array.
#:
farray_length() {
    local __farr_varname __farr_name

    local __farr_token __farr_gvrname __farr_len

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_array_get_meta "$@"
    eval "${__farr_varname}"=${__farr_len}
}


#:
#: Get the length of an array and print it to stdout.
#:
#: Args:
#:   $1 (str): The name of the array.
#:
#: Output (stdout):
#:   The number of elements of the array.
#:   If the array does not exist the output is -1.
#:
#: Returns:
#:   0 (truthy)
#:
farray_print_length() {
    local __farr_vn

    ( farray_length __farr_vn "$@" && printf "%s" "${__farr_vn}"; ) \
    || printf "%s" "-1"
}


#:
#: Append one or more values to an existing array.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2...: The values to append.
#:
farray_append() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len __farr_len_1
    local __farr_newval

    _farr_array_get_meta "$@"
    shift

    for __farr_newval in "$@"; do
        __farr_len_1=$((__farr_len + 1))

        #
        # Set value Escape properly: use $' ' and escape any
        # backslashes and single quotes.
        #
        _farr_acquire_object "${__farr_newval}"
        eval ${__farr_gvrname}_${__farr_len_1}=\"\$\{__farr_newval\}\"
        # the implementation below line does not escape properly
        #   eval ${__farr_gvrname}_${__farr_len_1}="\"${__farr_value}\""

        # Set new array length
        #  ... persistently in the array data storage
        eval ${__farr_gvrname}__=${__farr_len_1}
        #  ... and locally
        __farr_len=${__farr_len_1}
    done
}


#:
#: Set an array at an index to a value.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2 (int): The index.
#:   $3 (optional): The value to set. If the value is not given the null
#:                  will be set.
#:
#: No holes are allowed in an array: only values at existing indices are
#: allowed. As an exception a value can be appended if the given index
#: is exactly the current length + 1.
#:
farray_set() {
    local __farr_name __farr_index __farr_value

    local __farr_token __farr_gvrname __farr_len __farr_len_1
    local __farr_old_value

    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # first check
    [ ${__farr_index} -lt 1 ] && _farr_fatal "index must be >= 1"
    __farr_value="${3-}"

    # For proper quoting: see farray_append
    if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_len} \) ]; then
        _farr_acquire_object "${__farr_value}"
        # replace a value at an existing index
        eval __farr_old_value=\"\$\{${__farr_gvrname}_${__farr_index}\}\"
        _farr_release_object "${__farr_old_value}"
        eval ${__farr_gvrname}_${__farr_index}=\"\$\{__farr_value\}\"
    else
        __farr_len_1=$((__farr_len + 1))
        if [ ${__farr_index} -eq ${__farr_len_1} ]; then
            _farr_acquire_object "${__farr_value}"
            # append value
            eval ${__farr_gvrname}_${__farr_len_1}=\"\$\{__farr_value\}\"
            # and set new length
            eval ${__farr_gvrname}__=${__farr_len_1}
        else
            _farr_fatal "array index out of bounds (cannot create holes)"
        fi
    fi
}


#:
#: Get an array value from a given index and put it into given variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of the existing array.
#:   $3 (int): The index.
#:
farray_get() {
    local __farr_varname __farr_name __farr_index

    local __farr_token __farr_gvrname __farr_len
    local __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt ${__farr_len} \) ]; then
	_farr_fatal "array index out of bounds"
    fi

    eval __farr_get_value=\"\$\{${__farr_gvrname}_${__farr_index}\}\"
    _farr_acquire_object "${__farr_get_value}"
    eval "${__farr_varname}"=\"\$\{__farr_get_value\}\"
}


#:
#: Try to get an array value from a given index into a variable
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of the existing array.
#:   $3 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds (i.e. EOD).
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
farray_tryget() {
    local __farr_varname __farr_name __farr_index

    local __farr_token __farr_gvrname __farr_len
    local __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt ${__farr_len} \) ]; then
	return 1
    fi

    eval __farr_get_value=\"\$\{${__farr_gvrname}_${__farr_index}\}\"
    _farr_acquire_object "${__farr_get_value}"
    eval "${__farr_varname}"=\"\$\{__farr_get_value\}\"
    return 0
}


#:
#: Delete an array value at a given index.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2 (int): The index to delete to.
#:
farray_del() {
    local __farr_name __farr_index

    local __farr_token __farr_gvrname __farr_len __farr_idx
    local __farr_del_value

    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt ${__farr_len} \) ]; then
	_farr_fatal "array index out of bounds"
    fi

    # Release the item at index
    eval __farr_del_value=\"\$\{${__farr_gvrname}_${__farr_index}\}\"
    _farr_release_object "${__farr_del_value}"

    # Move all other items down by one
    __farr_idx=${__farr_index}
    while [ ${__farr_idx} -lt ${__farr_len} ]; do
        # copy the following value to the current index
        eval ${__farr_gvrname}_${__farr_idx}=\"\$\{${__farr_gvrname}_$((__farr_idx + 1))\}\"
        __farr_idx=$((__farr_idx + 1))
    done
    # Drop the last item
    eval unset ${__farr_gvrname}_${__farr_idx}
    # Set the new length
    eval ${__farr_gvrname}__=$((__farr_len - 1))
}


#:
#: Remove the elements designated by an index and a length from an array,
#: and replace them with the elements of another array list, if any.
#:
#: Args:
#:   $1 (str, null): The name of an array where the deleted items will be
#:                   appended to. May be the `null` value if this is not
#:                   desired: nothing will be done with the deleted elements.
#:   $2 (str): The name of the array that is to be spliced
#:   $3 (int, null): Index, where to remove and/or insert elements.
#:                   A `null` index value is evaluated to `len + 1`.
#:   $4 (int, null): The length -- the number of elements to delete at given
#:                   index.
#:                   If `null` then the length from index to the end of the
#:                   array is applied ("automatic").
#:   $5 (str, null, optional): An array whose elements will be inserted at
#:                             given index.
#:
#: Using this universal function you can insert, replace or delete items.
#:
#: Examples:
#:
#:   Using ARRAY for the array to be changed and INSERTED for the new
#:   items and DELETED/POPPED for the returned items:
#:
#:   Prepend (insert at the start position)::
#:
#:     farray_splice "" ARRAY 1 0 INSERTED
#:
#:   Extend (insert after the end position)::
#:
#:     farray_splice "" ARRAY "" 0 INSERTED
#:
#:   Copy INSERTED into ARRAY, replacing the complete existing content::
#:
#:     farray_splice "" ARRAY 1 "" INSERTED
#:
#:   Copy INSERTED into ARRAY, replacing the complete existing content and
#:   returning it in DELETED::
#:
#:     farray_splice DELETED ARRAY 1 "" INSERTED
#:
#:   Pop the first item::
#:
#:     farray_splice POPPED ARRAY 1 1
#:
#:   Pop the last item::
#:
#:     farray_splice POPPED ARRAY 0 1
#:
#:   Shift by one item (similar to pop the first item, but no return value)::
#:
#:     farray_splice "" ARRAY 1 1
#:
farray_splice() {
    local __farr_del_array __farr_l_name __farr_index __farr_length
    local __farr_r_name

    local __farr_del_name __farr_del_token __farr_del_gvrname __farr_del_len
    local __farr_l_token __farr_l_gvrname __farr_l_len
    local __farr_r_token __farr_r_gvrname __farr_r_len

    #
    # Dynamically scoped variables for _farr_array_tryget_meta_nonfatal()
    # and _farr_array_tryget_meta().
    #
    local __farr_name __farr_token __farr_gvrname __farr_len

    local __farr_off __farr_v __farr_delta __farr_src_idx __farr_dst_idx

    [ $# -lt 4 ] && _farr_fatal "missing required arguments"

    __farr_del_name=''
    if [ -n "${1}" ] && _farr_array_tryget_meta "${1}"; then
        __farr_del_array="${1}"
        __farr_del_name="${__farr_name}"
        __farr_del_token="${__farr_token}"
        __farr_del_gvrname="${__farr_gvrname}"
        __farr_del_len="${__farr_len}"
    fi
    _farr_array_get_meta "${2}"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"

    __farr_index="${3}"
    __farr_length="${4}"

    if _farr_array_tryget_meta_nonfatal "${5-}"; then
        __farr_r_name="${__farr_name}"
        __farr_r_token="${__farr_token}"
        __farr_r_gvrname="${__farr_gvrname}"
        __farr_r_len="${__farr_len}"
    else
        __farr_r_name=''
        __farr_r_len=0
    fi

    _farr_make_index __farr_index "${__farr_index}" "${__farr_l_len}"
    # NOTE: index value array_length + 1 is allowed: splice at the end
    [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt "$((__farr_l_len + 1))" \) ] && _farr_fatal "index out of range"

    # also check the given length
    if [ -z "${__farr_length}" ]; then
        __farr_length="$((__farr_l_len - __farr_index + 1))"
    else
        _farr_is_decimal_number "${__farr_length}" || _farr_fatal "given length is not a valid number"
        [ \( "${__farr_length}" -lt 0 \) -o \( "${__farr_length}" -gt "$((__farr_l_len - __farr_index + 1))" \) ] && _farr_fatal "length out of valid range"
    fi
    if [ ${__farr_length} -eq ${__farr_r_len} ]; then
        # Just replace
        __farr_off=0
        while [ ${__farr_off} -lt ${__farr_length} ]; do
            eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"
            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval __farr_v=\"\$\{${__farr_r_gvrname}_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            eval ${__farr_l_gvrname}_$((__farr_index + __farr_off))=\"\$\{__farr_v\}\"
            __farr_off=$((__farr_off + 1))
        done
    elif [ ${__farr_length} -gt ${__farr_r_len} ]; then
        # More to delete than to copy: the resulting array shrinks
        __farr_delta=$((__farr_length - __farr_r_len))
        __farr_off=0
        while [ ${__farr_off} -lt ${__farr_r_len} ]; do
            eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"
            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval __farr_v=\"\$\{${__farr_r_gvrname}_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            eval ${__farr_l_gvrname}_$((__farr_index + __farr_off))=\"\$\{__farr_v\}\"
            __farr_off=$((__farr_off + 1))
        done
        # Copy / unset the rest that is to delete
        while [ ${__farr_off} -lt ${__farr_length} ]; do
            eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"
            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval unset ${__farr_l_gvrname}_$((__farr_index + __farr_off))
            __farr_off=$((__farr_off + 1))
        done
        # Move the rest -- here no refcount changes
        __farr_src_idx=$((__farr_index + __farr_length))
        __farr_dst_idx=$((__farr_index + __farr_r_len))
        while [ ${__farr_src_idx} -le ${__farr_l_len} ]; do
            eval __farr_v=\"\$\{${__farr_l_gvrname}_${__farr_src_idx}\}\"
            eval ${__farr_l_gvrname}_${__farr_dst_idx}=\"\$\{__farr_v\}\"
            eval unset ${__farr_l_gvrname}_${__farr_src_idx}
            __farr_src_idx=$((__farr_src_idx + 1))
            __farr_dst_idx=$((__farr_dst_idx + 1))
        done
        # Adjust the length
        eval ${__farr_l_gvrname}__=$((__farr_l_len - __farr_delta))
    else
        # More to copy than to delete: the resulting array grows
        __farr_delta=$((__farr_r_len - __farr_length))
        __farr_off=0
        while [ ${__farr_off} -lt ${__farr_length} ]; do
            eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"

            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval __farr_v=\"\$\{${__farr_r_gvrname}_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            eval ${__farr_l_gvrname}_$((__farr_index + __farr_off))=\"\$\{__farr_v\}\"
            __farr_off=$((__farr_off + 1))
        done
        #
        # Make room from last item to the first non-deleted
        # -- no refcount changes
        #
        __farr_src_idx=${__farr_l_len}
        __farr_dst_idx=$((__farr_src_idx + __farr_delta))
        while [ ${__farr_src_idx} -ge $((__farr_index + __farr_length)) ]; do
            eval __farr_v=\"\$\{${__farr_l_gvrname}_${__farr_src_idx}\}\"
            eval ${__farr_l_gvrname}_${__farr_dst_idx}=\"\$\{__farr_v\}\"
            __farr_src_idx=$((__farr_src_idx - 1))
            __farr_dst_idx=$((__farr_dst_idx - 1))
        done
        #
        # Copy the rest of the given data to be inserted
        #
        # NOTE: The offset variable __farr_off from above is NOT changed in
        #       between and valid here!
        #
        while [ ${__farr_off} -lt ${__farr_r_len} ]; do
            eval __farr_v=\"\$\{${__farr_r_gvrname}_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            eval ${__farr_l_gvrname}_$((__farr_index + __farr_off))=\"\$\{__farr_v\}\"
            __farr_off=$((__farr_off + 1))
        done
        # Adjust the length
        eval ${__farr_l_gvrname}__=$((__farr_l_len + __farr_delta))
    fi
    return 0
}


#:
#: Merge two *sorted* arrays using the mergesort algorithm.
#:
#: Sources: - https://de.wikipedia.org/wiki/Mergesort
#:          - https://en.wikipedia.org/wiki/Merge_sort
#:
#: Args:
#:   $1 (str): The result array where all the sorted items will be appended to
#:   $2 (str): The first sorted input array
#:   $3 (str): The second sorted input array
#:
farray_merge() {
    local __farr_result __farr_input_1 __farr_input_2

    local __farr_name __farr_token __farr_gvrname __farr_len
    local __farr_name_1 __farr_token_1 __farr_gvrname_1 __farr_len_1
    local __farr_name_2 __farr_token_2 __farr_gvrname_2 __farr_len_2
    local __farr_idx_1 __farr_idx_2 __farr_item_1 __farr_item_2

    _farr_array_get_meta "$2"
    __farr_input_1="$2"
    __farr_name_1="${__farr_name}"
    __farr_token_1="${__farr_token}"
    __farr_gvrname_1="${__farr_gvrname}"
    __farr_len_1="${__farr_len}"
    _farr_array_get_meta "$3"
    __farr_input_2="$3"
    __farr_name_2="${__farr_name}"
    __farr_token_2="${__farr_token}"
    __farr_gvrname_2="${__farr_gvrname}"
    __farr_len_2="${__farr_len}"
    _farr_array_get_meta "$1"
    __farr_result="$1"

    __farr_idx_1=1
    if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
        eval __farr_item_1=\"\$\{${__farr_gvrname_1}_${__farr_idx_1}\}\"
    fi
    __farr_idx_2=1
    if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
        eval __farr_item_2=\"\$\{${__farr_gvrname_2}_${__farr_idx_2}\}\"
    fi
    while [ \( "${__farr_idx_1}" -le "${__farr_len_1}" \) -a \( "${__farr_idx_2}" -le "${__farr_len_2}" \) ]; do
        # shellcheck disable=SC3012 # lexicographical '<' is undefined in POSIX
        if [ \( "${__farr_item_1}" '<' "${__farr_item_2}" \) -o \( "${__farr_item_1}" '=' "${__farr_item_2}" \) ] ; then
            farray_append "${__farr_result}" "${__farr_item_1}"
            __farr_idx_1=$((__farr_idx_1 + 1))
            if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
                eval __farr_item_1=\"\$\{${__farr_gvrname_1}_${__farr_idx_1}\}\"
            fi
        else
            farray_append "${__farr_result}" "${__farr_item_2}"
            __farr_idx_2=$((__farr_idx_2 + 1))
            if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
                eval __farr_item_2=\"\$\{${__farr_gvrname_2}_${__farr_idx_2}\}\"
            fi
        fi
    done
    # Only one of the two while-loops below will be entered
    while [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; do
        eval __farr_item_1=\"\$\{${__farr_gvrname_1}_${__farr_idx_1}\}\"
        farray_append "${__farr_result}" "${__farr_item_1}"
        __farr_idx_1=$((__farr_idx_1 + 1))
    done
    while [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; do
        eval __farr_item_2=\"\$\{${__farr_gvrname_2}_${__farr_idx_2}\}\"
        farray_append "${__farr_result}" "${__farr_item_2}"
        __farr_idx_2=$((__farr_idx_2 + 1))
    done
    return 0
}


#:
#: Empty an existing array.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:
farray_clear() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len __farr_idx __farr_del_value

    _farr_array_get_meta "$@"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_del_value=\"\$\{${__farr_gvrname}_${__farr_idx}\}\"
        _farr_release_object "${__farr_del_value}"
	eval unset ${__farr_gvrname}_${__farr_idx}
	__farr_idx=$((__farr_idx + 1))
    done

    # Length is now zero
    eval ${__farr_gvrname}__=0
}


#:
#: Release an array.
#:
#: Decrement its reference count. If it reaches zero then destroy and
#: unset an array and all its elements.
#:
#: Args:
#:   $1 (str): The name of an array. The array may exist or not.
#:
#: Returns:
#:   - A truthy value if the array existed and has been deleted.
#:   - A falsy value if the array does not exist.
#:
farray_release() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len
    local __farr_idx __farr_del_value
    local __farr_refcnt

    _farr_array_tryget_meta "$@" || return 1

    #
    # Decrement the reference count.
    # Note that the existence of the reference count proper is already
    # checked by `_farr_array_tryget_meta`.
    #
    eval __farr_refcnt=\$\{${__farr_gvrname}_C\}
    __farr_refcnt=$((__farr_refcnt - 1))
    eval ${__farr_gvrname}_C=\$\{__farr_refcnt\}
    if [ "${__farr_refcnt}" -ne 0 ] ; then
        # Clean out the array name from the token always
        [ -n "${__farr_name}" ] && eval "${__farr_name}=''"
        return 0
    fi

    # Remove "storage" because the reference count is 0
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_del_value=\"\$\{${__farr_gvrname}_${__farr_idx}\}\"
        _farr_release_object "${__farr_del_value}"
	eval unset ${__farr_gvrname}_${__farr_idx}
	__farr_idx=$((__farr_idx + 1))
    done

    # Remove length itself ...
    eval unset ${__farr_gvrname}__
    # ... and the reference count
    eval unset ${__farr_gvrname}_C
    # Clean out the array name from the token
    [ -n "${__farr_name}" ] && eval "${__farr_name}=''"
    return 0
}


#:
#: Test the boolean truth of an array.
#:
#: Args:
#:   $1 (str): The name of the array.
#:
#: Returns:
#:   int: 0 (truthy) if the array contains elements,
#:        1 (falsy) otherwise (empty or not created/destroyed properly).
#:
farray_istrue() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len

    _farr_array_tryget_meta "$@" || return 1
    if [ "${__farr_len}" -gt 0 ]; then
        return 0
    else
        return 1
    fi
}


#:
#: Determine whether any of given values is found within the array.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2...: The value to search for.
#:
#: Returns:
#:   int: 0 (truish) if any of the argument value is found within the given
#:        array,
#:        1 (falsy) if the value is not found.
#:
farray_contains() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len
    local __farr_idx __farr_existing_value __farr_searched_value

    _farr_array_get_meta "$@"
    shift
    [ $# -lt 1 ] && _farr_fatal "no search value given"
    for __farr_searched_value in "$@"; do
        __farr_idx=1
        while [ ${__farr_idx} -le ${__farr_len} ]; do
            eval __farr_existing_value=\"\$\{${__farr_gvrname}_${__farr_idx}\}\"
            [ "${__farr_existing_value}" = "${__farr_searched_value}" ] && return 0
	    __farr_idx=$((__farr_idx + 1))
        done
    done
    return 1
}


#:
#: Try to find the index of a given value in an existing array.
#:
#: Args:
#:   $1 (str): The name of a variable where to put the found index into
#:   $2 (str): The name of an existing array
#:   $3: The value to search for
#:   $4 (int, nuĺl, optional): The start index to search for (inclusive).
#:                             If not given or `null` then `1` is used.
#:   $5 (int, null, optional):  The index to stop (inclusive).
#:                              If not given or `null` then the length of
#:                              `$2` is used.
#:
#: Returns:
#:   - 0 (truish) if the argument value is found within the given array
#:     and index constraints
#:   - 1 (falsy) otherwise
#:
farray_find() {
    local __farr_varname __farr_name __farr_searched_value
    local __farr_start __farr_end

    local __farr_token __farr_gvrname __farr_len
    local __farr_cur_find_idx __farr_existing_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_searched_value="${2+SET}"
    [ -z "${__farr_searched_value}" ] && _farr_fatal "no search value given"
    __farr_searched_value="$2"

    __farr_start="${3-}"
    [ -z "${__farr_start}" ] && __farr_start=1
    _farr_make_index __farr_start "${__farr_start}" "${__farr_len}"
    [ ${__farr_start} -lt 1 ] && _farr_fatal "start index must be >= 1"
    __farr_end="${4-}"
    [ -z "${__farr_end}" ] && __farr_end="${__farr_len}"
    _farr_make_index __farr_end "${__farr_end}" "${__farr_len}"
    [ ${__farr_end} -lt 1 ] && _farr_fatal "end index must be >= 1"
    [ ${__farr_end} -gt "${__farr_len}" ] && _farr_fatal "end index exceeds array length"

    __farr_cur_find_idx=${__farr_start}
    while [ ${__farr_cur_find_idx} -le ${__farr_end} ]; do
        eval __farr_existing_value=\"\$\{${__farr_gvrname}_${__farr_cur_find_idx}\}\"
        if [ "${__farr_existing_value}" = "${__farr_searched_value}" ]; then
            #printf "%d" ${__farr_cur_find_idx}
            eval "${__farr_varname}"=${__farr_cur_find_idx}
            return 0
        fi
	__farr_cur_find_idx=$((__farr_cur_find_idx + 1))
    done
    return 1
}


#:
#: Sort using Gnome Sort.
#:
#: This is a very simple stable sort (a variant of insertion sort).
#:
#: See: https://en.wikipedia.org/wiki/Gnome_sort
#:
#: Args:
#:   $1: The array to sort to
#:
farray_sort() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len
    local __farr_pos
    local __farr_val __farr_val_1

    _farr_array_get_meta "$@"

    __farr_pos=1
    while [ ${__farr_pos} -le "${__farr_len}" ]; do
        if [ ${__farr_pos} -eq 1 ]; then
            __farr_pos=$((__farr_pos + 1))
        else
            eval __farr_val=\"\$\{${__farr_gvrname}_${__farr_pos}\}\"
            eval __farr_val_1=\"\$\{${__farr_gvrname}_$((__farr_pos - 1))\}\"
            # shellcheck disable=SC3012  # POSIX sh: lexicographical > undef
            if [ \( "${__farr_val}" '>' "${__farr_val_1}" \) -o \( "${__farr_val}" '=' "${__farr_val_1}" \) ] ; then
                __farr_pos=$((__farr_pos + 1))
            else
                # swap
                eval ${__farr_gvrname}_${__farr_pos}=\"\$\{__farr_val_1\}\"
                eval ${__farr_gvrname}_$((__farr_pos - 1))=\"\$\{__farr_val\}\"
                __farr_pos=$((__farr_pos - 1))
            fi
        fi
    done
}


#:
#: Join all the elements in given array with a separator and put the result
#: into a variable.
#:
#: Args:
#:   $1 (str): The name of a variable where to put joined string value into.
#:   $2 (str): The name of an existing array.
#:   $3 (str, optional): The separator (default: a space `` ``).
#:
farray_join() {
    local __farr_varname __farr_name __farr_separator

    local __farr_token __farr_gvrname __farr_len __farr_join_idx
    local __farr_command __farr_real_separator __farr_current_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_separator="${2-" "}"

    __farr_real_separator=""
    __farr_command=""

    __farr_join_idx=1
    while [ ${__farr_join_idx} -le ${__farr_len} ]; do
	eval __farr_current_value=\"\$\{${__farr_gvrname}_${__farr_join_idx}\}\"
	__farr_command="${__farr_command}${__farr_real_separator}${__farr_current_value}"
	__farr_real_separator="${__farr_separator}"
	__farr_join_idx=$((__farr_join_idx + 1))
    done
    eval "${__farr_varname}"=\"\$\{__farr_command\}\"
}


#:
#: Join all the elements in given array with a space `` `` character while
#: escaping properly for feeding into shell's ``eval`` and put it into a
#: variable.
#:
#: It is meant that ``eval "$(farray_join_for_eval ARRAY)"`` is safe:
#: every item of the array becomes a word when the eval evaluates the
#: joined string.
#:
#: Args:
#:   $1 (str): The name of a variable where to put joined and properly encoded
#:             string value into.
#:   $2 (str): The name of an existing array.
#:
#: Output (stdout):
#:   The result string.
#:
farray_join_for_eval() {
    local __farr_varname  __farr_name

    local __farr_token __farr_gvrname __farr_len
    local __farr_join_idx __farr_command __farr_real_separator
    local __farr_current_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_real_separator=""
    __farr_command=""

    __farr_join_idx=1
    while [ ${__farr_join_idx} -le ${__farr_len} ]; do
	eval __farr_current_value=\"\$\{${__farr_gvrname}_${__farr_join_idx}\}\"
	__farr_command="${__farr_command}${__farr_real_separator}$(_farr_quote_for_eval "${__farr_current_value}")"
	__farr_real_separator=' '
	__farr_join_idx=$((__farr_join_idx + 1))
    done
    eval "${__farr_varname}"=\"\$\{__farr_command\}\"
}


#:
#: Join all the elements in given array with a space `` `` character while
#: escaping properly for feeding into shell's ``eval``.
#:
#: ``eval "$(farray_join_for_eval ARRAY)"`` is safe:
#: every item of the array becomes a word when the eval evaluates the
#: joined string.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:
#: Output (stdout):
#:   The joined and properly encoded string.
#:
farray_print_join_for_eval() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len
    local __farr_join_idx __farr_current_value

    _farr_array_get_meta "$@"

    __farr_join_idx=1
    while [ ${__farr_join_idx} -le ${__farr_len} ]; do
	eval __farr_current_value=\"\$\{${__farr_gvrname}_${__farr_join_idx}\}\"
        if [ ${__farr_join_idx} -gt 1 ]; then
            printf "%s" " "
        fi
        printf "%s" "$(_farr_quote_for_eval "${__farr_current_value}")"
	__farr_join_idx=$((__farr_join_idx + 1))
    done
}


#:
#: Test whether two arrays are equal.
#:
#: Two arrays are equal if they have both the same length and if
#: all elements are equal (using ``test value1 = value2``).
#:
#: Args:
#:   $1 (str): The name of the first array
#:   $2 (str): The name of the second array
#:
#: Returns:
#:   int: 0 if both input arrays are equal, 1 otherwise
#:
farray_are_equal() {
    local __farr_l_name __farr_r_name

    local __farr_l_token __farr_l_gvrname __farr_l_len
    local __farr_r_token __farr_r_gvrname __farr_r_len

    local __farr_name __farr_token __farr_gvrname __farr_len
    local __farr_idx __farr_vl __farr_vr

    [ $# -ne 2 ] && _farr_fatal "missing array"

    _farr_array_get_meta "$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"

    _farr_array_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_gvrname="${__farr_gvrname}"
    __farr_r_len="${__farr_len}"

    [ ${__farr_l_len} -ne ${__farr_r_len} ] && return 1

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_l_len} ]; do
        eval __farr_vl=\"\$\{${__farr_l_gvrname}_${__farr_idx}\}\"
        eval __farr_vr=\"\$\{${__farr_r_gvrname}_${__farr_idx}\}\"
        [ "${__farr_vl}" != "${__farr_vr}" ] && return 1
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Call a function for every element in an array starting at the first index.
#:
#: The function to be called must accept at least three arguments:
#: - the array name
#: - the current index
#: - the element value at the current index
#: - all the extra arguments (`$3`, `$4`, ...) given as arguments are
#:   forwarded also
#:
#: The iteration stops if the called function returns a falsy value.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2 (str): The name of a function to be called with three arguments.
#:   $3... (optional): Extra arguments forwared to `$2` also
#:
#: Warning:
#:   If the number of elements changes while being in `farray_for_each` then
#:   the behaviour is undefined.
#:   The current implementation determines the length of the array once
#:   at the start of execution.
#:
farray_for_each() {
    local __farr_name __farr_callback

    local __farr_token __farr_gvrname __farr_len __farr_idx __farr_rv
    local __farr_gm_name_or_value
    local __farr_feval

    __farr_gm_name_or_value="${1-}"
    _farr_array_get_meta "$@"

    __farr_callback="${2-}"
    [ -z "${__farr_callback}" ] && _farr_fatal "missing callback function name"

    shift 2

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_feval=\"\$\{${__farr_gvrname}_${__farr_idx}\}\"
        _farr_acquire_object "${__farr_feval}"
	eval "${__farr_callback} \"\${__farr_name:-\"\${__farr_gm_name_or_value}\"}\" \"\${__farr_idx}\" \"\${__farr_feval}\" \"\$@\""
	__farr_rv=$?
        _farr_release_object "${__farr_feval}"
	[ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
	__farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Like `farray_for_each`, but the callback function is called in reversed
#: order -- beginning with the last index.
#:
farray_reversed_for_each() {
    local __farr_name __farr_callback

    local __farr_token __farr_gvrname __farr_len __farr_idx __farr_rv
    local __farr_gm_name_or_value
    local __farr_feval

    __farr_gm_name_or_value="${1-}"
    _farr_array_get_meta "$@"
    __farr_callback="${2-}"
    [ -z "${__farr_callback}" ] && _farr_fatal "missing callback function name"

    shift 2

    __farr_idx=${__farr_len}
    while [ ${__farr_idx} -gt 0 ]; do
        eval __farr_feval=\"\$\{${__farr_gvrname}_${__farr_idx}\}\"
        _farr_acquire_object "${__farr_feval}"
	eval "${__farr_callback} \"\${__farr_name:-\"\${__farr_gm_name_or_value}\"}\" \"\${__farr_idx}\" \"\${__farr_feval}\" \"\$@\""
	__farr_rv=$?
        _farr_release_object "${__farr_feval}"
	[ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
	__farr_idx=$((__farr_idx - 1))
    done
    return 0
}


#:
#: Print the contents of an array to stderr.
#:
#: Args:
#:   $1 (str): The name of an array. The array may exist or not.
#:
#: Returns:
#:   int: 0
#:
farray_debug() {
    _farr_array_debug '' "$@"
}


#:
#: Internal implementation of `farray_debug`.
#:
#: Args:
#:   $1 (str): The indent
#:   $2 (str): The name or the complete prefixed token of an array
#:
#: Returns:
#:   int: 0
#:
_farr_array_debug() {
    local __farr_debug_indent __farr_name

    local __farr_token __farr_gvrname __farr_len __farr_name_or_token

    __farr_debug_indent="${1}"
    shift
    if ! _farr_array_tryget_meta "$@"; then
        printf "%sDEBUG: no (meta-)data for farray \`%s'\\n" "${__farr_debug_indent}" "${1-}" 1>&2
        return 0
    fi
    __farr_name_or_token="${__farr_name:-"${1}"}"
    if [ -n "${__farr_name}" ]; then
        printf "%sDEBUG: array \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_name}" "${__farr_len}" 1>&2
    else
        printf "%sDEBUG: array with token \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_token}" "${__farr_len}" 1>&2
    fi
    if [ ${__farr_len} -gt 0 ]; then
        printf '%sDEBUG:   the items:\n' "${__farr_debug_indent}" 1>&2
        farray_for_each "${__farr_name_or_token}" _farr_debug_print_value  "${__farr_debug_indent}" || true
    fi
    return 0
}


#:
#: Debug output helper for `farray_debug`.
#:
#: Args:
#:   $4: The current indentation string
#:
_farr_debug_print_value() {
    case "$3" in
        "${_farr_array_token_prefix}"*)
            printf "%sDEBUG:     %s: >>>\\n" "$4" "$2" 1>&2
            _farr_array_debug "$4    " "$3"
            # let the return value pass through
            ;;
        "${_farr_alist_token_prefix}"*)
            printf "%sDEBUG:     %s: >>>\\n" "$4" "$2" 1>&2
            _farr_alist_debug "$4    " "$3"
            # let the return value pass through
            ;;
        *)
            printf "%sDEBUG:     %s: \`%s'\\n" "$4" "$2" "$3" 1>&2
            ;;
    esac
    return 0
}


#:
#: Just an official alias for `fobject_type`
#:
falist_type() {
    fobject_type "$@"
}


#:
#: Test whether `$1` is an alist.
#:
#: Args:
#:   $1 (str): The name of an object
#:
#: Returns:
#:   int: 0 if `$1` is an alist, 1 otherwise
#:
falist_isalist() {
    [ "$(fobject_type "$@")" = 'alist' ]
}


#:
#: Create a new alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:             Must conform to shell variable naming conventions.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Exit:
#:   Iff the alist already exists.
#:
falist_create() {
    local __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len

    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing falist name"
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    [ -n "${__farr_token}" ] && _farr_fatal "object \`${__farr_name}' already created (value \`${__farr_token}')"

    __farr_token="$(/usr/bin/hexdump -v -e '/1 "%02x"' -n 16 '/dev/urandom')"

    __farr_objname=${_farr_alist_prefix}${__farr_token}
    __farr_keyname=${_farr_alist_key_prefix}${__farr_token}
    __farr_valname=${_farr_alist_value_prefix}${__farr_token}

    # Check whether the variable already exists
    eval __farr_len=\$\{${__farr_objname}__+SET\}
    [ -n "${__farr_len}" ] && _farr_fatal "falist \`${__farr_name}' already exists: existing token \`${__farr_token}'"

    # Really create the storage by initializing its length ...
    eval ${__farr_objname}__=0
    # ... and its reference count
    eval ${__farr_objname}_C=1

    # And associate the token with the array name
    eval "${__farr_name}=\"\${_farr_alist_token_prefix}\${__farr_token}\""

    #
    # When there are key-value pairs populate the alist with.
    # Note that the alist's name is not shifted away yet and must be taken
    # into account. It is also needed for `falist_set`.
    #
    if [ $# -gt 2 ]; then
	falist_set "$@"
    fi
}


#:
#: Internal helper to get all the metadata for an alist.
#:
#: Args:
#:   $1 (str): The name of the alist or a complete alist value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the alist if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name.
#:   __farr_objname (str): The variable prefix for the length ("object").
#:   __farr_keyname (str): The variable prefix for all item keys.
#:   __farr_valname (str): The variable prefix for all item values.
#:   __farr_len (int): The length of the alist.
#:
#: Exit:
#:   Iff the array does not exist in some fashion (token and/or storage).
#:
_farr_alist_get_meta() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            _farr_fatal "missing falist name or token value"
            ;;
        "${_farr_alist_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_alist_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_fatal "object \`${__farr_name}' not created properly: token empty"
                    ;;

                "${_farr_alist_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_alist_token_prefix}"}"
                    ;;
                *)
                    _farr_fatal "object \`${__farr_name}' is not an alist"
                    ;;
            esac
            ;;
    esac

    __farr_objname="${_farr_alist_prefix}${__farr_token}"
    __farr_keyname=${_farr_alist_key_prefix}${__farr_token}
    __farr_valname=${_farr_alist_value_prefix}${__farr_token}

    eval __farr_len=\$\{${__farr_objname}__:+SET\}
    [ -z "${__farr_len}" ] && _farr_fatal "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no object for token \`${__farr_token}'"
    eval __farr_tmp_refcount=\$\{${__farr_objname}_C:+SET\}
    [ -z "${__farr_tmp_refcount}" ] && _farr_fatal "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt for token \`${__farr_token}'"
    eval __farr_len="\${${__farr_objname}__}"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an alist.
#:
#: Args:
#:   $1 (str): The name of the alist or a complete alist value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the alist if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_objname (str): The variable prefix for the length ("object").
#:   __farr_keyname (str): The variable prefix for all item keys.
#:   __farr_valname (str): The variable prefix for all item values.
#:   __farr_len (int): The length of the alist.
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing.
#:
_farr_alist_tryget_meta() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            _farr_err "missing falist name or token value"
            return 1
            ;;
        "${_farr_alist_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_alist_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_err "object \`${__farr_name}' not created properly: token empty"
                    return 1
                    ;;

                "${_farr_alist_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_alist_token_prefix}"}"
                    ;;
                *)
                    _farr_err "object \`${__farr_name}' is not an alist"
                    return 1
                    ;;
            esac
            ;;
    esac

    __farr_objname="${_farr_alist_prefix}${__farr_token}"
    __farr_keyname=${_farr_alist_key_prefix}${__farr_token}
    __farr_valname=${_farr_alist_value_prefix}${__farr_token}

    eval __farr_len=\$\{${__farr_objname}__:+SET\}
    if [ -z "${__farr_len}" ] ; then
        _farr_err "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no object for token \`${__farr_token}'"
        return 1
    fi
    eval __farr_tmp_refcount=\$\{${__farr_objname}_C:+SET\}
    if [ -z "${__farr_tmp_refcount}" ] ; then
        _farr_err "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt for token \`${__farr_token}'"
        return 1
    fi
    eval __farr_len="\${${__farr_objname}__}"
    return 0
}


#:
#: Get the length of an alist and put it into a variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the length info.
#:   $2 (str): The name of the alist.
#:
falist_length() {
    local __farr_varname __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_alist_get_meta "$@"
    eval "${__farr_varname}"=${__farr_len}
}


#:
#: Get the length of an alist and print it to stdout.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:
#: Output (stdout):
#:   The number of elements in the alist.
#:   If the array does not exist the output is -1.
#:
#: Returns:
#:   0 (truthy)
#:
falist_print_length() {
    local __farr_vn

    ( falist_length __farr_vn "$@" && printf "%s" "${__farr_vn}"; ) \
    || printf "%s" "-1"
}


#:
#: Empty an existing alist.
#:
#: Args:
#:   $1 (str): The name of the existing alist.
#:
falist_clear() {
    local __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_del_value

    _farr_alist_get_meta "$@"

    # Remove "storage"
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        # XXX FIXME: no arrays/alists as keys: should we check this
        #eval __farr_del_value=\"\$\{${__farr_valname}_${__farr_idx}\}\"
        #_farr_release_object "${__farr_del_value}"
        eval __farr_del_value=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
        _farr_release_object "${__farr_del_value}"
        eval unset ${__farr_valname}_${__farr_idx}
        eval unset ${__farr_keyname}_${__farr_idx}
        __farr_idx=$((__farr_idx + 1))
    done

    # Reset object (length) itself
    eval ${__farr_objname}__=0
    return 0
}


#:
#: Release an alist.
#:
#: Decrement its reference count. If it reaches zero then destroy and
#: unset an alist and all its items.
#:
#: Args:
#:   $1 (str): The name of an alist. The alist may exist or not.
#:
#: Returns:
#:   - A truthy value if the alist existed and has been deleted.
#:   - A falsy value if the alist does not exist.
#:
falist_release() {
    local __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_del_value
    local __farr_refcnt

    _farr_alist_tryget_meta "$@" || return 1

    #
    # Decrement the reference count.
    # Note that the existence of the reference count proper is already
    # checked by `_farr_alist_tryget_meta`.
    #
    eval __farr_refcnt=\$\{${__farr_objname}_C\}
    __farr_refcnt=$((__farr_refcnt - 1))
    eval ${__farr_objname}_C=\$\{__farr_refcnt\}
    if [ "${__farr_refcnt}" -ne 0 ] ; then
        # Clean out the alist name from the token always
        [ -n "${__farr_name}" ] && eval "${__farr_name}=''"
        return 0
    fi

    # Remove "storage" because the reference count is 0
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_del_value=\"\$\{${__farr_valname}_${__farr_idx}\}\"
        _farr_release_object "${__farr_del_value}"
        # XXX FIXME: no arrays/alists as keys: should we check this
        #eval __farr_del_value=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
        #_farr_release_object "${__farr_del_value}"
        eval unset ${__farr_valname}_${__farr_idx}
        eval unset ${__farr_keyname}_${__farr_idx}
        __farr_idx=$((__farr_idx + 1))
    done

    # Remove object (length) itself ...
    eval unset ${__farr_objname}__
    # ... and its reference count
    eval unset ${__farr_objname}_C
    # Clean out the alist name from the token
    [ -n "${__farr_name}" ] && eval "${__farr_name}=''"
    return 0
}


#:
#: Map a key to a value.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Exit:
#:   If one of the underlying arrays that implement the alist does not exist
#:   or if an internal inconsistency will be detected.
#:
falist_set() {
    local __farr_name __farr_key __farr_value

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_elkey
    local __farr_old_value

    _farr_alist_get_meta "$@"
    shift

    while [ $# -ne 0 ]; do
        [ $# -lt 1 ] && _farr_fatal "missing key"
        __farr_key="$1"
        [ $# -lt 2 ] && _farr_fatal "missing value"
        __farr_value="$2"

        __farr_idx=1
        while [ ${__farr_idx} -le ${__farr_len} ]; do
            eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\"
            if [ -n "${__farr_elkey}" ]; then
                eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
                if [ "${__farr_elkey}" = "${__farr_key}" ]; then
                    eval __farr_old_value=\"\$\{${__farr_valname}_${__farr_idx}\}\"
                    _farr_release_object "${__farr_old_value}"
                    _farr_acquire_object "${__farr_value}"
                    eval ${__farr_valname}_${__farr_idx}=\"\$\{__farr_value\}\"
                    return 0
                fi
            else
                _farr_fatal "key unexpectedly unset (index ${__farr_idx})"
            fi
            __farr_idx=$((__farr_idx + 1))
        done
        #
        # Not yet found: "append" ...
        #
        # NOTE: __farr_idx here already is the new correct length
        #
        __farr_len=${__farr_idx}
        #   ... the key/value pairs to storage
        eval ${__farr_keyname}_${__farr_len}=\"\$\{__farr_key\}\"
        _farr_acquire_object "${__farr_value}"
        eval ${__farr_valname}_${__farr_len}=\"\$\{__farr_value\}\"
        #   ... the new length to the storage
        eval ${__farr_objname}__=${__farr_len}
        shift 2
    done
    return 0
}


#:
#: Map a key to a value while assuming that the given keys are not already
#: in the alist.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Exit:
#:   If one of the underlying arrays that implement the alist does not exist
#:   or if an internal inconsistency will be detected.
#:
falist_add() {
    local __farr_name __farr_key __farr_value

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len

    _farr_alist_get_meta "$@"
    shift

    while [ $# -ne 0 ]; do
        [ $# -lt 1 ] && _farr_fatal "missing key"
        __farr_key="$1"
        [ $# -lt 2 ] && _farr_fatal "missing value"
        __farr_value="$2"

        #
        # We do just append ...
        #
        __farr_len=$((__farr_len + 1))
        #   ... the key/value pairs to storage
        eval ${__farr_keyname}_${__farr_len}=\"\$\{__farr_key\}\"
        _farr_acquire_object "${__farr_value}"
        eval ${__farr_valname}_${__farr_len}=\"\$\{__farr_value\}\"
        #   ... the new length to the storage
        eval ${__farr_objname}__=${__farr_len}
        shift 2
    done
    return 0
}


#:
#: Map a key to a value but error if the alist contains already an item
#: with the given key.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Returns:
#:   int: 0 (truthy) if the item got set, 1 (falsy) if there is already an
#:        item with key `$1` in the alist
#:
#: Exit:
#:   If one of the underlying arrays that implement the alist does not exist
#:   or if an internal inconsistency will be detected.
#:
falist_set_unique() {
    local __farr_name __farr_key __farr_value

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_elkey

    _farr_alist_get_meta "$@"
    shift

    while [ $# -ne 0 ]; do
        [ $# -lt 1 ] && _farr_fatal "missing key"
        __farr_key="$1"
        [ $# -lt 2 ] && _farr_fatal "missing value"
        __farr_value="$2"

        __farr_idx=1
        while [ ${__farr_idx} -le ${__farr_len} ]; do
            eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\"
            if [ -n "${__farr_elkey}" ]; then
                eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
                if [ "${__farr_elkey}" = "${__farr_key}" ]; then
                    # key is already set: would be non-unique
                    return 1
                fi
            else
                _farr_fatal "key unexpectedly unset (index ${__farr_idx})"
            fi
            __farr_idx=$((__farr_idx + 1))
        done
        #
        # Not yet found: "append" ..
        #
        # NOTE: __farr_idx here already is the new correct length
        #
        __farr_len=${__farr_idx}
        #   ... the key/value pairs to storage
        eval ${__farr_keyname}_${__farr_len}=\"\$\{__farr_key\}\"
        _farr_acquire_object "${__farr_value}"
        eval ${__farr_valname}_${__farr_len}=\"\$\{__farr_value\}\"
        #   ... the new length
        eval ${__farr_objname}__=${__farr_len}
        shift 2
    done
    return 0
}


#:
#: Update an alist from another alist.
#:
#: Key-values from the other alist are given precedence.
#:
#: Args:
#:   $1 (str): The name of the alist that is to be updated.
#:   $2 (str): The name of the other alist.
#:
falist_update() {

    local __farr_l_name __farr_r_name

    local __farr_l_token __farr_l_objname __farr_l_keyname __farr_l_valname __farr_l_len
    local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len

    local __farr_name __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_l_idx __farr_r_idx __farr_r_key  __farr_l_key __farr_value

    [ $# -ne 2 ] && _farr_fatal "exactly two arrays must be given"
    _farr_alist_get_meta "$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_objname="${__farr_objname}"
    __farr_l_keyname="${__farr_keyname}"
    __farr_l_valname="${__farr_valname}"
    __farr_l_len="${__farr_len}"
    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_len="${__farr_len}"

    __farr_r_idx=1
    while [ ${__farr_r_idx} -le ${__farr_r_len} ]; do
        eval __farr_r_key=\"\$\{${__farr_r_keyname}_${__farr_r_idx}\}\"

        __farr_l_idx=1
        while [ ${__farr_l_idx} -le ${__farr_l_len} ]; do
            eval __farr_l_key=\"\$\{${__farr_l_keyname}_${__farr_l_idx}\}\"
            if [ "${__farr_l_key}" = "${__farr_r_key}" ]; then
                eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_r_idx}\}\"
                _farr_acquire_object "${__farr_value}"
                eval ${__farr_l_valname}_${__farr_l_idx}=\"\$\{__farr_value\}\"
                break
            fi
            __farr_l_idx=$((__farr_l_idx + 1))
        done
        #
        # If __farr_l_idx > __farr_l_len: Not yet found: "append" ..
        #
        # NOTE: __farr_l_idx is here also the new correct length
        #
        if [ ${__farr_l_idx} -eq $((__farr_l_len + 1)) ]; then
            #   ... the key/value pairs to storage
            eval ${__farr_l_keyname}_${__farr_l_idx}=\"\$\{__farr_r_key\}\"
            eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_r_idx}\}\"
            _farr_acquire_object "${__farr_value}"
            eval ${__farr_l_valname}_${__farr_l_idx}=\"\$\{__farr_value\}\"
            #   ... the new length in storage
            eval ${__farr_l_objname}__=${__farr_l_idx}
            #   ... and temporary here
            __farr_l_len=${__farr_l_idx}
        fi
        __farr_r_idx=$((__farr_r_idx + 1))
    done
    return 0
}


#:
#: Merge two *sorted* alists using the mergesort algorithm.
#:
#: A "sorted" alist is an alist where all the key-value pairs are added
#: in a sorted fashion: `falist_keys()` yields a lexicographcally sorted
#: array.
#:
#: Sources: - https://de.wikipedia.org/wiki/Mergesort
#:          - https://en.wikipedia.org/wiki/Merge_sort
#:
#: Args:
#:   $1 (str): The result alist where all the sorted items will be added to
#:             using `falist_add`
#:   $2 (str): The first sorted input alist
#:   $3 (str): The second sorted input alist
#:
falist_merge() {
    local __farr_result __farr_input_1 __farr_input_2

    local __farr_name __farr_token __farr_objname __farr_valname __farr_keyname __farr_len
    local __farr_name_1 __farr_token_1 __farr_objname_1 __farr_valname_1 __farr_keyname_1 __farr_len_1
    local __farr_name_2 __farr_token_2 __farr_objname_2 __farr_valname_2 __farr_keyname_2 __farr_len_2
    local __farr_idx_1 __farr_key_1 __farr_val_2
    local __farr_idx_2 __farr_key_2 __farr_val_2

    _farr_alist_get_meta "$2"
    __farr_input_1="$2"
    __farr_name_1="${__farr_name}"
    __farr_token_1="${__farr_token}"
    __farr_objname_1="${__farr_objname}"
    __farr_keyname_1="${__farr_keyname}"
    __farr_valname_1="${__farr_valname}"
    __farr_len_1="${__farr_len}"
    _farr_alist_get_meta "$3"
    __farr_input_2="$3"
    __farr_name_2="${__farr_name}"
    __farr_token_2="${__farr_token}"
    __farr_objname_2="${__farr_objname}"
    __farr_keyname_2="${__farr_keyname}"
    __farr_valname_2="${__farr_valname}"
    __farr_len_2="${__farr_len}"
    _farr_alist_get_meta "$1"
    __farr_result="$1"

    __farr_idx_1=1
    if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
        eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\"
    fi
    __farr_idx_2=1
    if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
        eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\"
    fi
    while [ \( "${__farr_idx_1}" -le "${__farr_len_1}" \) -a \( "${__farr_idx_2}" -le "${__farr_len_2}" \) ]; do
        # shellcheck disable=SC3012 # lexicographical '<' is undefined in POSIX
        if [ \( "${__farr_key_1}" '<' "${__farr_key_2}" \) -o \( "${__farr_key_1}" '=' "${__farr_key_2}" \) ] ; then
            eval __farr_val_1=\"\$\{${__farr_valname_1}_${__farr_idx_1}\}\"
            # shellcheck disable=SC2154  # bogus __farr_val_1 is ref but not set
            falist_add "${__farr_result}" "${__farr_key_1}" "${__farr_val_1}"
            __farr_idx_1=$((__farr_idx_1 + 1))
            if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
                eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\"
            fi
        else
            eval __farr_val_2=\"\$\{${__farr_valname_2}_${__farr_idx_2}\}\"
            falist_add "${__farr_result}" "${__farr_key_2}" "${__farr_val_2}"
            __farr_idx_2=$((__farr_idx_2 + 1))
            if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
                eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\"
            fi
        fi
    done
    # Only one of the two while-loops below will be entered
    while [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; do
        eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\"
        eval __farr_val_1=\"\$\{${__farr_valname_1}_${__farr_idx_1}\}\"
        falist_add "${__farr_result}" "${__farr_key_1}" "${__farr_val_1}"
        __farr_idx_1=$((__farr_idx_1 + 1))
    done
    while [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; do
        eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\"
        eval __farr_val_2=\"\$\{${__farr_valname_2}_${__farr_idx_2}\}\"
        falist_add "${__farr_result}" "${__farr_key_2}" "${__farr_val_2}"
        __farr_idx_2=$((__farr_idx_2 + 1))
    done
    return 0
}


#:
#: Get the value that is associated with a key and put it into a variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3: The key.
#:   $4 (str, optional): The name of a variable where to store the index
#:                       of the found item into.
#:
#: Exit:
#:   - If the key is not found.
#:   - If one of the underlying arrays that implement the alist does not exist.
#:     or if an internal inconsistency will be detected.
#:
falist_get() {
    local __farr_varname __farr_name __farr_key __farr_idx_varname

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_getkey
    local __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_alist_get_meta "$@"
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_key="$2"
    __farr_idx_varname="${3-}"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\"
        if [ -n "${__farr_getkey}" ]; then
            eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
            if [ "${__farr_getkey}" = "${__farr_key}" ]; then
                eval __farr_get_value=\"\$\{${__farr_valname}_${__farr_idx}\}\"
                _farr_acquire_object "${__farr_get_value}"
                eval "${__farr_varname}"=\"\$\{__farr_get_value\}\"
                [ -n "${__farr_idx_varname}" ] && eval "${__farr_idx_varname}"=${__farr_idx}
                return 0
            fi
        else
            _farr_fatal "key unexpectedly unset (index ${__farr_idx})"
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    _farr_fatal "alist \`${__farr_name:-"${1}"}': key \`${__farr_key}' not found"
}


#:
#: Try to get the value that is associated with a key and store it in a
#: variable.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3: The key.
#:   $4 (str, optional): The name of a variable where to store the index
#:                       of the found item into.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given key is not found.
#:
falist_tryget() {
    local __farr_varname __farr_name __farr_key __farr_idx_varname

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_getkey
    local __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_alist_get_meta "$@"
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_key="$2"
    __farr_idx_varname="${3-}"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\"
        if [ -n "${__farr_getkey}" ]; then
            eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
            if [ "${__farr_getkey}" = "${__farr_key}" ]; then
                eval __farr_get_value=\"\$\{${__farr_valname}_${__farr_idx}\}\"
                _farr_acquire_object "${__farr_get_value}"
                eval "${__farr_varname}"=\"\$\{__farr_get_value\}\"
                [ -n "${__farr_idx_varname}" ] && eval "${__farr_idx_varname}"=${__farr_idx}
                return 0
            fi
        else
            _farr_fatal "key unexpectedly unset (index ${__farr_idx})"
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    return 1
}


#:
#: Try to get the key that is associated with a storage index and store it in a variable.
#:
#: Use this for iteration over values.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the key into.
#:   $2 (str): The name of an existing alist.
#:   $3 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
falist_tryget_key_at_index() {
    local __farr_varname __farr_name __farr_index

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_getikey

    __farr_varname=${1-}
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_alist_get_meta "$@"
    __farr_index="${2-}"
    [ -z "${__farr_index}" ] && _farr_fatal "missing index"
    _farr_make_index __farr_index "${__farr_index}" "${__farr_len}"

    if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_len} \) ]; then
        eval __farr_getikey=\"\$\{${__farr_keyname}_${__farr_index}+SET\}\"
        if [ -n "${__farr_getikey}" ]; then
            # no refcount change because no complex values allowed yet
            eval "${__farr_varname}"=\"\$\{${__farr_keyname}_${__farr_index}\}\"
            return 0
        else
            _farr_fatal "key unexpectedly unset (index ${__farr_index})"
        fi
    else
        return 1
    fi
}


#:
#: Try to get the value that is associated with a storage index and store it in a variable.
#:
#: Use this for iteration over keys.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
falist_tryget_value_at_index() {
    local __farr_varname __farr_name __farr_index

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_getival

    __farr_varname=${1-}
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_alist_get_meta "$@"
    __farr_index="${2-}"
    [ -z "${__farr_index}" ] && _farr_fatal "missing index"
    _farr_make_index __farr_index "${__farr_index}" "${__farr_len}"

    if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_len} \) ]; then
        eval __farr_getival=\"\$\{${__farr_valname}_${__farr_index}+SET\}\"
        if [ -n "${__farr_getival}" ]; then
            eval __farr_getival=\"\$\{${__farr_valname}_${__farr_index}\}\"
            _farr_acquire_object "${__farr_getival}"
            eval "${__farr_varname}"=\"\$\{__farr_getival\}\"
            return 0
        else
            _farr_fatal "value unexpectedly unset (index ${__farr_index})"
        fi
    else
        return 1
    fi
}


#:
#: Try to get the key-value item that is associated with a storage index and
#: store it into variables.
#:
#: Use this for iteration over key-value items.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the key into.
#:   $2 (str): The name of the variable where to put the value into.
#:   $3 (str): The name of an existing alist.
#:   $4 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
falist_tryget_item_at_index() {
    local __farr_key_varname __farr_value_varname __farr_name __farr_index

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_getikey __farr_getival

    __farr_key_varname=${1-}
    [ -z "${__farr_key_varname}" ] && _farr_fatal "missing variable name for key"
    __farr_value_varname=${2-}
    [ -z "${__farr_value_varname}" ] && _farr_fatal "missing variable name for value"
    shift 2
    _farr_alist_get_meta "$@"
    __farr_index="${2-}"
    [ -z "${__farr_index}" ] && _farr_fatal "missing index"
    _farr_make_index __farr_index "${__farr_index}" "${__farr_len}"

    if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_len} \) ]; then
        eval __farr_getikey=\"\$\{${__farr_keyname}_${__farr_index}+SET\}\"
        if [ -n "${__farr_getikey}" ]; then
            eval __farr_getival=\"\$\{${__farr_valname}_${__farr_index}+SET\}\"
            if [ -n "${__farr_getival}" ]; then
                eval "${__farr_key_varname}"=\"\$\{${__farr_keyname}_${__farr_index}\}\"
                eval __farr_getival=\"\$\{${__farr_valname}_${__farr_index}\}\"
                _farr_acquire_object "${__farr_getival}"
                eval "${__farr_value_varname}"=\"\$\{__farr_getival\}\"
                return 0
            else
                _farr_fatal "value unexpectedly unset (index ${__farr_index})"
            fi
        else
            _farr_fatal "key unexpectedly unset (index ${__farr_index})"
        fi
    else
        return 1
    fi
}


#:
#: Determine whether a key is found within the alist.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2: The key.
#:
#: Returns:
#:   0 (truthy) on success if the key is found,
#:   1 (falsy) if the given key is not found.
#:
falist_contains() {
    local __farr_name __farr_key

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_cokey

    _farr_alist_get_meta "$@"
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_key="$2"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_cokey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\"
        if [ -n "${__farr_cokey}" ]; then
            eval __farr_cokey=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
            if [ "${__farr_cokey}" = "${__farr_key}" ]; then
                return 0
            fi
        else
            _farr_fatal "key unexpectedly unset (index ${__farr_idx})"
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    return 1
}


#:
#: Try to find the index of a given key in an alist.
#:
#: Args:
#:   $1 (str): The name of a variable where to put the found index into
#:   $2 (str): The existing alist.
#:   $3: The key.
#:   $4 (int, nuĺl, optional): The start index to search for (inclusive).
#:                             If not given or `null` then `1` is used.
#:   $5 (int, null, optional):  The index to stop (inclusive).
#:                              If not given or `null` then the length of
#:                              `$2` is used.
#:
#: Returns:
#:   0 (truthy) on success if the key is found,
#:   1 (falsy) if the given key is not found.
#:
falist_find() {
    local __farr_varname __farr_name __farr_key
    local __farr_start __farr_end

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_cur_find_idx __farr_fikey

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_alist_get_meta "$@"
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_key="$2"

    __farr_start="${3-}"
    [ -z "${__farr_start}" ] && __farr_start=1
    _farr_make_index __farr_start "${__farr_start}" "${__farr_len}"
    [ ${__farr_start} -lt 1 ] && _farr_fatal "start index must be >= 1"
    __farr_end="${4-}"
    [ -z "${__farr_end}" ] && __farr_end="${__farr_len}"
    _farr_make_index __farr_end "${__farr_end}" "${__farr_len}"
    [ ${__farr_end} -lt 1 ] && _farr_fatal "end index must be >= 1"
    [ ${__farr_end} -gt "${__farr_len}" ] && _farr_fatal "end index exceeds array length"

    __farr_cur_find_idx=${__farr_start}
    while [ ${__farr_cur_find_idx} -le ${__farr_end} ]; do
        eval __farr_fikey=\"\$\{${__farr_keyname}_${__farr_cur_find_idx}+SET\}\"
        if [ -n "${__farr_fikey}" ]; then
            eval __farr_fikey=\"\$\{${__farr_keyname}_${__farr_cur_find_idx}\}\"
            if [ "${__farr_fikey}" = "${__farr_key}" ]; then
                eval "${__farr_varname}"=${__farr_cur_find_idx}
                return 0
            fi
        else
            _farr_fatal "key unexpectedly unset (index ${__farr_cur_find_idx})"
        fi
        __farr_cur_find_idx=$((__farr_cur_find_idx + 1))
    done
    return 1
}


#:
#: Internal helper to delete an item from an alist storage.
#:
#: Args:
#:   $1 (str): The name of the storage object
#:   $2 (int): The current length of the storage object (i.e. the current
#:             length of the alist)
#:   $3 (int): The storage index that will be deleted
#:   $4: if no-null use release semantics (used for values)
#:
#: Returns:
#:   int: Always 0
#:
#: Important:
#:   This is an internal function. No index and other storage consistency
#:   checks are done.
#:
#: Note:
#:   The implementation is very similar to `farray_del`.
#:   But the new length must be managed by the caller.
#:
_farr_alist_del_storage_at_index() {
    local __farr_storage_name __farr_storage_length __farr_storage_index
    local __farr_use_release

    local __farr_idx __farr_del_item

    __farr_storage_name="$1"
    __farr_storage_length="$2"
    __farr_storage_index="$3"
    __farr_use_release="$4"

    # Release the item at index -- if requested
    if [ -n "${__farr_use_release}" ] ; then
        eval __farr_del_item=\"\$\{${__farr_storage_name}_${__farr_idx}\}\"
        _farr_release_object "${__farr_del_item}"
    fi

    # Move all other items down by one
    __farr_idx=${__farr_storage_index}
    while [ ${__farr_idx} -lt ${__farr_storage_length} ] ; do
        # copy the following value to the current index
        eval ${__farr_storage_name}_${__farr_idx}=\"\$\{${__farr_storage_name}_$((__farr_idx + 1))\}\"
        __farr_idx=$((__farr_idx + 1))
    done
    # Drop the last item
    eval unset ${__farr_storage_name}_${__farr_idx}
    return 0
}


#:
#: Try to delete an item with a given key from the alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:   $2: The key of the key-value pair to delete to
#:
#: Returns:
#:   int: 0 if the key has been found and is deleted,
#:        1 if the key has not been found.
#:
falist_trydel() {
    local __farr_name __farr_delkey

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_curkey

    _farr_alist_get_meta "$@"
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_delkey="$2"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ] ; do
        eval __farr_curkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\"
        if [ -n "${__farr_curkey}" ]; then
            eval __farr_curkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
            if [ "${__farr_curkey}" = "${__farr_delkey}" ]; then
                _farr_alist_del_storage_at_index "${__farr_valname}" "${__farr_len}" "${__farr_idx}" '1'
                _farr_alist_del_storage_at_index "${__farr_keyname}" "${__farr_len}" "${__farr_idx}" ""
                # Reduce the length by 1
                eval ${__farr_objname}__=$((__farr_len - 1))
                return 0
            fi
        else
            _farr_fatal "key unexpectedly unset (index ${__farr_idx})"
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    # Not found
    return 1
}


#:
#: Test the boolean truth of an alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:
#: Returns:
#:   int: 0 (truthy) if the alist contains items,
#:        1 (falsy) otherwise (empty or not created/destroyed properly).
#:
falist_istrue() {
    local __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len

    _farr_alist_tryget_meta "$@" || return 1
    if [ "${__farr_len}" -gt 0 ]; then
        return 0
    else
        return 1
    fi
}


#:
#: Test whether two alists are equal.
#:
#: Two alists compare equal if and only if they have the same (key, value)
#: pairs (regardless of ordering). Comparison is done using the shell's
#: builtin ``=`` operator for both keys and values.
#:
#: Args:
#:   $1 (str): The name of the first alist
#:   $2 (str): The name of the second alist
#:
#: Returns:
#:   int: 0 if both input alists are equal, 1 otherwise
#:
falist_are_equal() {
    local __farr_l_name __farr_r_name

    local __farr_l_token __farr_l_objname __farr_l_keyname __farr_l_valname __farr_l_len
    local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len

    local __farr_name __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_l_idx __farr_l_key __farr_l_value
    local __farr_r_idx __farr_r_key __farr_r_value

    [ $# -ne 2 ] && _farr_fatal "missing alist parameter"

    _farr_alist_get_meta "$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_objname="${__farr_objname}"
    __farr_l_keyname="${__farr_keyname}"
    __farr_l_valname="${__farr_valname}"
    __farr_l_len="${__farr_len}"
    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_len="${__farr_len}"

    [ ${__farr_l_len} -ne ${__farr_r_len} ] && return 1

    __farr_l_idx=1
    while [ ${__farr_l_idx} -le ${__farr_l_len} ]; do
        __farr_r_idx=1
        eval __farr_l_key=\"\$\{${__farr_l_keyname}_${__farr_l_idx}\}\"
        # Find within the right alist
        __farr_r_idx=1
        while [ ${__farr_r_idx} -le ${__farr_r_len} ]; do
            eval __farr_r_key=\"\$\{${__farr_r_keyname}_${__farr_r_idx}\}\"
            [ "${__farr_l_key}" = "${__farr_r_key}" ] && break
            __farr_r_idx=$((__farr_r_idx + 1))
        done
        # The index is above the right length if not found
        [ ${__farr_r_idx} -gt ${__farr_r_len} ] && return 1
        # Also compare the values
        eval __farr_l_value=\"\$\{${__farr_l_valname}_${__farr_l_idx}\}\"
        eval __farr_r_value=\"\$\{${__farr_r_valname}_${__farr_r_idx}\}\"
        [ "${__farr_l_value}" != "${__farr_r_value}" ] && return 1
        __farr_l_idx=$((__farr_l_idx + 1))
    done
    return 0
}


#:
#: Test whether two alists are equal respecting the (insertion) order.
#:
#: Two alists compare equal if and only if they have the same (key, value)
#: pairs **with** regard of ordering. Comparison is done using the shell's
#: builtin ``=`` operator for both keys and values.
#:
#: Args:
#:   $1 (str): The name of the first alist
#:   $2 (str): The name of the second alist
#:
#: Returns:
#:   int: 0 if both input alists are equal, 1 otherwise
#:
falist_are_equal_with_order() {
    local __farr_l_name __farr_r_name

    local __farr_l_token __farr_l_objname __farr_l_keyname __farr_l_valname __farr_l_len
    local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len

    local __farr_name __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx
    local __farr_l_key __farr_l_value
    local __farr_r_key __farr_r_value

    [ $# -ne 2 ] && _farr_fatal "missing alist parameter"

    _farr_alist_get_meta "$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_objname="${__farr_objname}"
    __farr_l_keyname="${__farr_keyname}"
    __farr_l_valname="${__farr_valname}"
    __farr_l_len="${__farr_len}"
    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_len="${__farr_len}"

    [ ${__farr_l_len} -ne ${__farr_r_len} ] && return 1

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_l_len} ]; do
        eval __farr_l_key=\"\$\{${__farr_l_keyname}_${__farr_idx}\}\"
        eval __farr_r_key=\"\$\{${__farr_r_keyname}_${__farr_idx}\}\"
        [ "${__farr_l_key}" != "${__farr_r_key}" ] && return 1
        # Also compare the values
        eval __farr_l_value=\"\$\{${__farr_l_valname}_${__farr_idx}\}\"
        eval __farr_r_value=\"\$\{${__farr_r_valname}_${__farr_idx}\}\"
        [ "${__farr_l_value}" != "${__farr_r_value}" ] && return 1
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Get all keys from the alist and put it into an array.
#:
#: Args:
#:   $1 (str): The name of the target array where the keys are appended to.
#:   $2 (str): The name of the alist from where to get the keys.
#:
falist_keys() {
    local __farr_l_result __farr_r_name

    local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len
    local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len

    local __farr_name __farr_token __farr_gvrname __farr_objname
    local __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_key

    # Try to get the array metadata here to provide an early error message
    [ $# -lt 1 ] && _ferr_fatal "missing target array"
    _farr_array_get_meta "$1"
    __farr_l_result="$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"
    [ $# -lt 2 ] && _farr_fatal "missing alist"
    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_len="${__farr_len}"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_r_len} ]; do
        eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}+SET\}\"
        if [ -n "${__farr_key}" ]; then
            eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}\}\"
            farray_append "${__farr_l_result}" "${__farr_key}"
        else
            _farr_fatal "alist \`${__farr_r_name}': missing key index"
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Get all values from the alist and put it into an array.
#:
#: Args:
#:   $1 (str): The name of the target array where values are appended to.
#:   $2 (str): The name of the alist from where to get the values.
#:
falist_values() {
    local __farr_l_result __farr_r_name

    local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len
    local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len

    local __farr_name __farr_token __farr_gvrname __farr_objname
    local __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_value

    # Try to get the array metadata here to provide an early error message
    [ $# -lt 1 ] && _ferr_fatal "missing target array"
    _farr_array_get_meta "$1"
    __farr_l_result="$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"
    [ $# -lt 2 ] && _farr_fatal "missing alist"
    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_len="${__farr_len}"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_r_len} ]; do
        eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}+SET\}\"
        if [ -n "${__farr_value}" ]; then
            eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}\}\"
            farray_append "${__farr_l_result}" "${__farr_value}"
        else
            _farr_fatal "alist \`${__farr_r_name}': missing value index"
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Get all items (key-value pairs) from the alist and put it into an array.
#:
#: Args:
#:   $1 (str): The name of the target array where the sequence of
#:             key-value pairs are to be appended to.
#:   $2 (str): The name of the alist from where to get the items.
#:
falist_items() {
    local __farr_l_result __farr_r_name

    local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len
    local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len

    local __farr_name __farr_token __farr_gvrname __farr_objname
    local __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_key __farr_value

    # Try to get the array metadata here to provide an early error message
    [ $# -lt 1 ] && _ferr_fatal "missing target array"
    _farr_array_get_meta "$1"
    __farr_l_result="$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"
    [ $# -lt 2 ] && _farr_fatal "missing alist"
    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_len="${__farr_len}"

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_r_len} ]; do
        eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}+SET\}\"
        if [ -n "${__farr_key}" ]; then
            eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}\}\"
            eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}+SET\}\"
            if [ -n "${__farr_value}" ]; then
                eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}\}\"
                farray_append "${__farr_l_result}" "${__farr_key}" "${__farr_value}"
            else
                _farr_fatal "alist \`${__farr_r_name}': missing value index"
            fi
        else
            _farr_fatal "alist \`${__farr_r_name}': missing key index"
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Call a function for every key-value pair in an alist starting in index order.
#:
#: The function to be called must accept at least three or four arguments:
#: - the alist name
#: - the element key at the current index
#: - the element value at the current index
#: - the current index
#: - all the extra arguments (`$3`, `$4`, ...) given as arguments are
#:   forwarded also
#:
#: The iteration stops if the called function returns a falsy value.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2 (str): The name of a function to be called with four arguments.
#:   $3... (optional): Extra arguments forwared to `$2` also
#:
#: Warning:
#:   If the number of elements changes while being in `falist_for_each` then
#:   the behaviour is undefined.
#:   The current implementation determines the length of the alist once
#:   at the start of execution.
#:
falist_for_each() {
    local __farr_name __farr_callback

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_feidx __farr_fekey __farr_feval __farr_rv
    local __farr_gm_name_or_value

    __farr_gm_name_or_value="${1-}"
    _farr_alist_get_meta "$@"
    __farr_callback="${2-}"
    [ -z "${__farr_callback}" ] && _farr_fatal "missing callback function name"

    shift 2

    __farr_feidx=1
    while [ ${__farr_feidx} -le ${__farr_len} ]; do
        eval __farr_fekey=\"\$\{${__farr_keyname}_${__farr_feidx}+SET\}\"
        if [ -n "${__farr_fekey}" ]; then
            eval __farr_fekey=\"\$\{${__farr_keyname}_${__farr_feidx}\}\"
            eval __farr_feval=\"\$\{${__farr_valname}_${__farr_feidx}+SET\}\"
            if [ -n "${__farr_feval}" ]; then
                eval __farr_feval=\"\$\{${__farr_valname}_${__farr_feidx}\}\"
                _farr_acquire_object "${__farr_feval}"
                eval "${__farr_callback} \"\${__farr_name:-\"\${__farr_gm_name_or_value}\"}\" \"\${__farr_fekey}\" \"\${__farr_feval}\" \"\${__farr_feidx}\" \"\$@\""
                __farr_rv=$?
                _farr_release_object "${__farr_feval}"
                [ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
            else
                _farr_fatal "alist \`${__farr_name:-"${__farr_gm_name_or_value}"}': missing value index"
            fi
        else
            _farr_fatal "alist \`${__farr_name:-"${__farr_gm_name_or_value}"}': missing key index"
        fi
        __farr_feidx=$((__farr_feidx + 1))
    done
    return 0
}


#:
#: Print the contents of an alist to stderr.
#:
#: Args:
#:   $1 (str): The name of an alist. The array may exist or not.
#:
#: Returns:
#:   0
#:
falist_debug() {
    _farr_alist_debug '' "$@"
}


#:
#: Internal implementation of `falist_debug`.
#:
#: Args:
#:   $1 (str): The indent
#:   $2 (str): The name or the complete prefixed token of an alist.
#:
#: Returns:
#:   0
#:
_farr_alist_debug() {
    local __farr_debug_indent __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_el_key __farr_el_val

    __farr_debug_indent="${1}"
    shift
    if ! _farr_alist_tryget_meta "$@"; then
        printf "%sDEBUG: no (meta-)data for falist \`%s'\\n" "${__farr_debug_indent}" "${1-}" 1>&2
        return 0
    fi

    if [ -n "${__farr_name}" ]; then
        printf "%sDEBUG: alist \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_name}" "${__farr_len}" 1>&2
    else
        printf "%sDEBUG: alist with token \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_token}" "${__farr_len}" 1>&2
    fi
    if [ ${__farr_len} -gt 0 ]; then
        printf '%sDEBUG:   the items:\n' "${__farr_debug_indent}" 1>&2
    fi
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval __farr_el_key=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\"
        if [ -z "${__farr_el_key}" ]; then
            printf "%sDEBqUG: key unexpectedly unset (index %s)\\n" "${__farr_debug_indent}" "${__farr_idx}" 1>&2
        fi
        eval __farr_el_val=\"\$\{${__farr_valname}_${__farr_idx}+SET\}\"
        if [ -z "${__farr_el_val}" ]; then
            printf "%s DEBUG: value unexpectedly unset (index %s)\\n" "${__farr_debug_indent}" "${__farr_idx}" 1>&2
        fi
        if [ \( -n "${__farr_el_key}" \) -a \( -n "${__farr_el_val}" \) ]; then
            eval __farr_el_key=\"\$\{${__farr_keyname}_${__farr_idx}\}\"
            eval __farr_el_val=\"\$\{${__farr_valname}_${__farr_idx}\}\"
            case "${__farr_el_val}" in
                "${_farr_array_token_prefix}"*)
                    printf "%sDEBUG:     \`%s' -> >>>\\n" "${__farr_debug_indent}" "${__farr_el_key}" 1>&2
                    _farr_array_debug "${__farr_debug_indent}    " "${__farr_el_val}"
                    ;;
                "${_farr_alist_token_prefix}"*)
                    printf "%sDEBUG:     \`%s' -> >>>\\n" "${__farr_debug_indent}" "${__farr_el_key}" 1>&2
                    _farr_alist_debug "${__farr_debug_indent}    " "${__farr_el_val}"
                    ;;
                *)
                    printf "%sDEBUG:     \`%s' -> \`%s'\\n" "${__farr_debug_indent}" "${__farr_el_key}" "${__farr_el_val}" 1>&2
                    ;;
            esac
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Acquire any object.
#:
#: If an object represents an array or alist its reference count will be
#: increased.
#:
#: Args:
#:   $1: The object's value
#:
#: Returns:
#:   int: 0 if the incrementation went properly, 1 otherwise
#:
_farr_acquire_object() {

    local __farr_tmp_refcount __farr_tmp_token

    case "$1" in
        '')
            return 0
            ;;
        "${_farr_array_token_prefix}"*)
            __farr_tmp_token="${1#"${_farr_array_token_prefix}"}"
            eval __farr_tmp_refcount=\$\{${_farr_array_prefix}${__farr_tmp_token}_C:+SET\}
            [ -z "${__farr_tmp_refcount}" ] && return 1
            eval __farr_tmp_refcount=\$\{${_farr_array_prefix}${__farr_tmp_token}_C\}
            __farr_tmp_refcount=$((__farr_tmp_refcount + 1))
            eval ${_farr_array_prefix}${__farr_tmp_token}_C=\$\{__farr_tmp_refcount\}
            return 0
            ;;
        "${_farr_alist_token_prefix}"*)
            __farr_tmp_token="${1#"${_farr_alist_token_prefix}"}"
            eval __farr_tmp_refcount=\$\{${_farr_alist_prefix}${__farr_tmp_token}_C:+SET\}
            [ -z "${__farr_tmp_refcount}" ] && return 1
            eval __farr_tmp_refcount=\$\{${_farr_alist_prefix}${__farr_tmp_token}_C\}
            __farr_tmp_refcount=$((__farr_tmp_refcount + 1))
            eval ${_farr_alist_prefix}${__farr_tmp_token}_C=\$\{__farr_tmp_refcount\}
            return 0
            ;;
        *)
            return 0
            ;;
    esac
}


#:
#: Release any object.
#:
#: If an object represents an array or alist its reference count will be
#: decreased properly.
#:
#: Args:
#:   $1: The object's value
#:
#: Returns:
#:   int: 0 if the destruction went properly without errors, 1 otherwise
#:
_farr_release_object() {

    case "$1" in
        '')
            return 0
            ;;
        "${_farr_array_token_prefix}"*)
            farray_release "$1"
            # let the return value pass through
            ;;
        "${_farr_alist_token_prefix}"*)
            falist_release "$1"
            # let the return value pass through
            ;;
        *)
            return 0
            ;;
    esac
}