garnet/bin/zxdb/expr/expr_parser_unittest.cc

// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <sstream>

#include "garnet/bin/zxdb/common/string_util.h"
#include "garnet/bin/zxdb/expr/expr_parser.h"
#include "garnet/bin/zxdb/expr/expr_tokenizer.h"
#include "garnet/bin/zxdb/symbols/collection.h"
#include "gtest/gtest.h"

namespace zxdb {

namespace {

// This name looker-upper declares anything beginning with "Namespace" is a
// namespace, anything beginning with "Template" is a template, and anything
// beginning with "Type" is a type.
NameLookupResult TestLookupName(const Identifier& ident) {
  const Identifier::Component& comp = ident.components().back();
  const std::string& name = comp.name().value();

  if (StringBeginsWith(name, "Namespace"))
    return NameLookupResult(NameLookupResult::kNamespace);
  if (StringBeginsWith(name, "Type")) {
    // Make up a random class to go with the type.
    auto type = fxl::MakeRefCounted<Collection>(DwarfTag::kClassType);
    type->set_assigned_name("Type");

    // NOTE: This doesn't qualify the type with namespaces or classes present
    // in the identifier so qualified names ("Namespace::Type") won't convert
    // to strings properly. This could be added if necessary.
    return NameLookupResult(NameLookupResult::kType, std::move(type));
  }
  if (StringBeginsWith(name, "Template")) {
    if (comp.has_template()) {
      // Assume templates with arguments are types.
      return NameLookupResult(
          NameLookupResult::kType,
          fxl::MakeRefCounted<Collection>(DwarfTag::kClassType));
    }
    return NameLookupResult(NameLookupResult::kTemplate);
  }
  return NameLookupResult(NameLookupResult::kOther);
}

}  // namespace

class ExprParserTest : public testing::Test {
 public:
  ExprParserTest() = default;

  // Valid after Parse() is called.
  ExprParser& parser() { return *parser_; }

  fxl::RefPtr<ExprNode> Parse(
      const char* input,
      NameLookupCallback name_lookup = NameLookupCallback()) {
    parser_.reset();

    tokenizer_ = std::make_unique<ExprTokenizer>(input);
    if (!tokenizer_->Tokenize()) {
      ADD_FAILURE() << "Tokenization failure: " << input;
      return nullptr;
    }

    parser_ =
        std::make_unique<ExprParser>(tokenizer_->TakeTokens(), name_lookup);
    return parser_->Parse();
  }

  // Does the parse and returns the string dump of the structure.
  std::string GetParseString(const char* input, NameLookupCallback name_lookup =
                                                    NameLookupCallback()) {
    auto root = Parse(input, name_lookup);
    if (!root) {
      // Expect calls to this to parse successfully.
      if (parser_.get())
        ADD_FAILURE() << "Parse failure: " << parser_->err().msg();
      return std::string();
    }

    std::ostringstream out;
    root->Print(out, 0);
    return out.str();
  }

