diagnostics: add support for directed graphs; use them for state graphs

diagnostics: add support for directed graphs; use them for state graphs

In r16-1631-g2334d30cd8feac I added support for capturing state
information from -fanalyzer in XML form, and adding a way to visualize
these states in HTML output.  The data was optionally captured in SARIF
output (with "xml-state=yes"), stashing the XML in string form in
a property bag.

This worked, but there was no way to round-trip the stored data back
from SARIF without adding an XML parser to GCC, which I don't want to
do.

SARIF supports capturing directed graphs, so this patch:

(a) adds a new namespace diagnostics::digraphs, with classes digraph,
node, and edge, representing directed graphs in a form similar to
what SARIF can serialize

(b) adds support to GCC's diagnostic subsystem for reporting graphs,
either "globally" or as part of a diagnostic.  An example in a testsuite
plugin emits an error that has a couple of dummy graphs associated with
it, and captures the optimization passes as a digraph "globally".
Graphs are ignored by text sinks, but are captured by sarif sinks,
and the "experimental-html" sink gains SVG-based rendering of any graphs
using dot.  This HTML output is rather crude; an example can be seen
here:
  https://dmalcolm.fedorapeople.org/gcc/2025-07-10/diagnostic-test-graphs-html.c.html

(c) adds support to libgdiagnostics for the above

(d) adds support to sarif-replay for the above (round-tripping any
graph information)

(e) replaces the XML representation of state with a representation
based on the above directed graphs, using property bags to stash
additional information (e.g. "this is an on-stack buffer")

(f) implements round-tripping of this information in sarif-replay

To summarize:
- previously we could generate HTML diagrams for debugging
  -fanalyzer directly from gcc, but not from stored .sarif output.
- with this patch, we can generate such HTML diagrams both directly
  *and* from stored .sarif output (provided the SARIF sink was created
  with "state-graphs=yes")

Examples of HTML output can be seen here:
  https://dmalcolm.fedorapeople.org/gcc/2025-07-10/
where as before j/k can be used to cycle through the events.
which is almost identical to the output from the old XML-based
implementation seen at:
  https://dmalcolm.fedorapeople.org/gcc/2025-06-23/

gcc/ChangeLog:
	* Makefile.in (OBJS-libcommon): Add diagnostic-digraphs.o and
	diagnostic-state-graphs.o.

