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>

7 files changed, 327 insertions, 151 deletions

diff --git a/core/dive.h b/core/dive.h
index b9ec48824..f80412a03 100644
--- a/core/dive.h
+++ b/core/dive.h
@@ -416,12 +416,13 @@ extern bool autogroup;
 
 extern void add_dive_to_trip(struct dive *, dive_trip_t *);
 
+struct dive *unregister_dive(int idx);
 extern void delete_single_dive(int idx);
 extern void add_single_dive(int idx, struct dive *dive);
 
 extern void insert_trip(dive_trip_t **trip);
-extern struct dive_trip *clone_empty_trip(struct dive_trip *trip);
-
+extern void unregister_trip(dive_trip_t *trip);
+extern void free_trip(dive_trip_t *trip);
 
 extern const struct units SI_units, IMPERIAL_units;
 extern struct units xml_parsing_units;
diff --git a/core/divelist.c b/core/divelist.c
index 8d0fa77e5..07c9ea87d 100644
--- a/core/divelist.c
+++ b/core/divelist.c
@@ -16,10 +16,14 @@
  * void update_cylinder_related_info(struct dive *dive)
  * void dump_trip_list(void)
  * void insert_trip(dive_trip_t **dive_trip_p)
+ * void unregister_trip(dive_trip_t *trip)
+ * void free_trip(dive_trip_t *trip)
+ * void remove_dive_from_trip(struct dive *dive)
  * void remove_dive_from_trip(struct dive *dive, bool was_autogen)
  * void add_dive_to_trip(struct dive *dive, dive_trip_t *trip)
  * dive_trip_t *create_and_hookup_trip_from_dive(struct dive *dive)
  * void autogroup_dives(void)
+ * struct dive *unregister_dive(int idx)
  * void delete_single_dive(int idx)
  * void add_single_dive(int idx, struct dive *dive)
  * void merge_two_dives(struct dive *a, struct dive *b)
@@ -732,20 +736,17 @@ void insert_trip(dive_trip_t **dive_trip_p)
 #endif
 }
 
-/* create a copy of a dive trip, but don't add any dives. */
-dive_trip_t *clone_empty_trip(dive_trip_t *trip)
+/* free resources associated with a trip structure */
+void free_trip(dive_trip_t *trip)
 {
-	dive_trip_t *copy = malloc(sizeof(struct dive_trip));
-	*copy = *trip;
-	copy->location = copy_string(trip->location);
-	copy->notes = copy_string(trip->notes);
-	copy->nrdives = 0;
-	copy->next = NULL;
-	copy->dives = NULL;
-	return copy;
+	free(trip->location);
+	free(trip->notes);
+	free(trip);
 }
 
-static void delete_trip(dive_trip_t *trip)
+/* remove trip from the trip-list, but don't free its memory.
+ * caller takes ownership of the trip. */
+void unregister_trip(dive_trip_t *trip)
 {
 	dive_trip_t **p, *tmp;
 
@@ -760,11 +761,12 @@ static void delete_trip(dive_trip_t *trip)
 		}
 		p = &tmp->next;
 	}
+}
 
-	/* .. and free it */
-	free(trip->location);
-	free(trip->notes);
-	free(trip);
+static void delete_trip(dive_trip_t *trip)
+{
+	unregister_trip(trip);
+	free_trip(trip);
 }
 
 void find_new_trip_start_time(dive_trip_t *trip)
@@ -817,13 +819,17 @@ struct dive *last_selected_dive()
 	return ret;
 }
 
-void remove_dive_from_trip(struct dive *dive, short was_autogen)
+/* remove a dive from the trip it's associated to, but don't delete the
+ * trip if this was the last dive in the trip. the caller is responsible
+ * for removing the trip, if the trip->nrdives went to 0.
+ */
+struct dive_trip *unregister_dive_from_trip(struct dive *dive, short was_autogen)
 {
 	struct dive *next, **pprev;
 	dive_trip_t *trip = dive->divetrip;
 
 	if (!trip)
-		return;
+		return NULL;
 
 	/* Remove the dive from the trip's list of dives */
 	next = dive->next;
@@ -838,10 +844,17 @@ void remove_dive_from_trip(struct dive *dive, short was_autogen)
 	else
 		dive->tripflag = NO_TRIP;
 	assert(trip->nrdives > 0);
-	if (!--trip->nrdives)
-		delete_trip(trip);
-	else if (trip->when == dive->when)
+	--trip->nrdives;
+	if (trip->nrdives > 0 && trip->when == dive->when)
 		find_new_trip_start_time(trip);
+	return trip;
+}
+
+void remove_dive_from_trip(struct dive *dive, short was_autogen)
+{
+	struct dive_trip *trip = unregister_dive_from_trip(dive, was_autogen);
+	if (trip && trip->nrdives == 0)
+		delete_trip(trip);
 }
 
 void add_dive_to_trip(struct dive *dive, dive_trip_t *trip)
