hadoop-hdfs-project/hadoop-hdfs-client/src/main/java/org/apache/hadoop/hdfs/client/impl/SnapshotDiffReportGenerator.java

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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 org.apache.hadoop.hdfs.client.impl;

import java.util.*;

import org.apache.hadoop.thirdparty.com.google.common.primitives.SignedBytes;

import org.apache.hadoop.util.ChunkedArrayList;
import org.apache.hadoop.hdfs.protocol.SnapshotDiffReportListing.DiffReportListingEntry;
import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport;
import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffReportEntry;
import org.apache.hadoop.hdfs.protocol.SnapshotDiffReport.DiffType;
/**
 * This class represents to end users the difference between two snapshots of
 * the same directory, or the difference between a snapshot of the directory and
 * its current state. Instead of capturing all the details of the diff, this
 * class only lists where the changes happened and their types.
 */
public class SnapshotDiffReportGenerator {
  /**
   * Compare two inodes based on their full names.
   */
  public static final Comparator<DiffReportListingEntry> INODE_COMPARATOR =
      new Comparator<DiffReportListingEntry>() {
        @Override
        public int compare(DiffReportListingEntry left,
            DiffReportListingEntry right) {
          final Comparator<byte[]> cmp =
              SignedBytes.lexicographicalComparator();
          //source path can never be null
          final byte[][] l = left.getSourcePath();
          final byte[][] r = right.getSourcePath();
          if (l.length == 1 && l[0] == null) {
            return -1;
          } else if (r.length == 1 && r[0] == null) {
            return 1;
          } else {
            for (int i = 0; i < l.length && i < r.length; i++) {
              final int diff = cmp.compare(l[i], r[i]);
              if (diff != 0) {
                return diff;
              }
            }
            return l.length == r.length ? 0 : l.length > r.length ? 1 : -1;
          }
        }
      };

  static class RenameEntry {
    private byte[][] sourcePath;
    private byte[][] targetPath;

    void setSource(byte[][] srcPath) {
      this.sourcePath = srcPath;
    }

    void setTarget(byte[][] target) {
      this.targetPath = target;
    }

    boolean isRename() {
      return sourcePath != null && targetPath != null;
    }

    byte[][] getSourcePath() {
      return sourcePath;
    }

    byte[][] getTargetPath() {
      return targetPath;
    }
  }

  /*
   * A class represnting the diff in a directory between two given snapshots
   * in two lists: createdList and deleted list.
   */
  static class ChildrenDiff {
    private final List<DiffReportListingEntry> createdList;
    private final List<DiffReportListingEntry> deletedList;

    ChildrenDiff(List<DiffReportListingEntry> createdList,
        List<DiffReportListingEntry> deletedList) {
      this.createdList = createdList != null ? createdList :
          Collections.emptyList();
      this.deletedList = deletedList != null ? deletedList :
          Collections.emptyList();
    }

    public List<DiffReportListingEntry> getCreatedList() {
      return createdList;
    }

    public List<DiffReportListingEntry> getDeletedList() {
      return deletedList;
    }
  }

  /**
   * snapshot root full path.
   */
  private final String snapshotRoot;

  /**
   * start point of the diff.
   */
  private final String fromSnapshot;

  /**
   * end point of the diff.
   */
  private final String toSnapshot;

  /**
   * Flag to indicate the diff is calculated from older to newer snapshot
   * or not.
   */
  private final boolean isFromEarlier;

  /**
   * A map capturing the detailed difference about file creation/deletion.
   * Each key indicates a directory inode whose children have been changed
   * between the two snapshots, while its associated value is a
   * {@link ChildrenDiff} storing the changes (creation/deletion) happened to
   * the children (files).
   */
  private final Map<Long, ChildrenDiff> dirDiffMap =
      new HashMap<>();

  private final Map<Long, RenameEntry> renameMap =
      new HashMap<>();

  private List<DiffReportListingEntry> mlist = null;
  private List<DiffReportListingEntry> clist = null;
  private List<DiffReportListingEntry> dlist = null;

