[vcpkg format-manifest] Add convert-control flag (#12471)

* [vcpkg format-manifest] initial convert-control attempt

TODO: manifest comments! we should keep $directives

* Finalize x-format-manifest

First, fix Json::parse -- "\c", for any c, was incorrectly parsed.
It would emit the escaped character, and then parse the character, so
that `\b` would give you { '\b', 'b' }.

Second, canonicalize source paragraphs as we're parsing them. This found
an error in qt5 -- The `declarative` feature was listed twice, and we
now catch it, so I removed the second paragraph.

Add PlatformExpression::complexity to allow ordering platform
expressions in a somewhat reasonable way.

Notes:
  - We allow `all_modules` as a feature name for back-compat with
    paraview
  - In order to actually convert CONTROL to vcpkg.json, we'd need to
    rename the qt5 `default` feature.
  - We need to add support for $directives in x-format-manifest

* fix qt5 port

* format

* fix compile

* fix tests for canonicalization

* Clean up code

* add error message for nothing to format

* add extra_info field

* add `const X&` overloads for `Object::insert[_or_replace]`

* fix compile

* simple CRs

* add tests

* format

* Fix mosquitto port file

also unmerge a line

* fail the tests on malformed manifest

* fix format_all

* fix coroutine port-version

* format manifests

6 files changed, 84 insertions, 13 deletions

diff --git a/toolsrc/include/vcpkg/base/json.h b/toolsrc/include/vcpkg/base/json.h
index 3195c223a..b7adde38f 100644
--- a/toolsrc/include/vcpkg/base/json.h
+++ b/toolsrc/include/vcpkg/base/json.h
@@ -88,11 +88,11 @@ namespace vcpkg::Json
     {
         Value() noexcept; // equivalent to Value::null()
         Value(Value&&) noexcept;
+        Value(const Value&);
         Value& operator=(Value&&) noexcept;
+        Value& operator=(const Value&);
         ~Value();
 
-        Value clone() const noexcept;
-
         ValueKind kind() const noexcept;
 
         bool is_null() const noexcept;
@@ -124,7 +124,12 @@ namespace vcpkg::Json
         static Value number(double d) noexcept;
         static Value string(StringView) noexcept;
         static Value array(Array&&) noexcept;
+        static Value array(const Array&) noexcept;
         static Value object(Object&&) noexcept;
+        static Value object(const Object&) noexcept;
+
+        friend bool operator==(const Value& lhs, const Value& rhs);
+        friend bool operator!=(const Value& lhs, const Value& rhs) { return !(lhs == rhs); }
 
     private:
         friend struct impl::ValueImpl;
@@ -138,14 +143,12 @@ namespace vcpkg::Json
 
     public:
         Array() = default;
-        Array(Array const&) = delete;
+        Array(Array const&) = default;
         Array(Array&&) = default;
-        Array& operator=(Array const&) = delete;
+        Array& operator=(Array const&) = default;
         Array& operator=(Array&&) = default;
         ~Array() = default;
 
-        Array clone() const noexcept;
-
         using iterator = underlying_t::iterator;
         using const_iterator = underlying_t::const_iterator;
 
@@ -177,37 +180,45 @@ namespace vcpkg::Json
         const_iterator cbegin() const { return underlying_.cbegin(); }
         const_iterator cend() const { return underlying_.cend(); }
 
+        friend bool operator==(const Array& lhs, const Array& rhs);
+        friend bool operator!=(const Array& lhs, const Array& rhs) { return !(lhs == rhs); }
+
     private:
         underlying_t underlying_;
     };
     struct Object
     {
     private:
-        using underlying_t = std::vector<std::pair<std::string, Value>>;
+        using value_type = std::pair<std::string, Value>;
+        using underlying_t = std::vector<value_type>;
 
         underlying_t::const_iterator internal_find_key(StringView key) const noexcept;
 
     public:
         // these are here for better diagnostics
         Object() = default;
-        Object(Object const&) = delete;
+        Object(Object const&) = default;
         Object(Object&&) = default;
-        Object& operator=(Object const&) = delete;
+        Object& operator=(Object const&) = default;
         Object& operator=(Object&&) = default;
         ~Object() = default;
 
-        Object clone() const noexcept;
-
         // asserts if the key is found
         Value& insert(std::string key, Value&& value);
+        Value& insert(std::string key, const Value& value);
         Object& insert(std::string key, Object&& value);
+        Object& insert(std::string key, const Object& value);
         Array& insert(std::string key, Array&& value);
+        Array& insert(std::string key, const Array& value);
 
         // replaces the value if the key is found, otherwise inserts a new
         // value.
         Value& insert_or_replace(std::string key, Value&& value);
+        Value& insert_or_replace(std::string key, const Value& value);
         Object& insert_or_replace(std::string key, Object&& value);
+        Object& insert_or_replace(std::string key, const Object& value);
         Array& insert_or_replace(std::string key, Array&& value);
+        Array& insert_or_replace(std::string key, const Array& value);
 
         // returns whether the key existed
         bool remove(StringView key) noexcept;
@@ -231,8 +242,12 @@ namespace vcpkg::Json
 
         bool contains(StringView key) const noexcept { return this->get(key); }
 
+        bool is_empty() const noexcept { return size() == 0; }
         std::size_t size() const noexcept { return this->underlying_.size(); }
 
+        // sorts keys alphabetically
+        void sort_keys();
+
         struct const_iterator
         {
             using value_type = std::pair<StringView, const Value&>;
@@ -267,6 +282,9 @@ namespace vcpkg::Json
         const_iterator cbegin() const noexcept { return const_iterator{this->underlying_.begin()}; }
         const_iterator cend() const noexcept { return const_iterator{this->underlying_.end()}; }
 
+        friend bool operator==(const Object& lhs, const Object& rhs);
+        friend bool operator!=(const Object& lhs, const Object& rhs) { return !(lhs == rhs); }
+
     private:
         underlying_t underlying_;
     };
diff --git a/toolsrc/include/vcpkg/base/strings.h b/toolsrc/include/vcpkg/base/strings.h
index cd4838029..5042dd158 100644
--- a/toolsrc/include/vcpkg/base/strings.h
+++ b/toolsrc/include/vcpkg/base/strings.h
@@ -185,6 +185,8 @@ namespace vcpkg::Strings
 
     std::string trim(std::string&& s);
 
+    StringView trim(StringView sv);
+
     void trim_all_and_remove_whitespace_strings(std::vector<std::string>* strings);
 
     std::vector<std::string> split(StringView s, const char delimiter);
diff --git a/toolsrc/include/vcpkg/base/stringview.h b/toolsrc/include/vcpkg/base/stringview.h
index 6a5503e1c..4f39e9103 100644
--- a/toolsrc/include/vcpkg/base/stringview.h
+++ b/toolsrc/include/vcpkg/base/stringview.h
@@ -37,6 +37,9 @@ namespace vcpkg
         constexpr const char* begin() const { return m_ptr; }
         constexpr const char* end() const { return m_ptr + m_size; }
 
+        constexpr std::reverse_iterator<const char*> rbegin() const { return std::make_reverse_iterator(end()); }
+        constexpr std::reverse_iterator<const char*> rend() const { return std::make_reverse_iterator(begin()); }
+
         constexpr const char* data() const { return m_ptr; }
         constexpr size_t size() const { return m_size; }
 
diff --git a/toolsrc/include/vcpkg/packagespec.h b/toolsrc/include/vcpkg/packagespec.h
index e23aa924e..7601127d5 100644
--- a/toolsrc/include/vcpkg/packagespec.h
+++ b/toolsrc/include/vcpkg/packagespec.h
@@ -1,6 +1,7 @@
 #pragma once
 
 #include <vcpkg/base/expected.h>
+#include <vcpkg/base/json.h>
 #include <vcpkg/base/optional.h>
 
 #include <vcpkg/platform-expression.h>
@@ -130,6 +131,11 @@ namespace vcpkg
         std::string name;
         std::vector<std::string> features;
         PlatformExpression::Expr platform;
+
+        Json::Object extra_info;
+
+        friend bool operator==(const Dependency& lhs, const Dependency& rhs);
+        friend bool operator!=(const Dependency& lhs, const Dependency& rhs) { return !(lhs == rhs); }
     };
 
     struct ParsedQualifiedSpecifier
@@ -146,7 +152,7 @@ namespace vcpkg
     Optional<ParsedQualifiedSpecifier> parse_qualified_specifier(Parse::ParserBase& parser);
 
     bool operator==(const PackageSpec& left, const PackageSpec& right);
-    bool operator!=(const PackageSpec& left, const PackageSpec& right);
+    inline bool operator!=(const PackageSpec& left, const PackageSpec& right) { return !(left == right); }
 }
 
 namespace std
