scroll.c 31.6 KB
Newer Older
1 2
/* Calculate what line insertion or deletion to do, and do it

Paul Eggert's avatar
Paul Eggert committed
3
Copyright (C) 1985-1986, 1990, 1993-1994, 2001-2020 Free Software
4
Foundation, Inc.
Jim Blandy's avatar
Jim Blandy committed
5 6 7

This file is part of GNU Emacs.

8
GNU Emacs is free software: you can redistribute it and/or modify
Jim Blandy's avatar
Jim Blandy committed
9
it under the terms of the GNU General Public License as published by
10 11
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.
Jim Blandy's avatar
Jim Blandy committed
12 13 14 15 16 17 18

GNU Emacs 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
19
along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
Jim Blandy's avatar
Jim Blandy committed
20 21


22
#include <config.h>
23

24
#include "lisp.h"
Jim Blandy's avatar
Jim Blandy committed
25 26
#include "termchar.h"
#include "dispextern.h"
Jim Blandy's avatar
Jim Blandy committed
27
#include "frame.h"
28
#include "termhooks.h"
Jim Blandy's avatar
Jim Blandy committed
29 30 31 32 33

struct matrix_elt
  {
    /* Cost of outputting through this line
       if no insert/delete is done just above it.  */
34
    int writecost;
Jim Blandy's avatar
Jim Blandy committed
35 36
    /* Cost of outputting through this line
       if an insert is done just above it.  */
37
    int insertcost;
Jim Blandy's avatar
Jim Blandy committed
38 39
    /* Cost of outputting through this line
       if a delete is done just above it.  */
40
    int deletecost;
Jim Blandy's avatar
Jim Blandy committed
41 42
    /* Number of inserts so far in this run of inserts,
       for the cost in insertcost.  */
43
    int insertcount;
Jim Blandy's avatar
Jim Blandy committed
44 45
    /* Number of deletes so far in this run of deletes,
       for the cost in deletecost.  */
46
    int deletecount;
47 48
    /* Number of writes so far since the last insert
       or delete for the cost in writecost. */
49
    int writecount;
Jim Blandy's avatar
Jim Blandy committed
50 51
  };

52 53 54 55 56 57 58 59
static void do_direct_scrolling (struct frame *,
                                 struct glyph_matrix *,
                                 struct matrix_elt *,
                                 int, int);
static void do_scrolling (struct frame *,
                          struct glyph_matrix *,
                          struct matrix_elt *,
                          int, int);
Gerd Moellmann's avatar
Gerd Moellmann committed
60

Jim Blandy's avatar
Jim Blandy committed
61

62 63
/* Determine, in matrix[i,j], the cost of updating the first j old
   lines into the first i new lines using the general scrolling method.
Jim Blandy's avatar
Jim Blandy committed
64 65 66 67 68 69 70 71 72 73 74
   This involves using insert or delete somewhere if i != j.
   For each matrix elements, three kinds of costs are recorded:
   the smallest cost that ends with an insert, the smallest
   cost that ends with a delete, and the smallest cost that
   ends with neither one.  These are kept separate because
   on some terminals the cost of doing an insert varies
   depending on whether one was just done, etc.  */

/* draw_cost[VPOS] is the cost of outputting new line at VPOS.
   old_hash[VPOS] is the hash code of the old line at VPOS.
   new_hash[VPOS] is the hash code of the new line at VPOS.
Jim Blandy's avatar
Jim Blandy committed
75
   Note that these are not true frame vpos's, but relative
Jim Blandy's avatar
Jim Blandy committed
76 77 78 79
   to the place at which the first mismatch between old and
   new contents appears.  */

static void
Dmitry Antipov's avatar
Dmitry Antipov committed
80
calculate_scrolling (struct frame *frame,
81 82 83
		     /* matrix is of size window_size + 1 on each side.  */
		     struct matrix_elt *matrix,
		     int window_size, int lines_below,
84
		     int *draw_cost, unsigned *old_hash, unsigned *new_hash,
85
		     int free_at_end)