gcc/ChangeLog:
	* diagnostic-format-html.cc: Include "diagnostic-format-sarif.h",
	Replace include of "diagnostic-state.h" with includes of
	"diagnostic-digraphs.h" and "diagnostic-state-graphs.h".
	(html_generation_options::html_generation_options): Update for
	field renaming.
	(html_builder::m_body_element): New field.
	(html_builder::html_builder): Initialize m_body_element.
	(html_builder::maybe_make_state_diagram): Port from XML
	implementation to state graph implementation.
	(html_builder::make_element_for_diagnostic): Add any
	per-diagnostic graphs.
	(html_builder::add_graph): New.
	(html_builder::emit_global_graph): New.
	(html_output_format::report_global_digraph): New.
	* diagnostic-format-html.h
	(html_generation_options::m_show_state_diagram_xml): Replace
	with...
	(html_generation_options::m_show_state_diagrams_sarif): ...this.
	(html_generation_options::m_show_state_diagram_dot_src): Rename
	to...
	(html_generation_options::m_show_state_diagrams_dot_src): ...this.
	* diagnostic-format-sarif.cc: Include "diagnostic-digraphs.h" and
	"diagnostic-state-graphs.h".
	(sarif_builder::m_run_graphs): New field.
	(sarif_result::on_nested_diagnostic): Update call to
	make_location_object to pass arg by pointer.
	(sarif_builder::sarif_builder): Initialize m_run_graphs.
	(sarif_builder::report_global_digraph): New.
	(sarif_builder::make_result_object): Add any graphs to
	the result object.
	(sarif_builder::make_locations_arr): Update call to
	make_location_object to pass arg by pointer.
	(sarif_builder::make_location_object): Pass param "loc_mgr" by
	pointer rather than by reference so that it can be null, and
	handle this case.
	(copy_any_property_bag): New.
	(make_sarif_graph): New.
	(make_sarif_node): New.
	(make_sarif_edge): New.
	(sarif_property_bag::set_graph): New.
	(populate_thread_flow_location_object): Port from XML
	implementation to state graph implementation.
	(make_run_object): Store any graphs.
	(sarif_output_format::report_global_digraph): New.
	(sarif_generation_options::sarif_generation_options): Rename
	m_xml_state to m_state_graph.
	(selftest::test_make_location_object): Update for change to
	make_location_object.
	* diagnostic-format-sarif.h:
	(sarif_generation_options::m_xml_state): Replace with...
	(sarif_generation_options::m_state_graph): ...this.
	(class sarif_location_manager): Add forward decl.
	(diagnostics::digraphs::digraph): New forward decl.
	(diagnostics::digraphs::node): New forward decl.
	(diagnostics::digraphs::edge): New forward decl.
	(sarif_property_bag::set_graph): New decl.
	(class sarif_graph): New.
	(class sarif_node): New.
	(class sarif_edge): New.
	(make_sarif_graph): New decl.
	(make_sarif_node): New decl.
	(make_sarif_edge): New decl.
	* diagnostic-format-text.h
	(diagnostic_text_output_format::report_global_digraph): New.
	* diagnostic-format.h
	(diagnostic_output_format::report_global_digraph): New vfunc.
	* diagnostic-digraphs.cc: New file.
	* diagnostic-digraphs.h: New file.
	* diagnostic-metadata.h (diagnostics::digraphs::lazy_digraphs):
	New forward decl.
	(diagnostic_metadata::diagnostic_metadata): Initialize
	m_lazy_digraphs.
	(diagnostic_metadata::set_lazy_digraphs): New.
	(diagnostic_metadata::get_lazy_digraphs): New.
	(diagnostic_metadata::m_lazy_digraphs): New field.
	* diagnostic-output-spec.cc (sarif_scheme_handler::make_sink):
	Update for XML to state graph changes.
	(sarif_scheme_handler::make_sarif_gen_opts): Likewise.
	(html_scheme_handler::make_sink): Rename "show-state-diagram-xml"
	to "show-state-diagrams-sarif" and use pluralization consistently.
	* diagnostic-path.cc: Replace include of "xml.h" with
	"diagnostic-state-graphs.h".
	(diagnostic_event::maybe_make_xml_state): Replace with...
	(diagnostic_event::maybe_make_diagnostic_state_graph): ...this.
	* diagnostic-path.h (diagnostics::digraphs::digraph): New forward
	decl.
	(diagnostic_event::maybe_make_xml_state): Replace with...
	(diagnostic_event::maybe_make_diagnostic_state_graph): ...this.
	* diagnostic-state-graphs.cc: New file.
	* diagnostic-state-graphs.h: New file.
	* diagnostic-state-to-dot.cc: Port implementation from XML to
	state graphs.
	* diagnostic-state.h: Deleted file.
	* diagnostic.cc (diagnostic_context::report_global_digraph): New.
	* diagnostic.h (diagnostics::digraphs::lazy_digraph): New forward
	decl.
	(diagnostic_context::report_global_digraph): New decl.
	* doc/analyzer.texi (Debugging the Analyzer): Update to reflect
	change from XML to state graphs.
	* doc/invoke.texi ("sarif" diagnostics sink): Replace "xml-state"
	with "state-graphs".
	("experimental-html" diagnostics sink): Replace
	"show-state-diagrams-xml" with "show-state-diagrams-sarif"
	* doc/libgdiagnostics/topics/compatibility.rst
	(LIBGDIAGNOSTICS_ABI_3): New.
	* doc/libgdiagnostics/topics/graphs.rst: New file.
	* doc/libgdiagnostics/topics/index.rst: Add graphs.rst.
	* graphviz.h (node_id::operator=): New.
	* json.h (json::value::dyn_cast_string): New.
	(json::object::get_num_keys): New accessor.
	(json::object::get_key): New accessor.
	(json::string::dyn_cast_string): New.
	* libgdiagnostics++.h (class libgdiagnostics::graph): New.
	(class libgdiagnostics::node): New.
	(class libgdiagnostics::edge): New.
	(class libgdiagnostics::diagnostic::take_graph): New.
	(class libgdiagnostics::manager::take_global_graph): New.
	(class libgdiagnostics::graph::set_description): New.
	(class libgdiagnostics::graph::get_node_by_id): New.
	(class libgdiagnostics::graph::get_edge_by_id): New.
	(class libgdiagnostics::graph::add_edge): New.
	(class libgdiagnostics::node::set_label): New.
	(class libgdiagnostics::node::set_location): New.
	(class libgdiagnostics::node::set_logical_location): New.
	* libgdiagnostics-private.h: New file.
	* libgdiagnostics.cc: Define INCLUDE_STRING.  Include
	"diagnostic-digraphs.h", "diagnostic-state-graphs.h", and
	"libgdiagnostics-private.h".
	(struct diagnostic_graph): New.
	(struct diagnostic_node): New.
	(struct diagnostic_edge): New.
	(libgdiagnostics_path_event::libgdiagnostics_path_event): Add
	state_graph param.
	(libgdiagnostics_path_event::maybe_make_diagnostic_state_graph):
	New.
	(libgdiagnostics_path_event::m_state_graph): New field.
	(diagnostic_execution_path::add_event_va): Add state_graph param.
	(class prebuilt_digraphs): New.
	(diagnostic::diagnostic): Use m_graphs in m_metadata.
	(diagnostic::take_graph): New.
	(diagnostic::get_graphs): New accessor.
	(diagnostic::m_graphs): New field.
	(diagnostic_manager::take_global_graph): New.
	(diagnostic_execution_path_add_event): Update for new param to
	add_event_va.
	(diagnostic_execution_path_add_event_va): Likewise.
	(diagnostic_graph::add_node_with_id): New public entrypoint.
	(diagnostic_graph::add_edge_with_label): New public entrypoint.
	(diagnostic_manager_new_graph): New public entrypoint.
	(diagnostic_manager_take_global_graph): New public entrypoint.
	(diagnostic_take_graph): New public entrypoint.
	(diagnostic_graph_release): New public entrypoint.
	(diagnostic_graph_set_description): New public entrypoint.
	(diagnostic_graph_add_node): New public entrypoint.
	(diagnostic_graph_add_edge): New public entrypoint.
	(diagnostic_graph_get_node_by_id): New public entrypoint.
	(diagnostic_graph_get_edge_by_id): New public entrypoint.
	(diagnostic_node_set_location): New public entrypoint.
	(diagnostic_node_set_label): New public entrypoint.
	(diagnostic_node_set_logical_location): New public entrypoint.
	(private_diagnostic_execution_path_add_event_2): New private
	entrypoint.
	(private_diagnostic_graph_set_property_bag): New private
	entrypoint.
	(private_diagnostic_node_set_property_bag): New private
	entrypoint.
	(private_diagnostic_edge_set_property_bag): New private
	entrypoint.
	* libgdiagnostics.h (diagnostic_graph): New typedef.
	(diagnostic_node): New typedef.
	(diagnostic_edge): New typedef.
	(diagnostic_manager_new_graph): New decl.
	(diagnostic_manager_take_global_graph): New decl.
	(diagnostic_take_graph): New decl.
	(diagnostic_graph_release): New decl.
	(diagnostic_graph_set_description): New decl.
	(diagnostic_graph_add_node): New decl.
	(diagnostic_graph_add_edge): New decl.
	(diagnostic_graph_get_node_by_id): New decl.
	(diagnostic_graph_get_edge_by_id): New decl.
	(diagnostic_node_set_label): New decl.
	(diagnostic_node_set_location): New decl.
	(diagnostic_node_set_logical_location): New decl.
	* libgdiagnostics.map (LIBGDIAGNOSTICS_ABI_3): New.
	* libsarifreplay.cc: Include "libgdiagnostics-private.h".
	(id_map): New "using".
	(sarif_replayer::report_invalid_sarif): Update for change to
	report_problem params.
	(sarif_replayer::report_unhandled_sarif): Likewise.
	(sarif_replayer::report_note): New.
	(sarif_replayer::report_problem): Pass param "ref" by
	pointer rather than reference and handle it being null.
	(sarif_replayer::maybe_get_property_bag): New.
	(sarif_replayer::maybe_get_property_bag_value): New.
	(sarif_replayer::handle_run_obj): Handle run-level "graphs" as per
	§3.14.20.
	(sarif_replayer::handle_result_obj): Handle result-level "graphs"
	as per §3.27.19.
	(handle_thread_flow_location_object): Optionally handle graphs
	stored in property "gcc/diagnostic_event/state_graph" as state
	graphs.
	(sarif_replayer::handle_graph_object): New.
	(sarif_replayer::handle_node_object): New.
	(sarif_replayer::handle_edge_object): New.
	(sarif_replayer::get_graph_node_by_id_property): New.
	* selftest-run-tests.cc (selftest::run_tests): Call
	selftest::diagnostic_graph_cc_tests and
	selftest::diagnostic_state_graph_cc_tests.
	* selftest.h (selftest::diagnostic_graph_cc_tests): New decl.
	(selftest::diagnostic_state_graph_cc_tests): New decl.

