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