[obj2yaml] - Better indentations in the ELF output.

[grimar]

Summary

The current obj2yaml's output has an issue: it places
a lot of an excessive indentation spaces between keys and values.
Then we have to remove them manually to improve the readability of
test cases. I see such requests from reviewers regularly around
and it is not ideal.

The issue happens because Output::paddedKey has a trivial logic which
hardcodes the maximum of spaces used to align the values column:

const char *spaces = "                ";
if (key.size() < strlen(spaces))
  Padding = &spaces[key.size()];

I've experimented with a ways to improve this situation and
seems finally found the solution, though it is not that simple
as I've hoped when started.

The main problem is that until we performed a mapping of
fields, we know nothing about their names and hence
can't use this information to tweak the indentations on the fly.
At the same time we write the output during doing the mapping,
so it is too late to do something on this step.

So. In this patch I've introduced a "pre-mapping" pass. This is a
cheap "mapping" that is done right before the real mapping.
This pass only scans the keys which are on the current level of the output
and finds the maximum key length. This information is then used
to calculate and print a better indentation during the real mapping pass.

Given that the approach is not that simple, I'd like to discuss before
doing additional polishing. Perhaps the main question is: do we want
such complexity to improve indentations?

[grimar]

It is rebased on top of D73046.

[grimar]

llvm/test/tools/obj2yaml/elf-output-indentation.yaml

19

Here the additional indentation appears because of AddressAlign, which is
the largest key among others. The same situation is shown below.
I did not investigate how much hard to to improve such places too yet.

[jhenderson]

I'll give this a more thorough look at some point hopefully, but my instinct is the current situation is the worst of the three cases "good padding"/"excessive padding"/"no padding". I think a little bit of code complexity would be okay to improve the excessive padding situation. I'm not sure instinctively whether this is too much however. I'll give it some thought.

llvm/test/tools/obj2yaml/elf-output-indentation.yaml

19

I definitely find it weird that .text is not indented to the same extend as .data.

20–24

I'm guessing this block is indented because of Relocations? This doesn't seem great, given that the Reloctions line doesn't have a direct value itself.

[MaskRay]

I agree that a preflight pass is unavoidable if we want to improve indentation. This patch does not seem to bring much complexity, so I am in favor of such a change. I'll need to dive deeply into the logic.

[grimar]

In D73045#1829853, @MaskRay wrote:

I agree that a preflight pass is unavoidable if we want to improve indentation.

There was one more way I though about.
For each type handler, like:

void MappingTraits<ELFYAML::Object>::mapping(IO &IO, ELFYAML::Object &Object) {
...
  IO.mapTag("!ELF", true);
  IO.mapRequired("FileHeader", Object.Header);
  IO.mapOptional("ProgramHeaders", Object.ProgramHeaders);
  IO.mapOptional("Sections", Object.Chunks);
  IO.mapOptional("Symbols", Object.Symbols);
  IO.mapOptional("DynamicSymbols", Object.DynamicSymbols);
....
}

We could calculate the indentation in its code, like:
(pseudocode)

