Modernization of several core classes

[DNKpp]

As I'm quite new to godot, I wanted to get a picture of some of the engine internals. I was very surprises when I discovered many copy-paste code, lots of manual raw loops, which in fact mimic stl algorithms, and some questionable class designs. Don't get me wrong, I'm not in the position right now to make a general statement about the code quality of godot, but there are definitely core classes (CowData, Vector, Array, Variant) which can be modernized. Making more use of the stl leads to less maintainable code and will most likely as fast or even faster than now.
But lets start the discussion at Vector. https://github.com/godotengine/godot/blob/master/core/templates/vector.h

Better Iterator Support

The first improvement could be extended the use of iterators, as those are very powerful abstractions over tedious manual indices. Yes, that's probably a matter of taste, but as c++ (and especially c++20) sees iterators as one of their core-concepts, it's totally worth getting used to them. Especially if we can get rid of some hard to understandable code. As you can see, Vector already has (Const)Iterators but they are in fact nothing else than pointers. We can get rid of both classes by simply adding:

using Iterator = T *;
using ConstIterator = const T *;

This will make our iterators instantly a RandomAccessIterator.
and as we support bidirectional iteration,

using ReverseIterator = std::reverse_iterator<Iterator>;
using ConstReverseIterator = std::reverse_iterator<ConstIterator>;

The iterator functions are then simply that:

_NO_DISCARD_ Iterator begin() { return _cowdata.ptrw(); }
_NO_DISCARD_ Iterator end() { return _cowdata.ptrw() + _cowdata.size(); }
_NO_DISCARD_ ConstIterator begin() const { return _cowdata.ptr(); }
_NO_DISCARD_ ConstIterator end() const { return _cowdata.ptr() + _cowdata.size(); }
_NO_DISCARD_ ConstIterator cbegin() const { return begin(); }
_NO_DISCARD_ ConstIterator cend() const { return end(); }
_NO_DISCARD_ ReverseIterator rbegin() { return std::reverse_iterator{ end() }; }
_NO_DISCARD_ ReverseIterator rend() { return std::reverse_iterator{ begin() }; }
_NO_DISCARD_ ConstReverseIterator rbegin() const { return std::reverse_iterator{ end() }; }
_NO_DISCARD_ ConstReverseIterator rend() const { return std::reverse_iterator{ begin() }; }
_NO_DISCARD_ ConstReverseIterator crbegin() const { return rbegin(); }
_NO_DISCARD_ ConstReverseIterator crend() const { return rend(); }

Note: The cbegin, cend, etc. aren't of course not explicitly necessary, but as Vector is often making a deep copy when working with .ptrw(), I recommend adding them, because users can then easily select the immutable iterators.

Extended iterator support will at least come in handy, when godot moves to c++20, but are also currently a big deal with the existing stl algorithms and libraries such as ranges-v3.

Make use of the iterators

The Vector class implements many algorithms manually, which we can simply replace with stl counterparts:

void fill(const T &p_elem) {
    std::fill(begin(), end(), p_elem);
}

void reverse() {
    std::reverse(begin(), end());
}
private:
template <class Begin, class End>
_NO_DISCARD_ static int _find(const Begin beginIter, const End endIter, const T &p_value) {
	const auto iter = std::find(beginIter, endIter, p_value);
	return iter == endIter ? -1 : static_cast<int>(std::distance(beginIter, iter));
}

public:
_NO_DISCARD_ int find(const T &p_value, const int p_from = 0) const {
	return _find(begin() + p_from, end(), p_value);
}

_NO_DISCARD_ int rfind(const T &p_value, const int p_from = 0) const {
	return _find(rbegin() + p_from, rend(), p_value);
}

_NO_DISCARD_ int count(const T &p_val) const {
	return std::count(begin(), end(), p_val);
}

_NO_DISCARD_ bool has(const T &p_value) const {
	const auto endItr = end();
	return std::find(begin(), endItr, p_value) != endItr;
}

_NO_DISCARD_ bool operator==(const Vector<T> &p_arr) const {
	return std::equal(begin(), end(), p_arr.begin(), p_arr.end());
}

_NO_DISCARD_ bool operator!=(const Vector<T> &p_arr) const {
	return !(*this == p_arr);
}

The Vector also offers a binary search, which is implemented in an other file. We can get rid of the include and replace them with

_NO_DISCARD_ int bsearch(const T &p_value, bool p_before) const {
	return bsearch_custom<std::less<>>(p_value, p_before);
}

template <class Comparator, class Value, class... Args>
_NO_DISCARD_ int bsearch_custom(const Value &p_value, bool p_before, Args &&...args) const {
	const ConstIterator beginIter = begin();
	const ConstIterator endIter = end();
	const ConstIterator iter = p_before
			? std::lower_bound(beginIter, endIter, p_value, Comparator{ std::forward<Args>(args)... })
			: std::upper_bound(beginIter, endIter, p_value, Comparator{ std::forward<Args>(args)... });
	return iter == endIter ? -1 : static_cast<int>(std::distance(beginIter, iter));
}

One interesting thing is, that the class documentation recommends using Vector for "large arrays", but then uses the insertion sort as sorting algorithm, which scales quite bad for larger ranges. std::sort uses the quicksort algorithm, which is far more efficent for larger arrays, thus the whole array_sort.h header can be removed and the sort simply implemented via stl:

void sort() {
	sort_custom<std::less<>>();
}

