/*
 * Fracture.xs
 * Copyright (c) 2007, 2008, Juergen Weigert, Novell Inc.
 * This module is free software. It may be used, redistributed
 * and/or modified under the same terms as perl itself.
 *
 * see perldoc perlxstut, perlguts, perlapi
 *
 * Linus Torvalds: 
 * "Quite frankly, even if the choice of C were to do *nothing*
 * but keep the C++ programmers out, that in itself would be a 
 * huge reason to use C."
 * (http://thread.gmane.org/gmane.comp.version-control.git/57643/focus=57918)
 */
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include "ppport.h"
static int max_chars = 2000;
static int max_lines = 20;
static int max_cpl = 300;
static int verbose = 0;
struct char_stat
{
  char top_four[4];             // unused.
  unsigned int n_top_four[4];   // unused.
  unsigned int n_wordsx;        // number of words (distinct strings of is_word_ch_x()).
  int n_distinct;       // number of different printable nonwhitespace chars seen.
  int n_nonprint;       // number of chars >= 128, or < 32 but not whitespace.
  int n_whitespace;     // ' ', '\t', '\n', '\r' (only space and tab should appear, though)
  int n_iswordx;        // number of chars with is_word_ch_x()
  int n_other;          // non_word, non_withespace, but printable -> punctuation, etc.
  int wet_indent;       // whitespace indentation, including but not counting 
                        //MAX_INDENT_WETNESS
};
struct line
{
  int offset;           // byte offset of the first char of this line.
  int offset_l;         // line offset from the beginning of the file, beginning with 1
  int end_offset;       // byte offset of the first char of next line.
  int length;           // eff. length, ignoring trailing, includiing indent
  int weight;           // accumulator for fracture weights. Break after this line, if high.
  struct char_stat s;
};
#define MAX_INDENT_WETNESS      2       // two printable nonword chars allowed in indent.
#define WEIGHT_BLANK_LINE       800             // an empty line (applies to current line).
#define WEIGHT_NO_INDENT        400             // no longer indented line start
#define WEIGHT_wW_CHANGE        200             // word-char -> non-word-char transition
#define WEIGHT_INDENT_DIFF      100             // add/subtract max for indent change.
#define WEIGHT_LLEN_DIFF        300             // cut after short lines.
#define WEIGHT_DISTINCT_DIFF    50              // add/subtract max for distinct change.
#define WEIGHT_BALANCE_CHANGE   3               // other/iswordx balance changes
#if 0 //UNUSED
#define WEIGHT_Ww_START         100             // non-word-char start -> word-char start (applies to prev line)
#define WEIGHT_LINE_LENGTH      -1              // per character "cut after short lines" (applies to current line)
#endif
struct char_input
{
  int offset;                   // byte offset of ch in text.
  int next_offset;              // byte offset of next_ch in text.
  int ch, next_ch, last_ch;     // characters read examined from text
  int next_ch_raw;              // identical to next_ch, except '\r' if next_ch is '\n'.
};
#define char_input_init(in)     \
do {                            \
  (in)->ch = '\0';           \
  (in)->last_ch = '\0';              \
  (in)->next_ch = '\n';              \
  (in)->offset = -1;                 \
} while (0)
static int do_fetch(int *offp, const char *text, int len)
{
  while (++(*offp) < len)
    if (text[*offp])
      return text[*offp];
  *offp = len;                  // oops, we walked beyond len.
  return '\n';                  // fake a newline.
}
static int char_input_fetch(struct char_input *in, const char *text, int len)
{
  if (!in->ch)               // initialisation.
    {
      in->ch = do_fetch(&in->offset, text, len);
      in->next_offset = in->offset;
      in->next_ch = do_fetch(&in->next_offset, text, len);
    }
  else
    {
      in->last_ch = in->ch;
      in->ch = in->next_ch_raw;                           // get a '\r' to see "\r\n" correctly.
      in->offset = in->next_offset;
      in->next_ch = do_fetch(&in->next_offset, text, len);
    }
  if ((in->ch == '\n' && in->next_ch == '\r') ||
      (in->ch == '\r' && in->next_ch == '\n'))
    in->next_ch = do_fetch(&in->next_offset, text, len); // handle cr-lf and lf-cr as lf.
  in->next_ch_raw = in->next_ch;
  if (in->ch      == '\v') in->ch      = '\f';            // handle vert-tab as form-feed.
  if (in->ch      == '\r') in->ch      = '\n';            // handles single cr as lf.
  if (in->next_ch == '\r') in->next_ch = '\n';            // handles single cr as lf.
  return in->ch;
}
// private version of \w, we also include "$:."
// This is plain wrong for e.g. /etc/passed, where colon seperates fields.
// but nowadays, we more often see colon as a namespace separator, which 
// should not chop words in pieces. Imagine "Data::Dumper"
//
static int is_word_ch_x(int c)
{
  if ((c <= 'z' && c >= 'a') ||
      (c <= 'Z' && c >= 'A') ||
      (c <= '9' && c >= '0') ||
       c == '_' || c == '$' || 
       c == ':' || c == '.')
    return 1;
  return 0;
}
// returns number of characters excluding trailing whitespace or nonprintables,
// including wet_indent
// fills in the char_stat structure.
static int char_stat(struct char_stat *s, const char *text, int len)
{
  int ch_arr[128-32];
  int i, j, wetness = 0, in_word = 0;
  for (i = 0; i < 128-32; i++) ch_arr[i] = 0;
  while ((len > 0) && (text[len-1] <= ' ')) len--;
  bzero((void *)s, sizeof(struct char_stat));
  s->wet_indent = -1;
  for (i = 0; i < len; i++)
    {
      unsigned char c = (unsigned char)text[i];
      if (c == ' ' || c == '\t' || c == '\0' || c == '\n' || c == '\r') 
        {
          in_word = 0;
          s->n_whitespace++;
        }
      else if (c < 32 || c > 127) 
        {
          in_word = 0;
          if (s->wet_indent < 0) s->wet_indent = i - wetness;
          s->n_nonprint++;
        }
      else
        {
          ch_arr[c-32]++;
          if (is_word_ch_x(c))
            {
              if (s->wet_indent < 0) s->wet_indent = i - wetness;
              s->n_iswordx++;
              if (!in_word) s->n_wordsx++;
              in_word++;
            }
          else
            {
              in_word = 0;
              if ((s->wet_indent < 0) && (++wetness > MAX_INDENT_WETNESS)) 
                s->wet_indent = i - wetness + 1;
              s->n_other++;
            }
        }
    }
  if (s->wet_indent < 0) s->wet_indent = len - wetness;
  for (j = 0; j < 128-32; j++)
    {
      if (ch_arr[j]) s->n_distinct++;
    }
  for (i = 0; i < 4; i++)
    {
      int m = -1;
      int c = -1;
      for (j = 0; j < 128-32; j++)
        {
          if (ch_arr[j] > m)
            {
              m = ch_arr[j];
              c = j+32;
            }
        }
      s->top_four[i] = c;
      s->n_top_four[i] = m;
      ch_arr[c-32] = 0;
    }
  return len;
}
// call once per line.
//
static void weight_line(struct line *l1, struct line *l2, const char *text)
{
  struct char_stat *s1, *s2;
  s1 = &l1->s;
  s2 = &l2->s;
  if (!l1->length)   // triggers only for first element.
    l1->length = char_stat(s1, text+l1->offset, l1->end_offset - l1->offset);
  if (!l2->length)   // triggers always...
    l2->length = char_stat(s2, text+l2->offset, l2->end_offset - l2->offset);
  // now use the stats left and right of the break point to adjust its 
  // weight in l1->weight.
  // break very easy, where an indent disappeared.
  if (s1->wet_indent > 0 && s2->wet_indent == 0) 
    l1->weight += WEIGHT_NO_INDENT;
  // encourage break, where indent decreases, emphasizing small numbers.
  // discourage break, where indent inreases, emphasizing small numbers.
  if (s2->wet_indent > 0) 
    l1->weight += (s1->wet_indent - s2->wet_indent) * WEIGHT_INDENT_DIFF / 
                  (s1->wet_indent + s2->wet_indent);
  // encourage break when coming from more iswordx chars to more other chars.
  if ((s1->n_iswordx > s1->n_other) &&
      (s2->n_iswordx < s2->n_other)) 
    l1->weight += (s1->n_iswordx + s2->n_other - s1->n_other - s2->n_iswordx)
      * WEIGHT_BALANCE_CHANGE;
  // also encourage when coming from less iswordx to more other chars.
  if ((s2->n_iswordx > s2->n_other) &&
      (s1->n_iswordx < s1->n_other)) 
    l1->weight += (s2->n_iswordx + s1->n_other - s2->n_other - s1->n_iswordx)
      * WEIGHT_BALANCE_CHANGE;
  // strongly encourage break when a line had no word chars, but the next has.
  // encourage a bit, where isxwordx increases,
  // discourage a bit, where isxwordx decreases.
  if ((s1->n_iswordx == 0) && s2->n_iswordx > 0) 
    l1->weight += WEIGHT_wW_CHANGE;
  else
    l1->weight += s2->n_iswordx - s1->n_iswordx;
  // encourage where number of distinct chars grows
  // discurage where number of distinct chars gets less
  // ... emphasizing small numbers..
  if (s2->n_distinct > 0)
    l1->weight += (s2->n_distinct - s1->n_distinct) * WEIGHT_DISTINCT_DIFF /
                  (s2->n_distinct + s1->n_distinct);
  // number of words, avg length of words, does that mean anything?
  // l1->weight += s1->n_wordsx   - s2->n_wordsx;      
  // encourage where lines get longer
  // discourage where lines get shorter,
  // emphasizing small numbers.
  if (l2->length > 0)
    l1->weight += (l2->length - l1->length) * WEIGHT_LLEN_DIFF /
                  (l2->length + l1->length);      
  // little hack: 
  // WEIGHT_BLANK_LINE is already there, before weight_line gets called.
  // we use this property in this look-ahead logic:
  if (l2->weight >= WEIGHT_BLANK_LINE)
    {
      // Here we propagate 'something' into the blank lines.
      // without such propagation, all blank lines ar exactly equal (1250)
      // without any variation. This gives the peak detector a hard time to 
      // choose good peaks. bisect_fract() easily degenerates to cut at *every* 
      // 1250 peak, even, if there is only one or two lines of text between them.
      // Adding a small random value to the peaks is sufficient to help peak detector 
      // out of this degenerated mode.
      //
      // Instead of a random value, we use the weight of the line just before the 
      // blank line, because randomness is really bad for re-recognition of breaks.
      // And there is actually no reason to use a *small* value. :-)
      //
      l2->weight += l1->weight;
    }
}
// push_fracture
// adds the range from after the start_idx-line, to and including the 
// end_idx line to the return value r.
//
// use start_idx == -1 to include larr[0] ...
// 
static void push_fracture(AV *r, struct line *larr, int start_idx, int end_idx)
{
  AV *fra;
  int s_e_offset, s_offset_l;
  struct line *e = &larr[end_idx];
         
  if (start_idx < 0)
    {
      s_e_offset = 0;
      s_offset_l = 1;
    }
  else
    {
      s_e_offset = larr[start_idx].end_offset;
      s_offset_l = larr[start_idx].offset_l;
    }
  fra = (AV *)sv_2mortal((SV *)newAV());
  av_push(fra, newSVnv(s_e_offset));                    // offset in bytes
  av_push(fra, newSVnv(e->end_offset - s_e_offset)); // length in bytes
  av_push(fra, newSVnv(s_offset_l));                    // offset in lines
  av_push(fra, newSVnv(e->offset_l - s_offset_l+1)); // length in lines
  av_push(r, newRV((SV *)fra));
}
// is_small_enough() is a predicate, which returns true, if the 
// interval after start_idx, up to including end_idx does not exceeds the
// given max_* limits.
//
// use start_idx == -1 to include larr[0]
//
static int is_small_enough(struct line *larr, int start_idx, int end_idx, int max_lines, int max_chars)
{
  int n_chars = 0;
  struct line *l;
  if ((end_idx - start_idx) < 2) return 1;
  if ((end_idx - start_idx) > max_lines) return 0;
  // count chars after start_idx line, up to including end_idx line.
  for (l = &larr[start_idx+1]; l <= &larr[end_idx]; l++)
    n_chars += l->length;
  if (n_chars > max_chars) return 0;
  return 1;
}
static int find_max_idx(struct line *larr, int i1, int i2)
{
  int m = larr[i1].weight;
  int i = i1;
  int r = i;
  while (++i < i2)
    {
      if (m < larr[i].weight)
        {
          m = larr[i].weight;
          r = i;
        }
    }
  // printf("bisect(%d,%d, idx=%d, thr=%d)\n", i1, i2, r, m);
  return r;
}
// initial call shall be with start_idx == -1 and end_idx = larr_size;
static void bisect_fract(AV *r, struct line *larr, int start_idx, int end_idx, int max_lines, int max_chars)
{
  int bisec_idx;
  int ss, ee;
  if (is_small_enough(larr, start_idx, end_idx, max_lines, max_chars))
    {
      push_fracture(r, larr, start_idx, end_idx);
      return;
    }
   
  // find maximum weight, between excluding first and last weight, 
  // so that we have three distinct points to break at.
  ss = 1;
  ee = 1;
  bisec_idx = find_max_idx(larr, start_idx+ss, end_idx-ee);
  // max two of the following three blocks will be executed.
  // these three blocks are here to counter monotonic slopes
  // at the end of intervals. 
  // if other peaks surface, we jump there.
  // if all fails, we produce a series of two-liners along the slope,
  // only in this case we get a quadratic runtime.
  // given the high dynamics in calculating weight, a monotonic slope 
  // is unlikely, and a long monotonic slope extremly unlikely.
  // try to move away from the upper end, if we are there.
  while (bisec_idx == end_idx-ee-1)
    {
      ee++;
      // printf("%d,%d move down\n",start_idx,end_idx);
      if (end_idx-ee < start_idx+ss + 2) break;
      bisec_idx = find_max_idx(larr, start_idx+ss, end_idx-ee);
    }
  // try to move away from the lower end, if we are there.
  while (bisec_idx == start_idx+ss)
    {
      ss++;
      // printf("%d,%d move up\n",start_idx,end_idx);
      if (end_idx-ee < start_idx+ss + 2) break;
      bisec_idx = find_max_idx(larr, start_idx+ss, end_idx-ee);
    }
  // again try to move away from the upper end, if we are there.
  while (bisec_idx == end_idx-ee-1)
    {
      ee++;
      // printf("%d,%d move down\n",start_idx,end_idx);
      if (end_idx-ee < start_idx+ss + 2) break;
      bisec_idx = find_max_idx(larr, start_idx+ss, end_idx-ee);
    }
   
  // be recursive; this trivially keeps the entries in r sorted.
  bisect_fract(r, larr, start_idx, bisec_idx, max_lines, max_chars);
  bisect_fract(r, larr, bisec_idx,   end_idx, max_lines, max_chars);
}
MODULE = Text::Fracture PACKAGE = Text::Fracture
PROTOTYPES: ENABLE
int
init(obj)
    HV *obj
  PREINIT:
    SV** pp;
  CODE:
    pp = hv_fetch(obj, "max_chars",    9, 0); if (pp) max_chars   = SvUV(*pp);
    pp = hv_fetch(obj, "max_lines",    9, 0); if (pp) max_lines   = SvUV(*pp);
    pp = hv_fetch(obj, "max_cpl",      7, 0); if (pp) max_cpl     = SvUV(*pp);
    pp = hv_fetch(obj, "verbose",      7, 0); if (pp) verbose     = SvUV(*pp);
    if (max_chars < max_cpl) croak("max_chars=%d must be greater than max_cpl=%d\n", max_chars, max_cpl);
    if (max_lines <= 1) croak("max_lines must > 1, not %d\n", max_lines);
     
    RETVAL = 1;
  OUTPUT:
    RETVAL
