/* Text art visualizations within -fanalyzer.
   Copyright (C) 2023 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#define INCLUDE_ALGORITHM
#define INCLUDE_MEMORY
#define INCLUDE_MAP
#define INCLUDE_SET
#define INCLUDE_VECTOR
#include "system.h"
#include "coretypes.h"
#include "coretypes.h"
#include "tree.h"
#include "function.h"
#include "basic-block.h"
#include "gimple.h"
#include "diagnostic.h"
#include "intl.h"
#include "make-unique.h"
#include "tree-diagnostic.h" /* for default_tree_printer.  */
#include "analyzer/analyzer.h"
#include "analyzer/region-model.h"
#include "analyzer/access-diagram.h"
#include "text-art/ruler.h"
#include "fold-const.h"

#if ENABLE_ANALYZER

/* Consider this code:
     int32_t arr[10];
     arr[10] = x;
   where we've emitted a buffer overflow diagnostic like this:
     out-of-bounds write from byte 40 till byte 43 but 'arr' ends at byte 40

   We want to emit a diagram that visualizes:
   - the spatial relationship between the valid region to access, versus
   the region that was actually accessed: does it overlap, was it touching,
   close, or far away?  Was it before or after in memory?  What are the
   relative sizes involved?
   - the direction of the access (read vs write)

   The following code supports emitting diagrams similar to the following:

   #                                        +--------------------------------+
   #                                        |write from ‘x’ (type: ‘int32_t’)|
   #                                        +--------------------------------+
   #                                                        |
   #                                                        |
   #                                                        v
   #  +---------+-----------+-----------+   +--------------------------------+
   #  |   [0]   |    ...    |    [9]    |   |       after valid range        |
   #  +---------+-----------+-----------+   |                                |
   #  |   ‘arr’ (type: ‘int32_t[10]’)   |   |                                |
   #  +---------------------------------+   +--------------------------------+
   #  |~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~|   |~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~|
   #                   |                                    |
   #         +---------+--------+                 +---------+---------+
   #         |capacity: 40 bytes|                 |overflow of 4 bytes|
   #         +------------------+                 +-------------------+

  where the diagram is laid out via table columns where each table column
  represents either a range of bits/bytes, or is a spacing column (to highlight
  the boundary between valid vs invalid accesses).  The table columns can be
  seen via -fanalyzer-debug-text-art.  For example, here there are 5 table
  columns ("tc0" through "tc4"):

   #  +---------+-----------+-----------+---+--------------------------------+
   #  |   tc0   |    tc1    |    tc2    |tc3|              tc4               |
   #  +---------+-----------+-----------+---+--------------------------------+
   #  |bytes 0-3|bytes 4-35 |bytes 36-39|   |          bytes 40-43           |
   #  +---------+-----------+-----------+   +--------------------------------+
   #
   #                                        +--------------------------------+
   #                                        |write from ‘x’ (type: ‘int32_t’)|
   #                                        +--------------------------------+
   #                                                        |
   #                                                        |
   #                                                        v
   #  +---------+-----------+-----------+   +--------------------------------+
   #  |   [0]   |    ...    |    [9]    |   |       after valid range        |
   #  +---------+-----------+-----------+   |                                |
   #  |   ‘arr’ (type: ‘int32_t[10]’)   |   |                                |
   #  +---------------------------------+   +--------------------------------+
   #  |~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~|   |~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~|
   #                   |                                    |
   #         +---------+--------+                 +---------+---------+
   #         |capacity: 40 bytes|                 |overflow of 4 bytes|
   #         +------------------+                 +-------------------+

  The diagram is built up from the following:

   #                                        +--------------------------------+
   #                                        | ITEM FOR SVALUE/ACCESSED REGION|
   #                                        +--------------------------------+
   #                                                        |
   #                                                        | DIRECTION WIDGET
   #                                                        v
   #  +---------------------------------+   +--------------------------------+
   #  |   VALID REGION                  |   | INVALID ACCESS                 |
   #  +---------------------------------+   +--------------------------------+
   #
   #  |                       VALID-VS-INVALID RULER                         |

  i.e. a vbox_widget containing 4 child widgets laid out vertically:
  - ALIGNED CHILD WIDGET: ITEM FOR SVALUE/ACCESSED REGION
  - DIRECTION WIDGET
  - ALIGNED CHILD WIDGET: VALID AND INVALID ACCESSES
  - VALID-VS-INVALID RULER.

  A more complicated example, given this overflow:
     char buf[100];
     strcpy (buf, LOREM_IPSUM);

   01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   02| |[0]|[1]|[2]|[3]|[4]|[5]|   ...    |[440]|[441]|[442]|[443]|[444]|[445]|
   03| +---+---+---+---+---+---+          +-----+-----+-----+-----+-----+-----+
   04| |'L'|'o'|'r'|'e'|'m'|' '|          | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
   05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   06| |                  string literal (type: 'char[446]')                  |
   07| +----------------------------------------------------------------------+
   08|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   09|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   10|   v   v   v   v   v   v  v  v    v    v     v     v     v     v     v
   11| +---+---------------------+----++--------------------------------------+
   12| |[0]|         ...         |[99]||          after valid range           |
   13| +---+---------------------+----+|                                      |
   14| |  'buf' (type: 'char[100]')   ||                                      |
   15| +------------------------------++--------------------------------------+
   16| |~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
   17|                |                                   |
   18|      +---------+---------+              +----------+----------+
   19|      |capacity: 100 bytes|              |overflow of 346 bytes|
   20|      +-------------------+              +---------------------+

 which is:

   01| ALIGNED CHILD WIDGET (lines 01-07): (string_region_spatial_item)-+-----+
   02| |[0]|[1]|[2]|[3]|[4]|[5]|   ...    |[440]|[441]|[442]|[443]|[444]|[445]|
   03| +---+---+---+---+---+---+          +-----+-----+-----+-----+-----+-----+
   04| |'L'|'o'|'r'|'e'|'m'|' '|          | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
   05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   06| |                  string literal (type: 'char[446]')                  |
   07| +----------------------------------------------------------------------+
   08| DIRECTION WIDGET (lines 08-10)   |    |     |     |     |     |     |
   09|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   10|   v   v   v   v   v   v  v  v    v    v     v     v     v     v     v
   11| ALIGNED CHILD WIDGET (lines 11-15)-------------------------------------+
   12| VALID REGION  ...         |[99]|| INVALID ACCESS                       |
   13| +---+---------------------+----+|                                      |
   14| |  'buf' (type: 'char[100]')   ||                                      |
   15| +------------------------------++--------------------------------------+
   16| VALID-VS-INVALID RULER (lines 16-20): ~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
   17|                |                                   |
   18|      +---------+---------+              +----------+----------+
   19|      |capacity: 100 bytes|              |overflow of 346 bytes|
   20|      +-------------------+              +---------------------+

   We build the diagram in several phases:
   - (1) we construct an access_diagram_impl widget.  Within the ctor, we have
   these subphases:
   -   (1.1) find all of the boundaries of interest
   -   (1.2) use the boundaries to build a bit_table_map, associating bit ranges
   with table columns (e.g. "byte 0 is column 0, bytes 1-98 are column 2" etc)
   -   (1.3) create child widgets that share this table-based geometry
   - (2) ask the widget for its size request
   -   (2.1) column widths and row heights for the table are computed by
   access_diagram_impl::calc_req_size
   -   (2.2) child widgets request sizes based on these widths/heights
   - (3) create a canvas of the appropriate size
   - (4) paint the widget hierarchy to the canvas.  */


using namespace text_art;

