Improve extraction of accessible text from PDF.

pdf/pdfium/pdfium_page.cc

Index: pdf/pdfium/pdfium_page.cc
diff --git a/pdf/pdfium/pdfium_page.cc b/pdf/pdfium/pdfium_page.cc
index 95a8fba3d7100a3f7dd658ba26ac54cf8645415c..5f43c83278b3c244e32f9711683a7d5cc62b4d3d 100644
--- a/pdf/pdfium/pdfium_page.cc
+++ b/pdf/pdfium/pdfium_page.cc
@@ -32,10 +32,72 @@ const char kTextBoxFontSize[] = "fontSize";
 const char kTextBoxNodes[] = "textNodes";
 const char kTextNodeType[] = "type";
 const char kTextNodeText[] = "text";
-const char kTextNodeURL[] = "url";
 const char kTextNodeTypeText[] = "text";
-const char kTextNodeTypeURL[] = "url";
-const char kDocLinkURLPrefix[] = "#page";
+
+pp::Rect PageRectToGViewRect(FPDF_PAGE page, const pp::Rect& input) {
+  int output_width = FPDF_GetPageWidth(page);
+  int output_height = FPDF_GetPageHeight(page);
+
+  int min_x, min_y;

[Lei Zhang, 2016/01/14 02:45:06]

One var per line please.

[dmazzoni, 2016/01/21 23:10:43]

Done.

+  int max_x, max_y;
+  FPDF_PageToDevice(page, 0, 0, output_width, output_height, 0,
+                    input.x(), input.y(), &min_x, &min_y);
+  FPDF_PageToDevice(page, 0, 0, output_width, output_height, 0,
+                    input.right(), input.bottom(), &max_x, &max_y);
+
+  if (max_x < min_x)

[jbreiden, 2016/01/14 01:07:56]

Hmmm.... this works best for left-to-right languages. See how
jbreiden3.mtv/results/ara.pdf has bad justification? Something like this should
fix it.

int w = abs(max_x - min_x);  // width
int h = abs(max_y - min_y);  // height

if (max_y < min_y)
  std::swap(min_y, max_y);

if (max_x < min_x)
  pp::Rect output_rect(max_x - w, max_y - h, w, h);
else
  pp::Rect output_rect(min_x, min_y, w, h);

But honestly, the world of Arabic and Hebrew is a mess in PDF
there is a lot of variation. So getting this working beautifully
for Google Books does not mean we will do well with arbitrary
Hebrew and Arabic PDF. E.g. I think the suggested code change above will work
nicely and not harm anything, but it is hard to be sure.

Maybe it is best just to leave the code alone add a comment 
mentioning our weakness. Something like:

// This code left justifies text in the bounding box, which 
// makes sense for left-to-right languages such as English.
// This is not correct for a right to left language such as 
// Arabic.
 

[dmazzoni, 2016/01/21 23:10:43]

No, the issue here is that a pp::Rect isn't allowed to be "backwards", i.e. with
a left coordinate that's larger than its right coordinate.

This code is correct no matter what the text direction.

However, in order to correctly *display* the resulting text properly, we need to
extract the text direction and pass that as part of the data structure.

FWIW, I think this will be moot once I switch to implementing accessibility
natively. The way it will work then is that we'll just export the bounds of
every character, and the user will see the full rendered PDF visually with an
accessible bounding box for whatever range they have selected.

+    std::swap(min_x, max_x);
+  if (max_y < min_y)
+    std::swap(min_y, max_y);
+
+  pp::Rect output_rect(min_x, min_y, max_x - min_x, max_y - min_y);
+  output_rect.Intersect(pp::Rect(0, 0, output_width, output_height));
+  return output_rect;
+}
+
+pp::Rect GetCharRectInGViewCoords(FPDF_PAGE page, FPDF_TEXTPAGE text_page,
+                                  int index) {
+  double left, right, bottom, top;
+  FPDFText_GetCharBox(text_page, index, &left, &right, &bottom, &top);
+  if (right < left)

[jbreiden, 2016/01/14 01:07:56]

Same as above.

[dmazzoni, 2016/01/21 23:10:43]

Same answer. We have to swap or it doesn't work.

+    std::swap(left, right);
+  if (bottom < top)
+    std::swap(top, bottom);
+  pp::Rect page_coords(left, top, right - left, bottom - top);
+  return PageRectToGViewRect(page, page_coords);
+}
+
+// This is the character Pfdium inserts where a word is broken across lines.

