ring.cc 49.2 KB
Newer Older
1
/*
2
 * Copyright (C) 2002,2009,2010 Red Hat, Inc.
3
 *
4 5 6 7
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
8
 *
9 10
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12
 * Lesser General Public License for more details.
13
 *
14 15 16
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
17 18
 *
 * Red Hat Author(s): Nalin Dahyabhai, Behdad Esfahbod
19 20
 */

21
#include "config.h"
22

23
#include "debug.h"
24
#include "ring.hh"
25
#include "vterowdata.hh"
26

27
#include <string.h>
28

29 30 31 32 33 34 35 36 37 38
/*
 * Copy the common attributes from VteCellAttr to VteStreamCellAttr or vice versa.
 */
static inline void
_attrcpy (void *dst, void *src)
{
        memcpy(dst, src, VTE_CELL_ATTR_COMMON_BYTES);
}

using namespace vte::base;
39

40
/*
41
 * VteRing: A buffer ring
42 43
 */

44
#ifdef VTE_DEBUG
45 46
void
Ring::validate() const
47
{
48
	_vte_debug_print(VTE_DEBUG_RING,
49
			" Delta = %lu, Length = %lu, Next = %lu, Max = %lu, Writable = %lu.\n",
50 51
			m_start, m_end - m_start, m_end,
			m_max, m_end - m_writable);
52

53 54
	g_assert_cmpuint(m_start, <=, m_writable);
	g_assert_cmpuint(m_writable, <=, m_end);
55

56 57
	g_assert_cmpuint(m_end - m_start, <=, m_max);
	g_assert_cmpuint(m_end - m_writable, <=, m_mask);
58
}
59
#else
60
#define validate(...) do { } while(0)
61
#endif
62

63 64 65 66 67
Ring::Ring(row_t max_rows,
           bool has_streams)
        : m_max{MAX(max_rows, 3)},
          m_has_streams{has_streams},
          m_last_attr{basic_cell.attr}
68
{
69
	_vte_debug_print(VTE_DEBUG_RING, "New ring %p.\n", this);
70

71
	m_array = (VteRowData* ) g_malloc0 (sizeof (m_array[0]) * (m_mask + 1));
72

73
	if (has_streams) {
74 75 76
		m_attr_stream = _vte_file_stream_new ();
		m_text_stream = _vte_file_stream_new ();
		m_row_stream = _vte_file_stream_new ();
77
	} else {
78
		m_attr_stream = m_text_stream = m_row_stream = nullptr;
79
	}
80

81
	m_utf8_buffer = g_string_sized_new (128);
82

83
	_vte_row_data_init (&m_cached_row);
84

85 86 87
        m_hyperlinks = g_ptr_array_new();
        auto empty_str = g_string_new_len("", 0);
        g_ptr_array_add(m_hyperlinks, empty_str);
88

89
	validate();
90 91
}

92
Ring::~Ring()
93
{
94 95
	for (size_t i = 0; i <= m_mask; i++)
		_vte_row_data_fini (&m_array[i]);
96

97
	g_free (m_array);
98

99 100 101 102
	if (m_has_streams) {
		g_object_unref (m_attr_stream);
		g_object_unref (m_text_stream);
		g_object_unref (m_row_stream);
103
	}
104

105
	g_string_free (m_utf8_buffer, TRUE);
106

107 108 109
        for (size_t i = 0; i < m_hyperlinks->len; i++)
                g_string_free (hyperlink_get(i), TRUE);
        g_ptr_array_free (m_hyperlinks, TRUE);
110

111
	_vte_row_data_fini(&m_cached_row);
112 113 114 115 116 117 118 119
}

#define SET_BIT(buf, n) buf[(n) / 8] |= (1 << ((n) % 8))
#define GET_BIT(buf, n) ((buf[(n) / 8] >> ((n) % 8)) & 1)

/*
 * Do a round of garbage collection. Hyperlinks that no longer occur in the ring are wiped out.
 */
120 121
void
Ring::hyperlink_gc()
122
{
123
        row_t i, j;
124
        hyperlink_idx_t idx;
125
        VteRowData* row;
126 127 128 129
        char *used;

        _vte_debug_print (VTE_DEBUG_HYPERLINK,
                          "hyperlink: GC starting (highest used idx is %d)\n",
130
                          m_hyperlink_highest_used_idx);
131

132
        m_hyperlink_maybe_gc_counter = 0;
133

134
        if (m_hyperlink_highest_used_idx == 0) {
135 136 137 138 139 140
                _vte_debug_print (VTE_DEBUG_HYPERLINK,
                                  "hyperlink: GC done (no links at all, nothing to do)\n");
                return;
        }

        /* One bit for each idx to see if it's used. */
141
        used = (char *) g_malloc0 (m_hyperlink_highest_used_idx / 8 + 1);
142 143

        /* A few special values not to be garbage collected. */
144 145 146
        SET_BIT(used, m_hyperlink_current_idx);
        SET_BIT(used, m_hyperlink_hover_idx);
        SET_BIT(used, m_last_attr.hyperlink_idx);
147

148 149
        for (i = m_writable; i < m_end; i++) {
                row = get_writable_index(i);
150 151 152 153 154 155
                for (j = 0; j < row->len; j++) {
                        idx = row->cells[j].attr.hyperlink_idx;
                        SET_BIT(used, idx);
                }
        }

156 157
        for (idx = 1; idx <= m_hyperlink_highest_used_idx; idx++) {
                if (!GET_BIT(used, idx) && hyperlink_get(idx)->len != 0) {
158 159
                        _vte_debug_print (VTE_DEBUG_HYPERLINK,
                                          "hyperlink: GC purging link %d to id;uri=\"%s\"\n",
160
                                          idx, hyperlink_get(idx)->str);
161
                        /* Wipe out the ID and URI itself so it doesn't linger on in the memory for a long time */
162 163
                        memset(hyperlink_get(idx)->str, 0, hyperlink_get(idx)->len);
                        g_string_truncate (hyperlink_get(idx), 0);
164 165 166
                }
        }

167 168
        while (m_hyperlink_highest_used_idx >= 1 && hyperlink_get(m_hyperlink_highest_used_idx)->len == 0) {
               m_hyperlink_highest_used_idx--;
169 170 171 172
        }

        _vte_debug_print (VTE_DEBUG_HYPERLINK,
                          "hyperlink: GC done (highest used idx is now %d)\n",
173
                          m_hyperlink_highest_used_idx);
174 175 176 177 178 179 180 181

        g_free (used);
}

