diagnostics: add state diagrams to analyzer experimental-html output [PR116792]

diagnostics: add state diagrams to analyzer experimental-html output [PR116792]

This patch adds various support for debugging diagnostic paths and
events, intended initially for myself to help with debugging -fanalyzer.

It adds the optional ability for a diagnostic_event to supply a
description of the predicted state of the program at that point along
the diagnostic_path.  To isolate the diagnostic subsystem from the
analyzer, this representation is currently an xml::document with custom
elements.  The XML representation is similar to the analyzer's internal
state but can be easier to read - for example, rather than storing the
contents of memory via byte offsets, it uses fields for structs and
element indexes for arrays, recursively.

These states are handled by the HTML and SARIF diagnostic sinks.

The SARIF sink simply embeds the XML as a string in a property bag of the
threadFlowLocation object (SARIF v2.1.0 section 3.38).

For HTML output, the "experimental-html" sink gains a new
"show-state-diagrams=yes" option i.e.:
  -fdiagnostics-add-output=experimental-html:show-state-diagrams=yes
which converts the state XML into SVG diagrams visualizing the state of
memory at each event, inspired by the "ddd" debugger.  These can be seen
by pressing 'j' and 'k' to single-step forward and backward through
events, making it *much* easier to debug -fanalyzer.

An example of output can be seen here:
  https://dmalcolm.fedorapeople.org/gcc/2025-06-23/state-diagram-1.c.html
showing an issue in a singly-linked list; there are various other
examples in the parent directory.

Generating the SVG diagrams requires an invocation of "dot" per event,
so it noticeable slows down diagnostic emission, hence the opt-in
command-line flag.  However, I'm already finding bugs in -fanalyzer with
this that I hadn't seen before.

Given that the UI is rather clunky and there is lots of room for
improvement to the visualizations, for now this feature is marked
as being for GCC developers, not end-users.

The patch also adds a dot::ast_node class hierarachy to make it easy to
create GraphViz dot files with the correct escaping, and adds a C++
wrapper around pex adding some syntactic sugar for invoking
subprocesses.

