1: /* Definitions and global variables for intervals.
    2:    Copyright (C) 1993, 1994, 2000, 2001, 2002, 2003, 2004,
    3:                  2005, 2006, 2007  Free Software Foundation, Inc.
    4: 
    5: This file is part of GNU Emacs.
    6: 
    7: GNU Emacs is free software; you can redistribute it and/or modify
    8: it under the terms of the GNU General Public License as published by
    9: the Free Software Foundation; either version 2, or (at your option)
   10: any later version.
   11: 
   12: GNU Emacs is distributed in the hope that it will be useful,
   13: but WITHOUT ANY WARRANTY; without even the implied warranty of
   14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   15: GNU General Public License for more details.
   16: 
   17: You should have received a copy of the GNU General Public License
   18: along with GNU Emacs; see the file COPYING.  If not, write to
   19: the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
   20: Boston, MA 02110-1301, USA.  */
   21: 
   22: #include "dispextern.h"
   23: 
   24: #define NULL_INTERVAL ((INTERVAL)0)
   25: #define INTERVAL_DEFAULT NULL_INTERVAL
   26: 
   27: /* Basic data type for use of intervals.  */
   28: 
   29: struct interval
   30: {
   31:   /* The first group of entries deal with the tree structure.  */
   32: 
   33:   unsigned EMACS_INT total_length; /* Length of myself and both children.  */
   34:   unsigned EMACS_INT position;  /* Cache of interval's character position.  */
   35:                                 /* This field is usually updated
   36:                                    simultaneously with an interval
   37:                                    traversal, there is no guarantee
   38:                                    that it is valid for a random
   39:                                    interval.  */
   40:   struct interval *left;        /* Intervals which precede me.  */
   41:   struct interval *right;       /* Intervals which succeed me.  */
   42: 
   43:   /* Parent in the tree, or the Lisp_Object containing this interval tree.  */
   44:   union
   45:   {
   46:     struct interval *interval;
   47:     Lisp_Object obj;
   48:   } up;
   49:   unsigned int up_obj : 1;
   50: 
   51:   unsigned gcmarkbit : 1;
   52: 
   53:   /* The remaining components are `properties' of the interval.
   54:      The first four are duplicates for things which can be on the list,
   55:      for purposes of speed.  */
   56: 
   57:   unsigned int write_protect : 1;   /* Non-zero means can't modify.  */
   58:   unsigned int visible : 1;         /* Zero means don't display.  */
   59:   unsigned int front_sticky : 1;    /* Non-zero means text inserted just
   60:                                        before this interval goes into it.  */
   61:   unsigned int rear_sticky : 1;     /* Likewise for just after it.  */
   62: 
   63:   /* Properties of this interval.
   64:      The mark bit on this field says whether this particular interval
   65:      tree node has been visited.  Since intervals should never be
   66:      shared, GC aborts if it seems to have visited an interval twice.  */
   67:   Lisp_Object plist;
   68: };
   69: 
   70: /* These are macros for dealing with the interval tree. */
   71: 
   72: /* Size of the structure used to represent an interval */
   73: #define INTERVAL_SIZE (sizeof (struct interval))
   74: 
   75: /* Size of a pointer to an interval structure */
   76: #define INTERVAL_PTR_SIZE (sizeof (struct interval *))
   77: 
   78: /* True if an interval pointer is null, or is a Lisp_Buffer or
   79:    Lisp_String pointer (meaning it points to the owner of this
   80:    interval tree). */
   81: #ifdef NO_UNION_TYPE
   82: #define INT_LISPLIKE(i) (BUFFERP ((Lisp_Object)(i)) \
   83:                          || STRINGP ((Lisp_Object)(i)))
   84: #else
   85: #define INT_LISPLIKE(i) (BUFFERP ((Lisp_Object){(EMACS_INT)(i)}) \
   86:                          || STRINGP ((Lisp_Object){(EMACS_INT)(i)}))
   87: #endif
   88: 
   89: #ifdef ENABLE_CHECKING
   90: #define NULL_INTERVAL_P(i) \
   91:    (CHECK (!INT_LISPLIKE (i), "non-interval"), (i) == NULL_INTERVAL)
   92: /* old #define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL || INT_LISPLIKE (i)) */
   93: #else
   94: #define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL)
   95: #endif
   96: 
   97: /* True if this interval has no right child. */
   98: #define NULL_RIGHT_CHILD(i) ((i)->right == NULL_INTERVAL)
   99: 
  100: /* True if this interval has no left child. */
  101: #define NULL_LEFT_CHILD(i) ((i)->left == NULL_INTERVAL)
  102: 
  103: /* True if this interval has no parent. */
  104: #define NULL_PARENT(i) ((i)->up_obj || (i)->up.interval == 0)
  105: 
  106: /* True if this interval is the left child of some other interval. */
  107: #define AM_LEFT_CHILD(i) (! NULL_PARENT (i) \
  108:                           && INTERVAL_PARENT (i)->left == (i))
  109: 
  110: /* True if this interval is the right child of some other interval. */
  111: #define AM_RIGHT_CHILD(i) (! NULL_PARENT (i) \
  112:                            && INTERVAL_PARENT (i)->right == (i))
  113: 
  114: /* True if this interval has no children. */
  115: #define LEAF_INTERVAL_P(i) ((i)->left == NULL_INTERVAL \
  116:                             && (i)->right == NULL_INTERVAL)
  117: 
  118: /* True if this interval has no parent and is therefore the root. */
  119: #define ROOT_INTERVAL_P(i) (NULL_PARENT (i))
  120: 
  121: /* True if this interval is the only interval in the interval tree. */
  122: #define ONLY_INTERVAL_P(i) (ROOT_INTERVAL_P ((i)) && LEAF_INTERVAL_P ((i)))
  123: 
  124: /* True if this interval has both left and right children. */
  125: #define BOTH_KIDS_P(i) ((i)->left != NULL_INTERVAL     \
  126:                         && (i)->right != NULL_INTERVAL)
  127: 
  128: /* The total size of all text represented by this interval and all its
  129:    children in the tree.   This is zero if the interval is null. */
  130: #define TOTAL_LENGTH(i) ((i) == NULL_INTERVAL ? 0 : (i)->total_length)
  131: 
  132: /* The size of text represented by this interval alone. */
  133: #define LENGTH(i) ((i) == NULL_INTERVAL ? 0 : (TOTAL_LENGTH ((i))          \
  134:                                                - TOTAL_LENGTH ((i)->right) \
  135:                                                - TOTAL_LENGTH ((i)->left)))
  136: 
  137: /* The position of the character just past the end of I.  Note that
  138:    the position cache i->position must be valid for this to work. */
  139: #define INTERVAL_LAST_POS(i) ((i)->position + LENGTH ((i)))
  140: 
  141: /* The total size of the left subtree of this interval. */
  142: #define LEFT_TOTAL_LENGTH(i) ((i)->left ? (i)->left->total_length : 0)
  143: 
  144: /* The total size of the right subtree of this interval. */
  145: #define RIGHT_TOTAL_LENGTH(i) ((i)->right ? (i)->right->total_length : 0)
  146: 
  147: 
  148: /* These macros are for dealing with the interval properties. */
  149: 
  150: /* True if this is a default interval, which is the same as being null
  151:    or having no properties. */
  152: #define DEFAULT_INTERVAL_P(i) (NULL_INTERVAL_P (i) || EQ ((i)->plist, Qnil))
  153: 
  154: /* Test what type of parent we have.  Three possibilities: another
  155:    interval, a buffer or string object, or NULL_INTERVAL.  */
  156: #define INTERVAL_HAS_PARENT(i) ((i)->up_obj == 0 && (i)->up.interval != 0)
  157: #define INTERVAL_HAS_OBJECT(i) ((i)->up_obj)
  158: 
  159: /* Set/get parent of an interval.
  160: 
  161:    The choice of macros is dependent on the type needed.  Don't add
  162:    casts to get around this, it will break some development work in
  163:    progress.  */
  164: #define SET_INTERVAL_PARENT(i,p) \
  165:    (eassert (!INT_LISPLIKE (p)), (i)->up_obj = 0, (i)->up.interval = (p))
  166: #define SET_INTERVAL_OBJECT(i,o) \
  167:    (eassert (BUFFERP (o) || STRINGP (o)), (i)->up_obj = 1, (i)->up.obj = (o))
  168: #define INTERVAL_PARENT(i) \
  169:    (eassert ((i) != 0 && (i)->up_obj == 0),(i)->up.interval)
  170: #define GET_INTERVAL_OBJECT(d,s) (eassert((s)->up_obj == 1), (d) = (s)->up.obj)
  171: 
  172: /* Make the parent of D be whatever the parent of S is, regardless of
  173:    type.  This is used when balancing an interval tree.  */
  174: #define COPY_INTERVAL_PARENT(d,s) \
  175:    ((d)->up = (s)->up, (d)->up_obj = (s)->up_obj)
  176: 
  177: /* Get the parent interval, if any, otherwise a null pointer.  Useful
  178:    for walking up to the root in a "for" loop; use this to get the
  179:    "next" value, and test the result to see if it's NULL_INTERVAL.  */
  180: #define INTERVAL_PARENT_OR_NULL(i) \
  181:    (INTERVAL_HAS_PARENT (i) ? INTERVAL_PARENT (i) : 0)
  182: 
  183: /* Abort if interval I's size is negative.  */
  184: #define CHECK_TOTAL_LENGTH(i) \
  185:   if ((int) (i)->total_length < 0) abort (); else
  186: 
  187: /* Reset this interval to its vanilla, or no-property state. */
  188: #define RESET_INTERVAL(i) \
  189: { \
  190:     (i)->total_length = (i)->position = 0;    \
  191:     (i)->left = (i)->right = NULL_INTERVAL;   \
  192:     SET_INTERVAL_PARENT (i, NULL_INTERVAL);   \
  193:     (i)->write_protect = 0;                   \
  194:     (i)->visible = 0;                         \
  195:     (i)->front_sticky = (i)->rear_sticky = 0; \
  196:     (i)->plist = Qnil;                        \
  197: }
  198: 
  199: /* Copy the cached property values of interval FROM to interval TO. */
  200: #define COPY_INTERVAL_CACHE(from,to) \
  201: { \
  202:   (to)->write_protect = (from)->write_protect; \
  203:   (to)->visible = (from)->visible;             \
  204:   (to)->front_sticky = (from)->front_sticky;   \
  205:   (to)->rear_sticky = (from)->rear_sticky;     \
  206: }
  207: 
  208: /* Copy only the set bits of FROM's cache. */
  209: #define MERGE_INTERVAL_CACHE(from,to) \
  210: { \
  211:   if ((from)->write_protect) (to)->write_protect = 1; \
  212:   if ((from)->visible) (to)->visible = 1;             \
  213:   if ((from)->front_sticky) (to)->front_sticky = 1;   \
  214:   if ((from)->rear_sticky) (to)->rear_sticky = 1;     \
  215: }
  216: 
  217: /* Macro determining whether the properties of an interval being
  218:    inserted should be merged with the properties of the text where
  219:    they are being inserted. */
  220: #define MERGE_INSERTIONS(i) 1
  221: 
  222: /* Macro determining if an invisible interval should be displayed
  223:    as a special glyph, or not at all. */
  224: #define DISPLAY_INVISIBLE_GLYPH(i) 0
  225: 
  226: /* Is this interval visible?  Replace later with cache access */
  227: #define INTERVAL_VISIBLE_P(i) \
  228:   (! NULL_INTERVAL_P (i) && NILP (textget ((i)->plist, Qinvisible)))
  229: 
  230: /* Is this interval writable?  Replace later with cache access */
  231: #define INTERVAL_WRITABLE_P(i)                                  \
  232:   (! NULL_INTERVAL_P (i)                                        \
  233:    && (NILP (textget ((i)->plist, Qread_only))                  \
  234:        || ((CONSP (Vinhibit_read_only)                          \
  235:             ? !NILP (Fmemq (textget ((i)->plist, Qread_only),  \
  236:                             Vinhibit_read_only))             \
  237:             : !NILP (Vinhibit_read_only)))))                   \
  238: 
  239: /* Macros to tell whether insertions before or after this interval
  240:    should stick to it. */
  241: /* Replace later with cache access */
  242: /*#define FRONT_STICKY_P(i) ((i)->front_sticky != 0)
  243:   #define END_STICKY_P(i) ((i)->rear_sticky != 0)*/
  244: /* As we now have Vtext_property_default_nonsticky, these macros are
  245:    unreliable now.  Currently, they are never used.  */
  246: #define FRONT_STICKY_P(i) \
  247:   (! NULL_INTERVAL_P (i) && ! NILP (textget ((i)->plist, Qfront_sticky)))
  248: #define END_NONSTICKY_P(i) \
  249:   (! NULL_INTERVAL_P (i) && ! NILP (textget ((i)->plist, Qrear_nonsticky)))
  250: #define FRONT_NONSTICKY_P(i) \
  251:   (! NULL_INTERVAL_P (i) && ! EQ (Qt, textget ((i)->plist, Qfront_sticky)))
  252: 
  253: 
  254: /* If PROP is the `invisible' property of a character,
  255:    this is 1 if the character should be treated as invisible,
  256:    and 2 if it is invisible but with an ellipsis.  */
  257: 
  258: #define TEXT_PROP_MEANS_INVISIBLE(prop)                         \
  259:   (EQ (current_buffer->invisibility_spec, Qt)                   \
  260:    ? !NILP (prop)                                               \
  261:    : invisible_p (prop, current_buffer->invisibility_spec))
  262: 
  263: /* Declared in alloc.c */
  264: 
  265: extern INTERVAL make_interval P_ ((void));
  266: 
  267: /* Declared in intervals.c */
  268: 
  269: extern INTERVAL create_root_interval P_ ((Lisp_Object));
  270: extern void copy_properties P_ ((INTERVAL, INTERVAL));
  271: extern int intervals_equal P_ ((INTERVAL, INTERVAL));
  272: extern void traverse_intervals P_ ((INTERVAL, int,
  273:                                     void (*) (INTERVAL, Lisp_Object),
  274:                                     Lisp_Object));
  275: extern void traverse_intervals_noorder P_ ((INTERVAL,
  276:                                     void (*) (INTERVAL, Lisp_Object),
  277:                                     Lisp_Object));
  278: extern INTERVAL split_interval_right P_ ((INTERVAL, int));
  279: extern INTERVAL split_interval_left P_ ((INTERVAL, int));
  280: extern INTERVAL find_interval P_ ((INTERVAL, int));
  281: extern INTERVAL next_interval P_ ((INTERVAL));
  282: extern INTERVAL previous_interval P_ ((INTERVAL));
  283: extern INTERVAL merge_interval_left P_ ((INTERVAL));
  284: extern INTERVAL merge_interval_right P_ ((INTERVAL));
  285: extern void delete_interval P_ ((INTERVAL));
  286: extern INLINE void offset_intervals P_ ((struct buffer *, int, int));
  287: extern void graft_intervals_into_buffer P_ ((INTERVAL, int, int,
  288:                                              struct buffer *, int));
  289: extern void set_point P_ ((struct buffer *, int));
  290: extern INLINE void temp_set_point P_ ((struct buffer *, int));
  291: extern void set_point_both P_ ((struct buffer *, int, int));
  292: extern INLINE void temp_set_point_both P_ ((struct buffer *, int, int));
  293: extern void verify_interval_modification P_ ((struct buffer *, int, int));
  294: extern INTERVAL balance_intervals P_ ((INTERVAL));
  295: extern INLINE void copy_intervals_to_string P_ ((Lisp_Object, struct buffer *,
  296:                                                  int, int));
  297: extern INTERVAL copy_intervals P_ ((INTERVAL, int, int));
  298: extern int compare_string_intervals P_ ((Lisp_Object, Lisp_Object));
  299: extern Lisp_Object textget P_ ((Lisp_Object, Lisp_Object));
  300: extern Lisp_Object lookup_char_property P_ ((Lisp_Object, Lisp_Object, int));
  301: extern void move_if_not_intangible P_ ((int));
  302: extern int get_property_and_range P_ ((int, Lisp_Object, Lisp_Object *,
  303:                                        int *, int *, Lisp_Object));
  304: extern Lisp_Object get_local_map P_ ((int, struct buffer *, Lisp_Object));
  305: extern INTERVAL update_interval P_ ((INTERVAL, int));
  306: extern void set_intervals_multibyte P_ ((int));
  307: extern INTERVAL validate_interval_range P_ ((Lisp_Object, Lisp_Object *,
  308:                                              Lisp_Object *, int));
  309: 
  310: /* Defined in xdisp.c */
  311: extern int invisible_p P_ ((Lisp_Object, Lisp_Object));
  312: 
  313: /* Declared in textprop.c */
  314: 
  315: /* Types of hooks. */
  316: extern Lisp_Object Qmouse_left;
  317: extern Lisp_Object Qmouse_entered;
  318: extern Lisp_Object Qpoint_left;
  319: extern Lisp_Object Qpoint_entered;
  320: extern Lisp_Object Qmodification_hooks;
  321: extern Lisp_Object Qcategory;
  322: extern Lisp_Object Qlocal_map;
  323: extern Lisp_Object Qkeymap;
  324: 
  325: /* Visual properties text (including strings) may have. */
  326: extern Lisp_Object Qforeground, Qbackground, Qfont, Qunderline, Qstipple;
  327: extern Lisp_Object Qinvisible, Qintangible, Qread_only;
  328: 
  329: extern Lisp_Object Vinhibit_point_motion_hooks;
  330: extern Lisp_Object Vdefault_text_properties;
  331: extern Lisp_Object Vchar_property_alias_alist;
  332: extern Lisp_Object Vtext_property_default_nonsticky;
  333: 
  334: /* Sticky properties */
  335: extern Lisp_Object Qfront_sticky, Qrear_nonsticky;
  336: 
  337: EXFUN (Fget_char_property, 3);
  338: EXFUN (Fget_char_property_and_overlay, 3);
  339: EXFUN (Fget_text_property, 3);
  340: EXFUN (Ftext_properties_at, 2);
  341: EXFUN (Fnext_property_change, 3);
  342: EXFUN (Fprevious_property_change, 3);
  343: EXFUN (Fadd_text_properties, 4);
  344: EXFUN (Fset_text_properties, 4);
  345: EXFUN (Fremove_text_properties, 4);
  346: EXFUN (Ftext_property_any, 5);
  347: EXFUN (Ftext_property_not_all, 5);
  348: EXFUN (Fprevious_single_char_property_change, 4);
  349: extern Lisp_Object copy_text_properties P_ ((Lisp_Object, Lisp_Object,
  350:                                              Lisp_Object, Lisp_Object,
  351:                                              Lisp_Object, Lisp_Object));
  352: extern Lisp_Object set_text_properties P_ ((Lisp_Object, Lisp_Object,
  353:                                             Lisp_Object, Lisp_Object,
  354:                                             Lisp_Object));
  355: extern void set_text_properties_1 P_ ((Lisp_Object, Lisp_Object,
  356:                                        Lisp_Object, Lisp_Object, INTERVAL));
  357: 
  358: Lisp_Object text_property_list P_ ((Lisp_Object, Lisp_Object, Lisp_Object,
  359:                                     Lisp_Object));
  360: int add_text_properties_from_list P_ ((Lisp_Object, Lisp_Object, Lisp_Object));
  361: void extend_property_ranges P_ ((Lisp_Object, Lisp_Object, Lisp_Object));
  362: Lisp_Object get_char_property_and_overlay P_ ((Lisp_Object, Lisp_Object,
  363:                                                Lisp_Object, Lisp_Object*));
  364: extern int text_property_stickiness P_ ((Lisp_Object prop, Lisp_Object pos,
  365:                                          Lisp_Object buffer));
  366: extern Lisp_Object get_pos_property P_ ((Lisp_Object pos, Lisp_Object prop,
  367:                                          Lisp_Object object));
  368: 
  369: extern void syms_of_textprop P_ ((void));
  370: 
  371: #include "composite.h"
  372: 
  373: /* arch-tag: f0bc16c0-b084-498d-9de4-21cc8f077795
  374:    (do not change this comment) */