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