// Copyright 2019 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/client/stack.h"

#include <lib/syslog/cpp/macros.h>

#include <map>

#include <gtest/gtest.h>

#include "llvm/BinaryFormat/Dwarf.h"
#include "src/developer/debug/shared/message_loop.h"
#include "src/developer/debug/zxdb/client/frame_fingerprint.h"
#include "src/developer/debug/zxdb/client/mock_frame.h"
#include "src/developer/debug/zxdb/client/mock_stack_delegate.h"
#include "src/developer/debug/zxdb/common/err.h"
#include "src/developer/debug/zxdb/common/test_with_loop.h"
#include "src/developer/debug/zxdb/expr/eval_context.h"
#include "src/developer/debug/zxdb/expr/expr.h"
#include "src/developer/debug/zxdb/symbols/function.h"
#include "src/developer/debug/zxdb/symbols/type_test_support.h"
#include "src/developer/debug/zxdb/symbols/variable.h"

namespace zxdb {

namespace {

class StackTest : public TestWithLoop {};

// Stack pointers used by MakeInlineStackFrames.
constexpr uint64_t kTopSP = 0x2000;
constexpr uint64_t kMiddleSP = 0x2020;
constexpr uint64_t kBottomSP = 0x2040;

// Returns a set of stack frames:
//   [0] =   inline #2 from frame 2
//   [1] =   inline #1 from frame 2
//   [2] = physical frame at kTopSP
//   [3] =   inline from frame 4
//   [4] = physical frame at kMiddleSP
//   [5] = physical frame at kBottomSP
std::vector<std::unique_ptr<Frame>> MakeInlineStackFrames() {
  // Create three physical frames.
  Location top_location(Location::State::kSymbolized, 0x1000);
  Location middle_location(Location::State::kSymbolized, 0x1010);
  Location bottom_location(Location::State::kSymbolized, 0x1020);

  auto phys_top = std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP, kMiddleSP);
  auto phys_middle =
      std::make_unique<MockFrame>(nullptr, nullptr, middle_location, kMiddleSP, kBottomSP);
  auto phys_bottom = std::make_unique<MockFrame>(nullptr, nullptr, bottom_location, kBottomSP, 0);

  std::vector<std::unique_ptr<Frame>> frames;

  // Top frame has two inline functions expanded on top of it. This uses the same Location object
  // for simplicity, in real life these will be different.
  frames.push_back(std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP, kMiddleSP,
                                               std::vector<debug_ipc::Register>(), kTopSP,
                                               phys_top.get()));
  frames.push_back(std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP, kMiddleSP,
                                               std::vector<debug_ipc::Register>(), kTopSP,
                                               phys_top.get()));

  // Physical top frame below those.
  frames.push_back(std::move(phys_top));

  // Middle frame has one inline function expanded on top of it.
  frames.push_back(std::make_unique<MockFrame>(nullptr, nullptr, middle_location, kMiddleSP,
                                               kBottomSP, std::vector<debug_ipc::Register>(),
                                               kMiddleSP, phys_middle.get()));
  frames.push_back(std::move(phys_middle));

  // Bottom frame has no inline frame.
  frames.push_back(std::move(phys_bottom));

  return frames;
}

}  // namespace

// IndexForFrame is trivial when there's no inline frame, but when there is, the returned index
// must take this into account.
TEST_F(StackTest, IndexForFrame) {
  MockStackDelegate delegate;
  Stack stack(&delegate);
  delegate.set_stack(&stack);

  // Set some stack frames with inline frames. Nothing should start out as hidden.
  auto frames = MakeInlineStackFrames();

  // Make a function for the top stack frame. It needs this to get the ranges for the ambiguity
  // comuptation.
  auto func = fxl::MakeRefCounted<Function>(DwarfTag::kInlinedSubroutine);
  func->set_assigned_name("Inline");
  // Must start exactly at kBottomAddr for the location to be ambiguous.
  uint64_t ambiguous_address = frames[0]->GetLocation().address();
  func->set_code_ranges(AddressRanges(AddressRange(ambiguous_address, ambiguous_address + 8)));

  // Force the top frame to be ambiguous. For this it needs an inline function that starts at the
  // current address.
  Location ambig_loc(ambiguous_address, FileLine("file", 10), 0,
                     SymbolContext::ForRelativeAddresses(), func);
  auto new_top_frame = std::make_unique<MockFrame>(nullptr, nullptr, ambig_loc, kTopSP, kMiddleSP,
                                                   std::vector<debug_ipc::Register>(), kTopSP,
                                                   frames[0]->GetPhysicalFrame());
  new_top_frame->set_is_ambiguous_inline(true);
  frames[0] = std::move(new_top_frame);

  stack.SetFramesForTest(std::move(frames), true);
  ASSERT_EQ(1u, stack.GetAmbiguousInlineFrameCount());
  EXPECT_EQ(0u, stack.hide_ambiguous_inline_frame_count());

  // The operator[] and the IndexForFrame results should match.
  for (size_t i = 0; i < stack.size(); i++)
    EXPECT_EQ(i, stack.IndexForFrame(stack[i])) << i;

  // Hide some inline frames, the indices should still match.
  stack.SetHideAmbiguousInlineFrameCount(1);
  for (size_t i = 0; i < stack.size(); i++)
    EXPECT_EQ(i, stack.IndexForFrame(stack[i])) << i;
}

