Replace StackID's operator "<" with a function returning FrameComparison

[tatyana-krasnukha]

Summary

"false" result of the operator can imply not only "the frame is not younger". When CFAs are equal, StackID's operator "<" can only compare symbol contexts of the same function. Otherwise, it also returns false.

In the case I described in D114861, two different frames can have the same CFA, and then the operator's result may be incorrect. "thread step-*" commands get broken in this case.

This patch replaces the operator that can return only boolean value with the function that returns a value of lldb::FrameComparison type. It also updates thread plans to use this function instead of the operator.

[labath]

I don't really know what to make of this, but adding Jim for the thread plan changes.

[jingham]

IIUC, the crux of this change is having the comparison able to return eFrameCompareUnknown when the < operator was returning "less than", and the handling of Unknown in the various thread plans. Is that right? There's so much formal change here it's hard to see what you are actually doing.
So the functional parts of the change are just the couple of places where you added eFrameCompareUnknown handling that does an additional "pc" compare. Is that right? If so, that seems fine to me, though it would be much nicer if there were examples we could use to test this new behavior.

I actually like having the CompareTo rather than doing a bunch if if ==, then else if < then else. So that part seems good. But it's a little hard to grok the extent of this change.

lldb/source/Target/StackID.cpp

33

It would be easier to read this if the operator== were above CompareTo rather than below it. The first thing this function does is call the == comparator, so it would be nice to have that right next to where it's called.

It's seems a little odd at first to still have the == operator, you'd thing CompareTo should handle everything and then the == should just be lhs.CompareTo(rhs) == eFrameCompareEqual but the CompareTo computation does work that's not needed for ==, so actually that part is fine.

lldb/source/Target/ThreadPlanStepOut.cpp

513

"Current" is confusing, since in the context of frames we use it as part of "Currently Selected Frame" most often, which this is not treating. This has also become a somewhat obscure function, so it definitely needs some comment saying why this computation does what the function name says it does.

lldb/source/Target/ThreadPlanStepRange.cpp

219

This doesn't seem like a good use of auto. In an IDE it's nice to be able to do "Jump to definition" to see the options here, which is harder to do with auto than with the actual type.

[jingham]

It might also be good to document that CompareTo doesn't try to calculate, and will never return eFrameCompareSameParent. A StackID can't do that because it doesn't really know how to unwind from itself, so that's a pretty sensible restriction, but it makes it easier to reason about all the places where CompareTo is called and SameParent isn't handled.

lldb/include/lldb/Target/StackID.h

const StackID &operator=(const StackID &rhs) {
     if (this != &rhs) {
       m_pc = rhs.m_pc;
       m_cfa = rhs.m_cfa;
       m_symbol_scope = rhs.m_symbol_scope;
     }
     return *this;
   }
 
+lldb::FrameComparison CompareTo(const StackID &rhs) const;
+
 protected:
   friend class StackFrame;
 
   void SetPC(lldb::addr_t pc) { m_pc = pc; }
 
   void SetCFA(lldb::addr_t cfa) { m_cfa = cfa; }
 
   lldb::addr_t m_pc =
SymbolContextScope *m_symbol_scope =
                // pointers since the are part of the Block and Symbol
                // objects and can easily be used to tell if a stack ID
                // is the same as another.
 };
 
 bool operator==(const StackID &lhs, const StackID &rhs);
 bool operator!=(const StackID &lhs, const StackID &rhs);
 
-// frame_id_1 < frame_id_2 means "frame_id_1 is YOUNGER than frame_id_2"
-bool operator<(const StackID &lhs, const StackID &rhs);
-
 } // namespace lldb_private
 
 #endif // LLDB_TARGET_STACKID_H

lldb/include/lldb/Target/ThreadPlanStepOut.h