SV *
do_fract(sv_text)
    SV *sv_text
  PREINIT:
    int larr_size = 0;          // allocated max number of lines 
    int larr_idx = 0;           // idx = larr-l;
    struct line *larr = NULL;   // array to store line info.
    struct line *l = NULL;      // l = &larr[larr_idx]
    int line_count_total;       // counts through the file
    int line_count;             // counts since start of fragment
    AV *r;                      // return array;
    int text_lnr;               // line number in text. starts with 1.
    int line_off;               // byte offset in text, where this line starts.
    int last_nonprint_off;      // byte offset in text, where a nonprintable char was.
    int last_whitespace_off;    // byte offset in text, where a whitespace was.
    int last_nonwordx_off;      // byte offset in text, where a non-word char was.
    STRLEN text_len;            // like strlen(text), but including '\0' bytes. STRLEN is unsigned!
    struct char_input in;       // input object.
    const char *text;
  INIT:
    text = (const char *)SvPV(sv_text, text_len);
    line_count = line_count_total = 0;
    r = (AV *)sv_2mortal((SV *)newAV());
    last_whitespace_off = last_nonprint_off = last_nonwordx_off = 0;
  CODE:
    if (verbose) warn(" max_chars=%d, max_lines=%d, max_cpl=%d\n text_len=%d\n", 
        max_chars, max_lines, max_cpl, (int)text_len);
    // estimate size of larr[]
    line_off = 0;
    char_input_init(&in);
    while (in.offset < (int)text_len)
      {
        char_input_fetch(&in, text, (int)text_len);
        if ((in.ch == '\n') || (in.ch == '\f') || 
            (in.next_offset - line_off > max_cpl))
          {
            // count this line as 1, or more, if it is longer than max_cpl.
            // more is: chunks of at least max_cpl/2 size.
            larr_size += (int)((in.next_offset - line_off) / max_cpl * 2) + 1;
            line_off = in.next_offset;
          }
      }
    larr_size++;        // we'll add one additional dummy element after the loop
    larr = (struct line *)calloc(sizeof(struct line), larr_size+1);
    // populate larr[]
    line_off = 0;
    text_lnr = 1;
    larr_idx = 0;
    char_input_init(&in);
    while (in.offset < (int)text_len)
      {
        unsigned char c;
        char_input_fetch(&in, text, (int)text_len);
        // similar logic as in char_stat(), but ignoring \0
        c = (unsigned char)in.ch;
        if (!is_word_ch_x(c)) 
          last_nonwordx_off = in.offset;
        if (c == ' ' || c == '\t' || c == '\n' || c == '\r') 
          last_whitespace_off = in.offset;
        if ((c && c < 32) || c > 127) 
          last_nonprint_off = in.offset;
        if ((in.ch == '\n') || (in.ch == '\f'))
          {
            l = &larr[larr_idx++];
            l->offset = line_off;
            l->offset_l = text_lnr;
            line_off = l->end_offset = in.next_offset;
            if ((in.ch == '\f') || (in.ch == '\n' && in.last_ch == '\n'))
              l->weight = WEIGHT_BLANK_LINE;
            // This is the only weight that gets applied outside of weight_line().
            // reason for this little hack: see inside of weight_line()
            text_lnr++;
          }
        else if (in.next_offset - line_off > max_cpl)
          {
            int break_off, min_break_off;
            l = &larr[larr_idx++];
            l->offset = line_off;
            l->offset_l = text_lnr;
            //
            // no newline in viscinity. sigh.
            // find a (good?) break point or rather a not so bad one .
            // between halfway of max_cpl and max_cpl
            // we prefer to take the rightmost whitespace,
            // if there is none, we take the rightmost nonprinting
            // or failing the above, we take the rightmost nonword character.
            // failing everything, we break just at max_cpl.
            // 
            break_off = in.next_offset;
            // must consume at least max_cpl/2 chars now, 
            // or larr_idx may go out of bounds later. Take care.
            min_break_off = line_off+max_cpl/2;
            if (last_whitespace_off > min_break_off)
              break_off = last_whitespace_off;
            else if (last_nonprint_off > min_break_off)
              break_off = last_nonprint_off;
            else if (last_nonwordx_off > min_break_off)
              break_off = last_nonwordx_off;
            line_off = l->end_offset = break_off;
          }
      }
    assert(larr_idx < larr_size);    // calloc() above was big enough
    l = &larr[larr_idx];
    l->offset = line_off;
    l->offset_l = text_lnr;
    l->end_offset = in.next_offset;
    l->weight = WEIGHT_BLANK_LINE * 2;
    larr_size = larr_idx;               //  we know how long we really are
    for (larr_idx = 0; larr_idx <= larr_size; larr_idx++)
      {
        weight_line(&larr[larr_idx], &larr[larr_idx+1], text);
        if (verbose > 1)
          {
            printf("larr[%d].w=%-5d lno=%-3d l=%d\n", 
            larr_idx, larr[larr_idx].weight,
            larr[larr_idx].offset_l, larr[larr_idx].length);
          }
      }
     
    bisect_fract(r, larr, -1, larr_size, max_lines, max_chars);
    // 
    if (larr) free((void *)larr);
    //
    RETVAL = newRV((SV *)r);
  OUTPUT:
    RETVAL