gcc/ChangeLog:
	PR other/116792
	* Makefile.in (ANALYZER_OBJS): Add
	analyzer/ana-state-to-diagnostic-state.o.
	(OBJS): Move graphviz.o to...
	(OBJS-libcommon): ...here.  Add diagnostic-state-to-dot.o and pex.o.
	* diagnostic-format-html.cc: Include "diagnostic-state.h" and
	"graphviz.h".
	(html_generation_options::html_generation_options): Initialize the
	new flags.
	(HTML_SCRIPT): Add function "get_any_state_diagram".  Use it
	when changing current focus id to update the visibility of the
	pertinent diagram, if any.
	(print_pre_source): New.
	(html_builder::maybe_make_state_diagram): New.
	(html_path_label_writer::html_path_label_writer): Add "path" param.
	Initialize m_path and m_curr_event_id.
	(html_path_label_writer::begin_label): Store current event id.
	(html_path_label_writer::end_label): Attempt to make a state
	diagram and add it if successful.
	(html_path_label_writer::get_element_id): New.
	(html_path_label_writer::m_path): New field.
	(html_path_label_writer::m_curr_event_id): New field.
	(html_builder::make_element_for_diagnostic): Pass path to label
	writer.
	* diagnostic-format-html.h
	(html_generation_options::m_show_state_diagrams): New field.
	(html_generation_options::m_show_state_diagram_xml): New field.
	(html_generation_options::m_show_state_diagram_dot_src): New field.
	* diagnostic-format-sarif.cc: Include "xml.h".
	(populate_thread_flow_location_object): If requested, attempt to
	generate xml state and add it to the proeprty bag as
	"gcc/diagnostic_event/xml_state" in xml source form.
	(sarif_generation_options::sarif_generation_options): Initialize
	m_xml_state.
	* diagnostic-format-sarif.h
	(sarif_generation_options::m_xml_state): New field.
	* diagnostic-path.cc: Define INCLUDE_MAP.  Include "xml.h".
	(diagnostic_event::maybe_make_xml_state): New.
	* diagnostic-path.h (class xml::document): New forward decl.
	(diagnostic_event::maybe_make_xml_state): New vfunc decl.
	* diagnostic-state-to-dot.cc: New file.
	* diagnostic-state.h: New file.
	* digraph.cc: Define INCLUDE_STRING and INCLUDE_VECTOR.
	* doc/analyzer.texi: Document state diagrams in html output.
	(__analyzer_dump_dot): New.
	(__analyzer_dump_xml): New.
	* doc/invoke.texi (sarif): Add "xml-state" key.
	(experimental-html): Add keys "show-state-diagrams",
	"show-state-diagrams-dot-src" and "show-state-diagrams-xml".
	* graphviz.cc: Define INCLUDE_MAP, INCLUDE_STRING, and
	INCLUDE_VECTOR.  Include "xml.h", "xml-printer.h", "pex.h" and
	"selftest.h".
	(graphviz_out::graphviz_out): Extract...
	(dot::writer::writer): ...this.
	(graphviz_out::write_indent): Convert to...
	(dot::writer::write_indent): ...this.
	(graphviz_out::print): Use get_pp.
	(graphviz_out::println): Likewise.
	(graphviz_out::begin_tr): Likewise.
	(graphviz_out::end_tr): Likewise.
	(graphviz_out::begin_td): Likewise.
	(graphviz_out::end_td): Likewise.
	(graphviz_out::begin_trtd): Likewise.
	(graphviz_out::end_tdtr): Likewise.
	(dot::ast_node::dump): New.
	(dot::id::id): New.
	(dot::id::print): New.
	(dot::id::is_identifier_p): New.
	(dot::kv_pair::print): New.
	(dot::attr_list::print): New.
	(dot::stmt_list::print): New.
	(dot::stmt_list::add_edge): New.
	(dot::stmt_list::add_attr): New.
	(dot::graph::print): New.
	(dot::stmt_with_attr_list::set_label): New.
	(dot::node_stmt::print): New.
	(dot::attr_stmt::print): New.
	(dot::kv_stmt::print): New.
	(dot::node_id::print): New.
	(dot::port::print): New.
	(dot::edge_stmt::print): New.
	(dot::subgraph::print): New.
	(dot::make_svg_document_buffer_from_graph): New.
	(dot::make_svg_from_graph): New.
	(selftest:test_ids): New.
	(selftest:test_trivial_graph): New.
	(selftest:test_layout_example): New.
	(selftest:graphviz_cc_tests): New.
	* graphviz.h (xml::node): New forward decl.
	(class graphviz_out): Split out into...
	(class dot::writer): ...this new class
	(struct dot::ast_node): New.
	(struct dot::id): New.
	(struct dot::kv_pair): New.
	(struct dot::attr_list): New.
	(struct dot::stmt_list): New.
	(struct dot::graph): New.
	(struct dot::stmt): New.
	(struct dot::stmt_with_attr_list): New.
	(struct dot::node_stmt): New.
	(struct dot::attr_stmt): New.
	(struct dot::kv_stmt): New.
	(enum class dot::compass_pt): New.
	(struct dot::port): New.
	(struct dot::node_id): New.
	(struct dot::edge_stmt): New.
	(struct dot::subgraph): New.
	(dot::make_svg_from_graph): New.
	* opts-diagnostic.cc (sarif_scheme_handler::make_sink): Add
	"xml-state" flag.
	(html_scheme_handler::make_sink): Add flags "show-state-diagrams",
	"show-state-diagram-dot-src", and "show-state-diagram-xml".
	* pex.cc: New file.
	* pex.h: New file.
	* selftest-run-tests.cc (selftest::run_tests): Call
	graphviz_cc_tests.
	* selftest.h (selftest::graphviz_cc_tests): New decl.
	* xml.cc (xml::node_with_children::add_comment): New.
	(xml::node_with_children::find_child_element): New.
	(xml::element::get_attr): New.
	(xml::comment::write_as_xml): New.
	(selftest::test_printer): Add coverage of find_child_element and
	get_attr.
	(selftest::test_comment): New.
	(selftest::xml_cc_tests): Call test_comment.
	* xml.h: New forward decls.
	(xml::node::dyn_cast_text): Use nullptr.
	(xml::node::dyn_cast_element): New vfunc.
	(xml::node_with_children::add_comment): New decl.
	(xml::node_with_children::find_child_element): New decl.
	(xml::element::dyn_cast_element): New vfunc impl.
	(xml::element::get_attr): New decl.
	(struct xml::comment): New xml::node subclass.

