Back out bug 263359 and bug 624798 because of performance regressions (bug 650189)
authorSimon Montagu <smontagu@smontagu.org>
Wed, 27 Apr 2011 11:47:18 +0300
changeset 68657 fa0295a97f1bb58251479ac0734eef96b1394249
parent 68656 8deabe91c24be22a06849ac6d44c8ecd624f5272
child 68658 1e64d699aa012c88e45473b97ce43c70f91f5046
push idunknown
push userunknown
push dateunknown
bugs263359, 624798, 650189
milestone6.0a1
Back out bug 263359 and bug 624798 because of performance regressions (bug 650189)
content/base/src/nsGkAtomList.h
content/canvas/src/nsCanvasRenderingContext2D.cpp
layout/base/nsBidi.h
layout/base/nsBidiPresUtils.cpp
layout/base/nsBidiPresUtils.h
layout/base/nsLayoutUtils.cpp
layout/base/nsPresContext.cpp
layout/base/nsPresContext.h
layout/base/nsPresShell.cpp
layout/base/tests/Makefile.in
layout/base/tests/test_bug644768.html
layout/generic/Makefile.in
layout/generic/nsBidiFrames.cpp
layout/generic/nsBidiFrames.h
layout/generic/nsBlockFrame.cpp
layout/generic/nsFrameList.cpp
layout/generic/nsImageFrame.cpp
layout/generic/nsLineBox.cpp
layout/generic/nsQueryFrame.h
layout/generic/nsTextFrameThebes.cpp
layout/reftests/bidi/229367-1-ref.html
layout/reftests/bidi/229367-1.html
layout/reftests/bidi/229367-2-ref.html
layout/reftests/bidi/229367-2.html
layout/reftests/bidi/229367-3-ref.html
layout/reftests/bidi/229367-3.html
layout/reftests/bidi/263359-1-ref.html
layout/reftests/bidi/263359-1.html
layout/reftests/bidi/263359-1a.html
layout/reftests/bidi/263359-1b.html
layout/reftests/bidi/263359-2-ref.html
layout/reftests/bidi/263359-2.html
layout/reftests/bidi/263359-3-ref.html
layout/reftests/bidi/263359-3.html
layout/reftests/bidi/263359-4-ref.html
layout/reftests/bidi/263359-4.html
layout/reftests/bidi/613157-1-ref.html
layout/reftests/bidi/613157-1.html
layout/reftests/bidi/613157-2-ref.html
layout/reftests/bidi/613157-2.html
layout/reftests/bidi/reftest.list
layout/svg/base/src/nsSVGGlyphFrame.cpp
layout/xul/base/src/nsTextBoxFrame.cpp
layout/xul/base/src/tree/src/nsTreeBodyFrame.cpp
--- a/content/base/src/nsGkAtomList.h
+++ b/content/base/src/nsGkAtomList.h
@@ -1718,16 +1718,17 @@ GK_ATOM(bcTableCellFrame, "BCTableCellFr
 GK_ATOM(blockFrame, "BlockFrame")
 GK_ATOM(boxFrame, "BoxFrame")
 GK_ATOM(brFrame, "BRFrame")
 GK_ATOM(bulletFrame, "BulletFrame")
 GK_ATOM(columnSetFrame, "ColumnSetFrame")
 GK_ATOM(comboboxControlFrame, "ComboboxControlFrame")
 GK_ATOM(comboboxDisplayFrame, "ComboboxDisplayFrame")
 GK_ATOM(deckFrame, "DeckFrame")
+GK_ATOM(directionalFrame, "DirectionalFrame")
 GK_ATOM(fieldSetFrame, "FieldSetFrame")
 GK_ATOM(frameSetFrame, "FrameSetFrame")
 GK_ATOM(gfxButtonControlFrame, "gfxButtonControlFrame")
 GK_ATOM(HTMLButtonControlFrame, "HTMLButtonControlFrame")
 GK_ATOM(HTMLCanvasFrame, "HTMLCanvasFrame")
 GK_ATOM(subDocumentFrame, "subDocumentFrame")
 GK_ATOM(imageBoxFrame, "ImageBoxFrame")
 GK_ATOM(imageFrame, "ImageFrame")
--- a/content/canvas/src/nsCanvasRenderingContext2D.cpp
+++ b/content/canvas/src/nsCanvasRenderingContext2D.cpp
@@ -98,17 +98,16 @@
 #include "gfxPlatform.h"
 #include "gfxFont.h"
 #include "gfxTextRunCache.h"
 #include "gfxBlur.h"
 #include "gfxUtils.h"
 
 #include "nsFrameManager.h"
 #include "nsFrameLoader.h"
-#include "nsBidi.h"
 #include "nsBidiPresUtils.h"
 #include "Layers.h"
 #include "CanvasUtils.h"
 #include "nsIMemoryReporter.h"
 #include "nsStyleUtil.h"
 #include "CanvasImageCache.h"
 
 #include <algorithm>
@@ -2648,16 +2647,20 @@ nsCanvasRenderingContext2D::DrawOrMeasur
     }
 
     nsIPresShell* presShell = GetPresShell();
     if (!presShell)
         return NS_ERROR_FAILURE;
 
     nsIDocument* document = presShell->GetDocument();
 
+    nsBidiPresUtils* bidiUtils = presShell->GetPresContext()->GetBidiUtils();
+    if (!bidiUtils)
+        return NS_ERROR_FAILURE;
+
     // replace all the whitespace characters with U+0020 SPACE
     nsAutoString textToDraw(aRawText);
     TextReplaceWhitespaceCharacters(textToDraw);
 
     // for now, default to ltr if not in doc
     PRBool isRTL = PR_FALSE;
 
     if (content && content->IsInDoc()) {
@@ -2693,27 +2696,25 @@ nsCanvasRenderingContext2D::DrawOrMeasur
 
     processor.mFontgrp = GetCurrentFontStyle();
     NS_ASSERTION(processor.mFontgrp, "font group is null");
 
     nscoord totalWidth;
 
     // calls bidi algo twice since it needs the full text width and the
     // bounding boxes before rendering anything
-    nsBidi bidiEngine;
-    rv = nsBidiPresUtils::ProcessText(textToDraw.get(),
-                                      textToDraw.Length(),
-                                      isRTL ? NSBIDI_RTL : NSBIDI_LTR,
-                                      presShell->GetPresContext(),
-                                      processor,
-                                      nsBidiPresUtils::MODE_MEASURE,
-                                      nsnull,
-                                      0,
-                                      &totalWidth,
-                                      &bidiEngine);
+    rv = bidiUtils->ProcessText(textToDraw.get(),
+                                textToDraw.Length(),
+                                isRTL ? NSBIDI_RTL : NSBIDI_LTR,
+                                presShell->GetPresContext(),
+                                processor,
+                                nsBidiPresUtils::MODE_MEASURE,
+                                nsnull,
+                                0,
+                                &totalWidth);
     if (NS_FAILED(rv))
         return rv;
 
     if (aWidth)
         *aWidth = static_cast<float>(totalWidth);
 
     // if only measuring, don't need to do any more work
     if (aOp==TEXT_DRAW_OPERATION_MEASURE)
@@ -2801,26 +2802,25 @@ nsCanvasRenderingContext2D::DrawOrMeasur
 
         gfxContext* ctx = ShadowInitialize(drawExtents, blur);
 
         if (ctx) {
             CopyContext(ctx, mThebes);
             ctx->SetOperator(gfxContext::OPERATOR_SOURCE);
             processor.mThebes = ctx;
 
-            rv = nsBidiPresUtils::ProcessText(textToDraw.get(),
-                                              textToDraw.Length(),
-                                              isRTL ? NSBIDI_RTL : NSBIDI_LTR,
-                                              presShell->GetPresContext(),
-                                              processor,
-                                              nsBidiPresUtils::MODE_DRAW,
-                                              nsnull,
-                                              0,
-                                              nsnull,
-                                              &bidiEngine);
+            rv = bidiUtils->ProcessText(textToDraw.get(),
+                                        textToDraw.Length(),
+                                        isRTL ? NSBIDI_RTL : NSBIDI_LTR,
+                                        presShell->GetPresContext(),
+                                        processor,
+                                        nsBidiPresUtils::MODE_DRAW,
+                                        nsnull,
+                                        0,
+                                        nsnull);
             if (NS_FAILED(rv))
                 return rv;
 
             ShadowFinalize(blur);
         }
 
         processor.mThebes = mThebes;
     }
@@ -2839,26 +2839,25 @@ nsCanvasRenderingContext2D::DrawOrMeasur
 
             // don't want operators to be applied twice
             mThebes->SetOperator(gfxContext::OPERATOR_SOURCE);
         }
 
         ApplyStyle(STYLE_FILL);
     }
 
-    rv = nsBidiPresUtils::ProcessText(textToDraw.get(),
-                                      textToDraw.Length(),
-                                      isRTL ? NSBIDI_RTL : NSBIDI_LTR,
-                                      presShell->GetPresContext(),
-                                      processor,
-                                      nsBidiPresUtils::MODE_DRAW,
-                                      nsnull,
-                                      0,
-                                      nsnull,
-                                      &bidiEngine);
+    rv = bidiUtils->ProcessText(textToDraw.get(),
+                                textToDraw.Length(),
+                                isRTL ? NSBIDI_RTL : NSBIDI_LTR,
+                                presShell->GetPresContext(),
+                                processor,
+                                nsBidiPresUtils::MODE_DRAW,
+                                nsnull,
+                                0,
+                                nsnull);
 
     // this needs to be restored before function can return
     if (doUseIntermediateSurface) {
         mThebes->PopGroupToSource();
         DirtyAllStyles();
     }
 
     if (NS_FAILED(rv))
--- a/layout/base/nsBidi.h
+++ b/layout/base/nsBidi.h
@@ -768,17 +768,17 @@ public:
    *      the number of objects to be reordered.
    *      It must be <code>aLength>0</code>.
    *
    * @param aIndexMap is a pointer to an array of <code>aLength</code>
    *      indexes which will reflect the reordering of the characters.
    *      The array does not need to be initialized.<p>
    *      The index map will result in <code>aIndexMap[aLogicalIndex]==aVisualIndex</code>.
    */
-  static nsresult ReorderLogical(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap);
+  nsresult ReorderLogical(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap);
 #endif // FULL_BIDI_ENGINE
   /**
    * This is a convenience function that does not use a nsBidi object.
    * It is intended to be used for when an application has determined the levels
    * of objects (character sequences) and just needs to have them reordered (L2).
    * This is equivalent to using <code>GetVisualMap</code> on a
    * <code>nsBidi</code> object.
    *
@@ -789,17 +789,17 @@ public:
    *      the number of objects to be reordered.
    *      It must be <code>aLength>0</code>.
    *
    * @param aIndexMap is a pointer to an array of <code>aLength</code>
    *      indexes which will reflect the reordering of the characters.
    *      The array does not need to be initialized.<p>
    *      The index map will result in <code>aIndexMap[aVisualIndex]==aLogicalIndex</code>.
    */
-  static nsresult ReorderVisual(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap);
+  nsresult ReorderVisual(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap);
 
 #ifdef FULL_BIDI_ENGINE
   /**
    * Invert an index map.
    * The one-to-one index mapping of the first map is inverted and written to
    * the second one.
    *
    * @param aSrcMap is an array with <code>aLength</code> indexes
@@ -912,16 +912,16 @@ private:
   void SetTrailingWSStart();
 
   PRBool GetRuns();
 
   void GetSingleRun(nsBidiLevel aLevel);
 
   void ReorderLine(nsBidiLevel aMinLevel, nsBidiLevel aMaxLevel);
 
-  static PRBool PrepareReorder(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap, nsBidiLevel *aMinLevel, nsBidiLevel *aMaxLevel);
+  PRBool PrepareReorder(const nsBidiLevel *aLevels, PRInt32 aLength, PRInt32 *aIndexMap, nsBidiLevel *aMinLevel, nsBidiLevel *aMaxLevel);
 
   PRInt32 doWriteReverse(const PRUnichar *src, PRInt32 srcLength,
                          PRUnichar *dest, PRUint16 options);
 
 };
 
 #endif // _nsBidi_h_
--- a/layout/base/nsBidiPresUtils.cpp
+++ b/layout/base/nsBidiPresUtils.cpp
@@ -42,220 +42,75 @@
 
 #include "nsBidiPresUtils.h"
 #include "nsTextFragment.h"
 #include "nsGkAtoms.h"
 #include "nsPresContext.h"
 #include "nsRenderingContext.h"
 #include "nsIServiceManager.h"
 #include "nsFrameManager.h"
+#include "nsBidiFrames.h"
 #include "nsBidiUtils.h"
 #include "nsCSSFrameConstructor.h"
 #include "nsHTMLContainerFrame.h"
 #include "nsInlineFrame.h"
 #include "nsPlaceholderFrame.h"
 #include "nsContainerFrame.h"
 #include "nsFirstLetterFrame.h"
 #include "gfxUnicodeProperties.h"
-#include "nsTextFrame.h"
 
 #undef NOISY_BIDI
 #undef REALLY_NOISY_BIDI
 
 using namespace mozilla;
 
 static const PRUnichar kSpace            = 0x0020;
 static const PRUnichar kLineSeparator    = 0x2028;
 static const PRUnichar kObjectSubstitute = 0xFFFC;
 static const PRUnichar kLRE              = 0x202A;
 static const PRUnichar kRLE              = 0x202B;
 static const PRUnichar kLRO              = 0x202D;
 static const PRUnichar kRLO              = 0x202E;
 static const PRUnichar kPDF              = 0x202C;
-
-#define NS_BIDI_CONTROL_FRAME ((nsIFrame*)0xfffb1d1)
-
-struct BidiParagraphData {
-  nsString            mBuffer;
-  nsAutoTArray<PRUnichar, 16> mEmbeddingStack;
-  nsTArray<nsIFrame*> mLogicalFrames;
-  nsDataHashtable<nsISupportsHashKey, PRInt32> mContentToFrameIndex;
-  PRPackedBool        mIsVisual;
-  nsBidiLevel         mParaLevel;
-  nsIContent*         mPrevContent;
-  nsAutoPtr<nsBidi>   mBidiEngine;
-
-  void Init(nsBlockFrame *aBlockFrame)
-  {
-    mContentToFrameIndex.Init();
-    mBidiEngine = new nsBidi();
-    mPrevContent = nsnull;
-    mParaLevel =
-     (NS_STYLE_DIRECTION_RTL == aBlockFrame->GetStyleVisibility()->mDirection) ?
-        NSBIDI_RTL : NSBIDI_LTR;
+static const PRUnichar ALEF              = 0x05D0;
 
-    mIsVisual = aBlockFrame->PresContext()->IsVisualMode();
-    if (mIsVisual) {
-      /**
-       * Drill up in content to detect whether this is an element that needs to
-       * be rendered with logical order even on visual pages.
-       *
-       * We always use logical order on form controls, firstly so that text
-       * entry will be in logical order, but also because visual pages were
-       * written with the assumption that even if the browser had no support
-       * for right-to-left text rendering, it would use native widgets with
-       * bidi support to display form controls.
-       *
-       * We also use logical order in XUL elements, since we expect that if a
-       * XUL element appears in a visual page, it will be generated by an XBL
-       * binding and contain localized text which will be in logical order.
-       */
-      for (nsIContent* content = aBlockFrame->GetContent() ; content; 
-           content = content->GetParent()) {
-        if (content->IsNodeOfType(nsINode::eHTML_FORM_CONTROL) ||
-            content->IsXUL()) {
-          mIsVisual = PR_FALSE;
-          break;
-        }
-      }
-    }
-  }
+#define CHAR_IS_HEBREW(c) ((0x0590 <= (c)) && ((c)<= 0x05FF))
+// Note: The above code are moved from gfx/src/windows/nsRenderingContextWin.cpp
 
-  nsresult SetPara()
-  {
-    return mBidiEngine->SetPara(mBuffer.get(), BufferLength(),
-                                mParaLevel, nsnull);
-  }
-
-  nsresult CountRuns(PRInt32 *runCount){ return mBidiEngine->CountRuns(runCount); }
-
-  nsresult GetLogicalRun(PRInt32 aLogicalStart, 
-                         PRInt32* aLogicalLimit,
-                         nsBidiLevel* aLevel)
-  {
-    nsresult rv = mBidiEngine->GetLogicalRun(aLogicalStart,
-                                             aLogicalLimit, aLevel);
-    if (mIsVisual || NS_FAILED(rv))
-      *aLevel = mParaLevel;
-    return rv;
-  }
-
-  void ResetData()
-  {
-    mLogicalFrames.Clear();
-    mContentToFrameIndex.Clear();
-    mBuffer.SetLength(0);
-    for (PRUint32 i = 0; i < mEmbeddingStack.Length(); ++i) {
-      mBuffer.Append(mEmbeddingStack[i]);
-      mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
-    }
-  }
-
-  void AppendFrame(nsIFrame* aFrame, nsIContent* aContent = nsnull)
-  {
-    if (aContent) {
-      mContentToFrameIndex.Put(aContent, FrameCount());
-    }
-    mLogicalFrames.AppendElement(aFrame);
-  }
+nsIFrame*
+NS_NewDirectionalFrame(nsIPresShell* aPresShell, nsStyleContext* aContext, PRUnichar aChar);
 
-  PRInt32 GetLastFrameForContent(nsIContent *aContent)
-  {
-    PRInt32 index = 0;
-    mContentToFrameIndex.Get(aContent, &index);
-    return index;
+nsBidiPresUtils::nsBidiPresUtils() : mArraySize(8),
+                                     mIndexMap(nsnull),
+                                     mLevels(nsnull),
+                                     mSuccess(NS_ERROR_FAILURE),
+                                     mBidiEngine(nsnull)
+{
+  mBidiEngine = new nsBidi();
+  if (mBidiEngine && mContentToFrameIndex.Init()) {
+    mSuccess = NS_OK;
   }
-
-  PRInt32 FrameCount(){ return mLogicalFrames.Length(); }
-
-  PRInt32 BufferLength(){ return mBuffer.Length(); }
-
-  nsIFrame* FrameAt(PRInt32 aIndex){ return mLogicalFrames[aIndex]; }
-
-  void AppendUnichar(PRUnichar aCh){ mBuffer.Append(aCh); }
-
-  void AppendString(const nsDependentSubstring& aString){ mBuffer.Append(aString); }
-
-  void PushBidiControl(PRUnichar aCh)
-  {
-    mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
-    mBuffer.Append(aCh);
-    mEmbeddingStack.AppendElement(aCh);
-  }
-
-  void PopBidiControl()
-  {
-    mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
-    mBuffer.Append(kPDF);
-    NS_ASSERTION(mEmbeddingStack.Length(), "embedding/override underflow");
-    mEmbeddingStack.TruncateLength(mEmbeddingStack.Length() - 1);
-  }
-
-  void ClearBidiControls()
-  {
-    for (PRUint32 i = 0; i < mEmbeddingStack.Length(); ++i) {
-      mBuffer.Append(kPDF);
-      mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
-    }
-  }
-};
+}
 
