intervals.h 11.7 KB
Newer Older
Joseph Arceneaux's avatar
Joseph Arceneaux committed
1
/* Definitions and global variables for intervals.
Paul Eggert's avatar
Paul Eggert committed
2
   Copyright (C) 1993-1994, 2000-2019 Free Software Foundation, Inc.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
3 4 5

This file is part of GNU Emacs.

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

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
17
along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
18

19 20 21
#ifndef EMACS_INTERVALS_H
#define EMACS_INTERVALS_H

22 23 24
#include "buffer.h"
#include "lisp.h"

25 26
INLINE_HEADER_BEGIN

27 28 29 30 31
/* Basic data type for use of intervals.  */

struct interval
{
  /* The first group of entries deal with the tree structure.  */
32 33
  ptrdiff_t total_length;       /* Length of myself and both children.  */
  ptrdiff_t position;	        /* Cache of interval's character position.  */
34 35 36 37 38 39 40 41 42
                                /* This field is valid in the final
                                   target interval returned by
                                   find_interval, next_interval,
                                   previous_interval and
                                   update_interval.  It cannot be
                                   depended upon in any intermediate
                                   intervals traversed by these
                                   functions, or any other
                                   interval. */
43 44 45 46 47 48 49 50 51
  struct interval *left;	/* Intervals which precede me.  */
  struct interval *right;	/* Intervals which succeed me.  */

  /* Parent in the tree, or the Lisp_Object containing this interval tree.  */
  union
  {
    struct interval *interval;
    Lisp_Object obj;
  } up;
52
  bool_bf up_obj : 1;
53

54
  bool_bf gcmarkbit : 1;
55 56 57 58 59

  /* The remaining components are `properties' of the interval.
     The first four are duplicates for things which can be on the list,
     for purposes of speed.  */

60 61 62
  bool_bf write_protect : 1;	    /* True means can't modify.  */
  bool_bf visible : 1;		    /* False means don't display.  */
  bool_bf front_sticky : 1;	    /* True means text inserted just
63
				       before this interval goes into it.  */
64
  bool_bf rear_sticky : 1;	    /* Likewise for just after it.  */
65
  Lisp_Object plist;		    /* Other properties.  */
66 67
};

68
/* These are macros for dealing with the interval tree.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
69

70
/* True if this interval has no right child.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
71
#define NULL_RIGHT_CHILD(i) ((i)->right == NULL)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
72

73
/* True if this interval has no left child.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
74
#define NULL_LEFT_CHILD(i) ((i)->left == NULL)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
75

76
/* True if this interval has no parent.  */
77
#define NULL_PARENT(i) ((i)->up_obj || (i)->up.interval == 0)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
78

79
/* True if this interval is the left child of some other interval.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
80 81
#define AM_LEFT_CHILD(i)					\
  (! NULL_PARENT (i) && INTERVAL_PARENT (i)->left == (i))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
82

83
/* True if this interval is the right child of some other interval.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
84 85
#define AM_RIGHT_CHILD(i)					\
  (! NULL_PARENT (i) && INTERVAL_PARENT (i)->right == (i))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
86

87
/* True if this interval has no children.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
88
#define LEAF_INTERVAL_P(i) ((i)->left == NULL && (i)->right == NULL)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
89

90
/* True if this interval has no parent and is therefore the root.  */
91
#define ROOT_INTERVAL_P(i) NULL_PARENT (i)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
92

93
/* True if this interval is the only interval in the interval tree.  */
94
#define ONLY_INTERVAL_P(i) (ROOT_INTERVAL_P (i) && LEAF_INTERVAL_P (i))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
95

