/*
 * Copyright (C) 2019 The Android Open Source Project
 *
 * 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.android.tools.lint.checks;

import com.android.annotations.NonNull;
import com.android.tools.lint.client.api.LintClient;
import com.google.common.io.Files;
import java.io.File;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Random;
import kotlin.text.Charsets;

/**
 * Database for API checking, providing efficient lookup for a given class, method or field.
 *
 * <p>This class provides a binary cache around an API to make initialization faster and to require
 * fewer objects. It creates a binary cache data structure which fits in a single byte array,
 * meaning that to open the database you can just read in the byte array and go. On one particular
 * machine, this takes about 30-50 ms versus seconds for the full parse. It also helps memory by
 * placing everything in a compact byte array instead of needing separate strings (2 bytes per
 * character in a char[] for the 25k method entries, 11k field entries and 6k class entries) - and
 * it also avoids the same number of Map.Entry objects.
 *
 * <p>Note: It stores the strings as single bytes, since all the JVM signatures are in ASCII.
 */
public class ApiDatabase {
    protected static final String FILE_HEADER = "API database used by Android lint\000";

    protected static final boolean DEBUG_SEARCH = false;
    protected static final boolean WRITE_STATS = false;

    public static final int HAS_EXTRA_BYTE_FLAG = 1 << 7;
    public static final int API_MASK = ~HAS_EXTRA_BYTE_FLAG;

    private static final int BINARY_FORMAT_VERSION = 15;

    protected byte[] mData;
    protected int[] mIndices;
    protected int containerCount;

    @FunctionalInterface
    interface CacheCreator {
        boolean create(LintClient client, File binaryData);
    }

    /**
     * Computes the binary format version
     *
     * <p>This is a byte, the first 3 bits of which are from the {@param majorBinaryFormatVersion}
     * specified by subclasses (which can change the representation of the custom API attributes),
     * and the remaining 5 bits are a minor version from this class ({@code BINARY_FORMAT_VERSION}),
     * which controls the binary representation of most of the Api.
     *
     * @param majorBinaryFormatVersion which must fit in 3 bits (therefore less than 8)
     * @return the computed binary format version
     */
    public static int getBinaryFormatVersion(int majorBinaryFormatVersion) {
        assert (majorBinaryFormatVersion & 0x07) == majorBinaryFormatVersion;
        return majorBinaryFormatVersion << 5 + BINARY_FORMAT_VERSION;
    }

