[lldb] Fix (unintentional) recursion in CommandObjectRegexCommand

[JDevlieghere]

Summary

Jim noticed that the regex command is unintentionally recursive:

Let's use the following command regex as an example:

(lldb) com regex humm 's/([^ ]+) ([^ ]+)/p %1 %2 %1 %2/'

If we call it with arguments foo bar, thing behave as expected:

(lldb) humm foo bar
(...)
foo bar foo bar

However, if we include %2 in the arguments, things break down:

(lldb) humm fo%2o bar
(...)
fobaro bar fobaro bar

The problem is that the implementation of the substitution is too naive. It substitutes the %1 token into the target template in place, then does the %2 substitution starting with the resultant string. So if the previous substitution introduced a %2 token, it would get processed in the second sweep, etc.

This patch addresses the issue by walking the command once and substituting the % variables in place. I didn't really trust myself so I also wrote a few unit tests to make sure I didn't miss any edge cases.

(lldb) humm fo%2o bar
(...)
fo%2o bar fo%2o bar

rdar://81236994

[mib]

lldb/source/Commands/CommandObjectRegexCommand.cpp

40

Are we assuming that the number following % will always have a single digit ?

52

TIL but I think the exact formula is floor(log10(num))+2 according to this https://stackoverflow.com/questions/61707231/why-is-log-base-10-used-in-this-code-to-convert-int-to-string

I don't know if this formula has a name but if it does it would be great to add it as a comment above.

[JDevlieghere]

lldb/source/Commands/CommandObjectRegexCommand.cpp

40

Added a comment to make it clear that atoi will parse until it encounters a character that's not a digit.

52

The formula you linked is to compute the size in bytes for the number, not the string length. Take 1 for example: floor(log10(1)) + 2 = 0 + 2 = 2.

[clayborg]

lldb/source/Commands/CommandObjectRegexCommand.cpp

13

I cringe every time I see an old C header being imported as C++ because of the huge amounts of junk it causes the DWARF to incur with many import declarations inside the std namespace for any types that are defined... If we import <math.h> we don't end up with all that. We don't have to change it, but as you are aware dsymutil keeps every type that is defined in these header files because of this extra fluff in the DWARF.

41

We don't want negative numbers to succeed here. Might be better to use strtoul()

51

Update to use strtoul "end" parameter

[clayborg]

We also have StringExtractor that we could call StringExtractor::GetU32(...) on. We would need to add a new method like:

bool StringExtractor::SkipTo(char ch);

And then we could call StringExtractor::GetU32(..) if that returns true. The current string position only gets updated if the number extraction succeeds. This uses strtoul being the scenes:

uint32_t StringExtractor::GetU32(uint32_t fail_value, int base);

lldb/source/Commands/CommandObjectRegexCommand.cpp

13

If we end up using strtoul as mentioned below, then:
#include <stdlib.h>

[labath]

Wouldn't want to miss a good bikeshed. Logarithms are cool, but I think something like this (untested) snippet would be simpler

Input.split(Parts, '%');
Result << Parts[0];
for (llvm::StringRef Part : drop_begin(Parts)) {
  if (!Part.consumeInteger(10, Idx) && Idx < Replacements.size())
    Result << Replacements[Idx];
  else
    Result << '%';
  Result << Part;
}

[JDevlieghere]

Use Pavel's not-as-cool solution.

[clayborg]

lldb/source/Commands/CommandObjectRegexCommand.h

47

Do we want a "Expected<std::string>" as the result? If any index that follows a '%' 'that is 1 or higher could require the index be valid within "replacements" or we would return an error like "%4 is out of range, not enough arguments specified". Seems weird to just leave it in the resulting string as that is most certainly not what the user would expect? I might be what we used to do, but since we are improving things here, is seems like this would be easy to do

[clayborg]

lldb/source/Commands/CommandObjectRegexCommand.h

47

And also, do we really want to print "%0" if we have one in the string? Maybe an error for that as well?

[JDevlieghere]

• Allow using %0
• Return an error when using an out of range index

[mib]

LGTM !

