1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17
18package com.android.internal.app;
19
20import android.app.usage.UsageStats;
21import android.app.usage.UsageStatsManager;
22import android.content.ComponentName;
23import android.content.Context;
24import android.content.Intent;
25import android.content.IntentFilter;
26import android.content.pm.ApplicationInfo;
27import android.content.pm.ComponentInfo;
28import android.content.pm.PackageManager;
29import android.content.pm.PackageManager.NameNotFoundException;
30import android.content.pm.ResolveInfo;
31import android.content.SharedPreferences;
32import android.content.ServiceConnection;
33import android.os.Environment;
34import android.os.Handler;
35import android.os.IBinder;
36import android.os.Looper;
37import android.os.Message;
38import android.os.RemoteException;
39import android.os.storage.StorageManager;
40import android.os.UserHandle;
41import android.service.resolver.IResolverRankerService;
42import android.service.resolver.IResolverRankerResult;
43import android.service.resolver.ResolverRankerService;
44import android.service.resolver.ResolverTarget;
45import android.text.TextUtils;
46import android.util.ArrayMap;
47import android.util.Log;
48import com.android.internal.app.ResolverActivity.ResolvedComponentInfo;
49
50import java.io.File;
51import java.lang.InterruptedException;
52import java.text.Collator;
53import java.util.ArrayList;
54import java.util.Comparator;
55import java.util.concurrent.CountDownLatch;
56import java.util.concurrent.TimeUnit;
57import java.util.LinkedHashMap;
58import java.util.List;
59import java.util.Map;
60
61/**
62 * Ranks and compares packages based on usage stats.
63 */
64class ResolverComparator implements Comparator<ResolvedComponentInfo> {
65    private static final String TAG = "ResolverComparator";
66
67    private static final boolean DEBUG = false;
68
69    private static final int NUM_OF_TOP_ANNOTATIONS_TO_USE = 3;
70
71    // One week
72    private static final long USAGE_STATS_PERIOD = 1000 * 60 * 60 * 24 * 7;
73
74    private static final long RECENCY_TIME_PERIOD = 1000 * 60 * 60 * 12;
75
76    private static final float RECENCY_MULTIPLIER = 2.f;
77
78    // message types
79    private static final int RESOLVER_RANKER_SERVICE_RESULT = 0;
80    private static final int RESOLVER_RANKER_RESULT_TIMEOUT = 1;
81
82    // timeout for establishing connections with a ResolverRankerService.
83    private static final int CONNECTION_COST_TIMEOUT_MILLIS = 200;
84    // timeout for establishing connections with a ResolverRankerService, collecting features and
85    // predicting ranking scores.
86    private static final int WATCHDOG_TIMEOUT_MILLIS = 500;
87
88    private final Collator mCollator;
89    private final boolean mHttp;
90    private final PackageManager mPm;
91    private final UsageStatsManager mUsm;
92    private final Map<String, UsageStats> mStats;
93    private final long mCurrentTime;
94    private final long mSinceTime;
95    private final LinkedHashMap<ComponentName, ResolverTarget> mTargetsDict = new LinkedHashMap<>();
96    private final String mReferrerPackage;
97    private final Object mLock = new Object();
98    private ArrayList<ResolverTarget> mTargets;
99    private String mContentType;
100    private String[] mAnnotations;
101    private String mAction;
102    private IResolverRankerService mRanker;
103    private ResolverRankerServiceConnection mConnection;
104    private AfterCompute mAfterCompute;
105    private Context mContext;
106    private CountDownLatch mConnectSignal;
107
108    private final Handler mHandler = new Handler(Looper.getMainLooper()) {
109        public void handleMessage(Message msg) {
110            switch (msg.what) {
111                case RESOLVER_RANKER_SERVICE_RESULT:
112                    if (DEBUG) {
113                        Log.d(TAG, "RESOLVER_RANKER_SERVICE_RESULT");
114                    }
115                    if (mHandler.hasMessages(RESOLVER_RANKER_RESULT_TIMEOUT)) {
116                        if (msg.obj != null) {
117                            final List<ResolverTarget> receivedTargets =
118                                    (List<ResolverTarget>) msg.obj;
119                            if (receivedTargets != null && mTargets != null
120                                    && receivedTargets.size() == mTargets.size()) {
121                                final int size = mTargets.size();
122                                for (int i = 0; i < size; ++i) {
123                                    mTargets.get(i).setSelectProbability(
124                                            receivedTargets.get(i).getSelectProbability());
125                                }
126                            } else {
127                                Log.e(TAG, "Sizes of sent and received ResolverTargets diff.");
128                            }
129                        } else {
130                            Log.e(TAG, "Receiving null prediction results.");
131                        }
132                        mHandler.removeMessages(RESOLVER_RANKER_RESULT_TIMEOUT);
133                        mAfterCompute.afterCompute();
134                    }
135                    break;
136
137                case RESOLVER_RANKER_RESULT_TIMEOUT:
138                    if (DEBUG) {
139                        Log.d(TAG, "RESOLVER_RANKER_RESULT_TIMEOUT; unbinding services");
140                    }
141                    mHandler.removeMessages(RESOLVER_RANKER_SERVICE_RESULT);
142                    mAfterCompute.afterCompute();
143                    break;
144
145                default:
146                    super.handleMessage(msg);
147            }
148        }
149    };
150
151    public interface AfterCompute {
152        public void afterCompute ();
153    }
154
155    public ResolverComparator(Context context, Intent intent, String referrerPackage,
156                              AfterCompute afterCompute) {
157        mCollator = Collator.getInstance(context.getResources().getConfiguration().locale);
158        String scheme = intent.getScheme();
159        mHttp = "http".equals(scheme) || "https".equals(scheme);
160        mReferrerPackage = referrerPackage;
161        mAfterCompute = afterCompute;
162        mContext = context;
163
164        mPm = context.getPackageManager();
165        mUsm = (UsageStatsManager) context.getSystemService(Context.USAGE_STATS_SERVICE);
166
167        mCurrentTime = System.currentTimeMillis();
168        mSinceTime = mCurrentTime - USAGE_STATS_PERIOD;
169        mStats = mUsm.queryAndAggregateUsageStats(mSinceTime, mCurrentTime);
170        mContentType = intent.getType();
171        getContentAnnotations(intent);
172        mAction = intent.getAction();
173    }
174
175    // get annotations of content from intent.
176    public void getContentAnnotations(Intent intent) {
177        ArrayList<String> annotations = intent.getStringArrayListExtra(
178                Intent.EXTRA_CONTENT_ANNOTATIONS);
179        if (annotations != null) {
180            int size = annotations.size();
181            if (size > NUM_OF_TOP_ANNOTATIONS_TO_USE) {
182                size = NUM_OF_TOP_ANNOTATIONS_TO_USE;
183            }
184            mAnnotations = new String[size];
185            for (int i = 0; i < size; i++) {
186                mAnnotations[i] = annotations.get(i);
187            }
188        }
189    }
190
191    public void setCallBack(AfterCompute afterCompute) {
192        mAfterCompute = afterCompute;
193    }
194
195    // compute features for each target according to usage stats of targets.
196    public void compute(List<ResolvedComponentInfo> targets) {
197        reset();
198
199        final long recentSinceTime = mCurrentTime - RECENCY_TIME_PERIOD;
200
201        float mostRecencyScore = 1.0f;
202        float mostTimeSpentScore = 1.0f;
203        float mostLaunchScore = 1.0f;
204        float mostChooserScore = 1.0f;
205
206        for (ResolvedComponentInfo target : targets) {
207            final ResolverTarget resolverTarget = new ResolverTarget();
208            mTargetsDict.put(target.name, resolverTarget);
209            final UsageStats pkStats = mStats.get(target.name.getPackageName());
210            if (pkStats != null) {
211                // Only count recency for apps that weren't the caller
212                // since the caller is always the most recent.
213                // Persistent processes muck this up, so omit them too.
214                if (!target.name.getPackageName().equals(mReferrerPackage)
215                        && !isPersistentProcess(target)) {
216                    final float recencyScore =
217                            (float) Math.max(pkStats.getLastTimeUsed() - recentSinceTime, 0);
218                    resolverTarget.setRecencyScore(recencyScore);
219                    if (recencyScore > mostRecencyScore) {
220                        mostRecencyScore = recencyScore;
221                    }
222                }
223                final float timeSpentScore = (float) pkStats.getTotalTimeInForeground();
224                resolverTarget.setTimeSpentScore(timeSpentScore);
225                if (timeSpentScore > mostTimeSpentScore) {
226                    mostTimeSpentScore = timeSpentScore;
227                }
228                final float launchScore = (float) pkStats.mLaunchCount;
229                resolverTarget.setLaunchScore(launchScore);
230                if (launchScore > mostLaunchScore) {
231                    mostLaunchScore = launchScore;
232                }
233
234                float chooserScore = 0.0f;
235                if (pkStats.mChooserCounts != null && mAction != null
236                        && pkStats.mChooserCounts.get(mAction) != null) {
237                    chooserScore = (float) pkStats.mChooserCounts.get(mAction)
238                            .getOrDefault(mContentType, 0);
239                    if (mAnnotations != null) {
240                        final int size = mAnnotations.length;
241                        for (int i = 0; i < size; i++) {
242                            chooserScore += (float) pkStats.mChooserCounts.get(mAction)
243                                    .getOrDefault(mAnnotations[i], 0);
244                        }
245                    }
246                }
247                if (DEBUG) {
248                    if (mAction == null) {
249                        Log.d(TAG, "Action type is null");
250                    } else {
251                        Log.d(TAG, "Chooser Count of " + mAction + ":" +
252                                target.name.getPackageName() + " is " +
253                                Float.toString(chooserScore));
254                    }
255                }
256                resolverTarget.setChooserScore(chooserScore);
257                if (chooserScore > mostChooserScore) {
258                    mostChooserScore = chooserScore;
259                }
260            }
261        }
262
263        if (DEBUG) {
264            Log.d(TAG, "compute - mostRecencyScore: " + mostRecencyScore
265                    + " mostTimeSpentScore: " + mostTimeSpentScore
266                    + " mostLaunchScore: " + mostLaunchScore
267                    + " mostChooserScore: " + mostChooserScore);
268        }
269
270        mTargets = new ArrayList<>(mTargetsDict.values());
271        for (ResolverTarget target : mTargets) {
272            final float recency = target.getRecencyScore() / mostRecencyScore;
273            setFeatures(target, recency * recency * RECENCY_MULTIPLIER,
274                    target.getLaunchScore() / mostLaunchScore,
275                    target.getTimeSpentScore() / mostTimeSpentScore,
276                    target.getChooserScore() / mostChooserScore);
277            addDefaultSelectProbability(target);
278            if (DEBUG) {
279                Log.d(TAG, "Scores: " + target);
280            }
281        }
282        predictSelectProbabilities(mTargets);
283    }
284
285    @Override
286    public int compare(ResolvedComponentInfo lhsp, ResolvedComponentInfo rhsp) {
287        final ResolveInfo lhs = lhsp.getResolveInfoAt(0);
288        final ResolveInfo rhs = rhsp.getResolveInfoAt(0);
289
290        // We want to put the one targeted to another user at the end of the dialog.
291        if (lhs.targetUserId != UserHandle.USER_CURRENT) {
292            return rhs.targetUserId != UserHandle.USER_CURRENT ? 0 : 1;
293        }
294        if (rhs.targetUserId != UserHandle.USER_CURRENT) {
295            return -1;
296        }
297
298        if (mHttp) {
299            // Special case: we want filters that match URI paths/schemes to be
300            // ordered before others.  This is for the case when opening URIs,
301            // to make native apps go above browsers.
302            final boolean lhsSpecific = ResolverActivity.isSpecificUriMatch(lhs.match);
303            final boolean rhsSpecific = ResolverActivity.isSpecificUriMatch(rhs.match);
304            if (lhsSpecific != rhsSpecific) {
305                return lhsSpecific ? -1 : 1;
306            }
307        }
308
309        final boolean lPinned = lhsp.isPinned();
310        final boolean rPinned = rhsp.isPinned();
311
312        if (lPinned && !rPinned) {
313            return -1;
314        } else if (!lPinned && rPinned) {
315            return 1;
316        }
317
318        // Pinned items stay stable within a normal lexical sort and ignore scoring.
319        if (!lPinned && !rPinned) {
320            if (mStats != null) {
321                final ResolverTarget lhsTarget = mTargetsDict.get(new ComponentName(
322                        lhs.activityInfo.packageName, lhs.activityInfo.name));
323                final ResolverTarget rhsTarget = mTargetsDict.get(new ComponentName(
324                        rhs.activityInfo.packageName, rhs.activityInfo.name));
325
326                final int selectProbabilityDiff = Float.compare(
327                        rhsTarget.getSelectProbability(), lhsTarget.getSelectProbability());
328
329                if (selectProbabilityDiff != 0) {
330                    return selectProbabilityDiff > 0 ? 1 : -1;
331                }
332            }
333        }
334
335        CharSequence  sa = lhs.loadLabel(mPm);
336        if (sa == null) sa = lhs.activityInfo.name;
337        CharSequence  sb = rhs.loadLabel(mPm);
338        if (sb == null) sb = rhs.activityInfo.name;
339
340        return mCollator.compare(sa.toString().trim(), sb.toString().trim());
341    }
342
343    public float getScore(ComponentName name) {
344        final ResolverTarget target = mTargetsDict.get(name);
345        if (target != null) {
346            return target.getSelectProbability();
347        }
348        return 0;
349    }
350
351    public void updateChooserCounts(String packageName, int userId, String action) {
352        if (mUsm != null) {
353            mUsm.reportChooserSelection(packageName, userId, mContentType, mAnnotations, action);
354        }
355    }
356
357    // update ranking model when the connection to it is valid.
358    public void updateModel(ComponentName componentName) {
359        synchronized (mLock) {
360            if (mRanker != null) {
361                try {
362                    int selectedPos = new ArrayList<ComponentName>(mTargetsDict.keySet())
363                            .indexOf(componentName);
364                    if (selectedPos > 0) {
365                        mRanker.train(mTargets, selectedPos);
366                    } else {
367                        if (DEBUG) {
368                            Log.d(TAG, "Selected a unknown component: " + componentName);
369                        }
370                    }
371                } catch (RemoteException e) {
372                    Log.e(TAG, "Error in Train: " + e);
373                }
374            } else {
375                if (DEBUG) {
376                    Log.d(TAG, "Ranker is null; skip updateModel.");
377                }
378            }
379        }
380    }
381
382    // unbind the service and clear unhandled messges.
383    public void destroy() {
384        mHandler.removeMessages(RESOLVER_RANKER_SERVICE_RESULT);
385        mHandler.removeMessages(RESOLVER_RANKER_RESULT_TIMEOUT);
386        if (mConnection != null) {
387            mContext.unbindService(mConnection);
388            mConnection.destroy();
389        }
390        if (DEBUG) {
391            Log.d(TAG, "Unbinded Resolver Ranker.");
392        }
393    }
394
395    // connect to a ranking service.
396    private void initRanker(Context context) {
397        synchronized (mLock) {
398            if (mConnection != null && mRanker != null) {
399                if (DEBUG) {
400                    Log.d(TAG, "Ranker still exists; reusing the existing one.");
401                }
402                return;
403            }
404        }
405        Intent intent = resolveRankerService();
406        if (intent == null) {
407            return;
408        }
409        mConnectSignal = new CountDownLatch(1);
410        mConnection = new ResolverRankerServiceConnection(mConnectSignal);
411        context.bindServiceAsUser(intent, mConnection, Context.BIND_AUTO_CREATE, UserHandle.SYSTEM);
412    }
413
414    // resolve the service for ranking.
415    private Intent resolveRankerService() {
416        Intent intent = new Intent(ResolverRankerService.SERVICE_INTERFACE);
417        final List<ResolveInfo> resolveInfos = mPm.queryIntentServices(intent, 0);
418        for (ResolveInfo resolveInfo : resolveInfos) {
419            if (resolveInfo == null || resolveInfo.serviceInfo == null
420                    || resolveInfo.serviceInfo.applicationInfo == null) {
421                if (DEBUG) {
422                    Log.d(TAG, "Failed to retrieve a ranker: " + resolveInfo);
423                }
424                continue;
425            }
426            ComponentName componentName = new ComponentName(
427                    resolveInfo.serviceInfo.applicationInfo.packageName,
428                    resolveInfo.serviceInfo.name);
429            try {
430                final String perm = mPm.getServiceInfo(componentName, 0).permission;
431                if (!ResolverRankerService.BIND_PERMISSION.equals(perm)) {
432                    Log.w(TAG, "ResolverRankerService " + componentName + " does not require"
433                            + " permission " + ResolverRankerService.BIND_PERMISSION
434                            + " - this service will not be queried for ResolverComparator."
435                            + " add android:permission=\""
436                            + ResolverRankerService.BIND_PERMISSION + "\""
437                            + " to the <service> tag for " + componentName
438                            + " in the manifest.");
439                    continue;
440                }
441                if (PackageManager.PERMISSION_GRANTED != mPm.checkPermission(
442                        ResolverRankerService.HOLD_PERMISSION,
443                        resolveInfo.serviceInfo.packageName)) {
444                    Log.w(TAG, "ResolverRankerService " + componentName + " does not hold"
445                            + " permission " + ResolverRankerService.HOLD_PERMISSION
446                            + " - this service will not be queried for ResolverComparator.");
447                    continue;
448                }
449            } catch (NameNotFoundException e) {
450                Log.e(TAG, "Could not look up service " + componentName
451                        + "; component name not found");
452                continue;
453            }
454            if (DEBUG) {
455                Log.d(TAG, "Succeeded to retrieve a ranker: " + componentName);
456            }
457            intent.setComponent(componentName);
458            return intent;
459        }
460        return null;
461    }
462
463    // set a watchdog, to avoid waiting for ranking service for too long.
464    private void startWatchDog(int timeOutLimit) {
465        if (DEBUG) Log.d(TAG, "Setting watchdog timer for " + timeOutLimit + "ms");
466        if (mHandler == null) {
467            Log.d(TAG, "Error: Handler is Null; Needs to be initialized.");
468        }
469        mHandler.sendEmptyMessageDelayed(RESOLVER_RANKER_RESULT_TIMEOUT, timeOutLimit);
470    }
471
472    private class ResolverRankerServiceConnection implements ServiceConnection {
473        private final CountDownLatch mConnectSignal;
474
475        public ResolverRankerServiceConnection(CountDownLatch connectSignal) {
476            mConnectSignal = connectSignal;
477        }
478
479        public final IResolverRankerResult resolverRankerResult =
480                new IResolverRankerResult.Stub() {
481            @Override
482            public void sendResult(List<ResolverTarget> targets) throws RemoteException {
483                if (DEBUG) {
484                    Log.d(TAG, "Sending Result back to Resolver: " + targets);
485                }
486                synchronized (mLock) {
487                    final Message msg = Message.obtain();
488                    msg.what = RESOLVER_RANKER_SERVICE_RESULT;
489                    msg.obj = targets;
490                    mHandler.sendMessage(msg);
491                }
492            }
493        };
494
495        @Override
496        public void onServiceConnected(ComponentName name, IBinder service) {
497            if (DEBUG) {
498                Log.d(TAG, "onServiceConnected: " + name);
499            }
500            synchronized (mLock) {
501                mRanker = IResolverRankerService.Stub.asInterface(service);
502                mConnectSignal.countDown();
503            }
504        }
505
506        @Override
507        public void onServiceDisconnected(ComponentName name) {
508            if (DEBUG) {
509                Log.d(TAG, "onServiceDisconnected: " + name);
510            }
511            synchronized (mLock) {
512                destroy();
513            }
514        }
515
516        public void destroy() {
517            synchronized (mLock) {
518                mRanker = null;
519            }
520        }
521    }
522
523    private void reset() {
524        mTargetsDict.clear();
525        mTargets = null;
526        startWatchDog(WATCHDOG_TIMEOUT_MILLIS);
527        initRanker(mContext);
528    }
529
530    // predict select probabilities if ranking service is valid.
531    private void predictSelectProbabilities(List<ResolverTarget> targets) {
532        if (mConnection == null) {
533            if (DEBUG) {
534                Log.d(TAG, "Has not found valid ResolverRankerService; Skip Prediction");
535            }
536            return;
537        } else {
538            try {
539                mConnectSignal.await(CONNECTION_COST_TIMEOUT_MILLIS, TimeUnit.MILLISECONDS);
540                synchronized (mLock) {
541                    if (mRanker != null) {
542                        mRanker.predict(targets, mConnection.resolverRankerResult);
543                        return;
544                    } else {
545                        if (DEBUG) {
546                            Log.d(TAG, "Ranker has not been initialized; skip predict.");
547                        }
548                    }
549                }
550            } catch (InterruptedException e) {
551                Log.e(TAG, "Error in Wait for Service Connection.");
552            } catch (RemoteException e) {
553                Log.e(TAG, "Error in Predict: " + e);
554            }
555        }
556        mAfterCompute.afterCompute();
557    }
558
559    // adds select prob as the default values, according to a pre-trained Logistic Regression model.
560    private void addDefaultSelectProbability(ResolverTarget target) {
561        float sum = 2.5543f * target.getLaunchScore() + 2.8412f * target.getTimeSpentScore() +
562                0.269f * target.getRecencyScore() + 4.2222f * target.getChooserScore();
563        target.setSelectProbability((float) (1.0 / (1.0 + Math.exp(1.6568f - sum))));
564    }
565
566    // sets features for each target
567    private void setFeatures(ResolverTarget target, float recencyScore, float launchScore,
568                             float timeSpentScore, float chooserScore) {
569        target.setRecencyScore(recencyScore);
570        target.setLaunchScore(launchScore);
571        target.setTimeSpentScore(timeSpentScore);
572        target.setChooserScore(chooserScore);
573    }
574
575    static boolean isPersistentProcess(ResolvedComponentInfo rci) {
576        if (rci != null && rci.getCount() > 0) {
577            return (rci.getResolveInfoAt(0).activityInfo.applicationInfo.flags &
578                    ApplicationInfo.FLAG_PERSISTENT) != 0;
579        }
580        return false;
581    }
582}
583