1: /* Buffer insertion/deletion and gap motion for GNU Emacs.
    2:    Copyright (C) 1985, 1986, 1993, 1994, 1995, 1997, 1998, 1999, 2000, 2001,
    3:                  2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
    4: 
    5: This file is part of GNU Emacs.
    6: 
    7: GNU Emacs is free software; you can redistribute it and/or modify
    8: it under the terms of the GNU General Public License as published by
    9: the Free Software Foundation; either version 2, or (at your option)
   10: any later version.
   11: 
   12: GNU Emacs is distributed in the hope that it will be useful,
   13: but WITHOUT ANY WARRANTY; without even the implied warranty of
   14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   15: GNU General Public License for more details.
   16: 
   17: You should have received a copy of the GNU General Public License
   18: along with GNU Emacs; see the file COPYING.  If not, write to
   19: the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
   20: Boston, MA 02110-1301, USA.  */
   21: 
   22: 
   23: #include <config.h>
   24: #include "lisp.h"
   25: #include "intervals.h"
   26: #include "buffer.h"
   27: #include "charset.h"
   28: #include "window.h"
   29: #include "blockinput.h"
   30: #include "region-cache.h"
   31: 
   32: #ifndef NULL
   33: #define NULL 0
   34: #endif
   35: 
   36: static void insert_from_string_1 P_ ((Lisp_Object, int, int, int, int, int, int));
   37: static void insert_from_buffer_1 ();
   38: static void gap_left P_ ((int, int, int));
   39: static void gap_right P_ ((int, int));
   40: static void adjust_markers_gap_motion P_ ((int, int, int));
   41: static void adjust_markers_for_insert P_ ((int, int, int, int, int));
   42: void        adjust_markers_for_delete P_ ((int, int, int, int));
   43: static void adjust_markers_for_replace P_ ((int, int, int, int, int, int));
   44: static void adjust_point P_ ((int, int));
   45: 
   46: Lisp_Object Fcombine_after_change_execute ();
   47: 
   48: /* Non-nil means don't call the after-change-functions right away,
   49:    just record an element in Vcombine_after_change_calls_list.  */
   50: Lisp_Object Vcombine_after_change_calls;
   51: 
   52: /* List of elements of the form (BEG-UNCHANGED END-UNCHANGED CHANGE-AMOUNT)
   53:    describing changes which happened while combine_after_change_calls
   54:    was nonzero.  We use this to decide how to call them
   55:    once the deferral ends.
   56: 
   57:    In each element.
   58:    BEG-UNCHANGED is the number of chars before the changed range.
   59:    END-UNCHANGED is the number of chars after the changed range,
   60:    and CHANGE-AMOUNT is the number of characters inserted by the change
   61:    (negative for a deletion).  */
   62: Lisp_Object combine_after_change_list;
   63: 
   64: /* Buffer which combine_after_change_list is about.  */
   65: Lisp_Object combine_after_change_buffer;
   66: 
   67: Lisp_Object Qinhibit_modification_hooks;
   68: 
   69: ^L
   70: /* Check all markers in the current buffer, looking for something invalid.  */
   71: 
   72: static int check_markers_debug_flag;
   73: 
   74: #define CHECK_MARKERS()                         \
   75:   if (check_markers_debug_flag)                 \
   76:     check_markers ();                           \
   77:   else
   78: 
   79: void
   80: check_markers ()
   81: {
   82:   register struct Lisp_Marker *tail;
   83:   int multibyte = ! NILP (current_buffer->enable_multibyte_characters);
   84: 
   85:   for (tail = BUF_MARKERS (current_buffer); tail; tail = tail->next)
   86:     {
   87:       if (tail->buffer->text != current_buffer->text)
   88:         abort ();
   89:       if (tail->charpos > Z)
   90:         abort ();
   91:       if (tail->bytepos > Z_BYTE)
   92:         abort ();
   93:       if (multibyte && ! CHAR_HEAD_P (FETCH_BYTE (tail->bytepos)))
   94:         abort ();
   95:     }
   96: }
   97: ^L
   98: /* Move gap to position CHARPOS.
   99:    Note that this can quit!  */
  100: 
  101: void
  102: move_gap (charpos)
  103:      int charpos;
  104: {
  105:   move_gap_both (charpos, charpos_to_bytepos (charpos));
  106: }
  107: 
  108: /* Move gap to byte position BYTEPOS, which is also char position CHARPOS.
  109:    Note that this can quit!  */
  110: 
  111: void
  112: move_gap_both (charpos, bytepos)
  113:      int charpos, bytepos;
  114: {
  115:   if (bytepos < GPT_BYTE)
  116:     gap_left (charpos, bytepos, 0);
  117:   else if (bytepos > GPT_BYTE)
  118:     gap_right (charpos, bytepos);
  119: }
  120: 
  121: /* Move the gap to a position less than the current GPT.
  122:    BYTEPOS describes the new position as a byte position,
  123:    and CHARPOS is the corresponding char position.
  124:    If NEWGAP is nonzero, then don't update beg_unchanged and end_unchanged.  */
  125: 
  126: static void
  127: gap_left (charpos, bytepos, newgap)
  128:      register int charpos, bytepos;
  129:      int newgap;
  130: {
  131:   register unsigned char *to, *from;
  132:   register int i;
  133:   int new_s1;
  134: 
  135:   if (!newgap)
  136:     BUF_COMPUTE_UNCHANGED (current_buffer, charpos, GPT);
  137: 
  138:   i = GPT_BYTE;
  139:   to = GAP_END_ADDR;
  140:   from = GPT_ADDR;
  141:   new_s1 = GPT_BYTE;
  142: 
  143:   /* Now copy the characters.  To move the gap down,
  144:      copy characters up.  */
  145: 
  146:   while (1)
  147:     {
  148:       /* I gets number of characters left to copy.  */
  149:       i = new_s1 - bytepos;
  150:       if (i == 0)
  151:         break;
  152:       /* If a quit is requested, stop copying now.
  153:          Change BYTEPOS to be where we have actually moved the gap to.  */
  154:       if (QUITP)
  155:         {
  156:           bytepos = new_s1;
  157:           charpos = BYTE_TO_CHAR (bytepos);
  158:           break;
  159:         }
  160:       /* Move at most 32000 chars before checking again for a quit.  */
  161:       if (i > 32000)
  162:         i = 32000;
  163: #ifdef GAP_USE_BCOPY
  164:       if (i >= 128
  165:           /* bcopy is safe if the two areas of memory do not overlap
  166:              or on systems where bcopy is always safe for moving upward.  */
  167:           && (BCOPY_UPWARD_SAFE
  168:               || to - from >= 128))
  169:         {
  170:           /* If overlap is not safe, avoid it by not moving too many
  171:              characters at once.  */
  172:           if (!BCOPY_UPWARD_SAFE && i > to - from)
  173:             i = to - from;
  174:           new_s1 -= i;
  175:           from -= i, to -= i;
  176:           bcopy (from, to, i);
  177:         }
  178:       else
  179: #endif
  180:         {
  181:           new_s1 -= i;
  182:           while (--i >= 0)
  183:             *--to = *--from;
  184:         }
  185:     }
  186: 
  187:   /* Adjust markers, and buffer data structure, to put the gap at BYTEPOS.
  188:      BYTEPOS is where the loop above stopped, which may be what was specified
  189:      or may be where a quit was detected.  */
  190:   adjust_markers_gap_motion (bytepos, GPT_BYTE, GAP_SIZE);
  191:   GPT_BYTE = bytepos;
  192:   GPT = charpos;
  193:   if (bytepos < charpos)
  194:     abort ();
  195:   if (GAP_SIZE > 0) *(GPT_ADDR) = 0; /* Put an anchor.  */
  196:   QUIT;
  197: }
  198: 
  199: /* Move the gap to a position greater than than the current GPT.
  200:    BYTEPOS describes the new position as a byte position,
  201:    and CHARPOS is the corresponding char position.  */
  202: 
  203: static void
  204: gap_right (charpos, bytepos)
  205:      register int charpos, bytepos;
  206: {
  207:   register unsigned char *to, *from;
  208:   register int i;
  209:   int new_s1;
  210: 
  211:   BUF_COMPUTE_UNCHANGED (current_buffer, charpos, GPT);
  212: 
  213:   i = GPT_BYTE;
  214:   from = GAP_END_ADDR;
  215:   to = GPT_ADDR;
  216:   new_s1 = GPT_BYTE;
  217: 
  218:   /* Now copy the characters.  To move the gap up,
  219:      copy characters down.  */
  220: 
  221:   while (1)
  222:     {
  223:       /* I gets number of characters left to copy.  */
  224:       i = bytepos - new_s1;
  225:       if (i == 0)
  226:         break;
  227:       /* If a quit is requested, stop copying now.
  228:          Change BYTEPOS to be where we have actually moved the gap to.  */
  229:       if (QUITP)
  230:         {
  231:           bytepos = new_s1;
  232:           charpos = BYTE_TO_CHAR (bytepos);
  233:           break;
  234:         }
  235:       /* Move at most 32000 chars before checking again for a quit.  */
  236:       if (i > 32000)
  237:         i = 32000;
  238: #ifdef GAP_USE_BCOPY
  239:       if (i >= 128
  240:           /* bcopy is safe if the two areas of memory do not overlap
  241:              or on systems where bcopy is always safe for moving downward.  */
  242:           && (BCOPY_DOWNWARD_SAFE
  243:               || from - to >= 128))
  244:         {
  245:           /* If overlap is not safe, avoid it by not moving too many
  246:              characters at once.  */
  247:           if (!BCOPY_DOWNWARD_SAFE && i > from - to)
  248:             i = from - to;
  249:           new_s1 += i;
  250:           bcopy (from, to, i);
  251:           from += i, to += i;
  252:         }
  253:       else
  254: #endif
  255:         {
  256:           new_s1 += i;
  257:           while (--i >= 0)
  258:             *to++ = *from++;
  259:         }
  260:     }
  261: 
  262:   adjust_markers_gap_motion (GPT_BYTE + GAP_SIZE, bytepos + GAP_SIZE,
  263:                              - GAP_SIZE);
  264:   GPT = charpos;
  265:   GPT_BYTE = bytepos;
  266:   if (bytepos < charpos)
  267:     abort ();
  268:   if (GAP_SIZE > 0) *(GPT_ADDR) = 0; /* Put an anchor.  */
  269:   QUIT;
  270: }
  271: ^L
  272: /* Add AMOUNT to the byte position of every marker in the current buffer
  273:    whose current byte position is between FROM (exclusive) and TO (inclusive).
  274: 
  275:    Also, any markers past the outside of that interval, in the direction
  276:    of adjustment, are first moved back to the near end of the interval
  277:    and then adjusted by AMOUNT.
  278: 
  279:    When the latter adjustment is done, if AMOUNT is negative,
  280:    we record the adjustment for undo.  (This case happens only for
  281:    deletion.)
  282: 
  283:    The markers' character positions are not altered,
  284:    because gap motion does not affect character positions.  */
  285: 
  286: int adjust_markers_test;
  287: 
  288: static void
  289: adjust_markers_gap_motion (from, to, amount)
  290:      register int from, to, amount;
  291: {
  292:   /* Now that a marker has a bytepos, not counting the gap,
  293:      nothing needs to be done here.  */
  294: #if 0
  295:   Lisp_Object marker;
  296:   register struct Lisp_Marker *m;
  297:   register int mpos;
  298: 
  299:   marker = BUF_MARKERS (current_buffer);
  300: 
  301:   while (!NILP (marker))
  302:     {
  303:       m = XMARKER (marker);
  304:       mpos = m->bytepos;
  305:       if (amount > 0)
  306:         {
  307:           if (mpos > to && mpos < to + amount)
  308:             {
  309:               if (adjust_markers_test)
  310:                 abort ();
  311:               mpos = to + amount;
  312:             }
  313:         }
  314:       else
  315:         {
  316:           /* Here's the case where a marker is inside text being deleted.
  317:              AMOUNT can be negative for gap motion, too,
  318:              but then this range contains no markers.  */
  319:           if (mpos > from + amount && mpos <= from)
  320:             {
  321:               if (adjust_markers_test)
  322:                 abort ();
  323:               mpos = from + amount;
  324:             }
  325:         }
  326:       if (mpos > from && mpos <= to)
  327:         mpos += amount;
  328:       m->bufpos = mpos;
  329:       marker = m->chain;
  330:     }
  331: #endif
  332: }
  333: ^L
  334: /* Adjust all markers for a deletion
  335:    whose range in bytes is FROM_BYTE to TO_BYTE.
  336:    The range in charpos is FROM to TO.
  337: 
  338:    This function assumes that the gap is adjacent to
  339:    or inside of the range being deleted.  */
  340: 
  341: void
  342: adjust_markers_for_delete (from, from_byte, to, to_byte)
  343:      register int from, from_byte, to, to_byte;
  344: {
  345:   Lisp_Object marker;
  346:   register struct Lisp_Marker *m;
  347:   register int charpos;
  348: 
  349:   for (m = BUF_MARKERS (current_buffer); m; m = m->next)
  350:     {
  351:       charpos = m->charpos;
  352: 
  353:       if (charpos > Z)
  354:         abort ();
  355: 
  356:       /* If the marker is after the deletion,
  357:          relocate by number of chars / bytes deleted.  */
  358:       if (charpos > to)
  359:         {
  360:           m->charpos -= to - from;
  361:           m->bytepos -= to_byte - from_byte;
  362:         }
  363:       /* Here's the case where a marker is inside text being deleted.  */
  364:       else if (charpos > from)
  365:         {
  366:           if (! m->insertion_type)
  367:             { /* Normal markers will end up at the beginning of the
  368:                re-inserted text after undoing a deletion, and must be
  369:                adjusted to move them to the correct place.  */
  370:               XSETMISC (marker, m);
  371:             record_marker_adjustment (marker, from - charpos);
  372:             }
  373:           else if (charpos < to)
  374:             { /* Before-insertion markers will automatically move forward
  375:                upon re-inserting the deleted text, so we have to arrange
  376:                for them to move backward to the correct position.  */
  377:               XSETMISC (marker, m);
  378:             record_marker_adjustment (marker, charpos - to);
  379:             }
  380:           m->charpos = from;
  381:           m->bytepos = from_byte;
  382:         }
  383:       /* Here's the case where a before-insertion marker is immediately
  384:          before the deleted region.  */
  385:       else if (charpos == from && m->insertion_type)
  386:         {
  387:           /* Undoing the change uses normal insertion, which will
  388:              incorrectly make MARKER move forward, so we arrange for it
  389:              to then move backward to the correct place at the beginning
  390:              of the deleted region.  */
  391:           XSETMISC (marker, m);
  392:           record_marker_adjustment (marker, to - from);
  393:         }
  394:     }
  395: }
  396: 
  397: ^L
  398: /* Adjust markers for an insertion that stretches from FROM / FROM_BYTE
  399:    to TO / TO_BYTE.  We have to relocate the charpos of every marker
  400:    that points after the insertion (but not their bytepos).
  401: 
  402:    When a marker points at the insertion point,
  403:    we advance it if either its insertion-type is t
  404:    or BEFORE_MARKERS is true.  */
  405: 
  406: static void
  407: adjust_markers_for_insert (from, from_byte, to, to_byte, before_markers)
  408:      register int from, from_byte, to, to_byte;
  409:      int before_markers;
  410: {
  411:   struct Lisp_Marker *m;
  412:   int adjusted = 0;
  413:   int nchars = to - from;
  414:   int nbytes = to_byte - from_byte;
  415: 
  416:   for (m = BUF_MARKERS (current_buffer); m; m = m->next)
  417:     {
  418:       /* In a single-byte buffer, a marker's two positions must be
  419:          equal.  */
  420:       if (Z == Z_BYTE)
  421:         {
  422:           if (m->charpos != m->bytepos)
  423:             abort ();
  424:         }
  425: 
  426:       if (m->bytepos == from_byte)
  427:         {
  428:           if (m->insertion_type || before_markers)
  429:             {
  430:               m->bytepos = to_byte;
  431:               m->charpos = to;
  432:               if (m->insertion_type)
  433:                 adjusted = 1;
  434:             }
  435:         }
  436:       else if (m->bytepos > from_byte)
  437:         {
  438:           m->bytepos += nbytes;
  439:           m->charpos += nchars;
  440:         }
  441:     }
  442: 
  443:   /* Adjusting only markers whose insertion-type is t may result in
  444:      - disordered start and end in overlays, and 
  445:      - disordered overlays in the slot `overlays_before' of current_buffer.  */
  446:   if (adjusted)
  447:     {
  448:       fix_start_end_in_overlays(from, to);
  449:       fix_overlays_before (current_buffer, from, to);
  450:     }
  451: }
  452: 
  453: /* Adjust point for an insertion of NBYTES bytes, which are NCHARS characters.
  454: 
  455:    This is used only when the value of point changes due to an insert
  456:    or delete; it does not represent a conceptual change in point as a
  457:    marker.  In particular, point is not crossing any interval
  458:    boundaries, so there's no need to use the usual SET_PT macro.  In
  459:    fact it would be incorrect to do so, because either the old or the
  460:    new value of point is out of sync with the current set of
  461:    intervals.  */
  462: 
  463: static void
  464: adjust_point (nchars, nbytes)
  465:      int nchars, nbytes;
  466: {
  467:   BUF_PT (current_buffer) += nchars;
  468:   BUF_PT_BYTE (current_buffer) += nbytes;
  469: 
  470:   /* In a single-byte buffer, the two positions must be equal.  */
  471:   if (ZV == ZV_BYTE
  472:       && PT != PT_BYTE)
  473:     abort ();
  474: }
  475: ^L
  476: /* Adjust markers for a replacement of a text at FROM (FROM_BYTE) of
  477:    length OLD_CHARS (OLD_BYTES) to a new text of length NEW_CHARS
  478:    (NEW_BYTES).  It is assumed that OLD_CHARS > 0, i.e., this is not
  479:    an insertion.  */
  480: 
  481: static void
  482: adjust_markers_for_replace (from, from_byte, old_chars, old_bytes,
  483:                             new_chars, new_bytes)
  484:      int from, from_byte, old_chars, old_bytes, new_chars, new_bytes;
  485: {
  486:   register struct Lisp_Marker *m;
  487:   int prev_to_byte = from_byte + old_bytes;
  488:   int diff_chars = new_chars - old_chars;
  489:   int diff_bytes = new_bytes - old_bytes;
  490: 
  491:   for (m = BUF_MARKERS (current_buffer); m; m = m->next)
  492:     {
  493:       if (m->bytepos >= prev_to_byte)
  494:         {
  495:           m->charpos += diff_chars;
  496:           m->bytepos += diff_bytes;
  497:         }
  498:       else if (m->bytepos > from_byte)
  499:         {
  500:           m->charpos = from;
  501:           m->bytepos = from_byte;
  502:         }
  503:     }
  504: 
  505:   CHECK_MARKERS ();
  506: }
  507: 
  508: ^L
  509: /* Make the gap NBYTES_ADDED bytes longer.  */
  510: 
  511: void
  512: make_gap_larger (nbytes_added)
  513:      int nbytes_added;
  514: {
  515:   Lisp_Object tem;
  516:   int real_gap_loc;
  517:   int real_gap_loc_byte;
  518:   int old_gap_size;
  519: 
  520:   /* If we have to get more space, get enough to last a while.  */
  521:   nbytes_added += 2000;
  522: 
  523:   /* Don't allow a buffer size that won't fit in an int
  524:      even if it will fit in a Lisp integer.
  525:      That won't work because so many places use `int'.
  526: 
  527:      Make sure we don't introduce overflows in the calculation.  */
  528: 
  529:   if (Z_BYTE - BEG_BYTE + GAP_SIZE
  530:       >= (((EMACS_INT) 1 << (min (VALBITS, BITS_PER_INT) - 1)) - 1
  531:           - nbytes_added))
  532:     error ("Buffer exceeds maximum size");
  533: 
  534:   enlarge_buffer_text (current_buffer, nbytes_added);
  535: 
  536:   /* Prevent quitting in move_gap.  */
  537:   tem = Vinhibit_quit;
  538:   Vinhibit_quit = Qt;
  539: 
  540:   real_gap_loc = GPT;
  541:   real_gap_loc_byte = GPT_BYTE;
  542:   old_gap_size = GAP_SIZE;
  543: 
  544:   /* Call the newly allocated space a gap at the end of the whole space.  */
  545:   GPT = Z + GAP_SIZE;
  546:   GPT_BYTE = Z_BYTE + GAP_SIZE;
  547:   GAP_SIZE = nbytes_added;
  548: 
  549:   /* Move the new gap down to be consecutive with the end of the old one.
  550:      This adjusts the markers properly too.  */
  551:   gap_left (real_gap_loc + old_gap_size, real_gap_loc_byte + old_gap_size, 1);
  552: 
  553:   /* Now combine the two into one large gap.  */
  554:   GAP_SIZE += old_gap_size;
  555:   GPT = real_gap_loc;
  556:   GPT_BYTE = real_gap_loc_byte;
  557: 
  558:   /* Put an anchor.  */
  559:   *(Z_ADDR) = 0;
  560: 
  561:   Vinhibit_quit = tem;
  562: }
  563: 
  564: 
  565: /* Make the gap NBYTES_REMOVED bytes shorter.  */
  566: 
  567: void
  568: make_gap_smaller (nbytes_removed)
  569:      int nbytes_removed;
  570: {
  571:   Lisp_Object tem;
  572:   int real_gap_loc;
  573:   int real_gap_loc_byte;
  574:   int real_Z;
  575:   int real_Z_byte;
  576:   int real_beg_unchanged;
  577:   int new_gap_size;
  578: 
  579:   /* Make sure the gap is at least 20 bytes.  */
  580:   if (GAP_SIZE - nbytes_removed < 20)
  581:     nbytes_removed = GAP_SIZE - 20;
  582: 
  583:   /* Prevent quitting in move_gap.  */
  584:   tem = Vinhibit_quit;
  585:   Vinhibit_quit = Qt;
  586: 
  587:   real_gap_loc = GPT;
  588:   real_gap_loc_byte = GPT_BYTE;
  589:   new_gap_size = GAP_SIZE - nbytes_removed;
  590:   real_Z = Z;
  591:   real_Z_byte = Z_BYTE;
  592:   real_beg_unchanged = BEG_UNCHANGED;
  593: 
  594:   /* Pretend that the last unwanted part of the gap is the entire gap,
  595:      and that the first desired part of the gap is part of the buffer
  596:      text.  */
  597:   bzero (GPT_ADDR, new_gap_size);
  598:   GPT += new_gap_size;
  599:   GPT_BYTE += new_gap_size;
  600:   Z += new_gap_size;
  601:   Z_BYTE += new_gap_size;
  602:   GAP_SIZE = nbytes_removed;
  603: 
  604:   /* Move the unwanted pretend gap to the end of the buffer.  This
  605:      adjusts the markers properly too.  */
  606:   gap_right (Z, Z_BYTE);
  607: 
  608:   enlarge_buffer_text (current_buffer, -nbytes_removed);
  609: 
  610:   /* Now restore the desired gap.  */
  611:   GAP_SIZE = new_gap_size;
  612:   GPT = real_gap_loc;
  613:   GPT_BYTE = real_gap_loc_byte;
  614:   Z = real_Z;
  615:   Z_BYTE = real_Z_byte;
  616:   BEG_UNCHANGED = real_beg_unchanged;
  617: 
  618:   /* Put an anchor.  */
  619:   *(Z_ADDR) = 0;
  620: 
  621:   Vinhibit_quit = tem;
  622: }
  623: 
  624: void
  625: make_gap (nbytes_added)
  626:      int nbytes_added;
  627: {
  628:   if (nbytes_added >= 0)
  629:     make_gap_larger (