src/main/java/com/google/devtools/build/lib/remote/merkletree/DirectoryTree.java

// Copyright 2019 The Bazel Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package com.google.devtools.build.lib.remote.merkletree;

import build.bazel.remote.execution.v2.Digest;
import com.google.common.base.Preconditions;
import com.google.common.base.Strings;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.protobuf.ByteString;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.SortedSet;

/**
 * Intermediate tree representation of a list of lexicographically sorted list of files. Each node
 * in the tree represents either a directory or file.
 */
final class DirectoryTree {

  interface Visitor {
    void visitDirectory(PathFragment dirname, List<FileNode> files, List<DirectoryNode> dirs);
  }

  abstract static class Node implements Comparable<Node> {
    private final String pathSegment;

    Node(String pathSegment) {
      this.pathSegment = Preconditions.checkNotNull(pathSegment);
    }

    String getPathSegment() {
      return pathSegment;
    }

    @Override
    public int compareTo(Node other) {
      return pathSegment.compareTo(other.pathSegment);
    }

    @Override
    public int hashCode() {
      return pathSegment.hashCode();
    }

    @Override
    public boolean equals(Object o) {
      if (o instanceof Node) {
        Node other = (Node) o;
        return Objects.equals(pathSegment, other.pathSegment);
      }
      return false;
    }
  }

  static class FileNode extends Node {
    private final Path path;
    private final ByteString data;
    private final Digest digest;

    FileNode(String pathSegment, Path path, Digest digest) {
      super(pathSegment);
      this.path = Preconditions.checkNotNull(path, "path");
      this.data = null;
      this.digest = Preconditions.checkNotNull(digest, "digest");
    }

    FileNode(String pathSegment, ByteString data, Digest digest) {
      super(pathSegment);
      this.path = null;
      this.data = Preconditions.checkNotNull(data, "data");
      ;
      this.digest = Preconditions.checkNotNull(digest, "digest");
    }

    Digest getDigest() {
      return digest;
    }

    Path getPath() {
      return path;
    }

    ByteString getBytes() {
      return data;
    }

    @Override
    public int hashCode() {
      return Objects.hash(super.hashCode(), path, data, digest);
    }

    @Override
    public boolean equals(Object o) {
      if (o instanceof FileNode) {
        FileNode other = (FileNode) o;
        return super.equals(other)
            && Objects.equals(path, other.path)
            && Objects.equals(data, other.data)
            && Objects.equals(digest, other.digest);
      }
      return false;
    }
  }

  static class DirectoryNode extends Node {
    private final SortedSet<Node> children = Sets.newTreeSet();

    DirectoryNode(String pathSegment) {
      super(pathSegment);
    }

    void addChild(Node child) {
      children.add(Preconditions.checkNotNull(child, "child"));
    }

    @Override
    public int hashCode() {
      return Objects.hash(super.hashCode(), children.hashCode());
    }

    @Override
    public boolean equals(Object o) {
      if (o instanceof DirectoryNode) {
        DirectoryNode other = (DirectoryNode) o;
        return super.equals(other) && Objects.equals(children, other.children);
      }
      return false;
    }
  }

  private final Map<PathFragment, DirectoryNode> tree;
  private final int numFiles;

  protected DirectoryTree(Map<PathFragment, DirectoryNode> tree, int numFiles) {
    Preconditions.checkState(numFiles >= 0, "numFiles must gte 0");
    this.tree = Preconditions.checkNotNull(tree, "tree");
    this.numFiles = numFiles;
  }

  int numDirectories() {
    return tree.size();
  }

  int numFiles() {
    return numFiles;
  }

  boolean isEmpty() {
    return tree.isEmpty();
  }

  /**
   * Traverses the {@link ActionInputsTree} in a depth first search manner. The children are visited
   * in lexographical order.
   */
  void visit(Visitor visitor) {
    Preconditions.checkNotNull(visitor, "visitor");
    visit(visitor, PathFragment.EMPTY_FRAGMENT);
  }

  private void visit(Visitor visitor, PathFragment dirname) {
    DirectoryNode dir = tree.get(dirname);
    if (dir == null) {
      return;
    }

    List<FileNode> files = new ArrayList<>(dir.children.size());
    List<DirectoryNode> dirs = new ArrayList<>();
    for (Node child : dir.children) {
      if (child instanceof FileNode) {
        files.add((FileNode) child);
      } else if (child instanceof DirectoryNode) {
        dirs.add((DirectoryNode) child);
        visit(visitor, dirname.getRelative(child.pathSegment));
      } else {
        throw new IllegalStateException(
            String.format("Node type '%s' is not supported", child.getClass().getSimpleName()));
      }
    }
    visitor.visitDirectory(dirname, files, dirs);
  }

  @Override
  public String toString() {
    Map<PathFragment, StringBuilder> m = new HashMap<>();
    visit(
        (dirname, files, dirs) -> {
          int depth = dirname.segmentCount() - 1;
          StringBuilder sb = new StringBuilder();

          if (!dirname.equals(PathFragment.EMPTY_FRAGMENT)) {
            sb.append(Strings.repeat("  ", depth));
            sb.append(dirname.getBaseName());
            sb.append("\n");
          }
          if (!files.isEmpty()) {
            for (FileNode file : files) {
              sb.append(Strings.repeat("  ", depth + 1));
              sb.append(formatFile(file));
              sb.append("\n");
            }
          }
          if (!dirs.isEmpty()) {
            for (DirectoryNode dir : dirs) {
              sb.append(m.remove(dirname.getRelative(dir.getPathSegment())));
            }
          }
          m.put(dirname, sb);
        });
    return m.get(PathFragment.EMPTY_FRAGMENT).toString();
  }

  @Override
  public int hashCode() {
    return tree.hashCode();
  }

  @Override
  public boolean equals(Object o) {
    if (o == this) {
      return true;
    }
    if (!(o instanceof DirectoryTree)) {
      return false;
    }
    DirectoryTree other = (DirectoryTree) o;
    return tree.equals(other.tree);
  }

  private static String formatFile(FileNode file) {
    return String.format(
        "%s (hash: %s, size: %d)",
        file.getPathSegment(), file.digest.getHash(), file.digest.getSizeBytes());
  }
}