gcc/analyzer/ChangeLog:
	* ana-state-to-diagnostic-state.cc: Reimplement, replacing
	XML-based implementation with one based on state graphs.
	* ana-state-to-diagnostic-state.h: Likewise.
	* checker-event.cc: Replace include of "xml.h" with include of
	"diagnostic-state-graphs.h".
	(checker_event::maybe_make_xml_state): Replace with...
	(checker_event::maybe_make_diagnostic_state_graph): ...this.
	* checker-event.h: Add include of "diagnostic-digraphs.h".
	(checker_event::maybe_make_xml_state): Replace decl with...
	(checker_event::maybe_make_diagnostic_state_graph): ...this.
	* engine.cc (exploded_node::on_stmt_pre): Replace
	"_analyzer_dump_xml" with "__analyzer_dump_sarif".
	* program-state.cc: Replace include of "diagnostic-state.h" with
	"diagnostic-state-graphs.h".
	(program_state::dump_dot): Port from XML to state graphs.
	* program-state.h: Drop reduntant forward decl of xml::document.
	(program_state::make_xml): Replace decl with...
	(program_state::make_diagnostic_state_graph): ...this.
	(program_state::dump_xml_to_pp): Drop decl.
	(program_state::dump_xml_to_file): Drop decl.
	(program_state::dump_xml): Drop decl.
	(program_state::dump_dump_sarif): New decl.
	* sm-malloc.cc (get_dynalloc_state_for_state): New.
	(malloc_state_machine::add_state_to_xml): Replace with...
	(malloc_state_machine::add_state_to_state_graph): ...this.
	* sm.cc (state_machine::add_state_to_xml): Replace with...
	(state_machine::add_state_to_state_graph): ...this.
	(state_machine::add_global_state_to_xml): Replace with...
	(state_machine::add_global_state_to_state_graph): ...this.
	* sm.h (class xml_state): Drop forward decl.
	(class analyzer_state_graph): New forward decl.
	(state_machine::add_state_to_xml): Replace decl with...
	(state_machine::add_state_to_state_graph): ...this.
	(state_machine::add_global_state_to_xml): Replace decl with...
	(state_machine::add_global_state_to_state_graph): ...this.

