xdisp.c

/* Display generation from window structure and buffer text.

Copyright (C) 1985-1988, 1993-1995, 1997-2012  Free Software Foundation, Inc.

This file is part of GNU Emacs.

GNU Emacs is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

GNU Emacs is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */

/* New redisplay written by Gerd Moellmann <gerd@gnu.org>.

   Redisplay.

   Emacs separates the task of updating the display from code
   modifying global state, e.g. buffer text.  This way functions
   operating on buffers don't also have to be concerned with updating
   the display.

   Updating the display is triggered by the Lisp interpreter when it
   decides it's time to do it.  This is done either automatically for
   you as part of the interpreter's command loop or as the result of
   calling Lisp functions like `sit-for'.  The C function `redisplay'
   in xdisp.c is the only entry into the inner redisplay code.

   The following diagram shows how redisplay code is invoked.  As you
   can see, Lisp calls redisplay and vice versa.  Under window systems
   like X, some portions of the redisplay code are also called
   asynchronously during mouse movement or expose events.  It is very
   important that these code parts do NOT use the C library (malloc,
   free) because many C libraries under Unix are not reentrant.  They
   may also NOT call functions of the Lisp interpreter which could
   change the interpreter's state.  If you don't follow these rules,
   you will encounter bugs which are very hard to explain.

   +--------------+   redisplay     +----------------+
   | Lisp machine |---------------->| Redisplay code |<--+
   +--------------+   (xdisp.c)     +----------------+   |
	  ^				     |		 |
	  +----------------------------------+           |
	    Don't use this path when called		 |
	    asynchronously!				 |
                                                         |
                           expose_window (asynchronous)  |
                                                         |
			           X expose events  -----+

   What does redisplay do?  Obviously, it has to figure out somehow what
   has been changed since the last time the display has been updated,
   and to make these changes visible.  Preferably it would do that in
   a moderately intelligent way, i.e. fast.

   Changes in buffer text can be deduced from window and buffer
   structures, and from some global variables like `beg_unchanged' and
   `end_unchanged'.  The contents of the display are additionally
   recorded in a `glyph matrix', a two-dimensional matrix of glyph
   structures.  Each row in such a matrix corresponds to a line on the
   display, and each glyph in a row corresponds to a column displaying
   a character, an image, or what else.  This matrix is called the
   `current glyph matrix' or `current matrix' in redisplay
   terminology.

   For buffer parts that have been changed since the last update, a
   second glyph matrix is constructed, the so called `desired glyph
   matrix' or short `desired matrix'.  Current and desired matrix are
   then compared to find a cheap way to update the display, e.g. by
   reusing part of the display by scrolling lines.

   You will find a lot of redisplay optimizations when you start
   looking at the innards of redisplay.  The overall goal of all these
   optimizations is to make redisplay fast because it is done
   frequently.  Some of these optimizations are implemented by the
   following functions:

    . try_cursor_movement

      This function tries to update the display if the text in the
      window did not change and did not scroll, only point moved, and
      it did not move off the displayed portion of the text.

    . try_window_reusing_current_matrix

      This function reuses the current matrix of a window when text
      has not changed, but the window start changed (e.g., due to
      scrolling).

    . try_window_id

      This function attempts to redisplay a window by reusing parts of
      its existing display.  It finds and reuses the part that was not
      changed, and redraws the rest.

    . try_window

      This function performs the full redisplay of a single window
      assuming that its fonts were not changed and that the cursor
      will not end up in the scroll margins.  (Loading fonts requires
      re-adjustment of dimensions of glyph matrices, which makes this
      method impossible to use.)

   These optimizations are tried in sequence (some can be skipped if
   it is known that they are not applicable).  If none of the
   optimizations were successful, redisplay calls redisplay_windows,
   which performs a full redisplay of all windows.

   Desired matrices.

   Desired matrices are always built per Emacs window.  The function
   `display_line' is the central function to look at if you are
   interested.  It constructs one row in a desired matrix given an
   iterator structure containing both a buffer position and a
   description of the environment in which the text is to be
   displayed.  But this is too early, read on.

   Characters and pixmaps displayed for a range of buffer text depend
   on various settings of buffers and windows, on overlays and text
   properties, on display tables, on selective display.  The good news
   is that all this hairy stuff is hidden behind a small set of
   interface functions taking an iterator structure (struct it)
   argument.

   Iteration over things to be displayed is then simple.  It is
   started by initializing an iterator with a call to init_iterator,
   passing it the buffer position where to start iteration.  For
   iteration over strings, pass -1 as the position to init_iterator,
   and call reseat_to_string when the string is ready, to initialize
   the iterator for that string.  Thereafter, calls to
   get_next_display_element fill the iterator structure with relevant
   information about the next thing to display.  Calls to
   set_iterator_to_next move the iterator to the next thing.

   Besides this, an iterator also contains information about the
   display environment in which glyphs for display elements are to be
   produced.  It has fields for the width and height of the display,
   the information whether long lines are truncated or continued, a
   current X and Y position, and lots of other stuff you can better
   see in dispextern.h.

   Glyphs in a desired matrix are normally constructed in a loop
   calling get_next_display_element and then PRODUCE_GLYPHS.  The call
   to PRODUCE_GLYPHS will fill the iterator structure with pixel
   information about the element being displayed and at the same time
   produce glyphs for it.  If the display element fits on the line
   being displayed, set_iterator_to_next is called next, otherwise the
   glyphs produced are discarded.  The function display_line is the
   workhorse of filling glyph rows in the desired matrix with glyphs.
   In addition to producing glyphs, it also handles line truncation
   and continuation, word wrap, and cursor positioning (for the
   latter, see also set_cursor_from_row).

   Frame matrices.

   That just couldn't be all, could it?  What about terminal types not
   supporting operations on sub-windows of the screen?  To update the
   display on such a terminal, window-based glyph matrices are not
   well suited.  To be able to reuse part of the display (scrolling
   lines up and down), we must instead have a view of the whole
   screen.  This is what `frame matrices' are for.  They are a trick.

   Frames on terminals like above have a glyph pool.  Windows on such
   a frame sub-allocate their glyph memory from their frame's glyph
   pool.  The frame itself is given its own glyph matrices.  By
   coincidence---or maybe something else---rows in window glyph
   matrices are slices of corresponding rows in frame matrices.  Thus
   writing to window matrices implicitly updates a frame matrix which
   provides us with the view of the whole screen that we originally
   wanted to have without having to move many bytes around.  To be
   honest, there is a little bit more done, but not much more.  If you
   plan to extend that code, take a look at dispnew.c.  The function
   build_frame_matrix is a good starting point.

   Bidirectional display.

   Bidirectional display adds quite some hair to this already complex
   design.  The good news are that a large portion of that hairy stuff
   is hidden in bidi.c behind only 3 interfaces.  bidi.c implements a
   reordering engine which is called by set_iterator_to_next and
   returns the next character to display in the visual order.  See
   commentary on bidi.c for more details.  As far as redisplay is
   concerned, the effect of calling bidi_move_to_visually_next, the
   main interface of the reordering engine, is that the iterator gets
   magically placed on the buffer or string position that is to be
   displayed next.  In other words, a linear iteration through the
   buffer/string is replaced with a non-linear one.  All the rest of
   the redisplay is oblivious to the bidi reordering.

   Well, almost oblivious---there are still complications, most of
   them due to the fact that buffer and string positions no longer
   change monotonously with glyph indices in a glyph row.  Moreover,
   for continued lines, the buffer positions may not even be
   monotonously changing with vertical positions.  Also, accounting
   for face changes, overlays, etc. becomes more complex because
   non-linear iteration could potentially skip many positions with
   changes, and then cross them again on the way back...

   One other prominent effect of bidirectional display is that some
   paragraphs of text need to be displayed starting at the right
   margin of the window---the so-called right-to-left, or R2L
   paragraphs.  R2L paragraphs are displayed with R2L glyph rows,
   which have their reversed_p flag set.  The bidi reordering engine
   produces characters in such rows starting from the character which
   should be the rightmost on display.  PRODUCE_GLYPHS then reverses
   the order, when it fills up the glyph row whose reversed_p flag is
   set, by prepending each new glyph to what is already there, instead
   of appending it.  When the glyph row is complete, the function
   extend_face_to_end_of_line fills the empty space to the left of the
   leftmost character with special glyphs, which will display as,
   well, empty.  On text terminals, these special glyphs are simply
   blank characters.  On graphics terminals, there's a single stretch
   glyph of a suitably computed width.  Both the blanks and the
   stretch glyph are given the face of the background of the line.
   This way, the terminal-specific back-end can still draw the glyphs
   left to right, even for R2L lines.

   Bidirectional display and character compositions

   Some scripts cannot be displayed by drawing each character
   individually, because adjacent characters change each other's shape
   on display.  For example, Arabic and Indic scripts belong to this
   category.

   Emacs display supports this by providing "character compositions",
   most of which is implemented in composite.c.  During the buffer
   scan that delivers characters to PRODUCE_GLYPHS, if the next
   character to be delivered is a composed character, the iteration
   calls composition_reseat_it and next_element_from_composition.  If
   they succeed to compose the character with one or more of the
   following characters, the whole sequence of characters that where
   composed is recorded in the `struct composition_it' object that is
   part of the buffer iterator.  The composed sequence could produce
   one or more font glyphs (called "grapheme clusters") on the screen.
   Each of these grapheme clusters is then delivered to PRODUCE_GLYPHS
   in the direction corresponding to the current bidi scan direction
   (recorded in the scan_dir member of the `struct bidi_it' object
   that is part of the buffer iterator).  In particular, if the bidi
   iterator currently scans the buffer backwards, the grapheme
   clusters are delivered back to front.  This reorders the grapheme
   clusters as appropriate for the current bidi context.  Note that
   this means that the grapheme clusters are always stored in the
   LGSTRING object (see composite.c) in the logical order.

   Moving an iterator in bidirectional text
   without producing glyphs

   Note one important detail mentioned above: that the bidi reordering
   engine, driven by the iterator, produces characters in R2L rows
   starting at the character that will be the rightmost on display.
   As far as the iterator is concerned, the geometry of such rows is
   still left to right, i.e. the iterator "thinks" the first character
   is at the leftmost pixel position.  The iterator does not know that
   PRODUCE_GLYPHS reverses the order of the glyphs that the iterator
   delivers.  This is important when functions from the move_it_*
   family are used to get to certain screen position or to match
   screen coordinates with buffer coordinates: these functions use the
   iterator geometry, which is left to right even in R2L paragraphs.
   This works well with most callers of move_it_*, because they need
   to get to a specific column, and columns are still numbered in the
   reading order, i.e. the rightmost character in a R2L paragraph is
   still column zero.  But some callers do not get well with this; a
   notable example is mouse clicks that need to find the character
   that corresponds to certain pixel coordinates.  See
   buffer_posn_from_coords in dispnew.c for how this is handled.  */