/*
 * Cumulate the given value, and do a GC when 65536 is reached.
 */
void
182
Ring::hyperlink_maybe_gc(row_t increment)
183
{
184
        m_hyperlink_maybe_gc_counter += increment;
185 186 187

        _vte_debug_print (VTE_DEBUG_HYPERLINK,
                          "hyperlink: maybe GC, counter at %ld\n",
188
                          m_hyperlink_maybe_gc_counter);
189

190 191
        if (m_hyperlink_maybe_gc_counter >= 65536)
                hyperlink_gc();
192 193 194 195 196 197 198 199 200 201 202
}

/*
 * Find existing idx for the hyperlink or allocate a new one.
 *
 * Returns 0 if given no hyperlink or an empty one, or if the pool is full.
 * Returns the idx (either already existing or newly allocated) from 1 up to
 * VTE_HYPERLINK_COUNT_MAX inclusive otherwise.
 *
 * FIXME do something more effective than a linear search
 */
203 204
Ring::hyperlink_idx_t
Ring::get_hyperlink_idx_no_update_current(char const* hyperlink)
205 206 207 208 209 210 211 212 213 214 215
{
        hyperlink_idx_t idx;
        gsize len;
        GString *str;

        if (!hyperlink || !hyperlink[0])
                return 0;

        len = strlen(hyperlink);

        /* Linear search for this particular URI */
216 217 218
        auto const last_idx = m_hyperlink_highest_used_idx + 1;
        for (idx = 1; idx < last_idx; ++idx) {
                if (strcmp(hyperlink_get(idx)->str, hyperlink) == 0) {
219 220 221 222 223 224 225
                        _vte_debug_print (VTE_DEBUG_HYPERLINK,
                                          "get_hyperlink_idx: already existing idx %d for id;uri=\"%s\"\n",
                                          idx, hyperlink);
                        return idx;
                }
        }

226 227
        /* FIXME it's the second time we're GCing if coming from get_hyperlink_idx */
        hyperlink_gc();
228 229

        /* Another linear search for an empty slot where a GString is already allocated */
230 231
        for (idx = 1; idx < m_hyperlinks->len; idx++) {
                if (hyperlink_get(idx)->len == 0) {
232 233 234 235
                        _vte_debug_print (VTE_DEBUG_HYPERLINK,
                                          "get_hyperlink_idx: reassigning old idx %d for id;uri=\"%s\"\n",
                                          idx, hyperlink);
                        /* Grow size if required, however, never shrink to avoid long-term memory fragmentation. */
236 237
                        g_string_append_len (hyperlink_get(idx), hyperlink, len);
                        m_hyperlink_highest_used_idx = MAX (m_hyperlink_highest_used_idx, idx);
238 239 240 241 242
                        return idx;
                }
        }

        /* All allocated slots are in use. Gotta allocate a new one */
243
        g_assert_cmpuint(m_hyperlink_highest_used_idx + 1, ==, m_hyperlinks->len);
244 245 246

        /* VTE_HYPERLINK_COUNT_MAX should be big enough for this not to happen under
           normal circumstances. Anyway, it's cheap to protect against extreme ones. */
247
        if (m_hyperlink_highest_used_idx == VTE_HYPERLINK_COUNT_MAX) {
248 249 250 251 252 253
                _vte_debug_print (VTE_DEBUG_HYPERLINK,
                                  "get_hyperlink_idx: idx 0 (ran out of available idxs) for id;uri=\"%s\"\n",
                                  hyperlink);
                return 0;
        }

254
        idx = ++m_hyperlink_highest_used_idx;
255 256 257 258
        _vte_debug_print (VTE_DEBUG_HYPERLINK,
                          "get_hyperlink_idx: brand new idx %d for id;uri=\"%s\"\n",
                          idx, hyperlink);
        str = g_string_new_len (hyperlink, len);
259
        g_ptr_array_add(m_hyperlinks, str);
260

261
        g_assert_cmpuint(m_hyperlink_highest_used_idx + 1, ==, m_hyperlinks->len);
262 263 264 265 266 267 268 269 270 271 272 273 274

        return idx;
}

/*
 * Find existing idx for the hyperlink or allocate a new one.
 *
 * Returns 0 if given no hyperlink or an empty one, or if the pool is full.
 * Returns the idx (either already existing or newly allocated) from 1 up to
 * VTE_HYPERLINK_COUNT_MAX inclusive otherwise.
 *
 * The current idx is also updated, in order not to be garbage collected.
 */
275 276
Ring::hyperlink_idx_t
Ring::get_hyperlink_idx(char const* hyperlink)
277 278
{
        /* Release current idx and do a round of GC to possibly purge its hyperlink,
279 280 281
         * even if new hyperlink is nullptr or empty. */
        m_hyperlink_current_idx = 0;
        hyperlink_gc();
282

283 284
        m_hyperlink_current_idx = get_hyperlink_idx_no_update_current(hyperlink);
        return m_hyperlink_current_idx;
285 286
}

