Undo: fix multi-level undo of delete-dive and remove-dive-from-trip

The original undo-code was fundamentally broken. Not only did it leak
resources (copied trips were never freed), it also kept references
to trips or dives that could be changed by other commands. Thus,
anything more than a single undo could lead to crashes.

Two ways of fixing this were considered
1) Don't store pointers, but unique dive-ids and trip-ids.
   Whereas such unique ids exist for dives, they would have to be
   implemented for trips.
2) Don't free objects in the backend.
   Instead, take ownership of deleted objects in the undo-object.
   Thus, all references in previous undo-objects are guaranteed to
   still exist (unless the objects are deleted elsewhere).

After some contemplation, the second method was chosen, because
it is significantly less intrusive. While touching the undo-objects,
clearly separate backend from ui-code, such that they can ultimately
be reused for mobile.

Note that if other parts of the code delete dives, crashes can still
be provoked. Notable examples are split/merge dives. These will have
to be fixed later. Nevertheless, the new code is a significant
improvement over the old state.

While touching the code, implement proper translation string based
on Qt's plural-feature (using %n).

Signed-off-by: Berthold Stoeger <bstoeger@mail.tuwien.ac.at>

1 files changed, 177 insertions, 15 deletions

diff --git a/desktop-widgets/undocommands.h b/desktop-widgets/undocommands.h
index 4e485e5ed..bbc1f05bd 100644
--- a/desktop-widgets/undocommands.h
+++ b/desktop-widgets/undocommands.h
@@ -2,50 +2,212 @@
 #ifndef UNDOCOMMANDS_H
 #define UNDOCOMMANDS_H
 
+#include "core/dive.h"
+
 #include <QUndoCommand>
