TOC for documents

[letsfindaway]

Problem

Currently, the table of contents (TOC) of an OpenBoard document only consists of the file names, which must always be numbered in ascending order without gaps. When inserting or deleting pages in a huge document, lots of files need to be renamed, which leads to serious delays, especially when using a network drive.

Proposal

The idea is now to decouple the file names from the sequence of pages by using a TOC. The individual page files never get renamed. Instead, just the entries in the TOC are updated.

The TOC also offers additional benefits for future features:

• It could serve as a container storing page names, so that we can offer named pages instead of just numbers.
• It could contain bookmarks to specific pages to ease navigation.
• It could contain a list of referenced media files, thus giving an overview at a single place.

The structure of the TOC is just a list of pages, containing various attributes. In a first step the only attribute might be the real file name of a page. Other attributes can be added later.

Serialization

As the TOC is relevant for understanding the document, it must be flushed to disk after any modification. That means that it is beneficial when serializing the TOC is fast and the data format is compact. Besides that, there are many data formats which could be used. Just to name a few, which are natively supported by Qt Core:

• XML
• JSON
• CBOR
• DataStream

See also https://doc.qt.io/qt-6/qtserialization.html for an overview of Qt serialization mechanisms including a discussion on advantages.

Version compatibility

To provide upward compatibility OpenBoard can simply add a TOC if it opens a document without that file. It just enumerates the existing pages in numerical order. and adds no other page attributes.

Providing downward compatibility is more difficult:

• When deleting a page, it will just be removed from the TOC and the associated files are deleted, leaving a gap in numbering. The current OpenBoard would stop scanning pages at the gap.

We could however provide an "Export as..." option for UBZ files creating the current format without TOC. This will definitely help with the page sequence. However additional attributes stored in the TOC will be lost. Alternatively we could try to make a compatible export version by renumbering the pages during creation of the compressed file AND updating the TOC accordingly and store both in the exported UBZ file. The resulting file will be compatible without loosing additional attributes.

Implementation

The PR OpenBoard-org#1162 offers a good base for adding a TOC, as it introduces a UBDocument class, which handles adding, removing and moving of pages. The TOC will however not directly be attached to that class, but to the UBPersistenceManager, which provides functions to retrieve file names for a page index. Other classes which need the file names will always use those functions.

Edit After longer considerations I now tend to attach the TOC to UBDocument:

• The lifetime of document and TOC are the same: when the document is no longer needed, we also can drop the TOC in memory.
• We will also move the scene cache to the document. There is no need to access a scene when we don't have the document. Scene cache remains at the persistence manager, as there are functions (especially deleting all pages of a document) which do not require an existing UBDocument instance.
• The API of the persistence manager should then use file names instead of indexes.
• The responsibility of the persistence manager will then just be file handling. The document class handles the structure of the document.

An implementation of the TOC should separate the TOC itself and the serialization of the TOC, so that the serialization format can easily be switched. No serialization specific classes must appear on the API of the TOC.

[letsfindaway]

Performance of serialization

I made some first experiments with serialization to JSON and CBOR. The results for a 2000 pages document are as follows:

Format	Time	Size
JSON (compact)	2.4 ms	104 kByte
CBOR	0.9 ms	83 kBytes

So the benefit in compactness for CBOR it not much, as most data are just strings, which have the same size in JSON and CBOR. Of course serialization is faster with CBOR, but JSON is still not a problem.

Note that this is for compact JSON (single line, no spaces) and pretty printed JSON would be larger (141 kByte with an indentation of 2 spaces per level).

[kaamui]

I think pretty printed JSON should be preferred unless you anticipate it to be a potential performance issue.

[letsfindaway]

Class responsibilities and sequence of refactoring

Work split of UBDocument and UBPersistenceManager

UBPersistenceManager

Its role is data I/O. It does not have to know much about the document.

• File handling
• Directory scanning
• Asynchronous loading and saving

UBDocument

Its role is document handling. It does not have to know much about persistence.

