Recursive Traversal and Filtering

Part II · Module 18 · Chapter 18.6 · Recursive Traversal and Filtering

1. Where Chapter 18.5 Stopped

The previous chapter ended with the observation that a glob pattern matches names and cannot express "except", and showed the filter that results:

srcs = [p for p in RTL.rglob("*.sv")
        if "generated" not in p.parts]

That is correct, it is the right default, and this chapter is about the two things it leaves open: how to express an exclusion policy that has more than one entry, and what to do when walking the excluded directories is itself the expensive part.

2. One Name Is Never Enough

A real tree has several categories to exclude, and they arrive one at a time:

module alu; endmodule

module fifo; endmodule

module regs; endmodule

module axi; endmodule

from pathlib import Path

SKIP = {"generated", "third_party", ".git", "work"}

everything = sorted(Path(".").rglob("*.sv"))
wanted = sorted(p for p in everything if not (SKIP & set(p.parts)))

print("discovered:", len(everything))
for p in everything:
    print("   ", p)
print()
print("kept      :", len(wanted))
for p in wanted:
    print("   ", p)

discovered: 4
    rtl/alu.sv
    rtl/core/fifo.sv
    rtl/generated/regs.sv
    third_party/vip/axi.sv

kept      : 2
    rtl/alu.sv
    rtl/core/fifo.sv

Two things about that filter are deliberate.

SKIP is a named set, declared once at the top. The exclusion policy is now a value a reader can find and a reviewer can question, rather than a chain of and not conditions grown by accretion inside a loop. When somebody asks "do we compile the vendor IP?", the answer is one line.

SKIP & set(p.parts) is set intersection (Chapter 7.4): it is truthy when the path passes through any excluded directory. The alternative — "generated" not in p.parts and "third_party" not in p.parts and ... — grows a clause per entry and is where the fifth exclusion gets forgotten.

3. Filtering Walks Everything First

The filter is correct and it is not free. rglob has to visit a path before the comprehension can discard it:

from pathlib import Path

for d in ["rtl/core", "rtl/generated", ".git/objects", "third_party/vip"]:
    Path(d).mkdir(parents=True)
for f in ["rtl/alu.sv", "rtl/core/fifo.sv", "rtl/generated/regs.sv",
          ".git/objects/blob.sv", "third_party/vip/axi.sv"]:
    Path(f).write_text("")

SKIP = {"generated", "third_party", ".git"}

examined = 0
kept = []
for p in Path(".").rglob("*.sv"):
    examined += 1
    if not (SKIP & set(p.parts)):
        kept.append(str(p))

print("paths examined:", examined)
print("paths kept    :", len(kept))
print("kept          :", sorted(kept))

paths examined: 5
paths kept    : 2
kept          : ['rtl/alu.sv', 'rtl/core/fifo.sv']

Five examined to keep two. On this toy tree that is irrelevant. On a real checkout, .git/objects alone contains thousands of files, and third_party/ can contain an entire vendor source tree — so a discovery that walks them and then throws the results away does most of its work for nothing.

4. Pruning Refuses to Enter

os.walk yields one directory at a time and lets you edit the list of subdirectories it is about to descend into:

import os
from pathlib import Path

for d in ["rtl/core", "rtl/generated", ".git/objects", "third_party/vip"]:
    Path(d).mkdir(parents=True)
for f in ["rtl/alu.sv", "rtl/core/fifo.sv", "rtl/generated/regs.sv",
          ".git/objects/blob.sv", "third_party/vip/axi.sv"]:
    Path(f).write_text("")

SKIP = {"generated", "third_party", ".git"}

examined = 0
kept = []
for dirpath, dirnames, filenames in os.walk("."):
    dirnames[:] = [d for d in dirnames if d not in SKIP]
    for name in filenames:
        examined += 1
        if name.endswith(".sv"):
            kept.append(os.path.join(dirpath, name))

print("files examined:", examined)
print("files kept    :", len(kept))
print("kept          :", sorted(kept))

files examined: 3
files kept    : 2
kept          : ['./rtl/alu.sv', './rtl/core/fifo.sv']

Three examined instead of five, for the same answer. The excluded directories were never entered, so their contents were never listed.

os.walk yields a three-part tuple per directory: where it is, the subdirectories in it, and the files in it. The result paths come out with a leading ./ because the walk started at . — convert with Path() when you want them clean.

The scaling is the point. Filtering costs O(everything in the tree); pruning costs O(what you kept). For a tree where the excluded part is small, use the filter — it is one readable line. For one containing .git, a vendor drop or a previous run's output, prune.

5. The Idiom That Fails Silently

dirnames[:] = [...] has a slice on the left, and it is not optional:

import os
from pathlib import Path

for d in ["rtl/generated"]:
    Path(d).mkdir(parents=True)
Path("rtl/alu.sv").write_text("")
Path("rtl/generated/regs.sv").write_text("")

SKIP = {"generated"}


def walk(prune_correctly):
    found = []
    for dirpath, dirnames, filenames in os.walk("rtl"):
        if prune_correctly:
            dirnames[:] = [d for d in dirnames if d not in SKIP]
        else:
            dirnames = [d for d in dirnames if d not in SKIP]
        for name in filenames:
            if name.endswith(".sv"):
                found.append(os.path.join(dirpath, name))
    return sorted(found)


print("with dirnames[:] =", walk(True))
print("with dirnames   =", walk(False))

with dirnames[:] = ['rtl/alu.sv']
with dirnames   = ['rtl/alu.sv', 'rtl/generated/regs.sv']

