Fix DCP content font ID allocation to cope with DCPs that have multiple fonts

with the same name in the same reel (#2600).

Previously we had this id_for_font_in_reel() which would give an ID
of N_font-ID.  This means we got duplicate font IDs.

Here we replace that method with FontAllocator, which gives an ID of
N_font-ID for the first font and M_font-ID, where M is a number higher than
the highest reel index.  The idea is to support the required new IDs
without breaking exisiting projects.

There is some documentation of how it works  in doc/design/fonts

10 files changed, 286 insertions, 96 deletions

diff --git a/src/lib/dcp_content.cc b/src/lib/dcp_content.cc
index 770e5bfad..249eb47b5 100644
--- a/src/lib/dcp_content.cc
+++ b/src/lib/dcp_content.cc
@@ -280,14 +280,14 @@ DCPContent::examine (shared_ptr<const Film> film, shared_ptr<Job> job)
 	for (int i = 0; i < examiner->text_count(TextType::OPEN_SUBTITLE); ++i) {
 		auto c = make_shared<TextContent>(this, TextType::OPEN_SUBTITLE, TextType::OPEN_SUBTITLE);
 		c->set_language (examiner->open_subtitle_language());
-		add_fonts_from_examiner(c, examiner->fonts());
+		examiner->add_fonts(c);
 		new_text.push_back (c);
 	}
 
 	for (int i = 0; i < examiner->text_count(TextType::CLOSED_CAPTION); ++i) {
 		auto c = make_shared<TextContent>(this, TextType::CLOSED_CAPTION, TextType::CLOSED_CAPTION);
 		c->set_dcp_track (examiner->dcp_text_track(i));
-		add_fonts_from_examiner(c, examiner->fonts());
+		examiner->add_fonts(c);
 		new_text.push_back (c);
 	}
 
@@ -843,33 +843,6 @@ DCPContent::resolution () const
 
 
 void
-add_fonts_from_examiner(shared_ptr<TextContent> text, vector<vector<shared_ptr<Font>>> const & all_fonts)
-{
-	int reel_number = 0;
-	for (auto reel_fonts: all_fonts) {
-		for (auto font: reel_fonts) {
-			/* Each reel could have its own font with the same ID, so we disambiguate them here
-			 * by prepending the reel number.  We do the same disambiguation when emitting the
-			 * subtitles in the DCP decoder.
-			 */
-			auto font_copy = make_shared<dcpomatic::Font>(*font);
-			font_copy->set_id(id_for_font_in_reel(font->id(), reel_number));
-			text->add_font(font_copy);
-		}
-		++reel_number;
-	}
-
-}
-
-
-string
-id_for_font_in_reel(string id, int reel)
-{
-	return String::compose("%1_%2", reel, id);
-}
-
-
-void
 DCPContent::check_font_ids()
 {
 	if (text.empty()) {
@@ -877,7 +850,7 @@ DCPContent::check_font_ids()
 	}
 
 	DCPExaminer examiner(shared_from_this(), true);
-	add_fonts_from_examiner(text.front(), examiner.fonts());
+	examiner.add_fonts(text.front());
 }
 
 
diff --git a/src/lib/dcp_content.h b/src/lib/dcp_content.h
index fd78cd0ac..3753740a2 100644
--- a/src/lib/dcp_content.h
+++ b/src/lib/dcp_content.h
@@ -232,9 +232,4 @@ private:
 };
 
 
-extern std::string id_for_font_in_reel(std::string id, int reel);
-extern void add_fonts_from_examiner(std::shared_ptr<TextContent> text, std::vector<std::vector<std::shared_ptr<dcpomatic::Font>>> const& fonts);
-
-
-
 #endif
diff --git a/src/lib/dcp_decoder.cc b/src/lib/dcp_decoder.cc
index e72573ebc..0a57ce7f5 100644
--- a/src/lib/dcp_decoder.cc
+++ b/src/lib/dcp_decoder.cc
@@ -23,6 +23,7 @@
 #include "audio_content.h"
 #include "audio_decoder.h"
 #include "config.h"
+#include "constants.h"
 #include "dcp_content.h"
 #include "dcp_decoder.h"
 #include "digester.h"
