Reference counting issues with xlnt::format_impl

[YurkoFlisk]

There seem to be some problems regarding reference counting implementation for xlnt::format_impl which manifest themselves, particularly when loading an XLSX document where some cells share the same style. E.g. the following crashes in Debug mode in VS for a simple sheet containing two same-style cells A1 and B1:

#include <xlnt/xlnt.hpp>

int main()
{
	using namespace xlnt;

	workbook wb(path("test.xlsx"));
	worksheet sheet(wb.sheet_by_index(0));
	sheet[{1u, 1u}].fill(fill::solid(color::green())); // 1
	sheet[{2u, 1u}].fill(fill::solid(color::green())); // 2 (Crashes here)
	return 0;
}

test.xlsx
Debugging showed that the crash happens on statement 2 due to reading deleted memory at line 447 here (which in this case for me was caused by length exception during attempted std::string copying):

xlnt/source/detail/implementations/stylesheet.hpp

Lines 445 to 455 in 297b331

	format_impl *find_or_create_with(format_impl *pattern, const fill &new_fill, optional<bool> applied)
	{
	format_impl new_format = *pattern;
	new_format.fill_id = find_or_add(fills, new_fill);
	new_format.fill_applied = applied;
	if (pattern->references == 0)
	{
	*pattern = new_format;
	}
	return find_or_create(new_format);
	}

called from here:

xlnt/source/styles/format.cpp

Lines 108 to 112 in 297b331

	format format::fill(const xlnt::fill &new_fill, optional<bool> applied)
	{
	d_ = d_->parent->find_or_create_with(d_, new_fill, applied);
	return format(d_);
	}

which is called from here:

xlnt/source/cell/cell.cpp

Lines 682 to 686 in 297b331

	void cell::fill(const class fill &fill_)
	{
	auto new_format = has_format() ? modifiable_format() : workbook().create_format();
	format(new_format.fill(fill_, optional<bool>(true)));
	}

This happens because at statement 1 the format_impl object shared between the two cells (which pattern refers to above) gets destroyed during garbage_collect here:

xlnt/source/detail/implementations/stylesheet.hpp

Lines 379 to 408 in 297b331

	format_impl *find_or_create(format_impl &pattern)
	{
	pattern.references = 0;
	std::size_t id = 0;
	auto iter = format_impls.begin();
	while (iter != format_impls.end() && !(*iter == pattern))
	{
	++id;
	++iter;
	}
	if (iter == format_impls.end())
	{
	iter = format_impls.emplace(format_impls.end(), pattern);
	}
	auto &result = *iter;
	result.parent = this;
	result.id = id;
	result.references++;
	if (id != pattern.id)
	{
	iter = format_impls.begin();
	std::advance(iter, static_cast<std::list<format_impl>::difference_type>(pattern.id));
	iter->references -= iter->references > 0 ? 1 : 0;
	garbage_collect();
	}
	return &result;
	}

This happens because iter->references was initially 1 instead of 2, so it gets 0 before call to garbage_collect above. In fact, all format_impl's have reference count 1 after loading because it is only incremented during format creation during stylesheet parsing:

xlnt/source/detail/serialization/xlsx_consumer.cpp

Lines 2943 to 2971 in 297b331

	std::size_t record_index = 0;
	for (const auto &record : format_records)
	{
	stylesheet.format_impls.push_back(format_impl());
	auto &new_format = stylesheet.format_impls.back();
	new_format.id = record_index++;
	new_format.parent = &stylesheet;
	++new_format.references;
	new_format.alignment_id = record.first.alignment_id;
	new_format.alignment_applied = record.first.alignment_applied;
	new_format.border_id = record.first.border_id;
	new_format.border_applied = record.first.border_applied;
	new_format.fill_id = record.first.fill_id;
	new_format.fill_applied = record.first.fill_applied;
	new_format.font_id = record.first.font_id;
	new_format.font_applied = record.first.font_applied;
	new_format.number_format_id = record.first.number_format_id;
	new_format.number_format_applied = record.first.number_format_applied;
	new_format.protection_id = record.first.protection_id;
	new_format.protection_applied = record.first.protection_applied;
	new_format.pivot_button_ = record.first.pivot_button_;
	new_format.quote_prefix_ = record.first.quote_prefix_;
	set_style_by_xfid(styles, record.second, new_format.style);
	}

