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.LinkedHashMap;
 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;
 import android.content.Context;
 import android.content.Intent;
+import android.content.SharedPreferences;
+import android.content.SharedPreferences.Editor;
 import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
 import android.content.pm.PackageManager.NameNotFoundException;
 import android.net.ConnectivityManager;
 import android.net.NetworkInfo;
 import android.net.Uri;
 import android.os.Build;
+import android.preference.PreferenceManager;
 import android.provider.Settings;
 import android.util.Log;
 
 public class AdblockPlus extends Application
 {
   private final static String TAG = "Application";
 
   private final static Pattern RE_JS = Pattern.compile(".*\\.js$", Pattern.CASE_INSENSITIVE);
   private final static Pattern RE_CSS = Pattern.compile(".*\\.css$", Pattern.CASE_INSENSITIVE);
   private final static Pattern RE_IMAGE = Pattern.compile(".*\\.(?:gif|png|jpe?g|bmp|ico)$", Pattern.CASE_INSENSITIVE);
@@ skipping 18 matching lines @@
   private Subscription[] subscriptions;
 
   /**
    * 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>>();
+  
+  private static class ReferrerMappingCache extends LinkedHashMap<String, String>
+  {
+    private static final long serialVersionUID = 1L;
+    private static final int MAX_SIZE = 5000;
+
+    public ReferrerMappingCache()
+    {
+      super(MAX_SIZE + 1, 0.75f, true);
+    }
+
+    @Override
+    protected boolean removeEldestEntry(Map.Entry<String, String> eldest)
+    {
+      return size() > MAX_SIZE;
+    }
+  };
+
+  private ReferrerMappingCache referrerMapping = new ReferrerMappingCache();
 
   /**
    * Returns pointer to itself (singleton pattern).
    */
   public static AdblockPlus getApplication()
   {
     return instance;
   }
 
   public int getBuildNumber()
@@ skipping 181 matching lines @@
     abpEngine.actualizeSubscriptionStatus(url);
   }
 
 
   /**
    * Enables or disables Acceptable Ads
    */
   public void setAcceptableAdsEnabled(boolean enabled)
   {
     abpEngine.setAcceptableAdsEnabled(enabled);
+  }
+
+  public String getAcceptableAdsUrl()
+  {
+    final String documentationLink = abpEngine.getDocumentationLink();
+    final String locale = getResources().getConfiguration().locale.toString().replace("_", "-");
+    return documentationLink.replace("%LINK%", "acceptable_ads").replace("%LANG%", locale);
+  }
+
+  public void setNotifiedAboutAcceptableAds(boolean notified)
+  {
+    final SharedPreferences preferences = PreferenceManager.getDefaultSharedPreferences(this);
+    final Editor editor = preferences.edit();
+    editor.putBoolean("notified_about_acceptable_ads", notified);
+    editor.commit();
+  }
+
+  public boolean isNotifiedAboutAcceptableAds()
+  {
+    final SharedPreferences preferences = PreferenceManager.getDefaultSharedPreferences(this);
+    return preferences.getBoolean("notified_about_acceptable_ads", false);
   }
 
   /**
    * Returns ElemHide selectors for domain.
    *
    * @param domain The domain
    * @return A list of CSS selectors
    */
   public String[] getSelectorsForDomain(final String domain)
   {
@@ skipping 13 matching lines @@
    * @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);
+      referrerMapping.put(url, referrer);
 
     if (!filteringEnabled)
       return false;
     
     String contentType = null;
 
     if (accept != null)
     {
       if (accept.contains("text/css"))
         contentType = "STYLESHEET";
@@ skipping 11 matching lines @@
         contentType = "IMAGE";
       else if (RE_FONT.matcher(url).matches())
         contentType = "FONT";
     }
     if (contentType == null)
       contentType = "OTHER";
 
     if (!"".equals(query))
       url = url + "?" + query;
 
-    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>();
+    final List<String> referrerChain = buildReferrerChain(referrer);
+    Log.d("Referrer chain", url + ": " + referrerChain.toString());
+    String[] referrerChainArray = referrerChain.toArray(new String[referrerChain.size()]);
+    return abpEngine.matches(url, contentType, referrerChainArray);
+  }
+
+  private List<String> buildReferrerChain(String url)
+  {
+    final List<String> referrerChain = new ArrayList<String>();
+    // We need to limit the chain length to ensure we don't block indefinitely if there's
+    // a referrer loop.
+    final int maxChainLength = 10;
+    for (int i = 0; i < maxChainLength && url != null; i++)
+    {
       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;
+      url = referrerMapping.get(url);
+    }
+    return referrerChain;
   }
 
   /**
    * 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);
   }
 }