287 288 289
void
Ring::freeze_row(row_t position,
                 VteRowData const* row)
290
{
291
	VteCell *cell;
292
	GString *buffer = m_utf8_buffer;
293
        GString *hyperlink;
294
	int i;
295
        gboolean froze_hyperlink = FALSE;
296

297
	_vte_debug_print (VTE_DEBUG_RING, "Freezing row %lu.\n", position);
298

299
        g_assert(m_has_streams);
300

301 302 303 304
	RowRecord record;
	memset(&record, 0, sizeof(record));
	record.text_start_offset = _vte_stream_head(m_text_stream);
	record.attr_start_offset = _vte_stream_head(m_attr_stream);
305
	record.is_ascii = 1;
306 307 308

	g_string_set_size (buffer, 0);
	for (i = 0, cell = row->cells; i < row->len; i++, cell++) {
309
		VteCellAttr attr;
310 311 312 313 314 315 316 317 318 319 320 321 322
		int num_chars;

		/* Attr storage:
		 *
		 * 1. We don't store attrs for fragments.  They can be
		 * reconstructed using the columns of their start cell.
		 *
		 * 2. We store one attr per vteunistr character starting
		 * from the second character, with columns=0.
		 *
		 * That's enough to reconstruct the attrs, and to store
		 * the text in real UTF-8.
		 */
323
		attr = cell->attr;
324
		if (G_LIKELY (!attr.fragment())) {
325
			CellAttrChange attr_change;
326
                        guint16 hyperlink_length;
327

328 329
			if (memcmp(&m_last_attr, &attr, sizeof (VteCellAttr)) != 0) {
				m_last_attr_text_start_offset = record.text_start_offset + buffer->len;
330
				memset(&attr_change, 0, sizeof (attr_change));
331 332 333
				attr_change.text_end_offset = m_last_attr_text_start_offset;
                                _attrcpy(&attr_change.attr, &m_last_attr);
                                hyperlink = hyperlink_get(m_last_attr.hyperlink_idx);
334
                                attr_change.attr.hyperlink_length = hyperlink->len;
335
				_vte_stream_append (m_attr_stream, (char const* ) &attr_change, sizeof (attr_change));
336
                                if (G_UNLIKELY (hyperlink->len != 0)) {
337
                                        _vte_stream_append (m_attr_stream, hyperlink->str, hyperlink->len);
338 339 340
                                        froze_hyperlink = TRUE;
                                }
                                hyperlink_length = attr_change.attr.hyperlink_length;
341
                                _vte_stream_append (m_attr_stream, (char const* ) &hyperlink_length, 2);
342 343
				if (!buffer->len)
					/* This row doesn't use last_attr, adjust */
344
                                        record.attr_start_offset += sizeof (attr_change) + hyperlink_length + 2;
345
				m_last_attr = attr;
346 347 348 349
			}

			num_chars = _vte_unistr_strlen (cell->c);
			if (num_chars > 1) {
350
                                /* Combining chars */
351
				attr.set_columns(0);
352 353
				m_last_attr_text_start_offset = record.text_start_offset + buffer->len
								  + g_unichar_to_utf8 (_vte_unistr_get_base (cell->c), nullptr);
354
				memset(&attr_change, 0, sizeof (attr_change));
355 356 357
				attr_change.text_end_offset = m_last_attr_text_start_offset;
                                _attrcpy(&attr_change.attr, &m_last_attr);
                                hyperlink = hyperlink_get(m_last_attr.hyperlink_idx);
358
                                attr_change.attr.hyperlink_length = hyperlink->len;
359
				_vte_stream_append (m_attr_stream, (char const* ) &attr_change, sizeof (attr_change));
360
                                if (G_UNLIKELY (hyperlink->len != 0)) {
361
                                        _vte_stream_append (m_attr_stream, hyperlink->str, hyperlink->len);
362 363 364
                                        froze_hyperlink = TRUE;
                                }
                                hyperlink_length = attr_change.attr.hyperlink_length;
365 366
                                _vte_stream_append (m_attr_stream, (char const* ) &hyperlink_length, 2);
				m_last_attr = attr;
367 368
			}

369
			if (cell->c < 32 || cell->c > 126) record.is_ascii = 0;
370 371
			_vte_unistr_append_to_string (cell->c, buffer);
		}
372 373 374
	}
	if (!row->attr.soft_wrapped)
		g_string_append_c (buffer, '\n');
375
	record.soft_wrapped = row->attr.soft_wrapped;
376

377 378
	_vte_stream_append(m_text_stream, buffer->str, buffer->len);
	append_row_record(&record, position);
379 380 381

        /* After freezing some hyperlinks, do a hyperlink GC. The constant is totally arbitrary, feel free to fine tune. */
        if (froze_hyperlink)
382
                hyperlink_maybe_gc(1024);
383 384
}

385 386 387 388 389 390
/* If do_truncate (data is placed back from the stream to the ring), real new hyperlink idxs are looked up or allocated.
 *
 * If !do_truncate (data is fetched only to be displayed), hyperlinked cells are given the pseudo idx VTE_HYPERLINK_IDX_TARGET_IN_STREAM,
 * except for the hyperlink_hover_idx which gets this real idx. This is important for hover underlining.
 *
 * Optionally updates the hyperlink parameter to point to the ring-owned hyperlink target. */
391 392 393 394 395 396
void
Ring::thaw_row(row_t position,
               VteRowData* row,
               bool do_truncate,
               int hyperlink_column,
               char const** hyperlink)