gcc/analyzer/ChangeLog:
	PR other/116792
	* ana-state-to-diagnostic-state.cc: New file.
	* ana-state-to-diagnostic-state.h: New file.
	* checker-event.cc: Include "xml.h".
	(checker_event::checker_event): Initialize m_path.
	(checker_event::prepare_for_emission): Store the path pointer into
	m_path.
	(checker_event::maybe_make_xml_state): New.
	(function_entry_event::function_entry_event): Add "state" param
	and use it to initialize m_state.
	(superedge_event::get_program_state): New.
	(call_event::get_program_state): New.
	(warning_event::get_program_state): New.
	* checker-event.h (checker_event::get_program_state): New vfunc.
	(checker_event::maybe_make_xml_state): New decl.
	(checker_event::m_path): New field.
	(statement_event::get_program_state): New vfunc impl.
	(function_entry_event::function_entry_event): Add "state" param.
	(function_entry_event::get_program_state): New vfunc impl.
	(function_entry_event::m_state): New field.
	(state_change_event::get_program_state): New vfunc impl.
	(superedge_event::get_program_state): New vfunc decl.
	(warning_event::warning_event): Add "program_state_" param and
	copy it.
	(warning_event::get_program_state): New vfunc decl.
	(warning_event::m_program_state): New field.
	* checker-path.h (checker_path::checker_path): Add ext_state param.
	(checker_path::get_ext_state): New accessor.
	(checker_path::m_ext_state): New field.
	* common.h: Define INCLUDE_MAP and INCLUDE_STRING.
	* diagnostic-manager.cc (saved_diagnostic::operator==): Don't
	deduplicate dump_path_diagnostic instances.
	(diagnostic_manager::emit_saved_diagnostic): Pass ext_state to
	checker_path ctor.
	* engine.cc:
	(impl_region_model_context::on_state_leak): Pass old and new state
	to state_machine::on_leak.
	(exploded_node::on_stmt_pre): Implement __analyzer_dump_xml and
	__analyzer_dump_dot.
	* exploded-graph.h (impl_region_model_context::get_state): New.
	* infinite-recursion.cc
	(recursive_function_entry_event::recursive_function_entry_event):
	Add "dst_state" param and pass to function_entry_event ctor.
	(infinite_recursion_diagnostic::add_function_entry_event): Pass state
	to event ctor.
	* kf-analyzer.cc: Include "analyzer/program-state.h"
	(dump_path_diagnostic::dump_path_diagnostic): Add "state" param.
	(dump_path_diagnostic::get_final_state): New.
	(dump_path_diagnostic::m_state): New field.
	(kf_analyzer_dump_path::impl_call_pre): Pass state to warning.
	* pending-diagnostic.cc
	(pending_diagnostic::add_function_entry_event): Pass state to
	function_entry_event.
	(pending_diagnostic::add_final_event): Likewise to warning_event.
	* pending-diagnostic.h (pending_diagnostic::get_final_state): New
	vfunc decl.
	* program-state.cc: Include "diagnostic-state.h", "graphviz.h" and
	"analyzer/ana-state-to-diagnostic-state.h".
	(program_state::dump_dot): New.
	* program-state.h: Include "text-art/tree-widget.h" and
	"analyzer/store.h".
	(class xml::document): New forward decl.
	(make_xml): New.
	(dump_xml_to_pp): New.
	(dump_xml_to_file): New.
	(dump_xml): New.
	(dump_dot): New.
	* record-layout.cc (record_layout::record_layout): Make param
	const_tree.
	* record-layout.h (item::item): Likewise.
	(item::m_field): Likewise.
	(record_layout::record_layout): Likewise.
	(record_layout::begin): New.
	(record_layout::end): New.
	* region-model.cc
	(exposure_through_uninit_copy::complain_about_fully_uninit_item):
	Use const_tree.
	(exposure_through_uninit_copy::complain_about_partially_uninit_item):
	Likewise.
	* region-model.h (region_model_context::get_state): New vfunc.
	(noop_region_model_context::get_state): New.
	(region_model_context_decorator::get_state): New.
	* sm-fd.cc (fd_leak::fd_leak): Add "final_state" param and capture
	it if present.
	(fd_leak::get_final_state): New.
	(fd_leak::m_final_state): New.
	(fd_state_machine::on_open): Pass nullptr for new "final_state"
	param.
	(fd_state_machine::on_creat): Likewise.
	(fd_state_machine::on_socket): Likewise.
	(fd_state_machine::on_accept): Likewise.
	(fd_state_machine::on_leak): Add state params and pass new state
	as final state to fd_leak ctor.
	* sm-file.cc: Include "analyzer/program-state.h".
	(file_leak::file_leak): Add "final_state" param and capture it if
	present.
	(file_leak::get_final_state): New.
	(file_leak::m_final_state): New.
	(fileptr_state_machine::on_leak): Add state params and pass new
	state as final state to fd_leak ctor.
	* sm-malloc.cc: Include
	"analyzer/ana-state-to-diagnostic-state.h".
	(malloc_leak::malloc_leak): Add "final_state" param and use it.
	(malloc_leak::get_final_state): New vfunc impl.
	(malloc_leak::m_final_state): New field.
	(malloc_state_machine::on_leak): Add state params; capture final
	state.
	(malloc_state_machine::add_state_to_xml): New.
	* sm.cc (state_machine::on_leak): Add "old_state" and "new_state"
	params.  Use nullptr.
	(state_machine::add_state_to_xml): New.
	(state_machine::add_global_state_to_xml): New.
	* sm.h (class xml_state): New forward decl.
	(state_machine::on_leak): Add state params.
	(state_machine::add_state_to_xml): New vfunc decl.
	(state_machine::add_global_state_to_xml): New vfunc decl.
	* store.h (bit_range::operator<): New.
	* varargs.cc (va_list_leak::va_list_leak): Add final_state param
	and capture it if non-null.
	(va_list_leak::get_final_state): New.
	(va_list_leak::m_final_state): New.
	(va_list_state_machine::on_leak): Add state params and pass final
	state to va_list_leak ctor.

