Dockerfile Layer Cache Invalidation

1. Background Knowledge

Docker builds are optimized using a layer caching mechanism. Each instruction in a Dockerfile creates a new layer. If the inputs to an instruction (and all preceding instructions) remain unchanged from the previous build, Docker reuses the cached layer, skipping execution. This significantly speeds up iterative development. However, the cache is fragile: if any layer fails to match the cache, all subsequent layers are invalidated and must be rebuilt. This phenomenon is known as cache invalidation cascade.

The core challenge in this problem is determining which specific instructions trigger a cache miss based on file system changes. The primary culprit is usually the COPY or ADD instruction, which copies files from the build context (the local directory) into the image. If a file referenced by COPY has changed, that layer's content hash changes, causing a miss. Crucially, COPY --from=<stage> references another build stage's output, not the local build context, so local file changes do not directly invalidate these layers.

Understanding path matching is essential. A source path like . or ./ matches any file in the context. A specific path like src/ matches any file starting with src/. The problem simplifies this by defining strict rules: split the instruction, identify sources (operands not starting with -- and not the last operand), and check if any changed file falls under these sources. This requires careful string manipulation and logical comparison of file paths.

2. Algorithm Approach

The problem can be modeled as a sequential scan with state propagation. Since Docker processes instructions in order, we can iterate through the instructions list from first to last. We maintain a boolean flag, cache_missed, initialized to False.

For each instruction:

1. If cache_missed is already True, the current instruction is automatically rebuilt due to the cascade rule.
2. If cache_missed is False, we check if the current instruction itself causes a miss. This only applies to COPY or ADD instructions that read from the build context (i.e., do not have --from).
3. To check if a COPY/ADD misses, we parse its source paths and compare them against the changed_files set. If any changed file matches any source path, the layer misses.
4. If a miss is detected (either by cascade or direct match), we mark cache_missed as True and record the current instruction's index.

This approach is linear because each instruction is processed exactly once, and the state (cache_missed) is updated incrementally.

3. Step-by-Step Strategy

1. Initialize State: Create an empty list rebuilt_indices to store results. Set a boolean is_invalidated to False.
2. Iterate Instructions: Loop through instructions with index i (0-based). Convert to 1-based index for output.
3. Check Cascade: If is_invalidated is True, append i + 1 to rebuilt_indices and continue to the next instruction. No further parsing is needed for this layer.
4. Parse Instruction: If not invalidated, check if the instruction starts with COPY or ADD.

• If it does not, the layer is a cache hit (assuming no prior invalidation). Continue.
• If it does, check for --from. If --from is present, it reads from another stage, so it cannot be invalidated by local context changes. Continue.

5. Identify Sources: Split the instruction string by whitespace.

• The last token is the destination.
• Tokens before the destination that do not start with -- are source paths.

6. Match Changed Files: For each source path:

• Normalize the source: strip leading ./ and trailing /.
• If the normalized source is empty or ., it matches all changed files. If changed_files is not empty, the layer misses.
• Otherwise, check if any file in changed_files equals the source or starts with source + "/".

7. Update State: If a match is found, set is_invalidated to True and append i + 1 to rebuilt_indices.
8. Return Result: After the loop, return rebuilt_indices.

4. Common Pitfalls

• Misidentifying Sources: Remember that the last operand is the destination. In COPY src/ dest/, src/ is the source. In COPY --from=builder /app /local, /app is the source, but it’s from a stage, so ignore it for context changes.
• Path Matching Logic: Be careful with directory prefixes. A source src matches src/file.txt but not src2/file.txt. Ensure you check for file.startswith(source + "/") or file == source.
• Leading/Trailing Slashes: The problem specifies stripping leading ./ and trailing /. Failing to normalize ./src/ to src might cause mismatches if changed files are listed as src/file.txt.
• COPY. /app: The source . (or ./) matches any changed file. Do not treat it as a literal filename match only.
• 1-Based Indexing: The problem requires 1-based indices. Ensure you add 1 to the loop index when appending to the result list.
• Empty Changed Files: If changed_files is empty, no COPY from context will miss (unless the instruction itself changed, but the problem implies only file content changes matter for COPY cache). The cascade rule still applies if a previous layer missed.

5. Time & Space Complexity

• Time Complexity: $O(N \cdot M \cdot L)$, where $N$ is the number of instructions, $M$ is the number of changed files, and $L$ is the average length of file paths. In the worst case, for each COPY instruction, we compare every changed file against every source path. String matching takes $O(L)$. If $M$ is large, this could be optimized with a trie or sorting, but for typical Dockerfiles, $M$ is small.
• Space Complexity: $O(K)$, where $K$ is the number of rebuilt layers, to store the result list. Auxiliary space for parsing instructions is $O(L)$ per instruction. The changed_files set lookup can be optimized to $O(1)$ average if converted to a set, but since we need prefix matching, a simple list iteration is often sufficient unless $M$ is very large.