397
{
398
	RowRecord records[2], record;
399
	VteCellAttr attr;
400
	CellAttrChange attr_change;
401
	VteCell cell;
402 403
	char const* p, *q, *end;
	GString *buffer = m_utf8_buffer;
404 405 406 407
        char hyperlink_readbuf[VTE_HYPERLINK_TOTAL_LENGTH_MAX + 1];

        hyperlink_readbuf[0] = '\0';
        if (hyperlink) {
408 409
                m_hyperlink_buf[0] = '\0';
                *hyperlink = m_hyperlink_buf;
410
        }
411

412
	_vte_debug_print (VTE_DEBUG_RING, "Thawing row %lu.\n", position);
413

414
        g_assert(m_has_streams);
415

416 417
	_vte_row_data_clear (row);

418
	attr_change.text_end_offset = 0;
419

420
	if (!read_row_record(&records[0], position))
421
		return;
422 423
	if ((position + 1) * sizeof (records[0]) < _vte_stream_head (m_row_stream)) {
		if (!read_row_record(&records[1], position + 1))
424 425
			return;
	} else
426
		records[1].text_start_offset = _vte_stream_head (m_text_stream);
427

428
	g_string_set_size (buffer, records[1].text_start_offset - records[0].text_start_offset);
429
	if (!_vte_stream_read (m_text_stream, records[0].text_start_offset, buffer->str, buffer->len))
430
		return;
431 432 433 434

	record = records[0];

	if (G_LIKELY (buffer->len && buffer->str[buffer->len - 1] == '\n'))
435
                g_string_truncate (buffer, buffer->len - 1);
436 437 438 439 440 441
	else
		row->attr.soft_wrapped = TRUE;

	p = buffer->str;
	end = p + buffer->len;
	while (p < end) {
442 443 444
		if (record.text_start_offset >= m_last_attr_text_start_offset) {
			attr = m_last_attr;
                        strcpy(hyperlink_readbuf, hyperlink_get(attr.hyperlink_idx)->str);
445
		} else {
446
			if (record.text_start_offset >= attr_change.text_end_offset) {
447
				if (!_vte_stream_read (m_attr_stream, record.attr_start_offset, (char *) &attr_change, sizeof (attr_change)))
448
					return;
449
				record.attr_start_offset += sizeof (attr_change);
450
                                g_assert_cmpuint (attr_change.attr.hyperlink_length, <=, VTE_HYPERLINK_TOTAL_LENGTH_MAX);
451
                                if (attr_change.attr.hyperlink_length && !_vte_stream_read (m_attr_stream, record.attr_start_offset, hyperlink_readbuf, attr_change.attr.hyperlink_length))
452 453 454 455 456 457 458 459 460 461
                                        return;
                                hyperlink_readbuf[attr_change.attr.hyperlink_length] = '\0';
                                record.attr_start_offset += attr_change.attr.hyperlink_length + 2;

                                _attrcpy(&attr, &attr_change.attr);
                                attr.hyperlink_idx = 0;
                                if (G_UNLIKELY (attr_change.attr.hyperlink_length)) {
                                        if (do_truncate) {
                                                /* Find the existing idx or allocate a new one, just as when receiving an OSC 8 escape sequence.
                                                 * Do not update the current idx though. */
462
                                                attr.hyperlink_idx = get_hyperlink_idx_no_update_current(hyperlink_readbuf);
463 464 465
                                        } else {
                                                /* Use a special hyperlink idx, except if to be underlined because the hyperlink is the same as the hovered cell's. */
                                                attr.hyperlink_idx = VTE_HYPERLINK_IDX_TARGET_IN_STREAM;
466 467 468
                                                if (m_hyperlink_hover_idx != 0 && strcmp(hyperlink_readbuf, hyperlink_get(m_hyperlink_hover_idx)->str) == 0) {
                                                        /* FIXME here we're calling the expensive strcmp() above and get_hyperlink_idx_no_update_current() way too many times. */
                                                        attr.hyperlink_idx = get_hyperlink_idx_no_update_current(hyperlink_readbuf);
469 470 471
                                                }
                                        }
                                }
472 473 474
			}
		}

475
		cell.attr = attr;
476
                _VTE_DEBUG_IF(VTE_DEBUG_RING | VTE_DEBUG_HYPERLINK) {
477 478
                        /* Debug: Reverse the colors for the stream's contents. */
                        if (!do_truncate) {
479
                                cell.attr.attr ^= VTE_ATTR_REVERSE;
480 481
                        }
                }
482 483 484
		cell.c = g_utf8_get_char (p);

		q = g_utf8_next_char (p);
485
		record.text_start_offset += q - p;
486 487
		p = q;

488
		if (G_UNLIKELY (cell.attr.columns() == 0)) {
489 490 491
			if (G_LIKELY (row->len)) {
				/* Combine it */
				row->cells[row->len - 1].c = _vte_unistr_append_unichar (row->cells[row->len - 1].c, cell.c);
492 493 494 495
                                /* Spread it to all the previous cells of a potentially multicell character */
                                for (int i = row->len - 1; i >= 1 && row->cells[i].attr.fragment(); i--) {
                                        row->cells[i - 1].c = row->cells[i].c;
                                }
496
			} else {
497
				cell.attr.set_columns(1);
498 499
                                if (row->len == hyperlink_column && hyperlink != nullptr)
                                        *hyperlink = strcpy(m_hyperlink_buf, hyperlink_readbuf);
500 501
				_vte_row_data_append (row, &cell);
			}
502
		} else {
503 504
                        if (row->len == hyperlink_column && hyperlink != nullptr)
                                *hyperlink = strcpy(m_hyperlink_buf, hyperlink_readbuf);
505
			_vte_row_data_append (row, &cell);
506
			if (cell.attr.columns() > 1) {
507
				/* Add the fragments */
508 509 510
				int i, columns = cell.attr.columns();
				cell.attr.set_fragment(true);
				cell.attr.set_columns(1);
511
                                for (i = 1; i < columns; i++) {
512 513
                                        if (row->len == hyperlink_column && hyperlink != nullptr)
                                                *hyperlink = strcpy(m_hyperlink_buf, hyperlink_readbuf);
514
					_vte_row_data_append (row, &cell);
515
                                }
516 517
			}
		}
518
	}
519

520 521 522
        /* FIXME this is extremely complicated (by design), figure out something better.
           This is the only place where we need to walk backwards in attr_stream,
           which is the reason for the hyperlink's length being repeated after the hyperlink itself. */
523
	if (do_truncate) {
524 525
		gsize attr_stream_truncate_at = records[0].attr_start_offset;
		_vte_debug_print (VTE_DEBUG_RING, "Truncating\n");
526
		if (records[0].text_start_offset <= m_last_attr_text_start_offset) {
527
			/* Check the previous attr record. If its text ends where truncating, this attr record also needs to be removed. */
528
                        guint16 hyperlink_length;
529
                        if (_vte_stream_read (m_attr_stream, attr_stream_truncate_at - 2, (char *) &hyperlink_length, 2)) {
530
                                g_assert_cmpuint (hyperlink_length, <=, VTE_HYPERLINK_TOTAL_LENGTH_MAX);
531
                                if (_vte_stream_read (m_attr_stream, attr_stream_truncate_at - 2 - hyperlink_length - sizeof (attr_change), (char *) &attr_change, sizeof (attr_change))) {
532 533 534 535
                                        if (records[0].text_start_offset == attr_change.text_end_offset) {
                                                _vte_debug_print (VTE_DEBUG_RING, "... at attribute change\n");
                                                attr_stream_truncate_at -= sizeof (attr_change) + hyperlink_length + 2;
                                        }
536 537 538 539
				}
			}
			/* Reconstruct last_attr from the first record of attr_stream that we cut off,
			   last_attr_text_start_offset from the last record that we keep. */
540 541 542 543
			if (_vte_stream_read (m_attr_stream, attr_stream_truncate_at, (char *) &attr_change, sizeof (attr_change))) {
                                _attrcpy(&m_last_attr, &attr_change.attr);
                                m_last_attr.hyperlink_idx = 0;
                                if (attr_change.attr.hyperlink_length && _vte_stream_read (m_attr_stream, attr_stream_truncate_at + sizeof (attr_change), (char *) &hyperlink_readbuf, attr_change.attr.hyperlink_length)) {
544
                                        hyperlink_readbuf[attr_change.attr.hyperlink_length] = '\0';
545
                                        m_last_attr.hyperlink_idx = get_hyperlink_idx(hyperlink_readbuf);
546
                                }
547
                                if (_vte_stream_read (m_attr_stream, attr_stream_truncate_at - 2, (char *) &hyperlink_length, 2)) {
548
                                        g_assert_cmpuint (hyperlink_length, <=, VTE_HYPERLINK_TOTAL_LENGTH_MAX);
549 550
                                        if (_vte_stream_read (m_attr_stream, attr_stream_truncate_at - 2 - hyperlink_length - sizeof (attr_change), (char *) &attr_change, sizeof (attr_change))) {
                                                m_last_attr_text_start_offset = attr_change.text_end_offset;
551
                                        } else {
552
                                                m_last_attr_text_start_offset = 0;
553
                                        }
554
				} else {
555
					m_last_attr_text_start_offset = 0;
556
				}
557
			} else {
558 559
				m_last_attr_text_start_offset = 0;
				m_last_attr = basic_cell.attr;
560
			}
561
		}
562 563 564
		_vte_stream_truncate (m_row_stream, position * sizeof (record));
		_vte_stream_truncate (m_attr_stream, attr_stream_truncate_at);
		_vte_stream_truncate (m_text_stream, records[0].text_start_offset);
565
	}
566 567
}

