Switch InternalContext to store dependency/source pairs more compactly.

First, use an ArrayList instead of LinkedList, since it has only 4-8
bytes overhead per entry (depending on resize phase).  Second, remove
the overhead of the DependencyAndSource object, which saves 8 bytes per
object, and materialize only when getDependencyChain() is called.

-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=47284141
diff --git a/core/src/com/google/inject/internal/InternalContext.java b/core/src/com/google/inject/internal/InternalContext.java
index 2ff2af6..71d953c 100644
--- a/core/src/com/google/inject/internal/InternalContext.java
+++ b/core/src/com/google/inject/internal/InternalContext.java
@@ -17,12 +17,13 @@
 package com.google.inject.internal;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
 import com.google.inject.Key;
 import com.google.inject.spi.Dependency;
 import com.google.inject.spi.DependencyAndSource;
 
-import java.util.LinkedList;
+import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
 
@@ -35,10 +36,18 @@
 final class InternalContext {
 
   private Map<Object, ConstructionContext<?>> constructionContexts = Maps.newHashMap();
+
   /** Keeps track of the type that is currently being requested for injection. */
-  private Dependency dependency;
-  /** Keeps track of the hierarchy of types needed during injection. */
-  private LinkedList<DependencyAndSource> state = new LinkedList<DependencyAndSource>();
+  private Dependency<?> dependency;
+
+  /**
+   * Keeps track of the hierarchy of types needed during injection.
+   *
+   * <p>This is a pairwise combination of dependencies and sources, with dependencies on even
+   * indices, and sources on odd indices. This structure is to avoid the memory overhead of
+   * DependencyAndSource objects, which can add to several tens of megabytes in large applications.
+   */
+  private final List<Object> state = Lists.newArrayList();
 
   @SuppressWarnings("unchecked")
   public <T> ConstructionContext<T> getConstructionContext(Object key) {
@@ -51,36 +60,44 @@
     return constructionContext;
   }
 
-  public Dependency getDependency() {
+  public Dependency<?> getDependency() {
     return dependency;
   }
 
   /** Sets the new current dependency & adds it to the state. */
-  public Dependency pushDependency(Dependency dependency, Object source) {
-    Dependency previous = this.dependency;
+  public Dependency<?> pushDependency(Dependency<?> dependency, Object source) {
+    Dependency<?> previous = this.dependency;
     this.dependency = dependency;
-    state.addLast(new DependencyAndSource(dependency, source));
+    state.add(dependency);
+    state.add(source);
     return previous;
   }
   
   /** Pops the current state & sets the new dependency. */
-  public void popStateAndSetDependency(Dependency newDependency) {
+  public void popStateAndSetDependency(Dependency<?> newDependency) {
     popState();
     this.dependency = newDependency;
   }
   
   /** Adds to the state without setting the dependency. */
   public void pushState(Key<?> key, Object source) {
-    state.addLast(new DependencyAndSource(key == null ? null : Dependency.get(key), source));
+    state.add(key == null ? null : Dependency.get(key));
+    state.add(source);
   }
   
   /** Pops from the state without setting a dependency. */
   public void popState() {
-    state.removeLast();
+    state.remove(state.size() - 1);
+    state.remove(state.size() - 1);
   }
   
   /** Returns the current dependency chain (all the state). */
   public List<DependencyAndSource> getDependencyChain() {
-    return ImmutableList.copyOf(state);
+    ImmutableList.Builder<DependencyAndSource> builder = ImmutableList.builder();
+    for (int i = 0; i < state.size(); i += 2) {
+      builder.add(new DependencyAndSource(
+          (Dependency<?>) state.get(i), state.get(i + 1)));
+    }
+    return builder.build();
   }
 }