1// This is an open source non-commercial project. Dear PVS-Studio, please check
2// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
3
4/*
5 * undo.c: multi level undo facility
6 *
7 * The saved lines are stored in a list of lists (one for each buffer):
8 *
9 * b_u_oldhead------------------------------------------------+
10 * |
11 * V
12 * +--------------+ +--------------+ +--------------+
13 * b_u_newhead--->| u_header | | u_header | | u_header |
14 * | uh_next------>| uh_next------>| uh_next---->NULL
15 * NULL<--------uh_prev |<---------uh_prev |<---------uh_prev |
16 * | uh_entry | | uh_entry | | uh_entry |
17 * +--------|-----+ +--------|-----+ +--------|-----+
18 * | | |
19 * V V V
20 * +--------------+ +--------------+ +--------------+
21 * | u_entry | | u_entry | | u_entry |
22 * | ue_next | | ue_next | | ue_next |
23 * +--------|-----+ +--------|-----+ +--------|-----+
24 * | | |
25 * V V V
26 * +--------------+ NULL NULL
27 * | u_entry |
28 * | ue_next |
29 * +--------|-----+
30 * |
31 * V
32 * etc.
33 *
34 * Each u_entry list contains the information for one undo or redo.
35 * curbuf->b_u_curhead points to the header of the last undo (the next redo),
36 * or is NULL if nothing has been undone (end of the branch).
37 *
38 * For keeping alternate undo/redo branches the uh_alt field is used. Thus at
39 * each point in the list a branch may appear for an alternate to redo. The
40 * uh_seq field is numbered sequentially to be able to find a newer or older
41 * branch.
42 *
43 * +---------------+ +---------------+
44 * b_u_oldhead --->| u_header | | u_header |
45 * | uh_alt_next ---->| uh_alt_next ----> NULL
46 * NULL <----- uh_alt_prev |<------ uh_alt_prev |
47 * | uh_prev | | uh_prev |
48 * +-----|---------+ +-----|---------+
49 * | |
50 * V V
51 * +---------------+ +---------------+
52 * | u_header | | u_header |
53 * | uh_alt_next | | uh_alt_next |
54 * b_u_newhead --->| uh_alt_prev | | uh_alt_prev |
55 * | uh_prev | | uh_prev |
56 * +-----|---------+ +-----|---------+
57 * | |
58 * V V
59 * NULL +---------------+ +---------------+
60 * | u_header | | u_header |
61 * | uh_alt_next ---->| uh_alt_next |
62 * | uh_alt_prev |<------ uh_alt_prev |
63 * | uh_prev | | uh_prev |
64 * +-----|---------+ +-----|---------+
65 * | |
66 * etc. etc.
67 *
68 *
69 * All data is allocated and will all be freed when the buffer is unloaded.
70 */
71
72/* Uncomment the next line for including the u_check() function. This warns
73 * for errors in the debug information. */
74/* #define U_DEBUG 1 */
75#define UH_MAGIC 0x18dade /* value for uh_magic when in use */
76#define UE_MAGIC 0xabc123 /* value for ue_magic when in use */
77
78#include <assert.h>
79#include <inttypes.h>
80#include <limits.h>
81#include <stdbool.h>
82#include <string.h>
83#include <fcntl.h>
84
85#include "nvim/buffer.h"
86#include "nvim/ascii.h"
87#include "nvim/change.h"
88#include "nvim/undo.h"
89#include "nvim/cursor.h"
90#include "nvim/edit.h"
91#include "nvim/fileio.h"
92#include "nvim/fold.h"
93#include "nvim/buffer_updates.h"
94#include "nvim/mark.h"
95#include "nvim/memline.h"
96#include "nvim/message.h"
97#include "nvim/misc1.h"
98#include "nvim/memory.h"
99#include "nvim/garray.h"
100#include "nvim/option.h"
101#include "nvim/os_unix.h"
102#include "nvim/path.h"
103#include "nvim/sha256.h"
104#include "nvim/state.h"
105#include "nvim/strings.h"
106#include "nvim/types.h"
107#include "nvim/os/os.h"
108#include "nvim/os/time.h"
109
110#ifdef INCLUDE_GENERATED_DECLARATIONS
111# include "undo.c.generated.h"
112#endif
113
114/* used in undo_end() to report number of added and deleted lines */
115static long u_newcount, u_oldcount;
116
117/*
118 * When 'u' flag included in 'cpoptions', we behave like vi. Need to remember
119 * the action that "u" should do.
120 */
121static bool undo_undoes = false;
122
123static int lastmark = 0;
124
125#if defined(U_DEBUG)
126/*
127 * Check the undo structures for being valid. Print a warning when something
128 * looks wrong.
129 */
130static int seen_b_u_curhead;
131static int seen_b_u_newhead;
132static int header_count;
133
134static void u_check_tree(u_header_T *uhp,
135 u_header_T *exp_uh_next,
136 u_header_T *exp_uh_alt_prev) {
137 u_entry_T *uep;
138
139 if (uhp == NULL)
140 return;
141 ++header_count;
142 if (uhp == curbuf->b_u_curhead && ++seen_b_u_curhead > 1) {
143 EMSG("b_u_curhead found twice (looping?)");
144 return;
145 }
146 if (uhp == curbuf->b_u_newhead && ++seen_b_u_newhead > 1) {
147 EMSG("b_u_newhead found twice (looping?)");
148 return;
149 }
150
151 if (uhp->uh_magic != UH_MAGIC)
152 EMSG("uh_magic wrong (may be using freed memory)");
153 else {
154 /* Check pointers back are correct. */
155 if (uhp->uh_next.ptr != exp_uh_next) {
156 EMSG("uh_next wrong");
157 smsg("expected: 0x%x, actual: 0x%x",
158 exp_uh_next, uhp->uh_next.ptr);
159 }
160 if (uhp->uh_alt_prev.ptr != exp_uh_alt_prev) {
161 EMSG("uh_alt_prev wrong");
162 smsg("expected: 0x%x, actual: 0x%x",
163 exp_uh_alt_prev, uhp->uh_alt_prev.ptr);
164 }
165
166 /* Check the undo tree at this header. */
167 for (uep = uhp->uh_entry; uep != NULL; uep = uep->ue_next) {
168 if (uep->ue_magic != UE_MAGIC) {
169 EMSG("ue_magic wrong (may be using freed memory)");
170 break;
171 }
172 }
173
174 /* Check the next alt tree. */
175 u_check_tree(uhp->uh_alt_next.ptr, uhp->uh_next.ptr, uhp);
176
177 /* Check the next header in this branch. */
178 u_check_tree(uhp->uh_prev.ptr, uhp, NULL);
179 }
180}
181
182static void u_check(int newhead_may_be_NULL) {
183 seen_b_u_newhead = 0;
184 seen_b_u_curhead = 0;
185 header_count = 0;
186
187 u_check_tree(curbuf->b_u_oldhead, NULL, NULL);
188
189 if (seen_b_u_newhead == 0 && curbuf->b_u_oldhead != NULL
190 && !(newhead_may_be_NULL && curbuf->b_u_newhead == NULL))
191 EMSGN("b_u_newhead invalid: 0x%x", curbuf->b_u_newhead);
192 if (curbuf->b_u_curhead != NULL && seen_b_u_curhead == 0)
193 EMSGN("b_u_curhead invalid: 0x%x", curbuf->b_u_curhead);
194 if (header_count != curbuf->b_u_numhead) {
195 EMSG("b_u_numhead invalid");
196 smsg("expected: %" PRId64 ", actual: %" PRId64,
197 (int64_t)header_count, (int64_t)curbuf->b_u_numhead);
198 }
199}
200
201#endif
202
203/*
204 * Save the current line for both the "u" and "U" command.
205 * Careful: may trigger autocommands that reload the buffer.
206 * Returns OK or FAIL.
207 */
208int u_save_cursor(void)
209{
210 linenr_T cur = curwin->w_cursor.lnum;
211 linenr_T top = cur > 0 ? cur - 1 : 0;
212 linenr_T bot = cur + 1;
213
214 return u_save(top, bot);
215}
216
217/*
218 * Save the lines between "top" and "bot" for both the "u" and "U" command.
219 * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
220 * Careful: may trigger autocommands that reload the buffer.
221 * Returns FAIL when lines could not be saved, OK otherwise.
222 */
223int u_save(linenr_T top, linenr_T bot)
224{
225 if (undo_off)
226 return OK;
227
228 if (top >= bot || bot > (curbuf->b_ml.ml_line_count + 1)) {
229 return FAIL; /* rely on caller to do error messages */
230 }
231
232 if (top + 2 == bot)
233 u_saveline((linenr_T)(top + 1));
234
235 return u_savecommon(top, bot, (linenr_T)0, FALSE);
236}
237
238/*
239 * Save the line "lnum" (used by ":s" and "~" command).
240 * The line is replaced, so the new bottom line is lnum + 1.
241 * Careful: may trigger autocommands that reload the buffer.
242 * Returns FAIL when lines could not be saved, OK otherwise.
243 */
244int u_savesub(linenr_T lnum)
245{
246 if (undo_off)
247 return OK;
248
249 return u_savecommon(lnum - 1, lnum + 1, lnum + 1, FALSE);
250}
251
252/*
253 * A new line is inserted before line "lnum" (used by :s command).
254 * The line is inserted, so the new bottom line is lnum + 1.
255 * Careful: may trigger autocommands that reload the buffer.
256 * Returns FAIL when lines could not be saved, OK otherwise.
257 */
258int u_inssub(linenr_T lnum)
259{
260 if (undo_off)
261 return OK;
262
263 return u_savecommon(lnum - 1, lnum, lnum + 1, FALSE);
264}
265
266/*
267 * Save the lines "lnum" - "lnum" + nlines (used by delete command).
268 * The lines are deleted, so the new bottom line is lnum, unless the buffer
269 * becomes empty.
270 * Careful: may trigger autocommands that reload the buffer.
271 * Returns FAIL when lines could not be saved, OK otherwise.
272 */
273int u_savedel(linenr_T lnum, long nlines)
274{
275 if (undo_off)
276 return OK;
277
278 return u_savecommon(lnum - 1, lnum + nlines,
279 nlines == curbuf->b_ml.ml_line_count ? 2 : lnum, FALSE);
280}
281
282/// Return true when undo is allowed. Otherwise print an error message and
283/// return false.
284///
285/// @return true if undo is allowed.
286bool undo_allowed(void)
287{
288 /* Don't allow changes when 'modifiable' is off. */
289 if (!MODIFIABLE(curbuf)) {
290 EMSG(_(e_modifiable));
291 return false;
292 }
293
294 // In the sandbox it's not allowed to change the text.
295 if (sandbox != 0) {
296 EMSG(_(e_sandbox));
297 return false;
298 }
299
300 /* Don't allow changes in the buffer while editing the cmdline. The
301 * caller of getcmdline() may get confused. */
302 if (textlock != 0) {
303 EMSG(_(e_secure));
304 return false;
305 }
306
307 return true;
308}
309
310/// Get the 'undolevels' value for the current buffer.
311static long get_undolevel(void)
312{
313 if (curbuf->b_p_ul == NO_LOCAL_UNDOLEVEL) {
314 return p_ul;
315 }
316 return curbuf->b_p_ul;
317}
318
319static inline void zero_fmark_additional_data(fmark_T *fmarks)
320{
321 for (size_t i = 0; i < NMARKS; i++) {
322 tv_dict_unref(fmarks[i].additional_data);
323 fmarks[i].additional_data = NULL;
324 }
325}
326
327/*
328 * Common code for various ways to save text before a change.
329 * "top" is the line above the first changed line.
330 * "bot" is the line below the last changed line.
331 * "newbot" is the new bottom line. Use zero when not known.
332 * "reload" is TRUE when saving for a buffer reload.
333 * Careful: may trigger autocommands that reload the buffer.
334 * Returns FAIL when lines could not be saved, OK otherwise.
335 */
336int u_savecommon(linenr_T top, linenr_T bot, linenr_T newbot, int reload)
337{
338 linenr_T lnum;
339 long i;
340 u_header_T *uhp;
341 u_header_T *old_curhead;
342 u_entry_T *uep;
343 u_entry_T *prev_uep;
344 long size;
345
346 if (!reload) {
347 /* When making changes is not allowed return FAIL. It's a crude way
348 * to make all change commands fail. */
349 if (!undo_allowed())
350 return FAIL;
351
352
353 /*
354 * Saving text for undo means we are going to make a change. Give a
355 * warning for a read-only file before making the change, so that the
356 * FileChangedRO event can replace the buffer with a read-write version
357 * (e.g., obtained from a source control system).
358 */
359 change_warning(0);
360 if (bot > curbuf->b_ml.ml_line_count + 1) {
361 /* This happens when the FileChangedRO autocommand changes the
362 * file in a way it becomes shorter. */
363 EMSG(_("E881: Line count changed unexpectedly"));
364 return FAIL;
365 }
366 }
367
368#ifdef U_DEBUG
369 u_check(FALSE);
370#endif
371
372 size = bot - top - 1;
373
374 /*
375 * If curbuf->b_u_synced == true make a new header.
376 */
377 if (curbuf->b_u_synced) {
378 /* Need to create new entry in b_changelist. */
379 curbuf->b_new_change = true;
380
381 if (get_undolevel() >= 0) {
382 /*
383 * Make a new header entry. Do this first so that we don't mess
384 * up the undo info when out of memory.
385 */
386 uhp = xmalloc(sizeof(u_header_T));
387#ifdef U_DEBUG
388 uhp->uh_magic = UH_MAGIC;
389#endif
390 } else
391 uhp = NULL;
392
393 /*
394 * If we undid more than we redid, move the entry lists before and
395 * including curbuf->b_u_curhead to an alternate branch.
396 */
397 old_curhead = curbuf->b_u_curhead;
398 if (old_curhead != NULL) {
399 curbuf->b_u_newhead = old_curhead->uh_next.ptr;
400 curbuf->b_u_curhead = NULL;
401 }
402
403 /*
404 * free headers to keep the size right
405 */
406 while (curbuf->b_u_numhead > get_undolevel()
407 && curbuf->b_u_oldhead != NULL) {
408 u_header_T *uhfree = curbuf->b_u_oldhead;
409
410 if (uhfree == old_curhead)
411 /* Can't reconnect the branch, delete all of it. */
412 u_freebranch(curbuf, uhfree, &old_curhead);
413 else if (uhfree->uh_alt_next.ptr == NULL)
414 /* There is no branch, only free one header. */
415 u_freeheader(curbuf, uhfree, &old_curhead);
416 else {
417 /* Free the oldest alternate branch as a whole. */
418 while (uhfree->uh_alt_next.ptr != NULL)
419 uhfree = uhfree->uh_alt_next.ptr;
420 u_freebranch(curbuf, uhfree, &old_curhead);
421 }
422#ifdef U_DEBUG
423 u_check(TRUE);
424#endif
425 }
426
427 if (uhp == NULL) { /* no undo at all */
428 if (old_curhead != NULL)
429 u_freebranch(curbuf, old_curhead, NULL);
430 curbuf->b_u_synced = false;
431 return OK;
432 }
433
434 uhp->uh_prev.ptr = NULL;
435 uhp->uh_next.ptr = curbuf->b_u_newhead;
436 uhp->uh_alt_next.ptr = old_curhead;
437 if (old_curhead != NULL) {
438 uhp->uh_alt_prev.ptr = old_curhead->uh_alt_prev.ptr;
439 if (uhp->uh_alt_prev.ptr != NULL)
440 uhp->uh_alt_prev.ptr->uh_alt_next.ptr = uhp;
441 old_curhead->uh_alt_prev.ptr = uhp;
442 if (curbuf->b_u_oldhead == old_curhead)
443 curbuf->b_u_oldhead = uhp;
444 } else
445 uhp->uh_alt_prev.ptr = NULL;
446 if (curbuf->b_u_newhead != NULL)
447 curbuf->b_u_newhead->uh_prev.ptr = uhp;
448
449 uhp->uh_seq = ++curbuf->b_u_seq_last;
450 curbuf->b_u_seq_cur = uhp->uh_seq;
451 uhp->uh_time = time(NULL);
452 uhp->uh_save_nr = 0;
453 curbuf->b_u_time_cur = uhp->uh_time + 1;
454
455 uhp->uh_walk = 0;
456 uhp->uh_entry = NULL;
457 uhp->uh_getbot_entry = NULL;
458 uhp->uh_cursor = curwin->w_cursor; /* save cursor pos. for undo */
459 if (virtual_active() && curwin->w_cursor.coladd > 0)
460 uhp->uh_cursor_vcol = getviscol();
461 else
462 uhp->uh_cursor_vcol = -1;
463
464 /* save changed and buffer empty flag for undo */
465 uhp->uh_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
466 ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
467
468 /* save named marks and Visual marks for undo */
469 zero_fmark_additional_data(curbuf->b_namedm);
470 memmove(uhp->uh_namedm, curbuf->b_namedm,
471 sizeof(curbuf->b_namedm[0]) * NMARKS);
472 uhp->uh_visual = curbuf->b_visual;
473
474 curbuf->b_u_newhead = uhp;
475 if (curbuf->b_u_oldhead == NULL)
476 curbuf->b_u_oldhead = uhp;
477 ++curbuf->b_u_numhead;
478 } else {
479 if (get_undolevel() < 0) /* no undo at all */
480 return OK;
481
482 /*
483 * When saving a single line, and it has been saved just before, it
484 * doesn't make sense saving it again. Saves a lot of memory when
485 * making lots of changes inside the same line.
486 * This is only possible if the previous change didn't increase or
487 * decrease the number of lines.
488 * Check the ten last changes. More doesn't make sense and takes too
489 * long.
490 */
491 if (size == 1) {
492 uep = u_get_headentry();
493 prev_uep = NULL;
494 for (i = 0; i < 10; ++i) {
495 if (uep == NULL)
496 break;
497
498 /* If lines have been inserted/deleted we give up.
499 * Also when the line was included in a multi-line save. */
500 if ((curbuf->b_u_newhead->uh_getbot_entry != uep
501 ? (uep->ue_top + uep->ue_size + 1
502 != (uep->ue_bot == 0
503 ? curbuf->b_ml.ml_line_count + 1
504 : uep->ue_bot))
505 : uep->ue_lcount != curbuf->b_ml.ml_line_count)
506 || (uep->ue_size > 1
507 && top >= uep->ue_top
508 && top + 2 <= uep->ue_top + uep->ue_size + 1))
509 break;
510
511 /* If it's the same line we can skip saving it again. */
512 if (uep->ue_size == 1 && uep->ue_top == top) {
513 if (i > 0) {
514 /* It's not the last entry: get ue_bot for the last
515 * entry now. Following deleted/inserted lines go to
516 * the re-used entry. */
517 u_getbot();
518 curbuf->b_u_synced = false;
519
520 /* Move the found entry to become the last entry. The
521 * order of undo/redo doesn't matter for the entries
522 * we move it over, since they don't change the line
523 * count and don't include this line. It does matter
524 * for the found entry if the line count is changed by
525 * the executed command. */
526 prev_uep->ue_next = uep->ue_next;
527 uep->ue_next = curbuf->b_u_newhead->uh_entry;
528 curbuf->b_u_newhead->uh_entry = uep;
529 }
530
531 /* The executed command may change the line count. */
532 if (newbot != 0)
533 uep->ue_bot = newbot;
534 else if (bot > curbuf->b_ml.ml_line_count)
535 uep->ue_bot = 0;
536 else {
537 uep->ue_lcount = curbuf->b_ml.ml_line_count;
538 curbuf->b_u_newhead->uh_getbot_entry = uep;
539 }
540 return OK;
541 }
542 prev_uep = uep;
543 uep = uep->ue_next;
544 }
545 }
546
547 /* find line number for ue_bot for previous u_save() */
548 u_getbot();
549 }
550
551 /*
552 * add lines in front of entry list
553 */
554 uep = xmalloc(sizeof(u_entry_T));
555 memset(uep, 0, sizeof(u_entry_T));
556#ifdef U_DEBUG
557 uep->ue_magic = UE_MAGIC;
558#endif
559
560 uep->ue_size = size;
561 uep->ue_top = top;
562 if (newbot != 0)
563 uep->ue_bot = newbot;
564 /*
565 * Use 0 for ue_bot if bot is below last line.
566 * Otherwise we have to compute ue_bot later.
567 */
568 else if (bot > curbuf->b_ml.ml_line_count)
569 uep->ue_bot = 0;
570 else {
571 uep->ue_lcount = curbuf->b_ml.ml_line_count;
572 curbuf->b_u_newhead->uh_getbot_entry = uep;
573 }
574
575 if (size > 0) {
576 uep->ue_array = xmalloc(sizeof(char_u *) * (size_t)size);
577 for (i = 0, lnum = top + 1; i < size; ++i) {
578 fast_breakcheck();
579 if (got_int) {
580 u_freeentry(uep, i);
581 return FAIL;
582 }
583 uep->ue_array[i] = u_save_line(lnum++);
584 }
585 } else
586 uep->ue_array = NULL;
587 uep->ue_next = curbuf->b_u_newhead->uh_entry;
588 curbuf->b_u_newhead->uh_entry = uep;
589 curbuf->b_u_synced = false;
590 undo_undoes = false;
591
592#ifdef U_DEBUG
593 u_check(FALSE);
594#endif
595 return OK;
596}
597
598
599# define UF_START_MAGIC "Vim\237UnDo\345" /* magic at start of undofile */
600# define UF_START_MAGIC_LEN 9
601# define UF_HEADER_MAGIC 0x5fd0 /* magic at start of header */
602# define UF_HEADER_END_MAGIC 0xe7aa /* magic after last header */
603# define UF_ENTRY_MAGIC 0xf518 /* magic at start of entry */
604# define UF_ENTRY_END_MAGIC 0x3581 /* magic after last entry */
605# define UF_VERSION 2 /* 2-byte undofile version number */
606
607/* extra fields for header */
608# define UF_LAST_SAVE_NR 1
609
610/* extra fields for uhp */
611# define UHP_SAVE_NR 1
612
613static char_u e_not_open[] = N_("E828: Cannot open undo file for writing: %s");
614
615/*
616 * Compute the hash for the current buffer text into hash[UNDO_HASH_SIZE].
617 */
618void u_compute_hash(char_u *hash)
619{
620 context_sha256_T ctx;
621 linenr_T lnum;
622 char_u *p;
623
624 sha256_start(&ctx);
625 for (lnum = 1; lnum <= curbuf->b_ml.ml_line_count; ++lnum) {
626 p = ml_get(lnum);
627 sha256_update(&ctx, p, (uint32_t)(STRLEN(p) + 1));
628 }
629 sha256_finish(&ctx, hash);
630}
631
632/// Return an allocated string of the full path of the target undofile.
633///
634/// @param[in] buf_ffname Full file name for which undo file location should
635/// be found.
636/// @param[in] reading If true, find the file to read by traversing all of the
637/// directories in &undodir. If false use the first
638/// existing directory. If none of the directories in
639/// &undodir option exist then last directory in the list
640/// will be automatically created.
641///
642/// @return [allocated] File name to read from/write to or NULL.
643char *u_get_undo_file_name(const char *const buf_ffname, const bool reading)
644 FUNC_ATTR_WARN_UNUSED_RESULT
645{
646 char *dirp;
647 char dir_name[MAXPATHL + 1];
648 char *munged_name = NULL;
649 char *undo_file_name = NULL;
650 const char *ffname = buf_ffname;
651#ifdef HAVE_READLINK
652 char fname_buf[MAXPATHL];
653#endif
654
655 if (ffname == NULL) {
656 return NULL;
657 }
658
659#ifdef HAVE_READLINK
660 // Expand symlink in the file name, so that we put the undo file with the
661 // actual file instead of with the symlink.
662 if (resolve_symlink((const char_u *)ffname, (char_u *)fname_buf) == OK) {
663 ffname = fname_buf;
664 }
665#endif
666
667 // Loop over 'undodir'. When reading find the first file that exists.
668 // When not reading use the first directory that exists or ".".
669 dirp = (char *) p_udir;
670 while (*dirp != NUL) {
671 size_t dir_len = copy_option_part((char_u **)&dirp, (char_u *)dir_name,
672 MAXPATHL, ",");
673 if (dir_len == 1 && dir_name[0] == '.') {
674 // Use same directory as the ffname,
675 // "dir/name" -> "dir/.name.un~"
676 const size_t ffname_len = strlen(ffname);
677 undo_file_name = xmalloc(ffname_len + 6);
678 memmove(undo_file_name, ffname, ffname_len + 1);
679 char *const tail = (char *) path_tail((char_u *) undo_file_name);
680 const size_t tail_len = strlen(tail);
681 memmove(tail + 1, tail, tail_len + 1);
682 *tail = '.';
683 memmove(tail + tail_len + 1, ".un~", sizeof(".un~"));
684 } else {
685 dir_name[dir_len] = NUL;
686 bool has_directory = os_isdir((char_u *)dir_name);
687 if (!has_directory && *dirp == NUL && !reading) {
688 // Last directory in the list does not exist, create it.
689 int ret;
690 char *failed_dir;
691 if ((ret = os_mkdir_recurse(dir_name, 0755, &failed_dir)) != 0) {
692 EMSG3(_("E5003: Unable to create directory \"%s\" for undo file: %s"),
693 failed_dir, os_strerror(ret));
694 xfree(failed_dir);
695 } else {
696 has_directory = true;
697 }
698 }
699 if (has_directory) {
700 if (munged_name == NULL) {
701 munged_name = xstrdup(ffname);
702 for (char *p = munged_name; *p != NUL; MB_PTR_ADV(p)) {
703 if (vim_ispathsep(*p)) {
704 *p = '%';
705 }
706 }
707 }
708 undo_file_name = concat_fnames(dir_name, munged_name, true);
709 }
710 }
711
712 // When reading check if the file exists.
713 if (undo_file_name != NULL
714 && (!reading || os_path_exists((char_u *)undo_file_name))) {
715 break;
716 }
717 XFREE_CLEAR(undo_file_name);
718 }
719
720 xfree(munged_name);
721 return undo_file_name;
722}
723
724/// Display an error for corrupted undo file
725///
726/// @param[in] mesg Identifier of the corruption kind.
727/// @param[in] file_name File in which error occurred.
728static void corruption_error(const char *const mesg,
729 const char *const file_name)
730 FUNC_ATTR_NONNULL_ALL
731{
732 EMSG3(_("E825: Corrupted undo file (%s): %s"), mesg, file_name);
733}
734
735static void u_free_uhp(u_header_T *uhp)
736{
737 u_entry_T *nuep;
738 u_entry_T *uep;
739
740 uep = uhp->uh_entry;
741 while (uep != NULL) {
742 nuep = uep->ue_next;
743 u_freeentry(uep, uep->ue_size);
744 uep = nuep;
745 }
746 xfree(uhp);
747}
748
749/// Writes the undofile header.
750///
751/// @param bi The buffer information
752/// @param hash The hash of the buffer contents
753//
754/// @returns false in case of an error.
755static bool serialize_header(bufinfo_T *bi, char_u *hash)
756 FUNC_ATTR_NONNULL_ALL
757{
758 buf_T *buf = bi->bi_buf;
759 FILE *fp = bi->bi_fp;
760
761 // Start writing, first the magic marker and undo info version.
762 if (fwrite(UF_START_MAGIC, UF_START_MAGIC_LEN, 1, fp) != 1) {
763 return false;
764 }
765
766 undo_write_bytes(bi, UF_VERSION, 2);
767
768 // Write a hash of the buffer text, so that we can verify it is
769 // still the same when reading the buffer text.
770 if (!undo_write(bi, hash, UNDO_HASH_SIZE)) {
771 return false;
772 }
773
774 // Write buffer-specific data.
775 undo_write_bytes(bi, (uintmax_t)buf->b_ml.ml_line_count, 4);
776 size_t len = buf->b_u_line_ptr ? STRLEN(buf->b_u_line_ptr) : 0;
777 undo_write_bytes(bi, len, 4);
778 if (len > 0 && !undo_write(bi, buf->b_u_line_ptr, len)) {
779 return false;
780 }
781 undo_write_bytes(bi, (uintmax_t)buf->b_u_line_lnum, 4);
782 undo_write_bytes(bi, (uintmax_t)buf->b_u_line_colnr, 4);
783
784 // Write undo structures header data.
785 put_header_ptr(bi, buf->b_u_oldhead);
786 put_header_ptr(bi, buf->b_u_newhead);
787 put_header_ptr(bi, buf->b_u_curhead);
788
789 undo_write_bytes(bi, (uintmax_t)buf->b_u_numhead, 4);
790 undo_write_bytes(bi, (uintmax_t)buf->b_u_seq_last, 4);
791 undo_write_bytes(bi, (uintmax_t)buf->b_u_seq_cur, 4);
792 uint8_t time_buf[8];
793 time_to_bytes(buf->b_u_time_cur, time_buf);
794 undo_write(bi, time_buf, sizeof(time_buf));
795
796 // Write optional fields.
797 undo_write_bytes(bi, 4, 1);
798 undo_write_bytes(bi, UF_LAST_SAVE_NR, 1);
799 undo_write_bytes(bi, (uintmax_t)buf->b_u_save_nr_last, 4);
800
801 // Write end marker.
802 undo_write_bytes(bi, 0, 1);
803
804 return true;
805}
806
807/// Writes an undo header.
808///
809/// @param bi The buffer information
810/// @param uhp The undo header to write
811//
812/// @returns false in case of an error.
813static bool serialize_uhp(bufinfo_T *bi, u_header_T *uhp)
814{
815 if (!undo_write_bytes(bi, (uintmax_t)UF_HEADER_MAGIC, 2)) {
816 return false;
817 }
818
819 put_header_ptr(bi, uhp->uh_next.ptr);
820 put_header_ptr(bi, uhp->uh_prev.ptr);
821 put_header_ptr(bi, uhp->uh_alt_next.ptr);
822 put_header_ptr(bi, uhp->uh_alt_prev.ptr);
823 undo_write_bytes(bi, (uintmax_t)uhp->uh_seq, 4);
824 serialize_pos(bi, uhp->uh_cursor);
825 undo_write_bytes(bi, (uintmax_t)uhp->uh_cursor_vcol, 4);
826 undo_write_bytes(bi, (uintmax_t)uhp->uh_flags, 2);
827 // Assume NMARKS will stay the same.
828 for (size_t i = 0; i < (size_t)NMARKS; i++) {
829 serialize_pos(bi, uhp->uh_namedm[i].mark);
830 }
831 serialize_visualinfo(bi, &uhp->uh_visual);
832 uint8_t time_buf[8];
833 time_to_bytes(uhp->uh_time, time_buf);
834 undo_write(bi, time_buf, sizeof(time_buf));
835
836 // Write optional fields.
837 undo_write_bytes(bi, 4, 1);
838 undo_write_bytes(bi, UHP_SAVE_NR, 1);
839 undo_write_bytes(bi, (uintmax_t)uhp->uh_save_nr, 4);
840
841 // Write end marker.
842 undo_write_bytes(bi, 0, 1);
843
844 // Write all the entries.
845 for (u_entry_T *uep = uhp->uh_entry; uep; uep = uep->ue_next) {
846 undo_write_bytes(bi, (uintmax_t)UF_ENTRY_MAGIC, 2);
847 if (!serialize_uep(bi, uep)) {
848 return false;
849 }
850 }
851 undo_write_bytes(bi, (uintmax_t)UF_ENTRY_END_MAGIC, 2);
852 return true;
853}
854
855static u_header_T *unserialize_uhp(bufinfo_T *bi,
856 const char *file_name)
857{
858 u_header_T *uhp = xmalloc(sizeof(u_header_T));
859 memset(uhp, 0, sizeof(u_header_T));
860#ifdef U_DEBUG
861 uhp->uh_magic = UH_MAGIC;
862#endif
863 uhp->uh_next.seq = undo_read_4c(bi);
864 uhp->uh_prev.seq = undo_read_4c(bi);
865 uhp->uh_alt_next.seq = undo_read_4c(bi);
866 uhp->uh_alt_prev.seq = undo_read_4c(bi);
867 uhp->uh_seq = undo_read_4c(bi);
868 if (uhp->uh_seq <= 0) {
869 corruption_error("uh_seq", file_name);
870 xfree(uhp);
871 return NULL;
872 }
873 unserialize_pos(bi, &uhp->uh_cursor);
874 uhp->uh_cursor_vcol = undo_read_4c(bi);
875 uhp->uh_flags = undo_read_2c(bi);
876 const Timestamp cur_timestamp = os_time();
877 for (size_t i = 0; i < (size_t)NMARKS; i++) {
878 unserialize_pos(bi, &uhp->uh_namedm[i].mark);
879 uhp->uh_namedm[i].timestamp = cur_timestamp;
880 uhp->uh_namedm[i].fnum = 0;
881 }
882 unserialize_visualinfo(bi, &uhp->uh_visual);
883 uhp->uh_time = undo_read_time(bi);
884
885 // Unserialize optional fields.
886 for (;; ) {
887 int len = undo_read_byte(bi);
888
889 if (len == 0 || len == EOF) {
890 break;
891 }
892 int what = undo_read_byte(bi);
893 switch (what) {
894 case UHP_SAVE_NR:
895 uhp->uh_save_nr = undo_read_4c(bi);
896 break;
897 default:
898 // Field not supported, skip it.
899 while (--len >= 0) {
900 (void)undo_read_byte(bi);
901 }
902 }
903 }
904
905 // Unserialize the uep list.
906 u_entry_T *last_uep = NULL;
907 int c;
908 while ((c = undo_read_2c(bi)) == UF_ENTRY_MAGIC) {
909 bool error = false;
910 u_entry_T *uep = unserialize_uep(bi, &error, file_name);
911 if (last_uep == NULL) {
912 uhp->uh_entry = uep;
913 } else {
914 last_uep->ue_next = uep;
915 }
916 last_uep = uep;
917 if (uep == NULL || error) {
918 u_free_uhp(uhp);
919 return NULL;
920 }
921 }
922 if (c != UF_ENTRY_END_MAGIC) {
923 corruption_error("entry end", file_name);
924 u_free_uhp(uhp);
925 return NULL;
926 }
927
928 return uhp;
929}
930
931/// Serializes "uep".
932///
933/// @param bi The buffer information
934/// @param uep The undo entry to write
935//
936/// @returns false in case of an error.
937static bool serialize_uep(bufinfo_T *bi, u_entry_T *uep)
938{
939 undo_write_bytes(bi, (uintmax_t)uep->ue_top, 4);
940 undo_write_bytes(bi, (uintmax_t)uep->ue_bot, 4);
941 undo_write_bytes(bi, (uintmax_t)uep->ue_lcount, 4);
942 undo_write_bytes(bi, (uintmax_t)uep->ue_size, 4);
943
944 for (size_t i = 0; i < (size_t)uep->ue_size; i++) {
945 size_t len = STRLEN(uep->ue_array[i]);
946 if (!undo_write_bytes(bi, len, 4)) {
947 return false;
948 }
949 if (len > 0 && !undo_write(bi, uep->ue_array[i], len)) {
950 return false;
951 }
952 }
953 return true;
954}
955
956static u_entry_T *unserialize_uep(bufinfo_T * bi, bool *error,
957 const char *file_name)
958{
959 u_entry_T *uep = xmalloc(sizeof(u_entry_T));
960 memset(uep, 0, sizeof(u_entry_T));
961#ifdef U_DEBUG
962 uep->ue_magic = UE_MAGIC;
963#endif
964 uep->ue_top = undo_read_4c(bi);
965 uep->ue_bot = undo_read_4c(bi);
966 uep->ue_lcount = undo_read_4c(bi);
967 uep->ue_size = undo_read_4c(bi);
968
969 char_u **array = NULL;
970 if (uep->ue_size > 0) {
971 if ((size_t)uep->ue_size < SIZE_MAX / sizeof(char_u *)) { // -V547
972 array = xmalloc(sizeof(char_u *) * (size_t)uep->ue_size);
973 memset(array, 0, sizeof(char_u *) * (size_t)uep->ue_size);
974 }
975 }
976 uep->ue_array = array;
977
978 for (size_t i = 0; i < (size_t)uep->ue_size; i++) {
979 int line_len = undo_read_4c(bi);
980 char_u *line;
981 if (line_len >= 0) {
982 line = undo_read_string(bi, (size_t)line_len);
983 } else {
984 line = NULL;
985 corruption_error("line length", file_name);
986 }
987 if (line == NULL) {
988 *error = true;
989 return uep;
990 }
991 array[i] = line;
992 }
993 return uep;
994}
995
996/// Serializes "pos".
997static void serialize_pos(bufinfo_T *bi, pos_T pos)
998{
999 undo_write_bytes(bi, (uintmax_t)pos.lnum, 4);
1000 undo_write_bytes(bi, (uintmax_t)pos.col, 4);
1001 undo_write_bytes(bi, (uintmax_t)pos.coladd, 4);
1002}
1003
1004/// Unserializes the pos_T at the current position.
1005static void unserialize_pos(bufinfo_T *bi, pos_T *pos)
1006{
1007 pos->lnum = undo_read_4c(bi);
1008 if (pos->lnum < 0) {
1009 pos->lnum = 0;
1010 }
1011 pos->col = undo_read_4c(bi);
1012 if (pos->col < 0) {
1013 pos->col = 0;
1014 }
1015 pos->coladd = undo_read_4c(bi);
1016 if (pos->coladd < 0) {
1017 pos->coladd = 0;
1018 }
1019}
1020
1021/// Serializes "info".
1022static void serialize_visualinfo(bufinfo_T *bi, visualinfo_T *info)
1023{
1024 serialize_pos(bi, info->vi_start);
1025 serialize_pos(bi, info->vi_end);
1026 undo_write_bytes(bi, (uintmax_t)info->vi_mode, 4);
1027 undo_write_bytes(bi, (uintmax_t)info->vi_curswant, 4);
1028}
1029
1030/// Unserializes the visualinfo_T at the current position.
1031static void unserialize_visualinfo(bufinfo_T *bi, visualinfo_T *info)
1032{
1033 unserialize_pos(bi, &info->vi_start);
1034 unserialize_pos(bi, &info->vi_end);
1035 info->vi_mode = undo_read_4c(bi);
1036 info->vi_curswant = undo_read_4c(bi);
1037}
1038
1039/// Write the undo tree in an undo file.
1040///
1041/// @param[in] name Name of the undo file or NULL if this function needs to
1042/// generate the undo file name based on buf->b_ffname.
1043/// @param[in] forceit True for `:wundo!`, false otherwise.
1044/// @param[in] buf Buffer for which undo file is written.
1045/// @param[in] hash Hash value of the buffer text. Must have #UNDO_HASH_SIZE
1046/// size.
1047void u_write_undo(const char *const name, const bool forceit, buf_T *const buf,
1048 char_u *const hash)
1049 FUNC_ATTR_NONNULL_ARG(3, 4)
1050{
1051 u_header_T *uhp;
1052 char *file_name;
1053 int mark;
1054#ifdef U_DEBUG
1055 int headers_written = 0;
1056#endif
1057 int fd;
1058 FILE *fp = NULL;
1059 int perm;
1060 bool write_ok = false;
1061 bufinfo_T bi;
1062
1063 if (name == NULL) {
1064 file_name = u_get_undo_file_name((char *) buf->b_ffname, false);
1065 if (file_name == NULL) {
1066 if (p_verbose > 0) {
1067 verbose_enter();
1068 smsg(_("Cannot write undo file in any directory in 'undodir'"));
1069 verbose_leave();
1070 }
1071 return;
1072 }
1073 } else {
1074 file_name = (char *) name;
1075 }
1076
1077 /*
1078 * Decide about the permission to use for the undo file. If the buffer
1079 * has a name use the permission of the original file. Otherwise only
1080 * allow the user to access the undo file.
1081 */
1082 perm = 0600;
1083 if (buf->b_ffname != NULL) {
1084 perm = os_getperm((const char *)buf->b_ffname);
1085 if (perm < 0) {
1086 perm = 0600;
1087 }
1088 }
1089
1090 // Strip any sticky and executable bits.
1091 perm = perm & 0666;
1092
1093 /* If the undo file already exists, verify that it actually is an undo
1094 * file, and delete it. */
1095 if (os_path_exists((char_u *)file_name)) {
1096 if (name == NULL || !forceit) {
1097 /* Check we can read it and it's an undo file. */
1098 fd = os_open(file_name, O_RDONLY, 0);
1099 if (fd < 0) {
1100 if (name != NULL || p_verbose > 0) {
1101 if (name == NULL)
1102 verbose_enter();
1103 smsg(_("Will not overwrite with undo file, cannot read: %s"),
1104 file_name);
1105 if (name == NULL)
1106 verbose_leave();
1107 }
1108 goto theend;
1109 } else {
1110 char_u mbuf[UF_START_MAGIC_LEN];
1111 ssize_t len = read_eintr(fd, mbuf, UF_START_MAGIC_LEN);
1112 close(fd);
1113 if (len < UF_START_MAGIC_LEN
1114 || memcmp(mbuf, UF_START_MAGIC, UF_START_MAGIC_LEN) != 0) {
1115 if (name != NULL || p_verbose > 0) {
1116 if (name == NULL)
1117 verbose_enter();
1118 smsg(_("Will not overwrite, this is not an undo file: %s"),
1119 file_name);
1120 if (name == NULL)
1121 verbose_leave();
1122 }
1123 goto theend;
1124 }
1125 }
1126 }
1127 os_remove(file_name);
1128 }
1129
1130 /* If there is no undo information at all, quit here after deleting any
1131 * existing undo file. */
1132 if (buf->b_u_numhead == 0 && buf->b_u_line_ptr == NULL) {
1133 if (p_verbose > 0) {
1134 verb_msg(_("Skipping undo file write, nothing to undo"));
1135 }
1136 goto theend;
1137 }
1138
1139 fd = os_open(file_name, O_CREAT|O_WRONLY|O_EXCL|O_NOFOLLOW, perm);
1140 if (fd < 0) {
1141 EMSG2(_(e_not_open), file_name);
1142 goto theend;
1143 }
1144 (void)os_setperm(file_name, perm);
1145 if (p_verbose > 0) {
1146 verbose_enter();
1147 smsg(_("Writing undo file: %s"), file_name);
1148 verbose_leave();
1149 }
1150
1151#ifdef U_DEBUG
1152 /* Check there is no problem in undo info before writing. */
1153 u_check(FALSE);
1154#endif
1155
1156#ifdef UNIX
1157 /*
1158 * Try to set the group of the undo file same as the original file. If
1159 * this fails, set the protection bits for the group same as the
1160 * protection bits for others.
1161 */
1162 FileInfo file_info_old;
1163 FileInfo file_info_new;
1164 if (buf->b_ffname != NULL
1165 && os_fileinfo((char *)buf->b_ffname, &file_info_old)
1166 && os_fileinfo(file_name, &file_info_new)
1167 && file_info_old.stat.st_gid != file_info_new.stat.st_gid
1168 && os_fchown(fd, (uv_uid_t)-1, (uv_gid_t)file_info_old.stat.st_gid)) {
1169 os_setperm(file_name, (perm & 0707) | ((perm & 07) << 3));
1170 }
1171#endif
1172
1173 fp = fdopen(fd, "w");
1174 if (fp == NULL) {
1175 EMSG2(_(e_not_open), file_name);
1176 close(fd);
1177 os_remove(file_name);
1178 goto theend;
1179 }
1180
1181 /* Undo must be synced. */
1182 u_sync(TRUE);
1183
1184 /*
1185 * Write the header.
1186 */
1187 bi.bi_buf = buf;
1188 bi.bi_fp = fp;
1189 if (!serialize_header(&bi, hash)) {
1190 goto write_error;
1191 }
1192
1193 /*
1194 * Iteratively serialize UHPs and their UEPs from the top down.
1195 */
1196 mark = ++lastmark;
1197 uhp = buf->b_u_oldhead;
1198 while (uhp != NULL) {
1199 /* Serialize current UHP if we haven't seen it */
1200 if (uhp->uh_walk != mark) {
1201 uhp->uh_walk = mark;
1202#ifdef U_DEBUG
1203 ++headers_written;
1204#endif
1205 if (!serialize_uhp(&bi, uhp)) {
1206 goto write_error;
1207 }
1208 }
1209
1210 /* Now walk through the tree - algorithm from undo_time(). */
1211 if (uhp->uh_prev.ptr != NULL && uhp->uh_prev.ptr->uh_walk != mark)
1212 uhp = uhp->uh_prev.ptr;
1213 else if (uhp->uh_alt_next.ptr != NULL
1214 && uhp->uh_alt_next.ptr->uh_walk != mark)
1215 uhp = uhp->uh_alt_next.ptr;
1216 else if (uhp->uh_next.ptr != NULL && uhp->uh_alt_prev.ptr == NULL
1217 && uhp->uh_next.ptr->uh_walk != mark)
1218 uhp = uhp->uh_next.ptr;
1219 else if (uhp->uh_alt_prev.ptr != NULL)
1220 uhp = uhp->uh_alt_prev.ptr;
1221 else
1222 uhp = uhp->uh_next.ptr;
1223 }
1224
1225 if (undo_write_bytes(&bi, (uintmax_t)UF_HEADER_END_MAGIC, 2)) {
1226 write_ok = true;
1227 }
1228#ifdef U_DEBUG
1229 if (headers_written != buf->b_u_numhead) {
1230 EMSGN("Written %" PRId64 " headers, ...", headers_written);
1231 EMSGN("... but numhead is %" PRId64, buf->b_u_numhead);
1232 }
1233#endif
1234
1235write_error:
1236 fclose(fp);
1237 if (!write_ok)
1238 EMSG2(_("E829: write error in undo file: %s"), file_name);
1239
1240#ifdef HAVE_ACL
1241 if (buf->b_ffname != NULL) {
1242 vim_acl_T acl;
1243
1244 /* For systems that support ACL: get the ACL from the original file. */
1245 acl = mch_get_acl(buf->b_ffname);
1246 mch_set_acl((char_u *)file_name, acl);
1247 mch_free_acl(acl);
1248 }
1249#endif
1250
1251theend:
1252 if (file_name != name)
1253 xfree(file_name);
1254}
1255
1256/// Loads the undo tree from an undo file.
1257/// If "name" is not NULL use it as the undo file name. This also means being
1258/// a bit more verbose.
1259/// Otherwise use curbuf->b_ffname to generate the undo file name.
1260/// "hash[UNDO_HASH_SIZE]" must be the hash value of the buffer text.
1261void u_read_undo(char *name, char_u *hash, char_u *orig_name)
1262 FUNC_ATTR_NONNULL_ARG(2)
1263{
1264 u_header_T **uhp_table = NULL;
1265 char_u *line_ptr = NULL;
1266
1267 char *file_name;
1268 if (name == NULL) {
1269 file_name = u_get_undo_file_name((char *) curbuf->b_ffname, true);
1270 if (file_name == NULL) {
1271 return;
1272 }
1273
1274#ifdef UNIX
1275 // For safety we only read an undo file if the owner is equal to the
1276 // owner of the text file or equal to the current user.
1277 FileInfo file_info_orig;
1278 FileInfo file_info_undo;
1279 if (os_fileinfo((char *)orig_name, &file_info_orig)
1280 && os_fileinfo((char *)file_name, &file_info_undo)
1281 && file_info_orig.stat.st_uid != file_info_undo.stat.st_uid
1282 && file_info_undo.stat.st_uid != getuid()) {
1283 if (p_verbose > 0) {
1284 verbose_enter();
1285 smsg(_("Not reading undo file, owner differs: %s"),
1286 file_name);
1287 verbose_leave();
1288 }
1289 return;
1290 }
1291#endif
1292 } else {
1293 file_name = (char *) name;
1294 }
1295
1296 if (p_verbose > 0) {
1297 verbose_enter();
1298 smsg(_("Reading undo file: %s"), file_name);
1299 verbose_leave();
1300 }
1301
1302 FILE *fp = os_fopen(file_name, "r");
1303 if (fp == NULL) {
1304 if (name != NULL || p_verbose > 0) {
1305 EMSG2(_("E822: Cannot open undo file for reading: %s"), file_name);
1306 }
1307 goto error;
1308 }
1309
1310 bufinfo_T bi;
1311 bi.bi_buf = curbuf;
1312 bi.bi_fp = fp;
1313
1314 // Read the undo file header.
1315 char_u magic_buf[UF_START_MAGIC_LEN];
1316 if (fread(magic_buf, UF_START_MAGIC_LEN, 1, fp) != 1
1317 || memcmp(magic_buf, UF_START_MAGIC, UF_START_MAGIC_LEN) != 0) {
1318 EMSG2(_("E823: Not an undo file: %s"), file_name);
1319 goto error;
1320 }
1321 int version = get2c(fp);
1322 if (version != UF_VERSION) {
1323 EMSG2(_("E824: Incompatible undo file: %s"), file_name);
1324 goto error;
1325 }
1326
1327 char_u read_hash[UNDO_HASH_SIZE];
1328 if (!undo_read(&bi, read_hash, UNDO_HASH_SIZE)) {
1329 corruption_error("hash", file_name);
1330 goto error;
1331 }
1332 linenr_T line_count = (linenr_T)undo_read_4c(&bi);
1333 if (memcmp(hash, read_hash, UNDO_HASH_SIZE) != 0
1334 || line_count != curbuf->b_ml.ml_line_count) {
1335 if (p_verbose > 0 || name != NULL) {
1336 if (name == NULL) {
1337 verbose_enter();
1338 }
1339 give_warning((char_u *)
1340 _("File contents changed, cannot use undo info"), true);
1341 if (name == NULL) {
1342 verbose_leave();
1343 }
1344 }
1345 goto error;
1346 }
1347
1348 // Read undo data for "U" command.
1349 int str_len = undo_read_4c(&bi);
1350 if (str_len < 0) {
1351 goto error;
1352 }
1353
1354 if (str_len > 0) {
1355 line_ptr = undo_read_string(&bi, (size_t)str_len);
1356 }
1357 linenr_T line_lnum = (linenr_T)undo_read_4c(&bi);
1358 colnr_T line_colnr = (colnr_T)undo_read_4c(&bi);
1359 if (line_lnum < 0 || line_colnr < 0) {
1360 corruption_error("line lnum/col", file_name);
1361 goto error;
1362 }
1363
1364 // Begin general undo data
1365 int old_header_seq = undo_read_4c(&bi);
1366 int new_header_seq = undo_read_4c(&bi);
1367 int cur_header_seq = undo_read_4c(&bi);
1368 int num_head = undo_read_4c(&bi);
1369 int seq_last = undo_read_4c(&bi);
1370 int seq_cur = undo_read_4c(&bi);
1371 time_t seq_time = undo_read_time(&bi);
1372
1373 // Optional header fields.
1374 long last_save_nr = 0;
1375 for (;; ) {
1376 int len = undo_read_byte(&bi);
1377
1378 if (len == 0 || len == EOF) {
1379 break;
1380 }
1381 int what = undo_read_byte(&bi);
1382 switch (what) {
1383 case UF_LAST_SAVE_NR:
1384 last_save_nr = undo_read_4c(&bi);
1385 break;
1386
1387 default:
1388 // field not supported, skip
1389 while (--len >= 0) {
1390 (void)undo_read_byte(&bi);
1391 }
1392 }
1393 }
1394
1395 // uhp_table will store the freshly created undo headers we allocate
1396 // until we insert them into curbuf. The table remains sorted by the
1397 // sequence numbers of the headers.
1398 // When there are no headers uhp_table is NULL.
1399 if (num_head > 0) {
1400 if ((size_t)num_head < SIZE_MAX / sizeof(*uhp_table)) { // -V547
1401 uhp_table = xmalloc((size_t)num_head * sizeof(*uhp_table));
1402 }
1403 }
1404
1405 long num_read_uhps = 0;
1406
1407 int c;
1408 while ((c = undo_read_2c(&bi)) == UF_HEADER_MAGIC) {
1409 if (num_read_uhps >= num_head) {
1410 corruption_error("num_head too small", file_name);
1411 goto error;
1412 }
1413
1414 u_header_T *uhp = unserialize_uhp(&bi, file_name);
1415 if (uhp == NULL) {
1416 goto error;
1417 }
1418 uhp_table[num_read_uhps++] = uhp;
1419 }
1420
1421 if (num_read_uhps != num_head) {
1422 corruption_error("num_head", file_name);
1423 goto error;
1424 }
1425 if (c != UF_HEADER_END_MAGIC) {
1426 corruption_error("end marker", file_name);
1427 goto error;
1428 }
1429
1430#ifdef U_DEBUG
1431 size_t amount = num_head * sizeof(int) + 1;
1432 int *uhp_table_used = xmalloc(amount);
1433 memset(uhp_table_used, 0, amount);
1434# define SET_FLAG(j) ++ uhp_table_used[j]
1435#else
1436# define SET_FLAG(j)
1437#endif
1438
1439 // We have put all of the headers into a table. Now we iterate through the
1440 // table and swizzle each sequence number we have stored in uh_*_seq into
1441 // a pointer corresponding to the header with that sequence number.
1442 short old_idx = -1, new_idx = -1, cur_idx = -1;
1443 for (int i = 0; i < num_head; i++) {
1444 u_header_T *uhp = uhp_table[i];
1445 if (uhp == NULL) {
1446 continue;
1447 }
1448 for (int j = 0; j < num_head; j++) {
1449 if (uhp_table[j] != NULL && i != j
1450 && uhp_table[i]->uh_seq == uhp_table[j]->uh_seq) {
1451 corruption_error("duplicate uh_seq", file_name);
1452 goto error;
1453 }
1454 }
1455 for (int j = 0; j < num_head; j++) {
1456 if (uhp_table[j] != NULL
1457 && uhp_table[j]->uh_seq == uhp->uh_next.seq) {
1458 uhp->uh_next.ptr = uhp_table[j];
1459 SET_FLAG(j);
1460 break;
1461 }
1462 }
1463 for (int j = 0; j < num_head; j++) {
1464 if (uhp_table[j] != NULL
1465 && uhp_table[j]->uh_seq == uhp->uh_prev.seq) {
1466 uhp->uh_prev.ptr = uhp_table[j];
1467 SET_FLAG(j);
1468 break;
1469 }
1470 }
1471 for (int j = 0; j < num_head; j++) {
1472 if (uhp_table[j] != NULL
1473 && uhp_table[j]->uh_seq == uhp->uh_alt_next.seq) {
1474 uhp->uh_alt_next.ptr = uhp_table[j];
1475 SET_FLAG(j);
1476 break;
1477 }
1478 }
1479 for (int j = 0; j < num_head; j++) {
1480 if (uhp_table[j] != NULL
1481 && uhp_table[j]->uh_seq == uhp->uh_alt_prev.seq) {
1482 uhp->uh_alt_prev.ptr = uhp_table[j];
1483 SET_FLAG(j);
1484 break;
1485 }
1486 }
1487 if (old_header_seq > 0 && old_idx < 0 && uhp->uh_seq == old_header_seq) {
1488 assert(i <= SHRT_MAX);
1489 old_idx = (short)i;
1490 SET_FLAG(i);
1491 }
1492 if (new_header_seq > 0 && new_idx < 0 && uhp->uh_seq == new_header_seq) {
1493 assert(i <= SHRT_MAX);
1494 new_idx = (short)i;
1495 SET_FLAG(i);
1496 }
1497 if (cur_header_seq > 0 && cur_idx < 0 && uhp->uh_seq == cur_header_seq) {
1498 assert(i <= SHRT_MAX);
1499 cur_idx = (short)i;
1500 SET_FLAG(i);
1501 }
1502 }
1503
1504 // Now that we have read the undo info successfully, free the current undo
1505 // info and use the info from the file.
1506 u_blockfree(curbuf);
1507 curbuf->b_u_oldhead = old_idx < 0 ? NULL : uhp_table[old_idx];
1508 curbuf->b_u_newhead = new_idx < 0 ? NULL : uhp_table[new_idx];
1509 curbuf->b_u_curhead = cur_idx < 0 ? NULL : uhp_table[cur_idx];
1510 curbuf->b_u_line_ptr = line_ptr;
1511 curbuf->b_u_line_lnum = line_lnum;
1512 curbuf->b_u_line_colnr = line_colnr;
1513 curbuf->b_u_numhead = num_head;
1514 curbuf->b_u_seq_last = seq_last;
1515 curbuf->b_u_seq_cur = seq_cur;
1516 curbuf->b_u_time_cur = seq_time;
1517 curbuf->b_u_save_nr_last = last_save_nr;
1518 curbuf->b_u_save_nr_cur = last_save_nr;
1519
1520 curbuf->b_u_synced = true;
1521 xfree(uhp_table);
1522
1523#ifdef U_DEBUG
1524 for (int i = 0; i < num_head; i++) {
1525 if (uhp_table_used[i] == 0) {
1526 EMSGN("uhp_table entry %" PRId64 " not used, leaking memory", i);
1527 }
1528 }
1529 xfree(uhp_table_used);
1530 u_check(TRUE);
1531#endif
1532
1533 if (name != NULL) {
1534 smsg(_("Finished reading undo file %s"), file_name);
1535 }
1536 goto theend;
1537
1538error:
1539 xfree(line_ptr);
1540 if (uhp_table != NULL) {
1541 for (long i = 0; i < num_read_uhps; i++)
1542 if (uhp_table[i] != NULL) {
1543 u_free_uhp(uhp_table[i]);
1544 }
1545 xfree(uhp_table);
1546 }
1547
1548theend:
1549 if (fp != NULL) {
1550 fclose(fp);
1551 }
1552 if (file_name != name) {
1553 xfree(file_name);
1554 }
1555}
1556
1557/// Writes a sequence of bytes to the undo file.
1558///
1559/// @param bi The buffer info
1560/// @param ptr The byte buffer to write
1561/// @param len The number of bytes to write
1562///
1563/// @returns false in case of an error.
1564static bool undo_write(bufinfo_T *bi, uint8_t *ptr, size_t len)
1565 FUNC_ATTR_NONNULL_ARG(1)
1566{
1567 return fwrite(ptr, len, 1, bi->bi_fp) == 1;
1568}
1569
1570/// Writes a number, most significant bit first, in "len" bytes.
1571///
1572/// Must match with undo_read_?c() functions.
1573///
1574/// @param bi The buffer info
1575/// @param nr The number to write
1576/// @param len The number of bytes to use when writing the number.
1577///
1578/// @returns false in case of an error.
1579static bool undo_write_bytes(bufinfo_T *bi, uintmax_t nr, size_t len)
1580{
1581 assert(len > 0);
1582 uint8_t buf[8];
1583 for (size_t i = len - 1, bufi = 0; bufi < len; i--, bufi++) {
1584 buf[bufi] = (uint8_t)(nr >> (i * 8));
1585 }
1586 return undo_write(bi, buf, len);
1587}
1588
1589/// Writes the pointer to an undo header.
1590///
1591/// Instead of writing the pointer itself, we use the sequence
1592/// number of the header. This is converted back to pointers
1593/// when reading.
1594static void put_header_ptr(bufinfo_T *bi, u_header_T *uhp)
1595{
1596 assert(uhp == NULL || uhp->uh_seq >= 0);
1597 undo_write_bytes(bi, (uint64_t)(uhp != NULL ? uhp->uh_seq : 0), 4);
1598}
1599
1600static int undo_read_4c(bufinfo_T *bi)
1601{
1602 return get4c(bi->bi_fp);
1603}
1604
1605static int undo_read_2c(bufinfo_T *bi)
1606{
1607 return get2c(bi->bi_fp);
1608}
1609
1610static int undo_read_byte(bufinfo_T *bi)
1611{
1612 return getc(bi->bi_fp);
1613}
1614
1615static time_t undo_read_time(bufinfo_T *bi)
1616{
1617 return get8ctime(bi->bi_fp);
1618}
1619
1620/// Reads "buffer[size]" from the undo file.
1621///
1622/// @param bi The buffer info
1623/// @param buffer Character buffer to read data into
1624/// @param size The size of the character buffer
1625///
1626/// @returns false in case of an error.
1627static bool undo_read(bufinfo_T *bi, uint8_t *buffer, size_t size)
1628 FUNC_ATTR_NONNULL_ARG(1)
1629{
1630 const bool retval = fread(buffer, size, 1, bi->bi_fp) == 1;
1631 if (!retval) {
1632 // Error may be checked for only later. Fill with zeros,
1633 // so that the reader won't use garbage.
1634 memset(buffer, 0, size);
1635 }
1636 return retval;
1637}
1638
1639/// Reads a string of length "len" from "bi->bi_fd" and appends a zero to it.
1640///
1641/// @param len can be zero to allocate an empty line.
1642///
1643/// @returns a pointer to allocated memory or NULL in case of an error.
1644static uint8_t *undo_read_string(bufinfo_T *bi, size_t len)
1645{
1646 uint8_t *ptr = xmallocz(len);
1647 if (len > 0 && !undo_read(bi, ptr, len)) {
1648 xfree(ptr);
1649 return NULL;
1650 }
1651 return ptr;
1652}
1653
1654/*
1655 * If 'cpoptions' contains 'u': Undo the previous undo or redo (vi compatible).
1656 * If 'cpoptions' does not contain 'u': Always undo.
1657 */
1658void u_undo(int count)
1659{
1660 /*
1661 * If we get an undo command while executing a macro, we behave like the
1662 * original vi. If this happens twice in one macro the result will not
1663 * be compatible.
1664 */
1665 if (curbuf->b_u_synced == false) {
1666 u_sync(TRUE);
1667 count = 1;
1668 }
1669
1670 if (vim_strchr(p_cpo, CPO_UNDO) == NULL) {
1671 undo_undoes = true;
1672 } else {
1673 undo_undoes = !undo_undoes;
1674 }
1675 u_doit(count, false, true);
1676}
1677
1678/*
1679 * If 'cpoptions' contains 'u': Repeat the previous undo or redo.
1680 * If 'cpoptions' does not contain 'u': Always redo.
1681 */
1682void u_redo(int count)
1683{
1684 if (vim_strchr(p_cpo, CPO_UNDO) == NULL) {
1685 undo_undoes = false;
1686 }
1687
1688 u_doit(count, false, true);
1689}
1690
1691/// Undo and remove the branch from the undo tree.
1692/// Also moves the cursor (as a "normal" undo would).
1693bool u_undo_and_forget(int count)
1694{
1695 if (curbuf->b_u_synced == false) {
1696 u_sync(true);
1697 count = 1;
1698 }
1699 undo_undoes = true;
1700 u_doit(count, true,
1701 // Don't send nvim_buf_lines_event for u_undo_and_forget().
1702 false);
1703
1704 if (curbuf->b_u_curhead == NULL) {
1705 // nothing was undone.
1706 return false;
1707 }
1708
1709 // Delete the current redo header
1710 // set the redo header to the next alternative branch (if any)
1711 // otherwise we will be in the leaf state
1712 u_header_T *to_forget = curbuf->b_u_curhead;
1713 curbuf->b_u_newhead = to_forget->uh_next.ptr;
1714 curbuf->b_u_curhead = to_forget->uh_alt_next.ptr;
1715 if (curbuf->b_u_curhead) {
1716 to_forget->uh_alt_next.ptr = NULL;
1717 curbuf->b_u_curhead->uh_alt_prev.ptr = to_forget->uh_alt_prev.ptr;
1718 curbuf->b_u_seq_cur = curbuf->b_u_curhead->uh_next.ptr ?
1719 curbuf->b_u_curhead->uh_next.ptr->uh_seq : 0;
1720 } else if (curbuf->b_u_newhead) {
1721 curbuf->b_u_seq_cur = curbuf->b_u_newhead->uh_seq;
1722 }
1723 if (to_forget->uh_alt_prev.ptr) {
1724 to_forget->uh_alt_prev.ptr->uh_alt_next.ptr = curbuf->b_u_curhead;
1725 }
1726 if (curbuf->b_u_newhead) {
1727 curbuf->b_u_newhead->uh_prev.ptr = curbuf->b_u_curhead;
1728 }
1729 if (curbuf->b_u_seq_last == to_forget->uh_seq) {
1730 curbuf->b_u_seq_last--;
1731 }
1732 u_freebranch(curbuf, to_forget, NULL);
1733 return true;
1734}
1735
1736/// Undo or redo, depending on `undo_undoes`, `count` times.
1737///
1738/// @param startcount How often to undo or redo
1739/// @param quiet If `true`, don't show messages
1740/// @param do_buf_event If `true`, send the changedtick with the buffer updates
1741static void u_doit(int startcount, bool quiet, bool do_buf_event)
1742{
1743 int count = startcount;
1744
1745 if (!undo_allowed())
1746 return;
1747
1748 u_newcount = 0;
1749 u_oldcount = 0;
1750 if (curbuf->b_ml.ml_flags & ML_EMPTY)
1751 u_oldcount = -1;
1752 while (count--) {
1753 /* Do the change warning now, so that it triggers FileChangedRO when
1754 * needed. This may cause the file to be reloaded, that must happen
1755 * before we do anything, because it may change curbuf->b_u_curhead
1756 * and more. */
1757 change_warning(0);
1758
1759 if (undo_undoes) {
1760 if (curbuf->b_u_curhead == NULL) /* first undo */
1761 curbuf->b_u_curhead = curbuf->b_u_newhead;
1762 else if (get_undolevel() > 0) /* multi level undo */
1763 /* get next undo */
1764 curbuf->b_u_curhead = curbuf->b_u_curhead->uh_next.ptr;
1765 /* nothing to undo */
1766 if (curbuf->b_u_numhead == 0 || curbuf->b_u_curhead == NULL) {
1767 /* stick curbuf->b_u_curhead at end */
1768 curbuf->b_u_curhead = curbuf->b_u_oldhead;
1769 beep_flush();
1770 if (count == startcount - 1) {
1771 MSG(_("Already at oldest change"));
1772 return;
1773 }
1774 break;
1775 }
1776
1777 u_undoredo(true, do_buf_event);
1778 } else {
1779 if (curbuf->b_u_curhead == NULL || get_undolevel() <= 0) {
1780 beep_flush(); /* nothing to redo */
1781 if (count == startcount - 1) {
1782 MSG(_("Already at newest change"));
1783 return;
1784 }
1785 break;
1786 }
1787
1788 u_undoredo(false, do_buf_event);
1789
1790 /* Advance for next redo. Set "newhead" when at the end of the
1791 * redoable changes. */
1792 if (curbuf->b_u_curhead->uh_prev.ptr == NULL)
1793 curbuf->b_u_newhead = curbuf->b_u_curhead;
1794 curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev.ptr;
1795 }
1796 }
1797 u_undo_end(undo_undoes, false, quiet);
1798}
1799
1800// Undo or redo over the timeline.
1801// When "step" is negative go back in time, otherwise goes forward in time.
1802// When "sec" is false make "step" steps, when "sec" is true use "step" as
1803// seconds.
1804// When "file" is true use "step" as a number of file writes.
1805// When "absolute" is true use "step" as the sequence number to jump to.
1806// "sec" must be false then.
1807void undo_time(long step, bool sec, bool file, bool absolute)
1808{
1809 long target;
1810 long closest;
1811 long closest_start;
1812 long closest_seq = 0;
1813 long val;
1814 u_header_T *uhp = NULL;
1815 u_header_T *last;
1816 int mark;
1817 int nomark = 0; // shut up compiler
1818 int round;
1819 bool dosec = sec;
1820 bool dofile = file;
1821 bool above = false;
1822 bool did_undo = true;
1823
1824 /* First make sure the current undoable change is synced. */
1825 if (curbuf->b_u_synced == false)
1826 u_sync(TRUE);
1827
1828 u_newcount = 0;
1829 u_oldcount = 0;
1830 if (curbuf->b_ml.ml_flags & ML_EMPTY)
1831 u_oldcount = -1;
1832
1833 /* "target" is the node below which we want to be.
1834 * Init "closest" to a value we can't reach. */
1835 if (absolute) {
1836 target = step;
1837 closest = -1;
1838 } else {
1839 if (dosec) {
1840 target = (long)(curbuf->b_u_time_cur) + step;
1841 } else if (dofile) {
1842 if (step < 0) {
1843 /* Going back to a previous write. If there were changes after
1844 * the last write, count that as moving one file-write, so
1845 * that ":earlier 1f" undoes all changes since the last save. */
1846 uhp = curbuf->b_u_curhead;
1847 if (uhp != NULL)
1848 uhp = uhp->uh_next.ptr;
1849 else
1850 uhp = curbuf->b_u_newhead;
1851 if (uhp != NULL && uhp->uh_save_nr != 0)
1852 /* "uh_save_nr" was set in the last block, that means
1853 * there were no changes since the last write */
1854 target = curbuf->b_u_save_nr_cur + step;
1855 else
1856 /* count the changes since the last write as one step */
1857 target = curbuf->b_u_save_nr_cur + step + 1;
1858 if (target <= 0)
1859 /* Go to before first write: before the oldest change. Use
1860 * the sequence number for that. */
1861 dofile = false;
1862 } else {
1863 /* Moving forward to a newer write. */
1864 target = curbuf->b_u_save_nr_cur + step;
1865 if (target > curbuf->b_u_save_nr_last) {
1866 /* Go to after last write: after the latest change. Use
1867 * the sequence number for that. */
1868 target = curbuf->b_u_seq_last + 1;
1869 dofile = false;
1870 }
1871 }
1872 } else
1873 target = curbuf->b_u_seq_cur + step;
1874 if (step < 0) {
1875 if (target < 0)
1876 target = 0;
1877 closest = -1;
1878 } else {
1879 if (dosec) {
1880 closest = (long)(os_time() + 1);
1881 } else if (dofile) {
1882 closest = curbuf->b_u_save_nr_last + 2;
1883 } else {
1884 closest = curbuf->b_u_seq_last + 2;
1885 }
1886 if (target >= closest) {
1887 target = closest - 1;
1888 }
1889 }
1890 }
1891 closest_start = closest;
1892 closest_seq = curbuf->b_u_seq_cur;
1893
1894 // When "target" is 0; Back to origin.
1895 if (target == 0) {
1896 mark = lastmark; // avoid that GCC complains
1897 goto target_zero;
1898 }
1899
1900 /*
1901 * May do this twice:
1902 * 1. Search for "target", update "closest" to the best match found.
1903 * 2. If "target" not found search for "closest".
1904 *
1905 * When using the closest time we use the sequence number in the second
1906 * round, because there may be several entries with the same time.
1907 */
1908 for (round = 1; round <= 2; ++round) {
1909 /* Find the path from the current state to where we want to go. The
1910 * desired state can be anywhere in the undo tree, need to go all over
1911 * it. We put "nomark" in uh_walk where we have been without success,
1912 * "mark" where it could possibly be. */
1913 mark = ++lastmark;
1914 nomark = ++lastmark;
1915
1916 if (curbuf->b_u_curhead == NULL) /* at leaf of the tree */
1917 uhp = curbuf->b_u_newhead;
1918 else
1919 uhp = curbuf->b_u_curhead;
1920
1921 while (uhp != NULL) {
1922 uhp->uh_walk = mark;
1923 if (dosec) {
1924 val = (long)(uhp->uh_time);
1925 } else if (dofile) {
1926 val = uhp->uh_save_nr;
1927 } else {
1928 val = uhp->uh_seq;
1929 }
1930
1931 if (round == 1 && !(dofile && val == 0)) {
1932 /* Remember the header that is closest to the target.
1933 * It must be at least in the right direction (checked with
1934 * "b_u_seq_cur"). When the timestamp is equal find the
1935 * highest/lowest sequence number. */
1936 if ((step < 0 ? uhp->uh_seq <= curbuf->b_u_seq_cur
1937 : uhp->uh_seq > curbuf->b_u_seq_cur)
1938 && ((dosec && val == closest)
1939 ? (step < 0
1940 ? uhp->uh_seq < closest_seq
1941 : uhp->uh_seq > closest_seq)
1942 : closest == closest_start
1943 || (val > target
1944 ? (closest > target
1945 ? val - target <= closest - target
1946 : val - target <= target - closest)
1947 : (closest > target
1948 ? target - val <= closest - target
1949 : target - val <= target - closest)))) {
1950 closest = val;
1951 closest_seq = uhp->uh_seq;
1952 }
1953 }
1954
1955 /* Quit searching when we found a match. But when searching for a
1956 * time we need to continue looking for the best uh_seq. */
1957 if (target == val && !dosec) {
1958 target = uhp->uh_seq;
1959 break;
1960 }
1961
1962 /* go down in the tree if we haven't been there */
1963 if (uhp->uh_prev.ptr != NULL && uhp->uh_prev.ptr->uh_walk != nomark
1964 && uhp->uh_prev.ptr->uh_walk != mark)
1965 uhp = uhp->uh_prev.ptr;
1966
1967 /* go to alternate branch if we haven't been there */
1968 else if (uhp->uh_alt_next.ptr != NULL
1969 && uhp->uh_alt_next.ptr->uh_walk != nomark
1970 && uhp->uh_alt_next.ptr->uh_walk != mark)
1971 uhp = uhp->uh_alt_next.ptr;
1972
1973 /* go up in the tree if we haven't been there and we are at the
1974 * start of alternate branches */
1975 else if (uhp->uh_next.ptr != NULL && uhp->uh_alt_prev.ptr == NULL
1976 && uhp->uh_next.ptr->uh_walk != nomark
1977 && uhp->uh_next.ptr->uh_walk != mark) {
1978 /* If still at the start we don't go through this change. */
1979 if (uhp == curbuf->b_u_curhead)
1980 uhp->uh_walk = nomark;
1981 uhp = uhp->uh_next.ptr;
1982 } else {
1983 /* need to backtrack; mark this node as useless */
1984 uhp->uh_walk = nomark;
1985 if (uhp->uh_alt_prev.ptr != NULL)
1986 uhp = uhp->uh_alt_prev.ptr;
1987 else
1988 uhp = uhp->uh_next.ptr;
1989 }
1990 }
1991
1992 if (uhp != NULL) /* found it */
1993 break;
1994
1995 if (absolute) {
1996 EMSGN(_("E830: Undo number %" PRId64 " not found"), step);
1997 return;
1998 }
1999
2000 if (closest == closest_start) {
2001 if (step < 0)
2002 MSG(_("Already at oldest change"));
2003 else
2004 MSG(_("Already at newest change"));
2005 return;
2006 }
2007
2008 target = closest_seq;
2009 dosec = false;
2010 dofile = false;
2011 if (step < 0) {
2012 above = true; // stop above the header
2013 }
2014 }
2015
2016target_zero:
2017 // If we found it: Follow the path to go to where we want to be.
2018 if (uhp != NULL || target == 0) {
2019 // First go up the tree as much as needed.
2020 while (!got_int) {
2021 /* Do the change warning now, for the same reason as above. */
2022 change_warning(0);
2023
2024 uhp = curbuf->b_u_curhead;
2025 if (uhp == NULL)
2026 uhp = curbuf->b_u_newhead;
2027 else
2028 uhp = uhp->uh_next.ptr;
2029 if (uhp == NULL
2030 || (target > 0 && uhp->uh_walk != mark)
2031 || (uhp->uh_seq == target && !above)) {
2032 break;
2033 }
2034 curbuf->b_u_curhead = uhp;
2035 u_undoredo(true, true);
2036 if (target > 0) {
2037 uhp->uh_walk = nomark; // don't go back down here
2038 }
2039 }
2040
2041 // When back to origin, redo is not needed.
2042 if (target > 0) {
2043 // And now go down the tree (redo), branching off where needed.
2044 while (!got_int) {
2045 // Do the change warning now, for the same reason as above.
2046 change_warning(0);
2047
2048 uhp = curbuf->b_u_curhead;
2049 if (uhp == NULL) {
2050 break;
2051 }
2052
2053 // Go back to the first branch with a mark.
2054 while (uhp->uh_alt_prev.ptr != NULL
2055 && uhp->uh_alt_prev.ptr->uh_walk == mark) {
2056 uhp = uhp->uh_alt_prev.ptr;
2057 }
2058
2059 // Find the last branch with a mark, that's the one.
2060 last = uhp;
2061 while (last->uh_alt_next.ptr != NULL
2062 && last->uh_alt_next.ptr->uh_walk == mark) {
2063 last = last->uh_alt_next.ptr;
2064 }
2065 if (last != uhp) {
2066 // Make the used branch the first entry in the list of
2067 // alternatives to make "u" and CTRL-R take this branch.
2068 while (uhp->uh_alt_prev.ptr != NULL) {
2069 uhp = uhp->uh_alt_prev.ptr;
2070 }
2071 if (last->uh_alt_next.ptr != NULL) {
2072 last->uh_alt_next.ptr->uh_alt_prev.ptr = last->uh_alt_prev.ptr;
2073 }
2074 last->uh_alt_prev.ptr->uh_alt_next.ptr = last->uh_alt_next.ptr;
2075 last->uh_alt_prev.ptr = NULL;
2076 last->uh_alt_next.ptr = uhp;
2077 uhp->uh_alt_prev.ptr = last;
2078
2079 if (curbuf->b_u_oldhead == uhp) {
2080 curbuf->b_u_oldhead = last;
2081 }
2082 uhp = last;
2083 if (uhp->uh_next.ptr != NULL) {
2084 uhp->uh_next.ptr->uh_prev.ptr = uhp;
2085 }
2086 }
2087 curbuf->b_u_curhead = uhp;
2088
2089 if (uhp->uh_walk != mark) {
2090 break; // must have reached the target
2091 }
2092
2093 // Stop when going backwards in time and didn't find the exact
2094 // header we were looking for.
2095 if (uhp->uh_seq == target && above) {
2096 curbuf->b_u_seq_cur = target - 1;
2097 break;
2098 }
2099
2100 u_undoredo(false, true);
2101
2102 // Advance "curhead" to below the header we last used. If it
2103 // becomes NULL then we need to set "newhead" to this leaf.
2104 if (uhp->uh_prev.ptr == NULL) {
2105 curbuf->b_u_newhead = uhp;
2106 }
2107 curbuf->b_u_curhead = uhp->uh_prev.ptr;
2108 did_undo = false;
2109
2110 if (uhp->uh_seq == target) { // found it!
2111 break;
2112 }
2113
2114 uhp = uhp->uh_prev.ptr;
2115 if (uhp == NULL || uhp->uh_walk != mark) {
2116 // Need to redo more but can't find it...
2117 internal_error("undo_time()");
2118 break;
2119 }
2120 }
2121 }
2122 }
2123 u_undo_end(did_undo, absolute, false);
2124}
2125
2126/// u_undoredo: common code for undo and redo
2127///
2128/// The lines in the file are replaced by the lines in the entry list at
2129/// curbuf->b_u_curhead. The replaced lines in the file are saved in the entry
2130/// list for the next undo/redo.
2131///
2132/// @param undo If `true`, go up the tree. Down if `false`.
2133/// @param do_buf_event If `true`, send buffer updates.
2134static void u_undoredo(int undo, bool do_buf_event)
2135{
2136 char_u **newarray = NULL;
2137 linenr_T oldsize;
2138 linenr_T newsize;
2139 linenr_T top, bot;
2140 linenr_T lnum;
2141 linenr_T newlnum = MAXLNUM;
2142 long i;
2143 u_entry_T *uep, *nuep;
2144 u_entry_T *newlist = NULL;
2145 int old_flags;
2146 int new_flags;
2147 fmark_T namedm[NMARKS];
2148 visualinfo_T visualinfo;
2149 bool empty_buffer; // buffer became empty
2150 u_header_T *curhead = curbuf->b_u_curhead;
2151
2152 /* Don't want autocommands using the undo structures here, they are
2153 * invalid till the end. */
2154 block_autocmds();
2155
2156#ifdef U_DEBUG
2157 u_check(FALSE);
2158#endif
2159 old_flags = curhead->uh_flags;
2160 new_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
2161 ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
2162 setpcmark();
2163
2164 /*
2165 * save marks before undo/redo
2166 */
2167 zero_fmark_additional_data(curbuf->b_namedm);
2168 memmove(namedm, curbuf->b_namedm, sizeof(curbuf->b_namedm[0]) * NMARKS);
2169 visualinfo = curbuf->b_visual;
2170 curbuf->b_op_start.lnum = curbuf->b_ml.ml_line_count;
2171 curbuf->b_op_start.col = 0;
2172 curbuf->b_op_end.lnum = 0;
2173 curbuf->b_op_end.col = 0;
2174
2175 for (uep = curhead->uh_entry; uep != NULL; uep = nuep) {
2176 top = uep->ue_top;
2177 bot = uep->ue_bot;
2178 if (bot == 0)
2179 bot = curbuf->b_ml.ml_line_count + 1;
2180 if (top > curbuf->b_ml.ml_line_count || top >= bot
2181 || bot > curbuf->b_ml.ml_line_count + 1) {
2182 unblock_autocmds();
2183 IEMSG(_("E438: u_undo: line numbers wrong"));
2184 changed(); // don't want UNCHANGED now
2185 return;
2186 }
2187
2188 oldsize = bot - top - 1; /* number of lines before undo */
2189 newsize = uep->ue_size; /* number of lines after undo */
2190
2191 if (top < newlnum) {
2192 /* If the saved cursor is somewhere in this undo block, move it to
2193 * the remembered position. Makes "gwap" put the cursor back
2194 * where it was. */
2195 lnum = curhead->uh_cursor.lnum;
2196 if (lnum >= top && lnum <= top + newsize + 1) {
2197 curwin->w_cursor = curhead->uh_cursor;
2198 newlnum = curwin->w_cursor.lnum - 1;
2199 } else {
2200 /* Use the first line that actually changed. Avoids that
2201 * undoing auto-formatting puts the cursor in the previous
2202 * line. */
2203 for (i = 0; i < newsize && i < oldsize; ++i)
2204 if (STRCMP(uep->ue_array[i], ml_get(top + 1 + i)) != 0)
2205 break;
2206 if (i == newsize && newlnum == MAXLNUM && uep->ue_next == NULL) {
2207 newlnum = top;
2208 curwin->w_cursor.lnum = newlnum + 1;
2209 } else if (i < newsize) {
2210 newlnum = top + i;
2211 curwin->w_cursor.lnum = newlnum + 1;
2212 }
2213 }
2214 }
2215
2216 empty_buffer = false;
2217
2218 /* delete the lines between top and bot and save them in newarray */
2219 if (oldsize > 0) {
2220 newarray = xmalloc(sizeof(char_u *) * (size_t)oldsize);
2221 /* delete backwards, it goes faster in most cases */
2222 for (lnum = bot - 1, i = oldsize; --i >= 0; --lnum) {
2223 /* what can we do when we run out of memory? */
2224 newarray[i] = u_save_line(lnum);
2225 /* remember we deleted the last line in the buffer, and a
2226 * dummy empty line will be inserted */
2227 if (curbuf->b_ml.ml_line_count == 1) {
2228 empty_buffer = true;
2229 }
2230 ml_delete(lnum, false);
2231 }
2232 } else
2233 newarray = NULL;
2234
2235 /* insert the lines in u_array between top and bot */
2236 if (newsize) {
2237 for (lnum = top, i = 0; i < newsize; ++i, ++lnum) {
2238 /*
2239 * If the file is empty, there is an empty line 1 that we
2240 * should get rid of, by replacing it with the new line
2241 */
2242 if (empty_buffer && lnum == 0) {
2243 ml_replace((linenr_T)1, uep->ue_array[i], true);
2244 } else {
2245 ml_append(lnum, uep->ue_array[i], (colnr_T)0, false);
2246 }
2247 xfree(uep->ue_array[i]);
2248 }
2249 xfree((char_u *)uep->ue_array);
2250 }
2251
2252 /* adjust marks */
2253 if (oldsize != newsize) {
2254 mark_adjust(top + 1, top + oldsize, (long)MAXLNUM,
2255 (long)newsize - (long)oldsize, false);
2256 if (curbuf->b_op_start.lnum > top + oldsize) {
2257 curbuf->b_op_start.lnum += newsize - oldsize;
2258 }
2259 if (curbuf->b_op_end.lnum > top + oldsize) {
2260 curbuf->b_op_end.lnum += newsize - oldsize;
2261 }
2262 }
2263
2264 changed_lines(top + 1, 0, bot, newsize - oldsize, do_buf_event);
2265
2266 /* set '[ and '] mark */
2267 if (top + 1 < curbuf->b_op_start.lnum)
2268 curbuf->b_op_start.lnum = top + 1;
2269 if (newsize == 0 && top + 1 > curbuf->b_op_end.lnum)
2270 curbuf->b_op_end.lnum = top + 1;
2271 else if (top + newsize > curbuf->b_op_end.lnum)
2272 curbuf->b_op_end.lnum = top + newsize;
2273
2274 u_newcount += newsize;
2275 u_oldcount += oldsize;
2276 uep->ue_size = oldsize;
2277 uep->ue_array = newarray;
2278 uep->ue_bot = top + newsize + 1;
2279
2280 /*
2281 * insert this entry in front of the new entry list
2282 */
2283 nuep = uep->ue_next;
2284 uep->ue_next = newlist;
2285 newlist = uep;
2286 }
2287
2288 curhead->uh_entry = newlist;
2289 curhead->uh_flags = new_flags;
2290 if ((old_flags & UH_EMPTYBUF) && BUFEMPTY()) {
2291 curbuf->b_ml.ml_flags |= ML_EMPTY;
2292 }
2293 if (old_flags & UH_CHANGED) {
2294 changed();
2295 } else {
2296 unchanged(curbuf, false, true);
2297 }
2298
2299 // because the calls to changed()/unchanged() above will bump changedtick
2300 // again, we need to send a nvim_buf_lines_event with just the new value of
2301 // b:changedtick
2302 if (do_buf_event) {
2303 buf_updates_changedtick(curbuf);
2304 }
2305
2306 /*
2307 * restore marks from before undo/redo
2308 */
2309 for (i = 0; i < NMARKS; ++i) {
2310 if (curhead->uh_namedm[i].mark.lnum != 0) {
2311 free_fmark(curbuf->b_namedm[i]);
2312 curbuf->b_namedm[i] = curhead->uh_namedm[i];
2313 }
2314 if (namedm[i].mark.lnum != 0) {
2315 curhead->uh_namedm[i] = namedm[i];
2316 } else {
2317 curhead->uh_namedm[i].mark.lnum = 0;
2318 }
2319 }
2320 if (curhead->uh_visual.vi_start.lnum != 0) {
2321 curbuf->b_visual = curhead->uh_visual;
2322 curhead->uh_visual = visualinfo;
2323 }
2324
2325 /*
2326 * If the cursor is only off by one line, put it at the same position as
2327 * before starting the change (for the "o" command).
2328 * Otherwise the cursor should go to the first undone line.
2329 */
2330 if (curhead->uh_cursor.lnum + 1 == curwin->w_cursor.lnum
2331 && curwin->w_cursor.lnum > 1)
2332 --curwin->w_cursor.lnum;
2333 if (curwin->w_cursor.lnum <= curbuf->b_ml.ml_line_count) {
2334 if (curhead->uh_cursor.lnum == curwin->w_cursor.lnum) {
2335 curwin->w_cursor.col = curhead->uh_cursor.col;
2336 if (virtual_active() && curhead->uh_cursor_vcol >= 0)
2337 coladvance((colnr_T)curhead->uh_cursor_vcol);
2338 else
2339 curwin->w_cursor.coladd = 0;
2340 } else
2341 beginline(BL_SOL | BL_FIX);
2342 } else {
2343 /* We get here with the current cursor line being past the end (eg
2344 * after adding lines at the end of the file, and then undoing it).
2345 * check_cursor() will move the cursor to the last line. Move it to
2346 * the first column here. */
2347 curwin->w_cursor.col = 0;
2348 curwin->w_cursor.coladd = 0;
2349 }
2350
2351 /* Make sure the cursor is on an existing line and column. */
2352 check_cursor();
2353
2354 /* Remember where we are for "g-" and ":earlier 10s". */
2355 curbuf->b_u_seq_cur = curhead->uh_seq;
2356 if (undo)
2357 /* We are below the previous undo. However, to make ":earlier 1s"
2358 * work we compute this as being just above the just undone change. */
2359 curbuf->b_u_seq_cur = curhead->uh_next.ptr ?
2360 curhead->uh_next.ptr->uh_seq : 0;
2361
2362 /* Remember where we are for ":earlier 1f" and ":later 1f". */
2363 if (curhead->uh_save_nr != 0) {
2364 if (undo)
2365 curbuf->b_u_save_nr_cur = curhead->uh_save_nr - 1;
2366 else
2367 curbuf->b_u_save_nr_cur = curhead->uh_save_nr;
2368 }
2369
2370 /* The timestamp can be the same for multiple changes, just use the one of
2371 * the undone/redone change. */
2372 curbuf->b_u_time_cur = curhead->uh_time;
2373
2374 unblock_autocmds();
2375#ifdef U_DEBUG
2376 u_check(FALSE);
2377#endif
2378}
2379
2380/// If we deleted or added lines, report the number of less/more lines.
2381/// Otherwise, report the number of changes (this may be incorrect
2382/// in some cases, but it's better than nothing).
2383static void u_undo_end(
2384 bool did_undo, ///< just did an undo
2385 bool absolute, ///< used ":undo N"
2386 bool quiet)
2387{
2388 char *msgstr;
2389 u_header_T *uhp;
2390 char_u msgbuf[80];
2391
2392 if ((fdo_flags & FDO_UNDO) && KeyTyped)
2393 foldOpenCursor();
2394
2395 if (quiet
2396 || global_busy // no messages until global is finished
2397 || !messaging()) { // 'lazyredraw' set, don't do messages now
2398 return;
2399 }
2400
2401 if (curbuf->b_ml.ml_flags & ML_EMPTY)
2402 --u_newcount;
2403
2404 u_oldcount -= u_newcount;
2405 if (u_oldcount == -1)
2406 msgstr = N_("more line");
2407 else if (u_oldcount < 0)
2408 msgstr = N_("more lines");
2409 else if (u_oldcount == 1)
2410 msgstr = N_("line less");
2411 else if (u_oldcount > 1)
2412 msgstr = N_("fewer lines");
2413 else {
2414 u_oldcount = u_newcount;
2415 if (u_newcount == 1)
2416 msgstr = N_("change");
2417 else
2418 msgstr = N_("changes");
2419 }
2420
2421 if (curbuf->b_u_curhead != NULL) {
2422 /* For ":undo N" we prefer a "after #N" message. */
2423 if (absolute && curbuf->b_u_curhead->uh_next.ptr != NULL) {
2424 uhp = curbuf->b_u_curhead->uh_next.ptr;
2425 did_undo = false;
2426 } else if (did_undo) {
2427 uhp = curbuf->b_u_curhead;
2428 } else {
2429 uhp = curbuf->b_u_curhead->uh_next.ptr;
2430 }
2431 } else {
2432 uhp = curbuf->b_u_newhead;
2433 }
2434
2435 if (uhp == NULL)
2436 *msgbuf = NUL;
2437 else
2438 u_add_time(msgbuf, sizeof(msgbuf), uhp->uh_time);
2439
2440 {
2441 FOR_ALL_WINDOWS_IN_TAB(wp, curtab) {
2442 if (wp->w_buffer == curbuf && wp->w_p_cole > 0) {
2443 redraw_win_later(wp, NOT_VALID);
2444 }
2445 }
2446 }
2447
2448 smsg_attr_keep(
2449 0,
2450 _("%" PRId64 " %s; %s #%" PRId64 " %s"),
2451 u_oldcount < 0 ? (int64_t)-u_oldcount : (int64_t)u_oldcount,
2452 _(msgstr),
2453 did_undo ? _("before") : _("after"),
2454 uhp == NULL ? (int64_t)0L : (int64_t)uhp->uh_seq,
2455 msgbuf);
2456}
2457
2458/*
2459 * u_sync: stop adding to the current entry list
2460 */
2461void
2462u_sync(
2463 int force // Also sync when no_u_sync is set.
2464)
2465{
2466 /* Skip it when already synced or syncing is disabled. */
2467 if (curbuf->b_u_synced || (!force && no_u_sync > 0))
2468 return;
2469 if (get_undolevel() < 0)
2470 curbuf->b_u_synced = true; /* no entries, nothing to do */
2471 else {
2472 u_getbot(); /* compute ue_bot of previous u_save */
2473 curbuf->b_u_curhead = NULL;
2474 }
2475}
2476
2477/*
2478 * ":undolist": List the leafs of the undo tree
2479 */
2480void ex_undolist(exarg_T *eap)
2481{
2482 garray_T ga;
2483 u_header_T *uhp;
2484 int mark;
2485 int nomark;
2486 int changes = 1;
2487
2488 /*
2489 * 1: walk the tree to find all leafs, put the info in "ga".
2490 * 2: sort the lines
2491 * 3: display the list
2492 */
2493 mark = ++lastmark;
2494 nomark = ++lastmark;
2495 ga_init(&ga, (int)sizeof(char *), 20);
2496
2497 uhp = curbuf->b_u_oldhead;
2498 while (uhp != NULL) {
2499 if (uhp->uh_prev.ptr == NULL && uhp->uh_walk != nomark
2500 && uhp->uh_walk != mark) {
2501 vim_snprintf((char *)IObuff, IOSIZE, "%6ld %7d ",
2502 uhp->uh_seq, changes);
2503 u_add_time(IObuff + STRLEN(IObuff), IOSIZE - STRLEN(IObuff),
2504 uhp->uh_time);
2505 if (uhp->uh_save_nr > 0) {
2506 while (STRLEN(IObuff) < 33)
2507 STRCAT(IObuff, " ");
2508 vim_snprintf_add((char *)IObuff, IOSIZE,
2509 " %3ld", uhp->uh_save_nr);
2510 }
2511 GA_APPEND(char_u *, &ga, vim_strsave(IObuff));
2512 }
2513
2514 uhp->uh_walk = mark;
2515
2516 /* go down in the tree if we haven't been there */
2517 if (uhp->uh_prev.ptr != NULL && uhp->uh_prev.ptr->uh_walk != nomark
2518 && uhp->uh_prev.ptr->uh_walk != mark) {
2519 uhp = uhp->uh_prev.ptr;
2520 ++changes;
2521 }
2522 /* go to alternate branch if we haven't been there */
2523 else if (uhp->uh_alt_next.ptr != NULL
2524 && uhp->uh_alt_next.ptr->uh_walk != nomark
2525 && uhp->uh_alt_next.ptr->uh_walk != mark)
2526 uhp = uhp->uh_alt_next.ptr;
2527
2528 /* go up in the tree if we haven't been there and we are at the
2529 * start of alternate branches */
2530 else if (uhp->uh_next.ptr != NULL && uhp->uh_alt_prev.ptr == NULL
2531 && uhp->uh_next.ptr->uh_walk != nomark
2532 && uhp->uh_next.ptr->uh_walk != mark) {
2533 uhp = uhp->uh_next.ptr;
2534 --changes;
2535 } else {
2536 /* need to backtrack; mark this node as done */
2537 uhp->uh_walk = nomark;
2538 if (uhp->uh_alt_prev.ptr != NULL)
2539 uhp = uhp->uh_alt_prev.ptr;
2540 else {
2541 uhp = uhp->uh_next.ptr;
2542 --changes;
2543 }
2544 }
2545 }
2546
2547 if (GA_EMPTY(&ga))
2548 MSG(_("Nothing to undo"));
2549 else {
2550 sort_strings((char_u **)ga.ga_data, ga.ga_len);
2551
2552 msg_start();
2553 msg_puts_attr(_("number changes when saved"),
2554 HL_ATTR(HLF_T));
2555 for (int i = 0; i < ga.ga_len && !got_int; i++) {
2556 msg_putchar('\n');
2557 if (got_int) {
2558 break;
2559 }
2560 msg_puts(((const char **)ga.ga_data)[i]);
2561 }
2562 msg_end();
2563
2564 ga_clear_strings(&ga);
2565 }
2566}
2567
2568/*
2569 * Put the timestamp of an undo header in "buf[buflen]" in a nice format.
2570 */
2571static void u_add_time(char_u *buf, size_t buflen, time_t tt)
2572{
2573 struct tm curtime;
2574
2575 if (time(NULL) - tt >= 100) {
2576 os_localtime_r(&tt, &curtime);
2577 if (time(NULL) - tt < (60L * 60L * 12L))
2578 /* within 12 hours */
2579 (void)strftime((char *)buf, buflen, "%H:%M:%S", &curtime);
2580 else
2581 /* longer ago */
2582 (void)strftime((char *)buf, buflen, "%Y/%m/%d %H:%M:%S", &curtime);
2583 } else {
2584 int64_t seconds = time(NULL) - tt;
2585 vim_snprintf((char *)buf, buflen,
2586 NGETTEXT("%" PRId64 " second ago",
2587 "%" PRId64 " seconds ago", (uint32_t)seconds),
2588 seconds);
2589 }
2590}
2591
2592/*
2593 * ":undojoin": continue adding to the last entry list
2594 */
2595void ex_undojoin(exarg_T *eap)
2596{
2597 if (curbuf->b_u_newhead == NULL) {
2598 return; // nothing changed before
2599 }
2600 if (curbuf->b_u_curhead != NULL) {
2601 EMSG(_("E790: undojoin is not allowed after undo"));
2602 return;
2603 }
2604 if (!curbuf->b_u_synced) {
2605 return; // already unsynced
2606 }
2607 if (get_undolevel() < 0) {
2608 return; // no entries, nothing to do
2609 } else {
2610 curbuf->b_u_synced = false; // Append next change to last entry
2611 }
2612}
2613
2614/*
2615 * Called after writing or reloading the file and setting b_changed to FALSE.
2616 * Now an undo means that the buffer is modified.
2617 */
2618void u_unchanged(buf_T *buf)
2619{
2620 u_unch_branch(buf->b_u_oldhead);
2621 buf->b_did_warn = false;
2622}
2623
2624/*
2625 * After reloading a buffer which was saved for 'undoreload': Find the first
2626 * line that was changed and set the cursor there.
2627 */
2628void u_find_first_changed(void)
2629{
2630 u_header_T *uhp = curbuf->b_u_newhead;
2631 u_entry_T *uep;
2632 linenr_T lnum;
2633
2634 if (curbuf->b_u_curhead != NULL || uhp == NULL)
2635 return; /* undid something in an autocmd? */
2636
2637 /* Check that the last undo block was for the whole file. */
2638 uep = uhp->uh_entry;
2639 if (uep->ue_top != 0 || uep->ue_bot != 0)
2640 return;
2641
2642 for (lnum = 1; lnum < curbuf->b_ml.ml_line_count
2643 && lnum <= uep->ue_size; ++lnum)
2644 if (STRCMP(ml_get_buf(curbuf, lnum, FALSE),
2645 uep->ue_array[lnum - 1]) != 0) {
2646 clearpos(&(uhp->uh_cursor));
2647 uhp->uh_cursor.lnum = lnum;
2648 return;
2649 }
2650 if (curbuf->b_ml.ml_line_count != uep->ue_size) {
2651 /* lines added or deleted at the end, put the cursor there */
2652 clearpos(&(uhp->uh_cursor));
2653 uhp->uh_cursor.lnum = lnum;
2654 }
2655}
2656
2657/*
2658 * Increase the write count, store it in the last undo header, what would be
2659 * used for "u".
2660 */
2661void u_update_save_nr(buf_T *buf)
2662{
2663 u_header_T *uhp;
2664
2665 ++buf->b_u_save_nr_last;
2666 buf->b_u_save_nr_cur = buf->b_u_save_nr_last;
2667 uhp = buf->b_u_curhead;
2668 if (uhp != NULL)
2669 uhp = uhp->uh_next.ptr;
2670 else
2671 uhp = buf->b_u_newhead;
2672 if (uhp != NULL)
2673 uhp->uh_save_nr = buf->b_u_save_nr_last;
2674}
2675
2676static void u_unch_branch(u_header_T *uhp)
2677{
2678 u_header_T *uh;
2679
2680 for (uh = uhp; uh != NULL; uh = uh->uh_prev.ptr) {
2681 uh->uh_flags |= UH_CHANGED;
2682 if (uh->uh_alt_next.ptr != NULL)
2683 u_unch_branch(uh->uh_alt_next.ptr); /* recursive */
2684 }
2685}
2686
2687/*
2688 * Get pointer to last added entry.
2689 * If it's not valid, give an error message and return NULL.
2690 */
2691static u_entry_T *u_get_headentry(void)
2692{
2693 if (curbuf->b_u_newhead == NULL || curbuf->b_u_newhead->uh_entry == NULL) {
2694 IEMSG(_("E439: undo list corrupt"));
2695 return NULL;
2696 }
2697 return curbuf->b_u_newhead->uh_entry;
2698}
2699
2700/*
2701 * u_getbot(): compute the line number of the previous u_save
2702 * It is called only when b_u_synced is false.
2703 */
2704static void u_getbot(void)
2705{
2706 u_entry_T *uep;
2707 linenr_T extra;
2708
2709 uep = u_get_headentry(); /* check for corrupt undo list */
2710 if (uep == NULL)
2711 return;
2712
2713 uep = curbuf->b_u_newhead->uh_getbot_entry;
2714 if (uep != NULL) {
2715 /*
2716 * the new ue_bot is computed from the number of lines that has been
2717 * inserted (0 - deleted) since calling u_save. This is equal to the
2718 * old line count subtracted from the current line count.
2719 */
2720 extra = curbuf->b_ml.ml_line_count - uep->ue_lcount;
2721 uep->ue_bot = uep->ue_top + uep->ue_size + 1 + extra;
2722 if (uep->ue_bot < 1 || uep->ue_bot > curbuf->b_ml.ml_line_count) {
2723 IEMSG(_("E440: undo line missing"));
2724 uep->ue_bot = uep->ue_top + 1; // assume all lines deleted, will
2725 // get all the old lines back
2726 // without deleting the current
2727 // ones
2728 }
2729
2730 curbuf->b_u_newhead->uh_getbot_entry = NULL;
2731 }
2732
2733 curbuf->b_u_synced = true;
2734}
2735
2736/*
2737 * Free one header "uhp" and its entry list and adjust the pointers.
2738 */
2739static void
2740u_freeheader(
2741 buf_T *buf,
2742 u_header_T *uhp,
2743 u_header_T **uhpp // if not NULL reset when freeing this header
2744)
2745{
2746 u_header_T *uhap;
2747
2748 /* When there is an alternate redo list free that branch completely,
2749 * because we can never go there. */
2750 if (uhp->uh_alt_next.ptr != NULL)
2751 u_freebranch(buf, uhp->uh_alt_next.ptr, uhpp);
2752
2753 if (uhp->uh_alt_prev.ptr != NULL)
2754 uhp->uh_alt_prev.ptr->uh_alt_next.ptr = NULL;
2755
2756 /* Update the links in the list to remove the header. */
2757 if (uhp->uh_next.ptr == NULL)
2758 buf->b_u_oldhead = uhp->uh_prev.ptr;
2759 else
2760 uhp->uh_next.ptr->uh_prev.ptr = uhp->uh_prev.ptr;
2761
2762 if (uhp->uh_prev.ptr == NULL)
2763 buf->b_u_newhead = uhp->uh_next.ptr;
2764 else
2765 for (uhap = uhp->uh_prev.ptr; uhap != NULL;
2766 uhap = uhap->uh_alt_next.ptr)
2767 uhap->uh_next.ptr = uhp->uh_next.ptr;
2768
2769 u_freeentries(buf, uhp, uhpp);
2770}
2771
2772/*
2773 * Free an alternate branch and any following alternate branches.
2774 */
2775static void
2776u_freebranch(
2777 buf_T *buf,
2778 u_header_T *uhp,
2779 u_header_T **uhpp // if not NULL reset when freeing this header
2780)
2781{
2782 u_header_T *tofree, *next;
2783
2784 /* If this is the top branch we may need to use u_freeheader() to update
2785 * all the pointers. */
2786 if (uhp == buf->b_u_oldhead) {
2787 while (buf->b_u_oldhead != NULL)
2788 u_freeheader(buf, buf->b_u_oldhead, uhpp);
2789 return;
2790 }
2791
2792 if (uhp->uh_alt_prev.ptr != NULL)
2793 uhp->uh_alt_prev.ptr->uh_alt_next.ptr = NULL;
2794
2795 next = uhp;
2796 while (next != NULL) {
2797 tofree = next;
2798 if (tofree->uh_alt_next.ptr != NULL)
2799 u_freebranch(buf, tofree->uh_alt_next.ptr, uhpp); /* recursive */
2800 next = tofree->uh_prev.ptr;
2801 u_freeentries(buf, tofree, uhpp);
2802 }
2803}
2804
2805/*
2806 * Free all the undo entries for one header and the header itself.
2807 * This means that "uhp" is invalid when returning.
2808 */
2809static void
2810u_freeentries(
2811 buf_T *buf,
2812 u_header_T *uhp,
2813 u_header_T **uhpp // if not NULL reset when freeing this header
2814)
2815{
2816 u_entry_T *uep, *nuep;
2817
2818 /* Check for pointers to the header that become invalid now. */
2819 if (buf->b_u_curhead == uhp)
2820 buf->b_u_curhead = NULL;
2821 if (buf->b_u_newhead == uhp)
2822 buf->b_u_newhead = NULL; /* freeing the newest entry */
2823 if (uhpp != NULL && uhp == *uhpp)
2824 *uhpp = NULL;
2825
2826 for (uep = uhp->uh_entry; uep != NULL; uep = nuep) {
2827 nuep = uep->ue_next;
2828 u_freeentry(uep, uep->ue_size);
2829 }
2830
2831#ifdef U_DEBUG
2832 uhp->uh_magic = 0;
2833#endif
2834 xfree((char_u *)uhp);
2835 --buf->b_u_numhead;
2836}
2837
2838/*
2839 * free entry 'uep' and 'n' lines in uep->ue_array[]
2840 */
2841static void u_freeentry(u_entry_T *uep, long n)
2842{
2843 while (n > 0)
2844 xfree(uep->ue_array[--n]);
2845 xfree((char_u *)uep->ue_array);
2846#ifdef U_DEBUG
2847 uep->ue_magic = 0;
2848#endif
2849 xfree((char_u *)uep);
2850}
2851
2852/*
2853 * invalidate the undo buffer; called when storage has already been released
2854 */
2855void u_clearall(buf_T *buf)
2856{
2857 buf->b_u_newhead = buf->b_u_oldhead = buf->b_u_curhead = NULL;
2858 buf->b_u_synced = true;
2859 buf->b_u_numhead = 0;
2860 buf->b_u_line_ptr = NULL;
2861 buf->b_u_line_lnum = 0;
2862}
2863
2864/*
2865 * save the line "lnum" for the "U" command
2866 */
2867void u_saveline(linenr_T lnum)
2868{
2869 if (lnum == curbuf->b_u_line_lnum) /* line is already saved */
2870 return;
2871 if (lnum < 1 || lnum > curbuf->b_ml.ml_line_count) /* should never happen */
2872 return;
2873 u_clearline();
2874 curbuf->b_u_line_lnum = lnum;
2875 if (curwin->w_cursor.lnum == lnum)
2876 curbuf->b_u_line_colnr = curwin->w_cursor.col;
2877 else
2878 curbuf->b_u_line_colnr = 0;
2879 curbuf->b_u_line_ptr = u_save_line(lnum);
2880}
2881
2882/*
2883 * clear the line saved for the "U" command
2884 * (this is used externally for crossing a line while in insert mode)
2885 */
2886void u_clearline(void)
2887{
2888 if (curbuf->b_u_line_ptr != NULL) {
2889 XFREE_CLEAR(curbuf->b_u_line_ptr);
2890 curbuf->b_u_line_lnum = 0;
2891 }
2892}
2893
2894/*
2895 * Implementation of the "U" command.
2896 * Differentiation from vi: "U" can be undone with the next "U".
2897 * We also allow the cursor to be in another line.
2898 * Careful: may trigger autocommands that reload the buffer.
2899 */
2900void u_undoline(void)
2901{
2902 colnr_T t;
2903 char_u *oldp;
2904
2905 if (undo_off)
2906 return;
2907
2908 if (curbuf->b_u_line_ptr == NULL
2909 || curbuf->b_u_line_lnum > curbuf->b_ml.ml_line_count) {
2910 beep_flush();
2911 return;
2912 }
2913
2914 /* first save the line for the 'u' command */
2915 if (u_savecommon(curbuf->b_u_line_lnum - 1,
2916 curbuf->b_u_line_lnum + 1, (linenr_T)0, FALSE) == FAIL)
2917 return;
2918 oldp = u_save_line(curbuf->b_u_line_lnum);
2919 ml_replace(curbuf->b_u_line_lnum, curbuf->b_u_line_ptr, true);
2920 changed_bytes(curbuf->b_u_line_lnum, 0);
2921 xfree(curbuf->b_u_line_ptr);
2922 curbuf->b_u_line_ptr = oldp;
2923
2924 t = curbuf->b_u_line_colnr;
2925 if (curwin->w_cursor.lnum == curbuf->b_u_line_lnum)
2926 curbuf->b_u_line_colnr = curwin->w_cursor.col;
2927 curwin->w_cursor.col = t;
2928 curwin->w_cursor.lnum = curbuf->b_u_line_lnum;
2929 check_cursor_col();
2930}
2931
2932/*
2933 * Free all allocated memory blocks for the buffer 'buf'.
2934 */
2935void u_blockfree(buf_T *buf)
2936{
2937 while (buf->b_u_oldhead != NULL) {
2938#ifndef NDEBUG
2939 u_header_T *previous_oldhead = buf->b_u_oldhead;
2940#endif
2941
2942 u_freeheader(buf, buf->b_u_oldhead, NULL);
2943 assert(buf->b_u_oldhead != previous_oldhead);
2944 }
2945 xfree(buf->b_u_line_ptr);
2946}
2947
2948/*
2949 * u_save_line(): allocate memory and copy line 'lnum' into it.
2950 */
2951static char_u *u_save_line(linenr_T lnum)
2952{
2953 return vim_strsave(ml_get(lnum));
2954}
2955
2956/// Check if the 'modified' flag is set, or 'ff' has changed (only need to
2957/// check the first character, because it can only be "dos", "unix" or "mac").
2958/// "nofile" and "scratch" type buffers are considered to always be unchanged.
2959///
2960/// @param buf The buffer to check
2961///
2962/// @return true if the buffer has changed
2963bool bufIsChanged(buf_T *buf)
2964 FUNC_ATTR_NONNULL_ALL FUNC_ATTR_WARN_UNUSED_RESULT
2965{
2966 return !bt_dontwrite(buf) && (buf->b_changed || file_ff_differs(buf, true));
2967}
2968
2969// Return true if any buffer has changes. Also buffers that are not written.
2970bool anyBufIsChanged(void)
2971 FUNC_ATTR_WARN_UNUSED_RESULT
2972{
2973 FOR_ALL_BUFFERS(buf) {
2974 if (bufIsChanged(buf)) {
2975 return true;
2976 }
2977 }
2978 return false;
2979}
2980
2981/// @see bufIsChanged
2982/// @return true if the current buffer has changed
2983bool curbufIsChanged(void)
2984 FUNC_ATTR_WARN_UNUSED_RESULT
2985{
2986 return bufIsChanged(curbuf);
2987}
2988
2989/// Append the list of undo blocks to a newly allocated list
2990///
2991/// For use in undotree(). Recursive.
2992///
2993/// @param[in] first_uhp Undo blocks list to start with.
2994///
2995/// @return [allocated] List with a representation of undo blocks.
2996list_T *u_eval_tree(const u_header_T *const first_uhp)
2997 FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_RET
2998{
2999 list_T *const list = tv_list_alloc(kListLenMayKnow);
3000
3001 for (const u_header_T *uhp = first_uhp; uhp != NULL; uhp = uhp->uh_prev.ptr) {
3002 dict_T *const dict = tv_dict_alloc();
3003 tv_dict_add_nr(dict, S_LEN("seq"), (varnumber_T)uhp->uh_seq);
3004 tv_dict_add_nr(dict, S_LEN("time"), (varnumber_T)uhp->uh_time);
3005 if (uhp == curbuf->b_u_newhead) {
3006 tv_dict_add_nr(dict, S_LEN("newhead"), 1);
3007 }
3008 if (uhp == curbuf->b_u_curhead) {
3009 tv_dict_add_nr(dict, S_LEN("curhead"), 1);
3010 }
3011 if (uhp->uh_save_nr > 0) {
3012 tv_dict_add_nr(dict, S_LEN("save"), (varnumber_T)uhp->uh_save_nr);
3013 }
3014
3015 if (uhp->uh_alt_next.ptr != NULL) {
3016 // Recursive call to add alternate undo tree.
3017 tv_dict_add_list(dict, S_LEN("alt"), u_eval_tree(uhp->uh_alt_next.ptr));
3018 }
3019
3020 tv_list_append_dict(list, dict);
3021 }
3022
3023 return list;
3024}
3025