The second form did nothing. dirnames = [...] rebinds the local name to a new list; os.walk is still holding the original list object and descends into everything in it. Only mutating the list in place reaches the walker.

This is Chapter 6.6's aliasing fact with a consequence: the two statements look equivalent, one works, and the failure is silent — the walk simply descends anyway and the filter appears not to be applied. If pruning seems to have no effect, this is why.

6. Matching a Directory Name Is Slightly Too Broad

The honest limit on in p.parts.

Testing membership in parts excludes a directory with that name anywhere in the path, at any depth. That is usually exactly right — a generated directory is generated wherever it appears. Occasionally it is too broad:

from pathlib import Path

RTL = Path("rtl")
paths = [
    RTL / "alu.sv",
    RTL / "generated" / "regs.sv",
    RTL / "generated_checks" / "assert.sv",
    RTL / "core" / "generated" / "mux.sv",
]

print("by parts membership:")
for p in paths:
    print(f"  {str(p):<36} skipped: {'generated' in p.parts}")

print()
print("by exact top-level directory:")
for p in paths:
    rel = p.relative_to(RTL)
    print(f"  {str(p):<36} skipped: {rel.parts[0] == 'generated'}")

by parts membership:
  rtl/alu.sv                           skipped: False
  rtl/generated/regs.sv                skipped: True
  rtl/generated_checks/assert.sv       skipped: False
  rtl/core/generated/mux.sv            skipped: True

by exact top-level directory:
  rtl/alu.sv                           skipped: False
  rtl/generated/regs.sv                skipped: True
  rtl/generated_checks/assert.sv       skipped: False
  rtl/core/generated/mux.sv            skipped: False

The two policies differ on the last row. parts membership excludes a nested generated/ anywhere; the relative_to version excludes only the one directly under rtl/.

Neither is correct in general — they are different policies, and the point is to know which one you have written. The nested case is usually wanted (a generated directory is generated wherever it is), which is why parts is the default. When it is not, relative_to plus a prefix test says so precisely.

Note also that generated_checks is kept by both, which is the trap Chapter 18.3 Section 4 warned about: "generated" in str(p) would have excluded it, and it is a hand-written directory.

7. Predict, Run, Observe

import os
from pathlib import Path

Path("a/b/c").mkdir(parents=True)
Path("a/skip/d").mkdir(parents=True)
for f in ["a/top.sv", "a/b/mid.sv", "a/b/c/deep.sv", "a/skip/d/no.sv"]:
    Path(f).write_text("")

dirs_seen = []
files_seen = 0
for dirpath, dirnames, filenames in os.walk("a"):
    dirs_seen.append(dirpath)
    dirnames[:] = [d for d in dirnames if d != "skip"]
    files_seen += len(filenames)

print("A:", sorted(dirs_seen))
print("B:", files_seen)
print("C:", len(sorted(Path("a").rglob("*.sv"))))
print("D:", sorted(str(p) for p in Path("a").rglob("*.sv") if "skip" not in p.parts))

A: ['a', 'a/b', 'a/b/c']
B: 3
C: 4
D: ['a/b/c/deep.sv', 'a/b/mid.sv', 'a/top.sv']

A shows a/skip was never visited — the pruning happened before the walker descended, so it does not appear in the list of directories seen at all.

B is 3 against C's 4. The walk counted three files and rglob found four, and the difference is the one inside the pruned directory. Same final answer, different amount of work.

The pruning happens after dirpath is recorded, which is why a appears in A — you prune the directories below the one you are currently in, not the current one. Excluding the starting directory is not something os.walk can do for you.

D matches B's result by filtering instead, which is the one-line version when the tree is small enough not to care.

8. Exercises

Exercise 1 — a skip set. Build a tree with three directories worth excluding. Write the filter with a named set and confirm the result.

Exercise 2 — the intersection. Rewrite the same filter as a chain of and not conditions. Say which you would rather maintain when a fourth exclusion arrives.

Exercise 3 — count the work. Count paths examined by rglob and by a pruning walk on the same tree. Report both numbers.

Exercise 4 — the silent failure. Write the pruning loop with dirnames = [...] and confirm it has no effect. Then fix it and explain why in one sentence.

Exercise 5 — real scale. Run a filtering discovery over a checkout that contains .git. Time it, then prune .git and time it again.

Exercise 6 — two policies. Create generated/ and core/generated/ and show that parts membership and the relative_to test disagree. Say which you want.

Exercise 7 — the substring trap. Add a generated_checks/ directory and show that in str(p) excludes it while in parts does not.

Exercise 8 — prune the root. Try to exclude the starting directory itself with os.walk. Say what you have to do instead.

9. Summary

• A real tree contains several categories to exclude, and they arrive one at a time.
• Declare the exclusions as a named set, so the policy is a value a reviewer can question.
• SKIP & set(p.parts) is truthy when the path passes through any excluded directory, and does not grow a clause per entry.
• Filtering visits everything and discards after: cost is O(the whole tree).
• Pruning refuses to descend: cost is O(what you kept).
• Use the filter when the excluded part is small; prune when it contains .git, a vendor drop or previous run output.
• dirnames[:] = [...] prunes; dirnames = [...] does nothing — only in-place mutation reaches the walker, and the failure is silent.
• os.walk yields where it is, the subdirectories below it, and the files in it, and you prune the subdirectories before it descends.
• You cannot prune the starting directory — the walk has already entered it.
• in p.parts excludes a name at any depth; relative_to plus a prefix test excludes only the top-level one, and they are different policies.

The next chapter turns a discovered, filtered set of sources into the file a simulator will actually read.