@@ -918,29 +931,44 @@ void autogroup_dives(void)
 #endif
 }
 
+static void unregister_dive_from_table(struct dive_table *table, int idx)
+{
+	int i;
+	for (i = idx; i < table->nr - 1; i++)
+		table->dives[i] = table->dives[i + 1];
+	table->dives[--table->nr] = NULL;
+}
+
 /* Remove a dive from a dive table. This assumes that the
  * dive was already removed from any trip and deselected.
  * It simply shrinks the table and frees the trip */
 void delete_dive_from_table(struct dive_table *table, int idx)
 {
-	int i;
 	free_dive(table->dives[idx]);
-	for (i = idx; i < table->nr - 1; i++)
-		table->dives[i] = table->dives[i + 1];
-	table->dives[--table->nr] = NULL;
+	unregister_dive_from_table(table, idx);
 }
 
-/* this implements the mechanics of removing the dive from the table,
- * but doesn't deal with updating dive trips, etc */
-void delete_single_dive(int idx)
+/* this removes a dive from the dive table and trip-list but doesn't
+ * free the resources associated with the dive. It returns a pointer
+ * to the unregistered dive. */
+struct dive *unregister_dive(int idx)
 {
 	struct dive *dive = get_dive(idx);
 	if (!dive)
-		return; /* this should never happen */
+		return NULL; /* this should never happen */
 	remove_dive_from_trip(dive, false);
 	if (dive->selected)
 		deselect_dive(idx);
-	delete_dive_from_table(&dive_table, idx);
+	unregister_dive_from_table(&dive_table, idx);
+	return dive;
+}
+
+/* this implements the mechanics of removing the dive from the table,
+ * but doesn't deal with updating dive trips, etc */
+void delete_single_dive(int idx)
+{
+	struct dive *dive = unregister_dive(idx);
+	free_dive(dive);
 }
 
 struct dive **grow_dive_table(struct dive_table *table)
diff --git a/core/divelist.h b/core/divelist.h
index ac9435356..3687b0881 100644
--- a/core/divelist.h
+++ b/core/divelist.h
@@ -26,6 +26,7 @@ struct dive **grow_dive_table(struct dive_table *table);
 extern void get_dive_gas(struct dive *dive, int *o2_p, int *he_p, int *o2low_p);
 extern int get_divenr(const struct dive *dive);
 extern int get_divesite_idx(const struct dive_site *ds);
+extern struct dive_trip *unregister_dive_from_trip(struct dive *dive, short was_autogen);
 extern void remove_dive_from_trip(struct dive *dive, short was_autogen);
 extern dive_trip_t *create_and_hookup_trip_from_dive(struct dive *dive);
 extern void autogroup_dives(void);
diff --git a/desktop-widgets/divelistview.cpp b/desktop-widgets/divelistview.cpp
index fbcd96fd6..945a7381e 100644
--- a/desktop-widgets/divelistview.cpp
+++ b/desktop-widgets/divelistview.cpp
@@ -679,10 +679,10 @@ void DiveListView::removeFromTrip()
 	//TODO: move this to C-code.
 	int i;
 	struct dive *d;
-	QMap<struct dive*, dive_trip*> divesToRemove;
+	QVector<struct dive *> divesToRemove;
 	for_each_dive (i, d) {
 		if (d->selected && d->divetrip)
-			divesToRemove.insert(d, d->divetrip);
+			divesToRemove.append(d);
 	}
 	if (divesToRemove.isEmpty())
 		return;
@@ -797,7 +797,7 @@ void DiveListView::deleteDive()
 
 	int i;
 	int lastDiveNr = -1;
