1 /* Updating of data structures for redisplay.
   2    Copyright (C) 1985, 1986, 1987, 1988, 1993, 1994, 1995,
   3                  1997, 1998, 1999, 2000, 2001, 2002, 2003,
   4                  2004, 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
   5 
   6 This file is part of GNU Emacs.
   7 
   8 GNU Emacs is free software: you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation, either version 3 of the License, or
  11 (at your option) any later version.
  12 
  13 GNU Emacs is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17 
  18 You should have received a copy of the GNU General Public License
  19 along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
  20 
  21 #include <config.h>
  22 #include <signal.h>
  23 #include <stdio.h>
  24 #include <ctype.h>
  25 #include <setjmp.h>
  26 
  27 #ifdef HAVE_UNISTD_H
  28 #include <unistd.h>
  29 #endif
  30 
  31 #include "lisp.h"
  32 #include "termchar.h"
  33 #include "termopts.h"
  34 /* cm.h must come after dispextern.h on Windows.  */
  35 #include "dispextern.h"
  36 #include "cm.h"
  37 #include "buffer.h"
  38 #include "character.h"
  39 #include "keyboard.h"
  40 #include "frame.h"
  41 #include "termhooks.h"
  42 #include "window.h"
  43 #include "commands.h"
  44 #include "disptab.h"
  45 #include "indent.h"
  46 #include "intervals.h"
  47 #include "blockinput.h"
  48 #include "process.h"
  49 
  50 /* I don't know why DEC Alpha OSF1 fail to compile this file if we
  51    include the following file.  */
  52 /* #include "systty.h" */
  53 #include "syssignal.h"
  54 
  55 #ifdef HAVE_X_WINDOWS
  56 #include "xterm.h"
  57 #endif /* HAVE_X_WINDOWS */
  58 
  59 #ifdef HAVE_NTGUI
  60 #include "w32term.h"
  61 #endif /* HAVE_NTGUI */
  62 
  63 #ifdef HAVE_NS
  64 #include "nsterm.h"
  65 #endif
  66 
  67 /* Include systime.h after xterm.h to avoid double inclusion of time.h.  */
  68 
  69 #include "systime.h"
  70 #include <errno.h>
  71 
  72 /* To get the prototype for `sleep'.  */
  73 
  74 #ifdef HAVE_UNISTD_H
  75 #include <unistd.h>
  76 #endif
  77 
  78 /* Get number of chars of output now in the buffer of a stdio stream.
  79    This ought to be built in in stdio, but it isn't.  Some s- files
  80    override this because their stdio internals differ.  */
  81 
  82 #ifdef __GNU_LIBRARY__
  83 
  84 /* The s- file might have overridden the definition with one that
  85    works for the system's C library.  But we are using the GNU C
  86    library, so this is the right definition for every system.  */
  87 
  88 #ifdef GNU_LIBRARY_PENDING_OUTPUT_COUNT
  89 #define PENDING_OUTPUT_COUNT GNU_LIBRARY_PENDING_OUTPUT_COUNT
  90 #else
  91 #undef  PENDING_OUTPUT_COUNT
  92 #define PENDING_OUTPUT_COUNT(FILE) ((FILE)->__bufp - (FILE)->__buffer)
  93 #endif
  94 #else /* not __GNU_LIBRARY__ */
  95 #if !defined (PENDING_OUTPUT_COUNT) && HAVE_STDIO_EXT_H && HAVE___FPENDING
  96 #include <stdio_ext.h>
  97 #define PENDING_OUTPUT_COUNT(FILE) __fpending (FILE)
  98 #endif
  99 #ifndef PENDING_OUTPUT_COUNT
 100 #define PENDING_OUTPUT_COUNT(FILE) ((FILE)->_ptr - (FILE)->_base)
 101 #endif
 102 #endif /* not __GNU_LIBRARY__ */
 103 
 104 #if defined(HAVE_TERM_H) && defined (GNU_LINUX) && defined (HAVE_LIBNCURSES)
 105 #include <term.h>               /* for tgetent */
 106 #endif
 107 
 108 /* Structure to pass dimensions around.  Used for character bounding
 109    boxes, glyph matrix dimensions and alike.  */
 110 
 111 struct dim
 112 {
 113   int width;
 114   int height;
 115 };
 116 
 117 
 118 /* Function prototypes.  */
 119 
 120 static struct glyph_matrix *save_current_matrix P_ ((struct frame *));
 121 static void restore_current_matrix P_ ((struct frame *, struct glyph_matrix *));
 122 static int showing_window_margins_p P_ ((struct window *));
 123 static void fake_current_matrices P_ ((Lisp_Object));
 124 static void redraw_overlapping_rows P_ ((struct window *, int));
 125 static void redraw_overlapped_rows P_ ((struct window *, int));
 126 static int count_blanks P_ ((struct glyph *, int));
 127 static int count_match P_ ((struct glyph *, struct glyph *,
 128                             struct glyph *, struct glyph *));
 129 static unsigned line_draw_cost P_ ((struct glyph_matrix *, int));
 130 static void update_frame_line P_ ((struct frame *, int));
 131 static struct dim allocate_matrices_for_frame_redisplay
 132      P_ ((Lisp_Object, int, int, int, int *));
 133 static void allocate_matrices_for_window_redisplay P_ ((struct window *));
 134 static int realloc_glyph_pool P_ ((struct glyph_pool *, struct dim));
 135 static void adjust_frame_glyphs P_ ((struct frame *));
 136 struct glyph_matrix *new_glyph_matrix P_ ((struct glyph_pool *));
 137 static void free_glyph_matrix P_ ((struct glyph_matrix *));
 138 static void adjust_glyph_matrix P_ ((struct window *, struct glyph_matrix *,
 139                                      int, int, struct dim));
 140 static void change_frame_size_1 P_ ((struct frame *, int, int, int, int, int));
 141 static void swap_glyph_pointers P_ ((struct glyph_row *, struct glyph_row *));
 142 #if GLYPH_DEBUG
 143 static int glyph_row_slice_p P_ ((struct glyph_row *, struct glyph_row *));
 144 #endif
 145 static void fill_up_frame_row_with_spaces P_ ((struct glyph_row *, int));
 146 static void build_frame_matrix_from_window_tree P_ ((struct glyph_matrix *,
 147                                                      struct window *));
 148 static void build_frame_matrix_from_leaf_window P_ ((struct glyph_matrix *,
 149                                                      struct window *));
 150 static struct glyph_pool *new_glyph_pool P_ ((void));
 151 static void free_glyph_pool P_ ((struct glyph_pool *));
 152 static void adjust_frame_glyphs_initially P_ ((void));
 153 static void adjust_frame_message_buffer P_ ((struct frame *));
 154 static void adjust_decode_mode_spec_buffer P_ ((struct frame *));
 155 static void fill_up_glyph_row_with_spaces P_ ((struct glyph_row *));
 156 static void build_frame_matrix P_ ((struct frame *));
 157 void clear_current_matrices P_ ((struct frame *));
 158 void scroll_glyph_matrix_range P_ ((struct glyph_matrix *, int, int,
 159                                     int, int));
 160 static void clear_window_matrices P_ ((struct window *, int));
 161 static void fill_up_glyph_row_area_with_spaces P_ ((struct glyph_row *, int));
 162 static int scrolling_window P_ ((struct window *, int));
 163 static int update_window_line P_ ((struct window *, int, int *));
 164 static void update_marginal_area P_ ((struct window *, int, int));
 165 static int update_text_area P_ ((struct window *, int));
 166 static void make_current P_ ((struct glyph_matrix *, struct glyph_matrix *,
 167                               int));
 168 static void mirror_make_current P_ ((struct window *, int));
 169 void check_window_matrix_pointers P_ ((struct window *));
 170 #if GLYPH_DEBUG
 171 static void check_matrix_pointers P_ ((struct glyph_matrix *,
 172                                        struct glyph_matrix *));
 173 #endif
 174 static void mirror_line_dance P_ ((struct window *, int, int, int *, char *));
 175 static int update_window_tree P_ ((struct window *, int));
 176 static int update_window P_ ((struct window *, int));
 177 static int update_frame_1 P_ ((struct frame *, int, int));
 178 static void set_window_cursor_after_update P_ ((struct window *));
 179 static int row_equal_p P_ ((struct window *, struct glyph_row *,
 180                             struct glyph_row *, int));
 181 static void adjust_frame_glyphs_for_window_redisplay P_ ((struct frame *));
 182 static void adjust_frame_glyphs_for_frame_redisplay P_ ((struct frame *));
 183 static void reverse_rows P_ ((struct glyph_matrix *, int, int));
 184 static int margin_glyphs_to_reserve P_ ((struct window *, int, Lisp_Object));
 185 static void sync_window_with_frame_matrix_rows P_ ((struct window *));
 186 struct window *frame_row_to_window P_ ((struct window *, int));
 187 
 188 
 189 /* Non-zero means don't pause redisplay for pending input.  (This is
 190    for debugging and for a future implementation of EDT-like
 191    scrolling.  */
 192 
 193 int redisplay_dont_pause;
 194 
 195 /* Define PERIODIC_PREEMPTION_CHECKING to 1, if micro-second timers
 196    are supported, so we can check for input during redisplay at
 197    regular intervals.  */
 198 #ifdef EMACS_HAS_USECS
 199 #define PERIODIC_PREEMPTION_CHECKING 1
 200 #else
 201 #define PERIODIC_PREEMPTION_CHECKING 0
 202 #endif
 203 
 204 #if PERIODIC_PREEMPTION_CHECKING
 205 
 206 /* If a number (float), check for user input every N seconds.  */
 207 
 208 Lisp_Object Vredisplay_preemption_period;
 209 
 210 /* Redisplay preemption timers.  */
 211 
 212 static EMACS_TIME preemption_period;
 213 static EMACS_TIME preemption_next_check;
 214 
 215 #endif
 216 
 217 /* Nonzero upon entry to redisplay means do not assume anything about
 218    current contents of actual terminal frame; clear and redraw it.  */
 219 
 220 int frame_garbaged;
 221 
 222 /* Nonzero means last display completed.  Zero means it was preempted.  */
 223 
 224 int display_completed;
 225 
 226 /* Lisp variable visible-bell; enables use of screen-flash instead of
 227    audible bell.  */
 228 
 229 int visible_bell;
 230 
 231 /* Invert the color of the whole frame, at a low level.  */
 232 
 233 int inverse_video;
 234 
 235 /* Line speed of the terminal.  */
 236 
 237 EMACS_INT baud_rate;
 238 
 239 /* Either nil or a symbol naming the window system under which Emacs
 240    creates the first frame.  */
 241 
 242 Lisp_Object Vinitial_window_system;
 243 
 244 /* Version number of X windows: 10, 11 or nil.  */
 245 
 246 Lisp_Object Vwindow_system_version;
 247 
 248 /* Vector of glyph definitions.  Indexed by glyph number, the contents
 249    are a string which is how to output the glyph.
 250 
 251    If Vglyph_table is nil, a glyph is output by using its low 8 bits
 252    as a character code.
 253 
 254    This is an obsolete feature that is no longer used.  The variable
 255    is retained for compatibility.  */
 256 
 257 Lisp_Object Vglyph_table;
 258 
 259 /* Display table to use for vectors that don't specify their own.  */
 260 
 261 Lisp_Object Vstandard_display_table;
 262 
 263 /* Nonzero means reading single-character input with prompt so put
 264    cursor on mini-buffer after the prompt.  Positive means at end of
 265    text in echo area; negative means at beginning of line.  */
 266 
 267 int cursor_in_echo_area;
 268 
 269 Lisp_Object Qdisplay_table, Qredisplay_dont_pause;
 270 
 271 
 272 /* The currently selected frame.  In a single-frame version, this
 273    variable always equals the_only_frame.  */
 274 
 275 Lisp_Object selected_frame;
 276 
 277 /* A frame which is not just a mini-buffer, or 0 if there are no such
 278    frames.  This is usually the most recent such frame that was
 279    selected.  In a single-frame version, this variable always holds
 280    the address of the_only_frame.  */
 281 
 282 struct frame *last_nonminibuf_frame;
 283 
 284 /* 1 means SIGWINCH happened when not safe.  */
 285 
 286 int delayed_size_change;
 287 
 288 /* 1 means glyph initialization has been completed at startup.  */
 289 
 290 static int glyphs_initialized_initially_p;
 291 
 292 /* Updated window if != 0.  Set by update_window.  */
 293 
 294 struct window *updated_window;
 295 
 296 /* Glyph row updated in update_window_line, and area that is updated.  */
 297 
 298 struct glyph_row *updated_row;
 299 int updated_area;
 300 
 301 /* A glyph for a space.  */
 302 
 303 struct glyph space_glyph;
 304 
 305 /* Counts of allocated structures.  These counts serve to diagnose
 306    memory leaks and double frees.  */
 307 
 308 int glyph_matrix_count;
 309 int glyph_pool_count;
 310 
 311 /* If non-null, the frame whose frame matrices are manipulated.  If
 312    null, window matrices are worked on.  */
 313 
 314 static struct frame *frame_matrix_frame;
 315 
 316 /* Non-zero means that fonts have been loaded since the last glyph
 317    matrix adjustments.  Redisplay must stop, and glyph matrices must
 318    be adjusted when this flag becomes non-zero during display.  The
 319    reason fonts can be loaded so late is that fonts of fontsets are
 320    loaded on demand.  Another reason is that a line contains many
 321    characters displayed by zero width or very narrow glyphs of
 322    variable-width fonts.  */
 323 
 324 int fonts_changed_p;
 325 
 326 /* Convert vpos and hpos from frame to window and vice versa.
 327    This may only be used for terminal frames.  */
 328 
 329 #if GLYPH_DEBUG
 330 
 331 static int window_to_frame_vpos P_ ((struct window *, int));
 332 static int window_to_frame_hpos P_ ((struct window *, int));
 333 #define WINDOW_TO_FRAME_VPOS(W, VPOS) window_to_frame_vpos ((W), (VPOS))
 334 #define WINDOW_TO_FRAME_HPOS(W, HPOS) window_to_frame_hpos ((W), (HPOS))
 335 
 336 /* One element of the ring buffer containing redisplay history
 337    information.  */
 338 
 339 struct redisplay_history
 340 {
 341   char trace[512 + 100];
 342 };
 343 
 344 /* The size of the history buffer.  */
 345 
 346 #define REDISPLAY_HISTORY_SIZE  30
 347 
 348 /* The redisplay history buffer.  */
 349 
 350 static struct redisplay_history redisplay_history[REDISPLAY_HISTORY_SIZE];
 351 
 352 /* Next free entry in redisplay_history.  */
 353 
 354 static int history_idx;
 355 
 356 /* A tick that's incremented each time something is added to the
 357    history.  */
 358 
 359 static unsigned history_tick;
 360 
 361 static void add_frame_display_history P_ ((struct frame *, int));
 362 static void add_window_display_history P_ ((struct window *, char *, int));
 363 
 364 /* Add to the redisplay history how window W has been displayed.
 365    MSG is a trace containing the information how W's glyph matrix
 366    has been constructed.  PAUSED_P non-zero means that the update
 367    has been interrupted for pending input.  */
 368 
 369 static void
 370 add_window_display_history (w, msg, paused_p)
 371      struct window *w;
 372      char *msg;
 373      int paused_p;
 374 {
 375   char *buf;
 376 
 377   if (history_idx >= REDISPLAY_HISTORY_SIZE)
 378     history_idx = 0;
 379   buf = redisplay_history[history_idx].trace;
 380   ++history_idx;
 381 
 382   sprintf (buf, "%d: window %p (`%s')%s\n",
 383            history_tick++,
 384            w,
 385            ((BUFFERP (w->buffer)
 386              && STRINGP (XBUFFER (w->buffer)->name))
 387             ? (char *) SDATA (XBUFFER (w->buffer)->name)
 388             : "???"),
 389            paused_p ? " ***paused***" : "");
 390   strcat (buf, msg);
 391 }
 392 
 393 
 394 /* Add to the redisplay history that frame F has been displayed.
 395    PAUSED_P non-zero means that the update has been interrupted for
 396    pending input.  */
 397 
 398 static void
 399 add_frame_display_history (f, paused_p)
 400      struct frame *f;
 401      int paused_p;
 402 {
 403   char *buf;
 404 
 405   if (history_idx >= REDISPLAY_HISTORY_SIZE)
 406     history_idx = 0;
 407   buf = redisplay_history[history_idx].trace;
 408   ++history_idx;
 409 
 410   sprintf (buf, "%d: update frame %p%s",
 411            history_tick++,
 412            f, paused_p ? " ***paused***" : "");
 413 }
 414 
 415 
 416 DEFUN ("dump-redisplay-history", Fdump_redisplay_history,
 417        Sdump_redisplay_history, 0, 0, "",
 418        doc: /* Dump redisplay history to stderr.  */)
 419      ()
 420 {
 421   int i;
 422 
 423   for (i = history_idx - 1; i != history_idx; --i)
 424     {
 425       if (i < 0)
 426         i = REDISPLAY_HISTORY_SIZE - 1;
 427       fprintf (stderr, "%s\n", redisplay_history[i].trace);
 428     }
 429 
 430   return Qnil;
 431 }
 432 
 433 
 434 #else /* GLYPH_DEBUG == 0 */
 435 
 436 #define WINDOW_TO_FRAME_VPOS(W, VPOS) ((VPOS) + WINDOW_TOP_EDGE_LINE (W))
 437 #define WINDOW_TO_FRAME_HPOS(W, HPOS) ((HPOS) + WINDOW_LEFT_EDGE_COL (W))
 438 
 439 #endif /* GLYPH_DEBUG == 0 */
 440 
 441 
 442 /* Like bcopy except never gets confused by overlap.  Let this be the
 443    first function defined in this file, or change emacs.c where the
 444    address of this function is used.  */
 445 
 446 void
 447 safe_bcopy (from, to, size)
 448      const char *from;
 449      char *to;
 450      int size;
 451 {
 452   if (size <= 0 || from == to)
 453     return;
 454 
 455   /* If the source and destination don't overlap, then bcopy can
 456      handle it.  If they do overlap, but the destination is lower in
 457      memory than the source, we'll assume bcopy can handle that.  */
 458   if (to < from || from + size <= to)
 459     bcopy (from, to, size);
 460 
 461   /* Otherwise, we'll copy from the end.  */
 462   else
 463     {
 464       register const char *endf = from + size;
 465       register char *endt = to + size;
 466 
 467       /* If TO - FROM is large, then we should break the copy into
 468          nonoverlapping chunks of TO - FROM bytes each.  However, if
 469          TO - FROM is small, then the bcopy function call overhead
 470          makes this not worth it.  The crossover point could be about
 471          anywhere.  Since I don't think the obvious copy loop is too
 472          bad, I'm trying to err in its favor.  */
 473       if (to - from < 64)
 474         {
 475           do
 476             *--endt = *--endf;
 477           while (endf != from);
 478         }
 479       else
 480         {
 481           for (;;)
 482             {
 483               endt -= (to - from);
 484               endf -= (to - from);
 485 
 486               if (endt < to)
 487                 break;
 488 
 489               bcopy (endf, endt, to - from);
 490             }
 491 
 492           /* If SIZE wasn't a multiple of TO - FROM, there will be a
 493              little left over.  The amount left over is (endt + (to -
 494              from)) - to, which is endt - from.  */
 495           bcopy (from, to, endt - from);
 496         }
 497     }
 498 }
 499 
 500 
 501 
 502 /***********************************************************************
 503                             Glyph Matrices
 504  ***********************************************************************/
 505 
 506 /* Allocate and return a glyph_matrix structure.  POOL is the glyph
 507    pool from which memory for the matrix should be allocated, or null
 508    for window-based redisplay where no glyph pools are used.  The
 509    member `pool' of the glyph matrix structure returned is set to
 510    POOL, the structure is otherwise zeroed.  */
 511 
 512 struct glyph_matrix *
 513 new_glyph_matrix (pool)
 514      struct glyph_pool *pool;
 515 {
 516   struct glyph_matrix *result;
 517 
 518   /* Allocate and clear.  */
 519   result = (struct glyph_matrix *) xmalloc (sizeof *result);
 520   bzero (result, sizeof *result);
 521 
 522   /* Increment number of allocated matrices.  This count is used
 523      to detect memory leaks.  */
 524   ++glyph_matrix_count;
 525 
 526   /* Set pool and return.  */
 527   result->pool = pool;
 528   return result;
 529 }
 530 
 531 
 532 /* Free glyph matrix MATRIX.  Passing in a null MATRIX is allowed.
 533 
 534    The global counter glyph_matrix_count is decremented when a matrix
 535    is freed.  If the count gets negative, more structures were freed
 536    than allocated, i.e. one matrix was freed more than once or a bogus
 537    pointer was passed to this function.
 538 
 539    If MATRIX->pool is null, this means that the matrix manages its own
 540    glyph memory---this is done for matrices on X frames.  Freeing the
 541    matrix also frees the glyph memory in this case.  */
 542 
 543 static void
 544 free_glyph_matrix (matrix)
 545      struct glyph_matrix *matrix;
 546 {
 547   if (matrix)
 548     {
 549       int i;
 550 
 551       /* Detect the case that more matrices are freed than were
 552          allocated.  */
 553       if (--glyph_matrix_count < 0)
 554         abort ();
 555 
 556       /* Free glyph memory if MATRIX owns it.  */
 557       if (matrix->pool == NULL)
 558         for (i = 0; i < matrix->rows_allocated; ++i)
 559           xfree (matrix->rows[i].glyphs[LEFT_MARGIN_AREA]);
 560 
 561       /* Free row structures and the matrix itself.  */
 562       xfree (matrix->rows);
 563       xfree (matrix);
 564     }
 565 }
 566 
 567 
 568 /* Return the number of glyphs to reserve for a marginal area of
 569    window W.  TOTAL_GLYPHS is the number of glyphs in a complete
 570    display line of window W.  MARGIN gives the width of the marginal
 571    area in canonical character units.  MARGIN should be an integer
 572    or a float.  */
 573 
 574 static int
 575 margin_glyphs_to_reserve (w, total_glyphs, margin)
 576      struct window *w;
 577      int total_glyphs;
 578      Lisp_Object margin;
 579 {
 580   int n;
 581 
 582   if (NUMBERP (margin))
 583     {
 584       int width = XFASTINT (w->total_cols);
 585       double d = max (0, XFLOATINT (margin));
 586       d = min (width / 2 - 1, d);
 587       n = (int) ((double) total_glyphs / width * d);
 588     }
 589   else
 590     n = 0;
 591 
 592   return n;
 593 }
 594 
 595 
 596 /* Adjust glyph matrix MATRIX on window W or on a frame to changed
 597    window sizes.
 598 
 599    W is null if the function is called for a frame glyph matrix.
 600    Otherwise it is the window MATRIX is a member of.  X and Y are the
 601    indices of the first column and row of MATRIX within the frame
 602    matrix, if such a matrix exists.  They are zero for purely
 603    window-based redisplay.  DIM is the needed size of the matrix.
 604 
 605    In window-based redisplay, where no frame matrices exist, glyph
 606    matrices manage their own glyph storage.  Otherwise, they allocate
 607    storage from a common frame glyph pool which can be found in
 608    MATRIX->pool.
 609 
 610    The reason for this memory management strategy is to avoid complete
 611    frame redraws if possible.  When we allocate from a common pool, a
 612    change of the location or size of a sub-matrix within the pool
 613    requires a complete redisplay of the frame because we cannot easily
 614    make sure that the current matrices of all windows still agree with
 615    what is displayed on the screen.  While this is usually fast, it
 616    leads to screen flickering.  */
 617 
 618 static void
 619 adjust_glyph_matrix (w, matrix, x, y, dim)
 620      struct window *w;
 621      struct glyph_matrix *matrix;
 622      int x, y;
 623      struct dim dim;
 624 {
 625   int i;
 626   int new_rows;
 627   int marginal_areas_changed_p = 0;
 628   int header_line_changed_p = 0;
 629   int header_line_p = 0;
 630   int left = -1, right = -1;
 631   int window_width = -1, window_height = -1;
 632 
 633   /* See if W had a header line that has disappeared now, or vice versa.
 634      Get W's size.  */
 635   if (w)
 636     {
 637       window_box (w, -1, 0, 0, &window_width, &window_height);
 638 
 639       header_line_p = WINDOW_WANTS_HEADER_LINE_P (w);
 640       header_line_changed_p = header_line_p != matrix->header_line_p;
 641     }
 642   matrix->header_line_p = header_line_p;
 643 
 644   /* If POOL is null, MATRIX is a window matrix for window-based redisplay.
 645      Do nothing if MATRIX' size, position, vscroll, and marginal areas
 646      haven't changed.  This optimization is important because preserving
 647      the matrix means preventing redisplay.  */
 648   if (matrix->pool == NULL)
 649     {
 650       left = margin_glyphs_to_reserve (w, dim.width, w->left_margin_cols);
 651       right = margin_glyphs_to_reserve (w, dim.width, w->right_margin_cols);
 652       xassert (left >= 0 && right >= 0);
 653       marginal_areas_changed_p = (left != matrix->left_margin_glyphs
 654                                   || right != matrix->right_margin_glyphs);
 655 
 656       if (!marginal_areas_changed_p
 657           && !fonts_changed_p
 658           && !header_line_changed_p
 659           && matrix->window_left_col == WINDOW_LEFT_EDGE_COL (w)
 660           && matrix->window_top_line == WINDOW_TOP_EDGE_LINE (w)
 661           && matrix->window_height == window_height
 662           && matrix->window_vscroll == w->vscroll
 663           && matrix->window_width == window_width)
 664         return;
 665     }
 666 
 667   /* Enlarge MATRIX->rows if necessary.  New rows are cleared.  */
 668   if (matrix->rows_allocated < dim.height)
 669     {
 670       int size = dim.height * sizeof (struct glyph_row);
 671       new_rows = dim.height - matrix->rows_allocated;
 672       matrix->rows = (struct glyph_row *) xrealloc (matrix->rows, size);
 673       bzero (matrix->rows + matrix->rows_allocated,
 674              new_rows * sizeof *matrix->rows);
 675       matrix->rows_allocated = dim.height;
 676     }
 677   else
 678     new_rows = 0;
 679 
 680   /* If POOL is not null, MATRIX is a frame matrix or a window matrix
 681      on a frame not using window-based redisplay.  Set up pointers for
 682      each row into the glyph pool.  */
 683   if (matrix->pool)
 684     {
 685       xassert (matrix->pool->glyphs);
 686 
 687       if (w)
 688         {
 689           left = margin_glyphs_to_reserve (w, dim.width,
 690                                            w->left_margin_cols);
 691           right = margin_glyphs_to_reserve (w, dim.width,
 692                                             w->right_margin_cols);
 693         }
 694       else
 695         left = right = 0;
 696 
 697       for (i = 0; i < dim.height; ++i)
 698         {
 699           struct glyph_row *row = &matrix->rows[i];
 700 
 701           row->glyphs[LEFT_MARGIN_AREA]
 702             = (matrix->pool->glyphs
 703                + (y + i) * matrix->pool->ncolumns
 704                + x);
 705 
 706           if (w == NULL
 707               || row == matrix->rows + dim.height - 1
 708               || (row == matrix->rows && matrix->header_line_p))
 709             {
 710               row->glyphs[TEXT_AREA]
 711                 = row->glyphs[LEFT_MARGIN_AREA];
 712               row->glyphs[RIGHT_MARGIN_AREA]
 713                 = row->glyphs[TEXT_AREA] + dim.width;
 714               row->glyphs[LAST_AREA]
 715                 = row->glyphs[RIGHT_MARGIN_AREA];
 716             }
 717           else
 718             {
 719               row->glyphs[TEXT_AREA]
 720                 = row->glyphs[LEFT_MARGIN_AREA] + left;
 721               row->glyphs[RIGHT_MARGIN_AREA]
 722                 = row->glyphs[TEXT_AREA] + dim.width - left - right;
 723               row->glyphs[LAST_AREA]
 724                 = row->glyphs[LEFT_MARGIN_AREA] + dim.width;
 725             }
 726         }
 727 
 728       matrix->left_margin_glyphs = left;
 729       matrix->right_margin_glyphs = right;
 730     }
 731   else
 732     {
 733       /* If MATRIX->pool is null, MATRIX is responsible for managing
 734          its own memory.  It is a window matrix for window-based redisplay.
 735          Allocate glyph memory from the heap.  */
 736       if (dim.width > matrix->matrix_w
 737           || new_rows
 738           || header_line_changed_p
 739           || marginal_areas_changed_p)
 740         {
 741           struct glyph_row *row = matrix->rows;
 742           struct glyph_row *end = row + matrix->rows_allocated;
 743 
 744           while (row < end)
 745             {
 746               row->glyphs[LEFT_MARGIN_AREA]
 747                 = (struct glyph *) xrealloc (row->glyphs[LEFT_MARGIN_AREA],
 748                                              (dim.width
 749                                               * sizeof (struct glyph)));
 750 
 751               /* The mode line never has marginal areas.  */
 752               if (row == matrix->rows + dim.height - 1
 753                   || (row == matrix->rows && matrix->header_line_p))
 754                 {
 755                   row->glyphs[TEXT_AREA]
 756                     = row->glyphs[LEFT_MARGIN_AREA];
 757                   row->glyphs[RIGHT_MARGIN_AREA]
 758                     = row->glyphs[TEXT_AREA] + dim.width;
 759                   row->glyphs[LAST_AREA]
 760                     = row->glyphs[RIGHT_MARGIN_AREA];
 761                 }
 762               else
 763                 {
 764                   row->glyphs[TEXT_AREA]
 765                     = row->glyphs[LEFT_MARGIN_AREA] + left;
 766                   row->glyphs[RIGHT_MARGIN_AREA]
 767                     = row->glyphs[TEXT_AREA] + dim.width - left - right;
 768                   row->glyphs[LAST_AREA]
 769                     = row->glyphs[LEFT_MARGIN_AREA] + dim.width;
 770                 }
 771               ++row;
 772             }
 773         }
 774 
 775       xassert (left >= 0 && right >= 0);
 776       matrix->left_margin_glyphs = left;
 777       matrix->right_margin_glyphs = right;
 778     }
 779 
 780   /* Number of rows to be used by MATRIX.  */
 781   matrix->nrows = dim.height;
 782   xassert (matrix->nrows >= 0);
 783 
 784   if (w)
 785     {
 786       if (matrix == w->current_matrix)
 787         {
 788           /* Mark rows in a current matrix of a window as not having
 789              valid contents.  It's important to not do this for
 790              desired matrices.  When Emacs starts, it may already be
 791              building desired matrices when this function runs.  */
 792           if (window_width < 0)
 793             window_width = window_box_width (w, -1);
 794 
 795           /* Optimize the case that only the height has changed (C-x 2,
 796              upper window).  Invalidate all rows that are no longer part
 797              of the window.  */
 798           if (!marginal_areas_changed_p
 799               && !header_line_changed_p
 800               && new_rows == 0
 801               && dim.width == matrix->matrix_w
 802               && matrix->window_left_col == WINDOW_LEFT_EDGE_COL (w)
 803               && matrix->window_top_line == WINDOW_TOP_EDGE_LINE (w)
 804               && matrix->window_width == window_width)
 805             {
 806               /* Find the last row in the window.  */
 807               for (i = 0; i < matrix->nrows && matrix->rows[i].enabled_p; ++i)
 808                 if (MATRIX_ROW_BOTTOM_Y (matrix->rows + i) >= window_height)
 809                   {
 810                     ++i;
 811                     break;
 812                   }
 813 
 814               /* Window end is invalid, if inside of the rows that
 815                  are invalidated below.  */
 816               if (INTEGERP (w->window_end_vpos)
 817                   && XFASTINT (w->window_end_vpos) >= i)
 818                 w->window_end_valid = Qnil;
 819 
 820               while (i < matrix->nrows)
 821                 matrix->rows[i++].enabled_p = 0;
 822             }
 823           else
 824             {
 825               for (i = 0; i < matrix->nrows; ++i)
 826                 matrix->rows[i].enabled_p = 0;
 827             }
 828         }
 829       else if (matrix == w->desired_matrix)
 830         {
 831           /* Rows in desired matrices always have to be cleared;
 832              redisplay expects this is the case when it runs, so it
 833              had better be the case when we adjust matrices between
 834              redisplays.  */
 835           for (i = 0; i < matrix->nrows; ++i)
 836             matrix->rows[i].enabled_p = 0;
 837         }
 838     }
 839 
 840 
 841   /* Remember last values to be able to optimize frame redraws.  */
 842   matrix->matrix_x = x;
 843   matrix->matrix_y = y;
 844   matrix->matrix_w = dim.width;
 845   matrix->matrix_h = dim.height;
 846 
 847   /* Record the top y location and height of W at the time the matrix
 848      was last adjusted.  This is used to optimize redisplay above.  */
 849   if (w)
 850     {
 851       matrix->window_left_col = WINDOW_LEFT_EDGE_COL (w);
 852       matrix->window_top_line = WINDOW_TOP_EDGE_LINE (w);
 853       matrix->window_height = window_height;
 854       matrix->window_width = window_width;
 855       matrix->window_vscroll = w->vscroll;
 856     }
 857 }
 858 
 859 
 860 /* Reverse the contents of rows in MATRIX between START and END.  The
 861    contents of the row at END - 1 end up at START, END - 2 at START +
 862    1 etc.  This is part of the implementation of rotate_matrix (see
 863    below).  */
 864 
 865 static void
 866 reverse_rows (matrix, start, end)
 867      struct glyph_matrix *matrix;
 868      int start, end;
 869 {
 870   int i, j;
 871 
 872   for (i = start, j = end - 1; i < j; ++i, --j)
 873     {
 874       /* Non-ISO HP/UX compiler doesn't like auto struct
 875          initialization.  */
 876       struct glyph_row temp;
 877       temp = matrix->rows[i];
 878       matrix->rows[i] = matrix->rows[j];
 879       matrix->rows[j] = temp;
 880     }
 881 }
 882 
 883 
 884 /* Rotate the contents of rows in MATRIX in the range FIRST .. LAST -
 885    1 by BY positions.  BY < 0 means rotate left, i.e. towards lower
 886    indices.  (Note: this does not copy glyphs, only glyph pointers in
 887    row structures are moved around).
 888 
 889    The algorithm used for rotating the vector was, I believe, first
 890    described by Kernighan.  See the vector R as consisting of two
 891    sub-vectors AB, where A has length BY for BY >= 0.  The result
 892    after rotating is then BA.  Reverse both sub-vectors to get ArBr
 893    and reverse the result to get (ArBr)r which is BA.  Similar for
 894    rotating right.  */
 895 
 896 void
 897 rotate_matrix (matrix, first, last, by)
 898      struct glyph_matrix *matrix;
 899      int first, last, by;
 900 {
 901   if (by < 0)
 902     {
 903       /* Up (rotate left, i.e. towards lower indices).  */
 904       by = -by;
 905       reverse_rows (matrix, first, first + by);
 906       reverse_rows (matrix, first + by, last);
 907       reverse_rows (matrix, first, last);
 908     }
 909   else if (by > 0)
 910     {
 911       /* Down (rotate right, i.e. towards higher indices).  */
 912       reverse_rows (matrix, last - by, last);
 913       reverse_rows (matrix, first, last - by);
 914       reverse_rows (matrix, first, last);
 915     }
 916 }
 917 
 918 
 919 /* Increment buffer positions in glyph rows of MATRIX.  Do it for rows
 920    with indices START <= index < END.  Increment positions by DELTA/
 921    DELTA_BYTES.  */
 922 
 923 void
 924 increment_matrix_positions (matrix, start, end, delta, delta_bytes)
 925      struct glyph_matrix *matrix;
 926      int start, end, delta, delta_bytes;
 927 {
 928   /* Check that START and END are reasonable values.  */
 929   xassert (start >= 0 && start <= matrix->nrows);
 930   xassert (end >= 0 && end <= matrix->nrows);
 931   xassert (start <= end);
 932 
 933   for (; start < end; ++start)
 934     increment_row_positions (matrix->rows + start, delta, delta_bytes);
 935 }
 936 
 937 
 938 /* Enable a range of rows in glyph matrix MATRIX.  START and END are
 939    the row indices of the first and last + 1 row to enable.  If
 940    ENABLED_P is non-zero, enabled_p flags in rows will be set to 1.  */
 941 
 942 void
 943 enable_glyph_matrix_rows (matrix, start, end, enabled_p)
 944      struct glyph_matrix *matrix;
 945      int start, end;
 946      int enabled_p;
 947 {
 948   xassert (start <= end);
 949   xassert (start >= 0 && start < matrix->nrows);
 950   xassert (end >= 0 && end <= matrix->nrows);
 951 
 952   for (; start < end; ++start)
 953     matrix->rows[start].enabled_p = enabled_p != 0;
 954 }
 955 
 956 
 957 /* Clear MATRIX.
 958 
 959    This empties all rows in MATRIX by setting the enabled_p flag for
 960    all rows of the matrix to zero.  The function prepare_desired_row
 961    will eventually really clear a row when it sees one with a zero
 962    enabled_p flag.
 963 
 964    Resets update hints to defaults value.  The only update hint
 965    currently present is the flag MATRIX->no_scrolling_p.  */
 966 
 967 void
 968 clear_glyph_matrix (matrix)
 969      struct glyph_matrix *matrix;
 970 {
 971   if (matrix)
 972     {
 973       enable_glyph_matrix_rows (matrix, 0, matrix->nrows, 0);
 974       matrix->no_scrolling_p = 0;
 975     }
 976 }
 977 
 978 
 979 /* Shift part of the glyph matrix MATRIX of window W up or down.
 980    Increment y-positions in glyph rows between START and END by DY,
 981    and recompute their visible height.  */
 982 
 983 void
 984 shift_glyph_matrix (w, matrix, start, end, dy)
 985      struct window *w;
 986      struct glyph_matrix *matrix;
 987      int start, end, dy;
 988 {
 989   int min_y, max_y;
 990 
 991   xassert (start <= end);
 992   xassert (start >= 0 && start < matrix->nrows);
 993   xassert (end >= 0 && end <= matrix->nrows);
 994 
 995   min_y = WINDOW_HEADER_LINE_HEIGHT (w);
 996   max_y = WINDOW_BOX_HEIGHT_NO_MODE_LINE (w);
 997 
 998   for (; start < end; ++start)
 999     {
1000       struct glyph_row *row = &matrix->rows[start];
1001 
1002       row->y += dy;
1003       row->visible_height = row->height;
1004 
1005       if (row->y < min_y)
1006         row->visible_height -= min_y - row->y;
1007       if (row->y + row->height > max_y)
1008         row->visible_height -= row->y + row->height - max_y;
1009     }
1010 }
1011 
1012 
1013 /* Mark all rows in current matrices of frame F as invalid.  Marking
1014    invalid is done by setting enabled_p to zero for all rows in a
1015    current matrix.  */
1016 
1017 void
1018 clear_current_matrices (f)
1019      register struct frame *f;
1020 {
1021   /* Clear frame current matrix, if we have one.  */
1022   if (f->current_matrix)
1023     clear_glyph_matrix (f->current_matrix);
1024 
1025   /* Clear the matrix of the menu bar window, if such a window exists.
1026      The menu bar window is currently used to display menus on X when
1027      no toolkit support is compiled in.  */
1028   if (WINDOWP (f->menu_bar_window))
1029     clear_glyph_matrix (XWINDOW (f->menu_bar_window)->current_matrix);
1030 
1031   /* Clear the matrix of the tool-bar window, if any.  */
1032   if (WINDOWP (f->tool_bar_window))
1033     clear_glyph_matrix (XWINDOW (f->tool_bar_window)->current_matrix);
1034 
1035   /* Clear current window matrices.  */
1036   xassert (WINDOWP (FRAME_ROOT_WINDOW (f)));
1037   clear_window_matrices (XWINDOW (FRAME_ROOT_WINDOW (f)), 0);
1038 }
1039 
1040 
1041 /* Clear out all display lines of F for a coming redisplay.  */
1042 
1043 void
1044 clear_desired_matrices (f)
1045      register struct frame *f;
1046 {
1047   if (f->desired_matrix)
1048     clear_glyph_matrix (f->desired_matrix);
1049 
1050   if (WINDOWP (f->menu_bar_window))
1051     clear_glyph_matrix (XWINDOW (f->menu_bar_window)->desired_matrix);
1052 
1053   if (WINDOWP (f->tool_bar_window))
1054     clear_glyph_matrix (XWINDOW (f->tool_bar_window)->desired_matrix);
1055 
1056   /* Do it for window matrices.  */
1057   xassert (WINDOWP (FRAME_ROOT_WINDOW (f)));
1058   clear_window_matrices (XWINDOW (FRAME_ROOT_WINDOW (f)), 1);
1059 }
1060 
1061 
1062 /* Clear matrices in window tree rooted in W.  If DESIRED_P is
1063    non-zero clear desired matrices, otherwise clear current matrices.  */
1064 
1065 static void
1066 clear_window_matrices (w, desired_p)
1067      struct window *w;
1068      int desired_p;
1069 {
1070   while (w)
1071     {
1072       if (!NILP (w->hchild))
1073         {
1074           xassert (WINDOWP (w->hchild));
1075           clear_window_matrices (XWINDOW (w->hchild), desired_p);
1076         }
1077       else if (!NILP (w->vchild))
1078         {
1079           xassert (WINDOWP (w->vchild));
1080           clear_window_matrices (XWINDOW (w->vchild), desired_p);
1081         }
1082       else
1083         {
1084           if (desired_p)
1085             clear_glyph_matrix (w->desired_matrix);
1086           else
1087             {
1088               clear_glyph_matrix (w->current_matrix);
1089               w->window_end_valid = Qnil;
1090             }
1091         }
1092 
1093       w = NILP (w->next) ? 0 : XWINDOW (w->next);
1094     }
1095 }
1096 
1097 
1098 
1099 /***********************************************************************
1100                               Glyph Rows
1101 
1102       See dispextern.h for an overall explanation of glyph rows.
1103  ***********************************************************************/
1104 
1105 /* Clear glyph row ROW.  Do it in a way that makes it robust against
1106    changes in the glyph_row structure, i.e. addition or removal of
1107    structure members.  */
1108 
1109 static struct glyph_row null_row;
1110 
1111 void
1112 clear_glyph_row (row)
1113      struct glyph_row *row;
1114 {
1115   struct glyph *p[1 + LAST_AREA];
1116 
1117   /* Save pointers.  */
1118   p[LEFT_MARGIN_AREA] = row->glyphs[LEFT_MARGIN_AREA];
1119   p[TEXT_AREA] = row->glyphs[TEXT_AREA];
1120   p[RIGHT_MARGIN_AREA] = row->glyphs[RIGHT_MARGIN_AREA];
1121   p[LAST_AREA] = row->glyphs[LAST_AREA];
1122 
1123   /* Clear.  */
1124   *row = null_row;
1125 
1126   /* Restore pointers.  */
1127   row->glyphs[LEFT_MARGIN_AREA] = p[LEFT_MARGIN_AREA];
1128   row->glyphs[TEXT_AREA] = p[TEXT_AREA];
1129   row->glyphs[RIGHT_MARGIN_AREA] = p[RIGHT_MARGIN_AREA];
1130   row->glyphs[LAST_AREA] = p[LAST_AREA];
1131 
1132 #if 0 /* At some point, some bit-fields of struct glyph were not set,
1133          which made glyphs unequal when compared with GLYPH_EQUAL_P.
1134          Redisplay outputs such glyphs, and flickering effects were
1135          the result.  This also depended on the contents of memory
1136          returned by xmalloc.  If flickering happens again, activate
1137          the code below.  If the flickering is gone with that, chances
1138          are that the flickering has the same reason as here.  */
1139   bzero (p[0], (char *) p[LAST_AREA] - (char *) p[0]);
1140 #endif
1141 }
1142 
1143 
1144 /* Make ROW an empty, enabled row of canonical character height,
1145    in window W starting at y-position Y.  */
1146 
1147 void
1148 blank_row (w, row, y)
1149      struct window *w;
1150      struct glyph_row *row;
1151      int y;
1152 {
1153   int min_y, max_y;
1154 
1155   min_y = WINDOW_HEADER_LINE_HEIGHT (w);
1156   max_y = WINDOW_BOX_HEIGHT_NO_MODE_LINE (w);
1157 
1158   clear_glyph_row (row);
1159   row->y = y;
1160   row->ascent = row->phys_ascent = 0;
1161   row->height = row->phys_height = FRAME_LINE_HEIGHT (XFRAME (w->frame));
1162   row->visible_height = row->height;
1163 
1164   if (row->y < min_y)
1165     row->visible_height -= min_y - row->y;
1166   if (row->y + row->height > max_y)
1167     row->visible_height -= row->y + row->height - max_y;
1168 
1169   row->enabled_p = 1;
1170 }
1171 
1172 
1173 /* Increment buffer positions in glyph row ROW.  DELTA and DELTA_BYTES
1174    are the amounts by which to change positions.  Note that the first
1175    glyph of the text area of a row can have a buffer position even if
1176    the used count of the text area is zero.  Such rows display line
1177    ends.  */
1178 
1179 void
1180 increment_row_positions (row, delta, delta_bytes)
1181      struct glyph_row *row;
1182      int delta, delta_bytes;
1183 {
1184   int area, i;
1185 
1186   /* Increment start and end positions.  */
1187   MATRIX_ROW_START_CHARPOS (row) += delta;
1188   MATRIX_ROW_START_BYTEPOS (row) += delta_bytes;
1189   MATRIX_ROW_END_CHARPOS (row) += delta;
1190   MATRIX_ROW_END_BYTEPOS (row) += delta_bytes;
1191   CHARPOS (row->start.pos) += delta;
1192   BYTEPOS (row->start.pos) += delta_bytes;
1193   CHARPOS (row->end.pos) += delta;
1194   BYTEPOS (row->end.pos) += delta_bytes;
1195 
1196   if (!row->enabled_p)
1197     return;
1198 
1199   /* Increment positions in glyphs.  */
1200   for (area = 0; area < LAST_AREA; ++area)
1201     for (i = 0; i < row->used[area]; ++i)
1202       if (BUFFERP (row->glyphs[area][i].object)
1203           && row->glyphs[area][i].charpos > 0)
1204         row->glyphs[area][i].charpos += delta;
1205 
1206   /* Capture the case of rows displaying a line end.  */
1207   if (row->used[TEXT_AREA] == 0
1208       && MATRIX_ROW_DISPLAYS_TEXT_P (row))
1209     row->glyphs[TEXT_AREA]->charpos += delta;
1210 }
1211 
1212 
1213 #if 0
1214 /* Swap glyphs between two glyph rows A and B.  This exchanges glyph
1215    contents, i.e. glyph structure contents are exchanged between A and
1216    B without changing glyph pointers in A and B.  */
1217 
1218 static void
1219 swap_glyphs_in_rows (a, b)
1220      struct glyph_row *a, *b;
1221 {
1222   int area;
1223 
1224   for (area = 0; area < LAST_AREA; ++area)
1225     {
1226       /* Number of glyphs to swap.  */
1227       int max_used = max (a->used[area], b->used[area]);
1228 
1229       /* Start of glyphs in area of row A.  */
1230       struct glyph *glyph_a = a->glyphs[area];
1231 
1232       /* End + 1 of glyphs in area of row A.  */
1233       struct glyph *glyph_a_end = a->glyphs[max_used];
1234 
1235       /* Start of glyphs in area of row B.  */
1236       struct glyph *glyph_b = b->glyphs[area];
1237 
1238       while (glyph_a < glyph_a_end)
1239         {
1240           /* Non-ISO HP/UX compiler doesn't like auto struct
1241              initialization.  */
1242           struct glyph temp;
1243           temp = *glyph_a;
1244           *glyph_a = *glyph_b;
1245           *glyph_b = temp;
1246           ++glyph_a;
1247           ++glyph_b;
1248         }
1249     }
1250 }
1251 
1252 #endif /* 0 */
1253 
1254 /* Exchange pointers to glyph memory between glyph rows A and B.  */
1255 
1256 static INLINE void
1257 swap_glyph_pointers (a, b)
1258      struct glyph_row *a, *b;
1259 {
1260   int i;
1261   for (i = 0; i < LAST_AREA + 1; ++i)
1262     {
1263       struct glyph *temp = a->glyphs[i];
1264       a->glyphs[i] = b->glyphs[i];
1265       b->glyphs[i] = temp;
1266     }
1267 }
1268 
1269 
1270 /* Copy glyph row structure FROM to glyph row structure TO, except
1271    that glyph pointers in the structures are left unchanged.  */
1272 
1273 INLINE void
1274 copy_row_except_pointers (to, from)
1275      struct glyph_row *to, *from;
1276 {
1277   struct glyph *pointers[1 + LAST_AREA];
1278 
1279   /* Save glyph pointers of TO.  */
1280   bcopy (to->glyphs, pointers, sizeof to->glyphs);
1281 
1282   /* Do a structure assignment.  */
1283   *to = *from;
1284 
1285   /* Restore original pointers of TO.  */
1286   bcopy (pointers, to->glyphs, sizeof to->glyphs);
1287 }
1288 
1289 
1290 /* Copy contents of glyph row FROM to glyph row TO.  Glyph pointers in
1291    TO and FROM are left unchanged.  Glyph contents are copied from the
1292    glyph memory of FROM to the glyph memory of TO.  Increment buffer
1293    positions in row TO by DELTA/ DELTA_BYTES.  */
1294 
1295 void
1296 copy_glyph_row_contents (to, from, delta, delta_bytes)
1297      struct glyph_row *to, *from;
1298      int delta, delta_bytes;
1299 {
1300   int area;
1301 
1302   /* This is like a structure assignment TO = FROM, except that
1303      glyph pointers in the rows are left unchanged.  */
1304   copy_row_except_pointers (to, from);
1305 
1306   /* Copy glyphs from FROM to TO.  */
1307   for (area = 0; area < LAST_AREA; ++area)
1308     if (from->used[area])
1309       bcopy (from->glyphs[area], to->glyphs[area],
1310              from->used[area] * sizeof (struct glyph));
1311 
1312   /* Increment buffer positions in TO by DELTA.  */
1313   increment_row_positions (to, delta, delta_bytes);
1314 }
1315 
1316 
1317 /* Assign glyph row FROM to glyph row TO.  This works like a structure
1318    assignment TO = FROM, except that glyph pointers are not copied but
1319    exchanged between TO and FROM.  Pointers must be exchanged to avoid
1320    a memory leak.  */
1321 
1322 static INLINE void
1323 assign_row (to, from)
1324      struct glyph_row *to, *from;
1325 {
1326   swap_glyph_pointers (to, from);
1327   copy_row_except_pointers (to, from);
1328 }
1329 
1330 
1331 /* Test whether the glyph memory of the glyph row WINDOW_ROW, which is
1332    a row in a window matrix, is a slice of the glyph memory of the
1333    glyph row FRAME_ROW which is a row in a frame glyph matrix.  Value
1334    is non-zero if the glyph memory of WINDOW_ROW is part of the glyph
1335    memory of FRAME_ROW.  */
1336 
1337 #if GLYPH_DEBUG
1338 
1339 static int
1340 glyph_row_slice_p (window_row, frame_row)
1341      struct glyph_row *window_row, *frame_row;
1342 {
1343   struct glyph *window_glyph_start = window_row->glyphs[0];
1344   struct glyph *frame_glyph_start = frame_row->glyphs[0];
1345   struct glyph *frame_glyph_end = frame_row->glyphs[LAST_AREA];
1346 
1347   return (frame_glyph_start <= window_glyph_start
1348           && window_glyph_start < frame_glyph_end);
1349 }
1350 
1351 #endif /* GLYPH_DEBUG */
1352 
1353 #if 0
1354 
1355 /* Find the row in the window glyph matrix WINDOW_MATRIX being a slice
1356    of ROW in the frame matrix FRAME_MATRIX.  Value is null if no row
1357    in WINDOW_MATRIX is found satisfying the condition.  */
1358 
1359 static struct glyph_row *
1360 find_glyph_row_slice (window_matrix, frame_matrix, row)
1361      struct glyph_matrix *window_matrix, *frame_matrix;
1362      int row;
1363 {
1364   int i;
1365 
1366   xassert (row >= 0 && row < frame_matrix->nrows);
1367 
1368   for (i = 0; i < window_matrix->nrows; ++i)
1369     if (glyph_row_slice_p (window_matrix->rows + i,
1370                            frame_matrix->rows + row))
1371       break;
1372 
1373   return i < window_matrix->nrows ? window_matrix->rows + i : 0;
1374 }
1375 
1376 #endif /* 0 */
1377 
1378 /* Prepare ROW for display.  Desired rows are cleared lazily,
1379    i.e. they are only marked as to be cleared by setting their
1380    enabled_p flag to zero.  When a row is to be displayed, a prior
1381    call to this function really clears it.  */
1382 
1383 void
1384 prepare_desired_row (row)
1385      struct glyph_row *row;
1386 {
1387   if (!row->enabled_p)
1388     {
1389       unsigned rp = row->reversed_p;
1390 
1391       clear_glyph_row (row);
1392       row->enabled_p = 1;
1393       row->reversed_p = rp;
1394     }
1395 }
1396 
1397 
1398 /* Return a hash code for glyph row ROW.  */
1399 
1400 int
1401 line_hash_code (row)
1402      struct glyph_row *row;
1403 {
1404   int hash = 0;
1405 
1406   if (row->enabled_p)
1407     {
1408       struct glyph *glyph = row->glyphs[TEXT_AREA];
1409       struct glyph *end = glyph + row->used[TEXT_AREA];
1410 
1411       while (glyph < end)
1412         {
1413           int c = glyph->u.ch;
1414           int face_id = glyph->face_id;
1415           if (FRAME_MUST_WRITE_SPACES (SELECTED_FRAME ())) /* XXX Is SELECTED_FRAME OK here? */
1416             c -= SPACEGLYPH;
1417           hash = (((hash << 4) + (hash >> 24)) & 0x0fffffff) + c;
1418           hash = (((hash << 4) + (hash >> 24)) & 0x0fffffff) + face_id;
1419           ++glyph;
1420         }
1421 
1422       if (hash == 0)
1423         hash = 1;
1424     }
1425 
1426   return hash;
1427 }
1428 
1429 
1430 /* Return the cost of drawing line VPOS in MATRIX.  The cost equals
1431    the number of characters in the line.  If must_write_spaces is
1432    zero, leading and trailing spaces are ignored.  */
1433 
1434 static unsigned int
1435 line_draw_cost (matrix, vpos)
1436      struct glyph_matrix *matrix;
1437      int vpos;
1438 {
1439   struct glyph_row *row = matrix->rows + vpos;
1440   struct glyph *beg = row->glyphs[TEXT_AREA];
1441   struct glyph *end = beg + row->used[TEXT_AREA];
1442   int len;
1443   Lisp_Object *glyph_table_base = GLYPH_TABLE_BASE;
1444   int glyph_table_len = GLYPH_TABLE_LENGTH;
1445 
1446   /* Ignore trailing and leading spaces if we can.  */
1447   if (!FRAME_MUST_WRITE_SPACES (SELECTED_FRAME ())) /* XXX Is SELECTED_FRAME OK here? */
1448     {
1449       /* Skip from the end over trailing spaces.  */
1450       while (end > beg && CHAR_GLYPH_SPACE_P (*(end - 1)))
1451         --end;
1452 
1453       /* All blank line.  */
1454       if (end == beg)
1455         return 0;
1456 
1457       /* Skip over leading spaces.  */
1458       while (CHAR_GLYPH_SPACE_P (*beg))
1459         ++beg;
1460     }
1461 
1462   /* If we don't have a glyph-table, each glyph is one character,
1463      so return the number of glyphs.  */
1464   if (glyph_table_base == 0)
1465     len = end - beg;
1466   else
1467     {
1468       /* Otherwise, scan the glyphs and accumulate their total length
1469          in LEN.  */
1470       len = 0;
1471       while (beg < end)
1472         {
1473           GLYPH g;
1474 
1475           SET_GLYPH_FROM_CHAR_GLYPH (g, *beg);
1476 
1477           if (GLYPH_INVALID_P (g)
1478               || GLYPH_SIMPLE_P (glyph_table_base, glyph_table_len, g))
1479             len += 1;
1480           else
1481             len += GLYPH_LENGTH (glyph_table_base, g);
1482 
1483           ++beg;
1484         }
1485     }
1486 
1487   return len;
1488 }
1489 
1490 
1491 /* Test two glyph rows A and B for equality.  Value is non-zero if A
1492    and B have equal contents.  W is the window to which the glyphs
1493    rows A and B belong.  It is needed here to test for partial row
1494    visibility.  MOUSE_FACE_P non-zero means compare the mouse_face_p
1495    flags of A and B, too.  */
1496 
1497 static INLINE int
1498 row_equal_p (w, a, b, mouse_face_p)
1499      struct window *w;
1500      struct glyph_row *a, *b;
1501      int mouse_face_p;
1502 {
1503   if (a == b)
1504     return 1;
1505   else if (a->hash != b->hash)
1506     return 0;
1507   else
1508     {
1509       struct glyph *a_glyph, *b_glyph, *a_end;
1510       int area;
1511 
1512       if (mouse_face_p && a->mouse_face_p != b->mouse_face_p)
1513         return 0;
1514 
1515       /* Compare glyphs.  */
1516       for (area = LEFT_MARGIN_AREA; area < LAST_AREA; ++area)
1517         {
1518           if (a->used[area] != b->used[area])
1519             return 0;
1520 
1521           a_glyph = a->glyphs[area];
1522           a_end = a_glyph + a->used[area];
1523           b_glyph = b->glyphs[area];
1524 
1525           while (a_glyph < a_end
1526                  && GLYPH_EQUAL_P (a_glyph, b_glyph))
1527             ++a_glyph, ++b_glyph;
1528 
1529           if (a_glyph != a_end)
1530             return 0;
1531         }
1532 
1533       if (a->fill_line_p != b->fill_line_p
1534           || a->cursor_in_fringe_p != b->cursor_in_fringe_p
1535           || a->left_fringe_bitmap != b->left_fringe_bitmap
1536           || a->left_fringe_face_id != b->left_fringe_face_id
1537           || a->right_fringe_bitmap != b->right_fringe_bitmap
1538           || a->right_fringe_face_id != b->right_fringe_face_id
1539           || a->overlay_arrow_bitmap != b->overlay_arrow_bitmap
1540           || a->exact_window_width_line_p != b->exact_window_width_line_p
1541           || a->overlapped_p != b->overlapped_p
1542           || (MATRIX_ROW_CONTINUATION_LINE_P (a)
1543               != MATRIX_ROW_CONTINUATION_LINE_P (b))
1544           || a->reversed_p != b->reversed_p
1545           /* Different partially visible characters on left margin.  */
1546           || a->x != b->x
1547           /* Different height.  */
1548           || a->ascent != b->ascent
1549           || a->phys_ascent != b->phys_ascent
1550           || a->phys_height != b->phys_height
1551           || a->visible_height != b->visible_height)
1552         return 0;
1553     }
1554 
1555   return 1;
1556 }
1557 
1558 
1559 
1560 /***********************************************************************
1561                               Glyph Pool
1562 
1563      See dispextern.h for an overall explanation of glyph pools.
1564  ***********************************************************************/
1565 
1566 /* Allocate a glyph_pool structure.  The structure returned is
1567    initialized with zeros.  The global variable glyph_pool_count is
1568    incremented for each pool allocated.  */
1569 
1570 static struct glyph_pool *
1571 new_glyph_pool ()
1572 {
1573   struct glyph_pool *result;
1574 
1575   /* Allocate a new glyph_pool and clear it.  */
1576   result = (struct glyph_pool *) xmalloc (sizeof *result);
1577   bzero (result, sizeof *result);
1578 
1579   /* For memory leak and double deletion checking.  */
1580   ++glyph_pool_count;
1581 
1582   return result;
1583 }
1584 
1585 
1586 /* Free a glyph_pool structure POOL.  The function may be called with
1587    a null POOL pointer.  The global variable glyph_pool_count is
1588    decremented with every pool structure freed.  If this count gets
1589    negative, more structures were freed than allocated, i.e. one
1590    structure must have been freed more than once or a bogus pointer
1591    was passed to free_glyph_pool.  */
1592 
1593 static void
1594 free_glyph_pool (pool)
1595      struct glyph_pool *pool;
1596 {
1597   if (pool)
1598     {
1599       /* More freed than allocated?  */
1600       --glyph_pool_count;
1601       xassert (glyph_pool_count >= 0);
1602 
1603       xfree (pool->glyphs);
1604       xfree (pool);
1605     }
1606 }
1607 
1608 
1609 /* Enlarge a glyph pool POOL.  MATRIX_DIM gives the number of rows and
1610    columns we need.  This function never shrinks a pool.  The only
1611    case in which this would make sense, would be when a frame's size
1612    is changed from a large value to a smaller one.  But, if someone
1613    does it once, we can expect that he will do it again.
1614 
1615    Value is non-zero if the pool changed in a way which makes
1616    re-adjusting window glyph matrices necessary.  */
1617 
1618 static int
1619 realloc_glyph_pool (pool, matrix_dim)
1620      struct glyph_pool *pool;
1621      struct dim matrix_dim;
1622 {
1623   int needed;
1624   int changed_p;
1625 
1626   changed_p = (pool->glyphs == 0
1627                || matrix_dim.height != pool->nrows
1628                || matrix_dim.width != pool->ncolumns);
1629 
1630   /* Enlarge the glyph pool.  */
1631   needed = matrix_dim.width * matrix_dim.height;
1632   if (needed > pool->nglyphs)
1633     {
1634       int size = needed * sizeof (struct glyph);
1635 
1636       if (pool->glyphs)
1637         pool->glyphs = (struct glyph *) xrealloc (pool->glyphs, size);
1638       else
1639         {
1640           pool->glyphs = (struct glyph *) xmalloc (size);
1641           bzero (pool->glyphs, size);
1642         }
1643 
1644       pool->nglyphs = needed;
1645     }
1646 
1647   /* Remember the number of rows and columns because (a) we use them
1648      to do sanity checks, and (b) the number of columns determines
1649      where rows in the frame matrix start---this must be available to
1650      determine pointers to rows of window sub-matrices.  */
1651   pool->nrows = matrix_dim.height;
1652   pool->ncolumns = matrix_dim.width;
1653 
1654   return changed_p;
1655 }
1656 
1657 
1658 
1659 /***********************************************************************
1660                               Debug Code
1661  ***********************************************************************/
1662 
1663 #if GLYPH_DEBUG
1664 
1665 
1666 /* Flush standard output.  This is sometimes useful to call from the debugger.
1667    XXX Maybe this should be changed to flush the current terminal instead of
1668    stdout.
1669 */
1670 
1671 void
1672 flush_stdout ()
1673 {
1674   fflush (stdout);
1675 }
1676 
1677 
1678 /* Check that no glyph pointers have been lost in MATRIX.  If a
1679    pointer has been lost, e.g. by using a structure assignment between
1680    rows, at least one pointer must occur more than once in the rows of
1681    MATRIX.  */
1682 
1683 void
1684 check_matrix_pointer_lossage (matrix)
1685      struct glyph_matrix *matrix;
1686 {
1687   int i, j;
1688 
1689   for (i = 0; i < matrix->nrows; ++i)
1690     for (j = 0; j < matrix->nrows; ++j)
1691       xassert (i == j
1692                || (matrix->rows[i].glyphs[TEXT_AREA]
1693                    != matrix->rows[j].glyphs[TEXT_AREA]));
1694 }
1695 
1696 
1697 /* Get a pointer to glyph row ROW in MATRIX, with bounds checks.  */
1698 
1699 struct glyph_row *
1700 matrix_row (matrix, row)
1701      struct glyph_matrix *matrix;
1702      int row;
1703 {
1704   xassert (matrix && matrix->rows);
1705   xassert (row >= 0 && row < matrix->nrows);
1706 
1707   /* That's really too slow for normal testing because this function
1708      is called almost everywhere.  Although---it's still astonishingly
1709      fast, so it is valuable to have for debugging purposes.  */
1710 #if 0
1711   check_matrix_pointer_lossage (matrix);
1712 #endif
1713 
1714   return matrix->rows + row;
1715 }
1716 
1717 
1718 #if 0 /* This function makes invalid assumptions when text is
1719          partially invisible.  But it might come handy for debugging
1720          nevertheless.  */
1721 
1722 /* Check invariants that must hold for an up to date current matrix of
1723    window W.  */
1724 
1725 static void
1726 check_matrix_invariants (w)
1727      struct window *w;
1728 {
1729   struct glyph_matrix *matrix = w->current_matrix;
1730   int yb = window_text_bottom_y (w);
1731   struct glyph_row *row = matrix->rows;
1732   struct glyph_row *last_text_row = NULL;
1733   struct buffer *saved = current_buffer;
1734   struct buffer *buffer = XBUFFER (w->buffer);
1735   int c;
1736 
1737   /* This can sometimes happen for a fresh window.  */
1738   if (matrix->nrows < 2)
1739     return;
1740 
1741   set_buffer_temp (buffer);
1742 
1743   /* Note: last row is always reserved for the mode line.  */
1744   while (MATRIX_ROW_DISPLAYS_TEXT_P (row)
1745          && MATRIX_ROW_BOTTOM_Y (row) < yb)
1746     {
1747       struct glyph_row *next = row + 1;
1748 
1749       if (MATRIX_ROW_DISPLAYS_TEXT_P (row))
1750         last_text_row = row;
1751 
1752       /* Check that character and byte positions are in sync.  */
1753       xassert (MATRIX_ROW_START_BYTEPOS (row)
1754                == CHAR_TO_BYTE (MATRIX_ROW_START_CHARPOS (row)));
1755       xassert (BYTEPOS (row->start.pos)
1756                == CHAR_TO_BYTE (CHARPOS (row->start.pos)));
1757 
1758       /* CHAR_TO_BYTE aborts when invoked for a position > Z.  We can
1759          have such a position temporarily in case of a minibuffer
1760          displaying something like `[Sole completion]' at its end.  */
1761       if (MATRIX_ROW_END_CHARPOS (row) < BUF_ZV (current_buffer))
1762         {
1763           xassert (MATRIX_ROW_END_BYTEPOS (row)
1764                    == CHAR_TO_BYTE (MATRIX_ROW_END_CHARPOS (row)));
1765           xassert (BYTEPOS (row->end.pos)
1766                    == CHAR_TO_BYTE (CHARPOS (row->end.pos)));
1767         }
1768 
1769       /* Check that end position of `row' is equal to start position
1770          of next row.  */
1771       if (next->enabled_p && MATRIX_ROW_DISPLAYS_TEXT_P (next))
1772         {
1773           xassert (MATRIX_ROW_END_CHARPOS (row)
1774                    == MATRIX_ROW_START_CHARPOS (next));
1775           xassert (MATRIX_ROW_END_BYTEPOS (row)
1776                    == MATRIX_ROW_START_BYTEPOS (next));
1777           xassert (CHARPOS (row->end.pos) == CHARPOS (next->start.pos));
1778           xassert (BYTEPOS (row->end.pos) == BYTEPOS (next->start.pos));
1779         }
1780       row = next;
1781     }
1782 
1783   xassert (w->current_matrix->nrows == w->desired_matrix->nrows);
1784   xassert (w->desired_matrix->rows != NULL);
1785   set_buffer_temp (saved);
1786 }
1787 
1788 #endif /* 0  */
1789 
1790 #endif /* GLYPH_DEBUG != 0 */
1791 
1792 
1793 
1794 /**********************************************************************
1795                  Allocating/ Adjusting Glyph Matrices
1796  **********************************************************************/
1797 
1798 /* Allocate glyph matrices over a window tree for a frame-based
1799    redisplay
1800 
1801    X and Y are column/row within the frame glyph matrix where
1802    sub-matrices for the window tree rooted at WINDOW must be
1803    allocated.  DIM_ONLY_P non-zero means that the caller of this
1804    function is only interested in the result matrix dimension, and
1805    matrix adjustments should not be performed.
1806 
1807    The function returns the total width/height of the sub-matrices of
1808    the window tree.  If called on a frame root window, the computation
1809    will take the mini-buffer window into account.
1810 
1811    *WINDOW_CHANGE_FLAGS is set to a bit mask with bits
1812 
1813    NEW_LEAF_MATRIX set if any window in the tree did not have a
1814    glyph matrices yet, and
1815 
1816    CHANGED_LEAF_MATRIX set if the dimension or location of a matrix of
1817    any window in the tree will be changed or have been changed (see
1818    DIM_ONLY_P)
1819 
1820    *WINDOW_CHANGE_FLAGS must be initialized by the caller of this
1821    function.
1822 
1823    Windows are arranged into chains of windows on the same level
1824    through the next fields of window structures.  Such a level can be
1825    either a sequence of horizontally adjacent windows from left to
1826    right, or a sequence of vertically adjacent windows from top to
1827    bottom.  Each window in a horizontal sequence can be either a leaf
1828    window or a vertical sequence; a window in a vertical sequence can
1829    be either a leaf or a horizontal sequence.  All windows in a
1830    horizontal sequence have the same height, and all windows in a
1831    vertical sequence have the same width.
1832 
1833    This function uses, for historical reasons, a more general
1834    algorithm to determine glyph matrix dimensions that would be
1835    necessary.
1836 
1837    The matrix height of a horizontal sequence is determined by the
1838    maximum height of any matrix in the sequence.  The matrix width of
1839    a horizontal sequence is computed by adding up matrix widths of
1840    windows in the sequence.
1841 
1842    |<------- result width ------->|
1843    +---------+----------+---------+ ---
1844    |         |          |         |  |
1845    |         |          |         |
1846    +---------+          |         |  result height
1847              |          +---------+
1848              |          |            |
1849              +----------+           ---
1850 
1851    The matrix width of a vertical sequence is the maximum matrix width
1852    of any window in the sequence.  Its height is computed by adding up
1853    matrix heights of windows in the sequence.
1854 
1855    |<---- result width -->|
1856    +---------+              ---
1857    |         |               |
1858    |         |               |
1859    +---------+--+            |
1860    |            |            |
1861    |            |            result height
1862    |            |
1863    +------------+---------+  |
1864    |                      |  |
1865    |                      |  |
1866    +------------+---------+ ---  */
1867 
1868 /* Bit indicating that a new matrix will be allocated or has been
1869    allocated.  */
1870 
1871 #define NEW_LEAF_MATRIX         (1 << 0)
1872 
1873 /* Bit indicating that a matrix will or has changed its location or
1874    size.  */
1875 
1876 #define CHANGED_LEAF_MATRIX     (1 << 1)
1877 
1878 static struct dim
1879 allocate_matrices_for_frame_redisplay (window, x, y, dim_only_p,
1880                                        window_change_flags)
1881      Lisp_Object window;
1882      int x, y;
1883      int dim_only_p;
1884      int *window_change_flags;
1885 {
1886   struct frame *f = XFRAME (WINDOW_FRAME (XWINDOW (window)));
1887   int x0 = x, y0 = y;
1888   int wmax = 0, hmax = 0;
1889   struct dim total;
1890   struct dim dim;
1891   struct window *w;
1892   int in_horz_combination_p;
1893 
1894   /* What combination is WINDOW part of?  Compute this once since the
1895      result is the same for all windows in the `next' chain.  The
1896      special case of a root window (parent equal to nil) is treated
1897      like a vertical combination because a root window's `next'
1898      points to the mini-buffer window, if any, which is arranged
1899      vertically below other windows.  */
1900   in_horz_combination_p
1901     = (!NILP (XWINDOW (window)->parent)
1902        && !NILP (XWINDOW (XWINDOW (window)->parent)->hchild));
1903 
1904   /* For WINDOW and all windows on the same level.  */
1905   do
1906     {
1907       w = XWINDOW (window);
1908 
1909       /* Get the dimension of the window sub-matrix for W, depending
1910          on whether this is a combination or a leaf window.  */
1911       if (!NILP (w->hchild))
1912         dim = allocate_matrices_for_frame_redisplay (w->hchild, x, y,
1913                                                      dim_only_p,
1914                                                      window_change_flags);
1915       else if (!NILP (w->vchild))
1916         dim = allocate_matrices_for_frame_redisplay (w->vchild, x, y,
1917                                                      dim_only_p,
1918                                                      window_change_flags);
1919       else
1920         {
1921           /* If not already done, allocate sub-matrix structures.  */
1922           if (w->desired_matrix == NULL)
1923             {
1924               w->desired_matrix = new_glyph_matrix (f->desired_pool);
1925               w->current_matrix = new_glyph_matrix (f->current_pool);
1926               *window_change_flags |= NEW_LEAF_MATRIX;
1927             }
1928 
1929           /* Width and height MUST be chosen so that there are no
1930              holes in the frame matrix.  */
1931           dim.width = required_matrix_width (w);
1932           dim.height = required_matrix_height (w);
1933 
1934           /* Will matrix be re-allocated?  */
1935           if (x != w->desired_matrix->matrix_x
1936               || y != w->desired_matrix->matrix_y
1937               || dim.width != w->desired_matrix->matrix_w
1938               || dim.height != w->desired_matrix->matrix_h
1939               || (margin_glyphs_to_reserve (w, dim.width,
1940                                             w->left_margin_cols)
1941                   != w->desired_matrix->left_margin_glyphs)
1942               || (margin_glyphs_to_reserve (w, dim.width,
1943                                             w->right_margin_cols)
1944                   != w->desired_matrix->right_margin_glyphs))
1945             *window_change_flags |= CHANGED_LEAF_MATRIX;
1946 
1947           /* Actually change matrices, if allowed.  Do not consider
1948              CHANGED_LEAF_MATRIX computed above here because the pool
1949              may have been changed which we don't now here.  We trust
1950              that we only will be called with DIM_ONLY_P != 0 when
1951              necessary.  */
1952           if (!dim_only_p)
1953             {
1954               adjust_glyph_matrix (w, w->desired_matrix, x, y, dim);
1955               adjust_glyph_matrix (w, w->current_matrix, x, y, dim);
1956             }
1957         }
1958 
1959       /* If we are part of a horizontal combination, advance x for
1960          windows to the right of W; otherwise advance y for windows
1961          below W.  */
1962       if (in_horz_combination_p)
1963         x += dim.width;
1964       else
1965         y += dim.height;
1966 
1967       /* Remember maximum glyph matrix dimensions.  */
1968       wmax = max (wmax, dim.width);
1969       hmax = max (hmax, dim.height);
1970 
1971       /* Next window on same level.  */
1972       window = w->next;
1973     }
1974   while (!NILP (window));
1975 
1976   /* Set `total' to the total glyph matrix dimension of this window
1977      level.  In a vertical combination, the width is the width of the
1978      widest window; the height is the y we finally reached, corrected
1979      by the y we started with.  In a horizontal combination, the total
1980      height is the height of the tallest window, and the width is the
1981      x we finally reached, corrected by the x we started with.  */
1982   if (in_horz_combination_p)
1983     {
1984       total.width = x - x0;
1985       total.height = hmax;
1986     }
1987   else
1988     {
1989       total.width = wmax;
1990       total.height = y - y0;
1991     }
1992 
1993   return total;
1994 }
1995 
1996 
1997 /* Return the required height of glyph matrices for window W.  */
1998 
1999 int
2000 required_matrix_height (w)
2001      struct window *w;
2002 {
2003 #ifdef HAVE_WINDOW_SYSTEM
2004   struct frame *f = XFRAME (w->frame);
2005 
2006   if (FRAME_WINDOW_P (f))
2007     {
2008       int ch_height = FRAME_SMALLEST_FONT_HEIGHT (f);
2009       int window_pixel_height = window_box_height (w) + eabs (w->vscroll);
2010       return (((window_pixel_height + ch_height - 1)
2011                / ch_height) * w->nrows_scale_factor
2012               /* One partially visible line at the top and
2013                  bottom of the window.  */
2014               + 2
2015               /* 2 for header and mode line.  */
2016               + 2);
2017     }
2018 #endif /* HAVE_WINDOW_SYSTEM */
2019 
2020   return WINDOW_TOTAL_LINES (w);
2021 }
2022 
2023 
2024 /* Return the required width of glyph matrices for window W.  */
2025 
2026 int
2027 required_matrix_width (w)
2028      struct window *w;
2029 {
2030 #ifdef HAVE_WINDOW_SYSTEM
2031   struct frame *f = XFRAME (w->frame);
2032   if (FRAME_WINDOW_P (f))
2033     {
2034       int ch_width = FRAME_SMALLEST_CHAR_WIDTH (f);
2035       int window_pixel_width = WINDOW_TOTAL_WIDTH (w);
2036 
2037       /* Compute number of glyphs needed in a glyph row.  */
2038       return (((window_pixel_width + ch_width - 1)
2039                / ch_width) * w->ncols_scale_factor
2040               /* 2 partially visible columns in the text area.  */
2041               + 2
2042               /* One partially visible column at the right
2043                  edge of each marginal area.  */
2044               + 1 + 1);
2045     }
2046 #endif /* HAVE_WINDOW_SYSTEM */
2047 
2048   return XINT (w->total_cols);
2049 }
2050 
2051 
2052 /* Allocate window matrices for window-based redisplay.  W is the
2053    window whose matrices must be allocated/reallocated.  */
2054 
2055 static void
2056 allocate_matrices_for_window_redisplay (w)
2057      struct window *w;
2058 {
2059   while (w)
2060     {
2061       if (!NILP (w->vchild))
2062         allocate_matrices_for_window_redisplay (XWINDOW (w->vchild));
2063       else if (!NILP (w->hchild))
2064         allocate_matrices_for_window_redisplay (XWINDOW (w->hchild));
2065       else
2066         {
2067           /* W is a leaf window.  */
2068           struct dim dim;
2069 
2070           /* If matrices are not yet allocated, allocate them now.  */
2071           if (w->desired_matrix == NULL)
2072             {
2073               w->desired_matrix = new_glyph_matrix (NULL);
2074               w->current_matrix = new_glyph_matrix (NULL);
2075             }
2076 
2077           dim.width = required_matrix_width (w);
2078           dim.height = required_matrix_height (w);
2079           adjust_glyph_matrix (w, w->desired_matrix, 0, 0, dim);
2080           adjust_glyph_matrix (w, w->current_matrix, 0, 0, dim);
2081         }
2082 
2083       w = NILP (w->next) ? NULL : XWINDOW (w->next);
2084     }
2085 }
2086 
2087 
2088 /* Re-allocate/ re-compute glyph matrices on frame F.  If F is null,
2089    do it for all frames; otherwise do it just for the given frame.
2090    This function must be called when a new frame is created, its size
2091    changes, or its window configuration changes.  */
2092 
2093 void
2094 adjust_glyphs (f)
2095      struct frame *f;
2096 {
2097   /* Block input so that expose events and other events that access
2098      glyph matrices are not processed while we are changing them.  */
2099   BLOCK_INPUT;
2100 
2101   if (f)
2102     adjust_frame_glyphs (f);
2103   else
2104     {
2105       Lisp_Object tail, lisp_frame;
2106 
2107       FOR_EACH_FRAME (tail, lisp_frame)
2108         adjust_frame_glyphs (XFRAME (lisp_frame));
2109     }
2110 
2111   UNBLOCK_INPUT;
2112 }
2113 
2114 
2115 /* Adjust frame glyphs when Emacs is initialized.
2116 
2117    To be called from init_display.
2118 
2119    We need a glyph matrix because redraw will happen soon.
2120    Unfortunately, window sizes on selected_frame are not yet set to
2121    meaningful values.  I believe we can assume that there are only two
2122    windows on the frame---the mini-buffer and the root window.  Frame
2123    height and width seem to be correct so far.  So, set the sizes of
2124    windows to estimated values.  */
2125 
2126 static void
2127 adjust_frame_glyphs_initially ()
2128 {
2129   struct frame *sf = SELECTED_FRAME ();
2130   struct window *root = XWINDOW (sf->root_window);
2131   struct window *mini = XWINDOW (root->next);
2132   int frame_lines = FRAME_LINES (sf);
2133   int frame_cols = FRAME_COLS (sf);
2134   int top_margin = FRAME_TOP_MARGIN (sf);
2135 
2136   /* Do it for the root window.  */
2137   XSETFASTINT (root->top_line, top_margin);
2138   XSETFASTINT (root->total_cols, frame_cols);
2139   set_window_height (sf->root_window, frame_lines - 1 - top_margin, 0);
2140 
2141   /* Do it for the mini-buffer window.  */
2142   XSETFASTINT (mini->top_line, frame_lines - 1);
2143   XSETFASTINT (mini->total_cols, frame_cols);
2144   set_window_height (root->next, 1, 0);
2145 
2146   adjust_frame_glyphs (sf);
2147   glyphs_initialized_initially_p = 1;
2148 }
2149 
2150 
2151 /* Allocate/reallocate glyph matrices of a single frame F.  */
2152 
2153 static void
2154 adjust_frame_glyphs (f)
2155      struct frame *f;
2156 {
2157   if (FRAME_WINDOW_P (f))
2158     adjust_frame_glyphs_for_window_redisplay (f);
2159   else
2160     adjust_frame_glyphs_for_frame_redisplay (f);
2161 
2162   /* Don't forget the message buffer and the buffer for
2163      decode_mode_spec.  */
2164   adjust_frame_message_buffer (f);
2165   adjust_decode_mode_spec_buffer (f);
2166 
2167   f->glyphs_initialized_p = 1;
2168 }
2169 
2170 /* Return 1 if any window in the tree has nonzero window margins.  See
2171    the hack at the end of adjust_frame_glyphs_for_frame_redisplay.  */
2172 static int
2173 showing_window_margins_p (w)
2174      struct window *w;
2175 {
2176   while (w)
2177     {
2178       if (!NILP (w->hchild))
2179         {
2180           if (showing_window_margins_p (XWINDOW (w->hchild)))
2181             return 1;
2182         }
2183       else if (!NILP (w->vchild))
2184         {
2185           if (showing_window_margins_p (XWINDOW (w->vchild)))
2186             return 1;
2187         }
2188       else if (!NILP (w->left_margin_cols)
2189                || !NILP (w->right_margin_cols))
2190         return 1;
2191 
2192       w = NILP (w->next) ? 0 : XWINDOW (w->next);
2193     }
2194   return 0;
2195 }
2196 
2197 
2198 /* In the window tree with root W, build current matrices of leaf
2199    windows from the frame's current matrix.  */
2200 
2201 static void
2202 fake_current_matrices (window)
2203      Lisp_Object window;
2204 {
2205   struct window *w;
2206 
2207   for (; !NILP (window); window = w->next)
2208     {
2209       w = XWINDOW (window);
2210 
2211       if (!NILP (w->hchild))
2212         fake_current_matrices (w->hchild);
2213       else if (!NILP (w->vchild))
2214         fake_current_matrices (w->vchild);
2215       else
2216         {
2217           int i;
2218           struct frame *f = XFRAME (w->frame);
2219           struct glyph_matrix *m = w->current_matrix;
2220           struct glyph_matrix *fm = f->current_matrix;
2221 
2222           xassert (m->matrix_h == WINDOW_TOTAL_LINES (w));
2223           xassert (m->matrix_w == WINDOW_TOTAL_COLS (w));
2224 
2225           for (i = 0; i < m->matrix_h; ++i)
2226             {
2227               struct glyph_row *r = m->rows + i;
2228               struct glyph_row *fr = fm->rows + i + WINDOW_TOP_EDGE_LINE (w);
2229 
2230               xassert (r->glyphs[TEXT_AREA] >= fr->glyphs[TEXT_AREA]
2231                        && r->glyphs[LAST_AREA] <= fr->glyphs[LAST_AREA]);
2232 
2233               r->enabled_p = fr->enabled_p;
2234               if (r->enabled_p)
2235                 {
2236                   r->used[LEFT_MARGIN_AREA] = m->left_margin_glyphs;
2237                   r->used[RIGHT_MARGIN_AREA] = m->right_margin_glyphs;
2238                   r->used[TEXT_AREA] = (m->matrix_w
2239                                         - r->used[LEFT_MARGIN_AREA]
2240                                         - r->used[RIGHT_MARGIN_AREA]);
2241                   r->mode_line_p = 0;
2242                 }
2243             }
2244         }
2245     }
2246 }
2247 
2248 
2249 /* Save away the contents of frame F's current frame matrix.  Value is
2250    a glyph matrix holding the contents of F's current frame matrix.  */
2251 
2252 static struct glyph_matrix *
2253 save_current_matrix (f)
2254      struct frame *f;
2255 {
2256   int i;
2257   struct glyph_matrix *saved;
2258 
2259   saved = (struct glyph_matrix *) xmalloc (sizeof *saved);
2260   bzero (saved, sizeof *saved);
2261   saved->nrows = f->current_matrix->nrows;
2262   saved->rows = (struct glyph_row *) xmalloc (saved->nrows
2263                                               * sizeof *saved->rows);
2264   bzero (saved->rows, saved->nrows * sizeof *saved->rows);
2265 
2266   for (i = 0; i < saved->nrows; ++i)
2267     {
2268       struct glyph_row *from = f->current_matrix->rows + i;
2269       struct glyph_row *to = saved->rows + i;
2270       size_t nbytes = from->used[TEXT_AREA] * sizeof (struct glyph);
2271       to->glyphs[TEXT_AREA] = (struct glyph *) xmalloc (nbytes);
2272       bcopy (from->glyphs[TEXT_AREA], to->glyphs[TEXT_AREA], nbytes);
2273       to->used[TEXT_AREA] = from->used[TEXT_AREA];
2274     }
2275 
2276   return saved;
2277 }
2278 
2279 
2280 /* Restore the contents of frame F's current frame matrix from SAVED,
2281    and free memory associated with SAVED.  */
2282 
2283 static void
2284 restore_current_matrix (f, saved)
2285      struct frame *f;
2286      struct glyph_matrix *saved;
2287 {
2288   int i;
2289 
2290   for (i = 0; i < saved->nrows; ++i)
2291     {
2292       struct glyph_row *from = saved->rows + i;
2293       struct glyph_row *to = f->current_matrix->rows + i;
2294       size_t nbytes = from->used[TEXT_AREA] * sizeof (struct glyph);
2295       bcopy (from->glyphs[TEXT_AREA], to->glyphs[TEXT_AREA], nbytes);
2296       to->used[TEXT_AREA] = from->used[TEXT_AREA];
2297       xfree (from->glyphs[TEXT_AREA]);
2298     }
2299 
2300   xfree (saved->rows);
2301   xfree (saved);
2302 }
2303 
2304 
2305 
2306 /* Allocate/reallocate glyph matrices of a single frame F for
2307    frame-based redisplay.  */
2308 
2309 static void
2310 adjust_frame_glyphs_for_frame_redisplay (f)
2311      struct frame *f;
2312 {
2313   struct dim matrix_dim;
2314   int pool_changed_p;
2315   int window_change_flags;
2316   int top_window_y;
2317 
2318   if (!FRAME_LIVE_P (f))
2319     return;
2320 
2321   top_window_y = FRAME_TOP_MARGIN (f);
2322 
2323   /* Allocate glyph pool structures if not already done.  */
2324   if (f->desired_pool == NULL)
2325     {
2326       f->desired_pool = new_glyph_pool ();
2327       f->current_pool = new_glyph_pool ();
2328     }
2329 
2330   /* Allocate frames matrix structures if needed.  */
2331   if (f->desired_matrix == NULL)
2332     {
2333       f->desired_matrix = new_glyph_matrix (f->desired_pool);
2334       f->current_matrix = new_glyph_matrix (f->current_pool);
2335     }
2336 
2337   /* Compute window glyph matrices.  (This takes the mini-buffer
2338      window into account).  The result is the size of the frame glyph
2339      matrix needed.  The variable window_change_flags is set to a bit
2340      mask indicating whether new matrices will be allocated or
2341      existing matrices change their size or location within the frame
2342      matrix.  */
2343   window_change_flags = 0;
2344   matrix_dim
2345     = allocate_matrices_for_frame_redisplay (FRAME_ROOT_WINDOW (f),
2346                                              0, top_window_y,
2347                                              1,
2348                                              &window_change_flags);
2349 
2350   /* Add in menu bar lines, if any.  */
2351   matrix_dim.height += top_window_y;
2352 
2353   /* Enlarge pools as necessary.  */
2354   pool_changed_p = realloc_glyph_pool (f->desired_pool, matrix_dim);
2355   realloc_glyph_pool (f->current_pool, matrix_dim);
2356 
2357   /* Set up glyph pointers within window matrices.  Do this only if
2358      absolutely necessary since it requires a frame redraw.  */
2359   if (pool_changed_p || window_change_flags)
2360     {
2361       /* Do it for window matrices.  */
2362       allocate_matrices_for_frame_redisplay (FRAME_ROOT_WINDOW (f),
2363                                              0, top_window_y, 0,
2364                                              &window_change_flags);
2365 
2366       /* Size of frame matrices must equal size of frame.  Note
2367          that we are called for X frames with window widths NOT equal
2368          to the frame width (from CHANGE_FRAME_SIZE_1).  */
2369       xassert (matrix_dim.width == FRAME_COLS (f)
2370                && matrix_dim.height == FRAME_LINES (f));
2371 
2372       /* Pointers to glyph memory in glyph rows are exchanged during
2373          the update phase of redisplay, which means in general that a
2374          frame's current matrix consists of pointers into both the
2375          desired and current glyph pool of the frame.  Adjusting a
2376          matrix sets the frame matrix up so that pointers are all into
2377          the same pool.  If we want to preserve glyph contents of the
2378          current matrix over a call to adjust_glyph_matrix, we must
2379          make a copy of the current glyphs, and restore the current
2380          matrix' contents from that copy.  */
2381       if (display_completed
2382           && !FRAME_GARBAGED_P (f)
2383           && matrix_dim.width == f->current_matrix->matrix_w
2384           && matrix_dim.height == f->current_matrix->matrix_h
2385           /* For some reason, the frame glyph matrix gets corrupted if
2386              any of the windows contain margins.  I haven't been able
2387              to hunt down the reason, but for the moment this prevents
2388              the problem from manifesting. -- cyd  */
2389           && !showing_window_margins_p (XWINDOW (FRAME_ROOT_WINDOW (f))))
2390         {
2391           struct glyph_matrix *copy = save_current_matrix (f);
2392           adjust_glyph_matrix (NULL, f->desired_matrix, 0, 0, matrix_dim);
2393           adjust_glyph_matrix (NULL, f->current_matrix, 0, 0, matrix_dim);
2394           restore_current_matrix (f, copy);
2395           fake_current_matrices (FRAME_ROOT_WINDOW (f));
2396         }
2397       else
2398         {
2399           adjust_glyph_matrix (NULL, f->desired_matrix, 0, 0, matrix_dim);
2400           adjust_glyph_matrix (NULL, f->current_matrix, 0, 0, matrix_dim);
2401           SET_FRAME_GARBAGED (f);
2402         }
2403     }
2404 }
2405 
2406 
2407 /* Allocate/reallocate glyph matrices of a single frame F for
2408    window-based redisplay.  */
2409 
2410 static void
2411 adjust_frame_glyphs_for_window_redisplay (f)
2412      struct frame *f;
2413 {
2414   struct window *w;
2415 
2416   xassert (FRAME_WINDOW_P (f) && FRAME_LIVE_P (f));
2417 
2418   /* Allocate/reallocate window matrices.  */
2419   allocate_matrices_for_window_redisplay (XWINDOW (FRAME_ROOT_WINDOW (f)));
2420 
2421 #ifdef HAVE_X_WINDOWS
2422   /* Allocate/ reallocate matrices of the dummy window used to display
2423      the menu bar under X when no X toolkit support is available.  */
2424 #if ! defined (USE_X_TOOLKIT) && ! defined (USE_GTK)
2425   {
2426     /* Allocate a dummy window if not already done.  */
2427     if (NILP (f->menu_bar_window))
2428       {
2429         f->menu_bar_window = make_window ();
2430         w = XWINDOW (f->menu_bar_window);
2431         XSETFRAME (w->frame, f);
2432         w->pseudo_window_p = 1;
2433       }
2434     else
2435       w = XWINDOW (f->menu_bar_window);
2436 
2437     /* Set window dimensions to frame dimensions and allocate or
2438        adjust glyph matrices of W.  */
2439     XSETFASTINT (w->top_line, 0);
2440     XSETFASTINT (w->left_col, 0);
2441     XSETFASTINT (w->total_lines, FRAME_MENU_BAR_LINES (f));
2442     XSETFASTINT (w->total_cols, FRAME_TOTAL_COLS (f));
2443     allocate_matrices_for_window_redisplay (w);
2444   }
2445 #endif /* not USE_X_TOOLKIT && not USE_GTK */
2446 #endif /* HAVE_X_WINDOWS */
2447 
2448 #ifndef USE_GTK
2449   /* Allocate/ reallocate matrices of the tool bar window.  If we
2450      don't have a tool bar window yet, make one.  */
2451   if (NILP (f->tool_bar_window))
2452     {
2453       f->tool_bar_window = make_window ();
2454       w = XWINDOW (f->tool_bar_window);
2455       XSETFRAME (w->frame, f);
2456       w->pseudo_window_p = 1;
2457     }
2458   else
2459     w = XWINDOW (f->tool_bar_window);
2460 
2461   XSETFASTINT (w->top_line, FRAME_MENU_BAR_LINES (f));
2462   XSETFASTINT (w->left_col, 0);
2463   XSETFASTINT (w->total_lines, FRAME_TOOL_BAR_LINES (f));
2464   XSETFASTINT (w->total_cols, FRAME_TOTAL_COLS (f));
2465   allocate_matrices_for_window_redisplay (w);
2466 #endif
2467 }
2468 
2469 
2470 /* Adjust/ allocate message buffer of frame F.
2471 
2472    Note that the message buffer is never freed.  Since I could not
2473    find a free in 19.34, I assume that freeing it would be
2474    problematic in some way and don't do it either.
2475 
2476    (Implementation note: It should be checked if we can free it
2477    eventually without causing trouble).  */
2478 
2479 static void
2480 adjust_frame_message_buffer (f)
2481      struct frame *f;
2482 {
2483   int size = FRAME_MESSAGE_BUF_SIZE (f) + 1;
2484 
2485   if (FRAME_MESSAGE_BUF (f))
2486     {
2487       char *buffer = FRAME_MESSAGE_BUF (f);
2488       char *new_buffer = (char *) xrealloc (buffer, size);
2489       FRAME_MESSAGE_BUF (f) = new_buffer;
2490     }
2491   else
2492     FRAME_MESSAGE_BUF (f) = (char *) xmalloc (size);
2493 }
2494 
2495 
2496 /* Re-allocate buffer for decode_mode_spec on frame F.  */
2497 
2498 static void
2499 adjust_decode_mode_spec_buffer (f)
2500      struct frame *f;
2501 {
2502   f->decode_mode_spec_buffer
2503     = (char *) xrealloc (f->decode_mode_spec_buffer,
2504                          FRAME_MESSAGE_BUF_SIZE (f) + 1);
2505 }
2506 
2507 
2508 
2509 /**********************************************************************
2510                         Freeing Glyph Matrices
2511  **********************************************************************/
2512 
2513 /* Free glyph memory for a frame F.  F may be null.  This function can
2514    be called for the same frame more than once.  The root window of
2515    F may be nil when this function is called.  This is the case when
2516    the function is called when F is destroyed.  */
2517 
2518 void
2519 free_glyphs (f)
2520      struct frame *f;
2521 {
2522   if (f && f->glyphs_initialized_p)
2523     {
2524       /* Block interrupt input so that we don't get surprised by an X
2525          event while we're in an inconsistent state.  */
2526       BLOCK_INPUT;
2527       f->glyphs_initialized_p = 0;
2528 
2529       /* Release window sub-matrices.  */
2530       if (!NILP (f->root_window))
2531         free_window_matrices (XWINDOW (f->root_window));
2532 
2533       /* Free the dummy window for menu bars without X toolkit and its
2534          glyph matrices.  */
2535       if (!NILP (f->menu_bar_window))
2536         {
2537           struct window *w = XWINDOW (f->menu_bar_window);
2538           free_glyph_matrix (w->desired_matrix);
2539           free_glyph_matrix (w->current_matrix);
2540           w->desired_matrix = w->current_matrix = NULL;
2541           f->menu_bar_window = Qnil;
2542         }
2543 
2544       /* Free the tool bar window and its glyph matrices.  */
2545       if (!NILP (f->tool_bar_window))
2546         {
2547           struct window *w = XWINDOW (f->tool_bar_window);
2548           free_glyph_matrix (w->desired_matrix);
2549           free_glyph_matrix (w->current_matrix);
2550           w->desired_matrix = w->current_matrix = NULL;
2551           f->tool_bar_window = Qnil;
2552         }
2553 
2554       /* Release frame glyph matrices.  Reset fields to zero in
2555          case we are called a second time.  */
2556       if (f->desired_matrix)
2557         {
2558           free_glyph_matrix (f->desired_matrix);
2559           free_glyph_matrix (f->current_matrix);
2560           f->desired_matrix = f->current_matrix = NULL;
2561         }
2562 
2563       /* Release glyph pools.  */
2564       if (f->desired_pool)
2565         {
2566           free_glyph_pool (f->desired_pool);
2567           free_glyph_pool (f->current_pool);
2568           f->desired_pool = f->current_pool = NULL;
2569         }
2570 
2571       UNBLOCK_INPUT;
2572     }
2573 }
2574 
2575 
2576 /* Free glyph sub-matrices in the window tree rooted at W.  This
2577    function may be called with a null pointer, and it may be called on
2578    the same tree more than once.  */
2579 
2580 void
2581 free_window_matrices (w)
2582      struct window *w;
2583 {
2584   while (w)
2585     {
2586       if (!NILP (w->hchild))
2587         free_window_matrices (XWINDOW (w->hchild));
2588       else if (!NILP (w->vchild))
2589         free_window_matrices (XWINDOW (w->vchild));
2590       else
2591         {
2592           /* This is a leaf window.  Free its memory and reset fields
2593              to zero in case this function is called a second time for
2594              W.  */
2595           free_glyph_matrix (w->current_matrix);
2596           free_glyph_matrix (w->desired_matrix);
2597           w->current_matrix = w->desired_matrix = NULL;
2598         }
2599 
2600       /* Next window on same level.  */
2601       w = NILP (w->next) ? 0 : XWINDOW (w->next);
2602     }
2603 }
2604 
2605 
2606 /* Check glyph memory leaks.  This function is called from
2607    shut_down_emacs.  Note that frames are not destroyed when Emacs
2608    exits.  We therefore free all glyph memory for all active frames
2609    explicitly and check that nothing is left allocated.  */
2610 
2611 void
2612 check_glyph_memory ()
2613 {
2614   Lisp_Object tail, frame;
2615 
2616   /* Free glyph memory for all frames.  */
2617   FOR_EACH_FRAME (tail, frame)
2618     free_glyphs (XFRAME (frame));
2619 
2620   /* Check that nothing is left allocated.  */
2621   if (glyph_matrix_count)
2622     abort ();
2623   if (glyph_pool_count)
2624     abort ();
2625 }
2626 
2627 
2628 
2629 /**********************************************************************
2630                        Building a Frame Matrix
2631  **********************************************************************/
2632 
2633 /* Most of the redisplay code works on glyph matrices attached to
2634    windows.  This is a good solution most of the time, but it is not
2635    suitable for terminal code.  Terminal output functions cannot rely
2636    on being able to set an arbitrary terminal window.  Instead they
2637    must be provided with a view of the whole frame, i.e. the whole
2638    screen.  We build such a view by constructing a frame matrix from
2639    window matrices in this section.
2640 
2641    Windows that must be updated have their must_be_update_p flag set.
2642    For all such windows, their desired matrix is made part of the
2643    desired frame matrix.  For other windows, their current matrix is
2644    made part of the desired frame matrix.
2645 
2646    +-----------------+----------------+
2647    |     desired     |   desired      |
2648    |                 |                |
2649    +-----------------+----------------+
2650    |               current            |
2651    |                                  |
2652    +----------------------------------+
2653 
2654    Desired window matrices can be made part of the frame matrix in a
2655    cheap way: We exploit the fact that the desired frame matrix and
2656    desired window matrices share their glyph memory.  This is not
2657    possible for current window matrices.  Their glyphs are copied to
2658    the desired frame matrix.  The latter is equivalent to
2659    preserve_other_columns in the old redisplay.
2660 
2661    Used glyphs counters for frame matrix rows are the result of adding
2662    up glyph lengths of the window matrices.  A line in the frame
2663    matrix is enabled, if a corresponding line in a window matrix is
2664    enabled.
2665 
2666    After building the desired frame matrix, it will be passed to
2667    terminal code, which will manipulate both the desired and current
2668    frame matrix.  Changes applied to the frame's current matrix have
2669    to be visible in current window matrices afterwards, of course.
2670 
2671    This problem is solved like this:
2672 
2673    1. Window and frame matrices share glyphs.  Window matrices are
2674    constructed in a way that their glyph contents ARE the glyph
2675    contents needed in a frame matrix.  Thus, any modification of
2676    glyphs done in terminal code will be reflected in window matrices
2677    automatically.
2678 
2679    2. Exchanges of rows in a frame matrix done by terminal code are
2680    intercepted by hook functions so that corresponding row operations
2681    on window matrices can be performed.  This is necessary because we
2682    use pointers to glyphs in glyph row structures.  To satisfy the
2683    assumption of point 1 above that glyphs are updated implicitly in
2684    window matrices when they are manipulated via the frame matrix,
2685    window and frame matrix must of course agree where to find the
2686    glyphs for their rows.  Possible manipulations that must be
2687    mirrored are assignments of rows of the desired frame matrix to the
2688    current frame matrix and scrolling the current frame matrix.  */
2689 
2690 /* Build frame F's desired matrix from window matrices.  Only windows
2691    which have the flag must_be_updated_p set have to be updated.  Menu
2692    bar lines of a frame are not covered by window matrices, so make
2693    sure not to touch them in this function.  */
2694 
2695 static void
2696 build_frame_matrix (f)
2697      struct frame *f;
2698 {
2699   int i;
2700 
2701   /* F must have a frame matrix when this function is called.  */
2702   xassert (!FRAME_WINDOW_P (f));
2703 
2704   /* Clear all rows in the frame matrix covered by window matrices.
2705      Menu bar lines are not covered by windows.  */
2706   for (i = FRAME_TOP_MARGIN (f); i < f->desired_matrix->nrows; ++i)
2707     clear_glyph_row (MATRIX_ROW (f->desired_matrix, i));
2708 
2709   /* Build the matrix by walking the window tree.  */
2710   build_frame_matrix_from_window_tree (f->desired_matrix,
2711                                        XWINDOW (FRAME_ROOT_WINDOW (f)));
2712 }
2713 
2714 
2715 /* Walk a window tree, building a frame matrix MATRIX from window
2716    matrices.  W is the root of a window tree.  */
2717 
2718 static void
2719 build_frame_matrix_from_window_tree (matrix, w)
2720      struct glyph_matrix *matrix;
2721      struct window *w;
2722 {
2723   while (w)
2724     {
2725       if (!NILP (w->hchild))
2726         build_frame_matrix_from_window_tree (matrix, XWINDOW (w->hchild));
2727       else if (!NILP (w->vchild))
2728         build_frame_matrix_from_window_tree (matrix, XWINDOW (w->vchild));
2729       else
2730         build_frame_matrix_from_leaf_window (matrix, w);
2731 
2732       w = NILP (w->next) ? 0 : XWINDOW (w->next);
2733     }
2734 }
2735 
2736 
2737 /* Add a window's matrix to a frame matrix.  FRAME_MATRIX is the
2738    desired frame matrix built.  W is a leaf window whose desired or
2739    current matrix is to be added to FRAME_MATRIX.  W's flag
2740    must_be_updated_p determines which matrix it contributes to
2741    FRAME_MATRIX.  If must_be_updated_p is non-zero, W's desired matrix
2742    is added to FRAME_MATRIX, otherwise W's current matrix is added.
2743    Adding a desired matrix means setting up used counters and such in
2744    frame rows, while adding a current window matrix to FRAME_MATRIX
2745    means copying glyphs.  The latter case corresponds to
2746    preserve_other_columns in the old redisplay.  */
2747 
2748 static void
2749 build_frame_matrix_from_leaf_window (frame_matrix, w)
2750      struct glyph_matrix *frame_matrix;
2751      struct window *w;
2752 {
2753   struct glyph_matrix *window_matrix;
2754   int window_y, frame_y;
2755   /* If non-zero, a glyph to insert at the right border of W.  */
2756   GLYPH right_border_glyph;
2757 
2758   SET_GLYPH_FROM_CHAR (right_border_glyph, 0);
2759 
2760   /* Set window_matrix to the matrix we have to add to FRAME_MATRIX.  */
2761   if (w->must_be_updated_p)
2762     {
2763       window_matrix = w->desired_matrix;
2764 
2765       /* Decide whether we want to add a vertical border glyph.  */
2766       if (!WINDOW_RIGHTMOST_P (w))
2767         {
2768           struct Lisp_Char_Table *dp = window_display_table (w);
2769           Lisp_Object gc;
2770 
2771           SET_GLYPH_FROM_CHAR (right_border_glyph, '|');
2772           if (dp
2773               && (gc = DISP_BORDER_GLYPH (dp), GLYPH_CODE_P (gc))
2774               && GLYPH_CODE_CHAR_VALID_P (gc))
2775             {
2776               SET_GLYPH_FROM_GLYPH_CODE (right_border_glyph, gc);
2777               spec_glyph_lookup_face (w, &right_border_glyph);
2778             }
2779 
2780           if (GLYPH_FACE (right_border_glyph) <= 0)
2781             SET_GLYPH_FACE (right_border_glyph, VERTICAL_BORDER_FACE_ID);
2782         }
2783     }
2784   else
2785     window_matrix = w->current_matrix;
2786 
2787   /* For all rows in the window matrix and corresponding rows in the
2788      frame matrix.  */
2789   window_y = 0;
2790   frame_y = window_matrix->matrix_y;
2791   while (window_y < window_matrix->nrows)
2792     {
2793       struct glyph_row *frame_row = frame_matrix->rows + frame_y;
2794       struct glyph_row *window_row = window_matrix->rows + window_y;
2795       int current_row_p = window_matrix == w->current_matrix;
2796 
2797       /* Fill up the frame row with spaces up to the left margin of the
2798          window row.  */
2799       fill_up_frame_row_with_spaces (frame_row, window_matrix->matrix_x);
2800 
2801       /* Fill up areas in the window matrix row with spaces.  */
2802       fill_up_glyph_row_with_spaces (window_row);
2803 
2804       /* If only part of W's desired matrix has been built, and
2805          window_row wasn't displayed, use the corresponding current
2806          row instead.  */
2807       if (window_matrix == w->desired_matrix
2808           && !window_row->enabled_p)
2809         {
2810           window_row = w->current_matrix->rows + window_y;
2811           current_row_p = 1;
2812         }
2813 
2814       if (current_row_p)
2815         {
2816           /* Copy window row to frame row.  */
2817           bcopy (window_row->glyphs[0],
2818                  frame_row->glyphs[TEXT_AREA] + window_matrix->matrix_x,
2819                  window_matrix->matrix_w * sizeof (struct glyph));
2820         }
2821       else
2822         {
2823           xassert (window_row->enabled_p);
2824 
2825           /* Only when a desired row has been displayed, we want
2826              the corresponding frame row to be updated.  */
2827           frame_row->enabled_p = 1;
2828 
2829           /* Maybe insert a vertical border between horizontally adjacent
2830              windows.  */
2831           if (GLYPH_CHAR (right_border_glyph) != 0)
2832             {
2833               struct glyph *border = window_row->glyphs[LAST_AREA] - 1;
2834               SET_CHAR_GLYPH_FROM_GLYPH (*border, right_border_glyph);
2835             }
2836 
2837 #if GLYPH_DEBUG
2838           /* Window row window_y must be a slice of frame row
2839              frame_y.  */
2840           xassert (glyph_row_slice_p (window_row, frame_row));
2841 
2842           /* If rows are in sync, we don't have to copy glyphs because
2843              frame and window share glyphs.  */
2844 
2845           strcpy (w->current_matrix->method, w->desired_matrix->method);
2846           add_window_display_history (w, w->current_matrix->method, 0);
2847 #endif
2848         }
2849 
2850       /* Set number of used glyphs in the frame matrix.  Since we fill
2851          up with spaces, and visit leaf windows from left to right it
2852          can be done simply.  */
2853       frame_row->used[TEXT_AREA]
2854         = window_matrix->matrix_x + window_matrix->matrix_w;
2855 
2856       /* Next row.  */
2857       ++window_y;
2858       ++frame_y;
2859     }
2860 }
2861 
2862 /* Given a user-specified glyph, possibly including a Lisp-level face
2863    ID, return a glyph that has a realized face ID.
2864    This is used for glyphs displayed specially and not part of the text;
2865    for instance, vertical separators, truncation markers, etc.  */
2866 
2867 void
2868 spec_glyph_lookup_face (w, glyph)
2869      struct window *w;
2870      GLYPH *glyph;
2871 {
2872   int lface_id = GLYPH_FACE (*glyph);
2873   /* Convert the glyph's specified face to a realized (cache) face.  */
2874   if (lface_id > 0)
2875     {
2876       int face_id = merge_faces (XFRAME (w->frame),
2877                                  Qt, lface_id, DEFAULT_FACE_ID);
2878       SET_GLYPH_FACE (*glyph, face_id);
2879     }
2880 }
2881 
2882 /* Add spaces to a glyph row ROW in a window matrix.
2883 
2884    Each row has the form:
2885 
2886    +---------+-----------------------------+------------+
2887    | left    |  text                       | right      |
2888    +---------+-----------------------------+------------+
2889 
2890    Left and right marginal areas are optional.  This function adds
2891    spaces to areas so that there are no empty holes between areas.
2892    In other words:  If the right area is not empty, the text area
2893    is filled up with spaces up to the right area.   If the text area
2894    is not empty, the left area is filled up.
2895 
2896    To be called for frame-based redisplay, only.  */
2897 
2898 static void
2899 fill_up_glyph_row_with_spaces (row)
2900      struct glyph_row *row;
2901 {
2902   fill_up_glyph_row_area_with_spaces (row, LEFT_MARGIN_AREA);
2903   fill_up_glyph_row_area_with_spaces (row, TEXT_AREA);
2904   fill_up_glyph_row_area_with_spaces (row, RIGHT_MARGIN_AREA);
2905 }
2906 
2907 
2908 /* Fill area AREA of glyph row ROW with spaces.  To be called for
2909    frame-based redisplay only.  */
2910 
2911 static void
2912 fill_up_glyph_row_area_with_spaces (row, area)
2913      struct glyph_row *row;
2914      int area;
2915 {
2916   if (row->glyphs[area] < row->glyphs[area + 1])
2917     {
2918       struct glyph *end = row->glyphs[area + 1];
2919       struct glyph *text = row->glyphs[area] + row->used[area];
2920 
2921       while (text < end)
2922         *text++ = space_glyph;
2923       row->used[area] = text - row->glyphs[area];
2924     }
2925 }
2926 
2927 
2928 /* Add spaces to the end of ROW in a frame matrix until index UPTO is
2929    reached.  In frame matrices only one area, TEXT_AREA, is used.  */
2930 
2931 static void
2932 fill_up_frame_row_with_spaces (row, upto)
2933      struct glyph_row *row;
2934      int upto;
2935 {
2936   int i = row->used[TEXT_AREA];
2937   struct glyph *glyph = row->glyphs[TEXT_AREA];
2938 
2939   while (i < upto)
2940     glyph[i++] = space_glyph;
2941 
2942   row->used[TEXT_AREA] = i;
2943 }
2944 
2945 
2946 
2947 /**********************************************************************
2948       Mirroring operations on frame matrices in window matrices
2949  **********************************************************************/
2950 
2951 /* Set frame being updated via frame-based redisplay to F.  This
2952    function must be called before updates to make explicit that we are
2953    working on frame matrices or not.  */
2954 
2955 static INLINE void
2956 set_frame_matrix_frame (f)
2957      struct frame *f;
2958 {
2959   frame_matrix_frame = f;
2960 }
2961 
2962 
2963 /* Make sure glyph row ROW in CURRENT_MATRIX is up to date.
2964    DESIRED_MATRIX is the desired matrix corresponding to
2965    CURRENT_MATRIX.  The update is done by exchanging glyph pointers
2966    between rows in CURRENT_MATRIX and DESIRED_MATRIX.  If
2967    frame_matrix_frame is non-null, this indicates that the exchange is
2968    done in frame matrices, and that we have to perform analogous
2969    operations in window matrices of frame_matrix_frame.  */
2970 
2971 static INLINE void
2972 make_current (desired_matrix, current_matrix, row)
2973      struct glyph_matrix *desired_matrix, *current_matrix;
2974      int row;
2975 {
2976   struct glyph_row *current_row = MATRIX_ROW (current_matrix, row);
2977   struct glyph_row *desired_row = MATRIX_ROW (desired_matrix, row);
2978   int mouse_face_p = current_row->mouse_face_p;
2979 
2980   /* Do current_row = desired_row.  This exchanges glyph pointers
2981      between both rows, and does a structure assignment otherwise.  */
2982   assign_row (current_row, desired_row);
2983 
2984   /* Enable current_row to mark it as valid.  */
2985   current_row->enabled_p = 1;
2986   current_row->mouse_face_p = mouse_face_p;
2987 
2988   /* If we are called on frame matrices, perform analogous operations
2989      for window matrices.  */
2990   if (frame_matrix_frame)
2991     mirror_make_current (XWINDOW (frame_matrix_frame->root_window), row);
2992 }
2993 
2994 
2995 /* W is the root of a window tree.  FRAME_ROW is the index of a row in
2996    W's frame which has been made current (by swapping pointers between
2997    current and desired matrix).  Perform analogous operations in the
2998    matrices of leaf windows in the window tree rooted at W.  */
2999 
3000 static void
3001 mirror_make_current (w, frame_row)
3002      struct window *w;
3003      int frame_row;
3004 {
3005   while (w)
3006     {
3007       if (!NILP (w->hchild))
3008         mirror_make_current (XWINDOW (w->hchild), frame_row);
3009       else if (!NILP (w->vchild))
3010         mirror_make_current (XWINDOW (w->vchild), frame_row);
3011       else
3012         {
3013           /* Row relative to window W.  Don't use FRAME_TO_WINDOW_VPOS
3014              here because the checks performed in debug mode there
3015              will not allow the conversion.  */
3016           int row = frame_row - w->desired_matrix->matrix_y;
3017 
3018           /* If FRAME_ROW is within W, assign the desired row to the
3019              current row (exchanging glyph pointers).  */
3020           if (row >= 0 && row < w->desired_matrix->matrix_h)
3021             {
3022               struct glyph_row *current_row
3023                 = MATRIX_ROW (w->current_matrix, row);
3024               struct glyph_row *desired_row
3025                 = MATRIX_ROW (w->desired_matrix, row);
3026 
3027               if (desired_row->enabled_p)
3028                 assign_row (current_row, desired_row);
3029               else
3030                 swap_glyph_pointers (desired_row, current_row);
3031               current_row->enabled_p = 1;
3032             }
3033         }
3034 
3035       w = NILP (w->next) ? 0 : XWINDOW (w->next);
3036     }
3037 }
3038 
3039 
3040 /* Perform row dance after scrolling.  We are working on the range of
3041    lines UNCHANGED_AT_TOP + 1 to UNCHANGED_AT_TOP + NLINES (not
3042    including) in MATRIX.  COPY_FROM is a vector containing, for each
3043    row I in the range 0 <= I < NLINES, the index of the original line
3044    to move to I.  This index is relative to the row range, i.e. 0 <=
3045    index < NLINES.  RETAINED_P is a vector containing zero for each
3046    row 0 <= I < NLINES which is empty.
3047 
3048    This function is called from do_scrolling and do_direct_scrolling.  */
3049 
3050 void
3051 mirrored_line_dance (matrix, unchanged_at_top, nlines, copy_from,
3052                      retained_p)
3053      struct glyph_matrix *matrix;
3054      int unchanged_at_top, nlines;
3055      int *copy_from;
3056      char *retained_p;
3057 {
3058   /* A copy of original rows.  */
3059   struct glyph_row *old_rows;
3060 
3061   /* Rows to assign to.  */
3062   struct glyph_row *new_rows = MATRIX_ROW (matrix, unchanged_at_top);
3063 
3064   int i;
3065 
3066   /* Make a copy of the original rows.  */
3067   old_rows = (struct glyph_row *) alloca (nlines * sizeof *old_rows);
3068   bcopy (new_rows, old_rows, nlines * sizeof *old_rows);
3069 
3070   /* Assign new rows, maybe clear lines.  */
3071   for (i = 0; i < nlines; ++i)
3072     {
3073       int enabled_before_p = new_rows[i].enabled_p;
3074 
3075       xassert (i + unchanged_at_top < matrix->nrows);
3076       xassert (unchanged_at_top + copy_from[i] < matrix->nrows);
3077       new_rows[i] = old_rows[copy_from[i]];
3078       new_rows[i].enabled_p = enabled_before_p;
3079 
3080       /* RETAINED_P is zero for empty lines.  */
3081       if (!retained_p[copy_from[i]])
3082         new_rows[i].enabled_p = 0;
3083     }
3084 
3085   /* Do the same for window matrices, if MATRIX is a frame matrix.  */
3086   if (frame_matrix_frame)
3087     mirror_line_dance (XWINDOW (frame_matrix_frame->root_window),
3088                        unchanged_at_top, nlines, copy_from, retained_p);
3089 }
3090 
3091 
3092 /* Synchronize glyph pointers in the current matrix of window W with
3093    the current frame matrix.  */
3094 
3095 static void
3096 sync_window_with_frame_matrix_rows (w)
3097      struct window *w;
3098 {
3099   struct frame *f = XFRAME (w->frame);
3100   struct glyph_row *window_row, *window_row_end, *frame_row;
3101   int left, right, x, width;
3102 
3103   /* Preconditions: W must be a leaf window on a tty frame.  */
3104   xassert (NILP (w->hchild) && NILP (w->vchild));
3105   xassert (!FRAME_WINDOW_P (f));
3106 
3107   left = margin_glyphs_to_reserve (w, 1, w->left_margin_cols);
3108   right = margin_glyphs_to_reserve (w, 1, w->right_margin_cols);
3109   x = w->current_matrix->matrix_x;
3110   width = w->current_matrix->matrix_w;
3111 
3112   window_row = w->current_matrix->rows;
3113   window_row_end = window_row + w->current_matrix->nrows;
3114   frame_row = f->current_matrix->rows + WINDOW_TOP_EDGE_LINE (w);
3115 
3116   for (; window_row < window_row_end; ++window_row, ++frame_row)
3117     {
3118       window_row->glyphs[LEFT_MARGIN_AREA]
3119         = frame_row->glyphs[0] + x;
3120       window_row->glyphs[TEXT_AREA]
3121         = window_row->glyphs[LEFT_MARGIN_AREA] + left;
3122       window_row->glyphs[LAST_AREA]
3123         = window_row->glyphs[LEFT_MARGIN_AREA] + width;
3124       window_row->glyphs[RIGHT_MARGIN_AREA]
3125         = window_row->glyphs[LAST_AREA] - right;
3126     }
3127 }
3128 
3129 
3130 /* Return the window in the window tree rooted in W containing frame
3131    row ROW.  Value is null if none is found.  */
3132 
3133 struct window *
3134 frame_row_to_window (w, row)
3135      struct window *w;
3136      int row;
3137 {
3138   struct window *found = NULL;
3139 
3140   while (w && !found)
3141     {
3142       if (!NILP (w->hchild))
3143         found = frame_row_to_window (XWINDOW (w->hchild), row);
3144       else if (!NILP (w->vchild))
3145         found = frame_row_to_window (XWINDOW (w->vchild), row);
3146       else if (row >= WINDOW_TOP_EDGE_LINE (w)
3147                && row < WINDOW_BOTTOM_EDGE_LINE (w))
3148         found = w;
3149 
3150       w = NILP (w->next) ? 0 : XWINDOW (w->next);
3151     }
3152 
3153   return found;
3154 }
3155 
3156 
3157 /* Perform a line dance in the window tree rooted at W, after
3158    scrolling a frame matrix in mirrored_line_dance.
3159 
3160    We are working on the range of lines UNCHANGED_AT_TOP + 1 to
3161    UNCHANGED_AT_TOP + NLINES (not including) in W's frame matrix.
3162    COPY_FROM is a vector containing, for each row I in the range 0 <=
3163    I < NLINES, the index of the original line to move to I.  This
3164    index is relative to the row range, i.e. 0 <= index < NLINES.
3165    RETAINED_P is a vector containing zero for each row 0 <= I < NLINES
3166    which is empty.  */
3167 
3168 static void
3169 mirror_line_dance (w, unchanged_at_top, nlines, copy_from, retained_p)
3170      struct window *w;
3171      int unchanged_at_top, nlines;
3172      int *copy_from;
3173      char *retained_p;
3174 {
3175   while (w)
3176     {
3177       if (!NILP (w->hchild))
3178         mirror_line_dance (XWINDOW (w->hchild), unchanged_at_top,
3179                            nlines, copy_from, retained_p);
3180       else if (!NILP (w->vchild))
3181         mirror_line_dance (XWINDOW (w->vchild), unchanged_at_top,
3182                            nlines, copy_from, retained_p);
3183       else
3184         {
3185           /* W is a leaf window, and we are working on its current
3186              matrix m.  */
3187           struct glyph_matrix *m = w->current_matrix;
3188           int i, sync_p = 0;
3189           struct glyph_row *old_rows;
3190 
3191           /* Make a copy of the original rows of matrix m.  */
3192           old_rows = (struct glyph_row *) alloca (m->nrows * sizeof *old_rows);
3193           bcopy (m->rows, old_rows, m->nrows * sizeof *old_rows);
3194 
3195           for (i = 0; i < nlines; ++i)
3196             {
3197               /* Frame relative line assigned to.  */
3198               int frame_to = i + unchanged_at_top;
3199 
3200               /* Frame relative line assigned.  */
3201               int frame_from = copy_from[i] + unchanged_at_top;
3202 
3203               /* Window relative line assigned to.  */
3204               int window_to = frame_to - m->matrix_y;
3205 
3206               /* Window relative line assigned.  */
3207               int window_from = frame_from - m->matrix_y;
3208 
3209               /* Is assigned line inside window?  */
3210               int from_inside_window_p
3211                 = window_from >= 0 && window_from < m->matrix_h;
3212 
3213               /* Is assigned to line inside window?  */
3214               int to_inside_window_p
3215                 = window_to >= 0 && window_to < m->matrix_h;
3216 
3217               if (from_inside_window_p && to_inside_window_p)
3218                 {
3219                   /* Enabled setting before assignment.  */
3220                   int enabled_before_p;
3221 
3222                   /* Do the assignment.  The enabled_p flag is saved
3223                      over the assignment because the old redisplay did
3224                      that.  */
3225                   enabled_before_p = m->rows[window_to].enabled_p;
3226                   m->rows[window_to] = old_rows[window_from];
3227                   m->rows[window_to].enabled_p = enabled_before_p;
3228 
3229                   /* If frame line is empty, window line is empty, too.  */
3230                   if (!retained_p[copy_from[i]])
3231                     m->rows[window_to].enabled_p = 0;
3232                 }
3233               else if (to_inside_window_p)
3234                 {
3235                   /* A copy between windows.  This is an infrequent
3236                      case not worth optimizing.  */
3237                   struct frame *f = XFRAME (w->frame);
3238                   struct window *root = XWINDOW (FRAME_ROOT_WINDOW (f));
3239                   struct window *w2;
3240                   struct glyph_matrix *m2;
3241                   int m2_from;
3242 
3243                   w2 = frame_row_to_window (root, frame_from);
3244                   /* ttn@surf.glug.org: when enabling menu bar using `emacs
3245                      -nw', FROM_FRAME sometimes has no associated window.
3246                      This check avoids a segfault if W2 is null.  */
3247                   if (w2)
3248                     {
3249                       m2 = w2->current_matrix;
3250                       m2_from = frame_from - m2->matrix_y;
3251                       copy_row_except_pointers (m->rows + window_to,
3252                                                 m2->rows + m2_from);
3253 
3254                       /* If frame line is empty, window line is empty, too.  */
3255                       if (!retained_p[copy_from[i]])
3256                         m->rows[window_to].enabled_p = 0;
3257                     }
3258                   sync_p = 1;
3259                 }
3260               else if (from_inside_window_p)
3261                 sync_p = 1;
3262             }
3263 
3264           /* If there was a copy between windows, make sure glyph
3265              pointers are in sync with the frame matrix.  */
3266           if (sync_p)
3267             sync_window_with_frame_matrix_rows (w);
3268 
3269           /* Check that no pointers are lost.  */
3270           CHECK_MATRIX (m);
3271         }
3272 
3273       /* Next window on same level.  */
3274       w = NILP (w->next) ? 0 : XWINDOW (w->next);
3275     }
3276 }
3277 
3278 
3279 #if GLYPH_DEBUG
3280 
3281 /* Check that window and frame matrices agree about their
3282    understanding where glyphs of the rows are to find.  For each
3283    window in the window tree rooted at W, check that rows in the
3284    matrices of leaf window agree with their frame matrices about
3285    glyph pointers.  */
3286 
3287 void
3288 check_window_matrix_pointers (w)
3289      struct window *w;
3290 {
3291   while (w)
3292     {
3293       if (!NILP (w->hchild))
3294         check_window_matrix_pointers (XWINDOW (w->hchild));
3295       else if (!NILP (w->vchild))
3296         check_window_matrix_pointers (XWINDOW (w->vchild));
3297       else
3298         {
3299           struct frame *f = XFRAME (w->frame);
3300           check_matrix_pointers (w->desired_matrix, f->desired_matrix);
3301           check_matrix_pointers (w->current_matrix, f->current_matrix);
3302         }
3303 
3304       w = NILP (w->next) ? 0 : XWINDOW (w->next);
3305     }
3306 }
3307 
3308 
3309 /* Check that window rows are slices of frame rows.  WINDOW_MATRIX is
3310    a window and FRAME_MATRIX is the corresponding frame matrix.  For
3311    each row in WINDOW_MATRIX check that it's a slice of the
3312    corresponding frame row.  If it isn't, abort.  */
3313 
3314 static void
3315 check_matrix_pointers (window_matrix, frame_matrix)
3316      struct glyph_matrix *window_matrix, *frame_matrix;
3317 {
3318   /* Row number in WINDOW_MATRIX.  */
3319   int i = 0;
3320 
3321   /* Row number corresponding to I in FRAME_MATRIX.  */
3322   int j = window_matrix->matrix_y;
3323 
3324   /* For all rows check that the row in the window matrix is a
3325      slice of the row in the frame matrix.  If it isn't we didn't
3326      mirror an operation on the frame matrix correctly.  */
3327   while (i < window_matrix->nrows)
3328     {
3329       if (!glyph_row_slice_p (window_matrix->rows + i,
3330                               frame_matrix->rows + j))
3331         abort ();
3332       ++i, ++j;
3333     }
3334 }
3335 
3336 #endif /* GLYPH_DEBUG != 0 */
3337 
3338 
3339 
3340 /**********************************************************************
3341                       VPOS and HPOS translations
3342  **********************************************************************/
3343 
3344 #if GLYPH_DEBUG
3345 
3346 /* Translate vertical position VPOS which is relative to window W to a
3347    vertical position relative to W's frame.  */
3348 
3349 static int
3350 window_to_frame_vpos (w, vpos)
3351      struct window *w;
3352      int vpos;
3353 {
3354   struct frame *f = XFRAME (w->frame);
3355 
3356   xassert (!FRAME_WINDOW_P (f));
3357   xassert (vpos >= 0 && vpos <= w->desired_matrix->nrows);
3358   vpos += WINDOW_TOP_EDGE_LINE (w);
3359   xassert (vpos >= 0 && vpos <= FRAME_LINES (f));
3360   return vpos;
3361 }
3362 
3363 
3364 /* Translate horizontal position HPOS which is relative to window W to
3365    a horizontal position relative to W's frame.  */
3366 
3367 static int
3368 window_to_frame_hpos (w, hpos)
3369      struct window *w;
3370      int hpos;
3371 {
3372   xassert (!FRAME_WINDOW_P (XFRAME (w->frame)));
3373   hpos += WINDOW_LEFT_EDGE_COL (w);
3374   return hpos;
3375 }
3376 
3377 #endif /* GLYPH_DEBUG */
3378 
3379 
3380 
3381 /**********************************************************************
3382                             Redrawing Frames
3383  **********************************************************************/
3384 
3385 DEFUN ("redraw-frame", Fredraw_frame, Sredraw_frame, 1, 1, 0,
3386        doc: /* Clear frame FRAME and output again what is supposed to appear on it.  */)
3387      (frame)
3388      Lisp_Object frame;
3389 {
3390   struct frame *f;
3391 
3392   CHECK_LIVE_FRAME (frame);
3393   f = XFRAME (frame);
3394 
3395   /* Ignore redraw requests, if frame has no glyphs yet.
3396      (Implementation note: It still has to be checked why we are
3397      called so early here).  */
3398   if (!glyphs_initialized_initially_p)
3399     return Qnil;
3400 
3401   update_begin (f);
3402 #ifdef MSDOS
3403   if (FRAME_MSDOS_P (f))
3404     FRAME_TERMINAL (f)->set_terminal_modes_hook (FRAME_TERMINAL (f));
3405 #endif
3406   clear_frame (f);
3407   clear_current_matrices (f);
3408   update_end (f);
3409   if (FRAME_TERMCAP_P (f))
3410     fflush (FRAME_TTY (f)->output);
3411   windows_or_buffers_changed++;
3412   /* Mark all windows as inaccurate, so that every window will have
3413      its redisplay done.  */
3414   mark_window_display_accurate (FRAME_ROOT_WINDOW (f), 0);
3415   set_window_update_flags (XWINDOW (FRAME_ROOT_WINDOW (f)), 1);
3416   f->garbaged = 0;
3417   return Qnil;
3418 }
3419 
3420 
3421 /* Redraw frame F.  This is nothing more than a call to the Lisp
3422    function redraw-frame.  */
3423 
3424 void
3425 redraw_frame (f)
3426      struct frame *f;
3427 {
3428   Lisp_Object frame;
3429   XSETFRAME (frame, f);
3430   Fredraw_frame (frame);
3431 }
3432 
3433 
3434 DEFUN ("redraw-display", Fredraw_display, Sredraw_display, 0, 0, "",
3435        doc: /* Clear and redisplay all visible frames.  */)
3436      ()
3437 {
3438   Lisp_Object tail, frame;
3439 
3440   FOR_EACH_FRAME (tail, frame)
3441     if (FRAME_VISIBLE_P (XFRAME (frame)))
3442       Fredraw_frame (frame);
3443 
3444   return Qnil;
3445 }
3446 
3447 
3448 /* This is used when frame_garbaged is set.  Call Fredraw_frame on all
3449    visible frames marked as garbaged.  */
3450 
3451 void
3452 redraw_garbaged_frames ()
3453 {
3454   Lisp_Object tail, frame;
3455 
3456   FOR_EACH_FRAME (tail, frame)
3457     if (FRAME_VISIBLE_P (XFRAME (frame))
3458         && FRAME_GARBAGED_P (XFRAME (frame)))
3459       Fredraw_frame (frame);
3460 }
3461 
3462 
3463 
3464 /***********************************************************************
3465                              Frame Update
3466  ***********************************************************************/
3467 
3468 /* Update frame F based on the data in desired matrices.
3469 
3470    If FORCE_P is non-zero, don't let redisplay be stopped by detecting
3471    pending input.  If INHIBIT_HAIRY_ID_P is non-zero, don't try
3472    scrolling.
3473 
3474    Value is non-zero if redisplay was stopped due to pending input.  */
3475 
3476 int
3477 update_frame (f, force_p, inhibit_hairy_id_p)
3478      struct frame *f;
3479      int force_p;
3480      int inhibit_hairy_id_p;
3481 {
3482   /* 1 means display has been paused because of pending input.  */
3483   int paused_p;
3484   struct window *root_window = XWINDOW (f->root_window);
3485 
3486   if (redisplay_dont_pause)
3487     force_p = 1;
3488 #if PERIODIC_PREEMPTION_CHECKING
3489   else if (NILP (Vredisplay_preemption_period))
3490     force_p = 1;
3491   else if (!force_p && NUMBERP (Vredisplay_preemption_period))
3492     {
3493       EMACS_TIME tm;
3494       double p = XFLOATINT (Vredisplay_preemption_period);
3495       int sec, usec;
3496 
3497       if (detect_input_pending_ignore_squeezables ())
3498         {
3499           paused_p = 1;
3500           goto do_pause;
3501         }
3502 
3503       sec = (int) p;
3504       usec = (p - sec) * 1000000;
3505 
3506       EMACS_GET_TIME (tm);
3507       EMACS_SET_SECS_USECS (preemption_period, sec, usec);
3508       EMACS_ADD_TIME (preemption_next_check, tm, preemption_period);
3509     }
3510 #endif
3511 
3512   if (FRAME_WINDOW_P (f))
3513     {
3514       /* We are working on window matrix basis.  All windows whose
3515          flag must_be_updated_p is set have to be updated.  */
3516 
3517       /* Record that we are not working on frame matrices.  */
3518       set_frame_matrix_frame (NULL);
3519 
3520       /* Update all windows in the window tree of F, maybe stopping
3521          when pending input is detected.  */
3522       update_begin (f);
3523 
3524       /* Update the menu bar on X frames that don't have toolkit
3525          support.  */
3526       if (WINDOWP (f->menu_bar_window))
3527         update_window (XWINDOW (f->menu_bar_window), 1);
3528 
3529       /* Update the tool-bar window, if present.  */
3530       if (WINDOWP (f->tool_bar_window))
3531         {
3532           struct window *w = XWINDOW (f->tool_bar_window);
3533 
3534           /* Update tool-bar window.  */
3535           if (w->must_be_updated_p)
3536             {
3537               Lisp_Object tem;
3538 
3539               update_window (w, 1);
3540               w->must_be_updated_p = 0;
3541 
3542               /* Swap tool-bar strings.  We swap because we want to
3543                  reuse strings.  */
3544               tem = f->current_tool_bar_string;
3545               f->current_tool_bar_string = f->desired_tool_bar_string;
3546               f->desired_tool_bar_string = tem;
3547             }
3548         }
3549 
3550 
3551       /* Update windows.  */
3552       paused_p = update_window_tree (root_window, force_p);
3553       update_end (f);
3554 
3555       /* This flush is a performance bottleneck under X,
3556          and it doesn't seem to be necessary anyway (in general).
3557          It is necessary when resizing the window with the mouse, or
3558          at least the fringes are not redrawn in a timely manner.  ++kfs */
3559       if (f->force_flush_display_p)
3560         {
3561           FRAME_RIF (f)->flush_display (f);
3562           f->force_flush_display_p = 0;
3563         }
3564     }
3565   else
3566     {
3567       /* We are working on frame matrix basis.  Set the frame on whose
3568          frame matrix we operate.  */
3569       set_frame_matrix_frame (f);
3570 
3571       /* Build F's desired matrix from window matrices.  */
3572       build_frame_matrix (f);
3573 
3574       /* Update the display  */
3575       update_begin (f);
3576       paused_p = update_frame_1 (f, force_p, inhibit_hairy_id_p);
3577       update_end (f);
3578 
3579       if (FRAME_TERMCAP_P (f) || FRAME_MSDOS_P (f))
3580         {
3581           if (FRAME_TTY (f)->termscript)
3582             fflush (FRAME_TTY (f)->termscript);
3583           if (FRAME_TERMCAP_P (f))
3584             fflush (FRAME_TTY (f)->output);
3585         }
3586 
3587       /* Check window matrices for lost pointers.  */
3588 #if GLYPH_DEBUG
3589       check_window_matrix_pointers (root_window);
3590       add_frame_display_history (f, paused_p);
3591 #endif
3592     }
3593 
3594  do_pause:
3595   /* Reset flags indicating that a window should be updated.  */
3596   set_window_update_flags (root_window, 0);
3597 
3598   display_completed = !paused_p;
3599   return paused_p;
3600 }
3601 
3602 
3603 
3604 /************************************************************************
3605                          Window-based updates
3606  ************************************************************************/
3607 
3608 /* Perform updates in window tree rooted at W.  FORCE_P non-zero means
3609    don't stop updating when input is pending.  */
3610 
3611 static int
3612 update_window_tree (w, force_p)
3613      struct window *w;
3614      int force_p;
3615 {
3616   int paused_p = 0;
3617 
3618   while (w && !paused_p)
3619     {
3620       if (!NILP (w->hchild))
3621         paused_p |= update_window_tree (XWINDOW (w->hchild), force_p);
3622       else if (!NILP (w->vchild))
3623         paused_p |= update_window_tree (XWINDOW (w->vchild), force_p);
3624       else if (w->must_be_updated_p)
3625         paused_p |= update_window (w, force_p);
3626 
3627       w = NILP (w->next) ? 0 : XWINDOW (w->next);
3628     }
3629 
3630   return paused_p;
3631 }
3632 
3633 
3634 /* Update window W if its flag must_be_updated_p is non-zero.  If
3635    FORCE_P is non-zero, don't stop updating if input is pending.  */
3636 
3637 void
3638 update_single_window (w, force_p)
3639      struct window *w;
3640      int force_p;
3641 {
3642   if (w->must_be_updated_p)
3643     {
3644       struct frame *f = XFRAME (WINDOW_FRAME (w));
3645 
3646       /* Record that this is not a frame-based redisplay.  */
3647       set_frame_matrix_frame (NULL);
3648 
3649       if (redisplay_dont_pause)
3650         force_p = 1;
3651 #if PERIODIC_PREEMPTION_CHECKING
3652       else if (NILP (Vredisplay_preemption_period))
3653         force_p = 1;
3654       else if (!force_p && NUMBERP (Vredisplay_preemption_period))
3655         {
3656           EMACS_TIME tm;
3657           double p = XFLOATINT (Vredisplay_preemption_period);
3658           int sec, usec;
3659 
3660           sec = (int) p;
3661           usec = (p - sec) * 1000000;
3662 
3663           EMACS_GET_TIME (tm);
3664           EMACS_SET_SECS_USECS (preemption_period, sec, usec);
3665           EMACS_ADD_TIME (preemption_next_check, tm, preemption_period);
3666         }
3667 #endif
3668 
3669       /* Update W.  */
3670       update_begin (f);
3671       update_window (w, force_p);
3672       update_end (f);
3673 
3674       /* Reset flag in W.  */
3675       w->must_be_updated_p = 0;
3676     }
3677 }
3678 
3679 #ifdef HAVE_WINDOW_SYSTEM
3680 
3681 /* Redraw lines from the current matrix of window W that are
3682    overlapped by other rows.  YB is bottom-most y-position in W.  */
3683 
3684 static void
3685 redraw_overlapped_rows (w, yb)
3686      struct window *w;
3687      int yb;
3688 {
3689   int i;
3690   struct frame *f = XFRAME (WINDOW_FRAME (w));
3691 
3692   /* If rows overlapping others have been changed, the rows being
3693      overlapped have to be redrawn.  This won't draw lines that have
3694      already been drawn in update_window_line because overlapped_p in
3695      desired rows is 0, so after row assignment overlapped_p in
3696      current rows is 0.  */
3697   for (i = 0; i < w->current_matrix->nrows; ++i)
3698     {
3699       struct glyph_row *row = w->current_matrix->rows + i;
3700 
3701       if (!row->enabled_p)
3702         break;
3703       else if (row->mode_line_p)
3704         continue;
3705 
3706       if (row->overlapped_p)
3707         {
3708           enum glyph_row_area area;
3709 
3710           for (area = LEFT_MARGIN_AREA; area < LAST_AREA; ++area)
3711             {
3712               updated_row = row;
3713               updated_area = area;
3714               FRAME_RIF (f)->cursor_to (i, 0, row->y,
3715                                         area == TEXT_AREA ? row->x : 0);
3716               if (row->used[area])
3717                 FRAME_RIF (f)->write_glyphs (row->glyphs[area],
3718                                              row->used[area]);
3719               FRAME_RIF (f)->clear_end_of_line (-1);
3720             }
3721 
3722           row->overlapped_p = 0;
3723         }
3724 
3725       if (MATRIX_ROW_BOTTOM_Y (row) >= yb)
3726         break;
3727     }
3728 }
3729 
3730 
3731 /* Redraw lines from the current matrix of window W that overlap
3732    others.  YB is bottom-most y-position in W.  */
3733 
3734 static void
3735 redraw_overlapping_rows (w, yb)
3736      struct window *w;
3737      int yb;
3738 {
3739   int i, bottom_y;
3740   struct glyph_row *row;
3741   struct redisplay_interface *rif = FRAME_RIF (XFRAME (WINDOW_FRAME (w)));
3742 
3743   for (i = 0; i < w->current_matrix->nrows; ++i)
3744     {
3745       row = w->current_matrix->rows + i;
3746 
3747       if (!row->enabled_p)
3748         break;
3749       else if (row->mode_line_p)
3750         continue;
3751 
3752       bottom_y = MATRIX_ROW_BOTTOM_Y (row);
3753 
3754       if (row->overlapping_p)
3755         {
3756           int overlaps = 0;
3757 
3758           if (MATRIX_ROW_OVERLAPS_PRED_P (row) && i > 0
3759               && !MATRIX_ROW (w->current_matrix, i - 1)->overlapped_p)
3760             overlaps |= OVERLAPS_PRED;
3761           if (MATRIX_ROW_OVERLAPS_SUCC_P (row) && bottom_y < yb
3762               && !MATRIX_ROW (w->current_matrix, i + 1)->overlapped_p)
3763             overlaps |= OVERLAPS_SUCC;
3764 
3765           if (overlaps)
3766             {
3767               if (row->used[LEFT_MARGIN_AREA])
3768                 rif->fix_overlapping_area (w, row, LEFT_MARGIN_AREA, overlaps);
3769 
3770               if (row->used[TEXT_AREA])
3771                 rif->fix_overlapping_area (w, row, TEXT_AREA, overlaps);
3772 
3773               if (row->used[RIGHT_MARGIN_AREA])
3774                 rif->fix_overlapping_area (w, row, RIGHT_MARGIN_AREA, overlaps);
3775 
3776               /* Record in neighbour rows that ROW overwrites part of
3777                  their display.  */
3778               if (overlaps & OVERLAPS_PRED)
3779                 MATRIX_ROW (w->current_matrix, i - 1)->overlapped_p = 1;
3780               if (overlaps & OVERLAPS_SUCC)
3781                 MATRIX_ROW (w->current_matrix, i + 1)->overlapped_p = 1;
3782             }
3783         }
3784 
3785       if (bottom_y >= yb)
3786         break;
3787     }
3788 }
3789 
3790 #endif /* HAVE_WINDOW_SYSTEM */
3791 
3792 
3793 #ifdef GLYPH_DEBUG
3794 
3795 /* Check that no row in the current matrix of window W is enabled
3796    which is below what's displayed in the window.  */
3797 
3798 void
3799 check_current_matrix_flags (w)
3800      struct window *w;
3801 {
3802   int last_seen_p = 0;
3803   int i, yb = window_text_bottom_y (w);
3804 
3805   for (i = 0; i < w->current_matrix->nrows - 1; ++i)
3806     {
3807       struct glyph_row *row = MATRIX_ROW (w->current_matrix, i);
3808       if (!last_seen_p && MATRIX_ROW_BOTTOM_Y (row) >= yb)
3809         last_seen_p = 1;
3810       else if (last_seen_p && row->enabled_p)
3811         abort ();
3812     }
3813 }
3814 
3815 #endif /* GLYPH_DEBUG */
3816 
3817 
3818 /* Update display of window W.  FORCE_P non-zero means that we should
3819    not stop when detecting pending input.  */
3820 
3821 static int
3822 update_window (w, force_p)
3823      struct window *w;
3824      int force_p;
3825 {
3826   struct glyph_matrix *desired_matrix = w->desired_matrix;
3827   int paused_p;
3828 #if !PERIODIC_PREEMPTION_CHECKING
3829   int preempt_count = baud_rate / 2400 + 1;
3830 #endif
3831   extern int input_pending;
3832   extern Lisp_Object do_mouse_tracking;
3833   struct redisplay_interface *rif = FRAME_RIF (XFRAME (WINDOW_FRAME (w)));
3834 #if GLYPH_DEBUG
3835   /* Check that W's frame doesn't have glyph matrices.  */
3836   xassert (FRAME_WINDOW_P (XFRAME (WINDOW_FRAME (w))));
3837 #endif
3838 
3839   /* Check pending input the first time so that we can quickly return.  */
3840 #if !PERIODIC_PREEMPTION_CHECKING
3841   if (!force_p)
3842     detect_input_pending_ignore_squeezables ();
3843 #endif
3844 
3845   /* If forced to complete the update, or if no input is pending, do
3846      the update.  */
3847   if (force_p || !input_pending || !NILP (do_mouse_tracking))
3848     {
3849       struct glyph_row *row, *end;
3850       struct glyph_row *mode_line_row;
3851       struct glyph_row *header_line_row;
3852       int yb, changed_p = 0, mouse_face_overwritten_p = 0, n_updated;
3853 
3854       rif->update_window_begin_hook (w);
3855       yb = window_text_bottom_y (w);
3856 
3857       /* If window has a header line, update it before everything else.
3858          Adjust y-positions of other rows by the header line height.  */
3859       row = desired_matrix->rows;
3860       end = row + desired_matrix->nrows - 1;
3861 
3862       if (row->mode_line_p)
3863         {
3864           header_line_row = row;
3865           ++row;
3866         }
3867       else
3868         header_line_row = NULL;
3869 
3870       /* Update the mode line, if necessary.  */
3871       mode_line_row = MATRIX_MODE_LINE_ROW (desired_matrix);
3872       if (mode_line_row->mode_line_p && mode_line_row->enabled_p)
3873         {
3874           mode_line_row->y = yb;
3875           update_window_line (w, MATRIX_ROW_VPOS (mode_line_row,
3876                                                   desired_matrix),
3877                               &mouse_face_overwritten_p);
3878         }
3879 
3880       /* Find first enabled row.  Optimizations in redisplay_internal
3881          may lead to an update with only one row enabled.  There may
3882          be also completely empty matrices.  */
3883       while (row < end && !row->enabled_p)
3884         ++row;
3885 
3886       /* Try reusing part of the display by copying.  */
3887       if (row < end && !desired_matrix->no_scrolling_p)
3888         {
3889           int rc = scrolling_window (w, header_line_row != NULL);
3890           if (rc < 0)
3891             {
3892               /* All rows were found to be equal.  */
3893               paused_p = 0;
3894               goto set_cursor;
3895             }
3896           else if (rc > 0)
3897             {
3898               /* We've scrolled the display.  */
3899               force_p = 1;
3900               changed_p = 1;
3901             }
3902         }
3903 
3904       /* Update the rest of the lines.  */
3905       for (n_updated = 0; row < end && (force_p || !input_pending); ++row)
3906         if (row->enabled_p)
3907           {
3908             int vpos = MATRIX_ROW_VPOS (row, desired_matrix);
3909             int i;
3910 
3911             /* We'll have to play a little bit with when to
3912                detect_input_pending.  If it's done too often,
3913                scrolling large windows with repeated scroll-up
3914                commands will too quickly pause redisplay.  */
3915 #if PERIODIC_PREEMPTION_CHECKING
3916             if (!force_p)
3917               {
3918                 EMACS_TIME tm, dif;
3919                 EMACS_GET_TIME (tm);
3920                 EMACS_SUB_TIME (dif, preemption_next_check, tm);
3921                 if (EMACS_TIME_NEG_P (dif))
3922                   {
3923                     EMACS_ADD_TIME (preemption_next_check, tm, preemption_period);
3924                     if (detect_input_pending_ignore_squeezables ())
3925                       break;
3926                   }
3927               }
3928 #else
3929             if (!force_p && ++n_updated % preempt_count == 0)
3930               detect_input_pending_ignore_squeezables ();
3931 #endif
3932             changed_p |= update_window_line (w, vpos,
3933                                              &mouse_face_overwritten_p);
3934 
3935             /* Mark all rows below the last visible one in the current
3936                matrix as invalid.  This is necessary because of
3937                variable line heights.  Consider the case of three
3938                successive redisplays, where the first displays 5
3939                lines, the second 3 lines, and the third 5 lines again.
3940                If the second redisplay wouldn't mark rows in the
3941                current matrix invalid, the third redisplay might be
3942                tempted to optimize redisplay based on lines displayed
3943                in the first redisplay.  */
3944             if (MATRIX_ROW_BOTTOM_Y (row) >= yb)
3945               for (i = vpos + 1; i < w->current_matrix->nrows - 1; ++i)
3946                 MATRIX_ROW (w->current_matrix, i)->enabled_p = 0;
3947           }
3948 
3949       /* Was display preempted?  */
3950       paused_p = row < end;
3951 
3952     set_cursor:
3953 
3954       /* Update the header line after scrolling because a new header
3955          line would otherwise overwrite lines at the top of the window
3956          that can be scrolled.  */
3957       if (header_line_row && header_line_row->enabled_p)
3958         {
3959           header_line_row->y = 0;
3960           update_window_line (w, 0, &mouse_face_overwritten_p);
3961         }
3962 
3963       /* Fix the appearance of overlapping/overlapped rows.  */
3964       if (!paused_p && !w->pseudo_window_p)
3965         {
3966 #ifdef HAVE_WINDOW_SYSTEM
3967           if (changed_p && rif->fix_overlapping_area)
3968             {
3969               redraw_overlapped_rows (w, yb);
3970               redraw_overlapping_rows (w, yb);
3971             }
3972 #endif
3973 
3974           /* Make cursor visible at cursor position of W.  */
3975           set_window_cursor_after_update (w);
3976 
3977 #if 0 /* Check that current matrix invariants are satisfied.  This is
3978          for debugging only.  See the comment of check_matrix_invariants.  */
3979           IF_DEBUG (check_matrix_invariants (w));
3980 #endif
3981         }
3982 
3983 #if GLYPH_DEBUG
3984       /* Remember the redisplay method used to display the matrix.  */
3985       strcpy (w->current_matrix->method, w->desired_matrix->method);
3986 #endif
3987 
3988 #ifdef HAVE_WINDOW_SYSTEM
3989       update_window_fringes (w, 0);
3990 #endif
3991 
3992       /* End the update of window W.  Don't set the cursor if we
3993          paused updating the display because in this case,
3994          set_window_cursor_after_update hasn't been called, and
3995          output_cursor doesn't contain the cursor location.  */
3996       rif->update_window_end_hook (w, !paused_p, mouse_face_overwritten_p);
3997     }
3998   else
3999     paused_p = 1;
4000 
4001 #if GLYPH_DEBUG
4002   /* check_current_matrix_flags (w); */
4003   add_window_display_history (w, w->current_matrix->method, paused_p);
4004 #endif
4005 
4006   clear_glyph_matrix (desired_matrix);
4007 
4008   return paused_p;
4009 }
4010 
4011 
4012 /* Update the display of area AREA in window W, row number VPOS.
4013    AREA can be either LEFT_MARGIN_AREA or RIGHT_MARGIN_AREA.  */
4014 
4015 static void
4016 update_marginal_area (w, area, vpos)
4017      struct window *w;
4018      int area, vpos;
4019 {
4020   struct glyph_row *desired_row = MATRIX_ROW (w->desired_matrix, vpos);
4021   struct redisplay_interface *rif = FRAME_RIF (XFRAME (WINDOW_FRAME (w)));
4022 
4023   /* Let functions in xterm.c know what area subsequent X positions
4024      will be relative to.  */
4025   updated_area = area;
4026 
4027   /* Set cursor to start of glyphs, write them, and clear to the end
4028      of the area.  I don't think that something more sophisticated is
4029      necessary here, since marginal areas will not be the default.  */
4030   rif->cursor_to (vpos, 0, desired_row->y, 0);
4031   if (desired_row->used[area])
4032     rif->write_glyphs (desired_row->glyphs[area], desired_row->used[area]);
4033   rif->clear_end_of_line (-1);
4034 }
4035 
4036 
4037 /* Update the display of the text area of row VPOS in window W.
4038    Value is non-zero if display has changed.  */
4039 
4040 static int
4041 update_text_area (w, vpos)
4042      struct window *w;
4043      int vpos;
4044 {
4045   struct glyph_row *current_row = MATRIX_ROW (w->current_matrix, vpos);
4046   struct glyph_row *desired_row = MATRIX_ROW (w->desired_matrix, vpos);
4047   struct redisplay_interface *rif = FRAME_RIF (XFRAME (WINDOW_FRAME (w)));
4048   int changed_p = 0;
4049 
4050   /* Let functions in xterm.c know what area subsequent X positions
4051      will be relative to.  */
4052   updated_area = TEXT_AREA;
4053 
4054   /* If rows are at different X or Y, or rows have different height,
4055      or the current row is marked invalid, write the entire line.  */
4056   if (!current_row->enabled_p
4057       || desired_row->y != current_row->y
4058       || desired_row->ascent != current_row->ascent
4059       || desired_row->phys_ascent != current_row->phys_ascent
4060       || desired_row->phys_height != current_row->phys_height
4061       || desired_row->visible_height != current_row->visible_height
4062       || current_row->overlapped_p
4063       /* This next line is necessary for correctly redrawing
4064          mouse-face areas after scrolling and other operations.
4065          However, it causes excessive flickering when mouse is moved
4066          across the mode line.  Luckily, turning it off for the mode
4067          line doesn't seem to hurt anything. -- cyd.
4068          But it is still needed for the header line. -- kfs.  */
4069       || (current_row->mouse_face_p
4070           && !(current_row->mode_line_p && vpos > 0))
4071       || current_row->x != desired_row->x)
4072     {
4073       rif->cursor_to (vpos, 0, desired_row->y, desired_row->x);
4074 
4075       if (desired_row->used[TEXT_AREA])
4076         rif->write_glyphs (desired_row->glyphs[TEXT_AREA],
4077                            desired_row->used[TEXT_AREA]);
4078 
4079       /* Clear to end of window.  */
4080       rif->clear_end_of_line (-1);
4081       changed_p = 1;
4082 
4083       /* This erases the cursor.  We do this here because
4084          notice_overwritten_cursor cannot easily check this, which
4085          might indicate that the whole functionality of
4086          notice_overwritten_cursor would better be implemented here.
4087          On the other hand, we need notice_overwritten_cursor as long
4088          as mouse highlighting is done asynchronously outside of
4089          redisplay.  */
4090       if (vpos == w->phys_cursor.vpos)
4091         w->phys_cursor_on_p = 0;
4092     }
4093   else
4094     {
4095       int stop, i, x;
4096       struct glyph *current_glyph = current_row->glyphs[TEXT_AREA];
4097       struct glyph *desired_glyph = desired_row->glyphs[TEXT_AREA];
4098       int overlapping_glyphs_p = current_row->contains_overlapping_glyphs_p;
4099       int desired_stop_pos = desired_row->used[TEXT_AREA];
4100       int abort_skipping = 0;
4101 
4102       /* If the desired row extends its face to the text area end, and
4103          unless the current row also does so at the same position,
4104          make sure we write at least one glyph, so that the face
4105          extension actually takes place.  */
4106       if (MATRIX_ROW_EXTENDS_FACE_P (desired_row)
4107           && (desired_stop_pos < current_row->used[TEXT_AREA]
4108               || (desired_stop_pos == current_row->used[TEXT_AREA]
4109                   && !MATRIX_ROW_EXTENDS_FACE_P (current_row))))
4110         --desired_stop_pos;
4111 
4112       stop = min (current_row->used[TEXT_AREA], desired_stop_pos);
4113       i = 0;
4114       x = desired_row->x;
4115 
4116       /* Loop over glyphs that current and desired row may have
4117          in common.  */
4118       while (i < stop)
4119         {
4120           int can_skip_p = !abort_skipping;
4121 
4122           /* Skip over glyphs that both rows have in common.  These
4123              don't have to be written.  We can't skip if the last
4124              current glyph overlaps the glyph to its right.  For
4125              example, consider a current row of `if ' with the `f' in
4126              Courier bold so that it overlaps the ` ' to its right.
4127              If the desired row is ` ', we would skip over the space
4128              after the `if' and there would remain a pixel from the
4129              `f' on the screen.  */
4130           if (overlapping_glyphs_p && i > 0)
4131             {
4132               struct glyph *glyph = &current_row->glyphs[TEXT_AREA][i - 1];
4133               int left, right;
4134 
4135               rif->get_glyph_overhangs (glyph, XFRAME (w->frame),
4136                                         &left, &right);
4137               can_skip_p = (right == 0 && !abort_skipping);
4138             }
4139 
4140           if (can_skip_p)
4141             {
4142               int start_hpos = i;
4143 
4144               while (i < stop
4145                      && GLYPH_EQUAL_P (desired_glyph, current_glyph))
4146                 {
4147                   x += desired_glyph->pixel_width;
4148                   ++desired_glyph, ++current_glyph, ++i;
4149                 }
4150 
4151               /* Consider the case that the current row contains "xxx
4152                  ppp ggg" in italic Courier font, and the desired row
4153                  is "xxx ggg".  The character `p' has lbearing, `g'
4154                  has not.  The loop above will stop in front of the
4155                  first `p' in the current row.  If we would start
4156                  writing glyphs there, we wouldn't erase the lbearing
4157                  of the `p'.  The rest of the lbearing problem is then
4158                  taken care of by draw_glyphs.  */
4159               if (overlapping_glyphs_p
4160                   && i > 0
4161                   && i < current_row->used[TEXT_AREA]
4162                   && (current_row->used[TEXT_AREA]
4163                       != desired_row->used[TEXT_AREA]))
4164                 {
4165                   int left, right;
4166 
4167                   rif->get_glyph_overhangs (current_glyph, XFRAME (w->frame),
4168                                             &left, &right);
4169                   while (left > 0 && i > 0)
4170                     {
4171                       --i, --desired_glyph, --current_glyph;
4172                       x -= desired_glyph->pixel_width;
4173                       left -= desired_glyph->pixel_width;
4174                     }
4175 
4176                   /* Abort the skipping algorithm if we end up before
4177                      our starting point, to avoid looping (bug#1070).
4178                      This can happen when the lbearing is larger than
4179                      the pixel width.  */
4180                   abort_skipping = (i < start_hpos);
4181                 }
4182             }
4183 
4184           /* Try to avoid writing the entire rest of the desired row
4185              by looking for a resync point.  This mainly prevents
4186              mode line flickering in the case the mode line is in
4187              fixed-pitch font, which it usually will be.  */
4188           if (i < desired_row->used[TEXT_AREA])
4189             {
4190               int start_x = x, start_hpos = i;
4191               struct glyph *start = desired_glyph;
4192               int current_x = x;
4193               int skip_first_p = !can_skip_p;
4194 
4195               /* Find the next glyph that's equal again.  */
4196               while (i < stop
4197                      && (skip_first_p
4198                          || !GLYPH_EQUAL_P (desired_glyph, current_glyph))
4199                      && x == current_x)
4200                 {
4201                   x += desired_glyph->pixel_width;
4202                   current_x += current_glyph->pixel_width;
4203                   ++desired_glyph, ++current_glyph, ++i;
4204                   skip_first_p = 0;
4205                 }
4206 
4207               if (i == start_hpos || x != current_x)
4208                 {
4209                   i = start_hpos;
4210                   x = start_x;
4211                   desired_glyph = start;
4212                   break;
4213                 }
4214 
4215               rif->cursor_to (vpos, start_hpos, desired_row->y, start_x);
4216               rif->write_glyphs (start, i - start_hpos);
4217               changed_p = 1;
4218             }
4219         }
4220 
4221       /* Write the rest.  */
4222       if (i < desired_row->used[TEXT_AREA])
4223         {
4224           rif->cursor_to (vpos, i, desired_row->y, x);
4225           rif->write_glyphs (desired_glyph, desired_row->used[TEXT_AREA] - i);
4226           changed_p = 1;
4227         }
4228 
4229       /* Maybe clear to end of line.  */
4230       if (MATRIX_ROW_EXTENDS_FACE_P (desired_row))
4231         {
4232           /* If new row extends to the end of the text area, nothing
4233              has to be cleared, if and only if we did a write_glyphs
4234              above.  This is made sure by setting desired_stop_pos
4235              appropriately above.  */
4236           xassert (i < desired_row->used[TEXT_AREA]
4237                    || ((desired_row->used[TEXT_AREA]
4238                         == current_row->used[TEXT_AREA])
4239                        && MATRIX_ROW_EXTENDS_FACE_P (current_row)));
4240         }
4241       else if (MATRIX_ROW_EXTENDS_FACE_P (current_row))
4242         {
4243           /* If old row extends to the end of the text area, clear.  */
4244           if (i >= desired_row->used[TEXT_AREA])
4245             rif->cursor_to (vpos, i, desired_row->y,
4246                             desired_row->pixel_width);
4247           rif->clear_end_of_line (-1);
4248           changed_p = 1;
4249         }
4250       else if (desired_row->pixel_width < current_row->pixel_width)
4251         {
4252           /* Otherwise clear to the end of the old row.  Everything
4253              after that position should be clear already.  */
4254           int x;
4255 
4256           if (i >= desired_row->used[TEXT_AREA])
4257             rif->cursor_to (vpos, i, desired_row->y,
4258                             desired_row->pixel_width);
4259 
4260           /* If cursor is displayed at the end of the line, make sure
4261              it's cleared.  Nowadays we don't have a phys_cursor_glyph
4262              with which to erase the cursor (because this method
4263              doesn't work with lbearing/rbearing), so we must do it
4264              this way.  */
4265           if (vpos == w->phys_cursor.vpos
4266               && (desired_row->reversed_p
4267                   ? (w->phys_cursor.hpos < 0)
4268                   : (w->phys_cursor.hpos >= desired_row->used[TEXT_AREA])))
4269             {
4270               w->phys_cursor_on_p = 0;
4271               x = -1;
4272             }
4273           else
4274             x = current_row->pixel_width;
4275           rif->clear_end_of_line (x);
4276           changed_p = 1;
4277         }
4278     }
4279 
4280   return changed_p;
4281 }
4282 
4283 
4284 /* Update row VPOS in window W.  Value is non-zero if display has been
4285    changed.  */
4286 
4287 static int
4288 update_window_line (w, vpos, mouse_face_overwritten_p)
4289      struct window *w;
4290      int vpos, *mouse_face_overwritten_p;
4291 {
4292   struct glyph_row *current_row = MATRIX_ROW (w->current_matrix, vpos);
4293   struct glyph_row *desired_row = MATRIX_ROW (w->desired_matrix, vpos);
4294   struct redisplay_interface *rif = FRAME_RIF (XFRAME (WINDOW_FRAME (w)));
4295   int changed_p = 0;
4296 
4297   /* Set the row being updated.  This is important to let xterm.c
4298      know what line height values are in effect.  */
4299   updated_row = desired_row;
4300 
4301   /* A row can be completely invisible in case a desired matrix was
4302      built with a vscroll and then make_cursor_line_fully_visible shifts
4303      the matrix.  Make sure to make such rows current anyway, since
4304      we need the correct y-position, for example, in the current matrix.  */
4305   if (desired_row->mode_line_p
4306       || desired_row->visible_height > 0)
4307     {
4308       xassert (desired_row->enabled_p);
4309 
4310       /* Update display of the left margin area, if there is one.  */
4311       if (!desired_row->full_width_p
4312           && !NILP (w->left_margin_cols))
4313         {
4314           changed_p = 1;
4315           update_marginal_area (w, LEFT_MARGIN_AREA, vpos);
4316         }
4317 
4318       /* Update the display of the text area.  */
4319       if (update_text_area (w, vpos))
4320         {
4321           changed_p = 1;
4322           if (current_row->mouse_face_p)
4323             *mouse_face_overwritten_p = 1;
4324         }
4325 
4326       /* Update display of the right margin area, if there is one.  */
4327       if (!desired_row->full_width_p
4328           && !NILP (w->right_margin_cols))
4329         {
4330           changed_p = 1;
4331           update_marginal_area (w, RIGHT_MARGIN_AREA, vpos);
4332         }
4333 
4334       /* Draw truncation marks etc.  */
4335       if (!current_row->enabled_p
4336           || desired_row->y != current_row->y
4337           || desired_row->visible_height != current_row->visible_height
4338           || desired_row->cursor_in_fringe_p != current_row->cursor_in_fringe_p
4339           || desired_row->overlay_arrow_bitmap != current_row->overlay_arrow_bitmap
4340           || current_row->redraw_fringe_bitmaps_p
4341           || desired_row->mode_line_p != current_row->mode_line_p
4342           || desired_row->exact_window_width_line_p != current_row->exact_window_width_line_p
4343           || (MATRIX_ROW_CONTINUATION_LINE_P (desired_row)
4344               != MATRIX_ROW_CONTINUATION_LINE_P (current_row)))
4345         rif->after_update_window_line_hook (desired_row);
4346     }
4347 
4348   /* Update current_row from desired_row.  */
4349   make_current (w->desired_matrix, w->current_matrix, vpos);
4350   updated_row = NULL;
4351   return changed_p;
4352 }
4353 
4354 
4355 /* Set the cursor after an update of window W.  This function may only
4356    be called from update_window.  */
4357 
4358 static void
4359 set_window_cursor_after_update (w)
4360      struct window *w;
4361 {
4362   struct frame *f = XFRAME (w->frame);
4363   struct redisplay_interface *rif = FRAME_RIF (f);
4364   int cx, cy, vpos, hpos;
4365 
4366   /* Not intended for frame matrix updates.  */
4367   xassert (FRAME_WINDOW_P (f));
4368 
4369   if (cursor_in_echo_area
4370       && !NILP (echo_area_buffer[0])
4371       /* If we are showing a message instead of the mini-buffer,
4372          show the cursor for the message instead.  */
4373       && XWINDOW (minibuf_window) == w
4374       && EQ (minibuf_window, echo_area_window)
4375       /* These cases apply only to the frame that contains
4376          the active mini-buffer window.  */
4377       && FRAME_HAS_MINIBUF_P (f)
4378       && EQ (FRAME_MINIBUF_WINDOW (f), echo_area_window))
4379     {
4380       cx = cy = vpos = hpos = 0;
4381 
4382       if (cursor_in_echo_area >= 0)
4383         {
4384           /* If the mini-buffer is several lines high, find the last
4385              line that has any text on it.  Note: either all lines
4386              are enabled or none.  Otherwise we wouldn't be able to
4387              determine Y.  */
4388           struct glyph_row *row, *last_row;
4389           struct glyph *glyph;
4390           int yb = window_text_bottom_y (w);
4391 
4392           last_row = NULL;
4393           row = w->current_matrix->rows;
4394           while (row->enabled_p
4395                  && (last_row == NULL
4396                      || MATRIX_ROW_BOTTOM_Y (row) <= yb))
4397             {
4398               if (row->used[TEXT_AREA]
4399                   && row->glyphs[TEXT_AREA][0].charpos >= 0)
4400                 last_row = row;
4401               ++row;
4402             }
4403 
4404           if (last_row)
4405             {
4406               struct glyph *start = last_row->glyphs[TEXT_AREA];
4407               struct glyph *last = start + last_row->used[TEXT_AREA] - 1;
4408 
4409               while (last > start && last->charpos < 0)
4410                 --last;
4411 
4412               for (glyph = start; glyph < last; ++glyph)
4413                 {
4414                   cx += glyph->pixel_width;
4415                   ++hpos;
4416                 }
4417 
4418               cy = last_row->y;
4419               vpos = MATRIX_ROW_VPOS (last_row, w->current_matrix);
4420             }
4421         }
4422     }
4423   else
4424     {
4425       cx = w->cursor.x;
4426       cy = w->cursor.y;
4427       hpos = w->cursor.hpos;
4428       vpos = w->cursor.vpos;
4429     }
4430 
4431   /* Window cursor can be out of sync for horizontally split windows.  */
4432   hpos = max (-1, hpos); /* -1 is for when cursor is on the left fringe */
4433   hpos = min (w->current_matrix->matrix_w - 1, hpos);
4434   vpos = max (0, vpos);
4435   vpos = min (w->current_matrix->nrows - 1, vpos);
4436   rif->cursor_to (vpos, hpos, cy, cx);
4437 }
4438 
4439 
4440 /* Set WINDOW->must_be_updated_p to ON_P for all windows in the window
4441    tree rooted at W.  */
4442 
4443 void
4444 set_window_update_flags (w, on_p)
4445      struct window *w;
4446      int on_p;
4447 {
4448   while (w)
4449     {
4450       if (!NILP (w->hchild))
4451         set_window_update_flags (XWINDOW (w->hchild), on_p);
4452       else if (!NILP (w->vchild))
4453         set_window_update_flags (XWINDOW (w->vchild), on_p);
4454       else
4455         w->must_be_updated_p = on_p;
4456 
4457       w = NILP (w->next) ? 0 : XWINDOW (w->next);
4458     }
4459 }
4460 
4461 
4462 
4463 /***********************************************************************
4464                         Window-Based Scrolling
4465  ***********************************************************************/
4466 
4467 /* Structure describing rows in scrolling_window.  */
4468 
4469 struct row_entry
4470 {
4471   /* Number of occurrences of this row in desired and current matrix.  */
4472   int old_uses, new_uses;
4473 
4474   /* Vpos of row in new matrix.  */
4475   int new_line_number;
4476 
4477   /* Bucket index of this row_entry in the hash table row_table.  */
4478   int bucket;
4479 
4480   /* The row described by this entry.  */
4481   struct glyph_row *row;
4482 
4483   /* Hash collision chain.  */
4484   struct row_entry *next;
4485 };
4486 
4487 /* A pool to allocate row_entry structures from, and the size of the
4488    pool.  The pool is reallocated in scrolling_window when we find
4489    that we need a larger one.  */
4490 
4491 static struct row_entry *row_entry_pool;
4492 static int row_entry_pool_size;
4493 
4494 /* Index of next free entry in row_entry_pool.  */
4495 
4496 static int row_entry_idx;
4497 
4498 /* The hash table used during scrolling, and the table's size.  This
4499    table is used to quickly identify equal rows in the desired and
4500    current matrix.  */
4501 
4502 static struct row_entry **row_table;
4503 static int row_table_size;
4504 
4505 /* Vectors of pointers to row_entry structures belonging to the
4506    current and desired matrix, and the size of the vectors.  */
4507 
4508 static struct row_entry **old_lines, **new_lines;
4509 static int old_lines_size, new_lines_size;
4510 
4511 /* A pool to allocate run structures from, and its size.  */
4512 
4513 static struct run *run_pool;
4514 static int runs_size;
4515 
4516 /* A vector of runs of lines found during scrolling.  */
4517 
4518 static struct run **runs;
4519 
4520 /* Add glyph row ROW to the scrolling hash table during the scrolling
4521    of window W.  */
4522 
4523 static INLINE struct row_entry *
4524 add_row_entry (w, row)
4525      struct window *w;
4526      struct glyph_row *row;
4527 {
4528   struct row_entry *entry;
4529   int i = row->hash % row_table_size;
4530 
4531   entry = row_table[i];
4532   while (entry && !row_equal_p (w, entry->row, row, 1))
4533     entry = entry->next;
4534 
4535   if (entry == NULL)
4536     {
4537       entry = row_entry_pool + row_entry_idx++;
4538       entry->row = row;
4539       entry->old_uses = entry->new_uses = 0;
4540       entry->new_line_number = 0;
4541       entry->bucket = i;
4542       entry->next = row_table[i];
4543       row_table[i] = entry;
4544     }
4545 
4546   return entry;
4547 }
4548 
4549 
4550 /* Try to reuse part of the current display of W by scrolling lines.
4551    HEADER_LINE_P non-zero means W has a header line.
4552 
4553    The algorithm is taken from Communications of the ACM, Apr78 "A
4554    Technique for Isolating Differences Between Files."  It should take
4555    O(N) time.
4556 
4557    A short outline of the steps of the algorithm
4558 
4559    1. Skip lines equal at the start and end of both matrices.
4560 
4561    2. Enter rows in the current and desired matrix into a symbol
4562    table, counting how often they appear in both matrices.
4563 
4564    3. Rows that appear exactly once in both matrices serve as anchors,
4565    i.e. we assume that such lines are likely to have been moved.
4566 
4567    4. Starting from anchor lines, extend regions to be scrolled both
4568    forward and backward.
4569 
4570    Value is
4571 
4572    -1   if all rows were found to be equal.
4573    0    to indicate that we did not scroll the display, or
4574    1    if we did scroll.  */
4575 
4576 static int
4577 scrolling_window (w, header_line_p)
4578      struct window *w;
4579      int header_line_p;
4580 {
4581   struct glyph_matrix *desired_matrix = w->desired_matrix;
4582   struct glyph_matrix *current_matrix = w->current_matrix;
4583   int yb = window_text_bottom_y (w);
4584   int i, j, first_old, first_new, last_old, last_new;
4585   int nruns, nbytes, n, run_idx;
4586   struct row_entry *entry;
4587   struct redisplay_interface *rif = FRAME_RIF (XFRAME (WINDOW_FRAME (w)));
4588 
4589   /* Skip over rows equal at the start.  */
4590   for (i = header_line_p ? 1 : 0; i < current_matrix->nrows - 1; ++i)
4591     {
4592       struct glyph_row *d = MATRIX_ROW (desired_matrix, i);
4593       struct glyph_row *c = MATRIX_ROW (current_matrix, i);
4594 
4595       if (c->enabled_p
4596           && d->enabled_p
4597           && !d->redraw_fringe_bitmaps_p
4598           && c->y == d->y
4599           && MATRIX_ROW_BOTTOM_Y (c) <= yb
4600           && MATRIX_ROW_BOTTOM_Y (d) <= yb
4601           && row_equal_p (w, c, d, 1))
4602         {
4603           assign_row (c, d);
4604           d->enabled_p = 0;
4605         }
4606       else
4607         break;
4608     }
4609 
4610   /* Give up if some rows in the desired matrix are not enabled.  */
4611   if (!MATRIX_ROW (desired_matrix, i)->enabled_p)
4612     return -1;
4613 
4614   first_old = first_new = i;
4615 
4616   /* Set last_new to the index + 1 of the last enabled row in the
4617      desired matrix.  */
4618   i = first_new + 1;
4619   while (i < desired_matrix->nrows - 1
4620          && MATRIX_ROW (desired_matrix, i)->enabled_p
4621          && MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (desired_matrix, i)) <= yb)
4622     ++i;
4623 
4624   if (!MATRIX_ROW (desired_matrix, i)->enabled_p)
4625     return 0;
4626 
4627   last_new = i;
4628 
4629   /* Set last_old to the index + 1 of the last enabled row in the
4630      current matrix.  We don't look at the enabled flag here because
4631      we plan to reuse part of the display even if other parts are
4632      disabled.  */
4633   i = first_old + 1;
4634   while (i < current_matrix->nrows - 1)
4635     {
4636       int bottom = MATRIX_ROW_BOTTOM_Y (MATRIX_ROW (current_matrix, i));
4637       if (bottom <= yb)
4638         ++i;
4639       if (bottom >= yb)
4640         break;
4641     }
4642 
4643   last_old = i;
4644 
4645   /* Skip over rows equal at the bottom.  */
4646   i = last_new;
4647   j = last_old;
4648   while (i - 1 > first_new
4649          && j - 1 > first_old
4650          && MATRIX_ROW (current_matrix, i - 1)->enabled_p
4651          && (MATRIX_ROW (current_matrix, i - 1)->y
4652              == MATRIX_ROW (desired_matrix, j - 1)->y)
4653          && !MATRIX_ROW (desired_matrix, j - 1)->redraw_fringe_bitmaps_p
4654          && row_equal_p (w,
4655                          MATRIX_ROW (desired_matrix, i - 1),
4656                          MATRIX_ROW (current_matrix, j - 1), 1))
4657     --i, --j;
4658   last_new = i;
4659   last_old = j;
4660 
4661   /* Nothing to do if all rows are equal.  */
4662   if (last_new == first_new)
4663     return 0;
4664 
4665   /* Reallocate vectors, tables etc. if necessary.  */
4666 
4667   if (current_matrix->nrows > old_lines_size)
4668     {
4669       old_lines_size = current_matrix->nrows;
4670       nbytes = old_lines_size * sizeof *old_lines;
4671       old_lines = (struct row_entry **) xrealloc (old_lines, nbytes);
4672     }
4673 
4674   if (desired_matrix->nrows > new_lines_size)
4675     {
4676       new_lines_size = desired_matrix->nrows;
4677       nbytes = new_lines_size * sizeof *new_lines;
4678       new_lines = (struct row_entry **) xrealloc (new_lines, nbytes);
4679     }
4680 
4681   n = desired_matrix->nrows + current_matrix->nrows;
4682   if (3 * n > row_table_size)
4683     {
4684       row_table_size = next_almost_prime (3 * n);
4685       nbytes = row_table_size * sizeof *row_table;
4686       row_table = (struct row_entry **) xrealloc (row_table, nbytes);
4687       bzero (row_table, nbytes);
4688     }
4689 
4690   if (n > row_entry_pool_size)
4691     {
4692       row_entry_pool_size = n;
4693       nbytes = row_entry_pool_size * sizeof *row_entry_pool;
4694       row_entry_pool = (struct row_entry *) xrealloc (row_entry_pool, nbytes);
4695     }
4696 
4697   if (desired_matrix->nrows > runs_size)
4698     {
4699       runs_size = desired_matrix->nrows;
4700       nbytes = runs_size * sizeof *runs;
4701       runs = (struct run **) xrealloc (runs, nbytes);
4702       nbytes = runs_size * sizeof *run_pool;
4703       run_pool = (struct run *) xrealloc (run_pool, nbytes);
4704     }
4705 
4706   nruns = run_idx = 0;
4707   row_entry_idx = 0;
4708 
4709   /* Add rows from the current and desired matrix to the hash table
4710      row_hash_table to be able to find equal ones quickly.  */
4711 
4712   for (i = first_old; i < last_old; ++i)
4713     {
4714       if (MATRIX_ROW (current_matrix, i)->enabled_p)
4715         {
4716           entry = add_row_entry (w, MATRIX_ROW (current_matrix, i));
4717           old_lines[i] = entry;
4718           ++entry->old_uses;
4719         }
4720       else
4721         old_lines[i] = NULL;
4722     }
4723 
4724   for (i = first_new; i < last_new; ++i)
4725     {
4726       xassert (MATRIX_ROW_ENABLED_P (desired_matrix, i));
4727       entry = add_row_entry (w, MATRIX_ROW (desired_matrix, i));
4728       ++entry->new_uses;
4729       entry->new_line_number = i;
4730       new_lines[i] = entry;
4731     }
4732 
4733   /* Identify moves based on lines that are unique and equal
4734      in both matrices.  */
4735   for (i = first_old; i < last_old;)
4736     if (old_lines[i]
4737         && old_lines[i]->old_uses == 1
4738         && old_lines[i]->new_uses == 1)
4739       {
4740         int j, k;
4741         int new_line = old_lines[i]->new_line_number;
4742         struct run *run = run_pool + run_idx++;
4743 
4744         /* Record move.  */
4745         run->current_vpos = i;
4746         run->current_y = MATRIX_ROW (current_matrix, i)->y;
4747         run->desired_vpos = new_line;
4748         run->desired_y = MATRIX_ROW (desired_matrix, new_line)->y;
4749         run->nrows = 1;
4750         run->height = MATRIX_ROW (current_matrix, i)->height;
4751 
4752         /* Extend backward.  */
4753         j = i - 1;
4754         k = new_line - 1;
4755         while (j > first_old
4756                && k > first_new
4757                && old_lines[j] == new_lines[k])
4758           {
4759             int h = MATRIX_ROW (current_matrix, j)->height;
4760             --run->current_vpos;
4761             --run->desired_vpos;
4762             ++run->nrows;
4763             run->height += h;
4764             run->desired_y -= h;
4765             run->current_y -= h;
4766             --j, --k;
4767           }
4768 
4769         /* Extend forward.  */
4770         j = i + 1;
4771         k = new_line + 1;
4772         while (j < last_old
4773                && k < last_new
4774                && old_lines[j] == new_lines[k])
4775           {
4776             int h = MATRIX_ROW (current_matrix, j)->height;
4777             ++run->nrows;
4778             run->height += h;
4779             ++j, ++k;
4780           }
4781 
4782         /* Insert run into list of all runs.  Order runs by copied
4783            pixel lines.  Note that we record runs that don't have to
4784            be copied because they are already in place.  This is done
4785            because we can avoid calling update_window_line in this
4786            case.  */
4787         for (j = 0; j < nruns && runs[j]->height > run->height; ++j)
4788           ;
4789         for (k = nruns; k > j; --k)
4790           runs[k] = runs[k - 1];
4791         runs[j] = run;
4792         ++nruns;
4793 
4794         i += run->nrows;
4795       }
4796     else
4797       ++i;
4798 
4799   /* Do the moves.  Do it in a way that we don't overwrite something
4800      we want to copy later on.  This is not solvable in general
4801      because there is only one display and we don't have a way to
4802      exchange areas on this display.  Example:
4803 
4804           +-----------+       +-----------+
4805           |     A     |       |     B     |
4806           +-----------+  -->  +-----------+
4807           |     B     |       |     A     |
4808           +-----------+       +-----------+
4809 
4810      Instead, prefer bigger moves, and invalidate moves that would
4811      copy from where we copied to.  */
4812 
4813   for (i = 0; i < nruns; ++i)
4814     if (runs[i]->nrows > 0)
4815       {
4816         struct run *r = runs[i];
4817 
4818         /* Copy on the display.  */
4819         if (r->current_y != r->desired_y)
4820           {
4821             rif->scroll_run_hook (w, r);
4822 
4823             /* Invalidate runs that copy from where we copied to.  */
4824             for (j = i + 1; j < nruns; ++j)
4825               {
4826                 struct run *p = runs[j];
4827 
4828                 if ((p->current_y >= r->desired_y
4829                      && p->current_y < r->desired_y + r->height)
4830                     || (p->current_y + p->height >= r->desired_y
4831                         && (p->current_y + p->height
4832                             < r->desired_y + r->height)))
4833                   p->nrows = 0;
4834               }
4835           }
4836 
4837         /* Assign matrix rows.  */
4838         for (j = 0; j < r->nrows; ++j)
4839           {
4840             struct glyph_row *from, *to;
4841             int to_overlapped_p;
4842 
4843             to = MATRIX_ROW (current_matrix, r->desired_vpos + j);
4844             from = MATRIX_ROW (desired_matrix, r->desired_vpos + j);
4845             to_overlapped_p = to->overlapped_p;
4846             if (!from->mode_line_p && !w->pseudo_window_p
4847                 && (to->left_fringe_bitmap != from->left_fringe_bitmap
4848                     || to->right_fringe_bitmap != from->right_fringe_bitmap
4849                     || to->left_fringe_face_id != from->left_fringe_face_id
4850                     || to->right_fringe_face_id != from->right_fringe_face_id
4851                     || to->overlay_arrow_bitmap != from->overlay_arrow_bitmap))
4852               from->redraw_fringe_bitmaps_p = 1;
4853             assign_row (to, from);
4854             to->enabled_p = 1, from->enabled_p = 0;
4855             to->overlapped_p = to_overlapped_p;
4856           }
4857       }
4858 
4859   /* Clear the hash table, for the next time.  */
4860   for (i = 0; i < row_entry_idx; ++i)
4861     row_table[row_entry_pool[i].bucket] = NULL;
4862 
4863   /* Value is > 0 to indicate that we scrolled the display.  */
4864   return nruns;
4865 }
4866 
4867 
4868 
4869 /************************************************************************
4870                          Frame-Based Updates
4871  ************************************************************************/
4872 
4873 /* Update the desired frame matrix of frame F.
4874 
4875    FORCE_P non-zero means that the update should not be stopped by
4876    pending input.  INHIBIT_HAIRY_ID_P non-zero means that scrolling
4877    should not be tried.
4878 
4879    Value is non-zero if update was stopped due to pending input.  */
4880 
4881 static int
4882 update_frame_1 (f, force_p, inhibit_id_p)
4883      struct frame *f;
4884      int force_p;
4885      int inhibit_id_p;
4886 {
4887   /* Frame matrices to work on.  */
4888   struct glyph_matrix *current_matrix = f->current_matrix;
4889   struct glyph_matrix *desired_matrix = f->desired_matrix;
4890   int i;
4891   int pause;
4892   int preempt_count = baud_rate / 2400 + 1;
4893   extern int input_pending;
4894 
4895   xassert (current_matrix && desired_matrix);
4896 
4897   if (baud_rate != FRAME_COST_BAUD_RATE (f))
4898     calculate_costs (f);
4899 
4900   if (preempt_count <= 0)
4901     preempt_count = 1;
4902 
4903 #if !PERIODIC_PREEMPTION_CHECKING
4904   if (!force_p && detect_input_pending_ignore_squeezables ())
4905     {
4906       pause = 1;
4907       goto do_pause;
4908     }
4909 #endif
4910 
4911   /* If we cannot insert/delete lines, it's no use trying it.  */
4912   if (!FRAME_LINE_INS_DEL_OK (f))
4913     inhibit_id_p = 1;
4914 
4915   /* See if any of the desired lines are enabled; don't compute for
4916      i/d line if just want cursor motion.  */
4917   for (i = 0; i < desired_matrix->nrows; i++)
4918     if (MATRIX_ROW_ENABLED_P (desired_matrix, i))
4919       break;
4920 
4921   /* Try doing i/d line, if not yet inhibited.  */
4922   if (!inhibit_id_p && i < desired_matrix->nrows)
4923     force_p |= scrolling (f);
4924 
4925   /* Update the individual lines as needed.  Do bottom line first.  */
4926   if (MATRIX_ROW_ENABLED_P (desired_matrix, desired_matrix->nrows - 1))
4927     update_frame_line (f, desired_matrix->nrows - 1);
4928 
4929   /* Now update the rest of the lines.  */
4930   for (i = 0; i < desired_matrix->nrows - 1 && (force_p || !input_pending); i++)
4931     {
4932       if (MATRIX_ROW_ENABLED_P (desired_matrix, i))
4933         {
4934           if (FRAME_TERMCAP_P (f))
4935             {
4936               /* Flush out every so many lines.
4937                  Also flush out if likely to have more than 1k buffered
4938                  otherwise.   I'm told that some telnet connections get
4939                  really screwed by more than 1k output at once.  */
4940               FILE *display_output = FRAME_TTY (f)->output;
4941               if (display_output)
4942                 {
4943                   int outq = PENDING_OUTPUT_COUNT (display_output);
4944                   if (outq > 900
4945                       || (outq > 20 && ((i - 1) % preempt_count == 0)))
4946                     {
4947                       fflush (display_output);
4948                       if (preempt_count == 1)
4949                         {
4950 #ifdef EMACS_OUTQSIZE
4951                           if (EMACS_OUTQSIZE (0, &outq) < 0)
4952                             /* Probably not a tty.  Ignore the error and reset
4953                                the outq count.  */
4954                             outq = PENDING_OUTPUT_COUNT (FRAME_TTY (f->output));
4955 #endif
4956                           outq *= 10;
4957                           if (baud_rate <= outq && baud_rate > 0)
4958                             sleep (outq / baud_rate);
4959                         }
4960                     }
4961                 }
4962             }
4963 
4964 #if PERIODIC_PREEMPTION_CHECKING
4965           if (!force_p)
4966             {
4967               EMACS_TIME tm, dif;
4968               EMACS_GET_TIME (tm);
4969               EMACS_SUB_TIME (dif, preemption_next_check, tm);
4970               if (EMACS_TIME_NEG_P (dif))
4971                 {
4972                   EMACS_ADD_TIME (preemption_next_check, tm, preemption_period);
4973                   if (detect_input_pending_ignore_squeezables ())
4974                     break;
4975                 }
4976             }
4977 #else
4978           if (!force_p && (i - 1) % preempt_count == 0)
4979             detect_input_pending_ignore_squeezables ();
4980 #endif
4981 
4982           update_frame_line (f, i);
4983         }
4984     }
4985 
4986   pause = (i < FRAME_LINES (f) - 1) ? i : 0;
4987 
4988   /* Now just clean up termcap drivers and set cursor, etc.  */
4989   if (!pause)
4990     {
4991       if ((cursor_in_echo_area
4992            /* If we are showing a message instead of the mini-buffer,
4993               show the cursor for the message instead of for the
4994               (now hidden) mini-buffer contents.  */
4995            || (EQ (minibuf_window, selected_window)
4996                && EQ (minibuf_window, echo_area_window)
4997                && !NILP (echo_area_buffer[0])))
4998           /* These cases apply only to the frame that contains
4999              the active mini-buffer window.  */
5000           && FRAME_HAS_MINIBUF_P (f)
5001           && EQ (FRAME_MINIBUF_WINDOW (f), echo_area_window))
5002         {
5003           int top = WINDOW_TOP_EDGE_LINE (XWINDOW (FRAME_MINIBUF_WINDOW (f)));
5004           int row, col;
5005 
5006           if (cursor_in_echo_area < 0)
5007             {
5008               /* Negative value of cursor_in_echo_area means put
5009                  cursor at beginning of line.  */
5010               row = top;
5011               col = 0;
5012             }
5013           else
5014             {
5015               /* Positive value of cursor_in_echo_area means put
5016                  cursor at the end of the prompt.  If the mini-buffer
5017                  is several lines high, find the last line that has
5018                  any text on it.  */
5019               row = FRAME_LINES (f);
5020               do
5021                 {
5022                   --row;
5023                   col = 0;
5024 
5025                   if (MATRIX_ROW_ENABLED_P (current_matrix, row))
5026                     {
5027                       /* Frame rows are filled up with spaces that
5028                          must be ignored here.  */
5029                       struct glyph_row *r = MATRIX_ROW (current_matrix,
5030                                                         row);
5031                       struct glyph *start = r->glyphs[TEXT_AREA];
5032                       struct glyph *last = start + r->used[TEXT_AREA];
5033 
5034                       while (last > start
5035                              && (last - 1)->charpos < 0)
5036                         --last;
5037 
5038                       col = last - start;
5039                     }
5040                 }
5041               while (row > top && col == 0);
5042 
5043               /* Make sure COL is not out of range.  */
5044               if (col >= FRAME_CURSOR_X_LIMIT (f))
5045                 {
5046                   /* If we have another row, advance cursor into it.  */
5047                   if (row < FRAME_LINES (f) - 1)
5048                     {
5049                       col = FRAME_LEFT_SCROLL_BAR_COLS (f);
5050                       row++;
5051                     }
5052                   /* Otherwise move it back in range.  */
5053                   else
5054                     col = FRAME_CURSOR_X_LIMIT (f) - 1;
5055                 }
5056             }
5057 
5058           cursor_to (f, row, col);
5059         }
5060       else
5061         {
5062           /* We have only one cursor on terminal frames.  Use it to
5063              display the cursor of the selected window.  */
5064           struct window *w = XWINDOW (FRAME_SELECTED_WINDOW (f));
5065           if (w->cursor.vpos >= 0
5066               /* The cursor vpos may be temporarily out of bounds
5067                  in the following situation:  There is one window,
5068                  with the cursor in the lower half of it.  The window
5069                  is split, and a message causes a redisplay before
5070                  a new cursor position has been computed.  */
5071               && w->cursor.vpos < WINDOW_TOTAL_LINES (w))
5072             {
5073               int x = WINDOW_TO_FRAME_HPOS (w, w->cursor.hpos);
5074               int y = WINDOW_TO_FRAME_VPOS (w, w->cursor.vpos);
5075 
5076               if (INTEGERP (w->left_margin_cols))
5077                 x += XFASTINT (w->left_margin_cols);
5078 
5079               /* x = max (min (x, FRAME_TOTAL_COLS (f) - 1), 0); */
5080               cursor_to (f, y, x);
5081             }
5082         }
5083     }
5084 
5085  do_pause:
5086 
5087   clear_desired_matrices (f);
5088   return pause;
5089 }
5090 
5091 
5092 /* Do line insertions/deletions on frame F for frame-based redisplay.  */
5093 
5094 int
5095 scrolling (frame)
5096      struct frame *frame;
5097 {
5098   int unchanged_at_top, unchanged_at_bottom;
5099   int window_size;
5100   int changed_lines;
5101   int *old_hash = (int *) alloca (FRAME_LINES (frame) * sizeof (int));
5102   int *new_hash = (int *) alloca (FRAME_LINES (frame) * sizeof (int));
5103   int *draw_cost = (int *) alloca (FRAME_LINES (frame) * sizeof (int));
5104   int *old_draw_cost = (int *) alloca (FRAME_LINES (frame) * sizeof (int));
5105   register int i;
5106   int free_at_end_vpos = FRAME_LINES (frame);
5107   struct glyph_matrix *current_matrix = frame->current_matrix;
5108   struct glyph_matrix *desired_matrix = frame->desired_matrix;
5109 
5110   if (!current_matrix)
5111     abort ();
5112 
5113   /* Compute hash codes of all the lines.  Also calculate number of
5114      changed lines, number of unchanged lines at the beginning, and
5115      number of unchanged lines at the end.  */
5116   changed_lines = 0;
5117   unchanged_at_top = 0;
5118   unchanged_at_bottom = FRAME_LINES (frame);
5119   for (i = 0; i < FRAME_LINES (frame); i++)
5120     {
5121       /* Give up on this scrolling if some old lines are not enabled.  */
5122       if (!MATRIX_ROW_ENABLED_P (current_matrix, i))
5123         return 0;
5124       old_hash[i] = line_hash_code (MATRIX_ROW (current_matrix, i));
5125       if (! MATRIX_ROW_ENABLED_P (desired_matrix, i))
5126         {
5127           /* This line cannot be redrawn, so don't let scrolling mess it.  */
5128           new_hash[i] = old_hash[i];
5129 #define INFINITY 1000000        /* Taken from scroll.c */
5130           draw_cost[i] = INFINITY;
5131         }
5132       else
5133         {
5134           new_hash[i] = line_hash_code (MATRIX_ROW (desired_matrix, i));
5135           draw_cost[i] = line_draw_cost (desired_matrix, i);
5136         }
5137 
5138       if (old_hash[i] != new_hash[i])
5139         {
5140           changed_lines++;
5141           unchanged_at_bottom = FRAME_LINES (frame) - i - 1;
5142         }
5143       else if (i == unchanged_at_top)
5144         unchanged_at_top++;
5145       old_draw_cost[i] = line_draw_cost (current_matrix, i);
5146     }
5147 
5148   /* If changed lines are few, don't allow preemption, don't scroll.  */
5149   if ((!FRAME_SCROLL_REGION_OK (frame)
5150        && changed_lines < baud_rate / 2400)
5151       || unchanged_at_bottom == FRAME_LINES (frame))
5152     return 1;
5153 
5154   window_size = (FRAME_LINES (frame) - unchanged_at_top
5155                  - unchanged_at_bottom);
5156 
5157   if (FRAME_SCROLL_REGION_OK (frame))
5158     free_at_end_vpos -= unchanged_at_bottom;
5159   else if (FRAME_MEMORY_BELOW_FRAME (frame))
5160     free_at_end_vpos = -1;
5161 
5162   /* If large window, fast terminal and few lines in common between
5163      current frame and desired frame, don't bother with i/d calc.  */
5164   if (!FRAME_SCROLL_REGION_OK (frame)
5165       && window_size >= 18 && baud_rate > 2400
5166       && (window_size >=
5167           10 * scrolling_max_lines_saved (unchanged_at_top,
5168                                           FRAME_LINES (frame) - unchanged_at_bottom,
5169                                           old_hash, new_hash, draw_cost)))
5170     return 0;
5171 
5172   if (window_size < 2)
5173     return 0;
5174 
5175   scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
5176                draw_cost + unchanged_at_top - 1,
5177                old_draw_cost + unchanged_at_top - 1,
5178                old_hash + unchanged_at_top - 1,
5179                new_hash + unchanged_at_top - 1,
5180                free_at_end_vpos - unchanged_at_top);
5181 
5182   return 0;
5183 }
5184 
5185 
5186 /* Count the number of blanks at the start of the vector of glyphs R
5187    which is LEN glyphs long.  */
5188 
5189 static int
5190 count_blanks (r, len)
5191      struct glyph *r;
5192      int len;
5193 {
5194   int i;
5195 
5196   for (i = 0; i < len; ++i)
5197     if (!CHAR_GLYPH_SPACE_P (r[i]))
5198       break;
5199 
5200   return i;
5201 }
5202 
5203 
5204 /* Count the number of glyphs in common at the start of the glyph
5205    vectors STR1 and STR2.  END1 is the end of STR1 and END2 is the end
5206    of STR2.  Value is the number of equal glyphs equal at the start.  */
5207 
5208 static int
5209 count_match (str1, end1, str2, end2)
5210      struct glyph *str1, *end1, *str2, *end2;
5211 {
5212   struct glyph *p1 = str1;
5213   struct glyph *p2 = str2;
5214 
5215   while (p1 < end1
5216          && p2 < end2
5217          && GLYPH_CHAR_AND_FACE_EQUAL_P (p1, p2))
5218     ++p1, ++p2;
5219 
5220   return p1 - str1;
5221 }
5222 
5223 
5224 /* Char insertion/deletion cost vector, from term.c */
5225 
5226 extern int *char_ins_del_vector;
5227 #define char_ins_del_cost(f) (&char_ins_del_vector[FRAME_TOTAL_COLS((f))])
5228 
5229 
5230 /* Perform a frame-based update on line VPOS in frame FRAME.  */
5231 
5232 static void
5233 update_frame_line (f, vpos)
5234      struct frame *f;
5235      int vpos;
5236 {
5237   struct glyph *obody, *nbody, *op1, *op2, *np1, *nend;
5238   int tem;
5239   int osp, nsp, begmatch, endmatch, olen, nlen;
5240   struct glyph_matrix *current_matrix = f->current_matrix;
5241   struct glyph_matrix *desired_matrix = f->desired_matrix;
5242   struct glyph_row *current_row = MATRIX_ROW (current_matrix, vpos);
5243   struct glyph_row *desired_row = MATRIX_ROW (desired_matrix, vpos);
5244   int must_write_whole_line_p;
5245   int write_spaces_p = FRAME_MUST_WRITE_SPACES (f);
5246   int colored_spaces_p = (FACE_FROM_ID (f, DEFAULT_FACE_ID)->background
5247                           != FACE_TTY_DEFAULT_BG_COLOR);
5248 
5249   if (colored_spaces_p)
5250     write_spaces_p = 1;
5251 
5252   /* Current row not enabled means it has unknown contents.  We must
5253      write the whole desired line in that case.  */
5254   must_write_whole_line_p = !current_row->enabled_p;
5255   if (must_write_whole_line_p)
5256     {
5257       obody = 0;
5258       olen = 0;
5259     }
5260   else
5261     {
5262       obody = MATRIX_ROW_GLYPH_START (current_matrix, vpos);
5263       olen = current_row->used[TEXT_AREA];
5264 
5265       /* Ignore trailing spaces, if we can.  */
5266       if (!write_spaces_p)
5267         while (olen > 0 && CHAR_GLYPH_SPACE_P (obody[olen-1]))
5268           olen--;
5269     }
5270 
5271   current_row->enabled_p = 1;
5272   current_row->used[TEXT_AREA] = desired_row->used[TEXT_AREA];
5273 
5274   /* If desired line is empty, just clear the line.  */
5275   if (!desired_row->enabled_p)
5276     {
5277       nlen = 0;
5278       goto just_erase;
5279     }
5280 
5281   nbody = desired_row->glyphs[TEXT_AREA];
5282   nlen = desired_row->used[TEXT_AREA];
5283   nend = nbody + nlen;
5284 
5285   /* If display line has unknown contents, write the whole line.  */
5286   if (must_write_whole_line_p)
5287     {
5288       /* Ignore spaces at the end, if we can.  */
5289       if (!write_spaces_p)
5290         while (nlen > 0 && CHAR_GLYPH_SPACE_P (nbody[nlen - 1]))
5291           --nlen;
5292 
5293       /* Write the contents of the desired line.  */
5294       if (nlen)
5295         {
5296           cursor_to (f, vpos, 0);
5297           write_glyphs (f, nbody, nlen);
5298         }
5299 
5300       /* Don't call clear_end_of_line if we already wrote the whole
5301          line.  The cursor will not be at the right margin in that
5302          case but in the line below.  */
5303       if (nlen < FRAME_TOTAL_COLS (f))
5304         {
5305           cursor_to (f, vpos, nlen);
5306           clear_end_of_line (f, FRAME_TOTAL_COLS (f));
5307         }
5308       else
5309         /* Make sure we are in the right row, otherwise cursor movement
5310            with cmgoto might use `ch' in the wrong row.  */
5311         cursor_to (f, vpos, 0);
5312 
5313       make_current (desired_matrix, current_matrix, vpos);
5314       return;
5315     }
5316 
5317   /* Pretend trailing spaces are not there at all,
5318      unless for one reason or another we must write all spaces.  */
5319   if (!write_spaces_p)
5320     while (nlen > 0 && CHAR_GLYPH_SPACE_P (nbody[nlen - 1]))
5321       nlen--;
5322 
5323   /* If there's no i/d char, quickly do the best we can without it.  */
5324   if (!FRAME_CHAR_INS_DEL_OK (f))
5325     {
5326       int i, j;
5327 
5328       /* Find the first glyph in desired row that doesn't agree with
5329          a glyph in the current row, and write the rest from there on.  */
5330       for (i = 0; i < nlen; i++)
5331         {
5332           if (i >= olen || !GLYPH_EQUAL_P (nbody + i, obody + i))
5333             {
5334               /* Find the end of the run of different glyphs.  */
5335               j = i + 1;
5336               while (j < nlen
5337                      && (j >= olen
5338                          || !GLYPH_EQUAL_P (nbody + j, obody + j)
5339                          || CHAR_GLYPH_PADDING_P (nbody[j])))
5340                 ++j;
5341 
5342               /* Output this run of non-matching chars.  */
5343               cursor_to (f, vpos, i);
5344               write_glyphs (f, nbody + i, j - i);
5345               i = j - 1;
5346 
5347               /* Now find the next non-match.  */
5348             }
5349         }
5350 
5351       /* Clear the rest of the line, or the non-clear part of it.  */
5352       if (olen > nlen)
5353         {
5354           cursor_to (f, vpos, nlen);
5355           clear_end_of_line (f, olen);
5356         }
5357 
5358       /* Make current row = desired row.  */
5359       make_current (desired_matrix, current_matrix, vpos);
5360       return;
5361     }
5362 
5363   /* Here when CHAR_INS_DEL_OK != 0, i.e. we can insert or delete
5364      characters in a row.  */
5365 
5366   if (!olen)
5367     {
5368       /* If current line is blank, skip over initial spaces, if
5369          possible, and write the rest.  */
5370       if (write_spaces_p)
5371         nsp = 0;
5372       else
5373         nsp = count_blanks (nbody, nlen);
5374 
5375       if (nlen > nsp)
5376         {
5377           cursor_to (f, vpos, nsp);
5378           write_glyphs (f, nbody + nsp, nlen - nsp);
5379         }
5380 
5381       /* Exchange contents between current_frame and new_frame.  */
5382       make_current (desired_matrix, current_matrix, vpos);
5383       return;
5384     }
5385 
5386   /* Compute number of leading blanks in old and new contents.  */
5387   osp = count_blanks (obody, olen);
5388   nsp = (colored_spaces_p ? 0 : count_blanks (nbody, nlen));
5389 
5390   /* Compute number of matching chars starting with first non-blank.  */
5391   begmatch = count_match (obody + osp, obody + olen,
5392                           nbody + nsp, nbody + nlen);
5393 
5394   /* Spaces in new match implicit space past the end of old.  */
5395   /* A bug causing this to be a no-op was fixed in 18.29.  */
5396   if (!write_spaces_p && osp + begmatch == olen)
5397     {
5398       np1 = nbody + nsp;
5399       while (np1 + begmatch < nend && CHAR_GLYPH_SPACE_P (np1[begmatch]))
5400         ++begmatch;
5401     }
5402 
5403   /* Avoid doing insert/delete char
5404      just cause number of leading spaces differs
5405      when the following text does not match.  */
5406   if (begmatch == 0 && osp != nsp)
5407     osp = nsp = min (osp, nsp);
5408 
5409   /* Find matching characters at end of line */
5410   op1 = obody + olen;
5411   np1 = nbody + nlen;
5412   op2 = op1 + begmatch - min (olen - osp, nlen - nsp);
5413   while (op1 > op2
5414          && GLYPH_EQUAL_P (op1 - 1, np1 - 1))
5415     {
5416       op1--;
5417       np1--;
5418     }
5419   endmatch = obody + olen - op1;
5420 
5421   /* tem gets the distance to insert or delete.
5422      endmatch is how many characters we save by doing so.
5423      Is it worth it?  */
5424 
5425   tem = (nlen - nsp) - (olen - osp);
5426   if (endmatch && tem
5427       && (!FRAME_CHAR_INS_DEL_OK (f)
5428           || endmatch <= char_ins_del_cost (f)[tem]))
5429     endmatch = 0;
5430 
5431   /* nsp - osp is the distance to insert or delete.
5432      If that is nonzero, begmatch is known to be nonzero also.
5433      begmatch + endmatch is how much we save by doing the ins/del.
5434      Is it worth it?  */
5435 
5436   if (nsp != osp
5437       && (!FRAME_CHAR_INS_DEL_OK (f)
5438           || begmatch + endmatch <= char_ins_del_cost (f)[nsp - osp]))
5439     {
5440       begmatch = 0;
5441       endmatch = 0;
5442       osp = nsp = min (osp, nsp);
5443     }
5444 
5445   /* Now go through the line, inserting, writing and
5446      deleting as appropriate.  */
5447 
5448   if (osp > nsp)
5449     {
5450       cursor_to (f, vpos, nsp);
5451       delete_glyphs (f, osp - nsp);
5452     }
5453   else if (nsp > osp)
5454     {
5455       /* If going to delete chars later in line
5456          and insert earlier in the line,
5457          must delete first to avoid losing data in the insert */
5458       if (endmatch && nlen < olen + nsp - osp)
5459         {
5460           cursor_to (f, vpos, nlen - endmatch + osp - nsp);
5461           delete_glyphs (f, olen + nsp - osp - nlen);
5462           olen = nlen - (nsp - osp);
5463         }
5464       cursor_to (f, vpos, osp);
5465       insert_glyphs (f, 0, nsp - osp);
5466     }
5467   olen += nsp - osp;
5468 
5469   tem = nsp + begmatch + endmatch;
5470   if (nlen != tem || olen != tem)
5471     {
5472       if (!endmatch || nlen == olen)
5473         {
5474           /* If new text being written reaches right margin, there is
5475              no need to do clear-to-eol at the end of this function
5476              (and it would not be safe, since cursor is not going to
5477              be "at the margin" after the text is done).  */
5478           if (nlen == FRAME_TOTAL_COLS (f))
5479             olen = 0;
5480 
5481           /* Function write_glyphs is prepared to do nothing
5482              if passed a length <= 0.  Check it here to avoid
5483              unnecessary cursor movement.  */
5484           if (nlen - tem > 0)
5485             {
5486               cursor_to (f, vpos, nsp + begmatch);
5487               write_glyphs (f, nbody + nsp + begmatch, nlen - tem);
5488             }
5489         }
5490       else if (nlen > olen)
5491         {
5492           /* Here, we used to have the following simple code:
5493              ----------------------------------------
5494              write_glyphs (nbody + nsp + begmatch, olen - tem);
5495              insert_glyphs (nbody + nsp + begmatch + olen - tem, nlen - olen);
5496              ----------------------------------------
5497              but it doesn't work if nbody[nsp + begmatch + olen - tem]
5498              is a padding glyph.  */
5499           int out = olen - tem; /* Columns to be overwritten originally.  */
5500           int del;
5501 
5502           cursor_to (f, vpos, nsp + begmatch);
5503 
5504           /* Calculate columns we can actually overwrite.  */
5505           while (CHAR_GLYPH_PADDING_P (nbody[nsp + begmatch + out]))
5506             out--;
5507           write_glyphs (f, nbody + nsp + begmatch, out);
5508 
5509           /* If we left columns to be overwritten, we must delete them.  */
5510           del = olen - tem - out;
5511           if (del > 0)
5512             delete_glyphs (f, del);
5513 
5514           /* At last, we insert columns not yet written out.  */
5515           insert_glyphs (f, nbody + nsp + begmatch + out, nlen - olen + del);
5516           olen = nlen;
5517         }
5518       else if (olen > nlen)
5519         {
5520           cursor_to (f, vpos, nsp + begmatch);
5521           write_glyphs (f, nbody + nsp + begmatch, nlen - tem);
5522           delete_glyphs (f, olen - nlen);
5523           olen = nlen;
5524         }
5525     }
5526 
5527  just_erase:
5528   /* If any unerased characters remain after the new line, erase them.  */
5529   if (olen > nlen)
5530     {
5531       cursor_to (f, vpos, nlen);
5532       clear_end_of_line (f, olen);
5533     }
5534 
5535   /* Exchange contents between current_frame and new_frame.  */
5536   make_current (desired_matrix, current_matrix, vpos);
5537 }
5538 
5539 
5540 
5541 /***********************************************************************
5542                    X/Y Position -> Buffer Position
5543  ***********************************************************************/
5544 
5545 /* Determine what's under window-relative pixel position (*X, *Y).
5546    Return the object (string or buffer) that's there.
5547    Return in *POS the position in that object.
5548    Adjust *X and *Y to character positions.  */
5549 
5550 Lisp_Object
5551 buffer_posn_from_coords (w, x, y, pos, object, dx, dy, width, height)
5552      struct window *w;
5553      int *x, *y;
5554      struct display_pos *pos;
5555      Lisp_Object *object;
5556      int *dx, *dy;
5557      int *width, *height;
5558 {
5559   struct it it;
5560   Lisp_Object old_current_buffer = Fcurrent_buffer ();
5561   struct text_pos startp;
5562   Lisp_Object string;
5563   struct glyph_row *row;
5564 #ifdef HAVE_WINDOW_SYSTEM
5565   struct image *img = 0;
5566 #endif
5567   int x0, x1;
5568 
5569   /* We used to set current_buffer directly here, but that does the
5570      wrong thing with `face-remapping-alist' (bug#2044).  */
5571   Fset_buffer (w->buffer);
5572   SET_TEXT_POS_FROM_MARKER (startp, w->start);
5573   CHARPOS (startp) = min (ZV, max (BEGV, CHARPOS (startp)));
5574   BYTEPOS (startp) = min (ZV_BYTE, max (BEGV_BYTE, BYTEPOS (startp)));
5575   start_display (&it, w, startp);
5576 
5577   x0 = *x - WINDOW_LEFT_MARGIN_WIDTH (w);
5578   move_it_to (&it, -1, x0 + it.first_visible_x, *y, -1,
5579               MOVE_TO_X | MOVE_TO_Y);
5580 
5581   Fset_buffer (old_current_buffer);
5582 
5583   *dx = x0 + it.first_visible_x - it.current_x;
5584   *dy = *y - it.current_y;
5585 
5586   string =  w->buffer;
5587   if (STRINGP (it.string))
5588     string = it.string;
5589   *pos = it.current;
5590 
5591 #ifdef HAVE_WINDOW_SYSTEM
5592   if (it.what == IT_IMAGE)
5593     {
5594       if ((img = IMAGE_FROM_ID (it.f, it.image_id)) != NULL
5595           && !NILP (img->spec))
5596         *object = img->spec;
5597     }
5598 #endif
5599 
5600   if (it.vpos < w->current_matrix->nrows
5601       && (row = MATRIX_ROW (w->current_matrix, it.vpos),
5602           row->enabled_p))
5603     {
5604       if (it.hpos < row->used[TEXT_AREA])
5605         {
5606           struct glyph *glyph = row->glyphs[TEXT_AREA] + it.hpos;
5607 #ifdef HAVE_WINDOW_SYSTEM
5608           if (img)
5609             {
5610               *dy -= row->ascent - glyph->ascent;
5611               *dx += glyph->slice.x;
5612               *dy += glyph->slice.y;
5613               /* Image slices positions are still relative to the entire image */
5614               *width = img->width;
5615               *height = img->height;
5616             }
5617           else
5618 #endif
5619             {
5620               *width = glyph->pixel_width;
5621               *height = glyph->ascent + glyph->descent;
5622             }
5623         }
5624       else
5625         {
5626           *width = 0;
5627           *height = row->height;
5628         }
5629     }
5630   else
5631     {
5632       *width = *height = 0;
5633     }
5634 
5635   /* Add extra (default width) columns if clicked after EOL. */
5636   x1 = max(0, it.current_x + it.pixel_width - it.first_visible_x);
5637   if (x0 > x1)
5638     it.hpos += (x0 - x1) / WINDOW_FRAME_COLUMN_WIDTH (w);
5639 
5640   *x = it.hpos;
5641   *y = it.vpos;
5642 
5643   return string;
5644 }
5645 
5646 
5647 /* Value is the string under window-relative coordinates X/Y in the
5648    mode line or header line (PART says which) of window W, or nil if none.
5649    *CHARPOS is set to the position in the string returned.  */
5650 
5651 Lisp_Object
5652 mode_line_string (w, part, x, y, charpos, object, dx, dy, width, height)
5653      struct window *w;
5654      enum window_part part;
5655      int *x, *y;
5656      int *charpos;
5657      Lisp_Object *object;
5658      int *dx, *dy;
5659      int *width, *height;
5660 {
5661   struct glyph_row *row;
5662   struct glyph *glyph, *end;
5663   int x0, y0;
5664   Lisp_Object string = Qnil;
5665 
5666   if (part == ON_MODE_LINE)
5667     row = MATRIX_MODE_LINE_ROW (w->current_matrix);
5668   else
5669     row = MATRIX_HEADER_LINE_ROW (w->current_matrix);
5670   y0 = *y - row->y;
5671   *y = row - MATRIX_FIRST_TEXT_ROW (w->current_matrix);
5672 
5673   if (row->mode_line_p && row->enabled_p)
5674     {
5675       /* Find the glyph under X.  If we find one with a string object,
5676          it's the one we were looking for.  */
5677       glyph = row->glyphs[TEXT_AREA];
5678       end = glyph + row->used[TEXT_AREA];
5679       for (x0 = *x; glyph < end && x0 >= glyph->pixel_width; ++glyph)
5680         x0 -= glyph->pixel_width;
5681       *x = glyph - row->glyphs[TEXT_AREA];
5682       if (glyph < end)
5683         {
5684           string = glyph->object;
5685           *charpos = glyph->charpos;
5686           *width = glyph->pixel_width;
5687           *height = glyph->ascent + glyph->descent;
5688 #ifdef HAVE_WINDOW_SYSTEM
5689           if (glyph->type == IMAGE_GLYPH)
5690             {
5691               struct image *img;
5692               img = IMAGE_FROM_ID (WINDOW_XFRAME (w), glyph->u.img_id);
5693               if (img != NULL)
5694                 *object = img->spec;
5695               y0 -= row->ascent - glyph->ascent;
5696             }
5697 #endif
5698         }
5699       else
5700         {
5701           /* Add extra (default width) columns if clicked after EOL. */
5702           *x += x0 / WINDOW_FRAME_COLUMN_WIDTH (w);
5703           *width = 0;
5704           *height = row->height;
5705         }
5706     }
5707   else
5708     {
5709       *x = 0;
5710       x0 = 0;
5711       *width = *height = 0;
5712     }
5713 
5714   *dx = x0;
5715   *dy = y0;
5716 
5717   return string;
5718 }
5719 
5720 
5721 /* Value is the string under window-relative coordinates X/Y in either
5722    marginal area, or nil if none.  *CHARPOS is set to the position in
5723    the string returned.  */
5724 
5725 Lisp_Object
5726 marginal_area_string (w, part, x, y, charpos, object, dx, dy, width, height)
5727      struct window *w;
5728      enum window_part part;
5729      int *x, *y;
5730      int *charpos;
5731      Lisp_Object *object;
5732      int *dx, *dy;
5733      int *width, *height;
5734 {
5735   struct glyph_row *row = w->current_matrix->rows;
5736   struct glyph *glyph, *end;
5737   int x0, y0, i, wy = *y;
5738   int area;
5739   Lisp_Object string = Qnil;
5740 
5741   if (part == ON_LEFT_MARGIN)
5742     area = LEFT_MARGIN_AREA;
5743   else if (part == ON_RIGHT_MARGIN)
5744     area = RIGHT_MARGIN_AREA;
5745   else
5746     abort ();
5747 
5748   for (i = 0; row->enabled_p && i < w->current_matrix->nrows; ++i, ++row)
5749     if (wy >= row->y && wy < MATRIX_ROW_BOTTOM_Y (row))
5750       break;
5751   y0 = *y - row->y;
5752   *y = row - MATRIX_FIRST_TEXT_ROW (w->current_matrix);
5753 
5754   if (row->enabled_p)
5755     {
5756       /* Find the glyph under X.  If we find one with a string object,
5757          it's the one we were looking for.  */
5758       if (area == RIGHT_MARGIN_AREA)
5759         x0 = ((WINDOW_HAS_FRINGES_OUTSIDE_MARGINS (w)
5760                ? WINDOW_LEFT_FRINGE_WIDTH (w)
5761                : WINDOW_TOTAL_FRINGE_WIDTH (w))
5762               + window_box_width (w, LEFT_MARGIN_AREA)
5763               + window_box_width (w, TEXT_AREA));
5764       else
5765         x0 = (WINDOW_HAS_FRINGES_OUTSIDE_MARGINS (w)
5766               ? WINDOW_LEFT_FRINGE_WIDTH (w)
5767               : 0);
5768 
5769       glyph = row->glyphs[area];
5770       end = glyph + row->used[area];
5771       for (x0 = *x - x0; glyph < end && x0 >= glyph->pixel_width; ++glyph)
5772         x0 -= glyph->pixel_width;
5773       *x = glyph - row->glyphs[area];
5774       if (glyph < end)
5775         {
5776           string = glyph->object;
5777           *charpos = glyph->charpos;
5778           *width = glyph->pixel_width;
5779           *height = glyph->ascent + glyph->descent;
5780 #ifdef HAVE_WINDOW_SYSTEM
5781           if (glyph->type == IMAGE_GLYPH)
5782             {
5783               struct image *img;
5784               img = IMAGE_FROM_ID (WINDOW_XFRAME (w), glyph->u.img_id);
5785               if (img != NULL)
5786                 *object = img->spec;
5787               y0 -= row->ascent - glyph->ascent;
5788               x0 += glyph->slice.x;
5789               y0 += glyph->slice.y;
5790             }
5791 #endif
5792         }
5793       else
5794         {
5795           /* Add extra (default width) columns if clicked after EOL. */
5796           *x += x0 / WINDOW_FRAME_COLUMN_WIDTH (w);
5797           *width = 0;
5798           *height = row->height;
5799         }
5800     }
5801   else
5802     {
5803       x0 = 0;
5804       *x = 0;
5805       *width = *height = 0;
5806     }
5807 
5808   *dx = x0;
5809   *dy = y0;
5810 
5811   return string;
5812 }
5813 
5814 
5815 /***********************************************************************
5816                          Changing Frame Sizes
5817  ***********************************************************************/
5818 
5819 #ifdef SIGWINCH
5820 
5821 SIGTYPE
5822 window_change_signal (signalnum) /* If we don't have an argument, */
5823      int signalnum;             /* some compilers complain in signal calls.  */
5824 {
5825   int width, height;
5826   int old_errno = errno;
5827 
5828   struct tty_display_info *tty;
5829 
5830   signal (SIGWINCH, window_change_signal);
5831   SIGNAL_THREAD_CHECK (signalnum);
5832 
5833   /* The frame size change obviously applies to a single
5834      termcap-controlled terminal, but we can't decide which.
5835      Therefore, we resize the frames corresponding to each tty.
5836   */
5837   for (tty = tty_list; tty; tty = tty->next) {
5838 
5839     if (! tty->term_initted)
5840       continue;
5841 
5842     /* Suspended tty frames have tty->input == NULL avoid trying to
5843        use it.  */
5844     if (!tty->input)
5845       continue;
5846 
5847     get_tty_size (fileno (tty->input), &width, &height);
5848 
5849     if (width > 5 && height > 2) {
5850       Lisp_Object tail, frame;
5851 
5852       FOR_EACH_FRAME (tail, frame)
5853         if (FRAME_TERMCAP_P (XFRAME (frame)) && FRAME_TTY (XFRAME (frame)) == tty)
5854           /* Record the new sizes, but don't reallocate the data
5855              structures now.  Let that be done later outside of the
5856              signal handler.  */
5857           change_frame_size (XFRAME (frame), height, width, 0, 1, 0);
5858     }
5859   }
5860 
5861   errno = old_errno;
5862 }
5863 #endif /* SIGWINCH */
5864 
5865 
5866 /* Do any change in frame size that was requested by a signal.  SAFE
5867    non-zero means this function is called from a place where it is
5868    safe to change frame sizes  while a redisplay is in progress.  */
5869 
5870 void
5871 do_pending_window_change (safe)
5872      int safe;
5873 {
5874   /* If window_change_signal should have run before, run it now.  */
5875   if (redisplaying_p && !safe)
5876     return;
5877 
5878   while (delayed_size_change)
5879     {
5880       Lisp_Object tail, frame;
5881 
5882       delayed_size_change = 0;
5883 
5884       FOR_EACH_FRAME (tail, frame)
5885         {
5886           struct frame *f = XFRAME (frame);
5887 
5888           if (f->new_text_lines != 0 || f->new_text_cols != 0)
5889             change_frame_size (f, f->new_text_lines, f->new_text_cols,
5890                                0, 0, safe);
5891         }
5892     }
5893 }
5894 
5895 
5896 /* Change the frame height and/or width.  Values may be given as zero to
5897    indicate no change is to take place.
5898 
5899    If DELAY is non-zero, then assume we're being called from a signal
5900    handler, and queue the change for later - perhaps the next
5901    redisplay.  Since this tries to resize windows, we can't call it
5902    from a signal handler.
5903 
5904    SAFE non-zero means this function is called from a place where it's
5905    safe to change frame sizes while a redisplay is in progress.  */
5906 
5907 void
5908 change_frame_size (f, newheight, newwidth, pretend, delay, safe)
5909      register struct frame *f;
5910      int newheight, newwidth, pretend, delay, safe;
5911 {
5912   Lisp_Object tail, frame;
5913 
5914   if (FRAME_MSDOS_P (f))
5915     {
5916       /* On MS-DOS, all frames use the same screen, so a change in
5917          size affects all frames.  Termcap now supports multiple
5918          ttys. */
5919       FOR_EACH_FRAME (tail, frame)
5920         if (! FRAME_WINDOW_P (XFRAME (frame)))
5921           change_frame_size_1 (XFRAME (frame), newheight, newwidth,
5922                                pretend, delay, safe);
5923     }
5924   else
5925     change_frame_size_1 (f, newheight, newwidth, pretend, delay, safe);
5926 }
5927 
5928 static void
5929 change_frame_size_1 (f, newheight, newwidth, pretend, delay, safe)
5930      register struct frame *f;
5931      int newheight, newwidth, pretend, delay, safe;
5932 {
5933   int new_frame_total_cols;
5934   int count = SPECPDL_INDEX ();
5935 
5936   /* If we can't deal with the change now, queue it for later.  */
5937   if (delay || (redisplaying_p && !safe))
5938     {
5939       f->new_text_lines = newheight;
5940       f->new_text_cols = newwidth;
5941       delayed_size_change = 1;
5942       return;
5943     }
5944 
5945   /* This size-change overrides any pending one for this frame.  */
5946   f->new_text_lines = 0;
5947   f->new_text_cols = 0;
5948 
5949   /* If an argument is zero, set it to the current value.  */
5950   if (newheight == 0)
5951     newheight = FRAME_LINES (f);
5952   if (newwidth == 0)
5953     newwidth  = FRAME_COLS  (f);
5954 
5955   /* Compute width of windows in F.
5956      This is the width of the frame without vertical scroll bars.  */
5957   new_frame_total_cols = FRAME_TOTAL_COLS_ARG (f, newwidth);
5958 
5959   /* Round up to the smallest acceptable size.  */
5960   check_frame_size (f, &newheight, &newwidth);
5961 
5962   /* If we're not changing the frame size, quit now.  */
5963   /* Frame width may be unchanged but the text portion may change, for example,
5964      fullscreen and remove/add scroll bar.  */
5965   if (newheight == FRAME_LINES (f)
5966       && newwidth == FRAME_COLS  (f) // text portion unchanged
5967       && new_frame_total_cols == FRAME_TOTAL_COLS (f)) // frame width unchanged
5968     return;
5969 
5970   BLOCK_INPUT;
5971 
5972 #ifdef MSDOS
5973   /* We only can set screen dimensions to certain values supported
5974      by our video hardware.  Try to find the smallest size greater
5975      or equal to the requested dimensions.  */
5976   dos_set_window_size (&newheight, &newwidth);
5977 #endif
5978 
5979   if (newheight != FRAME_LINES (f))
5980     {
5981       if (FRAME_HAS_MINIBUF_P (f) && !FRAME_MINIBUF_ONLY_P (f))
5982         {
5983           /* Frame has both root and mini-buffer.  */
5984           XSETFASTINT (XWINDOW (FRAME_ROOT_WINDOW (f))->top_line,
5985                        FRAME_TOP_MARGIN (f));
5986           set_window_height (FRAME_ROOT_WINDOW (f),
5987                              (newheight
5988                               - 1
5989                               - FRAME_TOP_MARGIN (f)),
5990                              2);
5991           XSETFASTINT (XWINDOW (FRAME_MINIBUF_WINDOW (f))->top_line,
5992                        newheight - 1);
5993           set_window_height (FRAME_MINIBUF_WINDOW (f), 1, 0);
5994         }
5995       else
5996         /* Frame has just one top-level window.  */
5997         set_window_height (FRAME_ROOT_WINDOW (f),
5998                            newheight - FRAME_TOP_MARGIN (f), 2);
5999 
6000       /* MSDOS frames cannot PRETEND, as they change frame size by
6001          manipulating video hardware.  */
6002       if ((FRAME_TERMCAP_P (f) && !pretend) || FRAME_MSDOS_P (f))
6003         FrameRows (FRAME_TTY (f)) = newheight;
6004     }
6005 
6006   if (new_frame_total_cols != FRAME_TOTAL_COLS (f))
6007     {
6008       set_window_width (FRAME_ROOT_WINDOW (f), new_frame_total_cols, 2);
6009       if (FRAME_HAS_MINIBUF_P (f))
6010         set_window_width (FRAME_MINIBUF_WINDOW (f), new_frame_total_cols, 0);
6011 
6012       /* MSDOS frames cannot PRETEND, as they change frame size by
6013          manipulating video hardware.  */
6014       if ((FRAME_TERMCAP_P (f) && !pretend) || FRAME_MSDOS_P (f))
6015         FrameCols (FRAME_TTY (f)) = newwidth;
6016 
6017       if (WINDOWP (f->tool_bar_window))
6018         XSETFASTINT (XWINDOW (f->tool_bar_window)->total_cols, newwidth);
6019     }
6020 
6021   FRAME_LINES (f) = newheight;
6022   SET_FRAME_COLS (f, newwidth);
6023 
6024   {
6025     struct window *w = XWINDOW (FRAME_SELECTED_WINDOW (f));
6026     int text_area_x, text_area_y, text_area_width, text_area_height;
6027 
6028     window_box (w, TEXT_AREA, &text_area_x, &text_area_y, &text_area_width,
6029                 &text_area_height);
6030     if (w->cursor.x >= text_area_x + text_area_width)
6031       w->cursor.hpos = w->cursor.x = 0;
6032     if (w->cursor.y >= text_area_y + text_area_height)
6033       w->cursor.vpos = w->cursor.y = 0;
6034   }
6035 
6036   adjust_glyphs (f);
6037   calculate_costs (f);
6038   SET_FRAME_GARBAGED (f);
6039   f->resized_p = 1;
6040 
6041   UNBLOCK_INPUT;
6042 
6043   record_unwind_protect (Fset_buffer, Fcurrent_buffer ());
6044 
6045   run_window_configuration_change_hook (f);
6046 
6047   unbind_to (count, Qnil);
6048 }
6049 
6050 
6051 
6052 /***********************************************************************
6053                    Terminal Related Lisp Functions
6054  ***********************************************************************/
6055 
6056 DEFUN ("open-termscript", Fopen_termscript, Sopen_termscript,
6057        1, 1, "FOpen termscript file: ",
6058        doc: /* Start writing all terminal output to FILE as well as the terminal.
6059 FILE = nil means just close any termscript file currently open.  */)
6060      (file)
6061      Lisp_Object file;
6062 {
6063   struct tty_display_info *tty;
6064 
6065   if (! FRAME_TERMCAP_P (SELECTED_FRAME ())
6066       && ! FRAME_MSDOS_P (SELECTED_FRAME ()))
6067     error ("Current frame is not on a tty device");
6068 
6069   tty = CURTTY ();
6070 
6071   if (tty->termscript != 0)
6072   {
6073     BLOCK_INPUT;
6074     fclose (tty->termscript);
6075     UNBLOCK_INPUT;
6076   }
6077   tty->termscript = 0;
6078 
6079   if (! NILP (file))
6080     {
6081       file = Fexpand_file_name (file, Qnil);
6082       tty->termscript = fopen (SDATA (file), "w");
6083       if (tty->termscript == 0)
6084         report_file_error ("Opening termscript", Fcons (file, Qnil));
6085     }
6086   return Qnil;
6087 }
6088 
6089 
6090 DEFUN ("send-string-to-terminal", Fsend_string_to_terminal,
6091        Ssend_string_to_terminal, 1, 2, 0,
6092        doc: /* Send STRING to the terminal without alteration.
6093 Control characters in STRING will have terminal-dependent effects.
6094 
6095 Optional parameter TERMINAL specifies the tty terminal device to use.
6096 It may be a terminal object, a frame, or nil for the terminal used by
6097 the currently selected frame.  In batch mode, STRING is sent to stdout
6098 when TERMINAL is nil.  */)
6099   (string, terminal)
6100      Lisp_Object string;
6101      Lisp_Object terminal;
6102 {
6103   struct terminal *t = get_terminal (terminal, 1);
6104   FILE *out;
6105 
6106   /* ??? Perhaps we should do something special for multibyte strings here.  */
6107   CHECK_STRING (string);
6108   BLOCK_INPUT;
6109 
6110   if (!t)
6111     error ("Unknown terminal device");
6112 
6113   if (t->type == output_initial)
6114     out = stdout;
6115   else if (t->type != output_termcap && t->type != output_msdos_raw)
6116     error ("Device %d is not a termcap terminal device", t->id);
6117   else
6118     {
6119       struct tty_display_info *tty = t->display_info.tty;
6120 
6121       if (! tty->output)
6122         error ("Terminal is currently suspended");
6123 
6124       if (tty->termscript)
6125         {
6126           fwrite (SDATA (string), 1, SBYTES (string), tty->termscript);
6127           fflush (tty->termscript);
6128         }
6129       out = tty->output;
6130     }
6131   fwrite (SDATA (string), 1, SBYTES (string), out);
6132   fflush (out);
6133   UNBLOCK_INPUT;
6134   return Qnil;
6135 }
6136 
6137 
6138 DEFUN ("ding", Fding, Sding, 0, 1, 0,
6139        doc: /* Beep, or flash the screen.
6140 Also, unless an argument is given,
6141 terminate any keyboard macro currently executing.  */)
6142      (arg)
6143   Lisp_Object arg;
6144 {
6145   if (!NILP (arg))
6146     {
6147       if (noninteractive)
6148         putchar (07);
6149       else
6150         ring_bell (XFRAME (selected_frame));
6151     }
6152   else
6153     bitch_at_user ();
6154 
6155   return Qnil;
6156 }
6157 
6158 void
6159 bitch_at_user ()
6160 {
6161   if (noninteractive)
6162     putchar (07);
6163   else if (!INTERACTIVE)  /* Stop executing a keyboard macro.  */
6164     error ("Keyboard macro terminated by a command ringing the bell");
6165   else
6166     ring_bell (XFRAME (selected_frame));
6167 }
6168 
6169 
6170 
6171 /***********************************************************************
6172                           Sleeping, Waiting
6173  ***********************************************************************/
6174 
6175 DEFUN ("sleep-for", Fsleep_for, Ssleep_for, 1, 2, 0,
6176        doc: /* Pause, without updating display, for SECONDS seconds.
6177 SECONDS may be a floating-point value, meaning that you can wait for a
6178 fraction of a second.  Optional second arg MILLISECONDS specifies an
6179 additional wait period, in milliseconds; this may be useful if your
6180 Emacs was built without floating point support.
6181 \(Not all operating systems support waiting for a fraction of a second.)  */)
6182      (seconds, milliseconds)
6183      Lisp_Object seconds, milliseconds;
6184 {
6185   int sec, usec;
6186 
6187   if (NILP (milliseconds))
6188     XSETINT (milliseconds, 0);
6189   else
6190     CHECK_NUMBER (milliseconds);
6191   usec = XINT (milliseconds) * 1000;
6192 
6193   {
6194     double duration = extract_float (seconds);
6195     sec = (int) duration;
6196     usec += (duration - sec) * 1000000;
6197   }
6198 
6199 #ifndef EMACS_HAS_USECS
6200   if (sec == 0 && usec != 0)
6201     error ("Millisecond `sleep-for' not supported on %s", SYSTEM_TYPE);
6202 #endif
6203 
6204   /* Assure that 0 <= usec < 1000000.  */
6205   if (usec < 0)
6206     {
6207       /* We can't rely on the rounding being correct if usec is negative.  */
6208       if (-1000000 < usec)
6209         sec--, usec += 1000000;
6210       else
6211         sec -= -usec / 1000000, usec = 1000000 - (-usec % 1000000);
6212     }
6213   else
6214     sec += usec / 1000000, usec %= 1000000;
6215 
6216   if (sec < 0 || (sec == 0 && usec == 0))
6217     return Qnil;
6218 
6219   wait_reading_process_output (sec, usec, 0, 0, Qnil, NULL, 0);
6220 
6221   return Qnil;
6222 }
6223 
6224 
6225 /* This is just like wait_reading_process_output, except that
6226    it does redisplay.
6227 
6228    TIMEOUT is number of seconds to wait (float or integer),
6229    or t to wait forever.
6230    READING is 1 if reading input.
6231    If DO_DISPLAY is >0 display process output while waiting.
6232    If DO_DISPLAY is >1 perform an initial redisplay before waiting.
6233 */
6234 
6235 Lisp_Object
6236 sit_for (timeout, reading, do_display)
6237      Lisp_Object timeout;
6238      int reading, do_display;
6239 {
6240   int sec, usec;
6241 
6242   swallow_events (do_display);
6243 
6244   if ((detect_input_pending_run_timers (do_display))
6245       || !NILP (Vexecuting_kbd_macro))
6246     return Qnil;
6247 
6248   if (do_display >= 2)
6249     redisplay_preserve_echo_area (2);
6250 
6251   if (INTEGERP (timeout))
6252     {
6253       sec = XINT (timeout);
6254       usec = 0;
6255     }
6256   else if (FLOATP (timeout))
6257     {
6258       double seconds = XFLOAT_DATA (timeout);
6259       sec = (int) seconds;
6260       usec = (int) ((seconds - sec) * 1000000);
6261     }
6262   else if (EQ (timeout, Qt))
6263     {
6264       sec = 0;
6265       usec = 0;
6266     }
6267   else
6268     wrong_type_argument (Qnumberp, timeout);
6269 
6270   if (sec == 0 && usec == 0 && !EQ (timeout, Qt))
6271     return Qt;
6272 
6273 #ifdef SIGIO
6274   gobble_input (0);
6275 #endif
6276 
6277   wait_reading_process_output (sec, usec, reading ? -1 : 1, do_display,
6278                                Qnil, NULL, 0);
6279 
6280   return detect_input_pending () ? Qnil : Qt;
6281 }
6282 
6283 
6284 DEFUN ("redisplay", Fredisplay, Sredisplay, 0, 1, 0,
6285        doc: /* Perform redisplay if no input is available.
6286 If optional arg FORCE is non-nil or `redisplay-dont-pause' is non-nil,
6287 perform a full redisplay even if input is available.
6288 Return t if redisplay was performed, nil otherwise.  */)
6289      (force)
6290   Lisp_Object force;
6291 {
6292   int count;
6293 
6294   swallow_events (1);
6295   if ((detect_input_pending_run_timers (1)
6296        && NILP (force) && !redisplay_dont_pause)
6297       || !NILP (Vexecuting_kbd_macro))
6298     return Qnil;
6299 
6300   count = SPECPDL_INDEX ();
6301   if (!NILP (force) && !redisplay_dont_pause)
6302     specbind (Qredisplay_dont_pause, Qt);
6303   redisplay_preserve_echo_area (2);
6304   unbind_to (count, Qnil);
6305   return Qt;
6306 }
6307 
6308 
6309 
6310 /***********************************************************************
6311                          Other Lisp Functions
6312  ***********************************************************************/
6313 
6314 /* A vector of size >= 2 * NFRAMES + 3 * NBUFFERS + 1, containing the
6315    session's frames, frame names, buffers, buffer-read-only flags, and
6316    buffer-modified-flags.  */
6317 
6318 static Lisp_Object frame_and_buffer_state;
6319 
6320 
6321 DEFUN ("frame-or-buffer-changed-p", Fframe_or_buffer_changed_p,
6322        Sframe_or_buffer_changed_p, 0, 1, 0,
6323        doc: /* Return non-nil if the frame and buffer state appears to have changed.
6324 VARIABLE is a variable name whose value is either nil or a state vector
6325 that will be updated to contain all frames and buffers,
6326 aside from buffers whose names start with space,
6327 along with the buffers' read-only and modified flags.  This allows a fast
6328 check to see whether buffer menus might need to be recomputed.
6329 If this function returns non-nil, it updates the internal vector to reflect
6330 the current state.
6331 
6332 If VARIABLE is nil, an internal variable is used.  Users should not
6333 pass nil for VARIABLE.  */)
6334      (variable)
6335      Lisp_Object variable;
6336 {
6337   Lisp_Object state, tail, frame, buf;
6338   Lisp_Object *vecp, *end;
6339   int n;
6340 
6341   if (! NILP (variable))
6342     {
6343       CHECK_SYMBOL (variable);
6344       state = Fsymbol_value (variable);
6345       if (! VECTORP (state))
6346         goto changed;
6347     }
6348   else
6349     state = frame_and_buffer_state;
6350 
6351   vecp = XVECTOR (state)->contents;
6352   end = vecp + XVECTOR (state)->size;
6353 
6354   FOR_EACH_FRAME (tail, frame)
6355     {
6356       if (vecp == end)
6357         goto changed;
6358       if (!EQ (*vecp++, frame))
6359         goto changed;
6360       if (vecp == end)
6361         goto changed;
6362       if (!EQ (*vecp++, XFRAME (frame)->name))
6363         goto changed;
6364     }
6365   /* Check that the buffer info matches.  */
6366   for (tail = Vbuffer_alist; CONSP (tail); tail = XCDR (tail))
6367     {
6368       buf = XCDR (XCAR (tail));
6369       /* Ignore buffers that aren't included in buffer lists.  */
6370       if (SREF (XBUFFER (buf)->name, 0) == ' ')
6371         continue;
6372       if (vecp == end)
6373         goto changed;
6374       if (!EQ (*vecp++, buf))
6375         goto changed;
6376       if (vecp == end)
6377         goto changed;
6378       if (!EQ (*vecp++, XBUFFER (buf)->read_only))
6379         goto changed;
6380       if (vecp == end)
6381         goto changed;
6382       if (!EQ (*vecp++, Fbuffer_modified_p (buf)))
6383         goto changed;
6384     }
6385   if (vecp == end)
6386     goto changed;
6387   /* Detect deletion of a buffer at the end of the list.  */
6388   if (EQ (*vecp, Qlambda))
6389     return Qnil;
6390 
6391   /* Come here if we decide the data has changed.  */
6392  changed:
6393   /* Count the size we will need.
6394      Start with 1 so there is room for at least one lambda at the end.  */
6395   n = 1;
6396   FOR_EACH_FRAME (tail, frame)
6397     n += 2;
6398   for (tail = Vbuffer_alist; CONSP (tail); tail = XCDR (tail))
6399     n += 3;
6400   /* Reallocate the vector if data has grown to need it,
6401      or if it has shrunk a lot.  */
6402   if (! VECTORP (state)
6403       || n > XVECTOR (state)->size
6404       || n + 20 < XVECTOR (state)->size / 2)
6405     /* Add 20 extra so we grow it less often.  */
6406     {
6407       state = Fmake_vector (make_number (n + 20), Qlambda);
6408       if (! NILP (variable))
6409         Fset (variable, state);
6410       else
6411         frame_and_buffer_state = state;
6412     }
6413 
6414   /* Record the new data in the (possibly reallocated) vector.  */
6415   vecp = XVECTOR (state)->contents;
6416   FOR_EACH_FRAME (tail, frame)
6417     {
6418       *vecp++ = frame;
6419       *vecp++ = XFRAME (frame)->name;
6420     }
6421   for (tail = Vbuffer_alist; CONSP (tail); tail = XCDR (tail))
6422     {
6423       buf = XCDR (XCAR (tail));
6424       /* Ignore buffers that aren't included in buffer lists.  */
6425       if (SREF (XBUFFER (buf)->name, 0) == ' ')
6426         continue;
6427       *vecp++ = buf;
6428       *vecp++ = XBUFFER (buf)->read_only;
6429       *vecp++ = Fbuffer_modified_p (buf);
6430     }
6431   /* Fill up the vector with lambdas (always at least one).  */
6432   *vecp++ = Qlambda;
6433   while (vecp - XVECTOR (state)->contents
6434          < XVECTOR (state)->size)
6435     *vecp++ = Qlambda;
6436   /* Make sure we didn't overflow the vector.  */
6437   if (vecp - XVECTOR (state)->contents
6438       > XVECTOR (state)->size)
6439     abort ();
6440   return Qt;
6441 }
6442 
6443 
6444 
6445 /***********************************************************************
6446                             Initialization
6447 ***********************************************************************/
6448 
6449 /* Initialization done when Emacs fork is started, before doing stty.
6450    Determine terminal type and set terminal_driver.  Then invoke its
6451    decoding routine to set up variables in the terminal package.  */
6452 
6453 void
6454 init_display ()
6455 {
6456   char *terminal_type;
6457 
6458 #ifdef HAVE_X_WINDOWS
6459   extern int display_arg;
6460 #endif
6461 
6462   /* Construct the space glyph.  */
6463   space_glyph.type = CHAR_GLYPH;
6464   SET_CHAR_GLYPH (space_glyph, ' ', DEFAULT_FACE_ID, 0);
6465   space_glyph.charpos = -1;
6466 
6467   inverse_video = 0;
6468   cursor_in_echo_area = 0;
6469   terminal_type = (char *) 0;
6470 
6471   /* Now is the time to initialize this; it's used by init_sys_modes
6472      during startup.  */
6473   Vinitial_window_system = Qnil;
6474 
6475   /* SIGWINCH needs to be handled no matter what display we start
6476      with.  Otherwise newly opened tty frames will not resize
6477      automatically. */
6478 #ifdef SIGWINCH
6479 #ifndef CANNOT_DUMP
6480   if (initialized)
6481 #endif /* CANNOT_DUMP */
6482     signal (SIGWINCH, window_change_signal);
6483 #endif /* SIGWINCH */
6484 
6485   /* If running as a daemon, no need to initialize any frames/terminal. */
6486   if (IS_DAEMON)
6487       return;
6488 
6489   /* If the user wants to use a window system, we shouldn't bother
6490      initializing the terminal.  This is especially important when the
6491      terminal is so dumb that emacs gives up before and doesn't bother
6492      using the window system.
6493 
6494      If the DISPLAY environment variable is set and nonempty,
6495      try to use X, and die with an error message if that doesn't work.  */
6496 
6497 #ifdef HAVE_X_WINDOWS
6498   if (! inhibit_window_system && ! display_arg)
6499     {
6500       char *display;
6501       display = getenv ("DISPLAY");
6502       display_arg = (display != 0 && *display != 0);
6503 
6504       if (display_arg && !x_display_ok (display))
6505         {
6506           fprintf (stderr, "Display %s unavailable, simulating -nw\n",
6507                    display);
6508           inhibit_window_system = 1;
6509         }
6510     }
6511 
6512   if (!inhibit_window_system && display_arg
6513 #ifndef CANNOT_DUMP
6514      && initialized
6515 #endif
6516      )
6517     {
6518       Vinitial_window_system = Qx;
6519 #ifdef HAVE_X11
6520       Vwindow_system_version = make_number (11);
6521 #endif
6522 #if defined (GNU_LINUX) && defined (HAVE_LIBNCURSES)
6523       /* In some versions of ncurses,
6524          tputs crashes if we have not called tgetent.
6525          So call tgetent.  */
6526       { char b[2044]; tgetent (b, "xterm");}
6527 #endif
6528       adjust_frame_glyphs_initially ();
6529       return;
6530     }
6531 #endif /* HAVE_X_WINDOWS */
6532 
6533 #ifdef HAVE_NTGUI
6534   if (!inhibit_window_system)
6535     {
6536       Vinitial_window_system = Qw32;
6537       Vwindow_system_version = make_number (1);
6538       adjust_frame_glyphs_initially ();
6539       return;
6540     }
6541 #endif /* HAVE_NTGUI */
6542 
6543 #ifdef HAVE_NS
6544   if (!inhibit_window_system
6545 #ifndef CANNOT_DUMP
6546      && initialized
6547 #endif
6548       )
6549     {
6550       Vinitial_window_system = Qns;
6551       Vwindow_system_version = make_number(10);
6552       adjust_frame_glyphs_initially ();
6553       return;
6554     }
6555 #endif
6556 
6557   /* If no window system has been specified, try to use the terminal.  */
6558   if (! isatty (0))
6559     {
6560       fatal ("standard input is not a tty");
6561       exit (1);
6562     }
6563 
6564 #ifdef WINDOWSNT
6565   terminal_type = "w32console";
6566 #else
6567   /* Look at the TERM variable.  */
6568   terminal_type = (char *) getenv ("TERM");
6569 #endif
6570   if (!terminal_type)
6571     {
6572 #ifdef HAVE_WINDOW_SYSTEM
6573       if (! inhibit_window_system)
6574         fprintf (stderr, "Please set the environment variable DISPLAY or TERM (see `tset').\n");
6575       else
6576 #endif /* HAVE_WINDOW_SYSTEM */
6577         fprintf (stderr, "Please set the environment variable TERM; see `tset'.\n");
6578       exit (1);
6579     }
6580 
6581   {
6582     struct terminal *t;
6583     struct frame *f = XFRAME (selected_frame);
6584 
6585     /* Open a display on the controlling tty. */
6586     t = init_tty (0, terminal_type, 1); /* Errors are fatal. */
6587 
6588     /* Convert the initial frame to use the new display. */
6589     if (f->output_method != output_initial)
6590       abort ();
6591     f->output_method = t->type;
6592     f->terminal = t;
6593 
6594     t->reference_count++;
6595     t->display_info.tty->top_frame = selected_frame;
6596     change_frame_size (XFRAME (selected_frame),
6597                        FrameRows (t->display_info.tty),
6598                        FrameCols (t->display_info.tty), 0, 0, 1);
6599 
6600     /* Delete the initial terminal. */
6601     if (--initial_terminal->reference_count == 0
6602         && initial_terminal->delete_terminal_hook)
6603       (*initial_terminal->delete_terminal_hook) (initial_terminal);
6604 
6605     /* Update frame parameters to reflect the new type. */
6606     Fmodify_frame_parameters
6607       (selected_frame, Fcons (Fcons (Qtty_type,
6608                                      Ftty_type (selected_frame)), Qnil));
6609     if (t->display_info.tty->name)
6610       Fmodify_frame_parameters (selected_frame,
6611                                 Fcons (Fcons (Qtty, build_string (t->display_info.tty->name)),
6612                                        Qnil));
6613     else
6614       Fmodify_frame_parameters (selected_frame, Fcons (Fcons (Qtty, Qnil),
6615                                                        Qnil));
6616   }
6617 
6618   {
6619     struct frame *sf = SELECTED_FRAME ();
6620     int width = FRAME_TOTAL_COLS (sf);
6621     int height = FRAME_LINES (sf);
6622 
6623     unsigned int total_glyphs = height * (width + 2) * sizeof (struct glyph);
6624 
6625     /* If these sizes are so big they cause overflow, just ignore the
6626        change.  It's not clear what better we could do.  */
6627     if (total_glyphs / sizeof (struct glyph) / height != width + 2)
6628       fatal ("screen size %dx%d too big", width, height);
6629   }
6630 
6631   adjust_frame_glyphs_initially ();
6632   calculate_costs (XFRAME (selected_frame));
6633 
6634   /* Set up faces of the initial terminal frame of a dumped Emacs.  */
6635   if (initialized
6636       && !noninteractive
6637       && NILP (Vinitial_window_system))
6638     {
6639       /* For the initial frame, we don't have any way of knowing what
6640          are the foreground and background colors of the terminal.  */
6641       struct frame *sf = SELECTED_FRAME();
6642 
6643       FRAME_FOREGROUND_PIXEL (sf) = FACE_TTY_DEFAULT_FG_COLOR;
6644       FRAME_BACKGROUND_PIXEL (sf) = FACE_TTY_DEFAULT_BG_COLOR;
6645       call0 (intern ("tty-set-up-initial-frame-faces"));
6646     }
6647 }
6648 
6649 
6650 
6651 /***********************************************************************
6652                            Blinking cursor
6653  ***********************************************************************/
6654 
6655 DEFUN ("internal-show-cursor", Finternal_show_cursor,
6656        Sinternal_show_cursor, 2, 2, 0,
6657        doc: /* Set the cursor-visibility flag of WINDOW to SHOW.
6658 WINDOW nil means use the selected window.  SHOW non-nil means
6659 show a cursor in WINDOW in the next redisplay.  SHOW nil means
6660 don't show a cursor.  */)
6661      (window, show)
6662      Lisp_Object window, show;
6663 {
6664   /* Don't change cursor state while redisplaying.  This could confuse
6665      output routines.  */
6666   if (!redisplaying_p)
6667     {
6668       if (NILP (window))
6669         window = selected_window;
6670       else
6671         CHECK_WINDOW (window);
6672 
6673       XWINDOW (window)->cursor_off_p = NILP (show);
6674     }
6675 
6676   return Qnil;
6677 }
6678 
6679 
6680 DEFUN ("internal-show-cursor-p", Finternal_show_cursor_p,
6681        Sinternal_show_cursor_p, 0, 1, 0,
6682        doc: /* Value is non-nil if next redisplay will display a cursor in WINDOW.
6683 WINDOW nil or omitted means report on the selected window.  */)
6684      (window)
6685      Lisp_Object window;
6686 {
6687   struct window *w;
6688 
6689   if (NILP (window))
6690     window = selected_window;
6691   else
6692     CHECK_WINDOW (window);
6693 
6694   w = XWINDOW (window);
6695   return w->cursor_off_p ? Qnil : Qt;
6696 }
6697 
6698 DEFUN ("last-nonminibuffer-frame", Flast_nonminibuf_frame,
6699        Slast_nonminibuf_frame, 0, 0, 0,
6700        doc: /* Value is last nonminibuffer frame. */)
6701      ()
6702 {
6703   Lisp_Object frame = Qnil;
6704 
6705   if (last_nonminibuf_frame)
6706     XSETFRAME (frame, last_nonminibuf_frame);
6707 
6708   return frame;
6709 }
6710 
6711 /***********************************************************************
6712                             Initialization
6713  ***********************************************************************/
6714 
6715 void
6716 syms_of_display ()
6717 {
6718   defsubr (&Sredraw_frame);
6719   defsubr (&Sredraw_display);
6720   defsubr (&Sframe_or_buffer_changed_p);
6721   defsubr (&Sopen_termscript);
6722   defsubr (&Sding);
6723   defsubr (&Sredisplay);
6724   defsubr (&Ssleep_for);
6725   defsubr (&Ssend_string_to_terminal);
6726   defsubr (&Sinternal_show_cursor);
6727   defsubr (&Sinternal_show_cursor_p);
6728   defsubr (&Slast_nonminibuf_frame);
6729 
6730 #if GLYPH_DEBUG
6731   defsubr (&Sdump_redisplay_history);
6732 #endif
6733 
6734   frame_and_buffer_state = Fmake_vector (make_number (20), Qlambda);
6735   staticpro (&frame_and_buffer_state);
6736 
6737   Qdisplay_table = intern_c_string ("display-table");
6738   staticpro (&Qdisplay_table);
6739   Qredisplay_dont_pause = intern_c_string ("redisplay-dont-pause");
6740   staticpro (&Qredisplay_dont_pause);
6741 
6742   DEFVAR_INT ("baud-rate", &baud_rate,
6743               doc: /* *The output baud rate of the terminal.
6744 On most systems, changing this value will affect the amount of padding
6745 and the other strategic decisions made during redisplay.  */);
6746 
6747   DEFVAR_BOOL ("inverse-video", &inverse_video,
6748                doc: /* *Non-nil means invert the entire frame display.
6749 This means everything is in inverse video which otherwise would not be.  */);
6750 
6751   DEFVAR_BOOL ("visible-bell", &visible_bell,
6752                doc: /* *Non-nil means try to flash the frame to represent a bell.
6753 
6754 See also `ring-bell-function'.  */);
6755 
6756   DEFVAR_BOOL ("no-redraw-on-reenter", &no_redraw_on_reenter,
6757                doc: /* *Non-nil means no need to redraw entire frame after suspending.
6758 A non-nil value is useful if the terminal can automatically preserve
6759 Emacs's frame display when you reenter Emacs.
6760 It is up to you to set this variable if your terminal can do that.  */);
6761 
6762   DEFVAR_LISP ("initial-window-system", &Vinitial_window_system,
6763                doc: /* Name of the window system that Emacs uses for the first frame.
6764 The value is a symbol--for instance, `x' for X windows.
6765 The value is nil if Emacs is using a text-only terminal.  */);
6766 
6767   DEFVAR_KBOARD ("window-system", Vwindow_system,
6768                  doc: /* Name of window system through which the selected frame is displayed.
6769 The value is a symbol--for instance, `x' for X windows.
6770 The value is nil if the selected frame is on a text-only-terminal.  */);
6771 
6772   DEFVAR_LISP ("window-system-version", &Vwindow_system_version,
6773                doc: /* The version number of the window system in use.
6774 For X windows, this is 11.  */);
6775 
6776   DEFVAR_BOOL ("cursor-in-echo-area", &cursor_in_echo_area,
6777                doc: /* Non-nil means put cursor in minibuffer, at end of any message there.  */);
6778 
6779   DEFVAR_LISP ("glyph-table", &Vglyph_table,
6780                doc: /* Table defining how to output a glyph code to the frame.
6781 If not nil, this is a vector indexed by glyph code to define the glyph.
6782 Each element can be:
6783  integer: a glyph code which this glyph is an alias for.
6784  string: output this glyph using that string (not impl. in X windows).
6785  nil: this glyph mod 524288 is the code of a character to output,
6786     and this glyph / 524288 is the face number (see `face-id') to use
6787     while outputting it.  */);
6788   Vglyph_table = Qnil;
6789 
6790   DEFVAR_LISP ("standard-display-table", &Vstandard_display_table,
6791                doc: /* Display table to use for buffers that specify none.
6792 See `buffer-display-table' for more information.  */);
6793   Vstandard_display_table = Qnil;
6794 
6795   DEFVAR_BOOL ("redisplay-dont-pause", &redisplay_dont_pause,
6796                doc: /* *Non-nil means update isn't paused when input is detected.  */);
6797   redisplay_dont_pause = 0;
6798 
6799 #if PERIODIC_PREEMPTION_CHECKING
6800   DEFVAR_LISP ("redisplay-preemption-period", &Vredisplay_preemption_period,
6801                doc: /* *The period in seconds between checking for input during redisplay.
6802 If input is detected, redisplay is pre-empted, and the input is processed.
6803 If nil, never pre-empt redisplay.  */);
6804   Vredisplay_preemption_period = make_float (0.10);
6805 #endif
6806 
6807 #ifdef CANNOT_DUMP
6808   if (noninteractive)
6809 #endif
6810     {
6811       Vinitial_window_system = Qnil;
6812       Vwindow_system_version = Qnil;
6813     }
6814 }
6815 
6816 /* arch-tag: 8d812b1f-04a2-4195-a9c4-381f8457a413
6817    (do not change this comment) */