 private:
  std::unique_ptr<ExprTokenizer> tokenizer_;
  std::unique_ptr<ExprParser> parser_;
};

TEST_F(ExprParserTest, Empty) {
  auto result = Parse("");
  ASSERT_FALSE(result);
  EXPECT_EQ("No input to parse.", parser().err().msg());
}

TEST_F(ExprParserTest, Identifier) {
  auto result = Parse("name");
  ASSERT_TRUE(result);

  const IdentifierExprNode* ident = result->AsIdentifier();
  ASSERT_TRUE(ident);
  EXPECT_EQ("name", ident->ident().GetFullName());
}

TEST_F(ExprParserTest, Dot) {
  auto result = Parse("base.member");
  ASSERT_TRUE(result);

  const MemberAccessExprNode* access = result->AsMemberAccess();
  ASSERT_TRUE(access);
  EXPECT_EQ(ExprToken::kDot, access->accessor().type());
  EXPECT_EQ(".", access->accessor().value());

  // Left side is the "base" identifier.
  const IdentifierExprNode* base = access->left()->AsIdentifier();
  ASSERT_TRUE(base);
  EXPECT_EQ("base", base->ident().GetFullName());

  // Member name.
  EXPECT_EQ("member", access->member().GetFullName());
}

TEST_F(ExprParserTest, AccessorAtEnd) {
  auto result = Parse("base. ");
  ASSERT_FALSE(result);

  EXPECT_EQ("Expected identifier for right-hand-side of \".\".",
            parser().err().msg());

  EXPECT_EQ(4u, parser().error_token().byte_offset());
  EXPECT_EQ(".", parser().error_token().value());
}

TEST_F(ExprParserTest, BadAccessorMemberName) {
  auto result = Parse("base->23");
  ASSERT_FALSE(result);

  EXPECT_EQ("Expected identifier for right-hand-side of \"->\".",
            parser().err().msg());

  // This error reports the "->" as the location, one could also imagine
  // reporting the right-side token (if any) instead.
  EXPECT_EQ(4u, parser().error_token().byte_offset());
  EXPECT_EQ("->", parser().error_token().value());
}

TEST_F(ExprParserTest, Arrow) {
  auto result = Parse("base->member");
  ASSERT_TRUE(result);

  const MemberAccessExprNode* access = result->AsMemberAccess();
  ASSERT_TRUE(access);
  EXPECT_EQ(ExprToken::kArrow, access->accessor().type());
  EXPECT_EQ("->", access->accessor().value());

  // Left side is the "base" identifier.
  const IdentifierExprNode* base = access->left()->AsIdentifier();
  ASSERT_TRUE(base);
  EXPECT_EQ("base", base->ident().GetFullName());

  // Member name.
  EXPECT_EQ("member", access->member().GetFullName());

  // Arrow with no name.
  result = Parse("base->");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected identifier for right-hand-side of \"->\".",
            parser().err().msg());
}

TEST_F(ExprParserTest, NestedDotArrow) {
  // These should be left-associative so do the "." first, then the "->".
  // When evaluating the tree, one first evaluates the left side of the
  // accessor, then the right, which is why it looks backwards in the dump.
  EXPECT_EQ(
      "ACCESSOR(->)\n"
      " ACCESSOR(.)\n"
      "  IDENTIFIER(\"foo\")\n"
      "  bar\n"
      " baz\n",
      GetParseString("foo.bar->baz"));
}

TEST_F(ExprParserTest, UnexpectedInput) {
  auto result = Parse("foo 5");
  ASSERT_FALSE(result);

  EXPECT_EQ("Unexpected input, did you forget an operator?",
            parser().err().msg());
  EXPECT_EQ(4u, parser().error_token().byte_offset());
}

TEST_F(ExprParserTest, ArrayAccess) {
  EXPECT_EQ(
      "ARRAY_ACCESS\n"
      " ARRAY_ACCESS\n"
      "  ACCESSOR(->)\n"
      "   ACCESSOR(.)\n"
      "    IDENTIFIER(\"foo\")\n"
      "    bar\n"
      "   baz\n"
      "  LITERAL(34)\n"
      " IDENTIFIER(\"bar\")\n",
      GetParseString("foo.bar->baz[34][bar]"));

  // Empty array access is an error.
  auto result = Parse("foo[]");
  ASSERT_FALSE(result);
  EXPECT_EQ("Unexpected token ']'.", parser().err().msg());
}

TEST_F(ExprParserTest, DereferenceAndAddress) {
  EXPECT_EQ(
      "DEREFERENCE\n"
      " IDENTIFIER(\"foo\")\n",
      GetParseString("*foo"));

  EXPECT_EQ(
      "ADDRESS_OF\n"
      " IDENTIFIER(\"foo\")\n",
      GetParseString("&foo"));

  // "*" and "&" should be right-associative with respect to each other but
  // lower precedence than -> and [].
  EXPECT_EQ(
      "ADDRESS_OF\n"
      " DEREFERENCE\n"
      "  ADDRESS_OF\n"
      "   ARRAY_ACCESS\n"
      "    ACCESSOR(->)\n"
      "     IDENTIFIER(\"foo\")\n"
      "     bar\n"
      "    LITERAL(1)\n",
      GetParseString("&*&foo->bar[1]"));

  // "*" by itself is an error.
  auto result = Parse("*");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected expression for '*'.", parser().err().msg());
  EXPECT_EQ(0u, parser().error_token().byte_offset());
}

// () should override the default precedence of other operators.
TEST_F(ExprParserTest, Parens) {
  EXPECT_EQ(
      "ADDRESS_OF\n"
      " ARRAY_ACCESS\n"
      "  DEREFERENCE\n"
      "   ACCESSOR(->)\n"
      "    ADDRESS_OF\n"
      "     IDENTIFIER(\"foo\")\n"
      "    bar\n"
      "  LITERAL(1)\n",
      GetParseString("(&(*(&foo)->bar)[1])"));
}

