01484b7aae39f4d8988a767fb8d70cdcf49de6a4
[chise/xemacs-chise.git] / src / insdel.c
1 /* Buffer insertion/deletion and gap motion for XEmacs.
2    Copyright (C) 1985, 1986, 1991, 1992, 1993, 1994, 1995
3    Free Software Foundation, Inc.
4    Copyright (C) 1995 Sun Microsystems, Inc.
5
6 This file is part of XEmacs.
7
8 XEmacs is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 2, or (at your option) any
11 later version.
12
13 XEmacs is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with XEmacs; see the file COPYING.  If not, write to
20 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA.  */
22
23 /* Synched up with: Mule 2.0, FSF 19.30.  Diverges significantly. */
24
25 /* This file has been Mule-ized. */
26
27 /* Overhauled by Ben Wing, December 1994, for Mule implementation. */
28
29 /*
30    There are three possible ways to specify positions in a buffer.  All
31    of these are one-based: the beginning of the buffer is position or
32    index 1, and 0 is not a valid position.
33
34    As a "buffer position" (typedef Bufpos):
35
36       This is an index specifying an offset in characters from the
37       beginning of the buffer.  Note that buffer positions are
38       logically *between* characters, not on a character.  The
39       difference between two buffer positions specifies the number of
40       characters between those positions.  Buffer positions are the
41       only kind of position externally visible to the user.
42
43    As a "byte index" (typedef Bytind):
44
45       This is an index over the bytes used to represent the characters
46       in the buffer.  If there is no Mule support, this is identical
47       to a buffer position, because each character is represented
48       using one byte.  However, with Mule support, many characters
49       require two or more bytes for their representation, and so a
50       byte index may be greater than the corresponding buffer
51       position.
52
53    As a "memory index" (typedef Memind):
54
55       This is the byte index adjusted for the gap.  For positions
56       before the gap, this is identical to the byte index.  For
57       positions after the gap, this is the byte index plus the gap
58       size.  There are two possible memory indices for the gap
59       position; the memory index at the beginning of the gap should
60       always be used, except in code that deals with manipulating the
61       gap, where both indices may be seen.  The address of the
62       character "at" (i.e. following) a particular position can be
63       obtained from the formula
64
65         buffer_start_address + memory_index(position) - 1
66
67       except in the case of characters at the gap position.
68
69    Other typedefs:
70    ===============
71
72       Emchar:
73       -------
74         This typedef represents a single Emacs character, which can be
75         ASCII, ISO-8859, or some extended character, as would typically
76         be used for Kanji.  Note that the representation of a character
77         as an Emchar is *not* the same as the representation of that
78         same character in a string; thus, you cannot do the standard
79         C trick of passing a pointer to a character to a function that
80         expects a string.
81
82         An Emchar takes up 19 bits of representation and (for code
83         compatibility and such) is compatible with an int.  This
84         representation is visible on the Lisp level.  The important
85         characteristics of the Emchar representation are
86
87           -- values 0x00 - 0x7f represent ASCII.
88           -- values 0x80 - 0xff represent the right half of ISO-8859-1.
89           -- values 0x100 and up represent all other characters.
90
91         This means that Emchar values are upwardly compatible with
92         the standard 8-bit representation of ASCII/ISO-8859-1.
93
94       Bufbyte:
95       --------
96         The data in a buffer or string is logically made up of Bufbyte
97         objects, where a Bufbyte takes up the same amount of space as a
98         char. (It is declared differently, though, to catch invalid
99         usages.) Strings stored using Bufbytes are said to be in
100         "internal format".  The important characteristics of internal
101         format are
102
103           -- ASCII characters are represented as a single Bufbyte,
104              in the range 0 - 0x7f.
105           -- All other characters are represented as a Bufbyte in
106              the range 0x80 - 0x9f followed by one or more Bufbytes
107              in the range 0xa0 to 0xff.
108
109         This leads to a number of desirable properties:
110
111           -- Given the position of the beginning of a character,
112              you can find the beginning of the next or previous
113              character in constant time.
114           -- When searching for a substring or an ASCII character
115              within the string, you need merely use standard
116              searching routines.
117
118       array of char:
119       --------------
120         Strings that go in or out of Emacs are in "external format",
121         typedef'ed as an array of char or a char *.  There is more
122         than one external format (JIS, EUC, etc.) but they all
123         have similar properties.  They are modal encodings,
124         which is to say that the meaning of particular bytes is
125         not fixed but depends on what "mode" the string is currently
126         in (e.g. bytes in the range 0 - 0x7f might be
127         interpreted as ASCII, or as Hiragana, or as 2-byte Kanji,
128         depending on the current mode).  The mode starts out in
129         ASCII/ISO-8859-1 and is switched using escape sequences --
130         for example, in the JIS encoding, 'ESC $ B' switches to a
131         mode where pairs of bytes in the range 0 - 0x7f
132         are interpreted as Kanji characters.
133
134         External-formatted data is generally desirable for passing
135         data between programs because it is upwardly compatible
136         with standard ASCII/ISO-8859-1 strings and may require
137         less space than internal encodings such as the one
138         described above.  In addition, some encodings (e.g. JIS)
139         keep all characters (except the ESC used to switch modes)
140         in the printing ASCII range 0x20 - 0x7e, which results in
141         a much higher probability that the data will avoid being
142         garbled in transmission.  Externally-formatted data is
143         generally not very convenient to work with, however, and
144         for this reason is usually converted to internal format
145         before any work is done on the string.
146
147         NOTE: filenames need to be in external format so that
148         ISO-8859-1 characters come out correctly.
149
150       Charcount:
151       ----------
152         This typedef represents a count of characters, such as
153         a character offset into a string or the number of
154         characters between two positions in a buffer.  The
155         difference between two Bufpos's is a Charcount, and
156         character positions in a string are represented using
157         a Charcount.
158
159       Bytecount:
160       ----------
161         Similar to a Charcount but represents a count of bytes.
162         The difference between two Bytind's is a Bytecount.
163
164
165    Usage of the various representations:
166    =====================================
167
168    Memory indices are used in low-level functions in insdel.c and for
169    extent endpoints and marker positions.  The reason for this is that
170    this way, the extents and markers don't need to be updated for most
171    insertions, which merely shrink the gap and don't move any
172    characters around in memory.
173
174    (The beginning-of-gap memory index simplifies insertions w.r.t.
175    markers, because text usually gets inserted after markers.  For
176    extents, it is merely for consistency, because text can get
177    inserted either before or after an extent's endpoint depending on
178    the open/closedness of the endpoint.)
179
180    Byte indices are used in other code that needs to be fast,
181    such as the searching, redisplay, and extent-manipulation code.
182
183    Buffer positions are used in all other code.  This is because this
184    representation is easiest to work with (especially since Lisp
185    code always uses buffer positions), necessitates the fewest
186    changes to existing code, and is the safest (e.g. if the text gets
187    shifted underneath a buffer position, it will still point to a
188    character; if text is shifted under a byte index, it might point
189    to the middle of a character, which would be bad).
190
191    Similarly, Charcounts are used in all code that deals with strings
192    except for code that needs to be fast, which used Bytecounts.
193
194    Strings are always passed around internally using internal format.
195    Conversions between external format are performed at the time
196    that the data goes in or out of Emacs.
197
198    Working with the various representations:
199    ========================================= */
200
201 #include <config.h>
202 #include "lisp.h"
203 #include <limits.h>
204
205 #include "buffer.h"
206 #include "device.h"
207 #include "frame.h"
208 #include "extents.h"
209 #include "insdel.h"
210 #include "lstream.h"
211 #include "redisplay.h"
212 #include "line-number.h"
213
214 /* We write things this way because it's very important the
215    MAX_BYTIND_GAP_SIZE_3 is a multiple of 3. (As it happens,
216    65535 is a multiple of 3, but this may not always be the
217    case.) */
218
219 #define MAX_BUFPOS_GAP_SIZE_3 (65535/3)
220 #define MAX_BYTIND_GAP_SIZE_3 (3 * MAX_BUFPOS_GAP_SIZE_3)
221
222 short three_to_one_table[1 + MAX_BYTIND_GAP_SIZE_3];
223
224 /* Various macros modelled along the lines of those in buffer.h.
225    Purposefully omitted from buffer.h because files other than this
226    one should not be using them. */
227
228 /* Address of beginning of buffer.  This is an lvalue because
229    BUFFER_ALLOC needs it to be. */
230 #define BUF_BEG_ADDR(buf) ((buf)->text->beg)
231
232 /* Set the address of beginning of buffer. */
233 #define SET_BUF_BEG_ADDR(buf, addr) do { (buf)->text->beg = (addr); } while (0)
234
235 /* Gap size.  */
236 #define BUF_GAP_SIZE(buf) ((buf)->text->gap_size + 0)
237 #define BUF_END_GAP_SIZE(buf) ((buf)->text->end_gap_size + 0)
238 /* Set gap size.  */
239 #define SET_BUF_GAP_SIZE(buf, value) \
240   do { (buf)->text->gap_size = (value); } while (0)
241 #define SET_BUF_END_GAP_SIZE(buf, value) \
242   do { (buf)->text->end_gap_size = (value); } while (0)
243
244 /* Gap location.  */
245 #define BI_BUF_GPT(buf) ((buf)->text->gpt + 0)
246 #define BUF_GPT_ADDR(buf) (BUF_BEG_ADDR (buf) + BI_BUF_GPT (buf) - 1)
247
248 /* Set gap location.  */
249 #define SET_BI_BUF_GPT(buf, value) do { (buf)->text->gpt = (value); } while (0)
250
251 /* Set end of buffer.  */
252 #define SET_BOTH_BUF_Z(buf, val, bival)         \
253 do                                              \
254 {                                               \
255   (buf)->text->z = (bival);                     \
256   (buf)->text->bufz = (val);                    \
257 } while (0)
258
259 /* Under Mule, we maintain two sentinels in the buffer: one at the
260    beginning of the gap, and one at the end of the buffer.  This
261    allows us to move forward, examining bytes looking for the
262    end of a character, and not worry about running off the end.
263    We do not need corresponding sentinels when moving backwards
264    because we do not have to look past the beginning of a character
265    to find the beginning of the character.
266
267    Every time we change the beginning of the gap, we have to
268    call SET_GAP_SENTINEL().
269
270    Every time we change the total size (characters plus gap)
271    of the buffer, we have to call SET_END_SENTINEL().
272  */
273
274
275 #ifdef MULE
276 # define GAP_CAN_HOLD_SIZE_P(buf, len) (BUF_GAP_SIZE (buf) >= (len) + 1)
277 # define SET_GAP_SENTINEL(buf) (*BUF_GPT_ADDR (buf) = 0)
278 # define BUF_END_SENTINEL_SIZE 1
279 # define SET_END_SENTINEL(buf) \
280   (*(BUF_BEG_ADDR (buf) + BUF_GAP_SIZE (buf) + BI_BUF_Z (buf) - 1) = 0)
281 #else
282 # define GAP_CAN_HOLD_SIZE_P(buf, len) (BUF_GAP_SIZE (buf) >= (len))
283 # define SET_GAP_SENTINEL(buf)
284 # define BUF_END_SENTINEL_SIZE 0
285 # define SET_END_SENTINEL(buf)
286 #endif
287
288 \f
289 /************************************************************************/
290 /*                    Charcount/Bytecount conversion                    */
291 /************************************************************************/
292
293 /* Optimization.  Do it.  Live it.  Love it.  */
294
295 #ifdef MULE
296
297 /* We include the basic functions here that require no specific
298    knowledge of how data is Mule-encoded into a buffer other
299    than the basic (00 - 7F), (80 - 9F), (A0 - FF) scheme.
300    Anything that requires more specific knowledge goes into
301    mule-charset.c. */
302
303 /* Given a pointer to a text string and a length in bytes, return
304    the equivalent length in characters. */
305
306 Charcount
307 bytecount_to_charcount (CONST Bufbyte *ptr, Bytecount len)
308 {
309   Charcount count = 0;
310   CONST Bufbyte *end = ptr + len;
311
312 #if (LONGBITS == 32 || LONGBITS == 64)
313
314 # if (LONGBITS == 32)
315 #  define LONG_BYTES 4
316 #  define ALIGN_MASK 0xFFFFFFFCU
317 #  define HIGH_BIT_MASK 0x80808080U
318 # else
319 #  define LONG_BYTES 8
320 #  define ALIGN_MASK 0xFFFFFFFFFFFFFFF8UL
321    /* I had a dream, I was being overrun with early Intel processors ... */
322 #  define HIGH_BIT_MASK 0x8080808080808080UL
323 # endif
324
325   /* When we have a large number of bytes to scan, we can be trickier
326      and significantly faster by scanning them in chunks of the CPU word
327      size (assuming that they're all ASCII -- we cut out as soon as
328      we find something non-ASCII). */
329   if (len >= 12)
330     {
331       /* Determine the section in the middle of the string that's
332          amenable to this treatment.  Everything has to be aligned
333          on CPU word boundaries. */
334       CONST Bufbyte *aligned_ptr =
335         (CONST Bufbyte *) (((unsigned long) (ptr + LONG_BYTES - 1)) &
336                            ALIGN_MASK);
337       CONST Bufbyte *aligned_end =
338         (CONST Bufbyte *) (((unsigned long) end) & ALIGN_MASK);
339
340       /* Handle unaligned stuff at the beginning. */
341       while (ptr < aligned_ptr)
342         {
343           if (!BYTE_ASCII_P (*ptr))
344             goto bail;
345           count++, ptr++;
346         }
347       /* Now do it. */
348       while (ptr < aligned_end)
349         {
350
351           if ((* (unsigned long *) ptr) & HIGH_BIT_MASK)
352             goto bail;
353           ptr += LONG_BYTES;
354           count += LONG_BYTES;
355         }
356     }
357
358 #endif /* LONGBITS == 32 || LONGBITS == 64 */
359
360  bail:
361   while (ptr < end)
362     {
363       count++;
364       INC_CHARPTR (ptr);
365     }
366 #ifdef ERROR_CHECK_BUFPOS
367   /* Bomb out if the specified substring ends in the middle
368      of a character.  Note that we might have already gotten
369      a core dump above from an invalid reference, but at least
370      we will get no farther than here. */
371   assert (ptr == end);
372 #endif
373
374   return count;
375 }
376
377 /* Given a pointer to a text string and a length in characters, return
378    the equivalent length in bytes. */
379
380 Bytecount
381 charcount_to_bytecount (CONST Bufbyte *ptr, Charcount len)
382 {
383   CONST Bufbyte *newptr = ptr;
384
385   while (len > 0)
386     {
387       INC_CHARPTR (newptr);
388       len--;
389     }
390   return newptr - ptr;
391 }
392
393 /* The next two functions are the actual meat behind the
394    bufpos-to-bytind and bytind-to-bufpos conversions.  Currently
395    the method they use is fairly unsophisticated; see buffer.h.
396
397    Note that bufpos_to_bytind_func() is probably the most-called
398    function in all of XEmacs.  Therefore, it must be FAST FAST FAST.
399    This is the reason why so much of the code is duplicated.
400
401    Similar considerations apply to bytind_to_bufpos_func(), although
402    less so because the function is not called so often.
403
404    #### At some point this should use a more sophisticated method;
405    see buffer.h. */
406
407 static int not_very_random_number;
408
409 Bytind
410 bufpos_to_bytind_func (struct buffer *buf, Bufpos x)
411 {
412   Bufpos bufmin;
413   Bufpos bufmax;
414   Bytind bytmin;
415   Bytind bytmax;
416   int size;
417   int forward_p;
418   Bytind retval;
419   int diff_so_far;
420   int add_to_cache = 0;
421
422   /* Check for some cached positions, for speed. */
423   if (x == BUF_PT (buf))
424     return BI_BUF_PT (buf);
425   if (x == BUF_ZV (buf))
426     return BI_BUF_ZV (buf);
427   if (x == BUF_BEGV (buf))
428     return BI_BUF_BEGV (buf);
429
430   bufmin = buf->text->mule_bufmin;
431   bufmax = buf->text->mule_bufmax;
432   bytmin = buf->text->mule_bytmin;
433   bytmax = buf->text->mule_bytmax;
434   size = (1 << buf->text->mule_shifter) + !!buf->text->mule_three_p;
435
436   /* The basic idea here is that we shift the "known region" up or down
437      until it overlaps the specified position.  We do this by moving
438      the upper bound of the known region up one character at a time,
439      and moving the lower bound of the known region up as necessary
440      when the size of the character just seen changes.
441
442      We optimize this, however, by first shifting the known region to
443      one of the cached points if it's close by. (We don't check BEG or
444      Z, even though they're cached; most of the time these will be the
445      same as BEGV and ZV, and when they're not, they're not likely
446      to be used.) */
447
448   if (x > bufmax)
449     {
450       Bufpos diffmax = x - bufmax;
451       Bufpos diffpt = x - BUF_PT (buf);
452       Bufpos diffzv = BUF_ZV (buf) - x;
453       /* #### This value could stand some more exploration. */
454       Charcount heuristic_hack = (bufmax - bufmin) >> 2;
455
456       /* Check if the position is closer to PT or ZV than to the
457          end of the known region. */
458
459       if (diffpt < 0)
460         diffpt = -diffpt;
461       if (diffzv < 0)
462         diffzv = -diffzv;
463
464       /* But also implement a heuristic that favors the known region
465          over PT or ZV.  The reason for this is that switching to
466          PT or ZV will wipe out the knowledge in the known region,
467          which might be annoying if the known region is large and
468          PT or ZV is not that much closer than the end of the known
469          region. */
470
471       diffzv += heuristic_hack;
472       diffpt += heuristic_hack;
473       if (diffpt < diffmax && diffpt <= diffzv)
474         {
475           bufmax = bufmin = BUF_PT (buf);
476           bytmax = bytmin = BI_BUF_PT (buf);
477           /* We set the size to 1 even though it doesn't really
478              matter because the new known region contains no
479              characters.  We do this because this is the most
480              likely size of the characters around the new known
481              region, and we avoid potential yuckiness that is
482              done when size == 3. */
483           size = 1;
484         }
485       if (diffzv < diffmax)
486         {
487           bufmax = bufmin = BUF_ZV (buf);
488           bytmax = bytmin = BI_BUF_ZV (buf);
489           size = 1;
490         }
491     }
492 #ifdef ERROR_CHECK_BUFPOS
493   else if (x >= bufmin)
494     abort ();
495 #endif
496   else
497     {
498       Bufpos diffmin = bufmin - x;
499       Bufpos diffpt = BUF_PT (buf) - x;
500       Bufpos diffbegv = x - BUF_BEGV (buf);
501       /* #### This value could stand some more exploration. */
502       Charcount heuristic_hack = (bufmax - bufmin) >> 2;
503
504       if (diffpt < 0)
505         diffpt = -diffpt;
506       if (diffbegv < 0)
507         diffbegv = -diffbegv;
508
509       /* But also implement a heuristic that favors the known region --
510          see above. */
511
512       diffbegv += heuristic_hack;
513       diffpt += heuristic_hack;
514
515       if (diffpt < diffmin && diffpt <= diffbegv)
516         {
517           bufmax = bufmin = BUF_PT (buf);
518           bytmax = bytmin = BI_BUF_PT (buf);
519           /* We set the size to 1 even though it doesn't really
520              matter because the new known region contains no
521              characters.  We do this because this is the most
522              likely size of the characters around the new known
523              region, and we avoid potential yuckiness that is
524              done when size == 3. */
525           size = 1;
526         }
527       if (diffbegv < diffmin)
528         {
529           bufmax = bufmin = BUF_BEGV (buf);
530           bytmax = bytmin = BI_BUF_BEGV (buf);
531           size = 1;
532         }
533     }
534
535   diff_so_far = x > bufmax ? x - bufmax : bufmin - x;
536   if (diff_so_far > 50)
537     {
538       /* If we have to move more than a certain amount, then look
539          into our cache. */
540       int minval = INT_MAX;
541       int found = 0;
542       int i;
543
544       add_to_cache = 1;
545       /* I considered keeping the positions ordered.  This would speed
546          up this loop, but updating the cache would take longer, so
547          it doesn't seem like it would really matter. */
548       for (i = 0; i < 16; i++)
549         {
550           int diff = buf->text->mule_bufpos_cache[i] - x;
551
552           if (diff < 0)
553             diff = -diff;
554           if (diff < minval)
555             {
556               minval = diff;
557               found = i;
558             }
559         }
560
561       if (minval < diff_so_far)
562         {
563           bufmax = bufmin = buf->text->mule_bufpos_cache[found];
564           bytmax = bytmin = buf->text->mule_bytind_cache[found];
565           size = 1;
566         }
567     }
568
569   /* It's conceivable that the caching above could lead to X being
570      the same as one of the range edges. */
571   if (x >= bufmax)
572     {
573       Bytind newmax;
574       Bytecount newsize;
575
576       forward_p = 1;
577       while (x > bufmax)
578         {
579           newmax = bytmax;
580
581           INC_BYTIND (buf, newmax);
582           newsize = newmax - bytmax;
583           if (newsize != size)
584             {
585               bufmin = bufmax;
586               bytmin = bytmax;
587               size = newsize;
588             }
589           bytmax = newmax;
590           bufmax++;
591         }
592       retval = bytmax;
593
594       /* #### Should go past the found location to reduce the number
595          of times that this function is called */
596     }
597   else /* x < bufmin */
598     {
599       Bytind newmin;
600       Bytecount newsize;
601
602       forward_p = 0;
603       while (x < bufmin)
604         {
605           newmin = bytmin;
606
607           DEC_BYTIND (buf, newmin);
608           newsize = bytmin - newmin;
609           if (newsize != size)
610             {
611               bufmax = bufmin;
612               bytmax = bytmin;
613               size = newsize;
614             }
615           bytmin = newmin;
616           bufmin--;
617         }
618       retval = bytmin;
619
620       /* #### Should go past the found location to reduce the number
621          of times that this function is called
622          */
623     }
624
625   /* If size is three, than we have to max sure that the range we
626      discovered isn't too large, because we use a fixed-length
627      table to divide by 3. */
628
629   if (size == 3)
630     {
631       int gap = bytmax - bytmin;
632       buf->text->mule_three_p = 1;
633       buf->text->mule_shifter = 1;
634
635       if (gap > MAX_BYTIND_GAP_SIZE_3)
636         {
637           if (forward_p)
638             {
639               bytmin = bytmax - MAX_BYTIND_GAP_SIZE_3;
640               bufmin = bufmax - MAX_BUFPOS_GAP_SIZE_3;
641             }
642           else
643             {
644               bytmax = bytmin + MAX_BYTIND_GAP_SIZE_3;
645               bufmax = bufmin + MAX_BUFPOS_GAP_SIZE_3;
646             }
647         }
648     }
649   else
650     {
651       buf->text->mule_three_p = 0;
652       if (size == 4)
653         buf->text->mule_shifter = 2;
654       else
655         buf->text->mule_shifter = size - 1;
656     }
657
658   buf->text->mule_bufmin = bufmin;
659   buf->text->mule_bufmax = bufmax;
660   buf->text->mule_bytmin = bytmin;
661   buf->text->mule_bytmax = bytmax;
662
663   if (add_to_cache)
664     {
665       int replace_loc;
666
667       /* We throw away a "random" cached value and replace it with
668          the new value.  It doesn't actually have to be very random
669          at all, just evenly distributed.
670
671          #### It would be better to use a least-recently-used algorithm
672          or something that tries to space things out, but I'm not sure
673          it's worth it to go to the trouble of maintaining that. */
674       not_very_random_number += 621;
675       replace_loc = not_very_random_number & 15;
676       buf->text->mule_bufpos_cache[replace_loc] = x;
677       buf->text->mule_bytind_cache[replace_loc] = retval;
678     }
679
680   return retval;
681 }
682
683 /* The logic in this function is almost identical to the logic in
684    the previous function. */
685
686 Bufpos
687 bytind_to_bufpos_func (struct buffer *buf, Bytind x)
688 {
689   Bufpos bufmin;
690   Bufpos bufmax;
691   Bytind bytmin;
692   Bytind bytmax;
693   int size;
694   int forward_p;
695   Bufpos retval;
696   int diff_so_far;
697   int add_to_cache = 0;
698
699   /* Check for some cached positions, for speed. */
700   if (x == BI_BUF_PT (buf))
701     return BUF_PT (buf);
702   if (x == BI_BUF_ZV (buf))
703     return BUF_ZV (buf);
704   if (x == BI_BUF_BEGV (buf))
705     return BUF_BEGV (buf);
706
707   bufmin = buf->text->mule_bufmin;
708   bufmax = buf->text->mule_bufmax;
709   bytmin = buf->text->mule_bytmin;
710   bytmax = buf->text->mule_bytmax;
711   size = (1 << buf->text->mule_shifter) + !!buf->text->mule_three_p;
712
713   /* The basic idea here is that we shift the "known region" up or down
714      until it overlaps the specified position.  We do this by moving
715      the upper bound of the known region up one character at a time,
716      and moving the lower bound of the known region up as necessary
717      when the size of the character just seen changes.
718
719      We optimize this, however, by first shifting the known region to
720      one of the cached points if it's close by. (We don't check BI_BEG or
721      BI_Z, even though they're cached; most of the time these will be the
722      same as BI_BEGV and BI_ZV, and when they're not, they're not likely
723      to be used.) */
724
725   if (x > bytmax)
726     {
727       Bytind diffmax = x - bytmax;
728       Bytind diffpt = x - BI_BUF_PT (buf);
729       Bytind diffzv = BI_BUF_ZV (buf) - x;
730       /* #### This value could stand some more exploration. */
731       Bytecount heuristic_hack = (bytmax - bytmin) >> 2;
732
733       /* Check if the position is closer to PT or ZV than to the
734          end of the known region. */
735
736       if (diffpt < 0)
737         diffpt = -diffpt;
738       if (diffzv < 0)
739         diffzv = -diffzv;
740
741       /* But also implement a heuristic that favors the known region
742          over BI_PT or BI_ZV.  The reason for this is that switching to
743          BI_PT or BI_ZV will wipe out the knowledge in the known region,
744          which might be annoying if the known region is large and
745          BI_PT or BI_ZV is not that much closer than the end of the known
746          region. */
747
748       diffzv += heuristic_hack;
749       diffpt += heuristic_hack;
750       if (diffpt < diffmax && diffpt <= diffzv)
751         {
752           bufmax = bufmin = BUF_PT (buf);
753           bytmax = bytmin = BI_BUF_PT (buf);
754           /* We set the size to 1 even though it doesn't really
755              matter because the new known region contains no
756              characters.  We do this because this is the most
757              likely size of the characters around the new known
758              region, and we avoid potential yuckiness that is
759              done when size == 3. */
760           size = 1;
761         }
762       if (diffzv < diffmax)
763         {
764           bufmax = bufmin = BUF_ZV (buf);
765           bytmax = bytmin = BI_BUF_ZV (buf);
766           size = 1;
767         }
768     }
769 #ifdef ERROR_CHECK_BUFPOS
770   else if (x >= bytmin)
771     abort ();
772 #endif
773   else
774     {
775       Bytind diffmin = bytmin - x;
776       Bytind diffpt = BI_BUF_PT (buf) - x;
777       Bytind diffbegv = x - BI_BUF_BEGV (buf);
778       /* #### This value could stand some more exploration. */
779       Bytecount heuristic_hack = (bytmax - bytmin) >> 2;
780
781       if (diffpt < 0)
782         diffpt = -diffpt;
783       if (diffbegv < 0)
784         diffbegv = -diffbegv;
785
786       /* But also implement a heuristic that favors the known region --
787          see above. */
788
789       diffbegv += heuristic_hack;
790       diffpt += heuristic_hack;
791
792       if (diffpt < diffmin && diffpt <= diffbegv)
793         {
794           bufmax = bufmin = BUF_PT (buf);
795           bytmax = bytmin = BI_BUF_PT (buf);
796           /* We set the size to 1 even though it doesn't really
797              matter because the new known region contains no
798              characters.  We do this because this is the most
799              likely size of the characters around the new known
800              region, and we avoid potential yuckiness that is
801              done when size == 3. */
802           size = 1;
803         }
804       if (diffbegv < diffmin)
805         {
806           bufmax = bufmin = BUF_BEGV (buf);
807           bytmax = bytmin = BI_BUF_BEGV (buf);
808           size = 1;
809         }
810     }
811
812   diff_so_far = x > bytmax ? x - bytmax : bytmin - x;
813   if (diff_so_far > 50)
814     {
815       /* If we have to move more than a certain amount, then look
816          into our cache. */
817       int minval = INT_MAX;
818       int found = 0;
819       int i;
820
821       add_to_cache = 1;
822       /* I considered keeping the positions ordered.  This would speed
823          up this loop, but updating the cache would take longer, so
824          it doesn't seem like it would really matter. */
825       for (i = 0; i < 16; i++)
826         {
827           int diff = buf->text->mule_bytind_cache[i] - x;
828
829           if (diff < 0)
830             diff = -diff;
831           if (diff < minval)
832             {
833               minval = diff;
834               found = i;
835             }
836         }
837
838       if (minval < diff_so_far)
839         {
840           bufmax = bufmin = buf->text->mule_bufpos_cache[found];
841           bytmax = bytmin = buf->text->mule_bytind_cache[found];
842           size = 1;
843         }
844     }
845
846   /* It's conceivable that the caching above could lead to X being
847      the same as one of the range edges. */
848   if (x >= bytmax)
849     {
850       Bytind newmax;
851       Bytecount newsize;
852
853       forward_p = 1;
854       while (x > bytmax)
855         {
856           newmax = bytmax;
857
858           INC_BYTIND (buf, newmax);
859           newsize = newmax - bytmax;
860           if (newsize != size)
861             {
862               bufmin = bufmax;
863               bytmin = bytmax;
864               size = newsize;
865             }
866           bytmax = newmax;
867           bufmax++;
868         }
869       retval = bufmax;
870
871       /* #### Should go past the found location to reduce the number
872          of times that this function is called */
873     }
874   else /* x <= bytmin */
875     {
876       Bytind newmin;
877       Bytecount newsize;
878
879       forward_p = 0;
880       while (x < bytmin)
881         {
882           newmin = bytmin;
883
884           DEC_BYTIND (buf, newmin);
885           newsize = bytmin - newmin;
886           if (newsize != size)
887             {
888               bufmax = bufmin;
889               bytmax = bytmin;
890               size = newsize;
891             }
892           bytmin = newmin;
893           bufmin--;
894         }
895       retval = bufmin;
896
897       /* #### Should go past the found location to reduce the number
898          of times that this function is called
899          */
900     }
901
902   /* If size is three, than we have to max sure that the range we
903      discovered isn't too large, because we use a fixed-length
904      table to divide by 3. */
905
906   if (size == 3)
907     {
908       int gap = bytmax - bytmin;
909       buf->text->mule_three_p = 1;
910       buf->text->mule_shifter = 1;
911
912       if (gap > MAX_BYTIND_GAP_SIZE_3)
913         {
914           if (forward_p)
915             {
916               bytmin = bytmax - MAX_BYTIND_GAP_SIZE_3;
917               bufmin = bufmax - MAX_BUFPOS_GAP_SIZE_3;
918             }
919           else
920             {
921               bytmax = bytmin + MAX_BYTIND_GAP_SIZE_3;
922               bufmax = bufmin + MAX_BUFPOS_GAP_SIZE_3;
923             }
924         }
925     }
926   else
927     {
928       buf->text->mule_three_p = 0;
929       if (size == 4)
930         buf->text->mule_shifter = 2;
931       else
932         buf->text->mule_shifter = size - 1;
933     }
934
935   buf->text->mule_bufmin = bufmin;
936   buf->text->mule_bufmax = bufmax;
937   buf->text->mule_bytmin = bytmin;
938   buf->text->mule_bytmax = bytmax;
939
940   if (add_to_cache)
941     {
942       int replace_loc;
943
944       /* We throw away a "random" cached value and replace it with
945          the new value.  It doesn't actually have to be very random
946          at all, just evenly distributed.
947
948          #### It would be better to use a least-recently-used algorithm
949          or something that tries to space things out, but I'm not sure
950          it's worth it to go to the trouble of maintaining that. */
951       not_very_random_number += 621;
952       replace_loc = not_very_random_number & 15;
953       buf->text->mule_bufpos_cache[replace_loc] = retval;
954       buf->text->mule_bytind_cache[replace_loc] = x;
955     }
956
957   return retval;
958 }
959
960 /* Text of length BYTELENGTH and CHARLENGTH (in different units)
961    was inserted at bufpos START. */
962
963 static void
964 buffer_mule_signal_inserted_region (struct buffer *buf, Bufpos start,
965                                     Bytecount bytelength,
966                                     Charcount charlength)
967 {
968   int size = (1 << buf->text->mule_shifter) + !!buf->text->mule_three_p;
969   int i;
970
971   /* Adjust the cache of known positions. */
972   for (i = 0; i < 16; i++)
973     {
974
975       if (buf->text->mule_bufpos_cache[i] > start)
976         {
977           buf->text->mule_bufpos_cache[i] += charlength;
978           buf->text->mule_bytind_cache[i] += bytelength;
979         }
980     }
981
982   if (start >= buf->text->mule_bufmax)
983     return;
984
985   /* The insertion is either before the known region, in which case
986      it shoves it forward; or within the known region, in which case
987      it shoves the end forward. (But it may make the known region
988      inconsistent, so we may have to shorten it.) */
989
990   if (start <= buf->text->mule_bufmin)
991     {
992       buf->text->mule_bufmin += charlength;
993       buf->text->mule_bufmax += charlength;
994       buf->text->mule_bytmin += bytelength;
995       buf->text->mule_bytmax += bytelength;
996     }
997   else
998     {
999       Bufpos end = start + charlength;
1000       /* the insertion point divides the known region in two.
1001          Keep the longer half, at least, and expand into the
1002          inserted chunk as much as possible. */
1003
1004       if (start - buf->text->mule_bufmin > buf->text->mule_bufmax - start)
1005         {
1006           Bytind bytestart = (buf->text->mule_bytmin
1007                               + size * (start - buf->text->mule_bufmin));
1008           Bytind bytenew;
1009
1010           while (start < end)
1011             {
1012               bytenew = bytestart;
1013               INC_BYTIND (buf, bytenew);
1014               if (bytenew - bytestart != size)
1015                 break;
1016               start++;
1017               bytestart = bytenew;
1018             }
1019           if (start != end)
1020             {
1021               buf->text->mule_bufmax = start;
1022               buf->text->mule_bytmax = bytestart;
1023             }
1024           else
1025             {
1026               buf->text->mule_bufmax += charlength;
1027               buf->text->mule_bytmax += bytelength;
1028             }
1029         }
1030       else
1031         {
1032           Bytind byteend = (buf->text->mule_bytmin
1033                             + size * (start - buf->text->mule_bufmin)
1034                             + bytelength);
1035           Bytind bytenew;
1036
1037           buf->text->mule_bufmax += charlength;
1038           buf->text->mule_bytmax += bytelength;
1039
1040           while (end > start)
1041             {
1042               bytenew = byteend;
1043               DEC_BYTIND (buf, bytenew);
1044               if (byteend - bytenew != size)
1045                 break;
1046               end--;
1047               byteend = bytenew;
1048             }
1049           if (start != end)
1050             {
1051               buf->text->mule_bufmin = end;
1052               buf->text->mule_bytmin = byteend;
1053             }
1054         }
1055     }
1056 }
1057
1058 /* Text from START to END (equivalent in Bytinds: from BI_START to
1059    BI_END) was deleted. */
1060
1061 static void
1062 buffer_mule_signal_deleted_region (struct buffer *buf, Bufpos start,
1063                                    Bufpos end, Bytind bi_start,
1064                                    Bytind bi_end)
1065 {
1066   int i;
1067
1068   /* Adjust the cache of known positions. */
1069   for (i = 0; i < 16; i++)
1070     {
1071       /* After the end; gets shoved backward */
1072       if (buf->text->mule_bufpos_cache[i] > end)
1073         {
1074           buf->text->mule_bufpos_cache[i] -= end - start;
1075           buf->text->mule_bytind_cache[i] -= bi_end - bi_start;
1076         }
1077       /* In the range; moves to start of range */
1078       else if (buf->text->mule_bufpos_cache[i] > start)
1079         {
1080           buf->text->mule_bufpos_cache[i] = start;
1081           buf->text->mule_bytind_cache[i] = bi_start;
1082         }
1083     }
1084
1085   /* We don't care about any text after the end of the known region. */
1086
1087   end = min (end, buf->text->mule_bufmax);
1088   bi_end = min (bi_end, buf->text->mule_bytmax);
1089   if (start >= end)
1090     return;
1091
1092   /* The end of the known region offsets by the total amount of deletion,
1093      since it's all before it. */
1094
1095   buf->text->mule_bufmax -= end - start;
1096   buf->text->mule_bytmax -= bi_end - bi_start;
1097
1098   /* Now we don't care about any text after the start of the known region. */
1099
1100   end = min (end, buf->text->mule_bufmin);
1101   bi_end = min (bi_end, buf->text->mule_bytmin);
1102   if (start >= end)
1103     return;
1104
1105   buf->text->mule_bufmin -= end - start;
1106   buf->text->mule_bytmin -= bi_end - bi_start;
1107 }
1108
1109 #endif /* MULE */
1110
1111 #ifdef ERROR_CHECK_BUFPOS
1112
1113 Bytind
1114 bufpos_to_bytind (struct buffer *buf, Bufpos x)
1115 {
1116   Bytind retval = real_bufpos_to_bytind (buf, x);
1117   ASSERT_VALID_BYTIND_UNSAFE (buf, retval);
1118   return retval;
1119 }
1120
1121 Bufpos
1122 bytind_to_bufpos (struct buffer *buf, Bytind x)
1123 {
1124   ASSERT_VALID_BYTIND_UNSAFE (buf, x);
1125   return real_bytind_to_bufpos (buf, x);
1126 }
1127
1128 #endif /* ERROR_CHECK_BUFPOS */
1129
1130 \f
1131 /************************************************************************/
1132 /*                verifying buffer and string positions                 */
1133 /************************************************************************/
1134
1135 /* Functions below are tagged with either _byte or _char indicating
1136    whether they return byte or character positions.  For a buffer,
1137    a character position is a "Bufpos" and a byte position is a "Bytind".
1138    For strings, these are sometimes typed using "Charcount" and
1139    "Bytecount". */
1140
1141 /* Flags for the functions below are:
1142
1143    GB_ALLOW_PAST_ACCESSIBLE
1144
1145      Allow positions to range over the entire buffer (BUF_BEG to BUF_Z),
1146      rather than just the accessible portion (BUF_BEGV to BUF_ZV).
1147      For strings, this flag has no effect.
1148
1149    GB_COERCE_RANGE
1150
1151      If the position is outside the allowable range, return the lower
1152      or upper bound of the range, whichever is closer to the specified
1153      position.
1154
1155    GB_NO_ERROR_IF_BAD
1156
1157      If the position is outside the allowable range, return -1.
1158
1159    GB_NEGATIVE_FROM_END
1160
1161      If a value is negative, treat it as an offset from the end.
1162      Only applies to strings.
1163
1164    The following additional flags apply only to the functions
1165    that return ranges:
1166
1167    GB_ALLOW_NIL
1168
1169      Either or both positions can be nil.  If FROM is nil,
1170      FROM_OUT will contain the lower bound of the allowed range.
1171      If TO is nil, TO_OUT will contain the upper bound of the
1172      allowed range.
1173
1174    GB_CHECK_ORDER
1175
1176      FROM must contain the lower bound and TO the upper bound
1177      of the range.  If the positions are reversed, an error is
1178      signalled.
1179
1180    The following is a combination flag:
1181
1182    GB_HISTORICAL_STRING_BEHAVIOR
1183
1184      Equivalent to (GB_NEGATIVE_FROM_END | GB_ALLOW_NIL).
1185  */
1186
1187 /* Return a buffer position stored in a Lisp_Object.  Full
1188    error-checking is done on the position.  Flags can be specified to
1189    control the behavior of out-of-range values.  The default behavior
1190    is to require that the position is within the accessible part of
1191    the buffer (BEGV and ZV), and to signal an error if the position is
1192    out of range.
1193
1194 */
1195
1196 Bufpos
1197 get_buffer_pos_char (struct buffer *b, Lisp_Object pos, unsigned int flags)
1198 {
1199   Bufpos ind;
1200   Bufpos min_allowed, max_allowed;
1201
1202   CHECK_INT_COERCE_MARKER (pos);
1203   ind = XINT (pos);
1204   min_allowed = flags & GB_ALLOW_PAST_ACCESSIBLE ? BUF_BEG (b) : BUF_BEGV (b);
1205   max_allowed = flags & GB_ALLOW_PAST_ACCESSIBLE ? BUF_Z   (b) : BUF_ZV   (b);
1206
1207   if (ind < min_allowed || ind > max_allowed)
1208     {
1209       if (flags & GB_COERCE_RANGE)
1210         ind = ind < min_allowed ? min_allowed : max_allowed;
1211       else if (flags & GB_NO_ERROR_IF_BAD)
1212         ind = -1;
1213       else
1214         {
1215           Lisp_Object buffer;
1216           XSETBUFFER (buffer, b);
1217           args_out_of_range (buffer, pos);
1218         }
1219     }
1220
1221   return ind;
1222 }
1223
1224 Bytind
1225 get_buffer_pos_byte (struct buffer *b, Lisp_Object pos, unsigned int flags)
1226 {
1227   Bufpos bpos = get_buffer_pos_char (b, pos, flags);
1228   if (bpos < 0) /* could happen with GB_NO_ERROR_IF_BAD */
1229     return -1;
1230   return bufpos_to_bytind (b, bpos);
1231 }
1232
1233 /* Return a pair of buffer positions representing a range of text,
1234    taken from a pair of Lisp_Objects.  Full error-checking is
1235    done on the positions.  Flags can be specified to control the
1236    behavior of out-of-range values.  The default behavior is to
1237    allow the range bounds to be specified in either order
1238    (however, FROM_OUT will always be the lower bound of the range
1239    and TO_OUT the upper bound),to require that the positions
1240    are within the accessible part of the buffer (BEGV and ZV),
1241    and to signal an error if the positions are out of range.
1242 */
1243
1244 void
1245 get_buffer_range_char (struct buffer *b, Lisp_Object from, Lisp_Object to,
1246                        Bufpos *from_out, Bufpos *to_out, unsigned int flags)
1247 {
1248   Bufpos min_allowed, max_allowed;
1249
1250   min_allowed = (flags & GB_ALLOW_PAST_ACCESSIBLE) ?
1251     BUF_BEG (b) : BUF_BEGV (b);
1252   max_allowed = (flags & GB_ALLOW_PAST_ACCESSIBLE) ?
1253     BUF_Z (b) : BUF_ZV (b);
1254
1255   if (NILP (from) && (flags & GB_ALLOW_NIL))
1256     *from_out = min_allowed;
1257   else
1258     *from_out = get_buffer_pos_char (b, from, flags | GB_NO_ERROR_IF_BAD);
1259
1260   if (NILP (to) && (flags & GB_ALLOW_NIL))
1261     *to_out = max_allowed;
1262   else
1263     *to_out = get_buffer_pos_char (b, to, flags | GB_NO_ERROR_IF_BAD);
1264
1265   if ((*from_out < 0 || *to_out < 0) && !(flags & GB_NO_ERROR_IF_BAD))
1266     {
1267       Lisp_Object buffer;
1268       XSETBUFFER (buffer, b);
1269       args_out_of_range_3 (buffer, from, to);
1270     }
1271
1272   if (*from_out >= 0 && *to_out >= 0 && *from_out > *to_out)
1273     {
1274       if (flags & GB_CHECK_ORDER)
1275         signal_simple_error_2 ("start greater than end", from, to);
1276       else
1277         {
1278           Bufpos temp = *from_out;
1279           *from_out = *to_out;
1280           *to_out = temp;
1281         }
1282     }
1283 }
1284
1285 void
1286 get_buffer_range_byte (struct buffer *b, Lisp_Object from, Lisp_Object to,
1287                        Bytind *from_out, Bytind *to_out, unsigned int flags)
1288 {
1289   Bufpos s, e;
1290
1291   get_buffer_range_char (b, from, to, &s, &e, flags);
1292   if (s >= 0)
1293     *from_out = bufpos_to_bytind (b, s);
1294   else /* could happen with GB_NO_ERROR_IF_BAD */
1295     *from_out = -1;
1296   if (e >= 0)
1297     *to_out = bufpos_to_bytind (b, e);
1298   else
1299     *to_out = -1;
1300 }
1301
1302 static Charcount
1303 get_string_pos_char_1 (Lisp_Object string, Lisp_Object pos, unsigned int flags,
1304                        Charcount known_length)
1305 {
1306   Charcount ccpos;
1307   Charcount min_allowed = 0;
1308   Charcount max_allowed = known_length;
1309
1310   /* Computation of KNOWN_LENGTH is potentially expensive so we pass
1311      it in. */
1312   CHECK_INT (pos);
1313   ccpos = XINT (pos);
1314   if (ccpos < 0 && flags & GB_NEGATIVE_FROM_END)
1315     ccpos += max_allowed;
1316
1317   if (ccpos < min_allowed || ccpos > max_allowed)
1318     {
1319       if (flags & GB_COERCE_RANGE)
1320         ccpos = ccpos < min_allowed ? min_allowed : max_allowed;
1321       else if (flags & GB_NO_ERROR_IF_BAD)
1322         ccpos = -1;
1323       else
1324         args_out_of_range (string, pos);
1325     }
1326
1327   return ccpos;
1328 }
1329
1330 Charcount
1331 get_string_pos_char (Lisp_Object string, Lisp_Object pos, unsigned int flags)
1332 {
1333   return get_string_pos_char_1 (string, pos, flags,
1334                                 XSTRING_CHAR_LENGTH (string));
1335 }
1336
1337 Bytecount
1338 get_string_pos_byte (Lisp_Object string, Lisp_Object pos, unsigned int flags)
1339 {
1340   Charcount ccpos = get_string_pos_char (string, pos, flags);
1341   if (ccpos < 0) /* could happen with GB_NO_ERROR_IF_BAD */
1342     return -1;
1343   return charcount_to_bytecount (XSTRING_DATA (string), ccpos);
1344 }
1345
1346 void
1347 get_string_range_char (Lisp_Object string, Lisp_Object from, Lisp_Object to,
1348                        Charcount *from_out, Charcount *to_out,
1349                        unsigned int flags)
1350 {
1351   Charcount min_allowed = 0;
1352   Charcount max_allowed = XSTRING_CHAR_LENGTH (string);
1353
1354   if (NILP (from) && (flags & GB_ALLOW_NIL))
1355     *from_out = min_allowed;
1356   else
1357     *from_out = get_string_pos_char_1 (string, from,
1358                                        flags | GB_NO_ERROR_IF_BAD,
1359                                        max_allowed);
1360
1361   if (NILP (to) && (flags & GB_ALLOW_NIL))
1362     *to_out = max_allowed;
1363   else
1364     *to_out = get_string_pos_char_1 (string, to,
1365                                      flags | GB_NO_ERROR_IF_BAD,
1366                                      max_allowed);
1367
1368   if ((*from_out < 0 || *to_out < 0) && !(flags & GB_NO_ERROR_IF_BAD))
1369     args_out_of_range_3 (string, from, to);
1370
1371   if (*from_out >= 0 && *to_out >= 0 && *from_out > *to_out)
1372     {
1373       if (flags & GB_CHECK_ORDER)
1374         signal_simple_error_2 ("start greater than end", from, to);
1375       else
1376         {
1377           Bufpos temp = *from_out;
1378           *from_out = *to_out;
1379           *to_out = temp;
1380         }
1381     }
1382 }
1383
1384 void
1385 get_string_range_byte (Lisp_Object string, Lisp_Object from, Lisp_Object to,
1386                        Bytecount *from_out, Bytecount *to_out,
1387                        unsigned int flags)
1388 {
1389   Charcount s, e;
1390
1391   get_string_range_char (string, from, to, &s, &e, flags);
1392   if (s >= 0)
1393     *from_out = charcount_to_bytecount (XSTRING_DATA (string), s);
1394   else /* could happen with GB_NO_ERROR_IF_BAD */
1395     *from_out = -1;
1396   if (e >= 0)
1397     *to_out = charcount_to_bytecount (XSTRING_DATA (string), e);
1398   else
1399     *to_out = -1;
1400
1401 }
1402
1403 Bufpos
1404 get_buffer_or_string_pos_char (Lisp_Object object, Lisp_Object pos,
1405                                unsigned int flags)
1406 {
1407   return STRINGP (object) ?
1408     get_string_pos_char (object, pos, flags) :
1409     get_buffer_pos_char (XBUFFER (object), pos, flags);
1410 }
1411
1412 Bytind
1413 get_buffer_or_string_pos_byte (Lisp_Object object, Lisp_Object pos,
1414                                unsigned int flags)
1415 {
1416   return STRINGP (object) ?
1417     get_string_pos_byte (object, pos, flags) :
1418     get_buffer_pos_byte (XBUFFER (object), pos, flags);
1419 }
1420
1421 void
1422 get_buffer_or_string_range_char (Lisp_Object object, Lisp_Object from,
1423                                  Lisp_Object to, Bufpos *from_out,
1424                                  Bufpos *to_out, unsigned int flags)
1425 {
1426   if (STRINGP (object))
1427     get_string_range_char (object, from, to, from_out, to_out, flags);
1428   else
1429     get_buffer_range_char (XBUFFER (object), from, to, from_out, to_out, flags);
1430 }
1431
1432 void
1433 get_buffer_or_string_range_byte (Lisp_Object object, Lisp_Object from,
1434                                  Lisp_Object to, Bytind *from_out,
1435                                  Bytind *to_out, unsigned int flags)
1436 {
1437   if (STRINGP (object))
1438     get_string_range_byte (object, from, to, from_out, to_out, flags);
1439   else
1440     get_buffer_range_byte (XBUFFER (object), from, to, from_out, to_out, flags);
1441 }
1442
1443 Bufpos
1444 buffer_or_string_accessible_begin_char (Lisp_Object object)
1445 {
1446   return STRINGP (object) ? 0 : BUF_BEGV (XBUFFER (object));
1447 }
1448
1449 Bufpos
1450 buffer_or_string_accessible_end_char (Lisp_Object object)
1451 {
1452   return STRINGP (object) ?
1453     XSTRING_CHAR_LENGTH (object) : BUF_ZV (XBUFFER (object));
1454 }
1455
1456 Bytind
1457 buffer_or_string_accessible_begin_byte (Lisp_Object object)
1458 {
1459   return STRINGP (object) ? 0 : BI_BUF_BEGV (XBUFFER (object));
1460 }
1461
1462 Bytind
1463 buffer_or_string_accessible_end_byte (Lisp_Object object)
1464 {
1465   return STRINGP (object) ?
1466     XSTRING_LENGTH (object) : BI_BUF_ZV (XBUFFER (object));
1467 }
1468
1469 Bufpos
1470 buffer_or_string_absolute_begin_char (Lisp_Object object)
1471 {
1472   return STRINGP (object) ? 0 : BUF_BEG (XBUFFER (object));
1473 }
1474
1475 Bufpos
1476 buffer_or_string_absolute_end_char (Lisp_Object object)
1477 {
1478   return STRINGP (object) ?
1479     XSTRING_CHAR_LENGTH (object) : BUF_Z (XBUFFER (object));
1480 }
1481
1482 Bytind
1483 buffer_or_string_absolute_begin_byte (Lisp_Object object)
1484 {
1485   return STRINGP (object) ? 0 : BI_BUF_BEG (XBUFFER (object));
1486 }
1487
1488 Bytind
1489 buffer_or_string_absolute_end_byte (Lisp_Object object)
1490 {
1491   return STRINGP (object) ?
1492     XSTRING_LENGTH (object) : BI_BUF_Z (XBUFFER (object));
1493 }
1494
1495 \f
1496 /************************************************************************/
1497 /*                     point and marker adjustment                      */
1498 /************************************************************************/
1499
1500 /* just_set_point() is the only place `PT' is an lvalue in all of emacs.
1501    This function is called from set_buffer_point(), which is the function
1502    that the SET_PT and BUF_SET_PT macros expand into, and from the
1503    routines below that insert and delete text. (This is in cases where
1504    the point marker logically doesn't move but PT (being a byte index)
1505    needs to get adjusted.) */
1506
1507 /* Set point to a specified value.  This is used only when the value
1508    of point changes due to an insert or delete; it does not represent
1509    a conceptual change in point as a marker.  In particular, point is
1510    not crossing any interval boundaries, so there's no need to use the
1511    usual SET_PT macro.  In fact it would be incorrect to do so, because
1512    either the old or the new value of point is out of synch with the
1513    current set of intervals.  */
1514
1515 /* This gets called more than enough to make the function call
1516    overhead a significant factor so we've turned it into a macro. */
1517 #define JUST_SET_POINT(buf, bufpos, ind)        \
1518 do                                              \
1519 {                                               \
1520   buf->bufpt = (bufpos);                        \
1521   buf->pt = (ind);                              \
1522 } while (0)
1523
1524 /* Set a buffer's point. */
1525
1526 void
1527 set_buffer_point (struct buffer *buf, Bufpos bufpos, Bytind bytpos)
1528 {
1529   assert (bytpos >= BI_BUF_BEGV (buf) && bytpos <= BI_BUF_ZV (buf));
1530   if (bytpos == BI_BUF_PT (buf))
1531     return;
1532   JUST_SET_POINT (buf, bufpos, bytpos);
1533   MARK_POINT_CHANGED;
1534   assert (MARKERP (buf->point_marker));
1535   XMARKER (buf->point_marker)->memind =
1536     bytind_to_memind (buf, bytpos);
1537
1538   /* FSF makes sure that PT is not being set within invisible text.
1539      However, this is the wrong place for that check.  The check
1540      should happen only at the next redisplay. */
1541
1542   /* Some old coder said:
1543
1544      "If there were to be hooks which were run when point entered/left an
1545      extent, this would be the place to put them.
1546
1547      However, it's probably the case that such hooks should be implemented
1548      using a post-command-hook instead, to avoid running the hooks as a
1549      result of intermediate motion inside of save-excursions, for example."
1550
1551      I definitely agree with this.  PT gets moved all over the place
1552      and it would be a Bad Thing for any hooks to get called, both for
1553      the reason above and because many callers are not prepared for
1554      a GC within this function. --ben
1555    */
1556 }
1557
1558 /* Do the correct marker-like adjustment on MPOS (see below).  FROM, TO,
1559    and AMOUNT are as in adjust_markers().  If MPOS doesn't need to be
1560    adjusted, nothing will happen. */
1561 Memind
1562 do_marker_adjustment (Memind mpos, Memind from,
1563                       Memind to, Bytecount amount)
1564 {
1565   if (amount > 0)
1566     {
1567       if (mpos > to && mpos < to + amount)
1568         mpos = to + amount;
1569     }
1570   else
1571     {
1572       if (mpos > from + amount && mpos <= from)
1573         mpos = from + amount;
1574     }
1575   if (mpos > from && mpos <= to)
1576     mpos += amount;
1577   return mpos;
1578 }
1579
1580 /* Do the following:
1581
1582    (1) Add `amount' to the position of every marker in the current buffer
1583    whose current position is between `from' (exclusive) and `to' (inclusive).
1584
1585    (2) Also, any markers past the outside of that interval, in the direction
1586    of adjustment, are first moved back to the near end of the interval
1587    and then adjusted by `amount'.
1588
1589    This function is called in two different cases: when a region of
1590    characters adjacent to the gap is moved, causing the gap to shift
1591    to the other side of the region (in this case, `from' and `to'
1592    point to the old position of the region and there should be no
1593    markers affected by (2) because they would be inside the gap),
1594    or when a region of characters adjacent to the gap is wiped out,
1595    causing the gap to increase to include the region (in this case,
1596    `from' and `to' are the same, both pointing to the boundary
1597    between the gap and the deleted region, and there are no markers
1598    affected by (1)).
1599
1600    The reason for the use of exclusive and inclusive is that markers at
1601    the gap always sit at the beginning, not at the end.
1602 */
1603
1604 static void
1605 adjust_markers (struct buffer *buf, Memind from, Memind to,
1606                 Bytecount amount)
1607 {
1608   struct Lisp_Marker *m;
1609
1610   for (m = BUF_MARKERS (buf); m; m = marker_next (m))
1611     m->memind = do_marker_adjustment (m->memind, from, to, amount);
1612 }
1613
1614 /* Adjust markers whose insertion-type is t
1615    for an insertion of AMOUNT characters at POS.  */
1616
1617 static void
1618 adjust_markers_for_insert (struct buffer *buf, Memind ind, Bytecount amount)
1619 {
1620   struct Lisp_Marker *m;
1621
1622   for (m = BUF_MARKERS (buf); m; m = marker_next (m))
1623     {
1624       if (m->insertion_type && m->memind == ind)
1625         m->memind += amount;
1626     }
1627 }
1628
1629 \f
1630 /************************************************************************/
1631 /*                  Routines for dealing with the gap                   */
1632 /************************************************************************/
1633
1634 /* XEmacs requires an ANSI C compiler, and it damn well better have a
1635    working memmove() */
1636 #define GAP_USE_BCOPY
1637 #ifdef BCOPY_UPWARD_SAFE
1638 # undef BCOPY_UPWARD_SAFE
1639 #endif
1640 #ifdef BCOPY_DOWNWARD_SAFE
1641 # undef BCOPY_DOWNWARD_SAFE
1642 #endif
1643 #define BCOPY_UPWARD_SAFE 1
1644 #define BCOPY_DOWNWARD_SAFE 1
1645
1646 /* maximum amount of memory moved in a single chunk.  Increasing this
1647    value improves gap-motion efficiency but decreases QUIT responsiveness
1648    time.  Was 32000 but today's processors are faster and files are
1649    bigger.  --ben */
1650 #define GAP_MOVE_CHUNK 300000
1651
1652 /* Move the gap to POS, which is less than the current GPT. */
1653
1654 static void
1655 gap_left (struct buffer *buf, Bytind pos)
1656 {
1657   Bufbyte *to, *from;
1658   Bytecount i;
1659   Bytind new_s1;
1660
1661   from = BUF_GPT_ADDR (buf);
1662   to = from + BUF_GAP_SIZE (buf);
1663   new_s1 = BI_BUF_GPT (buf);
1664
1665   /* Now copy the characters.  To move the gap down,
1666      copy characters up.  */
1667
1668   while (1)
1669     {
1670       /* I gets number of characters left to copy.  */
1671       i = new_s1 - pos;
1672       if (i == 0)
1673         break;
1674       /* If a quit is requested, stop copying now.
1675          Change POS to be where we have actually moved the gap to.  */
1676       if (QUITP)
1677         {
1678           pos = new_s1;
1679           break;
1680         }
1681       /* Move at most GAP_MOVE_CHUNK chars before checking again for a quit. */
1682       if (i > GAP_MOVE_CHUNK)
1683         i = GAP_MOVE_CHUNK;
1684 #ifdef GAP_USE_BCOPY
1685       if (i >= 128
1686           /* bcopy is safe if the two areas of memory do not overlap
1687              or on systems where bcopy is always safe for moving upward.  */
1688           && (BCOPY_UPWARD_SAFE
1689               || to - from >= 128))
1690         {
1691           /* If overlap is not safe, avoid it by not moving too many
1692              characters at once.  */
1693           if (!BCOPY_UPWARD_SAFE && i > to - from)
1694             i = to - from;
1695           new_s1 -= i;
1696           from -= i, to -= i;
1697           memmove (to, from, i);
1698         }
1699       else
1700 #endif
1701         {
1702           new_s1 -= i;
1703           while (--i >= 0)
1704             *--to = *--from;
1705         }
1706     }
1707
1708   /* Adjust markers, and buffer data structure, to put the gap at POS.
1709      POS is where the loop above stopped, which may be what was specified
1710      or may be where a quit was detected.  */
1711   adjust_markers (buf, pos, BI_BUF_GPT (buf), BUF_GAP_SIZE (buf));
1712   adjust_extents (make_buffer (buf), pos, BI_BUF_GPT (buf),
1713                   BUF_GAP_SIZE (buf));
1714   SET_BI_BUF_GPT (buf, pos);
1715   SET_GAP_SENTINEL (buf);
1716 #ifdef ERROR_CHECK_EXTENTS
1717   sledgehammer_extent_check (make_buffer (buf));
1718 #endif
1719   QUIT;
1720 }
1721
1722 static void
1723 gap_right (struct buffer *buf, Bytind pos)
1724 {
1725   Bufbyte *to, *from;
1726   Bytecount i;
1727   Bytind new_s1;
1728
1729   to = BUF_GPT_ADDR (buf);
1730   from = to + BUF_GAP_SIZE (buf);
1731   new_s1 = BI_BUF_GPT (buf);
1732
1733   /* Now copy the characters.  To move the gap up,
1734      copy characters down.  */
1735
1736   while (1)
1737     {
1738       /* I gets number of characters left to copy.  */
1739       i = pos - new_s1;
1740       if (i == 0)
1741         break;
1742       /* If a quit is requested, stop copying now.
1743          Change POS to be where we have actually moved the gap to.  */
1744       if (QUITP)
1745         {
1746           pos = new_s1;
1747           break;
1748         }
1749       /* Move at most GAP_MOVE_CHUNK chars before checking again for a quit. */
1750       if (i > GAP_MOVE_CHUNK)
1751         i = GAP_MOVE_CHUNK;
1752 #ifdef GAP_USE_BCOPY
1753       if (i >= 128
1754           /* bcopy is safe if the two areas of memory do not overlap
1755              or on systems where bcopy is always safe for moving downward. */
1756           && (BCOPY_DOWNWARD_SAFE
1757               || from - to >= 128))
1758         {
1759           /* If overlap is not safe, avoid it by not moving too many
1760              characters at once.  */
1761           if (!BCOPY_DOWNWARD_SAFE && i > from - to)
1762             i = from - to;
1763           new_s1 += i;
1764           memmove (to, from, i);
1765           from += i, to += i;
1766         }
1767       else
1768 #endif
1769         {
1770           new_s1 += i;
1771           while (--i >= 0)
1772             *to++ = *from++;
1773         }
1774     }
1775
1776   {
1777     int gsize = BUF_GAP_SIZE (buf);
1778     adjust_markers (buf, BI_BUF_GPT (buf) + gsize, pos + gsize, - gsize);
1779     adjust_extents (make_buffer (buf), BI_BUF_GPT (buf) + gsize, pos + gsize,
1780                     - gsize);
1781     SET_BI_BUF_GPT (buf, pos);
1782     SET_GAP_SENTINEL (buf);
1783 #ifdef ERROR_CHECK_EXTENTS
1784     sledgehammer_extent_check (make_buffer (buf));
1785 #endif
1786   }
1787   if (pos == BI_BUF_Z (buf))
1788     {
1789       /* merge gap with end gap */
1790
1791       SET_BUF_GAP_SIZE (buf, BUF_GAP_SIZE (buf) + BUF_END_GAP_SIZE (buf));
1792       SET_BUF_END_GAP_SIZE (buf, 0);
1793       SET_END_SENTINEL (buf);
1794     }
1795
1796   QUIT;
1797 }
1798
1799 /* Move gap to position `pos'.
1800    Note that this can quit!  */
1801
1802 static void
1803 move_gap (struct buffer *buf, Bytind pos)
1804 {
1805   if (! BUF_BEG_ADDR (buf))
1806     abort ();
1807   if (pos < BI_BUF_GPT (buf))
1808     gap_left (buf, pos);
1809   else if (pos > BI_BUF_GPT (buf))
1810     gap_right (buf, pos);
1811 }
1812
1813 /* Merge the end gap into the gap */
1814
1815 static void
1816 merge_gap_with_end_gap (struct buffer *buf)
1817 {
1818   Lisp_Object tem;
1819   Bytind real_gap_loc;
1820   Bytecount old_gap_size;
1821   Bytecount increment;
1822
1823   increment = BUF_END_GAP_SIZE (buf);
1824   SET_BUF_END_GAP_SIZE (buf, 0);
1825
1826   if (increment > 0)
1827     {
1828       /* Prevent quitting in move_gap.  */
1829       tem = Vinhibit_quit;
1830       Vinhibit_quit = Qt;
1831
1832       real_gap_loc = BI_BUF_GPT (buf);
1833       old_gap_size = BUF_GAP_SIZE (buf);
1834
1835       /* Pretend the end gap is the gap */
1836       SET_BI_BUF_GPT (buf, BI_BUF_Z (buf) + BUF_GAP_SIZE (buf));
1837       SET_BUF_GAP_SIZE (buf, increment);
1838
1839       /* Move the new gap down to be consecutive with the end of the old one.
1840          This adjusts the markers properly too.  */
1841       gap_left (buf, real_gap_loc + old_gap_size);
1842
1843       /* Now combine the two into one large gap.  */
1844       SET_BUF_GAP_SIZE (buf, BUF_GAP_SIZE (buf) + old_gap_size);
1845       SET_BI_BUF_GPT (buf, real_gap_loc);
1846       SET_GAP_SENTINEL (buf);
1847
1848       /* We changed the total size of the buffer (including gap),
1849          so we need to fix up the end sentinel. */
1850       SET_END_SENTINEL (buf);
1851
1852       Vinhibit_quit = tem;
1853     }
1854 }
1855
1856 /* Make the gap INCREMENT bytes longer.  */
1857
1858 static void
1859 make_gap (struct buffer *buf, Bytecount increment)
1860 {
1861   Bufbyte *result;
1862   Lisp_Object tem;
1863   Bytind real_gap_loc;
1864   Bytecount old_gap_size;
1865
1866   /* If we have to get more space, get enough to last a while.  We use
1867      a geometric progession that saves on realloc space. */
1868   increment += 2000 + ((BI_BUF_Z (buf) - BI_BUF_BEG (buf)) / 8);
1869
1870   if (increment > BUF_END_GAP_SIZE (buf))
1871     {
1872       /* Don't allow a buffer size that won't fit in an int
1873          even if it will fit in a Lisp integer.
1874          That won't work because so many places use `int'.  */
1875
1876       if (BUF_Z (buf) - BUF_BEG (buf) + BUF_GAP_SIZE (buf) + increment
1877           > EMACS_INT_MAX)
1878         error ("Maximum buffer size exceeded");
1879
1880       result = BUFFER_REALLOC (buf->text->beg,
1881                                BI_BUF_Z (buf) - BI_BUF_BEG (buf) +
1882                                BUF_GAP_SIZE (buf) + increment +
1883                                BUF_END_SENTINEL_SIZE);
1884       if (result == 0)
1885         memory_full ();
1886
1887       SET_BUF_BEG_ADDR (buf, result);
1888     }
1889   else
1890     increment = BUF_END_GAP_SIZE (buf);
1891
1892   /* Prevent quitting in move_gap.  */
1893   tem = Vinhibit_quit;
1894   Vinhibit_quit = Qt;
1895
1896   real_gap_loc = BI_BUF_GPT (buf);
1897   old_gap_size = BUF_GAP_SIZE (buf);
1898
1899   /* Call the newly allocated space a gap at the end of the whole space.  */
1900   SET_BI_BUF_GPT (buf, BI_BUF_Z (buf) + BUF_GAP_SIZE (buf));
1901   SET_BUF_GAP_SIZE (buf, increment);
1902
1903   SET_BUF_END_GAP_SIZE (buf, 0);
1904
1905   /* Move the new gap down to be consecutive with the end of the old one.
1906      This adjusts the markers properly too.  */
1907   gap_left (buf, real_gap_loc + old_gap_size);
1908
1909   /* Now combine the two into one large gap.  */
1910   SET_BUF_GAP_SIZE (buf, BUF_GAP_SIZE (buf) + old_gap_size);
1911   SET_BI_BUF_GPT (buf, real_gap_loc);
1912   SET_GAP_SENTINEL (buf);
1913
1914   /* We changed the total size of the buffer (including gap),
1915      so we need to fix up the end sentinel. */
1916   SET_END_SENTINEL (buf);
1917
1918   Vinhibit_quit = tem;
1919 }
1920
1921 \f
1922 /************************************************************************/
1923 /*                     Before/after-change processing                   */
1924 /************************************************************************/
1925
1926 /* Those magic changes ... */
1927
1928 static void
1929 buffer_signal_changed_region (struct buffer *buf, Bufpos start,
1930                               Bufpos end)
1931 {
1932   /* The changed region is recorded as the number of unchanged
1933      characters from the beginning and from the end of the
1934      buffer.  This obviates much of the need of shifting the
1935      region around to compensate for insertions and deletions.
1936      */
1937   if (buf->changes->begin_unchanged < 0 ||
1938       buf->changes->begin_unchanged > start - BUF_BEG (buf))
1939     buf->changes->begin_unchanged = start - BUF_BEG (buf);
1940   if (buf->changes->end_unchanged < 0 ||
1941       buf->changes->end_unchanged > BUF_Z (buf) - end)
1942     buf->changes->end_unchanged = BUF_Z (buf) - end;
1943 }
1944
1945 void
1946 buffer_extent_signal_changed_region (struct buffer *buf, Bufpos start,
1947                                      Bufpos end)
1948 {
1949   if (buf->changes->begin_extent_unchanged < 0 ||
1950       buf->changes->begin_extent_unchanged > start - BUF_BEG (buf))
1951     buf->changes->begin_extent_unchanged = start - BUF_BEG (buf);
1952   if (buf->changes->end_extent_unchanged < 0 ||
1953       buf->changes->end_extent_unchanged > BUF_Z (buf) - end)
1954     buf->changes->end_extent_unchanged = BUF_Z (buf) - end;
1955 }
1956
1957 void
1958 buffer_reset_changes (struct buffer *buf)
1959 {
1960   buf->changes->begin_unchanged = -1;
1961   buf->changes->end_unchanged = -1;
1962   buf->changes->begin_extent_unchanged = -1;
1963   buf->changes->end_extent_unchanged = -1;
1964   buf->changes->newline_was_deleted = 0;
1965 }
1966
1967 static void
1968 signal_after_change (struct buffer *buf, Bufpos start, Bufpos orig_end,
1969                      Bufpos new_end);
1970
1971
1972 /* Call the after-change-functions according to the changes made so far
1973    and treat all further changes as single until the outermost
1974    multiple change exits.  This is called when the outermost multiple
1975    change exits and when someone is trying to make a change that violates
1976    the constraints specified in begin_multiple_change(), typically
1977    when nested multiple-change sessions occur. (There are smarter ways of
1978    dealing with nested multiple changes, but these rarely occur so there's
1979    probably no point in it.) */
1980
1981 /* #### This needs to keep track of what actually changed and only
1982    call the after-change functions on that region. */
1983
1984 static void
1985 cancel_multiple_change (struct buffer *buf)
1986 {
1987   /* This function can GC */
1988   /* Call the after-change-functions except when they've already been
1989      called or when there were no changes made to the buffer at all. */
1990   if (buf->text->changes->mc_begin != 0 &&
1991       buf->text->changes->mc_begin_signaled)
1992     {
1993       Bufpos real_mc_begin = buf->text->changes->mc_begin;
1994       buf->text->changes->mc_begin = 0;
1995
1996       signal_after_change (buf, real_mc_begin, buf->text->changes->mc_orig_end,
1997                            buf->text->changes->mc_new_end);
1998     }
1999   else
2000     {
2001       buf->text->changes->mc_begin = 0;
2002     }
2003 }
2004
2005 /* this is an unwind_protect, to ensure that the after-change-functions
2006    get called even in a non-local exit. */
2007
2008 static Lisp_Object
2009 multiple_change_finish_up (Lisp_Object buffer)
2010 {
2011   struct buffer *buf = XBUFFER (buffer);
2012
2013   /* #### I don't know whether or not it should even be possible to
2014      get here with a dead buffer (though given how it is called I can
2015      see how it might be).  In any case, there isn't time before 19.14
2016      to find out. */
2017   if (!BUFFER_LIVE_P (buf))
2018     return Qnil;
2019
2020   /* This function can GC */
2021   buf->text->changes->in_multiple_change = 0; /* do this first so that
2022                                                  errors in the after-change
2023                                                  functions don't mess things
2024                                                  up. */
2025   cancel_multiple_change (buf);
2026   return Qnil;
2027 }
2028
2029 /* Call this function when you're about to make a number of buffer changes
2030    that should be considered a single change. (e.g. `replace-match' calls
2031    this.) You need to specify the START and END of the region that is
2032    going to be changed so that the before-change-functions are called
2033    with the correct arguments.  The after-change region is calculated
2034    automatically, however, and if changes somehow or other happen outside
2035    of the specified region, that will also be handled correctly.
2036
2037    begin_multiple_change() returns a number (actually a specpdl depth)
2038    that you must pass to end_multiple_change() when you are done. */
2039
2040 int
2041 begin_multiple_change (struct buffer *buf, Bufpos start, Bufpos end)
2042 {
2043   /* This function can GC */
2044   int count = -1;
2045   if (buf->text->changes->in_multiple_change)
2046     {
2047       if (buf->text->changes->mc_begin != 0 &&
2048           (start < buf->text->changes->mc_begin ||
2049            end > buf->text->changes->mc_new_end))
2050         cancel_multiple_change (buf);
2051     }
2052   else
2053     {
2054       Lisp_Object buffer;
2055
2056       buf->text->changes->mc_begin = start;
2057       buf->text->changes->mc_orig_end = buf->text->changes->mc_new_end = end;
2058       buf->text->changes->mc_begin_signaled = 0;
2059       count = specpdl_depth ();
2060       XSETBUFFER (buffer, buf);
2061       record_unwind_protect (multiple_change_finish_up, buffer);
2062     }
2063   buf->text->changes->in_multiple_change++;
2064   /* We don't call before-change-functions until signal_before_change()
2065      is called, in case there is a read-only or other error. */
2066   return count;
2067 }
2068
2069 void
2070 end_multiple_change (struct buffer *buf, int count)
2071 {
2072   assert (buf->text->changes->in_multiple_change > 0);
2073   buf->text->changes->in_multiple_change--;
2074   if (!buf->text->changes->in_multiple_change)
2075     unbind_to (count, Qnil);
2076 }
2077
2078 static int inside_change_hook;
2079
2080 static Lisp_Object
2081 change_function_restore (Lisp_Object buffer)
2082 {
2083   Fset_buffer (buffer);
2084   inside_change_hook = 0;
2085   return Qnil;
2086 }
2087
2088 static int in_first_change;
2089
2090 static Lisp_Object
2091 first_change_hook_restore (Lisp_Object buffer)
2092 {
2093   Fset_buffer (buffer);
2094   in_first_change = 0;
2095   return Qnil;
2096 }
2097
2098 /* Signal an initial modification to the buffer.  */
2099
2100 static void
2101 signal_first_change (struct buffer *buf)
2102 {
2103   /* This function can GC */
2104   Lisp_Object buffer;
2105   XSETBUFFER (buffer, current_buffer);
2106
2107   if (!in_first_change)
2108     {
2109       if (!preparing_for_armageddon &&
2110           !NILP (symbol_value_in_buffer (Qfirst_change_hook, buffer)))
2111         {
2112           int speccount = specpdl_depth ();
2113           record_unwind_protect (first_change_hook_restore, buffer);
2114           set_buffer_internal (buf);
2115           in_first_change = 1;
2116           run_hook (Qfirst_change_hook);
2117           unbind_to (speccount, Qnil);
2118         }
2119     }
2120 }
2121
2122 /* Signal a change to the buffer immediately before it happens.
2123    START and END are the bounds of the text to be changed. */
2124
2125 static void
2126 signal_before_change (struct buffer *buf, Bufpos start, Bufpos end)
2127 {
2128   /* This function can GC */
2129   Lisp_Object buffer;
2130   XSETBUFFER (buffer, buf);
2131
2132   if (!inside_change_hook)
2133     {
2134       /* Are we in a multiple-change session? */
2135       if (buf->text->changes->in_multiple_change &&
2136           buf->text->changes->mc_begin != 0)
2137         {
2138           /* If we're violating the constraints of the session,
2139              call the after-change-functions as necessary for the
2140              changes already made and treat further changes as
2141              single. */
2142           if (start < buf->text->changes->mc_begin ||
2143               end > buf->text->changes->mc_new_end)
2144             cancel_multiple_change (buf);
2145           /* Do nothing if this is not the first change in the session. */
2146           else if (buf->text->changes->mc_begin_signaled)
2147             return;
2148           else
2149             {
2150               /* First time through; call the before-change-functions
2151                  specifying the entire region to be changed. (Note that
2152                  we didn't call before-change-functions in
2153                  begin_multiple_change() because the buffer might be
2154                  read-only, etc.) */
2155               start = buf->text->changes->mc_begin;
2156               end = buf->text->changes->mc_new_end;
2157             }
2158         }
2159
2160       /* If buffer is unmodified, run a special hook for that case.  */
2161       if (BUF_SAVE_MODIFF (buf) >= BUF_MODIFF (buf))
2162         signal_first_change (buf);
2163
2164       /* Now in any case run the before-change-functions if any.  */
2165
2166       if (!preparing_for_armageddon &&
2167           (!NILP (symbol_value_in_buffer (Qbefore_change_functions, buffer)) ||
2168            /* Obsolete, for compatibility */
2169            !NILP (symbol_value_in_buffer (Qbefore_change_function, buffer))))
2170         {
2171           int speccount = specpdl_depth ();
2172           record_unwind_protect (change_function_restore, Fcurrent_buffer ());
2173           set_buffer_internal (buf);
2174           inside_change_hook = 1;
2175           va_run_hook_with_args (Qbefore_change_functions, 2,
2176                                  make_int (start), make_int (end));
2177           /* Obsolete, for compatibility */
2178           va_run_hook_with_args (Qbefore_change_function, 2,
2179                                  make_int (start), make_int (end));
2180           unbind_to (speccount, Qnil);
2181         }
2182
2183       /* Only now do we indicate that the before-change-functions have
2184          been called, in case some function throws out. */
2185       buf->text->changes->mc_begin_signaled = 1;
2186     }
2187
2188   /* #### At this point we should map over extents calling
2189      modification-hooks, insert-before-hooks and insert-after-hooks
2190      of relevant extents */
2191 }
2192
2193 /* Signal a change immediately after it happens.
2194    START is the bufpos of the start of the changed text.
2195    ORIG_END is the bufpos of the end of the before-changed text.
2196    NEW_END is the bufpos of the end of the after-changed text.
2197  */
2198
2199 static void
2200 signal_after_change (struct buffer *buf, Bufpos start, Bufpos orig_end,
2201                      Bufpos new_end)
2202 {
2203   /* This function can GC */
2204   Lisp_Object buffer;
2205   XSETBUFFER (buffer, buf);
2206
2207   /* always do this. */
2208   buffer_signal_changed_region (buf, start, new_end);
2209   font_lock_maybe_update_syntactic_caches (buf, start, orig_end, new_end);
2210
2211   if (!inside_change_hook)
2212     {
2213       if (buf->text->changes->in_multiple_change &&
2214           buf->text->changes->mc_begin != 0)
2215         {
2216           assert (start >= buf->text->changes->mc_begin &&
2217                   start <= buf->text->changes->mc_new_end);
2218           assert (orig_end >= buf->text->changes->mc_begin &&
2219                   orig_end <= buf->text->changes->mc_new_end);
2220           buf->text->changes->mc_new_end += new_end - orig_end;
2221           return; /* after-change-functions signalled when all changes done */
2222         }
2223
2224       if (!preparing_for_armageddon &&
2225           (!NILP (symbol_value_in_buffer (Qafter_change_functions, buffer)) ||
2226            /* Obsolete, for compatibility */
2227            !NILP (symbol_value_in_buffer (Qafter_change_function, buffer))))
2228         {
2229           int speccount = specpdl_depth ();
2230           record_unwind_protect (change_function_restore, Fcurrent_buffer ());
2231           set_buffer_internal (buf);
2232           inside_change_hook = 1;
2233           /* The actual after-change functions take slightly
2234              different arguments than what we were passed. */
2235           va_run_hook_with_args (Qafter_change_functions, 3,
2236                                  make_int (start), make_int (new_end),
2237                                  make_int (orig_end - start));
2238           /* Obsolete, for compatibility */
2239           va_run_hook_with_args (Qafter_change_function, 3,
2240                                  make_int (start), make_int (new_end),
2241                                  make_int (orig_end - start));
2242           unbind_to (speccount, Qnil);
2243         }
2244     }
2245
2246   /* #### At this point we should map over extents calling
2247      some sort of modification hooks of relevant extents */
2248 }
2249
2250 /* Call this if you're about to change the region of BUFFER from START
2251    to END.  This checks the read-only properties of the region, calls
2252    the necessary modification hooks, and warns the next redisplay that
2253    it should pay attention to that area.  */
2254
2255 static void
2256 prepare_to_modify_buffer (struct buffer *buf, Bufpos start, Bufpos end,
2257                           int lockit)
2258 {
2259   /* This function can GC */
2260   /* dmoore - This function can also kill the buffer buf, the current
2261      buffer, and do anything it pleases.  So if you call it, be
2262      careful. */
2263   Lisp_Object buffer;
2264   struct gcpro gcpro1;
2265
2266   barf_if_buffer_read_only (buf, start, end);
2267
2268   /* if this is the first modification, see about locking the buffer's
2269      file */
2270   XSETBUFFER (buffer, buf);
2271   GCPRO1 (buffer);
2272   if (!NILP (buf->filename) && lockit &&
2273       BUF_SAVE_MODIFF (buf) >= BUF_MODIFF (buf))
2274     {
2275 #ifdef CLASH_DETECTION
2276       if (!NILP (buf->file_truename))
2277         /* Make binding buffer-file-name to nil effective.  */
2278         lock_file (buf->file_truename);
2279 #else
2280       /* At least warn if this file has changed on disk since it was visited.*/
2281       if (NILP (Fverify_visited_file_modtime (buffer))
2282           && !NILP (Ffile_exists_p (buf->filename)))
2283         call1_in_buffer (buf, intern ("ask-user-about-supersession-threat"),
2284                          buf->filename);
2285 #endif /* not CLASH_DETECTION */
2286     }
2287   UNGCPRO;
2288
2289   /* #### dmoore - is this reasonable in case of buf being killed above? */
2290   if (!BUFFER_LIVE_P (buf))
2291     return;
2292
2293   signal_before_change (buf, start, end);
2294
2295 #ifdef REGION_CACHE_NEEDS_WORK
2296   if (buf->newline_cache)
2297     invalidate_region_cache (buf,
2298                              buf->newline_cache,
2299                              start - BUF_BEG (buf), BUF_Z (buf) - end);
2300   if (buf->width_run_cache)
2301     invalidate_region_cache (buf,
2302                              buf->width_run_cache,
2303                              start - BUF_BEG (buf), BUF_Z (buf) - end);
2304 #endif
2305
2306 #if 0 /* FSFmacs */
2307   Vdeactivate_mark = Qt;
2308 #endif
2309
2310   buf->point_before_scroll = Qnil;
2311 }
2312
2313 \f
2314 /************************************************************************/
2315 /*                        Insertion of strings                          */
2316 /************************************************************************/
2317
2318 void
2319 fixup_internal_substring (CONST Bufbyte *nonreloc, Lisp_Object reloc,
2320                           Bytecount offset, Bytecount *len)
2321 {
2322   assert ((nonreloc && NILP (reloc)) || (!nonreloc && STRINGP (reloc)));
2323
2324   if (*len < 0)
2325     {
2326       if (nonreloc)
2327         *len = strlen ((CONST char *) nonreloc) - offset;
2328       else
2329         *len = XSTRING_LENGTH (reloc) - offset;
2330     }
2331 #ifdef ERROR_CHECK_BUFPOS
2332   assert (*len >= 0);
2333   if (STRINGP (reloc))
2334     {
2335       assert (offset >= 0 && offset <= XSTRING_LENGTH (reloc));
2336       assert (offset + *len <= XSTRING_LENGTH (reloc));
2337     }
2338 #endif
2339 }
2340
2341 /* Insert a string into BUF at Bufpos POS.  The string data comes
2342    from one of two sources: constant, non-relocatable data (specified
2343    in NONRELOC), or a Lisp string object (specified in RELOC), which
2344    is relocatable and may have extent data that needs to be copied
2345    into the buffer.  OFFSET and LENGTH specify the substring of the
2346    data that is actually to be inserted.  As a special case, if POS
2347    is -1, insert the string at point and move point to the end of the
2348    string.
2349
2350    Normally, markers at the insertion point end up before the
2351    inserted string.  If INSDEL_BEFORE_MARKERS is set in flags, however,
2352    they end up after the string.
2353
2354    INSDEL_NO_LOCKING is kludgy and is used when insert-file-contents is
2355    visiting a new file; it inhibits the locking checks normally done
2356    before modifying a buffer.  Similar checks were already done
2357    in the higher-level Lisp functions calling insert-file-contents. */
2358
2359 Charcount
2360 buffer_insert_string_1 (struct buffer *buf, Bufpos pos,
2361                         CONST Bufbyte *nonreloc, Lisp_Object reloc,
2362                         Bytecount offset, Bytecount length,
2363                         int flags)
2364 {
2365   /* This function can GC */
2366   struct gcpro gcpro1;
2367   Bytind ind;
2368   Charcount cclen;
2369   int move_point = 0;
2370
2371   /* Defensive steps just in case a buffer gets deleted and a calling
2372      function doesn't notice it. */
2373   if (!BUFFER_LIVE_P (buf))
2374     return 0;
2375
2376   fixup_internal_substring (nonreloc, reloc, offset, &length);
2377
2378   if (pos == -1)
2379     {
2380       pos = BUF_PT (buf);
2381       move_point = 1;
2382     }
2383
2384 #ifdef I18N3
2385   /* #### See the comment in print_internal().  If this buffer is marked
2386      as translatable, then Fgettext() should be called on obj if it
2387      is a string. */
2388 #endif
2389
2390   /* Make sure that point-max won't exceed the size of an emacs int. */
2391   if ((length + BUF_Z (buf)) > EMACS_INT_MAX)
2392     error ("Maximum buffer size exceeded");
2393
2394   /* theoretically not necessary -- caller should GCPRO */
2395   GCPRO1 (reloc);
2396
2397   prepare_to_modify_buffer (buf, pos, pos, !(flags & INSDEL_NO_LOCKING));
2398
2399   /* Defensive steps in case the before-change-functions fuck around */
2400   if (!BUFFER_LIVE_P (buf))
2401     {
2402       UNGCPRO;
2403       /* Bad bad pre-change function. */
2404       return 0;
2405     }
2406
2407   /* Make args be valid again.  prepare_to_modify_buffer() might have
2408      modified the buffer. */
2409   if (pos < BUF_BEGV (buf))
2410     pos = BUF_BEGV (buf);
2411   if (pos > BUF_ZV (buf))
2412     pos = BUF_ZV (buf);
2413
2414   /* string may have been relocated up to this point */
2415   if (STRINGP (reloc))
2416     nonreloc = XSTRING_DATA (reloc);
2417
2418   ind = bufpos_to_bytind (buf, pos);
2419   cclen = bytecount_to_charcount (nonreloc + offset, length);
2420
2421   if (ind != BI_BUF_GPT (buf))
2422     /* #### if debug-on-quit is invoked and the user changes the
2423        buffer, bad things can happen.  This is a rampant problem
2424        in Emacs. */
2425     move_gap (buf, ind); /* may QUIT */
2426   if (! GAP_CAN_HOLD_SIZE_P (buf, length))
2427     {
2428       if (BUF_END_GAP_SIZE (buf) >= length)
2429         merge_gap_with_end_gap (buf);
2430       else
2431         make_gap (buf, length - BUF_GAP_SIZE (buf));
2432     }
2433
2434   insert_invalidate_line_number_cache (buf, pos, nonreloc + offset, length);
2435
2436   record_insert (buf, pos, cclen);
2437   BUF_MODIFF (buf)++;
2438   MARK_BUFFERS_CHANGED;
2439
2440   /* string may have been relocated up to this point */
2441   if (STRINGP (reloc))
2442     nonreloc = XSTRING_DATA (reloc);
2443
2444   memcpy (BUF_GPT_ADDR (buf), nonreloc + offset, length);
2445
2446   SET_BUF_GAP_SIZE (buf, BUF_GAP_SIZE (buf) - length);
2447   SET_BI_BUF_GPT (buf, BI_BUF_GPT (buf) + length);
2448   SET_BOTH_BUF_ZV (buf, BUF_ZV (buf) + cclen, BI_BUF_ZV (buf) + length);
2449   SET_BOTH_BUF_Z (buf, BUF_Z (buf) + cclen, BI_BUF_Z (buf) + length);
2450   SET_GAP_SENTINEL (buf);
2451
2452 #ifdef MULE
2453   buffer_mule_signal_inserted_region (buf, pos, length, cclen);
2454 #endif
2455
2456   process_extents_for_insertion (make_buffer (buf), ind, length);
2457   /* We know the gap is at IND so the cast is OK. */
2458   adjust_markers_for_insert (buf, (Memind) ind, length);
2459
2460   /* Point logically doesn't move, but may need to be adjusted because
2461      it's a byte index.  point-marker doesn't change because it's a
2462      memory index. */
2463   if (BI_BUF_PT (buf) > ind)
2464     JUST_SET_POINT (buf, BUF_PT (buf) + cclen, BI_BUF_PT (buf) + length);
2465
2466   /* Well, point might move. */
2467   if (move_point)
2468     BI_BUF_SET_PT (buf, ind + length);
2469
2470   if (STRINGP (reloc))
2471     splice_in_string_extents (reloc, buf, ind, length, offset);
2472
2473   if (flags & INSDEL_BEFORE_MARKERS)
2474     {
2475       /* ind - 1 is correct because the FROM argument is exclusive.
2476          I formerly used DEC_BYTIND() but that caused problems at the
2477          beginning of the buffer. */
2478       adjust_markers (buf, ind - 1, ind, length);
2479     }
2480
2481   signal_after_change (buf, pos, pos, pos + cclen);
2482
2483   UNGCPRO;
2484
2485   return cclen;
2486 }
2487
2488
2489 /* The following functions are interfaces onto the above function,
2490    for inserting particular sorts of data.  In all the functions,
2491    BUF and POS specify the buffer and location where the insertion is
2492    to take place. (If POS is -1, text is inserted at point and point
2493    moves forward past the text.) FLAGS is as above. */
2494
2495 Charcount
2496 buffer_insert_raw_string_1 (struct buffer *buf, Bufpos pos,
2497                             CONST Bufbyte *nonreloc, Bytecount length,
2498                             int flags)
2499 {
2500   /* This function can GC */
2501   return buffer_insert_string_1 (buf, pos, nonreloc, Qnil, 0, length,
2502                                  flags);
2503 }
2504
2505 Charcount
2506 buffer_insert_lisp_string_1 (struct buffer *buf, Bufpos pos, Lisp_Object str,
2507                              int flags)
2508 {
2509   /* This function can GC */
2510   assert (STRINGP (str));
2511   return buffer_insert_string_1 (buf, pos, 0, str, 0,
2512                                  XSTRING_LENGTH (str),
2513                                  flags);
2514 }
2515
2516 /* Insert the null-terminated string S (in external format). */
2517
2518 Charcount
2519 buffer_insert_c_string_1 (struct buffer *buf, Bufpos pos, CONST char *s,
2520                           int flags)
2521 {
2522   /* This function can GC */
2523
2524   CONST char *translated = GETTEXT (s);
2525   return buffer_insert_string_1 (buf, pos, (CONST Bufbyte *) translated, Qnil,
2526                                  0, strlen (translated), flags);
2527 }
2528
2529 Charcount
2530 buffer_insert_emacs_char_1 (struct buffer *buf, Bufpos pos, Emchar ch,
2531                             int flags)
2532 {
2533   /* This function can GC */
2534   Bufbyte str[MAX_EMCHAR_LEN];
2535   Bytecount len;
2536
2537   len = set_charptr_emchar (str, ch);
2538   return buffer_insert_string_1 (buf, pos, str, Qnil, 0, len, flags);
2539 }
2540
2541 Charcount
2542 buffer_insert_c_char_1 (struct buffer *buf, Bufpos pos, char c,
2543                         int flags)
2544 {
2545   /* This function can GC */
2546   return buffer_insert_emacs_char_1 (buf, pos, (Emchar) (unsigned char) c,
2547                                      flags);
2548 }
2549
2550 Charcount
2551 buffer_insert_from_buffer_1 (struct buffer *buf, Bufpos pos,
2552                              struct buffer *buf2, Bufpos pos2,
2553                              Charcount length, int flags)
2554 {
2555   /* This function can GC */
2556   Lisp_Object str = make_string_from_buffer (buf2, pos2, length);
2557   return buffer_insert_string_1 (buf, pos, 0, str, 0,
2558                                  XSTRING_LENGTH (str), flags);
2559 }
2560
2561 \f
2562 /************************************************************************/
2563 /*                        Deletion of ranges                            */
2564 /************************************************************************/
2565
2566 /* Delete characters in buffer from FROM up to (but not including) TO.  */
2567
2568 void
2569 buffer_delete_range (struct buffer *buf, Bufpos from, Bufpos to, int flags)
2570 {
2571   /* This function can GC */
2572   Charcount numdel;
2573   Bytind bi_from, bi_to;
2574   Bytecount bc_numdel;
2575   EMACS_INT shortage;
2576   Lisp_Object bufobj;
2577
2578   /* Defensive steps just in case a buffer gets deleted and a calling
2579      function doesn't notice it. */
2580   if (!BUFFER_LIVE_P (buf))
2581     return;
2582
2583   /* Make args be valid */
2584   if (from < BUF_BEGV (buf))
2585     from = BUF_BEGV (buf);
2586   if (to > BUF_ZV (buf))
2587     to = BUF_ZV (buf);
2588   if ((numdel = to - from) <= 0)
2589     return;
2590
2591   prepare_to_modify_buffer (buf, from, to, !(flags & INSDEL_NO_LOCKING));
2592
2593   /* Defensive steps in case the before-change-functions fuck around */
2594   if (!BUFFER_LIVE_P (buf))
2595     /* Bad bad pre-change function. */
2596     return;
2597
2598   /* Make args be valid again.  prepare_to_modify_buffer() might have
2599      modified the buffer. */
2600   if (from < BUF_BEGV (buf))
2601     from = BUF_BEGV (buf);
2602   if (to > BUF_ZV (buf))
2603     to = BUF_ZV (buf);
2604   if ((numdel = to - from) <= 0)
2605     return;
2606
2607   XSETBUFFER (bufobj, buf);
2608
2609   /* Redisplay needs to know if a newline was in the deleted region.
2610      If we've already marked the changed region as having a deleted
2611      newline there is no use in performing the check. */
2612   if (!buf->changes->newline_was_deleted)
2613     {
2614       scan_buffer (buf, '\n', from, to, 1, &shortage, 1);
2615       if (!shortage)
2616         buf->changes->newline_was_deleted = 1;
2617     }
2618
2619   bi_from = bufpos_to_bytind (buf, from);
2620   bi_to = bufpos_to_bytind (buf, to);
2621   bc_numdel = bi_to - bi_from;
2622
2623   delete_invalidate_line_number_cache (buf, from, to);
2624
2625   if (to == BUF_Z (buf) &&
2626       bi_from > BI_BUF_GPT (buf))
2627     {
2628       /* avoid moving the gap just to delete from the bottom. */
2629
2630       record_delete (buf, from, numdel);
2631       BUF_MODIFF (buf)++;
2632       MARK_BUFFERS_CHANGED;
2633
2634       /* ### Point used to be modified here, but this causes problems with MULE,
2635          as point is used to calculate bytinds, and if the offset in bc_numdel causes
2636          point to move to a non first-byte location, causing some other function to
2637          throw an assertion in ASSERT_VALID_BYTIND. I've moved the code to right after
2638           the other movements and adjustments, but before the gap is moved.
2639           -- jh 970813 */
2640
2641       /* Detach any extents that are completely within the range [FROM, TO],
2642          if the extents are detachable.
2643
2644          This must come AFTER record_delete(), so that the appropriate extents
2645          will be present to be recorded, and BEFORE the gap size is increased,
2646          as otherwise we will be confused about where the extents end. */
2647       process_extents_for_deletion (bufobj, bi_from, bi_to, 0);
2648
2649       /* Relocate all markers pointing into the new, larger gap
2650          to point at the end of the text before the gap.  */
2651       adjust_markers (buf,
2652                       (bi_to + BUF_GAP_SIZE (buf)),
2653                       (bi_to + BUF_GAP_SIZE (buf)),
2654                       (- bc_numdel));
2655
2656       /* Relocate any extent endpoints just like markers. */
2657       adjust_extents_for_deletion (bufobj, bi_from, bi_to,
2658                                    BUF_GAP_SIZE (buf), bc_numdel, 0);
2659
2660       /* Relocate point as if it were a marker.  */
2661       if (bi_from < BI_BUF_PT (buf))
2662         {
2663           if (BI_BUF_PT (buf) < bi_to)
2664             JUST_SET_POINT (buf, from, bi_from);
2665           else
2666             JUST_SET_POINT (buf, BUF_PT (buf) - numdel,
2667                             BI_BUF_PT (buf) - bc_numdel);
2668         }
2669
2670       SET_BUF_END_GAP_SIZE (buf, BUF_END_GAP_SIZE (buf) + bc_numdel);
2671
2672       SET_BOTH_BUF_ZV (buf, BUF_ZV (buf) - numdel, BI_BUF_ZV (buf) - bc_numdel);
2673       SET_BOTH_BUF_Z (buf, BUF_Z (buf) - numdel, BI_BUF_Z (buf) - bc_numdel);
2674       SET_GAP_SENTINEL (buf);
2675     }
2676   else
2677     {
2678       /* Make sure the gap is somewhere in or next to what we are deleting.  */
2679       if (bi_to < BI_BUF_GPT (buf))
2680         gap_left (buf, bi_to);
2681       if (bi_from > BI_BUF_GPT (buf))
2682         gap_right (buf, bi_from);
2683
2684       record_delete (buf, from, numdel);
2685       BUF_MODIFF (buf)++;
2686       MARK_BUFFERS_CHANGED;
2687
2688       /* ### Point used to be modified here, but this causes problems with MULE,
2689          as point is used to calculate bytinds, and if the offset in bc_numdel causes
2690          point to move to a non first-byte location, causing some other function to
2691          throw an assertion in ASSERT_VALID_BYTIND. I've moved the code to right after
2692           the other movements and adjustments, but before the gap is moved.
2693           -- jh 970813 */
2694
2695       /* Detach any extents that are completely within the range [FROM, TO],
2696          if the extents are detachable.
2697
2698          This must come AFTER record_delete(), so that the appropriate extents
2699          will be present to be recorded, and BEFORE the gap size is increased,
2700          as otherwise we will be confused about where the extents end. */
2701       process_extents_for_deletion (bufobj, bi_from, bi_to, 0);
2702
2703       /* Relocate all markers pointing into the new, larger gap
2704          to point at the end of the text before the gap.  */
2705       adjust_markers (buf,
2706                       (bi_to + BUF_GAP_SIZE (buf)),
2707                       (bi_to + BUF_GAP_SIZE (buf)),
2708                       (- bc_numdel - BUF_GAP_SIZE (buf)));
2709
2710       /* Relocate any extent endpoints just like markers. */
2711       adjust_extents_for_deletion (bufobj, bi_from, bi_to, BUF_GAP_SIZE (buf),
2712                                    bc_numdel, BUF_GAP_SIZE (buf));
2713
2714       /* Relocate point as if it were a marker.  */
2715       if (bi_from < BI_BUF_PT (buf))
2716         {
2717           if (BI_BUF_PT (buf) < bi_to)
2718             JUST_SET_POINT (buf, from, bi_from);
2719           else
2720             JUST_SET_POINT (buf, BUF_PT (buf) - numdel,
2721                             BI_BUF_PT (buf) - bc_numdel);
2722         }
2723
2724       SET_BUF_GAP_SIZE (buf, BUF_GAP_SIZE (buf) + bc_numdel);
2725       SET_BOTH_BUF_ZV (buf, BUF_ZV (buf) - numdel, BI_BUF_ZV (buf) - bc_numdel);
2726       SET_BOTH_BUF_Z (buf, BUF_Z (buf) - numdel, BI_BUF_Z (buf) - bc_numdel);
2727       SET_BI_BUF_GPT (buf, bi_from);
2728       SET_GAP_SENTINEL (buf);
2729     }
2730
2731 #ifdef MULE
2732   buffer_mule_signal_deleted_region (buf, from, to, bi_from, bi_to);
2733 #endif
2734
2735 #ifdef ERROR_CHECK_EXTENTS
2736   sledgehammer_extent_check (bufobj);
2737 #endif
2738
2739   signal_after_change (buf, from, to, from);
2740 }
2741
2742 \f
2743 /************************************************************************/
2744 /*                    Replacement of characters                         */
2745 /************************************************************************/
2746
2747 /* Replace the character at POS in buffer B with CH. */
2748
2749 void
2750 buffer_replace_char (struct buffer *b, Bufpos pos, Emchar ch,
2751                      int not_real_change, int force_lock_check)
2752 {
2753   /* This function can GC */
2754   Bufbyte curstr[MAX_EMCHAR_LEN];
2755   Bufbyte newstr[MAX_EMCHAR_LEN];
2756   Bytecount curlen, newlen;
2757
2758   /* Defensive steps just in case a buffer gets deleted and a calling
2759      function doesn't notice it. */
2760   if (!BUFFER_LIVE_P (b))
2761     return;
2762
2763   curlen = BUF_CHARPTR_COPY_CHAR (b, pos, curstr);
2764   newlen = set_charptr_emchar (newstr, ch);
2765
2766   if (curlen == newlen)
2767     {
2768       /* then we can just replace the text. */
2769       prepare_to_modify_buffer (b, pos, pos + 1,
2770                                 !not_real_change || force_lock_check);
2771       /* Defensive steps in case the before-change-functions fuck around */
2772       if (!BUFFER_LIVE_P (b))
2773         /* Bad bad pre-change function. */
2774         return;
2775
2776       /* Make args be valid again.  prepare_to_modify_buffer() might have
2777          modified the buffer. */
2778       if (pos < BUF_BEGV (b))
2779         pos = BUF_BEGV (b);
2780       if (pos >= BUF_ZV (b))
2781         pos = BUF_ZV (b) - 1;
2782       if (pos < BUF_BEGV (b))
2783         /* no more characters in buffer! */
2784         return;
2785
2786       if (BUF_FETCH_CHAR (b, pos) == '\n')
2787         b->changes->newline_was_deleted = 1;
2788       MARK_BUFFERS_CHANGED;
2789       if (!not_real_change)
2790         {
2791           record_change (b, pos, 1);
2792           BUF_MODIFF (b)++;
2793         }
2794       memcpy (BUF_BYTE_ADDRESS (b, pos), newstr, newlen);
2795       signal_after_change (b, pos, pos + 1, pos + 1);
2796
2797       /* We do not have to adjust the Mule data; we just replaced a
2798          character with another of the same number of bytes. */
2799     }
2800   else
2801     {
2802       /*
2803        * Must implement as deletion followed by insertion.
2804        *
2805        * Make a note to move point forward later in the one situation
2806        * where it is needed, a delete/insert one position behind
2807        * point.  Point will drift backward by one position and stay
2808        * there otherwise.
2809        */
2810       int movepoint = (pos == BUF_PT (b) - 1);
2811
2812       buffer_delete_range (b, pos, pos + 1, 0);
2813       /* Defensive steps in case the before-change-functions fuck around */
2814       if (!BUFFER_LIVE_P (b))
2815         /* Bad bad pre-change function. */
2816         return;
2817
2818       /* Make args be valid again.  prepare_to_modify_buffer() might have
2819          modified the buffer. */
2820       if (pos < BUF_BEGV (b))
2821         pos = BUF_BEGV (b);
2822       if (pos >= BUF_ZV (b))
2823         pos = BUF_ZV (b) - 1;
2824       if (pos < BUF_BEGV (b))
2825         /* no more characters in buffer! */
2826         return;
2827       /*
2828        * -1 as the pos argument means to move point forward with the
2829        * insertion, which we must do if the deletion moved point
2830        * backward so that it now equals the insertion point.
2831        */
2832       buffer_insert_string_1 (b, (movepoint ? -1 : pos),
2833                               newstr, Qnil, 0, newlen, 0);
2834     }
2835 }
2836
2837 \f
2838 /************************************************************************/
2839 /*                            Other functions                           */
2840 /************************************************************************/
2841
2842 /* Make a string from a buffer.  This needs to take into account the gap,
2843    and add any necessary extents from the buffer. */
2844
2845 Lisp_Object
2846 make_string_from_buffer (struct buffer *buf, Bufpos pos, Charcount length)
2847 {
2848   /* This function can GC */
2849   Lisp_Object val;
2850   struct gcpro gcpro1;
2851   Bytind bi_ind;
2852   Bytecount bi_len;
2853
2854   bi_ind = bufpos_to_bytind (buf, pos);
2855   bi_len = bufpos_to_bytind (buf, pos + length) - bi_ind;
2856
2857   val = make_uninit_string (bi_len);
2858   GCPRO1 (val);
2859
2860   add_string_extents (val, buf, bi_ind, bi_len);
2861
2862   {
2863     Bytecount len1 = BI_BUF_GPT (buf) - bi_ind;
2864     Bufbyte *start1 = BI_BUF_BYTE_ADDRESS (buf, bi_ind);
2865     Bufbyte *dest = XSTRING_DATA (val);
2866
2867     if (len1 < 0)
2868       {
2869         /* Completely after gap */
2870         memcpy (dest, start1, bi_len);
2871       }
2872     else if (bi_len <= len1)
2873       {
2874         /* Completely before gap */
2875         memcpy (dest, start1, bi_len);
2876       }
2877     else
2878       {
2879         /* Spans gap */
2880         Bytind pos2 = bi_ind + len1;
2881         Bufbyte *start2 = BI_BUF_BYTE_ADDRESS (buf, pos2);
2882
2883         memcpy (dest, start1, len1);
2884         memcpy (dest + len1, start2, bi_len - len1);
2885       }
2886   }
2887
2888   UNGCPRO;
2889   return val;
2890 }
2891
2892 void
2893 barf_if_buffer_read_only (struct buffer *buf, Bufpos from, Bufpos to)
2894 {
2895   Lisp_Object buffer;
2896   Lisp_Object iro;
2897
2898   XSETBUFFER (buffer, buf);
2899  back:
2900   iro = (buf == current_buffer ? Vinhibit_read_only :
2901          symbol_value_in_buffer (Qinhibit_read_only, buffer));
2902   if (!LISTP (iro))
2903     return;
2904   if (NILP (iro) && !NILP (buf->read_only))
2905     {
2906       Fsignal (Qbuffer_read_only, (list1 (buffer)));
2907       goto back;
2908     }
2909   if (from > 0)
2910     {
2911       if (to < 0)
2912         to = from;
2913       verify_extent_modification (buffer,
2914                                   bufpos_to_bytind (buf, from),
2915                                   bufpos_to_bytind (buf, to),
2916                                   iro);
2917     }
2918 }
2919
2920 void
2921 find_charsets_in_bufbyte_string (unsigned char *charsets, CONST Bufbyte *str,
2922                                  Bytecount len)
2923 {
2924 #ifndef MULE
2925   /* Telescope this. */
2926   charsets[0] = 1;
2927 #else
2928   CONST Bufbyte *strend = str + len;
2929   memset (charsets, 0, NUM_LEADING_BYTES);
2930
2931   while (str < strend)
2932     {
2933       charsets[CHAR_LEADING_BYTE (charptr_emchar (str)) - 128] = 1;
2934       INC_CHARPTR (str);
2935     }
2936 #endif
2937 }
2938
2939 void
2940 find_charsets_in_emchar_string (unsigned char *charsets, CONST Emchar *str,
2941                                 Charcount len)
2942 {
2943 #ifndef MULE
2944   /* Telescope this. */
2945   charsets[0] = 1;
2946 #else
2947   int i;
2948
2949   memset (charsets, 0, NUM_LEADING_BYTES);
2950   for (i = 0; i < len; i++)
2951     {
2952       charsets[CHAR_LEADING_BYTE (str[i]) - 128] = 1;
2953     }
2954 #endif
2955 }
2956
2957 int
2958 bufbyte_string_displayed_columns (CONST Bufbyte *str, Bytecount len)
2959 {
2960   int cols = 0;
2961   CONST Bufbyte *end = str + len;
2962
2963   while (str < end)
2964     {
2965 #ifdef MULE
2966       Emchar ch = charptr_emchar (str);
2967       cols += XCHARSET_COLUMNS (CHAR_CHARSET (ch));
2968 #else
2969       cols++;
2970 #endif
2971       INC_CHARPTR (str);
2972     }
2973
2974   return cols;
2975 }
2976
2977 int
2978 emchar_string_displayed_columns (CONST Emchar *str, Charcount len)
2979 {
2980 #ifdef MULE
2981   int cols = 0;
2982   int i;
2983
2984   for (i = 0; i < len; i++)
2985     cols += XCHARSET_COLUMNS (CHAR_CHARSET (str[i]));
2986
2987   return cols;
2988 #else  /* not MULE */
2989   return len;
2990 #endif
2991 }
2992
2993 /* NOTE: Does not reset the Dynarr. */
2994
2995 void
2996 convert_bufbyte_string_into_emchar_dynarr (CONST Bufbyte *str, Bytecount len,
2997                                            Emchar_dynarr *dyn)
2998 {
2999   CONST Bufbyte *strend = str + len;
3000
3001   while (str < strend)
3002     {
3003       Emchar ch = charptr_emchar (str);
3004       Dynarr_add (dyn, ch);
3005       INC_CHARPTR (str);
3006     }
3007 }
3008
3009 int
3010 convert_bufbyte_string_into_emchar_string (CONST Bufbyte *str, Bytecount len,
3011                                            Emchar *arr)
3012 {
3013   CONST Bufbyte *strend = str + len;
3014   Charcount newlen = 0;
3015   while (str < strend)
3016     {
3017       Emchar ch = charptr_emchar (str);
3018       arr[newlen++] = ch;
3019       INC_CHARPTR (str);
3020     }
3021   return newlen;
3022 }
3023
3024 /* Convert an array of Emchars into the equivalent string representation.
3025    Store into the given Bufbyte dynarr.  Does not reset the dynarr.
3026    Does not add a terminating zero. */
3027
3028 void
3029 convert_emchar_string_into_bufbyte_dynarr (Emchar *arr, int nels,
3030                                           Bufbyte_dynarr *dyn)
3031 {
3032   Bufbyte str[MAX_EMCHAR_LEN];
3033   int i;
3034
3035   for (i = 0; i < nels; i++)
3036     {
3037       Bytecount len = set_charptr_emchar (str, arr[i]);
3038       Dynarr_add_many (dyn, str, len);
3039     }
3040 }
3041
3042 /* Convert an array of Emchars into the equivalent string representation.
3043    Malloc the space needed for this and return it.  If LEN_OUT is not a
3044    NULL pointer, store into LEN_OUT the number of Bufbytes in the
3045    malloc()ed string.  Note that the actual number of Bufbytes allocated
3046    is one more than this: the returned string is zero-terminated. */
3047
3048 Bufbyte *
3049 convert_emchar_string_into_malloced_string (Emchar *arr, int nels,
3050                                            Bytecount *len_out)
3051 {
3052   /* Damn zero-termination. */
3053   Bufbyte *str = (Bufbyte *) alloca (nels * MAX_EMCHAR_LEN + 1);
3054   Bufbyte *strorig = str;
3055   Bytecount len;
3056
3057   int i;
3058
3059   for (i = 0; i < nels; i++)
3060     str += set_charptr_emchar (str, arr[i]);
3061   *str = '\0';
3062   len = str - strorig;
3063   str = (Bufbyte *) xmalloc (1 + len);
3064   memcpy (str, strorig, 1 + len);
3065   if (len_out)
3066     *len_out = len;
3067   return str;
3068 }
3069
3070 \f
3071 /************************************************************************/
3072 /*                            initialization                            */
3073 /************************************************************************/
3074
3075 void
3076 vars_of_insdel (void)
3077 {
3078   int i;
3079
3080   inside_change_hook = 0;
3081   in_first_change = 0;
3082
3083   for (i = 0; i <= MAX_BYTIND_GAP_SIZE_3; i++)
3084     three_to_one_table[i] = i / 3;
3085 }
3086
3087 void
3088 init_buffer_text (struct buffer *b, int indirect_p)
3089 {
3090   if (!indirect_p)
3091     {
3092       SET_BUF_GAP_SIZE (b, 20);
3093       BUFFER_ALLOC (b->text->beg, BUF_GAP_SIZE (b) + BUF_END_SENTINEL_SIZE);
3094       if (! BUF_BEG_ADDR (b))
3095         memory_full ();
3096
3097       SET_BUF_END_GAP_SIZE (b, 0);
3098       SET_BI_BUF_GPT (b, 1);
3099       SET_BOTH_BUF_Z (b, 1, 1);
3100       SET_GAP_SENTINEL (b);
3101       SET_END_SENTINEL (b);
3102 #ifdef MULE
3103       {
3104         int i;
3105
3106         b->text->mule_bufmin = b->text->mule_bufmax = 1;
3107         b->text->mule_bytmin = b->text->mule_bytmax = 1;
3108         b->text->mule_shifter = 0;
3109         b->text->mule_three_p = 0;
3110
3111         for (i = 0; i < 16; i++)
3112           {
3113             b->text->mule_bufpos_cache[i] = 1;
3114             b->text->mule_bytind_cache[i] = 1;
3115           }
3116       }
3117 #endif /* MULE */
3118
3119       BUF_MODIFF (b) = 1;
3120       BUF_SAVE_MODIFF (b) = 1;
3121
3122       JUST_SET_POINT (b, 1, 1);
3123       SET_BOTH_BUF_BEGV (b, 1, 1);
3124       SET_BOTH_BUF_ZV (b, 1, 1);
3125
3126       b->text->changes = xnew_and_zero (struct buffer_text_change_data);
3127     }
3128   else
3129     {
3130       JUST_SET_POINT (b, BUF_PT (b->base_buffer), BI_BUF_PT (b->base_buffer));
3131       SET_BOTH_BUF_BEGV (b, BUF_BEGV (b->base_buffer),
3132                          BI_BUF_BEGV (b->base_buffer));
3133       SET_BOTH_BUF_ZV (b, BUF_ZV (b->base_buffer),
3134                          BI_BUF_ZV (b->base_buffer));
3135     }
3136
3137   b->changes = xnew_and_zero (struct each_buffer_change_data);
3138   BUF_FACECHANGE (b) = 1;
3139
3140 #ifdef REGION_CACHE_NEEDS_WORK
3141   b->newline_cache = 0;
3142   b->width_run_cache = 0;
3143   b->width_table = Qnil;
3144 #endif
3145 }
3146
3147 void
3148 uninit_buffer_text (struct buffer *b, int indirect_p)
3149 {
3150   if (!indirect_p)
3151     {
3152       BUFFER_FREE (b->text->beg);
3153       xfree (b->text->changes);
3154     }
3155   xfree (b->changes);
3156
3157 #ifdef REGION_CACHE_NEEDS_WORK
3158   if (b->newline_cache)
3159     {
3160       free_region_cache (b->newline_cache);
3161       b->newline_cache = 0;
3162     }
3163   if (b->width_run_cache)
3164     {
3165       free_region_cache (b->width_run_cache);
3166       b->width_run_cache = 0;
3167     }
3168   b->width_table = Qnil;
3169 #endif
3170 }