Partially fixes issue #1765.
We've seen some threads about excessive memory consumption in IE when using
ImageBundles due to the fact that the directx alpha filter creates a 32 bit
/ pixel copy of the full bundle each place it is used. This change adds
Next-Fit Decreasing Height Decreasing Width image packing (or something
close to it) to decrease the amount of space we're wasting in the bundles.

Review by: rdayal



git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@2187 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/user/src/com/google/gwt/user/rebind/ui/ImageBundleBuilder.java b/user/src/com/google/gwt/user/rebind/ui/ImageBundleBuilder.java
index dd9e1d2..d57a42b 100644
--- a/user/src/com/google/gwt/user/rebind/ui/ImageBundleBuilder.java
+++ b/user/src/com/google/gwt/user/rebind/ui/ImageBundleBuilder.java
@@ -1,5 +1,5 @@
 /*
- * Copyright 2007 Google Inc.
+ * Copyright 2008 Google Inc.
  * 
  * 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
@@ -20,17 +20,19 @@
 import com.google.gwt.core.ext.UnableToCompleteException;
 import com.google.gwt.dev.util.Util;
 
-import java.awt.image.BufferedImage;
 import java.awt.Graphics2D;
+import java.awt.image.BufferedImage;
+import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.OutputStream;
-import java.io.ByteArrayOutputStream;
 import java.net.URL;
-import java.util.HashMap;
-import java.util.Map;
+import java.util.ArrayList;
 import java.util.Collection;
-import java.util.SortedMap;
-import java.util.TreeMap;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
 
 import javax.imageio.ImageIO;
 
@@ -38,31 +40,241 @@
  * Accumulates state for the bundled image.
  */
 class ImageBundleBuilder {
-
   /**
    * The rectangle at which the original image is placed into the composite
    * image.
    */
-  public static class ImageRect {
+  public static class ImageRect implements HasRect {
 
-    public final int height;
-    public final BufferedImage image;
-    public int left;
-    public final int width;
+    private final String name;
+    private final int height, width;
+    private final BufferedImage image;
+    private int left, top;
 
-    public ImageRect(BufferedImage image) {
+    private boolean hasBeenPositioned;
+
+    public ImageRect(String name, BufferedImage image) {
+      this.name = name;
       this.image = image;
       this.width = image.getWidth();
       this.height = image.getHeight();
     }
+
+    public int getHeight() {
+      return height;
+    }
+
+    public int getLeft() {
+      return left;
+    }
+
+    public String getName() {
+      return name;
+    }
+
+    public int getTop() {
+      return top;
+    }
+
+    public int getWidth() {
+      return width;
+    }
+
+    public boolean hasBeenPositioned() {
+      return hasBeenPositioned;
+    }
+
+    public void setPosition(int left, int top) {
+      hasBeenPositioned = true;
+      this.left = left;
+      this.top = top;
+    }
   }
 
+  /**
+   * A mockable interface to test the image arrangement algorithms.
+   */
+  interface HasRect {
+
+    String getName();
+
+    int getHeight();
+
+    int getLeft();
+
+    int getTop();
+
+    int getWidth();
+
+    boolean hasBeenPositioned();
+
+    void setPosition(int left, int top);
+  }
+
+  /**
+   * Used to return the size of the resulting image from the method
+   * {@link ImageBundleBuilder#arrangeImages()}.
+   */
+  private static class Size {
+    private final int width, height;
+
+    Size(int width, int height) {
+      this.width = width;
+      this.height = height;
+    }
+  }
+
+  private static final Comparator<HasRect> decreasingHeightComparator = new Comparator<HasRect>() {
+    public int compare(HasRect a, HasRect b) {
+      final int c = b.getHeight() - a.getHeight();
+      // If we encounter equal heights, use the name to keep things
+      // deterministic.
+      return (c != 0) ? c : b.getName().compareTo(a.getName());
+    }
+  };
+
+  private static final Comparator<HasRect> decreasingWidthComparator = new Comparator<HasRect>() {
+    public int compare(HasRect a, HasRect b) {
+      final int c = b.getWidth() - a.getWidth();
+      // If we encounter equal heights, use the name to keep things
+      // deterministic.
+      return (c != 0) ? c : b.getName().compareTo(a.getName());
+    }
+  };
+
   /*
    * Only PNG is supported right now. In the future, we may be able to infer the
    * best output type, and get rid of this constant.
    */
   private static final String BUNDLE_FILE_TYPE = "png";
 
+  /**
+   * Arranges the images to try to decrease the overall area of the resulting
+   * bundle. This uses a strategy that is basically Next-Fit Decreasing Height
+   * Decreasing Width (NFDHDW). The rectangles to be packed are sorted in
+   * decreasing order by height. The tallest rectangle is placed at the far
+   * left. We attempt to stack the remaining rectangles on top of one another to
+   * construct as many columns as necessary. After finishing each column, we
+   * also attempt to do some horizontal packing to fill up the space left due to
+   * widths of rectangles differing in the column.
+   */
+  static Size arrangeImages(Collection<? extends HasRect> rects) {
+    if (rects.size() == 0) {
+      return new Size(0, 0);
+    }
+
+    // Create a list of ImageRects ordered by decreasing height used for
+    // constructing columns.
+    final ArrayList<HasRect> rectsOrderedByHeight = new ArrayList<HasRect>(
+        rects);
+    Collections.sort(rectsOrderedByHeight, decreasingHeightComparator);
+
+    // Create a list of ImageRects ordered by decreasing width used for packing
+    // individual columns.
+    final ArrayList<HasRect> rectsOrderedByWidth = new ArrayList<HasRect>(rects);
+    Collections.sort(rectsOrderedByWidth, decreasingWidthComparator);
+
+    // Place the first, tallest image as the first column.
+    final HasRect first = rectsOrderedByHeight.get(0);
+    first.setPosition(0, 0);
+
+    // Setup state for laying things cumulatively.
+    int curX = first.getWidth();
+    final int colH = first.getHeight();
+
+    for (int i = 1, n = rectsOrderedByHeight.size(); i < n; i++) {
+      // If this ImageRect has been positioned already, move on.
+      if (rectsOrderedByHeight.get(i).hasBeenPositioned()) {
+        continue;
+      }
+
+      int colW = 0;
+      int curY = 0;
+
+      final ArrayList<HasRect> rectsInColumn = new ArrayList<HasRect>();
+      for (int j = i; j < n; j++) {
+        final HasRect current = rectsOrderedByHeight.get(j);
+        // Look for rects that have not been positioned with a small enough
+        // height to go in this column.
+        if (!current.hasBeenPositioned()
+            && (curY + current.getHeight()) <= colH) {
+
+          // Set the horizontal position here, the top field will be set in
+          // arrangeColumn after we've collected a full set of ImageRects.
+          current.setPosition(curX, 0);
+          colW = Math.max(colW, current.getWidth());
+          curY += current.getHeight();
+
+          // Keep the ImageRects in this column in decreasing order by width.
+          final int pos = Collections.binarySearch(rectsInColumn, current,
+              decreasingWidthComparator);
+          assert pos < 0;
+          rectsInColumn.add(-1 - pos, current);
+        }
+      }
+
+      // Having selected a set of ImageRects that fill out this column vertical,
+      // now we'll scan the remaining ImageRects to try to fit some in the
+      // horizontal gaps.
+      if (!rectsInColumn.isEmpty()) {
+        arrangeColumn(rectsInColumn, rectsOrderedByWidth);
+      }
+
+      // We're done with that column, so move the horizontal accumulator by the
+      // width of the column we just finished.
+      curX += colW;
+    }
+
+    return new Size(curX, colH);
+  }
+
+  /**
+   * Companion method to {@link #arrangeImages()}. This method does a best
+   * effort horizontal packing of a column after it was packed vertically. This
+   * is the Decreasing Width part of Next-Fit Decreasing Height Decreasing
+   * Width. The basic strategy is to sort the remaining rectangles by decreasing
+   * width and try to fit them to the left of each of the rectangles we've
+   * already picked for this column.
+   * 
+   * @param rectsInColumn the ImageRects that were already selected for this
+   *          column
+   * @param remainingRectsOrderedByWidth the sub list of ImageRects that may not
+   *          have been positioned yet
+   */
+  private static void arrangeColumn(List<HasRect> rectsInColumn,
+      List<HasRect> remainingRectsOrderedByWidth) {
+    final HasRect first = rectsInColumn.get(0);
+
+    final int columnWidth = first.getWidth();
+    int curY = first.getHeight();
+
+    // Skip this first ImageRect because it is guaranteed to consume the full
+    // width of the column.
+    for (int i = 1, m = rectsInColumn.size(); i < m; i++) {
+      final HasRect r = rectsInColumn.get(i);
+      // The ImageRect was previously positioned horizontally, now set the top
+      // field.
+      r.setPosition(r.getLeft(), curY);
+      int curX = r.getWidth();
+
+      // Search for ImageRects that are shorter than the left most ImageRect and
+      // narrow enough to fit in the column.
+      for (int j = 0, n = remainingRectsOrderedByWidth.size(); j < n; j++) {
+        final HasRect current = remainingRectsOrderedByWidth.get(j);
+        if (!current.hasBeenPositioned()
+            && (curX + current.getWidth()) <= columnWidth
+            && (current.getHeight() <= r.getHeight())) {
+          current.setPosition(r.getLeft() + curX, r.getTop());
+          curX += current.getWidth();
+        }
+      }
+
+      // Update the vertical accumulator so we'll know where to place the next
+      // ImageRect.
+      curY += r.getHeight();
+    }
+  }
+
   private final Map<String, ImageRect> imageNameToImageRectMap = new HashMap<String, ImageRect>();
 
   /**
@@ -202,7 +414,7 @@
         throw new UnableToCompleteException();
       }
 
-      return new ImageRect(image);
+      return new ImageRect(imageName, image);
 
     } catch (IOException e) {
       logger.log(TreeLogger.ERROR, "Unable to read image resource", null);
@@ -210,61 +422,41 @@
     }
   }
 
-  /*
+  /**
    * This method creates the bundled image through the composition of the other
    * images.
    * 
-   * This method could be implemented in a variety of ways. For example, one
-   * could use a knapsack algorithm to draw these images in an optimal amount of
-   * space.
-   * 
-   * In this particular implementation, we iterate through the image rectangles
-   * in ascending order of associated filename, and draw the rectangles from
-   * left to right in a single row.
+   * In this particular implementation, we use NFDHDW (see
+   * {@link #arrangeImages()}) to get an approximate optimal image packing.
    * 
    * The most important aspect of drawing the bundled image is that it be drawn
    * in a deterministic way. The drawing of the image should not rely on
    * implementation details of the Generator system which may be subject to
-   * change. For example, at the time of this writing, the image names are added
-   * to imageNameToImageRectMap based on the alphabetical ordering of their
-   * associated methods. This behavior is the result of the oracle returning the
-   * list of a type's methods in alphabetical order. However, this behavior is
-   * undocumented, and should not be relied on. If this behavior were to change,
-   * it would inadvertently affect the generation of bundled images.
+   * change.
    */
   private BufferedImage drawBundledImage() {
 
-    // Impose an ordering on the image rectangles, so that we construct
-    // the bundled image in a deterministic way.
-    SortedMap<String, ImageRect> sortedImageNameToImageRectMap = new TreeMap<String, ImageRect>();
-    sortedImageNameToImageRectMap.putAll(imageNameToImageRectMap);
-    Collection<ImageRect> orderedImageRects = sortedImageNameToImageRectMap.values();
+    // There is no need to impose any order here, because arrangeImages
+    // will position the ImageRects in a deterministic fashion, even though
+    // we might paint them in a non-deterministic order.
+    Collection<ImageRect> imageRects = imageNameToImageRectMap.values();
 
-    // Determine how big the composited image should be by taking the
-    // sum of the widths and the max of the heights.
-    int nextLeft = 0;
-    int maxHeight = 0;
-    for (ImageRect imageRect : orderedImageRects) {
-      imageRect.left = nextLeft;
-      nextLeft += imageRect.width;
-      if (imageRect.height > maxHeight) {
-        maxHeight = imageRect.height;
-      }
-    }
+    // Arrange images and determine the size of the resulting bundle.
+    final Size size = arrangeImages(imageRects);
 
     // Create the bundled image.
-    BufferedImage bundledImage = new BufferedImage(nextLeft, maxHeight,
+    BufferedImage bundledImage = new BufferedImage(size.width, size.height,
         BufferedImage.TYPE_INT_ARGB_PRE);
     Graphics2D g2d = bundledImage.createGraphics();
 
-    for (ImageRect imageRect : orderedImageRects) {
+    for (ImageRect imageRect : imageRects) {
 
       // We do not need to pass in an ImageObserver, because we are working
       // with BufferedImages. ImageObservers only need to be used when
       // the image to be drawn is being loaded asynchronously. See
       // http://java.sun.com/docs/books/tutorial/2d/images/drawimage.html
       // for more information.
-      g2d.drawImage(imageRect.image, imageRect.left, 0, null);
+      g2d.drawImage(imageRect.image, imageRect.left, imageRect.top, null);
     }
     g2d.dispose();
 
diff --git a/user/src/com/google/gwt/user/rebind/ui/ImageBundleGenerator.java b/user/src/com/google/gwt/user/rebind/ui/ImageBundleGenerator.java
index 5627daf..ea35ff8 100644
--- a/user/src/com/google/gwt/user/rebind/ui/ImageBundleGenerator.java
+++ b/user/src/com/google/gwt/user/rebind/ui/ImageBundleGenerator.java
@@ -218,11 +218,13 @@
       sw.print("private static final ClippedImagePrototype ");
       sw.print(singletonName);
       sw.print(" = new ClippedImagePrototype(IMAGE_BUNDLE_URL, ");
-      sw.print(Integer.toString(imageRect.left));
-      sw.print(", 0, ");
-      sw.print(Integer.toString(imageRect.width));
+      sw.print(Integer.toString(imageRect.getLeft()));
       sw.print(", ");
-      sw.print(Integer.toString(imageRect.height));
+      sw.print(Integer.toString(imageRect.getTop()));
+      sw.print(", ");
+      sw.print(Integer.toString(imageRect.getWidth()));
+      sw.print(", ");
+      sw.print(Integer.toString(imageRect.getHeight()));
       sw.println(");");
 
       sw.print(decl);
diff --git a/user/test/com/google/gwt/user/rebind/ui/ImageBundleGeneratorTest.java b/user/test/com/google/gwt/user/rebind/ui/ImageBundleGeneratorTest.java
index 6fd10ef..e36b869 100644
--- a/user/test/com/google/gwt/user/rebind/ui/ImageBundleGeneratorTest.java
+++ b/user/test/com/google/gwt/user/rebind/ui/ImageBundleGeneratorTest.java
@@ -18,13 +18,19 @@
 import com.google.gwt.core.ext.UnableToCompleteException;
 import com.google.gwt.dev.util.UnitTestTreeLogger;
 import com.google.gwt.user.client.ui.ImageBundle.Resource;
+import com.google.gwt.user.rebind.ui.ImageBundleBuilder.HasRect;
 import com.google.gwt.user.rebind.ui.ImageBundleGenerator.JMethodOracle;
 
 import junit.framework.TestCase;
 
 import java.net.URL;
+import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 
 /**
  * Unit tests for {@link ImageBundleGenerator}. Note that, at present, only a
@@ -34,6 +40,146 @@
  */
 public class ImageBundleGeneratorTest extends TestCase {
 
+  private static class MockRect implements HasRect {
+    private final String name;
+    private final int width, height;
+    private int left, top;
+    private boolean hasBeenPositioned;
+
+    MockRect(String name, int width, int height) {
+      this.name = name;
+      this.width = width;
+      this.height = height;
+    }
+
+    public int getHeight() {
+      return height;
+    }
+
+    public int getLeft() {
+      return left;
+    }
+
+    public String getName() {
+      return name;
+    }
+
+    public int getTop() {
+      return top;
+    }
+
+    public int getWidth() {
+      return width;
+    }
+
+    public boolean hasBeenPositioned() {
+      return hasBeenPositioned;
+    }
+
+    public void setPosition(int left, int top) {
+      this.left = left;
+      this.top = top;
+      hasBeenPositioned = true;
+    }
+
+    @Override
+    public String toString() {
+      return "{" + left + ", " + top + ", " + width + ", " + height + "}";
+    }
+
+    void assertPosition(int left, int top) {
+      assertTrue(hasBeenPositioned);
+      assertEquals(left, this.left);
+      assertEquals(top, this.top);
+    }
+
+    MockRect duplicate() {
+      final MockRect mr = new MockRect(name, width, height);
+      mr.hasBeenPositioned = hasBeenPositioned;
+      mr.left = left;
+      mr.top = top;
+      return mr;
+    }
+  }
+
+  /**
+   * Ensures that two collections of MockRects are arranged identically.
+   * 
+   * @param a first collection
+   * @param b second collection
+   */
+  private static void assertSameArrangement(Collection<MockRect> a,
+      Collection<MockRect> b) {
+    final Map<String, MockRect> index = new HashMap<String, MockRect>();
+    for (MockRect r : a) {
+      index.put(r.getName(), r);
+    }
+
+    for (MockRect rb : b) {
+      final MockRect ra = index.get(rb.getName());
+      rb.assertPosition(ra.getLeft(), ra.getTop());
+    }
+  }
+
+  @Resource("dunebuggy.gif")
+  public void duneBuggyInDefaultPackage() {
+  }
+
+  @Resource("a/b/c/dunebuggy.gif")
+  public void duneBuggyInNonDefaultPackage() {
+  }
+
+  @Resource("io.jpg")
+  public void ioInSamePackage() {
+  }
+
+  /**
+   * Validates that presenting the images in different orders does not affect
+   * the arrangement.
+   */
+  public void testArrangementIsDeterministic() {
+
+    List<MockRect> orderA = Arrays.asList(new MockRect("a", 50, 100),
+        new MockRect("b", 50, 100), new MockRect("c", 100, 50), new MockRect(
+            "d", 50, 50), new MockRect("e", 50, 50));
+    List<MockRect> orderB = new ArrayList<MockRect>();
+    for (int i = orderA.size() - 1; i <= 0; --i) {
+      orderB.add(orderA.get(i));
+    }
+
+    ImageBundleBuilder.arrangeImages(orderA);
+    ImageBundleBuilder.arrangeImages(orderB);
+
+    assertSameArrangement(orderA, orderB);
+  }
+
+  /**
+   * Ensures that the basic image packing algorithm is arranging images as
+   * expected.
+   */
+  public void testBasicImageArrangement() {
+    // Expected in 2nd column, 2nd in 2nd row.
+    final MockRect ra = new MockRect("a", 20, 30);
+    // Expected to be 1st column.
+    final MockRect rb = new MockRect("b", 10, 100);
+    // Expected in 2nd column, 1st in 2nd row.
+    final MockRect rc = new MockRect("c", 20, 40);
+    // Expected in 2nd column, it is the 1st row.
+    final MockRect rd = new MockRect("d", 100, 60);
+    // Expected in 2nd column, 3rd in 2nd row.
+    final MockRect re = new MockRect("e", 10, 30);
+
+    final Collection<MockRect> rects = new ArrayList<MockRect>();
+    Collections.addAll(rects, ra, rb, rc, rd, re);
+    ImageBundleBuilder.arrangeImages(rects);
+
+    ra.assertPosition(30, 60);
+    rb.assertPosition(0, 0);
+    rc.assertPosition(10, 60);
+    rd.assertPosition(10, 0);
+    re.assertPosition(50, 60);
+  }
+
   /**
    * This method is to remind the reader that ClassLoader.getResource() doesn't
    * want a leading "/" on resource names.
@@ -57,18 +203,21 @@
 
   /**
    * Tests that a message is logged and an exception is thrown when a resource
-   * isn't found after being sought based on the method name.
+   * isn't found after being sought based on the ImageBundle.Resource
+   * annotation.
    */
-  public void testResourceNotFoundGivenNoMetaData() {
+  @Resource("notfound.png")
+  public void testResourceNotFoundGivenAnnotation() {
     UnitTestTreeLogger.Builder b = new UnitTestTreeLogger.Builder();
-    b.expectError(ImageBundleGenerator.MSG_NO_FILE_BASED_ON_METHOD_NAME, null);
-    b.expectError("test/nonexistentImg.png", null);
-    b.expectError("test/nonexistentImg.gif", null);
-    b.expectError("test/nonexistentImg.jpg", null);
+    b.expectError(
+        ImageBundleGenerator.msgCannotFindImageFromMetaData("from/metadata/notfound.png"),
+        null);
     UnitTestTreeLogger logger = b.createLogger();
 
     try {
-      getImageName(logger, new String[0], "nonexistentImg", "test", new String[0][], null);
+      getImageName(logger, new String[0], "nonexistentImg", "from.metadata",
+          new String[0][],
+          getResourceAnnotation("testResourceNotFoundGivenAnnotation"));
       fail("Should have thrown");
     } catch (UnableToCompleteException e) {
     }
@@ -84,7 +233,8 @@
     UnitTestTreeLogger.Builder b = new UnitTestTreeLogger.Builder();
     b.expectWarn(ImageBundleGenerator.MSG_JAVADOC_FORM_DEPRECATED, null);
     b.expectError(
-        ImageBundleGenerator.msgCannotFindImageFromMetaData("from/metadata/notfound.png"), null);
+        ImageBundleGenerator.msgCannotFindImageFromMetaData("from/metadata/notfound.png"),
+        null);
     UnitTestTreeLogger logger = b.createLogger();
 
     try {
@@ -98,42 +248,31 @@
 
   /**
    * Tests that a message is logged and an exception is thrown when a resource
-   * isn't found after being sought based on the ImageBundle.Resource
-   * annotation.
+   * isn't found after being sought based on the method name.
    */
-  @Resource("notfound.png")
-  public void testResourceNotFoundGivenAnnotation() {
+  public void testResourceNotFoundGivenNoMetaData() {
     UnitTestTreeLogger.Builder b = new UnitTestTreeLogger.Builder();
-    b.expectError(
-        ImageBundleGenerator.msgCannotFindImageFromMetaData("from/metadata/notfound.png"), null);
+    b.expectError(ImageBundleGenerator.MSG_NO_FILE_BASED_ON_METHOD_NAME, null);
+    b.expectError("test/nonexistentImg.png", null);
+    b.expectError("test/nonexistentImg.gif", null);
+    b.expectError("test/nonexistentImg.jpg", null);
     UnitTestTreeLogger logger = b.createLogger();
 
     try {
-      getImageName(logger, new String[0], "nonexistentImg", "from.metadata", new String[0][],
-          getResourceAnnotation("testResourceNotFoundGivenAnnotation"));
+      getImageName(logger, new String[0], "nonexistentImg", "test",
+          new String[0][], null);
       fail("Should have thrown");
     } catch (UnableToCompleteException e) {
     }
     logger.assertCorrectLogEntries();
   }
 
-  @Resource("dunebuggy.gif")
-  public void duneBuggyInDefaultPackage() {
-  }
-
-  @Resource("a/b/c/dunebuggy.gif")
-  public void duneBuggyInNonDefaultPackage() {
-  }
-
-  @Resource("io.jpg")
-  public void ioInSamePackage() {
-  }
-
   /**
    * Tests that resources can be found in a variety of ways from an image bundle
    * residing in the default package.
    */
-  public void testResourcesFoundFromImageBundleInDefaultPackage() throws UnableToCompleteException {
+  public void testResourcesFoundFromImageBundleInDefaultPackage()
+      throws UnableToCompleteException {
     UnitTestTreeLogger.Builder b = new UnitTestTreeLogger.Builder();
     // Due to [2] below
     b.expectWarn(ImageBundleGenerator.MSG_JAVADOC_FORM_DEPRECATED, null);
@@ -143,37 +282,46 @@
 
     {
       // [1] Find an image in the default package using the method name.
-      String imgName = getImageName(logger, new String[] {"cabbage.jpg", "lettuce.jpg",},
-          "cabbage", "", new String[0][], null);
+      String imgName = getImageName(logger, new String[] {
+          "cabbage.jpg", "lettuce.jpg",}, "cabbage", "", new String[0][], null);
       assertEquals("cabbage.jpg", imgName);
     }
 
     {
       // [2] Find an image in the default package using javadoc.
-      String imgName = getImageName(logger, new String[] {"car.png", "dunebuggy.gif",},
-          "vehicleImage", "", new String[][] {{"dunebuggy.gif"}}, null);
-      assertEquals("dunebuggy.gif", imgName);
-    }
-
-    {
-      // [3] Find an image in the default package using an annotation.
-      String imgName = getImageName(logger, new String[] {"car.png", "dunebuggy.gif",},
-          "vehicleImage", "", new String[0][], getResourceAnnotation("duneBuggyInDefaultPackage"));
-      assertEquals("dunebuggy.gif", imgName);
-    }
-
-    {
-      // [4] Find an image in a non-default package using javadoc.
       String imgName = getImageName(logger, new String[] {
-          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage", "",
-          new String[][] {{"a/b/c/dunebuggy.gif"}}, null);
+          "car.png", "dunebuggy.gif",}, "vehicleImage", "",
+          new String[][] {{"dunebuggy.gif"}}, null);
+      assertEquals("dunebuggy.gif", imgName);
+    }
+
+    {
+      // [3] Find an image in
+      // the default package
+      // using an annotation.
+      String imgName = getImageName(logger, new String[] {
+          "car.png", "dunebuggy.gif",}, "vehicleImage", "", new String[0][],
+          getResourceAnnotation("duneBuggyInDefaultPackage"));
+      assertEquals("dunebuggy.gif", imgName);
+    }
+
+    {
+      // [4] Find an image in a
+      // non-default package using
+      // javadoc.
+      String imgName = getImageName(logger, new String[] {
+          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage",
+          "", new String[][] {{"a/b/c/dunebuggy.gif"}}, null);
       assertEquals("a/b/c/dunebuggy.gif", imgName);
     }
 
     {
-      // [5] Find an image in a non-default package using an annotation.
+      // [5] Find an image in a
+      // non-default package using an
+      // annotation.
       String imgName = getImageName(logger, new String[] {
-          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage", "", new String[0][],
+          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage",
+          "", new String[0][],
           getResourceAnnotation("duneBuggyInNonDefaultPackage"));
       assertEquals("a/b/c/dunebuggy.gif", imgName);
     }
@@ -196,38 +344,42 @@
 
     {
       // [1] Find an image in the same package using the method name.
-      String imgName = getImageName(logger, new String[] {"x/y/z/europa.png", "x/y/z/io.jpg",},
-          "io", "x.y.z", new String[0][], null);
+      String imgName = getImageName(logger, new String[] {
+          "x/y/z/europa.png", "x/y/z/io.jpg",}, "io", "x.y.z", new String[0][],
+          null);
       assertEquals("x/y/z/io.jpg", imgName);
     }
 
     {
       // [2] Find an image in the same package using javadoc.
-      String imgName = getImageName(logger, new String[] {"x/y/z/europa.png", "x/y/z/io.jpg",},
-          "moonImage", "x.y.z", new String[][] {{"io.jpg"}}, null);
+      String imgName = getImageName(logger, new String[] {
+          "x/y/z/europa.png", "x/y/z/io.jpg",}, "moonImage", "x.y.z",
+          new String[][] {{"io.jpg"}}, null);
       assertEquals("x/y/z/io.jpg", imgName);
     }
 
     {
       // [3] Find an image in the same package using an annotation.
-      String imgName = getImageName(logger, new String[] {"x/y/z/europa.png", "x/y/z/io.jpg",},
-          "moonImage", "x.y.z", new String[0][], getResourceAnnotation("ioInSamePackage"));
+      String imgName = getImageName(logger, new String[] {
+          "x/y/z/europa.png", "x/y/z/io.jpg",}, "moonImage", "x.y.z",
+          new String[0][], getResourceAnnotation("ioInSamePackage"));
       assertEquals("x/y/z/io.jpg", imgName);
     }
 
     {
       // [4] Find an image in a non-default package using javadoc.
       String imgName = getImageName(logger, new String[] {
-          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage", "x.y.z",
-          new String[][] {{"a/b/c/dunebuggy.gif"}}, null);
+          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage",
+          "x.y.z", new String[][] {{"a/b/c/dunebuggy.gif"}}, null);
       assertEquals("a/b/c/dunebuggy.gif", imgName);
     }
 
     {
       // [5] Find an image in a non-default package using an annotation.
       String imgName = getImageName(logger, new String[] {
-          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage", "x.y.z",
-          new String[0][], getResourceAnnotation("duneBuggyInNonDefaultPackage"));
+          "car.png", "dunebuggy.gif", "a/b/c/dunebuggy.gif",}, "vehicleImage",
+          "x.y.z", new String[0][],
+          getResourceAnnotation("duneBuggyInNonDefaultPackage"));
       assertEquals("a/b/c/dunebuggy.gif", imgName);
     }
 
@@ -235,6 +387,26 @@
   }
 
   /**
+   * Tests that a warning is logged if both the old "gwt.resource" javadoc
+   * construct is used and a resource annotation is used.
+   */
+  @Resource("Horse Shoes.jpg")
+  public void testWarnOnUseOfAnnotationAndLegacyJavaDoc()
+      throws UnableToCompleteException {
+    UnitTestTreeLogger.Builder b = new UnitTestTreeLogger.Builder();
+    b.expectWarn(ImageBundleGenerator.MSG_MULTIPLE_ANNOTATIONS, null);
+    UnitTestTreeLogger logger = b.createLogger();
+
+    Resource resAnn = getResourceAnnotation("testWarnOnUseOfAnnotationAndLegacyJavaDoc");
+    String imgName = getImageName(logger, new String[] {
+        "test/flypaper.gif", "test/horse shoes.jpg", "test/Horse Shoes.jpg"},
+        "horseshoes", "test", new String[][] {{"Horse Shoes.jpg"}}, resAnn);
+
+    assertEquals("test/Horse Shoes.jpg", imgName);
+    logger.assertCorrectLogEntries();
+  }
+
+  /**
    * Tests that a warning is logged if the old "gwt.resource" javadoc construct
    * is used.
    */
@@ -244,64 +416,16 @@
     UnitTestTreeLogger logger = b.createLogger();
 
     String imgName = getImageName(logger, new String[] {
-        "test/flypaper.gif", "test/horse shoes.jpg", "test/Horse Shoes.jpg"}, "horseshoes", "test",
-        new String[][] {{"Horse Shoes.jpg"}}, null);
+        "test/flypaper.gif", "test/horse shoes.jpg", "test/Horse Shoes.jpg"},
+        "horseshoes", "test", new String[][] {{"Horse Shoes.jpg"}}, null);
 
     assertEquals("test/Horse Shoes.jpg", imgName);
     logger.assertCorrectLogEntries();
   }
 
-  /**
-   * Tests that a warning is logged if both the old "gwt.resource" javadoc
-   * construct is used and a resource annotation is used.
-   */
-  @Resource("Horse Shoes.jpg")
-  public void testWarnOnUseOfAnnotationAndLegacyJavaDoc() throws UnableToCompleteException {
-    UnitTestTreeLogger.Builder b = new UnitTestTreeLogger.Builder();
-    b.expectWarn(ImageBundleGenerator.MSG_MULTIPLE_ANNOTATIONS, null);
-    UnitTestTreeLogger logger = b.createLogger();
-
-    Resource resAnn = getResourceAnnotation("testWarnOnUseOfAnnotationAndLegacyJavaDoc");
-    String imgName = getImageName(logger, new String[] {
-        "test/flypaper.gif", "test/horse shoes.jpg", "test/Horse Shoes.jpg"}, "horseshoes", "test",
-        new String[][] {{"Horse Shoes.jpg"}}, resAnn);
-
-    assertEquals("test/Horse Shoes.jpg", imgName);
-    logger.assertCorrectLogEntries();
-  }
-
-  private Resource getResourceAnnotation(String methodName) {
-    Throwable caught = null;
-    try {
-      Resource res = getClass().getMethod(methodName, new Class[0]).getAnnotation(Resource.class);
-      assertNotNull(res);
-      return res;
-    } catch (SecurityException e) {
-      caught = e;
-    } catch (NoSuchMethodException e) {
-      caught = e;
-    }
-    fail("Unable to get @Resource annotation from method '" + methodName
-        + "' during test due to exception: " + caught.getMessage());
-    return null;
-  }
-
-  private String getImageName(UnitTestTreeLogger logger, final String[] pretendResources,
-      String methodName, String pkgName, String[][] resMetadata, final Resource resAnn)
-      throws UnableToCompleteException {
-    ImageBundleGenerator ibg = new ImageBundleGenerator(new ImageBundleGenerator.ResourceLocator() {
-      private final List<String> resList = Arrays.asList(pretendResources);
-
-      public boolean isResourcePresent(String resName) {
-        return resList.contains(resName);
-      }
-    });
-    JMethodOracle methodOracle = createJMethodOracle(methodName, pkgName, resMetadata, resAnn);
-    return ibg.getImageResourceName(logger, methodOracle);
-  }
-
-  private JMethodOracle createJMethodOracle(final String methodName, final String packageName,
-      final String[][] resourceMetadata, final Resource resourceAnnotation) {
+  private JMethodOracle createJMethodOracle(final String methodName,
+      final String packageName, final String[][] resourceMetadata,
+      final Resource resourceAnnotation) {
     return new JMethodOracle() {
       public Resource getAnnotation(Class<Resource> clazz) {
         return resourceAnnotation;
@@ -320,4 +444,38 @@
       }
     };
   }
+
+  private String getImageName(UnitTestTreeLogger logger,
+      final String[] pretendResources, String methodName, String pkgName,
+      String[][] resMetadata, final Resource resAnn)
+      throws UnableToCompleteException {
+    ImageBundleGenerator ibg = new ImageBundleGenerator(
+        new ImageBundleGenerator.ResourceLocator() {
+          private final List<String> resList = Arrays.asList(pretendResources);
+
+          public boolean isResourcePresent(String resName) {
+            return resList.contains(resName);
+          }
+        });
+    JMethodOracle methodOracle = createJMethodOracle(methodName, pkgName,
+        resMetadata, resAnn);
+    return ibg.getImageResourceName(logger, methodOracle);
+  }
+
+  private Resource getResourceAnnotation(String methodName) {
+    Throwable caught = null;
+    try {
+      Resource res = getClass().getMethod(methodName, new Class[0]).getAnnotation(
+          Resource.class);
+      assertNotNull(res);
+      return res;
+    } catch (SecurityException e) {
+      caught = e;
+    } catch (NoSuchMethodException e) {
+      caught = e;
+    }
+    fail("Unable to get @Resource annotation from method '" + methodName
+        + "' during test due to exception: " + caught.getMessage());
+    return null;
+  }
 }