#include <config.h>
#include <stdio.h>
#include <limits.h>
#include <setjmp.h>

#include "lisp.h"
#include "keyboard.h"
#include "frame.h"
#include "window.h"
#include "termchar.h"
#include "dispextern.h"
#include "buffer.h"
#include "character.h"
#include "charset.h"
#include "indent.h"
#include "commands.h"
#include "keymap.h"
#include "macros.h"
#include "disptab.h"
#include "termhooks.h"
#include "termopts.h"
#include "intervals.h"
#include "coding.h"
#include "process.h"
#include "region-cache.h"
#include "font.h"
#include "fontset.h"
#include "blockinput.h"

#ifdef HAVE_X_WINDOWS
#include "xterm.h"
#endif
#ifdef WINDOWSNT
#include "w32term.h"
#endif
#ifdef HAVE_NS
#include "nsterm.h"
#endif
#ifdef USE_GTK
#include "gtkutil.h"
#endif

#include "font.h"

#ifndef FRAME_X_OUTPUT
#define FRAME_X_OUTPUT(f) ((f)->output_data.x)
#endif

#define INFINITY 10000000

Lisp_Object Qoverriding_local_map, Qoverriding_terminal_local_map;
Lisp_Object Qwindow_scroll_functions;
static Lisp_Object Qwindow_text_change_functions;
static Lisp_Object Qredisplay_end_trigger_functions;
Lisp_Object Qinhibit_point_motion_hooks;
static Lisp_Object QCeval, QCpropertize;
Lisp_Object QCfile, QCdata;
static Lisp_Object Qfontified;
static Lisp_Object Qgrow_only;
static Lisp_Object Qinhibit_eval_during_redisplay;
static Lisp_Object Qbuffer_position, Qposition, Qobject;
static Lisp_Object Qright_to_left, Qleft_to_right;

