#include <config.h>
#include "lisp.h"
#include "intervals.h"
#include "buffer.h"
#include "puresize.h"
#include "keyboard.h"
#define TMEM(sym, set) (CONSP (set) ? ! NILP (Fmemq (sym, set)) : ! NILP (set))
#define min(x, y) ((x) < (y) ? (x) : (y))
Lisp_Object merge_properties_sticky ();
static INTERVAL reproduce_tree P_ ((INTERVAL, INTERVAL));
static INTERVAL reproduce_tree_obj P_ ((INTERVAL, Lisp_Object));
INTERVAL
create_root_interval (parent)
Lisp_Object parent;
{
INTERVAL new;
CHECK_IMPURE (parent);
new = make_interval ();
if (BUFFERP (parent))
{
new->total_length = (BUF_Z (XBUFFER (parent))
- BUF_BEG (XBUFFER (parent)));
BUF_INTERVALS (XBUFFER (parent)) = new;
new->position = 1;
}
else if (STRINGP (parent))
{
new->total_length = XSTRING (parent)->size;
XSTRING (parent)->intervals = new;
new->position = 0;
}
SET_INTERVAL_OBJECT (new, parent);
return new;
}
void
copy_properties (source, target)
register INTERVAL source, target;
{
if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
return;
COPY_INTERVAL_CACHE (source, target);
target->plist = Fcopy_sequence (source->plist);
}
static void
merge_properties (source, target)
register INTERVAL source, target;
{
register Lisp_Object o, sym, val;
if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
return;
MERGE_INTERVAL_CACHE (source, target);
o = source->plist;
while (! EQ (o, Qnil))
{
sym = Fcar (o);
val = Fmemq (sym, target->plist);
if (NILP (val))
{
o = Fcdr (o);
val = Fcar (o);
target->plist = Fcons (sym, Fcons (val, target->plist));
o = Fcdr (o);
}
else
o = Fcdr (Fcdr (o));
}
}
int
intervals_equal (i0, i1)
INTERVAL i0, i1;
{
register Lisp_Object i0_cdr, i0_sym, i1_val;
register int i1_len;
if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
return 1;
if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1))
return 0;
i1_len = XFASTINT (Flength (i1->plist));
if (i1_len & 0x1)
abort ();
i1_len /= 2;
i0_cdr = i0->plist;
while (!NILP (i0_cdr))
{
if (i1_len == 0)
return 0;
i0_sym = Fcar (i0_cdr);
i1_val = Fmemq (i0_sym, i1->plist);
if (EQ (i1_val, Qnil))
return 0;
i0_cdr = Fcdr (i0_cdr);
if (! EQ (Fcar (Fcdr (i1_val)), Fcar (i0_cdr)))
return 0;
i0_cdr = Fcdr (i0_cdr);
i1_len--;
}
if (i1_len > 0)
return 0;
return 1;
}
void
traverse_intervals (tree, position, depth, function, arg)
INTERVAL tree;
int position, depth;
void (* function) P_ ((INTERVAL, Lisp_Object));
Lisp_Object arg;
{
if (NULL_INTERVAL_P (tree))
return;
traverse_intervals (tree->left, position, depth + 1, function, arg);
position += LEFT_TOTAL_LENGTH (tree);
tree->position = position;
(*function) (tree, arg);
position += LENGTH (tree);
traverse_intervals (tree->right, position, depth + 1, function, arg);
}
#if 0
static int icount;
static int idepth;
static int zero_length;
INTERVAL search_interval, found_interval;
void
check_for_interval (i)
register INTERVAL i;
{
if (i == search_interval)
{
found_interval = i;
icount++;
}
}
INTERVAL
search_for_interval (i, tree)
register INTERVAL i, tree;
{
icount = 0;
search_interval = i;
found_interval = NULL_INTERVAL;
traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
return found_interval;
}
static void
inc_interval_count (i)
INTERVAL i;
{
icount++;
if (LENGTH (i) == 0)
zero_length++;
if (depth > idepth)
idepth = depth;
}
int
count_intervals (i)
register INTERVAL i;
{
icount = 0;
idepth = 0;
zero_length = 0;
traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);
return icount;
}
static INTERVAL
root_interval (interval)
INTERVAL interval;
{
register INTERVAL i = interval;
while (! ROOT_INTERVAL_P (i))
i = INTERVAL_PARENT (i);
return i;
}
#endif
static INTERVAL
rotate_right (interval)
INTERVAL interval;
{
INTERVAL i;
INTERVAL B = interval->left;
int old_total = interval->total_length;
if (! ROOT_INTERVAL_P (interval))
{
if (AM_LEFT_CHILD (interval))
INTERVAL_PARENT (interval)->left = B;
else
INTERVAL_PARENT (interval)->right = B;
}
COPY_INTERVAL_PARENT (B, interval);
i = B->right;
B->right = interval;
SET_INTERVAL_PARENT (interval, B);
interval->left = i;
if (! NULL_INTERVAL_P (i))
SET_INTERVAL_PARENT (i, interval);
interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);
B->total_length = old_total;
return B;
}
static INTERVAL
rotate_left (interval)
INTERVAL interval;
{
INTERVAL i;
INTERVAL B = interval->right;
int old_total = interval->total_length;
if (! ROOT_INTERVAL_P (interval))
{
if (AM_LEFT_CHILD (interval))
INTERVAL_PARENT (interval)->left = B;
else
INTERVAL_PARENT (interval)->right = B;
}
COPY_INTERVAL_PARENT (B, interval);
i = B->left;
B->left = interval;
SET_INTERVAL_PARENT (interval, B);
interval->right = i;
if (! NULL_INTERVAL_P (i))
SET_INTERVAL_PARENT (i, interval);
interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval);
B->total_length = old_total;
return B;
}
static INTERVAL
balance_an_interval (i)
INTERVAL i;
{
register int old_diff, new_diff;
while (1)
{
old_diff = LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i);
if (old_diff > 0)
{
new_diff = i->total_length - i->left->total_length
+ RIGHT_TOTAL_LENGTH (i->left) - LEFT_TOTAL_LENGTH (i->left);
if (abs (new_diff) >= old_diff)
break;
i = rotate_right (i);
balance_an_interval (i->right);
}
else if (old_diff < 0)
{
new_diff = i->total_length - i->right->total_length
+ LEFT_TOTAL_LENGTH (i->right) - RIGHT_TOTAL_LENGTH (i->right);
if (abs (new_diff) >= -old_diff)
break;
i = rotate_left (i);
balance_an_interval (i->left);
}
else
break;
}
return i;
}
static INLINE INTERVAL
balance_possible_root_interval (interval)
register INTERVAL interval;
{
Lisp_Object parent;
int have_parent = 0;
if (!INTERVAL_HAS_OBJECT (interval) && !INTERVAL_HAS_PARENT (interval))
return interval;
if (INTERVAL_HAS_OBJECT (interval))
{
have_parent = 1;
GET_INTERVAL_OBJECT (parent, interval);
}
interval = balance_an_interval (interval);
if (have_parent)
{
if (BUFFERP (parent))
BUF_INTERVALS (XBUFFER (parent)) = interval;
else if (STRINGP (parent))
XSTRING (parent)->intervals = interval;
}
return interval;
}
static INTERVAL
balance_intervals_internal (tree)
register INTERVAL tree;
{
if (tree->left)
balance_intervals_internal (tree->left);
if (tree->right)
balance_intervals_internal (tree->right);
return balance_an_interval (tree);
}
INTERVAL
balance_intervals (tree)
INTERVAL tree;
{
if (tree == NULL_INTERVAL)
return NULL_INTERVAL;
return balance_intervals_internal (tree);
}
INTERVAL
split_interval_right (interval, offset)
INTERVAL interval;
int offset;
{
INTERVAL new = make_interval ();
int position = interval->position;
int new_length = LENGTH (interval) - offset;
new->position = position + offset;
SET_INTERVAL_PARENT (new, interval);
if (NULL_RIGHT_CHILD (interval))
{
interval->right = new;
new->total_length = new_length;
}
else
{
new->right = interval->right;
SET_INTERVAL_PARENT (interval->right, new);
interval->right = new;
new->total_length = new_length + new->right->total_length;
balance_an_interval (new);
}
balance_possible_root_interval (interval);
return new;
}
INTERVAL
split_interval_left (interval, offset)
INTERVAL interval;
int offset;
{
INTERVAL new = make_interval ();
int new_length = offset;
new->position = interval->position;
interval->position = interval->position + offset;
SET_INTERVAL_PARENT (new, interval);
if (NULL_LEFT_CHILD (interval))
{
interval->left = new;
new->total_length = new_length;
}
else
{
new->left = interval->left;
SET_INTERVAL_PARENT (new->left, new);
interval->left = new;
new->total_length = new_length + new->left->total_length;
balance_an_interval (new);
}
balance_possible_root_interval (interval);
return new;
}
int
interval_start_pos (source)
INTERVAL source;
{
Lisp_Object parent;
if (NULL_INTERVAL_P (source))
return 0;
if (! INTERVAL_HAS_OBJECT (source))
return 0;
GET_INTERVAL_OBJECT (parent, source);
if (BUFFERP (parent))
return BUF_BEG (XBUFFER (parent));
return 0;
}
INTERVAL
find_interval (tree, position)
register INTERVAL tree;
register int position;
{
register int relative_position;
if (NULL_INTERVAL_P (tree))
return NULL_INTERVAL;
relative_position = position;
if (INTERVAL_HAS_OBJECT (tree))
{
Lisp_Object parent;
GET_INTERVAL_OBJECT (parent, tree);
if (BUFFERP (parent))
relative_position -= BUF_BEG (XBUFFER (parent));
}
if (relative_position > TOTAL_LENGTH (tree))
abort ();
if (!handling_signal)
tree = balance_possible_root_interval (tree);
while (1)
{
if (relative_position < LEFT_TOTAL_LENGTH (tree))
{
tree = tree->left;
}
else if (! NULL_RIGHT_CHILD (tree)
&& relative_position >= (TOTAL_LENGTH (tree)
- RIGHT_TOTAL_LENGTH (tree)))
{
relative_position -= (TOTAL_LENGTH (tree)
- RIGHT_TOTAL_LENGTH (tree));
tree = tree->right;
}
else
{
tree->position
= (position - relative_position
+ LEFT_TOTAL_LENGTH (tree));
return tree;
}
}
}
INTERVAL
next_interval (interval)
register INTERVAL interval;
{
register INTERVAL i = interval;
register int next_position;
if (NULL_INTERVAL_P (i))
return NULL_INTERVAL;
next_position = interval->position + LENGTH (interval);
if (! NULL_RIGHT_CHILD (i))
{
i = i->right;
while (! NULL_LEFT_CHILD (i))
i = i->left;
i->position = next_position;
return i;
}
while (! NULL_PARENT (i))
{
if (AM_LEFT_CHILD (i))
{
i = INTERVAL_PARENT (i);
i->position = next_position;
return i;
}
i = INTERVAL_PARENT (i);
}
return NULL_INTERVAL;
}
INTERVAL
previous_interval (interval)
register INTERVAL interval;
{
register INTERVAL i;
if (NULL_INTERVAL_P (interval))
return NULL_INTERVAL;
if (! NULL_LEFT_CHILD (interval))
{
i = interval->left;
while (! NULL_RIGHT_CHILD (i))
i = i->right;
i->position = interval->position - LENGTH (i);
return i;
}
i = interval;
while (! NULL_PARENT (i))
{
if (AM_RIGHT_CHILD (i))
{
i = INTERVAL_PARENT (i);
i->position = interval->position - LENGTH (i);
return i;
}
i = INTERVAL_PARENT (i);
}
return NULL_INTERVAL;
}
INTERVAL
update_interval (i, pos)
register INTERVAL i;
int pos;
{
if (NULL_INTERVAL_P (i))
return NULL_INTERVAL;
while (1)
{
if (pos < i->position)
{
if (pos >= i->position - TOTAL_LENGTH (i->left))
{
i->left->position = i->position - TOTAL_LENGTH (i->left)
+ LEFT_TOTAL_LENGTH (i->left);
i = i->left;
}
else if (NULL_PARENT (i))
error ("Point before start of properties");
else
i = INTERVAL_PARENT (i);
continue;
}
else if (pos >= INTERVAL_LAST_POS (i))
{
if (pos < INTERVAL_LAST_POS (i) + TOTAL_LENGTH (i->right))
{
i->right->position = INTERVAL_LAST_POS (i) +
LEFT_TOTAL_LENGTH (i->right);
i = i->right;
}
else if (NULL_PARENT (i))
error ("Point after end of properties");
else
i = INTERVAL_PARENT (i);
continue;
}
else
return i;
}
}
#if 0
static INTERVAL
adjust_intervals_for_insertion (tree, position, length)
INTERVAL tree;
int position, length;
{
register int relative_position;
register INTERVAL this;
if (TOTAL_LENGTH (tree) == 0)
abort ();
if (position > TOTAL_LENGTH (tree))
position = TOTAL_LENGTH (tree);
relative_position = position;
this = tree;
while (1)
{
if (relative_position <= LEFT_TOTAL_LENGTH (this))
{
this->total_length += length;
this = this->left;
}
else if (relative_position > (TOTAL_LENGTH (this)
- RIGHT_TOTAL_LENGTH (this)))
{
relative_position -= (TOTAL_LENGTH (this)
- RIGHT_TOTAL_LENGTH (this));
this->total_length += length;
this = this->right;
}
else
{
this->total_length += length;
this->position = LEFT_TOTAL_LENGTH (this)
+ position - relative_position + 1;
return tree;
}
}
}
#endif
static INTERVAL
adjust_intervals_for_insertion (tree, position, length)
INTERVAL tree;
int position, length;
{
register INTERVAL i;
register INTERVAL temp;
int eobp = 0;
Lisp_Object parent;
int offset;
if (TOTAL_LENGTH (tree) == 0)
abort ();
GET_INTERVAL_OBJECT (parent, tree);
offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0);
if (position >= TOTAL_LENGTH (tree) + offset)
{
position = TOTAL_LENGTH (tree) + offset;
eobp = 1;
}
i = find_interval (tree, position);
if (! (position == i->position || eobp))
{
Lisp_Object tail;
Lisp_Object front, rear;
tail = i->plist;
rear = textget (i->plist, Qrear_nonsticky);
if (! CONSP (rear) && ! NILP (rear))
{
goto check_done;
}
front = textget (i->plist, Qfront_sticky);
if (! CONSP (front) && ! NILP (front))
{
tail = Qnil;
goto check_done;
}
for (; CONSP (tail); tail = Fcdr (XCDR (tail)))
{
Lisp_Object prop, tmp;
prop = XCAR (tail);
if (CONSP (front) && ! NILP (Fmemq (prop, front)))
continue;
if (CONSP (rear) && ! NILP (Fmemq (prop, rear)))
break;
tmp = Fassq (prop, Vtext_property_default_nonsticky);
if (CONSP (tmp))
{
if (NILP (tmp))
continue;
break;
}
}
check_done:
if (! NILP (tail))
{
temp = split_interval_right (i, position - i->position);
copy_properties (i, temp);
i = temp;
}
}
if (position == i->position || eobp)
{
register INTERVAL prev;
if (position == BEG)
prev = 0;
else if (eobp)
{
prev = i;
i = 0;
}
else
prev = previous_interval (i);
for (temp = prev ? prev : i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
{
temp->total_length += length;
temp = balance_possible_root_interval (temp);
}
if (1)
{
Lisp_Object pleft, pright;
struct interval newi;
pleft = NULL_INTERVAL_P (prev) ? Qnil : prev->plist;
pright = NULL_INTERVAL_P (i) ? Qnil : i->plist;
newi.plist = merge_properties_sticky (pleft, pright);
if (! prev)
{
if (! intervals_equal (i, &newi))
{
i = split_interval_left (i, length);
i->plist = newi.plist;
}
}
else if (! intervals_equal (prev, &newi))
{
prev = split_interval_right (prev,
position - prev->position);
prev->plist = newi.plist;
if (! NULL_INTERVAL_P (i)
&& intervals_equal (prev, i))
merge_interval_right (prev);
}
}
else if (! prev && ! NILP (i->plist))
{
i = split_interval_left (i, length);
}
}
else
{
for (temp = i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
{
temp->total_length += length;
temp = balance_possible_root_interval (temp);
}
}
return tree;
}
Lisp_Object
merge_properties_sticky (pleft, pright)
Lisp_Object pleft, pright;
{
register Lisp_Object props, front, rear;
Lisp_Object lfront, lrear, rfront, rrear;
register Lisp_Object tail1, tail2, sym, lval, rval, cat;
int use_left, use_right;
int lpresent;
props = Qnil;
front = Qnil;
rear = Qnil;
lfront = textget (pleft, Qfront_sticky);
lrear = textget (pleft, Qrear_nonsticky);
rfront = textget (pright, Qfront_sticky);
rrear = textget (pright, Qrear_nonsticky);
for (tail1 = pright; CONSP (tail1); tail1 = Fcdr (Fcdr (tail1)))
{
Lisp_Object tmp;
sym = Fcar (tail1);
if (EQ (sym, Qrear_nonsticky) || EQ (sym, Qfront_sticky))
continue;
rval = Fcar (Fcdr (tail1));
for (tail2 = pleft; CONSP (tail2); tail2 = Fcdr (Fcdr (tail2)))
if (EQ (sym, Fcar (tail2)))
break;
lpresent = ! NILP (tail2);
lval = (NILP (tail2) ? Qnil : Fcar (Fcdr (tail2)));
tmp = Fassq (sym, Vtext_property_default_nonsticky);
use_left = (lpresent
&& ! (TMEM (sym, lrear)
|| CONSP (tmp) && ! NILP (XCDR (tmp))));
use_right = (TMEM (sym, rfront)
|| (CONSP (tmp) && NILP (XCDR (tmp))));
if (use_left && use_right)
{
if (NILP (lval))
use_left = 0;
else if (NILP (rval))
use_right = 0;
}
if (use_left)
{
props = Fcons (lval, Fcons (sym, props));
if (TMEM (sym, lfront))
front = Fcons (sym, front);
if (TMEM (sym, lrear))
rear = Fcons (sym, rear);
}
else if (use_right)
{
props = Fcons (rval, Fcons (sym, props));
if (TMEM (sym, rfront))
front = Fcons (sym, front);
if (TMEM (sym, rrear))
rear = Fcons (sym, rear);
}
}
for (tail2 = pleft; CONSP (tail2); tail2 = Fcdr (Fcdr (tail2)))
{
Lisp_Object tmp;
sym = Fcar (tail2);
if (EQ (sym, Qrear_nonsticky) || EQ (sym, Qfront_sticky))
continue;
for (tail1 = pright; CONSP (tail1); tail1 = Fcdr (Fcdr (tail1)))
if (EQ (sym, Fcar (tail1)))
break;
if (! NILP (tail1))
continue;
lval = Fcar (Fcdr (tail2));
tmp = Fassq (sym, Vtext_property_default_nonsticky);
if (! (TMEM (sym, lrear) || (CONSP (tmp) && ! NILP (XCDR (tmp)))))
{
props = Fcons (lval, Fcons (sym, props));
if (TMEM (sym, lfront))
front = Fcons (sym, front);
}
else if (TMEM (sym, rfront) || (CONSP (tmp) && NILP (XCDR (tmp))))
{
front = Fcons (sym, front);
if (TMEM (sym, rrear))
rear = Fcons (sym, rear);
}
}
props = Fnreverse (props);
if (! NILP (rear))
props = Fcons (Qrear_nonsticky, Fcons (Fnreverse (rear), props));
cat = textget (props, Qcategory);
if (! NILP (front)
&&
! (! NILP (cat) && SYMBOLP (cat)
&& EQ (Fget (cat, Qfront_sticky), Qt)))
props = Fcons (Qfront_sticky, Fcons (Fnreverse (front), props));
return props;
}
static INTERVAL
delete_node (i)
register INTERVAL i;
{
register INTERVAL migrate, this;
register int migrate_amt;
if (NULL_INTERVAL_P (i->left))
return i->right;
if (NULL_INTERVAL_P (i->right))
return i->left;
migrate = i->left;
migrate_amt = i->left->total_length;
this = i->right;
this->total_length += migrate_amt;
while (! NULL_INTERVAL_P (this->left))
{
this = this->left;
this->total_length += migrate_amt;
}
this->left = migrate;
SET_INTERVAL_PARENT (migrate, this);
return i->right;
}
void
delete_interval (i)
register INTERVAL i;
{
register INTERVAL parent;
int amt = LENGTH (i);
if (amt > 0)
abort ();
if (ROOT_INTERVAL_P (i))
{
Lisp_Object owner;
GET_INTERVAL_OBJECT (owner, i);
parent = delete_node (i);
if (! NULL_INTERVAL_P (parent))
SET_INTERVAL_OBJECT (parent, owner);
if (BUFFERP (owner))
BUF_INTERVALS (XBUFFER (owner)) = parent;
else if (STRINGP (owner))
XSTRING (owner)->intervals = parent;
else
abort ();
return;
}
parent = INTERVAL_PARENT (i);
if (AM_LEFT_CHILD (i))
{
parent->left = delete_node (i);
if (! NULL_INTERVAL_P (parent->left))
SET_INTERVAL_PARENT (parent->left, parent);
}
else
{
parent->right = delete_node (i);
if (! NULL_INTERVAL_P (parent->right))
SET_INTERVAL_PARENT (parent->right, parent);
}
}
static int
interval_deletion_adjustment (tree, from, amount)
register INTERVAL tree;
register int from, amount;
{
register int relative_position = from;
if (NULL_INTERVAL_P (tree))
return 0;
if (relative_position < LEFT_TOTAL_LENGTH (tree))
{
int subtract = interval_deletion_adjustment (tree->left,
relative_position,
amount);
tree->total_length -= subtract;
return subtract;
}
else if (relative_position >= (TOTAL_LENGTH (tree)
- RIGHT_TOTAL_LENGTH (tree)))
{
int subtract;
relative_position -= (tree->total_length
- RIGHT_TOTAL_LENGTH (tree));
subtract = interval_deletion_adjustment (tree->right,
relative_position,
amount);
tree->total_length -= subtract;
return subtract;
}
else
{
int my_amount = ((tree->total_length
- RIGHT_TOTAL_LENGTH (tree))
- relative_position);
if (amount > my_amount)
amount = my_amount;
tree->total_length -= amount;
if (LENGTH (tree) == 0)
delete_interval (tree);
return amount;
}
}
static void
adjust_intervals_for_deletion (buffer, start, length)
struct buffer *buffer;
int start, length;
{
register int left_to_delete = length;
register INTERVAL tree = BUF_INTERVALS (buffer);
Lisp_Object parent;
int offset;
GET_INTERVAL_OBJECT (parent, tree);
offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0);
if (NULL_INTERVAL_P (tree))
return;
if (start > offset + TOTAL_LENGTH (tree)
|| start + length > offset + TOTAL_LENGTH (tree))
abort ();
if (length == TOTAL_LENGTH (tree))
{
BUF_INTERVALS (buffer) = NULL_INTERVAL;
return;
}
if (ONLY_INTERVAL_P (tree))
{
tree->total_length -= length;
return;
}
if (start > offset + TOTAL_LENGTH (tree))
start = offset + TOTAL_LENGTH (tree);
while (left_to_delete > 0)
{
left_to_delete -= interval_deletion_adjustment (tree, start - offset,
left_to_delete);
tree = BUF_INTERVALS (buffer);
if (left_to_delete == tree->total_length)
{
BUF_INTERVALS (buffer) = NULL_INTERVAL;
return;
}
}
}
INLINE void
offset_intervals (buffer, start, length)
struct buffer *buffer;
int start, length;
{
if (NULL_INTERVAL_P (BUF_INTERVALS (buffer)) || length == 0)
return;
if (length > 0)
adjust_intervals_for_insertion (BUF_INTERVALS (buffer), start, length);
else
adjust_intervals_for_deletion (buffer, start, -length);
}
INTERVAL
merge_interval_right (i)
register INTERVAL i;
{
register int absorb = LENGTH (i);
register INTERVAL successor;
i->total_length -= absorb;
if (! NULL_RIGHT_CHILD (i))
{
successor = i->right;
while (! NULL_LEFT_CHILD (successor))
{
successor->total_length += absorb;
successor = successor->left;
}
successor->total_length += absorb;
delete_interval (i);
return successor;
}
successor = i;
while (! NULL_PARENT (successor))
{
if (AM_LEFT_CHILD (successor))
{
successor = INTERVAL_PARENT (successor);
delete_interval (i);
return successor;
}
successor = INTERVAL_PARENT (successor);
successor->total_length -= absorb;
}
abort ();
}
INTERVAL
merge_interval_left (i)
register INTERVAL i;
{
register int absorb = LENGTH (i);
register INTERVAL predecessor;
i->total_length -= absorb;
if (! NULL_LEFT_CHILD (i))
{
predecessor = i->left;
while (! NULL_RIGHT_CHILD (predecessor))
{
predecessor->total_length += absorb;
predecessor = predecessor->right;
}
predecessor->total_length += absorb;
delete_interval (i);
return predecessor;
}
predecessor = i;
while (! NULL_PARENT (predecessor))
{
if (AM_RIGHT_CHILD (predecessor))
{
predecessor = INTERVAL_PARENT (predecessor);
delete_interval (i);
return predecessor;
}
predecessor = INTERVAL_PARENT (predecessor);
predecessor->total_length -= absorb;
}
abort ();
}
static INTERVAL
reproduce_tree (source, parent)
INTERVAL source, parent;
{
register INTERVAL t = make_interval ();
bcopy (source, t, INTERVAL_SIZE);
copy_properties (source, t);
SET_INTERVAL_PARENT (t, parent);
if (! NULL_LEFT_CHILD (source))
t->left = reproduce_tree (source->left, t);
if (! NULL_RIGHT_CHILD (source))
t->right = reproduce_tree (source->right, t);
return t;
}
static INTERVAL
reproduce_tree_obj (source, parent)
INTERVAL source;
Lisp_Object parent;
{
register INTERVAL t = make_interval ();
bcopy (source, t, INTERVAL_SIZE);
copy_properties (source, t);
SET_INTERVAL_OBJECT (t, parent);
if (! NULL_LEFT_CHILD (source))
t->left = reproduce_tree (source->left, t);
if (! NULL_RIGHT_CHILD (source))
t->right = reproduce_tree (source->right, t);
return t;
}
#if 0
static INTERVAL
make_new_interval (intervals, start, length)
INTERVAL intervals;
int start, length;
{
INTERVAL slot;
slot = find_interval (intervals, start);
if (start + length > slot->position + LENGTH (slot))
error ("Interval would overlap");
if (start == slot->position && length == LENGTH (slot))
return slot;
if (slot->position == start)
{
split_interval_right (slot, length);
return slot;
}
if (slot->position + LENGTH (slot) == start + length)
{
split_interval_left (slot, LENGTH (slot) - length);
return slot;
}
split_interval_left (slot, start - slot->position);
split_interval_right (slot, length);
return slot;
}
#endif
void
graft_intervals_into_buffer (source, position, length, buffer, inherit)
INTERVAL source;
int position, length;
struct buffer *buffer;
int inherit;
{
register INTERVAL under, over, this, prev;
register INTERVAL tree;
int middle;
tree = BUF_INTERVALS (buffer);
if (NULL_INTERVAL_P (source))
{
Lisp_Object buf;
if (!inherit && ! NULL_INTERVAL_P (tree))
{
int saved_inhibit_modification_hooks = inhibit_modification_hooks;
XSETBUFFER (buf, buffer);
inhibit_modification_hooks = 1;
Fset_text_properties (make_number (position),
make_number (position + length),
Qnil, buf);
inhibit_modification_hooks = saved_inhibit_modification_hooks;
}
if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer)))
BUF_INTERVALS (buffer) = balance_an_interval (BUF_INTERVALS (buffer));
return;
}
if (NULL_INTERVAL_P (tree))
{
if ((BUF_Z (buffer) - BUF_BEG (buffer)) == TOTAL_LENGTH (source))
{
Lisp_Object buf;
XSETBUFFER (buf, buffer);
BUF_INTERVALS (buffer) = reproduce_tree_obj (source, buf);
BUF_INTERVALS (buffer)->position = 1;
return;
}
{
Lisp_Object buf;
XSETBUFFER (buf, buffer);
tree = create_root_interval (buf);
}
}
else if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (source))
{
BUF_INTERVALS (buffer) = reproduce_tree (source, INTERVAL_PARENT (tree));
BUF_INTERVALS (buffer)->position = 1;
return;
}
else if (TOTAL_LENGTH (tree) == 0)
abort ();
this = under = find_interval (tree, position);
if (NULL_INTERVAL_P (under))
abort ();
over = find_interval (source, interval_start_pos (source));
if (position > under->position)
{
INTERVAL end_unchanged
= split_interval_left (this, position - under->position);
copy_properties (under, end_unchanged);
under->position = position;
#if 0
prev = 0;
middle = 1;
#endif
}
else
{
prev = previous_interval (under);
#if 0
if (prev && !END_NONSTICKY_P (prev))
prev = 0;
#endif
}
while (! NULL_INTERVAL_P (over))
{
if (LENGTH (over) < LENGTH (under))
{
this = split_interval_left (under, LENGTH (over));
copy_properties (under, this);
}
else
this = under;
copy_properties (over, this);
if (inherit)
merge_properties (over, this);
else
copy_properties (over, this);
over = next_interval (over);
}
if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer)))
BUF_INTERVALS (buffer) = balance_an_interval (BUF_INTERVALS (buffer));
return;
}
Lisp_Object
textget (plist, prop)
Lisp_Object plist;
register Lisp_Object prop;
{
register Lisp_Object tail, fallback;
fallback = Qnil;
for (tail = plist; !NILP (tail); tail = Fcdr (Fcdr (tail)))
{
register Lisp_Object tem;
tem = Fcar (tail);
if (EQ (prop, tem))
return Fcar (Fcdr (tail));
if (EQ (tem, Qcategory))
{
tem = Fcar (Fcdr (tail));
if (SYMBOLP (tem))
fallback = Fget (tem, prop);
}
}
if (! NILP (fallback))
return fallback;
if (CONSP (Vdefault_text_properties))
return Fplist_get (Vdefault_text_properties, prop);
return Qnil;
}
INLINE void
temp_set_point (buffer, charpos)
struct buffer *buffer;
int charpos;
{
temp_set_point_both (buffer, charpos,
buf_charpos_to_bytepos (buffer, charpos));
}
INLINE void
temp_set_point_both (buffer, charpos, bytepos)
int charpos, bytepos;
struct buffer *buffer;
{
if (BUF_ZV (buffer) == BUF_ZV_BYTE (buffer)
&& charpos != bytepos)
abort ();
if (charpos > bytepos)
abort ();
if (charpos > BUF_ZV (buffer) || charpos < BUF_BEGV (buffer))
abort ();
BUF_PT_BYTE (buffer) = bytepos;
BUF_PT (buffer) = charpos;
}
void
set_point (buffer, charpos)
register struct buffer *buffer;
register int charpos;
{
set_point_both (buffer, charpos, buf_charpos_to_bytepos (buffer, charpos));
}
void
set_point_both (buffer, charpos, bytepos)
register struct buffer *buffer;
register int charpos, bytepos;
{
register INTERVAL to, from, toprev, fromprev;
int buffer_point;
int old_position = BUF_PT (buffer);
int backwards = (charpos < old_position ? 1 : 0);
int have_overlays;
int original_position;
buffer->point_before_scroll = Qnil;
if (charpos == BUF_PT (buffer))
return;
if (BUF_ZV (buffer) == BUF_ZV_BYTE (buffer)
&& charpos != bytepos)
abort ();
if (charpos > BUF_ZV (buffer) || charpos < BUF_BEGV (buffer))
abort ();
have_overlays = (! NILP (buffer->overlays_before)
|| ! NILP (buffer->overlays_after));
if (NULL_INTERVAL_P (BUF_INTERVALS (buffer)) && ! have_overlays)
{
temp_set_point_both (buffer, charpos, bytepos);
return;
}
to = find_interval (BUF_INTERVALS (buffer), charpos);
if (charpos == BUF_BEGV (buffer))
toprev = 0;
else if (to && to->position == charpos)
toprev = previous_interval (to);
else
toprev = to;
buffer_point = (BUF_PT (buffer) == BUF_ZV (buffer)
? BUF_ZV (buffer) - 1
: BUF_PT (buffer));
from = find_interval (BUF_INTERVALS (buffer), buffer_point);
if (buffer_point == BUF_BEGV (buffer))
fromprev = 0;
else if (from && from->position == BUF_PT (buffer))
fromprev = previous_interval (from);
else if (buffer_point != BUF_PT (buffer))
fromprev = from, from = 0;
else
fromprev = from;
if (to == from && toprev == fromprev && INTERVAL_VISIBLE_P (to)
&& ! have_overlays)
{
temp_set_point_both (buffer, charpos, bytepos);
return;
}
original_position = charpos;
if (NILP (Vinhibit_point_motion_hooks)
&& ((! NULL_INTERVAL_P (to) && ! NULL_INTERVAL_P (toprev))
|| have_overlays)
&& charpos != BEGV && charpos != ZV)
{
Lisp_Object intangible_propval;
Lisp_Object pos;
XSETINT (pos, charpos);
if (backwards)
{
intangible_propval = Fget_char_property (make_number (charpos),
Qintangible, Qnil);
if (! NILP (intangible_propval))
while (XINT (pos) > BUF_BEGV (buffer)
&& EQ (Fget_char_property (make_number (XINT (pos) - 1),
Qintangible, Qnil),
intangible_propval))
pos = Fprevious_char_property_change (pos, Qnil);
}
else
{
intangible_propval = Fget_char_property (make_number (charpos - 1),
Qintangible, Qnil);
if (! NILP (intangible_propval))
while (XINT (pos) < BUF_ZV (buffer)
&& EQ (Fget_char_property (pos, Qintangible, Qnil),
intangible_propval))
pos = Fnext_char_property_change (pos, Qnil);
}
charpos = XINT (pos);
bytepos = buf_charpos_to_bytepos (buffer, charpos);
}
if (charpos != original_position)
{
to = find_interval (BUF_INTERVALS (buffer), charpos);
if (charpos == BUF_BEGV (buffer))
toprev = 0;
else if (to && to->position == charpos)
toprev = previous_interval (to);
else
toprev = to;
}
temp_set_point_both (buffer, charpos, bytepos);
if (NILP (Vinhibit_point_motion_hooks)
&& (! intervals_equal (from, to)
|| ! intervals_equal (fromprev, toprev)))
{
Lisp_Object leave_after, leave_before, enter_after, enter_before;
if (fromprev)
leave_after = textget (fromprev->plist, Qpoint_left);
else
leave_after = Qnil;
if (from)
leave_before = textget (from->plist, Qpoint_left);
else
leave_before = Qnil;
if (toprev)
enter_after = textget (toprev->plist, Qpoint_entered);
else
enter_after = Qnil;
if (to)
enter_before = textget (to->plist, Qpoint_entered);
else
enter_before = Qnil;
if (! EQ (leave_before, enter_before) && !NILP (leave_before))
call2 (leave_before, make_number (old_position),
make_number (charpos));
if (! EQ (leave_after, enter_after) && !NILP (leave_after))
call2 (leave_after, make_number (old_position),
make_number (charpos));
if (! EQ (enter_before, leave_before) && !NILP (enter_before))
call2 (enter_before, make_number (old_position),
make_number (charpos));
if (! EQ (enter_after, leave_after) && !NILP (enter_after))
call2 (enter_after, make_number (old_position),
make_number (charpos));
}
}
void
move_if_not_intangible (position)
int position;
{
Lisp_Object pos;
Lisp_Object intangible_propval;
XSETINT (pos, position);
if (! NILP (Vinhibit_point_motion_hooks))
;
else if (PT < position && XINT (pos) < ZV)
{
intangible_propval = Fget_char_property (pos,
Qintangible, Qnil);
if (! NILP (intangible_propval))
while (XINT (pos) > BEGV
&& EQ (Fget_char_property (make_number (XINT (pos) - 1),
Qintangible, Qnil),
intangible_propval))
pos = Fprevious_char_property_change (pos, Qnil);
}
else if (XINT (pos) > BEGV)
{
intangible_propval = Fget_char_property (make_number (XINT (pos) - 1),
Qintangible, Qnil);
if (! NILP (intangible_propval))
while (XINT (pos) < ZV
&& EQ (Fget_char_property (pos, Qintangible, Qnil),
intangible_propval))
pos = Fnext_char_property_change (pos, Qnil);
}
if (XINT (pos) != PT)
SET_PT (position);
}
int
get_property_and_range (pos, prop, val, start, end, object)
int pos;
Lisp_Object prop, *val;
int *start, *end;
Lisp_Object object;
{
INTERVAL i, prev, next;
if (NILP (object))
i = find_interval (BUF_INTERVALS (current_buffer), pos);
else if (BUFFERP (object))
i = find_interval (BUF_INTERVALS (XBUFFER (object)), pos);
else if (STRINGP (object))
i = find_interval (XSTRING (object)->intervals, pos);
else
abort ();
if (NULL_INTERVAL_P (i) || (i->position + LENGTH (i) <= pos))
return 0;
*val = textget (i->plist, prop);
if (NILP (*val))
return 0;
next = i;
prev = previous_interval (i);
while (! NULL_INTERVAL_P (prev)
&& EQ (*val, textget (prev->plist, prop)))
i = prev, prev = previous_interval (prev);
*start = i->position;
next = next_interval (i);
while (! NULL_INTERVAL_P (next)
&& EQ (*val, textget (next->plist, prop)))
i = next, next = next_interval (next);
*end = i->position + LENGTH (i);
return 1;
}
Lisp_Object
get_local_map (position, buffer, type)
register int position;
register struct buffer *buffer;
Lisp_Object type;
{
Lisp_Object prop, lispy_position, lispy_buffer;
int old_begv, old_zv, old_begv_byte, old_zv_byte;
if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
abort ();
old_begv = BUF_BEGV (buffer);
old_zv = BUF_ZV (buffer);
old_begv_byte = BUF_BEGV_BYTE (buffer);
old_zv_byte = BUF_ZV_BYTE (buffer);
BUF_BEGV (buffer) = BUF_BEG (buffer);
BUF_ZV (buffer) = BUF_Z (buffer);
BUF_BEGV_BYTE (buffer) = BUF_BEG_BYTE (buffer);
BUF_ZV_BYTE (buffer) = BUF_Z_BYTE (buffer);
if (position == BUF_Z (buffer) && BUF_Z (buffer) > BUF_BEG (buffer))
--position;
XSETFASTINT (lispy_position, position);
XSETBUFFER (lispy_buffer, buffer);
prop = Fget_char_property (lispy_position, type, lispy_buffer);
BUF_BEGV (buffer) = old_begv;
BUF_ZV (buffer) = old_zv;
BUF_BEGV_BYTE (buffer) = old_begv_byte;
BUF_ZV_BYTE (buffer) = old_zv_byte;
prop = get_keymap (prop, 0, 0);
if (CONSP (prop))
return prop;
if (EQ (type, Qkeymap))
return Qnil;
else
return buffer->keymap;
}
INTERVAL
copy_intervals (tree, start, length)
INTERVAL tree;
int start, length;
{
register INTERVAL i, new, t;
register int got, prevlen;
if (NULL_INTERVAL_P (tree) || length <= 0)
return NULL_INTERVAL;
i = find_interval (tree, start);
if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
abort ();
if ((start - i->position + 1 + length) < LENGTH (i)
&& DEFAULT_INTERVAL_P (i))
return NULL_INTERVAL;
new = make_interval ();
new->position = 0;
got = (LENGTH (i) - (start - i->position));
new->total_length = length;
copy_properties (i, new);
t = new;
prevlen = got;
while (got < length)
{
i = next_interval (i);
t = split_interval_right (t, prevlen);
copy_properties (i, t);
prevlen = LENGTH (i);
got += prevlen;
}
return balance_an_interval (new);
}
INLINE void
copy_intervals_to_string (string, buffer, position, length)
Lisp_Object string;
struct buffer *buffer;
int position, length;
{
INTERVAL interval_copy = copy_intervals (BUF_INTERVALS (buffer),
position, length);
if (NULL_INTERVAL_P (interval_copy))
return;
SET_INTERVAL_OBJECT (interval_copy, string);
XSTRING (string)->intervals = interval_copy;
}
int
compare_string_intervals (s1, s2)
Lisp_Object s1, s2;
{
INTERVAL i1, i2;
int pos = 0;
int end = XSTRING (s1)->size;
i1 = find_interval (XSTRING (s1)->intervals, 0);
i2 = find_interval (XSTRING (s2)->intervals, 0);
while (pos < end)
{
int len1 = (i1 != 0 ? INTERVAL_LAST_POS (i1) : end) - pos;
int len2 = (i2 != 0 ? INTERVAL_LAST_POS (i2) : end) - pos;
int distance = min (len1, len2);
if (! intervals_equal (i1, i2))
return 0;
pos += distance;
if (len1 == distance)
i1 = next_interval (i1);
if (len2 == distance)
i2 = next_interval (i2);
}
return 1;
}
static void
set_intervals_multibyte_1 (i, multi_flag, start, start_byte, end, end_byte)
INTERVAL i;
int multi_flag;
int start, start_byte, end, end_byte;
{
if (multi_flag)
i->total_length = end - start;
else
i->total_length = end_byte - start_byte;
if (i->left)
{
int left_end, left_end_byte;
if (multi_flag)
{
left_end_byte = start_byte + LEFT_TOTAL_LENGTH (i);
left_end = BYTE_TO_CHAR (left_end_byte);
}
else
{
left_end = start + LEFT_TOTAL_LENGTH (i);
left_end_byte = CHAR_TO_BYTE (left_end);
}
set_intervals_multibyte_1 (i->left, multi_flag, start, start_byte,
left_end, left_end_byte);
}
if (i->right)
{
int right_start_byte, right_start;
if (multi_flag)
{
right_start_byte = end_byte - RIGHT_TOTAL_LENGTH (i);
right_start = BYTE_TO_CHAR (right_start_byte);
}
else
{
right_start = end - RIGHT_TOTAL_LENGTH (i);
right_start_byte = CHAR_TO_BYTE (right_start);
}
set_intervals_multibyte_1 (i->right, multi_flag,
right_start, right_start_byte,
end, end_byte);
}
}
void
set_intervals_multibyte (multi_flag)
int multi_flag;
{
if (BUF_INTERVALS (current_buffer))
set_intervals_multibyte_1 (BUF_INTERVALS (current_buffer), multi_flag,
BEG, BEG_BYTE, Z, Z_BYTE);
}