Jim Blandy's avatar
Jim Blandy committed
86
{
87 88 89 90
  int i, j;
  int frame_total_lines = FRAME_TOTAL_LINES (frame);
  struct matrix_elt *p, *p1;
  int cost, cost1;
Jim Blandy's avatar
Jim Blandy committed
91

92
  int lines_moved = window_size
93
    + (FRAME_SCROLL_REGION_OK (frame) ? 0 : lines_below);
Jim Blandy's avatar
Jim Blandy committed
94
  /* first_insert_cost[I] is the cost of doing the first insert-line
Gerd Moellmann's avatar
Gerd Moellmann committed
95
     at the i'th line of the lines we are considering,
Jim Blandy's avatar
Jim Blandy committed
96 97
     where I is origin 1 (as it is below).  */
  int *first_insert_cost
98
    = &FRAME_INSERT_COST (frame)[frame_total_lines - 1 - lines_moved];
Jim Blandy's avatar
Jim Blandy committed
99
  int *first_delete_cost
100
    = &FRAME_DELETE_COST (frame)[frame_total_lines - 1 - lines_moved];
Jim Blandy's avatar
Jim Blandy committed
101
  int *next_insert_cost
102
    = &FRAME_INSERTN_COST (frame)[frame_total_lines - 1 - lines_moved];
Jim Blandy's avatar
Jim Blandy committed
103
  int *next_delete_cost
104
    = &FRAME_DELETEN_COST (frame)[frame_total_lines - 1 - lines_moved];
Jim Blandy's avatar
Jim Blandy committed
105 106

  /* Discourage long scrolls on fast lines.
Jim Blandy's avatar
Jim Blandy committed
107
     Don't scroll nearly a full frame height unless it saves
Jim Blandy's avatar
Jim Blandy committed
108
     at least 1/4 second.  */
109 110
  int extra_cost
    = clip_to_bounds (1, baud_rate / (10 * 4) / frame_total_lines, INT_MAX / 2);
111

Jim Blandy's avatar
Jim Blandy committed
112 113
  /* initialize the top left corner of the matrix */
  matrix->writecost = 0;
114 115
  matrix->insertcost = SCROLL_INFINITY;
  matrix->deletecost = SCROLL_INFINITY;
Jim Blandy's avatar
Jim Blandy committed
116 117 118 119 120 121 122 123 124 125
  matrix->insertcount = 0;
  matrix->deletecount = 0;

  /* initialize the left edge of the matrix */
  cost = first_insert_cost[1] - next_insert_cost[1];
  for (i = 1; i <= window_size; i++)
    {
      p = matrix + i * (window_size + 1);
      cost += draw_cost[i] + next_insert_cost[i] + extra_cost;
      p->insertcost = cost;
126 127
      p->writecost = SCROLL_INFINITY;
      p->deletecost = SCROLL_INFINITY;
Jim Blandy's avatar
Jim Blandy committed
128 129 130 131 132 133 134 135 136 137
      p->insertcount = i;
      p->deletecount = 0;
    }

  /* initialize the top edge of the matrix */
  cost = first_delete_cost[1] - next_delete_cost[1];
  for (j = 1; j <= window_size; j++)
    {
      cost += next_delete_cost[j];
      matrix[j].deletecost = cost;
138 139
      matrix[j].writecost = SCROLL_INFINITY;
      matrix[j].insertcost = SCROLL_INFINITY;
Jim Blandy's avatar
Jim Blandy committed
140 141 142 143
      matrix[j].deletecount = j;
      matrix[j].insertcount = 0;
    }

Jim Blandy's avatar
Jim Blandy committed
144 145
  /* `i' represents the vpos among new frame contents.
     `j' represents the vpos among the old frame contents.  */
Jim Blandy's avatar
Jim Blandy committed
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
  p = matrix + window_size + 2;	/* matrix [1, 1] */
  for (i = 1; i <= window_size; i++, p++)
    for (j = 1; j <= window_size; j++, p++)
      {
	/* p contains the address of matrix [i, j] */

	/* First calculate the cost assuming we do
	   not insert or delete above this line.
	   That is, if we update through line i-1
	   based on old lines through j-1,
	   and then just change old line j to new line i.  */
	p1 = p - window_size - 2; /* matrix [i-1, j-1] */
	cost = p1->writecost;
	if (cost > p1->insertcost)
	  cost = p1->insertcost;
	if (cost > p1->deletecost)
	  cost = p1->deletecost;
	if (old_hash[j] != new_hash[i])
	  cost += draw_cost[i];
	p->writecost = cost;

	/* Calculate the cost if we do an insert-line
	   before outputting this line.
	   That is, we update through line i-1
	   based on old lines through j,
	   do an insert-line on line i,
	   and then output line i from scratch,
	   leaving old lines starting from j for reuse below.  */
	p1 = p - window_size - 1; /* matrix [i-1, j] */
	/* No need to think about doing a delete followed
	   immediately by an insert.  It cannot be as good
	   as not doing either of them.  */
	if (free_at_end == i)
	  {
	    cost = p1->writecost;
	    cost1 = p1->insertcost;
	  }
	else
	  {
	    cost = p1->writecost + first_insert_cost[i];
186
	    if (p1->insertcount > i)
187
	      emacs_abort ();
Jim Blandy's avatar
Jim Blandy committed
188 189 190 191
	    cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
	  }
	p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
	p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
192
	if (p->insertcount > i)
193
	  emacs_abort ();
Jim Blandy's avatar
Jim Blandy committed
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216

	/* Calculate the cost if we do a delete line after
	   outputting this line.
	   That is, we update through line i
	   based on old lines through j-1,
	   and throw away old line j.  */
	p1 = p - 1;		/* matrix [i, j-1] */
	/* No need to think about doing an insert followed
	   immediately by a delete.  */
	if (free_at_end == i)
	  {
	    cost = p1->writecost;
	    cost1 = p1->deletecost;
	  }
	else
	  {
	    cost = p1->writecost + first_delete_cost[i];
	    cost1 = p1->deletecost + next_delete_cost[i];
	  }
	p->deletecost = min (cost, cost1);
	p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
      }
}
Gerd Moellmann's avatar
Gerd Moellmann committed
217 218


Jim Blandy's avatar
Jim Blandy committed
219

Gerd Moellmann's avatar
Gerd Moellmann committed
220 221 222
/* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
   according to the costs in MATRIX, using the general scrolling
   method that is used if the terminal does not support the setting of
223
   scroll windows (scroll_region_ok == 0).
224 225

   WINDOW_SIZE is the number of lines being considered for scrolling
Gerd Moellmann's avatar
Gerd Moellmann committed
226 227 228
   and UNCHANGED_AT_TOP is the vpos of the first line being
   considered.  These two arguments can specify any contiguous range
   of lines.  */
229

Jim Blandy's avatar
Jim Blandy committed
230
static void
231 232 233
do_scrolling (struct frame *frame, struct glyph_matrix *current_matrix,
              struct matrix_elt *matrix, int window_size,
              int unchanged_at_top)
