Intro

Welcome back; as a reminder, in the previous part, you learned about completions generation flow, how to deal with user input, and how to deal with edge cases. In this part, we'll figure out how the actual navigation logic happens, its execution logic, and how the z command is exposed as an executable.

C-7 Create navigation

# z.sh:146 # _z { ... } / else { .. } local cd cd="$( < <( _z_dirs ) \awk -v t="$(\date +%s)" -v list="$list" -v typ="$typ" -v q="$fnd" -F"|" ' function frecent(rank, time) { # relate frequency and time dx = t - time return int(10000 * rank * (3.75/((0.0001 * dx + 1) + 0.25))) } function output(matches, best_match, common) { # list or return the desired directory if( list ) { if( common ) { printf "%-10s %s\n", "common:", common > "/dev/stderr" } cmd = "sort -n >&2" for( x in matches ) { if( matches[x] ) { printf "%-10s %s\n", matches[x], x | cmd } } } else { if( common && !typ ) best_match = common print best_match } } function common(matches) { # find the common root of a list of matches, if it exists for( x in matches ) { if( matches[x] && (!short || length(x) < length(short)) ) { short = x } } if( short == "/" ) return for( x in matches ) if( matches[x] && index(x, short) != 1 ) { return } return short } BEGIN { gsub(" ", ".*", q) hi_rank = ihi_rank = -9999999999 } { if( typ == "rank" ) { rank = $2 } else if( typ == "recent" ) { rank = $3 - t } else rank = frecent($2, $3) if( $1 ~ q ) { matches[$1] = rank } else if( tolower($1) ~ tolower(q) ) imatches[$1] = rank if( matches[$1] && matches[$1] > hi_rank ) { best_match = $1 hi_rank = matches[$1] } else if( imatches[$1] && imatches[$1] > ihi_rank ) { ibest_match = $1 ihi_rank = imatches[$1] } } END { # prefer case sensitive if( best_match ) { output(matches, best_match, common(matches)) exit } else if( ibest_match ) { output(imatches, ibest_match, common(imatches)) exit } exit(1) } ')"

Now that we have extracted all the supplied positional arguments and command options cases into our local variables and also dealt with possible edge cases, we can start building the main navigation logic, the bread and butter of the z program, and the part we have all been waiting for.

Using the awk program, we want to find the best matching path from the data file and store it in a local variable cd for future navigation using the built-in "cd" command.

We find this path by reading from the $datafile line by line; each line entry is referred to as a record in awk context which contains 3 fields:

1. Path field.
2. Rank field.
3. Timestamp field.

REMINDER: Awk Input shall be interpreted as a sequence of records. By default, a record is a line, less its terminating, but this can be changed by using the RS built-in variable. Read more.

A line in our $datafile will have the following structure:

• "PATH|RANK|TIMESTAMP\n"

When we pass the $datafile to the awk program, it will iterate on its lines, treating them as records, it will split each record into array-like fields by the provided field separator (FS), a pipe character in our case (|), those fields can be accessed by $n accessor where n represents the array position starting from 1:

• $1 - PATH
• $2 - RANK
• $3 - TIMESTAMP

We find the best-matching record by calculating each record's frequency and recency from its rank and timestamp fields.

We compare each record resulting calculation to the previous record's result to find the highest-ranking one. We then extract its path field and store it in our local cd variable.

Next, we'll break the above logic into smaller pieces and discuss each in detail to examine how this happens.

Providing input for AWK

local cd cd="$( < <( _z_dirs ) \awk -v t="$(\date +%s)" -v list="$list" -v typ="$typ" -v q="$fnd" -F"|" ' ...Awk body ')"

• <( list ) - Process substitution. The process list is run asynchronously, and its input or output appears as a filename. This filename is passed as an argument to the current command as the result of the expansion. The file passed as an argument should be read to obtain the output of list. Read more.

Goal: Pass the function _z_dirs output to the awk command as input alongside our local variables, execute it in a sub-shell process, and save its resulting path output to the cd variable so that we can later perform navigation using this variable as the destination.

Walkthrough: We start by defining a local variable cd and assigning to it a string resulting from the evaluation of the command substitution "$(command)"; remember that a command substitution invokes a sub-shell and replaces the command with its resulting stdout. If the substitution appears within double quotes, as in our case, word splitting and filename expansion are not performed on the result.

