Determine the frame structure

src/org/adblockplus/android/AdblockPlus.java

Index: src/org/adblockplus/android/AdblockPlus.java
===================================================================
--- a/src/org/adblockplus/android/AdblockPlus.java
+++ b/src/org/adblockplus/android/AdblockPlus.java
@@ -23,7 +23,14 @@
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.InputStreamReader;
+import java.util.ArrayList;
 import java.util.Calendar;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
 import java.util.TimeZone;
 import java.util.regex.Pattern;
 
@@ -84,6 +91,25 @@
   private ABPEngine abpEngine;
   
   private static AdblockPlus instance;
+  
+  private static class ReferrerMappingCache extends LinkedHashMap<String, Set<String>>
+  {
+    private static final long serialVersionUID = 1L;
+    private static final int MAX_SIZE = 2;

[Felix Dahlke, 2013/11/27 12:19:33]

Note that I've set this to 5000, not 2. I'd rather not upload a new patch set
for this since I already added a bunch of comments.

As to how I arrived at 5000: I assumed that each referrer mapping takes on
average around 512 bytes of memory. With 5000 of these, we're at around 2.5 MB
and possibly a little overhead. Seems reasonable.

[Wladimir Palant, 2013/11/27 12:59:01]

I think that "how much memory can we sacrifice" is the wrong logic here. The
question is rather "how many referrer chains can be relevant at any given time?"
Here "relevant" means that the corresponding website is open and might still
load new content into a frame. UI limitations of Android browsers make lots of
open tabs rather unlikely. Also, the web content embedded in Android apps
doesn't tend to have a complicated structure. So if we assume 50 open web
contexts (tabs or apps) each having on average five referrer chains we get 250
as size of this cache - and that's already a very generous estimate. I would
limit the cache to 500 entries, just to be on the safe side. Anything beyond
that doesn't seem to be justified.

Note that the memory overhead is very significant if you store sets rather than
single strings (which you shouldn't, see other comment).

[Felix Dahlke, 2013/11/27 13:38:59]

I think we're still not on the same page here. IMO, we need to cache as many
referrer mappings as possible, simply because browsers will cache intermediate
requests and not make them again in the near future. That's the same reason why
I want to persist these mappings.

+
+    public ReferrerMappingCache()
+    {
+      super(MAX_SIZE, 0.75f, true);

[Wladimir Palant, 2013/11/27 12:59:01]

I think that the first parameter should be MAX_SIZE + 1 here. When the cache is
already full a new entry will be inserted first and only then the least recently
used entry will be evicted.

[Felix Dahlke, 2013/11/27 13:38:59]

Done.

+    }
+
+    @Override
+    protected boolean removeEldestEntry(Map.Entry<String, Set<String>> eldest)
+    {
+      return size() > MAX_SIZE;
+    }
+  };
+
+  private ReferrerMappingCache referrerMapping = new ReferrerMappingCache();
 
   /**
    * Returns pointer to itself (singleton pattern).
@@ -338,6 +364,9 @@
    */
   public boolean matches(String url, String query, String referrer, String accept)
   {
+    if (referrer != null)
+      recordReferrer(url, referrer);
+
     if (!filteringEnabled)
       return false;
     
@@ -368,7 +397,48 @@
     if (!"".equals(query))
       url = url + "?" + query;
 
-    return abpEngine.matches(url, contentType, referrer);
+    final List<List<String>> referrerChains = referrer != null
+      ? buildReferrerChains(referrer)
+      : Collections.singletonList(Collections.<String>emptyList());
+    for (List<String> referrerChain : referrerChains)
+    {
+      Log.d("Referrer chain", url + ": " + referrerChain.toString());
+      String[] referrerChainArray = referrerChain.toArray(new String[referrerChain.size()]);
+      if (abpEngine.matches(url, contentType, referrerChainArray))
+        return true;
+    }
+    return false;
+  }
+
+  private void recordReferrer(String url, String referrer)
+  {
+    if (!referrerMapping.containsKey(url))
+      referrerMapping.put(url, new HashSet<String>());
+    Set<String> referrers = referrerMapping.get(url);
+    referrers.add(referrer);
+  }
+
+  private List<List<String>> buildReferrerChains(String url)
+  {
+    List<List<String>> referrerChains = new ArrayList<List<String>>();
+    Set<String> referrers = referrerMapping.get(url);
+    if (referrers == null)
+    {
+      List<String> referrerChain = new ArrayList<String>();
+      referrerChain.add(url);
+      referrerChains.add(referrerChain);
+      return referrerChains;
+    }
+
+    for (String referrer : referrers) {
+      List<List<String>> currentReferrerChains = buildReferrerChains(referrer);
+      for (List<String> referrerChain : currentReferrerChains)
+      {
+        referrerChain.add(0, url);
+        referrerChains.add(referrerChain);
+      }
+    }
+    return referrerChains;
   }
 
   /**