    /**
     * Database format:
     *
     * <pre>
     * (Note: all numbers are big endian; the format uses 1, 2, 3 and 4 byte integers.)
     *
     *
     * 1. A file header, which is the exact contents of {@link #FILE_HEADER} encoded
     *     as ASCII characters. The purpose of the header is to identify what the file
     *     is for, for anyone attempting to open the file.
     * 2. A file version number. If the binary file does not match the reader's expected
     *     version, it can ignore it (and regenerate the cache from XML).
     *
     * 3. The index table. When the data file is read, this is used to initialize the
     *    {@link #mIndices} array. The index table is built up like this:
     *    a. The number of index entries (e.g. number of elements in the {@link #mIndices} array)
     *        [a 4-byte integer]
     *    b. The number of java/javax packages [a 4-byte integer]
     *    c. Offsets to the container entries, one for each package or a class containing inner
     *       classes [a 4-byte integer].
     *    d. Offsets to the class entries, one for each class [a 4-byte integer].
     *    e. Offsets to the member entries, one for each member [a 4-byte integer].
     *
     * 4. The member entries -- one for each member. A given class entry will point to the
     *    first and last members in the index table above, and the offset of a given member
     *    is pointing to the offset of these entries.
     *    a. The name and description (except for the return value) of the member, in JVM format
     *       (e.g. for toLowerCase(char) we'd have "toLowerCase(C)". This is converted into
     *       UTF_8 representation as bytes [n bytes, the length of the byte representation of
     *       the description).
     *    b. A terminating 0 byte [1 byte].
     *    c. A sequence of bytes representing custom data attached to this entry, to be interpreted
     *       by the consumer.
     *       All bytes except the last one have the top bit ({@link #HAS_EXTRA_BYTE_FLAG}) set.
     *
     * 5. The class entries -- one for each class.
     *    a. The index within this class entry where the metadata (other than the name)
     *       can be found. [1 byte]. This means that if you know a class by its number,
     *       you can quickly jump to its metadata without scanning through the string to
     *       find the end of it, by just adding this byte to the current offset and
     *       then you're at the data described below for (d).
     *    b. The name of the class (just the base name, not the package), as encoded as a
     *       UTF-8 string. [n bytes]
     *    c. A terminating 0 [1 byte].
     *    d. The index in the index table (3) of the first member in the class [a 3-byte integer.]
     *    e. The number of members in the class [a 2-byte integer].
     *    f. Custom metadata associated with the class.
     *
     * 6. The container entries -- one for each package and for each class containing inner classes.
     *    a. The name of the package or the outer class [n bytes].
     *    b. A terminating 0 for packages, or 1 for outer classes [1 byte].
     *    c. The index in the index table (3) of the first class in the package or the first inner
     *       class [a 3-byte integer.]
     *    d. The number of classes in the package or the number of inner classes in the outer class
     *       [a 2-byte integer].
     * </pre>
     */
    protected void readData(
            @NonNull LintClient client,
            @NonNull File binaryFile,
            @NonNull CacheCreator cacheCreator,
            int majorBinaryFormatVersion) {
        if (!binaryFile.exists()) {
            client.log(null, "%1$s does not exist", binaryFile);
            return;
        }
        long start = WRITE_STATS ? System.currentTimeMillis() : 0;
        try {
            byte[] b = Files.toByteArray(binaryFile);

            // First skip the header
            int offset = 0;
            byte[] expectedHeader = FILE_HEADER.getBytes(Charsets.US_ASCII);
            for (byte anExpectedHeader : expectedHeader) {
                if (anExpectedHeader != b[offset++]) {
                    client.log(
                            null,
                            "Incorrect file header: not an API database cache "
                                    + "file, or a corrupt cache file");
                    return;
                }
            }

            // Read in the format number.
            if (b[offset++] != getBinaryFormatVersion(majorBinaryFormatVersion)) {
                // Force regeneration of new binary data with up to date format.
                if (cacheCreator.create(client, binaryFile)) {
                    readData(client, binaryFile, cacheCreator, majorBinaryFormatVersion); // Recurse
                }

                return;
            }

            int indexCount = get4ByteInt(b, offset);
            offset += 4;
            containerCount = get4ByteInt(b, offset);
            offset += 4;

            mIndices = new int[indexCount];
            for (int i = 0; i < indexCount; i++) {
                // TODO: Pack the offsets: They increase by a small amount for each entry, so
                // no need to spend 4 bytes on each. These will need to be processed when read
                // back in anyway, so consider storing the offset -deltas- as single bytes and
                // adding them up cumulatively in readData().
                mIndices[i] = get4ByteInt(b, offset);
                offset += 4;
            }
            mData = b;
            // TODO: We only need to keep the data portion here since we've initialized
            // the offset array separately.
            // TODO: Investigate (profile) accessing the byte buffer directly instead of
            // accessing a byte array.

            if (WRITE_STATS) {
                long end = System.currentTimeMillis();
                System.out.println("\nRead API database in " + (end - start) + " milliseconds.");
                System.out.print("Size of data table: " + mData.length + " bytes");
                System.out.println(
                        String.format(Locale.US, " (%.3gMB)", mData.length / (1024. * 1024.)));
            }
        } catch (Throwable e) {
            client.log(null, "Failure reading binary cache file %1$s", binaryFile.getPath());
            client.log(
                    null,
                    "Please delete the file and restart the IDE/lint: %1$s",
                    binaryFile.getPath());
            client.log(e, null);
        }
    }

