content/browser/accessibility/accessibility_tree_formatter_base.cc - chromium/src - Git at Google

 // Copyright 2019 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "content/browser/accessibility/accessibility_tree_formatter_base.h"

 #include <stddef.h>

 #include <memory>
 #include <utility>
 #include <vector>

 #include "base/check_op.h"
 #include "base/strings/pattern.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_util.h"
 #include "base/strings/stringprintf.h"
 #include "base/strings/utf_string_conversions.h"
 #include "content/browser/accessibility/accessibility_tree_formatter_blink.h"
 #include "content/browser/accessibility/browser_accessibility_manager.h"
 #include "content/browser/renderer_host/render_widget_host_view_base.h"
 #include "content/browser/web_contents/web_contents_impl.h"
 #include "content/public/browser/web_contents.h"

 namespace content {

 namespace {

 const char kIndentSymbol = '+';
 const int kIndentSymbolCount = 2;
 const char kSkipString[] = "@NO_DUMP";
 const char kSkipChildren[] = "@NO_CHILDREN_DUMP";

 }  // namespace

 //
 // PropertyNode
 //

 // static
 PropertyNode PropertyNode::FromPropertyFilter(
     const ui::AXPropertyFilter& filter) {
   // Property invocation: property_str expected format is
   // prop_name or prop_name(arg1, ... argN).
   PropertyNode root;
   const std::string& property_str = filter.property_str;
   Parse(&root, property_str.begin(), property_str.end());

   PropertyNode* node = &root.parameters[0];

   // Expel a trailing wildcard if any.
   node->original_property =
       property_str.substr(0, property_str.find_last_of('*'));

   // Line indexes filter: filter_str expected format is
   // :line_num_1, ... :line_num_N, a comma separated list of line indexes
   // the property should be queried for. For example, ":1,:5,:7" indicates that
   // the property should called for objects placed on 1, 5 and 7 lines only.
   const std::string& filter_str = filter.filter_str;
   if (!filter_str.empty()) {
     node->line_indexes =
         base::SplitString(filter_str, std::string(1, ','),
                           base::TRIM_WHITESPACE, base::SPLIT_WANT_NONEMPTY);
   }

   return std::move(*node);
 }

 PropertyNode::PropertyNode() = default;
 PropertyNode::PropertyNode(PropertyNode&& o)
     : key(std::move(o.key)),
       target(std::move(o.target)),
       name_or_value(std::move(o.name_or_value)),
       parameters(std::move(o.parameters)),
       original_property(std::move(o.original_property)),
       line_indexes(std::move(o.line_indexes)) {}
 PropertyNode::~PropertyNode() = default;

 PropertyNode& PropertyNode::operator=(PropertyNode&& o) {
   key = std::move(o.key);
   target = std::move(o.target);
   name_or_value = std::move(o.name_or_value);
   parameters = std::move(o.parameters);
   original_property = std::move(o.original_property);
   line_indexes = std::move(o.line_indexes);
   return *this;
 }

 PropertyNode::operator bool() const {
   return !name_or_value.empty();
 }

 bool PropertyNode::IsMatching(const std::string& pattern) const {
   // Looking for exact property match. Expel a trailing whildcard from
   // the property filter to handle filters like AXRole*.
   return name_or_value.compare(0, name_or_value.find_last_of('*'), pattern) ==
          0;
 }

 bool PropertyNode::IsArray() const {
   return name_or_value == "[]";
 }

 bool PropertyNode::IsDict() const {
   return name_or_value == "{}";
 }

 base::Optional<int> PropertyNode::AsInt() const {
   int value = 0;
   if (!base::StringToInt(name_or_value, &value)) {
     return base::nullopt;
   }
   return value;
 }

 const PropertyNode* PropertyNode::FindKey(const char* refkey) const {
   for (const auto& param : parameters) {
     if (param.key == refkey) {
       return &param;
     }
   }
   return nullptr;
 }

 base::Optional<std::string> PropertyNode::FindStringKey(
     const char* refkey) const {
   for (const auto& param : parameters) {
     if (param.key == refkey) {
       return param.name_or_value;
     }
   }
   return base::nullopt;
 }

 base::Optional<int> PropertyNode::FindIntKey(const char* refkey) const {
   for (const auto& param : parameters) {
     if (param.key == refkey) {
       return param.AsInt();
     }
   }
   return base::nullopt;
 }

 std::string PropertyNode::ToString() const {
   std::string out;
   for (const auto& index : line_indexes) {
     if (!out.empty()) {
       out += ',';
     }
     out += index;
   }
   if (!out.empty()) {
     out += ';';
   }

   if (!key.empty()) {
     out += key + ": ";
   }

   if (!target.empty()) {
     out += target + '.';
   }
   out += name_or_value;
   if (parameters.size()) {
     out += '(';
     for (size_t i = 0; i < parameters.size(); i++) {
       if (i != 0) {
         out += ", ";
       }
       out += parameters[i].ToString();
     }
     out += ')';
   }
   return out;
 }

 // private
 PropertyNode::PropertyNode(PropertyNode::iterator key_begin,
                            PropertyNode::iterator key_end,
                            const std::string& name_or_value)
     : key(key_begin, key_end) {
   Set(name_or_value.begin(), name_or_value.end());
 }
 PropertyNode::PropertyNode(PropertyNode::iterator begin,
                            PropertyNode::iterator end) {
   Set(begin, end);
 }
 PropertyNode::PropertyNode(PropertyNode::iterator key_begin,
                            PropertyNode::iterator key_end,
                            PropertyNode::iterator value_begin,
                            PropertyNode::iterator value_end)
     : key(key_begin, key_end), name_or_value(value_begin, value_end) {
   Set(value_begin, value_end);
 }

 void PropertyNode::Set(PropertyNode::iterator begin,
                        PropertyNode::iterator end) {
   PropertyNode::iterator dot_operator = std::find(begin, end, '.');
   if (dot_operator != end) {
     target = std::string(begin, dot_operator);
     name_or_value = std::string(dot_operator + 1, end);
   } else {
     name_or_value = std::string(begin, end);
   }
 }

 // private static
 PropertyNode::iterator PropertyNode::Parse(PropertyNode* node,
                                            PropertyNode::iterator begin,
                                            PropertyNode::iterator end) {
   auto iter = begin;
   auto key_begin = end, key_end = end;
   while (iter != end) {
     // Subnode begins: create a new node, record its name and parse its
     // arguments.
     if (*iter == '(') {
       node->parameters.push_back(PropertyNode(key_begin, key_end, begin, iter));
       key_begin = key_end = end;
       begin = iter = Parse(&node->parameters.back(), ++iter, end);
       continue;
     }

     // Subnode begins: a special case for arrays, which have [arg1, ..., argN]
     // form.
     if (*iter == '[') {
       node->parameters.push_back(PropertyNode(key_begin, key_end, "[]"));
       key_begin = key_end = end;
       begin = iter = Parse(&node->parameters.back(), ++iter, end);
       continue;
     }

     // Subnode begins: a special case for dictionaries of {key1: value1, ...,
     // key2: value2} form.
     if (*iter == '{') {
       node->parameters.push_back(PropertyNode(key_begin, key_end, "{}"));
       key_begin = key_end = end;
       begin = iter = Parse(&node->parameters.back(), ++iter, end);
       continue;
     }

     // Subnode ends.
     if (*iter == ')' || *iter == ']' || *iter == '}') {
       if (begin != iter) {
         node->parameters.push_back(
             PropertyNode(key_begin, key_end, begin, iter));
         key_begin = key_end = end;
       }
       return ++iter;
     }

     // Dictionary key
     auto maybe_key_end = end;
     if (*iter == ':') {
       maybe_key_end = iter++;
     }

     // Skip spaces, adjust new node start.
     if (*iter == ' ') {
       if (maybe_key_end != end) {
         key_begin = begin;
         key_end = maybe_key_end;
       }
       begin = ++iter;
       continue;
     }

     // Subsequent scalar param case.
     if (*iter == ',' && begin != iter) {
       node->parameters.push_back(PropertyNode(key_begin, key_end, begin, iter));
       iter++;
       key_begin = key_end = end;
       begin = iter;
       continue;
     }

     iter++;
   }

   // Single scalar param case.
   if (begin != iter) {
     node->parameters.push_back(PropertyNode(begin, iter));
   }
   return iter;
 }

 //
 // AccessibilityTreeFormatter
 //

 // static
 std::string AccessibilityTreeFormatterBase::DumpAccessibilityTreeFromManager(
     BrowserAccessibilityManager* ax_mgr,
     bool internal,
     std::vector<AXPropertyFilter> property_filters) {
   std::unique_ptr<AccessibilityTreeFormatter> formatter;
   if (internal)
     formatter = std::make_unique<AccessibilityTreeFormatterBlink>();
   else
     formatter = Create();
   std::string accessibility_contents;
   formatter->SetPropertyFilters(property_filters);
   std::unique_ptr<base::DictionaryValue> dict =
       static_cast<AccessibilityTreeFormatterBase*>(formatter.get())
           ->BuildAccessibilityTree(ax_mgr->GetRoot());
   formatter->FormatAccessibilityTree(*dict, &accessibility_contents);
   return accessibility_contents;
 }

 bool AccessibilityTreeFormatter::MatchesPropertyFilters(
     const std::vector<AXPropertyFilter>& property_filters,
     const std::string& text,
     bool default_result) {
   bool allow = default_result;
   for (const auto& filter : property_filters) {
     // Either
     //   1) the line matches a filter pattern, for example, AXSubrole=* filter
     //      will match AXSubrole=AXTerm line or
     //   2) a property on the line is exactly equal to the filter pattern, for
     //      example, AXSubrole filter will match AXSubrole=AXTerm line.
     if (base::MatchPattern(text, filter.match_str) ||
         (filter.match_str.length() > 0 &&
          filter.match_str.find('=') == std::string::npos &&
          filter.match_str[filter.match_str.length() - 1] != '*' &&
          base::MatchPattern(text, filter.match_str + "=*"))) {
       switch (filter.type) {
         case AXPropertyFilter::ALLOW_EMPTY:
           allow = true;
           break;
         case AXPropertyFilter::ALLOW:
           allow = (!base::MatchPattern(text, "*=''"));
           break;
         case AXPropertyFilter::DENY:
           allow = false;
           break;
       }
     }
   }
   return allow;
 }

 bool AccessibilityTreeFormatter::MatchesNodeFilters(
     const std::vector<AXNodeFilter>& node_filters,
     const base::DictionaryValue& dict) {
   for (const auto& filter : node_filters) {
     std::string value;
     if (!dict.GetString(filter.property, &value)) {
       continue;
     }
     if (base::MatchPattern(value, filter.pattern)) {
       return true;
     }
   }
   return false;
 }

 AccessibilityTreeFormatterBase::AccessibilityTreeFormatterBase() = default;

 AccessibilityTreeFormatterBase::~AccessibilityTreeFormatterBase() = default;

 void AccessibilityTreeFormatterBase::FormatAccessibilityTree(
     const base::DictionaryValue& dict,
     std::string* contents) {
   RecursiveFormatAccessibilityTree(dict, contents);
 }

 void AccessibilityTreeFormatterBase::FormatAccessibilityTreeForTesting(
     ui::AXPlatformNodeDelegate* root,
     std::string* contents) {
   auto* node_internal = BrowserAccessibility::FromAXPlatformNodeDelegate(root);
   DCHECK(node_internal);
   FormatAccessibilityTree(*BuildAccessibilityTree(node_internal), contents);
 }

 std::unique_ptr<base::DictionaryValue>
 AccessibilityTreeFormatterBase::FilterAccessibilityTree(
     const base::DictionaryValue& dict) {
   auto filtered_dict = std::make_unique<base::DictionaryValue>();
   ProcessTreeForOutput(dict, filtered_dict.get());
   const base::ListValue* children;
   if (dict.GetList(kChildrenDictAttr, &children) && !children->empty()) {
     const base::DictionaryValue* child_dict;
     auto filtered_children = std::make_unique<base::ListValue>();
     for (size_t i = 0; i < children->GetSize(); i++) {
       children->GetDictionary(i, &child_dict);
       auto filtered_child = FilterAccessibilityTree(*child_dict);
       filtered_children->Append(std::move(filtered_child));
     }
     filtered_dict->Set(kChildrenDictAttr, std::move(filtered_children));
   }
   return filtered_dict;
 }

 void AccessibilityTreeFormatterBase::RecursiveFormatAccessibilityTree(
     const base::DictionaryValue& dict,
     std::string* contents,
     int depth) {
   // Check dictionary against node filters, may require us to skip this node
   // and its children.
   if (MatchesNodeFilters(dict))
     return;

   std::string indent = std::string(depth * kIndentSymbolCount, kIndentSymbol);
   std::string line = indent + ProcessTreeForOutput(dict);
   if (line.find(kSkipString) != std::string::npos)
     return;

   // Normalize any Windows-style line endings by removing \r.
   base::RemoveChars(line, "\r", &line);

   // Replace literal newlines with "<newline>"
   base::ReplaceChars(line, "\n", "<newline>", &line);

   *contents += line + "\n";
   if (line.find(kSkipChildren) != std::string::npos)
     return;

   const base::ListValue* children;
   if (!dict.GetList(kChildrenDictAttr, &children))
     return;
   const base::DictionaryValue* child_dict;
   for (size_t i = 0; i < children->GetSize(); i++) {
     children->GetDictionary(i, &child_dict);
     RecursiveFormatAccessibilityTree(*child_dict, contents, depth + 1);
   }
 }

 void AccessibilityTreeFormatterBase::SetPropertyFilters(
     const std::vector<AXPropertyFilter>& property_filters) {
   property_filters_ = property_filters;
 }

 void AccessibilityTreeFormatterBase::SetNodeFilters(
     const std::vector<AXNodeFilter>& node_filters) {
   node_filters_ = node_filters;
 }

 void AccessibilityTreeFormatterBase::set_show_ids(bool show_ids) {
   show_ids_ = show_ids;
 }

 base::FilePath::StringType
 AccessibilityTreeFormatterBase::GetVersionSpecificExpectedFileSuffix() {
   return FILE_PATH_LITERAL("");
 }

 std::vector<PropertyNode>
 AccessibilityTreeFormatterBase::PropertyFilterNodesFor(
     const std::string& line_index) const {
   std::vector<PropertyNode> list;
   for (const auto& filter : property_filters_) {
     PropertyNode property_node = PropertyNode::FromPropertyFilter(filter);

     // Filter out if doesn't match line index (if specified).
     if (!property_node.line_indexes.empty() &&
         std::find(property_node.line_indexes.begin(),
                   property_node.line_indexes.end(),
                   line_index) == property_node.line_indexes.end()) {
       continue;
     }

     switch (filter.type) {
       case AXPropertyFilter::ALLOW_EMPTY:
       case AXPropertyFilter::ALLOW:
         list.push_back(std::move(property_node));
         break;
       case AXPropertyFilter::DENY:
         break;
       default:
         break;
     }
   }
   return list;
 }

 bool AccessibilityTreeFormatterBase::HasMatchAllPropertyFilter() const {
   for (const auto& filter : property_filters_) {
     if (filter.type == AXPropertyFilter::ALLOW && filter.match_str == "*") {
       return true;
     }
   }
   return false;
 }

 bool AccessibilityTreeFormatterBase::MatchesPropertyFilters(
     const std::string& text,
     bool default_result) const {
   return AccessibilityTreeFormatter::MatchesPropertyFilters(
       property_filters_, text, default_result);
 }

 bool AccessibilityTreeFormatterBase::MatchesNodeFilters(
     const base::DictionaryValue& dict) const {
   return AccessibilityTreeFormatter::MatchesNodeFilters(node_filters_, dict);
 }

 std::string AccessibilityTreeFormatterBase::FormatCoordinates(
     const base::DictionaryValue& value,
     const std::string& name,
     const std::string& x_name,
     const std::string& y_name) {
   int x, y;
   value.GetInteger(x_name, &x);
   value.GetInteger(y_name, &y);
   return base::StringPrintf("%s=(%d, %d)", name.c_str(), x, y);
 }

 std::string AccessibilityTreeFormatterBase::FormatRectangle(
     const base::DictionaryValue& value,
     const std::string& name,
     const std::string& left_name,
     const std::string& top_name,
     const std::string& width_name,
     const std::string& height_name) {
   int left, top, width, height;
   value.GetInteger(left_name, &left);
   value.GetInteger(top_name, &top);
   value.GetInteger(width_name, &width);
   value.GetInteger(height_name, &height);
   return base::StringPrintf("%s=(%d, %d, %d, %d)", name.c_str(), left, top,
                             width, height);
 }

 bool AccessibilityTreeFormatterBase::WriteAttribute(bool include_by_default,
                                                     const std::string& attr,
                                                     std::string* line) {
   if (attr.empty())
     return false;
   if (!MatchesPropertyFilters(attr, include_by_default))
     return false;
   if (!line->empty())
     *line += " ";
   *line += attr;
   return true;
 }

 void AccessibilityTreeFormatterBase::AddPropertyFilter(
     std::vector<AXPropertyFilter>* property_filters,
     std::string filter,
     AXPropertyFilter::Type type) {
   property_filters->push_back(AXPropertyFilter(filter, type));
 }

 void AccessibilityTreeFormatterBase::AddDefaultFilters(
     std::vector<AXPropertyFilter>* property_filters) {}

 }  // namespace content
	// Copyright 2019 The Chromium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "content/browser/accessibility/accessibility_tree_formatter_base.h"

	#include <stddef.h>

	#include <memory>
	#include <utility>
	#include <vector>

	#include "base/check_op.h"
	#include "base/strings/pattern.h"
	#include "base/strings/string_number_conversions.h"
	#include "base/strings/string_util.h"
	#include "base/strings/stringprintf.h"
	#include "base/strings/utf_string_conversions.h"
	#include "content/browser/accessibility/accessibility_tree_formatter_blink.h"
	#include "content/browser/accessibility/browser_accessibility_manager.h"
	#include "content/browser/renderer_host/render_widget_host_view_base.h"
	#include "content/browser/web_contents/web_contents_impl.h"
	#include "content/public/browser/web_contents.h"

	namespace content {

	namespace {

	const char kIndentSymbol = '+';
	const int kIndentSymbolCount = 2;
	const char kSkipString[] = "@NO_DUMP";
	const char kSkipChildren[] = "@NO_CHILDREN_DUMP";

	} // namespace

	//
	// PropertyNode
	//

	// static
	PropertyNode PropertyNode::FromPropertyFilter(
	const ui::AXPropertyFilter& filter) {
	// Property invocation: property_str expected format is
	// prop_name or prop_name(arg1, ... argN).
	PropertyNode root;
	const std::string& property_str = filter.property_str;
	Parse(&root, property_str.begin(), property_str.end());

	PropertyNode* node = &root.parameters[0];

	// Expel a trailing wildcard if any.
	node->original_property =
	property_str.substr(0, property_str.find_last_of('*'));

	// Line indexes filter: filter_str expected format is
	// :line_num_1, ... :line_num_N, a comma separated list of line indexes
	// the property should be queried for. For example, ":1,:5,:7" indicates that
	// the property should called for objects placed on 1, 5 and 7 lines only.
	const std::string& filter_str = filter.filter_str;
	if (!filter_str.empty()) {
	node->line_indexes =
	base::SplitString(filter_str, std::string(1, ','),
	base::TRIM_WHITESPACE, base::SPLIT_WANT_NONEMPTY);
	}

	return std::move(*node);
	}

	PropertyNode::PropertyNode() = default;
	PropertyNode::PropertyNode(PropertyNode&& o)
	: key(std::move(o.key)),
	target(std::move(o.target)),
	name_or_value(std::move(o.name_or_value)),
	parameters(std::move(o.parameters)),
	original_property(std::move(o.original_property)),
	line_indexes(std::move(o.line_indexes)) {}
	PropertyNode::~PropertyNode() = default;

	PropertyNode& PropertyNode::operator=(PropertyNode&& o) {
	key = std::move(o.key);
	target = std::move(o.target);
	name_or_value = std::move(o.name_or_value);
	parameters = std::move(o.parameters);
	original_property = std::move(o.original_property);
	line_indexes = std::move(o.line_indexes);
	return *this;
	}

	PropertyNode::operator bool() const {
	return !name_or_value.empty();
	}

	bool PropertyNode::IsMatching(const std::string& pattern) const {
	// Looking for exact property match. Expel a trailing whildcard from
	// the property filter to handle filters like AXRole*.
	return name_or_value.compare(0, name_or_value.find_last_of('*'), pattern) ==
	0;
	}

	bool PropertyNode::IsArray() const {
	return name_or_value == "[]";
	}

	bool PropertyNode::IsDict() const {
	return name_or_value == "{}";
	}

	base::Optional<int> PropertyNode::AsInt() const {
	int value = 0;
	if (!base::StringToInt(name_or_value, &value)) {
	return base::nullopt;
	}
	return value;
	}

	const PropertyNode* PropertyNode::FindKey(const char* refkey) const {
	for (const auto& param : parameters) {
	if (param.key == refkey) {
	return &param;
	}
	}
	return nullptr;
	}

	base::Optional<std::string> PropertyNode::FindStringKey(
	const char* refkey) const {
	for (const auto& param : parameters) {
	if (param.key == refkey) {
	return param.name_or_value;
	}
	}
	return base::nullopt;
	}

	base::Optional<int> PropertyNode::FindIntKey(const char* refkey) const {
	for (const auto& param : parameters) {
	if (param.key == refkey) {
	return param.AsInt();
	}
	}
	return base::nullopt;
	}

	std::string PropertyNode::ToString() const {
	std::string out;
	for (const auto& index : line_indexes) {
	if (!out.empty()) {
	out += ',';
	}
	out += index;
	}
	if (!out.empty()) {
	out += ';';
	}

	if (!key.empty()) {
	out += key + ": ";
	}

	if (!target.empty()) {
	out += target + '.';
	}
	out += name_or_value;
	if (parameters.size()) {
	out += '(';
	for (size_t i = 0; i < parameters.size(); i++) {
	if (i != 0) {
	out += ", ";
	}
	out += parameters[i].ToString();
	}
	out += ')';
	}
	return out;
	}

	// private
	PropertyNode::PropertyNode(PropertyNode::iterator key_begin,
	PropertyNode::iterator key_end,
	const std::string& name_or_value)
	: key(key_begin, key_end) {
	Set(name_or_value.begin(), name_or_value.end());
	}
	PropertyNode::PropertyNode(PropertyNode::iterator begin,
	PropertyNode::iterator end) {
	Set(begin, end);
	}
	PropertyNode::PropertyNode(PropertyNode::iterator key_begin,
	PropertyNode::iterator key_end,
	PropertyNode::iterator value_begin,
	PropertyNode::iterator value_end)
	: key(key_begin, key_end), name_or_value(value_begin, value_end) {
	Set(value_begin, value_end);
	}

	void PropertyNode::Set(PropertyNode::iterator begin,
	PropertyNode::iterator end) {
	PropertyNode::iterator dot_operator = std::find(begin, end, '.');
	if (dot_operator != end) {
	target = std::string(begin, dot_operator);
	name_or_value = std::string(dot_operator + 1, end);
	} else {
	name_or_value = std::string(begin, end);
	}
	}

	// private static
	PropertyNode::iterator PropertyNode::Parse(PropertyNode* node,
	PropertyNode::iterator begin,
	PropertyNode::iterator end) {
	auto iter = begin;
	auto key_begin = end, key_end = end;
	while (iter != end) {
	// Subnode begins: create a new node, record its name and parse its
	// arguments.
	if (*iter == '(') {
	node->parameters.push_back(PropertyNode(key_begin, key_end, begin, iter));
	key_begin = key_end = end;
	begin = iter = Parse(&node->parameters.back(), ++iter, end);
	continue;
	}

	// Subnode begins: a special case for arrays, which have [arg1, ..., argN]
	// form.
	if (*iter == '[') {
	node->parameters.push_back(PropertyNode(key_begin, key_end, "[]"));
	key_begin = key_end = end;
	begin = iter = Parse(&node->parameters.back(), ++iter, end);
	continue;
	}

	// Subnode begins: a special case for dictionaries of {key1: value1, ...,
	// key2: value2} form.
	if (*iter == '{') {
	node->parameters.push_back(PropertyNode(key_begin, key_end, "{}"));
	key_begin = key_end = end;
	begin = iter = Parse(&node->parameters.back(), ++iter, end);
	continue;
	}

	// Subnode ends.
	if (iter == ')' \|\| iter == ']' \|\| *iter == '}') {
	if (begin != iter) {
	node->parameters.push_back(
	PropertyNode(key_begin, key_end, begin, iter));
	key_begin = key_end = end;
	}
	return ++iter;
	}

	// Dictionary key
	auto maybe_key_end = end;
	if (*iter == ':') {
	maybe_key_end = iter++;
	}

	// Skip spaces, adjust new node start.
	if (*iter == ' ') {
	if (maybe_key_end != end) {
	key_begin = begin;
	key_end = maybe_key_end;
	}
	begin = ++iter;
	continue;
	}

	// Subsequent scalar param case.
	if (*iter == ',' && begin != iter) {
	node->parameters.push_back(PropertyNode(key_begin, key_end, begin, iter));
	iter++;
	key_begin = key_end = end;
	begin = iter;
	continue;
	}

	iter++;
	}

	// Single scalar param case.
	if (begin != iter) {
	node->parameters.push_back(PropertyNode(begin, iter));
	}
	return iter;
	}

	//
	// AccessibilityTreeFormatter
	//

	// static
	std::string AccessibilityTreeFormatterBase::DumpAccessibilityTreeFromManager(
	BrowserAccessibilityManager* ax_mgr,
	bool internal,
	std::vector<AXPropertyFilter> property_filters) {
	std::unique_ptr<AccessibilityTreeFormatter> formatter;
	if (internal)
	formatter = std::make_unique<AccessibilityTreeFormatterBlink>();
	else
	formatter = Create();
	std::string accessibility_contents;
	formatter->SetPropertyFilters(property_filters);
	std::unique_ptr<base::DictionaryValue> dict =
	static_cast<AccessibilityTreeFormatterBase*>(formatter.get())
	->BuildAccessibilityTree(ax_mgr->GetRoot());
	formatter->FormatAccessibilityTree(*dict, &accessibility_contents);
	return accessibility_contents;
	}

	bool AccessibilityTreeFormatter::MatchesPropertyFilters(
	const std::vector<AXPropertyFilter>& property_filters,
	const std::string& text,
	bool default_result) {
	bool allow = default_result;
	for (const auto& filter : property_filters) {
	// Either
	// 1) the line matches a filter pattern, for example, AXSubrole=* filter
	// will match AXSubrole=AXTerm line or
	// 2) a property on the line is exactly equal to the filter pattern, for
	// example, AXSubrole filter will match AXSubrole=AXTerm line.
	if (base::MatchPattern(text, filter.match_str) \|\|
	(filter.match_str.length() > 0 &&
	filter.match_str.find('=') == std::string::npos &&
	filter.match_str[filter.match_str.length() - 1] != '*' &&
	base::MatchPattern(text, filter.match_str + "=*"))) {
	switch (filter.type) {
	case AXPropertyFilter::ALLOW_EMPTY:
	allow = true;
	break;
	case AXPropertyFilter::ALLOW:
	allow = (!base::MatchPattern(text, "*=''"));
	break;
	case AXPropertyFilter::DENY:
	allow = false;
	break;
	}
	}
	}
	return allow;
	}

	bool AccessibilityTreeFormatter::MatchesNodeFilters(
	const std::vector<AXNodeFilter>& node_filters,
	const base::DictionaryValue& dict) {
	for (const auto& filter : node_filters) {
	std::string value;
	if (!dict.GetString(filter.property, &value)) {
	continue;
	}
	if (base::MatchPattern(value, filter.pattern)) {
	return true;
	}
	}
	return false;
	}

	AccessibilityTreeFormatterBase::AccessibilityTreeFormatterBase() = default;

	AccessibilityTreeFormatterBase::~AccessibilityTreeFormatterBase() = default;

	void AccessibilityTreeFormatterBase::FormatAccessibilityTree(
	const base::DictionaryValue& dict,
	std::string* contents) {
	RecursiveFormatAccessibilityTree(dict, contents);
	}

	void AccessibilityTreeFormatterBase::FormatAccessibilityTreeForTesting(
	ui::AXPlatformNodeDelegate* root,
	std::string* contents) {
	auto* node_internal = BrowserAccessibility::FromAXPlatformNodeDelegate(root);
	DCHECK(node_internal);
	FormatAccessibilityTree(*BuildAccessibilityTree(node_internal), contents);
	}

	std::unique_ptr<base::DictionaryValue>
	AccessibilityTreeFormatterBase::FilterAccessibilityTree(
	const base::DictionaryValue& dict) {
	auto filtered_dict = std::make_unique<base::DictionaryValue>();
	ProcessTreeForOutput(dict, filtered_dict.get());
	const base::ListValue* children;
	if (dict.GetList(kChildrenDictAttr, &children) && !children->empty()) {
	const base::DictionaryValue* child_dict;
	auto filtered_children = std::make_unique<base::ListValue>();
	for (size_t i = 0; i < children->GetSize(); i++) {
	children->GetDictionary(i, &child_dict);
	auto filtered_child = FilterAccessibilityTree(*child_dict);
	filtered_children->Append(std::move(filtered_child));
	}
	filtered_dict->Set(kChildrenDictAttr, std::move(filtered_children));
	}
	return filtered_dict;
	}

	void AccessibilityTreeFormatterBase::RecursiveFormatAccessibilityTree(
	const base::DictionaryValue& dict,
	std::string* contents,
	int depth) {
	// Check dictionary against node filters, may require us to skip this node
	// and its children.
	if (MatchesNodeFilters(dict))
	return;

	std::string indent = std::string(depth * kIndentSymbolCount, kIndentSymbol);
	std::string line = indent + ProcessTreeForOutput(dict);
	if (line.find(kSkipString) != std::string::npos)
	return;

	// Normalize any Windows-style line endings by removing \r.
	base::RemoveChars(line, "\r", &line);

	// Replace literal newlines with "<newline>"
	base::ReplaceChars(line, "\n", "<newline>", &line);

	*contents += line + "\n";
	if (line.find(kSkipChildren) != std::string::npos)
	return;

	const base::ListValue* children;
	if (!dict.GetList(kChildrenDictAttr, &children))
	return;
	const base::DictionaryValue* child_dict;
	for (size_t i = 0; i < children->GetSize(); i++) {
	children->GetDictionary(i, &child_dict);
	RecursiveFormatAccessibilityTree(*child_dict, contents, depth + 1);
	}
	}

	void AccessibilityTreeFormatterBase::SetPropertyFilters(
	const std::vector<AXPropertyFilter>& property_filters) {
	property_filters_ = property_filters;
	}

	void AccessibilityTreeFormatterBase::SetNodeFilters(
	const std::vector<AXNodeFilter>& node_filters) {
	node_filters_ = node_filters;
	}

	void AccessibilityTreeFormatterBase::set_show_ids(bool show_ids) {
	show_ids_ = show_ids;
	}

	base::FilePath::StringType
	AccessibilityTreeFormatterBase::GetVersionSpecificExpectedFileSuffix() {
	return FILE_PATH_LITERAL("");
	}

	std::vector<PropertyNode>
	AccessibilityTreeFormatterBase::PropertyFilterNodesFor(
	const std::string& line_index) const {
	std::vector<PropertyNode> list;
	for (const auto& filter : property_filters_) {
	PropertyNode property_node = PropertyNode::FromPropertyFilter(filter);

	// Filter out if doesn't match line index (if specified).
	if (!property_node.line_indexes.empty() &&
	std::find(property_node.line_indexes.begin(),
	property_node.line_indexes.end(),
	line_index) == property_node.line_indexes.end()) {
	continue;
	}

	switch (filter.type) {
	case AXPropertyFilter::ALLOW_EMPTY:
	case AXPropertyFilter::ALLOW:
	list.push_back(std::move(property_node));
	break;
	case AXPropertyFilter::DENY:
	break;
	default:
	break;
	}
	}
	return list;
	}

	bool AccessibilityTreeFormatterBase::HasMatchAllPropertyFilter() const {
	for (const auto& filter : property_filters_) {
	if (filter.type == AXPropertyFilter::ALLOW && filter.match_str == "*") {
	return true;
	}
	}
	return false;
	}

	bool AccessibilityTreeFormatterBase::MatchesPropertyFilters(
	const std::string& text,
	bool default_result) const {
	return AccessibilityTreeFormatter::MatchesPropertyFilters(
	property_filters_, text, default_result);
	}

	bool AccessibilityTreeFormatterBase::MatchesNodeFilters(
	const base::DictionaryValue& dict) const {
	return AccessibilityTreeFormatter::MatchesNodeFilters(node_filters_, dict);
	}

	std::string AccessibilityTreeFormatterBase::FormatCoordinates(
	const base::DictionaryValue& value,
	const std::string& name,
	const std::string& x_name,
	const std::string& y_name) {
	int x, y;
	value.GetInteger(x_name, &x);
	value.GetInteger(y_name, &y);
	return base::StringPrintf("%s=(%d, %d)", name.c_str(), x, y);
	}

	std::string AccessibilityTreeFormatterBase::FormatRectangle(
	const base::DictionaryValue& value,
	const std::string& name,
	const std::string& left_name,
	const std::string& top_name,
	const std::string& width_name,
	const std::string& height_name) {
	int left, top, width, height;
	value.GetInteger(left_name, &left);
	value.GetInteger(top_name, &top);
	value.GetInteger(width_name, &width);
	value.GetInteger(height_name, &height);
	return base::StringPrintf("%s=(%d, %d, %d, %d)", name.c_str(), left, top,
	width, height);
	}

	bool AccessibilityTreeFormatterBase::WriteAttribute(bool include_by_default,
	const std::string& attr,
	std::string* line) {
	if (attr.empty())
	return false;
	if (!MatchesPropertyFilters(attr, include_by_default))
	return false;
	if (!line->empty())
	*line += " ";
	*line += attr;
	return true;
	}

	void AccessibilityTreeFormatterBase::AddPropertyFilter(
	std::vector<AXPropertyFilter>* property_filters,
	std::string filter,
	AXPropertyFilter::Type type) {
	property_filters->push_back(AXPropertyFilter(filter, type));
	}

	void AccessibilityTreeFormatterBase::AddDefaultFilters(
	std::vector<AXPropertyFilter>* property_filters) {}

	} // namespace content