path: root/src/hist.h

#ifndef WSAP_TERM_HIST_H
#define WSAP_TERM_HIST_H

#include "cell.h"
#include "gstore.h"
#include "compat.h"
#include "pen.h"
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

/*
 * History of logical lines. A line is stored once, independent of the
 * terminal width. A line id counts logical lines: a line that needs more than
 * one storage part keeps one id. Ids never change while the line is retained.
 */

#define HIST_PAGE_SIZE 65536
#define HIST_PAGE_SLACK 64
#define HIST_PAGE_USABLE (HIST_PAGE_SIZE - HIST_PAGE_SLACK)
#define HIST_MAX_PART_CELLS 65535

enum hline_flags {
    HLINE_NARROW      = 1 << 0,   /* one ASCII byte per cell */
    HLINE_HAS_WIDE    = 1 << 1,
    HLINE_HAS_CLUSTER = 1 << 2,
    HLINE_HAS_LINK    = 1 << 3,
    HLINE_CONT        = 1 << 4,   /* continues the line of the previous part */
    HLINE_ROWS_EXACT  = 1 << 6,   /* first part: cached row count is exact */
    HLINE_OPEN        = 1 << 5,   /* the part that grows; only the last part */
};

/* One storage part. The first part of a line holds the line's row count. */
struct hline {
    uint32_t off;           /* page << 16 | offset in the page */
    uint32_t text_len;      /* bytes */
    uint16_t cells;         /* display width */
    uint16_t wide;          /* wide glyphs; a one-column view clips them */
    uint16_t attr_len;      /* 0: every cell has the default pen */
    uint8_t flags;
    uint8_t wrap_rows;      /* first part: rows of the line at wrap_cols; 255: count them */
};

_Static_assert(sizeof(struct hline) == 16, "struct hline must stay 16 bytes");

/* Attribute runs of the open part. They move to the page when it closes.
 * count comes before the pens, so a wide store of the pens never covers
 * it. */
struct hist_runs {
    uint8_t *data;
    uint32_t len, cap;
    uint32_t count;         /* cells of the pending run */
    struct pen_attr base;   /* pen of the last emitted run */
    struct pen_attr pen;    /* pen of the pending run */
};

/* Totals for 16 closed lines in one page. A sequence and epoch validate it. */
struct hist_block {
    uint64_t seq, epoch;
    uint32_t page, refs, rows;
    uint16_t cols;
};

struct hist_ascii_line {
    const char *ptr;
    uint16_t len;
    uint8_t wrapped;
};

/*
 * One row of text in the history format, built by appending. A screen text
 * row holds one, so a row that scrolls into history moves by copy. The runs
 * start from the pen start; their buffer never grows, because every run
 * covers at least one cell and the caller sizes it for a full row.
 */
struct text_row {
    uint8_t *text;
    uint8_t *storage;           /* owned buffer, when text uses compact ASCII storage */
    uint16_t text_len;
    uint16_t cells;
    uint16_t wide;
    uint16_t fill_to;           /* blanks with pen fill follow the text up to here */
    uint8_t flags;              /* HLINE_NARROW, HLINE_HAS_WIDE, HLINE_HAS_LINK */
    struct pen_attr start;
    struct pen_attr fill;
    struct hist_runs runs;
};

/* Bytes a text row of cols cells may need: text, and runs. */
#define TEXT_ROW_BYTES(cols) ((size_t)(cols) * 4 + 16)
#define TEXT_ROW_RUNS(cols) (((size_t)(cols) + 2) * 22)

/* A pen as three words: fg, bg, and flags | link << 16 (the layout of
 * pen_attr.flags and .link). The hot path reads and writes whole words, so
 * a store is never read back through a wider load. */
static inline uint32_t pen_sl(const struct pen_attr *p)
{
    uint32_t sl;
    memcpy(&sl, &p->flags, 4);
    return sl;
}

static inline void pen_set(struct pen_attr *p, uint32_t fg, uint32_t bg, uint32_t sl)
{
    p->fg = fg;
    p->bg = bg;
    memcpy(&p->flags, &sl, 4);
}

/* Emit the pending run in the general form. */
void term_hist_runs_emit_slow(struct hist_runs *r);

/* Close the pending run and start one with the pen fg, bg, sl. The caller
 * sized the buffer. A run that changes only colors and covers fewer than
 * 128 cells is a header byte (bit 0 fg, bit 1 bg), a count byte, and the
 * changed colors. */
