Pretty cool. It might help if the PR had some ReQL bitwise query tests to go with it. See: https://github.com/rethinkdb/rethinkdb/tree/next/test/rql_test/src/math_logic

Related issues: #1401, #1018

@bchavez Thank you for the feedback. Yes, I saw the tests in that directory, but I cannot run the tests for some reason. I have no idea what I was doing wrong, and this is what I've been stuck (logs from a Docker container, but also occurs on my host machine):

Got error while shutting down server at exit: Server cluster_uztbzj stopped unexpectedly with return code: -5
Traceback (most recent call last):
  File "/home/rethinkdb/src/test/rql_test/../common/driver.py", line 73, in endRunningServers
    server.check_and_stop()
  File "/home/rethinkdb/src/test/rql_test/../common/driver.py", line 881, in check_and_stop
    raise RuntimeError('%s %s stopped unexpectedly with return code: %r' % (self.server_type.capitalize(), self._name, self.returncode))
RuntimeError: Server cluster_uztbzj stopped unexpectedly with return code: -5

@lyubomyr-shaydariv You're under no obligation to write tests, I'd be happy to add the tests for you in order to get this merged.

I'll try and look into the test failure.

@srh It would be fantastic! Thank you!

_{(I do believe I just run the tests in a wrong way, and, if necessary, I'll provide the Docker files I've tried to build (succeeds) and test (fails) with.)}

OK, here's some feedback about bit shifting. I think I'm going to make some changes before merging this so I want to get your opinion.

1. To be consistent with other ReQL commands like mod, we should require that the values be integers instead of truncating them.
2. The size of long isn't consistent across platforms. We should use int32_t and uint32_t, or int64_t and uint64_t.
3. If the right hand argument to shift operators in C++ is out of range, we get undefined behavior, so we need to avoid that.
4. We don't need an arithmetic / logical right shift distinction because users have the full range of integers from -2^53 to 2^53. If they want logical right shift behavior, they can just use non-negative values.

I think maybe we should make the behavior like this:

1. Only offer the shift commands SAL and SAR. They require their parameters be integers in the -2^53<=..<2^53 range, the second parameter being non-negative, with the return value being defined to be sal(x, y) => (x * (2**y)) (handling an infinite result with error), and sar(x, y) => floor(x / (2**y)). It's the user's job to attach mod or bitAnd to sal operations if they need to simulate n-bit integers. (It's kind of uncomfortable for us to decide for the user what the sal behavior on too-negative values should be, otherwise.)

I'll note, if we ever add the datatype for unbounded integers ("bignums"), this produces the identical value to what bignum shift behavior looks like. This means we don't have multiple distinct notions of bitshifting floating around. Until we add fixed width integers.

2. Bitwise and, or, xor, and not, should require integer parameters bounded in the range -2^53<=..<2^53, casts them to int64_t, and performs the integer bitwise operation, then converts back to double.

Having the range be 2^53<=..<2^53 is kind of weird-looking -- it lets not(2^53-1) evaluate to -2^53 and back. Treating it like an int64_t, the 53 least significant bits of the integer can be anything, and the remaining bits are either all 0 or all 1, for positive or negative values.

3. Maybe I'll implement support for and/or/xor/not on binary objects.

4. The Java driver should be variadic for the and/or/xor operations.

To be consistent with other ReQL commands like mod, we should require that the values be integers instead of truncating them.

I didn’t know that mod requires both arguments to be integer, and I mostly tried to mimic JavaScript behavior and JavaScript had real influence on how it now works in my branch for all bitwise operations. For example, it can easily operate on doubles truncating them where necessary. Why JavaScript? No clue, probably because of Data Explorer. :) Since I don’t write in C++, it may take longer to get it fixed from my side. Therefore all 8 operations should operate on explicit integers only, and if any of arguments are non-integers, an error should be thrown, right?
(EDIT: I'm not sure if I've done it right. Please see https://github.com/lyubomyr-shaydariv/rethinkdb/commits/bitwise-review for the commit with a log message "Make bitwise operations accept integer operands only" (no commit hash since I'm going to amend it if it's done wrong))

The size of long isn't consistent across platforms. We should use int32_t and uint32_t, or int64_t and uint64_t.

Oh, I knew that C/C++ int/long widths are not consistent across platforms, but I totally missed it and what you use for constant-width integers. I’ll fix it, thank you!
(EDIT: Fixed)

If the right hand argument to shift operators in C++ is out of range, we get undefined behavior, so we need to avoid that.

I guess, it should throw an error then?
(EDIT: See below)

We don't need an arithmetic / logical right shift distinction because users have the full range of integers from -2^53 to 2^53. If they want logical right shift behavior, they can just use non-negative values.

I was thinking of logical operations as operations that are consistent to their arithmetic counterparts with slightly different semantics doing exactly the same what JavaScript/node.js do. I don’t have any solid opinion here (+ neither for big numbers nor for binaries), but I think that having both arithmetic and logic bitwise operations may have sense for systems where numbers already have a specific integer range (at least from what I understood in your comment). Sorry it’s really hard to tell much about it, because I was just trying to add a simple bitwise operations scenario to get rid of r.js in my code, and now I see it requires much more design attention than I initially thought. :) You decide.