568 569
void
Ring::reset_streams(row_t position)
570
{
571
	_vte_debug_print (VTE_DEBUG_RING, "Reseting streams to %lu.\n", position);
572

573 574 575 576
	if (m_has_streams) {
		_vte_stream_reset(m_row_stream, position * sizeof(RowRecord));
                _vte_stream_reset(m_text_stream, _vte_stream_head(m_text_stream));
                _vte_stream_reset(m_attr_stream, _vte_stream_head(m_attr_stream));
577
	}
578

579 580
	m_last_attr_text_start_offset = 0;
	m_last_attr = basic_cell.attr;
581 582
}

583 584
Ring::row_t
Ring::reset()
585
{
586
        _vte_debug_print (VTE_DEBUG_RING, "Reseting the ring at %lu.\n", m_end);
587

588 589 590
        reset_streams(m_end);
        m_start = m_writable = m_end;
        m_cached_row_num = (row_t)-1;
591

592
        return m_end;
593 594
}

595 596
VteRowData const*
Ring::index(row_t position)
597
{
598 599
	if (G_LIKELY (position >= m_writable))
		return get_writable_index(position);
600

601
	if (m_cached_row_num != position) {
602
		_vte_debug_print(VTE_DEBUG_RING, "Caching row %lu.\n", position);
603 604
                thaw_row(position, &m_cached_row, false, -1, nullptr);
		m_cached_row_num = position;
605
	}
606

607
	return &m_cached_row;
608 609
}