void MappingTraits<ELFYAML::Object>::mapping(IO &IO, ELFYAML::Object &Object) {
  int MaxKey = sizeof("FileHeader") or sizeof("ProgramHeaders") if exist and not empty or ...;
  IO.setMaxPadding(MaxKey);
...
  IO.mapTag("!ELF", true);
  IO.mapRequired("FileHeader", Object.Header);

It could give a nice results, it is simple and does not require pre-mapping, but
it is not a generic approach, that is why I supposed it is not an option.

llvm/test/tools/obj2yaml/elf-output-indentation.yaml

19

Yes, though it just follows the simple rule: "find the largest key size and align others".
I am not sure what can be a good generic heuristic without knowing the context.

20–24

Yeah, but the problem here is that preflightKey which is used to scan keys:

bool preflightKey(const char *Key, bool Required, bool SameAsDefault, bool &,
                   void *&) override {
   if (Required || !SameAsDefault)
     MaxKeyLen = std::max(MaxKeyLen, strlen(Key));
   return false;
 }

does not have any information about values (how to know that Relocations is an empty list?)
Accessing to the values never happens,
because of return false, which prevents any more logic from execution.
I.e. The code only scans over keys on the current level and does not allow going deeper.
If it did than much more logic would be needed to be implemented for this "pre-mapping" pass.

The solutions I see are: either adopting the code in yaml::Output to teach it about possibility of "pre-mapping"
(the idea of this patch was to avoid touching Output code, I've only fixed a minor misbehaviors in processKeyWithDefault)
and/or implementing a smarter (and larger) PreMappingOutput class.

[jhenderson]

Okay, I'm happy with the concept, and I don't think it's too complex, but I do think my inline comments about the formatting for lists (members, and also other keys in the list owner) need resolving for this to be properly worthwhile.

llvm/include/llvm/Support/YAMLTraits.h

1133

Some doxygen-style comments on this and the other new functions and classes are needed.

1139

Should this be a size_t? Negative padding doesn't make much sense...

1206

MaxPaddingsStack -> MaxPaddingStack

1217

This seems like a weird way of structuring the code. A PreMappingOutput is a subclass of Output, but that means it also contains a unique pointer to itself? That seems like a recipe for destruction order issues.

llvm/lib/Support/YAMLTraits.cpp

833

Why not just StringRef Spaces = " ";?

836

My immediate thought here was "what if the key is longer than the spaces". I imagine it's handled, but it's not obvious.

838

clang-format?

llvm/test/tools/obj2yaml/elf-output-indentation.yaml

19

Is it not possible to iterate over all list elements to find their individual required padding sizes, and then set them all to the max of the list members?

20–24

I'm not really an expert in how all this code fits together, so I don't know what's possible. However, I do think that indenting a value like this looks bad, and will regularly leave us with extra spurious spaces again. Is it possible to tell what kind of mapping keys are (e.g. lists versus strings/numbers) at all? I do think some extra smarts to solve this would be wise if needed.

[grimar]

I'll continue D74611 which is alternative.

llvm/include/llvm/Support/YAMLTraits.h

void processKeyWithDefault(const char *Key, Optional<T> &Val,
     if (!outputting() && !Val.hasValue())
       Val = T();
     if (Val.hasValue() &&
         this->preflightKey(Key, Required, sameAsDefault, UseDefault,
                            SaveInfo)) {
       yamlize(*this, Val.getValue(), Required, Ctx);
       this->postflightKey(SaveInfo);
     } else {
-      if (UseDefault)
+      if (!outputting() && UseDefault)
         Val = DefaultValue;
     }
   }
 
   template <typename T, typename Context>
   void processKeyWithDefault(const char *Key, T &Val, const T &DefaultValue,
                              bool Required, Context &Ctx) {
     void *SaveInfo;
     bool UseDefault;
     const bool sameAsDefault = outputting() && Val == DefaultValue;
     if ( this->preflightKey(Key, Required, sameAsDefault, UseDefault,
                                                                   SaveInfo) ) {
       yamlize(*this, Val, Required, Ctx);
       this->postflightKey(SaveInfo);
     }
     else {
-      if ( UseDefault )
+      if (!outputting() && UseDefault)
         Val = DefaultValue;
     }
   }
 
   template <typename T, typename Context>
   void processKey(const char *Key, T &Val, bool Required, Context &Ctx) {
     void *SaveInfo;
     bool UseDefault;
private:
   std::error_code EC;
   BumpPtrAllocator StringAllocator;
   document_iterator DocIterator;
   std::vector<bool> BitValuesUsed;
   HNode *CurrentNode = nullptr;
   bool ScalarMatchFound = false;
 };
 
+class PreMappingOutput;
+
 ///
 /// The Output class is used to generate a yaml document from in-memory structs
 /// and vectors.
 ///
 class Output : public IO {
 public:
   Output(raw_ostream &, void *Ctxt = nullptr, int WrapColumn = 70);
+  Output(Output& Parent);
   ~Output() override;
 
   /// Set whether or not to output optional values which are equal
   /// to the default value.  By default, when outputting if you attempt
   /// to write a value that is equal to the default, the value gets ignored.
   /// Sometimes, it is useful to be able to see these in the resulting YAML
   /// anyway.
   void setWriteDefaultValues(bool Write) { WriteDefaultValues = Write; }
 
+  void setOptimizeIndentations(bool Optimize);
+
+  IO *getPreMappingOutput() const;
+
+  void endPremapping();
+
+  void setMaxPadding(int Val) { MaxPadding = Val; }
+
   bool outputting() const override;
   bool mapTag(StringRef, bool) override;
   void beginMapping() override;
   void endMapping() override;
   bool preflightKey(const char *key, bool, bool, bool &, void *&) override;
   void postflightKey(void *) override;
   std::vector<StringRef> keys() override;
   void beginFlowMapping() override;
private:
   static bool inSeqAnyElement(InState State);
   static bool inFlowSeqAnyElement(InState State);
   static bool inMapAnyKey(InState State);
   static bool inFlowMapAnyKey(InState State);
 
   raw_ostream &Out;
   int WrapColumn;
   SmallVector<InState, 8> StateStack;
+  SmallVector<int, 8> MaxPaddingsStack;
   int Column = 0;
   int ColumnAtFlowStart = 0;
   int ColumnAtMapFlowStart = 0;
   bool NeedBitValueComma = false;
   bool NeedFlowSequenceComma = false;
   bool EnumerationMatchFound = false;
   bool WriteDefaultValues = false;
+  int MaxPadding = -1;
   StringRef Padding;
   StringRef PaddingBeforeContainer;
+  std::unique_ptr<PreMappingOutput> PreMappingOut;
+};
+
+class PreMappingOutput final : public Output {
+  Output &Parent;
+  size_t MaxKeyLen;
+
+public:
+  PreMappingOutput(Output &O) : Output(O), Parent(O), MaxKeyLen(0) {}
+
+  bool preflightKey(const char *Key, bool Required, bool SameAsDefault, bool &,
+                    void *&) override {
+    if (Required || !SameAsDefault)
+      MaxKeyLen = std::max(MaxKeyLen, strlen(Key));
+    return false;
+  }
+
+  void endPremapping() {
+    Parent.setMaxPadding(MaxKeyLen + 1);
+    MaxKeyLen = 0;
+  }
 };
 
 namespace detail {
 
 template <typename T, typename Context>
 void doMapping(IO &io, T &Val, Context &Ctx) {
   MappingContextTraits<T, Context>::mapping(io, Val, Ctx);
 }
 
+template <typename T> void doPreMapping(IO &InOut, T &Val, EmptyContext &Ctx) {
+  if (!InOut.outputting())
+    return;
+
+  Output &Out = (Output &)InOut;
+  if (IO *O = Out.getPreMappingOutput())
+    MappingTraits<T>::mapping(*O, Val);
+  Out.endPremapping();
+}
+
 template <typename T> void doMapping(IO &io, T &Val, EmptyContext &Ctx) {
+  doPreMapping(io, Val, Ctx);
   MappingTraits<T>::mapping(io, Val);
 }
 
 } // end namespace detail
 
 template <typename T>
 typename std::enable_if<has_ScalarEnumerationTraits<T>::value, void>::type
 yamlize(IO &io, T &Val, bool, EmptyContext &Ctx) {

llvm/lib/ObjectYAML/ELFYAML.cpp

if (Object->Header.Machine == ELFYAML::ELF_EM(ELF::EM_MIPS) &&
     IO.mapRequired("Type", Rel.Type);
 
   IO.mapOptional("Addend", Rel.Addend, (int64_t)0);
 }
 
 void MappingTraits<ELFYAML::Object>::mapping(IO &IO, ELFYAML::Object &Object) {
   assert(!IO.getContext() && "The IO context is initialized already");
   IO.setContext(&Object);
+  if (IO.outputting())
+    ((Output &)IO).setOptimizeIndentations(true);
+
   IO.mapTag("!ELF", true);
   IO.mapRequired("FileHeader", Object.Header);
   IO.mapOptional("ProgramHeaders", Object.ProgramHeaders);
   IO.mapOptional("Sections", Object.Chunks);
   IO.mapOptional("Symbols", Object.Symbols);
   IO.mapOptional("DynamicSymbols", Object.DynamicSymbols);
+
+  if (IO.outputting())
+    ((Output &)IO).setOptimizeIndentations(false);
   IO.setContext(nullptr);
 }
 
 void MappingTraits<ELFYAML::AddrsigSymbol>::mapping(IO &IO, ELFYAML::AddrsigSymbol &Sym) {
   assert(IO.getContext() && "The IO context is not initialized");
   IO.mapOptional("Name", Sym.Name);
   IO.mapOptional("Index", Sym.Index);
 }

llvm/lib/Support/YAMLTraits.cpp

 
 //===----------------------------------------------------------------------===//
 //  Output
 //===----------------------------------------------------------------------===//
 
 Output::Output(raw_ostream &yout, void *context, int WrapColumn)
     : IO(context), Out(yout), WrapColumn(WrapColumn) {}
 
+Output::Output(Output &Parent) : IO(Parent.getContext()), Out(Parent.Out) {}
+
 Output::~Output() = default;
 
 bool Output::outputting() const {
   return true;
 }
 
 void Output::beginMapping() {
   StateStack.push_back(inMapFirstKey);
   PaddingBeforeContainer = Padding;
   Padding = "\n";
+
+  if (PreMappingOut)
+    MaxPaddingsStack.push_back(MaxPadding);
+}
+
+void Output::setOptimizeIndentations(bool Optimize) {
+  assert((Optimize && !PreMappingOut) || (!Optimize && PreMappingOut));
+  if (Optimize)
+    PreMappingOut = std::make_unique<PreMappingOutput>(*this);
+  else
+    PreMappingOut.reset();
 }
 
+void Output::endPremapping() {
+  if (PreMappingOut)
+    PreMappingOut->endPremapping();
+}
+
+IO *Output::getPreMappingOutput() const { return PreMappingOut.get(); }
+
 bool Output::mapTag(StringRef Tag, bool Use) {
   if (Use) {
     // If this tag is being written inside a sequence we should write the start
     // of the sequence before writing the tag, otherwise the tag won't be
     // attached to the element in the sequence, but rather the sequence itself.
     bool SequenceElement = false;
     if (StateStack.size() > 1) {
       auto &E = StateStack[StateStack.size() - 2];
void Output::endMapping() {
   // If we did not map anything, we should explicitly emit an empty map
   if (StateStack.back() == inMapFirstKey) {
     Padding = PaddingBeforeContainer;
     newLineCheck();
     output("{}");
     Padding = "\n";
   }
   StateStack.pop_back();
+
+  if (PreMappingOut)
+    MaxPadding = MaxPaddingsStack.pop_back_val();
 }
 
 std::vector<StringRef> Output::keys() {
   report_fatal_error("invalid call");
 }
 
 bool Output::preflightKey(const char *Key, bool Required, bool SameAsDefault,
                           bool &UseDefault, void *&) {
if (OutputDash) {
     output("- ");
   }
 
 }
 
 void Output::paddedKey(StringRef key) {
   output(key);
   output(":");
-  const char *spaces = "                ";
-  if (key.size() < strlen(spaces))
-    Padding = &spaces[key.size()];
+
+  static std::string Spaces(16, ' ');
+  int PaddingLen;
+  if (MaxPadding == -1)
+    PaddingLen = std::max<int>(Spaces.size() - key.size(), 1);
   else
-    Padding = " ";
+    PaddingLen = std::min<int>(std::max<int>(MaxPadding - key.size(), 1), Spaces.size());
+  Padding = StringRef(Spaces).take_front(PaddingLen);
 }
 
 void Output::flowKey(StringRef Key) {
   if (StateStack.back() == inFlowMapOtherKey)
     output(", ");
   if (WrapColumn && Column > WrapColumn) {
     output("\n");
     for (int I = 0; I < ColumnAtMapFlowStart; ++I)

llvm/test/tools/obj2yaml/elf-output-indentation.yaml

+## obj2yaml tries to optimize indentations between keys and
+## values to make an output nicer.
+## In this test we demonstrate the output produced.
+
+# RUN: yaml2obj %s -o %t
+# RUN: obj2yaml %t | FileCheck %s --strict-whitespace --match-full-lines
+
+#      CHECK:--- !ELF
+# CHECK-NEXT:FileHeader:
+# CHECK-NEXT:  Class:   ELFCLASS64
+# CHECK-NEXT:  Data:    ELFDATA2LSB
+# CHECK-NEXT:  Type:    ET_REL
+# CHECK-NEXT:  Machine: EM_X86_64
+# CHECK-NEXT:Sections:
+# CHECK-NEXT:  - Name: .text
+# CHECK-NEXT:    Type: SHT_PROGBITS
+# CHECK-NEXT:  - Name:         .data
+# CHECK-NEXT:    Type:         SHT_PROGBITS
+# CHECK-NEXT:    AddressAlign: 0x0000000000000001
+# CHECK-NEXT:  - Name:        .rela.text
+# CHECK-NEXT:    Type:        SHT_RELA
+# CHECK-NEXT:    Link:        .symtab
+# CHECK-NEXT:    EntSize:     0x0000000000000018
+# CHECK-NEXT:    Info:        .text
+# CHECK-NEXT:    Relocations:
+# CHECK-NEXT:      - Offset: 0x0000000000000000
+# CHECK-NEXT:        Type:   R_X86_64_PC32
+# CHECK-NEXT:  - Name:    .rela.text2
+# CHECK-NEXT:    Type:    SHT_RELA
+# CHECK-NEXT:    Link:    .symtab
+# CHECK-NEXT:    EntSize: 0x0000000000000018
+# CHECK-NEXT:Symbols: []
+# CHECK-NEXT:DynamicSymbols:
+# CHECK-NEXT:  - Name:    dynamic
+# CHECK-NEXT:    Binding: STB_GLOBAL
+# CHECK-NEXT:    Value:   0x0000000012345678
+# CHECK-NEXT:  - Name:  both
+# CHECK-NEXT:    Value: 0x0000000087654321
+# CHECK-NEXT:...
+
+## Use an arbitrary YAML with different fields.
+
+--- !ELF
+FileHeader:
+  Class:   ELFCLASS64
+  Data:    ELFDATA2LSB
+  Type:    ET_REL
+  Machine: EM_X86_64
+Sections:
+  - Name: .text
+    Type: SHT_PROGBITS
+  - Name: .data
+    Type: SHT_PROGBITS
+    AddressAlign: 0x1
+  - Name:    .rela.text
+    Type:    SHT_RELA
+    Link:    .symtab
+    EntSize: 0x0000000000000018
+    Info:    .text
+    Relocations:
+      - Offset: 0x0000000000000000
+        Type:   R_X86_64_PC32
+  - Name:    .rela.text2
+    Type:    SHT_RELA
+    Link:    .symtab
+    EntSize: 0x0000000000000018
+    Relocations: []
+ProgramHeaders:
+  - Type:  PT_LOAD
+    VAddr: 0x100
+    Sections:
+      - Section: .text
+Symbols: []
+DynamicSymbols:
+  - Name:    dynamic
+    Binding: STB_GLOBAL
+    Value:   0x0000000012345678
+  - Name:  both
+    Value: 0x0000000087654321

llvm/tools/obj2yaml/elf2yaml.cpp

 static Error elf2yaml(raw_ostream &Out, const object::ELFFile<ELFT> &Obj) {
   ELFDumper<ELFT> Dumper(Obj);
   Expected<ELFYAML::Object *> YAMLOrErr = Dumper.dump();
   if (!YAMLOrErr)
     return YAMLOrErr.takeError();
 
   std::unique_ptr<ELFYAML::Object> YAML(YAMLOrErr.get());
   yaml::Output Yout(Out);
+  Yout.setMaxPadding(1);
   Yout << *YAML;
 
   return Error::success();
 }
 
 Error elf2yaml(raw_ostream &Out, const object::ObjectFile &Obj) {
   if (const auto *ELFObj = dyn_cast<object::ELF32LEObjectFile>(&Obj))
     return elf2yaml(Out, *ELFObj->getELFFile());