2 Copyright (C) 1997 Free Software Foundation, Inc.
4 This file is part of SXEmacs
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.
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.
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/>. */
20 /* Synched up with: Not in FSF. */
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.
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.
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().)
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.
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). */
55 #include "line-number.h"
57 /* #### The following three values could stand more exploration for
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
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
68 #define LINE_NUMBER_FAR 16384
70 /* How large a string has to be to give up searching it for newlines,
72 #define LINE_NUMBER_LARGE_STRING 256
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))
78 /* Initialize the cache. Cache is (in pseudo-BNF):
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)
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)
92 b->text->line_number_cache =
93 Fcons(make_vector(LINE_NUMBER_RING_SIZE, Qnil), Qzero);
94 narrow_line_number_cache(b);
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)
101 if (NILP(b->text->line_number_cache))
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;
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);
115 /* Invalidate the line number cache positions that lie after POS. */
116 static void invalidate_line_number_cache(struct buffer *b, Bufpos pos)
119 Lisp_Object *ring = XVECTOR_DATA(LINE_NUMBER_RING(b));
121 for (i = 0; i < LINE_NUMBER_RING_SIZE; i++) {
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.
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. */
138 !NILP(ring[j]) && j < LINE_NUMBER_RING_SIZE - 1;
140 ring[j] = ring[j + 1];
142 /* Must recheck position i. */
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.
153 This will do nothing if the cache is uninitialized. */
155 insert_invalidate_line_number_cache(struct buffer *b, Bufpos pos,
156 const Bufbyte * nonreloc, Bytecount length)
158 if (NILP(b->text->line_number_cache))
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);
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.
174 This will do nothing if the cache is uninitialized. */
176 delete_invalidate_line_number_cache(struct buffer *b, Bufpos from, Bufpos to)
178 if (NILP(b->text->line_number_cache))
181 if ((to - from) > LINE_NUMBER_LARGE_STRING)
182 invalidate_line_number_cache(b, from);
185 scan_buffer(b, '\n', from, to, 1, &shortage, 0);
187 invalidate_line_number_cache(b, from);
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.
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. */
200 get_nearest_line_number(struct buffer *b, Bufpos * beg, Bufpos pos,
204 Lisp_Object *ring = XVECTOR_DATA(LINE_NUMBER_RING(b));
205 Charcount length = pos - *beg;
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;
216 if (howfar < length) {
219 *line = XINT(XCDR(ring[i]));
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)
227 Lisp_Object *ring = XVECTOR_DATA(LINE_NUMBER_RING(b));
228 int i = LINE_NUMBER_RING_SIZE - 1;
230 /* Set the last marker in the ring to point nowhere. */
232 Fset_marker(XCAR(ring[i]), Qnil, Qnil);
234 /* Rotate the ring... */
236 ring[i] = ring[i - 1];
238 /* ...and update it. */
239 ring[0] = Fcons(Fset_marker(Fmake_marker(), make_int(pos),
240 make_buffer(b)), make_int(line));
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.
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
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)
261 Bufpos beg = BUF_BEGV(b);
262 EMACS_INT cached_lines = 0;
263 EMACS_INT shortage, line;
265 if ((pos > beg ? pos - beg : beg - pos) <= LINE_NUMBER_FAR)
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));
278 cached_lines = XINT(LINE_NUMBER_BEGV(b));
279 get_nearest_line_number(b, &beg, pos, &cached_lines);
282 scan_buffer(b, '\n', beg, pos,
283 pos > beg ? EMACS_INT_MAX : -EMACS_INT_MAX, &shortage, 0);
285 line = EMACS_INT_MAX - shortage;
288 line += cached_lines;
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));