/**
 * 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.server.namenode;

import java.util.Arrays;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.apache.hadoop.hdfs.DFSUtil;
import org.apache.hadoop.hdfs.protocol.HdfsConstants;
import org.apache.hadoop.hdfs.server.common.HdfsServerConstants;
import org.apache.hadoop.hdfs.server.namenode.snapshot.DirectoryWithSnapshotFeature;
import org.apache.hadoop.hdfs.server.namenode.snapshot.Snapshot;

import org.apache.hadoop.thirdparty.com.google.common.base.Preconditions;

import static org.apache.hadoop.hdfs.server.namenode.snapshot.Snapshot.CURRENT_STATE_ID;
import static org.apache.hadoop.hdfs.server.namenode.snapshot.Snapshot.ID_INTEGER_COMPARATOR;

/**
 * Contains INodes information resolved from a given path.
 */
public class INodesInPath {
  public static final Logger LOG = LoggerFactory.getLogger(INodesInPath.class);

  /**
   * @return true if path component is {@link HdfsConstants#DOT_SNAPSHOT_DIR}
   */
  private static boolean isDotSnapshotDir(byte[] pathComponent) {
    return pathComponent != null &&
        Arrays.equals(HdfsServerConstants.DOT_SNAPSHOT_DIR_BYTES, pathComponent);
  }

  private static INode[] getINodes(final INode inode) {
    int depth = 0, index;
    INode tmp = inode;
    while (tmp != null) {
      depth++;
      tmp = tmp.getParent();
    }
    INode[] inodes = new INode[depth];
    tmp = inode;
    index = depth;
    while (tmp != null) {
      index--;
      inodes[index] = tmp;
      tmp = tmp.getParent();
    }
    return inodes;
  }

  private static byte[][] getPaths(final INode[] inodes) {
    byte[][] paths = new byte[inodes.length][];
    for (int i = 0; i < inodes.length; i++) {
      paths[i] = inodes[i].getKey();
    }
    return paths;
  }

  /**
   * Construct {@link INodesInPath} from {@link INode}.
   *
   * @param inode to construct from
   * @return INodesInPath
   */
  static INodesInPath fromINode(INode inode) {
    INode[] inodes = getINodes(inode);
    byte[][] paths = getPaths(inodes);
    return new INodesInPath(inodes, paths);
  }

  /**
   * Construct {@link INodesInPath} from {@link INode} and its root
   * {@link INodeDirectory}. INodesInPath constructed this way will
   * each have its snapshot and latest snapshot id filled in.
   *
   * This routine is specifically for
   * {@link LeaseManager#getINodeWithLeases(INodeDirectory)} to get
   * open files along with their snapshot details which is used during
   * new snapshot creation to capture their meta data.
   *
   * @param rootDir the root {@link INodeDirectory} under which inode
   *                needs to be resolved
   * @param inode the {@link INode} to be resolved
   * @return INodesInPath
   */
  static INodesInPath fromINode(final INodeDirectory rootDir, INode inode) {
    byte[][] paths = getPaths(getINodes(inode));
    return resolve(rootDir, paths);
  }

  static INodesInPath fromComponents(byte[][] components) {
    return new INodesInPath(new INode[components.length], components);
  }

  /**
   * Retrieve existing INodes from a path.  The number of INodes is equal
   * to the number of path components.  For a snapshot path
   * (e.g. /foo/.snapshot/s1/bar), the ".snapshot/s1" will be represented in
   * one path component corresponding to its Snapshot.Root inode.  This 1-1
   * mapping ensures the path can always be properly reconstructed.
   *
   * <p>
   * Example: <br>
   * Given the path /c1/c2/c3 where only /c1/c2 exists, resulting in the
   * following path components: ["","c1","c2","c3"]
   * 
   * <p>
   * <code>getExistingPathINodes(["","c1","c2"])</code> should fill
   * the array with [rootINode,c1,c2], <br>
   * <code>getExistingPathINodes(["","c1","c2","c3"])</code> should
   * fill the array with [rootINode,c1,c2,null]
   * 
   * @param startingDir the starting directory
   * @param components array of path component name
   * @return the specified number of existing INodes in the path
   */
  static INodesInPath resolve(final INodeDirectory startingDir,
      final byte[][] components) {
    return resolve(startingDir, components, false);
  }

