Attachment #519654 for bug #624798

Attachment #519654: Patch for bug #624798

View | Details | Raw Unified | Return to bug 624798
Collapse All | Expand All





#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"


    }

    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()) {


    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);
    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)


        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);
            if (NS_FAILED(rv))
                return rv;

            ShadowFinalize(blur);
        }

        processor.mThebes = mThebes;
    }


            // 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);

    // this needs to be restored before function can return
    if (doUseIntermediateSurface) {
        mThebes->PopGroupToSource();
        DirtyAllStyles();
    }

    if (NS_FAILED(rv))





   *      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);
#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.
   *

   *      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);

#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

  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);

  PRInt32 doWriteReverse(const PRUnichar *src, PRInt32 srcLength,
                         PRUnichar *dest, PRUint16 options);

};

#endif // _nsBidi_h_





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;
  nsTArray<PRUnichar> mEmbeddingStack;
  nsTArray<nsIFrame*> mLogicalFrames;
  nsDataHashtable<nsISupportsHashKey, PRInt32> mContentToFrameIndex;
  PRPackedBool        mIsVisual;
  nsBidiLevel         mParaLevel;
  nsIContent*         mPrevContent;
  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;

    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;
        }
      }
    }
  }
}

  void Destroy() { delete mBidiEngine; }

  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;
  }
  delete mBidiEngine;
}

  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);
  }

  PRInt32 GetLastFrameForContent(nsIContent *aContent)
  {
    PRInt32 index = 0;
    mContentToFrameIndex.Get(aContent, &index);
    return index;
  }

  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;
  nsTArray<PRUint8>   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;

    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]; }
};