namespace ana {

static styled_string
fmt_styled_string (style_manager &sm,
		   const char *fmt, ...)
    ATTRIBUTE_GCC_DIAG(2, 3);

static styled_string
fmt_styled_string (style_manager &sm,
		   const char *fmt, ...)
{
  va_list ap;
  va_start (ap, fmt);
  styled_string result
    = styled_string::from_fmt_va (sm, default_tree_printer, fmt, &ap);
  va_end (ap);
  return result;
}

class access_diagram_impl;
class bit_to_table_map;

static void
pp_bit_size_t (pretty_printer *pp, bit_size_t num_bits)
{
  if (num_bits % BITS_PER_UNIT == 0)
    {
      byte_size_t num_bytes = num_bits / BITS_PER_UNIT;
      if (num_bytes == 1)
	pp_printf (pp, _("%wi byte"), num_bytes.to_uhwi ());
      else
	pp_printf (pp, _("%wi bytes"), num_bytes.to_uhwi ());
    }
  else
    {
      if (num_bits == 1)
	pp_printf (pp, _("%wi bit"), num_bits.to_uhwi ());
      else
	pp_printf (pp, _("%wi bits"), num_bits.to_uhwi ());
    }
}

static styled_string
get_access_size_str (style_manager &sm,
		     const access_operation &op,
		     access_range accessed_range,
		     tree type)
{
  bit_size_expr num_bits;
  if (accessed_range.get_size (op.m_model, &num_bits))
    {
      if (type)
	{
	  styled_string s;

	  pretty_printer pp;
	  num_bits.print (&pp);

	  if (op.m_dir == DIR_READ)
	    return fmt_styled_string (sm,
				      _("read of %qT (%s)"),
				      type,
				      pp_formatted_text (&pp));
	  else
	    return fmt_styled_string (sm,
				      _("write of %qT (%s)"),
				      type,
				      pp_formatted_text (&pp));
	}
      if (op.m_dir == DIR_READ)
	return num_bits.get_formatted_str (sm,
					   _("read of %wi bit"),
					   _("read of %wi bits"),
					   _("read of %wi byte"),
					   _("read of %wi bytes"),
					   _("read of %qE bits"),
					   _("read of %qE bytes"));
      else
	return num_bits.get_formatted_str (sm,
					   _("write of %wi bit"),
					   _("write of %wi bits"),
					   _("write of %wi byte"),
					   _("write of %wi bytes"),
					   _("write of %qE bits"),
					   _("write of %qE bytes"));
    }

  if (type)
    {
      if (op.m_dir == DIR_READ)
	return fmt_styled_string (sm, _("read of %qT"), type);
      else
	return fmt_styled_string (sm, _("write of %qT"), type);
    }

  if (op.m_dir == DIR_READ)
    return styled_string (sm, _("read"));
  else
    return styled_string (sm, _("write"));
}

/* Subroutine of clean_up_for_diagram.  */

static tree
strip_any_cast (tree expr)
{
  if (TREE_CODE (expr) == NOP_EXPR
      || TREE_CODE (expr) == NON_LVALUE_EXPR)
    expr = TREE_OPERAND (expr, 0);
  return expr;
}

/* Subroutine of clean_up_for_diagram.  */

static tree
remove_ssa_names (tree expr)
{
  if (TREE_CODE (expr) == SSA_NAME
      && SSA_NAME_VAR (expr))
    return SSA_NAME_VAR (expr);
  tree t = copy_node (expr);
  for (int i = 0; i < TREE_OPERAND_LENGTH (expr); i++)
    TREE_OPERAND (t, i) = remove_ssa_names (TREE_OPERAND (expr, i));
  return t;
}

/* We want to be able to print tree expressions from the analyzer,
   which is in the middle end.

   We could use the front-end pretty_printer's formatting routine,
   but:
   (a) some have additional state in a pretty_printer subclass, so we'd
   need to clone global_dc->printer
   (b) the "aka" type information added by the C and C++ frontends are
   too verbose when building a diagram, and there isn't a good way to ask
   for a less verbose version of them.

   Hence we use default_tree_printer.
   However, we want to avoid printing SSA names, and instead print the
   underlying var name.
   Ideally there would be a better tree printer for use by middle end
   warnings, but as workaround, this function clones a tree, replacing
   SSA names with the var names.  */

tree
clean_up_for_diagram (tree expr)
{
  tree without_ssa_names = remove_ssa_names (expr);
  return strip_any_cast (without_ssa_names);
}

/* struct bit_size_expr.  */

text_art::styled_string
bit_size_expr::get_formatted_str (text_art::style_manager &sm,
				  const char *concrete_single_bit_fmt,
				  const char *concrete_plural_bits_fmt,
				  const char *concrete_single_byte_fmt,
				  const char *concrete_plural_bytes_fmt,
				  const char *symbolic_bits_fmt,
				  const char *symbolic_bytes_fmt) const
{
  if (TREE_CODE (m_num_bits) == INTEGER_CST)
    {
      bit_size_t concrete_num_bits = wi::to_offset (m_num_bits);
      if (concrete_num_bits % BITS_PER_UNIT == 0)
	{
	  byte_size_t concrete_num_bytes = concrete_num_bits / BITS_PER_UNIT;
	  if (concrete_num_bytes == 1)
	    return fmt_styled_string (sm, concrete_single_byte_fmt,
				      concrete_num_bytes.to_uhwi ());
	  else
	    return fmt_styled_string (sm, concrete_plural_bytes_fmt,
				      concrete_num_bytes.to_uhwi ());
	}
      else
	{
	  if (concrete_num_bits == 1)
	    return fmt_styled_string (sm, concrete_single_bit_fmt,
				      concrete_num_bits.to_uhwi ());
	  else
	    return fmt_styled_string (sm, concrete_plural_bits_fmt,
				      concrete_num_bits.to_uhwi ());
	}
    }
  else
    {
      if (tree bytes_expr = maybe_get_as_bytes ())
	return fmt_styled_string (sm,
				  symbolic_bytes_fmt,
				  clean_up_for_diagram (bytes_expr));
      return fmt_styled_string (sm,
				symbolic_bits_fmt,
				clean_up_for_diagram (m_num_bits));
    }
}

void
bit_size_expr::print (pretty_printer *pp) const
{
  if (TREE_CODE (m_num_bits) == INTEGER_CST)
    {
      bit_size_t concrete_num_bits = wi::to_offset (m_num_bits);
      pp_bit_size_t (pp, concrete_num_bits);
    }
  else
    {
      if (tree bytes_expr = maybe_get_as_bytes ())
	pp_printf (pp, _("%qE bytes"), bytes_expr);
      else
	pp_printf (pp, _("%qE bits"), m_num_bits);
    }
}

tree
bit_size_expr::maybe_get_as_bytes () const
{
  switch (TREE_CODE (m_num_bits))
    {
    default:
      break;
    case INTEGER_CST:
      {
	const bit_size_t num_bits = wi::to_offset (m_num_bits);
	if (num_bits % BITS_PER_UNIT != 0)
	  return NULL_TREE;
	const bit_size_t num_bytes = num_bits / BITS_PER_UNIT;
	return wide_int_to_tree (size_type_node, num_bytes);
      }
      break;
    case PLUS_EXPR:
    case MINUS_EXPR:
      {
	bit_size_expr op0
	  = bit_size_expr (TREE_OPERAND (m_num_bits, 0));
	tree op0_as_bytes = op0.maybe_get_as_bytes ();
	if (!op0_as_bytes)
	  return NULL_TREE;
	bit_size_expr op1
	  = bit_size_expr (TREE_OPERAND (m_num_bits, 1));
	tree op1_as_bytes = op1.maybe_get_as_bytes ();
	if (!op1_as_bytes)
	  return NULL_TREE;
	return fold_build2 (TREE_CODE (m_num_bits), size_type_node,
			    op0_as_bytes, op1_as_bytes);
      }
      break;
    case MULT_EXPR:
      {
	bit_size_expr op1
	  = bit_size_expr (TREE_OPERAND (m_num_bits, 1));
	if (tree op1_as_bytes = op1.maybe_get_as_bytes ())
	  return fold_build2 (MULT_EXPR, size_type_node,
			      TREE_OPERAND (m_num_bits, 0),
			      op1_as_bytes);
      }
      break;
    }
  return NULL_TREE;
}

/* struct access_range.  */

access_range::access_range (const region *base_region, const bit_range &bits)
: m_start (region_offset::make_concrete (base_region,
					 bits.get_start_bit_offset ())),
  m_next (region_offset::make_concrete (base_region,
					bits.get_next_bit_offset ()))
{
}

access_range::access_range (const region *base_region, const byte_range &bytes)
: m_start (region_offset::make_concrete (base_region,
					 bytes.get_start_bit_offset ())),
  m_next (region_offset::make_concrete (base_region,
					bytes.get_next_bit_offset ()))
{
}

access_range::access_range (const region &reg, region_model_manager *mgr)
: m_start (reg.get_offset (mgr)),
  m_next (reg.get_next_offset (mgr))
{
}

bool
access_range::get_size (const region_model &model, bit_size_expr *out) const
{
  tree start_expr = m_start.calc_symbolic_bit_offset (model);
  if (!start_expr)
    return false;
  tree next_expr = m_next.calc_symbolic_bit_offset (model);
  if (!next_expr)
    return false;
  *out = bit_size_expr (fold_build2 (MINUS_EXPR, size_type_node,
					 next_expr, start_expr));
  return true;
}

bool
access_range::contains_p (const access_range &other) const
{
  return (m_start <= other.m_start
	  && other.m_next <= m_next);
}

bool
access_range::empty_p () const
{
  bit_range concrete_bits (0, 0);
  if (!as_concrete_bit_range (&concrete_bits))
    return false;
  return concrete_bits.empty_p ();
}

void
access_range::dump_to_pp (pretty_printer *pp, bool simple) const
{
  if (m_start.concrete_p () && m_next.concrete_p ())
    {
      bit_range bits (m_start.get_bit_offset (),
		      m_next.get_bit_offset () - m_start.get_bit_offset ());
      bits.dump_to_pp (pp);
      return;
    }
  pp_character (pp, '[');
  m_start.dump_to_pp (pp, simple);
  pp_string (pp, " to ");
  m_next.dump_to_pp (pp, simple);
  pp_character (pp, ')');
}

DEBUG_FUNCTION void
access_range::dump (bool simple) const
{
  pretty_printer pp;
  pp_format_decoder (&pp) = default_tree_printer;
  pp_show_color (&pp) = pp_show_color (global_dc->printer);
  pp.buffer->stream = stderr;
  dump_to_pp (&pp, simple);
  pp_newline (&pp);
  pp_flush (&pp);
}

void
access_range::log (const char *title, logger &logger) const
{
  logger.start_log_line ();
  logger.log_partial ("%s: ", title);
  dump_to_pp (logger.get_printer (), true);
  logger.end_log_line ();
}

/* struct access_operation.  */

access_range
access_operation::get_valid_bits () const
{
  const svalue *capacity_in_bytes_sval = m_model.get_capacity (m_base_region);
  return access_range
    (region_offset::make_concrete (m_base_region, 0),
     region_offset::make_byte_offset (m_base_region, capacity_in_bytes_sval));
}

access_range
access_operation::get_actual_bits () const
{
  return access_range (m_reg, get_manager ());
}

/* If there are any bits accessed invalidly before the valid range,
   return true and write their range to *OUT.
   Return false if there aren't, or if there's a problem
   (e.g. symbolic ranges.  */

bool
access_operation::maybe_get_invalid_before_bits (access_range *out) const
{
  access_range valid_bits (get_valid_bits ());
  access_range actual_bits (get_actual_bits ());

  if (actual_bits.m_start >= valid_bits.m_start)
    {
      /* No part of accessed range is before the valid range.  */
      return false;
    }
  else if (actual_bits.m_next > valid_bits.m_start)
    {
      /* Get part of accessed range that's before the valid range.  */
      *out = access_range (actual_bits.m_start, valid_bits.m_start);
      return true;
    }
  else
    {
      /* Accessed range is fully before valid range.  */
      *out = actual_bits;
      return true;
    }
}

/* If there are any bits accessed invalidly after the valid range,
   return true and write their range to *OUT.
   Return false if there aren't, or if there's a problem.  */

bool
access_operation::maybe_get_invalid_after_bits (access_range *out) const
{
  access_range valid_bits (get_valid_bits ());
  access_range actual_bits (get_actual_bits ());

  if (actual_bits.m_next <= valid_bits.m_next)
    {
      /* No part of accessed range is after the valid range.  */
      return false;
    }
  else if (actual_bits.m_start < valid_bits.m_next)
    {
      /* Get part of accessed range that's after the valid range.  */
      *out = access_range (valid_bits.m_next, actual_bits.m_next);
      return true;
    }
  else
    {
      /* Accessed range is fully after valid range.  */
      *out = actual_bits;
      return true;
    }
}

/* A class for capturing all of the region offsets of interest (both concrete
   and symbolic), to help align everything in the diagram.
   Boundaries can be soft or hard; hard boundaries are emphasized visually
   (e.g. the boundary between valid vs invalid accesses).

   Offsets in the boundaries are all expressed relative to the base
   region of the access_operation.  */

class boundaries
{
public:
  enum class kind { HARD, SOFT};

