Refactor `OpenSim::Array` to internally use `std::vector`

[adamkewley]

Fixes a deep dark hole in my heart - and makes adding iterators, range for-loop support, etc. etc. much easier, because I'm getting bored of seeing for (int...) in modern C++.

WIP:

• The binary search algorithm is slightly different from the original specification The implementation should now match the wording of the initial implementation
• Need to run the test suite /w libASAN to ensure that there isn't any funny business now that the memory allocation pattern has changed

Brief summary of changes

• Replaced the custom implementation with std::vector and added various shims etc. to ensure it's API-compatible with the legacy API
• The only exception to backwards compatibility is the growth increment, which isn't customizable in std::vector, so was deprecated

Testing I've completed

• Because it's so widely used, it affects almost every part of OpenSim - I am guessing that the test suite would kick out the worst offenders
• ... but (WIP) i need to triple-check the binary search code, because it was very tricksy

Looking for feedback on...

CHANGELOG.md (choose one)

• no need to update because users need not know the incredibly tedious process of legacy maintenance

---

This change is 

[adamkewley]

Nice! Looks very reasonable to me.

I noticed that searchBinary is used in various parts of the codebase. Did you test that change locally or confirm that we already test coverage for it? My only comment is to consider a short unit test if it seems useful (perhaps for theManager class, which depends on it for retrieving integrator time steps).

Reviewed 17 of 17 files at r1, all commit messages. Reviewable status: :shipit: complete! all files reviewed, all discussions resolved (waiting on @adamkewley)

I haven't tested it yet, but I think that one way to do it would be to copy+paste the old implementation into a unit test and confirm it gives similar results.

From what I can see of it, its main usage purpose is to find an insertion point for data, but (imo) std::lower_bound alone would be better for this (it's used elsewhere): the behavior (as documented) seems likely to insert data one-too-early in a sequence (I'll have to check)

[nickbianco]

I haven't tested it yet, but I think that one way to do it would be to copy+paste the old implementation into a unit test and confirm it gives similar results.

Even if you confirmed this locally it would likely be fine, but a unit test would be safer. I'm fine with replacing usages of searchBinary with std::lower_bound if you want to add that here too.

[adamkewley]

I added a legacy-exercising unit test to ensure that the results will be the same. It found a bug in the implementation!

Assuming this passes CI, it should be ready to merge

[aymanhab]

@adamkewley Looks great, I'd only ask that you run swig and diff/compare the swig output since the Array class is used in numerous places across the API. It would be great to verify that the GUI builds with this branch. Thank you 🥇

[adamkewley]

This is held up by the SWIG check: building /w swig on Linux/WSL2 results in a missing preliminaries file and it's not entirely clear why the build depends on a file that doesn't exist

[adamkewley]

Think I found the bug: SWIG generation will fail if cmake is ran while the current working directory is opensim-core, because this execute_process call to generate SWIG's dependencies:

• https://github.com/opensim-org/opensim-core/blob/v4.3.1/cmake/OpenSimMacros.cmake#L644

Will short-circuit some of the dependencies to (e.g.) Bindings/preliminaries.i because SWIG prioritizes the current dir as the highest-prio search path. However, all paths from that step must be absolute because the build can run from a different directory (it usually does).

[adamkewley]

Java SWIG diff, before and after:

• https://gist.github.com/adamkewley/e4f4fdb851ce362fa1ad9f033a47226b

[adamkewley]

All changes in the java diff appear to be due to renamed variables and/or updated comment strings, so I'm guessing the SWIG API is going to be fine (unless someone's code depended on variable names O_o).

[adamkewley]

Not sure if this is ever used but is aSize == _size still noop?

@ayman to reply to this question, it's still a noop. resize only "fills in" with _defaultValue on vector growth, and will only ever reallocate if the new size is greater than the current capacity of the vector.