diff --git a/toolsrc/include/vcpkg/platform-expression.h b/toolsrc/include/vcpkg/platform-expression.h
index fd2bb8589..43ae6e89d 100644
--- a/toolsrc/include/vcpkg/platform-expression.h
+++ b/toolsrc/include/vcpkg/platform-expression.h
@@ -38,6 +38,31 @@ namespace vcpkg::PlatformExpression
         bool evaluate(const Context& context) const;
         bool is_empty() const { return !static_cast<bool>(underlying_); }
 
+        // returns:
+        //   - 0 for empty
+        //   - 1 for identifiers
+        //   - 1 + complexity(inner) for !
+        //   - 1 + sum(complexity(inner)) for & and |
+        int complexity() const;
+
+        // these two are friends so that they're only findable via ADL
+
+        // this does a structural equality, so, for example:
+        //   !structurally_equal((x & y) & z, x & y & z)
+        //   !structurally_equal((x & y) | z, (x | z) & (y | z))
+        // even though these expressions are equivalent
+        friend bool structurally_equal(const Expr& lhs, const Expr& rhs);
+
+        // returns 0 if and only if structurally_equal(lhs, rhs)
+        // Orders via the following:
+        //   - If complexity(a) < complexity(b) => a < b
+        //   - Otherwise, if to_string(a).size() < to_string(b).size() => a < b
+        //   - Otherwise, if to_string(a) < to_string(b) => a < b
+        //   - else, they must be structurally equal
+        friend int compare(const Expr& lhs, const Expr& rhs);
+
+        friend std::string to_string(const Expr& expr);
+
     private:
         std::unique_ptr<detail::ExprImpl> underlying_;
     };