// Tests fingerprint computations involving inline frames.
TEST_F(StackTest, InlineFingerprint) {
  MockStackDelegate delegate;
  Stack stack(&delegate);
  delegate.set_stack(&stack);
  stack.SetFramesForTest(MakeInlineStackFrames(), true);

  // The top frames (physical and inline) have the middle frame's SP as their fingerprint, along
  // with the inline count.
  EXPECT_EQ(FrameFingerprint(kMiddleSP, 2), stack.GetFrameFingerprint(0));
  EXPECT_EQ(2u, stack.InlineDepthForIndex(0));
  EXPECT_EQ(FrameFingerprint(kMiddleSP, 1), stack.GetFrameFingerprint(1));
  EXPECT_EQ(1u, stack.InlineDepthForIndex(1));
  EXPECT_EQ(FrameFingerprint(kMiddleSP, 0), stack.GetFrameFingerprint(2));
  EXPECT_EQ(0u, stack.InlineDepthForIndex(2));

  // Middle frames have the bottom frame's SP.
  EXPECT_EQ(FrameFingerprint(kBottomSP, 1), stack.GetFrameFingerprint(3));
  EXPECT_EQ(1u, stack.InlineDepthForIndex(3));
  EXPECT_EQ(FrameFingerprint(kBottomSP, 0), stack.GetFrameFingerprint(4));
  EXPECT_EQ(0u, stack.InlineDepthForIndex(4));

  // Bottom frame reports the 0 CFA.
  EXPECT_EQ(FrameFingerprint(0, 0), stack.GetFrameFingerprint(5));
  EXPECT_EQ(0u, stack.InlineDepthForIndex(5));
}