Jim Blandy's avatar
Jim Blandy committed
234
{
Gerd Moellmann's avatar
Gerd Moellmann committed
235 236
  struct matrix_elt *p;
  int i, j, k;
237
  USE_SAFE_ALLOCA;
Gerd Moellmann's avatar
Gerd Moellmann committed
238

239 240
  /* True if we have set a terminal window with set_terminal_window.  */
  bool terminal_window_p = 0;
Gerd Moellmann's avatar
Gerd Moellmann committed
241 242 243

  /* A queue for line insertions to be done.  */
  struct queue { int count, pos; };
244 245
  struct queue *queue_start;
  SAFE_NALLOCA (queue_start, 1, current_matrix->nrows);
Gerd Moellmann's avatar
Gerd Moellmann committed
246
  struct queue *queue = queue_start;
247

248 249 250
  char *retained_p = SAFE_ALLOCA (window_size);
  int *copy_from;
  SAFE_NALLOCA (copy_from, 1, window_size);
Gerd Moellmann's avatar
Gerd Moellmann committed
251 252

  /* Zero means line is empty.  */
253
  memset (retained_p, 0, window_size * sizeof (char));
Gerd Moellmann's avatar
Gerd Moellmann committed
254 255 256
  for (k = 0; k < window_size; ++k)
    copy_from[k] = -1;

257
#ifdef GLYPH_DEBUG
258
# define CHECK_BOUNDS							\
Gerd Moellmann's avatar
Gerd Moellmann committed
259 260
  do									\
    {									\
Paul Eggert's avatar
Paul Eggert committed
261 262
      int ck;								\
      for (ck = 0; ck < window_size; ++ck)				\
263
	eassert (copy_from[ck] == -1					\
Paul Eggert's avatar
Paul Eggert committed
264
		 || (copy_from[ck] >= 0 && copy_from[ck] < window_size)); \
Gerd Moellmann's avatar
Gerd Moellmann committed
265 266
    }									\
  while (0);
267
#endif
Gerd Moellmann's avatar
Gerd Moellmann committed
268 269 270

  /* When j is advanced, this corresponds to deleted lines.
     When i is advanced, this corresponds to inserted lines.  */
Jim Blandy's avatar
Jim Blandy committed
271 272 273 274
  i = j = window_size;
  while (i > 0 || j > 0)
    {
      p = matrix + i * (window_size + 1) + j;
275

Gerd Moellmann's avatar
Gerd Moellmann committed
276
      if (p->insertcost < p->writecost && p->insertcost < p->deletecost)
Jim Blandy's avatar
Jim Blandy committed
277
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
278 279 280 281 282 283 284 285
	  /* Insert should be done at vpos i-1, plus maybe some before.
	     Queue the screen operation to be performed.  */
	  queue->count = p->insertcount;
	  queue->pos = i + unchanged_at_top - p->insertcount;
	  ++queue;

	  /* By incrementing I, we leave room in the result rows
	     for the empty rows opened up.  */
Jim Blandy's avatar
Jim Blandy committed
286 287 288 289
	  i -= p->insertcount;
	}
      else if (p->deletecost < p->writecost)
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
290 291 292 293
	  /* Old line at vpos j-1, and maybe some before it, should be
	     deleted.  By decrementing J, we skip some lines in the
	     temp_rows which is equivalent to omitting these lines in
	     the result rows, thus deleting them.  */
Jim Blandy's avatar
Jim Blandy committed
294
	  j -= p->deletecount;
Gerd Moellmann's avatar
Gerd Moellmann committed
295 296 297

	  /* Set the terminal window, if not done already.  */
 	  if (! terminal_window_p)
Jim Blandy's avatar
Jim Blandy committed
298
	    {
Karoly Lorentey's avatar
Karoly Lorentey committed
299
	      set_terminal_window (frame, window_size + unchanged_at_top);
Gerd Moellmann's avatar
Gerd Moellmann committed
300
	      terminal_window_p = 1;
Jim Blandy's avatar
Jim Blandy committed
301
	    }
Gerd Moellmann's avatar
Gerd Moellmann committed
302 303

	  /* Delete lines on the terminal.  */
Karoly Lorentey's avatar
Karoly Lorentey committed
304
	  ins_del_lines (frame, j + unchanged_at_top, - p->deletecount);
Jim Blandy's avatar
Jim Blandy committed
305 306 307
	}
      else
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
308 309
	  /* Best thing done here is no insert or delete, i.e. a write.  */
	  --i, --j;
310 311
	  eassert (i >= 0 && i < window_size);
	  eassert (j >= 0 && j < window_size);
Gerd Moellmann's avatar
Gerd Moellmann committed
312 313 314
	  copy_from[i] = j;
	  retained_p[j] = 1;

315
#ifdef GLYPH_DEBUG
316
	  CHECK_BOUNDS;
Gerd Moellmann's avatar
Gerd Moellmann committed
317
#endif
Jim Blandy's avatar
Jim Blandy committed
318 319 320
	}
    }

Gerd Moellmann's avatar
Gerd Moellmann committed
321 322
  /* Now do all insertions queued above.  */
  if (queue > queue_start)
Jim Blandy's avatar
Jim Blandy committed
323
    {
Gerd Moellmann's avatar
Gerd Moellmann committed
324
      int next = -1;
Jim Blandy's avatar
Jim Blandy committed
325

Gerd Moellmann's avatar
Gerd Moellmann committed
326 327 328
      /* Set the terminal window if not yet done.  */
      if (!terminal_window_p)
	{
Karoly Lorentey's avatar
Karoly Lorentey committed
329
	  set_terminal_window (frame, window_size + unchanged_at_top);
Gerd Moellmann's avatar
Gerd Moellmann committed
330 331
	  terminal_window_p = 1;
	}
Jim Blandy's avatar
Jim Blandy committed
332

Gerd Moellmann's avatar
Gerd Moellmann committed
333
      do
Jim Blandy's avatar
Jim Blandy committed
334
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
335 336 337
	  --queue;

	  /* Do the deletion on the terminal.  */
Karoly Lorentey's avatar
Karoly Lorentey committed
338
	  ins_del_lines (frame, queue->pos, queue->count);
Gerd Moellmann's avatar
Gerd Moellmann committed
339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354

	  /* All lines in the range deleted become empty in the glyph
	     matrix.  Assign to them glyph rows that are not retained.
	     K is the starting position of the deleted range relative
	     to the window we are working in.  */
	  k = queue->pos - unchanged_at_top;
	  for (j = 0; j < queue->count; ++j)
	    {
	      /* Find the next row not retained.  */
	      while (retained_p[++next])
		;

	      /* Record that this row is to be used for the empty
		 glyph row j.  */
	      copy_from[k + j] = next;
	    }
Jim Blandy's avatar
Jim Blandy committed
355
	}