610 611 612 613 614 615 616 617 618 619 620 621 622
/*
 * Returns the hyperlink idx at the given position.
 *
 * Updates the hyperlink parameter to point to the hyperlink's target.
 * The buffer is owned by the ring and must not be modified by the caller.
 *
 * Optionally also updates the internal concept of the hovered idx. In this case,
 * a real idx is looked up or newly allocated in the hyperlink pool even if the
 * cell is scrolled out to the streams.
 * This is to be able to underline all cells that share the same hyperlink.
 *
 * Otherwise cells from the stream might get the pseudo idx VTE_HYPERLINK_IDX_TARGET_IN_STREAM.
 */
623 624 625 626 627
Ring::hyperlink_idx_t
Ring::get_hyperlink_at_position(row_t position,
                                column_t col,
                                bool update_hover_idx,
                                char const** hyperlink)
628 629
{
        hyperlink_idx_t idx;
630
        char const* hp;
631

632
        if (hyperlink == nullptr)
633
                hyperlink = &hp;
634
        *hyperlink = nullptr;
635 636 637

        if (update_hover_idx) {
                /* Invalidate the cache because new hover idx might result in new idxs to report. */
638
                m_cached_row_num = (row_t)-1;
639 640
        }

641
        if (G_UNLIKELY (!contains(position) || col < 0)) {
642
                if (update_hover_idx)
643
                        m_hyperlink_hover_idx = 0;
644 645 646
                return 0;
        }

647 648
        if (G_LIKELY (position >= m_writable)) {
                VteRowData* row = get_writable_index(position);
649 650
                if (col >= _vte_row_data_length(row)) {
                        if (update_hover_idx)
651
                                m_hyperlink_hover_idx = 0;
652 653
                        return 0;
                }
654
                *hyperlink = hyperlink_get(row->cells[col].attr.hyperlink_idx)->str;
655 656
                idx = row->cells[col].attr.hyperlink_idx;
        } else {
657
                thaw_row(position, &m_cached_row, false, col, hyperlink);
658
                /* Note: Intentionally don't set cached_row_num. We're about to update
659 660
                 * m_hyperlink_hover_idx which makes some idxs no longer valid. */
                idx = get_hyperlink_idx_no_update_current(*hyperlink);
661 662
        }
        if (**hyperlink == '\0')
663
                *hyperlink = nullptr;
664
        if (update_hover_idx)
665
                m_hyperlink_hover_idx = idx;
666 667 668
        return idx;
}

669 670
VteRowData*
Ring::index_writable(row_t position)
671
{
672 673
	ensure_writable(position);
	return get_writable_index(position);
674 675
}

676 677
void
Ring::freeze_one_row()
678
{
679
	VteRowData* row;
680

681 682
	if (G_UNLIKELY (m_writable == m_start))
		reset_streams(m_writable);
683

684 685
	row = get_writable_index(m_writable);
	freeze_row(m_writable, row);
686

687
	m_writable++;
688 689
}

690 691
void
Ring::thaw_one_row()
692
{
693
	VteRowData* row;
694

695
	g_assert_cmpuint(m_start, <, m_writable);
696

697
	ensure_writable_room();
698

699
	m_writable--;
700

701 702
	if (m_writable == m_cached_row_num)
		m_cached_row_num = (row_t)-1; /* Invalidate cached row */
703

704 705
	row = get_writable_index(m_writable);
        thaw_row(m_writable, row, true, -1, nullptr);
706 707
}

708 709
void
Ring::discard_one_row()
710
{
711 712 713 714 715 716 717 718 719
	m_start++;
	if (G_UNLIKELY(m_start == m_writable)) {
		reset_streams(m_writable);
	} else if (m_start < m_writable) {
		RowRecord record;
		_vte_stream_advance_tail(m_row_stream, m_start * sizeof (record));
		if (G_LIKELY(read_row_record(&record, m_start))) {
			_vte_stream_advance_tail(m_text_stream, record.text_start_offset);
			_vte_stream_advance_tail(m_attr_stream, record.attr_start_offset);
720
		}
721
	} else {
722
		m_writable = m_start;
723
	}
724 725
}

726 727
void
Ring::maybe_freeze_one_row()
728
{
729 730 731
        if (G_LIKELY(m_mask >= m_visible_rows &&
                     m_writable + m_mask + 1 == m_end))
		freeze_one_row();
732
	else
733
		ensure_writable_room();
734 735
}

736 737 738
//FIXMEchpe maybe inline this one
void
Ring::maybe_discard_one_row()
739
{
740 741
	if (length() == m_max)
		discard_one_row();
742 743
}

744 745
void
Ring::ensure_writable_room()
Behdad Esfahbod's avatar
Behdad Esfahbod committed
746
{
747 748
	row_t new_mask, old_mask, i, end;
	VteRowData* old_array, *new_array;;
Behdad Esfahbod's avatar
Behdad Esfahbod committed
749

750 751
        if (G_LIKELY(m_mask >= m_visible_rows &&
                     m_writable + m_mask + 1 > m_end))
752
		return;
Behdad Esfahbod's avatar
Behdad Esfahbod committed
753

754 755
	old_mask = m_mask;
	old_array = m_array;
Behdad Esfahbod's avatar
Behdad Esfahbod committed
756

757
	do {
758 759
		m_mask = (m_mask << 1) + 1;
        } while (m_mask < m_visible_rows || m_writable + m_mask + 1 <= m_end);
760

761
	_vte_debug_print(VTE_DEBUG_RING, "Enlarging writable array from %lu to %lu\n", old_mask, m_mask);
762

763
	m_array = (VteRowData* ) g_malloc0(sizeof (m_array[0]) * (m_mask + 1));
Behdad Esfahbod's avatar
Behdad Esfahbod committed
764

765 766
	new_mask = m_mask;
	new_array = m_array;
Behdad Esfahbod's avatar
Behdad Esfahbod committed
767

768 769
	end = m_writable + old_mask + 1;
	for (i = m_writable; i < end; i++)
770
		new_array[i & new_mask] = old_array[i & old_mask];
771

772
	g_free (old_array);
773 774
}