• TOC handling
• Page count (moved from proxy)
• Scene cache (moved from PM)
• Thumbnails

Sequence for refactoring

Many things now depend on each other. Best sequence for refactoring:

• Move pageCount and related functions to UBDocument.
• Scan TOC for highest page number.
• Move scene cache to UBDocument. cache remains at the PM.
• Refactor functions of PM only used by UBDocument to use file names instead of indexes.
• At the same time, add TOC handling where the PM renamed files.
• At the same time, add scene cache management when inserting/deleting/moving pages.

[kaamui]

Alternatively we could try to make a compatible export version by renumbering the pages during creation of the compressed file AND updating the TOC accordingly and store both in the exported UBZ file. The resulting file will be compatible without loosing additional attributes.

Good idea. However, in our context, where the files are stored on a shared disk, it doesn't help, because you can have multiple version of OpenBoard that access the same folder. With this change, I'll have to make clear that we can't accept older version to persist in some machines anymore. it will be OK after that, but the release containing this change will force our schools to transition quickly and on every machine.

I'll discuss it internally with the deploy team to see how much of an issue it could be.

[letsfindaway]

And here another transition strategy:

We introduce a configuration flag

[App]
KeepPagesSequential=true|false

Initially we set this flag to true. This means:

• If a TOC is found, then it is used to get page file names. This assures that we can handle documents created or modified with this flag set to false (See phase two below).
• If that TOC is fully sequential or If no TOC is found, then a TOC is created based on the existing pages. This assures that we can handle documents created or modified with previous versions of OpenBoard, where potentially pages have been inserted or removed without updating the TOC.
• When pages are inserted, deleted or moved, the page files are still renamed as before. The TOC is updated accordingly.

In this phase, we have no performance advantage, but just make sure that we have a smooth transition.

When we know that all OpenBoard instances are updated to the new version, then we can set this flag to false. Then we work completely using the TOC:

• If no TOC is found, one is created based on the pages found.
• When pages are inserted, deleted or moved, the page files are not renamed, but instead the TOC is updated accordingly.

In this phase we additionally have the performance benefit.

So this means we have two steps in the transition, but both can take any time needed.

[letsfindaway]

A big problem of this approach is that we cannot clean-up the architecture as we want. E.g. with TOC, it would be much more natural to have the scene cache indexed by the scene name instead of the scene index, because this avoids shifting scenes in the cache when inserting, deleting or moving scenes.

However if we keep renaming the files (at least as an option), we either have to implement code to rename the keys of the scene cache entries or we have to keep the index as the key for the cache. Both is not my favorite, but the first option is definitely better.

[letsfindaway]

Alternatively we could try to make a compatible export version by renumbering the pages during creation of the compressed file AND updating the TOC accordingly and store both in the exported UBZ file. The resulting file will be compatible without loosing additional attributes.

Good idea. However, in our context, where the files are stored on a shared disk, it doesn't help, because you can have multiple version of OpenBoard that access the same folder. With this change, I'll have to make clear that we can't accept older version to persist in some machines anymore. it will be OK after that, but the release containing this change will force our schools to transition quickly and on every machine.

I'll discuss it internally with the deploy team to see how much of an issue it could be.

Another question: How do you avoid that the same document is accessed - and potentially modified - by multiple instances of OpenBoard at the same time? Wouldn't it be necessary (or at least helpful) to add a locking mechanism?

Typically programs create a .lock file when opening a document and delete it again when releasing it. When the .lock file exists, other instances at least display a warning dialog.

[letsfindaway]

Currently the KeepPagesSequential flag seems to be a good approach for me. There is still a big benefit compared to the current behavior:

• When inserting a page at the beginning of a large document we currently have no choice and must wait until all pages are renamed, because the file name for the new scene would not be "available" before that.
• With the TOC approach and that flag, we can start with just assigning an arbitrary number to the new page. The user can immediately start working with that page. We can then rename pages and update the TOC accordingly in the background.

This means we can define some "scrubbing" task executed afterwards, similar to the idea of a scrubbing job here: #204 (reply in thread). This task performs renaming and updating TOC in small steps. After each step or after a certain number of steps, the TOC is written to disk to guarantee a consistent document.

