Determine the frame structure

src/org/adblockplus/android/AdblockPlus.java

 /*
  * This file is part of Adblock Plus <http://adblockplus.org/>,
  * Copyright (C) 2006-2013 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/>.
  */
 
 package org.adblockplus.android;
 
 import java.io.BufferedReader;
 import java.io.File;
 import java.io.FileNotFoundException;
 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;
 
 import org.adblockplus.android.updater.AlarmReceiver;
 
 import android.app.ActivityManager;
 import android.app.ActivityManager.RunningServiceInfo;
 import android.app.AlarmManager;
 import android.app.Application;
 import android.app.PendingIntent;
@@ skipping 38 matching lines @@
 
   /**
    * Indicates whether filtering is enabled or not.
    */
   private boolean filteringEnabled = false;
 
   private ABPEngine abpEngine;
   
   private static AdblockPlus instance;
 
+  private Map<String, Set<String>> referrerMapping = new HashMap<String, Set<String>>();
+
   /**
    * Returns pointer to itself (singleton pattern).
    */
   public static AdblockPlus getApplication()
   {
     return instance;
   }
 
   public int getBuildNumber()
   {
@@ skipping 212 matching lines @@
    *          Request query string
    * @param referrer
    *          Request referrer header
    * @param accept
    *          Request accept header
    * @return true if matched filter was found
    * @throws Exception
    */
   public boolean matches(String url, String query, String referrer, String accept)
   {
+    if (referrer != null)
+      recordReferrer(url, referrer);
+
     if (!filteringEnabled)
       return false;
     
     String contentType = null;
 
     if (accept != null)
     {
       if (accept.contains("text/css"))
         contentType = "STYLESHEET";
       else if (accept.contains("image/*"))
@@ skipping 10 matching lines @@
         contentType = "IMAGE";
       else if (RE_FONT.matcher(url).matches())
         contentType = "FONT";
     }
     if (contentType == null)
       contentType = "OTHER";
 
     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;
   }
 
   /**
    * Checks if filtering is enabled.
    */
   public boolean isFilteringEnabled()
   {
     return filteringEnabled;
   }
 
@@ skipping 114 matching lines @@
       Log.e(TAG, e.getMessage(), e);
     }
 
     // Set crash handler
     Thread.setDefaultUncaughtExceptionHandler(new CrashHandler(this));
 
     // Initiate update check
     scheduleUpdater(0);
   }
 }