1// Copyright 2017 Google Inc. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package finder
16
17import (
18	"fmt"
19	"io/ioutil"
20	"log"
21	"os"
22	"path/filepath"
23	"sort"
24	"strings"
25	"testing"
26
27	"android/soong/finder/fs"
28)
29
30// some utils for tests to use
31func newFs() *fs.MockFs {
32	return fs.NewMockFs(map[string][]byte{})
33}
34
35func newFinder(t *testing.T, filesystem *fs.MockFs, cacheParams CacheParams) *Finder {
36	return newFinderWithNumThreads(t, filesystem, cacheParams, 2)
37}
38
39func newFinderWithNumThreads(t *testing.T, filesystem *fs.MockFs, cacheParams CacheParams, numThreads int) *Finder {
40	f, err := newFinderAndErr(t, filesystem, cacheParams, numThreads)
41	if err != nil {
42		t.Fatal(err.Error())
43	}
44	return f
45}
46
47func newFinderAndErr(t *testing.T, filesystem *fs.MockFs, cacheParams CacheParams, numThreads int) (*Finder, error) {
48	cachePath := "/finder/finder-db"
49	cacheDir := filepath.Dir(cachePath)
50	filesystem.MkDirs(cacheDir)
51	if cacheParams.WorkingDirectory == "" {
52		cacheParams.WorkingDirectory = "/cwd"
53	}
54
55	logger := log.New(ioutil.Discard, "", 0)
56	f, err := newImpl(cacheParams, filesystem, logger, cachePath, numThreads)
57	return f, err
58}
59
60func finderWithSameParams(t *testing.T, original *Finder) *Finder {
61	f, err := finderAndErrorWithSameParams(t, original)
62	if err != nil {
63		t.Fatal(err.Error())
64	}
65	return f
66}
67
68func finderAndErrorWithSameParams(t *testing.T, original *Finder) (*Finder, error) {
69	f, err := newImpl(
70		original.cacheMetadata.Config.CacheParams,
71		original.filesystem,
72		original.logger,
73		original.DbPath,
74		original.numDbLoadingThreads,
75	)
76	return f, err
77}
78
79// runSimpleTests creates a few files, searches for findme.txt, and checks for the expected matches
80func runSimpleTest(t *testing.T, existentPaths []string, expectedMatches []string) {
81	filesystem := newFs()
82	root := "/tmp"
83	filesystem.MkDirs(root)
84	for _, path := range existentPaths {
85		fs.Create(t, filepath.Join(root, path), filesystem)
86	}
87
88	finder := newFinder(t,
89		filesystem,
90		CacheParams{
91			"/cwd",
92			[]string{root},
93			nil,
94			nil,
95			[]string{"findme.txt", "skipme.txt"},
96			nil,
97		},
98	)
99	defer finder.Shutdown()
100
101	foundPaths := finder.FindNamedAt(root, "findme.txt")
102	absoluteMatches := []string{}
103	for i := range expectedMatches {
104		absoluteMatches = append(absoluteMatches, filepath.Join(root, expectedMatches[i]))
105	}
106	fs.AssertSameResponse(t, foundPaths, absoluteMatches)
107}
108
109// runTestWithSuffixes creates a few files, searches for findme.txt or any file
110// with suffix `.findme_ext` and checks for the expected matches
111func runTestWithSuffixes(t *testing.T, existentPaths []string, expectedMatches []string) {
112	filesystem := newFs()
113	root := "/tmp"
114	filesystem.MkDirs(root)
115	for _, path := range existentPaths {
116		fs.Create(t, filepath.Join(root, path), filesystem)
117	}
118
119	finder := newFinder(t,
120		filesystem,
121		CacheParams{
122			"/cwd",
123			[]string{root},
124			nil,
125			nil,
126			[]string{"findme.txt", "skipme.txt"},
127			[]string{".findme_ext"},
128		},
129	)
130	defer finder.Shutdown()
131
132	foundPaths := finder.FindMatching(root,
133		func(entries DirEntries) (dirs []string, files []string) {
134			matches := []string{}
135			for _, foundName := range entries.FileNames {
136				if foundName == "findme.txt" || strings.HasSuffix(foundName, ".findme_ext") {
137					matches = append(matches, foundName)
138				}
139			}
140			return entries.DirNames, matches
141		})
142	absoluteMatches := []string{}
143	for i := range expectedMatches {
144		absoluteMatches = append(absoluteMatches, filepath.Join(root, expectedMatches[i]))
145	}
146	fs.AssertSameResponse(t, foundPaths, absoluteMatches)
147}
148
149// testAgainstSeveralThreadcounts runs the given test for each threadcount that we care to test
150func testAgainstSeveralThreadcounts(t *testing.T, tester func(t *testing.T, numThreads int)) {
151	// test singlethreaded, multithreaded, and also using the same number of threads as
152	// will be used on the current system
153	threadCounts := []int{1, 2, defaultNumThreads}
154	for _, numThreads := range threadCounts {
155		testName := fmt.Sprintf("%v threads", numThreads)
156		// store numThreads in a new variable to prevent numThreads from changing in each loop
157		localNumThreads := numThreads
158		t.Run(testName, func(t *testing.T) {
159			tester(t, localNumThreads)
160		})
161	}
162}
163
164// end of utils, start of individual tests
165
166func TestSingleFile(t *testing.T) {
167	runSimpleTest(t,
168		[]string{"findme.txt"},
169		[]string{"findme.txt"},
170	)
171}
172
173func TestIncludeFiles(t *testing.T) {
174	runSimpleTest(t,
175		[]string{"findme.txt", "skipme.txt"},
176		[]string{"findme.txt"},
177	)
178}
179
180func TestIncludeFilesAndSuffixes(t *testing.T) {
181	runTestWithSuffixes(t,
182		[]string{"findme.txt", "skipme.txt", "alsome.findme_ext"},
183		[]string{"findme.txt", "alsome.findme_ext"},
184	)
185}
186
187func TestNestedDirectories(t *testing.T) {
188	runSimpleTest(t,
189		[]string{"findme.txt", "skipme.txt", "subdir/findme.txt", "subdir/skipme.txt"},
190		[]string{"findme.txt", "subdir/findme.txt"},
191	)
192}
193
194func TestNestedDirectoriesWithSuffixes(t *testing.T) {
195	runTestWithSuffixes(t,
196		[]string{"findme.txt", "skipme.txt", "subdir/findme.txt", "subdir/skipme.txt", "subdir/alsome.findme_ext"},
197		[]string{"findme.txt", "subdir/findme.txt", "subdir/alsome.findme_ext"},
198	)
199}
200
201func TestEmptyDirectory(t *testing.T) {
202	runSimpleTest(t,
203		[]string{},
204		[]string{},
205	)
206}
207
208func TestEmptyPath(t *testing.T) {
209	filesystem := newFs()
210	root := "/tmp"
211	fs.Create(t, filepath.Join(root, "findme.txt"), filesystem)
212
213	finder := newFinder(
214		t,
215		filesystem,
216		CacheParams{
217			RootDirs:     []string{root},
218			IncludeFiles: []string{"findme.txt", "skipme.txt"},
219		},
220	)
221	defer finder.Shutdown()
222
223	foundPaths := finder.FindNamedAt("", "findme.txt")
224
225	fs.AssertSameResponse(t, foundPaths, []string{})
226}
227
228func TestFilesystemRoot(t *testing.T) {
229
230	testWithNumThreads := func(t *testing.T, numThreads int) {
231		filesystem := newFs()
232		root := "/"
233		createdPath := "/findme.txt"
234		fs.Create(t, createdPath, filesystem)
235
236		finder := newFinderWithNumThreads(
237			t,
238			filesystem,
239			CacheParams{
240				RootDirs:     []string{root},
241				IncludeFiles: []string{"findme.txt", "skipme.txt"},
242			},
243			numThreads,
244		)
245		defer finder.Shutdown()
246
247		foundPaths := finder.FindNamedAt(root, "findme.txt")
248
249		fs.AssertSameResponse(t, foundPaths, []string{createdPath})
250	}
251
252	testAgainstSeveralThreadcounts(t, testWithNumThreads)
253}
254
255func TestNonexistentDir(t *testing.T) {
256	filesystem := newFs()
257	fs.Create(t, "/tmp/findme.txt", filesystem)
258
259	_, err := newFinderAndErr(
260		t,
261		filesystem,
262		CacheParams{
263			RootDirs:     []string{"/tmp/IDontExist"},
264			IncludeFiles: []string{"findme.txt", "skipme.txt"},
265		},
266		1,
267	)
268	if err == nil {
269		t.Fatal("Did not fail when given a nonexistent root directory")
270	}
271}
272
273func TestExcludeDirs(t *testing.T) {
274	filesystem := newFs()
275	fs.Create(t, "/tmp/exclude/findme.txt", filesystem)
276	fs.Create(t, "/tmp/exclude/subdir/findme.txt", filesystem)
277	fs.Create(t, "/tmp/subdir/exclude/findme.txt", filesystem)
278	fs.Create(t, "/tmp/subdir/subdir/findme.txt", filesystem)
279	fs.Create(t, "/tmp/subdir/findme.txt", filesystem)
280	fs.Create(t, "/tmp/findme.txt", filesystem)
281
282	finder := newFinder(
283		t,
284		filesystem,
285		CacheParams{
286			RootDirs:     []string{"/tmp"},
287			ExcludeDirs:  []string{"exclude"},
288			IncludeFiles: []string{"findme.txt", "skipme.txt"},
289		},
290	)
291	defer finder.Shutdown()
292
293	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
294
295	fs.AssertSameResponse(t, foundPaths,
296		[]string{"/tmp/findme.txt",
297			"/tmp/subdir/findme.txt",
298			"/tmp/subdir/subdir/findme.txt"})
299}
300
301func TestPruneFiles(t *testing.T) {
302	filesystem := newFs()
303	fs.Create(t, "/tmp/out/findme.txt", filesystem)
304	fs.Create(t, "/tmp/out/.ignore-out-dir", filesystem)
305	fs.Create(t, "/tmp/out/child/findme.txt", filesystem)
306
307	fs.Create(t, "/tmp/out2/.ignore-out-dir", filesystem)
308	fs.Create(t, "/tmp/out2/sub/findme.txt", filesystem)
309
310	fs.Create(t, "/tmp/findme.txt", filesystem)
311	fs.Create(t, "/tmp/include/findme.txt", filesystem)
312
313	finder := newFinder(
314		t,
315		filesystem,
316		CacheParams{
317			RootDirs:     []string{"/tmp"},
318			PruneFiles:   []string{".ignore-out-dir"},
319			IncludeFiles: []string{"findme.txt"},
320		},
321	)
322	defer finder.Shutdown()
323
324	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
325
326	fs.AssertSameResponse(t, foundPaths,
327		[]string{"/tmp/findme.txt",
328			"/tmp/include/findme.txt"})
329}
330
331// TestRootDir tests that the value of RootDirs is used
332// tests of the filesystem root are in TestFilesystemRoot
333func TestRootDir(t *testing.T) {
334	filesystem := newFs()
335	fs.Create(t, "/tmp/a/findme.txt", filesystem)
336	fs.Create(t, "/tmp/a/subdir/findme.txt", filesystem)
337	fs.Create(t, "/tmp/b/findme.txt", filesystem)
338	fs.Create(t, "/tmp/b/subdir/findme.txt", filesystem)
339
340	finder := newFinder(
341		t,
342		filesystem,
343		CacheParams{
344			RootDirs:     []string{"/tmp/a"},
345			IncludeFiles: []string{"findme.txt"},
346		},
347	)
348	defer finder.Shutdown()
349
350	foundPaths := finder.FindNamedAt("/tmp/a", "findme.txt")
351
352	fs.AssertSameResponse(t, foundPaths,
353		[]string{"/tmp/a/findme.txt",
354			"/tmp/a/subdir/findme.txt"})
355}
356
357func TestUncachedDir(t *testing.T) {
358	filesystem := newFs()
359	fs.Create(t, "/tmp/a/findme.txt", filesystem)
360	fs.Create(t, "/tmp/a/subdir/findme.txt", filesystem)
361	fs.Create(t, "/tmp/b/findme.txt", filesystem)
362	fs.Create(t, "/tmp/b/subdir/findme.txt", filesystem)
363
364	finder := newFinder(
365		t,
366		filesystem,
367		CacheParams{
368			RootDirs:     []string{"/tmp/b"},
369			IncludeFiles: []string{"findme.txt"},
370		},
371	)
372
373	foundPaths := finder.FindNamedAt("/tmp/a", "findme.txt")
374	// If the caller queries for a file that is in the cache, then computing the
375	// correct answer won't be fast, and it would be easy for the caller to
376	// fail to notice its slowness. Instead, we only ever search the cache for files
377	// to return, which enforces that we can determine which files will be
378	// interesting upfront.
379	fs.AssertSameResponse(t, foundPaths, []string{})
380
381	finder.Shutdown()
382}
383
384func TestSearchingForFilesExcludedFromCache(t *testing.T) {
385	// setup filesystem
386	filesystem := newFs()
387	fs.Create(t, "/tmp/findme.txt", filesystem)
388	fs.Create(t, "/tmp/a/findme.txt", filesystem)
389	fs.Create(t, "/tmp/a/misc.txt", filesystem)
390
391	// set up the finder and run it
392	finder := newFinder(
393		t,
394		filesystem,
395		CacheParams{
396			RootDirs:     []string{"/tmp"},
397			IncludeFiles: []string{"findme.txt"},
398		},
399	)
400	foundPaths := finder.FindNamedAt("/tmp", "misc.txt")
401	// If the caller queries for a file that is in the cache, then computing the
402	// correct answer won't be fast, and it would be easy for the caller to
403	// fail to notice its slowness. Instead, we only ever search the cache for files
404	// to return, which enforces that we can determine which files will be
405	// interesting upfront.
406	fs.AssertSameResponse(t, foundPaths, []string{})
407
408	finder.Shutdown()
409}
410
411func TestRelativeFilePaths(t *testing.T) {
412	filesystem := newFs()
413
414	fs.Create(t, "/tmp/ignore/hi.txt", filesystem)
415	fs.Create(t, "/tmp/include/hi.txt", filesystem)
416	fs.Create(t, "/cwd/hi.txt", filesystem)
417	fs.Create(t, "/cwd/a/hi.txt", filesystem)
418	fs.Create(t, "/cwd/a/a/hi.txt", filesystem)
419	fs.Create(t, "/rel/a/hi.txt", filesystem)
420
421	finder := newFinder(
422		t,
423		filesystem,
424		CacheParams{
425			RootDirs:     []string{"/cwd", "../rel", "/tmp/include"},
426			IncludeFiles: []string{"hi.txt"},
427		},
428	)
429	defer finder.Shutdown()
430
431	foundPaths := finder.FindNamedAt("a", "hi.txt")
432	fs.AssertSameResponse(t, foundPaths,
433		[]string{"a/hi.txt",
434			"a/a/hi.txt"})
435
436	foundPaths = finder.FindNamedAt("/tmp/include", "hi.txt")
437	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/include/hi.txt"})
438
439	foundPaths = finder.FindNamedAt(".", "hi.txt")
440	fs.AssertSameResponse(t, foundPaths,
441		[]string{"hi.txt",
442			"a/hi.txt",
443			"a/a/hi.txt"})
444
445	foundPaths = finder.FindNamedAt("/rel", "hi.txt")
446	fs.AssertSameResponse(t, foundPaths,
447		[]string{"/rel/a/hi.txt"})
448
449	foundPaths = finder.FindNamedAt("/tmp/include", "hi.txt")
450	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/include/hi.txt"})
451}
452
453// have to run this test with the race-detector (`go test -race src/android/soong/finder/*.go`)
454// for there to be much chance of the test actually detecting any error that may be present
455func TestRootDirsContainedInOtherRootDirs(t *testing.T) {
456	filesystem := newFs()
457
458	fs.Create(t, "/tmp/a/b/c/d/e/f/g/h/i/j/findme.txt", filesystem)
459
460	finder := newFinder(
461		t,
462		filesystem,
463		CacheParams{
464			RootDirs:     []string{"/", "/tmp/a/b/c", "/tmp/a/b/c/d/e/f", "/tmp/a/b/c/d/e/f/g/h/i"},
465			IncludeFiles: []string{"findme.txt"},
466		},
467	)
468	defer finder.Shutdown()
469
470	foundPaths := finder.FindNamedAt("/tmp/a", "findme.txt")
471
472	fs.AssertSameResponse(t, foundPaths,
473		[]string{"/tmp/a/b/c/d/e/f/g/h/i/j/findme.txt"})
474}
475
476func TestFindFirst(t *testing.T) {
477	filesystem := newFs()
478	fs.Create(t, "/tmp/a/hi.txt", filesystem)
479	fs.Create(t, "/tmp/b/hi.txt", filesystem)
480	fs.Create(t, "/tmp/b/a/hi.txt", filesystem)
481
482	finder := newFinder(
483		t,
484		filesystem,
485		CacheParams{
486			RootDirs:     []string{"/tmp"},
487			IncludeFiles: []string{"hi.txt"},
488		},
489	)
490	defer finder.Shutdown()
491
492	foundPaths := finder.FindFirstNamed("hi.txt")
493
494	fs.AssertSameResponse(t, foundPaths,
495		[]string{"/tmp/a/hi.txt",
496			"/tmp/b/hi.txt"},
497	)
498}
499
500func TestConcurrentFindSameDirectory(t *testing.T) {
501
502	testWithNumThreads := func(t *testing.T, numThreads int) {
503		filesystem := newFs()
504
505		// create a bunch of files and directories
506		paths := []string{}
507		for i := 0; i < 10; i++ {
508			parentDir := fmt.Sprintf("/tmp/%v", i)
509			for j := 0; j < 10; j++ {
510				filePath := filepath.Join(parentDir, fmt.Sprintf("%v/findme.txt", j))
511				paths = append(paths, filePath)
512			}
513		}
514		sort.Strings(paths)
515		for _, path := range paths {
516			fs.Create(t, path, filesystem)
517		}
518
519		// set up a finder
520		finder := newFinderWithNumThreads(
521			t,
522			filesystem,
523			CacheParams{
524				RootDirs:     []string{"/tmp"},
525				IncludeFiles: []string{"findme.txt"},
526			},
527			numThreads,
528		)
529		defer finder.Shutdown()
530
531		numTests := 20
532		results := make(chan []string, numTests)
533		// make several parallel calls to the finder
534		for i := 0; i < numTests; i++ {
535			go func() {
536				foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
537				results <- foundPaths
538			}()
539		}
540
541		// check that each response was correct
542		for i := 0; i < numTests; i++ {
543			foundPaths := <-results
544			fs.AssertSameResponse(t, foundPaths, paths)
545		}
546	}
547
548	testAgainstSeveralThreadcounts(t, testWithNumThreads)
549}
550
551func TestConcurrentFindDifferentDirectories(t *testing.T) {
552	filesystem := newFs()
553
554	// create a bunch of files and directories
555	allFiles := []string{}
556	numSubdirs := 10
557	rootPaths := []string{}
558	queryAnswers := [][]string{}
559	for i := 0; i < numSubdirs; i++ {
560		parentDir := fmt.Sprintf("/tmp/%v", i)
561		rootPaths = append(rootPaths, parentDir)
562		queryAnswers = append(queryAnswers, []string{})
563		for j := 0; j < 10; j++ {
564			filePath := filepath.Join(parentDir, fmt.Sprintf("%v/findme.txt", j))
565			queryAnswers[i] = append(queryAnswers[i], filePath)
566			allFiles = append(allFiles, filePath)
567		}
568		sort.Strings(queryAnswers[i])
569	}
570	sort.Strings(allFiles)
571	for _, path := range allFiles {
572		fs.Create(t, path, filesystem)
573	}
574
575	// set up a finder
576	finder := newFinder(
577		t,
578		filesystem,
579
580		CacheParams{
581			RootDirs:     []string{"/tmp"},
582			IncludeFiles: []string{"findme.txt"},
583		},
584	)
585	defer finder.Shutdown()
586
587	type testRun struct {
588		path           string
589		foundMatches   []string
590		correctMatches []string
591	}
592
593	numTests := numSubdirs + 1
594	testRuns := make(chan testRun, numTests)
595
596	searchAt := func(path string, correctMatches []string) {
597		foundPaths := finder.FindNamedAt(path, "findme.txt")
598		testRuns <- testRun{path, foundPaths, correctMatches}
599	}
600
601	// make several parallel calls to the finder
602	go searchAt("/tmp", allFiles)
603	for i := 0; i < len(rootPaths); i++ {
604		go searchAt(rootPaths[i], queryAnswers[i])
605	}
606
607	// check that each response was correct
608	for i := 0; i < numTests; i++ {
609		testRun := <-testRuns
610		fs.AssertSameResponse(t, testRun.foundMatches, testRun.correctMatches)
611	}
612}
613
614func TestStrangelyFormattedPaths(t *testing.T) {
615	filesystem := newFs()
616
617	fs.Create(t, "/tmp/findme.txt", filesystem)
618	fs.Create(t, "/tmp/a/findme.txt", filesystem)
619	fs.Create(t, "/tmp/b/findme.txt", filesystem)
620
621	finder := newFinder(
622		t,
623		filesystem,
624		CacheParams{
625			RootDirs:     []string{"//tmp//a//.."},
626			IncludeFiles: []string{"findme.txt"},
627		},
628	)
629	defer finder.Shutdown()
630
631	foundPaths := finder.FindNamedAt("//tmp//a//..", "findme.txt")
632
633	fs.AssertSameResponse(t, foundPaths,
634		[]string{"/tmp/a/findme.txt",
635			"/tmp/b/findme.txt",
636			"/tmp/findme.txt"})
637}
638
639func TestCorruptedCacheHeader(t *testing.T) {
640	filesystem := newFs()
641
642	fs.Create(t, "/tmp/findme.txt", filesystem)
643	fs.Create(t, "/tmp/a/findme.txt", filesystem)
644	fs.Write(t, "/finder/finder-db", "sample header", filesystem)
645
646	finder := newFinder(
647		t,
648		filesystem,
649		CacheParams{
650			RootDirs:     []string{"/tmp"},
651			IncludeFiles: []string{"findme.txt"},
652		},
653	)
654	defer finder.Shutdown()
655
656	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
657
658	fs.AssertSameResponse(t, foundPaths,
659		[]string{"/tmp/a/findme.txt",
660			"/tmp/findme.txt"})
661}
662
663func TestCanUseCache(t *testing.T) {
664	// setup filesystem
665	filesystem := newFs()
666	fs.Create(t, "/tmp/findme.txt", filesystem)
667	fs.Create(t, "/tmp/a/findme.txt", filesystem)
668
669	// run the first finder
670	finder := newFinder(
671		t,
672		filesystem,
673		CacheParams{
674			RootDirs:     []string{"/tmp"},
675			IncludeFiles: []string{"findme.txt"},
676		},
677	)
678	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
679	// check the response of the first finder
680	correctResponse := []string{"/tmp/a/findme.txt",
681		"/tmp/findme.txt"}
682	fs.AssertSameResponse(t, foundPaths, correctResponse)
683	finder.Shutdown()
684
685	// check results
686	cacheText := fs.Read(t, finder.DbPath, filesystem)
687	if len(cacheText) < 1 {
688		t.Fatalf("saved cache db is empty\n")
689	}
690	if len(filesystem.StatCalls) == 0 {
691		t.Fatal("No Stat calls recorded by mock filesystem")
692	}
693	if len(filesystem.ReadDirCalls) == 0 {
694		t.Fatal("No ReadDir calls recorded by filesystem")
695	}
696	statCalls := filesystem.StatCalls
697	filesystem.ClearMetrics()
698
699	// run the second finder
700	finder2 := finderWithSameParams(t, finder)
701	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
702	// check results
703	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{})
704	fs.AssertSameReadDirCalls(t, filesystem.StatCalls, statCalls)
705
706	finder2.Shutdown()
707}
708
709func TestCorruptedCacheBody(t *testing.T) {
710	// setup filesystem
711	filesystem := newFs()
712	fs.Create(t, "/tmp/findme.txt", filesystem)
713	fs.Create(t, "/tmp/a/findme.txt", filesystem)
714
715	// run the first finder
716	finder := newFinder(
717		t,
718		filesystem,
719		CacheParams{
720			RootDirs:     []string{"/tmp"},
721			IncludeFiles: []string{"findme.txt"},
722		},
723	)
724	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
725	finder.Shutdown()
726
727	// check the response of the first finder
728	correctResponse := []string{"/tmp/a/findme.txt",
729		"/tmp/findme.txt"}
730	fs.AssertSameResponse(t, foundPaths, correctResponse)
731	numStatCalls := len(filesystem.StatCalls)
732	numReadDirCalls := len(filesystem.ReadDirCalls)
733
734	// load the cache file, corrupt it, and save it
735	cacheReader, err := filesystem.Open(finder.DbPath)
736	if err != nil {
737		t.Fatal(err)
738	}
739	cacheData, err := ioutil.ReadAll(cacheReader)
740	if err != nil {
741		t.Fatal(err)
742	}
743	cacheData = append(cacheData, []byte("DontMindMe")...)
744	filesystem.WriteFile(finder.DbPath, cacheData, 0777)
745	filesystem.ClearMetrics()
746
747	// run the second finder
748	finder2 := finderWithSameParams(t, finder)
749	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
750	// check results
751	fs.AssertSameResponse(t, foundPaths, correctResponse)
752	numNewStatCalls := len(filesystem.StatCalls)
753	numNewReadDirCalls := len(filesystem.ReadDirCalls)
754	// It's permissable to make more Stat calls with a corrupted cache because
755	// the Finder may restart once it detects corruption.
756	// However, it may have already issued many Stat calls.
757	// Because a corrupted db is not expected to be a common (or even a supported case),
758	// we don't care to optimize it and don't cache the already-issued Stat calls
759	if numNewReadDirCalls < numReadDirCalls {
760		t.Fatalf(
761			"Finder made fewer ReadDir calls with a corrupted cache (%v calls) than with no cache"+
762				" (%v calls)",
763			numNewReadDirCalls, numReadDirCalls)
764	}
765	if numNewStatCalls < numStatCalls {
766		t.Fatalf(
767			"Finder made fewer Stat calls with a corrupted cache (%v calls) than with no cache (%v calls)",
768			numNewStatCalls, numStatCalls)
769	}
770	finder2.Shutdown()
771}
772
773func TestStatCalls(t *testing.T) {
774	// setup filesystem
775	filesystem := newFs()
776	fs.Create(t, "/tmp/a/findme.txt", filesystem)
777
778	// run finder
779	finder := newFinder(
780		t,
781		filesystem,
782		CacheParams{
783			RootDirs:     []string{"/tmp"},
784			IncludeFiles: []string{"findme.txt"},
785		},
786	)
787	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
788	finder.Shutdown()
789
790	// check response
791	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/findme.txt"})
792	fs.AssertSameStatCalls(t, filesystem.StatCalls, []string{"/tmp", "/tmp/a"})
793	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp", "/tmp/a"})
794}
795
796func TestFileAdded(t *testing.T) {
797	// setup filesystem
798	filesystem := newFs()
799	fs.Create(t, "/tmp/ignoreme.txt", filesystem)
800	fs.Create(t, "/tmp/a/findme.txt", filesystem)
801	fs.Create(t, "/tmp/b/ignore.txt", filesystem)
802	fs.Create(t, "/tmp/b/c/nope.txt", filesystem)
803	fs.Create(t, "/tmp/b/c/d/irrelevant.txt", filesystem)
804
805	// run the first finder
806	finder := newFinder(
807		t,
808		filesystem,
809		CacheParams{
810			RootDirs:     []string{"/tmp"},
811			IncludeFiles: []string{"findme.txt"},
812		},
813	)
814	filesystem.Clock.Tick()
815	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
816	finder.Shutdown()
817	// check the response of the first finder
818	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/findme.txt"})
819
820	// modify the filesystem
821	filesystem.Clock.Tick()
822	fs.Create(t, "/tmp/b/c/findme.txt", filesystem)
823	filesystem.Clock.Tick()
824	filesystem.ClearMetrics()
825
826	// run the second finder
827	finder2 := finderWithSameParams(t, finder)
828	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
829
830	// check results
831	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/findme.txt", "/tmp/b/c/findme.txt"})
832	fs.AssertSameStatCalls(t, filesystem.StatCalls, []string{"/tmp", "/tmp/a", "/tmp/b", "/tmp/b/c", "/tmp/b/c/d"})
833	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp/b/c"})
834	finder2.Shutdown()
835
836}
837
838func TestDirectoriesAdded(t *testing.T) {
839	// setup filesystem
840	filesystem := newFs()
841	fs.Create(t, "/tmp/ignoreme.txt", filesystem)
842	fs.Create(t, "/tmp/a/findme.txt", filesystem)
843	fs.Create(t, "/tmp/b/ignore.txt", filesystem)
844	fs.Create(t, "/tmp/b/c/nope.txt", filesystem)
845	fs.Create(t, "/tmp/b/c/d/irrelevant.txt", filesystem)
846
847	// run the first finder
848	finder := newFinder(
849		t,
850		filesystem,
851		CacheParams{
852			RootDirs:     []string{"/tmp"},
853			IncludeFiles: []string{"findme.txt"},
854		},
855	)
856	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
857	finder.Shutdown()
858	// check the response of the first finder
859	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/findme.txt"})
860
861	// modify the filesystem
862	filesystem.Clock.Tick()
863	fs.Create(t, "/tmp/b/c/new/findme.txt", filesystem)
864	fs.Create(t, "/tmp/b/c/new/new2/findme.txt", filesystem)
865	fs.Create(t, "/tmp/b/c/new/new2/ignoreme.txt", filesystem)
866	filesystem.ClearMetrics()
867
868	// run the second finder
869	finder2 := finderWithSameParams(t, finder)
870	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
871
872	// check results
873	fs.AssertSameResponse(t, foundPaths,
874		[]string{"/tmp/a/findme.txt", "/tmp/b/c/new/findme.txt", "/tmp/b/c/new/new2/findme.txt"})
875	fs.AssertSameStatCalls(t, filesystem.StatCalls,
876		[]string{"/tmp", "/tmp/a", "/tmp/b", "/tmp/b/c", "/tmp/b/c/d", "/tmp/b/c/new", "/tmp/b/c/new/new2"})
877	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp/b/c", "/tmp/b/c/new", "/tmp/b/c/new/new2"})
878
879	finder2.Shutdown()
880}
881
882func TestDirectoryAndSubdirectoryBothUpdated(t *testing.T) {
883	// setup filesystem
884	filesystem := newFs()
885	fs.Create(t, "/tmp/hi1.txt", filesystem)
886	fs.Create(t, "/tmp/a/hi1.txt", filesystem)
887
888	// run the first finder
889	finder := newFinder(
890		t,
891		filesystem,
892		CacheParams{
893			RootDirs:     []string{"/tmp"},
894			IncludeFiles: []string{"hi1.txt", "hi2.txt"},
895		},
896	)
897	foundPaths := finder.FindNamedAt("/tmp", "hi1.txt")
898	finder.Shutdown()
899	// check the response of the first finder
900	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/hi1.txt", "/tmp/a/hi1.txt"})
901
902	// modify the filesystem
903	filesystem.Clock.Tick()
904	fs.Create(t, "/tmp/hi2.txt", filesystem)
905	fs.Create(t, "/tmp/a/hi2.txt", filesystem)
906	filesystem.ClearMetrics()
907
908	// run the second finder
909	finder2 := finderWithSameParams(t, finder)
910	foundPaths = finder2.FindAll()
911
912	// check results
913	fs.AssertSameResponse(t, foundPaths,
914		[]string{"/tmp/hi1.txt", "/tmp/hi2.txt", "/tmp/a/hi1.txt", "/tmp/a/hi2.txt"})
915	fs.AssertSameStatCalls(t, filesystem.StatCalls,
916		[]string{"/tmp", "/tmp/a"})
917	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp", "/tmp/a"})
918
919	finder2.Shutdown()
920}
921
922func TestFileDeleted(t *testing.T) {
923	// setup filesystem
924	filesystem := newFs()
925	fs.Create(t, "/tmp/ignoreme.txt", filesystem)
926	fs.Create(t, "/tmp/a/findme.txt", filesystem)
927	fs.Create(t, "/tmp/b/findme.txt", filesystem)
928	fs.Create(t, "/tmp/b/c/nope.txt", filesystem)
929	fs.Create(t, "/tmp/b/c/d/irrelevant.txt", filesystem)
930
931	// run the first finder
932	finder := newFinder(
933		t,
934		filesystem,
935		CacheParams{
936			RootDirs:     []string{"/tmp"},
937			IncludeFiles: []string{"findme.txt"},
938		},
939	)
940	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
941	finder.Shutdown()
942	// check the response of the first finder
943	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/findme.txt", "/tmp/b/findme.txt"})
944
945	// modify the filesystem
946	filesystem.Clock.Tick()
947	fs.Delete(t, "/tmp/b/findme.txt", filesystem)
948	filesystem.ClearMetrics()
949
950	// run the second finder
951	finder2 := finderWithSameParams(t, finder)
952	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
953
954	// check results
955	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/findme.txt"})
956	fs.AssertSameStatCalls(t, filesystem.StatCalls, []string{"/tmp", "/tmp/a", "/tmp/b", "/tmp/b/c", "/tmp/b/c/d"})
957	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp/b"})
958
959	finder2.Shutdown()
960}
961
962func TestDirectoriesDeleted(t *testing.T) {
963	// setup filesystem
964	filesystem := newFs()
965	fs.Create(t, "/tmp/findme.txt", filesystem)
966	fs.Create(t, "/tmp/a/findme.txt", filesystem)
967	fs.Create(t, "/tmp/a/1/findme.txt", filesystem)
968	fs.Create(t, "/tmp/a/1/2/findme.txt", filesystem)
969	fs.Create(t, "/tmp/b/findme.txt", filesystem)
970
971	// run the first finder
972	finder := newFinder(
973		t,
974		filesystem,
975		CacheParams{
976			RootDirs:     []string{"/tmp"},
977			IncludeFiles: []string{"findme.txt"},
978		},
979	)
980	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
981	finder.Shutdown()
982	// check the response of the first finder
983	fs.AssertSameResponse(t, foundPaths,
984		[]string{"/tmp/findme.txt",
985			"/tmp/a/findme.txt",
986			"/tmp/a/1/findme.txt",
987			"/tmp/a/1/2/findme.txt",
988			"/tmp/b/findme.txt"})
989
990	// modify the filesystem
991	filesystem.Clock.Tick()
992	fs.RemoveAll(t, "/tmp/a/1", filesystem)
993	filesystem.ClearMetrics()
994
995	// run the second finder
996	finder2 := finderWithSameParams(t, finder)
997	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
998
999	// check results
1000	fs.AssertSameResponse(t, foundPaths,
1001		[]string{"/tmp/findme.txt", "/tmp/a/findme.txt", "/tmp/b/findme.txt"})
1002	// Technically, we don't care whether /tmp/a/1/2 gets Statted or gets skipped
1003	// if the Finder detects the nonexistence of /tmp/a/1
1004	// However, when resuming from cache, we don't want the Finder to necessarily wait
1005	// to stat a directory until after statting its parent.
1006	// So here we just include /tmp/a/1/2 in the list.
1007	// The Finder is currently implemented to always restat every dir and
1008	// to not short-circuit due to nonexistence of parents (but it will remove
1009	// missing dirs from the cache for next time)
1010	fs.AssertSameStatCalls(t, filesystem.StatCalls,
1011		[]string{"/tmp", "/tmp/a", "/tmp/a/1", "/tmp/a/1/2", "/tmp/b"})
1012	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp/a"})
1013
1014	finder2.Shutdown()
1015}
1016
1017func TestDirectoriesMoved(t *testing.T) {
1018	// setup filesystem
1019	filesystem := newFs()
1020	fs.Create(t, "/tmp/findme.txt", filesystem)
1021	fs.Create(t, "/tmp/a/findme.txt", filesystem)
1022	fs.Create(t, "/tmp/a/1/findme.txt", filesystem)
1023	fs.Create(t, "/tmp/a/1/2/findme.txt", filesystem)
1024	fs.Create(t, "/tmp/b/findme.txt", filesystem)
1025
1026	// run the first finder
1027	finder := newFinder(
1028		t,
1029		filesystem,
1030		CacheParams{
1031			RootDirs:     []string{"/tmp"},
1032			IncludeFiles: []string{"findme.txt"},
1033		},
1034	)
1035	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
1036	finder.Shutdown()
1037	// check the response of the first finder
1038	fs.AssertSameResponse(t, foundPaths,
1039		[]string{"/tmp/findme.txt",
1040			"/tmp/a/findme.txt",
1041			"/tmp/a/1/findme.txt",
1042			"/tmp/a/1/2/findme.txt",
1043			"/tmp/b/findme.txt"})
1044
1045	// modify the filesystem
1046	filesystem.Clock.Tick()
1047	fs.Move(t, "/tmp/a", "/tmp/c", filesystem)
1048	filesystem.ClearMetrics()
1049
1050	// run the second finder
1051	finder2 := finderWithSameParams(t, finder)
1052	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
1053
1054	// check results
1055	fs.AssertSameResponse(t, foundPaths,
1056		[]string{"/tmp/findme.txt",
1057			"/tmp/b/findme.txt",
1058			"/tmp/c/findme.txt",
1059			"/tmp/c/1/findme.txt",
1060			"/tmp/c/1/2/findme.txt"})
1061	// Technically, we don't care whether /tmp/a/1/2 gets Statted or gets skipped
1062	// if the Finder detects the nonexistence of /tmp/a/1
1063	// However, when resuming from cache, we don't want the Finder to necessarily wait
1064	// to stat a directory until after statting its parent.
1065	// So here we just include /tmp/a/1/2 in the list.
1066	// The Finder is currently implemented to always restat every dir and
1067	// to not short-circuit due to nonexistence of parents (but it will remove
1068	// missing dirs from the cache for next time)
1069	fs.AssertSameStatCalls(t, filesystem.StatCalls,
1070		[]string{"/tmp", "/tmp/a", "/tmp/a/1", "/tmp/a/1/2", "/tmp/b", "/tmp/c", "/tmp/c/1", "/tmp/c/1/2"})
1071	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp", "/tmp/c", "/tmp/c/1", "/tmp/c/1/2"})
1072	finder2.Shutdown()
1073}
1074
1075func TestDirectoriesSwapped(t *testing.T) {
1076	// setup filesystem
1077	filesystem := newFs()
1078	fs.Create(t, "/tmp/findme.txt", filesystem)
1079	fs.Create(t, "/tmp/a/findme.txt", filesystem)
1080	fs.Create(t, "/tmp/a/1/findme.txt", filesystem)
1081	fs.Create(t, "/tmp/a/1/2/findme.txt", filesystem)
1082	fs.Create(t, "/tmp/b/findme.txt", filesystem)
1083
1084	// run the first finder
1085	finder := newFinder(
1086		t,
1087		filesystem,
1088		CacheParams{
1089			RootDirs:     []string{"/tmp"},
1090			IncludeFiles: []string{"findme.txt"},
1091		},
1092	)
1093	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
1094	finder.Shutdown()
1095	// check the response of the first finder
1096	fs.AssertSameResponse(t, foundPaths,
1097		[]string{"/tmp/findme.txt",
1098			"/tmp/a/findme.txt",
1099			"/tmp/a/1/findme.txt",
1100			"/tmp/a/1/2/findme.txt",
1101			"/tmp/b/findme.txt"})
1102
1103	// modify the filesystem
1104	filesystem.Clock.Tick()
1105	fs.Move(t, "/tmp/a", "/tmp/temp", filesystem)
1106	fs.Move(t, "/tmp/b", "/tmp/a", filesystem)
1107	fs.Move(t, "/tmp/temp", "/tmp/b", filesystem)
1108	filesystem.ClearMetrics()
1109
1110	// run the second finder
1111	finder2 := finderWithSameParams(t, finder)
1112	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
1113
1114	// check results
1115	fs.AssertSameResponse(t, foundPaths,
1116		[]string{"/tmp/findme.txt",
1117			"/tmp/a/findme.txt",
1118			"/tmp/b/findme.txt",
1119			"/tmp/b/1/findme.txt",
1120			"/tmp/b/1/2/findme.txt"})
1121	// Technically, we don't care whether /tmp/a/1/2 gets Statted or gets skipped
1122	// if the Finder detects the nonexistence of /tmp/a/1
1123	// However, when resuming from cache, we don't want the Finder to necessarily wait
1124	// to stat a directory until after statting its parent.
1125	// So here we just include /tmp/a/1/2 in the list.
1126	// The Finder is currently implemented to always restat every dir and
1127	// to not short-circuit due to nonexistence of parents (but it will remove
1128	// missing dirs from the cache for next time)
1129	fs.AssertSameStatCalls(t, filesystem.StatCalls,
1130		[]string{"/tmp", "/tmp/a", "/tmp/a/1", "/tmp/a/1/2", "/tmp/b", "/tmp/b/1", "/tmp/b/1/2"})
1131	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp", "/tmp/a", "/tmp/b", "/tmp/b/1", "/tmp/b/1/2"})
1132	finder2.Shutdown()
1133}
1134
1135// runFsReplacementTest tests a change modifying properties of the filesystem itself:
1136// runFsReplacementTest tests changing the user, the hostname, or the device number
1137// runFsReplacementTest is a helper method called by other tests
1138func runFsReplacementTest(t *testing.T, fs1 *fs.MockFs, fs2 *fs.MockFs) {
1139	// setup fs1
1140	fs.Create(t, "/tmp/findme.txt", fs1)
1141	fs.Create(t, "/tmp/a/findme.txt", fs1)
1142	fs.Create(t, "/tmp/a/a/findme.txt", fs1)
1143
1144	// setup fs2 to have the same directories but different files
1145	fs.Create(t, "/tmp/findme.txt", fs2)
1146	fs.Create(t, "/tmp/a/findme.txt", fs2)
1147	fs.Create(t, "/tmp/a/a/ignoreme.txt", fs2)
1148	fs.Create(t, "/tmp/a/b/findme.txt", fs2)
1149
1150	// run the first finder
1151	finder := newFinder(
1152		t,
1153		fs1,
1154		CacheParams{
1155			RootDirs:     []string{"/tmp"},
1156			IncludeFiles: []string{"findme.txt"},
1157		},
1158	)
1159	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
1160	finder.Shutdown()
1161	// check the response of the first finder
1162	fs.AssertSameResponse(t, foundPaths,
1163		[]string{"/tmp/findme.txt", "/tmp/a/findme.txt", "/tmp/a/a/findme.txt"})
1164
1165	// copy the cache data from the first filesystem to the second
1166	cacheContent := fs.Read(t, finder.DbPath, fs1)
1167	fs.Write(t, finder.DbPath, cacheContent, fs2)
1168
1169	// run the second finder, with the same config and same cache contents but a different filesystem
1170	finder2 := newFinder(
1171		t,
1172		fs2,
1173		CacheParams{
1174			RootDirs:     []string{"/tmp"},
1175			IncludeFiles: []string{"findme.txt"},
1176		},
1177	)
1178	foundPaths = finder2.FindNamedAt("/tmp", "findme.txt")
1179
1180	// check results
1181	fs.AssertSameResponse(t, foundPaths,
1182		[]string{"/tmp/findme.txt", "/tmp/a/findme.txt", "/tmp/a/b/findme.txt"})
1183	fs.AssertSameStatCalls(t, fs2.StatCalls,
1184		[]string{"/tmp", "/tmp/a", "/tmp/a/a", "/tmp/a/b"})
1185	fs.AssertSameReadDirCalls(t, fs2.ReadDirCalls,
1186		[]string{"/tmp", "/tmp/a", "/tmp/a/a", "/tmp/a/b"})
1187	finder2.Shutdown()
1188}
1189
1190func TestChangeOfDevice(t *testing.T) {
1191	fs1 := newFs()
1192	// not as fine-grained mounting controls as a real filesystem, but should be adequate
1193	fs1.SetDeviceNumber(0)
1194
1195	fs2 := newFs()
1196	fs2.SetDeviceNumber(1)
1197
1198	runFsReplacementTest(t, fs1, fs2)
1199}
1200
1201func TestChangeOfUserOrHost(t *testing.T) {
1202	fs1 := newFs()
1203	fs1.SetViewId("me@here")
1204
1205	fs2 := newFs()
1206	fs2.SetViewId("you@there")
1207
1208	runFsReplacementTest(t, fs1, fs2)
1209}
1210
1211func TestConsistentCacheOrdering(t *testing.T) {
1212	// setup filesystem
1213	filesystem := newFs()
1214	for i := 0; i < 5; i++ {
1215		fs.Create(t, fmt.Sprintf("/tmp/%v/findme.txt", i), filesystem)
1216	}
1217
1218	// run the first finder
1219	finder := newFinder(
1220		t,
1221		filesystem,
1222		CacheParams{
1223			RootDirs:     []string{"/tmp"},
1224			IncludeFiles: []string{"findme.txt"},
1225		},
1226	)
1227	finder.FindNamedAt("/tmp", "findme.txt")
1228	finder.Shutdown()
1229
1230	// read db file
1231	string1 := fs.Read(t, finder.DbPath, filesystem)
1232
1233	err := filesystem.Remove(finder.DbPath)
1234	if err != nil {
1235		t.Fatal(err)
1236	}
1237
1238	// run another finder
1239	finder2 := finderWithSameParams(t, finder)
1240	finder2.FindNamedAt("/tmp", "findme.txt")
1241	finder2.Shutdown()
1242
1243	string2 := fs.Read(t, finder.DbPath, filesystem)
1244
1245	if string1 != string2 {
1246		t.Errorf("Running Finder twice generated two dbs not having identical contents.\n"+
1247			"Content of first file:\n"+
1248			"\n"+
1249			"%v"+
1250			"\n"+
1251			"\n"+
1252			"Content of second file:\n"+
1253			"\n"+
1254			"%v\n"+
1255			"\n",
1256			string1,
1257			string2,
1258		)
1259	}
1260
1261}
1262
1263func TestNumSyscallsOfSecondFind(t *testing.T) {
1264	// setup filesystem
1265	filesystem := newFs()
1266	fs.Create(t, "/tmp/findme.txt", filesystem)
1267	fs.Create(t, "/tmp/a/findme.txt", filesystem)
1268	fs.Create(t, "/tmp/a/misc.txt", filesystem)
1269
1270	// set up the finder and run it once
1271	finder := newFinder(
1272		t,
1273		filesystem,
1274		CacheParams{
1275			RootDirs:     []string{"/tmp"},
1276			IncludeFiles: []string{"findme.txt"},
1277		},
1278	)
1279	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
1280	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/findme.txt", "/tmp/a/findme.txt"})
1281
1282	filesystem.ClearMetrics()
1283
1284	// run the finder again and confirm it doesn't check the filesystem
1285	refoundPaths := finder.FindNamedAt("/tmp", "findme.txt")
1286	fs.AssertSameResponse(t, refoundPaths, foundPaths)
1287	fs.AssertSameStatCalls(t, filesystem.StatCalls, []string{})
1288	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{})
1289
1290	finder.Shutdown()
1291}
1292
1293func TestChangingParamsOfSecondFind(t *testing.T) {
1294	// setup filesystem
1295	filesystem := newFs()
1296	fs.Create(t, "/tmp/findme.txt", filesystem)
1297	fs.Create(t, "/tmp/a/findme.txt", filesystem)
1298	fs.Create(t, "/tmp/a/metoo.txt", filesystem)
1299
1300	// set up the finder and run it once
1301	finder := newFinder(
1302		t,
1303		filesystem,
1304		CacheParams{
1305			RootDirs:     []string{"/tmp"},
1306			IncludeFiles: []string{"findme.txt", "metoo.txt"},
1307		},
1308	)
1309	foundPaths := finder.FindNamedAt("/tmp", "findme.txt")
1310	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/findme.txt", "/tmp/a/findme.txt"})
1311
1312	filesystem.ClearMetrics()
1313
1314	// run the finder again and confirm it gets the right answer without asking the filesystem
1315	refoundPaths := finder.FindNamedAt("/tmp", "metoo.txt")
1316	fs.AssertSameResponse(t, refoundPaths, []string{"/tmp/a/metoo.txt"})
1317	fs.AssertSameStatCalls(t, filesystem.StatCalls, []string{})
1318	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{})
1319
1320	finder.Shutdown()
1321}
1322
1323func TestSymlinkPointingToFile(t *testing.T) {
1324	// setup filesystem
1325	filesystem := newFs()
1326	fs.Create(t, "/tmp/a/hi.txt", filesystem)
1327	fs.Create(t, "/tmp/a/ignoreme.txt", filesystem)
1328	fs.Link(t, "/tmp/hi.txt", "a/hi.txt", filesystem)
1329	fs.Link(t, "/tmp/b/hi.txt", "../a/hi.txt", filesystem)
1330	fs.Link(t, "/tmp/c/hi.txt", "/tmp/hi.txt", filesystem)
1331	fs.Link(t, "/tmp/d/hi.txt", "../a/bye.txt", filesystem)
1332	fs.Link(t, "/tmp/d/bye.txt", "../a/hi.txt", filesystem)
1333	fs.Link(t, "/tmp/e/bye.txt", "../a/bye.txt", filesystem)
1334	fs.Link(t, "/tmp/f/hi.txt", "somethingThatDoesntExist", filesystem)
1335
1336	// set up the finder and run it once
1337	finder := newFinder(
1338		t,
1339		filesystem,
1340		CacheParams{
1341			RootDirs:     []string{"/tmp"},
1342			IncludeFiles: []string{"hi.txt"},
1343		},
1344	)
1345	foundPaths := finder.FindNamedAt("/tmp", "hi.txt")
1346	// should search based on the name of the link rather than the destination or validity of the link
1347	correctResponse := []string{
1348		"/tmp/a/hi.txt",
1349		"/tmp/hi.txt",
1350		"/tmp/b/hi.txt",
1351		"/tmp/c/hi.txt",
1352		"/tmp/d/hi.txt",
1353		"/tmp/f/hi.txt",
1354	}
1355	fs.AssertSameResponse(t, foundPaths, correctResponse)
1356
1357}
1358
1359func TestSymlinkPointingToDirectory(t *testing.T) {
1360	// setup filesystem
1361	filesystem := newFs()
1362	fs.Create(t, "/tmp/dir/hi.txt", filesystem)
1363	fs.Create(t, "/tmp/dir/ignoreme.txt", filesystem)
1364
1365	fs.Link(t, "/tmp/links/dir", "../dir", filesystem)
1366	fs.Link(t, "/tmp/links/link", "../dir", filesystem)
1367	fs.Link(t, "/tmp/links/hi.txt", "../dir", filesystem)
1368	fs.Link(t, "/tmp/links/broken", "nothingHere", filesystem)
1369	fs.Link(t, "/tmp/links/recursive", "recursive", filesystem)
1370
1371	// set up the finder and run it once
1372	finder := newFinder(
1373		t,
1374		filesystem,
1375		CacheParams{
1376			RootDirs:     []string{"/tmp"},
1377			IncludeFiles: []string{"hi.txt"},
1378		},
1379	)
1380
1381	foundPaths := finder.FindNamedAt("/tmp", "hi.txt")
1382
1383	// should completely ignore symlinks that point to directories
1384	correctResponse := []string{
1385		"/tmp/dir/hi.txt",
1386	}
1387	fs.AssertSameResponse(t, foundPaths, correctResponse)
1388
1389}
1390
1391// TestAddPruneFile confirms that adding a prune-file (into a directory for which we
1392// already had a cache) causes the directory to be ignored
1393func TestAddPruneFile(t *testing.T) {
1394	// setup filesystem
1395	filesystem := newFs()
1396	fs.Create(t, "/tmp/out/hi.txt", filesystem)
1397	fs.Create(t, "/tmp/out/a/hi.txt", filesystem)
1398	fs.Create(t, "/tmp/hi.txt", filesystem)
1399
1400	// do find
1401	finder := newFinder(
1402		t,
1403		filesystem,
1404		CacheParams{
1405			RootDirs:     []string{"/tmp"},
1406			PruneFiles:   []string{".ignore-out-dir"},
1407			IncludeFiles: []string{"hi.txt"},
1408		},
1409	)
1410
1411	foundPaths := finder.FindNamedAt("/tmp", "hi.txt")
1412
1413	// check result
1414	fs.AssertSameResponse(t, foundPaths,
1415		[]string{"/tmp/hi.txt",
1416			"/tmp/out/hi.txt",
1417			"/tmp/out/a/hi.txt"},
1418	)
1419	finder.Shutdown()
1420
1421	// modify filesystem
1422	filesystem.Clock.Tick()
1423	fs.Create(t, "/tmp/out/.ignore-out-dir", filesystem)
1424	// run another find and check its result
1425	finder2 := finderWithSameParams(t, finder)
1426	foundPaths = finder2.FindNamedAt("/tmp", "hi.txt")
1427	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/hi.txt"})
1428	finder2.Shutdown()
1429}
1430
1431func TestUpdatingDbIffChanged(t *testing.T) {
1432	// setup filesystem
1433	filesystem := newFs()
1434	fs.Create(t, "/tmp/a/hi.txt", filesystem)
1435	fs.Create(t, "/tmp/b/bye.txt", filesystem)
1436
1437	// run the first finder
1438	finder := newFinder(
1439		t,
1440		filesystem,
1441		CacheParams{
1442			RootDirs:     []string{"/tmp"},
1443			IncludeFiles: []string{"hi.txt"},
1444		},
1445	)
1446	filesystem.Clock.Tick()
1447	foundPaths := finder.FindAll()
1448	finder.Shutdown()
1449	// check results
1450	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/hi.txt"})
1451
1452	// modify the filesystem
1453	filesystem.Clock.Tick()
1454	fs.Create(t, "/tmp/b/hi.txt", filesystem)
1455	filesystem.Clock.Tick()
1456	filesystem.ClearMetrics()
1457
1458	// run the second finder
1459	finder2 := finderWithSameParams(t, finder)
1460	foundPaths = finder2.FindAll()
1461	finder2.Shutdown()
1462	// check results
1463	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/hi.txt", "/tmp/b/hi.txt"})
1464	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{"/tmp/b"})
1465	expectedDbWriteTime := filesystem.Clock.Time()
1466	actualDbWriteTime := fs.ModTime(t, finder2.DbPath, filesystem)
1467	if actualDbWriteTime != expectedDbWriteTime {
1468		t.Fatalf("Expected to write db at %v, actually wrote db at %v\n",
1469			expectedDbWriteTime, actualDbWriteTime)
1470	}
1471
1472	// reset metrics
1473	filesystem.ClearMetrics()
1474
1475	// run the third finder
1476	finder3 := finderWithSameParams(t, finder2)
1477	foundPaths = finder3.FindAll()
1478
1479	// check results
1480	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/hi.txt", "/tmp/b/hi.txt"})
1481	fs.AssertSameReadDirCalls(t, filesystem.ReadDirCalls, []string{})
1482	finder3.Shutdown()
1483	actualDbWriteTime = fs.ModTime(t, finder3.DbPath, filesystem)
1484	if actualDbWriteTime != expectedDbWriteTime {
1485		t.Fatalf("Re-wrote db even when contents did not change")
1486	}
1487
1488}
1489
1490func TestDirectoryNotPermitted(t *testing.T) {
1491	// setup filesystem
1492	filesystem := newFs()
1493	fs.Create(t, "/tmp/hi.txt", filesystem)
1494	fs.Create(t, "/tmp/a/hi.txt", filesystem)
1495	fs.Create(t, "/tmp/a/a/hi.txt", filesystem)
1496	fs.Create(t, "/tmp/b/hi.txt", filesystem)
1497
1498	// run the first finder
1499	finder := newFinder(
1500		t,
1501		filesystem,
1502		CacheParams{
1503			RootDirs:     []string{"/tmp"},
1504			IncludeFiles: []string{"hi.txt"},
1505		},
1506	)
1507	filesystem.Clock.Tick()
1508	foundPaths := finder.FindAll()
1509	finder.Shutdown()
1510	allPaths := []string{"/tmp/hi.txt", "/tmp/a/hi.txt", "/tmp/a/a/hi.txt", "/tmp/b/hi.txt"}
1511	// check results
1512	fs.AssertSameResponse(t, foundPaths, allPaths)
1513
1514	// modify the filesystem
1515	filesystem.Clock.Tick()
1516
1517	fs.SetReadable(t, "/tmp/a", false, filesystem)
1518	filesystem.Clock.Tick()
1519
1520	// run the second finder
1521	finder2 := finderWithSameParams(t, finder)
1522	foundPaths = finder2.FindAll()
1523	finder2.Shutdown()
1524	// check results
1525	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/hi.txt", "/tmp/b/hi.txt"})
1526
1527	// modify the filesystem back
1528	fs.SetReadable(t, "/tmp/a", true, filesystem)
1529
1530	// run the third finder
1531	finder3 := finderWithSameParams(t, finder2)
1532	foundPaths = finder3.FindAll()
1533	finder3.Shutdown()
1534	// check results
1535	fs.AssertSameResponse(t, foundPaths, allPaths)
1536}
1537
1538func TestFileNotPermitted(t *testing.T) {
1539	// setup filesystem
1540	filesystem := newFs()
1541	fs.Create(t, "/tmp/hi.txt", filesystem)
1542	fs.SetReadable(t, "/tmp/hi.txt", false, filesystem)
1543
1544	// run the first finder
1545	finder := newFinder(
1546		t,
1547		filesystem,
1548		CacheParams{
1549			RootDirs:     []string{"/tmp"},
1550			IncludeFiles: []string{"hi.txt"},
1551		},
1552	)
1553	filesystem.Clock.Tick()
1554	foundPaths := finder.FindAll()
1555	finder.Shutdown()
1556	// check results
1557	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/hi.txt"})
1558}
1559
1560func TestCacheEntryPathUnexpectedError(t *testing.T) {
1561	// setup filesystem
1562	filesystem := newFs()
1563	fs.Create(t, "/tmp/a/hi.txt", filesystem)
1564
1565	// run the first finder
1566	finder := newFinder(
1567		t,
1568		filesystem,
1569		CacheParams{
1570			RootDirs:     []string{"/tmp"},
1571			IncludeFiles: []string{"hi.txt"},
1572		},
1573	)
1574	filesystem.Clock.Tick()
1575	foundPaths := finder.FindAll()
1576	finder.Shutdown()
1577	// check results
1578	fs.AssertSameResponse(t, foundPaths, []string{"/tmp/a/hi.txt"})
1579
1580	// make the directory not readable
1581	fs.SetReadErr(t, "/tmp/a", os.ErrInvalid, filesystem)
1582
1583	// run the second finder
1584	_, err := finderAndErrorWithSameParams(t, finder)
1585	if err == nil {
1586		t.Fatal("Failed to detect unexpected filesystem error")
1587	}
1588}
1589