// Tests that stack frames inside inline functions are expanded so that the inline functions have
// their own "inline" frames.
//
// This tests a bottom function calling an inline function which calls a top function. The tricky
// part is the IP of the bottom frame is actually in a different inline function (the "ambiguous"
// one) because the address in the bottom frame is immediately following the TopFunc() call and this
// happens to fall in range of an inlined function. This should be omitted from the stack.
//
//   void TopFunc() {
//     ...                          // <- top_line
//   }
//
//   // Not actually on the stack but looks like it.
//   inline void bottom_ambig_inline_func() {
//     ...                          // <- inline_exec_line
//   }
//
//   inline void bottom_inline_func() {
//     ...
//     TopFunc();                   // Non-inline
//     bottom_ambig_inline_func();  // <- inline_ambig_call_line
//   }
//
//   void bottom() {
//     ...
//     bottom_inline_func();       // <- inline_call_line
//     ...
//   }
TEST_F(StackTest, InlineExpansion) {
  constexpr uint64_t kBottomAddr = 0x127365;  // IP for bottom stack frame.
  constexpr uint64_t kTopAddr = 0x893746123;  // IP for top stack frale.

  const char kFileName[] = "file.cc";
  FileLine inline_ambig_call_line(kFileName, 5);
  FileLine inline_call_line(kFileName, 10);
  FileLine inline_exec_line(kFileName, 20);
  FileLine top_line(kFileName, 30);

  MockStackDelegate delegate;
  SymbolContext symbol_context = SymbolContext::ForRelativeAddresses();

  // Non-inline location for the top stack frame.
  auto top_func = fxl::MakeRefCounted<Function>(DwarfTag::kSubprogram);
  top_func->set_assigned_name("Top");
  Location top_location(kTopAddr, top_line, 0, symbol_context, top_func);
  delegate.AddLocation(top_location);

  // Bottom stack frame has a real function, an inline function, and an ambiguous inline location
  // (at the start of an inline range).
  auto bottom_ambig_inline_func = fxl::MakeRefCounted<Function>(DwarfTag::kInlinedSubroutine);
  bottom_ambig_inline_func->set_assigned_name("Inline");
  // Must start exactly at kBottomAddr for the location to be ambiguous.
  bottom_ambig_inline_func->set_code_ranges(
      AddressRanges(AddressRange(kBottomAddr, kBottomAddr + 8)));
  bottom_ambig_inline_func->set_call_line(inline_ambig_call_line);

  auto bottom_inline_func = fxl::MakeRefCounted<Function>(DwarfTag::kInlinedSubroutine);
  bottom_inline_func->set_assigned_name("Inline");
  // Must start before at kBottomAddr for the location to not be ambiguous.
  bottom_inline_func->set_code_ranges(
      AddressRanges(AddressRange(kBottomAddr - 8, kBottomAddr + 8)));
  bottom_inline_func->set_call_line(inline_call_line);

  auto bottom_func = fxl::MakeRefCounted<Function>(DwarfTag::kSubprogram);
  bottom_func->set_assigned_name("Bottom");
  bottom_func->set_code_ranges(AddressRanges(AddressRange(kBottomAddr - 8, kBottomAddr + 16)));

  // Our containing functions don't have references to the contained functions so we don't have to
  // worry about a reference cycle here (hence "unsafe").
  bottom_ambig_inline_func->set_containing_block(
      UncachedLazySymbol::MakeUnsafe(bottom_inline_func));
  bottom_inline_func->set_containing_block(UncachedLazySymbol::MakeUnsafe(bottom_func));

  // The location returned by the symbol function will have the file/line inside the inline
  // function.
  Location bottom_location(kBottomAddr, inline_exec_line, 0, symbol_context,
                           bottom_ambig_inline_func);
  delegate.AddLocation(bottom_location);

  Stack stack(&delegate);
  delegate.set_stack(&stack);

  // Send IPs that will map to the bottom and top addresses.
  constexpr uint64_t kTopSP = 0x100;
  constexpr uint64_t kBottomSP = 0x200;

  stack.SetFrames(debug_ipc::ThreadRecord::StackAmount::kFull,
                  {debug_ipc::StackFrame(kTopAddr, kTopSP, kBottomSP),
                   debug_ipc::StackFrame(kBottomAddr, kBottomSP, 0)});

  // This should expand to tree stack entries, the one in the middle should be the inline function
  // expanded from the "bottom".
  EXPECT_EQ(3u, stack.size());

  // Bottom stack frame should be the non-inline bottom function.
  EXPECT_FALSE(stack[2]->IsInline());
  EXPECT_EQ(stack[2], stack[2]->GetPhysicalFrame());
  EXPECT_EQ(kBottomAddr, stack[2]->GetAddress());
  Location loc = stack[2]->GetLocation();
  EXPECT_EQ(kBottomAddr, loc.address());
  EXPECT_EQ(inline_call_line, loc.file_line());
  EXPECT_EQ(bottom_func.get(), loc.symbol().Get()->AsFunction());

  // Middle stack frame should be the inline bottom function, referencing the bottom one as the
  // physical frame. The location should be the call line of the ambiguous inline function because
  // it's next, even though that function was omitted from the stack.
  EXPECT_TRUE(stack[1]->IsInline());
  EXPECT_EQ(stack[2], stack[1]->GetPhysicalFrame());
  EXPECT_EQ(kBottomAddr, stack[1]->GetAddress());
  loc = stack[1]->GetLocation();
  EXPECT_EQ(kBottomAddr, loc.address());
  EXPECT_EQ(inline_ambig_call_line, loc.file_line());
  EXPECT_EQ(bottom_inline_func.get(), loc.symbol().Get()->AsFunction());

  // The bottom_ambig_inline_func should be skipped because it's at the beginning of an inline call
  // and it's not at the top physical frame of the stack.

  // Top stack frame.
  EXPECT_FALSE(stack[0]->IsInline());
  EXPECT_EQ(stack[0], stack[0]->GetPhysicalFrame());
  EXPECT_EQ(kTopAddr, stack[0]->GetAddress());
  loc = stack[0]->GetLocation();
  EXPECT_EQ(kTopAddr, loc.address());
  EXPECT_EQ(top_line, loc.file_line());
  EXPECT_EQ(top_func.get(), loc.symbol().Get()->AsFunction());
}

