#!/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.
#: - 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 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.
#:
#: 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_`` or ``falist_``.
#:


_farr_array_prefix=_farr_A_
_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
}


#:
#: 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. $'...').
#:
#:
#: 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
}


#:
#: 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 (token \`${__farr_token}')"

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

    __farr_gvrname=${_farr_array_prefix}${__farr_token}
    shift

    # 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 associate the token with the array name
    eval "${__farr_name}"="${__farr_token}"

    if [ $# -gt 0 ]; then
	farray_append "${__farr_name}" "$@"
    fi
}


#:
#: Internal helper to get all the metadata for an array.
#:
#: Args:
#:   $1 (str): The name of the array
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array.
#:   __farr_token (str): The token that is the value of the name.
#:   __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() {
    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing farray name"
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    [ -z "${__farr_token}" ] && _farr_fatal "farray \`${__farr_name}' does not exist: token empty"
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\$\{${__farr_gvrname}__:+SET\}
    [ -z "${__farr_len}" ] && _farr_fatal "farray \`${__farr_name}' does not exist: no storage for token \`${__farr_token}'"
#    eval __farr_len="\$((\${${__farr_gvrname}__} + 0))"
    eval __farr_len="\$((${__farr_gvrname}__ + 0))"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an array.
#:
#: Args:
#:   $1 (str): The name of the array
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array.
#:   __farr_token (str): The token that is the value of the name.
#:   __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.
#:
#: Exit:
#:   Iff the array name is not given
#:
_farr_array_tryget_meta() {
    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing farray name"
    __farr_token=''
    __farr_gvrname=''
    __farr_len=''
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    if [ -z "${__farr_token}" ]; then
        _farr_err "farray \`${__farr_name}' does not exist: token empty"
        return 1;
    fi
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\$\{${__farr_gvrname}__:+SET\}
    if [ -z "${__farr_len}" ]; then
        _farr_err "farray \`${__farr_name}' does not exist: no storage for token \`${__farr_token}'"
        return 1
    fi
    # eval __farr_len="\$((\${${__farr_gvrname}__} + 0))"
    eval __farr_len="\$((${__farr_gvrname}__ + 0))"
    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
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array.
#:   __farr_token (str): The token that is the value of the name.
#:   __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() {
    __farr_token=''
    __farr_gvrname=''
    __farr_len=''
    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && return 1
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    [ -z "${__farr_token}" ]  && return 1
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"
    eval __farr_len=\$\{${__farr_gvrname}__:+SET\}
    [ -z "${__farr_len}" ] && return 1
    # eval __farr_len="\$((\${${__farr_gvrname}__} + 0))"
    eval __farr_len="\$((${__farr_gvrname}__ + 0))"
    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.
        #
        eval ${__farr_gvrname}_${__farr_len_1}="$(_farr_quote_for_eval "${__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 appended.
#:
#: 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

    _farr_array_get_meta "$@"
    __farr_index="${2-}"
    [ -z "${__farr_index}" ] && _farr_fatal "no valid index for set given"
    # make it to a number
    __farr_index=$((__farr_index + 0))
    [ ${__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
        # replace a value at an existing index
        eval ${__farr_gvrname}_${__farr_index}="$(_farr_quote_for_eval "${__farr_value}")"
    else
        __farr_len_1=$((__farr_len + 1))
        if [ ${__farr_index} -eq ${__farr_len_1} ]; then
            # append value
            eval ${__farr_gvrname}_${__farr_len_1}="$(_farr_quote_for_eval "${__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

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_array_get_meta "$@"
    __farr_index="${2-}"
    [ -z "${__farr_index}" ] && _farr_fatal "no valid index given"
    # make it to a number
    __farr_index=$((__farr_index + 0))

    # 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_varname}"=\"\$\{${__farr_gvrname}_${__farr_index}\}\"
}


#:
#: 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

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

    _farr_array_get_meta "$@"
    __farr_index="${2-}"
    [ -z "${__farr_index}" ] && _farr_fatal "no valid index given"
    # make it to a number
    __farr_index=$((__farr_index + 0))

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

    eval "${__farr_varname}"=\"\$\{${__farr_gvrname}_${__farr_index}\}\"
    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

    _farr_array_get_meta "$@"
    __farr_index="${2-}"
    [ -z "${__farr_index}" ] && _farr_fatal "no valid index given"
    # make it to a number
    __farr_index=$((__farr_index + 0))

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

    __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.
#:                   -  `null` is len+1.
#:                   -  0, -1, -2, ...  -(len-1) are len + given index.
#:   $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.
#:
farray_splice() {
    local __farr_del_name __farr_del_token __farr_del_gvrname __farr_del_len
    local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len
    local __farr_index __farr_length
    local __farr_r_name __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_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

    if [ -z "${__farr_index}" ]; then
        __farr_index=$((__farr_l_len + 1))
    else
        if [ "${__farr_index}" -le 0 ]; then
            __farr_index=$((__farr_l_len + __farr_index))
        fi
        # NOTE: index value 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"
    fi
    # also check the given length
    if [ -z "${__farr_length}" ]; then
        __farr_length="$((__farr_l_len - __farr_index + 1))"
    else
        [ \( "${__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
            if [ -n "${__farr_del_name}" ]; then
                eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"
                farray_append "${__farr_del_name}" "${__farr_v}"
            fi
            eval __farr_v=\"\$\{${__farr_r_gvrname}_$((__farr_off + 1))\}\"
            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
            if [ -n "${__farr_del_name}" ]; then
                eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"
                farray_append "${__farr_del_name}" "${__farr_v}"
            fi
            eval __farr_v=\"\$\{${__farr_r_gvrname}_$((__farr_off + 1))\}\"
            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
            if [ -n "${__farr_del_name}" ]; then
                eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"
                farray_append "${__farr_del_name}" "${__farr_v}"
            fi
            eval unset ${__farr_l_gvrname}_$((__farr_index + __farr_off))
            __farr_off=$((__farr_off + 1))
        done
        # Move the rest
        __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
            if [ -n "${__farr_del_name}" ]; then
                eval __farr_v=\"\$\{${__farr_l_gvrname}_$((__farr_index + __farr_off))\}\"
                farray_append "${__farr_del_name}" "${__farr_v}"
            fi
            eval __farr_v=\"\$\{${__farr_r_gvrname}_$((__farr_off + 1))\}\"
            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
        __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))\}\"
            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
}


#:
#: 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_array_get_meta "$@"

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

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


#:
#: 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_destroy() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len
    local __farr_idx

    if ! _farr_array_tryget_meta "$@" ; then
        return 1
    fi
    # Remove "storage"
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
	eval unset ${__farr_gvrname}_${__farr_idx}
	__farr_idx=$((__farr_idx + 1))
    done

    # Remove length itselt
    eval unset ${__farr_gvrname}__
    # Clean out the array name from the token
    eval ${__farr_name}=\"\"
}


#:
#: 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, optional): The start index to search for (inclusive)
#:   $5 (int, optional):  The index to stop (inclusive)
#:
#: Output (stdout):
#:   The index number where the value is found -- if any
#:
#: 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_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=$((${4-1} + 0))
    [ ${__farr_start} -lt 1 ] && _farr_fatal "start index must be >= 1"
    __farr_end=$((${5-${__farr_len}} + 0))
    [ ${__farr_end} -lt 1 ] && _farr_fatal "end index must be >= 1"

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


#:
#: 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 three arguments:
#: - the array name
#: - the current index
#: - the element value at the current index
#:
#: 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.
#:
#: 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

    _farr_array_get_meta "$@"

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

    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
	eval "${__farr_callback} ${__farr_name} ${__farr_idx} \"\${${__farr_gvrname}_${__farr_idx}}\""
	__farr_rv=$?
	[ ${__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

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

    __farr_idx=${__farr_len}
    while [ ${__farr_idx} -gt 0 ]; do
	eval "${__farr_callback} ${__farr_name} ${__farr_idx} \"\${${__farr_gvrname}_${__farr_idx}}\""
	__farr_rv=$?
	[ ${__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:
#:   0
#:
farray_debug() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len

    if ! _farr_array_tryget_meta "$@"; then
        echo "DEBUG: no (meta-)data for farray \`${1-}'" 1>&2
        return 0
    fi

    echo "DEBUG: array \`${__farr_name}' has length ${__farr_len}" 1>&2
    if [ ${__farr_len} -gt 0 ]; then
        echo "DEBUG:   its contents:" 1>&2
        farray_for_each "${__farr_name}" _farr_debug_print_value
    fi
    return 0
}


#:
#: Debug output helper for `farray_debug`.
#:
_farr_debug_print_value() {
    printf "DEBUG:     %s: \`%s'\\n" "$2" "$3" 1>&2
    return 0
}


#:
#: Create a new alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:             Must conform to shell variable naming conventions.
#:
#: 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 (token \`${__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 associate the token with the array name
    eval "${__farr_name}"="${__farr_token}"
}


#:
#: Internal helper to get all the metadata for an alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:
#: Output (Globals):
#:   __farr_name (str):
#:   __farr_token (str):
#:   __farr_objname (str):
#:   __farr_keyname (str):
#:   __farr_valname (str):
#:   __farr_len (int): The length of the array
#:
#: Exit:
#:   Iff the array does not exist in some fashion (token and/or storage).
#:
_farr_alist_get_meta() {
    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing farray name"
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    [ -z "${__farr_token}" ] && _farr_fatal "falist \`${__farr_name}' does not exist: token empty"

    __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}' does not exist: no object for token \`${__farr_token}'"
    # eval __farr_len="\$((\${${__farr_objname}__} + 0))"
    eval __farr_len="\$((${__farr_objname}__ + 0))"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an alist.
#:
#: Args:
#:   $1 (str): The name of the alist
#:
#: Output (Globals):
#:   __farr_name (str): The name of the alist.
#:   __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.
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing.
#:
#: Exit:
#:   Iff the array name is not given
#:
_farr_alist_tryget_meta() {
    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing farray name"
    __farr_token=""
    __farr_objname=""
    __farr_keyname=""
    __farr_valname=""
    __farr_len=""
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    if [ -z "${__farr_token}" ]; then
        _farr_err "falist \`${__farr_name}' does not exist: token empty"
        return 1;
    fi

    __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}' does not exist: no object for token \`${__farr_token}'"
        return 1
    fi
    # eval __farr_len="\$((\${${__farr_objname}__} + 0))"
    eval __farr_len="\$((${__farr_objname}__ + 0))"
    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_alist_get_meta "$@"

    # Remove "storage"
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        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
}


#:
#: Destroy and unset an alist
#:
#: 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_destroy() {
    local __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx

    if ! _farr_alist_tryget_meta "$@" ; then
        return 1
    fi

    # Remove "storage"
    __farr_idx=1
    while [ ${__farr_idx} -le ${__farr_len} ]; do
        eval unset ${__farr_valname}_${__farr_idx}
        eval unset ${__farr_keyname}_${__farr_idx}
        __farr_idx=$((__farr_idx + 1))
    done

    # Remove object (length) itselt
    eval unset ${__farr_objname}__
    # Clean out the alist name from the token
    eval ${__farr_name}=\"\"
    return 0
}


#:
#: Map a key to a value.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2: The key.
#:   $3: The value.
#:
#: 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

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

    __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_valname}_${__farr_idx}="$(_farr_quote_for_eval "${__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 already the new correct length
    #
    __farr_len=${__farr_idx}
    #   ... the key/value pairs to storage
    eval ${__farr_keyname}_${__farr_len}="$(_farr_quote_for_eval "${__farr_key}")"
    eval ${__farr_valname}_${__farr_len}="$(_farr_quote_for_eval "${__farr_value}")"
    #   ... the new length
    eval ${__farr_objname}__=${__farr_len}
    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.
#:
#: 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

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_getkey

    __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=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_varname}"=\"\$\{${__farr_valname}_${__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}': 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.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given key is not found.
#:
falist_tryget() {
    local __farr_varname __farr_name __farr_key

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_getkey

    __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=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_varname}"=\"\$\{${__farr_valname}_${__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 "$@"
    [ $# -lt 2 ] && _farr_fatal "missing index"
    __farr_index=$(($2 + 0))

    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_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 "$@"
    [ $# -lt 2 ] && _farr_fatal "missing index"
    __farr_index=$(($2 + 0))

    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_varname}"=\"\$\{${__farr_valname}_${__farr_index}\}\"
            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 "$@"
    [ $# -lt 2 ] && _farr_fatal "missing index"
    __farr_index=$(($2 + 0))

    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_value_varname}"=\"\$\{${__farr_valname}_${__farr_index}\}\"
                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
}


#:
#: 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
#:
#: 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_idx

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

    __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}
                _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
}


