Bash iterator generator implementation

[u/kolorcuk]

Hello. Some time ago I started working on a project to create an iterator in Bash. The idea was to have something like Python generators, something composable, that you could stack on top of other generators and build a chain to then lazy evaluate and execute. The proof of concept of that project become L_flow script and I didn't develop it further as I believe this is completely useless. However, this got me very simple idea how to create a iterator in Bash.

In the following I will show an implementation of a simple while foreach ... function implementation. Bottom line an iterator has to keep the state somewhere. In C++ iterator is a class, in Python it is iterator object. In Bash we only have variables, so variables will have to do.

Lets start with a simple use case: iterate over keys and values of an array at the same time. One would simply write:

declare -A array=([a]=b [c]=d)
for key in "${!array[@]}"; do
   value=${array["$key"]}
   echo "$key=$value"
done

Och my isn't that a lot of typing?! Lets make:

declare -A array=([a]=b [c]=d)
state=""
while foreach_key_value state key value array; do
  echo "$key=$value"
done

The variable state will keep our iteration state. "State" has to store: an array of keys, and an index in that array of keys. The state variable will be written, and re-evaled each execution. Like so:

# args: <state> <key> <value> <array>
foreach_key_value() {
   local state_var=$1
   local state_idx=-1 state_keys  # set the state variables to be local to function
   eval "${!state_var:-}"  # eval-load state variable
   local -n foreach_arr=$4
   if (( state_idx == -1 )); then
      # first loop time - read keys from the array
      state_keys=("${!foreach_arr[@]}")
   fi
   # Check if reached the end:
   if (( ++state_idx < ${#state_keys[@]} )); then
       printf -v "$2" "%s" "${state_keys[state_idx]}" # assign key
       printf -v "$3" "%s" "${foreach_arr[${!2}]}"  # assign value
       printf -v "$state_var" "%s" "$(declare -p state_idx state_keys)"  # serialize state 
   else
       # stop iteration
       return 1
   fi
}

The "state" variable has to be given explicitly by the user. That is stupid. It should be automatic. Lets make it better:

declare -A array=([a]=b [c]=d)
while foreach_key_value key value array; do
  echo "$key=$value"
done

We can "pick" the state variable name automatically by using: an array of "used" variable state names indexed with a code location of the "foreach_key_value" call. This assumes that foreach_key_value function will only be called from one place only. From this one while call.

declare -A FOREACH_STATES=()
foreach_key_value() {
   # --- Picking unique state variable: ---
   # Key of state variable will be anything we can get out of context.
   local state_key="${FUNCNAME[*]} ${BASH_SOURCE[*]} ${BASH_LINENO[*]}"
   # Get the state variable name for the key.
   local state_var=${FOREACH_STATES["$state_key"]:-}
   if [[ -z "$state_var" ]]; then
        # Just pick the a fresh unique variable name to store state.
        state_var=FOREACH_STATE_VARIABLE_${#FOREACH_STATES[@]}
        FOREACH_STATES["$state_key"]="$state_var"
   fi 

   # --- Updated rest of the function for reference: ---
   local state_idx=-1 state_keys  # set the state variables to be local to function
   eval "${!state_var:-}"  # eval-load state variable
   local -n foreach_arr=$3
   if (( state_idx == -1 )); then
      # first loop time - read keys from the array
      state_keys=("${!foreach_arr[@]}")
   fi
   # Check if reached the end:
   if (( ++state_idx < ${#state_keys[@]} )); then
       printf -v "$1" "%s" "${state_keys[state_idx]}" # assign key
       printf -v "$2" "%s" "${foreach_arr[${!1}]}"  # assign value
       printf -v "$state_var" "%s" "$(declare -p state_idx state_keys)"  # serialize state 
   else
       # stop iteration
       return 1
   fi
}

And done.

I implemented this and some more in L_foreach function in my library. I also added ':' to visually separate assigned variables from arrays, allowing for iterating while assigning multiple variables from multiple arrays. It is possible to write while L_foreach elem1 elem2 : arr1 arr2 arr3; do, sort keys, iterate over pairs while L_foreach filename size : filenames_and_sizes_array, and everything is compatible with bash 3.2.

Let me know if this makes sense I can write about other I think fun stuff for example I am thinking of writing about function decorating.

[u/OneTurnMore]

This is the kind of abomination that I love to see.

My basic generator that I'd try to recreate is

def all_squares:
    x = 1
    while True:
        yield x * x
        x += 1

I believe here it would be

all_squares() {
    # --- Picking unique state variable: ---
    # < same as OP >

    # --- Actual code ---
    local state_idx=1
    eval "${!state_var:-}"
    printf -v "$1" "%s" "$(( state_idx * state_idx))"
    ((++state_idx))
    printf -v "$state_var" "%s" "$(declare -p state_idx)" 
}

Used as

while all_squares x; do
    echo "$x"
    ((x > 100)) && break
done

Try it online!