cgit.sxemacs.org Git - sxemacs/blob - src/line-number.c

   1 /* Line number cache.
   2    Copyright (C) 1997 Free Software Foundation, Inc.
   3
   4 This file is part of SXEmacs
   5
   6 SXEmacs is free software: you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation, either version 3 of the License, or
   9 (at your option) any later version.
  10
  11 SXEmacs is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  18
  19
  20 /* Synched up with: Not in FSF. */
  21
  22 /* To calculate the line numbers, redisplay must count the newlines
  23    from a known position.  This used to be BUF_BEGV, but this made the
  24    line numbering extremely slow for large buffers, because Emacs had
  25    to rescan the whole buffer at each redisplay.
  26
  27    To make line numbering efficient, we maintain a buffer-local cache
  28    of recently used positions and their line numbers.  The cache is
  29    implemented as a small ring of cache positions.  A cache position
  30    is either nil or a cons of a buffer position (marker) and the
  31    corresponding line number.
  32
  33    When calculating the line numbers, this cache is consulted if it
  34    would otherwise take too much time to count the newlines in the
  35    buffer (see the comment to buffer_line_number().)
  36
  37    Insertion and deletions that contain/delete newlines invalidate the
  38    cached positions after the insertion point.  This guarantees
  39    relatively fast line numbers caching (even in buffers where point
  40    moves a lot), and low memory usage.  All of this is done only in
  41    the buffers where the cache is actually initialized -- i.e. where
  42    line-numbering is on, and you move the point farther than
  43    LINE_NUMBER_FAR from the beginning of buffer.  In this sense, the
  44    cache is lazy -- if you don't use it, you don't pay for it.
  45
  46    NOTE: line-number cache should not be confused with line-start
  47    cache.  Line-start cache (a part of redisplay) works with the
  48    display lines, whereas this works with the buffer lines (literally
  49    counting the newlines).  */
  50
  51 #include <config.h>
  52 #include "lisp.h"
  53 #include "buffer.h"
  54
  55 #include "line-number.h"
  56
  57 /* #### The following three values could stand more exploration for
  58    best performance.  */
  59
  60 /* Size of the ring.  The current code expects this to be a small
  61    number.  If you make it larger, you should probably optimize the
  62    code below to keep it sorted. */
  63 #define LINE_NUMBER_RING_SIZE 8
  64
  65 /* How much traversal has to be exceeded for two points to be
  66    considered "far" from each other.  When two points are far, cache
  67    will be used.  */
  68 #define LINE_NUMBER_FAR 16384
  69
  70 /* How large a string has to be to give up searching it for newlines,
  71    before change. */
  72 #define LINE_NUMBER_LARGE_STRING 256
  73
  74 /* To be used only when you *know* the cache has been allocated!  */
  75 #define LINE_NUMBER_RING(b) (XCAR ((b)->text->line_number_cache))
  76 #define LINE_NUMBER_BEGV(b) (XCDR ((b)->text->line_number_cache))
  77
  78 /* Initialize the cache.  Cache is (in pseudo-BNF):
  79
  80    CACHE                = nil | INITIALIZED-CACHE
  81    INITIALIZED-CACHE    = cons (RING, BEGV-LINE)
  82    RING                 = vector (*RING-ELEMENT)
  83    RING-ELEMENT         = nil | RING-PAIR
  84    RING-PAIR            = cons (marker, integer)
  85    BEGV-LINE            = integer
  86
  87    Line number cache should never, ever, be visible to Lisp (because
  88    destructively modifying its elements can cause crashes.)  Debug it
  89    using debug_print (current_buffer->text->last_number_cache).  */
  90 static void allocate_line_number_cache(struct buffer *b)
  91 {
  92         b->text->line_number_cache =
  93             Fcons(make_vector(LINE_NUMBER_RING_SIZE, Qnil), Qzero);
  94         narrow_line_number_cache(b);
  95 }
  96
  97 /* Flag LINE_NUMBER_BEGV (b) as dirty.  Do it only if the line number
  98    cache is already initialized.  */
  99 void narrow_line_number_cache(struct buffer *b)
 100 {
 101         if (NILP(b->text->line_number_cache))
 102                 return;
 103
 104         if (BUF_BEG(b) == BUF_BEGV(b))
 105                 /* The is the case Fwiden and save_restriction_restore.  Since we
 106                    know the correct value, we can update it now.  */
 107                 LINE_NUMBER_BEGV(b) = Qzero;
 108         else
 109                 /* Calculating the line number of BUF_BEGV here is a bad idea,
 110                    because there is absolutely no reason to do it before the next
 111                    redisplay.  We simply mark it as dirty instead.  */
 112                 LINE_NUMBER_BEGV(b) = make_int(-1);
 113 }
 114
 115 /* Invalidate the line number cache positions that lie after POS. */
 116 static void invalidate_line_number_cache(struct buffer *b, Bufpos pos)
 117 {
 118         EMACS_INT i, j;
 119         Lisp_Object *ring = XVECTOR_DATA(LINE_NUMBER_RING(b));
 120
 121         for (i = 0; i < LINE_NUMBER_RING_SIZE; i++) {
 122                 if (!CONSP(ring[i]))
 123                         break;
 124                 /* As the marker stays behind the insertions, this check might
 125                    as well be `>'.  However, Finsert_before_markers can advance
 126                    the marker anyway, which bites in shell buffers.
 127
 128                    #### This forces recreation of the cached marker (and
 129                    recalculation of newlines) every time a newline is inserted
 130                    at point, which is way losing.  Isn't there a way to make a
 131                    marker impervious to Finsert_before_markers()??  Maybe I
 132                    should convert the code to use extents.  */
 133                 if (marker_position(XCAR(ring[i])) >= pos) {
 134                         /* Get the marker out of the way.  */
 135                         Fset_marker(XCAR(ring[i]), Qnil, Qnil);
 136                         /* ...and shift the ring elements, up to the first nil.  */
 137                         for (j = i;
 138                              !NILP(ring[j]) && j < LINE_NUMBER_RING_SIZE - 1;
 139                              j++)
 140                                 ring[j] = ring[j + 1];
 141                         ring[j] = Qnil;
 142                         /* Must recheck position i. */
 143                         i--;
 144                 }
 145         }
 146 }
 147
 148 /* Invalidate the cache positions after POS, if the string to be
 149    inserted contains a newline.  If the string is too large (larger
 150    than LINE_NUMBER_LARGE_STRING), invalidate the cache positions
 151    after POS without prior search.
 152
 153    This will do nothing if the cache is uninitialized.  */
 154 void
 155 insert_invalidate_line_number_cache(struct buffer *b, Bufpos pos,
 156                                     const Bufbyte * nonreloc, Bytecount length)
 157 {
 158         if (NILP(b->text->line_number_cache))
 159                 return;
 160
 161         if (length > LINE_NUMBER_LARGE_STRING ||
 162             /* We could also count how many newlines there are in the string
 163                and update the cache accordingly, but it would be too much
 164                work for too little gain. */
 165             memchr((const void *)nonreloc, '\n', (size_t) length))
 166                 invalidate_line_number_cache(b, pos);
 167 }
 168
 169 /* Invalidate the cache positions after FROM, if the region to be
 170    deleted contains a newline.  If the region-to-be-deleted is larger
 171    than LINE_NUMBER_LARGE_STRING, invalidate the cache positions after
 172    FROM without unconditionally.
 173
 174    This will do nothing if the cache is uninitialized.  */
 175 void
 176 delete_invalidate_line_number_cache(struct buffer *b, Bufpos from, Bufpos to)
 177 {
 178         if (NILP(b->text->line_number_cache))
 179                 return;
 180
 181         if ((to - from) > LINE_NUMBER_LARGE_STRING)
 182                 invalidate_line_number_cache(b, from);
 183         else {
 184                 EMACS_INT shortage;
 185                 scan_buffer(b, '\n', from, to, 1, &shortage, 0);
 186                 if (!shortage)
 187                         invalidate_line_number_cache(b, from);
 188         }
 189 }
 190 \f
 191 /* Get the nearest known position we know the line number of
 192    (i.e. BUF_BEGV, and cached positions).  The return position will be
 193    either closer than BEG, or BEG.  The line of this known position
 194    will be stored in LINE.
 195
 196    *LINE should be initialized to the line number of BEG (normally,
 197    BEG will be BUF_BEGV, and *LINE will be XINT (LINE_NUMBER_BEGV).
 198    This will initialize the cache, if necessary.  */
 199 static void
 200 get_nearest_line_number(struct buffer *b, Bufpos * beg, Bufpos pos,
 201                         EMACS_INT * line)
 202 {
 203         EMACS_INT i;
 204         Lisp_Object *ring = XVECTOR_DATA(LINE_NUMBER_RING(b));
 205         Charcount length = pos - *beg;
 206
 207         if (length < 0)
 208                 length = -length;
 209
 210         /* Find the ring entry closest to POS, if it is closer than BEG. */
 211         for (i = 0; i < LINE_NUMBER_RING_SIZE && CONSP(ring[i]); i++) {
 212                 Bufpos newpos = marker_position(XCAR(ring[i]));
 213                 Charcount howfar = newpos - pos;
 214                 if (howfar < 0)
 215                         howfar = -howfar;
 216                 if (howfar < length) {
 217                         length = howfar;
 218                         *beg = newpos;
 219                         *line = XINT(XCDR(ring[i]));
 220                 }
 221         }
 222 }
 223
 224 /* Add a (POS . LINE) pair to the ring, and rotate it. */
 225 static void add_position_to_cache(struct buffer *b, Bufpos pos, EMACS_INT line)
 226 {
 227         Lisp_Object *ring = XVECTOR_DATA(LINE_NUMBER_RING(b));
 228         int i = LINE_NUMBER_RING_SIZE - 1;
 229
 230         /* Set the last marker in the ring to point nowhere. */
 231         if (CONSP(ring[i]))
 232                 Fset_marker(XCAR(ring[i]), Qnil, Qnil);
 233
 234         /* Rotate the ring... */
 235         for (; i > 0; i--)
 236                 ring[i] = ring[i - 1];
 237
 238         /* ...and update it. */
 239         ring[0] = Fcons(Fset_marker(Fmake_marker(), make_int(pos),
 240                                     make_buffer(b)), make_int(line));
 241 }
 242
 243 /* Calculate the line number in buffer B at position POS.  If CACHEP
 244    is non-zero, initialize and facilitate the line-number cache.  The
 245    line number of the first line is 0.  If narrowing is in effect,
 246    count the lines are counted from the beginning of the visible
 247    portion of the buffer.
 248
 249    The cache works as follows: To calculate the line number, we need
 250    two positions: position of point (POS) and the position from which
 251    to count newlines (BEG).  We start by setting BEG to BUF_BEGV.  If
 252    this would require too much searching (i.e. pos - BUF_BEGV >
 253    LINE_NUMBER_FAR), try to find a closer position in the ring.  If it
 254    is found, use that position for BEG, and increment the line number
 255    appropriately.
 256
 257    If the calculation (with or without the cache lookup) required more
 258    than LINE_NUMBER_FAR characters of traversal, update the cache.  */
 259 EMACS_INT buffer_line_number(struct buffer *b, Bufpos pos, int cachep)
 260 {
 261         Bufpos beg = BUF_BEGV(b);
 262         EMACS_INT cached_lines = 0;
 263         EMACS_INT shortage, line;
 264
 265         if ((pos > beg ? pos - beg : beg - pos) <= LINE_NUMBER_FAR)
 266                 cachep = 0;
 267
 268         if (cachep) {
 269                 if (NILP(b->text->line_number_cache))
 270                         allocate_line_number_cache(b);
 271                 /* If we don't know the line number of BUF_BEGV, calculate it now.  */
 272                 if (XINT(LINE_NUMBER_BEGV(b)) == -1) {
 273                         LINE_NUMBER_BEGV(b) = Qzero;
 274                         /* #### This has a side-effect of changing the cache.  */
 275                         LINE_NUMBER_BEGV(b) =
 276                             make_int(buffer_line_number(b, BUF_BEGV(b), 1));
 277                 }
 278                 cached_lines = XINT(LINE_NUMBER_BEGV(b));
 279                 get_nearest_line_number(b, &beg, pos, &cached_lines);
 280         }
 281
 282         scan_buffer(b, '\n', beg, pos,
 283                     pos > beg ? EMACS_INT_MAX : -EMACS_INT_MAX, &shortage, 0);
 284
 285         line = EMACS_INT_MAX - shortage;
 286         if (beg > pos)
 287                 line = -line;
 288         line += cached_lines;
 289
 290         if (cachep) {
 291                 /* If too far, update the cache. */
 292                 if ((pos > beg ? pos - beg : beg - pos) > LINE_NUMBER_FAR)
 293                         add_position_to_cache(b, pos, line);
 294                 /* Account for narrowing.  If cache is not used, this is
 295                    unnecessary, because we counted from BUF_BEGV anyway.  */
 296                 line -= XINT(LINE_NUMBER_BEGV(b));
 297         }
 298
 299         return line;
 300 }