    /**
     * See the {@link #readData(LintClient, File, CacheCreator, int)} for documentation on the data
     * format.
     */
    protected static void writeDatabase(
            File file, Api<? extends ApiClassBase> info, int majorBinaryFormatVersion)
            throws IOException {
        Map<String, ? extends ApiClassBase> classMap = info.getClasses();

        List<ApiClassOwner<? extends ApiClassBase>> containers =
                new ArrayList<>(info.getContainers().values());
        Collections.sort(containers);

        // Compute members of each class that must be included in the database; we can
        // skip those that have the same since-level as the containing class. And we
        // also need to keep those entries that are marked deprecated or removed.
        int estimatedSize = 0;
        for (ApiClassOwner<? extends ApiClassBase> container : containers) {
            estimatedSize += 4; // offset entry
            estimatedSize += container.getName().length() + 20; // Container entry.

            for (ApiClassBase cls : container.getClasses()) {
                estimatedSize += 4; // offset entry
                estimatedSize += cls.getName().length() + 20; // Class entry.

                estimatedSize += cls.computeExtraStorageNeeded(info);
            }

            // Ensure that the classes are sorted.
            Collections.sort(container.getClasses());
        }

        // Write header
        ByteBuffer buffer = ByteBuffer.allocate(estimatedSize);
        buffer.order(ByteOrder.BIG_ENDIAN);
        buffer.put(FILE_HEADER.getBytes(StandardCharsets.US_ASCII));
        buffer.put((byte) getBinaryFormatVersion(majorBinaryFormatVersion));

        int indexCountOffset = buffer.position();
        int indexCount = 0;

        buffer.putInt(0); // placeholder

        // Write the number of containers in the containers index.
        buffer.putInt(containers.size());

        // Write container index.
        int newIndex = buffer.position();
        for (ApiClassOwner container : containers) {
            container.indexOffset = newIndex;
            newIndex += 4;
            indexCount++;
        }

        // Write class index.
        for (ApiClassOwner<? extends ApiClassBase> container : containers) {
            for (ApiClassBase cls : container.getClasses()) {
                cls.indexOffset = newIndex;
                cls.index = indexCount;
                newIndex += 4;
                indexCount++;
            }
        }

        // Write member indices.
        for (ApiClassOwner<? extends ApiClassBase> container : containers) {
            for (ApiClassBase cls : container.getClasses()) {
                if (cls.members != null && !cls.members.isEmpty()) {
                    cls.memberOffsetBegin = newIndex;
                    cls.memberIndexStart = indexCount;
                    for (String ignored : cls.members) {
                        newIndex += 4;
                        indexCount++;
                    }
                    cls.memberOffsetEnd = newIndex;
                    cls.memberIndexLength = indexCount - cls.memberIndexStart;
                } else {
                    cls.memberOffsetBegin = -1;
                    cls.memberOffsetEnd = -1;
                    cls.memberIndexStart = -1;
                    cls.memberIndexLength = 0;
                }
            }
        }

        // Fill in the earlier index count.
        buffer.position(indexCountOffset);
        buffer.putInt(indexCount);
        buffer.position(newIndex);

        // Write member entries.
        for (ApiClassOwner<? extends ApiClassBase> container : containers) {
            for (ApiClassBase apiClass : container.getClasses()) {
                int index = apiClass.memberOffsetBegin;
                for (String member : apiClass.members) {
                    // Update member offset to point to this entry
                    int start = buffer.position();
                    buffer.position(index);
                    buffer.putInt(start);
                    index = buffer.position();
                    buffer.position(start);

                    apiClass.writeMemberData(info, member, buffer);
                }
                assert index == apiClass.memberOffsetEnd : apiClass.memberOffsetEnd;
            }
        }

        // Write class entries. These are written together, rather than
        // being spread out among the member entries, in order to have
        // reference locality (search that a binary search through the classes
        // are likely to look at entries near each other.)
        for (ApiClassOwner<? extends ApiClassBase> container : containers) {
            List<? extends ApiClassBase> classes = container.getClasses();
            for (ApiClassBase cls : classes) {
                int index = buffer.position();
                buffer.position(cls.indexOffset);
                buffer.putInt(index);
                buffer.position(index);
                String name = cls.getSimpleName();
                int pos = name.lastIndexOf('$');
                if (pos > 0) {
                    name = name.substring(pos + 1);
                }

                byte[] nameBytes = name.getBytes(StandardCharsets.UTF_8);
                assert nameBytes.length < 254 : name;
                buffer.put((byte) (nameBytes.length + 2)); // 2: terminating 0, and this byte itself
                buffer.put(nameBytes);
                buffer.put((byte) 0);

                // 3 bytes for beginning, 2 bytes for *length*
                put3ByteInt(buffer, cls.memberIndexStart);
                put2ByteInt(buffer, cls.memberIndexLength);

                ApiClassBase apiClass = classMap.get(cls.getName());
                assert apiClass != null : cls.getName();
                apiClass.writeSuperInterfaces(info, buffer);
            }
        }

        for (ApiClassOwner<? extends ApiClassBase> container : containers) {
            int index = buffer.position();
            buffer.position(container.indexOffset);
            buffer.putInt(index);
            buffer.position(index);

            byte[] bytes = container.getName().getBytes(StandardCharsets.UTF_8);
            buffer.put(bytes);
            buffer.put(container.isClass() ? (byte) 1 : (byte) 0);

            List<? extends ApiClassBase> classes = container.getClasses();
            if (classes.isEmpty()) {
                put3ByteInt(buffer, 0);
                put2ByteInt(buffer, 0);
            } else {
                // 3 bytes for beginning, 2 bytes for *length*
                int firstClassIndex = classes.get(0).index;
                int classCount = classes.get(classes.size() - 1).index - firstClassIndex + 1;
                put3ByteInt(buffer, firstClassIndex);
                put2ByteInt(buffer, classCount);
            }
        }

        int size = buffer.position();
        assert size <= buffer.limit();
        buffer.mark();

        if (WRITE_STATS) {
            System.out.print("Actual binary size: " + size + " bytes");
            System.out.println(String.format(Locale.US, " (%.3gMB)", size / (1024. * 1024.)));
        }

        // Now dump this out as a file
        // There's probably an API to do this more efficiently; TODO: Look into this.
        byte[] b = new byte[size];
        buffer.rewind();
        buffer.get(b);
        if (file.exists()) {
            boolean deleted = file.delete();
            assert deleted : file;
        }

        // Write to a different file and swap it in last minute.
        // This helps in scenarios where multiple simultaneous Gradle
        // threads are attempting to access the file before it's ready.
        File tmp = new File(file.getPath() + "." + new Random().nextInt());
        Files.asByteSink(tmp).write(b);
        if (!tmp.renameTo(file)) {
            //noinspection ResultOfMethodCallIgnored
            tmp.delete();
        }
    }

