Repository: godot
Issue: Light2D-tracking code (also occluders, likely others) depends on undefined behavior
Labels: bug,topic:core,topic:rendering,topic:2d

**Godot version:** master`

**OS/device including version:** n/a

**Issue description:**

While trying to track down some strange behavior involving the interaction of a moving light and a stationary one, I discovered that the light-tracking code unwittingly relies on undefined behavior -- i.e. it performs operations that are specifically forbidden by well-formed C++ code.

1. When a light is added to the canvas, it is first allocated using `canvas_light_create` (https://github.com/godotengine/godot/blob/master/servers/rendering/rendering_server_canvas.cpp#L1007) which ultimately calls `new`.

2. Lights are tracked in the `lights` member of a `struct Canvas` (https://github.com/godotengine/godot/blob/master/servers/rendering/rendering_server_canvas.h).  This is a `Set<RasterizerCanvas::Light *>` -- a set of "pointer to RasterizierCanvas::Light".

3. The `Set` class (https://github.com/godotengine/godot/blob/master/core/set.h#L40) is based on a binary tree.

4. The default comparison operator for `Set` is `Comparator<T>` (defined here: https://github.com/godotengine/godot/blob/master/core/typedefs.h#L218 )

```
template <class T>
struct Comparator {
	_ALWAYS_INLINE_ bool operator()(const T &p_a, const T &p_b) const { return (p_a < p_b); }
};
```

5. Since `T` here is `RasterizerCanvas::Light *`, and there are no template specializations for `Comparator`, this boils down to direct pointer comparison.

However, in C and C++, the results of comparing two pointers using `<` or `>` is *undefined* unless both pointers come from the same allocation (i.e. array declaration, `malloc`, or `new`).  There are some special exceptions, but none of them apply here.

The most significant consequence of this is that, if the compiler's optimizer becomes aggressive enough, it could make some assumptions that cause the application to break in highly surprising ways:

- That the only objects ever passed into the Set were allocated independently.  In that case, the only defined comparison that will ever occur is a light with itself; therefore, the comparison `less(a, b)` can simply always be false, which would cause some very interesting effects.

- That the first comparison check, if any, will always use '<' to compare two unrelated (i.e. separately allocated) pointers.  Since that's undefined behavior, the compiler can assume that no comparisons will ever be made (the resulting program is likely to crash immediately on startup, or it will never add more than one light, or maybe it won't ever add any lights to the canvas at all.)


I'll be honest, there's not a lot of good, simple ways to fix this.  

- The ideal method would likely be to have the Set be of _references_, not pointers; the mistake would have produced a compile-time error.  
   However, you can't modify a reference, so the element allocation would have to be adjusted to call a non-default constructor.  Plus, of course, all the code that uses `Set` would have to be modified accordingly.

- Switching to a hash table would work, although, unless you're willing to take a dependency on the standard library, I don't see a portable way to produce a hashcode from a pointer.

The least-invasive-prone way I can think to fix this would be to do:

```
template<class T>
struct RidComparator {
	_ALWAYS_INLINE_ bool operator()(const T &p_a, const T &p_b) const {
		return (p_a->primary_rid() < p_b->primary_rid());
	}
};

template <class T, class C = RidComparator<T>, class A = DefaultAllocator>
class RidSet : public Set<T, C, A>
{
};
```

then and stick a `primary_rid` method on `Light` and `LightOccluderInstance` and whatnot, returning the RID that uniquely identifies the object in question.  However, while I'm certain that doing this would _work_, I don't know if there's a better way.


**Steps to reproduce:** n/a

**Minimal reproduction project:** n/a