The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

 /* This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #include "TextUpdater.h"

 #include "Accessible-inl.h"

 #include "DocAccessible-inl.h"

 #include "TextLeafAccessible.h"

 #include <algorithm>

 using namespace mozilla::a11y;

 void

 TextUpdater::Run(DocAccessible* aDocument, TextLeafAccessible* aTextLeaf,

                  const nsAString& aNewText)

 {

   NS_ASSERTION(aTextLeaf, "No text leaf accessible?");

   const nsString& oldText = aTextLeaf->Text();

   uint32_t oldLen = oldText.Length(), newLen = aNewText.Length();

   uint32_t minLen = std::min(oldLen, newLen);

   // Skip coinciding begin substrings.

   uint32_t skipStart = 0;

   for (; skipStart < minLen; skipStart++) {

     if (aNewText[skipStart] != oldText[skipStart])

       break;

   }

   // The text was changed. Do update.

   if (skipStart != minLen || oldLen != newLen) {

     TextUpdater updater(aDocument, aTextLeaf);

     updater.DoUpdate(aNewText, oldText, skipStart);

   }

 }

 void

 TextUpdater::DoUpdate(const nsAString& aNewText, const nsAString& aOldText,

                       uint32_t aSkipStart)

 {

   Accessible* parent = mTextLeaf->Parent();

   if (!parent)

     return;

   mHyperText = parent->AsHyperText();

   if (!mHyperText) {

     NS_ERROR("Text leaf parent is not hypertext!");

     return;

   }

   // Get the text leaf accessible offset and invalidate cached offsets after it.

   mTextOffset = mHyperText->GetChildOffset(mTextLeaf, true);

   NS_ASSERTION(mTextOffset != -1,

                "Text leaf hasn't offset within hyper text!");

   uint32_t oldLen = aOldText.Length(), newLen = aNewText.Length();

   uint32_t minLen = std::min(oldLen, newLen);

   // Trim coinciding substrings from the end.

   uint32_t skipEnd = 0;

   while (minLen - skipEnd > aSkipStart &&

          aNewText[newLen - skipEnd - 1] == aOldText[oldLen - skipEnd - 1]) {

     skipEnd++;

   }

   uint32_t strLen1 = oldLen - aSkipStart - skipEnd;

   uint32_t strLen2 = newLen - aSkipStart - skipEnd;

   const nsAString& str1 = Substring(aOldText, aSkipStart, strLen1);

   const nsAString& str2 = Substring(aNewText, aSkipStart, strLen2);

   // Increase offset of the text leaf on skipped characters amount.

   mTextOffset += aSkipStart;

   // It could be single insertion or removal or the case of long strings. Do not

   // calculate the difference between long strings and prefer to fire pair of

   // insert/remove events as the old string was replaced on the new one.

   if (strLen1 == 0 || strLen2 == 0 ||

       strLen1 > kMaxStrLen || strLen2 > kMaxStrLen) {

     if (strLen1 > 0) {

       // Fire text change event for removal.

       nsRefPtr<AccEvent> textRemoveEvent =

         new AccTextChangeEvent(mHyperText, mTextOffset, str1, false);

       mDocument->FireDelayedEvent(textRemoveEvent);

     }

     if (strLen2 > 0) {

       // Fire text change event for insertion.

       nsRefPtr<AccEvent> textInsertEvent =

         new AccTextChangeEvent(mHyperText, mTextOffset, str2, true);

       mDocument->FireDelayedEvent(textInsertEvent);

     }

     mDocument->MaybeNotifyOfValueChange(mHyperText);

     // Update the text.

     mTextLeaf->SetText(aNewText);

     return;

   }

   // Otherwise find the difference between strings and fire events.

   // Note: we can skip initial and final coinciding characters since they don't

   // affect the Levenshtein distance.

   // Compute the flat structured matrix need to compute the difference.

   uint32_t len1 = strLen1 + 1, len2 = strLen2 + 1;

   uint32_t* entries = new uint32_t[len1 * len2];

   for (uint32_t colIdx = 0; colIdx < len1; colIdx++)

     entries[colIdx] = colIdx;

   uint32_t* row = entries;

   for (uint32_t rowIdx = 1; rowIdx < len2; rowIdx++) {

     uint32_t* prevRow = row;

     row += len1;

     row[0] = rowIdx;

     for (uint32_t colIdx = 1; colIdx < len1; colIdx++) {

       if (str1[colIdx - 1] != str2[rowIdx - 1]) {

         uint32_t left = row[colIdx - 1];

         uint32_t up = prevRow[colIdx];

         uint32_t upleft = prevRow[colIdx - 1];

         row[colIdx] = std::min(upleft, std::min(left, up)) + 1;

       } else {

         row[colIdx] = prevRow[colIdx - 1];

       }

     }

   }

   // Compute events based on the difference.

   nsTArray<nsRefPtr<AccEvent> > events;

   ComputeTextChangeEvents(str1, str2, entries, events);

   delete [] entries;

   // Fire events.

   for (int32_t idx = events.Length() - 1; idx >= 0; idx--)

     mDocument->FireDelayedEvent(events[idx]);

   mDocument->MaybeNotifyOfValueChange(mHyperText);

   // Update the text.

   mTextLeaf->SetText(aNewText);

 }

 void

 TextUpdater::ComputeTextChangeEvents(const nsAString& aStr1,

                                      const nsAString& aStr2,

                                      uint32_t* aEntries,

                                      nsTArray<nsRefPtr<AccEvent> >& aEvents)

 {

   int32_t colIdx = aStr1.Length(), rowIdx = aStr2.Length();

   // Point at which strings last matched.

   int32_t colEnd = colIdx;

   int32_t rowEnd = rowIdx;

   int32_t colLen = colEnd + 1;

   uint32_t* row = aEntries + rowIdx * colLen;

   uint32_t dist = row[colIdx]; // current Levenshtein distance

   while (rowIdx && colIdx) { // stop when we can't move diagonally

     if (aStr1[colIdx - 1] == aStr2[rowIdx - 1]) { // match

       if (rowIdx < rowEnd) { // deal with any pending insertion

         FireInsertEvent(Substring(aStr2, rowIdx, rowEnd - rowIdx),

                         rowIdx, aEvents);

       }

       if (colIdx < colEnd) { // deal with any pending deletion

         FireDeleteEvent(Substring(aStr1, colIdx, colEnd - colIdx),

                         rowIdx, aEvents);

       }

       colEnd = --colIdx; // reset the match point

       rowEnd = --rowIdx;

       row -= colLen;

       continue;

     }

     --dist;

     if (dist == row[colIdx - 1 - colLen]) { // substitution

       --colIdx;

       --rowIdx;

       row -= colLen;

       continue;

     }

     if (dist == row[colIdx - colLen]) { // insertion

       --rowIdx;

       row -= colLen;

       continue;

     }

     if (dist == row[colIdx - 1]) { // deletion

       --colIdx;

       continue;

     }

     NS_NOTREACHED("huh?");

     return;

   }

   if (rowEnd)

     FireInsertEvent(Substring(aStr2, 0, rowEnd), 0, aEvents);

   if (colEnd)

     FireDeleteEvent(Substring(aStr1, 0, colEnd), 0, aEvents);

 }