template <class Comparator, class... Args>
void sort_custom(Args &&...args) {
	std::sort(begin(), end(), Comparator{ std::forward<Args>(args)... });
}

What the hacks?!

From my point of view, there are several design flaws within that class.

const vs non-const get Function

In contrast to the const ref returned by the const overload of get, the non-const get Function always returns a copy of the retrieved value, because the Vector trys to only expose immutable data. I don't think that's a nice and clean design as this has its own flaws and may lead to surprising results for users of that class, as both overloads in fact do different things. I suggest removing the non-const get.

VectorWriteProxy

VectorWriteProxy is one of the dirties tricks I have ever seen in c++. I think we can do better and simply get rid of the operator [] overloads, as we already have get and set functions, which reflect our use-case very well. In fact this is simply another redundance.

Crazy Copy Constructor

The copy constructor is a huge hack. If someone tries copying the Vector, they will simply receive a completely independent empty Vector. There should be a better solution, even if its simply deleting the copy.

Explicit function aliases

push_back and append are simply aliases for each other. I think godot 4 alpha is a good time for removing redundant functionalities. I would probably go with the append and rename the append_array also to append. But that's clearly a matter of taste.

Erase seems unintuitive

erase searches for a value and erases it once. Wouldn't it be more intuitive if it erases all appearances of that value?

So, what now?

I invested some time and applied most of the changes I have in mind for that vector class, without changing too much of the interface. Have a look here: https://pastebin.com/HiSmw4A4
Note, that isn't tested yet, may contain some compile errors and is not finally thought about, but it's probably enough to get the idea what I'm talking about. Is that something the godot team is interested in? Then I would make a more complete pull request and have also a look at the other mentioned classes.

Greetings

[Calinou]

See also #3058.

Note that Godot's philosophy is to prefer the use of simple C-like constructs over using modern C++ constructs. This makes the codebase easier to understand for people who aren't C++ experts (we have a lot of contributors for whom C++ is not their primary language).

Explicit function aliases

push_back and append are simply aliases for each other. I think godot 4 alpha is a good time for removing redundant functionalities. I would probably go with the append and rename the append_array also to append. But that's clearly a matter of taste.

This was proposed in godotengine/godot#44382 and was rejected.

[alekh-ai]

I think append and append_array work differently.

[DNKpp]

See also #3058.

Good to see. But its from 2021, so when will you make a decision about that topic?

Note that Godot's philosophy is to prefer the use of simple C-like constructs over using modern C++ constructs. This makes the codebase easier to understand for people who aren't C++ experts (we have a lot of contributors for whom C++ is not their primary language).

Well, don't know if that's really a good idea. As you are explicitly targeting c++, you should write c++. Doing c-things in c++ is most often a bad idea and will lead to UB. See VectorWriteProxy. That happens if some fancy c-coders attempt to put their c knowledge into c++. In c that might be valid, in c++ its definitely not. On the top-level c++ isn't much harder than any other language; especially not harder than fancy c. I bet every programmer can understand what std::find(begin(), end(), value) does and therefore its easy to adapt. Nobody has to look twice whether the algorithm works and what it does. It's well known and tested. Writing the same algorithm manually leads inevitably to harder to read, error prone and less maintainable code. And it's getting duplicated everywhere. This is an excerpt from array.cpp

Variant Array::min() const {
	Variant minval;
	for (int i = 0; i < size(); i++) {
		if (i == 0) {
			minval = get(i);
		} else {
			bool valid;
			Variant ret;
			Variant test = get(i);
			Variant::evaluate(Variant::OP_LESS, test, minval, ret, valid);
			if (!valid) {
				return Variant(); //not a valid comparison
			}
			if (bool(ret)) {
				//is less
				minval = test;
			}
		}
	}
	return minval;
}

Variant Array::max() const {
	Variant maxval;
	for (int i = 0; i < size(); i++) {
		if (i == 0) {
			maxval = get(i);
		} else {
			bool valid;
			Variant ret;
			Variant test = get(i);
			Variant::evaluate(Variant::OP_GREATER, test, maxval, ret, valid);
			if (!valid) {
				return Variant(); //not a valid comparison
			}
			if (bool(ret)) {
				//is less
				maxval = test;
			}
		}
	}
	return maxval;
}

Exactly the same code is duplicated, except the comparison differs. Even the comments are the same; but one is simply not correct. And then I said nothing about the performance hit, due to the repeated i == 0 check on each iteration.

It's not that I propose any fancy c++ expert level stuff, those are simply basics. Enabling iterators where applicable and using them, will help making godot more stable and maintainable in the long run.

Explicit function aliases

push_back and append are simply aliases for each other. I think godot 4 alpha is a good time for removing redundant functionalities. I would probably go with the append and rename the append_array also to append. But that's clearly a matter of taste.

This was proposed in godotengine/godot#44382 and was rejected.

Well, that's ok for me. Was just an spontanious idea ;)

EDIT: I can fully understand the need for simple top-level code, so I don't mind doing raw loop iterations and so on in several node classes if it helps users. But from my point of view, the core of the engine has to be correct, efficent and clean.

[Calinou]

Good to see. But its from 2021, so when will you make a decision about that topic?

We have a huge proposal backlog (many of them being more essential than the proposal I linked). As a result, we don't have an ETA on making decisions like these. However, we're entering feature freeze for 4.0 in a few days, so this will be postponed for 4.1 at the earliest if it's ever accepted.