/* Cursor shapes */
Lisp_Object Qbar, Qhbar, Qbox, Qhollow;

/* Pointer shapes */
static Lisp_Object Qarrow, Qhand;
Lisp_Object Qtext;

/* Holds the list (error).  */
static Lisp_Object list_of_error;

static Lisp_Object Qfontification_functions;

static Lisp_Object Qwrap_prefix;
static Lisp_Object Qline_prefix;

/* Non-nil means don't actually do any redisplay.  */

Lisp_Object Qinhibit_redisplay;

/* Names of text properties relevant for redisplay.  */

Lisp_Object Qdisplay;

Lisp_Object Qspace, QCalign_to;
static Lisp_Object QCrelative_width, QCrelative_height;
Lisp_Object Qleft_margin, Qright_margin;
static Lisp_Object Qspace_width, Qraise;
static Lisp_Object Qslice;
Lisp_Object Qcenter;
static Lisp_Object Qmargin, Qpointer;
static Lisp_Object Qline_height;

#ifdef HAVE_WINDOW_SYSTEM

/* Test if overflow newline into fringe.  Called with iterator IT
   at or past right window margin, and with IT->current_x set.  */

#define IT_OVERFLOW_NEWLINE_INTO_FRINGE(IT)		\
  (!NILP (Voverflow_newline_into_fringe)		\
   && FRAME_WINDOW_P ((IT)->f)				\
   && ((IT)->bidi_it.paragraph_dir == R2L		\
       ? (WINDOW_LEFT_FRINGE_WIDTH ((IT)->w) > 0)	\
       : (WINDOW_RIGHT_FRINGE_WIDTH ((IT)->w) > 0))	\
   && (IT)->current_x == (IT)->last_visible_x		\
   && (IT)->line_wrap != WORD_WRAP)

#else /* !HAVE_WINDOW_SYSTEM */
#define IT_OVERFLOW_NEWLINE_INTO_FRINGE(it) 0
#endif /* HAVE_WINDOW_SYSTEM */

/* Test if the display element loaded in IT is a space or tab
   character.  This is used to determine word wrapping.  */