  boundaries (const region &base_reg)
  : m_base_reg (base_reg)
  {
  }

  void add (region_offset offset, enum kind k)
  {
    m_all_offsets.insert (offset);
    if (k == kind::HARD)
      m_hard_offsets.insert (offset);
  }

  void add (const access_range &range, enum kind kind)
  {
    add (range.m_start, kind);
    add (range.m_next, kind);
  }

  void add (const region &reg, region_model_manager *mgr, enum kind kind)
  {
    add (access_range (reg.get_offset (mgr),
		       reg.get_next_offset (mgr)),
	 kind);
  }

  void add (const byte_range bytes, enum kind kind)
  {
    add (access_range (&m_base_reg, bytes), kind);
  }

  void add_all_bytes_in_range (const byte_range &bytes)
  {
    for (byte_offset_t byte_idx = bytes.get_start_byte_offset ();
	 byte_idx <= bytes.get_next_byte_offset ();
	 byte_idx = byte_idx + 1)
      add (region_offset::make_concrete (&m_base_reg, byte_idx * 8),
	   kind::SOFT);
  }

  void add_all_bytes_in_range (const access_range &range)
  {
    byte_range bytes (0, 0);
    bool valid = range.as_concrete_byte_range (&bytes);
    gcc_assert (valid);
    add_all_bytes_in_range (bytes);
  }

  void log (logger &logger) const
  {
    logger.log ("boundaries:");
    logger.inc_indent ();
    for (auto offset : m_all_offsets)
      {
	enum kind k = get_kind (offset);
	logger.start_log_line ();
	logger.log_partial ("%s: ", (k == kind::HARD) ? "HARD" : "soft");
	offset.dump_to_pp (logger.get_printer (), true);
	logger.end_log_line ();
      }
    logger.dec_indent ();
  }

  enum kind get_kind (region_offset offset) const
  {
    gcc_assert (m_all_offsets.find (offset) != m_all_offsets.end ());
    if (m_hard_offsets.find (offset) != m_hard_offsets.end ())
      return kind::HARD;
    else
      return kind::SOFT;
  }

  std::set<region_offset>::const_iterator begin () const
  {
    return m_all_offsets.begin ();
  }
  std::set<region_offset>::const_iterator end () const
  {
    return m_all_offsets.end ();
  }
  std::set<region_offset>::size_type size () const
  {
    return m_all_offsets.size ();
  }

private:
  const region &m_base_reg;
  std::set<region_offset> m_all_offsets;
  std::set<region_offset> m_hard_offsets;
};

/* A widget that wraps a table but offloads column-width calculation
   to a shared object, so that we can vertically line up multiple tables
   and have them all align their columns.

   For example, in:

   01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   02| |[0]|[1]|[2]|[3]|[4]|[5]|   ...    |[440]|[441]|[442]|[443]|[444]|[445]|
   03| +---+---+---+---+---+---+          +-----+-----+-----+-----+-----+-----+
   04| |'L'|'o'|'r'|'e'|'m'|' '|          | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
   05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   06| |                  string literal (type: 'char[446]')                  |
   07| +----------------------------------------------------------------------+
   08|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   09|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   10|   v   v   v   v   v   v  v  v    v    v     v     v     v     v     v
   11|+---+---------------------+----++--------------------------------------+
   12||[0]|         ...         |[99]||          after valid range           |
   13|+---+---------------------+----+|                                      |
   14||  'buf' (type: 'char[100]')   ||                                      |
   15|+------------------------------++--------------------------------------+
   16||~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
   17|               |                                   |
   18|     +---------+---------+              +----------+----------+
   19|     |capacity: 100 bytes|              |overflow of 346 bytes|
   20|     +-------------------+              +---------------------+

   rows 01-07 and rows 11-15 are x_aligned_table_widget instances.  */

class x_aligned_table_widget : public leaf_widget
{
public:
  x_aligned_table_widget (table t,
			  const theme &theme,
			  table_dimension_sizes &col_widths)
  : m_table (std::move (t)),
    m_theme (theme),
    m_col_widths (col_widths),
    m_row_heights (t.get_size ().h),
    m_cell_sizes (m_col_widths, m_row_heights),
    m_tg (m_table, m_cell_sizes)
  {
  }

  const char *get_desc () const override
  {
    return "x_aligned_table_widget";
  }

  canvas::size_t calc_req_size () final override
  {
    /* We don't compute the size requirements;
       the parent should have done this.  */
    return m_tg.get_canvas_size ();
  }

  void paint_to_canvas (canvas &canvas) final override
  {
    m_table.paint_to_canvas (canvas,
			     get_top_left (),
			     m_tg,
			     m_theme);
  }

  const table &get_table () const { return m_table; }
  table_cell_sizes &get_cell_sizes () { return m_cell_sizes; }
  void recalc_coords ()
  {
    m_tg.recalc_coords ();
  }

private:
  table m_table;
  const theme &m_theme;
  table_dimension_sizes &m_col_widths; // Reference to shared column widths
  table_dimension_sizes m_row_heights; // Unique row heights
  table_cell_sizes m_cell_sizes;
  table_geometry m_tg;
};

/* A widget for printing arrows between the accessed region
   and the svalue, showing the direction of the access.

   For example, in:

   01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   02| |[0]|[1]|[2]|[3]|[4]|[5]|   ...    |[440]|[441]|[442]|[443]|[444]|[445]|
   03| +---+---+---+---+---+---+          +-----+-----+-----+-----+-----+-----+
   04| |'L'|'o'|'r'|'e'|'m'|' '|          | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
   05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   06| |                  string literal (type: 'char[446]')                  |
   07| +----------------------------------------------------------------------+
   08|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   09|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   10|   v   v   v   v   v   v  v  v    v    v     v     v     v     v     v
   11|+---+---------------------+----++--------------------------------------+
   12||[0]|         ...         |[99]||          after valid range           |
   13|+---+---------------------+----+|                                      |
   14||  'buf' (type: 'char[100]')   ||                                      |
   15|+------------------------------++--------------------------------------+
   16||~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
   17|               |                                   |
   18|     +---------+---------+              +----------+----------+
   19|     |capacity: 100 bytes|              |overflow of 346 bytes|
   20|     +-------------------+              +---------------------+

   rows 8-10 are the direction widget.  */

class direction_widget : public leaf_widget
{
public:
  direction_widget (const access_diagram_impl &dia_impl,
		    const bit_to_table_map &btm)
  : leaf_widget (),
    m_dia_impl (dia_impl),
    m_btm (btm)
  {
  }
  const char *get_desc () const override
  {
    return "direction_widget";
  }
  canvas::size_t calc_req_size () final override
  {
    /* Get our width from our siblings.  */
    return canvas::size_t (0, 3);
  }
  void paint_to_canvas (canvas &canvas) final override;

private:
  const access_diagram_impl &m_dia_impl;
  const bit_to_table_map &m_btm;
};

/* A widget for adding an x_ruler to a diagram based on table columns,
   offloading column-width calculation to shared objects, so that the ruler
   lines up with other tables in the diagram.

   For example, in:

   01| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   02| |[0]|[1]|[2]|[3]|[4]|[5]|   ...    |[440]|[441]|[442]|[443]|[444]|[445]|
   03| +---+---+---+---+---+---+          +-----+-----+-----+-----+-----+-----+
   04| |'L'|'o'|'r'|'e'|'m'|' '|          | 'o' | 'r' | 'u' | 'm' | '.' | NUL |
   05| +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
   06| |                  string literal (type: 'char[446]')                  |
   07| +----------------------------------------------------------------------+
   08|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   09|   |   |   |   |   |   |  |  |    |    |     |     |     |     |     |
   10|   v   v   v   v   v   v  v  v    v    v     v     v     v     v     v
   11|+---+---------------------+----++--------------------------------------+
   12||[0]|         ...         |[99]||          after valid range           |
   13|+---+---------------------+----+|                                      |
   14||  'buf' (type: 'char[100]')   ||                                      |
   15|+------------------------------++--------------------------------------+
   16||~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~||~~~~~~~~~~~~~~~~~~+~~~~~~~~~~~~~~~~~~~|
   17|               |                                   |
   18|     +---------+---------+              +----------+----------+
   19|     |capacity: 100 bytes|              |overflow of 346 bytes|
   20|     +-------------------+              +---------------------+

   rows 16-20 are the x_aligned_x_ruler_widget.  */

class x_aligned_x_ruler_widget : public leaf_widget
{
public:
  x_aligned_x_ruler_widget (const access_diagram_impl &dia_impl,
			    const theme &theme,
			    table_dimension_sizes &col_widths)
  : m_dia_impl (dia_impl),
    m_theme (theme),
    m_col_widths (col_widths)
  {
  }

  const char *get_desc () const override
  {
    return "x_aligned_ruler_widget";
  }

  void add_range (const table::range_t &x_range,
		  styled_string text,
		  style::id_t style_id)
  {
    m_labels.push_back (label (x_range, std::move (text), style_id));
  }

  canvas::size_t calc_req_size () final override
  {
    x_ruler r (make_x_ruler ());
    return r.get_size ();
  }

  void paint_to_canvas (canvas &canvas) final override
  {
    x_ruler r (make_x_ruler ());
    r.paint_to_canvas (canvas,
		       get_top_left (),
		       m_theme);
  }

private:
  struct label
  {
    label (const table::range_t &table_x_range,
	   styled_string text,
	   style::id_t style_id)
    : m_table_x_range (table_x_range),
      m_text (std::move (text)),
      m_style_id (style_id)
    {
    }
    table::range_t m_table_x_range;
    styled_string m_text;
    style::id_t m_style_id;
  };

  x_ruler make_x_ruler () const;

