4 files changed, 234 insertions, 33 deletions

diff --git a/apt-pkg/cachefilter-patterns.cc b/apt-pkg/cachefilter-patterns.cc
index a9f76ff1d..5a58a9767 100644
--- a/apt-pkg/cachefilter-patterns.cc
+++ b/apt-pkg/cachefilter-patterns.cc
@@ -17,6 +17,32 @@ namespace APT
 namespace Internal
 {
 
+static const constexpr struct
+{
+   APT::StringView shortName;
+   APT::StringView longName;
+   bool takesArgument;
+} shortPatterns[] = {
+   {"r"_sv, "?architecture"_sv, true},
+   {"A"_sv, "?archive"_sv, true},
+   {"M"_sv, "?automatic"_sv, false},
+   {"b"_sv, "?broken"_sv, false},
+   {"c"_sv, "?config-files"_sv, false},
+   {"E"_sv, "?essential"_sv, false},
+   {"F"_sv, "?false"_sv, false},
+   {"g"_sv, "?garbage"_sv, false},
+   {"i"_sv, "?installed"_sv, false},
+   {"n"_sv, "?name"_sv, true},
+   {"o"_sv, "?obsolete"_sv, false},
+   {"O"_sv, "?origin"_sv, true},
+   {"s"_sv, "?section"_sv, true},
+   {"e"_sv, "?source-package"_sv, true},
+   {"T"_sv, "?true"_sv, false},
+   {"U"_sv, "?upgradable"_sv, false},
+   {"V"_sv, "?version"_sv, true},
+   {"v"_sv, "?virtual"_sv, false},
+};
+
 template <class... Args>
 std::string rstrprintf(Args... args)
 {
@@ -32,41 +58,197 @@ std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseTop()
    auto node = parse();
    skipSpace();
 
+   if (node == nullptr)
+      throw Error{Node{0, sentence.size()}, "Expected pattern"};
+
    if (node->end != sentence.size())
+      throw Error{Node{node->end, sentence.size()}, "Expected end of file"};
+
+   return node;
+}
+
+// Parse any pattern
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parse()
+{
+   return parseOr();
+}
+
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseOr()
+{
+   auto start = state.offset;
+   std::vector<std::unique_ptr<PatternTreeParser::Node>> nodes;
+
+   auto firstNode = parseAnd();
+
+   if (firstNode == nullptr)
+      return nullptr;
+
+   nodes.push_back(std::move(firstNode));
+   for (skipSpace(); sentence[state.offset] == '|'; skipSpace())
+   {
+      state.offset++;
+      skipSpace();
+      auto node = parseAnd();
+
+      if (node == nullptr)
+	 throw Error{Node{state.offset, sentence.size()}, "Expected pattern after |"};
+
+      nodes.push_back(std::move(node));
+   }
+
+   if (nodes.size() == 0)
+      return nullptr;
+   if (nodes.size() == 1)
+      return std::move(nodes[0]);
+
+   auto node = std::make_unique<PatternNode>();
+   node->start = start;
+   node->end = nodes[nodes.size() - 1]->end;
+   node->term = "?or";
+   node->arguments = std::move(nodes);
+   node->haveArgumentList = true;
+
+   return node;
+}
+
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseAnd()
+{
+   auto start = state.offset;
+   std::vector<std::unique_ptr<PatternTreeParser::Node>> nodes;
+
+   for (skipSpace(); state.offset < sentence.size(); skipSpace())
    {
-      Node node2;
+      auto node = parseUnary();
+
+      if (node == nullptr)
+	 break;
 
-      node2.start = node->end;
-      node2.end = sentence.size();
-      throw Error{node2, "Expected end of file"};
+      nodes.push_back(std::move(node));
    }
 
+   if (nodes.size() == 0)
+      return nullptr;
+   if (nodes.size() == 1)
+      return std::move(nodes[0]);
+
+   auto node = std::make_unique<PatternNode>();
+   node->start = start;
+   node->end = nodes[nodes.size() - 1]->end;
+   node->term = "?and";
+   node->arguments = std::move(nodes);
+   node->haveArgumentList = true;
+
    return node;
 }
 
-// Parse any pattern
-std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parse()
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseUnary()
+{
+
+   if (sentence[state.offset] != '!')
+      return parsePrimary();
+
+   auto start = ++state.offset;
+   auto primary = parsePrimary();
+
+   if (primary == nullptr)
+      throw Error{Node{start, sentence.size()}, "Expected pattern"};
+
+   auto node = std::make_unique<PatternNode>();
+   node->start = start;
+   node->end = primary->end;
+   node->term = "?not";
+   node->arguments.push_back(std::move(primary));
+   node->haveArgumentList = true;
+   return node;
+}
+
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parsePrimary()
 {
    std::unique_ptr<Node> node;
+   if ((node = parseShortPattern()) != nullptr)
+      return node;
    if ((node = parsePattern()) != nullptr)
       return node;
+   if ((node = parseGroup()) != nullptr)
+      return node;
+
+   return nullptr;
+}
+
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseGroup()
+{
+   if (sentence[state.offset] != '(')
+      return nullptr;
+
+   auto start = state.offset++;
+
+   skipSpace();
+   auto node = parse();
+   if (node == nullptr)
+      throw Error{Node{state.offset, sentence.size()},
+		  "Expected pattern after '('"};
+   skipSpace();
+
+   if (sentence[state.offset] != ')')
+      throw Error{Node{state.offset, sentence.size()},
+		  "Expected closing parenthesis"};
+
+   auto end = ++state.offset;
+   node->start = start;
+   node->end = end;
+   return node;
+}
+
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseArgument(bool shrt)
+{
+   std::unique_ptr<Node> node;
    if ((node = parseQuotedWord()) != nullptr)
       return node;
-   if ((node = parseWord()) != nullptr)
+   if ((node = parseWord(shrt)) != nullptr)
+      return node;
+   if ((node = parse()) != nullptr)
+      return node;
+
+   throw Error{Node{state.offset, sentence.size()},
+	       "Expected pattern, quoted word, or word"};
+}
+
+// Parse a short pattern
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseShortPattern()
+{
+   if (sentence[state.offset] != '~')
+      return nullptr;
+
+   for (auto &sp : shortPatterns)
+   {
+      if (sentence.substr(state.offset + 1, sp.shortName.size()) != sp.shortName)
+	 continue;
+
+      auto node = std::make_unique<PatternNode>();
+      node->end = node->start = state.offset;
+      node->term = sp.longName;
+
+      state.offset += sp.shortName.size() + 1;
+      if (sp.takesArgument)
+      {
+	 node->arguments.push_back(parseArgument(true));
+	 node->haveArgumentList = true;
+      }
+      node->end = state.offset;
+
       return node;
+   }
 
-   Node eNode;
-   eNode.end = eNode.start = state.offset;
-   throw Error{eNode, "Expected pattern, quoted word, or word"};
+   throw Error{Node{state.offset, sentence.size()}, "Unknown short pattern"};
 }
 
 // Parse a list pattern (or function call pattern)
 std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parsePattern()
 {
-   static const APT::StringView CHARS("0123456789"
-				      "abcdefghijklmnopqrstuvwxyz"
-				      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
-				      "-");
+   static constexpr auto CHARS = ("0123456789"
+				  "abcdefghijklmnopqrstuvwxyz"
+				  "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+				  "-"_sv);
    if (sentence[state.offset] != '?')
       return nullptr;
 
@@ -81,6 +263,9 @@ std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parsePattern()
 
    node->term = sentence.substr(node->start, state.offset - node->start);
 
+   if (node->term.size() <= 1)
+      throw Error{*node, "Pattern must have a term/name"};
+
    node->end = skipSpace();
    // We don't have any arguments, return node;
    if (sentence[state.offset] != '(')
@@ -97,7 +282,7 @@ std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parsePattern()
       return node;
    }
 
-   node->arguments.push_back(parse());
+   node->arguments.push_back(parseArgument(false));
    skipSpace();
    while (sentence[state.offset] == ',')
    {
@@ -106,7 +291,7 @@ std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parsePattern()
       // This was a trailing comma - allow it and break the loop
       if (sentence[state.offset] == ')')
 	 break;
-      node->arguments.push_back(parse());
+      node->arguments.push_back(parseArgument(false));
       skipSpace();
    }
 
@@ -146,10 +331,13 @@ std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseQuotedWord()
 }
 
 // Parse a bare word atom
-std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseWord()
+std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseWord(bool shrt)
 {
-   static const APT::StringView DISALLOWED_START("?~,()\0", 6);
-   static const APT::StringView DISALLOWED(",()\0", 4);
+   static const constexpr auto DISALLOWED_START = "!?~|,() \0"_sv;
+   static const constexpr auto DISALLOWED_LONG = "|,()\0"_sv;
+   static const constexpr auto DISALLOWED_SHRT = "|,() ?\0"_sv;
+   const auto DISALLOWED = shrt ? DISALLOWED_SHRT : DISALLOWED_LONG;
+
    if (DISALLOWED_START.find(sentence[state.offset]) != APT::StringView::npos)
       return nullptr;
 
@@ -167,20 +355,21 @@ std::unique_ptr<PatternTreeParser::Node> PatternTreeParser::parseWord()
 // Rendering of the tree in JSON for debugging
 std::ostream &PatternTreeParser::PatternNode::render(std::ostream &os)
 {
-   os << "{"
-      << "\"term\": \"" << term.to_string() << "\",\n"
-      << "\"arguments\": [\n";
-   for (auto &node : arguments)
-      node->render(os) << "," << std::endl;
-   os << "null]\n";
-   os << "}\n";
+
+   os << term.to_string();
+   if (haveArgumentList)
+   {
+      os << "(";
+      for (auto &node : arguments)
+	 node->render(os) << ",";
+      os << ")";
+   }
    return os;
 }
 
 std::ostream &PatternTreeParser::WordNode::render(std::ostream &os)
 {
-   os << '"' << word.to_string() << '"';
-   return os;
+   return quoted ? os << '"' << word.to_string() << '"' : os << word.to_string();
 }
 
 std::nullptr_t PatternTreeParser::Node::error(std::string message)
diff --git a/apt-pkg/cachefilter-patterns.h b/apt-pkg/cachefilter-patterns.h
index bd8ce7e7e..4eeb68594 100644
--- a/apt-pkg/cachefilter-patterns.h
+++ b/apt-pkg/cachefilter-patterns.h
@@ -39,6 +39,8 @@ struct PatternTreeParser
       size_t start = 0;
       size_t end = 0;
 
+      explicit Node(size_t start = 0, size_t end = 0) : start(start), end(end) {}
+
       virtual std::ostream &render(std::ostream &os) { return os; };
       std::nullptr_t error(std::string message);
    };
@@ -71,7 +73,7 @@ struct PatternTreeParser
 
    struct State
    {
-      off_t offset = 0;
+      size_t offset = 0;
    };
 
    APT::StringView sentence;
@@ -90,11 +92,18 @@ struct PatternTreeParser
    /// There may not be anything before or after the pattern, except for
    /// whitespace.
    std::unique_ptr<Node> parseTop();
+   std::unique_ptr<Node> parse(); // public for test cases only
 
    private:
-   std::unique_ptr<Node> parse();
+   std::unique_ptr<Node> parseOr();
+   std::unique_ptr<Node> parseAnd();
+   std::unique_ptr<Node> parseUnary();
+   std::unique_ptr<Node> parsePrimary();
+   std::unique_ptr<Node> parseGroup();
    std::unique_ptr<Node> parsePattern();
-   std::unique_ptr<Node> parseWord();
+   std::unique_ptr<Node> parseShortPattern();
+   std::unique_ptr<Node> parseArgument(bool shrt);
+   std::unique_ptr<Node> parseWord(bool shrt);
    std::unique_ptr<Node> parseQuotedWord();
 };
 