// This test covers that the extent of number tokens are identified properly.
// Actually converting the strings to integers should be covered by the number
// parser tests.
TEST_F(ExprParserTest, IntegerLiterals) {
  EXPECT_EQ("LITERAL(5)\n", GetParseString("5"));
  EXPECT_EQ("LITERAL(5ull)\n", GetParseString(" 5ull"));
  EXPECT_EQ("LITERAL(0xAbC)\n", GetParseString("0xAbC"));
  EXPECT_EQ("LITERAL(0o551)\n", GetParseString("  0o551 "));
  EXPECT_EQ("LITERAL(0123)\n", GetParseString("0123"));
}

TEST_F(ExprParserTest, UnaryMath) {
  EXPECT_EQ(
      "UNARY(-)\n"
      " LITERAL(5)\n",
      GetParseString("-5"));
  EXPECT_EQ(
      "UNARY(-)\n"
      " LITERAL(5)\n",
      GetParseString(" - 5 "));

  EXPECT_EQ(
      "UNARY(-)\n"
      " DEREFERENCE\n"
      "  IDENTIFIER(\"foo\")\n",
      GetParseString("-*foo"));

  // "-" by itself is an error.
  auto result = Parse("-");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected expression for '-'.", parser().err().msg());
  EXPECT_EQ(0u, parser().error_token().byte_offset());
}

TEST_F(ExprParserTest, AndOr) {
  EXPECT_EQ(
      "BINARY_OP(&&)\n"
      " BINARY_OP(&)\n"
      "  ADDRESS_OF\n"
      "   IDENTIFIER(\"a\")\n"
      "  ADDRESS_OF\n"
      "   IDENTIFIER(\"b\")\n"
      " BINARY_OP(&)\n"
      "  IDENTIFIER(\"c\")\n"
      "  IDENTIFIER(\"d\")\n",
      GetParseString("& a & & b && c & d"));
  EXPECT_EQ(
      "BINARY_OP(||)\n"
      " BINARY_OP(|)\n"
      "  IDENTIFIER(\"a\")\n"
      "  IDENTIFIER(\"b\")\n"
      " BINARY_OP(|)\n"
      "  IDENTIFIER(\"c\")\n"
      "  IDENTIFIER(\"d\")\n",
      GetParseString("a | b || c | d"));
  EXPECT_EQ(
      "BINARY_OP(||)\n"
      " BINARY_OP(&&)\n"
      "  IDENTIFIER(\"a\")\n"
      "  IDENTIFIER(\"b\")\n"
      " BINARY_OP(&&)\n"
      "  IDENTIFIER(\"c\")\n"
      "  IDENTIFIER(\"d\")\n",
      GetParseString("a && b || c && d"));
}

TEST_F(ExprParserTest, Identifiers) {
  EXPECT_EQ("IDENTIFIER(\"foo\")\n", GetParseString("foo"));
  EXPECT_EQ("IDENTIFIER(::,\"foo\")\n", GetParseString("::foo"));
  EXPECT_EQ("IDENTIFIER(::,\"foo\"; ::,\"bar\")\n",
            GetParseString("::foo :: bar"));

  auto result = Parse("::");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected name after '::'.", parser().err().msg());

  result = Parse(":: :: name");
  ASSERT_FALSE(result);
  EXPECT_EQ(
      "Could not identify thing to the left of '::' as a type or namespace.",
      parser().err().msg());

  result = Parse("foo bar");
  ASSERT_FALSE(result);
  EXPECT_EQ("Unexpected identifier, did you forget an operator?",
            parser().err().msg());

  // It's valid to have identifiers with colons in them to access class members
  // (this is how you provide an explicit base class).
  /* TODO(brettw) convert an accessor to use an Identifier for the name so this
     test works.
  EXPECT_EQ(
      "ACCESSOR(->)\n"
      "  IDENTIFIER(\"foo\")\n",
      GetParseString("foo->Baz::bar"));
  */
}