Gerd Moellmann's avatar
Gerd Moellmann committed
356
      while (queue > queue_start);
357

Jim Blandy's avatar
Jim Blandy committed
358 359
    }

Gerd Moellmann's avatar
Gerd Moellmann committed
360
  for (k = 0; k < window_size; ++k)
361
    eassert (copy_from[k] >= 0 && copy_from[k] < window_size);
Gerd Moellmann's avatar
Gerd Moellmann committed
362 363 364 365 366

  /* Perform the row swizzling.  */
  mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
		       copy_from, retained_p);

367
  /* Some sanity checks if GLYPH_DEBUG is defined.  */
Gerd Moellmann's avatar
Gerd Moellmann committed
368
  CHECK_MATRIX (current_matrix);
369

Gerd Moellmann's avatar
Gerd Moellmann committed
370
  if (terminal_window_p)
Karoly Lorentey's avatar
Karoly Lorentey committed
371
    set_terminal_window (frame, 0);
372
  SAFE_FREE ();
Jim Blandy's avatar
Jim Blandy committed
373
}
Gerd Moellmann's avatar
Gerd Moellmann committed
374

Jim Blandy's avatar
Jim Blandy committed
375

376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416
/* Determine, in matrix[i,j], the cost of updating the first j
   old lines into the first i new lines using the direct
   scrolling method.  When the old line and the new line have
   different hash codes, the calculated cost of updating old
   line j into new line i includes the cost of outputting new
   line i, and if i != j, the cost of outputting the old line j
   is also included, as a penalty for moving the line and then
   erasing it.  In addition, the cost of updating a sequence of
   lines with constant i - j includes the cost of scrolling the
   old lines into their new positions, unless i == j.  Scrolling
   is achieved by setting the screen window to avoid affecting
   other lines below, and inserting or deleting lines at the top
   of the scrolled region.  The cost of scrolling a sequence of
   lines includes the fixed cost of specifying a scroll region,
   plus a variable cost which can depend upon the number of lines
   involved and the distance by which they are scrolled, and an
   extra cost to discourage long scrolls.

   As reflected in the matrix, an insert or delete does not
   correspond directly to the insertion or deletion which is
   used in scrolling lines.  An insert means that the value of i
   has increased without a corresponding increase in the value
   of j.  A delete means that the value of j has increased
   without a corresponding increase in the value of i.  A write
   means that i and j are both increased by the same amount, and
   that the old lines will be moved to their new positions.

   An insert following a delete is allowed only if i > j.
   A delete following an insert is allowed only if i < j.
   These restrictions ensure that the new lines in an insert
   will always be blank as an effect of the neighboring writes.
   Thus the calculated cost of an insert is simply the cost of
   outputting the new line contents.  The direct cost of a
   delete is zero.  Inserts and deletes indirectly affect the
   total cost through their influence on subsequent writes. */

/* The vectors draw_cost, old_hash, and new_hash have the same
   meanings here as in calculate_scrolling, and old_draw_cost
   is the equivalent of draw_cost for the old line contents */

static void
Dmitry Antipov's avatar
Dmitry Antipov committed
417
calculate_direct_scrolling (struct frame *frame,
418 419 420 421
			    /* matrix is of size window_size + 1 on each side.  */
			    struct matrix_elt *matrix,
			    int window_size, int lines_below,
			    int *draw_cost, int *old_draw_cost,
422
			    unsigned *old_hash, unsigned *new_hash,
423
			    int free_at_end)