... but not when cells using it are added:

xlnt/source/detail/serialization/xlsx_consumer.cpp

Lines 848 to 901 in 297b331

	auto impl = detail::cell_impl();
	for (Cell &cell : ws_data.parsed_cells)
	{
	impl.parent_ = current_worksheet_;
	impl.column_ = cell.ref.column;
	impl.row_ = cell.ref.row;
	detail::cell_impl *ws_cell_impl = &current_worksheet_->cell_map_.emplace(cell_reference(impl.column_, impl.row_), std::move(impl)).first->second;
	if (cell.style_index != -1)
	{
	ws_cell_impl->format_ = target_.format(static_cast<size_t>(cell.style_index)).d_;
	}
	if (cell.cell_metatdata_idx != -1)
	{
	}
	ws_cell_impl->phonetics_visible_ = cell.is_phonetic;
	if (!cell.formula_string.empty())
	{
	ws_cell_impl->formula_ = cell.formula_string[0] == '=' ? cell.formula_string.substr(1) : std::move(cell.formula_string);
	}
	if (!cell.value.empty())
	{
	ws_cell_impl->type_ = cell.type;
	switch (cell.type)
	{
	case cell::type::boolean: {
	ws_cell_impl->value_numeric_ = is_true(cell.value) ? 1.0 : 0.0;
	break;
	}
	case cell::type::empty:
	case cell::type::number:
	case cell::type::date: {
	ws_cell_impl->value_numeric_ = converter_.deserialise(cell.value);
	break;
	}
	case cell::type::shared_string: {
	ws_cell_impl->value_numeric_ = static_cast<double>(strtol(cell.value.c_str(), nullptr, 10));
	break;
	}
	case cell::type::inline_string: {
	ws_cell_impl->value_text_ = std::move(cell.value);
	break;
	}
	case cell::type::formula_string: {
	ws_cell_impl->value_text_ = std::move(cell.value);
	break;
	}
	case cell::type::error: {
	ws_cell_impl->value_text_.plain_text(cell.value, false);
	break;
	}
	}
	}
	}
	stack_.pop_back();

So, this explains how crash happens due to use-after-free at statement 2 . However, there is a use-after-free even earlier, while still executing statement 1, which doesn't cause crash probably because it only changes a reference counter inside deleted format_impl. It happens when that reference counter is decremented for the second time (first time it happens in find_or_create during new_format.fill(...) in cell::fill which results in garbage collection explained above), now inside cell::format:

xlnt/source/cell/cell.cpp

Lines 756 to 765 in 297b331

	void cell::format(const class format new_format)
	{
	if (has_format())
	{
	format().d_->references -= format().d_->references > 0 ? 1 : 0;
	}
	++new_format.d_->references;
	d_->format_ = new_format.d_;
	}

where has_format returns true because cell_impl's pointer to (now-deleted) format_impl was never cleared. Note that it also increments reference counter of the new format_impl for the second time (first time it also happens in find_or_create).

So, summing up, if format references are supposed to represent how many cells use a particular format, they do so incorrectly now. At least, during loading from file the increments for these references should happen when cells use a format, not when that format is loaded. Also, double reference count increase/decrease is semantically wrong, even if it sometimes just cancels out, and can cause uncaught use-after-free, so there should be consistency about where reference counting happens. It can probably be resolved using the existing system, but I think the least error-prone solution is to get rid of manual reference counting and rewrite the code to use standard C++ smart pointers. I.e. std::shared_ptr<xlnt::format_impl> instead of xlnt::optional<xlnt::format_impl*> as a pointer to format_impl, while format_impls list would then be std::list<std::weak_ptr<xlnt::format_impl>> instead of std::list<xlnt::format_impl>. Though there would be no need to make format_impls iterator-stable, so std::vector could be considered instead of list for the latter. Also note that std::shared_prt will take care of destroying xlnt::format_impl, so when the new garbage_collect will "collect" an expired std::weak_ptr, it will just destroy the control block, and as for deallocation, it depends on whether a single chunk for control block and managed object was allocated (using std::allocate_shared; then it as a whole is deallocated when control block is with the destruction of the last std::weak_ptr) or separate ones (using std::shared_ptr constructors; then memory allocated for managed object is deallcoated when reference count in control block drops to zero and the control block is destroyed/deallocated when the last std::weak_ptr destroys).