research/arrays-and-hashes.txt: New fileHEADmaster

1 files changed, 465 insertions, 0 deletions

diff --git a/research/arrays-and-hashes.txt b/research/arrays-and-hashes.txt
new file mode 100644
index 0000000..eac18cd
--- /dev/null
+++ b/research/arrays-and-hashes.txt
@@ -0,0 +1,465 @@
+Arrays
+======
+
+Arrays are simple lists of values.  Arrays are zero-indexed, but internally
+there is an offset that is affected by `shift` and `unshift` calls.
+
+Array keys are non-zero integers.
+
+An array has a length limited only by the highest non-zero integer in the
+shell's built-in arithmetic.  An array is grown by calls to `push` and `unshift`
+as well as by assigning values with out-of-bounds keys.  An array is shrunk by
+calls to `pop` and `shift` as well as by unsetting the 0th and last values.
+
+Array Expansion
+---------------
+
+Array expansion initializes an array.  The format for array expansion is as
+follows:
+
+	@(values)
+
+where *values* is zero or more *word*s.  A reference to the new array is
+substituted.
+
+eshtrans will translate array expansions into calls to `__a_new` (part of
+libeshtrans) with array references returned in registers allocated at compile
+time.
+
+For example:
+
+	cardinals=@("zero" "one" "two")
+
+compiles to:
+
+	__a_new __r0 "zero" "one" "two"
+	cardinals=${__r0}
+
+while:
+
+	cmd @("zero" "one" "two")
+
+compiles to:
+
+	__a_new __r0 "zero" "one" "two"
+	cmd ${__r0}
+
+and:
+
+	cardinals=@(@("zero" "cero") @("one" "uno") @("two" "dos"))
+
+compiles to:
+
+	__a_new __r0 "zero" "cero"
+	__a_new __r1 "one" "uno"
+	__a_new __r2 "two" "dos"
+	__a_new __r3 ${__r0} ${__r1} ${__r2}
+	cardinals=${__r3}
+
+Quoting the `@(` operator removes its special meaning.
+
+Array Value Assignment
+----------------------
+
+The format for array value assignment is as follows:
+
+	name[key]=word
+
+eshtrans will translate array value assignments into calls to `__a_set` (part of
+libeshtrans).
+
+For example:
+
+	cardinals[0]="zero"
+
+compiles to:
+
+	__a_set cardinals 0 "zero"
+
+Array Value Expansion
+---------------------
+
+The format for array value expansion is as follows:
+
+	${name[key]}
+
+eshtrans will translate array value expansions into calls to `__a_get` (part of
+libeshtrans).
+
+For example:
+
+	zero=${cardinals[0]}
+
+compiles to:
+
+	__a_get __r0 cardinals 0
+	zero=${__r0}
+
+`unset`
+-------
+
+`unset` is a reserved word and a function that unsets variables, functions,
+array values, and arrays.
+
+The format for unsetting an array value is as follows:
+
+	unset name[key]
+
+The format for unsetting an array is as follows:
+
+	unset name
+
+eshtrans will check the types of all of the operands of `unset` commands and
+translate them into calls to `unset` (the shell's built-in utility),
+`__a_unset`, or `__a_delete` as appropriate.
+
+For example:
+
+	unset cardinals[1] cardinals[2]
+
+compiles to:
+
+	__a_unset cardinals 1
+	__a_unset cardinals 2
+
+and:
+
+	unset cardinals
+
+compiles to:
+
+	__a_delete cardinals
+
+libeshtrans Functions
+---------------------
+
+	# __a_new(__r)
+	# Paramters:
+	#   * __r: Register in which to store array reference
+	__a_new()
+	{
+		__r=${1}
+		shift 1
+	
+		# Allocate a slot on the array heap.
+		__malloc __a
+		__a=__mr
+	
+		# Set values.
+		__k=0
+		for __v in "${@}"; do
+			eval "${__a}__${__k}=\${__v}"
+			__k=$((${__k} + 1))
+		done
+	
+		# Set length.
+		eval "${__a}_l=\${__k}"
+	
+		# Store the array reference in the specified return register.
+		eval "${__r}=\${__a}
+	}
+	
+	# __a_set(__a __k __v)
+	# Parameters:
+	#   * __a: Array
+	#   * __k: Key
+	#   * __v: Value
+	__a_set()
+	{
+		__a=${1}
+		__k=${2}
+		__v=${3}
+	
+		# Validate key.
+		case ${__k} in *[!0-9]*)
+			printf 'Error: Illegal array key: %s\n' "${__k}" 1>&2
+			exit 1
+		;; esac
+	
+		# Enlarge array if key is out-of-bounds.
+		eval "__l=\${${__a}_l}"
+		if [ ${__k} -ge ${__l} ]; then
+			eval "${__a}_l=\$((\${__k} - 1))"
+		fi
+	
+		# Set value.
+		eval "${__a}__${__k}=\${__v}"
+	}
+	
+	# __a_get(__r __a __k)
+	# Parameters:
+	#   * __r: Register in which to store value
+	#   * __a: Array
+	#   * __k: Key
+	__a_get()
+	{
+		__r=${1}
+		__a=${2}
+		__k=${3}
+	
+		# Validate key.
+		case ${__k} in *[!0-9]*)
+			printf 'Error: Illegal array key: %s\n' "${__k}" 1>&2
+			exit 1
+		;; esac
+	
+		# Offset key.
+		eval "__k=\$((\${__k} + \${${__a}__o}))"
+	
+		# Store the value in the specified return register.
+		# NB: If `set -u` is on, the shell will throw an error on undefined values
+		# or out-of-bound keys, as one would expect.
+		eval "${__r}=\${${__a}__${__k}}"
+	}
+	
+	# __a_unset(__a __k)
+	# Parameters:
+	#   * __a: Array
+	#   * __k: Key
+	__a_unset()
+	{
+		__a=${1}
+		__k=${2}
+	
+		# ...
+	}
+	
+	# __a_delete(__a)
+	# Parameters:
+	#   * __a: Array
+	__a_delete()
+	{
+		__a=${1}
+	
+		# ...
+	}
+
+libesh Functions
+----------------
+
+	# length(a)
+	# Parameters:
+	#   * a: Array
+	length(a)
+	{
+		l=
+	
+		eval "${&l}=\${${a}_l}"
+	
+		return "${l}"
+	}
+	
+	# push(a v)
+	# Parameters:
+	#   * a: Array
+	#   * v: Value
+	push(a v)
+	{
+		l=
+		k=
+	
+		# Get the current length.
+		eval "${&l}=\${${a}_l}"
+		# Offset the length to get the new key.
+		eval "${&k}=\$((${l} + \${${a}_o}))"
+		# Set the new value.
+		eval "${a}__${k}=\${${&v}}"
+		# Increment the length.
+		eval "${a}_l=\$((${l} + 1))"
+	}
+	
+	# pop(a)
+	# Parameters:
+	#   * a: Array
+	pop(a)
+	{
+		# ...
+	}
+	
+	# __shift(a)
+	# Parameters:
+	#   * a: Array
+	__shift(a)
+	{
+		# ...
+	}
+	
+	# unshift(a v)
+	# Parameters:
+	#   * a: Array
+	#   * v: Value
+	unshift(a v)
+	{
+		# ...
+	}
+	
+	# split(fs str)
+	# Parameters:
+	#   * fs: Field separator
+	#   * str: String to split
+	split(fs str)
+	{
+		# See split.sh
+	}
+	
+	# join(str a)
+	# Parameters:
+	#   * str: Separator
+	#   * a: Array to join
+	# str will be duplicated around unset values in the middle of the array.
+	join()
+	{
+		l=
+		joined=
+	
+		# Get the current length.
+		eval "${&l}=\${${a}_l}"
+	
+		# Join all the array values.
+		joined="$(eval "printf '%s' \"$(printf "\\\${${a}__%d}\${str}" \
+			$(awk -v end=${l} \
+			'BEGIN { for (i = 0; i < end; ++i) print(i); }'))\"")"
+	
+		return "${joined%${str}}"
+	}
+
+Hashes
+======
+
+Hashes are sets of key/value pairs.
+
+Hash keys may only consist of Latin letters, digits, and underscores.
+
+Each hash has a list of keys, which is returned by the `keys` function.
+
+Hash Expansion
+--------------
+
+Hash expansion initializes a hash.  The format for hash expansion is as follows:
+
+	%(values)
+
+where *values* is zero or more *word*s of the following format:
+
+	key=value
+
+A reference to the new hash is substituted.
+
+eshtrans will translate hash expansions into calls to `__h_new` (part of
+libeshtrans) with hash references returned in registers allocated at compile
+time.
+
+For example:
+
+	numerals=%(zero=0 one=1 two=2)
+
+compiles to:
+
+	__h_new __r0 zero 0 one 1 two 2
+	numerals=${__r0}
+
+while:
+
+	cmd %(zero=0 one=1 two=2)
+
+compiles to:
+
+	__h_new __r0 zero 0 one 1 two 2
+	cmd ${__r0}
+
+and:
+
+	numerals=%(\
+		zero=%(arabic=0 roman=N) \
+		one=%(arabic=1 roman=i) \
+		two=%(arabic=2 roman=ii) \
+	)
+
+compiles to:
+
+	__h_new __r0 arabic 0 roman N
+	__h_new __r1 arabic 1 roman i
+	__h_new __r2 arabic 2 roman ii
+	__h_new __r3 zero ${__r0} one ${__r1} two ${__r2}
+	numerals=${__r3}
+
+Quoting the `%(` operator removes its special meaning.
+
+Hash Value Assignment
+---------------------
+
+The format for hash value assignment is as follows:
+
+	name{key}=word
+
+eshtrans will translate hash value assignments into calls to `__h_set` (part of
+libeshtrans).
+
+For example:
+
+	numerals{zero}=0
+
+compiles to:
+
+	__h_set numerals zero 0
+
+Hash Value Expansion
+--------------------
+
+The format for hash value expansion is as follows:
+
+	${name{key}}
+
+eshtrans will translate hash value expansions into calls to `__h_get` (part of
+libeshtrans).
+
+For example:
+
+	zero=${numerals{zero}}
+
+compiles to:
+
+	__h_get __r0 numerals zero
+	zero=${__r0}
+
+`ENV` Hash
+----------
+
+Environment variables can be accessed through the `ENV` hash.  This circumvents
+identifier mangling.
+
+Environment variables can be expanded as in the following example:
+
+	IFS=:
+	for dir in ${ENV{PATH}}; do
+		: ${dir:=.}
+		if [ -x "${dir}/${cmd}" ]; then
+			printf '%s\n' "${dir}/${cmd}"
+			break
+		fi
+	done
+
+Environment variables can be set as in the following example:
+
+	ENV[LC_ALL]=C
+
+TODO
+====
+
+  * Array function `each` (maintains an iterator)
+  * Hash value functions: `length`, `keys`, `values`, `each`
+    - `keys` `join`s the keys array with `${US}`, then returns the result?
+      + Maybe sets `IFS="${US}"`, uses the shell's field splitting to remove
+        `${US}`, and returns a string (bad: space-delimited string of keys that
+        may contain spaces)
+      + Or just return the array?
+    - `each` iterates over the keys array (skipping unset keys) and returns a
+      key and value, delimited somehow (or, a new array?)
+  * Unsetting hash values and hashes
+    - Will need to unset keys array value
+    - Maintain a key ID (or key key) for each hash key (i.e. the key in the keys
+      array)
+    - Keys array could become large and sparse with lots of unsetting and
+      setting; should be heap instead?
+  * As above, consider building the hash structure on a heap built on an array
+  * Reference type checking in functions