424
{
425 426 427 428
  int i, j;
  int frame_total_lines = FRAME_TOTAL_LINES (frame);
  struct matrix_elt *p, *p1;
  int cost, cost1, delta;
429 430 431 432

  /* first_insert_cost[-I] is the cost of doing the first insert-line
     at a position I lines above the bottom line in the scroll window. */
  int *first_insert_cost
433
    = &FRAME_INSERT_COST (frame)[frame_total_lines - 1];
434
  int *first_delete_cost
435
    = &FRAME_DELETE_COST (frame)[frame_total_lines - 1];
436
  int *next_insert_cost
437
    = &FRAME_INSERTN_COST (frame)[frame_total_lines - 1];
438
  int *next_delete_cost
439
    = &FRAME_DELETEN_COST (frame)[frame_total_lines - 1];
440 441 442 443 444 445

  int scroll_overhead;

  /* Discourage long scrolls on fast lines.
     Don't scroll nearly a full frame height unless it saves
     at least 1/4 second.  */
446 447
  int extra_cost
    = clip_to_bounds (1, baud_rate / (10 * 4) / frame_total_lines, INT_MAX / 2);
448

449
  /* Overhead of setting the scroll window, plus the extra
450 451
     cost of scrolling by a distance of one.  The extra cost is
     added once for consistency with the cost vectors */
452
  scroll_overhead
453
    = FRAME_SCROLL_REGION_COST (frame) + extra_cost;
454 455 456

  /* initialize the top left corner of the matrix */
  matrix->writecost = 0;
457 458
  matrix->insertcost = SCROLL_INFINITY;
  matrix->deletecost = SCROLL_INFINITY;
459 460 461 462 463 464 465 466 467 468 469
  matrix->writecount = 0;
  matrix->insertcount = 0;
  matrix->deletecount = 0;

  /* initialize the left edge of the matrix */
  cost = 0;
  for (i = 1; i <= window_size; i++)
    {
      p = matrix + i * (window_size + 1);
      cost += draw_cost[i];
      p->insertcost = cost;
470 471
      p->writecost = SCROLL_INFINITY;
      p->deletecost = SCROLL_INFINITY;
472 473 474 475 476 477 478 479 480
      p->insertcount = i;
      p->writecount = 0;
      p->deletecount = 0;
    }

  /* initialize the top edge of the matrix */
  for (j = 1; j <= window_size; j++)
    {
      matrix[j].deletecost = 0;
481 482
      matrix[j].writecost = SCROLL_INFINITY;
      matrix[j].insertcost = SCROLL_INFINITY;
483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548
      matrix[j].deletecount = j;
      matrix[j].writecount = 0;
      matrix[j].insertcount = 0;
    }

  /* `i' represents the vpos among new frame contents.
     `j' represents the vpos among the old frame contents.  */
  p = matrix + window_size + 2;	/* matrix [1, 1] */

  for (i = 1; i <= window_size; i++, p++)
    for (j = 1; j <= window_size; j++, p++)
      {
	/* p contains the address of matrix [i, j] */

	/* First calculate the cost assuming we do
	   not insert or delete above this line.
	   That is, if we update through line i-1
	   based on old lines through j-1,
	   and then just change old line j to new line i.

	   Depending on which choice gives the lower cost,
	   this usually involves either scrolling a single line
	   or extending a sequence of scrolled lines, but
	   when i == j, no scrolling is required. */
	p1 = p - window_size - 2; /* matrix [i-1, j-1] */
	cost = p1->insertcost;
	if (cost > p1->deletecost)
	  cost = p1->deletecost;
	cost1 = p1->writecost;
	if (i == j)
	  {
	    if (cost > cost1)
	      {
		cost = cost1;
		p->writecount = p1->writecount + 1;
	      }
	    else
	      p->writecount = 1;
	    if (old_hash[j] != new_hash[i])
	      {
		cost += draw_cost[i];
	      }
	  }
	else
	  {
	    if (i > j)
	      {
		delta = i - j;

		/* The cost added here for scrolling the first line by
		   a distance N includes the overhead of setting the
		   scroll window, the cost of inserting N lines at a
		   position N lines above the bottom line of the window,
		   and an extra cost which is proportional to N. */
		cost += scroll_overhead + first_insert_cost[-delta] +
		  (delta-1) * (next_insert_cost[-delta] + extra_cost);

		/* In the most general case, the insertion overhead and
		   the multiply factor can grow linearly as the distance
		   from the bottom of the window increases.  The incremental
		   cost of scrolling an additional line depends upon the
		   rate of change of these two parameters.  Each of these
		   growth rates can be determined by a simple difference.
		   To reduce the cumulative effects of rounding error, we
		   vary the position at which the difference is computed. */
		cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
549
		  (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]);
550 551 552 553 554 555 556
	      }
	    else
	      {
		delta = j - i;
		cost += scroll_overhead + first_delete_cost[-delta] +
		  (delta-1) * (next_delete_cost[-delta] + extra_cost);
		cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
557
		  (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]);
558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615
	      }
	    if (cost1 < cost)
	      {
		cost = cost1;
		p->writecount = p1->writecount + 1;
	      }
	    else
	      p->writecount = 1;
	    if (old_hash[j] != new_hash[i])
	      {
		cost += draw_cost[i] + old_draw_cost[j];
	      }
	  }
	p->writecost = cost;

	/* Calculate the cost if we do an insert-line
	   before outputting this line.
	   That is, we update through line i-1
	   based on old lines through j,
	   do an insert-line on line i,
	   and then output line i from scratch,
	   leaving old lines starting from j for reuse below.  */
	p1 = p - window_size - 1; /* matrix [i-1, j] */
	cost = p1->writecost;
	/* If i > j, an insert is allowed after a delete. */
	if (i > j && p1->deletecost < cost)
	  cost = p1->deletecost;
	if (p1->insertcost <= cost)
	  {
	    cost = p1->insertcost;
	    p->insertcount = p1->insertcount + 1;
	  }
	else
	  p->insertcount = 1;
	cost += draw_cost[i];
	p->insertcost = cost;

	/* Calculate the cost if we do a delete line after
	   outputting this line.
	   That is, we update through line i
	   based on old lines through j-1,
	   and throw away old line j.  */
	p1 = p - 1;		/* matrix [i, j-1] */
	cost = p1->writecost;
	/* If i < j, a delete is allowed after an insert. */
	if (i < j && p1->insertcost < cost)
	  cost = p1->insertcost;
	cost1 = p1->deletecost;
	if (p1->deletecost <= cost)
	  {
	    cost = p1->deletecost;
	    p->deletecount = p1->deletecount + 1;
	  }
	else
	  p->deletecount = 1;
	p->deletecost = cost;
      }
}
Gerd Moellmann's avatar
Gerd Moellmann committed
616 617


618

Gerd Moellmann's avatar
Gerd Moellmann committed
619 620 621 622
/* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
   according to the costs in MATRIX, using the direct scrolling method
   which is used when the terminal supports setting a scroll window
   (scroll_region_ok).
623 624

   WINDOW_SIZE is the number of lines being considered for scrolling
Gerd Moellmann's avatar
Gerd Moellmann committed
625 626 627
   and UNCHANGED_AT_TOP is the vpos of the first line being
   considered.  These two arguments can specify any contiguous range
   of lines.
628

629 630 631
   In the direct scrolling method, a new scroll window is selected
   before each insertion or deletion, so that groups of lines can be
   scrolled directly to their final vertical positions.  This method
Gerd Moellmann's avatar
Gerd Moellmann committed
632 633
   is described in more detail in calculate_direct_scrolling, where
   the cost matrix for this approach is constructed. */
634 635

static void
636 637 638
do_direct_scrolling (struct frame *frame, struct glyph_matrix *current_matrix,
		     struct matrix_elt *cost_matrix, int window_size,
		     int unchanged_at_top)
