1 /*
2  * Copyright (C) 2018 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 #include "inode2filename/search_directories.h"
18 #include "inode2filename/system_call.h"
19 
20 #include <android-base/logging.h>
21 #include <android-base/strings.h>
22 
23 #include <fruit/fruit.h>
24 #include <gmock/gmock.h>
25 #include <gtest/gtest.h>
26 
27 #include <optional>
28 
29 #include <sys/sysmacros.h>
30 
31 
32 // Set this to 1 when debugging by hand to get more output.
33 // Otherwise the spam might be too much when most tests are failing.
34 #define LOG_WITH_VERBOSE 0
35 // Set this to 1 when debugging by hand to have the logging output go to stderr.
36 // TODO: I think the automated test bots have problems capturing non-logcat output.
37 #define LOG_TO_STDERR 1
38 
39 // TODO: Might be nice to have these controlled by command line.
40 
41 using namespace std::literals::string_literals;  // NOLINT
42 using namespace std::literals::string_view_literals;  // NOLINT
43 using namespace iorap::inode2filename;  // NOLINT
44 using namespace testing;  // NOLINT
45 
ConfigureLogging()46 static void ConfigureLogging() {
47   if (LOG_TO_STDERR) {
48     ::android::base::SetLogger(::android::base::StderrLogger);
49   }
50   if (LOG_WITH_VERBOSE) {
51     ::android::base::SetMinimumLogSeverity(::android::base::VERBOSE);
52   } else {
53     ::android::base::SetMinimumLogSeverity(::android::base::DEBUG);
54   }
55 }
56 
57 // Iterate substrings in 'what' that are separated by 'separator'.
58 // Should be similar to the python 'str.split' behavior.
59 //
60 // Empty separators will have 0 iterations.
61 //
62 // NOTE: this could end up returning empty strings, e.g. '/'.split('/') -> ('', '')
63 // Think of it more like splitting on "$/^" except the $ and ^ become empty strings in the end.
64 //
65 // Zero-copy guarantee (and no dynamic allocation).
66 struct StringSplit {
67   struct SplitIterable;
68 
69   // Return a 0-length substring whose address range is one past the end of 'what'.
70   // Logically equivalent to a "", but its real address will be within 'what'.
71   //
72   // Repeatedly applying this function on itself will return the same value.
73   //
74   // Do not use operator[] on the returned substring, as that would cause undefined
75   // behavior.
76   //
77   // To safely access the pointer, use #data(). The pointer must not be dereferenced,
78   // which would cause undefined behavior.
EmptySubstringAtEndStringSplit79   static constexpr std::string_view EmptySubstringAtEnd(std::string_view what) {
80     return what.substr(/*pos*/what.size(), /*count*/0);
81   }
82 
83   // Create an Iterable that will iterate over substrings in 'what' separated by 'separator'.
84   //
85   // Each such 'value' emitted is guaranteed to be:
86   //  - a substring of 'what'
87   //  - not have any 'separator' substrings
88   //  - the address range of 'value' is within the address range of 'what' (or one-past-the-end)
89   //
90   // For example:
91   //
92   //   for (std::string_view substr : StringSplit("hello/world"sv, "/"sv)) {
93   //     ... // loop 0: substr == "hello"
94   //     ... // loop 1: substr == "world"
95   //   }
IterableStringSplit96   static constexpr SplitIterable Iterable(std::string_view what,
97                                           std::string_view separator) {
98     return SplitIterable{what, separator};
99   }
100 
101   // Implement LegacyForwardIterator concept.
102   struct SplitIterator {
103     using value_type = std::string_view;
104     using reference = value_type&;
105     using pointer = value_type*;
106     using iterator_category = std::forward_iterator_tag;
107     using difference_type = std::ptrdiff_t;  // required by concept, but its meaningless.
108 
operator ==StringSplit::SplitIterator109     constexpr bool operator==(const SplitIterator& other) const {
110       if (state != other.state) {
111         return false;
112       }
113       switch (state) {
114         case kNormal:
115         case kNearEnd:
116           return current_split.data() == other.current_split.data();
117         case kAtEnd:
118           return true;
119       }
120     }
121 
operator !=StringSplit::SplitIterator122     constexpr bool operator!=(const SplitIterator& other) const {
123       return !(*this == other);
124     }
125 
operator *StringSplit::SplitIterator126     constexpr std::string_view& operator*() {
127         DCHECK(state != kAtEnd) << "Undefined behavior to dereference end() iterators";
128         return current_split;
129     }
130 
operator ->StringSplit::SplitIterator131     constexpr std::string_view* operator->() {
132         DCHECK(state != kAtEnd) << "Undefined behavior to dereference end() iterators";
133         return &current_split;
134     }
135 
136     /*
137     constexpr const std::string_view& operator*() const {
138         return current_split;
139     }
140 
141     constexpr const std::string_view* operator->() const {
142         return &current_split;
143     }
144     */
145 
operator ++StringSplit::SplitIterator146     constexpr SplitIterator& operator++() {
147       UpdateValues();
148       return *this;
149     }
150 
operator ++StringSplit::SplitIterator151     constexpr SplitIterator operator++(int) {
152       SplitIterator copy{*this};
153       ++(*this);
154       return copy;
155     }
156 
157    private:
158     // Avoid defining constructors etc. We get the default constructors and operator= then.
159 
160     friend struct SplitIterable;  // Use below Make functions.
161 
MakeBeginStringSplit::SplitIterator162     constexpr static SplitIterator MakeBegin(std::string_view whole, std::string_view separator) {
163       SplitIterator it;
164       it.state = kNormal;
165 
166       if (separator == "") {
167         it.rest_of_string = StringSplit::EmptySubstringAtEnd(whole);
168         // point to one past-the end (which is legal), also equivalent to ""
169         // the difference being that the address range is guaranteed to be within 'whole'
170         // actually any 0-length subrange would be appropriate here, but just go with the 'end'
171         // because dereferencing it would be obviously bad.
172         it.state = kAtEnd;
173         // Empty separator -> empty # of visits. This seems the most composable.
174         // Note: Need to handle this case especially since find_first_of("") would return the
175         // entire string.
176       } else {
177         it.rest_of_string = whole;
178         it.separator = separator;
179         it.UpdateValues();
180       }
181       return it;
182     }
183 
MakeEndStringSplit::SplitIterator184     constexpr static SplitIterator MakeEnd() {
185       SplitIterator it;
186       it.state = kAtEnd;
187       return it;
188     }
189 
UpdateValuesStringSplit::SplitIterator190     constexpr void UpdateValues() {
191       switch (state) {
192         case kNormal:
193           break;
194         case kNearEnd:
195           // Address of emitted value is always within subrange of 'whole'.
196           current_split = StringSplit::EmptySubstringAtEnd(rest_of_string);
197           state = kAtEnd;
198           return;
199         case kAtEnd:
200           // Incrementing the 'end()' operator is undefined behavior.
201           DCHECK(false) << "Undefined behavior: Cannot increment end() iterator.";
202           return;
203       }
204 
205       DCHECK(state == kNormal);
206 
207       size_t pos = rest_of_string.find_first_of(separator);
208       if (std::string_view::npos == pos) {
209         // Always visit at least once for non-empty separators, even if the string is empty.
210 
211         current_split = rest_of_string;
212         // Address of emitted value is always within subrange of 'whole'.
213         rest_of_string = rest_of_string.substr(/*pos*/0, /*count*/0);  // = ""
214         state = kNearEnd;
215       } else {
216         // includes the starting position of the needle
217         // e.g. "+x-".find_first_of('x') -> 1
218 
219         // current_split = rest_of_string[0..pos)
220         current_split = rest_of_string.substr(/*pos*/0, pos);
221 
222         // strip '${left}${separator}' from the left hand side.
223         // continue iterating.
224         rest_of_string = rest_of_string.substr(pos + separator.size());
225       }
226     }
227 
228  public:
229 
PrintToStreamStringSplit::SplitIterator230     void PrintToStream(std::ostream& os) const {
231       os << "SplitIterator{";
232       os << "current_split:\"" << current_split << "\",";
233       os << "rest_of_string:\"" << rest_of_string << "\",";
234       os << "separator:\"" << separator << "\",";
235       os << "state:";
236       switch (state) {
237         case kNormal:
238           os << "kNormal";
239           break;
240         case kNearEnd:
241           os << "kNearEnd";
242           break;
243         case kAtEnd:
244           os << "kAtEnd";
245           break;
246       }
247       os << "}";
248     }
249  private:
250     // Not intended to be used directly.
251     // Public visibility to avoid making extra constructors.
252     std::string_view current_split;
253     std::string_view rest_of_string;
254     std::string_view separator;
255 
256     enum State {
257       kNormal,
258       kNearEnd,
259       kAtEnd
260     };
261     State state{kNormal};
262     // This cannot have a field initializer due to a clang bug,
263     // https://bugs.llvm.org/show_bug.cgi?id=36684
264     // So define an explicit constructor below.
265 
266     // This needs to go last:
267     // undefined constructor 'SplitIterator' cannot be used in a constant expression
268     // constexpr SplitIterator() : state{kNormal} {}
269    // constexpr SplitIterator() {}
270   };
271 
272   friend struct SplitIterable;
273 
274   struct SplitIterable {
275     std::string_view whole;
276     std::string_view separator;
277 
beginStringSplit::SplitIterable278     constexpr SplitIterator begin() {
279       return SplitIterator::MakeBegin(whole, separator);
280     }
281 
endStringSplit::SplitIterable282     constexpr SplitIterator end() {
283       return SplitIterator::MakeEnd();
284     }
285   };
286 };
287 
operator <<(std::ostream & os,const StringSplit::SplitIterator & it)288 std::ostream& operator<<(std::ostream& os, const StringSplit::SplitIterator& it) {
289   it.PrintToStream(os);
290   return os;
291 }
292 
293 static constexpr  const StringSplit::SplitIterator kBlankSplit;
294 
295 // Visit substrings in 'what' that are separated by 'separator'.
296 // Should be similar to the python 'str.split' behavior.
297 //
298 // Empty separators will have 0 visits.
299 //
300 // 'f' is called back for each visit of a substring, this means there's 0 allocations here.
301 //
302 // NOTE: this could end up returning empty strings, e.g. '/'.split('/') -> ('', '')
303 // Think of it more like splitting on "$/^" except the $ and ^ become empty strings in the end.
304 //
305 // (Dynamic allocation free)
306 template <typename Fn>
VisitSplitStringView(std::string_view what,std::string_view separator,Fn f)307 static constexpr void VisitSplitStringView(std::string_view what,
308                                            std::string_view separator,
309                                            Fn f) {
310   // Empty separator -> empty # of visits. This seems the most composable.
311   if (separator == "") {
312     // Note: Need to handle this case especially since find_first_of("") would return the
313     // entire string.
314     return;
315   }
316 
317   size_t sep_length = separator.size();
318 
319   do {
320     size_t pos = what.find_first_of(separator);
321     if (std::string_view::npos == pos) {
322       // Always visit at least once for non-empty separators, even if the string is empty.
323       f(what);
324       break;
325     } else {
326       // includes the starting position of the needle
327       // e.g. "+x-".find_first_of('x') -> 1
328 
329       // left = what[0..pos)
330       std::string_view left_split = what.substr(/*pos*/0, pos);
331       f(left_split);
332 
333       // strip '${left}${separator}' from the left hand side.
334       // continue iterating.
335       what = what.substr(pos + sep_length);
336     }
337   }
338   while (true);
339 }
340 
VisitSplitStringViewVec(std::string_view what,std::string_view separator)341 std::vector<std::string> VisitSplitStringViewVec(std::string_view what,
342                                                  std::string_view separator) {
343   std::vector<std::string> vec;
344   VisitSplitStringView(what, separator, [&vec](auto&& part) {
345                          vec.push_back(std::string{part});
346                        });
347   return vec;
348 }
349 
IterableSplitStringViewVec(std::string_view what,std::string_view separator)350 std::vector<std::string> IterableSplitStringViewVec(std::string_view what,
351                                                     std::string_view separator) {
352   auto iterable = StringSplit::Iterable(what, separator);
353   std::vector<std::string> vec{iterable.begin(), iterable.end()};
354 
355   return vec;
356 }
357 
TEST(SplitStringView,Tests)358 TEST(SplitStringView, Tests) {
359   EXPECT_THAT(VisitSplitStringViewVec("", ""), IsEmpty());
360   EXPECT_THAT(VisitSplitStringViewVec("abcdef", ""), IsEmpty());
361   EXPECT_THAT(VisitSplitStringViewVec("", "/"), ElementsAre(""s));
362   EXPECT_THAT(VisitSplitStringViewVec("/", "/"), ElementsAre(""s, ""s));
363   EXPECT_THAT(VisitSplitStringViewVec("//", "/"), ElementsAre(""s, ""s, ""s));
364   EXPECT_THAT(VisitSplitStringViewVec("/hello", "/"), ElementsAre(""s, "hello"s));
365   EXPECT_THAT(VisitSplitStringViewVec("/hello/world", "/"), ElementsAre(""s, "hello"s, "world"s));
366   EXPECT_THAT(VisitSplitStringViewVec("bar", "/"), ElementsAre("bar"s));
367   EXPECT_THAT(VisitSplitStringViewVec("bar/baz", "/"), ElementsAre("bar"s, "baz"s));
368 
369   EXPECT_THAT(IterableSplitStringViewVec("", ""), IsEmpty());
370   EXPECT_THAT(IterableSplitStringViewVec("abcdef", ""), IsEmpty());
371   EXPECT_THAT(IterableSplitStringViewVec("", "/"), ElementsAre(""s));
372   EXPECT_THAT(IterableSplitStringViewVec("/", "/"), ElementsAre(""s, ""s));
373   EXPECT_THAT(IterableSplitStringViewVec("//", "/"), ElementsAre(""s, ""s, ""s));
374   EXPECT_THAT(IterableSplitStringViewVec("/hello", "/"), ElementsAre(""s, "hello"s));
375   EXPECT_THAT(IterableSplitStringViewVec("/hello/world", "/"), ElementsAre(""s, "hello"s, "world"s));
376   EXPECT_THAT(IterableSplitStringViewVec("bar", "/"), ElementsAre("bar"s));
377   EXPECT_THAT(IterableSplitStringViewVec("bar/baz", "/"), ElementsAre("bar"s, "baz"s));
378 
379   EXPECT_THAT(IterableSplitStringViewVec("/hello", "/"), ElementsAre(""sv, "hello"sv));
380   EXPECT_THAT(IterableSplitStringViewVec("/hello///", "/"), ElementsAre(""sv, "hello"sv, ""sv, ""sv, ""sv));
381 
382 }
383 
384 
385 // Allocation-free immutable path representation and manipulation.
386 //
387 // A PurePath is logically represented by its 'parts', which is a view of each component.
388 //
389 // Examples:
390 //   parts('foo/bar') -> ['foo', 'bar']
391 //   parts('/bar') -> ['/', 'bar']
392 //   parts('') -> []
393 //   parts('.') -> []
394 //   parts('baz//') -> ['baz']
395 //   parts('hello/././world') -> ['hello', 'world']
396 //   parts('../down/../down2') -> ['..', 'down', '..', 'down2']
397 //
398 // See also #VisitParts which allows an allocation-free traversal of the parts.
399 //
400 // Memory allocation/ownership guarantees:
401 // * Functions marked as 'constexpr' are guaranteed never to allocate (zero-copy).
402 // * Functions not marked as 'constexpr' and returning a PurePath will always return an object
403 //   with its own internal copy of the underlying data (i.e. the memory is not borrowed).
404 struct PurePath {
405   using part_type = std::string_view;
406 
407   struct PartIterable;
408 
409   // Create an empty PurePath.
410   //
411   // Empty paths are considered to have 0 parts, i.e.
412   //   PurePath{}.VisitParts() -> []
PurePathPurePath413   constexpr PurePath() : path_(".") {
414   }
415 
416   // Create a PurePath from a string view.
417   //
418   // This borrows memory ownership of the string view. If you wish to make a copy,
419   // use the PurePath(std::string) constructor.
420   //
421   // Paths are non-normalized (i.e. redundant up-references, "..", are not stripped),
422   // you may wish to call 'NormalizePath' if this is important.
PurePathPurePath423   constexpr PurePath(std::string_view path)  : path_(path) {
424     /// : owner_(std::string(path)), path_(owner_.value()) {
425     // TODO: no copy
426   }
427 
PurePathPurePath428   constexpr PurePath(const char* path) : PurePath(std::string_view(path)) {}
429 
430   // Creates a PurePath from a string.
431   //
432   // The PurePath owns the memory of the string path.
433   //
434   // Only accepts movable strings, so that the cheaper borrowing (string_view)
435   // constructor is used by default.
PurePathPurePath436   PurePath(std::string&& path) : owner_(std::move(path)), path_(owner_.value()) {
437   }
438 
439   // Return an Iterable, which upon traversing would
440   // return each part as an std::string_view.
441   //
442   // Empty and '.' path components are not visited,
443   // effectively ignoring redundant // and intermediate '.' components.
444   //
445   // To also ignore redundant up-references, see #NormalizePath.
446   //
447   // Example:
448   //   for (std::string_view part : PurePath("hello//world/./").IterateParts()) {
449   //     // loop 0, part == "hello"sv
450   //     // loop 1, part == "world"sv
451   //   }
IteratePartsPurePath452   constexpr PartIterable IterateParts() const {
453     return PartIterable::FromPath(*this);
454   }
455 
456   // f is a function<void(std::string_view part)>
457   //
458   // Invoke 'f' repeatedly on each logical part of this path.
459   //
460   // Empty and '.' path components are not visited,
461   // effectively ignoring redundant // and intermediate '.' components.
462   //
463   // To also ignore redundant up-references, see #NormalizePath.
464   template <typename Fn>
VisitPartsPurePath465   constexpr void VisitParts(Fn f) const {
466     // Note: Near the top to avoid -Wundefined-inline warnings.
467     if (IsAbsolute()) {
468       f(kRoot);  // When we split, we no longer visit the '/' tokens. Handle root explicitly.
469     }
470     VisitSplitStringView(path_,
471                          kRoot,
472                          [&f](auto&& substr) {
473                            // Ignore duplicate /// and also .
474                            //
475                            // e.g.
476                            //   '//foo' -> ['/', 'foo']
477                            //   './foo' -> ['foo']
478                            //
479                            // This is consistent with PurePath.parts implementation.
480                            //
481                            // Note that redundant .. are not removed, e.g.
482                            //   '../foo/..' is not rewritten to ['..']
483                            //
484                            // Use 'NormalizePath' to do this explicitly.
485                            if (!substr.empty() && substr != ".") {
486                              f(substr);
487                            }
488                          });
489   }
490 
491 
492   // A path is considered equal to another path if all of the parts are identical.
operator ==PurePath493   /*constexpr*/ bool operator==(const PurePath& other) const {
494     /*if (path_ == other.path_) {
495       return true;
496     } else*/ {
497       auto this_range = IterateParts();
498       auto other_range = other.IterateParts();
499 
500       return std::equal(this_range.begin(),
501                         this_range.end(),
502                         other_range.begin(),
503                         other_range.end());
504     }
505   }
506 
507   // Returns the name component (if any).
508   //
509   // Logically equivalent to returning the last part unless:
510   //   - the last part is the root '/'
511   //   - there are no parts
512   //
513   // If the above conditions do not hold, return the empty string.
NamePurePath514   constexpr std::string_view Name() const {
515     std::string_view component = StringSplit::EmptySubstringAtEnd(path_);
516 
517     size_t count = 0;
518     for (auto&& part : IterateParts()) {
519       if (count++ == 0 && part == kRoot) {
520         continue;  // '/' does not count as a name.
521       } else {
522         DCHECK_NE(part, kRoot);
523       }
524 
525       component = part;
526     }
527 
528     return component;
529   }
530 
531   // Find the parent of this path.
532   //
533   // This is usually the path with the last part stripped off, with some special cases:
534   // - The parent of '/' is always '/' (recursive).
535   // - The parent of '' is always '..'.
536   // - The parent of '..[/..]*' is an additional '/..' appended.
537   //
538   // The parent is always distinct (i.e. not equal to this) except for '/', whose parent
539   // is itself.
ParentPurePath540   /*constexpr*/ PurePath Parent() const {
541     size_t parts_count = 0;
542     size_t upreference_count = 0;
543     // TODO: this should be constexpr, but it complains about PurePath not being a literal type.
544 
545     for (auto&& part : IterateParts()) {
546       ++parts_count;
547 
548       if (part == "..") {
549         ++upreference_count;
550       }
551     }
552 
553     if (upreference_count == parts_count) {  // Could also have 0 parts.
554       // "../../../" etc. No other parts are there.
555       // We need to add another '..'
556 
557       // Explicitly handle a few iterations to remain constexpr.
558       switch (upreference_count) {
559         case 0:
560           return {".."};
561         case 1:
562           return {"../.."};
563         case 2:
564           return {"../../.."};
565         case 3:
566           return {"../../../.."};
567         default:
568           break;
569       }
570 
571       // As a special case, this part of the function is not constexpr.
572       std::string built_parent_string = "..";
573       for (size_t i = 0; i < upreference_count; ++i) {
574         built_parent_string += kRoot;
575         built_parent_string += "..";
576       }
577 
578       return PurePath{std::move(built_parent_string)};
579 
580     } else if (parts_count == 1) {
581       if (IsAbsolute()) {
582         // "/" + ".." is still "/"
583         return {kRoot};
584       } else {
585         // <NOT-ROOT-OR-UP-REFERENCE> + ".." is just "."
586         return {};
587       }
588     } else {
589       DCHECK_GE(parts_count, 2u);
590 
591       // Find the last iterator before we hit the end.
592       std::optional<std::string_view> last;
593       std::optional<std::string_view> prev_last;
594       for (auto&& part : IterateParts()) {
595         prev_last = last;
596         last = part;
597       }
598 
599       DCHECK(last.has_value());
600       DCHECK(prev_last.has_value());
601 
602       std::string_view& prev_last_view = *prev_last;
603       // prev_last_view must be within address of subrange_.
604       DCHECK_GE(prev_last_view.data(), path_.data());
605       DCHECK_LE(prev_last_view.data() + prev_last_view.size(), path_.data() + path_.size());
606 
607       // take advantage of the address subrange property by calculating a new substring
608       // for the parent.
609       size_t length = prev_last_view.data() + prev_last_view.size() - path_.data();
610       std::string_view parent = std::string_view{path_.data(), length} ;
611 
612       if ((false)) {
613         LOG(DEBUG) << "PurePath::Parent of \"" << path_ << "\" returns \"" << parent << "\"";
614       }
615       return { parent };
616     }
617   }
618 
619   // A path is considered non-equal to another path if one or more of the parts differ.
operator !=PurePath620   constexpr bool operator!=(const PurePath& other) const {
621     return !(*this == other);
622   }
623 
624   // Return the string view, i.e. to pass to other classes that need a string-like type.
625   //
626   // This passes in the original string as was passed into the constructor.
627   // The exact char-by-char representation may be different than concatenating all the parts
628   // together.
629   //
630   // See also #NormalizePath if you want to get a 1:1 mapping between a PurePath
631   // and a string.
AsStringViewPurePath632   constexpr std::string_view AsStringView() const {
633     // This is slightly inconsistent with PurePath#bytes because it actually collapses the string
634     // to the equivalent of concatenating the parts together. But we prefer not to do that,
635     // since it just causes more work and more allocations unnecessarily.
636     //
637     // This is generally not-noticeable when operating with the path at the logical layer.
638     return path_;
639   }
640 
IsAbsolutePurePath641   constexpr bool IsAbsolute() const {
642     return !path_.empty() && path_[0] == '/';  // left-whitespace is considered significant.
643   }
644 
645   // Join one or more paths together.
646   //
647   // Logically equivalent to calling JoinPath(other) repeatedly.
648   template <typename It>
JoinPathPurePath649   PurePath JoinPath(It begin, It end) const {
650     std::vector<std::string_view> parts_stack = PartsList();
651 
652     while (begin != end) {
653       const PurePath& path = *begin;
654 
655       if (path.IsAbsolute()) {
656         parts_stack = path.PartsList();
657       } else {
658         path.VisitParts([&parts_stack](auto&& part) {
659           parts_stack.push_back(part);
660         });
661       }
662 
663       ++begin;
664     }
665 
666     return {JoinPartsList(parts_stack)};
667   }
668 
669   // Join two paths together:
670   //
671   // If 'other' is an absolute path, it is returned.
672   //
673   // Otherwise, return the concatenation of the parts (this and other) as a new path.
674   // (The returned path is always owned by the caller -- this is triggering an allocation every
675   // time).
JoinPathPurePath676   PurePath JoinPath(const PurePath& other) const {
677     if (other.IsAbsolute()) {
678       return other.OwningCopy();
679     } else {
680       std::vector<std::string_view> parts_stack = PartsList();
681       other.VisitParts([&parts_stack](auto&& part) {
682         parts_stack.push_back(part);
683       });
684       return {JoinPartsList(parts_stack)};
685     }
686   }
687 
PurePathPurePath688   constexpr PurePath(const PurePath& other) {
689     if (this == &other) {
690       return;
691     }
692     if (other.owner_) {  // stay constexpr for non-owning paths.
693       owner_ = other.owner_;
694       path_ = *owner_;   // path_ always points to owner if possible.
695     } else {
696       path_ = other.path_;
697     }
698   }
699 
PurePathPurePath700   constexpr PurePath(PurePath&& other) {
701     if (this == &other) {
702       return;
703     }
704     if (other.owner_) {  // stay constexpr for non-owning paths.
705       owner_ = std::move(other.owner_);
706       path_ = *owner_;   // path_ always points to owner if possible.
707     } else {
708       path_ = std::move(other.path_);
709     }
710   }
711 
712   // "/.." -> "/"
713   // "../foo/.." -> ".."
714   // etc.
715   //
716   // PurePath returned always owns its own memory (this always triggers an allocation).
NormalizePathPurePath717   PurePath NormalizePath() const {
718     if (IsNormalized()) {
719       return OwningCopy();  // Don't call this function if you want to avoid copies!
720     } else {
721       // Invariant: [/]? <UP-REFERENCE>* <NOT-AN-UP-REFERENCE>*
722       std::vector<std::string_view> parts_stack;
723       size_t not_an_up_reference = 0;
724 
725       // Special handling of absolute paths:
726       //   '/' '..'* -> '/'
727       //
728       // Otherwise, remove the last part when encountering redundant up-references:
729       //   e.g. '../foo/bar/baz/..' -> '../foo/bar'
730       VisitParts([&](auto&& part) {
731                    if (part == "..") {
732                      // <UP-REFERENCE>
733                      if (not_an_up_reference > 0) {
734                        // Remove redundant up-references.
735                        DCHECK(!parts_stack.empty());
736 
737                        // Could trigger de-normalization, remove redundant part from stack.
738 
739                        if (parts_stack.back() != kRoot) {  // '/' '..'* -> '/'
740                          parts_stack.pop_back();
741                          --not_an_up_reference;            // '../foo/..' -> '..'
742                        }
743                      } else {
744                        // Did not trigger a denormalization.
745                        parts_stack.push_back(part);
746                      }
747                    } else {
748                      // <NOT-AN-UP-REFERENCE> or '/' (note: / is only visited the first time).
749                      parts_stack.push_back(part);
750                      ++not_an_up_reference;
751                    }
752                  });
753 
754       // join again with empty delimiter.
755       std::string concat = JoinPartsList(std::move(parts_stack));
756 
757       return PurePath(std::move(concat));
758     }
759   }
760 
761   // Returns true if 'NormalizePath' would return a Path with a different parts representation.
762   //
763   // (This is not as strict as normalizing the underlying string, i.e. redundant '.' and "//"
764   // in AsStringView() could still be seen).
765   //
766   // A path is considered non-normalized unless all up-references are at the start.
767   //
768   //   NormalizedString := <UP-REFERENCE>* <NOT-AN-UP-REFERENCE>*
769   //
770   // where each token is a 'part' returned by VisitParts.
771   //
772   // Returning false here means that 'NormalizePath' will also trigger an extra allocation.
IsNormalizedPurePath773   constexpr bool IsNormalized() const {
774     size_t not_an_up_reference = 0;
775     bool is_normalized = true;
776 
777     // Note that this also handles '/' [..]* because '/' is treated identically to non-up-refs.
778     VisitParts([&](auto&& part) {
779                 // Remove redundant up-references.
780                 if (part != "..") {
781                   ++not_an_up_reference;
782                 } else {  // part == ".."
783                   if (not_an_up_reference > 0) {   // <not-an-up-reference> <up-reference>
784                     is_normalized = false;
785                   }
786                 }
787                });
788 
789     return is_normalized;
790   }
791 
792   // Implement LegacyForwardIterator concept.
793   struct PartIterator {
794     using value_type = std::string_view;
795     using reference = value_type&;
796     using pointer = value_type*;
797     using iterator_category = std::forward_iterator_tag;
798     using difference_type = std::ptrdiff_t;  // required by concept, but its meaningless.
799 
800    private:
801     enum State {
802       kUninitialized,
803       kAtRoot,
804       kInitialized,
805       kAtEnd
806     };
807 
808     using SplitIterable = StringSplit::SplitIterable;
809     using SplitIterator = StringSplit::SplitIterator;
810 
811     State state{kUninitialized};
812     value_type cur_value;
813     SplitIterator cur;
814     SplitIterator end;
815 
816     friend std::ostream& operator<<(std::ostream& os, const PartIterator& it);
817 
818     // Print out extra debugging information when looping through the iterator.
819     static constexpr bool kLogDebug = false;
820 
821    public:
PrintToStreamPurePath::PartIterator822     void PrintToStream(std::ostream& os) const {
823       os << "PartIterator{";
824       os << "state:";
825       switch (state) {
826         case kUninitialized:
827           os << "kUninitialized";
828           break;
829         case kAtRoot:
830           os << "kAtRoot";
831           break;
832         case kInitialized:
833           os << "kInitialized";
834           break;
835         case kAtEnd:
836           os << "kAtEnd";
837           break;
838       }
839       os << ",";
840       os << "cur_value:\"" << cur_value << "\",";
841       os << "cur:" << cur << ",";
842       os << "end:" << end << ",";
843       os << "}";
844     }
845 
operator ==PurePath::PartIterator846     /*constexpr*/ bool operator==(const PartIterator& other) const {
847       DCHECK(state != kUninitialized) << "State must be initialized";
848       DCHECK(other.state != kUninitialized) << "Other state must be initialized";
849 
850       if (kLogDebug) {
851         LOG(DEBUG) << "PartIterator ==";
852       }
853 
854       if (state != other.state) {
855         if (kLogDebug) {
856           LOG(DEBUG) << "State: " << static_cast<int>(state);
857           LOG(DEBUG) << "Other State: " << static_cast<int>(other.state);
858 
859           LOG(DEBUG) << "== states differ (&self=" << this << ",&other=" << &other << ")";
860           LOG(DEBUG) << "Self=" << *this;
861           LOG(DEBUG) << "Other=" << other;
862         }
863         return false;
864       }
865 
866       switch (state) {
867         case kAtRoot:
868           DCHECK(cur != end);
869           return cur == other.cur;
870         case kInitialized:
871           DCHECK(cur != end);
872           return cur == other.cur;
873         case kAtEnd:
874           DCHECK(cur == end);
875           DCHECK(cur == other.cur);
876           return true;
877         default:
878           DCHECK(false);  // -Werror -Wswitch
879           return true;
880       }
881     }
882 
operator !=PurePath::PartIterator883     constexpr bool operator!=(const PartIterator& other) const {
884       return !(*this == other);
885     }
886 
operator *PurePath::PartIterator887     constexpr reference operator*() {
888         DCHECK(state != kAtEnd) << "Undefined behavior to dereference end() iterators";
889         return cur_value;  // Can't use *cur because we could yield a '/'.
890     }
891 
operator ->PurePath::PartIterator892     constexpr pointer operator->() {
893         DCHECK(state != kAtEnd) << "Undefined behavior to dereference end() iterators";
894         return &cur_value;  // Can't use &*cur because we could yield a '/'.
895     }
896 
897     /*
898     constexpr const reference operator*() const {
899         return *cur;
900     }
901 
902     constexpr const pointer operator->() const {
903         return &*cur;
904     }*/
905 
operator ++PurePath::PartIterator906     constexpr PartIterator& operator++() {
907       DCHECK(state != kAtEnd) << "Undefined behavior to increment end() iterators";
908       UpdateValues();
909       return *this;
910     }
911 
operator ++PurePath::PartIterator912     constexpr PartIterator operator++(int) {
913       PartIterator copy{*this};
914       ++(*this);
915       return copy;
916     }
917 
MakeBeginPurePath::PartIterator918     constexpr static PartIterator MakeBegin(SplitIterable& split_iterable,
919                                             std::string_view whole_path) {
920       SplitIterator begin = split_iterable.begin();
921       SplitIterator end = split_iterable.end();
922 
923       PartIterator it;
924       it.end = end;
925 
926       const bool is_absolute = !whole_path.empty() && whole_path[0] == '/';
927 
928       if (begin == end) {
929         it.cur = end;
930         it.state = kAtEnd;
931         // I'm not sure this path is actually possible due to the nature of how StringSplit
932         // works, but it's better to cover this case just to be safe.
933         DCHECK(false) << "unreachable code, splitting by '/' always returns at least 1 split";
934       } else {
935         it.cur = begin;
936 
937         if (is_absolute) {
938           // When we split, we no longer visit the '/' tokens. Handle root explicitly.
939           //
940           // All emitted values must be within the address range of the whole path.
941           it.cur_value = whole_path.substr(0, /*count*/1);  // '/'
942           DCHECK_EQ(it.cur_value, "/"sv);
943           it.state = kAtRoot;
944         } else {
945           it.state = kUninitialized;
946           it.UpdateValues();
947         }
948       }
949 
950       return it;
951     }
952 
MakeEndPurePath::PartIterator953     constexpr static PartIterator MakeEnd(SplitIterable& split_iterable) {
954       SplitIterator end = split_iterable.end();
955 
956       PartIterator it;
957       it.cur = end;
958       it.end = end;
959       it.state = kAtEnd;
960 
961       return it;
962     }
963 
964    private:
UpdateValuesPurePath::PartIterator965     void UpdateValues() {
966       State previous_state = state;
967 
968       if (kLogDebug) {
969         LOG(DEBUG) << "operator ++ // UpdateValues (&this=" << this << ")";
970       }
971 
972       if (state == kAtEnd) {
973         return;
974       }
975 
976       if (state == kInitialized) {
977         DCHECK(IsValidCurrent());
978       }
979 
980       // '/' has no corresponding split, so it's handled as a special case.
981       // Furthermore, any splits that are empty or "." are skipped since they aren't
982       // considered to be a valid path component.
983       //
984       // The below code handles these special cases.
985 
986       if (state == kAtRoot) {
987         state = kUninitialized;
988       }
989 
990       if (state == kUninitialized) {
991         // If we are already at a valid value stop.
992         if (cur != end && IsValidCurrent()) {
993           state = kInitialized;
994           cur_value = *cur;
995           return;
996         }
997 
998         // Otherwise we are either at the end, or
999         // the current value is invalid (e.g. empty or '.').
1000         state = kInitialized;
1001       }
1002 
1003       DCHECK(state == kInitialized) << static_cast<int>(state);
1004       if (previous_state == kInitialized) {
1005         // If we fell-through from kAtRoot or kUninitialized
1006         // then there's no guarantee that the current value is valid.
1007         DCHECK(IsValidCurrent());
1008       }
1009 
1010       auto old_cur_value = *cur;
1011 
1012       // Already at the end. Switch to end state.
1013       if (cur == end) {
1014         state = kAtEnd;
1015         LOG(DEBUG) << "Updated state is: kAtEnd (1)";
1016         return;
1017       }
1018 
1019       // Skip ahead.
1020       // We may or may not be at a valid value now.
1021       ++cur;
1022 
1023       // If we aren't at a valid value yet, then keep going forward
1024       // until we hit a valid value (or we exhaust the iterator).
1025       while (cur != end && !IsValidCurrent()) {
1026         ++cur;
1027       }
1028 
1029       if (cur == end) {
1030         state = kAtEnd;
1031       } else {
1032         // We reached a valid value before exhausting the iterator.
1033 
1034         // Stay in the 'Initialized' state.
1035         DCHECK(IsValidCurrent()) << *cur;
1036         cur_value = *cur;
1037 
1038         // After we go forward, the old and current value cannot match.
1039         DCHECK_NE(&cur_value[0], &old_cur_value[0]);
1040       }
1041 
1042       if (kLogDebug) {
1043         LOG(DEBUG) << "Updated state is: " << state;
1044       }
1045     }
1046 
IsValidCurrentPurePath::PartIterator1047     constexpr bool IsValidCurrent() {
1048       if (cur->empty()) {
1049         return false;
1050       } else if (*cur == ".") {
1051         return false;
1052       }
1053 
1054       return true;
1055     }
1056   };
1057 
1058   friend struct PartIterable;
1059 
1060   struct PartIterable {
FromPathPurePath::PartIterable1061     constexpr static PartIterable FromPath(const PurePath& path) {
1062       return PartIterable{
1063           path.AsStringView(),
1064           StringSplit::Iterable(path.AsStringView(), PurePath::kRoot),
1065       };
1066     }
1067 
beginPurePath::PartIterable1068     constexpr PartIterator begin() {
1069       return PartIterator::MakeBegin(split_iterable, whole_path);
1070     }
1071 
endPurePath::PartIterable1072     constexpr PartIterator end() {
1073       return PartIterator::MakeEnd(split_iterable);
1074     }
1075 
1076     std::string_view whole_path;
1077     StringSplit::SplitIterable split_iterable;
1078   };
1079 
1080   // This isn't performance-efficient, but it might be needed by some functions
1081   // that have to allocate anyway such as JoinPaths.
1082   //
1083   // Intended only for testing.
PartsListPurePath1084   std::vector<std::string_view> PartsList() const {
1085     PartIterable iterable = IterateParts();
1086 
1087     std::vector<std::string_view> parts{iterable.begin(), iterable.end()};
1088     return parts;
1089   }
1090 
1091   // Does this PurePath own the underlying memory?
1092   //
1093   // true = borrowing memory from someone else (might not be safe to retain this object)
1094   // false = owns its own memory (can keep this object indefinitely long)
1095   //
1096   // Currently intended only for testing.
IsBorrowedPurePath1097   constexpr bool IsBorrowed() const {
1098     return !owner_.has_value();
1099   }
1100 
1101  private:
1102   // Return a PurePath that owns its own memory.
1103   //
1104   // This way functions which 'may' allocate memory turn into functions
1105   // that always allocate memory, and avoid a dangling reference.
OwningCopyPurePath1106   const PurePath OwningCopy() const {
1107     std::string make_copy{path_};
1108     return PurePath{std::move(make_copy)};
1109   }
1110 
PartsCountPurePath1111   constexpr size_t PartsCount() const {
1112     size_t count = 0;
1113     VisitParts([&count](auto&& /*part*/) {
1114       ++count;
1115     });
1116     return count;
1117   }
1118 
1119   // Basically a string join with an empty delimiter.
1120   template <typename Container>
JoinPartsListPurePath1121   static std::string JoinPartsList(Container&& c) {
1122     std::string build;
1123     for (auto begin = c.begin(), end = c.end(); begin != end; ++begin) {
1124       build += *begin;
1125 
1126       // TODO: use forward_dependent here.
1127     }
1128 
1129     return build;
1130   }
1131 
1132   // This might be empty, in which case path_ is just a temporary borrow of path_.
1133   std::optional<std::string> owner_;
1134   std::string_view path_;  // points to owner_ if there's a value there.
1135 
1136   // TODO: this is a bit error-prone, so we might want to refactor into a
1137   // never-owning PathView and an always-owning PurePath.
1138 
1139   static constexpr std::string_view kRoot = "/";
1140 };
1141 
operator <<(std::ostream & os,const PurePath::PartIterator & it)1142 std::ostream& operator<<(std::ostream& os, const PurePath::PartIterator& it) {
1143   it.PrintToStream(os);
1144   return os;
1145 }
1146 
1147 static constexpr const PurePath::PartIterator kMakeMeABlank;
1148 
operator <<(std::ostream & os,const PurePath & path)1149 std::ostream& operator<<(std::ostream& os, const PurePath& path) {
1150   os << path.AsStringView();
1151   return os;
1152 }
1153 
TEST(PurePathTest,Ctor)1154 TEST(PurePathTest, Ctor) {
1155   ConfigureLogging();
1156 
1157   EXPECT_EQ(PurePath{}.AsStringView(), "."sv);
1158   EXPECT_EQ(PurePath{""}.AsStringView(), ""sv);
1159   EXPECT_EQ(PurePath{""sv}.AsStringView(), ""sv);
1160   EXPECT_EQ(PurePath{""s}.AsStringView(), ""sv);
1161   EXPECT_EQ(PurePath{"/hello/world"}.AsStringView(), "/hello/world"sv);
1162   EXPECT_EQ(PurePath{"/hello/world"s}.AsStringView(), "/hello/world"sv);
1163   EXPECT_EQ(PurePath{"/hello/world"sv}.AsStringView(), "/hello/world"sv);
1164   EXPECT_EQ(PurePath{"hello/world"}.AsStringView(), "hello/world"sv);
1165   EXPECT_EQ(PurePath{"hello/world"s}.AsStringView(), "hello/world"sv);
1166   EXPECT_EQ(PurePath{"hello/world"sv}.AsStringView(), "hello/world"sv);
1167 
1168   // Ensure that std::string is only owning memory when we move a string into it.
1169   // Otherwise, always take the string_view constructor.
1170   EXPECT_FALSE(PurePath{std::string{"hello"}}.IsBorrowed());
1171   std::string hello{"hello"};
1172   EXPECT_TRUE(PurePath{hello}.IsBorrowed());
1173   EXPECT_FALSE(PurePath{std::move(hello)}.IsBorrowed());
1174 }
1175 
TEST(PurePathTest,Parts)1176 TEST(PurePathTest, Parts) {
1177   ConfigureLogging();
1178 
1179   EXPECT_THAT(PurePath{}.PartsList(), IsEmpty());
1180   EXPECT_THAT(PurePath{"."}.PartsList(), IsEmpty());
1181   EXPECT_THAT(PurePath{"./"}.PartsList(), IsEmpty());
1182   EXPECT_THAT(PurePath{"./."}.PartsList(), IsEmpty());
1183   EXPECT_THAT(PurePath{".///"}.PartsList(), IsEmpty());
1184   EXPECT_THAT(PurePath{"./././."}.PartsList(), IsEmpty());
1185   EXPECT_THAT(PurePath{"/"s}.PartsList(), ElementsAre("/"sv));
1186   EXPECT_THAT(PurePath{"///"s}.PartsList(), ElementsAre("/"sv));
1187   EXPECT_THAT(PurePath{"/hello"s}.PartsList(), ElementsAre("/"sv, "hello"sv));
1188   EXPECT_THAT(PurePath{"/hello///"s}.PartsList(), ElementsAre("/"sv, "hello"sv));
1189   EXPECT_THAT(PurePath{"/hello/world"s}.PartsList(), ElementsAre("/"sv, "hello"sv, "world"sv));
1190   EXPECT_THAT(PurePath{"hello/world"sv}.PartsList(), ElementsAre("hello"sv, "world"sv));
1191   EXPECT_THAT(PurePath{"hello/world"sv}.PartsList(), ElementsAre("hello"sv, "world"sv));
1192   EXPECT_THAT(PurePath{"hello//world"sv}.PartsList(), ElementsAre("hello"sv, "world"sv));
1193   EXPECT_THAT(PurePath{"hello/./world"sv}.PartsList(), ElementsAre("hello"sv, "world"sv));
1194   EXPECT_THAT(PurePath{"hello/./world/././"sv}.PartsList(), ElementsAre("hello"sv, "world"sv));
1195 }
1196 
1197 #define EXPECT_PATH_EQ(lhs, rhs) EXPECT_EQ(PurePath{lhs}, PurePath{rhs})
1198 #define EXPECT_PATH_NE(lhs, rhs) EXPECT_NE(PurePath{lhs}, PurePath{rhs})
1199 
TEST(PurePathTest,Equals)1200 TEST(PurePathTest, Equals) {
1201   ConfigureLogging();
1202 
1203   EXPECT_PATH_EQ("", "");
1204   EXPECT_PATH_EQ(".", ".");
1205   EXPECT_PATH_EQ("", ".");
1206   EXPECT_PATH_EQ("./", ".");
1207   EXPECT_PATH_EQ(".////", ".");
1208   EXPECT_PATH_EQ(".//././", ".");
1209   EXPECT_PATH_EQ("hello/world//", "hello/world");
1210   EXPECT_PATH_EQ("hello/world//", "./hello/world");
1211   EXPECT_PATH_EQ("//hello/world//", "/hello/world");
1212   EXPECT_PATH_EQ("/./hello/world//", "/hello/world/./");
1213   EXPECT_PATH_EQ("..", ".././.");
1214   EXPECT_PATH_EQ("../..//", "../..");
1215 
1216   // Also make sure that the path is not equal to its parent [which is a substring].
1217   EXPECT_PATH_NE("/data", "/data/baz");
1218   EXPECT_PATH_NE("/data/././baz", "/data/baz/bar");
1219 
1220   // Also make sure its not equal when the other path shares the same underlying starting data().
1221   {
1222     std::string_view view = "/data/bar";
1223     EXPECT_PATH_NE(PurePath{view}, PurePath{view.substr(/*pos*/0, /*count*/5)});
1224   }
1225 }
1226 
1227 // A parent is always different than its child (except for '/').
1228 #define EXPECT_PATH_PARENT_EQ(actual, expected) \
1229     EXPECT_EQ(PurePath{actual}.Parent(), PurePath{expected}); \
1230     { auto act = PurePath{actual};   \
1231       EXPECT_NE(act, act.Parent());  \
1232     }
TEST(PurePathTest,Parent)1233 TEST(PurePathTest, Parent) {
1234   ConfigureLogging();
1235 
1236   // Special recursive case: parent of '/' is still '/'.
1237   EXPECT_EQ(PurePath{"/"}, PurePath{"/"}.Parent());
1238   EXPECT_NE(PurePath{""}, PurePath{"/"}.Parent());
1239 
1240   // All other cases are non-recursive.
1241   EXPECT_PATH_PARENT_EQ("", "..");
1242   EXPECT_PATH_PARENT_EQ("..", "../..");
1243   EXPECT_PATH_PARENT_EQ("../..", "../../..");
1244   EXPECT_PATH_PARENT_EQ("../../../../../../../../..", "../../../../../../../../../..");
1245 
1246   EXPECT_PATH_PARENT_EQ("/abc", "/");
1247   EXPECT_PATH_PARENT_EQ("abc", "");
1248 
1249   EXPECT_PATH_PARENT_EQ("/foo/bar", "/foo");
1250   EXPECT_PATH_PARENT_EQ("/foo/bar/b", "/foo/bar");
1251   EXPECT_PATH_PARENT_EQ("/foo/bar///baz///././/nay", "/foo/bar/baz");
1252 
1253   EXPECT_PATH_PARENT_EQ("foo/bar", "foo");
1254   EXPECT_PATH_PARENT_EQ("foo/bar/b", "foo/bar");
1255   EXPECT_PATH_PARENT_EQ("foo/bar///baz///././/nay", "foo/bar/baz");
1256 
1257   EXPECT_PATH_PARENT_EQ("../foo/bar", "../foo");
1258   EXPECT_PATH_PARENT_EQ("../foo/bar/b", "../foo/bar");
1259   EXPECT_PATH_PARENT_EQ("../foo/bar///baz///././/nay", "../foo/bar/baz");
1260 }
1261 
1262 #define EXPECT_PATH_NAME_EQ(expected, actual) EXPECT_EQ(PurePath{actual}, PurePath{expected}.Name())
TEST(PurePathTest,Name)1263 TEST(PurePathTest, Name) {
1264   ConfigureLogging();
1265 
1266   EXPECT_PATH_NAME_EQ("", "");
1267   EXPECT_PATH_NAME_EQ("..", "..");
1268   EXPECT_PATH_NAME_EQ("../..", "..");
1269   EXPECT_PATH_NAME_EQ("../../../../../../../../..", "..");
1270 
1271   EXPECT_PATH_NAME_EQ("/", "");
1272   EXPECT_PATH_NAME_EQ("/abc", "abc");
1273   EXPECT_PATH_NAME_EQ("abc", "abc");
1274 
1275   EXPECT_PATH_NAME_EQ("/foo/bar", "bar");
1276   EXPECT_PATH_NAME_EQ("/foo/bar/b", "b");
1277   EXPECT_PATH_NAME_EQ("/foo/bar///baz///././/nay", "nay");
1278   EXPECT_PATH_NAME_EQ("/foo/bar///baz///././/nay//./.", "nay");
1279 
1280   EXPECT_PATH_NAME_EQ("foo/bar", "bar");
1281   EXPECT_PATH_NAME_EQ("foo/bar/b", "b");
1282   EXPECT_PATH_NAME_EQ("foo/bar///baz///././/nay", "nay");
1283 
1284   EXPECT_PATH_NAME_EQ("../foo/bar", "bar");
1285   EXPECT_PATH_NAME_EQ("../foo/bar/b", "b");
1286   EXPECT_PATH_NAME_EQ("../foo/bar///baz///././/nay", "nay");
1287 }
1288 
1289 
1290 struct PathEntry {
1291   Inode inode;
1292   PurePath path;  // full path
1293 
ZipPathEntry1294   static std::vector<PathEntry> Zip(std::vector<Inode>& inodes, std::vector<std::string>& paths) {
1295     CHECK_EQ(inodes.size(), paths.size());
1296 
1297     std::vector<PathEntry> entries;
1298 
1299     static bool debug = true;  // Print only once.
1300 
1301     if (debug) {
1302       LOG(DEBUG) << "PathEntry::Zip (begin)";
1303     }
1304 
1305     for (size_t i = 0; i < inodes.size(); ++i) {
1306       entries.push_back(PathEntry{inodes[i], PurePath{std::string{paths[i]}}});
1307 
1308       // TODO: this seems awkward, maybe refactor into PurePath + PurePathView ?
1309       DCHECK(entries[i].path.IsBorrowed() == false);
1310 
1311       if (debug) {
1312         LOG(DEBUG) << "PathEntry - add " << inodes[i] << " at '" << paths[i] << "'";
1313       }
1314     }
1315 
1316     debug = false;
1317 
1318     return entries;
1319   }
1320 };
1321 
operator <<(std::ostream & os,const PathEntry & path_entry)1322 std::ostream& operator<<(std::ostream& os, const PathEntry& path_entry) {
1323   os << "PathEntry{inode=" << path_entry.inode << ",path=\"" << path_entry.path << "\"}";
1324   return os;
1325 }
1326 
1327 // This super-inefficient class models a Tree to a list of absolute path names.
1328 // Obviously intended only for testing, since its algorithmically suboptimal.
1329 struct PathEntryTree {
1330   std::vector<PathEntry> entries;
1331 
1332   static constexpr bool debug{false};
1333 #define PET_LOG_DEBUG if (debug) LOG(DEBUG)
1334 
GetEntryForPathEntryTree1335   std::optional<PathEntry> GetEntryFor(const std::string& path_name) {
1336     PurePath path{path_name};
1337     for (auto&& entry : entries) {
1338       if (entry.path == path) {
1339         return entry;
1340       }
1341     }
1342     return {};
1343   }
1344 
HasDirectoryPathEntryTree1345   bool HasDirectory(const std::string& path_name) {
1346     PurePath path{path_name};
1347     for (auto&& entry : entries) {
1348       if (entry.path == path) {
1349         return true;
1350       }
1351     }
1352     return false;
1353   }
1354 
OpenDirectoryPathEntryTree1355   std::vector<PathEntry> OpenDirectory(const std::string& path_name) {
1356     PurePath path{path_name};
1357     return OpenDirectory(path);
1358   }
1359 
OpenDirectoryPathEntryTree1360   std::vector<PathEntry> OpenDirectory(const PurePath& path) {
1361     std::vector<PathEntry> children;
1362 
1363     PET_LOG_DEBUG << "OpenDirectory(" << path << ")";
1364 
1365     for (auto&& entry : entries) {
1366       // Only find the immediate children, don't find any other offspring.
1367       PurePath parent = entry.path.Parent();
1368       if (parent == path) {
1369         if (parent == entry.path) {
1370           // Ignore recursive parents, e.g. '/'
1371           PET_LOG_DEBUG << "OpenDirectory - Ignore recursive parent " << parent;
1372           continue;
1373         }
1374 
1375         children.push_back(entry);
1376 
1377         DCHECK(!children.back().path.IsBorrowed());
1378 
1379         PET_LOG_DEBUG << "OpenDirectory - Child added = " << entry;
1380       }
1381     }
1382 
1383 
1384     return children;
1385   }
1386 
sizePathEntryTree1387   size_t size() const {
1388     return entries.size();
1389   }
1390 };
1391 
1392 
ParseLines(const char * what)1393 static std::vector<std::string> ParseLines(const char* what) {
1394   std::vector<std::string> do_split = android::base::Split(what, "\n");
1395 
1396   std::vector<std::string> output;
1397   for (std::string& s : do_split) {
1398     if (s.size() != 0) {
1399       output.push_back(s);
1400     }
1401   }
1402 
1403   return output;
1404 }
1405 
ParseInodes(std::vector<std::string> inode_strings)1406 static std::vector<Inode> ParseInodes(std::vector<std::string> inode_strings) {
1407   std::vector<Inode> results;
1408 
1409   for (std::string& s : inode_strings) {
1410     Inode inode;
1411 
1412     std::string error_msg;
1413     bool inode_parse_succeeded = Inode::Parse(s, /*out*/&inode, /*out*/&error_msg);
1414     CHECK(inode_parse_succeeded) << s << ", error: " << error_msg;
1415 
1416     results.push_back(inode);
1417   }
1418 
1419   return results;
1420 }
1421 
1422 
1423 
CreateFakePathEntries()1424 static PathEntryTree CreateFakePathEntries() {
1425 #if 1
1426     // adb shell 'find /data/data/com.google.android.googlequicksearchbox/ | xargs stat -c "%d@%i"'
1427     static const char* kInodeValues = R"1N0D3(
1428 66323@1117133
1429 66323@1127133
1430 66323@1137133
1431 66323@1327133
1432 66323@1336383
1433 66323@1376559
1434 66323@1376448
1435 66323@1376446
1436 66323@1376596
1437 66323@1376638
1438 66323@1376438
1439 66323@1376444
1440 66323@1376563
1441 66323@1376434
1442 66323@1376439
1443 66323@1336384
1444 66323@1335704
1445 66323@1336031
1446 66323@1335751
1447 66323@1337692
1448 66323@1336090
1449 66323@1336385
1450 66323@1376543
1451 66323@1376449
1452 66323@1376544
1453 66323@1376547
1454 66323@1376436
1455 66323@1336619
1456 66323@1336070
1457 66323@1336681
1458 66323@1336064
1459 66323@1336088
1460 66323@1336470
1461 66323@1335570
1462 66323@1335668
1463 66323@1336471
1464 66323@1335514
1465 66323@1376475
1466 66323@1376462
1467 66323@1376435
1468 66323@1376476
1469 66323@1376632
1470 66323@1351934
1471 66323@1351948
1472 66323@1351949
1473 66323@1351950
1474 66323@1351939
1475 66323@1376479
1476 66323@1376437
1477 66323@1376450
1478 66323@1376480
1479 66323@1376442
1480 66323@1376451
1481 66323@1376454
1482 66323@1376457
1483 66323@1376452
1484 66323@1376546
1485 66323@1335629
1486 66323@1343800
1487 66323@1343801
1488 66323@1336890
1489 66323@1336616
1490 66323@1336921
1491 66323@1327135
1492 66323@1335862
1493 66323@1336547
1494 66323@1351681
1495 66323@1351684
1496 66323@1351744
1497 66323@1351705
1498 66323@1351699
1499 66323@1351711
1500 66323@1351748
1501 66323@1351734
1502 66323@1351682
1503 66323@1351683
1504 66323@1351719
1505 66323@1351739
1506 66323@1351689
1507 66323@1351724
1508 66323@1351690
1509 66323@1351745
1510 66323@1351686
1511 66323@1351691
1512 66323@1351741
1513 66323@1351687
1514 66323@1351747
1515 66323@1351736
1516 66323@1351698
1517 66323@1351697
1518 66323@1351730
1519 66323@1351712
1520 66323@1351703
1521 66323@1351721
1522 66323@1351701
1523 66323@1351717
1524 66323@1351716
1525 66323@1351695
1526 66323@1351720
1527 66323@1351688
1528 66323@1351685
1529 66323@1351727
1530 66323@1351738
1531 66323@1351729
1532 66323@1351704
1533 66323@1351743
1534 66323@1351723
1535 66323@1351700
1536 66323@1351713
1537 66323@1351707
1538 66323@1351709
1539 66323@1351731
1540 66323@1351732
1541 66323@1351693
1542 66323@1351726
1543 66323@1351708
1544 66323@1351714
1545 66323@1351728
1546 66323@1351694
1547 66323@1351706
1548 66323@1351722
1549 66323@1351696
1550 66323@1351715
1551 66323@1351740
1552 66323@1351725
1553 66323@1351702
1554 66323@1351710
1555 66323@1351737
1556 66323@1351742
1557 66323@1351746
1558 66323@1351735
1559 66323@1351733
1560 66323@1351692
1561 66323@1351718
1562 66323@1336864
1563 66323@1335446
1564 66323@1337584
1565 66323@1335740
1566 66323@1335854
1567 66323@1336644
1568 66323@1376553
1569 66323@1376554
1570 66323@1376469
1571 66323@1376637
1572 66323@1376555
1573 66323@1376556
1574 66323@1376570
1575 66323@1376565
1576 66323@1376557
1577 66323@1376558
1578 66323@1376432
1579 66323@1376567
1580 66323@1376440
1581 66323@1343805
1582 66323@1336646
1583 66323@1336947
1584 66323@1336393
1585 66323@1336394
1586 66323@1335920
1587 66323@1336041
1588 66323@1335650
1589 66323@1336667
1590 66323@1336665
1591 66323@1335760
1592 66323@1343802
1593 66323@1343803
1594 66323@1344013
1595 66323@1344134
1596 66323@1376276
1597 66323@1336598
1598 66323@1336634
1599 66323@1336652
1600 66323@1336656
1601 66323@1336446
1602 66323@1336863
1603 66323@1337682
1604 66323@1336866
1605 66323@1336867
1606 66323@1335678
1607 66323@1336865
1608 66323@1327631
1609 66323@1327664
1610 66323@1327660
1611 66323@1327134
1612 66323@1336825
1613 66323@1337969
1614 66323@1335938
1615 66323@1337849
1616 66323@1337839
1617 66323@1337866
1618 66323@1337122
1619 66323@1337756
1620 66323@1336966
1621 66323@1337982
1622 66323@1337097
1623 66323@1336683
1624 66323@1337824
1625 66323@1337460
1626 66323@1337775
1627 66323@1337810
1628 66323@1337847
1629 66323@1335853
1630 66323@1337594
1631 66323@1337808
1632 66323@1337817
1633 66323@1337092
1634 66323@1337699
1635 66323@1337593
1636 66323@1337089
1637 66323@1335959
1638 66323@1337788
1639 66323@1337181
1640 66323@1337610
1641 66323@1336980
1642 66323@1337972
1643 66323@1337554
1644 66323@1337661
1645 66323@1337770
1646 66323@1335951
1647 66323@1337984
1648 66323@1336061
1649 66323@1337497
1650 66323@1337835
1651 66323@1337805
1652 66323@1336557
1653 66323@1336780
1654 66323@1337816
1655 66323@1337732
1656 66323@1337983
1657 66323@1337954
1658 66323@1337713
1659 66323@1337687
1660 66323@1337597
1661 66323@1337466
1662 66323@1337814
1663 66323@1337603
1664 66323@1337031
1665 66323@1336784
1666 66323@1337534
1667 66323@1337727
1668 66323@1337693
1669 66323@1337791
1670 66323@1337567
1671 66323@1337748
1672 66323@1337777
1673 66323@1336194
1674 66323@1337843
1675 66323@1336971
1676 66323@1337974
1677 66323@1336785
1678 66323@1337871
1679 66323@1337815
1680 66323@1337709
1681 66323@1337551
1682 66323@1337088
1683 66323@1337776
1684 66323@1337672
1685 66323@1335979
1686 66323@1337823
1687 66323@1336028
1688 66323@1337526
1689 66323@1337971
1690 66323@1337853
1691 66323@1337596
1692 66323@1337901
1693 66323@1337572
1694 66323@1335921
1695 66323@1336954
1696 66323@1337820
1697 66323@1335492
1698 66323@1337809
1699 66323@1337696
1700 66323@1335636
1701 66323@1337608
1702 66323@1335746
1703 66323@1337731
1704 66323@1337967
1705 66323@1337769
1706 66323@1337751
1707 66323@1337973
1708 66323@1337697
1709 66323@1335939
1710 66323@1336001
1711 66323@1337598
1712 66323@1336713
1713 66323@1337702
1714 66323@1337844
1715 66323@1337862
1716 66323@1336978
1717 66323@1337975
1718 66323@1336798
1719 66323@1337858
1720 66323@1337605
1721 66323@1337510
1722 66323@1337914
1723 66323@1376548
1724 66323@1376549
1725 66323@1376550
1726 66323@1376564
1727 66323@1376571
1728 66323@1376683
1729 66323@1376681
1730 66323@1376652
1731 66323@1376682
1732 66323@1376684
1733 66323@1376649
1734 66323@1376568
1735 66323@1376569
1736 66323@1376576
1737 66323@1376578
1738 66323@1376579
1739 66323@1376581
1740 66323@1376582
1741 66323@1376577
1742 66323@1376580
1743 66323@1376597
1744 66323@1376598
1745 66323@1376602
1746 66323@1376599
1747 66323@1376600
1748 66323@1376601
1749 66323@1376583
1750 66323@1376551
1751 66323@1376552
1752 66323@1376560
1753 66323@1376561
1754 66323@1376562
1755 66323@1376591
1756 66323@1376497
1757 66323@1376482
1758 66323@1376536
1759 66323@1376533
1760 66323@1376532
1761 66323@1336380
1762 66323@1336425
1763 66323@1337738
1764 66323@1337978
1765 66323@1337796
1766 66323@1337819
1767 66323@1337781
1768 66323@1337857
1769 66323@1337963
1770 66323@1335777
1771 66323@1337569
1772 66323@1337818
1773 66323@1337758
1774 66323@1337742
1775 66323@1336950
1776 66323@1337730
1777 66323@1337021
1778 66323@1335774
1779 66323@1337813
1780 66323@1337755
1781 66323@1337964
1782 66323@1337860
1783 66323@1338005
1784 66323@1336592
1785 66323@1336428
1786 66323@1335779
1787 66323@1337976
1788 66323@1337461
1789 66323@1337789
1790 66323@1337745
1791 66323@1337602
1792 66323@1337698
1793 66323@1336813
1794 66323@1337606
1795 66323@1337896
1796 66323@1337712
1797 66323@1337970
1798 66323@1337981
1799 66323@1335435
1800 66323@1337587
1801 66323@1337821
1802 66323@1337716
1803 66323@1337754
1804 66323@1337786
1805 66323@1337778
1806 66323@1336032
1807 66323@1338029
1808 66323@1337550
1809 66323@1337783
1810 66323@1337609
1811 66323@1337107
1812 66323@1337841
1813 66323@1337557
1814 66323@1337700
1815 66323@1337604
1816 66323@1337920
1817 66323@1337469
1818 66323@1337811
1819 66323@1337715
1820 66323@1337980
1821 66323@1336949
1822 66323@1337812
1823 66323@1337806
1824 66323@1337779
1825 66323@1337600
1826 66323@1336080
1827 66323@1337601
1828 66323@1336920
1829 66323@1337703
1830 66323@1337033
1831 66323@1336824
1832 66323@1337104
1833 66323@1337854
1834 66323@1336078
1835 66323@1336970
1836 66323@1337917
1837 66323@1337671
1838 66323@1337926
1839 66323@1336802
1840 66323@1337797
1841 66323@1338031
1842 66323@1337095
1843 66323@1337676
1844 66323@1337708
1845 66323@1335905
1846 66323@1336124
1847 66323@1337859
1848 66323@1337784
1849 66323@1337795
1850 66323@1337724
1851 66323@1337822
1852 66323@1336426
1853 66323@1337852
1854 66323@1337856
1855 66323@1337855
1856 66323@1337780
1857 66323@1337607
1858 66323@1336956
1859 66323@1337038
1860 66323@1336513
1861 66323@1336918
1862 66323@1336739
1863 66323@1337924
1864 66323@1337530
1865 66323@1337757
1866 66323@1337850
1867 66323@1337701
1868 66323@1336613
1869 66323@1337737
1870 66323@1336817
1871 66323@1337977
1872 66323@1336314
1873 66323@1337465
1874 66323@1336991
1875 66323@1337279
1876 66323@1337922
1877 66323@1337710
1878 66323@1337599
1879 66323@1337861
1880 66323@1336388
1881 66323@1336389
1882 66323@1336084
1883 66323@1335615
1884 66323@1336375
1885 66323@1335759
1886 66323@1336036
1887 66323@1336433
1888 66323@1335649
1889 66323@1337744
1890 66323@1336008
1891 66323@1336004
1892 66323@1336026
1893 66323@1335834
1894 66323@1336376
1895 66323@1336377
1896 66323@1336505
1897 66323@1336378
1898 66323@1335382
1899 66323@1337015
1900 66323@1336108
1901 66323@1337103
1902 66323@1335413
1903 66323@1335935
1904 66323@1335429
1905 66323@1337733
1906 66323@1336382
1907 66323@1336381
1908 66323@1336633
1909 66323@1337522
1910 66323@1336694
1911 66323@1335428
1912 )1N0D3";
1913 
1914     const char* kPathNames = R"F1L3N4M3(
1915 /
1916 /data/
1917 /data/data/
1918 /data/data/com.google.android.googlequicksearchbox/
1919 /data/data/com.google.android.googlequicksearchbox/app_si
1920 /data/data/com.google.android.googlequicksearchbox/app_si/searchbox_stats_content_store
1921 /data/data/com.google.android.googlequicksearchbox/app_si/searchbox_stats_content_store/content_store.db-shm
1922 /data/data/com.google.android.googlequicksearchbox/app_si/searchbox_stats_content_store/content_store.db-wal
1923 /data/data/com.google.android.googlequicksearchbox/app_si/searchbox_stats_content_store/content_store.db
1924 /data/data/com.google.android.googlequicksearchbox/app_si/searchbox_stats_content_store/content_store.db-wipecheck
1925 /data/data/com.google.android.googlequicksearchbox/app_si/shortcuts_content_store
1926 /data/data/com.google.android.googlequicksearchbox/app_si/shortcuts_content_store/content_store.db-shm
1927 /data/data/com.google.android.googlequicksearchbox/app_si/shortcuts_content_store/content_store.db-wipecheck
1928 /data/data/com.google.android.googlequicksearchbox/app_si/shortcuts_content_store/content_store.db-wal
1929 /data/data/com.google.android.googlequicksearchbox/app_si/shortcuts_content_store/content_store.db
1930 /data/data/com.google.android.googlequicksearchbox/app_si/now_content_store
1931 /data/data/com.google.android.googlequicksearchbox/app_si/now_content_store/content_store.db-wal
1932 /data/data/com.google.android.googlequicksearchbox/app_si/now_content_store/content_store.db-shm
1933 /data/data/com.google.android.googlequicksearchbox/app_si/now_content_store/now_content_store_blob_9060309284749123123.bin
1934 /data/data/com.google.android.googlequicksearchbox/app_si/now_content_store/content_store.db-wipecheck
1935 /data/data/com.google.android.googlequicksearchbox/app_si/now_content_store/now_content_store_blob_9184734810098631032.bin
1936 /data/data/com.google.android.googlequicksearchbox/app_si/now_content_store/content_store.db
1937 /data/data/com.google.android.googlequicksearchbox/app_si/proactive_key_value_content_store
1938 /data/data/com.google.android.googlequicksearchbox/app_si/proactive_key_value_content_store/content_store.db-shm
1939 /data/data/com.google.android.googlequicksearchbox/app_si/proactive_key_value_content_store/content_store.db
1940 /data/data/com.google.android.googlequicksearchbox/app_si/proactive_key_value_content_store/content_store.db-wipecheck
1941 /data/data/com.google.android.googlequicksearchbox/app_si/proactive_key_value_content_store/content_store.db-wal
1942 /data/data/com.google.android.googlequicksearchbox/app_si/srp_content_store
1943 /data/data/com.google.android.googlequicksearchbox/app_si/srp_content_store/content_store.db-wal
1944 /data/data/com.google.android.googlequicksearchbox/app_si/srp_content_store/content_store.db
1945 /data/data/com.google.android.googlequicksearchbox/app_si/srp_content_store/content_store.db-wipecheck
1946 /data/data/com.google.android.googlequicksearchbox/app_si/srp_content_store/content_store.db-shm
1947 /data/data/com.google.android.googlequicksearchbox/app_si/state_dump_event_content_store
1948 /data/data/com.google.android.googlequicksearchbox/app_si/state_dump_event_content_store/content_store.db-wipecheck
1949 /data/data/com.google.android.googlequicksearchbox/app_si/state_dump_event_content_store/content_store.db-shm
1950 /data/data/com.google.android.googlequicksearchbox/app_si/state_dump_event_content_store/content_store.db
1951 /data/data/com.google.android.googlequicksearchbox/app_si/state_dump_event_content_store/content_store.db-wal
1952 /data/data/com.google.android.googlequicksearchbox/app_si/homescreen_shortcut_content_store
1953 /data/data/com.google.android.googlequicksearchbox/app_si/homescreen_shortcut_content_store/content_store.db-shm
1954 /data/data/com.google.android.googlequicksearchbox/app_si/homescreen_shortcut_content_store/content_store.db-wal
1955 /data/data/com.google.android.googlequicksearchbox/app_si/homescreen_shortcut_content_store/content_store.db
1956 /data/data/com.google.android.googlequicksearchbox/app_si/homescreen_shortcut_content_store/content_store.db-wipecheck
1957 /data/data/com.google.android.googlequicksearchbox/app_si/search_widget_overlay_content_store
1958 /data/data/com.google.android.googlequicksearchbox/app_si/search_widget_overlay_content_store/content_store.db-wal
1959 /data/data/com.google.android.googlequicksearchbox/app_si/search_widget_overlay_content_store/content_store.db-shm
1960 /data/data/com.google.android.googlequicksearchbox/app_si/search_widget_overlay_content_store/content_store.db-wipecheck
1961 /data/data/com.google.android.googlequicksearchbox/app_si/search_widget_overlay_content_store/content_store.db
1962 /data/data/com.google.android.googlequicksearchbox/app_si/opa_content_store
1963 /data/data/com.google.android.googlequicksearchbox/app_si/opa_content_store/content_store.db-wal
1964 /data/data/com.google.android.googlequicksearchbox/app_si/opa_content_store/content_store.db-wipecheck
1965 /data/data/com.google.android.googlequicksearchbox/app_si/opa_content_store/content_store.db
1966 /data/data/com.google.android.googlequicksearchbox/app_si/opa_content_store/content_store.db-shm
1967 /data/data/com.google.android.googlequicksearchbox/app_si/accl_conv_client_content_store
1968 /data/data/com.google.android.googlequicksearchbox/app_si/accl_conv_client_content_store/content_store.db-shm
1969 /data/data/com.google.android.googlequicksearchbox/app_si/accl_conv_client_content_store/content_store.db
1970 /data/data/com.google.android.googlequicksearchbox/app_si/accl_conv_client_content_store/content_store.db-wal
1971 /data/data/com.google.android.googlequicksearchbox/app_si/accl_conv_client_content_store/content_store.db-wipecheck
1972 /data/data/com.google.android.googlequicksearchbox/app_session
1973 /data/data/com.google.android.googlequicksearchbox/app_monet_init_data
1974 /data/data/com.google.android.googlequicksearchbox/app_monet_init_data/search.TYPE_SEARCHNOW.binarypb
1975 /data/data/com.google.android.googlequicksearchbox/no_backup
1976 /data/data/com.google.android.googlequicksearchbox/no_backup/com.google.InstanceId.properties
1977 /data/data/com.google.android.googlequicksearchbox/no_backup/com.google.android.gms.appid-no-backup
1978 /data/data/com.google.android.googlequicksearchbox/code_cache
1979 /data/data/com.google.android.googlequicksearchbox/app_sid
1980 /data/data/com.google.android.googlequicksearchbox/app_g3_models
1981 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US
1982 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/CLG.prewalk.fst
1983 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/verbalizer_terse.mfar
1984 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_app-actions_prompted-app-name_TWIDDLER_FST.fst
1985 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/contacts.abnf
1986 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_monastery_contact-disambig-static_TWIDDLER_FST.fst
1987 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/wordlist.syms
1988 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/norm_fst
1989 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/APP_NAME.fst
1990 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/APP_NAME.syms
1991 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/ep_portable_mean_stddev
1992 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/portable_meanstddev
1993 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/SONG_NAME.syms
1994 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/g2p_phonemes.syms
1995 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/TERSE_LSTM_LM.lstm_lm.main_model.uint8.data
1996 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/voice_actions.config
1997 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/CONTACT_NAME.fst
1998 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/TERSE_LSTM_LM.lstm_lm.self_normalized_model.uint8.data
1999 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/pumpkin.mmap
2000 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/CONTACT_NAME.syms
2001 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/word_confidence_classifier
2002 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/offline_action_data.pb
2003 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/config.pumpkin
2004 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/compile_grammar.config
2005 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/lstm_model.uint8.data
2006 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_read-items_SearchMessageAction-Prompted-Read_TWIDDLER_FST.fst
2007 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/embedded_class_denorm.mfar
2008 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/g2p.data
2009 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/dictation.config
2010 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/endpointer_model.mmap
2011 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/endpointer_model
2012 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/c_fst
2013 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/ep_portable_model.uint8.mmap
2014 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/SONG_NAME.fst
2015 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/CONTACT.transform.mfar
2016 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/hmmlist
2017 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/portable_lstm
2018 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/lexicon.U.fst
2019 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/embedded_normalizer.mfar
2020 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/semantics.pumpkin
2021 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/g2p_graphemes.syms
2022 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/dict
2023 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_read-items_SearchMessageAction-Prompted-Skip_TWIDDLER_FST.fst
2024 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_confirmation_confirmation-cancellation_TWIDDLER_FST.fst
2025 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_media-actions_music-service-controllable_TWIDDLER_FST.fst
2026 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/magic_mic.config
2027 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/metadata
2028 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/am_phonemes.syms
2029 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/hmm_symbols
2030 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_gmm-actions_gmm-nav-actions_TWIDDLER_FST.fst
2031 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_time-actions_time-context_TWIDDLER_FST.fst
2032 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/input_mean_std_dev
2033 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/benchmark.volvo.txt
2034 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_calendar-actions_AddCalendarEvent-Prompted-FieldToChange_TWIDDLER_FST.fst
2035 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/g2p_fst
2036 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/commands.abnf
2037 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/endpointer_dictation.config
2038 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/prons_exception_dictionary_file.txt
2039 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/grammar.config
2040 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/dnn
2041 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/en-US_monastery_GenericAction-Prompted-ContactName_TWIDDLER_FST.fst
2042 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/phonelist
2043 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/rescoring.fst.compact
2044 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/voice_actions_compiler.config
2045 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/offensive_word_normalizer.mfar
2046 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/monastery_config.pumpkin
2047 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/TERSE_LSTM_LM.lstm_lm.syms
2048 /data/data/com.google.android.googlequicksearchbox/app_g3_models/en-US/endpointer_voicesearch.config
2049 /data/data/com.google.android.googlequicksearchbox/app_textures
2050 /data/data/com.google.android.googlequicksearchbox/files
2051 /data/data/com.google.android.googlequicksearchbox/files/current_experiments.bin
2052 /data/data/com.google.android.googlequicksearchbox/files/training_question_data
2053 /data/data/com.google.android.googlequicksearchbox/files/now_request_queue
2054 /data/data/com.google.android.googlequicksearchbox/files/velour
2055 /data/data/com.google.android.googlequicksearchbox/files/velour/preferences
2056 /data/data/com.google.android.googlequicksearchbox/files/velour/preferences/ipa
2057 /data/data/com.google.android.googlequicksearchbox/files/velour/preferences/ipa/IpaBgTask
2058 /data/data/com.google.android.googlequicksearchbox/files/velour/preferences/wernicke_player
2059 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data
2060 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa
2061 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa/ipa_0p_instant_cache
2062 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa/ZeroPrefixContacts
2063 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa/ipa_content_store
2064 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa/ipa_content_store/content_store.db
2065 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa/ipa_content_store/content_store.db-wal
2066 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa/ipa_content_store/content_store.db-wipecheck
2067 /data/data/com.google.android.googlequicksearchbox/files/velour/feature_data/ipa/ipa_content_store/content_store.db-shm
2068 /data/data/com.google.android.googlequicksearchbox/files/velour/jar_data
2069 /data/data/com.google.android.googlequicksearchbox/files/velour/verified_jars
2070 /data/data/com.google.android.googlequicksearchbox/files/velour/dex_cache
2071 /data/data/com.google.android.googlequicksearchbox/files/native_crash_dir
2072 /data/data/com.google.android.googlequicksearchbox/files/native_crash_dir/com.google.android.googlequicksearchbox:search
2073 /data/data/com.google.android.googlequicksearchbox/files/current_configuration.bin
2074 /data/data/com.google.android.googlequicksearchbox/files/dynamic_update_config_log
2075 /data/data/com.google.android.googlequicksearchbox/files/brainsuggest
2076 /data/data/com.google.android.googlequicksearchbox/files/brainsuggest/libbrainsuggest.so
2077 /data/data/com.google.android.googlequicksearchbox/files/brainsuggest/tensors.bin
2078 /data/data/com.google.android.googlequicksearchbox/files/persisted_profiling_statistics
2079 /data/data/com.google.android.googlequicksearchbox/files/en-US
2080 /data/data/com.google.android.googlequicksearchbox/files/en-US/x_hotword.data
2081 /data/data/com.google.android.googlequicksearchbox/files/recently
2082 /data/data/com.google.android.googlequicksearchbox/files/recently/libcore.test@gmail.com
2083 /data/data/com.google.android.googlequicksearchbox/files/dump
2084 /data/data/com.google.android.googlequicksearchbox/files/bloblobber
2085 /data/data/com.google.android.googlequicksearchbox/files/bloblobber/pending
2086 /data/data/com.google.android.googlequicksearchbox/files/web_suggest_model
2087 /data/data/com.google.android.googlequicksearchbox/files/web_suggest_model/index.bin
2088 /data/data/com.google.android.googlequicksearchbox/files/client_data_request_log
2089 /data/data/com.google.android.googlequicksearchbox/app_webview
2090 /data/data/com.google.android.googlequicksearchbox/app_webview/variations_seed_new
2091 /data/data/com.google.android.googlequicksearchbox/app_webview/Cookies-journal
2092 /data/data/com.google.android.googlequicksearchbox/app_webview/variations_stamp
2093 /data/data/com.google.android.googlequicksearchbox/app_webview/variations_seed
2094 /data/data/com.google.android.googlequicksearchbox/app_webview/Cookies
2095 /data/data/com.google.android.googlequicksearchbox/app_shared_prefs
2096 /data/data/com.google.android.googlequicksearchbox/app_shared_prefs/StartupSettings.bin
2097 /data/data/com.google.android.googlequicksearchbox/app_shared_prefs/SearchSettings.bin
2098 /data/data/com.google.android.googlequicksearchbox/cache
2099 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache
2100 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/fd12e9a1ba593cbe075c925a95626534054861f9dd82fa27f656ac0088648fd9.0
2101 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/4a19d733c917d730443eaff509ee0496e116f79c69d0d2fa54a594f5accd19d1.0
2102 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/76f6a9848373162cd602a03e00e363ad8455e62293e9218d57da728f7382ee34.0
2103 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/666d7a8c0d257a9a9f1457a1bb04b8eda821966283d466db872d5693de42d29b.0
2104 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/0f714cd570228ce48e2741fd6ff959bcbbab49e40427b6eb5c4b1ff3aae4ad40.0
2105 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/458acc9b996dc815a7259a2c9dbf5b94ae549da3d66f3649d1e0a1e239214390.0
2106 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/13ec5eaf61460a0be11467ba2e0efad6602142e45fd1c97988bc42aa54832407.0
2107 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/99b468ff1549d8e260ce274f7afdaaf32fb70064c31596173b812ea2d11c8097.0
2108 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/40c737d31b2d843c5772648820deeb4c8d5bef9426b025f75bdc72ba7913e0fd.0
2109 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/41186543405abfea16b57da566ce9e509826f9b1b6337473d05d9421f53912aa.0
2110 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/cda361ffde7db6bedfeb9f01a63dd51ebbe4b733d3c6be69cede7a681d20b583.0
2111 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/108adf201cd9b479777504c8e7fb74299bbc2b51082d2872a34616abe6c743fb.0
2112 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/47a3358d7989bf06c4ce1ecb350149b1669bf16073ea1d321371a02ad3507d63.0
2113 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/0c25c0bd4df514cdd4531872553e053b74a3b9a60476871184b7e8c2a1b67048.0
2114 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/936a9280b8b33ffaf98e9497927d7d84cfc87757bf235569fa950c55922ab76c.0
2115 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/4cb136284aa9e19be2492e23d421297736f888ddf03cd7eebdb690d4f3b929c1.0
2116 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/43f3dcad386912254bc1b2a6cd8414c3373f465665655584a0cf31b9c2f6ce6f.0
2117 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/73c62366e6dda1ee960692d71e4ff9ba92d193b966986866793e64dec10fdc9b.0
2118 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/d361cbbc4c1c8a5eeda8dda6173926c112f28f0bc49efc7946a0c218b4195fa3.0
2119 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/eb0939417658eea85bdccd5b4c1c460f836649e442cad3100393e039f8f82fe6.0
2120 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/5979b3d43ade0ddbf8aa86e3ef5e2951fb677bcc0a39d133433bd58989328130.0
2121 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/82f2aaeedc6ddb9a8086912bd8064c5aac85437814d7ef6e5a6fb5e22bd71491.0
2122 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/cf4ed99e5d88c5bbf18d812c6eb7a5b90f12e47f346b33061f6ad6c073d81be7.0
2123 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/f5f95fe8ca532f13faeb1209981138d786f0df2e061d151fe655a571a8ddd88c.0
2124 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/5a5f20fcb280a697e2f22c460d796fbd291481760480a764d6fe6a6c83e6380a.0
2125 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/dba86bd8a4f75d2148b80fb04d525193b29b060fbf8a4743fe1b41e39c4fb25d.0
2126 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/d7017ff3c9fbda9a376ff72d8a95eb9e0a5858cf50ee82a5b92d6e995550867d.0
2127 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/a6bf758115a73beafa9124803667e93729442e7cad367a86608ad9ad8655b08b.0
2128 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/24ae44003669f9f9640832b4c9cf9acb8ac3c2adf5ab5a2444a7715b090b3f67.0
2129 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/b39aac6d9d0b5ea2ce78831602e48e0a48f7f2c792697e9c58de1d45b27a792a.0
2130 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/9194df1b37d6a7da9ee8fd03abebdc3e81ec6ea366224eecb0cd7d3d66024062.0
2131 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/f64b3e72b098f53f10ca3f3031b93df60c8ef407510bab8a003c9747e82f6043.0
2132 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/6ff297c691797ab5fd5222b0c1fa13abc750fc031685a29589eace7748864318.0
2133 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/8704bbe8a29455b6034d773c57246b1633da5393fd102f87fcb6eca819b82753.0
2134 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/ef4146d94b8e32988b3cb0eba7e967cfa9627a683a1359cf00a1d76aa5022680.0
2135 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/ebf974f9350e2f784145463f0afcccac69f265af0e8b233813617829684a290f.0
2136 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/06a6aaede02e9527e1eb6dad977a7889e22d2dfcc098f9342eacc134c31363df.0
2137 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/d915555e83e27c4d5f6dcd1badaaed666fa80e5ae11d6d2382e666efe606bd1f.0
2138 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/a189554aa8b3185799fdb5bfb89cc42698c544a1041e65709b0e79d267cabdc5.0
2139 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/0f310a87cae45484d5da35274ff89463eb966a1aeb32d53a2fb8350cf9d836b2.0
2140 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/df7598066371b7da446954feb42a1febdb8921cacf436285e85606cae9de4bb5.0
2141 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/ff8d8869f35a9a4243fac1ce8ab5deff7ee161dfc8c2ea1107099ec1cf74e100.0
2142 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/75d36a907297689726ca96ef721c091c04a879f1f096f503076dd172834a27dc.0
2143 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/5e6fee09c93c6f1d493bd04dd18cc8043c0b40093d85ed94c2df28ab129b226b.0
2144 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/d7ddd06a2070b76dc05fe12741d7882df5a4312b174a11ce3d98d059fcc17173.0
2145 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/7bcac404ee6981364837ac1a89033184ff65939507a81caa7c43ea52a195e215.0
2146 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/392ac948386e63063f941449eeb9199c3f1a05959934c47c5987bbf6aa0721a3.0
2147 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/df13e0aac1211176a1939bf2198f9e0e7dedd1f043875a4093ce0265cd02744e.0
2148 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/052649971efbb0e18631044219b92ab68f12dc244041042b24203c88a62377b6.0
2149 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/1e86ba82b4061a7ef799089ce29826fcba0ba07c77aec6638f20e850d1864144.0
2150 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/7fe25319e6b2049b96c6659264568defe6a7e21bb3817685970b3a3aa511d8c8.0
2151 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/3a66049907f84778aa548c747d9a52c2e67ce880c19fa4b0a8b4e58ae96fd9ef.0
2152 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/54f622cb04525cc1953cc1ffbe12646be3290de6ca378ce5508869860df761e5.0
2153 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/6fa117d5fcf115733a154f5d0911ce05b103ea33d5eee65d2b08a83605cf6e80.0
2154 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/cc1d2b8828dc4dba9f0ea7d980eb8b24d2b0792c3282725552a56f7c8929459f.0
2155 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/9b59194c025f9e6fc5c1d60ee444be69f14546b7efa4389a30ee6db88fbc207f.0
2156 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/8686d00f5e82bb2343d8154fad3d66afca1420c45e4f63fe5decb6b9f5b84d2b.0
2157 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/6b7ac224bb235b03798c358125eadc5d805445744543c368ebc0a4f7bb7a4328.0
2158 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/dfb89354e0b433989eab276004296575f5b5e3ecb8c700cfcee620765ef0e74d.0
2159 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/ef0656c2dce6c462c2e2591b5c43b76c1fe83ebebbaa778c1194706577c46d5c.0
2160 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/7bfb6c4c45d0dcfbd66456456c5300b3ba83d52f37c5434e3e78baf0b54e5c07.0
2161 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/c61ee02616c8d1c87be89499cb1ebdcd7267e47e51fa53e10578e8935a8b7aa9.0
2162 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/f32062ec857d3d40d3a82359511167113065019d09d10755764aec91ba37bb32.0
2163 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/d678ca3b06ea1872ebb20236ed1099e1b6e1451c51d78ab98d914abead7e4651.0
2164 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/ee4c2e6785e3062be57305190a480ee437f6569471534533dd3524794b125ace.0
2165 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/9a3ee31c30754a89da9280cbff44440e8e974bfac4c815376a0df768ef926590.0
2166 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/334ae045a86998d77ed3fca093d7c43dfd5be53f939d156d9e71a885263739c1.0
2167 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/65b4c081cd081eb8716e435c51abf7882f9aacb47005d77aa336ddf8190f2249.0
2168 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/e2d38a33de7d378bf8a2989ae6db7b20d9168dd9b4c078225ced7aef9154a370.0
2169 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/988ece4e5c191b30ff71dd2ce3fa3dc16f22dd3076702c17e9f3373612765c9c.0
2170 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/272e01e003b0a4ed9b8ebb908d88cf1fbc841f65cf3c5994e99c7e5b10332209.0
2171 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/eb1fd91a2d9b5feba4504c7ee8182ec680121e83a1571a292d52bf7cac12c396.0
2172 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/ea4967bd3dec3fdcf48ba9682777ae09b1be48ae861a5fb55f8650fccb24aeb5.0
2173 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/23653a7282567de2cc678619554153f1aff5409061b2a08ffedf208b10c7fd9f.0
2174 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/6e4b9df052f0c4c0b726301c66e4aedc596a01416268857f3742c1eaf6760c64.0
2175 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/7f82912066c187783d04de0b189314fcde9d33208335827a6d0fa8755637a136.0
2176 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/f07293e9a6dc9a826363cb52fbc0db1f75fbba49814cb626db63affa74dbc9bc.0
2177 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/46df84d2163240ae59efe0c91b94b3d23018daa816de1d44405275e17b5f4e77.0
2178 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/1101fd494d1a226a790d5091f04fae9bcab5543eec8c80a0d3dd8b83a8d31c14.0
2179 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/2f405ef994ff2c7470116d092ec7e9a8833400354479760742e616f800e19831.0
2180 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/5f1efddc7e6c6bb7984813794cd275f0cf46d2bf598ac16cc7adc05c9878eb22.0
2181 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/c641b68789fcc05feb518d6ea7dd5ffa1344c124263e67573c86786766547fa8.0
2182 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/f9b35c5e0adbd9f0084559cd909d57a1dc8928b5c48887a1119d226226664270.0
2183 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/3ab2ef4b9b5f1900ff51f892d531b2abc539f9acfb728c841f35dab93bde160f.0
2184 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/c92c58cb868b0c698c9e24ea9dfb63f1f4587a04fbc0cc6d495058ebb7534f69.0
2185 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/46cb9725c59d409c7e7603f9eab6d2dbd3b29e5d4aef2fb154d5ceda40a33f85.0
2186 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/b4fd15d151bbcf2f299a24ccd2c7e94afae7d6eccf7208f65b06febc5958d95d.0
2187 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/191e06e43ac8a9618a5c1f10178e7cdf6e609f14dc7ec56be2ea89ac19b5e253.0
2188 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/69191aa596bfd2633279e0488152f67565ae47bf3e9e728b9c57376bfd2abdc3.0
2189 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/222870114e13280aa20077b14588e6d2fa8e7a7b347cde4a01553e395fb40a22.0
2190 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/ba3636d73e375a6f16a878752464adaa57a03614dbb3e2d68e26d08d686262c3.0
2191 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/b9b7fb42891473d4906c7acb11f8680565eb02eabce71a8645f917bb1375c0d2.0
2192 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/7d62853edb09b73996a0d4bb369067e45fc229926a8961207596a3162941dccd.0
2193 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/c0bcad354275f905e235af359dd789db4110201a4ef1fd7f8d4aae3563ff06a5.0
2194 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/66397bf25b427e4d910ca117e3ce8afb8e19012403c7a1716696eca2da261884.0
2195 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/487b35586c4591772393a2d2f430d00f97c3d36ad8ee7be784f130249cac7c31.0
2196 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/6b664a4b20fde7754d5448f129532fded9103284aa101b50b79f810246f75a3b.0
2197 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/2752173075a4ef17451a0a3db546956389eff82db209711e4a1fff47e90b6065.0
2198 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/265252b3db2c2501483502b6aadab3ea891f32cae539b5ccc7ef8295b63f4018.0
2199 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/b5cc6b97c28bd853ebf7d853a7b19e4b5018c01eae8823ac537800c2cbb06011.0
2200 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/c9b094709f2b2773b5e5258716df0663b2aee98a6ea47c3cb4040322123cb99c.0
2201 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/7f158d1bfbafe42c7b3118d2b9ea701bda16df10dbdf9c4f2779ea15595a331f.0
2202 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/518548841153bce3488afa3a36ad6e6cbddb4f1689f5e9366ee80e206b6a1ffe.0
2203 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/629e460d17bf23cce5d75bbe8672e037db86d8d757cc4efd9a1a0f53d435425b.0
2204 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/667ddeda218b4f95a47792345550d546e00fe2a52a505437d30608cefd0fc4bd.0
2205 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/20d9f1018284a761162108e9a82d6a73b1fa8a9fd6866a506db77ed07ec5e578.0
2206 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/1f35f42d565dd11860e30c41241c78bc5f06d724117bfc83b3784c66d52e332f.0
2207 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/58cdc6432a1cd95f7f6427744019b59d164384edfc54aa51537d4685f847ba39.0
2208 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/journal
2209 /data/data/com.google.android.googlequicksearchbox/cache/image_manager_disk_cache/61f774ab3a005d56366b267b08b994e5b035ff8eab1e454f00fb2cf7b356a46f.0
2210 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars
2211 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US
2212 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts
2213 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/prons.cache
2214 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/v1539635905559
2215 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/v1539635905559/digest
2216 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/v1539635905559/semantic_fst
2217 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/v1539635905559/grammar_symbols
2218 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/v1539635905559/semantic_symbols
2219 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/v1539635905559/metadata
2220 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contacts/v1539635905559/grammar_clg
2221 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands
2222 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/v1536705472984
2223 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/v1536705472984/grammar_clg
2224 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/v1536705472984/semantic_fst
2225 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/v1536705472984/semantic_symbols
2226 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/v1536705472984/digest
2227 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/v1536705472984/metadata
2228 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/v1536705472984/grammar_symbols
2229 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/hands_free_commands/prons.cache
2230 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/music_names
2231 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/music_names/v1536705480879
2232 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/music_names/v1536705480879/metadata
2233 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/music_names/v1536705480879/SONG_NAME.fst
2234 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/music_names/v1536705480879/SONG_NAME.syms
2235 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/music_names/v1536705480879/digest
2236 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contact_names
2237 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contact_names/v1539635914600
2238 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contact_names/v1539635914600/CONTACT_NAME.fst
2239 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contact_names/v1539635914600/CONTACT_NAME.syms
2240 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contact_names/v1539635914600/digest
2241 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/contact_names/v1539635914600/metadata
2242 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/app_names
2243 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/app_names/v1543480552712
2244 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/app_names/v1543480552712/APP_NAME.fst
2245 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/app_names/v1543480552712/digest
2246 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/app_names/v1543480552712/metadata
2247 /data/data/com.google.android.googlequicksearchbox/cache/g3_grammars/en-US/app_names/v1543480552712/APP_NAME.syms
2248 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async
2249 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache
2250 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/79b5269c206115a4_0
2251 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/aa9db037f918da1f_0
2252 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/aebae57f6f7dcdb9_0
2253 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e446f170a9c613a1_0
2254 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/2f06680d22ff6fbf_0
2255 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ffa3f495612db016_0
2256 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/69c20684e88c955b_0
2257 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ef65bf506ba3e339_0
2258 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/014821f96953c508_0
2259 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/1180e087d9bd1160_0
2260 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/3b36cd7b2f6df416_0
2261 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e5701f55e9ce22c8_0
2262 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/9ec568d6b3dc0762_0
2263 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/88f57d1088993219_0
2264 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/83fd8318538fbe29_0
2265 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/22930ed83887868c_0
2266 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/333bf7ac47cc9770_0
2267 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/adfd903f6a8ce876_0
2268 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/2a1237e13688c120_0
2269 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/3f3f18bf8e704931_0
2270 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/b8262fc8c9591057_0
2271 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/59829c5897cb9d93_0
2272 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/index-dir
2273 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/index-dir/the-real-index
2274 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/feb5af6bca039e09_0
2275 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/0050e1bcb6d6546c_0
2276 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/3a3d22ec4fc7ad21_0
2277 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/5f269f49d811cd82_0
2278 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e1cf52389fbebceb_0
2279 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/359582e09cf26c7a_0
2280 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/964347070fc23ea0_0
2281 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/fb7d48b4e068afda_0
2282 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/a5c586e8f0aeb850_0
2283 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/37fadb6203e4e379_0
2284 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/a7c25e80d95ef15d_0
2285 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/a11922fc39ec0249_0
2286 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/bebb870e573c852c_0
2287 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/89c95cdfc9b59f48_0
2288 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/fcb3fff3117a2d12_0
2289 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/5c48229cf8e35d0b_0
2290 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/55a3abf82b2a626c_0
2291 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/f79ff1a77d9e9492_0
2292 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ca9ccf019443fb16_0
2293 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/986246894e9084ec_0
2294 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e546ff051d5dbafc_0
2295 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/23b6960b741da560_0
2296 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/8c9509f47aa07ed8_0
2297 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/81be3f3a1ebb3222_0
2298 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/4edb09d9737acff2_0
2299 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e89950485ea68183_0
2300 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e40df7fec15afae9_0
2301 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/cc338158aa28d723_0
2302 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/4797a2fb8c7eac6b_0
2303 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/411f64d386b7c4fe_0
2304 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/29f6d5d8b27eb0c5_0
2305 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e99ae68f3e468751_0
2306 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/502dafda143b5a74_0
2307 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/d1783d0a170fdb8e_0
2308 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ac27a389f7bf6b67_0
2309 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/40300177b5c0050d_0
2310 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/4a8de756f1428237_0
2311 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e029cf1b0932611f_0
2312 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/c69ff5c7e450ab22_0
2313 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/bdfd0aa008d40005_0
2314 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/40dd89dd968602d3_0
2315 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/d04eb6456f31d2f7_0
2316 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ff4e7b79b6327627_0
2317 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/b136f3771ffb9958_0
2318 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/207bb56723cc5c3a_0
2319 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/95035b9448e65cf2_0
2320 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/73afbe7f6b7a496c_0
2321 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/84b41c998e542199_0
2322 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/d68d127f97a27059_0
2323 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/037a0f2e4460355f_0
2324 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/da584b3cb202e078_0
2325 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/2d6c5245e29028b2_0
2326 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ca9b25d228896196_0
2327 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/0e2708cf50936235_0
2328 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ab39283d30a39dd1_0
2329 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/f721910d7c288b54_0
2330 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/e1cd683779c2ea08_0
2331 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/d1a8c9a323296d5b_0
2332 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/4821c08320e603ae_0
2333 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/01a2afcf422b3b4f_0
2334 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/d41f0a4d475402fd_0
2335 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/fcacc70d27c27f8b_0
2336 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/f76d072b8c546a89_0
2337 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/aff6b5b6e20cc2fa_0
2338 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/8037b4d4c7774071_0
2339 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/index
2340 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/1e6d9e3ecd002bc9_0
2341 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/3cfe648fbdd026a7_0
2342 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/ab5d3ea4f0904068_0
2343 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/9a785469b604c8af_0
2344 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/472d78242cce2d22_0
2345 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/503a7645e7f2d973_0
2346 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/593a42d396c32634_0
2347 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/b6ee82fb12843073_0
2348 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/3561efa2281c73ed_0
2349 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/318755c427839e86_0
2350 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/3ef890a79ddb7e0c_0
2351 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/d9772c6ee701ad39_0
2352 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/5b3eff799688e021_0
2353 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/30bb71565ae0cc27_0
2354 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/54afe61c6fcf0e3f_0
2355 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/8c9d078e6dbc501d_0
2356 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/32a4f6fc17306385_0
2357 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/0111bfd7286ca658_0
2358 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/55ccaf33bd76fb46_0
2359 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/65b80b5a552aaeaf_0
2360 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/30fffcc41f7846bf_0
2361 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/5377846224f95fc9_0
2362 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/f9c93b74a177706b_0
2363 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/94239554b50b59b5_0
2364 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/14ced047ba93cdd3_0
2365 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/2ceea49fe8c9e2fe_0
2366 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/disk_cache/3ec7cdbc127eae35_0
2367 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/version
2368 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/prefs
2369 /data/data/com.google.android.googlequicksearchbox/cache/cronet-async/prefs/local_prefs.json
2370 /data/data/com.google.android.googlequicksearchbox/cache/si
2371 /data/data/com.google.android.googlequicksearchbox/databases
2372 /data/data/com.google.android.googlequicksearchbox/databases/icing-mdh.db-wal
2373 /data/data/com.google.android.googlequicksearchbox/databases/google_app_measurement.db-shm
2374 /data/data/com.google.android.googlequicksearchbox/databases/icing-mdh.db-shm
2375 /data/data/com.google.android.googlequicksearchbox/databases/google_app_measurement_local.db
2376 /data/data/com.google.android.googlequicksearchbox/databases/google_app_measurement_local.db-wipecheck
2377 /data/data/com.google.android.googlequicksearchbox/databases/google_app_measurement.db-wal
2378 /data/data/com.google.android.googlequicksearchbox/databases/google_app_measurement.db-wipecheck
2379 /data/data/com.google.android.googlequicksearchbox/databases/google_app_measurement.db
2380 /data/data/com.google.android.googlequicksearchbox/databases/icing-mdh.db-wipecheck
2381 /data/data/com.google.android.googlequicksearchbox/databases/launcher.db
2382 /data/data/com.google.android.googlequicksearchbox/databases/launcher.db-wal
2383 /data/data/com.google.android.googlequicksearchbox/databases/icing-mdh.db
2384 /data/data/com.google.android.googlequicksearchbox/databases/launcher.db-shm
2385 /data/data/com.google.android.googlequicksearchbox/shared_prefs
2386 /data/data/com.google.android.googlequicksearchbox/shared_prefs/AccountSwitcherDrawerPresenter.Prefs.xml
2387 /data/data/com.google.android.googlequicksearchbox/shared_prefs/com.google.android.gms.appid.xml
2388 /data/data/com.google.android.googlequicksearchbox/shared_prefs/consecutive_crash_stats.xml
2389 /data/data/com.google.android.googlequicksearchbox/shared_prefs/uncaught_exception_handler_stats.xml
2390 /data/data/com.google.android.googlequicksearchbox/shared_prefs/VoiceInteractionService.xml
2391 /data/data/com.google.android.googlequicksearchbox/shared_prefs/interactor_process_uncaught_exception_handler_stats.xml
2392 /data/data/com.google.android.googlequicksearchbox/shared_prefs/WebViewChromiumPrefs.xml
2393 /data/data/com.google.android.googlequicksearchbox/shared_prefs/com.android.launcher3.managedusers.prefs.xml
2394 /data/data/com.google.android.googlequicksearchbox/shared_prefs/com.android.launcher3.prefs.xml
2395 /data/data/com.google.android.googlequicksearchbox/shared_prefs/GEL.GSAPrefs.xml
2396 /data/data/com.google.android.googlequicksearchbox/shared_prefs/com.google.android.gms.measurement.prefs.xml
2397 /data/data/com.google.android.googlequicksearchbox/shared_prefs/ThrottlingLogger.xml
2398 /data/data/com.google.android.googlequicksearchbox/shared_prefs/default_process_uncaught_exception_handler_stats.xml
2399 )F1L3N4M3";
2400 
2401 #else
2402 
2403     static const char* kInodeValues = R"1N0D3(
2404 66323@1117133
2405 66323@1127134
2406 66323@1137135
2407 66323@1137136
2408 66323@1137137
2409 )1N0D3";
2410 
2411     const char* kPathNames = R"F1L3N4M3(
2412 /
2413 /data/
2414 /data/data/
2415 /data/data/file
2416 /data/data/last_file
2417 )F1L3N4M3";
2418 
2419 #endif
2420 
2421 
2422     std::vector<std::string> inode_values = ParseLines(kInodeValues);
2423     std::vector<std::string> path_names = ParseLines(kPathNames);
2424 
2425     std::vector<Inode> inodes = ParseInodes(inode_values);
2426 
2427     return PathEntryTree{ PathEntry::Zip(inodes, path_names) };
2428 }
2429 
2430 class FakeSystemCall : public SystemCall {
2431  public:
2432   // stat(2)
stat(const char * pathname,struct stat * statbuf)2433   virtual int stat(const char *pathname, struct stat *statbuf) override {
2434     if (pathname == nullptr || statbuf == nullptr) {
2435       errno = EINVAL;
2436       return -1;
2437     }
2438 
2439     std::optional<PathEntry> maybe_path_entry = path_entries_.GetEntryFor(pathname);
2440 
2441     if (!maybe_path_entry) {
2442       errno = ENOENT;
2443       return -1;
2444     }
2445 
2446     memset(statbuf, 0, sizeof(*statbuf));
2447 
2448     Inode inode = maybe_path_entry->inode;
2449     statbuf->st_dev = makedev(static_cast<int>(inode.device_major),
2450                               static_cast<int>(inode.device_minor));
2451     statbuf->st_ino = static_cast<ino_t>(inode.inode);
2452 
2453     return 0;
2454   }
2455 
2456   static constexpr bool debug{false};
2457 
2458 #define FS_LOG_DEBUG if (debug) LOG(DEBUG)
2459 
2460   // opendir(3)
opendir(const char * name)2461   virtual DIR *opendir(const char *name) override {
2462 
2463     FS_LOG_DEBUG << "opendir(" << name << ")";
2464 
2465     std::string name_str{name};
2466     if (path_entries_.HasDirectory(name_str)) {
2467         CHECK(!state_.open_);
2468 
2469         std::vector<PathEntry> children = path_entries_.OpenDirectory(name_str);
2470 
2471         state_ = State::Open(name_str, std::move(children));
2472 
2473         FS_LOG_DEBUG << "opendir - success, state address: " << &state_;
2474 
2475         return get_state_as_dir();
2476     }
2477 
2478     FS_LOG_DEBUG << "opendir - no matching entry, scanned " << path_entries_.size();
2479 
2480     // TODO. errno.
2481     errno = EINVAL;
2482     return nullptr;
2483   }
2484 
2485   // readdir(3)
readdir(DIR * dirp)2486   virtual struct dirent *readdir(DIR *dirp) override {
2487     DCHECK(dirp != nullptr);
2488     // We could also errno=EBADF but this seems more apropro to test.
2489 
2490     State* state = dir_to_state(dirp);
2491     (void) state;
2492     DCHECK(state != nullptr);
2493 
2494     std::optional<PathEntry> path_entry_opt = state->ReadDir();
2495 
2496     if (!path_entry_opt) {
2497       FS_LOG_DEBUG << "readdir(" << &state << ") - no children left ";
2498 
2499       // No more children left. We have exhausted them all.
2500       return nullptr;
2501     }
2502 
2503     PathEntry path_entry = *path_entry_opt;
2504 
2505     FS_LOG_DEBUG << "readdir(" << &state << ") - called for " << path_entry.path;
2506 
2507     // TODO. impelment this.
2508     static struct dirent dir_ent{};
2509 
2510     // Clear it again.
2511     memset(&dir_ent, 0, sizeof(dir_ent));
2512 
2513     dir_ent.d_ino = path_entry.inode.inode;
2514 
2515     FS_LOG_DEBUG << "readdir(" << &state << ") - children check" << path_entry.path;
2516 
2517     // Is this a file (no children) or a directory (some children)?
2518     //
2519     // In reality some directories might be empty too, but lets not worry about it yet.
2520     std::vector<PathEntry> children = path_entries_.OpenDirectory(path_entry.path);
2521 
2522     if (children.empty()) {
2523       dir_ent.d_type = DT_REG;
2524     } else {
2525       dir_ent.d_type = DT_DIR;
2526     }
2527 
2528     // the d_name must be just the final name component of a path.
2529     // Do not include the full path.
2530 
2531     std::string_view name_view = path_entry.path.Name();
2532     DCHECK_LT(name_view.size(), sizeof(dir_ent.d_name));
2533 
2534     std::copy(name_view.begin(),
2535               name_view.end(),
2536               &dir_ent.d_name[0]);
2537     dir_ent.d_name[name_view.size()] = '\0';
2538 
2539     FS_LOG_DEBUG << "readdir(" << &state << ") - return , d_name=\"" << dir_ent.d_name << "\""
2540                  << ", d_type=" << (dir_ent.d_type == DT_REG ? "DT_REG" : "DT_DIR");
2541 
2542     return &dir_ent;
2543   }
2544 
2545   // closedir(3)
closedir(DIR * dirp)2546   virtual int closedir(DIR *dirp) override {
2547     CHECK(dirp != nullptr);
2548     State* state = dir_to_state(dirp);
2549     state->Close();
2550 
2551     return 0;
2552   }
2553 
FakeSystemCall()2554   FakeSystemCall() {
2555     path_entries_ = CreateFakePathEntries();
2556   }
2557 
2558  private:
2559   struct State {
2560     std::string name_;
2561     bool open_{false};
2562     std::vector<PathEntry> children;
2563 
OpenFakeSystemCall::State2564     static State Open(std::string name, std::vector<PathEntry> children) {
2565       return State{name, /*open*/true, std::move(children)};
2566     }
2567 
ReadDirFakeSystemCall::State2568     std::optional<PathEntry> ReadDir() {
2569       if (children.empty()) {
2570         return {};
2571       }
2572 
2573       PathEntry last = children.back();
2574       children.pop_back();
2575 
2576       return { std::move(last) };
2577     }
2578 
CloseFakeSystemCall::State2579     void Close() {
2580       CHECK(open_);
2581       open_ = false;
2582     }
2583   };
2584 
get_state_as_dir()2585   DIR* get_state_as_dir() {
2586     return reinterpret_cast<DIR*>(reinterpret_cast<void*>(&state_));
2587   }
2588 
dir_to_state(DIR * dirp)2589   State* dir_to_state(DIR* dirp) {
2590     return reinterpret_cast<State*>(reinterpret_cast<void*>(dirp));
2591   }
2592 
2593   State state_;
2594 
2595   PathEntryTree path_entries_;
2596 };
2597 
2598 class MockSystemCall : public SystemCall {
2599  public:
INJECT(MockSystemCall ())2600   INJECT(MockSystemCall()) {
2601     // Delegate calls to a fake (see the googlemock CookBook for more details).
2602     // https://github.com/google/googletest/blob/master/googlemock/docs/CookBook.md#delegating-calls-to-a-fake
2603     DelegateToFake();
2604 
2605     WorkAroundForNiceMock();
2606   }
2607 
~MockSystemCall()2608   ~MockSystemCall() {
2609   }
2610 
2611   MOCK_METHOD2(stat, int(const char *, struct stat *));
2612   MOCK_METHOD1(opendir, DIR*(const char *));
2613   MOCK_METHOD1(readdir, struct dirent*(DIR*));
2614   MOCK_METHOD1(closedir, int(DIR*));
2615 
2616   // Delegates the default actions of the methods to a FakeSystemCall object.
2617   // This must be called *before* the custom ON_CALL() statements.
DelegateToFake()2618   void DelegateToFake() {
2619     ON_CALL(*this, stat(_,_))
2620         .WillByDefault(Invoke(&fake_, &FakeSystemCall::stat));
2621     ON_CALL(*this, opendir(_))
2622         .WillByDefault(Invoke(&fake_, &FakeSystemCall::opendir));
2623     ON_CALL(*this, readdir(_))
2624         .WillByDefault(Invoke(&fake_, &FakeSystemCall::readdir));
2625     ON_CALL(*this, closedir(_))
2626         .WillByDefault(Invoke(&fake_, &FakeSystemCall::closedir));
2627   }
2628 
2629   void WorkAroundForNiceMock();
2630 
2631  private:
2632   FakeSystemCall fake_;
2633 };
2634 
2635 // Don't print any warnings when methods are executed without EXPECT_CALL.
2636 //using NiceMockSystemCall = NiceMock<MockSystemCall>;
2637 
2638 // Can't use NiceMock<MockSystemCall> here, fails with this compilation error
2639 //
2640 // external/google-fruit/include/fruit/impl/injection_errors.h:107:3: error: static_assert failed due to requirement 'AlwaysFalse<NiceMock<MockSystemCall> >::value' "C::Inject is a signature, but does not return a C. Maybe the class C has no Inject typedef and inherited the base class' one? If that's not the case, make sure it returns just C, not C* or other types."
2641 using NiceMockSystemCall = MockSystemCall;
2642 
WorkAroundForNiceMock()2643 void MockSystemCall::WorkAroundForNiceMock() {
2644   // Should be able to use NiceMock instead, but fruit is having problems compiling.
2645   EXPECT_CALL(*this, stat).Times(AtLeast(0));
2646   EXPECT_CALL(*this, opendir).Times(AtLeast(0));
2647   EXPECT_CALL(*this, readdir).Times(AtLeast(0));
2648   EXPECT_CALL(*this, closedir).Times(AtLeast(0));
2649 }
2650 
getTestComponents()2651 fruit::Component<SearchDirectories, NiceMockSystemCall> getTestComponents() {
2652     return fruit::createComponent()
2653         .bind<SystemCall, NiceMockSystemCall>();
2654 }
2655 
2656 // TODO: there might be a helper or similar to do this instead.
2657 template <typename T>
subscribe_drain(std::pair<rxcpp::observable<T>,std::unique_ptr<SearchDirectories::RxAnyConnectable>> pair)2658 static std::vector<T> subscribe_drain(std::pair<rxcpp::observable<T>,
2659                                                 std::unique_ptr<SearchDirectories::RxAnyConnectable>> pair) {
2660   rxcpp::observable<T>& obs = pair.first;
2661   std::unique_ptr<SearchDirectories::RxAnyConnectable>& connectable_ptr = pair.second;
2662 
2663   std::vector<T> vec;
2664 
2665   obs.subscribe([&vec](auto&& x) {
2666     vec.push_back(IORAP_FORWARD_LAMBDA(x));
2667   });
2668 
2669   CHECK(connectable_ptr != nullptr);
2670 
2671   // Execute above lambda, blocking until all values are drained.
2672   connectable_ptr->connect();
2673 
2674   return vec;
2675 }
2676 
2677 struct SearchDirectoriesParam {
2678   std::vector<std::string> root_directories;
2679   std::vector<Inode> search_inodes;
2680   std::vector<InodeResult> expected_results;
2681 };
2682 
2683 template <typename It>
iterator_to_stream(std::ostream & os,It begin,It end)2684 std::ostream& iterator_to_stream(std::ostream& os, It begin, It end) {
2685   os << "{";
2686   while (begin != end) {
2687     os << *begin;
2688     os << ",";
2689 
2690     ++begin;
2691   }
2692   os << "}";
2693 
2694   return os;
2695 }
2696 
2697 template <typename T>
container_to_stream(std::ostream & os,T && c)2698 std::ostream& container_to_stream(std::ostream& os, T&& c) {
2699   return iterator_to_stream(os, c.begin(), c.end());
2700 }
2701 
operator <<(std::ostream & os,const SearchDirectoriesParam & p)2702 std::ostream& operator<<(std::ostream& os, const SearchDirectoriesParam& p) {
2703   os << "{";
2704   os << "root_directories:";
2705   container_to_stream(os, p.root_directories);
2706   os << ", ";
2707   os << "search_inodes:";
2708   container_to_stream(os, p.search_inodes) << ", ";
2709   os << "expected_results:";
2710   container_to_stream(os, p.expected_results);
2711   os << "}";
2712   return os;
2713 }
2714 
2715 struct SearchDirectoriesTest :
2716     public ::testing::TestWithParam<SearchDirectoriesParam> {
2717 
SetUpTestCaseSearchDirectoriesTest2718   static void SetUpTestCase() {
2719     ConfigureLogging();
2720   }
2721 
SetUpSearchDirectoriesTest2722   virtual void SetUp() override {
2723     auto pair =
2724         search.FindFilenamesFromInodesPair(GetParam().root_directories,
2725                                            GetParam().search_inodes,
2726                                            SearchMode::kInProcessDirect);
2727 
2728     actual = subscribe_drain(std::move(pair));
2729     expected = GetParam().expected_results;
2730   }
2731 
TearDownSearchDirectoriesTest2732   virtual void TearDown() override {
2733     // TODO.
2734   }
2735 
2736  protected:
2737   fruit::Injector<SearchDirectories, NiceMockSystemCall> injector{getTestComponents};
2738 
2739   SearchDirectories& search = injector.get<SearchDirectories&>();
2740   MockSystemCall& mock_syscall = injector.get<NiceMockSystemCall&>();
2741 
2742   std::vector<InodeResult> actual;
2743   std::vector<InodeResult> expected;
2744 };
2745 
TEST_P(SearchDirectoriesTest,ElementsAreArrayMatcher)2746 TEST_P(SearchDirectoriesTest, ElementsAreArrayMatcher) {
2747   EXPECT_THAT(actual, ElementsAreArray(expected));
2748 }
2749 
MakeEmptyInodes(std::vector<std::string> root_dirs)2750 auto MakeEmptyInodes(std::vector<std::string> root_dirs) {
2751   return SearchDirectoriesParam{root_dirs, /*inodes*/{}, /*actual*/{}};
2752 }
2753 
2754 // When are are 0 inodes to search for, the results will be empty.
2755 INSTANTIATE_TEST_CASE_P(EmptyResults,
2756                         SearchDirectoriesTest,
2757                         ::testing::Values(
2758                             MakeEmptyInodes(/*root_dirs*/{}),
2759                             MakeEmptyInodes(/*root_dirs*/{""}),
2760                             MakeEmptyInodes(/*root_dirs*/{"/"}),
2761                             MakeEmptyInodes(/*root_dirs*/{"/abc"})
2762                         ));
2763 
2764 
MakeAllFailInodes(std::vector<std::string> root_dirs,std::vector<Inode> inodes)2765 auto MakeAllFailInodes(std::vector<std::string> root_dirs, std::vector<Inode> inodes) {
2766   std::vector<InodeResult> results;
2767   for (const Inode& inode : inodes) {
2768     results.push_back(InodeResult::makeFailure(inode, InodeResult::kCouldNotFindFilename));
2769   }
2770 
2771   return SearchDirectoriesParam{root_dirs, inodes, results};
2772 }
2773 
2774 // TODO: fixme
2775 
2776 #if 1
2777 
2778 // When none of the inodes can be found, all results will be failing results.
2779 INSTANTIATE_TEST_CASE_P(AllResultsAreErrorCouldNotFindFilename,
2780                         SearchDirectoriesTest,
2781                         ::testing::Values(
2782                             // TODO: why is empty root dir failing?
2783                             // MakeAllFailInodes(/*root_dirs*/{}, {Inode{1,2,3}}),
2784                             MakeAllFailInodes(/*root_dirs*/{"/"}, {Inode{1,2,3}}),
2785                             MakeAllFailInodes(/*root_dirs*/{"/data"}, {Inode{1,2,3}}),
2786                             MakeAllFailInodes(/*root_dirs*/{"/data/data"}, {Inode{1,2,3}})
2787                         ));
2788 
MakeAllPassInodes(std::vector<std::string> root_dirs,std::vector<std::string> inodes,std::vector<std::string> paths)2789 auto MakeAllPassInodes(std::vector<std::string> root_dirs, std::vector<std::string> inodes, std::vector<std::string> paths) {
2790   std::vector<InodeResult> results;
2791 
2792   std::vector<Inode> inodes_actual;
2793 
2794   size_t i = 0;
2795   for (const std::string& inode_str : inodes) {
2796     Inode inode;
2797     std::string error_msg;
2798 
2799     CHECK(Inode::Parse(inode_str, &inode, &error_msg));
2800 
2801     inodes_actual.push_back(inode);
2802 
2803     std::string& path = paths[i];
2804     results.push_back(InodeResult::makeSuccess(inode, path));
2805 
2806     ++i;
2807   }
2808 
2809   return SearchDirectoriesParam{root_dirs, inodes_actual, results};
2810 }
2811 
2812 // Find all the inodes. Yay.
2813 INSTANTIATE_TEST_CASE_P(AllResultsAreSuccess,
2814                         SearchDirectoriesTest,
2815                         ::testing::Values(
2816                             MakeAllPassInodes(/*root_dirs*/{"/"}, {"66323@1127133"}, {"/data"})
2817                         ));
2818 
2819 #endif
2820