TEST_F(StackTest, InlineHiding) {
  constexpr uint64_t kTopSP = 0x2000;
  constexpr uint64_t kBottomSP = 0x2020;

  // Create two physical frames.
  Location top_location(Location::State::kSymbolized, 0x1000);
  Location bottom_location(Location::State::kSymbolized, 0x1020);

  auto phys_top = std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP);
  auto phys_bottom = std::make_unique<MockFrame>(nullptr, nullptr, bottom_location, kBottomSP);

  std::vector<std::unique_ptr<Frame>> frames;

  // Top frame has two inline functions expanded on top of it.
  frames.push_back(std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP, 0,
                                               std::vector<debug_ipc::Register>(), kTopSP,
                                               phys_top.get(), true));
  frames.push_back(std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP, 0,
                                               std::vector<debug_ipc::Register>(), kTopSP,
                                               phys_top.get(), true));

  // Physical top frame below those.
  frames.push_back(std::move(phys_top));

  // Bottom frame has no inline frame.
  frames.push_back(std::move(phys_bottom));

  MockStackDelegate delegate;
  Stack stack(&delegate);
  delegate.set_stack(&stack);

  // With no frames, there should be no inline frames.
  EXPECT_EQ(0u, stack.GetAmbiguousInlineFrameCount());

  // Setting the frames should give the two inline ones, followed by two physical ones.
  stack.SetFramesForTest(std::move(frames), true);
  EXPECT_EQ(4u, stack.size());
  EXPECT_EQ(2u, stack.GetAmbiguousInlineFrameCount());

  // Hide both inline frames, the top frame should now be the physical one.
  stack.SetHideAmbiguousInlineFrameCount(2);
  EXPECT_EQ(2u, stack.size());
  EXPECT_EQ(2u, stack.GetAmbiguousInlineFrameCount());
}

// Appends stack items to an already existing stack via SetFrames(). The existing frames and the
// inline hide count should be unchanged.
TEST_F(StackTest, UpdateExisting) {
  MockStackDelegate delegate;
  Stack stack(&delegate);
  delegate.set_stack(&stack);

  // Make a stack with one physial frame and one inline frame above it.
  Location top_location(Location::State::kSymbolized, 0x1000);
  auto phys_top = std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP, 0,
                                              std::vector<debug_ipc::Register>(), kTopSP);
  auto inline_top =
      std::make_unique<MockFrame>(nullptr, nullptr, top_location, kTopSP, 0,
                                  std::vector<debug_ipc::Register>(), kTopSP, phys_top.get(), true);
  inline_top->set_is_ambiguous_inline(true);

  // Save for verification later.
  const Frame* frame0 = inline_top.get();
  const Frame* frame1 = phys_top.get();

  std::vector<std::unique_ptr<Frame>> input_frames;
  input_frames.push_back(std::move(inline_top));
  input_frames.push_back(std::move(phys_top));
  stack.SetFramesForTest(std::move(input_frames), true);

  // The ambiguous inline frame is hidden so we can check later this is preserved across updates.
  ASSERT_EQ(2u, stack.size());
  ASSERT_EQ(1u, stack.GetAmbiguousInlineFrameCount());
  stack.SetHideAmbiguousInlineFrameCount(1);

  // Synthesize a frame update. The first physical frame matches the first physical frame from
  // above. This uses the non-test update flow which should preserve the frame objects that haven't
  // changed.
  std::vector<debug_ipc::StackFrame> raw_frames;
  debug_ipc::StackFrame phys_top_record(0x1000, kTopSP, kBottomSP);
  raw_frames.push_back(phys_top_record);
  debug_ipc::StackFrame phys_bottom_record(0x1020, kBottomSP);
  raw_frames.push_back(phys_bottom_record);

  stack.SetFrames(debug_ipc::ThreadRecord::StackAmount::kFull, raw_frames);

  // The update should have left the existing top physical frame and the inline frame expanded on
  // top of it, and add the additional physical frame below it.
  EXPECT_EQ(1u, stack.GetAmbiguousInlineFrameCount());
  // Now that we checked it, reset the hidden frame count so we can see them.
  stack.SetHideAmbiguousInlineFrameCount(0);
  ASSERT_EQ(3u, stack.size());
  EXPECT_EQ(frame0, stack[0]);
  EXPECT_EQ(frame1, stack[1]);
  EXPECT_EQ(phys_bottom_record.ip, stack[2]->GetAddress());

  // Now supply a slightly different stack, it should be replaced and the hidden inline frame count
  // reset.
  stack.SetHideAmbiguousInlineFrameCount(0);  // So we can test for reset.
  raw_frames[0].sp++;                         // Modify frame.
  stack.SetFrames(debug_ipc::ThreadRecord::StackAmount::kFull, raw_frames);

  // The inline frame at the top should have gone away because we didn't provide any inline
  // information for the Stack to expand it.
  ASSERT_EQ(2u, stack.size());
  EXPECT_EQ(0u, stack.GetAmbiguousInlineFrameCount());
  EXPECT_EQ(raw_frames[0].ip, stack[0]->GetAddress());
  EXPECT_EQ(raw_frames[0].sp, stack[0]->GetStackPointer());
  EXPECT_EQ(raw_frames[1].ip, stack[1]->GetAddress());
  EXPECT_EQ(raw_frames[1].sp, stack[1]->GetStackPointer());
}