The awk command expects to get its input from file descriptor 0 (stdin); to provide awk input to work on, we need to assign a value to stdin inside the command substitution sub-shell.

We provide this value by performing a process substitution <(command) on the _z_dirs function as a command; this allows us to use the output of _z_dirs as if it were a file, meaning the result appears as the filename "/dev/fd/<n>."

We pass the resulting filename as an argument to the input redirection command [n]<word, this command causes the file whose name results from the expansion of the word portion to be opened for reading on the standard input (file descriptor 0) if n is not specified as in our case.

The combination of both process substitution and input redirection without explicitly specifying file descriptor and defaulting to 0 (stdin) will look like < <( _z_dirs); this will result in stdin holding the output of _z_dirs for the awk command to operate on.

Next, we pass our local variables and define a field separator for awk to be used inside the awk command execution.

We pass variables using the -v option followed by a value; the local variables we'll use are $list, $typ, $fnd and pass them into awk as list, typ, q alongside t as a variable holding the current timestamp. Then, we use the -F option with the pipe character | as a value for the field separator.

Next, we'll dive into the Awk language. We start by defining three functions: freecent, output, and common, which will abstract repeating calculations and help us keep the code DRY.

Don’t repeat yourself (DRY) - is a principle of software development aimed at reducing repetition of information which is likely to change, replacing it with abstractions that are less likely to change, or using data normalization which avoids redundancy in the first place. Read more.

---

Frecent function

