// Copyright 2014 The Bazel Authors. All rights reserved.
//
// 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.google.devtools.build.lib.packages;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
import com.google.errorprone.annotations.CheckReturnValue;
import java.util.BitSet;
import java.util.List;
import javax.annotation.Nullable;

/**
 * AttributeContainer holds all attribute values of a rule. In addition, for each one, it records
 * whether it is 'explicit', that is, provided by the function call that instantiated the rule, as
 * opposed to the default value, or a value computed from other attributes.
 *
 * <p>This class provides the lowest-level access to attribute information. The public interface for
 * attribute access is the rule itself. For a higher level abstraction use {@link AttributeMap}
 * instead.
 */
abstract class AttributeContainer {

  /**
   * Returns true iff the value of the specified attribute is explicitly set in the BUILD file. In
   * addition, this method returns false if the rule has no attribute with the given index.
   */
  abstract boolean isAttributeValueExplicitlySpecified(int attrIndex);

  /**
   * Returns the value of the attribute with index attrIndex. Returns null if the attribute is not
   * set in the container.
   */
  @Nullable
  abstract Object getAttributeValue(int attrIndex);

  /**
   * Returns attribute values as tracked by this instance. The indices of attribute values in the
   * returned list are not guaranteed to be consistent with the other methods of this class. If this
   * is important, which is generally the case, avoid this method.
   */
  abstract List<Object> getRawAttributeValues();

  /**
   * Updates the value of the attribute.
   *
   * @param attrIndex the index of attribute whose value to update. Assumed to be valid index.
   * @param value the value to set
   * @param explicit was this explicitly set in the BUILD file.
   */
  abstract void setAttributeValue(int attrIndex, Object value, boolean explicit);

  /** Returns a frozen AttributeContainer with the same attributes, and a compact representation. */
  @CheckReturnValue
  abstract AttributeContainer freeze(Rule rule);

  /**
   * Returns {@code true} if this container is immutable.
   *
   * <p>Frozen containers optimize for space by omitting storage for non-explicit attribute values
   * that match the {@link Attribute} default. If {@link #getAttributeValue} returns {@code null},
   * the value should be taken from {@link Attribute#getDefaultValue}, even for computed defaults.
   *
   * <p>Mutable containers have no such optimization. During rule creation, this allows for
   * distinguishing whether a computed default (which may depend on other unset attributes) is
   * available.
   */
  abstract boolean isFrozen();

  /** Returns an AttributeContainer for holding attributes of the given rule class. */
  static AttributeContainer newMutableInstance(RuleClass ruleClass) {
    int attrCount = ruleClass.getAttributeCount();
    Preconditions.checkArgument(attrCount < 254);
    return new Mutable(attrCount);
  }

  /** An AttributeContainer to which attributes may be added. */
  private static final class Mutable extends AttributeContainer {

    // Sparsely populated array of values, indexed by Attribute.index.
    final Object[] values;
    final BitSet explicitIndices = new BitSet();

    Mutable(int maxAttrCount) {
      values = new Object[maxAttrCount];
    }

    @Override
    public boolean isAttributeValueExplicitlySpecified(int attrIndex) {
      return (attrIndex >= 0) && explicitIndices.get(attrIndex);
    }

    /**
     * Returns the value of the attribute with index attrIndex. Returns null if the attribute is not
     * yet been set.
     */
    @Override
    @Nullable
    Object getAttributeValue(int attrIndex) {
      return values[attrIndex];
    }

    /**
     * Updates the value of the attribute.
     *
     * @param attrIndex the index of the attribute whose value to update.
     * @param value the value to set
     * @param explicit was this explicitly set in the BUILD file.
     */
    @Override
    void setAttributeValue(int attrIndex, Object value, boolean explicit) {
      if (attrIndex < 0 || attrIndex >= values.length) {
        throw new IllegalArgumentException(
            "attribute with index " + attrIndex + " is not valid for rule");
      }
      if (!explicit && explicitIndices.get(attrIndex)) {
        throw new IllegalArgumentException(
            "attribute with index " + attrIndex + " already explicitly set");
      }
      values[attrIndex] = value;
      if (explicit) {
        explicitIndices.set(attrIndex);
      }
    }

    @Override
    public AttributeContainer freeze(Rule rule) {
      BitSet indicesToStore = new BitSet();
      RuleClass ruleClass = rule.getRuleClassObject();

      for (int i = 0; i < values.length; i++) {
        Object value = values[i];
        if (value == null) {
          continue;
        }
        if (!explicitIndices.get(i)) {
          Attribute attr = ruleClass.getAttribute(i);
          Object defaultValue = attr.getDefaultValue(attr.hasComputedDefault() ? rule : null);
          if (value.equals(defaultValue)) {
            // Non-explicit value matches the attribute's default. Save space by omitting storage.
            continue;
          }
        }
        indicesToStore.set(i);
      }

      return values.length < 126
          ? new Small(values, explicitIndices, indicesToStore)
          : new Large(values, explicitIndices, indicesToStore);
    }

