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)
+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));

[Wladimir Palant, 2014/11/25 15:46:37]

My understanding is that map::emplace won't replace existing entries. That's
wrong - we should keep the most current referrer for each request. Consider for
example multiple websites using the same ad provider.

[sergei, 2014/11/26 10:34:43]

Excellent point, I forget about it.

 
   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(
+std::vector<std::string> ReferrerMapping::BuildFrameStructure(
   const std::string& url) const
 {
   std::vector<std::string> referrerChain;

[Wladimir Palant, 2014/11/25 15:46:37]

If you rename the function you should also rename the name of this variable.

[sergei, 2014/11/26 10:34:43]

renamed to `frames`.

-  referrerChain.push_back(url);
+  if (url.empty())
+  {
+    return referrerChain;

[Wladimir Palant, 2014/11/25 15:46:37]

Why is this special case necessary? An empty string simply won't be found in the
map.

[sergei, 2014/11/26 10:34:43]

Because it's rather an invalid argument and we should neither even try to find
it in the container nor increase the complexity of the logic below by it. I
would even add it to ReferrerMapping::Add as well, but I guess it's inconsistent
with the current approach.

Removed.

[Wladimir Palant, 2014/12/09 21:20:03]

I realized that I misunderstood how this method is supposed to work - see below.

+  }
   // 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.

[Wladimir Palant, 2014/11/25 15:46:37]

This snarky comment seems completely pointless to document the code below.

[sergei, 2014/11/26 10:34:43]

removed

+  const int maxChainLength = 20;

[Wladimir Palant, 2014/11/25 15:46:37]

Why increase this value? 10 should be enough for any real-world scenario.

[sergei, 2014/11/26 10:34:43]

It was needed for tests.
removed.

+  referrerChain.reserve(maxChainLength);

[Wladimir Palant, 2014/11/25 15:46:37]

I doubt that this makes sense. While we might get a lengthy chain, this is an
absolutely exceptional case. In the overwhelming majority of cases the resulting
vector will have length 1 - no point reserving space for 32 elements (vector
size will be "rounded up" to the next power of two).

[sergei, 2014/11/26 10:34:43]

I've tested, it's indeed has only one frame in about 70% cases and in about 30%
it has 2 frames.
removed.

BTW, could you point to the reference where it's stated that `reserve` rounds up
to the next power of two? It was not before and the current implementation does
not do it.

[Wladimir Palant, 2014/12/09 21:20:03]

Any sane allocation approach does, to minimize memory fragmentation - but that's
an implementation detail of course, so it won't be mentioned in any
documentation.

[sergei, 2014/12/12 17:07:07]

Actually on a lower level usual allocator rounds it to some granularity which
depends on the machine. But it's not the proper place to discuss it.

+  std::map<std::string, RequestInfo>::const_iterator currentEntry =

[Wladimir Palant, 2014/11/25 15:46:37]

Given that you use std::map<std::string, RequestInfo> several times, why not set
up ReferrerMap as an alias for it?

[sergei, 2014/11/26 10:34:43]

changed.

     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.

[Wladimir Palant, 2014/11/25 15:46:37]

I assume that the code this comment refers to will be removed. However, the
comment is currently completely unintelligible.

+  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);

[Wladimir Palant, 2014/11/25 15:46:37]

This special case is unnecessary. An empty referrer chain is perfectly valid and
FilterEngine::Matches() can deal with it. So please don't duplicate code outside
the loop.

[sergei, 2014/11/26 10:34:43]

Not clear which special case is mentioned, could you point to the incorrect
test, provide another test which demonstrates the expected behaviour or explain
how it can be in the loop.

[Wladimir Palant, 2014/12/09 21:20:03]

I just realized that this was designed to work differently from what I expected
:-( I thought that one would call this function with the URL of a request, but
apparently it is supposed to be called with the URL of its referrer - and that
referrer will always be listed in the frame structure. Given your changes here,
the current design seems wrong. What do you think?

[sergei, 2014/12/12 17:07:07]

I also misunderstood it the same way initially and there was even the issue
1160. So it's definitely a tricky point, feel free to suggest the fix of the
documentation or API.
Eventually, I actually came with the conclusion that it's done the correct way
because we should not and we don't have to modify ReferrerMapping to get the
frame structure for new request. It's very good from the design point of view.

What concerns the current design, let's consider the following example
Resource relation structure ;requestType; referrer
http://root-page/
 +http://some-frame/        ;subdocument; http://root-page/
   +http://flash/player.swf ;object     ; http://some-frame/
   | +http://cdn/img        ;image      ; http://flash/player.swf
   +http://some-frame/script;script     ; http://some-frame/

For the call matches(url: "http://some-frame/", subdocument, referrer:
"http://root-page/") or matches(url: "http://some-frame/script", script,
referrer: "http://some-frame/") we should build the frame structure based on
"http://root-page/" or "http://some-frame/" respectively and it seems we need
*always* include it into the frame structure. But for the call matches(url:
"http://cdn/img", image, referrer: "http://flash/player.swf") we should not
include "http://flash/player.swf" into the frame structure, the frame structure
is "http://root-page/" -> "http://some-frame/".
So, yes, it's wrong and the aim of this fix is to adjust it.

+  }
+  for (int i = 0; i < maxChainLength && currentEntry != mapping.end(); i++,
+    currentEntry = mapping.find(currentEntry->second.referrer))

[Wladimir Palant, 2014/11/25 15:46:37]

Please put the assignment to currentEntry at the end of the loop body, where it
was before. The code is much easier to read that way, in particular prevEntry
and currentEntry should always be set in the same place.

[sergei, 2014/11/26 10:34:43]

Not sure whether it's easier to read, because 'for loop' has 'initialization',
'condition' and 'increment' (post iteration statement), here we spread the
'increment' among `for(....)` and the body of the loop. May be it should not be
a for-loop?

+  {
+    if (currentEntry->second.type == FilterEngine::ContentType::CONTENT_TYPE_SUBDOCUMENT)
+    {
+      referrerChain.push_back(currentEntry->first);

[Wladimir Palant, 2014/11/25 15:46:37]

This should be .insert(referrerChain.begin(), ...) - same as before.

[sergei, 2014/11/26 10:34:43]

In general it's inefficient, I don't understand why we need it, but it's OK
here, because as I see its size does not usually grow more than 2 elements.

[Wladimir Palant, 2014/12/09 21:20:03]

That's what I meant - for tiny lists like what we have here, doing this kind of
optimizations (making the logic more complicated to follow) just isn't worth it.

+    }
+    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.

[Wladimir Palant, 2014/11/25 15:46:37]

It should also be pretty pointless, with the referrer chain having only one
element most of the time...

[sergei, 2014/11/26 10:34:43]

The main reason of it was to use push_back and reverse it at the end.

+  reverse(referrerChain.begin(), referrerChain.end());
   return referrerChain;
 }