dagolden / Path-Iterator-Rule / 23

94%

Pull #22

travis-ci

in breadth-first traversals, don't scan a directory  until its contents are examined

In a breadth-first traversal a directory's children are determined
directly after visiting the directory entry, even if they are not the
next entries to be visited.  If the traversal were to be aborted
prior to visting the directory's children, then scanning the directory
is a waste.  For example, if the directory structure is

p/a
p/a/1
p/b
p/b/2
p/c
p/c/3

The current code results in a visit/find-children pattern of:

visit: .
find children: .
visit: ./p
find children: ./p
visit: ./p/a
find children: ./p/a
visit: ./p/b
find children: ./p/b
visit: ./p/c
find children: ./p/c
visit: ./p/a/1
visit: ./p/b/2
visit: ./p/c/3

Note that the children of all of p/a, p/b, and p/c are determined prior to
descending into p/a.  If the search is aborted whle in p/a, the scans of p/b and p/c are wasted.

This patch delays the scanning of a directory until its children are
requested.  This results in a visit/find-children pattern of

visit: .
find children: .
visit: ./p
find children: ./p
visit: ./p/a
visit: ./p/b
visit: ./p/c
find children: ./p/a
visit: ./p/a/1
find children: ./p/b
visit: ./p/b/2
find children: ./p/c
visit: ./p/c/3

which ensures that if the search is aborted at ./p/a/1, the
unnecessary scanning of ./p/b and ./p/c is avoided.

It does this by pushing closures which perform directory scans onto
the queue of entries to be examined. The closures are evaluated when
they are the next-in-line elements to be examined, thus preventing
premature effort.

14 of 14 new or added lines in 1 file covered. (100.0%)

220 of 235 relevant lines covered (93.62%)

154.4 hits per line