/* 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.

 *  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);
  mBuffer.SetLength(0);
  mEmbeddingStack.Clear();
  
  nsPresContext *presContext = aBlockFrame->PresContext();

  const nsStyleVisibility* vis = aBlockFrame->GetStyleVisibility();

  mParaLevel = (NS_STYLE_DIRECTION_RTL == vis->mDirection) ?
                NSBIDI_RTL : NSBIDI_LTR;

  mLineIter = new nsBlockInFlowLineIterator(aBlockFrame,
                                            aBlockFrame->begin_lines(),
                                            PR_FALSE);
  if (mLineIter->GetLine() == aBlockFrame->end_lines()) {
    // Advance to first valid line (might be in a next-continuation)
    mLineIter->Next();
  }

  mIsVisual = 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;
      }
    }
  }
  mPrevFrame = nsnull;

  // handle bidi-override being set on the block itself before calling
  // TraverseFrames.
  const nsStyleTextReset* text = aBlockFrame->GetStyleTextReset();
  PRUnichar ch = 0;
  if (text->mUnicodeBidi == NS_STYLE_UNICODE_BIDI_OVERRIDE) {
    const nsStyleVisibility* vis = aBlockFrame->GetStyleVisibility();
    if (NS_STYLE_DIRECTION_RTL == vis->mDirection) {
      ch = kRLO;
    }
    else if (NS_STYLE_DIRECTION_LTR == vis->mDirection) {
      ch = kLRO;
    }
    if (ch != 0) {
      bpd.PushBidiControl(ch);
      mBuffer.Append(ch);
      mEmbeddingStack.AppendElement(ch);
    }
  }
  mPrevContent = nsnull;
  for (nsBlockFrame* block = aBlockFrame; block;
       block = static_cast<nsBlockFrame*>(block->GetNextContinuation())) {
    block->RemoveStateBits(NS_BLOCK_NEEDS_BIDI_RESOLUTION);
    TraverseFrames(aBlockFrame, block->GetFirstChild(nsnull), &bpd);
  }

  if (ch != 0) {
    bpd.PopBidiControl();
    mBuffer.Append(kPDF);
    NS_ASSERTION(mEmbeddingStack.Length(), "embedding/override underflow");
    mEmbeddingStack.TruncateLength(mEmbeddingStack.Length() - 1);
  }

  // Resolve final paragraph
  nsresult rv = ResolveParagraph(aBlockFrame, &bpd);
  bpd.Destroy();
  return rv;
}

nsresult
nsBidiPresUtils::ResolveParagraph(nsBlockFrame* aBlockFrame,
                                  BidiParagraphData* aBpd)
{
  nsPresContext *presContext = aBlockFrame->PresContext();
  PRInt32 bufferLength = mBuffer.Length();

  if (aBpd->BufferLength() < 1) {
    return NS_OK;
    return;
  }
  aBpd->mBuffer.ReplaceChar("\t\r\n", kSpace);

  PRInt32 runCount;
  PRUint8 embeddingLevel = aBpd->mParaLevel;

  nsresult rv = aBpd->SetPara();
  NS_ENSURE_SUCCESS(rv, rv);
      return;
  }

  rv = aBpd->CountRuns(&runCount);
  NS_ENSURE_SUCCESS(rv, rv);

  }
  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     contentOffset  = 0;   // offset of current frame in its content node
  PRBool      isTextFrame    = PR_FALSE;
  nsIFrame*   frame = nsnull;
  nsIContent* content = nsnull;
  PRInt32     contentTextLength;

  FramePropertyTable *propTable = presContext->PropertyTable();

  
  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;

  if (frameCount == 1 && runCount == 1) {
    // Nothing more to do, just make sure that the frame has the right
    // embedding level.
    aBpd->GetLogicalRun(lineOffset, &logicalLimit, &embeddingLevel);
        NS_FAILED(mBidiEngine->GetLogicalRun(lineOffset, &logicalLimit,
                                             &embeddingLevel))) {
      embeddingLevel = mParaLevel;
    }

    frame = aBpd->FrameAt(0);
    nsBidiLevel oldEmbeddingLevel = NS_GET_EMBEDDING_LEVEL(frame);
    nsBidiLevel oldBaseLevel = NS_GET_BASE_LEVEL(frame);

    if (oldEmbeddingLevel != embeddingLevel ||
        oldBaseLevel != aBpd->mParaLevel) {
      frame->Properties().Set(nsIFrame::EmbeddingLevelProperty(),
                              NS_INT32_TO_PTR(embeddingLevel));
      frame->Properties().Set(nsIFrame::BaseLevelProperty(),
                              NS_INT32_TO_PTR(aBpd->mParaLevel));
      AdvanceLineIteratorToFrame(frame, &lineIter, prevFrame);
      lineIter.GetLine()->MarkDirty();
      if (frame->GetType() == nsGkAtoms::textFrame) {
        frame->AddStateBits(NS_FRAME_IS_BIDI);
      }
    }

    return NS_OK;
    return;
  }

  PRBool lineNeedsUpdate = PR_FALSE;
  
#ifdef NOISY_BIDI
  if (aBpd->mBuffer[0] != kObjectSubstitute) {
    printf("Before Resolve(), aBlockFrame=0x%p, mBuffer='%s', frameCount=%d\n",
           (void*)aBlockFrame, NS_ConvertUTF16toUTF8(aBpd->mBuffer).get(), frameCount);
#ifdef REALLY_NOISY_BIDI
    printf(" frameTree=:\n");
    nsFrame::DumpFrameTree(aBlockFrame);
#endif
  }
#endif
  for (; ;) {
    if (fragmentLength <= 0) {
      // Get the next frame from mLogicalFrames
      if (++frameIndex >= frameCount) {
        break;
      }
      frame = aBpd->FrameAt(frameIndex);
      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 {
        content = frame->GetContent();
        if (!content) {
          rv = 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));
          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;

    } // 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(
              lineOffset, &logicalLimit, &embeddingLevel) ) ) {
        break;
      }
      runLength = logicalLimit - lineOffset;
      if (mIsVisual) {
        embeddingLevel = mParaLevel;
      }
    } // if (runLength <= 0)

    if (frame == NS_BIDI_CONTROL_FRAME) {
      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));
      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)) {
            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);
            mContentToFrameIndex.Get(content, &newIndex);
            if (newIndex > frameIndex) {
              RemoveBidiContinuation(aBpd, 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) {
            /*
             * 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
             */
            nsIFrame* next = frame->GetNextInFlow();
            if (next) {
              frame->SetNextContinuation(next);
              next->SetPrevContinuation(frame);
            }
          }
          frame->AdjustOffsetsForBidi(contentOffset, contentOffset + fragmentLength);
          if (lineNeedsUpdate) {
            AdvanceLineIteratorToFrame(frame, &lineIter, prevFrame);
            lineNeedsUpdate = PR_FALSE;
          }
          lineIter.GetLine()->MarkDirty();
        }
      } // isTextFrame
      else {
        ++lineOffset;
      }
    } // not bidi control frame
    PRInt32 temp = runLength;
    runLength -= fragmentLength;

        // 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);
      }
    }
  } // for