#define IT_DISPLAYING_WHITESPACE(it)				\
  (it->what == IT_CHARACTER && (it->c == ' ' || it->c == '\t'))

/* Name of the face used to highlight trailing whitespace.  */

static Lisp_Object Qtrailing_whitespace;

/* Name and number of the face used to highlight escape glyphs.  */

static Lisp_Object Qescape_glyph;

/* Name and number of the face used to highlight non-breaking spaces.  */

static Lisp_Object Qnobreak_space;

/* The symbol `image' which is the car of the lists used to represent
   images in Lisp.  Also a tool bar style.  */

Lisp_Object Qimage;

/* The image map types.  */
Lisp_Object QCmap;
static Lisp_Object QCpointer;
static Lisp_Object Qrect, Qcircle, Qpoly;

/* Tool bar styles */
Lisp_Object Qboth, Qboth_horiz, Qtext_image_horiz;

/* Non-zero means print newline to stdout before next mini-buffer
   message.  */

int noninteractive_need_newline;

/* Non-zero means print newline to message log before next message.  */

static int message_log_need_newline;

/* Three markers that message_dolog uses.
   It could allocate them itself, but that causes trouble
   in handling memory-full errors.  */
static Lisp_Object message_dolog_marker1;
static Lisp_Object message_dolog_marker2;
static Lisp_Object message_dolog_marker3;

/* The buffer position of the first character appearing entirely or
   partially on the line of the selected window which contains the
   cursor; <= 0 if not known.  Set by set_cursor_from_row, used for
   redisplay optimization in redisplay_internal.  */

static struct text_pos this_line_start_pos;

/* Number of characters past the end of the line above, including the
   terminating newline.  */

static struct text_pos this_line_end_pos;

/* The vertical positions and the height of this line.  */

static int this_line_vpos;
static int this_line_y;
static int this_line_pixel_height;

/* X position at which this display line starts.  Usually zero;
   negative if first character is partially visible.  */

static int this_line_start_x;

/* The smallest character position seen by move_it_* functions as they
   move across display lines.  Used to set MATRIX_ROW_START_CHARPOS of
   hscrolled lines, see display_line.  */

static struct text_pos this_line_min_pos;

/* Buffer that this_line_.* variables are referring to.  */

static struct buffer *this_line_buffer;


/* Values of those variables at last redisplay are stored as
   properties on `overlay-arrow-position' symbol.  However, if
   Voverlay_arrow_position is a marker, last-arrow-position is its
   numerical position.  */

static Lisp_Object Qlast_arrow_position, Qlast_arrow_string;

/* Alternative overlay-arrow-string and overlay-arrow-bitmap
   properties on a symbol in overlay-arrow-variable-list.  */

static Lisp_Object Qoverlay_arrow_string, Qoverlay_arrow_bitmap;

Lisp_Object Qmenu_bar_update_hook;

/* Nonzero if an overlay arrow has been displayed in this window.  */

static int overlay_arrow_seen;

/* Number of windows showing the buffer of the selected window (or
   another buffer with the same base buffer).  keyboard.c refers to
   this.  */

int buffer_shared;

/* Vector containing glyphs for an ellipsis `...'.  */

static Lisp_Object default_invis_vector[3];

/* This is the window where the echo area message was displayed.  It
   is always a mini-buffer window, but it may not be the same window
   currently active as a mini-buffer.  */

Lisp_Object echo_area_window;

/* List of pairs (MESSAGE . MULTIBYTE).  The function save_message
   pushes the current message and the value of
   message_enable_multibyte on the stack, the function restore_message
   pops the stack and displays MESSAGE again.  */

static Lisp_Object Vmessage_stack;

/* Nonzero means multibyte characters were enabled when the echo area
   message was specified.  */

static int message_enable_multibyte;

/* Nonzero if we should redraw the mode lines on the next redisplay.  */

int update_mode_lines;

/* Nonzero if window sizes or contents have changed since last
   redisplay that finished.  */

int windows_or_buffers_changed;

/* Nonzero means a frame's cursor type has been changed.  */

int cursor_type_changed;

/* Nonzero after display_mode_line if %l was used and it displayed a
   line number.  */

static int line_number_displayed;

/* The name of the *Messages* buffer, a string.  */

static Lisp_Object Vmessages_buffer_name;

/* Current, index 0, and last displayed echo area message.  Either
   buffers from echo_buffers, or nil to indicate no message.  */

Lisp_Object echo_area_buffer[2];

/* The buffers referenced from echo_area_buffer.  */

static Lisp_Object echo_buffer[2];

/* A vector saved used in with_area_buffer to reduce consing.  */

static Lisp_Object Vwith_echo_area_save_vector;

/* Non-zero means display_echo_area should display the last echo area
   message again.  Set by redisplay_preserve_echo_area.  */

static int display_last_displayed_message_p;

/* Nonzero if echo area is being used by print; zero if being used by
   message.  */

static int message_buf_print;