-struct BidiLineData {
-  nsTArray<nsIFrame*> mLogicalFrames;
-  nsTArray<nsIFrame*> mVisualFrames;
-  nsTArray<PRInt32> mIndexMap;
-  nsAutoTArray<PRUint8, 18> mLevels;
-  PRBool mIsReordered;
-
-  BidiLineData(nsIFrame* aFirstFrameOnLine, PRInt32   aNumFramesOnLine)
-  {
-    /**
-     * Initialize the logically-ordered array of frames using the top-level
-     * frames of a single line
-     */
-    mLogicalFrames.Clear();
-
-    PRBool isReordered = PR_FALSE;
-    PRBool hasRTLFrames = PR_FALSE;
+nsBidiPresUtils::~nsBidiPresUtils()
+{
+  if (mLevels) {
+    delete[] mLevels;
+  }
+  if (mIndexMap) {
+    delete[] mIndexMap;
+  }
+  delete mBidiEngine;
+}
 
-    for (nsIFrame* frame = aFirstFrameOnLine;
-         frame && aNumFramesOnLine--;
-         frame = frame->GetNextSibling()) {
-      AppendFrame(frame);
-      PRUint8 level = nsBidiPresUtils::GetFrameEmbeddingLevel(frame);
-      mLevels.AppendElement(level);
-      mIndexMap.AppendElement(0);
-      if (level & 1) {
-        hasRTLFrames = PR_TRUE;
-      }
-    }
-
-    // Reorder the line
-    nsBidi::ReorderVisual(mLevels.Elements(), FrameCount(),
-                          mIndexMap.Elements());
-
-    for (PRInt32 i = 0; i < FrameCount(); i++) {
-      mVisualFrames.AppendElement(LogicalFrameAt(mIndexMap[i]));
-      if (i != mIndexMap[i]) {
-        isReordered = PR_TRUE;
-      }
-    }
-
-    // If there's an RTL frame, assume the line is reordered
-    mIsReordered = isReordered || hasRTLFrames;
-  }
-
-  void AppendFrame(nsIFrame* aFrame){ mLogicalFrames.AppendElement(aFrame); }
-
-  PRInt32 FrameCount(){ return mLogicalFrames.Length(); }
-
-  nsIFrame* LogicalFrameAt(PRInt32 aIndex){ return mLogicalFrames[aIndex]; }
-
-  nsIFrame* VisualFrameAt(PRInt32 aIndex){ return mVisualFrames[aIndex]; }
-};
+PRBool
+nsBidiPresUtils::IsSuccessful() const
+{ 
+  return NS_SUCCEEDED(mSuccess); 
+}
 
 /* Some helper methods for Resolve() */
 
 // Should this frame be split between text runs?
 PRBool
 IsBidiSplittable(nsIFrame* aFrame) {
   nsIAtom* frameType = aFrame->GetType();
   // Bidi inline containers should be split, unless they're line frames.
@@ -306,99 +161,87 @@ SplitInlineAncestors(nsIFrame*     aFram
     
     frame = parent;
     parent = grandparent;
   }
   
   return NS_OK;
 }
 
-static void
-MakeContinuationFluid(nsIFrame* aFrame, nsIFrame* aNext)
-{
-  NS_ASSERTION (!aFrame->GetNextInFlow() || aFrame->GetNextInFlow() == aNext, 
-                "next-in-flow is not next continuation!");
-  aFrame->SetNextInFlow(aNext);
-
-  NS_ASSERTION (!aNext->GetPrevInFlow() || aNext->GetPrevInFlow() == aFrame,
-                "prev-in-flow is not prev continuation!");
-  aNext->SetPrevInFlow(aFrame);
-}
-
-// If aFrame is the last child of its parent, convert bidi continuations to
-// fluid continuations for all of its inline ancestors.
+// Convert bidi continuations to fluid continuations for a frame and all of its
+// inline ancestors.
 static void
 JoinInlineAncestors(nsIFrame* aFrame)
 {
-  if (aFrame->GetNextSibling()) {
-    return;
-  }
-  nsIFrame* frame = aFrame->GetParent();
+  nsIFrame* frame = aFrame;
   while (frame && IsBidiSplittable(frame)) {
     nsIFrame* next = frame->GetNextContinuation();
     if (next) {
-      MakeContinuationFluid(frame, next);
+      NS_ASSERTION (!frame->GetNextInFlow() || frame->GetNextInFlow() == next, 
+                    "next-in-flow is not next continuation!");
+      frame->SetNextInFlow(next);
+
+      NS_ASSERTION (!next->GetPrevInFlow() || next->GetPrevInFlow() == frame,
+                    "prev-in-flow is not prev continuation!");
+      next->SetPrevInFlow(frame);
     }
     // Join the parent only as long as we're its last child.
     if (frame->GetNextSibling())
       break;
     frame = frame->GetParent();
   }
 }
 
 static nsresult
-CreateContinuation(nsIFrame*       aFrame,
-                   nsIFrame**      aNewFrame,
-                   PRBool          aIsFluid)
+CreateBidiContinuation(nsIFrame*       aFrame,
+                       nsIFrame**      aNewFrame)
 {
   NS_PRECONDITION(aNewFrame, "null OUT ptr");
   NS_PRECONDITION(aFrame, "null ptr");
 
   *aNewFrame = nsnull;
 
   nsPresContext *presContext = aFrame->PresContext();
   nsIPresShell *presShell = presContext->PresShell();
-  NS_ASSERTION(presShell, "PresShell must be set on PresContext before calling nsBidiPresUtils::CreateContinuation");
+  NS_ASSERTION(presShell, "PresShell must be set on PresContext before calling nsBidiPresUtils::CreateBidiContinuation");
 
   nsIFrame* parent = aFrame->GetParent();
-  NS_ASSERTION(parent, "Couldn't get frame parent in nsBidiPresUtils::CreateContinuation");
+  NS_ASSERTION(parent, "Couldn't get frame parent in nsBidiPresUtils::CreateBidiContinuation");
 
   nsresult rv = NS_OK;
   
   // Have to special case floating first letter frames because the continuation
   // doesn't go in the first letter frame. The continuation goes with the rest
   // of the text that the first letter frame was made out of.
   if (parent->GetType() == nsGkAtoms::letterFrame &&
       parent->GetStyleDisplay()->IsFloating()) {
     nsFirstLetterFrame* letterFrame = do_QueryFrame(parent);
     rv = letterFrame->CreateContinuationForFloatingParent(presContext, aFrame,
-                                                          aNewFrame, aIsFluid);
+                                                          aNewFrame, PR_FALSE);
     return rv;
   }
 
   rv = presShell->FrameConstructor()->
-    CreateContinuingFrame(presContext, aFrame, parent, aNewFrame, aIsFluid);
+    CreateContinuingFrame(presContext, aFrame, parent, aNewFrame, PR_FALSE);
   if (NS_FAILED(rv)) {
     return rv;
   }
 
   // The list name nsGkAtoms::nextBidi would indicate we don't want reflow
   // XXXbz this needs higher-level framelist love
   nsFrameList temp(*aNewFrame, *aNewFrame);
   rv = parent->InsertFrames(nsGkAtoms::nextBidi, aFrame, temp);
   if (NS_FAILED(rv)) {
     return rv;
   }
   
-  if (!aIsFluid) {
-    // Split inline ancestor frames
-    rv = SplitInlineAncestors(aFrame);
-    if (NS_FAILED(rv)) {
-      return rv;
-    }
+  // Split inline ancestor frames
+  rv = SplitInlineAncestors(aFrame);
+  if (NS_FAILED(rv)) {
+    return rv;
   }
 
   return NS_OK;
 }
 
 static PRBool
 IsFrameInCurrentLine(nsBlockInFlowLineIterator* aLineIter,
                      nsIFrame* aPrevFrame, nsIFrame* aFrame)