  const access_diagram_impl &m_dia_impl;
  const theme &m_theme;
  table_dimension_sizes &m_col_widths;
  std::vector<label> m_labels;
};

/* A two-way mapping between access_ranges and table columns, for use by
   spatial_item subclasses for creating tables.
   For example when visualizing a bogus access of 'int arr[10];'
   at 'arr[10]', we might have:
   - table column 0 is "bytes 0-3" (for arr[0])
   - table column 1 is "bytes 4-35" (for arr[1] through arr[8])
   - table column 2 is "bytes 36-39 (for arr[9])
   - table column 3 is blank to emphasize a hard boundary between
     valid/invalid accesses.
   - table column 4 is "bytes 40-44" (for arr[10])

   We store this as a pair of maps from region_offset to table x; in
   the abvove example:

     region offset          table_x  prev_table_x
     bit 0 (aka byte 0)     0        (none)
     bit 32 (aka byte 4)    1        0
     bit 288 (aka byte 36)  2        1
     bit 320 (aka byte 40)  4        2
     bit 352 (aka byte 44)  (none)   (none)

     so that e.g given the half-open byte range [0, 40)
     we can determine the closed range of table x [0, 2].  */

class bit_to_table_map
{
public:
  /* Populate m_table_x_for_bit and m_bit_for_table_x.  */
  void populate (const boundaries &boundaries, logger *logger)
  {
    LOG_SCOPE (logger);

    int table_x = 0;
    std::vector <region_offset> vec_boundaries (boundaries.begin (),
						boundaries.end ());

    /* Sort into an order that makes sense.  */
    std::sort (vec_boundaries.begin (),
	       vec_boundaries.end ());

    if (logger)
      {
	logger->log ("vec_boundaries");
	logger->inc_indent ();
	for (unsigned idx = 0; idx < vec_boundaries.size (); idx++)
	  {
	    logger->start_log_line ();
	    logger->log_partial ("idx: %i: ", idx);
	    vec_boundaries[idx].dump_to_pp (logger->get_printer (), true);
	    logger->end_log_line ();
	  }
	logger->dec_indent ();
      }

    for (size_t idx = 0; idx < vec_boundaries.size (); idx++)
      {
	const region_offset &offset = vec_boundaries[idx];
	if (idx > 0 && (idx + 1) < vec_boundaries.size ())
	  {
	    if (boundaries.get_kind (offset) == boundaries::kind::HARD)
	      table_x += 1;
	  }
	m_table_x_for_offset[offset] = table_x;
	if ((idx + 1) < vec_boundaries.size ())
	  {
	    const region_offset &next_offset = vec_boundaries[idx + 1];
	    m_table_x_for_prev_offset[next_offset] = table_x;
	    m_range_for_table_x[table_x] = access_range (offset, next_offset);
	  }
	table_x += 1;
      }
    m_num_columns = table_x - 1;

    if (logger)
      log (*logger);
  }

  unsigned get_num_columns () const
  {
    return m_num_columns;
  }

  table::range_t get_table_x_for_range (const access_range &range) const
  {
    return table::range_t (get_table_x_for_offset (range.m_start),
			   get_table_x_for_prev_offset (range.m_next) + 1);
  }

  table::rect_t get_table_rect (const access_range &range,
				const int table_y, const int table_h) const
  {
    const table::range_t x_range (get_table_x_for_range (range));
    return table::rect_t (table::coord_t (x_range.start, table_y),
			  table::size_t (x_range.get_size (), table_h));
  }

  table::rect_t get_table_rect (const region *base_reg,
				const bit_range &bits,
				const int table_y, const int table_h) const
  {
    const access_range range (base_reg, bits);
    return get_table_rect (range, table_y, table_h);
  }

  table::rect_t get_table_rect (const region *base_reg,
				const byte_range &bytes,
				const int table_y, const int table_h) const
  {
    return get_table_rect (base_reg, bytes.as_bit_range (), table_y, table_h);
  }

  bool maybe_get_access_range_for_table_x (int table_x,
					   access_range *out) const
  {
    auto slot = m_range_for_table_x.find (table_x);
    if (slot == m_range_for_table_x.end ())
      return false;
    *out = slot->second;
    return true;
  }

  void log (logger &logger) const
  {
    logger.log ("table columns");
    logger.inc_indent ();
    for (unsigned table_x = 0; table_x < get_num_columns (); table_x++)
      {
	logger.start_log_line ();
	logger.log_partial ("table_x: %i", table_x);
	access_range range_for_column (NULL, bit_range (0, 0));
	if (maybe_get_access_range_for_table_x (table_x, &range_for_column))
	  {
	    logger.log_partial (": range: ");
	    range_for_column.dump_to_pp (logger.get_printer (), true);
	  }
	logger.end_log_line ();
      }
    logger.dec_indent ();
  }

private:
  int get_table_x_for_offset (region_offset offset) const
  {
    auto slot = m_table_x_for_offset.find (offset);

    /* If this fails, then we probably failed to fully populate m_boundaries
       in find_boundaries.  */
    gcc_assert (slot != m_table_x_for_offset.end ());

    return slot->second;
  }

  int get_table_x_for_prev_offset (region_offset offset) const
  {
    auto slot = m_table_x_for_prev_offset.find (offset);

    /* If this fails, then we probably failed to fully populate m_boundaries
       in find_boundaries.  */
    gcc_assert (slot != m_table_x_for_prev_offset.end ());

    return slot->second;
  }

  std::map<region_offset, int> m_table_x_for_offset;
  std::map<region_offset, int> m_table_x_for_prev_offset;
  std::map<int, access_range> m_range_for_table_x;
  unsigned m_num_columns;
};

/* Base class for something in the diagram that participates
   in two steps of diagram creation:
   (a) populating a boundaries instance with the boundaries of interest
   (b) creating a table instance for itself.

   Offsets in the boundaries are all expressed relative to the base
   region of the access_operation.  */

class spatial_item
{
public:
  virtual ~spatial_item () {}
  virtual void add_boundaries (boundaries &out, logger *) const = 0;

  virtual table make_table (const bit_to_table_map &btm,
			    style_manager &sm) const = 0;
};

/* Subclass of spatial_item for visualizing the region of memory
   that's valid to access relative to the base region of region accessed in
   the operation.  */

class valid_region_spatial_item : public spatial_item
{
public:
  valid_region_spatial_item (const access_operation &op,
			     diagnostic_event_id_t region_creation_event_id)
  : m_op (op),
    m_region_creation_event_id (region_creation_event_id)
  {}

  void add_boundaries (boundaries &out, logger *logger) const final override
  {
    LOG_SCOPE (logger);
    access_range valid_bits = m_op.get_valid_bits ();
    if (logger)
      {
	logger->start_log_line ();
	logger->log_partial ("valid bits: ");
	valid_bits.dump_to_pp (logger->get_printer (), true);
	logger->end_log_line ();
      }
    out.add (valid_bits, boundaries::kind::HARD);

    /* Support for showing first and final element in array types.  */
    if (tree base_type = m_op.m_base_region->get_type ())
      if (TREE_CODE (base_type) == ARRAY_TYPE)
	{
	  if (logger)
	    logger->log ("showing first and final element in array type");
	  region_model_manager *mgr = m_op.m_model.get_manager ();
	  tree domain = TYPE_DOMAIN (base_type);
	  if (TYPE_MIN_VALUE (domain) && TYPE_MAX_VALUE (domain))
	    {
	      const svalue *min_idx_sval
		= mgr->get_or_create_constant_svalue (TYPE_MIN_VALUE (domain));
	      const svalue *max_idx_sval
		= mgr->get_or_create_constant_svalue (TYPE_MAX_VALUE (domain));
	      const region *min_element =
		mgr->get_element_region (m_op.m_base_region,
					 TREE_TYPE (base_type),
					 min_idx_sval);
	      out.add (*min_element, mgr, boundaries::kind::SOFT);
	      const region *max_element =
		mgr->get_element_region (m_op.m_base_region,
					 TREE_TYPE (base_type),
					 max_idx_sval);
	      out.add (*max_element, mgr, boundaries::kind::SOFT);
	    }
	}
  }

  /* Subroutine of make_table when base region has ARRAY_TYPE.  */
  void add_array_elements_to_table (table &t,
				    const bit_to_table_map &btm,
				    style_manager &sm) const
  {
    tree base_type = m_op.m_base_region->get_type ();
    gcc_assert (TREE_CODE (base_type) == ARRAY_TYPE);

    tree domain = TYPE_DOMAIN (base_type);
    if (!(TYPE_MIN_VALUE (domain) && TYPE_MAX_VALUE (domain)))
      return;

    region_model_manager * const mgr = m_op.get_manager ();
    const int table_y = 0;
    const int table_h = 1;
    const table::range_t table_y_range (table_y, table_y + table_h);

    t.add_row ();
    const svalue *min_idx_sval
      = mgr->get_or_create_constant_svalue (TYPE_MIN_VALUE (domain));
    const region *min_element = mgr->get_element_region (m_op.m_base_region,
							 TREE_TYPE (base_type),
							 min_idx_sval);
    const access_range min_element_range (*min_element, mgr);
    const table::range_t min_element_x_range
      = btm.get_table_x_for_range (min_element_range);

    t.set_cell_span (table::rect_t (min_element_x_range,
				    table_y_range),
		     fmt_styled_string (sm, "[%E]",
					TYPE_MIN_VALUE (domain)));

    const svalue *max_idx_sval
      = mgr->get_or_create_constant_svalue (TYPE_MAX_VALUE (domain));
    const region *max_element = mgr->get_element_region (m_op.m_base_region,
							 TREE_TYPE (base_type),
							 max_idx_sval);
    if (min_element == max_element)
      return; // 1-element array

    const access_range max_element_range (*max_element, mgr);
    const table::range_t max_element_x_range
      = btm.get_table_x_for_range (max_element_range);
    t.set_cell_span (table::rect_t (max_element_x_range,
				    table_y_range),
		     fmt_styled_string (sm, "[%E]",
					TYPE_MAX_VALUE (domain)));

    const table::range_t other_elements_x_range (min_element_x_range.next,
						 max_element_x_range.start);
    if (other_elements_x_range.get_size () > 0)
      t.set_cell_span (table::rect_t (other_elements_x_range, table_y_range),
		       styled_string (sm, "..."));
  }

