# Reading loop-driven C code

Target function (dmenu-style word movement):

```c
static void
movewordedge(int dir)
{
	if (dir < 0) { /* move cursor to the start of the word*/
		while (cursor > 0 && strchr(worddelimiters, text[nextrune(-1)]))
			cursor = nextrune(-1);
		while (cursor > 0 && !strchr(worddelimiters, text[nextrune(-1)]))
			cursor = nextrune(-1);
	} else { /* move cursor to the end of the word */
		while (text[cursor] && strchr(worddelimiters, text[cursor]))
			cursor = nextrune(+1);
		while (text[cursor] && !strchr(worddelimiters, text[cursor]))
			cursor = nextrune(+1);
	}
}
```

## Facts needed before tracing

- `cursor` is a gap between characters. `text[cursor]` is the character to its right. For ASCII, `text[cursor-1]` is the character to its left.
- `nextrune(-1)` is the index of the previous character, `nextrune(+1)` the index of the next one. For ASCII text these are `cursor-1` and `cursor+1`. Level 4 covers UTF-8.
- `strchr(set, c)` is non-NULL when `c` occurs in `set`. It also returns non-NULL for `c == '\0'`, because the terminator counts as part of the string. This is why the forward loops test `text[cursor]` first.
- `A && B` evaluates `B` only when `A` is true. The guard on the left protects the access on the right.
- A `while` loop stops when its condition is false. For `while (A && B)` that means `!A || !B`.

## Tracing on paper

1. Write the text as a row of boxes with an index row underneath. Include the terminating `\0`.
2. Mark the cursor as an arrow between two boxes.
3. Replace helper calls with their meaning for this input: `nextrune(-1)` becomes `cursor-1`, `strchr(worddelimiters, x)` becomes "x is a delimiter".
4. Make a table with one row per loop iteration: cursor, each condition, action.
5. When a loop stops, write which condition failed. This gives the state after the loop.

Worked example. Delimiters are `" "`, direction is backward, cursor is 7.

```
s:  f  o  o  _  b  a  r  \0
i:  0  1  2  3  4  5  6  7
```

Loop 1 (skip delimiters leftwards): `s[6]` is `r`, not a delimiter. It stops immediately. Cursor stays 7.

Loop 2 (skip word characters leftwards):

| cursor | cursor > 0 | s[cursor-1] | delimiter? | action |
|---|---|---|---|---|
| 7 | T | r | no | cursor = 6 |
| 6 | T | a | no | cursor = 5 |
| 5 | T | b | no | cursor = 4 |
| 4 | T | _ | yes | stop |

Result: 4, the start of `bar`.

## Reading by what is true after each loop

A loop can be read by its exit condition instead of by its iterations.

- Backward loop 1 ends with: cursor is 0, or the character to its left is not a delimiter.
- Backward loop 2 ends with: cursor is 0, or the character to its left is a delimiter.
- After both, the cursor sits at the start of a word, or at 0.

The forward version mirrors this with the right-hand neighbour. Loop 2 ends on a delimiter or the end of the string, so the cursor lands one past the last character of the word.

Each function in this style is a sequence of "skip while class A" and "skip while class not-A". Once that shape is recognised, reading reduces to identifying the classes and the direction.

## Speeding up

| Stage | Write down | Leave out |
|---|---|---|
| 1 | Full table, every iteration, every condition | nothing |
| 2 | Box diagram with indices, cursor value at each loop exit | per-iteration condition values |
| 3 | Box diagram and one phrase per loop ("skip delimiters leftwards") | mid-loop cursor values |
| 4 | The phrases and the boundary cases | the diagram, except at boundaries |
| 5 | nothing | paper |

Rules for moving between stages:

- Move up after five consecutive correct answers in a level.
- Move down one stage after any wrong answer on a boundary case.
- Record the time per exercise. Move up when the times stop falling.

Boundary cases to check at every stage: cursor at 0, cursor at the end, text made only of delimiters, empty text, cursor already on an edge.

Suggested pairing: levels 0 to 2 at stages 1 and 2, levels 3 to 5 at stages 3 and 4, levels 6 and 7 at stage 4 and 5.

## Level 0. Conditions

Delimiters are `" ,."`.