[Lei Zhang, 2016/01/14 02:45:06]

PDFium

[dmazzoni, 2016/01/21 23:10:43]

Done.

+const unsigned int kSoftHyphen = 0x02;
+
+// The following characters should all be recognized as Unicode newlines:
+//   LF:    Line Feed, U+000A
+//   VT:    Vertical Tab, U+000B
+//   FF:    Form Feed, U+000C
+//   CR:    Carriage Return, U+000D
+//   CR+LF: CR (U+000D) followed by LF (U+000A)
+//   NEL:   Next Line, U+0085
+//   LS:    Line Separator, U+2028
+//   PS:    Paragraph Separator, U+2029.
+// Source: http://en.wikipedia.org/wiki/Newline#Unicode .
+const unsigned int kUnicodeNewlines[] = {
+  0xA, 0xB, 0xC, 0xD, 0X85, 0x2028, 0x2029
+};
+
+bool IsSoftHyphen(unsigned int character) {
+  return kSoftHyphen == character;
+}
+
+bool OverlapsOnYAxis(const pp::Rect &a, const pp::Rect& b) {
+  return !(a.IsEmpty() || b.IsEmpty() ||
+           a.bottom() < b.y() || b.bottom() < a.y());
+}
+
+bool IsEol(unsigned int character) {
+  const unsigned int* first = kUnicodeNewlines;
+  const unsigned int* last = kUnicodeNewlines + arraysize(kUnicodeNewlines);
+  return std::find(first, last, character) != last;
+}
 
 }  // namespace
 