96
/* True if this interval has both left and right children.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
97
#define BOTH_KIDS_P(i) ((i)->left != NULL && (i)->right != NULL)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
98 99

/* The total size of all text represented by this interval and all its
100
   children in the tree.   This is zero if the interval is null.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
101
#define TOTAL_LENGTH(i) ((i) == NULL ? 0 : (i)->total_length)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
102

103
/* The size of text represented by this interval alone.  */
104 105 106
#define LENGTH(i) ((i)->total_length			\
		   - TOTAL_LENGTH ((i)->right)		\
		   - TOTAL_LENGTH ((i)->left))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
107

108
/* The position of the character just past the end of I.  Note that
109
   the position cache i->position must be valid for this to work.  */
110
#define INTERVAL_LAST_POS(i) ((i)->position + LENGTH (i))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
111

112
/* The total size of the left subtree of this interval.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
113 114
#define LEFT_TOTAL_LENGTH(i) ((i)->left ? (i)->left->total_length : 0)

115
/* The total size of the right subtree of this interval.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
116 117
#define RIGHT_TOTAL_LENGTH(i) ((i)->right ? (i)->right->total_length : 0)

118
/* These macros are for dealing with the interval properties.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
119 120

/* True if this is a default interval, which is the same as being null
121
   or having no properties.  */
122
#define DEFAULT_INTERVAL_P(i) (!i || NILP ((i)->plist))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
123

124
/* Test what type of parent we have.  Three possibilities: another
Dmitry Antipov's avatar
Dmitry Antipov committed
125
   interval, a buffer or string object, or NULL.  */
126
#define INTERVAL_HAS_PARENT(i) (! (i)->up_obj && (i)->up.interval != 0)
127
#define INTERVAL_HAS_OBJECT(i) ((i)->up_obj)
128

129
/* Use these macros to get parent of an interval.
130 131 132 133

   The choice of macros is dependent on the type needed.  Don't add
   casts to get around this, it will break some development work in
   progress.  */
134 135

#define INTERVAL_PARENT(i)					\
136
   (eassert ((i) != 0 && ! (i)->up_obj), (i)->up.interval)
137

138
#define GET_INTERVAL_OBJECT(d,s) (eassert ((s)->up_obj), (d) = (s)->up.obj)
139 140 141 142

/* Use these functions to set Lisp_Object
   or pointer slots of struct interval.  */

143 144 145 146 147 148 149 150
INLINE void
set_interval_object (INTERVAL i, Lisp_Object obj)
{
  eassert (BUFFERP (obj) || STRINGP (obj));
  i->up_obj = 1;
  i->up.obj = obj;
}

Paul Eggert's avatar
Paul Eggert committed
151
INLINE void
152
set_interval_parent (INTERVAL i, INTERVAL parent)
153
{
154
  i->up_obj = false;
155 156 157
  i->up.interval = parent;
}

Paul Eggert's avatar
Paul Eggert committed
158
INLINE void
159
set_interval_plist (INTERVAL i, Lisp_Object plist)
160 161 162
{
  i->plist = plist;
}
163 164 165

/* Get the parent interval, if any, otherwise a null pointer.  Useful
   for walking up to the root in a "for" loop; use this to get the
Dmitry Antipov's avatar
Dmitry Antipov committed
166
   "next" value, and test the result to see if it's NULL.  */
167 168
#define INTERVAL_PARENT_OR_NULL(i) \
   (INTERVAL_HAS_PARENT (i) ? INTERVAL_PARENT (i) : 0)
169

170
/* Reset this interval to its vanilla, or no-property state.  */
171
#define RESET_INTERVAL(i)		      \
172
 do {					      \
173
  (i)->total_length = (i)->position = 0;      \
Dmitry Antipov's avatar
Dmitry Antipov committed
174
  (i)->left = (i)->right = NULL;	      \
175
  set_interval_parent (i, NULL);	      \
176 177 178
  (i)->write_protect = false;		      \
  (i)->visible = false;			      \
  (i)->front_sticky = (i)->rear_sticky = false;	\
179
  set_interval_plist (i, Qnil);		      \
180
 } while (false)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
181

