src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java - bazel - Git at Google

 // Copyright 2014 The Bazel Authors. All rights reserved.
 //
 // Licensed under the Apache License, Version 2.0 (the "License");
 // you may not use this file except in compliance with the License.
 // You may obtain a copy of the License at
 //
 //    http://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS,
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.
 package com.google.devtools.build.lib.syntax;

 import com.google.common.base.Preconditions;
 import com.google.common.base.Strings;
 import com.google.common.collect.Ordering;
 import java.util.IllegalFormatException;
 import net.starlark.java.spelling.SpellChecker;

 /** Utilities used by the evaluator. */
 // TODO(adonovan): move all fundamental values and operators of the language to Starlark
 // class---equal, compare, getattr, index, slice, parse, exec, eval, and so on---and make this
 // private.
 public final class EvalUtils {

   private EvalUtils() {}

   /**
    * The exception that STARLARK_COMPARATOR might throw. This is an unchecked exception because
    * Comparator doesn't let us declare exceptions. It should normally be caught and wrapped in an
    * EvalException.
    */
   static class ComparisonException extends RuntimeException {
     ComparisonException(String msg) {
       super(msg);
     }
   }

   /**
    * Compare two Starlark values.
    *
    * <p>It may throw an unchecked exception ComparisonException that should be wrapped in an
    * EvalException.
    */
   // TODO(adonovan): consider what API to expose around comparison and ordering. Java's three-valued
   // comparator cannot properly handle weakly or partially ordered values such as IEEE754 floats.
   static final Ordering<Object> STARLARK_COMPARATOR =
       new Ordering<Object>() {
         private int compareLists(Sequence<?> o1, Sequence<?> o2) {
           if (o1 instanceof RangeList || o2 instanceof RangeList) {
             throw new ComparisonException("Cannot compare range objects");
           }

           for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) {
             int cmp = compare(o1.get(i), o2.get(i));
             if (cmp != 0) {
               return cmp;
             }
           }
           return Integer.compare(o1.size(), o2.size());
         }

         @Override
         @SuppressWarnings("unchecked")
         public int compare(Object o1, Object o2) {

           // optimize the most common cases

           if (o1 instanceof String && o2 instanceof String) {
             return ((String) o1).compareTo((String) o2);
           }
           if (o1 instanceof Integer && o2 instanceof Integer) {
             return Integer.compare((Integer) o1, (Integer) o2);
           }

           o1 = Starlark.fromJava(o1, null);
           o2 = Starlark.fromJava(o2, null);

           if (o1 instanceof Sequence
               && o2 instanceof Sequence
               && o1 instanceof Tuple == o2 instanceof Tuple) {
             return compareLists((Sequence) o1, (Sequence) o2);
           }

           if (o1 instanceof ClassObject) {
             throw new ComparisonException("Cannot compare structs");
           }
           try {
             return ((Comparable<Object>) o1).compareTo(o2);
           } catch (ClassCastException e) {
             throw new ComparisonException(
                 "Cannot compare " + Starlark.type(o1) + " with " + Starlark.type(o2));
           }
         }
       };

   /** Throws EvalException if x is not hashable. */
   static void checkHashable(Object x) throws EvalException {
     if (!isHashable(x)) {
       // This results in confusing errors such as "unhashable type: tuple".
       // TODO(adonovan): ideally the error message would explain which
       // element of, say, a tuple is unhashable. The only practical way
       // to implement this is by implementing isHashable as a call to
       // Object.hashCode within a try/catch, and requiring all
       // unhashable Starlark values to throw a particular unchecked exception
       // with a helpful error message.
       throw Starlark.errorf("unhashable type: '%s'", Starlark.type(x));
     }
   }

   /**
    * Reports whether a legal Starlark value is considered hashable to Starlark, and thus suitable as
    * a key in a dict.
    */
   static boolean isHashable(Object o) {
     // Bazel makes widespread assumptions that all Starlark values can be hashed
     // by Java code, so we cannot implement isHashable by having
     // StarlarkValue.hashCode throw an unchecked exception, which would be more
     // efficient. Instead, before inserting a value in a dict, we must first ask
     // it whether it isHashable, and then call its hashCode method only if so.
     // For structs and tuples, this unfortunately visits the object graph twice.
     //
     // One subtlety: the struct.isHashable recursively asks whether its
     // elements are immutable, not hashable. Consequently, even though a list
     // may not be used as a dict key (even if frozen), a struct containing
     // a list is hashable. TODO(adonovan): fix this inconsistency.
     // Requires an incompatible change flag.
     if (o instanceof StarlarkValue) {
       return ((StarlarkValue) o).isHashable();
     }
     return isImmutable(o);
   }

   /** Reports whether a Starlark value is assumed to be deeply immutable. */
   // TODO(adonovan): eliminate the concept of querying for immutability. It is currently used for
   // only one purpose, the precondition for adding an element to a Depset, but Depsets should check
   // hashability, like Dicts. (Similarly, querying for hashability should go: just attempt to hash a
   // value, and be prepared for it to fail.) In practice, a value may be immutable, either
   // inherently (e.g. string) or because it has become frozen, but we don't need to query for it.
   // Just attempt a mutation and be prepared for it to fail.
   // It is inefficient and potentially inconsistent to ask before doing.
   public static boolean isImmutable(Object x) {
     // NB: This is used as the basis for accepting objects in Depsets,
     // as well as for accepting objects as keys for Starlark dicts.

     if (x instanceof String || x instanceof Integer || x instanceof Boolean) {
       return true;
     } else if (x instanceof StarlarkValue) {
       return ((StarlarkValue) x).isImmutable();
     } else {
       throw new IllegalArgumentException("invalid Starlark value: " + x.getClass());
     }
   }

   static void addIterator(Object x) {
     if (x instanceof Mutability.Freezable) {
       ((Mutability.Freezable) x).updateIteratorCount(+1);
     }
   }

   static void removeIterator(Object x) {
     if (x instanceof Mutability.Freezable) {
       ((Mutability.Freezable) x).updateIteratorCount(-1);
     }
   }

   // The following functions for indexing and slicing match the behavior of Python.

   /**
    * Resolves a positive or negative index to an index in the range [0, length), or throws
    * EvalException if it is out of range. If the index is negative, it counts backward from length.
    */
   static int getSequenceIndex(int index, int length) throws EvalException {
     int actualIndex = index;
     if (actualIndex < 0) {
       actualIndex += length;
     }
     if (actualIndex < 0 || actualIndex >= length) {
       throw Starlark.errorf(
           "index out of range (index is %d, but sequence has %d elements)", index, length);
     }
     return actualIndex;
   }

   /**
    * Returns the effective index denoted by a user-supplied integer. First, if the integer is
    * negative, the length of the sequence is added to it, so an index of -1 represents the last
    * element of the sequence. Then, the integer is "clamped" into the inclusive interval [0,
    * length].
    */
   static int toIndex(int index, int length) {
     if (index < 0) {
       index += length;
     }

     if (index < 0) {
       return 0;
     } else if (index > length) {
       return length;
     } else {
       return index;
     }
   }

   /** @return true if x is Java null or Starlark None */
   public static boolean isNullOrNone(Object x) {
     return x == null || x == Starlark.NONE;
   }

   /** Returns the named field or method of value {@code x}, or null if not found. */
   // TODO(adonovan): publish this method as Starlark.getattr(Semantics, Mutability, Object, String).
   static Object getAttr(StarlarkThread thread, Object x, String name)
       throws EvalException, InterruptedException {
     StarlarkSemantics semantics = thread.getSemantics();
     Mutability mu = thread.mutability();

     // @StarlarkMethod-annotated field or method?
     MethodDescriptor method = CallUtils.getMethod(semantics, x.getClass(), name);
     if (method != null) {
       if (method.isStructField()) {
         return method.callField(x, semantics, mu);
       } else {
         return new BuiltinCallable(x, name, method);
       }
     }

     // user-defined field?
     if (x instanceof ClassObject) {
       Object field = ((ClassObject) x).getValue(semantics, name);
       if (field != null) {
         return Starlark.checkValid(field);
       }
     }

     return null;
   }

   static EvalException getMissingAttrException(
       Object object, String name, StarlarkSemantics semantics) {
     String suffix = "";
     if (object instanceof ClassObject) {
       String customErrorMessage = ((ClassObject) object).getErrorMessageForUnknownField(name);
       if (customErrorMessage != null) {
         return Starlark.errorf("%s", customErrorMessage);
       }
       suffix = SpellChecker.didYouMean(name, ((ClassObject) object).getFieldNames());
     } else {
       suffix = SpellChecker.didYouMean(name, CallUtils.getFieldNames(semantics, object));
     }
     return Starlark.errorf(
         "'%s' value has no field or method '%s'%s", Starlark.type(object), name, suffix);
   }

   /** Evaluates an eager binary operation, {@code x op y}. (Excludes AND and OR.) */
   static Object binaryOp(
       TokenKind op, Object x, Object y, StarlarkSemantics semantics, Mutability mu)
       throws EvalException {
     switch (op) {
       case PLUS:
         if (x instanceof Integer) {
           if (y instanceof Integer) {
             // int + int
             int xi = (Integer) x;
             int yi = (Integer) y;
             int z = xi + yi;
             // Overflow Detection, §2-13 Hacker's Delight:
             // "operands have the same sign and the sum
             // has a sign opposite to that of the operands."
             if (((xi ^ z) & (yi ^ z)) < 0) {
               throw Starlark.errorf("integer overflow in addition");
             }
             return z;
           }

         } else if (x instanceof String) {
           if (y instanceof String) {
             // string + string
             return (String) x + (String) y;
           }

         } else if (x instanceof Tuple) {
           if (y instanceof Tuple) {
             // tuple + tuple
             return Tuple.concat((Tuple<?>) x, (Tuple<?>) y);
           }

         } else if (x instanceof StarlarkList) {
           if (y instanceof StarlarkList) {
             // list + list
             return StarlarkList.concat((StarlarkList<?>) x, (StarlarkList<?>) y, mu);
           }

         }
         break;

       case PIPE:
         if (x instanceof Integer) {
           if (y instanceof Integer) {
             // int | int
             return ((Integer) x) | (Integer) y;
           }
         }
         break;

       case AMPERSAND:
         if (x instanceof Integer && y instanceof Integer) {
           // int & int
           return (Integer) x & (Integer) y;
         }
         break;

       case CARET:
         if (x instanceof Integer && y instanceof Integer) {
           // int ^ int
           return (Integer) x ^ (Integer) y;
         }
         break;

       case GREATER_GREATER:
         if (x instanceof Integer && y instanceof Integer) {
           // int >> int
           int xi = (Integer) x;
           int yi = (Integer) y;
           if (yi < 0) {
             throw Starlark.errorf("negative shift count: %d", yi);
           } else if (yi >= Integer.SIZE) {
             return xi < 0 ? -1 : 0;
           }
           return xi >> yi;
         }
         break;

       case LESS_LESS:
         if (x instanceof Integer && y instanceof Integer) {
           // int << int
           int xi = (Integer) x;
           int yi = (Integer) y;
           if (yi < 0) {
             throw Starlark.errorf("negative shift count: %d", yi);
           }
           int z = xi << yi; // only uses low 5 bits of yi
           if ((z >> yi) != xi || yi >= 32) {
             throw Starlark.errorf("integer overflow in left shift");
           }
           return z;
         }
         break;

       case MINUS:
         if (x instanceof Integer && y instanceof Integer) {
           // int - int
           int xi = (Integer) x;
           int yi = (Integer) y;
           int z = xi - yi;
           if (((xi ^ yi) & (xi ^ z)) < 0) {
             throw Starlark.errorf("integer overflow in subtraction");
           }
           return z;
         }
         break;

       case STAR:
         if (x instanceof Integer) {
           int xi = (Integer) x;
           if (y instanceof Integer) {
             // int * int
             long z = (long) xi * (long) (Integer) y;
             if ((int) z != z) {
               throw Starlark.errorf("integer overflow in multiplication");
             }
             return (int) z;
           } else if (y instanceof String) {
             // int * string
             return repeatString((String) y, xi);
           } else if (y instanceof Tuple) {
             //  int * tuple
             return ((Tuple<?>) y).repeat(xi);
           } else if (y instanceof StarlarkList) {
             // int * list
             return ((StarlarkList<?>) y).repeat(xi, mu);
           }

         } else if (x instanceof String) {
           if (y instanceof Integer) {
             // string * int
             return repeatString((String) x, (Integer) y);
           }

         } else if (x instanceof Tuple) {
           if (y instanceof Integer) {
             // tuple * int
             return ((Tuple<?>) x).repeat((Integer) y);
           }

         } else if (x instanceof StarlarkList) {
           if (y instanceof Integer) {
             // list * int
             return ((StarlarkList<?>) x).repeat((Integer) y, mu);
           }
         }
         break;

       case SLASH:
         throw Starlark.errorf("The `/` operator is not allowed. For integer division, use `//`.");

       case SLASH_SLASH:
         if (x instanceof Integer && y instanceof Integer) {
           // int // int
           int xi = (Integer) x;
           int yi = (Integer) y;
           if (yi == 0) {
             throw Starlark.errorf("integer division by zero");
           }
           // http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floors.html
           int quo = xi / yi;
           int rem = xi % yi;
           if ((xi < 0) != (yi < 0) && rem != 0) {
             quo--;
           }
           if (xi == Integer.MIN_VALUE && yi == -1) { // HD 2-13
             throw Starlark.errorf("integer overflow in division");
           }
           return quo;
         }
         break;

       case PERCENT:
         if (x instanceof Integer) {
           if (y instanceof Integer) {
             // int % int
             int xi = (Integer) x;
             int yi = (Integer) y;
             if (yi == 0) {
               throw Starlark.errorf("integer modulo by zero");
             }
             // In Starlark, the sign of the result is the sign of the divisor.
             int z = xi % yi;
             if ((xi < 0) != (yi < 0) && z != 0) {
               z += yi;
             }
             return z;
           }

         } else if (x instanceof String) {
           // string % any
           String xs = (String) x;
           try {
             if (y instanceof Tuple) {
               return Starlark.formatWithList(xs, (Tuple) y);
             } else {
               return Starlark.format(xs, y);
             }
           } catch (IllegalFormatException ex) {
             throw new EvalException(null, ex.getMessage());
           }
         }
         break;

       case EQUALS_EQUALS:
         return x.equals(y);

       case NOT_EQUALS:
         return !x.equals(y);

       case LESS:
         return compare(x, y) < 0;

       case LESS_EQUALS:
         return compare(x, y) <= 0;

       case GREATER:
         return compare(x, y) > 0;

       case GREATER_EQUALS:
         return compare(x, y) >= 0;

       case IN:
         if (y instanceof StarlarkIndexable) {
           return ((StarlarkIndexable) y).containsKey(semantics, x);
         } else if (y instanceof String) {
           if (!(x instanceof String)) {
             throw Starlark.errorf(
                 "'in <string>' requires string as left operand, not '%s'", Starlark.type(x));
           }
           return ((String) y).contains((String) x);
         }
         break;

       case NOT_IN:
         Object z = binaryOp(TokenKind.IN, x, y, semantics, mu);
         if (z != null) {
           return !Starlark.truth(z);
         }
         break;

       default:
         throw new AssertionError("not a binary operator: " + op);
     }

     // custom binary operator?
     if (x instanceof HasBinary) {
       Object z = ((HasBinary) x).binaryOp(op, y, true);
       if (z != null) {
         return z;
       }
     }
     if (y instanceof HasBinary) {
       Object z = ((HasBinary) y).binaryOp(op, x, false);
       if (z != null) {
         return z;
       }
     }

     throw Starlark.errorf(
         "unsupported binary operation: %s %s %s", Starlark.type(x), op, Starlark.type(y));
   }

   /** Implements comparison operators. */
   private static int compare(Object x, Object y) throws EvalException {
     try {
       return STARLARK_COMPARATOR.compare(x, y);
     } catch (ComparisonException e) {
       throw new EvalException(null, e.getMessage());
     }
   }

   private static String repeatString(String s, int n) {
     return n <= 0 ? "" : Strings.repeat(s, n);
   }

   /** Evaluates a unary operation. */
   static Object unaryOp(TokenKind op, Object x) throws EvalException {
     switch (op) {
       case NOT:
         return !Starlark.truth(x);

       case MINUS:
         if (x instanceof Integer) {
           int xi = (Integer) x;
           if (xi == Integer.MIN_VALUE) {
             throw Starlark.errorf("integer overflow in negation");
           }
           return -xi;
         }
         break;

       case PLUS:
         if (x instanceof Integer) {
           return x;
         }
         break;

       case TILDE:
         if (x instanceof Integer) {
           return ~((Integer) x);
         }
         break;

       default:
         /* fall through */
     }
     throw Starlark.errorf("unsupported unary operation: %s%s", op, Starlark.type(x));
   }

   /**
    * Returns the element of sequence or mapping {@code object} indexed by {@code key}.
    *
    * @throws EvalException if {@code object} is not a sequence or mapping.
    */
   static Object index(Mutability mu, StarlarkSemantics semantics, Object object, Object key)
       throws EvalException {
     if (object instanceof StarlarkIndexable) {
       Object result = ((StarlarkIndexable) object).getIndex(semantics, key);
       // TODO(bazel-team): We shouldn't have this fromJava call here. If it's needed at all,
       // it should go in the implementations of StarlarkIndexable#getIndex that produce non-Starlark
       // values.
       return result == null ? null : Starlark.fromJava(result, mu);
     } else if (object instanceof String) {
       String string = (String) object;
       int index = Starlark.toInt(key, "string index");
       index = getSequenceIndex(index, string.length());
       return string.substring(index, index + 1);
     } else {
       throw Starlark.errorf(
           "type '%s' has no operator [](%s)", Starlark.type(object), Starlark.type(key));
     }
   }

   /**
    * Updates an object as if by the Starlark statement {@code object[key] = value}.
    *
    * @throws EvalException if the object is not a list or dict.
    */
   static void setIndex(Object object, Object key, Object value) throws EvalException {
     if (object instanceof Dict) {
       @SuppressWarnings("unchecked")
       Dict<Object, Object> dict = (Dict<Object, Object>) object;
       dict.put(key, value, (Location) null);

     } else if (object instanceof StarlarkList) {
       @SuppressWarnings("unchecked")
       StarlarkList<Object> list = (StarlarkList<Object>) object;
       int index = Starlark.toInt(key, "list index");
       index = EvalUtils.getSequenceIndex(index, list.size());
       list.set(index, value, (Location) null);

     } else {
       throw Starlark.errorf(
           "can only assign an element in a dictionary or a list, not in a '%s'",
           Starlark.type(object));
     }
   }

   /**
    * Parses the input as a file, resolves it in the module environment using the specified options
    * and returns the syntax tree. Scan/parse/resolve errors are recorded in the StarlarkFile. It is
    * the caller's responsibility to inspect them.
    */
   public static StarlarkFile parseAndValidate(
       ParserInput input, FileOptions options, Module module) {
     StarlarkFile file = StarlarkFile.parse(input, options);
     Resolver.resolveFile(file, module);
     return file;
   }

   /**
    * Parses the input as a file, resolves it in the module environment using the specified options
    * and executes it. It returns None, unless the final statement is an expression, in which case it
    * returns the expression's value.
    */
   public static Object exec(
       ParserInput input, FileOptions options, Module module, StarlarkThread thread)
       throws SyntaxError.Exception, EvalException, InterruptedException {
     StarlarkFile file = parseAndValidate(input, options, module);
     if (!file.ok()) {
       throw new SyntaxError.Exception(file.errors());
     }
     return exec(file, module, thread);
   }

   /** Executes a parsed, resolved Starlark file in the given StarlarkThread. */
   public static Object exec(StarlarkFile file, Module module, StarlarkThread thread)
       throws EvalException, InterruptedException {
     Preconditions.checkNotNull(
         file.resolved,
         "cannot evaluate unresolved syntax (use other exec method, or parseAndValidate)");

     Tuple<Object> defaultValues = Tuple.empty();
     StarlarkFunction toplevel = new StarlarkFunction(file.resolved, defaultValues, module);

     return Starlark.fastcall(thread, toplevel, NOARGS, NOARGS);
   }

   /**
    * Parses the input as an expression, resolves it in the module environment using the specified
    * options, and evaluates it.
    */
   public static Object eval(
       ParserInput input, FileOptions options, Module module, StarlarkThread thread)
       throws SyntaxError.Exception, EvalException, InterruptedException {
     Expression expr = Expression.parse(input, options);

     Resolver.Function rfn = Resolver.resolveExpr(expr, module, options);

     // Turn expression into a no-arg StarlarkFunction.
     Tuple<Object> defaultValues = Tuple.empty();
     StarlarkFunction exprFunc = new StarlarkFunction(rfn, defaultValues, module);

     return Starlark.fastcall(thread, exprFunc, NOARGS, NOARGS);
   }

   private static final Object[] NOARGS = {};
 }
	// Copyright 2014 The Bazel Authors. All rights reserved.
	//
	// Licensed under the Apache License, Version 2.0 (the "License");
	// you may not use this file except in compliance with the License.
	// You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS,
	// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	// See the License for the specific language governing permissions and
	// limitations under the License.
	package com.google.devtools.build.lib.syntax;

	import com.google.common.base.Preconditions;
	import com.google.common.base.Strings;
	import com.google.common.collect.Ordering;
	import java.util.IllegalFormatException;
	import net.starlark.java.spelling.SpellChecker;

	/** Utilities used by the evaluator. */
	// TODO(adonovan): move all fundamental values and operators of the language to Starlark
	// class---equal, compare, getattr, index, slice, parse, exec, eval, and so on---and make this
	// private.
	public final class EvalUtils {

	private EvalUtils() {}

	/**
	* The exception that STARLARK_COMPARATOR might throw. This is an unchecked exception because
	* Comparator doesn't let us declare exceptions. It should normally be caught and wrapped in an
	* EvalException.
	*/
	static class ComparisonException extends RuntimeException {
	ComparisonException(String msg) {
	super(msg);
	}
	}

	/**
	* Compare two Starlark values.
	*
	* <p>It may throw an unchecked exception ComparisonException that should be wrapped in an
	* EvalException.
	*/
	// TODO(adonovan): consider what API to expose around comparison and ordering. Java's three-valued
	// comparator cannot properly handle weakly or partially ordered values such as IEEE754 floats.
	static final Ordering<Object> STARLARK_COMPARATOR =
	new Ordering<Object>() {
	private int compareLists(Sequence<?> o1, Sequence<?> o2) {
	if (o1 instanceof RangeList \|\| o2 instanceof RangeList) {
	throw new ComparisonException("Cannot compare range objects");
	}

	for (int i = 0; i < Math.min(o1.size(), o2.size()); i++) {
	int cmp = compare(o1.get(i), o2.get(i));
	if (cmp != 0) {
	return cmp;
	}
	}
	return Integer.compare(o1.size(), o2.size());
	}

	@Override
	@SuppressWarnings("unchecked")
	public int compare(Object o1, Object o2) {

	// optimize the most common cases

	if (o1 instanceof String && o2 instanceof String) {
	return ((String) o1).compareTo((String) o2);
	}
	if (o1 instanceof Integer && o2 instanceof Integer) {
	return Integer.compare((Integer) o1, (Integer) o2);
	}

	o1 = Starlark.fromJava(o1, null);
	o2 = Starlark.fromJava(o2, null);

	if (o1 instanceof Sequence
	&& o2 instanceof Sequence
	&& o1 instanceof Tuple == o2 instanceof Tuple) {
	return compareLists((Sequence) o1, (Sequence) o2);
	}

	if (o1 instanceof ClassObject) {
	throw new ComparisonException("Cannot compare structs");
	}
	try {
	return ((Comparable<Object>) o1).compareTo(o2);
	} catch (ClassCastException e) {
	throw new ComparisonException(
	"Cannot compare " + Starlark.type(o1) + " with " + Starlark.type(o2));
	}
	}
	};

	/** Throws EvalException if x is not hashable. */
	static void checkHashable(Object x) throws EvalException {
	if (!isHashable(x)) {
	// This results in confusing errors such as "unhashable type: tuple".
	// TODO(adonovan): ideally the error message would explain which
	// element of, say, a tuple is unhashable. The only practical way
	// to implement this is by implementing isHashable as a call to
	// Object.hashCode within a try/catch, and requiring all
	// unhashable Starlark values to throw a particular unchecked exception
	// with a helpful error message.
	throw Starlark.errorf("unhashable type: '%s'", Starlark.type(x));
	}
	}

	/**
	* Reports whether a legal Starlark value is considered hashable to Starlark, and thus suitable as
	* a key in a dict.
	*/
	static boolean isHashable(Object o) {
	// Bazel makes widespread assumptions that all Starlark values can be hashed
	// by Java code, so we cannot implement isHashable by having
	// StarlarkValue.hashCode throw an unchecked exception, which would be more
	// efficient. Instead, before inserting a value in a dict, we must first ask
	// it whether it isHashable, and then call its hashCode method only if so.
	// For structs and tuples, this unfortunately visits the object graph twice.
	//
	// One subtlety: the struct.isHashable recursively asks whether its
	// elements are immutable, not hashable. Consequently, even though a list
	// may not be used as a dict key (even if frozen), a struct containing
	// a list is hashable. TODO(adonovan): fix this inconsistency.
	// Requires an incompatible change flag.
	if (o instanceof StarlarkValue) {
	return ((StarlarkValue) o).isHashable();
	}
	return isImmutable(o);
	}

	/** Reports whether a Starlark value is assumed to be deeply immutable. */
	// TODO(adonovan): eliminate the concept of querying for immutability. It is currently used for
	// only one purpose, the precondition for adding an element to a Depset, but Depsets should check
	// hashability, like Dicts. (Similarly, querying for hashability should go: just attempt to hash a
	// value, and be prepared for it to fail.) In practice, a value may be immutable, either
	// inherently (e.g. string) or because it has become frozen, but we don't need to query for it.
	// Just attempt a mutation and be prepared for it to fail.
	// It is inefficient and potentially inconsistent to ask before doing.
	public static boolean isImmutable(Object x) {
	// NB: This is used as the basis for accepting objects in Depsets,
	// as well as for accepting objects as keys for Starlark dicts.

	if (x instanceof String \|\| x instanceof Integer \|\| x instanceof Boolean) {
	return true;
	} else if (x instanceof StarlarkValue) {
	return ((StarlarkValue) x).isImmutable();
	} else {
	throw new IllegalArgumentException("invalid Starlark value: " + x.getClass());
	}
	}

	static void addIterator(Object x) {
	if (x instanceof Mutability.Freezable) {
	((Mutability.Freezable) x).updateIteratorCount(+1);
	}
	}

	static void removeIterator(Object x) {
	if (x instanceof Mutability.Freezable) {
	((Mutability.Freezable) x).updateIteratorCount(-1);
	}
	}

	// The following functions for indexing and slicing match the behavior of Python.

	/**
	* Resolves a positive or negative index to an index in the range [0, length), or throws
	* EvalException if it is out of range. If the index is negative, it counts backward from length.
	*/
	static int getSequenceIndex(int index, int length) throws EvalException {
	int actualIndex = index;
	if (actualIndex < 0) {
	actualIndex += length;
	}
	if (actualIndex < 0 \|\| actualIndex >= length) {
	throw Starlark.errorf(
	"index out of range (index is %d, but sequence has %d elements)", index, length);
	}
	return actualIndex;
	}

	/**
	* Returns the effective index denoted by a user-supplied integer. First, if the integer is
	* negative, the length of the sequence is added to it, so an index of -1 represents the last
	* element of the sequence. Then, the integer is "clamped" into the inclusive interval [0,
	* length].
	*/
	static int toIndex(int index, int length) {
	if (index < 0) {
	index += length;
	}

	if (index < 0) {
	return 0;
	} else if (index > length) {
	return length;
	} else {
	return index;
	}
	}

	/** @return true if x is Java null or Starlark None */
	public static boolean isNullOrNone(Object x) {
	return x == null \|\| x == Starlark.NONE;
	}

	/** Returns the named field or method of value {@code x}, or null if not found. */
	// TODO(adonovan): publish this method as Starlark.getattr(Semantics, Mutability, Object, String).
	static Object getAttr(StarlarkThread thread, Object x, String name)
	throws EvalException, InterruptedException {
	StarlarkSemantics semantics = thread.getSemantics();
	Mutability mu = thread.mutability();

	// @StarlarkMethod-annotated field or method?
	MethodDescriptor method = CallUtils.getMethod(semantics, x.getClass(), name);
	if (method != null) {
	if (method.isStructField()) {
	return method.callField(x, semantics, mu);
	} else {
	return new BuiltinCallable(x, name, method);
	}
	}

	// user-defined field?
	if (x instanceof ClassObject) {
	Object field = ((ClassObject) x).getValue(semantics, name);
	if (field != null) {
	return Starlark.checkValid(field);
	}
	}

	return null;
	}

	static EvalException getMissingAttrException(
	Object object, String name, StarlarkSemantics semantics) {
	String suffix = "";
	if (object instanceof ClassObject) {
	String customErrorMessage = ((ClassObject) object).getErrorMessageForUnknownField(name);
	if (customErrorMessage != null) {
	return Starlark.errorf("%s", customErrorMessage);
	}
	suffix = SpellChecker.didYouMean(name, ((ClassObject) object).getFieldNames());
	} else {
	suffix = SpellChecker.didYouMean(name, CallUtils.getFieldNames(semantics, object));
	}
	return Starlark.errorf(
	"'%s' value has no field or method '%s'%s", Starlark.type(object), name, suffix);
	}

	/** Evaluates an eager binary operation, {@code x op y}. (Excludes AND and OR.) */
	static Object binaryOp(
	TokenKind op, Object x, Object y, StarlarkSemantics semantics, Mutability mu)
	throws EvalException {
	switch (op) {
	case PLUS:
	if (x instanceof Integer) {
	if (y instanceof Integer) {
	// int + int
	int xi = (Integer) x;
	int yi = (Integer) y;
	int z = xi + yi;
	// Overflow Detection, §2-13 Hacker's Delight:
	// "operands have the same sign and the sum
	// has a sign opposite to that of the operands."
	if (((xi ^ z) & (yi ^ z)) < 0) {
	throw Starlark.errorf("integer overflow in addition");
	}
	return z;
	}

	} else if (x instanceof String) {
	if (y instanceof String) {
	// string + string
	return (String) x + (String) y;
	}

	} else if (x instanceof Tuple) {
	if (y instanceof Tuple) {
	// tuple + tuple
	return Tuple.concat((Tuple<?>) x, (Tuple<?>) y);
	}

	} else if (x instanceof StarlarkList) {
	if (y instanceof StarlarkList) {
	// list + list
	return StarlarkList.concat((StarlarkList<?>) x, (StarlarkList<?>) y, mu);
	}

	}
	break;

	case PIPE:
	if (x instanceof Integer) {
	if (y instanceof Integer) {
	// int \| int
	return ((Integer) x) \| (Integer) y;
	}
	}
	break;

	case AMPERSAND:
	if (x instanceof Integer && y instanceof Integer) {
	// int & int
	return (Integer) x & (Integer) y;
	}
	break;

	case CARET:
	if (x instanceof Integer && y instanceof Integer) {
	// int ^ int
	return (Integer) x ^ (Integer) y;
	}
	break;

	case GREATER_GREATER:
	if (x instanceof Integer && y instanceof Integer) {
	// int >> int
	int xi = (Integer) x;
	int yi = (Integer) y;
	if (yi < 0) {
	throw Starlark.errorf("negative shift count: %d", yi);
	} else if (yi >= Integer.SIZE) {
	return xi < 0 ? -1 : 0;
	}
	return xi >> yi;
	}
	break;

	case LESS_LESS:
	if (x instanceof Integer && y instanceof Integer) {
	// int << int
	int xi = (Integer) x;
	int yi = (Integer) y;
	if (yi < 0) {
	throw Starlark.errorf("negative shift count: %d", yi);
	}
	int z = xi << yi; // only uses low 5 bits of yi
	if ((z >> yi) != xi \|\| yi >= 32) {
	throw Starlark.errorf("integer overflow in left shift");
	}
	return z;
	}
	break;

	case MINUS:
	if (x instanceof Integer && y instanceof Integer) {
	// int - int
	int xi = (Integer) x;
	int yi = (Integer) y;
	int z = xi - yi;
	if (((xi ^ yi) & (xi ^ z)) < 0) {
	throw Starlark.errorf("integer overflow in subtraction");
	}
	return z;
	}
	break;

	case STAR:
	if (x instanceof Integer) {
	int xi = (Integer) x;
	if (y instanceof Integer) {
	// int * int
	long z = (long) xi * (long) (Integer) y;
	if ((int) z != z) {
	throw Starlark.errorf("integer overflow in multiplication");
	}
	return (int) z;
	} else if (y instanceof String) {
	// int * string
	return repeatString((String) y, xi);
	} else if (y instanceof Tuple) {
	// int * tuple
	return ((Tuple<?>) y).repeat(xi);
	} else if (y instanceof StarlarkList) {
	// int * list
	return ((StarlarkList<?>) y).repeat(xi, mu);
	}

	} else if (x instanceof String) {
	if (y instanceof Integer) {
	// string * int
	return repeatString((String) x, (Integer) y);
	}

	} else if (x instanceof Tuple) {
	if (y instanceof Integer) {
	// tuple * int
	return ((Tuple<?>) x).repeat((Integer) y);
	}

	} else if (x instanceof StarlarkList) {
	if (y instanceof Integer) {
	// list * int
	return ((StarlarkList<?>) x).repeat((Integer) y, mu);
	}
	}
	break;

	case SLASH:
	throw Starlark.errorf("The `/` operator is not allowed. For integer division, use `//`.");

	case SLASH_SLASH:
	if (x instanceof Integer && y instanceof Integer) {
	// int // int
	int xi = (Integer) x;
	int yi = (Integer) y;
	if (yi == 0) {
	throw Starlark.errorf("integer division by zero");
	}
	// http://python-history.blogspot.com/2010/08/why-pythons-integer-division-floors.html
	int quo = xi / yi;
	int rem = xi % yi;
	if ((xi < 0) != (yi < 0) && rem != 0) {
	quo--;
	}
	if (xi == Integer.MIN_VALUE && yi == -1) { // HD 2-13
	throw Starlark.errorf("integer overflow in division");
	}
	return quo;
	}
	break;

	case PERCENT:
	if (x instanceof Integer) {
	if (y instanceof Integer) {
	// int % int
	int xi = (Integer) x;
	int yi = (Integer) y;
	if (yi == 0) {
	throw Starlark.errorf("integer modulo by zero");
	}
	// In Starlark, the sign of the result is the sign of the divisor.
	int z = xi % yi;
	if ((xi < 0) != (yi < 0) && z != 0) {
	z += yi;
	}
	return z;
	}

	} else if (x instanceof String) {
	// string % any
	String xs = (String) x;
	try {
	if (y instanceof Tuple) {
	return Starlark.formatWithList(xs, (Tuple) y);
	} else {
	return Starlark.format(xs, y);
	}
	} catch (IllegalFormatException ex) {
	throw new EvalException(null, ex.getMessage());
	}
	}
	break;

	case EQUALS_EQUALS:
	return x.equals(y);

	case NOT_EQUALS:
	return !x.equals(y);

	case LESS:
	return compare(x, y) < 0;

	case LESS_EQUALS:
	return compare(x, y) <= 0;

	case GREATER:
	return compare(x, y) > 0;

	case GREATER_EQUALS:
	return compare(x, y) >= 0;

	case IN:
	if (y instanceof StarlarkIndexable) {
	return ((StarlarkIndexable) y).containsKey(semantics, x);
	} else if (y instanceof String) {
	if (!(x instanceof String)) {
	throw Starlark.errorf(
	"'in <string>' requires string as left operand, not '%s'", Starlark.type(x));
	}
	return ((String) y).contains((String) x);
	}
	break;

	case NOT_IN:
	Object z = binaryOp(TokenKind.IN, x, y, semantics, mu);
	if (z != null) {
	return !Starlark.truth(z);
	}
	break;

	default:
	throw new AssertionError("not a binary operator: " + op);
	}

	// custom binary operator?
	if (x instanceof HasBinary) {
	Object z = ((HasBinary) x).binaryOp(op, y, true);
	if (z != null) {
	return z;
	}
	}
	if (y instanceof HasBinary) {
	Object z = ((HasBinary) y).binaryOp(op, x, false);
	if (z != null) {
	return z;
	}
	}

	throw Starlark.errorf(
	"unsupported binary operation: %s %s %s", Starlark.type(x), op, Starlark.type(y));
	}

	/** Implements comparison operators. */
	private static int compare(Object x, Object y) throws EvalException {
	try {
	return STARLARK_COMPARATOR.compare(x, y);
	} catch (ComparisonException e) {
	throw new EvalException(null, e.getMessage());
	}
	}

	private static String repeatString(String s, int n) {
	return n <= 0 ? "" : Strings.repeat(s, n);
	}

	/** Evaluates a unary operation. */
	static Object unaryOp(TokenKind op, Object x) throws EvalException {
	switch (op) {
	case NOT:
	return !Starlark.truth(x);

	case MINUS:
	if (x instanceof Integer) {
	int xi = (Integer) x;
	if (xi == Integer.MIN_VALUE) {
	throw Starlark.errorf("integer overflow in negation");
	}
	return -xi;
	}
	break;

	case PLUS:
	if (x instanceof Integer) {
	return x;
	}
	break;

	case TILDE:
	if (x instanceof Integer) {
	return ~((Integer) x);
	}
	break;

	default:
	/* fall through */
	}
	throw Starlark.errorf("unsupported unary operation: %s%s", op, Starlark.type(x));
	}

	/**
	* Returns the element of sequence or mapping {@code object} indexed by {@code key}.
	*
	* @throws EvalException if {@code object} is not a sequence or mapping.
	*/
	static Object index(Mutability mu, StarlarkSemantics semantics, Object object, Object key)
	throws EvalException {
	if (object instanceof StarlarkIndexable) {
	Object result = ((StarlarkIndexable) object).getIndex(semantics, key);
	// TODO(bazel-team): We shouldn't have this fromJava call here. If it's needed at all,
	// it should go in the implementations of StarlarkIndexable#getIndex that produce non-Starlark
	// values.
	return result == null ? null : Starlark.fromJava(result, mu);
	} else if (object instanceof String) {
	String string = (String) object;
	int index = Starlark.toInt(key, "string index");
	index = getSequenceIndex(index, string.length());
	return string.substring(index, index + 1);
	} else {
	throw Starlark.errorf(
	"type '%s' has no operator [](%s)", Starlark.type(object), Starlark.type(key));
	}
	}

	/**
	* Updates an object as if by the Starlark statement {@code object[key] = value}.
	*
	* @throws EvalException if the object is not a list or dict.
	*/
	static void setIndex(Object object, Object key, Object value) throws EvalException {
	if (object instanceof Dict) {
	@SuppressWarnings("unchecked")
	Dict<Object, Object> dict = (Dict<Object, Object>) object;
	dict.put(key, value, (Location) null);

	} else if (object instanceof StarlarkList) {
	@SuppressWarnings("unchecked")
	StarlarkList<Object> list = (StarlarkList<Object>) object;
	int index = Starlark.toInt(key, "list index");
	index = EvalUtils.getSequenceIndex(index, list.size());
	list.set(index, value, (Location) null);

	} else {
	throw Starlark.errorf(
	"can only assign an element in a dictionary or a list, not in a '%s'",
	Starlark.type(object));
	}
	}

	/**
	* Parses the input as a file, resolves it in the module environment using the specified options
	* and returns the syntax tree. Scan/parse/resolve errors are recorded in the StarlarkFile. It is
	* the caller's responsibility to inspect them.
	*/
	public static StarlarkFile parseAndValidate(
	ParserInput input, FileOptions options, Module module) {
	StarlarkFile file = StarlarkFile.parse(input, options);
	Resolver.resolveFile(file, module);
	return file;
	}

	/**
	* Parses the input as a file, resolves it in the module environment using the specified options
	* and executes it. It returns None, unless the final statement is an expression, in which case it
	* returns the expression's value.
	*/
	public static Object exec(
	ParserInput input, FileOptions options, Module module, StarlarkThread thread)
	throws SyntaxError.Exception, EvalException, InterruptedException {
	StarlarkFile file = parseAndValidate(input, options, module);
	if (!file.ok()) {
	throw new SyntaxError.Exception(file.errors());
	}
	return exec(file, module, thread);
	}

	/** Executes a parsed, resolved Starlark file in the given StarlarkThread. */
	public static Object exec(StarlarkFile file, Module module, StarlarkThread thread)
	throws EvalException, InterruptedException {
	Preconditions.checkNotNull(
	file.resolved,
	"cannot evaluate unresolved syntax (use other exec method, or parseAndValidate)");

	Tuple<Object> defaultValues = Tuple.empty();
	StarlarkFunction toplevel = new StarlarkFunction(file.resolved, defaultValues, module);

	return Starlark.fastcall(thread, toplevel, NOARGS, NOARGS);
	}

	/**
	* Parses the input as an expression, resolves it in the module environment using the specified
	* options, and evaluates it.
	*/
	public static Object eval(
	ParserInput input, FileOptions options, Module module, StarlarkThread thread)
	throws SyntaxError.Exception, EvalException, InterruptedException {
	Expression expr = Expression.parse(input, options);

	Resolver.Function rfn = Resolver.resolveExpr(expr, module, options);

	// Turn expression into a no-arg StarlarkFunction.
	Tuple<Object> defaultValues = Tuple.empty();
	StarlarkFunction exprFunc = new StarlarkFunction(rfn, defaultValues, module);

	return Starlark.fastcall(thread, exprFunc, NOARGS, NOARGS);
	}

	private static final Object[] NOARGS = {};
	}