-#include <QMap>
+#include <QCoreApplication> // For Q_DECLARE_TR_FUNCTIONS
+#include <QVector>
+#include <memory>
+
+// The classes declared in this file represent units-of-work, which can be exectuted / undone
+// repeatedly. The command objects are collected in a linear list implemented in the QUndoStack class.
+// They contain the information that is necessary to either perform or undo the unit-of-work.
+// The usage is:
+//	constructor: generate information that is needed for executing the unit-of-work
+//	redo(): performs the unit-of-work and generates the information that is needed for undo()
+//	undo(): undos the unit-of-work and regenerates the initial information needed in redo()
+// The needed information is mostly kept in pointers to dives and/or trips, which have to be added
+// or removed.
+// For this to work it is crucial that
+// 1) Pointers to dives and trips remain valid as long as referencing command-objects exist.
+// 2) The dive-table is not resorted, because dives are inserted at given indices.
+//
+// Thus, if a command deletes a dive or a trip, the actual object must not be deleted. Instead,
+// the command object removes pointers to the dive/trip object from the backend and takes ownership.
+// To reverse such a deletion, the object is re-injected into the backend and ownership is given up.
+// Once ownership of a dive is taken, any reference to it was removed from the backend. Thus,
+// subsequent redo()/undo() actions cannot access this object and integrity of the data is ensured.
+//
+// As an example, consider the following course of events: Dive 1 is renumbered and deleted, dive 2
+// is added and renumbered. The undo list looks like this (---> non-owning, ***> owning pointers,
+// ===> next item in list)
+//
+//                                        Undo-List
+// +-----------------+     +---------------+     +------------+     +-----------------+
+// | Renumber dive 1 |====>| Delete dive 1 |====>| Add dive 2 |====>| Renumber dive 2 |
+// +------------------     +---------------+     +------------+     +-----------------+
+//          |                      *                   |                     |
+//          |      +--------+      *                   |    +--------+       |
+//          +----->| Dive 1 |<******                   +--->| Dive 2 |<------+
+//                 +--------+                               +--------+
+//                                                              ^
+//                                    +---------+               *
+//                                    | Backend |****************
+//                                    +---------+
+// Two points of note:
+// 1) Every dive is owned by either the backend or exactly one command object.
+// 2) All references to dive 1 are *before* the owner "delete dive 2", thus the pointer is always valid.
+// 3) References by the backend are *always* owning.
+//
+// The user undos the last two commands. The situation now looks like this:
+//
+//
+//                  Undo-List                                Redo-List
+// +-----------------+     +---------------+     +------------+     +-----------------+
+// | Renumber dive 1 |====>| Delete dive 1 |     | Add dive 2 |<====| Renumber dive 2 |
+// +------------------     +---------------+     +------------+     +-----------------+
+//          |                      *                   *                     |
+//          |      +--------+      *                   *    +--------+       |
+//          +----->| Dive 1 |<******                   ****>| Dive 2 |<------+
+//                 +--------+                               +--------+
+//
+//                                    +---------+
+//                                    | Backend |
+//                                    +---------+
+// Again:
+// 1) Every dive is owned by either the backend (here none) or exactly one command object.
+// 2) All references to dive 1 are *before* the owner "delete dive 1", thus the pointer is always valid.
+// 3) All references to dive 2 are *after* the owner "add dive 2", thus the pointer is always valid.
+//
+// The user undos one more command:
+//
+//       Undo-List                                 Redo-List
+// +-----------------+     +---------------+     +------------+     +-----------------+
+// | Renumber dive 1 |     | Delete dive 1 |<====| Add dive 2 |<====| Renumber dive 2 |
+// +------------------     +---------------+     +------------+     +-----------------+
+//          |                      |                   *                     |
+//          |      +--------+      |                   *    +--------+       |
+//          +----->| Dive 1 |<-----+                   ****>| Dive 2 |<------+
+//                 +--------+                               +--------+
+//                     ^
+//                     *              +---------+
+//                     ***************| Backend |
+//                                    +---------+
+// Same points as above.
+// The user now adds a dive 3. The redo list will be deleted:
+//
+//                                      Undo-List
+// +-----------------+                                              +------------+
+// | Renumber dive 1 |=============================================>| Add dive 3 |
+// +------------------                                              +------------+
+//          |                                                             |
+//          |      +--------+                               +--------+    |
+//          +----->| Dive 1 |                               | Dive 3 |<---+
+//                 +--------+                               +--------+
+//                     ^                                        ^
+//                     *              +---------+               *
+//                     ***************| Backend |****************
+//                                    +---------+
+// Note:
+// 1) Dive 2 was deleted with the "add dive 2" command, because that was the owner.
+// 2) Dive 1 was not deleted, because it is owned by the backend.
+//
+// To take ownership of dives/trips, the OnwingDivePtr and OwningTripPtr types are used. These
+// are simply derived from std::unique_ptr and therefore use well-established semantics.
+// Expressed in C-terms: std::unique_ptr<T> is exactly the same as T* with the following
+// twists:
+// 1) default-initialized to NULL.
+// 2) if it goes out of scope (local scope or containing object destroyed), it does:
+//	if (ptr) free_function(ptr);
+//    whereby free_function can be configured (defaults to delete ptr).
+// 3) assignment between two std::unique_ptr<T> compiles only if the source is reset (to NULL).
+//    (hence the name - there's a *unique* owner).
+// While this sounds trivial, experience shows that this distinctly simplifies memory-management
+// (it's not necessary to manually delete all vector items in the destructur, etc).
+// Note that Qt's own implementation (QScoperPointer) is not up to the job, because it doesn't implement
+// move-semantics and Qt's containers are incompatible, owing to COW semantics.
+//
+// Usage:
+//	OwningDivePtr dPtr;			// Initialize to null-state: not owning any dive.
+//	OwningDivePtr dPtr(dive);		// Take ownership of dive (which is of type struct dive *).
+//						// If dPtr goes out of scope, the dive will be freed with free_dive().
+//	struct dive *d = dPtr.release();	// Give up ownership of dive. dPtr is reset to null.
+//	struct dive *d = d.get();		// Get pointer dive, but don't release ownership.
+//	dPtr.reset(dive2);			// Delete currently owned dive with free_dive() and get ownership of dive2.
+//	dPtr.reset();				// Delete currently owned dive and reset to null.
+//	dPtr2 = dPtr1;				// Fails to compile.
+//	dPtr2 = std::move(dPtr1);		// dPtr2 takes ownership, dPtr1 is reset to null.
+//	OwningDivePtr fun();
+//	dPtr1 = fun();				// Compiles. Simply put: the compiler knows that the result of fun() will
+//						// be trashed and therefore can be moved-from.
+//	std::vector<OwningDivePtr> v:		// Define an empty vector of owning pointers.
+//	v.emplace_back(dive);			// Take ownership of dive and add at end of vector
+//						// If the vector goes out of scope, all dives will be freed with free_dive().
+//	v.clear(v);				// Reset the vector to zero length. If the elements weren't release()d,
+//						// the pointed-to dives are freed with free_dive()
+
+// Classes used to automatically call free_dive()/free_trip for owning pointers that go out of scope.
+struct DiveDeleter {
+	void operator()(dive *d) { free_dive(d); }
+};
+struct TripDeleter {
+	void operator()(dive_trip *t) { free_trip(t); }
+};
+
+// Owning pointers to dive and dive_trip objects.
+typedef std::unique_ptr<dive, DiveDeleter> OwningDivePtr;
+typedef std::unique_ptr<dive_trip, TripDeleter> OwningTripPtr;
 
 class UndoDeleteDive : public QUndoCommand {
+	Q_DECLARE_TR_FUNCTIONS(Command)
 public:
-	UndoDeleteDive(QList<struct dive*> deletedDives);
+	UndoDeleteDive(const QVector<dive *> &divesToDelete);
+private:
 	void undo() override;
 	void redo() override;
 
-private:
-	QList<struct dive*> diveList;
-	QList<struct dive_trip*> tripList;
+	// For redo
+	QVector<struct dive*> divesToDelete;
+
+	// For undo
+	struct DiveToAdd {
+		OwningDivePtr	 dive;	// Dive to add
+		dive_trip	*trip;	// Trip, may be null
+		int		 idx;	// Position in divelist
+	};
+	std::vector<OwningTripPtr> tripsToAdd;
+	std::vector<DiveToAdd> divesToAdd;
 };
 
 class UndoShiftTime : public QUndoCommand {
+	Q_DECLARE_TR_FUNCTIONS(Command)
 public:
-	UndoShiftTime(QList<int> changedDives, int amount);
+	UndoShiftTime(QVector<int> changedDives, int amount);
+private:
 	void undo() override;
 	void redo() override;
 
-private:
-	QList<int> diveList;
+	// For redo and undo
+	QVector<int> diveList;
 	int timeChanged;
 };
 
 class UndoRenumberDives : public QUndoCommand {
+	Q_DECLARE_TR_FUNCTIONS(Command)
 public:
-	UndoRenumberDives(QMap<int, QPair<int, int> > originalNumbers);
+	UndoRenumberDives(const QVector<QPair<int, int>> &divesToRenumber);
+private:
 	void undo() override;
 	void redo() override;
 
-private:
-	QMap<int,QPair<int, int> > oldNumbers;
+	// For redo and undo: pairs of dive-id / new number
+	QVector<QPair<int, int>> divesToRenumber;
 };
 
 class UndoRemoveDivesFromTrip : public QUndoCommand {
+	Q_DECLARE_TR_FUNCTIONS(Command)
 public:
-	UndoRemoveDivesFromTrip(QMap<struct dive*, dive_trip*> removedDives);
+	UndoRemoveDivesFromTrip(const QVector<dive *> &divesToRemove);
+private:
 	void undo() override;
 	void redo() override;
 
-private:
-	QMap<struct dive*, dive_trip*> divesToUndo;
-	QList<struct dive_trip*> tripList;
+	// For redo
+	QVector<dive *> divesToRemove;
+
+	// For undo
+	std::vector<std::pair<dive *, dive_trip *>> divesToAdd;
+	std::vector<OwningTripPtr> tripsToAdd;
 };
 
 #endif // UNDOCOMMANDS_H