182
/* Copy the cached property values of interval FROM to interval TO.  */
183
#define COPY_INTERVAL_CACHE(from,to)		\
184
 do {						\
185 186 187 188
  (to)->write_protect = (from)->write_protect;	\
  (to)->visible = (from)->visible;		\
  (to)->front_sticky = (from)->front_sticky;	\
  (to)->rear_sticky = (from)->rear_sticky;	\
189
 } while (false)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
190

191
/* Copy only the set bits of FROM's cache.  */
192 193 194 195 196 197 198
#define MERGE_INTERVAL_CACHE(from,to)				\
 do {								\
  if ((from)->write_protect) (to)->write_protect = true;	\
  if ((from)->visible) (to)->visible = true;			\
  if ((from)->front_sticky) (to)->front_sticky = true;		\
  if ((from)->rear_sticky) (to)->rear_sticky = true;		\
 } while (false)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
199

200
/* Is this interval visible?  Replace later with cache access.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
201
#define INTERVAL_VISIBLE_P(i) \
Dmitry Antipov's avatar
Dmitry Antipov committed
202
  (i && NILP (textget ((i)->plist, Qinvisible)))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
203

204
/* Is this interval writable?  Replace later with cache access.  */
205
#define INTERVAL_WRITABLE_P(i)					\
206 207 208 209 210 211
  (NILP (textget ((i)->plist, Qread_only))			\
   || !NILP (textget ((i)->plist, Qinhibit_read_only))		\
   || ((CONSP (Vinhibit_read_only)				\
	? !NILP (Fmemq (textget ((i)->plist, Qread_only),	\
			Vinhibit_read_only))			\
	: !NILP (Vinhibit_read_only))))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
212 213

/* Macros to tell whether insertions before or after this interval
Dmitry Antipov's avatar
Dmitry Antipov committed
214 215 216
   should stick to it.  Now we have Vtext_property_default_nonsticky,
   so these macros are unreliable now and never used.  */

217
#if false
Dmitry Antipov's avatar
Dmitry Antipov committed
218 219 220 221 222 223 224
#define FRONT_STICKY_P(i)				\
  (i && ! NILP (textget ((i)->plist, Qfront_sticky)))
#define END_NONSTICKY_P(i)				\
  (i && ! NILP (textget ((i)->plist, Qrear_nonsticky)))
#define FRONT_NONSTICKY_P(i)				\
  (i && ! EQ (Qt, textget ((i)->plist, Qfront_sticky)))
#endif
Joseph Arceneaux's avatar
Joseph Arceneaux committed
225

226
/* If PROP is the `invisible' property of a character,
227 228
   this is 1 if the character should be treated as invisible,
   and 2 if it is invisible but with an ellipsis.  */
229

Dmitry Antipov's avatar
Dmitry Antipov committed
230
#define TEXT_PROP_MEANS_INVISIBLE(prop)					\
Tom Tromey's avatar
Tom Tromey committed
231
  (EQ (BVAR (current_buffer, invisibility_spec), Qt)			\
Dmitry Antipov's avatar
Dmitry Antipov committed
232
   ? !NILP (prop)							\
233
   : invisible_prop (prop, BVAR (current_buffer, invisibility_spec)))
234

