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