walk.go

Documentation: github.com/bazelbuild/bazel-gazelle/walk

     1  /* Copyright 2018 The Bazel Authors. 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  */
    15  
    16  // Package walk provides customizable functionality for visiting each
    17  // subdirectory in a directory tree.
    18  package walk
    19  
    20  import (
    21  	"io/fs"
    22  	"log"
    23  	"os"
    24  	"path"
    25  	"path/filepath"
    26  	"strings"
    27  
    28  	"github.com/bazelbuild/bazel-gazelle/config"
    29  	"github.com/bazelbuild/bazel-gazelle/rule"
    30  )
    31  
    32  // Mode determines which directories Walk visits and which directories
    33  // should be updated.
    34  type Mode int
    35  
    36  const (
    37  	// In VisitAllUpdateSubdirsMode, Walk visits every directory in the
    38  	// repository. The directories given to Walk and their subdirectories are
    39  	// updated.
    40  	VisitAllUpdateSubdirsMode Mode = iota
    41  
    42  	// In VisitAllUpdateDirsMode, Walk visits every directory in the repository.
    43  	// Only the directories given to Walk are updated (not their subdirectories).
    44  	VisitAllUpdateDirsMode
    45  
    46  	// In UpdateDirsMode, Walk only visits and updates directories given to Walk.
    47  	// Build files in parent directories are read in order to produce a complete
    48  	// configuration, but the callback is not called for parent directories.
    49  	UpdateDirsMode
    50  
    51  	// In UpdateSubdirsMode, Walk visits and updates the directories given to Walk
    52  	// and their subdirectories. Build files in parent directories are read in
    53  	// order to produce a complete configuration, but the callback is not called
    54  	// for parent directories.
    55  	UpdateSubdirsMode
    56  )
    57  
    58  // WalkFunc is a callback called by Walk in each visited directory.
    59  //
    60  // dir is the absolute file system path to the directory being visited.
    61  //
    62  // rel is the relative slash-separated path to the directory from the
    63  // repository root. Will be "" for the repository root directory itself.
    64  //
    65  // c is the configuration for the current directory. This may have been
    66  // modified by directives in the directory's build file.
    67  //
    68  // update is true when the build file may be updated.
    69  //
    70  // f is the existing build file in the directory. Will be nil if there
    71  // was no file.
    72  //
    73  // subdirs is a list of base names of subdirectories within dir, not
    74  // including excluded files.
    75  //
    76  // regularFiles is a list of base names of regular files within dir, not
    77  // including excluded files or symlinks.
    78  //
    79  // genFiles is a list of names of generated files, found by reading
    80  // "out" and "outs" attributes of rules in f.
    81  type WalkFunc func(dir, rel string, c *config.Config, update bool, f *rule.File, subdirs, regularFiles, genFiles []string)
    82  
    83  // Walk traverses the directory tree rooted at c.RepoRoot. Walk visits
    84  // subdirectories in depth-first post-order.
    85  //
    86  // When Walk visits a directory, it lists the files and subdirectories within
    87  // that directory. If a build file is present, Walk reads the build file and
    88  // applies any directives to the configuration (a copy of the parent directory's
    89  // configuration is made, and the copy is modified). After visiting
    90  // subdirectories, the callback wf may be called, depending on the mode.
    91  //
    92  // c is the root configuration to start with. This includes changes made by
    93  // command line flags, but not by the root build file. This configuration
    94  // should not be modified.
    95  //
    96  // cexts is a list of configuration extensions. When visiting a directory,
    97  // before visiting subdirectories, Walk makes a copy of the parent configuration
    98  // and Configure for each extension on the copy. If Walk sees a directive
    99  // that is not listed in KnownDirectives of any extension, an error will
   100  // be logged.
   101  //
   102  // dirs is a list of absolute, canonical file system paths of directories
   103  // to visit.
   104  //
   105  // mode determines whether subdirectories of dirs should be visited recursively,
   106  // when the wf callback should be called, and when the "update" argument
   107  // to the wf callback should be set.
   108  //
   109  // wf is a function that may be called in each directory.
   110  func Walk(c *config.Config, cexts []config.Configurer, dirs []string, mode Mode, wf WalkFunc) {
   111  	knownDirectives := make(map[string]bool)
   112  	for _, cext := range cexts {
   113  		for _, d := range cext.KnownDirectives() {
   114  			knownDirectives[d] = true
   115  		}
   116  	}
   117  
   118  	updateRels := buildUpdateRelMap(c.RepoRoot, dirs)
   119  
   120  	var visit func(*config.Config, string, string, bool)
   121  	visit = func(c *config.Config, dir, rel string, updateParent bool) {
   122  		haveError := false
   123  
   124  		// TODO: OPT: ReadDir stats all the files, which is slow. We just care about
   125  		// names and modes, so we should use something like
   126  		// golang.org/x/tools/internal/fastwalk to speed this up.
   127  		ents, err := os.ReadDir(dir)
   128  		if err != nil {
   129  			log.Print(err)
   130  			return
   131  		}
   132  
   133  		f, err := loadBuildFile(c, rel, dir, ents)
   134  		if err != nil {
   135  			log.Print(err)
   136  			if c.Strict {
   137  				// TODO(https://github.com/bazelbuild/bazel-gazelle/issues/1029):
   138  				// Refactor to accumulate and propagate errors to main.
   139  				log.Fatal("Exit as strict mode is on")
   140  			}
   141  			haveError = true
   142  		}
   143  
   144  		c = configure(cexts, knownDirectives, c, rel, f)
   145  		wc := getWalkConfig(c)
   146  
   147  		if wc.isExcluded(rel, ".") {
   148  			return
   149  		}
   150  
   151  		var subdirs, regularFiles []string
   152  		for _, ent := range ents {
   153  			base := ent.Name()
   154  			ent := resolveFileInfo(wc, dir, rel, ent)
   155  			switch {
   156  			case ent == nil:
   157  				continue
   158  			case ent.IsDir():
   159  				subdirs = append(subdirs, base)
   160  			default:
   161  				regularFiles = append(regularFiles, base)
   162  			}
   163  		}
   164  
   165  		shouldUpdate := shouldUpdate(rel, mode, updateParent, updateRels)
   166  		for _, sub := range subdirs {
   167  			if subRel := path.Join(rel, sub); shouldVisit(subRel, mode, shouldUpdate, updateRels) {
   168  				visit(c, filepath.Join(dir, sub), subRel, shouldUpdate)
   169  			}
   170  		}
   171  
   172  		update := !haveError && !wc.ignore && shouldUpdate
   173  		if shouldCall(rel, mode, updateParent, updateRels) {
   174  			genFiles := findGenFiles(wc, f)
   175  			wf(dir, rel, c, update, f, subdirs, regularFiles, genFiles)
   176  		}
   177  	}
   178  	visit(c, c.RepoRoot, "", false)
   179  }
   180  
   181  // buildUpdateRelMap builds a table of prefixes, used to determine which
   182  // directories to update and visit.
   183  //
   184  // root and dirs must be absolute, canonical file paths. Each entry in dirs
   185  // must be a subdirectory of root. The caller is responsible for checking this.
   186  //
   187  // buildUpdateRelMap returns a map from slash-separated paths relative to the
   188  // root directory ("" for the root itself) to a boolean indicating whether
   189  // the directory should be updated.
   190  func buildUpdateRelMap(root string, dirs []string) map[string]bool {
   191  	relMap := make(map[string]bool)
   192  	for _, dir := range dirs {
   193  		rel, _ := filepath.Rel(root, dir)
   194  		rel = filepath.ToSlash(rel)
   195  		if rel == "." {
   196  			rel = ""
   197  		}
   198  
   199  		i := 0
   200  		for {
   201  			next := strings.IndexByte(rel[i:], '/') + i
   202  			if next-i < 0 {
   203  				relMap[rel] = true
   204  				break
   205  			}
   206  			prefix := rel[:next]
   207  			if _, ok := relMap[prefix]; !ok {
   208  				relMap[prefix] = false
   209  			}
   210  			i = next + 1
   211  		}
   212  	}
   213  	return relMap
   214  }
   215  
   216  // shouldCall returns true if Walk should call the callback in the
   217  // directory rel.
   218  func shouldCall(rel string, mode Mode, updateParent bool, updateRels map[string]bool) bool {
   219  	switch mode {
   220  	case VisitAllUpdateSubdirsMode, VisitAllUpdateDirsMode:
   221  		return true
   222  	case UpdateSubdirsMode:
   223  		return updateParent || updateRels[rel]
   224  	default: // UpdateDirsMode
   225  		return updateRels[rel]
   226  	}
   227  }
   228  
   229  // shouldUpdate returns true if Walk should pass true to the callback's update
   230  // parameter in the directory rel. This indicates the build file should be
   231  // updated.
   232  func shouldUpdate(rel string, mode Mode, updateParent bool, updateRels map[string]bool) bool {
   233  	if (mode == VisitAllUpdateSubdirsMode || mode == UpdateSubdirsMode) && updateParent {
   234  		return true
   235  	}
   236  	return updateRels[rel]
   237  }
   238  
   239  // shouldVisit returns true if Walk should visit the subdirectory rel.
   240  func shouldVisit(rel string, mode Mode, updateParent bool, updateRels map[string]bool) bool {
   241  	switch mode {
   242  	case VisitAllUpdateSubdirsMode, VisitAllUpdateDirsMode:
   243  		return true
   244  	case UpdateSubdirsMode:
   245  		_, ok := updateRels[rel]
   246  		return ok || updateParent
   247  	default: // UpdateDirsMode
   248  		_, ok := updateRels[rel]
   249  		return ok
   250  	}
   251  }
   252  
   253  func loadBuildFile(c *config.Config, pkg, dir string, ents []fs.DirEntry) (*rule.File, error) {
   254  	var err error
   255  	readDir := dir
   256  	readEnts := ents
   257  	if c.ReadBuildFilesDir != "" {
   258  		readDir = filepath.Join(c.ReadBuildFilesDir, filepath.FromSlash(pkg))
   259  		readEnts, err = os.ReadDir(readDir)
   260  		if err != nil {
   261  			return nil, err
   262  		}
   263  	}
   264  	path := rule.MatchBuildFile(readDir, c.ValidBuildFileNames, readEnts)
   265  	if path == "" {
   266  		return nil, nil
   267  	}
   268  	return rule.LoadFile(path, pkg)
   269  }
   270  
   271  func configure(cexts []config.Configurer, knownDirectives map[string]bool, c *config.Config, rel string, f *rule.File) *config.Config {
   272  	if rel != "" {
   273  		c = c.Clone()
   274  	}
   275  	if f != nil {
   276  		for _, d := range f.Directives {
   277  			if !knownDirectives[d.Key] {
   278  				log.Printf("%s: unknown directive: gazelle:%s", f.Path, d.Key)
   279  				if c.Strict {
   280  					// TODO(https://github.com/bazelbuild/bazel-gazelle/issues/1029):
   281  					// Refactor to accumulate and propagate errors to main.
   282  					log.Fatal("Exit as strict mode is on")
   283  				}
   284  			}
   285  		}
   286  	}
   287  	for _, cext := range cexts {
   288  		cext.Configure(c, rel, f)
   289  	}
   290  	return c
   291  }
   292  
   293  func findGenFiles(wc *walkConfig, f *rule.File) []string {
   294  	if f == nil {
   295  		return nil
   296  	}
   297  	var strs []string
   298  	for _, r := range f.Rules {
   299  		for _, key := range []string{"out", "outs"} {
   300  			if s := r.AttrString(key); s != "" {
   301  				strs = append(strs, s)
   302  			} else if ss := r.AttrStrings(key); len(ss) > 0 {
   303  				strs = append(strs, ss...)
   304  			}
   305  		}
   306  	}
   307  
   308  	var genFiles []string
   309  	for _, s := range strs {
   310  		if !wc.isExcluded(f.Pkg, s) {
   311  			genFiles = append(genFiles, s)
   312  		}
   313  	}
   314  	return genFiles
   315  }
   316  
   317  func resolveFileInfo(wc *walkConfig, dir, rel string, ent fs.DirEntry) fs.DirEntry {
   318  	base := ent.Name()
   319  	if base == "" || wc.isExcluded(rel, base) {
   320  		return nil
   321  	}
   322  	if ent.Type()&os.ModeSymlink == 0 {
   323  		// Not a symlink, use the original FileInfo.
   324  		return ent
   325  	}
   326  	if !wc.shouldFollow(rel, ent.Name()) {
   327  		// A symlink, but not one we should follow.
   328  		return nil
   329  	}
   330  	fi, err := os.Stat(path.Join(dir, base))
   331  	if err != nil {
   332  		// A symlink, but not one we could resolve.
   333  		return nil
   334  	}
   335  	return fs.FileInfoToDirEntry(fi)
   336  }
   337
View as plain text