  table make_table (const bit_to_table_map &btm,
		    style_manager &sm) const final override
  {
    table t (table::size_t (btm.get_num_columns (), 1));

    if (tree base_type = m_op.m_base_region->get_type ())
      if (TREE_CODE (base_type) == ARRAY_TYPE)
	add_array_elements_to_table (t, btm, sm);

    access_range valid_bits = m_op.get_valid_bits ();
    const int table_y = t.get_size ().h - 1;
    const int table_h = 1;
    table::rect_t rect = btm.get_table_rect (valid_bits, table_y, table_h);
    styled_string s;
    switch (m_op.m_base_region->get_kind ())
      {
      default:
	s = styled_string (sm, _("region"));
	break;
      case RK_DECL:
	{
	  const decl_region *decl_reg
	    = as_a <const decl_region *> (m_op.m_base_region);
	  tree decl = decl_reg->get_decl ();
	  s = fmt_styled_string (sm, "%qE (type: %qT)",
				 decl,
				 TREE_TYPE (decl));
	}
	break;
      case RK_HEAP_ALLOCATED:
	{
	  if (m_region_creation_event_id.known_p ())
	    s = fmt_styled_string (sm, _("buffer allocated on heap at %@"),
				   &m_region_creation_event_id);
	  else
	    s = styled_string (sm, _("heap-allocated buffer"));
	}
	break;
      case RK_ALLOCA:
	{
	  if (m_region_creation_event_id.known_p ())
	    s = fmt_styled_string (sm, _("buffer allocated on stack at %@"),
				   &m_region_creation_event_id);
	  else
	    s = styled_string (sm, _("stack-allocated buffer"));
	}
	break;
      case RK_STRING:
	{
	  const string_region *string_reg
	    = as_a <const string_region *> (m_op.m_base_region);
	  tree string_cst = string_reg->get_string_cst ();
	  s = fmt_styled_string (sm, _("string literal (type: %qT)"),
				 TREE_TYPE (string_cst));
	}
	break;
      }
    t.set_cell_span (rect, std::move (s));

    return t;
  }

private:
  const access_operation &m_op;
  diagnostic_event_id_t m_region_creation_event_id;
};

/* Subclass of spatial_item for visualizing the region of memory
   that's actually accessed by the read or write, for reads and
   for write cases where we don't know the svalue written.  */

class accessed_region_spatial_item : public spatial_item
{
public:
  accessed_region_spatial_item (const access_operation &op) : m_op (op) {}

  void add_boundaries (boundaries &out, logger *logger) const final override
  {
    LOG_SCOPE (logger);
    access_range actual_bits = m_op.get_actual_bits ();
    if (logger)
      {
	logger->start_log_line ();
	logger->log_partial ("actual bits: ");
	actual_bits.dump_to_pp (logger->get_printer (), true);
	logger->end_log_line ();
      }
    out.add (actual_bits, boundaries::kind::HARD);
  }

  table make_table (const bit_to_table_map &btm,
		    style_manager &sm) const final override
  {
    table t (table::size_t (btm.get_num_columns (), 1));

    access_range actual_bits = m_op.get_actual_bits ();
    const int table_y = 0;
    const int table_h = 1;
    table::rect_t rect = btm.get_table_rect (actual_bits, table_y, table_h);
    t.set_cell_span (rect, styled_string (get_label_string (sm)));

    return t;
  }

private:
  styled_string get_label_string (style_manager &sm) const
  {
    const access_range accessed_bits (m_op.get_actual_bits ());
    return get_access_size_str (sm,
				m_op,
				accessed_bits,
				m_op.m_reg.get_type ());
  }

  const access_operation &m_op;
};

/* Subclass of spatial_item for when we know the svalue being written
   to the accessed region.
   Can be subclassed to give visualizations of specific kinds of svalue.  */

class svalue_spatial_item : public spatial_item
{
public:
  static std::unique_ptr<svalue_spatial_item> make (const access_operation &op,
						    const svalue &sval,
						    access_range actual_bits,
						    const theme &theme);

  svalue_spatial_item (const access_operation &op,
		       const svalue &sval,
		       access_range actual_bits)
  : m_op (op), m_sval (sval), m_actual_bits (actual_bits)
  {}

  void add_boundaries (boundaries &out, logger *logger) const override
  {
    LOG_SCOPE (logger);
    out.add (m_actual_bits, boundaries::kind::HARD);
  }

  table make_table (const bit_to_table_map &btm,
		    style_manager &sm) const override
  {
    table t (table::size_t (btm.get_num_columns (), 0));

    const int table_y = t.add_row ();
    const int table_h = 1;
    table::rect_t rect = btm.get_table_rect (m_actual_bits, table_y, table_h);
    t.set_cell_span (rect, styled_string (get_label_string (sm)));
    return t;
  }

protected:
  styled_string get_label_string (style_manager &sm) const
  {
    tree rep_tree = m_op.m_model.get_representative_tree (&m_sval);
    if (rep_tree)
      {
	if (TREE_CODE (rep_tree) == SSA_NAME)
	  rep_tree = SSA_NAME_VAR (rep_tree);
	switch (TREE_CODE (rep_tree))
	  {
	  default:
	    break;
	  case INTEGER_CST:
	    return fmt_styled_string (sm, _("write of %<(%T) %E%>"),
				      TREE_TYPE (rep_tree),
				      rep_tree);

	  case PARM_DECL:
	  case VAR_DECL:
	    return fmt_styled_string (sm, _("write from %qE (type: %qT)"),
				      rep_tree,
				      TREE_TYPE (rep_tree));
	    break;
	  }
	}

    const access_range accessed_bits (m_op.get_actual_bits ());
    return get_access_size_str (sm,
				m_op,
				accessed_bits,
				m_sval.get_type ());
  }

  const access_operation &m_op;
  const svalue &m_sval;
  access_range m_actual_bits;
};

/* Subclass of svalue_spatial_item for initial_svalue of a string_region
   i.e. for string literals.

   There are three cases:
   (a) for long strings, show just the head and tail of the string,
   with an ellipsis:
     +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
     |[0]|[1]|[2]|[3]|[4]|[5]|          |[440]|[441]|[442]|[443]|[444]|[445]|
     +---+---+---+---+---+---+   ...    +-----+-----+-----+-----+-----+-----+
     |‘L’|‘o’|‘r’|‘e’|‘m’|‘ ’|          | ‘o’ | ‘r’ | ‘u’ | ‘m’ | ‘.’ | NUL |
     +---+---+---+---+---+---+----------+-----+-----+-----+-----+-----+-----+
     |                  string literal (type: ‘char[446]’)                  |
     +----------------------------------------------------------------------+
   (b) For sufficiently short strings, show the full string:
     +----------+---------+---------+---------+---------+ +-----------------+
     |   [0]    |   [1]   |   [2]   |   [3]   |   [4]   | |       [5]       |
     +----------+---------+---------+---------+---------+ +-----------------+
     |   ‘h’    |   ‘e’   |   ‘l’   |   ‘l’   |   ‘o’   | |       NUL       |
     +----------+---------+---------+---------+---------+-+-----------------+
     |                   string literal (type: ‘char[6]’)                   |
     +----------------------------------------------------------------------+
   (c) for non-ASCII strings that are short enough to show the full string,
   show how unicode code points of the bytes decoded as UTF-8:
     +-----+-----+-----+----+----++----+----+----+----+----+----+----+------+
     | [0] | [1] | [2] |[3] |[4] ||[5] |[6] |[7] |[8] |[9] |[10]|[11]| [12] |
     +-----+-----+-----+----+----++----+----+----+----+----+----+----+------+
     |0xe6 |0x96 |0x87 |0xe5|0xad||0x97|0xe5|0x8c|0x96|0xe3|0x81|0x91| 0x00 |
     +-----+-----+-----+----+----++----+----+----+----+----+----+----+------+
     |     U+6587      |    U+5b57     |    U+5316    |    U+3051    |U+0000|
     +-----------------+---------------+--------------+--------------+------+
     |                  string literal (type: ‘char[13]’)                   |
     +----------------------------------------------------------------------+
   and show the characters themselves if unicode is supported and they are not
   control characters:
     ┌─────┬─────┬─────┬────┬────┐┌────┬────┬────┬────┬────┬────┬────┬──────┐
     │ [0] │ [1] │ [2] │[3] │[4] ││[5] │[6] │[7] │[8] │[9] │[10]│[11]│ [12] │
     ├─────┼─────┼─────┼────┼────┤├────┼────┼────┼────┼────┼────┼────┼──────┤
     │0xe6 │0x96 │0x87 │0xe5│0xad││0x97│0xe5│0x8c│0x96│0xe3│0x81│0x91│ 0x00 │
     ├─────┴─────┴─────┼────┴────┴┴────┼────┴────┴────┼────┴────┴────┼──────┤
     │     U+6587      │    U+5b57     │    U+5316    │    U+3051    │U+0000│
     ├─────────────────┼───────────────┼──────────────┼──────────────┼──────┤
     │       文        │      字       │      化      │      け      │ NUL  │
     ├─────────────────┴───────────────┴──────────────┴──────────────┴──────┤
     │                  string literal (type: ‘char[13]’)                   │
     └──────────────────────────────────────────────────────────────────────┘
*/

class string_region_spatial_item : public svalue_spatial_item
{
public:
  string_region_spatial_item (const access_operation &op,
			      const svalue &sval,
			      access_range actual_bits,
			      const string_region &string_reg,
			      const theme &theme)
  : svalue_spatial_item (op, sval, actual_bits),
    m_string_reg (string_reg),
    m_theme (theme),
    m_ellipsis_threshold (param_analyzer_text_art_string_ellipsis_threshold),
    m_ellipsis_head_len (param_analyzer_text_art_string_ellipsis_head_len),
    m_ellipsis_tail_len (param_analyzer_text_art_string_ellipsis_tail_len),
    m_show_full_string (calc_show_full_string ()),
    m_show_utf8 (m_show_full_string && !pure_ascii_p ())
  {
  }

  void add_boundaries (boundaries &out, logger *logger) const override
  {
    LOG_SCOPE (logger);
    out.add (m_actual_bits, boundaries::kind::HARD);

    tree string_cst = get_string_cst ();
    /* TREE_STRING_LENGTH is sizeof, not strlen.  */
    if (m_show_full_string)
      out.add_all_bytes_in_range (m_actual_bits);
    else
      {
	byte_range bytes (0, 0);
	bool valid = m_actual_bits.as_concrete_byte_range (&bytes);
	gcc_assert (valid);
	byte_range head_of_string (bytes.get_start_byte_offset (),
				   m_ellipsis_head_len);
	out.add_all_bytes_in_range (head_of_string);
	byte_range tail_of_string
	  ((bytes.get_start_byte_offset ()
	    + TREE_STRING_LENGTH (string_cst)
	    - m_ellipsis_tail_len),
	   m_ellipsis_tail_len);
	out.add_all_bytes_in_range (tail_of_string);
	/* Adding the above pair of ranges will also effectively add
	   the boundaries of the range of ellipsized chars, as they're
	   exactly in between head_of_string and tail_of_string.  */
      }
  }

