libextractor

pdf_extractor.cc (28935B)

---

 /*
      This file is part of libextractor.
      Copyright (C) 2002, 2003, 2009, 2026 Vidyut Samanta and Christian Grothoff
 
      libextractor is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
      by the Free Software Foundation; either version 3, or (at your
      option) any later version.
 
      libextractor is distributed in the hope that it will be useful, but
      WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      General Public License for more details.
 
      You should have received a copy of the GNU General Public License
      along with libextractor; see the file COPYING.  If not, write to the
      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
      Boston, MA 02110-1301, USA.
  */
 /**
  * @file plugins/pdf_extractor.cc
  * @brief plugin to support PDF files
  * @author Vidyut Samanta
  * @author Christian Grothoff
  */
 #include "platform.h"
 #include "extractor.h"
 #include "pagelayout.h"
 #include <poppler/cpp/poppler-document.h>
 #include <poppler/cpp/poppler-global.h>
 #include <poppler/cpp/poppler-page.h>
 #include <algorithm>
 #include <cmath>
 #include <ctime>
 #include <string>
 #include <utility>
 #include <vector>
 
 
 /**
  * Sanity bound on the size of a PDF we are willing to buffer
  * in memory (1 GB).  libpoppler needs the whole document, and
  * its raw-data loader takes an `int` length.
  */
 #define MAX_PDF_SIZE (1024LL * 1024LL * 1024LL)
 
 
 /**
  * Entry in the mapping from poppler accessors to LE types.
  */
 struct Matches
 {
   /**
    * Accessor on the poppler document returning the value.
    */
   poppler::ustring (poppler::document::*get) () const;
 
   /**
    * Corresponding meta data type in LE.
    */
   enum EXTRACTOR_MetaType type;
 };
 
 
 /**
  * Map from poppler document info accessors to LE types.
  *
  * Note that we deliberately map "Creator" to
  * #EXTRACTOR_METATYPE_CREATED_BY_SOFTWARE: we believe that
  * Adobe's "Creator" is not a person nor an organisation, but
  * just a piece of software.
  */
 static const struct Matches tmap[] = {
   { &poppler::document::get_title,    EXTRACTOR_METATYPE_TITLE },
   { &poppler::document::get_subject,  EXTRACTOR_METATYPE_SUBJECT },
   { &poppler::document::get_keywords, EXTRACTOR_METATYPE_KEYWORDS },
   { &poppler::document::get_author,   EXTRACTOR_METATYPE_AUTHOR_NAME },
   { &poppler::document::get_creator,  EXTRACTOR_METATYPE_CREATED_BY_SOFTWARE },
   { &poppler::document::get_producer, EXTRACTOR_METATYPE_PRODUCED_BY_SOFTWARE },
   { NULL, EXTRACTOR_METATYPE_RESERVED }
 };
 
 
 /**
  * Silence libpoppler: we do not want parsing diagnostics on
  * stderr of the plugin child process.
  *
  * @param msg the message (ignored)
  * @param cls closure (ignored)
  */
 static void
 quiet_error (const std::string &msg,
              void *cls)
 {
   (void) msg;
   (void) cls;
 }
 
 
 /**
  * Hand a UTF-8 string to the meta data processor, after
  * stripping trailing whitespace.  Empty values are skipped.
  *
  * @param ec extraction context
  * @param type meta data type to use
  * @param val UTF-8 bytes (need not be 0-terminated)
  * @return 0 to continue extracting, 1 if @a ec asked us to stop
  */
 static int
 add_utf8 (struct EXTRACTOR_ExtractContext *ec,
           enum EXTRACTOR_MetaType type,
           std::vector<char> val)
 {
   size_t len = val.size ();
 
   /*
    * Avoid outputting trailing whitespace.  Note that ISO-8859
    * NBSP (0xA0) becomes 0xC2 0xA0 in UTF-8 and is intentionally
    * not stripped here.
    */
   while ((0 < len) &&
          ((' ' == val[len - 1]) ||
           ('\r' == val[len - 1]) ||
           ('\n' == val[len - 1]) ||
           ('\t' == val[len - 1]) ||
           ('\v' == val[len - 1]) ||
           ('\f' == val[len - 1])))
     len--;
   if (0 == len)
     return 0;
   std::string s (val.data (), len);
   if (0 != ec->proc (ec->cls,
                      "pdf",
                      type,
                      EXTRACTOR_METAFORMAT_UTF8,
                      "text/plain",
                      s.c_str (),
                      s.size () + 1))
     return 1;
   return 0;
 }
 
 
 /**
  * Hand a 0-terminated C string to the meta data processor.
  *
  * @param ec extraction context
  * @param type meta data type to use
  * @param s the string
  * @return 0 to continue extracting, 1 if @a ec asked us to stop
  */
 static int
 add_str (struct EXTRACTOR_ExtractContext *ec,
          enum EXTRACTOR_MetaType type,
          const char *s)
 {
   if ((NULL == s) || ('\0' == s[0]))
     return 0;
   if (0 != ec->proc (ec->cls,
                      "pdf",
                      type,
                      EXTRACTOR_METAFORMAT_UTF8,
                      "text/plain",
                      s,
                      strlen (s) + 1))
     return 1;
   return 0;
 }
 
 
 /**
  * Report a date (given as a `time_t`) in ISO-8601 / UTC.
  *
  * @param ec extraction context
  * @param type meta data type to use
  * @param t the time, `(time_t) -1` or 0 if absent
  * @return 0 to continue extracting, 1 if @a ec asked us to stop
  */
 static int
 add_date (struct EXTRACTOR_ExtractContext *ec,
           enum EXTRACTOR_MetaType type,
           time_t t)
 {
   char buf[32];
   struct tm tv;
 
   if (((time_t) -1 == t) || (0 == t))
     return 0;
   if (NULL == gmtime_r (&t, &tv))
     return 0;
   if (0 == strftime (buf, sizeof (buf), "%Y-%m-%d %H:%M:%S", &tv))
     return 0;
   return add_str (ec, type, buf);
 }
 
 
 /**
  * Read the entire input into @a buf.
  *
  * @param ec extraction context
  * @param[out] buf buffer to fill with the file contents
  * @return 0 on success, -1 on error
  */
 static int
 read_all (struct EXTRACTOR_ExtractContext *ec,
           std::vector<char> &buf)
 {
   uint64_t size;
 
   size = ec->get_size (ec->cls);
   if ((UINT64_MAX == size) ||
       (0 == size) ||
       (size > MAX_PDF_SIZE))
     return -1;
   if (0 != ec->seek (ec->cls, 0, SEEK_SET))
     return -1;
   buf.reserve ((size_t) size);
   while (buf.size () < size)
   {
     void *data;
     ssize_t got;
 
     got = ec->read (ec->cls,
                     &data,
                     (size_t) (size - buf.size ()));
     if ((got <= 0) || (NULL == data))
       break;
     buf.insert (buf.end (),
                 static_cast<char *> (data),
                 static_cast<char *> (data) + got);
   }
   if (buf.empty ())
     return -1;
   return 0;
 }
 
 
 /* ****************** full text extraction ********************** */
 
 /**
  * Maximum number of pages we extract text from.
  */
 #define PDF_FT_MAX_PAGES 5000
 
 /**
  * Maximum number of text boxes (words) we look at per page.
  */
 #define PDF_FT_MAX_WORDS 100000
 
 /**
  * Maximum number of lines we collect over the whole document.
  */
 #define PDF_FT_MAX_LINES 500000
 
 /**
  * Wall-clock budget for the full text extraction, in seconds.
  */
 #define PDF_FT_DEADLINE 60
 
 /**
  * Relative height of the top and bottom margin bands in which lines
  * separated from the body are treated as page furniture that never
  * splits into columns.
  */
 #define PDF_FT_BAND 0.12
 
 
 /**
  * A word (poppler text box) on a page.
  */
 struct Word
 {
   /**
    * Bounding box, in points, origin top left.
    */
   double x0;
   double y0;
   double x1;
   double y1;
 
   /**
    * UTF-8 text.
    */
   std::string text;
 
   /**
    * 1 if the word is followed by a space.
    */
   bool space_after;
 
   /**
    * 1 if the word consists of digits only.
    */
   bool numeric;
 };
 
 
 /**
  * A line of words (in reading order once built).
  */
 struct Line
 {
   /**
    * Indices into the word array, sorted left to right.
    */
   std::vector<size_t> words;
 
   /**
    * Vertical extent of the line's first word (for grouping).
    */
   double core_y0;
   double core_y1;
 
   /**
    * Baseline (median bottom of the words).
    */
   double base;
 
   /**
    * Horizontal extent.
    */
   double x0;
   double x1;
 
   /**
    * Median word height.
    */
   double size;
 };
 
 
 /**
  * Median of a vector of doubles.
  *
  * @param v values (reordered), not empty
  * @return the median
  */
 static double
 median (std::vector<double> &v)
 {
   size_t mid = v.size () / 2;
 
   std::nth_element (v.begin (),
                     v.begin () + mid,
                     v.end ());
   return v[mid];
 }
 
 
 /**
  * Current monotonic time in seconds.
  *
  * @return seconds
  */
 static double
 now_s ()
 {
   struct timespec ts;
 
   if (0 != clock_gettime (CLOCK_MONOTONIC, &ts))
     return 0;
   return (double) ts.tv_sec + ts.tv_nsec / 1e9;
 }
 
 
 /**
  * Append the text of @a w to @a out, expanding the Latin ligature
  * characters U+FB00..U+FB06.
  *
  * @param out string to append to
  * @param w text to append
  */
 static void
 append_expanded (std::string &out,
                  const std::string &w)
 {
   static const char *const ligs[] = {
     "ff", "fi", "fl", "ffi", "ffl", "st", "st"
   };
   size_t i = 0;
 
   while (i < w.size ())
   {
     if ( (i + 2 < w.size ()) &&
          ((unsigned char) w[i] == 0xEF) &&
          ((unsigned char) w[i + 1] == 0xAC) &&
          ((unsigned char) w[i + 2] <= 0x86) &&
          ((unsigned char) w[i + 2] >= 0x80) )
     {
       out += ligs[(unsigned char) w[i + 2] - 0x80];
       i += 3;
       continue;
     }
     out += w[i];
     i++;
   }
 }
 
 
 /**
  * Replace a Latin letter followed by a combining accent by the
  * precomposed character (poppler reports TeX's accents that way).
  *
  * @param s UTF-8 text, modified in place
  */
 static void
 compose_accents (std::string &s)
 {
   std::string out;
   size_t i = 0;
 
   out.reserve (s.size ());
   while (i < s.size ())
   {
     unsigned char c = (unsigned char) s[i];
     uint32_t base = 0;
     size_t blen = 0;
 
     if ( (c < 0x80) &&
          isalpha (c) )
     {
       base = c;
       blen = 1;
     }
     else if ( (0xC4 == c) &&
               (i + 1 < s.size ()) &&
               (0xB1 == (unsigned char) s[i + 1]) )
     {
       base = 0x131;
       blen = 2;
     }
     if ( (0 != base) &&
          (i + blen + 1 < s.size ()) )
     {
       unsigned char m0 = (unsigned char) s[i + blen];
       unsigned char m1 = (unsigned char) s[i + blen + 1];
 
       if ( ( (0xCC == m0) || (0xCD == m0) ) &&
            ( (m1 & 0xC0) == 0x80) )
       {
         uint32_t mark = ((uint32_t) (m0 & 0x1F) << 6) | (m1 & 0x3F);
         uint32_t comp = EXTRACTOR_pagelayout_compose_ (base,
                                                        mark);
 
         if (0 != comp)
         {
           /* all precomposed results are below U+0800 */
           out += (char) (0xC0 | (comp >> 6));
           out += (char) (0x80 | (comp & 0x3F));
           i += blen + 2;
           continue;
         }
       }
     }
     out += s[i];
     i++;
   }
   s.swap (out);
 }
 
 
 /**
  * Drop columns of line numbers (or similar pure numbers) in the left
  * and right page margins, i.e. numbers that are outside of all other
  * text on the page and aligned with each other.
  *
  * @param words words of the page, filtered in place
  */
 static void
 drop_marginal_numbers (std::vector<Word> &words)
 {
   double tmin = HUGE_VAL;
   double tmax = -HUGE_VAL;
   std::vector<double> hs;
   double h;
 
   for (const Word &w : words)
     if (! w.numeric)
     {
       tmin = std::min (tmin, w.x0);
       tmax = std::max (tmax, w.x1);
       hs.push_back (w.y1 - w.y0);
     }
   if (hs.empty ())
     return;
   h = median (hs);
   for (int side = 0; side < 2; side++)
   {
     std::vector<size_t> cand;
     double lo = HUGE_VAL;
     double hi = -HUGE_VAL;
 
     for (size_t i = 0; i < words.size (); i++)
     {
       const Word &w = words[i];
 
       if (! w.numeric)
         continue;
       if ( (0 == side) &&
            (w.x1 < tmin - 0.3 * h) )
       {
         cand.push_back (i);
         lo = std::min (lo, w.x1);
         hi = std::max (hi, w.x1);
       }
       if ( (1 == side) &&
            (w.x0 > tmax + 0.3 * h) )
       {
         cand.push_back (i);
         lo = std::min (lo, w.x0);
         hi = std::max (hi, w.x0);
       }
     }
     if ( (cand.size () < 5) ||
          (hi - lo > 4 * h) )
       continue;
     for (size_t i : cand)
       words[i].text.clear ();
   }
   words.erase (std::remove_if (words.begin (),
                                words.end (),
                                [] (const Word &w) {
     return w.text.empty ();
   }),
                words.end ());
 }
 
 
 /**
  * Group the words of a page into lines by their vertical position.
  *
  * @param words words of the page
  * @param[out] lines resulting lines, sorted top to bottom, each with
  *             its words sorted left to right
  */
 static void
 group_lines (const std::vector<Word> &words,
              std::vector<Line> &lines)
 {
   std::vector<size_t> order (words.size ());
 
   for (size_t i = 0; i < words.size (); i++)
     order[i] = i;
   std::sort (order.begin (),
              order.end (),
              [&words] (size_t a, size_t b) {
     double ca = words[a].y0 + words[a].y1;
     double cb = words[b].y0 + words[b].y1;
 
     if (ca != cb)
       return ca < cb;
     return words[a].x0 < words[b].x0;
   });
   for (size_t i : order)
   {
     const Word &w = words[i];
     double wh = w.y1 - w.y0;
     bool placed = false;
 
     /* check the last two lines (a superscript may have opened one) */
     for (size_t k = 0; (k < 2) && (k < lines.size ()); k++)
     {
       Line &l = lines[lines.size () - 1 - k];
       double lh = l.core_y1 - l.core_y0;
       double ov = std::min (w.y1, l.core_y1) - std::max (w.y0, l.core_y0);
 
       if (ov >= 0.5 * std::min (wh, lh))
       {
         l.words.push_back (i);
         placed = true;
         break;
       }
     }
     if (placed)
       continue;
     lines.emplace_back ();
     lines.back ().words.push_back (i);
     lines.back ().core_y0 = w.y0;
     lines.back ().core_y1 = w.y1;
   }
   for (Line &l : lines)
   {
     std::vector<double> bases;
     std::vector<double> hs;
 
     std::sort (l.words.begin (),
                l.words.end (),
                [&words] (size_t a, size_t b) {
       return words[a].x0 < words[b].x0;
     });
     l.x0 = HUGE_VAL;
     l.x1 = -HUGE_VAL;
     for (size_t i : l.words)
     {
       bases.push_back (words[i].y1);
       hs.push_back (words[i].y1 - words[i].y0);
       l.x0 = std::min (l.x0, words[i].x0);
       l.x1 = std::max (l.x1, words[i].x1);
     }
     l.base = median (bases);
     l.size = median (hs);
   }
   std::stable_sort (lines.begin (),
                     lines.end (),
                     [] (const Line &a, const Line &b) {
     return a.base < b.base;
   });
 }
 
 
 /**
  * Compute the horizontal coverage of a line: its words, with gaps of
  * less than half the line height closed.
  *
  * @param words words of the page
  * @param l the line
  * @param[out] iv resulting intervals, left to right
  */
 static void
 line_coverage (const std::vector<Word> &words,
                const Line &l,
                std::vector<std::pair<double, double> > &iv)
 {
   iv.clear ();
   for (size_t i : l.words)
   {
     const Word &w = words[i];
 
     if ( (! iv.empty ()) &&
          (w.x0 - iv.back ().second < 0.5 * l.size) )
       iv.back ().second = std::max (iv.back ().second, w.x1);
     else
       iv.push_back (std::make_pair (w.x0, w.x1));
   }
 }
 
 
 /**
  * Look for a vertical gutter separating two text columns.
  *
  * @param words words of the page
  * @param lines lines of the page
  * @param furniture which lines are page furniture (ignored)
  * @param[out] g0 left end of the gutter
  * @param[out] g1 right end of the gutter
  * @return true if a gutter was found
  */
 static bool
 find_gutter (const std::vector<Word> &words,
              const std::vector<Line> &lines,
              const std::vector<bool> &furniture,
              double &g0,
              double &g1)
 {
   double left = HUGE_VAL;
   double right = -HUGE_VAL;
   std::vector<double> sizes;
   std::vector<std::pair<double, double> > iv;
   size_t nbins;
   size_t body = 0;
   double bw;
   double sz;
 
   for (size_t i = 0; i < lines.size (); i++)
   {
     if (furniture[i])
       continue;
     left = std::min (left, lines[i].x0);
     right = std::max (right, lines[i].x1);
     sizes.push_back (lines[i].size);
     body++;
   }
   if (body < 6)
     return false;
   sz = median (sizes);
   if ( (! (right - left > 10 * sz)) ||
        (! (sz > 0)) )
     return false;
   nbins = 1000;
   bw = (right - left) / nbins;
   std::vector<long> cnt (nbins + 1, 0);
 
   /* difference array: +1 where an interval starts, -1 after its end */
   for (size_t i = 0; i < lines.size (); i++)
   {
     if (furniture[i])
       continue;
     line_coverage (words, lines[i], iv);
     for (const auto &p : iv)
     {
       double f0 = std::max (0.0, (p.first - left) / bw);
       double f1 = std::max (0.0, (p.second - left) / bw);
       size_t b0 = (size_t) std::min (f0, (double) nbins);
       size_t b1 = (size_t) std::min (f1 + 1, (double) nbins);
 
       cnt[b0]++;
       cnt[b1]--;
     }
   }
   for (size_t b = 1; b < nbins; b++)
     cnt[b] += cnt[b - 1];
   /* widest run of rarely covered bins in the middle half */
   long thr = (long) (body / 5);
   size_t best_s = 0;
   size_t best_len = 0;
   size_t run_s = 0;
   size_t run_len = 0;
 
   for (size_t b = nbins / 4; b < 3 * nbins / 4; b++)
   {
     if (cnt[b] <= thr)
     {
       if (0 == run_len)
         run_s = b;
       run_len++;
       if (run_len > best_len)
       {
         best_len = run_len;
         best_s = run_s;
       }
     }
     else
     {
       run_len = 0;
     }
   }
   if ( (0 == best_len) ||
        (best_len * bw < std::max (4.0, 0.3 * sz)) )
     return false;
   g0 = left + best_s * bw;
   g1 = left + (best_s + best_len) * bw;
   /* both sides must hold a good share of the text */
   size_t nl = 0;
   size_t nr = 0;
 
   for (size_t i = 0; i < lines.size (); i++)
   {
     bool l = false;
     bool r = false;
 
     if (furniture[i])
       continue;
     for (size_t w : lines[i].words)
     {
       if (words[w].x1 <= g0 + bw)
         l = true;
       if (words[w].x0 >= g1 - bw)
         r = true;
     }
     if (l)
       nl++;
     if (r)
       nr++;
   }
   return (10 * nl >= 3 * body) && (10 * nr >= 3 * body);
 }
 
 
 /**
  * Build the text of a line from its words and add it to @a page.
  *
  * @param words words of the page
  * @param widx indices of the words of the line, left to right
  * @param page_top top of the page
  * @param page_h height of the page
  * @param page page to add to
  * @param geom geometry array of @a page to append to
  * @param total_bytes running total of text bytes, updated
  * @return 0 on success, -1 to stop (limit reached or no memory)
  */
 static int
 emit_line (const std::vector<Word> &words,
            const std::vector<size_t> &widx,
            double page_top,
            double page_h,
            struct EXTRACTOR_FullTextPage *page,
            std::vector<struct EXTRACTOR_PageLineGeom> &geom,
            size_t &total_bytes)
 {
   std::string text;
   std::vector<double> bases;
   std::vector<double> hs;
   struct EXTRACTOR_PageLineGeom g;
   double y;
 
   if (widx.empty ())
     return 0;
   g.x0 = HUGE_VAL;
   g.x1 = -HUGE_VAL;
   for (size_t k = 0; k < widx.size (); k++)
   {
     const Word &w = words[widx[k]];
 
     bases.push_back (w.y1);
     hs.push_back (w.y1 - w.y0);
     g.x0 = std::min (g.x0, w.x0);
     g.x1 = std::max (g.x1, w.x1);
   }
   g.y = median (bases);
   g.size = median (hs);
   for (size_t k = 0; k < widx.size (); k++)
   {
     const Word &w = words[widx[k]];
 
     if (k > 0)
     {
       const Word &p = words[widx[k - 1]];
 
       if ( (p.space_after) ||
            (w.x0 - p.x1 > 0.15 * g.size) )
         text += ' ';
     }
     append_expanded (text, w.text);
   }
   compose_accents (text);
   if (text.empty ())
     return 0;
   if (total_bytes + text.size () >= EXTRACTOR_FULLTEXT_MAX)
     return -1;
   y = (g.y - page_top) / page_h;
   if (! (y >= 0))
     y = 0;
   if (y > 1)
     y = 1;
   if (0 != EXTRACTOR_fulltext_page_add_ (page,
                                          text.data (),
                                          text.size (),
                                          y,
                                          0))
     return -1;
   geom.push_back (g);
   total_bytes += text.size ();
   return 0;
 }
 
 
 /**
  * Collect the lines of page @a pg in reading order.
  *
  * @param pg the page
  * @param page page to fill
  * @param geom geometry of the lines to fill
  * @param total_bytes running total of text bytes, updated
  * @return 0 on success, -1 to stop
  */
 static int
 collect_page (poppler::page *pg,
               struct EXTRACTOR_FullTextPage *page,
               std::vector<struct EXTRACTOR_PageLineGeom> &geom,
               size_t &total_bytes)
 {
   poppler::rectf rect = pg->page_rect ();
   double top = rect.top ();
   double ph = rect.height ();
   std::vector<poppler::text_box> boxes;
   std::vector<Word> words;
   std::vector<Line> lines;
 
   if ( (! (ph > 0)) ||
        (! std::isfinite (ph)) ||
        (! std::isfinite (top)) )
     return 0;
   boxes = pg->text_list ();
   for (const poppler::text_box &b : boxes)
   {
     poppler::rectf r = b.bbox ();
     std::vector<char> u = b.text ().to_utf8 ();
     Word w;
 
     if (words.size () >= PDF_FT_MAX_WORDS)
       break;
     if ( (0 != b.rotation ()) ||
          (u.empty ()) )
       continue;
     w.x0 = r.left ();
     w.x1 = r.right ();
     w.y0 = r.top ();
     w.y1 = r.bottom ();
     if ( (! std::isfinite (w.x0)) ||
          (! std::isfinite (w.x1)) ||
          (! std::isfinite (w.y0)) ||
          (! std::isfinite (w.y1)) ||
          (! (w.y1 > w.y0)) ||
          (w.x1 < w.x0) ||
          (w.y1 - w.y0 > ph) )
       continue;
     w.text.assign (u.data (), u.size ());
     w.space_after = b.has_space_after ();
     w.numeric = (w.text.size () <= 4);
     for (char c : w.text)
       if (! isdigit ((unsigned char) c))
         w.numeric = false;
     words.push_back (std::move (w));
   }
   boxes.clear ();
   if (words.empty ())
     return 0;
   drop_marginal_numbers (words);
   group_lines (words, lines);
   if (lines.empty ())
     return 0;
 
   /* page furniture: lines in the top/bottom band set apart from
      the rest by a clear vertical gap */
   std::vector<bool> furniture (lines.size (), false);
   {
     std::vector<double> gaps;
     double spacing;
 
     for (size_t i = 1; i < lines.size (); i++)
     {
       double d = lines[i].base - lines[i - 1].base;
 
       if ( (d > 0.3 * lines[i].size) &&
            (d < 3 * lines[i].size) )
         gaps.push_back (d);
     }
     spacing = gaps.empty () ? 0 : median (gaps);
     for (size_t i = 0; i + 1 < lines.size (); i++)
     {
       if ( (lines[i].base - top) / ph > PDF_FT_BAND)
         break;
       if (lines[i + 1].base - lines[i].base <= 1.3 * spacing)
         break;
       furniture[i] = true;
     }
     for (size_t i = lines.size () - 1; i > 0; i--)
     {
       if ( (lines[i].base - top) / ph < 1.0 - PDF_FT_BAND)
         break;
       if (lines[i].base - lines[i - 1].base <= 1.3 * spacing)
         break;
       furniture[i] = true;
     }
   }
 
   double g0 = 0;
   double g1 = 0;
   bool cols = find_gutter (words, lines, furniture, g0, g1);
   std::vector<std::vector<size_t> > left_col;
   std::vector<std::vector<size_t> > right_col;
   std::vector<std::pair<double, double> > iv;
 
   for (size_t i = 0; i <= lines.size (); i++)
   {
     bool spanning = true;
 
     if ( (i < lines.size ()) &&
          cols &&
          (! furniture[i]) )
     {
       line_coverage (words, lines[i], iv);
       spanning = false;
       for (const auto &p : iv)
         if ( (p.first < g1) &&
              (p.second > g0) )
           spanning = true;
     }
     if (spanning)
     {
       /* flush the column region above */
       for (const auto &l : left_col)
         if (0 != emit_line (words, l, top, ph, page, geom, total_bytes))
           return -1;
       for (const auto &l : right_col)
         if (0 != emit_line (words, l, top, ph, page, geom, total_bytes))
           return -1;
       left_col.clear ();
       right_col.clear ();
       if (i == lines.size ())
         break;
       if (0 != emit_line (words, lines[i].words, top, ph, page, geom,
                           total_bytes))
         return -1;
       continue;
     }
     std::vector<size_t> l;
     std::vector<size_t> r;
 
     for (size_t w : lines[i].words)
     {
       if (words[w].x1 <= g1)
         l.push_back (w);
       else
         r.push_back (w);
     }
     if (! l.empty ())
       left_col.push_back (std::move (l));
     if (! r.empty ())
       right_col.push_back (std::move (r));
   }
   return 0;
 }
 
 
 /**
  * Extract the full text of @a doc and emit it.
  *
  * @param ec extraction context
  * @param doc the document
  * @return 0 to continue, 1 if the callback asked us to stop
  */
 static int
 pdf_fulltext (struct EXTRACTOR_ExtractContext *ec,
               poppler::document *doc)
 {
   std::vector<struct EXTRACTOR_FullTextPage> pages;
   std::vector<std::vector<struct EXTRACTOR_PageLineGeom> > geoms;
   std::vector<struct EXTRACTOR_PageLineGeom *> gptrs;
   size_t total_bytes = 0;
   size_t total_lines = 0;
   double deadline = now_s () + PDF_FT_DEADLINE;
   int npages = doc->pages ();
   int ret = 0;
 
   if (npages > PDF_FT_MAX_PAGES)
     npages = PDF_FT_MAX_PAGES;
   try
   {
     pages.reserve (npages);
     geoms.reserve (npages);
     for (int i = 0; i < npages; i++)
     {
       poppler::page *pg;
       struct EXTRACTOR_FullTextPage fp;
       int r;
 
       if (now_s () > deadline)
         break;
       /* keep the host from presuming us hung */
       ec->seek (ec->cls, 0, SEEK_CUR);
       pg = doc->create_page (i);
       if (NULL == pg)
         continue;
       memset (&fp, 0, sizeof (fp));
       pages.push_back (fp);
       geoms.emplace_back ();
       r = collect_page (pg,
                         &pages.back (),
                         geoms.back (),
                         total_bytes);
       delete pg;
       total_lines += pages.back ().num_lines;
       if ( (0 != r) ||
            (total_lines > PDF_FT_MAX_LINES) )
         break;
     }
   }
   catch (...)
   {
     /* out of memory: go with what we have */
   }
   /* we may have failed half-way; keep geometry and lines in sync */
   while (pages.size () > geoms.size ())
   {
     EXTRACTOR_fulltext_page_clear_ (&pages.back ());
     pages.pop_back ();
   }
   for (size_t i = 0; i < pages.size (); i++)
     while (pages[i].num_lines > geoms[i].size ())
     {
       pages[i].num_lines--;
       free (pages[i].lines[pages[i].num_lines].text);
     }
   if (! pages.empty ())
   {
     struct EXTRACTOR_FullText ft;
 
     for (size_t i = 0; i < geoms.size (); i++)
       gptrs.push_back (geoms[i].data ());
     EXTRACTOR_fulltext_filter_margins_ (pages.data (),
                                         (unsigned int) pages.size ());
     EXTRACTOR_pagelayout_paragraphs_ (pages.data (),
                                       gptrs.data (),
                                       (unsigned int) pages.size (),
                                       0.02);
     EXTRACTOR_fulltext_init_ (&ft);
     EXTRACTOR_fulltext_append_pages_ (&ft,
                                       pages.data (),
                                       (unsigned int) pages.size ());
     ret = EXTRACTOR_fulltext_emit_ (&ft,
                                     ec,
                                     "pdf");
     EXTRACTOR_fulltext_clear_ (&ft);
   }
   for (size_t i = 0; i < pages.size (); i++)
     EXTRACTOR_fulltext_page_clear_ (&pages[i]);
   return (0 != ret) ? 1 : 0;
 }
 
 
 /**
  * Main entry method for the PDF extraction plugin.
  *
  * @param ec extraction context provided to the plugin
  */
 extern "C" void
 EXTRACTOR_pdf_extract_method (struct EXTRACTOR_ExtractContext *ec)
 {
   void *hdr;
   std::vector<char> buf;
   poppler::document *doc;
   int major;
   int minor;
   char ver[32];
   char pages[16];
 
   if (4 != ec->read (ec->cls, &hdr, 4))
     return;
   if (0 != memcmp ("%PDF", hdr, 4))
     return;
   if (0 != read_all (ec, buf))
     return;
 
   poppler::set_debug_error_function (&quiet_error, NULL);
   doc = poppler::document::load_from_raw_data (buf.data (),
                                                (int) buf.size ());
   if (NULL == doc)
     return;
   /* An encrypted document we cannot open exposes no usable meta data. */
   if (doc->is_locked ())
   {
     delete doc;
     return;
   }
 
   if (0 != add_str (ec,
                     EXTRACTOR_METATYPE_MIMETYPE,
                     "application/pdf"))
     goto CLEANUP;
   for (unsigned int i = 0; NULL != tmap[i].get; i++)
     if (0 != add_utf8 (ec,
                        tmap[i].type,
                        (doc->*tmap[i].get)().to_utf8 ()))
       goto CLEANUP;
   doc->get_pdf_version (&major, &minor);
   snprintf (ver, sizeof (ver), "PDF %d.%d", major, minor);
   if (0 != add_str (ec, EXTRACTOR_METATYPE_FORMAT, ver))
     goto CLEANUP;
   snprintf (pages, sizeof (pages), "%d", doc->pages ());
   if (0 != add_str (ec, EXTRACTOR_METATYPE_PAGE_COUNT, pages))
     goto CLEANUP;
   if (0 != add_date (ec,
                      EXTRACTOR_METATYPE_CREATION_DATE,
                      doc->get_creation_date_t ()))
     goto CLEANUP;
   if (0 != add_date (ec,
                      EXTRACTOR_METATYPE_MODIFICATION_DATE,
                      doc->get_modification_date_t ()))
     goto CLEANUP;
   if (EXTRACTOR_fulltext_requested_ (ec->config))
     (void) pdf_fulltext (ec, doc);
 CLEANUP:
   delete doc;
 }
 
 
 /* end of pdf_extractor.cc */