The Java driver should be variadic for the and/or/xor operations.

You’re right, I missed the , "*"] definition. Shift operations should be variadic too. I'll fix it.
(EDIT: Fixed)

It should throw an error (because C++ exceptions are used to implement errors in the ReQL interpreter). I'm implementing it right now.

@srh I've made some edits at the bitwise-review branch, but I'm really confused on how bitshift operations must really work. I don't believe I made it right (especially (DBL_MANT_DIG + 1) in order to make the right-shift get 0 from any value despite it seems to contradict with what the standard says).

At that branch

const P = 9007199254740992;
const N = -P;
r.range(55)
  .map(e => ({
    '#': e,
    '?<<': r.branch(e.le(53), r(1).bitSal(e), 'undefined'),
    'N>>': r(N).bitShr(e),
    'N>>>': r(N).bitSar(e),
    'P>>': r(P).bitShr(e),
    'P>>>': r(P).bitSar(e),
  }))

produces

Could you please review? If you could make the necessary fixes at the bitwise-review branch, I'd appreciate it very and very much! Thank you!

Your use of DBL_MANT_DIG+1 is correct if you want it to be possible to shift 2^53 to zero. Negative numbers will stop at -1. Your code looks very good, especially for somebody that doesn't write C++. The problem that you're encountering is with bitShr -- it's converting to uint64_t (by adding 2^64) and then doing a right shift. This can make sense for 32-bit shifting (if we're copying Javascript) or 64-bit shifting (if we've only got a 64-bit signed integer type, like Java does) but it's pretty weird when the bound on integer range is 2^53.

Before your last update, I had already made a branch to improve performance and also to change the semantic behavior of the functions (to what I think they should be). You can see them in my branch here: https://github.com/srh/rethinkdb/commits/sam/bitwise

I'll go over them now. Some of this is obvious but I want to overexplain the changes because you say you're not used to C++.

The first commit avoids smart quotes in the docs, to be consistent with the rest of the docs, which also avoid smart quotes. (Maybe the docs should use smart quotes consistently instead.)

The second commit address the and/or/not/xor operators. The parameters are now restricted to the range 2^53<=..<2^53. The type of op is changed to a C-style function that works on int64_t values. This avoids the overhead of making intermediate datum_t objects and converting integers back and forth between doubles. (This does not change semantics. However, if 2^53 were a legal argument value, then semantics would have changed for the expression r.or(2^53, 2, 0), because the intermediate acc value, 2^53+2, would no longer be rejected by a call to as_int().) I also initialized op using lambdas, which does exactly the same thing as if they were implemented with static methods or global functions. The lambdas compile to a C-style function pointer because they do not capture any local variables. This just saves on lines of code: less scrolling for the reader.

The third commit changes the API so that bit_sal and bit_sar are the only functions, and they only take two parameters. I think this is better than making the functions variadic, because using a different number of parameters would be a very rare use case. In the C++ implementation, you can see that this time I didn't use lambdas, because the functions are pretty big. Also, I used nullptr (new in C++11) instead of 0. Personally I would have used NULL before, but that's just me.

The third commit also changes the behavior of shifting to that I described before.

My fourth commit is just idiotic. In my sleep-deprived stupor I looked at your most recent changes, noticed bit_not_term_t, and thought, "I didn't change this to check the range properly!" And somehow I managed to make that change to bit_not_term_t without noticing it already had bit_arith_ranged_int in there.

The fifth commit just adds a static assertion.

Edit: It still needs tests. And I might get rid of the function pointer and just use if-then (because the CPU usually runs that faster).

I added tests, and squashed/merged onto next as of 1601118.

Thank you!

There is still room for debate in terms of the question, what should the user API be. A name other than "sal" and "sar" might be appropriate for the shifting operations. Some people would like binary objects to be supported for the and/or/xor/not operations.

I didn't update the ReQL version, but that shouldn't be necessary because these are brand new commands. But... that should be investigated. Made issue #6550 to make a note of that.

@srh Wow, thank you! I didn't have much time the last days to complete everything to meet your detailed review comments, but I really appreciate how you took over all the necessary fixes and made it as it has to be keeping a sharp eye on my mistakes, typos and even tests I was not able to run. This is absolutely fantastic! It was a great time to bring a new microcontribuion to a great tool RethinkDB is and learn new stuff. Thank you very and very much!