  table make_table (const bit_to_table_map &btm,
		    style_manager &sm) const override
  {
    table t (table::size_t (btm.get_num_columns (), 0));

    const int byte_idx_table_y = t.add_row ();
    const int byte_val_table_y = t.add_row ();

    byte_range bytes (0, 0);
    bool valid = m_actual_bits.as_concrete_byte_range (&bytes);
    gcc_assert (valid);
    tree string_cst = get_string_cst ();
    if (m_show_full_string)
      {
       for (byte_offset_t byte_idx_within_cluster
	      = bytes.get_start_byte_offset ();
	    byte_idx_within_cluster < bytes.get_next_byte_offset ();
	    byte_idx_within_cluster = byte_idx_within_cluster + 1)
	 add_column_for_byte
	   (t, btm, sm, byte_idx_within_cluster,
	    byte_idx_within_cluster - bytes.get_start_byte_offset (),
	    byte_idx_table_y, byte_val_table_y);

       if (m_show_utf8)
	 {
	   const bool show_unichars = m_theme.unicode_p ();
	   const int utf8_code_point_table_y = t.add_row ();
	   int utf8_character_table_y;
	   if (show_unichars)
	     utf8_character_table_y = t.add_row ();

	   /* We don't actually want the display widths here, but
	      it's an easy way to decode UTF-8.  */
	   cpp_char_column_policy policy (8, cpp_wcwidth);
	   cpp_display_width_computation dw (TREE_STRING_POINTER (string_cst),
					     TREE_STRING_LENGTH (string_cst),
					     policy);
	   while (!dw.done ())
	     {
	       cpp_decoded_char decoded_char;
	       dw.process_next_codepoint (&decoded_char);

	       if (!decoded_char.m_valid_ch)
		 continue;
	       size_t start_byte_idx
		 = decoded_char.m_start_byte - TREE_STRING_POINTER (string_cst);
	       byte_size_t size_in_bytes
		 = decoded_char.m_next_byte - decoded_char.m_start_byte;
	       byte_range cluster_bytes_for_codepoint
		 (start_byte_idx + bytes.get_start_byte_offset (),
		  size_in_bytes);

	       const table::rect_t code_point_table_rect
		 = btm.get_table_rect (&m_string_reg,
				       cluster_bytes_for_codepoint,
				       utf8_code_point_table_y, 1);
	       char buf[100];
	       sprintf (buf, "U+%04x", decoded_char.m_ch);
	       t.set_cell_span (code_point_table_rect,
				styled_string (sm, buf));

	       if (show_unichars)
		 {
		   const table::rect_t character_table_rect
		     = btm.get_table_rect (&m_string_reg,
					   cluster_bytes_for_codepoint,
					   utf8_character_table_y, 1);
		   if (cpp_is_printable_char (decoded_char.m_ch))
		     t.set_cell_span (character_table_rect,
				      styled_string (decoded_char.m_ch));
		   else if (decoded_char.m_ch == 0)
		     t.set_cell_span (character_table_rect,
				      styled_string (sm, "NUL"));
		   else
		     t.set_cell_span (character_table_rect,
				      styled_string (sm, ""));
		 }
	     }
	 }
      }
    else
      {
	/* Head of string.  */
	for (int byte_idx = 0; byte_idx < m_ellipsis_head_len; byte_idx++)
	  add_column_for_byte (t, btm, sm,
			       byte_idx + bytes.get_start_byte_offset (),
			       byte_idx,
			       byte_idx_table_y, byte_val_table_y);

	/* Ellipsis (two rows high).  */
	const byte_range ellipsis_bytes
	  (m_ellipsis_head_len + bytes.get_start_byte_offset (),
	   TREE_STRING_LENGTH (string_cst)
	   - (m_ellipsis_head_len + m_ellipsis_tail_len));
	const table::rect_t table_rect
	  = btm.get_table_rect (&m_string_reg, ellipsis_bytes,
				byte_idx_table_y, 2);
	t.set_cell_span(table_rect, styled_string (sm, "..."));

	/* Tail of string.  */
	for (int byte_idx
	       = (TREE_STRING_LENGTH (string_cst) - m_ellipsis_tail_len);
	     byte_idx < TREE_STRING_LENGTH (string_cst);
	     byte_idx++)
	  add_column_for_byte (t, btm, sm,
			       byte_idx + bytes.get_start_byte_offset (),
			       byte_idx,
			       byte_idx_table_y, byte_val_table_y);
      }

    const int summary_table_y = t.add_row ();
    t.set_cell_span (btm.get_table_rect (&m_string_reg, bytes,
					 summary_table_y, 1),
		     fmt_styled_string (sm,
					_("string literal (type: %qT)"),
					TREE_TYPE (string_cst)));

    return t;
  }

  tree get_string_cst () const { return m_string_reg.get_string_cst (); }

private:
  bool calc_show_full_string () const
  {
    tree string_cst = get_string_cst ();
    if (TREE_STRING_LENGTH (string_cst) < m_ellipsis_threshold)
      return true;
    if (TREE_STRING_LENGTH (string_cst) <
	(m_ellipsis_head_len + m_ellipsis_tail_len))
      return true;
    return false;
  }

  bool pure_ascii_p () const
  {
    tree string_cst = get_string_cst ();
    for (unsigned byte_idx = 0;
	 byte_idx < (unsigned) TREE_STRING_LENGTH (string_cst);
	 byte_idx++)
      {
	unsigned char ch = TREE_STRING_POINTER (string_cst)[byte_idx];
	if (ch >= 0x80)
	  return false;
      }
    return true;
  }

  void add_column_for_byte (table &t, const bit_to_table_map &btm,
			    style_manager &sm,
			    const byte_offset_t byte_idx_within_cluster,
			    const byte_offset_t byte_idx_within_string,
			    const int byte_idx_table_y,
			    const int byte_val_table_y) const
  {
    tree string_cst = get_string_cst ();
    gcc_assert (byte_idx_within_string >= 0);
    gcc_assert (byte_idx_within_string < TREE_STRING_LENGTH (string_cst));

    const byte_range bytes (byte_idx_within_cluster, 1);
    if (1) // show_byte_indices
      {
	const table::rect_t idx_table_rect
	  = btm.get_table_rect (&m_string_reg, bytes, byte_idx_table_y, 1);
	t.set_cell_span (idx_table_rect,
			 fmt_styled_string (sm, "[%li]",
					    byte_idx_within_string.ulow ()));
      }

    char byte_val
      = TREE_STRING_POINTER (string_cst)[byte_idx_within_string.ulow ()];
    const table::rect_t val_table_rect
      = btm.get_table_rect (&m_string_reg, bytes, byte_val_table_y, 1);
    table_cell_content content (make_cell_content_for_byte (sm, byte_val));
    t.set_cell_span (val_table_rect, std::move (content));
  }

  table_cell_content make_cell_content_for_byte (style_manager &sm,
						 unsigned char byte_val) const
  {
    if (!m_show_utf8)
       {
	if (byte_val == '\0')
	  return styled_string (sm, "NUL");
	else if (byte_val < 0x80)
	  if (ISPRINT (byte_val))
	    return fmt_styled_string (sm, "%qc", byte_val);
       }
    char buf[100];
    sprintf (buf, "0x%02x", byte_val);
    return styled_string (sm, buf);
  }

  const string_region &m_string_reg;
  const theme &m_theme;
  const int m_ellipsis_threshold;
  const int m_ellipsis_head_len;
  const int m_ellipsis_tail_len;
  const bool m_show_full_string;
  const bool m_show_utf8;
};

std::unique_ptr<svalue_spatial_item>
svalue_spatial_item::make (const access_operation &op,
			   const svalue &sval,
			   access_range actual_bits,
			   const theme &theme)
{
  if (const initial_svalue *initial_sval = sval.dyn_cast_initial_svalue ())
    if (const string_region *string_reg
	= initial_sval->get_region ()->dyn_cast_string_region ())
      return make_unique <string_region_spatial_item> (op, sval, actual_bits,
						       *string_reg, theme);
  return make_unique <svalue_spatial_item> (op, sval, actual_bits);
}

/* Widget subclass implementing access diagrams.  */

class access_diagram_impl : public vbox_widget
{
public:
  access_diagram_impl (const access_operation &op,
		       diagnostic_event_id_t region_creation_event_id,
		       style_manager &sm,
		       const theme &theme,
		       logger *logger)
  : m_op (op),
    m_region_creation_event_id (region_creation_event_id),
    m_sm (sm),
    m_theme (theme),
    m_logger (logger),
    m_invalid (false),
    m_valid_region_spatial_item (op, region_creation_event_id),
    m_accessed_region_spatial_item (op),
    m_btm (),
    m_calc_req_size_called (false)
  {
    LOG_SCOPE (logger);

    if (logger)
      {
	access_range invalid_before_bits;
	if (op.maybe_get_invalid_before_bits (&invalid_before_bits))
	  invalid_before_bits.log ("invalid before range", *logger);
	access_range invalid_after_bits;
	if (op.maybe_get_invalid_after_bits (&invalid_after_bits))
	  invalid_after_bits.log ("invalid after range", *logger);

	if (op.m_sval_hint)
	  {
	    logger->start_log_line ();
	    logger->log_partial ("sval_hint: ");
	    op.m_sval_hint->dump_to_pp (logger->get_printer (), true);
	    logger->end_log_line ();
	  }
      }

    /* Register painting styles.  */
    {
      style valid_style;
      valid_style.m_fg_color = style::named_color::GREEN;
      valid_style.m_bold = true;
      m_valid_style_id = m_sm.get_or_create_id (valid_style);

      style invalid_style;
      invalid_style.m_fg_color = style::named_color::RED;
      invalid_style.m_bold = true;
      m_invalid_style_id = m_sm.get_or_create_id (invalid_style);
    }

    if (op.m_sval_hint)
      {
	access_range actual_bits = m_op.get_actual_bits ();
	m_svalue_spatial_item = svalue_spatial_item::make (m_op,
							   *op.m_sval_hint,
							   actual_bits,
							   m_theme);
      }

    /* Two passes:
       First, figure out all of the boundaries of interest.
       Then use that to build child widgets showing the regions of interest,
       with a common tabular layout.  */

    m_boundaries = find_boundaries ();
    if (logger)
      m_boundaries->log (*logger);

    /* Populate m_table_x_for_bit and m_bit_for_table_x.
       Each table column represents the range [offset, next_offset).
       We don't create a column in the table for the final offset, but we
       do populate it, so that looking at the table_x of one beyond the
       final table column gives us the upper bound offset.  */
    m_btm.populate (*m_boundaries, logger);

    /* Gracefully reject cases where the boundary sorting has gone wrong
       (due to awkward combinations of symbolic values).  */
    {
      table::range_t actual_bits_x_range
	= m_btm.get_table_x_for_range (m_op.get_actual_bits ());
      if (actual_bits_x_range.get_size () <= 0)
	{
	  if (logger)
	    logger->log ("giving up: bad table columns for actual_bits");
	  m_invalid = true;
	  return;
	}
      table::range_t valid_bits_x_range
	= m_btm.get_table_x_for_range (m_op.get_valid_bits ());
      if (valid_bits_x_range.get_size () <= 0)
	{
	  if (logger)
	    logger->log ("giving up: bad table columns for valid_bits");
	  m_invalid = true;
	  return;
	}
    }

    m_col_widths
      = make_unique <table_dimension_sizes> (m_btm.get_num_columns ());

    /* Now create child widgets.  */

    if (flag_analyzer_debug_text_art)
      {
	table t_headings (make_headings_table ());
	add_aligned_child_table (std::move (t_headings));
      }

    if (m_svalue_spatial_item)
      {
	table t_sval (m_svalue_spatial_item->make_table (m_btm, m_sm));
	add_aligned_child_table (std::move (t_sval));
      }
    else
      {
	table t_accessed
	  (m_accessed_region_spatial_item.make_table (m_btm, m_sm));
	add_aligned_child_table (std::move (t_accessed));
      }

    add_direction_widget ();

    table t_valid (m_valid_region_spatial_item.make_table (m_btm, m_sm));
    add_invalid_accesses_to_region_table (t_valid);
    add_aligned_child_table (std::move (t_valid));

    add_valid_vs_invalid_ruler ();
  }