#:
#: Call a function for every key-value pair in an alist starting in index order.
#:
#: The function to be called must accept three or four arguments:
#: - the alist name
#: - the element key at the current index
#: - the element value at the current index
#: - the current index
#:
#: 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.
#:
#: 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

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

    __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}\}\"
                eval "${__farr_callback} ${__farr_name} \"\${__farr_fekey}\" \"\${__farr_feval}\" ${__farr_feidx}"
                __farr_rv=$?
                [ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
            else
                _farr_fatal "alist \`${__farr_name}': missing value index"
            fi
        else
            _farr_fatal "alist \`${__farr_name}': missing value 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() {
    local __farr_name

    local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len
    local __farr_idx __farr_el_key __farr_el_val

    if ! _farr_alist_tryget_meta "$@"; then
        echo "DEBUG: no (meta-)data for falist \`${1-}'" 1>&2
        return 0
    fi

    echo "DEBUG: alist \`${__farr_name}' has length ${__farr_len}" 1>&2
    __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
            echo "DEBUG: key unexpectedly unset (index ${__farr_idx})" 1>&2
        fi
        eval __farr_el_val=\"\$\{${__farr_valname}_${__farr_idx}+SET\}\"
        if [ -z "${__farr_el_val}" ]; then
            echo "DEBUG: value unexpectedly unset (index ${__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}\}\"
            printf "DEBUG:     \`%s' -> \`%s'\\n" "${__farr_el_key}" "${__farr_el_val}" 1>&2
        fi
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Some basic tests.
#:
_farray_test() {
    local CMD
    local _i _var _k _v

    set -
    set -eu

    farray_create TEST 0 1 2 '3  4   5' $'" 678" \\\'90 '    # '
    farray_debug TEST
    farray_destroy TEST
    farray_destroy TEST || { echo "(this is ok.)"; true; }

    farray_create TEST 1 2 3 '4  5   6' $'" 123" \\\'45 '    # '
    farray_debug TEST
    if farray_contains TEST 7; then
        echo "CONTAINS (ERROR)"
    fi
    if ! farray_contains TEST '4  5   6'; then
        echo "NO CONTAINS (ERROR)"
    fi
    if farray_contains TEST '4 5 6'; then
        echo "CONTAINS (ERROR)"
    fi
    if ! farray_contains TEST 1; then
        echo "NOT CONTAINS (ERROR)"
    fi
    if ! farray_contains TEST 2; then
        echo "NOT CONTAINS (ERROR)"
    fi

    if ! farray_contains TEST $'" 123" \\\'45 ' ; then      # '
       echo "NOT CONTAINS (ERROR)"
    fi
    if ! farray_contains TEST 'NO VAL 1' $'" 123" \\\'45 ' 'NO VAL 3'; then      # '
       echo "NOT CONTAINS (ERROR)"
    fi
    if farray_contains TEST 'NO VAL 1' 'NO VAL 3'; then
       echo "CONTAINS (ERROR)"
    fi
    if ! farray_find _i TEST $'" 123" \\\'45 ' ; then       # '
       echo "NOT CONTAINS (ERROR)"
    fi

    farray_get _var TEST 1
    printf "VAR 1: %s\n" "$_var"
    farray_get _var TEST 5
    printf "VAR 2: %s\n" "$_var"
    [ "$_var" = $'" 123" \\\'45 ' ] || echo "COMPARE ERROR"   # '

    farray_destroy TEST

    farray_create TEST 11 22 33 '44  55   66' $'" 112233" \\\'4455 '    # '
    farray_debug TEST

    farray_get _i TEST 1
    echo $_i
    farray_get _i TEST 2
    farray_get _var TEST 4
    [ "$_var" = '44  55   66' ] || echo "COMPARE ERROR"  # '
    farray_del TEST 4
    farray_get _i TEST 4
    echo $_i
    farray_tryget _i TEST 1 || echo "NOT FOUND (ERROR)"
    farray_tryget _i TEST 4 || echo "NOT FOUND (ERROR)"
    ! farray_tryget _i TEST 5 || echo "FOUND (ERROR)"
    farray_get _var TEST 4
    [ "$_var" = $'" 112233" \\\'4455 ' ] || echo "COMPARE ERROR"  # '

    farray_clear TEST
    farray_length _var TEST
    [ ${_var} -eq 0 ] || echo "LENGTH != 0 (ERROR)"

    if ! farray_destroy TEST; then
        echo "DESTROY FAILED (ERROR)"
    fi
    if farray_destroy TEST; then
        echo "DESTROY succeeded (ERROR)"
    else
        echo "(this is ok)"
    fi
    farray_destroy TEST || true
    echo "(this is ok)"

    # shellcheck disable=SC1003
    farray_create CMD zfs list "-H" "-o" "name,canmount,mounted,mountpoint,origin" "zpool/ROOT/test- YYY" "'" '\' 'abc'\''d\tef'
    farray_join _var CMD
    echo "CMD: join with ' ': $_var"
    farray_join _var CMD ' --- '
    echo "CMD: join with ' --- ': $_var"
    farray_clear CMD
    farray_join _var CMD ' --- '
    echo "CMD: join with ' --- ': $_var   (empty: ok)"

    farray_destroy CMD
    # shellcheck disable=SC1003
    farray_create CMD zfs list "-H" "-o" "name,canmount,mounted,mountpoint,origin" "zpool/ROOT/test- YYY" "'" '\' 'abc'\''d\tef'
    farray_join_for_eval _var CMD
    echo "CMD-EVAL: $_var"
    farray_destroy CMD || true

    farray_create TEST
    farray_set TEST 1 "VAL-1"     # appends here
    farray_set TEST 2 "VAL-2"     # appends here
    farray_set TEST 1 "VAL-1 1"   # replaces at index 1
    farray_length _var TEST
    [ ${_var} -eq 2 ] || echo "LENGTH != 2 (ERROR)"
    farray_get _var TEST 1
    [ "${_var}" = "VAL-1 1" ] || echo "unexpected value (ERROR)"
    farray_get _var TEST 2
    [ "${_var}" = "VAL-2" ] || echo "unexpected value (ERROR)"
    farray_destroy TEST

    falist_create LIST
    falist_length _i LIST
    [ "$_i" -eq 0 ] || echo "alist length != 0 (ERROR)"
    falist_print_length LIST && echo
    falist_debug LIST
    falist_destroy LIST

    falist_create LIST
    falist_set LIST K1 V1
    falist_set LIST K2 V2
    falist_debug LIST
    falist_set LIST K2 "V2 2"
    falist_set LIST K3 $'" 111222333" \\\'444555 '    # '
    falist_debug LIST
    if ! falist_contains LIST K1; then
        echo "NOT CONTAINS (ERROR)"
    fi
    if falist_contains LIST K; then
        echo "CONTAINS (ERROR)"
    fi
    falist_debug LIST
    falist_get _var LIST K2
    [ "$_var" = "V2 2" ] || echo "alist element not found (ERROR)"
    if ! falist_tryget _var LIST K1; then
        echo "NOT FOUND (ERROR)"
    fi
    if falist_tryget _i LIST K; then
        echo "FOUND (ERROR)"
    fi
    falist_length _i LIST
    echo "LENGTH: $_i"
    printf "%s" "PRINT LENGTH: "
    falist_print_length LIST
    echo
    _var="$(falist_print_length NON_EXISTING_LIST)"
    if [ "${_var}" != "-1" ]; then
        echo "VALID LENGTH (ERROR)"
    fi

    # Iteration by indexing key and values separately
    echo "ITERATE (manual indexing):"
    _i=1
    while falist_tryget_key_at_index _k LIST ${_i}; do
        # cannot fail under "normal" circumstances
        falist_tryget_value_at_index _v LIST ${_i}
        printf "  KEY: \`%s', VAL: \`%s'\\n" "${_k}" "${_v}"
        _i=$((${_i} + 1))
    done

    # Iteration by indexing key and values separately
    echo "ITERATE (manual indexing over items):"
    _i=1
    while falist_tryget_item_at_index _k _v LIST ${_i}; do
        printf "  KEY: \`%s', VAL: \`%s'\\n" "${_k}" "${_v}"
        _i=$((${_i} + 1))
    done

    # Iteration with for each
    echo "ITERATE (for each):"
    falist_for_each LIST $'printf "EACH: %s key \\`%s\\\', value \\`%s\\\' at idx %d\\n"'   # `

    falist_clear LIST
    if ! falist_destroy LIST ; then
        echo "DESTROY FAILED (ERROR)"
    fi
    if falist_destroy LIST ; then
        echo "DESTROY SUCCEEDED (ERROR)"
    else
        echo "(this is ok)"
    fi

    # Deletion of keys
    falist_create LIST
    falist_set LIST 'key 1' 'value 1'
    falist_set LIST 'key 2' 'value 2'
    falist_set LIST 'key 3' 'value 3'
    falist_set LIST 'key 4' 'value 4'
    falist_set LIST 'key 5' 'value 5'
    falist_trydel LIST 'key 1' || echo "cannot del key 1"
    falist_trydel LIST 'key 5'  || echo "cannot del key 5"
    falist_trydel LIST 'key 3' || echo "cannot del key 3"
    [ "$(falist_print_length LIST)" -eq 2 ] || echo "length mismatch"
    falist_get _var LIST 'key 2'
    [ "$_var" = 'value 2' ] || echo "value mismatch"
    falist_get _var LIST 'key 4'
    [ "$_var" = 'value 4' ] || echo "value mismatch"
    falist_destroy LIST

    # set
    echo "============================================================"
    echo "OK."
    echo "============================================================"
}


# _farray_test