core-mark.c

   1 /*
   2  * Copyright Neil Brown ©2015-2023 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * Marks and Points.
   6  *
   7  * A 'Mark' is a reference to a location in a text.  The location
   8  * is between two characters and remains there while characters
   9  * are added or removed before or after.
  10  * All marks are linked together in text order and are assigned
  11  * sparse ordered numbers so that it is easy to determine the
  12  * relative order of two points.
  13  *
  14  * Each mark is optionally in two lists.  There is one list that
  15  * contains all marks on a given text, and arbitrary other lists
  16  * that contain only select marks.  A given mark can only be in one
  17  * of these extra lists - except for points which are described below.
  18  *
  19  * A mark has a list of attributes and a pointer to a handler
  20  * which can be called in various circumstances to customise
  21  * handling of different sections of text.
  22  *
  23  * A 'point' is a special mark which identifies a place where
  24  * things can happen.  Text can be added or removed, marks can
  25  * be created or destroyed, only at a 'point'.
  26  * A 'point' is on all lists.  This allows nearby marks on any list to be
  27  * found quickly.
  28  *
  29  * As the 'group' lists can hold either marks or points, and with a
  30  * different anchor in each, we use 'tlist_head'.  Pointers in a
  31  * tlist use the bottom 2 bits to store a type.  We only have
  32  * two types: mark or point.  When we find a point we know which of the
  33  * various lists because we know the index of the list we are walking.
  34  *
  35  * The text buffer can only be modified at a point.
  36  * Prior to deleting text, all marks/points must be moved off the removed
  37  * section.  After adding text ... something.
  38  *
  39  * A mark or point can be deleted at any time with impunity.
  40  * A point can be duplicated, or can fork a mark.  When this happens
  41  * we might need to re-assign some seq numbers to keep them sparse.
  42  * A point can move forward or backward, or can jump to a mark.
  43  * When that happens, various lists might need to be adjusted and
  44  * seq number might need to be reassigned.
  45  *
  46  * There can only be one (non-borrowed) reference to a mark.  So
  47  * a second reference is wanted, the mark must be duplicated.
  48  * How these references are stored is not yet clear.  Maybe that is
  49  * up to whatever module uses it.
  50  *
  51  * Each mark has a 'type' identifying which group it is of.
  52  * Type -1 is points.  They aren't like other groups.
  53  * Other types(groups) can be defined as needed
  54  * The number is an index into text->groups and point->lists.
  55  *
  56  * This is distinct from the type used by the tlist to differentiate
  57  * points the location of the tlist_head.  There 'GRP_MARK' is the 'group'
  58  * in each mark of that group, and 'GRP_LIST' is the 'lists[n]' in each
  59  * point.  GRP_HEAD is the head of the list.
  60  */
  61
  62 #include <unistd.h>
  63 #include <stdlib.h>
  64 #include <memory.h>
  65
  66 #define DOC_DATA_TYPE struct doc
  67 #include "core.h"
  68 #include "core-pane.h"
  69 #include "internal.h"
  70 #include "misc.h"
  71
  72 static MEMPOOL(mark);
  73
  74 static struct mark *vmark_or_point_next(struct mark *m safe, int view);
  75 static struct mark *vmark_or_point_prev(struct mark *m safe, int view);
  76
  77 /* seq numbers added to the end are given a gap of 128.
  78  * seq numbers at other locations are placed at mean of before and after.
  79  * If there is no room, seq add 256 to the 'next' seq, 255 to the one
  80  * after etc until we find a seq already above the target, or reach
  81  * gap size of 64. In later case we continue with fixed gap size.
  82  */
  83 static void assign_seq(struct mark *m safe)
  84 {
  85         struct mark *p, *n;
  86         int gap = 256;
  87
  88         n = mark_next(m);
  89         p = mark_prev(m);
  90         if (!n && !p) {
  91                 /* First mark: start in the middle */
  92                 m->seq = INT_MAX/2;
  93                 return;
  94         }
  95         while (--gap >= 2) {
  96                 if (n && p && n->seq - p->seq >= 2) {
  97                         /* There is room here, so insert */
  98                         m->seq = p->seq + (n->seq - p->seq)/2;
  99                         return;
 100                 }
 101                 if (!n && p->seq < INT_MAX - 1) {
 102                         if (INT_MAX - p->seq < gap)
 103                                 gap = INT_MAX - p->seq;
 104                         m->seq = p->seq + gap / 2;
 105                         return;
 106                 }
 107                 if (!p && n->seq > 1) {
 108                         if (n->seq < gap)
 109                                 gap = n->seq;
 110                         m->seq = n->seq - gap / 2;
 111                         return;
 112                 }
 113
 114                 /* We are between two marks with no room for a seq number,
 115                  * need to reshuffle and try to find space somewhere.
 116                  * Try to spread out the current marks more so there is
 117                  * 'gap' space between them, but let 'gap' decrease as we
 118                  * go to avoid pushing too hard.
 119                  */
 120                 if (p && n && p->seq > INT_MAX / 2) {
 121                         while (p && n->seq - p->seq < gap) {
 122                                 /* step back to 'p' and leave 'm' with a larger
 123                                  * gap.
 124                                  */
 125                                 if (n->seq > gap)
 126                                         m->seq = n->seq - gap;
 127                                 else if (n->seq > 0)
 128                                         m->seq = n->seq - 1;
 129                                 else
 130                                         m->seq = 0; /* Ouch! */
 131                                 n = m;
 132                                 m = p;
 133                                 p = mark_prev(p);
 134                                 if (gap > 4)
 135                                         gap -= 1;
 136                         }
 137                 } else if (p) {
 138                         while (n && n->seq - p->seq < gap) {
 139                                 if (INT_MAX - p->seq > gap)
 140                                         m->seq = p->seq + gap;
 141                                 else if (p->seq < INT_MAX)
 142                                         m->seq = p->seq + 1;
 143                                 else
 144                                         m->seq = INT_MAX; /* Ouch! */
 145                                 p = m;
 146                                 m = n;
 147                                 n = mark_next(n);
 148                                 if (gap > 4)
 149                                         gap -= 1;
 150                         }
 151                 }
 152                 /* NOTE: p->seq may now exceed n->seq, and
 153                  * there might be adjacent seq numbers if we hit 0 or INT_MAX.
 154                  * These will be fixed up on next loop through.
 155                  */
 156         }
 157         /* We must have scanned all the way to one end, and all the way to the
 158          * other, and found no space, so 4 billion marks.  Seems unlikely.
 159          */
 160         abort();
 161 }
 162
 163 static void point_free(struct mark *p safe)
 164 {
 165         unsigned int i;
 166         struct point_links *lnk = safe_cast p->mdata;
 167         for (i = 0; i < lnk->size; i++)
 168                 tlist_del_init(&lnk->lists[i]);
 169         unalloc_buf(p->mdata, sizeof(*lnk) + lnk->size * sizeof(lnk->lists[0]),
 170                     mark);
 171 }
 172
 173 void do_mark_free(struct mark *m)
 174 {
 175         unalloc(m, mark);
 176 }
 177
 178 static void mark_refcnt(struct mark *m safe, int inc)
 179 {
 180         struct doc *d = &m->owner->doc;
 181
 182         if (d->refcnt)
 183                 d->refcnt(m, inc);
 184 }
 185
 186 void mark_free(struct mark *m)
 187 {
 188         struct pane *owner;
 189
 190         /* mark might have already been freed by the
 191          * pane getting closed.
 192          */
 193         if (!mark_valid(m))
 194                 return;
 195         if (m->viewnum == MARK_POINT)
 196                 point_free(m);
 197         ASSERT(m->mdata == NULL);
 198
 199         hlist_del_init(&m->all);
 200         if (m->viewnum != MARK_UNGROUPED)
 201                 tlist_del_init(&m->view);
 202         attr_free(&m->attrs);
 203
 204         mark_refcnt(m, -1);
 205         owner = m->owner;
 206         memset(m, 0xff, sizeof(*m));
 207         m->owner = owner;
 208         owner->marks -= 1;
 209         m->viewnum = MARK_UNGROUPED;
 210         editor_delayed_mark_free(m);
 211 }
 212
 213 static void notify_mark_moving(struct mark *m safe, struct mark *m2)
 214 {
 215         if (m->flags & MARK_FLAG_WATCHED) {
 216                 m->flags &= ~MARK_FLAG_WATCHED;
 217                 pane_notify("mark:moving", m->owner, 0, m);
 218         }
 219
 220         if (m2 && (m2->flags & MARK_FLAG_WATCHED))
 221                 pane_notify("mark:arrived", m->owner, 0, m, NULL, 0, m2);
 222 }
 223
 224 void mark_watch(struct mark *m)
 225 {
 226         if (m)
 227                 m->flags |= MARK_FLAG_WATCHED;
 228 }
 229
 230 static void mark_ref_copy(struct mark *to safe, struct mark *from safe)
 231 {
 232         if (!mark_valid(to) || !mark_valid(from))
 233                 return;
 234
 235         if ((void*)to->owner && to->owner != from->owner) {
 236                 LOG("mark_ref_copy given marks with different owners");
 237                 return;
 238         }
 239         if (!(void*)to->owner) {
 240                 from->owner->marks += 1;
 241                 ASSERT(from->owner->marks < 20000000);
 242         }
 243         to->owner = from->owner;
 244         if (to->ref.p == from->ref.p &&
 245             to->ref.i == from->ref.i)
 246                 return;
 247         mark_refcnt(to, -1);
 248         to->ref = from->ref;
 249         mark_refcnt(to, 1);
 250 }
 251
 252 static void dup_mark(struct mark *orig safe, struct mark *new safe)
 253 {
 254         hlist_add_after(&orig->all, &new->all);
 255         INIT_TLIST_HEAD(&new->view, GRP_MARK);
 256         new->attrs = NULL;
 257         new->flags = 0;
 258         assign_seq(new);
 259         mark_ref_copy(new, orig);
 260 }
 261
 262 struct mark *do_mark_at_point(struct mark *pt safe, int view)
 263 {
 264         struct mark *ret;
 265         struct point_links *lnk;
 266
 267         if (pt->viewnum != MARK_POINT)
 268                 return NULL;
 269         lnk = safe_cast pt->mdata;
 270
 271         alloc(ret, mark);
 272
 273         dup_mark(pt, ret);
 274         ret->viewnum = view;
 275         if (view >= 0)
 276                 tlist_add(&ret->view, GRP_MARK, &lnk->lists[view]);
 277         else
 278                 INIT_TLIST_HEAD(&ret->view, GRP_MARK);
 279         notify_mark_moving(ret, pt);
 280         return ret;
 281 }
 282
 283 struct mark *mark_at_point(struct pane *p safe, struct mark *pm, int view)
 284 {
 285         return call_ret(mark, "doc:dup-point", p, 0, pm, NULL, view);
 286 }
 287
 288 struct mark *safe point_dup(struct mark *p safe)
 289 {
 290         unsigned int i;
 291         struct point_links *old = safe_cast p->mdata;
 292         struct mark *ret;
 293         struct point_links *lnk;
 294
 295         alloc(ret, mark);
 296         lnk = alloc_buf(sizeof(*lnk) + old->size * sizeof(lnk->lists[0]),
 297                         mark);
 298
 299         dup_mark(p, ret);
 300         ret->viewnum = MARK_POINT;
 301         ret->mdata = lnk;
 302         lnk->size = old->size;
 303         lnk->pt = ret;
 304         tlist_add(&ret->view, GRP_MARK, &p->view);
 305         for (i = 0; lnk && i < lnk->size; i++)
 306                 if (tlist_empty(&old->lists[i]))
 307                         INIT_TLIST_HEAD(&lnk->lists[i], GRP_LIST);
 308                 else
 309                         tlist_add(&lnk->lists[i], GRP_LIST, &old->lists[i]);
 310         notify_mark_moving(ret, p);
 311         return ret;
 312 }
 313
 314 void points_resize(struct doc *d safe)
 315 {
 316         struct mark *p;
 317         tlist_for_each_entry(p, &d->points, view) {
 318                 unsigned int i;
 319                 struct point_links *old = safe_cast p->mdata;
 320                 struct point_links *new = alloc_buf(sizeof(*new) +
 321                                                     d->nviews *
 322                                                     sizeof(new->lists[0]),
 323                                                     mark);
 324                 new->pt = p;
 325                 new->size = d->nviews;
 326                 p->mdata = new;
 327                 for (i = 0; i < old->size; i++) {
 328                         tlist_add(&new->lists[i], GRP_LIST, &old->lists[i]);
 329                         tlist_del(&old->lists[i]);
 330                 }
 331                 for (; i < new->size; i++)
 332                         INIT_TLIST_HEAD(&new->lists[i], GRP_HEAD);
 333                 free(old);
 334         }
 335 }
 336
 337 void points_attach(struct doc *d safe, int view)
 338 {
 339         struct mark *p;
 340         tlist_for_each_entry(p, &d->points, view) {
 341                 struct point_links *lnk = safe_cast p->mdata;
 342                 tlist_add_tail(&lnk->lists[view], GRP_LIST,
 343                                &d->views[view].head);
 344         }
 345 }
 346
 347 struct mark *safe mark_dup(struct mark *m safe)
 348 {
 349         struct mark *ret;
 350
 351         if (!mark_valid(m))
 352                 return m;
 353
 354         alloc(ret, mark);
 355         dup_mark(m, ret);
 356         ret->viewnum = MARK_UNGROUPED;
 357         INIT_TLIST_HEAD(&ret->view, GRP_MARK);
 358         notify_mark_moving(ret, m);
 359         return ret;
 360 }
 361
 362 struct mark *safe mark_dup_view(struct mark *m safe)
 363 {
 364         struct mark *ret;
 365
 366         if (!mark_valid(m))
 367                 return m;
 368
 369         if (m->viewnum == MARK_POINT)
 370                 return point_dup(m);
 371
 372         alloc(ret, mark);
 373         dup_mark(m, ret);
 374         if (m->viewnum == MARK_POINT) abort();
 375         ret->viewnum = m->viewnum;
 376         if (ret->viewnum == MARK_UNGROUPED)
 377                 INIT_TLIST_HEAD(&ret->view, GRP_MARK);
 378         else
 379                 tlist_add(&ret->view, GRP_MARK, &m->view);
 380         notify_mark_moving(ret, m);
 381         return ret;
 382 }
 383
 384 /* if 'end', move mark after all other marks, else move before all others */
 385 void mark_to_end(struct pane *p safe, struct mark *m safe, int end)
 386 {
 387         struct doc *d = &p->doc;
 388         unsigned int i;
 389         struct point_links *lnk;
 390
 391         if (!mark_valid(m))
 392                 return;
 393
 394         ASSERT(m->owner == p);
 395         notify_mark_moving(m, NULL);
 396
 397         hlist_del(&m->all);
 398         if (end) {
 399                 if (hlist_empty(&d->marks))
 400                         hlist_add_head(&m->all, &d->marks);
 401                 else {
 402                         struct mark *last = hlist_first_entry(&d->marks,
 403                                                               struct mark, all);
 404                         while (last->all.next)
 405                                 last = hlist_next_entry(last, all);
 406                         hlist_add_after(&last->all, &m->all);
 407                 }
 408         } else
 409                 hlist_add_head(&m->all, &d->marks);
 410         assign_seq(m);
 411
 412         if (m->viewnum == MARK_UNGROUPED)
 413                 return;
 414         if (m->viewnum != MARK_POINT) {
 415                 tlist_del(&m->view);
 416                 if (end)
 417                         tlist_add_tail(&m->view, GRP_MARK,
 418                                        &d->views[m->viewnum].head);
 419                 else
 420                         tlist_add(&m->view, GRP_MARK,
 421                                   &d->views[m->viewnum].head);
 422                 return;
 423         }
 424         /* MARK_POINT */
 425         tlist_del(&m->view);
 426         if (end)
 427                 tlist_add_tail(&m->view, GRP_MARK, &d->points);
 428         else
 429                 tlist_add(&m->view, GRP_MARK, &d->points);
 430
 431         lnk = safe_cast m->mdata;
 432         for (i = 0; d->views && i < lnk->size; i++)
 433                 if (d->views[i].owner) {
 434                         tlist_del(&lnk->lists[i]);
 435                         if (end)
 436                                 tlist_add_tail(&lnk->lists[i], GRP_LIST,
 437                                                &d->views[i].head);
 438                         else
 439                                 tlist_add(&lnk->lists[i],
 440                                           GRP_LIST, &d->views[i].head);
 441                 }
 442 }
 443
 444 void mark_reset(struct pane *p safe, struct mark *m safe, int end)
 445 {
 446         ASSERT((void*)m->owner == NULL || m->owner == p);
 447
 448         if (!mark_valid(m))
 449                 return;
 450
 451         if (!(void*)m->owner) {
 452                 p->marks += 1;
 453                 ASSERT(p->marks < 20000000);
 454         }
 455         m->owner = p;
 456         pane_call(p, "doc:set-ref", p, !end, m);
 457 }
 458
 459 struct mark *mark_first(struct doc *d safe)
 460 {
 461         if (!hlist_empty(&d->marks))
 462                 return hlist_first_entry(&d->marks, struct mark, all);
 463         return NULL;
 464 }
 465
 466 struct mark *mark_next(struct mark *m safe)
 467 {
 468         if (mark_valid(m) && m->all.next)
 469                 return hlist_next_entry(m, all);
 470         return NULL;
 471 }
 472
 473 struct mark *mark_prev(struct mark *m safe)
 474 {
 475         if (mark_valid(m) && !HLIST_IS_HEAD(m->all.pprev))
 476                 return hlist_prev_entry(m, all);
 477         return NULL;
 478 }
 479
 480 struct mark *doc_new_mark(struct pane *p safe, int view, struct pane *owner)
 481 {
 482         /* FIXME view is >= -1 */
 483         struct mark *ret;
 484         struct doc *d = &p->doc;
 485
 486         if (view >= d->nviews ||
 487             view < MARK_UNGROUPED ||
 488             (view >= 0 && (!d->views || d->views[view].owner != owner))) {
 489                 /* Erroneous call, or race with document closing down */
 490                 return NULL;
 491         }
 492         alloc(ret, mark);
 493         INIT_HLIST_NODE(&ret->all);
 494         INIT_TLIST_HEAD(&ret->view, GRP_MARK);
 495         ret->viewnum = view;
 496         hlist_add_head(&ret->all, &d->marks);
 497
 498         if (view == MARK_POINT) {
 499                 struct point_links *lnk = alloc_buf(sizeof(*lnk) +
 500                                                     d->nviews *
 501                                                     sizeof(lnk->lists[0]),
 502                                                     mark);
 503                 int i;
 504
 505                 lnk->size = d->nviews;
 506                 lnk->pt = ret;
 507                 for (i = 0; i < d->nviews; i++)
 508                         INIT_TLIST_HEAD(&lnk->lists[i], GRP_LIST);
 509                 ret->mdata = lnk;
 510         }
 511         mark_reset(p, ret, 0);
 512         if (hlist_unhashed(&ret->all)) {
 513                 /* Document misbehaved, fail gracefully */
 514                 mark_free(ret);
 515                 return NULL;
 516         }
 517         return ret;
 518 }
 519
 520 /* Movement of points and marks.
 521  *
 522  * Both points and marks can move.
 523  * Marks can move forward or backward one character. They only
 524  * step over other marks if they have to.
 525  * To move a mark to another mark of the same group, or to a
 526  * point, the mark needs to be deleted and a new one created.
 527  * Points can step fore/back like marks.  They can jump to another
 528  * point easily but to move to mark they must walk one mark at a time.
 529  *
 530  * Note that 'm' isn't 'safe' - A NULL mark will be step to point
 531  * by the doc redirector.
 532  */
 533
 534 wint_t do_doc_step(struct pane *p safe, struct mark *m,
 535                    int forward, int move)
 536 {
 537         int ret;
 538         static int dodebug = -1;
 539         static int count;
 540
 541         if (dodebug < 0)
 542                 dodebug = atoi(getenv("EDLIB_DEBUG_MARKS")?:"10000");
 543
 544         if (m && dodebug && count++ >= dodebug) {
 545                 count = 0;
 546                 doc_check_consistent(&m->owner->doc);
 547         }
 548
 549         if (move)
 550                 ret = call("doc:char", p, forward ? 1 : -1, m);
 551         else
 552                 ret = call("doc:char", p, 0, m, NULL, forward ? 1 : -1);
 553         if (ret <= 0)
 554                 return WEOF;
 555         if ((unsigned)ret >= CHAR_RET(WEOF))
 556                 return WEOF;
 557         else
 558                 return ret & 0x1fffff;
 559 }
 560
 561 /* Move the point so it is at the same location as the mark, both in the
 562  * text.
 563  * Firstly find the point closest to the mark, though that will often
 564  * be the point we already have.
 565  * Then for each mark group we find the last that is before the target,
 566  * and move the point to there.
 567  * Then update 'all' list, text ref and seq number.
 568  */
 569
 570 static void point_forward_to_mark(struct mark *p safe, struct mark *m safe)
 571 {
 572         struct mark *ptmp, *pnear;
 573         unsigned int i;
 574         struct point_links *plnk = safe_cast p->mdata;
 575
 576         pnear = p;
 577         ptmp = p;
 578         tlist_for_each_entry_continue(ptmp, GRP_HEAD, view) {
 579                 if (ptmp->seq <= m->seq)
 580                         pnear = ptmp;
 581                 else
 582                         break;
 583         }
 584         /* pnear is the nearest point to m that is before m. So
 585          * move p after pnear in the point list. */
 586         if (p != pnear) {
 587                 tlist_del(&p->view);
 588                 tlist_add(&p->view, GRP_MARK, &pnear->view);
 589         }
 590
 591         /* Now move 'p' in the various mark lists */
 592         for (i = 0; i < plnk->size; i++) {
 593                 struct mark *mnear = NULL;
 594                 struct tlist_head *tl;
 595                 struct point_links *pnlnk = safe_cast pnear->mdata;
 596
 597                 tl = &pnlnk->lists[i];
 598                 if (tlist_empty(tl))
 599                         continue;
 600                 tlist_for_each_continue(tl,  GRP_HEAD) {
 601                         struct mark *mtmp;
 602                         if (TLIST_TYPE(tl) != GRP_MARK)
 603                                 break;
 604                         mtmp = container_of(tl, struct mark, view);
 605                         if (mtmp->seq <= m->seq)
 606                                 mnear = mtmp;
 607                         else
 608                                 break;
 609                 }
 610                 if (mnear) {
 611                         tlist_del(&plnk->lists[i]);
 612                         tlist_add(&plnk->lists[i], GRP_LIST, &mnear->view);
 613                 } else if (p != pnear) {
 614                         tlist_del(&plnk->lists[i]);
 615                         tlist_add(&plnk->lists[i], GRP_LIST, &pnlnk->lists[i]);
 616                 }
 617         }
 618         /* finally move in the overall list */
 619         hlist_del(&p->all);
 620         hlist_add_after(&m->all, &p->all);
 621         assign_seq(p);
 622 }
 623
 624 static void point_backward_to_mark(struct mark *p safe, struct mark *m safe)
 625 {
 626         struct mark *ptmp, *pnear;
 627         unsigned int i;
 628         struct point_links *plnk = safe_cast p->mdata;
 629
 630         pnear = p;
 631         ptmp = p;
 632         tlist_for_each_entry_continue_reverse(ptmp, GRP_HEAD, view) {
 633                 if (ptmp->seq >= m->seq)
 634                         pnear = ptmp;
 635                 else
 636                         break;
 637         }
 638         /* pnear is the nearest point to m that is after m. So
 639          * move p before pnear in the point list */
 640         if (p != pnear) {
 641                 tlist_del(&p->view);
 642                 tlist_add_tail(&p->view, GRP_MARK, &pnear->view);
 643         }
 644
 645         /* Now move 'p' in the various mark lists */
 646         for (i = 0; i < plnk->size; i++) {
 647                 struct mark *mnear = NULL;
 648                 struct tlist_head *tl;
 649                 struct point_links *pnlnk = safe_cast pnear->mdata;
 650
 651                 tl = &pnlnk->lists[i];
 652                 if (tlist_empty(tl))
 653                         continue;
 654                 tlist_for_each_continue_reverse(tl, GRP_HEAD) {
 655                         struct mark *mtmp;
 656                         if (TLIST_TYPE(tl) != GRP_MARK)
 657                                 break;
 658                         mtmp = container_of(tl, struct mark, view);
 659                         if (mtmp->seq >= m->seq)
 660                                 mnear = mtmp;
 661                         else
 662                                 break;
 663                 }
 664                 if (mnear) {
 665                         tlist_del(&plnk->lists[i]);
 666                         tlist_add_tail(&plnk->lists[i], GRP_LIST, &mnear->view);
 667                 } else if (p != pnear) {
 668                         tlist_del(&plnk->lists[i]);
 669                         tlist_add_tail(&plnk->lists[i], GRP_LIST,
 670                                        &pnlnk->lists[i]);
 671                 }
 672         }
 673         /* finally move in the overall list */
 674         hlist_del(&p->all);
 675         hlist_add_before(&p->all, &m->all);
 676         assign_seq(p);
 677 }
 678
 679 static void _mark_to_mark_noref(struct mark *m safe, struct mark *target safe)
 680 {
 681         /* DEBUG: Make sure they are on same list */
 682         struct mark *a = m, *b = target;
 683
 684         if (!mark_valid(m) || !mark_valid(target))
 685                 return;
 686         if (a->owner != b->owner)
 687                 LOG("mark_to_mark: marks have different owners");
 688         else {
 689                 if (m->seq > target->seq) {
 690                         a = target; b = m;
 691                 }
 692                 while (a && a != b)
 693                         a = mark_next(a);
 694                 if (a != b)
 695                         LOG("mark_to_mark with marks on different list - same owner");
 696         }
 697         if (a != b) {
 698                 call("editor:notify:Message:broadcast",
 699                      m->owner, 0, NULL,
 700                      "WARNING marks inconsistent - see log");
 701                 return;
 702         }
 703         /* END DEBUG */
 704
 705         if (m == target)
 706                 return;
 707         if (!mark_same(m, target))
 708                 notify_mark_moving(m, target);
 709         if (m->viewnum == MARK_POINT) {
 710                 /* Lots of linkage to fix up */
 711                 if (m->seq < target->seq)
 712                         point_forward_to_mark(m, target);
 713                 else if (m->seq > target->seq)
 714                         point_backward_to_mark(m, target);
 715                 return;
 716         }
 717         if (m->viewnum == MARK_UNGROUPED) {
 718                 /* Only one linked list to worry about */
 719                 if (m->seq < target->seq) {
 720                         hlist_del(&m->all);
 721                         hlist_add_after(&target->all, &m->all);
 722                         assign_seq(m);
 723                 } else {
 724                         hlist_del(&m->all);
 725                         hlist_add_before(&m->all, &target->all);
 726                         m->seq = target->seq;
 727                         assign_seq(target);
 728                 }
 729                 return;
 730         }
 731         if (m->viewnum == target->viewnum) {
 732                 /* Same view, both on the same 2 lists */
 733                 if (m->seq < target->seq) {
 734                         hlist_del(&m->all);
 735                         hlist_add_after(&target->all, &m->all);
 736                         tlist_del(&m->view);
 737                         tlist_add(&m->view, GRP_MARK, &target->view);
 738                         assign_seq(m);
 739                 } else {
 740                         hlist_del(&m->all);
 741                         hlist_add_before(&m->all, &target->all);
 742                         tlist_del(&m->view);
 743                         tlist_add_tail(&m->view, GRP_MARK, &target->view);
 744                         m->seq = target->seq;
 745                         assign_seq(target);
 746                 }
 747                 return;
 748         }
 749         if (target->viewnum == MARK_POINT) {
 750                 /* A vmark and a point, both on the only 2 lists
 751                  * that need changing */
 752                 struct point_links *lnks = safe_cast target->mdata;
 753                 if (m->seq < target->seq) {
 754                         hlist_del(&m->all);
 755                         hlist_add_after(&target->all, &m->all);
 756                         tlist_del(&m->view);
 757                         tlist_add(&m->view, GRP_MARK, &lnks->lists[m->viewnum]);
 758                         assign_seq(m);
 759                 } else {
 760                         hlist_del(&m->all);
 761                         hlist_add_before(&m->all, &target->all);
 762                         tlist_del(&m->view);
 763                         tlist_add_tail(&m->view, GRP_MARK,
 764                                        &lnks->lists[m->viewnum]);
 765                         m->seq = target->seq;
 766                         assign_seq(target);
 767                 }
 768                 return;
 769         }
 770         /* Hard case: We have a vmark and a mark which isn't on the same list.
 771          * We need to find a matching vmark 'close' to the destination and link
 772          * after that.
 773          */
 774         if (m->seq < target->seq) {
 775                 struct mark *m1 = m, *n;
 776                 while ((n = vmark_or_point_next(m1, m->viewnum)) != NULL &&
 777                        n->seq <= target->seq)
 778                         m1 = n;
 779                 if (m1 != m) {
 780                         tlist_del(&m->view);
 781                         if (m1->viewnum == MARK_POINT) {
 782                                 struct point_links *lnks = safe_cast m1->mdata;
 783                                 tlist_add(&m->view, GRP_MARK,
 784                                           &lnks->lists[m->viewnum]);
 785                         } else
 786                                 tlist_add(&m->view, GRP_MARK, &m1->view);
 787                 }
 788                 hlist_del(&m->all);
 789                 hlist_add_after(&target->all, &m->all);
 790                 assign_seq(m);
 791         } else {
 792                 struct mark *m1 = m, *n;
 793                 while ((n = vmark_or_point_prev(m1, m->viewnum)) != NULL &&
 794                        n->seq >= target->seq)
 795                         m1 = n;
 796                 if (m1 != m) {
 797                         tlist_del(&m->view);
 798                         if (m1->viewnum == MARK_POINT) {
 799                                 struct point_links *lnks = safe_cast m1->mdata;
 800                                 tlist_add_tail(&m->view, GRP_MARK,
 801                                                &lnks->lists[m->viewnum]);
 802                         } else
 803                                 tlist_add_tail(&m->view, GRP_MARK, &m1->view);
 804                 }
 805                 hlist_del(&m->all);
 806                 hlist_add_before(&m->all, &target->all);
 807                 m->seq = target->seq;
 808                 assign_seq(target);
 809         }
 810 }
 811
 812 void mark_to_mark_noref(struct mark *m safe, struct mark *target safe)
 813 {
 814         struct mark *m2;
 815         int err = 0;
 816         static bool warned = False;
 817
 818         _mark_to_mark_noref(m, target);
 819         m2 = mark_prev(m);
 820         if (m2 && !mark_same(m2, m) &&
 821             pane_call(m->owner, "debug:validate-marks", m->owner,
 822                       0, m2, NULL, 0, m) < 0)
 823                 err = 1;
 824         m2 = mark_next(m);
 825         if (m2 && !mark_same(m, m2) &&
 826             pane_call(m->owner, "debug:validate-marks", m->owner,
 827                       0, m, NULL, 0, m2) < 0)
 828                 err = 1;
 829
 830         if (err && !warned) {
 831                 LOG_BT();
 832                 call("editor:notify:Message:broadcast",
 833                      m->owner, 0, NULL,
 834                      "WARNING: marks inconsistent in mark_to_mark, check log");
 835                 warned = True;
 836         }
 837 }
 838
 839 void mark_to_mark(struct mark *m safe, struct mark *target safe)
 840 {
 841         _mark_to_mark_noref(m, target);
 842         mark_ref_copy(m, target);
 843 }
 844
 845 void mark_step(struct mark *m safe, int forward)
 846 {
 847         /* step mark forward, or backward, over all marks with same
 848          * ref.
 849          */
 850         struct mark *m2, *target = m;
 851
 852         /* This is called after .ref has been updated, so we can
 853          * assume the point really is moving.
 854          */
 855         notify_mark_moving(m, NULL);
 856
 857         if (forward) {
 858                 for (m2 = mark_next(m);
 859                      m2 && mark_same(m, m2);
 860                      m2 = mark_next(m2))
 861                         target = m2;
 862         } else {
 863                 for (m2 = mark_prev(m);
 864                      m2 && mark_same(m, m2);
 865                      m2 = mark_prev(m2))
 866                         target = m2;
 867         }
 868         mark_to_mark_noref(m, target);
 869 }
 870
 871 void mark_step_sharesref(struct mark *m safe, int forward)
 872 {
 873         /* step mark forward, or backward, over all marks with same
 874          * ref, ignoring the .i, and sets '.i' to a safe value wrt the
 875          * last mark stepped over.
 876          */
 877         struct mark *m2, *target = m;
 878
 879         /* This is called after .ref has been updated, so we can
 880          * assume the point really is moving.
 881          */
 882         notify_mark_moving(m, NULL);
 883
 884         if (forward) {
 885                 for (m2 = mark_next(m);
 886                      m2 && m->ref.p == m2->ref.p;
 887                      m2 = mark_next(m2))
 888                         target = m2;
 889         } else {
 890                 for (m2 = mark_prev(m);
 891                      m2 && m->ref.p == m2->ref.p;
 892                      m2 = mark_prev(m2))
 893                         target = m2;
 894         }
 895         m->ref.i = target->ref.i;
 896         mark_to_mark_noref(m, target);
 897 }
 898
 899 /* A 'vmark' is a mark in a particular view.  We can walk around those
 900  * silently skipping over the points.
 901  */
 902
 903 static struct mark *_vmark_next(struct tlist_head *tl safe)
 904 {
 905         while (TLIST_TYPE(tl) != GRP_HEAD) {
 906                 if (TLIST_TYPE(tl) == GRP_LIST) {
 907                         tl = TLIST_PTR(tl->next);
 908                         continue;
 909                 }
 910                 return container_of(tl, struct mark, view);
 911         }
 912         return NULL;
 913 }
 914
 915 struct mark *vmark_next(struct mark *m safe)
 916 {
 917         struct tlist_head *tl;
 918
 919         if (!mark_valid(m))
 920                 return NULL;
 921
 922         tl = TLIST_PTR(m->view.next);
 923         return _vmark_next(tl);
 924 }
 925
 926 static struct mark *vmark_or_point_next(struct mark *m safe, int view)
 927 {
 928         struct tlist_head *tl;
 929         struct point_links *lnk;
 930
 931         if (m->viewnum == view)
 932                 tl = TLIST_PTR(m->view.next);
 933         else if (m->viewnum == MARK_POINT) {
 934                 lnk = safe_cast m->mdata;
 935                 tl = TLIST_PTR(lnk->lists[view].next);
 936         } else
 937                 return NULL;
 938         switch(TLIST_TYPE(tl)) {
 939         default:
 940         case GRP_HEAD:
 941                 return NULL;
 942         case GRP_MARK:
 943                 return container_of(tl, struct mark, view);
 944         case GRP_LIST:
 945                 lnk = container_of_array(tl, struct point_links, lists, view);
 946                 return lnk->pt;
 947         }
 948 }
 949
 950 static struct mark *_vmark_prev(struct tlist_head *tl safe)
 951 {
 952         while (TLIST_TYPE(tl) != GRP_HEAD) {
 953                 if (TLIST_TYPE(tl) == GRP_LIST) {
 954                         tl = TLIST_PTR(tl->prev);
 955                         continue;
 956                 }
 957                 return container_of(tl, struct mark, view);
 958         }
 959         return NULL;
 960 }
 961
 962 struct mark *vmark_prev(struct mark *m safe)
 963 {
 964         struct tlist_head *tl;
 965
 966         if (!mark_valid(m))
 967                 return NULL;
 968
 969         tl = TLIST_PTR(m->view.prev);
 970         return _vmark_prev(tl);
 971 }
 972
 973 static struct mark *vmark_or_point_prev(struct mark *m safe, int view)
 974 {
 975         struct tlist_head *tl;
 976         struct point_links *lnk;
 977
 978         if (m->viewnum == view)
 979                 tl = TLIST_PTR(m->view.prev);
 980         else if (m->viewnum == MARK_POINT) {
 981                 lnk = safe_cast m->mdata;
 982                 tl = TLIST_PTR(lnk->lists[view].prev);
 983         } else
 984                 return NULL;
 985         switch(TLIST_TYPE(tl)) {
 986         default:
 987         case GRP_HEAD:
 988                 return NULL;
 989         case GRP_MARK:
 990                 return container_of(tl, struct mark, view);
 991         case GRP_LIST:
 992                 lnk = container_of_array(tl, struct point_links, lists, view);
 993                 return lnk->pt;
 994         }
 995 }
 996
 997 struct mark *do_vmark_first(struct doc *d safe, int view,
 998                             struct pane *owner safe)
 999 {
1000         struct tlist_head *tl;
1001
1002         if (view < 0 || view >= d->nviews || d->views == NULL)
1003                 return NULL;
1004         if (d->views[view].owner != owner)
1005                 return NULL;
1006
1007         tl = TLIST_PTR(d->views[view].head.next);
1008         while (TLIST_TYPE(tl) != GRP_HEAD) {
1009                 if (TLIST_TYPE(tl) == GRP_LIST) {
1010                         tl = TLIST_PTR(tl->next);
1011                         continue;
1012                 }
1013                 return container_of(tl, struct mark, view);
1014         }
1015         return NULL;
1016 }
1017
1018 struct mark *do_vmark_last(struct doc *d safe, int view,
1019                            struct pane *owner safe)
1020 {
1021         struct tlist_head *tl;
1022
1023         if (view < 0 || view >= d->nviews || d->views == NULL)
1024                 return NULL;
1025         if (d->views[view].owner != owner)
1026                 return NULL;
1027
1028         tl = TLIST_PTR(d->views[view].head.prev);
1029         while (TLIST_TYPE(tl) != GRP_HEAD) {
1030                 if (TLIST_TYPE(tl) == GRP_LIST) {
1031                         tl = TLIST_PTR(tl->prev);
1032                         continue;
1033                 }
1034                 return container_of(tl, struct mark, view);
1035         }
1036         return NULL;
1037 }
1038
1039 struct mark *vmark_first(struct pane *p safe, int view, struct pane *owner safe)
1040 {
1041         return home_call_ret(mark, p, "doc:vmark-get", owner, view);
1042 }
1043
1044 struct mark *vmark_last(struct pane *p safe, int view, struct pane *owner safe)
1045 {
1046         return home_call_ret(mark2, p, "doc:vmark-get", owner, view);
1047 }
1048
1049 struct mark *vmark_at_or_before(struct pane *p safe, struct mark *m safe,
1050                                 int view, struct pane *owner)
1051 {
1052         return home_call_ret(mark, p, "doc:vmark-prev", owner?:p,
1053                              view, m);
1054 }
1055
1056 struct mark *vmark_new(struct pane *p safe, int view, struct pane *owner)
1057 {
1058         return home_call_ret(mark, p, "doc:vmark-new", owner?:p, view);
1059 }
1060
1061 struct mark *vmark_matching(struct mark *m safe)
1062 {
1063         /* Find a nearby mark in the same view with the same ref */
1064         struct mark *m2;
1065
1066         if (!mark_valid(m))
1067                 return NULL;
1068
1069         m2 = vmark_prev(m);
1070         if (m2 && mark_same(m, m2))
1071                 return m2;
1072         m2 = vmark_next(m);
1073         if (m2 && mark_same(m, m2))
1074                 return m2;
1075         return NULL;
1076 }
1077
1078 struct mark *do_vmark_at_or_before(struct doc *d safe,
1079                                    struct mark *m safe,
1080                                    int view, struct pane *owner)
1081 {
1082         /* Find the last 'view' mark that is not later in the document than 'm'.
1083          * It might be later in the mark list, but not in the document.
1084          * Return NULL if all 'view' marks are after 'm' in the document.
1085          */
1086         struct mark *vm = m;
1087
1088         if (!mark_valid(m))
1089                 return NULL;
1090
1091         if (&m->owner->doc != d) {
1092                 LOG("vmark_at_or_before called with incorrect mark");
1093                 return NULL;
1094         }
1095
1096         if ((view < 0 && view != MARK_POINT) || view >= d->nviews ||
1097             d->views == NULL || d->views[view].owner != owner)
1098                 return NULL;
1099
1100         /* might need to hunt along 'all' list for something suitable */
1101         while (vm && vm->viewnum != MARK_POINT && vm->viewnum != view)
1102                 vm = mark_next(vm);
1103         if (!vm) {
1104                 vm = m;
1105                 while (vm && vm->viewnum != MARK_POINT && vm->viewnum != view)
1106                         vm = mark_prev(vm);
1107         }
1108         if (!vm)
1109                 /* No 'view' marks at all! */
1110                 return vm;
1111         /* 'vm' is either a point or a 'view' mark.  It is probably after 'm',
1112          * but if it is before, then no 'view' mark is after.
1113          */
1114         if (vm->viewnum == MARK_POINT) {
1115                 struct point_links *lnk = safe_cast vm->mdata;
1116                 struct tlist_head *tl = &lnk->lists[view];
1117                 vm = _vmark_next(tl);
1118                 if (!vm)
1119                         vm = _vmark_prev(tl);
1120                 else if (mark_same(vm, m)) {
1121                         /* maybe there are even more */
1122                         struct mark *vm2;
1123                         while ((vm2 = vmark_next(vm)) != NULL &&
1124                                mark_same(vm, vm2))
1125                                 vm = vm2;
1126                 }
1127         } else if (vm->viewnum == view) {
1128                 /* Just use this, or nearby */
1129                 struct mark *vm2;
1130                 while ((vm2 = vmark_next(vm)) != NULL &&
1131                        mark_same(vm, m))
1132                         vm = vm2;
1133         }
1134         while (vm && !mark_ordered_or_same(vm, m))
1135                 vm = vmark_prev(vm);
1136
1137         return vm;
1138 }
1139
1140 void mark_clip(struct mark *m safe, struct mark *start, struct mark *end,
1141                bool tostart)
1142 {
1143         /* Note: if this is called while looping over a list of marks,
1144          * the loop should move forward when tostart,
1145          * and backward when !tostart.
1146          */
1147         if (!mark_valid(m) || !mark_valid(start) || !mark_valid(end))
1148                 return;
1149         if (!mark_ordered_or_same(start, m))
1150                 return;
1151         if (!mark_ordered_not_same(m, end))
1152                 return;
1153
1154         if (tostart)
1155                 mark_to_mark(m, start);
1156         else
1157                 mark_to_mark(m, end);
1158 }
1159
1160 void marks_clip(struct pane *p safe, struct mark *start, struct mark *end,
1161                 int view, struct pane *owner, bool tostart)
1162 {
1163         struct mark *m, *m2;
1164
1165         if (!mark_valid(start) || !mark_valid(end))
1166                 return;
1167
1168         if (tostart) {
1169                 m = vmark_at_or_before(p, start, view, owner);
1170                 while (m && (m2=vmark_prev(m)) && mark_same(start, m2))
1171                         m = m2;
1172                 while (m && !mark_ordered_or_same(start, m))
1173                         m = vmark_next(m);
1174
1175                 while (m && !mark_ordered_or_same(end, m)) {
1176                         m2 = vmark_next(m);
1177                         mark_clip(m, start, end, tostart);
1178                         m = m2;
1179                 }
1180         } else {
1181                 m = vmark_at_or_before(p, end, view, owner);
1182                 while (m && (m2=vmark_next(m)) && mark_same(end,m2))
1183                         m = m2;
1184                 while (m && !mark_ordered_not_same(m, end))
1185                         m = vmark_prev(m);
1186
1187                 while (m && !mark_ordered_not_same(m, start)) {
1188                         m2 = vmark_prev(m);
1189                         mark_clip(m, start, end, tostart);
1190                         m = m2;
1191                 }
1192         }
1193 }
1194
1195 void doc_check_consistent(struct doc *d safe)
1196 {
1197         /* Check consistency of marks, and abort if not.
1198          * Check:
1199          * - all marks are in seq order
1200          * - all view lists are in seq order
1201          */
1202         struct mark *m, *m2 = NULL;
1203         int seq = 0;
1204         int i;
1205         int max = 1000;
1206         static bool warned = False;
1207
1208         if (pane_no_consistency(safe_cast container_of(d, struct pane, doc)))
1209                 return;
1210
1211         hlist_for_each_entry(m, &d->marks, all) {
1212                 ASSERT(m->seq >= seq);
1213                 ASSERT(&m->owner->doc == d);
1214                 seq = m->seq + 1;
1215                 if (m2 && !marks_validate(m2, m) && !warned) {
1216                         LOG_BT();
1217                         call("editor:notify:Message:broadcast",
1218                              m->owner, 0, NULL,
1219                              "WARNING: mark inconsistency, check log");
1220                         warned = True;
1221                 }
1222                 m2 = m;
1223                 if (max-- < 0)
1224                         break;
1225         }
1226         for (i = 0; d->views && i < d->nviews; i++)
1227                 if (d->views[i].owner == NULL) {
1228                         if (!tlist_empty(&d->views[i].head)) abort();
1229                 } else {
1230                         struct tlist_head *tl;
1231                         struct point_links *pl;
1232                         seq = 0;
1233                         tlist_for_each(tl, &d->views[i].head) {
1234                                 switch(TLIST_TYPE(tl)) {
1235                                 case GRP_HEAD: abort();
1236                                 case GRP_MARK:
1237                                         m = container_of(tl, struct mark, view);
1238                                         break;
1239                                 case GRP_LIST:
1240                                         pl = container_of_array(
1241                                                 tl, struct point_links,
1242                                                 lists, i);
1243                                         m = pl->pt;
1244                                         break;
1245                                 default: abort();
1246                                 }
1247                                 if (m->seq < seq)
1248                                         abort();
1249                                 seq = m->seq + 1;
1250                                 if (max-- < 0)
1251                                         break;
1252                         }
1253                 }
1254 }
1255
1256 bool marks_validate(struct mark *m1 safe, struct mark *m2 safe)
1257 {
1258         struct mark *m;
1259         struct doc *d = &m1->owner->doc;
1260         int found = 0;
1261         int ret;
1262         int max = 1000;
1263
1264         if (m1 == m2) {
1265                 for (m = mark_first(d); m; m = mark_next(m)) {
1266                         if (m1 == m)
1267                                 return True;
1268                         if (max-- < 0)
1269                                 break;
1270                 }
1271                 LOG("marks_validate: marks not found");
1272                 return False;
1273         }
1274         if (m1->seq >= m2->seq) {
1275                 m = m1; m1 = m2; m2 = m;
1276         }
1277
1278         for (m = mark_first(d); m; m = mark_next(m)) {
1279                 if (m == m1 || m == m2)
1280                         found += 1;
1281                 if (max-- < 0)
1282                         break;
1283         }
1284         if (found != 2) {
1285                 LOG("log_val_marks not both found, only %d", found);
1286                 return False;
1287         }
1288         if (mark_same(m1, m2))
1289                 return True;
1290         ret = pane_call(m1->owner, "debug:validate-marks", m1->owner,
1291                         0, m1, NULL, 0, m2);
1292         return (ret > 0 || ret == Efallthrough);
1293 }