@@ -136,6 +137,9 @@ DCPDecoder::DCPDecoder (shared_ptr<const Film> film, shared_ptr<const DCPContent
 
 	_reel = _reels.begin ();
 	get_readers ();
+
+	_font_id_allocator.add_fonts_from_reels(_reels);
+	_font_id_allocator.allocate();
 }
 
 
@@ -310,7 +314,7 @@ DCPDecoder::pass_texts (
 				}
 
 				dcp::SubtitleString is_copy = *is;
-				is_copy.set_font(id_for_font_in_reel(is_copy.font().get_value_or(""), _reel - _reels.begin()));
+				is_copy.set_font(_font_id_allocator.font_id(_reel - _reels.begin(), asset->id(), is_copy.font().get_value_or("")));
 				strings.push_back(is_copy);
 			}
 
diff --git a/src/lib/dcp_decoder.h b/src/lib/dcp_decoder.h
index 803c93a86..2c0cd8f41 100644
--- a/src/lib/dcp_decoder.h
+++ b/src/lib/dcp_decoder.h
@@ -26,6 +26,7 @@
 
 #include "atmos_metadata.h"
 #include "decoder.h"
+#include "font_id_allocator.h"
 #include <dcp/mono_picture_asset_reader.h>
 #include <dcp/stereo_picture_asset_reader.h>
 #include <dcp/sound_asset_reader.h>
@@ -106,4 +107,6 @@ private:
 	boost::optional<int> _forced_reduction;
 
 	std::string _lazy_digest;
+
+	FontIDAllocator _font_id_allocator;
 };
diff --git a/src/lib/dcp_examiner.cc b/src/lib/dcp_examiner.cc
index 3163f59c4..a9a6dee5e 100644
--- a/src/lib/dcp_examiner.cc
+++ b/src/lib/dcp_examiner.cc
@@ -20,11 +20,13 @@
 
 
 #include "config.h"
+#include "constants.h"
 #include "dcp_content.h"
 #include "dcp_examiner.h"
 #include "dcpomatic_log.h"
 #include "exceptions.h"
 #include "image.h"
+#include "text_content.h"
 #include "util.h"
 #include <dcp/cpl.h>
 #include <dcp/dcp.h>
@@ -128,9 +130,9 @@ DCPExaminer::DCPExaminer (shared_ptr<const DCPContent> content, bool tolerant)
 
 	LOG_GENERAL("Looking at %1 reels", selected_cpl->reels().size());
 
+	int reel_index = 0;
 	for (auto reel: selected_cpl->reels()) {
 		LOG_GENERAL("Reel %1", reel->id());
-		vector<shared_ptr<dcpomatic::Font>> reel_fonts;
 
 		if (reel->main_picture()) {
 			if (!reel->main_picture()->asset_ref().resolved()) {
@@ -205,8 +207,12 @@ DCPExaminer::DCPExaminer (shared_ptr<const DCPContent> content, bool tolerant)
 			_text_count[TextType::OPEN_SUBTITLE] = 1;
 			_open_subtitle_language = try_to_parse_language(reel->main_subtitle()->language());
 
-			for (auto const& font: reel->main_subtitle()->asset()->font_data()) {
-				reel_fonts.push_back(make_shared<dcpomatic::Font>(font.first, font.second));
+			auto asset = reel->main_subtitle()->asset();
+			for (auto const& font: asset->font_data()) {
+				_fonts.push_back({reel_index, asset->id(), make_shared<dcpomatic::Font>(font.first, font.second)});
+			}
+			if (asset->font_data().empty()) {
+				_fonts.push_back({reel_index, asset->id(), make_shared<dcpomatic::Font>("")});
 			}
 		}
 
@@ -232,8 +238,12 @@ DCPExaminer::DCPExaminer (shared_ptr<const DCPContent> content, bool tolerant)
 
 			LOG_GENERAL("Closed caption %1 of reel %2 found", ccap->id(), reel->id());
 
-			for (auto const& font: ccap->asset()->font_data()) {
-				reel_fonts.push_back(make_shared<dcpomatic::Font>(font.first, font.second));
+			auto asset = ccap->asset();
+			for (auto const& font: asset->font_data()) {
+				_fonts.push_back({reel_index, asset->id(), make_shared<dcpomatic::Font>(font.first, font.second)});
+			}
+			if (asset->font_data().empty()) {
+				_fonts.push_back({reel_index, asset->id(), make_shared<dcpomatic::Font>("")});
 			}
 		}
 
@@ -263,11 +273,7 @@ DCPExaminer::DCPExaminer (shared_ptr<const DCPContent> content, bool tolerant)
 			_reel_lengths.push_back(reel->atmos()->actual_duration());
 		}
 
-		if (reel_fonts.empty()) {
-			reel_fonts.push_back(make_shared<dcpomatic::Font>(""));
-		}
-
-		_fonts.push_back(reel_fonts);
+		++reel_index;
 	}
 
 	_encrypted = selected_cpl->any_encrypted();
@@ -355,3 +361,21 @@ DCPExaminer::DCPExaminer (shared_ptr<const DCPContent> content, bool tolerant)
 
 	_cpl = selected_cpl->id();
 }
