Undefined behavior

[zeeev]

Dear @lh3,

While running sanitation (address,undefined), I hit errors in IITree. I attempted debugging, but was unable to figure out the shifts. I would really appreciate it if you could take a look at this undefined behavior, and variable name masking. Let me know if I can help in any way.

Best wishes,

Zev

+  SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/third-party/cgranges/IITree.h:84:41 in
+  ../src/third-party/cgranges/IITree.h:84:54: runtime error: signed integer overflow: -9223372036854775808 - 1 cannot be represented in type 'long long'
+  SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/third-party/cgranges/IITree.h:84:54 in
+  ../src/third-party/cgranges/IITree.h:88:24: runtime error: shift exponent -1 is negative
+  SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/third-party/cgranges/IITree.h:88:24 in
+  ../src/third-party/cgranges/IITree.h:88:31: runtime error: shift exponent -1 is negative
+  SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../src/third-party/cgranges/IITree.h:88:31 in

[lh3]

What is the value of max_level? Do you use any negative numbers? PS: probably you are using an empty list.

[zeeev]

Dear @lh3,

Thanks for the reply. How can I check the max level? I'm using the cpp api. I assume I'm using the default. If a tree is empty is there a way to check first? I know these are pedantic issues, but I'd like to pass UBSAN and No warnings if possible.

Best,

Zev

[lh3]

You can modify IITree::overlap() such that it directly returns when max_level is negative. If that works, I can make the change on my end. Thanks.

[zeeev]

Hi @lh3,

	bool overlap(const S &st, const S &en, std::vector<size_t> &out) const {
		int t = 0;
		StackCell stack[64];
		out.clear();
		if(max_level < 0) return false;

This did the trick. All UBSAN tests passing.

[pb-cdunn]

Yes, this is a good fix. It occurs after calling index() on an empty tree.

[lh3]

Thanks for the confirmation. Changes made.

[zeeev]

Thanks @lh3!