core/java/android/net/Uri.java

   1 /*
   2  * Copyright (C) 2007 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 package android.net;
  18
  19 import android.os.Environment;
  20 import android.os.Parcel;
  21 import android.os.Parcelable;
  22 import android.os.StrictMode;
  23 import android.util.Log;
  24
  25 import java.io.File;
  26 import java.io.IOException;
  27 import java.io.UnsupportedEncodingException;
  28 import java.net.URLEncoder;
  29 import java.nio.charset.StandardCharsets;
  30 import java.util.AbstractList;
  31 import java.util.ArrayList;
  32 import java.util.Collections;
  33 import java.util.LinkedHashSet;
  34 import java.util.List;
  35 import java.util.Locale;
  36 import java.util.Objects;
  37 import java.util.RandomAccess;
  38 import java.util.Set;
  39
  40 import libcore.net.UriCodec;
  41
  42 /**
  43  * Immutable URI reference. A URI reference includes a URI and a fragment, the
  44  * component of the URI following a '#'. Builds and parses URI references
  45  * which conform to
  46  * <a href="http://www.faqs.org/rfcs/rfc2396.html">RFC 2396</a>.
  47  *
  48  * <p>In the interest of performance, this class performs little to no
  49  * validation. Behavior is undefined for invalid input. This class is very
  50  * forgiving--in the face of invalid input, it will return garbage
  51  * rather than throw an exception unless otherwise specified.
  52  */
  53 public abstract class Uri implements Parcelable, Comparable<Uri> {
  54
  55     /*
  56
  57     This class aims to do as little up front work as possible. To accomplish
  58     that, we vary the implementation depending on what the user passes in.
  59     For example, we have one implementation if the user passes in a
  60     URI string (StringUri) and another if the user passes in the
  61     individual components (OpaqueUri).
  62
  63     *Concurrency notes*: Like any truly immutable object, this class is safe
  64     for concurrent use. This class uses a caching pattern in some places where
  65     it doesn't use volatile or synchronized. This is safe to do with ints
  66     because getting or setting an int is atomic. It's safe to do with a String
  67     because the internal fields are final and the memory model guarantees other
  68     threads won't see a partially initialized instance. We are not guaranteed
  69     that some threads will immediately see changes from other threads on
  70     certain platforms, but we don't mind if those threads reconstruct the
  71     cached result. As a result, we get thread safe caching with no concurrency
  72     overhead, which means the most common case, access from a single thread,
  73     is as fast as possible.
  74
  75     From the Java Language spec.:
  76
  77     "17.5 Final Field Semantics
  78
  79     ... when the object is seen by another thread, that thread will always
  80     see the correctly constructed version of that object's final fields.
  81     It will also see versions of any object or array referenced by
  82     those final fields that are at least as up-to-date as the final fields
  83     are."
  84
  85     In that same vein, all non-transient fields within Uri
  86     implementations should be final and immutable so as to ensure true
  87     immutability for clients even when they don't use proper concurrency
  88     control.
  89
  90     For reference, from RFC 2396:
  91
  92     "4.3. Parsing a URI Reference
  93
  94        A URI reference is typically parsed according to the four main
  95        components and fragment identifier in order to determine what
  96        components are present and whether the reference is relative or
  97        absolute.  The individual components are then parsed for their
  98        subparts and, if not opaque, to verify their validity.
  99
 100        Although the BNF defines what is allowed in each component, it is
 101        ambiguous in terms of differentiating between an authority component
 102        and a path component that begins with two slash characters.  The
 103        greedy algorithm is used for disambiguation: the left-most matching
 104        rule soaks up as much of the URI reference string as it is capable of
 105        matching.  In other words, the authority component wins."
 106
 107     The "four main components" of a hierarchical URI consist of
 108     <scheme>://<authority><path>?<query>
 109
 110     */
 111
 112     /** Log tag. */
 113     private static final String LOG = Uri.class.getSimpleName();
 114
 115     /**
 116      * NOTE: EMPTY accesses this field during its own initialization, so this
 117      * field *must* be initialized first, or else EMPTY will see a null value!
 118      *
 119      * Placeholder for strings which haven't been cached. This enables us
 120      * to cache null. We intentionally create a new String instance so we can
 121      * compare its identity and there is no chance we will confuse it with
 122      * user data.
 123      */
 124     @SuppressWarnings("RedundantStringConstructorCall")
 125     private static final String NOT_CACHED = new String("NOT CACHED");
 126
 127     /**
 128      * The empty URI, equivalent to "".
 129      */
 130     public static final Uri EMPTY = new HierarchicalUri(null, Part.NULL,
 131             PathPart.EMPTY, Part.NULL, Part.NULL);
 132
 133     /**
 134      * Prevents external subclassing.
 135      */
 136     private Uri() {}
 137
 138     /**
 139      * Returns true if this URI is hierarchical like "http://google.com".
 140      * Absolute URIs are hierarchical if the scheme-specific part starts with
 141      * a '/'. Relative URIs are always hierarchical.
 142      */
 143     public abstract boolean isHierarchical();
 144
 145     /**
 146      * Returns true if this URI is opaque like "mailto:nobody@google.com". The
 147      * scheme-specific part of an opaque URI cannot start with a '/'.
 148      */
 149     public boolean isOpaque() {
 150         return !isHierarchical();
 151     }
 152
 153     /**
 154      * Returns true if this URI is relative, i.e.&nbsp;if it doesn't contain an
 155      * explicit scheme.
 156      *
 157      * @return true if this URI is relative, false if it's absolute
 158      */
 159     public abstract boolean isRelative();
 160
 161     /**
 162      * Returns true if this URI is absolute, i.e.&nbsp;if it contains an
 163      * explicit scheme.
 164      *
 165      * @return true if this URI is absolute, false if it's relative
 166      */
 167     public boolean isAbsolute() {
 168         return !isRelative();
 169     }
 170
 171     /**
 172      * Gets the scheme of this URI. Example: "http"
 173      *
 174      * @return the scheme or null if this is a relative URI
 175      */
 176     public abstract String getScheme();
 177
 178     /**
 179      * Gets the scheme-specific part of this URI, i.e.&nbsp;everything between
 180      * the scheme separator ':' and the fragment separator '#'. If this is a
 181      * relative URI, this method returns the entire URI. Decodes escaped octets.
 182      *
 183      * <p>Example: "//www.google.com/search?q=android"
 184      *
 185      * @return the decoded scheme-specific-part
 186      */
 187     public abstract String getSchemeSpecificPart();
 188
 189     /**
 190      * Gets the scheme-specific part of this URI, i.e.&nbsp;everything between
 191      * the scheme separator ':' and the fragment separator '#'. If this is a
 192      * relative URI, this method returns the entire URI. Leaves escaped octets
 193      * intact.
 194      *
 195      * <p>Example: "//www.google.com/search?q=android"
 196      *
 197      * @return the decoded scheme-specific-part
 198      */
 199     public abstract String getEncodedSchemeSpecificPart();
 200
 201     /**
 202      * Gets the decoded authority part of this URI. For
 203      * server addresses, the authority is structured as follows:
 204      * {@code [ userinfo '@' ] host [ ':' port ]}
 205      *
 206      * <p>Examples: "google.com", "bob@google.com:80"
 207      *
 208      * @return the authority for this URI or null if not present
 209      */
 210     public abstract String getAuthority();
 211
 212     /**
 213      * Gets the encoded authority part of this URI. For
 214      * server addresses, the authority is structured as follows:
 215      * {@code [ userinfo '@' ] host [ ':' port ]}
 216      *
 217      * <p>Examples: "google.com", "bob@google.com:80"
 218      *
 219      * @return the authority for this URI or null if not present
 220      */
 221     public abstract String getEncodedAuthority();
 222
 223     /**
 224      * Gets the decoded user information from the authority.
 225      * For example, if the authority is "nobody@google.com", this method will
 226      * return "nobody".
 227      *
 228      * @return the user info for this URI or null if not present
 229      */
 230     public abstract String getUserInfo();
 231
 232     /**
 233      * Gets the encoded user information from the authority.
 234      * For example, if the authority is "nobody@google.com", this method will
 235      * return "nobody".
 236      *
 237      * @return the user info for this URI or null if not present
 238      */
 239     public abstract String getEncodedUserInfo();
 240
 241     /**
 242      * Gets the encoded host from the authority for this URI. For example,
 243      * if the authority is "bob@google.com", this method will return
 244      * "google.com".
 245      *
 246      * @return the host for this URI or null if not present
 247      */
 248     public abstract String getHost();
 249
 250     /**
 251      * Gets the port from the authority for this URI. For example,
 252      * if the authority is "google.com:80", this method will return 80.
 253      *
 254      * @return the port for this URI or -1 if invalid or not present
 255      */
 256     public abstract int getPort();
 257
 258     /**
 259      * Gets the decoded path.
 260      *
 261      * @return the decoded path, or null if this is not a hierarchical URI
 262      * (like "mailto:nobody@google.com") or the URI is invalid
 263      */
 264     public abstract String getPath();
 265
 266     /**
 267      * Gets the encoded path.
 268      *
 269      * @return the encoded path, or null if this is not a hierarchical URI
 270      * (like "mailto:nobody@google.com") or the URI is invalid
 271      */
 272     public abstract String getEncodedPath();
 273
 274     /**
 275      * Gets the decoded query component from this URI. The query comes after
 276      * the query separator ('?') and before the fragment separator ('#'). This
 277      * method would return "q=android" for
 278      * "http://www.google.com/search?q=android".
 279      *
 280      * @return the decoded query or null if there isn't one
 281      */
 282     public abstract String getQuery();
 283
 284     /**
 285      * Gets the encoded query component from this URI. The query comes after
 286      * the query separator ('?') and before the fragment separator ('#'). This
 287      * method would return "q=android" for
 288      * "http://www.google.com/search?q=android".
 289      *
 290      * @return the encoded query or null if there isn't one
 291      */
 292     public abstract String getEncodedQuery();
 293
 294     /**
 295      * Gets the decoded fragment part of this URI, everything after the '#'.
 296      *
 297      * @return the decoded fragment or null if there isn't one
 298      */
 299     public abstract String getFragment();
 300
 301     /**
 302      * Gets the encoded fragment part of this URI, everything after the '#'.
 303      *
 304      * @return the encoded fragment or null if there isn't one
 305      */
 306     public abstract String getEncodedFragment();
 307
 308     /**
 309      * Gets the decoded path segments.
 310      *
 311      * @return decoded path segments, each without a leading or trailing '/'
 312      */
 313     public abstract List<String> getPathSegments();
 314
 315     /**
 316      * Gets the decoded last segment in the path.
 317      *
 318      * @return the decoded last segment or null if the path is empty
 319      */
 320     public abstract String getLastPathSegment();
 321
 322     /**
 323      * Compares this Uri to another object for equality. Returns true if the
 324      * encoded string representations of this Uri and the given Uri are
 325      * equal. Case counts. Paths are not normalized. If one Uri specifies a
 326      * default port explicitly and the other leaves it implicit, they will not
 327      * be considered equal.
 328      */
 329     public boolean equals(Object o) {
 330         if (!(o instanceof Uri)) {
 331             return false;
 332         }
 333
 334         Uri other = (Uri) o;
 335
 336         return toString().equals(other.toString());
 337     }
 338
 339     /**
 340      * Hashes the encoded string represention of this Uri consistently with
 341      * {@link #equals(Object)}.
 342      */
 343     public int hashCode() {
 344         return toString().hashCode();
 345     }
 346
 347     /**
 348      * Compares the string representation of this Uri with that of
 349      * another.
 350      */
 351     public int compareTo(Uri other) {
 352         return toString().compareTo(other.toString());
 353     }
 354
 355     /**
 356      * Returns the encoded string representation of this URI.
 357      * Example: "http://google.com/"
 358      */
 359     public abstract String toString();
 360
 361     /**
 362      * Return a string representation of the URI that is safe to print
 363      * to logs and other places where PII should be avoided.
 364      * @hide
 365      */
 366     public String toSafeString() {
 367         String scheme = getScheme();
 368         String ssp = getSchemeSpecificPart();
 369         if (scheme != null) {
 370             if (scheme.equalsIgnoreCase("tel") || scheme.equalsIgnoreCase("sip")
 371                     || scheme.equalsIgnoreCase("sms") || scheme.equalsIgnoreCase("smsto")
 372                     || scheme.equalsIgnoreCase("mailto")) {
 373                 StringBuilder builder = new StringBuilder(64);
 374                 builder.append(scheme);
 375                 builder.append(':');
 376                 if (ssp != null) {
 377                     for (int i=0; i<ssp.length(); i++) {
 378                         char c = ssp.charAt(i);
 379                         if (c == '-' || c == '@' || c == '.') {
 380                             builder.append(c);
 381                         } else {
 382                             builder.append('x');
 383                         }
 384                     }
 385                 }
 386                 return builder.toString();
 387             } else if (scheme.equalsIgnoreCase("http") || scheme.equalsIgnoreCase("https")
 388                     || scheme.equalsIgnoreCase("ftp")) {
 389                 ssp = "//" + ((getHost() != null) ? getHost() : "")
 390                         + ((getPort() != -1) ? (":" + getPort()) : "")
 391                         + "/...";
 392             }
 393         }
 394         // Not a sensitive scheme, but let's still be conservative about
 395         // the data we include -- only the ssp, not the query params or
 396         // fragment, because those can often have sensitive info.
 397         StringBuilder builder = new StringBuilder(64);
 398         if (scheme != null) {
 399             builder.append(scheme);
 400             builder.append(':');
 401         }
 402         if (ssp != null) {
 403             builder.append(ssp);
 404         }
 405         return builder.toString();
 406     }
 407
 408     /**
 409      * Constructs a new builder, copying the attributes from this Uri.
 410      */
 411     public abstract Builder buildUpon();
 412
 413     /** Index of a component which was not found. */
 414     private final static int NOT_FOUND = -1;
 415
 416     /** Placeholder value for an index which hasn't been calculated yet. */
 417     private final static int NOT_CALCULATED = -2;
 418
 419     /**
 420      * Error message presented when a user tries to treat an opaque URI as
 421      * hierarchical.
 422      */
 423     private static final String NOT_HIERARCHICAL
 424             = "This isn't a hierarchical URI.";
 425
 426     /** Default encoding. */
 427     private static final String DEFAULT_ENCODING = "UTF-8";
 428
 429     /**
 430      * Creates a Uri which parses the given encoded URI string.
 431      *
 432      * @param uriString an RFC 2396-compliant, encoded URI
 433      * @throws NullPointerException if uriString is null
 434      * @return Uri for this given uri string
 435      */
 436     public static Uri parse(String uriString) {
 437         return new StringUri(uriString);
 438     }
 439
 440     /**
 441      * Creates a Uri from a file. The URI has the form
 442      * "file://<absolute path>". Encodes path characters with the exception of
 443      * '/'.
 444      *
 445      * <p>Example: "file:///tmp/android.txt"
 446      *
 447      * @throws NullPointerException if file is null
 448      * @return a Uri for the given file
 449      */
 450     public static Uri fromFile(File file) {
 451         if (file == null) {
 452             throw new NullPointerException("file");
 453         }
 454
 455         PathPart path = PathPart.fromDecoded(file.getAbsolutePath());
 456         return new HierarchicalUri(
 457                 "file", Part.EMPTY, path, Part.NULL, Part.NULL);
 458     }
 459
 460     /**
 461      * An implementation which wraps a String URI. This URI can be opaque or
 462      * hierarchical, but we extend AbstractHierarchicalUri in case we need
 463      * the hierarchical functionality.
 464      */
 465     private static class StringUri extends AbstractHierarchicalUri {
 466
 467         /** Used in parcelling. */
 468         static final int TYPE_ID = 1;
 469
 470         /** URI string representation. */
 471         private final String uriString;
 472
 473         private StringUri(String uriString) {
 474             if (uriString == null) {
 475                 throw new NullPointerException("uriString");
 476             }
 477
 478             this.uriString = uriString;
 479         }
 480
 481         static Uri readFrom(Parcel parcel) {
 482             return new StringUri(parcel.readString());
 483         }
 484
 485         public int describeContents() {
 486             return 0;
 487         }
 488
 489         public void writeToParcel(Parcel parcel, int flags) {
 490             parcel.writeInt(TYPE_ID);
 491             parcel.writeString(uriString);
 492         }
 493
 494         /** Cached scheme separator index. */
 495         private volatile int cachedSsi = NOT_CALCULATED;
 496
 497         /** Finds the first ':'. Returns -1 if none found. */
 498         private int findSchemeSeparator() {
 499             return cachedSsi == NOT_CALCULATED
 500                     ? cachedSsi = uriString.indexOf(':')
 501                     : cachedSsi;
 502         }
 503
 504         /** Cached fragment separator index. */
 505         private volatile int cachedFsi = NOT_CALCULATED;
 506
 507         /** Finds the first '#'. Returns -1 if none found. */
 508         private int findFragmentSeparator() {
 509             return cachedFsi == NOT_CALCULATED
 510                     ? cachedFsi = uriString.indexOf('#', findSchemeSeparator())
 511                     : cachedFsi;
 512         }
 513
 514         public boolean isHierarchical() {
 515             int ssi = findSchemeSeparator();
 516
 517             if (ssi == NOT_FOUND) {
 518                 // All relative URIs are hierarchical.
 519                 return true;
 520             }
 521
 522             if (uriString.length() == ssi + 1) {
 523                 // No ssp.
 524                 return false;
 525             }
 526
 527             // If the ssp starts with a '/', this is hierarchical.
 528             return uriString.charAt(ssi + 1) == '/';
 529         }
 530
 531         public boolean isRelative() {
 532             // Note: We return true if the index is 0
 533             return findSchemeSeparator() == NOT_FOUND;
 534         }
 535
 536         private volatile String scheme = NOT_CACHED;
 537
 538         public String getScheme() {
 539             @SuppressWarnings("StringEquality")
 540             boolean cached = (scheme != NOT_CACHED);
 541             return cached ? scheme : (scheme = parseScheme());
 542         }
 543
 544         private String parseScheme() {
 545             int ssi = findSchemeSeparator();
 546             return ssi == NOT_FOUND ? null : uriString.substring(0, ssi);
 547         }
 548
 549         private Part ssp;
 550
 551         private Part getSsp() {
 552             return ssp == null ? ssp = Part.fromEncoded(parseSsp()) : ssp;
 553         }
 554
 555         public String getEncodedSchemeSpecificPart() {
 556             return getSsp().getEncoded();
 557         }
 558
 559         public String getSchemeSpecificPart() {
 560             return getSsp().getDecoded();
 561         }
 562
 563         private String parseSsp() {
 564             int ssi = findSchemeSeparator();
 565             int fsi = findFragmentSeparator();
 566
 567             // Return everything between ssi and fsi.
 568             return fsi == NOT_FOUND
 569                     ? uriString.substring(ssi + 1)
 570                     : uriString.substring(ssi + 1, fsi);
 571         }
 572
 573         private Part authority;
 574
 575         private Part getAuthorityPart() {
 576             if (authority == null) {
 577                 String encodedAuthority
 578                         = parseAuthority(this.uriString, findSchemeSeparator());
 579                 return authority = Part.fromEncoded(encodedAuthority);
 580             }
 581
 582             return authority;
 583         }
 584
 585         public String getEncodedAuthority() {
 586             return getAuthorityPart().getEncoded();
 587         }
 588
 589         public String getAuthority() {
 590             return getAuthorityPart().getDecoded();
 591         }
 592
 593         private PathPart path;
 594
 595         private PathPart getPathPart() {
 596             return path == null
 597                     ? path = PathPart.fromEncoded(parsePath())
 598                     : path;
 599         }
 600
 601         public String getPath() {
 602             return getPathPart().getDecoded();
 603         }
 604
 605         public String getEncodedPath() {
 606             return getPathPart().getEncoded();
 607         }
 608
 609         public List<String> getPathSegments() {
 610             return getPathPart().getPathSegments();
 611         }
 612
 613         private String parsePath() {
 614             String uriString = this.uriString;
 615             int ssi = findSchemeSeparator();
 616
 617             // If the URI is absolute.
 618             if (ssi > -1) {
 619                 // Is there anything after the ':'?
 620                 boolean schemeOnly = ssi + 1 == uriString.length();
 621                 if (schemeOnly) {
 622                     // Opaque URI.
 623                     return null;
 624                 }
 625
 626                 // A '/' after the ':' means this is hierarchical.
 627                 if (uriString.charAt(ssi + 1) != '/') {
 628                     // Opaque URI.
 629                     return null;
 630                 }
 631             } else {
 632                 // All relative URIs are hierarchical.
 633             }
 634
 635             return parsePath(uriString, ssi);
 636         }
 637
 638         private Part query;
 639
 640         private Part getQueryPart() {
 641             return query == null
 642                     ? query = Part.fromEncoded(parseQuery()) : query;
 643         }
 644
 645         public String getEncodedQuery() {
 646             return getQueryPart().getEncoded();
 647         }
 648
 649         private String parseQuery() {
 650             // It doesn't make sense to cache this index. We only ever
 651             // calculate it once.
 652             int qsi = uriString.indexOf('?', findSchemeSeparator());
 653             if (qsi == NOT_FOUND) {
 654                 return null;
 655             }
 656
 657             int fsi = findFragmentSeparator();
 658
 659             if (fsi == NOT_FOUND) {
 660                 return uriString.substring(qsi + 1);
 661             }
 662
 663             if (fsi < qsi) {
 664                 // Invalid.
 665                 return null;
 666             }
 667
 668             return uriString.substring(qsi + 1, fsi);
 669         }
 670
 671         public String getQuery() {
 672             return getQueryPart().getDecoded();
 673         }
 674
 675         private Part fragment;
 676
 677         private Part getFragmentPart() {
 678             return fragment == null
 679                     ? fragment = Part.fromEncoded(parseFragment()) : fragment;
 680         }
 681
 682         public String getEncodedFragment() {
 683             return getFragmentPart().getEncoded();
 684         }
 685
 686         private String parseFragment() {
 687             int fsi = findFragmentSeparator();
 688             return fsi == NOT_FOUND ? null : uriString.substring(fsi + 1);
 689         }
 690
 691         public String getFragment() {
 692             return getFragmentPart().getDecoded();
 693         }
 694
 695         public String toString() {
 696             return uriString;
 697         }
 698
 699         /**
 700          * Parses an authority out of the given URI string.
 701          *
 702          * @param uriString URI string
 703          * @param ssi scheme separator index, -1 for a relative URI
 704          *
 705          * @return the authority or null if none is found
 706          */
 707         static String parseAuthority(String uriString, int ssi) {
 708             int length = uriString.length();
 709
 710             // If "//" follows the scheme separator, we have an authority.
 711             if (length > ssi + 2
 712                     && uriString.charAt(ssi + 1) == '/'
 713                     && uriString.charAt(ssi + 2) == '/') {
 714                 // We have an authority.
 715
 716                 // Look for the start of the path, query, or fragment, or the
 717                 // end of the string.
 718                 int end = ssi + 3;
 719                 LOOP: while (end < length) {
 720                     switch (uriString.charAt(end)) {
 721                         case '/': // Start of path
 722                         case '?': // Start of query
 723                         case '#': // Start of fragment
 724                             break LOOP;
 725                     }
 726                     end++;
 727                 }
 728
 729                 return uriString.substring(ssi + 3, end);
 730             } else {
 731                 return null;
 732             }
 733
 734         }
 735
 736         /**
 737          * Parses a path out of this given URI string.
 738          *
 739          * @param uriString URI string
 740          * @param ssi scheme separator index, -1 for a relative URI
 741          *
 742          * @return the path
 743          */
 744         static String parsePath(String uriString, int ssi) {
 745             int length = uriString.length();
 746
 747             // Find start of path.
 748             int pathStart;
 749             if (length > ssi + 2
 750                     && uriString.charAt(ssi + 1) == '/'
 751                     && uriString.charAt(ssi + 2) == '/') {
 752                 // Skip over authority to path.
 753                 pathStart = ssi + 3;
 754                 LOOP: while (pathStart < length) {
 755                     switch (uriString.charAt(pathStart)) {
 756                         case '?': // Start of query
 757                         case '#': // Start of fragment
 758                             return ""; // Empty path.
 759                         case '/': // Start of path!
 760                             break LOOP;
 761                     }
 762                     pathStart++;
 763                 }
 764             } else {
 765                 // Path starts immediately after scheme separator.
 766                 pathStart = ssi + 1;
 767             }
 768
 769             // Find end of path.
 770             int pathEnd = pathStart;
 771             LOOP: while (pathEnd < length) {
 772                 switch (uriString.charAt(pathEnd)) {
 773                     case '?': // Start of query
 774                     case '#': // Start of fragment
 775                         break LOOP;
 776                 }
 777                 pathEnd++;
 778             }
 779
 780             return uriString.substring(pathStart, pathEnd);
 781         }
 782
 783         public Builder buildUpon() {
 784             if (isHierarchical()) {
 785                 return new Builder()
 786                         .scheme(getScheme())
 787                         .authority(getAuthorityPart())
 788                         .path(getPathPart())
 789                         .query(getQueryPart())
 790                         .fragment(getFragmentPart());
 791             } else {
 792                 return new Builder()
 793                         .scheme(getScheme())
 794                         .opaquePart(getSsp())
 795                         .fragment(getFragmentPart());
 796             }
 797         }
 798     }
 799
 800     /**
 801      * Creates an opaque Uri from the given components. Encodes the ssp
 802      * which means this method cannot be used to create hierarchical URIs.
 803      *
 804      * @param scheme of the URI
 805      * @param ssp scheme-specific-part, everything between the
 806      *  scheme separator (':') and the fragment separator ('#'), which will
 807      *  get encoded
 808      * @param fragment fragment, everything after the '#', null if undefined,
 809      *  will get encoded
 810      *
 811      * @throws NullPointerException if scheme or ssp is null
 812      * @return Uri composed of the given scheme, ssp, and fragment
 813      *
 814      * @see Builder if you don't want the ssp and fragment to be encoded
 815      */
 816     public static Uri fromParts(String scheme, String ssp,
 817             String fragment) {
 818         if (scheme == null) {
 819             throw new NullPointerException("scheme");
 820         }
 821         if (ssp == null) {
 822             throw new NullPointerException("ssp");
 823         }
 824
 825         return new OpaqueUri(scheme, Part.fromDecoded(ssp),
 826                 Part.fromDecoded(fragment));
 827     }
 828
 829     /**
 830      * Opaque URI.
 831      */
 832     private static class OpaqueUri extends Uri {
 833
 834         /** Used in parcelling. */
 835         static final int TYPE_ID = 2;
 836
 837         private final String scheme;
 838         private final Part ssp;
 839         private final Part fragment;
 840
 841         private OpaqueUri(String scheme, Part ssp, Part fragment) {
 842             this.scheme = scheme;
 843             this.ssp = ssp;
 844             this.fragment = fragment == null ? Part.NULL : fragment;
 845         }
 846
 847         static Uri readFrom(Parcel parcel) {
 848             return new OpaqueUri(
 849                 parcel.readString(),
 850                 Part.readFrom(parcel),
 851                 Part.readFrom(parcel)
 852             );
 853         }
 854
 855         public int describeContents() {
 856             return 0;
 857         }
 858
 859         public void writeToParcel(Parcel parcel, int flags) {
 860             parcel.writeInt(TYPE_ID);
 861             parcel.writeString(scheme);
 862             ssp.writeTo(parcel);
 863             fragment.writeTo(parcel);
 864         }
 865
 866         public boolean isHierarchical() {
 867             return false;
 868         }
 869
 870         public boolean isRelative() {
 871             return scheme == null;
 872         }
 873
 874         public String getScheme() {
 875             return this.scheme;
 876         }
 877
 878         public String getEncodedSchemeSpecificPart() {
 879             return ssp.getEncoded();
 880         }
 881
 882         public String getSchemeSpecificPart() {
 883             return ssp.getDecoded();
 884         }
 885
 886         public String getAuthority() {
 887             return null;
 888         }
 889
 890         public String getEncodedAuthority() {
 891             return null;
 892         }
 893
 894         public String getPath() {
 895             return null;
 896         }
 897
 898         public String getEncodedPath() {
 899             return null;
 900         }
 901
 902         public String getQuery() {
 903             return null;
 904         }
 905
 906         public String getEncodedQuery() {
 907             return null;
 908         }
 909
 910         public String getFragment() {
 911             return fragment.getDecoded();
 912         }
 913
 914         public String getEncodedFragment() {
 915             return fragment.getEncoded();
 916         }
 917
 918         public List<String> getPathSegments() {
 919             return Collections.emptyList();
 920         }
 921
 922         public String getLastPathSegment() {
 923             return null;
 924         }
 925
 926         public String getUserInfo() {
 927             return null;
 928         }
 929
 930         public String getEncodedUserInfo() {
 931             return null;
 932         }
 933
 934         public String getHost() {
 935             return null;
 936         }
 937
 938         public int getPort() {
 939             return -1;
 940         }
 941
 942         private volatile String cachedString = NOT_CACHED;
 943
 944         public String toString() {
 945             @SuppressWarnings("StringEquality")
 946             boolean cached = cachedString != NOT_CACHED;
 947             if (cached) {
 948                 return cachedString;
 949             }
 950
 951             StringBuilder sb = new StringBuilder();
 952
 953             sb.append(scheme).append(':');
 954             sb.append(getEncodedSchemeSpecificPart());
 955
 956             if (!fragment.isEmpty()) {
 957                 sb.append('#').append(fragment.getEncoded());
 958             }
 959
 960             return cachedString = sb.toString();
 961         }
 962
 963         public Builder buildUpon() {
 964             return new Builder()
 965                     .scheme(this.scheme)
 966                     .opaquePart(this.ssp)
 967                     .fragment(this.fragment);
 968         }
 969     }
 970
 971     /**
 972      * Wrapper for path segment array.
 973      */
 974     static class PathSegments extends AbstractList<String>
 975             implements RandomAccess {
 976
 977         static final PathSegments EMPTY = new PathSegments(null, 0);
 978
 979         final String[] segments;
 980         final int size;
 981
 982         PathSegments(String[] segments, int size) {
 983             this.segments = segments;
 984             this.size = size;
 985         }
 986
 987         public String get(int index) {
 988             if (index >= size) {
 989                 throw new IndexOutOfBoundsException();
 990             }
 991
 992             return segments[index];
 993         }
 994
 995         public int size() {
 996             return this.size;
 997         }
 998     }
 999
1000     /**
1001      * Builds PathSegments.
1002      */
1003     static class PathSegmentsBuilder {
1004
1005         String[] segments;
1006         int size = 0;
1007
1008         void add(String segment) {
1009             if (segments == null) {
1010                 segments = new String[4];
1011             } else if (size + 1 == segments.length) {
1012                 String[] expanded = new String[segments.length * 2];
1013                 System.arraycopy(segments, 0, expanded, 0, segments.length);
1014                 segments = expanded;
1015             }
1016
1017             segments[size++] = segment;
1018         }
1019
1020         PathSegments build() {
1021             if (segments == null) {
1022                 return PathSegments.EMPTY;
1023             }
1024
1025             try {
1026                 return new PathSegments(segments, size);
1027             } finally {
1028                 // Makes sure this doesn't get reused.
1029                 segments = null;
1030             }
1031         }
1032     }
1033
1034     /**
1035      * Support for hierarchical URIs.
1036      */
1037     private abstract static class AbstractHierarchicalUri extends Uri {
1038
1039         public String getLastPathSegment() {
1040             // TODO: If we haven't parsed all of the segments already, just
1041             // grab the last one directly so we only allocate one string.
1042
1043             List<String> segments = getPathSegments();
1044             int size = segments.size();
1045             if (size == 0) {
1046                 return null;
1047             }
1048             return segments.get(size - 1);
1049         }
1050
1051         private Part userInfo;
1052
1053         private Part getUserInfoPart() {
1054             return userInfo == null
1055                     ? userInfo = Part.fromEncoded(parseUserInfo()) : userInfo;
1056         }
1057
1058         public final String getEncodedUserInfo() {
1059             return getUserInfoPart().getEncoded();
1060         }
1061
1062         private String parseUserInfo() {
1063             String authority = getEncodedAuthority();
1064             if (authority == null) {
1065                 return null;
1066             }
1067
1068             int end = authority.lastIndexOf('@');
1069             return end == NOT_FOUND ? null : authority.substring(0, end);
1070         }
1071
1072         public String getUserInfo() {
1073             return getUserInfoPart().getDecoded();
1074         }
1075
1076         private volatile String host = NOT_CACHED;
1077
1078         public String getHost() {
1079             @SuppressWarnings("StringEquality")
1080             boolean cached = (host != NOT_CACHED);
1081             return cached ? host
1082                     : (host = parseHost());
1083         }
1084
1085         private String parseHost() {
1086             String authority = getEncodedAuthority();
1087             if (authority == null) {
1088                 return null;
1089             }
1090
1091             // Parse out user info and then port.
1092             int userInfoSeparator = authority.lastIndexOf('@');
1093             int portSeparator = authority.indexOf(':', userInfoSeparator);
1094
1095             String encodedHost = portSeparator == NOT_FOUND
1096                     ? authority.substring(userInfoSeparator + 1)
1097                     : authority.substring(userInfoSeparator + 1, portSeparator);
1098
1099             return decode(encodedHost);
1100         }
1101
1102         private volatile int port = NOT_CALCULATED;
1103
1104         public int getPort() {
1105             return port == NOT_CALCULATED
1106                     ? port = parsePort()
1107                     : port;
1108         }
1109
1110         private int parsePort() {
1111             String authority = getEncodedAuthority();
1112             if (authority == null) {
1113                 return -1;
1114             }
1115
1116             // Make sure we look for the port separtor *after* the user info
1117             // separator. We have URLs with a ':' in the user info.
1118             int userInfoSeparator = authority.lastIndexOf('@');
1119             int portSeparator = authority.indexOf(':', userInfoSeparator);
1120
1121             if (portSeparator == NOT_FOUND) {
1122                 return -1;
1123             }
1124
1125             String portString = decode(authority.substring(portSeparator + 1));
1126             try {
1127                 return Integer.parseInt(portString);
1128             } catch (NumberFormatException e) {
1129                 Log.w(LOG, "Error parsing port string.", e);
1130                 return -1;
1131             }
1132         }
1133     }
1134
1135     /**
1136      * Hierarchical Uri.
1137      */
1138     private static class HierarchicalUri extends AbstractHierarchicalUri {
1139
1140         /** Used in parcelling. */
1141         static final int TYPE_ID = 3;
1142
1143         private final String scheme; // can be null
1144         private final Part authority;
1145         private final PathPart path;
1146         private final Part query;
1147         private final Part fragment;
1148
1149         private HierarchicalUri(String scheme, Part authority, PathPart path,
1150                 Part query, Part fragment) {
1151             this.scheme = scheme;
1152             this.authority = Part.nonNull(authority);
1153             this.path = path == null ? PathPart.NULL : path;
1154             this.query = Part.nonNull(query);
1155             this.fragment = Part.nonNull(fragment);
1156         }
1157
1158         static Uri readFrom(Parcel parcel) {
1159             return new HierarchicalUri(
1160                 parcel.readString(),
1161                 Part.readFrom(parcel),
1162                 PathPart.readFrom(parcel),
1163                 Part.readFrom(parcel),
1164                 Part.readFrom(parcel)
1165             );
1166         }
1167
1168         public int describeContents() {
1169             return 0;
1170         }
1171
1172         public void writeToParcel(Parcel parcel, int flags) {
1173             parcel.writeInt(TYPE_ID);
1174             parcel.writeString(scheme);
1175             authority.writeTo(parcel);
1176             path.writeTo(parcel);
1177             query.writeTo(parcel);
1178             fragment.writeTo(parcel);
1179         }
1180
1181         public boolean isHierarchical() {
1182             return true;
1183         }
1184
1185         public boolean isRelative() {
1186             return scheme == null;
1187         }
1188
1189         public String getScheme() {
1190             return scheme;
1191         }
1192
1193         private Part ssp;
1194
1195         private Part getSsp() {
1196             return ssp == null
1197                     ? ssp = Part.fromEncoded(makeSchemeSpecificPart()) : ssp;
1198         }
1199
1200         public String getEncodedSchemeSpecificPart() {
1201             return getSsp().getEncoded();
1202         }
1203
1204         public String getSchemeSpecificPart() {
1205             return getSsp().getDecoded();
1206         }
1207
1208         /**
1209          * Creates the encoded scheme-specific part from its sub parts.
1210          */
1211         private String makeSchemeSpecificPart() {
1212             StringBuilder builder = new StringBuilder();
1213             appendSspTo(builder);
1214             return builder.toString();
1215         }
1216
1217         private void appendSspTo(StringBuilder builder) {
1218             String encodedAuthority = authority.getEncoded();
1219             if (encodedAuthority != null) {
1220                 // Even if the authority is "", we still want to append "//".
1221                 builder.append("//").append(encodedAuthority);
1222             }
1223
1224             String encodedPath = path.getEncoded();
1225             if (encodedPath != null) {
1226                 builder.append(encodedPath);
1227             }
1228
1229             if (!query.isEmpty()) {
1230                 builder.append('?').append(query.getEncoded());
1231             }
1232         }
1233
1234         public String getAuthority() {
1235             return this.authority.getDecoded();
1236         }
1237
1238         public String getEncodedAuthority() {
1239             return this.authority.getEncoded();
1240         }
1241
1242         public String getEncodedPath() {
1243             return this.path.getEncoded();
1244         }
1245
1246         public String getPath() {
1247             return this.path.getDecoded();
1248         }
1249
1250         public String getQuery() {
1251             return this.query.getDecoded();
1252         }
1253
1254         public String getEncodedQuery() {
1255             return this.query.getEncoded();
1256         }
1257
1258         public String getFragment() {
1259             return this.fragment.getDecoded();
1260         }
1261
1262         public String getEncodedFragment() {
1263             return this.fragment.getEncoded();
1264         }
1265
1266         public List<String> getPathSegments() {
1267             return this.path.getPathSegments();
1268         }
1269
1270         private volatile String uriString = NOT_CACHED;
1271
1272         @Override
1273         public String toString() {
1274             @SuppressWarnings("StringEquality")
1275             boolean cached = (uriString != NOT_CACHED);
1276             return cached ? uriString
1277                     : (uriString = makeUriString());
1278         }
1279
1280         private String makeUriString() {
1281             StringBuilder builder = new StringBuilder();
1282
1283             if (scheme != null) {
1284                 builder.append(scheme).append(':');
1285             }
1286
1287             appendSspTo(builder);
1288
1289             if (!fragment.isEmpty()) {
1290                 builder.append('#').append(fragment.getEncoded());
1291             }
1292
1293             return builder.toString();
1294         }
1295
1296         public Builder buildUpon() {
1297             return new Builder()
1298                     .scheme(scheme)
1299                     .authority(authority)
1300                     .path(path)
1301                     .query(query)
1302                     .fragment(fragment);
1303         }
1304     }
1305
1306     /**
1307      * Helper class for building or manipulating URI references. Not safe for
1308      * concurrent use.
1309      *
1310      * <p>An absolute hierarchical URI reference follows the pattern:
1311      * {@code <scheme>://<authority><absolute path>?<query>#<fragment>}
1312      *
1313      * <p>Relative URI references (which are always hierarchical) follow one
1314      * of two patterns: {@code <relative or absolute path>?<query>#<fragment>}
1315      * or {@code //<authority><absolute path>?<query>#<fragment>}
1316      *
1317      * <p>An opaque URI follows this pattern:
1318      * {@code <scheme>:<opaque part>#<fragment>}
1319      *
1320      * <p>Use {@link Uri#buildUpon()} to obtain a builder representing an existing URI.
1321      */
1322     public static final class Builder {
1323
1324         private String scheme;
1325         private Part opaquePart;
1326         private Part authority;
1327         private PathPart path;
1328         private Part query;
1329         private Part fragment;
1330
1331         /**
1332          * Constructs a new Builder.
1333          */
1334         public Builder() {}
1335
1336         /**
1337          * Sets the scheme.
1338          *
1339          * @param scheme name or {@code null} if this is a relative Uri
1340          */
1341         public Builder scheme(String scheme) {
1342             this.scheme = scheme;
1343             return this;
1344         }
1345
1346         Builder opaquePart(Part opaquePart) {
1347             this.opaquePart = opaquePart;
1348             return this;
1349         }
1350
1351         /**
1352          * Encodes and sets the given opaque scheme-specific-part.
1353          *
1354          * @param opaquePart decoded opaque part
1355          */
1356         public Builder opaquePart(String opaquePart) {
1357             return opaquePart(Part.fromDecoded(opaquePart));
1358         }
1359
1360         /**
1361          * Sets the previously encoded opaque scheme-specific-part.
1362          *
1363          * @param opaquePart encoded opaque part
1364          */
1365         public Builder encodedOpaquePart(String opaquePart) {
1366             return opaquePart(Part.fromEncoded(opaquePart));
1367         }
1368
1369         Builder authority(Part authority) {
1370             // This URI will be hierarchical.
1371             this.opaquePart = null;
1372
1373             this.authority = authority;
1374             return this;
1375         }
1376
1377         /**
1378          * Encodes and sets the authority.
1379          */
1380         public Builder authority(String authority) {
1381             return authority(Part.fromDecoded(authority));
1382         }
1383
1384         /**
1385          * Sets the previously encoded authority.
1386          */
1387         public Builder encodedAuthority(String authority) {
1388             return authority(Part.fromEncoded(authority));
1389         }
1390
1391         Builder path(PathPart path) {
1392             // This URI will be hierarchical.
1393             this.opaquePart = null;
1394
1395             this.path = path;
1396             return this;
1397         }
1398
1399         /**
1400          * Sets the path. Leaves '/' characters intact but encodes others as
1401          * necessary.
1402          *
1403          * <p>If the path is not null and doesn't start with a '/', and if
1404          * you specify a scheme and/or authority, the builder will prepend the
1405          * given path with a '/'.
1406          */
1407         public Builder path(String path) {
1408             return path(PathPart.fromDecoded(path));
1409         }
1410
1411         /**
1412          * Sets the previously encoded path.
1413          *
1414          * <p>If the path is not null and doesn't start with a '/', and if
1415          * you specify a scheme and/or authority, the builder will prepend the
1416          * given path with a '/'.
1417          */
1418         public Builder encodedPath(String path) {
1419             return path(PathPart.fromEncoded(path));
1420         }
1421
1422         /**
1423          * Encodes the given segment and appends it to the path.
1424          */
1425         public Builder appendPath(String newSegment) {
1426             return path(PathPart.appendDecodedSegment(path, newSegment));
1427         }
1428
1429         /**
1430          * Appends the given segment to the path.
1431          */
1432         public Builder appendEncodedPath(String newSegment) {
1433             return path(PathPart.appendEncodedSegment(path, newSegment));
1434         }
1435
1436         Builder query(Part query) {
1437             // This URI will be hierarchical.
1438             this.opaquePart = null;
1439
1440             this.query = query;
1441             return this;
1442         }
1443
1444         /**
1445          * Encodes and sets the query.
1446          */
1447         public Builder query(String query) {
1448             return query(Part.fromDecoded(query));
1449         }
1450
1451         /**
1452          * Sets the previously encoded query.
1453          */
1454         public Builder encodedQuery(String query) {
1455             return query(Part.fromEncoded(query));
1456         }
1457
1458         Builder fragment(Part fragment) {
1459             this.fragment = fragment;
1460             return this;
1461         }
1462
1463         /**
1464          * Encodes and sets the fragment.
1465          */
1466         public Builder fragment(String fragment) {
1467             return fragment(Part.fromDecoded(fragment));
1468         }
1469
1470         /**
1471          * Sets the previously encoded fragment.
1472          */
1473         public Builder encodedFragment(String fragment) {
1474             return fragment(Part.fromEncoded(fragment));
1475         }
1476
1477         /**
1478          * Encodes the key and value and then appends the parameter to the
1479          * query string.
1480          *
1481          * @param key which will be encoded
1482          * @param value which will be encoded
1483          */
1484         public Builder appendQueryParameter(String key, String value) {
1485             // This URI will be hierarchical.
1486             this.opaquePart = null;
1487
1488             String encodedParameter = encode(key, null) + "="
1489                     + encode(value, null);
1490
1491             if (query == null) {
1492                 query = Part.fromEncoded(encodedParameter);
1493                 return this;
1494             }
1495
1496             String oldQuery = query.getEncoded();
1497             if (oldQuery == null || oldQuery.length() == 0) {
1498                 query = Part.fromEncoded(encodedParameter);
1499             } else {
1500                 query = Part.fromEncoded(oldQuery + "&" + encodedParameter);
1501             }
1502
1503             return this;
1504         }
1505
1506         /**
1507          * Clears the the previously set query.
1508          */
1509         public Builder clearQuery() {
1510           return query((Part) null);
1511         }
1512
1513         /**
1514          * Constructs a Uri with the current attributes.
1515          *
1516          * @throws UnsupportedOperationException if the URI is opaque and the
1517          *  scheme is null
1518          */
1519         public Uri build() {
1520             if (opaquePart != null) {
1521                 if (this.scheme == null) {
1522                     throw new UnsupportedOperationException(
1523                             "An opaque URI must have a scheme.");
1524                 }
1525
1526                 return new OpaqueUri(scheme, opaquePart, fragment);
1527             } else {
1528                 // Hierarchical URIs should not return null for getPath().
1529                 PathPart path = this.path;
1530                 if (path == null || path == PathPart.NULL) {
1531                     path = PathPart.EMPTY;
1532                 } else {
1533                     // If we have a scheme and/or authority, the path must
1534                     // be absolute. Prepend it with a '/' if necessary.
1535                     if (hasSchemeOrAuthority()) {
1536                         path = PathPart.makeAbsolute(path);
1537                     }
1538                 }
1539
1540                 return new HierarchicalUri(
1541                         scheme, authority, path, query, fragment);
1542             }
1543         }
1544
1545         private boolean hasSchemeOrAuthority() {
1546             return scheme != null
1547                     || (authority != null && authority != Part.NULL);
1548
1549         }
1550
1551         @Override
1552         public String toString() {
1553             return build().toString();
1554         }
1555     }
1556
1557     /**
1558      * Returns a set of the unique names of all query parameters. Iterating
1559      * over the set will return the names in order of their first occurrence.
1560      *
1561      * @throws UnsupportedOperationException if this isn't a hierarchical URI
1562      *
1563      * @return a set of decoded names
1564      */
1565     public Set<String> getQueryParameterNames() {
1566         if (isOpaque()) {
1567             throw new UnsupportedOperationException(NOT_HIERARCHICAL);
1568         }
1569
1570         String query = getEncodedQuery();
1571         if (query == null) {
1572             return Collections.emptySet();
1573         }
1574
1575         Set<String> names = new LinkedHashSet<String>();
1576         int start = 0;
1577         do {
1578             int next = query.indexOf('&', start);
1579             int end = (next == -1) ? query.length() : next;
1580
1581             int separator = query.indexOf('=', start);
1582             if (separator > end || separator == -1) {
1583                 separator = end;
1584             }
1585
1586             String name = query.substring(start, separator);
1587             names.add(decode(name));
1588
1589             // Move start to end of name.
1590             start = end + 1;
1591         } while (start < query.length());
1592
1593         return Collections.unmodifiableSet(names);
1594     }
1595
1596     /**
1597      * Searches the query string for parameter values with the given key.
1598      *
1599      * @param key which will be encoded
1600      *
1601      * @throws UnsupportedOperationException if this isn't a hierarchical URI
1602      * @throws NullPointerException if key is null
1603      * @return a list of decoded values
1604      */
1605     public List<String> getQueryParameters(String key) {
1606         if (isOpaque()) {
1607             throw new UnsupportedOperationException(NOT_HIERARCHICAL);
1608         }
1609         if (key == null) {
1610           throw new NullPointerException("key");
1611         }
1612
1613         String query = getEncodedQuery();
1614         if (query == null) {
1615             return Collections.emptyList();
1616         }
1617
1618         String encodedKey;
1619         try {
1620             encodedKey = URLEncoder.encode(key, DEFAULT_ENCODING);
1621         } catch (UnsupportedEncodingException e) {
1622             throw new AssertionError(e);
1623         }
1624
1625         ArrayList<String> values = new ArrayList<String>();
1626
1627         int start = 0;
1628         do {
1629             int nextAmpersand = query.indexOf('&', start);
1630             int end = nextAmpersand != -1 ? nextAmpersand : query.length();
1631
1632             int separator = query.indexOf('=', start);
1633             if (separator > end || separator == -1) {
1634                 separator = end;
1635             }
1636
1637             if (separator - start == encodedKey.length()
1638                     && query.regionMatches(start, encodedKey, 0, encodedKey.length())) {
1639                 if (separator == end) {
1640                   values.add("");
1641                 } else {
1642                   values.add(decode(query.substring(separator + 1, end)));
1643                 }
1644             }
1645
1646             // Move start to end of name.
1647             if (nextAmpersand != -1) {
1648                 start = nextAmpersand + 1;
1649             } else {
1650                 break;
1651             }
1652         } while (true);
1653
1654         return Collections.unmodifiableList(values);
1655     }
1656
1657     /**
1658      * Searches the query string for the first value with the given key.
1659      *
1660      * <p><strong>Warning:</strong> Prior to Jelly Bean, this decoded
1661      * the '+' character as '+' rather than ' '.
1662      *
1663      * @param key which will be encoded
1664      * @throws UnsupportedOperationException if this isn't a hierarchical URI
1665      * @throws NullPointerException if key is null
1666      * @return the decoded value or null if no parameter is found
1667      */
1668     public String getQueryParameter(String key) {
1669         if (isOpaque()) {
1670             throw new UnsupportedOperationException(NOT_HIERARCHICAL);
1671         }
1672         if (key == null) {
1673             throw new NullPointerException("key");
1674         }
1675
1676         final String query = getEncodedQuery();
1677         if (query == null) {
1678             return null;
1679         }
1680
1681         final String encodedKey = encode(key, null);
1682         final int length = query.length();
1683         int start = 0;
1684         do {
1685             int nextAmpersand = query.indexOf('&', start);
1686             int end = nextAmpersand != -1 ? nextAmpersand : length;
1687
1688             int separator = query.indexOf('=', start);
1689             if (separator > end || separator == -1) {
1690                 separator = end;
1691             }
1692
1693             if (separator - start == encodedKey.length()
1694                     && query.regionMatches(start, encodedKey, 0, encodedKey.length())) {
1695                 if (separator == end) {
1696                     return "";
1697                 } else {
1698                     String encodedValue = query.substring(separator + 1, end);
1699                     return UriCodec.decode(encodedValue, true, StandardCharsets.UTF_8, false);
1700                 }
1701             }
1702
1703             // Move start to end of name.
1704             if (nextAmpersand != -1) {
1705                 start = nextAmpersand + 1;
1706             } else {
1707                 break;
1708             }
1709         } while (true);
1710         return null;
1711     }
1712
1713     /**
1714      * Searches the query string for the first value with the given key and interprets it
1715      * as a boolean value. "false" and "0" are interpreted as <code>false</code>, everything
1716      * else is interpreted as <code>true</code>.
1717      *
1718      * @param key which will be decoded
1719      * @param defaultValue the default value to return if there is no query parameter for key
1720      * @return the boolean interpretation of the query parameter key
1721      */
1722     public boolean getBooleanQueryParameter(String key, boolean defaultValue) {
1723         String flag = getQueryParameter(key);
1724         if (flag == null) {
1725             return defaultValue;
1726         }
1727         flag = flag.toLowerCase(Locale.ROOT);
1728         return (!"false".equals(flag) && !"0".equals(flag));
1729     }
1730
1731     /**
1732      * Return an equivalent URI with a lowercase scheme component.
1733      * This aligns the Uri with Android best practices for
1734      * intent filtering.
1735      *
1736      * <p>For example, "HTTP://www.android.com" becomes
1737      * "http://www.android.com"
1738      *
1739      * <p>All URIs received from outside Android (such as user input,
1740      * or external sources like Bluetooth, NFC, or the Internet) should
1741      * be normalized before they are used to create an Intent.
1742      *
1743      * <p class="note">This method does <em>not</em> validate bad URI's,
1744      * or 'fix' poorly formatted URI's - so do not use it for input validation.
1745      * A Uri will always be returned, even if the Uri is badly formatted to
1746      * begin with and a scheme component cannot be found.
1747      *
1748      * @return normalized Uri (never null)
1749      * @see android.content.Intent#setData
1750      * @see android.content.Intent#setDataAndNormalize
1751      */
1752     public Uri normalizeScheme() {
1753         String scheme = getScheme();
1754         if (scheme == null) return this;  // give up
1755         String lowerScheme = scheme.toLowerCase(Locale.ROOT);
1756         if (scheme.equals(lowerScheme)) return this;  // no change
1757
1758         return buildUpon().scheme(lowerScheme).build();
1759     }
1760
1761     /** Identifies a null parcelled Uri. */
1762     private static final int NULL_TYPE_ID = 0;
1763
1764     /**
1765      * Reads Uris from Parcels.
1766      */
1767     public static final Parcelable.Creator<Uri> CREATOR
1768             = new Parcelable.Creator<Uri>() {
1769         public Uri createFromParcel(Parcel in) {
1770             int type = in.readInt();
1771             switch (type) {
1772                 case NULL_TYPE_ID: return null;
1773                 case StringUri.TYPE_ID: return StringUri.readFrom(in);
1774                 case OpaqueUri.TYPE_ID: return OpaqueUri.readFrom(in);
1775                 case HierarchicalUri.TYPE_ID:
1776                     return HierarchicalUri.readFrom(in);
1777             }
1778
1779             throw new IllegalArgumentException("Unknown URI type: " + type);
1780         }
1781
1782         public Uri[] newArray(int size) {
1783             return new Uri[size];
1784         }
1785     };
1786
1787     /**
1788      * Writes a Uri to a Parcel.
1789      *
1790      * @param out parcel to write to
1791      * @param uri to write, can be null
1792      */
1793     public static void writeToParcel(Parcel out, Uri uri) {
1794         if (uri == null) {
1795             out.writeInt(NULL_TYPE_ID);
1796         } else {
1797             uri.writeToParcel(out, 0);
1798         }
1799     }
1800
1801     private static final char[] HEX_DIGITS = "0123456789ABCDEF".toCharArray();
1802
1803     /**
1804      * Encodes characters in the given string as '%'-escaped octets
1805      * using the UTF-8 scheme. Leaves letters ("A-Z", "a-z"), numbers
1806      * ("0-9"), and unreserved characters ("_-!.~'()*") intact. Encodes
1807      * all other characters.
1808      *
1809      * @param s string to encode
1810      * @return an encoded version of s suitable for use as a URI component,
1811      *  or null if s is null
1812      */
1813     public static String encode(String s) {
1814         return encode(s, null);
1815     }
1816
1817     /**
1818      * Encodes characters in the given string as '%'-escaped octets
1819      * using the UTF-8 scheme. Leaves letters ("A-Z", "a-z"), numbers
1820      * ("0-9"), and unreserved characters ("_-!.~'()*") intact. Encodes
1821      * all other characters with the exception of those specified in the
1822      * allow argument.
1823      *
1824      * @param s string to encode
1825      * @param allow set of additional characters to allow in the encoded form,
1826      *  null if no characters should be skipped
1827      * @return an encoded version of s suitable for use as a URI component,
1828      *  or null if s is null
1829      */
1830     public static String encode(String s, String allow) {
1831         if (s == null) {
1832             return null;
1833         }
1834
1835         // Lazily-initialized buffers.
1836         StringBuilder encoded = null;
1837
1838         int oldLength = s.length();
1839
1840         // This loop alternates between copying over allowed characters and
1841         // encoding in chunks. This results in fewer method calls and
1842         // allocations than encoding one character at a time.
1843         int current = 0;
1844         while (current < oldLength) {
1845             // Start in "copying" mode where we copy over allowed chars.
1846
1847             // Find the next character which needs to be encoded.
1848             int nextToEncode = current;
1849             while (nextToEncode < oldLength
1850                     && isAllowed(s.charAt(nextToEncode), allow)) {
1851                 nextToEncode++;
1852             }
1853
1854             // If there's nothing more to encode...
1855             if (nextToEncode == oldLength) {
1856                 if (current == 0) {
1857                     // We didn't need to encode anything!
1858                     return s;
1859                 } else {
1860                     // Presumably, we've already done some encoding.
1861                     encoded.append(s, current, oldLength);
1862                     return encoded.toString();
1863                 }
1864             }
1865
1866             if (encoded == null) {
1867                 encoded = new StringBuilder();
1868             }
1869
1870             if (nextToEncode > current) {
1871                 // Append allowed characters leading up to this point.
1872                 encoded.append(s, current, nextToEncode);
1873             } else {
1874                 // assert nextToEncode == current
1875             }
1876
1877             // Switch to "encoding" mode.
1878
1879             // Find the next allowed character.
1880             current = nextToEncode;
1881             int nextAllowed = current + 1;
1882             while (nextAllowed < oldLength
1883                     && !isAllowed(s.charAt(nextAllowed), allow)) {
1884                 nextAllowed++;
1885             }
1886
1887             // Convert the substring to bytes and encode the bytes as
1888             // '%'-escaped octets.
1889             String toEncode = s.substring(current, nextAllowed);
1890             try {
1891                 byte[] bytes = toEncode.getBytes(DEFAULT_ENCODING);
1892                 int bytesLength = bytes.length;
1893                 for (int i = 0; i < bytesLength; i++) {
1894                     encoded.append('%');
1895                     encoded.append(HEX_DIGITS[(bytes[i] & 0xf0) >> 4]);
1896                     encoded.append(HEX_DIGITS[bytes[i] & 0xf]);
1897                 }
1898             } catch (UnsupportedEncodingException e) {
1899                 throw new AssertionError(e);
1900             }
1901
1902             current = nextAllowed;
1903         }
1904
1905         // Encoded could still be null at this point if s is empty.
1906         return encoded == null ? s : encoded.toString();
1907     }
1908
1909     /**
1910      * Returns true if the given character is allowed.
1911      *
1912      * @param c character to check
1913      * @param allow characters to allow
1914      * @return true if the character is allowed or false if it should be
1915      *  encoded
1916      */
1917     private static boolean isAllowed(char c, String allow) {
1918         return (c >= 'A' && c <= 'Z')
1919                 || (c >= 'a' && c <= 'z')
1920                 || (c >= '0' && c <= '9')
1921                 || "_-!.~'()*".indexOf(c) != NOT_FOUND
1922                 || (allow != null && allow.indexOf(c) != NOT_FOUND);
1923     }
1924
1925     /**
1926      * Decodes '%'-escaped octets in the given string using the UTF-8 scheme.
1927      * Replaces invalid octets with the unicode replacement character
1928      * ("\\uFFFD").
1929      *
1930      * @param s encoded string to decode
1931      * @return the given string with escaped octets decoded, or null if
1932      *  s is null
1933      */
1934     public static String decode(String s) {
1935         if (s == null) {
1936             return null;
1937         }
1938         return UriCodec.decode(s, false, StandardCharsets.UTF_8, false);
1939     }
1940
1941     /**
1942      * Support for part implementations.
1943      */
1944     static abstract class AbstractPart {
1945
1946         /**
1947          * Enum which indicates which representation of a given part we have.
1948          */
1949         static class Representation {
1950             static final int BOTH = 0;
1951             static final int ENCODED = 1;
1952             static final int DECODED = 2;
1953         }
1954
1955         volatile String encoded;
1956         volatile String decoded;
1957
1958         AbstractPart(String encoded, String decoded) {
1959             this.encoded = encoded;
1960             this.decoded = decoded;
1961         }
1962
1963         abstract String getEncoded();
1964
1965         final String getDecoded() {
1966             @SuppressWarnings("StringEquality")
1967             boolean hasDecoded = decoded != NOT_CACHED;
1968             return hasDecoded ? decoded : (decoded = decode(encoded));
1969         }
1970
1971         final void writeTo(Parcel parcel) {
1972             @SuppressWarnings("StringEquality")
1973             boolean hasEncoded = encoded != NOT_CACHED;
1974
1975             @SuppressWarnings("StringEquality")
1976             boolean hasDecoded = decoded != NOT_CACHED;
1977
1978             if (hasEncoded && hasDecoded) {
1979                 parcel.writeInt(Representation.BOTH);
1980                 parcel.writeString(encoded);
1981                 parcel.writeString(decoded);
1982             } else if (hasEncoded) {
1983                 parcel.writeInt(Representation.ENCODED);
1984                 parcel.writeString(encoded);
1985             } else if (hasDecoded) {
1986                 parcel.writeInt(Representation.DECODED);
1987                 parcel.writeString(decoded);
1988             } else {
1989                 throw new IllegalArgumentException("Neither encoded nor decoded");
1990             }
1991         }
1992     }
1993
1994     /**
1995      * Immutable wrapper of encoded and decoded versions of a URI part. Lazily
1996      * creates the encoded or decoded version from the other.
1997      */
1998     static class Part extends AbstractPart {
1999
2000         /** A part with null values. */
2001         static final Part NULL = new EmptyPart(null);
2002
2003         /** A part with empty strings for values. */
2004         static final Part EMPTY = new EmptyPart("");
2005
2006         private Part(String encoded, String decoded) {
2007             super(encoded, decoded);
2008         }
2009
2010         boolean isEmpty() {
2011             return false;
2012         }
2013
2014         String getEncoded() {
2015             @SuppressWarnings("StringEquality")
2016             boolean hasEncoded = encoded != NOT_CACHED;
2017             return hasEncoded ? encoded : (encoded = encode(decoded));
2018         }
2019
2020         static Part readFrom(Parcel parcel) {
2021             int representation = parcel.readInt();
2022             switch (representation) {
2023                 case Representation.BOTH:
2024                     return from(parcel.readString(), parcel.readString());
2025                 case Representation.ENCODED:
2026                     return fromEncoded(parcel.readString());
2027                 case Representation.DECODED:
2028                     return fromDecoded(parcel.readString());
2029                 default:
2030                     throw new IllegalArgumentException("Unknown representation: "
2031                             + representation);
2032             }
2033         }
2034
2035         /**
2036          * Returns given part or {@link #NULL} if the given part is null.
2037          */
2038         static Part nonNull(Part part) {
2039             return part == null ? NULL : part;
2040         }
2041
2042         /**
2043          * Creates a part from the encoded string.
2044          *
2045          * @param encoded part string
2046          */
2047         static Part fromEncoded(String encoded) {
2048             return from(encoded, NOT_CACHED);
2049         }
2050
2051         /**
2052          * Creates a part from the decoded string.
2053          *
2054          * @param decoded part string
2055          */
2056         static Part fromDecoded(String decoded) {
2057             return from(NOT_CACHED, decoded);
2058         }
2059
2060         /**
2061          * Creates a part from the encoded and decoded strings.
2062          *
2063          * @param encoded part string
2064          * @param decoded part string
2065          */
2066         static Part from(String encoded, String decoded) {
2067             // We have to check both encoded and decoded in case one is
2068             // NOT_CACHED.
2069
2070             if (encoded == null) {
2071                 return NULL;
2072             }
2073             if (encoded.length() == 0) {
2074                 return EMPTY;
2075             }
2076
2077             if (decoded == null) {
2078                 return NULL;
2079             }
2080             if (decoded .length() == 0) {
2081                 return EMPTY;
2082             }
2083
2084             return new Part(encoded, decoded);
2085         }
2086
2087         private static class EmptyPart extends Part {
2088             public EmptyPart(String value) {
2089                 super(value, value);
2090             }
2091
2092             @Override
2093             boolean isEmpty() {
2094                 return true;
2095             }
2096         }
2097     }
2098
2099     /**
2100      * Immutable wrapper of encoded and decoded versions of a path part. Lazily
2101      * creates the encoded or decoded version from the other.
2102      */
2103     static class PathPart extends AbstractPart {
2104
2105         /** A part with null values. */
2106         static final PathPart NULL = new PathPart(null, null);
2107
2108         /** A part with empty strings for values. */
2109         static final PathPart EMPTY = new PathPart("", "");
2110
2111         private PathPart(String encoded, String decoded) {
2112             super(encoded, decoded);
2113         }
2114
2115         String getEncoded() {
2116             @SuppressWarnings("StringEquality")
2117             boolean hasEncoded = encoded != NOT_CACHED;
2118
2119             // Don't encode '/'.
2120             return hasEncoded ? encoded : (encoded = encode(decoded, "/"));
2121         }
2122
2123         /**
2124          * Cached path segments. This doesn't need to be volatile--we don't
2125          * care if other threads see the result.
2126          */
2127         private PathSegments pathSegments;
2128
2129         /**
2130          * Gets the individual path segments. Parses them if necessary.
2131          *
2132          * @return parsed path segments or null if this isn't a hierarchical
2133          *  URI
2134          */
2135         PathSegments getPathSegments() {
2136             if (pathSegments != null) {
2137                 return pathSegments;
2138             }
2139
2140             String path = getEncoded();
2141             if (path == null) {
2142                 return pathSegments = PathSegments.EMPTY;
2143             }
2144
2145             PathSegmentsBuilder segmentBuilder = new PathSegmentsBuilder();
2146
2147             int previous = 0;
2148             int current;
2149             while ((current = path.indexOf('/', previous)) > -1) {
2150                 // This check keeps us from adding a segment if the path starts
2151                 // '/' and an empty segment for "//".
2152                 if (previous < current) {
2153                     String decodedSegment
2154                             = decode(path.substring(previous, current));
2155                     segmentBuilder.add(decodedSegment);
2156                 }
2157                 previous = current + 1;
2158             }
2159
2160             // Add in the final path segment.
2161             if (previous < path.length()) {
2162                 segmentBuilder.add(decode(path.substring(previous)));
2163             }
2164
2165             return pathSegments = segmentBuilder.build();
2166         }
2167
2168         static PathPart appendEncodedSegment(PathPart oldPart,
2169                 String newSegment) {
2170             // If there is no old path, should we make the new path relative
2171             // or absolute? I pick absolute.
2172
2173             if (oldPart == null) {
2174                 // No old path.
2175                 return fromEncoded("/" + newSegment);
2176             }
2177
2178             String oldPath = oldPart.getEncoded();
2179
2180             if (oldPath == null) {
2181                 oldPath = "";
2182             }
2183
2184             int oldPathLength = oldPath.length();
2185             String newPath;
2186             if (oldPathLength == 0) {
2187                 // No old path.
2188                 newPath = "/" + newSegment;
2189             } else if (oldPath.charAt(oldPathLength - 1) == '/') {
2190                 newPath = oldPath + newSegment;
2191             } else {
2192                 newPath = oldPath + "/" + newSegment;
2193             }
2194
2195             return fromEncoded(newPath);
2196         }
2197
2198         static PathPart appendDecodedSegment(PathPart oldPart, String decoded) {
2199             String encoded = encode(decoded);
2200
2201             // TODO: Should we reuse old PathSegments? Probably not.
2202             return appendEncodedSegment(oldPart, encoded);
2203         }
2204
2205         static PathPart readFrom(Parcel parcel) {
2206             int representation = parcel.readInt();
2207             switch (representation) {
2208                 case Representation.BOTH:
2209                     return from(parcel.readString(), parcel.readString());
2210                 case Representation.ENCODED:
2211                     return fromEncoded(parcel.readString());
2212                 case Representation.DECODED:
2213                     return fromDecoded(parcel.readString());
2214                 default:
2215                     throw new IllegalArgumentException("Bad representation: " + representation);
2216             }
2217         }
2218
2219         /**
2220          * Creates a path from the encoded string.
2221          *
2222          * @param encoded part string
2223          */
2224         static PathPart fromEncoded(String encoded) {
2225             return from(encoded, NOT_CACHED);
2226         }
2227
2228         /**
2229          * Creates a path from the decoded string.
2230          *
2231          * @param decoded part string
2232          */
2233         static PathPart fromDecoded(String decoded) {
2234             return from(NOT_CACHED, decoded);
2235         }
2236
2237         /**
2238          * Creates a path from the encoded and decoded strings.
2239          *
2240          * @param encoded part string
2241          * @param decoded part string
2242          */
2243         static PathPart from(String encoded, String decoded) {
2244             if (encoded == null) {
2245                 return NULL;
2246             }
2247
2248             if (encoded.length() == 0) {
2249                 return EMPTY;
2250             }
2251
2252             return new PathPart(encoded, decoded);
2253         }
2254
2255         /**
2256          * Prepends path values with "/" if they're present, not empty, and
2257          * they don't already start with "/".
2258          */
2259         static PathPart makeAbsolute(PathPart oldPart) {
2260             @SuppressWarnings("StringEquality")
2261             boolean encodedCached = oldPart.encoded != NOT_CACHED;
2262
2263             // We don't care which version we use, and we don't want to force
2264             // unneccessary encoding/decoding.
2265             String oldPath = encodedCached ? oldPart.encoded : oldPart.decoded;
2266
2267             if (oldPath == null || oldPath.length() == 0
2268                     || oldPath.startsWith("/")) {
2269                 return oldPart;
2270             }
2271
2272             // Prepend encoded string if present.
2273             String newEncoded = encodedCached
2274                     ? "/" + oldPart.encoded : NOT_CACHED;
2275
2276             // Prepend decoded string if present.
2277             @SuppressWarnings("StringEquality")
2278             boolean decodedCached = oldPart.decoded != NOT_CACHED;
2279             String newDecoded = decodedCached
2280                     ? "/" + oldPart.decoded
2281                     : NOT_CACHED;
2282
2283             return new PathPart(newEncoded, newDecoded);
2284         }
2285     }
2286
2287     /**
2288      * Creates a new Uri by appending an already-encoded path segment to a
2289      * base Uri.
2290      *
2291      * @param baseUri Uri to append path segment to
2292      * @param pathSegment encoded path segment to append
2293      * @return a new Uri based on baseUri with the given segment appended to
2294      *  the path
2295      * @throws NullPointerException if baseUri is null
2296      */
2297     public static Uri withAppendedPath(Uri baseUri, String pathSegment) {
2298         Builder builder = baseUri.buildUpon();
2299         builder = builder.appendEncodedPath(pathSegment);
2300         return builder.build();
2301     }
2302
2303     /**
2304      * If this {@link Uri} is {@code file://}, then resolve and return its
2305      * canonical path. Also fixes legacy emulated storage paths so they are
2306      * usable across user boundaries. Should always be called from the app
2307      * process before sending elsewhere.
2308      *
2309      * @hide
2310      */
2311     public Uri getCanonicalUri() {
2312         if ("file".equals(getScheme())) {
2313             final String canonicalPath;
2314             try {
2315                 canonicalPath = new File(getPath()).getCanonicalPath();
2316             } catch (IOException e) {
2317                 return this;
2318             }
2319
2320             if (Environment.isExternalStorageEmulated()) {
2321                 final String legacyPath = Environment.getLegacyExternalStorageDirectory()
2322                         .toString();
2323
2324                 // Splice in user-specific path when legacy path is found
2325                 if (canonicalPath.startsWith(legacyPath)) {
2326                     return Uri.fromFile(new File(
2327                             Environment.getExternalStorageDirectory().toString(),
2328                             canonicalPath.substring(legacyPath.length() + 1)));
2329                 }
2330             }
2331
2332             return Uri.fromFile(new File(canonicalPath));
2333         } else {
2334             return this;
2335         }
2336     }
2337
2338     /**
2339      * If this is a {@code file://} Uri, it will be reported to
2340      * {@link StrictMode}.
2341      *
2342      * @hide
2343      */
2344     public void checkFileUriExposed(String location) {
2345         if ("file".equals(getScheme()) && !getPath().startsWith("/system/")) {
2346             StrictMode.onFileUriExposed(this, location);
2347         }
2348     }
2349
2350     /**
2351      * Test if this is a path prefix match against the given Uri. Verifies that
2352      * scheme, authority, and atomic path segments match.
2353      *
2354      * @hide
2355      */
2356     public boolean isPathPrefixMatch(Uri prefix) {
2357         if (!Objects.equals(getScheme(), prefix.getScheme())) return false;
2358         if (!Objects.equals(getAuthority(), prefix.getAuthority())) return false;
2359
2360         List<String> seg = getPathSegments();
2361         List<String> prefixSeg = prefix.getPathSegments();
2362
2363         final int prefixSize = prefixSeg.size();
2364         if (seg.size() < prefixSize) return false;
2365
2366         for (int i = 0; i < prefixSize; i++) {
2367             if (!Objects.equals(seg.get(i), prefixSeg.get(i))) {
2368                 return false;
2369             }
2370         }
2371
2372         return true;
2373     }
2374 }