From dd84b9d64fb98746a230cd24233ff50a562c39c9 Mon Sep 17 00:00:00 2001 From: 简律纯 Date: Fri, 28 Apr 2023 01:36:44 +0800 Subject: --- cli/internal/scope/filter/filter.go | 421 ++++++++++++++ cli/internal/scope/filter/filter_test.go | 614 +++++++++++++++++++++ cli/internal/scope/filter/matcher.go | 32 ++ cli/internal/scope/filter/matcher_test.go | 65 +++ cli/internal/scope/filter/parse_target_selector.go | 165 ++++++ .../scope/filter/parse_target_selector_test.go | 311 +++++++++++ 6 files changed, 1608 insertions(+) create mode 100644 cli/internal/scope/filter/filter.go create mode 100644 cli/internal/scope/filter/filter_test.go create mode 100644 cli/internal/scope/filter/matcher.go create mode 100644 cli/internal/scope/filter/matcher_test.go create mode 100644 cli/internal/scope/filter/parse_target_selector.go create mode 100644 cli/internal/scope/filter/parse_target_selector_test.go (limited to 'cli/internal/scope/filter') diff --git a/cli/internal/scope/filter/filter.go b/cli/internal/scope/filter/filter.go new file mode 100644 index 0000000..60aaf1d --- /dev/null +++ b/cli/internal/scope/filter/filter.go @@ -0,0 +1,421 @@ +package filter + +import ( + "fmt" + "strings" + + "github.com/pkg/errors" + "github.com/pyr-sh/dag" + "github.com/vercel/turbo/cli/internal/doublestar" + "github.com/vercel/turbo/cli/internal/turbopath" + "github.com/vercel/turbo/cli/internal/util" + "github.com/vercel/turbo/cli/internal/workspace" +) + +type SelectedPackages struct { + pkgs util.Set + unusedFilters []*TargetSelector +} + +// PackagesChangedInRange is the signature of a function to provide the set of +// packages that have changed in a particular range of git refs. +type PackagesChangedInRange = func(fromRef string, toRef string) (util.Set, error) + +// PackageInference holds the information we have inferred from the working-directory +// (really --infer-filter-root flag) about which packages are of interest. +type PackageInference struct { + // PackageName, if set, means that we have determined that filters without a package-specifier + // should get this package name + PackageName string + // DirectoryRoot is used to infer a "parentDir" for the filter in the event that we haven't + // identified a specific package. If the filter already contains a parentDir, this acts as + // a prefix. If the filter does not contain a parentDir, we consider this to be a glob for + // all subdirectories + DirectoryRoot turbopath.RelativeSystemPath +} + +type Resolver struct { + Graph *dag.AcyclicGraph + WorkspaceInfos workspace.Catalog + Cwd turbopath.AbsoluteSystemPath + Inference *PackageInference + PackagesChangedInRange PackagesChangedInRange +} + +// GetPackagesFromPatterns compiles filter patterns and applies them, returning +// the selected packages +func (r *Resolver) GetPackagesFromPatterns(patterns []string) (util.Set, error) { + selectors := []*TargetSelector{} + for _, pattern := range patterns { + selector, err := ParseTargetSelector(pattern) + if err != nil { + return nil, err + } + selectors = append(selectors, selector) + } + selected, err := r.getFilteredPackages(selectors) + if err != nil { + return nil, err + } + return selected.pkgs, nil +} + +func (pi *PackageInference) apply(selector *TargetSelector) error { + if selector.namePattern != "" { + // The selector references a package name, don't apply inference + return nil + } + if pi.PackageName != "" { + selector.namePattern = pi.PackageName + } + if selector.parentDir != "" { + parentDir := pi.DirectoryRoot.Join(selector.parentDir) + selector.parentDir = parentDir + } else if pi.PackageName == "" { + // The user didn't set a parent directory and we didn't find a single package, + // so use the directory we inferred and select all subdirectories + selector.parentDir = pi.DirectoryRoot.Join("**") + } + return nil +} + +func (r *Resolver) applyInference(selectors []*TargetSelector) ([]*TargetSelector, error) { + if r.Inference == nil { + return selectors, nil + } + // If there are existing patterns, use inference on those. If there are no + // patterns, but there is a directory supplied, synthesize a selector + if len(selectors) == 0 { + selectors = append(selectors, &TargetSelector{}) + } + for _, selector := range selectors { + if err := r.Inference.apply(selector); err != nil { + return nil, err + } + } + return selectors, nil +} + +func (r *Resolver) getFilteredPackages(selectors []*TargetSelector) (*SelectedPackages, error) { + selectors, err := r.applyInference(selectors) + if err != nil { + return nil, err + } + prodPackageSelectors := []*TargetSelector{} + allPackageSelectors := []*TargetSelector{} + for _, selector := range selectors { + if selector.followProdDepsOnly { + prodPackageSelectors = append(prodPackageSelectors, selector) + } else { + allPackageSelectors = append(allPackageSelectors, selector) + } + } + if len(allPackageSelectors) > 0 || len(prodPackageSelectors) > 0 { + if len(allPackageSelectors) > 0 { + selected, err := r.filterGraph(allPackageSelectors) + if err != nil { + return nil, err + } + return selected, nil + } + } + return &SelectedPackages{ + pkgs: make(util.Set), + }, nil +} + +func (r *Resolver) filterGraph(selectors []*TargetSelector) (*SelectedPackages, error) { + includeSelectors := []*TargetSelector{} + excludeSelectors := []*TargetSelector{} + for _, selector := range selectors { + if selector.exclude { + excludeSelectors = append(excludeSelectors, selector) + } else { + includeSelectors = append(includeSelectors, selector) + } + } + var include *SelectedPackages + if len(includeSelectors) > 0 { + found, err := r.filterGraphWithSelectors(includeSelectors) + if err != nil { + return nil, err + } + include = found + } else { + vertexSet := make(util.Set) + for _, v := range r.Graph.Vertices() { + vertexSet.Add(v) + } + include = &SelectedPackages{ + pkgs: vertexSet, + } + } + exclude, err := r.filterGraphWithSelectors(excludeSelectors) + if err != nil { + return nil, err + } + return &SelectedPackages{ + pkgs: include.pkgs.Difference(exclude.pkgs), + unusedFilters: append(include.unusedFilters, exclude.unusedFilters...), + }, nil +} + +func (r *Resolver) filterGraphWithSelectors(selectors []*TargetSelector) (*SelectedPackages, error) { + unmatchedSelectors := []*TargetSelector{} + + cherryPickedPackages := make(dag.Set) + walkedDependencies := make(dag.Set) + walkedDependents := make(dag.Set) + walkedDependentsDependencies := make(dag.Set) + + for _, selector := range selectors { + // TODO(gsoltis): this should be a list? + entryPackages, err := r.filterGraphWithSelector(selector) + if err != nil { + return nil, err + } + if entryPackages.Len() == 0 { + unmatchedSelectors = append(unmatchedSelectors, selector) + } + for _, pkg := range entryPackages { + if selector.includeDependencies { + dependencies, err := r.Graph.Ancestors(pkg) + if err != nil { + return nil, errors.Wrapf(err, "failed to get dependencies of package %v", pkg) + } + for dep := range dependencies { + walkedDependencies.Add(dep) + } + if !selector.excludeSelf { + walkedDependencies.Add(pkg) + } + } + if selector.includeDependents { + dependents, err := r.Graph.Descendents(pkg) + if err != nil { + return nil, errors.Wrapf(err, "failed to get dependents of package %v", pkg) + } + for dep := range dependents { + walkedDependents.Add(dep) + if selector.includeDependencies { + dependentDeps, err := r.Graph.Ancestors(dep) + if err != nil { + return nil, errors.Wrapf(err, "failed to get dependencies of dependent %v", dep) + } + for dependentDep := range dependentDeps { + walkedDependentsDependencies.Add(dependentDep) + } + } + } + if !selector.excludeSelf { + walkedDependents.Add(pkg) + } + } + if !selector.includeDependencies && !selector.includeDependents { + cherryPickedPackages.Add(pkg) + } + } + } + allPkgs := make(util.Set) + for pkg := range cherryPickedPackages { + allPkgs.Add(pkg) + } + for pkg := range walkedDependencies { + allPkgs.Add(pkg) + } + for pkg := range walkedDependents { + allPkgs.Add(pkg) + } + for pkg := range walkedDependentsDependencies { + allPkgs.Add(pkg) + } + return &SelectedPackages{ + pkgs: allPkgs, + unusedFilters: unmatchedSelectors, + }, nil +} + +func (r *Resolver) filterGraphWithSelector(selector *TargetSelector) (util.Set, error) { + if selector.matchDependencies { + return r.filterSubtreesWithSelector(selector) + } + return r.filterNodesWithSelector(selector) +} + +// filterNodesWithSelector returns the set of nodes that match a given selector +func (r *Resolver) filterNodesWithSelector(selector *TargetSelector) (util.Set, error) { + entryPackages := make(util.Set) + selectorWasUsed := false + if selector.fromRef != "" { + // get changed packaged + selectorWasUsed = true + changedPkgs, err := r.PackagesChangedInRange(selector.fromRef, selector.getToRef()) + if err != nil { + return nil, err + } + parentDir := selector.parentDir + for pkgName := range changedPkgs { + if parentDir != "" { + // Type assert/coerce to string here because we want to use + // this value in a map that has string keys. + // TODO(mehulkar) `changedPkgs` is a util.Set, we could make a `util.PackageNamesSet`` + // or something similar that is all strings. + pkgNameStr := pkgName.(string) + if pkgName == util.RootPkgName { + // The root package changed, only add it if + // the parentDir is equivalent to the root + if matches, err := doublestar.PathMatch(r.Cwd.Join(parentDir).ToString(), r.Cwd.ToString()); err != nil { + return nil, fmt.Errorf("failed to resolve directory relationship %v contains %v: %v", parentDir, r.Cwd, err) + } else if matches { + entryPackages.Add(pkgName) + } + } else if pkg, ok := r.WorkspaceInfos.PackageJSONs[pkgNameStr]; !ok { + return nil, fmt.Errorf("missing info for package %v", pkgName) + } else if matches, err := doublestar.PathMatch(r.Cwd.Join(parentDir).ToString(), pkg.Dir.RestoreAnchor(r.Cwd).ToString()); err != nil { + return nil, fmt.Errorf("failed to resolve directory relationship %v contains %v: %v", selector.parentDir, pkg.Dir, err) + } else if matches { + entryPackages.Add(pkgName) + } + } else { + entryPackages.Add(pkgName) + } + } + } else if selector.parentDir != "" { + // get packages by path + selectorWasUsed = true + parentDir := selector.parentDir + if parentDir == "." { + entryPackages.Add(util.RootPkgName) + } else { + for name, pkg := range r.WorkspaceInfos.PackageJSONs { + if matches, err := doublestar.PathMatch(r.Cwd.Join(parentDir).ToString(), pkg.Dir.RestoreAnchor(r.Cwd).ToString()); err != nil { + return nil, fmt.Errorf("failed to resolve directory relationship %v contains %v: %v", selector.parentDir, pkg.Dir, err) + } else if matches { + entryPackages.Add(name) + } + } + } + } + if selector.namePattern != "" { + // find packages that match name + if !selectorWasUsed { + matched, err := matchPackageNamesToVertices(selector.namePattern, r.Graph.Vertices()) + if err != nil { + return nil, err + } + entryPackages = matched + selectorWasUsed = true + } else { + matched, err := matchPackageNames(selector.namePattern, entryPackages) + if err != nil { + return nil, err + } + entryPackages = matched + } + } + // TODO(gsoltis): we can do this earlier + // Check if the selector specified anything + if !selectorWasUsed { + return nil, fmt.Errorf("invalid selector: %v", selector.raw) + } + return entryPackages, nil +} + +// filterSubtreesWithSelector returns the set of nodes where the node or any of its dependencies +// match a selector +func (r *Resolver) filterSubtreesWithSelector(selector *TargetSelector) (util.Set, error) { + // foreach package that matches parentDir && namePattern, check if any dependency is in changed packages + changedPkgs, err := r.PackagesChangedInRange(selector.fromRef, selector.getToRef()) + if err != nil { + return nil, err + } + + parentDir := selector.parentDir + entryPackages := make(util.Set) + for name, pkg := range r.WorkspaceInfos.PackageJSONs { + if parentDir == "" { + entryPackages.Add(name) + } else if matches, err := doublestar.PathMatch(parentDir.ToString(), pkg.Dir.RestoreAnchor(r.Cwd).ToString()); err != nil { + return nil, fmt.Errorf("failed to resolve directory relationship %v contains %v: %v", selector.parentDir, pkg.Dir, err) + } else if matches { + entryPackages.Add(name) + } + } + if selector.namePattern != "" { + matched, err := matchPackageNames(selector.namePattern, entryPackages) + if err != nil { + return nil, err + } + entryPackages = matched + } + roots := make(util.Set) + matched := make(util.Set) + for pkg := range entryPackages { + if matched.Includes(pkg) { + roots.Add(pkg) + continue + } + deps, err := r.Graph.Ancestors(pkg) + if err != nil { + return nil, err + } + for changedPkg := range changedPkgs { + if !selector.excludeSelf && pkg == changedPkg { + roots.Add(pkg) + break + } + if deps.Include(changedPkg) { + roots.Add(pkg) + matched.Add(changedPkg) + break + } + } + } + return roots, nil +} + +func matchPackageNamesToVertices(pattern string, vertices []dag.Vertex) (util.Set, error) { + packages := make(util.Set) + for _, v := range vertices { + packages.Add(v) + } + packages.Add(util.RootPkgName) + return matchPackageNames(pattern, packages) +} + +func matchPackageNames(pattern string, packages util.Set) (util.Set, error) { + matcher, err := matcherFromPattern(pattern) + if err != nil { + return nil, err + } + matched := make(util.Set) + for _, pkg := range packages { + pkg := pkg.(string) + if matcher(pkg) { + matched.Add(pkg) + } + } + if matched.Len() == 0 && !strings.HasPrefix(pattern, "@") && !strings.Contains(pattern, "/") { + // we got no matches and the pattern isn't a scoped package. + // Check if we have exactly one scoped package that does match + scopedPattern := fmt.Sprintf("@*/%v", pattern) + matcher, err = matcherFromPattern(scopedPattern) + if err != nil { + return nil, err + } + foundScopedPkg := false + for _, pkg := range packages { + pkg := pkg.(string) + if matcher(pkg) { + if foundScopedPkg { + // we found a second scoped package. Return the empty set, we can't + // disambiguate + return make(util.Set), nil + } + foundScopedPkg = true + matched.Add(pkg) + } + } + } + return matched, nil +} diff --git a/cli/internal/scope/filter/filter_test.go b/cli/internal/scope/filter/filter_test.go new file mode 100644 index 0000000..a23ae1d --- /dev/null +++ b/cli/internal/scope/filter/filter_test.go @@ -0,0 +1,614 @@ +package filter + +import ( + "fmt" + "os" + "strings" + "testing" + + "github.com/pyr-sh/dag" + "github.com/vercel/turbo/cli/internal/fs" + "github.com/vercel/turbo/cli/internal/turbopath" + "github.com/vercel/turbo/cli/internal/util" + "github.com/vercel/turbo/cli/internal/workspace" +) + +func setMatches(t *testing.T, name string, s util.Set, expected []string) { + expectedSet := make(util.Set) + for _, item := range expected { + expectedSet.Add(item) + } + missing := s.Difference(expectedSet) + if missing.Len() > 0 { + t.Errorf("%v set has extra elements: %v", name, strings.Join(missing.UnsafeListOfStrings(), ", ")) + } + extra := expectedSet.Difference(s) + if extra.Len() > 0 { + t.Errorf("%v set missing elements: %v", name, strings.Join(extra.UnsafeListOfStrings(), ", ")) + } +} + +func Test_filter(t *testing.T) { + rawCwd, err := os.Getwd() + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + root, err := fs.GetCwd(rawCwd) + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + workspaceInfos := workspace.Catalog{ + PackageJSONs: make(map[string]*fs.PackageJSON), + } + packageJSONs := workspaceInfos.PackageJSONs + graph := &dag.AcyclicGraph{} + graph.Add("project-0") + packageJSONs["project-0"] = &fs.PackageJSON{ + Name: "project-0", + Dir: turbopath.AnchoredUnixPath("packages/project-0").ToSystemPath(), + } + graph.Add("project-1") + packageJSONs["project-1"] = &fs.PackageJSON{ + Name: "project-1", + Dir: turbopath.AnchoredUnixPath("packages/project-1").ToSystemPath(), + } + graph.Add("project-2") + packageJSONs["project-2"] = &fs.PackageJSON{ + Name: "project-2", + Dir: "project-2", + } + graph.Add("project-3") + packageJSONs["project-3"] = &fs.PackageJSON{ + Name: "project-3", + Dir: "project-3", + } + graph.Add("project-4") + packageJSONs["project-4"] = &fs.PackageJSON{ + Name: "project-4", + Dir: "project-4", + } + graph.Add("project-5") + packageJSONs["project-5"] = &fs.PackageJSON{ + Name: "project-5", + Dir: "project-5", + } + // Note: inside project-5 + graph.Add("project-6") + packageJSONs["project-6"] = &fs.PackageJSON{ + Name: "project-6", + Dir: turbopath.AnchoredUnixPath("project-5/packages/project-6").ToSystemPath(), + } + // Add dependencies + graph.Connect(dag.BasicEdge("project-0", "project-1")) + graph.Connect(dag.BasicEdge("project-0", "project-5")) + graph.Connect(dag.BasicEdge("project-1", "project-2")) + graph.Connect(dag.BasicEdge("project-1", "project-4")) + + testCases := []struct { + Name string + Selectors []*TargetSelector + PackageInference *PackageInference + Expected []string + }{ + { + "select root package", + []*TargetSelector{ + { + namePattern: util.RootPkgName, + }, + }, + nil, + []string{util.RootPkgName}, + }, + { + "select only package dependencies (excluding the package itself)", + []*TargetSelector{ + { + excludeSelf: true, + includeDependencies: true, + namePattern: "project-1", + }, + }, + nil, + []string{"project-2", "project-4"}, + }, + { + "select package with dependencies", + []*TargetSelector{ + { + excludeSelf: false, + includeDependencies: true, + namePattern: "project-1", + }, + }, + nil, + []string{"project-1", "project-2", "project-4"}, + }, + { + "select package with dependencies and dependents, including dependent dependencies", + []*TargetSelector{ + { + excludeSelf: true, + includeDependencies: true, + includeDependents: true, + namePattern: "project-1", + }, + }, + nil, + []string{"project-0", "project-1", "project-2", "project-4", "project-5"}, + }, + { + "select package with dependents", + []*TargetSelector{ + { + includeDependents: true, + namePattern: "project-2", + }, + }, + nil, + []string{"project-1", "project-2", "project-0"}, + }, + { + "select dependents excluding package itself", + []*TargetSelector{ + { + excludeSelf: true, + includeDependents: true, + namePattern: "project-2", + }, + }, + nil, + []string{"project-0", "project-1"}, + }, + { + "filter using two selectors: one selects dependencies another selects dependents", + []*TargetSelector{ + { + excludeSelf: true, + includeDependents: true, + namePattern: "project-2", + }, + { + excludeSelf: true, + includeDependencies: true, + namePattern: "project-1", + }, + }, + nil, + []string{"project-0", "project-1", "project-2", "project-4"}, + }, + { + "select just a package by name", + []*TargetSelector{ + { + namePattern: "project-2", + }, + }, + nil, + []string{"project-2"}, + }, + // Note: we don't support the option to switch path prefix mode + // { + // "select by parentDir", + // []*TargetSelector{ + // { + // parentDir: "/packages", + // }, + // }, + // []string{"project-0", "project-1"}, + // }, + { + "select by parentDir using glob", + []*TargetSelector{ + { + parentDir: turbopath.MakeRelativeSystemPath("packages", "*"), + }, + }, + nil, + []string{"project-0", "project-1"}, + }, + { + "select by parentDir using globstar", + []*TargetSelector{ + { + parentDir: turbopath.MakeRelativeSystemPath("project-5", "**"), + }, + }, + nil, + []string{"project-5", "project-6"}, + }, + { + "select by parentDir with no glob", + []*TargetSelector{ + { + parentDir: turbopath.MakeRelativeSystemPath("project-5"), + }, + }, + nil, + []string{"project-5"}, + }, + { + "select all packages except one", + []*TargetSelector{ + { + exclude: true, + namePattern: "project-1", + }, + }, + nil, + []string{"project-0", "project-2", "project-3", "project-4", "project-5", "project-6"}, + }, + { + "select by parentDir and exclude one package by pattern", + []*TargetSelector{ + { + parentDir: turbopath.MakeRelativeSystemPath("packages", "*"), + }, + { + exclude: true, + namePattern: "*-1", + }, + }, + nil, + []string{"project-0"}, + }, + { + "select root package by directory", + []*TargetSelector{ + { + parentDir: turbopath.MakeRelativeSystemPath("."), // input . gets cleaned to "" + }, + }, + nil, + []string{util.RootPkgName}, + }, + { + "select packages directory", + []*TargetSelector{}, + &PackageInference{ + DirectoryRoot: turbopath.MakeRelativeSystemPath("packages"), + }, + []string{"project-0", "project-1"}, + }, + { + "infer single package", + []*TargetSelector{}, + &PackageInference{ + DirectoryRoot: turbopath.MakeRelativeSystemPath("packages", "project-0"), + PackageName: "project-0", + }, + []string{"project-0"}, + }, + { + "infer single package from subdirectory", + []*TargetSelector{}, + &PackageInference{ + DirectoryRoot: turbopath.MakeRelativeSystemPath("packages", "project-0", "src"), + PackageName: "project-0", + }, + []string{"project-0"}, + }, + } + + for _, tc := range testCases { + t.Run(tc.Name, func(t *testing.T) { + r := &Resolver{ + Graph: graph, + WorkspaceInfos: workspaceInfos, + Cwd: root, + Inference: tc.PackageInference, + } + pkgs, err := r.getFilteredPackages(tc.Selectors) + if err != nil { + t.Fatalf("%v failed to filter packages: %v", tc.Name, err) + } + setMatches(t, tc.Name, pkgs.pkgs, tc.Expected) + }) + } + + t.Run("report unmatched filters", func(t *testing.T) { + r := &Resolver{ + Graph: graph, + WorkspaceInfos: workspaceInfos, + Cwd: root, + } + pkgs, err := r.getFilteredPackages([]*TargetSelector{ + { + excludeSelf: true, + includeDependencies: true, + namePattern: "project-7", + }, + }) + if err != nil { + t.Fatalf("unmatched filter failed to filter packages: %v", err) + } + if pkgs.pkgs.Len() != 0 { + t.Errorf("unmatched filter expected no packages, got %v", strings.Join(pkgs.pkgs.UnsafeListOfStrings(), ", ")) + } + if len(pkgs.unusedFilters) != 1 { + t.Errorf("unmatched filter expected to report one unused filter, got %v", len(pkgs.unusedFilters)) + } + }) +} + +func Test_matchScopedPackage(t *testing.T) { + rawCwd, err := os.Getwd() + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + root, err := fs.GetCwd(rawCwd) + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + + workspaceInfos := workspace.Catalog{ + PackageJSONs: make(map[string]*fs.PackageJSON), + } + packageJSONs := workspaceInfos.PackageJSONs + graph := &dag.AcyclicGraph{} + graph.Add("@foo/bar") + packageJSONs["@foo/bar"] = &fs.PackageJSON{ + Name: "@foo/bar", + Dir: turbopath.AnchoredUnixPath("packages/bar").ToSystemPath(), + } + r := &Resolver{ + Graph: graph, + WorkspaceInfos: workspaceInfos, + Cwd: root, + } + pkgs, err := r.getFilteredPackages([]*TargetSelector{ + { + namePattern: "bar", + }, + }) + if err != nil { + t.Fatalf("failed to filter packages: %v", err) + } + setMatches(t, "match scoped package", pkgs.pkgs, []string{"@foo/bar"}) +} + +func Test_matchExactPackages(t *testing.T) { + rawCwd, err := os.Getwd() + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + root, err := fs.GetCwd(rawCwd) + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + + workspaceInfos := workspace.Catalog{ + PackageJSONs: make(map[string]*fs.PackageJSON), + } + packageJSONs := workspaceInfos.PackageJSONs + graph := &dag.AcyclicGraph{} + graph.Add("@foo/bar") + packageJSONs["@foo/bar"] = &fs.PackageJSON{ + Name: "@foo/bar", + Dir: turbopath.AnchoredUnixPath("packages/@foo/bar").ToSystemPath(), + } + graph.Add("bar") + packageJSONs["bar"] = &fs.PackageJSON{ + Name: "bar", + Dir: turbopath.AnchoredUnixPath("packages/bar").ToSystemPath(), + } + r := &Resolver{ + Graph: graph, + WorkspaceInfos: workspaceInfos, + Cwd: root, + } + pkgs, err := r.getFilteredPackages([]*TargetSelector{ + { + namePattern: "bar", + }, + }) + if err != nil { + t.Fatalf("failed to filter packages: %v", err) + } + setMatches(t, "match exact package", pkgs.pkgs, []string{"bar"}) +} + +func Test_matchMultipleScopedPackages(t *testing.T) { + rawCwd, err := os.Getwd() + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + root, err := fs.GetCwd(rawCwd) + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + + workspaceInfos := workspace.Catalog{ + PackageJSONs: make(map[string]*fs.PackageJSON), + } + packageJSONs := workspaceInfos.PackageJSONs + graph := &dag.AcyclicGraph{} + graph.Add("@foo/bar") + packageJSONs["@foo/bar"] = &fs.PackageJSON{ + Name: "@foo/bar", + Dir: turbopath.AnchoredUnixPath("packages/@foo/bar").ToSystemPath(), + } + graph.Add("@types/bar") + packageJSONs["@types/bar"] = &fs.PackageJSON{ + Name: "@types/bar", + Dir: turbopath.AnchoredUnixPath("packages/@types/bar").ToSystemPath(), + } + r := &Resolver{ + Graph: graph, + WorkspaceInfos: workspaceInfos, + Cwd: root, + } + pkgs, err := r.getFilteredPackages([]*TargetSelector{ + { + namePattern: "bar", + }, + }) + if err != nil { + t.Fatalf("failed to filter packages: %v", err) + } + setMatches(t, "match nothing with multiple scoped packages", pkgs.pkgs, []string{}) +} + +func Test_SCM(t *testing.T) { + rawCwd, err := os.Getwd() + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + root, err := fs.GetCwd(rawCwd) + if err != nil { + t.Fatalf("failed to get working directory: %v", err) + } + head1Changed := make(util.Set) + head1Changed.Add("package-1") + head1Changed.Add("package-2") + head1Changed.Add(util.RootPkgName) + head2Changed := make(util.Set) + head2Changed.Add("package-3") + workspaceInfos := workspace.Catalog{ + PackageJSONs: make(map[string]*fs.PackageJSON), + } + packageJSONs := workspaceInfos.PackageJSONs + graph := &dag.AcyclicGraph{} + graph.Add("package-1") + packageJSONs["package-1"] = &fs.PackageJSON{ + Name: "package-1", + Dir: "package-1", + } + graph.Add("package-2") + packageJSONs["package-2"] = &fs.PackageJSON{ + Name: "package-2", + Dir: "package-2", + } + graph.Add("package-3") + packageJSONs["package-3"] = &fs.PackageJSON{ + Name: "package-3", + Dir: "package-3", + } + graph.Add("package-20") + packageJSONs["package-20"] = &fs.PackageJSON{ + Name: "package-20", + Dir: "package-20", + } + + graph.Connect(dag.BasicEdge("package-3", "package-20")) + + r := &Resolver{ + Graph: graph, + WorkspaceInfos: workspaceInfos, + Cwd: root, + PackagesChangedInRange: func(fromRef string, toRef string) (util.Set, error) { + if fromRef == "HEAD~1" && toRef == "HEAD" { + return head1Changed, nil + } else if fromRef == "HEAD~2" && toRef == "HEAD" { + union := head1Changed.Copy() + for val := range head2Changed { + union.Add(val) + } + return union, nil + } else if fromRef == "HEAD~2" && toRef == "HEAD~1" { + return head2Changed, nil + } + panic(fmt.Sprintf("unsupported commit range %v...%v", fromRef, toRef)) + }, + } + + testCases := []struct { + Name string + Selectors []*TargetSelector + Expected []string + }{ + { + "all changed packages", + []*TargetSelector{ + { + fromRef: "HEAD~1", + }, + }, + []string{"package-1", "package-2", util.RootPkgName}, + }, + { + "all changed packages with parent dir exact match", + []*TargetSelector{ + { + fromRef: "HEAD~1", + parentDir: ".", + }, + }, + []string{util.RootPkgName}, + }, + { + "changed packages in directory", + []*TargetSelector{ + { + fromRef: "HEAD~1", + parentDir: "package-2", + }, + }, + []string{"package-2"}, + }, + { + "changed packages matching pattern", + []*TargetSelector{ + { + fromRef: "HEAD~1", + namePattern: "package-2*", + }, + }, + []string{"package-2"}, + }, + { + "changed packages matching pattern", + []*TargetSelector{ + { + fromRef: "HEAD~1", + namePattern: "package-2*", + }, + }, + []string{"package-2"}, + }, + // Note: missing test here that takes advantage of automatically exempting + // test-only changes from pulling in dependents + // + // turbo-specific tests below here + { + "changed package was requested scope, and we're matching dependencies", + []*TargetSelector{ + { + fromRef: "HEAD~1", + namePattern: "package-1", + matchDependencies: true, + }, + }, + []string{"package-1"}, + }, + { + "older commit", + []*TargetSelector{ + { + fromRef: "HEAD~2", + }, + }, + []string{"package-1", "package-2", "package-3", util.RootPkgName}, + }, + { + "commit range", + []*TargetSelector{ + { + fromRef: "HEAD~2", + toRefOverride: "HEAD~1", + }, + }, + []string{"package-3"}, + }, + } + + for _, tc := range testCases { + t.Run(tc.Name, func(t *testing.T) { + pkgs, err := r.getFilteredPackages(tc.Selectors) + if err != nil { + t.Fatalf("%v failed to filter packages: %v", tc.Name, err) + } + setMatches(t, tc.Name, pkgs.pkgs, tc.Expected) + }) + } +} diff --git a/cli/internal/scope/filter/matcher.go b/cli/internal/scope/filter/matcher.go new file mode 100644 index 0000000..2460326 --- /dev/null +++ b/cli/internal/scope/filter/matcher.go @@ -0,0 +1,32 @@ +package filter + +import ( + "regexp" + "strings" + + "github.com/pkg/errors" +) + +type Matcher = func(pkgName string) bool + +func matchAll(pkgName string) bool { + return true +} + +func matcherFromPattern(pattern string) (Matcher, error) { + if pattern == "*" { + return matchAll, nil + } + + escaped := regexp.QuoteMeta(pattern) + // replace escaped '*' with regex '.*' + normalized := strings.ReplaceAll(escaped, "\\*", ".*") + if normalized == pattern { + return func(pkgName string) bool { return pkgName == pattern }, nil + } + regex, err := regexp.Compile("^" + normalized + "$") + if err != nil { + return nil, errors.Wrapf(err, "failed to compile filter pattern to regex: %v", pattern) + } + return func(pkgName string) bool { return regex.Match([]byte(pkgName)) }, nil +} diff --git a/cli/internal/scope/filter/matcher_test.go b/cli/internal/scope/filter/matcher_test.go new file mode 100644 index 0000000..966be2b --- /dev/null +++ b/cli/internal/scope/filter/matcher_test.go @@ -0,0 +1,65 @@ +package filter + +import "testing" + +func TestMatcher(t *testing.T) { + testCases := map[string][]struct { + test string + want bool + }{ + "*": { + { + test: "@eslint/plugin-foo", + want: true, + }, + { + test: "express", + want: true, + }, + }, + "eslint-*": { + { + test: "eslint-plugin-foo", + want: true, + }, + { + test: "express", + want: false, + }, + }, + "*plugin*": { + { + test: "@eslint/plugin-foo", + want: true, + }, + { + test: "express", + want: false, + }, + }, + "a*c": { + { + test: "abc", + want: true, + }, + }, + "*-positive": { + { + test: "is-positive", + want: true, + }, + }, + } + for pattern, tests := range testCases { + matcher, err := matcherFromPattern(pattern) + if err != nil { + t.Fatalf("failed to compile match pattern %v, %v", pattern, err) + } + for _, testCase := range tests { + got := matcher(testCase.test) + if got != testCase.want { + t.Errorf("%v.match(%v) got %v, want %v", pattern, testCase.test, got, testCase.want) + } + } + } +} diff --git a/cli/internal/scope/filter/parse_target_selector.go b/cli/internal/scope/filter/parse_target_selector.go new file mode 100644 index 0000000..4f5c90f --- /dev/null +++ b/cli/internal/scope/filter/parse_target_selector.go @@ -0,0 +1,165 @@ +package filter + +import ( + "regexp" + "strings" + + "github.com/pkg/errors" + "github.com/vercel/turbo/cli/internal/turbopath" +) + +type TargetSelector struct { + includeDependencies bool + matchDependencies bool + includeDependents bool + exclude bool + excludeSelf bool + followProdDepsOnly bool + parentDir turbopath.RelativeSystemPath + namePattern string + fromRef string + toRefOverride string + raw string +} + +func (ts *TargetSelector) IsValid() bool { + return ts.fromRef != "" || ts.parentDir != "" || ts.namePattern != "" +} + +// getToRef returns the git ref to use for upper bound of the comparison when finding changed +// packages. +func (ts *TargetSelector) getToRef() string { + if ts.toRefOverride == "" { + return "HEAD" + } + return ts.toRefOverride +} + +var errCantMatchDependencies = errors.New("cannot use match dependencies without specifying either a directory or package") + +var targetSelectorRegex = regexp.MustCompile(`^(?P[^.](?:[^{}[\]]*[^{}[\].])?)?(?P\{[^}]*\})?(?P(?:\.{3})?\[[^\]]+\])?$`) + +// ParseTargetSelector is a function that returns pnpm compatible --filter command line flags +func ParseTargetSelector(rawSelector string) (*TargetSelector, error) { + exclude := false + firstChar := rawSelector[0] + selector := rawSelector + if firstChar == '!' { + selector = selector[1:] + exclude = true + } + excludeSelf := false + includeDependencies := strings.HasSuffix(selector, "...") + if includeDependencies { + selector = selector[:len(selector)-3] + if strings.HasSuffix(selector, "^") { + excludeSelf = true + selector = selector[:len(selector)-1] + } + } + includeDependents := strings.HasPrefix(selector, "...") + if includeDependents { + selector = selector[3:] + if strings.HasPrefix(selector, "^") { + excludeSelf = true + selector = selector[1:] + } + } + + matches := targetSelectorRegex.FindAllStringSubmatch(selector, -1) + + if len(matches) == 0 { + if relativePath, ok := isSelectorByLocation(selector); ok { + return &TargetSelector{ + exclude: exclude, + includeDependencies: includeDependencies, + includeDependents: includeDependents, + parentDir: relativePath, + raw: rawSelector, + }, nil + } + return &TargetSelector{ + exclude: exclude, + excludeSelf: excludeSelf, + includeDependencies: includeDependencies, + includeDependents: includeDependents, + namePattern: selector, + raw: rawSelector, + }, nil + } + + fromRef := "" + toRefOverride := "" + var parentDir turbopath.RelativeSystemPath + namePattern := "" + preAddDepdencies := false + if len(matches) > 0 && len(matches[0]) > 0 { + match := matches[0] + namePattern = match[targetSelectorRegex.SubexpIndex("name")] + rawParentDir := match[targetSelectorRegex.SubexpIndex("directory")] + if len(rawParentDir) > 0 { + // trim {} + rawParentDir = rawParentDir[1 : len(rawParentDir)-1] + if rawParentDir == "" { + return nil, errors.New("empty path specification") + } else if relPath, err := turbopath.CheckedToRelativeSystemPath(rawParentDir); err == nil { + parentDir = relPath + } else { + return nil, errors.Wrapf(err, "invalid path specification: %v", rawParentDir) + } + } + rawCommits := match[targetSelectorRegex.SubexpIndex("commits")] + if len(rawCommits) > 0 { + fromRef = rawCommits + if strings.HasPrefix(fromRef, "...") { + if parentDir == "" && namePattern == "" { + return &TargetSelector{}, errCantMatchDependencies + } + preAddDepdencies = true + fromRef = fromRef[3:] + } + // strip [] + fromRef = fromRef[1 : len(fromRef)-1] + refs := strings.Split(fromRef, "...") + if len(refs) == 2 { + fromRef = refs[0] + toRefOverride = refs[1] + } + } + } + + return &TargetSelector{ + fromRef: fromRef, + toRefOverride: toRefOverride, + exclude: exclude, + excludeSelf: excludeSelf, + includeDependencies: includeDependencies, + matchDependencies: preAddDepdencies, + includeDependents: includeDependents, + namePattern: namePattern, + parentDir: parentDir, + raw: rawSelector, + }, nil +} + +// isSelectorByLocation returns true if the selector is by filesystem location +func isSelectorByLocation(rawSelector string) (turbopath.RelativeSystemPath, bool) { + if rawSelector[0:1] != "." { + return "", false + } + + // . or ./ or .\ + if len(rawSelector) == 1 || rawSelector[1:2] == "/" || rawSelector[1:2] == "\\" { + return turbopath.MakeRelativeSystemPath(rawSelector), true + } + + if rawSelector[1:2] != "." { + return "", false + } + + // .. or ../ or ..\ + if len(rawSelector) == 2 || rawSelector[2:3] == "/" || rawSelector[2:3] == "\\" { + return turbopath.MakeRelativeSystemPath(rawSelector), true + } + return "", false +} diff --git a/cli/internal/scope/filter/parse_target_selector_test.go b/cli/internal/scope/filter/parse_target_selector_test.go new file mode 100644 index 0000000..2973a61 --- /dev/null +++ b/cli/internal/scope/filter/parse_target_selector_test.go @@ -0,0 +1,311 @@ +package filter + +import ( + "reflect" + "testing" + + "github.com/vercel/turbo/cli/internal/turbopath" +) + +func TestParseTargetSelector(t *testing.T) { + tests := []struct { + rawSelector string + want *TargetSelector + wantErr bool + }{ + { + "{}", + &TargetSelector{}, + true, + }, + { + "foo", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "foo", + parentDir: "", + }, + false, + }, + { + "foo...", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: true, + includeDependents: false, + namePattern: "foo", + parentDir: "", + }, + false, + }, + { + "...foo", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: true, + namePattern: "foo", + parentDir: "", + }, + false, + }, + { + "...foo...", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: true, + includeDependents: true, + namePattern: "foo", + parentDir: "", + }, + false, + }, + { + "foo^...", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: true, + includeDependencies: true, + includeDependents: false, + namePattern: "foo", + parentDir: "", + }, + false, + }, + { + "...^foo", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: true, + includeDependencies: false, + includeDependents: true, + namePattern: "foo", + parentDir: "", + }, + false, + }, + { + "./foo", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "", + parentDir: "foo", + }, + false, + }, + { + "../foo", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "", + parentDir: turbopath.MakeRelativeSystemPath("..", "foo"), + }, + false, + }, + { + "...{./foo}", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: true, + namePattern: "", + parentDir: "foo", + }, + false, + }, + { + ".", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "", + parentDir: ".", + }, + false, + }, + { + "..", + &TargetSelector{ + fromRef: "", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "", + parentDir: "..", + }, + false, + }, + { + "[master]", + &TargetSelector{ + fromRef: "master", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "", + parentDir: "", + }, + false, + }, + { + "[from...to]", + &TargetSelector{ + fromRef: "from", + toRefOverride: "to", + }, + false, + }, + { + "{foo}[master]", + &TargetSelector{ + fromRef: "master", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "", + parentDir: "foo", + }, + false, + }, + { + "pattern{foo}[master]", + &TargetSelector{ + fromRef: "master", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: false, + namePattern: "pattern", + parentDir: "foo", + }, + false, + }, + { + "[master]...", + &TargetSelector{ + fromRef: "master", + exclude: false, + excludeSelf: false, + includeDependencies: true, + includeDependents: false, + namePattern: "", + parentDir: "", + }, + false, + }, + { + "...[master]", + &TargetSelector{ + fromRef: "master", + exclude: false, + excludeSelf: false, + includeDependencies: false, + includeDependents: true, + namePattern: "", + parentDir: "", + }, + false, + }, + { + "...[master]...", + &TargetSelector{ + fromRef: "master", + exclude: false, + excludeSelf: false, + includeDependencies: true, + includeDependents: true, + namePattern: "", + parentDir: "", + }, + false, + }, + { + "...[from...to]...", + &TargetSelector{ + fromRef: "from", + toRefOverride: "to", + includeDependencies: true, + includeDependents: true, + }, + false, + }, + { + "foo...[master]", + &TargetSelector{ + fromRef: "master", + namePattern: "foo", + matchDependencies: true, + }, + false, + }, + { + "foo...[master]...", + &TargetSelector{ + fromRef: "master", + namePattern: "foo", + matchDependencies: true, + includeDependencies: true, + }, + false, + }, + { + "{foo}...[master]", + &TargetSelector{ + fromRef: "master", + parentDir: "foo", + matchDependencies: true, + }, + false, + }, + { + "......[master]", + &TargetSelector{}, + true, + }, + } + for _, tt := range tests { + t.Run(tt.rawSelector, func(t *testing.T) { + got, err := ParseTargetSelector(tt.rawSelector) + if tt.wantErr { + if err == nil { + t.Errorf("ParseTargetSelector() error = %#v, wantErr %#v", err, tt.wantErr) + } + } else { + // copy the raw selector from the args into what we want. This value is used + // for reporting errors in the case of a malformed selector + tt.want.raw = tt.rawSelector + if !reflect.DeepEqual(got, tt.want) { + t.Errorf("ParseTargetSelector() = %#v, want %#v", got, tt.want) + } + } + }) + } +} -- cgit v1.2.3-70-g09d2