1 // Copyright 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "ui/accessibility/ax_language_detection.h"
6 #include <algorithm>
7 #include <functional>
8
9 #include "base/command_line.h"
10 #include "base/i18n/unicodestring.h"
11 #include "base/metrics/histogram_functions.h"
12 #include "base/metrics/histogram_macros.h"
13 #include "base/strings/utf_string_conversions.h"
14 #include "base/trace_event/trace_event.h"
15 #include "ui/accessibility/accessibility_switches.h"
16 #include "ui/accessibility/ax_enums.mojom.h"
17 #include "ui/accessibility/ax_tree.h"
18
19 namespace ui {
20
21 namespace {
22 // This is the maximum number of languages we assign per page, so only the top
23 // 3 languages on the top will be assigned to any node.
24 const int kMaxDetectedLanguagesPerPage = 3;
25
26 // This is the maximum number of languages that cld3 will detect for each
27 // input we give it, 3 was recommended to us by the ML team as a good
28 // starting point.
29 const int kMaxDetectedLanguagesPerSpan = 3;
30
31 const int kShortTextIdentifierMinByteLength = 1;
32 // TODO(https://crbug.com/971360): Determine appropriate value for
33 // |kShortTextIdentifierMaxByteLength|.
34 const int kShortTextIdentifierMaxByteLength = 1000;
35 } // namespace
36
37 using Result = chrome_lang_id::NNetLanguageIdentifier::Result;
38 using SpanInfo = chrome_lang_id::NNetLanguageIdentifier::SpanInfo;
39
40 AXLanguageInfo::AXLanguageInfo() = default;
41 AXLanguageInfo::~AXLanguageInfo() = default;
42
AXLanguageInfoStats()43 AXLanguageInfoStats::AXLanguageInfoStats()
44 : top_results_valid_(false),
45 disable_metric_clearing_(false),
46 count_detection_attempted_(0),
47 count_detection_results_(0),
48 count_labelled_(0),
49 count_labelled_with_top_result_(0),
50 count_overridden_(0) {}
51
52 AXLanguageInfoStats::~AXLanguageInfoStats() = default;
53
Add(const std::vector<std::string> & languages)54 void AXLanguageInfoStats::Add(const std::vector<std::string>& languages) {
55 // Count this as a successful detection with results.
56 ++count_detection_results_;
57
58 // Assign languages with higher probability a higher score.
59 // TODO(chrishall): consider more complex scoring
60 int score = kMaxDetectedLanguagesPerSpan;
61 for (const auto& lang : languages) {
62 lang_counts_[lang] += score;
63
64 // Record the highest scoring detected languages for each node.
65 if (score == kMaxDetectedLanguagesPerSpan)
66 unique_top_lang_detected_.insert(lang);
67
68 --score;
69 }
70
71 InvalidateTopResults();
72 }
73
GetScore(const std::string & lang) const74 int AXLanguageInfoStats::GetScore(const std::string& lang) const {
75 const auto& lang_count_it = lang_counts_.find(lang);
76 if (lang_count_it == lang_counts_.end()) {
77 return 0;
78 }
79 return lang_count_it->second;
80 }
81
InvalidateTopResults()82 void AXLanguageInfoStats::InvalidateTopResults() {
83 top_results_valid_ = false;
84 }
85
86 // Check if a given language is within the top results.
CheckLanguageWithinTop(const std::string & lang)87 bool AXLanguageInfoStats::CheckLanguageWithinTop(const std::string& lang) {
88 if (!top_results_valid_) {
89 GenerateTopResults();
90 }
91
92 for (const auto& item : top_results_) {
93 if (lang == item.second) {
94 return true;
95 }
96 }
97
98 return false;
99 }
100
GenerateTopResults()101 void AXLanguageInfoStats::GenerateTopResults() {
102 top_results_.clear();
103
104 for (const auto& item : lang_counts_) {
105 top_results_.emplace_back(item.second, item.first);
106 }
107
108 // Since we store the pair as (score, language) the default operator> on pairs
109 // does our sort appropriately.
110 // Sort in descending order.
111 std::sort(top_results_.begin(), top_results_.end(), std::greater<>());
112
113 // Resize down to remove all values greater than the N we are considering.
114 // TODO(chrishall): In the event of a tie, we want to include more than N.
115 top_results_.resize(kMaxDetectedLanguagesPerPage);
116
117 top_results_valid_ = true;
118 }
119
RecordLabelStatistics(const std::string & labelled_lang,const std::string & author_lang,bool labelled_with_first_result)120 void AXLanguageInfoStats::RecordLabelStatistics(
121 const std::string& labelled_lang,
122 const std::string& author_lang,
123 bool labelled_with_first_result) {
124 // Count the number of nodes we labelled, and the number we labelled with
125 // our highest confidence result.
126 ++count_labelled_;
127
128 if (labelled_with_first_result)
129 ++count_labelled_with_top_result_;
130
131 // Record if we assigned a language that disagrees with the author
132 // provided language for that node.
133 if (author_lang != labelled_lang)
134 ++count_overridden_;
135 }
136
RecordDetectionAttempt()137 void AXLanguageInfoStats::RecordDetectionAttempt() {
138 ++count_detection_attempted_;
139 }
140
ReportMetrics()141 void AXLanguageInfoStats::ReportMetrics() {
142 // Only report statistics for pages which had detected results.
143 if (!count_detection_attempted_)
144 return;
145
146 // 50 buckets exponentially covering the range from 1 to 1000.
147 base::UmaHistogramCustomCounts(
148 "Accessibility.LanguageDetection.CountDetectionAttempted",
149 count_detection_attempted_, 1, 1000, 50);
150
151 int percentage_detected =
152 count_detection_results_ * 100 / count_detection_attempted_;
153 base::UmaHistogramPercentage(
154 "Accessibility.LanguageDetection.PercentageLanguageDetected",
155 percentage_detected);
156
157 // 50 buckets exponentially covering the range from 1 to 1000.
158 base::UmaHistogramCustomCounts(
159 "Accessibility.LanguageDetection.CountLabelled", count_labelled_, 1, 1000,
160 50);
161
162 // If no nodes were labelled, then the percentage labelled with the top result
163 // doesn't make sense to report.
164 if (count_labelled_) {
165 int percentage_top =
166 count_labelled_with_top_result_ * 100 / count_labelled_;
167 base::UmaHistogramPercentage(
168 "Accessibility.LanguageDetection.PercentageLabelledWithTop",
169 percentage_top);
170
171 int percentage_overridden = count_overridden_ * 100 / count_labelled_;
172 base::UmaHistogramPercentage(
173 "Accessibility.LanguageDetection.PercentageOverridden",
174 percentage_overridden);
175 }
176
177 // Exact count from 0 to 15, overflow is then truncated to 15.
178 base::UmaHistogramExactLinear("Accessibility.LanguageDetection.LangsPerPage",
179 unique_top_lang_detected_.size(), 15);
180
181 // TODO(chrishall): Consider adding timing metrics for performance, consider:
182 // - detect step.
183 // - label step.
184 // - total initial static detection & label timing.
185 // - total incremental dynamic detection & label timing.
186
187 // Reset statistics for metrics.
188 ClearMetrics();
189 }
190
ClearMetrics()191 void AXLanguageInfoStats::ClearMetrics() {
192 // Do not clear metrics if we are specifically testing metrics.
193 if (disable_metric_clearing_)
194 return;
195
196 unique_top_lang_detected_.clear();
197 count_detection_attempted_ = 0;
198 count_detection_results_ = 0;
199 count_labelled_ = 0;
200 count_labelled_with_top_result_ = 0;
201 count_overridden_ = 0;
202 }
203
AXLanguageDetectionManager(AXTree * tree)204 AXLanguageDetectionManager::AXLanguageDetectionManager(AXTree* tree)
205 : short_text_language_identifier_(kShortTextIdentifierMinByteLength,
206 kShortTextIdentifierMaxByteLength),
207 tree_(tree) {}
208
209 AXLanguageDetectionManager::~AXLanguageDetectionManager() = default;
210
RegisterLanguageDetectionObserver()211 void AXLanguageDetectionManager::RegisterLanguageDetectionObserver() {
212 // If the dynamic feature flag is not enabled then do nothing.
213 if (!::switches::
214 IsExperimentalAccessibilityLanguageDetectionDynamicEnabled()) {
215 return;
216 }
217
218 // Construct our new Observer as requested.
219 // If there is already an Observer on this Manager then this will destroy it.
220 language_detection_observer_.reset(new AXLanguageDetectionObserver(tree_));
221 }
222
223 // Detect languages for each node.
DetectLanguages()224 void AXLanguageDetectionManager::DetectLanguages() {
225 TRACE_EVENT0("accessibility", "AXLanguageInfo::DetectLanguages");
226 if (!::switches::IsExperimentalAccessibilityLanguageDetectionEnabled()) {
227 return;
228 }
229
230 DetectLanguagesForSubtree(tree_->root());
231 }
232
233 // Detect languages for a subtree rooted at the given subtree_root.
234 // Will not check feature flag.
DetectLanguagesForSubtree(AXNode * subtree_root)235 void AXLanguageDetectionManager::DetectLanguagesForSubtree(
236 AXNode* subtree_root) {
237 // Only perform detection for kStaticText(s).
238 //
239 // Do not visit the children of kStaticText(s) as they don't have
240 // interesting children for language detection.
241 //
242 // Since kInlineTextBox(es) contain text from their parent, any detection on
243 // them is redundant. Instead they can inherit the detected language.
244 if (subtree_root->data().role == ax::mojom::Role::kStaticText) {
245 DetectLanguagesForNode(subtree_root);
246 } else {
247 // Otherwise, recurse into children for detection.
248 for (AXNode* child : subtree_root->children()) {
249 DetectLanguagesForSubtree(child);
250 }
251 }
252 }
253
254 // Detect languages for a single node.
255 // Will not descend into children.
256 // Will not check feature flag.
DetectLanguagesForNode(AXNode * node)257 void AXLanguageDetectionManager::DetectLanguagesForNode(AXNode* node) {
258 // Count this detection attempt.
259 lang_info_stats_.RecordDetectionAttempt();
260
261 // TODO(chrishall): implement strategy for nodes which are too small to get
262 // reliable language detection results. Consider combination of
263 // concatenation and bubbling up results.
264 auto text = node->GetStringAttribute(ax::mojom::StringAttribute::kName);
265
266 // FindTopNMostFreqLangs() will pad the results with
267 // |NNetLanguageIdentifier::kUnknown| in order to reach the requested number
268 // of languages, this means we cannot rely on the results' length and we
269 // have to filter the results.
270 const std::vector<Result> results =
271 language_identifier_.FindTopNMostFreqLangs(text,
272 kMaxDetectedLanguagesPerSpan);
273
274 std::vector<std::string> reliable_results;
275
276 for (const auto& res : results) {
277 // The output of FindTopNMostFreqLangs() is already sorted by byte count,
278 // this seems good enough for now.
279 // Only consider results which are 'reliable', this will also remove
280 // 'unknown'.
281 if (res.is_reliable) {
282 reliable_results.push_back(res.language);
283 }
284 }
285
286 // Only allocate a(n) LanguageInfo if we have results worth keeping.
287 if (reliable_results.size()) {
288 AXLanguageInfo* lang_info = node->GetLanguageInfo();
289 if (lang_info) {
290 // Clear previously detected and labelled languages.
291 lang_info->detected_languages.clear();
292 lang_info->language.clear();
293 } else {
294 node->SetLanguageInfo(std::make_unique<AXLanguageInfo>());
295 lang_info = node->GetLanguageInfo();
296 }
297
298 // Keep these results.
299 lang_info->detected_languages = std::move(reliable_results);
300
301 // Update statistics to take these results into account.
302 lang_info_stats_.Add(lang_info->detected_languages);
303 }
304 }
305
306 // Label languages for each node. This relies on DetectLanguages having already
307 // been run.
LabelLanguages()308 void AXLanguageDetectionManager::LabelLanguages() {
309 TRACE_EVENT0("accessibility", "AXLanguageInfo::LabelLanguages");
310
311 if (!::switches::IsExperimentalAccessibilityLanguageDetectionEnabled()) {
312 return;
313 }
314
315 LabelLanguagesForSubtree(tree_->root());
316
317 // TODO(chrishall): consider refactoring to have a more clearly named entry
318 // point for static language detection.
319 //
320 // LabelLanguages is only called for the initial run of language detection for
321 // static content, this call to ReportMetrics therefore covers only the work
322 // we performed in response to a page load complete event.
323 lang_info_stats_.ReportMetrics();
324 }
325
326 // Label languages for each node in the subtree rooted at the given
327 // subtree_root. Will not check feature flag.
LabelLanguagesForSubtree(AXNode * subtree_root)328 void AXLanguageDetectionManager::LabelLanguagesForSubtree(
329 AXNode* subtree_root) {
330 LabelLanguagesForNode(subtree_root);
331
332 // Recurse into children to continue labelling.
333 for (AXNode* child : subtree_root->children()) {
334 LabelLanguagesForSubtree(child);
335 }
336 }
337
338 // Label languages for a single node.
339 // Will not descend into children.
340 // Will not check feature flag.
LabelLanguagesForNode(AXNode * node)341 void AXLanguageDetectionManager::LabelLanguagesForNode(AXNode* node) {
342 AXLanguageInfo* lang_info = node->GetLanguageInfo();
343 if (!lang_info)
344 return;
345
346 // There is no work to do if we already have an assigned (non-empty) language.
347 if (lang_info->language.size())
348 return;
349
350 // Assign the highest probability language which is both:
351 // 1) reliably detected for this node, and
352 // 2) one of the top (kMaxDetectedLanguagesPerPage) languages on this page.
353 //
354 // This helps guard against false positives for nodes which have noisy
355 // language detection results in isolation.
356 //
357 // Note that we assign a language even if it is the same as the author's
358 // annotation. This may not be needed in practice. In theory this would help
359 // if the author later on changed the language annotation to be incorrect, but
360 // this seems unlikely to occur in practice.
361 //
362 // TODO(chrishall): consider optimisation: only assign language if it
363 // disagrees with author's language annotation.
364 bool labelled_with_first_result = true;
365 for (const auto& lang : lang_info->detected_languages) {
366 if (lang_info_stats_.CheckLanguageWithinTop(lang)) {
367 lang_info->language = lang;
368
369 const std::string& author_lang = node->GetInheritedStringAttribute(
370 ax::mojom::StringAttribute::kLanguage);
371 lang_info_stats_.RecordLabelStatistics(lang, author_lang,
372 labelled_with_first_result);
373
374 // After assigning a label we no longer need detected languages.
375 // NB: clearing this invalidates the reference `lang`, so we must do this
376 // last and then immediately return.
377 lang_info->detected_languages.clear();
378
379 return;
380 }
381 labelled_with_first_result = false;
382 }
383
384 // If we didn't label a language, then we can discard all language detection
385 // information for this node.
386 node->ClearLanguageInfo();
387 }
388
389 std::vector<AXLanguageSpan>
GetLanguageAnnotationForStringAttribute(const AXNode & node,ax::mojom::StringAttribute attr)390 AXLanguageDetectionManager::GetLanguageAnnotationForStringAttribute(
391 const AXNode& node,
392 ax::mojom::StringAttribute attr) {
393 std::vector<AXLanguageSpan> language_annotation;
394 if (!node.HasStringAttribute(attr))
395 return language_annotation;
396
397 std::string attr_value = node.GetStringAttribute(attr);
398
399 // Use author-provided language if present.
400 if (node.HasStringAttribute(ax::mojom::StringAttribute::kLanguage)) {
401 // Use author-provided language if present.
402 language_annotation.push_back(AXLanguageSpan{
403 0 /* start_index */, int(attr_value.length()) /* end_index */,
404 node.GetStringAttribute(
405 ax::mojom::StringAttribute::kLanguage) /* language */,
406 1 /* probability */});
407 return language_annotation;
408 }
409 // Calculate top 3 languages.
410 // TODO(akihiroota): What's a reasonable number of languages to have
411 // cld_3 find? Should vary.
412 std::vector<Result> top_languages =
413 short_text_language_identifier_.FindTopNMostFreqLangs(
414 attr_value, kMaxDetectedLanguagesPerPage);
415 // Create vector of AXLanguageSpans.
416 for (const auto& result : top_languages) {
417 const std::vector<SpanInfo>& ranges = result.byte_ranges;
418 for (const auto& span_info : ranges) {
419 language_annotation.push_back(
420 AXLanguageSpan{span_info.start_index, span_info.end_index,
421 result.language, span_info.probability});
422 }
423 }
424 // Sort Language Annotations by increasing start index. LanguageAnnotations
425 // with lower start index should appear earlier in the vector.
426 std::sort(
427 language_annotation.begin(), language_annotation.end(),
428 [](const AXLanguageSpan& left, const AXLanguageSpan& right) -> bool {
429 return left.start_index <= right.start_index;
430 });
431 // Ensure that AXLanguageSpans do not overlap.
432 for (size_t i = 0; i < language_annotation.size(); ++i) {
433 if (i > 0) {
434 DCHECK(language_annotation[i].start_index <=
435 language_annotation[i - 1].end_index);
436 }
437 }
438 return language_annotation;
439 }
440
AXLanguageDetectionObserver(AXTree * tree)441 AXLanguageDetectionObserver::AXLanguageDetectionObserver(AXTree* tree)
442 : tree_(tree) {
443 // We expect the feature flag to have be checked before this Observer is
444 // constructed, this should have been checked by
445 // RegisterLanguageDetectionObserver.
446 DCHECK(
447 ::switches::IsExperimentalAccessibilityLanguageDetectionDynamicEnabled());
448
449 tree_->AddObserver(this);
450 }
451
~AXLanguageDetectionObserver()452 AXLanguageDetectionObserver::~AXLanguageDetectionObserver() {
453 tree_->RemoveObserver(this);
454 }
455
OnAtomicUpdateFinished(ui::AXTree * tree,bool root_changed,const std::vector<Change> & changes)456 void AXLanguageDetectionObserver::OnAtomicUpdateFinished(
457 ui::AXTree* tree,
458 bool root_changed,
459 const std::vector<Change>& changes) {
460 // TODO(chrishall): We likely want to re-consider updating or resetting
461 // AXLanguageInfoStats over time to better support detection on long running
462 // pages.
463
464 // TODO(chrishall): To support pruning deleted node data from stats we should
465 // consider implementing OnNodeWillBeDeleted. Other options available include:
466 // 1) move lang info from AXNode into a map on AXTree so that we can fetch
467 // based on id in here
468 // 2) AXLanguageInfo destructor could remove itself
469
470 // TODO(chrishall): Possible optimisation: only run detect/label for certain
471 // change.type(s)), at least NODE_CREATED, NODE_CHANGED, and SUBTREE_CREATED.
472
473 DCHECK(tree->language_detection_manager);
474
475 // Perform Detect and Label for each node changed or created.
476 // We currently only consider kStaticText for detection.
477 //
478 // Note that language inheritance is now handled by AXNode::GetLanguage.
479 //
480 // Note that since Label no longer handles language inheritance, we only need
481 // to call Label and Detect on the nodes that changed and don't need to
482 // recurse.
483 //
484 // We do this in two passes because Detect updates page level statistics which
485 // are later used by Label in order to make more accurate decisions.
486
487 for (auto& change : changes) {
488 if (change.node->data().role == ax::mojom::Role::kStaticText) {
489 tree->language_detection_manager->DetectLanguagesForNode(change.node);
490 }
491 }
492
493 for (auto& change : changes) {
494 if (change.node->data().role == ax::mojom::Role::kStaticText) {
495 tree->language_detection_manager->LabelLanguagesForNode(change.node);
496 }
497 }
498
499 // OnAtomicUpdateFinished is used for dynamic language detection, this call to
500 // ReportMetrics covers only the work we have performed in response to one
501 // update to the AXTree.
502 tree->language_detection_manager->lang_info_stats_.ReportMetrics();
503 }
504
505 } // namespace ui
506