1	/*
2	* Gtktextbtree.c --
3	*
4	* This file contains code that manages the B-tree representation
5	* of text for the text buffer and implements character and
6	* toggle segment types.
7	*
8	* Copyright (c) 1992-1994 The Regents of the University of California.
9	* Copyright (c) 1994-1995 Sun Microsystems, Inc.
10	* Copyright (c) 2000 Red Hat, Inc.
11	* Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
12	*
13	* This software is copyrighted by the Regents of the University of
14	* California, Sun Microsystems, Inc., and other parties. The
15	* following terms apply to all files associated with the software
16	* unless explicitly disclaimed in individual files.
17	*
18	* The authors hereby grant permission to use, copy, modify,
19	* distribute, and license this software and its documentation for any
20	* purpose, provided that existing copyright notices are retained in
21	* all copies and that this notice is included verbatim in any
22	* distributions. No written agreement, license, or royalty fee is
23	* required for any of the authorized uses. Modifications to this
24	* software may be copyrighted by their authors and need not follow
25	* the licensing terms described here, provided that the new terms are
26	* clearly indicated on the first page of each file where they apply.
27	*
28	* IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
29	* PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
30	* DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
31	* OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
32	* OF THE POSSIBILITY OF SUCH DAMAGE.
33	*
34	* THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
35	* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
36	* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
37	* NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
38	* AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
39	* MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
40	*
41	* GOVERNMENT USE: If you are acquiring this software on behalf of the
42	* U.S. government, the Government shall have only "Restricted Rights"
43	* in the software and related documentation as defined in the Federal
44	* Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you
45	* are acquiring the software on behalf of the Department of Defense,
46	* the software shall be classified as "Commercial Computer Software"
47	* and the Government shall have only "Restricted Rights" as defined
48	* in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the
49	* foregoing, the authors grant the U.S. Government and others acting
50	* in its behalf permission to use and distribute the software in
51	* accordance with the terms specified in this license.
52	*
53	*/
54
55	#include "config.h"
56	#include "gtktextbtree.h"
57	#include <string.h>
58	#include <stdlib.h>
59	#include <stdio.h>
60	#include "gtktextbufferprivate.h"
61	#include "gtktexttag.h"
62	#include "gtktexttagprivate.h"
63	#include "gtktexttagtableprivate.h"
64	#include "gtktextlayoutprivate.h"
65	#include "gtktextiterprivate.h"
66	#include "gtkdebug.h"
67	#include "gtktextmarkprivate.h"
68	#include "gtktextsegment.h"
69	#include "gtkpango.h"
70	#include "gdk-private.h"
71
72	/*
73	* Types
74	*/
75
76
77	/*
78	* The structure below is used to pass information between
79	* _gtk_text_btree_get_tags and inc_count:
80	*/
81
82	typedef struct TagInfo {
83	GPtrArray *tags;
84	GArray *counts;
85	} TagInfo;
86
87
88	/*
89	* This is used to store per-view width/height info at the tree nodes.
90	*/
91
92	typedef struct _NodeData NodeData;
93
94	struct _NodeData {
95	gpointer view_id;
96	NodeData *next;
97
98	/* Height and width of this node */
99	int height;
100	signed int width : 24;
101
102	/* boolean indicating whether the lines below this node are in need of validation.
103	* However, width/height should always represent the current total width and
104	* max height for lines below this node; the valid flag indicates whether the
105	* width/height on the lines needs recomputing, not whether the totals
106	* need recomputing.
107	*/
108	guint valid : 8; /* Actually a boolean */
109	};
110
111
112	/*
113	* The data structure below keeps summary information about one tag as part
114	* of the tag information in a node.
115	*/
116
117	typedef struct Summary {
118	GtkTextTagInfo *info; /* Handle for tag. */
119	int toggle_count; /* Number of transitions into or
120	* out of this tag that occur in
121	* the subtree rooted at this node. */
122	struct Summary *next; /* Next in list of all tags for same
123	* node, or NULL if at end of list. */
124	} Summary;
125
126	/*
127	* The data structure below defines a node in the B-tree.
128	*/
129
130	struct _GtkTextBTreeNode {
131	GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
132	* this is the root. */
133	GtkTextBTreeNode *next; /* Next in list of siblings with the
134	* same parent node, or NULL for end
135	* of list. */
136	Summary *summary; /* First in malloc-ed list of info
137	* about tags in this subtree (NULL if
138	* no tag info in the subtree). */
139	int level; /* Level of this node in the B-tree.
140	* 0 refers to the bottom of the tree
141	* (children are lines, not nodes). */
142	int num_lines; /* Total number of lines (leaves) in
143	* the subtree rooted here. */
144	int num_chars; /* Number of chars below here */
145	int num_children; /* Number of children of this node. */
146	union { /* First in linked list of children. */
147	struct _GtkTextBTreeNode *node; /* Used if level > 0. */
148	GtkTextLine *line; /* Used if level == 0. */
149	} children;
150
151	NodeData *node_data;
152	};
153
154
155	/*
156	* Used to store the list of views in our btree
157	*/
158
159	typedef struct _BTreeView BTreeView;
160
161	struct _BTreeView {
162	gpointer view_id;
163	GtkTextLayout *layout;
164	BTreeView *next;
165	BTreeView *prev;
166	};
167
168	/*
169	* And the tree itself
170	*/
171
172	struct _GtkTextBTree {
173	GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
174	GtkTextTagTable *table;
175	GHashTable *mark_table;
176	guint refcount;
177	GtkTextMark *insert_mark;
178	GtkTextMark *selection_bound_mark;
179	GtkTextBuffer *buffer;
180	BTreeView *views;
181	GSList *tag_infos;
182	gulong tag_changed_handler;
183
184	/* Incremented when a segment with a byte size > 0
185	* is added to or removed from the tree (i.e. the
186	* length of a line may have changed, and lines may
187	* have been added or removed). This invalidates
188	* all outstanding iterators.
189	*/
190	guint chars_changed_stamp;
191	/* Incremented when any segments are added or deleted;
192	* this makes outstanding iterators recalculate their
193	* pointed-to segment and segment offset.
194	*/
195	guint segments_changed_stamp;
196
197	/* Cache the last line in the buffer */
198	GtkTextLine *last_line;
199	guint last_line_stamp;
200
201	/* Cache the next-to-last line in the buffer,
202	* containing the end iterator
203	*/
204	GtkTextLine *end_iter_line;
205	GtkTextLineSegment *end_iter_segment;
206	int end_iter_segment_byte_index;
207	int end_iter_segment_char_offset;
208	guint end_iter_line_stamp;
209	guint end_iter_segment_stamp;
210
211	GHashTable *child_anchor_table;
212	};
213
214
215	/*
216	* Upper and lower bounds on how many children a node may have:
217	* rebalance when either of these limits is exceeded. MAX_CHILDREN
218	* should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
219	*/
220
221	/* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
222	shallow. It appears to be faster to locate a particular line number
223	if the tree is narrow and deep, since it is more finely sorted. I
224	guess this may increase memory use though, and make it slower to
225	walk the tree in order, or locate a particular byte index (which
226	is done by walking the tree in order).
227
228	There's basically a tradeoff here. However I'm thinking we want to
229	add pixels, byte counts, and char counts to the tree nodes,
230	at that point narrow and deep should speed up all operations,
231	not just the line number searches.
232	*/
233
234	#if 1
235	#define MAX_CHILDREN 12
236	#define MIN_CHILDREN 6
237	#else
238	#define MAX_CHILDREN 6
239	#define MIN_CHILDREN 3
240	#endif
241
242	/*
243	* Prototypes
244	*/
245
246	static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
247	gpointer view_id);
248	static void gtk_text_btree_rebalance (GtkTextBTree *tree,
249	GtkTextBTreeNode *node);
250	static GtkTextLine * get_last_line (GtkTextBTree *tree);
251	static void post_insert_fixup (GtkTextBTree *tree,
252	GtkTextLine *insert_line,
253	int line_count_delta,
254	int char_count_delta);
255	static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
256	GtkTextTagInfo *info,
257	int adjust);
258	static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
259	GtkTextTag *tag);
260
261	static void segments_changed (GtkTextBTree *tree);
262	static void chars_changed (GtkTextBTree *tree);
263	static void summary_list_destroy (Summary *summary);
264	static GtkTextLine *gtk_text_line_new (void);
265	static void gtk_text_line_destroy (GtkTextBTree *tree,
266	GtkTextLine *line);
267	static void gtk_text_line_set_parent (GtkTextLine *line,
268	GtkTextBTreeNode *node);
269	static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
270	gpointer view_id);
271
272	static GtkTextBTreeNode *gtk_text_btree_node_new (void);
273	#if 0
274	static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
275	#endif
276	static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
277	gpointer view_id);
278	static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
279	gpointer view_id);
280	static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
281	gpointer view_id);
282	static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
283	gpointer view_id);
284
285	static void gtk_text_btree_node_remove_view (BTreeView *view,
286	GtkTextBTreeNode *node,
287	gpointer view_id);
288	static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
289	GtkTextBTreeNode *node);
290	static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
291	GtkTextBTreeNode *node);
292	static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
293	gpointer view_id);
294	static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
295	gpointer view_id,
296	int *width,
297	int *height);
298	static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
299	GtkTextBTreeNode *node2);
300	static void get_tree_bounds (GtkTextBTree *tree,
301	GtkTextIter *start,
302	GtkTextIter *end);
303	static void tag_changed_cb (GtkTextTagTable *table,
304	GtkTextTag *tag,
305	gboolean size_changed,
306	GtkTextBTree *tree);
307	static void cleanup_line (GtkTextLine *line);
308	static void recompute_node_counts (GtkTextBTree *tree,
309	GtkTextBTreeNode *node);
310	static void inc_count (GtkTextTag *tag,
311	int inc,
312	TagInfo *tagInfoPtr);
313
314	static void summary_destroy (Summary *summary);
315
316	static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
317	const GtkTextIter *iter);
318	static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
319	GtkTextLineSegment *seg,
320	GtkTextLine *line);
321
322
323	static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
324	GtkTextTag *tag);
325	static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
326	GtkTextTag *tag);
327	static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
328	GtkTextTag *tag);
329
330	static void redisplay_region (GtkTextBTree *tree,
331	const GtkTextIter *start,
332	const GtkTextIter *end,
333	gboolean cursors_only);
334
335	/* Inline thingies */
336
337	static inline void
338	segments_changed (GtkTextBTree *tree)
339	{
340	tree->segments_changed_stamp += 1;
341	}
342
343	static inline void
344	chars_changed (GtkTextBTree *tree)
345	{
346	tree->chars_changed_stamp += 1;
347	}
348
349	/*
350	* BTree operations
351	*/
352
353	GtkTextBTree*
354	_gtk_text_btree_new (GtkTextTagTable *table,
355	GtkTextBuffer *buffer)
356	{
357	GtkTextBTree *tree;
358	GtkTextBTreeNode *root_node;
359	GtkTextLine *line, *line2;
360
361	g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
362	g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
363
364	/*
365	* The tree will initially have two empty lines. The second line
366	* isn't actually part of the tree's contents, but its presence
367	* makes several operations easier. The tree will have one GtkTextBTreeNode,
368	* which is also the root of the tree.
369	*/
370
371	/* Create the root node. */
372
373	root_node = gtk_text_btree_node_new ();
374
375	line = gtk_text_line_new ();
376	line2 = gtk_text_line_new ();
377
378	root_node->parent = NULL;
379	root_node->next = NULL;
380	root_node->summary = NULL;
381	root_node->level = 0;
382	root_node->children.line = line;
383	root_node->num_children = 2;
384	root_node->num_lines = 2;
385	root_node->num_chars = 2;
386
387	line->parent = root_node;
388	line->next = line2;
389
390	line->segments = _gtk_char_segment_new (text: "\n", len: 1);
391
392	line2->parent = root_node;
393	line2->next = NULL;
394	line2->segments = _gtk_char_segment_new (text: "\n", len: 1);
395
396	/* Create the tree itself */
397
398	tree = g_slice_new0 (GtkTextBTree);
399	tree->root_node = root_node;
400	tree->table = table;
401	tree->views = NULL;
402
403	/* Set these to values that are unlikely to be found
404	* in random memory garbage, and also avoid
405	* duplicates between tree instances.
406	*/
407	tree->chars_changed_stamp = g_random_int ();
408	tree->segments_changed_stamp = g_random_int ();
409
410	tree->last_line_stamp = tree->chars_changed_stamp - 1;
411	tree->last_line = NULL;
412
413	tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
414	tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
415	tree->end_iter_line = NULL;
416	tree->end_iter_segment_byte_index = 0;
417	tree->end_iter_segment_char_offset = 0;
418
419	g_object_ref (tree->table);
420
421	tree->tag_changed_handler = g_signal_connect (tree->table,
422	"tag-changed",
423	G_CALLBACK (tag_changed_cb),
424	tree);
425
426	tree->mark_table = g_hash_table_new (hash_func: g_str_hash, key_equal_func: g_str_equal);
427	tree->child_anchor_table = NULL;
428
429	/* We don't ref the buffer, since the buffer owns us;
430	* we'd have some circularity issues. The buffer always
431	* lasts longer than the BTree
432	*/
433	tree->buffer = buffer;
434
435	{
436	GtkTextIter start;
437	GtkTextLineSegment *seg;
438
439	_gtk_text_btree_get_iter_at_line_char (tree, iter: &start, line_number: 0, char_index: 0);
440
441
442	tree->insert_mark = _gtk_text_btree_set_mark (tree,
443	NULL,
444	name: "insert",
445	FALSE,
446	index: &start,
447	FALSE);
448
449	seg = tree->insert_mark->segment;
450
451	seg->body.mark.not_deleteable = TRUE;
452	seg->body.mark.visible = TRUE;
453
454	tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
455	NULL,
456	name: "selection_bound",
457	FALSE,
458	index: &start,
459	FALSE);
460
461	seg = tree->selection_bound_mark->segment;
462
463	seg->body.mark.not_deleteable = TRUE;
464
465	g_object_ref (tree->insert_mark);
466	g_object_ref (tree->selection_bound_mark);
467	}
468
469	tree->refcount = 1;
470
471	return tree;
472	}
473
474	void
475	_gtk_text_btree_ref (GtkTextBTree *tree)
476	{
477	g_return_if_fail (tree != NULL);
478	g_return_if_fail (tree->refcount > 0);
479
480	tree->refcount += 1;
481	}
482
483	void
484	_gtk_text_btree_unref (GtkTextBTree *tree)
485	{
486	g_return_if_fail (tree != NULL);
487	g_return_if_fail (tree->refcount > 0);
488
489	tree->refcount -= 1;
490
491	if (tree->refcount == 0)
492	{
493	g_signal_handler_disconnect (instance: tree->table,
494	handler_id: tree->tag_changed_handler);
495
496	g_object_unref (object: tree->table);
497	tree->table = NULL;
498
499	gtk_text_btree_node_destroy (tree, node: tree->root_node);
500	tree->root_node = NULL;
501
502	g_assert (g_hash_table_size (tree->mark_table) == 0);
503	g_hash_table_destroy (hash_table: tree->mark_table);
504	tree->mark_table = NULL;
505	if (tree->child_anchor_table != NULL)
506	{
507	g_hash_table_destroy (hash_table: tree->child_anchor_table);
508	tree->child_anchor_table = NULL;
509	}
510
511	g_object_unref (object: tree->insert_mark);
512	tree->insert_mark = NULL;
513	g_object_unref (object: tree->selection_bound_mark);
514	tree->selection_bound_mark = NULL;
515
516	g_slice_free (GtkTextBTree, tree);
517	}
518	}
519
520	GtkTextBuffer*
521	_gtk_text_btree_get_buffer (GtkTextBTree *tree)
522	{
523	return tree->buffer;
524	}
525
526	guint
527	_gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
528	{
529	return tree->chars_changed_stamp;
530	}
531
532	guint
533	_gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
534	{
535	return tree->segments_changed_stamp;
536	}
537
538	void
539	_gtk_text_btree_segments_changed (GtkTextBTree *tree)
540	{
541	g_return_if_fail (tree != NULL);
542	segments_changed (tree);
543	}
544
545	/*
546	* Indexable segment mutation
547	*/
548
549	/*
550	* The following function is responsible for resolving the bidi direction
551	* for the lines between start and end. But it also calculates any
552	* dependent bidi direction for surrounding lines that change as a result
553	* of the bidi direction decisions within the range. The function is
554	* trying to do as little propagation as is needed.
555	*/
556	static void
557	gtk_text_btree_resolve_bidi (GtkTextIter *start,
558	GtkTextIter *end)
559	{
560	GtkTextBTree *tree = _gtk_text_iter_get_btree (iter: start);
561	GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
562	PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
563
564	/* Resolve the strong bidi direction for all lines between
565	* start and end.
566	*/
567	start_line = _gtk_text_iter_get_text_line (iter: start);
568	start_line_prev = _gtk_text_line_previous (line: start_line);
569	end_line = _gtk_text_iter_get_text_line (iter: end);
570	end_line_next = _gtk_text_line_next (line: end_line);
571
572	line = start_line;
573	while (line && line != end_line_next)
574	{
575	/* Loop through the segments and search for a strong character
576	*/
577	GtkTextLineSegment *seg = line->segments;
578	line->dir_strong = PANGO_DIRECTION_NEUTRAL;
579
580	while (seg)
581	{
582	if (seg->type == &gtk_text_char_type && seg->byte_count > 0)
583	{
584	PangoDirection pango_dir;
585
586	pango_dir = gdk_find_base_dir (text: seg->body.chars, len: seg->byte_count);
587
588	if (pango_dir != PANGO_DIRECTION_NEUTRAL)
589	{
590	line->dir_strong = pango_dir;
591	break;
592	}
593	}
594	seg = seg->next;
595	}
596
597	line = _gtk_text_line_next (line);
598	}
599
600	/* Sweep forward */
601
602	/* The variable dir_above_propagated contains the forward propagated
603	* direction before start. It is neutral if start is in the beginning
604	* of the buffer.
605	*/
606	dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
607	if (start_line_prev)
608	dir_above_propagated = start_line_prev->dir_propagated_forward;
609
610	/* Loop forward and propagate the direction of each paragraph
611	* to all neutral lines.
612	*/
613	line = start_line;
614	last_strong = dir_above_propagated;
615	while (line != end_line_next)
616	{
617	if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
618	last_strong = line->dir_strong;
619
620	line->dir_propagated_forward = last_strong;
621
622	line = _gtk_text_line_next (line);
623	}
624
625	/* Continue propagating as long as the previous resolved forward
626	* is different from last_strong.
627	*/
628	{
629	GtkTextIter end_propagate;
630
631	while (line &&
632	line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
633	line->dir_propagated_forward != last_strong)
634	{
635	GtkTextLine *prev = line;
636	line->dir_propagated_forward = last_strong;
637
638	line = _gtk_text_line_next(line);
639	if (!line)
640	{
641	line = prev;
642	break;
643	}
644	}
645
646	/* The last line to invalidate is the last line before the
647	* line with the strong character. Or in case of the end of the
648	* buffer, the last line of the buffer. (There seems to be an
649	* extra "virtual" last line in the buffer that must not be used
650	* calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
651	* _gtk_text_line_previous is ok in that case as well.)
652	*/
653	line = _gtk_text_line_previous (line);
654	_gtk_text_btree_get_iter_at_line (tree, iter: &end_propagate, line, byte_offset: 0);
655	_gtk_text_btree_invalidate_region (tree, start: end, end: &end_propagate, FALSE);
656	}
657
658	/* Sweep backward */
659
660	/* The variable dir_below_propagated contains the backward propagated
661	* direction after end. It is neutral if end is at the end of
662	* the buffer.
663	*/
664	dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
665	if (end_line_next)
666	dir_below_propagated = end_line_next->dir_propagated_back;
667
668	/* Loop backward and propagate the direction of each paragraph
669	* to all neutral lines.
670	*/
671	line = end_line;
672	last_strong = dir_below_propagated;
673	while (line != start_line_prev)
674	{
675	if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
676	last_strong = line->dir_strong;
677
678	line->dir_propagated_back = last_strong;
679
680	line = _gtk_text_line_previous (line);
681	}
682
683	/* Continue propagating as long as the resolved backward dir
684	* is different from last_strong.
685	*/
686	{
687	GtkTextIter start_propagate;
688
689	while (line &&
690	line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
691	line->dir_propagated_back != last_strong)
692	{
693	GtkTextLine *prev = line;
694	line->dir_propagated_back = last_strong;
695
696	line = _gtk_text_line_previous (line);
697	if (!line)
698	{
699	line = prev;
700	break;
701	}
702	}
703
704	/* We only need to invalidate for backwards propagation if the
705	* line we ended up on didn't get a direction from forwards
706	* propagation.
707	*/
708	if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
709	{
710	_gtk_text_btree_get_iter_at_line (tree, iter: &start_propagate, line, byte_offset: 0);
711	_gtk_text_btree_invalidate_region (tree, start: &start_propagate, end: start, FALSE);
712	}
713	}
714	}
715
716	void
717	_gtk_text_btree_delete (GtkTextIter *start,
718	GtkTextIter *end)
719	{
720	GtkTextLineSegment *prev_seg; /* The segment just before the start
721	* of the deletion range. */
722	GtkTextLineSegment *last_seg; /* The segment just after the end
723	* of the deletion range. */
724	GtkTextLineSegment *seg, *next, *next2;
725	GtkTextLine *curline;
726	GtkTextBTreeNode *curnode, *node;
727	GtkTextBTree *tree;
728	GtkTextLine *start_line;
729	GtkTextLine *end_line;
730	GtkTextLine *line;
731	GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
732	int start_byte_offset;
733
734	g_return_if_fail (start != NULL);
735	g_return_if_fail (end != NULL);
736	g_return_if_fail (_gtk_text_iter_get_btree (start) ==
737	_gtk_text_iter_get_btree (end));
738
739	gtk_text_iter_order (first: start, second: end);
740
741	tree = _gtk_text_iter_get_btree (iter: start);
742
743	#ifdef G_ENABLE_DEBUG
744	if (GTK_DEBUG_CHECK (TEXT))
745	_gtk_text_btree_check (tree);
746	#endif
747
748	/* Broadcast the need for redisplay before we break the iterators */
749	DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
750	_gtk_text_btree_invalidate_region (tree, start, end, FALSE);
751
752	/* Save the byte offset so we can reset the iterators */
753	start_byte_offset = gtk_text_iter_get_line_index (iter: start);
754
755	start_line = _gtk_text_iter_get_text_line (iter: start);
756	end_line = _gtk_text_iter_get_text_line (iter: end);
757
758	/*
759	* Split the start and end segments, so we have a place
760	* to insert our new text.
761	*
762	* Tricky point: split at end first; otherwise the split
763	* at end may invalidate seg and/or prev_seg. This allows
764	* us to avoid invalidating segments for start.
765	*/
766
767	last_seg = gtk_text_line_segment_split (iter: end);
768	if (last_seg != NULL)
769	last_seg = last_seg->next;
770	else
771	last_seg = end_line->segments;
772
773	prev_seg = gtk_text_line_segment_split (iter: start);
774	if (prev_seg != NULL)
775	{
776	seg = prev_seg->next;
777	prev_seg->next = last_seg;
778	}
779	else
780	{
781	seg = start_line->segments;
782	start_line->segments = last_seg;
783	}
784
785	/* notify iterators that their segments need recomputation,
786	just for robustness. */
787	segments_changed (tree);
788
789	/*
790	* Delete all of the segments between prev_seg and last_seg.
791	*/
792
793	curline = start_line;
794	curnode = curline->parent;
795	while (seg != last_seg)
796	{
797	int char_count = 0;
798
799	if (seg == NULL)
800	{
801	GtkTextLine *nextline;
802
803	/*
804	* We just ran off the end of a line. First find the
805	* next line, then go back to the old line and delete it
806	* (unless it's the starting line for the range).
807	*/
808
809	nextline = _gtk_text_line_next (line: curline);
810	if (curline != start_line)
811	{
812	if (curnode == start_line->parent)
813	start_line->next = curline->next;
814	else
815	curnode->children.line = curline->next;
816
817	for (node = curnode; node != NULL;
818	node = node->parent)
819	{
820	/* Don't update node->num_chars, because
821	* that was done when we deleted the segments.
822	*/
823	node->num_lines -= 1;
824	}
825
826	curnode->num_children -= 1;
827	curline->next = deleted_lines;
828	deleted_lines = curline;
829	}
830
831	curline = nextline;
832	seg = curline->segments;
833
834	/*
835	* If the GtkTextBTreeNode is empty then delete it and its parents,
836	* recursively upwards until a non-empty GtkTextBTreeNode is found.
837	*/
838
839	while (curnode->num_children == 0)
840	{
841	GtkTextBTreeNode *parent;
842
843	parent = curnode->parent;
844	if (parent->children.node == curnode)
845	{
846	parent->children.node = curnode->next;
847	}
848	else
849	{
850	GtkTextBTreeNode *prevnode = parent->children.node;
851	while (prevnode->next != curnode)
852	{
853	prevnode = prevnode->next;
854	}
855	prevnode->next = curnode->next;
856	}
857	parent->num_children--;
858	gtk_text_btree_node_free_empty (tree, node: curnode);
859	curnode = parent;
860	}
861	curnode = curline->parent;
862	continue;
863	}
864
865	next = seg->next;
866	char_count = seg->char_count;
867
868	if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
869	{
870	/*
871	* This segment refuses to die. Move it to prev_seg and
872	* advance prev_seg if the segment has left gravity.
873	*/
874
875	if (prev_seg == NULL)
876	{
877	seg->next = start_line->segments;
878	start_line->segments = seg;
879	}
880	else if (prev_seg->next &&
881	prev_seg->next != last_seg &&
882	seg->type == &gtk_text_toggle_off_type &&
883	prev_seg->next->type == &gtk_text_toggle_on_type &&
884	seg->body.toggle.info == prev_seg->next->body.toggle.info)
885	{
886	/* Try to match an off toggle with the matching on toggle
887	* if it immediately follows. This is a common case, and
888	* handling it here prevents quadratic blowup in
889	* cleanup_line() below. See bug 317125.
890	*/
891	next2 = prev_seg->next->next;
892	_gtk_toggle_segment_free (seg: prev_seg->next);
893	prev_seg->next = next2;
894	_gtk_toggle_segment_free (seg);
895	seg = NULL;
896	}
897	else
898	{
899	seg->next = prev_seg->next;
900	prev_seg->next = seg;
901	}
902
903	if (seg && seg->type->leftGravity)
904	{
905	prev_seg = seg;
906	}
907	}
908	else
909	{
910	/* Segment is gone. Decrement the char count of the node and
911	all its parents. */
912	for (node = curnode; node != NULL;
913	node = node->parent)
914	{
915	node->num_chars -= char_count;
916	}
917	}
918
919	seg = next;
920	}
921
922	/*
923	* If the beginning and end of the deletion range are in different
924	* lines, join the two lines together and discard the ending line.
925	*/
926
927	if (start_line != end_line)
928	{
929	BTreeView *view;
930	GtkTextBTreeNode *ancestor_node;
931	GtkTextLine *prevline;
932	int chars_moved;
933
934	/* last_seg was appended to start_line up at the top of this function */
935	chars_moved = 0;
936	for (seg = last_seg; seg != NULL;
937	seg = seg->next)
938	{
939	chars_moved += seg->char_count;
940	if (seg->type->lineChangeFunc != NULL)
941	{
942	(*seg->type->lineChangeFunc)(seg, end_line);
943	}
944	}
945
946	for (node = start_line->parent; node != NULL;
947	node = node->parent)
948	{
949	node->num_chars += chars_moved;
950	}
951
952	curnode = end_line->parent;
953	for (node = curnode; node != NULL;
954	node = node->parent)
955	{
956	node->num_chars -= chars_moved;
957	node->num_lines--;
958	}
959	curnode->num_children--;
960	prevline = curnode->children.line;
961	if (prevline == end_line)
962	{
963	curnode->children.line = end_line->next;
964	}
965	else
966	{
967	while (prevline->next != end_line)
968	{
969	prevline = prevline->next;
970	}
971	prevline->next = end_line->next;
972	}
973	end_line->next = deleted_lines;
974	deleted_lines = end_line;
975
976	/* We now fix up the per-view aggregates. We add all the height and
977	* width for the deleted lines to the start line, so that when revalidation
978	* occurs, the correct change in size is seen.
979	*/
980	ancestor_node = gtk_text_btree_node_common_parent (node1: curnode, node2: start_line->parent);
981	view = tree->views;
982	while (view)
983	{
984	GtkTextLineData *ld;
985
986	int deleted_width = 0;
987	int deleted_height = 0;
988
989	line = deleted_lines;
990	while (line)
991	{
992	GtkTextLine *next_line = line->next;
993	ld = _gtk_text_line_get_data (line, view_id: view->view_id);
994
995	if (ld)
996	{
997	deleted_width = MAX (deleted_width, ld->width);
998	deleted_height += ld->height;
999	}
1000
1001	line = next_line;
1002	}
1003
1004	if (deleted_width > 0 || deleted_height > 0)
1005	{
1006	ld = _gtk_text_line_get_data (line: start_line, view_id: view->view_id);
1007
1008	if (ld == NULL)
1009	{
1010	/* This means that start_line has never been validated.
1011	* We don't really want to do the validation here but
1012	* we do need to store our temporary sizes. So we
1013	* create the line data and assume a line w/h of 0.
1014	*/
1015	ld = _gtk_text_line_data_new (layout: view->layout, line: start_line);
1016	_gtk_text_line_add_data (line: start_line, data: ld);
1017	ld->width = 0;
1018	ld->height = 0;
1019	ld->valid = FALSE;
1020	}
1021
1022	ld->width = MAX (deleted_width, ld->width);
1023	ld->height += deleted_height;
1024	ld->valid = FALSE;
1025	}
1026
1027	gtk_text_btree_node_check_valid_downward (node: ancestor_node, view_id: view->view_id);
1028	if (ancestor_node->parent)
1029	gtk_text_btree_node_check_valid_upward (node: ancestor_node->parent, view_id: view->view_id);
1030
1031	view = view->next;
1032	}
1033
1034	line = deleted_lines;
1035	while (line)
1036	{
1037	GtkTextLine *next_line = line->next;
1038
1039	gtk_text_line_destroy (tree, line);
1040
1041	line = next_line;
1042	}
1043
1044	/* avoid dangling pointer */
1045	deleted_lines = NULL;
1046
1047	gtk_text_btree_rebalance (tree, node: curnode);
1048	}
1049
1050	/*
1051	* Cleanup the segments in the new line.
1052	*/
1053
1054	cleanup_line (line: start_line);
1055
1056	/*
1057	* Lastly, rebalance the first GtkTextBTreeNode of the range.
1058	*/
1059
1060	gtk_text_btree_rebalance (tree, node: start_line->parent);
1061
1062	/* Notify outstanding iterators that they
1063	are now hosed */
1064	chars_changed (tree);
1065	segments_changed (tree);
1066
1067	#ifdef G_ENABLE_DEBUG
1068	if (GTK_DEBUG_CHECK (TEXT))
1069	_gtk_text_btree_check (tree);
1070	#endif
1071
1072	/* Re-initialize our iterators */
1073	_gtk_text_btree_get_iter_at_line (tree, iter: start, line: start_line, byte_offset: start_byte_offset);
1074	*end = *start;
1075
1076	gtk_text_btree_resolve_bidi (start, end);
1077	}
1078
1079	void
1080	_gtk_text_btree_insert (GtkTextIter *iter,
1081	const char *text,
1082	int len)
1083	{
1084	GtkTextLineSegment *prev_seg; /* The segment just before the first
1085	* new segment (NULL means new segment
1086	* is at beginning of line). */
1087	GtkTextLineSegment *cur_seg; /* Current segment; new characters
1088	* are inserted just after this one.
1089	* NULL means insert at beginning of
1090	* line. */
1091	GtkTextLine *line; /* Current line (new segments are
1092	* added to this line). */
1093	GtkTextLineSegment *seg;
1094	GtkTextLine *newline;
1095	int chunk_len; /* # characters in current chunk. */
1096	int sol; /* start of line */
1097	int eol; /* Pointer to character just after last
1098	* one in current chunk.
1099	*/
1100	int delim; /* index of paragraph delimiter */
1101	int line_count_delta; /* Counts change to total number of
1102	* lines in file.
1103	*/
1104
1105	int char_count_delta; /* change to number of chars */
1106	GtkTextBTree *tree;
1107	int start_byte_index;
1108	GtkTextLine *start_line;
1109
1110	g_return_if_fail (text != NULL);
1111	g_return_if_fail (iter != NULL);
1112
1113	if (len < 0)
1114	len = strlen (s: text);
1115
1116	/* extract iterator info */
1117	tree = _gtk_text_iter_get_btree (iter);
1118	line = _gtk_text_iter_get_text_line (iter);
1119
1120	start_line = line;
1121	start_byte_index = gtk_text_iter_get_line_index (iter);
1122
1123	/* Get our insertion segment split. Note this assumes line allows
1124	* char insertions, which isn't true of the "last" line. But iter
1125	* should not be on that line, as we assert here.
1126	*/
1127	g_assert (!_gtk_text_line_is_last (line, tree));
1128	prev_seg = gtk_text_line_segment_split (iter);
1129	cur_seg = prev_seg;
1130
1131	/* Invalidate all iterators */
1132	chars_changed (tree);
1133	segments_changed (tree);
1134
1135	/*
1136	* Chop the text up into lines and create a new segment for
1137	* each line, plus a new line for the leftovers from the
1138	* previous line.
1139	*/
1140
1141	eol = 0;
1142	sol = 0;
1143	line_count_delta = 0;
1144	char_count_delta = 0;
1145	while (eol < len)
1146	{
1147	sol = eol;
1148
1149	pango_find_paragraph_boundary (text: text + sol,
1150	length: len - sol,
1151	paragraph_delimiter_index: &delim,
1152	next_paragraph_start: &eol);
1153
1154	/* make these relative to the start of the text */
1155	delim += sol;
1156	eol += sol;
1157
1158	g_assert (eol >= sol);
1159	g_assert (delim >= sol);
1160	g_assert (eol >= delim);
1161	g_assert (sol >= 0);
1162	g_assert (eol <= len);
1163
1164	chunk_len = eol - sol;
1165
1166	g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1167	seg = _gtk_char_segment_new (text: &text[sol], len: chunk_len);
1168
1169	char_count_delta += seg->char_count;
1170
1171	if (cur_seg == NULL)
1172	{
1173	seg->next = line->segments;
1174	line->segments = seg;
1175	}
1176	else
1177	{
1178	seg->next = cur_seg->next;
1179	cur_seg->next = seg;
1180	}
1181
1182	if (delim == eol)
1183	{
1184	/* chunk didn't end with a paragraph separator */
1185	g_assert (eol == len);
1186	break;
1187	}
1188
1189	/*
1190	* The chunk ended with a newline, so create a new GtkTextLine
1191	* and move the remainder of the old line to it.
1192	*/
1193
1194	newline = gtk_text_line_new ();
1195	gtk_text_line_set_parent (line: newline, node: line->parent);
1196	newline->next = line->next;
1197	line->next = newline;
1198	newline->segments = seg->next;
1199	seg->next = NULL;
1200	line = newline;
1201	cur_seg = NULL;
1202	line_count_delta++;
1203	}
1204
1205	/*
1206	* Cleanup the starting line for the insertion, plus the ending
1207	* line if it's different.
1208	*/
1209
1210	cleanup_line (line: start_line);
1211	if (line != start_line)
1212	{
1213	cleanup_line (line);
1214	}
1215
1216	post_insert_fixup (tree, insert_line: line, line_count_delta, char_count_delta);
1217
1218	/* Invalidate our region, and reset the iterator the user
1219	passed in to point to the end of the inserted text. */
1220	{
1221	GtkTextIter start;
1222	GtkTextIter end;
1223
1224
1225	_gtk_text_btree_get_iter_at_line (tree,
1226	iter: &start,
1227	line: start_line,
1228	byte_offset: start_byte_index);
1229	end = start;
1230
1231	/* We could almost certainly be more efficient here
1232	by saving the information from the insertion loop
1233	above. FIXME */
1234	gtk_text_iter_forward_chars (iter: &end, count: char_count_delta);
1235
1236	DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1237	_gtk_text_btree_invalidate_region (tree, start: &start, end: &end, FALSE);
1238
1239
1240	/* Convenience for the user */
1241	*iter = end;
1242
1243	gtk_text_btree_resolve_bidi (start: &start, end: &end);
1244	}
1245	}
1246
1247	static void
1248	insert_paintable_or_widget_segment (GtkTextIter *iter,
1249	GtkTextLineSegment *seg)
1250	{
1251	GtkTextIter start;
1252	GtkTextLineSegment *prevPtr;
1253	GtkTextLine *line;
1254	GtkTextBTree *tree;
1255	int start_byte_offset;
1256
1257	line = _gtk_text_iter_get_text_line (iter);
1258	tree = _gtk_text_iter_get_btree (iter);
1259	start_byte_offset = gtk_text_iter_get_line_index (iter);
1260
1261	prevPtr = gtk_text_line_segment_split (iter);
1262	if (prevPtr == NULL)
1263	{
1264	seg->next = line->segments;
1265	line->segments = seg;
1266	}
1267	else
1268	{
1269	seg->next = prevPtr->next;
1270	prevPtr->next = seg;
1271	}
1272
1273	post_insert_fixup (tree, insert_line: line, line_count_delta: 0, char_count_delta: seg->char_count);
1274
1275	chars_changed (tree);
1276	segments_changed (tree);
1277
1278	/* reset *iter for the user, and invalidate tree nodes */
1279
1280	_gtk_text_btree_get_iter_at_line (tree, iter: &start, line, byte_offset: start_byte_offset);
1281
1282	*iter = start;
1283	gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1284
1285	DV (g_print ("invalidating due to inserting paintable/widget (%s)\n", G_STRLOC));
1286	_gtk_text_btree_invalidate_region (tree, start: &start, end: iter, FALSE);
1287	}
1288
1289	void
1290	_gtk_text_btree_insert_paintable (GtkTextIter *iter,
1291	GdkPaintable *paintable)
1292	{
1293	GtkTextLineSegment *seg;
1294
1295	seg = _gtk_paintable_segment_new (paintable);
1296	seg->body.paintable.tree = _gtk_text_iter_get_btree (iter);
1297	seg->body.paintable.line = _gtk_text_iter_get_text_line (iter);
1298
1299	insert_paintable_or_widget_segment (iter, seg);
1300	}
1301
1302	void
1303	_gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1304	GtkTextChildAnchor *anchor)
1305	{
1306	GtkTextLineSegment *seg;
1307	GtkTextBTree *tree;
1308
1309	if (anchor->segment != NULL)
1310	{
1311	g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1312	return;
1313	}
1314
1315	seg = _gtk_widget_segment_new (anchor);
1316
1317	tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1318	seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1319
1320	insert_paintable_or_widget_segment (iter, seg);
1321
1322	if (tree->child_anchor_table == NULL)
1323	tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1324
1325	g_hash_table_insert (hash_table: tree->child_anchor_table,
1326	key: seg->body.child.obj,
1327	value: seg->body.child.obj);
1328	}
1329
1330	void
1331	_gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1332	{
1333	GtkTextLineSegment *seg;
1334
1335	seg = anchor->segment;
1336
1337	g_hash_table_remove (hash_table: seg->body.child.tree->child_anchor_table,
1338	key: anchor);
1339	}
1340
1341	/*
1342	* View stuff
1343	*/
1344
1345	static GtkTextLine*
1346	find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1347	GtkTextBTreeNode *node, int y, int *line_top,
1348	GtkTextLine *last_line)
1349	{
1350	int current_y = 0;
1351
1352	#ifdef G_ENABLE_DEBUG
1353	if (GTK_DEBUG_CHECK (TEXT))
1354	_gtk_text_btree_check (tree);
1355	#endif
1356
1357	if (node->level == 0)
1358	{
1359	GtkTextLine *line;
1360
1361	line = node->children.line;
1362
1363	while (line != NULL && line != last_line)
1364	{
1365	GtkTextLineData *ld;
1366
1367	ld = _gtk_text_line_get_data (line, view_id: view->view_id);
1368
1369	if (ld)
1370	{
1371	if (y < (current_y + ld->height))
1372	return line;
1373
1374	current_y += ld->height;
1375	*line_top += ld->height;
1376	}
1377
1378	line = line->next;
1379	}
1380	return NULL;
1381	}
1382	else
1383	{
1384	GtkTextBTreeNode *child;
1385
1386	child = node->children.node;
1387
1388	while (child != NULL)
1389	{
1390	int width;
1391	int height;
1392
1393	gtk_text_btree_node_get_size (node: child, view_id: view->view_id,
1394	width: &width, height: &height);
1395
1396	if (y < (current_y + height))
1397	return find_line_by_y (tree, view, node: child,
1398	y: y - current_y, line_top,
1399	last_line);
1400
1401	current_y += height;
1402	*line_top += height;
1403
1404	child = child->next;
1405	}
1406
1407	return NULL;
1408	}
1409	}
1410
1411	GtkTextLine *
1412	_gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1413	gpointer view_id,
1414	int ypixel,
1415	int *line_top_out)
1416	{
1417	GtkTextLine *line;
1418	BTreeView *view;
1419	GtkTextLine *last_line;
1420	int line_top = 0;
1421
1422	view = gtk_text_btree_get_view (tree, view_id);
1423	g_return_val_if_fail (view != NULL, NULL);
1424
1425	last_line = get_last_line (tree);
1426
1427	line = find_line_by_y (tree, view, node: tree->root_node, y: ypixel, line_top: &line_top,
1428	last_line);
1429
1430	if (line_top_out)
1431	*line_top_out = line_top;
1432
1433	return line;
1434	}
1435
1436	static int
1437	find_line_top_in_line_list (GtkTextBTree *tree,
1438	BTreeView *view,
1439	GtkTextLine *line,
1440	GtkTextLine *target_line,
1441	int y)
1442	{
1443	while (line != NULL)
1444	{
1445	GtkTextLineData *ld;
1446
1447	if (line == target_line)
1448	return y;
1449
1450	ld = _gtk_text_line_get_data (line, view_id: view->view_id);
1451	if (ld)
1452	y += ld->height;
1453
1454	line = line->next;
1455	}
1456
1457	g_assert_not_reached (); /* If we get here, our
1458	target line didn't exist
1459	under its parent node */
1460	return 0;
1461	}
1462
1463	int
1464	_gtk_text_btree_find_line_top (GtkTextBTree *tree,
1465	GtkTextLine *target_line,
1466	gpointer view_id)
1467	{
1468	int y = 0;
1469	BTreeView *view;
1470	GtkTextBTreeNode *node;
1471	GtkTextBTreeNode *nodes[64];
1472	int tos = 0;
1473
1474	view = gtk_text_btree_get_view (tree, view_id);
1475
1476	g_return_val_if_fail (view != NULL, 0);
1477
1478	node = target_line->parent;
1479	while (node != NULL)
1480	{
1481	nodes[tos++] = node;
1482	node = node->parent;
1483	}
1484
1485	tos--;
1486	while (tos >= 0)
1487	{
1488	node = nodes[tos];
1489
1490	if (node->level == 0)
1491	{
1492	return find_line_top_in_line_list (tree, view,
1493	line: node->children.line,
1494	target_line, y);
1495	}
1496	else
1497	{
1498	GtkTextBTreeNode *child;
1499	GtkTextBTreeNode *target_node;
1500
1501	g_assert (tos > 0); /* not at level 0 */
1502	target_node = nodes[tos - 1];
1503
1504	child = node->children.node;
1505
1506	while (child != NULL)
1507	{
1508	int width;
1509	int height;
1510
1511	if (child == target_node)
1512	break;
1513	else
1514	{
1515	gtk_text_btree_node_get_size (node: child, view_id: view->view_id,
1516	width: &width, height: &height);
1517	y += height;
1518	}
1519	child = child->next;
1520	}
1521	g_assert (child != NULL); /* should have broken out before we
1522	ran out of nodes */
1523	}
1524
1525	tos--;
1526	}
1527
1528	g_assert_not_reached (); /* we return when we find the target line */
1529	return 0;
1530	}
1531
1532	void
1533	_gtk_text_btree_add_view (GtkTextBTree *tree,
1534	GtkTextLayout *layout)
1535	{
1536	BTreeView *view;
1537	GtkTextLine *last_line;
1538	GtkTextLineData *line_data;
1539
1540	g_return_if_fail (tree != NULL);
1541
1542	view = g_slice_new (BTreeView);
1543
1544	view->view_id = layout;
1545	view->layout = layout;
1546
1547	view->next = tree->views;
1548	view->prev = NULL;
1549
1550	if (tree->views)
1551	{
1552	g_assert (tree->views->prev == NULL);
1553	tree->views->prev = view;
1554	}
1555
1556	tree->views = view;
1557
1558	/* The last line in the buffer has identity values for the per-view
1559	* data so that we can avoid special case checks for it in a large
1560	* number of loops
1561	*/
1562	last_line = get_last_line (tree);
1563
1564	line_data = g_slice_new (GtkTextLineData);
1565	line_data->view_id = layout;
1566	line_data->next = NULL;
1567	line_data->width = 0;
1568	line_data->height = 0;
1569	line_data->valid = TRUE;
1570
1571	_gtk_text_line_add_data (line: last_line, data: line_data);
1572	}
1573
1574	void
1575	_gtk_text_btree_remove_view (GtkTextBTree *tree,
1576	gpointer view_id)
1577	{
1578	BTreeView *view;
1579	GtkTextLine *last_line;
1580	GtkTextLineData *line_data;
1581
1582	g_return_if_fail (tree != NULL);
1583
1584	view = tree->views;
1585
1586	while (view != NULL)
1587	{
1588	if (view->view_id == view_id)
1589	break;
1590
1591	view = view->next;
1592	}
1593
1594	g_return_if_fail (view != NULL);
1595
1596	if (view->next)
1597	view->next->prev = view->prev;
1598
1599	if (view->prev)
1600	view->prev->next = view->next;
1601
1602	if (view == tree->views)
1603	tree->views = view->next;
1604
1605	/* Remove the line data for the last line which we added ourselves.
1606	* (Do this first, so that we don't try to call the view's line data destructor on it.)
1607	*/
1608	last_line = get_last_line (tree);
1609	line_data = _gtk_text_line_remove_data (line: last_line, view_id);
1610	g_slice_free (GtkTextLineData, line_data);
1611
1612	gtk_text_btree_node_remove_view (view, node: tree->root_node, view_id);
1613
1614	view->layout = (gpointer) 0xdeadbeef;
1615	view->view_id = (gpointer) 0xdeadbeef;
1616
1617	g_slice_free (BTreeView, view);
1618	}
1619
1620	void
1621	_gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1622	const GtkTextIter *start,
1623	const GtkTextIter *end,
1624	gboolean cursors_only)
1625	{
1626	BTreeView *view;
1627
1628	view = tree->views;
1629
1630	while (view != NULL)
1631	{
1632	if (cursors_only)
1633	gtk_text_layout_invalidate_cursors (layout: view->layout, start, end);
1634	else
1635	gtk_text_layout_invalidate (layout: view->layout, start, end);
1636
1637	view = view->next;
1638	}
1639	}
1640
1641	void
1642	_gtk_text_btree_get_view_size (GtkTextBTree *tree,
1643	gpointer view_id,
1644	int *width,
1645	int *height)
1646	{
1647	g_return_if_fail (tree != NULL);
1648	g_return_if_fail (view_id != NULL);
1649
1650	gtk_text_btree_node_get_size (node: tree->root_node, view_id,
1651	width, height);
1652	}
1653
1654	/*
1655	* Tag
1656	*/
1657
1658	typedef struct {
1659	GtkTextIter *iters;
1660	guint count;
1661	guint allocated;
1662	} IterStack;
1663
1664	static IterStack*
1665	iter_stack_new (void)
1666	{
1667	IterStack *stack;
1668	stack = g_slice_new (IterStack);
1669	stack->iters = NULL;
1670	stack->count = 0;
1671	stack->allocated = 0;
1672	return stack;
1673	}
1674
1675	static void
1676	iter_stack_push (IterStack *stack,
1677	const GtkTextIter *iter)
1678	{
1679	stack->count += 1;
1680	if (stack->count > stack->allocated)
1681	{
1682	stack->allocated = stack->count*2;
1683	stack->iters = g_realloc (mem: stack->iters,
1684	n_bytes: stack->allocated * sizeof (GtkTextIter));
1685	}
1686	stack->iters[stack->count-1] = *iter;
1687	}
1688
1689	static gboolean
1690	iter_stack_pop (IterStack *stack,
1691	GtkTextIter *iter)
1692	{
1693	if (stack->count == 0)
1694	return FALSE;
1695	else
1696	{
1697	stack->count -= 1;
1698	*iter = stack->iters[stack->count];
1699	return TRUE;
1700	}
1701	}
1702
1703	static void
1704	iter_stack_free (IterStack *stack)
1705	{
1706	g_free (mem: stack->iters);
1707	g_slice_free (IterStack, stack);
1708	}
1709
1710	static void
1711	iter_stack_invert (IterStack *stack)
1712	{
1713	if (stack->count > 0)
1714	{
1715	guint i = 0;
1716	guint j = stack->count - 1;
1717	while (i < j)
1718	{
1719	GtkTextIter tmp;
1720
1721	tmp = stack->iters[i];
1722	stack->iters[i] = stack->iters[j];
1723	stack->iters[j] = tmp;
1724
1725	++i;
1726	--j;
1727	}
1728	}
1729	}
1730
1731	static void
1732	queue_tag_redisplay (GtkTextBTree *tree,
1733	GtkTextTag *tag,
1734	const GtkTextIter *start,
1735	const GtkTextIter *end)
1736	{
1737	if (_gtk_text_tag_affects_size (tag))
1738	{
1739	DV (g_print ("invalidating due to size-affecting tag (%s)\n", G_STRLOC));
1740	_gtk_text_btree_invalidate_region (tree, start, end, FALSE);
1741	}
1742	else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1743	{
1744	/* We only need to queue a redraw, not a relayout */
1745	redisplay_region (tree, start, end, FALSE);
1746	}
1747
1748	/* We don't need to do anything if the tag doesn't affect display */
1749	}
1750
1751	void
1752	_gtk_text_btree_tag (const GtkTextIter *start_orig,
1753	const GtkTextIter *end_orig,
1754	GtkTextTag *tag,
1755	gboolean add)
1756	{
1757	GtkTextLineSegment *seg, *prev;
1758	GtkTextLine *cleanupline;
1759	gboolean toggled_on;
1760	GtkTextLine *start_line;
1761	GtkTextLine *end_line;
1762	GtkTextIter iter;
1763	GtkTextIter start, end;
1764	GtkTextBTree *tree;
1765	IterStack *stack;
1766	GtkTextTagInfo *info;
1767
1768	g_return_if_fail (start_orig != NULL);
1769	g_return_if_fail (end_orig != NULL);
1770	g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1771	g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1772	_gtk_text_iter_get_btree (end_orig));
1773	g_return_if_fail (tag->priv->table == _gtk_text_iter_get_btree (start_orig)->table);
1774
1775	#if 0
1776	printf ("%s tag %s from %d to %d\n",
1777	add ? "Adding" : "Removing",
1778	tag->name,
1779	gtk_text_buffer_get_offset (start_orig),
1780	gtk_text_buffer_get_offset (end_orig));
1781	#endif
1782
1783	if (gtk_text_iter_equal (lhs: start_orig, rhs: end_orig))
1784	return;
1785
1786	start = *start_orig;
1787	end = *end_orig;
1788
1789	gtk_text_iter_order (first: &start, second: &end);
1790
1791	tree = _gtk_text_iter_get_btree (iter: &start);
1792
1793	queue_tag_redisplay (tree, tag, start: &start, end: &end);
1794
1795	info = gtk_text_btree_get_tag_info (tree, tag);
1796
1797	start_line = _gtk_text_iter_get_text_line (iter: &start);
1798	end_line = _gtk_text_iter_get_text_line (iter: &end);
1799
1800	/* Find all tag toggles in the region; we are going to delete them.
1801	We need to find them in advance, because
1802	forward_find_tag_toggle () won't work once we start playing around
1803	with the tree. */
1804	stack = iter_stack_new ();
1805	iter = start;
1806
1807	/* forward_to_tag_toggle() skips a toggle at the start iterator,
1808	* which is deliberate - we don't want to delete a toggle at the
1809	* start.
1810	*/
1811	while (gtk_text_iter_forward_to_tag_toggle (iter: &iter, tag))
1812	{
1813	if (gtk_text_iter_compare (lhs: &iter, rhs: &end) >= 0)
1814	break;
1815	else
1816	iter_stack_push (stack, iter: &iter);
1817	}
1818
1819	/* We need to traverse the toggles in order. */
1820	iter_stack_invert (stack);
1821
1822	/*
1823	* See whether the tag is present at the start of the range. If
1824	* the state doesn't already match what we want then add a toggle
1825	* there.
1826	*/
1827
1828	toggled_on = gtk_text_iter_has_tag (iter: &start, tag);
1829	if ( (add && !toggled_on) ||
1830	(!add && toggled_on) )
1831	{
1832	/* This could create a second toggle at the start position;
1833	cleanup_line () will remove it if so. */
1834	seg = _gtk_toggle_segment_new (info, on: add);
1835
1836	prev = gtk_text_line_segment_split (iter: &start);
1837	if (prev == NULL)
1838	{
1839	seg->next = start_line->segments;
1840	start_line->segments = seg;
1841	}
1842	else
1843	{
1844	seg->next = prev->next;
1845	prev->next = seg;
1846	}
1847
1848	/* cleanup_line adds the new toggle to the node counts. */
1849	#if 0
1850	printf ("added toggle at start\n");
1851	#endif
1852	/* we should probably call segments_changed, but in theory
1853	any still-cached segments in the iters we are about to
1854	use are still valid, since they're in front
1855	of this spot. */
1856	}
1857
1858	/*
1859	*
1860	* Scan the range of characters and delete any internal tag
1861	* transitions. Keep track of what the old state was at the end
1862	* of the range, and add a toggle there if it's needed.
1863	*
1864	*/
1865
1866	cleanupline = start_line;
1867	while (iter_stack_pop (stack, iter: &iter))
1868	{
1869	GtkTextLineSegment *indexable_seg;
1870	GtkTextLine *line;
1871
1872	line = _gtk_text_iter_get_text_line (iter: &iter);
1873	seg = _gtk_text_iter_get_any_segment (iter: &iter);
1874	indexable_seg = _gtk_text_iter_get_indexable_segment (iter: &iter);
1875
1876	g_assert (seg != NULL);
1877	g_assert (indexable_seg != NULL);
1878	g_assert (seg != indexable_seg);
1879
1880	prev = line->segments;
1881
1882	/* Find the segment that actually toggles this tag. */
1883	while (seg != indexable_seg)
1884	{
1885	g_assert (seg != NULL);
1886	g_assert (indexable_seg != NULL);
1887	g_assert (seg != indexable_seg);
1888
1889	if ( (seg->type == &gtk_text_toggle_on_type ||
1890	seg->type == &gtk_text_toggle_off_type) &&
1891	(seg->body.toggle.info == info) )
1892	break;
1893	else
1894	seg = seg->next;
1895	}
1896
1897	g_assert (seg != NULL);
1898	g_assert (indexable_seg != NULL);
1899
1900	g_assert (seg != indexable_seg); /* If this happens, then
1901	forward_to_tag_toggle was
1902	full of shit. */
1903	g_assert (seg->body.toggle.info->tag == tag);
1904
1905	/* If this happens, when previously tagging we didn't merge
1906	overlapping tags. */
1907	g_assert ( (toggled_on && seg->type == &gtk_text_toggle_off_type) ||
1908	(!toggled_on && seg->type == &gtk_text_toggle_on_type) );
1909
1910	toggled_on = !toggled_on;
1911
1912	#if 0
1913	printf ("deleting %s toggle\n",
1914	seg->type == &gtk_text_toggle_on_type ? "on" : "off");
1915	#endif
1916	/* Remove toggle segment from the list. */
1917	if (prev == seg)
1918	{
1919	line->segments = seg->next;
1920	}
1921	else
1922	{
1923	while (prev->next != seg)
1924	{
1925	prev = prev->next;
1926	}
1927	prev->next = seg->next;
1928	}
1929
1930	/* Inform iterators we've hosed them. This actually reflects a
1931	bit of inefficiency; if you have the same tag toggled on and
1932	off a lot in a single line, we keep having the rescan from
1933	the front of the line. Of course we have to do that to get
1934	"prev" anyway, but here we are doing it an additional
1935	time. FIXME */
1936	segments_changed (tree);
1937
1938	/* Update node counts */
1939	if (seg->body.toggle.inNodeCounts)
1940	{
1941	_gtk_change_node_toggle_count (node: line->parent,
1942	info, delta: -1);
1943	seg->body.toggle.inNodeCounts = FALSE;
1944	}
1945
1946	_gtk_toggle_segment_free (seg);
1947
1948	/* We only clean up lines when we're done with them, saves some
1949	gratuitous line-segment-traversals */
1950
1951	if (cleanupline != line)
1952	{
1953	cleanup_line (line: cleanupline);
1954	cleanupline = line;
1955	}
1956	}
1957
1958	iter_stack_free (stack);
1959
1960	/* toggled_on now reflects the toggle state _just before_ the
1961	end iterator. The end iterator could already have a toggle
1962	on or a toggle off. */
1963	if ( (add && !toggled_on) ||
1964	(!add && toggled_on) )
1965	{
1966	/* This could create a second toggle at the start position;
1967	cleanup_line () will remove it if so. */
1968
1969	seg = _gtk_toggle_segment_new (info, on: !add);
1970
1971	prev = gtk_text_line_segment_split (iter: &end);
1972	if (prev == NULL)
1973	{
1974	seg->next = end_line->segments;
1975	end_line->segments = seg;
1976	}
1977	else
1978	{
1979	seg->next = prev->next;
1980	prev->next = seg;
1981	}
1982	/* cleanup_line adds the new toggle to the node counts. */
1983	g_assert (seg->body.toggle.inNodeCounts == FALSE);
1984	#if 0
1985	printf ("added toggle at end\n");
1986	#endif
1987	}
1988
1989	/*
1990	* Cleanup cleanupline and the last line of the range, if
1991	* these are different.
1992	*/
1993
1994	cleanup_line (line: cleanupline);
1995	if (cleanupline != end_line)
1996	{
1997	cleanup_line (line: end_line);
1998	}
1999
2000	segments_changed (tree);
2001
2002	queue_tag_redisplay (tree, tag, start: &start, end: &end);
2003
2004	#ifdef G_ENABLE_DEBUG
2005	if (GTK_DEBUG_CHECK (TEXT))
2006	_gtk_text_btree_check (tree);
2007	#endif
2008	}
2009
2010
2011	/*
2012	* "Getters"
2013	*/
2014
2015	static GtkTextLine*
2016	get_line_internal (GtkTextBTree *tree,
2017	int line_number,
2018	int *real_line_number,
2019	gboolean include_last)
2020	{
2021	GtkTextBTreeNode *node;
2022	GtkTextLine *line;
2023	int lines_left;
2024	int line_count;
2025
2026	line_count = _gtk_text_btree_line_count (tree);
2027	if (!include_last)
2028	line_count -= 1;
2029
2030	if (line_number < 0)
2031	{
2032	line_number = line_count;
2033	}
2034	else if (line_number > line_count)
2035	{
2036	line_number = line_count;
2037	}
2038
2039	if (real_line_number)
2040	*real_line_number = line_number;
2041
2042	node = tree->root_node;
2043	lines_left = line_number;
2044
2045	/*
2046	* Work down through levels of the tree until a GtkTextBTreeNode is found at
2047	* level 0.
2048	*/
2049
2050	while (node->level != 0)
2051	{
2052	for (node = node->children.node;
2053	node->num_lines <= lines_left;
2054	node = node->next)
2055	{
2056	#if 0
2057	if (node == NULL)
2058	{
2059	g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
2060	}
2061	#endif
2062	lines_left -= node->num_lines;
2063	}
2064	}
2065
2066	/*
2067	* Work through the lines attached to the level-0 GtkTextBTreeNode.
2068	*/
2069
2070	for (line = node->children.line; lines_left > 0;
2071	line = line->next)
2072	{
2073	#if 0
2074	if (line == NULL)
2075	{
2076	g_error ("gtk_text_btree_find_line ran out of lines");
2077	}
2078	#endif
2079	lines_left -= 1;
2080	}
2081	return line;
2082	}
2083
2084	GtkTextLine*
2085	_gtk_text_btree_get_end_iter_line (GtkTextBTree *tree)
2086	{
2087	return
2088	_gtk_text_btree_get_line (tree,
2089	line_number: _gtk_text_btree_line_count (tree) - 1,
2090	NULL);
2091	}
2092
2093	GtkTextLine*
2094	_gtk_text_btree_get_line (GtkTextBTree *tree,
2095	int line_number,
2096	int *real_line_number)
2097	{
2098	return get_line_internal (tree, line_number, real_line_number, TRUE);
2099	}
2100
2101	GtkTextLine*
2102	_gtk_text_btree_get_line_no_last (GtkTextBTree *tree,
2103	int line_number,
2104	int *real_line_number)
2105	{
2106	return get_line_internal (tree, line_number, real_line_number, FALSE);
2107	}
2108
2109	GtkTextLine*
2110	_gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
2111	int char_index,
2112	int *line_start_index,
2113	int *real_char_index)
2114	{
2115	GtkTextBTreeNode *node;
2116	GtkTextLine *line;
2117	GtkTextLineSegment *seg;
2118	int chars_left;
2119	int chars_in_line;
2120
2121	node = tree->root_node;
2122
2123	/* Clamp to valid indexes (-1 is magic for "highest index"),
2124	* node->num_chars includes the two newlines that aren't really
2125	* in the buffer.
2126	*/
2127	if (char_index < 0 || char_index >= (node->num_chars - 1))
2128	{
2129	char_index = node->num_chars - 2;
2130	}
2131
2132	*real_char_index = char_index;
2133
2134	/*
2135	* Work down through levels of the tree until a GtkTextBTreeNode is found at
2136	* level 0.
2137	*/
2138
2139	chars_left = char_index;
2140	while (node->level != 0)
2141	{
2142	for (node = node->children.node;
2143	chars_left >= node->num_chars;
2144	node = node->next)
2145	{
2146	chars_left -= node->num_chars;
2147
2148	g_assert (chars_left >= 0);
2149	}
2150	}
2151
2152	if (chars_left == 0)
2153	{
2154	/* Start of a line */
2155
2156	*line_start_index = char_index;
2157	return node->children.line;
2158	}
2159
2160	/*
2161	* Work through the lines attached to the level-0 GtkTextBTreeNode.
2162	*/
2163
2164	chars_in_line = 0;
2165	seg = NULL;
2166	for (line = node->children.line; line != NULL; line = line->next)
2167	{
2168	seg = line->segments;
2169	while (seg != NULL)
2170	{
2171	if (chars_in_line + seg->char_count > chars_left)
2172	goto found; /* found our line/segment */
2173
2174	chars_in_line += seg->char_count;
2175
2176	seg = seg->next;
2177	}
2178
2179	chars_left -= chars_in_line;
2180
2181	chars_in_line = 0;
2182	seg = NULL;
2183	}
2184
2185	found:
2186
2187	g_assert (line != NULL); /* hosage, ran out of lines */
2188	g_assert (seg != NULL);
2189
2190	*line_start_index = char_index - chars_left;
2191	return line;
2192	}
2193
2194	/* It returns an array sorted by tags priority, ready to pass to
2195	* _gtk_text_attributes_fill_from_tags() */
2196	GPtrArray *
2197	_gtk_text_btree_get_tags (const GtkTextIter *iter)
2198	{
2199	GtkTextBTreeNode *node;
2200	GtkTextLine *siblingline;
2201	GtkTextLineSegment *seg;
2202	int src, dst, index;
2203	TagInfo tagInfo;
2204	GtkTextLine *line;
2205	int byte_index;
2206
2207	#define NUM_TAG_INFOS 10
2208
2209	line = _gtk_text_iter_get_text_line (iter);
2210	byte_index = gtk_text_iter_get_line_index (iter);
2211
2212	tagInfo.tags = g_ptr_array_sized_new (NUM_TAG_INFOS);
2213	tagInfo.counts = g_array_new (FALSE, FALSE, element_size: sizeof (int));
2214
2215	/*
2216	* Record tag toggles within the line of indexPtr but preceding
2217	* indexPtr. Note that if this loop segfaults, your
2218	* byte_index probably points past the sum of all
2219	* seg->byte_count */
2220
2221	for (index = 0, seg = line->segments;
2222	(index + seg->byte_count) <= byte_index;
2223	index += seg->byte_count, seg = seg->next)
2224	{
2225	if ((seg->type == &gtk_text_toggle_on_type)
2226	|| (seg->type == &gtk_text_toggle_off_type))
2227	{
2228	inc_count (tag: seg->body.toggle.info->tag, inc: 1, tagInfoPtr: &tagInfo);
2229	}
2230	}
2231
2232	/*
2233	* Record toggles for tags in lines that are predecessors of
2234	* line but under the same level-0 GtkTextBTreeNode.
2235	*/
2236
2237	for (siblingline = line->parent->children.line;
2238	siblingline != line;
2239	siblingline = siblingline->next)
2240	{
2241	for (seg = siblingline->segments; seg != NULL;
2242	seg = seg->next)
2243	{
2244	if ((seg->type == &gtk_text_toggle_on_type)
2245	|| (seg->type == &gtk_text_toggle_off_type))
2246	{
2247	inc_count (tag: seg->body.toggle.info->tag, inc: 1, tagInfoPtr: &tagInfo);
2248	}
2249	}
2250	}
2251
2252	/*
2253	* For each GtkTextBTreeNode in the ancestry of this line, record tag
2254	* toggles for all siblings that precede that GtkTextBTreeNode.
2255	*/
2256
2257	for (node = line->parent; node->parent != NULL;
2258	node = node->parent)
2259	{
2260	GtkTextBTreeNode *siblingPtr;
2261	Summary *summary;
2262
2263	for (siblingPtr = node->parent->children.node;
2264	siblingPtr != node; siblingPtr = siblingPtr->next)
2265	{
2266	for (summary = siblingPtr->summary; summary != NULL;
2267	summary = summary->next)
2268	{
2269	if (summary->toggle_count & 1)
2270	{
2271	inc_count (tag: summary->info->tag, inc: summary->toggle_count,
2272	tagInfoPtr: &tagInfo);
2273	}
2274	}
2275	}
2276	}
2277
2278	/*
2279	* Go through the tag information and squash out all of the tags
2280	* that have even toggle counts (these tags exist before the point
2281	* of interest, but not at the desired character itself).
2282	*/
2283
2284	for (src = 0, dst = 0; src < tagInfo.tags->len; src++)
2285	{
2286	if (g_array_index (tagInfo.counts, int, src) & 1)
2287	{
2288	g_assert (GTK_IS_TEXT_TAG (g_ptr_array_index (tagInfo.tags, src)));
2289	g_ptr_array_index (tagInfo.tags, dst) = g_ptr_array_index (tagInfo.tags, src);
2290	dst++;
2291	}
2292	}
2293
2294	g_ptr_array_set_size (array: tagInfo.tags, length: dst);
2295	g_array_unref (array: tagInfo.counts);
2296	if (dst == 0)
2297	{
2298	g_ptr_array_unref (array: tagInfo.tags);
2299	return NULL;
2300	}
2301
2302	/* Sort tags in ascending order of priority */
2303	_gtk_text_tag_array_sort (tags: tagInfo.tags);
2304
2305	return tagInfo.tags;
2306	}
2307
2308	static void
2309	copy_segment (GString *string,
2310	gboolean include_hidden,
2311	gboolean include_nonchars,
2312	const GtkTextIter *start,
2313	const GtkTextIter *end)
2314	{
2315	GtkTextLineSegment *end_seg;
2316	GtkTextLineSegment *seg;
2317
2318	if (gtk_text_iter_equal (lhs: start, rhs: end))
2319	return;
2320
2321	seg = _gtk_text_iter_get_indexable_segment (iter: start);
2322	end_seg = _gtk_text_iter_get_indexable_segment (iter: end);
2323
2324	if (seg->type == &gtk_text_char_type)
2325	{
2326	gboolean copy = TRUE;
2327	int copy_bytes = 0;
2328	int copy_start = 0;
2329
2330	/* Don't copy if we're invisible; segments are invisible/not
2331	as a whole, no need to check each char */
2332	if (!include_hidden &&
2333	_gtk_text_btree_char_is_invisible (iter: start))
2334	{
2335	copy = FALSE;
2336	/* printf (" <invisible>\n"); */
2337	}
2338
2339	copy_start = _gtk_text_iter_get_segment_byte (iter: start);
2340
2341	if (seg == end_seg)
2342	{
2343	/* End is in the same segment; need to copy fewer bytes. */
2344	int end_byte = _gtk_text_iter_get_segment_byte (iter: end);
2345
2346	copy_bytes = end_byte - copy_start;
2347	}
2348	else
2349	copy_bytes = seg->byte_count - copy_start;
2350
2351	g_assert (copy_bytes != 0); /* Due to iter equality check at
2352	front of this function. */
2353
2354	if (copy)
2355	{
2356	g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2357
2358	g_string_append_len (string,
2359	val: seg->body.chars + copy_start,
2360	len: copy_bytes);
2361	}
2362
2363	/* printf (" :%s\n", string->str); */
2364	}
2365	else if (seg->type == &gtk_text_paintable_type)
2366	{
2367	gboolean copy = TRUE;
2368
2369	if (!include_nonchars)
2370	{
2371	copy = FALSE;
2372	}
2373	else if (!include_hidden &&
2374	_gtk_text_btree_char_is_invisible (iter: start))
2375	{
2376	copy = FALSE;
2377	}
2378
2379	if (copy)
2380	{
2381	g_string_append_len (string,
2382	val: _gtk_text_unknown_char_utf8,
2383	GTK_TEXT_UNKNOWN_CHAR_UTF8_LEN);
2384	}
2385	}
2386	else if (seg->type == &gtk_text_child_type)
2387	{
2388	gboolean copy = TRUE;
2389	if (!include_nonchars &&
2390	g_strcmp0 (str1: _gtk_text_unknown_char_utf8, str2: gtk_text_child_anchor_get_replacement (anchor: seg->body.child.obj)) == 0)
2391	{
2392	copy = FALSE;
2393	}
2394	else if (!include_hidden &&
2395	_gtk_text_btree_char_is_invisible (iter: start))
2396	{
2397	copy = FALSE;
2398	}
2399
2400	if (copy)
2401	{
2402	g_string_append_len (string,
2403	val: gtk_text_child_anchor_get_replacement (anchor: seg->body.child.obj),
2404	len: seg->byte_count);
2405	}
2406	}
2407	}
2408
2409	char *
2410	_gtk_text_btree_get_text (const GtkTextIter *start_orig,
2411	const GtkTextIter *end_orig,
2412	gboolean include_hidden,
2413	gboolean include_nonchars)
2414	{
2415	GtkTextLineSegment *seg;
2416	GtkTextLineSegment *end_seg;
2417	GString *retval;
2418	char *str;
2419	GtkTextIter iter;
2420	GtkTextIter start;
2421	GtkTextIter end;
2422
2423	g_return_val_if_fail (start_orig != NULL, NULL);
2424	g_return_val_if_fail (end_orig != NULL, NULL);
2425	g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2426	_gtk_text_iter_get_btree (end_orig), NULL);
2427
2428	start = *start_orig;
2429	end = *end_orig;
2430
2431	gtk_text_iter_order (first: &start, second: &end);
2432
2433	retval = g_string_new (NULL);
2434
2435	end_seg = _gtk_text_iter_get_indexable_segment (iter: &end);
2436	iter = start;
2437	seg = _gtk_text_iter_get_indexable_segment (iter: &iter);
2438	while (seg != end_seg)
2439	{
2440	copy_segment (string: retval, include_hidden, include_nonchars,
2441	start: &iter, end: &end);
2442
2443	_gtk_text_iter_forward_indexable_segment (iter: &iter);
2444
2445	seg = _gtk_text_iter_get_indexable_segment (iter: &iter);
2446	}
2447
2448	copy_segment (string: retval, include_hidden, include_nonchars, start: &iter, end: &end);
2449
2450	str = retval->str;
2451	g_string_free (string: retval, FALSE);
2452	return str;
2453	}
2454
2455	int
2456	_gtk_text_btree_line_count (GtkTextBTree *tree)
2457	{
2458	/* Subtract bogus line at the end; we return a count
2459	of usable lines. */
2460	return tree->root_node->num_lines - 1;
2461	}
2462
2463	int
2464	_gtk_text_btree_char_count (GtkTextBTree *tree)
2465	{
2466	/* Exclude newline in bogus last line and the
2467	* one in the last line that is after the end iterator
2468	*/
2469	return tree->root_node->num_chars - 2;
2470	}
2471
2472	gboolean
2473	_gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2474	{
2475	gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2476	int *tagCnts;
2477	GtkTextTag **tags;
2478	int numTags;
2479	GtkTextBTreeNode *node;
2480	GtkTextLine *siblingline;
2481	GtkTextLineSegment *seg;
2482	GtkTextTag *tag;
2483	int i, index;
2484	GtkTextLine *line;
2485	GtkTextBTree *tree;
2486	int byte_index;
2487
2488	tree = _gtk_text_iter_get_btree (iter);
2489
2490	/* Short-circuit if we've never seen a visibility tag within the
2491	* tag table (meaning everything must be visible).
2492	*/
2493	if G_LIKELY (!_gtk_text_tag_table_affects_visibility (tree->table))
2494	return FALSE;
2495
2496	line = _gtk_text_iter_get_text_line (iter);
2497
2498	byte_index = gtk_text_iter_get_line_index (iter);
2499
2500	numTags = gtk_text_tag_table_get_size (table: tree->table);
2501
2502	tagCnts = g_alloca (sizeof (int) * numTags);
2503	tags = g_alloca (sizeof (GtkTextTag *) * numTags);
2504
2505	memset (s: tagCnts, c: 0, n: sizeof (int) * numTags);
2506
2507	/*
2508	* Record tag toggles within the line of indexPtr but preceding
2509	* indexPtr.
2510	*/
2511
2512	for (index = 0, seg = line->segments;
2513	(index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2514	index += seg->byte_count, seg = seg->next)
2515	{
2516	if ((seg->type == &gtk_text_toggle_on_type)
2517	|| (seg->type == &gtk_text_toggle_off_type))
2518	{
2519	tag = seg->body.toggle.info->tag;
2520	if (tag->priv->invisible_set)
2521	{
2522	tags[tag->priv->priority] = tag;
2523	tagCnts[tag->priv->priority]++;
2524	}
2525	}
2526	}
2527
2528	/*
2529	* Record toggles for tags in lines that are predecessors of
2530	* line but under the same level-0 GtkTextBTreeNode.
2531	*/
2532
2533	for (siblingline = line->parent->children.line;
2534	siblingline != line;
2535	siblingline = siblingline->next)
2536	{
2537	for (seg = siblingline->segments; seg != NULL;
2538	seg = seg->next)
2539	{
2540	if ((seg->type == &gtk_text_toggle_on_type)
2541	|| (seg->type == &gtk_text_toggle_off_type))
2542	{
2543	tag = seg->body.toggle.info->tag;
2544	if (tag->priv->invisible_set)
2545	{
2546	tags[tag->priv->priority] = tag;
2547	tagCnts[tag->priv->priority]++;
2548	}
2549	}
2550	}
2551	}
2552
2553	/*
2554	* For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2555	* for all siblings that precede that GtkTextBTreeNode.
2556	*/
2557
2558	for (node = line->parent; node->parent != NULL;
2559	node = node->parent)
2560	{
2561	GtkTextBTreeNode *siblingPtr;
2562	Summary *summary;
2563
2564	for (siblingPtr = node->parent->children.node;
2565	siblingPtr != node; siblingPtr = siblingPtr->next)
2566	{
2567	for (summary = siblingPtr->summary; summary != NULL;
2568	summary = summary->next)
2569	{
2570	if (summary->toggle_count & 1)
2571	{
2572	tag = summary->info->tag;
2573	if (tag->priv->invisible_set)
2574	{
2575	tags[tag->priv->priority] = tag;
2576	tagCnts[tag->priv->priority] += summary->toggle_count;
2577	}
2578	}
2579	}
2580	}
2581	}
2582
2583	/*
2584	* Now traverse from highest priority to lowest,
2585	* take invisible value from first odd count (= on)
2586	*/
2587
2588	for (i = numTags-1; i >=0; i--)
2589	{
2590	if (tagCnts[i] & 1)
2591	{
2592	/* FIXME not sure this should be if 0 */
2593	#if 0
2594	#ifndef ALWAYS_SHOW_SELECTION
2595	/* who would make the selection invisible? */
2596	if ((tag == tkxt->seltag)
2597	&& !(tkxt->flags & GOT_FOCUS))
2598	{
2599	continue;
2600	}
2601	#endif
2602	#endif
2603	invisible = tags[i]->priv->values->invisible;
2604	break;
2605	}
2606	}
2607
2608	return invisible;
2609	}
2610
2611
2612	/*
2613	* Manipulate marks
2614	*/
2615
2616	static void
2617	redisplay_region (GtkTextBTree *tree,
2618	const GtkTextIter *start,
2619	const GtkTextIter *end,
2620	gboolean cursors_only)
2621	{
2622	BTreeView *view;
2623	GtkTextLine *start_line, *end_line;
2624
2625	if (gtk_text_iter_compare (lhs: start, rhs: end) > 0)
2626	{
2627	const GtkTextIter *tmp = start;
2628	start = end;
2629	end = tmp;
2630	}
2631
2632	start_line = _gtk_text_iter_get_text_line (iter: start);
2633	end_line = _gtk_text_iter_get_text_line (iter: end);
2634
2635	view = tree->views;
2636	while (view != NULL)
2637	{
2638	int start_y, end_y;
2639	GtkTextLineData *ld;
2640
2641	start_y = _gtk_text_btree_find_line_top (tree, target_line: start_line, view_id: view->view_id);
2642
2643	if (end_line == start_line)
2644	end_y = start_y;
2645	else
2646	end_y = _gtk_text_btree_find_line_top (tree, target_line: end_line, view_id: view->view_id);
2647
2648	ld = _gtk_text_line_get_data (line: start_line, view_id: view->view_id);
2649	if (ld)
2650	start_y -= ld->top_ink;
2651
2652	ld = _gtk_text_line_get_data (line: end_line, view_id: view->view_id);
2653	if (ld)
2654	end_y += ld->height + ld->bottom_ink;
2655
2656	if (cursors_only)
2657	gtk_text_layout_cursors_changed (layout: view->layout, y: start_y,
2658	old_height: end_y - start_y,
2659	new_height: end_y - start_y);
2660	else
2661	gtk_text_layout_changed (layout: view->layout, y: start_y,
2662	old_height: end_y - start_y,
2663	new_height: end_y - start_y);
2664
2665	view = view->next;
2666	}
2667	}
2668
2669	static void
2670	redisplay_mark (GtkTextLineSegment *mark)
2671	{
2672	GtkTextIter iter;
2673	GtkTextIter end;
2674	gboolean cursor_only;
2675
2676	_gtk_text_btree_get_iter_at_mark (tree: mark->body.mark.tree,
2677	iter: &iter,
2678	mark: mark->body.mark.obj);
2679
2680	end = iter;
2681	gtk_text_iter_forward_char (iter: &end);
2682
2683	DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2684	cursor_only = mark == mark->body.mark.tree->insert_mark->segment;
2685	_gtk_text_btree_invalidate_region (tree: mark->body.mark.tree, start: &iter, end: &end, cursors_only: cursor_only);
2686	}
2687
2688	static void
2689	redisplay_mark_if_visible (GtkTextLineSegment *mark)
2690	{
2691	if (!mark->body.mark.visible)
2692	return;
2693	else
2694	redisplay_mark (mark);
2695	}
2696
2697	static void
2698	ensure_not_off_end (GtkTextBTree *tree,
2699	GtkTextLineSegment *mark,
2700	GtkTextIter *iter)
2701	{
2702	if (gtk_text_iter_get_line (iter) == _gtk_text_btree_line_count (tree))
2703	gtk_text_iter_backward_char (iter);
2704	}
2705
2706	static GtkTextLineSegment*
2707	real_set_mark (GtkTextBTree *tree,
2708	GtkTextMark *existing_mark,
2709	const char *name,
2710	gboolean left_gravity,
2711	const GtkTextIter *where,
2712	gboolean should_exist,
2713	gboolean redraw_selections)
2714	{
2715	GtkTextLineSegment *mark;
2716	GtkTextIter iter;
2717
2718	g_return_val_if_fail (tree != NULL, NULL);
2719	g_return_val_if_fail (where != NULL, NULL);
2720	g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2721
2722	if (existing_mark)
2723	{
2724	if (gtk_text_mark_get_buffer (mark: existing_mark) != NULL)
2725	mark = existing_mark->segment;
2726	else
2727	mark = NULL;
2728	}
2729	else if (name != NULL)
2730	mark = g_hash_table_lookup (hash_table: tree->mark_table,
2731	key: name);
2732	else
2733	mark = NULL;
2734
2735	if (should_exist && mark == NULL)
2736	{
2737	g_warning ("No mark '%s' exists!", name);
2738	return NULL;
2739	}
2740
2741	/* OK if !should_exist and it does already exist, in that case
2742	* we just move it.
2743	*/
2744
2745	iter = *where;
2746
2747	#ifdef G_ENABLE_DEBUG
2748	if (GTK_DEBUG_CHECK (TEXT))
2749	_gtk_text_iter_check (iter: &iter);
2750	#endif
2751
2752	if (mark != NULL)
2753	{
2754	if (redraw_selections &&
2755	(mark == tree->insert_mark->segment ||
2756	mark == tree->selection_bound_mark->segment))
2757	{
2758	GtkTextIter old_pos;
2759
2760	_gtk_text_btree_get_iter_at_mark (tree, iter: &old_pos,
2761	mark: mark->body.mark.obj);
2762	redisplay_region (tree, start: &old_pos, end: where, TRUE);
2763	}
2764
2765	/*
2766	* don't let visible marks be after the final newline of the
2767	* file.
2768	*/
2769
2770	if (mark->body.mark.visible)
2771	{
2772	ensure_not_off_end (tree, mark, iter: &iter);
2773	}
2774
2775	/* Redraw the mark's old location. */
2776	redisplay_mark_if_visible (mark);
2777
2778	/* Unlink mark from its current location.
2779	This could hose our iterator... */
2780	gtk_text_btree_unlink_segment (tree, seg: mark,
2781	line: mark->body.mark.line);
2782	mark->body.mark.line = _gtk_text_iter_get_text_line (iter: &iter);
2783	g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2784
2785	segments_changed (tree); /* make sure the iterator recomputes its
2786	segment */
2787	}
2788	else
2789	{
2790	if (existing_mark)
2791	g_object_ref (existing_mark);
2792	else
2793	existing_mark = gtk_text_mark_new (name, left_gravity);
2794
2795	mark = existing_mark->segment;
2796	_gtk_mark_segment_set_tree (mark, tree);
2797
2798	mark->body.mark.line = _gtk_text_iter_get_text_line (iter: &iter);
2799
2800	if (mark->body.mark.name)
2801	g_hash_table_insert (hash_table: tree->mark_table,
2802	key: mark->body.mark.name,
2803	value: mark);
2804	}
2805
2806	#ifdef G_ENABLE_DEBUG
2807	if (GTK_DEBUG_CHECK (TEXT))
2808	_gtk_text_iter_check (iter: &iter);
2809	#endif
2810
2811	/* Link mark into new location */
2812	gtk_text_btree_link_segment (seg: mark, iter: &iter);
2813
2814	/* Invalidate some iterators. */
2815	segments_changed (tree);
2816
2817	/*
2818	* update the screen at the mark's new location.
2819	*/
2820
2821	redisplay_mark_if_visible (mark);
2822
2823	#ifdef G_ENABLE_DEBUG
2824	if (GTK_DEBUG_CHECK (TEXT))
2825	{
2826	_gtk_text_iter_check (iter: &iter);
2827	_gtk_text_btree_check (tree);
2828	}
2829	#endif
2830
2831	return mark;
2832	}
2833
2834
2835	GtkTextMark*
2836	_gtk_text_btree_set_mark (GtkTextBTree *tree,
2837	GtkTextMark *existing_mark,
2838	const char *name,
2839	gboolean left_gravity,
2840	const GtkTextIter *iter,
2841	gboolean should_exist)
2842	{
2843	GtkTextLineSegment *seg;
2844
2845	seg = real_set_mark (tree, existing_mark,
2846	name, left_gravity, where: iter, should_exist,
2847	TRUE);
2848	g_assert (seg);
2849
2850	return seg->body.mark.obj;
2851	}
2852
2853	gboolean
2854	_gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2855	GtkTextIter *start,
2856	GtkTextIter *end)
2857	{
2858	GtkTextIter tmp_start, tmp_end;
2859
2860	_gtk_text_btree_get_iter_at_mark (tree, iter: &tmp_start,
2861	mark: tree->insert_mark);
2862	_gtk_text_btree_get_iter_at_mark (tree, iter: &tmp_end,
2863	mark: tree->selection_bound_mark);
2864
2865	if (gtk_text_iter_equal (lhs: &tmp_start, rhs: &tmp_end))
2866	{
2867	if (start)
2868	*start = tmp_start;
2869
2870	if (end)
2871	*end = tmp_end;
2872
2873	return FALSE;
2874	}
2875	else
2876	{
2877	gtk_text_iter_order (first: &tmp_start, second: &tmp_end);
2878
2879	if (start)
2880	*start = tmp_start;
2881
2882	if (end)
2883	*end = tmp_end;
2884
2885	return TRUE;
2886	}
2887	}
2888
2889	void
2890	_gtk_text_btree_place_cursor (GtkTextBTree *tree,
2891	const GtkTextIter *iter)
2892	{
2893	_gtk_text_btree_select_range (tree, ins: iter, bound: iter);
2894	}
2895
2896	void
2897	_gtk_text_btree_select_range (GtkTextBTree *tree,
2898	const GtkTextIter *ins,
2899	const GtkTextIter *bound)
2900	{
2901	GtkTextIter old_ins, old_bound;
2902
2903	_gtk_text_btree_get_iter_at_mark (tree, iter: &old_ins,
2904	mark: tree->insert_mark);
2905	_gtk_text_btree_get_iter_at_mark (tree, iter: &old_bound,
2906	mark: tree->selection_bound_mark);
2907
2908	/* Check if it's no-op since gtk_text_buffer_place_cursor()
2909	* also calls this, and this will redraw the cursor line. */
2910	if (!gtk_text_iter_equal (lhs: &old_ins, rhs: ins) ||
2911	!gtk_text_iter_equal (lhs: &old_bound, rhs: bound))
2912	{
2913	redisplay_region (tree, start: &old_ins, end: &old_bound, TRUE);
2914
2915	/* Move insert AND selection_bound before we redisplay */
2916	real_set_mark (tree, existing_mark: tree->insert_mark,
2917	name: "insert", FALSE, where: ins, TRUE, FALSE);
2918	real_set_mark (tree, existing_mark: tree->selection_bound_mark,
2919	name: "selection_bound", FALSE, where: bound, TRUE, FALSE);
2920
2921	redisplay_region (tree, start: ins, end: bound, TRUE);
2922	}
2923	}
2924
2925
2926	void
2927	_gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2928	const char *name)
2929	{
2930	GtkTextMark *mark;
2931
2932	g_return_if_fail (tree != NULL);
2933	g_return_if_fail (name != NULL);
2934
2935	mark = g_hash_table_lookup (hash_table: tree->mark_table,
2936	key: name);
2937
2938	_gtk_text_btree_remove_mark (tree, segment: mark);
2939	}
2940
2941	void
2942	_gtk_text_btree_release_mark_segment (GtkTextBTree *tree,
2943	GtkTextLineSegment *segment)
2944	{
2945
2946	if (segment->body.mark.name)
2947	g_hash_table_remove (hash_table: tree->mark_table, key: segment->body.mark.name);
2948
2949	segment->body.mark.tree = NULL;
2950	segment->body.mark.line = NULL;
2951
2952	/* Remove the ref on the mark, which frees segment as a side effect
2953	* if this is the last reference.
2954	*/
2955	g_object_unref (object: segment->body.mark.obj);
2956	}
2957
2958	void
2959	_gtk_text_btree_remove_mark (GtkTextBTree *tree,
2960	GtkTextMark *mark)
2961	{
2962	GtkTextLineSegment *segment;
2963
2964	g_return_if_fail (mark != NULL);
2965	g_return_if_fail (tree != NULL);
2966
2967	segment = mark->segment;
2968
2969	if (segment->body.mark.not_deleteable)
2970	{
2971	g_warning ("Can't delete special mark '%s'", segment->body.mark.name);
2972	return;
2973	}
2974
2975	/* This calls cleanup_line and segments_changed */
2976	gtk_text_btree_unlink_segment (tree, seg: segment, line: segment->body.mark.line);
2977
2978	_gtk_text_btree_release_mark_segment (tree, segment);
2979	}
2980
2981	gboolean
2982	_gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2983	GtkTextMark *segment)
2984	{
2985	return segment == tree->insert_mark;
2986	}
2987
2988	gboolean
2989	_gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2990	GtkTextMark *segment)
2991	{
2992	return segment == tree->selection_bound_mark;
2993	}
2994
2995	GtkTextMark *
2996	_gtk_text_btree_get_insert (GtkTextBTree *tree)
2997	{
2998	return tree->insert_mark;
2999	}
3000
3001	GtkTextMark *
3002	_gtk_text_btree_get_selection_bound (GtkTextBTree *tree)
3003	{
3004	return tree->selection_bound_mark;
3005	}
3006
3007	GtkTextMark*
3008	_gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
3009	const char *name)
3010	{
3011	GtkTextLineSegment *seg;
3012
3013	g_return_val_if_fail (tree != NULL, NULL);
3014	g_return_val_if_fail (name != NULL, NULL);
3015
3016	seg = g_hash_table_lookup (hash_table: tree->mark_table, key: name);
3017
3018	return seg ? seg->body.mark.obj : NULL;
3019	}
3020
3021	/**
3022	* gtk_text_mark_set_visible:
3023	* @mark: a GtkTextMark
3024	* @setting: visibility of mark
3025	*
3026	* Sets the visibility of @mark.
3027	*
3028	* The insertion point is normally visible, i.e. you can see it as
3029	* a vertical bar. Also, the text widget uses a visible mark to
3030	* indicate where a drop will occur when dragging-and-dropping text.
3031	* Most other marks are not visible.
3032	*
3033	* Marks are not visible by default.
3034	*/
3035	void
3036	gtk_text_mark_set_visible (GtkTextMark *mark,
3037	gboolean setting)
3038	{
3039	GtkTextLineSegment *seg;
3040
3041	g_return_if_fail (mark != NULL);
3042
3043	seg = mark->segment;
3044
3045	if (seg->body.mark.visible == setting)
3046	return;
3047	else
3048	{
3049	seg->body.mark.visible = setting;
3050
3051	if (seg->body.mark.tree)
3052	redisplay_mark (mark: seg);
3053	}
3054	}
3055
3056	GtkTextLine*
3057	_gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
3058	GtkTextTag *tag)
3059	{
3060	GtkTextBTreeNode *node;
3061	GtkTextTagInfo *info;
3062
3063	g_return_val_if_fail (tree != NULL, NULL);
3064
3065	if (tag != NULL)
3066	{
3067	info = gtk_text_btree_get_existing_tag_info (tree, tag);
3068
3069	if (info == NULL)
3070	return NULL;
3071
3072	if (info->tag_root == NULL)
3073	return NULL;
3074
3075	node = info->tag_root;
3076
3077	/* We know the tag root has instances of the given
3078	tag below it */
3079
3080	continue_outer_loop:
3081	g_assert (node != NULL);
3082	while (node->level > 0)
3083	{
3084	g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3085	node = node->children.node;
3086	while (node != NULL)
3087	{
3088	if (gtk_text_btree_node_has_tag (node, tag))
3089	goto continue_outer_loop;
3090
3091	node = node->next;
3092	}
3093	g_assert (node != NULL);
3094	}
3095
3096	g_assert (node != NULL); /* The tag summaries said some node had
3097	tag toggles... */
3098
3099	g_assert (node->level == 0);
3100
3101	return node->children.line;
3102	}
3103	else
3104	{
3105	/* Looking for any tag at all (tag == NULL).
3106	Unfortunately this can't be done in a simple and efficient way
3107	right now; so I'm just going to return the
3108	first line in the btree. FIXME */
3109	return _gtk_text_btree_get_line (tree, line_number: 0, NULL);
3110	}
3111	}
3112
3113	GtkTextLine*
3114	_gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3115	GtkTextTag *tag)
3116	{
3117	GtkTextBTreeNode *node;
3118	GtkTextBTreeNode *last_node;
3119	GtkTextLine *line;
3120	GtkTextTagInfo *info;
3121
3122	g_return_val_if_fail (tree != NULL, NULL);
3123
3124	if (tag != NULL)
3125	{
3126	info = gtk_text_btree_get_existing_tag_info (tree, tag);
3127
3128	if (info == NULL || info->tag_root == NULL)
3129	return NULL;
3130
3131	node = info->tag_root;
3132	/* We know the tag root has instances of the given
3133	tag below it */
3134
3135	while (node->level > 0)
3136	{
3137	last_node = NULL;
3138	node = node->children.node;
3139	while (node != NULL)
3140	{
3141	if (gtk_text_btree_node_has_tag (node, tag))
3142	last_node = node;
3143	node = node->next;
3144	}
3145
3146	node = last_node;
3147	g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3148	}
3149
3150	g_assert (node != NULL); /* The tag summaries said some node had
3151	tag toggles... */
3152
3153	g_assert (node->level == 0);
3154
3155	/* Find the last line in this node */
3156	line = node->children.line;
3157	while (line->next != NULL)
3158	line = line->next;
3159
3160	return line;
3161	}
3162	else
3163	{
3164	/* This search can't be done efficiently at the moment,
3165	at least not without complexity.
3166	So, we just return the last line.
3167	*/
3168	return _gtk_text_btree_get_end_iter_line (tree);
3169	}
3170	}
3171
3172
3173	/*
3174	* Lines
3175	*/
3176
3177	int
3178	_gtk_text_line_get_number (GtkTextLine *line)
3179	{
3180	GtkTextLine *line2;
3181	GtkTextBTreeNode *node, *parent, *node2;
3182	int index;
3183
3184	/*
3185	* First count how many lines precede this one in its level-0
3186	* GtkTextBTreeNode.
3187	*/
3188
3189	node = line->parent;
3190	index = 0;
3191	for (line2 = node->children.line; line2 != line;
3192	line2 = line2->next)
3193	{
3194	if (line2 == NULL)
3195	{
3196	g_error ("gtk_text_btree_line_number couldn't find line");
3197	}
3198	index += 1;
3199	}
3200
3201	/*
3202	* Now work up through the levels of the tree one at a time,
3203	* counting how many lines are in GtkTextBTreeNodes preceding the current
3204	* GtkTextBTreeNode.
3205	*/
3206
3207	for (parent = node->parent ; parent != NULL;
3208	node = parent, parent = parent->parent)
3209	{
3210	for (node2 = parent->children.node; node2 != node;
3211	node2 = node2->next)
3212	{
3213	if (node2 == NULL)
3214	{
3215	g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3216	}
3217	index += node2->num_lines;
3218	}
3219	}
3220	return index;
3221	}
3222
3223	static GtkTextLineSegment*
3224	find_toggle_segment_before_char (GtkTextLine *line,
3225	int char_in_line,
3226	GtkTextTag *tag)
3227	{
3228	GtkTextLineSegment *seg;
3229	GtkTextLineSegment *toggle_seg;
3230	int index;
3231
3232	toggle_seg = NULL;
3233	index = 0;
3234	seg = line->segments;
3235	while ( (index + seg->char_count) <= char_in_line )
3236	{
3237	if (((seg->type == &gtk_text_toggle_on_type)
3238	|| (seg->type == &gtk_text_toggle_off_type))
3239	&& (seg->body.toggle.info->tag == tag))
3240	toggle_seg = seg;
3241
3242	index += seg->char_count;
3243	seg = seg->next;
3244	}
3245
3246	return toggle_seg;
3247	}
3248
3249	static GtkTextLineSegment*
3250	find_toggle_segment_before_byte (GtkTextLine *line,
3251	int byte_in_line,
3252	GtkTextTag *tag)
3253	{
3254	GtkTextLineSegment *seg;
3255	GtkTextLineSegment *toggle_seg;
3256	int index;
3257
3258	toggle_seg = NULL;
3259	index = 0;
3260	seg = line->segments;
3261	while ( (index + seg->byte_count) <= byte_in_line )
3262	{
3263	if (((seg->type == &gtk_text_toggle_on_type)
3264	|| (seg->type == &gtk_text_toggle_off_type))
3265	&& (seg->body.toggle.info->tag == tag))
3266	toggle_seg = seg;
3267
3268	index += seg->byte_count;
3269	seg = seg->next;
3270	}
3271
3272	return toggle_seg;
3273	}
3274
3275	static gboolean
3276	find_toggle_outside_current_line (GtkTextLine *line,
3277	GtkTextBTree *tree,
3278	GtkTextTag *tag)
3279	{
3280	GtkTextBTreeNode *node;
3281	GtkTextLine *sibling_line;
3282	GtkTextLineSegment *seg;
3283	GtkTextLineSegment *toggle_seg;
3284	int toggles;
3285	GtkTextTagInfo *info = NULL;
3286
3287	/*
3288	* No toggle in this line. Look for toggles for the tag in lines
3289	* that are predecessors of line but under the same
3290	* level-0 GtkTextBTreeNode.
3291	*/
3292	toggle_seg = NULL;
3293	sibling_line = line->parent->children.line;
3294	while (sibling_line != line)
3295	{
3296	seg = sibling_line->segments;
3297	while (seg != NULL)
3298	{
3299	if (((seg->type == &gtk_text_toggle_on_type)
3300	|| (seg->type == &gtk_text_toggle_off_type))
3301	&& (seg->body.toggle.info->tag == tag))
3302	toggle_seg = seg;
3303
3304	seg = seg->next;
3305	}
3306
3307	sibling_line = sibling_line->next;
3308	}
3309
3310	if (toggle_seg != NULL)
3311	return (toggle_seg->type == &gtk_text_toggle_on_type);
3312
3313	/*
3314	* No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3315	* this GtkTextBTreeNode, counting the number of toggles of the given tag in
3316	* siblings that precede that GtkTextBTreeNode.
3317	*/
3318
3319	info = gtk_text_btree_get_existing_tag_info (tree, tag);
3320
3321	if (info == NULL)
3322	return FALSE;
3323
3324	toggles = 0;
3325	node = line->parent;
3326	while (node->parent != NULL)
3327	{
3328	GtkTextBTreeNode *sibling_node;
3329
3330	sibling_node = node->parent->children.node;
3331	while (sibling_node != node)
3332	{
3333	Summary *summary;
3334
3335	summary = sibling_node->summary;
3336	while (summary != NULL)
3337	{
3338	if (summary->info == info)
3339	toggles += summary->toggle_count;
3340
3341	summary = summary->next;
3342	}
3343
3344	sibling_node = sibling_node->next;
3345	}
3346
3347	if (node == info->tag_root)
3348	break;
3349
3350	node = node->parent;
3351	}
3352
3353	/*
3354	* An odd number of toggles means that the tag is present at the
3355	* given point.
3356	*/
3357
3358	return (toggles & 1) != 0;
3359	}
3360
3361	/* FIXME this function is far too slow, for no good reason. */
3362	gboolean
3363	_gtk_text_line_char_has_tag (GtkTextLine *line,
3364	GtkTextBTree *tree,
3365	int char_in_line,
3366	GtkTextTag *tag)
3367	{
3368	GtkTextLineSegment *toggle_seg;
3369
3370	g_return_val_if_fail (line != NULL, FALSE);
3371
3372	/*
3373	* Check for toggles for the tag in the line but before
3374	* the char. If there is one, its type indicates whether or
3375	* not the character is tagged.
3376	*/
3377
3378	toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3379
3380	if (toggle_seg != NULL)
3381	return (toggle_seg->type == &gtk_text_toggle_on_type);
3382	else
3383	return find_toggle_outside_current_line (line, tree, tag);
3384	}
3385
3386	gboolean
3387	_gtk_text_line_byte_has_tag (GtkTextLine *line,
3388	GtkTextBTree *tree,
3389	int byte_in_line,
3390	GtkTextTag *tag)
3391	{
3392	GtkTextLineSegment *toggle_seg;
3393
3394	g_return_val_if_fail (line != NULL, FALSE);
3395
3396	/*
3397	* Check for toggles for the tag in the line but before
3398	* the char. If there is one, its type indicates whether or
3399	* not the character is tagged.
3400	*/
3401
3402	toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3403
3404	if (toggle_seg != NULL)
3405	return (toggle_seg->type == &gtk_text_toggle_on_type);
3406	else
3407	return find_toggle_outside_current_line (line, tree, tag);
3408	}
3409
3410	gboolean
3411	_gtk_text_line_is_last (GtkTextLine *line,
3412	GtkTextBTree *tree)
3413	{
3414	return line == get_last_line (tree);
3415	}
3416
3417	static void
3418	ensure_end_iter_line (GtkTextBTree *tree)
3419	{
3420	if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3421	{
3422	int real_line;
3423
3424	/* n_lines is without the magic line at the end */
3425	g_assert (_gtk_text_btree_line_count (tree) >= 1);
3426
3427	tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, line_number: -1, real_line_number: &real_line);
3428
3429	tree->end_iter_line_stamp = tree->chars_changed_stamp;
3430	}
3431	}
3432
3433	static void
3434	ensure_end_iter_segment (GtkTextBTree *tree)
3435	{
3436	if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3437	{
3438	GtkTextLineSegment *seg;
3439	GtkTextLineSegment *last_with_chars;
3440
3441	ensure_end_iter_line (tree);
3442
3443	last_with_chars = NULL;
3444
3445	seg = tree->end_iter_line->segments;
3446	while (seg != NULL)
3447	{
3448	if (seg->char_count > 0)
3449	last_with_chars = seg;
3450	seg = seg->next;
3451	}
3452	g_assert (last_with_chars);
3453
3454	tree->end_iter_segment = last_with_chars;
3455
3456	/* We know the last char in the last line is '\n' */
3457	tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3458	tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3459
3460	tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3461
3462	g_assert (tree->end_iter_segment->type == &gtk_text_char_type);
3463	g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3464	}
3465	}
3466
3467	gboolean
3468	_gtk_text_line_contains_end_iter (GtkTextLine *line,
3469	GtkTextBTree *tree)
3470	{
3471	ensure_end_iter_line (tree);
3472
3473	return line == tree->end_iter_line;
3474	}
3475
3476	gboolean
3477	_gtk_text_btree_is_end (GtkTextBTree *tree,
3478	GtkTextLine *line,
3479	GtkTextLineSegment *seg,
3480	int byte_index,
3481	int char_offset)
3482	{
3483	g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3484
3485	/* Do this first to avoid walking segments in most cases */
3486	if (!_gtk_text_line_contains_end_iter (line, tree))
3487	return FALSE;
3488
3489	ensure_end_iter_segment (tree);
3490
3491	if (seg != tree->end_iter_segment)
3492	return FALSE;
3493
3494	if (byte_index >= 0)
3495	return byte_index == tree->end_iter_segment_byte_index;
3496	else
3497	return char_offset == tree->end_iter_segment_char_offset;
3498	}
3499
3500	GtkTextLine*
3501	_gtk_text_line_next (GtkTextLine *line)
3502	{
3503	GtkTextBTreeNode *node;
3504
3505	if (line->next != NULL)
3506	return line->next;
3507	else
3508	{
3509	/*
3510	* This was the last line associated with the particular parent
3511	* GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3512	* then search down from that GtkTextBTreeNode to find the first
3513	* line.
3514	*/
3515
3516	node = line->parent;
3517	while (node != NULL && node->next == NULL)
3518	node = node->parent;
3519
3520	if (node == NULL)
3521	return NULL;
3522
3523	node = node->next;
3524	while (node->level > 0)
3525	{
3526	node = node->children.node;
3527	}
3528
3529	g_assert (node->children.line != line);
3530
3531	return node->children.line;
3532	}
3533	}
3534
3535	GtkTextLine*
3536	_gtk_text_line_next_excluding_last (GtkTextLine *line)
3537	{
3538	GtkTextLine *next;
3539
3540	next = _gtk_text_line_next (line);
3541
3542	/* If we were on the end iter line, we can't go to
3543	* the last line
3544	*/
3545	if (next && next->next == NULL && /* these checks are optimization only */
3546	_gtk_text_line_next (line: next) == NULL)
3547	return NULL;
3548
3549	return next;
3550	}
3551
3552	GtkTextLine*
3553	_gtk_text_line_previous (GtkTextLine *line)
3554	{
3555	GtkTextBTreeNode *node;
3556	GtkTextBTreeNode *node2;
3557	GtkTextLine *prev;
3558
3559	/*
3560	* Find the line under this GtkTextBTreeNode just before the starting line.
3561	*/
3562	prev = line->parent->children.line; /* First line at leaf */
3563	while (prev != line)
3564	{
3565	if (prev->next == line)
3566	return prev;
3567
3568	prev = prev->next;
3569
3570	if (prev == NULL)
3571	g_error ("gtk_text_btree_previous_line ran out of lines");
3572	}
3573
3574	/*
3575	* This was the first line associated with the particular parent
3576	* GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3577	* then search down from that GtkTextBTreeNode to find its last line.
3578	*/
3579	for (node = line->parent; ; node = node->parent)
3580	{
3581	if (node == NULL || node->parent == NULL)
3582	return NULL;
3583	else if (node != node->parent->children.node)
3584	break;
3585	}
3586
3587	for (node2 = node->parent->children.node; ;
3588	node2 = node2->children.node)
3589	{
3590	while (node2->next != node)
3591	node2 = node2->next;
3592
3593	if (node2->level == 0)
3594	break;
3595
3596	node = NULL;
3597	}
3598
3599	for (prev = node2->children.line ; ; prev = prev->next)
3600	{
3601	if (prev->next == NULL)
3602	return prev;
3603	}
3604
3605	g_assert_not_reached ();
3606	return NULL;
3607	}
3608
3609
3610	GtkTextLineData*
3611	_gtk_text_line_data_new (GtkTextLayout *layout,
3612	GtkTextLine *line)
3613	{
3614	GtkTextLineData *line_data;
3615
3616	line_data = g_slice_new (GtkTextLineData);
3617
3618	line_data->view_id = layout;
3619	line_data->next = NULL;
3620	line_data->width = 0;
3621	line_data->height = 0;
3622	line_data->top_ink = 0;
3623	line_data->bottom_ink = 0;
3624	line_data->valid = FALSE;
3625
3626	return line_data;
3627	}
3628
3629	void
3630	_gtk_text_line_add_data (GtkTextLine *line,
3631	GtkTextLineData *data)
3632	{
3633	g_return_if_fail (line != NULL);
3634	g_return_if_fail (data != NULL);
3635	g_return_if_fail (data->view_id != NULL);
3636
3637	if (line->views)
3638	{
3639	data->next = line->views;
3640	line->views = data;
3641	}
3642	else
3643	{
3644	line->views = data;
3645	}
3646	}
3647
3648	gpointer
3649	_gtk_text_line_remove_data (GtkTextLine *line,
3650	gpointer view_id)
3651	{
3652	GtkTextLineData *prev;
3653	GtkTextLineData *iter;
3654
3655	g_return_val_if_fail (line != NULL, NULL);
3656	g_return_val_if_fail (view_id != NULL, NULL);
3657
3658	prev = NULL;
3659	iter = line->views;
3660	while (iter != NULL)
3661	{
3662	if (iter->view_id == view_id)
3663	break;
3664	prev = iter;
3665	iter = iter->next;
3666	}
3667
3668	if (iter)
3669	{
3670	if (prev)
3671	prev->next = iter->next;
3672	else
3673	line->views = iter->next;
3674
3675	return iter;
3676	}
3677	else
3678	return NULL;
3679	}
3680
3681	gpointer
3682	_gtk_text_line_get_data (GtkTextLine *line,
3683	gpointer view_id)
3684	{
3685	GtkTextLineData *iter;
3686
3687	g_return_val_if_fail (line != NULL, NULL);
3688	g_return_val_if_fail (view_id != NULL, NULL);
3689
3690	iter = line->views;
3691	while (iter != NULL)
3692	{
3693	if (iter->view_id == view_id)
3694	break;
3695	iter = iter->next;
3696	}
3697
3698	return iter;
3699	}
3700
3701	void
3702	_gtk_text_line_invalidate_wrap (GtkTextLine *line,
3703	GtkTextLineData *ld)
3704	{
3705	/* For now this is totally unoptimized. FIXME?
3706
3707	We could probably optimize the case where the width removed
3708	is less than the max width for the parent node,
3709	and the case where the height is unchanged when we re-wrap.
3710	*/
3711
3712	g_return_if_fail (ld != NULL);
3713
3714	ld->valid = FALSE;
3715	gtk_text_btree_node_invalidate_upward (node: line->parent, view_id: ld->view_id);
3716	}
3717
3718	int
3719	_gtk_text_line_char_count (GtkTextLine *line)
3720	{
3721	GtkTextLineSegment *seg;
3722	int size;
3723
3724	size = 0;
3725	seg = line->segments;
3726	while (seg != NULL)
3727	{
3728	size += seg->char_count;
3729	seg = seg->next;
3730	}
3731	return size;
3732	}
3733
3734	int
3735	_gtk_text_line_byte_count (GtkTextLine *line)
3736	{
3737	GtkTextLineSegment *seg;
3738	int size;
3739
3740	size = 0;
3741	seg = line->segments;
3742	while (seg != NULL)
3743	{
3744	size += seg->byte_count;
3745	seg = seg->next;
3746	}
3747
3748	return size;
3749	}
3750
3751	int
3752	_gtk_text_line_char_index (GtkTextLine *target_line)
3753	{
3754	GtkTextBTreeNode *node_stack[64];
3755	GtkTextBTreeNode *iter;
3756	GtkTextLine *line;
3757	int num_chars;
3758	int tos = 0;
3759
3760	/* Push all our parent nodes onto a stack */
3761	iter = target_line->parent;
3762
3763	g_assert (iter != NULL);
3764
3765	while (iter != NULL && tos < 64)
3766	{
3767	node_stack[tos++] = iter;
3768	iter = iter->parent;
3769	}
3770
3771	tos--;
3772
3773	/* Check that we have the root node on top of the stack. */
3774	g_assert (node_stack != NULL &&
3775	node_stack[tos] != NULL &&
3776	node_stack[tos]->parent == NULL);
3777
3778	/* Add up chars in all nodes before the nodes in our stack.
3779	*/
3780
3781	num_chars = 0;
3782	while (tos >= 0)
3783	{
3784	GtkTextBTreeNode *child_iter;
3785
3786	iter = node_stack[tos];
3787
3788	if (iter->level == 0)
3789	{
3790	/* stack should be empty when we're on the last node */
3791	g_assert (tos == 0);
3792	break; /* Our children are now lines */
3793	}
3794
3795	tos--;
3796
3797	/* Add up chars before us in the tree */
3798	child_iter = iter->children.node;
3799	while (child_iter != node_stack[tos])
3800	{
3801	g_assert (child_iter != NULL);
3802
3803	num_chars += child_iter->num_chars;
3804	child_iter = child_iter->next;
3805	}
3806	}
3807
3808	g_assert (iter != NULL);
3809	g_assert (iter == target_line->parent);
3810
3811	/* Since we don't store char counts in lines, only in segments, we
3812	have to iterate over the lines adding up segment char counts
3813	until we find our line. */
3814	line = iter->children.line;
3815	while (line != target_line)
3816	{
3817	g_assert (line != NULL);
3818
3819	num_chars += _gtk_text_line_char_count (line);
3820	line = line->next;
3821	}
3822
3823	g_assert (line == target_line);
3824
3825	return num_chars;
3826	}
3827
3828	GtkTextLineSegment*
3829	_gtk_text_line_byte_to_segment (GtkTextLine *line,
3830	int byte_offset,
3831	int *seg_offset)
3832	{
3833	GtkTextLineSegment *seg;
3834	int offset;
3835
3836	g_return_val_if_fail (line != NULL, NULL);
3837
3838	offset = byte_offset;
3839	seg = line->segments;
3840
3841	while (offset >= seg->byte_count)
3842	{
3843	offset -= seg->byte_count;
3844	seg = seg->next;
3845	g_assert (seg != NULL); /* means an invalid byte index */
3846	}
3847
3848	if (seg_offset)
3849	*seg_offset = offset;
3850
3851	return seg;
3852	}
3853
3854	GtkTextLineSegment*
3855	_gtk_text_line_char_to_segment (GtkTextLine *line,
3856	int char_offset,
3857	int *seg_offset)
3858	{
3859	GtkTextLineSegment *seg;
3860	int offset;
3861
3862	g_return_val_if_fail (line != NULL, NULL);
3863
3864	offset = char_offset;
3865	seg = line->segments;
3866
3867	while (offset >= seg->char_count)
3868	{
3869	offset -= seg->char_count;
3870	seg = seg->next;
3871	g_assert (seg != NULL); /* means an invalid char index */
3872	}
3873
3874	if (seg_offset)
3875	*seg_offset = offset;
3876
3877	return seg;
3878	}
3879
3880	GtkTextLineSegment*
3881	_gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3882	int byte_offset,
3883	int *seg_offset)
3884	{
3885	GtkTextLineSegment *seg;
3886	int offset;
3887
3888	g_return_val_if_fail (line != NULL, NULL);
3889
3890	offset = byte_offset;
3891	seg = line->segments;
3892
3893	while (offset > 0 && offset >= seg->byte_count)
3894	{
3895	offset -= seg->byte_count;
3896	seg = seg->next;
3897	g_assert (seg != NULL); /* means an invalid byte index */
3898	}
3899
3900	if (seg_offset)
3901	*seg_offset = offset;
3902
3903	return seg;
3904	}
3905
3906	GtkTextLineSegment*
3907	_gtk_text_line_char_to_any_segment (GtkTextLine *line,
3908	int char_offset,
3909	int *seg_offset)
3910	{
3911	GtkTextLineSegment *seg;
3912	int offset;
3913
3914	g_return_val_if_fail (line != NULL, NULL);
3915
3916	offset = char_offset;
3917	seg = line->segments;
3918
3919	while (offset > 0 && offset >= seg->char_count)
3920	{
3921	offset -= seg->char_count;
3922	seg = seg->next;
3923	g_assert (seg != NULL); /* means an invalid byte index */
3924	}
3925
3926	if (seg_offset)
3927	*seg_offset = offset;
3928
3929	return seg;
3930	}
3931
3932	int
3933	_gtk_text_line_byte_to_char (GtkTextLine *line,
3934	int byte_offset)
3935	{
3936	int char_offset;
3937	GtkTextLineSegment *seg;
3938
3939	g_return_val_if_fail (line != NULL, 0);
3940	g_return_val_if_fail (byte_offset >= 0, 0);
3941
3942	char_offset = 0;
3943	seg = line->segments;
3944	while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3945	the next segment) */
3946	{
3947	byte_offset -= seg->byte_count;
3948	char_offset += seg->char_count;
3949	seg = seg->next;
3950	g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3951	}
3952
3953	g_assert (seg != NULL);
3954
3955	/* Now byte_offset is the offset into the current segment,
3956	and char_offset is the start of the current segment.
3957	Optimize the case where no chars use > 1 byte */
3958	if (seg->byte_count == seg->char_count)
3959	return char_offset + byte_offset;
3960	else
3961	{
3962	if (seg->type == &gtk_text_char_type)
3963	return char_offset + g_utf8_strlen (p: seg->body.chars, max: byte_offset);
3964	else
3965	{
3966	g_assert (seg->char_count == 1);
3967	g_assert (byte_offset == 0);
3968
3969	return char_offset;
3970	}
3971	}
3972	}
3973
3974	int
3975	_gtk_text_line_char_to_byte (GtkTextLine *line,
3976	int char_offset)
3977	{
3978	g_warning ("FIXME not implemented");
3979
3980	return 0;
3981	}
3982
3983	/* FIXME sync with char_locate (or figure out a clean
3984	way to merge the two functions) */
3985	gboolean
3986	_gtk_text_line_byte_locate (GtkTextLine *line,
3987	int byte_offset,
3988	GtkTextLineSegment **segment,
3989	GtkTextLineSegment **any_segment,
3990	int *seg_byte_offset,
3991	int *line_byte_offset)
3992	{
3993	GtkTextLineSegment *seg;
3994	GtkTextLineSegment *after_last_indexable;
3995	GtkTextLineSegment *last_indexable;
3996	int offset;
3997	int bytes_in_line;
3998
3999	g_return_val_if_fail (line != NULL, FALSE);
4000	g_return_val_if_fail (byte_offset >= 0, FALSE);
4001
4002	*segment = NULL;
4003	*any_segment = NULL;
4004	bytes_in_line = 0;
4005
4006	offset = byte_offset;
4007
4008	last_indexable = NULL;
4009	after_last_indexable = line->segments;
4010	seg = line->segments;
4011
4012	/* The loop ends when we're inside a segment;
4013	last_indexable refers to the last segment
4014	we passed entirely. */
4015	while (seg && offset >= seg->byte_count)
4016	{
4017	if (seg->char_count > 0)
4018	{
4019	offset -= seg->byte_count;
4020	bytes_in_line += seg->byte_count;
4021	last_indexable = seg;
4022	after_last_indexable = last_indexable->next;
4023	}
4024
4025	seg = seg->next;
4026	}
4027
4028	if (seg == NULL)
4029	{
4030	/* We went off the end of the line */
4031	if (offset != 0)
4032	g_warning ("%s: byte index off the end of the line", G_STRLOC);
4033
4034	return FALSE;
4035	}
4036	else
4037	{
4038	*segment = seg;
4039	if (after_last_indexable != NULL)
4040	*any_segment = after_last_indexable;
4041	else
4042	*any_segment = *segment;
4043	}
4044
4045	/* Override any_segment if we're in the middle of a segment. */
4046	if (offset > 0)
4047	*any_segment = *segment;
4048
4049	*seg_byte_offset = offset;
4050
4051	g_assert (*segment != NULL);
4052	g_assert (*any_segment != NULL);
4053	g_assert (*seg_byte_offset < (*segment)->byte_count);
4054
4055	*line_byte_offset = bytes_in_line + *seg_byte_offset;
4056
4057	return TRUE;
4058	}
4059
4060	/* FIXME sync with byte_locate (or figure out a clean
4061	way to merge the two functions) */
4062	gboolean
4063	_gtk_text_line_char_locate (GtkTextLine *line,
4064	int char_offset,
4065	GtkTextLineSegment **segment,
4066	GtkTextLineSegment **any_segment,
4067	int *seg_char_offset,
4068	int *line_char_offset)
4069	{
4070	GtkTextLineSegment *seg;
4071	GtkTextLineSegment *after_last_indexable;
4072	GtkTextLineSegment *last_indexable;
4073	int offset;
4074	int chars_in_line;
4075
4076	g_return_val_if_fail (line != NULL, FALSE);
4077	g_return_val_if_fail (char_offset >= 0, FALSE);
4078
4079	*segment = NULL;
4080	*any_segment = NULL;
4081	chars_in_line = 0;
4082
4083	offset = char_offset;
4084
4085	last_indexable = NULL;
4086	after_last_indexable = line->segments;
4087	seg = line->segments;
4088
4089	/* The loop ends when we're inside a segment;
4090	last_indexable refers to the last segment
4091	we passed entirely. */
4092	while (seg && offset >= seg->char_count)
4093	{
4094	if (seg->char_count > 0)
4095	{
4096	offset -= seg->char_count;
4097	chars_in_line += seg->char_count;
4098	last_indexable = seg;
4099	after_last_indexable = last_indexable->next;
4100	}
4101
4102	seg = seg->next;
4103	}
4104
4105	if (seg == NULL)
4106	{
4107	/* end of the line */
4108	if (offset != 0)
4109	g_warning ("%s: char offset off the end of the line", G_STRLOC);
4110
4111	return FALSE;
4112	}
4113	else
4114	{
4115	*segment = seg;
4116	if (after_last_indexable != NULL)
4117	*any_segment = after_last_indexable;
4118	else
4119	*any_segment = *segment;
4120	}
4121
4122	/* Override any_segment if we're in the middle of a segment. */
4123	if (offset > 0)
4124	*any_segment = *segment;
4125
4126	*seg_char_offset = offset;
4127
4128	g_assert (*segment != NULL);
4129	g_assert (*any_segment != NULL);
4130	g_assert (*seg_char_offset < (*segment)->char_count);
4131
4132	*line_char_offset = chars_in_line + *seg_char_offset;
4133
4134	return TRUE;
4135	}
4136
4137	void
4138	_gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4139	int byte_offset,
4140	int *line_char_offset,
4141	int *seg_char_offset)
4142	{
4143	GtkTextLineSegment *seg;
4144	int offset;
4145
4146	g_return_if_fail (line != NULL);
4147	g_return_if_fail (byte_offset >= 0);
4148
4149	*line_char_offset = 0;
4150
4151	offset = byte_offset;
4152	seg = line->segments;
4153
4154	while (offset >= seg->byte_count)
4155	{
4156	offset -= seg->byte_count;
4157	*line_char_offset += seg->char_count;
4158	seg = seg->next;
4159	g_assert (seg != NULL); /* means an invalid char offset */
4160	}
4161
4162	g_assert (seg->char_count > 0); /* indexable. */
4163
4164	/* offset is now the number of bytes into the current segment we
4165	* want to go. Count chars into the current segment.
4166	*/
4167
4168	if (seg->type == &gtk_text_char_type)
4169	{
4170	*seg_char_offset = g_utf8_strlen (p: seg->body.chars, max: offset);
4171
4172	g_assert (*seg_char_offset < seg->char_count);
4173
4174	*line_char_offset += *seg_char_offset;
4175	}
4176	else
4177	{
4178	g_assert (offset == 0);
4179	*seg_char_offset = 0;
4180	}
4181	}
4182
4183	void
4184	_gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4185	int char_offset,
4186	int *line_byte_offset,
4187	int *seg_byte_offset)
4188	{
4189	GtkTextLineSegment *seg;
4190	int offset;
4191
4192	g_return_if_fail (line != NULL);
4193	g_return_if_fail (char_offset >= 0);
4194
4195	*line_byte_offset = 0;
4196
4197	offset = char_offset;
4198	seg = line->segments;
4199
4200	while (offset >= seg->char_count)
4201	{
4202	offset -= seg->char_count;
4203	*line_byte_offset += seg->byte_count;
4204	seg = seg->next;
4205	g_assert (seg != NULL); /* means an invalid char offset */
4206	}
4207
4208	g_assert (seg->char_count > 0); /* indexable. */
4209
4210	/* offset is now the number of chars into the current segment we
4211	want to go. Count bytes into the current segment. */
4212
4213	if (seg->type == &gtk_text_char_type)
4214	{
4215	const char *p;
4216
4217	/* if in the last fourth of the segment walk backwards */
4218	if (seg->char_count - offset < seg->char_count / 4)
4219	p = g_utf8_offset_to_pointer (str: seg->body.chars + seg->byte_count,
4220	offset: offset - seg->char_count);
4221	else
4222	p = g_utf8_offset_to_pointer (str: seg->body.chars, offset);
4223
4224	*seg_byte_offset = p - seg->body.chars;
4225
4226	g_assert (*seg_byte_offset < seg->byte_count);
4227
4228	*line_byte_offset += *seg_byte_offset;
4229	}
4230	else
4231	{
4232	g_assert (offset == 0);
4233	*seg_byte_offset = 0;
4234	}
4235	}
4236
4237	static int
4238	node_compare (GtkTextBTreeNode *lhs,
4239	GtkTextBTreeNode *rhs)
4240	{
4241	GtkTextBTreeNode *iter;
4242	GtkTextBTreeNode *node;
4243	GtkTextBTreeNode *common_parent;
4244	GtkTextBTreeNode *parent_of_lower;
4245	GtkTextBTreeNode *parent_of_higher;
4246	gboolean lhs_is_lower;
4247	GtkTextBTreeNode *lower;
4248	GtkTextBTreeNode *higher;
4249
4250	/* This function assumes that lhs and rhs are not underneath each
4251	* other.
4252	*/
4253
4254	if (lhs == rhs)
4255	return 0;
4256
4257	if (lhs->level < rhs->level)
4258	{
4259	lhs_is_lower = TRUE;
4260	lower = lhs;
4261	higher = rhs;
4262	}
4263	else
4264	{
4265	lhs_is_lower = FALSE;
4266	lower = rhs;
4267	higher = lhs;
4268	}
4269
4270	/* Algorithm: find common parent of lhs/rhs. Save the child nodes
4271	* of the common parent we used to reach the common parent; the
4272	* ordering of these child nodes in the child list is the ordering
4273	* of lhs and rhs.
4274	*/
4275
4276	/* Get on the same level (may be on same level already) */
4277	node = lower;
4278	while (node->level < higher->level)
4279	node = node->parent;
4280
4281	g_assert (node->level == higher->level);
4282
4283	g_assert (node != higher); /* Happens if lower is underneath higher */
4284
4285	/* Go up until we have two children with a common parent.
4286	*/
4287	parent_of_lower = node;
4288	parent_of_higher = higher;
4289
4290	while (parent_of_lower->parent != parent_of_higher->parent)
4291	{
4292	parent_of_lower = parent_of_lower->parent;
4293	parent_of_higher = parent_of_higher->parent;
4294	}
4295
4296	g_assert (parent_of_lower->parent == parent_of_higher->parent);
4297
4298	common_parent = parent_of_lower->parent;
4299
4300	g_assert (common_parent != NULL);
4301
4302	/* See which is first in the list of common_parent's children */
4303	iter = common_parent->children.node;
4304	while (iter != NULL)
4305	{
4306	if (iter == parent_of_higher)
4307	{
4308	/* higher is less than lower */
4309
4310	if (lhs_is_lower)
4311	return 1; /* lhs > rhs */
4312	else
4313	return -1;
4314	}
4315	else if (iter == parent_of_lower)
4316	{
4317	/* lower is less than higher */
4318
4319	if (lhs_is_lower)
4320	return -1; /* lhs < rhs */
4321	else
4322	return 1;
4323	}
4324
4325	iter = iter->next;
4326	}
4327
4328	g_assert_not_reached ();
4329	return 0;
4330	}
4331
4332	/* remember that tag == NULL means "any tag" */
4333	GtkTextLine*
4334	_gtk_text_line_next_could_contain_tag (GtkTextLine *line,
4335	GtkTextBTree *tree,
4336	GtkTextTag *tag)
4337	{
4338	GtkTextBTreeNode *node;
4339	GtkTextTagInfo *info;
4340	gboolean below_tag_root;
4341
4342	g_return_val_if_fail (line != NULL, NULL);
4343
4344	#ifdef G_ENABLE_DEBUG
4345	if (GTK_DEBUG_CHECK (TEXT))
4346	_gtk_text_btree_check (tree);
4347	#endif
4348
4349	if (tag == NULL)
4350	{
4351	/* Right now we can only offer linear-search if the user wants
4352	* to know about any tag toggle at all.
4353	*/
4354	return _gtk_text_line_next_excluding_last (line);
4355	}
4356
4357	/* Our tag summaries only have node precision, not line
4358	* precision. This means that if any line under a node could contain a
4359	* tag, then any of the others could also contain a tag.
4360	*
4361	* In the future we could have some mechanism to keep track of how
4362	* many toggles we've found under a node so far, since we have a
4363	* count of toggles under the node. But for now I'm going with KISS.
4364	*/
4365
4366	/* return same-node line, if any. */
4367	if (line->next)
4368	return line->next;
4369
4370	info = gtk_text_btree_get_existing_tag_info (tree, tag);
4371	if (info == NULL)
4372	return NULL;
4373
4374	if (info->tag_root == NULL)
4375	return NULL;
4376
4377	if (info->tag_root == line->parent)
4378	return NULL; /* we were at the last line under the tag root */
4379
4380	/* We need to go up out of this node, and on to the next one with
4381	toggles for the target tag. If we're below the tag root, we need to
4382	find the next node below the tag root that has tag summaries. If
4383	we're not below the tag root, we need to see if the tag root is
4384	after us in the tree, and if so, return the first line underneath
4385	the tag root. */
4386
4387	node = line->parent;
4388	below_tag_root = FALSE;
4389	while (node != NULL)
4390	{
4391	if (node == info->tag_root)
4392	{
4393	below_tag_root = TRUE;
4394	break;
4395	}
4396
4397	node = node->parent;
4398	}
4399
4400	if (below_tag_root)
4401	{
4402	node = line->parent;
4403	while (node != info->tag_root)
4404	{
4405	if (node->next == NULL)
4406	node = node->parent;
4407	else
4408	{
4409	node = node->next;
4410
4411	if (gtk_text_btree_node_has_tag (node, tag))
4412	goto found;
4413	}
4414	}
4415	return NULL;
4416	}
4417	else
4418	{
4419	int ordering;
4420
4421	ordering = node_compare (lhs: line->parent, rhs: info->tag_root);
4422
4423	if (ordering < 0)
4424	{
4425	/* Tag root is ahead of us, so search there. */
4426	node = info->tag_root;
4427	goto found;
4428	}
4429	else
4430	{
4431	/* Tag root is after us, so no more lines that
4432	* could contain the tag.
4433	*/
4434	return NULL;
4435	}
4436
4437	g_assert_not_reached ();
4438	}
4439
4440	found:
4441
4442	g_assert (node != NULL);
4443
4444	/* We have to find the first sub-node of this node that contains
4445	* the target tag.
4446	*/
4447
4448	while (node->level > 0)
4449	{
4450	node = node->children.node;
4451	while (node != NULL)
4452	{
4453	if (gtk_text_btree_node_has_tag (node, tag))
4454	break;
4455	node = node->next;
4456	}
4457	g_assert (node != NULL); /* If this fails, it likely means an
4458	incorrect tag summary led us on a
4459	wild goose chase down this branch of
4460	the tree. */
4461	}
4462
4463	g_assert (node != NULL);
4464	g_assert (node->level == 0);
4465
4466	return node->children.line;
4467	}
4468
4469	static GtkTextLine*
4470	prev_line_under_node (GtkTextBTreeNode *node,
4471	GtkTextLine *line)
4472	{
4473	GtkTextLine *prev;
4474
4475	prev = node->children.line;
4476
4477	g_assert (prev);
4478
4479	if (prev != line)
4480	{
4481	while (prev->next != line)
4482	prev = prev->next;
4483
4484	return prev;
4485	}
4486
4487	return NULL;
4488	}
4489
4490	GtkTextLine*
4491	_gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4492	GtkTextBTree *tree,
4493	GtkTextTag *tag)
4494	{
4495	GtkTextBTreeNode *node;
4496	GtkTextBTreeNode *found_node = NULL;
4497	GtkTextTagInfo *info;
4498	gboolean below_tag_root;
4499	GtkTextLine *prev;
4500	GtkTextBTreeNode *line_ancestor;
4501	GtkTextBTreeNode *line_ancestor_parent;
4502
4503	/* See next_could_contain_tag () for more extensive comments
4504	* on what's going on here.
4505	*/
4506
4507	g_return_val_if_fail (line != NULL, NULL);
4508
4509	#ifdef G_ENABLE_DEBUG
4510	if (GTK_DEBUG_CHECK (TEXT))
4511	_gtk_text_btree_check (tree);
4512	#endif
4513
4514	if (tag == NULL)
4515	{
4516	/* Right now we can only offer linear-search if the user wants
4517	* to know about any tag toggle at all.
4518	*/
4519	return _gtk_text_line_previous (line);
4520	}
4521
4522	/* Return same-node line, if any. */
4523	prev = prev_line_under_node (node: line->parent, line);
4524	if (prev)
4525	return prev;
4526
4527	info = gtk_text_btree_get_existing_tag_info (tree, tag);
4528	if (info == NULL)
4529	return NULL;
4530
4531	if (info->tag_root == NULL)
4532	return NULL;
4533
4534	if (info->tag_root == line->parent)
4535	return NULL; /* we were at the first line under the tag root */
4536
4537	/* Are we below the tag root */
4538	node = line->parent;
4539	below_tag_root = FALSE;
4540	while (node != NULL)
4541	{
4542	if (node == info->tag_root)
4543	{
4544	below_tag_root = TRUE;
4545	break;
4546	}
4547
4548	node = node->parent;
4549	}
4550
4551	if (below_tag_root)
4552	{
4553	/* Look for a previous node under this tag root that has our
4554	* tag.
4555	*/
4556
4557	/* this assertion holds because line->parent is not the
4558	* tag root, we are below the tag root, and the tag
4559	* root exists.
4560	*/
4561	g_assert (line->parent->parent != NULL);
4562
4563	line_ancestor = line->parent;
4564	line_ancestor_parent = line->parent->parent;
4565
4566	while (line_ancestor != info->tag_root)
4567	{
4568	GSList *child_nodes = NULL;
4569	GSList *tmp;
4570
4571	/* Create reverse-order list of nodes before
4572	* line_ancestor
4573	*/
4574	if (line_ancestor_parent != NULL)
4575	node = line_ancestor_parent->children.node;
4576	else
4577	node = line_ancestor;
4578
4579	while (node != line_ancestor && node != NULL)
4580	{
4581	child_nodes = g_slist_prepend (list: child_nodes, data: node);
4582
4583	node = node->next;
4584	}
4585
4586	/* Try to find a node with our tag on it in the list */
4587	tmp = child_nodes;
4588	while (tmp != NULL)
4589	{
4590	GtkTextBTreeNode *this_node = tmp->data;
4591
4592	g_assert (this_node != line_ancestor);
4593
4594	if (gtk_text_btree_node_has_tag (node: this_node, tag))
4595	{
4596	found_node = this_node;
4597	g_slist_free (list: child_nodes);
4598	goto found;
4599	}
4600
4601	tmp = tmp->next;
4602	}
4603
4604	g_slist_free (list: child_nodes);
4605
4606	/* Didn't find anything on this level; go up one level. */
4607	line_ancestor = line_ancestor_parent;
4608	line_ancestor_parent = line_ancestor->parent;
4609	}
4610
4611	/* No dice. */
4612	return NULL;
4613	}
4614	else
4615	{
4616	int ordering;
4617
4618	ordering = node_compare (lhs: line->parent, rhs: info->tag_root);
4619
4620	if (ordering < 0)
4621	{
4622	/* Tag root is ahead of us, so no more lines
4623	* with this tag.
4624	*/
4625	return NULL;
4626	}
4627	else
4628	{
4629	/* Tag root is after us, so grab last tagged
4630	* line underneath the tag root.
4631	*/
4632	found_node = info->tag_root;
4633	goto found;
4634	}
4635
4636	g_assert_not_reached ();
4637	}
4638
4639	found:
4640
4641	g_assert (found_node != NULL);
4642
4643	/* We have to find the last sub-node of this node that contains
4644	* the target tag.
4645	*/
4646	node = found_node;
4647
4648	while (node->level > 0)
4649	{
4650	GSList *child_nodes = NULL;
4651	GSList *iter;
4652	g_assert (node != NULL); /* If this fails, it likely means an
4653	incorrect tag summary led us on a
4654	wild goose chase down this branch of
4655	the tree. */
4656
4657	node = node->children.node;
4658	while (node != NULL)
4659	{
4660	child_nodes = g_slist_prepend (list: child_nodes, data: node);
4661	node = node->next;
4662	}
4663
4664	node = NULL; /* detect failure to find a child node. */
4665
4666	iter = child_nodes;
4667	while (iter != NULL)
4668	{
4669	if (gtk_text_btree_node_has_tag (node: iter->data, tag))
4670	{
4671	/* recurse into this node. */
4672	node = iter->data;
4673	break;
4674	}
4675
4676	iter = iter->next;
4677	}
4678
4679	g_slist_free (list: child_nodes);
4680
4681	g_assert (node != NULL);
4682	}
4683
4684	g_assert (node != NULL);
4685	g_assert (node->level == 0);
4686
4687	/* this assertion is correct, but slow. */
4688	/* g_assert (node_compare (node, line->parent) < 0); */
4689
4690	/* Return last line in this node. */
4691
4692	prev = node->children.line;
4693	while (prev->next)
4694	prev = prev->next;
4695
4696	return prev;
4697	}
4698
4699	/*
4700	* Non-public function implementations
4701	*/
4702
4703	static void
4704	summary_list_destroy (Summary *summary)
4705	{
4706	g_slice_free_chain (Summary, summary, next);
4707	}
4708
4709	static GtkTextLine*
4710	get_last_line (GtkTextBTree *tree)
4711	{
4712	if (tree->last_line_stamp != tree->chars_changed_stamp)
4713	{
4714	int n_lines;
4715	GtkTextLine *line;
4716	int real_line;
4717
4718	n_lines = _gtk_text_btree_line_count (tree);
4719
4720	g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4721
4722	line = _gtk_text_btree_get_line (tree, line_number: n_lines, real_line_number: &real_line);
4723
4724	tree->last_line_stamp = tree->chars_changed_stamp;
4725	tree->last_line = line;
4726	}
4727
4728	return tree->last_line;
4729	}
4730
4731	/*
4732	* Lines
4733	*/
4734
4735	static GtkTextLine*
4736	gtk_text_line_new (void)
4737	{
4738	GtkTextLine *line;
4739
4740	line = g_slice_new0 (GtkTextLine);
4741	line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4742	line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4743	line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4744
4745	return line;
4746	}
4747
4748	static void
4749	gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4750	{
4751	GtkTextLineData *ld;
4752	GtkTextLineData *next;
4753
4754	g_return_if_fail (line != NULL);
4755
4756	ld = line->views;
4757	while (ld != NULL)
4758	{
4759	BTreeView *view;
4760
4761	view = gtk_text_btree_get_view (tree, view_id: ld->view_id);
4762
4763	g_assert (view != NULL);
4764
4765	next = ld->next;
4766	gtk_text_layout_free_line_data (layout: view->layout, line, line_data: ld);
4767
4768	ld = next;
4769	}
4770
4771	g_slice_free (GtkTextLine, line);
4772	}
4773
4774	static void
4775	gtk_text_line_set_parent (GtkTextLine *line,
4776	GtkTextBTreeNode *node)
4777	{
4778	if (line->parent == node)
4779	return;
4780	line->parent = node;
4781	gtk_text_btree_node_invalidate_upward (node, NULL);
4782	}
4783
4784	static void
4785	cleanup_line (GtkTextLine *line)
4786	{
4787	GtkTextLineSegment *seg, **prev_p;
4788	gboolean changed;
4789
4790	/*
4791	* Make a pass over all of the segments in the line, giving each
4792	* a chance to clean itself up. This could potentially change
4793	* the structure of the line, e.g. by merging two segments
4794	* together or having two segments cancel themselves; if so,
4795	* then repeat the whole process again, since the first structure
4796	* change might make other structure changes possible. Repeat
4797	* until eventually there are no changes.
4798	*/
4799
4800	changed = TRUE;
4801	while (changed)
4802	{
4803	changed = FALSE;
4804	prev_p = &line->segments;
4805	for (seg = *prev_p; seg != NULL; seg = *prev_p)
4806	{
4807	if (seg->type->cleanupFunc != NULL)
4808	{
4809	*prev_p = (*seg->type->cleanupFunc)(seg, line);
4810	if (seg != *prev_p)
4811	{
4812	changed = TRUE;
4813	continue;
4814	}
4815	}
4816
4817	prev_p = &(*prev_p)->next;
4818	}
4819	}
4820	}
4821
4822	/*
4823	* Nodes
4824	*/
4825
4826	static inline NodeData*
4827	node_data_new (gpointer view_id,
4828	NodeData *next)
4829	{
4830	NodeData *nd;
4831
4832	nd = g_slice_new (NodeData);
4833
4834	nd->view_id = view_id;
4835	nd->next = next;
4836	nd->width = 0;
4837	nd->height = 0;
4838	nd->valid = FALSE;
4839
4840	return nd;
4841	}
4842
4843	static inline void
4844	node_data_destroy (NodeData *nd)
4845	{
4846	g_slice_free (NodeData, nd);
4847	}
4848
4849	static inline void
4850	node_data_list_destroy (NodeData *nd)
4851	{
4852	g_slice_free_chain (NodeData, nd, next);
4853	}
4854
4855	static inline NodeData*
4856	node_data_find (NodeData *nd,
4857	gpointer view_id)
4858	{
4859	while (nd != NULL)
4860	{
4861	if (nd->view_id == view_id)
4862	break;
4863	nd = nd->next;
4864	}
4865	return nd;
4866	}
4867
4868	static void
4869	summary_destroy (Summary *summary)
4870	{
4871	/* Fill with error-triggering garbage */
4872	summary->info = (void*)0x1;
4873	summary->toggle_count = 567;
4874	summary->next = (void*)0x1;
4875	g_slice_free (Summary, summary);
4876	}
4877
4878	static GtkTextBTreeNode*
4879	gtk_text_btree_node_new (void)
4880	{
4881	GtkTextBTreeNode *node;
4882
4883	node = g_slice_new (GtkTextBTreeNode);
4884
4885	node->node_data = NULL;
4886
4887	return node;
4888	}
4889
4890	static void
4891	gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4892	GtkTextTagInfo *info,
4893	int adjust)
4894	{
4895	Summary *summary;
4896
4897	summary = node->summary;
4898	while (summary != NULL)
4899	{
4900	if (summary->info == info)
4901	{
4902	summary->toggle_count += adjust;
4903	break;
4904	}
4905
4906	summary = summary->next;
4907	}
4908
4909	if (summary == NULL)
4910	{
4911	/* didn't find a summary for our tag. */
4912	g_return_if_fail (adjust > 0);
4913	summary = g_slice_new (Summary);
4914	summary->info = info;
4915	summary->toggle_count = adjust;
4916	summary->next = node->summary;
4917	node->summary = summary;
4918	}
4919	}
4920
4921	/* Note that the tag root and above do not have summaries
4922	for the tag; only nodes below the tag root have
4923	the summaries. */
4924	static gboolean
4925	gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4926	{
4927	Summary *summary;
4928
4929	summary = node->summary;
4930	while (summary != NULL)
4931	{
4932	if (tag == NULL ||
4933	summary->info->tag == tag)
4934	return TRUE;
4935
4936	summary = summary->next;
4937	}
4938
4939	return FALSE;
4940	}
4941
4942	/* Add node and all children to the damage region. */
4943	#if 0
4944	static void
4945	gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4946	{
4947	NodeData *nd;
4948
4949	nd = node->node_data;
4950	while (nd != NULL)
4951	{
4952	nd->valid = FALSE;
4953	nd = nd->next;
4954	}
4955
4956	if (node->level == 0)
4957	{
4958	GtkTextLine *line;
4959
4960	line = node->children.line;
4961	while (line != NULL)
4962	{
4963	GtkTextLineData *ld;
4964
4965	ld = line->views;
4966	while (ld != NULL)
4967	{
4968	ld->valid = FALSE;
4969	ld = ld->next;
4970	}
4971
4972	line = line->next;
4973	}
4974	}
4975	else
4976	{
4977	GtkTextBTreeNode *child;
4978
4979	child = node->children.node;
4980
4981	while (child != NULL)
4982	{
4983	gtk_text_btree_node_invalidate_downward (child);
4984
4985	child = child->next;
4986	}
4987	}
4988	}
4989	#endif
4990
4991	static void
4992	gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4993	{
4994	GtkTextBTreeNode *iter;
4995
4996	iter = node;
4997	while (iter != NULL)
4998	{
4999	NodeData *nd;
5000
5001	if (view_id)
5002	{
5003	nd = node_data_find (nd: iter->node_data, view_id);
5004
5005	if (nd == NULL || !nd->valid)
5006	break; /* Once a node is invalid, we know its parents are as well. */
5007
5008	nd->valid = FALSE;
5009	}
5010	else
5011	{
5012	gboolean should_continue = FALSE;
5013
5014	nd = iter->node_data;
5015	while (nd != NULL)
5016	{
5017	if (nd->valid)
5018	{
5019	should_continue = TRUE;
5020	nd->valid = FALSE;
5021	}
5022
5023	nd = nd->next;
5024	}
5025
5026	if (!should_continue)
5027	break; /* This node was totally invalidated, so are its
5028	parents */
5029	}
5030
5031	iter = iter->parent;
5032	}
5033	}
5034
5035
5036	/**
5037	* _gtk_text_btree_is_valid:
5038	* @tree: a GtkTextBTree
5039	* @view_id: ID for the view
5040	*
5041	* Check to see if the entire GtkTextBTree is valid or not for
5042	* the given view.
5043	*
5044	* Returns: %TRUE if the entire GtkTextBTree is valid
5045	**/
5046	gboolean
5047	_gtk_text_btree_is_valid (GtkTextBTree *tree,
5048	gpointer view_id)
5049	{
5050	NodeData *nd;
5051	g_return_val_if_fail (tree != NULL, FALSE);
5052
5053	nd = node_data_find (nd: tree->root_node->node_data, view_id);
5054	return (nd && nd->valid);
5055	}
5056
5057	typedef struct _ValidateState ValidateState;
5058
5059	struct _ValidateState
5060	{
5061	int remaining_pixels;
5062	gboolean in_validation;
5063	int y;
5064	int old_height;
5065	int new_height;
5066	};
5067
5068	static void
5069	gtk_text_btree_node_validate (BTreeView *view,
5070	GtkTextBTreeNode *node,
5071	gpointer view_id,
5072	ValidateState *state)
5073	{
5074	int node_valid = TRUE;
5075	int node_width = 0;
5076	int node_height = 0;
5077
5078	NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5079	g_return_if_fail (!nd->valid);
5080
5081	if (node->level == 0)
5082	{
5083	GtkTextLine *line = node->children.line;
5084	GtkTextLineData *ld;
5085
5086	/* Iterate over leading valid lines */
5087	while (line != NULL)
5088	{
5089	ld = _gtk_text_line_get_data (line, view_id);
5090
5091	if (!ld || !ld->valid)
5092	break;
5093	else if (state->in_validation)
5094	{
5095	state->in_validation = FALSE;
5096	return;
5097	}
5098	else
5099	{
5100	state->y += ld->height;
5101	node_width = MAX (ld->width, node_width);
5102	node_height += ld->height;
5103	}
5104
5105	line = line->next;
5106	}
5107
5108	state->in_validation = TRUE;
5109
5110	/* Iterate over invalid lines */
5111	while (line != NULL)
5112	{
5113	ld = _gtk_text_line_get_data (line, view_id);
5114
5115	if (ld && ld->valid)
5116	break;
5117	else
5118	{
5119	if (ld)
5120	state->old_height += ld->height;
5121	ld = gtk_text_layout_wrap (layout: view->layout, line, line_data: ld);
5122	state->new_height += ld->height;
5123
5124	node_width = MAX (ld->width, node_width);
5125	node_height += ld->height;
5126
5127	state->remaining_pixels -= ld->height;
5128	if (state->remaining_pixels <= 0)
5129	{
5130	line = line->next;
5131	break;
5132	}
5133	}
5134
5135	line = line->next;
5136	}
5137
5138	/* Iterate over the remaining lines */
5139	while (line != NULL)
5140	{
5141	ld = _gtk_text_line_get_data (line, view_id);
5142	state->in_validation = FALSE;
5143
5144	if (!ld || !ld->valid)
5145	node_valid = FALSE;
5146
5147	if (ld)
5148	{
5149	node_width = MAX (ld->width, node_width);
5150	node_height += ld->height;
5151	}
5152
5153	line = line->next;
5154	}
5155	}
5156	else
5157	{
5158	GtkTextBTreeNode *child;
5159	NodeData *child_nd;
5160
5161	child = node->children.node;
5162
5163	/* Iterate over leading valid nodes */
5164	while (child)
5165	{
5166	child_nd = gtk_text_btree_node_ensure_data (node: child, view_id);
5167
5168	if (!child_nd->valid)
5169	break;
5170	else if (state->in_validation)
5171	{
5172	state->in_validation = FALSE;
5173	return;
5174	}
5175	else
5176	{
5177	state->y += child_nd->height;
5178	node_width = MAX (node_width, child_nd->width);
5179	node_height += child_nd->height;
5180	}
5181
5182	child = child->next;
5183	}
5184
5185	/* Iterate over invalid nodes */
5186	while (child)
5187	{
5188	child_nd = gtk_text_btree_node_ensure_data (node: child, view_id);
5189
5190	if (child_nd->valid)
5191	break;
5192	else
5193	{
5194	gtk_text_btree_node_validate (view, node: child, view_id, state);
5195
5196	if (!child_nd->valid)
5197	node_valid = FALSE;
5198	node_width = MAX (node_width, child_nd->width);
5199	node_height += child_nd->height;
5200
5201	if (!state->in_validation || state->remaining_pixels <= 0)
5202	{
5203	child = child->next;
5204	break;
5205	}
5206	}
5207
5208	child = child->next;
5209	}
5210
5211	/* Iterate over the remaining lines */
5212	while (child)
5213	{
5214	child_nd = gtk_text_btree_node_ensure_data (node: child, view_id);
5215	state->in_validation = FALSE;
5216
5217	if (!child_nd->valid)
5218	node_valid = FALSE;
5219
5220	node_width = MAX (child_nd->width, node_width);
5221	node_height += child_nd->height;
5222
5223	child = child->next;
5224	}
5225	}
5226
5227	nd->width = node_width;
5228	nd->height = node_height;
5229	nd->valid = node_valid;
5230	}
5231
5232	/**
5233	* _gtk_text_btree_validate:
5234	* @tree: a GtkTextBTree
5235	* @view_id: view id
5236	* @max_pixels: the maximum number of pixels to validate. (No more
5237	* than one paragraph beyond this limit will be validated)
5238	* @y: location to store starting y coordinate of validated region
5239	* @old_height: location to store old height of validated region
5240	* @new_height: location to store new height of validated region
5241	*
5242	* Validate a single contiguous invalid region of a GtkTextBTree for
5243	* a given view.
5244	*
5245	* Returns: %TRUE if a region has been validated, %FALSE if the
5246	* entire tree was already valid.
5247	**/
5248	gboolean
5249	_gtk_text_btree_validate (GtkTextBTree *tree,
5250	gpointer view_id,
5251	int max_pixels,
5252	int *y,
5253	int *old_height,
5254	int *new_height)
5255	{
5256	BTreeView *view;
5257
5258	g_return_val_if_fail (tree != NULL, FALSE);
5259
5260	view = gtk_text_btree_get_view (tree, view_id);
5261	g_return_val_if_fail (view != NULL, FALSE);
5262
5263	if (!_gtk_text_btree_is_valid (tree, view_id))
5264	{
5265	ValidateState state;
5266
5267	state.remaining_pixels = max_pixels;
5268	state.in_validation = FALSE;
5269	state.y = 0;
5270	state.old_height = 0;
5271	state.new_height = 0;
5272
5273	gtk_text_btree_node_validate (view,
5274	node: tree->root_node,
5275	view_id, state: &state);
5276
5277	if (y)
5278	*y = state.y;
5279	if (old_height)
5280	*old_height = state.old_height;
5281	if (new_height)
5282	*new_height = state.new_height;
5283
5284	#ifdef G_ENABLE_DEBUG
5285	if (GTK_DEBUG_CHECK (TEXT))
5286	_gtk_text_btree_check (tree);
5287	#endif
5288
5289	return TRUE;
5290	}
5291	else
5292	return FALSE;
5293	}
5294
5295	static void
5296	gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5297	gpointer view_id,
5298	int *width_out,
5299	int *height_out,
5300	gboolean *valid_out)
5301	{
5302	int width = 0;
5303	int height = 0;
5304	gboolean valid = TRUE;
5305
5306	if (node->level == 0)
5307	{
5308	GtkTextLine *line = node->children.line;
5309
5310	while (line != NULL)
5311	{
5312	GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5313
5314	if (!ld || !ld->valid)
5315	valid = FALSE;
5316
5317	if (ld)
5318	{
5319	width = MAX (ld->width, width);
5320	height += ld->height;
5321	}
5322
5323	line = line->next;
5324	}
5325	}
5326	else
5327	{
5328	GtkTextBTreeNode *child = node->children.node;
5329
5330	while (child)
5331	{
5332	NodeData *child_nd = node_data_find (nd: child->node_data, view_id);
5333
5334	if (!child_nd || !child_nd->valid)
5335	valid = FALSE;
5336
5337	if (child_nd)
5338	{
5339	width = MAX (child_nd->width, width);
5340	height += child_nd->height;
5341	}
5342
5343	child = child->next;
5344	}
5345	}
5346
5347	*width_out = width;
5348	*height_out = height;
5349	*valid_out = valid;
5350	}
5351
5352
5353	/* Recompute the validity and size of the view data for a given
5354	* view at this node from the immediate children of the node
5355	*/
5356	static NodeData *
5357	gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5358	gpointer view_id)
5359	{
5360	NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5361	gboolean valid;
5362	int width;
5363	int height;
5364
5365	gtk_text_btree_node_compute_view_aggregates (node, view_id,
5366	width_out: &width, height_out: &height, valid_out: &valid);
5367	nd->width = width;
5368	nd->height = height;
5369	nd->valid = valid;
5370
5371	return nd;
5372	}
5373
5374	static void
5375	gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5376	gpointer view_id)
5377	{
5378	while (node)
5379	{
5380	gtk_text_btree_node_check_valid (node, view_id);
5381	node = node->parent;
5382	}
5383	}
5384
5385	static NodeData *
5386	gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5387	gpointer view_id)
5388	{
5389	if (node->level == 0)
5390	{
5391	return gtk_text_btree_node_check_valid (node, view_id);
5392	}
5393	else
5394	{
5395	GtkTextBTreeNode *child = node->children.node;
5396
5397	NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5398
5399	nd->valid = TRUE;
5400	nd->width = 0;
5401	nd->height = 0;
5402
5403	while (child)
5404	{
5405	NodeData *child_nd = gtk_text_btree_node_check_valid_downward (node: child, view_id);
5406
5407	if (!child_nd->valid)
5408	nd->valid = FALSE;
5409	nd->width = MAX (child_nd->width, nd->width);
5410	nd->height += child_nd->height;
5411
5412	child = child->next;
5413	}
5414	return nd;
5415	}
5416	}
5417
5418
5419
5420	/**
5421	* _gtk_text_btree_validate_line:
5422	* @tree: a GtkTextBTree
5423	* @line: line to validate
5424	* @view_id: view ID for the view to validate
5425	*
5426	* Revalidate a single line of the btree for the given view, propagate
5427	* results up through the entire tree.
5428	**/
5429	void
5430	_gtk_text_btree_validate_line (GtkTextBTree *tree,
5431	GtkTextLine *line,
5432	gpointer view_id)
5433	{
5434	GtkTextLineData *ld;
5435	BTreeView *view;
5436
5437	g_return_if_fail (tree != NULL);
5438	g_return_if_fail (line != NULL);
5439
5440	view = gtk_text_btree_get_view (tree, view_id);
5441	g_return_if_fail (view != NULL);
5442
5443	ld = _gtk_text_line_get_data (line, view_id);
5444	if (!ld || !ld->valid)
5445	{
5446	gtk_text_layout_wrap (layout: view->layout, line, line_data: ld);
5447	gtk_text_btree_node_check_valid_upward (node: line->parent, view_id);
5448	}
5449	}
5450
5451	static void
5452	gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5453	{
5454	if (node->level == 0)
5455	{
5456	GtkTextLine *line;
5457
5458	line = node->children.line;
5459	while (line != NULL)
5460	{
5461	GtkTextLineData *ld;
5462
5463	ld = _gtk_text_line_remove_data (line, view_id);
5464
5465	if (ld)
5466	gtk_text_layout_free_line_data (layout: view->layout, line, line_data: ld);
5467
5468	line = line->next;
5469	}
5470	}
5471	else
5472	{
5473	GtkTextBTreeNode *child;
5474
5475	child = node->children.node;
5476
5477	while (child != NULL)
5478	{
5479	/* recurse */
5480	gtk_text_btree_node_remove_view (view, node: child, view_id);
5481
5482	child = child->next;
5483	}
5484	}
5485
5486	gtk_text_btree_node_remove_data (node, view_id);
5487	}
5488
5489	static void
5490	gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5491	{
5492	if (node->level == 0)
5493	{
5494	GtkTextLine *line;
5495	GtkTextLineSegment *seg;
5496
5497	while (node->children.line != NULL)
5498	{
5499	line = node->children.line;
5500	node->children.line = line->next;
5501	while (line->segments != NULL)
5502	{
5503	seg = line->segments;
5504	line->segments = seg->next;
5505
5506	(*seg->type->deleteFunc) (seg, line, TRUE);
5507	}
5508	gtk_text_line_destroy (tree, line);
5509	}
5510	}
5511	else
5512	{
5513	GtkTextBTreeNode *childPtr;
5514
5515	while (node->children.node != NULL)
5516	{
5517	childPtr = node->children.node;
5518	node->children.node = childPtr->next;
5519	gtk_text_btree_node_destroy (tree, node: childPtr);
5520	}
5521	}
5522
5523	gtk_text_btree_node_free_empty (tree, node);
5524	}
5525
5526	static void
5527	gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5528	GtkTextBTreeNode *node)
5529	{
5530	g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5531	(node->level == 0 && node->children.line == NULL));
5532
5533	summary_list_destroy (summary: node->summary);
5534	node_data_list_destroy (nd: node->node_data);
5535	g_slice_free (GtkTextBTreeNode, node);
5536	}
5537
5538	static NodeData*
5539	gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5540	{
5541	NodeData *nd;
5542
5543	nd = node_data_find (nd: node->node_data, view_id);
5544
5545	if (nd == NULL)
5546	nd = node->node_data = node_data_new (view_id, next: node->node_data);
5547
5548	return nd;
5549	}
5550
5551	static void
5552	gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5553	{
5554	NodeData *nd;
5555	NodeData *prev;
5556
5557	prev = NULL;
5558	nd = node->node_data;
5559	while (nd != NULL)
5560	{
5561	if (nd->view_id == view_id)
5562	break;
5563
5564	prev = nd;
5565	nd = nd->next;
5566	}
5567
5568	if (nd == NULL)
5569	return;
5570
5571	if (prev != NULL)
5572	prev->next = nd->next;
5573
5574	if (node->node_data == nd)
5575	node->node_data = nd->next;
5576
5577	nd->next = NULL;
5578
5579	node_data_destroy (nd);
5580	}
5581
5582	static void
5583	gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5584	int *width, int *height)
5585	{
5586	NodeData *nd;
5587
5588	g_return_if_fail (width != NULL);
5589	g_return_if_fail (height != NULL);
5590
5591	nd = gtk_text_btree_node_ensure_data (node, view_id);
5592
5593	if (width)
5594	*width = nd->width;
5595	if (height)
5596	*height = nd->height;
5597	}
5598
5599	/* Find the closest common ancestor of the two nodes. FIXME: The interface
5600	* here isn’t quite right, since for a lot of operations we want to
5601	* know which children of the common parent correspond to the two nodes
5602	* (e.g., when computing the order of two iters)
5603	*/
5604	static GtkTextBTreeNode *
5605	gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5606	GtkTextBTreeNode *node2)
5607	{
5608	while (node1->level < node2->level)
5609	node1 = node1->parent;
5610	while (node2->level < node1->level)
5611	node2 = node2->parent;
5612	while (node1 != node2)
5613	{
5614	node1 = node1->parent;
5615	node2 = node2->parent;
5616	}
5617
5618	return node1;
5619	}
5620
5621	/*
5622	* BTree
5623	*/
5624
5625	static BTreeView*
5626	gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5627	{
5628	BTreeView *view;
5629
5630	view = tree->views;
5631	while (view != NULL)
5632	{
5633	if (view->view_id == view_id)
5634	break;
5635	view = view->next;
5636	}
5637
5638	return view;
5639	}
5640
5641	static void
5642	get_tree_bounds (GtkTextBTree *tree,
5643	GtkTextIter *start,
5644	GtkTextIter *end)
5645	{
5646	_gtk_text_btree_get_iter_at_line_char (tree, iter: start, line_number: 0, char_index: 0);
5647	_gtk_text_btree_get_end_iter (tree, iter: end);
5648	}
5649
5650	static void
5651	tag_changed_cb (GtkTextTagTable *table,
5652	GtkTextTag *tag,
5653	gboolean size_changed,
5654	GtkTextBTree *tree)
5655	{
5656	if (size_changed)
5657	{
5658	/* We need to queue a relayout on all regions that are tagged with
5659	* this tag.
5660	*/
5661
5662	GtkTextIter start;
5663	GtkTextIter end;
5664
5665	if (_gtk_text_btree_get_iter_at_first_toggle (tree, iter: &start, tag))
5666	{
5667	/* Must be a last toggle if there was a first one. */
5668	_gtk_text_btree_get_iter_at_last_toggle (tree, iter: &end, tag);
5669	DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5670	_gtk_text_btree_invalidate_region (tree, start: &start, end: &end, FALSE);
5671
5672	}
5673	}
5674	else
5675	{
5676	/* We only need to queue a redraw, not a relayout */
5677	BTreeView *view;
5678
5679	view = tree->views;
5680
5681	while (view != NULL)
5682	{
5683	int width = 0;
5684	int height = 0;
5685
5686	_gtk_text_btree_get_view_size (tree, view_id: view->view_id, width: &width, height: &height);
5687	gtk_text_layout_changed (layout: view->layout, y: 0, old_height: height, new_height: height);
5688
5689	view = view->next;
5690	}
5691	}
5692	}
5693
5694	void
5695	_gtk_text_btree_notify_will_remove_tag (GtkTextBTree *tree,
5696	GtkTextTag *tag)
5697	{
5698	/* Remove the tag from the tree */
5699
5700	GtkTextIter start;
5701	GtkTextIter end;
5702
5703	get_tree_bounds (tree, start: &start, end: &end);
5704
5705	_gtk_text_btree_tag (start_orig: &start, end_orig: &end, tag, FALSE);
5706	gtk_text_btree_remove_tag_info (tree, tag);
5707	}
5708
5709
5710	/* Rebalance the out-of-whack node "node" */
5711	static void
5712	gtk_text_btree_rebalance (GtkTextBTree *tree,
5713	GtkTextBTreeNode *node)
5714	{
5715	/*
5716	* Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5717	* up through the tree one GtkTextBTreeNode at a time until the root
5718	* GtkTextBTreeNode has been processed.
5719	*/
5720
5721	while (node != NULL)
5722	{
5723	GtkTextBTreeNode *new_node, *child;
5724	GtkTextLine *line;
5725	int i;
5726
5727	/*
5728	* Check to see if the GtkTextBTreeNode has too many children. If it does,
5729	* then split off all but the first MIN_CHILDREN into a separate
5730	* GtkTextBTreeNode following the original one. Then repeat until the
5731	* GtkTextBTreeNode has a decent size.
5732	*/
5733
5734	if (node->num_children > MAX_CHILDREN)
5735	{
5736	while (1)
5737	{
5738	/*
5739	* If the GtkTextBTreeNode being split is the root
5740	* GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5741	* it first.
5742	*/
5743
5744	if (node->parent == NULL)
5745	{
5746	new_node = gtk_text_btree_node_new ();
5747	new_node->parent = NULL;
5748	new_node->next = NULL;
5749	new_node->summary = NULL;
5750	new_node->level = node->level + 1;
5751	new_node->children.node = node;
5752	recompute_node_counts (tree, node: new_node);
5753	tree->root_node = new_node;
5754	}
5755	new_node = gtk_text_btree_node_new ();
5756	new_node->parent = node->parent;
5757	new_node->next = node->next;
5758	node->next = new_node;
5759	new_node->summary = NULL;
5760	new_node->level = node->level;
5761	new_node->num_children = node->num_children - MIN_CHILDREN;
5762	if (node->level == 0)
5763	{
5764	for (i = MIN_CHILDREN-1,
5765	line = node->children.line;
5766	i > 0; i--, line = line->next)
5767	{
5768	/* Empty loop body. */
5769	}
5770	new_node->children.line = line->next;
5771	line->next = NULL;
5772	}
5773	else
5774	{
5775	for (i = MIN_CHILDREN-1,
5776	child = node->children.node;
5777	i > 0; i--, child = child->next)
5778	{
5779	/* Empty loop body. */
5780	}
5781	new_node->children.node = child->next;
5782	child->next = NULL;
5783	}
5784	recompute_node_counts (tree, node);
5785	node->parent->num_children++;
5786	node = new_node;
5787	if (node->num_children <= MAX_CHILDREN)
5788	{
5789	recompute_node_counts (tree, node);
5790	break;
5791	}
5792	}
5793	}
5794
5795	while (node->num_children < MIN_CHILDREN)
5796	{
5797	GtkTextBTreeNode *other;
5798	GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5799	GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5800	int total_children, first_children;
5801
5802	/*
5803	* Too few children for this GtkTextBTreeNode. If this is the root then,
5804	* it's OK for it to have less than MIN_CHILDREN children
5805	* as long as it's got at least two. If it has only one
5806	* (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5807	* the tree and use its child as the new root.
5808	*/
5809
5810	if (node->parent == NULL)
5811	{
5812	if ((node->num_children == 1) && (node->level > 0))
5813	{
5814	tree->root_node = node->children.node;
5815	tree->root_node->parent = NULL;
5816
5817	node->children.node = NULL;
5818	gtk_text_btree_node_free_empty (tree, node);
5819	}
5820	return;
5821	}
5822
5823	/*
5824	* Not the root. Make sure that there are siblings to
5825	* balance with.
5826	*/
5827
5828	if (node->parent->num_children < 2)
5829	{
5830	gtk_text_btree_rebalance (tree, node: node->parent);
5831	continue;
5832	}
5833
5834	/*
5835	* Find a sibling neighbor to borrow from, and arrange for
5836	* node to be the earlier of the pair.
5837	*/
5838
5839	if (node->next == NULL)
5840	{
5841	for (other = node->parent->children.node;
5842	other->next != node;
5843	other = other->next)
5844	{
5845	/* Empty loop body. */
5846	}
5847	node = other;
5848	}
5849	other = node->next;
5850
5851	/*
5852	* We're going to either merge the two siblings together
5853	* into one GtkTextBTreeNode or redivide the children among them to
5854	* balance their loads. As preparation, join their two
5855	* child lists into a single list and remember the half-way
5856	* point in the list.
5857	*/
5858
5859	total_children = node->num_children + other->num_children;
5860	first_children = total_children/2;
5861	if (node->children.node == NULL)
5862	{
5863	node->children = other->children;
5864	other->children.node = NULL;
5865	other->children.line = NULL;
5866	}
5867	if (node->level == 0)
5868	{
5869	GtkTextLine *line2;
5870
5871	for (line2 = node->children.line, i = 1;
5872	line2->next != NULL;
5873	line2 = line2->next, i++)
5874	{
5875	if (i == first_children)
5876	{
5877	halfwayline = line2;
5878	}
5879	}
5880	line2->next = other->children.line;
5881	while (i <= first_children)
5882	{
5883	halfwayline = line2;
5884	line2 = line2->next;
5885	i++;
5886	}
5887	}
5888	else
5889	{
5890	GtkTextBTreeNode *child2;
5891
5892	for (child2 = node->children.node, i = 1;
5893	child2->next != NULL;
5894	child2 = child2->next, i++)
5895	{
5896	if (i <= first_children)
5897	{
5898	if (i == first_children)
5899	{
5900	halfwaynode = child2;
5901	}
5902	}
5903	}
5904	child2->next = other->children.node;
5905	while (i <= first_children)
5906	{
5907	halfwaynode = child2;
5908	child2 = child2->next;
5909	i++;
5910	}
5911	}
5912
5913	/*
5914	* If the two siblings can simply be merged together, do it.
5915	*/
5916
5917	if (total_children <= MAX_CHILDREN)
5918	{
5919	recompute_node_counts (tree, node);
5920	node->next = other->next;
5921	node->parent->num_children--;
5922
5923	other->children.node = NULL;
5924	other->children.line = NULL;
5925	gtk_text_btree_node_free_empty (tree, node: other);
5926	continue;
5927	}
5928
5929	/*
5930	* The siblings can't be merged, so just divide their
5931	* children evenly between them.
5932	*/
5933
5934	if (node->level == 0)
5935	{
5936	other->children.line = halfwayline->next;
5937	halfwayline->next = NULL;
5938	}
5939	else
5940	{
5941	other->children.node = halfwaynode->next;
5942	halfwaynode->next = NULL;
5943	}
5944
5945	recompute_node_counts (tree, node);
5946	recompute_node_counts (tree, node: other);
5947	}
5948
5949	node = node->parent;
5950	}
5951	}
5952
5953	static void
5954	post_insert_fixup (GtkTextBTree *tree,
5955	GtkTextLine *line,
5956	int line_count_delta,
5957	int char_count_delta)
5958
5959	{
5960	GtkTextBTreeNode *node;
5961
5962	/*
5963	* Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5964	* point, then rebalance the tree if necessary.
5965	*/
5966
5967	for (node = line->parent ; node != NULL;
5968	node = node->parent)
5969	{
5970	node->num_lines += line_count_delta;
5971	node->num_chars += char_count_delta;
5972	}
5973	node = line->parent;
5974	node->num_children += line_count_delta;
5975
5976	if (node->num_children > MAX_CHILDREN)
5977	{
5978	gtk_text_btree_rebalance (tree, node);
5979	}
5980
5981	#ifdef G_ENABLE_DEBUG
5982	if (GTK_DEBUG_CHECK (TEXT))
5983	_gtk_text_btree_check (tree);
5984	#endif
5985	}
5986
5987	static GtkTextTagInfo*
5988	gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5989	GtkTextTag *tag)
5990	{
5991	GtkTextTagInfo *info;
5992	GSList *list;
5993
5994
5995	list = tree->tag_infos;
5996	while (list != NULL)
5997	{
5998	info = list->data;
5999	if (info->tag == tag)
6000	return info;
6001
6002	list = list->next;
6003	}
6004
6005	return NULL;
6006	}
6007
6008	static GtkTextTagInfo*
6009	gtk_text_btree_get_tag_info (GtkTextBTree *tree,
6010	GtkTextTag *tag)
6011	{
6012	GtkTextTagInfo *info;
6013
6014	info = gtk_text_btree_get_existing_tag_info (tree, tag);
6015
6016	if (info == NULL)
6017	{
6018	/* didn't find it, create. */
6019
6020	info = g_slice_new (GtkTextTagInfo);
6021
6022	info->tag = tag;
6023	g_object_ref (tag);
6024	info->tag_root = NULL;
6025	info->toggle_count = 0;
6026
6027	tree->tag_infos = g_slist_prepend (list: tree->tag_infos, data: info);
6028	}
6029
6030	return info;
6031	}
6032
6033	static void
6034	gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
6035	GtkTextTag *tag)
6036	{
6037	GtkTextTagInfo *info;
6038	GSList *list;
6039	GSList *prev;
6040
6041	prev = NULL;
6042	list = tree->tag_infos;
6043	while (list != NULL)
6044	{
6045	info = list->data;
6046	if (info->tag == tag)
6047	{
6048	if (prev != NULL)
6049	{
6050	prev->next = list->next;
6051	}
6052	else
6053	{
6054	tree->tag_infos = list->next;
6055	}
6056	list->next = NULL;
6057	g_slist_free (list);
6058
6059	g_object_unref (object: info->tag);
6060
6061	g_slice_free (GtkTextTagInfo, info);
6062	return;
6063	}
6064
6065	prev = list;
6066	list = list->next;
6067	}
6068	}
6069
6070	static void
6071	recompute_level_zero_counts (GtkTextBTreeNode *node)
6072	{
6073	GtkTextLine *line;
6074	GtkTextLineSegment *seg;
6075
6076	g_assert (node->level == 0);
6077
6078	line = node->children.line;
6079	while (line != NULL)
6080	{
6081	node->num_children++;
6082	node->num_lines++;
6083
6084	if (line->parent != node)
6085	gtk_text_line_set_parent (line, node);
6086
6087	seg = line->segments;
6088	while (seg != NULL)
6089	{
6090
6091	node->num_chars += seg->char_count;
6092
6093	if (((seg->type != &gtk_text_toggle_on_type)
6094	&& (seg->type != &gtk_text_toggle_off_type))
6095	|| !(seg->body.toggle.inNodeCounts))
6096	{
6097	; /* nothing */
6098	}
6099	else
6100	{
6101	GtkTextTagInfo *info;
6102
6103	info = seg->body.toggle.info;
6104
6105	gtk_text_btree_node_adjust_toggle_count (node, info, adjust: 1);
6106	}
6107
6108	seg = seg->next;
6109	}
6110
6111	line = line->next;
6112	}
6113	}
6114
6115	static void
6116	recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6117	{
6118	Summary *summary;
6119	GtkTextBTreeNode *child;
6120
6121	g_assert (node->level > 0);
6122
6123	child = node->children.node;
6124	while (child != NULL)
6125	{
6126	node->num_children += 1;
6127	node->num_lines += child->num_lines;
6128	node->num_chars += child->num_chars;
6129
6130	if (child->parent != node)
6131	{
6132	child->parent = node;
6133	gtk_text_btree_node_invalidate_upward (node, NULL);
6134	}
6135
6136	summary = child->summary;
6137	while (summary != NULL)
6138	{
6139	gtk_text_btree_node_adjust_toggle_count (node,
6140	info: summary->info,
6141	adjust: summary->toggle_count);
6142
6143	summary = summary->next;
6144	}
6145
6146	child = child->next;
6147	}
6148	}
6149
6150	/*
6151	*----------------------------------------------------------------------
6152	*
6153	* recompute_node_counts --
6154	*
6155	* This procedure is called to recompute all the counts in a GtkTextBTreeNode
6156	* (tags, child information, etc.) by scanning the information in
6157	* its descendants. This procedure is called during rebalancing
6158	* when a GtkTextBTreeNode’s child structure has changed.
6159	*
6160	* Results:
6161	* None.
6162	*
6163	* Side effects:
6164	* The tag counts for node are modified to reflect its current
6165	* child structure, as are its num_children, num_lines, num_chars fields.
6166	* Also, all of the childrens’ parent fields are made to point
6167	* to node.
6168	*
6169	*----------------------------------------------------------------------
6170	*/
6171
6172	static void
6173	recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6174	{
6175	BTreeView *view;
6176	Summary *summary, *summary2;
6177
6178	/*
6179	* Zero out all the existing counts for the GtkTextBTreeNode, but don’t delete
6180	* the existing Summary records (most of them will probably be reused).
6181	*/
6182
6183	summary = node->summary;
6184	while (summary != NULL)
6185	{
6186	summary->toggle_count = 0;
6187	summary = summary->next;
6188	}
6189
6190	node->num_children = 0;
6191	node->num_lines = 0;
6192	node->num_chars = 0;
6193
6194	/*
6195	* Scan through the children, adding the childrens’ tag counts into
6196	* the GtkTextBTreeNode’s tag counts and adding new Summary structures if
6197	* necessary.
6198	*/
6199
6200	if (node->level == 0)
6201	recompute_level_zero_counts (node);
6202	else
6203	recompute_level_nonzero_counts (node);
6204
6205	view = tree->views;
6206	while (view)
6207	{
6208	gtk_text_btree_node_check_valid (node, view_id: view->view_id);
6209	view = view->next;
6210	}
6211
6212	/*
6213	* Scan through the GtkTextBTreeNode’s tag records again and delete any Summary
6214	* records that still have a zero count, or that have all the toggles.
6215	* The GtkTextBTreeNode with the children that account for all the tags toggles
6216	* have no summary information, and they become the tag_root for the tag.
6217	*/
6218
6219	summary2 = NULL;
6220	for (summary = node->summary; summary != NULL; )
6221	{
6222	if (summary->toggle_count > 0 &&
6223	summary->toggle_count < summary->info->toggle_count)
6224	{
6225	if (node->level == summary->info->tag_root->level)
6226	{
6227	/*
6228	* The tag’s root GtkTextBTreeNode split and some toggles left.
6229	* The tag root must move up a level.
6230	*/
6231	summary->info->tag_root = node->parent;
6232	}
6233	summary2 = summary;
6234	summary = summary->next;
6235	continue;
6236	}
6237	if (summary->toggle_count == summary->info->toggle_count)
6238	{
6239	/*
6240	* A GtkTextBTreeNode merge has collected all the toggles under
6241	* one GtkTextBTreeNode. Push the root down to this level.
6242	*/
6243	summary->info->tag_root = node;
6244	}
6245	if (summary2 != NULL)
6246	{
6247	summary2->next = summary->next;
6248	summary_destroy (summary);
6249	summary = summary2->next;
6250	}
6251	else
6252	{
6253	node->summary = summary->next;
6254	summary_destroy (summary);
6255	summary = node->summary;
6256	}
6257	}
6258	}
6259
6260	void
6261	_gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6262	GtkTextTagInfo *info,
6263	int delta) /* may be negative */
6264	{
6265	Summary *summary, *prevPtr;
6266	GtkTextBTreeNode *node2Ptr;
6267	int rootLevel; /* Level of original tag root */
6268
6269	info->toggle_count += delta;
6270
6271	if (info->tag_root == (GtkTextBTreeNode *) NULL)
6272	{
6273	info->tag_root = node;
6274	return;
6275	}
6276
6277	/*
6278	* Note the level of the existing root for the tag so we can detect
6279	* if it needs to be moved because of the toggle count change.
6280	*/
6281
6282	rootLevel = info->tag_root->level;
6283
6284	/*
6285	* Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6286	* summary counts at each GtkTextBTreeNode and moving the tag’s root upwards if
6287	* necessary.
6288	*/
6289
6290	for ( ; node != info->tag_root; node = node->parent)
6291	{
6292	/*
6293	* See if there’s already an entry for this tag for this GtkTextBTreeNode. If so,
6294	* perhaps all we have to do is adjust its count.
6295	*/
6296
6297	for (prevPtr = NULL, summary = node->summary;
6298	summary != NULL;
6299	prevPtr = summary, summary = summary->next)
6300	{
6301	if (summary->info == info)
6302	{
6303	break;
6304	}
6305	}
6306	if (summary != NULL)
6307	{
6308	summary->toggle_count += delta;
6309	if (summary->toggle_count > 0 &&
6310	summary->toggle_count < info->toggle_count)
6311	{
6312	continue;
6313	}
6314	if (summary->toggle_count != 0)
6315	{
6316	/*
6317	* Should never find a GtkTextBTreeNode with max toggle count at this
6318	* point (there shouldn’t have been a summary entry in the
6319	* first place).
6320	*/
6321
6322	g_error ("%s: bad toggle count (%d) max (%d)",
6323	G_STRLOC, summary->toggle_count, info->toggle_count);
6324	}
6325
6326	/*
6327	* Zero toggle count; must remove this tag from the list.
6328	*/
6329
6330	if (prevPtr == NULL)
6331	{
6332	node->summary = summary->next;
6333	}
6334	else
6335	{
6336	prevPtr->next = summary->next;
6337	}
6338	summary_destroy (summary);
6339	}
6340	else
6341	{
6342	/*
6343	* This tag isn’t currently in the summary information list.
6344	*/
6345
6346	if (rootLevel == node->level)
6347	{
6348
6349	/*
6350	* The old tag root is at the same level in the tree as this
6351	* GtkTextBTreeNode, but it isn’t at this GtkTextBTreeNode. Move the tag root up
6352	* a level, in the hopes that it will now cover this GtkTextBTreeNode
6353	* as well as the old root (if not, we’ll move it up again
6354	* the next time through the loop). To push it up one level
6355	* we copy the original toggle count into the summary
6356	* information at the old root and change the root to its
6357	* parent GtkTextBTreeNode.
6358	*/
6359
6360	GtkTextBTreeNode *rootnode = info->tag_root;
6361	summary = g_slice_new (Summary);
6362	summary->info = info;
6363	summary->toggle_count = info->toggle_count - delta;
6364	summary->next = rootnode->summary;
6365	rootnode->summary = summary;
6366	rootnode = rootnode->parent;
6367	rootLevel = rootnode->level;
6368	info->tag_root = rootnode;
6369	}
6370	summary = g_slice_new (Summary);
6371	summary->info = info;
6372	summary->toggle_count = delta;
6373	summary->next = node->summary;
6374	node->summary = summary;
6375	}
6376	}
6377
6378	/*
6379	* If we’ve decremented the toggle count, then it may be necessary
6380	* to push the tag root down one or more levels.
6381	*/
6382
6383	if (delta >= 0)
6384	{
6385	return;
6386	}
6387	if (info->toggle_count == 0)
6388	{
6389	info->tag_root = (GtkTextBTreeNode *) NULL;
6390	return;
6391	}
6392	node = info->tag_root;
6393	while (node->level > 0)
6394	{
6395	/*
6396	* See if a single child GtkTextBTreeNode accounts for all of the tag’s
6397	* toggles. If so, push the root down one level.
6398	*/
6399
6400	for (node2Ptr = node->children.node;
6401	node2Ptr != (GtkTextBTreeNode *)NULL ;
6402	node2Ptr = node2Ptr->next)
6403	{
6404	for (prevPtr = NULL, summary = node2Ptr->summary;
6405	summary != NULL;
6406	prevPtr = summary, summary = summary->next)
6407	{
6408	if (summary->info == info)
6409	{
6410	break;
6411	}
6412	}
6413	if (summary == NULL)
6414	{
6415	continue;
6416	}
6417	if (summary->toggle_count != info->toggle_count)
6418	{
6419	/*
6420	* No GtkTextBTreeNode has all toggles, so the root is still valid.
6421	*/
6422
6423	return;
6424	}
6425
6426	/*
6427	* This GtkTextBTreeNode has all the toggles, so push down the root.
6428	*/
6429
6430	if (prevPtr == NULL)
6431	{
6432	node2Ptr->summary = summary->next;
6433	}
6434	else
6435	{
6436	prevPtr->next = summary->next;
6437	}
6438	summary_destroy (summary);
6439	info->tag_root = node2Ptr;
6440	break;
6441	}
6442	node = info->tag_root;
6443	}
6444	}
6445
6446	/*
6447	*----------------------------------------------------------------------
6448	*
6449	* inc_count --
6450	*
6451	* This is a utility procedure used by _gtk_text_btree_get_tags. It
6452	* increments the count for a particular tag, adding a new
6453	* entry for that tag if there wasn’t one previously.
6454	*
6455	* Results:
6456	* None.
6457	*
6458	* Side effects:
6459	* The information at *tagInfoPtr may be modified, and the arrays
6460	* may be reallocated to make them larger.
6461	*
6462	*----------------------------------------------------------------------
6463	*/
6464
6465	static void
6466	inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6467	{
6468	for (int i = 0; i < tagInfoPtr->tags->len; i++)
6469	{
6470	GtkTextTag *t = g_ptr_array_index (tagInfoPtr->tags, i);
6471	if (t == tag)
6472	{
6473	g_array_index (tagInfoPtr->counts, int, i) += inc;
6474	return;
6475	}
6476	}
6477
6478	/*
6479	* There isn’t currently an entry for this tag, so we have to
6480	* make a new one. If the arrays are full, then enlarge the
6481	* arrays first.
6482	*/
6483
6484	g_ptr_array_add (array: tagInfoPtr->tags, data: tag);
6485	g_array_append_val (tagInfoPtr->counts, inc);
6486	}
6487
6488	static void
6489	gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6490	const GtkTextIter *iter)
6491	{
6492	GtkTextLineSegment *prev;
6493	GtkTextLine *line;
6494	GtkTextBTree *tree;
6495
6496	line = _gtk_text_iter_get_text_line (iter);
6497	tree = _gtk_text_iter_get_btree (iter);
6498
6499	prev = gtk_text_line_segment_split (iter);
6500	if (prev == NULL)
6501	{
6502	seg->next = line->segments;
6503	line->segments = seg;
6504	}
6505	else
6506	{
6507	seg->next = prev->next;
6508	prev->next = seg;
6509	}
6510	cleanup_line (line);
6511	segments_changed (tree);
6512
6513	#ifdef G_ENABLE_DEBUG
6514	if (GTK_DEBUG_CHECK (TEXT))
6515	_gtk_text_btree_check (tree);
6516	#endif
6517	}
6518
6519	static void
6520	gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6521	GtkTextLineSegment *seg,
6522	GtkTextLine *line)
6523	{
6524	GtkTextLineSegment *prev;
6525
6526	if (line->segments == seg)
6527	{
6528	line->segments = seg->next;
6529	}
6530	else
6531	{
6532	for (prev = line->segments; prev->next != seg;
6533	prev = prev->next)
6534	{
6535	/* Empty loop body. */
6536	}
6537	prev->next = seg->next;
6538	}
6539	cleanup_line (line);
6540	segments_changed (tree);
6541	}
6542
6543	/*
6544	* This is here because it requires BTree internals, it logically
6545	* belongs in gtktextsegment.c
6546	*/
6547
6548
6549	/*
6550	*--------------------------------------------------------------
6551	*
6552	* _gtk_toggle_segment_check_func --
6553	*
6554	* This procedure is invoked to perform consistency checks
6555	* on toggle segments.
6556	*
6557	* Results:
6558	* None.
6559	*
6560	* Side effects:
6561	* If a consistency problem is found the procedure g_errors.
6562	*
6563	*--------------------------------------------------------------
6564	*/
6565
6566	void
6567	_gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6568	GtkTextLine *line)
6569	{
6570	Summary *summary;
6571	int needSummary;
6572
6573	if (segPtr->byte_count != 0)
6574	{
6575	g_error ("toggle_segment_check_func: segment had non-zero size");
6576	}
6577	if (!segPtr->body.toggle.inNodeCounts)
6578	{
6579	g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6580	}
6581	needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6582	for (summary = line->parent->summary; ;
6583	summary = summary->next)
6584	{
6585	if (summary == NULL)
6586	{
6587	if (needSummary)
6588	{
6589	g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6590	}
6591	else
6592	{
6593	break;
6594	}
6595	}
6596	if (summary->info == segPtr->body.toggle.info)
6597	{
6598	if (!needSummary)
6599	{
6600	g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6601	}
6602	break;
6603	}
6604	}
6605	}
6606
6607	/*
6608	* Debug
6609	*/
6610	#ifdef G_ENABLE_DEBUG
6611	static void
6612	gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6613	GtkTextBTreeNode *node,
6614	NodeData *nd)
6615	{
6616	int width;
6617	int height;
6618	gboolean valid;
6619	BTreeView *view;
6620
6621	view = tree->views;
6622
6623	while (view != NULL)
6624	{
6625	if (view->view_id == nd->view_id)
6626	break;
6627
6628	view = view->next;
6629	}
6630
6631	if (view == NULL)
6632	g_error ("Node has data for a view %p no longer attached to the tree",
6633	nd->view_id);
6634
6635	gtk_text_btree_node_compute_view_aggregates (node, view_id: nd->view_id,
6636	width_out: &width, height_out: &height, valid_out: &valid);
6637
6638	/* valid aggregate not checked the same as width/height, because on
6639	* btree rebalance we can have invalid nodes where all lines below
6640	* them are actually valid, due to moving lines around between
6641	* nodes.
6642	*
6643	* The guarantee is that if there are invalid lines the node is
6644	* invalid - we don’t guarantee that if the node is invalid there
6645	* are invalid lines.
6646	*/
6647
6648	if (nd->width != width ||
6649	nd->height != height ||
6650	(nd->valid && !valid))
6651	{
6652	g_error ("Node aggregates for view %p are invalid:\n"
6653	"Are (%d,%d,%s), should be (%d,%d,%s)",
6654	nd->view_id,
6655	nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6656	width, height, valid ? "TRUE" : "FALSE");
6657	}
6658	}
6659
6660	static void
6661	gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6662	GtkTextBTreeNode *node)
6663	{
6664	GtkTextBTreeNode *childnode;
6665	Summary *summary, *summary2;
6666	GtkTextLine *line;
6667	GtkTextLineSegment *segPtr;
6668	int num_children, num_lines, num_chars, toggle_count, min_children;
6669	GtkTextLineData *ld;
6670	NodeData *nd;
6671
6672	if (node->parent != NULL)
6673	{
6674	min_children = MIN_CHILDREN;
6675	}
6676	else if (node->level > 0)
6677	{
6678	min_children = 2;
6679	}
6680	else {
6681	min_children = 1;
6682	}
6683	if ((node->num_children < min_children)
6684	|| (node->num_children > MAX_CHILDREN))
6685	{
6686	g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6687	node->num_children);
6688	}
6689
6690	nd = node->node_data;
6691	while (nd != NULL)
6692	{
6693	gtk_text_btree_node_view_check_consistency (tree, node, nd);
6694	nd = nd->next;
6695	}
6696
6697	num_children = 0;
6698	num_lines = 0;
6699	num_chars = 0;
6700	if (node->level == 0)
6701	{
6702	for (line = node->children.line; line != NULL;
6703	line = line->next)
6704	{
6705	if (line->parent != node)
6706	{
6707	g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6708	}
6709	if (line->segments == NULL)
6710	{
6711	g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6712	}
6713
6714	ld = line->views;
6715	while (ld != NULL)
6716	{
6717	/* Just ensuring we don’t segv while doing this loop */
6718
6719	ld = ld->next;
6720	}
6721
6722	for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6723	{
6724	if (segPtr->type->checkFunc != NULL)
6725	{
6726	(*segPtr->type->checkFunc)(segPtr, line);
6727	}
6728	if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6729	&& (segPtr->next != NULL)
6730	&& (segPtr->next->byte_count == 0)
6731	&& (segPtr->next->type->leftGravity))
6732	{
6733	g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6734	}
6735	if ((segPtr->next == NULL)
6736	&& (segPtr->type != &gtk_text_char_type))
6737	{
6738	g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6739	}
6740
6741	num_chars += segPtr->char_count;
6742	}
6743
6744	num_children++;
6745	num_lines++;
6746	}
6747	}
6748	else
6749	{
6750	for (childnode = node->children.node; childnode != NULL;
6751	childnode = childnode->next)
6752	{
6753	if (childnode->parent != node)
6754	{
6755	g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6756	}
6757	if (childnode->level != (node->level-1))
6758	{
6759	g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6760	node->level, childnode->level);
6761	}
6762	gtk_text_btree_node_check_consistency (tree, node: childnode);
6763	for (summary = childnode->summary; summary != NULL;
6764	summary = summary->next)
6765	{
6766	for (summary2 = node->summary; ;
6767	summary2 = summary2->next)
6768	{
6769	if (summary2 == NULL)
6770	{
6771	if (summary->info->tag_root == node)
6772	{
6773	break;
6774	}
6775	g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6776	summary->info->tag->priv->name,
6777	"present in parent summaries");
6778	}
6779	if (summary->info == summary2->info)
6780	{
6781	break;
6782	}
6783	}
6784	}
6785	num_children++;
6786	num_lines += childnode->num_lines;
6787	num_chars += childnode->num_chars;
6788	}
6789	}
6790	if (num_children != node->num_children)
6791	{
6792	g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6793	num_children, node->num_children);
6794	}
6795	if (num_lines != node->num_lines)
6796	{
6797	g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6798	num_lines, node->num_lines);
6799	}
6800	if (num_chars != node->num_chars)
6801	{
6802	g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6803	num_chars, node->num_chars);
6804	}
6805
6806	for (summary = node->summary; summary != NULL;
6807	summary = summary->next)
6808	{
6809	if (summary->info->toggle_count == summary->toggle_count)
6810	{
6811	g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6812	summary->info->tag->priv->name);
6813	}
6814	toggle_count = 0;
6815	if (node->level == 0)
6816	{
6817	for (line = node->children.line; line != NULL;
6818	line = line->next)
6819	{
6820	for (segPtr = line->segments; segPtr != NULL;
6821	segPtr = segPtr->next)
6822	{
6823	if ((segPtr->type != &gtk_text_toggle_on_type)
6824	&& (segPtr->type != &gtk_text_toggle_off_type))
6825	{
6826	continue;
6827	}
6828	if (segPtr->body.toggle.info == summary->info)
6829	{
6830	if (!segPtr->body.toggle.inNodeCounts)
6831	g_error ("Toggle segment not in the node counts");
6832
6833	toggle_count ++;
6834	}
6835	}
6836	}
6837	}
6838	else
6839	{
6840	for (childnode = node->children.node;
6841	childnode != NULL;
6842	childnode = childnode->next)
6843	{
6844	for (summary2 = childnode->summary;
6845	summary2 != NULL;
6846	summary2 = summary2->next)
6847	{
6848	if (summary2->info == summary->info)
6849	{
6850	toggle_count += summary2->toggle_count;
6851	}
6852	}
6853	}
6854	}
6855	if (toggle_count != summary->toggle_count)
6856	{
6857	g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6858	toggle_count, summary->toggle_count);
6859	}
6860	for (summary2 = summary->next; summary2 != NULL;
6861	summary2 = summary2->next)
6862	{
6863	if (summary2->info == summary->info)
6864	{
6865	g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6866	summary->info->tag->priv->name);
6867	}
6868	}
6869	}
6870	}
6871
6872	static void
6873	listify_foreach (GtkTextTag *tag, gpointer user_data)
6874	{
6875	GSList** listp = user_data;
6876
6877	*listp = g_slist_prepend (list: *listp, data: tag);
6878	}
6879
6880	static GSList*
6881	list_of_tags (GtkTextTagTable *table)
6882	{
6883	GSList *list = NULL;
6884
6885	gtk_text_tag_table_foreach (table, func: listify_foreach, data: &list);
6886
6887	return list;
6888	}
6889
6890	void
6891	_gtk_text_btree_check (GtkTextBTree *tree)
6892	{
6893	Summary *summary;
6894	GtkTextBTreeNode *node;
6895	GtkTextLine *line;
6896	GtkTextLineSegment *seg;
6897	GtkTextTag *tag;
6898	GSList *all_tags, *taglist = NULL;
6899	int count;
6900	GtkTextTagInfo *info;
6901
6902	/*
6903	* Make sure that the tag toggle counts and the tag root pointers are OK.
6904	*/
6905	all_tags = list_of_tags (table: tree->table);
6906	for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6907	{
6908	tag = taglist->data;
6909	info = gtk_text_btree_get_existing_tag_info (tree, tag);
6910	if (info != NULL)
6911	{
6912	node = info->tag_root;
6913	if (node == NULL)
6914	{
6915	if (info->toggle_count != 0)
6916	{
6917	g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6918	tag->priv->name, info->toggle_count);
6919	}
6920	continue; /* no ranges for the tag */
6921	}
6922	else if (info->toggle_count == 0)
6923	{
6924	g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6925	tag->priv->name);
6926	}
6927	else if (info->toggle_count & 1)
6928	{
6929	g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6930	tag->priv->name, info->toggle_count);
6931	}
6932	for (summary = node->summary; summary != NULL;
6933	summary = summary->next)
6934	{
6935	if (summary->info->tag == tag)
6936	{
6937	g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6938	}
6939	}
6940	count = 0;
6941	if (node->level > 0)
6942	{
6943	for (node = node->children.node ; node != NULL ;
6944	node = node->next)
6945	{
6946	for (summary = node->summary; summary != NULL;
6947	summary = summary->next)
6948	{
6949	if (summary->info->tag == tag)
6950	{
6951	count += summary->toggle_count;
6952	}
6953	}
6954	}
6955	}
6956	else
6957	{
6958	const GtkTextLineSegmentClass *last = NULL;
6959
6960	for (line = node->children.line ; line != NULL ;
6961	line = line->next)
6962	{
6963	for (seg = line->segments; seg != NULL;
6964	seg = seg->next)
6965	{
6966	if ((seg->type == &gtk_text_toggle_on_type ||
6967	seg->type == &gtk_text_toggle_off_type) &&
6968	seg->body.toggle.info->tag == tag)
6969	{
6970	if (last == seg->type)
6971	g_error ("Two consecutive toggles on or off weren't merged");
6972	if (!seg->body.toggle.inNodeCounts)
6973	g_error ("Toggle segment not in the node counts");
6974
6975	last = seg->type;
6976
6977	count++;
6978	}
6979	}
6980	}
6981	}
6982	if (count != info->toggle_count)
6983	{
6984	g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6985	info->toggle_count, tag->priv->name, count);
6986	}
6987	}
6988	}
6989
6990	g_slist_free (list: all_tags);
6991
6992	/*
6993	* Call a recursive procedure to do the main body of checks.
6994	*/
6995
6996	node = tree->root_node;
6997	gtk_text_btree_node_check_consistency (tree, node: tree->root_node);
6998
6999	/*
7000	* Make sure that there are at least two lines in the text and
7001	* that the last line has no characters except a newline.
7002	*/
7003
7004	if (node->num_lines < 2)
7005	{
7006	g_error ("_gtk_text_btree_check: less than 2 lines in tree");
7007	}
7008	if (node->num_chars < 2)
7009	{
7010	g_error ("_gtk_text_btree_check: less than 2 chars in tree");
7011	}
7012	while (node->level > 0)
7013	{
7014	node = node->children.node;
7015	while (node->next != NULL)
7016	{
7017	node = node->next;
7018	}
7019	}
7020	line = node->children.line;
7021	while (line->next != NULL)
7022	{
7023	line = line->next;
7024	}
7025	seg = line->segments;
7026	while ((seg->type == &gtk_text_toggle_off_type)
7027	|| (seg->type == &gtk_text_right_mark_type)
7028	|| (seg->type == &gtk_text_left_mark_type))
7029	{
7030	/*
7031	* It’s OK to toggle a tag off in the last line, but
7032	* not to start a new range. It’s also OK to have marks
7033	* in the last line.
7034	*/
7035
7036	seg = seg->next;
7037	}
7038	if (seg->type != &gtk_text_char_type)
7039	{
7040	g_error ("_gtk_text_btree_check: last line has bogus segment type");
7041	}
7042	if (seg->next != NULL)
7043	{
7044	g_error ("_gtk_text_btree_check: last line has too many segments");
7045	}
7046	if (seg->byte_count != 1)
7047	{
7048	g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7049	seg->byte_count);
7050	}
7051	if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7052	{
7053	g_error ("_gtk_text_btree_check: last line had bad value: %s",
7054	seg->body.chars);
7055	}
7056	}
7057	#endif /* G_ENABLE_DEBUG */
7058
7059	void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7060	void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7061	void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7062	void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7063
7064	void
7065	_gtk_text_btree_spew (GtkTextBTree *tree)
7066	{
7067	GtkTextLine * line;
7068	int real_line;
7069
7070	printf (format: "%d lines in tree %p\n",
7071	_gtk_text_btree_line_count (tree), tree);
7072
7073	line = _gtk_text_btree_get_line (tree, line_number: 0, real_line_number: &real_line);
7074
7075	while (line != NULL)
7076	{
7077	_gtk_text_btree_spew_line (tree, line);
7078	line = _gtk_text_line_next (line);
7079	}
7080
7081	printf (format: "=================== Tag information\n");
7082
7083	{
7084	GSList * list;
7085
7086	list = tree->tag_infos;
7087
7088	while (list != NULL)
7089	{
7090	GtkTextTagInfo *info;
7091
7092	info = list->data;
7093
7094	printf (format: " tag '%s': root at %p, toggle count %d\n",
7095	info->tag->priv->name, info->tag_root, info->toggle_count);
7096
7097	list = list->next;
7098	}
7099
7100	if (tree->tag_infos == NULL)
7101	{
7102	printf (format: " (no tags in the tree)\n");
7103	}
7104	}
7105
7106	printf (format: "=================== Tree nodes\n");
7107
7108	{
7109	_gtk_text_btree_spew_node (node: tree->root_node, indent: 0);
7110	}
7111	}
7112
7113	void
7114	_gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7115	{
7116	char * spaces;
7117	GtkTextLineSegment *seg;
7118
7119	spaces = g_strnfill (length: indent, fill_char: ' ');
7120
7121	printf (format: "%sline %p chars %d bytes %d\n",
7122	spaces, line,
7123	_gtk_text_line_char_count (line),
7124	_gtk_text_line_byte_count (line));
7125
7126	seg = line->segments;
7127	while (seg != NULL)
7128	{
7129	if (seg->type == &gtk_text_char_type)
7130	{
7131	char * str = g_strndup (str: seg->body.chars, MIN (seg->byte_count, 10));
7132	char * s;
7133	s = str;
7134	while (*s)
7135	{
7136	if (*s == '\n' || *s == '\r')
7137	*s = '\\';
7138	++s;
7139	}
7140	printf (format: "%s chars '%s'...\n", spaces, str);
7141	g_free (mem: str);
7142	}
7143	else if (seg->type == &gtk_text_child_type)
7144	{
7145	char *str = g_strndup (str: gtk_text_child_anchor_get_replacement (anchor: seg->body.child.obj), n: seg->byte_count);
7146	printf (format: "%s child '%s'...\n", spaces, str);
7147	g_free (mem: str);
7148	}
7149	else if (seg->type == &gtk_text_right_mark_type)
7150	{
7151	printf (format: "%s right mark '%s' visible: %d\n",
7152	spaces,
7153	seg->body.mark.name,
7154	seg->body.mark.visible);
7155	}
7156	else if (seg->type == &gtk_text_left_mark_type)
7157	{
7158	printf (format: "%s left mark '%s' visible: %d\n",
7159	spaces,
7160	seg->body.mark.name,
7161	seg->body.mark.visible);
7162	}
7163	else if (seg->type == &gtk_text_toggle_on_type ||
7164	seg->type == &gtk_text_toggle_off_type)
7165	{
7166	printf (format: "%s tag '%s' %s\n",
7167	spaces, seg->body.toggle.info->tag->priv->name,
7168	seg->type == &gtk_text_toggle_off_type ? "off" : "on");
7169	}
7170
7171	seg = seg->next;
7172	}
7173
7174	g_free (mem: spaces);
7175	}
7176
7177	void
7178	_gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7179	{
7180	char * spaces;
7181	GtkTextBTreeNode *iter;
7182	Summary *s;
7183
7184	spaces = g_strnfill (length: indent, fill_char: ' ');
7185
7186	printf (format: "%snode %p level %d children %d lines %d chars %d\n",
7187	spaces, node, node->level,
7188	node->num_children, node->num_lines, node->num_chars);
7189
7190	s = node->summary;
7191	while (s)
7192	{
7193	printf (format: "%s %d toggles of '%s' below this node\n",
7194	spaces, s->toggle_count, s->info->tag->priv->name);
7195	s = s->next;
7196	}
7197
7198	g_free (mem: spaces);
7199
7200	if (node->level > 0)
7201	{
7202	iter = node->children.node;
7203	while (iter != NULL)
7204	{
7205	_gtk_text_btree_spew_node (node: iter, indent: indent + 2);
7206
7207	iter = iter->next;
7208	}
7209	}
7210	else
7211	{
7212	GtkTextLine *line = node->children.line;
7213	while (line != NULL)
7214	{
7215	_gtk_text_btree_spew_line_short (line, indent: indent + 2);
7216
7217	line = line->next;
7218	}
7219	}
7220	}
7221
7222	void
7223	_gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7224	{
7225	GtkTextLineSegment * seg;
7226
7227	printf (format: "%4d| line: %p parent: %p next: %p\n",
7228	_gtk_text_line_get_number (line), line, line->parent, line->next);
7229
7230	seg = line->segments;
7231
7232	while (seg != NULL)
7233	{
7234	_gtk_text_btree_spew_segment (tree, seg);
7235	seg = seg->next;
7236	}
7237	}
7238
7239	void
7240	_gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7241	{
7242	printf (format: " segment: %p type: %s bytes: %d chars: %d\n",
7243	seg, seg->type->name, seg->byte_count, seg->char_count);
7244
7245	if (seg->type == &gtk_text_char_type)
7246	{
7247	char * str = g_strndup (str: seg->body.chars, n: seg->byte_count);
7248	printf (format: " '%s'\n", str);
7249	g_free (mem: str);
7250	}
7251	else if (seg->type == &gtk_text_child_type)
7252	{
7253	char *str = g_strndup (str: gtk_text_child_anchor_get_replacement (anchor: seg->body.child.obj), n: seg->byte_count);
7254	printf (format: " '%s'\n", str);
7255	g_free (mem: str);
7256	}
7257	else if (seg->type == &gtk_text_right_mark_type)
7258	{
7259	printf (format: " right mark '%s' visible: %d not_deleteable: %d\n",
7260	seg->body.mark.name,
7261	seg->body.mark.visible,
7262	seg->body.mark.not_deleteable);
7263	}
7264	else if (seg->type == &gtk_text_left_mark_type)
7265	{
7266	printf (format: " left mark '%s' visible: %d not_deleteable: %d\n",
7267	seg->body.mark.name,
7268	seg->body.mark.visible,
7269	seg->body.mark.not_deleteable);
7270	}
7271	else if (seg->type == &gtk_text_toggle_on_type ||
7272	seg->type == &gtk_text_toggle_off_type)
7273	{
7274	printf (format: " tag '%s' priority %d\n",
7275	seg->body.toggle.info->tag->priv->name,
7276	seg->body.toggle.info->tag->priv->priority);
7277	}
7278	}
7279