775 776
void
Ring::ensure_writable(row_t position)
777
{
778
	if (G_LIKELY(position >= m_writable))
779 780
		return;

781
	_vte_debug_print(VTE_DEBUG_RING, "Ensure writable %lu.\n", position);
782

783 784 785
        //FIXMEchpe surely this can be optimised
	while (position < m_writable)
		thaw_one_row();
786 787
}

Behdad Esfahbod's avatar
Behdad Esfahbod committed
788
/**
789
 * Ring::resize:
Behdad Esfahbod's avatar
Behdad Esfahbod committed
790 791 792 793 794
 * @max_rows: new maximum numbers of rows in the ring
 *
 * Changes the number of lines the ring can contain.
 */
void
795
Ring::resize(row_t max_rows)
Behdad Esfahbod's avatar
Behdad Esfahbod committed
796
{
797
	_vte_debug_print(VTE_DEBUG_RING, "Resizing to %lu.\n", max_rows);
798 799

	validate();
800

Behdad Esfahbod's avatar
Behdad Esfahbod committed
801
	/* Adjust the start of tail chunk now */
802 803 804 805 806
	if (length() > max_rows) {
		m_start = m_end - max_rows;
		if (m_start >= m_writable) {
			reset_streams(m_writable);
			m_writable = m_start;
807
		}
808
	}
Behdad Esfahbod's avatar
Behdad Esfahbod committed
809

810
	m_max = max_rows;
Behdad Esfahbod's avatar
Behdad Esfahbod committed
811 812 813
}

void
814
Ring::shrink(row_t max_len)
Behdad Esfahbod's avatar
Behdad Esfahbod committed
815
{
816
	if (length() <= max_len)
Behdad Esfahbod's avatar
Behdad Esfahbod committed
817 818
		return;

819
	_vte_debug_print(VTE_DEBUG_RING, "Shrinking to %lu.\n", max_len);
820

821 822 823 824
	validate();

	if (m_writable - m_start <= max_len)
		m_end = m_start + max_len;
Behdad Esfahbod's avatar
Behdad Esfahbod committed
825
	else {
826 827 828
		while (m_writable - m_start > max_len) {
			ensure_writable(m_writable - 1);
			m_end = m_writable;
Behdad Esfahbod's avatar
Behdad Esfahbod committed
829 830
		}
	}
831

832
	/* TODO May want to shrink down m_array */
833

834
	validate();
Behdad Esfahbod's avatar
Behdad Esfahbod committed
835 836
}

837
/**
838
 * Ring::insert:
839 840
 * @position: an index
 *
841
 * Inserts a new, empty, row into @ring at the @position'th offset.
Behdad Esfahbod's avatar
Behdad Esfahbod committed
842
 * The item at that position and any items after that are shifted down.
843
 *
844
 * Return: the newly added row.
845
 */
846 847
VteRowData*
Ring::insert(row_t position)
848
{
849 850
	row_t i;
	VteRowData* row, tmp;
851

852
	_vte_debug_print(VTE_DEBUG_RING, "Inserting at position %lu.\n", position);
853
	validate();
854

855 856 857
	maybe_discard_one_row();
	ensure_writable(position);
	ensure_writable_room();
858

859 860
	g_assert_cmpuint (position, >=, m_writable);
	g_assert_cmpuint (position, <=, m_end);
Behdad Esfahbod's avatar
Behdad Esfahbod committed
861

862 863 864 865 866
        //FIXMEchpe WTF use better data structures!
	tmp = *get_writable_index(m_end);
	for (i = m_end; i > position; i--)
		*get_writable_index(i) = *get_writable_index(i - 1);
	*get_writable_index(position) = tmp;
867

868
	row = get_writable_index(position);
869
	_vte_row_data_clear (row);
870
	m_end++;
871

872 873
	maybe_freeze_one_row();
        validate();
874
	return row;
875 876
}

877
/**
878
 * Ring::remove:
879 880 881 882 883
 * @position: an index
 *
 * Removes the @position'th item from @ring.
 */
void
884
Ring::remove(row_t position)
885
{
886
	row_t i;
887 888
	VteRowData tmp;

889
	_vte_debug_print(VTE_DEBUG_RING, "Removing item at position %lu.\n", position);
890
        validate();
891

892
	if (G_UNLIKELY(!contains(position)))
893
		return;
894

895
	ensure_writable(position);
896

897 898 899 900 901
        //FIXMEchpe WTF as above
	tmp = *get_writable_index(position);
	for (i = position; i < m_end - 1; i++)
		*get_writable_index(i) = *get_writable_index(i + 1);
	*get_writable_index(m_end - 1) = tmp;
902

903 904
	if (m_end > m_writable)
		m_end--;
905

906
        validate();
907 908 909
}


910
/**
911
 * Ring::append:
912 913
 * @data: the new item
 *
Behdad Esfahbod's avatar
Behdad Esfahbod committed
914
 * Appends a new item to the ring.
915 916 917
 *
 * Return: the newly added row.
 */
918 919
VteRowData*
Ring::append()
920
{
921
	return insert(next());
922 923
}

924

925
/**
926
 * Ring::drop_scrollback:
927 928 929 930 931 932 933
 * @position: drop contents up to this point, which must be in the writable region.
 *
 * Drop the scrollback (offscreen contents).
 *
 * TODOegmont: We wouldn't need the position argument after addressing 708213#c29.
 */