TEST_F(ExprParserTest, FunctionCall) {
  // Simple call with no args.
  EXPECT_EQ("FUNCTIONCALL(\"Call\")\n", GetParseString("Call()"));

  // Scoped call with namespaces and templates.
  EXPECT_EQ(R"(FUNCTIONCALL("ns"; ::,"Foo",<"int">; ::,"GetCurrent"))"
            "\n",
            GetParseString("ns::Foo<int>::GetCurrent()"));

  // One arg.
  EXPECT_EQ(
      "FUNCTIONCALL(\"Call\")\n"
      " LITERAL(42)\n",
      GetParseString("Call(42)"));

  // Several complex args and a nested call.
  EXPECT_EQ(
      "FUNCTIONCALL(\"Call\")\n"
      " IDENTIFIER(\"a\")\n"
      " BINARY_OP(=)\n"
      "  IDENTIFIER(\"b\")\n"
      "  LITERAL(5)\n"
      " FUNCTIONCALL(\"OtherCall\")\n",
      GetParseString("Call(a, b = 5, OtherCall())"));

  // Unmatched "(" error.
  auto result = Parse("Call(a, ");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected ')' to match. Hit the end of input instead.",
            parser().err().msg());

  // Arguments not separated by commas.
  result = Parse("Call(a b)");
  ASSERT_FALSE(result);
  EXPECT_EQ("Unexpected identifier, did you forget an operator?",
            parser().err().msg());

  // Empty parameter
  result = Parse("Call(a, , b)");
  ASSERT_FALSE(result);
  EXPECT_EQ("Unexpected token ','.", parser().err().msg());

  // Trailing comma.
  result = Parse("Call(a,)");
  ASSERT_FALSE(result);
  EXPECT_EQ("Unexpected token ')'.", parser().err().msg());

  // Thing on the left is not an identifier.
  result = Parse("5()");
  ASSERT_FALSE(result);
  EXPECT_EQ("Unexpected '('.", parser().err().msg());
}

TEST_F(ExprParserTest, Templates) {
  EXPECT_EQ(R"(IDENTIFIER("foo",<>))"
            "\n",
            GetParseString("foo<>"));
  EXPECT_EQ(R"(IDENTIFIER("foo",<"Foo">))"
            "\n",
            GetParseString("foo<Foo>"));
  EXPECT_EQ(R"(IDENTIFIER("foo",<"Foo", "5">))"
            "\n",
            GetParseString("foo< Foo,5 >"));
  EXPECT_EQ(
      R"(IDENTIFIER("std"; ::,"map",<"Key", "Value", "std::less<Key>", "std::allocator<std::pair<Key const, Value>>">; ::,"insert"))"
      "\n",
      GetParseString("std::map<Key, Value, std::less<Key>, "
                     "std::allocator<std::pair<Key const, Value>>>::insert"));

  // Unmatched "<" error. This is generated by the parser because it's
  // expecting the match for the outer level.
  auto result = Parse("std::map<Key, Value");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected '>' to match. Hit the end of input instead.",
            parser().err().msg());

  // This unmatched token is generated by the template type skipper which is
  // why the error message is slightly different (both are OK).
  result = Parse("std::map<key[, value");
  ASSERT_FALSE(result);
  EXPECT_EQ("Unmatched '['.", parser().err().msg());

  // Duplicate template spec.
  result = Parse("Foo<Bar><Baz>");
  ASSERT_FALSE(result);
  EXPECT_EQ("Comparisons not supported yet.", parser().err().msg());

  // Empty value.
  result = Parse("Foo<1,,2>");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected template parameter.", parser().err().msg());

  // Trailing comma.
  result = Parse("Foo<Bar,>");
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected template parameter.", parser().err().msg());
}

TEST_F(ExprParserTest, BinaryOp) {
  EXPECT_EQ(
      "BINARY_OP(=)\n"
      " IDENTIFIER(\"a\")\n"
      " LITERAL(23)\n",
      GetParseString("a = 23"));
}

