From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- accessible/base/TextUpdater.cpp | 215 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 215 insertions(+) create mode 100644 accessible/base/TextUpdater.cpp (limited to 'accessible/base/TextUpdater.cpp') diff --git a/accessible/base/TextUpdater.cpp b/accessible/base/TextUpdater.cpp new file mode 100644 index 0000000000..29f8ac11f3 --- /dev/null +++ b/accessible/base/TextUpdater.cpp @@ -0,0 +1,215 @@ +/* -*- 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 + +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 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 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 textRemoveEvent = + new AccTextChangeEvent(mHyperText, mTextOffset, str1, false); + mDocument->FireDelayedEvent(textRemoveEvent); + } + + if (strLen2 > 0) { + // Fire text change event for insertion. + RefPtr 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 > 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 >& 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); +} -- cgit v1.2.3