/*
 * 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.commons.compress.archivers.dump;

import java.io.EOFException;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

import org.apache.commons.compress.archivers.ArchiveException;
import org.apache.commons.compress.archivers.ArchiveInputStream;
import org.apache.commons.compress.archivers.zip.ZipEncoding;
import org.apache.commons.compress.archivers.zip.ZipEncodingHelper;
import org.apache.commons.compress.utils.IOUtils;

/**
 * The DumpArchiveInputStream reads a UNIX dump archive as an InputStream. Methods are provided to position at each successive entry in the archive, and the
 * read each entry as a normal input stream using read().
 * <p>
 * There doesn't seem to exist a hint on the encoding of string values in any piece documentation. Given the main purpose of dump/restore is backing up a system
 * it seems very likely the format uses the current default encoding of the system.
 * </p>
 * @NotThreadSafe
 * @since 1.3
 */
public class DumpArchiveInputStream extends ArchiveInputStream<DumpArchiveEntry> {

    private static final String CURRENT_PATH_SEGMENT = ".";
    private static final String PARENT_PATH_SEGMENT = "..";

    /**
     * Look at the first few bytes of the file to decide if it's a dump archive. With 32 bytes we can look at the magic value, with a full 1k we can verify the
     * checksum.
     *
     * @param buffer data to match
     * @param length length of data
     * @return whether the buffer seems to contain dump data
     */
    public static boolean matches(final byte[] buffer, final int length) {
        // do we have enough of the header?
        if (length < 32) {
            return false;
        }

        // this is the best test
        if (length >= DumpArchiveConstants.TP_SIZE) {
            return DumpArchiveUtil.verify(buffer);
        }

        // this will work in a pinch.
        return DumpArchiveConstants.NFS_MAGIC == DumpArchiveUtil.convert32(buffer, 24);
    }

    private final DumpArchiveSummary summary;
    private DumpArchiveEntry active;
    private boolean isClosed;
    private boolean hasHitEOF;
    private long entrySize;
    private long entryOffset;
    private int readIdx;
    private final byte[] readBuf = new byte[DumpArchiveConstants.TP_SIZE];
    private byte[] blockBuffer;
    private int recordOffset;
    private long filepos;

    protected TapeInputStream raw;

    /** Map of ino -> dirent entry. We can use this to reconstruct full paths. */
    private final Map<Integer, Dirent> names = new HashMap<>();

    /** Map of ino -> (directory) entry when we're missing one or more elements in the path. */
    private final Map<Integer, DumpArchiveEntry> pending = new HashMap<>();

    /** Queue of (directory) entries where we now have the full path. */
    private final Queue<DumpArchiveEntry> queue;

    /**
     * The encoding to use for file names and labels.
     */
    private final ZipEncoding zipEncoding;

    /**
     * Constructor using the platform's default encoding for file names.
     *
     * @param is stream to read from
     * @throws ArchiveException on error
     */
    public DumpArchiveInputStream(final InputStream is) throws ArchiveException {
        this(is, null);
    }

    /**
     * Constructs a new instance.
     *
     * @param is       stream to read from
     * @param encoding the encoding to use for file names, use null for the platform's default encoding
     * @since 1.6
     * @throws ArchiveException on error
     */
    public DumpArchiveInputStream(final InputStream is, final String encoding) throws ArchiveException {
        super(is, encoding);
        this.raw = new TapeInputStream(is);
        this.hasHitEOF = false;
        this.zipEncoding = ZipEncodingHelper.getZipEncoding(encoding);

        try {
            // read header, verify it's a dump archive.
            final byte[] headerBytes = raw.readRecord();

            if (!DumpArchiveUtil.verify(headerBytes)) {
                throw new UnrecognizedFormatException();
            }

            // get summary information
            summary = new DumpArchiveSummary(headerBytes, this.zipEncoding);

            // reset buffer with actual block size.
            raw.resetBlockSize(summary.getNTRec(), summary.isCompressed());

            // allocate our read buffer.
            blockBuffer = new byte[4 * DumpArchiveConstants.TP_SIZE];

            // skip past CLRI and BITS segments since we don't handle them yet.
            readCLRI();
            readBITS();
        } catch (final IOException ex) {
            throw new ArchiveException(ex.getMessage(), ex);
        }

        // put in a dummy record for the root node.
        final Dirent root = new Dirent(2, 2, 4, CURRENT_PATH_SEGMENT);
        names.put(2, root);

        // use priority based on queue to ensure parent directories are
        // released first.
        queue = new PriorityQueue<>(10, (p, q) -> {
            if (p.getOriginalName() == null || q.getOriginalName() == null) {
                return Integer.MAX_VALUE;
            }

            return p.getOriginalName().compareTo(q.getOriginalName());
        });
    }

    /**
     * Closes the stream for this entry.
     */
    @Override
    public void close() throws IOException {
        if (!isClosed) {
            isClosed = true;
            raw.close();
        }
    }

    @Override
    public long getBytesRead() {
        return raw.getBytesRead();
    }

    @Deprecated
    @Override
    public int getCount() {
        return (int) getBytesRead();
    }

