The buffer protocol =================== General ------- buffer [protocol class] The base class for all buffers. A buffer conceptually contains a large array of arbitrary objects. Lines of objects are separated by newline characters. The last object of the buffer is not necessarily a newline character. standard-buffer [class] The standard instantiable class for buffers. A subclass of buffer. mark [protocol class] The base class for all marks. :buffer [initarg] :offset [initarg] The :buffer initarg is mandatory because no mark can exist without a buffer. When the :offset initarg is not given, it defaults to zero. If an :offset initarg is given that is less than zero or greater than the size of the buffer, a no-such-offset condition is signaled. left-sticky-mark [protocol class] A subclass of mark. A mark of this type will "stick" to the object to the left of it, i.e. when an object is inserted at this mark, the mark will be positioned to the left of the object. right-sticky-mark [protocol class] A subclass of mark. A mark of this type will "stick" to the object to the right of it, i.e. when an object is inserted at this mark, the mark will be positioned to the right of the object. clone-mark (mark &key type) [generic function] Clone a mark. By default (when type is NIL) the same type of mark is returned. Otherwise type is the name of a class (subclass of the mark class) to be used as a class of the clone. buffer mark [generic function] Return the buffer that the mark is positioned in. no-such-offset [error condition] This condition is signaled whenever an attempt is made at an operation that is before the beginning or after the end of the buffer. size buffer [generic function] Return the number of objects in the buffer. number-of-lines buffer [generic function] Return the number of lines of the buffer, or really the number of newline characters. Operations related to the offset of marks ----------------------------------------- offset mark [generic function] Return the offset of the mark into the buffer. (setf offset) offset mark Set the offset of the mark into the buffer. A no-such-offset condition is signaled if the offset is less than zero or greater than the size of the buffer. mark< mark1 mark2 [generic function] Return t if the offset of mark1 is strictly less than that of mark2. An error is signaled if the two marks are not positioned in the same buffer. It is acceptable to pass an offset in place of one of the marks. mark<= mark1 mark2 [generic function] Return t if the offset of mark1 is less than or equal to that of mark2. An error is signaled if the two marks are not positioned in the same buffer. It is acceptable to pass an offset in place of one of the marks. mark> mark1 mark2 [generic function] Return t if the offset of mark1 is strictly greater than that of mark2. An error is signaled if the two marks are not positioned in the same buffer. It is acceptable to pass an offset in place of one of the marks. mark>= mark1 mark2 [generic function] Return t if the offset of mark1 is greater than or equal to that of mark2. An error is signaled if the two marks are not positioned in the same buffer. It is acceptable to pass an offset in place of one of the marks. mark= mark1 mark2 [generic function] Return t if the offset of mark1 is equal to that of mark2. An error is signaled if the two marks are not positioned in the same buffer. It is acceptable to pass an offset in place of one of the marks. beginning-of-buffer mark [generic function] Move the mark to the beginning of the buffer. This is equivalent to (setf (offset mark) 0) end-of-buffer mark [generic function] Move the mark to the end of the buffer. beginning-of-buffer-p mark [generic function] Return t if the mark is at the beginning of the buffer, nil otherwise. end-of-buffer-p mark [generic function] Return t if the mark is at the end of the buffer, nil otherwise. beginning-of-line mark [generic function] Move the mark to the beginning of the line. The mark will be positioned either immediately after the closest preceding newline character, or at the beginning of the buffer if no preceding newline character exists. end-of-line mark [generic function] Move the mark to the end of the line. The mark will be positioned either immediately before the closest following newline character, or at the end of the buffer if no following newline character exists. beginning-of-line-p mark [generic function] Return t if the mark is at the beginning of the line (i.e., if the character preceding the mark is a newline character or if the mark is at the beginning of the buffer), nil otherwise. end-of-line-p mark [generic function] Return t if the mark is at the end of the line (i.e., if the character following the mark is a newline character, or if the mark is at the end of the buffer), nil otherwise. line-number mark [generic function] Return the line number of the mark. Lines are numbered from zero. column-number mark [generic function] Return the column number of the mark. The column number of a mark is the number of objects between it and the preceding newline, or between it and the beginning of the buffer if the mark is on the first line of the buffer. Inserting and deleting objects ------------------------------ insert-buffer-object buffer offset object [generic function] Insert the object at the offset in the buffer. Any left-sticky marks that are placed at the offset will remain positioned before the inserted object. Any right-sticky marks that are placed at the offset will be positioned after the inserted object. insert-buffer-sequence buffer offset sequence [generic function] Like calling insert-buffer-object on each of the objects in the sequence. insert-object mark object [generic function] Insert the object at the mark. This function simply calls insert-buffer-object with the buffer and the position of the mark. insert-sequence mark sequence [generic function] Insert the objects in the sequence at the mark. This function simply calls insert-buffer-sequence with the buffer and the position of the mark. delete-buffer-range buffer offset n [generic function] Delete n objects from the buffer starting at the offset. If offset is negative or offset+n is greater than the size of the buffer, a no-such-offset condition is signaled. delete-range mark &optional (n 1) [generic function] Delete n objects after (if n > 0) or before (if n < 0) the mark. This function eventually calls delete-buffer-range, provided that n is not zero. delete-region mark1 mark2 [generic function] Delete the objects in the buffer that are after mark1 and before mark2. An error is signaled if the two marks are positioned in different buffers. If mark1 is positioned at an offset equal to or greater than that of mark2, no objects are deleted. If objects are to be deleted, this function calls delete-buffer-range with the appropriate arguments. It is acceptable to pass an offset in place of one of the marks. Getting objects out of the buffer --------------------------------- buffer-object buffer offset [generic function] Return the object at the offset in the buffer. The first object has offset 0. If offset is less than zero or greater than or equal to the size of the buffer, a no-such-offset condition is signaled. buffer-sequence buffer offset1 offset2 [generic function] Return the contents of the buffer starting at offset1 and ending at offset2-1 as a sequence. If either of the offsets is less than zero or greater than or equal to the size of the buffer, a no-such-offset condition is signaled. If offset2 is smaller than or equal to offset1, an empty sequence will be returned. objecct-before mark [generic function] Return the object that is immediately before the mark. If mark is at the beginning of the buffer, a no-such-offset condition is signaled. If the mark is at the beginning of a line, but not at the beginning of the buffer, a newline character is returned. objecct-after mark [generic function] Return the object that is immediately after the mark. If mark is at the end of the buffer, a no-such-offset condition is signaled. If the mark is at the end of a line, but not at the end of the buffer, a newline character is returned. region-to-sequence mark1 mark2 [generic function] Return a freshly allocated sequence of the objects after mark1 and before mark2. An error is signaled if the two marks are positioned in different buffers. If mark1 is positioned at an offset equal to or greater than that of mark2, an empty sequence is returned. It is acceptable to pass an offset in place of one of the marks. Implementation of the buffer protocol ===================================== The buffer is implemented as lines organized in a 2-3-tree. The leaves of the tree contain the lines, and the internal nodes contain additional information of the left subtree (if it is a 2-node) or the left and the middle subtree (if it is a 3-node). Two pieces of information are stored: The number of lines in up to and including the subtree and the total number of objects up to an including the subtree. This organization allows us to determine, the line number and object position of any mark in O(log N) where N is the number of lines. A line is an instance of the `buffer-line' class. A line can either be open or closed. A closed line is represented as a sequence. The exact type of the sequence depends on the objects contained in the line. If the line contains only characters of type base-char, then the sequence is of type base-string. If the line contains only characters, but not of type base-char, the sequence is a string. Otherwise it is a vector of arbitrary objects. This way, closed lines containing characters with code points below 256 have a compact representation with 8 bits per character while still allowing for arbitrary objects when necessary. An open line is represented as a cursorchain of objects. Marks in a closed line are represented as an integer offset into the sequence. Marks in an open line are represented as flexicursors. When a line is opened, it is converted to a cursorchain. When a line is closed, it is examined to determine whether it contains non-character objects, in which case it is converted to a vector of objects. If contains only characters, but it contains characters with code points above what can be represented in a base-char, it is converted to a string. If it contains only base-chars, it is converted to a base-string. A mark contains two slots: a flexicursor that determines which line it is on, and either an integer (if the line is closed) that determines the offset within the line or another flexicursor (if the line is open). For each line, open or closed, a list of weak references to marks into that line is kept. Lines are closed according to a LRU scheme. Whenever objects are inserted to or deleted from a line, it becomes the most recently used line. We keep a fixed number of open lines so that when a line is opened and the threshold is reached, the least recently used line is closed. The buffer modification protocol ================================ The buffer maintains two marks, the low mark and the high mark: low-mark buffer [generic function] Return the low mark of the buffer. high-mark buffer [generic function] Return the high mark of the buffer. The low mark is a left-sticky mark and high mark is a right-sticky mark. Whenever a modification is made to the buffer, the offset of the low mark is set to the minimum of its current value and the position of the modification. Similarly, whenever a modification is made to the buffer, the offset of the high mark is set to the maximum of its current value and the position of the modification. Redisplay code may use these values to determine what part of the screen needs to be updated. At the end of an invocation of redisplay, the offset of the low mark is set to the size of the buffer, and the offset of the high mark is set to zero. These values can also be used to update information about syntax highlighting and other cached information. The redisplay protocol ====================== A buffer can be on display in several windows. The redisplay algorithm is invoked on each such window. During redisplay, the values of low-mark and high-mark are examined to determine how to display the buffer in each window. When all windows have been redisplayed, the low-mark is set to the end of the buffer and the high-mark is set to the beginning of the buffer. Each window is associated with a distinguished mark called the `point' of the window. The point is a right-sticky mark independently of whether you are typing left-to-right or right-to-left. redisplay-window window [generic function] Determine which region of the buffer should be displayed in the window, and then call display-lines with the window, and two marks defining that region. This function does not attempt to minimize the text to be redrawn, because even though some parts of the buffer are unchanged, those objects might be displayed differently (highlighted, for instance) as a result of modified objects with higher offsets in the buffer. It used to be the case that the purpose of the redisplay protocol was to minimize cursor movement and text drawing because of slow serial connections. Nowadays, that is not such a big problem. The purpose of this protocol is to minimize unnecessary scrolling so as to avoid confusing the user as to where the point is located. Specifically, we do not want the window to scroll unless point would otherwise be outside the window. For each window, the redisplay protocol maintains two marks: a left-sticky mark called `window-top' that is positioned at the beginning of the first line on display and a right-sticky mark called `window-bottom' that is positioned at the end of the last line on display. When invoked on a window, redisplay first determines whether the height of the window corresponds to the number of lines between window-top and window-bottom. If not, window-bottom is adjusted accordingly. Next, redisplay determines whether the point is located between window-top and window-bottom. If that is not the case, new values of window-top and window bottom are found that puts point in the middle of the window. Finally, redisplay calls display-lines with the window, window-top, and window-bottom as arguments, and then draws a cursor at the location of point. The syntax protocol =================== Every buffer contains a parser that maintains an `optimistic parse tree' containing information of the contents of the buffer from the beginning and up to some point P in the buffer that depends on a variety of circumstances, such as the last buffer offset at which a modification was made, the highest offset of any window on display, etc. The parse tree is optimistic in the sense that there exists some possible buffer contents from the point P to the end of the buffer that will generate the (non optimistic version of the) parse tree. The syntax module maintains the highest buffer offset that has been analyzed. invalidate-parse buffer offset [generic function] Inform the parser that the buffer has been altered starting at the offset indicated. advance-parse buffer offset [generic function] Inform the parser that it should construct a valid parse tree up to the offset indicated. The redisplay module will call this function with the highest offset of all the windows on display before calling display-region for each window. display-region window mark1 mark2 Display the region between mark1 and mark2 in the window. It is an error to call this function with a mark2 having an offset that is smaller than the previous call to advance-parse. An error is signaled if the two marks are not positioned in the same buffer. It is acceptable to pass an offset in place of one of the marks. For each syntactic role encountered in the region, display-region calls display-chunk. display-chunk window role offset1 offset2 [generic function] This function is called by display-region, and client code must supply methods for this function for the different syntactic roles that it would like to distinguish. These roles are the leaves of the syntax tree (what is traditionally called `tokens' in parsing theory, not to be confused with what Common Lisp calls `tokens'). Examples of syntactic roles would be numbers, symbols, parentheses, comments, words, etc.