-	QList<struct dive*> deletedDives; //a list of all deleted dives to be stored in the undo command
+	QVector<struct dive*> deletedDives; //a list of all deleted dives to be stored in the undo command
 	for_each_dive (i, d) {
 		if (!d->selected)
 			continue;
diff --git a/desktop-widgets/simplewidgets.cpp b/desktop-widgets/simplewidgets.cpp
index 64845712d..25345551a 100644
--- a/desktop-widgets/simplewidgets.cpp
+++ b/desktop-widgets/simplewidgets.cpp
@@ -160,15 +160,15 @@ void RenumberDialog::buttonClicked(QAbstractButton *button)
 {
 	if (ui.buttonBox->buttonRole(button) == QDialogButtonBox::AcceptRole) {
 		MainWindow::instance()->dive_list()->rememberSelection();
-		// we remember a map from dive uuid to a pair of old number / new number
-		QMap<int, QPair<int, int>> renumberedDives;
+		// we remember a list from dive uuid to a new number
+		QVector<QPair<int, int>> renumberedDives;
 		int i;
 		int newNr = ui.spinBox->value();
 		struct dive *dive = NULL;
 		for_each_dive (i, dive) {
 			if (!selectedOnly || dive->selected) {
 				invalidate_dive_cache(dive);
-				renumberedDives.insert(dive->id, QPair<int, int>(dive->number, newNr++));
+				renumberedDives.append(QPair<int, int>(dive->id, newNr++));
 			}
 		}
 		UndoRenumberDives *undoCommand = new UndoRenumberDives(renumberedDives);
@@ -241,7 +241,7 @@ void ShiftTimesDialog::buttonClicked(QAbstractButton *button)
 			// DANGER, DANGER - this could get our dive_table unsorted...
 			int i;
 			struct dive *dive;
-			QList<int> affectedDives;
+			QVector<int> affectedDives;
 			for_each_dive (i, dive) {
 				if (!dive->selected)
 					continue;
@@ -249,8 +249,6 @@ void ShiftTimesDialog::buttonClicked(QAbstractButton *button)
 				affectedDives.append(dive->id);
 			}
 			MainWindow::instance()->undoStack->push(new UndoShiftTime(affectedDives, amount));
-			sort_table(&dive_table);
-			mark_divelist_changed(true);
 			MainWindow::instance()->dive_list()->rememberSelection();
 			MainWindow::instance()->refreshDisplay();
 			MainWindow::instance()->dive_list()->restoreSelection();
diff --git a/desktop-widgets/undocommands.cpp b/desktop-widgets/undocommands.cpp
index 06879eb51..d58ac7a4b 100644
--- a/desktop-widgets/undocommands.cpp
+++ b/desktop-widgets/undocommands.cpp
@@ -3,170 +3,156 @@
 #include "desktop-widgets/mainwindow.h"
 #include "core/divelist.h"
 #include "core/subsurface-string.h"
+#include "core/gettextfromc.h"
 
-UndoDeleteDive::UndoDeleteDive(QList<dive *> deletedDives) : diveList(deletedDives)
+UndoDeleteDive::UndoDeleteDive(const QVector<struct dive*> &divesToDeleteIn) : divesToDelete(divesToDeleteIn)
 {
-	setText("delete dive");
-	if (diveList.count() > 1)
-		setText(QString("delete %1 dives").arg(QString::number(diveList.count())));
+	setText(tr("delete %n dive(s)", "", divesToDelete.size()));
 }
 
 void UndoDeleteDive::undo()
 {
 	// first bring back the trip(s)
-	Q_FOREACH(struct dive_trip *trip, tripList)
-		insert_trip(&trip);
+	for (auto &trip: tripsToAdd) {
+		dive_trip *t = trip.release();	// Give up ownership
+		insert_trip(&t);		// Return ownership to backend
+	}
+	tripsToAdd.clear();
 
-	// now walk the list of deleted dives
-	for (int i = 0; i < diveList.count(); i++) {
-		struct dive *d = diveList.at(i);
-		// we adjusted the divetrip to point to the "new" divetrip
-		if (d->divetrip) {
-			struct dive_trip *trip = d->divetrip;
-			tripflag_t tripflag = d->tripflag; // this gets overwritten in add_dive_to_trip()
-			d->divetrip = NULL;
-			d->next = NULL;
-			d->pprev = NULL;
-			add_dive_to_trip(d, trip);
-			d->tripflag = tripflag;
-		}
-		record_dive(diveList.at(i));
+	for (DiveToAdd &d: divesToAdd) {
+		if (d.trip)
+			add_dive_to_trip(d.dive.get(), d.trip);
+		divesToDelete.append(d.dive.get());		// Delete dive on redo
+		add_single_dive(d.idx, d.dive.release());	// Return ownership to backend
 	}
 	mark_divelist_changed(true);
-	tripList.clear();
+	divesToAdd.clear();
+
+	// Finally, do the UI stuff:
 	MainWindow::instance()->refreshDisplay();
 }
 
 void UndoDeleteDive::redo()
 {
-	QList<struct dive*> newList;
-	for (int i = 0; i < diveList.count(); i++) {
-		// make a copy of the dive before deleting it
-		struct dive* d = alloc_dive();
-		copy_dive(diveList.at(i), d);
-		newList.append(d);
-		// check for trip - if this is the last dive in the trip
-		// the trip will get deleted, so we need to remember it as well
-		if (d->divetrip && d->divetrip->nrdives == 1) {
-			dive_trip *undo_trip = clone_empty_trip(d->divetrip);
-			// update all the dives who were in this trip to point to the copy of the
-			// trip that we are about to delete implicitly when deleting its last dive below
-			Q_FOREACH(struct dive *inner_dive, newList) {
-				if (inner_dive->divetrip == d->divetrip)
-					inner_dive->divetrip = undo_trip;
-			}
-			d->divetrip = undo_trip;
-			tripList.append(undo_trip);
+	for (dive *d: divesToDelete) {
+		int idx = get_divenr(d);
+		if (idx < 0) {
+			qWarning() << "Deletion of unknown dive!";
+			continue;
+		}
+		// remove dive from trip - if this is the last dive in the trip
+		// remove the whole trip.
+		dive_trip *trip = unregister_dive_from_trip(d, false);
+		if (trip && trip->nrdives == 0) {
+			unregister_trip(trip);			// Remove trip from backend
+			tripsToAdd.emplace_back(trip);		// Take ownership of trip
 		}
-		//delete the dive
-		int nr;
-		if ((nr = get_divenr(diveList.at(i))) >= 0)
-			delete_single_dive(nr);
+
+		unregister_dive(idx);			// Remove dive from backend
+		divesToAdd.push_back({ OwningDivePtr(d), trip, idx });
+							// Take ownership for dive
 	}
+	divesToDelete.clear();
 	mark_divelist_changed(true);
+
+	// Finally, do the UI stuff:
 	MainWindow::instance()->refreshDisplay();
-	diveList.clear();
-	diveList = newList;
 }
 
 
-UndoShiftTime::UndoShiftTime(QList<int> changedDives, int amount)
+UndoShiftTime::UndoShiftTime(QVector<int> changedDives, int amount)
 	: diveList(changedDives), timeChanged(amount)
 {
-	setText("shift time");
+	setText(tr("delete %n dive(s)", "", changedDives.size()));
 }
 
 void UndoShiftTime::undo()
 {
 	for (int i = 0; i < diveList.count(); i++) {
-		struct dive* d = get_dive_by_uniq_id(diveList.at(i));
+		dive *d = get_dive_by_uniq_id(diveList.at(i));
 		d->when -= timeChanged;
 	}
+	// Changing times may have unsorted the dive table
+	sort_table(&dive_table);
 	mark_divelist_changed(true);
+
+	// Negate the time-shift so that the next call does the reverse
+	timeChanged = -timeChanged;
+
+	// Finally, do the UI stuff:
 	MainWindow::instance()->refreshDisplay();
 }
 
 void UndoShiftTime::redo()
 {
-	for (int i = 0; i < diveList.count(); i++) {
-		struct dive* d = get_dive_by_uniq_id(diveList.at(i));
-		d->when += timeChanged;
-	}
-	mark_divelist_changed(true);
-	MainWindow::instance()->refreshDisplay();
+	// Same as undo(), since after undo() we reversed the timeOffset
+	undo();
 }
 
 
-UndoRenumberDives::UndoRenumberDives(QMap<int, QPair<int, int> > originalNumbers)
+UndoRenumberDives::UndoRenumberDives(const QVector<QPair<int, int>> &divesToRenumberIn) : divesToRenumber(divesToRenumberIn)
 {
-	oldNumbers = originalNumbers;
-	if (oldNumbers.count() > 1)
-		setText(QString("renumber %1 dives").arg(QString::number(oldNumbers.count())));
-	else
-		setText("renumber dive");
+	setText(tr("renumber %n dive(s)", "", divesToRenumber.count()));
 }
 
 void UndoRenumberDives::undo()
 {
-	foreach (int key, oldNumbers.keys()) {
-		struct dive* d = get_dive_by_uniq_id(key);
-		d->number = oldNumbers.value(key).first;
+	for (auto &pair: divesToRenumber) {
+		dive *d = get_dive_by_uniq_id(pair.first);
+		if (!d)
+			continue;
+		std::swap(d->number, pair.second);
 	}
 	mark_divelist_changed(true);
+
+	// Finally, do the UI stuff:
 	MainWindow::instance()->refreshDisplay();
 }
 
 void UndoRenumberDives::redo()
 {
-	foreach (int key, oldNumbers.keys()) {
-		struct dive* d = get_dive_by_uniq_id(key);
-		d->number = oldNumbers.value(key).second;
-	}
-	mark_divelist_changed(true);
-	MainWindow::instance()->refreshDisplay();
+	// Redo and undo do the same thing!
+	undo();
 }
 
-
-UndoRemoveDivesFromTrip::UndoRemoveDivesFromTrip(QMap<dive *, dive_trip *> removedDives)
+UndoRemoveDivesFromTrip::UndoRemoveDivesFromTrip(const QVector<dive *> &divesToRemoveIn) : divesToRemove(divesToRemoveIn)
 {
-	divesToUndo = removedDives;
-	setText("remove dive(s) from trip");
+	setText(tr("remove %n dive(s) from trip", "", divesToRemove.size()));
 }
 
 void UndoRemoveDivesFromTrip::undo()
 {
 	// first bring back the trip(s)
-	Q_FOREACH(struct dive_trip *trip, tripList)
-		insert_trip(&trip);
-	tripList.clear();
-
-	QMapIterator<dive*, dive_trip*> i(divesToUndo);
-	while (i.hasNext()) {
-		i.next();
-		add_dive_to_trip(i.key(), i.value());
+	for (auto &trip: tripsToAdd) {
+		dive_trip *t = trip.release();	// Give up ownership
+		insert_trip(&t);		// Return ownership to backend
 	}
-	mark_divelist_changed(true);
+	tripsToAdd.clear();
+
+	for (auto &pair: divesToAdd)
+		add_dive_to_trip(pair.first, pair.second);
+	divesToAdd.clear();
+
+	// Finally, do the UI stuff:
 	MainWindow::instance()->refreshDisplay();
 }
 
 void UndoRemoveDivesFromTrip::redo()
 {
-	QMapIterator<dive*, dive_trip*> i(divesToUndo);
-	while (i.hasNext()) {
-		i.next();
-		// If the trip will be deleted, remember it so that we can restore it later.
-		dive_trip *trip = i.value();
-		if (trip->nrdives == 1) {
-			dive_trip *cloned_trip = clone_empty_trip(trip);
-			tripList.append(cloned_trip);
-			// Rewrite the dive list, such that the dives will be added to the resurrected trip.
-			for (dive_trip *&old_trip: divesToUndo) {
-				if (old_trip == trip)
-					old_trip = cloned_trip;
-			}
+	for (dive *d: divesToRemove) {
+		// remove dive from trip - if this is the last dive in the trip
+		// remove the whole trip.
+		dive_trip *trip = unregister_dive_from_trip(d, false);
+		if (!trip)
+			continue;				// This was not part of a trip
+		if (trip->nrdives == 0) {
+			unregister_trip(trip);			// Remove trip from backend
+			tripsToAdd.emplace_back(trip);		// Take ownership of trip
 		}
-		remove_dive_from_trip(i.key(), false);
+		divesToAdd.emplace_back(d, trip);
 	}
 	mark_divelist_changed(true);
+
+	// Finally, do the UI stuff:
 	MainWindow::instance()->refreshDisplay();
 }
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