  public SnapshotDiffReportGenerator(String snapshotRoot, String fromSnapshot,
      String toSnapshot, boolean isFromEarlier,
      List<DiffReportListingEntry> mlist, List<DiffReportListingEntry> clist,
      List<DiffReportListingEntry> dlist) {
    this.snapshotRoot = snapshotRoot;
    this.fromSnapshot = fromSnapshot;
    this.toSnapshot = toSnapshot;
    this.isFromEarlier = isFromEarlier;
    this.mlist =
        mlist != null ? mlist : Collections.emptyList();
    this.clist =
        clist != null ? clist : Collections.emptyList();
    this.dlist =
        dlist != null ? dlist : Collections.emptyList();
  }

  private RenameEntry getEntry(long inodeId) {
    RenameEntry entry = renameMap.get(inodeId);
    if (entry == null) {
      entry = new RenameEntry();
      renameMap.put(inodeId, entry);
    }
    return entry;
  }

  public void generateReportList() {
    mlist.sort(INODE_COMPARATOR);
    for (DiffReportListingEntry created : clist) {
      ChildrenDiff entry = dirDiffMap.get(created.getDirId());
      if (entry == null) {
        List<DiffReportListingEntry> createdList = new ChunkedArrayList<>();
        createdList.add(created);
        ChildrenDiff list = new ChildrenDiff(createdList, null);
        dirDiffMap.put(created.getDirId(), list);
      } else {
        dirDiffMap.get(created.getDirId()).getCreatedList().add(created);
      }
      if (created.isReference()) {
        RenameEntry renameEntry = getEntry(created.getFileId());
        if (renameEntry.getTargetPath() != null) {
          renameEntry.setTarget(created.getSourcePath());
        }
      }
    }
    for (DiffReportListingEntry deleted : dlist) {
      ChildrenDiff entry = dirDiffMap.get(deleted.getDirId());
      if (entry == null || (entry.getDeletedList().isEmpty())) {
        ChildrenDiff list;
        List<DiffReportListingEntry> deletedList = new ChunkedArrayList<>();
        deletedList.add(deleted);
        if (entry == null) {
          list = new ChildrenDiff(null, deletedList);
        } else {
          list = new ChildrenDiff(entry.getCreatedList(), deletedList);
        }
        dirDiffMap.put(deleted.getDirId(), list);
      } else {
        entry.getDeletedList().add(deleted);
      }
      if (deleted.isReference()) {
        RenameEntry renameEntry = getEntry(deleted.getFileId());
        renameEntry.setTarget(deleted.getTargetPath());
        renameEntry.setSource(deleted.getSourcePath());
      }
    }
  }

  public SnapshotDiffReport generateReport() {
    List<DiffReportEntry> diffReportList = new ChunkedArrayList<>();
    generateReportList();
    for (DiffReportListingEntry modified : mlist) {
      diffReportList.add(
          new DiffReportEntry(DiffType.MODIFY, modified.getSourcePath(), null));
      if (modified.isReference()
          && dirDiffMap.get(modified.getDirId()) != null) {
        List<DiffReportEntry> subList = generateReport(modified);
        diffReportList.addAll(subList);
      }
    }
    return new SnapshotDiffReport(snapshotRoot, fromSnapshot, toSnapshot,
        diffReportList);
  }

  private List<DiffReportEntry> generateReport(
      DiffReportListingEntry modified) {
    List<DiffReportEntry> diffReportList = new ChunkedArrayList<>();
    ChildrenDiff list = dirDiffMap.get(modified.getDirId());
    for (DiffReportListingEntry created : list.getCreatedList()) {
      RenameEntry entry = renameMap.get(created.getFileId());
      if (entry == null || !entry.isRename()) {
        diffReportList.add(new DiffReportEntry(
            isFromEarlier ? DiffType.CREATE : DiffType.DELETE,
            created.getSourcePath()));
      }
    }
    for (DiffReportListingEntry deleted : list.getDeletedList()) {
      RenameEntry entry = renameMap.get(deleted.getFileId());
      if (entry != null && entry.isRename()) {
        diffReportList.add(new DiffReportEntry(DiffType.RENAME,
            isFromEarlier ? entry.getSourcePath() : entry.getTargetPath(),
            isFromEarlier ? entry.getTargetPath() : entry.getSourcePath()));
      } else {
        diffReportList.add(new DiffReportEntry(
            isFromEarlier ? DiffType.DELETE : DiffType.CREATE,
            deleted.getSourcePath()));
      }
    }
    return diffReportList;
  }
}