#ifdef REALLY_NOISY_BIDI
  if (aBpd->mBuffer[0] != kObjectSubstitute) {
    printf("---\nAfter Resolve(), frameTree =:\n");
    nsFrame::DumpFrameTree(aBlockFrame);
    printf("===\n");
  }
#endif
  return rv;
}

// 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)
{
  if (!aCurrentFrame)
    return;

  nsIFrame* childFrame = aCurrentFrame;
  do {
    /*
     * It's important to get the next sibling and next continuation *before*

            ch = kLRO;
          }
          break;
      }

      // Add a dummy frame pointer representing a bidi control code before the
      // first frame of an element specifying embedding or override
      if (ch != 0 && !frame->GetPrevContinuation()) {
        aBpd->PushBidiControl(ch);
        mBuffer.Append(ch);
        mEmbeddingStack.AppendElement(ch);
      }
    }

    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);
        mContentToFrameIndex.Put(content, mLogicalFrames.Length());
      }
      mLogicalFrames.AppendElement(frame);

      // 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;

              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()) {
                nsTextFrame* textFrame = static_cast<nsTextFrame*>(frame);
                textFrame->SetLength(endLine - start, nsnull);
                next = frame->GetNextInFlow();
                if (!next) {
                  // If the frame already has a bidi continuation, make it fluid
                  next = frame->GetNextContinuation();

                    MakeContinuationFluid(frame, next);
                    JoinInlineAncestors(frame);
                  } else {
                    // If the frame has no next in flow, create one
                    CreateContinuation(frame, &next, PR_TRUE);
                  }
                }
              }
              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);
        }
      }
    }
    else {
      // For a non-leaf frame, recurse into TraverseFrames
      nsIFrame* kid = frame->GetFirstChild(nsnull);
      TraverseFrames(aBlockFrame, kid, aBpd);
    }

    // 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();
      mBuffer.Append(kPDF);
      NS_ASSERTION(mEmbeddingStack.Length(), "embedding/override underflow");
      mEmbeddingStack.TruncateLength(mEmbeddingStack.Length() - 1);
    }
    childFrame = nextSibling;
  } while (childFrame);
}

void
nsBidiPresUtils::ResolveParagraphWithinBlock(nsBlockFrame* aBlockFrame,
                                             BidiParagraphData* aBpd)
{
  // pop all embeddings and overrides
  aBpd->ClearBidiControls();

  ResolveParagraph(aBlockFrame, aBpd);
    shell = aBlockFrame->PresContext()->PresShell();
    styleContext = aBlockFrame->GetStyleContext();

    // pop all embeddings and overrides
    for (PRUint32 i = 0; i < mEmbeddingStack.Length(); ++i) {
      mBuffer.Append(kPDF);
      mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
    }
  }

  ResolveParagraph(aBlockFrame);

  // Clear the frame array and paragraph buffer, and restore the stored 
  // embeddings and overrides
  aBpd->ResetData();
  mContentToFrameIndex.Clear();
  mBuffer.SetLength(0);
  if (mEmbeddingStack.Length() > 0) {
    for (PRUint32 i = 0; i < mEmbeddingStack.Length(); ++i) {
      mBuffer.Append(mEmbeddingStack[i]);
      mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
    }
  } 
}

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);
  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);

  }
  return NS_GET_BASE_LEVEL(firstLeaf);
}

void
nsBidiPresUtils::IsLeftOrRightMost(nsIFrame*              aFrame,
                                   nsContinuationStates*  aContinuationStates,
                                   PRBool&                aIsLeftMost /* out */,
                                   PRBool&                aIsRightMost /* out */)
{
  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.

  // 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)
{
  if (!aFrame)
    return;

  PRBool isLeftMost, isRightMost;
  IsLeftOrRightMost(aFrame,
                    aContinuationStates,
                    isLeftMost /* out */,

  aFrame->SetRect(nsRect(start, rect.y, aLeft - start, rect.height));

  if (isRightMost)
    aLeft += margin.right;
}

void
nsBidiPresUtils::InitContinuationStates(nsIFrame*              aFrame,
                                        nsContinuationStates*  aContinuationStates)
{
  nsFrameContinuationState* state = aContinuationStates->PutEntry(aFrame);
  state->mFirstVisualFrame = nsnull;
  state->mFrameCount = 0;

  if (!IsBidiLeaf(aFrame)) {
    // Continue for child frames
    nsIFrame* frame;

         frame = frame->GetNextSibling()) {
      InitContinuationStates(frame,
                             aContinuationStates);
    }
  }
}

void
nsBidiPresUtils::RepositionInlineFrames(BidiLineData *aBld,
                                        nsIFrame* aFirstChild)
{
  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 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);
  }

  // Reposition frames in visual order
  for (index = 0; index < count; index++) {
    frame = aBld->VisualFrameAt(index);
    RepositionFrame(frame,
                    (aBld->mLevels[aBld->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();
  PRBool isReordered;
  PRBool hasRTLFrames;
  Reorder(isReordered, hasRTLFrames);
  PRInt32 count = mLogicalFrames.Length();
  
  if (aFirstVisual) {
    *aFirstVisual = bld.VisualFrameAt(0);
  }
  if (aLastVisual) {
    *aLastVisual = bld.VisualFrameAt(count-1);
  }
  
  return bld.mIsReordered;
  return isReordered || hasRTLFrames;
}

nsIFrame*
nsBidiPresUtils::GetFrameToRightOf(const nsIFrame*  aFrame,
                                   nsIFrame*        aFirstFrameOnLine,
                                   PRInt32          aNumFramesOnLine)
{
  BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);

  PRInt32 count = bld.mVisualFrames.Length();
  PRBool hasRTLFrames;
  Reorder(isReordered, hasRTLFrames);
  PRInt32 count = mVisualFrames.Length();

  if (aFrame == nsnull)
    return bld.VisualFrameAt(0);
  
  for (PRInt32 i = 0; i < count - 1; i++) {
    if (bld.VisualFrameAt(i) == aFrame) {
      return bld.VisualFrameAt(i+1);
    }
  }
  
  return nsnull;
}

nsIFrame*
nsBidiPresUtils::GetFrameToLeftOf(const nsIFrame*  aFrame,
                                  nsIFrame*        aFirstFrameOnLine,
                                  PRInt32          aNumFramesOnLine)
{
  BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);

  PRInt32 count = bld.mVisualFrames.Length();
  PRBool hasRTLFrames;
  Reorder(isReordered, hasRTLFrames);
  PRInt32 count = mVisualFrames.Length();
  
  if (aFrame == nsnull)
    return bld.VisualFrameAt(count-1);
  
  for (PRInt32 i = 1; i < count; i++) {
    if (bld.VisualFrameAt(i) == aFrame) {
      return bld.VisualFrameAt(i-1);
    }
  }
  
  return nsnull;
}

inline nsresult
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);
}

