src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java

// 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.collect.nestedset;

import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Maps;
import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
import java.util.HashMap;

/**
 * Type of a nested set (defines order).
 *
 * <p>STABLE_ORDER: an unspecified traversal order. Use when the order of elements does not matter.
 * In Starlark it is called "default"; its older deprecated name is "stable".
 *
 * <p>COMPILE_ORDER: left-to-right postorder. In Starlark it is called "postorder"; its older
 * deprecated name is "compile".
 *
 * <p>For example, for the nested set {B, D, {A, C}}, the iteration order is "A C B D"
 * (child-first).
 *
 * <p>This type of set would typically be used for artifacts where elements of nested sets go before
 * the direct members of a set, for example in the case of Javascript dependencies.
 *
 * <p>LINK_ORDER: a variation of left-to-right preorder that enforces topological sorting. In
 * Starlark it is called "topological"; its older deprecated name is "link".
 *
 * <p>For example, for the nested set {A, C, {B, D}}, the iteration order is "A C B D"
 * (parent-first).
 *
 * <p>This type of set would typically be used for artifacts where elements of nested sets go after
 * the direct members of a set, for example when providing a list of libraries to the C++ compiler.
 *
 * <p>The custom ordering has the property that elements of nested sets always come before elements
 * of descendant nested sets. Left-to-right order is preserved if possible, both for items and for
 * references to nested sets.
 *
 * <p>The left-to-right pre-order-like ordering is implemented by running a right-to-left postorder
 * traversal and then reversing the result.
 *
 * <p>The reason naive left-to left-to-right preordering is not used here is that it does not handle
 * diamond-like structures properly. For example, take the following structure (nesting downwards):
 *
 * <pre>
 *    A
 *   / \
 *  B   C
 *   \ /
 *    D
 * </pre>
 *
 * <p>Naive preordering would produce "A B D C", which does not preserve the "parent before child"
 * property: C is a parent of D, so C should come before D. Either "A B C D" or "A C B D" would be
 * acceptable. This implementation returns the first option of the two so that left-to-right order
 * is preserved.
 *
 * <p>In case the nested sets form a tree, the ordering algorithm is equivalent to standard
 * left-to-right preorder.
 *
 * <p>Sometimes it may not be possible to preserve left-to-right order:
 *
 * <pre>
 *      A
 *    /   \
 *   B     C
 *  / \   / \
 *  \   E   /
 *   \     /
 *    \   /
 *      D
 * </pre>
 *
 * <p>The left branch (B) would indicate "D E" ordering and the right branch (C) dictates "E D". In
 * such cases ordering is decided by the rightmost branch because of the list reversing behind the
 * scenes, so the ordering in the final enumeration will be "E D".
 *
 * <p>NAIVE_LINK_ORDER: a left-to-right preordering. In Starlark it is called "preorder"; its older
 * deprecated name is "naive_link".
 *
 * <p>For example, for the nested set {B, D, {A, C}}, the iteration order is "B D A C".
 *
 * <p>The order is called naive because it does no special treatment of dependency graphs that are
 * not trees. For such graphs the property of parent-before-dependencies in the iteration order will
 * not be upheld. For example, the diamond-shape graph A->{B, C}, B->{D}, C->{D} will be enumerated
 * as "A B D C" rather than "A B C D" or "A C B D".
 *
 * <p>The difference from LINK_ORDER is that this order gives priority to left-to-right order over
 * dependencies-after-parent ordering. Note that the latter is usually more important, so please use
 * LINK_ORDER whenever possible.
 */
// TODO(bazel-team): Remove deprecated names from the documentation above.
public enum Order {
  STABLE_ORDER("default"),
  COMPILE_ORDER("postorder"),
  LINK_ORDER("topological"),
  NAIVE_LINK_ORDER("preorder");

  private static final ImmutableMap<String, Order> VALUES;
  private static final Order[] ORDINALS;

  private final String starlarkName;
  private final NestedSet<?> emptySet;
  private final Depset emptyDepset;

  Order(String starlarkName) {
    this.starlarkName = starlarkName;
    this.emptySet = new NestedSet<>(this);
    this.emptyDepset = new Depset(null, this.emptySet);
  }

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final Order STABLE_ORDER_CONSTANT = STABLE_ORDER;

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final Order COMPILE_ORDER_CONSTANT = COMPILE_ORDER;

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final Order LINK_ORDER_CONSTANT = LINK_ORDER;

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final Order NAIVE_LINK_ORDER_CONSTANT = NAIVE_LINK_ORDER;

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final NestedSet<?> EMPTY_STABLE = STABLE_ORDER.emptySet();

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final NestedSet<?> EMPTY_COMPILE = COMPILE_ORDER.emptySet();

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final NestedSet<?> EMPTY_LINK = LINK_ORDER.emptySet();

  @SerializationConstant @AutoCodec.VisibleForSerialization
  static final NestedSet<?> EMPTY_NAIVE_LINK = NAIVE_LINK_ORDER.emptySet();

  /**
   * Returns an empty set of the given ordering.
   */
  @SuppressWarnings("unchecked")  // Nested sets are immutable, so a downcast is fine.
  <E> NestedSet<E> emptySet() {
    return (NestedSet<E>) emptySet;
  }

  /** Returns an empty depset of the given ordering. */
  Depset emptyDepset() {
    return emptyDepset;
  }

  public String getStarlarkName() {
    return starlarkName;
  }

  /**
   * Parses the given string as a nested set order
   *
   * @param name unique name of the order
   * @return the appropriate order instance
   * @throws IllegalArgumentException if the name is not valid
   */
  public static Order parse(String name) {
    if (VALUES.containsKey(name)) {
      return VALUES.get(name);
    } else {
      throw new IllegalArgumentException("Invalid order: " + name);
    }
  }

  /**
   * Determines whether two orders are considered compatible.
   *
   * <p>An order is compatible with itself (reflexivity) and all orders are compatible with
   * {@link #STABLE_ORDER}; the rest of the combinations are incompatible.
   */
  public boolean isCompatible(Order other) {
    return this == other || this == STABLE_ORDER || other == STABLE_ORDER;
  }

  /**
   * Indexes all possible values by name and stores the results in a {@code ImmutableMap}
   */
  static {
    ORDINALS = values();
    HashMap<String, Order> entries = Maps.newHashMapWithExpectedSize(ORDINALS.length);

    for (Order current : ORDINALS) {
      entries.put(current.getStarlarkName(), current);
    }

    VALUES = ImmutableMap.copyOf(entries);
  }

  static Order getOrder(int ordinal) {
    return ORDINALS[ordinal];
  }
}