--- a/accessible/src/base/nsDocAccessible.cpp
+++ b/accessible/src/base/nsDocAccessible.cpp
@@ -1949,17 +1949,21 @@ nsDocAccessible::UpdateTreeInternal(nsAc
     if (!accessible) {
       updateFlags |= UpdateTreeInternal(aContainer, node->GetFirstChild(),
                                         nsnull, aIsInsert);
       continue;
     }
 
     updateFlags |= eAccessible;
 
-    if (!aIsInsert) {
+    if (aIsInsert) {
+      // Create accessible tree for shown accessible.
+      CacheChildrenInSubtree(accessible);
+
+    } else {
       // Fire menupopup end event before hide event if a menu goes away.
 
       // XXX: We don't look into children of hidden subtree to find hiding
       // menupopup (as we did prior bug 570275) because we don't do that when
       // menu is showing (and that's impossible until bug 606924 is fixed).
       // Nevertheless we should do this at least because layout coalesces
       // the changes before our processing and we may miss some menupopup
       // events. Now we just want to be consistent in content insertion/removal
@@ -2017,16 +2021,30 @@ nsDocAccessible::UpdateTreeInternal(nsAc
       UncacheChildrenInSubtree(accessible);
     }
   }
 
   return updateFlags;
 }
 
 void
+nsDocAccessible::CacheChildrenInSubtree(nsAccessible* aRoot)
+{
+  aRoot->EnsureChildren();
+
+  PRUint32 count = aRoot->GetChildCount();
+  for (PRUint32 idx = 0; idx < count; idx++)  {
+    nsAccessible* child = aRoot->GetChildAt(idx);
+    // Don't cross document boundaries.
+    if (child->IsContent())
+      CacheChildrenInSubtree(child);
+  }
+}
+
+void
 nsDocAccessible::UncacheChildrenInSubtree(nsAccessible* aRoot)
 {
   PRUint32 count = aRoot->GetCachedChildCount();
   for (PRUint32 idx = 0; idx < count; idx++)
     UncacheChildrenInSubtree(aRoot->GetCachedChildAt(idx));
 
   if (aRoot->IsPrimaryForNode() &&
       mNodeToAccessibleMap.Get(aRoot->GetNode()) == aRoot)

--- a/accessible/src/base/nsDocAccessible.h
+++ b/accessible/src/base/nsDocAccessible.h
@@ -413,16 +413,21 @@ protected:
   };
 
   PRUint32 UpdateTreeInternal(nsAccessible* aContainer,
                               nsIContent* aStartNode,
                               nsIContent* aEndNode,
                               PRBool aIsInsert);
 
   /**
+   * Create accessible tree.
+   */
+  void CacheChildrenInSubtree(nsAccessible* aRoot);
+
+  /**
    * Remove accessibles in subtree from node to accessible map.
    */
   void UncacheChildrenInSubtree(nsAccessible* aRoot);
 
   /**
    * Shutdown any cached accessible in the subtree.
    *
    * @param aAccessible  [in] the root of the subrtee to invalidate accessible

--- a/accessible/tests/mochitest/test_nsIAccessibleHyperText.html
+++ b/accessible/tests/mochitest/test_nsIAccessibleHyperText.html
@@ -9,16 +9,18 @@ https://bugzilla.mozilla.org/show_bug.cg
 
   <script type="application/javascript"
           src="chrome://mochikit/content/MochiKit/packed.js"></script>
   <script type="application/javascript"
           src="chrome://mochikit/content/tests/SimpleTest/SimpleTest.js"></script>
 
   <script type="application/javascript"
           src="common.js"></script>
+  <script type="application/javascript"
+          src="events.js"></script>
 
   <script type="application/javascript">
     var gParagraphAcc;
 
     function testLinkIndexAtOffset(aID, aOffset, aIndex)
     {
       var htAcc = getAccessible(aID, [nsIAccessibleHyperText]);
       is(htAcc.getLinkIndexAtOffset(aOffset), aIndex,
@@ -35,33 +37,58 @@ https://bugzilla.mozilla.org/show_bug.cg
       var linkIndex = gParagraphAcc.getLinkIndex(linkAcc);
       is(linkIndex, aExpectedLinkIndex, "Wrong link index for " + aID + "!");
 
       // Just test the link's name to make sure we get the right one.
       is(linkAcc.getAnchor(0).name, aName, "Wrong name for " + aID + "!");
     }
 
     const kLinksCount = 128;
-    function prepareTest()
+    function addLinks(aContainerID)
     {
-      var container = document.getElementById("p3");
-      for (var jdx = 0; jdx < kLinksCount; jdx++) {
-        var a = document.createElement("a");
-        a.setAttribute("href", "mozilla.org");
-        a.textContent = "mozilla";
-        container.appendChild(a);
+      this.containerNode = getNode(aContainerID);
+
+      this.eventSeq = [
+        new invokerChecker(EVENT_REORDER, this.containerNode)
+      ];
 
-        var span = document.createElement("span");
-        span.textContent = " text ";
-        container.appendChild(span);
+      this.invoke = function addLinks_invoke()
+      {
+        for (var jdx = 0; jdx < kLinksCount; jdx++) {
+          var a = document.createElement("a");
+          a.setAttribute("href", "mozilla.org");
+          a.textContent = "mozilla";
+          this.containerNode.appendChild(a);
+
+          var span = document.createElement("span");
+          span.textContent = " text ";
+          this.containerNode.appendChild(span);
+        }
       }
 
-      window.setTimeout(doTest, 0);
+      this.finalCheck = function addLinks_finalCheck()
+      {
+        // getLinkAt and getLinkIndex.
+        var htAcc = getAccessible(this.containerNode, [nsIAccessibleHyperText]);
+        for (var jdx = 0; jdx < kLinksCount; jdx++) {
+          var link = htAcc.getLinkAt(jdx);
+          ok(link, "No link at index " + jdx + " for '" + aContainerID + "'");
+
+          var linkIdx = htAcc.getLinkIndex(link);
+          is(linkIdx, jdx, "Wrong link index for '" + aContainerID + "'!");
+        }
+      }
+
+      this.getID = function addLinks_getID()
+      {
+        return "Add links for '" + aContainerID + "'";
+      }
     }
 
+    var gQueue = null;
     function doTest()
     {
       // Test link count
       gParagraphAcc = getAccessible("testParagraph", [nsIAccessibleHyperText]);
       is(gParagraphAcc.linkCount, 7, "Wrong link count for paragraph!");
 
       // normal hyperlink
       testThis("NormalHyperlink", 14, 0, "Mozilla Foundation");
@@ -85,27 +112,16 @@ https://bugzilla.mozilla.org/show_bug.cg
       testThis("namedAnchor", 193, 6, "This should never be of state_linked");
 
       // Paragraph with link
       var p2 = getAccessible("p2", [nsIAccessibleHyperText]);
       var link = p2.getLinkAt(0);
       is(link, p2.getChildAt(0), "Wrong link for p2");
       is(p2.linkCount, 1, "Wrong link count for p2");
 
-      // getLinkAt and getLinkIndex.
-      var container = document.getElementById("p3");
-      var htAcc = getAccessible(container, [nsIAccessibleHyperText]);
-      for (var jdx = 0; jdx < kLinksCount; jdx++) {
-        var link = htAcc.getLinkAt(jdx);
-        ok(link, "No link at index " + jdx + " for 'p3'");
-
-        var linkIdx = htAcc.getLinkIndex(link);
-        is(linkIdx, jdx, "Wrong link index for 'p3'!");
-      };
-
       // getLinkIndexAtOffset, causes the offsets to be cached;
       testLinkIndexAtOffset("p4", 0, 0); // 1st 'mozilla' link
       testLinkIndexAtOffset("p4", 1, 1); // 2nd 'mozilla' link
       testLinkIndexAtOffset("p4", 2, -1); // ' ' of ' te' text node
       testLinkIndexAtOffset("p4", 3, -1); // 't' of ' te' text node
       testLinkIndexAtOffset("p4", 5, -1); // 'x' of 'xt ' text node
       testLinkIndexAtOffset("p4", 7, -1); // ' ' of 'xt ' text node
       testLinkIndexAtOffset("p4", 8, 2); // 3d 'mozilla' link
@@ -117,21 +133,23 @@ https://bugzilla.mozilla.org/show_bug.cg
       testLinkIndexAtOffset("p4", 1, 1); // 2nd 'mozilla' link
       testLinkIndexAtOffset("p4", 2, -1); // ' ' of ' te' text node
       testLinkIndexAtOffset("p4", 3, -1); // 't' of ' te' text node
       testLinkIndexAtOffset("p4", 5, -1); // 'x' of 'xt ' text node
       testLinkIndexAtOffset("p4", 7, -1); // ' ' of 'xt ' text node
       testLinkIndexAtOffset("p4", 8, 2); // 3d 'mozilla' link
       testLinkIndexAtOffset("p4", 9, 2); // the end, latest link
 
-      SimpleTest.finish();
+      gQueue = new eventQueue();
+      gQueue.push(new addLinks("p3"));
+      gQueue.invoke(); // Will call SimpleTest.finish();
     }
 
     SimpleTest.waitForExplicitFinish();
-    addA11yLoadEvent(prepareTest);
+    addA11yLoadEvent(doTest);
   </script>
 </head>
 <body>
 
   <a target="_blank"
      title="Create tests for NSIAccessibleHyperlink interface"
      href="https://bugzilla.mozilla.org/show_bug.cgi?id=418368">
     Mozilla Bug 418368