  const char *get_desc () const override
  {
    return "access_diagram_impl";
  }

  canvas::size_t calc_req_size () final override
  {
    if (m_invalid)
      return canvas::size_t (0, 0);

    /* Now compute the size requirements for the tables.  */
    for (auto iter : m_aligned_table_widgets)
      iter->get_cell_sizes ().pass_1 (iter->get_table ());
    for (auto iter : m_aligned_table_widgets)
      iter->get_cell_sizes ().pass_2 (iter->get_table ());

    adjust_to_scale();

    /* ...and relayout the tables.  */
    for (auto iter : m_aligned_table_widgets)
      iter->recalc_coords ();

    /* Populate the canvas_x per table_x.  */
    m_col_start_x.clear ();
    int iter_canvas_x = 0;
    for (auto w : m_col_widths->m_requirements)
      {
	m_col_start_x.push_back (iter_canvas_x);
	iter_canvas_x += w + 1;
      }
    m_col_start_x.push_back (iter_canvas_x);

    m_calc_req_size_called = true;

    return vbox_widget::calc_req_size ();
  }

  int get_canvas_x_for_table_x (int table_x) const
  {
    gcc_assert (m_calc_req_size_called);
    return m_col_start_x[table_x];
  }

  canvas::range_t get_canvas_x_range (const table::range_t &table_x_range) const
  {
    gcc_assert (m_calc_req_size_called);
    return canvas::range_t (get_canvas_x_for_table_x (table_x_range.start),
			    get_canvas_x_for_table_x (table_x_range.next));
  }

  const access_operation &get_op () const { return m_op; }

  style::id_t get_style_id_for_validity (bool is_valid) const
  {
    return is_valid ? m_valid_style_id : m_invalid_style_id;
  }

  const theme &get_theme () const { return m_theme; }

private:
  /* Figure out all of the boundaries of interest when visualizing ths op.  */
  std::unique_ptr<boundaries>
  find_boundaries () const
  {
    std::unique_ptr<boundaries> result
      = make_unique<boundaries> (*m_op.m_base_region);

    m_valid_region_spatial_item.add_boundaries (*result, m_logger);
    m_accessed_region_spatial_item.add_boundaries (*result, m_logger);
    if (m_svalue_spatial_item)
      m_svalue_spatial_item->add_boundaries (*result, m_logger);

    return result;
  }

  void add_aligned_child_table (table t)
  {
    x_aligned_table_widget *w
      = new x_aligned_table_widget (std::move (t), m_theme, *m_col_widths);
    m_aligned_table_widgets.push_back (w);
    add_child (std::unique_ptr<widget> (w));
  }

  /* Create a table showing headings for use by -fanalyzer-debug-text-art, for
     example:
     +---------+-----------+-----------+---+--------------------------------+
     |   tc0   |    tc1    |    tc2    |tc3|              tc4               |
     +---------+-----------+-----------+---+--------------------------------+
     |bytes 0-3|bytes 4-35 |bytes 36-39|   |          bytes 40-43           |
     +---------+-----------+-----------+   +--------------------------------+
     which has:
     - a row showing the table column numbers, labelled "tc0", "tc1", etc
     - a row showing the memory range of each table column that has one.  */

  table make_headings_table () const
  {
    table t (table::size_t (m_btm.get_num_columns (), 2));

    for (int table_x = 0; table_x < t.get_size ().w; table_x++)
      {
	const int table_y = 0;
	t.set_cell (table::coord_t (table_x, table_y),
		    fmt_styled_string (m_sm, "tc%i", table_x));
      }
    for (int table_x = 0; table_x < t.get_size ().w; table_x++)
      {
	const int table_y = 1;
	access_range range_for_column (NULL, bit_range (0, 0));
	if (m_btm.maybe_get_access_range_for_table_x (table_x,
						      &range_for_column))
	  {
	    pretty_printer pp;
	    pp_format_decoder (&pp) = default_tree_printer;
	    range_for_column.dump_to_pp (&pp, true);
	    t.set_cell (table::coord_t (table_x, table_y),
			styled_string (m_sm, pp_formatted_text (&pp)));
	  }
      }

    return t;
  }

  void add_direction_widget ()
  {
    add_child (::make_unique<direction_widget> (*this, m_btm));
  }

  void add_invalid_accesses_to_region_table (table &t_region)
  {
    gcc_assert (t_region.get_size ().w == (int)m_btm.get_num_columns ());

    const int table_y = 0;
    const int table_h = t_region.get_size ().h;

    access_range invalid_before_bits;
    if (m_op.maybe_get_invalid_before_bits (&invalid_before_bits))
      {
	t_region.set_cell_span (m_btm.get_table_rect (invalid_before_bits,
						      table_y, table_h),
				styled_string (m_sm,
					       _("before valid range")));
      }
    access_range invalid_after_bits;
    if (m_op.maybe_get_invalid_after_bits (&invalid_after_bits))
      {
	t_region.set_cell_span (m_btm.get_table_rect (invalid_after_bits,
						      table_y, table_h),
				styled_string (m_sm,
					       _("after valid range")));
      }
  }

  void maybe_add_gap (x_aligned_x_ruler_widget *w,
		      const access_range &lower,
		      const access_range &upper) const
  {
    LOG_SCOPE (m_logger);
    if (m_logger)
      {
	lower.log ("lower", *m_logger);
	upper.log ("upper", *m_logger);
      }
    tree lower_next = lower.m_next.calc_symbolic_bit_offset (m_op.m_model);
    if (!lower_next)
      {
	if (m_logger)
	  m_logger->log ("failed to get lower_next");
	return;
      }
    tree upper_start = upper.m_start.calc_symbolic_bit_offset (m_op.m_model);
    if (!upper_start)
      {
	if (m_logger)
	  m_logger->log ("failed to get upper_start");
	return;
      }
    tree num_bits_gap = fold_build2 (MINUS_EXPR,
				     size_type_node,
				     upper_start, lower_next);
    if (m_logger)
      m_logger->log ("num_bits_gap: %qE", num_bits_gap);
    tree zero = build_int_cst (size_type_node, 0);
    tristate ts_gt_zero = m_op.m_model.eval_condition (num_bits_gap,
						       GT_EXPR,
						       zero,
						       NULL);
    if (ts_gt_zero.is_false ())
      {
	if (m_logger)
	  m_logger->log ("rejecting as not > 0");
	return;
      }

    bit_size_expr num_bits (num_bits_gap);
    styled_string label = num_bits.get_formatted_str (m_sm,
						      _("%wi bit"),
						      _("%wi bits"),
						      _("%wi byte"),
						      _("%wi bytes"),
						      _("%qE bits"),
						      _("%qE bytes"));
    w->add_range (m_btm.get_table_x_for_range (access_range (lower.m_next,
							     upper.m_start)),
		  std::move (label),
		  style::id_plain);
  }

  styled_string
  make_warning_string (styled_string &&text)
  {
    styled_string result;
    if (!m_theme.emojis_p ())
      return std::move (text);

    result.append (styled_string (0x26A0, /* U+26A0 WARNING SIGN.  */
				  true));
    /* U+26A0 WARNING SIGN has East_Asian_Width == Neutral, but in its
       emoji variant is printed (by vte at least) with a 2nd half
       overlapping the next char.  Hence we add two spaces here: a space
       to be covered by this overlap, plus another space of padding.  */
    result.append (styled_string (m_sm, "  "));
    result.append (std::move (text));
    return result;
  }