- 0.1 Is `strchr(worddelimiters, c)` non-NULL for `'a'`, `','`, `' '`, `'\0'`?
- 0.2 In `cursor > 0 && strchr(d, text[cursor-1])` with `cursor == 0`, which operands are evaluated?
- 0.3 `while (A && B) body;` Write the condition that holds on exit.
- 0.4 `while (text[cursor] && strchr(d, text[cursor])) cursor++;` Name every reason the loop can stop.

## Level 1. A single loop

Text `s = "  ab c"` (indices 0 to 5, `\0` at 6).

```c
(a) while (s[i] == ' ') i++;
(b) while (s[i] && s[i] != ' ') i++;
(c) while (i > 0 && s[i-1] != ' ') i--;
```

Final value of `i`:

- 1.1 loop (a), start `i = 0`
- 1.2 loop (b), start `i = 2`
- 1.3 loop (c), start `i = 6`
- 1.4 loop (c), start `i = 4`
- 1.5 loop (c), `s = "abc"`, start `i = 3`
- 1.6 loop (a), `s = "    "` (four spaces), start `i = 0`

## Level 2. Two loops in sequence

Delimiter is a single space. `F` and `B` are the ASCII versions of the forward and backward branches.

```c
F:  while (s[c] && s[c] == ' ') c++;
    while (s[c] && s[c] != ' ') c++;

B:  while (c > 0 && s[c-1] == ' ') c--;
    while (c > 0 && s[c-1] != ' ') c--;
```

Final cursor:

| # | text | op | start |
|---|---|---|---|
| 2.1 | `foo bar` | F | 0 |
| 2.2 | `foo bar` | F | 3 |
| 2.3 | `foo   bar` | F | 3 |
| 2.4 | `foo  ` | F | 3 |
| 2.5 | `  x` | F | 0 |
| 2.6 | `` (empty) | F | 0 |
| 2.7 | `foo bar` | B | 7 |
| 2.8 | `foo bar` | B | 4 |
| 2.9 | `foo   bar` | B | 6 |
| 2.10 | `  foo` | B | 2 |
| 2.11 | `foo bar ` | B | 8 |

## Level 3. Reading by exit condition

Do these without a trace table first, then check with one.

- 3.1 For B, state in words what each loop guarantees on exit.
- 3.2 Delimiters are `" ,"`, text is `a,b c`. Find F from 0, F from 1, B from 5.
- 3.3 Swap the two loops of F. Text `foo bar`. Find the result from 0, 3, 4. Describe the new behaviour in one sentence.
- 3.4 Swap the two loops of B. Text `foo bar`. Find the result from 7 and from 3.

## Level 4. UTF-8 and nextrune

```c
static size_t
nextrune(int inc)
{
	ssize_t n;

	/* return location of next utf8 rune in the given direction (+1 or -1) */
	for (n = cursor + inc; n + inc >= 0 && (text[n] & 0xc0) == 0x80; n += inc)
		;
	return n;
}
```

Continuation bytes have the bit pattern `10xxxxxx`. The loop steps over them and stops on a lead byte.

Text `aé b` is the bytes `61 C3 A9 20 62`, indices 0 to 4, `\0` at 5. Delimiter is a space.

- 4.1 `nextrune(-1)` with cursor 4, 3, 1.
- 4.2 `nextrune(+1)` with cursor 0, 1, 4.
- 4.3 Run the full backward branch from cursor 5, then from 4, then from 3.

## Level 5. The full function

Delimiters `" ,"`, text `hello, world  foo`, length 17.

- 5.1 Call `movewordedge(+1)` repeatedly from 0 until the cursor stops changing. List the cursor values.
- 5.2 Call `movewordedge(-1)` repeatedly from 17. List the cursor values.
- 5.3 Write the full trace table for one call, `movewordedge(-1)` from 14, and time yourself.

## Level 6. Breaking the code

- 6.1 Remove `cursor > 0 &&` from the first backward loop. Text `x`, cursor 0. What happens?
- 6.2 Remove `text[cursor] &&` from the first forward loop. Text `ab`, cursor 2. What happens?
- 6.3 In the backward branch, remove the `!` from the second loop. Text `foo bar`, delimiter space. Find the result from 7 and from 4.
- 6.4 Write the first backward condition as `strchr(worddelimiters, text[nextrune(-1)]) && cursor > 0`. What changes?

## Level 7. Writing and transfer

