// Copyright 2014 Google Inc. 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.Joiner;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Ordering;
import com.google.devtools.build.lib.collect.nestedset.Order;
import com.google.devtools.build.lib.events.Event;
import com.google.devtools.build.lib.events.Location;
import com.google.devtools.build.lib.syntax.ClassObject.SkylarkClassObject;
import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
import com.google.devtools.build.lib.syntax.SkylarkSignature.Param;
import com.google.devtools.build.lib.syntax.SkylarkSignatureProcessor.HackHackEitherList;
import com.google.devtools.build.lib.syntax.Type.ConversionException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.ExecutionException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* A helper class containing built in functions for the Build and the Build Extension Language.
*/
public class MethodLibrary {
private MethodLibrary() {}
// TODO(bazel-team):
// the Build language and Skylark currently have different list types:
// the Build language uses plain java List (usually ArrayList) which is mutable and accepts
// any argument, whereas Skylark uses SkylarkList which is immutable and accepts only
// arguments of the same kind. Some methods below use HackHackEitherList as a magic marker
// to indicate that either kind of lists is used depending on the evaluation context.
// It might be a good idea to either have separate methods for the two languages where it matters,
// or to unify the two languages so they use the same data structure (which might require
// updating all existing clients).
// Convert string index in the same way Python does.
// If index is negative, starts from the end.
// If index is outside bounds, it is restricted to the valid range.
private static int clampIndex(int index, int length) {
if (index < 0) {
index += length;
}
return Math.max(Math.min(index, length), 0);
}
// Emulate Python substring function
// It converts out of range indices, and never fails
private static String pythonSubstring(String str, int start, Object end, String msg)
throws ConversionException {
if (start == 0 && EvalUtils.isNullOrNone(end)) {
return str;
}
start = clampIndex(start, str.length());
int stop;
if (EvalUtils.isNullOrNone(end)) {
stop = str.length();
} else {
stop = clampIndex(Type.INTEGER.convert(end, msg), str.length());
}
if (start >= stop) {
return "";
}
return str.substring(start, stop);
}
private static int getListIndex(Object key, int listSize, Location loc)
throws ConversionException, EvalException {
// Get the nth element in the list
int index = Type.INTEGER.convert(key, "index operand");
if (index < 0) {
index += listSize;
}
if (index < 0 || index >= listSize) {
throw new EvalException(loc, "List index out of range (index is "
+ index + ", but list has " + listSize + " elements)");
}
return index;
}
// supported string methods
@SkylarkSignature(name = "join", objectType = StringModule.class, returnType = String.class,
doc = "Returns a string in which the string elements of the argument have been "
+ "joined by this string as a separator. Example: "
+ "
\"|\".join([\"a\", \"b\", \"c\"]) == \"a|b|c\"
",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string, a separator."),
@Param(name = "elements", type = HackHackEitherList.class, doc = "The objects to join.")})
private static BuiltinFunction join = new BuiltinFunction("join") {
public String invoke(String self, Object elements) throws ConversionException {
List> seq = Type.OBJECT_LIST.convert(elements, "'join.elements' argument");
return Joiner.on(self).join(seq);
}
};
@SkylarkSignature(name = "lower", objectType = StringModule.class, returnType = String.class,
doc = "Returns the lower case version of this string.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string, to convert to lower case.")})
private static BuiltinFunction lower = new BuiltinFunction("lower") {
public String invoke(String self) {
return self.toLowerCase();
}
};
@SkylarkSignature(name = "upper", objectType = StringModule.class, returnType = String.class,
doc = "Returns the upper case version of this string.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string, to convert to upper case.")})
private static BuiltinFunction upper = new BuiltinFunction("upper") {
public String invoke(String self) {
return self.toUpperCase();
}
};
@SkylarkSignature(name = "replace", objectType = StringModule.class, returnType = String.class,
doc = "Returns a copy of the string in which the occurrences "
+ "of old have been replaced with new, optionally restricting "
+ "the number of replacements to maxsplit.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "old", type = String.class, doc = "The string to be replaced."),
@Param(name = "new", type = String.class, doc = "The string to replace with.")},
optionalPositionals = {
@Param(name = "maxsplit", type = Integer.class, noneable = true, defaultValue = "None",
doc = "The maximum number of replacements.")},
useLocation = true)
private static BuiltinFunction replace = new BuiltinFunction("replace") {
public String invoke(String self, String oldString, String newString, Object maxSplitO,
Location loc) throws EvalException, ConversionException {
StringBuffer sb = new StringBuffer();
Integer maxSplit = Type.INTEGER.convertOptional(
maxSplitO, "'maxsplit' argument of 'replace'", /*label*/null, Integer.MAX_VALUE);
try {
Matcher m = Pattern.compile(oldString, Pattern.LITERAL).matcher(self);
for (int i = 0; i < maxSplit && m.find(); i++) {
m.appendReplacement(sb, Matcher.quoteReplacement(newString));
}
m.appendTail(sb);
} catch (IllegalStateException e) {
throw new EvalException(loc, e.getMessage() + " in call to replace");
}
return sb.toString();
}
};
@SkylarkSignature(name = "split", objectType = StringModule.class,
returnType = HackHackEitherList.class,
doc = "Returns a list of all the words in the string, using sep "
+ "as the separator, optionally limiting the number of splits to maxsplit.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sep", type = String.class, doc = "The string to split on.")},
optionalPositionals = {
@Param(name = "maxsplit", type = Integer.class, noneable = true, defaultValue = "None",
doc = "The maximum number of splits.")},
useEnvironment = true,
useLocation = true)
private static BuiltinFunction split = new BuiltinFunction("split") {
public Object invoke(String self, String sep, Object maxSplitO, Location loc,
Environment env) throws ConversionException, EvalException {
int maxSplit = Type.INTEGER.convertOptional(
maxSplitO, "'split' argument of 'split'", /*label*/null, -2);
// + 1 because the last result is the remainder, and default of -2 so that after +1 it's -1
String[] ss = Pattern.compile(sep, Pattern.LITERAL).split(self, maxSplit + 1);
return convert(Arrays.asList(ss), env);
}
};
@SkylarkSignature(name = "rsplit", objectType = StringModule.class,
returnType = HackHackEitherList.class,
doc = "Returns a list of all the words in the string, using sep "
+ "as the separator, optionally limiting the number of splits to maxsplit. "
+ "Except for splitting from the right, this method behaves like split().",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sep", type = String.class, doc = "The string to split on.")},
optionalPositionals = {
@Param(name = "maxsplit", type = Integer.class, noneable = true,
defaultValue = "None", doc = "The maximum number of splits.")},
useEnvironment = true,
useLocation = true)
private static BuiltinFunction rsplit = new BuiltinFunction("rsplit") {
@SuppressWarnings("unused")
public Object invoke(String self, String sep, Object maxSplitO, Location loc, Environment env)
throws ConversionException, EvalException {
int maxSplit =
Type.INTEGER.convertOptional(maxSplitO, "'split' argument of 'split'", null, -1);
List result;
try {
result = stringRSplit(self, sep, maxSplit);
} catch (IllegalArgumentException ex) {
throw new EvalException(loc, ex);
}
return convert(result, env);
}
};
/**
* Splits the given string into a list of words, using {@code separator} as a
* delimiter.
*
*
At most {@code maxSplits} will be performed, going from right to left.
*
* @param input The input string.
* @param separator The separator string.
* @param maxSplits The maximum number of splits. Negative values mean unlimited splits.
* @return A list of words
* @throws IllegalArgumentException
*/
private static List stringRSplit(String input, String separator, int maxSplits)
throws IllegalArgumentException {
if (separator.isEmpty()) {
throw new IllegalArgumentException("Empty separator");
}
if (maxSplits <= 0) {
maxSplits = Integer.MAX_VALUE;
}
LinkedList result = new LinkedList<>();
String[] parts = input.split(Pattern.quote(separator), -1);
int sepLen = separator.length();
int remainingLength = input.length();
int splitsSoFar = 0;
// Copies parts from the array into the final list, starting at the end (because
// it's rsplit), as long as fewer than maxSplits splits are performed. The
// last spot in the list is reserved for the remaining string, whose length
// has to be tracked throughout the loop.
for (int pos = parts.length - 1; (pos >= 0) && (splitsSoFar < maxSplits); --pos) {
String current = parts[pos];
result.addFirst(current);
++splitsSoFar;
remainingLength -= sepLen + current.length();
}
if (splitsSoFar == maxSplits && remainingLength >= 0) {
result.addFirst(input.substring(0, remainingLength));
}
return result;
}
@SkylarkSignature(name = "partition", objectType = StringModule.class,
returnType = HackHackEitherList.class,
doc = "Splits the input string at the first occurrence of the separator "
+ "sep and returns the resulting partition as a three-element "
+ "list of the form [substring_before, separator, substring_after].",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string.")},
optionalPositionals = {
@Param(name = "sep", type = String.class,
defaultValue = "' '", doc = "The string to split on, default is space (\" \").")},
useEnvironment = true,
useLocation = true)
private static BuiltinFunction partition = new BuiltinFunction("partition") {
@SuppressWarnings("unused")
public Object invoke(String self, String sep, Location loc, Environment env)
throws EvalException {
return partitionWrapper(self, sep, true, env, loc);
}
};
@SkylarkSignature(name = "rpartition", objectType = StringModule.class,
returnType = HackHackEitherList.class,
doc = "Splits the input string at the last occurrence of the separator "
+ "sep and returns the resulting partition as a three-element "
+ "list of the form [substring_before, separator, substring_after].",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string.")},
optionalPositionals = {
@Param(name = "sep", type = String.class,
defaultValue = "' '", doc = "The string to split on, default is space (\" \").")},
useEnvironment = true,
useLocation = true)
private static BuiltinFunction rpartition = new BuiltinFunction("rpartition") {
@SuppressWarnings("unused")
public Object invoke(String self, String sep, Location loc, Environment env)
throws EvalException {
return partitionWrapper(self, sep, false, env, loc);
}
};
/**
* Wraps the stringPartition() method and converts its results and exceptions
* to the expected types.
*
* @param self The input string
* @param separator The string to split on
* @param forward A flag that controls whether the input string is split around
* the first ({@code true}) or last ({@code false}) occurrence of the separator.
* @param env The current environment
* @param loc The location that is used for potential exceptions
* @return A list with three elements
*/
private static Object partitionWrapper(String self, String separator, boolean forward,
Environment env, Location loc) throws EvalException {
try {
return convert(stringPartition(self, separator, forward), env);
} catch (IllegalArgumentException ex) {
throw new EvalException(loc, ex);
}
}
/**
* Splits the input string at the {first|last} occurrence of the given separator
* and returns the resulting partition as a three-tuple of Strings, contained
* in a {@code List}.
*
*
If the input string does not contain the separator, the tuple will
* consist of the original input string and two empty strings.
*
*
This method emulates the behavior of Python's str.partition() and
* str.rpartition(), depending on the value of the {@code forward} flag.
*
* @param input The input string
* @param separator The string to split on
* @param forward A flag that controls whether the input string is split around
* the first ({@code true}) or last ({@code false}) occurrence of the separator.
* @return A three-tuple (List) of the form [part_before_separator, separator,
* part_after_separator].
*
*/
private static List stringPartition(String input, String separator, boolean forward)
throws IllegalArgumentException {
if (separator.isEmpty()) {
throw new IllegalArgumentException("Empty separator");
}
int partitionSize = 3;
ArrayList result = new ArrayList<>(partitionSize);
int pos = forward ? input.indexOf(separator) : input.lastIndexOf(separator);
if (pos < 0) {
for (int i = 0; i < partitionSize; ++i) {
result.add("");
}
// Following Python's implementation of str.partition() and str.rpartition(),
// the input string is copied to either the first or the last position in the
// list, depending on the value of the forward flag.
result.set(forward ? 0 : partitionSize - 1, input);
} else {
result.add(input.substring(0, pos));
result.add(separator);
// pos + sep.length() is at most equal to input.length(). This worst-case
// happens when the separator is at the end of the input string. However,
// substring() will return an empty string in this scenario, thus making
// any additional safety checks obsolete.
result.add(input.substring(pos + separator.length()));
}
return result;
}
@SkylarkSignature(
name = "capitalize",
objectType = StringModule.class,
returnType = String.class,
doc =
"Returns a copy of the string with its first character capitalized and the rest "
+ "lowercased. This method does not support non-ascii characters.",
mandatoryPositionals = {@Param(name = "self", type = String.class, doc = "This string.")}
)
private static BuiltinFunction capitalize =
new BuiltinFunction("capitalize") {
@SuppressWarnings("unused")
public String invoke(String self) throws EvalException {
if (self.isEmpty()) {
return self;
}
return Character.toUpperCase(self.charAt(0)) + self.substring(1).toLowerCase();
}
};
@SkylarkSignature(name = "title", objectType = StringModule.class,
returnType = String.class,
doc =
"Converts the input string into title case, i.e. every word starts with an "
+ "uppercase letter while the remaining letters are lowercase. In this "
+ "context, a word means strictly a sequence of letters. This method does "
+ "not support supplementary Unicode characters.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string.")})
private static BuiltinFunction title = new BuiltinFunction("title") {
@SuppressWarnings("unused")
public String invoke(String self) throws EvalException {
char[] data = self.toCharArray();
boolean previousWasLetter = false;
for (int pos = 0; pos < data.length; ++pos) {
char current = data[pos];
boolean currentIsLetter = Character.isLetter(current);
if (currentIsLetter) {
if (previousWasLetter && Character.isUpperCase(current)) {
data[pos] = Character.toLowerCase(current);
} else if (!previousWasLetter && Character.isLowerCase(current)) {
data[pos] = Character.toUpperCase(current);
}
}
previousWasLetter = currentIsLetter;
}
return new String(data);
}
};
/**
* Common implementation for find, rfind, index, rindex.
* @param forward true if we want to return the last matching index.
*/
private static int stringFind(boolean forward,
String self, String sub, int start, Object end, String msg)
throws ConversionException {
String substr = pythonSubstring(self, start, end, msg);
int subpos = forward ? substr.indexOf(sub) : substr.lastIndexOf(sub);
start = clampIndex(start, self.length());
return subpos < 0 ? subpos : subpos + start;
}
@SkylarkSignature(name = "rfind", objectType = StringModule.class, returnType = Integer.class,
doc = "Returns the last index where sub is found, "
+ "or -1 if no such index exists, optionally restricting to "
+ "[start:end], "
+ "start being inclusive and end being exclusive.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sub", type = String.class, doc = "The substring to find.")},
optionalPositionals = {
@Param(name = "start", type = Integer.class, defaultValue = "0",
doc = "Restrict to search from this position."),
@Param(name = "end", type = Integer.class, noneable = true, defaultValue = "None",
doc = "optional position before which to restrict to search.")})
private static BuiltinFunction rfind = new BuiltinFunction("rfind") {
public Integer invoke(String self, String sub, Integer start, Object end)
throws ConversionException {
return stringFind(false, self, sub, start, end, "'end' argument to rfind");
}
};
@SkylarkSignature(name = "find", objectType = StringModule.class, returnType = Integer.class,
doc = "Returns the first index where sub is found, "
+ "or -1 if no such index exists, optionally restricting to "
+ "[start:end], "
+ "start being inclusive and end being exclusive.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sub", type = String.class, doc = "The substring to find.")},
optionalPositionals = {
@Param(name = "start", type = Integer.class, defaultValue = "0",
doc = "Restrict to search from this position."),
@Param(name = "end", type = Integer.class, noneable = true, defaultValue = "None",
doc = "optional position before which to restrict to search.")})
private static BuiltinFunction find = new BuiltinFunction("find") {
public Integer invoke(String self, String sub, Integer start, Object end)
throws ConversionException {
return stringFind(true, self, sub, start, end, "'end' argument to find");
}
};
@SkylarkSignature(name = "rindex", objectType = StringModule.class, returnType = Integer.class,
doc = "Returns the last index where sub is found, "
+ "or raises an error if no such index exists, optionally restricting to "
+ "[start:end], "
+ "start being inclusive and end being exclusive.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sub", type = String.class, doc = "The substring to find.")},
optionalPositionals = {
@Param(name = "start", type = Integer.class, defaultValue = "0",
doc = "Restrict to search from this position."),
@Param(name = "end", type = Integer.class, noneable = true, defaultValue = "None",
doc = "optional position before which to restrict to search.")},
useLocation = true)
private static BuiltinFunction rindex = new BuiltinFunction("rindex") {
public Integer invoke(String self, String sub, Integer start, Object end,
Location loc) throws EvalException, ConversionException {
int res = stringFind(false, self, sub, start, end, "'end' argument to rindex");
if (res < 0) {
throw new EvalException(loc, Printer.format("substring %r not found in %r", sub, self));
}
return res;
}
};
@SkylarkSignature(name = "index", objectType = StringModule.class, returnType = Integer.class,
doc = "Returns the first index where sub is found, "
+ "or raises an error if no such index exists, optionally restricting to "
+ "[start:end], "
+ "start being inclusive and end being exclusive.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sub", type = String.class, doc = "The substring to find.")},
optionalPositionals = {
@Param(name = "start", type = Integer.class, defaultValue = "0",
doc = "Restrict to search from this position."),
@Param(name = "end", type = Integer.class, noneable = true,
doc = "optional position before which to restrict to search.")},
useLocation = true)
private static BuiltinFunction index = new BuiltinFunction("index") {
public Integer invoke(String self, String sub, Integer start, Object end,
Location loc) throws EvalException, ConversionException {
int res = stringFind(true, self, sub, start, end, "'end' argument to index");
if (res < 0) {
throw new EvalException(loc, Printer.format("substring %r not found in %r", sub, self));
}
return res;
}
};
@SkylarkSignature(name = "isalpha", objectType = StringModule.class, returnType = Boolean.class,
doc = "Returns True if all characters in the string are alphabetic ([a-zA-Z]) and it "
+ "contains at least one character.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string.")})
private static BuiltinFunction isalpha = new BuiltinFunction("isalpha") {
public Boolean invoke(String self) throws EvalException {
int length = self.length();
if (length < 1) {
return false;
}
for (int index = 0; index < length; index++) {
char character = self.charAt(index);
if (!((character >= 'A' && character <= 'Z')
|| (character >= 'a' && character <= 'z'))) {
return false;
}
}
return true;
}
};
@SkylarkSignature(name = "count", objectType = StringModule.class, returnType = Integer.class,
doc = "Returns the number of (non-overlapping) occurrences of substring sub in "
+ "string, optionally restricting to [start:end], "
+ "start being inclusive and end being exclusive.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sub", type = String.class, doc = "The substring to count.")},
optionalPositionals = {
@Param(name = "start", type = Integer.class, defaultValue = "0",
doc = "Restrict to search from this position."),
@Param(name = "end", type = Integer.class, noneable = true, defaultValue = "None",
doc = "optional position before which to restrict to search.")})
private static BuiltinFunction count = new BuiltinFunction("count") {
public Integer invoke(String self, String sub, Integer start, Object end)
throws ConversionException {
String str = pythonSubstring(self, start, end, "'end' operand of 'find'");
if (sub.isEmpty()) {
return str.length() + 1;
}
int count = 0;
int index = -1;
while ((index = str.indexOf(sub)) >= 0) {
count++;
str = str.substring(index + sub.length());
}
return count;
}
};
@SkylarkSignature(name = "endswith", objectType = StringModule.class, returnType = Boolean.class,
doc = "Returns True if the string ends with sub, "
+ "otherwise False, optionally restricting to [start:end], "
+ "start being inclusive and end being exclusive.",
mandatoryPositionals = {
@Param(name = "self", type = String.class, doc = "This string."),
@Param(name = "sub", type = String.class, doc = "The substring to check.")},
optionalPositionals = {
@Param(name = "start", type = Integer.class, defaultValue = "0",
doc = "Test beginning at this position."),
@Param(name = "end", type = Integer.class, noneable = true, defaultValue = "None",
doc = "optional position at which to stop comparing.")})
private static BuiltinFunction endswith = new BuiltinFunction("endswith") {
public Boolean invoke(String self, String sub, Integer start, Object end)
throws ConversionException {
return pythonSubstring(self, start, end, "'end' operand of 'endswith'").endsWith(sub);
}
};
// In Python, formatting is very complex.
// We handle here the simplest case which provides most of the value of the function.
// https://docs.python.org/3/library/string.html#formatstrings
@SkylarkSignature(name = "format", objectType = StringModule.class, returnType = String.class,
doc = "Perform string interpolation. Format strings contain replacement fields "
+ "surrounded by curly braces {}. Anything that is not contained "
+ "in braces is considered literal text, which is copied unchanged to the output."
+ "If you need to include a brace character in the literal text, it can be "
+ "escaped by doubling: {{ and }}"
+ "A replacement field can be either a name, a number, or empty. Values are "
+ "converted to strings using the str function."
+ "