static inline void hist_runs_switch(struct hist_runs *r, uint32_t fg, uint32_t bg, uint32_t sl)
{
    if (r->count) {
        uint32_t psl = pen_sl(&r->pen);
        if (TERM_EXPECT(r->count < 0x80 && psl == pen_sl(&r->base), 1)) {
            uint8_t *p = r->data + r->len;
            uint32_t dfg = r->pen.fg != r->base.fg, dbg = r->pen.bg != r->base.bg;
            p[0] = (uint8_t)(dfg | dbg << 1);
            p[1] = (uint8_t)r->count;
            memcpy(p + 2, &r->pen.fg, 4);
            p += 2 + dfg * 4;
            memcpy(p, &r->pen.bg, 4);
            r->len = (uint32_t)(p + dbg * 4 - r->data);
        } else {
            term_hist_runs_emit_slow(r);
        }
        pen_set(&r->base, r->pen.fg, r->pen.bg, psl);
    }
    pen_set(&r->pen, fg, bg, sl);
    r->count = 0;
}

static inline void hist_runs_add_pen(struct hist_runs *r, uint32_t fg, uint32_t bg, uint32_t sl,
                                     uint32_t n)
{
    if (fg != r->pen.fg || bg != r->pen.bg || sl != pen_sl(&r->pen))
        hist_runs_switch(r, fg, bg, sl);
    r->count += n;
}

static inline void hist_runs_add(struct hist_runs *r, const struct pen_attr *pen, uint32_t n)
{
    hist_runs_add_pen(r, pen->fg, pen->bg, pen_sl(pen), n);
}

/* Start a text row. Each field gets its own store of its own width, because
 * the first append reads them back at once. */
static inline void text_row_start(struct text_row *row, const struct pen_attr *start)
{
    if (row->storage) row->text = row->storage;
    uint32_t fg = start->fg, bg = start->bg, sl = pen_sl(start);
    row->text_len = 0;
    row->cells = 0;
    row->wide = 0;
    row->fill_to = 0;
    row->flags = HLINE_NARROW;
    pen_set(&row->start, fg, bg, sl);
    row->runs.len = 0;
    row->runs.count = 0;
    pen_set(&row->runs.base, fg, bg, sl);
    pen_set(&row->runs.pen, fg, bg, sl);
}

static inline void text_row_unshare(struct text_row *row)
{
    if (row->storage && row->text != row->storage) {
        memcpy(row->storage, row->text, row->text_len);
        row->text = row->storage;
    }
}

/* The pen of the last cell of a text row. */
static inline struct pen_attr text_row_last_pen(const struct text_row *row)
{
    return row->runs.pen;
}

/* Write the cells of a text row to out; return the cell count. */
int term_hist_text_decode(const struct text_row *row, struct cell *out, int cap, struct gstore *g);
void term_hist_text_mark_links(const struct text_row *row, void (*mark)(void *ud, uint16_t link), void *ud);

struct hist_dec_cache {
    const uint8_t *p, *end;
    struct pen_attr pending_pen;
    struct pen_attr pen;
    uint64_t epoch;
    uint64_t id;
    uint64_t seq;
    uint32_t seg;
    uint32_t off;
    uint32_t col;
    uint32_t pending_count;
    uint32_t left;
    uint16_t cols;
    bool pending;
    bool valid;
};

struct hist {
    struct hline *ring;
    struct hist_block *blocks;
    uint64_t tail, head;        /* part sequence numbers [tail, head) */
    uint64_t base_id;           /* line id of the part at tail */
    uint64_t *cont;             /* CONT parts after tail, oldest first */
    uint8_t **pages;
    uint32_t *page_used;
    uint32_t *page_parts;
    uint32_t *page_rows;
    uint8_t *page_simple;
    uint16_t *free_pages;
    uint32_t *exact_rows;       /* counts that exceed the descriptor byte */
    struct hist_runs runs;
    struct hist_dec_cache dec;

    /* Rows at wrap_cols. counted_rows covers [base_id, rows_id).
     * Snapshot capture counts later closed lines from descriptors.
     * A wide open line keeps a walk that resumes where it stopped. */
    uint64_t rows_id;
    uint64_t counted_rows;
    uint64_t walk_seq;

    /* Changes when retained line ids can name different content. */
    uint64_t index_epoch;
    uint64_t base_cell_id, base_cell; /* removed prefix and its line */
    uint64_t last_id, last_cells, last_wide;