  static INodesInPath resolve(final INodeDirectory startingDir,
      byte[][] components, final boolean isRaw) {
    Preconditions.checkArgument(startingDir.compareTo(components[0]) == 0);

    INode curNode = startingDir;
    int count = 0;
    int inodeNum = 0;
    INode[] inodes = new INode[components.length];
    boolean isSnapshot = false;
    int snapshotId = CURRENT_STATE_ID;

    while (count < components.length && curNode != null) {
      final boolean lastComp = (count == components.length - 1);
      inodes[inodeNum++] = curNode;
      final boolean isRef = curNode.isReference();
      final boolean isDir = curNode.isDirectory();
      final INodeDirectory dir = isDir? curNode.asDirectory(): null;
      if (!isRef && isDir && dir.isWithSnapshot()) {
        //if the path is a non-snapshot path, update the latest snapshot.
        if (!isSnapshot && shouldUpdateLatestId(
            dir.getDirectoryWithSnapshotFeature().getLastSnapshotId(),
            snapshotId)) {
          snapshotId = dir.getDirectoryWithSnapshotFeature().getLastSnapshotId();
        }
      } else if (isRef && isDir && !lastComp) {
        // If the curNode is a reference node, need to check its dstSnapshot:
        // 1. if the existing snapshot is no later than the dstSnapshot (which
        // is the latest snapshot in dst before the rename), the changes 
        // should be recorded in previous snapshots (belonging to src).
        // 2. however, if the ref node is already the last component, we still 
        // need to know the latest snapshot among the ref node's ancestors, 
        // in case of processing a deletion operation. Thus we do not overwrite
        // the latest snapshot if lastComp is true. In case of the operation is
        // a modification operation, we do a similar check in corresponding 
        // recordModification method.
        if (!isSnapshot) {
          int dstSnapshotId = curNode.asReference().getDstSnapshotId();
          if (snapshotId == CURRENT_STATE_ID || // no snapshot in dst tree of rename
              (dstSnapshotId != CURRENT_STATE_ID &&
               dstSnapshotId >= snapshotId)) { // the above scenario
            int lastSnapshot = CURRENT_STATE_ID;
            DirectoryWithSnapshotFeature sf;
            if (curNode.isDirectory() && 
                (sf = curNode.asDirectory().getDirectoryWithSnapshotFeature()) != null) {
              lastSnapshot = sf.getLastSnapshotId();
            }
            snapshotId = lastSnapshot;
          }
        }
      }
      if (lastComp || !isDir) {
        break;
      }

      final byte[] childName = components[++count];
      // check if the next byte[] in components is for ".snapshot"
      if (isDotSnapshotDir(childName) && dir.isSnapshottable()) {
        isSnapshot = true;
        // check if ".snapshot" is the last element of components
        if (count == components.length - 1) {
          break;
        }
        // Resolve snapshot root
        final Snapshot s = dir.getSnapshot(components[count + 1]);
        if (s == null) {
          curNode = null; // snapshot not found
        } else {
          curNode = s.getRoot();
          snapshotId = s.getId();
        }
        // combine .snapshot & name into 1 component element to ensure
        // 1-to-1 correspondence between components and inodes arrays is
        // preserved so a path can be reconstructed.
        byte[][] componentsCopy =
            Arrays.copyOf(components, components.length - 1);
        componentsCopy[count] = DFSUtil.string2Bytes(
            DFSUtil.byteArray2PathString(components, count, 2));
        // shift the remaining components after snapshot name
        int start = count + 2;
        System.arraycopy(components, start, componentsCopy, count + 1,
            components.length - start);
        components = componentsCopy;
        // reduce the inodes array to compensate for reduction in components
        inodes = Arrays.copyOf(inodes, components.length);
      } else {
        // normal case, and also for resolving file/dir under snapshot root
        curNode = dir.getChild(childName,
            isSnapshot ? snapshotId : CURRENT_STATE_ID);
      }
    }
    return new INodesInPath(inodes, components, isRaw, isSnapshot, snapshotId);
  }

  private static boolean shouldUpdateLatestId(int sid, int snapshotId) {
    return snapshotId == CURRENT_STATE_ID || (sid != CURRENT_STATE_ID &&
        ID_INTEGER_COMPARATOR.compare(snapshotId, sid) < 0);
  }

