* How is text properties stored?
@ 2019-05-08 21:08 Yuan Fu
2019-05-09 0:58 ` Stefan Monnier
0 siblings, 1 reply; 8+ messages in thread
From: Yuan Fu @ 2019-05-08 21:08 UTC (permalink / raw
To: emacs-devel
[-- Attachment #1: Type: text/plain, Size: 834 bytes --]
Hi,
I’m interested in how is text properties stored in a string/buffer. From what I see (printing propertzied string and try reading textprop.c), it seems that they are stored in ranges. Is that true?
If that’s the case, I have two more questions:
1. How is it implemented? I.e., is it like (very roughly):
struct string {
char* string;
property* properties;
};
struct property {
int beg;
int end;
Lisp_Object* plist;
}
?
2. In my naive minds, if the text properties are implemented like this, every time when the user insert something in to a buffer/string, all the properties after the point of insert has to adjust their position (like overlays). That’s probably not the case since text property is supposed to be more efficient than overlays. So how does it work?
Sincerely, Yuan
[-- Attachment #2: Type: text/html, Size: 2053 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: How is text properties stored?
2019-05-08 21:08 How is text properties stored? Yuan Fu
@ 2019-05-09 0:58 ` Stefan Monnier
2019-05-09 1:41 ` Yuan Fu
0 siblings, 1 reply; 8+ messages in thread
From: Stefan Monnier @ 2019-05-09 0:58 UTC (permalink / raw
To: emacs-devel
> overlays). That’s probably not the case since text property is supposed to
> be more efficient than overlays. So how does it work?
It's all in src/intervals.[ch].
It starts with:
struct interval
{
/* The first group of entries deal with the tree structure. */
ptrdiff_t total_length; /* Length of myself and both children. */
ptrdiff_t position; /* Cache of interval's character position. */
/* This field is valid in the final
target interval returned by
find_interval, next_interval,
previous_interval and
update_interval. It cannot be
depended upon in any intermediate
intervals traversed by these
functions, or any other
interval. */
struct interval *left; /* Intervals which precede me. */
struct interval *right; /* Intervals which succeed me. */
/* Parent in the tree, or the Lisp_Object containing this interval tree. */
union
{
struct interval *interval;
Lisp_Object obj;
} up;
bool_bf up_obj : 1;
bool_bf gcmarkbit : 1;
/* The remaining components are `properties' of the interval.
The first four are duplicates for things which can be on the list,
for purposes of speed. */
bool_bf write_protect : 1; /* True means can't modify. */
bool_bf visible : 1; /* False means don't display. */
bool_bf front_sticky : 1; /* True means text inserted just
before this interval goes into it. */
bool_bf rear_sticky : 1; /* Likewise for just after it. */
Lisp_Object plist; /* Other properties. */
};
As you can see from the left/right fields, it's a binary tree.
And we try to keep it balanced (tho IIRC it's not quite always
balanced).
Stefan
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: How is text properties stored?
2019-05-09 0:58 ` Stefan Monnier
@ 2019-05-09 1:41 ` Yuan Fu
2019-05-09 5:41 ` Eli Zaretskii
0 siblings, 1 reply; 8+ messages in thread
From: Yuan Fu @ 2019-05-09 1:41 UTC (permalink / raw
To: Stefan Monnier; +Cc: emacs-devel
[-- Attachment #1: Type: text/plain, Size: 259 bytes --]
IIUC, position of a particular interval is calculated whenever needed;
looking for the property in a particular position is done via binary search;
and when a user inserts text, only the interval under point is affected,
is that correct?
Sincerely, Yuan
[-- Attachment #2: Type: text/html, Size: 1047 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: How is text properties stored?
2019-05-09 1:41 ` Yuan Fu
@ 2019-05-09 5:41 ` Eli Zaretskii
2019-05-09 20:26 ` Yuan Fu
0 siblings, 1 reply; 8+ messages in thread
From: Eli Zaretskii @ 2019-05-09 5:41 UTC (permalink / raw
To: Yuan Fu; +Cc: monnier, emacs-devel
> From: Yuan Fu <casouri@gmail.com>
> Date: Wed, 8 May 2019 21:41:45 -0400
> Cc: emacs-devel@gnu.org
>
> IIUC, position of a particular interval is calculated whenever needed;
No, positions of intervals are continuously maintained as side effect
of editing commands that change buffer text.
> looking for the property in a particular position is done via binary search;
Yes. See find_interval.
> and when a user inserts text, only the interval under point is affected,
> is that correct?
Not exactly, insertion also affects all the ancestors of the interval
at point. See adjust_intervals_for_insertion.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: How is text properties stored?
2019-05-09 5:41 ` Eli Zaretskii
@ 2019-05-09 20:26 ` Yuan Fu
2019-05-09 20:40 ` Stefan Monnier
0 siblings, 1 reply; 8+ messages in thread
From: Yuan Fu @ 2019-05-09 20:26 UTC (permalink / raw
To: emacs-devel
[-- Attachment #1: Type: text/plain, Size: 577 bytes --]
> No, positions of intervals are continuously maintained as side effect
> of editing commands that change buffer text.
I still don't understand how is position maintained when user inserts
something. Say I insert some characters in interval (3), I know
total_length of (2) and (4) are updated. But how are the positions of
all the intervals after (3) -- (4), (5) and (6) updated? I don't see
relevant code in adjust_intervals_for_insertion.
----- (4) ---
/ | \
- (2) - | - (6)
/ | \ | / |
(1) (2) (3) (4) (5) (6)
Sincerely, Yuan
[-- Attachment #2: Type: text/html, Size: 2240 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: How is text properties stored?
2019-05-09 20:26 ` Yuan Fu
@ 2019-05-09 20:40 ` Stefan Monnier
2019-05-10 1:50 ` Yuan Fu
0 siblings, 1 reply; 8+ messages in thread
From: Stefan Monnier @ 2019-05-09 20:40 UTC (permalink / raw
To: emacs-devel
>> No, positions of intervals are continuously maintained as side effect
>> of editing commands that change buffer text.
>
>
> I still don't understand how is position maintained when user inserts
> something. Say I insert some characters in interval (3), I know
> total_length of (2) and (4) are updated. But how are the positions of
> all the intervals after (3) -- (4), (5) and (6) updated? I don't see
> relevant code in adjust_intervals_for_insertion.
They're not updated at that moment. They'll be updated when you "move"
to those other intervals: find_interval and next_interval presume that
the current interval has correct `position` info and (re)compute the
destination's `position` based on that info (and on the total_length of
the relevant intervals along the way).
Stefan
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: How is text properties stored?
2019-05-09 20:40 ` Stefan Monnier
@ 2019-05-10 1:50 ` Yuan Fu
2019-05-10 5:43 ` Eli Zaretskii
0 siblings, 1 reply; 8+ messages in thread
From: Yuan Fu @ 2019-05-10 1:50 UTC (permalink / raw
To: emacs-devel
[-- Attachment #1: Type: text/plain, Size: 318 bytes --]
> They're not updated at that moment. They'll be updated when you "move"
> to those other intervals: find_interval and next_interval presume that
I guess “move” means more than moving the point? What happens if we need to copy or display some text with outdated intervals on that range?
Sincerely, Yuan
[-- Attachment #2: Type: text/html, Size: 1119 bytes --]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: How is text properties stored?
2019-05-10 1:50 ` Yuan Fu
@ 2019-05-10 5:43 ` Eli Zaretskii
0 siblings, 0 replies; 8+ messages in thread
From: Eli Zaretskii @ 2019-05-10 5:43 UTC (permalink / raw
To: Yuan Fu; +Cc: emacs-devel
> From: Yuan Fu <casouri@gmail.com>
> Date: Thu, 9 May 2019 21:50:29 -0400
>
> They're not updated at that moment. They'll be updated when you "move"
> to those other intervals: find_interval and next_interval presume that
>
> I guess “move” means more than moving the point? What happens if we need to copy or display some text
> with outdated intervals on that range?
All of those operations call primitives that report text properties at
a given position, and those primitives call find_interval internally.
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2019-05-10 5:43 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2019-05-08 21:08 How is text properties stored? Yuan Fu
2019-05-09 0:58 ` Stefan Monnier
2019-05-09 1:41 ` Yuan Fu
2019-05-09 5:41 ` Eli Zaretskii
2019-05-09 20:26 ` Yuan Fu
2019-05-09 20:40 ` Stefan Monnier
2019-05-10 1:50 ` Yuan Fu
2019-05-10 5:43 ` Eli Zaretskii
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.