639
{
Gerd Moellmann's avatar
Gerd Moellmann committed
640 641
  struct matrix_elt *p;
  int i, j;
642
  USE_SAFE_ALLOCA;
643

Gerd Moellmann's avatar
Gerd Moellmann committed
644 645
  /* A queue of deletions and insertions to be performed.  */
  struct alt_queue { int count, pos, window; };
646 647
  struct alt_queue *queue_start;
  SAFE_NALLOCA (queue_start, 1, window_size);
Gerd Moellmann's avatar
Gerd Moellmann committed
648
  struct alt_queue *queue = queue_start;
649

650 651
  /* True if a terminal window has been set with set_terminal_window.  */
  bool terminal_window_p = 0;
652

653 654
  /* If true, a write has been selected, allowing either an insert or a
     delete to be selected next.  If false, a delete cannot be selected
Gerd Moellmann's avatar
Gerd Moellmann committed
655 656 657 658
     unless j < i, and an insert cannot be selected unless i < j.
     This corresponds to a similar restriction (with the ordering
     reversed) in calculate_direct_scrolling, which is intended to
     ensure that lines marked as inserted will be blank. */
659
  bool write_follows_p = 1;
Gerd Moellmann's avatar
Gerd Moellmann committed
660 661

  /* For each row in the new matrix what row of the old matrix it is.  */
662 663
  int *copy_from;
  SAFE_NALLOCA (copy_from, 1, window_size);
Gerd Moellmann's avatar
Gerd Moellmann committed
664 665 666

  /* Non-zero for each row in the new matrix that is retained from the
     old matrix.  Lines not retained are empty.  */
667
  char *retained_p = SAFE_ALLOCA (window_size);
Gerd Moellmann's avatar
Gerd Moellmann committed
668

669
  memset (retained_p, 0, window_size * sizeof (char));
Gerd Moellmann's avatar
Gerd Moellmann committed
670 671 672 673 674 675 676 677 678 679 680 681 682 683 684

  /* Perform some sanity checks when GLYPH_DEBUG is on.  */
  CHECK_MATRIX (current_matrix);

  /* We are working on the line range UNCHANGED_AT_TOP ...
     UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX.
     We step through lines in this range from the end to the start.  I
     is an index into new lines, j an index into old lines.  The cost
     matrix determines what to do for ranges of indices.

     If i is decremented without also decrementing j, this corresponds
     to inserting empty lines in the result.  If j is decremented
     without also decrementing i, this corresponds to omitting these
     lines in the new rows, i.e. rows are deleted.  */
  i = j = window_size;
685

686 687
  while (i > 0 || j > 0)
    {
Gerd Moellmann's avatar
Gerd Moellmann committed
688
      p = cost_matrix + i * (window_size + 1) + j;
689

Gerd Moellmann's avatar
Gerd Moellmann committed
690 691 692
      if (p->insertcost < p->writecost
	  && p->insertcost < p->deletecost
	  && (write_follows_p || i < j))
693
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
694 695 696 697 698 699 700
	  /* Insert is cheaper than deleting or writing lines.  Leave
	     a hole in the result display that will be filled with
	     empty lines when the queue is emptied.  */
	  queue->count = 0;
	  queue->window = i;
	  queue->pos = i - p->insertcount;
	  ++queue;
701

702
	  i -= p->insertcount;
Gerd Moellmann's avatar
Gerd Moellmann committed
703
	  write_follows_p = 0;
704
	}
Gerd Moellmann's avatar
Gerd Moellmann committed
705 706
      else if (p->deletecost < p->writecost
	       && (write_follows_p || i > j))
707
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
708 709 710
	  /* Deleting lines is cheaper.  By decrementing J, omit
	     deletecount lines from the original.  */
	  write_follows_p = 0;
711 712 713 714
	  j -= p->deletecount;
	}
      else
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
715 716 717 718 719
	  /* One or more lines should be written.  In the direct
	     scrolling method we do this by scrolling the lines to the
	     place they belong.  */
	  int n_to_write = p->writecount;
	  write_follows_p = 1;
720
	  eassert (n_to_write > 0);
Gerd Moellmann's avatar
Gerd Moellmann committed
721

722 723
	  if (i > j)
	    {
Gerd Moellmann's avatar
Gerd Moellmann committed
724
	      /* Immediately insert lines */
Karoly Lorentey's avatar
Karoly Lorentey committed
725
	      set_terminal_window (frame, i + unchanged_at_top);
Gerd Moellmann's avatar
Gerd Moellmann committed
726
	      terminal_window_p = 1;
Karoly Lorentey's avatar
Karoly Lorentey committed
727
	      ins_del_lines (frame, j - n_to_write + unchanged_at_top, i - j);
728 729 730
	    }
	  else if (i < j)
	    {
Gerd Moellmann's avatar
Gerd Moellmann committed
731 732 733 734 735
	      /* Queue the deletion of a group of lines */
	      queue->pos = i - n_to_write + unchanged_at_top;
	      queue->window = j + unchanged_at_top;
	      queue->count = i - j;
	      ++queue;
736 737
	    }

Gerd Moellmann's avatar
Gerd Moellmann committed
738
	  while (n_to_write > 0)
739
	    {
Gerd Moellmann's avatar
Gerd Moellmann committed
740 741 742
	      --i, --j, --n_to_write;
	      copy_from[i] = j;
	      retained_p[j] = 1;
743 744 745 746
	    }
	}
    }

Gerd Moellmann's avatar
Gerd Moellmann committed
747 748
  /* Do queued operations.  */
  if (queue > queue_start)
749
    {
Gerd Moellmann's avatar
Gerd Moellmann committed
750 751 752
      int next = -1;

      do
753
	{
Gerd Moellmann's avatar
Gerd Moellmann committed
754 755 756
	  --queue;
	  if (queue->count)
	    {
Karoly Lorentey's avatar
Karoly Lorentey committed
757
	      set_terminal_window (frame, queue->window);
Gerd Moellmann's avatar
Gerd Moellmann committed
758
	      terminal_window_p = 1;
Karoly Lorentey's avatar
Karoly Lorentey committed
759
	      ins_del_lines (frame, queue->pos, queue->count);
Gerd Moellmann's avatar
Gerd Moellmann committed
760 761
	    }
	  else
762
	    {
Gerd Moellmann's avatar
Gerd Moellmann committed
763 764 765 766 767 768
	      for (j = queue->window - 1; j >= queue->pos; --j)
		{
		  while (retained_p[++next])
		    ;
		  copy_from[j] = next;
		}
769 770
	    }
	}
Gerd Moellmann's avatar
Gerd Moellmann committed
771
      while (queue > queue_start);
772 773
    }

