In `PRNT` chunks, write links in depth-first order

[Dekkonot]

EDIT: It turns out this is as simple as iterating through things in the reverse order from what we currently do. It's fast, it's easy, it's free, so we're doing it correctly.

Turns out the issue in #406 is resolved if we just put humanoids last in the PRNT chunks. The "correct" way to handle this would be serialize things in reverse order of descendants, so that top level models get parented last.

I chose to not do that because it would require iterating through the DOM from potentially many starting points (you can serialize with theoretically infinite referents) and it's probably too much work to be worth it -- Humanoids are, as far as I know, one of a handful of Instances with special behavior based on when they're loaded. The other one is I assume Attachments but it hasn't proven a problem yet.

Resolves #406.

[Dekkonot]

Unexpected issue with this PR. Going to close it and reopen it when the time comes, I suppose. Sorry Ken.

[Dekkonot]

So after giving it another try today, it looks like this is fine. I was concerned because the Rojo build I was using still had this problem, but at some point I must have gotten something wrong since it's working as I expected.

[Dekkonot]

...Looking at the existing code, it's filling relevant_instances such that children always come after their parents, right? Is there any reason we can't just iterate through it in reverse order vs your code snippet? I'm looking for a reason that it isn't this simple and failing.

EDIT: To clarify, I mean when serializing the PRNT chunk we'd just use .rev() on the iterators. Is there a reason that isn't fine?

[kennethloeffler]

That might be alright? I'm not totally sure how this weld insertion behavior works. Reversing the iterators as you described does fix the duplicated accessory weld problem I observed, and if it also fixes your issues at Uplift then I'm game to try it out... but at the same time I'd like to inspect the ordering of the PRNT chunk in Roblox-produced files more, just in case they're depending on it in any other ways

[Dekkonot]

I talked to an engineer at Roblox when we first ran into the weld duplication problem, and what we worked out was that it was an issue with Humanoids auto-generating joints if they're not present. Since they were being parented into Workspace before their joints, they were auto-generating them, then the joints were being added from the file, which resulted in a duplication.

My assumption with Roblox, though I'll have to look to verify it, is that they do it in a similar way. My basis is that GetChildren is deterministic through file loads, which indicates they're clearly serializing in the order children were added. And logically, since they don't have this problem with humanoids, the serializer must put children before their parents.

I will verify this, just to make sure there isn't anarchy, but that's my guess and reasoning.

[kennethloeffler]

I've just done some testing myself using a tree of Folders, folders.rbxm.zip, which has the following structure (the lettering shows their order of insertion):

A
├── B
├── C
│   └── E
│   └── F
├── D
│   └── G

I ran the rbxm through rbx-util view-binary, and to make it easier to see what happened, I stripped out irrelevant information, annotated the values in the Name PROP chunk with their respective referents, and annotated the values of the PRNT chunk with their respective names:

---
  - Inst:
      type_id: 0
      type_name: Folder
      object_format: 0
      referents:
        - 0
        - 1
        - 2
        - 3
        - 4
        - 5
        - 6
  - Prop:
      type_id: 0
      prop_name: Name
      prop_type: String
      values:
        - A (0)
        - B (1)
        - C (2)
        - E (3)
        - F (4)
        - D (5)
        - G (6)
  - Prnt:
      version: 0
      links:
        - - 1 (B)
          - 0
        - - 3 (E)
          - 2
        - - 4 (F)
          - 2
        - - 2 (C)
          - 0
        - - 6 (G)
          - 5
        - - 5 (D)
          - 0
        - - 0 (A)
          - -1
  - End

From this it's apparent that:

• Referents are numbered in a depth-first preordering
• the PRNT chunk is in a depth-first postordering (note this is not the same as reversed breadth-first)

Right now, we do both of these breadth-first. We should probably stay focused on the PRNT chunk in this PR, but it's interesting to note the former!

This also shows that I made a mistake in my code a bit further up that causes it to diverge from Roblox's implementation. I wrote a reverse postordered traversal - it would match the Roblox results if I reversed the order of children before pushing them onto the stack, and check if we haven't yet visited the last child of each visited child's children, rather than the first:

-           let mut current_first_child = None;
+           let mut last_visited_child  = None;
            to_visit.push(root_referent);

            while let Some(referent) = to_visit.last() {
                let instance =
                    self.dom
                        .get_by_ref(**referent)
                        .ok_or(InnerError::InvalidInstanceId {
                            referent: **referent,
                        })?;

-               to_visit.extend(instance.children());
+               to_visit.extend(instance.children().rev());

                while let Some(referent) = to_visit.last() {
                    let instance =
                        self.dom
                            .get_by_ref(**referent)
                            .ok_or(InnerError::InvalidInstanceId {
                                referent: **referent,
                            })?;

                    if !instance.children().is_empty()
-                       && instance.children().first() != current_first_child
+                       && instance.children().last() != last_visited_child
                    {
                        break;
                    }

                    self.relevant_instances.push(**referent);
                    self.collect_type_info(instance)?;

-                   current_first_child = to_visit.pop();
+                   last_visited_child = to_visit.pop();
                }
            }
        }

Now, I'm not sure how important it actually is to get these orderings right. We have a real-life example of where the PRNT chunk ordering is important. I can't think of why referent numbering would matter, but there might be surprises there too. It seems like it's only really necessary to get the PRNT chunk nearly right... at least for now.

I'd prefer to stay on the safe side and respect Roblox's implementation, but I'll leave the final call up to you.

[Dekkonot]

I don't know if matching the behavior 1:1 is important, to be honest. Looking at it, we're guaranteeing the same thing Roblox is in the PRNT chunk after this PR (depth-first), so I think it's probably fine.

That said, I can understand the desire to replicate it 1:1 given we're changing it anyway. If you think it's necessary I can do it, but I don't think we need to.