diff --git a/toolsrc/include/vcpkg/sourceparagraph.h b/toolsrc/include/vcpkg/sourceparagraph.h
index b2743645c..2ce4c7bca 100644
--- a/toolsrc/include/vcpkg/sourceparagraph.h
+++ b/toolsrc/include/vcpkg/sourceparagraph.h
@@ -40,6 +40,11 @@ namespace vcpkg
         std::string name;
         std::vector<std::string> description;
         std::vector<Dependency> dependencies;
+
+        Json::Object extra_info;
+
+        friend bool operator==(const FeatureParagraph& lhs, const FeatureParagraph& rhs);
+        friend bool operator!=(const FeatureParagraph& lhs, const FeatureParagraph& rhs) { return !(lhs == rhs); }
     };
 
     /// <summary>
@@ -60,6 +65,11 @@ namespace vcpkg
 
         Type type;
         PlatformExpression::Expr supports_expression;
+
+        Json::Object extra_info;
+
+        friend bool operator==(const SourceParagraph& lhs, const SourceParagraph& rhs);
+        friend bool operator!=(const SourceParagraph& lhs, const SourceParagraph& rhs) { return !(lhs == rhs); }
     };
 
     /// <summary>
@@ -73,7 +83,7 @@ namespace vcpkg
         {
             for (const auto& feat_ptr : scf.feature_paragraphs)
             {
-                feature_paragraphs.emplace_back(std::make_unique<FeatureParagraph>(*feat_ptr));
+                feature_paragraphs.push_back(std::make_unique<FeatureParagraph>(*feat_ptr));
             }
         }
 
@@ -89,8 +99,14 @@ namespace vcpkg
 
         Optional<const FeatureParagraph&> find_feature(const std::string& featurename) const;
         Optional<const std::vector<Dependency>&> find_dependencies_for_feature(const std::string& featurename) const;
+
+        friend bool operator==(const SourceControlFile& lhs, const SourceControlFile& rhs);
+        friend bool operator!=(const SourceControlFile& lhs, const SourceControlFile& rhs) { return !(lhs == rhs); }
     };
 
+    Json::Object serialize_manifest(const SourceControlFile& scf);
+    Json::Object serialize_debug_manifest(const SourceControlFile& scf);
+
     /// <summary>
     /// Full metadata of a package: core and other features. As well as the location the SourceControlFile was
     /// loaded from.
@@ -117,6 +133,7 @@ namespace vcpkg
         fs::path source_location;
     };
 
+    std::string get_error_message(Span<const std::unique_ptr<Parse::ParseControlErrorInfo>> error_info_list);
     void print_error_message(Span<const std::unique_ptr<Parse::ParseControlErrorInfo>> error_info_list);
     inline void print_error_message(const std::unique_ptr<Parse::ParseControlErrorInfo>& error_info_list)
     {