Restore comments documenting the NestedSet orderings (accidentally

removed along with the per-order expander classes).

--
MOS_MIGRATED_REVID=125215096

1 files changed, 82 insertions, 2 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
index 175ea3ec82..3b207c7f13 100644
--- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
+++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java
@@ -19,8 +19,88 @@ import com.google.common.collect.Maps;
 import java.util.HashMap;
 
 /**
- * Type of a nested set (defines order). For explanation what these ordering mean,
- * see CompileOrderExpander, LinkOrderExpander, NaiveLinkOrderExpander.
+ * Type of a nested set (defines order).
+ *
+ *
+ * <p>STABLE_ORDER: an unspecified traversal order.  Use when the order of elements does not matter.
+ *
+ *
+ * <p>COMPILE_ORDER: left-to-right postorder.
+ *
+ * <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.
+ *
+ * <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.
+ *
+ * <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.
  */
 public enum Order {
   STABLE_ORDER("stable"),