improve logic expression evaluation (#7508)

* better logic expression evaluation

Improve the logic expression evaluation currently used when filtering
dependencies.

Biggest improvements:
+  Allow '|' operator
+  Support nested '()'
+  Allow whitespace
+  Useful error message for malformed expressions

Also changed names of types to RawParagraph when that is what the original author was using.

10 files changed, 326 insertions, 54 deletions

diff --git a/toolsrc/src/vcpkg/binaryparagraph.cpp b/toolsrc/src/vcpkg/binaryparagraph.cpp
index 4b80debab..8b1886098 100644
--- a/toolsrc/src/vcpkg/binaryparagraph.cpp
+++ b/toolsrc/src/vcpkg/binaryparagraph.cpp
@@ -27,7 +27,7 @@ namespace vcpkg
 
     BinaryParagraph::BinaryParagraph() = default;
 
-    BinaryParagraph::BinaryParagraph(std::unordered_map<std::string, std::string> fields)
+    BinaryParagraph::BinaryParagraph(Parse::RawParagraph fields)
     {
         using namespace vcpkg::Parse;
 
diff --git a/toolsrc/src/vcpkg/build.cpp b/toolsrc/src/vcpkg/build.cpp
index 235adb819..54a691454 100644
--- a/toolsrc/src/vcpkg/build.cpp
+++ b/toolsrc/src/vcpkg/build.cpp
@@ -938,7 +938,7 @@ namespace vcpkg::Build
                                Commands::Version::version());

     }

 

-    static BuildInfo inner_create_buildinfo(std::unordered_map<std::string, std::string> pgh)