  /**
   * Replace an inode of the given INodesInPath in the given position. We do a
   * deep copy of the INode array.
   * @param pos the position of the replacement
   * @param inode the new inode
   * @return a new INodesInPath instance
   */
  public static INodesInPath replace(INodesInPath iip, int pos, INode inode) {
    Preconditions.checkArgument(iip.length() > 0 && pos > 0 // no for root
        && pos < iip.length());
    if (iip.getINode(pos) == null) {
      Preconditions.checkState(iip.getINode(pos - 1) != null);
    }
    INode[] inodes = new INode[iip.inodes.length];
    System.arraycopy(iip.inodes, 0, inodes, 0, inodes.length);
    inodes[pos] = inode;
    return new INodesInPath(inodes, iip.path, iip.isRaw,
        iip.isSnapshot, iip.snapshotId);
  }

  /**
   * Extend a given INodesInPath with a child INode. The child INode will be
   * appended to the end of the new INodesInPath.
   */
  public static INodesInPath append(INodesInPath iip, INode child,
      byte[] childName) {
    Preconditions.checkArgument(iip.length() > 0);
    Preconditions.checkArgument(iip.getLastINode() != null && iip
        .getLastINode().isDirectory());
    INode[] inodes = new INode[iip.length() + 1];
    System.arraycopy(iip.inodes, 0, inodes, 0, inodes.length - 1);
    inodes[inodes.length - 1] = child;
    byte[][] path = new byte[iip.path.length + 1][];
    System.arraycopy(iip.path, 0, path, 0, path.length - 1);
    path[path.length - 1] = childName;
    return new INodesInPath(inodes, path, iip.isRaw,
        iip.isSnapshot, iip.snapshotId);
  }

  private final byte[][] path;
  private volatile String pathname;

  /**
   * Array with the specified number of INodes resolved for a given path.
   */
  private final INode[] inodes;
  /**
   * true if this path corresponds to a snapshot
   */
  private final boolean isSnapshot;

  /**
   * true if this is a /.reserved/raw path.  path component resolution strips
   * it from the path so need to track it separately.
   */
  private final boolean isRaw;

  /**
   * For snapshot paths, it is the id of the snapshot; or 
   * {@link Snapshot#CURRENT_STATE_ID} if the snapshot does not exist. For 
   * non-snapshot paths, it is the id of the latest snapshot found in the path;
   * or {@link Snapshot#CURRENT_STATE_ID} if no snapshot is found.
   */
  private final int snapshotId;

  private INodesInPath(INode[] inodes, byte[][] path, boolean isRaw,
      boolean isSnapshot,int snapshotId) {
    Preconditions.checkArgument(inodes != null && path != null);
    this.inodes = inodes;
    this.path = path;
    this.isRaw = isRaw;
    this.isSnapshot = isSnapshot;
    this.snapshotId = snapshotId;
  }

  private INodesInPath(INode[] inodes, byte[][] path) {
    this(inodes, path, false, false, CURRENT_STATE_ID);
  }

  /**
   * For non-snapshot paths, return the latest snapshot id found in the path.
   */
  public int getLatestSnapshotId() {
    Preconditions.checkState(!isSnapshot);
    return snapshotId;
  }
  
  /**
   * For snapshot paths, return the id of the snapshot specified in the path.
   * For non-snapshot paths, return {@link Snapshot#CURRENT_STATE_ID}.
   */
  public int getPathSnapshotId() {
    return isSnapshot ? snapshotId : CURRENT_STATE_ID;
  }

  /**
   * @return the i-th inode if i {@literal >=} 0;
   *         otherwise, i {@literal <} 0, return the (length + i)-th inode.
   */
  public INode getINode(int i) {
    return inodes[(i < 0) ? inodes.length + i : i];
  }

  /** @return the last inode. */
  public INode getLastINode() {
    return getINode(-1);
  }

  byte[] getLastLocalName() {
    return path[path.length - 1];
  }

  public byte[][] getPathComponents() {
    return path;
  }

  public byte[] getPathComponent(int i) {
    return path[i];
  }

  /** @return the full path in string form */
  public String getPath() {
    if (pathname == null) {
      pathname = DFSUtil.byteArray2PathString(path);
    }
    return pathname;
  }

  public String getParentPath() {
    return getPath(path.length - 2);
  }

  public String getPath(int pos) {
    return DFSUtil.byteArray2PathString(path, 0, pos + 1); // it's a length...
  }

  public int length() {
    return inodes.length;
  }

  public INode[] getINodesArray() {
    INode[] retArr = new INode[inodes.length];
    System.arraycopy(inodes, 0, retArr, 0, inodes.length);
    return retArr;
  }

