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.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
 import java.util.TimeZone;
 import java.util.regex.Pattern;
 
@@ -82,6 +89,8 @@
   
   private static AdblockPlus instance;
 
+  private Map<String, Set<String>> referrerMapping = new HashMap<String, Set<String>>();
+
   /**
    * Returns pointer to itself (singleton pattern).
    */
@@ -314,6 +323,9 @@
    */
   public boolean matches(String url, String query, String referrer, String accept)
   {
+    if (referrer != null)
+      recordReferrer(url, referrer);
+
     if (!filteringEnabled)
       return false;
     
@@ -344,7 +356,51 @@
     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)
+  {
+    // TODO: Garbage collect the mapping - currently it will grow out of control.
+    //       In addition, we might have to persist mappings, because clients are
+    //       likely to cache some requests in the chain.
+    if (!referrerMapping.containsKey(url))
+      referrerMapping.put(url, new HashSet<String>());
+    Set<String> referrers = referrerMapping.get(url);
+    referrers.add(referrer);

[Wladimir Palant, 2013/11/25 10:24:41]

Do you think that this is really necessary? We aren't doing exact science here,
it's a heuristic that should work in *most* cases. In other words, a simple
string => string mapping should do, we can overwrite the referrer if we get a
new one.

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

Yes, I think it makes sense to not have a single chain per referrer, frames by
ad providers are supposedly used on several sites.

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

Not with the same parameters - they have to know somehow who needs to get paid,
referrers aren't reliable enough for that. IMHO frames with identical URLs
embedded from different websites that are open at the same time should be a very
rare edge case not worth complicating the code over.

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

Alright, didn't think of that. Makes the code much simpler indeed.

+  }
+
+  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;
   }
 
   /**