This function was calling `realloc` and not checking the return value. To fix
this, we rephrase it into using string views and then a final checked
allocation. This removes the long lived static allocation here, now requiring
the caller to free the returned value. This function is not on a hot path, so
removing this optimization is fine.
ccomps process: replace 'sprintf' with 'agxbprint'
This replaces some error prone manual calculation with a dynamic buffer that
handles the calculation of needed allocations. This also potentially saves
memory in cases of short strings where an agxbuf can use inline storage.
ccomps processClusters: replace 'sprintf' with 'agxbprint'
This replaces some error prone manual calculation with a dynamic buffer that
handles the calculation of needed allocations. This also potentially saves
memory in cases of short strings where an agxbuf can use inline storage.
ccomps gwrite: fix crash when failing to open files
This code looks as if it and the similar code in bcomps.c were copy-pasted from
the same common source. Except the bcomps.c version remembered to exit when
failing to open the output file, whereas the ccomps.c code would go on to crash
when using the null `outf`.
It looks like a mistake in the initial revision of Graphviz that this function
never wrote to `bufsz`. The effect of this was that this function would
reallocate on every single call. So empirically it seems there was no need to
avoid allocating new memory on each call, which is what this commit does.
smyrna DrawEllipse: use doubles for local temporaries
Values being stored into these were doubles and later use of these promoted them
to double. So it is not clear why they were not double to begin with. Squashes 2
-Wfloat-conversion warnings.
Most of the calculations with this and uses of it are with doubles. So making it
a double as well avoids losing intermediate precision. Squashes 5
-Wfloat-conversion warnings.
Link-Time Optimization (LTO) is a mechanism that enables the compiler to
optimize across translation unit boundaries. In particular, it enables
cross-file function inlining. This is present and mature in the majority of
contemporary compilers and switching it on has few downsides.
¹ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1652 run as
`neato -Tsvg -o /dev/null 1652.dot`.
² swedish-flat.dot Magnus attached to
https://gitlab.com/graphviz/graphviz/-/issues/1718 run as
`circo -Tsvg -o /dev/null swedish-flag.dot`.
³ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1864 run as
`twopi -Tsvg -o /dev/null 1864.dot`.
⁴ The test case from https://gitlab.com/graphviz/graphviz/-/issues/2064 run as
`dot -Gnslimit=2 -Gnslimit1=2 -Gmaxiter=5000 -Tsvg -o /dev/null 2064.dot`.
⁵ The tests/2095.dot test case from prior to minimization
(3819821ea70fae730dd224936628ed3929b03531). Run as
`dot -Tsvg -o /dev/null 2095.dot`.
pathplan: replace unchecked allocation calls with cgraph wrappers
After the prior UB fixes, the #1999 example bottoms out in this code, failing
the second allocation call while trying to allocate ~938GB. The return values
for neither of these calls were checked, resulting in messy crashes when
scenarios like this occurred. This change swaps them for calls to the cgraph
allocation wrappers that exit gracefully on out-of-memory conditions.
After this change, a ASan+UBSan build of Graphviz can process the #1999 example
without crashing. Graphs with >46341 (⌈√INT_MAX⌉) nodes no longer cause an
integer overflow.
UBSan revealed the graph attached to #1999 was triggering an integer overflow in
this multiplication, later on causing a crash in `twopi`. Any number of nodes
≥⌈√INT_MAX⌉ exceeds INT_MAX during multiplication. This fix still does not
enable the graph to be processed in a reasonable amount of time, and it still
crashes later after several hours due to another integer overflow.
ortho: use zero initialization for 'boxf' variables
This was phrased as `{{0}}` to avoid a compiler warning on CentOS 7 about the
LHS being a nested struct. However it turns out this is a false positive in
older versions of GCC, and this form of zero initialization should be valid for
any aggregate in C99. Accordingly _newer_ versions of GCC warn if you use this
double braced phrasing. This change switches to the more standard C99
initialization, squashing warnings on newer platforms at the expense of
reintroducing some warnings on CentOS 7.
sparse Multilevel_MQ_Clustering_establish: replace linked-list with generic list
Linked-lists are a common option for implementing dynamic arrays in C. However
on contemporary platforms they have poor performance characteristics. The need
to allocate on every element addition and the pointer chasing involved in
traversing the list pollutes caches and degrades branch prediction.
This change swaps the use of a linked-list for a contiguous array that is
expanded on demand in the manner of C++’s `std::vector`. Traversal is cheap and
the amortized element addition cost is low.
The previous code prepended to linked-lists and then traversed them from
beginning to end. The new code flips this and appends to the lists and then
traverses them from end to beginning in order to preserve the ordering.
While making this change, we also replace the use of a common/memory.h
allocation wrapper with a cgraph/alloc.h one.