Gerd Moellmann's avatar
Gerd Moellmann committed
774 775 776 777 778 779 780 781
  /* Now, for each row I in the range of rows we are working on,
     copy_from[i] gives the original line to copy to I, and
     retained_p[copy_from[i]] is zero if line I in the new display is
     empty.  */
  mirrored_line_dance (current_matrix, unchanged_at_top, window_size,
		       copy_from, retained_p);

  if (terminal_window_p)
Karoly Lorentey's avatar
Karoly Lorentey committed
782
    set_terminal_window (frame, 0);
783
  SAFE_FREE ();
784
}
Gerd Moellmann's avatar
Gerd Moellmann committed
785 786


787

Jim Blandy's avatar
Jim Blandy committed
788
void
Dmitry Antipov's avatar
Dmitry Antipov committed
789
scrolling_1 (struct frame *frame, int window_size, int unchanged_at_top,
790
	     int unchanged_at_bottom, int *draw_cost, int *old_draw_cost,
791
	     unsigned *old_hash, unsigned *new_hash, int free_at_end)
Jim Blandy's avatar
Jim Blandy committed
792
{
793 794 795
  USE_SAFE_ALLOCA;
  struct matrix_elt *matrix;
  SAFE_NALLOCA (matrix, window_size + 1, window_size + 1);
Jim Blandy's avatar
Jim Blandy committed
796

797
  if (FRAME_SCROLL_REGION_OK (frame))
798 799 800
    {
      calculate_direct_scrolling (frame, matrix, window_size,
				  unchanged_at_bottom,
801
				  draw_cost, old_draw_cost,
802
				  old_hash, new_hash, free_at_end);
Karoly Lorentey's avatar
Karoly Lorentey committed
803
      do_direct_scrolling (frame, frame->current_matrix,
Gerd Moellmann's avatar
Gerd Moellmann committed
804
			   matrix, window_size, unchanged_at_top);
805 806 807 808 809 810
    }
  else
    {
      calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
			   draw_cost, old_hash, new_hash,
			   free_at_end);
Karoly Lorentey's avatar
Karoly Lorentey committed
811 812
      do_scrolling (frame,
                    frame->current_matrix, matrix, window_size,
Gerd Moellmann's avatar
Gerd Moellmann committed
813
		    unchanged_at_top);
814
    }
815 816

  SAFE_FREE ();
Jim Blandy's avatar
Jim Blandy committed
817
}
Gerd Moellmann's avatar
Gerd Moellmann committed
818 819


Jim Blandy's avatar
Jim Blandy committed
820

Gerd Moellmann's avatar
Gerd Moellmann committed
821 822 823 824 825
/* Return number of lines in common between current and desired frame
   contents described to us only as vectors of hash codes OLDHASH and
   NEWHASH.  Consider only vpos range START to END (not including
   END).  Ignore short lines on the assumption that avoiding redrawing
   such a line will have little weight.  */
Jim Blandy's avatar
Jim Blandy committed
826 827

int
828
scrolling_max_lines_saved (int start, int end,
829
                           unsigned *oldhash, unsigned *newhash,
830
                           int *cost)
Jim Blandy's avatar
Jim Blandy committed
831
{
832 833 834 835 836
  enum { LOG2_NLINES = 9 };
  enum { NLINES = 1 << LOG2_NLINES };
  struct { unsigned hash; int count; } lines[NLINES];
  int i, h;
  int matchcount = 0;
Jim Blandy's avatar
Jim Blandy committed
837 838 839 840 841 842 843 844 845 846 847
  int avg_length = 0;
  int threshold;

  /* Compute a threshold which is 1/4 of average length of these lines.  */

  for (i = start; i < end; i++)
    avg_length += cost[i];

  avg_length /= end - start;
  threshold = avg_length / 4;

848
  memset (lines, 0, sizeof lines);
Jim Blandy's avatar
Jim Blandy committed
849

Gerd Moellmann's avatar
Gerd Moellmann committed
850 851 852
  /* Put new lines' hash codes in hash table.  Ignore lines shorter
     than the threshold.  Thus, if the lines that are in common are
     mainly the ones that are short, they won't count.  */
Jim Blandy's avatar
Jim Blandy committed
853 854 855 856
  for (i = start; i < end; i++)
    {
      if (cost[i] > threshold)
	{
857
	  h = newhash[i] & (NLINES - 1);
Jim Blandy's avatar
Jim Blandy committed
858 859 860 861 862
	  lines[h].hash = newhash[i];
	  lines[h].count++;
	}
    }

Gerd Moellmann's avatar
Gerd Moellmann committed
863 864
  /* Look up old line hash codes in the hash table.  Count number of
     matches between old lines and new.  */
Jim Blandy's avatar
Jim Blandy committed
865 866
  for (i = start; i < end; i++)
    {
867
      h = oldhash[i] & (NLINES - 1);
Jim Blandy's avatar
Jim Blandy committed
868 869 870 871 872 873 874 875 876 877 878 879 880 881 882
      if (oldhash[i] == lines[h].hash)
	{
	  matchcount++;
	  if (--lines[h].count == 0)
	    lines[h].hash = 0;
	}
    }

  return matchcount;
}

/* Calculate the line insertion/deletion
   overhead and multiply factor values */

static void
Dmitry Antipov's avatar
Dmitry Antipov committed
883
line_ins_del (struct frame *frame, int ov1, int pf1, int ovn, int pfn,
884
              int *ov, int *mf)