lldb/include/lldb/Interpreter/CommandReturnObject.h

 #define LLDB_INTERPRETER_COMMANDRETURNOBJECT_H
 
 #include "lldb/Core/StreamFile.h"
 #include "lldb/Utility/StreamString.h"
 #include "lldb/Utility/StreamTee.h"
 #include "lldb/lldb-private.h"
 
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Error.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/WithColor.h"
 
 #include <memory>
 
 namespace lldb_private {
 
 class CommandReturnObject {
public:
 
   template <typename... Args>
   void AppendErrorWithFormatv(const char *format, Args &&... args) {
     AppendError(llvm::formatv(format, std::forward<Args>(args)...).str());
   }
 
   void SetError(const Status &error, const char *fallback_error_cstr = nullptr);
 
+  void SetError(llvm::Error error);
+
   lldb::ReturnStatus GetStatus() const;
 
   void SetStatus(lldb::ReturnStatus status);
 
   bool Succeeded() const;
 
   bool HasResult() const;
 

lldb/source/Commands/CommandObjectRegexCommand.h

public:
 
   bool HasRegexEntries() const { return !m_entries.empty(); }
 
   void HandleCompletion(CompletionRequest &request) override;
 
 protected:
   bool DoExecute(llvm::StringRef command, CommandReturnObject &result) override;
 
+  /// Substitute variables of the format %\d+ in the input string.
+  static llvm::Expected<std::string> SubstituteVariables(
+      llvm::StringRef input,
+      const llvm::SmallVectorImpl<llvm::StringRef> &replacements);
+
   struct Entry {
     RegularExpression regex;
     std::string command;
   };
 
   typedef std::list<Entry> EntryCollection;
   const uint32_t m_max_matches;
   const uint32_t m_completion_type_mask;
   EntryCollection m_entries;

lldb/source/Commands/CommandObjectRegexCommand.cpp

 //===-- CommandObjectRegexCommand.cpp -------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "CommandObjectRegexCommand.h"
 #include "lldb/Interpreter/CommandInterpreter.h"
 #include "lldb/Interpreter/CommandReturnObject.h"
 
+#include "llvm/Support/Errc.h"
+#include "llvm/Support/Error.h"
+
 using namespace lldb;
 using namespace lldb_private;
 
 // CommandObjectRegexCommand constructor
 CommandObjectRegexCommand::CommandObjectRegexCommand(
     CommandInterpreter &interpreter, llvm::StringRef name, llvm::StringRef help,
     llvm::StringRef syntax, uint32_t max_matches, uint32_t completion_type_mask,
     bool is_removable)
     : CommandObjectRaw(interpreter, name, help, syntax),
       m_max_matches(max_matches), m_completion_type_mask(completion_type_mask),
       m_is_removable(is_removable) {}
 
 // Destructor
 CommandObjectRegexCommand::~CommandObjectRegexCommand() = default;
 
+llvm::Expected<std::string> CommandObjectRegexCommand::SubstituteVariables(
+    llvm::StringRef input,
+    const llvm::SmallVectorImpl<llvm::StringRef> &replacements) {
+  std::string buffer;
+  llvm::raw_string_ostream output(buffer);
+
+  llvm::SmallVector<llvm::StringRef, 4> parts;
+  input.split(parts, '%');
+
+  output << parts[0];
+  for (llvm::StringRef part : drop_begin(parts)) {
+    size_t idx = 0;
+    if (part.consumeInteger(10, idx))
+      output << '%';
+    else if (idx < replacements.size())
+      output << replacements[idx];
+    else
+      return llvm::make_error<llvm::StringError>(
+          llvm::formatv("%{0} is out of range: not enough arguments specified",
+                        idx),
+          llvm::errc::invalid_argument);
+    output << part;
+  }
+
+  return output.str();
+}
+
 bool CommandObjectRegexCommand::DoExecute(llvm::StringRef command,
                                           CommandReturnObject &result) {
   EntryCollection::const_iterator pos, end = m_entries.end();
   for (pos = m_entries.begin(); pos != end; ++pos) {
     llvm::SmallVector<llvm::StringRef, 4> matches;
     if (pos->regex.Execute(command, &matches)) {
-      std::string new_command(pos->command);
-      char percent_var[8];
-      size_t idx, percent_var_idx;
-      for (uint32_t match_idx = 1; match_idx <= m_max_matches; ++match_idx) {
-        if (match_idx < matches.size()) {
-          const std::string match_str = matches[match_idx].str();
-          const int percent_var_len =
-              ::snprintf(percent_var, sizeof(percent_var), "%%%u", match_idx);
-          for (idx = 0; (percent_var_idx = new_command.find(
-                             percent_var, idx)) != std::string::npos;) {
-            new_command.erase(percent_var_idx, percent_var_len);
-            new_command.insert(percent_var_idx, match_str);
-            idx = percent_var_idx + match_str.size();
-          }
-        }
+      llvm::Expected<std::string> new_command =
+          SubstituteVariables(pos->command, matches);
+      if (!new_command) {
+        result.SetError(new_command.takeError());
+        return false;
       }
+
       // Interpret the new command and return this as the result!
       if (m_interpreter.GetExpandRegexAliases())
-        result.GetOutputStream().Printf("%s\n", new_command.c_str());
+        result.GetOutputStream().Printf("%s\n", new_command->c_str());
       // Pass in true for "no context switching".  The command that called us
       // should have set up the context appropriately, we shouldn't have to
       // redo that.
-      return m_interpreter.HandleCommand(new_command.c_str(),
+      return m_interpreter.HandleCommand(new_command->c_str(),
                                          eLazyBoolCalculate, result);
     }
   }
   result.SetStatus(eReturnStatusFailed);
   if (!GetSyntax().empty())
     result.AppendError(GetSyntax());
   else
-    result.GetOutputStream() << "Command contents '" << command
-                             << "' failed to match any "
-                                "regular expression in the '"
-                             << m_cmd_name << "' regex ";
+    result.GetErrorStream() << "Command contents '" << command
   return false;
 }
 
 bool CommandObjectRegexCommand::AddRegexCommand(llvm::StringRef re_cstr,
                                                 llvm::StringRef command_cstr) {
   m_entries.resize(m_entries.size() + 1);
   // Only add the regular expression if it compiles
   m_entries.back().regex = RegularExpression(re_cstr);

lldb/source/Interpreter/CommandReturnObject.cpp

void CommandReturnObject::AppendError(llvm::StringRef in_string) {
   error(GetErrorStream()) << in_string.rtrim() << '\n';
 }
 
 void CommandReturnObject::SetError(const Status &error,
                                    const char *fallback_error_cstr) {
   AppendError(error.AsCString(fallback_error_cstr));
 }
 
+void CommandReturnObject::SetError(llvm::Error error) {
+  if (error)
+    AppendError(llvm::toString(std::move(error)));
+}
+
 // Similar to AppendError, but do not prepend 'Status: ' to message, and don't
 // append "\n" to the end of it.
 
 void CommandReturnObject::AppendRawError(llvm::StringRef in_string) {
   SetStatus(eReturnStatusFailed);
   assert(!in_string.empty() && "Expected a non-empty error message");
   GetErrorStream() << in_string;
 }

lldb/unittests/Interpreter/CMakeLists.txt

 add_lldb_unittest(InterpreterTests
   TestCommandPaths.cpp
   TestCompletion.cpp
   TestOptionArgParser.cpp
   TestOptionValue.cpp
   TestOptionValueFileColonLine.cpp
+  TestRegexCommand.cpp
 
   LINK_LIBS
       lldbCore
       lldbHost
       lldbTarget
       lldbSymbol
       lldbUtility
       lldbUtilityHelpers
       lldbInterpreter
       lldbPluginPlatformMacOSX
+      LLVMTestingSupport
 )

lldb/unittests/Interpreter/TestRegexCommand.cpp

+//===-- TestRegexCommand.cpp ----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "Commands/CommandObjectRegexCommand.h"
+#include "llvm/Testing/Support/Error.h"
+#include "gtest/gtest.h"
+
+using namespace lldb_private;
+using namespace lldb;
+
+namespace {
+class TestRegexCommand : public CommandObjectRegexCommand {
+public:
+  using CommandObjectRegexCommand::SubstituteVariables;
+
+  static std::string
+  Substitute(llvm::StringRef input,
+             const llvm::SmallVectorImpl<llvm::StringRef> &replacements) {
+    llvm::Expected<std::string> str = SubstituteVariables(input, replacements);
+    if (!str)
+      return llvm::toString(str.takeError());
+    return *str;
+  }
+};
+} // namespace
+
+TEST(RegexCommandTest, SubstituteVariablesSuccess) {
+  const llvm::SmallVector<llvm::StringRef, 4> substitutions = {"all", "foo",
+                                                               "bar", "baz"};
+
+  EXPECT_EQ(TestRegexCommand::Substitute("%0", substitutions), "all");
+  EXPECT_EQ(TestRegexCommand::Substitute("%1", substitutions), "foo");
+  EXPECT_EQ(TestRegexCommand::Substitute("%2", substitutions), "bar");
+  EXPECT_EQ(TestRegexCommand::Substitute("%3", substitutions), "baz");
+  EXPECT_EQ(TestRegexCommand::Substitute("%1%2%3", substitutions), "foobarbaz");
+  EXPECT_EQ(TestRegexCommand::Substitute("#%1#%2#%3#", substitutions),
+            "#foo#bar#baz#");
+}
+
+TEST(RegexCommandTest, SubstituteVariablesFailed) {
+  const llvm::SmallVector<llvm::StringRef, 4> substitutions = {"all", "foo",
+                                                               "bar", "baz"};
+
+  ASSERT_THAT_EXPECTED(
+      TestRegexCommand::SubstituteVariables("%1%2%3%4", substitutions),
+      llvm::Failed());
+  ASSERT_THAT_EXPECTED(
+      TestRegexCommand::SubstituteVariables("%5", substitutions),
+      llvm::Failed());
+  ASSERT_THAT_EXPECTED(
+      TestRegexCommand::SubstituteVariables("%11", substitutions),
+      llvm::Failed());
+}
+
+TEST(RegexCommandTest, SubstituteVariablesNoRecursion) {
+  const llvm::SmallVector<llvm::StringRef, 4> substitutions = {"all", "%2",
+                                                               "%3", "%4"};
+  EXPECT_EQ(TestRegexCommand::Substitute("%0", substitutions), "all");
+  EXPECT_EQ(TestRegexCommand::Substitute("%1", substitutions), "%2");
+  EXPECT_EQ(TestRegexCommand::Substitute("%2", substitutions), "%3");
+  EXPECT_EQ(TestRegexCommand::Substitute("%3", substitutions), "%4");
+  EXPECT_EQ(TestRegexCommand::Substitute("%1%2%3", substitutions), "%2%3%4");
+}