)]}'
{
  "commit": "d5353257a835631a83c25efff3b5560b5bbce7e7",
  "tree": "d210b9befa4a5e39dce9ae163ce15cad6162a6ce",
  "parents": [
    "bab0d481dea8be7568cd593460c26111bf302175"
  ],
  "author": {
    "name": "Greg Estren",
    "email": "gregce@google.com",
    "time": "Thu Aug 11 22:13:31 2016 +0000"
  },
  "committer": {
    "name": "Yue Gan",
    "email": "yueg@google.com",
    "time": "Fri Aug 12 08:53:59 2016 +0000"
  },
  "message": "Changes DependencyResolver \u003cAttribute, Dep\u003e map from a ListMultimap to new class\nOrderedSetMultimap. This maintains insertion order while eliminating duplicates.\n\nCertain rules, in particular, otherwise break this invariant:\nhttps://github.com/bazelbuild/bazel/blo[]e3e28274cca5b87f48abe33884edb84016dd3/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java#L403\n\nThere\u0027s no reason (to my knowledge) to need multiple instances of the same \u003cAttribute, Dependency\u003e pair.\n\nMore context from Google code review:\n\n(Michael Staib):\n\u003e There are many things which pass around a dependentNodeMap or help construct one or modify one. We want an interface which has the right guarantees.\n\u003e ListMultimap is not the right interface because it has no guarantee of unique elements, which we want - we don\u0027t want the problem that this CL ran into, and there\u0027s no reason (that we know of, to be confirmed) that anyone would want multiple identical Dependencies.\n\u003e SetMultimap is not the right interface because it has no guarantee of deterministic iteration order or efficient iteration, which we want - dependency order sometimes matters (e.g., Java classpath or C++ link order).\n\u003e We agreed that the best way to get what we want is to define our own interface with its own simultaneous uniqueness and iterability guarantees. Unspoken in the discussion was why we wouldn\u0027t just use LinkedHashMultimap as the thing we pass around. IMO the reason for that is that we don\u0027t care that it be a LinkedHashMultimap specifically; if tomorrow Guava comes out with a faster cooler map that has deterministic and efficient iteration and guarantees element uniqueness, we want it.\n\u003e In this case we\u0027re going to make the \"interface\" be a (final?) class: OrderedSetMultimap, an extension of ForwardingSetMultimap which delegates to LinkedHashMultimap, an implementation which does support both of those guarantees.\n\u003e I had mentioned in the conversation that none of the Multimap implementations make guarantees about key iteration order, but this is not true - LinkedHashMultimap preserves key insertion order. We should perhaps declare this as part of the OrderedSetMultimap contract as well.\n\n--\nMOS_MIGRATED_REVID\u003d130037643\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "55bcf81851fbacfb1f56b9757e9a0d06ad133fe6",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/analysis/BuildView.java",
      "new_id": "5fed4a32fa82de6c39b587f668730e5a242b1b45",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/analysis/BuildView.java"
    },
    {
      "type": "modify",
      "old_id": "ac47679ddb6462867638846dde529a69ec4b2287",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java",
      "new_id": "0ace78b5519626483e7f4af1ad900eab3961a649",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/analysis/ConfiguredTargetFactory.java"
    },
    {
      "type": "modify",
      "old_id": "395603751684d3aa47ac8a5cc9f3ee53ebc742f9",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java",
      "new_id": "6816b42e8daf54a15708a251a71f93d059df87b3",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/analysis/DependencyResolver.java"
    },
    {
      "type": "modify",
      "old_id": "d4cea81c205b24f6a9811940935925fb8ab17356",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java",
      "new_id": "321c385d0787b388fbfd108b3a90c725a260b3cf",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/analysis/RuleContext.java"
    },
    {
      "type": "modify",
      "old_id": "ff608695374c0469977e661986a315dfd505c5e5",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java",
      "new_id": "cf1afb2de61dc9c1054b5129b294dc0ac72d9305",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/analysis/TargetContext.java"
    },
    {
      "type": "modify",
      "old_id": "9de5f09b815d0180a734d1d81ccdab2805ee4256",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java",
      "new_id": "c1f8c335ec59d74aaa770fb352da002e1e92f1b7",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/skyframe/AspectFunction.java"
    },
    {
      "type": "modify",
      "old_id": "b09fc1dbe4c34d91a4a0aea3fd570c270c45899b",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java",
      "new_id": "9a82ef4d983a4ea2e46a8c99cf733b621922618b",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetFunction.java"
    },
    {
      "type": "modify",
      "old_id": "92b2678d133729e9c9eee1c91081bc1eff999496",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java",
      "new_id": "e221ae7be13125c14bae5429f2360943d71e0a58",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/skyframe/PostConfiguredTargetFunction.java"
    },
    {
      "type": "modify",
      "old_id": "556d781aa04590e58c93344407f705d3479f0c9a",
      "old_mode": 33188,
      "old_path": "src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java",
      "new_id": "546a0e257530c69c5f1d1b44ca49bd761e09751f",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/skyframe/SkyframeBuildView.java"
    },
    {
      "type": "add",
      "old_id": "0000000000000000000000000000000000000000",
      "old_mode": 0,
      "old_path": "/dev/null",
      "new_id": "a64ddf66022bd6d3c631a58cdd471f8d5d3a8960",
      "new_mode": 33188,
      "new_path": "src/main/java/com/google/devtools/build/lib/util/OrderedSetMultimap.java"
    },
    {
      "type": "modify",
      "old_id": "7f1538464de39ac4a139bb4a9ba3bcba07f487d7",
      "old_mode": 33188,
      "old_path": "src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java",
      "new_id": "be4988ecaf00c9f62ed850250ccf423f62b8473f",
      "new_mode": 33188,
      "new_path": "src/test/java/com/google/devtools/build/lib/analysis/DependencyResolverTest.java"
    }
  ]
}