gcc/testsuite/ChangeLog:
	PR other/116792
	* g++.dg/analyzer/state-diagram.C: New test.
	* gcc.dg/analyzer/analyzer-decls.h (__analyzer_dump_dot): New
	decl.
	(__analyzer_dump_xml): New decl.
	* gcc.dg/analyzer/state-diagram-1-sarif.py: New test script.
	* gcc.dg/analyzer/state-diagram-1.c: New test.
	* gcc.dg/analyzer/state-diagram-2.c: New test.
	* gcc.dg/analyzer/state-diagram-3.c: New test.
	* gcc.dg/analyzer/state-diagram-4.c: New test.
	* gcc.dg/analyzer/state-diagram-5-html.py: New test script.
	* gcc.dg/analyzer/state-diagram-5-sarif.py: New test script.
	* gcc.dg/analyzer/state-diagram-5.c: New test.
	* gcc.dg/plugin/analyzer_cpython_plugin.cc: Define INCLUDE_STRING.
	* gcc.dg/plugin/analyzer_gil_plugin.cc: Likewise.
	* gcc.dg/plugin/analyzer_kernel_plugin.cc: Likewise.
	* gcc.dg/plugin/analyzer_known_fns_plugin.cc: Likewise.
	* lib/htmltest.py (ns): Add SVG namespace.
	* lib/sarif.py (get_result_by_index): New.
	(get_xml_state): New.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>