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 "components/autofill_assistant/browser/web/element_finder.h"
6 
7 #include "components/autofill_assistant/browser/devtools/devtools_client.h"
8 #include "components/autofill_assistant/browser/service.pb.h"
9 #include "components/autofill_assistant/browser/web/web_controller_util.h"
10 #include "content/public/browser/render_frame_host.h"
11 #include "content/public/browser/web_contents.h"
12 
13 namespace autofill_assistant {
14 
15 namespace {
16 // Javascript code to get document root element.
17 const char kGetDocumentElement[] =
18     "(function() { return document.documentElement; }())";
19 
20 const char kGetArrayElement[] = "function(index) { return this[index]; }";
21 
ConvertPseudoType(const PseudoType pseudo_type,dom::PseudoType * pseudo_type_output)22 bool ConvertPseudoType(const PseudoType pseudo_type,
23                        dom::PseudoType* pseudo_type_output) {
24   switch (pseudo_type) {
25     case PseudoType::UNDEFINED:
26       break;
27     case PseudoType::FIRST_LINE:
28       *pseudo_type_output = dom::PseudoType::FIRST_LINE;
29       return true;
30     case PseudoType::FIRST_LETTER:
31       *pseudo_type_output = dom::PseudoType::FIRST_LETTER;
32       return true;
33     case PseudoType::BEFORE:
34       *pseudo_type_output = dom::PseudoType::BEFORE;
35       return true;
36     case PseudoType::AFTER:
37       *pseudo_type_output = dom::PseudoType::AFTER;
38       return true;
39     case PseudoType::BACKDROP:
40       *pseudo_type_output = dom::PseudoType::BACKDROP;
41       return true;
42     case PseudoType::SELECTION:
43       *pseudo_type_output = dom::PseudoType::SELECTION;
44       return true;
45     case PseudoType::FIRST_LINE_INHERITED:
46       *pseudo_type_output = dom::PseudoType::FIRST_LINE_INHERITED;
47       return true;
48     case PseudoType::SCROLLBAR:
49       *pseudo_type_output = dom::PseudoType::SCROLLBAR;
50       return true;
51     case PseudoType::SCROLLBAR_THUMB:
52       *pseudo_type_output = dom::PseudoType::SCROLLBAR_THUMB;
53       return true;
54     case PseudoType::SCROLLBAR_BUTTON:
55       *pseudo_type_output = dom::PseudoType::SCROLLBAR_BUTTON;
56       return true;
57     case PseudoType::SCROLLBAR_TRACK:
58       *pseudo_type_output = dom::PseudoType::SCROLLBAR_TRACK;
59       return true;
60     case PseudoType::SCROLLBAR_TRACK_PIECE:
61       *pseudo_type_output = dom::PseudoType::SCROLLBAR_TRACK_PIECE;
62       return true;
63     case PseudoType::SCROLLBAR_CORNER:
64       *pseudo_type_output = dom::PseudoType::SCROLLBAR_CORNER;
65       return true;
66     case PseudoType::RESIZER:
67       *pseudo_type_output = dom::PseudoType::RESIZER;
68       return true;
69     case PseudoType::INPUT_LIST_BUTTON:
70       *pseudo_type_output = dom::PseudoType::INPUT_LIST_BUTTON;
71       return true;
72   }
73   return false;
74 }
75 }  // namespace
76 
77 ElementFinder::JsFilterBuilder::JsFilterBuilder() = default;
78 ElementFinder::JsFilterBuilder::~JsFilterBuilder() = default;
79 
80 std::vector<std::unique_ptr<runtime::CallArgument>>
BuildArgumentList() const81 ElementFinder::JsFilterBuilder::BuildArgumentList() const {
82   auto str_array_arg = std::make_unique<base::Value>(base::Value::Type::LIST);
83   for (const std::string& str : arguments_) {
84     str_array_arg->Append(str);
85   }
86   std::vector<std::unique_ptr<runtime::CallArgument>> arguments;
87   arguments.emplace_back(runtime::CallArgument::Builder()
88                              .SetValue(std::move(str_array_arg))
89                              .Build());
90   return arguments;
91 }
92 
93 // clang-format off
BuildFunction() const94 std::string ElementFinder::JsFilterBuilder::BuildFunction() const {
95   return base::StrCat({
96     R"(
97     function(args) {
98       let elements = [this];
99     )",
100     snippet_.ToString(),
101     R"(
102       if (elements.length == 0) return null;
103       if (elements.length == 1) { return elements[0] }
104       return elements;
105     })"
106   });
107 }
108 // clang-format on
109 
AddFilter(const SelectorProto::Filter & filter)110 bool ElementFinder::JsFilterBuilder::AddFilter(
111     const SelectorProto::Filter& filter) {
112   switch (filter.filter_case()) {
113     case SelectorProto::Filter::kCssSelector:
114       // We querySelectorAll the current elements and remove duplicates, which
115       // are likely when using inner text before CSS selector filters. We must
116       // not return duplicates as they cause incorrect TOO_MANY_ELEMENTS errors.
117       DefineQueryAllDeduplicated();
118       AddLine({"elements = queryAllDeduplicated(elements, ",
119                AddArgument(filter.css_selector()), ");"});
120       return true;
121 
122     case SelectorProto::Filter::kInnerText:
123       AddRegexpFilter(filter.inner_text(), "innerText");
124       return true;
125 
126     case SelectorProto::Filter::kValue:
127       AddRegexpFilter(filter.value(), "value");
128       return true;
129 
130     case SelectorProto::Filter::kBoundingBox:
131       if (filter.bounding_box().require_nonempty()) {
132         AddLine("elements = elements.filter((e) => {");
133         AddLine("  const rect = e.getBoundingClientRect();");
134         AddLine("  return rect.width != 0 && rect.height != 0;");
135         AddLine("});");
136       } else {
137         AddLine(
138             "elements = elements.filter((e) => e.getClientRects().length > "
139             "0);");
140       }
141       return true;
142 
143     case SelectorProto::Filter::kPseudoElementContent: {
144       // When a content is set, window.getComputedStyle().content contains a
145       // double-quoted string with the content, unquoted here by JSON.parse().
146       std::string re_var =
147           AddRegexpInstance(filter.pseudo_element_content().content());
148       std::string pseudo_type =
149           PseudoTypeName(filter.pseudo_element_content().pseudo_type());
150 
151       AddLine("elements = elements.filter((e) => {");
152       AddLine({"  const s = window.getComputedStyle(e, '", pseudo_type, "');"});
153       AddLine("  if (!s || !s.content || !s.content.startsWith('\"')) {");
154       AddLine("    return false;");
155       AddLine("  }");
156       AddLine({"  return ", re_var, ".test(JSON.parse(s.content));"});
157       AddLine("});");
158       return true;
159     }
160 
161     case SelectorProto::Filter::kCssStyle: {
162       std::string re_var = AddRegexpInstance(filter.css_style().value());
163       std::string property = AddArgument(filter.css_style().property());
164       std::string element = AddArgument(filter.css_style().pseudo_element());
165       AddLine("elements = elements.filter((e) => {");
166       AddLine("  const s = window.getComputedStyle(e, ");
167       AddLine({"      ", element, " === '' ? null : ", element, ");"});
168       AddLine({"  const match = ", re_var, ".test(s[", property, "]);"});
169       if (filter.css_style().should_match()) {
170         AddLine("  return match;");
171       } else {
172         AddLine("  return !match;");
173       }
174       AddLine("});");
175       return true;
176     }
177 
178     case SelectorProto::Filter::kLabelled:
179       AddLine("elements = elements.flatMap((e) => {");
180       AddLine(
181           "  return e.tagName === 'LABEL' && e.control ? [e.control] : [];");
182       AddLine("});");
183       return true;
184 
185     case SelectorProto::Filter::kMatchCssSelector:
186       AddLine({"elements = elements.filter((e) => e.webkitMatchesSelector(",
187                AddArgument(filter.match_css_selector()), "));"});
188       return true;
189 
190     case SelectorProto::Filter::kOnTop:
191       AddLine("elements = elements.filter((e) => {");
192       AddLine("if (e.getClientRects().length == 0) return false;");
193       if (filter.on_top().scroll_into_view_if_needed()) {
194         AddLine("e.scrollIntoViewIfNeeded(false);");
195       }
196       AddReturnIfOnTop(
197           &snippet_, "e", /* on_top= */ "true", /* not_on_top= */ "false",
198           /* not_in_view= */ filter.on_top().accept_element_if_not_in_view()
199               ? "true"
200               : "false");
201       AddLine("});");
202       return true;
203 
204     case SelectorProto::Filter::kEnterFrame:
205     case SelectorProto::Filter::kPseudoType:
206     case SelectorProto::Filter::kNthMatch:
207     case SelectorProto::Filter::kClosest:
208     case SelectorProto::Filter::FILTER_NOT_SET:
209       return false;
210   }
211 }
212 
AddRegexpInstance(const SelectorProto::TextFilter & filter)213 std::string ElementFinder::JsFilterBuilder::AddRegexpInstance(
214     const SelectorProto::TextFilter& filter) {
215   std::string re_flags = filter.case_sensitive() ? "" : "i";
216   std::string re_var = DeclareVariable();
217   AddLine({"const ", re_var, " = RegExp(", AddArgument(filter.re2()), ", '",
218            re_flags, "');"});
219   return re_var;
220 }
221 
AddRegexpFilter(const SelectorProto::TextFilter & filter,const std::string & property)222 void ElementFinder::JsFilterBuilder::AddRegexpFilter(
223     const SelectorProto::TextFilter& filter,
224     const std::string& property) {
225   std::string re_var = AddRegexpInstance(filter);
226   AddLine({"elements = elements.filter((e) => ", re_var, ".test(e.", property,
227            "));"});
228 }
229 
DeclareVariable()230 std::string ElementFinder::JsFilterBuilder::DeclareVariable() {
231   return base::StrCat({"v", base::NumberToString(variable_counter_++)});
232 }
233 
AddArgument(const std::string & value)234 std::string ElementFinder::JsFilterBuilder::AddArgument(
235     const std::string& value) {
236   int index = arguments_.size();
237   arguments_.emplace_back(value);
238   return base::StrCat({"args[", base::NumberToString(index), "]"});
239 }
240 
DefineQueryAllDeduplicated()241 void ElementFinder::JsFilterBuilder::DefineQueryAllDeduplicated() {
242   // Ensure that we don't define the function more than once.
243   if (defined_query_all_deduplicated_)
244     return;
245 
246   defined_query_all_deduplicated_ = true;
247 
248   AddLine(R"(
249     const queryAllDeduplicated = function(roots, selector) {
250       if (roots.length == 0) {
251         return [];
252       }
253 
254       const matchesSet = new Set();
255       const matches = [];
256       roots.forEach((root) => {
257         root.querySelectorAll(selector).forEach((elem) => {
258           if (!matchesSet.has(elem)) {
259             matchesSet.add(elem);
260             matches.push(elem);
261           }
262         });
263       });
264       return matches;
265     }
266   )");
267 }
268 
269 ElementFinder::Result::Result() = default;
270 
271 ElementFinder::Result::~Result() = default;
272 
273 ElementFinder::Result::Result(const Result&) = default;
274 
ElementFinder(content::WebContents * web_contents,DevtoolsClient * devtools_client,const Selector & selector,ResultType result_type)275 ElementFinder::ElementFinder(content::WebContents* web_contents,
276                              DevtoolsClient* devtools_client,
277                              const Selector& selector,
278                              ResultType result_type)
279     : web_contents_(web_contents),
280       devtools_client_(devtools_client),
281       selector_(selector),
282       result_type_(result_type) {}
283 
284 ElementFinder::~ElementFinder() = default;
285 
Start(Callback callback)286 void ElementFinder::Start(Callback callback) {
287   StartInternal(std::move(callback), web_contents_->GetMainFrame(),
288                 /* frame_id= */ "", /* document_object_id= */ "");
289 }
290 
StartInternal(Callback callback,content::RenderFrameHost * frame,const std::string & frame_id,const std::string & document_object_id)291 void ElementFinder::StartInternal(Callback callback,
292                                   content::RenderFrameHost* frame,
293                                   const std::string& frame_id,
294                                   const std::string& document_object_id) {
295   callback_ = std::move(callback);
296 
297   if (selector_.empty()) {
298     SendResult(ClientStatus(INVALID_SELECTOR));
299     return;
300   }
301 
302   current_frame_ = frame;
303   current_frame_id_ = frame_id;
304   current_frame_root_ = document_object_id;
305   if (current_frame_root_.empty()) {
306     GetDocumentElement();
307   } else {
308     current_matches_.emplace_back(current_frame_root_);
309     ExecuteNextTask();
310   }
311 }
312 
SendResult(const ClientStatus & status)313 void ElementFinder::SendResult(const ClientStatus& status) {
314   if (!callback_)
315     return;
316 
317   std::move(callback_).Run(status, std::make_unique<Result>());
318 }
319 
SendSuccessResult(const std::string & object_id)320 void ElementFinder::SendSuccessResult(const std::string& object_id) {
321   if (!callback_)
322     return;
323 
324   // Fill in result and return
325   std::unique_ptr<Result> result =
326       std::make_unique<Result>(BuildResult(object_id));
327   result->frame_stack = frame_stack_;
328   std::move(callback_).Run(OkClientStatus(), std::move(result));
329 }
330 
BuildResult(const std::string & object_id)331 ElementFinder::Result ElementFinder::BuildResult(const std::string& object_id) {
332   Result result;
333   result.container_frame_host = current_frame_;
334   result.object_id = object_id;
335   result.node_frame_id = current_frame_id_;
336   return result;
337 }
338 
ExecuteNextTask()339 void ElementFinder::ExecuteNextTask() {
340   const auto& filters = selector_.proto.filters();
341 
342   if (next_filter_index_ >= filters.size()) {
343     std::string object_id;
344     switch (result_type_) {
345       case ResultType::kExactlyOneMatch:
346         if (!ConsumeOneMatchOrFail(object_id)) {
347           return;
348         }
349         break;
350 
351       case ResultType::kAnyMatch:
352         if (!ConsumeMatchAtOrFail(0, object_id)) {
353           return;
354         }
355         break;
356 
357       case ResultType::kMatchArray:
358         if (!ConsumeMatchArrayOrFail(object_id)) {
359           return;
360         }
361         break;
362     }
363     SendSuccessResult(object_id);
364     return;
365   }
366 
367   const auto& filter = filters.Get(next_filter_index_);
368   switch (filter.filter_case()) {
369     case SelectorProto::Filter::kEnterFrame: {
370       std::string object_id;
371       if (!ConsumeOneMatchOrFail(object_id))
372         return;
373 
374       // The above fails if there is more than one frame. To preserve
375       // backward-compatibility with the previous, lax behavior, callers must
376       // add pick_one before enter_frame. TODO(b/155264465): allow searching in
377       // more than one frame.
378       next_filter_index_++;
379       EnterFrame(object_id);
380       return;
381     }
382 
383     case SelectorProto::Filter::kPseudoType: {
384       std::vector<std::string> matches;
385       if (!ConsumeAllMatchesOrFail(matches))
386         return;
387 
388       next_filter_index_++;
389       matching_pseudo_elements_ = true;
390       ResolvePseudoElement(filter.pseudo_type(), matches);
391       return;
392     }
393 
394     case SelectorProto::Filter::kNthMatch: {
395       std::string object_id;
396       if (!ConsumeMatchAtOrFail(filter.nth_match().index(), object_id))
397         return;
398 
399       next_filter_index_++;
400       current_matches_ = {object_id};
401       ExecuteNextTask();
402       return;
403     }
404 
405     case SelectorProto::Filter::kCssSelector:
406     case SelectorProto::Filter::kInnerText:
407     case SelectorProto::Filter::kValue:
408     case SelectorProto::Filter::kBoundingBox:
409     case SelectorProto::Filter::kPseudoElementContent:
410     case SelectorProto::Filter::kMatchCssSelector:
411     case SelectorProto::Filter::kCssStyle:
412     case SelectorProto::Filter::kLabelled:
413     case SelectorProto::Filter::kOnTop: {
414       std::vector<std::string> matches;
415       if (!ConsumeAllMatchesOrFail(matches))
416         return;
417 
418       JsFilterBuilder js_filter;
419       for (int i = next_filter_index_; i < filters.size(); i++) {
420         if (!js_filter.AddFilter(filters.Get(i))) {
421           break;
422         }
423         next_filter_index_++;
424       }
425       ApplyJsFilters(js_filter, matches);
426       return;
427     }
428 
429     case SelectorProto::Filter::kClosest: {
430       std::string array_object_id;
431       if (!ConsumeMatchArrayOrFail(array_object_id))
432         return;
433 
434       ApplyProximityFilter(next_filter_index_++, array_object_id);
435       return;
436     }
437 
438     case SelectorProto::Filter::FILTER_NOT_SET:
439       VLOG(1) << __func__ << " Unset or unknown filter in " << filter << " in "
440               << selector_;
441       SendResult(ClientStatus(INVALID_SELECTOR));
442       return;
443   }
444 }
445 
ConsumeOneMatchOrFail(std::string & object_id_out)446 bool ElementFinder::ConsumeOneMatchOrFail(std::string& object_id_out) {
447   if (current_matches_.size() > 1) {
448     VLOG(1) << __func__ << " Got " << current_matches_.size() << " matches for "
449             << selector_ << ", when only 1 was expected.";
450     SendResult(ClientStatus(TOO_MANY_ELEMENTS));
451     return false;
452   }
453   if (current_matches_.empty()) {
454     SendResult(ClientStatus(ELEMENT_RESOLUTION_FAILED));
455     return false;
456   }
457 
458   object_id_out = current_matches_[0];
459   current_matches_.clear();
460   return true;
461 }
462 
ConsumeMatchAtOrFail(size_t index,std::string & object_id_out)463 bool ElementFinder::ConsumeMatchAtOrFail(size_t index,
464                                          std::string& object_id_out) {
465   if (index < current_matches_.size()) {
466     object_id_out = current_matches_[index];
467     current_matches_.clear();
468     return true;
469   }
470 
471   SendResult(ClientStatus(ELEMENT_RESOLUTION_FAILED));
472   return false;
473 }
474 
ConsumeAllMatchesOrFail(std::vector<std::string> & matches_out)475 bool ElementFinder::ConsumeAllMatchesOrFail(
476     std::vector<std::string>& matches_out) {
477   if (!current_matches_.empty()) {
478     matches_out = std::move(current_matches_);
479     current_matches_.clear();
480     return true;
481   }
482   SendResult(ClientStatus(ELEMENT_RESOLUTION_FAILED));
483   return false;
484 }
485 
ConsumeMatchArrayOrFail(std::string & array_object_id)486 bool ElementFinder::ConsumeMatchArrayOrFail(std::string& array_object_id) {
487   if (!current_matches_js_array_.empty()) {
488     array_object_id = current_matches_js_array_;
489     current_matches_js_array_.clear();
490     return true;
491   }
492 
493   if (current_matches_.empty()) {
494     SendResult(ClientStatus(ELEMENT_RESOLUTION_FAILED));
495     return false;
496   }
497 
498   MoveMatchesToJSArrayRecursive(/* index= */ 0);
499   return false;
500 }
501 
MoveMatchesToJSArrayRecursive(size_t index)502 void ElementFinder::MoveMatchesToJSArrayRecursive(size_t index) {
503   if (index >= current_matches_.size()) {
504     current_matches_.clear();
505     ExecuteNextTask();
506     return;
507   }
508 
509   // Push the value at |current_matches_[index]| to |current_matches_js_array_|.
510   std::string function;
511   std::vector<std::unique_ptr<runtime::CallArgument>> arguments;
512   if (index == 0) {
513     // Create an array containing a single element.
514     function = "function() { return [this]; }";
515   } else {
516     // Add an element to an existing array.
517     function = "function(dest) { dest.push(this); }";
518     AddRuntimeCallArgumentObjectId(current_matches_js_array_, &arguments);
519   }
520 
521   devtools_client_->GetRuntime()->CallFunctionOn(
522       runtime::CallFunctionOnParams::Builder()
523           .SetObjectId(current_matches_[index])
524           .SetArguments(std::move(arguments))
525           .SetFunctionDeclaration(function)
526           .Build(),
527       current_frame_id_,
528       base::BindOnce(&ElementFinder::OnMoveMatchesToJSArrayRecursive,
529                      weak_ptr_factory_.GetWeakPtr(), index));
530 }
531 
OnMoveMatchesToJSArrayRecursive(size_t index,const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<runtime::CallFunctionOnResult> result)532 void ElementFinder::OnMoveMatchesToJSArrayRecursive(
533     size_t index,
534     const DevtoolsClient::ReplyStatus& reply_status,
535     std::unique_ptr<runtime::CallFunctionOnResult> result) {
536   ClientStatus status =
537       CheckJavaScriptResult(reply_status, result.get(), __FILE__, __LINE__);
538   if (!status.ok()) {
539     VLOG(1) << __func__ << ": Failed to push value to JS array.";
540     SendResult(status);
541     return;
542   }
543 
544   // We just created an array which contains the first element. We store its ID
545   // in |current_matches_js_array_|.
546   if (index == 0 &&
547       !SafeGetObjectId(result->GetResult(), &current_matches_js_array_)) {
548     VLOG(1) << __func__ << " Failed to get array ID.";
549     SendResult(ClientStatus(ELEMENT_RESOLUTION_FAILED));
550     return;
551   }
552 
553   // Continue the recursion to push the other values into the array.
554   MoveMatchesToJSArrayRecursive(index + 1);
555 }
556 
GetDocumentElement()557 void ElementFinder::GetDocumentElement() {
558   devtools_client_->GetRuntime()->Evaluate(
559       std::string(kGetDocumentElement), current_frame_id_,
560       base::BindOnce(&ElementFinder::OnGetDocumentElement,
561                      weak_ptr_factory_.GetWeakPtr()));
562 }
563 
OnGetDocumentElement(const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<runtime::EvaluateResult> result)564 void ElementFinder::OnGetDocumentElement(
565     const DevtoolsClient::ReplyStatus& reply_status,
566     std::unique_ptr<runtime::EvaluateResult> result) {
567   ClientStatus status =
568       CheckJavaScriptResult(reply_status, result.get(), __FILE__, __LINE__);
569   if (!status.ok()) {
570     VLOG(1) << __func__ << " Failed to get document root element.";
571     SendResult(status);
572     return;
573   }
574   std::string object_id;
575   if (!SafeGetObjectId(result->GetResult(), &object_id)) {
576     VLOG(1) << __func__ << " Failed to get document root element.";
577     SendResult(ClientStatus(ELEMENT_RESOLUTION_FAILED));
578     return;
579   }
580 
581   current_frame_root_ = object_id;
582   // Use the node as root for the rest of the evaluation.
583   current_matches_.emplace_back(object_id);
584 
585   ExecuteNextTask();
586 }
587 
ApplyJsFilters(const JsFilterBuilder & builder,const std::vector<std::string> & object_ids)588 void ElementFinder::ApplyJsFilters(const JsFilterBuilder& builder,
589                                    const std::vector<std::string>& object_ids) {
590   DCHECK(!object_ids.empty());  // Guaranteed by ExecuteNextTask()
591   PrepareBatchTasks(object_ids.size());
592   std::string function = builder.BuildFunction();
593   for (size_t task_id = 0; task_id < object_ids.size(); task_id++) {
594     devtools_client_->GetRuntime()->CallFunctionOn(
595         runtime::CallFunctionOnParams::Builder()
596             .SetObjectId(object_ids[task_id])
597             .SetArguments(builder.BuildArgumentList())
598             .SetFunctionDeclaration(function)
599             .Build(),
600         current_frame_id_,
601         base::BindOnce(&ElementFinder::OnApplyJsFilters,
602                        weak_ptr_factory_.GetWeakPtr(), task_id));
603   }
604 }
605 
OnApplyJsFilters(size_t task_id,const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<runtime::CallFunctionOnResult> result)606 void ElementFinder::OnApplyJsFilters(
607     size_t task_id,
608     const DevtoolsClient::ReplyStatus& reply_status,
609     std::unique_ptr<runtime::CallFunctionOnResult> result) {
610   if (!result) {
611     // It is possible for a document element to already exist, but not be
612     // available yet to query because the document hasn't been loaded. This
613     // results in OnQuerySelectorAll getting a nullptr result. For this specific
614     // call, it is expected.
615     VLOG(1) << __func__ << ": Context doesn't exist yet to query frame "
616             << frame_stack_.size() << " of " << selector_;
617     SendResult(ClientStatus(ELEMENT_RESOLUTION_FAILED));
618     return;
619   }
620   ClientStatus status =
621       CheckJavaScriptResult(reply_status, result.get(), __FILE__, __LINE__);
622   if (!status.ok()) {
623     VLOG(1) << __func__ << ": Failed to query selector for frame "
624             << frame_stack_.size() << " of " << selector_ << ": " << status;
625     SendResult(status);
626     return;
627   }
628 
629   // The result can be empty (nothing found), an array (multiple matches
630   // found) or a single node.
631   std::string object_id;
632   if (!SafeGetObjectId(result->GetResult(), &object_id)) {
633     ReportNoMatchingElement(task_id);
634     return;
635   }
636 
637   if (result->GetResult()->HasSubtype() &&
638       result->GetResult()->GetSubtype() ==
639           runtime::RemoteObjectSubtype::ARRAY) {
640     ReportMatchingElementsArray(task_id, object_id);
641     return;
642   }
643 
644   ReportMatchingElement(task_id, object_id);
645 }
646 
ResolvePseudoElement(PseudoType proto_pseudo_type,const std::vector<std::string> & object_ids)647 void ElementFinder::ResolvePseudoElement(
648     PseudoType proto_pseudo_type,
649     const std::vector<std::string>& object_ids) {
650   dom::PseudoType pseudo_type;
651   if (!ConvertPseudoType(proto_pseudo_type, &pseudo_type)) {
652     VLOG(1) << __func__ << ": Unsupported pseudo-type "
653             << PseudoTypeName(proto_pseudo_type);
654     SendResult(ClientStatus(INVALID_ACTION));
655     return;
656   }
657 
658   DCHECK(!object_ids.empty());  // Guaranteed by ExecuteNextTask()
659   PrepareBatchTasks(object_ids.size());
660   for (size_t task_id = 0; task_id < object_ids.size(); task_id++) {
661     devtools_client_->GetDOM()->DescribeNode(
662         dom::DescribeNodeParams::Builder()
663             .SetObjectId(object_ids[task_id])
664             .Build(),
665         current_frame_id_,
666         base::BindOnce(&ElementFinder::OnDescribeNodeForPseudoElement,
667                        weak_ptr_factory_.GetWeakPtr(), pseudo_type, task_id));
668   }
669 }
670 
OnDescribeNodeForPseudoElement(dom::PseudoType pseudo_type,size_t task_id,const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<dom::DescribeNodeResult> result)671 void ElementFinder::OnDescribeNodeForPseudoElement(
672     dom::PseudoType pseudo_type,
673     size_t task_id,
674     const DevtoolsClient::ReplyStatus& reply_status,
675     std::unique_ptr<dom::DescribeNodeResult> result) {
676   if (!result || !result->GetNode()) {
677     VLOG(1) << __func__ << " Failed to describe the node for pseudo element.";
678     SendResult(UnexpectedDevtoolsErrorStatus(reply_status, __FILE__, __LINE__));
679     return;
680   }
681 
682   auto* node = result->GetNode();
683   if (node->HasPseudoElements()) {
684     for (const auto& pseudo_element : *(node->GetPseudoElements())) {
685       if (pseudo_element->HasPseudoType() &&
686           pseudo_element->GetPseudoType() == pseudo_type) {
687         devtools_client_->GetDOM()->ResolveNode(
688             dom::ResolveNodeParams::Builder()
689                 .SetBackendNodeId(pseudo_element->GetBackendNodeId())
690                 .Build(),
691             current_frame_id_,
692             base::BindOnce(&ElementFinder::OnResolveNodeForPseudoElement,
693                            weak_ptr_factory_.GetWeakPtr(), task_id));
694         return;
695       }
696     }
697   }
698 
699   ReportNoMatchingElement(task_id);
700 }
701 
OnResolveNodeForPseudoElement(size_t task_id,const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<dom::ResolveNodeResult> result)702 void ElementFinder::OnResolveNodeForPseudoElement(
703     size_t task_id,
704     const DevtoolsClient::ReplyStatus& reply_status,
705     std::unique_ptr<dom::ResolveNodeResult> result) {
706   if (result && result->GetObject() && result->GetObject()->HasObjectId()) {
707     ReportMatchingElement(task_id, result->GetObject()->GetObjectId());
708     return;
709   }
710 
711   ReportNoMatchingElement(task_id);
712 }
713 
EnterFrame(const std::string & object_id)714 void ElementFinder::EnterFrame(const std::string& object_id) {
715   devtools_client_->GetDOM()->DescribeNode(
716       dom::DescribeNodeParams::Builder().SetObjectId(object_id).Build(),
717       current_frame_id_,
718       base::BindOnce(&ElementFinder::OnDescribeNodeForFrame,
719                      weak_ptr_factory_.GetWeakPtr(), object_id));
720 }
721 
OnDescribeNodeForFrame(const std::string & object_id,const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<dom::DescribeNodeResult> result)722 void ElementFinder::OnDescribeNodeForFrame(
723     const std::string& object_id,
724     const DevtoolsClient::ReplyStatus& reply_status,
725     std::unique_ptr<dom::DescribeNodeResult> result) {
726   if (!result || !result->GetNode()) {
727     VLOG(1) << __func__ << " Failed to describe the node.";
728     SendResult(UnexpectedDevtoolsErrorStatus(reply_status, __FILE__, __LINE__));
729     return;
730   }
731 
732   auto* node = result->GetNode();
733   std::vector<int> backend_ids;
734 
735   if (node->GetNodeName() == "IFRAME") {
736     DCHECK(node->HasFrameId());  // Ensure all frames have an id.
737 
738     frame_stack_.push_back(BuildResult(object_id));
739 
740     auto* frame = FindCorrespondingRenderFrameHost(node->GetFrameId());
741     if (!frame) {
742       VLOG(1) << __func__ << " Failed to find corresponding owner frame.";
743       SendResult(ClientStatus(FRAME_HOST_NOT_FOUND));
744       return;
745     }
746     current_frame_ = frame;
747     current_frame_root_.clear();
748 
749     if (node->HasContentDocument()) {
750       // If the frame has a ContentDocument it's considered a local frame. In
751       // this case, current_frame_ doesn't change and can directly use the
752       // content document as root for the evaluation.
753       backend_ids.emplace_back(node->GetContentDocument()->GetBackendNodeId());
754     } else {
755       current_frame_id_ = node->GetFrameId();
756       // Kick off another find element chain to walk down the OOP iFrame.
757       GetDocumentElement();
758       return;
759     }
760   }
761 
762   if (node->HasShadowRoots()) {
763     // TODO(crbug.com/806868): Support multiple shadow roots.
764     backend_ids.emplace_back(
765         node->GetShadowRoots()->front()->GetBackendNodeId());
766   }
767 
768   if (!backend_ids.empty()) {
769     devtools_client_->GetDOM()->ResolveNode(
770         dom::ResolveNodeParams::Builder()
771             .SetBackendNodeId(backend_ids[0])
772             .Build(),
773         current_frame_id_,
774         base::BindOnce(&ElementFinder::OnResolveNode,
775                        weak_ptr_factory_.GetWeakPtr()));
776     return;
777   }
778 
779   // Element was not a frame and didn't have shadow dom. This is unexpected, but
780   // to remain backward compatible, don't complain and just continue filtering
781   // with the current element as root.
782   current_matches_.emplace_back(object_id);
783   ExecuteNextTask();
784 }
785 
OnResolveNode(const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<dom::ResolveNodeResult> result)786 void ElementFinder::OnResolveNode(
787     const DevtoolsClient::ReplyStatus& reply_status,
788     std::unique_ptr<dom::ResolveNodeResult> result) {
789   if (!result || !result->GetObject() || !result->GetObject()->HasObjectId()) {
790     VLOG(1) << __func__ << " Failed to resolve object id from backend id.";
791     SendResult(UnexpectedDevtoolsErrorStatus(reply_status, __FILE__, __LINE__));
792     return;
793   }
794 
795   std::string object_id = result->GetObject()->GetObjectId();
796   if (current_frame_root_.empty()) {
797     current_frame_root_ = object_id;
798   }
799   // Use the node as root for the rest of the evaluation.
800   current_matches_.emplace_back(object_id);
801   ExecuteNextTask();
802 }
803 
FindCorrespondingRenderFrameHost(std::string frame_id)804 content::RenderFrameHost* ElementFinder::FindCorrespondingRenderFrameHost(
805     std::string frame_id) {
806   for (auto* frame : web_contents_->GetAllFrames()) {
807     if (frame->GetDevToolsFrameToken().ToString() == frame_id) {
808       return frame;
809     }
810   }
811 
812   return nullptr;
813 }
814 
ApplyProximityFilter(int filter_index,const std::string & array_object_id)815 void ElementFinder::ApplyProximityFilter(int filter_index,
816                                          const std::string& array_object_id) {
817   Selector target_selector;
818   target_selector.proto.mutable_filters()->MergeFrom(
819       selector_.proto.filters(filter_index).closest().target());
820   proximity_target_filter_ =
821       std::make_unique<ElementFinder>(web_contents_, devtools_client_,
822                                       target_selector, ResultType::kMatchArray);
823   proximity_target_filter_->StartInternal(
824       base::BindOnce(&ElementFinder::OnProximityFilterTarget,
825                      weak_ptr_factory_.GetWeakPtr(), filter_index,
826                      array_object_id),
827       current_frame_, current_frame_id_, current_frame_root_);
828 }
829 
OnProximityFilterTarget(int filter_index,const std::string & array_object_id,const ClientStatus & status,std::unique_ptr<Result> result)830 void ElementFinder::OnProximityFilterTarget(int filter_index,
831                                             const std::string& array_object_id,
832                                             const ClientStatus& status,
833                                             std::unique_ptr<Result> result) {
834   if (!status.ok()) {
835     VLOG(1) << __func__
836             << " Could not find proximity filter target for resolving "
837             << selector_.proto.filters(filter_index);
838     SendResult(status);
839     return;
840   }
841   if (result->container_frame_host != current_frame_) {
842     VLOG(1) << __func__ << " Cannot compare elements on different frames.";
843     SendResult(ClientStatus(INVALID_SELECTOR));
844     return;
845   }
846 
847   const auto& filter = selector_.proto.filters(filter_index).closest();
848 
849   std::string function = R"(function(targets, maxPairs) {
850   const candidates = this;
851   const pairs = candidates.length * targets.length;
852   if (pairs > maxPairs) {
853     return pairs;
854   }
855   const candidateBoxes = candidates.map((e) => e.getBoundingClientRect());
856   let closest = null;
857   let shortestDistance = Number.POSITIVE_INFINITY;
858   for (target of targets) {
859     const targetBox = target.getBoundingClientRect();
860     for (let i = 0; i < candidates.length; i++) {
861       const box = candidateBoxes[i];
862 )";
863 
864   if (filter.in_alignment()) {
865     // Rejects candidates that are not on the same row or or the same column as
866     // the target.
867     function.append("if ((box.bottom <= targetBox.top || ");
868     function.append("     box.top >= targetBox.bottom) && ");
869     function.append("    (box.right <= targetBox.left || ");
870     function.append("     box.left >= targetBox.right)) continue;");
871   }
872   switch (filter.relative_position()) {
873     case SelectorProto::ProximityFilter::UNSPECIFIED_POSITION:
874       // No constraints.
875       break;
876 
877     case SelectorProto::ProximityFilter::ABOVE:
878       // Candidate must be above target
879       function.append("if (box.bottom > targetBox.top) continue;");
880       break;
881 
882     case SelectorProto::ProximityFilter::BELOW:
883       // Candidate must be below target
884       function.append("if (box.top < targetBox.bottom) continue;");
885       break;
886 
887     case SelectorProto::ProximityFilter::LEFT:
888       // Candidate must be left of target
889       function.append("if (box.right > targetBox.left) continue;");
890       break;
891 
892     case SelectorProto::ProximityFilter::RIGHT:
893       // Candidate must be right of target
894       function.append("if (box.left < targetBox.right) continue;");
895       break;
896   }
897 
898   // The algorithm below computes distance to the closest border. If the
899   // distance is 0, then we have got our closest element and can stop there.
900   function.append(R"(
901       let w = 0;
902       if (targetBox.right < box.left) {
903         w = box.left - targetBox.right;
904       } else if (box.right < targetBox.left) {
905         w = targetBox.left - box.right;
906       }
907       let h = 0;
908       if (targetBox.bottom < box.top) {
909         h = box.top - targetBox.bottom;
910       } else if (box.bottom < targetBox.top) {
911         h = targetBox.top - box.bottom;
912       }
913       const dist = Math.sqrt(h * h + w * w);
914       if (dist == 0) return candidates[i];
915       if (dist < shortestDistance) {
916         closest = candidates[i];
917         shortestDistance = dist;
918       }
919     }
920   }
921   return closest;
922 })");
923 
924   std::vector<std::unique_ptr<runtime::CallArgument>> arguments;
925   AddRuntimeCallArgumentObjectId(result->object_id, &arguments);
926   AddRuntimeCallArgument(filter.max_pairs(), &arguments);
927 
928   devtools_client_->GetRuntime()->CallFunctionOn(
929       runtime::CallFunctionOnParams::Builder()
930           .SetObjectId(array_object_id)
931           .SetArguments(std::move(arguments))
932           .SetFunctionDeclaration(function)
933           .Build(),
934       current_frame_id_,
935       base::BindOnce(&ElementFinder::OnProximityFilterJs,
936                      weak_ptr_factory_.GetWeakPtr()));
937 }
938 
OnProximityFilterJs(const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<runtime::CallFunctionOnResult> result)939 void ElementFinder::OnProximityFilterJs(
940     const DevtoolsClient::ReplyStatus& reply_status,
941     std::unique_ptr<runtime::CallFunctionOnResult> result) {
942   ClientStatus status =
943       CheckJavaScriptResult(reply_status, result.get(), __FILE__, __LINE__);
944   if (!status.ok()) {
945     VLOG(1) << __func__ << ": Failed to execute proximity filter " << status;
946     SendResult(status);
947     return;
948   }
949 
950   std::string object_id;
951   if (SafeGetObjectId(result->GetResult(), &object_id)) {
952     // Function found a match.
953     current_matches_.push_back(object_id);
954     ExecuteNextTask();
955     return;
956   }
957 
958   int pair_count = 0;
959   if (SafeGetIntValue(result->GetResult(), &pair_count)) {
960     // Function got too many pairs to check.
961     VLOG(1) << __func__ << ": Too many pairs to consider for proximity checks: "
962             << pair_count;
963     SendResult(ClientStatus(TOO_MANY_CANDIDATES));
964     return;
965   }
966 
967   // Function found nothing, which is possible if the relative position
968   // constraints forced the algorithm to discard all candidates.
969   ExecuteNextTask();
970 }
971 
PrepareBatchTasks(int n)972 void ElementFinder::PrepareBatchTasks(int n) {
973   tasks_results_.clear();
974   tasks_results_.resize(n);
975 }
976 
ReportMatchingElement(size_t task_id,const std::string & object_id)977 void ElementFinder::ReportMatchingElement(size_t task_id,
978                                           const std::string& object_id) {
979   tasks_results_[task_id] =
980       std::make_unique<std::vector<std::string>>(1, object_id);
981   MaybeFinalizeBatchTasks();
982 }
983 
ReportNoMatchingElement(size_t task_id)984 void ElementFinder::ReportNoMatchingElement(size_t task_id) {
985   tasks_results_[task_id] = std::make_unique<std::vector<std::string>>();
986   MaybeFinalizeBatchTasks();
987 }
988 
ReportMatchingElementsArray(size_t task_id,const std::string & array_object_id)989 void ElementFinder::ReportMatchingElementsArray(
990     size_t task_id,
991     const std::string& array_object_id) {
992   // Recursively add each element ID to a vector then report it as this task
993   // result.
994   ReportMatchingElementsArrayRecursive(
995       task_id, array_object_id, std::make_unique<std::vector<std::string>>(),
996       /* index= */ 0);
997 }
998 
ReportMatchingElementsArrayRecursive(size_t task_id,const std::string & array_object_id,std::unique_ptr<std::vector<std::string>> acc,int index)999 void ElementFinder::ReportMatchingElementsArrayRecursive(
1000     size_t task_id,
1001     const std::string& array_object_id,
1002     std::unique_ptr<std::vector<std::string>> acc,
1003     int index) {
1004   std::vector<std::unique_ptr<runtime::CallArgument>> arguments;
1005   AddRuntimeCallArgument(index, &arguments);
1006   devtools_client_->GetRuntime()->CallFunctionOn(
1007       runtime::CallFunctionOnParams::Builder()
1008           .SetObjectId(array_object_id)
1009           .SetArguments(std::move(arguments))
1010           .SetFunctionDeclaration(std::string(kGetArrayElement))
1011           .Build(),
1012       current_frame_id_,
1013       base::BindOnce(&ElementFinder::OnReportMatchingElementsArrayRecursive,
1014                      weak_ptr_factory_.GetWeakPtr(), task_id, array_object_id,
1015                      std::move(acc), index));
1016 }
1017 
OnReportMatchingElementsArrayRecursive(size_t task_id,const std::string & array_object_id,std::unique_ptr<std::vector<std::string>> acc,int index,const DevtoolsClient::ReplyStatus & reply_status,std::unique_ptr<runtime::CallFunctionOnResult> result)1018 void ElementFinder::OnReportMatchingElementsArrayRecursive(
1019     size_t task_id,
1020     const std::string& array_object_id,
1021     std::unique_ptr<std::vector<std::string>> acc,
1022     int index,
1023     const DevtoolsClient::ReplyStatus& reply_status,
1024     std::unique_ptr<runtime::CallFunctionOnResult> result) {
1025   ClientStatus status =
1026       CheckJavaScriptResult(reply_status, result.get(), __FILE__, __LINE__);
1027   if (!status.ok()) {
1028     VLOG(1) << __func__ << ": Failed to get element from array for "
1029             << selector_;
1030     SendResult(status);
1031     return;
1032   }
1033 
1034   std::string object_id;
1035   if (!SafeGetObjectId(result->GetResult(), &object_id)) {
1036     // We've reached the end of the array.
1037     tasks_results_[task_id] = std::move(acc);
1038     MaybeFinalizeBatchTasks();
1039     return;
1040   }
1041 
1042   acc->emplace_back(object_id);
1043 
1044   // Fetch the next element.
1045   ReportMatchingElementsArrayRecursive(task_id, array_object_id, std::move(acc),
1046                                        index + 1);
1047 }
1048 
MaybeFinalizeBatchTasks()1049 void ElementFinder::MaybeFinalizeBatchTasks() {
1050   // Return early if one of the tasks is still pending.
1051   for (const auto& result : tasks_results_) {
1052     if (!result) {
1053       return;
1054     }
1055   }
1056 
1057   // Add all matching elements to current_matches_.
1058   for (const auto& result : tasks_results_) {
1059     current_matches_.insert(current_matches_.end(), result->begin(),
1060                             result->end());
1061   }
1062   tasks_results_.clear();
1063 
1064   ExecuteNextTask();
1065 }
1066 
1067 }  // namespace autofill_assistant
1068