/* The symbol `inhibit-menubar-update' and its DEFVAR_BOOL variable.  */

static Lisp_Object Qinhibit_menubar_update;
static Lisp_Object Qmessage_truncate_lines;

/* Set to 1 in clear_message to make redisplay_internal aware
   of an emptied echo area.  */

static int message_cleared_p;

/* A scratch glyph row with contents used for generating truncation
   glyphs.  Also used in direct_output_for_insert.  */

#define MAX_SCRATCH_GLYPHS 100
static struct glyph_row scratch_glyph_row;
static struct glyph scratch_glyphs[MAX_SCRATCH_GLYPHS];

/* Ascent and height of the last line processed by move_it_to.  */

static int last_max_ascent, last_height;

/* Non-zero if there's a help-echo in the echo area.  */

int help_echo_showing_p;

/* If >= 0, computed, exact values of mode-line and header-line height
   to use in the macros CURRENT_MODE_LINE_HEIGHT and
   CURRENT_HEADER_LINE_HEIGHT.  */

int current_mode_line_height, current_header_line_height;

/* The maximum distance to look ahead for text properties.  Values
   that are too small let us call compute_char_face and similar
   functions too often which is expensive.  Values that are too large
   let us call compute_char_face and alike too often because we
   might not be interested in text properties that far away.  */

#define TEXT_PROP_DISTANCE_LIMIT 100

/* SAVE_IT and RESTORE_IT are called when we save a snapshot of the
   iterator state and later restore it.  This is needed because the
   bidi iterator on bidi.c keeps a stacked cache of its states, which
   is really a singleton.  When we use scratch iterator objects to
   move around the buffer, we can cause the bidi cache to be pushed or
   popped, and therefore we need to restore the cache state when we
   return to the original iterator.  */
#define SAVE_IT(ITCOPY,ITORIG,CACHE)		\
  do {						\
    if (CACHE)					\
      bidi_unshelve_cache (CACHE, 1);		\
    ITCOPY = ITORIG;				\
    CACHE = bidi_shelve_cache ();		\
  } while (0)

#define RESTORE_IT(pITORIG,pITCOPY,CACHE)	\
  do {						\
    if (pITORIG != pITCOPY)			\
      *(pITORIG) = *(pITCOPY);			\
    bidi_unshelve_cache (CACHE, 0);		\
    CACHE = NULL;				\
  } while (0)

#if GLYPH_DEBUG

/* Non-zero means print traces of redisplay if compiled with
   GLYPH_DEBUG != 0.  */

int trace_redisplay_p;

#endif /* GLYPH_DEBUG */

#ifdef DEBUG_TRACE_MOVE
/* Non-zero means trace with TRACE_MOVE to stderr.  */
int trace_move;

#define TRACE_MOVE(x)	if (trace_move) fprintf x; else (void) 0
#else
#define TRACE_MOVE(x)	(void) 0
#endif

static Lisp_Object Qauto_hscroll_mode;

/* Buffer being redisplayed -- for redisplay_window_error.  */

static struct buffer *displayed_buffer;

/* Value returned from text property handlers (see below).  */

enum prop_handled
{
  HANDLED_NORMALLY,
  HANDLED_RECOMPUTE_PROPS,
  HANDLED_OVERLAY_STRING_CONSUMED,
  HANDLED_RETURN
};

/* A description of text properties that redisplay is interested
   in.  */

struct props
{
  /* The name of the property.  */
  Lisp_Object *name;

  /* A unique index for the property.  */
  enum prop_idx idx;

  /* A handler function called to set up iterator IT from the property
     at IT's current position.  Value is used to steer handle_stop.  */
  enum prop_handled (*handler) (struct it *it);
};

static enum prop_handled handle_face_prop (struct it *);
static enum prop_handled handle_invisible_prop (struct it *);
static enum prop_handled handle_display_prop (struct it *);
static enum prop_handled handle_composition_prop (struct it *);
static enum prop_handled handle_overlay_change (struct it *);
static enum prop_handled handle_fontified_prop (struct it *);

/* Properties handled by iterators.  */

static struct props it_props[] =
{
  {&Qfontified,		FONTIFIED_PROP_IDX,	handle_fontified_prop},
  /* Handle `face' before `display' because some sub-properties of
     `display' need to know the face.  */
  {&Qface,		FACE_PROP_IDX,		handle_face_prop},
  {&Qdisplay,		DISPLAY_PROP_IDX,	handle_display_prop},
  {&Qinvisible,		INVISIBLE_PROP_IDX,	handle_invisible_prop},
  {&Qcomposition,	COMPOSITION_PROP_IDX,	handle_composition_prop},
  {NULL,		0,			NULL}
};

/* Value is the position described by X.  If X is a marker, value is
   the marker_position of X.  Otherwise, value is X.  */

#define COERCE_MARKER(X) (MARKERP ((X)) ? Fmarker_position (X) : (X))

/* Enumeration returned by some move_it_.* functions internally.  */

enum move_it_result
{
  /* Not used.  Undefined value.  */
  MOVE_UNDEFINED,

