Import globbing from Soong

Add globbing with dependency checking to blueprint.  Calling
ModuleContext.GlobWithDeps or SingletonContext.GlobWithDeps will return
a list of files that match the globs, while also adding efficient
dependencies to rerun the primary builder if a file that matches the
glob is added or removed.

Also use the globbing support for optional_subdirs=, subdirs= and build=
lines in blueprints files.  The globbing slightly changes the behavior
of subname= lines, it no longer falls back to looking for a file called
"Blueprints".  Blueprint files that need to include a subdirectory with
a different name can use build= instead of subdir= to directly include
them.  The Blueprints file is updated to reset subname="Blueprints" in
case we want to include subdirectories inside blueprint and the primary
builder has changed the subname.

Also adds a new test directory that contains a simple primary builder
tree to test regeneration for globbing, and runs the tests in travis.

Change-Id: I83ce525fd11e11579cc58ba5308d01ca8eea7bc6
diff --git a/context.go b/context.go
index 48856cf..7e54150 100644
--- a/context.go
+++ b/context.go
@@ -25,6 +25,7 @@
 	"sort"
 	"strconv"
 	"strings"
+	"sync"
 	"sync/atomic"
 	"text/scanner"
 	"text/template"
@@ -105,6 +106,9 @@
 	renames      []rename
 	replacements []replace
 
+	globs    map[string]GlobPath
+	globLock sync.Mutex
+
 	fs fileSystem
 }
 
@@ -270,6 +274,7 @@
 		moduleNames:      make(map[string]*moduleGroup),
 		moduleInfo:       make(map[Module]*moduleInfo),
 		moduleNinjaNames: make(map[string]*moduleGroup),
+		globs:            make(map[string]GlobPath),
 		fs:               fs,
 	}
 
@@ -524,12 +529,11 @@
 // filename specifies the path to the Blueprints file.  These paths are used for
 // error reporting and for determining the module's directory.
 func (c *Context) parse(rootDir, filename string, r io.Reader,
-	scope *parser.Scope) (file *parser.File, subBlueprints []stringAndScope, deps []string,
-	errs []error) {
+	scope *parser.Scope) (file *parser.File, subBlueprints []stringAndScope, errs []error) {
 
 	relBlueprintsFile, err := filepath.Rel(rootDir, filename)
 	if err != nil {
-		return nil, nil, nil, []error{err}
+		return nil, nil, []error{err}
 	}
 
 	scope = parser.NewScope(scope)
@@ -550,7 +554,7 @@
 
 		// If there were any parse errors don't bother trying to interpret the
 		// result.
-		return nil, nil, nil, errs
+		return nil, nil, errs
 	}
 	file.Name = relBlueprintsFile
 
@@ -570,24 +574,28 @@
 	}
 
 	subBlueprintsName, _, err := getStringFromScope(scope, "subname")
+	if err != nil {
+		errs = append(errs, err)
+	}
+
+	if subBlueprintsName == "" {
+		subBlueprintsName = "Blueprints"
+	}
 
 	var blueprints []string
 
-	newBlueprints, newDeps, newErrs := c.findBuildBlueprints(filepath.Dir(filename), build, buildPos)
+	newBlueprints, newErrs := c.findBuildBlueprints(filepath.Dir(filename), build, buildPos)
 	blueprints = append(blueprints, newBlueprints...)
-	deps = append(deps, newDeps...)
 	errs = append(errs, newErrs...)
 
-	newBlueprints, newDeps, newErrs = c.findSubdirBlueprints(filepath.Dir(filename), subdirs, subdirsPos,
+	newBlueprints, newErrs = c.findSubdirBlueprints(filepath.Dir(filename), subdirs, subdirsPos,
 		subBlueprintsName, false)
 	blueprints = append(blueprints, newBlueprints...)
-	deps = append(deps, newDeps...)
 	errs = append(errs, newErrs...)
 
-	newBlueprints, newDeps, newErrs = c.findSubdirBlueprints(filepath.Dir(filename), optionalSubdirs,
+	newBlueprints, newErrs = c.findSubdirBlueprints(filepath.Dir(filename), optionalSubdirs,
 		optionalSubdirsPos, subBlueprintsName, true)
 	blueprints = append(blueprints, newBlueprints...)
-	deps = append(deps, newDeps...)
 	errs = append(errs, newErrs...)
 
 	subBlueprintsAndScope := make([]stringAndScope, len(blueprints))
@@ -595,7 +603,7 @@
 		subBlueprintsAndScope[i] = stringAndScope{b, scope}
 	}
 
-	return file, subBlueprintsAndScope, deps, errs
+	return file, subBlueprintsAndScope, errs
 }
 
 type stringAndScope struct {
@@ -790,7 +798,7 @@
 		}
 	}()
 
