runtime/vm/compiler/backend/sexpression.h

// Copyright (c) 2019, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#ifndef RUNTIME_VM_COMPILER_BACKEND_SEXPRESSION_H_
#define RUNTIME_VM_COMPILER_BACKEND_SEXPRESSION_H_

#if defined(DART_PRECOMPILED_RUNTIME)
#error "AOT runtime should not use compiler sources (including header files)"
#endif  // defined(DART_PRECOMPILED_RUNTIME)

#include "platform/text_buffer.h"

#include "vm/allocation.h"
#include "vm/growable_array.h"
#include "vm/hash_map.h"
#include "vm/zone.h"

namespace dart {

#define FOR_EACH_S_EXPRESSION_ATOM(M)                                          \
  M(Bool, bool)                                                                \
  M(Double, double)                                                            \
  M(Integer, int64_t)                                                          \
  M(String, const char*)                                                       \
  M(Symbol, const char*)

#define FOR_EACH_S_EXPRESSION(M)                                               \
  FOR_EACH_S_EXPRESSION_ATOM(M)                                                \
  M(List, _)

#define FOR_EACH_ABSTRACT_S_EXPRESSION(M) M(Atom, _)

#define FORWARD_DECLARATION(name, value_type) class SExp##name;
FOR_EACH_S_EXPRESSION(FORWARD_DECLARATION)
FOR_EACH_ABSTRACT_S_EXPRESSION(FORWARD_DECLARATION)
#undef FORWARD_DECLARATION

// Abstract base class for S-expressions used as an intermediate form for the
// IL serializer. These aren't true (LISP-like) S-expressions, as the atoms
// are more restricted and the lists have extra information. Here is an
// illustrative BNF-style grammar of the current serialized form of
// S-expressions that includes non-whitespace literal tokens:
//
// <s-exp>      ::= <atom> | <list>
// <atom>       ::= <bool> | <integer> | <string> | <symbol>
// <list>       ::= '(' <s-exp>* <extra-info>? ')'
// <extra-info> ::= '{' <extra-elem>* '}'
// <extra-elem> ::= <symbol> <s-exp> ','
//
// Here, <string>s are double-quoted strings with backslash escaping and
// <symbol>s are sequences of consecutive non-whitespace characters that do not
// include commas (,), parentheses (()), curly braces ({}), or the double-quote
// character (").
//
// In addition, the <extra-info> is considered a map from symbol labels to
// S-expression values, and as such each symbol used as a key in an <extra-info>
// block should only appear once as a key within that block.
class SExpression : public ZoneAllocated {
 public:
  explicit SExpression(intptr_t start = kInvalidPos) : start_(start) {}
  virtual ~SExpression() {}

  static intptr_t const kInvalidPos = -1;

  static SExpression* FromCString(Zone* zone, const char* cstr);
  const char* ToCString(Zone* zone) const;
  intptr_t start() const { return start_; }

#define S_EXPRESSION_TYPE_CHECK(name, value_type)                              \
  bool Is##name() const { return (As##name() != nullptr); }                    \
  SExp##name* As##name() {                                                     \
    auto const const_this = const_cast<const SExpression*>(this);              \
    return const_cast<SExp##name*>(const_this->As##name());                    \
  }                                                                            \
  virtual const SExp##name* As##name() const { return nullptr; }

  FOR_EACH_S_EXPRESSION(S_EXPRESSION_TYPE_CHECK)
  FOR_EACH_ABSTRACT_S_EXPRESSION(S_EXPRESSION_TYPE_CHECK)

  virtual const char* DebugName() const = 0;
  virtual bool Equals(SExpression* sexp) const = 0;
  virtual void SerializeTo(Zone* zone,
                           BaseTextBuffer* buffer,
                           const char* indent,
                           intptr_t width = 80) const = 0;
  virtual void SerializeToLine(BaseTextBuffer* buffer) const = 0;

 private:
  // Starting character position of the s-expression in the original
  // serialization, if it was deserialized.
  intptr_t const start_;
  DISALLOW_COPY_AND_ASSIGN(SExpression);
};