@@ -439,17 +282,17 @@ AdvanceLineIteratorToFrame(nsIFrame* aFr
   aPrevFrame = child;
 }
 
 /*
  * Overview of the implementation of Resolve():
  *
  *  Walk through the descendants of aBlockFrame and build:
  *   * mLogicalFrames: an nsTArray of nsIFrame* pointers in logical order
- *   * mBuffer: an nsString containing a representation of
+ *   * mBuffer: an nsAutoString containing a representation of
  *     the content of the frames.
  *     In the case of text frames, this is the actual text context of the
  *     frames, but some other elements are represented in a symbolic form which
  *     will make the Unicode Bidi Algorithm give the correct results.
  *     Bidi embeddings and overrides set by CSS or <bdo> elements are
  *     represented by the corresponding Unicode control characters.
  *     <br> elements are represented by U+2028 LINE SEPARATOR
  *     Other inline elements are represented by U+FFFC OBJECT REPLACEMENT
@@ -467,230 +310,260 @@ AdvanceLineIteratorToFrame(nsIFrame* aFr
  *  The rendering layer requires each text frame to contain text in only one
  *  direction, so we may need to call EnsureBidiContinuation() to split frames.
  *  We may also need to call RemoveBidiContinuation() to convert frames created
  *  by EnsureBidiContinuation() in previous reflows into fluid continuations.
  */
 nsresult
 nsBidiPresUtils::Resolve(nsBlockFrame* aBlockFrame)
 {
-  BidiParagraphData bpd;
-  bpd.Init(aBlockFrame);
+  mLogicalFrames.Clear();
+  mContentToFrameIndex.Clear();
+  
+  nsPresContext *presContext = aBlockFrame->PresContext();
+  nsIPresShell* shell = presContext->PresShell();
+  nsStyleContext* styleContext = aBlockFrame->GetStyleContext();
 
   // handle bidi-override being set on the block itself before calling
-  // TraverseFrames.
+  // InitLogicalArray.
+  const nsStyleVisibility* vis = aBlockFrame->GetStyleVisibility();
   const nsStyleTextReset* text = aBlockFrame->GetStyleTextReset();
-  PRUnichar ch = 0;
+
   if (text->mUnicodeBidi == NS_STYLE_UNICODE_BIDI_OVERRIDE) {
-    const nsStyleVisibility* vis = aBlockFrame->GetStyleVisibility();
+    nsIFrame *directionalFrame = nsnull;
+
     if (NS_STYLE_DIRECTION_RTL == vis->mDirection) {
-      ch = kRLO;
+      directionalFrame = NS_NewDirectionalFrame(shell, styleContext, kRLO);
     }
     else if (NS_STYLE_DIRECTION_LTR == vis->mDirection) {
-      ch = kLRO;
+      directionalFrame = NS_NewDirectionalFrame(shell, styleContext, kLRO);
     }
-    if (ch != 0) {
-      bpd.PushBidiControl(ch);
+
+    if (directionalFrame) {
+      mLogicalFrames.AppendElement(directionalFrame);
     }
   }
   for (nsBlockFrame* block = aBlockFrame; block;
        block = static_cast<nsBlockFrame*>(block->GetNextContinuation())) {
     block->RemoveStateBits(NS_BLOCK_NEEDS_BIDI_RESOLUTION);
-    TraverseFrames(aBlockFrame, block->GetFirstChild(nsnull), &bpd);
+    InitLogicalArray(block->GetFirstChild(nsnull));
   }
 
-  if (ch != 0) {
-    bpd.PopBidiControl();
+  if (text->mUnicodeBidi == NS_STYLE_UNICODE_BIDI_OVERRIDE) {
+    nsIFrame* directionalFrame = NS_NewDirectionalFrame(shell, styleContext, kPDF);
+    if (directionalFrame) {
+      mLogicalFrames.AppendElement(directionalFrame);
+    }
   }
 
-  // Resolve final paragraph
-  return ResolveParagraph(aBlockFrame, &bpd);
-}
+  CreateBlockBuffer();
+
+  PRInt32 bufferLength = mBuffer.Length();
 
-nsresult
-nsBidiPresUtils::ResolveParagraph(nsBlockFrame* aBlockFrame,
-                                  BidiParagraphData* aBpd)
-{
-  nsPresContext *presContext = aBlockFrame->PresContext();
+  if (bufferLength < 1) {
+    mSuccess = NS_OK;
+    return mSuccess;
+  }
+  PRInt32 runCount;
+  PRUint8 embeddingLevel;
 
-  if (aBpd->BufferLength() < 1) {
-    return NS_OK;
-  }
-  aBpd->mBuffer.ReplaceChar("\t\r\n", kSpace);
+  nsBidiLevel paraLevel = embeddingLevel =
+    (NS_STYLE_DIRECTION_RTL == vis->mDirection)
+    ? NSBIDI_RTL : NSBIDI_LTR;
 
-  PRInt32 runCount;
-  PRUint8 embeddingLevel = aBpd->mParaLevel;
+  mSuccess = mBidiEngine->SetPara(mBuffer.get(), bufferLength, paraLevel, nsnull);
+  if (NS_FAILED(mSuccess) ) {
+      return mSuccess;
+  }
 
-  nsresult rv = aBpd->SetPara();
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = aBpd->CountRuns(&runCount);
-  NS_ENSURE_SUCCESS(rv, rv);
-
+  mSuccess = mBidiEngine->CountRuns(&runCount);
+  if (NS_FAILED(mSuccess) ) {
+    return mSuccess;
+  }
   PRInt32     runLength      = 0;   // the length of the current run of text
   PRInt32     lineOffset     = 0;   // the start of the current run
   PRInt32     logicalLimit   = 0;   // the end of the current run + 1
   PRInt32     numRun         = -1;
   PRInt32     fragmentLength = 0;   // the length of the current text frame
   PRInt32     frameIndex     = -1;  // index to the frames in mLogicalFrames
-  PRInt32     frameCount     = aBpd->FrameCount();
+  PRInt32     frameCount     = mLogicalFrames.Length();
   PRInt32     contentOffset  = 0;   // offset of current frame in its content node
   PRBool      isTextFrame    = PR_FALSE;
   nsIFrame*   frame = nsnull;
   nsIContent* content = nsnull;
-  PRInt32     contentTextLength = 0;
+  PRInt32     contentTextLength;
+  nsIAtom*    frameType = nsnull;
 
   FramePropertyTable *propTable = presContext->PropertyTable();
-  
-  nsBlockInFlowLineIterator lineIter(aBlockFrame,
-                                     aBlockFrame->begin_lines(),
-                                     PR_FALSE);
+
+  nsBlockInFlowLineIterator lineIter(aBlockFrame, aBlockFrame->begin_lines(), PR_FALSE);
   if (lineIter.GetLine() == aBlockFrame->end_lines()) {
     // Advance to first valid line (might be in a next-continuation)
     lineIter.Next();
   }
   nsIFrame* prevFrame = nsnull;
+  PRBool lineNeedsUpdate = PR_FALSE;
 
-  PRBool lineNeedsUpdate = PR_FALSE;
+  PRBool isVisual = presContext->IsVisualMode();
+  if (isVisual) {
+    /**
+     * Drill up in content to detect whether this is an element that needs to be
+     * rendered with logical order even on visual pages.
+     *
+     * We always use logical order on form controls, firstly so that text entry
+     * will be in logical order, but also because visual pages were written with
+     * the assumption that even if the browser had no support for right-to-left
+     * text rendering, it would use native widgets with bidi support to display
+     * form controls.
+     *
+     * We also use logical order in XUL elements, since we expect that if a XUL
+     * element appears in a visual page, it will be generated by an XBL binding
+     * and contain localized text which will be in logical order.
+     */
+    for (content = aBlockFrame->GetContent() ; content; content = content->GetParent()) {
+      if (content->IsNodeOfType(nsINode::eHTML_FORM_CONTROL) || content->IsXUL()) {
+        isVisual = PR_FALSE;
+        break;
+      }
+    }
+  }
   
 #ifdef DEBUG
 #ifdef NOISY_BIDI
   printf("Before Resolve(), aBlockFrame=0x%p, mBuffer='%s', frameCount=%d\n",
-         (void*)aBlockFrame, NS_ConvertUTF16toUTF8(aBpd->mBuffer).get(), frameCount);
+         (void*)aBlockFrame, NS_ConvertUTF16toUTF8(mBuffer).get(), frameCount);
 #ifdef REALLY_NOISY_BIDI
   printf(" block frame tree=:\n");
   aBlockFrame->List(stdout, 0);
 #endif
 #endif
 #endif
 
   for (; ;) {
     if (fragmentLength <= 0) {
       // Get the next frame from mLogicalFrames
       if (++frameIndex >= frameCount) {
         break;
       }
-      frame = aBpd->FrameAt(frameIndex);
+      frame = mLogicalFrames[frameIndex];
+      frameType = frame->GetType();
       lineNeedsUpdate = PR_TRUE;
-      if (frame == NS_BIDI_CONTROL_FRAME ||
-          nsGkAtoms::textFrame != frame->GetType()) {
-        /*
-         * Any non-text frame corresponds to a single character in the text buffer
-         * (a bidi control character, LINE SEPARATOR, or OBJECT SUBSTITUTE)
-         */
-        isTextFrame = PR_FALSE;
-        fragmentLength = 1;
-      }
-      else {
+      if (nsGkAtoms::textFrame == frameType) {
         content = frame->GetContent();
         if (!content) {
-          rv = NS_OK;
+          mSuccess = NS_OK;
           break;
         }
         contentTextLength = content->TextLength();
         if (contentTextLength == 0) {
           frame->AdjustOffsetsForBidi(0, 0);
           // Set the base level and embedding level of the current run even
           // on an empty frame. Otherwise frame reordering will not be correct.
           propTable->Set(frame, nsIFrame::EmbeddingLevelProperty(),
                          NS_INT32_TO_PTR(embeddingLevel));
           propTable->Set(frame, nsIFrame::BaseLevelProperty(),
-                         NS_INT32_TO_PTR(aBpd->mParaLevel));
+                         NS_INT32_TO_PTR(paraLevel));
           continue;
         }
         PRInt32 start, end;
         frame->GetOffsets(start, end);
         NS_ASSERTION(!(contentTextLength < end - start),
                      "Frame offsets don't fit in content");
         fragmentLength = NS_MIN(contentTextLength, end - start);
         contentOffset = start;
         isTextFrame = PR_TRUE;
       }
+      else {
+        /*
+         * Any non-text frame corresponds to a single character in the text buffer
+         * (a bidi control character, LINE SEPARATOR, or OBJECT SUBSTITUTE)
+         */
+        isTextFrame = PR_FALSE;
+        fragmentLength = 1;
+      }
     } // if (fragmentLength <= 0)
 
     if (runLength <= 0) {
       // Get the next run of text from the Bidi engine
       if (++numRun >= runCount) {
         break;
       }
       lineOffset = logicalLimit;
-      if (NS_FAILED(aBpd->GetLogicalRun(
+      if (NS_FAILED(mBidiEngine->GetLogicalRun(
               lineOffset, &logicalLimit, &embeddingLevel) ) ) {
         break;
       }
       runLength = logicalLimit - lineOffset;
+      if (isVisual) {
+        embeddingLevel = paraLevel;
+      }
     } // if (runLength <= 0)
 
-    if (frame == NS_BIDI_CONTROL_FRAME) {
+    if (nsGkAtoms::directionalFrame == frameType) {
+      frame->Destroy();
       frame = nsnull;
       ++lineOffset;
     }
     else {
       propTable->Set(frame, nsIFrame::EmbeddingLevelProperty(),
                      NS_INT32_TO_PTR(embeddingLevel));
       propTable->Set(frame, nsIFrame::BaseLevelProperty(),
-                     NS_INT32_TO_PTR(aBpd->mParaLevel));
+                     NS_INT32_TO_PTR(paraLevel));
       if (isTextFrame) {
         if ( (runLength > 0) && (runLength < fragmentLength) ) {
           /*
            * The text in this frame continues beyond the end of this directional run.
            * Create a non-fluid continuation frame for the next directional run.
            */
           if (lineNeedsUpdate) {
             AdvanceLineIteratorToFrame(frame, &lineIter, prevFrame);
             lineNeedsUpdate = PR_FALSE;
           }
           lineIter.GetLine()->MarkDirty();
           nsIFrame* nextBidi;
           PRInt32 runEnd = contentOffset + runLength;
-          rv = EnsureBidiContinuation(frame, &nextBidi, frameIndex,
-                                      contentOffset,
-                                      runEnd);
-          if (NS_FAILED(rv)) {
+          EnsureBidiContinuation(frame, &nextBidi, frameIndex,
+                                 contentOffset,
+                                 runEnd);
+          if (NS_FAILED(mSuccess)) {
             break;
           }
           nextBidi->AdjustOffsetsForBidi(runEnd,
                                          contentOffset + fragmentLength);
           frame = nextBidi;
           contentOffset = runEnd;
         } // if (runLength < fragmentLength)
         else {
           if (contentOffset + fragmentLength == contentTextLength) {
             /* 
              * We have finished all the text in this content node. Convert any
              * further non-fluid continuations to fluid continuations and advance
              * frameIndex to the last frame in the content node
              */
-            PRInt32 newIndex = aBpd->GetLastFrameForContent(content);
+            PRInt32 newIndex = 0;
+            mContentToFrameIndex.Get(content, &newIndex);
             if (newIndex > frameIndex) {
-              RemoveBidiContinuation(aBpd, frame, 
-                                     frameIndex, newIndex, lineOffset);
+              RemoveBidiContinuation(frame, frameIndex, newIndex, lineOffset);
               frameIndex = newIndex;
             }
           } else if (fragmentLength > 0 && runLength > fragmentLength) {
             /*
              * There is more text that belongs to this directional run in the next
              * text frame: make sure it is a fluid continuation of the current frame.
              * Do not advance frameIndex, because the next frame may contain
              * multi-directional text and need to be split
              */
             PRInt32 newIndex = frameIndex;
             do {
-            } while (++newIndex < frameCount &&
-                     aBpd->FrameAt(newIndex) == NS_BIDI_CONTROL_FRAME);
-            if (newIndex < frameCount) {
-              RemoveBidiContinuation(aBpd, frame, 
-                                     frameIndex, newIndex, lineOffset);
-            }
-          } else if (runLength == fragmentLength &&
-                     numRun + 1 < runCount) {
+            } while (mLogicalFrames[++newIndex]->GetType() == nsGkAtoms::directionalFrame);
+            RemoveBidiContinuation(frame, frameIndex, newIndex, lineOffset);
+          } else if (runLength == fragmentLength) {
             /*
-             * If the directional run ends at the end of the frame, and this is
-             * not the end of our paragraph, make sure that the next frame is a
-             * non-fluid continuation
+             * The directional run ends at the end of the frame. Make sure that
+             * the next frame is a non-fluid continuation
              */
             nsIFrame* next = frame->GetNextInFlow();
             if (next) {
               frame->SetNextContinuation(next);
               next->SetPrevContinuation(frame);
             }
           }
           frame->AdjustOffsetsForBidi(contentOffset, contentOffset + fragmentLength);
@@ -699,29 +572,29 @@ nsBidiPresUtils::ResolveParagraph(nsBloc
             lineNeedsUpdate = PR_FALSE;
           }
           lineIter.GetLine()->MarkDirty();
         }
       } // isTextFrame
       else {
         ++lineOffset;
       }
-    } // not bidi control frame
+    } // not directionalFrame
     PRInt32 temp = runLength;
     runLength -= fragmentLength;
     fragmentLength -= temp;
 
     if (frame && fragmentLength <= 0) {
-      // If the frame is at the end of a run, and this is not the end of our
-      // paragrah, split all ancestor inlines that need splitting.
+      // If the frame is at the end of a run, split all ancestor inlines that
+      // need splitting.
       // To determine whether we're at the end of the run, we check that we've
       // finished processing the current run, and that the current frame
       // doesn't have a fluid continuation (it could have a fluid continuation
       // of zero length, so testing runLength alone is not sufficient).
-      if (numRun + 1 < runCount && runLength <= 0 && !frame->GetNextInFlow()) {
+      if (runLength <= 0 && !frame->GetNextInFlow()) {
         nsIFrame* child = frame;
         nsIFrame* parent = frame->GetParent();
         // As long as we're on the last sibling, the parent doesn't have to be split.
         // However, if the parent has a fluid continuation, we do have to make
         // it non-fluid. This can happen e.g. when we have a first-letter frame
         // and the end of the first-letter coincides with the end of a
         // directional run.
         while (parent &&
@@ -733,63 +606,55 @@ nsBidiPresUtils::ResolveParagraph(nsBloc
             next->SetPrevContinuation(parent);
           }
           child = parent;
           parent = child->GetParent();
         }
         if (parent && IsBidiSplittable(parent))
           SplitInlineAncestors(child);
       }
-      else {
-        // We're not at an end of a run. If |frame| is the last child of its
-        // parent, and its ancestors happen to have bidi continuations, convert
-        // them into fluid continuations.
-        JoinInlineAncestors(frame);
+      else if (!frame->GetNextSibling()) {
+        // We're not at an end of a run, and |frame| is the last child of its parent.
+        // If its ancestors happen to have bidi continuations, convert them into
+        // fluid continuations.
+        nsIFrame* parent = frame->GetParent();
+        JoinInlineAncestors(parent);
       }
     }
   } // for
 
 #ifdef DEBUG
 #ifdef REALLY_NOISY_BIDI
   printf("---\nAfter Resolve(), frameTree =:\n");
   aBlockFrame->List(stdout, 0);
   printf("===\n");
 #endif
 #endif
 
-  return rv;
+  return mSuccess;
 }
 
 // Should this frame be treated as a leaf (e.g. when building mLogicalFrames)?
 PRBool IsBidiLeaf(nsIFrame* aFrame) {
   nsIFrame* kid = aFrame->GetFirstChild(nsnull);
   return !kid
     || !aFrame->IsFrameOfType(nsIFrame::eBidiInlineContainer);
 }
 
 void
-nsBidiPresUtils::TraverseFrames(nsBlockFrame* aBlockFrame,
-                                nsIFrame*     aCurrentFrame,
-                                BidiParagraphData* aBpd)
+nsBidiPresUtils::InitLogicalArray(nsIFrame*       aCurrentFrame)
 {
   if (!aCurrentFrame)
     return;
 
-  nsIFrame* childFrame = aCurrentFrame;
-  do {
-    /*
-     * It's important to get the next sibling and next continuation *before*
-     * handling the frame: If we encounter a forced paragraph break and call
-     * ResolveParagraph within this loop, doing GetNextSibling and
-     * GetNextContinuation after that could return a bidi continuation that had
-     * just been split from the original childFrame and we would process it
-     * twice.
-     */
-    nsIFrame* nextSibling = childFrame->GetNextSibling();
-    PRBool isLastFrame = !childFrame->GetNextContinuation();
+  nsIPresShell* shell = aCurrentFrame->PresContext()->PresShell();
+  nsStyleContext* styleContext;
+
+  for (nsIFrame* childFrame = aCurrentFrame; childFrame;
+       childFrame = childFrame->GetNextSibling()) {
 
     // If the real frame for a placeholder is a first letter frame, we need to
     // drill down into it and include its contents in Bidi resolution.
     // If not, we just use the placeholder.
     nsIFrame* frame = childFrame;
     if (nsGkAtoms::placeholderFrame == childFrame->GetType()) {
       nsIFrame* realFrame =
         nsPlaceholderFrame::GetRealFrameForPlaceholder(childFrame);
@@ -801,202 +666,205 @@ nsBidiPresUtils::TraverseFrames(nsBlockF
     PRUnichar ch = 0;
     if (frame->IsFrameOfType(nsIFrame::eBidiInlineContainer)) {
       const nsStyleVisibility* vis = frame->GetStyleVisibility();
       const nsStyleTextReset* text = frame->GetStyleTextReset();
       switch (text->mUnicodeBidi) {
         case NS_STYLE_UNICODE_BIDI_NORMAL:
           break;
         case NS_STYLE_UNICODE_BIDI_EMBED:
+          styleContext = frame->GetStyleContext();
+
           if (NS_STYLE_DIRECTION_RTL == vis->mDirection) {
             ch = kRLE;
           }
           else if (NS_STYLE_DIRECTION_LTR == vis->mDirection) {
             ch = kLRE;
           }
           break;
         case NS_STYLE_UNICODE_BIDI_OVERRIDE:
+          styleContext = frame->GetStyleContext();
+
           if (NS_STYLE_DIRECTION_RTL == vis->mDirection) {
             ch = kRLO;
           }
           else if (NS_STYLE_DIRECTION_LTR == vis->mDirection) {
             ch = kLRO;
           }
           break;
       }
 
-      // Add a dummy frame pointer representing a bidi control code before the
-      // first frame of an element specifying embedding or override
+      // Create a directional frame before the first frame of an
+      // element specifying embedding or override
       if (ch != 0 && !frame->GetPrevContinuation()) {
-        aBpd->PushBidiControl(ch);
+        nsIFrame* dirFrame = NS_NewDirectionalFrame(shell, styleContext, ch);
+        if (dirFrame) {
+          mLogicalFrames.AppendElement(dirFrame);
+        }
       }
     }
 
     if (IsBidiLeaf(frame)) {
       /* Bidi leaf frame: add the frame to the mLogicalFrames array,
        * and add its index to the mContentToFrameIndex hashtable. This
        * will be used in RemoveBidiContinuation() to identify the last
        * frame in the array with a given content.
        */
       nsIContent* content = frame->GetContent();
-      aBpd->AppendFrame(frame, content);
-
-      // Append the content of the frame to the paragraph buffer
-      nsIAtom* frameType = frame->GetType();
-      if (nsGkAtoms::textFrame == frameType) {
-        if (content != aBpd->mPrevContent) {
-          aBpd->mPrevContent = content;
-          if (!frame->GetStyleContext()->GetStyleText()->NewlineIsSignificant()) {
-            content->AppendTextTo(aBpd->mBuffer);
-          } else {
-            /*
-             * For preformatted text we have to do bidi resolution on each line
-             * separately. 
-             */
-            nsAutoString text;
-            content->AppendTextTo(text);
-            nsIFrame* next;
-            do {
-              next = nsnull;
-
-              PRInt32 start, end;
-              frame->GetOffsets(start, end);
-              PRInt32 endLine = text.FindCharInSet(NS_LITERAL_STRING("\n\r"),
-                                                   start);
-              if (endLine == -1) {
-                /*
-                 * If there is no newline in the frame, just save the text and
-                 * do bidi resolution later
-                 */
-                aBpd->AppendString(Substring(text, start));
-                break;
-              }
-
-              /*
-               * If there is a newline in the frame, break the frame after the
-               * newline, do bidi resolution and repeat until the end of the
-               * element.
-               */
-              ++endLine;
-
-              /*
-               * If the frame ends before the new line, save the text and move
-               * into the next continuation
-               */
-              while (end < endLine) {
-                aBpd->AppendString(Substring(text, start, end - start));
-                frame = frame->GetNextContinuation();
-                NS_ASSERTION(frame, "Premature end of continuation chain");
-                frame->GetOffsets(start, end);
-                aBpd->AppendFrame(frame);
-
-                /*
-                 * If we have already overshot the saved next-sibling while
-                 * scanning the frame's continuations, advance it.
-                 */
-                if (frame == nextSibling) {
-                  nextSibling = frame->GetNextSibling();
-                }
-              }
-
-              aBpd->AppendString(Substring(text, start, endLine - start));
-
-              if (PRUint32(endLine) < text.Length()) {
-                next = frame->GetNextInFlow();
-                if (!next) {
-                  // If the frame already has a bidi continuation, make it fluid
-                  next = frame->GetNextContinuation();
-                  if (next) {
-                    MakeContinuationFluid(frame, next);
-                    JoinInlineAncestors(frame);
-                  } else {
-                    // If the frame has no next in flow, create one
-                    CreateContinuation(frame, &next, PR_TRUE);
-                  }
-                }
-                nsTextFrame* textFrame = static_cast<nsTextFrame*>(frame);
-                textFrame->SetLength(endLine - start, nsnull);
-              }
-              ResolveParagraphWithinBlock(aBlockFrame, aBpd);
-
-              if (next) {
-                frame = next;
-                aBpd->AppendFrame(frame);
-              }
-
-              /*
-               * If we have already overshot the saved next-sibling while
-               * scanning the frame's continuations, advance it.
-               */
-              if (frame && frame == nextSibling) {
-                nextSibling = frame->GetNextSibling();
-              }
-
-            } while (next);
-          }
-        }
-      } else if (nsGkAtoms::brFrame == frameType) {
-        // break frame -- append line separator
-        aBpd->AppendUnichar(kLineSeparator);
-        ResolveParagraphWithinBlock(aBlockFrame, aBpd);
-      } else { 
-        // other frame type -- see the Unicode Bidi Algorithm:
-        // "...inline objects (such as graphics) are treated as if they are ...
-        // U+FFFC"
-        aBpd->AppendUnichar(kObjectSubstitute);
-        if (!frame->GetStyleContext()->GetStyleDisplay()->IsInlineOutside()) {
-          // if it is not inline, end the paragraph
-          ResolveParagraphWithinBlock(aBlockFrame, aBpd);
-        }
+      if (content) {
+        mContentToFrameIndex.Put(content, mLogicalFrames.Length());
       }
+      mLogicalFrames.AppendElement(frame);
     }
     else {
-      // For a non-leaf frame, recurse into TraverseFrames
       nsIFrame* kid = frame->GetFirstChild(nsnull);
-      TraverseFrames(aBlockFrame, kid, aBpd);
+      InitLogicalArray(kid);
     }
 
     // If the element is attributed by dir, indicate direction pop (add PDF frame)
-    if (ch != 0 && isLastFrame) {
-      // Add a dummy frame pointer representing a bidi control code after the
-      // last frame of an element specifying embedding or override
-      aBpd->PopBidiControl();
+    if (ch != 0 && !frame->GetNextContinuation()) {
+      // Create a directional frame after the last frame of an
+      // element specifying embedding or override
+      nsIFrame* dirFrame = NS_NewDirectionalFrame(shell, styleContext, kPDF);
+      if (dirFrame) {
+        mLogicalFrames.AppendElement(dirFrame);
+      }
     }
-    childFrame = nextSibling;
-  } while (childFrame);
+  } // for
 }
 
 void
-nsBidiPresUtils::ResolveParagraphWithinBlock(nsBlockFrame* aBlockFrame,
-                                             BidiParagraphData* aBpd)
+nsBidiPresUtils::CreateBlockBuffer()
 {
-  aBpd->ClearBidiControls();
+  mBuffer.SetLength(0);
+
+  nsIFrame*                 frame;
+  nsIContent*               prevContent = nsnull;
+  PRUint32                  i;
+  PRUint32                  count = mLogicalFrames.Length();
+
+  for (i = 0; i < count; i++) {
+    frame = mLogicalFrames[i];
+    nsIAtom* frameType = frame->GetType();
 
-  ResolveParagraph(aBlockFrame, aBpd);
-
-  // Clear the frame array and paragraph buffer, and restore the stored 
-  // embeddings and overrides
-  aBpd->ResetData();
+    if (nsGkAtoms::textFrame == frameType) {
+      nsIContent* content = frame->GetContent();
+      if (!content) {
+        mSuccess = NS_OK;
+        break;
+      }
+      if (content == prevContent) {
+        continue;
+      }
+      prevContent = content;
+      content->AppendTextTo(mBuffer);
+    }
+    else if (nsGkAtoms::brFrame == frameType) { // break frame
+      // Append line separator
+      mBuffer.Append(kLineSeparator);
+    }
+    else if (nsGkAtoms::directionalFrame == frameType) {
+      nsDirectionalFrame* dirFrame = static_cast<nsDirectionalFrame*>(frame);
+      mBuffer.Append(dirFrame->GetChar());
+    }
+    else { // not text frame
+      // See the Unicode Bidi Algorithm:
+      // "...inline objects (such as graphics) are treated as if they are ... U+FFFC"
+      mBuffer.Append(kObjectSubstitute);
+    }
+  }
+  // XXX: TODO: Handle preformatted text ('\n')
+  mBuffer.ReplaceChar("\t\r\n", kSpace);
 }
 
 void
 nsBidiPresUtils::ReorderFrames(nsIFrame*            aFirstFrameOnLine,
                                PRInt32              aNumFramesOnLine)
 {
   // If this line consists of a line frame, reorder the line frame's children.
   if (aFirstFrameOnLine->GetType() == nsGkAtoms::lineFrame) {
     aFirstFrameOnLine = aFirstFrameOnLine->GetFirstChild(nsnull);
     if (!aFirstFrameOnLine)
       return;
     // All children of the line frame are on the first line. Setting aNumFramesOnLine
     // to -1 makes InitLogicalArrayFromLine look at all of them.
     aNumFramesOnLine = -1;
   }
-  BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
-  RepositionInlineFrames(&bld, aFirstFrameOnLine);
+
+  InitLogicalArrayFromLine(aFirstFrameOnLine, aNumFramesOnLine);
+
+  PRBool isReordered;
+  PRBool hasRTLFrames;
+  Reorder(isReordered, hasRTLFrames);
+  RepositionInlineFrames(aFirstFrameOnLine);
+}
+
+nsresult
+nsBidiPresUtils::Reorder(PRBool& aReordered, PRBool& aHasRTLFrames)
+{
+  aReordered = PR_FALSE;
+  aHasRTLFrames = PR_FALSE;
+  PRInt32 count = mLogicalFrames.Length();
+
+  if (mArraySize < count) {
+    mArraySize = count << 1;
+    if (mLevels) {
+      delete[] mLevels;
+      mLevels = nsnull;
+    }
+    if (mIndexMap) {
+      delete[] mIndexMap;
+      mIndexMap = nsnull;
+    }
+  }
+  if (!mLevels) {
+    mLevels = new PRUint8[mArraySize];
+    if (!mLevels) {
+      return NS_ERROR_OUT_OF_MEMORY;
+    }
+  }
+  memset(mLevels, 0, sizeof(PRUint8) * mArraySize);
+
+  nsIFrame* frame;
+  PRInt32   i;
+
+  for (i = 0; i < count; i++) {
+    frame = mLogicalFrames[i];
+    mLevels[i] = GetFrameEmbeddingLevel(frame);
+    if (mLevels[i] & 1) {
+      aHasRTLFrames = PR_TRUE;
+    }      
+  }
+  if (!mIndexMap) {
+    mIndexMap = new PRInt32[mArraySize];
+  }
+  if (!mIndexMap) {
+    mSuccess = NS_ERROR_OUT_OF_MEMORY;
+  }
+  else {
+    memset(mIndexMap, 0, sizeof(PRUint32) * mArraySize);
+
+    mSuccess = mBidiEngine->ReorderVisual(mLevels, count, mIndexMap);
+
+    if (NS_SUCCEEDED(mSuccess) ) {
+      mVisualFrames.Clear();
+
+      for (i = 0; i < count; i++) {
+        mVisualFrames.AppendElement(mLogicalFrames[mIndexMap[i]]);
+        if (i != mIndexMap[i]) {
+          aReordered = PR_TRUE;
+        }
+      }
+    } // NS_SUCCEEDED(mSuccess)
+  } // indexMap
+
+  if (NS_FAILED(mSuccess) ) {
+    aReordered = PR_FALSE;
+  }
+  return mSuccess;
 }
 
 nsBidiLevel
 nsBidiPresUtils::GetFrameEmbeddingLevel(nsIFrame* aFrame)
 {
   nsIFrame* firstLeaf = aFrame;
   while (!IsBidiLeaf(firstLeaf)) {
     nsIFrame* firstChild = firstLeaf->GetFirstChild(nsnull);
@@ -1016,17 +884,17 @@ nsBidiPresUtils::GetFrameBaseLevel(nsIFr
   }
   return NS_GET_BASE_LEVEL(firstLeaf);
 }
 
 void
 nsBidiPresUtils::IsLeftOrRightMost(nsIFrame*              aFrame,
                                    nsContinuationStates*  aContinuationStates,
                                    PRBool&                aIsLeftMost /* out */,
-                                   PRBool&                aIsRightMost /* out */)
+                                   PRBool&                aIsRightMost /* out */) const
 {
   const nsStyleVisibility* vis = aFrame->GetStyleVisibility();
   PRBool isLTR = (NS_STYLE_DIRECTION_LTR == vis->mDirection);
 
   /*
    * Since we lay out frames from left to right (in both LTR and RTL), visiting a
    * frame with 'mFirstVisualFrame == nsnull', means it's the first appearance of
    * one of its continuation chain frames on the line.
@@ -1110,17 +978,17 @@ nsBidiPresUtils::IsLeftOrRightMost(nsIFr
   // Reduce number of remaining frames of the continuation chain on the line.
   firstFrameState->mFrameCount--;
 }
 
 void
 nsBidiPresUtils::RepositionFrame(nsIFrame*              aFrame,
                                  PRBool                 aIsOddLevel,
                                  nscoord&               aLeft,
-                                 nsContinuationStates*  aContinuationStates)
+                                 nsContinuationStates*  aContinuationStates) const
 {
   if (!aFrame)
     return;
 
   PRBool isLeftMost, isRightMost;
   IsLeftOrRightMost(aFrame,
                     aContinuationStates,
                     isLeftMost /* out */,
@@ -1195,17 +1063,17 @@ nsBidiPresUtils::RepositionFrame(nsIFram
   aFrame->SetRect(nsRect(start, rect.y, aLeft - start, rect.height));
 
   if (isRightMost)
     aLeft += margin.right;
 }
 
 void
 nsBidiPresUtils::InitContinuationStates(nsIFrame*              aFrame,
-                                        nsContinuationStates*  aContinuationStates)
+                                        nsContinuationStates*  aContinuationStates) const
 {
   nsFrameContinuationState* state = aContinuationStates->PutEntry(aFrame);
   state->mFirstVisualFrame = nsnull;
   state->mFrameCount = 0;
 
   if (!IsBidiLeaf(aFrame)) {
     // Continue for child frames
     nsIFrame* frame;
@@ -1214,161 +1082,189 @@ nsBidiPresUtils::InitContinuationStates(
          frame = frame->GetNextSibling()) {
       InitContinuationStates(frame,
                              aContinuationStates);
     }
   }
 }
 
 void
-nsBidiPresUtils::RepositionInlineFrames(BidiLineData *aBld,
-                                        nsIFrame* aFirstChild)
+nsBidiPresUtils::RepositionInlineFrames(nsIFrame* aFirstChild) const
 {
   const nsStyleVisibility* vis = aFirstChild->GetStyleVisibility();
   PRBool isLTR = (NS_STYLE_DIRECTION_LTR == vis->mDirection);
   nscoord leftSpace = 0;
 
   // This method is called from nsBlockFrame::PlaceLine via the call to
   // bidiUtils->ReorderFrames, so this is guaranteed to be after the inlines
   // have been reflowed, which is required for GetUsedMargin/Border/Padding
   nsMargin margin = aFirstChild->GetUsedMargin();
   if (!aFirstChild->GetPrevContinuation() &&
       !nsLayoutUtils::FrameIsNonFirstInIBSplit(aFirstChild))
     leftSpace = isLTR ? margin.left : margin.right;
 
   nscoord left = aFirstChild->GetPosition().x - leftSpace;
   nsIFrame* frame;
-  PRInt32 count = aBld->mVisualFrames.Length();
+  PRInt32 count = mVisualFrames.Length();
   PRInt32 index;
   nsContinuationStates continuationStates;
 
   continuationStates.Init();
 
   // Initialize continuation states to (nsnull, 0) for
   // each frame on the line.
   for (index = 0; index < count; index++) {
-    InitContinuationStates(aBld->VisualFrameAt(index), &continuationStates);
+    InitContinuationStates(mVisualFrames[index], &continuationStates);
   }
 
   // Reposition frames in visual order
   for (index = 0; index < count; index++) {
-    frame = aBld->VisualFrameAt(index);
+    frame = mVisualFrames[index];
     RepositionFrame(frame,
-                    (aBld->mLevels[aBld->mIndexMap[index]] & 1),
+                    (mLevels[mIndexMap[index]] & 1),
                     left,
                     &continuationStates);
   } // for
 }
 
+void 
+nsBidiPresUtils::InitLogicalArrayFromLine(nsIFrame* aFirstFrameOnLine,
+                                          PRInt32   aNumFramesOnLine) {
+  mLogicalFrames.Clear();
+  for (nsIFrame* frame = aFirstFrameOnLine;
+       frame && aNumFramesOnLine--;
+       frame = frame->GetNextSibling()) {
+    mLogicalFrames.AppendElement(frame);
+  }
+}
+
 PRBool
 nsBidiPresUtils::CheckLineOrder(nsIFrame*  aFirstFrameOnLine,
                                 PRInt32    aNumFramesOnLine,
                                 nsIFrame** aFirstVisual,
                                 nsIFrame** aLastVisual)
 {
-  BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
-  PRInt32 count = bld.FrameCount();
+  InitLogicalArrayFromLine(aFirstFrameOnLine, aNumFramesOnLine);
+  
+  PRBool isReordered;
+  PRBool hasRTLFrames;
+  Reorder(isReordered, hasRTLFrames);
+  PRInt32 count = mLogicalFrames.Length();
   
   if (aFirstVisual) {
-    *aFirstVisual = bld.VisualFrameAt(0);
+    *aFirstVisual = mVisualFrames[0];
   }
   if (aLastVisual) {
-    *aLastVisual = bld.VisualFrameAt(count-1);
+    *aLastVisual = mVisualFrames[count-1];
   }
   
-  return bld.mIsReordered;
+  // If there's an RTL frame, assume the line is reordered
+  return isReordered || hasRTLFrames;
 }
 
 nsIFrame*
 nsBidiPresUtils::GetFrameToRightOf(const nsIFrame*  aFrame,
                                    nsIFrame*        aFirstFrameOnLine,
                                    PRInt32          aNumFramesOnLine)
 {
-  BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
-
-  PRInt32 count = bld.mVisualFrames.Length();
+  InitLogicalArrayFromLine(aFirstFrameOnLine, aNumFramesOnLine);
+  
+  PRBool isReordered;
+  PRBool hasRTLFrames;
+  Reorder(isReordered, hasRTLFrames);
+  PRInt32 count = mVisualFrames.Length();
 
   if (aFrame == nsnull)
-    return bld.VisualFrameAt(0);
+    return mVisualFrames[0];
   
   for (PRInt32 i = 0; i < count - 1; i++) {
-    if (bld.VisualFrameAt(i) == aFrame) {
-      return bld.VisualFrameAt(i+1);
+    if (mVisualFrames[i] == aFrame) {
+      return mVisualFrames[i+1];
     }
   }
   
   return nsnull;
 }
 
 nsIFrame*
 nsBidiPresUtils::GetFrameToLeftOf(const nsIFrame*  aFrame,
                                   nsIFrame*        aFirstFrameOnLine,
                                   PRInt32          aNumFramesOnLine)
 {
-  BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
-
-  PRInt32 count = bld.mVisualFrames.Length();
+  InitLogicalArrayFromLine(aFirstFrameOnLine, aNumFramesOnLine);
+  
+  PRBool isReordered;
+  PRBool hasRTLFrames;
+  Reorder(isReordered, hasRTLFrames);
+  PRInt32 count = mVisualFrames.Length();
   
   if (aFrame == nsnull)
-    return bld.VisualFrameAt(count-1);
+    return mVisualFrames[count-1];
   
   for (PRInt32 i = 1; i < count; i++) {
-    if (bld.VisualFrameAt(i) == aFrame) {
-      return bld.VisualFrameAt(i-1);
+    if (mVisualFrames[i] == aFrame) {
+      return mVisualFrames[i-1];
     }
   }
   
   return nsnull;
 }
 
-inline nsresult
+inline void
 nsBidiPresUtils::EnsureBidiContinuation(nsIFrame*       aFrame,
                                         nsIFrame**      aNewFrame,
                                         PRInt32&        aFrameIndex,
                                         PRInt32         aStart,
                                         PRInt32         aEnd)
 {
   NS_PRECONDITION(aNewFrame, "null OUT ptr");
   NS_PRECONDITION(aFrame, "aFrame is null");
 
   aFrame->AdjustOffsetsForBidi(aStart, aEnd);
-  return CreateContinuation(aFrame, aNewFrame, PR_FALSE);
+  mSuccess = CreateBidiContinuation(aFrame, aNewFrame);
 }
 
 void
-nsBidiPresUtils::RemoveBidiContinuation(BidiParagraphData *aBpd,
-                                        nsIFrame*       aFrame,
+nsBidiPresUtils::RemoveBidiContinuation(nsIFrame*       aFrame,
                                         PRInt32         aFirstIndex,
                                         PRInt32         aLastIndex,
-                                        PRInt32&        aOffset)
+                                        PRInt32&        aOffset) const
 {
   FrameProperties props = aFrame->Properties();
   nsBidiLevel embeddingLevel =
     (nsBidiLevel)NS_PTR_TO_INT32(props.Get(nsIFrame::EmbeddingLevelProperty()));
   nsBidiLevel baseLevel =
     (nsBidiLevel)NS_PTR_TO_INT32(props.Get(nsIFrame::BaseLevelProperty()));
 
   for (PRInt32 index = aFirstIndex + 1; index <= aLastIndex; index++) {
-    nsIFrame* frame = aBpd->FrameAt(index);
-    if (frame == NS_BIDI_CONTROL_FRAME) {
+    nsIFrame* frame = mLogicalFrames[index];
+    if (nsGkAtoms::directionalFrame == frame->GetType()) {
+      frame->Destroy();
       ++aOffset;
     }
     else {
       // Make the frame and its continuation ancestors fluid,
       // so they can be reused or deleted by normal reflow code
       FrameProperties frameProps = frame->Properties();
       frameProps.Set(nsIFrame::EmbeddingLevelProperty(),
                      NS_INT32_TO_PTR(embeddingLevel));
       frameProps.Set(nsIFrame::BaseLevelProperty(),
                      NS_INT32_TO_PTR(baseLevel));
       frame->AddStateBits(NS_FRAME_IS_BIDI);
       while (frame) {
         nsIFrame* prev = frame->GetPrevContinuation();
         if (prev) {
-          MakeContinuationFluid(prev, frame);
+          NS_ASSERTION (!frame->GetPrevInFlow() || frame->GetPrevInFlow() == prev, 
+                        "prev-in-flow is not prev continuation!");
+          frame->SetPrevInFlow(prev);
+
+          NS_ASSERTION (!prev->GetNextInFlow() || prev->GetNextInFlow() == frame,
+                        "next-in-flow is not next continuation!");
+          prev->SetNextInFlow(frame);
+
           frame = frame->GetParent();
         } else {
           break;
         }
       }
     }
   }
 }
@@ -1436,17 +1332,17 @@ nsBidiPresUtils::FormatUnicodeText(nsPre
   }
 
   StripBidiControlCharacters(aText, aTextLength);
   return rv;
 }
 
 void
 nsBidiPresUtils::StripBidiControlCharacters(PRUnichar* aText,
-                                            PRInt32&   aTextLength)
+                                            PRInt32&   aTextLength) const
 {
   if ( (nsnull == aText) || (aTextLength < 1) ) {
     return;
   }
 
   PRInt32 stripLen = 0;
 
   for (PRInt32 i = 0; i < aTextLength; i++) {
@@ -1479,45 +1375,43 @@ RemoveDiacritics(PRUnichar* aText,
     }
     aTextLength = i - offset;
     aText[aTextLength] = 0;
   }
 }
 #endif
 
 void
-nsBidiPresUtils::CalculateCharType(nsBidi* aBidiEngine,
-                                   const PRUnichar* aText,
-                                   PRInt32& aOffset,
+nsBidiPresUtils::CalculateCharType(PRInt32& aOffset,
                                    PRInt32  aCharTypeLimit,
                                    PRInt32& aRunLimit,
                                    PRInt32& aRunLength,
                                    PRInt32& aRunCount,
                                    PRUint8& aCharType,
-                                   PRUint8& aPrevCharType)
+                                   PRUint8& aPrevCharType) const
 
 {
   PRBool     strongTypeFound = PR_FALSE;
   PRInt32    offset;
   nsCharType charType;
 
   aCharType = eCharType_OtherNeutral;
 
   for (offset = aOffset; offset < aCharTypeLimit; offset++) {
     // Make sure we give RTL chartype to all characters that would be classified
     // as Right-To-Left by a bidi platform.
     // (May differ from the UnicodeData, eg we set RTL chartype to some NSMs.)
-    if (IS_HEBREW_CHAR(aText[offset]) ) {
+    if (IS_HEBREW_CHAR(mBuffer[offset]) ) {
       charType = eCharType_RightToLeft;
     }
-    else if (IS_ARABIC_ALPHABETIC(aText[offset]) ) {
+    else if (IS_ARABIC_ALPHABETIC(mBuffer[offset]) ) {
       charType = eCharType_RightToLeftArabic;
     }
     else {
-      aBidiEngine->GetCharTypeAt(offset, &charType);
+      mBidiEngine->GetCharTypeAt(offset, &charType);
     }
 
     if (!CHARTYPE_IS_WEAK(charType) ) {
 
       if (strongTypeFound
           && (charType != aPrevCharType)
           && (CHARTYPE_IS_RTL(charType) || CHARTYPE_IS_RTL(aPrevCharType) ) ) {
         // Stop at this point to ensure uni-directionality of the text
@@ -1550,55 +1444,54 @@ nsBidiPresUtils::CalculateCharType(nsBid
 nsresult nsBidiPresUtils::ProcessText(const PRUnichar*       aText,
                                       PRInt32                aLength,
                                       nsBidiDirection        aBaseDirection,
                                       nsPresContext*         aPresContext,
                                       BidiProcessor&         aprocessor,
                                       Mode                   aMode,
                                       nsBidiPositionResolve* aPosResolve,
                                       PRInt32                aPosResolveCount,
-                                      nscoord*               aWidth,
-                                      nsBidi*                aBidiEngine)
+                                      nscoord*               aWidth)
 {
   NS_ASSERTION((aPosResolve == nsnull) != (aPosResolveCount > 0), "Incorrect aPosResolve / aPosResolveCount arguments");
 
   PRInt32 runCount;
 
-  nsAutoString textBuffer(aText, aLength);
+  mBuffer.Assign(aText, aLength);
 
-  nsresult rv = aBidiEngine->SetPara(aText, aLength, aBaseDirection, nsnull);
+  nsresult rv = mBidiEngine->SetPara(mBuffer.get(), aLength, aBaseDirection, nsnull);
   if (NS_FAILED(rv))
     return rv;
 
-  rv = aBidiEngine->CountRuns(&runCount);
+  rv = mBidiEngine->CountRuns(&runCount);
   if (NS_FAILED(rv))
     return rv;
 
   nscoord xOffset = 0;
-  nscoord width, xEndRun = 0;
+  nscoord width, xEndRun;
   nscoord totalWidth = 0;
   PRInt32 i, start, limit, length;
   PRUint32 visualStart = 0;
   PRUint8 charType;
   PRUint8 prevType = eCharType_LeftToRight;
   nsBidiLevel level;
       
   for(int nPosResolve=0; nPosResolve < aPosResolveCount; ++nPosResolve)
   {
     aPosResolve[nPosResolve].visualIndex = kNotFound;
     aPosResolve[nPosResolve].visualLeftTwips = kNotFound;
     aPosResolve[nPosResolve].visualWidth = kNotFound;
   }
 
   for (i = 0; i < runCount; i++) {
-    rv = aBidiEngine->GetVisualRun(i, &start, &length, &aBaseDirection);
+    rv = mBidiEngine->GetVisualRun(i, &start, &length, &aBaseDirection);
     if (NS_FAILED(rv))
       return rv;
 
-    rv = aBidiEngine->GetLogicalRun(start, &limit, &level);
+    rv = mBidiEngine->GetLogicalRun(start, &limit, &level);
     if (NS_FAILED(rv))
       return rv;
 
     PRInt32 subRunLength = limit - start;
     PRInt32 lineOffset = start;
     PRInt32 typeLimit = NS_MIN(limit, aLength);
     PRInt32 subRunCount = 1;
     PRInt32 subRunLimit = typeLimit;
@@ -1620,17 +1513,17 @@ nsresult nsBidiPresUtils::ProcessText(co
       width = aprocessor.GetWidth();
       xOffset += width;
       xEndRun = xOffset;
     }
 
     while (subRunCount > 0) {
       // CalculateCharType can increment subRunCount if the run
       // contains mixed character types
-      CalculateCharType(aBidiEngine, aText, lineOffset, typeLimit, subRunLimit, subRunLength, subRunCount, charType, prevType);
+      CalculateCharType(lineOffset, typeLimit, subRunLimit, subRunLength, subRunCount, charType, prevType);
       
       nsAutoString runVisualText;
       runVisualText.Assign(aText + start, subRunLength);
       if (PRInt32(runVisualText.Length()) < subRunLength)
         return NS_ERROR_OUT_OF_MEMORY;
       FormatUnicodeText(aPresContext, runVisualText.BeginWriting(), subRunLength,
                         (nsCharType)charType, level & 1);
 
@@ -1806,19 +1699,19 @@ nsresult nsBidiPresUtils::ProcessTextFor
                                                          Mode                   aMode,
                                                          nscoord                aX,
                                                          nscoord                aY,
                                                          nsBidiPositionResolve* aPosResolve,
                                                          PRInt32                aPosResolveCount,
                                                          nscoord*               aWidth)
 {
   nsIRenderingContextBidiProcessor processor(&aRenderingContext, &aTextRunConstructionContext, nsPoint(aX, aY));
-  nsBidi bidiEngine;
+
   return ProcessText(aText, aLength, aBaseDirection, aPresContext, processor,
-                     aMode, aPosResolve, aPosResolveCount, aWidth, &bidiEngine);
+                     aMode, aPosResolve, aPosResolveCount, aWidth);
 }
 
 /* static */
 void nsBidiPresUtils::WriteReverse(const PRUnichar* aSrc,
                                    PRUint32 aSrcLength,
                                    PRUnichar* aDest)
 {
   const PRUnichar* src = aSrc + aSrcLength;
@@ -1930,23 +1823,55 @@ void nsBidiPresUtils::CopyLogicalToVisua
       // no need to use the converter -- just copy the string in reverse order
       WriteReverse(fromBegin.get(), srcLength, toBegin.get());
     } else {
       // if aOverride && aBaseDirection == NSBIDI_LTR, fall through to the
       // simple copy
       aDest.SetLength(0);
     }
   } else {
-    nsBidi bidiEngine;
     if (!WriteLogicalToVisual(fromBegin.get(), srcLength, toBegin.get(),
-                             aBaseDirection, &bidiEngine)) {
+                             aBaseDirection, mBidiEngine)) {
       aDest.SetLength(0);
     }
   }
 
   if (aDest.IsEmpty()) {
     // Either there was an error or the source is unidirectional
     //  left-to-right. In either case, just copy source to dest.
     CopyUnicodeTo(aSource.BeginReading(fromBegin), aSource.EndReading(fromEnd),
                   aDest);
   }
 }
+
+PRUint32 nsBidiPresUtils::EstimateMemoryUsed()
+{
+  PRUint32 size = 0;
+
+  size += sizeof(nsBidiPresUtils);
+  size += mBuffer.Length() * sizeof(PRUnichar);
+  size += moz_malloc_usable_size(mBidiEngine->mDirPropsMemory);
+  size += moz_malloc_usable_size(mBidiEngine->mLevelsMemory);
+  size += moz_malloc_usable_size(mBidiEngine->mRunsMemory);
+
+  return size;
+}
+
+static PLDHashOperator
+TraverseKey(nsISupports *aKey, PRInt32 aData, void *aUserArg)
+{
+  nsCycleCollectionTraversalCallback *cb =
+    static_cast<nsCycleCollectionTraversalCallback*>(aUserArg);
+  NS_CYCLE_COLLECTION_NOTE_EDGE_NAME(*cb, "mContentToFrameIndex key");
+  cb->NoteXPCOMChild(aKey);
+  return PL_DHASH_NEXT;
+}
+
+void nsBidiPresUtils::Traverse(nsCycleCollectionTraversalCallback &cb) const
+{
+  mContentToFrameIndex.EnumerateRead(TraverseKey, &cb);
+}
+
+void nsBidiPresUtils::Unlink()
+{
+  mContentToFrameIndex.Clear();
+}
 #endif // IBMBIDI
--- a/layout/base/nsBidiPresUtils.h
+++ b/layout/base/nsBidiPresUtils.h
@@ -50,19 +50,16 @@
 #include "nsDataHashtable.h"
 #include "nsBlockFrame.h"
 #include "nsTHashtable.h"
 
 #ifdef DrawText
 #undef DrawText
 #endif
 
-struct BidiParagraphData;
-struct BidiLineData;
-
 /**
  * A structure representing some continuation state for each frame on the line,
  * used to determine the first and the last continuation frame for each
  * continuation chain on the line.
  */
 struct nsFrameContinuationState : public nsVoidPtrHashKey
 {
   nsFrameContinuationState(const void *aFrame) : nsVoidPtrHashKey(aFrame) {}
@@ -172,43 +169,39 @@ public:
   /**
    * Make Bidi engine calculate the embedding levels of the frames that are
    * descendants of a given block frame.
    *
    * @param aBlockFrame          The block frame
    *
    *  @lina 06/18/2000
    */
-  static nsresult Resolve(nsBlockFrame* aBlockFrame);
-  static nsresult ResolveParagraph(nsBlockFrame* aBlockFrame,
-                                   BidiParagraphData* aBpd);
-  static void ResolveParagraphWithinBlock(nsBlockFrame* aBlockFrame,
-                                          BidiParagraphData* aBpd);
+  nsresult Resolve(nsBlockFrame* aBlockFrame);
 
   /**
    * Reorder this line using Bidi engine.
    * Update frame array, following the new visual sequence.
    * 
    * @lina 05/02/2000
    */
-  static void ReorderFrames(nsIFrame*            aFirstFrameOnLine,
-                            PRInt32              aNumFramesOnLine);
+  void ReorderFrames(nsIFrame*            aFirstFrameOnLine,
+                     PRInt32              aNumFramesOnLine);
 
   /**
    * Format Unicode text, taking into account bidi capabilities
    * of the platform. The formatting includes: reordering, Arabic shaping,
    * symmetric and numeric swapping, removing control characters.
    *
    * @lina 06/18/2000 
    */
-  static nsresult FormatUnicodeText(nsPresContext* aPresContext,
-                                    PRUnichar*      aText,
-                                    PRInt32&        aTextLength,
-                                    nsCharType      aCharType,
-                                    PRBool          aIsOddLevel);
+  nsresult FormatUnicodeText(nsPresContext* aPresContext,
+                             PRUnichar*      aText,
+                             PRInt32&        aTextLength,
+                             nsCharType      aCharType,
+                             PRBool          aIsOddLevel);
 
   /**
    * Reorder plain text using the Unicode Bidi algorithm and send it to
    * a rendering context for rendering.
    *
    * @param[in] aText  the string to be rendered (in logical order)
    * @param aLength the number of characters in the string
    * @param aBaseDirection the base direction of the string
@@ -217,78 +210,78 @@ public:
    * @param aPresContext the presentation context
    * @param aRenderingContext the rendering context to render to
    * @param aTextRunConstructionContext the rendering context to be used to construct the textrun (affects font hinting)
    * @param aX the x-coordinate to render the string
    * @param aY the y-coordinate to render the string
    * @param[in,out] aPosResolve array of logical positions to resolve into visual positions; can be nsnull if this functionality is not required
    * @param aPosResolveCount number of items in the aPosResolve array
    */
-  static nsresult RenderText(const PRUnichar*       aText,
-                             PRInt32                aLength,
-                             nsBidiDirection        aBaseDirection,
-                             nsPresContext*         aPresContext,
-                             nsRenderingContext&    aRenderingContext,
-                             nsRenderingContext&    aTextRunConstructionContext,
-                             nscoord                aX,
-                             nscoord                aY,
-                             nsBidiPositionResolve* aPosResolve = nsnull,
-                             PRInt32                aPosResolveCount = 0)
+  nsresult RenderText(const PRUnichar*       aText,
+                      PRInt32                aLength,
+                      nsBidiDirection        aBaseDirection,
+                      nsPresContext*         aPresContext,
+                      nsRenderingContext&    aRenderingContext,
+                      nsRenderingContext&    aTextRunConstructionContext,
+                      nscoord                aX,
+                      nscoord                aY,
+                      nsBidiPositionResolve* aPosResolve = nsnull,
+                      PRInt32                aPosResolveCount = 0)
   {
     return ProcessTextForRenderingContext(aText, aLength, aBaseDirection, aPresContext, aRenderingContext,
                                           aTextRunConstructionContext, MODE_DRAW, aX, aY, aPosResolve, aPosResolveCount, nsnull);
   }
   
-  static nscoord MeasureTextWidth(const PRUnichar*     aText,
-                                  PRInt32              aLength,
-                                  nsBidiDirection      aBaseDirection,
-                                  nsPresContext*       aPresContext,
-                                  nsRenderingContext&  aRenderingContext)
+  nscoord MeasureTextWidth(const PRUnichar*     aText,
+                           PRInt32              aLength,
+                           nsBidiDirection      aBaseDirection,
+                           nsPresContext*       aPresContext,
+                           nsRenderingContext&  aRenderingContext)
   {
     nscoord length;
     nsresult rv = ProcessTextForRenderingContext(aText, aLength, aBaseDirection, aPresContext,
                                                  aRenderingContext, aRenderingContext,
                                                  MODE_MEASURE, 0, 0, nsnull, 0, &length);
     return NS_SUCCEEDED(rv) ? length : 0;
   }
 
   /**
    * Check if a line is reordered, i.e., if the child frames are not
    * all laid out left-to-right.
    * @param aFirstFrameOnLine : first frame of the line to be tested
    * @param aNumFramesOnLine : number of frames on this line
    * @param[out] aLeftMost : leftmost frame on this line
    * @param[out] aRightMost : rightmost frame on this line
    */
-  static PRBool CheckLineOrder(nsIFrame*  aFirstFrameOnLine,
-                               PRInt32    aNumFramesOnLine,
-                               nsIFrame** aLeftmost,
-                               nsIFrame** aRightmost);
+  PRBool CheckLineOrder(nsIFrame*  aFirstFrameOnLine,
+                        PRInt32    aNumFramesOnLine,
+                        nsIFrame** aLeftmost,
+                        nsIFrame** aRightmost);
 
   /**
    * Get the frame to the right of the given frame, on the same line.
    * @param aFrame : We're looking for the frame to the right of this frame.
    *                 If null, return the leftmost frame on the line.
    * @param aFirstFrameOnLine : first frame of the line to be tested
    * @param aNumFramesOnLine : number of frames on this line
    */
-  static nsIFrame* GetFrameToRightOf(const nsIFrame*  aFrame,
-                                     nsIFrame*        aFirstFrameOnLine,
-                                     PRInt32          aNumFramesOnLine);
+  nsIFrame* GetFrameToRightOf(const nsIFrame*  aFrame,
+                              nsIFrame*        aFirstFrameOnLine,
+                              PRInt32          aNumFramesOnLine);
     
   /**
    * Get the frame to the left of the given frame, on the same line.
    * @param aFrame : We're looking for the frame to the left of this frame.
    *                 If null, return the rightmost frame on the line.
    * @param aFirstFrameOnLine : first frame of the line to be tested
    * @param aNumFramesOnLine : number of frames on this line
    */
-  static nsIFrame* GetFrameToLeftOf(const nsIFrame*  aFrame,
-                                    nsIFrame*        aFirstFrameOnLine,
-                                    PRInt32          aNumFramesOnLine);
+  nsIFrame* GetFrameToLeftOf(const nsIFrame*  aFrame,
+                             nsIFrame*        aFirstFrameOnLine,
+                             PRInt32          aNumFramesOnLine);
     
   /**
    * Get the bidi embedding level of the given (inline) frame.
    */
   static nsBidiLevel GetFrameEmbeddingLevel(nsIFrame* aFrame);
 
   /**
    * Get the bidi base level of the given (inline) frame.
@@ -312,150 +305,177 @@ public:
    *  MODE_DRAW - invokes DrawText on the processor for each substring
    *  MODE_MEASURE - does not invoke DrawText on the processor
    *  Note that the string is always measured, regardless of mode
    * @param[in,out] aPosResolve array of logical positions to resolve into
    *  visual positions; can be nsnull if this functionality is not required
    * @param aPosResolveCount number of items in the aPosResolve array
    * @param[out] aWidth Pointer to where the width will be stored (may be null)
    */
-  static nsresult ProcessText(const PRUnichar*       aText,
-                              PRInt32                aLength,
-                              nsBidiDirection        aBaseDirection,
-                              nsPresContext*         aPresContext,
-                              BidiProcessor&         aprocessor,
-                              Mode                   aMode,
-                              nsBidiPositionResolve* aPosResolve,
-                              PRInt32                aPosResolveCount,
-                              nscoord*               aWidth,
-                              nsBidi*                aBidiEngine);
+  nsresult ProcessText(const PRUnichar*       aText,
+                       PRInt32                aLength,
+                       nsBidiDirection        aBaseDirection,
+                       nsPresContext*         aPresContext,
+                       BidiProcessor&         aprocessor,
+                       Mode                   aMode,
+                       nsBidiPositionResolve* aPosResolve,
+                       PRInt32                aPosResolveCount,
+                       nscoord*               aWidth);
 
   /**
    * Make a copy of a string, converting from logical to visual order
    *
    * @param aSource the source string
    * @param aDest the destination string
    * @param aBaseDirection the base direction of the string
    *       (NSBIDI_LTR or NSBIDI_RTL to force the base direction;
    *        NSBIDI_DEFAULT_LTR or NSBIDI_DEFAULT_RTL to let the bidi engine
    *        determine the direction from rules P2 and P3 of the bidi algorithm.
    *  @see nsBidi::GetPara
    * @param aOverride if TRUE, the text has a bidi override, according to
    *                    the direction in aDir
    */
-  static void CopyLogicalToVisual(const nsAString& aSource,
-                                  nsAString& aDest,
-                                  nsBidiLevel aBaseDirection,
-                                  PRBool aOverride);
+  void CopyLogicalToVisual(const nsAString& aSource,
+                           nsAString& aDest,
+                           nsBidiLevel aBaseDirection,
+                           PRBool aOverride);
+
+  /**
+   * Guess at how much memory is being used by this nsBidiPresUtils instance,
+   * including memory used by nsBidi.
+   */
+  PRUint32 EstimateMemoryUsed();
+
+  void Traverse(nsCycleCollectionTraversalCallback &cb) const;
+  void Unlink();
 
 private:
-  static nsresult ProcessTextForRenderingContext(const PRUnichar*       aText,
-                                                 PRInt32                aLength,
-                                                 nsBidiDirection        aBaseDirection,
-                                                 nsPresContext*         aPresContext,
-                                                 nsRenderingContext&    aRenderingContext,
-                                                 nsRenderingContext&    aTextRunConstructionContext,
-                                                 Mode                   aMode,
-                                                 nscoord                aX, // DRAW only
-                                                 nscoord                aY, // DRAW only
-                                                 nsBidiPositionResolve* aPosResolve,  /* may be null */
-                                                 PRInt32                aPosResolveCount,
-                                                 nscoord*               aWidth /* may be null */);
+  nsresult ProcessTextForRenderingContext(const PRUnichar*       aText,
+                                          PRInt32                aLength,
+                                          nsBidiDirection        aBaseDirection,
+                                          nsPresContext*         aPresContext,
+                                          nsRenderingContext&    aRenderingContext,
+                                          nsRenderingContext&    aTextRunConstructionContext,
+                                          Mode                   aMode,
+                                          nscoord                aX, // DRAW only
+                                          nscoord                aY, // DRAW only
+                                          nsBidiPositionResolve* aPosResolve,  /* may be null */
+                                          PRInt32                aPosResolveCount,
+                                          nscoord*               aWidth /* may be null */);
+
+  /**
+   *  Create a string containing entire text content of this block.
+   *
+   *  @lina 05/02/2000
+   */
+  void CreateBlockBuffer();
 
   /**
-   * Traverse the child frames of the block element and:
-   *  Set up an array of the frames in logical order
-   *  Create a string containing the text content of all the frames
-   *  If we encounter content that requires us to split the element into more
-   *  than one paragraph for bidi resolution, resolve the paragraph up to that
-   *  point.
+   * Set up an array of the frames after splitting frames so that each frame has
+   * consistent directionality. At this point the frames are still in logical
+   * order
+   */
+  void InitLogicalArray(nsIFrame* aCurrentFrame);
+
+  /**
+   * Initialize the logically-ordered array of frames
+   * using the top-level frames of a single line
    */
-  static void TraverseFrames(nsBlockFrame* aBlockFrame, nsIFrame* aCurrentFrame,
-                            BidiParagraphData *aBpd);
+  void InitLogicalArrayFromLine(nsIFrame* aFirstFrameOnLine,
+                                PRInt32   aNumFramesOnLine);
+
+  /**
+   * Reorder the frame array from logical to visual order
+   * 
+   * @param aReordered TRUE on return if the visual order is different from
+   *                   the logical order
+   * @param aHasRTLFrames TRUE on return if at least one of the frames is RTL
+   *                      (and therefore might have reordered descendents)
+   */
+  nsresult Reorder(PRBool& aReordered, PRBool& aHasRTLFrames);
   
   /*
    * Position aFrame and it's descendants to their visual places. Also if aFrame
    * is not leaf, resize it to embrace it's children.
    *
    * @param aFrame               The frame which itself and its children are going
    *                             to be repositioned
    * @param aIsOddLevel          TRUE means the embedding level of this frame is odd
    * @param[in,out] aLeft        IN value is the starting position of aFrame(without
    *                             considering its left margin)
    *                             OUT value will be the ending position of aFrame(after
    *                             adding its right margin)
    * @param aContinuationStates  A map from nsIFrame* to nsFrameContinuationState
    */
-  static void RepositionFrame(nsIFrame*              aFrame,
-                              PRBool                 aIsOddLevel,
-                              nscoord&               aLeft,
-                              nsContinuationStates*  aContinuationStates);
+  void RepositionFrame(nsIFrame*              aFrame,
+                       PRBool                 aIsOddLevel,
+                       nscoord&               aLeft,
+                       nsContinuationStates*  aContinuationStates) const;
 
   /*
    * Initialize the continuation state(nsFrameContinuationState) to
    * (nsnull, 0) for aFrame and its descendants.
    *
    * @param aFrame               The frame which itself and its descendants will
    *                             be initialized
    * @param aContinuationStates  A map from nsIFrame* to nsFrameContinuationState
    */
-  static void InitContinuationStates(nsIFrame*              aFrame,
-                                     nsContinuationStates*  aContinuationStates);
+  void InitContinuationStates(nsIFrame*              aFrame,
+                              nsContinuationStates*  aContinuationStates) const;
 
   /*
    * Determine if aFrame is leftmost or rightmost, and set aIsLeftMost and
    * aIsRightMost values. Also set continuation states of aContinuationStates.
    *
    * A frame is leftmost if it's the first appearance of its continuation chain
    * on the line and the chain is on its first line if it's LTR or the chain is
    * on its last line if it's RTL.
    * A frame is rightmost if it's the last appearance of its continuation chain
    * on the line and the chain is on its first line if it's RTL or the chain is
    * on its last line if it's LTR.
    *
    * @param aContinuationStates  A map from nsIFrame* to nsFrameContinuationState
    * @param[out] aIsLeftMost     TRUE means aFrame is leftmost frame or continuation
    * @param[out] aIsRightMost    TRUE means aFrame is rightmost frame or continuation
    */
-   static void IsLeftOrRightMost(nsIFrame*              aFrame,
-                                 nsContinuationStates*  aContinuationStates,
-                                 PRBool&                aIsLeftMost /* out */,
-                                 PRBool&                aIsRightMost /* out */);
+   void IsLeftOrRightMost(nsIFrame*              aFrame,
+                          nsContinuationStates*  aContinuationStates,
+                          PRBool&                aIsLeftMost /* out */,
+                          PRBool&                aIsRightMost /* out */) const;
 
   /**
    *  Adjust frame positions following their visual order
    *
    *  @param aFirstChild the first kid
    *
    *  @lina 04/11/2000
    */
-  static void RepositionInlineFrames(BidiLineData *aBld,
-                                     nsIFrame* aFirstChild);
+  void RepositionInlineFrames(nsIFrame* aFirstChild) const;
   
   /**
    * Helper method for Resolve()
    * Truncate a text frame to the end of a single-directional run and possibly
    * create a continuation frame for the remainder of its content.
    *
    * @param aFrame       the original frame
    * @param aNewFrame    [OUT] the new frame that was created
    * @param aFrameIndex  [IN/OUT] index of aFrame in mLogicalFrames
    * @param aStart       [IN] the start of the content mapped by aFrame (and 
    *                          any fluid continuations)
    * @param aEnd         [IN] the offset of the end of the single-directional
    *                          text run.
    * @see Resolve()
    * @see RemoveBidiContinuation()
    */
-  static inline
-  nsresult EnsureBidiContinuation(nsIFrame*       aFrame,
-                                  nsIFrame**      aNewFrame,
-                                  PRInt32&        aFrameIndex,
-                                  PRInt32         aStart,
-                                  PRInt32         aEnd);
+  inline
+  void EnsureBidiContinuation(nsIFrame*       aFrame,
+                              nsIFrame**      aNewFrame,
+                              PRInt32&        aFrameIndex,
+                              PRInt32         aStart,
+                              PRInt32         aEnd);
 
   /**
    * Helper method for Resolve()
    * Convert one or more bidi continuation frames created in a previous reflow by
    * EnsureBidiContinuation() into fluid continuations.
    * @param aFrame       the frame whose continuations are to be removed
    * @param aFirstIndex  index of aFrame in mLogicalFrames
    * @param aLastIndex   index of the last frame to be removed
@@ -463,40 +483,48 @@ private:
    *                     directional frames have control characters
    *                     corresponding to them in mBuffer, the pointers to
    *                     mBuffer in Resolve() will need to be updated after
    *                     deleting the frames.
    *
    * @see Resolve()
    * @see EnsureBidiContinuation()
    */
-  static void RemoveBidiContinuation(BidiParagraphData* aBpd,
-                                     nsIFrame*       aFrame,
-                                     PRInt32         aFirstIndex,
-                                     PRInt32         aLastIndex,
-                                     PRInt32&        aOffset);
-  static void CalculateCharType(nsBidi* aBidiEngine,
-                                const PRUnichar* aText,
-                                PRInt32& aOffset,
-                                PRInt32  aCharTypeLimit,
-                                PRInt32& aRunLimit,
-                                PRInt32& aRunLength,
-                                PRInt32& aRunCount,
-                                PRUint8& aCharType,
-                                PRUint8& aPrevCharType);
+  void RemoveBidiContinuation(nsIFrame*       aFrame,
+                              PRInt32         aFirstIndex,
+                              PRInt32         aLastIndex,
+                              PRInt32&        aOffset) const;
+  void CalculateCharType(PRInt32& aOffset,
+                         PRInt32  aCharTypeLimit,
+                         PRInt32& aRunLimit,
+                         PRInt32& aRunLength,
+                         PRInt32& aRunCount,
+                         PRUint8& aCharType,
+                         PRUint8& aPrevCharType) const;
   
-  static void StripBidiControlCharacters(PRUnichar* aText,
-                                         PRInt32&   aTextLength);
+  void StripBidiControlCharacters(PRUnichar* aText,
+                                  PRInt32&   aTextLength) const;
 
   static PRBool WriteLogicalToVisual(const PRUnichar* aSrc,
                                      PRUint32 aSrcLength,
                                      PRUnichar* aDest,
                                      nsBidiLevel aBaseDirection,
                                      nsBidi* aBidiEngine);
 
-  static void WriteReverse(const PRUnichar* aSrc,
-                           PRUint32 aSrcLength,
-                           PRUnichar* aDest);
+ static void WriteReverse(const PRUnichar* aSrc,
+                          PRUint32 aSrcLength,
+                          PRUnichar* aDest);
+
+  nsAutoString    mBuffer;
+  nsTArray<nsIFrame*> mLogicalFrames;
+  nsTArray<nsIFrame*> mVisualFrames;
+  nsDataHashtable<nsISupportsHashKey, PRInt32> mContentToFrameIndex;
+  PRInt32         mArraySize;
+  PRInt32*        mIndexMap;
+  PRUint8*        mLevels;
+  nsresult        mSuccess;
+
+  nsBidi*         mBidiEngine;
 };
 
 #endif /* nsBidiPresUtils_h___ */
 
 #endif // IBMBIDI
--- a/layout/base/nsLayoutUtils.cpp
+++ b/layout/base/nsLayoutUtils.cpp
@@ -2793,25 +2793,29 @@ nsLayoutUtils::DrawString(const nsIFrame
                           PRInt32              aLength,
                           nsPoint              aPoint,
                           PRUint8              aDirection)
 {
 #ifdef IBMBIDI
   nsresult rv = NS_ERROR_FAILURE;
   nsPresContext* presContext = aFrame->PresContext();
   if (presContext->BidiEnabled()) {
-    if (aDirection == NS_STYLE_DIRECTION_INHERIT) {
-      aDirection = aFrame->GetStyleVisibility()->mDirection;
+    nsBidiPresUtils* bidiUtils = presContext->GetBidiUtils();
+
+    if (bidiUtils) {
+      if (aDirection == NS_STYLE_DIRECTION_INHERIT) {
+        aDirection = aFrame->GetStyleVisibility()->mDirection;
+      }
+      nsBidiDirection direction =
+        (NS_STYLE_DIRECTION_RTL == aDirection) ?
+        NSBIDI_RTL : NSBIDI_LTR;
+      rv = bidiUtils->RenderText(aString, aLength, direction,
+                                 presContext, *aContext, *aContext,
+                                 aPoint.x, aPoint.y);
     }
-    nsBidiDirection direction =
-      (NS_STYLE_DIRECTION_RTL == aDirection) ?
-      NSBIDI_RTL : NSBIDI_LTR;
-    rv = nsBidiPresUtils::RenderText(aString, aLength, direction,
-                                     presContext, *aContext, *aContext,
-                                     aPoint.x, aPoint.y);
   }
   if (NS_FAILED(rv))
 #endif // IBMBIDI
   {
     aContext->SetTextRunRTL(PR_FALSE);
     aContext->DrawString(aString, aLength, aPoint.x, aPoint.y);
   }
 }
@@ -2820,22 +2824,26 @@ nscoord
 nsLayoutUtils::GetStringWidth(const nsIFrame*      aFrame,
                               nsRenderingContext* aContext,
                               const PRUnichar*     aString,
                               PRInt32              aLength)
 {
 #ifdef IBMBIDI
   nsPresContext* presContext = aFrame->PresContext();
   if (presContext->BidiEnabled()) {
-    const nsStyleVisibility* vis = aFrame->GetStyleVisibility();
-    nsBidiDirection direction =
-      (NS_STYLE_DIRECTION_RTL == vis->mDirection) ?
-      NSBIDI_RTL : NSBIDI_LTR;
-    return nsBidiPresUtils::MeasureTextWidth(aString, aLength,
-                                             direction, presContext, *aContext);
+    nsBidiPresUtils* bidiUtils = presContext->GetBidiUtils();
+
+    if (bidiUtils) {
+      const nsStyleVisibility* vis = aFrame->GetStyleVisibility();
+      nsBidiDirection direction =
+        (NS_STYLE_DIRECTION_RTL == vis->mDirection) ?
+        NSBIDI_RTL : NSBIDI_LTR;
+      return bidiUtils->MeasureTextWidth(aString, aLength,
+                                         direction, presContext, *aContext);
+    }
   }
 #endif // IBMBIDI
   aContext->SetTextRunRTL(PR_FALSE);
   return aContext->GetWidth(aString, aLength);
 }
 
 /* static */ nscoord
 nsLayoutUtils::GetCenteredFontBaseline(nsFontMetrics* aFontMetrics,
--- a/layout/base/nsPresContext.cpp
+++ b/layout/base/nsPresContext.cpp
@@ -361,16 +361,18 @@ NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN(
 
   for (PRUint32 i = 0; i < IMAGE_LOAD_TYPE_COUNT; ++i)
     tmp->mImageLoaders[i].Enumerate(TraverseImageLoader, &cb);
 
   // NS_IMPL_CYCLE_COLLECTION_TRAVERSE_NSCOMPTR(mTheme); // a service
   // NS_IMPL_CYCLE_COLLECTION_TRAVERSE_NSCOMPTR(mLangService); // a service
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE_NSCOMPTR(mPrintSettings);
   NS_IMPL_CYCLE_COLLECTION_TRAVERSE_NSCOMPTR(mPrefChangedTimer);
+  if (tmp->mBidiUtils)
+    tmp->mBidiUtils->Traverse(cb);
 NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
 
 NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(nsPresContext)
   NS_IMPL_CYCLE_COLLECTION_UNLINK_NSCOMPTR(mDocument);
   NS_RELEASE(tmp->mDeviceContext); // worth bothering?
   if (tmp->mEventManager) {
     // unclear if these are needed, but can't hurt
     tmp->mEventManager->NotifyDestroyPresContext(tmp);
@@ -385,16 +387,18 @@ NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(ns
   // NS_IMPL_CYCLE_COLLECTION_UNLINK_NSCOMPTR(mTheme); // a service
   // NS_IMPL_CYCLE_COLLECTION_UNLINK_NSCOMPTR(mLangService); // a service
   NS_IMPL_CYCLE_COLLECTION_UNLINK_NSCOMPTR(mPrintSettings);
   if (tmp->mPrefChangedTimer)
   {
     tmp->mPrefChangedTimer->Cancel();
     tmp->mPrefChangedTimer = nsnull;
   }
+  if (tmp->mBidiUtils)
+    tmp->mBidiUtils->Unlink();
 NS_IMPL_CYCLE_COLLECTION_UNLINK_END
 
 
 #define MAKE_FONT_PREF_KEY(_pref, _s0, _s1) \
  _pref.Assign(_s0); \
  _pref.Append(_s1);
 
 static const char* const kGenericFont[] = {
@@ -1468,16 +1472,25 @@ nsPresContext::SetBidiEnabled() const
   if (mShell) {
     nsIDocument *doc = mShell->GetDocument();
     if (doc) {
       doc->SetBidiEnabled();
     }
   }
 }
 
+nsBidiPresUtils*
+nsPresContext::GetBidiUtils()
+{
+  if (!mBidiUtils)
+    mBidiUtils = new nsBidiPresUtils;
+
+  return mBidiUtils;
+}
+
 void
 nsPresContext::SetBidi(PRUint32 aSource, PRBool aForceRestyle)
 {
   // Don't do all this stuff unless the options have changed.
   if (aSource == GetBidi()) {
     return;
   }
 
@@ -1510,16 +1523,25 @@ nsPresContext::SetBidi(PRUint32 aSource,
 }
 
 PRUint32
 nsPresContext::GetBidi() const
 {
   return Document()->GetBidiOptions();
 }
 
+PRUint32
+nsPresContext::GetBidiMemoryUsed()
+{
+  if (!mBidiUtils)
+    return 0;
+
+  return mBidiUtils->EstimateMemoryUsed();
+}
+
 #endif //IBMBIDI
 
 PRBool
 nsPresContext::IsTopLevelWindowInactive()
 {
   nsCOMPtr<nsIDocShellTreeItem> treeItem(do_QueryReferent(mContainer));
   if (!treeItem)
     return PR_FALSE;
--- a/layout/base/nsPresContext.h
+++ b/layout/base/nsPresContext.h
@@ -756,27 +756,36 @@ public:
    *
    *  @lina 05/02/2000
    */
   PRBool IsVisualMode() const { return mIsVisual; }
 
 //Mohamed
 
   /**
+   * Get a Bidi presentation utilities object
+   */
+  NS_HIDDEN_(nsBidiPresUtils*) GetBidiUtils();
+
+  /**
    * Set the Bidi options for the presentation context
    */  
   NS_HIDDEN_(void) SetBidi(PRUint32 aBidiOptions,
                            PRBool aForceRestyle = PR_FALSE);
 
   /**
    * Get the Bidi options for the presentation context
    * Not inline so consumers of nsPresContext are not forced to
    * include nsIDocument.
    */  
   NS_HIDDEN_(PRUint32) GetBidi() const;
+
+  PRUint32 GetBidiMemoryUsed();
+#else
+  PRUint32 GetBidiMemoryUsed() { return 0; }
 #endif // IBMBIDI
 
   /**
    * Render only Selection
    */
   void SetIsRenderingOnlySelection(PRBool aResult)
   {
     NS_ASSERTION(!(aResult & ~1), "Value must be true or false");
@@ -999,16 +1008,17 @@ public:
 
   PRBool MayHaveFixedBackgroundFrames() { return mMayHaveFixedBackgroundFrames; }
   void SetHasFixedBackgroundFrame() { mMayHaveFixedBackgroundFrames = PR_TRUE; }
 
   PRUint32 EstimateMemoryUsed() {
     PRUint32 result = 0;
 
     result += sizeof(nsPresContext);
+    result += GetBidiMemoryUsed();
 
     return result;
   }
 
   PRBool IsRootContentDocument();
 
 protected:
   friend class nsRunnableMethod<nsPresContext>;
@@ -1089,16 +1099,20 @@ protected:
 
   PRInt32               mMinFontSize;   // Min font size, defaults to 0
   float                 mTextZoom;      // Text zoom, defaults to 1.0
   float                 mFullZoom;      // Page zoom, defaults to 1.0
 
   PRInt32               mCurAppUnitsPerDevPixel;
   PRInt32               mAutoQualityMinFontSizePixelsPref;
 
+#ifdef IBMBIDI
+  nsAutoPtr<nsBidiPresUtils> mBidiUtils;
+#endif
+
   nsCOMPtr<nsITheme> mTheme;
   nsCOMPtr<nsILanguageAtomService> mLangService;
   nsCOMPtr<nsIPrintSettings> mPrintSettings;
   nsCOMPtr<nsITimer>    mPrefChangedTimer;
 
   FramePropertyTable    mPropertyTable;
 
   nsInvalidateRequestList mInvalidateRequests;
--- a/layout/base/nsPresShell.cpp
+++ b/layout/base/nsPresShell.cpp
@@ -1405,29 +1405,42 @@ public:
   {
     PresShell *aShell = static_cast<PresShell*>(aEntry->GetKey());
     PRUint32 *val = (PRUint32*)userArg;
     *val += aShell->EstimateMemoryUsed();
     *val += aShell->mPresContext->EstimateMemoryUsed();
     return PL_DHASH_NEXT;
   }
 
+  static PLDHashOperator LiveShellBidiSizeEnumerator(PresShellPtrKey *aEntry,
+                                                     void *userArg)
+  {
+    PresShell *aShell = static_cast<PresShell*>(aEntry->GetKey());
+    PRUint32 *val = (PRUint32*)userArg;
+    *val += aShell->mPresContext->GetBidiMemoryUsed();
+    return PL_DHASH_NEXT;
+  }
+
   static PRUint32
   EstimateShellsMemory(nsTHashtable<PresShellPtrKey>::Enumerator aEnumerator)
   {
     PRUint32 result = 0;
     sLiveShells->EnumerateEntries(aEnumerator, &result);
     return result;
   }
                   
                                   
   static PRInt64 SizeOfLayoutMemoryReporter(void *) {
     return EstimateShellsMemory(LiveShellSizeEnumerator);
   }
 
+  static PRInt64 SizeOfBidiMemoryReporter(void *) {
+    return EstimateShellsMemory(LiveShellBidiSizeEnumerator);
+  }
+
 protected:
   void QueryIsActive();
   nsresult UpdateImageLockingState();
 };
 
 class nsAutoCauseReflowNotifier
 {
 public:
@@ -1633,16 +1646,22 @@ NS_NewPresShell(nsIPresShell** aInstance
 nsTHashtable<PresShell::PresShellPtrKey> *nsIPresShell::sLiveShells = 0;
 
 NS_MEMORY_REPORTER_IMPLEMENT(LayoutPresShell,
                              "layout/all",
                              "Memory in use by layout PresShell, PresContext, and other related areas.",
                              PresShell::SizeOfLayoutMemoryReporter,
                              nsnull)
 
+NS_MEMORY_REPORTER_IMPLEMENT(LayoutBidi,
+                             "layout/bidi",
+                             "Memory in use by layout Bidi processor.",
+                             PresShell::SizeOfBidiMemoryReporter,
+                             nsnull)
+
 PresShell::PresShell()
 {
   mSelection = nsnull;
 #ifdef MOZ_REFLOW_PERF
   mReflowCountMgr = new ReflowCountMgr();
   mReflowCountMgr->SetPresContext(mPresContext);
   mReflowCountMgr->SetPresShell(this);
 #endif
@@ -1660,16 +1679,17 @@ PresShell::PresShell()
   mRenderFlags = 0;
   mXResolution = 1.0;
   mYResolution = 1.0;
   mViewportOverridden = PR_FALSE;
 
   static bool registeredReporter = false;
   if (!registeredReporter) {
     NS_RegisterMemoryReporter(new NS_MEMORY_REPORTER_NAME(LayoutPresShell));
+    NS_RegisterMemoryReporter(new NS_MEMORY_REPORTER_NAME(LayoutBidi));
     registeredReporter = true;
   }
 
   new (this) nsFrameManager();
 
   sLiveShells->PutEntry(this);
 }
 
--- a/layout/base/tests/Makefile.in
+++ b/layout/base/tests/Makefile.in
@@ -324,17 +324,16 @@ ifeq (,$(filter windows,$(MOZ_WIDGET_TOO
 		test_bug570378-persian-5e.html \
 		test_bug570378-persian-5f.html \
 		test_bug570378-persian-5g.html \
 		bug570378-persian-5.html \
 		bug570378-persian-5-ref.html \
 		test_bug588174.html \
 		test_bug607529.html \
 		file_bug607529.html \
-		test_bug644768.html \
 		$(NULL)
 endif
 
 _BROWSER_FILES = \
 	browser_bug617076.js \
 	$(NULL)
 
 libs:: $(_TEST_FILES)
deleted file mode 100644
--- a/layout/base/tests/test_bug644768.html
+++ /dev/null
@@ -1,59 +0,0 @@
-<!DOCTYPE HTML>
-<html>
-<!--
-https://bugzilla.mozilla.org/show_bug.cgi?id=644768
--->
-<head>
-  <title>Test for Bug 644768</title>
-  <script type="text/javascript" src="/MochiKit/packed.js"></script>
-  <script type="text/javascript" src="/tests/SimpleTest/SimpleTest.js"></script>
-  <script type="text/javascript" src="/tests/SimpleTest/WindowSnapshot.js"></script>
-  <script type="application/javascript" src="/tests/SimpleTest/EventUtils.js"></script>
-  <link rel="stylesheet" type="text/css" href="/tests/SimpleTest/test.css" />
-</head>
-<body onload="test()">
-<a target="_blank" href="https://bugzilla.mozilla.org/show_bug.cgi?id=644768">Mozilla Bug 644768</a>
-<p id="display"></p>
-<div id="content">
-<!-- test text is 
-== زادروزها ==
-* [[۱۳۰۷]]
--->
- <textarea id="testInput" dir="rtl" cols="80" rows="25">
-
-== &#x0632;&#x0627;&#x062F;&#x0631;&#x0648;&#x0632;&#x0647;&#x0627; ==
-* [[&#x06F1;&#x06F3;&#x06F0;&#x06F7;]]</textarea>
-</div>
-<pre id="test">
-<script class="testbody" type="text/javascript">
-
-/** Test for Bug 644768 **/
-
-SimpleTest.waitForExplicitFinish();
-
-function test() {
-  var textInput = $("testInput");
-  var s1, s2, equal, str1, str2;
-
-  textInput.focus();
-  s1 = snapshotWindow(window);
-
-  synthesizeKey("VK_UP", { });
-  synthesizeKey("VK_UP", { });
-  synthesizeKey("VK_UP", { });
-  synthesizeKey("VK_DELETE", { });
-  synthesizeKey("VK_ENTER", { });
-  s2 = snapshotWindow(window);
-
-  [equal, str1, str2] = compareSnapshots(s1, s2, true);
-  ok(equal, "newline before bidi text shouldn't change direction: expected " +
-     str1 + " but got " + str2);
-
-  SimpleTest.finish();
-}
-
-</script>
-</pre>
-</body>
-</html>
-
--- a/layout/generic/Makefile.in
+++ b/layout/generic/Makefile.in
@@ -66,16 +66,23 @@ EXPORTS		= \
 		nsIObjectFrame.h \
 		nsIPageSequenceFrame.h \
 		nsIScrollableFrame.h \
 		nsIStatefulFrame.h \
 		nsFrameSelection.h \
 		nsSubDocumentFrame.h \
 		$(NULL)
 
+ifdef IBMBIDI
+EXPORTS		+= \
+		nsBidiFrames.h      \
+		$(NULL)
+endif
+
+
 CPPSRCS		= \
 		nsAbsoluteContainingBlock.cpp \
 		nsBRFrame.cpp \
 		nsBlockFrame.cpp \
 		nsBlockReflowContext.cpp \
 		nsBlockReflowState.cpp \
 		nsBulletFrame.cpp \
 		nsColumnSetFrame.cpp \
@@ -114,16 +121,22 @@ CPPSRCS		= \
 		$(NULL)
 
 ifdef MOZ_MEDIA
 CPPSRCS		+= \
 		nsVideoFrame.cpp \
 		$(NULL)
 endif
 
+ifdef IBMBIDI
+CPPSRCS		+= \
+		nsBidiFrames.cpp \
+		$(NULL)
+endif
+
 ifeq (cocoa,$(MOZ_WIDGET_TOOLKIT))
 CMMSRCS		+= \
 		nsPluginUtilsOSX.mm \
 		$(NULL)
 endif
 
 RESOURCES_HTML = \
 		$(srcdir)/folder.png \
new file mode 100644
--- /dev/null
+++ b/layout/generic/nsBidiFrames.cpp
@@ -0,0 +1,76 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * IBM Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2000
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifdef IBMBIDI
+
+#include "nsBidiFrames.h"
+#include "nsGkAtoms.h"
+
+
+nsDirectionalFrame::nsDirectionalFrame(nsStyleContext* aContext, PRUnichar aChar)
+  : nsFrame(aContext), mChar(aChar)
+{
+}
+
+nsDirectionalFrame::~nsDirectionalFrame()
+{
+}
+
+nsIAtom*
+nsDirectionalFrame::GetType() const
+{ 
+  return nsGkAtoms::directionalFrame;
+}
+  
+#ifdef NS_DEBUG
+NS_IMETHODIMP
+nsDirectionalFrame::GetFrameName(nsAString& aResult) const
+{
+  return MakeFrameName(NS_LITERAL_STRING("Directional"), aResult);
+}
+#endif
+
+nsIFrame*
+NS_NewDirectionalFrame(nsIPresShell* aPresShell, nsStyleContext* aContext, PRUnichar aChar)
+{
+  return new (aPresShell) nsDirectionalFrame(aContext, aChar);
+}
+
+NS_IMPL_FRAMEARENA_HELPERS(nsDirectionalFrame)
+
+#endif /* IBMBIDI */
new file mode 100644
--- /dev/null
+++ b/layout/generic/nsBidiFrames.h
@@ -0,0 +1,76 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is mozilla.org code.
+ *
+ * The Initial Developer of the Original Code is
+ * IBM Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2000
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifdef IBMBIDI
+
+#ifndef nsBidiFrames_h___
+#define nsBidiFrames_h___
+
+#include "nsFrame.h"
+
+
+class nsDirectionalFrame : public nsFrame
+{
+protected:
+  virtual ~nsDirectionalFrame();
+
+public:
+  NS_DECL_FRAMEARENA_HELPERS
+
+  nsDirectionalFrame(nsStyleContext* aContext, PRUnichar aChar);
+
+  /**
+   * Get the "type" of the frame
+   *
+   * @see nsGkAtoms::directionalFrame
+   */
+  virtual nsIAtom* GetType() const;
+
+  PRUnichar GetChar() const { return mChar; }
+
+#ifdef NS_DEBUG
+  NS_IMETHOD GetFrameName(nsAString& aResult) const;
+#endif
+
+private:
+  PRUnichar mChar;
+};
+
+
+#endif /* nsBidiFrames_h___ */
+#endif /* IBMBIDI */
--- a/layout/generic/nsBlockFrame.cpp
+++ b/layout/generic/nsBlockFrame.cpp
@@ -4234,17 +4234,21 @@ nsBlockFrame::PlaceLine(nsBlockReflowSta
   // RelativePositionFrames!!!
   // XXXldb Is something here considering relatively positioned frames at
   // other than their original positions?
 #ifdef IBMBIDI
   // XXXldb Why don't we do this earlier?
   if (aState.mPresContext->BidiEnabled()) {
     if (!aState.mPresContext->IsVisualMode() ||
         GetStyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL) {
-      nsBidiPresUtils::ReorderFrames(aLine->mFirstChild, aLine->GetChildCount());
+      nsBidiPresUtils* bidiUtils = aState.mPresContext->GetBidiUtils();
+
+      if (bidiUtils && bidiUtils->IsSuccessful() ) {
+        bidiUtils->ReorderFrames(aLine->mFirstChild, aLine->GetChildCount());
+      } // bidiUtils
     } // not visual mode
   } // bidi enabled
 #endif // IBMBIDI
 
   // From here on, pfd->mBounds rectangles are incorrect because bidi
   // might have moved frames around!
   nsOverflowAreas overflowAreas;
   aLineLayout.RelativePositionFrames(overflowAreas);
@@ -7170,17 +7174,21 @@ nsBlockFrame::ResolveBidi()
   NS_ASSERTION(!GetPrevInFlow(),
                "ResolveBidi called on non-first continuation");
 
   nsPresContext* presContext = PresContext();
   if (!presContext->BidiEnabled()) {
     return NS_OK;
   }
 
-  return nsBidiPresUtils::Resolve(this);
+  nsBidiPresUtils* bidiUtils = presContext->GetBidiUtils();
+  if (!bidiUtils)
+    return NS_ERROR_NULL_POINTER;
+
+  return bidiUtils->Resolve(this);
 }
 #endif
 
 #ifdef DEBUG
 void
 nsBlockFrame::VerifyLines(PRBool aFinalCheckOK)
 {
   if (!gVerifyLines) {
--- a/layout/generic/nsFrameList.cpp
+++ b/layout/generic/nsFrameList.cpp
@@ -447,26 +447,27 @@ nsFrameList::GetPrevVisualFor(nsIFrame* 
   if (!mFirstChild)
     return nsnull;
   
   nsIFrame* parent = mFirstChild->GetParent();
   if (!parent)
     return aFrame ? aFrame->GetPrevSibling() : LastChild();
 
   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);  
+  nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
 
   nsAutoLineIterator iter = parent->GetLineIterator();
   if (!iter) { 
     // Parent is not a block Frame
     if (parent->GetType() == nsGkAtoms::lineFrame) {
       // Line frames are not bidi-splittable, so need to consider bidi reordering
       if (baseLevel == NSBIDI_LTR) {
-        return nsBidiPresUtils::GetFrameToLeftOf(aFrame, mFirstChild, -1);
+        return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
       } else { // RTL
-        return nsBidiPresUtils::GetFrameToRightOf(aFrame, mFirstChild, -1);
+        return bidiUtils->GetFrameToRightOf(aFrame, mFirstChild, -1);
       }
     } else {
       // Just get the next or prev sibling, depending on block and frame direction.
       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
         return aFrame ? aFrame->GetPrevSibling() : LastChild();
       } else {
         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
@@ -491,56 +492,57 @@ nsFrameList::GetPrevVisualFor(nsIFrame* 
   PRInt32 numFramesOnLine;
   nsRect lineBounds;
   PRUint32 lineFlags;
 
   if (aFrame) {
     iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 
     if (baseLevel == NSBIDI_LTR) {
-      frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
     } else { // RTL
-      frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
     }
   }
 
   if (!frame && thisLine > 0) {
     // Get the last frame of the previous line
     iter->GetLine(thisLine - 1, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
 
     if (baseLevel == NSBIDI_LTR) {
-      frame = nsBidiPresUtils::GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
     } else { // RTL
-      frame = nsBidiPresUtils::GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
     }
   }
   return frame;
 }
 
 nsIFrame*
 nsFrameList::GetNextVisualFor(nsIFrame* aFrame) const
 {
   if (!mFirstChild)
     return nsnull;
   
   nsIFrame* parent = mFirstChild->GetParent();
   if (!parent)
     return aFrame ? aFrame->GetPrevSibling() : mFirstChild;
 
   nsBidiLevel baseLevel = nsBidiPresUtils::GetFrameBaseLevel(mFirstChild);
+  nsBidiPresUtils* bidiUtils = mFirstChild->PresContext()->GetBidiUtils();
   
   nsAutoLineIterator iter = parent->GetLineIterator();
   if (!iter) { 
     // Parent is not a block Frame
     if (parent->GetType() == nsGkAtoms::lineFrame) {
       // Line frames are not bidi-splittable, so need to consider bidi reordering
       if (baseLevel == NSBIDI_LTR) {
-        return nsBidiPresUtils::GetFrameToRightOf(aFrame, mFirstChild, -1);
+        return bidiUtils->GetFrameToRightOf(aFrame, mFirstChild, -1);
       } else { // RTL
-        return nsBidiPresUtils::GetFrameToLeftOf(aFrame, mFirstChild, -1);
+        return bidiUtils->GetFrameToLeftOf(aFrame, mFirstChild, -1);
       }
     } else {
       // Just get the next or prev sibling, depending on block and frame direction.
       nsBidiLevel frameEmbeddingLevel = nsBidiPresUtils::GetFrameEmbeddingLevel(mFirstChild);
       if ((frameEmbeddingLevel & 1) == (baseLevel & 1)) {
         return aFrame ? aFrame->GetNextSibling() : mFirstChild;
       } else {
         return aFrame ? aFrame->GetPrevSibling() : LastChild();
@@ -565,31 +567,31 @@ nsFrameList::GetNextVisualFor(nsIFrame* 
   PRInt32 numFramesOnLine;
   nsRect lineBounds;
   PRUint32 lineFlags;
 
   if (aFrame) {
     iter->GetLine(thisLine, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
     
     if (baseLevel == NSBIDI_LTR) {
-      frame = nsBidiPresUtils::GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToRightOf(aFrame, firstFrameOnLine, numFramesOnLine);
     } else { // RTL
-      frame = nsBidiPresUtils::GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToLeftOf(aFrame, firstFrameOnLine, numFramesOnLine);
     }
   }
   
   PRInt32 numLines = iter->GetNumLines();
   if (!frame && thisLine < numLines - 1) {
     // Get the first frame of the next line
     iter->GetLine(thisLine + 1, &firstFrameOnLine, &numFramesOnLine, lineBounds, &lineFlags);
     
     if (baseLevel == NSBIDI_LTR) {
-      frame = nsBidiPresUtils::GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToRightOf(nsnull, firstFrameOnLine, numFramesOnLine);
     } else { // RTL
-      frame = nsBidiPresUtils::GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
+      frame = bidiUtils->GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
     }
   }
   return frame;
 }
 #endif
 
 #ifdef DEBUG_FRAME_LIST
 void
--- a/layout/generic/nsImageFrame.cpp
+++ b/layout/generic/nsImageFrame.cpp
@@ -996,27 +996,31 @@ nsImageFrame::DisplayAltText(nsPresConte
     PRUint32  maxFit;  // number of characters that fit
     nscoord strWidth = MeasureString(str, strLen, aRect.width, maxFit,
                                      aRenderingContext);
     
     // Display the text
     nsresult rv = NS_ERROR_FAILURE;
 
     if (aPresContext->BidiEnabled()) {
-      const nsStyleVisibility* vis = GetStyleVisibility();
-      if (vis->mDirection == NS_STYLE_DIRECTION_RTL)
-        rv = nsBidiPresUtils::RenderText(str, maxFit, NSBIDI_RTL,
-                                         aPresContext, aRenderingContext,
-                                         aRenderingContext,
-                                         aRect.XMost() - strWidth, y + maxAscent);
-      else
-        rv = nsBidiPresUtils::RenderText(str, maxFit, NSBIDI_LTR,
-                                         aPresContext, aRenderingContext,
-                                         aRenderingContext,
-                                         aRect.x, y + maxAscent);
+      nsBidiPresUtils* bidiUtils =  aPresContext->GetBidiUtils();
+      
+      if (bidiUtils) {
+        const nsStyleVisibility* vis = GetStyleVisibility();
+        if (vis->mDirection == NS_STYLE_DIRECTION_RTL)
+          rv = bidiUtils->RenderText(str, maxFit, NSBIDI_RTL,
+                                     aPresContext, aRenderingContext,
+                                     aRenderingContext,
+                                     aRect.XMost() - strWidth, y + maxAscent);
+        else
+          rv = bidiUtils->RenderText(str, maxFit, NSBIDI_LTR,
+                                     aPresContext, aRenderingContext,
+                                     aRenderingContext,
+                                     aRect.x, y + maxAscent);
+      }
     }
     if (NS_FAILED(rv))
       aRenderingContext.DrawString(str, maxFit, aRect.x, y + maxAscent);
 
     // Move to the next line
     str += maxFit;
     strLen -= maxFit;
     y += height;
--- a/layout/generic/nsLineBox.cpp
+++ b/layout/generic/nsLineBox.cpp
@@ -654,20 +654,22 @@ nsLineIterator::CheckLineOrder(PRInt32  
   nsLineBox* line = mLines[aLine];
 
   if (!line->mFirstChild) { // empty line
     *aIsReordered = PR_FALSE;
     *aFirstVisual = nsnull;
     *aLastVisual = nsnull;
     return NS_OK;
   }
-  
+
+  nsBidiPresUtils* bidiUtils = line->mFirstChild->PresContext()->GetBidiUtils();
+
   nsIFrame* leftmostFrame;
   nsIFrame* rightmostFrame;
-  *aIsReordered = nsBidiPresUtils::CheckLineOrder(line->mFirstChild, line->GetChildCount(), &leftmostFrame, &rightmostFrame);
+  *aIsReordered = bidiUtils->CheckLineOrder(line->mFirstChild, line->GetChildCount(), &leftmostFrame, &rightmostFrame);
 
   // map leftmost/rightmost to first/last according to paragraph direction
   *aFirstVisual = mRightToLeft ? rightmostFrame : leftmostFrame;
   *aLastVisual = mRightToLeft ? leftmostFrame : rightmostFrame;
 
   return NS_OK;
 }
 #endif // IBMBIDI
--- a/layout/generic/nsQueryFrame.h
+++ b/layout/generic/nsQueryFrame.h
@@ -83,16 +83,17 @@ public:
     nsButtonBoxFrame_id,
     nsCanvasFrame_id,
     nsColumnSetFrame_id,
     nsComboboxControlFrame_id,
     nsComboboxDisplayFrame_id,
     nsContainerFrame_id,
     nsContinuingTextFrame_id,
     nsDeckFrame_id,
+    nsDirectionalFrame_id,
     nsDocElementBoxFrame_id,
     nsFieldSetFrame_id,
     nsFileControlFrame_id,
     nsFirstLetterFrame_id,
     nsFirstLineFrame_id,
     nsFormControlFrame_id,
     nsFrame_id,
     nsGfxButtonControlFrame_id,
--- a/layout/generic/nsTextFrameThebes.cpp
+++ b/layout/generic/nsTextFrameThebes.cpp
@@ -101,16 +101,18 @@
 #include "nsILineIterator.h"
 
 #include "nsIServiceManager.h"
 #ifdef ACCESSIBILITY
 #include "nsAccessibilityService.h"
 #endif
 #include "nsAutoPtr.h"
 
+#include "nsBidiFrames.h"
+#include "nsBidiPresUtils.h"
 #include "nsBidiUtils.h"
 
 #include "gfxFont.h"
 #include "gfxContext.h"
 #include "gfxTextRunWordCache.h"
 #include "gfxImageSurface.h"
 #include "mozilla/dom/Element.h"
 
deleted file mode 100644
--- a/layout/reftests/bidi/229367-1-ref.html
+++ /dev/null
@@ -1,10 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>br-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
- </head>
- <body>
-  <p>&#x05D0; --&gt;&lrm;<br>--&gt; &#x05D1;</p>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/229367-1.html
+++ /dev/null
@@ -1,10 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>br-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
- </head>
- <body>
-  <p>&#x05D0; --&gt;<br>--&gt; &#x05D1;</p>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/229367-2-ref.html
+++ /dev/null
@@ -1,43 +0,0 @@
-<DOCTYPE html>
-<html DIR=RTL>
- <head>
-  <meta charset=UTF-8>
-  <title>BIDI Layout Testing</title>
- </head>
- <body>
-  <h2>This is a testing for BiDi layout issues.</h2> 
-<br> 
- 
-1 - No tag<br> 
-2 - SPAN<br> 
-3 - P<br> 
-4 - DIV<br> 
-
-<br> 
-<b>Test1: No space</b><br> 
-This is a testing for BiDi layout issues.&rlm;<br> 
-<span>This is a testing for BiDi layout issues.&rlm;<br></span> 
-<p>This is a testing for BiDi layout issues.&rlm;<br></p> 
-<div>This is a testing for BiDi layout issues.&rlm;<br></div> 
-<br><br> 
-<b>Test2: 3 spaces at the end</b><br> 
-This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br> 
-<span>This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br></span> 
-
-<p>This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br></p> 
-<div>This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br></div> 
-<br><br> 
-<b>Test3: 3 spaces at the beginning</b><br> 
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;<br> 
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;<br></span> 
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;<br></p> 
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;<br></div> 
-<br><br> 
-
-<b>Test4: 3 spaces at the end and the beginning</b><br> 
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br> 
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br></span> 
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br></p> 
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;<br></div> 
- </body> 
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/229367-2.html
+++ /dev/null
@@ -1,43 +0,0 @@
-<DOCTYPE html>
-<html DIR=RTL>
- <head>
-  <meta charset=UTF-8>
-  <title>BIDI Layout Testing</title>
- </head>
- <body>
-  <h2>This is a testing for BiDi layout issues.</h2> 
-<br> 
- 
-1 - No tag<br> 
-2 - SPAN<br> 
-3 - P<br> 
-4 - DIV<br> 
-
-<br> 
-<b>Test1: No space</b><br> 
-This is a testing for BiDi layout issues.<br> 
-<span>This is a testing for BiDi layout issues.<br></span> 
-<p>This is a testing for BiDi layout issues.<br></p> 
-<div>This is a testing for BiDi layout issues.<br></div> 
-<br><br> 
-<b>Test2: 3 spaces at the end</b><br> 
-This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br> 
-<span>This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br></span> 
-
-<p>This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br></p> 
-<div>This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br></div> 
-<br><br> 
-<b>Test3: 3 spaces at the beginning</b><br> 
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.<br> 
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.<br></span> 
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.<br></p> 
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.<br></div> 
-<br><br> 
-
-<b>Test4: 3 spaces at the end and the beginning</b><br> 
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br> 
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br></span> 
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br></p> 
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;<br></div> 
- </body> 
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/229367-3-ref.html
+++ /dev/null
@@ -1,35 +0,0 @@
-<DOCTYPE html>
-<!-- This tests that embeddings and overrides are preserved after <br> -->
-<html>
- <head>
-  <meta charset=UTF-8>
-  <title>Bug 229367</title>
-  <style type="text/css">
-   p { margin: 0; text-align: left; }
-   p.er { unicode-bidi: embed; direction: rtl; }
-   p.ol { unicode-bidi: bidi-override; direction: ltr; }
-   p.or { unicode-bidi: bidi-override; direction: rtl; }
-  </style>
- </head>
- <body>
-  <p>במה מדליקין,</p>
-  <p>ובמה אין מדליקין?</p>
-  <p class="er">אין מדליקין לא בלכש, </p>
-  <p class="er">ולא בחוסן, </p>
-  <p class="er">ולא בכלך, </p>
-  <p class="er">ולא בפתילת האידן, </p>
-  <p class="ol">ולא בפתילת המדבר, </p>
-  <p class="ol">ולא בירוקה שעל פני המים.  </p>
-  <p class="ol">לא בזפת, </p>
-  <p class="or">ולא בשעווה, </p>
-  <p class="or">ולא בשמן קיק, </p>
-  <p class="or">ולא בשמן שריפה, </p>
-  <p class="or">ולא באליה, </p>
-  <p class="ol">ולא בחלב.  </p>
-  <p class="ol">נחום המדי אומר, </p>
-  <p class="er">מדליקין בחלב מבושל;</p>
-  <p class="er">וחכמים אומרים, </p>
-  <p>אחד מבושל ואחד שאינו מבושל,</p>
-  <p>אין מדליקין בו.</p>
- </body> 
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/229367-3.html
+++ /dev/null
@@ -1,30 +0,0 @@
-<DOCTYPE html>
-<!-- This tests that embeddings and overrides are preserved after <br> -->
-<html>
- <head>
-  <meta charset=UTF-8>
-  <title>Bug 229367</title>
- </head>
- <body>
-  <div>במה מדליקין,<br>
-ובמה אין מדליקין?<br>
-<span style="unicode-bidi: embed; direction: rtl">אין מדליקין לא בלכש, <br>
-ולא בחוסן, <br>
-ולא בכלך, <br>
-ולא בפתילת האידן, <br>
-<span style="unicode-bidi: bidi-override; direction: ltr">ולא בפתילת המדבר, <br>
-ולא בירוקה שעל פני המים.  <br>
-לא בזפת, <br>
-<span style="unicode-bidi: bidi-override; direction: rtl">ולא בשעווה, <br>
-ולא בשמן קיק, <br>
-ולא בשמן שריפה, <br>
-ולא באליה, <br></span>
-ולא בחלב.  <br>
-נחום המדי אומר, <br></span>
-מדליקין בחלב מבושל; <br>
-וחכמים אומרים, <br></span>
-אחד מבושל ואחד שאינו מבושל,<br>
-אין מדליקין בו.
-  </div> 
- </body> 
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/263359-1-ref.html
+++ /dev/null
@@ -1,11 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>preformatted-paragraph-break-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
- </head>
- <body>
-  <pre>&#x05D0; --&gt;&lrm;
---&gt; &#x05D1;</pre>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/263359-1.html
+++ /dev/null
@@ -1,12 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>preformatted-paragraph-break-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
- </head>
- <body>
-  <pre>&#x05D0; --&gt;
---&gt; &#x05D1;</pre>
-</body>
-</html>
-
deleted file mode 100644
--- a/layout/reftests/bidi/263359-1a.html
+++ /dev/null
@@ -1,20 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>preformatted-paragraph-break-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
-<script type="text/javascript">
-
-function boom()
-{
-  document.getElementById("w").style.whiteSpace="pre";
-}
-
-</script>
- </head>
- <body onload="boom();">
-  <pre id="w" style="white-space: normal">&#x05D0; --&gt;
---&gt; &#x05D1;</pre>
-</body>
-</html>
-
deleted file mode 100644
--- a/layout/reftests/bidi/263359-1b.html
+++ /dev/null
@@ -1,20 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>preformatted-paragraph-break-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
-<script type="text/javascript">
-
-function boom()
-{
-  document.getElementById("w").style.whiteSpace="normal";
-}
-
-</script>
- </head>
- <body onload="boom();">
-  <pre id="w">&#x05D0; --&gt;
---&gt; &#x05D1;</pre>
-</body>
-</html>
-
deleted file mode 100644
--- a/layout/reftests/bidi/263359-2-ref.html
+++ /dev/null
@@ -1,47 +0,0 @@
-<DOCTYPE html>
-<html DIR=RTL>
- <head>
-  <meta charset=UTF-8>
-  <title>BIDI Layout Testing</title>
- </head>
- <body>
-  <div style="white-space: pre">
-<b>Test1: No space</b> 
-This is a testing for BiDi layout issues. &rlm;
-<span>This is a testing for BiDi layout issues.&rlm;
-</span> 
-<p>This is a testing for BiDi layout issues.&rlm;
-</p>
-<div>This is a testing for BiDi layout issues.&rlm;
-</div>
-
-<b>Test2: 3 spaces at the end</b>
-This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-<span>This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-</span>
-
-<p>This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-</p>
-<div>This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-</div>
-
-<b>Test3: 3 spaces at the beginning</b>
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;
-</span>
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;
-</p>
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;
-</div>
-
-<b>Test4: 3 spaces at the end and the beginning</b>
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-</span>
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-</p>
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&rlm;&nbsp;&nbsp;&nbsp;
-</div>
-</div>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/263359-2.html
+++ /dev/null
@@ -1,46 +0,0 @@
-<DOCTYPE html>
-<html DIR=RTL>
- <head>
-  <meta charset=UTF-8>
-  <title>BIDI Layout Testing</title>
- </head>
- <body>
-  <div style="white-space: pre">
-<b>Test1: No space</b> 
-This is a testing for BiDi layout issues. 
-<span>This is a testing for BiDi layout issues.
-</span> 
-<p>This is a testing for BiDi layout issues.
-</p>
-<div>This is a testing for BiDi layout issues.</div>
-
-<b>Test2: 3 spaces at the end</b>
-This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-<span>This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-</span>
-
-<p>This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-</p>
-<div>This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-</div>
-
-<b>Test3: 3 spaces at the beginning</b>
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.
-</span>
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.
-</p>
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.
-</div>
-
-<b>Test4: 3 spaces at the end and the beginning</b>
-&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-<span>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-</span>
-<p>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-</p>
-<div>&nbsp;&nbsp;&nbsp;This is a testing for BiDi layout issues.&nbsp;&nbsp;&nbsp;
-</div>
-</div>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/263359-3-ref.html
+++ /dev/null
@@ -1,35 +0,0 @@
-<DOCTYPE html>
-<!-- This tests that embeddings and overrides are preserved after <br> -->
-<html>
- <head>
-  <meta charset=UTF-8>
-  <title>Bug 263359</title>
-  <style type="text/css">
-   p { margin: 0; text-align: left; white-space: pre }
-   p.er { direction: rtl; }
-   p.ol { unicode-bidi: bidi-override; direction: ltr; }
-   p.or { unicode-bidi: bidi-override; direction: rtl; }
-  </style>
- </head>
- <body>
-<p>במה מדליקין,</p>
-<p>ובמה אין מדליקין?</p>
-<p class="er">אין מדליקין לא בלכש,</p>
-<p class="er">ולא בחוסן,</p>
-<p class="er">ולא בכלך,</p>
-<p class="er">ולא בפתילת האידן,</p>
-<p class="ol">ולא בפתילת המדבר,</p>
-<p class="ol">ולא בירוקה שעל פני המים.</p>
-<p class="ol">לא בזפת,</p>
-<p class="or">ולא בשעווה,</p>
-<p class="or">ולא בשמן קיק,</p>
-<p class="or">ולא בשמן שריפה,</p>
-<p class="or">ולא באליה,</p>
-<p class="ol">ולא בחלב.</p>
-<p class="ol">נחום המדי אומר,</p>
-<p class="er">מדליקין בחלב מבושל;</p>
-<p class="er">וחכמים אומרים,</p>
-<p>אחד מבושל ואחד שאינו מבושל,</p>
-<p>אין מדליקין בו.</p>
- </body> 
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/263359-3.html
+++ /dev/null
@@ -1,36 +0,0 @@
-<DOCTYPE html>
-<!-- This tests that embeddings and overrides are preserved in <pre> -->
-<html>
- <head>
-  <meta charset=UTF-8>
-  <title>Bug 263359</title>
-  <style type="text/css">
-   p {
- white-space: pre;
- margin: 0;
-     }
-  </style>
- </head>
- <body>
-  <p style="">במה מדליקין,
-ובמה אין מדליקין?
-<span dir="rtl">אין מדליקין לא בלכש,
-ולא בחוסן,
-ולא בכלך,
-ולא בפתילת האידן,
-<span style="unicode-bidi: bidi-override; direction: ltr">ולא בפתילת המדבר,
-ולא בירוקה שעל פני המים.
-לא בזפת,
-<span style="unicode-bidi: bidi-override; direction: rtl">ולא בשעווה,
-ולא בשמן קיק,
-ולא בשמן שריפה,
-ולא באליה, </span>
-ולא בחלב.
-נחום המדי אומר, </span>
-מדליקין בחלב מבושל;
-וחכמים אומרים, </span>
-אחד מבושל ואחד שאינו מבושל,
-אין מדליקין בו.
-  </pre>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/263359-4-ref.html
+++ /dev/null
@@ -1,16 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>change direction of pre with bidi text</title>
-  <meta charset="UTF-8">
- </head>
- <body>
-  <pre dir="rtl">	can_be_executable=TRUE
-	[he]description=סוג לא ידוע
-	description=Unknown type
-	[ar]description=نوع غير معروف
-	[az]description=Namə'lum növ
-</pre>
-</body>
-</html>
-
deleted file mode 100644
--- a/layout/reftests/bidi/263359-4.html
+++ /dev/null
@@ -1,24 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>change direction of pre with bidi text</title>
-  <meta charset="UTF-8">
-<script type="text/javascript">
-
-function boom()
-{
-  document.getElementById("w").style.direction="rtl";
-}
-
-</script>
- </head>
- <body onload="boom();">
-  <pre id="w">	can_be_executable=TRUE
-	[he]description=סוג לא ידוע
-	description=Unknown type
-	[ar]description=نوع غير معروف
-	[az]description=Namə'lum növ
-</pre>
-</body>
-</html>
-
deleted file mode 100644
--- a/layout/reftests/bidi/613157-1-ref.html
+++ /dev/null
@@ -1,10 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>block-element-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
- </head>
- <body>
-  <div>&#x05D0; --&gt;&lrm;<hr>--&gt; &#x05D1;</div>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/613157-1.html
+++ /dev/null
@@ -1,10 +0,0 @@
-<!DOCTYPE html>
-<html>
- <head>
-  <title>block-element-as-bidi-paragraph-break</title>
-  <meta charset="UTF-8">
- </head>
- <body>
-  <div>&#x05D0; --&gt;<hr>--&gt; &#x05D1;</div>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/613157-2-ref.html
+++ /dev/null
@@ -1,10 +0,0 @@
-<!DOCTYPE HTML>
-<html>
- <head>
-  <meta charset="utf-8">
-  <title>Inline blocks shouldn't end the paragraph</title>
- </head>
- <body>
-  <p>&#x202e;אני אוהב--&gt; 4 xoferiF--&gt;8 ימים בשבוע</p>
- </body>
-</html>
deleted file mode 100644
--- a/layout/reftests/bidi/613157-2.html
+++ /dev/null
@@ -1,11 +0,0 @@
-<!DOCTYPE HTML>
-<html>
- <head>
-  <meta charset="utf-8">
-  <title>Inline blocks shouldn't end the paragraph</title>
- </head>
- <body>
-  <p><span dir="rtl">אני אוהב</span>--&gt;<span style="display: inline-block">Firefox 4&nbsp;</span>--&gt;8 ימים בשבוע
-  </p>
- </body>
-</html>
--- a/layout/reftests/bidi/reftest.list
+++ b/layout/reftests/bidi/reftest.list
@@ -38,26 +38,17 @@ random-if(cocoaWidget) == mirroring-02.h
 == 83958-1a.html 83958-1-ref.html
 == 83958-1b.html 83958-1-ref.html
 == 83958-1c.html 83958-1-ref.html
 == 83958-2a.html 83958-2-ref.html
 == 83958-2b.html 83958-2-ref.html
 == 83958-2c.html 83958-2-ref.html
 == 115921-1.html 115921-1-ref.html
 == 115921-2.html 115921-2-ref.html
-== 229367-1.html 229367-1-ref.html
-== 229367-2.html 229367-2-ref.html
-== 229367-3.html 229367-3-ref.html
 == 258928-1.html 258928-1-ref.html
-== 263359-1.html 263359-1-ref.html
-== 263359-1a.html 263359-1-ref.html
-!= 263359-1b.html 263359-1-ref.html
-== 263359-2.html 263359-2-ref.html
-== 263359-3.html 263359-3-ref.html
-== 263359-4.html 263359-4-ref.html
 random-if(winWidget) == 267459-1.html 267459-1-ref.html # depends on windows version, see bug 590101
 fails-if(Android) == 267459-2.html 267459-2-ref.html # bug 650567
 == 299065-1.html 299065-1-ref.html
 random-if(winWidget) == 305643-1.html 305643-1-ref.html # depends on windows version, see bug 590101
 == 332655-1.html 332655-1-ref.html
 == 332655-2.html 332655-2-ref.html
 == 381279-1.html 381279-1-ref.html
 fails-if(Android) == 386339.html 386339-ref.html
@@ -75,10 +66,8 @@ fails-if(Android) == 386339.html 386339-
 == 503269-1.html 503269-1-ref.html
 == 503957-1.html 503957-1-ref.html
 == 525740-1.html 525740-1-ref.html
 == 536963-1.html 536963-1-ref.html
 == 588739-1.html 588739-ref.html
 == 588739-2.html 588739-ref.html
 == 588739-3.html 588739-ref.html
 == 612843-1.html 612843-1-ref.html
-== 613157-1.html 613157-1-ref.html
-== 613157-2.html 613157-2-ref.html
--- a/layout/svg/base/src/nsSVGGlyphFrame.cpp
+++ b/layout/svg/base/src/nsSVGGlyphFrame.cpp
@@ -1525,55 +1525,58 @@ nsSVGGlyphFrame::EnsureTextRun(float *aD
   double textRunSize;
   if (mTextRun) {
     textRunSize = mTextRun->GetFontGroup()->GetStyle()->size;
   } else {
     nsAutoString text;
     if (!GetCharacterData(text))
       return PR_FALSE;
 
-    nsAutoString visualText;
-      
-    /*
-     * XXXsmontagu: The SVG spec says:
-     *
-     * http://www.w3.org/TR/SVG11/text.html#DirectionProperty
-     *  "For the 'direction' property to have any effect, the 'unicode-bidi'
-     *   property's value must be embed or bidi-override."
-     *
-     * The SVGTiny spec, on the other hand, says 
-     *
-     * http://www.w3.org/TR/SVGTiny12/text.html#DirectionProperty
-     *  "For the 'direction' property to have any effect on an element that 
-     *   does not by itself establish a new text chunk (such as the 'tspan'
-     *   element in SVG 1.2 Tiny), the 'unicode-bidi' property's value must
-     *   be embed or bidi-override."
-     *
-     * Note that this is different from HTML/CSS, where setting the 'dir'
-     *  attribute on an inline element automatically sets unicode-bidi: embed
-     *
-     * Our current implementation of bidi in SVG does not distinguish between
-     * different text elements, but treats every text container frame as a
-     * new text chunk, so we always set the base direction according to the
-     * direction property
-     *
-     * See also XXXsmontagu comments in nsSVGTextFrame::UpdateGlyphPositioning
-     */
-    
-    // Get the unicodeBidi property from the parent, because it doesn't
-    // inherit
-    PRBool bidiOverride = (mParent->GetStyleTextReset()->mUnicodeBidi ==
-                           NS_STYLE_UNICODE_BIDI_OVERRIDE);
-    nsBidiLevel baseDirection =
-      GetStyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL ?
-        NSBIDI_RTL : NSBIDI_LTR;
-    nsBidiPresUtils::CopyLogicalToVisual(text, visualText,
-                                         baseDirection, bidiOverride);
-    if (!visualText.IsEmpty()) {
-      text = visualText;
+    nsBidiPresUtils* bidiUtils = presContext->GetBidiUtils();
+    if (bidiUtils) {
+      nsAutoString visualText;
+
+      /*
+       * XXXsmontagu: The SVG spec says:
+       *
+       * http://www.w3.org/TR/SVG11/text.html#DirectionProperty
+       *  "For the 'direction' property to have any effect, the 'unicode-bidi'
+       *   property's value must be embed or bidi-override."
+       *
+       * The SVGTiny spec, on the other hand, says 
+       *
+       * http://www.w3.org/TR/SVGTiny12/text.html#DirectionProperty
+       *  "For the 'direction' property to have any effect on an element that 
+       *   does not by itself establish a new text chunk (such as the 'tspan'
+       *   element in SVG 1.2 Tiny), the 'unicode-bidi' property's value must
+       *   be embed or bidi-override."
+       *
+       * Note that this is different from HTML/CSS, where setting the 'dir'
+       *  attribute on an inline element automatically sets unicode-bidi: embed
+       *
+       * Our current implementation of bidi in SVG does not distinguish between
+       * different text elements, but treats every text container frame as a
+       * new text chunk, so we always set the base direction according to the
+       * direction property
+       *
+       * See also XXXsmontagu comments in nsSVGTextFrame::UpdateGlyphPositioning
+       */
+        
+      // Get the unicodeBidi property from the parent, because it doesn't
+      // inherit
+      PRBool bidiOverride = (mParent->GetStyleTextReset()->mUnicodeBidi ==
+                             NS_STYLE_UNICODE_BIDI_OVERRIDE);
+      nsBidiLevel baseDirection =
+        GetStyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL ?
+          NSBIDI_RTL : NSBIDI_LTR;
+      bidiUtils->CopyLogicalToVisual(text, visualText,
+                                     baseDirection, bidiOverride);
+      if (!visualText.IsEmpty()) {
+        text = visualText;
+      }
     }
 
     gfxMatrix m;
     if (aForceGlobalTransform ||
         !(GetStateBits() & NS_STATE_SVG_NONDISPLAY_CHILD)) {
       if (!GetGlobalTransform(&m))
         return PR_FALSE;
     }
--- a/layout/xul/base/src/nsTextBoxFrame.cpp
+++ b/layout/xul/base/src/nsTextBoxFrame.cpp
@@ -530,38 +530,42 @@ nsTextBoxFrame::DrawText(nsRenderingCont
 
     aRenderingContext.SetColor(aOverrideColor ? *aOverrideColor : GetStyleColor()->mColor);
 
 #ifdef IBMBIDI
     nsresult rv = NS_ERROR_FAILURE;
 
     if (mState & NS_FRAME_IS_BIDI) {
       presContext->SetBidiEnabled();
-      const nsStyleVisibility* vis = GetStyleVisibility();
-      nsBidiDirection direction = (NS_STYLE_DIRECTION_RTL == vis->mDirection) ? NSBIDI_RTL : NSBIDI_LTR;
-      if (mAccessKeyInfo && mAccessKeyInfo->mAccesskeyIndex != kNotFound) {
-          // We let the RenderText function calculate the mnemonic's
-          // underline position for us.
-          nsBidiPositionResolve posResolve;
-          posResolve.logicalIndex = mAccessKeyInfo->mAccesskeyIndex;
-          rv = nsBidiPresUtils::RenderText(mCroppedTitle.get(), mCroppedTitle.Length(), direction,
-                                           presContext, aRenderingContext,
-                                           *refContext,
-                                           aTextRect.x, baseline,
-                                           &posResolve,
-                                           1);
-          mAccessKeyInfo->mBeforeWidth = posResolve.visualLeftTwips;
-          mAccessKeyInfo->mAccessWidth = posResolve.visualWidth;
-      }
-      else
-      {
-          rv = nsBidiPresUtils::RenderText(mCroppedTitle.get(), mCroppedTitle.Length(), direction,
-                                           presContext, aRenderingContext,
-                                           *refContext,
-                                           aTextRect.x, baseline);
+      nsBidiPresUtils* bidiUtils = presContext->GetBidiUtils();
+
+      if (bidiUtils) {
+        const nsStyleVisibility* vis = GetStyleVisibility();
+        nsBidiDirection direction = (NS_STYLE_DIRECTION_RTL == vis->mDirection) ? NSBIDI_RTL : NSBIDI_LTR;
+        if (mAccessKeyInfo && mAccessKeyInfo->mAccesskeyIndex != kNotFound) {
+           // We let the RenderText function calculate the mnemonic's
+           // underline position for us.
+           nsBidiPositionResolve posResolve;
+           posResolve.logicalIndex = mAccessKeyInfo->mAccesskeyIndex;
+           rv = bidiUtils->RenderText(mCroppedTitle.get(), mCroppedTitle.Length(), direction,
+                                      presContext, aRenderingContext,
+                                      *refContext,
+                                      aTextRect.x, baseline,
+                                      &posResolve,
+                                      1);
+           mAccessKeyInfo->mBeforeWidth = posResolve.visualLeftTwips;
+           mAccessKeyInfo->mAccessWidth = posResolve.visualWidth;
+        }
+        else
+        {
+           rv = bidiUtils->RenderText(mCroppedTitle.get(), mCroppedTitle.Length(), direction,
+                                      presContext, aRenderingContext,
+                                      *refContext,
+                                      aTextRect.x, baseline);
+        }
       }
     }
     if (NS_FAILED(rv) )
 #endif // IBMBIDI
     {
        aRenderingContext.SetTextRunRTL(PR_FALSE);
 
        if (mAccessKeyInfo && mAccessKeyInfo->mAccesskeyIndex != kNotFound) {
--- a/layout/xul/base/src/tree/src/nsTreeBodyFrame.cpp
+++ b/layout/xul/base/src/tree/src/nsTreeBodyFrame.cpp
@@ -102,17 +102,17 @@
 #include "nsLayoutUtils.h"
 #include "nsIScrollableFrame.h"
 #include "nsEventDispatcher.h"
 #include "nsDisplayList.h"
 #include "nsTreeBoxObject.h"
 #include "nsRenderingContext.h"
 
 #ifdef IBMBIDI
-#include "nsBidiUtils.h"
+#include "nsBidiPresUtils.h"
 #endif
 
 // Enumeration function that cancels all the image requests in our cache
 static PLDHashOperator
 CancelImageRequest(const nsAString& aKey,
                    nsTreeImageCacheEntry aEntry, void* aData)
 {
   aEntry.request->CancelAndForgetObserver(NS_BINDING_ABORTED);