Support bitwise operations
Add support for `~`, `&`, `|`, `^`, `<<`, `>>` bitwise operations.
Implements: https://github.com/bazelbuild/starlark/issues/20#issuecomment-456647994
Closes #8903.
PiperOrigin-RevId: 259732302
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
index 8ff947b..d2b334e 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BinaryOperatorExpression.java
@@ -189,6 +189,18 @@
case PIPE:
return pipe(x, y, env, location);
+ case AMPERSAND:
+ return and(x, y, location);
+
+ case CARET:
+ return xor(x, y, location);
+
+ case GREATER_GREATER:
+ return rightShift(x, y, location);
+
+ case LESS_LESS:
+ return leftShift(x, y, location);
+
case MINUS:
return minus(x, y, location);
@@ -346,7 +358,9 @@
/** Implements 'x | y'. */
private static Object pipe(Object x, Object y, Environment env, Location location)
throws EvalException {
- if (x instanceof SkylarkNestedSet) {
+ if (x instanceof Integer && y instanceof Integer) {
+ return ((Integer) x) | ((Integer) y);
+ } else if (x instanceof SkylarkNestedSet) {
if (env.getSemantics().incompatibleDepsetUnion()) {
throw new EvalException(
location,
@@ -447,6 +461,50 @@
throw typeException(x, y, TokenKind.PERCENT, location);
}
+ /** Implements 'x & y'. */
+ private static Object and(Object x, Object y, Location location) throws EvalException {
+ if (x instanceof Integer && y instanceof Integer) {
+ return (Integer) x & (Integer) y;
+ }
+ throw typeException(x, y, TokenKind.AMPERSAND, location);
+ }
+
+ /** Implements 'x ^ y'. */
+ private static Object xor(Object x, Object y, Location location) throws EvalException {
+ if (x instanceof Integer && y instanceof Integer) {
+ return (Integer) x ^ (Integer) y;
+ }
+ throw typeException(x, y, TokenKind.CARET, location);
+ }
+
+ /** Implements 'x >> y'. */
+ private static Object rightShift(Object x, Object y, Location location) throws EvalException {
+ if (x instanceof Integer && y instanceof Integer) {
+ if ((Integer) y < 0) {
+ throw new EvalException(location, "negative shift count: " + y);
+ } else if ((Integer) y >= Integer.SIZE) {
+ return ((Integer) x < 0) ? -1 : 0;
+ }
+ return (Integer) x >> (Integer) y;
+ }
+ throw typeException(x, y, TokenKind.GREATER_GREATER, location);
+ }
+
+ /** Implements 'x << y'. */
+ private static Object leftShift(Object x, Object y, Location location) throws EvalException {
+ if (x instanceof Integer && y instanceof Integer) {
+ if ((Integer) y < 0) {
+ throw new EvalException(location, "negative shift count: " + y);
+ }
+ Integer result = (Integer) x << (Integer) y;
+ if (!rightShift(result, y, location).equals(x)) {
+ throw new ArithmeticException("integer overflow");
+ }
+ return result;
+ }
+ throw typeException(x, y, TokenKind.LESS_LESS, location);
+ }
+
/** Throws an exception signifying incorrect types for the given operator. */
private static EvalException typeException(Object x, Object y, TokenKind op, Location location) {
// NB: this message format is identical to that used by CPython 2.7.6 or 3.4.0,
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Lexer.java b/src/main/java/com/google/devtools/build/lib/syntax/Lexer.java
index c7f424b..fd11e55 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Lexer.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Lexer.java
@@ -52,6 +52,9 @@
.put('*', TokenKind.STAR_EQUALS)
.put('/', TokenKind.SLASH_EQUALS)
.put('%', TokenKind.PERCENT_EQUALS)
+ .put('^', TokenKind.CARET_EQUALS)
+ .put('&', TokenKind.AMPERSAND_EQUALS)
+ .put('|', TokenKind.PIPE_EQUALS)
.build();
private final EventHandler eventHandler;
@@ -809,10 +812,26 @@
popParen();
break;
case '>':
- setToken(TokenKind.GREATER, pos - 1, pos);
+ if (lookaheadIs(0, '>') && lookaheadIs(1, '=')) {
+ setToken(TokenKind.GREATER_GREATER_EQUALS, pos - 1, pos + 2);
+ pos += 2;
+ } else if (lookaheadIs(0, '>')) {
+ setToken(TokenKind.GREATER_GREATER, pos - 1, pos + 1);
+ pos += 1;
+ } else {
+ setToken(TokenKind.GREATER, pos - 1, pos);
+ }
break;
case '<':
- setToken(TokenKind.LESS, pos - 1, pos);
+ if (lookaheadIs(0, '<') && lookaheadIs(1, '=')) {
+ setToken(TokenKind.LESS_LESS_EQUALS, pos - 1, pos + 2);
+ pos += 2;
+ } else if (lookaheadIs(0, '<')) {
+ setToken(TokenKind.LESS_LESS, pos - 1, pos + 1);
+ pos += 1;
+ } else {
+ setToken(TokenKind.LESS, pos - 1, pos);
+ }
break;
case ':':
setToken(TokenKind.COLON, pos - 1, pos);
@@ -835,6 +854,15 @@
case '%':
setToken(TokenKind.PERCENT, pos - 1, pos);
break;
+ case '~':
+ setToken(TokenKind.TILDE, pos - 1, pos);
+ break;
+ case '&':
+ setToken(TokenKind.AMPERSAND, pos - 1, pos);
+ break;
+ case '^':
+ setToken(TokenKind.CARET, pos - 1, pos);
+ break;
case '/':
if (lookaheadIs(0, '/') && lookaheadIs(1, '=')) {
setToken(TokenKind.SLASH_SLASH_EQUALS, pos - 1, pos + 2);
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
index fa25198..f1912e9 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Parser.java
@@ -134,6 +134,11 @@
.put(TokenKind.SLASH_EQUALS, TokenKind.SLASH)
.put(TokenKind.SLASH_SLASH_EQUALS, TokenKind.SLASH_SLASH)
.put(TokenKind.PERCENT_EQUALS, TokenKind.PERCENT)
+ .put(TokenKind.AMPERSAND_EQUALS, TokenKind.AMPERSAND)
+ .put(TokenKind.CARET_EQUALS, TokenKind.CARET)
+ .put(TokenKind.PIPE_EQUALS, TokenKind.PIPE)
+ .put(TokenKind.GREATER_GREATER_EQUALS, TokenKind.GREATER_GREATER)
+ .put(TokenKind.LESS_LESS_EQUALS, TokenKind.LESS_LESS)
.build();
/**
@@ -155,6 +160,9 @@
TokenKind.IN,
TokenKind.NOT_IN),
EnumSet.of(TokenKind.PIPE),
+ EnumSet.of(TokenKind.CARET),
+ EnumSet.of(TokenKind.AMPERSAND),
+ EnumSet.of(TokenKind.GREATER_GREATER, TokenKind.LESS_LESS),
EnumSet.of(TokenKind.MINUS, TokenKind.PLUS),
EnumSet.of(TokenKind.SLASH, TokenKind.SLASH_SLASH, TokenKind.STAR, TokenKind.PERCENT));
@@ -680,6 +688,13 @@
UnaryOperatorExpression plus = new UnaryOperatorExpression(TokenKind.PLUS, expr);
return setLocation(plus, start, expr);
}
+ case TILDE:
+ {
+ nextToken();
+ Expression expr = parsePrimaryWithSuffix();
+ UnaryOperatorExpression tilde = new UnaryOperatorExpression(TokenKind.TILDE, expr);
+ return setLocation(tilde, start, expr);
+ }
default:
{
syntaxError("expected expression");
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/TokenKind.java b/src/main/java/com/google/devtools/build/lib/syntax/TokenKind.java
index b85743c..aca3523 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/TokenKind.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/TokenKind.java
@@ -18,11 +18,14 @@
* A TokenKind is an enumeration of each different kind of lexical symbol.
*/
public enum TokenKind {
-
+ AMPERSAND("&"),
+ AMPERSAND_EQUALS("&="),
AND("and"),
AS("as"),
ASSERT("assert"),
BREAK("break"),
+ CARET("^"),
+ CARET_EQUALS("^="),
CLASS("class"),
COLON(":"),
COMMA(","),
@@ -42,6 +45,8 @@
GLOBAL("global"),
GREATER(">"),
GREATER_EQUALS(">="),
+ GREATER_GREATER(">>"),
+ GREATER_GREATER_EQUALS(">>="),
IDENTIFIER("identifier"),
IF("if"),
ILLEGAL("illegal character"),
@@ -55,6 +60,8 @@
LBRACKET("["),
LESS("<"),
LESS_EQUALS("<="),
+ LESS_LESS("<<"),
+ LESS_LESS_EQUALS("<<="),
LOAD("load"),
LPAREN("("),
MINUS("-"),
@@ -70,6 +77,7 @@
PERCENT("%"),
PERCENT_EQUALS("%="),
PIPE("|"),
+ PIPE_EQUALS("|="),
PLUS("+"),
PLUS_EQUALS("+="),
RAISE("raise"),
@@ -86,6 +94,7 @@
STAR_EQUALS("*="),
STAR_STAR("**"),
STRING("string literal"),
+ TILDE("~"),
TRY("try"),
WHILE("while"),
WITH("with"),
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/UnaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/syntax/UnaryOperatorExpression.java
index b16a07f..be44002 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/UnaryOperatorExpression.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/UnaryOperatorExpression.java
@@ -19,7 +19,7 @@
/** A UnaryOperatorExpression represents a unary operator expression, 'op x'. */
public final class UnaryOperatorExpression extends Expression {
- private final TokenKind op; // NOT, MINUS or PLUS
+ private final TokenKind op; // NOT, TILDE, MINUS or PLUS
private final Expression x;
public UnaryOperatorExpression(TokenKind op, Expression x) {
@@ -63,30 +63,34 @@
return !EvalUtils.toBoolean(value);
case MINUS:
- if (!(value instanceof Integer)) {
- throw new EvalException(
- loc,
- String.format(
- "unsupported operand type for -: '%s'", EvalUtils.getDataTypeName(value)));
+ if (value instanceof Integer) {
+ try {
+ return Math.negateExact((Integer) value);
+ } catch (ArithmeticException e) {
+ // Fails for -MIN_INT.
+ throw new EvalException(loc, e.getMessage());
+ }
}
- try {
- return Math.negateExact((Integer) value);
- } catch (ArithmeticException e) {
- // Fails for -MIN_INT.
- throw new EvalException(loc, e.getMessage());
- }
- case PLUS:
- if (!(value instanceof Integer)) {
- throw new EvalException(
- loc,
- String.format(
- "unsupported operand type for +: '%s'", EvalUtils.getDataTypeName(value)));
- }
- return value;
+ break;
+ case PLUS:
+ if (value instanceof Integer) {
+ return value;
+ }
+ break;
+
+ case TILDE:
+ if (value instanceof Integer) {
+ return ~((Integer) value);
+ }
+ break;
+
+ // ignore any other operator and proceed to report an error
default:
- throw new AssertionError("Unsupported unary operator: " + op);
}
+ throw new EvalException(
+ loc,
+ String.format("unsupported unary operation: %s%s", op, EvalUtils.getDataTypeName(value)));
}
@Override
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
index d199a91..544a583 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvaluationTest.java
@@ -62,7 +62,7 @@
.testStatement("8 % 3", 2)
.testIfErrorContains("unsupported operand type(s) for %: 'int' and 'string'", "3 % 'foo'")
.testStatement("-5", -5)
- .testIfErrorContains("unsupported operand type for -: 'string'", "-'foo'");
+ .testIfErrorContains("unsupported unary operation: -string", "-'foo'");
}
@Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java b/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java
index bc4d8cc..2e14cb8 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/ParserTest.java
@@ -473,6 +473,10 @@
assertThat(parseFile("x *= 1").toString()).isEqualTo("[x *= 1\n]");
assertThat(parseFile("x /= 1").toString()).isEqualTo("[x /= 1\n]");
assertThat(parseFile("x %= 1").toString()).isEqualTo("[x %= 1\n]");
+ assertThat(parseFile("x |= 1").toString()).isEqualTo("[x |= 1\n]");
+ assertThat(parseFile("x &= 1").toString()).isEqualTo("[x &= 1\n]");
+ assertThat(parseFile("x <<= 1").toString()).isEqualTo("[x <<= 1\n]");
+ assertThat(parseFile("x >>= 1").toString()).isEqualTo("[x >>= 1\n]");
}
@Test
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index 87ba491..a0f9cab 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -1504,7 +1504,7 @@
new SkylarkTest("--incompatible_depset_union=false")
.testStatement("str(depset([1, 3]) | depset([1, 2]))", "depset([1, 2, 3])")
.testStatement("str(depset([1, 2]) | [1, 3])", "depset([1, 2, 3])")
- .testIfExactError("unsupported operand type(s) for |: 'int' and 'int'", "2 | 4");
+ .testIfExactError("unsupported operand type(s) for |: 'int' and 'bool'", "2 | False");
}
@Test
diff --git a/src/test/starlark/testdata/int.sky b/src/test/starlark/testdata/int.sky
index 91212da..d4710cf 100644
--- a/src/test/starlark/testdata/int.sky
+++ b/src/test/starlark/testdata/int.sky
@@ -73,3 +73,66 @@
1 // 0 ### integer division by zero
---
1 % 0 ### integer modulo by zero
+---
+
+# bitwise
+
+def f():
+ x = 2
+ x &= 1
+ assert_eq(x, 0)
+ x = 0
+ x |= 2
+ assert_eq(x, 2)
+ x ^= 3
+ assert_eq(x, 1)
+ x <<= 2
+ assert_eq(x, 4)
+ x >>=2
+ assert_eq(x, 1)
+
+f()
+---
+assert_eq(1 | 2, 3)
+assert_eq(3 | 6, 7)
+assert_eq(7 | 0, 7)
+assert_eq(7 & 0, 0)
+assert_eq(7 & 7, 7)
+assert_eq(7 & 2, 2)
+assert_eq((1|2) & (2|4), 2)
+assert_eq(1 ^ 2, 3)
+assert_eq(2 ^ 2, 0)
+assert_eq(-6 ^ 0, -6)
+assert_eq(1 | 0 ^ 1, 1) # check | and ^ operators precedence
+assert_eq(~1, -2)
+assert_eq(~-2, 1)
+assert_eq(~0, -1)
+assert_eq(~6, -7)
+assert_eq(~0, -1)
+assert_eq(~2147483647, -2147483647 - 1);
+assert_eq(1 << 2, 4)
+assert_eq(7 << 0, 7)
+assert_eq(-1 << 31, -2147483647 - 1)
+assert_eq(2 >> 1, 1)
+assert_eq(7 >> 0, 7)
+assert_eq(0 >> 0, 0)
+assert_eq(1000 >> 100, 0)
+assert_eq(-10 >> 1000, -1)
+
+# precedence
+
+assert_eq(8 | 3 ^ 4 & -2, 15)
+assert_eq(~8 >> 1 | 3 ^ 4 & -2 << 2 * 3 + 4 // -2, -5)
+
+---
+1 & False ### unsupported operand type(s) for &: 'int' and 'bool'
+---
+"a" ^ 5 ### unsupported operand type(s) for ^: 'string' and 'int'
+---
+~False ### unsupported unary operation: ~bool
+---
+1 << 31 ### integer overflow
+---
+1 << -4 ### negative shift count: -4
+---
+2 >> -1 ### negative shift count: -1
