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

src/ReferrerMapping.cpp

 /*
  * This file is part of Adblock Plus <http://adblockplus.org/>,
  * Copyright (C) 2006-2014 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #include <AdblockPlus/ReferrerMapping.h>
 
 using namespace AdblockPlus;
 
 ReferrerMapping::ReferrerMapping(const int maxCachedUrls)
   : maxCachedUrls(maxCachedUrls)
 {
 }
 
-void ReferrerMapping::Add(const std::string& url, const std::string& referrer,
-                          FilterEngine::ContentType requestType)
+void ReferrerMapping::Add(const Url& url, const Url& referrer, FrameIndicator isFrame)
 {
   if (mapping.find(url) != mapping.end())
     cachedUrls.remove(url);
   cachedUrls.push_back(url);
-  mapping.emplace(url, RequestInfo(referrer, requestType));
+  mapping[url] = RequestInfo(referrer, isFrame);
 
   const int urlsToPop = cachedUrls.size() - maxCachedUrls;
   for (int i = 0; i < urlsToPop; i++)
   {
     const std::string poppedUrl = cachedUrls.front();
     cachedUrls.pop_front();
     mapping.erase(poppedUrl);
   }
 }
 
-std::vector<std::string> ReferrerMapping::BuildReferrerChain(
-  const std::string& url) const
+ReferrerMapping::Urls ReferrerMapping::BuildFrameStructure(const Url& url) const
 {
-  std::vector<std::string> referrerChain;
-  if (url.empty())
-  {
-    return referrerChain;
-  }
+  Urls frames;
   // We need to limit the chain length to ensure we don't block indefinitely
   // if there's a referrer loop.
-  // 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 =
+  const int maxChainLength = 10;
+  ReferrerMap::const_iterator currentEntry = url.empty() ? mapping.end() :
     mapping.find(url);
-  // 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())
+  ReferrerMap::const_iterator prevEntry = mapping.end();
+  for (int i = 0; i < maxChainLength && currentEntry != mapping.end(); i++)
   {
-    if (currentEntry->second.type == FilterEngine::ContentType::CONTENT_TYPE_SUBDOCUMENT)
+    if (currentEntry->second.IsFrame())
     {
-      referrerChain.push_back(url);
+      frames.insert(frames.begin(), currentEntry->first);
     }
     prevEntry = currentEntry;
     currentEntry = mapping.find(currentEntry->second.referrer);
   }
-  else
+  if (prevEntry == mapping.end())
   {
-    // 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);
+    if (!url.empty())
+    {
+      // No data, just assume that the url is a frame.
+      frames.push_back(url);
+    }
   }
-  for (int i = 0; i < maxChainLength && currentEntry != mapping.end(); i++,
-    currentEntry = mapping.find(currentEntry->second.referrer))
+  else if (!prevEntry->second.referrer.empty())
   {
-    if (currentEntry->second.type == FilterEngine::ContentType::CONTENT_TYPE_SUBDOCUMENT)
-    {
-      referrerChain.push_back(currentEntry->first);
-    }
-    prevEntry = currentEntry;
+    frames.insert(frames.begin(), prevEntry->second.referrer);
   }
-  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;
+  return frames;
 }