-	file, subBlueprints, deps, errs := c.parse(rootDir, filename, f, scope)
+	file, subBlueprints, errs := c.parse(rootDir, filename, f, scope)
 	if len(errs) > 0 {
 		errsCh <- errs
 	} else {
@@ -799,22 +807,31 @@
 
 	for _, b := range subBlueprints {
 		blueprintsCh <- b
-	}
-
-	for _, d := range deps {
-		depsCh <- d
+		depsCh <- b.string
 	}
 }
 
 func (c *Context) findBuildBlueprints(dir string, build []string,
-	buildPos scanner.Position) (blueprints, deps []string, errs []error) {
+	buildPos scanner.Position) ([]string, []error) {
+
+	var blueprints []string
+	var errs []error
 
 	for _, file := range build {
-		globPattern := filepath.Join(dir, file)
-		matches, matchedDirs, err := pathtools.Glob(globPattern)
+		pattern := filepath.Join(dir, file)
+		var matches []string
+		var err error
+
+		if pathtools.IsGlob(pattern) {
+			matches, err = c.glob(pattern, nil)
+		} else {
+			// Not a glob, but use filepath.Glob to check if it exists
+			matches, err = filepath.Glob(pattern)
+		}
+
 		if err != nil {
 			errs = append(errs, &BlueprintError{
-				Err: fmt.Errorf("%q: %s", globPattern, err.Error()),
+				Err: fmt.Errorf("%q: %s", pattern, err.Error()),
 				Pos: buildPos,
 			})
 			continue
@@ -822,47 +839,40 @@
 
 		if len(matches) == 0 {
 			errs = append(errs, &BlueprintError{
-				Err: fmt.Errorf("%q: not found", globPattern),
+				Err: fmt.Errorf("%q: not found", pattern),
 				Pos: buildPos,
 			})
 		}
 
-		// Depend on all searched directories so we pick up future changes.
-		deps = append(deps, matchedDirs...)
-
 		for _, foundBlueprints := range matches {
-			exists, dir, err := c.fs.Exists(foundBlueprints)
-			if err != nil {
-				errs = append(errs, err)
-			} else if !exists {
-				errs = append(errs, &BlueprintError{
-					Err: fmt.Errorf("%q not found", foundBlueprints),
-				})
-				continue
-			} else if dir {
-				errs = append(errs, &BlueprintError{
-					Err: fmt.Errorf("%q is a directory", foundBlueprints),
-				})
-				continue
-			}
-
 			blueprints = append(blueprints, foundBlueprints)
-			deps = append(deps, foundBlueprints)
 		}
 	}
 
-	return blueprints, deps, errs
+	return blueprints, errs
 }
 
 func (c *Context) findSubdirBlueprints(dir string, subdirs []string, subdirsPos scanner.Position,
-	subBlueprintsName string, optional bool) (blueprints, deps []string, errs []error) {
+	subBlueprintsName string, optional bool) ([]string, []error) {
+
+	var blueprints []string
+	var errs []error
 
 	for _, subdir := range subdirs {
-		globPattern := filepath.Join(dir, subdir)
-		matches, matchedDirs, err := pathtools.Glob(globPattern)
+		pattern := filepath.Join(dir, subdir, subBlueprintsName)
+		var matches []string
+		var err error
+
+		if pathtools.IsGlob(pattern) {
+			matches, err = c.glob(pattern, nil)
+		} else {
+			// Not a glob, but use filepath.Glob to check if it exists
+			matches, err = filepath.Glob(pattern)
+		}
+
 		if err != nil {
 			errs = append(errs, &BlueprintError{
-				Err: fmt.Errorf("%q: %s", globPattern, err.Error()),
+				Err: fmt.Errorf("%q: %s", pattern, err.Error()),
 				Pos: subdirsPos,
 			})
 			continue
@@ -870,56 +880,17 @@
 
 		if len(matches) == 0 && !optional {
 			errs = append(errs, &BlueprintError{
-				Err: fmt.Errorf("%q: not found", globPattern),
+				Err: fmt.Errorf("%q: not found", pattern),
 				Pos: subdirsPos,
 			})
 		}
 
-		// Depend on all searched directories so we pick up future changes.
-		deps = append(deps, matchedDirs...)
-
-		for _, foundSubdir := range matches {
-			exists, dir, subdirStatErr := c.fs.Exists(foundSubdir)
-			if subdirStatErr != nil {
-				errs = append(errs, subdirStatErr)
-				continue
-			}
-
-			// Skip files
-			if !dir {
-				continue
-			}
-
-			var subBlueprints string
-			if subBlueprintsName != "" {
-				subBlueprints = filepath.Join(foundSubdir, subBlueprintsName)
-				exists, _, err = c.fs.Exists(subBlueprints)
-			}
-
-			if err == nil && (!exists || subBlueprints == "") {
-				subBlueprints = filepath.Join(foundSubdir, "Blueprints")
-				exists, _, err = c.fs.Exists(subBlueprints)
-			}
-
-			if err != nil {
-				errs = append(errs, err)
-				continue
-			}
-
-			if !exists {
-				// There is no Blueprints file in this subdirectory.  We
-				// need to add the directory to the list of dependencies
-				// so that if someone adds a Blueprints file in the
-				// future we'll pick it up.
-				deps = append(deps, foundSubdir)
-			} else {
-				deps = append(deps, subBlueprints)
-				blueprints = append(blueprints, subBlueprints)
-			}
+		for _, subBlueprints := range matches {
+			blueprints = append(blueprints, subBlueprints)
 		}
 	}
 
-	return blueprints, deps, errs
+	return blueprints, errs
 }
 
 func getLocalStringListFromScope(scope *parser.Scope, v string) ([]string, scanner.Position, error) {