diff --git a/apt-pkg/cacheset.cc b/apt-pkg/cacheset.cc
index f5251eda8..ae1d5ee3e 100644
--- a/apt-pkg/cacheset.cc
+++ b/apt-pkg/cacheset.cc
@@ -295,7 +295,7 @@ bool CacheSetHelper::PackageFromPackageName(PackageContainerInterface * const pc
 
 bool CacheSetHelper::PackageFromPattern(PackageContainerInterface *const pci, pkgCacheFile &Cache, std::string const &pattern)
 {
-   if (pattern.size() < 1 || pattern[0] != '?')
+   if (pattern.size() < 1 || (pattern[0] != '?' && pattern[0] != '~'))
       return false;
 
    auto compiledPattern = APT::CacheFilter::ParsePattern(pattern, &Cache);
diff --git a/apt-pkg/contrib/string_view.h b/apt-pkg/contrib/string_view.h
index f4f0c645f..05aad3327 100644
--- a/apt-pkg/contrib/string_view.h
+++ b/apt-pkg/contrib/string_view.h
@@ -123,7 +123,10 @@ static inline int StringViewCompareFast(StringView a, StringView b) {
     return memcmp(a.data(), b.data(), a.size());
 }
 
-
+static constexpr inline APT::StringView operator""_sv(const char *data, size_t size)
+{
+   return APT::StringView(data, size);
+}
 }
 
 inline bool operator ==(const char *other, APT::StringView that);