+
+
+void
+DCPExaminer::add_fonts(shared_ptr<TextContent> content)
+{
+	for (auto const& font: _fonts) {
+		_font_id_allocator.add_font(font.reel_index, font.asset_id, font.font->id());
+	}
+
+	_font_id_allocator.allocate();
+
+	for (auto const& font: _fonts) {
+		auto font_copy = make_shared<dcpomatic::Font>(*font.font);
+		font_copy->set_id(_font_id_allocator.font_id(font.reel_index, font.asset_id, font.font->id()));
+		content->add_font(font_copy);
+	}
+}
+
diff --git a/src/lib/dcp_examiner.h b/src/lib/dcp_examiner.h
index 1a3615867..54e283548 100644
--- a/src/lib/dcp_examiner.h
+++ b/src/lib/dcp_examiner.h
@@ -27,6 +27,7 @@
 #include "audio_examiner.h"
 #include "dcp_text_track.h"
 #include "dcpomatic_assert.h"
+#include "font_id_allocator.h"
 #include "video_examiner.h"
 #include <dcp/dcp_time.h>
 #include <dcp/rating.h>
@@ -173,10 +174,7 @@ public:
 		return _atmos_edit_rate;
 	}
 
-	/** @return fonts in each reel */
-	std::vector<std::vector<std::shared_ptr<dcpomatic::Font>>> fonts() const {
-		return _fonts;
-	}
+	void add_fonts(std::shared_ptr<TextContent> content);
 
 private:
 	boost::optional<double> _video_frame_rate;
@@ -211,5 +209,20 @@ private:
 	bool _has_atmos = false;
 	Frame _atmos_length = 0;
 	dcp::Fraction _atmos_edit_rate;
-	std::vector<std::vector<std::shared_ptr<dcpomatic::Font>>> _fonts;
+
+	struct Font
+	{
+		Font(int reel_index_, std::string asset_id_, std::shared_ptr<dcpomatic::Font> font_)
+			: reel_index(reel_index_)
+			, asset_id(asset_id_)
+			, font(font_)
+		{}
+
+		int reel_index;
+		std::string asset_id;
+		std::shared_ptr<dcpomatic::Font> font;
+	};
+
+	std::vector<Font> _fonts;
+	FontIDAllocator _font_id_allocator;
 };
