--- a/accessible/src/base/TreeWalker.cpp
+++ b/accessible/src/base/TreeWalker.cpp
@@ -4,17 +4,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "TreeWalker.h"
 
 #include "Accessible.h"
 #include "nsAccessibilityService.h"
 #include "DocAccessible.h"
 
-#include "nsINodeList.h"
+#include "mozilla/dom/Element.h"
 
 using namespace mozilla::a11y;
 
 ////////////////////////////////////////////////////////////////////////////////
 // WalkState
 ////////////////////////////////////////////////////////////////////////////////
 
 namespace mozilla {
@@ -34,19 +34,19 @@ struct WalkState
 } // namespace a11y
 } // namespace mozilla
 
 ////////////////////////////////////////////////////////////////////////////////
 // TreeWalker
 ////////////////////////////////////////////////////////////////////////////////
 
 TreeWalker::
-  TreeWalker(Accessible* aContext, nsIContent* aContent, bool aWalkCache) :
+  TreeWalker(Accessible* aContext, nsIContent* aContent, uint32_t aFlags) :
   mDoc(aContext->Document()), mContext(aContext),
-  mWalkCache(aWalkCache), mState(nullptr)
+  mFlags(aFlags), mState(nullptr)
 {
   NS_ASSERTION(aContent, "No node for the accessible tree walker!");
 
   if (aContent)
     mState = new WalkState(aContent);
 
   mChildFilter = mContext->CanHaveAnonChildren() ?
     nsIContent::eAllChildren : nsIContent::eAllButXBL;
@@ -81,52 +81,79 @@ TreeWalker::NextChildInternal(bool aNoWa
   if (mState->childList)
     mState->childList->GetLength(&length);
 
   while (mState->childIdx < length) {
     nsIContent* childNode = mState->childList->Item(mState->childIdx);
     mState->childIdx++;
 
     bool isSubtreeHidden = false;
-    Accessible* accessible = mWalkCache ? mDoc->GetAccessible(childNode) :
+    Accessible* accessible = mFlags & eWalkCache ?
+      mDoc->GetAccessible(childNode) :
       GetAccService()->GetOrCreateAccessible(childNode, mContext,
                                              &isSubtreeHidden);
 
     if (accessible)
       return accessible;
 
     // Walk down into subtree to find accessibles.
     if (!isSubtreeHidden) {
-      if (!PushState(childNode))
-        break;
-
+      PushState(childNode);
       accessible = NextChildInternal(true);
       if (accessible)
         return accessible;
     }
   }
 
   // No more children, get back to the parent.
+  nsIContent* anchorNode = mState->content;
   PopState();
+  if (aNoWalkUp)
+    return nullptr;
+
+  if (mState)
+    return NextChildInternal(false);
+
+  // If we traversed the whole subtree of the anchor node. Move to next node
+  // relative anchor node within the context subtree if possible.
+  if (mFlags != eWalkContextTree)
+    return nullptr;
+
+  while (anchorNode != mContext->GetNode()) {
+    nsINode* parentNode = anchorNode->GetFlattenedTreeParent();
+    if (!parentNode || !parentNode->IsElement())
+      return nullptr;
 
-  return aNoWalkUp ? nullptr : NextChildInternal(false);
+    PushState(parentNode->AsElement());
+    mState->childList = mState->content->GetChildren(mChildFilter);
+    length = 0;
+    if (mState->childList)
+      mState->childList->GetLength(&length);
+
+    while (mState->childIdx < length) {
+      nsIContent* childNode = mState->childList->Item(mState->childIdx);
+      mState->childIdx++;
+      if (childNode == anchorNode)
+        return NextChildInternal(false);
+    }
+    PopState();
+
+    anchorNode = parentNode->AsElement();
+  }
+
+  return nullptr;
 }
 
 void
 TreeWalker::PopState()
 {
   WalkState* prevToLastState = mState->prevState;
   delete mState;
   mState = prevToLastState;
 }
 
-bool
+void
 TreeWalker::PushState(nsIContent* aContent)
 {
   WalkState* nextToLastState = new WalkState(aContent);
-  if (!nextToLastState)
-    return false;
-
   nextToLastState->prevState = mState;
   mState = nextToLastState;
-
-  return true;
 }

--- a/accessible/src/base/TreeWalker.h
+++ b/accessible/src/base/TreeWalker.h
@@ -1,36 +1,52 @@
 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef mozilla_a11y_TreeWalker_h_
 #define mozilla_a11y_TreeWalker_h_
 
+#include "mozilla/Attributes.h"
 #include <stdint.h>
 
 class nsIContent;
 
 namespace mozilla {
 namespace a11y {
 
 class Accessible;
 class DocAccessible;
 
 struct WalkState;
 
 /**
  * This class is used to walk the DOM tree to create accessible tree.
  */
-class TreeWalker
+class TreeWalker MOZ_FINAL
 {
 public:
-  TreeWalker(Accessible* aContext, nsIContent* aNode, bool aWalkCache = false);
-  virtual ~TreeWalker();
+  enum {
+    // used to walk the existing tree of the given node
+    eWalkCache = 1,
+    // used to walk the context tree starting from given node
+    eWalkContextTree = 2 | eWalkCache
+  };
+
+  /**
+   * Constructor
+   *
+   * @param aContext [in] container accessible for the given node, used to
+   *                   define accessible context
+   * @param aNode    [in] the node the search will be prepared relative to
+   * @param aFlags   [in] flags (see enum above)
+   */
+  TreeWalker(Accessible* aContext, nsIContent* aNode, uint32_t aFlags = 0);
+  ~TreeWalker();
 
   /**
    * Return the next child accessible.
    *
    * @note Returned accessible is bound to the document, if the accessible is
    *       rejected during tree creation then the caller should be unbind it
    *       from the document.
    */
@@ -54,26 +70,26 @@ private:
   Accessible* NextChildInternal(bool aNoWalkUp);
 
   /**
    * Create new state for the given node and push it on top of stack.
    *
    * @note State stack is used to navigate up/down the DOM subtree during
    *        accessible children search.
    */
-  bool PushState(nsIContent *aNode);
+  void PushState(nsIContent* aNode);
 
   /**
    * Pop state from stack.
    */
   void PopState();
 
   DocAccessible* mDoc;
   Accessible* mContext;
   int32_t mChildFilter;
-  bool mWalkCache;
+  uint32_t mFlags;
   WalkState* mState;
 };
 
 } // namespace a11y
 } // namespace mozilla
 
 #endif // mozilla_a11y_TreeWalker_h_

--- a/accessible/src/generic/Accessible.cpp
+++ b/accessible/src/generic/Accessible.cpp
@@ -3055,50 +3055,16 @@ Accessible::GetSiblingAtOffset(int32_t a
 
   Accessible* child = mParent->GetChildAt(mIndexInParent + aOffset);
   if (aError && !child)
     *aError = NS_ERROR_UNEXPECTED;
 
   return child;
 }
 
-Accessible* 
-Accessible::GetFirstAvailableAccessible(nsINode *aStartNode) const
-{
-  Accessible* accessible = mDoc->GetAccessible(aStartNode);
-  if (accessible)
-    return accessible;
-
-  nsCOMPtr<nsIDocument> doc = aStartNode->OwnerDoc();
-
-  nsCOMPtr<nsINode> currentNode = aStartNode;
-  ErrorResult rv;
-  nsRefPtr<dom::TreeWalker> walker =
-    doc->CreateTreeWalker(*GetNode(),
-                          nsIDOMNodeFilter::SHOW_ELEMENT | nsIDOMNodeFilter::SHOW_TEXT,
-                          nullptr, rv);
-  NS_ENSURE_TRUE(walker, nullptr);
-
-  walker->SetCurrentNode(*currentNode, rv);
-  if (rv.Failed())
-    return nullptr;
-
-  while (true) {
-    currentNode = walker->NextNode(rv);
-    if (!currentNode || rv.Failed())
-      return nullptr;
-
-    Accessible* accessible = mDoc->GetAccessible(currentNode);
-    if (accessible)
-      return accessible;
-  }
-
-  return nullptr;
-}
-
 double
 Accessible::AttrNumericValue(nsIAtom* aAttr) const
 {
   if (!mRoleMapEntry || mRoleMapEntry->valueRule == eNoValue)
     return UnspecifiedNaN();
 
   nsAutoString attrValue;
   if (!mContent->GetAttr(kNameSpaceID_None, aAttr, attrValue))

--- a/accessible/src/generic/Accessible.h
+++ b/accessible/src/generic/Accessible.h
@@ -883,26 +883,16 @@ protected:
    * Return the name for XUL element.
    */
   static void XULElmName(DocAccessible* aDocument,
                          nsIContent* aElm, nsString& aName);
 
   // helper method to verify frames
   static nsresult GetFullKeyName(const nsAString& aModifierName, const nsAString& aKeyName, nsAString& aStringOut);
 
-  /**
-   * Return an accessible for the given DOM node, or if that node isn't
-   * accessible, return the accessible for the next DOM node which has one
-   * (based on forward depth first search).
-   *
-   * @param  aStartNode  [in] the DOM node to start from
-   * @return              the resulting accessible
-   */
-  Accessible* GetFirstAvailableAccessible(nsINode* aStartNode) const;
-
   //////////////////////////////////////////////////////////////////////////////
   // Action helpers
 
   /**
    * Prepares click action that will be invoked in timeout.
    *
    * @note  DoCommand() prepares an action in timeout because when action
    *  command opens a modal dialog/window, it won't return until the

--- a/accessible/src/generic/DocAccessible.cpp
+++ b/accessible/src/generic/DocAccessible.cpp
@@ -1778,17 +1778,17 @@ DocAccessible::UpdateTree(Accessible* aC
 #endif
 
   nsRefPtr<AccReorderEvent> reorderEvent = new AccReorderEvent(aContainer);
 
   if (child) {
     updateFlags |= UpdateTreeInternal(child, aIsInsert, reorderEvent);
   } else {
     if (aIsInsert) {
-      TreeWalker walker(aContainer, aChildNode, true);
+      TreeWalker walker(aContainer, aChildNode, TreeWalker::eWalkCache);
 
       while ((child = walker.NextChild()))
         updateFlags |= UpdateTreeInternal(child, aIsInsert, reorderEvent);
     } else {
       // aChildNode may not coorespond to a particular accessible, to handle
       // this we go through all the children of aContainer.  Then if a child
       // has aChildNode as an ancestor, or does not have the node for
       // aContainer as an ancestor remove that child of aContainer.  Note that

--- a/accessible/src/generic/HyperTextAccessible.cpp
+++ b/accessible/src/generic/HyperTextAccessible.cpp
@@ -297,17 +297,26 @@ HyperTextAccessible::DOMPointToOffset(ns
         findContent->NodeInfo()->Equals(nsGkAtoms::br) &&
         findContent->AttrValueIs(kNameSpaceID_None,
                                  nsGkAtoms::mozeditorbogusnode,
                                  nsGkAtoms::_true,
                                  eIgnoreCase)) {
       // This <br> is the hacky "bogus node" used when there is no text in a control
       return 0;
     }
-    descendant = GetFirstAvailableAccessible(findNode);
+
+    descendant = mDoc->GetAccessible(findNode);
+    if (!descendant && findNode->IsContent()) {
+      Accessible* container = mDoc->GetContainerAccessible(findNode);
+      if (container) {
+        TreeWalker walker(container, findNode->AsContent(),
+                          TreeWalker::eWalkContextTree);
+        descendant = walker.NextChild();
+      }
+    }
   }
 
   return TransformOffset(descendant, offset, aIsEndOffset);
 }
 
 int32_t
 HyperTextAccessible::TransformOffset(Accessible* aDescendant,
                                      int32_t aOffset, bool aIsEndOffset) const

--- a/accessible/tests/mochitest/text/test_hypertext.html
+++ b/accessible/tests/mochitest/text/test_hypertext.html
@@ -53,17 +53,17 @@
       testText(IDs, 0, 13, "hello " + kEmbedChar + " see " + kEmbedChar);
 
       ////////////////////////////////////////////////////////////////////////
       // getTextAtOffset line boundary
 
       testTextAtOffset(0, BOUNDARY_LINE_START, "line ", 0, 5,
                        "hypertext3", kOk, kOk, kOk);
 
-      // XXX: see bug 638684.
+      // XXX: see bug 634202.
       testTextAtOffset(0, BOUNDARY_LINE_START, "line ", 0, 5,
                        "hypertext4", kTodo, kOk, kTodo);
 
       //////////////////////////////////////////////////////////////////////////
       // list
       //////////////////////////////////////////////////////////////////////////
 
       IDs = [ "list" ];

--- a/accessible/tests/mochitest/textselection/test_general.html
+++ b/accessible/tests/mochitest/textselection/test_general.html
@@ -104,16 +104,54 @@
       }
 
       this.getID = function removeSelection_getID()
       {
         return "nsIAccessibleText::removeSelection test for " + aID;
       }
     }
 
+    function changeDOMSelection(aID, aNodeID1, aNodeOffset1,
+                                aNodeID2, aNodeOffset2,
+                                aStartOffset, aEndOffset)
+    {
+      this.hyperText = getAccessible(aID, [ nsIAccessibleText ]);
+
+      this.eventSeq = [
+        new invokerChecker(EVENT_TEXT_SELECTION_CHANGED, aID)
+      ];
+
+      this.invoke = function changeDOMSelection_invoke()
+      {
+        var sel = window.getSelection();
+        var range = document.createRange();
+        range.setStart(getNode(aNodeID1), aNodeOffset1);
+        range.setEnd(getNode(aNodeID2), aNodeOffset2);
+        sel.addRange(range);
+      }
+
+      this.finalCheck = function changeDOMSelection_finalCheck()
+      {
+        is(this.hyperText.selectionCount, 1,
+           "setSelectionBounds: Wrong selection count for " + aID);
+        var startOffset = {}, endOffset = {};
+        this.hyperText.getSelectionBounds(0, startOffset, endOffset);
+
+        is(startOffset.value, aStartOffset,
+           "setSelectionBounds: Wrong start offset for " + aID);
+        is(endOffset.value, aEndOffset,
+           "setSelectionBounds: Wrong end offset for " + aID);
+      }
+
+      this.getID = function changeDOMSelection_getID()
+      {
+        return "DOM selection change for " + aID;
+      }
+    }
+
     function onfocusEventSeq(aID)
     {
       var caretMovedChecker =
         new invokerChecker(EVENT_TEXT_CARET_MOVED, aID);
       var selChangedChecker =
         new invokerChecker(EVENT_TEXT_SELECTION_CHANGED, aID);
       selChangedChecker.unexpected = true;
 
@@ -136,16 +174,17 @@
       gQueue.push(new removeSelection("paragraph"));
 
       gQueue.push(new synthFocus("textbox", onfocusEventSeq("textbox")));
       gQueue.push(new changeSelection("textbox", 1, 3));
 
       gQueue.push(new synthFocus("textarea", onfocusEventSeq("textarea")));
       gQueue.push(new changeSelection("textarea", 1, 3));
 
+      gQueue.push(new changeDOMSelection("c1", "c1_span1", 0, "c1_span2", 0, 2, 2));
       gQueue.invoke(); // Will call SimpleTest.finish();
     }
 
     SimpleTest.waitForExplicitFinish();
     addA11yLoadEvent(doTests);
   </script>
 </head>
 
@@ -164,11 +203,12 @@
   <p id="display"></p>
   <div id="content" style="display: none"></div>
   <pre id="test">
   </pre>
 
   <p id="paragraph">hello</p>
   <input id="textbox" value="hello"/>
   <textarea id="textarea">hello</textarea>
+  <div id="c1">hi<span id="c1_span1"></span><span id="c1_span2"></span>hi</div>
 
 </body>
 </html>