// Tests that variables in inline functions are found during evaluation.
//
// This sets up an inline frame and makes sure we can read a local variable out of it.
TEST_F(StackTest, InlineVars) {
  constexpr uint64_t kInlineAddr = 0x1002;
  constexpr uint64_t kPhysAddr = 0x1000;

  MockStackDelegate delegate;
  SymbolContext symbol_context = SymbolContext::ForRelativeAddresses();

  // Make inline function.
  auto inline_func = fxl::MakeRefCounted<Function>(DwarfTag::kInlinedSubroutine);
  inline_func->set_code_ranges(AddressRanges(AddressRange(kInlineAddr, kInlineAddr + 8)));

  // The inline function has a local variable ("var") that always evaluates to 3.
  VariableLocation::Entry loc_entry;
  loc_entry.expression = {llvm::dwarf::DW_OP_lit3, llvm::dwarf::DW_OP_stack_value};
  VariableLocation var_loc({loc_entry});

  auto int32_type = MakeInt32Type();
  auto inline_var =
      fxl::MakeRefCounted<Variable>(DwarfTag::kVariable, "var", LazySymbol(int32_type), var_loc);
  inline_func->set_variables({LazySymbol(inline_var)});

  // Make physical fuction.
  auto phys_func = fxl::MakeRefCounted<Function>(DwarfTag::kSubprogram);
  phys_func->set_code_ranges(AddressRanges(AddressRange(kPhysAddr, kPhysAddr + 16)));
  inline_func->set_containing_block(UncachedLazySymbol::MakeUnsafe(phys_func));

  // Physical stack frame.
  Location phys_location(kPhysAddr, FileLine("file.cc", 200), 0, symbol_context, phys_func);
  delegate.AddLocation(phys_location);

  // Inline frame on top of that.
  Location inline_location(kInlineAddr, FileLine("file.cc", 100), 0, symbol_context, inline_func);
  delegate.AddLocation(inline_location);

  Stack stack(&delegate);
  delegate.set_stack(&stack);

  stack.SetFrames(debug_ipc::ThreadRecord::StackAmount::kFull,
                  {debug_ipc::StackFrame(kInlineAddr, kTopSP, kBottomSP)});
  ASSERT_EQ(2u, stack.size());  // Should have expanded the inline frame.

  // ACTUAL TEST.

  // Evaluate "var + 1" which should be "4" given var evaluates to 3.
  auto eval_context = stack[0]->GetEvalContext();
  bool called = false;
  EvalExpression("var + 1", eval_context, true, [&called](ErrOrValue value) mutable {
    called = true;
    EXPECT_FALSE(value.has_error());

    int64_t result = 0;
    Err e = value.value().PromoteTo64(&result);
    EXPECT_FALSE(e.has_error());
    EXPECT_EQ(4, result);
  });
  EXPECT_TRUE(called);  // Callback should have been issued.
}

}  // namespace zxdb