235
/* Declared in alloc.c.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
236

Jan D's avatar
Jan D committed
237
extern INTERVAL make_interval (void);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
238

239
/* Declared in intervals.c.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
240

Jan D's avatar
Jan D committed
241 242
extern INTERVAL create_root_interval (Lisp_Object);
extern void copy_properties (INTERVAL, INTERVAL);
243
extern bool intervals_equal (INTERVAL, INTERVAL);
244
extern void traverse_intervals (INTERVAL, ptrdiff_t,
Jan D's avatar
Jan D committed
245 246 247
                                void (*) (INTERVAL, Lisp_Object),
                                Lisp_Object);
extern void traverse_intervals_noorder (INTERVAL,
248
					void (*) (INTERVAL, void *), void *);
249 250 251
extern INTERVAL split_interval_right (INTERVAL, ptrdiff_t);
extern INTERVAL split_interval_left (INTERVAL, ptrdiff_t);
extern INTERVAL find_interval (INTERVAL, ptrdiff_t);
Jan D's avatar
Jan D committed
252 253 254
extern INTERVAL next_interval (INTERVAL);
extern INTERVAL previous_interval (INTERVAL);
extern INTERVAL merge_interval_left (INTERVAL);
255 256
extern void offset_intervals (struct buffer *, ptrdiff_t, ptrdiff_t);
extern void graft_intervals_into_buffer (INTERVAL, ptrdiff_t, ptrdiff_t,
257
                                         struct buffer *, bool);
258
extern void verify_interval_modification (struct buffer *,
259
					  ptrdiff_t, ptrdiff_t);
Jan D's avatar
Jan D committed
260
extern INTERVAL balance_intervals (INTERVAL);
261
extern void copy_intervals_to_string (Lisp_Object, struct buffer *,
262 263
                                             ptrdiff_t, ptrdiff_t);
extern INTERVAL copy_intervals (INTERVAL, ptrdiff_t, ptrdiff_t);
264
extern bool compare_string_intervals (Lisp_Object, Lisp_Object);
Jan D's avatar
Jan D committed
265
extern Lisp_Object textget (Lisp_Object, Lisp_Object);
266
extern Lisp_Object lookup_char_property (Lisp_Object, Lisp_Object, bool);
267
extern void move_if_not_intangible (ptrdiff_t);
268 269
extern bool get_property_and_range (ptrdiff_t, Lisp_Object, Lisp_Object *,
				    ptrdiff_t *, ptrdiff_t *, Lisp_Object);
270 271
extern Lisp_Object get_local_map (ptrdiff_t, struct buffer *, Lisp_Object);
extern INTERVAL update_interval (INTERVAL, ptrdiff_t);
272
extern void set_intervals_multibyte (bool);
Jan D's avatar
Jan D committed
273
extern INTERVAL validate_interval_range (Lisp_Object, Lisp_Object *,
274
                                         Lisp_Object *, bool);
275
extern INTERVAL interval_of (ptrdiff_t, Lisp_Object);
276

277
/* Defined in xdisp.c.  */
278
extern int invisible_prop (Lisp_Object, Lisp_Object);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
279

280
/* Defined in textprop.c.  */
Jan D's avatar
Jan D committed
281 282 283 284 285 286 287 288 289 290 291
extern Lisp_Object copy_text_properties (Lisp_Object, Lisp_Object,
                                         Lisp_Object, Lisp_Object,
                                         Lisp_Object, Lisp_Object);
extern Lisp_Object set_text_properties (Lisp_Object, Lisp_Object,
                                        Lisp_Object, Lisp_Object,
                                        Lisp_Object);
extern void set_text_properties_1 (Lisp_Object, Lisp_Object,
                                   Lisp_Object, Lisp_Object, INTERVAL);

Lisp_Object text_property_list (Lisp_Object, Lisp_Object, Lisp_Object,
                                Lisp_Object);
292
void add_text_properties_from_list (Lisp_Object, Lisp_Object, Lisp_Object);
293
Lisp_Object extend_property_ranges (Lisp_Object, Lisp_Object, Lisp_Object);
Jan D's avatar
Jan D committed
294
Lisp_Object get_char_property_and_overlay (Lisp_Object, Lisp_Object,
295
                                           Lisp_Object, Lisp_Object *);
Jan D's avatar
Jan D committed
296 297 298 299
extern int text_property_stickiness (Lisp_Object prop, Lisp_Object pos,
                                     Lisp_Object buffer);

extern void syms_of_textprop (void);
Kenichi Handa's avatar
Kenichi Handa committed
300

301
INLINE_HEADER_END
302 303

#endif /* EMACS_INTERVALS_H */