When the user does another document manipulation while the scrubbing task was not finished, then we can simply abort it an restart it again.

The steps of the scrubbing task need locking against document manipulations (add, move, delete page, but also load and save page, as the file names are about to change), but not against any other work with the pages. We also need to make sure that the document is consistent when terminating the application. It would be best to make sure that all scrubbing tasks are finished. But it might be that we cannot guarantee that. Then at least the TOC should be saved in a consistent state.

[kaamui]

Another question: How do you avoid that the same document is accessed - and potentially modified - by multiple instances of OpenBoard at the same time? Wouldn't it be necessary (or at least helpful) to add a locking mechanism?

We don't. Not a possible use case for us. A locking mechanism seems to be a good idea, but the need is not there at this point.

[letsfindaway]

Concurrent with these considerations I'm also experimenting with some refactorings to see what consequences this has to other code. During this work, I repeatedly stumble across #198, the multiple and slightly different implementations for copying a scene. One example is the deletion of pages. Here we have again an implementation to copy pages in ?UBPersistenceManager::deleteDocumentScenes() to copy the deleted scenes to a trash document. So when I refactor this function to work with the TOC, I also have to touch this code.

I have the feeling that we first should address that problem before we go deeper into TOC work.

[kaamui]

Hi Martin,

Thank you for all the work you put in analysis of this issue. You had very good ideas to mitigate the possible issues a user would encounter playing with different versions of OpenBoard on a same document, after the TOC implementation.

Your recent idea of using document metadata version number (actually 4.8) could be the simpler and best solution : we check for the document version. If not 4.9, we update the document to the new structure (with a pages.json and a assets.json, when the file is requested).

We can even introduce an empty file in the folder, for example upgradedto.toc, so if we detect the metadata is 4.8, we check for this file existence, and if it exists, we know that the file is being used in two different instances, so we can alert the user that he should upgrade all his/her other versions of OpenBoard to the new one to avoid issues. We can then also update again the TOC.

Do you think it could work ? What are your thoughts based on 4.8/4.9 version number ?

[letsfindaway]

We can even introduce an empty file in the folder, for example upgradedto.toc, so if we detect the metadata is 4.8, we check for this file existence, and if it exists, we know that the file is being used in two different instances, so we can alert the user that he should upgrade all his/her other versions of OpenBoard to the new one to avoid issues. We can then also update again the TOC.

Do you think it could work ? What are your thoughts based on 4.8/4.9 version number ?

I think it would not even need that empty file. If we find a TOC and document version is 4.8, then we also know that this document was at least once opened by the current version, but handled last by a previous version.

[kaamui]

Good point !

[letsfindaway]

Just found out that currently reading the metadata version is buggy and always reads it as "4.1". See here:

OpenBoard/src/adaptors/UBMetadataDcSubsetAdaptor.cpp

Lines 165 to 229 in 9a8abac

	if (xml.isStartElement())
	{
	QString docVersion = "4.1"; // untagged doc version 4.1
	QString name = xml.name().toString();
	if (name == "title")
	{
	metadata.insert(UBSettings::documentName, xml.readElementText());
	}
	else if (name == "type")
	{
	metadata.insert(UBSettings::documentGroupName, xml.readElementText());
	}
	else if (name == "date")
	{
	date = xml.readElementText();
	}
	else if (name == "identifier") // introduced in UB 4.2
	{
	metadata.insert(UBSettings::documentIdentifer, xml.readElementText());
	}
	else if (name == "version" // introduced in UB 4.2
	&& xml.namespaceUri() == UBSettings::uniboardDocumentNamespaceUri)
	{
	docVersion = xml.readElementText();
	}
	else if (name == "size" // introduced in UB 4.2
	&& xml.namespaceUri() == UBSettings::uniboardDocumentNamespaceUri)
	{
	QString size = xml.readElementText();
	QStringList sizeParts = size.split("x");
	bool ok = false;
	int width, height;
	if (sizeParts.count() >= 2)
	{
	bool widthOK, heightOK;
	width = sizeParts.at(0).toInt(&widthOK);
	height = sizeParts.at(1).toInt(&heightOK);
	ok = widthOK && heightOK;
	QSize docSize(width, height);
	if (width == 1024 && height == 768) // move from 1024/768 to 1280/960
	{
	docSize = UBSettings::settings()->pageSize->get().toSize();
	}
	metadata.insert(UBSettings::documentSize, QVariant(docSize));
	}
	if (!ok)
	{
	qWarning() << "Invalid document size:" << size;
	}
	sizeFound = true;
	}
	else if (name == "updated-at" // introduced in UB 4.4
	&& xml.namespaceUri() == UBSettings::uniboardDocumentNamespaceUri)
	{
	metadata.insert(UBSettings::documentUpdatedAt, xml.readElementText());
	updatedAtFound = true;
	}
	metadata.insert(UBSettings::documentVersion, docVersion);
	}