  /* Move ended at the requested buffer position or ZV.  */
  MOVE_POS_MATCH_OR_ZV,

  /* Move ended at the requested X pixel position.  */
  MOVE_X_REACHED,

  /* Move within a line ended at the end of a line that must be
     continued.  */
  MOVE_LINE_CONTINUED,

  /* Move within a line ended at the end of a line that would
     be displayed truncated.  */
  MOVE_LINE_TRUNCATED,

  /* Move within a line ended at a line end.  */
  MOVE_NEWLINE_OR_CR
};

/* This counter is used to clear the face cache every once in a while
   in redisplay_internal.  It is incremented for each redisplay.
   Every CLEAR_FACE_CACHE_COUNT full redisplays, the face cache is
   cleared.  */

#define CLEAR_FACE_CACHE_COUNT	500
static int clear_face_cache_count;

/* Similarly for the image cache.  */

#ifdef HAVE_WINDOW_SYSTEM
#define CLEAR_IMAGE_CACHE_COUNT	101
static int clear_image_cache_count;

/* Null glyph slice */
static struct glyph_slice null_glyph_slice = { 0, 0, 0, 0 };
#endif

/* Non-zero while redisplay_internal is in progress.  */

int redisplaying_p;

static Lisp_Object Qinhibit_free_realized_faces;

/* If a string, XTread_socket generates an event to display that string.
   (The display is done in read_char.)  */

Lisp_Object help_echo_string;
Lisp_Object help_echo_window;
Lisp_Object help_echo_object;
EMACS_INT help_echo_pos;

/* Temporary variable for XTread_socket.  */

Lisp_Object previous_help_echo_string;

/* Platform-independent portion of hourglass implementation. */

/* Non-zero means an hourglass cursor is currently shown.  */
int hourglass_shown_p;

/* If non-null, an asynchronous timer that, when it expires, displays
   an hourglass cursor on all frames.  */
struct atimer *hourglass_atimer;

/* Name of the face used to display glyphless characters.  */
Lisp_Object Qglyphless_char;

/* Symbol for the purpose of Vglyphless_char_display.  */
static Lisp_Object Qglyphless_char_display;

/* Method symbols for Vglyphless_char_display.  */
static Lisp_Object Qhex_code, Qempty_box, Qthin_space, Qzero_width;

/* Default pixel width of `thin-space' display method.  */
#define THIN_SPACE_WIDTH 1

/* Default number of seconds to wait before displaying an hourglass
   cursor.  */
#define DEFAULT_HOURGLASS_DELAY 1


/* Function prototypes.  */

static void setup_for_ellipsis (struct it *, int);
static void set_iterator_to_next (struct it *, int);
static void mark_window_display_accurate_1 (struct window *, int);
static int single_display_spec_string_p (Lisp_Object, Lisp_Object);
static int display_prop_string_p (Lisp_Object, Lisp_Object);
static int cursor_row_p (struct glyph_row *);
static int redisplay_mode_lines (Lisp_Object, int);
static char *decode_mode_spec_coding (Lisp_Object, char *, int);

static Lisp_Object get_it_property (struct it *it, Lisp_Object prop);

static void handle_line_prefix (struct it *);

static void pint2str (char *, int, EMACS_INT);
static void pint2hrstr (char *, int, EMACS_INT);
static struct text_pos run_window_scroll_functions (Lisp_Object,
                                                    struct text_pos);
static void reconsider_clip_changes (struct window *, struct buffer *);
static int text_outside_line_unchanged_p (struct window *,
					  EMACS_INT, EMACS_INT);
static void store_mode_line_noprop_char (char);
static int store_mode_line_noprop (const char *, int, int);
static void handle_stop (struct it *);
static void handle_stop_backwards (struct it *, EMACS_INT);
static void vmessage (const char *, va_list) ATTRIBUTE_FORMAT_PRINTF (1, 0);
static void ensure_echo_area_buffers (void);
static Lisp_Object unwind_with_echo_area_buffer (Lisp_Object);
static Lisp_Object with_echo_area_buffer_unwind_data (struct window *);
static int with_echo_area_buffer (struct window *, int,
                                  int (*) (EMACS_INT, Lisp_Object, EMACS_INT, EMACS_INT),
                                  EMACS_INT, Lisp_Object, EMACS_INT, EMACS_INT);
static void clear_garbaged_frames (void);
static int current_message_1 (EMACS_INT, Lisp_Object, EMACS_INT, EMACS_INT);
static void pop_message (void);
static int truncate_message_1 (EMACS_INT, Lisp_Object, EMACS_INT, EMACS_INT);
static void set_message (const char *, Lisp_Object, EMACS_INT, int);
static int set_message_1 (EMACS_INT, Lisp_Object, EMACS_INT, EMACS_INT);
static int display_echo_area (struct window *);
static int display_echo_area_1 (EMACS_INT, Lisp_Object, EMACS_INT, EMACS_INT);
static int resize_mini_window_1 (EMACS_INT, Lisp_Object, EMACS_INT, EMACS_INT);
static Lisp_Object unwind_redisplay (Lisp_Object);
static int string_char_and_length (const unsigned char *, int *);
static struct text_pos display_prop_end (struct it *, Lisp_Object,
                                         struct text_pos);