gcc/testsuite/ChangeLog:
	* gcc.dg/analyzer/state-diagram-1-sarif.py (test_xml_state):
	Rename to...
	(test_state_graph): ...this.  Port from XML to SARIF graphs.
	* gcc.dg/analyzer/state-diagram-1.c: Update sink option
	from "sarif:xml-state=yes" to "sarif:state-graphs=yes".
	* gcc.dg/analyzer/state-diagram-5-sarif.c: Likewise.
	* gcc.dg/analyzer/state-diagram-5-sarif.py: Drop import of ET.
	(test_nested_types_in_xml_state): Rename to...
	(test_nested_types_in_state_graph): ...this.  Port from XML to
	SARIF graphs.
	* gcc.dg/plugin/diagnostic-test-graphs-html.c: New test.
	* gcc.dg/plugin/diagnostic-test-graphs-html.py: New test script.
	* gcc.dg/plugin/diagnostic-test-graphs-sarif.c: New test.
	* gcc.dg/plugin/diagnostic-test-graphs-sarif.py: New test script.
	* gcc.dg/plugin/diagnostic-test-graphs.c: New test.
	* gcc.dg/plugin/diagnostic_plugin_test_graphs.cc: New test plugin.
	* gcc.dg/plugin/plugin.exp (plugin_test_list): Add the above.
	* lib/sarif.py (get_xml_state): Delete.
	(get_state_graph): New.
	(def get_state_node_attr): New.
	(get_state_node_kind): New.
	(get_state_node_name): New.
	(get_state_node_type): New.
	(get_state_node_value): New.
	* sarif-replay.dg/2.1.0-invalid/3.40.2-duplicate-node-id.sarif:
	New test.
	* sarif-replay.dg/2.1.0-invalid/3.41.4-unrecognized-node-id.sarif:
	New test.
	* sarif-replay.dg/2.1.0-valid/graphs-check-html.py: New test
	script.
	* sarif-replay.dg/2.1.0-valid/graphs-check-sarif-roundtrip.py: New
	test script.
	* sarif-replay.dg/2.1.0-valid/graphs.sarif: New test.

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