friend lldb::ThreadPlanSP Thread::QueueThreadPlanForStepOut(
       LazyBool step_out_avoids_code_without_debug_info);
 
   void SetupAvoidNoDebug(LazyBool step_out_avoids_code_without_debug_info);
   // Need an appropriate marker for the current stack so we can tell step out
   // from step in.
 
   void CalculateReturnValue();
 
+  bool DoesCurrentFrameExplainStop();
+
   ThreadPlanStepOut(const ThreadPlanStepOut &) = delete;
   const ThreadPlanStepOut &operator=(const ThreadPlanStepOut &) = delete;
 };
 
 } // namespace lldb_private
 
 #endif // LLDB_TARGET_THREADPLANSTEPOUT_H

lldb/source/Target/StackFrameList.cpp

if (frame_sp->GetFrameIndex() == unwind_idx)
       break;
     frame_sp = GetFrameAtIndex(++frame_idx);
   }
   return frame_sp;
 }
 
 static bool CompareStackID(const StackFrameSP &stack_sp,
                            const StackID &stack_id) {
-  return stack_sp->GetStackID() < stack_id;
+  return stack_sp->GetStackID().CompareTo(stack_id) == eFrameCompareYounger;
 }
 
 StackFrameSP StackFrameList::GetFrameWithStackID(const StackID &stack_id) {
   StackFrameSP frame_sp;
 
   if (stack_id.IsValid()) {
     std::lock_guard<std::recursive_mutex> guard(m_mutex);
     uint32_t frame_idx = 0;

lldb/source/Target/StackID.cpp

if (m_symbol_scope) {
     if (sc.block)
       s->Printf(" (Block {0x%8.8" PRIx64 "})", sc.block->GetID());
     else if (sc.symbol)
       s->Printf(" (Symbol{0x%8.8x})", sc.symbol->GetID());
   }
   s->PutCString(") ");
 }
 
-bool lldb_private::operator==(const StackID &lhs, const StackID &rhs) {
-  if (lhs.GetCallFrameAddress() != rhs.GetCallFrameAddress())
-    return false;
-
-  SymbolContextScope *lhs_scope = lhs.GetSymbolContextScope();
-  SymbolContextScope *rhs_scope = rhs.GetSymbolContextScope();
-
-  // Only compare the PC values if both symbol context scopes are nullptr
-  if (lhs_scope == nullptr && rhs_scope == nullptr)
-    return lhs.GetPC() == rhs.GetPC();
-
-  return lhs_scope == rhs_scope;
-}
-
-bool lldb_private::operator!=(const StackID &lhs, const StackID &rhs) {
-  if (lhs.GetCallFrameAddress() != rhs.GetCallFrameAddress())
-    return true;
-
-  SymbolContextScope *lhs_scope = lhs.GetSymbolContextScope();
-  SymbolContextScope *rhs_scope = rhs.GetSymbolContextScope();
-
-  if (lhs_scope == nullptr && rhs_scope == nullptr)
-    return lhs.GetPC() != rhs.GetPC();
+lldb::FrameComparison StackID::CompareTo(const StackID &rhs) const {
+  if (*this == rhs)
+    return lldb::eFrameCompareEqual;
 
-  return lhs_scope != rhs_scope;
-}
-
-bool lldb_private::operator<(const StackID &lhs, const StackID &rhs) {
-  const lldb::addr_t lhs_cfa = lhs.GetCallFrameAddress();
   const lldb::addr_t rhs_cfa = rhs.GetCallFrameAddress();
 
   // FIXME: We are assuming that the stacks grow downward in memory.  That's not
   // necessary, but true on
   // all the machines we care about at present.  If this changes, we'll have to
   // deal with that.  The ABI is the agent who knows this ordering, but the
   // StackID has no access to the ABI. The most straightforward way to handle
   // this is to add a "m_grows_downward" bool to the StackID, and set it in the
   // constructor. But I'm not going to waste a bool per StackID on this till we
   // need it.
 
-  if (lhs_cfa != rhs_cfa)
-    return lhs_cfa < rhs_cfa;
+  if (m_cfa != rhs_cfa)
+    return m_cfa < rhs_cfa ? lldb::eFrameCompareYounger
+                           : lldb::eFrameCompareOlder;
 
-  SymbolContextScope *lhs_scope = lhs.GetSymbolContextScope();
   SymbolContextScope *rhs_scope = rhs.GetSymbolContextScope();
 
-  if (lhs_scope != nullptr && rhs_scope != nullptr) {
-    // Same exact scope, lhs is not less than (younger than rhs)
-    if (lhs_scope == rhs_scope)
-      return false;
+  if (m_symbol_scope != nullptr && rhs_scope != nullptr) {
+    // Same CFA and same exact scope, StackIDs are equal.
+    if (m_symbol_scope == rhs_scope)
+      return lldb::eFrameCompareEqual;
 
     SymbolContext lhs_sc;
     SymbolContext rhs_sc;
-    lhs_scope->CalculateSymbolContext(&lhs_sc);
+    m_symbol_scope->CalculateSymbolContext(&lhs_sc);
     rhs_scope->CalculateSymbolContext(&rhs_sc);
 
     // Items with the same function can only be compared
     if (lhs_sc.function == rhs_sc.function && lhs_sc.function != nullptr &&
         lhs_sc.block != nullptr && rhs_sc.function != nullptr &&
         rhs_sc.block != nullptr) {
-      return rhs_sc.block->Contains(lhs_sc.block);
-    }
-  }
+      if (rhs_sc.block->Contains(lhs_sc.block))
+        return lldb::eFrameCompareYounger;
+
+      if (lhs_sc.block->Contains(rhs_sc.block))
+        return lldb::eFrameCompareOlder;
+    }
+
+  return lldb::eFrameCompareUnknown;
+
+bool lldb_private::operator==(const StackID &lhs, const StackID &rhs) {
+  if (lhs.GetCallFrameAddress() != rhs.GetCallFrameAddress())
     return false;
+
+  SymbolContextScope *lhs_scope = lhs.GetSymbolContextScope();
+  SymbolContextScope *rhs_scope = rhs.GetSymbolContextScope();
+
+  // Only compare the PC values if both symbol context scopes are nullptr
+  if (lhs_scope == nullptr && rhs_scope == nullptr)
+    return lhs.GetPC() == rhs.GetPC();
+
+  return lhs_scope == rhs_scope;
+}
+
+bool lldb_private::operator!=(const StackID &lhs, const StackID &rhs) {
+  if (lhs.GetCallFrameAddress() != rhs.GetCallFrameAddress())
+    return true;
+
+  SymbolContextScope *lhs_scope = lhs.GetSymbolContextScope();
+  SymbolContextScope *rhs_scope = rhs.GetSymbolContextScope();
+
+  if (lhs_scope == nullptr && rhs_scope == nullptr)
+    return lhs.GetPC() != rhs.GetPC();
+
+  return lhs_scope != rhs_scope;
 }

lldb/source/Target/ThreadPlanStepInstruction.cpp

bool ThreadPlanStepInstruction::DoPlanExplainsStop(Event *event_ptr) {
   }
   return false;
 }
 
 bool ThreadPlanStepInstruction::IsPlanStale() {
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
   Thread &thread = GetThread();
   StackID cur_frame_id = thread.GetStackFrameAtIndex(0)->GetStackID();
-  if (cur_frame_id == m_stack_id) {
+  FrameComparison frame_order = cur_frame_id.CompareTo(m_stack_id);
+
+  if (frame_order == eFrameCompareEqual) {
     // Set plan Complete when we reach next instruction
     uint64_t pc = thread.GetRegisterContext()->GetPC(0);
     uint32_t max_opcode_size =
         GetTarget().GetArchitecture().GetMaximumOpcodeByteSize();
     bool next_instruction_reached = (pc > m_instruction_addr) &&
         (pc <= m_instruction_addr + max_opcode_size);
     if (next_instruction_reached) {
       SetPlanComplete();
     }
-    return (thread.GetRegisterContext()->GetPC(0) != m_instruction_addr);
-  } else if (cur_frame_id < m_stack_id) {
+    return (pc != m_instruction_addr);
+  } else if (frame_order == eFrameCompareYounger) {
     // If the current frame is younger than the start frame and we are stepping
     // over, then we need to continue, but if we are doing just one step, we're
     // done.
     return !m_step_over;
-  } else {
+  } else if (frame_order == eFrameCompareOlder) {
     if (log) {
       LLDB_LOGF(log,
                 "ThreadPlanStepInstruction::IsPlanStale - Current frame is "
                 "older than start frame, plan is stale.");
     }
     return true;
+  } else {
+    if (log)
+      LLDB_LOGF(log,
+                "ThreadPlanStepInstruction::IsPlanStale - Failed to compare "
+                "current frame to the start frame, rely on PC comparison.");
+
+    return (thread.GetRegisterContext()->GetPC(0) != m_instruction_addr);
   }
 }
 
 bool ThreadPlanStepInstruction::ShouldStop(Event *event_ptr) {
   Thread &thread = GetThread();
   if (m_step_over) {
     Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
     StackFrameSP cur_frame_sp = thread.GetStackFrameAtIndex(0);
     if (!cur_frame_sp) {
       LLDB_LOGF(
           log,
           "ThreadPlanStepInstruction couldn't get the 0th frame, stopping.");
       SetPlanComplete();
       return true;
     }
 
     StackID cur_frame_zero_id = cur_frame_sp->GetStackID();
 
-    if (cur_frame_zero_id == m_stack_id || m_stack_id < cur_frame_zero_id) {
+    FrameComparison frame_order = m_stack_id.CompareTo(cur_frame_zero_id);
+
+    if (frame_order == eFrameCompareEqual || frame_order == eFrameCompareYounger) {
       if (thread.GetRegisterContext()->GetPC(0) != m_instruction_addr) {
         if (--m_iteration_count <= 0) {
           SetPlanComplete();
           return true;
         } else {
           // We are still stepping, reset the start pc, and in case we've
           // stepped out, reset the current stack id.
           SetUpState();
           return false;
         }
       } else
         return false;
-    } else {
+    } else if (frame_order == eFrameCompareOlder) {
       // We've stepped in, step back out again:
       StackFrame *return_frame = thread.GetStackFrameAtIndex(1).get();
       if (return_frame) {
         if (return_frame->GetStackID() != m_parent_frame_id ||
             m_start_has_symbol) {
           // next-instruction shouldn't step out of inlined functions.  But we
           // may have stepped into a real function that starts with an inlined
           // function, and we do want to step out of that...
if (frame_order == eFrameCompareEqual || frame_order == eFrameCompareYounger) {
           SetPlanComplete();
           return true;
         }
       } else {
         LLDB_LOGF(log, "Could not find previous frame, stopping.");
         SetPlanComplete();
         return true;
       }
+    } else {
+      LLDB_LOGF(log, "Could not compare frame IDs, stopping.");
+      SetPlanComplete();
+      return true;
     }
   } else {
     lldb::addr_t pc_addr = thread.GetRegisterContext()->GetPC(0);
     if (pc_addr != m_instruction_addr) {
       if (--m_iteration_count <= 0) {
         SetPlanComplete();
         return true;
       } else {

lldb/source/Target/ThreadPlanStepOut.cpp

bool ThreadPlanStepOut::DoPlanExplainsStop(Event *event_ptr) {
   if (stop_info_sp) {
     StopReason reason = stop_info_sp->GetStopReason();
     if (reason == eStopReasonBreakpoint) {
       // If this is OUR breakpoint, we're fine, otherwise we don't know why
       // this happened...
       BreakpointSiteSP site_sp(
           m_process.GetBreakpointSiteList().FindByID(stop_info_sp->GetValue()));
       if (site_sp && site_sp->IsBreakpointAtThisSite(m_return_bp_id)) {
-        bool done;
-
-        StackID frame_zero_id =
-            GetThread().GetStackFrameAtIndex(0)->GetStackID();
-
-        if (m_step_out_to_id == frame_zero_id)
-          done = true;
-        else if (m_step_out_to_id < frame_zero_id) {
-          // Either we stepped past the breakpoint, or the stack ID calculation
-          // was incorrect and we should probably stop.
-          done = true;
-        } else {
-          done = (m_immediate_step_from_id < frame_zero_id);
-        }
-
-        if (done) {
+        if (DoesCurrentFrameExplainStop()) {
           if (InvokeShouldStopHereCallback(eFrameCompareOlder, m_status)) {
             CalculateReturnValue();
             SetPlanComplete();
           }
         }
 
         // If there was only one owner, then we're done.  But if we also hit
         // some user breakpoint on our way out, we should mark ourselves as
else
       return m_step_through_inline_plan_sp->ShouldStop(event_ptr);
   } else if (m_step_out_further_plan_sp) {
     if (m_step_out_further_plan_sp->MischiefManaged())
       m_step_out_further_plan_sp.reset();
     else
       return m_step_out_further_plan_sp->ShouldStop(event_ptr);
   }
 
-  if (!done) {
-    StackID frame_zero_id = GetThread().GetStackFrameAtIndex(0)->GetStackID();
-    done = !(frame_zero_id < m_step_out_to_id);
-  }
+  if (!done)
+    done = DoesCurrentFrameExplainStop();
 
   // The normal step out computations think we are done, so all we need to do
   // is consult the ShouldStopHere, and we are done.
 
   if (done) {
     if (InvokeShouldStopHereCallback(eFrameCompareOlder, m_status)) {
       CalculateReturnValue();
       SetPlanComplete();
void ThreadPlanStepOut::CalculateReturnValue() {
   }
 }
 
 bool ThreadPlanStepOut::IsPlanStale() {
   // If we are still lower on the stack than the frame we are returning to,
   // then there's something for us to do.  Otherwise, we're stale.
 
   StackID frame_zero_id = GetThread().GetStackFrameAtIndex(0)->GetStackID();
-  return !(frame_zero_id < m_step_out_to_id);
+  return frame_zero_id.CompareTo(m_step_out_to_id) != eFrameCompareYounger;
+}
+
+bool ThreadPlanStepOut::DoesCurrentFrameExplainStop() {
+  StackID frame_zero_id = GetThread().GetStackFrameAtIndex(0)->GetStackID();
+
+  auto comparison_result = m_step_out_to_id.CompareTo(frame_zero_id);
+
+  if (comparison_result == eFrameCompareYounger ||
+      comparison_result == eFrameCompareEqual)
+    return true;
+
+  if (comparison_result == eFrameCompareOlder)
+    return false;
+
+  // We can reach this point if frame_zero_id and m_step_out_to_id have the same
+  // CFA but belong to different functions.
+
+  if (m_immediate_step_from_id.CompareTo(frame_zero_id) == eFrameCompareYounger)
+    return true;
+
+  return m_return_addr == frame_zero_id.GetPC();
 }

lldb/source/Target/ThreadPlanStepRange.cpp

 // FIXME: This should also handle inlining if we aren't going to do inlining in
 // the
 // main stack.
 //
 // Ideally we should remember the whole stack frame list, and then compare that
 // to the current list.
 
 lldb::FrameComparison ThreadPlanStepRange::CompareCurrentFrameToStartFrame() {
-  FrameComparison frame_order;
   Thread &thread = GetThread();
   StackID cur_frame_id = thread.GetStackFrameAtIndex(0)->GetStackID();
 
-  if (cur_frame_id == m_stack_id) {
-    frame_order = eFrameCompareEqual;
-  } else if (cur_frame_id < m_stack_id) {
-    frame_order = eFrameCompareYounger;
-  } else {
-    StackFrameSP cur_parent_frame = thread.GetStackFrameAtIndex(1);
-    StackID cur_parent_id;
-    if (cur_parent_frame)
-      cur_parent_id = cur_parent_frame->GetStackID();
+  auto frame_order = cur_frame_id.CompareTo(m_stack_id);
+  if (frame_order != eFrameCompareUnknown)
+    return frame_order;
+
+  if (cur_parent_frame) {
+    StackID cur_parent_id = cur_parent_frame->GetStackID();
     if (m_parent_stack_id.IsValid() && cur_parent_id.IsValid() &&
         m_parent_stack_id == cur_parent_id)
       frame_order = eFrameCompareSameParent;
-    else
-      frame_order = eFrameCompareOlder;
   }
+
   return frame_order;
 }
 
 bool ThreadPlanStepRange::StopOthers() {
   switch (m_stop_others) {
   case lldb::eOnlyThisThread:
     return true;
   case lldb::eOnlyDuringStepping:

lldb/source/Target/ThreadPlanStepUntil.cpp

if (reason == eStopReasonBreakpoint) {
         // only breakpoint at that location, then we do explain the stop, and
         // we'll just continue. If there was another breakpoint here, then we
         // don't explain the stop, but we won't mark ourselves Completed,
         // because maybe that breakpoint will continue, and then we'll finish
         // the "until".
         bool done;
         StackID cur_frame_zero_id;
 
-        done = (m_stack_id < cur_frame_zero_id);
+        done = m_stack_id.CompareTo(cur_frame_zero_id) == eFrameCompareYounger;
 
         if (done) {
           m_stepped_out = true;
           SetPlanComplete();
         } else
           m_should_stop = false;
 
         if (this_site->GetNumberOfOwners() == 1)
           m_explains_stop = true;
         else
           m_explains_stop = false;
         return;
       } else {
         // Check if we've hit one of our "until" breakpoints.
         until_collection::iterator pos, end = m_until_points.end();
         for (pos = m_until_points.begin(); pos != end; pos++) {
           if (this_site->IsBreakpointAtThisSite((*pos).second)) {
             // If we're at the right stack depth, then we're done.
             Thread &thread = GetThread();
             bool done;
             StackID frame_zero_id =
                 thread.GetStackFrameAtIndex(0)->GetStackID();
 
-            if (frame_zero_id == m_stack_id)
+            auto frame_compare = frame_zero_id.CompareTo(m_stack_id);
+
+            if (frame_compare == eFrameCompareEqual)
               done = true;
-            else if (frame_zero_id < m_stack_id)
+            else if (frame_compare == eFrameCompareYounger)
               done = false;
-            else {
+            else if (frame_compare == eFrameCompareOlder) {
               StackFrameSP older_frame_sp = thread.GetStackFrameAtIndex(1);
 
               // But if we can't even unwind one frame we should just get out
               // of here & stop...
               if (older_frame_sp) {
                 const SymbolContext &older_context =
                     older_frame_sp->GetSymbolContext(eSymbolContextEverything);
                 SymbolContext stack_context;
                 m_stack_id.GetSymbolContextScope()->CalculateSymbolContext(
                     &stack_context);
 
                 done = (older_context == stack_context);
               } else
                 done = false;
-            }
+            } else
+              done = thread.GetRegisterContext()->GetPC(0) == m_return_addr;
 
             if (done)
               SetPlanComplete();
             else
               m_should_stop = false;
 
             // Otherwise we've hit this breakpoint recursively.  If we're the
             // only breakpoint here, then we do explain the stop, and we'll