The problem#

Continuing from the past two weeks, in my work on the Pacifist Factorio mod, I noticed there were rich text icons for military-related entities that I thought the mod had removed from the game. By "rich text icons", I'm referring to the dialog that some text boxes in the game (e.g. for naming a train stop) have a button to bring up which shows icons that can be inserted into the text box which include all of the items in the game along with a few other things. In that dialog, there were icons for things like biter corpses despite biters having been removed from the game.

The solution#

This PR, which is included in the latest version of Pacifist, hides all of the icons related only to items that have been removed or hidden by Pacifist.

The details#

Extra rich text icons#

Browsing around one thing I noticed was that with Pacifist enabled there were some rich text icons related to things that the mod had removed from the game like combat robots and remnants of buildings. Strangely, some of these icons didn't appear when Pacifist wasn't enabled, apparently getting added to that dialog due to the entities that referenced them being removed (e.g. gun turret remnants showing up when gun turrets were removed). Since icons seemed to appear once they no longer had anything referencing them, I figured I could fix that by implementing a kind of garbage collection algorithm, looking at what things Pacifist removed and what they were referencing and removing them if they were the last reference.

Identifying references#

There were a few problems with this plan. The first is that while Factorio does have a well-defined concept of a reference with EntityID and similar types, from the point of view of the mod code, they're all just strings. So either I had to somehow explicitly specify which strings are which kind of reference—which I didn't want to do—or treat any string as possibly being a reference, which could be an over-approximation (and therefore result in not deleting objects that should be deleted). I chose the latter on the assumption that such mistakes would be rare, and, after all, the worst case is extra icons in the rich text dialog that maybe need to be manually added to the list of objects to remove.

Tracing garbage collector#

So I implemented an algorithm that was essentially a simple tracing garbage collector. It scanned all of the objects and noted down which ones had no possible references. Then after the rest of the Pacifist logic had run and removed things, it checked again and removed anything that was newly lacking references. Then it repeated that scan removing anything that was no longer referenced due to its previous pass until it found nothing left to delete.

It seemed to more or less do the right thing. It did reveal a couple entities that I needed to explicitly hide as they really were still used, but other than that it worked fine without other mods.

Improving performance#

On the other hand, the developer of Pacifist expressed concern that the multiple passes could be a performance problem for mods that add a lot to the game, so I rewrote the algorithm to be more like a reference counting garbage collector. By adding some bookkeeping of which objects referenced which other objects in both directions as well as which objects were deleted, the full pass over all of the data only had to happen once, which resulted in a measureable improvement in performance.

Mod compatibility problems#

Unfortunately, that algorithm ran into problems with some mods. The first issue was that DamageTypeID is sometimes stored in properties named type which I had been ignoring for considering references because most properties named type are names of types or prototypes and the latter share names with entities, so I didn't think type properties should count as references. This is difficult to resolve in general without more precise type information, so I just added an exception to my algorithm for damage types to work around the issue.

But that wasn't the main mod incompatibility problem. Unsurprisingly, scripts in mods tend to assume the entities defined by the same mod actually exist. And by deleting them, Pacifist was causing the mod code to fail. That discovery led to the final version of the algorithm, which was actually a small change: instead of deleting everything, just mark things as "hidden". Then mod scripts can reference the objects since they stil exist in the game code, but they won't show up in the interface to the player, satisfying the goal of getting the icons out of the rich text dialog.