function frecent(rank, time) { # relate frequency and time dx = t - time return int(10000 * rank * (3.75/((0.0001 * dx + 1) + 0.25))) }

• int(x) - awk command that return the nearest integer to x, located between x and zero and truncated toward zero. Read more.

Goal: Define the frecent function which receives the current rank and time for each record and returns a newly calculated rank utilizing an algorithm, the resulting calculation will be derived from the number of times we visited the path (frequency) in conjunction with the amount of time passed since the last visit (recency).

Walkthrough: When we invoke the frecent function, we pass $2 and $3 as parameters, allowing us to access the rank and time for the current record that awk is iterating on.

Remember that t is a variable we passed earlier to the awk program. It stores the result of the date +%s command, which gives us a timestamp representing "now" in seconds since the epoch time.

We define a local variable dx, which will store the subtraction of the timestamp representing "now" (t) from the timestamp currently stored in the record (time), resulting in the delta between now and the last time the path was visited.

The algorithm we'll use can be reasoned about as follows:

• If a path visited less than an hour ago, the rank is multiplied by 4.
• If a path visited less than a day ago, the rank is multiplied by 2.
• If a path visited less than a week ago, the rank is divided by 2.
• If a path visited more than a week ago, the rank is divided by 4.

Conversion of hour, day, and week to seconds results in:

• Hour: 3600 seconds.
• Day: 86400 seconds.
• Week: 604800 seconds.

A simplified implementation of the above algorithm:

if( dx < 3600 ) return rank * 4 if( dx < 86400 ) return rank * 2 if( dx < 604800 ) return rank / 2 else return rank / 4

You may wonder about the difference between our simplified algorithm and what's written in the actual code. Let's work through it with a few examples to show they achieve the same goal.

Given that:

• Delta: dx=3600.
• Current rank: $2=5.
• Formula: 10000 * rank * (3.75/((0.0001 * dx + 1) + 0.25))

Placing given variables in the given formula and calculating the result:

1. (0.0001 * dx + 1) = 3600 * 0.0001 + 1 = 1.36
2. (1.36 + 0.25) = 1.61
3. (3.75/1.61) = 2.329
4. rank * 2.329 = 5 * 2.329 = 11.645
5. 10000 * 11.645 = 116,459

Given a current rank of 5 and a delta of one hour, it will result in a new rank of 116,459.

Given the same current rank and changing only the delta (dx) will yield the following results:

• Hour (dx=3600, $2=5): 116,459 (116k).
• Day (dx=86400, $2=5): 18,958 (18k).
• Week (dx=604800, $2=5): 3,037 (3k).
• Two weeks (dx=1209600, $2=5): 1,534 (1.5k).

We clearly see that we get a lower result for a given rank as time passes.

Let's see what happens if we put a higher rank resulting from the one-hour previous calculation to simulate two visits:

• Hour + hour (dx=3600, $2=116459): 2,712,554,347 (2.7b).
• Day + hour (dx=86400, $2=116459): 441,578,614 (441m).
• Week + hour (dx=604800, $2=116459): 70,747,003 (70m).
• Two weeks + hour (dx=1209600, $2=116459): 35,735,312 (35m).

As before, we get a lower result for a given rank as time passes; we also see that providing a higher initial rank results in higher output.

Let's see what happens if we put a lower rank resulting from the two-week previous calculation to simulate two visits:

• Hour + two weeks (dx=3600, $2=1534): 35,729,813 (35m).
• Day + two weeks (dx=86400, $2=1534): 5,816,481 (5m).
• Week + two weeks (dx=604800, $2=1534): 931,880 (931k).
• Two weeks + two weeks (dx=1209600, $2=1534): 470,706 (470k).

As before, we get a lower result for a given rank as time passes; we also see that providing a lower initial rank results in lower output.

Putting all the previous results in a single view:

• 1h + 1h (2 visits in 2h) = 2.7b.
• 1h + 1d (2 visits in 25h) = 441m.
• 1h + 1w (2 visits in 169h) = 70m.
• 1h + 2w (2 visits in 337h) = 35m.
• 2w + 1h (2 visits in 337h) = 35m.
• 2w + 1d (2 visits in 360h) = 5m.
• 2w + 1w (2 visits in 504h) = 931k.
• 2w + 2w (2 visits in 672h) = 470k.

We see correlation between accumulated visits time and the resulting rank, that is, a rank is lowered as more time passes per path.

Eventually, with enough time passed, the rank will drop beyond a certain threshold, and the corresponding entry will be removed from the $datafile.

Recall from line 72 that every time we add a new entry, all current entries are reevaluated and possibly dropped from the list.

---

Output function

function output(matches, best_match, common) { # list or return the desired directory if( list ) { if( common ) { printf "%-10s %s\n", "common:", common > "/dev/stderr" } cmd = "sort -n >&2" for( x in matches ) { if( matches[x] ) { printf "%-10s %s\n", matches[x], x | cmd } } } else { if( common && !typ ) best_match = common print best_match } }

• printf format [ , expression-list ] [ > expression ] - printf action statement, passing a format according to man 3 printf, it accepts comma separated expression-list, and optionally pipe(|) or redirect(>, >>) to expression surrounded by double quotes. in our case: printf "%-10s %s\n" will format first string field(%s) "%-10s" to left adjusted by 10 character, second field adds new line character(\n) at the end of line. it should accept two items as expression-list and a pipe or redirection expression. Read more.
• sort [OPTION]... [FILE]... - write sorted concatenation of all FILE(s) to standard output, -n OPTION or numeric sort, compares according to string numerical value. Read more.

Goal: should print the best_match argument unless some cases require a different output. If we encounter those cases, we use matches and common arguments to provide relevant output depending on the case. The cases are:

1. If the list variable is true.
   • The list variable is true when the -l option is used.
   • Iterate the matches argument and print each value.
   • Sort the output according to the numerical value of strings.
   • Redirect output to stderr.
2. If a common argument exists, and the list variable is true.
   • Print the formatted common path.
   • Redirect output to stderr.
   • Continue with case 1.
3. If a common argument exists, and list and typ args are false.
   • The typ variable is false when the -t option is not used.
   • The typ variable is false when the -r option is not used.
   • The list variable is false when the -l option is not used.
   • Assign best_match to equal the common variable.
   • Continue with case 4.
4. If none of the above cases apply.
   • Print the best_match argument or overwritten local variable.

Walkthrough: The output function receives the following three arguments:

• matches: an associative array, with keys as paths and values as ranks.
• best_match: the highest rank path string.
• common: a common path string from the matches array resulting from the common function.

In the next section we’ll walk through the common function and see exactly how it extracts the most common path from the matches array. All you need to know for now is that the common argument stores the result of this function, which is the common path for a given matches array, the same array we use as the first argument.

We check if the list variable exists before entering the if block; otherwise, we enter the else block. In the if block, we check if the common argument exists; if it does, we invoke the printf command with:

• format: "%-10s %s\n".
• expression-list: "common:", common.
• expression: "/dev/stderr".

The printed output will be: common: <common>\n with 4 spaces between the string "common:" and the common variable. We then redirect the output of printf to /dev/stderr so that it won't get to the awk stdout and won't get assigned to the cd variable as a result.

This interesting and unexpected result of 4 spaces makes perfect sense once you understand what's happening here.

The format "%-10s %s/n" states that:

• Left adjust the first field by 10 characters.
• Add a space character between the first field and the second.
• Append newline (/n) immediately after the second field.

The first expression list item is the "common:" string, which has a length of 7 characters; it will occupy the first string field from the left plus 3 extra space characters, for a total of 10, as defined by the format for the first string field. We get the fourth space character because the format adds an additional space character between the first and second fields.

We continue in the if block and define a cmd local variable; it encapsulates the sort command with a numeric sort (-n) option and redirects stdout (file descriptor 1) to stderr (file descriptor 2) (1>$2) by the standard redirection command ([n]>&word) we're already familiar with. We do this so that the sort output won't reach the awk stdout.

Then, we iterate over the matches array; each iteration checks if matchs[x] holds a value; if it does, we use the printf command with the same format as we previously used, only this time, we pass as an expression-list the rank (matches[x]) and the path (x). Then, we pipe the printf output to the previously defined cmd variable.

Suppose the list variable doesn't exist, and we get to the else block. In that case, we check if the common argument exists and typ variable is false, if the test passes then assign the common argument to equal the best_match variable instead of the passed argument.

Finally, print best_match as either the overwritten common or as the original best_match argument. We don't use redirection over the print command so that the output of the print command will return from awk as stdout and will be assigned to the outer cd variable so that we can perform a navigation.

---

Common function

function common(matches) { # find the common root of a list of matches, if it exists for( x in matches ) { if( matches[x] && (!short || length(x) < length(short)) ) { short = x } } if( short == "/" ) return for( x in matches ) if( matches[x] && index(x, short) != 1 ) { return } return short }

• return [expression] - this statement returns control to the calling part of the awk program. It can also be used to return a value for use in the rest of the awk program. Read more.
• index(in, fnd) - search the string in for the first occurrence of the string fnd and return the position in characters where that occurrence begins in the string in. Read more.

Goal: find the shortest path by character length and confirm that it's included in the "matches" array argument, hence the "common" path. We also need to handle an edge case in which the shortest path is the root.

Walkthrough: Iterate over the matches associative array argument; for each item x confirm existence by matches[x] and do the following:

• If the short variable doesn't exist, this will happen only on the first iteration; in this case, we immediately enter the if block.
• If the short variable exists, we enter the if block only if the character length of x is smaller than the character length of the previously assigned short.

In the if block, assign the short variable to equal the current x. At the end of this iteration, we will find the shortest path in the matches array.

Next, we deal with the edge case in which the shortest path we found is the root path (/). in this case, we compare our local variable short to the string "/"; if the check passes, we return early with no result.

Next, we confirm that the short variable is the common path for all matches by iterating again over the matches array; for each item x, confirm existence by matches[x] and check if short doesn't occupy its first index by index(x, short) != 1; if the index is not 1, return early with no result.

If all checks don't return early, we return with the most common shortest path result.

---

Awk BEGIN pattern

BEGIN { gsub(" ", ".*", q) hi_rank = ihi_rank = -9999999999 }

• BEGIN - Each BEGIN pattern shall be matched once and its associated action executed before the first record of input is read. you can Read more on Awk man page under “Special Patterns”.

• gsub(arg1, arg2, [, arg3]) - An internal global string replace function, it’s same as "sub" but works on all occurrences not just the first.

  • arg1 is a regex/string pattern to lookup.
  • arg2 is a string to replace found instances with.
  • arg3 is a variable/field/string to work on, i.e $3, [, string].

  you can Read more on the Awk man page under “String Functions”.

• .* - In regex the dot means anything can go here and the star means at least 0 times so .* accepts any sequence of characters, including an empty string.

Goal: Define variables that will be available during the awk body execution.

Walkthrough: Replace each space character from the current query (q) with the .* string using gsub(" ", ".*", q)overwriting the q variable with the result.

The reason we replace every space character with .* is because, in the awk body, we'll use the regular expression matching operator (~ explained on the next sub-chapter) to evaluate q as a regex pattern to match against the path field ($1). It should match on deeply nested paths that include any word from the search query.

For example, suppose we store in our $datafile two records with the following long paths fields:

1. /some/1/long/path/foo/bar|100|1234
2. /some/2/long/path/foo/bar|100|1234

Executing z 2 foo will result in the $fnd variable storing 2 foo as a string with two words. Since we passed the $fnd variable as the q awk variable, then q will be the same two-word string.

Replacing the separating space with .* using gsub will turn q into 2.*foo; the regex matching operator (~) will match the 2/long/path/foo part from our second example and return a truthy value of 1 for that record which we can then access its path field ($1) to get the full path.

You’ll see this in action on the next sub-chapter about the awk body.

Define two variables, hi_rank, and ihi_rank, for sensitive and insensitive cases and set them to equal the default minimum rank value of -9999999. In the next sub-chapter, we’ll see that the awk body will ignore any record with a lower rank than this value.

---

Awk body

{ if( typ == "rank" ) { rank = $2 } else if( typ == "recent" ) { rank = $3 - t } else rank = frecent($2, $3) if( $1 ~ q ) { matches[$1] = rank } else if( tolower($1) ~ tolower(q) ) imatches[$1] = rank if( matches[$1] && matches[$1] > hi_rank ) { best_match = $1 hi_rank = matches[$1] } else if( imatches[$1] && imatches[$1] > ihi_rank ) { ibest_match = $1 ihi_rank = imatches[$1] } }

• ~, !~ - The awk utility shall make use of the extended regular expression(ERE) notation. A regular expression can be matched against a specific field or string by using one of the two regular expression matching operators,~ and !~. These operators shall interpret their right-hand operand as a regular expression and their left-hand operand as a string. If the regular expression matches the string, the ~ expression shall evaluate to a value of 1, and the !~ expression shall evaluate to a value of 0. you can Read more on the Awk man page under “Regular Expressions”.
• tolower(s) - Return a string based on the string s. Each character in s that is an uppercase letter specified to have a "tolower" mapping by the LC_CTYPE category of the current locale shall be replaced in the returned string by the lowercase letter specified by the mapping. you can Read more on the Awk man page under “String Functions”.

Goal: Iterate over each record, recalculate rank per record unless the "typ" variable exists, store into an associative array variable every record matching the search query with the path being the key and rank as a value, find the highest rank best matching record, and store its path field to a variable. We'll use the array and the best match variables in the awk "END" block to output results.

Walkthrough: First, we need to create five variables that we'll fill during the Awk body iteration over each record:

• rank
• matches
• imatches
• best_match
• ibest_match

Awk will iterate over the records in its body, each record corresponding to a line from our $datafile; it will recalculate each record rank by utilizing our previously defined frecent function and save the result to a rank variable unless the user passed either the -r or -t options which will map to the typ variable. In that case, the rank variable will be either the current record rank ($2) on the -r case or the subtraction of the current record timestamp ($3) and now (t) on the -t case.

Then, we check if a record path field ($1) matches our search query (q) through the regex matching operator (~). If we find a match, we save the matching query record to the matches associative array with its path ($1) as the key and previously defined rank as the value.

Otherwise, if we don't find a match, then we try matching the insensitive case, we do the same logic, but this time passing it through the tolower function first and saving results to the imatches variable instead.

Then, we check if the saved matches array at the position of our record path field ($1) value, which is assigned to the current rank by the previous logic, has a higher rank value than the current hi_rank variable.

The hi_rank variable will default to -9999999999 on the first iteration as we defined it on the BEGIN block; if matches doesn't contain our record path field ($1), then we try extracting it from the imatches array and comparing it to ihi_rank which also default to the same negative integer.

Once we confirm we have an item with a higher rank than the default for either the insensitive case or the sensitive case, we assign the best_match or the ibest_match to the current record path ($1) and reassign hi_rank or ihi_rank to the current rank variable.

On the next record iteration, we will compare against those values instead of the default we defined in the BEGIN block; when we finish iterating over all records, those variables will contain the single highest rank and the best matching path by rank for the sensitive and insensitive cases that we can access in the awk END block.

---

Awk END pattern

END { if( best_match ) { output(matches, best_match, common(matches)) exit } else if( ibest_match ) { output(imatches, ibest_match, common(imatches)) exit } exit(1) }

• exit(expression) - The exit statement shall invoke all END actions in the order in which they occur in the program source and then terminate the program without reading further input. An exit statement inside an END action shall terminate the program without further execution of END actions. If an expression is specified in an exit statement, its numeric value shall be the exit status of awk, unless subsequent error are encountered or a subsequent exit statement with an expression is executed. You can Read more on the Awk man page under “Actions”.

Goal: execute the output function over the sensitive case if it exists or the insensitive if it does not. If neither exists, then exit with a nonzero argument indicating an error.

Walkthrough: Invoke the output function for either the sensitive or the insensitive case by using if on the best_match variable or else if on the ibest_match variable; each case invokes the function with three positional parameters, which are:

• matches or imatches - an associative array of the paths as keys and their rank as values.
• best_match or ibest_match - a single best-matching path field.
• common(matches) or common(imatches) - a common path shared between all matches.

For the sensitive case, we'll pass the matches variable as the first parameter, the best_case variable as the second, and the result of invoking the common function with the matches parameter as the third and last parameter.

For the insensitive case, we do the same but use imatches instead of the matches variable, ibest_match instead of the best_match variable, and invoke common with imatches instead of the matches parameter.

Once the output function finishes executing, we successfully exit the awk program. The print command output from our output function will be the value stored in the outer cd local variable, which will be either the best matching path or the most common one.

C-8 Execute navigation

# z.sh:217 # _z { ... } / else { .. } if [ "$?" -eq 0 ]; then if [ "$cd" ]; then if [ "$echo" ]; then echo "$cd"; else builtin cd "$cd"; fi fi else return $? fi fi # this is the end of the else block from line 119 } # this is the end of _z function block from line 34

• arg1 -eq arg2 - Arithmetic binary operator, return true if arg1 is equal to arg2, respectively. the arg1 and arg2 may be positive or negative integers. Read more.
• builtin [shell-builtin [args]] - Run a shell builtin, passing it args, and return its exit status. This is useful when defining a shell function with the same name as a shell builtin, retaining the functionality of the builtin within the function. The return status is non-zero if shell-builtin is not a shell builtin command. Read more.
• echo [-neE] [args …] - Output the args, separated by spaces, terminated with a newline. The return status is 0 unless a write error occurs. Read more.

Goal: navigate or print the best-matching path resulting from the awk stdout, which is stored in the cd variable. If a user executes the script with the -e option, print cd and prevent navigation instead.

• The -e option will assign 1 to the echo variable.

Walkthrough: test whether the last command was executed without error by [ "$?" -eq 0 ]. If the return code is anything but success (0 status code), we return from the script with the last execution status.

Note that we have a built-in cd command and a cd variable, which are not the same; this also applies to the echo command and the echo variable.

Then, test if the cd variable has a value; if not, silently fail. In a nested if, test that the echo variable has a value; if it does, then execute the echo command on the cd variable to print the best matching path. If the echo variable is undefined, use the built-in cd command and execute it over the path stored in the cd variable. This will navigate the user shell to that path.

---

C-9 Make executable

# z.sh:227 alias ${_Z_CMD:-z}='_z 2>&1'

• alias [-p] [name[=value] …] - Without arguments or with the -p option, alias prints the list of aliases on the standard output in a form that allows them to be reused as input. If arguments are supplied, an alias is defined for each name whose value is given. Read more.

Goal: enable the z command in the user shell using an alias.

Walkthrough: we define an alias with a name that is the possibly existing _Z_CMD environment variable. Since this global variable does not store a value by default, we will fall back to "z" as the default name.

Assign the value of the alias to the _z local function and redirect its stderr to stdout.

This alias allows the user to use the z command in the shell environment after sourcing the script file.

Part conclusion

Congratulations on making it to the end of this part. In this part, you learned about how the actual navigation logic happens, its execution logic, and how the "z" command is exposed as an executable. In the next part, we'll deep-dive into shell integration and explore how hooks and auto-completions work on both zsh and bash. This last chapter will tie together all the flows we covered up until now. Whenever you are ready, hit the following part link. See you there!