| Index: third_party/WebKit/Source/core/layout/ng/inline/ng_offset_mapping_builder.cc | 
| diff --git a/third_party/WebKit/Source/core/layout/ng/inline/ng_offset_mapping_builder.cc b/third_party/WebKit/Source/core/layout/ng/inline/ng_offset_mapping_builder.cc | 
| index 4d42e54cf8429eec5eddbf5f3518bde3e7466b46..46c551c224066683e16223b7fb2e9dc0cd94b9dd 100644 | 
| --- a/third_party/WebKit/Source/core/layout/ng/inline/ng_offset_mapping_builder.cc | 
| +++ b/third_party/WebKit/Source/core/layout/ng/inline/ng_offset_mapping_builder.cc | 
| @@ -4,10 +4,47 @@ | 
|  | 
| #include "core/layout/ng/inline/ng_offset_mapping_builder.h" | 
|  | 
| +#include "core/layout/ng/inline/ng_offset_mapping_result.h" | 
| #include "platform/wtf/text/StringBuilder.h" | 
|  | 
| namespace blink { | 
|  | 
| +namespace { | 
| + | 
| +// Returns the type of a unit-length simple offset mapping. | 
| +NGOffsetMappingUnitType GetUnitLengthMappingType(unsigned value) { | 
| +  if (value == 0u) | 
| +    return NGOffsetMappingUnitType::kCollapsed; | 
| +  if (value == 1u) | 
| +    return NGOffsetMappingUnitType::kIdentity; | 
| +  return NGOffsetMappingUnitType::kExpanded; | 
| +} | 
| + | 
| +// Finds the offset mapping unit starting from index |start|. | 
| +std::pair<NGOffsetMappingUnitType, unsigned> GetMappingUnitTypeAndEnd( | 
| +    const Vector<unsigned>& mapping, | 
| +    const Vector<const LayoutText*>& annotation, | 
| +    unsigned start) { | 
| +  DCHECK_LT(start + 1, mapping.size()); | 
| +  NGOffsetMappingUnitType type = | 
| +      GetUnitLengthMappingType(mapping[start + 1] - mapping[start]); | 
| +  if (type == NGOffsetMappingUnitType::kExpanded) | 
| +    return std::make_pair(type, start + 1); | 
| + | 
| +  unsigned end = start + 1; | 
| +  for (; end + 1 < mapping.size(); ++end) { | 
| +    if (annotation[end] != annotation[start]) | 
| +      break; | 
| +    NGOffsetMappingUnitType next_type = | 
| +        GetUnitLengthMappingType(mapping[end + 1] - mapping[end]); | 
| +    if (next_type != type) | 
| +      break; | 
| +  } | 
| +  return std::make_pair(type, end); | 
| +} | 
| + | 
| +}  // namespace | 
| + | 
| NGOffsetMappingBuilder::NGOffsetMappingBuilder() { | 
| mapping_.push_back(0); | 
| } | 
| @@ -19,6 +56,7 @@ void NGOffsetMappingBuilder::AppendIdentityMapping(unsigned length) { | 
| unsigned next = mapping_.back() + 1; | 
| mapping_.push_back(next); | 
| } | 
| +  annotation_.resize(annotation_.size() + length); | 
| } | 
|  | 
| void NGOffsetMappingBuilder::AppendCollapsedMapping(unsigned length) { | 
| @@ -27,6 +65,7 @@ void NGOffsetMappingBuilder::AppendCollapsedMapping(unsigned length) { | 
| const unsigned back = mapping_.back(); | 
| for (unsigned i = 0; i < length; ++i) | 
| mapping_.push_back(back); | 
| +  annotation_.resize(annotation_.size() + length); | 
| } | 
|  | 
| void NGOffsetMappingBuilder::CollapseTrailingSpace(unsigned skip_length) { | 
| @@ -43,8 +82,77 @@ void NGOffsetMappingBuilder::CollapseTrailingSpace(unsigned skip_length) { | 
| } | 
| } | 
|  | 
| +void NGOffsetMappingBuilder::Annotate(const LayoutText* layout_object) { | 
| +  std::fill(annotation_.begin(), annotation_.end(), layout_object); | 
| +} | 
| + | 
| +void NGOffsetMappingBuilder::Concatenate(const NGOffsetMappingBuilder& other) { | 
| +  DCHECK(!mapping_.IsEmpty()); | 
| +  DCHECK(!other.mapping_.IsEmpty()); | 
| +  const unsigned shift_amount = mapping_.back(); | 
| +  for (unsigned i = 1; i < other.mapping_.size(); ++i) | 
| +    mapping_.push_back(other.mapping_[i] + shift_amount); | 
| +  annotation_.AppendVector(other.annotation_); | 
| +} | 
| + | 
| +void NGOffsetMappingBuilder::Composite(const NGOffsetMappingBuilder& other) { | 
| +  DCHECK(!mapping_.IsEmpty()); | 
| +  DCHECK_EQ(mapping_.back() + 1, other.mapping_.size()); | 
| +  for (unsigned i = 0; i < mapping_.size(); ++i) | 
| +    mapping_[i] = other.mapping_[mapping_[i]]; | 
| +} | 
| + | 
| +NGOffsetMappingResult NGOffsetMappingBuilder::Build() const { | 
| +  NGOffsetMappingResult result; | 
| + | 
| +  const LayoutText* current_node = nullptr; | 
| +  unsigned inline_start = 0; | 
| +  unsigned unit_range_start = 0; | 
| +  for (unsigned start = 0; start + 1 < mapping_.size();) { | 
| +    if (annotation_[start] != current_node) { | 
| +      if (current_node) { | 
| +        result.ranges.insert(current_node, std::make_pair(unit_range_start, | 
| +                                                          result.units.size())); | 
| +      } | 
| +      current_node = annotation_[start]; | 
| +      inline_start = start; | 
| +      unit_range_start = result.units.size(); | 
| +    } | 
| + | 
| +    if (!annotation_[start]) { | 
| +      // Only extra characters are not annotated. | 
| +      DCHECK_EQ(mapping_[start] + 1, mapping_[start + 1]); | 
| +      ++start; | 
| +      continue; | 
| +    } | 
| + | 
| +    NGOffsetMappingUnit unit; | 
| +    unsigned end; | 
| +    std::tie(unit.type, end) = | 
| +        GetMappingUnitTypeAndEnd(mapping_, annotation_, start); | 
| +    unit.owner = current_node; | 
| +    unit.dom_start = start - inline_start + current_node->TextStartOffset(); | 
| +    unit.dom_end = end - inline_start + current_node->TextStartOffset(); | 
| +    unit.text_content_start = mapping_[start]; | 
| +    unit.text_content_end = mapping_[end]; | 
| +    result.units.push_back(unit); | 
| + | 
| +    start = end; | 
| +  } | 
| +  if (current_node) { | 
| +    result.ranges.insert(current_node, | 
| +                         std::make_pair(unit_range_start, result.units.size())); | 
| +  } | 
| +  return result; | 
| +} | 
| + | 
| Vector<unsigned> NGOffsetMappingBuilder::DumpOffsetMappingForTesting() const { | 
| return mapping_; | 
| } | 
|  | 
| +Vector<const LayoutText*> NGOffsetMappingBuilder::DumpAnnotationForTesting() | 
| +    const { | 
| +  return annotation_; | 
| +} | 
| + | 
| }  // namespace blink | 
|  |