  /* Add a ruler child widet showing valid, invalid, and gaps.  */
  void add_valid_vs_invalid_ruler ()
  {
    LOG_SCOPE (m_logger);

    x_aligned_x_ruler_widget *w
      = new x_aligned_x_ruler_widget (*this, m_theme, *m_col_widths);

    access_range invalid_before_bits;
    if (m_op.maybe_get_invalid_before_bits (&invalid_before_bits))
      {
	if (m_logger)
	  invalid_before_bits.log ("invalid_before_bits", *m_logger);
	bit_size_expr num_before_bits;
	if (invalid_before_bits.get_size (m_op.m_model, &num_before_bits))
	  {
	    styled_string label;
	    if (m_op.m_dir == DIR_READ)
	      label = num_before_bits.get_formatted_str
		(m_sm,
		 _("under-read of %wi bit"),
		 _("under-read of %wi bits"),
		 _("under-read of %wi byte"),
		 _("under-read of %wi bytes"),
		 _("under-read of %qE bits"),
		 _("under-read of %qE bytes"));
	    else
	      label = num_before_bits.get_formatted_str
		(m_sm,
		 _("underwrite of %wi bit"),
		 _("underwrite of %wi bits"),
		 _("underwrite of %wi byte"),
		 _("underwrite of %wi bytes"),
		 _("underwrite of %qE bits"),
		 _("underwrite of %qE bytes"));
	    w->add_range (m_btm.get_table_x_for_range (invalid_before_bits),
			  make_warning_string (std::move (label)),
			  m_invalid_style_id);
	  }
      }
    else
      {
	if (m_logger)
	  m_logger->log ("no invalid_before_bits");
      }

    /* It would be nice to be able to use std::optional<access_range> here,
       but std::optional is C++17.  */
    bool got_valid_bits = false;
    access_range valid_bits (m_op.get_valid_bits ());
    bit_size_expr num_valid_bits;
    if (valid_bits.get_size (m_op.m_model, &num_valid_bits))
      {
	if (m_logger)
	  valid_bits.log ("valid_bits", *m_logger);

	got_valid_bits = true;
	maybe_add_gap (w, invalid_before_bits, valid_bits);

	styled_string label;
	if (m_op.m_dir == DIR_READ)
	  label = num_valid_bits.get_formatted_str (m_sm,
						    _("size: %wi bit"),
						    _("size: %wi bits"),
						    _("size: %wi byte"),
						    _("size: %wi bytes"),
						    _("size: %qE bits"),
						    _("size: %qE bytes"));
	else
	  label = num_valid_bits.get_formatted_str (m_sm,
						    _("capacity: %wi bit"),
						    _("capacity: %wi bits"),
						    _("capacity: %wi byte"),
						    _("capacity: %wi bytes"),
						    _("capacity: %qE bits"),
						    _("capacity: %qE bytes"));
	w->add_range (m_btm.get_table_x_for_range (m_op.get_valid_bits ()),
		      std::move (label),
		      m_valid_style_id);
      }

    access_range invalid_after_bits;
    if (m_op.maybe_get_invalid_after_bits (&invalid_after_bits))
      {
	if (got_valid_bits)
	  maybe_add_gap (w, valid_bits, invalid_after_bits);

	if (m_logger)
	  invalid_before_bits.log ("invalid_after_bits", *m_logger);

	bit_size_expr num_after_bits;
	if (invalid_after_bits.get_size (m_op.m_model, &num_after_bits))
	  {
	    styled_string label;
	    if (m_op.m_dir == DIR_READ)
	      label = num_after_bits.get_formatted_str
		(m_sm,
		 _("over-read of %wi bit"),
		 _("over-read of %wi bits"),
		 _("over-read of %wi byte"),
		 _("over-read of %wi bytes"),
		 _("over-read of %qE bits"),
		 _("over-read of %qE bytes"));
	    else
	      label = num_after_bits.get_formatted_str
		(m_sm,
		 _("overflow of %wi bit"),
		 _("overflow of %wi bits"),
		 _("overflow of %wi byte"),
		 _("overflow of %wi bytes"),
		 _("over-read of %qE bits"),
		 _("overflow of %qE bytes"));
	    w->add_range (m_btm.get_table_x_for_range (invalid_after_bits),
			  make_warning_string (std::move (label)),
			  m_invalid_style_id);
	  }
      }
    else
      {
	if (m_logger)
	  m_logger->log ("no invalid_after_bits");
      }

    add_child (std::unique_ptr<widget> (w));
  }

  /* Subroutine of calc_req_size.
     Try to allocate surplus canvas width to table columns to make the
     per table-column canvas widths closer to being to scale.
     See e.g.:
       https://en.wikipedia.org/wiki/Fair_item_allocation
       https://en.wikipedia.org/wiki/Mathematics_of_apportionment
  */
  void adjust_to_scale ()
  {
    LOG_SCOPE (m_logger);
    const unsigned num_columns = m_btm.get_num_columns ();
    std::vector<bit_offset_t> bit_sizes (num_columns);
    for (unsigned table_x = 0; table_x < num_columns; table_x++)
      {
	access_range range_for_column (NULL, bit_range (0, 0));
	if (m_btm.maybe_get_access_range_for_table_x (table_x,
						      &range_for_column))
	  {
	    bit_size_t size_in_bits;
	    if (!range_for_column.get_size_in_bits (&size_in_bits))
	      size_in_bits = BITS_PER_UNIT; // arbitrary non-zero value
	    gcc_assert (size_in_bits > 0);
	    bit_sizes[table_x] = size_in_bits;
	  }
	else
	  bit_sizes[table_x] = 0;
      }

    while (adjust_to_scale_once (bit_sizes))
      {
      }
  }
  bool adjust_to_scale_once (const std::vector<bit_offset_t> &bit_sizes)
  {
    LOG_SCOPE (m_logger);

    const unsigned num_columns = m_btm.get_num_columns ();

    /* Find the total canvas width currently required.
       Require one extra canvas column for the right-hand border
       of the table.  */
    int total_width = 1;
    for (unsigned table_x = 0; table_x < num_columns; table_x++)
      {
	int canvas_w = m_col_widths->m_requirements[table_x];
	gcc_assert (canvas_w >= 0);
	total_width += canvas_w + 1;
      }

    const int max_width = param_analyzer_text_art_ideal_canvas_width;
    if (total_width >= max_width)
      {
	if (m_logger)
	  m_logger->log ("bailing out: total_width=%i ,>= max_width (%i)\n",
			 total_width, max_width);
	return false;
      }

    const int fixed_point = 1024;
    std::vector<bit_offset_t> canvas_w_per_bit (num_columns);
    for (unsigned table_x = 0; table_x < num_columns; table_x++)
      {
	bit_offset_t bit_size = bit_sizes[table_x];
	if (bit_size > 0)
	  canvas_w_per_bit[table_x]
	    = (m_col_widths->m_requirements[table_x] * fixed_point) / bit_size;
	else
	  canvas_w_per_bit[table_x] = INT_MAX;
      }

    /* Find the min canvas per bit, and give an extra canvas column to
       the table column that has least.  */
    size_t min_idx = std::distance (canvas_w_per_bit.begin (),
				    std::min_element (canvas_w_per_bit.begin (),
						      canvas_w_per_bit.end ()));
    m_col_widths->m_requirements[min_idx] += 1;
    if (m_logger)
      m_logger->log ("adding 1 canvas_w to column %i\n", (int)min_idx);

    return true; // keep going
  }

  const access_operation &m_op;
  diagnostic_event_id_t m_region_creation_event_id;
  style_manager &m_sm;
  const theme &m_theme;
  logger *m_logger;
  /* In lieu of being able to throw exceptions, a flag to mark this object
     as "invalid".  */
  bool m_invalid;

  style::id_t m_valid_style_id;
  style::id_t m_invalid_style_id;

  valid_region_spatial_item m_valid_region_spatial_item;
  accessed_region_spatial_item m_accessed_region_spatial_item;
  std::unique_ptr<svalue_spatial_item> m_svalue_spatial_item;

  std::unique_ptr<boundaries> m_boundaries;

  bit_to_table_map m_btm;

  bool m_calc_req_size_called;

  /* Column widths shared by all x_aligned_table_widget,
     created once we know how many columns we need.  */
  std::unique_ptr<table_dimension_sizes> m_col_widths;

  /* All of the child x_aligned_table_widget that share
     column widths.  */
  std::vector<x_aligned_table_widget *> m_aligned_table_widgets;

/* Mapping from table_x to canvas_x.  */
  std::vector<int> m_col_start_x;
};

x_ruler
x_aligned_x_ruler_widget::make_x_ruler () const
{
  x_ruler r (x_ruler::label_dir::BELOW);
  for (auto& iter : m_labels)
    {
      canvas::range_t canvas_x_range
	= m_dia_impl.get_canvas_x_range (iter.m_table_x_range);
      /* Include the end-point.  */
      canvas_x_range.next++;
      r.add_label (canvas_x_range, iter.m_text.copy (), iter.m_style_id,
		   x_ruler::label_kind::TEXT_WITH_BORDER);
    }
  return r;
}

/* class direction_widget : public leaf_widget.  */

/* Paint arrows indicating the direction of the access (read vs write),
   but only in the X-extent corresponding to the region that's actually
   accessed.  */

void
direction_widget::paint_to_canvas (canvas &canvas)
{
  const access_range accessed_bits (m_dia_impl.get_op ().get_actual_bits ());

  const access_range valid_bits (m_dia_impl.get_op ().get_valid_bits ());

  for (unsigned table_x = 0; table_x < m_btm.get_num_columns (); table_x++)
    {
      access_range column_access_range;
      if (m_btm.maybe_get_access_range_for_table_x (table_x,
						    &column_access_range))
	{
	  /* Only paint arrows in the accessed region.  */
	  if (!accessed_bits.contains_p (column_access_range))
	    continue;

	  /* Are we within the valid region?  */
	  const bool is_valid (valid_bits.contains_p (column_access_range));
	  const style::id_t style_id
	    = m_dia_impl.get_style_id_for_validity (is_valid);
	  const canvas::range_t x_canvas_range
	    = m_dia_impl.get_canvas_x_range (table::range_t (table_x,
							     table_x + 1));
	  const int canvas_x = x_canvas_range.get_midpoint ();
	  m_dia_impl.get_theme ().paint_y_arrow
	    (canvas,
	     canvas_x,
	     canvas::range_t (get_y_range ()),
	     (m_dia_impl.get_op ().m_dir == DIR_READ
	      ? theme::y_arrow_dir::UP
	      : theme::y_arrow_dir::DOWN),
	     style_id);
	}
    }
}

/* class access_diagram : public text_art::wrapper_widget.  */

/* To hide the implementation details, this is merely a wrapper around
   an access_diagram_impl.  */

access_diagram::access_diagram (const access_operation &op,
				diagnostic_event_id_t region_creation_event_id,
				style_manager &sm,
				const theme &theme,
				logger *logger)
: wrapper_widget (make_unique <access_diagram_impl> (op,
						     region_creation_event_id,
						     sm,
						     theme,
						     logger))
{
}

} // namespace ana

#endif /* #if ENABLE_ANALYZER */