void
nsBidiPresUtils::RemoveBidiContinuation(BidiParagraphData *aBpd,
                                        nsIFrame*       aFrame,
                                        PRInt32         aFirstIndex,
                                        PRInt32         aLastIndex,
                                        PRInt32&        aOffset)
{
  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) {
      ++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(),

  }

  StripBidiControlCharacters(aText, aTextLength);
  return rv;
}

void
nsBidiPresUtils::StripBidiControlCharacters(PRUnichar* aText,
                                            PRInt32&   aTextLength)
{
  if ( (nsnull == aText) || (aTextLength < 1) ) {
    return;
  }

  PRInt32 stripLen = 0;

  for (PRInt32 i = 0; i < aTextLength; i++) {

    }
    aTextLength = i - offset;
    aText[aTextLength] = 0;
  }
}
#endif

void
nsBidiPresUtils::CalculateCharType(nsBidi* aBidiEngine,
                                   const PRUnichar* aText,
                                   PRInt32& aOffset,
                                   PRInt32  aCharTypeLimit,
                                   PRInt32& aRunLimit,
                                   PRInt32& aRunLength,
                                   PRInt32& aRunCount,
                                   PRUint8& aCharType,
                                   PRUint8& aPrevCharType)

{
  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]) ) {
      charType = eCharType_RightToLeft;
    }
    else if (IS_ARABIC_ALPHABETIC(aText[offset]) ) {
      charType = eCharType_RightToLeftArabic;
    }
    else {
      aBidiEngine->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

nsresult nsBidiPresUtils::ProcessText(const PRUnichar*       aText,
                                      PRInt32                aLength,
                                      nsBidiDirection        aBaseDirection,
                                      nsPresContext*         aPresContext,
                                      BidiProcessor&         aprocessor,
                                      Mode                   aMode,
                                      nsBidiPositionResolve* aPosResolve,
                                      PRInt32                aPosResolveCount,
                                      nscoord*               aWidth,
                                      nsBidi*                aBidiEngine)
{
  NS_ASSERTION((aPosResolve == nsnull) != (aPosResolveCount > 0), "Incorrect aPosResolve / aPosResolveCount arguments");

  PRInt32 runCount;

  nsAutoString textBuffer(aText, aLength);

  nsresult rv = aBidiEngine->SetPara(aText, aLength, aBaseDirection, nsnull);
  if (NS_FAILED(rv))
    return rv;

  rv = aBidiEngine->CountRuns(&runCount);
  if (NS_FAILED(rv))
    return rv;

  nscoord xOffset = 0;
  nscoord width, xEndRun;
  nscoord totalWidth = 0;
  PRInt32 i, start, limit, length;
  PRUint32 visualStart = 0;

  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);
    if (NS_FAILED(rv))
      return rv;

    rv = aBidiEngine->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;

      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);
      
      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);


                                                         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);
}