+    static BuildInfo inner_create_buildinfo(Parse::RawParagraph pgh)

     {

         Parse::ParagraphParser parser(std::move(pgh));

 

@@ -995,7 +995,7 @@ namespace vcpkg::Build
 

     BuildInfo read_build_info(const Files::Filesystem& fs, const fs::path& filepath)

     {

-        const Expected<std::unordered_map<std::string, std::string>> pghs =

+        const Expected<Parse::RawParagraph> pghs =

             Paragraphs::get_single_paragraph(fs, filepath);

         Checks::check_exit(VCPKG_LINE_INFO, pghs.get() != nullptr, "Invalid BUILD_INFO file for package");

         return inner_create_buildinfo(*pghs.get());

diff --git a/toolsrc/src/vcpkg/commands.cache.cpp b/toolsrc/src/vcpkg/commands.cache.cpp
index c321de3b5..4c49db004 100644
--- a/toolsrc/src/vcpkg/commands.cache.cpp
+++ b/toolsrc/src/vcpkg/commands.cache.cpp
@@ -14,7 +14,7 @@ namespace vcpkg::Commands::Cache
         std::vector<BinaryParagraph> output;
         for (auto&& path : paths.get_filesystem().get_files_non_recursive(paths.packages))
         {
-            const Expected<std::unordered_map<std::string, std::string>> pghs =
+            const Expected<Parse::RawParagraph> pghs =
                 Paragraphs::get_single_paragraph(paths.get_filesystem(), path / "CONTROL");
             if (const auto p = pghs.get())
             {
diff --git a/toolsrc/src/vcpkg/commands.import.cpp b/toolsrc/src/vcpkg/commands.import.cpp
index 40f5a434c..c18d788c5 100644
--- a/toolsrc/src/vcpkg/commands.import.cpp
+++ b/toolsrc/src/vcpkg/commands.import.cpp
@@ -108,7 +108,7 @@ namespace vcpkg::Commands::Import
         const fs::path include_directory(args.command_arguments[1]);
         const fs::path project_directory(args.command_arguments[2]);
 
-        const Expected<std::unordered_map<std::string, std::string>> pghs =
+        const Expected<Parse::RawParagraph> pghs =
             Paragraphs::get_single_paragraph(paths.get_filesystem(), control_file_path);
         Checks::check_exit(VCPKG_LINE_INFO,
                            pghs.get() != nullptr,
diff --git a/toolsrc/src/vcpkg/logicexpression.cpp b/toolsrc/src/vcpkg/logicexpression.cpp
new file mode 100644
index 000000000..fc8c4ef56
--- /dev/null
+++ b/toolsrc/src/vcpkg/logicexpression.cpp
@@ -0,0 +1,285 @@
+
+#include "pch.h"
+
+#include <vcpkg/logicexpression.h>
+#include <vcpkg/base/checks.h>
+#include <vcpkg/base/system.print.h>
+
+#include <string>
+#include <vector>
+
+
+namespace vcpkg
+{
+    struct ParseError
+    {
+        ParseError(int column, std::string line, std::string message)
+            :column(column), line(line), message(message)
+        {}
+
+        const int column;
+        const std::string line;
+        const std::string message;
+
+        void print_error() const
+        {
+            System::print2(System::Color::error,
+                "Error: ", message, "\n"
+                "   on expression: \"", line, "\"\n",
+                "                   ", std::string(column, ' '), "^\n");
+            Checks::exit_fail(VCPKG_LINE_INFO);
+        }
+    };
+
+    // logic expression supports the following :
+    //  primary-expression:
+    //    ( logic-expression )
+    //    identifier
+    //  identifier:
+    //    alpha-numeric string of characters   
+    //  logic-expression: <- this is the entry point
+    //    not-expression
+    //    not-expression | logic-expression
+    //    not-expression & logic-expression
+    //  not-expression:
+    //    ! primary-expression
+    //    primary-expression
+    //
+    // | and & have equal precidence and cannot be used together at the same nesting level
+    //   for example a|b&c is not allowd but (a|b)&c and a|(b&c) are allowed.
+    class ExpressionParser
+    {
+    public:
+        ExpressionParser(const std::string& str, const std::string& evaluation_context)
+            : raw_text(str), evaluation_context(evaluation_context)
+        {
+            go_to_begin();
+
+            final_result = logic_expression();
+
+            if (current_iter != raw_text.end())
+            {
+                add_error("Invalid logic expression");
+            }
+
+            if (err)
+            {
+                err->print_error();
+                final_result = false;
+            }
+        }
+
+        bool get_result() const
+        {
+            return final_result;
+        }
+
+        bool has_error() const
+        {
+            return err == nullptr;
+        }
+
+    private:
+
+        bool final_result;
+
+        std::string::const_iterator current_iter;
+        const std::string& raw_text;
+		char current_char;
+
+		const std::string& evaluation_context;
+
+		std::unique_ptr<ParseError> err;
+
+        void add_error(std::string message, int column = -1)
+        {
+            // avoid castcading errors by only saving the first
+            if (!err)
+            {
+                if (column < 0)
+                {
+                    column = current_column();
+                }
+                err = std::make_unique<ParseError>(column, raw_text, message);
+            }
+
+            // Avoid error loops by skipping to the end
+            skip_to_end();
+        }
+
+        int current_column() const
+        {
+            return static_cast<int>(current_iter - raw_text.begin());
+        }
+
+        void go_to_begin()
+        {
+            current_iter = raw_text.begin();
+            current_char = (current_iter != raw_text.end() ? *current_iter : current_char);
+
+            if (current_char == ' ' || current_char == '\t')
+            {
+                next_skip_whitespace();
+            }
+        }
+        void skip_to_end()
+        {
+            current_iter = raw_text.end();
+            current_char = '\0';
+        }
+        char current() const
+        {
+            return current_char;
+        }
+        char next()
+        {
+            if (current_char != '\0')
+            {
+                current_iter++;
+                current_char = (current_iter != raw_text.end() ? *current_iter : '\0');
+            }
+            return current();
+        }
+        void skip_whitespace()
+        {
+            while (current_char == ' ' || current_char == '\t')
+            {
+                current_char = next();
+            }
+        }
+        char next_skip_whitespace()
+        {
+            next();
+            skip_whitespace();
+            return current_char;
+        }
+
+        static bool is_alphanum(char ch)
+        {
+            return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9') || (ch == '-');
+        }
+
+        bool evaluate_identifier(const std::string name) const
+        {
+            return evaluation_context.find(name) != std::string::npos;
+        }
+
+        //  identifier:
+        //    alpha-numeric string of characters   
+        bool identifier_expression()
+        {
+            auto curr = current();
+            std::string name;
+
+            for (curr = current(); is_alphanum(curr); curr = next())
+            {
+                name += curr;
+            }
+
+            if (name.empty())
+            {
+                add_error("Invalid logic expression, unexpected character");
+                return false;
+            }
+            
+            bool result = evaluate_identifier(name);
+            skip_whitespace();
+            return result;
+        }
+
+        //  not-expression:
+        //    ! primary-expression
+        //    primary-expression
+        bool not_expression()
+        {
+            if (current() == '!')
+            {
+                next_skip_whitespace();
+                return !primary_expression();
+            }
+
+            return primary_expression();
+        }
+
+
+        template <char oper, char other, bool operation(bool, bool)>
+        bool logic_expression_helper(bool seed)
+        {
+            do
+            {
+                // Support chains of the operator to avoid breaking backwards compatability
+                while (next() == oper) {};
+                seed = operation(not_expression(), seed);
+
+            } while (current() == oper);
+
+            if (current() == other)
+            {
+                add_error("Mixing & and | is not allowed, Use () to specify order of operations.");
+            }
+
+			skip_whitespace();
+            return seed;
+        }
+		static bool and_helper(bool left, bool right)
+		{
+			return left && right;
+		}
+		static bool or_helper(bool left, bool right)
+		{
+			return left || right;
+		}
+
+        //  logic-expression: <- entry point
+        //    not-expression
+        //    not-expression | logic-expression
+        //    not-expression & logic-expression
+        bool logic_expression()
+        {
+            auto result = not_expression();
+
+            switch (current())
+            {
+            case '|':
+            {
+                return logic_expression_helper< '|', '&', or_helper > (result);
+            }
+            case '&':
+            {
+                return logic_expression_helper< '&', '|', and_helper > (result);
+            }
+            default:
+                return result;
+            }
+        }
+
+        //  primary-expression:
+        //    ( logic-expression )
+        //    identifier
+        bool primary_expression()
+        {
+            if (current() == '(')
+            {
+                next_skip_whitespace();
+                bool result = logic_expression();
+                if (current() != ')')
+                {
+                    add_error("Error: missing closing )");
+                    return result;
+                }
+                next_skip_whitespace();
+                return result;
+            }
+
+            return identifier_expression();
+        }
+    };
+
+
+    bool evaluate_expression(const std::string& expression, const std::string& evaluation_context)
+    {
+        ExpressionParser parser(expression, evaluation_context);
+
+        return parser.get_result();
+    }
+}
diff --git a/toolsrc/src/vcpkg/paragraphs.cpp b/toolsrc/src/vcpkg/paragraphs.cpp
index 21ef2c4d9..b08a6b805 100644
--- a/toolsrc/src/vcpkg/paragraphs.cpp
+++ b/toolsrc/src/vcpkg/paragraphs.cpp
@@ -116,7 +116,7 @@ namespace vcpkg::Paragraphs
             skip_spaces(ch);
         }
 
-        void get_paragraph(char& ch, std::unordered_map<std::string, std::string>& fields)
+        void get_paragraph(char& ch, RawParagraph& fields)
         {
             fields.clear();
             std::string fieldname;
@@ -141,9 +141,9 @@ namespace vcpkg::Paragraphs
         }
 
     public:
-        std::vector<std::unordered_map<std::string, std::string>> get_paragraphs()
+        std::vector<RawParagraph> get_paragraphs()
         {
-            std::vector<std::unordered_map<std::string, std::string>> paragraphs;
+            std::vector<RawParagraph> paragraphs;
 
             char ch;
             peek(ch);
@@ -164,7 +164,20 @@ namespace vcpkg::Paragraphs
         }
     };
 
-    Expected<std::unordered_map<std::string, std::string>> get_single_paragraph(const Files::Filesystem& fs,
+    Expected<RawParagraph> parse_single_paragraph(const std::string& str)
+    {
+        const std::vector<RawParagraph> p =
+            Parser(str.c_str(), str.c_str() + str.size()).get_paragraphs();
+
+        if (p.size() == 1)
+        {
+            return p.at(0);
+        }
+
+        return std::error_code(ParagraphParseResult::EXPECTED_ONE_PARAGRAPH);
+    }
+
+    Expected<RawParagraph> get_single_paragraph(const Files::Filesystem& fs,
                                                                                 const fs::path& control_path)
     {
         const Expected<std::string> contents = fs.read_contents(control_path);
@@ -176,7 +189,7 @@ namespace vcpkg::Paragraphs
         return contents.error();
     }
 
-    Expected<std::vector<std::unordered_map<std::string, std::string>>> get_paragraphs(const Files::Filesystem& fs,
+    Expected<std::vector<RawParagraph>> get_paragraphs(const Files::Filesystem& fs,
                                                                                        const fs::path& control_path)
     {
         const Expected<std::string> contents = fs.read_contents(control_path);
@@ -188,27 +201,14 @@ namespace vcpkg::Paragraphs
         return contents.error();
     }
 
-    Expected<std::unordered_map<std::string, std::string>> parse_single_paragraph(const std::string& str)
-    {
-        const std::vector<std::unordered_map<std::string, std::string>> p =
-            Parser(str.c_str(), str.c_str() + str.size()).get_paragraphs();
-
-        if (p.size() == 1)
-        {
-            return p.at(0);
-        }
-
-        return std::error_code(ParagraphParseResult::EXPECTED_ONE_PARAGRAPH);
-    }
-
-    Expected<std::vector<std::unordered_map<std::string, std::string>>> parse_paragraphs(const std::string& str)
+    Expected<std::vector<RawParagraph>> parse_paragraphs(const std::string& str)
     {
         return Parser(str.c_str(), str.c_str() + str.size()).get_paragraphs();
     }
 
     ParseExpected<SourceControlFile> try_load_port(const Files::Filesystem& fs, const fs::path& path)
     {
-        Expected<std::vector<std::unordered_map<std::string, std::string>>> pghs = get_paragraphs(fs, path / "CONTROL");
+        Expected<std::vector<RawParagraph>> pghs = get_paragraphs(fs, path / "CONTROL");
         if (auto vector_pghs = pghs.get())
         {
             return SourceControlFile::parse_control_file(std::move(*vector_pghs));
@@ -221,7 +221,7 @@ namespace vcpkg::Paragraphs
 
     Expected<BinaryControlFile> try_load_cached_package(const VcpkgPaths& paths, const PackageSpec& spec)
     {
-        Expected<std::vector<std::unordered_map<std::string, std::string>>> pghs =
+        Expected<std::vector<RawParagraph>> pghs =
             get_paragraphs(paths.get_filesystem(), paths.package_dir(spec) / "CONTROL");
 
         if (auto p = pghs.get())
diff --git a/toolsrc/src/vcpkg/parse.cpp b/toolsrc/src/vcpkg/parse.cpp
index d50296cf8..68fac0b0f 100644
--- a/toolsrc/src/vcpkg/parse.cpp
+++ b/toolsrc/src/vcpkg/parse.cpp
@@ -6,7 +6,7 @@
 
 namespace vcpkg::Parse
 {
-    static Optional<std::string> remove_field(std::unordered_map<std::string, std::string>* fields,
+    static Optional<std::string> remove_field(RawParagraph* fields,
                                               const std::string& fieldname)
     {
         auto it = fields->find(fieldname);
diff --git a/toolsrc/src/vcpkg/sourceparagraph.cpp b/toolsrc/src/vcpkg/sourceparagraph.cpp
index 1a52bd05f..a5054eb3b 100644
--- a/toolsrc/src/vcpkg/sourceparagraph.cpp
+++ b/toolsrc/src/vcpkg/sourceparagraph.cpp
@@ -3,6 +3,7 @@
 #include <vcpkg/packagespec.h>
 #include <vcpkg/sourceparagraph.h>
 #include <vcpkg/triplet.h>
+#include <vcpkg/logicexpression.h>
 
 #include <vcpkg/base/checks.h>
 #include <vcpkg/base/expected.h>
@@ -142,7 +143,7 @@ namespace vcpkg
     }
 
     ParseExpected<SourceControlFile> SourceControlFile::parse_control_file(
-        std::vector<std::unordered_map<std::string, std::string>>&& control_paragraphs)
+        std::vector<Parse::RawParagraph>&& control_paragraphs)
     {
         if (control_paragraphs.size() == 0)
         {
@@ -222,18 +223,11 @@ namespace vcpkg
         std::vector<std::string> ret;
         for (auto&& dep : deps)
         {
-            auto qualifiers = Strings::split(dep.qualifier, "&");
-            if (std::all_of(qualifiers.begin(), qualifiers.end(), [&](const std::string& qualifier) {
-                    if (qualifier.empty()) return true;
-                    if (qualifier[0] == '!')
-                    {
-                        return t.canonical_name().find(qualifier.substr(1)) == std::string::npos;
-                    }
-                    return t.canonical_name().find(qualifier) != std::string::npos;
-                }))
-            {
-                ret.emplace_back(dep.name());
-            }
+			const auto & qualifier = dep.qualifier;
+			if (qualifier.empty() || evaluate_expression(qualifier, t.canonical_name()))
+			{
+				ret.emplace_back(dep.name());
+			}
         }
         return ret;
     }
@@ -244,18 +238,11 @@ namespace vcpkg
         std::vector<Features> ret;
         for (auto&& dep : deps)
         {
-            auto qualifiers = Strings::split(dep.qualifier, "&");
-            if (std::all_of(qualifiers.begin(), qualifiers.end(), [&](const std::string& qualifier) {
-                    if (qualifier.empty()) return true;
-                    if (qualifier[0] == '!')
-                    {
-                        return t.canonical_name().find(qualifier.substr(1)) == std::string::npos;
-                    }
-                    return t.canonical_name().find(qualifier) != std::string::npos;
-                }))
-            {
-                ret.emplace_back(dep.depend);
-            }
+			const auto & qualifier = dep.qualifier;
+			if (qualifier.empty() || evaluate_expression(qualifier, t.canonical_name()))
+			{
+				ret.emplace_back(dep.depend);
+			}
         }
         return ret;
     }
diff --git a/toolsrc/src/vcpkg/statusparagraph.cpp b/toolsrc/src/vcpkg/statusparagraph.cpp
index 86946a31a..f7e00f21c 100644
--- a/toolsrc/src/vcpkg/statusparagraph.cpp
+++ b/toolsrc/src/vcpkg/statusparagraph.cpp
@@ -24,7 +24,7 @@ namespace vcpkg
             .push_back('\n');
     }
 
-    StatusParagraph::StatusParagraph(std::unordered_map<std::string, std::string>&& fields)
+    StatusParagraph::StatusParagraph(Parse::RawParagraph&& fields)
         : want(Want::ERROR_STATE), state(InstallState::ERROR_STATE)
     {
         auto status_it = fields.find(BinaryParagraphRequiredField::STATUS);
diff --git a/toolsrc/src/vcpkg/userconfig.cpp b/toolsrc/src/vcpkg/userconfig.cpp
index a7c4e2765..3551ae81e 100644
--- a/toolsrc/src/vcpkg/userconfig.cpp
+++ b/toolsrc/src/vcpkg/userconfig.cpp
@@ -51,7 +51,7 @@ namespace vcpkg
             {
                 const auto& pghs = *p_pghs;
 
-                std::unordered_map<std::string, std::string> keys;
+				Parse::RawParagraph keys;
                 if (pghs.size() > 0) keys = pghs[0];
 
                 for (size_t x = 1; x < pghs.size(); ++x)