diff --git a/src/lib/font_id_allocator.cc b/src/lib/font_id_allocator.cc
new file mode 100644
index 000000000..ef25dc642
--- /dev/null
+++ b/src/lib/font_id_allocator.cc
@@ -0,0 +1,119 @@
+/*
+    Copyright (C) 2023 Carl Hetherington <cth@carlh.net>
+
+    This file is part of DCP-o-matic.
+
+    DCP-o-matic 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 2 of the License, or
+    (at your option) any later version.
+
+    DCP-o-matic 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 DCP-o-matic.  If not, see <http://www.gnu.org/licenses/>.
+
+*/
+
+
+#include "compose.hpp"
+#include "constants.h"
+#include "dcpomatic_assert.h"
+#include "font_id_allocator.h"
+#include <dcp/reel.h>
+#include <dcp/reel_closed_caption_asset.h>
+#include <dcp/reel_subtitle_asset.h>
+#include <dcp/subtitle_asset.h>
+#include <set>
+#include <string>
+#include <vector>
+
+
+using std::shared_ptr;
+using std::set;
+using std::string;
+using std::vector;
+
+
+void
+FontIDAllocator::add_fonts_from_reels(vector<shared_ptr<dcp::Reel>> const& reels)
+{
+	int reel_index = 0;
+	for (auto reel: reels) {
+		if (auto sub = reel->main_subtitle()) {
+			add_fonts_from_asset(reel_index, sub->asset());
+		}
+
+		for (auto ccap: reel->closed_captions()) {
+			add_fonts_from_asset(reel_index, ccap->asset());
+		}
+
+		++reel_index;
+	}
+}
+
+
+void
+FontIDAllocator::add_fonts_from_asset(int reel_index, shared_ptr<const dcp::SubtitleAsset> asset)
+{
+	for (auto const& font: asset->font_data()) {
+		_map[Font(reel_index, asset->id(), font.first)] = 0;
+	}
+
+	if (asset->font_data().empty()) {
+		_map[Font(reel_index, asset->id(), "")] = 0;
+	}
+}
+
+
+void
+FontIDAllocator::add_font(int reel_index, string asset_id, string font_id)
+{
+	_map[Font(reel_index, asset_id, font_id)] = 0;
+}
+
+
+void
+FontIDAllocator::allocate()
+{
+	/* Last reel index that we have; i.e. the last prefix number that would be used by "old"
+	 * font IDs (i.e. ones before this FontIDAllocator was added and used)
+	 */
+	auto const last_reel = std::max_element(
+		_map.begin(),
+		_map.end(),
+		[] (std::pair<Font, int> const& a, std::pair<Font, int> const& b) {
+			return a.first.reel_index < b.first.reel_index;
+		})->first.reel_index;
+
+	/* Number of times each ID has been used */
+	std::map<string, int> used_count;
+
+	for (auto& font: _map) {
+		auto const proposed = String::compose("%1_%2", font.first.reel_index, font.first.font_id);
+		if (used_count.find(proposed) != used_count.end()) {
+			/* This ID was already used; we need to disambiguate it.  Do so by using
+			 * an ID above last_reel
+			 */
+			font.second = last_reel + used_count[proposed];
+			++used_count[proposed];
+		} else {
+			/* This ID was not yet used */
+			used_count[proposed] = 1;
+			font.second = font.first.reel_index;
+		}
+	}
+}
+
+
+string
+FontIDAllocator::font_id(int reel_index, string asset_id, string font_id) const
+{
+	auto iter = _map.find(Font(reel_index, asset_id, font_id));
+	DCPOMATIC_ASSERT(iter != _map.end());
+	return String::compose("%1_%2", iter->second, font_id);
+}
+
diff --git a/src/lib/font_id_allocator.h b/src/lib/font_id_allocator.h
new file mode 100644
index 000000000..bd99cad63
--- /dev/null
+++ b/src/lib/font_id_allocator.h
@@ -0,0 +1,102 @@
+/*
+    Copyright (C) 2023 Carl Hetherington <cth@carlh.net>
+
+    This file is part of DCP-o-matic.
+
+    DCP-o-matic 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 2 of the License, or
+    (at your option) any later version.
+
+    DCP-o-matic 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 DCP-o-matic.  If not, see <http://www.gnu.org/licenses/>.
+
+*/
+
+
+#ifndef DCPOMATIC_FONT_ID_ALLOCATOR_H
+#define DCPOMATIC_FONT_ID_ALLOCATOR_H
+
+
+#include <map>
+#include <memory>
+#include <string>
+#include <vector>
+
+
+namespace dcp {
+	class Reel;
+	class SubtitleAsset;
+}
+
+
+/** A class which, given some pairs of (asset-id, font-id) can return a font ID
+ *  which is unique in a piece of content.
+ *
+ *  When we examine a 2-reel DCP we may have a pair of subtitle assets that
+ *  each have a font with ID "foo".  We want to store these in
+ *  TextContent::_fonts in such a way that they are distinguishable.
+ *
+ *  If TextContent is to carry on storing a list of dcpomatic::Font, we can
+ *  only do this by making each dcpomatic::Font have a different ID (i.e. not
+ *  both "foo").
+ *
+ *  Hence when we add the fonts to the TextContent we re-write them to have
+ *  unique IDs.
+ *
+ *  When we do this, we must do it in a repeatable way so that when the
+ *  DCPDecoder receives the "foo" font IDs it can obtain the same "new" ID given
+ *  "foo" and the asset ID that it came from.
+ *
+ *  FontIDAllocator can help with that: call add_fonts_from_reels() or add_font(),
+ *  then allocate(), then it will return repeatable unique "new" font IDs from
+ *  an asset map and "old" ID.
+ */
+class FontIDAllocator
+{
+public:
+	void add_fonts_from_reels(std::vector<std::shared_ptr<dcp::Reel>> const& reels);
+	void add_font(int reel_index, std::string asset_id, std::string font_id);
+
+	void allocate();
+
+	std::string font_id(int reel_index, std::string asset_id, std::string font_id) const;
+
+private:
+	void add_fonts_from_asset(int reel_index, std::shared_ptr<const dcp::SubtitleAsset> asset);
+
+	struct Font
+	{
+		Font(int reel_index_, std::string asset_id_, std::string font_id_)
+			: reel_index(reel_index_)
+			, asset_id(asset_id_)
+			, font_id(font_id_)
+		{}
+
+		bool operator<(Font const& other) const {
+			if (reel_index != other.reel_index) {
+				return reel_index < other.reel_index;
+			}
+
+			if (asset_id != other.asset_id) {
+				return asset_id < other.asset_id;
+			}
+
+			return font_id < other.font_id;
+		}
+
+		int reel_index;
+		std::string asset_id;
+		std::string font_id;
+	};
+
+	std::map<Font, int> _map;
+};
+
+
+#endif
diff --git a/src/lib/writer.cc b/src/lib/writer.cc
index 6bc3da504..9ab3d4e1e 100644
--- a/src/lib/writer.cc
+++ b/src/lib/writer.cc
@@ -875,53 +875,9 @@ Writer::write (vector<shared_ptr<Font>> fonts)
 		}
 		_chosen_interop_font = fonts[0];
 	} else {
-		set<string> used_ids;
-
-		/* Return the index of a _N at the end of a string, or string::npos */
-		auto underscore_number_position = [](string s) {
-			auto last_underscore = s.find_last_of("_");
-			if (last_underscore == string::npos) {
-				return string::npos;
-			}
-
-			for (auto i = last_underscore + 1; i < s.size(); ++i) {
-				if (!isdigit(s[i])) {
-					return string::npos;
-				}
-			}
-
-			return last_underscore;
-		};
-
-		/* Write fonts to _fonts, changing any duplicate IDs so that they are unique */
 		for (auto font: fonts) {
-			auto id = fix_id(font->id());
-			if (used_ids.find(id) == used_ids.end()) {
-				/* This ID is unique so we can just use it as-is */
-				_fonts.put(font, id);
-				used_ids.insert(id);
-			} else {
-				auto end = underscore_number_position(id);
-				if (end == string::npos) {
-					/* This string has no _N suffix, so add one */
-					id += "_0";
-					end = underscore_number_position(id);
-				}
-
-				++end;
-
-				/* Increment the suffix until we find a unique one */
-				auto number = dcp::raw_convert<int>(id.substr(end));
-				while (used_ids.find(id) != used_ids.end()) {
-					++number;
-					id = String::compose("%1_%2", id.substr(0, end - 1), number);
-				}
-				used_ids.insert(id);
-			}
-			_fonts.put(font, id);
+			_fonts.put(font, fix_id(font->id()));
 		}
-
-		DCPOMATIC_ASSERT(_fonts.map().size() == used_ids.size());
 	}
 }
 
diff --git a/src/lib/wscript b/src/lib/wscript
index 251f09cf7..56ffc39fe 100644
--- a/src/lib/wscript
+++ b/src/lib/wscript
@@ -119,6 +119,7 @@ sources = """
           filter.cc
           font.cc
           font_config.cc
+          font_id_allocator.cc
           font_id_map.cc
           frame_interval_checker.cc
           frame_rate_change.cc