  /**
   * @param length number of ancestral INodes in the returned INodesInPath
   *               instance
   * @return the INodesInPath instance containing ancestral INodes. Note that
   * this method only handles non-snapshot paths.
   */
  private INodesInPath getAncestorINodesInPath(int length) {
    Preconditions.checkArgument(length >= 0 && length < inodes.length);
    Preconditions.checkState(isDotSnapshotDir() || !isSnapshot());
    final INode[] anodes = new INode[length];
    final byte[][] apath = new byte[length][];
    System.arraycopy(this.inodes, 0, anodes, 0, length);
    System.arraycopy(this.path, 0, apath, 0, length);
    return new INodesInPath(anodes, apath, isRaw, false, snapshotId);
  }

  /**
   * @return an INodesInPath instance containing all the INodes in the parent
   *         path. We do a deep copy here.
   */
  public INodesInPath getParentINodesInPath() {
    return inodes.length > 1 ? getAncestorINodesInPath(inodes.length - 1) :
        null;
  }

  /**
   * Verify if this {@link INodesInPath} is a descendant of the
   * requested {@link INodeDirectory}.
   *
   * @param inodeDirectory the ancestor directory
   * @return true if this INodesInPath is a descendant of inodeDirectory
   */
  public boolean isDescendant(final INodeDirectory inodeDirectory) {
    final INodesInPath dirIIP = fromINode(inodeDirectory);
    return isDescendant(dirIIP);
  }

  private boolean isDescendant(final INodesInPath ancestorDirIIP) {
    int ancestorDirINodesLength = ancestorDirIIP.length();
    int myParentINodesLength = length() - 1;
    if (myParentINodesLength < ancestorDirINodesLength) {
      return false;
    }

    int index = 0;
    while (index < ancestorDirINodesLength) {
      if (inodes[index] != ancestorDirIIP.getINode(index)) {
        return false;
      }
      index++;
    }
    return true;
  }


  /**
   * @return a new INodesInPath instance that only contains existing INodes.
   * Note that this method only handles non-snapshot paths.
   */
  public INodesInPath getExistingINodes() {
    Preconditions.checkState(!isSnapshot());
    for (int i = inodes.length; i > 0; i--) {
      if (inodes[i - 1] != null) {
        return (i == inodes.length) ? this : getAncestorINodesInPath(i);
      }
    }
    return null;
  }

  /**
   * @return isSnapshot true for a snapshot path
   */
  boolean isSnapshot() {
    return this.isSnapshot;
  }

  /**
   * @return if .snapshot is the last path component.
   */
  boolean isDotSnapshotDir() {
    return isDotSnapshotDir(getLastLocalName());
  }

  /**
   * @return if this is a /.reserved/raw path.
   */
  public boolean isRaw() {
    return isRaw;
  }

  private static String toString(INode inode) {
    return inode == null? null: inode.getLocalName();
  }

  @Override
  public String toString() {
    return toString(true);
  }

  private String toString(boolean vaildateObject) {
    if (vaildateObject) {
      validate();
    }

    final StringBuilder b = new StringBuilder(getClass().getSimpleName())
        .append(": path = ").append(getPath())
        .append("\n  inodes = ");
    if (inodes == null) {
      b.append("null");
    } else if (inodes.length == 0) {
      b.append("[]");
    } else {
      b.append("[").append(toString(inodes[0]));
      for(int i = 1; i < inodes.length; i++) {
        b.append(", ").append(toString(inodes[i]));
      }
      b.append("], length=").append(inodes.length);
    }
    b.append("\n  isSnapshot        = ").append(isSnapshot)
     .append("\n  snapshotId        = ").append(snapshotId);
    return b.toString();
  }

  void validate() {
    // check parent up to snapshotRootIndex if this is a snapshot path
    int i = 0;
    if (inodes[i] != null) {
      for(i++; i < inodes.length && inodes[i] != null; i++) {
        final INodeDirectory parent_i = inodes[i].getParent();
        final INodeDirectory parent_i_1 = inodes[i-1].getParent();
        if (parent_i != inodes[i-1] &&
            (parent_i_1 == null || !parent_i_1.isSnapshottable()
                || parent_i != parent_i_1)) {
          throw new AssertionError(
              "inodes[" + i + "].getParent() != inodes[" + (i-1)
              + "]\n  inodes[" + i + "]=" + inodes[i].toDetailString()
              + "\n  inodes[" + (i-1) + "]=" + inodes[i-1].toDetailString()
              + "\n this=" + toString(false));
        }
      }
    }
    if (i != inodes.length) {
      throw new AssertionError("i = " + i + " != " + inodes.length
          + ", this=" + toString(false));
    }
  }
}