Recursively replacement on a variable

Question

Given this associative array:

declare -A variables=(
   [prefix]='/usr'
   [exec_prefix]='@prefix@'
   [libdir]='@exec_prefix@/lib'
)

I would like to replace any occurrence of the pattern @([^@/]+)@ (e.g. @prefix@, with prefix being the capture) with the value that's associated to the capture (e.g. /usr for prefix) in all its values, such that the substitution be performed recursively until there are no more occurrences. The steps for each key in the array would be:

1. Retrieve the value associated to it and perform (2) on it.
2. Check if there is a match of the pattern in the given string.
   • If there isn't any, return the given string.
   • If there's a match:
     1. Perform (1) on the capture and keep the result.
     2. Replace the match by the result.
     3. Perform (2) on the resulting string.
3. Drop the previous value associated to the key and associate to it the last string returned.

Whatever the approach, the desired result is:

prefix=/usr
exec_prefix=/usr
libdir=/usr/lib

---

Additional requirements:

• Self references (e.g. prefix=@prefix@) will not occur.
• If possible, use only Bash builtins.

---

Example in Lua:

local variables={
    prefix="/usr",
    exec_prefix="@prefix@",
    includedir="@prefix@/include",
    libdir="@exec_prefix@/lib",
    random_one_to_show_off_fancy_recursion="@prefix@@libdir@@includedir@"
}

function replacer( variable )
    return compute_value(variables[variable])
end

function compute_value( s )
    return s:gsub('@([^@/]+)@',replacer)
end

local variable, value = next(variables)
while variable do
    variables[variable] = compute_value(value)

    print( string.format('%-39s\t%s', variable, variables[variable]) )

    variable, value = next(variables,variable)
end

Answer 1

The (pure Bash) code below assumes that '@@' is left unchanged and '@xyz@' is left unchanged when 'xyz' is not a variable. It also attempts to detect recursive variable definitions, including indirect ones (e.g. [a]=@b@ [b]=@c@ [c]=@a@).

# Regular expression for a string with an embedded expansion
# For a string of the form 'u@v@w', where 'u' and 'v' do not contain '@':
#   u -> BASH_REMATCH[1]
#   v -> BASH_REMATCH[2]
#   w -> BASH_REMATCH[3]
readonly EXPANSION_RX='^([^@]*)@([^@]*)@(.*)$'

# First pass tries to expand all variables
vars_to_expand=( "${!variables[@]}" )

while (( ${#vars_to_expand[*]} > 0 )) ; do
    old_vars_to_expand=( "${vars_to_expand[@]}" )
    vars_to_expand=()
    for var in "${old_vars_to_expand[@]}" ; do
        val=${variables[$var]}
        unexpanded=$val
        newval=

        while [[ $unexpanded =~ $EXPANSION_RX ]] ; do
            newval+=${BASH_REMATCH[1]}
            v=${BASH_REMATCH[2]}
            unexpanded=${BASH_REMATCH[3]}

            if [[ $v == "$var" ]] ; then
                echo "ERROR - Expanding '@$var@' in '$var'" >&2
                exit 1
            elif [[ -z $v ]] ; then
                # The empty string can not be a hash key (Duh!)
                newval+=@$v@
            else
                newval+=${variables[$v]-@$v@}
            fi
        done

        newval+=$unexpanded

        if [[ $newval != "$val" ]] ; then
            # An expansion has occurred.

            # Update the variable value
            variables[$var]=$newval

            # Further expansions may be possible, so add the variable to the
            # list of variables to be expanded again
            vars_to_expand+=( "$var" )
        fi
    done
done