static int compute_window_start_on_continuation_line (struct window *);
static Lisp_Object safe_eval_handler (Lisp_Object);
static void insert_left_trunc_glyphs (struct it *);
static struct glyph_row *get_overlay_arrow_glyph_row (struct window *,
                                                      Lisp_Object);
static void extend_face_to_end_of_line (struct it *);
static int append_space_for_newline (struct it *, int);
static int cursor_row_fully_visible_p (struct window *, int, int);
static int try_scrolling (Lisp_Object, int, EMACS_INT, EMACS_INT, int, int);
static int try_cursor_movement (Lisp_Object, struct text_pos, int *);
static int trailing_whitespace_p (EMACS_INT);
static intmax_t message_log_check_duplicate (EMACS_INT, EMACS_INT);
static void push_it (struct it *, struct text_pos *);
static void pop_it (struct it *);
static void sync_frame_with_window_matrix_rows (struct window *);
static void select_frame_for_redisplay (Lisp_Object);
static void redisplay_internal (void);
static int echo_area_display (int);
static void redisplay_windows (Lisp_Object);
static void redisplay_window (Lisp_Object, int);
static Lisp_Object redisplay_window_error (Lisp_Object);
static Lisp_Object redisplay_window_0 (Lisp_Object);
static Lisp_Object redisplay_window_1 (Lisp_Object);
static int set_cursor_from_row (struct window *, struct glyph_row *,
				struct glyph_matrix *, EMACS_INT, EMACS_INT,
				int, int);
static int update_menu_bar (struct frame *, int, int);
static int try_window_reusing_current_matrix (struct window *);
static int try_window_id (struct window *);
static int display_line (struct it *);
static int display_mode_lines (struct window *);
static int display_mode_line (struct window *, enum face_id, Lisp_Object);
static int display_mode_element (struct it *, int, int, int, Lisp_Object, Lisp_Object, int);
static int store_mode_line_string (const char *, Lisp_Object, int, int, int, Lisp_Object);
static const char *decode_mode_spec (struct window *, int, int, Lisp_Object *);
static void display_menu_bar (struct window *);
static EMACS_INT display_count_lines (EMACS_INT, EMACS_INT, EMACS_INT,
				      EMACS_INT *);
static int display_string (const char *, Lisp_Object, Lisp_Object,
                           EMACS_INT, EMACS_INT, struct it *, int, int, int, int);
static void compute_line_metrics (struct it *);
static void run_redisplay_end_trigger_hook (struct it *);
static int get_overlay_strings (struct it *, EMACS_INT);
static int get_overlay_strings_1 (struct it *, EMACS_INT, int);
static void next_overlay_string (struct it *);
static void reseat (struct it *, struct text_pos, int);
static void reseat_1 (struct it *, struct text_pos, int);
static void back_to_previous_visible_line_start (struct it *);
void reseat_at_previous_visible_line_start (struct it *);
static void reseat_at_next_visible_line_start (struct it *, int);
static int next_element_from_ellipsis (struct it *);
static int next_element_from_display_vector (struct it *);
static int next_element_from_string (struct it *);
static int next_element_from_c_string (struct it *);
static int next_element_from_buffer (struct it *);
static int next_element_from_composition (struct it *);
static int next_element_from_image (struct it *);
static int next_element_from_stretch (struct it *);
static void load_overlay_strings (struct it *, EMACS_INT);
static int init_from_display_pos (struct it *, struct window *,
                                  struct display_pos *);
static void reseat_to_string (struct it *, const char *,
                              Lisp_Object, EMACS_INT, EMACS_INT, int, int);
static int get_next_display_element (struct it *);
static enum move_it_result
       move_it_in_display_line_to (struct it *, EMACS_INT, int,
				   enum move_operation_enum);
void move_it_vertically_backward (struct it *, int);
static void init_to_row_start (struct it *, struct window *,
                               struct glyph_row *);
static int init_to_row_end (struct it *, struct window *,
                            struct glyph_row *);
static void back_to_previous_line_start (struct it *);
static int forward_to_next_line_start (struct it *, int *, struct bidi_it *);
static struct text_pos string_pos_nchars_ahead (struct text_pos,
                                                Lisp_Object, EMACS_INT);
static struct text_pos string_pos (EMACS_INT, Lisp_Object);
static struct text_pos c_string_pos (EMACS_INT, const char *, int);
static EMACS_INT number_of_chars (const char *, int);
static void compute_stop_pos (struct it *);
static void compute_string_pos (struct text_pos *, struct text_pos,
                                Lisp_Object);
static int face_before_or_after_it_pos (struct it *, int);
static EMACS_INT next_overlay_change (EMACS_INT);
static int handle_display_spec (struct it *, Lisp_Object, Lisp_Object,
				Lisp_Object, struct text_pos *, EMACS_INT, int);