    uint32_t ring_mask;
    uint32_t lines;
    uint32_t line_limit;
    uint32_t cont_first, cont_count, cont_mask;
    uint32_t npages, max_pages, nfree, cur_page;
    uint32_t walk_off, walk_col, walk_rows;
    uint16_t wrap_cols;
    bool all_blank;
    bool walk_on;
};

static inline uint32_t rows_narrow(uint64_t cells, int cols)
{
    return cells <= (uint64_t)cols ? 1 :
        (uint32_t)((cells + (uint64_t)cols - 1) / (uint64_t)cols);
}

bool term_hist_init(struct hist *h, int line_limit, size_t byte_cap);
void term_hist_free(struct hist *h);
void term_hist_clear(struct hist *h);

/* Push one screen row. It joins the open line, or starts a new line. A
 * wrapped row leaves the line open for the next row. */
void term_hist_push_row(struct hist *h, const struct cell *cells, int len, bool wrapped,
                   const struct gstore *g);
void term_hist_push_ascii(struct hist *h, const char *bytes, int n,
                     const struct pen_attr *pen, bool wrapped);
void term_hist_push_ascii_lines(struct hist *h, const struct hist_ascii_line *lines,
                           int count, const struct pen_attr *pen);
/* Ends include LF. ends[0] is the start of the first line. */
void term_hist_push_ascii_lf(struct hist *h, const char *bytes, const uint16_t *ends, int count);
/* Push a text row as one screen row, like term_hist_push_row(). */
void term_hist_push_text(struct hist *h, const struct text_row *row, bool wrapped);
/* Push n empty unwrapped rows. The first one closes an open line. */
void term_hist_push_blank(struct hist *h, size_t n);
void term_hist_close_open_line(struct hist *h);

/* Remove the last line. Write its cells to out (at most cap) and return the
 * number of cells in the line. */
int term_hist_pop_line(struct hist *h, struct cell *out, int cap, struct gstore *g);
/* Copy the last line's cells to out, as term_hist_pop_line() does, and keep the line.
 * Return the number of cells in the line. */
int term_hist_peek_last_line(const struct hist *h, struct cell *out, int cap, struct gstore *g);
/* Take up to n cells back off the end of the last line. Return the count. */
int term_hist_pop_tail_cells(struct hist *h, int n, struct cell *out, struct gstore *g);

static inline uint64_t hist_first_id(const struct hist *h)
{
    return h->base_id;
}

static inline uint64_t hist_end_id(const struct hist *h)
{
    return h->base_id + h->lines;
}

static inline bool hist_is_open(const struct hist *h)
{
    return h->head != h->tail && (h->ring[(h->head - 1) & h->ring_mask].flags & HLINE_OPEN);
}

uint64_t term_hist_line_cells(const struct hist *h, uint64_t id);
uint64_t term_hist_line_wide(const struct hist *h, uint64_t id);
uint8_t term_hist_line_flags(const struct hist *h, uint64_t id);
int term_hist_line_rows(const struct hist *h, uint64_t id, int cols);
int term_hist_decode_segment(const struct hist *h, uint64_t id, int seg, int cols,
                        struct cell *out, struct gstore *g);
int term_hist_decode_segments(const struct hist *h, uint64_t id, int start_seg, int count, int cols,
                         struct cell *out, int *lens, struct gstore *g);

uint64_t term_hist_segment_cell(const struct hist *h, uint64_t id, int seg, int cols);
int term_hist_cell_segment(const struct hist *h, uint64_t id, uint64_t cell, int cols);

void term_hist_mark_links(const struct hist *h, void (*mark)(void *ud, uint16_t link), void *ud);

/* Set the width that pushed rows have. It costs O(1): the stored row counts
 * become stale. Reads count them without changing the history. */
void term_hist_set_width(struct hist *h, int cols);

/* Rows of all retained lines at cols. */
uint64_t term_hist_rows(const struct hist *h, int cols);
uint64_t term_hist_line_estimate(const struct hist *h, uint64_t id, int cols);
uint64_t term_hist_estimated_rows(const struct hist *h, int cols);
void term_hist_prepare_rows(struct hist *h, int cols);
void term_hist_refine_rows(struct hist *h, uint64_t id, int cols, int rows);
bool term_hist_find_row(const struct hist *h, int target_row, int cols, uint64_t *out_id, int *out_seg);

#endif