void
934
Ring::drop_scrollback(row_t position)
935
{
936
        ensure_writable(position);
937

938 939
        m_start = m_writable = position;
        reset_streams(position);
940 941
}

942
/**
943 944
 * Ring::set_visible_rows:
 * @rows: the number of visible rows
945
 *
946 947
 * Set the number of visible rows.
 * It's required to be set correctly for the alternate screen so that it
948
 * never hits the streams. It's also required for clearing the scrollback.
949 950
 */
void
951
Ring::set_visible_rows(row_t rows)
952
{
953
        m_visible_rows = rows;
954 955 956
}


957
/* Convert a (row,col) into a CellTextOffset.
958 959
 * Requires the row to be frozen, or be outsize the range covered by the ring.
 */
960 961 962 963
bool
Ring::frozen_row_column_to_text_offset(row_t position,
				       column_t column,
				       CellTextOffset* offset)
964
{
965
	RowRecord records[2];
966
	VteCell *cell;
967 968
	GString *buffer = m_utf8_buffer;
	VteRowData const* row;
969 970
	unsigned int i, num_chars, off;

971 972
	if (position >= m_end) {
		offset->text_offset = _vte_stream_head(m_text_stream) + position - m_end;
973 974
		offset->fragment_cells = 0;
		offset->eol_cells = column;
975
		return true;
976 977
	}

978
	if (G_UNLIKELY (position < m_start)) {
979 980
		/* This happens when the marker (saved cursor position) is
		   scrolled off at the top of the scrollback buffer. */
981
		position = m_start;
982 983 984 985
		column = 0;
		/* go on */
	}

986 987 988 989 990 991
	g_assert_cmpuint(position, <, m_writable);
	if (!read_row_record(&records[0], position))
		return false;
	if ((position + 1) * sizeof (records[0]) < _vte_stream_head(m_row_stream)) {
		if (!read_row_record(&records[1], position + 1))
			return false;
992
	} else
993
		records[1].text_start_offset = _vte_stream_head(m_text_stream);
994 995

	g_string_set_size (buffer, records[1].text_start_offset - records[0].text_start_offset);
996 997
	if (!_vte_stream_read(m_text_stream, records[0].text_start_offset, buffer->str, buffer->len))
		return false;
998 999 1000 1001

	if (G_LIKELY (buffer->len && buffer->str[buffer->len - 1] == '\n'))
		buffer->len--;

1002
	row = index(position);
1003 1004 1005 1006 1007 1008 1009 1010

	/* row and buffer now contain the same text, in different representation */

	/* count the number of characters up to the given column */
	offset->fragment_cells = 0;
	offset->eol_cells = -1;
	num_chars = 0;
	for (i = 0, cell = row->cells; i < row->len && i < column; i++, cell++) {
1011 1012
		if (G_LIKELY (!cell->attr.fragment())) {
			if (G_UNLIKELY (i + cell->attr.columns() > column)) {
1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029
				offset->fragment_cells = column - i;
				break;
			}
			num_chars += _vte_unistr_strlen(cell->c);
		}
	}
	if (i >= row->len) {
		offset->eol_cells = column - i;
	}

	/* count the number of UTF-8 bytes for the given number of characters */
	off = 0;
	while (num_chars > 0 && off < buffer->len) {
		off++;
		if ((buffer->str[off] & 0xC0) != 0x80) num_chars--;
	}
	offset->text_offset = records[0].text_start_offset + off;
1030
	return true;
1031 1032 1033
}


1034 1035
/* Given a row number and a CellTextOffset, compute the column within that row.
   It's the caller's responsibility to ensure that CellTextOffset really falls into that row.
1036 1037
   Requires the row to be frozen, or be outsize the range covered by the ring.
 */
1038 1039 1040 1041
bool
Ring::frozen_row_text_offset_to_column(row_t position,
				       CellTextOffset const* offset,
				       column_t* column)
1042
{
1043
	RowRecord records[2];
1044
	VteCell *cell;
1045 1046
	GString *buffer = m_utf8_buffer;
	VteRowData const* row;
1047 1048
	unsigned int i, off, num_chars, nc;

1049
	if (position >= m_end) {
1050
		*column = offset->eol_cells;
1051
		return true;
1052 1053
	}

1054
	if (G_UNLIKELY (position < m_start)) {
1055 1056 1057
		/* This happens when the marker (saved cursor position) is
		   scrolled off at the top of the scrollback buffer. */
		*column = 0;
1058
		return true;
1059 1060
	}

1061 1062 1063 1064 1065 1066
	g_assert_cmpuint(position, <, m_writable);
	if (!read_row_record(&records[0], position))
		return false;
	if ((position + 1) * sizeof (records[0]) < _vte_stream_head(m_row_stream)) {
		if (!read_row_record(&records[1], position + 1))
			return false;
1067
	} else
1068
		records[1].text_start_offset = _vte_stream_head (m_text_stream);
1069

1070 1071
	g_assert_cmpuint(offset->text_offset, >=, records[0].text_start_offset);
	g_assert_cmpuint(offset->text_offset, <, records[1].text_start_offset);
1072 1073

	g_string_set_size (buffer, records[1].text_start_offset - records[0].text_start_offset);
1074 1075
	if (!_vte_stream_read(m_text_stream, records[0].text_start_offset, buffer->str, buffer->len))
		return false;
1076 1077 1078 1079

	if (G_LIKELY (buffer->len && buffer->str[buffer->len - 1] == '\n'))
		buffer->len--;

1080
	row = index(position);
1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092

	/* row and buffer now contain the same text, in different representation */

	/* count the number of characters for the given UTF-8 text offset */
	off =<