// Tests parsing identifier names that require lookups from the symbol system.
// See TestLookupName above for the mocked symbol rules.
TEST_F(ExprParserTest, NamesWithSymbolLookup) {
  // Bare namespace is an error.
  auto result = Parse("Namespace", &TestLookupName);
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected expression after namespace name.", parser().err().msg());

  // Bare template is an error.
  result = Parse("Template", &TestLookupName);
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected template args after template name.",
            parser().err().msg());

  // Nothing after "::"
  result = Parse("Namespace::", &TestLookupName);
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected name after '::'.", parser().err().msg());

  // Can't put a template on a type that's not a template.
  result = Parse("Type<int>", &TestLookupName);
  ASSERT_FALSE(result);
  // This error message might change with future type support because it might
  // look like a comparison between a type and an int.
  EXPECT_EQ("Template parameters not valid on this object type.",
            parser().err().msg());

  // Can't put a template on a namespace.
  result = Parse("Namespace<int>", &TestLookupName);
  ASSERT_FALSE(result);
  EXPECT_EQ("Template parameters not valid on this object type.",
            parser().err().msg());

  // Good type name.
  EXPECT_EQ(
      "FUNCTIONCALL(\"Namespace\"; ::,\"Template\",<\"int\">; ::,\"fn\")\n",
      GetParseString("Namespace::Template<int>::fn()", &TestLookupName));
}

TEST_F(ExprParserTest, TrueFalse) {
  EXPECT_EQ("LITERAL(true)\n", GetParseString("true"));
  EXPECT_EQ("LITERAL(false)\n", GetParseString("false"));
  EXPECT_EQ(
      "BINARY_OP(&&)\n"
      " LITERAL(false)\n"
      " LITERAL(true)\n",
      GetParseString("false&&true"));
}

TEST_F(ExprParserTest, Types) {
  EXPECT_EQ("TYPE(Type)\n", GetParseString("Type", &TestLookupName));
  EXPECT_EQ("IDENTIFIER(\"NotType\")\n",
            GetParseString("NotType", &TestLookupName));

  EXPECT_EQ("TYPE(const Type)\n",
            GetParseString("const Type", &TestLookupName));
  EXPECT_EQ("TYPE(const Type)\n",
            GetParseString("Type const", &TestLookupName));

  // It would be better it this printed as "const volatile Type" but our
  // heuristic for moving modifiers to the beginning isn't good enough.
  EXPECT_EQ("TYPE(volatile Type const)\n",
            GetParseString("const volatile Type", &TestLookupName));

  // Duplicate const qualifications.
  auto result = Parse("const Type const", &TestLookupName);
  ASSERT_FALSE(result);
  EXPECT_EQ("Duplicate 'const' type qualification.", parser().err().msg());
  result = Parse("const const Type", &TestLookupName);
  ASSERT_FALSE(result);
  EXPECT_EQ("Duplicate 'const' type qualification.", parser().err().msg());

  EXPECT_EQ("TYPE(Type*)\n", GetParseString("Type*", &TestLookupName));
  EXPECT_EQ("TYPE(Type**)\n", GetParseString("Type * *", &TestLookupName));
  EXPECT_EQ("TYPE(Type&&)\n", GetParseString("Type &&", &TestLookupName));
  EXPECT_EQ("TYPE(Type&**)\n", GetParseString("Type&**", &TestLookupName));
  EXPECT_EQ("TYPE(volatile Type* restrict* const)\n",
            GetParseString("Type volatile *restrict* const", &TestLookupName));

  // "const" should force us into type mode.
  result = Parse("const NonType", &TestLookupName);
  ASSERT_FALSE(result);
  EXPECT_EQ("Expected a type name but could not find a type named 'NonType'.",
            parser().err().msg());

  // Try sizeof() with both a type and a non-type.
  EXPECT_EQ(
      "FUNCTIONCALL(\"sizeof\")\n"
      " TYPE(Type*)\n",
      GetParseString("sizeof(Type*)", &TestLookupName));
  EXPECT_EQ(
      "FUNCTIONCALL(\"sizeof\")\n"
      " IDENTIFIER(\"foo\")\n",
      GetParseString("sizeof(foo)", &TestLookupName));
}

TEST_F(ExprParserTest, Casts) {
  EXPECT_EQ(
      "CAST(C)\n"
      " TYPE(Type)\n"
      " IDENTIFIER(\"a\")\n",
      GetParseString("(Type)(a)", &TestLookupName));

  EXPECT_EQ(
      "BINARY_OP(&&)\n"
      " CAST(C)\n"
      "  TYPE(Type*)\n"
      "  IDENTIFIER(\"a\")\n"
      " IDENTIFIER(\"b\")\n",
      GetParseString("(Type*)a && b", &TestLookupName));

  // Looks like a cast but it's not a type.
  auto result = Parse("(NotType)a", &TestLookupName);
  EXPECT_FALSE(result);
  EXPECT_EQ("Unexpected input, did you forget an operator?",
            parser().err().msg());
}

}  // namespace zxdb