    @Override
    public boolean isFrozen() {
      return false;
    }

    @Override
    List<Object> getRawAttributeValues() {
      // Mutable copy since ImmutableList doesn't support null.
      return Lists.newArrayList(values);
    }
  }

  /** Frozen AttributeContainer based on compact array with indirect indexing. */
  private abstract static class Frozen extends AttributeContainer {

    @Override
    final void setAttributeValue(int attrIndex, Object value, boolean explicit) {
      throw new UnsupportedOperationException(
          "Readonly implementations do not support setAttributeValue");
    }

    @Override
    final AttributeContainer freeze(Rule rule) {
      return this;
    }

    @Override
    final boolean isFrozen() {
      return true;
    }
  }

  /** Returns index into state array for attrIndex, or -1 if not found */
  private static int getStateIndex(byte[] state, int start, int attrIndex, int mask) {
    // Binary search, treating values as unsigned bytes.
    int lo = start;
    int hi = state.length - 1;
    while (hi >= lo) {
      int mid = (lo + hi) / 2;
      int midAttrIndex = state[mid] & mask;
      if (midAttrIndex == attrIndex) {
        return mid;
      } else if (midAttrIndex < attrIndex) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return -1;
  }

  /**
   * A frozen implementation of AttributeContainer which supports RuleClasses with up to 126
   * attributes.
   */
  @VisibleForTesting
  static final class Small extends Frozen {

    private final int maxAttrCount;

    // Conceptually an AttributeContainer is an unordered set of triples
    // (attribute, value, explicit).
    // - attribute is represented internally as its index attrIndex.
    //   cheaply convertible to name and Attribute classes via RuleClass.
    // - value is an opaque object, stored in the values array
    // - explicit is a boolean which tracks if the attribute was
    //   explicitly set in the BUILD file.

    // Attribute values stored in attrIndex order.
    private final Object[] values;

    // The 'value' and 'explicit' components are encoded in the same byte.
    // Since this class only supports ruleClass with < 126 attributes,
    // state[i] encodes the 'value' index in the 7 lower bits and 'explicit' in the top bit.
    // This is the common case.
    private final byte[] state;

    // Useful Terminology for reading the code.
    //  - attrIndex: an integer associated with a legal attribute of the ruleClass.
    //    RuleClass owns the mapping between attribute, its name, and attributeIndex.
    //  - stateIndex: an index into the state[] array.
    //  - valueIndex: an index into the attributeValues array.

    /**
     * Creates a container for a rule of the given rule class. Assumes attrIndex < 126 always.
     *
     * @param attrValues values for all attributes, null values are considered unset
     * @param explicitIndices holds explicit bit for each attribute index
     * @param indicesToStore attribute indices for values that need to be stored, i.e., they were
     *     explicitly set and/or differ from the attribute's default value
     */
    private Small(Object[] attrValues, BitSet explicitIndices, BitSet indicesToStore) {
      this.maxAttrCount = attrValues.length;
      int numToStore = indicesToStore.cardinality();
      this.values = new Object[numToStore];
      this.state = new byte[numToStore];

      int attrIndex = 0;
      for (int i = 0; i < numToStore; i++) {
        attrIndex = indicesToStore.nextSetBit(attrIndex);
        byte stateValue = (byte) (0x7f & attrIndex);
        if (explicitIndices.get(attrIndex)) {
          stateValue = (byte) (stateValue | 0x80);
        }
        state[i] = stateValue;
        values[i] = attrValues[attrIndex];
        attrIndex++;
      }
    }

    /**
     * Returns true iff the value of the specified attribute is explicitly set in the BUILD file. In
     * addition, this method return false if the rule has no attribute with the given name.
     */
    @Override
    boolean isAttributeValueExplicitlySpecified(int attrIndex) {
      if (attrIndex < 0) {
        return false;
      }
      int stateIndex = getStateIndex(state, 0, attrIndex, 0x7f);
      return stateIndex >= 0 && (state[stateIndex] & 0x80) != 0;
    }

    @Nullable
    @Override
    Object getAttributeValue(int attrIndex) {
      Preconditions.checkArgument(attrIndex >= 0);
      if (attrIndex >= maxAttrCount) {
        throw new IndexOutOfBoundsException(
            "Maximum valid attrIndex is " + (maxAttrCount - 1) + ". Given " + attrIndex);
      }
      int stateIndex = getStateIndex(state, 0, attrIndex, 0x7f);
      return stateIndex < 0 ? null : values[stateIndex];
    }

    @Override
    List<Object> getRawAttributeValues() {
      // Mutable copy since ImmutableList doesn't support null.
      return Lists.newArrayList(values);
    }
  }

  /**
   * A frozen implementation of AttributeContainer which supports RuleClasses with up to 254
   * attributes.
   */
  @VisibleForTesting
  static final class Large extends Frozen {

    private final int maxAttrCount;

    // Conceptually an AttributeContainer is an unordered set of triples
    // (attribute, value, explicit).
    // - attribute is represented internally as its index attrIndex.
    //   cheaply convertible to name and Attribute classes via RuleClass.
    // - value is an opaque object, stored in the values array
    // - explicit is a boolean which tracks if the attribute was
    //   explicitly set in the BUILD file.

    // Attribute values stored in attrIndex order.
    private final Object[] values;

    // P = ceil(ruleClass.attributeCount()/8)
    // The first P bytes store the explicit bits, while the remaining bytes store attrIndex.
    //
    // NOTE: We could potentially shave off a few bytes by using P=ceil(values.length/8)
    // But
    // - it leads to higher CPU cost
    // - actual memory savings may not be much since memory is allocated in blocks of 8 bytes and
    //   the savings is at most 8 bytes.
    // - this implementation is used only if ruleClass supports > 126 attributes (very rare).
    private final byte[] state;

    // Useful Terminology for reading the code.
    //  - attrIndex: an integer associated with a legal attribute of the ruleClass.
    //    RuleClass owns the mapping between attribute, its name, and attributeIndex.
    //  - stateIndex: an index into the state[] array.
    //  - valueIndex: an index into the attributeValues array.

    /** Calculates the number of bytes necessary to have an explicit bit for each attribute. */
    private static int prefixSize(int attrCount) {
      // ceil(max attributes / 8)
      return (attrCount + 7) / 8;
    }

    /**
     * Sets the explicit bit for {@code attrIndex} in the byte array. Assumes {@code attrIndex} is a
     * valid index.
     */
    private static void setExplicitBit(byte[] bytes, int attrIndex) {
      int byteIndex = attrIndex / 8;
      int bitIndex = attrIndex % 8;
      byte byteValue = bytes[byteIndex];
      bytes[byteIndex] = (byte) (byteValue | (1 << bitIndex));
    }

    /**
     * Gets the explicit bit for {@code attrIndex} in the byte array. Assumes {@code attrIndex} is a
     * valid index.
     */
    private static boolean getExplicitBit(byte[] bytes, int attrIndex) {
      int byteIndex = attrIndex / 8;
      int bitIndex = attrIndex % 8;
      byte byteValue = bytes[byteIndex];
      return (byteValue & (1 << bitIndex)) != 0;
    }

    /**
     * Creates a container for a rule of the given rule class. Assumes maxAttrCount < 254
     *
     * @param attrValues values for all attributes, null values are considered unset.
     * @param explicitIndices holds explicit bit for each attribute index
     * @param indicesToStore attribute indices for values that need to be stored, i.e. they were
     *     explicitly set and/or differ from the attribute's default value
     */
    private Large(Object[] attrValues, BitSet explicitIndices, BitSet indicesToStore) {
      this.maxAttrCount = attrValues.length;
      int numToStore = indicesToStore.cardinality();
      int p = prefixSize(maxAttrCount);
      this.values = new Object[numToStore];
      this.state = new byte[p + numToStore];

      int attrIndex = 0;
      for (int i = 0; i < numToStore; i++) {
        attrIndex = indicesToStore.nextSetBit(attrIndex);
        if (explicitIndices.get(attrIndex)) {
          setExplicitBit(state, attrIndex);
        }
        state[i + p] = (byte) attrIndex;
        values[i] = attrValues[attrIndex];
        attrIndex++;
      }
    }

    /**
     * Returns true iff the value of the specified attribute is explicitly set in the BUILD file. In
     * addition, this method return false if the rule has no attribute with the given name.
     */
    @Override
    boolean isAttributeValueExplicitlySpecified(int attrIndex) {
      return (attrIndex >= 0) && getExplicitBit(state, attrIndex);
    }

    @Nullable
    @Override
    Object getAttributeValue(int attrIndex) {
      Preconditions.checkArgument(attrIndex >= 0);
      if (state.length == 0) {
        return null;
      }
      if (attrIndex >= maxAttrCount) {
        throw new IndexOutOfBoundsException(
            "Maximum valid attrIndex is " + (maxAttrCount - 1) + ". Given " + attrIndex);
      }
      int p = prefixSize(maxAttrCount);
      int stateIndex = getStateIndex(state, p, attrIndex, 0xff);
      return stateIndex < 0 ? null : values[stateIndex - p];
    }

    @Override
    List<Object> getRawAttributeValues() {
      // Mutable copy since ImmutableList doesn't support null.
      return Lists.newArrayList(values);
    }
  }
}