1	/* Text art visualizations within -fanalyzer.
2	Copyright (C) 2023-2025 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it
7	under the terms of the GNU General Public License as published by
8	the Free Software Foundation; either version 3, or (at your option)
9	any later version.
10
11	GCC is distributed in the hope that it will be useful, but
12	WITHOUT ANY WARRANTY; without even the implied warranty of
13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14	General Public License for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	#define INCLUDE_ALGORITHM
21	#define INCLUDE_MAP
22	#define INCLUDE_SET
23	#include "analyzer/common.h"
24
25	#include "fold-const.h"
26	#include "intl.h"
27
28	#include "text-art/ruler.h"
29
30	#include "analyzer/region-model.h"
31	#include "analyzer/access-diagram.h"
32	#include "analyzer/analyzer-selftests.h"
33
34	#if ENABLE_ANALYZER
35
36	/* Consider this code:
37	int32_t arr[10];
38	arr[10] = x;
39	where we've emitted a buffer overflow diagnostic like this:
40	out-of-bounds write from byte 40 till byte 43 but 'arr' ends at byte 40
41
42	We want to emit a diagram that visualizes:
43	- the spatial relationship between the valid region to access, versus
44	the region that was actually accessed: does it overlap, was it touching,
45	close, or far away? Was it before or after in memory? What are the
46	relative sizes involved?
47	- the direction of the access (read vs write)
48
49	The following code supports emitting diagrams similar to the following:
50
51	# +--------------------------------+
52	# |write from ‘x’ (type: ‘int32_t’)|
53	# +--------------------------------+
54	# |
55	# |
56	# v
57	# +---------+-----------+-----------+ +--------------------------------+
58	# | [0] | ... | [9] | | after valid range |
59	# +---------+-----------+-----------+ | |
60	# | ‘arr’ (type: ‘int32_t[10]’) | | |
61	# +---------------------------------+ +--------------------------------+
62	# |~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~| |~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~|
63	# | |
64	# +---------+--------+ +---------+---------+
65	# |capacity: 40 bytes| |overflow of 4 bytes|
66	# +------------------+ +-------------------+
67
68	where the diagram is laid out via table columns where each table column
69	represents either a range of bits/bytes, or is a spacing column (to highlight
70	the boundary between valid vs invalid accesses). The table columns can be
71	seen via -fanalyzer-debug-text-art. For example, here there are 5 table
72	columns ("tc0" through "tc4"):
73
74	# +---------+-----------+-----------+---+--------------------------------+
75	# | tc0 | tc1 | tc2 |tc3| tc4 |
76	# +---------+-----------+-----------+---+--------------------------------+
77	# |bytes 0-3|bytes 4-35 |bytes 36-39| | bytes 40-43 |
78	# +---------+-----------+-----------+ +--------------------------------+
79	#
80	# +--------------------------------+
81	# |write from ‘x’ (type: ‘int32_t’)|
82	# +--------------------------------+
83	# |
84	# |
85	# v
86	# +---------+-----------+-----------+ +--------------------------------+
87	# | [0] | ... | [9] | | after valid range |
88	# +---------+-----------+-----------+ | |
89	# | ‘arr’ (type: ‘int32_t[10]’) | | |
90	# +---------------------------------+ +--------------------------------+
91	# |~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~| |~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~|
92	# | |
93	# +---------+--------+ +---------+---------+
94	# |capacity: 40 bytes| |overflow of 4 bytes|
95	# +------------------+ +-------------------+
96
97	The diagram is built up from the following:
98
99	# +--------------------------------+
100	# | ITEM FOR SVALUE/ACCESSED REGION|
101	# +--------------------------------+
102	# |
103	# | DIRECTION WIDGET
104	# v
105	# +---------------------------------+ +--------------------------------+
106	# | VALID REGION | | INVALID ACCESS |
107	# +---------------------------------+ +--------------------------------+
108	#
109	# | VALID-VS-INVALID RULER |
110
111	i.e. a vbox_widget containing 4 child widgets laid out vertically:
112	- ALIGNED CHILD WIDGET: ITEM FOR SVALUE/ACCESSED REGION
113	- DIRECTION WIDGET
114	- ALIGNED CHILD WIDGET: VALID AND INVALID ACCESSES
115	- VALID-VS-INVALID RULER.
116
117	A more complicated example, given this overflow:
118	char buf[100];
119	strcpy (buf, LOREM_IPSUM);
120
121	01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
122	02| |[0]|[1]|[2]|[3]|[4]|[5]| ... |[440]|[441]|[442]|[443]|[444]|[445]|
123	03| +---+---+---+---+---+---+ +-----+-----+-----+-----+-----+-----+
124	04| |'L'|'o'|'r'|'e'|'m'|' '| | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
125	05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
126	06| | string literal (type: 'char[446]') |
127	07| +----------------------------------------------------------------------+
128	08| | | | | | | | | | | | | | | |
129	09| | | | | | | | | | | | | | | |
130	10| v v v v v v v v v v v v v v v
131	11| +---+---------------------+----++--------------------------------------+
132	12| |[0]| ... |[99]|| after valid range |
133	13| +---+---------------------+----+| |
134	14| | 'buf' (type: 'char[100]') || |
135	15| +------------------------------++--------------------------------------+
136	16| |~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
137	17| | |
138	18| +---------+---------+ +----------+----------+
139	19| |capacity: 100 bytes| |overflow of 346 bytes|
140	20| +-------------------+ +---------------------+
141
142	which is:
143
144	01| ALIGNED CHILD WIDGET (lines 01-07): (string_region_spatial_item)-+-----+
145	02| |[0]|[1]|[2]|[3]|[4]|[5]| ... |[440]|[441]|[442]|[443]|[444]|[445]|
146	03| +---+---+---+---+---+---+ +-----+-----+-----+-----+-----+-----+
147	04| |'L'|'o'|'r'|'e'|'m'|' '| | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
148	05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
149	06| | string literal (type: 'char[446]') |
150	07| +----------------------------------------------------------------------+
151	08| DIRECTION WIDGET (lines 08-10) | | | | | | |
152	09| | | | | | | | | | | | | | | |
153	10| v v v v v v v v v v v v v v v
154	11| ALIGNED CHILD WIDGET (lines 11-15)-------------------------------------+
155	12| VALID REGION ... |[99]|| INVALID ACCESS |
156	13| +---+---------------------+----+| |
157	14| | 'buf' (type: 'char[100]') || |
158	15| +------------------------------++--------------------------------------+
159	16| VALID-VS-INVALID RULER (lines 16-20): ~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
160	17| | |
161	18| +---------+---------+ +----------+----------+
162	19| |capacity: 100 bytes| |overflow of 346 bytes|
163	20| +-------------------+ +---------------------+
164
165	We build the diagram in several phases:
166	- (1) we construct an access_diagram_impl widget. Within the ctor, we have
167	these subphases:
168	- (1.1) find all of the boundaries of interest
169	- (1.2) use the boundaries to build a bit_table_map, associating bit ranges
170	with table columns (e.g. "byte 0 is column 0, bytes 1-98 are column 2" etc)
171	- (1.3) create child widgets that share this table-based geometry
172	- (2) ask the widget for its size request
173	- (2.1) column widths and row heights for the table are computed by
174	access_diagram_impl::calc_req_size
175	- (2.2) child widgets request sizes based on these widths/heights
176	- (3) create a canvas of the appropriate size
177	- (4) paint the widget hierarchy to the canvas. */
178
179
180	using namespace text_art;
181
182	namespace ana {
183
184	static styled_string
185	fmt_styled_string (style_manager &sm,
186	const char *fmt, ...)
187	ATTRIBUTE_GCC_DIAG(2, 3);
188
189	static styled_string
190	fmt_styled_string (style_manager &sm,
191	const char *fmt, ...)
192	{
193	va_list ap;
194	va_start (ap, fmt);
195	styled_string result
196	= styled_string::from_fmt_va (sm, format_decoder: default_tree_printer, fmt, args: &ap);
197	va_end (ap);
198	return result;
199	}
200
201	class access_diagram_impl;
202	class bit_to_table_map;
203
204	static void
205	pp_bit_size_t (pretty_printer *pp, bit_size_t num_bits)
206	{
207	if (num_bits % BITS_PER_UNIT == 0)
208	{
209	byte_size_t num_bytes = num_bits / BITS_PER_UNIT;
210	if (num_bytes == 1)
211	pp_printf (pp, _("%wi byte"), num_bytes.to_uhwi ());
212	else
213	pp_printf (pp, _("%wi bytes"), num_bytes.to_uhwi ());
214	}
215	else
216	{
217	if (num_bits == 1)
218	pp_printf (pp, _("%wi bit"), num_bits.to_uhwi ());
219	else
220	pp_printf (pp, _("%wi bits"), num_bits.to_uhwi ());
221	}
222	}
223
224	static styled_string
225	get_access_size_str (style_manager &sm,
226	const access_operation &op,
227	access_range accessed_range,
228	tree type)
229	{
230	bit_size_expr num_bits (accessed_range.get_size (mgr: op.m_model.get_manager ()));
231	if (type)
232	{
233	styled_string s;
234	pretty_printer pp;
235	pp_format_decoder (pp: &pp) = default_tree_printer;
236	if (num_bits.maybe_print_for_user (pp: &pp, model: op.m_model))
237	{
238	if (op.m_dir == access_direction::read)
239	return fmt_styled_string (sm,
240	_("read of %qT (%s)"),
241	type,
242	pp_formatted_text (&pp));
243	else
244	return fmt_styled_string (sm,
245	_("write of %qT (%s)"),
246	type,
247	pp_formatted_text (&pp));
248	}
249	}
250	if (op.m_dir == access_direction::read)
251	{
252	if (auto p
253	= num_bits.maybe_get_formatted_str (sm, model: op.m_model,
254	_("read of %wi bit"),
255	_("read of %wi bits"),
256	_("read of %wi byte"),
257	_("read of %wi bytes"),
258	_("read of %qs bits"),
259	_("read of %qs bytes")))
260	return std::move (*p.get ());
261	}
262	else
263	{
264	if (auto p
265	= num_bits.maybe_get_formatted_str (sm, model: op.m_model,
266	_("write of %wi bit"),
267	_("write of %wi bits"),
268	_("write of %wi byte"),
269	_("write of %wi bytes"),
270	_("write of %qs bits"),
271	_("write of %qs bytes")))
272	return std::move (*p.get ());
273	}
274
275	if (type)
276	{
277	if (op.m_dir == access_direction::read)
278	return fmt_styled_string (sm, _("read of %qT"), type);
279	else
280	return fmt_styled_string (sm, _("write of %qT"), type);
281	}
282
283	if (op.m_dir == access_direction::read)
284	return styled_string (sm, _("read"));
285	else
286	return styled_string (sm, _("write"));
287	}
288
289	/* Subroutine of clean_up_for_diagram. */
290
291	static tree
292	strip_any_cast (tree expr)
293	{
294	if (TREE_CODE (expr) == NOP_EXPR
295	|| TREE_CODE (expr) == NON_LVALUE_EXPR)
296	expr = TREE_OPERAND (expr, 0);
297	return expr;
298	}
299
300	/* Duplicate EXPR, replacing any SSA names with the underlying variable. */
301
302	tree
303	remove_ssa_names (tree expr)
304	{
305	if (TREE_CODE (expr) == SSA_NAME
306	&& SSA_NAME_VAR (expr))
307	return SSA_NAME_VAR (expr);
308	tree t = copy_node (expr);
309	for (int i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
310	if (TREE_OPERAND (expr, i))
311	TREE_OPERAND (t, i) = remove_ssa_names (TREE_OPERAND (expr, i));
312	return t;
313	}
314
315	/* We want to be able to print tree expressions from the analyzer,
316	which is in the middle end.
317
318	We could use the front-end pretty_printer's formatting routine,
319	but:
320	(a) some have additional state in a pretty_printer subclass, so we'd
321	need to clone global_dc->printer
322	(b) the "aka" type information added by the C and C++ frontends are
323	too verbose when building a diagram, and there isn't a good way to ask
324	for a less verbose version of them.
325
326	Hence we use default_tree_printer.
327	However, we want to avoid printing SSA names, and instead print the
328	underlying var name.
329	Ideally there would be a better tree printer for use by middle end
330	warnings, but as workaround, this function clones a tree, replacing
331	SSA names with the var names. */
332
333	tree
334	clean_up_for_diagram (tree expr)
335	{
336	tree without_ssa_names = remove_ssa_names (expr);
337	return strip_any_cast (expr: without_ssa_names);
338	}
339
340	/* struct bit_size_expr. */
341
342	/* Attempt to generate a user-facing styled string that mentions this
343	bit_size_expr.
344	Use MODEL for extracting representative tree values where necessary.
345	The CONCRETE_* format strings should contain a single %wi.
346	The SYMBOLIC_* format strings should contain a single %qs.
347	Return nullptr if unable to represent the expression. */
348
349	std::unique_ptr<text_art::styled_string>
350	bit_size_expr::maybe_get_formatted_str (text_art::style_manager &sm,
351	const region_model &model,
352	const char *concrete_single_bit_fmt,
353	const char *concrete_plural_bits_fmt,
354	const char *concrete_single_byte_fmt,
355	const char *concrete_plural_bytes_fmt,
356	const char *symbolic_bits_fmt,
357	const char *symbolic_bytes_fmt) const
358	{
359	region_model_manager &mgr = *model.get_manager ();
360	if (const svalue *num_bytes = maybe_get_as_bytes (mgr))
361	{
362	if (tree cst = num_bytes->maybe_get_constant ())
363	{
364	byte_size_t concrete_num_bytes = wi::to_offset (t: cst);
365	if (!wi::fits_uhwi_p (x: concrete_num_bytes))
366	return nullptr;
367	if (concrete_num_bytes == 1)
368	return std::make_unique <text_art::styled_string>
369	(args: fmt_styled_string (sm, fmt: concrete_single_byte_fmt,
370	concrete_num_bytes.to_uhwi ()));
371	else
372	return std::make_unique <text_art::styled_string>
373	(args: fmt_styled_string (sm, fmt: concrete_plural_bytes_fmt,
374	concrete_num_bytes.to_uhwi ()));
375	}
376	else
377	{
378	pretty_printer pp;
379	pp_format_decoder (pp: &pp) = default_tree_printer;
380	if (!num_bytes->maybe_print_for_user (pp: &pp, model))
381	return nullptr;
382	return std::make_unique <text_art::styled_string>
383	(args: fmt_styled_string (sm, fmt: symbolic_bytes_fmt,
384	pp_formatted_text (&pp)));
385	}
386	}
387	else if (tree cst = m_num_bits.maybe_get_constant ())
388	{
389	bit_size_t concrete_num_bits = wi::to_offset (t: cst);
390	if (!wi::fits_uhwi_p (x: concrete_num_bits))
391	return nullptr;
392	if (concrete_num_bits == 1)
393	return std::make_unique <text_art::styled_string>
394	(args: fmt_styled_string (sm, fmt: concrete_single_bit_fmt,
395	concrete_num_bits.to_uhwi ()));
396	else
397	return std::make_unique <text_art::styled_string>
398	(args: fmt_styled_string (sm, fmt: concrete_plural_bits_fmt,
399	concrete_num_bits.to_uhwi ()));
400	}
401	else
402	{
403	pretty_printer pp;
404	pp_format_decoder (pp: &pp) = default_tree_printer;
405	if (!m_num_bits.maybe_print_for_user (pp: &pp, model))
406	return nullptr;
407	return std::make_unique <text_art::styled_string>
408	(args: fmt_styled_string (sm, fmt: symbolic_bits_fmt,
409	pp_formatted_text (&pp)));
410	}
411	}
412
413	bool
414	bit_size_expr::maybe_print_for_user (pretty_printer *pp,
415	const region_model &model) const
416	{
417	if (tree cst = m_num_bits.maybe_get_constant ())
418	{
419	bit_size_t concrete_num_bits = wi::to_offset (t: cst);
420	pp_bit_size_t (pp, num_bits: concrete_num_bits);
421	return true;
422	}
423	else
424	{
425	if (const svalue *num_bytes = maybe_get_as_bytes (mgr&: *model.get_manager ()))
426	{
427	pretty_printer tmp_pp;
428	pp_format_decoder (pp: &tmp_pp) = default_tree_printer;
429	if (!num_bytes->maybe_print_for_user (pp: &tmp_pp, model))
430	return false;
431	pp_printf (pp, _("%qs bytes"), pp_formatted_text (&tmp_pp));
432	return true;
433	}
434	else
435	{
436	pretty_printer tmp_pp;
437	pp_format_decoder (pp: &tmp_pp) = default_tree_printer;
438	if (!m_num_bits.maybe_print_for_user (pp: &tmp_pp, model))
439	return false;
440	pp_printf (pp, _("%qs bits"), pp_formatted_text (&tmp_pp));
441	return true;
442	}
443	}
444	}
445
446	/* Attempt to get a symbolic value for this symbolic bit size,
447	expressed in bytes.
448	Return null if it's not known to divide exactly. */
449
450	const svalue *
451	bit_size_expr::maybe_get_as_bytes (region_model_manager &mgr) const
452	{
453	if (tree cst = m_num_bits.maybe_get_constant ())
454	{
455	bit_offset_t concrete_bits = wi::to_offset (t: cst);
456	if (concrete_bits % BITS_PER_UNIT != 0)
457	/* Not an exact multiple, so fail. */
458	return nullptr;
459	}
460	const svalue *bits_per_byte
461	= mgr.get_or_create_int_cst (NULL_TREE, BITS_PER_UNIT);
462	return mgr.maybe_fold_binop (NULL_TREE, op: EXACT_DIV_EXPR,
463	arg0: &m_num_bits, arg1: bits_per_byte);
464	}
465
466	/* struct access_range. */
467
468	access_range::access_range (const region *base_region, const bit_range &bits)
469	: m_start (region_offset::make_concrete (base_region,
470	offset: bits.get_start_bit_offset ())),
471	m_next (region_offset::make_concrete (base_region,
472	offset: bits.get_next_bit_offset ()))
473	{
474	}
475
476	access_range::access_range (const region *base_region, const byte_range &bytes)
477	: m_start (region_offset::make_concrete (base_region,
478	offset: bytes.get_start_bit_offset ())),
479	m_next (region_offset::make_concrete (base_region,
480	offset: bytes.get_next_bit_offset ()))
481	{
482	}
483
484	access_range::access_range (const region &reg, region_model_manager *mgr)
485	: m_start (strip_types (offset: reg.get_offset (mgr), mgr&: *mgr)),
486	m_next (strip_types (offset: reg.get_next_offset (mgr), mgr&: *mgr))
487	{
488	}
489
490	bit_size_expr
491	access_range::get_size (region_model_manager *mgr) const
492	{
493	const svalue &start_bit_offset = m_start.calc_symbolic_bit_offset (mgr);
494	const svalue &next_bit_offset = m_next.calc_symbolic_bit_offset (mgr);
495	return bit_size_expr
496	(*mgr->get_or_create_binop (NULL_TREE, op: MINUS_EXPR,
497	arg0: &next_bit_offset, arg1: &start_bit_offset));
498	}
499
500	bool
501	access_range::contains_p (const access_range &other) const
502	{
503	return (m_start <= other.m_start
504	&& other.m_next <= m_next);
505	}
506
507	bool
508	access_range::empty_p () const
509	{
510	bit_range concrete_bits (0, 0);
511	if (!as_concrete_bit_range (out: &concrete_bits))
512	return false;
513	return concrete_bits.empty_p ();
514	}
515
516	void
517	access_range::dump_to_pp (pretty_printer *pp, bool simple) const
518	{
519	if (m_start.concrete_p () && m_next.concrete_p ())
520	{
521	bit_range bits (m_start.get_bit_offset (),
522	m_next.get_bit_offset () - m_start.get_bit_offset ());
523	bits.dump_to_pp (pp);
524	return;
525	}
526	pp_character (pp, '[');
527	m_start.dump_to_pp (pp, simple);
528	pp_string (pp, " to ");
529	m_next.dump_to_pp (pp, simple);
530	pp_character (pp, ')');
531	}
532
533	DEBUG_FUNCTION void
534	access_range::dump (bool simple) const
535	{
536	tree_dump_pretty_printer pp (stderr);
537	dump_to_pp (pp: &pp, simple);
538	pp_newline (&pp);
539	}
540
541	void
542	access_range::log (const char *title, logger &logger) const
543	{
544	logger.start_log_line ();
545	logger.log_partial (fmt: "%s: ", title);
546	dump_to_pp (pp: logger.get_printer (), simple: true);
547	logger.end_log_line ();
548	}
549
550	/* struct access_operation. */
551
552	access_range
553	access_operation::get_valid_bits () const
554	{
555	const svalue *capacity_in_bytes_sval = m_model.get_capacity (reg: m_base_region);
556	return access_range
557	(region_offset::make_concrete (base_region: m_base_region, offset: 0),
558	region_offset::make_byte_offset (base_region: m_base_region, num_bytes_sval: capacity_in_bytes_sval),
559	*get_manager ());
560	}
561
562	access_range
563	access_operation::get_actual_bits () const
564	{
565	return access_range (m_reg, get_manager ());
566	}
567
568	/* If there are any bits accessed invalidly before the valid range,
569	return true and write their range to *OUT.
570	Return false if there aren't, or if there's a problem
571	(e.g. symbolic ranges. */
572
573	bool
574	access_operation::maybe_get_invalid_before_bits (access_range *out) const
575	{
576	access_range valid_bits (get_valid_bits ());
577	access_range actual_bits (get_actual_bits ());
578
579	if (actual_bits.m_start >= valid_bits.m_start)
580	{
581	/* No part of accessed range is before the valid range. */
582	return false;
583	}
584	else if (actual_bits.m_next > valid_bits.m_start)
585	{
586	/* Get part of accessed range that's before the valid range. */
587	*out = access_range (actual_bits.m_start, valid_bits.m_start,
588	*get_manager ());
589	return true;
590	}
591	else
592	{
593	/* Accessed range is fully before valid range. */
594	*out = actual_bits;
595	return true;
596	}
597	}
598
599	/* If there are any bits accessed invalidly after the valid range,
600	return true and write their range to *OUT.
601	Return false if there aren't, or if there's a problem. */
602
603	bool
604	access_operation::maybe_get_invalid_after_bits (access_range *out) const
605	{
606	access_range valid_bits (get_valid_bits ());
607	access_range actual_bits (get_actual_bits ());
608
609	if (actual_bits.m_next <= valid_bits.m_next)
610	{
611	/* No part of accessed range is after the valid range. */
612	return false;
613	}
614	else if (actual_bits.m_start < valid_bits.m_next)
615	{
616	/* Get part of accessed range that's after the valid range. */
617	*out = access_range (valid_bits.m_next, actual_bits.m_next,
618	*get_manager ());
619	return true;
620	}
621	else
622	{
623	/* Accessed range is fully after valid range. */
624	*out = actual_bits;
625	return true;
626	}
627	}
628
629	/* A class for capturing all of the region offsets of interest (both concrete
630	and symbolic), to help align everything in the diagram.
631	Boundaries can be soft or hard; hard boundaries are emphasized visually
632	(e.g. the boundary between valid vs invalid accesses).
633
634	Offsets in the boundaries are all expressed relative to the base
635	region of the access_operation. */
636
637	class boundaries
638	{
639	public:
640	enum class kind { HARD, SOFT};
641
642	boundaries (const region &base_reg, logger *logger)
643	: m_base_reg (base_reg), m_logger (logger)
644	{
645	}
646
647	void add (region_offset offset, enum kind k)
648	{
649	m_all_offsets.insert (x: offset);
650	if (k == kind::HARD)
651	m_hard_offsets.insert (x: offset);
652	}
653
654	void add (const access_range &range, enum kind kind)
655	{
656	add (offset: range.m_start, k: kind);
657	add (offset: range.m_next, k: kind);
658	if (m_logger)
659	{
660	m_logger->start_log_line ();
661	m_logger->log_partial (fmt: "added access_range: ");
662	range.dump_to_pp (pp: m_logger->get_printer (), simple: true);
663	m_logger->log_partial (fmt: " (%s)",
664	(kind == boundaries::kind::HARD)
665	? "HARD" : "soft");
666	m_logger->end_log_line ();
667	}
668	}
669
670	void add (const region &reg, region_model_manager *mgr, enum kind kind)
671	{
672	add (range: access_range (reg.get_offset (mgr),
673	reg.get_next_offset (mgr),
674	*mgr),
675	kind);
676	}
677
678	void add (const byte_range bytes, enum kind kind)
679	{
680	add (range: access_range (&m_base_reg, bytes), kind);
681	}
682
683	void add_all_bytes_in_range (const byte_range &bytes)
684	{
685	for (byte_offset_t byte_idx = bytes.get_start_byte_offset ();
686	byte_idx <= bytes.get_next_byte_offset ();
687	byte_idx = byte_idx + 1)
688	add (offset: region_offset::make_concrete (base_region: &m_base_reg, offset: byte_idx * 8),
689	k: kind::SOFT);
690	}
691
692	void add_all_bytes_in_range (const access_range &range)
693	{
694	byte_range bytes (0, 0);
695	bool valid = range.as_concrete_byte_range (out: &bytes);
696	gcc_assert (valid);
697	add_all_bytes_in_range (bytes);
698	}
699
700	void log (logger &logger) const
701	{
702	logger.log (fmt: "boundaries:");
703	logger.inc_indent ();
704	for (auto offset : m_all_offsets)
705	{
706	enum kind k = get_kind (offset);
707	logger.start_log_line ();
708	logger.log_partial (fmt: "%s: ", (k == kind::HARD) ? "HARD" : "soft");
709	offset.dump_to_pp (pp: logger.get_printer (), true);
710	logger.end_log_line ();
711	}
712	logger.dec_indent ();
713	}
714
715	enum kind get_kind (region_offset offset) const
716	{
717	gcc_assert (m_all_offsets.find (offset) != m_all_offsets.end ());
718	if (m_hard_offsets.find (x: offset) != m_hard_offsets.end ())
719	return kind::HARD;
720	else
721	return kind::SOFT;
722	}
723
724	std::set<region_offset>::const_iterator begin () const
725	{
726	return m_all_offsets.begin ();
727	}
728	std::set<region_offset>::const_iterator end () const
729	{
730	return m_all_offsets.end ();
731	}
732	std::set<region_offset>::size_type size () const
733	{
734	return m_all_offsets.size ();
735	}
736
737	std::vector<region_offset>
738	get_hard_boundaries_in_range (byte_offset_t min_offset,
739	byte_offset_t max_offset) const
740	{
741	std::vector<region_offset> result;
742	for (auto &offset : m_hard_offsets)
743	{
744	if (!offset.concrete_p ())
745	continue;
746	byte_offset_t byte;
747	if (!offset.get_concrete_byte_offset (out: &byte))
748	continue;
749	if (byte < min_offset)
750	continue;
751	if (byte > max_offset)
752	continue;
753	result.push_back (x: offset);
754	}
755	return result;
756	}
757
758	private:
759	const region &m_base_reg;
760	logger *m_logger;
761	std::set<region_offset> m_all_offsets;
762	std::set<region_offset> m_hard_offsets;
763	};
764
765	/* A widget that wraps a table but offloads column-width calculation
766	to a shared object, so that we can vertically line up multiple tables
767	and have them all align their columns.
768
769	For example, in:
770
771	01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
772	02| |[0]|[1]|[2]|[3]|[4]|[5]| ... |[440]|[441]|[442]|[443]|[444]|[445]|
773	03| +---+---+---+---+---+---+ +-----+-----+-----+-----+-----+-----+
774	04| |'L'|'o'|'r'|'e'|'m'|' '| | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
775	05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
776	06| | string literal (type: 'char[446]') |
777	07| +----------------------------------------------------------------------+
778	08| | | | | | | | | | | | | | | |
779	09| | | | | | | | | | | | | | | |
780	10| v v v v v v v v v v v v v v v
781	11|+---+---------------------+----++--------------------------------------+
782	12||[0]| ... |[99]|| after valid range |
783	13|+---+---------------------+----+| |
784	14|| 'buf' (type: 'char[100]') || |
785	15|+------------------------------++--------------------------------------+
786	16||~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
787	17| | |
788	18| +---------+---------+ +----------+----------+
789	19| |capacity: 100 bytes| |overflow of 346 bytes|
790	20| +-------------------+ +---------------------+
791
792	rows 01-07 and rows 11-15 are x_aligned_table_widget instances. */
793
794	class x_aligned_table_widget : public leaf_widget
795	{
796	public:
797	x_aligned_table_widget (table t,
798	const theme &theme,
799	table_dimension_sizes &col_widths)
800	: m_table (std::move (t)),
801	m_theme (theme),
802	m_col_widths (col_widths),
803	m_row_heights (t.get_size ().h),
804	m_cell_sizes (m_col_widths, m_row_heights),
805	m_tg (m_table, m_cell_sizes)
806	{
807	}
808
809	const char *get_desc () const override
810	{
811	return "x_aligned_table_widget";
812	}
813
814	canvas::size_t calc_req_size () final override
815	{
816	/* We don't compute the size requirements;
817	the parent should have done this. */
818	return m_tg.get_canvas_size ();
819	}
820
821	void paint_to_canvas (canvas &canvas) final override
822	{
823	m_table.paint_to_canvas (canvas,
824	offset: get_top_left (),
825	tg: m_tg,
826	theme: m_theme);
827	}
828
829	const table &get_table () const { return m_table; }
830	table_cell_sizes &get_cell_sizes () { return m_cell_sizes; }
831	void recalc_coords ()
832	{
833	m_tg.recalc_coords ();
834	}
835
836	private:
837	table m_table;
838	const theme &m_theme;
839	table_dimension_sizes &m_col_widths; // Reference to shared column widths
840	table_dimension_sizes m_row_heights; // Unique row heights
841	table_cell_sizes m_cell_sizes;
842	table_geometry m_tg;
843	};
844
845	/* A widget for printing arrows between the accessed region
846	and the svalue, showing the direction of the access.
847
848	For example, in:
849
850	01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
851	02| |[0]|[1]|[2]|[3]|[4]|[5]| ... |[440]|[441]|[442]|[443]|[444]|[445]|
852	03| +---+---+---+---+---+---+ +-----+-----+-----+-----+-----+-----+
853	04| |'L'|'o'|'r'|'e'|'m'|' '| | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
854	05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
855	06| | string literal (type: 'char[446]') |
856	07| +----------------------------------------------------------------------+
857	08| | | | | | | | | | | | | | | |
858	09| | | | | | | | | | | | | | | |
859	10| v v v v v v v v v v v v v v v
860	11|+---+---------------------+----++--------------------------------------+
861	12||[0]| ... |[99]|| after valid range |
862	13|+---+---------------------+----+| |
863	14|| 'buf' (type: 'char[100]') || |
864	15|+------------------------------++--------------------------------------+
865	16||~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
866	17| | |
867	18| +---------+---------+ +----------+----------+
868	19| |capacity: 100 bytes| |overflow of 346 bytes|
869	20| +-------------------+ +---------------------+
870
871	rows 8-10 are the direction widget. */
872
873	class direction_widget : public leaf_widget
874	{
875	public:
876	direction_widget (const access_diagram_impl &dia_impl,
877	const bit_to_table_map &btm)
878	: leaf_widget (),
879	m_dia_impl (dia_impl),
880	m_btm (btm)
881	{
882	}
883	const char *get_desc () const override
884	{
885	return "direction_widget";
886	}
887	canvas::size_t calc_req_size () final override
888	{
889	/* Get our width from our siblings. */
890	return canvas::size_t (0, 3);
891	}
892	void paint_to_canvas (canvas &canvas) final override;
893
894	private:
895	const access_diagram_impl &m_dia_impl;
896	const bit_to_table_map &m_btm;
897	};
898
899	/* A widget for adding an x_ruler to a diagram based on table columns,
900	offloading column-width calculation to shared objects, so that the ruler
901	lines up with other tables in the diagram.
902
903	For example, in:
904
905	01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
906	02| |[0]|[1]|[2]|[3]|[4]|[5]| ... |[440]|[441]|[442]|[443]|[444]|[445]|
907	03| +---+---+---+---+---+---+ +-----+-----+-----+-----+-----+-----+
908	04| |'L'|'o'|'r'|'e'|'m'|' '| | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
909	05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
910	06| | string literal (type: 'char[446]') |
911	07| +----------------------------------------------------------------------+
912	08| | | | | | | | | | | | | | | |
913	09| | | | | | | | | | | | | | | |
914	10| v v v v v v v v v v v v v v v
915	11|+---+---------------------+----++--------------------------------------+
916	12||[0]| ... |[99]|| after valid range |
917	13|+---+---------------------+----+| |
918	14|| 'buf' (type: 'char[100]') || |
919	15|+------------------------------++--------------------------------------+
920	16||~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
921	17| | |
922	18| +---------+---------+ +----------+----------+
923	19| |capacity: 100 bytes| |overflow of 346 bytes|
924	20| +-------------------+ +---------------------+
925
926	rows 16-20 are the x_aligned_x_ruler_widget. */
927
928	class x_aligned_x_ruler_widget : public leaf_widget
929	{
930	public:
931	x_aligned_x_ruler_widget (const access_diagram_impl &dia_impl,
932	const theme &theme)
933	: m_dia_impl (dia_impl),
934	m_theme (theme)
935	{
936	}
937
938	const char *get_desc () const override
939	{
940	return "x_aligned_ruler_widget";
941	}
942
943	void add_range (const table::range_t &x_range,
944	styled_string text,
945	style::id_t style_id)
946	{
947	m_labels.push_back (x: label (x_range, std::move (text), style_id));
948	}
949
950	canvas::size_t calc_req_size () final override
951	{
952	x_ruler r (make_x_ruler ());
953	return r.get_size ();
954	}
955
956	void paint_to_canvas (canvas &canvas) final override
957	{
958	x_ruler r (make_x_ruler ());
959	r.paint_to_canvas (canvas,
960	offset: get_top_left (),
961	theme: m_theme);
962	}
963
964	private:
965	struct label
966	{
967	label (const table::range_t &table_x_range,
968	styled_string text,
969	style::id_t style_id)
970	: m_table_x_range (table_x_range),
971	m_text (std::move (text)),
972	m_style_id (style_id)
973	{
974	}
975	table::range_t m_table_x_range;
976	styled_string m_text;
977	style::id_t m_style_id;
978	};
979
980	x_ruler make_x_ruler () const;
981
982	const access_diagram_impl &m_dia_impl;
983	const theme &m_theme;
984	std::vector<label> m_labels;
985	};
986
987	/* A two-way mapping between access_ranges and table columns, for use by
988	spatial_item subclasses for creating tables.
989	For example when visualizing a bogus access of 'int arr[10];'
990	at 'arr[10]', we might have:
991	- table column 0 is "bytes 0-3" (for arr[0])
992	- table column 1 is "bytes 4-35" (for arr[1] through arr[8])
993	- table column 2 is "bytes 36-39 (for arr[9])
994	- table column 3 is blank to emphasize a hard boundary between
995	valid/invalid accesses.
996	- table column 4 is "bytes 40-44" (for arr[10])
997
998	We store this as a pair of maps from region_offset to table x; in
999	the abvove example:
1000
1001	region offset table_x prev_table_x
1002	bit 0 (aka byte 0) 0 (none)
1003	bit 32 (aka byte 4) 1 0
1004	bit 288 (aka byte 36) 2 1
1005	bit 320 (aka byte 40) 4 2
1006	bit 352 (aka byte 44) (none) (none)
1007
1008	so that e.g given the half-open byte range [0, 40)
1009	we can determine the closed range of table x [0, 2]. */
1010
1011	class bit_to_table_map
1012	{
1013	public:
1014	/* Populate m_table_x_for_bit and m_bit_for_table_x. */
1015	void populate (const boundaries &boundaries,
1016	region_model_manager &mgr,
1017	logger *logger)
1018	{
1019	LOG_SCOPE (logger);
1020
1021	int table_x = 0;
1022	std::vector <region_offset> vec_boundaries (boundaries.begin (),
1023	boundaries.end ());
1024
1025	/* Sort into an order that makes sense. */
1026	std::sort (first: vec_boundaries.begin (),
1027	last: vec_boundaries.end ());
1028
1029	if (logger)
1030	{
1031	logger->log (fmt: "vec_boundaries");
1032	logger->inc_indent ();
1033	for (unsigned idx = 0; idx < vec_boundaries.size (); idx++)
1034	{
1035	logger->start_log_line ();
1036	logger->log_partial (fmt: "idx: %i: ", idx);
1037	vec_boundaries[idx].dump_to_pp (pp: logger->get_printer (), true);
1038	logger->end_log_line ();
1039	}
1040	logger->dec_indent ();
1041	}
1042
1043	for (size_t idx = 0; idx < vec_boundaries.size (); idx++)
1044	{
1045	const region_offset &offset = vec_boundaries[idx];
1046	if (idx > 0 && (idx + 1) < vec_boundaries.size ())
1047	{
1048	if (boundaries.get_kind (offset) == boundaries::kind::HARD)
1049	table_x += 1;
1050	}
1051	m_table_x_for_offset[offset] = table_x;
1052	if ((idx + 1) < vec_boundaries.size ())
1053	{
1054	const region_offset &next_offset = vec_boundaries[idx + 1];
1055	m_table_x_for_prev_offset[next_offset] = table_x;
1056	m_range_for_table_x[table_x]
1057	= access_range (offset, next_offset, mgr);
1058	}
1059	table_x += 1;
1060	}
1061	m_num_columns = table_x - 1;
1062
1063	if (logger)
1064	log (logger&: *logger);
1065	}
1066
1067	unsigned get_num_columns () const
1068	{
1069	return m_num_columns;
1070	}
1071
1072	table::range_t get_table_x_for_range (const access_range &range) const
1073	{
1074	return table::range_t (get_table_x_for_offset (offset: range.m_start),
1075	get_table_x_for_prev_offset (offset: range.m_next) + 1);
1076	}
1077
1078	table::rect_t get_table_rect (const access_range &range,
1079	const int table_y, const int table_h) const
1080	{
1081	const table::range_t x_range (get_table_x_for_range (range));
1082	return table::rect_t (table::coord_t (x_range.start, table_y),
1083	table::size_t (x_range.get_size (), table_h));
1084	}
1085
1086	table::rect_t get_table_rect (const region *base_reg,
1087	const bit_range &bits,
1088	const int table_y, const int table_h) const
1089	{
1090	const access_range range (base_reg, bits);
1091	return get_table_rect (range, table_y, table_h);
1092	}
1093
1094	table::rect_t get_table_rect (const region *base_reg,
1095	const byte_range &bytes,
1096	const int table_y, const int table_h) const
1097	{
1098	return get_table_rect (base_reg, bits: bytes.as_bit_range (), table_y, table_h);
1099	}
1100
1101	bool maybe_get_access_range_for_table_x (int table_x,
1102	access_range *out) const
1103	{
1104	auto slot = m_range_for_table_x.find (x: table_x);
1105	if (slot == m_range_for_table_x.end ())
1106	return false;
1107	*out = slot->second;
1108	return true;
1109	}
1110
1111	void log (logger &logger) const
1112	{
1113	logger.log (fmt: "table columns");
1114	logger.inc_indent ();
1115	for (unsigned table_x = 0; table_x < get_num_columns (); table_x++)
1116	{
1117	logger.start_log_line ();
1118	logger.log_partial (fmt: "table_x: %i", table_x);
1119	access_range range_for_column (NULL, bit_range (0, 0));
1120	if (maybe_get_access_range_for_table_x (table_x, out: &range_for_column))
1121	{
1122	logger.log_partial (fmt: ": range: ");
1123	range_for_column.dump_to_pp (pp: logger.get_printer (), simple: true);
1124	}
1125	logger.end_log_line ();
1126	}
1127	logger.dec_indent ();
1128	}
1129
1130	int get_table_x_for_offset (region_offset offset) const
1131	{
1132	auto slot = m_table_x_for_offset.find (x: offset);
1133
1134	/* If this fails, then we probably failed to fully populate m_boundaries
1135	in find_boundaries. */
1136	gcc_assert (slot != m_table_x_for_offset.end ());
1137
1138	return slot->second;
1139	}
1140
1141	private:
1142	int get_table_x_for_prev_offset (region_offset offset) const
1143	{
1144	auto slot = m_table_x_for_prev_offset.find (x: offset);
1145
1146	/* If this fails, then we probably failed to fully populate m_boundaries
1147	in find_boundaries. */
1148	gcc_assert (slot != m_table_x_for_prev_offset.end ());
1149
1150	return slot->second;
1151	}
1152
1153	std::map<region_offset, int> m_table_x_for_offset;
1154	std::map<region_offset, int> m_table_x_for_prev_offset;
1155	std::map<int, access_range> m_range_for_table_x;
1156	unsigned m_num_columns;
1157	};
1158
1159	/* Base class for something in the diagram that participates
1160	in two steps of diagram creation:
1161	(a) populating a boundaries instance with the boundaries of interest
1162	(b) creating a table instance for itself.
1163
1164	Offsets in the boundaries are all expressed relative to the base
1165	region of the access_operation. */
1166
1167	class spatial_item
1168	{
1169	public:
1170	virtual ~spatial_item () {}
1171	virtual void add_boundaries (boundaries &out, logger *) const = 0;
1172
1173	virtual table make_table (const bit_to_table_map &btm,
1174	style_manager &sm) const = 0;
1175	};
1176
1177	/* A spatial_item that involves showing an svalue at a particular offset. */
1178
1179	class svalue_spatial_item : public spatial_item
1180	{
1181	public:
1182	enum class kind
1183	{
1184	WRITTEN,
1185	EXISTING
1186	};
1187	protected:
1188	svalue_spatial_item (const svalue &sval,
1189	access_range bits,
1190	enum kind kind)
1191	: m_sval (sval), m_bits (bits), m_kind (kind)
1192	{
1193	}
1194
1195	const svalue &m_sval;
1196	access_range m_bits;
1197	enum kind m_kind;
1198	};
1199
1200	static std::unique_ptr<spatial_item>
1201	make_existing_svalue_spatial_item (const svalue *sval,
1202	const access_range &bits,
1203	const theme &theme);
1204
1205	class compound_svalue_spatial_item : public svalue_spatial_item
1206	{
1207	public:
1208	compound_svalue_spatial_item (const compound_svalue &sval,
1209	const access_range &bits,
1210	enum kind kind,
1211	const theme &theme)
1212	: svalue_spatial_item (sval, bits, kind),
1213	m_compound_sval (sval)
1214	{
1215	const binding_map &map = m_compound_sval.get_map ();
1216	auto_vec <const binding_key *> binding_keys;
1217	for (auto iter : map)
1218	{
1219	const binding_key *key = iter.first;
1220	const svalue *bound_sval = iter.second;
1221	if (const concrete_binding *concrete_key
1222	= key->dyn_cast_concrete_binding ())
1223	{
1224	access_range range (nullptr,
1225	concrete_key->get_bit_range ());
1226	if (std::unique_ptr<spatial_item> child
1227	= make_existing_svalue_spatial_item (sval: bound_sval,
1228	bits: range,
1229	theme))
1230	m_children.push_back (x: std::move (child));
1231	}
1232	}
1233	}
1234
1235	void add_boundaries (boundaries &out, logger *logger) const final override
1236	{
1237	LOG_SCOPE (logger);
1238	for (auto &iter : m_children)
1239	iter->add_boundaries (out, logger);
1240	}
1241
1242	table make_table (const bit_to_table_map &btm,
1243	style_manager &sm) const final override
1244	{
1245	std::vector<table> child_tables;
1246	int max_rows = 0;
1247	for (auto &iter : m_children)
1248	{
1249	table child_table (iter->make_table (btm, sm));
1250	max_rows = MAX (max_rows, child_table.get_size ().h);
1251	child_tables.push_back (x: std::move (child_table));
1252	}
1253	table t (table::size_t (btm.get_num_columns (), max_rows));
1254	for (auto &&child_table : child_tables)
1255	t.add_other_table (other: std::move (child_table),
1256	offset: table::coord_t (0, 0));
1257	return t;
1258	}
1259
1260	private:
1261	const compound_svalue &m_compound_sval;
1262	std::vector<std::unique_ptr<spatial_item>> m_children;
1263	};
1264
1265	/* Loop through the TABLE_X_RANGE columns of T, adding
1266	cells containing "..." in any unoccupied ranges of table cell. */
1267
1268	static void
1269	add_ellipsis_to_gaps (table &t,
1270	style_manager &sm,
1271	const table::range_t &table_x_range,
1272	const table::range_t &table_y_range)
1273	{
1274	int table_x = table_x_range.get_min ();
1275	while (table_x < table_x_range.get_next ())
1276	{
1277	/* Find a run of unoccupied table cells. */
1278	const int start_table_x = table_x;
1279	while (table_x < table_x_range.get_next ()
1280	&& !t.get_placement_at (coord: table::coord_t (table_x,
1281	table_y_range.get_min ())))
1282	table_x++;
1283	const table::range_t unoccupied_x_range (start_table_x, table_x);
1284	if (unoccupied_x_range.get_size () > 0)
1285	t.set_cell_span (span: table::rect_t (unoccupied_x_range, table_y_range),
1286	content: styled_string (sm, "..."));
1287	/* Skip occupied table cells. */
1288	while (table_x < table_x_range.get_next ()
1289	&& t.get_placement_at (coord: table::coord_t (table_x,
1290	table_y_range.get_min ())))
1291	table_x++;
1292	}
1293	}
1294
1295	/* Subclass of spatial_item for visualizing the region of memory
1296	that's valid to access relative to the base region of region accessed in
1297	the operation. */
1298
1299	class valid_region_spatial_item : public spatial_item
1300	{
1301	public:
1302	valid_region_spatial_item (const access_operation &op,
1303	diagnostic_event_id_t region_creation_event_id,
1304	const theme &theme)
1305	: m_op (op),
1306	m_region_creation_event_id (region_creation_event_id),
1307	m_boundaries (nullptr),
1308	m_existing_sval (op.m_model.get_store_value (reg: op.m_base_region, ctxt: nullptr)),
1309	m_existing_sval_spatial_item
1310	(make_existing_svalue_spatial_item (sval: m_existing_sval,
1311	bits: op.get_valid_bits (),
1312	theme))
1313	{
1314	}
1315
1316	void add_boundaries (boundaries &out, logger *logger) const final override
1317	{
1318	LOG_SCOPE (logger);
1319	m_boundaries = &out;
1320	access_range valid_bits = m_op.get_valid_bits ();
1321	if (logger)
1322	{
1323	logger->start_log_line ();
1324	logger->log_partial (fmt: "valid bits: ");
1325	valid_bits.dump_to_pp (pp: logger->get_printer (), simple: true);
1326	logger->end_log_line ();
1327	}
1328	out.add (range: valid_bits, kind: boundaries::kind::HARD);
1329
1330	if (m_existing_sval_spatial_item)
1331	{
1332	if (logger)
1333	{
1334	logger->start_log_line ();
1335	logger->log_partial (fmt: "existing svalue: ");
1336	m_existing_sval->dump_to_pp (pp: logger->get_printer (), simple: true);
1337	logger->end_log_line ();
1338	}
1339	m_existing_sval_spatial_item->add_boundaries (out, logger);
1340	}
1341
1342	/* Support for showing first and final element in array types. */
1343	if (tree base_type = m_op.m_base_region->get_type ())
1344	if (TREE_CODE (base_type) == ARRAY_TYPE)
1345	{
1346	if (logger)
1347	logger->log (fmt: "showing first and final element in array type");
1348	region_model_manager *mgr = m_op.m_model.get_manager ();
1349	tree domain = TYPE_DOMAIN (base_type);
1350	if (domain && TYPE_MIN_VALUE (domain) && TYPE_MAX_VALUE (domain))
1351	{
1352	const svalue *min_idx_sval
1353	= mgr->get_or_create_constant_svalue (TYPE_MIN_VALUE (domain));
1354	const svalue *max_idx_sval
1355	= mgr->get_or_create_constant_svalue (TYPE_MAX_VALUE (domain));
1356	const region *min_element =
1357	mgr->get_element_region (parent: m_op.m_base_region,
1358	TREE_TYPE (base_type),
1359	index: min_idx_sval);
1360	out.add (reg: *min_element, mgr, kind: boundaries::kind::SOFT);
1361	const region *max_element =
1362	mgr->get_element_region (parent: m_op.m_base_region,
1363	TREE_TYPE (base_type),
1364	index: max_idx_sval);
1365	out.add (reg: *max_element, mgr, kind: boundaries::kind::SOFT);
1366	}
1367	}
1368	}
1369
1370	/* Subroutine of make_table when base region has ARRAY_TYPE. */
1371	void add_array_elements_to_table (table &t,
1372	const bit_to_table_map &btm,
1373	style_manager &sm) const
1374	{
1375	tree base_type = m_op.m_base_region->get_type ();
1376	gcc_assert (TREE_CODE (base_type) == ARRAY_TYPE);
1377	gcc_assert (m_boundaries != nullptr);
1378
1379	tree domain = TYPE_DOMAIN (base_type);
1380	if (!(domain && TYPE_MIN_VALUE (domain) && TYPE_MAX_VALUE (domain)))
1381	return;
1382
1383	const int table_y = 0;
1384	const int table_h = 1;
1385	const table::range_t table_y_range (table_y, table_y + table_h);
1386
1387	t.add_row ();
1388
1389	const table::range_t min_x_range
1390	= maybe_add_array_index_to_table (t, btm, sm, table_y_range,
1391	TYPE_MIN_VALUE (domain));
1392	const table::range_t max_x_range
1393	= maybe_add_array_index_to_table (t, btm, sm, table_y_range,
1394	TYPE_MAX_VALUE (domain));
1395
1396	if (TREE_TYPE (base_type) == char_type_node)
1397	{
1398	/* For a char array,: if there are any hard boundaries in
1399	m_boundaries that are *within* the valid region,
1400	then show those index values. */
1401	std::vector<region_offset> hard_boundaries
1402	= m_boundaries->get_hard_boundaries_in_range
1403	(min_offset: tree_to_shwi (TYPE_MIN_VALUE (domain)),
1404	max_offset: tree_to_shwi (TYPE_MAX_VALUE (domain)));
1405	for (auto &offset : hard_boundaries)
1406	{
1407	const int table_x = btm.get_table_x_for_offset (offset);
1408	if (!offset.concrete_p ())
1409	continue;
1410	byte_offset_t byte;
1411	if (!offset.get_concrete_byte_offset (out: &byte))
1412	continue;
1413	table::range_t table_x_range (table_x, table_x + 1);
1414	t.maybe_set_cell_span (span: table::rect_t (table_x_range,
1415	table_y_range),
1416	content: fmt_styled_string (sm, fmt: "[%wi]",
1417	byte.to_shwi ()));
1418	}
1419	}
1420
1421	add_ellipsis_to_gaps (t, sm,
1422	table_x_range: table::range_t (min_x_range.get_next (),
1423	max_x_range.get_min ()),
1424	table_y_range);
1425	}
1426
1427	table::range_t
1428	maybe_add_array_index_to_table (table &t,
1429	const bit_to_table_map &btm,
1430	style_manager &sm,
1431	const table::range_t table_y_range,
1432	tree idx_cst) const
1433	{
1434	region_model_manager * const mgr = m_op.get_manager ();
1435	tree base_type = m_op.m_base_region->get_type ();
1436	const svalue *idx_sval
1437	= mgr->get_or_create_constant_svalue (cst_expr: idx_cst);
1438	const region *element_reg = mgr->get_element_region (parent: m_op.m_base_region,
1439	TREE_TYPE (base_type),
1440	index: idx_sval);
1441	const access_range element_range (*element_reg, mgr);
1442	const table::range_t element_x_range
1443	= btm.get_table_x_for_range (range: element_range);
1444
1445	t.maybe_set_cell_span (span: table::rect_t (element_x_range,
1446	table_y_range),
1447	content: fmt_styled_string (sm, fmt: "[%E]", idx_cst));
1448
1449	return element_x_range;
1450	}
1451
1452	table make_table (const bit_to_table_map &btm,
1453	style_manager &sm) const final override
1454	{
1455	table t (table::size_t (btm.get_num_columns (), 0));
1456
1457	if (tree base_type = m_op.m_base_region->get_type ())
1458	if (TREE_CODE (base_type) == ARRAY_TYPE)
1459	add_array_elements_to_table (t, btm, sm);
1460
1461	/* Make use of m_existing_sval_spatial_item, if any. */
1462	if (m_existing_sval_spatial_item)
1463	{
1464	table table_for_existing
1465	= m_existing_sval_spatial_item->make_table (btm, sm);
1466	const int table_y = t.add_rows (num: table_for_existing.get_size ().h);
1467	t.add_other_table (other: std::move (table_for_existing),
1468	offset: table::coord_t (0, table_y));
1469	}
1470
1471	access_range valid_bits = m_op.get_valid_bits ();
1472	const int table_y = t.add_row ();
1473	const int table_h = 1;
1474	table::rect_t rect = btm.get_table_rect (range: valid_bits, table_y, table_h);
1475	styled_string s;
1476	switch (m_op.m_base_region->get_kind ())
1477	{
1478	default:
1479	s = styled_string (sm, _("region"));
1480	break;
1481	case RK_DECL:
1482	{
1483	const decl_region *decl_reg
1484	= as_a <const decl_region *> (p: m_op.m_base_region);
1485	tree decl = decl_reg->get_decl ();
1486	s = fmt_styled_string (sm, fmt: "%qE (type: %qT)",
1487	decl,
1488	TREE_TYPE (decl));
1489	}
1490	break;
1491	case RK_HEAP_ALLOCATED:
1492	{
1493	if (m_region_creation_event_id.known_p ())
1494	s = fmt_styled_string (sm, _("buffer allocated on heap at %@"),
1495	&m_region_creation_event_id);
1496	else
1497	s = styled_string (sm, _("heap-allocated buffer"));
1498	}
1499	break;
1500	case RK_ALLOCA:
1501	{
1502	if (m_region_creation_event_id.known_p ())
1503	s = fmt_styled_string (sm, _("buffer allocated on stack at %@"),
1504	&m_region_creation_event_id);
1505	else
1506	s = styled_string (sm, _("stack-allocated buffer"));
1507	}
1508	break;
1509	case RK_STRING:
1510	{
1511	const string_region *string_reg
1512	= as_a <const string_region *> (p: m_op.m_base_region);
1513	tree string_cst = string_reg->get_string_cst ();
1514	s = fmt_styled_string (sm, _("string literal (type: %qT)"),
1515	TREE_TYPE (string_cst));
1516	}
1517	break;
1518	}
1519	t.set_cell_span (span: rect, content: std::move (s));
1520
1521	return t;
1522	}
1523
1524	private:
1525	const access_operation &m_op;
1526	diagnostic_event_id_t m_region_creation_event_id;
1527	mutable const boundaries *m_boundaries;
1528	const svalue *m_existing_sval;
1529	std::unique_ptr<spatial_item> m_existing_sval_spatial_item;
1530	};
1531
1532	/* Subclass of spatial_item for visualizing the region of memory
1533	that's actually accessed by the read or write, for reads and
1534	for write cases where we don't know the svalue written. */
1535
1536	class accessed_region_spatial_item : public spatial_item
1537	{
1538	public:
1539	accessed_region_spatial_item (const access_operation &op) : m_op (op) {}
1540
1541	void add_boundaries (boundaries &out, logger *logger) const final override
1542	{
1543	LOG_SCOPE (logger);
1544	access_range actual_bits = m_op.get_actual_bits ();
1545	if (logger)
1546	{
1547	logger->start_log_line ();
1548	logger->log_partial (fmt: "actual bits: ");
1549	actual_bits.dump_to_pp (pp: logger->get_printer (), simple: true);
1550	logger->end_log_line ();
1551	}
1552	out.add (range: actual_bits, kind: boundaries::kind::HARD);
1553	}
1554
1555	table make_table (const bit_to_table_map &btm,
1556	style_manager &sm) const final override
1557	{
1558	table t (table::size_t (btm.get_num_columns (), 1));
1559
1560	access_range actual_bits = m_op.get_actual_bits ();
1561	const int table_y = 0;
1562	const int table_h = 1;
1563	table::rect_t rect = btm.get_table_rect (range: actual_bits, table_y, table_h);
1564	t.set_cell_span (span: rect, content: styled_string (get_label_string (sm)));
1565
1566	return t;
1567	}
1568
1569	private:
1570	styled_string get_label_string (style_manager &sm) const
1571	{
1572	const access_range accessed_bits (m_op.get_actual_bits ());
1573	return get_access_size_str (sm,
1574	op: m_op,
1575	accessed_range: accessed_bits,
1576	type: m_op.m_reg.get_type ());
1577	}
1578
1579	const access_operation &m_op;
1580	};
1581
1582	/* Subclass of spatial_item for when we know the svalue being written
1583	to the accessed region.
1584	Can be subclassed to give visualizations of specific kinds of svalue. */
1585
1586	class written_svalue_spatial_item : public spatial_item
1587	{
1588	public:
1589	written_svalue_spatial_item (const access_operation &op,
1590	const svalue &sval,
1591	access_range actual_bits)
1592	: m_op (op), m_sval (sval), m_actual_bits (actual_bits)
1593	{}
1594
1595	void add_boundaries (boundaries &out, logger *logger) const override
1596	{
1597	LOG_SCOPE (logger);
1598	out.add (range: m_actual_bits, kind: boundaries::kind::HARD);
1599	}
1600
1601	table make_table (const bit_to_table_map &btm,
1602	style_manager &sm) const override
1603	{
1604	table t (table::size_t (btm.get_num_columns (), 0));
1605
1606	const int table_y = t.add_row ();
1607	const int table_h = 1;
1608	table::rect_t rect = btm.get_table_rect (range: m_actual_bits, table_y, table_h);
1609	t.set_cell_span (span: rect, content: styled_string (get_label_string (sm)));
1610	return t;
1611	}
1612
1613	protected:
1614	styled_string get_label_string (style_manager &sm) const
1615	{
1616	tree rep_tree = m_op.m_model.get_representative_tree (sval: &m_sval);
1617	if (rep_tree)
1618	{
1619	if (TREE_CODE (rep_tree) == SSA_NAME)
1620	if (tree var = SSA_NAME_VAR (rep_tree))
1621	rep_tree = var;
1622	switch (TREE_CODE (rep_tree))
1623	{
1624	default:
1625	break;
1626	case INTEGER_CST:
1627	return fmt_styled_string (sm, _("write of %<(%T) %E%>"),
1628	TREE_TYPE (rep_tree),
1629	rep_tree);
1630
1631	case PARM_DECL:
1632	case VAR_DECL:
1633	return fmt_styled_string (sm, _("write from %qE (type: %qT)"),
1634	rep_tree,
1635	TREE_TYPE (rep_tree));
1636	break;
1637	}
1638	}
1639
1640	const access_range accessed_bits (m_op.get_actual_bits ());
1641	return get_access_size_str (sm,
1642	op: m_op,
1643	accessed_range: accessed_bits,
1644	type: m_sval.get_type ());
1645	}
1646
1647	const access_operation &m_op;
1648	const svalue &m_sval;
1649	access_range m_actual_bits;
1650	};
1651
1652	/* Subclass of svalue_spatial_item for initial_svalue of a string_region
1653	i.e. for string literals.
1654
1655	There are three cases:
1656	(a) for long strings, show just the head and tail of the string,
1657	with an ellipsis:
1658	+---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
1659	|[0]|[1]|[2]|[3]|[4]|[5]| |[440]|[441]|[442]|[443]|[444]|[445]|
1660	+---+---+---+---+---+---+ ... +-----+-----+-----+-----+-----+-----+
1661	|‘L’|‘o’|‘r’|‘e’|‘m’|‘ ’| | ‘o’ | ‘r’ | ‘u’ | ‘m’ | ‘.’ | NUL |
1662	+---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
1663	| string literal (type: ‘char[446]’) |
1664	+----------------------------------------------------------------------+
1665	(b) For sufficiently short strings, show the full string:
1666	+----------+---------+---------+---------+---------+ +-----------------+
1667	| [0] | [1] | [2] | [3] | [4] | | [5] |
1668	+----------+---------+---------+---------+---------+ +-----------------+
1669	| ‘h’ | ‘e’ | ‘l’ | ‘l’ | ‘o’ | | NUL |
1670	+----------+---------+---------+---------+---------+-+-----------------+
1671	| string literal (type: ‘char[6]’) |
1672	+----------------------------------------------------------------------+
1673	(c) for non-ASCII strings that are short enough to show the full string,
1674	show how unicode code points of the bytes decoded as UTF-8:
1675	+-----+-----+-----+----+----++----+----+----+----+----+----+----+------+
1676	| [0] | [1] | [2] |[3] |[4] ||[5] |[6] |[7] |[8] |[9] |[10]|[11]| [12] |
1677	+-----+-----+-----+----+----++----+----+----+----+----+----+----+------+
1678	|0xe6 |0x96 |0x87 |0xe5|0xad||0x97|0xe5|0x8c|0x96|0xe3|0x81|0x91| 0x00 |
1679	+-----+-----+-----+----+----++----+----+----+----+----+----+----+------+
1680	| U+6587 | U+5b57 | U+5316 | U+3051 |U+0000|
1681	+-----------------+---------------+--------------+--------------+------+
1682	| string literal (type: ‘char[13]’) |
1683	+----------------------------------------------------------------------+
1684	and show the characters themselves if unicode is supported and they are not
1685	control characters:
1686	┌─────┬─────┬─────┬────┬────┐┌────┬────┬────┬────┬────┬────┬────┬──────┐
1687	│ [0] │ [1] │ [2] │[3] │[4] ││[5] │[6] │[7] │[8] │[9] │[10]│[11]│ [12] │
1688	├─────┼─────┼─────┼────┼────┤├────┼────┼────┼────┼────┼────┼────┼──────┤
1689	│0xe6 │0x96 │0x87 │0xe5│0xad││0x97│0xe5│0x8c│0x96│0xe3│0x81│0x91│ 0x00 │
1690	├─────┴─────┴─────┼────┴────┴┴────┼────┴────┴────┼────┴────┴────┼──────┤
1691	│ U+6587 │ U+5b57 │ U+5316 │ U+3051 │U+0000│
1692	├─────────────────┼───────────────┼──────────────┼──────────────┼──────┤
1693	│ 文 │ 字 │ 化 │ け │ NUL │
1694	├─────────────────┴───────────────┴──────────────┴──────────────┴──────┤
1695	│ string literal (type: ‘char[13]’) │
1696	└──────────────────────────────────────────────────────────────────────┘
1697	*/
1698
1699	class string_literal_spatial_item : public svalue_spatial_item
1700	{
1701	public:
1702	string_literal_spatial_item (const svalue &sval,
1703	access_range actual_bits,
1704	const string_region &string_reg,
1705	const theme &theme,
1706	enum kind kind)
1707	: svalue_spatial_item (sval, actual_bits, kind),
1708	m_string_reg (string_reg),
1709	m_theme (theme),
1710	m_ellipsis_threshold (param_analyzer_text_art_string_ellipsis_threshold),
1711	m_ellipsis_head_len (param_analyzer_text_art_string_ellipsis_head_len),
1712	m_ellipsis_tail_len (param_analyzer_text_art_string_ellipsis_tail_len),
1713	m_show_full_string (calc_show_full_string ()),
1714	m_show_utf8 (m_show_full_string && !pure_ascii_p ())
1715	{
1716	}
1717
1718	void add_boundaries (boundaries &out, logger *logger) const override
1719	{
1720	LOG_SCOPE (logger);
1721	out.add (range: m_bits, kind: m_kind == svalue_spatial_item::kind::WRITTEN
1722	? boundaries::kind::HARD
1723	: boundaries::kind::SOFT);
1724
1725	tree string_cst = get_string_cst ();
1726	/* TREE_STRING_LENGTH is sizeof, not strlen. */
1727	if (m_show_full_string)
1728	out.add_all_bytes_in_range (range: m_bits);
1729	else
1730	{
1731	byte_range bytes (0, 0);
1732	bool valid = m_bits.as_concrete_byte_range (out: &bytes);
1733	gcc_assert (valid);
1734	byte_range head_of_string (bytes.get_start_byte_offset (),
1735	m_ellipsis_head_len);
1736	out.add_all_bytes_in_range (bytes: head_of_string);
1737	byte_range tail_of_string
1738	((bytes.get_start_byte_offset ()
1739	+ TREE_STRING_LENGTH (string_cst)
1740	- m_ellipsis_tail_len),
1741	m_ellipsis_tail_len);
1742	out.add_all_bytes_in_range (bytes: tail_of_string);
1743	/* Adding the above pair of ranges will also effectively add
1744	the boundaries of the range of ellipsized chars, as they're
1745	exactly in between head_of_string and tail_of_string. */
1746	}
1747	}
1748
1749	table make_table (const bit_to_table_map &btm,
1750	style_manager &sm) const override
1751	{
1752	table t (table::size_t (btm.get_num_columns (), 0));
1753
1754	const int byte_idx_table_y = (m_kind == svalue_spatial_item::kind::WRITTEN
1755	? t.add_row ()
1756	: -1);
1757	const int byte_val_table_y = t.add_row ();
1758
1759	byte_range bytes (0, 0);
1760	bool valid = m_bits.as_concrete_byte_range (out: &bytes);
1761	gcc_assert (valid);
1762	tree string_cst = get_string_cst ();
1763	if (m_show_full_string)
1764	{
1765	for (byte_offset_t byte_idx_within_cluster
1766	= bytes.get_start_byte_offset ();
1767	byte_idx_within_cluster < bytes.get_next_byte_offset ();
1768	byte_idx_within_cluster = byte_idx_within_cluster + 1)
1769	add_column_for_byte
1770	(t, btm, sm, byte_idx_within_cluster,
1771	byte_idx_within_string: byte_idx_within_cluster - bytes.get_start_byte_offset (),
1772	byte_idx_table_y, byte_val_table_y);
1773
1774	if (m_show_utf8)
1775	{
1776	const bool show_unichars = m_theme.unicode_p ();
1777	const int utf8_code_point_table_y = t.add_row ();
1778	int utf8_character_table_y;
1779	if (show_unichars)
1780	utf8_character_table_y = t.add_row ();
1781
1782	/* We don't actually want the display widths here, but
1783	it's an easy way to decode UTF-8. */
1784	cpp_char_column_policy policy (8, cpp_wcwidth);
1785	cpp_display_width_computation dw (TREE_STRING_POINTER (string_cst),
1786	TREE_STRING_LENGTH (string_cst),
1787	policy);
1788	while (!dw.done ())
1789	{
1790	cpp_decoded_char decoded_char;
1791	dw.process_next_codepoint (out: &decoded_char);
1792
1793	if (!decoded_char.m_valid_ch)
1794	continue;
1795	size_t start_byte_idx
1796	= decoded_char.m_start_byte - TREE_STRING_POINTER (string_cst);
1797	byte_size_t size_in_bytes
1798	= decoded_char.m_next_byte - decoded_char.m_start_byte;
1799	byte_range cluster_bytes_for_codepoint
1800	(start_byte_idx + bytes.get_start_byte_offset (),
1801	size_in_bytes);
1802
1803	const table::rect_t code_point_table_rect
1804	= btm.get_table_rect (base_reg: &m_string_reg,
1805	bytes: cluster_bytes_for_codepoint,
1806	table_y: utf8_code_point_table_y, table_h: 1);
1807	char buf[100];
1808	sprintf (s: buf, format: "U+%04x", decoded_char.m_ch);
1809	t.set_cell_span (span: code_point_table_rect,
1810	content: styled_string (sm, buf));
1811
1812	if (show_unichars)
1813	{
1814	const table::rect_t character_table_rect
1815	= btm.get_table_rect (base_reg: &m_string_reg,
1816	bytes: cluster_bytes_for_codepoint,
1817	table_y: utf8_character_table_y, table_h: 1);
1818	if (cpp_is_printable_char (c: decoded_char.m_ch))
1819	t.set_cell_span (span: character_table_rect,
1820	content: styled_string (decoded_char.m_ch));
1821	else if (decoded_char.m_ch == 0)
1822	t.set_cell_span (span: character_table_rect,
1823	content: styled_string (sm, "NUL"));
1824	else
1825	t.set_cell_span (span: character_table_rect,
1826	content: styled_string (sm, ""));
1827	}
1828	}
1829	}
1830	}
1831	else
1832	{
1833	/* Head of string. */
1834	for (int byte_idx = 0; byte_idx < m_ellipsis_head_len; byte_idx++)
1835	add_column_for_byte (t, btm, sm,
1836	byte_idx_within_cluster: byte_idx + bytes.get_start_byte_offset (),
1837	byte_idx_within_string: byte_idx,
1838	byte_idx_table_y, byte_val_table_y);
1839
1840	/* Ellipsis. */
1841	const byte_range ellipsis_bytes
1842	(m_ellipsis_head_len + bytes.get_start_byte_offset (),
1843	TREE_STRING_LENGTH (string_cst)
1844	- (m_ellipsis_head_len + m_ellipsis_tail_len));
1845	const table::rect_t table_rect
1846	= ((byte_idx_table_y != -1)
1847	? btm.get_table_rect (base_reg: &m_string_reg, bytes: ellipsis_bytes,
1848	table_y: byte_idx_table_y, table_h: 2)
1849	: btm.get_table_rect (base_reg: &m_string_reg, bytes: ellipsis_bytes,
1850	table_y: byte_val_table_y, table_h: 1));
1851	t.set_cell_span(span: table_rect, content: styled_string (sm, "..."));
1852
1853	/* Tail of string. */
1854	for (int byte_idx
1855	= (TREE_STRING_LENGTH (string_cst) - m_ellipsis_tail_len);
1856	byte_idx < TREE_STRING_LENGTH (string_cst);
1857	byte_idx++)
1858	add_column_for_byte (t, btm, sm,
1859	byte_idx_within_cluster: byte_idx + bytes.get_start_byte_offset (),
1860	byte_idx_within_string: byte_idx,
1861	byte_idx_table_y, byte_val_table_y);
1862	}
1863
1864	if (m_kind == svalue_spatial_item::kind::WRITTEN)
1865	{
1866	const int summary_table_y = t.add_row ();
1867	t.set_cell_span (span: btm.get_table_rect (base_reg: &m_string_reg, bytes,
1868	table_y: summary_table_y, table_h: 1),
1869	content: fmt_styled_string (sm,
1870	_("string literal (type: %qT)"),
1871	TREE_TYPE (string_cst)));
1872	}
1873
1874	return t;
1875	}
1876
1877	tree get_string_cst () const { return m_string_reg.get_string_cst (); }
1878
1879	private:
1880	bool calc_show_full_string () const
1881	{
1882	tree string_cst = get_string_cst ();
1883	if (TREE_STRING_LENGTH (string_cst) < m_ellipsis_threshold)
1884	return true;
1885	if (TREE_STRING_LENGTH (string_cst) <
1886	(m_ellipsis_head_len + m_ellipsis_tail_len))
1887	return true;
1888	return false;
1889	}
1890
1891	bool pure_ascii_p () const
1892	{
1893	tree string_cst = get_string_cst ();
1894	for (unsigned byte_idx = 0;
1895	byte_idx < (unsigned) TREE_STRING_LENGTH (string_cst);
1896	byte_idx++)
1897	{
1898	unsigned char ch = TREE_STRING_POINTER (string_cst)[byte_idx];
1899	if (ch >= 0x80)
1900	return false;
1901	}
1902	return true;
1903	}
1904
1905	void add_column_for_byte (table &t, const bit_to_table_map &btm,
1906	style_manager &sm,
1907	const byte_offset_t byte_idx_within_cluster,
1908	const byte_offset_t byte_idx_within_string,
1909	const int byte_idx_table_y,
1910	const int byte_val_table_y) const
1911	{
1912	tree string_cst = get_string_cst ();
1913	gcc_assert (byte_idx_within_string >= 0);
1914	gcc_assert (byte_idx_within_string < TREE_STRING_LENGTH (string_cst));
1915
1916	const byte_range bytes (byte_idx_within_cluster, 1);
1917	if (byte_idx_table_y != -1)
1918	{
1919	const table::rect_t idx_table_rect
1920	= btm.get_table_rect (base_reg: &m_string_reg, bytes, table_y: byte_idx_table_y, table_h: 1);
1921	t.set_cell_span (span: idx_table_rect,
1922	content: fmt_styled_string (sm, fmt: "[%wu]",
1923	byte_idx_within_string.ulow ()));
1924	}
1925
1926	char byte_val
1927	= TREE_STRING_POINTER (string_cst)[byte_idx_within_string.ulow ()];
1928	const table::rect_t val_table_rect
1929	= btm.get_table_rect (base_reg: &m_string_reg, bytes, table_y: byte_val_table_y, table_h: 1);
1930	table_cell_content content (make_cell_content_for_byte (sm, byte_val));
1931	t.set_cell_span (span: val_table_rect, content: std::move (content));
1932	}
1933
1934	table_cell_content make_cell_content_for_byte (style_manager &sm,
1935	unsigned char byte_val) const
1936	{
1937	if (!m_show_utf8)
1938	{
1939	if (byte_val == '\0')
1940	return styled_string (sm, "NUL");
1941	else if (byte_val < 0x80)
1942	if (ISPRINT (byte_val))
1943	return fmt_styled_string (sm, fmt: "%qc", byte_val);
1944	}
1945	char buf[100];
1946	sprintf (s: buf, format: "0x%02x", byte_val);
1947	return styled_string (sm, buf);
1948	}
1949
1950	const string_region &m_string_reg;
1951	const theme &m_theme;
1952	const int m_ellipsis_threshold;
1953	const int m_ellipsis_head_len;
1954	const int m_ellipsis_tail_len;
1955	const bool m_show_full_string;
1956	const bool m_show_utf8;
1957	};
1958
1959	static std::unique_ptr<spatial_item>
1960	make_written_svalue_spatial_item (const access_operation &op,
1961	const svalue &sval,
1962	access_range actual_bits,
1963	const theme &theme)
1964	{
1965	if (const initial_svalue *initial_sval = sval.dyn_cast_initial_svalue ())
1966	if (const string_region *string_reg
1967	= initial_sval->get_region ()->dyn_cast_string_region ())
1968	return std::make_unique <string_literal_spatial_item>
1969	(args: sval, args&: actual_bits,
1970	args: *string_reg, args: theme,
1971	args: svalue_spatial_item::kind::WRITTEN);
1972	return std::make_unique <written_svalue_spatial_item> (args: op, args: sval, args&: actual_bits);
1973	}
1974
1975	static std::unique_ptr<spatial_item>
1976	make_existing_svalue_spatial_item (const svalue *sval,
1977	const access_range &bits,
1978	const theme &theme)
1979	{
1980	if (!sval)
1981	return nullptr;
1982
1983	switch (sval->get_kind ())
1984	{
1985	default:
1986	return nullptr;
1987
1988	case SK_INITIAL:
1989	{
1990	const initial_svalue *initial_sval = (const initial_svalue *)sval;
1991	if (const string_region *string_reg
1992	= initial_sval->get_region ()->dyn_cast_string_region ())
1993	return std::make_unique <string_literal_spatial_item>
1994	(args: *sval, args: bits,
1995	args: *string_reg, args: theme,
1996	args: svalue_spatial_item::kind::EXISTING);
1997	return nullptr;
1998	}
1999
2000	case SK_COMPOUND:
2001	return std::make_unique<compound_svalue_spatial_item>
2002	(args: *((const compound_svalue *)sval),
2003	args: bits,
2004	args: svalue_spatial_item::kind::EXISTING,
2005	args: theme);
2006	}
2007	}
2008
2009	/* Widget subclass implementing access diagrams. */
2010
2011	class access_diagram_impl : public vbox_widget
2012	{
2013	public:
2014	access_diagram_impl (const access_operation &op,
2015	diagnostic_event_id_t region_creation_event_id,
2016	style_manager &sm,
2017	const theme &theme,
2018	logger *logger)
2019	: m_op (op),
2020	m_region_creation_event_id (region_creation_event_id),
2021	m_sm (sm),
2022	m_theme (theme),
2023	m_logger (logger),
2024	m_invalid (false),
2025	m_valid_region_spatial_item (op, region_creation_event_id, theme),
2026	m_accessed_region_spatial_item (op),
2027	m_btm (),
2028	m_calc_req_size_called (false)
2029	{
2030	LOG_SCOPE (logger);
2031
2032	if (logger)
2033	{
2034	access_range invalid_before_bits;
2035	if (op.maybe_get_invalid_before_bits (out: &invalid_before_bits))
2036	invalid_before_bits.log (title: "invalid before range", logger&: *logger);
2037	access_range invalid_after_bits;
2038	if (op.maybe_get_invalid_after_bits (out: &invalid_after_bits))
2039	invalid_after_bits.log (title: "invalid after range", logger&: *logger);
2040
2041	if (op.m_sval_hint)
2042	{
2043	logger->start_log_line ();
2044	logger->log_partial (fmt: "sval_hint: ");
2045	op.m_sval_hint->dump_to_pp (pp: logger->get_printer (), simple: true);
2046	logger->end_log_line ();
2047	}
2048	}
2049
2050	/* Register painting styles. */
2051	{
2052	style valid_style (get_style_from_color_cap_name (name: "valid"));
2053	m_valid_style_id = m_sm.get_or_create_id (style: valid_style);
2054
2055	style invalid_style (get_style_from_color_cap_name (name: "invalid"));
2056	m_invalid_style_id = m_sm.get_or_create_id (style: invalid_style);
2057	}
2058
2059	if (op.m_sval_hint)
2060	{
2061	access_range actual_bits = m_op.get_actual_bits ();
2062	m_written_svalue_spatial_item
2063	= make_written_svalue_spatial_item (op: m_op,
2064	sval: *op.m_sval_hint,
2065	actual_bits,
2066	theme: m_theme);
2067	}
2068
2069	/* Two passes:
2070	First, figure out all of the boundaries of interest.
2071	Then use that to build child widgets showing the regions of interest,
2072	with a common tabular layout. */
2073
2074	m_boundaries = find_boundaries ();
2075	if (logger)
2076	m_boundaries->log (logger&: *logger);
2077
2078	/* Populate m_table_x_for_bit and m_bit_for_table_x.
2079	Each table column represents the range [offset, next_offset).
2080	We don't create a column in the table for the final offset, but we
2081	do populate it, so that looking at the table_x of one beyond the
2082	final table column gives us the upper bound offset. */
2083	m_btm.populate (boundaries: *m_boundaries, mgr&: *m_op.get_manager (), logger);
2084
2085	/* Gracefully reject cases where the boundary sorting has gone wrong
2086	(due to awkward combinations of symbolic values). */
2087	{
2088	table::range_t actual_bits_x_range
2089	= m_btm.get_table_x_for_range (range: m_op.get_actual_bits ());
2090	if (actual_bits_x_range.get_size () <= 0)
2091	{
2092	if (logger)
2093	logger->log (fmt: "giving up: bad table columns for actual_bits");
2094	m_invalid = true;
2095	return;
2096	}
2097	table::range_t valid_bits_x_range
2098	= m_btm.get_table_x_for_range (range: m_op.get_valid_bits ());
2099	if (valid_bits_x_range.get_size () <= 0)
2100	{
2101	if (logger)
2102	logger->log (fmt: "giving up: bad table columns for valid_bits");
2103	m_invalid = true;
2104	return;
2105	}
2106	}
2107
2108	m_col_widths
2109	= std::make_unique <table_dimension_sizes> (args: m_btm.get_num_columns ());
2110
2111	/* Now create child widgets. */
2112
2113	if (flag_analyzer_debug_text_art)
2114	{
2115	table t_headings (make_headings_table ());
2116	add_aligned_child_table (t: std::move (t_headings));
2117	}
2118
2119	if (m_written_svalue_spatial_item)
2120	{
2121	table t_sval (m_written_svalue_spatial_item->make_table (btm: m_btm, sm&: m_sm));
2122	add_aligned_child_table (t: std::move (t_sval));
2123	}
2124	else
2125	{
2126	table t_accessed
2127	(m_accessed_region_spatial_item.make_table (btm: m_btm, sm&: m_sm));
2128	add_aligned_child_table (t: std::move (t_accessed));
2129	}
2130
2131	add_direction_widget ();
2132
2133	table t_valid (m_valid_region_spatial_item.make_table (btm: m_btm, sm&: m_sm));
2134	add_invalid_accesses_to_region_table (t_region&: t_valid);
2135	add_aligned_child_table (t: std::move (t_valid));
2136
2137	add_valid_vs_invalid_ruler ();
2138	}
2139
2140	const char *get_desc () const override
2141	{
2142	return "access_diagram_impl";
2143	}
2144
2145	canvas::size_t calc_req_size () final override
2146	{
2147	if (m_invalid)
2148	return canvas::size_t (0, 0);
2149
2150	/* Now compute the size requirements for the tables. */
2151	for (auto iter : m_aligned_table_widgets)
2152	iter->get_cell_sizes ().pass_1 (table: iter->get_table ());
2153	for (auto iter : m_aligned_table_widgets)
2154	iter->get_cell_sizes ().pass_2 (table: iter->get_table ());
2155
2156	adjust_to_scale();
2157
2158	/* ...and relayout the tables. */
2159	for (auto iter : m_aligned_table_widgets)
2160	iter->recalc_coords ();
2161
2162	/* Populate the canvas_x per table_x. */
2163	m_col_start_x.clear ();
2164	int iter_canvas_x = 0;
2165	for (auto w : m_col_widths->m_requirements)
2166	{
2167	m_col_start_x.push_back (x: iter_canvas_x);
2168	iter_canvas_x += w + 1;
2169	}
2170	m_col_start_x.push_back (x: iter_canvas_x);
2171
2172	m_calc_req_size_called = true;
2173
2174	return vbox_widget::calc_req_size ();
2175	}
2176
2177	int get_canvas_x_for_table_x (int table_x) const
2178	{
2179	gcc_assert (m_calc_req_size_called);
2180	return m_col_start_x[table_x];
2181	}
2182
2183	canvas::range_t get_canvas_x_range (const table::range_t &table_x_range) const
2184	{
2185	gcc_assert (m_calc_req_size_called);
2186	return canvas::range_t (get_canvas_x_for_table_x (table_x: table_x_range.start),
2187	get_canvas_x_for_table_x (table_x: table_x_range.next));
2188	}
2189
2190	const access_operation &get_op () const { return m_op; }
2191
2192	style::id_t get_style_id_for_validity (bool is_valid) const
2193	{
2194	return is_valid ? m_valid_style_id : m_invalid_style_id;
2195	}
2196
2197	const theme &get_theme () const { return m_theme; }
2198
2199	private:
2200	/* Figure out all of the boundaries of interest when visualizing ths op. */
2201	std::unique_ptr<boundaries>
2202	find_boundaries () const
2203	{
2204	auto result
2205	= std::make_unique<boundaries> (args: *m_op.m_base_region, args: m_logger);
2206
2207	m_valid_region_spatial_item.add_boundaries (out&: *result, logger: m_logger);
2208	m_accessed_region_spatial_item.add_boundaries (out&: *result, logger: m_logger);
2209	if (m_written_svalue_spatial_item)
2210	m_written_svalue_spatial_item->add_boundaries (out&: *result, m_logger);
2211
2212	return result;
2213	}
2214
2215	void add_aligned_child_table (table t)
2216	{
2217	x_aligned_table_widget *w
2218	= new x_aligned_table_widget (std::move (t), m_theme, *m_col_widths);
2219	m_aligned_table_widgets.push_back (x: w);
2220	add_child (child: std::unique_ptr<widget> (w));
2221	}
2222
2223	/* Create a table showing headings for use by -fanalyzer-debug-text-art, for
2224	example:
2225	+---------+-----------+-----------+---+--------------------------------+
2226	| tc0 | tc1 | tc2 |tc3| tc4 |
2227	+---------+-----------+-----------+---+--------------------------------+
2228	|bytes 0-3|bytes 4-35 |bytes 36-39| | bytes 40-43 |
2229	+---------+-----------+-----------+ +--------------------------------+
2230	which has:
2231	- a row showing the table column numbers, labelled "tc0", "tc1", etc
2232	- a row showing the memory range of each table column that has one. */
2233
2234	table make_headings_table () const
2235	{
2236	table t (table::size_t (m_btm.get_num_columns (), 2));
2237
2238	for (int table_x = 0; table_x < t.get_size ().w; table_x++)
2239	{
2240	const int table_y = 0;
2241	t.set_cell (coord: table::coord_t (table_x, table_y),
2242	content: fmt_styled_string (sm&: m_sm, fmt: "tc%i", table_x));
2243	}
2244	for (int table_x = 0; table_x < t.get_size ().w; table_x++)
2245	{
2246	const int table_y = 1;
2247	access_range range_for_column (NULL, bit_range (0, 0));
2248	if (m_btm.maybe_get_access_range_for_table_x (table_x,
2249	out: &range_for_column))
2250	{
2251	pretty_printer pp;
2252	pp_format_decoder (pp: &pp) = default_tree_printer;
2253	range_for_column.dump_to_pp (pp: &pp, simple: true);
2254	t.set_cell (coord: table::coord_t (table_x, table_y),
2255	content: styled_string (m_sm, pp_formatted_text (&pp)));
2256	}
2257	}
2258
2259	return t;
2260	}
2261
2262	void add_direction_widget ()
2263	{
2264	add_child (child: std::make_unique<direction_widget> (args&: *this, args&: m_btm));
2265	}
2266
2267	void add_invalid_accesses_to_region_table (table &t_region)
2268	{
2269	gcc_assert (t_region.get_size ().w == (int)m_btm.get_num_columns ());
2270
2271	const int table_y = 0;
2272	const int table_h = t_region.get_size ().h;
2273
2274	access_range invalid_before_bits;
2275	if (m_op.maybe_get_invalid_before_bits (out: &invalid_before_bits))
2276	{
2277	t_region.set_cell_span (span: m_btm.get_table_rect (range: invalid_before_bits,
2278	table_y, table_h),
2279	content: styled_string (m_sm,
2280	_("before valid range")));
2281	}
2282	access_range invalid_after_bits;
2283	if (m_op.maybe_get_invalid_after_bits (out: &invalid_after_bits))
2284	{
2285	t_region.set_cell_span (span: m_btm.get_table_rect (range: invalid_after_bits,
2286	table_y, table_h),
2287	content: styled_string (m_sm,
2288	_("after valid range")));
2289	}
2290	}
2291
2292	void maybe_add_gap (x_aligned_x_ruler_widget *w,
2293	const access_range &lower,
2294	const access_range &upper) const
2295	{
2296	LOG_SCOPE (m_logger);
2297	if (m_logger)
2298	{
2299	lower.log (title: "lower", logger&: *m_logger);
2300	upper.log (title: "upper", logger&: *m_logger);
2301	}
2302	region_model_manager *mgr = m_op.get_manager ();
2303	const svalue &lower_next = lower.m_next.calc_symbolic_bit_offset (mgr);
2304	const svalue &upper_start = upper.m_start.calc_symbolic_bit_offset (mgr);
2305	const svalue *num_bits_gap
2306	= mgr->get_or_create_binop (NULL_TREE, op: MINUS_EXPR,
2307	arg0: &upper_start, arg1: &lower_next);
2308	if (m_logger)
2309	m_logger->log (fmt: "num_bits_gap: %qs", num_bits_gap->get_desc ().get ());
2310
2311	const svalue *zero = mgr->get_or_create_int_cst (NULL_TREE, cst: 0);
2312	tristate ts_gt_zero = m_op.m_model.eval_condition (lhs: num_bits_gap,
2313	op: GT_EXPR,
2314	rhs: zero);
2315	if (ts_gt_zero.is_false ())
2316	{
2317	if (m_logger)
2318	m_logger->log (fmt: "rejecting as not > 0");
2319	return;
2320	}
2321
2322	bit_size_expr num_bits (*num_bits_gap);
2323	if (auto p = num_bits.maybe_get_formatted_str (sm&: m_sm, model: m_op.m_model,
2324	_("%wi bit"),
2325	_("%wi bits"),
2326	_("%wi byte"),
2327	_("%wi bytes"),
2328	_("%qs bits"),
2329	_("%qs bytes")))
2330	{
2331	styled_string label = std::move (*p.get ());
2332	w->add_range (x_range: m_btm.get_table_x_for_range
2333	(range: access_range (lower.m_next,
2334	upper.m_start,
2335	*mgr)),
2336	text: std::move (label),
2337	style_id: style::id_plain);
2338	}
2339	}
2340
2341	styled_string
2342	make_warning_string (styled_string &&text)
2343	{
2344	styled_string result;
2345	if (!m_theme.emojis_p ())
2346	return std::move (text);
2347
2348	result.append (suffix: styled_string (0x26A0, /* U+26A0 WARNING SIGN. */
2349	true));
2350	/* U+26A0 WARNING SIGN has East_Asian_Width == Neutral, but in its
2351	emoji variant is printed (by vte at least) with a 2nd half
2352	overlapping the next char. Hence we add two spaces here: a space
2353	to be covered by this overlap, plus another space of padding. */
2354	result.append (suffix: styled_string (m_sm, " "));
2355	result.append (suffix: std::move (text));
2356	return result;
2357	}
2358
2359	/* Add a ruler child widet showing valid, invalid, and gaps. */
2360	void add_valid_vs_invalid_ruler ()
2361	{
2362	LOG_SCOPE (m_logger);
2363
2364	x_aligned_x_ruler_widget *w
2365	= new x_aligned_x_ruler_widget (*this, m_theme);
2366
2367	access_range invalid_before_bits;
2368	if (m_op.maybe_get_invalid_before_bits (out: &invalid_before_bits))
2369	{
2370	if (m_logger)
2371	invalid_before_bits.log (title: "invalid_before_bits", logger&: *m_logger);
2372	bit_size_expr num_before_bits
2373	(invalid_before_bits.get_size (mgr: m_op.get_manager ()));
2374	std::unique_ptr<styled_string> label;
2375	if (m_op.m_dir == access_direction::read)
2376	label = num_before_bits.maybe_get_formatted_str
2377	(sm&: m_sm, model: m_op.m_model,
2378	_("under-read of %wi bit"),
2379	_("under-read of %wi bits"),
2380	_("under-read of %wi byte"),
2381	_("under-read of %wi bytes"),
2382	_("under-read of %qs bits"),
2383	_("under-read of %qs bytes"));
2384	else
2385	label = num_before_bits.maybe_get_formatted_str
2386	(sm&: m_sm, model: m_op.m_model,
2387	_("underwrite of %wi bit"),
2388	_("underwrite of %wi bits"),
2389	_("underwrite of %wi byte"),
2390	_("underwrite of %wi bytes"),
2391	_("underwrite of %qs bits"),
2392	_("underwrite of %qs bytes"));
2393	if (label)
2394	w->add_range (x_range: m_btm.get_table_x_for_range (range: invalid_before_bits),
2395	text: make_warning_string (text: std::move (*label)),
2396	style_id: m_invalid_style_id);
2397	}
2398	else
2399	{
2400	if (m_logger)
2401	m_logger->log (fmt: "no invalid_before_bits");
2402	}
2403
2404	/* It would be nice to be able to use std::optional<access_range> here,
2405	but std::optional is C++17. */
2406	bool got_valid_bits = false;
2407	access_range valid_bits (m_op.get_valid_bits ());
2408	bit_size_expr num_valid_bits (valid_bits.get_size (mgr: m_op.get_manager ()));
2409	if (m_logger)
2410	valid_bits.log (title: "valid_bits", logger&: *m_logger);
2411
2412	got_valid_bits = true;
2413	maybe_add_gap (w, lower: invalid_before_bits, upper: valid_bits);
2414
2415	std::unique_ptr<styled_string> label;
2416	if (m_op.m_dir == access_direction::read)
2417	label = num_valid_bits.maybe_get_formatted_str (sm&: m_sm,
2418	model: m_op.m_model,
2419	_("size: %wi bit"),
2420	_("size: %wi bits"),
2421	_("size: %wi byte"),
2422	_("size: %wi bytes"),
2423	_("size: %qs bits"),
2424	_("size: %qs bytes"));
2425	else
2426	label
2427	= num_valid_bits.maybe_get_formatted_str (sm&: m_sm,
2428	model: m_op.m_model,
2429	_("capacity: %wi bit"),
2430	_("capacity: %wi bits"),
2431	_("capacity: %wi byte"),
2432	_("capacity: %wi bytes"),
2433	_("capacity: %qs bits"),
2434	_("capacity: %qs bytes"));
2435	if (label)
2436	w->add_range (x_range: m_btm.get_table_x_for_range (range: m_op.get_valid_bits ()),
2437	text: std::move (*label),
2438	style_id: m_valid_style_id);
2439
2440	access_range invalid_after_bits;
2441	if (m_op.maybe_get_invalid_after_bits (out: &invalid_after_bits))
2442	{
2443	if (got_valid_bits)
2444	maybe_add_gap (w, lower: valid_bits, upper: invalid_after_bits);
2445
2446	if (m_logger)
2447	invalid_before_bits.log (title: "invalid_after_bits", logger&: *m_logger);
2448
2449	bit_size_expr num_after_bits
2450	(invalid_after_bits.get_size (mgr: m_op.get_manager ()));
2451	std::unique_ptr<styled_string> label;
2452	if (m_op.m_dir == access_direction::read)
2453	label = num_after_bits.maybe_get_formatted_str
2454	(sm&: m_sm, model: m_op.m_model,
2455	_("over-read of %wi bit"),
2456	_("over-read of %wi bits"),
2457	_("over-read of %wi byte"),
2458	_("over-read of %wi bytes"),
2459	_("over-read of %qs bits"),
2460	_("over-read of %qs bytes"));
2461	else
2462	label = num_after_bits.maybe_get_formatted_str
2463	(sm&: m_sm, model: m_op.m_model,
2464	_("overflow of %wi bit"),
2465	_("overflow of %wi bits"),
2466	_("overflow of %wi byte"),
2467	_("overflow of %wi bytes"),
2468	_("overflow of %qs bits"),
2469	_("overflow of %qs bytes"));
2470	if (label)
2471	w->add_range (x_range: m_btm.get_table_x_for_range (range: invalid_after_bits),
2472	text: make_warning_string (text: std::move (*label)),
2473	style_id: m_invalid_style_id);
2474	}
2475	else
2476	{
2477	if (m_logger)
2478	m_logger->log (fmt: "no invalid_after_bits");
2479	}
2480
2481	add_child (child: std::unique_ptr<widget> (w));
2482	}
2483
2484	/* Subroutine of calc_req_size.
2485	Try to allocate surplus canvas width to table columns to make the
2486	per table-column canvas widths closer to being to scale.
2487	See e.g.:
2488	https://en.wikipedia.org/wiki/Fair_item_allocation
2489	https://en.wikipedia.org/wiki/Mathematics_of_apportionment
2490	*/
2491	void adjust_to_scale ()
2492	{
2493	LOG_SCOPE (m_logger);
2494	const unsigned num_columns = m_btm.get_num_columns ();
2495	std::vector<bit_offset_t> bit_sizes (num_columns);
2496	for (unsigned table_x = 0; table_x < num_columns; table_x++)
2497	{
2498	access_range range_for_column (NULL, bit_range (0, 0));
2499	if (m_btm.maybe_get_access_range_for_table_x (table_x,
2500	out: &range_for_column))
2501	{
2502	bit_size_t size_in_bits;
2503	if (!range_for_column.get_size_in_bits (out: &size_in_bits))
2504	size_in_bits = BITS_PER_UNIT; // arbitrary non-zero value
2505	gcc_assert (size_in_bits > 0);
2506	bit_sizes[table_x] = size_in_bits;
2507	}
2508	else
2509	bit_sizes[table_x] = 0;
2510	}
2511
2512	while (adjust_to_scale_once (bit_sizes))
2513	{
2514	}
2515	}
2516	bool adjust_to_scale_once (const std::vector<bit_offset_t> &bit_sizes)
2517	{
2518	LOG_SCOPE (m_logger);
2519
2520	const unsigned num_columns = m_btm.get_num_columns ();
2521
2522	/* Find the total canvas width currently required.
2523	Require one extra canvas column for the right-hand border
2524	of the table. */
2525	int total_width = 1;
2526	for (unsigned table_x = 0; table_x < num_columns; table_x++)
2527	{
2528	int canvas_w = m_col_widths->m_requirements[table_x];
2529	gcc_assert (canvas_w >= 0);
2530	total_width += canvas_w + 1;
2531	}
2532
2533	const int max_width = param_analyzer_text_art_ideal_canvas_width;
2534	if (total_width >= max_width)
2535	{
2536	if (m_logger)
2537	m_logger->log (fmt: "bailing out: total_width=%i ,>= max_width (%i)\n",
2538	total_width, max_width);
2539	return false;
2540	}
2541
2542	const int fixed_point = 1024;
2543	std::vector<bit_offset_t> canvas_w_per_bit (num_columns);
2544	for (unsigned table_x = 0; table_x < num_columns; table_x++)
2545	{
2546	bit_offset_t bit_size = bit_sizes[table_x];
2547	if (bit_size > 0)
2548	canvas_w_per_bit[table_x]
2549	= (m_col_widths->m_requirements[table_x] * fixed_point) / bit_size;
2550	else
2551	canvas_w_per_bit[table_x] = INT_MAX;
2552	}
2553
2554	/* Find the min canvas per bit, and give an extra canvas column to
2555	the table column that has least. */
2556	size_t min_idx = std::distance (first: canvas_w_per_bit.begin (),
2557	last: std::min_element (first: canvas_w_per_bit.begin (),
2558	last: canvas_w_per_bit.end ()));
2559	m_col_widths->m_requirements[min_idx] += 1;
2560	if (m_logger)
2561	m_logger->log (fmt: "adding 1 canvas_w to column %i\n", (int)min_idx);
2562
2563	return true; // keep going
2564	}
2565
2566	const access_operation &m_op;
2567	diagnostic_event_id_t m_region_creation_event_id;
2568	style_manager &m_sm;
2569	const theme &m_theme;
2570	logger *m_logger;
2571	/* In lieu of being able to throw exceptions, a flag to mark this object
2572	as "invalid". */
2573	bool m_invalid;
2574
2575	style::id_t m_valid_style_id;
2576	style::id_t m_invalid_style_id;
2577
2578	valid_region_spatial_item m_valid_region_spatial_item;
2579	accessed_region_spatial_item m_accessed_region_spatial_item;
2580	std::unique_ptr<spatial_item> m_written_svalue_spatial_item;
2581
2582	std::unique_ptr<boundaries> m_boundaries;
2583
2584	bit_to_table_map m_btm;
2585
2586	bool m_calc_req_size_called;
2587
2588	/* Column widths shared by all x_aligned_table_widget,
2589	created once we know how many columns we need. */
2590	std::unique_ptr<table_dimension_sizes> m_col_widths;
2591
2592	/* All of the child x_aligned_table_widget that share
2593	column widths. */
2594	std::vector<x_aligned_table_widget *> m_aligned_table_widgets;
2595
2596	/* Mapping from table_x to canvas_x. */
2597	std::vector<int> m_col_start_x;
2598	};
2599
2600	x_ruler
2601	x_aligned_x_ruler_widget::make_x_ruler () const
2602	{
2603	x_ruler r (x_ruler::label_dir::BELOW);
2604	for (auto& iter : m_labels)
2605	{
2606	canvas::range_t canvas_x_range
2607	= m_dia_impl.get_canvas_x_range (table_x_range: iter.m_table_x_range);
2608	/* Include the end-point. */
2609	canvas_x_range.next++;
2610	r.add_label (r: canvas_x_range, text: iter.m_text.copy (), style_id: iter.m_style_id,
2611	kind: x_ruler::label_kind::TEXT_WITH_BORDER);
2612	}
2613	return r;
2614	}
2615
2616	/* class direction_widget : public leaf_widget. */
2617
2618	/* Paint arrows indicating the direction of the access (read vs write),
2619	but only in the X-extent corresponding to the region that's actually
2620	accessed. */
2621
2622	void
2623	direction_widget::paint_to_canvas (canvas &canvas)
2624	{
2625	const access_range accessed_bits (m_dia_impl.get_op ().get_actual_bits ());
2626
2627	const access_range valid_bits (m_dia_impl.get_op ().get_valid_bits ());
2628
2629	for (unsigned table_x = 0; table_x < m_btm.get_num_columns (); table_x++)
2630	{
2631	access_range column_access_range;
2632	if (m_btm.maybe_get_access_range_for_table_x (table_x,
2633	out: &column_access_range))
2634	{
2635	/* Only paint arrows in the accessed region. */
2636	if (!accessed_bits.contains_p (other: column_access_range))
2637	continue;
2638
2639	/* Are we within the valid region? */
2640	const bool is_valid (valid_bits.contains_p (other: column_access_range));
2641	const style::id_t style_id
2642	= m_dia_impl.get_style_id_for_validity (is_valid);
2643	const canvas::range_t x_canvas_range
2644	= m_dia_impl.get_canvas_x_range (table_x_range: table::range_t (table_x,
2645	table_x + 1));
2646	const int canvas_x = x_canvas_range.get_midpoint ();
2647	m_dia_impl.get_theme ().paint_y_arrow
2648	(canvas,
2649	x: canvas_x,
2650	y_range: canvas::range_t (get_y_range ()),
2651	dir: (m_dia_impl.get_op ().m_dir == access_direction::read
2652	? theme::y_arrow_dir::UP
2653	: theme::y_arrow_dir::DOWN),
2654	style_id);
2655	}
2656	}
2657	}
2658
2659	/* class access_diagram : public text_art::wrapper_widget. */
2660
2661	/* To hide the implementation details, this is merely a wrapper around
2662	an access_diagram_impl. */
2663
2664	access_diagram::access_diagram (const access_operation &op,
2665	diagnostic_event_id_t region_creation_event_id,
2666	style_manager &sm,
2667	const theme &theme,
2668	logger *logger)
2669	: wrapper_widget
2670	(std::make_unique <access_diagram_impl> (args: op,
2671	args&: region_creation_event_id,
2672	args&: sm,
2673	args: theme,
2674	args&: logger))
2675	{
2676	}
2677
2678	#if CHECKING_P
2679
2680	namespace selftest {
2681
2682	/* Implementation detail of ASSERT_EQ_TYPELESS_INTEGER. */
2683
2684	static void
2685	assert_eq_typeless_integer (const location &loc,
2686	const svalue *sval,
2687	int expected_int_val)
2688	{
2689	ASSERT_NE_AT (loc, sval, nullptr);
2690	ASSERT_EQ_AT (loc, sval->get_kind (), SK_CONSTANT);
2691	ASSERT_EQ_AT (loc,
2692	wi::to_offset (sval->maybe_get_constant ()),
2693	expected_int_val);
2694	ASSERT_EQ_AT (loc, sval->get_type (), NULL_TREE);
2695	}
2696
2697	/* Assert that SVAL is a constant_svalue equal to EXPECTED_INT_VAL,
2698	with NULL_TREE as its type. */
2699
2700	#define ASSERT_EQ_TYPELESS_INTEGER(SVAL, EXPECTED_INT_VAL) \
2701	SELFTEST_BEGIN_STMT \
2702	assert_eq_typeless_integer ((SELFTEST_LOCATION), \
2703	(SVAL), \
2704	(EXPECTED_INT_VAL)); \
2705	SELFTEST_END_STMT
2706
2707
2708	/* Various tests of bit_size_expr::maybe_get_as_bytes. */
2709
2710	static void
2711	test_bit_size_expr_to_bytes ()
2712	{
2713	region_model_manager mgr;
2714
2715	/* 40 bits: should be 5 bytes. */
2716	{
2717	bit_size_expr num_bits (*mgr.get_or_create_int_cst (NULL_TREE, cst: 40));
2718	const svalue *as_bytes = num_bits.maybe_get_as_bytes (mgr);
2719	ASSERT_EQ_TYPELESS_INTEGER (as_bytes, 5);
2720	}
2721
2722	/* 41 bits: should not convert to bytes. */
2723	{
2724	bit_size_expr num_bits (*mgr.get_or_create_int_cst (NULL_TREE, cst: 41));
2725	const svalue *as_bytes = num_bits.maybe_get_as_bytes (mgr);
2726	ASSERT_EQ (as_bytes, nullptr);
2727	}
2728
2729	tree n = build_global_decl (name: "n", size_type_node);
2730
2731	const svalue *init_n
2732	= mgr.get_or_create_initial_value (reg: mgr.get_region_for_global (expr: n));
2733
2734	const svalue *n_times_8
2735	= mgr.get_or_create_binop (NULL_TREE, op: MULT_EXPR,
2736	arg0: init_n,
2737	arg1: mgr.get_or_create_int_cst (NULL_TREE, cst: 8));
2738
2739	/* (n * 8) bits should be n bytes */
2740	{
2741	bit_size_expr num_bits (*n_times_8);
2742	const svalue *as_bytes = num_bits.maybe_get_as_bytes (mgr);
2743	ASSERT_EQ (as_bytes, mgr.get_or_create_cast (NULL_TREE, init_n));
2744	}
2745
2746	/* (n * 8) + 16 bits should be n + 2 bytes */
2747	{
2748	bit_size_expr num_bits
2749	(*mgr.get_or_create_binop (NULL_TREE, op: PLUS_EXPR,
2750	arg0: n_times_8,
2751	arg1: mgr.get_or_create_int_cst (NULL_TREE, cst: 16)));
2752	const svalue *as_bytes = num_bits.maybe_get_as_bytes (mgr);
2753	ASSERT_EQ (as_bytes->get_kind (), SK_BINOP);
2754	const binop_svalue *binop = as_bytes->dyn_cast_binop_svalue ();
2755	ASSERT_EQ (binop->get_op (), PLUS_EXPR);
2756	ASSERT_EQ (binop->get_arg0 (), mgr.get_or_create_cast (NULL_TREE, init_n));
2757	ASSERT_EQ_TYPELESS_INTEGER (binop->get_arg1 (), 2);
2758	}
2759	}
2760
2761	/* Run all of the selftests within this file. */
2762
2763	void
2764	analyzer_access_diagram_cc_tests ()
2765	{
2766	test_bit_size_expr_to_bytes ();
2767	}
2768
2769	} // namespace selftest
2770
2771	#endif /* CHECKING_P */
2772
2773	} // namespace ana
2774
2775	#endif /* #if ENABLE_ANALYZER */
2776