How is text properties stored?

How is text properties stored?

[Yuan Fu]

[-- 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 --]

Re: How is text properties stored?

[Stefan Monnier]

> 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

Re: How is text properties stored?

[Yuan Fu]

[-- 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 --]

Re: How is text properties stored?

[Eli Zaretskii]

> 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.

Re: How is text properties stored?

[Yuan Fu]

[-- 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 --]

Re: How is text properties stored?

[Stefan Monnier]

>> 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

Re: How is text properties stored?

[Yuan Fu]

[-- 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 --]

Re: How is text properties stored?

[Eli Zaretskii]

> 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.