    protected static int get4ByteInt(@NonNull byte[] data, int offset) {
        byte b1 = data[offset++];
        byte b2 = data[offset++];
        byte b3 = data[offset++];
        byte b4 = data[offset];
        // The byte data is always big endian.
        return (b1 & 0xFF) << 24 | (b2 & 0xFF) << 16 | (b3 & 0xFF) << 8 | (b4 & 0xFF);
    }

    protected static void put3ByteInt(@NonNull ByteBuffer buffer, int value) {
        // Big endian
        byte b3 = (byte) (value & 0xFF);
        value >>>= 8;
        byte b2 = (byte) (value & 0xFF);
        value >>>= 8;
        byte b1 = (byte) (value & 0xFF);
        buffer.put(b1);
        buffer.put(b2);
        buffer.put(b3);
    }

    protected static void put2ByteInt(@NonNull ByteBuffer buffer, int value) {
        // Big endian
        byte b2 = (byte) (value & 0xFF);
        value >>>= 8;
        byte b1 = (byte) (value & 0xFF);
        buffer.put(b1);
        buffer.put(b2);
    }

    protected static int get3ByteInt(@NonNull byte[] mData, int offset) {
        byte b1 = mData[offset++];
        byte b2 = mData[offset++];
        byte b3 = mData[offset];
        // The byte data is always big endian.
        return (b1 & 0xFF) << 16 | (b2 & 0xFF) << 8 | (b3 & 0xFF);
    }

    protected static int get2ByteInt(@NonNull byte[] data, int offset) {
        byte b1 = data[offset++];
        byte b2 = data[offset];
        // The byte data is always big endian.
        return (b1 & 0xFF) << 8 | (b2 & 0xFF);
    }

