In a tree-like structure, how to make sure child entries aren't used by their uncles

This is a rather broad architectural question but it's an issue I often run into with Rust in all kinds of situations. I'll try to bring my point across with an example.

I often have a tree-like structure with few levels (usually just two), like an Excel Workbook that has Worksheets or, as in this example, a Backup Set and a Backup in a client application for a backup server. The BackupSet struct is constructed by reading metadata from the backup server and after that it contains a list of Backups. For simplicity in this example I pass the connection to every operation.

struct BackupSet {
  set_id: String,
  backups: Vec<Backup>
}
struct Backup {
  backup_id: String
}

let backup_set: BackupSet = backup_server_connection.read_metadata();

Now let's add a global function print_backup_files() which can print the files contained in a backup. It needs to fetch the list of files from the backup server, for a particular backup. To fetch the list of files it needs to tell the server the identifier for the backup set and the backup.

In a garbage collected language, Backup would simply have a reference to BackupSet and use that to get the backup set id:

struct BackupSet {
  set_id: String,
  backups: Vec<Backup>
}
struct Backup {
  backup_id: String,
  backup_set: &BackupSet
}

impl Backup {
  fn fetch_filenames(&self, conn: &ServerConnection) {
    conn.send_request("get_filenames", self.backup_set.set_id, self.backup_id)
  }
}

fn print_backup_files(conn: &ServerConnection, backup: &Backup) {
  dbg!(backup_set.fetch_filenames(conn: &ServerConnection));
}

let backup_set: BackupSet = backup_server_connection.read_metadata();
print_backup_files(backup_server_connection, &backup_set.backups[0]);

In Rust however having a reference to BackupSet in Backup while the Backups are stored in BackupSet needs unsafe and is generally better avoided, as far as I understand. This usually leads me to an interface where I just pass both the parent (BackupSet) and the child (Backup) to functions:

struct BackupSet {
  set_id: String,
  backups: Vec<Backup>
}
struct Backup {
  backup_id: String,
}

impl Backup {
  fn fetch_filenames(&self, conn: &ServerConnection, backup_set: &BackupSet) {
    conn.send_request("get_filenames", backup_set.set_id, self.backup_id)
  }
}

fn print_backup_files(conn: &ServerConnection, backup_set: &BackupSet, backup: &Backup) {
  dbg!(backup_set.fetch_filenames(conn: &ServerConnection, backup_set: &BackupSet));
}

let backup_set: BackupSet = backup_server_connection.read_metadata();
print_backup_files(backup_server_connection, backup_set, &backup_set.backups[0]);

But now assume I'm working with multiple BackupSets:

let first_backup_set: BackupSet = backup_server_connection.read_metadata("first");
let second_backup_set: BackupSet = backup_server_connection.read_metadata("second");

Nothing is stopping me from using a Backup that belongs to first_backup_set with second_backup_set:

let first_backup_set: BackupSet = backup_server_connection.read_metadata("first");
let second_backup_set: BackupSet = backup_server_connection.read_metadata("second");
let a_backup_from_first = first_backup_set.backups[0];
let a_backup_from_second = second_backup_set.backups[0];
print_backup_files(backup_server_connection, &first_backup_set, &a_backup_from_second); // Bug!!!

This might be "safe" in terms of memory management, but it will still lead to serious bugs that are hard to spot.

What techniques are generally used to avoid this kind of problem?

You could store the BackupSet inside an Rc (or Arc) which is a reference counted smart pointer, and store clones of this pointer inside every backup. (You can also use Weak for breaking eventual reference cycles, if you encounter those.)

In this case you could create a wrapper struct with a reference to a &BackupSet and &Backup. This wrapper struct will be returned when indexing into a BackupSet and should be the only way to get a reference to a &Backup inside the BackupSet. Being the only way to get a &Backup this will ensure you won't accidentaly pass the wrong parent along with a &Backup

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.