diff.go

Documentation: github.com/containerd/continuity/fs

     1  /*
     2     Copyright The containerd Authors.
     3  
     4     Licensed under the Apache License, Version 2.0 (the "License");
     5     you may not use this file except in compliance with the License.
     6     You may obtain a copy of the License at
     7  
     8         http://www.apache.org/licenses/LICENSE-2.0
     9  
    10     Unless required by applicable law or agreed to in writing, software
    11     distributed under the License is distributed on an "AS IS" BASIS,
    12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13     See the License for the specific language governing permissions and
    14     limitations under the License.
    15  */
    16  
    17  package fs
    18  
    19  import (
    20  	"context"
    21  	"os"
    22  	"path/filepath"
    23  	"strings"
    24  
    25  	"github.com/sirupsen/logrus"
    26  	"golang.org/x/sync/errgroup"
    27  )
    28  
    29  // ChangeKind is the type of modification that
    30  // a change is making.
    31  type ChangeKind int
    32  
    33  const (
    34  	// ChangeKindUnmodified represents an unmodified
    35  	// file
    36  	ChangeKindUnmodified = iota
    37  
    38  	// ChangeKindAdd represents an addition of
    39  	// a file
    40  	ChangeKindAdd
    41  
    42  	// ChangeKindModify represents a change to
    43  	// an existing file
    44  	ChangeKindModify
    45  
    46  	// ChangeKindDelete represents a delete of
    47  	// a file
    48  	ChangeKindDelete
    49  )
    50  
    51  func (k ChangeKind) String() string {
    52  	switch k {
    53  	case ChangeKindUnmodified:
    54  		return "unmodified"
    55  	case ChangeKindAdd:
    56  		return "add"
    57  	case ChangeKindModify:
    58  		return "modify"
    59  	case ChangeKindDelete:
    60  		return "delete"
    61  	default:
    62  		return ""
    63  	}
    64  }
    65  
    66  // Change represents single change between a diff and its parent.
    67  type Change struct {
    68  	Kind ChangeKind
    69  	Path string
    70  }
    71  
    72  // ChangeFunc is the type of function called for each change
    73  // computed during a directory changes calculation.
    74  type ChangeFunc func(ChangeKind, string, os.FileInfo, error) error
    75  
    76  // Changes computes changes between two directories calling the
    77  // given change function for each computed change. The first
    78  // directory is intended to the base directory and second
    79  // directory the changed directory.
    80  //
    81  // The change callback is called by the order of path names and
    82  // should be appliable in that order.
    83  //
    84  //	Due to this apply ordering, the following is true
    85  //	- Removed directory trees only create a single change for the root
    86  //	  directory removed. Remaining changes are implied.
    87  //	- A directory which is modified to become a file will not have
    88  //	  delete entries for sub-path items, their removal is implied
    89  //	  by the removal of the parent directory.
    90  //
    91  // Opaque directories will not be treated specially and each file
    92  // removed from the base directory will show up as a removal.
    93  //
    94  // File content comparisons will be done on files which have timestamps
    95  // which may have been truncated. If either of the files being compared
    96  // has a zero value nanosecond value, each byte will be compared for
    97  // differences. If 2 files have the same seconds value but different
    98  // nanosecond values where one of those values is zero, the files will
    99  // be considered unchanged if the content is the same. This behavior
   100  // is to account for timestamp truncation during archiving.
   101  func Changes(ctx context.Context, a, b string, changeFn ChangeFunc) error {
   102  	if a == "" {
   103  		logrus.Debugf("Using single walk diff for %s", b)
   104  		return addDirChanges(ctx, changeFn, b)
   105  	} else if diffOptions := detectDirDiff(b, a); diffOptions != nil {
   106  		logrus.Debugf("Using single walk diff for %s from %s", diffOptions.diffDir, a)
   107  		return diffDirChanges(ctx, changeFn, a, diffOptions)
   108  	}
   109  
   110  	logrus.Debugf("Using double walk diff for %s from %s", b, a)
   111  	return doubleWalkDiff(ctx, changeFn, a, b)
   112  }
   113  
   114  func addDirChanges(ctx context.Context, changeFn ChangeFunc, root string) error {
   115  	return filepath.Walk(root, func(path string, f os.FileInfo, err error) error {
   116  		if err != nil {
   117  			return err
   118  		}
   119  
   120  		// Rebase path
   121  		path, err = filepath.Rel(root, path)
   122  		if err != nil {
   123  			return err
   124  		}
   125  
   126  		path = filepath.Join(string(os.PathSeparator), path)
   127  
   128  		// Skip root
   129  		if path == string(os.PathSeparator) {
   130  			return nil
   131  		}
   132  
   133  		return changeFn(ChangeKindAdd, path, f, nil)
   134  	})
   135  }
   136  
   137  // diffDirOptions is used when the diff can be directly calculated from
   138  // a diff directory to its base, without walking both trees.
   139  type diffDirOptions struct {
   140  	diffDir      string
   141  	skipChange   func(string) (bool, error)
   142  	deleteChange func(string, string, os.FileInfo) (string, error)
   143  }
   144  
   145  // diffDirChanges walks the diff directory and compares changes against the base.
   146  func diffDirChanges(ctx context.Context, changeFn ChangeFunc, base string, o *diffDirOptions) error {
   147  	changedDirs := make(map[string]struct{})
   148  	return filepath.Walk(o.diffDir, func(path string, f os.FileInfo, err error) error {
   149  		if err != nil {
   150  			return err
   151  		}
   152  
   153  		// Rebase path
   154  		path, err = filepath.Rel(o.diffDir, path)
   155  		if err != nil {
   156  			return err
   157  		}
   158  
   159  		path = filepath.Join(string(os.PathSeparator), path)
   160  
   161  		// Skip root
   162  		if path == string(os.PathSeparator) {
   163  			return nil
   164  		}
   165  
   166  		// TODO: handle opaqueness, start new double walker at this
   167  		// location to get deletes, and skip tree in single walker
   168  
   169  		if o.skipChange != nil {
   170  			if skip, err := o.skipChange(path); skip {
   171  				return err
   172  			}
   173  		}
   174  
   175  		var kind ChangeKind
   176  
   177  		deletedFile, err := o.deleteChange(o.diffDir, path, f)
   178  		if err != nil {
   179  			return err
   180  		}
   181  
   182  		// Find out what kind of modification happened
   183  		if deletedFile != "" {
   184  			path = deletedFile
   185  			kind = ChangeKindDelete
   186  			f = nil
   187  		} else {
   188  			// Otherwise, the file was added
   189  			kind = ChangeKindAdd
   190  
   191  			// ...Unless it already existed in a base, in which case, it's a modification
   192  			stat, err := os.Stat(filepath.Join(base, path))
   193  			if err != nil && !os.IsNotExist(err) {
   194  				return err
   195  			}
   196  			if err == nil {
   197  				// The file existed in the base, so that's a modification
   198  
   199  				// However, if it's a directory, maybe it wasn't actually modified.
   200  				// If you modify /foo/bar/baz, then /foo will be part of the changed files only because it's the parent of bar
   201  				if stat.IsDir() && f.IsDir() {
   202  					if f.Size() == stat.Size() && f.Mode() == stat.Mode() && sameFsTime(f.ModTime(), stat.ModTime()) {
   203  						// Both directories are the same, don't record the change
   204  						return nil
   205  					}
   206  				}
   207  				kind = ChangeKindModify
   208  			}
   209  		}
   210  
   211  		// If /foo/bar/file.txt is modified, then /foo/bar must be part of the changed files.
   212  		// This block is here to ensure the change is recorded even if the
   213  		// modify time, mode and size of the parent directory in the rw and ro layers are all equal.
   214  		// Check https://github.com/docker/docker/pull/13590 for details.
   215  		if f.IsDir() {
   216  			changedDirs[path] = struct{}{}
   217  		}
   218  		if kind == ChangeKindAdd || kind == ChangeKindDelete {
   219  			parent := filepath.Dir(path)
   220  			if _, ok := changedDirs[parent]; !ok && parent != "/" {
   221  				pi, err := os.Stat(filepath.Join(o.diffDir, parent))
   222  				if err := changeFn(ChangeKindModify, parent, pi, err); err != nil {
   223  					return err
   224  				}
   225  				changedDirs[parent] = struct{}{}
   226  			}
   227  		}
   228  
   229  		return changeFn(kind, path, f, nil)
   230  	})
   231  }
   232  
   233  // doubleWalkDiff walks both directories to create a diff
   234  func doubleWalkDiff(ctx context.Context, changeFn ChangeFunc, a, b string) (err error) {
   235  	g, ctx := errgroup.WithContext(ctx)
   236  
   237  	var (
   238  		c1 = make(chan *currentPath)
   239  		c2 = make(chan *currentPath)
   240  
   241  		f1, f2 *currentPath
   242  		rmdir  string
   243  	)
   244  	g.Go(func() error {
   245  		defer close(c1)
   246  		return pathWalk(ctx, a, c1)
   247  	})
   248  	g.Go(func() error {
   249  		defer close(c2)
   250  		return pathWalk(ctx, b, c2)
   251  	})
   252  	g.Go(func() error {
   253  		for c1 != nil || c2 != nil {
   254  			if f1 == nil && c1 != nil {
   255  				f1, err = nextPath(ctx, c1)
   256  				if err != nil {
   257  					return err
   258  				}
   259  				if f1 == nil {
   260  					c1 = nil
   261  				}
   262  			}
   263  
   264  			if f2 == nil && c2 != nil {
   265  				f2, err = nextPath(ctx, c2)
   266  				if err != nil {
   267  					return err
   268  				}
   269  				if f2 == nil {
   270  					c2 = nil
   271  				}
   272  			}
   273  			if f1 == nil && f2 == nil {
   274  				continue
   275  			}
   276  
   277  			var f os.FileInfo
   278  			k, p := pathChange(f1, f2)
   279  			switch k {
   280  			case ChangeKindAdd:
   281  				if rmdir != "" {
   282  					rmdir = ""
   283  				}
   284  				f = f2.f
   285  				f2 = nil
   286  			case ChangeKindDelete:
   287  				// Check if this file is already removed by being
   288  				// under of a removed directory
   289  				if rmdir != "" && strings.HasPrefix(f1.path, rmdir) {
   290  					f1 = nil
   291  					continue
   292  				} else if f1.f.IsDir() {
   293  					rmdir = f1.path + string(os.PathSeparator)
   294  				} else if rmdir != "" {
   295  					rmdir = ""
   296  				}
   297  				f1 = nil
   298  			case ChangeKindModify:
   299  				same, err := sameFile(f1, f2)
   300  				if err != nil {
   301  					return err
   302  				}
   303  				if f1.f.IsDir() && !f2.f.IsDir() {
   304  					rmdir = f1.path + string(os.PathSeparator)
   305  				} else if rmdir != "" {
   306  					rmdir = ""
   307  				}
   308  				f = f2.f
   309  				f1 = nil
   310  				f2 = nil
   311  				if same {
   312  					if !isLinked(f) {
   313  						continue
   314  					}
   315  					k = ChangeKindUnmodified
   316  				}
   317  			}
   318  			if err := changeFn(k, p, f, nil); err != nil {
   319  				return err
   320  			}
   321  		}
   322  		return nil
   323  	})
   324  
   325  	return g.Wait()
   326  }
   327
View as plain text