• In line 167, docVersion is initialized.
• In line 189, it is correctly read and set.
• In line 228, it is inserted to the metadata each time.

This means, that finally the correct value is again overwritten when parsing the next start element. :-( The initialization should be much earlier, outside of the parsing loop.

So we do not have that warning message when opening a newer document.

Edit:

Just found a workaround: We change the UBMetadataDcSubsetAdaptor to write the version as the last element of the Description. Then it is parsed on the last round of the parser and does not get overwritten later. Just tested and confirmed: We can get the warning message with that!

[letsfindaway]

Here a further brain dump:

Do not change media asset UUIDs

• Create a unique function to copy pages and use it everywhere.
• Do not rename media assets when copying.
• Do not copy if it already exists.

Note:

• Duplicating an item (e.g. image) also duplicates the asset.
• See UBBoardController::duplicateItem() and change this accordingly.
• The hash based UUIDs would help in many cases.

Use hash based UUIDs for media files

Additional idea: We could also use a hash based UUID, e.g. created by QUuid::createUuidV5(), so that we get the same id when we add the same file twice.

This will not work for web widgets represented by a directory. We could hash the config.xml, provided these files are now really unique.

Increment document version number

To distinguish documents processed by the new version of OpenBoard, we increment the document version number to 4.9.0. We also have to write the version number as the last element of Description in order to circumvent a metadata parsing failure.

When opening a document in the new version of OpenBoard, we can detect

• if this document was last opened by a previous version of OpenBoard (by checking the document version),
• if this document was ever opened by the new version of OpenBoard (i.e. contains a TOC).

We should trigger a (re-)scan of the document and create or update the TOC whenever the version number is < 4.9.0.

Store assets as part of the TOC

The TOC entry for a page shall contain an "assets" list with the names of all assets used. The list is updated when saving a scene.

When deleting a UBDocument object, we delete all asset files which are not mentioned by at least one scene. Note that UBDocument objects are currently deleted when closing OpenBoard, as we otherwise do not delete UBDocument instances. This might change when we introduce more intelligent caching.

Store the scene UUID as part of the TOC

Storing the scene UUID as part of the TOC allows us to verify the integrity of the TOC when a document was modified by a previous version of OpenBoard. See "scanning" below.

Scanning a document

A document has to be scanned or re-scanned when the document version is < 4.9.0. Here a proposal for the algorithm which works both for an initial scan and for a re-scan. Scanning is started when we create a UBDocument, i.e. when click on a document in Document mode. Scanning should happen in foreground, because an up-to-date TOC is essential for further document manipulation. Time needed for a scan is probably similar to what we had before the thumbnail optimization.

• Load the TOC if it exists.
• Create a set of all scene UUIDs -> tocSceneUuids.
• Scan through the pages starting from the smallest number and counting up.
• Do not stop on gaps.
• Load the scenes and check the media assets.
• Check the media asset UUIDs. Convert it to a SHA-1 based UUIDv5 if needed. Copy the asset file in this case.
• Check whether the tocSceneUuids already contains this scene.
• If yes, locate and update the TOC entry, else add the file name, thumbnail file name and asset list to the TOC after the last processed TOC entry or at the beginning, if no entry was processed before.
• Remove the scene UUID from the tocSceneUuids.
• When finished, remove all scenes still in tocSceneUuids from the TOC. Those scenes might have been deleted using a previous version of OpenBoard.
• Go through the TOC and create a set of all referenced media assets.
• Delete all unreferenced media asset files.

[letsfindaway]

Question to @kaamui: In UBPersistenceManager::sceneCount(), QFile::exists() is used to check whether a scene file exists. Then the number is incremented until a file is missing.

In my scanner to create a TOC, I want to use QDir.entryList(). I remember that there were some problems when using network drives, which caused reverting my attempts to cleanup a document. Did this affect the completeness of a directory listing? See UBPersistenceManager::getSceneFileNames(). Was this the problematic point?

If yes, then I need other ways to scan for all scene files even if they are not in consecutive order and might have quite large gaps.

Edit: I assume this was not the problem. In UBPersistenceManager::createDocumentProxiesStructure() we're using QDir::entryInfoList() to get the list of all documents and this seems to work. But anyway: can you confirm this? Do you remember what the cause of the problem with the document cleanup was?

Edit 2: Found this comment in UBPersistenceManager on the possibility to get not all files in a directory listing:

// in a network-storage context, can happen on a newly created document, depending on the client and the cache mode you're using

So a directory listing of a newly created document can potentially return not all files. This would just mean that we should not create the first TOC of a new document by scanning, but just by creating it. That should be easy.

[kaamui]

Question to @kaamui: In UBPersistenceManager::sceneCount(), QFile::exists() is used to check whether a scene file exists. Then the number is incremented until a file is missing.

In my scanner to create a TOC, I want to use QDir.entryList(). I remember that there were some problems when using network drives, which caused reverting my attempts to cleanup a document. Did this affect the completeness of a directory listing? See UBPersistenceManager::getSceneFileNames(). Was this the problematic point?

If yes, then I need other ways to scan for all scene files even if they are not in consecutive order and might have quite large gaps.

Edit: I assume this was not the problem. In UBPersistenceManager::createDocumentProxiesStructure() we're using QDir::entryInfoList() to get the list of all documents and this seems to work. But anyway: can you confirm this? Do you remember what the cause of the problem with the document cleanup was?

Edit 2: Found this comment in UBPersistenceManager on the possibility to get not all files in a directory listing:

// in a network-storage context, can happen on a newly created document, depending on the client and the cache mode you're using

So a directory listing of a newly created document can potentially return not all files. This would just mean that we should not create the first TOC of a new document by scanning, but just by creating it. That should be easy.

Sorry for the late reply, The issue encountered was that because of the cache strategy used (to workaround performance issues) by the network storage client, newly created pages and/or documents could be missing when interrogating the directory with entryList etc

This is what I remember;

[letsfindaway]

Thanks, this fits to what I know about this issue.

[letsfindaway]

Just created branch feat-toc with all the current work. It is not ready for merging, but for testing. The work previously done in refactor-scene-copy is also contained (and improved) here, so that branch will be deleted.

Still missing is the cleanup of no longer referenced media asset files. Also the scanner for scanning pre-4.9.0 documents will be further improved to convert the asset files to use the new content-based UUIDv5 identifiers.

Here is the comparison of all changes: OpenBoard-org/OpenBoard@dev...letsfindaway:OpenBoard:feat-toc

With (currently) 11 commits containing 1,415 additions and 7,291 deletions it is more extensive than I have expected initially. The large number of deletions comes from the fact that the UBForeignObjectsHandler and CFF support, but also some unused functions were dropped.

I have also collected some TODOs in #215

[letsfindaway]

After a longer pause I now added one more commit to address most of the points in #215. Renumbering pages for export is still open, and some more documentation.

[letsfindaway]

Now also renumbering pages for export is complete. I will create a PR which can be used for testing.