@@ -130,130 +192,97 @@ base::Value* PDFiumPage::GetAccessibleContentAsValue(int rotation) {
   if (!available_)
     return node;
 
-  double width = FPDF_GetPageWidth(GetPage());
-  double height = FPDF_GetPageHeight(GetPage());
+  FPDF_PAGE page = GetPage();
+  FPDF_TEXTPAGE text_page = GetTextPage();
 
-  base::ListValue* text = new base::ListValue();
-  int box_count = FPDFText_CountRects(GetTextPage(), 0, GetCharCount());
-  for (int i = 0; i < box_count; i++) {
-    double left, top, right, bottom;
-    FPDFText_GetRect(GetTextPage(), i, &left, &top, &right, &bottom);
-    text->Append(
-        GetTextBoxAsValue(height, left, top, right, bottom, rotation));
-  }
+  double width = FPDF_GetPageWidth(page);
+  double height = FPDF_GetPageHeight(page);
 
   node->SetDouble(kPageWidth, width);
   node->SetDouble(kPageHeight, height);
-  node->Set(kPageTextBox, text);  // Takes ownership of |text|
-
-  return node;
-}
-
-base::Value* PDFiumPage::GetTextBoxAsValue(double page_height,
-                                           double left, double top,
-                                           double right, double bottom,
-                                           int rotation) {
-  base::string16 text_utf16;
-  int char_count =
-    FPDFText_GetBoundedText(GetTextPage(), left, top, right, bottom, NULL, 0);
-  if (char_count > 0) {
-    unsigned short* data = reinterpret_cast<unsigned short*>(
-        base::WriteInto(&text_utf16, char_count + 1));
-    FPDFText_GetBoundedText(GetTextPage(),
-                            left, top, right, bottom,
-                            data, char_count);
-  }
-  std::string text_utf8 = base::UTF16ToUTF8(text_utf16);
-
-  FPDF_LINK link = FPDFLink_GetLinkAtPoint(GetPage(), left, top);
-  Area area;
-  std::vector<LinkTarget> targets;
-  if (link) {
-    targets.push_back(LinkTarget());
-    area = GetLinkTarget(link, &targets[0]);
-  } else {
-    pp::Rect rect(
-        PageToScreen(pp::Point(), 1.0, left, top, right, bottom, rotation));
-    GetLinks(rect, &targets);
-    area = targets.empty() ? TEXT_AREA : WEBLINK_AREA;
-  }
+  base::ListValue* text = new base::ListValue();
 
-  int char_index = FPDFText_GetCharIndexAtPos(GetTextPage(), left, top,
-                                              kTolerance, kTolerance);
-  double font_size = FPDFText_GetFontSize(GetTextPage(), char_index);
+  int chars_count = FPDFText_CountChars(text_page);
+  pp::Rect line_rect;
+  pp::Rect word_rect;
+  bool seen_literal_text_in_word = false;
+
+  base::string16 line;
+  for (int i = 0; i <= chars_count; i++) {

[Lei Zhang, 2016/01/14 02:45:06]

This went it i < chars_count in patch set 2 and back to <= in patch set 3. Do we
need to go past the last char or not?

[Lei Zhang, 2016/01/14 02:47:58]

"This went to"

[dmazzoni, 2016/01/21 23:10:43]

This is on purpose. When i == chars_count, we pretend the character is a newline
in order to flush it.

I added a comment so it's clear this isn't a bug.

+    unsigned int character;
+    pp::Rect char_rect;
+
+    if (i < chars_count) {
+      character = FPDFText_GetUnicode(text_page, i);
+      char_rect = GetCharRectInGViewCoords(page, text_page, i);
+    } else {
+      // Make the last character a newline so the last line isn't lost.
+      character = '\n';
+    }
 
-  base::DictionaryValue* node = new base::DictionaryValue();
-  node->SetDouble(kTextBoxLeft, left);
-  node->SetDouble(kTextBoxTop, page_height - top);
-  node->SetDouble(kTextBoxWidth, right - left);
-  node->SetDouble(kTextBoxHeight, top - bottom);
-  node->SetDouble(kTextBoxFontSize, font_size);
-
-  base::ListValue* text_nodes = new base::ListValue();
-
-  if (area == DOCLINK_AREA) {
-    std::string url = kDocLinkURLPrefix + base::IntToString(targets[0].page);
-    text_nodes->Append(CreateURLNode(text_utf8, url));
-  } else if (area == WEBLINK_AREA && link) {
-    text_nodes->Append(CreateURLNode(text_utf8, targets[0].url));
-  } else if (area == WEBLINK_AREA && !link) {
-    size_t start = 0;
-    for (const auto& target : targets) {
-      // If there is an extra NULL character at end, find() will not return any
-      // matches. There should not be any though.
-      if (!target.url.empty())
-        DCHECK_NE(target.url.back(), '\0');
-
-      // PDFium may change the case of generated links.
-      std::string lowerCaseURL = base::ToLowerASCII(target.url);
-      std::string lowerCaseText = base::ToLowerASCII(text_utf8);
-      size_t pos = lowerCaseText.find(lowerCaseURL, start);
-      size_t length = target.url.size();
-      if (pos == std::string::npos) {
-        // Check if the link is a "mailto:" URL
-        if (lowerCaseURL.compare(0, 7, "mailto:") == 0) {
-          pos = lowerCaseText.find(lowerCaseURL.substr(7), start);
-          length -= 7;
-        }
+    // There are spurious STX chars appearing in place
+    // of ligatures.  Apply a heuristic to check that some vertical displacement
+    // is involved before assuming they are line-breaks.
+    bool is_intraword_linebreak = false;
+    if (i < chars_count - 1 && IsSoftHyphen(character)) {
+      // check if the next char and this char are in different lines.
+      pp::Rect next_char_rect = GetCharRectInGViewCoords(
+          page, text_page, i + 1);
+      is_intraword_linebreak = !OverlapsOnYAxis(char_rect, next_char_rect);

[jbreiden, 2016/01/14 01:07:56]

Maybe a comment somewhere in this function mentioning that we are assuming
horizontal text and will do badly with vertical text such as Japanese or
Chinese. 

This is not a regression (old ChromeVox was also a disaster) but we might want
to get this this working some day in the future and a comment may be useful.

[dmazzoni, 2016/01/21 23:10:43]

Added a link to a bug.

+    }
+    if (is_intraword_linebreak ||
+            base::IsUnicodeWhitespace(character) ||

[Lei Zhang, 2016/01/14 02:45:06]

funny indentation

[dmazzoni, 2016/01/21 23:10:43]

Done.

+            IsEol(character)) {
+      if (!word_rect.IsEmpty() && seen_literal_text_in_word) {
+        word_rect = pp::Rect();
+        seen_literal_text_in_word = false;
+      }
+    }
 
-        if (pos == std::string::npos) {
-          // No match has been found.  This should never happen.
-          continue;
+    if (IsEol(character) || is_intraword_linebreak) {

[Lei Zhang, 2016/01/14 02:45:06]

You can also check |is_intraword_linebreak| first here.

[dmazzoni, 2016/01/21 23:10:43]

Done.

+      if (!line_rect.IsEmpty()) {
+        if (is_intraword_linebreak) {
+          // Add a 0-width hyphen.
+          line.push_back('-');
         }
+        base::DictionaryValue* line_node = new base::DictionaryValue();

[Lei Zhang, 2016/01/14 02:45:06]

Can you create/initialize the Values in order? |text_node| -> |text_nodes| ->
|line_node|.

[dmazzoni, 2016/01/21 23:10:43]

Done.

+        line_node->SetDouble(kTextBoxLeft, line_rect.x());
+        line_node->SetDouble(kTextBoxTop, line_rect.y());
+        line_node->SetDouble(kTextBoxWidth, line_rect.width());
+        line_node->SetDouble(kTextBoxHeight, line_rect.height());
+        line_node->SetDouble(kTextBoxFontSize,
+                             FPDFText_GetFontSize(text_page, i));
+
+        base::ListValue* text_nodes = new base::ListValue();
+        base::DictionaryValue* text_node = new base::DictionaryValue();
+        text_node->SetString(kTextNodeType, kTextNodeTypeText);
+        text_node->SetString(kTextNodeText, line);
+        text_nodes->Append(text_node);
+
+        line_node->Set(kTextBoxNodes, text_nodes);
+        text->Append(line_node);
+
+        line.clear();
+        line_rect = pp::Rect();
+        word_rect = pp::Rect();
+        seen_literal_text_in_word = false;
       }
+      continue;
+    }
+    seen_literal_text_in_word = seen_literal_text_in_word ||
+        !base::IsUnicodeWhitespace(character);
+    line.push_back(character);
 
-      std::string before_text = text_utf8.substr(start, pos - start);
-      if (!before_text.empty())
-        text_nodes->Append(CreateTextNode(before_text));
-      std::string link_text = text_utf8.substr(pos, length);
-      text_nodes->Append(CreateURLNode(link_text, target.url));
+    if (!char_rect.IsEmpty()) {
+      line_rect = line_rect.Union(char_rect);
 
-      start = pos + length;
+      if (!base::IsUnicodeWhitespace(character))
+        word_rect = word_rect.Union(char_rect);
     }
-    std::string before_text = text_utf8.substr(start);
-    if (!before_text.empty())
-      text_nodes->Append(CreateTextNode(before_text));
-  } else {
-    text_nodes->Append(CreateTextNode(text_utf8));
   }
 
-  node->Set(kTextBoxNodes, text_nodes);  // Takes ownership of |text_nodes|.
-  return node;
-}
-
-base::Value* PDFiumPage::CreateTextNode(const std::string& text) {
-  base::DictionaryValue* node = new base::DictionaryValue();
-  node->SetString(kTextNodeType, kTextNodeTypeText);
-  node->SetString(kTextNodeText, text);
-  return node;
-}
+  node->Set(kPageTextBox, text);  // Takes ownership of |text|
 
-base::Value* PDFiumPage::CreateURLNode(const std::string& text,
-                                       const std::string& url) {
-  base::DictionaryValue* node = new base::DictionaryValue();
-  node->SetString(kTextNodeType, kTextNodeTypeURL);
-  node->SetString(kTextNodeText, text);
-  node->SetString(kTextNodeURL, url);
   return node;
 }