Cataclysm-dda: item::charges is a long, but often used as an int

[jbytheway]

Describe the bug
(Arising from discussion in the largely unrelated PR #26092)

item::charges is a long, but many places working with charges only use an int. For example:

https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/vehicle.cpp#L3476
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/activity_item_handling.cpp#L95
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/activity_item_handling.cpp#L255
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/activity_item_handling.cpp#L46
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/activity_item_handling.cpp#L546
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/activity_item_handling.cpp#L741
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/advanced_inv.cpp#L1286
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/advanced_inv.cpp#L1355
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/advanced_inv.cpp#L2225
https://github.com/CleverRaven/Cataclysm-DDA/blob/a36162e6579f463b7f61c4f3ef977daba774ccb8/src/bionics.cpp#L424

I'm stopping after 10 examples; they were not difficult to find and I'm sure there are many more.

In practical terms, a long is an awkward data type to use because under MSVC on Windows it's the same as an int (32 bits) but on most other current platforms it's 64 bits. Since you have Appveyor CI set up using MSVC, I presume 32 bits is fine, and perhaps charges should just be made an int.

On the other hand, if item::charges really needs 64 bits then it should probably be int64_t, or maybe a custom type that doesn't implicitly cast to int.

I don't really think this will be a problem in practice (although #26031 might bring us a little closer to concern). But since @alanbrady raised it in review it felt appropriate to open an issue on the topic.

[cake-pie]

I don't really think this will be a problem in practice (although #26031 might bring us a little closer to concern).

Not limited to #26031, there are several item stats that may be multiplied by number of charges, such as:
https://github.com/CleverRaven/Cataclysm-DDA/blob/79d9903e17b0ceb9e648f9e6d3fd73a599f3b7fe/src/itype.h#L771-L777
All of which have underlying type of int -- with volume in milliliters and mass in grams, so in theory overflow could occur. I'd concur that in practice it'll probably take some pretty absurd corner case before we get in trouble, but we may want to think about precautions nonetheless e.g. capping max number of charges in a stack, max values of weight/volume/price/etc per item.

[Xion350]

I don't think there's any risk of overflow here. Even with mods that give you unlimited storage space.

[Kelenius]

32 thousand batteries in one place isn't impossible. They tend to spawn in stacks of 100, so it's just 320 stacks.

[kevingranade]

Max int isnt 32K, its 2 billion.

[Kelenius]

Oh, right. In that case the highest likely number would probably be price of a battery stack: they cost 12000. There are more expensive items, but they're rare. 2147483647 / 12000 = 178956.971 so you'd need almost 179 thousand 100-battery stacks.

[cake-pie]

A map tile can accommodate up to 4096 different items and is capped at 1000L.
Assuming that's a safe upper limit in terms of how much space there is for items in a single place, and stack_size is fixed and working properly (see: #24929), then:

• Largest stack size currently found in json is 1000, giving per-charge volume of 0.25mL. That means a theoretical 4,000,000 charges of, say, gold gold_small could be put in one map tile, which is well below max int.
• Supposing we use int rather than long for item::charges, it would support max stack_size of 2^31 / (1000L/250mL) = 536,870, i.e. 1000L can hold max int charges of item having per-charge volume approx 0.466µL. That should be well beyond what we'd ever need -- the smallest volume I can imagine we'd care to measure is eyedrops at about 0.05mL per drop.

Which suggests int would suffice for item::charges.

For overflow avoidance (e.g. in #26031) stack size could be capped at around 2000 for a stack volume 250ml. That's 8,000,000 charges fits in 1000L, so (charges × stack_vol) / stack_size will see the numerator reach 2e9.

[jbytheway]

If you have gold_small in a 250L cargo container as well as on the floor, you can have 5 million charges per map square. And when accumulating the charges available for crafting, all charges from map squares within a radius of 6 will be added together. That's at most 13x13=169 map squares (I think), meaning nearly 850 million charges total. There's already a place in the code where INFINITE_CHARGES / 2 charges is considered infinite, which is only ~1e9. So in the most extreme case we're within about 20% of a potential problem.

[cake-pie]

There's already a place in the code where INFINITE_CHARGES / 2 charges is considered infinite

Hmm, that's bool item::merge_charges( const item &rhs )
https://github.com/CleverRaven/Cataclysm-DDA/blob/c9e5e364194761e7f7cdd0772483382f0a7b96b3/src/item.cpp#L612-L616

By contrast, see void item::mod_charges( long mod )
https://github.com/CleverRaven/Cataclysm-DDA/blob/c9e5e364194761e7f7cdd0772483382f0a7b96b3/src/item.cpp#L6784-L6785

The first doesn't actually look right; it's overzealous with the overflow prevention and potentially turns finite number of charges into infinite. (It'd also cause processing of item_counter in subsequent lines of code to be skipped unnecessarily for false positives of overflow detection.)

In practice it currently doesn't matter because no finite stacks get even close to these sizes.

If use int for charges then it'd become more important for that code to be correct; something like:

if( charges == INFINITE_CHARGES || rhs.charges == INFINITE_CHARGES ) {
    // merge finite stack into infinite stack, or two infinite stacks together
    charges = INFINITE_CHARGES;
    // process item_counter as sensibly as we can
    return true;
} else if ( rhs.charges > 0 && charges >= INFINITE_CHARGES - rhs.charges ) {
    // refuse to merge two finite stacks if it would lead to overflow
    // should not happen if item stats are kept within sane limits
    return false;
}

---

Continuing with the extreme worst conceivable case of combined number of charges within crafting range, 13×13=169 map squares with 1000L capacity on floor and 250L in vehicle storage can store 211250L.

211250 / (2^31-2) = 0.098371mL so we could support a per-charge volume of as low as 0.1mL if charges were int. [ (2^31-2) because INT_MAX reserved as special value INFINITE_CHARGES. ]

I was hoping for a minimum per-charge volume of 0.05mL (eyedrop dosage) but admittedly that's an outlier use case. (Unsigned int would do the trick, though!)

[Kelenius]

Gold doesn't spawn often enough for this to be a problem in the first place.

[cake-pie]

Sure, but it's prudent to to explore worst case scenarios so we can have strong guarantees in place and be pretty confident things aren't going to break if we switch to int or unsigned int.

Is there anything that contraindicates using unsigned for charges? I know item::mod_charges uses a signed parameter so it can be used for both adding and removing charges, but that's not a major blocker, I think?

[jbytheway]

I can think of a few reasons not to switch to unsigned:

• People are bound to write code that in practice doesn't work for values greater than INT_MAX, and those bugs will almost certainly not be caught in testing.
• Accidentally getting negative charges is entirely plausible to happen due to bugs, and it's helpful to be able to say with certainty that it was a bug, whereas with unsigned charges it's hard to distinguish underflow from really large numbers.
• Signed integer overflow is undefined behaviour, and thus detectable with ubsan, should the game ever be run/tested with that. It would be nice to know that it would catch such bugs.
• Whenever comparing charges with a signed number you'd have to agonise what kind of cast to use to avoid the compiler warning about signed/unsigned comparison.

[kevingranade]

@jbytheway makes great points, unsigned integers are terrible for use as counting numbers. IMO they should be qvoided.

[cake-pie]

Points taken re: unsigned.
Are we feeling comfortable with int then?

I'm thinking perhaps a couple checks could be added in Item_factory (check_definitions or finalize) to detect and warn about items whose stats may cause overflows in extreme circumstances:

• number of charges in 211250L > INT_MAX
• number of charges in 1000L × stat for stack_size charges > INT_MAX
  where stats to check are volume / integral_volume and price / price_postapoc

[Kelenius]

Maybe I'm saying a really stupid thing here, but are these checks really needed? The only way how this overflow could happen in the game is if you intentionally cause it by wishing for enough items, in which case you brought this upon yourself.

[kevingranade]

The reason to put in a persistent check is so we're alerted if something happens like someone adding a "metal shavings" item with very high count that's produced by grinding up a car. I.e. a tiny volume item that gets produced in large quantities.

[BevapDin]

int and long have no well-defined size, the C++ standard only requires them be have at least 16 / 32 bit (which means they can even have the same size). And even than, neither is guaranteed to be 32, 64 or whatever bits large. Your discussion should probably revolve around using int32_t vs int64_t, or int_fast32_t vs int_fast64_t.

[kevingranade]

There's also an issue of pragmatism. Changing all instances of long in the codebase to either int or int64_t (or int_fast64_t) brings us to a consistent state on all systems we care about and is a tractable change to make and maintain.

Changing all instances of int to... anything only brings us hypothetical correctness and would be massively invasive to the code base.

[Night-Pryanik]

Resolved by #30576.