content: /*
   * Licensed to the Apache Software Foundation (ASF) under one
   * or more contributor license agreements.  See the NOTICE file
   * distributed with this work for additional information
   * regarding copyright ownership.  The ASF licenses this file
   * to you 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 org.apache.cassandra.db.marshal;
  
  import java.lang.reflect.Field;
  import java.lang.reflect.InvocationTargetException;
  import java.lang.reflect.Method;
  import java.nio.ByteBuffer;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  
  import com.google.common.base.Verify;
  import com.google.common.collect.ImmutableMap;
  import org.apache.cassandra.config.DatabaseDescriptor;
  import org.apache.cassandra.cql3.FieldIdentifier;
  import org.apache.cassandra.dht.IPartitioner;
  import org.apache.cassandra.exceptions.ConfigurationException;
  import org.apache.cassandra.exceptions.SyntaxException;
  import org.apache.cassandra.service.StorageService;
  import org.apache.cassandra.utils.ByteBufferUtil;
  import org.apache.cassandra.utils.FBUtilities;
  import org.apache.cassandra.utils.Pair;
  
  /**
   * Parse a string containing an Type definition.
   */
  public class TypeParser
  {
      private final String str;
      private int idx;
  
      // A cache of parsed string, specially useful for DynamicCompositeType
      private static volatile ImmutableMap<String, AbstractType<?>> cache = ImmutableMap.of();
  
      public static final TypeParser EMPTY_PARSER = new TypeParser("", 0);
  
      private TypeParser(String str, int idx)
      {
          this.str = str;
          this.idx = idx;
      }
  
      public TypeParser(String str)
      {
          this(str, 0);
      }
  
      /**
       * Parse a string containing an type definition.
       */
      public static AbstractType<?> parse(String str) throws SyntaxException, ConfigurationException
      {
          if (str == null)
              return BytesType.instance;
  
          // A single volatile read of 'cache' should not hurt.
          AbstractType<?> type = cache.get(str);
  
          if (type != null)
              return type;
  
          // This could be simplier (i.e. new TypeParser(str).parse()) but we avoid creating a TypeParser object if not really necessary.
          int i = 0;
          i = skipBlank(str, i);
          int j = i;
          while (!isEOS(str, i) && isIdentifierChar(str.charAt(i)))
              ++i;
  
          if (i == j)
              return BytesType.instance;
  
          String name = str.substring(j, i);
          i = skipBlank(str, i);
  
          if (!isEOS(str, i) && str.charAt(i) == '(')
              type = getAbstractType(name, new TypeParser(str, i));
          else
              type = getAbstractType(name);
  
          Verify.verify(type != null, "Parsing %s yielded null, which is a bug", str);
  
          // Prevent concurrent modification to the map acting as the cache for TypeParser at the expense of
          // more allocation when the cache needs to be updated, since updates to the cache are rare compared
          // to the amount of reads.
          //
          // Copy the existing cache into a new map and add the parsed AbstractType instance and replace
          // the cache, if the type is not already in the cache.
          //
          // The cache-update is done in a short synchronized block to prevent duplicate instances of AbstractType
          // for the same string representation.
          synchronized (TypeParser.class)
          {
              if (!cache.containsKey(str))
              {
                  ImmutableMap.Builder<String, AbstractType<?>> builder = ImmutableMap.builder();
                  builder.putAll(cache).put(str, type);
                  cache = builder.build();
              }
              return type;
          }
      }
  
      public static AbstractType<?> parse(CharSequence compareWith) throws SyntaxException, ConfigurationException
      {
          return parse(compareWith == null ? null : compareWith.toString());
      }
  
      /**
       * Parse an AbstractType from current position of this parser.
       */
      public AbstractType<?> parse() throws SyntaxException, ConfigurationException
      {
          skipBlank();
          String name = readNextIdentifier();
  
          skipBlank();
          if (!isEOS() && str.charAt(idx) == '(')
              return getAbstractType(name, this);
          else
              return getAbstractType(name);
      }
  
      /**
       * Parse PartitionOrdering from old version of PartitionOrdering' string format
       */
      private static AbstractType<?> defaultParsePartitionOrdering(TypeParser typeParser)
      {
          IPartitioner partitioner = DatabaseDescriptor.getPartitioner();
          Iterator<String> argIterator = typeParser.getKeyValueParameters().keySet().iterator();
          if (argIterator.hasNext())
          {
              partitioner = FBUtilities.newPartitioner(argIterator.next());
              assert !argIterator.hasNext();
          }
          return partitioner.partitionOrdering(null);
      }
  
      /**
       * Parse and return the real {@link PartitionerDefinedOrder} from the string variable {@link #str}.
       * The {@link #str} format can be like {@code PartitionerDefinedOrder(<partitioner>)} or
       * {@code PartitionerDefinedOrder(<partitioner>:<baseType>)}.
       */
      public AbstractType<?> getPartitionerDefinedOrder()
      {
          int initIdx = idx;
          skipBlank();
          if (isEOS())
              return defaultParsePartitionOrdering(this);
          if (str.charAt(idx) != '(')
              throw new IllegalStateException();
  
          ++idx; // skipping '('
          skipBlank();
  
          String k = readNextIdentifier();
          IPartitioner partitioner = FBUtilities.newPartitioner(k);
          skipBlank();
          if (str.charAt(idx) == ':')
          {
              ++idx;
              skipBlank();
              // must be PartitionerDefinedOrder
              return partitioner.partitionOrdering(parse());
          }
          else if (str.charAt(idx) == ')')
          {
              idx = initIdx;
              return partitioner.partitionOrdering(null);
          }
          throw new SyntaxException("Syntax error parsing '" + str + ": for msg unexpected character '" + str.charAt(idx) + "'");
      }
  
      public static String stringifyTKeyValueParameters(Map<String, String> map)
      {
          StringBuilder sb = new StringBuilder();
          sb.append('(');
          for (Map.Entry<String, String> e : map.entrySet())
              sb.append(e.getKey()).append(" = ").append(e.getValue()).append(", ");
          if (!map.isEmpty())
              sb.setLength(sb.length() - 2);
          return sb.append(')').toString();
      }
  
      public Map<String, String> getKeyValueParameters() throws SyntaxException
      {
          if (isEOS())
              return Collections.emptyMap();
  
          if (str.charAt(idx) != '(')
              throw new IllegalStateException();
  
          Map<String, String> map = new HashMap<>();
          ++idx; // skipping '('
  
          while (skipBlankAndComma())
          {
              if (str.charAt(idx) == ')')
              {
                  ++idx;
                  return map;
              }
  
              String k = readNextIdentifier();
              String v = "";
              skipBlank();
              if (str.charAt(idx) == '=')
              {
                  ++idx;
                  skipBlank();
                  v = readNextIdentifier();
              }
              else if (str.charAt(idx) != ',' && str.charAt(idx) != ')')
              {
                  throwSyntaxError("unexpected character '" + str.charAt(idx) + "'");
              }
              map.put(k, v);
          }
          throw new SyntaxException(String.format("Syntax error parsing '%s' at char %d: unexpected end of string", str, idx));
      }
  
      public static String stringifyVectorParameters(AbstractType<?> type, boolean ignoreFreezing, int dimension)
      {
          return "(" + type.toString(ignoreFreezing) + " , " + dimension + ")";
      }
  
      public Vector getVectorParameters()
      {
          if (isEOS())
              return null;
          if (str.charAt(idx) != '(')
              throw new IllegalStateException();
  
          ++idx; // skipping '('
          AbstractType<?> type = parse();
          if (!skipBlankAndComma())
              throw new IllegalStateException();
          String s = readNextIdentifier();
          if (s.isEmpty())
              throw new IllegalStateException();
          int dimension = Integer.parseInt(s);
          if (str.charAt(idx) != ')')
              throw new IllegalStateException();
          ++idx; // skipping ')'
          return new Vector(type, dimension);
      }
  
      public List<AbstractType<?>> getTypeParameters() throws SyntaxException, ConfigurationException
      {
          List<AbstractType<?>> list = new ArrayList<>();
  
          if (isEOS())
              return list;
  
          if (str.charAt(idx) != '(')
              throw new IllegalStateException();
  
          ++idx; // skipping '('
  
          while (skipBlankAndComma())
          {
              if (str.charAt(idx) == ')')
              {
                  ++idx;
                  return list;
              }
  
              try
              {
                  list.add(parse());
              }
              catch (SyntaxException e)
              {
                  SyntaxException ex = new SyntaxException(String.format("Exception while parsing '%s' around char %d", str, idx));
                  ex.initCause(e);
                  throw ex;
              }
          }
          throw new SyntaxException(String.format("Syntax error parsing '%s' at char %d: unexpected end of string", str, idx));
      }
  
      public Map<Byte, AbstractType<?>> getAliasParameters() throws SyntaxException, ConfigurationException
      {
          Map<Byte, AbstractType<?>> map = new HashMap<>();
  
          if (isEOS())
              return map;
  
          if (str.charAt(idx) != '(')
              throw new IllegalStateException();
  
          ++idx; // skipping '('
  
  
          while (skipBlankAndComma())
          {
              if (str.charAt(idx) == ')')
              {
                  ++idx;
                  return map;
              }
  
              String alias = readNextIdentifier();
              if (alias.length() != 1)
                  throwSyntaxError("An alias should be a single character: '" + alias + "', string: " + str);
              char aliasChar = alias.charAt(0);
              if (aliasChar < 33 || aliasChar > 127)
                  throwSyntaxError("An alias should be a single character in [0..9a..bA..B-+._&]");
  
              skipBlank();
              if (!(str.charAt(idx) == '=' && str.charAt(idx+1) == '>'))
                  throwSyntaxError("expecting '=>' token");
  
              idx += 2;
              skipBlank();
              try
              {
                  map.put((byte)aliasChar, parse());
              }
              catch (SyntaxException e)
              {
                  SyntaxException ex = new SyntaxException(String.format("Exception while parsing '%s' around char %d", str, idx));
                  ex.initCause(e);
                  throw ex;
              }
          }
          throw new SyntaxException(String.format("Syntax error parsing '%s' at char %d: unexpected end of string", str, idx));
      }
  
      public Map<ByteBuffer, CollectionType> getCollectionsParameters() throws SyntaxException, ConfigurationException
      {
          Map<ByteBuffer, CollectionType> map = new HashMap<>();
  
          if (isEOS())
              return map;
  
          if (str.charAt(idx) != '(')
              throw new IllegalStateException();
  
          ++idx; // skipping '('
  
          while (skipBlankAndComma())
          {
              if (str.charAt(idx) == ')')
              {
                  ++idx;
                  return map;
              }
  
              ByteBuffer bb = fromHex(readNextIdentifier());
  
              skipBlank();
              if (str.charAt(idx) != ':')
                  throwSyntaxError("expecting ':' token");
  
              ++idx;
              skipBlank();
              try
              {
                  AbstractType<?> type = parse();
                  if (!(type instanceof CollectionType))
                      throw new SyntaxException(type + " is not a collection type");
                  map.put(bb, (CollectionType)type);
              }
              catch (SyntaxException e)
              {
                  SyntaxException ex = new SyntaxException(String.format("Exception while parsing '%s' around char %d", str, idx));
                  ex.initCause(e);
                  throw ex;
              }
          }
          throw new SyntaxException(String.format("Syntax error parsing '%s' at char %d: unexpected end of string", str, idx));
      }
  
      private ByteBuffer fromHex(String hex) throws SyntaxException
      {
          try
          {
              return ByteBufferUtil.hexToBytes(hex);
          }
          catch (NumberFormatException e)
          {
              throwSyntaxError(e.getMessage());
              return null;
          }
      }
  
      public Pair<Pair<String, ByteBuffer>, List<Pair<ByteBuffer, AbstractType>>> getUserTypeParameters() throws SyntaxException, ConfigurationException
      {
  
          if (isEOS() || str.charAt(idx) != '(')
              throw new IllegalStateException();
  
          ++idx; // skipping '('
  
          skipBlankAndComma();
          String keyspace = readNextIdentifier();
          skipBlankAndComma();
          ByteBuffer typeName = fromHex(readNextIdentifier());
          List<Pair<ByteBuffer, AbstractType>> defs = new ArrayList<>();
  
          while (skipBlankAndComma())
          {
              if (str.charAt(idx) == ')')
              {
                  ++idx;
                  return Pair.create(Pair.create(keyspace, typeName), defs);
              }
  
              ByteBuffer name = fromHex(readNextIdentifier());
              skipBlank();
              if (str.charAt(idx) != ':')
                  throwSyntaxError("expecting ':' token");
              ++idx;
              skipBlank();
              try
              {
                  AbstractType type = parse();
                  defs.add(Pair.create(name, type));
              }
              catch (SyntaxException e)
              {
                  SyntaxException ex = new SyntaxException(String.format("Exception while parsing '%s' around char %d", str, idx));
                  ex.initCause(e);
                  throw ex;
              }
          }
          throw new SyntaxException(String.format("Syntax error parsing '%s' at char %d: unexpected end of string", str, idx));
      }
  
      private static AbstractType<?> getAbstractType(String compareWith) throws ConfigurationException
      {
          String className = compareWith.contains(".") ? compareWith : "org.apache.cassandra.db.marshal." + compareWith;
          Class<? extends AbstractType<?>> typeClass = FBUtilities.<AbstractType<?>>classForName(className, "abstract-type");
          try
          {
              Field field = typeClass.getDeclaredField("instance");
              return (AbstractType<?>) field.get(null);
          }
          catch (NoSuchFieldException | IllegalAccessException e)
          {
              // Trying with empty parser
              return getRawAbstractType(typeClass, EMPTY_PARSER);
          }
      }
  
      private static AbstractType<?> getAbstractType(String compareWith, TypeParser parser) throws SyntaxException, ConfigurationException
      {
          String className = compareWith.contains(".") ? compareWith : "org.apache.cassandra.db.marshal." + compareWith;
          Class<? extends AbstractType<?>> typeClass = FBUtilities.<AbstractType<?>>classForName(className, "abstract-type");
          if (PseudoUtf8Type.class.isAssignableFrom(typeClass))
          {
              if (StorageService.instance.isDaemonSetupCompleted())
                  throw new ConfigurationException(typeClass.getName() + " is reserved for internal functionality");
          }
          try
          {
              Method method = typeClass.getDeclaredMethod("getInstance", TypeParser.class);
              return (AbstractType<?>) method.invoke(null, parser);
          }
          catch (NoSuchMethodException | IllegalAccessException e)
          {
              // Trying to see if we have an instance field and apply the default parameter to it
              AbstractType<?> type = getRawAbstractType(typeClass);
              return AbstractType.parseDefaultParameters(type, parser);
          }
          catch (InvocationTargetException e)
          {
              ConfigurationException ex = new ConfigurationException("Invalid definition for comparator " + typeClass.getName() + ".");
              ex.initCause(e.getTargetException());
              throw ex;
          }
      }
  
      private static AbstractType<?> getRawAbstractType(Class<? extends AbstractType<?>> typeClass) throws ConfigurationException
      {
          try
          {
              Field field = typeClass.getDeclaredField("instance");
              return (AbstractType<?>) field.get(null);
          }
          catch (NoSuchFieldException | IllegalAccessException e)
          {
              throw new ConfigurationException("Invalid comparator class " + typeClass.getName() + ": must define a public static instance field or a public static method getInstance(TypeParser).");
          }
      }
  
      private static AbstractType<?> getRawAbstractType(Class<? extends AbstractType<?>> typeClass, TypeParser parser) throws ConfigurationException
      {
          try
          {
              Method method = typeClass.getDeclaredMethod("getInstance", TypeParser.class);
              return (AbstractType<?>) method.invoke(null, parser);
          }
          catch (NoSuchMethodException | IllegalAccessException e)
          {
              throw new ConfigurationException("Invalid comparator class " + typeClass.getName() + ": must define a public static instance field or a public static method getInstance(TypeParser).");
          }
          catch (InvocationTargetException e)
          {
              ConfigurationException ex = new ConfigurationException("Invalid definition for comparator " + typeClass.getName() + ".");
              ex.initCause(e.getTargetException());
              throw ex;
          }
      }
  
      private void throwSyntaxError(String msg) throws SyntaxException
      {
          throw new SyntaxException(String.format("Syntax error parsing '%s' at char %d: %s", str, idx, msg));
      }
  
      private boolean isEOS()
      {
          return isEOS(str, idx);
      }
  
      private static boolean isEOS(String str, int i)
      {
          return i >= str.length();
      }
  
      private static boolean isBlank(int c)
      {
          return c == ' ' || c == '\t' || c == '\n';
      }
  
      private void skipBlank()
      {
          idx = skipBlank(str, idx);
      }
  
      private static int skipBlank(String str, int i)
      {
          while (!isEOS(str, i) && isBlank(str.charAt(i)))
              ++i;
  
          return i;
      }
  
      // skip all blank and at best one comma, return true if there not EOS
      private boolean skipBlankAndComma()
      {
          boolean commaFound = false;
          while (!isEOS())
          {
              int c = str.charAt(idx);
              if (c == ',')
              {
                  if (commaFound)
                      return true;
                  else
                      commaFound = true;
              }
              else if (!isBlank(c))
              {
                  return true;
              }
              ++idx;
          }
          return false;
      }
  
      /*
       * [0..9a..bA..B-+._&]
       */
      private static boolean isIdentifierChar(int c)
      {
          return (c >= '0' && c <= '9')
              || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
              || c == '-' || c == '+' || c == '.' || c == '_' || c == '&';
      }
  
      // left idx positioned on the character stopping the read
      public String readNextIdentifier()
      {
          int i = idx;
          while (!isEOS() && isIdentifierChar(str.charAt(idx)))
              ++idx;
  
          return str.substring(i, idx);
      }
  
      @Override
      public String toString()
      {
          return "TypeParser[" + str.substring(idx) + "]";
      }
  
      /**
       * Helper function to ease the writing of AbstractType.toString() methods.
       */
      public static String stringifyAliasesParameters(Map<Byte, AbstractType<?>> aliases)
      {
          StringBuilder sb = new StringBuilder();
          sb.append('(');
          Iterator<Map.Entry<Byte, AbstractType<?>>> iter = aliases.entrySet().iterator();
          if (iter.hasNext())
          {
              Map.Entry<Byte, AbstractType<?>> entry = iter.next();
              sb.append((char)(byte)entry.getKey()).append("=>").append(entry.getValue());
          }
          while (iter.hasNext())
          {
              Map.Entry<Byte, AbstractType<?>> entry = iter.next();
              sb.append(',').append((char)(byte)entry.getKey()).append("=>").append(entry.getValue());
          }
          sb.append(')');
          return sb.toString();
      }
  
      /**
       * Helper function to ease the writing of AbstractType.toString() methods.
       */
      public static String stringifyTypeParameters(List<AbstractType<?>> types)
      {
          return stringifyTypeParameters(types, false);
      }
  
      /**
       * Helper function to ease the writing of AbstractType.toString() methods.
       */
      public static String stringifyTypeParameters(List<AbstractType<?>> types, boolean ignoreFreezing)
      {
          StringBuilder sb = new StringBuilder("(");
          for (int i = 0; i < types.size(); i++)
          {
              if (i > 0)
                  sb.append(",");
              sb.append(types.get(i).toString(ignoreFreezing));
          }
          return sb.append(')').toString();
      }
  
      public static String stringifyCollectionsParameters(Map<ByteBuffer, ? extends CollectionType> collections)
      {
          StringBuilder sb = new StringBuilder();
          sb.append('(');
          boolean first = true;
          for (Map.Entry<ByteBuffer, ? extends CollectionType> entry : collections.entrySet())
          {
              if (!first)
                  sb.append(',');
  
              first = false;
              sb.append(ByteBufferUtil.bytesToHex(entry.getKey())).append(":");
              sb.append(entry.getValue());
          }
          sb.append(')');
          return sb.toString();
      }
  
      public static String stringifyUserTypeParameters(String keysace, ByteBuffer typeName, List<FieldIdentifier> fields,
                                                       List<AbstractType<?>> columnTypes, boolean ignoreFreezing)
      {
          StringBuilder sb = new StringBuilder();
          sb.append('(').append(keysace).append(",").append(ByteBufferUtil.bytesToHex(typeName));
  
          for (int i = 0; i < fields.size(); i++)
          {
              sb.append(',');
              sb.append(ByteBufferUtil.bytesToHex(fields.get(i).bytes)).append(":");
              sb.append(columnTypes.get(i).toString(ignoreFreezing));
          }
          sb.append(')');
          return sb.toString();
      }
  
      public static class Vector
      {
          public final int dimension;
          public final AbstractType<?> type;
  
          public Vector(AbstractType<?> type, int dimension)
          {
              this.dimension = dimension;
              this.type = type;
          }
      }
  }
  