layout/base/nsBidiPresUtils.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 #include "nsBidiPresUtils.h"
   7 #include "nsGkAtoms.h"
   8 #include "nsPresContext.h"
   9 #include "nsRenderingContext.h"
  10 #include "nsBidiUtils.h"
  11 #include "nsCSSFrameConstructor.h"
  12 #include "nsContainerFrame.h"
  13 #include "nsInlineFrame.h"
  14 #include "nsPlaceholderFrame.h"
  15 #include "nsFirstLetterFrame.h"
  16 #include "nsUnicodeProperties.h"
  17 #include "nsTextFrame.h"
  18 #include "nsBlockFrame.h"
  19 #include "nsIFrameInlines.h"
  20 #include <algorithm>
  21
  22 #undef NOISY_BIDI
  23 #undef REALLY_NOISY_BIDI
  24
  25 using namespace mozilla;
  26
  27 static const char16_t kSpace            = 0x0020;
  28 static const char16_t kZWSP             = 0x200B;
  29 static const char16_t kLineSeparator    = 0x2028;
  30 static const char16_t kObjectSubstitute = 0xFFFC;
  31 static const char16_t kLRE              = 0x202A;
  32 static const char16_t kRLE              = 0x202B;
  33 static const char16_t kLRO              = 0x202D;
  34 static const char16_t kRLO              = 0x202E;
  35 static const char16_t kPDF              = 0x202C;
  36 static const char16_t kSeparators[] = {
  37   // All characters with Bidi type Segment Separator or Block Separator
  38   char16_t('\t'),
  39   char16_t('\r'),
  40   char16_t('\n'),
  41   char16_t(0xb),
  42   char16_t(0x1c),
  43   char16_t(0x1d),
  44   char16_t(0x1e),
  45   char16_t(0x1f),
  46   char16_t(0x85),
  47   char16_t(0x2029),
  48   char16_t(0)
  49 };
  50
  51 #define NS_BIDI_CONTROL_FRAME ((nsIFrame*)0xfffb1d1)
  52
  53 struct BidiParagraphData {
  54   nsString            mBuffer;
  55   nsAutoTArray<char16_t, 16> mEmbeddingStack;
  56   nsTArray<nsIFrame*> mLogicalFrames;
  57   nsTArray<nsLineBox*> mLinePerFrame;
  58   nsDataHashtable<nsISupportsHashKey, int32_t> mContentToFrameIndex;
  59   bool                mIsVisual;
  60   bool                mReset;
  61   nsBidiLevel         mParaLevel;
  62   nsIContent*         mPrevContent;
  63   nsAutoPtr<nsBidi>   mBidiEngine;
  64   nsIFrame*           mPrevFrame;
  65   nsAutoPtr<BidiParagraphData> mSubParagraph;
  66   uint8_t             mParagraphDepth;
  67
  68   void Init(nsBlockFrame *aBlockFrame)
  69   {
  70     mBidiEngine = new nsBidi();
  71     mPrevContent = nullptr;
  72     mParagraphDepth = 0;
  73
  74     mParaLevel = nsBidiPresUtils::BidiLevelFromStyle(aBlockFrame->StyleContext());
  75
  76     mIsVisual = aBlockFrame->PresContext()->IsVisualMode();
  77     if (mIsVisual) {
  78       /**
  79        * Drill up in content to detect whether this is an element that needs to
  80        * be rendered with logical order even on visual pages.
  81        *
  82        * We always use logical order on form controls, firstly so that text
  83        * entry will be in logical order, but also because visual pages were
  84        * written with the assumption that even if the browser had no support
  85        * for right-to-left text rendering, it would use native widgets with
  86        * bidi support to display form controls.
  87        *
  88        * We also use logical order in XUL elements, since we expect that if a
  89        * XUL element appears in a visual page, it will be generated by an XBL
  90        * binding and contain localized text which will be in logical order.
  91        */
  92       for (nsIContent* content = aBlockFrame->GetContent() ; content;
  93            content = content->GetParent()) {
  94         if (content->IsNodeOfType(nsINode::eHTML_FORM_CONTROL) ||
  95             content->IsXUL()) {
  96           mIsVisual = false;
  97           break;
  98         }
  99       }
 100     }
 101   }
 102
 103   BidiParagraphData* GetSubParagraph()
 104   {
 105     if (!mSubParagraph) {
 106       mSubParagraph = new BidiParagraphData();
 107       mSubParagraph->Init(this);
 108     }
 109
 110     return mSubParagraph;
 111   }
 112
 113   // Initialise a sub-paragraph from its containing paragraph
 114   void Init(BidiParagraphData *aBpd)
 115   {
 116     mBidiEngine = new nsBidi();
 117     mPrevContent = nullptr;
 118     mIsVisual = aBpd->mIsVisual;
 119     mReset = false;
 120   }
 121
 122   void Reset(nsIFrame* aBDIFrame, BidiParagraphData *aBpd)
 123   {
 124     mReset = true;
 125     mLogicalFrames.Clear();
 126     mLinePerFrame.Clear();
 127     mContentToFrameIndex.Clear();
 128     mBuffer.SetLength(0);
 129     mPrevFrame = aBpd->mPrevFrame;
 130     mParagraphDepth = aBpd->mParagraphDepth + 1;
 131
 132     const nsStyleTextReset* text = aBDIFrame->StyleTextReset();
 133     bool isRTL = (NS_STYLE_DIRECTION_RTL ==
 134                   aBDIFrame->StyleVisibility()->mDirection);
 135
 136     if (text->mUnicodeBidi & NS_STYLE_UNICODE_BIDI_PLAINTEXT) {
 137       mParaLevel = NSBIDI_DEFAULT_LTR;
 138     } else {
 139       mParaLevel = mParagraphDepth * 2;
 140       if (isRTL) ++mParaLevel;
 141     }
 142
 143     if (text->mUnicodeBidi & NS_STYLE_UNICODE_BIDI_OVERRIDE) {
 144       PushBidiControl(isRTL ? kRLO : kLRO);
 145     }
 146   }
 147
 148   void EmptyBuffer()
 149   {
 150     mBuffer.SetLength(0);
 151   }
 152
 153   nsresult SetPara()
 154   {
 155     return mBidiEngine->SetPara(mBuffer.get(), BufferLength(),
 156                                 mParaLevel, nullptr);
 157   }
 158
 159   /**
 160    * mParaLevel can be NSBIDI_DEFAULT_LTR as well as NSBIDI_LTR or NSBIDI_RTL.
 161    * GetParaLevel() returns the actual (resolved) paragraph level which is
 162    * always either NSBIDI_LTR or NSBIDI_RTL
 163    */
 164   nsBidiLevel GetParaLevel()
 165   {
 166     nsBidiLevel paraLevel = mParaLevel;
 167     if (IS_DEFAULT_LEVEL(paraLevel)) {
 168       mBidiEngine->GetParaLevel(&paraLevel);
 169     }
 170     return paraLevel;
 171   }
 172
 173   nsBidiDirection GetDirection()
 174   {
 175     nsBidiDirection dir;
 176     mBidiEngine->GetDirection(&dir);
 177     return dir;
 178   }
 179
 180   nsresult CountRuns(int32_t *runCount){ return mBidiEngine->CountRuns(runCount); }
 181
 182   nsresult GetLogicalRun(int32_t aLogicalStart,
 183                          int32_t* aLogicalLimit,
 184                          nsBidiLevel* aLevel)
 185   {
 186     nsresult rv = mBidiEngine->GetLogicalRun(aLogicalStart,
 187                                              aLogicalLimit, aLevel);
 188     if (mIsVisual || NS_FAILED(rv))
 189       *aLevel = GetParaLevel();
 190     return rv;
 191   }
 192
 193   void ResetData()
 194   {
 195     mLogicalFrames.Clear();
 196     mLinePerFrame.Clear();
 197     mContentToFrameIndex.Clear();
 198     mBuffer.SetLength(0);
 199     mPrevContent = nullptr;
 200     for (uint32_t i = 0; i < mEmbeddingStack.Length(); ++i) {
 201       mBuffer.Append(mEmbeddingStack[i]);
 202       mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
 203       mLinePerFrame.AppendElement((nsLineBox*)nullptr);
 204     }
 205   }
 206
 207   void ResetForNewBlock()
 208   {
 209     for (BidiParagraphData* bpd = this; bpd; bpd = bpd->mSubParagraph) {
 210       bpd->mPrevFrame = nullptr;
 211     }
 212   }
 213
 214   void AppendFrame(nsIFrame* aFrame,
 215                    nsBlockInFlowLineIterator* aLineIter,
 216                    nsIContent* aContent = nullptr)
 217   {
 218     if (aContent) {
 219       mContentToFrameIndex.Put(aContent, FrameCount());
 220     }
 221     mLogicalFrames.AppendElement(aFrame);
 222
 223     AdvanceLineIteratorToFrame(aFrame, aLineIter, mPrevFrame);
 224     mLinePerFrame.AppendElement(aLineIter->GetLine().get());
 225   }
 226
 227   void AdvanceAndAppendFrame(nsIFrame** aFrame,
 228                              nsBlockInFlowLineIterator* aLineIter,
 229                              nsIFrame** aNextSibling)
 230   {
 231     nsIFrame* frame = *aFrame;
 232     nsIFrame* nextSibling = *aNextSibling;
 233
 234     frame = frame->GetNextContinuation();
 235     if (frame) {
 236       AppendFrame(frame, aLineIter, nullptr);
 237
 238       /*
 239        * If we have already overshot the saved next-sibling while
 240        * scanning the frame's continuations, advance it.
 241        */
 242       if (frame == nextSibling) {
 243         nextSibling = frame->GetNextSibling();
 244       }
 245     }
 246
 247     *aFrame = frame;
 248     *aNextSibling = nextSibling;
 249   }
 250
 251   int32_t GetLastFrameForContent(nsIContent *aContent)
 252   {
 253     int32_t index = 0;
 254     mContentToFrameIndex.Get(aContent, &index);
 255     return index;
 256   }
 257
 258   int32_t FrameCount(){ return mLogicalFrames.Length(); }
 259
 260   int32_t BufferLength(){ return mBuffer.Length(); }
 261
 262   nsIFrame* FrameAt(int32_t aIndex){ return mLogicalFrames[aIndex]; }
 263
 264   nsLineBox* GetLineForFrameAt(int32_t aIndex){ return mLinePerFrame[aIndex]; }
 265
 266   void AppendUnichar(char16_t aCh){ mBuffer.Append(aCh); }
 267
 268   void AppendString(const nsDependentSubstring& aString){ mBuffer.Append(aString); }
 269
 270   void AppendControlChar(char16_t aCh)
 271   {
 272     mLogicalFrames.AppendElement(NS_BIDI_CONTROL_FRAME);
 273     mLinePerFrame.AppendElement((nsLineBox*)nullptr);
 274     AppendUnichar(aCh);
 275   }
 276
 277   void PushBidiControl(char16_t aCh)
 278   {
 279     AppendControlChar(aCh);
 280     mEmbeddingStack.AppendElement(aCh);
 281   }
 282
 283   void PopBidiControl()
 284   {
 285     AppendControlChar(kPDF);
 286     NS_ASSERTION(mEmbeddingStack.Length(), "embedding/override underflow");
 287     mEmbeddingStack.TruncateLength(mEmbeddingStack.Length() - 1);
 288   }
 289
 290   void ClearBidiControls()
 291   {
 292     for (uint32_t i = 0; i < mEmbeddingStack.Length(); ++i) {
 293       AppendControlChar(kPDF);
 294     }
 295   }
 296
 297   static bool
 298   IsFrameInCurrentLine(nsBlockInFlowLineIterator* aLineIter,
 299                        nsIFrame* aPrevFrame, nsIFrame* aFrame)
 300   {
 301     nsIFrame* endFrame = aLineIter->IsLastLineInList() ? nullptr :
 302       aLineIter->GetLine().next()->mFirstChild;
 303     nsIFrame* startFrame = aPrevFrame ? aPrevFrame : aLineIter->GetLine()->mFirstChild;
 304     for (nsIFrame* frame = startFrame; frame && frame != endFrame;
 305          frame = frame->GetNextSibling()) {
 306       if (frame == aFrame)
 307         return true;
 308     }
 309     return false;
 310   }
 311
 312   static void
 313   AdvanceLineIteratorToFrame(nsIFrame* aFrame,
 314                              nsBlockInFlowLineIterator* aLineIter,
 315                              nsIFrame*& aPrevFrame)
 316   {
 317     // Advance aLine to the line containing aFrame
 318     nsIFrame* child = aFrame;
 319     nsIFrame* parent = nsLayoutUtils::GetParentOrPlaceholderFor(child);
 320     while (parent && !nsLayoutUtils::GetAsBlock(parent)) {
 321       child = parent;
 322       parent = nsLayoutUtils::GetParentOrPlaceholderFor(child);
 323     }
 324     NS_ASSERTION (parent, "aFrame is not a descendent of aBlockFrame");
 325     while (!IsFrameInCurrentLine(aLineIter, aPrevFrame, child)) {
 326 #ifdef DEBUG
 327       bool hasNext =
 328 #endif
 329         aLineIter->Next();
 330       NS_ASSERTION(hasNext, "Can't find frame in lines!");
 331       aPrevFrame = nullptr;
 332     }
 333     aPrevFrame = child;
 334   }
 335
 336 };
 337
 338 struct BidiLineData {
 339   nsTArray<nsIFrame*> mLogicalFrames;
 340   nsTArray<nsIFrame*> mVisualFrames;
 341   nsTArray<int32_t> mIndexMap;
 342   nsAutoTArray<uint8_t, 18> mLevels;
 343   bool mIsReordered;
 344
 345   BidiLineData(nsIFrame* aFirstFrameOnLine, int32_t   aNumFramesOnLine)
 346   {
 347     /**
 348      * Initialize the logically-ordered array of frames using the top-level
 349      * frames of a single line
 350      */
 351     mLogicalFrames.Clear();
 352
 353     bool isReordered = false;
 354     bool hasRTLFrames = false;
 355
 356     for (nsIFrame* frame = aFirstFrameOnLine;
 357          frame && aNumFramesOnLine--;
 358          frame = frame->GetNextSibling()) {
 359       AppendFrame(frame);
 360       uint8_t level = nsBidiPresUtils::GetFrameEmbeddingLevel(frame);
 361       mLevels.AppendElement(level);
 362       mIndexMap.AppendElement(0);
 363       if (level & 1) {
 364         hasRTLFrames = true;
 365       }
 366     }
 367
 368     // Reorder the line
 369     nsBidi::ReorderVisual(mLevels.Elements(), FrameCount(),
 370                           mIndexMap.Elements());
 371
 372     for (int32_t i = 0; i < FrameCount(); i++) {
 373       mVisualFrames.AppendElement(LogicalFrameAt(mIndexMap[i]));
 374       if (i != mIndexMap[i]) {
 375         isReordered = true;
 376       }
 377     }
 378
 379     // If there's an RTL frame, assume the line is reordered
 380     mIsReordered = isReordered || hasRTLFrames;
 381   }
 382
 383   void AppendFrame(nsIFrame* aFrame)
 384   {
 385     mLogicalFrames.AppendElement(aFrame);
 386   }
 387
 388   int32_t FrameCount(){ return mLogicalFrames.Length(); }
 389
 390   nsIFrame* LogicalFrameAt(int32_t aIndex){ return mLogicalFrames[aIndex]; }
 391
 392   nsIFrame* VisualFrameAt(int32_t aIndex){ return mVisualFrames[aIndex]; }
 393 };
 394
 395 /* Some helper methods for Resolve() */
 396
 397 // Should this frame be split between text runs?
 398 static bool
 399 IsBidiSplittable(nsIFrame* aFrame)
 400 {
 401   // Bidi inline containers should be split, unless they're line frames.
 402   nsIAtom* frameType = aFrame->GetType();
 403   return (aFrame->IsFrameOfType(nsIFrame::eBidiInlineContainer) &&
 404           frameType != nsGkAtoms::lineFrame) ||
 405          frameType == nsGkAtoms::textFrame;
 406 }
 407
 408 // Should this frame be treated as a leaf (e.g. when building mLogicalFrames)?
 409 static bool
 410 IsBidiLeaf(nsIFrame* aFrame)
 411 {
 412   nsIFrame* kid = aFrame->GetFirstPrincipalChild();
 413   return !kid || !aFrame->IsFrameOfType(nsIFrame::eBidiInlineContainer);
 414 }
 415
 416 /**
 417  * Create non-fluid continuations for the ancestors of a given frame all the way
 418  * up the frame tree until we hit a non-splittable frame (a line or a block).
 419  *
 420  * @param aParent the first parent frame to be split
 421  * @param aFrame the child frames after this frame are reparented to the
 422  *        newly-created continuation of aParent.
 423  *        If aFrame is null, all the children of aParent are reparented.
 424  */
 425 static nsresult
 426 SplitInlineAncestors(nsContainerFrame* aParent,
 427                      nsIFrame* aFrame)
 428 {
 429   nsPresContext* presContext = aParent->PresContext();
 430   nsIPresShell* presShell = presContext->PresShell();
 431   nsIFrame* frame = aFrame;
 432   nsContainerFrame* parent = aParent;
 433   nsContainerFrame* newParent;
 434
 435   while (IsBidiSplittable(parent)) {
 436     nsContainerFrame* grandparent = parent->GetParent();
 437     NS_ASSERTION(grandparent, "Couldn't get parent's parent in nsBidiPresUtils::SplitInlineAncestors");
 438
 439     // Split the child list after |frame|, unless it is the last child.
 440     if (!frame || frame->GetNextSibling()) {
 441
 442       newParent = static_cast<nsContainerFrame*>(presShell->FrameConstructor()->
 443         CreateContinuingFrame(presContext, parent, grandparent, false));
 444
 445       nsFrameList tail = parent->StealFramesAfter(frame);
 446
 447       // Reparent views as necessary
 448       nsresult rv;
 449       rv = nsContainerFrame::ReparentFrameViewList(tail, parent, newParent);
 450       if (NS_FAILED(rv)) {
 451         return rv;
 452       }
 453
 454       // The parent's continuation adopts the siblings after the split.
 455       newParent->InsertFrames(nsIFrame::kNoReflowPrincipalList, nullptr, tail);
 456
 457       // The list name kNoReflowPrincipalList would indicate we don't want reflow
 458       nsFrameList temp(newParent, newParent);
 459       grandparent->InsertFrames(nsIFrame::kNoReflowPrincipalList, parent, temp);
 460     }
 461
 462     frame = parent;
 463     parent = grandparent;
 464   }
 465
 466   return NS_OK;
 467 }
 468
 469 static void
 470 MakeContinuationFluid(nsIFrame* aFrame, nsIFrame* aNext)
 471 {
 472   NS_ASSERTION (!aFrame->GetNextInFlow() || aFrame->GetNextInFlow() == aNext,
 473                 "next-in-flow is not next continuation!");
 474   aFrame->SetNextInFlow(aNext);
 475
 476   NS_ASSERTION (!aNext->GetPrevInFlow() || aNext->GetPrevInFlow() == aFrame,
 477                 "prev-in-flow is not prev continuation!");
 478   aNext->SetPrevInFlow(aFrame);
 479 }
 480
 481 static void
 482 MakeContinuationsNonFluidUpParentChain(nsIFrame* aFrame, nsIFrame* aNext)
 483 {
 484   nsIFrame* frame;
 485   nsIFrame* next;
 486
 487   for (frame = aFrame, next = aNext;
 488        frame && next &&
 489          next != frame && next == frame->GetNextInFlow() &&
 490          IsBidiSplittable(frame);
 491        frame = frame->GetParent(), next = next->GetParent()) {
 492
 493     frame->SetNextContinuation(next);
 494     next->SetPrevContinuation(frame);
 495   }
 496 }
 497
 498 // If aFrame is the last child of its parent, convert bidi continuations to
 499 // fluid continuations for all of its inline ancestors.
 500 // If it isn't the last child, make sure that its continuation is fluid.
 501 static void
 502 JoinInlineAncestors(nsIFrame* aFrame)
 503 {
 504   nsIFrame* frame = aFrame;
 505   do {
 506     nsIFrame* next = frame->GetNextContinuation();
 507     if (next) {
 508       // Don't join frames if they come from different paragraph depths (i.e.
 509       // one is bidi isolated relative to the other
 510       if (nsBidiPresUtils::GetParagraphDepth(frame) ==
 511           nsBidiPresUtils::GetParagraphDepth(next)) {
 512         MakeContinuationFluid(frame, next);
 513       }
 514     }
 515     // Join the parent only as long as we're its last child.
 516     if (frame->GetNextSibling())
 517       break;
 518     frame = frame->GetParent();
 519   } while (frame && IsBidiSplittable(frame));
 520 }
 521
 522 static nsresult
 523 CreateContinuation(nsIFrame*  aFrame,
 524                    nsIFrame** aNewFrame,
 525                    bool       aIsFluid)
 526 {
 527   NS_PRECONDITION(aNewFrame, "null OUT ptr");
 528   NS_PRECONDITION(aFrame, "null ptr");
 529
 530   *aNewFrame = nullptr;
 531
 532   nsPresContext *presContext = aFrame->PresContext();
 533   nsIPresShell *presShell = presContext->PresShell();
 534   NS_ASSERTION(presShell, "PresShell must be set on PresContext before calling nsBidiPresUtils::CreateContinuation");
 535
 536   nsContainerFrame* parent = aFrame->GetParent();
 537   NS_ASSERTION(parent, "Couldn't get frame parent in nsBidiPresUtils::CreateContinuation");
 538
 539   nsresult rv = NS_OK;
 540
 541   // Have to special case floating first letter frames because the continuation
 542   // doesn't go in the first letter frame. The continuation goes with the rest
 543   // of the text that the first letter frame was made out of.
 544   if (parent->GetType() == nsGkAtoms::letterFrame &&
 545       parent->IsFloating()) {
 546     nsFirstLetterFrame* letterFrame = do_QueryFrame(parent);
 547     rv = letterFrame->CreateContinuationForFloatingParent(presContext, aFrame,
 548                                                           aNewFrame, aIsFluid);
 549     return rv;
 550   }
 551
 552   *aNewFrame = presShell->FrameConstructor()->
 553     CreateContinuingFrame(presContext, aFrame, parent, aIsFluid);
 554
 555   // The list name kNoReflowPrincipalList would indicate we don't want reflow
 556   // XXXbz this needs higher-level framelist love
 557   nsFrameList temp(*aNewFrame, *aNewFrame);
 558   parent->InsertFrames(nsIFrame::kNoReflowPrincipalList, aFrame, temp);
 559
 560   if (!aIsFluid) {
 561     // Split inline ancestor frames
 562     rv = SplitInlineAncestors(parent, aFrame);
 563     if (NS_FAILED(rv)) {
 564       return rv;
 565     }
 566   }
 567
 568   return NS_OK;
 569 }
 570
 571 /*
 572  * Overview of the implementation of Resolve():
 573  *
 574  *  Walk through the descendants of aBlockFrame and build:
 575  *   * mLogicalFrames: an nsTArray of nsIFrame* pointers in logical order
 576  *   * mBuffer: an nsString containing a representation of
 577  *     the content of the frames.
 578  *     In the case of text frames, this is the actual text context of the
 579  *     frames, but some other elements are represented in a symbolic form which
 580  *     will make the Unicode Bidi Algorithm give the correct results.
 581  *     Bidi embeddings and overrides set by CSS or <bdo> elements are
 582  *     represented by the corresponding Unicode control characters.
 583  *     <br> elements are represented by U+2028 LINE SEPARATOR
 584  *     Other inline elements are represented by U+FFFC OBJECT REPLACEMENT
 585  *     CHARACTER
 586  *
 587  *  Then pass mBuffer to the Bidi engine for resolving of embedding levels
 588  *  by nsBidi::SetPara() and division into directional runs by
 589  *  nsBidi::CountRuns().
 590  *
 591  *  Finally, walk these runs in logical order using nsBidi::GetLogicalRun() and
 592  *  correlate them with the frames indexed in mLogicalFrames, setting the
 593  *  baseLevel and embeddingLevel properties according to the results returned
 594  *  by the Bidi engine.
 595  *
 596  *  The rendering layer requires each text frame to contain text in only one
 597  *  direction, so we may need to call EnsureBidiContinuation() to split frames.
 598  *  We may also need to call RemoveBidiContinuation() to convert frames created
 599  *  by EnsureBidiContinuation() in previous reflows into fluid continuations.
 600  */
 601 nsresult
 602 nsBidiPresUtils::Resolve(nsBlockFrame* aBlockFrame)
 603 {
 604   BidiParagraphData bpd;
 605   bpd.Init(aBlockFrame);
 606
 607   // Handle bidi-override being set on the block itself before calling
 608   // TraverseFrames.
 609   const nsStyleTextReset* text = aBlockFrame->StyleTextReset();
 610   char16_t ch = 0;
 611   if (text->mUnicodeBidi & NS_STYLE_UNICODE_BIDI_OVERRIDE) {
 612     const nsStyleVisibility* vis = aBlockFrame->StyleVisibility();
 613     if (NS_STYLE_DIRECTION_RTL == vis->mDirection) {
 614       ch = kRLO;
 615     }
 616     else if (NS_STYLE_DIRECTION_LTR == vis->mDirection) {
 617       ch = kLRO;
 618     }
 619     if (ch != 0) {
 620       bpd.PushBidiControl(ch);
 621     }
 622   }
 623   for (nsBlockFrame* block = aBlockFrame; block;
 624        block = static_cast<nsBlockFrame*>(block->GetNextContinuation())) {
 625     block->RemoveStateBits(NS_BLOCK_NEEDS_BIDI_RESOLUTION);
 626     nsBlockInFlowLineIterator lineIter(block, block->begin_lines());
 627     bpd.ResetForNewBlock();
 628     TraverseFrames(aBlockFrame, &lineIter, block->GetFirstPrincipalChild(), &bpd);
 629     // XXX what about overflow lines?
 630   }
 631
 632   if (ch != 0) {
 633     bpd.PopBidiControl();
 634   }
 635
 636   BidiParagraphData* subParagraph = bpd.GetSubParagraph();
 637   if (subParagraph->BufferLength()) {
 638     ResolveParagraph(aBlockFrame, subParagraph);
 639     subParagraph->EmptyBuffer();
 640   }
 641   return ResolveParagraph(aBlockFrame, &bpd);
 642 }
 643
 644 nsresult
 645 nsBidiPresUtils::ResolveParagraph(nsBlockFrame* aBlockFrame,
 646                                   BidiParagraphData* aBpd)
 647 {
 648   nsPresContext *presContext = aBlockFrame->PresContext();
 649
 650   if (aBpd->BufferLength() < 1) {
 651     return NS_OK;
 652   }
 653   aBpd->mBuffer.ReplaceChar(kSeparators, kSpace);
 654
 655   int32_t runCount;
 656
 657   nsresult rv = aBpd->SetPara();
 658   NS_ENSURE_SUCCESS(rv, rv);
 659
 660   uint8_t embeddingLevel = aBpd->GetParaLevel();
 661
 662   rv = aBpd->CountRuns(&runCount);
 663   NS_ENSURE_SUCCESS(rv, rv);
 664
 665   int32_t     runLength      = 0;   // the length of the current run of text
 666   int32_t     lineOffset     = 0;   // the start of the current run
 667   int32_t     logicalLimit   = 0;   // the end of the current run + 1
 668   int32_t     numRun         = -1;
 669   int32_t     fragmentLength = 0;   // the length of the current text frame
 670   int32_t     frameIndex     = -1;  // index to the frames in mLogicalFrames
 671   int32_t     frameCount     = aBpd->FrameCount();
 672   int32_t     contentOffset  = 0;   // offset of current frame in its content node
 673   bool        isTextFrame    = false;
 674   nsIFrame*   frame = nullptr;
 675   nsIContent* content = nullptr;
 676   int32_t     contentTextLength = 0;
 677
 678   FramePropertyTable *propTable = presContext->PropertyTable();
 679   nsLineBox* currentLine = nullptr;
 680
 681 #ifdef DEBUG
 682 #ifdef NOISY_BIDI
 683   printf("Before Resolve(), aBlockFrame=0x%p, mBuffer='%s', frameCount=%d, runCount=%d\n",
 684          (void*)aBlockFrame, NS_ConvertUTF16toUTF8(aBpd->mBuffer).get(), frameCount, runCount);
 685 #ifdef REALLY_NOISY_BIDI
 686   printf(" block frame tree=:\n");
 687   aBlockFrame->List(stdout, 0);
 688 #endif
 689 #endif
 690 #endif
 691
 692   if (runCount == 1 && frameCount == 1 &&
 693       aBpd->mParagraphDepth == 0 && aBpd->GetDirection() == NSBIDI_LTR &&
 694       aBpd->GetParaLevel() == 0) {
 695     // We have a single left-to-right frame in a left-to-right paragraph,
 696     // without bidi isolation from the surrounding text.
 697     // Make sure that the embedding level and base level frame properties aren't
 698     // set (because if they are this frame used to have some other direction,
 699     // so we can't do this optimization), and we're done.
 700     nsIFrame* frame = aBpd->FrameAt(0);
 701     if (frame != NS_BIDI_CONTROL_FRAME &&
 702         !frame->Properties().Get(nsIFrame::EmbeddingLevelProperty()) &&
 703         !frame->Properties().Get(nsIFrame::BaseLevelProperty())) {
 704 #ifdef DEBUG
 705 #ifdef NOISY_BIDI
 706       printf("early return for single direction frame %p\n", (void*)frame);
 707 #endif
 708 #endif
 709       frame->AddStateBits(NS_FRAME_IS_BIDI);
 710       return NS_OK;
 711     }
 712   }
 713
 714   nsIFrame* firstFrame = nullptr;
 715   nsIFrame* lastFrame = nullptr;
 716
 717   for (; ;) {
 718     if (fragmentLength <= 0) {
 719       // Get the next frame from mLogicalFrames
 720       if (++frameIndex >= frameCount) {
 721         break;
 722       }
 723       frame = aBpd->FrameAt(frameIndex);
 724       if (frame == NS_BIDI_CONTROL_FRAME ||
 725           nsGkAtoms::textFrame != frame->GetType()) {
 726         /*
 727          * Any non-text frame corresponds to a single character in the text buffer
 728          * (a bidi control character, LINE SEPARATOR, or OBJECT SUBSTITUTE)
 729          */
 730         isTextFrame = false;
 731         fragmentLength = 1;
 732       }
 733       else {
 734         if (!firstFrame) {
 735           firstFrame = frame;
 736         }
 737         lastFrame = frame;
 738         currentLine = aBpd->GetLineForFrameAt(frameIndex);
 739         content = frame->GetContent();
 740         if (!content) {
 741           rv = NS_OK;
 742           break;
 743         }
 744         contentTextLength = content->TextLength();
 745         if (contentTextLength == 0) {
 746           frame->AdjustOffsetsForBidi(0, 0);
 747           // Set the base level and embedding level of the current run even
 748           // on an empty frame. Otherwise frame reordering will not be correct.
 749           propTable->Set(frame, nsIFrame::EmbeddingLevelProperty(),
 750                          NS_INT32_TO_PTR(embeddingLevel));
 751           propTable->Set(frame, nsIFrame::BaseLevelProperty(),
 752                          NS_INT32_TO_PTR(aBpd->GetParaLevel()));
 753           propTable->Set(frame, nsIFrame::ParagraphDepthProperty(),
 754                          NS_INT32_TO_PTR(aBpd->mParagraphDepth));
 755           continue;
 756         }
 757         int32_t start, end;
 758         frame->GetOffsets(start, end);
 759         NS_ASSERTION(!(contentTextLength < end - start),
 760                      "Frame offsets don't fit in content");
 761         fragmentLength = std::min(contentTextLength, end - start);
 762         contentOffset = start;
 763         isTextFrame = true;
 764       }
 765     } // if (fragmentLength <= 0)
 766
 767     if (runLength <= 0) {
 768       // Get the next run of text from the Bidi engine
 769       if (++numRun >= runCount) {
 770         break;
 771       }
 772       lineOffset = logicalLimit;
 773       if (NS_FAILED(aBpd->GetLogicalRun(
 774               lineOffset, &logicalLimit, &embeddingLevel) ) ) {
 775         break;
 776       }
 777       runLength = logicalLimit - lineOffset;
 778     } // if (runLength <= 0)
 779
 780     if (frame == NS_BIDI_CONTROL_FRAME) {
 781       frame = nullptr;
 782       ++lineOffset;
 783     }
 784     else {
 785       propTable->Set(frame, nsIFrame::EmbeddingLevelProperty(),
 786                      NS_INT32_TO_PTR(embeddingLevel));
 787       propTable->Set(frame, nsIFrame::BaseLevelProperty(),
 788                      NS_INT32_TO_PTR(aBpd->GetParaLevel()));
 789       propTable->Set(frame, nsIFrame::ParagraphDepthProperty(),
 790                      NS_INT32_TO_PTR(aBpd->mParagraphDepth));
 791       if (isTextFrame) {
 792         if ( (runLength > 0) && (runLength < fragmentLength) ) {
 793           /*
 794            * The text in this frame continues beyond the end of this directional run.
 795            * Create a non-fluid continuation frame for the next directional run.
 796            */
 797           currentLine->MarkDirty();
 798           nsIFrame* nextBidi;
 799           int32_t runEnd = contentOffset + runLength;
 800           rv = EnsureBidiContinuation(frame, &nextBidi, frameIndex,
 801                                       contentOffset,
 802                                       runEnd);
 803           if (NS_FAILED(rv)) {
 804             break;
 805           }
 806           nextBidi->AdjustOffsetsForBidi(runEnd,
 807                                          contentOffset + fragmentLength);
 808           lastFrame = frame = nextBidi;
 809           contentOffset = runEnd;
 810         } // if (runLength < fragmentLength)
 811         else {
 812           if (contentOffset + fragmentLength == contentTextLength) {
 813             /*
 814              * We have finished all the text in this content node. Convert any
 815              * further non-fluid continuations to fluid continuations and advance
 816              * frameIndex to the last frame in the content node
 817              */
 818             int32_t newIndex = aBpd->GetLastFrameForContent(content);
 819             if (newIndex > frameIndex) {
 820               currentLine->MarkDirty();
 821               RemoveBidiContinuation(aBpd, frame,
 822                                      frameIndex, newIndex, lineOffset);
 823               frameIndex = newIndex;
 824               lastFrame = frame = aBpd->FrameAt(frameIndex);
 825             }
 826           } else if (fragmentLength > 0 && runLength > fragmentLength) {
 827             /*
 828              * There is more text that belongs to this directional run in the next
 829              * text frame: make sure it is a fluid continuation of the current frame.
 830              * Do not advance frameIndex, because the next frame may contain
 831              * multi-directional text and need to be split
 832              */
 833             int32_t newIndex = frameIndex;
 834             do {
 835             } while (++newIndex < frameCount &&
 836                      aBpd->FrameAt(newIndex) == NS_BIDI_CONTROL_FRAME);
 837             if (newIndex < frameCount) {
 838               currentLine->MarkDirty();
 839               RemoveBidiContinuation(aBpd, frame,
 840                                      frameIndex, newIndex, lineOffset);
 841             }
 842           } else if (runLength == fragmentLength) {
 843             /*
 844              * If the directional run ends at the end of the frame, make sure
 845              * that any continuation is non-fluid, and do the same up the
 846              * parent chain
 847              */
 848             nsIFrame* next = frame->GetNextInFlow();
 849             if (next) {
 850               currentLine->MarkDirty();
 851               MakeContinuationsNonFluidUpParentChain(frame, next);
 852             }
 853           }
 854           frame->AdjustOffsetsForBidi(contentOffset, contentOffset + fragmentLength);
 855         }
 856       } // isTextFrame
 857       else {
 858         ++lineOffset;
 859       }
 860     } // not bidi control frame
 861     int32_t temp = runLength;
 862     runLength -= fragmentLength;
 863     fragmentLength -= temp;
 864
 865     if (frame && fragmentLength <= 0) {
 866       // If the frame is at the end of a run, and this is not the end of our
 867       // paragrah, split all ancestor inlines that need splitting.
 868       // To determine whether we're at the end of the run, we check that we've
 869       // finished processing the current run, and that the current frame
 870       // doesn't have a fluid continuation (it could have a fluid continuation
 871       // of zero length, so testing runLength alone is not sufficient).
 872       if (runLength <= 0 && !frame->GetNextInFlow()) {
 873         if (numRun + 1 < runCount) {
 874           nsIFrame* child = frame;
 875           nsContainerFrame* parent = frame->GetParent();
 876           // As long as we're on the last sibling, the parent doesn't have to
 877           // be split.
 878           // However, if the parent has a fluid continuation, we do have to make
 879           // it non-fluid. This can happen e.g. when we have a first-letter
 880           // frame and the end of the first-letter coincides with the end of a
 881           // directional run.
 882           while (parent &&
 883                  IsBidiSplittable(parent) &&
 884                  !child->GetNextSibling()) {
 885             nsIFrame* next = parent->GetNextInFlow();
 886             if (next) {
 887               parent->SetNextContinuation(next);
 888               next->SetPrevContinuation(parent);
 889             }
 890             child = parent;
 891             parent = child->GetParent();
 892           }
 893           if (parent && IsBidiSplittable(parent)) {
 894             SplitInlineAncestors(parent, child);
 895           }
 896         }
 897       }
 898       else {
 899         // We're not at an end of a run. If |frame| is the last child of its
 900         // parent, and its ancestors happen to have bidi continuations, convert
 901         // them into fluid continuations.
 902         JoinInlineAncestors(frame);
 903       }
 904     }
 905   } // for
 906
 907   if (aBpd->mParagraphDepth > 0) {
 908     if (firstFrame) {
 909       nsContainerFrame* child = firstFrame->GetParent();
 910       if (child) {
 911         nsContainerFrame* parent = child->GetParent();
 912         if (parent && IsBidiSplittable(parent)) {
 913           nsIFrame* prev = child->GetPrevSibling();
 914           if (prev) {
 915             SplitInlineAncestors(parent, prev);
 916           }
 917         }
 918       }
 919     }
 920     if (lastFrame) {
 921       nsContainerFrame* child = lastFrame->GetParent();
 922       if (child) {
 923         nsContainerFrame* parent = child->GetParent();
 924         if (parent && IsBidiSplittable(parent)) {
 925           SplitInlineAncestors(parent, child);
 926         }
 927       }
 928     }
 929   }
 930
 931 #ifdef DEBUG
 932 #ifdef REALLY_NOISY_BIDI
 933   printf("---\nAfter Resolve(), frameTree =:\n");
 934   aBlockFrame->List(stdout, 0);
 935   printf("===\n");
 936 #endif
 937 #endif
 938
 939   return rv;
 940 }
 941
 942 void
 943 nsBidiPresUtils::TraverseFrames(nsBlockFrame*              aBlockFrame,
 944                                 nsBlockInFlowLineIterator* aLineIter,
 945                                 nsIFrame*                  aCurrentFrame,
 946                                 BidiParagraphData*         aBpd)
 947 {
 948   if (!aCurrentFrame)
 949     return;
 950
 951 #ifdef DEBUG
 952   nsBlockFrame* initialLineContainer = aLineIter->GetContainer();
 953 #endif
 954
 955   nsIFrame* childFrame = aCurrentFrame;
 956   do {
 957     /*
 958      * It's important to get the next sibling and next continuation *before*
 959      * handling the frame: If we encounter a forced paragraph break and call
 960      * ResolveParagraph within this loop, doing GetNextSibling and
 961      * GetNextContinuation after that could return a bidi continuation that had
 962      * just been split from the original childFrame and we would process it
 963      * twice.
 964      */
 965     nsIFrame* nextSibling = childFrame->GetNextSibling();
 966     bool isLastFrame = !childFrame->GetNextContinuation();
 967     bool isFirstFrame = !childFrame->GetPrevContinuation();
 968
 969     // If the real frame for a placeholder is a first letter frame, we need to
 970     // drill down into it and include its contents in Bidi resolution.
 971     // If not, we just use the placeholder.
 972     nsIFrame* frame = childFrame;
 973     if (nsGkAtoms::placeholderFrame == childFrame->GetType()) {
 974       nsIFrame* realFrame =
 975         nsPlaceholderFrame::GetRealFrameForPlaceholder(childFrame);
 976       if (realFrame->GetType() == nsGkAtoms::letterFrame) {
 977         frame = realFrame;
 978       }
 979     }
 980
 981     char16_t ch = 0;
 982     if (frame->IsFrameOfType(nsIFrame::eBidiInlineContainer)) {
 983       if (!(frame->GetStateBits() & NS_FRAME_FIRST_REFLOW)) {
 984         nsContainerFrame* c = static_cast<nsContainerFrame*>(frame);
 985         MOZ_ASSERT(c = do_QueryFrame(frame),
 986                    "eBidiInlineContainer must be a nsContainerFrame subclass");
 987         c->DrainSelfOverflowList();
 988       }
 989
 990       const nsStyleVisibility* vis = frame->StyleVisibility();
 991       const nsStyleTextReset* text = frame->StyleTextReset();
 992       if (text->mUnicodeBidi & NS_STYLE_UNICODE_BIDI_OVERRIDE) {
 993         if (NS_STYLE_DIRECTION_RTL == vis->mDirection) {
 994           ch = kRLO;
 995         }
 996         else if (NS_STYLE_DIRECTION_LTR == vis->mDirection) {
 997           ch = kLRO;
 998         }
 999       } else if (text->mUnicodeBidi & NS_STYLE_UNICODE_BIDI_EMBED) {
1000         if (NS_STYLE_DIRECTION_RTL == vis->mDirection) {
1001           ch = kRLE;
1002         }
1003         else if (NS_STYLE_DIRECTION_LTR == vis->mDirection) {
1004           ch = kLRE;
1005         }
1006       }
1007
1008       // Add a dummy frame pointer representing a bidi control code before the
1009       // first frame of an element specifying embedding or override
1010       if (ch != 0 && isFirstFrame) {
1011         aBpd->PushBidiControl(ch);
1012       }
1013     }
1014
1015     if (IsBidiLeaf(frame)) {
1016       /* Bidi leaf frame: add the frame to the mLogicalFrames array,
1017        * and add its index to the mContentToFrameIndex hashtable. This
1018        * will be used in RemoveBidiContinuation() to identify the last
1019        * frame in the array with a given content.
1020        */
1021       nsIContent* content = frame->GetContent();
1022       aBpd->AppendFrame(frame, aLineIter, content);
1023
1024       // Append the content of the frame to the paragraph buffer
1025       nsIAtom* frameType = frame->GetType();
1026       if (nsGkAtoms::textFrame == frameType) {
1027         if (content != aBpd->mPrevContent) {
1028           aBpd->mPrevContent = content;
1029           if (!frame->StyleText()->NewlineIsSignificant()) {
1030             content->AppendTextTo(aBpd->mBuffer);
1031           } else {
1032             /*
1033              * For preformatted text we have to do bidi resolution on each line
1034              * separately.
1035              */
1036             nsAutoString text;
1037             content->AppendTextTo(text);
1038             nsIFrame* next;
1039             do {
1040               next = nullptr;
1041
1042               int32_t start, end;
1043               frame->GetOffsets(start, end);
1044               int32_t endLine = text.FindChar('\n', start);
1045               if (endLine == -1) {
1046                 /*
1047                  * If there is no newline in the text content, just save the
1048                  * text from this frame and its continuations, and do bidi
1049                  * resolution later
1050                  */
1051                 aBpd->AppendString(Substring(text, start));
1052                 while (frame && nextSibling) {
1053                   aBpd->AdvanceAndAppendFrame(&frame, aLineIter, &nextSibling);
1054                 }
1055                 break;
1056               }
1057
1058               /*
1059                * If there is a newline in the frame, break the frame after the
1060                * newline, do bidi resolution and repeat until the last sibling
1061                */
1062               ++endLine;
1063
1064               /*
1065                * If the frame ends before the new line, save the text and move
1066                * into the next continuation
1067                */
1068               aBpd->AppendString(Substring(text, start,
1069                                            std::min(end, endLine) - start));
1070               while (end < endLine && nextSibling) {
1071                 aBpd->AdvanceAndAppendFrame(&frame, aLineIter, &nextSibling);
1072                 NS_ASSERTION(frame, "Premature end of continuation chain");
1073                 frame->GetOffsets(start, end);
1074                 aBpd->AppendString(Substring(text, start,
1075                                              std::min(end, endLine) - start));
1076               }
1077
1078               if (end < endLine) {
1079                 aBpd->mPrevContent = nullptr;
1080                 break;
1081               }
1082
1083               bool createdContinuation = false;
1084               if (uint32_t(endLine) < text.Length()) {
1085                 /*
1086                  * Timing is everything here: if the frame already has a bidi
1087                  * continuation, we need to make the continuation fluid *before*
1088                  * resetting the length of the current frame. Otherwise
1089                  * nsTextFrame::SetLength won't set the continuation frame's
1090                  * text offsets correctly.
1091                  *
1092                  * On the other hand, if the frame doesn't have a continuation,
1093                  * we need to create one *after* resetting the length, or
1094                  * CreateContinuingFrame will complain that there is no more
1095                  * content for the continuation.
1096                  */
1097                 next = frame->GetNextInFlow();
1098                 if (!next) {
1099                   // If the frame already has a bidi continuation, make it fluid
1100                   next = frame->GetNextContinuation();
1101                   if (next) {
1102                     MakeContinuationFluid(frame, next);
1103                     JoinInlineAncestors(frame);
1104                   }
1105                 }
1106
1107                 nsTextFrame* textFrame = static_cast<nsTextFrame*>(frame);
1108                 textFrame->SetLength(endLine - start, nullptr);
1109
1110                 if (!next) {
1111                   // If the frame has no next in flow, create one.
1112                   CreateContinuation(frame, &next, true);
1113                   createdContinuation = true;
1114                 }
1115                 // Mark the line before the newline as dirty.
1116                 aBpd->GetLineForFrameAt(aBpd->FrameCount() - 1)->MarkDirty();
1117               }
1118               ResolveParagraphWithinBlock(aBlockFrame, aBpd);
1119
1120               if (!nextSibling && !createdContinuation) {
1121                 break;
1122               } else if (next) {
1123                 frame = next;
1124                 aBpd->AppendFrame(frame, aLineIter);
1125                 // Mark the line after the newline as dirty.
1126                 aBpd->GetLineForFrameAt(aBpd->FrameCount() - 1)->MarkDirty();
1127               }
1128
1129               /*
1130                * If we have already overshot the saved next-sibling while
1131                * scanning the frame's continuations, advance it.
1132                */
1133               if (frame && frame == nextSibling) {
1134                 nextSibling = frame->GetNextSibling();
1135               }
1136
1137             } while (next);
1138           }
1139         }
1140       } else if (nsGkAtoms::brFrame == frameType) {
1141         // break frame -- append line separator
1142         aBpd->AppendUnichar(kLineSeparator);
1143         ResolveParagraphWithinBlock(aBlockFrame, aBpd);
1144       } else {
1145         // other frame type -- see the Unicode Bidi Algorithm:
1146         // "...inline objects (such as graphics) are treated as if they are ...
1147         // U+FFFC"
1148         // <wbr>, however, is treated as U+200B ZERO WIDTH SPACE. See
1149         // http://dev.w3.org/html5/spec/Overview.html#phrasing-content-1
1150         aBpd->AppendUnichar(content->IsHTML(nsGkAtoms::wbr) ?
1151                             kZWSP : kObjectSubstitute);
1152         if (!frame->IsInlineOutside()) {
1153           // if it is not inline, end the paragraph
1154           ResolveParagraphWithinBlock(aBlockFrame, aBpd);
1155         }
1156       }
1157     } else {
1158       // For a non-leaf frame, recurse into TraverseFrames
1159       nsIFrame* kid = frame->GetFirstPrincipalChild();
1160       MOZ_ASSERT(!frame->GetFirstChild(nsIFrame::kOverflowList),
1161                  "should have drained the overflow list above");
1162       if (kid) {
1163         const nsStyleTextReset* text = frame->StyleTextReset();
1164         if (text->mUnicodeBidi & NS_STYLE_UNICODE_BIDI_ISOLATE ||
1165             text->mUnicodeBidi & NS_STYLE_UNICODE_BIDI_PLAINTEXT) {
1166           // css "unicode-bidi: isolate" and html5 bdi:
1167           //  resolve the element as a separate paragraph
1168           BidiParagraphData* subParagraph = aBpd->GetSubParagraph();
1169
1170           /*
1171            * As at the beginning of the loop, it's important to check for
1172            * next-continuations before handling the frame. If we do
1173            * TraverseFrames and *then* do GetNextContinuation on the original
1174            * first frame, it could return a bidi continuation that had only
1175            * just been created, and we would skip doing bidi resolution on the
1176            * last part of the sub-paragraph.
1177            */
1178           bool isLastContinuation = !frame->GetNextContinuation();
1179           if (!frame->GetPrevContinuation() || !subParagraph->mReset) {
1180             if (subParagraph->BufferLength()) {
1181               ResolveParagraph(aBlockFrame, subParagraph);
1182             }
1183             subParagraph->Reset(frame, aBpd);
1184           }
1185           TraverseFrames(aBlockFrame, aLineIter, kid, subParagraph);
1186           if (isLastContinuation) {
1187             ResolveParagraph(aBlockFrame, subParagraph);
1188             subParagraph->EmptyBuffer();
1189           }
1190
1191           // Treat the element as a neutral character within its containing
1192           //  paragraph.
1193           aBpd->AppendControlChar(kObjectSubstitute);
1194         } else {
1195           TraverseFrames(aBlockFrame, aLineIter, kid, aBpd);
1196         }
1197       }
1198     }
1199
1200     // If the element is attributed by dir, indicate direction pop (add PDF frame)
1201     if (isLastFrame) {
1202       if (ch) {
1203         // Add a dummy frame pointer representing a bidi control code after the
1204         // last frame of an element specifying embedding or override
1205         aBpd->PopBidiControl();
1206       }
1207     }
1208     childFrame = nextSibling;
1209   } while (childFrame);
1210
1211   MOZ_ASSERT(initialLineContainer == aLineIter->GetContainer());
1212 }
1213
1214 void
1215 nsBidiPresUtils::ResolveParagraphWithinBlock(nsBlockFrame* aBlockFrame,
1216                                              BidiParagraphData* aBpd)
1217 {
1218   aBpd->ClearBidiControls();
1219   ResolveParagraph(aBlockFrame, aBpd);
1220   aBpd->ResetData();
1221 }
1222
1223 void
1224 nsBidiPresUtils::ReorderFrames(nsIFrame*   aFirstFrameOnLine,
1225                                int32_t     aNumFramesOnLine,
1226                                WritingMode aLineWM,
1227                                nscoord&    aLineWidth)
1228 {
1229   // If this line consists of a line frame, reorder the line frame's children.
1230   if (aFirstFrameOnLine->GetType() == nsGkAtoms::lineFrame) {
1231     aFirstFrameOnLine = aFirstFrameOnLine->GetFirstPrincipalChild();
1232     if (!aFirstFrameOnLine)
1233       return;
1234     // All children of the line frame are on the first line. Setting aNumFramesOnLine
1235     // to -1 makes InitLogicalArrayFromLine look at all of them.
1236     aNumFramesOnLine = -1;
1237   }
1238
1239   BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
1240   RepositionInlineFrames(&bld, aFirstFrameOnLine, aLineWM, aLineWidth);
1241 }
1242
1243 nsIFrame*
1244 nsBidiPresUtils::GetFirstLeaf(nsIFrame* aFrame)
1245 {
1246   nsIFrame* firstLeaf = aFrame;
1247   while (!IsBidiLeaf(firstLeaf)) {
1248     nsIFrame* firstChild = firstLeaf->GetFirstPrincipalChild();
1249     nsIFrame* realFrame = nsPlaceholderFrame::GetRealFrameFor(firstChild);
1250     firstLeaf = (realFrame->GetType() == nsGkAtoms::letterFrame) ?
1251                  realFrame : firstChild;
1252   }
1253   return firstLeaf;
1254 }
1255
1256 nsBidiLevel
1257 nsBidiPresUtils::GetFrameEmbeddingLevel(nsIFrame* aFrame)
1258 {
1259   return NS_GET_EMBEDDING_LEVEL(nsBidiPresUtils::GetFirstLeaf(aFrame));
1260 }
1261
1262 uint8_t
1263 nsBidiPresUtils::GetParagraphDepth(nsIFrame* aFrame)
1264 {
1265   return NS_GET_PARAGRAPH_DEPTH(nsBidiPresUtils::GetFirstLeaf(aFrame));
1266 }
1267
1268
1269 nsBidiLevel
1270 nsBidiPresUtils::GetFrameBaseLevel(nsIFrame* aFrame)
1271 {
1272   nsIFrame* firstLeaf = aFrame;
1273   while (!IsBidiLeaf(firstLeaf)) {
1274     firstLeaf = firstLeaf->GetFirstPrincipalChild();
1275   }
1276   return NS_GET_BASE_LEVEL(firstLeaf);
1277 }
1278
1279 void
1280 nsBidiPresUtils::IsFirstOrLast(nsIFrame*             aFrame,
1281                                nsContinuationStates* aContinuationStates,
1282                                bool&                 aIsFirst /* out */,
1283                                bool&                 aIsLast /* out */)
1284 {
1285   /*
1286    * Since we lay out frames in the line's direction, visiting a frame with
1287    * 'mFirstVisualFrame == nullptr', means it's the first appearance of one
1288    * of its continuation chain frames on the line.
1289    * To determine if it's the last visual frame of its continuation chain on
1290    * the line or not, we count the number of frames of the chain on the line,
1291    * and then reduce it when we lay out a frame of the chain. If this value
1292    * becomes 1 it means that it's the last visual frame of its continuation
1293    * chain on this line.
1294    */
1295
1296   nsFrameContinuationState* frameState = aContinuationStates->GetEntry(aFrame);
1297   nsFrameContinuationState* firstFrameState;
1298
1299   if (!frameState->mFirstVisualFrame) {
1300     // aFrame is the first visual frame of its continuation chain
1301     nsFrameContinuationState* contState;
1302     nsIFrame* frame;
1303
1304     frameState->mFrameCount = 1;
1305     frameState->mFirstVisualFrame = aFrame;
1306
1307     /**
1308      * Traverse continuation chain of aFrame in both backward and forward
1309      * directions while the frames are on this line. Count the frames and
1310      * set their mFirstVisualFrame to aFrame.
1311      */
1312     // Traverse continuation chain backward
1313     for (frame = aFrame->GetPrevContinuation();
1314          frame && (contState = aContinuationStates->GetEntry(frame));
1315          frame = frame->GetPrevContinuation()) {
1316       frameState->mFrameCount++;
1317       contState->mFirstVisualFrame = aFrame;
1318     }
1319     frameState->mHasContOnPrevLines = (frame != nullptr);
1320
1321     // Traverse continuation chain forward
1322     for (frame = aFrame->GetNextContinuation();
1323          frame && (contState = aContinuationStates->GetEntry(frame));
1324          frame = frame->GetNextContinuation()) {
1325       frameState->mFrameCount++;
1326       contState->mFirstVisualFrame = aFrame;
1327     }
1328     frameState->mHasContOnNextLines = (frame != nullptr);
1329
1330     aIsFirst = !frameState->mHasContOnPrevLines;
1331     firstFrameState = frameState;
1332   } else {
1333     // aFrame is not the first visual frame of its continuation chain
1334     aIsFirst = false;
1335     firstFrameState = aContinuationStates->GetEntry(frameState->mFirstVisualFrame);
1336   }
1337
1338   aIsLast = (firstFrameState->mFrameCount == 1 &&
1339              !firstFrameState->mHasContOnNextLines);
1340
1341   if ((aIsFirst || aIsLast) &&
1342       (aFrame->GetStateBits() & NS_FRAME_PART_OF_IBSPLIT)) {
1343     // For ib splits, don't treat anything except the last part as
1344     // endmost or anything except the first part as startmost.
1345     // As an optimization, only get the first continuation once.
1346     nsIFrame* firstContinuation = aFrame->FirstContinuation();
1347     if (firstContinuation->FrameIsNonLastInIBSplit()) {
1348       // We are not endmost
1349       aIsLast = false;
1350     }
1351     if (firstContinuation->FrameIsNonFirstInIBSplit()) {
1352       // We are not startmost
1353       aIsFirst = false;
1354     }
1355   }
1356
1357   // Reduce number of remaining frames of the continuation chain on the line.
1358   firstFrameState->mFrameCount--;
1359 }
1360
1361 void
1362 nsBidiPresUtils::RepositionFrame(nsIFrame*             aFrame,
1363                                  bool                  aIsEvenLevel,
1364                                  nscoord&              aStart,
1365                                  nsContinuationStates* aContinuationStates,
1366                                  WritingMode           aLineWM,
1367                                  nscoord&              aLineWidth)
1368 {
1369   if (!aFrame)
1370     return;
1371
1372   bool isFirst, isLast;
1373   IsFirstOrLast(aFrame,
1374                 aContinuationStates,
1375                 isFirst /* out */,
1376                 isLast /* out */);
1377
1378   WritingMode frameWM = aFrame->GetWritingMode();
1379   nsInlineFrame* testFrame = do_QueryFrame(aFrame);
1380
1381   if (testFrame) {
1382     aFrame->AddStateBits(NS_INLINE_FRAME_BIDI_VISUAL_STATE_IS_SET);
1383
1384     if (isFirst) {
1385       aFrame->AddStateBits(NS_INLINE_FRAME_BIDI_VISUAL_IS_FIRST);
1386     } else {
1387       aFrame->RemoveStateBits(NS_INLINE_FRAME_BIDI_VISUAL_IS_FIRST);
1388     }
1389
1390     if (isLast) {
1391       aFrame->AddStateBits(NS_INLINE_FRAME_BIDI_VISUAL_IS_LAST);
1392     } else {
1393       aFrame->RemoveStateBits(NS_INLINE_FRAME_BIDI_VISUAL_IS_LAST);
1394     }
1395   }
1396   // This method is called from nsBlockFrame::PlaceLine via the call to
1397   // bidiUtils->ReorderFrames, so this is guaranteed to be after the inlines
1398   // have been reflowed, which is required for GetUsedMargin/Border/Padding
1399   LogicalMargin margin(aLineWM, aFrame->GetUsedMargin());
1400   if (isFirst) {
1401     aStart += margin.IStart(aLineWM);
1402   }
1403
1404   nscoord start = aStart;
1405   nscoord frameWidth = aFrame->GetSize().width;
1406
1407   if (!IsBidiLeaf(aFrame))
1408   {
1409     nscoord iCoord = 0;
1410     LogicalMargin borderPadding(frameWM, aFrame->GetUsedBorderAndPadding());
1411     if (isFirst) {
1412       iCoord += borderPadding.IStart(frameWM);
1413     }
1414
1415     // If the resolved direction of the container is different from the
1416     // direction of the frame, we need to traverse the child list in reverse
1417     // order, to make it O(n) we store the list locally and iterate the list
1418     // in reverse
1419     bool reverseOrder = aIsEvenLevel != frameWM.IsBidiLTR();
1420     nsTArray<nsIFrame*> childList;
1421     nsIFrame *frame = aFrame->GetFirstPrincipalChild();
1422     if (frame && reverseOrder) {
1423       childList.AppendElement((nsIFrame*)nullptr);
1424       while (frame) {
1425         childList.AppendElement(frame);
1426         frame = frame->GetNextSibling();
1427       }
1428       frame = childList[childList.Length() - 1];
1429     }
1430
1431     // Reposition the child frames
1432     int32_t index = 0;
1433     while (frame) {
1434       RepositionFrame(frame,
1435                       aIsEvenLevel,
1436                       iCoord,
1437                       aContinuationStates,
1438                       frameWM,
1439                       frameWidth);
1440       index++;
1441       frame = reverseOrder ?
1442                 childList[childList.Length() - index - 1] :
1443                 frame->GetNextSibling();
1444     }
1445
1446     if (isLast) {
1447       iCoord += borderPadding.IEnd(frameWM);
1448     }
1449     aStart += iCoord;
1450   } else {
1451     aStart += frameWidth;
1452   }
1453
1454   LogicalRect logicalRect(aLineWM, aFrame->GetRect(), aLineWidth);
1455   logicalRect.IStart(aLineWM) = start;
1456   logicalRect.ISize(aLineWM) = aStart - start;
1457   aFrame->SetRect(aLineWM, logicalRect, aLineWidth);
1458
1459   if (isLast) {
1460     aStart += margin.IEnd(aLineWM);
1461   }
1462 }
1463
1464 void
1465 nsBidiPresUtils::InitContinuationStates(nsIFrame*              aFrame,
1466                                         nsContinuationStates*  aContinuationStates)
1467 {
1468   nsFrameContinuationState* state = aContinuationStates->PutEntry(aFrame);
1469   state->mFirstVisualFrame = nullptr;
1470   state->mFrameCount = 0;
1471
1472   if (!IsBidiLeaf(aFrame)) {
1473     // Continue for child frames
1474     nsIFrame* frame;
1475     for (frame = aFrame->GetFirstPrincipalChild();
1476          frame;
1477          frame = frame->GetNextSibling()) {
1478       InitContinuationStates(frame,
1479                              aContinuationStates);
1480     }
1481   }
1482 }
1483
1484 void
1485 nsBidiPresUtils::RepositionInlineFrames(BidiLineData *aBld,
1486                                         nsIFrame* aFirstChild,
1487                                         WritingMode aLineWM,
1488                                         nscoord& aLineWidth)
1489 {
1490   nscoord startSpace = 0;
1491
1492   // This method is called from nsBlockFrame::PlaceLine via the call to
1493   // bidiUtils->ReorderFrames, so this is guaranteed to be after the inlines
1494   // have been reflowed, which is required for GetUsedMargin/Border/Padding
1495   LogicalMargin margin(aLineWM, aFirstChild->GetUsedMargin());
1496   if (!aFirstChild->GetPrevContinuation() &&
1497       !aFirstChild->FrameIsNonFirstInIBSplit())
1498     startSpace = margin.IStart(aLineWM);
1499
1500   nscoord start = LogicalRect(aLineWM, aFirstChild->GetRect(),
1501                               aLineWidth).IStart(aLineWM) - startSpace;
1502   nsIFrame* frame;
1503   int32_t count = aBld->mVisualFrames.Length();
1504   int32_t index;
1505   nsContinuationStates continuationStates;
1506
1507   // Initialize continuation states to (nullptr, 0) for
1508   // each frame on the line.
1509   for (index = 0; index < count; index++) {
1510     InitContinuationStates(aBld->VisualFrameAt(index), &continuationStates);
1511   }
1512
1513   // Reposition frames in visual order
1514   int32_t step, limit;
1515   if (aLineWM.IsBidiLTR()) {
1516     index = 0;
1517     step = 1;
1518     limit = count;
1519   } else {
1520     index = count - 1;
1521     step = -1;
1522     limit = -1;
1523   }
1524   for (; index != limit; index += step) {
1525     frame = aBld->VisualFrameAt(index);
1526     RepositionFrame(frame,
1527                     !(aBld->mLevels[aBld->mIndexMap[index]] & 1),
1528                     start,
1529                     &continuationStates,
1530                     aLineWM,
1531                     aLineWidth);
1532   }
1533 }
1534
1535 bool
1536 nsBidiPresUtils::CheckLineOrder(nsIFrame*  aFirstFrameOnLine,
1537                                 int32_t    aNumFramesOnLine,
1538                                 nsIFrame** aFirstVisual,
1539                                 nsIFrame** aLastVisual)
1540 {
1541   BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
1542   int32_t count = bld.FrameCount();
1543
1544   if (aFirstVisual) {
1545     *aFirstVisual = bld.VisualFrameAt(0);
1546   }
1547   if (aLastVisual) {
1548     *aLastVisual = bld.VisualFrameAt(count-1);
1549   }
1550
1551   return bld.mIsReordered;
1552 }
1553
1554 nsIFrame*
1555 nsBidiPresUtils::GetFrameToRightOf(const nsIFrame*  aFrame,
1556                                    nsIFrame*        aFirstFrameOnLine,
1557                                    int32_t          aNumFramesOnLine)
1558 {
1559   BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
1560
1561   int32_t count = bld.mVisualFrames.Length();
1562
1563   if (aFrame == nullptr && count)
1564     return bld.VisualFrameAt(0);
1565
1566   for (int32_t i = 0; i < count - 1; i++) {
1567     if (bld.VisualFrameAt(i) == aFrame) {
1568       return bld.VisualFrameAt(i+1);
1569     }
1570   }
1571
1572   return nullptr;
1573 }
1574
1575 nsIFrame*
1576 nsBidiPresUtils::GetFrameToLeftOf(const nsIFrame*  aFrame,
1577                                   nsIFrame*        aFirstFrameOnLine,
1578                                   int32_t          aNumFramesOnLine)
1579 {
1580   BidiLineData bld(aFirstFrameOnLine, aNumFramesOnLine);
1581
1582   int32_t count = bld.mVisualFrames.Length();
1583
1584   if (aFrame == nullptr && count)
1585     return bld.VisualFrameAt(count-1);
1586
1587   for (int32_t i = 1; i < count; i++) {
1588     if (bld.VisualFrameAt(i) == aFrame) {
1589       return bld.VisualFrameAt(i-1);
1590     }
1591   }
1592
1593   return nullptr;
1594 }
1595
1596 inline nsresult
1597 nsBidiPresUtils::EnsureBidiContinuation(nsIFrame*       aFrame,
1598                                         nsIFrame**      aNewFrame,
1599                                         int32_t&        aFrameIndex,
1600                                         int32_t         aStart,
1601                                         int32_t         aEnd)
1602 {
1603   NS_PRECONDITION(aNewFrame, "null OUT ptr");
1604   NS_PRECONDITION(aFrame, "aFrame is null");
1605
1606   aFrame->AdjustOffsetsForBidi(aStart, aEnd);
1607   return CreateContinuation(aFrame, aNewFrame, false);
1608 }
1609
1610 void
1611 nsBidiPresUtils::RemoveBidiContinuation(BidiParagraphData *aBpd,
1612                                         nsIFrame*       aFrame,
1613                                         int32_t         aFirstIndex,
1614                                         int32_t         aLastIndex,
1615                                         int32_t&        aOffset)
1616 {
1617   FrameProperties props = aFrame->Properties();
1618   nsBidiLevel embeddingLevel =
1619     (nsBidiLevel)NS_PTR_TO_INT32(props.Get(nsIFrame::EmbeddingLevelProperty()));
1620   nsBidiLevel baseLevel =
1621     (nsBidiLevel)NS_PTR_TO_INT32(props.Get(nsIFrame::BaseLevelProperty()));
1622   uint8_t paragraphDepth =
1623     NS_PTR_TO_INT32(props.Get(nsIFrame::ParagraphDepthProperty()));
1624
1625   for (int32_t index = aFirstIndex + 1; index <= aLastIndex; index++) {
1626     nsIFrame* frame = aBpd->FrameAt(index);
1627     if (frame == NS_BIDI_CONTROL_FRAME) {
1628       ++aOffset;
1629     }
1630     else {
1631       // Make the frame and its continuation ancestors fluid,
1632       // so they can be reused or deleted by normal reflow code
1633       FrameProperties frameProps = frame->Properties();
1634       frameProps.Set(nsIFrame::EmbeddingLevelProperty(),
1635                      NS_INT32_TO_PTR(embeddingLevel));
1636       frameProps.Set(nsIFrame::BaseLevelProperty(),
1637                      NS_INT32_TO_PTR(baseLevel));
1638       frameProps.Set(nsIFrame::ParagraphDepthProperty(),
1639                      NS_INT32_TO_PTR(paragraphDepth));
1640       frame->AddStateBits(NS_FRAME_IS_BIDI);
1641       while (frame) {
1642         nsIFrame* prev = frame->GetPrevContinuation();
1643         if (prev) {
1644           MakeContinuationFluid(prev, frame);
1645           frame = frame->GetParent();
1646         } else {
1647           break;
1648         }
1649       }
1650     }
1651   }
1652
1653   // Make sure that the last continuation we made fluid does not itself have a
1654   // fluid continuation (this can happen when re-resolving after dynamic changes
1655   // to content)
1656   nsIFrame* lastFrame = aBpd->FrameAt(aLastIndex);
1657   MakeContinuationsNonFluidUpParentChain(lastFrame, lastFrame->GetNextInFlow());
1658 }
1659
1660 nsresult
1661 nsBidiPresUtils::FormatUnicodeText(nsPresContext*  aPresContext,
1662                                    char16_t*       aText,
1663                                    int32_t&         aTextLength,
1664                                    nsCharType       aCharType,
1665                                    bool             aIsOddLevel)
1666 {
1667   nsresult rv = NS_OK;
1668   // ahmed
1669   //adjusted for correct numeral shaping
1670   uint32_t bidiOptions = aPresContext->GetBidi();
1671   switch (GET_BIDI_OPTION_NUMERAL(bidiOptions)) {
1672
1673     case IBMBIDI_NUMERAL_HINDI:
1674       HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_HINDI);
1675       break;
1676
1677     case IBMBIDI_NUMERAL_ARABIC:
1678       HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_ARABIC);
1679       break;
1680
1681     case IBMBIDI_NUMERAL_PERSIAN:
1682       HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_PERSIAN);
1683       break;
1684
1685     case IBMBIDI_NUMERAL_REGULAR:
1686
1687       switch (aCharType) {
1688
1689         case eCharType_EuropeanNumber:
1690           HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_ARABIC);
1691           break;
1692
1693         case eCharType_ArabicNumber:
1694           HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_HINDI);
1695           break;
1696
1697         default:
1698           break;
1699       }
1700       break;
1701
1702     case IBMBIDI_NUMERAL_HINDICONTEXT:
1703       if ( ( (GET_BIDI_OPTION_DIRECTION(bidiOptions)==IBMBIDI_TEXTDIRECTION_RTL) && (IS_ARABIC_DIGIT (aText[0])) ) || (eCharType_ArabicNumber == aCharType) )
1704         HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_HINDI);
1705       else if (eCharType_EuropeanNumber == aCharType)
1706         HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_ARABIC);
1707       break;
1708
1709     case IBMBIDI_NUMERAL_PERSIANCONTEXT:
1710       if ( ( (GET_BIDI_OPTION_DIRECTION(bidiOptions)==IBMBIDI_TEXTDIRECTION_RTL) && (IS_ARABIC_DIGIT (aText[0])) ) || (eCharType_ArabicNumber == aCharType) )
1711         HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_PERSIAN);
1712       else if (eCharType_EuropeanNumber == aCharType)
1713         HandleNumbers(aText,aTextLength,IBMBIDI_NUMERAL_ARABIC);
1714       break;
1715
1716     case IBMBIDI_NUMERAL_NOMINAL:
1717     default:
1718       break;
1719   }
1720
1721   StripBidiControlCharacters(aText, aTextLength);
1722   return rv;
1723 }
1724
1725 void
1726 nsBidiPresUtils::StripBidiControlCharacters(char16_t* aText,
1727                                             int32_t&   aTextLength)
1728 {
1729   if ( (nullptr == aText) || (aTextLength < 1) ) {
1730     return;
1731   }
1732
1733   int32_t stripLen = 0;
1734
1735   for (int32_t i = 0; i < aTextLength; i++) {
1736     // XXX: This silently ignores surrogate characters.
1737     //      As of Unicode 4.0, all Bidi control characters are within the BMP.
1738     if (IsBidiControl((uint32_t)aText[i])) {
1739       ++stripLen;
1740     }
1741     else {
1742       aText[i - stripLen] = aText[i];
1743     }
1744   }
1745   aTextLength -= stripLen;
1746 }
1747
1748 #if 0 // XXX: for the future use ???
1749 void
1750 RemoveDiacritics(char16_t* aText,
1751                  int32_t&   aTextLength)
1752 {
1753   if (aText && (aTextLength > 0) ) {
1754     int32_t offset = 0;
1755
1756     for (int32_t i = 0; i < aTextLength && aText[i]; i++) {
1757       if (IS_BIDI_DIACRITIC(aText[i]) ) {
1758         ++offset;
1759         continue;
1760       }
1761       aText[i - offset] = aText[i];
1762     }
1763     aTextLength = i - offset;
1764     aText[aTextLength] = 0;
1765   }
1766 }
1767 #endif
1768
1769 void
1770 nsBidiPresUtils::CalculateCharType(nsBidi* aBidiEngine,
1771                                    const char16_t* aText,
1772                                    int32_t& aOffset,
1773                                    int32_t  aCharTypeLimit,
1774                                    int32_t& aRunLimit,
1775                                    int32_t& aRunLength,
1776                                    int32_t& aRunCount,
1777                                    uint8_t& aCharType,
1778                                    uint8_t& aPrevCharType)
1779
1780 {
1781   bool       strongTypeFound = false;
1782   int32_t    offset;
1783   nsCharType charType;
1784
1785   aCharType = eCharType_OtherNeutral;
1786
1787   for (offset = aOffset; offset < aCharTypeLimit; offset++) {
1788     // Make sure we give RTL chartype to all characters that would be classified
1789     // as Right-To-Left by a bidi platform.
1790     // (May differ from the UnicodeData, eg we set RTL chartype to some NSMs.)
1791     if (IS_HEBREW_CHAR(aText[offset]) ) {
1792       charType = eCharType_RightToLeft;
1793     }
1794     else if (IS_ARABIC_ALPHABETIC(aText[offset]) ) {
1795       charType = eCharType_RightToLeftArabic;
1796     }
1797     else {
1798       aBidiEngine->GetCharTypeAt(offset, &charType);
1799     }
1800
1801     if (!CHARTYPE_IS_WEAK(charType) ) {
1802
1803       if (strongTypeFound
1804           && (charType != aPrevCharType)
1805           && (CHARTYPE_IS_RTL(charType) || CHARTYPE_IS_RTL(aPrevCharType) ) ) {
1806         // Stop at this point to ensure uni-directionality of the text
1807         // (from platform's point of view).
1808         // Also, don't mix Arabic and Hebrew content (since platform may
1809         // provide BIDI support to one of them only).
1810         aRunLength = offset - aOffset;
1811         aRunLimit = offset;
1812         ++aRunCount;
1813         break;
1814       }
1815
1816       if ( (eCharType_RightToLeftArabic == aPrevCharType
1817             || eCharType_ArabicNumber == aPrevCharType)
1818           && eCharType_EuropeanNumber == charType) {
1819         charType = eCharType_ArabicNumber;
1820       }
1821
1822       // Set PrevCharType to the last strong type in this frame
1823       // (for correct numeric shaping)
1824       aPrevCharType = charType;
1825
1826       strongTypeFound = true;
1827       aCharType = charType;
1828     }
1829   }
1830   aOffset = offset;
1831 }
1832
1833 nsresult nsBidiPresUtils::ProcessText(const char16_t*       aText,
1834                                       int32_t                aLength,
1835                                       nsBidiLevel            aBaseLevel,
1836                                       nsPresContext*         aPresContext,
1837                                       BidiProcessor&         aprocessor,
1838                                       Mode                   aMode,
1839                                       nsBidiPositionResolve* aPosResolve,
1840                                       int32_t                aPosResolveCount,
1841                                       nscoord*               aWidth,
1842                                       nsBidi*                aBidiEngine)
1843 {
1844   NS_ASSERTION((aPosResolve == nullptr) != (aPosResolveCount > 0), "Incorrect aPosResolve / aPosResolveCount arguments");
1845
1846   int32_t runCount;
1847
1848   nsAutoString textBuffer(aText, aLength);
1849
1850   nsresult rv = aBidiEngine->SetPara(aText, aLength, aBaseLevel, nullptr);
1851   if (NS_FAILED(rv))
1852     return rv;
1853
1854   rv = aBidiEngine->CountRuns(&runCount);
1855   if (NS_FAILED(rv))
1856     return rv;
1857
1858   nscoord xOffset = 0;
1859   nscoord width, xEndRun = 0;
1860   nscoord totalWidth = 0;
1861   int32_t i, start, limit, length;
1862   uint32_t visualStart = 0;
1863   uint8_t charType;
1864   uint8_t prevType = eCharType_LeftToRight;
1865   nsBidiLevel level;
1866
1867   for(int nPosResolve=0; nPosResolve < aPosResolveCount; ++nPosResolve)
1868   {
1869     aPosResolve[nPosResolve].visualIndex = kNotFound;
1870     aPosResolve[nPosResolve].visualLeftTwips = kNotFound;
1871     aPosResolve[nPosResolve].visualWidth = kNotFound;
1872   }
1873
1874   for (i = 0; i < runCount; i++) {
1875     nsBidiDirection dir;
1876     rv = aBidiEngine->GetVisualRun(i, &start, &length, &dir);
1877     if (NS_FAILED(rv))
1878       return rv;
1879
1880     rv = aBidiEngine->GetLogicalRun(start, &limit, &level);
1881     if (NS_FAILED(rv))
1882       return rv;
1883
1884     int32_t subRunLength = limit - start;
1885     int32_t lineOffset = start;
1886     int32_t typeLimit = std::min(limit, aLength);
1887     int32_t subRunCount = 1;
1888     int32_t subRunLimit = typeLimit;
1889
1890     /*
1891      * If |level| is even, i.e. the direction of the run is left-to-right, we
1892      * render the subruns from left to right and increment the x-coordinate
1893      * |xOffset| by the width of each subrun after rendering.
1894      *
1895      * If |level| is odd, i.e. the direction of the run is right-to-left, we
1896      * render the subruns from right to left. We begin by incrementing |xOffset| by
1897      * the width of the whole run, and then decrement it by the width of each
1898      * subrun before rendering. After rendering all the subruns, we restore the
1899      * x-coordinate of the end of the run for the start of the next run.
1900      */
1901
1902     if (level & 1) {
1903       aprocessor.SetText(aText + start, subRunLength, nsBidiDirection(level & 1));
1904       width = aprocessor.GetWidth();
1905       xOffset += width;
1906       xEndRun = xOffset;
1907     }
1908
1909     while (subRunCount > 0) {
1910       // CalculateCharType can increment subRunCount if the run
1911       // contains mixed character types
1912       CalculateCharType(aBidiEngine, aText, lineOffset, typeLimit, subRunLimit, subRunLength, subRunCount, charType, prevType);
1913
1914       nsAutoString runVisualText;
1915       runVisualText.Assign(aText + start, subRunLength);
1916       if (int32_t(runVisualText.Length()) < subRunLength)
1917         return NS_ERROR_OUT_OF_MEMORY;
1918       FormatUnicodeText(aPresContext, runVisualText.BeginWriting(), subRunLength,
1919                         (nsCharType)charType, level & 1);
1920
1921       aprocessor.SetText(runVisualText.get(), subRunLength, nsBidiDirection(level & 1));
1922       width = aprocessor.GetWidth();
1923       totalWidth += width;
1924       if (level & 1) {
1925         xOffset -= width;
1926       }
1927       if (aMode == MODE_DRAW) {
1928         aprocessor.DrawText(xOffset, width);
1929       }
1930
1931       /*
1932        * The caller may request to calculate the visual position of one
1933        * or more characters.
1934        */
1935       for(int nPosResolve=0; nPosResolve<aPosResolveCount; ++nPosResolve)
1936       {
1937         nsBidiPositionResolve* posResolve = &aPosResolve[nPosResolve];
1938         /*
1939          * Did we already resolve this position's visual metric? If so, skip.
1940          */
1941         if (posResolve->visualLeftTwips != kNotFound)
1942            continue;
1943
1944         /*
1945          * First find out if the logical position is within this run.
1946          */
1947         if (start <= posResolve->logicalIndex &&
1948             start + subRunLength > posResolve->logicalIndex) {
1949           /*
1950            * If this run is only one character long, we have an easy case:
1951            * the visual position is the x-coord of the start of the run
1952            * less the x-coord of the start of the whole text.
1953            */
1954           if (subRunLength == 1) {
1955             posResolve->visualIndex = visualStart;
1956             posResolve->visualLeftTwips = xOffset;
1957             posResolve->visualWidth = width;
1958           }
1959           /*
1960            * Otherwise, we need to measure the width of the run's part
1961            * which is to the visual left of the index.
1962            * In other words, the run is broken in two, around the logical index,
1963            * and we measure the part which is visually left.
1964            * If the run is right-to-left, this part will span from after the index
1965            * up to the end of the run; if it is left-to-right, this part will span
1966            * from the start of the run up to (and inclduing) the character before the index.
1967            */
1968           else {
1969             /*
1970              * Here is a description of how the width of the current character
1971              * (posResolve->visualWidth) is calculated:
1972              *
1973              * LTR (current char: "P"):
1974              *    S A M P L E          (logical index: 3, visual index: 3)
1975              *    ^ (visualLeftPart)
1976              *    ^ (visualRightSide)
1977              *    visualLeftLength == 3
1978              *    ^^^^^^ (subWidth)
1979              *    ^^^^^^^^ (aprocessor.GetWidth() -- with visualRightSide)
1980              *          ^^ (posResolve->visualWidth)
1981              *
1982              * RTL (current char: "M"):
1983              *    E L P M A S          (logical index: 2, visual index: 3)
1984              *        ^ (visualLeftPart)
1985              *          ^ (visualRightSide)
1986              *    visualLeftLength == 3
1987              *    ^^^^^^ (subWidth)
1988              *    ^^^^^^^^ (aprocessor.GetWidth() -- with visualRightSide)
1989              *          ^^ (posResolve->visualWidth)
1990              */
1991             nscoord subWidth;
1992             // The position in the text where this run's "left part" begins.
1993             const char16_t* visualLeftPart;
1994             const char16_t* visualRightSide;
1995             if (level & 1) {
1996               // One day, son, this could all be replaced with mBidiEngine.GetVisualIndex ...
1997               posResolve->visualIndex = visualStart + (subRunLength - (posResolve->logicalIndex + 1 - start));
1998               // Skipping to the "left part".
1999               visualLeftPart = aText + posResolve->logicalIndex + 1;
2000               // Skipping to the right side of the current character
2001               visualRightSide = visualLeftPart - 1;
2002             }
2003             else {
2004               posResolve->visualIndex = visualStart + (posResolve->logicalIndex - start);
2005               // Skipping to the "left part".
2006               visualLeftPart = aText + start;
2007               // In LTR mode this is the same as visualLeftPart
2008               visualRightSide = visualLeftPart;
2009             }
2010             // The delta between the start of the run and the left part's end.
2011             int32_t visualLeftLength = posResolve->visualIndex - visualStart;
2012             aprocessor.SetText(visualLeftPart, visualLeftLength, nsBidiDirection(level & 1));
2013             subWidth = aprocessor.GetWidth();
2014             aprocessor.SetText(visualRightSide, visualLeftLength + 1, nsBidiDirection(level & 1));
2015             posResolve->visualLeftTwips = xOffset + subWidth;
2016             posResolve->visualWidth = aprocessor.GetWidth() - subWidth;
2017           }
2018         }
2019       }
2020
2021       if (!(level & 1)) {
2022         xOffset += width;
2023       }
2024
2025       --subRunCount;
2026       start = lineOffset;
2027       subRunLimit = typeLimit;
2028       subRunLength = typeLimit - lineOffset;
2029     } // while
2030     if (level & 1) {
2031       xOffset = xEndRun;
2032     }
2033
2034     visualStart += length;
2035   } // for
2036
2037   if (aWidth) {
2038     *aWidth = totalWidth;
2039   }
2040   return NS_OK;
2041 }
2042
2043 class MOZ_STACK_CLASS nsIRenderingContextBidiProcessor : public nsBidiPresUtils::BidiProcessor {
2044 public:
2045   nsIRenderingContextBidiProcessor(nsRenderingContext* aCtx,
2046                                    nsRenderingContext* aTextRunConstructionContext,
2047                                    const nsPoint&       aPt)
2048     : mCtx(aCtx), mTextRunConstructionContext(aTextRunConstructionContext), mPt(aPt) { }
2049
2050   ~nsIRenderingContextBidiProcessor()
2051   {
2052     mCtx->SetTextRunRTL(false);
2053   }
2054
2055   virtual void SetText(const char16_t* aText,
2056                        int32_t          aLength,
2057                        nsBidiDirection  aDirection) MOZ_OVERRIDE
2058   {
2059     mTextRunConstructionContext->SetTextRunRTL(aDirection==NSBIDI_RTL);
2060     mText = aText;
2061     mLength = aLength;
2062   }
2063
2064   virtual nscoord GetWidth() MOZ_OVERRIDE
2065   {
2066     return mTextRunConstructionContext->GetWidth(mText, mLength);
2067   }
2068
2069   virtual void DrawText(nscoord aXOffset,
2070                         nscoord) MOZ_OVERRIDE
2071   {
2072     mCtx->FontMetrics()->DrawString(mText, mLength, mPt.x + aXOffset, mPt.y,
2073                                     mCtx, mTextRunConstructionContext);
2074   }
2075
2076 private:
2077   nsRenderingContext* mCtx;
2078   nsRenderingContext* mTextRunConstructionContext;
2079   nsPoint mPt;
2080   const char16_t* mText;
2081   int32_t mLength;
2082 };
2083
2084 nsresult nsBidiPresUtils::ProcessTextForRenderingContext(const char16_t*       aText,
2085                                                          int32_t                aLength,
2086                                                          nsBidiLevel            aBaseLevel,
2087                                                          nsPresContext*         aPresContext,
2088                                                          nsRenderingContext&   aRenderingContext,
2089                                                          nsRenderingContext&   aTextRunConstructionContext,
2090                                                          Mode                   aMode,
2091                                                          nscoord                aX,
2092                                                          nscoord                aY,
2093                                                          nsBidiPositionResolve* aPosResolve,
2094                                                          int32_t                aPosResolveCount,
2095                                                          nscoord*               aWidth)
2096 {
2097   nsIRenderingContextBidiProcessor processor(&aRenderingContext, &aTextRunConstructionContext, nsPoint(aX, aY));
2098   nsBidi bidiEngine;
2099   return ProcessText(aText, aLength, aBaseLevel, aPresContext, processor,
2100                      aMode, aPosResolve, aPosResolveCount, aWidth, &bidiEngine);
2101 }
2102
2103 /* static */
2104 void nsBidiPresUtils::WriteReverse(const char16_t* aSrc,
2105                                    uint32_t aSrcLength,
2106                                    char16_t* aDest)
2107 {
2108   char16_t* dest = aDest + aSrcLength;
2109   mozilla::unicode::ClusterIterator iter(aSrc, aSrcLength);
2110
2111   while (!iter.AtEnd()) {
2112     iter.Next();
2113     for (const char16_t *cp = iter; cp > aSrc; ) {
2114       // Here we rely on the fact that there are no non-BMP mirrored pairs
2115       // currently in Unicode, so we don't need to look for surrogates
2116       *--dest = mozilla::unicode::GetMirroredChar(*--cp);
2117     }
2118     aSrc = iter;
2119   }
2120
2121   NS_ASSERTION(dest == aDest, "Whole string not copied");
2122 }
2123
2124 /* static */
2125 bool nsBidiPresUtils::WriteLogicalToVisual(const char16_t* aSrc,
2126                                            uint32_t aSrcLength,
2127                                            char16_t* aDest,
2128                                            nsBidiLevel aBaseDirection,
2129                                            nsBidi* aBidiEngine)
2130 {
2131   const char16_t* src = aSrc;
2132   nsresult rv = aBidiEngine->SetPara(src, aSrcLength, aBaseDirection, nullptr);
2133   if (NS_FAILED(rv)) {
2134     return false;
2135   }
2136
2137   nsBidiDirection dir;
2138   rv = aBidiEngine->GetDirection(&dir);
2139   // NSBIDI_LTR returned from GetDirection means the whole text is LTR
2140   if (NS_FAILED(rv) || dir == NSBIDI_LTR) {
2141     return false;
2142   }
2143
2144   int32_t runCount;
2145   rv = aBidiEngine->CountRuns(&runCount);
2146   if (NS_FAILED(rv)) {
2147     return false;
2148   }
2149
2150   int32_t runIndex, start, length;
2151   char16_t* dest = aDest;
2152
2153   for (runIndex = 0; runIndex < runCount; ++runIndex) {
2154     rv = aBidiEngine->GetVisualRun(runIndex, &start, &length, &dir);
2155     if (NS_FAILED(rv)) {
2156       return false;
2157     }
2158
2159     src = aSrc + start;
2160
2161     if (dir == NSBIDI_RTL) {
2162       WriteReverse(src, length, dest);
2163       dest += length;
2164     } else {
2165       do {
2166         NS_ASSERTION(src >= aSrc && src < aSrc + aSrcLength,
2167                      "logical index out of range");
2168         NS_ASSERTION(dest < aDest + aSrcLength, "visual index out of range");
2169         *(dest++) = *(src++);
2170       } while (--length);
2171     }
2172   }
2173
2174   NS_ASSERTION(static_cast<uint32_t>(dest - aDest) == aSrcLength,
2175                "whole string not copied");
2176   return true;
2177 }
2178
2179 void nsBidiPresUtils::CopyLogicalToVisual(const nsAString& aSource,
2180                                           nsAString& aDest,
2181                                           nsBidiLevel aBaseDirection,
2182                                           bool aOverride)
2183 {
2184   aDest.SetLength(0);
2185   uint32_t srcLength = aSource.Length();
2186   if (srcLength == 0)
2187     return;
2188   if (!aDest.SetLength(srcLength, fallible_t())) {
2189     return;
2190   }
2191   nsAString::const_iterator fromBegin, fromEnd;
2192   nsAString::iterator toBegin;
2193   aSource.BeginReading(fromBegin);
2194   aSource.EndReading(fromEnd);
2195   aDest.BeginWriting(toBegin);
2196
2197   if (aOverride) {
2198     if (aBaseDirection == NSBIDI_RTL) {
2199       // no need to use the converter -- just copy the string in reverse order
2200       WriteReverse(fromBegin.get(), srcLength, toBegin.get());
2201     } else {
2202       // if aOverride && aBaseDirection == NSBIDI_LTR, fall through to the
2203       // simple copy
2204       aDest.SetLength(0);
2205     }
2206   } else {
2207     nsBidi bidiEngine;
2208     if (!WriteLogicalToVisual(fromBegin.get(), srcLength, toBegin.get(),
2209                              aBaseDirection, &bidiEngine)) {
2210       aDest.SetLength(0);
2211     }
2212   }
2213
2214   if (aDest.IsEmpty()) {
2215     // Either there was an error or the source is unidirectional
2216     //  left-to-right. In either case, just copy source to dest.
2217     CopyUnicodeTo(aSource.BeginReading(fromBegin), aSource.EndReading(fromEnd),
2218                   aDest);
2219   }
2220 }
2221
2222 /* static */
2223 nsBidiLevel
2224 nsBidiPresUtils::BidiLevelFromStyle(nsStyleContext* aStyleContext)
2225 {
2226   if (aStyleContext->StyleTextReset()->mUnicodeBidi &
2227       NS_STYLE_UNICODE_BIDI_PLAINTEXT) {
2228     return NSBIDI_DEFAULT_LTR;
2229   }
2230
2231   if (aStyleContext->StyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL) {
2232     return NSBIDI_RTL;
2233   }
2234
2235   return NSBIDI_LTR;
2236 }