class SExpAtom : public SExpression {
 public:
  explicit SExpAtom(intptr_t start = kInvalidPos) : SExpression(start) {}

  virtual const SExpAtom* AsAtom() const { return this; }
  // No atoms have sub-elements, so they always print to a single line.
  virtual void SerializeTo(Zone* zone,
                           BaseTextBuffer* buffer,
                           const char* indent,
                           intptr_t width = 80) const {
    SerializeToLine(buffer);
  }

 private:
  DISALLOW_COPY_AND_ASSIGN(SExpAtom);
};

#define DEFINE_S_EXPRESSION_TYPE_CHECK(name)                                   \
  virtual const SExp##name* As##name() const { return this; }                  \
  virtual const char* DebugName() const { return #name; }

// The various concrete S-expression atom classes are thin wrappers around
// their contained value that includes serialization and type check methods.
#define DEFINE_S_EXPRESSION_ATOM_CLASS(name, value_type)                       \
  class SExp##name : public SExpAtom {                                         \
   public:                                                                     \
    explicit SExp##name(value_type val, intptr_t start = kInvalidPos)          \
        : SExpAtom(start), val_(val) {}                                        \
    value_type value() const { return val_; }                                  \
    virtual bool Equals(SExpression* sexp) const;                              \
    bool Equals(value_type val) const;                                         \
    virtual void SerializeToLine(BaseTextBuffer* buffer) const;                \
    DEFINE_S_EXPRESSION_TYPE_CHECK(name)                                       \
   private:                                                                    \
    value_type const val_;                                                     \
    DISALLOW_COPY_AND_ASSIGN(SExp##name);                                      \
  };

FOR_EACH_S_EXPRESSION_ATOM(DEFINE_S_EXPRESSION_ATOM_CLASS)

// A list of S-expressions. Unlike normal S-expressions, an S-expression list
// also contains a hash map kept separate from the elements, which we use for
// extra non-argument information for IL instructions.
class SExpList : public SExpression {
 public:
  explicit SExpList(Zone* zone, intptr_t start = kInvalidPos)
      : SExpression(start), contents_(zone, 2), extra_info_(zone) {}

  using ExtraInfoHashMap = CStringMap<SExpression*>;

  void Add(SExpression* sexp);
  void AddExtra(const char* label, SExpression* value);

  SExpression* At(intptr_t i) const { return contents_.At(i); }
  intptr_t Length() const { return contents_.length(); }

  intptr_t ExtraLength() const { return extra_info_.Length(); }
  ExtraInfoHashMap::Iterator ExtraIterator() const {
    return extra_info_.GetIterator();
  }
  bool ExtraHasKey(const char* cstr) const { return extra_info_.HasKey(cstr); }
  SExpression* ExtraLookupValue(const char* cstr) const {
    return extra_info_.LookupValue(cstr);
  }

  // Shortcut for retrieving the tag from a tagged list (list that contains an
  // initial symbol). Returns nullptr if the list is not a tagged list.
  SExpSymbol* Tag() const {
    if (Length() == 0 || !At(0)->IsSymbol()) return nullptr;
    return At(0)->AsSymbol();
  }

  DEFINE_S_EXPRESSION_TYPE_CHECK(List)
  virtual bool Equals(SExpression* sexp) const;
  virtual void SerializeTo(Zone* zone,
                           BaseTextBuffer* buffer,
                           const char* indent,
                           intptr_t width = 80) const;
  virtual void SerializeToLine(BaseTextBuffer* buffer) const;

 private:
  static const char* const kElemIndent;
  static const char* const kExtraIndent;

  void SerializeExtraInfoTo(Zone* zone,
                            BaseTextBuffer* buffer,
                            const char* indent,
                            int width) const;
  void SerializeExtraInfoToLine(BaseTextBuffer* buffer) const;

  ZoneGrowableArray<SExpression*> contents_;
  ExtraInfoHashMap extra_info_;

  DISALLOW_COPY_AND_ASSIGN(SExpList);
};

class SExpParser : public ValueObject {
 public:
  SExpParser(Zone* zone, const char* cstr)
      : SExpParser(zone, cstr, strlen(cstr)) {}
  SExpParser(Zone* zone, const char* cstr, intptr_t len)
      : zone_(zone),
        buffer_(ASSERT_NOTNULL(cstr)),
        buffer_size_(strnlen(cstr, len)),
        cur_label_(nullptr),
        cur_value_(nullptr),
        list_stack_(zone, 2),
        in_extra_stack_(zone, 2),
        extra_start_stack_(zone, 2),
        cur_label_stack_(zone, 2),
        error_message_(nullptr) {}

  // Constants used in serializing and deserializing S-expressions.
  static const char* const kBoolTrueSymbol;
  static const char* const kBoolFalseSymbol;
  static char const kDoubleExponentChar;
  static const char* const kDoubleInfinitySymbol;
  static const char* const kDoubleNaNSymbol;

  struct ErrorStrings : AllStatic {
    static const char* const kOpenString;
    static const char* const kBadUnicodeEscape;
    static const char* const kOpenSExpList;
    static const char* const kOpenMap;
    static const char* const kNestedMap;
    static const char* const kMapOutsideList;
    static const char* const kNonSymbolLabel;
    static const char* const kNoMapLabel;
    static const char* const kRepeatedMapLabel;
    static const char* const kNoMapValue;
    static const char* const kExtraMapValue;
    static const char* const kUnexpectedComma;
    static const char* const kUnexpectedRightParen;
    static const char* const kUnexpectedRightCurly;
  };

  intptr_t error_pos() const { return error_pos_; }
  const char* error_message() const { return error_message_; }

  const char* Input() const { return buffer_; }
  SExpression* Parse();
  DART_NORETURN void ReportError() const;

 private:
#define S_EXP_TOKEN_LIST(M)                                                    \
  M(LeftParen)                                                                 \
  M(RightParen)                                                                \
  M(Comma)                                                                     \
  M(LeftCurly)                                                                 \
  M(RightCurly)                                                                \
  M(QuotedString)                                                              \
  M(Integer)                                                                   \
  M(Double)                                                                    \
  M(Boolean)                                                                   \
  M(Symbol)

  // clang-format off
#define DEFINE_S_EXP_TOKEN_ENUM_LINE(name) k##name,
  enum TokenType {
    S_EXP_TOKEN_LIST(DEFINE_S_EXP_TOKEN_ENUM_LINE)
    kMaxTokens,
  };
#undef DEFINE_S_EXP_TOKEN_ENUM
  // clang-format on

  class Token : public ZoneAllocated {
   public:
    Token(TokenType type, const char* cstr, intptr_t len)
        : type_(type), cstr_(cstr), len_(len) {}

    TokenType type() const { return type_; }
    intptr_t length() const { return len_; }
    const char* cstr() const { return cstr_; }
    const char* DebugName() const { return TokenNames[type()]; }
    const char* ToCString(Zone* zone);

   private:
    static const char* const TokenNames[kMaxTokens];

    TokenType const type_;
    const char* const cstr_;
    intptr_t const len_;
  };

  SExpression* TokenToSExpression(Token* token);
  Token* GetNextToken();
  void Reset();
  void StoreError(intptr_t pos, const char* format, ...) PRINTF_ATTRIBUTE(3, 4);

  static bool IsSymbolContinue(char c);

  Zone* const zone_;
  const char* const buffer_;
  intptr_t const buffer_size_;
  intptr_t cur_pos_ = 0;
  bool in_extra_ = false;
  intptr_t extra_start_ = -1;
  const char* cur_label_;
  SExpression* cur_value_;
  ZoneGrowableArray<SExpList*> list_stack_;
  ZoneGrowableArray<bool> in_extra_stack_;
  ZoneGrowableArray<intptr_t> extra_start_stack_;
  ZoneGrowableArray<const char*> cur_label_stack_;
  intptr_t error_pos_ = -1;
  const char* error_message_;
};

}  // namespace dart

#endif  // RUNTIME_VM_COMPILER_BACKEND_SEXPRESSION_H_