    /**
     * Reads the next entry.
     *
     * @return the next entry
     * @throws IOException on error
     * @deprecated Use {@link #getNextEntry()}.
     */
    @Deprecated
    public DumpArchiveEntry getNextDumpEntry() throws IOException {
        return getNextEntry();
    }

    @Override
    public DumpArchiveEntry getNextEntry() throws IOException {
        DumpArchiveEntry entry = null;
        String path = null;

        // is there anything in the queue?
        if (!queue.isEmpty()) {
            return queue.remove();
        }

        while (entry == null) {
            if (hasHitEOF) {
                return null;
            }

            // skip any remaining records in this segment for prior file.
            // we might still have holes... easiest to do it
            // block by block. We may want to revisit this if
            // the unnecessary decompression time adds up.
            while (readIdx < active.getHeaderCount()) {
                if (!active.isSparseRecord(readIdx++) && raw.skip(DumpArchiveConstants.TP_SIZE) == -1) {
                    throw new EOFException();
                }
            }

            readIdx = 0;
            filepos = raw.getBytesRead();

            byte[] headerBytes = raw.readRecord();

            if (!DumpArchiveUtil.verify(headerBytes)) {
                throw new InvalidFormatException();
            }

            active = DumpArchiveEntry.parse(headerBytes);

            // skip any remaining segments for prior file.
            while (DumpArchiveConstants.SEGMENT_TYPE.ADDR == active.getHeaderType()) {
                if (raw.skip((long) DumpArchiveConstants.TP_SIZE * (active.getHeaderCount() - active.getHeaderHoles())) == -1) {
                    throw new EOFException();
                }

                filepos = raw.getBytesRead();
                headerBytes = raw.readRecord();

                if (!DumpArchiveUtil.verify(headerBytes)) {
                    throw new InvalidFormatException();
                }

                active = DumpArchiveEntry.parse(headerBytes);
            }

            // check if this is an end-of-volume marker.
            if (DumpArchiveConstants.SEGMENT_TYPE.END == active.getHeaderType()) {
                hasHitEOF = true;

                return null;
            }

            entry = active;

            if (entry.isDirectory()) {
                readDirectoryEntry(active);

                // now we create an empty InputStream.
                entryOffset = 0;
                entrySize = 0;
                readIdx = active.getHeaderCount();
            } else {
                entryOffset = 0;
                entrySize = active.getEntrySize();
                readIdx = 0;
            }

            recordOffset = readBuf.length;

            path = getPath(entry);

            if (path == null) {
                entry = null;
            }
        }

        entry.setName(path);
        entry.setSimpleName(names.get(entry.getIno()).getName());
        entry.setOffset(filepos);

        return entry;
    }

    /**
     * Gets full path for specified archive entry, or null if there's a gap.
     *
     * @param entry
     * @return full path for specified archive entry, or null if there's a gap.
     * @throws DumpArchiveException Infinite loop detected in directory entries.
     */
    private String getPath(final DumpArchiveEntry entry) throws DumpArchiveException {
        // build the stack of elements. It's possible that we're
        // still missing an intermediate value and if so we
        final Stack<String> elements = new Stack<>();
        final BitSet visited = new BitSet();
        Dirent dirent = null;
        for (int i = entry.getIno();; i = dirent.getParentIno()) {
            if (!names.containsKey(i)) {
                elements.clear();
                break;
            }
            if (visited.get(i)) {
                throw new DumpArchiveException("Duplicate node " + i);
            }
            dirent = names.get(i);
            visited.set(i);
            elements.push(dirent.getName());
            if (dirent.getIno() == dirent.getParentIno()) {
                break;
            }
        }
        // if an element is missing defer the work and read next entry.
        if (elements.isEmpty()) {
            pending.put(entry.getIno(), entry);
            return null;
        }
        // generate full path from stack of elements.
        final StringBuilder sb = new StringBuilder(elements.pop());
        while (!elements.isEmpty()) {
            sb.append('/');
            sb.append(elements.pop());
        }
        return sb.toString();
    }

    /**
     * Gets the archive summary information.
     *
     * @return the summary
     */
    public DumpArchiveSummary getSummary() {
        return summary;
    }

    /**
     * Reads bytes from the current dump archive entry.
     *
     * This method is aware of the boundaries of the current entry in the archive and will deal with them as if they were this stream's start and EOF.
     *
     * @param buf The buffer into which to place bytes read.
     * @param off The offset at which to place bytes read.
     * @param len The number of bytes to read.
     * @return The number of bytes read, or -1 at EOF.
     * @throws IOException on error
     */
    @Override
    public int read(final byte[] buf, int off, int len) throws IOException {
        if (len == 0) {
            return 0;
        }
        int totalRead = 0;

        if (hasHitEOF || isClosed || entryOffset >= entrySize) {
            return -1;
        }

        if (active == null) {
            throw new IllegalStateException("No current dump entry");
        }

        if (len + entryOffset > entrySize) {
            len = (int) (entrySize - entryOffset);
        }

        while (len > 0) {
            final int sz = Math.min(len, readBuf.length - recordOffset);

            // copy any data we have
            if (recordOffset + sz <= readBuf.length) {
                System.arraycopy(readBuf, recordOffset, buf, off, sz);
                totalRead += sz;
                recordOffset += sz;
                len -= sz;
                off += sz;
            }

            // load next block if necessary.
            if (len > 0) {
                if (readIdx >= 512) {
                    final byte[] headerBytes = raw.readRecord();

                    if (!DumpArchiveUtil.verify(headerBytes)) {
                        throw new InvalidFormatException();
                    }

                    active = DumpArchiveEntry.parse(headerBytes);
                    readIdx = 0;
                }

                if (!active.isSparseRecord(readIdx++)) {
                    final int r = raw.read(readBuf, 0, readBuf.length);
                    if (r != readBuf.length) {
                        throw new EOFException();
                    }
                } else {
                    Arrays.fill(readBuf, (byte) 0);
                }

                recordOffset = 0;
            }
        }

        entryOffset += totalRead;

        return totalRead;
    }

