Improve extraction of accessible text from PDF.

pdf/pdfium/pdfium_page.cc

 // Copyright (c) 2010 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 "pdf/pdfium/pdfium_page.h"
 
 #include <math.h>
 #include <stddef.h>
 
 #include "base/logging.h"
@@ skipping 14 matching lines @@
 const char kPageHeight[] = "height";
 const char kPageTextBox[] = "textBox";
 const char kTextBoxLeft[] = "left";
 const char kTextBoxTop[]  = "top";
 const char kTextBoxWidth[] = "width";
 const char kTextBoxHeight[]  = "height";
 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
 
 namespace chrome_pdf {
 
 PDFiumPage::PDFiumPage(PDFiumEngine* engine,
                        int i,
                        const pp::Rect& r,
                        bool available)
     : engine_(engine),
@@ skipping 74 matching lines @@
   }
   return text_page_;
 }
 
 base::Value* PDFiumPage::GetAccessibleContentAsValue(int rotation) {
   base::DictionaryValue* node = new base::DictionaryValue();
 
   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);
+  base::ListValue* text = new base::ListValue();
+
+  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';
+    }
+
+    // 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 (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);
+
+    if (!char_rect.IsEmpty()) {
+      line_rect = line_rect.Union(char_rect);
+
+      if (!base::IsUnicodeWhitespace(character))
+        word_rect = word_rect.Union(char_rect);
+    }
+  }
+
   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;
-  }
-
-  int char_index = FPDFText_GetCharIndexAtPos(GetTextPage(), left, top,
-                                              kTolerance, kTolerance);
-  double font_size = FPDFText_GetFontSize(GetTextPage(), char_index);
-
-  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;
-        }
-
-        if (pos == std::string::npos) {
-          // No match has been found.  This should never happen.
-          continue;
-        }
-      }
-
-      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));
-
-      start = pos + length;
-    }
-    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;
-}
-
-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;
-}
-
 PDFiumPage::Area PDFiumPage::GetCharIndex(const pp::Point& point,
                                           int rotation,
                                           int* char_index,
                                           int* form_type,
                                           LinkTarget* target) {
   if (!available_)
     return NONSELECTABLE_AREA;
   pp::Point point2 = point - rect_.point();
   double new_x;
   double new_y;
@@ skipping 255 matching lines @@
   page_->loading_count_--;
 }
 
 PDFiumPage::Link::Link() {
 }
 
 PDFiumPage::Link::~Link() {
 }
 
 }  // namespace chrome_pdf