From 576709ad30571d7fb11d15229719c693cf0e92c4 Mon Sep 17 00:00:00 2001 From: Alex Goodman Date: Sat, 21 Sep 2019 16:28:45 -0400 Subject: rework package structure --- Makefile | 2 +- cmd/root.go | 2 +- filetree/cache.go | 79 -- filetree/data.go | 161 ----- filetree/data_test.go | 41 -- filetree/efficiency.go | 111 --- filetree/efficiency_test.go | 80 --- filetree/node.go | 315 -------- filetree/node_test.go | 168 ----- filetree/tree.go | 371 ---------- filetree/tree_test.go | 791 --------------------- filetree/types.go | 66 -- go.mod | 1 + go.sum | 2 + image/docker_image.go | 293 -------- image/docker_layer.go | 78 -- image/root.go | 10 - image/testing.go | 19 - image/types.go | 80 --- runtime/ci/evaluator.go | 187 +++++ runtime/ci/evaluator_test.go | 61 ++ runtime/ci/reference_file.go | 7 + runtime/ci/rule.go | 168 +++++ runtime/ci_evaluator.go | 186 ----- runtime/ci_evaluator_test.go | 61 -- runtime/ci_rule.go | 168 ----- runtime/export.go | 74 -- runtime/export/export.go | 79 ++ runtime/export/export_test.go | 134 ++++ runtime/export_test.go | 135 ---- runtime/reference_file.go | 7 - runtime/run.go | 32 +- runtime/ui/details_controller.go | 149 ++++ runtime/ui/filetree_controller.go | 403 +++++++++++ runtime/ui/filetree_viewmodel.go | 425 +++++++++++ runtime/ui/filetree_viewmodel_test.go | 385 ++++++++++ runtime/ui/filter_controller.go | 113 +++ runtime/ui/layer_controller.go | 313 ++++++++ runtime/ui/status_controller.go | 77 ++ .../ui/testdata/TestFileShowAggregateChanges.txt | 36 + runtime/ui/testdata/TestFileTreeDirCollapse.txt | 13 + runtime/ui/testdata/TestFileTreeDirCollapseAll.txt | 9 + runtime/ui/testdata/TestFileTreeDirCursorRight.txt | 22 + runtime/ui/testdata/TestFileTreeFilterTree.txt | 7 + runtime/ui/testdata/TestFileTreeGoCase.txt | 416 +++++++++++ .../TestFileTreeHideAddedRemovedModified.txt | 21 + .../ui/testdata/TestFileTreeHideTypeWithFilter.txt | 1 + runtime/ui/testdata/TestFileTreeHideUnmodified.txt | 10 + runtime/ui/testdata/TestFileTreeNoAttributes.txt | 416 +++++++++++ runtime/ui/testdata/TestFileTreePageDown.txt | 11 + runtime/ui/testdata/TestFileTreePageUp.txt | 11 + .../ui/testdata/TestFileTreeRestrictedHeight.txt | 22 + runtime/ui/testdata/TestFileTreeSelectLayer.txt | 23 + runtime/ui/ui.go | 395 ++++++++++ ui/details_controller.go | 149 ---- ui/filetree_controller.go | 403 ----------- ui/filetree_viewmodel.go | 425 ----------- ui/filetree_viewmodel_test.go | 385 ---------- ui/filter_controller.go | 113 --- ui/layer_controller.go | 314 -------- ui/status_controller.go | 77 -- ui/testdata/TestFileShowAggregateChanges.txt | 36 - ui/testdata/TestFileTreeDirCollapse.txt | 13 - ui/testdata/TestFileTreeDirCollapseAll.txt | 9 - ui/testdata/TestFileTreeDirCursorRight.txt | 22 - ui/testdata/TestFileTreeFilterTree.txt | 7 - ui/testdata/TestFileTreeGoCase.txt | 416 ----------- .../TestFileTreeHideAddedRemovedModified.txt | 21 - ui/testdata/TestFileTreeHideTypeWithFilter.txt | 1 - ui/testdata/TestFileTreeHideUnmodified.txt | 10 - ui/testdata/TestFileTreeNoAttributes.txt | 416 ----------- ui/testdata/TestFileTreePageDown.txt | 11 - ui/testdata/TestFileTreePageUp.txt | 11 - ui/testdata/TestFileTreeRestrictedHeight.txt | 22 - ui/testdata/TestFileTreeSelectLayer.txt | 23 - ui/ui.go | 395 ---------- utils/format.go | 9 + 77 files changed, 3943 insertions(+), 6592 deletions(-) delete mode 100644 filetree/cache.go delete mode 100644 filetree/data.go delete mode 100644 filetree/data_test.go delete mode 100644 filetree/efficiency.go delete mode 100644 filetree/efficiency_test.go delete mode 100644 filetree/node.go delete mode 100644 filetree/node_test.go delete mode 100644 filetree/tree.go delete mode 100644 filetree/tree_test.go delete mode 100644 filetree/types.go delete mode 100644 image/docker_image.go delete mode 100644 image/docker_layer.go delete mode 100644 image/root.go delete mode 100644 image/testing.go delete mode 100644 image/types.go create mode 100644 runtime/ci/evaluator.go create mode 100644 runtime/ci/evaluator_test.go create mode 100644 runtime/ci/reference_file.go create mode 100644 runtime/ci/rule.go delete mode 100644 runtime/ci_evaluator.go delete mode 100644 runtime/ci_evaluator_test.go delete mode 100644 runtime/ci_rule.go delete mode 100644 runtime/export.go create mode 100644 runtime/export/export.go create mode 100644 runtime/export/export_test.go delete mode 100644 runtime/export_test.go delete mode 100644 runtime/reference_file.go create mode 100644 runtime/ui/details_controller.go create mode 100644 runtime/ui/filetree_controller.go create mode 100644 runtime/ui/filetree_viewmodel.go create mode 100644 runtime/ui/filetree_viewmodel_test.go create mode 100644 runtime/ui/filter_controller.go create mode 100644 runtime/ui/layer_controller.go create mode 100644 runtime/ui/status_controller.go create mode 100644 runtime/ui/testdata/TestFileShowAggregateChanges.txt create mode 100644 runtime/ui/testdata/TestFileTreeDirCollapse.txt create mode 100644 runtime/ui/testdata/TestFileTreeDirCollapseAll.txt create mode 100644 runtime/ui/testdata/TestFileTreeDirCursorRight.txt create mode 100644 runtime/ui/testdata/TestFileTreeFilterTree.txt create mode 100644 runtime/ui/testdata/TestFileTreeGoCase.txt create mode 100644 runtime/ui/testdata/TestFileTreeHideAddedRemovedModified.txt create mode 100644 runtime/ui/testdata/TestFileTreeHideTypeWithFilter.txt create mode 100644 runtime/ui/testdata/TestFileTreeHideUnmodified.txt create mode 100644 runtime/ui/testdata/TestFileTreeNoAttributes.txt create mode 100644 runtime/ui/testdata/TestFileTreePageDown.txt create mode 100644 runtime/ui/testdata/TestFileTreePageUp.txt create mode 100644 runtime/ui/testdata/TestFileTreeRestrictedHeight.txt create mode 100644 runtime/ui/testdata/TestFileTreeSelectLayer.txt create mode 100644 runtime/ui/ui.go delete mode 100644 ui/details_controller.go delete mode 100644 ui/filetree_controller.go delete mode 100644 ui/filetree_viewmodel.go delete mode 100644 ui/filetree_viewmodel_test.go delete mode 100644 ui/filter_controller.go delete mode 100644 ui/layer_controller.go delete mode 100644 ui/status_controller.go delete mode 100644 ui/testdata/TestFileShowAggregateChanges.txt delete mode 100644 ui/testdata/TestFileTreeDirCollapse.txt delete mode 100644 ui/testdata/TestFileTreeDirCollapseAll.txt delete mode 100644 ui/testdata/TestFileTreeDirCursorRight.txt delete mode 100644 ui/testdata/TestFileTreeFilterTree.txt delete mode 100644 ui/testdata/TestFileTreeGoCase.txt delete mode 100644 ui/testdata/TestFileTreeHideAddedRemovedModified.txt delete mode 100644 ui/testdata/TestFileTreeHideTypeWithFilter.txt delete mode 100644 ui/testdata/TestFileTreeHideUnmodified.txt delete mode 100644 ui/testdata/TestFileTreeNoAttributes.txt delete mode 100644 ui/testdata/TestFileTreePageDown.txt delete mode 100644 ui/testdata/TestFileTreePageUp.txt delete mode 100644 ui/testdata/TestFileTreeRestrictedHeight.txt delete mode 100644 ui/testdata/TestFileTreeSelectLayer.txt delete mode 100644 ui/ui.go create mode 100644 utils/format.go diff --git a/Makefile b/Makefile index 06cf507..15a0574 100644 --- a/Makefile +++ b/Makefile @@ -30,7 +30,7 @@ test-coverage: build ./.scripts/test-coverage.sh validate: - grep -R 'const allowTestDataCapture = false' ui/ + grep -R 'const allowTestDataCapture = false' runtime/ui/ go vet ./... @! gofmt -s -l . 2>&1 | grep -vE '^\.git/' | grep -vE '^\.cache/' golangci-lint run diff --git a/cmd/root.go b/cmd/root.go index 2ed2534..9dadad2 100644 --- a/cmd/root.go +++ b/cmd/root.go @@ -2,6 +2,7 @@ package cmd import ( "fmt" + "github.com/wagoodman/dive/dive/filetree" "io/ioutil" "os" "path" @@ -11,7 +12,6 @@ import ( log "github.com/sirupsen/logrus" "github.com/spf13/cobra" "github.com/spf13/viper" - "github.com/wagoodman/dive/filetree" "github.com/wagoodman/dive/utils" ) diff --git a/filetree/cache.go b/filetree/cache.go deleted file mode 100644 index 82c1795..0000000 --- a/filetree/cache.go +++ /dev/null @@ -1,79 +0,0 @@ -package filetree - -import ( - "github.com/sirupsen/logrus" -) - -type TreeCacheKey struct { - bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop int -} - -type TreeCache struct { - refTrees []*FileTree - cache map[TreeCacheKey]*FileTree -} - -func (cache *TreeCache) Get(bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop int) *FileTree { - key := TreeCacheKey{bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop} - if value, exists := cache.cache[key]; exists { - return value - } - - value := cache.buildTree(key) - cache.cache[key] = value - return value -} - -func (cache *TreeCache) buildTree(key TreeCacheKey) *FileTree { - newTree := StackTreeRange(cache.refTrees, key.bottomTreeStart, key.bottomTreeStop) - for idx := key.topTreeStart; idx <= key.topTreeStop; idx++ { - err := newTree.CompareAndMark(cache.refTrees[idx]) - if err != nil { - logrus.Errorf("unable to build tree: %+v", err) - } - } - return newTree -} - -func (cache *TreeCache) Build() { - var bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop int - - // case 1: layer compare (top tree SIZE is fixed (BUT floats forward), Bottom tree SIZE changes) - for selectIdx := 0; selectIdx < len(cache.refTrees); selectIdx++ { - bottomTreeStart = 0 - topTreeStop = selectIdx - - if selectIdx == 0 { - bottomTreeStop = selectIdx - topTreeStart = selectIdx - } else { - bottomTreeStop = selectIdx - 1 - topTreeStart = selectIdx - } - - cache.Get(bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop) - } - - // case 2: aggregated compare (bottom tree is ENTIRELY fixed, top tree SIZE changes) - for selectIdx := 0; selectIdx < len(cache.refTrees); selectIdx++ { - bottomTreeStart = 0 - topTreeStop = selectIdx - if selectIdx == 0 { - bottomTreeStop = selectIdx - topTreeStart = selectIdx - } else { - bottomTreeStop = 0 - topTreeStart = 1 - } - - cache.Get(bottomTreeStart, bottomTreeStop, topTreeStart, topTreeStop) - } -} - -func NewFileTreeCache(refTrees []*FileTree) TreeCache { - - return TreeCache{ - refTrees: refTrees, - cache: make(map[TreeCacheKey]*FileTree), - } -} diff --git a/filetree/data.go b/filetree/data.go deleted file mode 100644 index 743ecb0..0000000 --- a/filetree/data.go +++ /dev/null @@ -1,161 +0,0 @@ -package filetree - -import ( - "archive/tar" - "fmt" - "io" - - "github.com/cespare/xxhash" - "github.com/sirupsen/logrus" -) - -const ( - Unmodified DiffType = iota - Modified - Added - Removed -) - -var GlobalFileTreeCollapse bool - -// NewNodeData creates an empty NodeData struct for a FileNode -func NewNodeData() *NodeData { - return &NodeData{ - ViewInfo: *NewViewInfo(), - FileInfo: FileInfo{}, - DiffType: Unmodified, - } -} - -// Copy duplicates a NodeData -func (data *NodeData) Copy() *NodeData { - return &NodeData{ - ViewInfo: *data.ViewInfo.Copy(), - FileInfo: *data.FileInfo.Copy(), - DiffType: data.DiffType, - } -} - -// NewViewInfo creates a default ViewInfo -func NewViewInfo() (view *ViewInfo) { - return &ViewInfo{ - Collapsed: GlobalFileTreeCollapse, - Hidden: false, - } -} - -// Copy duplicates a ViewInfo -func (view *ViewInfo) Copy() (newView *ViewInfo) { - newView = NewViewInfo() - *newView = *view - return newView -} - -func getHashFromReader(reader io.Reader) uint64 { - h := xxhash.New() - - buf := make([]byte, 1024) - for { - n, err := reader.Read(buf) - if err != nil && err != io.EOF { - logrus.Panic(err) - } - if n == 0 { - break - } - - _, err = h.Write(buf[:n]) - if err != nil { - logrus.Panic(err) - } - } - - return h.Sum64() -} - -// NewFileInfo extracts the metadata from a tar header and file contents and generates a new FileInfo object. -func NewFileInfo(reader *tar.Reader, header *tar.Header, path string) FileInfo { - if header.Typeflag == tar.TypeDir { - return FileInfo{ - Path: path, - TypeFlag: header.Typeflag, - Linkname: header.Linkname, - hash: 0, - Size: header.FileInfo().Size(), - Mode: header.FileInfo().Mode(), - Uid: header.Uid, - Gid: header.Gid, - IsDir: header.FileInfo().IsDir(), - } - } - - hash := getHashFromReader(reader) - - return FileInfo{ - Path: path, - TypeFlag: header.Typeflag, - Linkname: header.Linkname, - hash: hash, - Size: header.FileInfo().Size(), - Mode: header.FileInfo().Mode(), - Uid: header.Uid, - Gid: header.Gid, - IsDir: header.FileInfo().IsDir(), - } -} - -// Copy duplicates a FileInfo -func (data *FileInfo) Copy() *FileInfo { - if data == nil { - return nil - } - return &FileInfo{ - Path: data.Path, - TypeFlag: data.TypeFlag, - Linkname: data.Linkname, - hash: data.hash, - Size: data.Size, - Mode: data.Mode, - Uid: data.Uid, - Gid: data.Gid, - IsDir: data.IsDir, - } -} - -// Compare determines the DiffType between two FileInfos based on the type and contents of each given FileInfo -func (data *FileInfo) Compare(other FileInfo) DiffType { - if data.TypeFlag == other.TypeFlag { - if data.hash == other.hash && - data.Mode == other.Mode && - data.Uid == other.Uid && - data.Gid == other.Gid { - return Unmodified - } - } - return Modified -} - -// String of a DiffType -func (diff DiffType) String() string { - switch diff { - case Unmodified: - return "Unmodified" - case Modified: - return "Modified" - case Added: - return "Added" - case Removed: - return "Removed" - default: - return fmt.Sprintf("%d", int(diff)) - } -} - -// merge two DiffTypes into a single result. Essentially, return the given value unless they two values differ, -// in which case we can only determine that there is "a change". -func (diff DiffType) merge(other DiffType) DiffType { - if diff == other { - return diff - } - return Modified -} diff --git a/filetree/data_test.go b/filetree/data_test.go deleted file mode 100644 index 351d6df..0000000 --- a/filetree/data_test.go +++ /dev/null @@ -1,41 +0,0 @@ -package filetree - -import ( - "testing" -) - -func TestAssignDiffType(t *testing.T) { - tree := NewFileTree() - node, _, err := tree.AddPath("/usr", *BlankFileChangeInfo("/usr")) - if err != nil { - t.Errorf("Expected no error from fetching path. got: %v", err) - } - node.Data.DiffType = Modified - if tree.Root.Children["usr"].Data.DiffType != Modified { - t.Fail() - } -} - -func TestMergeDiffTypes(t *testing.T) { - a := Unmodified - b := Unmodified - merged := a.merge(b) - if merged != Unmodified { - t.Errorf("Expected Unchaged (0) but got %v", merged) - } - a = Modified - b = Unmodified - merged = a.merge(b) - if merged != Modified { - t.Errorf("Expected Unchaged (0) but got %v", merged) - } -} - -func BlankFileChangeInfo(path string) (f *FileInfo) { - result := FileInfo{ - Path: path, - TypeFlag: 1, - hash: 123, - } - return &result -} diff --git a/filetree/efficiency.go b/filetree/efficiency.go deleted file mode 100644 index e0b21cf..0000000 --- a/filetree/efficiency.go +++ /dev/null @@ -1,111 +0,0 @@ -package filetree - -import ( - "fmt" - "sort" - - "github.com/sirupsen/logrus" -) - -// Len is required for sorting. -func (efs EfficiencySlice) Len() int { - return len(efs) -} - -// Swap operation is required for sorting. -func (efs EfficiencySlice) Swap(i, j int) { - efs[i], efs[j] = efs[j], efs[i] -} - -// Less comparison is required for sorting. -func (efs EfficiencySlice) Less(i, j int) bool { - return efs[i].CumulativeSize < efs[j].CumulativeSize -} - -// Efficiency returns the score and file set of the given set of FileTrees (layers). This is loosely based on: -// 1. Files that are duplicated across layers discounts your score, weighted by file size -// 2. Files that are removed discounts your score, weighted by the original file size -func Efficiency(trees []*FileTree) (float64, EfficiencySlice) { - efficiencyMap := make(map[string]*EfficiencyData) - inefficientMatches := make(EfficiencySlice, 0) - currentTree := 0 - - visitor := func(node *FileNode) error { - path := node.Path() - if _, ok := efficiencyMap[path]; !ok { - efficiencyMap[path] = &EfficiencyData{ - Path: path, - Nodes: make([]*FileNode, 0), - minDiscoveredSize: -1, - } - } - data := efficiencyMap[path] - - // this node may have had children that were deleted, however, we won't explicitly list out every child, only - // the top-most parent with the cumulative size. These operations will need to be done on the full (stacked) - // tree. - // Note: whiteout files may also represent directories, so we need to find out if this was previously a file or dir. - var sizeBytes int64 - - if node.IsWhiteout() { - sizer := func(curNode *FileNode) error { - sizeBytes += curNode.Data.FileInfo.Size - return nil - } - stackedTree := StackTreeRange(trees, 0, currentTree-1) - previousTreeNode, err := stackedTree.GetNode(node.Path()) - if err != nil { - logrus.Debug(fmt.Sprintf("CurrentTree: %d : %s", currentTree, err)) - } else if previousTreeNode.Data.FileInfo.IsDir { - err = previousTreeNode.VisitDepthChildFirst(sizer, nil) - if err != nil { - logrus.Errorf("unable to propagate whiteout dir: %+v", err) - } - } - - } else { - sizeBytes = node.Data.FileInfo.Size - } - - data.CumulativeSize += sizeBytes - if data.minDiscoveredSize < 0 || sizeBytes < data.minDiscoveredSize { - data.minDiscoveredSize = sizeBytes - } - data.Nodes = append(data.Nodes, node) - - if len(data.Nodes) == 2 { - inefficientMatches = append(inefficientMatches, data) - } - - return nil - } - visitEvaluator := func(node *FileNode) bool { - return node.IsLeaf() - } - for idx, tree := range trees { - currentTree = idx - err := tree.VisitDepthChildFirst(visitor, visitEvaluator) - if err != nil { - logrus.Errorf("unable to propagate ref tree: %+v", err) - } - } - - // calculate the score - var minimumPathSizes int64 - var discoveredPathSizes int64 - - for _, value := range efficiencyMap { - minimumPathSizes += value.minDiscoveredSize - discoveredPathSizes += value.CumulativeSize - } - var score float64 - if discoveredPathSizes == 0 { - score = 1.0 - } else { - score = float64(minimumPathSizes) / float64(discoveredPathSizes) - } - - sort.Sort(inefficientMatches) - - return score, inefficientMatches -} diff --git a/filetree/efficiency_test.go b/filetree/efficiency_test.go deleted file mode 100644 index 831ceb5..0000000 --- a/filetree/efficiency_test.go +++ /dev/null @@ -1,80 +0,0 @@ -package filetree - -import ( - "testing" -) - -func checkError(t *testing.T, err error, message string) { - if err != nil { - t.Errorf(message+": %+v", err) - } -} - -func TestEfficency(t *testing.T) { - trees := make([]*FileTree, 3) - for idx := range trees { - trees[idx] = NewFileTree() - } - - _, _, err := trees[0].AddPath("/etc/nginx/nginx.conf", FileInfo{Size: 2000}) - checkError(t, err, "could not setup test") - - _, _, err = trees[0].AddPath("/etc/nginx/public", FileInfo{Size: 3000}) - checkError(t, err, "could not setup test") - - _, _, err = trees[1].AddPath("/etc/nginx/nginx.conf", FileInfo{Size: 5000}) - checkError(t, err, "could not setup test") - _, _, err = trees[1].AddPath("/etc/athing", FileInfo{Size: 10000}) - checkError(t, err, "could not setup test") - - _, _, err = trees[2].AddPath("/etc/.wh.nginx", *BlankFileChangeInfo("/etc/.wh.nginx")) - checkError(t, err, "could not setup test") - - var expectedScore = 0.75 - var expectedMatches = EfficiencySlice{ - &EfficiencyData{Path: "/etc/nginx/nginx.conf", CumulativeSize: 7000}, - } - actualScore, actualMatches := Efficiency(trees) - - if expectedScore != actualScore { - t.Errorf("Expected score of %v but go %v", expectedScore, actualScore) - } - - if len(actualMatches) != len(expectedMatches) { - for _, match := range actualMatches { - t.Logf(" match: %+v", match) - } - t.Fatalf("Expected to find %d inefficient paths, but found %d", len(expectedMatches), len(actualMatches)) - } - - if expectedMatches[0].Path != actualMatches[0].Path { - t.Errorf("Expected path of %s but go %s", expectedMatches[0].Path, actualMatches[0].Path) - } - - if expectedMatches[0].CumulativeSize != actualMatches[0].CumulativeSize { - t.Errorf("Expected cumulative size of %v but go %v", expectedMatches[0].CumulativeSize, actualMatches[0].CumulativeSize) - } -} - -func TestEfficency_ScratchImage(t *testing.T) { - trees := make([]*FileTree, 3) - for idx := range trees { - trees[idx] = NewFileTree() - } - - _, _, err := trees[0].AddPath("/nothing", FileInfo{Size: 0}) - checkError(t, err, "could not setup test") - - var expectedScore = 1.0 - var expectedMatches = EfficiencySlice{} - actualScore, actualMatches := Efficiency(trees) - - if expectedScore != actualScore { - t.Errorf("Expected score of %v but go %v", expectedScore, actualScore) - } - - if len(actualMatches) > 0 { - t.Fatalf("Expected to find %d inefficient paths, but found %d", len(expectedMatches), len(actualMatches)) - } - -} diff --git a/filetree/node.go b/filetree/node.go deleted file mode 100644 index d136f0d..0000000 --- a/filetree/node.go +++ /dev/null @@ -1,315 +0,0 @@ -package filetree - -import ( - "archive/tar" - "fmt" - "sort" - "strings" - - "github.com/sirupsen/logrus" - - "github.com/dustin/go-humanize" - "github.com/fatih/color" - "github.com/phayes/permbits" -) - -const ( - AttributeFormat = "%s%s %11s %10s " -) - -var diffTypeColor = map[DiffType]*color.Color{ - Added: color.New(color.FgGreen), - Removed: color.New(color.FgRed), - Modified: color.New(color.FgYellow), - Unmodified: color.New(color.Reset), -} - -// NewNode creates a new FileNode relative to the given parent node with a payload. -func NewNode(parent *FileNode, name string, data FileInfo) (node *FileNode) { - node = new(FileNode) - node.Name = name - node.Data = *NewNodeData() - node.Data.FileInfo = *data.Copy() - - node.Children = make(map[string]*FileNode) - node.Parent = parent - if parent != nil { - node.Tree = parent.Tree - } - - return node -} - -// renderTreeLine returns a string representing this FileNode in the context of a greater ASCII tree. -func (node *FileNode) renderTreeLine(spaces []bool, last bool, collapsed bool) string { - var otherBranches string - for _, space := range spaces { - if space { - otherBranches += noBranchSpace - } else { - otherBranches += branchSpace - } - } - - thisBranch := middleItem - if last { - thisBranch = lastItem - } - - collapsedIndicator := uncollapsedItem - if collapsed { - collapsedIndicator = collapsedItem - } - - return otherBranches + thisBranch + collapsedIndicator + node.String() + newLine -} - -// Copy duplicates the existing node relative to a new parent node. -func (node *FileNode) Copy(parent *FileNode) *FileNode { - newNode := NewNode(parent, node.Name, node.Data.FileInfo) - newNode.Data.ViewInfo = node.Data.ViewInfo - newNode.Data.DiffType = node.Data.DiffType - for name, child := range node.Children { - newNode.Children[name] = child.Copy(newNode) - child.Parent = newNode - } - return newNode -} - -// AddChild creates a new node relative to the current FileNode. -func (node *FileNode) AddChild(name string, data FileInfo) (child *FileNode) { - // never allow processing of purely whiteout flag files (for now) - if strings.HasPrefix(name, doubleWhiteoutPrefix) { - return nil - } - - child = NewNode(node, name, data) - if node.Children[name] != nil { - // tree node already exists, replace the payload, keep the children - node.Children[name].Data.FileInfo = *data.Copy() - } else { - node.Children[name] = child - node.Tree.Size++ - } - - return child -} - -// Remove deletes the current FileNode from it's parent FileNode's relations. -func (node *FileNode) Remove() error { - if node == node.Tree.Root { - return fmt.Errorf("cannot remove the tree root") - } - for _, child := range node.Children { - err := child.Remove() - if err != nil { - return err - } - } - delete(node.Parent.Children, node.Name) - node.Tree.Size-- - return nil -} - -// String shows the filename formatted into the proper color (by DiffType), additionally indicating if it is a symlink. -func (node *FileNode) String() string { - var display string - if node == nil { - return "" - } - - display = node.Name - if node.Data.FileInfo.TypeFlag == tar.TypeSymlink || node.Data.FileInfo.TypeFlag == tar.TypeLink { - display += " → " + node.Data.FileInfo.Linkname - } - return diffTypeColor[node.Data.DiffType].Sprint(display) -} - -// MetadatString returns the FileNode metadata in a columnar string. -func (node *FileNode) MetadataString() string { - if node == nil { - return "" - } - - fileMode := permbits.FileMode(node.Data.FileInfo.Mode).String() - dir := "-" - if node.Data.FileInfo.IsDir { - dir = "d" - } - user := node.Data.FileInfo.Uid - group := node.Data.FileInfo.Gid - userGroup := fmt.Sprintf("%d:%d", user, group) - - var sizeBytes int64 - - if node.IsLeaf() { - sizeBytes = node.Data.FileInfo.Size - } else { - sizer := func(curNode *FileNode) error { - // don't include file sizes of children that have been removed (unless the node in question is a removed dir, - // then show the accumulated size of removed files) - if curNode.Data.DiffType != Removed || node.Data.DiffType == Removed { - sizeBytes += curNode.Data.FileInfo.Size - } - return nil - } - - err := node.VisitDepthChildFirst(sizer, nil) - if err != nil { - logrus.Errorf("unable to propagate node for metadata: %+v", err) - } - } - - size := humanize.Bytes(uint64(sizeBytes)) - - return diffTypeColor[node.Data.DiffType].Sprint(fmt.Sprintf(AttributeFormat, dir, fileMode, userGroup, size)) -} - -// VisitDepthChildFirst iterates a tree depth-first (starting at this FileNode), evaluating the deepest depths first (visit on bubble up) -func (node *FileNode) VisitDepthChildFirst(visitor Visitor, evaluator VisitEvaluator) error { - var keys []string - for key := range node.Children { - keys = append(keys, key) - } - sort.Strings(keys) - for _, name := range keys { - child := node.Children[name] - err := child.VisitDepthChildFirst(visitor, evaluator) - if err != nil { - return err - } - } - // never visit the root node - if node == node.Tree.Root { - return nil - } else if evaluator != nil && evaluator(node) || evaluator == nil { - return visitor(node) - } - - return nil -} - -// VisitDepthParentFirst iterates a tree depth-first (starting at this FileNode), evaluating the shallowest depths first (visit while sinking down) -func (node *FileNode) VisitDepthParentFirst(visitor Visitor, evaluator VisitEvaluator) error { - var err error - - doVisit := evaluator != nil && evaluator(node) || evaluator == nil - - if !doVisit { - return nil - } - - // never visit the root node - if node != node.Tree.Root { - err = visitor(node) - if err != nil { - return err - } - } - - var keys []string - for key := range node.Children { - keys = append(keys, key) - } - sort.Strings(keys) - for _, name := range keys { - child := node.Children[name] - err = child.VisitDepthParentFirst(visitor, evaluator) - if err != nil { - return err - } - } - return err -} - -// IsWhiteout returns an indication if this file may be a overlay-whiteout file. -func (node *FileNode) IsWhiteout() bool { - return strings.HasPrefix(node.Name, whiteoutPrefix) -} - -// IsLeaf returns true is the current node has no child nodes. -func (node *FileNode) IsLeaf() bool { - return len(node.Children) == 0 -} - -// Path returns a slash-delimited string from the root of the greater tree to the current node (e.g. /a/path/to/here) -func (node *FileNode) Path() string { - if node.path == "" { - var path []string - curNode := node - for { - if curNode.Parent == nil { - break - } - - name := curNode.Name - if curNode == node { - // white out prefixes are fictitious on leaf nodes - name = strings.TrimPrefix(name, whiteoutPrefix) - } - - path = append([]string{name}, path...) - curNode = curNode.Parent - } - node.path = "/" + strings.Join(path, "/") - } - return strings.Replace(node.path, "//", "/", -1) -} - -// deriveDiffType determines a DiffType to the current FileNode. Note: the DiffType of a node is always the DiffType of -// its attributes and its contents. The contents are the bytes of the file of the children of a directory. -func (node *FileNode) deriveDiffType(diffType DiffType) error { - if node.IsLeaf() { - return node.AssignDiffType(diffType) - } - - myDiffType := diffType - for _, v := range node.Children { - myDiffType = myDiffType.merge(v.Data.DiffType) - } - - return node.AssignDiffType(myDiffType) -} - -// AssignDiffType will assign the given DiffType to this node, possibly affecting child nodes. -func (node *FileNode) AssignDiffType(diffType DiffType) error { - var err error - - node.Data.DiffType = diffType - - if diffType == Removed { - // if we've removed this node, then all children have been removed as well - for _, child := range node.Children { - err = child.AssignDiffType(diffType) - if err != nil { - return err - } - } - } - - return nil -} - -// compare the current node against the given node, returning a definitive DiffType. -func (node *FileNode) compare(other *FileNode) DiffType { - if node == nil && other == nil { - return Unmodified - } - - if node == nil && other != nil { - return Added - } - - if node != nil && other == nil { - return Removed - } - - if other.IsWhiteout() { - return Removed - } - if node.Name != other.Name { - panic("comparing mismatched nodes") - } - - return node.Data.FileInfo.Compare(other.Data.FileInfo) -} diff --git a/filetree/node_test.go b/filetree/node_test.go deleted file mode 100644 index a344475..0000000 --- a/filetree/node_test.go +++ /dev/null @@ -1,168 +0,0 @@ -package filetree - -import ( - "testing" -) - -func TestAddChild(t *testing.T) { - var expected, actual int - tree := NewFileTree() - - payload := FileInfo{ - Path: "stufffffs", - } - - one := tree.Root.AddChild("first node!", payload) - - two := tree.Root.AddChild("nil node!", FileInfo{}) - - tree.Root.AddChild("third node!", FileInfo{}) - two.AddChild("forth, one level down...", FileInfo{}) - two.AddChild("fifth, one level down...", FileInfo{}) - two.AddChild("fifth, one level down...", FileInfo{}) - - expected, actual = 5, tree.Size - if expected != actual { - t.Errorf("Expected a tree size of %d got %d.", expected, actual) - } - - expected, actual = 2, len(two.Children) - if expected != actual { - t.Errorf("Expected 'twos' number of children to be %d got %d.", expected, actual) - } - - expected, actual = 3, len(tree.Root.Children) - if expected != actual { - t.Errorf("Expected 'twos' number of children to be %d got %d.", expected, actual) - } - - expectedFC := FileInfo{ - Path: "stufffffs", - } - actualFC := one.Data.FileInfo - if expectedFC.Path != actualFC.Path { - t.Errorf("Expected 'ones' payload to be %+v got %+v.", expectedFC, actualFC) - } - -} - -func TestRemoveChild(t *testing.T) { - var expected, actual int - - tree := NewFileTree() - tree.Root.AddChild("first", FileInfo{}) - two := tree.Root.AddChild("nil", FileInfo{}) - tree.Root.AddChild("third", FileInfo{}) - forth := two.AddChild("forth", FileInfo{}) - two.AddChild("fifth", FileInfo{}) - - err := forth.Remove() - checkError(t, err, "unable to setup test") - - expected, actual = 4, tree.Size - if expected != actual { - t.Errorf("Expected a tree size of %d got %d.", expected, actual) - } - - if tree.Root.Children["forth"] != nil { - t.Errorf("Expected 'forth' node to be deleted.") - } - - err = two.Remove() - checkError(t, err, "unable to setup test") - - expected, actual = 2, tree.Size - if expected != actual { - t.Errorf("Expected a tree size of %d got %d.", expected, actual) - } - - if tree.Root.Children["nil"] != nil { - t.Errorf("Expected 'nil' node to be deleted.") - } - -} - -func TestPath(t *testing.T) { - expected := "/etc/nginx/nginx.conf" - tree := NewFileTree() - node, _, _ := tree.AddPath(expected, FileInfo{}) - - actual := node.Path() - if expected != actual { - t.Errorf("Expected path '%s' got '%s'", expected, actual) - } -} - -func TestIsWhiteout(t *testing.T) { - tree1 := NewFileTree() - p1, _, _ := tree1.AddPath("/etc/nginx/public1", FileInfo{}) - p2, _, _ := tree1.AddPath("/etc/nginx/.wh.public2", FileInfo{}) - p3, _, _ := tree1.AddPath("/etc/nginx/public3/.wh..wh..opq", FileInfo{}) - - if p1.IsWhiteout() != false { - t.Errorf("Expected path '%s' to **not** be a whiteout file", p1.Name) - } - - if p2.IsWhiteout() != true { - t.Errorf("Expected path '%s' to be a whiteout file", p2.Name) - } - - if p3 != nil { - t.Errorf("Expected to not be able to add path '%s'", p2.Name) - } -} - -func TestDiffTypeFromAddedChildren(t *testing.T) { - tree := NewFileTree() - node, _, _ := tree.AddPath("/usr", *BlankFileChangeInfo("/usr")) - node.Data.DiffType = Unmodified - - node, _, _ = tree.AddPath("/usr/bin", *BlankFileChangeInfo("/usr/bin")) - node.Data.DiffType = Added - - node, _, _ = tree.AddPath("/usr/bin2", *BlankFileChangeInfo("/usr/bin2")) - node.Data.DiffType = Removed - - err := tree.Root.Children["usr"].deriveDiffType(Unmodified) - checkError(t, err, "unable to setup test") - - if tree.Root.Children["usr"].Data.DiffType != Modified { - t.Errorf("Expected Modified but got %v", tree.Root.Children["usr"].Data.DiffType) - } -} -func TestDiffTypeFromRemovedChildren(t *testing.T) { - tree := NewFileTree() - _, _, _ = tree.AddPath("/usr", *BlankFileChangeInfo("/usr")) - - info1 := BlankFileChangeInfo("/usr/.wh.bin") - node, _, _ := tree.AddPath("/usr/.wh.bin", *info1) - node.Data.DiffType = Removed - - info2 := BlankFileChangeInfo("/usr/.wh.bin2") - node, _, _ = tree.AddPath("/usr/.wh.bin2", *info2) - node.Data.DiffType = Removed - - err := tree.Root.Children["usr"].deriveDiffType(Unmodified) - checkError(t, err, "unable to setup test") - - if tree.Root.Children["usr"].Data.DiffType != Modified { - t.Errorf("Expected Modified but got %v", tree.Root.Children["usr"].Data.DiffType) - } - -} - -func TestDirSize(t *testing.T) { - tree1 := NewFileTree() - _, _, err := tree1.AddPath("/etc/nginx/public1", FileInfo{Size: 100}) - checkError(t, err, "unable to setup test") - _, _, err = tree1.AddPath("/etc/nginx/thing1", FileInfo{Size: 200}) - checkError(t, err, "unable to setup test") - _, _, err = tree1.AddPath("/etc/nginx/public3/thing2", FileInfo{Size: 300}) - checkError(t, err, "unable to setup test") - - node, _ := tree1.GetNode("/etc/nginx") - expected, actual := "---------- 0:0 600 B ", node.MetadataString() - if expected != actual { - t.Errorf("Expected metadata '%s' got '%s'", expected, actual) - } -} diff --git a/filetree/tree.go b/filetree/tree.go deleted file mode 100644 index 192ad8d..0000000 --- a/filetree/tree.go +++ /dev/null @@ -1,371 +0,0 @@ -package filetree - -import ( - "fmt" - "sort" - "strings" - - "github.com/google/uuid" - "github.com/sirupsen/logrus" -) - -const ( - newLine = "\n" - noBranchSpace = " " - branchSpace = "│ " - middleItem = "├─" - lastItem = "└─" - whiteoutPrefix = ".wh." - doubleWhiteoutPrefix = ".wh..wh.." - uncollapsedItem = "─ " - collapsedItem = "⊕ " -) - -// NewFileTree creates an empty FileTree -func NewFileTree() (tree *FileTree) { - tree = new(FileTree) - tree.Size = 0 - tree.Root = new(FileNode) - tree.Root.Tree = tree - tree.Root.Children = make(map[string]*FileNode) - tree.Id = uuid.New() - return tree -} - -// renderParams is a representation of a FileNode in the context of the greater tree. All -// data stored is necessary for rendering a single line in a tree format. -type renderParams struct { - node *FileNode - spaces []bool - childSpaces []bool - showCollapsed bool - isLast bool -} - -// renderStringTreeBetween returns a string representing the given tree between the given rows. Since each node -// is rendered on its own line, the returned string shows the visible nodes not affected by a collapsed parent. -func (tree *FileTree) renderStringTreeBetween(startRow, stopRow int, showAttributes bool) string { - // generate a list of nodes to render - var params = make([]renderParams, 0) - var result string - - // visit from the front of the list - var paramsToVisit = []renderParams{{node: tree.Root, spaces: []bool{}, showCollapsed: false, isLast: false}} - for currentRow := 0; len(paramsToVisit) > 0 && currentRow <= stopRow; currentRow++ { - // pop the first node - var currentParams renderParams - currentParams, paramsToVisit = paramsToVisit[0], paramsToVisit[1:] - - // take note of the next nodes to visit later - var keys []string - for key := range currentParams.node.Children { - keys = append(keys, key) - } - // we should always visit nodes in order - sort.Strings(keys) - - var childParams = make([]renderParams, 0) - for idx, name := range keys { - child := currentParams.node.Children[name] - // don't visit this node... - if child.Data.ViewInfo.Hidden || currentParams.node.Data.ViewInfo.Collapsed { - continue - } - - // visit this node... - isLast := idx == (len(currentParams.node.Children) - 1) - showCollapsed := child.Data.ViewInfo.Collapsed && len(child.Children) > 0 - - // completely copy the reference slice - childSpaces := make([]bool, len(currentParams.childSpaces)) - copy(childSpaces, currentParams.childSpaces) - - if len(child.Children) > 0 && !child.Data.ViewInfo.Collapsed { - childSpaces = append(childSpaces, isLast) - } - - childParams = append(childParams, renderParams{ - node: child, - spaces: currentParams.childSpaces, - childSpaces: childSpaces, - showCollapsed: showCollapsed, - isLast: isLast, - }) - } - // keep the child nodes to visit later - paramsToVisit = append(childParams, paramsToVisit...) - - // never process the root node - if currentParams.node == tree.Root { - currentRow-- - continue - } - - // process the current node - if currentRow >= startRow && currentRow <= stopRow { - params = append(params, currentParams) - } - } - - // render the result - for idx := range params { - currentParams := params[idx] - - if showAttributes { - result += currentParams.node.MetadataString() + " " - } - result += currentParams.node.renderTreeLine(currentParams.spaces, currentParams.isLast, currentParams.showCollapsed) - } - - return result -} - -func (tree *FileTree) VisibleSize() int { - var size int - - visitor := func(node *FileNode) error { - size++ - return nil - } - visitEvaluator := func(node *FileNode) bool { - if node.Data.FileInfo.IsDir { - // we won't visit a collapsed dir, but we need to count it - if node.Data.ViewInfo.Collapsed { - size++ - } - return !node.Data.ViewInfo.Collapsed && !node.Data.ViewInfo.Hidden - } - return !node.Data.ViewInfo.Hidden - } - err := tree.VisitDepthParentFirst(visitor, visitEvaluator) - if err != nil { - logrus.Errorf("unable to determine visible tree size: %+v", err) - } - - // don't include root - size-- - - return size -} - -// String returns the entire tree in an ASCII representation. -func (tree *FileTree) String(showAttributes bool) string { - return tree.renderStringTreeBetween(0, tree.Size, showAttributes) -} - -// StringBetween returns a partial tree in an ASCII representation. -func (tree *FileTree) StringBetween(start, stop int, showAttributes bool) string { - return tree.renderStringTreeBetween(start, stop, showAttributes) -} - -// Copy returns a copy of the given FileTree -func (tree *FileTree) Copy() *FileTree { - newTree := NewFileTree() - newTree.Size = tree.Size - newTree.FileSize = tree.FileSize - newTree.Root = tree.Root.Copy(newTree.Root) - - // update the tree pointers - err := newTree.VisitDepthChildFirst(func(node *FileNode) error { - node.Tree = newTree - return nil - }, nil) - - if err != nil { - logrus.Errorf("unable to propagate tree on copy(): %+v", err) - } - - return newTree -} - -// Visitor is a function that processes, observes, or otherwise transforms the given node -type Visitor func(*FileNode) error - -// VisitEvaluator is a function that indicates whether the given node should be visited by a Visitor. -type VisitEvaluator func(*FileNode) bool - -// VisitDepthChildFirst iterates the given tree depth-first, evaluating the deepest depths first (visit on bubble up) -func (tree *FileTree) VisitDepthChildFirst(visitor Visitor, evaluator VisitEvaluator) error { - return tree.Root.VisitDepthChildFirst(visitor, evaluator) -} - -// VisitDepthParentFirst iterates the given tree depth-first, evaluating the shallowest depths first (visit while sinking down) -func (tree *FileTree) VisitDepthParentFirst(visitor Visitor, evaluator VisitEvaluator) error { - return tree.Root.VisitDepthParentFirst(visitor, evaluator) -} - -// Stack takes two trees and combines them together. This is done by "stacking" the given tree on top of the owning tree. -func (tree *FileTree) Stack(upper *FileTree) error { - graft := func(node *FileNode) error { - if node.IsWhiteout() { - err := tree.RemovePath(node.Path()) - if err != nil { - return fmt.Errorf("cannot remove node %s: %v", node.Path(), err.Error()) - } - } else { - newNode, _, err := tree.AddPath(node.Path(), node.Data.FileInfo) - if err != nil { - return fmt.Errorf("cannot add node %s: %v", newNode.Path(), err.Error()) - } - } - return nil - } - return upper.VisitDepthChildFirst(graft, nil) -} - -// GetNode fetches a single node when given a slash-delimited string from root ('/') to the desired node (e.g. '/a/node/path') -func (tree *FileTree) GetNode(path string) (*FileNode, error) { - nodeNames := strings.Split(strings.Trim(path, "/"), "/") - node := tree.Root - for _, name := range nodeNames { - if name == "" { - continue - } - if node.Children[name] == nil { - return nil, fmt.Errorf("path does not exist: %s", path) - } - node = node.Children[name] - } - return node, nil -} - -// AddPath adds a new node to the tree with the given payload -func (tree *FileTree) AddPath(path string, data FileInfo) (*FileNode, []*FileNode, error) { - nodeNames := strings.Split(strings.Trim(path, "/"), "/") - node := tree.Root - addedNodes := make([]*FileNode, 0) - for idx, name := range nodeNames { - if name == "" { - continue - } - // find or create node - if node.Children[name] != nil { - node = node.Children[name] - } else { - // don't add paths that should be deleted - if strings.HasPrefix(name, doubleWhiteoutPrefix) { - return nil, addedNodes, nil - } - - // don't attach the payload. The payload is destined for the - // Path's end node, not any intermediary node. - node = node.AddChild(name, FileInfo{}) - addedNodes = append(addedNodes, node) - - if node == nil { - // the child could not be added - return node, addedNodes, fmt.Errorf(fmt.Sprintf("could not add child node: '%s' (path:'%s')", name, path)) - } - } - - // attach payload to the last specified node - if idx == len(nodeNames)-1 { - node.Data.FileInfo = data - } - - } - return node, addedNodes, nil -} - -// RemovePath removes a node from the tree given its path. -func (tree *FileTree) RemovePath(path string) error { - node, err := tree.GetNode(path) - if err != nil { - return err - } - return node.Remove() -} - -type compareMark struct { - lowerNode *FileNode - upperNode *FileNode - tentative DiffType - final DiffType -} - -// CompareAndMark marks the FileNodes in the owning (lower) tree with DiffType annotations when compared to the given (upper) tree. -func (tree *FileTree) CompareAndMark(upper *FileTree) error { - // always compare relative to the original, unaltered tree. - originalTree := tree - - modifications := make([]compareMark, 0) - - graft := func(upperNode *FileNode) error { - if upperNode.IsWhiteout() { - err := tree.markRemoved(upperNode.Path()) - if err != nil { - return fmt.Errorf("cannot remove upperNode %s: %v", upperNode.Path(), err.Error()) - } - return nil - } - - // note: since we are not comparing against the original tree (copying the tree is expensive) we may mark the parent - // of an added node incorrectly as modified. This will be corrected later. - originalLowerNode, _ := originalTree.GetNode(upperNode.Path()) - - if originalLowerNode == nil { - _, newNodes, err := tree.AddPath(upperNode.Path(), upperNode.Data.FileInfo) - if err != nil { - return fmt.Errorf("cannot add new upperNode %s: %v", upperNode.Path(), err.Error()) - } - for idx := len(newNodes) - 1; idx >= 0; idx-- { - newNode := newNodes[idx] - modifications = append(modifications, compareMark{lowerNode: newNode, upperNode: upperNode, tentative: -1, final: Added}) - } - return nil - } - - // the file exists in the lower layer - lowerNode, _ := tree.GetNode(upperNode.Path()) - diffType := lowerNode.compare(upperNode) - modifications = append(modifications, compareMark{lowerNode: lowerNode, upperNode: upperNode, tentative: diffType, final: -1}) - - return nil - } - // we must visit from the leaves upwards to ensure that diff types can be derived from and assigned to children - err := upper.VisitDepthChildFirst(graft, nil) - if err != nil { - return err - } - - // take note of the comparison results on each note in the owning tree. - for _, pair := range modifications { - if pair.final > 0 { - err = pair.lowerNode.AssignDiffType(pair.final) - if err != nil { - return err - } - } else if pair.lowerNode.Data.DiffType == Unmodified { - err = pair.lowerNode.deriveDiffType(pair.tentative) - if err != nil { - return err - } - } - - // persist the upper's payload on the owning tree - pair.lowerNode.Data.FileInfo = *pair.upperNode.Data.FileInfo.Copy() - } - return nil -} - -// markRemoved annotates the FileNode at the given path as Removed. -func (tree *FileTree) markRemoved(path string) error { - node, err := tree.GetNode(path) - if err != nil { - return err - } - return node.AssignDiffType(Removed) -} - -// StackTreeRange combines an array of trees into a single tree -func StackTreeRange(trees []*FileTree, start, stop int) *FileTree { - - tree := trees[0].Copy() - for idx := start; idx <= stop; idx++ { - err := tree.Stack(trees[idx]) - if err != nil { - logrus.Errorf("could not stack tree range: %v", err) - } - } - return tree -} diff --git a/filetree/tree_test.go b/filetree/tree_test.go deleted file mode 100644 index fc57036..0000000 --- a/filetree/tree_test.go +++ /dev/null @@ -1,791 +0,0 @@ -package filetree - -import ( - "fmt" - "testing" -) - -func stringInSlice(a string, list []string) bool { - for _, b := range list { - if b == a { - return true - } - } - return false -} - -func AssertDiffType(node *FileNode, expectedDiffType DiffType) error { - if node.Data.DiffType != expectedDiffType { - return fmt.Errorf("Expecting node at %s to have DiffType %v, but had %v", node.Path(), expectedDiffType, node.Data.DiffType) - } - return nil -} - -func TestStringCollapsed(t *testing.T) { - tree := NewFileTree() - tree.Root.AddChild("1 node!", FileInfo{}) - two := tree.Root.AddChild("2 node!", FileInfo{}) - subTwo := two.AddChild("2 child!", FileInfo{}) - subTwo.AddChild("2 grandchild!", FileInfo{}) - subTwo.Data.ViewInfo.Collapsed = true - three := tree.Root.AddChild("3 node!", FileInfo{}) - subThree := three.AddChild("3 child!", FileInfo{}) - three.AddChild("3 nested child 1!", FileInfo{}) - threeGc1 := subThree.AddChild("3 grandchild 1!", FileInfo{}) - threeGc1.AddChild("3 greatgrandchild 1!", FileInfo{}) - subThree.AddChild("3 grandchild 2!", FileInfo{}) - four := tree.Root.AddChild("4 node!", FileInfo{}) - four.Data.ViewInfo.Collapsed = true - tree.Root.AddChild("5 node!", FileInfo{}) - four.AddChild("6, one level down...", FileInfo{}) - - expected := - `├── 1 node! -├── 2 node! -│ └─⊕ 2 child! -├── 3 node! -│ ├── 3 child! -│ │ ├── 3 grandchild 1! -│ │ │ └── 3 greatgrandchild 1! -│ │ └── 3 grandchild 2! -│ └── 3 nested child 1! -├─⊕ 4 node! -└── 5 node! -` - actual := tree.String(false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } - -} - -func TestString(t *testing.T) { - tree := NewFileTree() - tree.Root.AddChild("1 node!", FileInfo{}) - tree.Root.AddChild("2 node!", FileInfo{}) - tree.Root.AddChild("3 node!", FileInfo{}) - four := tree.Root.AddChild("4 node!", FileInfo{}) - tree.Root.AddChild("5 node!", FileInfo{}) - four.AddChild("6, one level down...", FileInfo{}) - - expected := - `├── 1 node! -├── 2 node! -├── 3 node! -├── 4 node! -│ └── 6, one level down... -└── 5 node! -` - actual := tree.String(false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } - -} - -func TestStringBetween(t *testing.T) { - tree := NewFileTree() - _, _, err := tree.AddPath("/etc/nginx/nginx.conf", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/etc/nginx/public", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/systemd", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/bashful", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp/nonsense", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - expected := - `│ └── public -├── tmp -│ └── nonsense -` - actual := tree.StringBetween(3, 5, false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } - -} - -func TestAddPath(t *testing.T) { - tree := NewFileTree() - _, _, err := tree.AddPath("/etc/nginx/nginx.conf", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/etc/nginx/public", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/systemd", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/bashful", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp/nonsense", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - expected := - `├── etc -│ └── nginx -│ ├── nginx.conf -│ └── public -├── tmp -│ └── nonsense -└── var - └── run - ├── bashful - └── systemd -` - actual := tree.String(false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } - -} - -func TestAddWhiteoutPath(t *testing.T) { - tree := NewFileTree() - node, _, err := tree.AddPath("usr/local/lib/python3.7/site-packages/pip/.wh..wh..opq", FileInfo{}) - if err != nil { - t.Errorf("expected no error but got: %v", err) - } - if node != nil { - t.Errorf("expected node to be nil, but got: %v", node) - } - expected := - `└── usr - └── local - └── lib - └── python3.7 - └── site-packages - └── pip -` - actual := tree.String(false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } -} - -func TestRemovePath(t *testing.T) { - tree := NewFileTree() - _, _, err := tree.AddPath("/etc/nginx/nginx.conf", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/etc/nginx/public", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/systemd", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/bashful", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp/nonsense", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - err = tree.RemovePath("/var/run/bashful") - if err != nil { - t.Errorf("could not setup test: %v", err) - } - err = tree.RemovePath("/tmp") - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - expected := - `├── etc -│ └── nginx -│ ├── nginx.conf -│ └── public -└── var - └── run - └── systemd -` - actual := tree.String(false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } - -} - -func TestStack(t *testing.T) { - payloadKey := "/var/run/systemd" - payloadValue := FileInfo{ - Path: "yup", - } - - tree1 := NewFileTree() - - _, _, err := tree1.AddPath("/etc/nginx/public", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree1.AddPath(payloadKey, FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree1.AddPath("/var/run/bashful", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree1.AddPath("/tmp", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree1.AddPath("/tmp/nonsense", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - tree2 := NewFileTree() - // add new files - _, _, err = tree2.AddPath("/etc/nginx/nginx.conf", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - // modify current files - _, _, err = tree2.AddPath(payloadKey, payloadValue) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - // whiteout the following files - _, _, err = tree2.AddPath("/var/run/.wh.bashful", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree2.AddPath("/.wh.tmp", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - // ignore opaque whiteout files entirely - node, _, err := tree2.AddPath("/.wh..wh..opq", FileInfo{}) - if err != nil { - t.Errorf("expected no error on whiteout file add, but got %v", err) - } - if node != nil { - t.Errorf("expected no node on whiteout file add, but got %v", node) - } - - err = tree1.Stack(tree2) - - if err != nil { - t.Errorf("Could not stack refTrees: %v", err) - } - - expected := - `├── etc -│ └── nginx -│ ├── nginx.conf -│ └── public -└── var - └── run - └── systemd -` - - node, err = tree1.GetNode(payloadKey) - if err != nil { - t.Errorf("Expected '%s' to still exist, but it doesn't", payloadKey) - } - - if node == nil || node.Data.FileInfo.Path != payloadValue.Path { - t.Errorf("Expected '%s' value to be %+v but got %+v", payloadKey, payloadValue, node.Data.FileInfo) - } - - actual := tree1.String(false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } - -} - -func TestCopy(t *testing.T) { - tree := NewFileTree() - _, _, err := tree.AddPath("/etc/nginx/nginx.conf", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/etc/nginx/public", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/systemd", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/var/run/bashful", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = tree.AddPath("/tmp/nonsense", FileInfo{}) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - err = tree.RemovePath("/var/run/bashful") - if err != nil { - t.Errorf("could not setup test: %v", err) - } - err = tree.RemovePath("/tmp") - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - expected := - `├── etc -│ └── nginx -│ ├── nginx.conf -│ └── public -└── var - └── run - └── systemd -` - - NewFileTree := tree.Copy() - actual := NewFileTree.String(false) - - if expected != actual { - t.Errorf("Expected tree string:\n--->%s<---\nGot:\n--->%s<---", expected, actual) - } - -} - -func TestCompareWithNoChanges(t *testing.T) { - lowerTree := NewFileTree() - upperTree := NewFileTree() - paths := [...]string{"/etc", "/etc/sudoers", "/etc/hosts", "/usr/bin", "/usr/bin/bash", "/usr"} - - for _, value := range paths { - fakeData := FileInfo{ - Path: value, - TypeFlag: 1, - hash: 123, - } - _, _, err := lowerTree.AddPath(value, fakeData) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = upperTree.AddPath(value, fakeData) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - } - err := lowerTree.CompareAndMark(upperTree) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - asserter := func(n *FileNode) error { - if n.Path() == "/" { - return nil - } - if (n.Data.DiffType) != Unmodified { - t.Errorf("Expecting node at %s to have DiffType unchanged, but had %v", n.Path(), n.Data.DiffType) - } - return nil - } - err = lowerTree.VisitDepthChildFirst(asserter, nil) - if err != nil { - t.Error(err) - } -} - -func TestCompareWithAdds(t *testing.T) { - lowerTree := NewFileTree() - upperTree := NewFileTree() - lowerPaths := [...]string{"/etc", "/etc/sudoers", "/usr", "/etc/hosts", "/usr/bin"} - upperPaths := [...]string{"/etc", "/etc/sudoers", "/usr", "/etc/hosts", "/usr/bin", "/usr/bin/bash", "/a/new/path"} - - for _, value := range lowerPaths { - _, _, err := lowerTree.AddPath(value, FileInfo{ - Path: value, - TypeFlag: 1, - hash: 123, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - } - - for _, value := range upperPaths { - _, _, err := upperTree.AddPath(value, FileInfo{ - Path: value, - TypeFlag: 1, - hash: 123, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - } - - failedAssertions := []error{} - err := lowerTree.CompareAndMark(upperTree) - if err != nil { - t.Errorf("Expected tree compare to have no errors, got: %v", err) - } - asserter := func(n *FileNode) error { - - p := n.Path() - if p == "/" { - return nil - } else if stringInSlice(p, []string{"/usr/bin/bash", "/a", "/a/new", "/a/new/path"}) { - if err := AssertDiffType(n, Added); err != nil { - failedAssertions = append(failedAssertions, err) - } - } else if stringInSlice(p, []string{"/usr/bin", "/usr"}) { - if err := AssertDiffType(n, Modified); err != nil { - failedAssertions = append(failedAssertions, err) - } - } else { - if err := AssertDiffType(n, Unmodified); err != nil { - failedAssertions = append(failedAssertions, err) - } - } - return nil - } - err = lowerTree.VisitDepthChildFirst(asserter, nil) - if err != nil { - t.Errorf("Expected no errors when visiting nodes, got: %+v", err) - } - - if len(failedAssertions) > 0 { - str := "\n" - for _, value := range failedAssertions { - str += fmt.Sprintf(" - %s\n", value.Error()) - } - t.Errorf("Expected no errors when evaluating nodes, got: %s", str) - } -} - -func TestCompareWithChanges(t *testing.T) { - lowerTree := NewFileTree() - upperTree := NewFileTree() - changedPaths := []string{"/etc", "/usr", "/etc/hosts", "/etc/sudoers", "/usr/bin"} - - for _, value := range changedPaths { - _, _, err := lowerTree.AddPath(value, FileInfo{ - Path: value, - TypeFlag: 1, - hash: 123, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - _, _, err = upperTree.AddPath(value, FileInfo{ - Path: value, - TypeFlag: 1, - hash: 456, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - } - - chmodPath := "/etc/non-data-change" - - _, _, err := lowerTree.AddPath(chmodPath, FileInfo{ - Path: chmodPath, - TypeFlag: 1, - hash: 123, - Mode: 0, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - _, _, err = upperTree.AddPath(chmodPath, FileInfo{ - Path: chmodPath, - TypeFlag: 1, - hash: 123, - Mode: 1, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - changedPaths = append(changedPaths, chmodPath) - - chownPath := "/etc/non-data-change-2" - - _, _, err = lowerTree.AddPath(chmodPath, FileInfo{ - Path: chownPath, - TypeFlag: 1, - hash: 123, - Mode: 1, - Gid: 0, - Uid: 0, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - _, _, err = upperTree.AddPath(chmodPath, FileInfo{ - Path: chownPath, - TypeFlag: 1, - hash: 123, - Mode: 1, - Gid: 12, - Uid: 12, - }) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - - changedPaths = append(changedPaths, chownPath) - - err = lowerTree.CompareAndMark(upperTree) - if err != nil { - t.Errorf("unable to compare and mark: %+v", err) - } - - failedAssertions := []error{} - asserter := func(n *FileNode) error { - p := n.Path() - if p == "/" { - return nil - } else if stringInSlice(p, changedPaths) { - if err := AssertDiffType(n, Modified); err != nil { - failedAssertions = append(failedAssertions, err) - } - } else { - if err := AssertDiffType(n, Unmodified); err != nil { - failedAssertions = append(failedAssertions, err) - } - } - return nil - } - err = lowerTree.VisitDepthChildFirst(asserter, nil) - if err != nil { - t.Errorf("Expected no errors when visiting nodes, got: %+v", err) - } - - if len(failedAssertions) > 0 { - str := "\n" - for _, value := range failedAssertions { - str += fmt.Sprintf(" - %s\n", value.Error()) - } - t.Errorf("Expected no errors when evaluating nodes, got: %s", str) - } -} - -func TestCompareWithRemoves(t *testing.T) { - lowerTree := NewFileTree() - upperTree := NewFileTree() - lowerPaths := [...]string{"/etc", "/usr", "/etc/hosts", "/etc/sudoers", "/usr/bin", "/root", "/root/example", "/root/example/some1", "/root/example/some2"} - upperPaths := [...]string{"/.wh.etc", "/usr", "/usr/.wh.bin", "/root/.wh.example"} - - for _, value := range lowerPaths { - fakeData := FileInfo{ - Path: value, - TypeFlag: 1, - hash: 123, - } - _, _, err := lowerTree.AddPath(value, fakeData) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - } - - for _, value := range upperPaths { - fakeData := FileInfo{ - Path: value, - TypeFlag: 1, - hash: 123, - } - _, _, err := upperTree.AddPath(value, fakeData) - if err != nil { - t.Errorf("could not setup test: %v", err) - } - } - - err := lowerT