2/2: Process formatters in reverse-chronological order

[jankratochvil]

Summary

If one reverts D66398 then the TestDataFormatterStdList does fail - as the C++ formatters are initialized in the opposite order. But the current state of trunk does not mind the order for C++ formatters.

[JDevlieghere]

I understand one could pass some better abstracted error-reporting interface instead of ValueObject itself but that would require some more code (interface definition, inheritance etc.).

How much work would it be to return an llvm::Expected<bool> from Get_Impl? I'd really prefer that over the current approach.

lldb/include/lldb/Core/ValueObject.h

459 ↗

(On Diff #216847)

This allows overwriting the error without checking if it's already set. Maybe it's better to use GetError, check that it's not set, and then either set it or append to it?

lldb/include/lldb/DataFormatters/FormattersContainer.h

296 ↗

(On Diff #216847)

If returning an expected isn't feasible, we should pass at least a Status* instead of setting the error in the ValueObject directly.

lldb/source/DataFormatters/TypeCategory.cpp

303 ↗

(On Diff #216847)

It's really unfortunate that so many call sites now require a null pointer. Can we make it a default argument?

[granata.enrico]

I'm not working on LLDB anymore. Sorry about that.

[jankratochvil]

In D66654#1643082, @JDevlieghere wrote:

How much work would it be to return an llvm::Expected<bool> from Get_Impl? I'd really prefer that over the current approach.

Done. Although now if (Get(...)) became confusing which I have commented in lldb_private::FormatDropExpected().

BTW I haven't found how to format a table for Doxygen. Also by searching around I have found other tables in LLDB/LLVM are also not recognized by Doxygen as tables.

lldb/include/lldb/DataFormatters/FormattersContainer.h

296 ↗

(On Diff #216847)

With Expected<bool> this is no longer applicable.

lldb/source/DataFormatters/TypeCategory.cpp

303 ↗

(On Diff #216847)

With Expected<bool> this is no longer applicable.

[jankratochvil]

Testcase for the regex sanity check is failing - ValueObject::m_error remains set even after type summary clear. ValueObject::UpdateValueIfNeeded will find did_change_formats==true but it does not help it. I think there is some bug in ValueObject updating but maybe that setting of ValueObject::m_error is a wrong idea.

runCmd: type summary clear
output:

runCmd: type summary add --summary-string "${var[0-1]}" -x "int \[[0-9]\]"
output:

runCmd: frame variable int_array
output: (int [5]) int_array = [-1,2]


Expecting sub string: 1,2
Matched

runCmd: type summary add --summary-string "${var[0-1]}" "int []"
output:

runCmd: frame variable int_array
output: (int [5]) int_array = <Two regexes ("int \[[0-9]+\]" and "int \[[0-9]\]") ambiguously match the same string "int [5]".>

Expecting pattern: int_array = <Two regexes \(("int\ \\\[\[0\-9\]\\\]" and "int\ \\\[\[0\-9\]\+\\\]"|"int\ \\\[\[0\-9\]\+\\\]" and "int\ \\\[\[0\-9\]\\\]")\) ambiguously match the same string "int\ \[5\]".>
Matched

runCmd: type summary clear
output:

runCmd: type summary add --summary-string "${var[0-1]}" "int []"
output:

runCmd: frame variable int_array
output: (int [5]) int_array = <Two regexes ("int \[[0-9]+\]" and "int \[[0-9]\]") ambiguously match the same string "int [5]".>

Expecting sub string: 1,2
Not matched

FAIL

[labath]

+ @jingham for value object stuff

Though I agree with the general principle of this change, the new api which implements it seems extremely confusing. Unfortunately, it's not really clear to me how to improve that. Maybe it would be better if the Get methods returned Expected<lldb::TypeFormatImplSP>? Then an "error" would mean ambiguous match, valid pointer would be "ok", and a null pointer would be "no match"? Or maybe both "no match" and "ambiguous match" should be errors? Or maybe, since these objects claim to be containers, they shouldn't even treat multiple matches as an error, but instead provide an interface to get *all* matches, and then this can be converted to an error higher up?

lldb/include/lldb/Core/ValueObject.h

460 ↗

(On Diff #217079)

I didn't mention this in the previous patches, but I think you're overusing the rvalue references here. It's generally better to use regular value objects in cases like these because this enforces proper contracts between functions.

Using rvalue references leaves open the possibility for a bug (which you've actually made here) that the TakeError function will do nothing to the passed-in object (on some path of execution), which means that the object will continue to exist in the "untaken" state in the caller, and then probably assert some distance away from where it was meant to be used.

Passing the argument as a plain object means that this function *must* do something with it (really *take* it) or *it* will assert. The cost of that is a single object move, but that should generally be trivial for objects that implement moving properly.

lldb/include/lldb/DataFormatters/FormatClasses.h

176 ↗

(On Diff #217079)

std::string, please. :) ConstString is severely overused in lldb..

[clayborg]

What about having the first one that matched being the one that is used and avoid errors all together? We do this with the regex alias stuff already. With regular expressions people are sure to make ones that conflict with each other.

[jankratochvil]

In D66654#1645658, @clayborg wrote:

What about having the first one that matched being the one that is used and avoid errors all together?

This is how it worked so far before the fix D66398 (which made the regexes unambiguous - always matching at most 1 regex for any string). The previous version of the patch just sorted the regexes alphabetically because original LLDB did not sort them at all printing random results.

@labath did not like the alphabetical sorting as (IIUC) adding formatters from a new library can affect formatting for a different library.

We do this with the regex alias stuff already.

I haven't found the work alias in either grep -ri alias $(find -name DataFormatters) or in Variable Formatting doc.

With regular expressions people are sure to make ones that conflict with each other.

So which order to choose? It should not have different output during different runs of LLDB.

[labath]

In D66654#1645792, @jankratochvil wrote:

In D66654#1645658, @clayborg wrote:

What about having the first one that matched being the one that is used and avoid errors all together?

This is how it worked so far before the fix D66398 (which made the regexes unambiguous - always matching at most 1 regex for any string). The previous version of the patch just sorted the regexes alphabetically because original LLDB did not sort them at all printing random results.

@labath did not like the alphabetical sorting as (IIUC) adding formatters from a new library can affect formatting for a different library.

Kind of, yes. My concern was a bit more general, in that the alphabetical sorting just seems arbitrary and I don't believe anybody would expect that. It happens to do what we want here, but I can imagine that in some cases it might do the exact opposite, and then we'd have to massage the regular expressions to reverse their sort order, but retain meaning...

Personally, I'd go for the registration order, or possibly the reverse registration order, depending on what we want to give precedence to. It seems to me that this would give the most predictable results, and would make it easy to swap the precedence of two formatters if needed. But I don't feel strongly about that, so if you want to go with alphabetical, then I guess that's fine with me (it's definitely better than sorting on pointer values :P).

[jankratochvil]

lldb/include/lldb/Core/ValueObject.h

460 ↗

(On Diff #217079)

Thanks for this notification, I see I was automatically using the && parameter specifier excessively. rvalues still work properly with std::move() even without using this parameter specifier.
I also agree there was the bug with possibly untaken Error asserting later (I find that as an orthogonal bug to the && one).

[jankratochvil]

In D66654#1646544, @labath wrote:

Personally, I'd go for the registration order,

Then you cannot override any existing formatter. Then it would be better to rather assert/error in such case which I tried to do in this patch but nobody likes this patch much.

or possibly the reverse registration order,

That is what this new patch implements.

[labath]

Summarizing our discussion on IRC:
While I think that this version of the patch is definitely better than the previous ones, I still feel that the two container solution is unnecessarily complicated. I think using llvm::MapVector or even std::vector would be sufficient. While this may be optimal in terms of performance (not memory), I don't think that is really important in this case. The only place where the std::list solution is better than a std::vector is the removal of an arbitrary element in the list. However, I would stipulate that this is a very uncommon operation. The most common operations are lookup (which are linear in any case), and insertion (constant).

Therefore, I think we should optimize for readability/bug-freeness and choose the simplest solution.

[labath]

Hm... "summarizing" might not have been the best word here. I have "summarized" what *I* said over IRC, but I did not mean to imply that Jan agreed with my position (and he didn't, not yet anyway..)

[jankratochvil]

In D66654#1654713, @labath wrote:

The most common operations are lookup (which are linear in any case),

There are also lookups by name (GetExact) which are logarithmic now by that std::map.

I can try the MapVector. I just tried not to regress performance by using optimal data structures. If one was concerned about performance there can be done many other easy improvements of the existing code.

[jankratochvil]

I have tried the MapVector with RegularExpressionSP as its key as suggested by @labath but that would be even more code than the std::list I provided here, both for its custom shared-pointer sorting and for its EmptyKey+TombstoneKey if we should not put std::map there.
So I returned back to a single std::vector as originally suggested by @labath and after fixing missing Delete in the Add implementation for vector it I think that may be a good compromise from all the variants.

[labath]

I think this looks great. Some operations may get less efficient with this, but OTOH, some will get actually faster. And it is definitely the most understandable solution out of everything we had so far.

lldb/include/lldb/DataFormatters/FormattersContainer.h

83 ↗

(On Diff #219147)

m_map.emplace_back, maybe?

109 ↗

(On Diff #219147)

range-based for

130–134 ↗

(On Diff #219147)

lol

168 ↗

(On Diff #219147)

Is this still needed, or is that a leftover from the MapVector attempt?

291–292 ↗

(On Diff #219147)

consider: for(const auto &entry: llvm::reverse(m_format_map))

[jankratochvil]

lldb/include/lldb/DataFormatters/FormattersContainer.h

83 ↗

(On Diff #219147)

Yes, not sure why I forgot here.

109 ↗

(On Diff #219147)

OK, other existing loops updated in: rL371922

168 ↗

(On Diff #219147)

Still needed.

291–292 ↗

(On Diff #219147)

Nice, thanks, used.

[labath]

lgtm

lldb/trunk/include/lldb/DataFormatters/FormattersContainer.h

static inline ConstString GetValidTypeName_Impl(ConstString type) {
   return ConstString(type_lexer.GetUnlexed());
 }
 
 template <typename KeyType, typename ValueType> class FormattersContainer;
 
 template <typename KeyType, typename ValueType> class FormatMap {
 public:
   typedef typename ValueType::SharedPointer ValueSP;
-  typedef std::map<KeyType, ValueSP> MapType;
+  typedef std::vector<std::pair<KeyType, ValueSP>> MapType;
   typedef typename MapType::iterator MapIterator;
   typedef std::function<bool(const KeyType &, const ValueSP &)> ForEachCallback;
 
   FormatMap(IFormatChangeListener *lst)
       : m_map(), m_map_mutex(), listener(lst) {}
 
   void Add(KeyType name, const ValueSP &entry) {
     if (listener)
       entry->GetRevision() = listener->GetCurrentRevision();
     else
       entry->GetRevision() = 0;
 
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
-    m_map[std::move(name)] = entry;
+    Delete(name);
+    m_map.emplace_back(std::move(name), std::move(entry));
     if (listener)
       listener->Changed();
   }
 
   bool Delete(const KeyType &name) {
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
-    MapIterator iter = m_map.find(name);
-    if (iter == m_map.end())
-      return false;
+    for (MapIterator iter = m_map.begin(); iter != m_map.end(); ++iter)
+      if (iter->first == name) {
         m_map.erase(iter);
         if (listener)
           listener->Changed();
         return true;
       }
+    return false;
+  }
 
   void Clear() {
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
     m_map.clear();
     if (listener)
       listener->Changed();
   }
 
   bool Get(const KeyType &name, ValueSP &entry) {
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
-    MapIterator iter = m_map.find(name);
-    if (iter == m_map.end())
-      return false;
-    entry = iter->second;
+    for (const auto &pos : m_map)
+      if (pos.first == name) {
+        entry = pos.second;
         return true;
       }
+    return false;
+  }
 
   void ForEach(ForEachCallback callback) {
     if (callback) {
       std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
       for (const auto &pos : m_map) {
         const KeyType &type = pos.first;
         if (!callback(type, pos.second))
           break;
       }
     }
   }
 
   uint32_t GetCount() { return m_map.size(); }
 
   ValueSP GetValueAtIndex(size_t index) {
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
-    MapIterator iter = m_map.begin();
-    MapIterator end = m_map.end();
-    while (index > 0) {
-      iter++;
-      index--;
-      if (end == iter)
-        return ValueSP();
-    }
-    return iter->second;
+    if (index >= m_map.size())
+    return m_map[index].second;
   }
 
   // If caller holds the mutex we could return a reference without copy ctor.
   KeyType GetKeyAtIndex(size_t index) {
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
-    MapIterator iter = m_map.begin();
-    MapIterator end = m_map.end();
-    while (index > 0) {
-      iter++;
-      index--;
-      if (end == iter)
-        return KeyType();
-    }
-    return iter->first;
+    if (index >= m_map.size())
+      return {};
+    return m_map[index].first;
   }
 
 protected:
   MapType m_map;
   std::recursive_mutex m_map_mutex;
   IFormatChangeListener *listener;
 
   MapType &map() { return m_map; }
 
   std::recursive_mutex &mutex() { return m_map_mutex; }
 
   friend class FormattersContainer<KeyType, ValueType>;
   friend class FormatManager;
 };
 
 template <typename KeyType, typename ValueType> class FormattersContainer {
 protected:
   typedef FormatMap<KeyType, ValueType> BackEndType;
 
 public:
   typedef typename BackEndType::MapType MapType;
   typedef typename MapType::iterator MapIterator;
-  typedef typename MapType::key_type MapKeyType;
-  typedef typename MapType::mapped_type MapValueType;
+  typedef KeyType MapKeyType;
+  typedef std::shared_ptr<ValueType> MapValueType;
   typedef typename BackEndType::ForEachCallback ForEachCallback;
   typedef typename std::shared_ptr<FormattersContainer<KeyType, ValueType>>
       SharedPointer;
 
   friend class TypeCategoryImpl;
 
   FormattersContainer(std::string name, IFormatChangeListener *lst)
       : m_format_map(lst), m_name(name) {}
GetTypeNameSpecifierAtIndex_Impl(size_t index, RegularExpression *dummy) {
     return lldb::TypeNameSpecifierImplSP(
         new TypeNameSpecifierImpl(regex.GetText().str().c_str(), true));
   }
 
   bool Get_Impl(ConstString key, MapValueType &value,
                 RegularExpression *dummy) {
     llvm::StringRef key_str = key.GetStringRef();
     std::lock_guard<std::recursive_mutex> guard(m_format_map.mutex());
-    for (const auto &pos : m_format_map.map()) {
+    // Patterns are matched in reverse-chronological order.
+    for (const auto &pos : llvm::reverse(m_format_map.map())) {
       const RegularExpression &regex = pos.first;
       if (regex.Execute(key_str)) {
         value = pos.second;
         return true;
       }
     }
     return false;
   }

lldb/trunk/include/lldb/Utility/RegularExpression.h

public:
 
   /// Return an error if the regular expression failed to compile.
   ///
   /// \return
   ///     A string error if the regular expression failed to compile, success
   ///     otherwise.
   llvm::Error GetError() const;
 
-  bool operator<(const RegularExpression &rhs) const {
-    return GetText() < rhs.GetText();
-  }
-
   bool operator==(const RegularExpression &rhs) const {
     return GetText() == rhs.GetText();
   }
 
 private:
   /// A copy of the original regular expression text.
   std::string m_regex_text;
   /// The compiled regular expression.
   mutable llvm::Regex m_regex;
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_RegularExpression_h_

lldb/trunk/packages/Python/lldbsuite/test/functionalities/data-formatter/data-formatter-advanced/TestDataFormatterAdv.py

def test_with_run_command(self):
                     substrs=['1,2'])
 
         self.runCmd(
             'type summary add --summary-string \"${var[0-1]}\" "int []"')
 
         self.expect("frame variable int_array",
                     substrs=['1,2'])
 
+        # Test the patterns are matched in reverse-chronological order.
+        self.runCmd(
+            'type summary add --summary-string \"${var[2-3]}\" "int []"')
+
+        self.expect("frame variable int_array",
+                    substrs=['3,4'])
+
         self.runCmd("type summary clear")
 
         self.runCmd("type summary add -c -x \"i_am_cool \[[0-9]\]\"")
         self.runCmd("type summary add -c i_am_cool")
 
         self.expect("frame variable cool_array",
                     substrs=['[0]',
                              '[1]',