static int handle_single_display_spec (struct it *, Lisp_Object,
                                       Lisp_Object, Lisp_Object,
                                       struct text_pos *, EMACS_INT, int, int);
static int underlying_face_id (struct it *);
static int in_ellipses_for_invisible_text_p (struct display_pos *,
                                             struct window *);

#define face_before_it_pos(IT) face_before_or_after_it_pos ((IT), 1)
#define face_after_it_pos(IT)  face_before_or_after_it_pos ((IT), 0)

#ifdef HAVE_WINDOW_SYSTEM

static void x_consider_frame_title (Lisp_Object);
static int tool_bar_lines_needed (struct frame *, int *);
static void update_tool_bar (struct frame *, int);
static void build_desired_tool_bar_string (struct frame *f);
static int redisplay_tool_bar (struct frame *);
static void display_tool_bar_line (struct it *, int);
static void notice_overwritten_cursor (struct window *,
                                       enum glyph_row_area,
                                       int, int, int, int);
static void append_stretch_glyph (struct it *, Lisp_Object,
                                  int, int, int);


#endif /* HAVE_WINDOW_SYSTEM */

static void show_mouse_face (Mouse_HLInfo *, enum draw_glyphs_face);
static int coords_in_mouse_face_p (struct window *, int, int);



/***********************************************************************
		      Window display dimensions
 ***********************************************************************/

/* Return the bottom boundary y-position for text lines in window W.
   This is the first y position at which a line cannot start.
   It is relative to the top of the window.

   This is the height of W minus the height of a mode line, if any.  */

int
window_text_bottom_y (struct window *w)
{
  int height = WINDOW_TOTAL_HEIGHT (w);

  if (WINDOW_WANTS_MODELINE_P (w))
    height -= CURRENT_MODE_LINE_HEIGHT (w);
  return height;
}

/* Return the pixel width of display area AREA of window W.  AREA < 0
   means return the total width of W, not including fringes to
   the left and right of the window.  */

int
window_box_width (struct window *w, int area)
{
  int cols = XFASTINT (w->total_cols);
  int pixels = 0;

  if (!w->pseudo_window_p)
    {
      cols -= WINDOW_SCROLL_BAR_COLS (w);

      if (area == TEXT_AREA)
	{
	  if (INTEGERP (w->left_margin_cols))
	    cols -= XFASTINT (w->left_margin_cols);
	  if (INTEGERP (w->right_margin_cols))
	    cols -= XFASTINT (w->right_margin_cols);
	  pixels = -WINDOW_TOTAL_FRINGE_WIDTH (w);
	}
      else if (area == LEFT_MARGIN_AREA)
	{
	  cols = (INTEGERP (w->left_margin_cols)
		   ? XFASTINT (w->left_margin_cols) : 0);
	  pixels = 0;
	}
      else if (area == RIGHT_MARGIN_AREA)
	{
	  cols = (INTEGERP (w->right_margin_cols)
		   ? XFASTINT (w->right_margin_cols) : 0);
	  pixels = 0;
	}
    }

  return cols * WINDOW_FRAME_COLUMN_WIDTH (w) + pixels;
}


/* Return the pixel height of the display area of window W, not
   including mode lines of W, if any.  */

int
window_box_height (struct window *w)
{
  struct frame *f = XFRAME (w->frame);
  int height = WINDOW_TOTAL_HEIGHT (w);

  xassert (height >= 0);

  /* Note: the code below that determines the mode-line/header-line
     height is essentially the same as that contained in the macro
     CURRENT_{MODE,HEADER}_LINE_HEIGHT, except that it checks whether
     the appropriate glyph row has its `mode_line_p' flag set,
     and if it doesn't, uses estimate_mode_line_height instead.  */

  if (WINDOW_WANTS_MODELINE_P (w))
    {
      struct glyph_row *ml_row
	= (w->current_matrix && w->current_matrix->rows
	   ? MATRIX_MODE_LINE_ROW (w->current_matrix)
	   : 0);
      if (ml_row && ml_row->mode_line_p)
	height -= ml_row->height;
      else
	height -= estimate_mode_line_height (f, CURRENT_MODE_LINE_FACE_ID (w));
    }

  if (WINDOW_WANTS_HEADER_LINE_P (w))
    {
      struct glyph_row *hl_row
	= (w->current_matrix && w->current_matrix->rows
	   ? MATRIX_HEADER_LINE_ROW (w->current_matrix)
	   : 0);
      if (hl_row && hl_row->mode_line_p)
	height -= hl_row->height;
      else
	height -= estimate_mode_line_height (f, HEADER_LINE_FACE_ID);
    }

  /* With a very small font and a mode-line that's taller than
     default, we might end up with a negative height.  */
  return max (0, height);
}

/* Return the window-relative coordinate of the left edge of display
   area AREA of window W.  AREA < 0 means return the left edge of the
   whole window, to the right of the left fringe of W.  */

int