Quelle TextUpdater.cpp Sprache: C

/* -*- 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 "CacheConstants.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);
    aDocument->QueueCacheUpdate(aTextLeaf, CacheDomain::Text);
  }
}

void TextUpdater::DoUpdate(const nsAString& aNewText, const nsAString& aOldText,
                           uint32_t aSkipStart) {
  LocalAccessible* parent = mTextLeaf->LocalParent();
  if (!parent) return;

  mHyperText = parent->AsHyperText();
  if (!mHyperText) {
    MOZ_ASSERT_UNREACHABLE("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!");

  // Don't bother diffing if the hypertext isn't editable. Diffing non-editable
  // text can lead to weird screen reader results with live regions, e.g.,
  // changing "text" to "testing" might read the diff "s ing" when we'd really
  // just like to hear "testing."
  if (!mHyperText->IsEditable()) {
    // Fire text change event for removal.
    RefPtr<AccEvent> textRemoveEvent =
        new AccTextChangeEvent(mHyperText, mTextOffset, aOldText, false);
    mDocument->FireDelayedEvent(textRemoveEvent);

    // Fire text change event for insertion if there's text to insert.
    if (!aNewText.IsEmpty()) {
      RefPtr<AccEvent> textInsertEvent =
          new AccTextChangeEvent(mHyperText, mTextOffset, aNewText, true);
      mDocument->FireDelayedEvent(textInsertEvent);
    }

    mDocument->MaybeNotifyOfValueChange(mHyperText);

    // Update the text.
    mTextLeaf->SetText(aNewText);
    return;
  }

  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.
      RefPtr<AccEvent> textRemoveEvent =
          new AccTextChangeEvent(mHyperText, mTextOffset, str1, false);
      mDocument->FireDelayedEvent(textRemoveEvent);
    }

    if (strLen2 > 0) {
      // Fire text change event for insertion.
      RefPtr<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<RefPtr<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<RefPtr<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;
    }
    MOZ_ASSERT_UNREACHABLE("huh?");
    return;
  }

  if (rowEnd) FireInsertEvent(Substring(aStr2, 0, rowEnd), 0, aEvents);
  if (colEnd) FireDeleteEvent(Substring(aStr1, 0, colEnd), 0, aEvents);
}

quality77%

¤ Dauer der Verarbeitung: 0.17 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.