    // For debugging only
    protected String dumpEntry(int offset) {
        if (DEBUG_SEARCH) {
            StringBuilder sb = new StringBuilder(200);
            for (int i = offset; i < mData.length; i++) {
                byte b = mData[i];
                if (b == 0 || b == 1) {
                    break;
                }
                char c = (char) Byte.toUnsignedInt(b);
                sb.append(c);
            }

            return sb.toString();
        } else {
            return "<disabled>";
        }
    }

    protected static int compare(
            byte[] data, int offset, byte terminator, String s, int sOffset, int max) {
        int i = offset;
        int j = sOffset;
        for (; j < max; i++, j++) {
            byte b = data[i];
            char c = s.charAt(j);
            if (c == '.' && (b == '/' || b == '$')) { // '.' matches both '/' and '$'.
                continue;
            }
            // TODO: Check somewhere that the strings are purely in the ASCII range.
            // If not, they will not match the database.
            byte cb = (byte) c;
            int delta = b - cb;
            if (delta != 0) {
                return delta;
            }
        }

        byte b = data[i];
        if (terminator == 1 && b == 0) { // Terminator 1 matches both 0 and 1.
            return 0;
        }
        return b - terminator;
    }

    /** Returns the container index of the given package or class, or -1 if it is unknown. */
    protected int findContainer(
            @NonNull String packageOrClassName, int containerNameLength, boolean packageOnly) {
        // The index array contains class indexes from 0 to classCount and
        // member indices from classCount to mIndices.length.
        int low = 0;
        int high = containerCount;
        while (low < high) {
            int middle = (low + high) >>> 1;
            int offset = mIndices[middle];

            if (DEBUG_SEARCH) {
                System.out.println(
                        "Comparing string \""
                                + packageOrClassName.substring(0, containerNameLength)
                                + "\" with entry at "
                                + offset
                                + ": "
                                + dumpEntry(offset));
            }

            byte terminator = packageOnly ? (byte) 0 : (byte) 1;
            int c = compare(mData, offset, terminator, packageOrClassName, 0, containerNameLength);
            if (c == 0) {
                if (DEBUG_SEARCH) {
                    System.out.println("Found " + dumpEntry(offset));
                }
                return middle;
            }

            if (c < 0) {
                low = middle + 1;
            } else {
                assert c > 0;
                high = middle;
            }
        }

        return -1;
    }

    /** Returns the class number of the given class, or -1 if it is unknown. */
    protected int findClass(@NonNull String className) {
        int lastSeparator = lastIndexOfDotOrSlashOrDollar(className);
        int containerNameLength = lastSeparator >= 0 ? lastSeparator : 0;
        int containerNumber = findContainer(className, containerNameLength, false);
        if (containerNumber < 0) {
            return -1;
        }
        int classNameLength = className.length();
        int classNameOffset = lastSeparator + 1;

        int curr = mIndices[containerNumber];
        // Skip the name of the container.
        while ((mData[curr] & ~1) != 0) { // Iterate until encountering 0 or 1.
            curr++;
        }
        curr++;

        // 3 bytes for first offset.
        int low = get3ByteInt(mData, curr);
        curr += 3;

        int length = get2ByteInt(mData, curr);
        int high = low + length;
        while (low < high) {
            int middle = (low + high) >>> 1;
            int offset = mIndices[middle];
            offset++; // Skip the byte which points to the metadata after the name.

            if (DEBUG_SEARCH) {
                System.out.println(
                        "Comparing string "
                                + className.substring(0, classNameLength)
                                + " with entry at "
                                + offset
                                + ": "
                                + dumpEntry(offset));
            }

            int c = compare(mData, offset, (byte) 0, className, classNameOffset, classNameLength);
            if (c == 0) {
                if (DEBUG_SEARCH) {
                    System.out.println("Found " + dumpEntry(offset));
                }
                return middle;
            }

            if (c < 0) {
                low = middle + 1;
            } else {
                assert c > 0;
                high = middle;
            }
        }

        return -1;
    }

    private static int lastIndexOfDotOrSlashOrDollar(@NonNull String className) {
        for (int i = className.length(); --i >= 0; ) {
            char c = className.charAt(i);
            if (c == '.' || c == '/' || c == '$') {
                return i;
            }
        }
        return -1;
    }
}