/*
 * 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
 *
 *   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 org.apache.bcel.verifier.statics;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

import org.apache.bcel.generic.Type;
import org.apache.bcel.verifier.exc.LocalVariableInfoInconsistentException;

/**
 * A utility class holding the information about the name and the type of a local variable in a given slot (== index).
 * This information often changes in course of byte code offsets.
 */
public class LocalVariableInfo {

    /**
     * A contiguous, inclusive range of bytecode offsets sharing one variable name and one type.
     */
    private static final class Range {
        private final int start;
        private final int end; // inclusive
        private final String name;
        private final Type type;

        Range(final int start, final int end, final String name, final Type type) {
            this.start = start;
            this.end = end;
            this.name = name;
            this.type = type;
        }
    }

    /**
     * The database of ranges, keyed by their start offset. Invariant: the stored ranges never overlap each other; additions overlapping an existing range
     * with consistent information are coalesced into it, inconsistent ones are rejected. Storing ranges instead of one entry per offset keeps the work and
     * memory proportional to the number of LocalVariableTable entries: the startPc and length fields are attacker-controlled in a malicious class file and
     * would otherwise amplify each 10-byte table entry into up to 65,536 hashtable operations (CWE-407).
     */
    private final NavigableMap<Integer, Range> ranges = new TreeMap<>();

    /**
     * Constructs a new LocalVariableInfo.
     */
    public LocalVariableInfo() {
    }

    /**
     * Adds some information about this local variable (slot).
     *
     * @param name variable name.
     * @param startPc Range in which the variable is valid.
     * @param length length of ...
     * @param type variable type.
     * @throws LocalVariableInfoInconsistentException Thrown if the new information conflicts with already gathered information.
     */
    public void add(final String name, final int startPc, final int length, final Type type) throws LocalVariableInfoInconsistentException {
        final int endPc = startPc + length; // incl/incl-notation!
        int mergedStart = startPc;
        int mergedEnd = endPc;
        // Only ranges starting at or before endPc can overlap [startPc, endPc]; since stored ranges never overlap each other, the first candidate is the
        // last range starting at or before startPc.
        Integer from = ranges.floorKey(startPc);
        if (from == null) {
            from = Integer.valueOf(startPc);
        }
        final List<Integer> merged = new ArrayList<>();
        for (final Map.Entry<Integer, Range> entry : ranges.subMap(from, true, Integer.valueOf(endPc), true).entrySet()) {
            final Range range = entry.getValue();
            if (range.end < startPc) {
                continue; // does not overlap.
            }
            final int offset = Math.max(startPc, range.start);
            if (!range.name.equals(name)) {
                throw new LocalVariableInfoInconsistentException(
                    "At bytecode offset '" + offset + "' a local variable has two different names: '" + range.name + "' and '" + name + "'.");
            }
            if (!range.type.equals(type)) {
                throw new LocalVariableInfoInconsistentException(
                    "At bytecode offset '" + offset + "' a local variable has two different types: '" + range.type + "' and '" + type + "'.");
            }
            // Consistent overlap: coalesce, so the database stays proportional to the number of disjoint ranges.
            mergedStart = Math.min(mergedStart, range.start);
            mergedEnd = Math.max(mergedEnd, range.end);
            merged.add(entry.getKey());
        }
        merged.forEach(ranges::remove);
        ranges.put(Integer.valueOf(mergedStart), new Range(mergedStart, mergedEnd, name, type));
    }

    /**
     * Returns the name of the local variable that uses this local variable slot at the given bytecode offset. Care for
     * legal bytecode offsets yourself, otherwise the return value might be wrong. May return 'null' if nothing is known
     * about the type of this local variable slot at the given bytecode offset.
     *
     * @param offset bytecode offset.
     * @return The name of the local variable that uses this local variable slot at the given bytecode offset.
     */
    public String getName(final int offset) {
        final Range range = lookup(offset);
        return range != null ? range.name : null;
    }

    /**
     * Returns the type of the local variable that uses this local variable slot at the given bytecode offset. Care for
     * legal bytecode offsets yourself, otherwise the return value might be wrong. May return 'null' if nothing is known
     * about the type of this local variable slot at the given bytecode offset.
     *
     * @param offset bytecode offset.
     * @return The type of the local variable that uses this local variable slot at the given bytecode offset.
     */
    public Type getType(final int offset) {
        final Range range = lookup(offset);
        return range != null ? range.type : null;
    }

    /**
     * Returns the range covering the given bytecode offset, or {@code null} if no range covers it. Since the stored ranges never overlap, only the range
     * with the greatest start offset at or below the given offset can cover it.
     */
    private Range lookup(final int offset) {
        final Map.Entry<Integer, Range> entry = ranges.floorEntry(Integer.valueOf(offset));
        return entry != null && entry.getValue().end >= offset ? entry.getValue() : null;
    }
}