- 7.1 Write `movewordstart(int dir)` that moves forward to the start of the next word, and backward to the end of the previous word. Use only the two loops you already have.
- 7.2 Both branches repeat the same shape. Write a helper `skip(int dir, int delim)` and rewrite `movewordedge` as two calls to it.
- 7.3 Trace the function below on `"  hi \t"` and on `"   "`. Pointer arithmetic replaces the index here. Draw both pointers on the diagram.

```c
static char *
trim(char *s)
{
	char *e;

	while (*s == ' ' || *s == '\t')
		s++;
	e = s + strlen(s);
	while (e > s && (e[-1] == ' ' || e[-1] == '\t'))
		e--;
	*e = '\0';
	return s;
}
```

- 7.4 Pick a function with two or three loops from a small C project. Reduce each loop to a phrase and predict the result on three inputs before running it.

## Answers

Level 0

- 0.1 no, yes, yes, yes. The terminator counts as part of the set.
- 0.2 Only `cursor > 0`. `text[cursor-1]` is never read.
- 0.3 `!A || !B`
- 0.4 End of string, or the current character is not a delimiter.

Level 1

- 1.1 2
- 1.2 4
- 1.3 5
- 1.4 2
- 1.5 0, stopped by the `i > 0` guard.
- 1.6 4. `\0` differs from `' '`, so the loop stops at the terminator.

Level 2

- 2.1 3
- 2.2 7
- 2.3 9
- 2.4 5
- 2.5 3
- 2.6 0
- 2.7 4
- 2.8 0
- 2.9 0
- 2.10 0
- 2.11 4

Level 3

- 3.1 Loop 1: cursor is 0 or the character to its left is not a delimiter. Loop 2: cursor is 0 or the character to its left is a delimiter.
- 3.2 F from 0 is 1. F from 1 is 3. B from 5 is 4.
- 3.3 0 gives 4, 3 gives 4, 4 gives 7. The cursor moves to the start of the next word, or to the end of the text.
- 3.4 7 gives 3, 3 gives 0. The cursor moves to the end of the previous word, or to 0.

Level 4

- 4.1 3, 1, 0. At cursor 1, `n` becomes 0, then `n + inc` is -1 and the loop stops.
- 4.2 1, 3, 5. From 1, byte 2 is a continuation byte, so `n` advances to 3.
- 4.3 From 5: 4. From 4: 0. From 3: 0. Byte `C3` is a lead byte and is not in the delimiter set.

Level 5

- 5.1 5, 12, 17
- 5.2 14, 7, 0
- 5.3 Loop 1: `s[13]` and `s[12]` are spaces, so cursor goes 14, 13, 12. `s[11]` is `d`, so it stops at 12. Loop 2: cursor goes 12, 11, 10, 9, 8, 7. `s[6]` is a space, so it stops. Result 7.

Level 6

- 6.1 `nextrune(-1)` at cursor 0 returns -1, converted to a huge `size_t`. `text` is read out of bounds, which is undefined behaviour.
- 6.2 `text[2]` is `'\0'`, `strchr` treats it as a delimiter, and the cursor advances past the end of the string. Undefined behaviour.
- 6.3 Both loops skip delimiters only. From 7 the result is 7. From 4 the result is 3.
- 6.4 The guard runs after the read, so `text[nextrune(-1)]` is evaluated at cursor 0 and the out-of-bounds read returns.

Level 7

- 7.1 Swap the loop order in each branch. Forward: skip non-delimiters, then delimiters. Backward: skip non-delimiters, then delimiters.
- 7.2 One possible form:

```c
static void
skip(int dir, int delim)
{
	if (dir < 0)
		while (cursor > 0 && !!strchr(worddelimiters, text[nextrune(-1)]) == delim)
			cursor = nextrune(-1);
	else
		while (text[cursor] && !!strchr(worddelimiters, text[cursor]) == delim)
			cursor = nextrune(+1);
}

static void
movewordedge(int dir)
{
	skip(dir, 1);
	skip(dir, 0);
}
```

- 7.3 `"  hi \t"` (length 6): `s` advances to index 2, `e` starts at 6 and moves to 4, `*e = '\0'`, result `"hi"`. `"   "`: `s` advances to index 3 (the terminator), `e == s`, the second loop does not run, result `""`.