Filename Expansion (Globbing)

After this lesson your shell turns a pattern such as src/*.[ch] into the sorted list of paths that match it, leaves the pattern alone when nothing matches, and refuses to let a wildcard cross a slash or sweep up hidden files by accident. The filesystem here is a list of declared files, so every case is testable.

The program never sees the star

Type ls *.c and ls receives main.c util.c, not *.c. The shell replaced the pattern with the names that matched before running anything. That is why rm * is dangerous and why a shell can use the same wildcard rules for every command. This expansion happens late, after variables and quote removal, and only on the parts of a word that were unquoted.

The pattern language (POSIX 2.13)

A ] right after the opening bracket (or after the !) is a member of the set, and a - first or last is a plain dash. A [ that never closes is just a literal bracket.

Three rules decide what a wildcard may touch:

1. Components. Patterns match one path component at a time. * never matches /, so src/*.c looks only inside src, and the pattern and the path must have the same number of components.
2. Hidden files. A name beginning with . matches only if the pattern component begins with a literal .. So * skips .git but .* finds it, and so does .g*. A bracket or ? in first position does not count.
3. Directories too. Any directory on the way to a declared file exists. A pattern like * can match a directory name as well as a file name.

If nothing matches, the word stays exactly as typed. With several matches the list is sorted in byte order, so uppercase letters come before lowercase and _ falls between them.

Matching one component

A matcher can be written as a recursion that tries every way to split the name at each *. That is correct, and on *a*a*a*a*b against a long name of a's it takes exponential time. The efficient method keeps two cursors, one in the pattern and one in the name. At a * it remembers where it was and tentatively matches nothing. On a later mismatch it goes back to that single remembered star, lets the star swallow one more character and tries again. Each name character is retried only a bounded number of times, so the work is quadratic at worst, and there is no stack growth.

A worked trace

Match *b? against abcbd. The star is recorded with the name cursor at a. The next element b fails against a, so the star swallows a and tries again: b matches b, then ? takes c. The pattern is used up but bd is left over, which is a mismatch, so the matcher goes back to the remembered star and lets it swallow one more character. b fails against c, the star swallows c, then b matches b and ? takes d. Both cursors reach the end together: a match. Your matcher repeats exactly this retry.

Common mistakes

• Letting * match a slash, so *.c finds src/app.c.
• Matching hidden files with *, or forgetting that .* is how you ask for them.
• Treating an unclosed [ as an error instead of a literal.
• Sorting in a locale-aware way. The shell here compares bytes.

Your exercise

The starter reads FILE and MATCH lines, builds the set of paths including implied directories, splits patterns and paths into components and prints the results. You write the function that decides whether one pattern component matches one name. The most likely mistake is recursion that blows up on repeated stars.