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.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;
@@ skipping 40 matching lines @@
   private Subscription[] subscriptions;
 
   /**
    * Indicates whether filtering is enabled or not.
    */
   private boolean filteringEnabled = false;
 
   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).
    */
   public static AdblockPlus getApplication()
   {
     return instance;
   }
 
   public int getBuildNumber()
@@ skipping 201 matching lines @@
   {
     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);

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

This change is unrelated, caused by rebasing.

   }
 
   /**
    * Returns ElemHide selectors for domain.
    *
    * @param domain The domain
    * @return A list of CSS selectors
    */
   public String[] getSelectorsForDomain(final String domain)
   {
@@ skipping 12 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)
+  {
+    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;
   }
 
   /**
    * 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);
   }
 }