/*
 * Copyright 2021 The Netty Project
 *
 * The Netty Project 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:
 *
 *   https://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 io.netty.handler.codec.http3;

import io.netty.util.AsciiString;

import static io.netty.handler.codec.http3.QpackHeaderField.ENTRY_OVERHEAD;
import static io.netty.handler.codec.http3.QpackUtil.MAX_HEADER_TABLE_SIZE;
import static io.netty.handler.codec.http3.QpackUtil.MIN_HEADER_TABLE_SIZE;
import static io.netty.handler.codec.http3.QpackUtil.equalsVariableTime;
import static io.netty.util.AsciiString.EMPTY_STRING;
import static io.netty.util.internal.MathUtil.findNextPositivePowerOfTwo;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.toIntExact;

final class QpackEncoderDynamicTable {
    private static final QpackException INVALID_KNOW_RECEIVED_COUNT_INCREMENT =
            QpackException.newStatic(QpackDecoder.class, "incrementKnownReceivedCount(...)",
                    "QPACK - invalid known received count increment.");
    private static final QpackException INVALID_REQUIRED_INSERT_COUNT_INCREMENT =
            QpackException.newStatic(QpackDecoder.class, "acknowledgeInsertCount(...)",
                    "QPACK - invalid required insert count acknowledgment.");
    private static final QpackException INVALID_TABLE_CAPACITY =
            QpackException.newStatic(QpackDecoder.class, "validateCapacity(...)",
                    "QPACK - dynamic table capacity is invalid.");
    private static final QpackException CAPACITY_ALREADY_SET =
            QpackException.newStatic(QpackDecoder.class, "maxTableCapacity(...)",
                    "QPACK - dynamic table capacity is already set.");
    /**
     * Special return value of {@link #getEntryIndex(CharSequence, CharSequence)} when the entry is not found.
     */
    public static final int NOT_FOUND = Integer.MIN_VALUE;

    /**
     * A hashmap of header entries.
     */
    private final HeaderEntry[] fields;

    /**
     * Percentage of capacity that we expect to be free after eviction of old entries.
     */
    private final int expectedFreeCapacityPercentage;

    /**
     * Hash mask for all entries in the hashmap.
     */
    private final byte hashMask;

    /**
     * <a href="https://www.rfc-editor.org/rfc/rfc9204.html#name-dynamic-table-size">Current size of the table</a>.
     */
    private long size;

    /**
     * <a href="https://www.rfc-editor.org/rfc/rfc9204.html#name-maximum-dynamic-table-capac">
     *     Maximum capacity of the table</a>. This is set once based on the
     *     {@link Http3SettingsFrame#HTTP3_SETTINGS_QPACK_MAX_TABLE_CAPACITY} received by the remote peer.
     */
    private long maxTableCapacity = -1;

    /*
     * The below indexes follow the suggested heuristics in Section 2.1.1.1 Avoiding Prohibited insertions
     * https://www.rfc-editor.org/rfc/rfc9204.html#name-avoiding-prohibited-inserti
     *
     *                Tail                             Drain       Head
     *                 |                                |           |
     *                 v                                v           v
     *       +--------+---------------------------------+----------+
     *       | Unused |          Referenceable          | Draining |
     *       | Space  |             Entries             | Entries  |
     *       +--------+---------------------------------+----------+
     *                ^                                 ^          ^
     *                |                                 |          |
     *          Insertion Index                 Draining Index  Dropping Index
     */

    /**
     * Head of the entries, such that {@link HeaderEntry#index} is the {@code droppingIndex}.
     */
    private final HeaderEntry head;

    /**
     * Pointer before which entries are marked for eviction post {@link #incrementKnownReceivedCount(int)}.
     * {@link HeaderEntry#index} is the {@code drainingIndex}.
     */
    private HeaderEntry drain;

     /**
     * Pointer to the entry representing the <a
     * href="https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#name-known-received-count">
     * known received count</a>.
     */
    private HeaderEntry knownReceived;

    /**
     * Tail of the entries, such that {@link HeaderEntry#index} is the {@code insertionIndex}.
     */
    private HeaderEntry tail;

    QpackEncoderDynamicTable() {
        this(16, 10);
    }

    QpackEncoderDynamicTable(int arraySizeHint, int expectedFreeCapacityPercentage) {
        // Enforce a bound of [2, 128] because hashMask is a byte. The max possible value of hashMask is one less
        // than the length of this array, and we want the mask to be > 0.
        fields = new HeaderEntry[findNextPositivePowerOfTwo(max(2, min(arraySizeHint, 128)))];
        hashMask = (byte) (fields.length - 1);
        // Start with index -1 so the first added header will have the index of 0.
        // See https://www.rfc-editor.org/rfc/rfc9204.html#name-absolute-indexing
        head = new HeaderEntry(-1, EMPTY_STRING, EMPTY_STRING, -1, null);
        this.expectedFreeCapacityPercentage = expectedFreeCapacityPercentage;
        resetIndicesToHead();
    }

    /**
     * Add a name - value pair to the dynamic table and returns the index.
     *
     * @param name          the name.
     * @param value         the value.
     * @param headerSize    the size of the header.
     * @return              the absolute index or {@code -1) if it could not be added.
     */
    int add(CharSequence name, CharSequence value, long headerSize) {
        if (maxTableCapacity - size < headerSize) {
            return -1;
        }

        if (tail.index == Integer.MAX_VALUE) {
            // Wait for all entries to evict before we restart indexing from zero
            evictUnreferencedEntries();
            return -1;
        }
        int h = AsciiString.hashCode(name);
        int i = index(h);
        HeaderEntry old = fields[i];
        HeaderEntry e = new HeaderEntry(h, name, value, tail.index + 1, old);
        fields[i] = e;
        e.addNextTo(tail);
        tail = e;
        size += headerSize;

        ensureFreeCapacity();
        return e.index;
    }

    /**
     * Callback when a header block which had a {@link #insertCount()}} greater than {@code 0} is
     * <a href="https://www.rfc-editor.org/rfc/rfc9204.html#name-section-acknowledgment">acknowledged</a>
     * by the decoder.
     *
     * @param entryIndex For the entry corresponding to the {@link #insertCount()}.
     * @throws QpackException If the count is invalid.
     */
    void acknowledgeInsertCountOnAck(int entryIndex) throws QpackException {
        acknowledgeInsertCount(entryIndex, true);
    }

    /**
     * Callback when a header block which had a {@link #insertCount()}} greater than {@code 0} is still not processed
     * and the stream is <a href="https://www.rfc-editor.org/rfc/rfc9204.html#name-stream-cancellation">cancelled</a>
     * by the decoder.
     *
     * @param entryIndex For the entry corresponding to the {@link #insertCount()}.
     * @throws QpackException If the count is invalid.
     */
    void acknowledgeInsertCountOnCancellation(int entryIndex) throws QpackException {
        acknowledgeInsertCount(entryIndex, false);
    }

    private void acknowledgeInsertCount(int entryIndex, boolean updateKnownReceived) throws QpackException {
        if (entryIndex < 0) {
            throw INVALID_REQUIRED_INSERT_COUNT_INCREMENT;
        }
        for (HeaderEntry e = head.next; e != null; e = e.next) {
            if (e.index == entryIndex) {
                assert e.refCount > 0;
                e.refCount--;
                if (updateKnownReceived && e.index > knownReceived.index) {
                    // https://www.rfc-editor.org/rfc/rfc9204.html#name-known-received-count
                    // If the Required Insert Count of the acknowledged field section is greater than the current Known
                    // Received Count, Known Received Count is updated to that Required Insert Count value.
                    knownReceived = e;
                }
                evictUnreferencedEntries();
                return;
            }
        }
        // We have reached the end of the linked list so the index was invalid and hence the connection should
        // be closed.
        // https://www.rfc-editor.org/rfc/rfc9204.html#section-4.4
        throw INVALID_REQUIRED_INSERT_COUNT_INCREMENT;
    }

    /**
     * Callback when a decoder <a
     * href="https://www.rfc-editor.org/rfc/rfc9204.html#name-insert-count-increment">increments its
     * insert count.</a>
     *
     * @param knownReceivedCountIncr Increment count.
     * @throws QpackException If the increment count is invalid.
     */
    void incrementKnownReceivedCount(int knownReceivedCountIncr) throws QpackException {
        if (knownReceivedCountIncr <= 0) {
            throw INVALID_KNOW_RECEIVED_COUNT_INCREMENT;
        }
        while (knownReceived.next != null && knownReceivedCountIncr > 0) {
            knownReceived = knownReceived.next;
            knownReceivedCountIncr--;
        }
        if (knownReceivedCountIncr == 0) {
            evictUnreferencedEntries();
            return;
        }
        // We have reached the end of the linked list so the index was invalid and hence the connection should be
        // closed.
        // https://www.rfc-editor.org/rfc/rfc9204.html#name-decoder-instructions
        throw INVALID_KNOW_RECEIVED_COUNT_INCREMENT;
    }

    /**
     * Returns the number of entries inserted to this dynamic table.
     *
     * @return number the added entries.
     */
    int insertCount() {
        return tail.index + 1;
    }

    /**
     * <a href="https://www.rfc-editor.org/rfc/rfc9204.html#name-required-insert-count">
     *     Encodes the required insert count.</a>
     * @param reqInsertCount    the required insert count.
     * @return                  the encoded count.
     */
    int encodedRequiredInsertCount(int reqInsertCount) {
        // https://www.rfc-editor.org/rfc/rfc9204.html#name-required-insert-count
        // if ReqInsertCount == 0:
        //      EncInsertCount = 0
        // else:
        //      EncInsertCount = (ReqInsertCount mod (2 * MaxEntries)) + 1
        //
        return reqInsertCount == 0 ? 0 : reqInsertCount % toIntExact(2 * QpackUtil.maxEntries(maxTableCapacity)) + 1;
    }

    // Visible for tests
    int encodedKnownReceivedCount() {
        // https://www.rfc-editor.org/rfc/rfc9204.html#name-known-received-count
        return encodedRequiredInsertCount(knownReceived.index + 1);
    }

    /**
     * Set the maximum capacity of the dynamic table. This can only be set once.
     * @param capacity          the capacity
     * @throws QpackException   if capacity was set before.
     */
    void maxTableCapacity(long capacity) throws QpackException {
        validateCapacity(capacity);
        if (this.maxTableCapacity >= 0) {
            throw CAPACITY_ALREADY_SET;
        }
        this.maxTableCapacity = capacity;
    }

    /**
     * Transforms the passed {@code entryIndex} as a <a
     * href="https://www.rfc-editor.org/rfc/rfc9204.html#name-relative-indexing">relative index for
     * encoder instructions</a>.
     *
     * @param entryIndex to transform.
     * @return Relative index for the passed {@code entryIndex}.
     */
    int relativeIndexForEncoderInstructions(int entryIndex) {
        assert entryIndex >= 0;
        assert entryIndex <= tail.index;
        return tail.index - entryIndex;
    }

    /**
     * Finds an entry with the passed {@code name} and {@code value} in this dynamic table.
     *
     * @param name of the entry to find.
     * @param value of the entry to find.
     * @return {@link #NOT_FOUND} if the entry does not exist. If an entry with matching {@code name} and {@code value}
     * exists, then the index is returned. If an entry with only matching name exists then {@code -index-1} is
     * returned.
     */
    int getEntryIndex(CharSequence name, CharSequence value) {
        if (tail != head && name != null && value != null) {
            int h = AsciiString.hashCode(name);
            int i = index(h);
            HeaderEntry firstNameMatch = null;
            HeaderEntry entry = null;
            for (HeaderEntry e = fields[i]; e != null; e = e.nextSibling) {
                if (e.hash == h && equalsVariableTime(value, e.value)) {
                    if (equalsVariableTime(name, e.name)) {
                        entry = e;
                        break;
                    }
                } else if (firstNameMatch == null && equalsVariableTime(name, e.name)) {
                    firstNameMatch = e;
                }
            }
            if (entry != null) {
                return entry.index;
            }
            if (firstNameMatch != null) {
                return -firstNameMatch.index - 1;
            }
        }
        return NOT_FOUND;
    }

    /**
     * Adds a reference to an entry at the passed {@code idx}.
     *
     * @param name of the entry for lookups, not verified for the entry at the pased {@code idx}
     * @param value of the entry for lookups, not verified for the entry at the pased {@code idx}
     * @param idx of the entry.
     * @return <a href="https://www.rfc-editor.org/rfc/rfc9204.html#name-required-insert-count">Required
     * insert count</a> if the passed entry has to be referenced in a header block.
     */
    int addReferenceToEntry(CharSequence name, CharSequence value, int idx) {
        if (tail != head && name != null && value != null) {
            int h = AsciiString.hashCode(name);
            int i = index(h);
            for (HeaderEntry e = fields[i]; e != null; e = e.nextSibling) {
                if (e.hash == h && idx == e.index) {
                    e.refCount++;
                    return e.index + 1;
                }
            }
        }
        throw new IllegalArgumentException("Index " + idx + " not found");
    }

    boolean requiresDuplication(int idx, long size) {
        assert head != tail;

        if (this.size + size > maxTableCapacity || head == drain) {
            return false;
        }
        return idx >= head.next.index && idx <= drain.index;
    }

    private void evictUnreferencedEntries() {
        if (head == knownReceived || head == drain) {
            return;
        }

        while (head.next != null && head.next != knownReceived.next && head.next != drain.next) {
            if (!removeIfUnreferenced()) {
                return;
            }
        }
    }

    private boolean removeIfUnreferenced() {
        final HeaderEntry toRemove = head.next;
        if (toRemove.refCount != 0) {
            return false;
        }
        size -= toRemove.size();

        // Remove from the hash map
        final int i = index(toRemove.hash);
        HeaderEntry e = fields[i];
        HeaderEntry prev = null;
        while (e != null && e != toRemove) {
            prev = e;
            e = e.nextSibling;
        }
        if (e == toRemove) {
            if (prev == null) {
                fields[i] = e.nextSibling;
            } else {
                prev.nextSibling = e.nextSibling;
            }
        }

        // Remove from the linked list
        toRemove.remove(head);
        if (toRemove == tail) {
            resetIndicesToHead();
        }
        if (toRemove == drain) {
            drain = head;
        }
        if (toRemove == knownReceived) {
            knownReceived = head;
        }
        return true;
    }

    private void resetIndicesToHead() {
        tail = head;
        drain = head;
        knownReceived = head;
    }

    private void ensureFreeCapacity() {
        long maxDesiredSize = max(ENTRY_OVERHEAD, ((100 - expectedFreeCapacityPercentage) * maxTableCapacity) / 100);
        long cSize = size;
        HeaderEntry nDrain;
        for (nDrain = head; nDrain.next != null && cSize > maxDesiredSize; nDrain = nDrain.next) {
            cSize -= nDrain.next.size();
        }
        if (cSize != size) {
            drain = nDrain;
            evictUnreferencedEntries();
        }
    }

    private int index(int h) {
        return h & hashMask;
    }

    private static void validateCapacity(long capacity) throws QpackException {
        if (capacity < MIN_HEADER_TABLE_SIZE || capacity > MAX_HEADER_TABLE_SIZE) {
            throw INVALID_TABLE_CAPACITY;
        }
    }

    /**
     * An entry for the {@link #fields} HashMap. This entry provides insertion order iteration using {@link #next}.
     */
    private static final class HeaderEntry extends QpackHeaderField {
        /**
         * Pointer to the next entry in insertion order with a different {@link #hash} than this entry.
         */
        HeaderEntry next;

        /**
         * Pointer to the next entry in insertion order with the same {@link #hash} as this entry, a.k.a hash collisions
         */
        HeaderEntry nextSibling;

        /**
         * Number of header blocks that refer to this entry as the value for its <a
         * href="https://www.rfc-editor.org/rfc/rfc9204.html#name-required-insert-count">
         * required insert count</a>
         */
        int refCount;

        /**
         * Hashcode for this entry.
         */
        final int hash;

        /**
         * Insertion index for this entry.
         */
        final int index;

        HeaderEntry(int hash, CharSequence name, CharSequence value, int index, HeaderEntry nextSibling) {
            super(name, value);
            this.index = index;
            this.hash = hash;
            this.nextSibling = nextSibling;
        }

        void remove(HeaderEntry prev) {
            assert prev != this;
            prev.next = next;
            next = null; // null references to prevent nepotism in generational GC.
            nextSibling = null;
        }

        void addNextTo(HeaderEntry prev) {
            assert prev != this;
            this.next = prev.next;
            prev.next = this;
        }
    }
}