Jim Blandy's avatar
Jim Blandy committed
885
{
886 887 888 889
  int i;
  int frame_total_lines = FRAME_TOTAL_LINES (frame);
  int insert_overhead = ov1 * 10;
  int next_insert_cost = ovn * 10;
Jim Blandy's avatar
Jim Blandy committed
890

891
  for (i = frame_total_lines - 1; i >= 0; i--)
Jim Blandy's avatar
Jim Blandy committed
892
    {
Jim Blandy's avatar
Jim Blandy committed
893
      mf[i] = next_insert_cost / 10;
Jim Blandy's avatar
Jim Blandy committed
894
      next_insert_cost += pfn;
Jim Blandy's avatar
Jim Blandy committed
895
      ov[i] = (insert_overhead + next_insert_cost) / 10;
Jim Blandy's avatar
Jim Blandy committed
896 897 898 899 900
      insert_overhead += pf1;
    }
}

static void
Dmitry Antipov's avatar
Dmitry Antipov committed
901
ins_del_costs (struct frame *frame,
902 903
	       const char *one_line_string, const char *multi_string,
	       const char *setup_string, const char *cleanup_string,
904 905
	       int *costvec, int *ncostvec,
	       int coefficient)
Jim Blandy's avatar
Jim Blandy committed
906 907
{
  if (multi_string)
Jim Blandy's avatar
Jim Blandy committed
908
    line_ins_del (frame,
Jim Blandy's avatar
Jim Blandy committed
909 910 911 912
		  string_cost (multi_string) * coefficient,
		  per_line_cost (multi_string) * coefficient,
		  0, 0, costvec, ncostvec);
  else if (one_line_string)
Jim Blandy's avatar
Jim Blandy committed
913
    line_ins_del (frame,
Jim Blandy's avatar
Jim Blandy committed
914 915 916 917 918
		  string_cost (setup_string) + string_cost (cleanup_string), 0,
		  string_cost (one_line_string),
		  per_line_cost (one_line_string),
		  costvec, ncostvec);
  else
Jim Blandy's avatar
Jim Blandy committed
919
    line_ins_del (frame,
Jim Blandy's avatar
Jim Blandy committed
920 921 922 923 924 925 926
		  9999, 0, 9999, 0,
		  costvec, ncostvec);
}

/* Calculate the insert and delete line costs.
   Note that this is done even when running with a window system
   because we want to know how long scrolling takes (and avoid it).
Jim Blandy's avatar
Jim Blandy committed
927
   This must be redone whenever the frame height changes.
Jim Blandy's avatar
Jim Blandy committed
928 929 930 931 932 933 934 935

   We keep the ID costs in a precomputed array based on the position
   at which the I or D is performed.  Also, there are two kinds of ID
   costs: the "once-only" and the "repeated".  This is to handle both
   those terminals that are able to insert N lines at a time (once-
   only) and those that must repeatedly insert one line.

   The cost to insert N lines at line L is
936 937
	    [tt.t_ILov  + (frame_total_lines + 1 - L) * tt.t_ILpf] +
	N * [tt.t_ILnov + (frame_total_lines + 1 - L) * tt.t_ILnpf]
Jim Blandy's avatar
Jim Blandy committed
938 939 940

   ILov represents the basic insert line overhead.  ILpf is the padding
   required to allow the terminal time to move a line: insertion at line
941
   L changes (frame_total_lines + 1 - L) lines.
Jim Blandy's avatar
Jim Blandy committed
942 943 944 945

   The first bracketed expression above is the overhead; the second is
   the multiply factor.  Both are dependent only on the position at
   which the insert is performed.  We store the overhead in
Jim Blandy's avatar
Jim Blandy committed
946 947
   FRAME_INSERT_COST (frame) and the multiply factor in
   FRAME_INSERTN_COST (frame).  Note however that any insertion
Jim Blandy's avatar
Jim Blandy committed
948
   must include at least one multiply factor.  Rather than compute this
Jim Blandy's avatar
Jim Blandy committed
949 950
   as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
   we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
Jim Blandy's avatar
Jim Blandy committed
951 952 953 954 955
   This is reasonable because of the particular algorithm used in calcM.

   Deletion is essentially the same as insertion.
 */

Andreas Schwab's avatar
Andreas Schwab committed
956
void
Dmitry Antipov's avatar
Dmitry Antipov committed
957
do_line_insertion_deletion_costs (struct frame *frame,
958 959 960 961 962 963
				  const char *ins_line_string,
				  const char *multi_ins_string,
				  const char *del_line_string,
				  const char *multi_del_string,
				  const char *setup_string,
				  const char *cleanup_string,
964
				  int coefficient)
Jim Blandy's avatar
Jim Blandy committed
965
{
966
  int frame_total_lines = FRAME_TOTAL_LINES (frame);
967
  FRAME_INSERT_COST (frame) =
968
    xnrealloc (FRAME_INSERT_COST (frame), frame_total_lines, sizeof (int));
969
  FRAME_DELETEN_COST (frame) =
970
    xnrealloc (FRAME_DELETEN_COST (frame), frame_total_lines, sizeof (int));
971
  FRAME_INSERTN_COST (frame) =
972
    xnrealloc (FRAME_INSERTN_COST (frame), frame_total_lines, sizeof (int));
973
  FRAME_DELETE_COST (frame) =
974
    xnrealloc (FRAME_DELETE_COST (frame), frame_total_lines, sizeof (int));
Jim Blandy's avatar
Jim Blandy committed
975

Jim Blandy's avatar
Jim Blandy committed
976
  ins_del_costs (frame,
Jim Blandy's avatar
Jim Blandy committed
977 978
		 ins_line_string, multi_ins_string,
		 setup_string, cleanup_string,
Jim Blandy's avatar
Jim Blandy committed
979
		 FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
Jim Blandy's avatar
Jim Blandy committed
980
		 coefficient);
Jim Blandy's avatar
Jim Blandy committed
981
  ins_del_costs (frame,
Jim Blandy's avatar
Jim Blandy committed
982 983
		 del_line_string, multi_del_string,
		 setup_string, cleanup_string,
984
		 FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame),
Jim Blandy's avatar
Jim Blandy committed
985 986
		 coefficient);
}