home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / e20313sr.zip / emacs / 20.3.1 / src / intervals.c < prev    next >
C/C++ Source or Header  |  1999-07-31  |  64KB  |  2,240 lines
  1. /* Code for doing intervals.
  2.    Copyright (C) 1993, 1994, 1995, 1997, 1998 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU Emacs.
  5.  
  6. GNU Emacs is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. GNU Emacs is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU Emacs; see the file COPYING.  If not, write to
  18. the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19. Boston, MA 02111-1307, USA.  */
  20.  
  21.  
  22. /* NOTES:
  23.  
  24.    Have to ensure that we can't put symbol nil on a plist, or some
  25.    functions may work incorrectly.
  26.  
  27.    An idea:  Have the owner of the tree keep count of splits and/or
  28.    insertion lengths (in intervals), and balance after every N.
  29.  
  30.    Need to call *_left_hook when buffer is killed.
  31.  
  32.    Scan for zero-length, or 0-length to see notes about handling
  33.    zero length interval-markers.
  34.  
  35.    There are comments around about freeing intervals.  It might be
  36.    faster to explicitly free them (put them on the free list) than
  37.    to GC them.
  38.  
  39. */
  40.  
  41.  
  42. #include <config.h>
  43. #include "lisp.h"
  44. #include "intervals.h"
  45. #include "buffer.h"
  46. #include "puresize.h"
  47. #include "keyboard.h"
  48.  
  49. /* The rest of the file is within this conditional.  */
  50. #ifdef USE_TEXT_PROPERTIES
  51.  
  52. /* Test for membership, allowing for t (actually any non-cons) to mean the
  53.    universal set.  */
  54.  
  55. #define TMEM(sym, set) (CONSP (set) ? ! NILP (Fmemq (sym, set)) : ! NILP (set))
  56.  
  57. #define min(x, y) ((x) < (y) ? (x) : (y))
  58.  
  59. Lisp_Object merge_properties_sticky ();
  60.  
  61. /* Utility functions for intervals.  */
  62.  
  63.  
  64. /* Create the root interval of some object, a buffer or string.  */
  65.  
  66. INTERVAL
  67. create_root_interval (parent)
  68.      Lisp_Object parent;
  69. {
  70.   INTERVAL new;
  71.  
  72.   CHECK_IMPURE (parent);
  73.  
  74.   new = make_interval ();
  75.  
  76.   if (BUFFERP (parent))
  77.     {
  78.       new->total_length = (BUF_Z (XBUFFER (parent))
  79.                - BUF_BEG (XBUFFER (parent)));
  80.       BUF_INTERVALS (XBUFFER (parent)) = new;
  81.       new->position = 1;
  82.     }
  83.   else if (STRINGP (parent))
  84.     {
  85.       new->total_length = XSTRING (parent)->size;
  86.       XSTRING (parent)->intervals = new;
  87.       new->position = 0;
  88.     }
  89.  
  90.   new->parent = (INTERVAL) XFASTINT (parent);
  91.  
  92.   return new;
  93. }
  94.  
  95. /* Make the interval TARGET have exactly the properties of SOURCE */
  96.  
  97. void
  98. copy_properties (source, target)
  99.      register INTERVAL source, target;
  100. {
  101.   if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
  102.     return;
  103.  
  104.   COPY_INTERVAL_CACHE (source, target);
  105.   target->plist = Fcopy_sequence (source->plist);
  106. }
  107.  
  108. /* Merge the properties of interval SOURCE into the properties
  109.    of interval TARGET.  That is to say, each property in SOURCE
  110.    is added to TARGET if TARGET has no such property as yet.  */
  111.  
  112. static void
  113. merge_properties (source, target)
  114.      register INTERVAL source, target;
  115. {
  116.   register Lisp_Object o, sym, val;
  117.  
  118.   if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
  119.     return;
  120.  
  121.   MERGE_INTERVAL_CACHE (source, target);
  122.  
  123.   o = source->plist;
  124.   while (! EQ (o, Qnil))
  125.     {
  126.       sym = Fcar (o);
  127.       val = Fmemq (sym, target->plist);
  128.  
  129.       if (NILP (val))
  130.     {
  131.       o = Fcdr (o);
  132.       val = Fcar (o);
  133.       target->plist = Fcons (sym, Fcons (val, target->plist));
  134.       o = Fcdr (o);
  135.     }
  136.       else
  137.     o = Fcdr (Fcdr (o));
  138.     }
  139. }
  140.  
  141. /* Return 1 if the two intervals have the same properties,
  142.    0 otherwise.  */
  143.  
  144. int
  145. intervals_equal (i0, i1)
  146.      INTERVAL i0, i1;
  147. {
  148.   register Lisp_Object i0_cdr, i0_sym, i1_val;
  149.   register int i1_len;
  150.  
  151.   if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
  152.     return 1;
  153.  
  154.   if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1))
  155.     return 0;
  156.  
  157.   i1_len = XFASTINT (Flength (i1->plist));
  158.   if (i1_len & 0x1)        /* Paranoia -- plists are always even */
  159.     abort ();
  160.   i1_len /= 2;
  161.   i0_cdr = i0->plist;
  162.   while (!NILP (i0_cdr))
  163.     {
  164.       /* Lengths of the two plists were unequal.  */
  165.       if (i1_len == 0)
  166.     return 0;
  167.  
  168.       i0_sym = Fcar (i0_cdr);
  169.       i1_val = Fmemq (i0_sym, i1->plist);
  170.  
  171.       /* i0 has something i1 doesn't.  */
  172.       if (EQ (i1_val, Qnil))
  173.     return 0;
  174.  
  175.       /* i0 and i1 both have sym, but it has different values in each.  */
  176.       i0_cdr = Fcdr (i0_cdr);
  177.       if (! EQ (Fcar (Fcdr (i1_val)), Fcar (i0_cdr)))
  178.     return 0;
  179.  
  180.       i0_cdr = Fcdr (i0_cdr);
  181.       i1_len--;
  182.     }
  183.  
  184.   /* Lengths of the two plists were unequal.  */
  185.   if (i1_len > 0)
  186.     return 0;
  187.  
  188.   return 1;
  189. }
  190.  
  191. static int icount;
  192. static int idepth;
  193. static int zero_length;
  194.  
  195. /* Traverse an interval tree TREE, performing FUNCTION on each node.
  196.    Pass FUNCTION two args: an interval, and ARG.  */
  197.  
  198. void
  199. traverse_intervals (tree, position, depth, function, arg)
  200.      INTERVAL tree;
  201.      int position, depth;
  202.      void (* function) P_ ((INTERVAL, Lisp_Object));
  203.      Lisp_Object arg;
  204. {
  205.   if (NULL_INTERVAL_P (tree))
  206.     return;
  207.  
  208.   traverse_intervals (tree->left, position, depth + 1, function, arg);
  209.   position += LEFT_TOTAL_LENGTH (tree);
  210.   tree->position = position;
  211.   (*function) (tree, arg);
  212.   position += LENGTH (tree);
  213.   traverse_intervals (tree->right, position, depth + 1,  function, arg);
  214. }
  215.  
  216. #if 0
  217. /* These functions are temporary, for debugging purposes only.  */
  218.  
  219. INTERVAL search_interval, found_interval;
  220.  
  221. void
  222. check_for_interval (i)
  223.      register INTERVAL i;
  224. {
  225.   if (i == search_interval)
  226.     {
  227.       found_interval = i;
  228.       icount++;
  229.     }
  230. }
  231.  
  232. INTERVAL
  233. search_for_interval (i, tree)
  234.      register INTERVAL i, tree;
  235. {
  236.   icount = 0;
  237.   search_interval = i;
  238.   found_interval = NULL_INTERVAL;
  239.   traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
  240.   return found_interval;
  241. }
  242.  
  243. static void
  244. inc_interval_count (i)
  245.      INTERVAL i;
  246. {
  247.   icount++;
  248.   if (LENGTH (i) == 0)
  249.     zero_length++;
  250.   if (depth > idepth)
  251.     idepth = depth;
  252. }
  253.  
  254. int
  255. count_intervals (i)
  256.      register INTERVAL i;
  257. {
  258.   icount = 0;
  259.   idepth = 0;
  260.   zero_length = 0;
  261.   traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);
  262.  
  263.   return icount;
  264. }
  265.  
  266. static INTERVAL
  267. root_interval (interval)
  268.      INTERVAL interval;
  269. {
  270.   register INTERVAL i = interval;
  271.  
  272.   while (! ROOT_INTERVAL_P (i))
  273.     i = i->parent;
  274.  
  275.   return i;
  276. }
  277. #endif
  278.  
  279. /* Assuming that a left child exists, perform the following operation:
  280.  
  281.      A          B
  282.     / \         / \
  283.    B       =>       A
  284.   / \           / \
  285.      c          c
  286. */
  287.  
  288. static INTERVAL
  289. rotate_right (interval)
  290.      INTERVAL interval;
  291. {
  292.   INTERVAL i;
  293.   INTERVAL B = interval->left;
  294.   int old_total = interval->total_length;
  295.  
  296.   /* Deal with any Parent of A;  make it point to B.  */
  297.   if (! ROOT_INTERVAL_P (interval))
  298.     if (AM_LEFT_CHILD (interval))
  299.       interval->parent->left = B;
  300.     else
  301.       interval->parent->right = B;
  302.   B->parent = interval->parent;
  303.  
  304.   /* Make B the parent of A */
  305.   i = B->right;
  306.   B->right = interval;
  307.   interval->parent = B;
  308.  
  309.   /* Make A point to c */
  310.   interval->left = i;
  311.   if (! NULL_INTERVAL_P (i))
  312.     i->parent = interval;
  313.  
  314.   /* A's total length is decreased by the length of B and its left child.  */
  315.   interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);
  316.  
  317.   /* B must have the same total length of A.  */
  318.   B->total_length = old_total;
  319.  
  320.   return B;
  321. }
  322.  
  323. /* Assuming that a right child exists, perform the following operation:
  324.  
  325.     A               B   
  326.    / \               / \  
  327.       B       =>     A
  328.      / \         / \    
  329.     c               c
  330. */
  331.  
  332. static INTERVAL
  333. rotate_left (interval)
  334.      INTERVAL interval;
  335. {
  336.   INTERVAL i;
  337.   INTERVAL B = interval->right;
  338.   int old_total = interval->total_length;
  339.  
  340.   /* Deal with any parent of A;  make it point to B.  */
  341.   if (! ROOT_INTERVAL_P (interval))
  342.     if (AM_LEFT_CHILD (interval))
  343.       interval->parent->left = B;
  344.     else
  345.       interval->parent->right = B;
  346.   B->parent = interval->parent;
  347.  
  348.   /* Make B the parent of A */
  349.   i = B->left;
  350.   B->left = interval;
  351.   interval->parent = B;
  352.  
  353.   /* Make A point to c */
  354.   interval->right = i;
  355.   if (! NULL_INTERVAL_P (i))
  356.     i->parent = interval;
  357.  
  358.   /* A's total length is decreased by the length of B and its right child.  */
  359.   interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval);
  360.  
  361.   /* B must have the same total length of A.  */
  362.   B->total_length = old_total;
  363.  
  364.   return B;
  365. }
  366.  
  367. /* Balance an interval tree with the assumption that the subtrees
  368.    themselves are already balanced.  */
  369.  
  370. static INTERVAL
  371. balance_an_interval (i)
  372.      INTERVAL i;
  373. {
  374.   register int old_diff, new_diff;
  375.  
  376.   while (1)
  377.     {
  378.       old_diff = LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i);
  379.       if (old_diff > 0)
  380.     {
  381.       new_diff = i->total_length - i->left->total_length
  382.         + RIGHT_TOTAL_LENGTH (i->left) - LEFT_TOTAL_LENGTH (i->left);
  383.       if (abs (new_diff) >= old_diff)
  384.         break;
  385.       i = rotate_right (i);
  386.       balance_an_interval (i->right);
  387.     }
  388.       else if (old_diff < 0)
  389.     {
  390.       new_diff = i->total_length - i->right->total_length
  391.         + LEFT_TOTAL_LENGTH (i->right) - RIGHT_TOTAL_LENGTH (i->right);
  392.       if (abs (new_diff) >= -old_diff)
  393.         break;
  394.       i = rotate_left (i);
  395.       balance_an_interval (i->left);
  396.     }
  397.       else
  398.     break;
  399.     }
  400.   return i;
  401. }
  402.  
  403. /* Balance INTERVAL, potentially stuffing it back into its parent
  404.    Lisp Object.  */
  405.  
  406. static INLINE INTERVAL
  407. balance_possible_root_interval (interval)
  408.      register INTERVAL interval;
  409. {
  410.   Lisp_Object parent;
  411.  
  412.   if (interval->parent == NULL_INTERVAL)
  413.     return interval;
  414.  
  415.   XSETFASTINT (parent, (EMACS_INT) interval->parent);
  416.   interval = balance_an_interval (interval);
  417.  
  418.   if (BUFFERP (parent))
  419.     BUF_INTERVALS (XBUFFER (parent)) = interval;
  420.   else if (STRINGP (parent))
  421.     XSTRING (parent)->intervals = interval;
  422.  
  423.   return interval;
  424. }
  425.  
  426. /* Balance the interval tree TREE.  Balancing is by weight
  427.    (the amount of text).  */
  428.  
  429. static INTERVAL
  430. balance_intervals_internal (tree)
  431.      register INTERVAL tree;
  432. {
  433.   /* Balance within each side.  */
  434.   if (tree->left)
  435.     balance_intervals_internal (tree->left);
  436.   if (tree->right)
  437.     balance_intervals_internal (tree->right);
  438.   return balance_an_interval (tree);
  439. }
  440.  
  441. /* Advertised interface to balance intervals.  */
  442.  
  443. INTERVAL
  444. balance_intervals (tree)
  445.      INTERVAL tree;
  446. {
  447.   if (tree == NULL_INTERVAL)
  448.     return NULL_INTERVAL;
  449.  
  450.   return balance_intervals_internal (tree);
  451. }
  452.  
  453. /* Split INTERVAL into two pieces, starting the second piece at
  454.    character position OFFSET (counting from 0), relative to INTERVAL.
  455.    INTERVAL becomes the left-hand piece, and the right-hand piece
  456.    (second, lexicographically) is returned.
  457.  
  458.    The size and position fields of the two intervals are set based upon
  459.    those of the original interval.  The property list of the new interval
  460.    is reset, thus it is up to the caller to do the right thing with the
  461.    result.
  462.  
  463.    Note that this does not change the position of INTERVAL;  if it is a root,
  464.    it is still a root after this operation.  */
  465.  
  466. INTERVAL
  467. split_interval_right (interval, offset)
  468.      INTERVAL interval;
  469.      int offset;
  470. {
  471.   INTERVAL new = make_interval ();
  472.   int position = interval->position;
  473.   int new_length = LENGTH (interval) - offset;
  474.  
  475.   new->position = position + offset;
  476.   new->parent = interval;
  477.  
  478.   if (NULL_RIGHT_CHILD (interval))
  479.     {
  480.       interval->right = new;
  481.       new->total_length = new_length;
  482.     }
  483.   else
  484.     {
  485.       /* Insert the new node between INTERVAL and its right child.  */
  486.       new->right = interval->right;
  487.       interval->right->parent = new;
  488.       interval->right = new;
  489.       new->total_length = new_length + new->right->total_length;
  490.       balance_an_interval (new);
  491.     }
  492.   
  493.   balance_possible_root_interval (interval);
  494.  
  495.   return new;
  496. }
  497.  
  498. /* Split INTERVAL into two pieces, starting the second piece at
  499.    character position OFFSET (counting from 0), relative to INTERVAL.
  500.    INTERVAL becomes the right-hand piece, and the left-hand piece
  501.    (first, lexicographically) is returned.
  502.  
  503.    The size and position fields of the two intervals are set based upon
  504.    those of the original interval.  The property list of the new interval
  505.    is reset, thus it is up to the caller to do the right thing with the
  506.    result.
  507.  
  508.    Note that this does not change the position of INTERVAL;  if it is a root,
  509.    it is still a root after this operation.  */
  510.  
  511. INTERVAL
  512. split_interval_left (interval, offset)
  513.      INTERVAL interval;
  514.      int offset;
  515. {
  516.   INTERVAL new = make_interval ();
  517.   int position = interval->position;
  518.   int new_length = offset;
  519.  
  520.   new->position = interval->position;
  521.   interval->position = interval->position + offset;
  522.   new->parent = interval;
  523.  
  524.   if (NULL_LEFT_CHILD (interval))
  525.     {
  526.       interval->left = new;
  527.       new->total_length = new_length;
  528.     }
  529.   else
  530.     {
  531.       /* Insert the new node between INTERVAL and its left child.  */
  532.       new->left = interval->left;
  533.       new->left->parent = new;
  534.       interval->left = new;
  535.       new->total_length = new_length + new->left->total_length;
  536.       balance_an_interval (new);
  537.     }
  538.   
  539.   balance_possible_root_interval (interval);
  540.  
  541.   return new;
  542. }
  543.  
  544. /* Return the proper position for the first character
  545.    described by the interval tree SOURCE.
  546.    This is 1 if the parent is a buffer,
  547.    0 if the parent is a string or if there is no parent.
  548.  
  549.    Don't use this function on an interval which is the child
  550.    of another interval!  */
  551.  
  552. int
  553. interval_start_pos (source)
  554.      INTERVAL source;
  555. {
  556.   Lisp_Object parent;
  557.  
  558.   if (NULL_INTERVAL_P (source))
  559.     return 0;
  560.  
  561.   XSETFASTINT (parent, (EMACS_INT) source->parent);
  562.   if (BUFFERP (parent))
  563.     return BUF_BEG (XBUFFER (parent));
  564.   return 0;
  565. }
  566.  
  567. /* Find the interval containing text position POSITION in the text
  568.    represented by the interval tree TREE.  POSITION is a buffer
  569.    position (starting from 1) or a string index (starting from 0).
  570.    If POSITION is at the end of the buffer or string,
  571.    return the interval containing the last character.
  572.  
  573.    The `position' field, which is a cache of an interval's position,
  574.    is updated in the interval found.  Other functions (e.g., next_interval)
  575.    will update this cache based on the result of find_interval.  */
  576.  
  577. INTERVAL
  578. find_interval (tree, position)
  579.      register INTERVAL tree;
  580.      register int position;
  581. {
  582.   /* The distance from the left edge of the subtree at TREE
  583.                     to POSITION.  */
  584.   register int relative_position;
  585.   Lisp_Object parent;
  586.  
  587.   if (NULL_INTERVAL_P (tree))
  588.     return NULL_INTERVAL;
  589.  
  590.   XSETFASTINT (parent, (EMACS_INT) tree->parent);
  591.   relative_position = position;
  592.   if (BUFFERP (parent))
  593.     relative_position -= BUF_BEG (XBUFFER (parent));
  594.  
  595.   if (relative_position > TOTAL_LENGTH (tree))
  596.     abort ();            /* Paranoia */
  597.  
  598.   tree = balance_possible_root_interval (tree);
  599.  
  600.   while (1)
  601.     {
  602.       if (relative_position < LEFT_TOTAL_LENGTH (tree))
  603.     {
  604.       tree = tree->left;
  605.     }
  606.       else if (! NULL_RIGHT_CHILD (tree)
  607.            && relative_position >= (TOTAL_LENGTH (tree)
  608.                     - RIGHT_TOTAL_LENGTH (tree)))
  609.     {
  610.       relative_position -= (TOTAL_LENGTH (tree)
  611.                 - RIGHT_TOTAL_LENGTH (tree));
  612.       tree = tree->right;
  613.     }
  614.       else
  615.     {
  616.       tree->position
  617.         = (position - relative_position /* the left edge of *tree */
  618.            + LEFT_TOTAL_LENGTH (tree)); /* the left edge of this interval */
  619.  
  620.       return tree;
  621.     }
  622.     }
  623. }
  624.  
  625. /* Find the succeeding interval (lexicographically) to INTERVAL.
  626.    Sets the `position' field based on that of INTERVAL (see
  627.    find_interval).  */
  628.  
  629. INTERVAL
  630. next_interval (interval)
  631.      register INTERVAL interval;
  632. {
  633.   register INTERVAL i = interval;
  634.   register int next_position;
  635.  
  636.   if (NULL_INTERVAL_P (i))
  637.     return NULL_INTERVAL;
  638.   next_position = interval->position + LENGTH (interval);
  639.  
  640.   if (! NULL_RIGHT_CHILD (i))
  641.     {
  642.       i = i->right;
  643.       while (! NULL_LEFT_CHILD (i))
  644.     i = i->left;
  645.  
  646.       i->position = next_position;
  647.       return i;
  648.     }
  649.  
  650.   while (! NULL_PARENT (i))
  651.     {
  652.       if (AM_LEFT_CHILD (i))
  653.     {
  654.       i = i->parent;
  655.       i->position = next_position;
  656.       return i;
  657.     }
  658.  
  659.       i = i->parent;
  660.     }
  661.  
  662.   return NULL_INTERVAL;
  663. }
  664.  
  665. /* Find the preceding interval (lexicographically) to INTERVAL.
  666.    Sets the `position' field based on that of INTERVAL (see
  667.    find_interval).  */
  668.  
  669. INTERVAL
  670. previous_interval (interval)
  671.      register INTERVAL interval;
  672. {
  673.   register INTERVAL i;
  674.   register int position_of_previous;
  675.  
  676.   if (NULL_INTERVAL_P (interval))
  677.     return NULL_INTERVAL;
  678.  
  679.   if (! NULL_LEFT_CHILD (interval))
  680.     {
  681.       i = interval->left;
  682.       while (! NULL_RIGHT_CHILD (i))
  683.     i = i->right;
  684.  
  685.       i->position = interval->position - LENGTH (i);
  686.       return i;
  687.     }
  688.  
  689.   i = interval;
  690.   while (! NULL_PARENT (i))
  691.     {
  692.       if (AM_RIGHT_CHILD (i))
  693.     {
  694.       i = i->parent;
  695.  
  696.       i->position = interval->position - LENGTH (i);
  697.       return i;
  698.     }
  699.       i = i->parent;
  700.     }
  701.  
  702.   return NULL_INTERVAL;
  703. }
  704.  
  705. /* Find the interval containing POS given some non-NULL INTERVAL
  706.    in the same tree.  Note that we need to update interval->position
  707.    if we go down the tree.  */
  708. INTERVAL
  709. update_interval (i, pos)
  710.      register INTERVAL i;
  711.      int pos;
  712. {
  713.   if (NULL_INTERVAL_P (i))
  714.     return NULL_INTERVAL;
  715.  
  716.   while (1) 
  717.     {
  718.       if (pos < i->position) 
  719.     {
  720.       /* Move left. */
  721.       if (pos >= i->position - TOTAL_LENGTH (i->left)) 
  722.         {
  723.           i->left->position = i->position - TOTAL_LENGTH (i->left)
  724.         + LEFT_TOTAL_LENGTH (i->left);
  725.           i = i->left;        /* Move to the left child */
  726.         }
  727.       else if (NULL_PARENT (i)) 
  728.         error ("Point before start of properties");
  729.       else  
  730.           i = i->parent;
  731.       continue;
  732.     }
  733.       else if (pos >= INTERVAL_LAST_POS (i))
  734.     {
  735.       /* Move right. */
  736.       if (pos < INTERVAL_LAST_POS (i) + TOTAL_LENGTH (i->right)) 
  737.         {
  738.           i->right->position = INTERVAL_LAST_POS (i) +
  739.         LEFT_TOTAL_LENGTH (i->right);
  740.           i = i->right;        /* Move to the right child */
  741.         }
  742.       else if (NULL_PARENT (i)) 
  743.         error ("Point after end of properties");
  744.       else 
  745.           i = i->parent;
  746.       continue;
  747.     }
  748.       else 
  749.     return i;
  750.     }
  751. }
  752.  
  753.  
  754. #if 0
  755. /* Traverse a path down the interval tree TREE to the interval
  756.    containing POSITION, adjusting all nodes on the path for
  757.    an addition of LENGTH characters.  Insertion between two intervals
  758.    (i.e., point == i->position, where i is second interval) means
  759.    text goes into second interval.
  760.  
  761.    Modifications are needed to handle the hungry bits -- after simply
  762.    finding the interval at position (don't add length going down),
  763.    if it's the beginning of the interval, get the previous interval
  764.    and check the hungry bits of both.  Then add the length going back up
  765.    to the root.  */
  766.  
  767. static INTERVAL
  768. adjust_intervals_for_insertion (tree, position, length)
  769.      INTERVAL tree;
  770.      int position, length;
  771. {
  772.   register int relative_position;
  773.   register INTERVAL this;
  774.  
  775.   if (TOTAL_LENGTH (tree) == 0)    /* Paranoia */
  776.     abort ();
  777.  
  778.   /* If inserting at point-max of a buffer, that position
  779.      will be out of range */
  780.   if (position > TOTAL_LENGTH (tree))
  781.     position = TOTAL_LENGTH (tree);
  782.   relative_position = position;
  783.   this = tree;
  784.  
  785.   while (1)
  786.     {
  787.       if (relative_position <= LEFT_TOTAL_LENGTH (this))
  788.     {
  789.       this->total_length += length;
  790.       this = this->left;
  791.     }
  792.       else if (relative_position > (TOTAL_LENGTH (this)
  793.                     - RIGHT_TOTAL_LENGTH (this)))
  794.     {
  795.       relative_position -= (TOTAL_LENGTH (this)
  796.                 - RIGHT_TOTAL_LENGTH (this));
  797.       this->total_length += length;
  798.       this = this->right;
  799.     }
  800.       else
  801.     {
  802.       /* If we are to use zero-length intervals as buffer pointers,
  803.          then this code will have to change.  */
  804.       this->total_length += length;
  805.       this->position = LEFT_TOTAL_LENGTH (this)
  806.                        + position - relative_position + 1;
  807.       return tree;
  808.     }
  809.     }
  810. }
  811. #endif
  812.  
  813. /* Effect an adjustment corresponding to the addition of LENGTH characters
  814.    of text.  Do this by finding the interval containing POSITION in the
  815.    interval tree TREE, and then adjusting all of its ancestors by adding
  816.    LENGTH to them.
  817.  
  818.    If POSITION is the first character of an interval, meaning that point
  819.    is actually between the two intervals, make the new text belong to
  820.    the interval which is "sticky".
  821.  
  822.    If both intervals are "sticky", then make them belong to the left-most
  823.    interval.  Another possibility would be to create a new interval for
  824.    this text, and make it have the merged properties of both ends.  */
  825.  
  826. static INTERVAL
  827. adjust_intervals_for_insertion (tree, position, length)
  828.      INTERVAL tree;
  829.      int position, length;
  830. {
  831.   register INTERVAL i;
  832.   register INTERVAL temp;
  833.   int eobp = 0;
  834.   Lisp_Object parent;
  835.   int offset;
  836.   
  837.   if (TOTAL_LENGTH (tree) == 0)    /* Paranoia */
  838.     abort ();
  839.  
  840.   XSETFASTINT (parent, (EMACS_INT) tree->parent);
  841.   offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0);
  842.  
  843.   /* If inserting at point-max of a buffer, that position will be out
  844.      of range.  Remember that buffer positions are 1-based.  */
  845.   if (position >= TOTAL_LENGTH (tree) + offset)
  846.     {
  847.       position = TOTAL_LENGTH (tree) + offset;
  848.       eobp = 1;
  849.     }
  850.  
  851.   i = find_interval (tree, position);
  852.  
  853.   /* If in middle of an interval which is not sticky either way,
  854.      we must not just give its properties to the insertion.
  855.      So split this interval at the insertion point.  */
  856.   if (! (position == i->position || eobp)
  857.       && END_NONSTICKY_P (i)
  858.       && FRONT_NONSTICKY_P (i))
  859.     {
  860.       Lisp_Object tail;
  861.       Lisp_Object front, rear;
  862.  
  863.       front = textget (i->plist, Qfront_sticky);
  864.       rear  = textget (i->plist, Qrear_nonsticky);
  865.  
  866.       /* Does any actual property pose an actual problem?  */
  867.       for (tail = i->plist; ! NILP (tail); tail = Fcdr (Fcdr (tail)))
  868.     {
  869.       Lisp_Object prop;
  870.       prop = XCONS (tail)->car;
  871.  
  872.       /* Is this particular property rear-sticky?
  873.          Note, if REAR isn't a cons, it must be non-nil,
  874.          which means that all properties are rear-nonsticky.  */
  875.       if (CONSP (rear) && NILP (Fmemq (prop, rear)))
  876.         continue;
  877.  
  878.       /* Is this particular property front-sticky?
  879.          Note, if FRONT isn't a cons, it must be nil,
  880.          which means that all properties are front-nonsticky.  */
  881.       if (CONSP (front) && ! NILP (Fmemq (prop, front)))
  882.         continue;
  883.  
  884.       /* PROP isn't sticky on either side => it is a real problem.  */
  885.       break;
  886.     }
  887.  
  888.       /* If any property is a real problem, split the interval.  */
  889.       if (! NILP (tail))
  890.     {
  891.       temp = split_interval_right (i, position - i->position);
  892.       copy_properties (i, temp);
  893.       i = temp;
  894.     }
  895.     }
  896.  
  897.   /* If we are positioned between intervals, check the stickiness of
  898.      both of them.  We have to do this too, if we are at BEG or Z.  */
  899.   if (position == i->position || eobp)
  900.     {
  901.       register INTERVAL prev;
  902.  
  903.       if (position == BEG)
  904.     prev = 0;
  905.       else if (eobp)
  906.     {
  907.       prev = i;
  908.       i = 0;
  909.     }
  910.       else
  911.     prev = previous_interval (i);
  912.  
  913.       /* Even if we are positioned between intervals, we default
  914.      to the left one if it exists.  We extend it now and split
  915.      off a part later, if stickiness demands it.  */
  916.       for (temp = prev ? prev : i;! NULL_INTERVAL_P (temp); temp = temp->parent)
  917.     {
  918.       temp->total_length += length;
  919.       temp = balance_possible_root_interval (temp);
  920.     }
  921.       
  922.       /* If at least one interval has sticky properties,
  923.      we check the stickiness property by property.  */
  924.       if (END_NONSTICKY_P (prev) || FRONT_STICKY_P (i))
  925.     {
  926.       Lisp_Object pleft, pright;
  927.       struct interval newi;
  928.  
  929.       pleft = NULL_INTERVAL_P (prev) ? Qnil : prev->plist;
  930.       pright = NULL_INTERVAL_P (i) ? Qnil : i->plist;
  931.       newi.plist = merge_properties_sticky (pleft, pright);
  932.  
  933.       if (! prev) /* i.e. position == BEG */
  934.         {
  935.           if (! intervals_equal (i, &newi))
  936.         {
  937.           i = split_interval_left (i, length);
  938.           i->plist = newi.plist;
  939.         }
  940.         }
  941.       else if (! intervals_equal (prev, &newi))
  942.         {
  943.           prev = split_interval_right (prev,
  944.                        position - prev->position);
  945.           prev->plist = newi.plist;
  946.           if (! NULL_INTERVAL_P (i)
  947.           && intervals_equal (prev, i))
  948.         merge_interval_right (prev);
  949.         }
  950.  
  951.       /* We will need to update the cache here later.  */
  952.     }
  953.       else if (! prev && ! NILP (i->plist))
  954.         {
  955.       /* Just split off a new interval at the left.
  956.          Since I wasn't front-sticky, the empty plist is ok.  */
  957.       i = split_interval_left (i, length);
  958.         }
  959.     }
  960.  
  961.   /* Otherwise just extend the interval.  */
  962.   else
  963.     {
  964.       for (temp = i; ! NULL_INTERVAL_P (temp); temp = temp->parent)
  965.     {
  966.       temp->total_length += length;
  967.       temp = balance_possible_root_interval (temp);
  968.     }
  969.     }
  970.       
  971.   return tree;
  972. }
  973.  
  974. /* Any property might be front-sticky on the left, rear-sticky on the left,
  975.    front-sticky on the right, or rear-sticky on the right; the 16 combinations
  976.    can be arranged in a matrix with rows denoting the left conditions and
  977.    columns denoting the right conditions:
  978.       _  __  _
  979. _     FR FR FR FR
  980. FR__   0  1  2  3
  981.  _FR   4  5  6  7
  982. FR     8  9  A  B
  983.   FR   C  D  E  F
  984.  
  985.    left-props  = '(front-sticky (p8 p9 pa pb pc pd pe pf)
  986.            rear-nonsticky (p4 p5 p6 p7 p8 p9 pa pb)
  987.            p0 L p1 L p2 L p3 L p4 L p5 L p6 L p7 L
  988.            p8 L p9 L pa L pb L pc L pd L pe L pf L)
  989.    right-props = '(front-sticky (p2 p3 p6 p7 pa pb pe pf)
  990.            rear-nonsticky (p1 p2 p5 p6 p9 pa pd pe)
  991.            p0 R p1 R p2 R p3 R p4 R p5 R p6 R p7 R
  992.            p8 R p9 R pa R pb R pc R pd R pe R pf R)
  993.  
  994.    We inherit from whoever has a sticky side facing us.  If both sides
  995.    do (cases 2, 3, E, and F), then we inherit from whichever side has a
  996.    non-nil value for the current property.  If both sides do, then we take
  997.    from the left.
  998.  
  999.    When we inherit a property, we get its stickiness as well as its value.
  1000.    So, when we merge the above two lists, we expect to get this:
  1001.  
  1002.    result      = '(front-sticky (p6 p7 pa pb pc pd pe pf)
  1003.            rear-nonsticky (p6 pa)
  1004.            p0 L p1 L p2 L p3 L p6 R p7 R
  1005.            pa R pb R pc L pd L pe L pf L)
  1006.  
  1007.    The optimizable special cases are:
  1008.        left rear-nonsticky = nil, right front-sticky = nil (inherit left)
  1009.        left rear-nonsticky = t,   right front-sticky = t   (inherit right)
  1010.        left rear-nonsticky = t,   right front-sticky = nil (inherit none)
  1011. */
  1012.  
  1013. Lisp_Object
  1014. merge_properties_sticky (pleft, pright)
  1015.      Lisp_Object pleft, pright;
  1016. {
  1017.   register Lisp_Object props, front, rear;
  1018.   Lisp_Object lfront, lrear, rfront, rrear;
  1019.   register Lisp_Object tail1, tail2, sym, lval, rval, cat;
  1020.   int use_left, use_right;
  1021.   int lpresent;
  1022.  
  1023.   props = Qnil;
  1024.   front = Qnil;
  1025.   rear  = Qnil;
  1026.   lfront = textget (pleft, Qfront_sticky);
  1027.   lrear  = textget (pleft, Qrear_nonsticky);
  1028.   rfront = textget (pright, Qfront_sticky);
  1029.   rrear  = textget (pright, Qrear_nonsticky);
  1030.  
  1031.   /* Go through each element of PRIGHT.  */
  1032.   for (tail1 = pright; ! NILP (tail1); tail1 = Fcdr (Fcdr (tail1)))
  1033.     {
  1034.       sym = Fcar (tail1);
  1035.  
  1036.       /* Sticky properties get special treatment.  */
  1037.       if (EQ (sym, Qrear_nonsticky) || EQ (sym, Qfront_sticky))
  1038.     continue;
  1039.  
  1040.       rval = Fcar (Fcdr (tail1));
  1041.       for (tail2 = pleft; ! NILP (tail2); tail2 = Fcdr (Fcdr (tail2)))
  1042.     if (EQ (sym, Fcar (tail2)))
  1043.       break;
  1044.  
  1045.       /* Indicate whether the property is explicitly defined on the left.
  1046.      (We know it is defined explicitly on the right
  1047.      because otherwise we don't get here.)  */
  1048.       lpresent = ! NILP (tail2);
  1049.       lval = (NILP (tail2) ? Qnil : Fcar (Fcdr (tail2)));
  1050.  
  1051.       use_left = ! TMEM (sym, lrear) && lpresent;
  1052.       use_right = TMEM (sym, rfront);
  1053.       if (use_left && use_right)
  1054.     {
  1055.       if (NILP (lval))
  1056.         use_left = 0;
  1057.       else if (NILP (rval))
  1058.         use_right = 0;
  1059.     }
  1060.       if (use_left)
  1061.     {
  1062.       /* We build props as (value sym ...) rather than (sym value ...)
  1063.          because we plan to nreverse it when we're done.  */
  1064.       props = Fcons (lval, Fcons (sym, props));
  1065.       if (TMEM (sym, lfront))
  1066.         front = Fcons (sym, front);
  1067.       if (TMEM (sym, lrear))
  1068.         rear = Fcons (sym, rear);
  1069.     }
  1070.       else if (use_right)
  1071.     {
  1072.       props = Fcons (rval, Fcons (sym, props));
  1073.       if (TMEM (sym, rfront))
  1074.         front = Fcons (sym, front);
  1075.       if (TMEM (sym, rrear))
  1076.         rear = Fcons (sym, rear);
  1077.     }
  1078.     }
  1079.  
  1080.   /* Now go through each element of PLEFT.  */
  1081.   for (tail2 = pleft; ! NILP (tail2); tail2 = Fcdr (Fcdr (tail2)))
  1082.     {
  1083.       sym = Fcar (tail2);
  1084.  
  1085.       /* Sticky properties get special treatment.  */
  1086.       if (EQ (sym, Qrear_nonsticky) || EQ (sym, Qfront_sticky))
  1087.     continue;
  1088.  
  1089.       /* If sym is in PRIGHT, we've already considered it.  */
  1090.       for (tail1 = pright; ! NILP (tail1); tail1 = Fcdr (Fcdr (tail1)))
  1091.     if (EQ (sym, Fcar (tail1)))
  1092.       break;
  1093.       if (! NILP (tail1))
  1094.     continue;
  1095.  
  1096.       lval = Fcar (Fcdr (tail2));
  1097.  
  1098.       /* Since rval is known to be nil in this loop, the test simplifies.  */
  1099.       if (! TMEM (sym, lrear))
  1100.     {
  1101.       props = Fcons (lval, Fcons (sym, props));
  1102.       if (TMEM (sym, lfront))
  1103.         front = Fcons (sym, front);
  1104.     }
  1105.       else if (TMEM (sym, rfront))
  1106.     {
  1107.       /* The value is nil, but we still inherit the stickiness
  1108.          from the right.  */
  1109.       front = Fcons (sym, front);
  1110.       if (TMEM (sym, rrear))
  1111.         rear = Fcons (sym, rear);
  1112.     }
  1113.     }
  1114.   props = Fnreverse (props);
  1115.   if (! NILP (rear))
  1116.     props = Fcons (Qrear_nonsticky, Fcons (Fnreverse (rear), props));
  1117.  
  1118.   cat = textget (props, Qcategory);
  1119.   if (! NILP (front)
  1120.       && 
  1121.       /* If we have inherited a front-stick category property that is t,
  1122.      we don't need to set up a detailed one.  */
  1123.       ! (! NILP (cat) && SYMBOLP (cat)
  1124.      && EQ (Fget (cat, Qfront_sticky), Qt)))
  1125.     props = Fcons (Qfront_sticky, Fcons (Fnreverse (front), props));
  1126.   return props;
  1127. }
  1128.  
  1129.  
  1130. /* Delete an node I from its interval tree by merging its subtrees
  1131.    into one subtree which is then returned.  Caller is responsible for
  1132.    storing the resulting subtree into its parent.  */
  1133.  
  1134. static INTERVAL
  1135. delete_node (i)
  1136.      register INTERVAL i;
  1137. {
  1138.   register INTERVAL migrate, this;
  1139.   register int migrate_amt;
  1140.  
  1141.   if (NULL_INTERVAL_P (i->left))
  1142.     return i->right;
  1143.   if (NULL_INTERVAL_P (i->right))
  1144.     return i->left;
  1145.  
  1146.   migrate = i->left;
  1147.   migrate_amt = i->left->total_length;
  1148.   this = i->right;
  1149.   this->total_length += migrate_amt;
  1150.   while (! NULL_INTERVAL_P (this->left))
  1151.     {
  1152.       this = this->left;
  1153.       this->total_length += migrate_amt;
  1154.     }
  1155.   this->left = migrate;
  1156.   migrate->parent = this;
  1157.  
  1158.   return i->right;
  1159. }
  1160.  
  1161. /* Delete interval I from its tree by calling `delete_node'
  1162.    and properly connecting the resultant subtree.
  1163.  
  1164.    I is presumed to be empty; that is, no adjustments are made
  1165.    for the length of I.  */
  1166.  
  1167. void
  1168. delete_interval (i)
  1169.      register INTERVAL i;
  1170. {
  1171.   register INTERVAL parent;
  1172.   int amt = LENGTH (i);
  1173.  
  1174.   if (amt > 0)            /* Only used on zero-length intervals now.  */
  1175.     abort ();
  1176.  
  1177.   if (ROOT_INTERVAL_P (i))
  1178.     {
  1179.       Lisp_Object owner;
  1180.       XSETFASTINT (owner, (EMACS_INT) i->parent);
  1181.       parent = delete_node (i);
  1182.       if (! NULL_INTERVAL_P (parent))
  1183.     parent->parent = (INTERVAL) XFASTINT (owner);
  1184.  
  1185.       if (BUFFERP (owner))
  1186.     BUF_INTERVALS (XBUFFER (owner)) = parent;
  1187.       else if (STRINGP (owner))
  1188.     XSTRING (owner)->intervals = parent;
  1189.       else
  1190.     abort ();
  1191.  
  1192.       return;
  1193.     }
  1194.  
  1195.   parent = i->parent;
  1196.   if (AM_LEFT_CHILD (i))
  1197.     {
  1198.       parent->left = delete_node (i);
  1199.       if (! NULL_INTERVAL_P (parent->left))
  1200.     parent->left->parent = parent;
  1201.     }
  1202.   else
  1203.     {
  1204.       parent->right = delete_node (i);
  1205.       if (! NULL_INTERVAL_P (parent->right))
  1206.     parent->right->parent = parent;
  1207.     }
  1208. }
  1209.  
  1210. /* Find the interval in TREE corresponding to the relative position
  1211.    FROM and delete as much as possible of AMOUNT from that interval.
  1212.    Return the amount actually deleted, and if the interval was
  1213.    zeroed-out, delete that interval node from the tree.
  1214.  
  1215.    Note that FROM is actually origin zero, aka relative to the
  1216.    leftmost edge of tree.  This is appropriate since we call ourselves
  1217.    recursively on subtrees.
  1218.  
  1219.    Do this by recursing down TREE to the interval in question, and
  1220.    deleting the appropriate amount of text.  */
  1221.  
  1222. static int
  1223. interval_deletion_adjustment (tree, from, amount)
  1224.      register INTERVAL tree;
  1225.      register int from, amount;
  1226. {
  1227.   register int relative_position = from;
  1228.  
  1229.   if (NULL_INTERVAL_P (tree))
  1230.     return 0;
  1231.  
  1232.   /* Left branch */
  1233.   if (relative_position < LEFT_TOTAL_LENGTH (tree))
  1234.     {
  1235.       int subtract = interval_deletion_adjustment (tree->left,
  1236.                            relative_position,
  1237.                            amount);
  1238.       tree->total_length -= subtract;
  1239.       return subtract;
  1240.     }
  1241.   /* Right branch */
  1242.   else if (relative_position >= (TOTAL_LENGTH (tree)
  1243.                  - RIGHT_TOTAL_LENGTH (tree)))
  1244.     {
  1245.       int subtract;
  1246.  
  1247.       relative_position -= (tree->total_length
  1248.                 - RIGHT_TOTAL_LENGTH (tree));
  1249.       subtract = interval_deletion_adjustment (tree->right,
  1250.                            relative_position,
  1251.                            amount);
  1252.       tree->total_length -= subtract;
  1253.       return subtract;
  1254.     }
  1255.   /* Here -- this node.  */
  1256.   else
  1257.     {
  1258.       /* How much can we delete from this interval?  */
  1259.       int my_amount = ((tree->total_length 
  1260.             - RIGHT_TOTAL_LENGTH (tree))
  1261.                - relative_position);
  1262.  
  1263.       if (amount > my_amount)
  1264.     amount = my_amount;
  1265.  
  1266.       tree->total_length -= amount;
  1267.       if (LENGTH (tree) == 0)
  1268.     delete_interval (tree);
  1269.       
  1270.       return amount;
  1271.     }
  1272.  
  1273.   /* Never reach here.  */
  1274. }
  1275.  
  1276. /* Effect the adjustments necessary to the interval tree of BUFFER to
  1277.    correspond to the deletion of LENGTH characters from that buffer
  1278.    text.  The deletion is effected at position START (which is a
  1279.    buffer position, i.e. origin 1).  */
  1280.  
  1281. static void
  1282. adjust_intervals_for_deletion (buffer, start, length)
  1283.      struct buffer *buffer;
  1284.      int start, length;
  1285. {
  1286.   register int left_to_delete = length;
  1287.   register INTERVAL tree = BUF_INTERVALS (buffer);
  1288.   register int deleted;
  1289.   Lisp_Object parent;
  1290.   int offset;
  1291.  
  1292.   XSETFASTINT (parent, (EMACS_INT) tree->parent);
  1293.   offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0);
  1294.  
  1295.   if (NULL_INTERVAL_P (tree))
  1296.     return;
  1297.  
  1298.   if (start > offset + TOTAL_LENGTH (tree)
  1299.       || start + length > offset + TOTAL_LENGTH (tree))
  1300.     abort ();
  1301.  
  1302.   if (length == TOTAL_LENGTH (tree))
  1303.     {
  1304.       BUF_INTERVALS (buffer) = NULL_INTERVAL;
  1305.       return;
  1306.     }
  1307.  
  1308.   if (ONLY_INTERVAL_P (tree))
  1309.     {
  1310.       tree->total_length -= length;
  1311.       return;
  1312.     }
  1313.  
  1314.   if (start > offset + TOTAL_LENGTH (tree))
  1315.     start = offset + TOTAL_LENGTH (tree);
  1316.   while (left_to_delete > 0)
  1317.     {
  1318.       left_to_delete -= interval_deletion_adjustment (tree, start - offset,
  1319.                               left_to_delete);
  1320.       tree = BUF_INTERVALS (buffer);
  1321.       if (left_to_delete == tree->total_length)
  1322.     {
  1323.       BUF_INTERVALS (buffer) = NULL_INTERVAL;
  1324.       return;
  1325.     }
  1326.     }
  1327. }
  1328.  
  1329. /* Make the adjustments necessary to the interval tree of BUFFER to
  1330.    represent an addition or deletion of LENGTH characters starting
  1331.    at position START.  Addition or deletion is indicated by the sign
  1332.    of LENGTH.  */
  1333.  
  1334. INLINE void
  1335. offset_intervals (buffer, start, length)
  1336.      struct buffer *buffer;
  1337.      int start, length;
  1338. {
  1339.   if (NULL_INTERVAL_P (BUF_INTERVALS (buffer)) || length == 0)
  1340.     return;
  1341.  
  1342.   if (length > 0)
  1343.     adjust_intervals_for_insertion (BUF_INTERVALS (buffer), start, length);
  1344.   else
  1345.     adjust_intervals_for_deletion (buffer, start, -length);
  1346. }
  1347.  
  1348. /* Merge interval I with its lexicographic successor. The resulting
  1349.    interval is returned, and has the properties of the original
  1350.    successor.  The properties of I are lost.  I is removed from the
  1351.    interval tree.
  1352.  
  1353.    IMPORTANT:
  1354.    The caller must verify that this is not the last (rightmost)
  1355.    interval.  */
  1356.  
  1357. INTERVAL
  1358. merge_interval_right (i)
  1359.      register INTERVAL i;
  1360. {
  1361.   register int absorb = LENGTH (i);
  1362.   register INTERVAL successor;
  1363.  
  1364.   /* Zero out this interval.  */
  1365.   i->total_length -= absorb;
  1366.  
  1367.   /* Find the succeeding interval.  */
  1368.   if (! NULL_RIGHT_CHILD (i))      /* It's below us.  Add absorb
  1369.                       as we descend.  */
  1370.     {
  1371.       successor = i->right;
  1372.       while (! NULL_LEFT_CHILD (successor))
  1373.     {
  1374.       successor->total_length += absorb;
  1375.       successor = successor->left;
  1376.     }
  1377.  
  1378.       successor->total_length += absorb;
  1379.       delete_interval (i);
  1380.       return successor;
  1381.     }
  1382.  
  1383.   successor = i;
  1384.   while (! NULL_PARENT (successor))       /* It's above us.  Subtract as
  1385.                           we ascend.  */
  1386.     {
  1387.       if (AM_LEFT_CHILD (successor))
  1388.     {
  1389.       successor = successor->parent;
  1390.       delete_interval (i);
  1391.       return successor;
  1392.     }
  1393.  
  1394.       successor = successor->parent;
  1395.       successor->total_length -= absorb;
  1396.     }
  1397.  
  1398.   /* This must be the rightmost or last interval and cannot
  1399.      be merged right.  The caller should have known.  */
  1400.   abort ();
  1401. }
  1402.  
  1403. /* Merge interval I with its lexicographic predecessor. The resulting
  1404.    interval is returned, and has the properties of the original predecessor.
  1405.    The properties of I are lost.  Interval node I is removed from the tree.
  1406.  
  1407.    IMPORTANT:
  1408.    The caller must verify that this is not the first (leftmost) interval.  */
  1409.  
  1410. INTERVAL
  1411. merge_interval_left (i)
  1412.      register INTERVAL i;
  1413. {
  1414.   register int absorb = LENGTH (i);
  1415.   register INTERVAL predecessor;
  1416.  
  1417.   /* Zero out this interval.  */
  1418.   i->total_length -= absorb;
  1419.  
  1420.   /* Find the preceding interval.  */
  1421.   if (! NULL_LEFT_CHILD (i))    /* It's below us. Go down,
  1422.                    adding ABSORB as we go.  */
  1423.     {
  1424.       predecessor = i->left;
  1425.       while (! NULL_RIGHT_CHILD (predecessor))
  1426.     {
  1427.       predecessor->total_length += absorb;
  1428.       predecessor = predecessor->right;
  1429.     }
  1430.  
  1431.       predecessor->total_length += absorb;
  1432.       delete_interval (i);
  1433.       return predecessor;
  1434.     }
  1435.  
  1436.   predecessor = i;
  1437.   while (! NULL_PARENT (predecessor))    /* It's above us.  Go up,
  1438.                    subtracting ABSORB.  */
  1439.     {
  1440.       if (AM_RIGHT_CHILD (predecessor))
  1441.     {
  1442.       predecessor = predecessor->parent;
  1443.       delete_interval (i);
  1444.       return predecessor;
  1445.     }
  1446.  
  1447.       predecessor = predecessor->parent;
  1448.       predecessor->total_length -= absorb;
  1449.     }
  1450.  
  1451.   /* This must be the leftmost or first interval and cannot
  1452.      be merged left.  The caller should have known.  */
  1453.   abort ();
  1454. }
  1455.  
  1456. /* Make an exact copy of interval tree SOURCE which descends from
  1457.    PARENT.  This is done by recursing through SOURCE, copying
  1458.    the current interval and its properties, and then adjusting
  1459.    the pointers of the copy.  */
  1460.  
  1461. static INTERVAL
  1462. reproduce_tree (source, parent)
  1463.      INTERVAL source, parent;
  1464. {
  1465.   register INTERVAL t = make_interval ();
  1466.  
  1467.   bcopy (source, t, INTERVAL_SIZE);
  1468.   copy_properties (source, t);
  1469.   t->parent = parent;
  1470.   if (! NULL_LEFT_CHILD (source))
  1471.     t->left = reproduce_tree (source->left, t);
  1472.   if (! NULL_RIGHT_CHILD (source))
  1473.     t->right = reproduce_tree (source->right, t);
  1474.  
  1475.   return t;
  1476. }
  1477.  
  1478. #if 0
  1479. /* Nobody calls this.  Perhaps it's a vestige of an earlier design.  */
  1480.  
  1481. /* Make a new interval of length LENGTH starting at START in the
  1482.    group of intervals INTERVALS, which is actually an interval tree.
  1483.    Returns the new interval.
  1484.  
  1485.    Generate an error if the new positions would overlap an existing
  1486.    interval.  */
  1487.  
  1488. static INTERVAL
  1489. make_new_interval (intervals, start, length)
  1490.      INTERVAL intervals;
  1491.      int start, length;
  1492. {
  1493.   INTERVAL slot;
  1494.  
  1495.   slot = find_interval (intervals, start);
  1496.   if (start + length > slot->position + LENGTH (slot))
  1497.     error ("Interval would overlap");
  1498.  
  1499.   if (start == slot->position && length == LENGTH (slot))
  1500.     return slot;
  1501.  
  1502.   if (slot->position == start)
  1503.     {
  1504.       /* New right node.  */
  1505.       split_interval_right (slot, length);
  1506.       return slot;
  1507.     }
  1508.  
  1509.   if (slot->position + LENGTH (slot) == start + length)
  1510.     {
  1511.       /* New left node.  */
  1512.       split_interval_left (slot, LENGTH (slot) - length);
  1513.       return slot;
  1514.     }
  1515.  
  1516.   /* Convert interval SLOT into three intervals.  */
  1517.   split_interval_left (slot, start - slot->position);
  1518.   split_interval_right (slot, length);
  1519.   return slot;
  1520. }
  1521. #endif
  1522.  
  1523. /* Insert the intervals of SOURCE into BUFFER at POSITION.
  1524.    LENGTH is the length of the text in SOURCE.
  1525.  
  1526.    The `position' field of the SOURCE intervals is assumed to be
  1527.    consistent with its parent; therefore, SOURCE must be an
  1528.    interval tree made with copy_interval or must be the whole
  1529.    tree of a buffer or a string.
  1530.  
  1531.    This is used in insdel.c when inserting Lisp_Strings into the
  1532.    buffer.  The text corresponding to SOURCE is already in the buffer
  1533.    when this is called.  The intervals of new tree are a copy of those
  1534.    belonging to the string being inserted; intervals are never
  1535.    shared.
  1536.  
  1537.    If the inserted text had no intervals associated, and we don't
  1538.    want to inherit the surrounding text's properties, this function
  1539.    simply returns -- offset_intervals should handle placing the
  1540.    text in the correct interval, depending on the sticky bits.
  1541.  
  1542.    If the inserted text had properties (intervals), then there are two
  1543.    cases -- either insertion happened in the middle of some interval,
  1544.    or between two intervals.
  1545.  
  1546.    If the text goes into the middle of an interval, then new
  1547.    intervals are created in the middle with only the properties of
  1548.    the new text, *unless* the macro MERGE_INSERTIONS is true, in
  1549.    which case the new text has the union of its properties and those
  1550.    of the text into which it was inserted.
  1551.  
  1552.    If the text goes between two intervals, then if neither interval
  1553.    had its appropriate sticky property set (front_sticky, rear_sticky),
  1554.    the new text has only its properties.  If one of the sticky properties
  1555.    is set, then the new text "sticks" to that region and its properties
  1556.    depend on merging as above.  If both the preceding and succeeding
  1557.    intervals to the new text are "sticky", then the new text retains
  1558.    only its properties, as if neither sticky property were set.  Perhaps
  1559.    we should consider merging all three sets of properties onto the new
  1560.    text...  */
  1561.  
  1562. void
  1563. graft_intervals_into_buffer (source, position, length, buffer, inherit)
  1564.      INTERVAL source;
  1565.      int position, length;
  1566.      struct buffer *buffer;
  1567.      int inherit;
  1568. {
  1569.   register INTERVAL under, over, this, prev;
  1570.   register INTERVAL tree;
  1571.   int middle;
  1572.  
  1573.   tree = BUF_INTERVALS (buffer);
  1574.  
  1575.   /* If the new text has no properties, it becomes part of whatever
  1576.      interval it was inserted into.  */
  1577.   if (NULL_INTERVAL_P (source))
  1578.     {
  1579.       Lisp_Object buf;
  1580.       if (!inherit && ! NULL_INTERVAL_P (tree))
  1581.     {
  1582.       XSETBUFFER (buf, buffer);
  1583.       Fset_text_properties (make_number (position),
  1584.                 make_number (position + length),
  1585.                 Qnil, buf);
  1586.     }
  1587.       if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer)))
  1588.     BUF_INTERVALS (buffer) = balance_an_interval (BUF_INTERVALS (buffer));
  1589.       return;
  1590.     }
  1591.  
  1592.   if (NULL_INTERVAL_P (tree))
  1593.     {
  1594.       /* The inserted text constitutes the whole buffer, so
  1595.      simply copy over the interval structure.  */
  1596.       if ((BUF_Z (buffer) - BUF_BEG (buffer)) == TOTAL_LENGTH (source))
  1597.     {
  1598.       Lisp_Object buf;
  1599.       XSETBUFFER (buf, buffer);
  1600.       BUF_INTERVALS (buffer) = reproduce_tree (source, buf);
  1601.       BUF_INTERVALS (buffer)->position = 1;
  1602.  
  1603.       /* Explicitly free the old tree here?  */
  1604.  
  1605.       return;
  1606.     }
  1607.  
  1608.       /* Create an interval tree in which to place a copy
  1609.      of the intervals of the inserted string.  */
  1610.       {
  1611.     Lisp_Object buf;
  1612.     XSETBUFFER (buf, buffer);
  1613.     tree = create_root_interval (buf);
  1614.       }
  1615.     }
  1616.   else if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (source))
  1617.     /* If the buffer contains only the new string, but
  1618.        there was already some interval tree there, then it may be
  1619.        some zero length intervals.  Eventually, do something clever
  1620.        about inserting properly.  For now, just waste the old intervals.  */
  1621.     {
  1622.       BUF_INTERVALS (buffer) = reproduce_tree (source, tree->parent);
  1623.       BUF_INTERVALS (buffer)->position = 1;
  1624.       /* Explicitly free the old tree here.  */
  1625.  
  1626.       return;
  1627.     }
  1628.   /* Paranoia -- the text has already been added, so this buffer
  1629.      should be of non-zero length.  */
  1630.   else if (TOTAL_LENGTH (tree) == 0)
  1631.     abort ();
  1632.  
  1633.   this = under = find_interval (tree, position);
  1634.   if (NULL_INTERVAL_P (under))    /* Paranoia */
  1635.     abort ();
  1636.   over = find_interval (source, interval_start_pos (source));
  1637.  
  1638.   /* Here for insertion in the middle of an interval.
  1639.      Split off an equivalent interval to the right,
  1640.      then don't bother with it any more.  */
  1641.  
  1642.   if (position > under->position)
  1643.     {
  1644.       INTERVAL end_unchanged
  1645.     = split_interval_left (this, position - under->position);
  1646.       copy_properties (under, end_unchanged);
  1647.       under->position = position;
  1648.       prev = 0;
  1649.       middle = 1;
  1650.     }
  1651.   else
  1652.     {
  1653.       prev = previous_interval (under);
  1654.       if (prev && !END_NONSTICKY_P (prev))
  1655.     prev = 0;
  1656.     }
  1657.  
  1658.   /* Insertion is now at beginning of UNDER.  */
  1659.  
  1660.   /* The inserted text "sticks" to the interval `under',
  1661.      which means it gets those properties.
  1662.      The properties of under are the result of
  1663.      adjust_intervals_for_insertion, so stickiness has
  1664.      already been taken care of.  */
  1665.      
  1666.   while (! NULL_INTERVAL_P (over))
  1667.     {
  1668.       if (LENGTH (over) < LENGTH (under))
  1669.     {
  1670.       this = split_interval_left (under, LENGTH (over));
  1671.       copy_properties (under, this);
  1672.     }
  1673.       else
  1674.     this = under;
  1675.       copy_properties (over, this);
  1676.       if (inherit)
  1677.     merge_properties (over, this);
  1678.       else
  1679.     copy_properties (over, this);
  1680.       over = next_interval (over);
  1681.     }
  1682.  
  1683.   if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer)))
  1684.     BUF_INTERVALS (buffer) = balance_an_interval (BUF_INTERVALS (buffer));
  1685.   return;
  1686. }
  1687.  
  1688. /* Get the value of property PROP from PLIST,
  1689.    which is the plist of an interval.
  1690.    We check for direct properties, for categories with property PROP, 
  1691.    and for PROP appearing on the default-text-properties list.  */
  1692.  
  1693. Lisp_Object
  1694. textget (plist, prop)
  1695.      Lisp_Object plist;
  1696.      register Lisp_Object prop;
  1697. {
  1698.   register Lisp_Object tail, fallback;
  1699.   fallback = Qnil;
  1700.  
  1701.   for (tail = plist; !NILP (tail); tail = Fcdr (Fcdr (tail)))
  1702.     {
  1703.       register Lisp_Object tem;
  1704.       tem = Fcar (tail);
  1705.       if (EQ (prop, tem))
  1706.     return Fcar (Fcdr (tail));
  1707.       if (EQ (tem, Qcategory))
  1708.     {
  1709.       tem = Fcar (Fcdr (tail));
  1710.       if (SYMBOLP (tem))
  1711.         fallback = Fget (tem, prop);
  1712.     }
  1713.     }
  1714.  
  1715.   if (! NILP (fallback))
  1716.     return fallback;
  1717.   if (CONSP (Vdefault_text_properties))
  1718.     return Fplist_get (Vdefault_text_properties, prop);
  1719.   return Qnil;
  1720. }
  1721.  
  1722.  
  1723. /* Set point "temporarily", without checking any text properties.  */
  1724.  
  1725. INLINE void
  1726. temp_set_point (buffer, charpos)
  1727.      struct buffer *buffer;
  1728.      int charpos;
  1729. {
  1730.   temp_set_point_both (buffer, charpos,
  1731.                buf_charpos_to_bytepos (buffer, charpos));
  1732. }
  1733.  
  1734. /* Set point in BUFFER "temporarily" to CHARPOS, which corresponds to
  1735.    byte position BYTEPOS.  */
  1736.  
  1737. INLINE void
  1738. temp_set_point_both (buffer, charpos, bytepos)
  1739.      int charpos, bytepos;
  1740.      struct buffer *buffer;
  1741. {
  1742.   /* In a single-byte buffer, the two positions must be equal.  */
  1743.   if (BUF_ZV (buffer) == BUF_ZV_BYTE (buffer)
  1744.       && charpos != bytepos)
  1745.     abort ();
  1746.  
  1747.   if (charpos > bytepos)
  1748.     abort ();
  1749.  
  1750.   if (charpos > BUF_ZV (buffer) || charpos < BUF_BEGV (buffer))
  1751.     abort ();
  1752.  
  1753.   BUF_PT_BYTE (buffer) = bytepos;
  1754.   BUF_PT (buffer) = charpos;
  1755. }
  1756.  
  1757. /* Set point in BUFFER to CHARPOS.  If the target position is 
  1758.    before an intangible character, move to an ok place.  */
  1759.  
  1760. void
  1761. set_point (buffer, charpos)
  1762.      register struct buffer *buffer;
  1763.      register int charpos;
  1764. {
  1765.   set_point_both (buffer, charpos, buf_charpos_to_bytepos (buffer, charpos));
  1766. }
  1767.  
  1768. /* Set point in BUFFER to CHARPOS, which corresponds to byte
  1769.    position BYTEPOS.  If the target position is 
  1770.    before an intangible character, move to an ok place.  */
  1771.  
  1772. void
  1773. set_point_both (buffer, charpos, bytepos)
  1774.      register struct buffer *buffer;
  1775.      register int charpos, bytepos;
  1776. {
  1777.   register INTERVAL to, from, toprev, fromprev, target;
  1778.   int buffer_point;
  1779.   register Lisp_Object obj;
  1780.   int old_position = BUF_PT (buffer);
  1781.   int backwards = (charpos < old_position ? 1 : 0);
  1782.   int have_overlays;
  1783.   int original_position;
  1784.  
  1785.   buffer->point_before_scroll = Qnil;
  1786.  
  1787.   if (charpos == BUF_PT (buffer))
  1788.     return;
  1789.  
  1790.   /* In a single-byte buffer, the two positions must be equal.  */
  1791.   if (BUF_ZV (buffer) == BUF_ZV_BYTE (buffer)
  1792.       && charpos != bytepos)
  1793.     abort ();
  1794.  
  1795.   /* Check this now, before checking if the buffer has any intervals.
  1796.      That way, we can catch conditions which break this sanity check
  1797.      whether or not there are intervals in the buffer.  */
  1798.   if (charpos > BUF_ZV (buffer) || charpos < BUF_BEGV (buffer))
  1799.     abort ();
  1800.  
  1801.   have_overlays = (! NILP (buffer->overlays_before)
  1802.            || ! NILP (buffer->overlays_after));
  1803.  
  1804.   /* If we have no text properties and overlays,
  1805.      then we can do it quickly.  */
  1806.   if (NULL_INTERVAL_P (BUF_INTERVALS (buffer)) && ! have_overlays)
  1807.     {
  1808.       temp_set_point_both (buffer, charpos, bytepos);
  1809.       return;
  1810.     }
  1811.  
  1812.   /* Set TO to the interval containing the char after CHARPOS,
  1813.      and TOPREV to the interval containing the char before CHARPOS.
  1814.      Either one may be null.  They may be equal.  */
  1815.   to = find_interval (BUF_INTERVALS (buffer), charpos);
  1816.   if (charpos == BUF_BEGV (buffer))
  1817.     toprev = 0;
  1818.   else if (to && to->position == charpos)
  1819.     toprev = previous_interval (to);
  1820.   else
  1821.     toprev = to;
  1822.  
  1823.   buffer_point = (BUF_PT (buffer) == BUF_ZV (buffer)
  1824.           ? BUF_ZV (buffer) - 1
  1825.           : BUF_PT (buffer));
  1826.  
  1827.   /* Set FROM to the interval containing the char after PT,
  1828.      and FROMPREV to the interval containing the char before PT.
  1829.      Either one may be null.  They may be equal.  */
  1830.   /* We could cache this and save time.  */
  1831.   from = find_interval (BUF_INTERVALS (buffer), buffer_point);
  1832.   if (buffer_point == BUF_BEGV (buffer))
  1833.     fromprev = 0;
  1834.   else if (from && from->position == BUF_PT (buffer))
  1835.     fromprev = previous_interval (from);
  1836.   else if (buffer_point != BUF_PT (buffer))
  1837.     fromprev = from, from = 0;
  1838.   else
  1839.     fromprev = from;
  1840.  
  1841.   /* Moving within an interval.  */
  1842.   if (to == from && toprev == fromprev && INTERVAL_VISIBLE_P (to)
  1843.       && ! have_overlays)
  1844.     {
  1845.       temp_set_point_both (buffer, charpos, bytepos);
  1846.       return;
  1847.     }
  1848.  
  1849.   original_position = charpos;
  1850.  
  1851.   /* If the new position is between two intangible characters
  1852.      with the same intangible property value,
  1853.      move forward or backward until a change in that property.  */
  1854.   if (NILP (Vinhibit_point_motion_hooks)
  1855.       && ((! NULL_INTERVAL_P (to) && ! NULL_INTERVAL_P (toprev))
  1856.       || have_overlays)
  1857.       /* Intangibility never stops us from positioning at the beginning
  1858.      or end of the buffer, so don't bother checking in that case.  */
  1859.       && charpos != BEGV && charpos != ZV)
  1860.     {
  1861.       Lisp_Object intangible_propval;
  1862.       Lisp_Object pos;
  1863.  
  1864.       XSETINT (pos, charpos);
  1865.  
  1866.       if (backwards)
  1867.     {
  1868.       intangible_propval = Fget_char_property (make_number (charpos),
  1869.                            Qintangible, Qnil);
  1870.  
  1871.       /* If following char is intangible,
  1872.          skip back over all chars with matching intangible property.  */
  1873.       if (! NILP (intangible_propval))
  1874.         while (XINT (pos) > BUF_BEGV (buffer)
  1875.            && EQ (Fget_char_property (make_number (XINT (pos) - 1),
  1876.                           Qintangible, Qnil),
  1877.               intangible_propval))
  1878.           pos = Fprevious_char_property_change (pos, Qnil);
  1879.     }
  1880.       else
  1881.     {
  1882.       intangible_propval = Fget_char_property (make_number (charpos - 1),
  1883.                            Qintangible, Qnil);
  1884.  
  1885.       /* If following char is intangible,
  1886.          skip back over all chars with matching intangible property.  */
  1887.       if (! NILP (intangible_propval))
  1888.         while (XINT (pos) < BUF_ZV (buffer)
  1889.            && EQ (Fget_char_property (pos, Qintangible, Qnil),
  1890.               intangible_propval))
  1891.           pos = Fnext_char_property_change (pos, Qnil);
  1892.  
  1893.     }
  1894.  
  1895.       charpos = XINT (pos);
  1896.       bytepos = buf_charpos_to_bytepos (buffer, charpos);
  1897.     }
  1898.  
  1899.   if (charpos != original_position)
  1900.     {
  1901.       /* Set TO to the interval containing the char after CHARPOS,
  1902.      and TOPREV to the interval containing the char before CHARPOS.
  1903.      Either one may be null.  They may be equal.  */
  1904.       to = find_interval (BUF_INTERVALS (buffer), charpos);
  1905.       if (charpos == BUF_BEGV (buffer))
  1906.     toprev = 0;
  1907.       else if (to && to->position == charpos)
  1908.     toprev = previous_interval (to);
  1909.       else
  1910.     toprev = to;
  1911.     }
  1912.  
  1913.   /* Here TO is the interval after the stopping point
  1914.      and TOPREV is the interval before the stopping point.
  1915.      One or the other may be null.  */
  1916.  
  1917.   temp_set_point_both (buffer, charpos, bytepos);
  1918.  
  1919.   /* We run point-left and point-entered hooks here, iff the
  1920.      two intervals are not equivalent.  These hooks take
  1921.      (old_point, new_point) as arguments.  */
  1922.   if (NILP (Vinhibit_point_motion_hooks)
  1923.       && (! intervals_equal (from, to)
  1924.       || ! intervals_equal (fromprev, toprev)))
  1925.     {
  1926.       Lisp_Object leave_after, leave_before, enter_after, enter_before;
  1927.  
  1928.       if (fromprev)
  1929.     leave_after = textget (fromprev->plist, Qpoint_left);
  1930.       else
  1931.     leave_after = Qnil;
  1932.       if (from)
  1933.     leave_before = textget (from->plist, Qpoint_left);
  1934.       else
  1935.     leave_before = Qnil;
  1936.  
  1937.       if (toprev)
  1938.     enter_after = textget (toprev->plist, Qpoint_entered);
  1939.       else
  1940.     enter_after = Qnil;
  1941.       if (to)
  1942.     enter_before = textget (to->plist, Qpoint_entered);
  1943.       else
  1944.     enter_before = Qnil;
  1945.  
  1946.       if (! EQ (leave_before, enter_before) && !NILP (leave_before))
  1947.     call2 (leave_before, make_number (old_position),
  1948.            make_number (charpos));
  1949.       if (! EQ (leave_after, enter_after) && !NILP (leave_after))
  1950.     call2 (leave_after, make_number (old_position),
  1951.            make_number (charpos));
  1952.  
  1953.       if (! EQ (enter_before, leave_before) && !NILP (enter_before))
  1954.     call2 (enter_before, make_number (old_position),
  1955.            make_number (charpos));
  1956.       if (! EQ (enter_after, leave_after) && !NILP (enter_after))
  1957.     call2 (enter_after, make_number (old_position),
  1958.            make_number (charpos));
  1959.     }
  1960. }
  1961.  
  1962. /* Move point to POSITION, unless POSITION is inside an intangible
  1963.    segment that reaches all the way to point.  */
  1964.  
  1965. void
  1966. move_if_not_intangible (position)
  1967.      int position;
  1968. {
  1969.   Lisp_Object pos;
  1970.   Lisp_Object intangible_propval;
  1971.  
  1972.   XSETINT (pos, position);
  1973.  
  1974.   if (! NILP (Vinhibit_point_motion_hooks))
  1975.     /* If intangible is inhibited, always move point to POSITION.  */
  1976.     ;
  1977.   else if (PT < position && XINT (pos) < ZV)
  1978.     {
  1979.       /* We want to move forward, so check the text before POSITION.  */
  1980.  
  1981.       intangible_propval = Fget_char_property (pos,
  1982.                            Qintangible, Qnil);
  1983.  
  1984.       /* If following char is intangible,
  1985.      skip back over all chars with matching intangible property.  */
  1986.       if (! NILP (intangible_propval))
  1987.     while (XINT (pos) > BEGV
  1988.            && EQ (Fget_char_property (make_number (XINT (pos) - 1),
  1989.                       Qintangible, Qnil),
  1990.               intangible_propval))
  1991.       pos = Fprevious_char_property_change (pos, Qnil);
  1992.     }
  1993.   else if (XINT (pos) > BEGV)
  1994.     {
  1995.       /* We want to move backward, so check the text after POSITION.  */
  1996.  
  1997.       intangible_propval = Fget_char_property (make_number (XINT (pos) - 1),
  1998.                            Qintangible, Qnil);
  1999.  
  2000.       /* If following char is intangible,
  2001.      skip back over all chars with matching intangible property.  */
  2002.       if (! NILP (intangible_propval))
  2003.     while (XINT (pos) < ZV
  2004.            && EQ (Fget_char_property (pos, Qintangible, Qnil),
  2005.               intangible_propval))
  2006.       pos = Fnext_char_property_change (pos, Qnil);
  2007.  
  2008.     }
  2009.  
  2010.   /* If the whole stretch between PT and POSITION isn't intangible, 
  2011.      try moving to POSITION (which means we actually move farther
  2012.      if POSITION is inside of intangible text).  */
  2013.  
  2014.   if (XINT (pos) != PT)
  2015.     SET_PT (position);
  2016. }
  2017.  
  2018. /* Return the proper local map for position POSITION in BUFFER.
  2019.    Use the map specified by the local-map property, if any.
  2020.    Otherwise, use BUFFER's local map.  */
  2021.  
  2022. Lisp_Object
  2023. get_local_map (position, buffer)
  2024.      register int position;
  2025.      register struct buffer *buffer;
  2026. {
  2027.   Lisp_Object prop, tem, lispy_position, lispy_buffer;
  2028.   int old_begv, old_zv, old_begv_byte, old_zv_byte;
  2029.  
  2030.   /* Perhaps we should just change `position' to the limit.  */
  2031.   if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
  2032.     abort ();
  2033.  
  2034.   /* Ignore narrowing, so that a local map continues to be valid even if
  2035.      the visible region contains no characters and hence no properties.  */
  2036.   old_begv = BUF_BEGV (buffer);
  2037.   old_zv = BUF_ZV (buffer);
  2038.   old_begv_byte = BUF_BEGV_BYTE (buffer);
  2039.   old_zv_byte = BUF_ZV_BYTE (buffer);
  2040.   BUF_BEGV (buffer) = BUF_BEG (buffer);
  2041.   BUF_ZV (buffer) = BUF_Z (buffer);
  2042.   BUF_BEGV_BYTE (buffer) = BUF_BEG_BYTE (buffer);
  2043.   BUF_ZV_BYTE (buffer) = BUF_Z_BYTE (buffer);
  2044.  
  2045.   /* There are no properties at the end of the buffer, so in that case
  2046.      check for a local map on the last character of the buffer instead.  */
  2047.   if (position == BUF_Z (buffer) && BUF_Z (buffer) > BUF_BEG (buffer))
  2048.     --position;
  2049.   XSETFASTINT (lispy_position, position);
  2050.   XSETBUFFER (lispy_buffer, buffer);
  2051.   prop = Fget_char_property (lispy_position, Qlocal_map, lispy_buffer);
  2052.  
  2053.   BUF_BEGV (buffer) = old_begv;
  2054.   BUF_ZV (buffer) = old_zv;
  2055.   BUF_BEGV_BYTE (buffer) = old_begv_byte;
  2056.   BUF_ZV_BYTE (buffer) = old_zv_byte;
  2057.  
  2058.   /* Use the local map only if it is valid.  */
  2059.   /* Do allow symbols that are defined as keymaps.  */
  2060.   if (SYMBOLP (prop) && !NILP (prop))
  2061.     prop = Findirect_function (prop);
  2062.   if (!NILP (prop)
  2063.       && (tem = Fkeymapp (prop), !NILP (tem)))
  2064.     return prop;
  2065.  
  2066.   return buffer->keymap;
  2067. }
  2068.  
  2069. /* Produce an interval tree reflecting the intervals in
  2070.    TREE from START to START + LENGTH.
  2071.    The new interval tree has no parent and has a starting-position of 0.  */
  2072.  
  2073. INTERVAL
  2074. copy_intervals (tree, start, length)
  2075.      INTERVAL tree;
  2076.      int start, length;
  2077. {
  2078.   register INTERVAL i, new, t;
  2079.   register int got, prevlen;
  2080.  
  2081.   if (NULL_INTERVAL_P (tree) || length <= 0)
  2082.     return NULL_INTERVAL;
  2083.  
  2084.   i = find_interval (tree, start);
  2085.   if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
  2086.     abort ();
  2087.  
  2088.   /* If there is only one interval and it's the default, return nil.  */
  2089.   if ((start - i->position + 1 + length) < LENGTH (i)
  2090.       && DEFAULT_INTERVAL_P (i))
  2091.     return NULL_INTERVAL;
  2092.  
  2093.   new = make_interval ();
  2094.   new->position = 0;
  2095.   got = (LENGTH (i) - (start - i->position));
  2096.   new->total_length = length;
  2097.   copy_properties (i, new);
  2098.  
  2099.   t = new;
  2100.   prevlen = got;
  2101.   while (got < length)
  2102.     {
  2103.       i = next_interval (i);
  2104.       t = split_interval_right (t, prevlen);
  2105.       copy_properties (i, t);
  2106.       prevlen = LENGTH (i);
  2107.       got += prevlen;
  2108.     }
  2109.  
  2110.   return balance_an_interval (new);
  2111. }
  2112.  
  2113. /* Give STRING the properties of BUFFER from POSITION to LENGTH.  */
  2114.  
  2115. INLINE void
  2116. copy_intervals_to_string (string, buffer, position, length)
  2117.      Lisp_Object string;
  2118.      struct buffer *buffer;
  2119.      int position, length;
  2120. {
  2121.   INTERVAL interval_copy = copy_intervals (BUF_INTERVALS (buffer),
  2122.                        position, length);
  2123.   if (NULL_INTERVAL_P (interval_copy))
  2124.     return;
  2125.  
  2126.   interval_copy->parent = (INTERVAL) XFASTINT (string);
  2127.   XSTRING (string)->intervals = interval_copy;
  2128. }
  2129.  
  2130. /* Return 1 if strings S1 and S2 have identical properties; 0 otherwise.
  2131.    Assume they have identical characters.  */
  2132.  
  2133. int
  2134. compare_string_intervals (s1, s2)
  2135.      Lisp_Object s1, s2;
  2136. {
  2137.   INTERVAL i1, i2;
  2138.   int pos = 0;
  2139.   int end = XSTRING (s1)->size;
  2140.  
  2141.   i1 = find_interval (XSTRING (s1)->intervals, 0);
  2142.   i2 = find_interval (XSTRING (s2)->intervals, 0);
  2143.  
  2144.   while (pos < end)
  2145.     {
  2146.       /* Determine how far we can go before we reach the end of I1 or I2.  */
  2147.       int len1 = (i1 != 0 ? INTERVAL_LAST_POS (i1) : end) - pos;
  2148.       int len2 = (i2 != 0 ? INTERVAL_LAST_POS (i2) : end) - pos;
  2149.       int distance = min (len1, len2);
  2150.  
  2151.       /* If we ever find a mismatch between the strings,
  2152.      they differ.  */
  2153.       if (! intervals_equal (i1, i2))
  2154.     return 0;
  2155.  
  2156.       /* Advance POS till the end of the shorter interval,
  2157.      and advance one or both interval pointers for the new position.  */
  2158.       pos += distance;
  2159.       if (len1 == distance)
  2160.     i1 = next_interval (i1);
  2161.       if (len2 == distance)
  2162.     i2 = next_interval (i2);
  2163.     }
  2164.   return 1;
  2165. }
  2166.  
  2167. /* Recursively adjust interval I in the current buffer
  2168.    for setting enable_multibyte_characters to MULTI_FLAG.
  2169.    The range of interval I is START ... END in characters,
  2170.    START_BYTE ... END_BYTE in bytes.  */
  2171.  
  2172. static void
  2173. set_intervals_multibyte_1 (i, multi_flag, start, start_byte, end, end_byte)
  2174.      INTERVAL i;
  2175.      int multi_flag;
  2176.      int start, start_byte, end, end_byte;
  2177. {
  2178.   INTERVAL left, right;
  2179.  
  2180.   /* Fix the length of this interval.  */
  2181.   if (multi_flag)
  2182.     i->total_length = end - start;
  2183.   else
  2184.     i->total_length = end_byte - start_byte;
  2185.  
  2186.   /* Recursively fix the length of the subintervals.  */
  2187.   if (i->left)
  2188.     {
  2189.       int left_end, left_end_byte;
  2190.  
  2191.       if (multi_flag)
  2192.     {
  2193.       left_end_byte = start_byte + LEFT_TOTAL_LENGTH (i);
  2194.       left_end = BYTE_TO_CHAR (left_end_byte);
  2195.     }
  2196.       else
  2197.     {
  2198.       left_end = start + LEFT_TOTAL_LENGTH (i);
  2199.       left_end_byte = CHAR_TO_BYTE (left_end);
  2200.     }
  2201.  
  2202.       set_intervals_multibyte_1 (i->left, multi_flag, start, start_byte,
  2203.                  left_end, left_end_byte);
  2204.     }
  2205.   if (i->right)
  2206.     {
  2207.       int right_start_byte, right_start;
  2208.  
  2209.       if (multi_flag)
  2210.     {
  2211.       right_start_byte = end_byte - RIGHT_TOTAL_LENGTH (i);
  2212.       right_start = BYTE_TO_CHAR (right_start_byte);
  2213.     }
  2214.       else
  2215.     {
  2216.       right_start = end - RIGHT_TOTAL_LENGTH (i);
  2217.       right_start_byte = CHAR_TO_BYTE (right_start);
  2218.     }
  2219.  
  2220.       set_intervals_multibyte_1 (i->right, multi_flag,
  2221.                  right_start, right_start_byte,
  2222.                  end, end_byte);
  2223.     }
  2224. }
  2225.  
  2226. /* Update the intervals of the current buffer
  2227.    to fit the contents as multibyte (if MULTI_FLAG is 1)
  2228.    or to fit them as non-multibyte (if MULTI_FLAG is 0).  */
  2229.  
  2230. void
  2231. set_intervals_multibyte (multi_flag)
  2232.      int multi_flag;
  2233. {
  2234.   if (BUF_INTERVALS (current_buffer))
  2235.     set_intervals_multibyte_1 (BUF_INTERVALS (current_buffer), multi_flag,
  2236.                    BEG, BEG_BYTE, Z, Z_BYTE);
  2237. }
  2238.  
  2239. #endif /* USE_TEXT_PROPERTIES */
  2240.