src/developer/debug/zxdb/expr/index_walker_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 "src/developer/debug/zxdb/expr/index_walker.h"

#include <gtest/gtest.h>

#include "src/developer/debug/zxdb/expr/expr_parser.h"
#include "src/developer/debug/zxdb/symbols/index.h"

namespace zxdb {

namespace {

bool EqualsElements(const IndexWalker::Stage& a, const IndexWalker::Stage& b) {
  if (a.size() != b.size())
    return false;

  for (const auto& cur : a) {
    if (std::find(b.begin(), b.end(), cur) == b.end())
      return false;
  }
  return true;
}

}  // namespace

TEST(IndexWalker, ComponentMatchesNameOnly) {
  ParsedIdentifierComponent foo_comp("Foo");
  ParsedIdentifierComponent foo_template_comp("Foo", {"A", "b"});

  // Simple name-only comparisons.
  EXPECT_TRUE(IndexWalker::ComponentMatchesNameOnly("Foo", foo_comp));
  EXPECT_FALSE(IndexWalker::ComponentMatchesNameOnly("FooBar", foo_comp));
  EXPECT_FALSE(IndexWalker::ComponentMatchesNameOnly("Fo2", foo_comp));

  // Component has a template, the index string doesn't.
  EXPECT_TRUE(IndexWalker::ComponentMatchesNameOnly("Foo", foo_template_comp));

  // Component has no template, the index does (this input is non-canonical).
  EXPECT_TRUE(IndexWalker::ComponentMatchesNameOnly("Foo < C >", foo_template_comp));
}

TEST(IndexWalker, ComponentMatchesTemplateOnly) {
  ParsedIdentifierComponent foo_comp("Foo");
  ParsedIdentifierComponent foo_template_comp("Foo", {"A", "b"});
  ParsedIdentifierComponent foo_empty_template_comp("Foo", {});

  // Neither inputs have templates (should be a match).
  EXPECT_TRUE(IndexWalker::ComponentMatchesTemplateOnly("Foo", foo_comp));

  // Template match but with different whitespace.
  EXPECT_TRUE(IndexWalker::ComponentMatchesTemplateOnly("Foo < A,  b > ", foo_template_comp));

  // One has a template but the other doesn't.
  EXPECT_FALSE(IndexWalker::ComponentMatchesTemplateOnly("Foo", foo_template_comp));
  EXPECT_FALSE(IndexWalker::ComponentMatchesTemplateOnly("Foo<C>", foo_comp));

  // Empty template doesn't match no template.
  EXPECT_FALSE(IndexWalker::ComponentMatchesTemplateOnly("Foo<>", foo_comp));
  EXPECT_FALSE(IndexWalker::ComponentMatchesTemplateOnly("Foo", foo_empty_template_comp));
}

// Most cases are tested by ComponentMatchesNameOnly and ...TemplateOnly above.
TEST(IndexWalker, ComponentMatches) {
  ParsedIdentifierComponent foo_comp("Foo");
  ParsedIdentifierComponent foo_template_comp("Foo", {"A", "b"});

  EXPECT_TRUE(IndexWalker::ComponentMatches("Foo", foo_comp));
  EXPECT_FALSE(IndexWalker::ComponentMatches("Foo<>", foo_comp));
  EXPECT_FALSE(IndexWalker::ComponentMatches("Foo<>", foo_template_comp));
  EXPECT_TRUE(IndexWalker::ComponentMatches("Foo <A,b >", foo_template_comp));
}

TEST(IndexWalker, IsIndexStringBeyondName) {
  // Identity comparison.
  EXPECT_FALSE(IndexWalker::IsIndexStringBeyondName("Foo", "Foo"));

  // Index nodes clearly before.
  EXPECT_FALSE(IndexWalker::IsIndexStringBeyondName("Fo", "Foo"));
  EXPECT_FALSE(IndexWalker::IsIndexStringBeyondName("Foa", "Foo"));

  // Index nodes clearly after.
  EXPECT_TRUE(IndexWalker::IsIndexStringBeyondName("FooBar", "Foo"));
  EXPECT_TRUE(IndexWalker::IsIndexStringBeyondName("Foz", "Foo"));
  EXPECT_TRUE(IndexWalker::IsIndexStringBeyondName("Fz", "Foo"));

  // Templates in the index could has "not beyond".
  EXPECT_FALSE(IndexWalker::IsIndexStringBeyondName("Foo<a>", "Foo"));
}

TEST(IndexWalker, WalkInto) {
  Index index;
  auto& root = index.root();
  auto foo_node = root.AddChild(IndexNode::Kind::kType, "Foo");
  root.AddChild(IndexNode::Kind::kType, "Foo<Bar>");

  // These template names are non-canonical so we can verify the correct comparisons happen.
  foo_node->AddChild(IndexNode::Kind::kType, "Bar< int >");
  auto bar_int_char_node = foo_node->AddChild(IndexNode::Kind::kType, "Bar< int,char >");

  // There could also be a non-template somewhere with the same name.
  auto bar_node = foo_node->AddChild(IndexNode::Kind::kType, "Bar");

  // These nodes start with the prefix "Bar" for when we're searching. We test things that will
  // compare before and after "Bar<" ('9' before, 'f' after).
  auto barf_node = foo_node->AddChild(IndexNode::Kind::kType, "Barf<int>");
  auto bar9_node = foo_node->AddChild(IndexNode::Kind::kType, "Bar9<int>");

  IndexWalker walker(&index);
  EXPECT_TRUE(EqualsElements(walker.current(), {&root}));

  // Walking up at this point should be a no-op.
  EXPECT_FALSE(walker.WalkUp());
  EXPECT_TRUE(EqualsElements(walker.current(), {&root}));

  // Walk to the "Foo" component.
  EXPECT_TRUE(walker.WalkInto(ParsedIdentifierComponent("Foo")));
  EXPECT_TRUE(EqualsElements(walker.current(), {foo_node}));

  // Walk to the "NotPresent" component. The current location should be unchanged.
  EXPECT_FALSE(walker.WalkInto(ParsedIdentifierComponent("NotFound")));
  EXPECT_TRUE(EqualsElements(walker.current(), {foo_node}));

  // Walk to the "Bar<int,char>" identifier.
  ParsedIdentifier bar_int_char;
  Err err = ExprParser::ParseIdentifier("Bar < int , char >", &bar_int_char);
  EXPECT_FALSE(err.has_error()) << err.msg();
  EXPECT_TRUE(walker.WalkInto(bar_int_char));
  EXPECT_TRUE(EqualsElements(walker.current(), {bar_int_char_node}));

  // Walk back up to "Foo".
  EXPECT_TRUE(walker.WalkUp());
  EXPECT_TRUE(EqualsElements(walker.current(), {foo_node}));

  // Walk to the "Bar" node.
  EXPECT_TRUE(walker.WalkInto(ParsedIdentifierComponent("Bar")));
  EXPECT_TRUE(EqualsElements(walker.current(), {bar_node}));

  // Parse the Barf identifier for the following two tests. This one has a toplevel scope.
  ParsedIdentifier barf;
  err = ExprParser::ParseIdentifier("::Foo::Barf<int>", &barf);
  EXPECT_FALSE(err.has_error()) << err.msg();

  // Walk to the "Foo::Bar9<int>" with copying the walker.
  {
    IndexWalker nested_walker(walker);
    ParsedIdentifier bar9;
    err = ExprParser::ParseIdentifier(":: Foo :: Bar9 < int >", &bar9);
    EXPECT_FALSE(err.has_error()) << err.msg();
    EXPECT_TRUE(nested_walker.WalkInto(bar9));
    EXPECT_TRUE(EqualsElements(nested_walker.current(), {bar9_node}));
  }

  // Walking from the root into the barf template should work.
  EXPECT_TRUE(walker.WalkInto(barf));
  EXPECT_TRUE(EqualsElements(walker.current(), {barf_node}));
}

// Tests that we can walk into multiple nodes of different types (namespaces, functions, etc.) at
// the same time when they have the same name.
TEST(IndexWalker, WalkIntoMultiple) {
  Index index;
  auto& root = index.root();
  const char kFoo[] = "Foo";
  auto foo_type_node = root.AddChild(IndexNode::Kind::kType, kFoo);
  auto foo_ns_node = root.AddChild(IndexNode::Kind::kNamespace, kFoo);
  auto foo_func_node = root.AddChild(IndexNode::Kind::kFunction, kFoo);
  auto foo_var_node = root.AddChild(IndexNode::Kind::kVar, kFoo);

  const char kBar[] = "Bar";
  auto foo_bar_type_func = foo_type_node->AddChild(IndexNode::Kind::kFunction, kBar);
  auto foo_bar_ns_func = foo_ns_node->AddChild(IndexNode::Kind::kFunction, kBar);

  IndexWalker walker(&index);
  IndexWalker::Stage expected_root{&root};
  EXPECT_TRUE(EqualsElements(walker.current(), expected_root));

  // Walking into "Foo" should identify all 4 categories of thing.
  EXPECT_TRUE(walker.WalkInto(ParsedIdentifierComponent(kFoo)));
  IndexWalker::Stage expected_foo{foo_type_node, foo_ns_node, foo_func_node, foo_var_node};
  EXPECT_TRUE(EqualsElements(walker.current(), expected_foo));

  // Walking into "Bar" from there should narrow down to two.
  EXPECT_TRUE(walker.WalkInto(ParsedIdentifierComponent(kBar)));
  IndexWalker::Stage expected_foo_bar{foo_bar_type_func, foo_bar_ns_func};
  EXPECT_TRUE(EqualsElements(walker.current(), expected_foo_bar));

  // Walking into something that doesn't exist reports failure and stays in the same place.
  EXPECT_FALSE(walker.WalkInto(ParsedIdentifierComponent("Nonexistant")));
  EXPECT_TRUE(EqualsElements(walker.current(), expected_foo_bar));

  // Walk up should give the same results.
  EXPECT_TRUE(walker.WalkUp());
  EXPECT_TRUE(EqualsElements(walker.current(), expected_foo));
  EXPECT_TRUE(walker.WalkUp());
  EXPECT_TRUE(EqualsElements(walker.current(), expected_root));

  // Going up above the root fails and does nothing.
  EXPECT_FALSE(walker.WalkUp());
  EXPECT_TRUE(EqualsElements(walker.current(), expected_root));
}

TEST(IndexWalker, WalkIntoAnonNS) {
  Index index;
  auto& root = index.root();

  // Anonymous and "ns" namespace at the top level.
  auto anon_ns = root.AddChild(IndexNode::Kind::kNamespace, "");
  const char kNsName[] = "ns";
  auto ns_ns = root.AddChild(IndexNode::Kind::kNamespace, kNsName);

  // Add a "Struct" at the toplevel and in the anon namespace.
  const char kStructName[] = "Struct";
  auto toplevel_struct = root.AddChild(IndexNode::Kind::kType, kStructName);
  auto anon_struct = anon_ns->AddChild(IndexNode::Kind::kType, kStructName);

  // Add a ns::<anon>::<anon>::OtherStruct type.
  const char kOtherStructName[] = "OtherStruct";
  auto ns_anon_ns = ns_ns->AddChild(IndexNode::Kind::kNamespace, "");
  auto ns_anon_anon_ns = ns_anon_ns->AddChild(IndexNode::Kind::kNamespace, "");
  auto otherstruct = ns_anon_anon_ns->AddChild(IndexNode::Kind::kType, kOtherStructName);

  IndexWalker walker(&index);
  // The initial search should be in the root and in the toplevel anonymous namespace.
  IndexWalker::Stage expected_root{&root, anon_ns};
  EXPECT_TRUE(EqualsElements(walker.current(), expected_root));

  // Walking into "Struct" should give both since we implicitly went into the anon namespace.
  EXPECT_TRUE(walker.WalkInto(ParsedIdentifier(kStructName)));
  IndexWalker::Stage expected_struct{toplevel_struct, anon_struct};
  EXPECT_TRUE(EqualsElements(walker.current(), expected_struct));

  // Go back to the root.
  EXPECT_TRUE(walker.WalkUp());

  // Walk into "ns::OtherStruct" which should find the one with two anon namespaces in it.
  ParsedIdentifier ns_otherstruct;
  ASSERT_TRUE(ExprParser::ParseIdentifier("ns::OtherStruct", &ns_otherstruct).ok());
  EXPECT_TRUE(walker.WalkInto(ns_otherstruct));
  IndexWalker::Stage expected_otherstruct{otherstruct};
  EXPECT_TRUE(EqualsElements(walker.current(), expected_otherstruct));
}

}  // namespace zxdb