/* static */
void nsBidiPresUtils::WriteReverse(const PRUnichar* aSrc,
                                   PRUint32 aSrcLength,
                                   PRUnichar* aDest)
{
  const PRUnichar* src = aSrc + aSrcLength;

      // 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)) {
      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





#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) {}

  /**
   * 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);

  /**
   * 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);

  /**
   * 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);

  /**
   * 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

   * @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,
                             nsIRenderingContext&   aRenderingContext,
                             nsIRenderingContext&   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,
                                  nsIRenderingContext& 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);

  /**
   * 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);
    
  /**
   * 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);
    
  /**
   * 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.

   *  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);

  /**
   * 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);

  /**
   * 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,
                                                 nsIRenderingContext&   aRenderingContext,
                                                 nsIRenderingContext&   aTextRunConstructionContext,
                                                 Mode                   aMode,
                                                 nscoord                aX, // DRAW only
                                                 nscoord                aY, // DRAW only
                                                 nsBidiPositionResolve* aPosResolve,  /* may be null */
                                                 PRInt32                aPosResolveCount,
                                                 nscoord*               aWidth /* may be null */);

  /**
   * 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.
   */
  static void TraverseFrames(nsBlockFrame* aBlockFrame, nsIFrame* aCurrentFrame,
                            BidiParagraphData *aBpd);
  /**
   * Initialize the logically-ordered array of frames
   * using the top-level frames of a single line
   */
  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);

  /*
   * 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);

  /*
   * 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 */);

  /**
   *  Adjust frame positions following their visual order
   *
   *  @param aFirstChild the first kid
   *
   *  @lina 04/11/2000
   */
  static void RepositionInlineFrames(BidiLineData *aBld,
                                     nsIFrame* aFirstChild);
  
  /**
   * 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);

  /**
   * 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

   *                     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);
  
  static void StripBidiControlCharacters(PRUnichar* aText,
                                         PRInt32&   aTextLength);

  static PRBool WriteLogicalToVisual(const PRUnichar* aSrc,
                                     PRUint32 aSrcLength,
                                     PRUnichar* aDest,
                                     nsBidiLevel aBaseDirection,
                                     nsBidi* aBidiEngine);

  static void WriteReverse(const PRUnichar* aSrc,
                           PRUint32 aSrcLength,
                           PRUnichar* aDest);

  nsString        mBuffer;
  nsTArray<PRUnichar> mEmbeddingStack;
  nsTArray<nsIFrame*> mLogicalFrames;
  nsTArray<nsIFrame*> mVisualFrames;
  nsDataHashtable<nsISupportsHashKey, PRInt32> mContentToFrameIndex;
  PRInt32         mArraySize;
  PRInt32*        mIndexMap;
  PRUint8*        mLevels;
  nsresult        mSuccess;
  PRPackedBool    mIsVisual;
  nsBidiLevel     mParaLevel;
  nsIFrame*       mPrevFrame;
  nsIContent*     mPrevContent;

  nsAutoPtr<nsBlockInFlowLineIterator> mLineIter;
  nsBidi*         mBidiEngine;
};

#endif /* nsBidiPresUtils_h___ */

