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