Issue 1564-Fix FilterEngine::Matches for allowing request which is whitelisted in the ascendant node

src/ReferrerMapping.cpp

Index: src/ReferrerMapping.cpp
===================================================================
--- a/src/ReferrerMapping.cpp
+++ b/src/ReferrerMapping.cpp
@@ -24,12 +24,13 @@
 {
 }
 
-void ReferrerMapping::Add(const std::string& url, const std::string& referrer)
+void ReferrerMapping::Add(const std::string& url, const std::string& referrer,
+                          FilterEngine::ContentType requestType)
 {
   if (mapping.find(url) != mapping.end())
     cachedUrls.remove(url);
   cachedUrls.push_back(url);
-  mapping[url] = referrer;
+  mapping.emplace(url, RequestInfo(referrer, requestType));
 
   const int urlsToPop = cachedUrls.size() - maxCachedUrls;
   for (int i = 0; i < urlsToPop; i++)
@@ -44,17 +45,57 @@
   const std::string& url) const
 {
   std::vector<std::string> referrerChain;
-  referrerChain.push_back(url);
+  if (url.empty())
+  {
+    return referrerChain;
+  }
   // We need to limit the chain length to ensure we don't block indefinitely
   // if there's a referrer loop.
-  const int maxChainLength = 10;
-  std::map<std::string, std::string>::const_iterator currentEntry =
+  // Despite there is quite effecient algorithm to work with such loops, merely
+  // limit the chain to some number works fine on practice and seems quiet
+  // elegant.
+  const int maxChainLength = 20;
+  referrerChain.reserve(maxChainLength);
+  std::map<std::string, RequestInfo>::const_iterator currentEntry =
     mapping.find(url);
-  for (int i = 0; i < maxChainLength && currentEntry != mapping.end(); i++)
+  // We need it to build [first, second] when there is only one entry in the
+  // `mapping` member, [{second, {first, AnyTypeOfSecond}}].
+  // So, if we exit from the cycle not because of loop limit and the first is
+  // not empty then add it.
+  std::map<std::string, RequestInfo>::const_iterator prevEntry = mapping.end();
+
+  // process the current url beyond the loop below because we should add it
+  // even if `mapping` is empty.
+  if (currentEntry != mapping.end())
   {
-    const std::string& currentUrl = currentEntry->second;
-    referrerChain.insert(referrerChain.begin(), currentUrl);
-    currentEntry = mapping.find(currentUrl);
+    if (currentEntry->second.type == FilterEngine::ContentType::CONTENT_TYPE_SUBDOCUMENT)
+    {
+      referrerChain.push_back(url);
+    }
+    prevEntry = currentEntry;
+    currentEntry = mapping.find(currentEntry->second.referrer);
   }
+  else
+  {
+    // If there is no information for the url in `mapping` then  assume that
+    // it's a frame, despite it's not necessary to be a frame.
+    referrerChain.push_back(url);
+  }
+  for (int i = 0; i < maxChainLength && currentEntry != mapping.end(); i++,
+    currentEntry = mapping.find(currentEntry->second.referrer))
+  {
+    if (currentEntry->second.type == FilterEngine::ContentType::CONTENT_TYPE_SUBDOCUMENT)
+    {
+      referrerChain.push_back(currentEntry->first);
+    }
+    prevEntry = currentEntry;
+  }
+  if (prevEntry != mapping.end() && !prevEntry->second.referrer.empty())
+  {
+    referrerChain.push_back(prevEntry->second.referrer);
+  }
+  // it should be slightly more efficient to reverse it at the end instead
+  // of copying the tail of the referrerChain on each adding.
+  reverse(referrerChain.begin(), referrerChain.end());
   return referrerChain;
 }