#endif // IBMBIDI





                          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;
    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);
  }
}

nsLayoutUtils::GetStringWidth(const nsIFrame*      aFrame,
                              nsIRenderingContext* 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);
        NSBIDI_RTL : NSBIDI_LTR;
      return bidiUtils->MeasureTextWidth(aString, aLength,
                                         direction, presContext, *aContext);
    }
  }
#endif // IBMBIDI
  aContext->SetTextRunRTL(PR_FALSE);
  nscoord width;
  aContext->GetWidth(aString, aLength, width);
  return width;
}







  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);

  // 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[] = {

  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;
  }


}

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;





   *
   *  @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");


  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>;


  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;





  {
    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:

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

  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);
}






  // 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());

      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);

  NS_ASSERTION(!GetPrevInFlow(),
               "ResolveBidi called on non-first continuation");

  nsPresContext* presContext = PresContext();
  if (!presContext->BidiEnabled()) {
    return NS_OK;
  }

  return nsBidiPresUtils::Resolve(this);
  if (!bidiUtils)
    return NS_ERROR_NULL_POINTER;

  return bidiUtils->Resolve(this);
}
#endif

#ifdef DEBUG
void
nsBlockFrame::VerifyLines(PRBool aFinalCheckOK)
{
  if (!gVerifyLines) {





  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);
      } else { // RTL
        return nsBidiPresUtils::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;

  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);
    } else { // RTL
      frame = nsBidiPresUtils::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);
    } else { // RTL
      frame = nsBidiPresUtils::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);
      } else { // RTL
        return nsBidiPresUtils::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();

  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);
    } else { // RTL
      frame = nsBidiPresUtils::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);
    } else { // RTL
      frame = nsBidiPresUtils::GetFrameToLeftOf(nsnull, firstFrameOnLine, numFramesOnLine);
    }
  }
  return frame;
}
#endif

#ifdef DEBUG_FRAME_LIST
void





    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);
                                     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;





    *aIsReordered = PR_FALSE;
    *aFirstVisual = nsnull;
    *aLastVisual = nsnull;
    return NS_OK;
  }
  
  nsPresContext* presContext = line->mFirstChild->PresContext();

  nsBidiPresUtils* bidiUtils = presContext->GetBidiUtils();

  nsIFrame* leftmostFrame;
  nsIFrame* rightmostFrame;
  *aIsReordered = nsBidiPresUtils::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





#include "nsILineIterator.h"

#include "nsIServiceManager.h"
#ifdef ACCESSIBILITY
#include "nsAccessibilityService.h"
#endif
#include "nsAutoPtr.h"

#include "nsBidiPresUtils.h"
#include "nsBidiUtils.h"

#include "nsIThebesFontMetrics.h"
#include "gfxFont.h"
#include "gfxContext.h"
#include "gfxTextRunWordCache.h"
#include "gfxImageSurface.h"
#include "mozilla/dom/Element.h"





  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;
      if (!visualText.IsEmpty()) {
        text = visualText;
      }
    }

    gfxMatrix m;
    if (aForceGlobalTransform ||
        !(GetStateBits() & NS_STATE_SVG_NONDISPLAY_CHILD)) {
      if (!GetGlobalTransform(&m))
        return PR_FALSE;
    }






    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);
                                      presContext, aRenderingContext,
                                      *refContext,
                                      aTextRect.x, baseline);
        }
      }
    }
    if (NS_FAILED(rv) )
#endif // IBMBIDI
    {
       aRenderingContext.SetTextRunRTL(PR_FALSE);

       if (mAccessKeyInfo && mAccessKeyInfo->mAccesskeyIndex != kNotFound) {





#include "nsContentUtils.h"
#include "nsLayoutUtils.h"
#include "nsIScrollableFrame.h"
#include "nsEventDispatcher.h"
#include "nsDisplayList.h"
#include "nsTreeBoxObject.h"

#ifdef IBMBIDI
#include "nsBidiUtils.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);

Return to bug 624798