    /**
     * Read BITS segment.
     */
    private void readBITS() throws IOException {
        final byte[] buffer = raw.readRecord();

        if (!DumpArchiveUtil.verify(buffer)) {
            throw new InvalidFormatException();
        }

        active = DumpArchiveEntry.parse(buffer);

        if (DumpArchiveConstants.SEGMENT_TYPE.BITS != active.getHeaderType()) {
            throw new InvalidFormatException();
        }

        // we don't do anything with this yet.
        if (raw.skip((long) DumpArchiveConstants.TP_SIZE * active.getHeaderCount()) == -1) {
            throw new EOFException();
        }
        readIdx = active.getHeaderCount();
    }

    /**
     * Read CLRI (deleted inode) segment.
     */
    private void readCLRI() throws IOException {
        final byte[] buffer = raw.readRecord();

        if (!DumpArchiveUtil.verify(buffer)) {
            throw new InvalidFormatException();
        }

        active = DumpArchiveEntry.parse(buffer);

        if (DumpArchiveConstants.SEGMENT_TYPE.CLRI != active.getHeaderType()) {
            throw new InvalidFormatException();
        }

        // we don't do anything with this yet.
        if (raw.skip((long) DumpArchiveConstants.TP_SIZE * active.getHeaderCount()) == -1) {
            throw new EOFException();
        }
        readIdx = active.getHeaderCount();
    }

    /**
     * Read directory entry.
     */
    private void readDirectoryEntry(DumpArchiveEntry entry) throws IOException {
        long size = entry.getEntrySize();
        boolean first = true;

        while (first || DumpArchiveConstants.SEGMENT_TYPE.ADDR == entry.getHeaderType()) {
            // read the header that we just peeked at.
            if (!first) {
                raw.readRecord();
            }

            if (!names.containsKey(entry.getIno()) && DumpArchiveConstants.SEGMENT_TYPE.INODE == entry.getHeaderType()) {
                pending.put(entry.getIno(), entry);
            }

            final int datalen = DumpArchiveConstants.TP_SIZE * entry.getHeaderCount();

            if (blockBuffer.length < datalen) {
                blockBuffer = IOUtils.readRange(raw, datalen);
                if (blockBuffer.length != datalen) {
                    throw new EOFException();
                }
            } else if (raw.read(blockBuffer, 0, datalen) != datalen) {
                throw new EOFException();
            }

            int reclen = 0;

            for (int i = 0; i < datalen - 8 && i < size - 8; i += reclen) {
                final int ino = DumpArchiveUtil.convert32(blockBuffer, i);
                reclen = DumpArchiveUtil.convert16(blockBuffer, i + 4);
                if (reclen == 0) {
                    throw new DumpArchiveException("reclen cannot be 0");
                }

                final byte type = blockBuffer[i + 6];

                final String name = DumpArchiveUtil.decode(zipEncoding, blockBuffer, i + 8, blockBuffer[i + 7]);

                if (CURRENT_PATH_SEGMENT.equals(name) || PARENT_PATH_SEGMENT.equals(name)) {
                    // do nothing...
                    continue;
                }

                final Dirent d = new Dirent(ino, entry.getIno(), type, name);

                /*
                 * if ((type == 4) && names.containsKey(ino)) { System.out.println("we already have ino: " + names.get(ino)); }
                 */

                names.put(ino, d);

                // check whether this allows us to fill anything in the pending list.
                for (final Map.Entry<Integer, DumpArchiveEntry> mapEntry : pending.entrySet()) {
                    final DumpArchiveEntry v = mapEntry.getValue();
                    final String path = getPath(v);
                    if (path != null) {
                        v.setName(path);
                        v.setSimpleName(names.get(mapEntry.getKey()).getName());
                        queue.add(v);
                    }
                }

                // remove anything that we found. (We can't do it earlier
                // because of concurrent modification exceptions.)
                queue.forEach(e -> pending.remove(e.getIno()));
            }

            final byte[] peekBytes = raw.peek();

            if (!DumpArchiveUtil.verify(peekBytes)) {
                throw new InvalidFormatException();
            }

            entry = DumpArchiveEntry.parse(peekBytes);
            first = false;
            size -= DumpArchiveConstants.TP_SIZE;
        }
    }

}