1 /*
2  * Copyright (c) 2024 Huawei Device Co., Ltd.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  *     http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include "core/components_ng/syntax/repeat_virtual_scroll_caches.h"
17 
18 #include <cstdint>
19 #include <optional>
20 #include <unordered_map>
21 #include <unordered_set>
22 
23 #include "base/log/log_wrapper.h"
24 #include "base/memory/referenced.h"
25 #include "core/components_ng/base/frame_node.h"
26 #include "core/components_ng/base/view_stack_processor.h"
27 #include "core/pipeline/base/element_register.h"
28 
29 namespace OHOS::Ace::NG {
30 
operator ()(const std::string & left,const std::string & right) const31 bool KeySorterClass::operator()(const std::string& left, const std::string& right) const
32 {
33     return virtualScroll_->CompareKeyByIndexDistance(left, right);
34 }
35 
RepeatVirtualScrollCaches(const std::map<std::string,std::pair<bool,uint32_t>> & cacheCountL24ttype,const std::function<void (uint32_t)> & onCreateNode,const std::function<void (const std::string &,uint32_t)> & onUpdateNode,const std::function<std::list<std::string> (uint32_t,uint32_t)> & onGetKeys4Range,const std::function<std::list<std::string> (uint32_t,uint32_t)> & onGetTypes4Range)36 RepeatVirtualScrollCaches::RepeatVirtualScrollCaches(
37     const std::map<std::string, std::pair<bool, uint32_t>>& cacheCountL24ttype,
38     const std::function<void(uint32_t)>& onCreateNode,
39     const std::function<void(const std::string&, uint32_t)>& onUpdateNode,
40     const std::function<std::list<std::string>(uint32_t, uint32_t)>& onGetKeys4Range,
41     const std::function<std::list<std::string>(uint32_t, uint32_t)>& onGetTypes4Range)
42     : cacheCountL24ttype_(cacheCountL24ttype), // each ttype incl default has own L2 cache size
43       // request TS to create new sub-tree for given index or update existing
44       // update subtree cached for (old) index
45       // API might need to change to tell which old item to update
46       onCreateNode_(onCreateNode), onUpdateNode_(onUpdateNode), onGetTypes4Range_(onGetTypes4Range),
47       onGetKeys4Range_(onGetKeys4Range)
48 {
49 }
50 
GetKey4Index(uint32_t index,bool allowFetch)51 std::optional<std::string> RepeatVirtualScrollCaches::GetKey4Index(uint32_t index, bool allowFetch)
52 {
53     if (key4index_.find(index) != key4index_.end()) {
54         return key4index_[index];
55     }
56 
57     if (!allowFetch) {
58         return std::nullopt;
59     }
60 
61     // need to rebuild L1 after fetch ?
62     const bool rebuildL1 =
63         key4index_.size() == 0 && HasOverlapWithLastActiveRange(index, index);
64 
65     // allow to fetch extended range of keys if rebuildL1 is needed
66     FetchMoreKeysTTypes(index, index, rebuildL1 == true);
67 
68     if (rebuildL1) {
69         // check for each L1 entry if its key is includes in newly received keys
70         // only keep these in L1
71         RebuildL1WithKey([&](const std::string &key) { return index4Key_.find(key) != index4Key_.end(); });
72     }
73 
74     return GetKey4Index(index, false);
75 }
76 
77 /**
78  * does given range overlap the last active range?
79  */
HasOverlapWithLastActiveRange(uint32_t from,uint32_t to)80 bool RepeatVirtualScrollCaches::HasOverlapWithLastActiveRange(uint32_t from, uint32_t to)
81 {
82     const auto lastFrom = lastActiveRanges_[0].first;
83     const auto lastTo = lastActiveRanges_[0].second;
84     if (lastFrom <= lastTo) {
85         return to >= lastFrom && from <= lastTo;
86     } else {
87         return to <= lastTo || to >= lastFrom || from <= lastTo || from >= lastFrom;
88     }
89 }
90 
91 /**
92  * get more index -> key and index -> ttype from TS side
93  */
FetchMoreKeysTTypes(uint32_t from,uint32_t to,bool allowFetchMore)94 bool RepeatVirtualScrollCaches::FetchMoreKeysTTypes(uint32_t from, uint32_t to, bool allowFetchMore)
95 {
96     if (from > to) {
97         return false;
98     }
99 
100     if (allowFetchMore) {
101         // following a key4index_/ttype4index_ purge fetch the whole range
102         const auto rangeStart = lastActiveRanges_[0].first;
103         const auto rangeEnd = lastActiveRanges_[0].second;
104 
105         if (rangeStart <= rangeEnd) {
106             return FetchMoreKeysTTypes(from, std::max(to, rangeEnd), false);
107         } else {
108             const bool v1 = FetchMoreKeysTTypes(0, rangeEnd, false);
109             const bool v2 = FetchMoreKeysTTypes(rangeStart, std::numeric_limits<int>::max(), false);
110             return v1 || v2;
111         }
112     }
113 
114     TAG_LOGD(AceLogTag::ACE_REPEAT, "from:%{public}d, to:%{public}d",
115         static_cast<int32_t>(from),  static_cast<int32_t>(to));
116 
117     // always request the same range for keys and ttype
118     // optimism by merging the two calls into one
119     const std::list<std::string> keysFrom = onGetKeys4Range_(from, to);
120     const std::list<std::string> ttypesFrom = onGetTypes4Range_(from, to);
121     if ((keysFrom.size() == 0) || (ttypesFrom.size() == 0) || (keysFrom.size() != ttypesFrom.size())) {
122         TAG_LOGE(AceLogTag::ACE_REPEAT,
123             "fail to fetch keys and/or ttyypes: requested range %{public}d - %{public}d. "
124             "Received number of keys: %{public}d, of ttypes: %{public}d",
125             static_cast<int32_t>(from), static_cast<int32_t>(to),
126             static_cast<int32_t>(keysFrom.size()), static_cast<int32_t>(ttypesFrom.size()));
127             return false;
128     }
129     TAG_LOGD(AceLogTag::ACE_REPEAT,
130         "Received number of keys: %{public}d, of ttypes: %{public}d:",
131         static_cast<int32_t>(keysFrom.size()), static_cast<int32_t>(ttypesFrom.size()));
132 
133     // fill-in index <-> key maps
134     auto from1 = from;
135     for (const auto& key : keysFrom) {
136         key4index_[from1] = key;
137         index4Key_[key] = from1;
138 
139         const auto cacheItemIter = node4key_.find(key);
140         if (cacheItemIter != node4key_.end()) {
141             // TS onGetKeys4Range_ has made any needed updates for this key -> UINode
142             cacheItemIter->second.isValid = true;
143         }
144         from1++;
145     }
146 
147     // fill-in index <-> ttype maps
148     from1 = from;
149     for (const auto& ttype : ttypesFrom) {
150         ttype4index_[from1] = ttype;
151         index4ttype_[ttype] = from1;
152         from1++;
153     }
154 
155     // false when nothing was fetched
156     return from1 > from;
157 }
158 
159 // get UINode for given index without create.
GetCachedNode4Index(uint32_t index)160 RefPtr<UINode> RepeatVirtualScrollCaches::GetCachedNode4Index(uint32_t index)
161 {
162     TAG_LOGD(AceLogTag::ACE_REPEAT, "index %{public}d", static_cast<int32_t>(index));
163 
164     const auto key = GetKey4Index(index, false);
165     const auto node4Key = GetCachedNode4Key(key);
166     const auto& ttype = GetTType4Index(index);
167 
168     if (!key.has_value() || !ttype.has_value() || !node4Key.has_value()) {
169         TAG_LOGD(AceLogTag::ACE_REPEAT, "no CachedItem for index %{public}d", static_cast<int32_t>(index));
170         return nullptr;
171     }
172     auto uiNode = node4Key.value().item;
173     const auto& node4Ttype = GetCachedNode4Key4Ttype(key, ttype);
174     if (node4Ttype != uiNode) {
175     // STATE_MGMT_NOTE check if the node4Ttype is a nullptr instead
176         // UINode for key exists, but the requested ttype is different from the ttype used
177         // to render the returned UINode
178         // STATE_MGMT_NOTE how to handle ?
179         TAG_LOGD(AceLogTag::ACE_REPEAT,
180             "index %{public}d -> %{public}s, templateId %{public}s, "
181             "found UINode %{public}s that has been created from a different template.",
182             static_cast<int32_t>(index), key.value().c_str(),
183             ttype.value().c_str(), DumpUINode(uiNode).c_str());
184         // mark as not valid, needs fresh render or update other UINode
185         // what to do with existing item?
186         // STATE_MGMT_NOTE: Can not just del like this?
187         // how to fix: call to RepeatVirtualScrollNode::DropFromL1
188         node4key_.erase(key.value());
189         activeNodeKeysInL1_.erase(key.value());
190         return nullptr;
191     }
192 
193     if (!node4Key.value().isValid) {
194         // impossible situation: TS onKeyIndex shoul;d have updated repeatItem.index already!
195         TAG_LOGW(AceLogTag::ACE_REPEAT,
196             "index %{public}d -> %{public}s, templateId %{public}s, "
197             "found UINode %{public}s marked inValid. Internal error!",
198             static_cast<int32_t>(index), key.value().c_str(), ttype.value().c_str(), DumpUINode(uiNode).c_str());
199         UpdateSameKeyItem(key.value(), index);
200         node4key_[key.value()].isValid = true;
201     }
202 
203     return node4Key.value().item;
204 }
205 
AddKeyToL1(const std::string & key,bool shouldTriggerReuse)206 void RepeatVirtualScrollCaches::AddKeyToL1(const std::string& key, bool shouldTriggerReuse)
207 {
208     TAG_LOGD(AceLogTag::ACE_REPEAT, "AddKeyToL1 key:%{public}s", key.c_str());
209     activeNodeKeysInL1_.emplace(key);
210 
211     if (!shouldTriggerReuse) {
212         return;
213     }
214 
215     RefPtr<UINode> child;
216     const auto& it = node4key_.find(key);
217     if (it != node4key_.end() && it->second.item) {
218         child = it->second.item->GetFrameChildByIndex(0, false);
219     }
220     CHECK_NULL_VOID(child);
221 
222     // if node is already reused, do nothing
223     if (reusedNodeIds_.emplace(child->GetId()).second == false) {
224         return;
225     }
226 
227     // fire OnReuse to trigger node pattern handlers
228     TAG_LOGD(AceLogTag::ACE_REPEAT, "OnReuse() nodeId:%{public}d key:%{public}s", child->GetId(), key.c_str());
229     child->OnReuse();
230 }
231 
AddKeyToL1WithNodeUpdate(const std::string & key,uint32_t index,bool shouldTriggerRecycle)232 void RepeatVirtualScrollCaches::AddKeyToL1WithNodeUpdate(const std::string& key, uint32_t index,
233     bool shouldTriggerRecycle)
234 {
235     onUpdateNode_(key, index);
236     AddKeyToL1(key, shouldTriggerRecycle);
237 }
238 
RemoveKeyFromL1(const std::string & key,bool shouldTriggerRecycle)239  void RepeatVirtualScrollCaches::RemoveKeyFromL1(const std::string& key, bool shouldTriggerRecycle)
240  {
241     TAG_LOGD(AceLogTag::ACE_REPEAT, "RemoveKeyFromL1 key:%{public}s", key.c_str());
242     activeNodeKeysInL1_.erase(key);
243 
244     if (!shouldTriggerRecycle) {
245         return;
246     }
247 
248     RefPtr<UINode> child;
249     const auto& it = node4key_.find(key);
250     if (it != node4key_.end() && it->second.item) {
251         child = it->second.item->GetFrameChildByIndex(0, false);
252     }
253     CHECK_NULL_VOID(child);
254 
255     // if node is not reused currently, do nothing
256     if (reusedNodeIds_.erase(child->GetId()) == 0) {
257         return;
258     }
259 
260     // fire OnRecycle to trigger node pattern handlers
261     TAG_LOGD(AceLogTag::ACE_REPEAT, "OnRecycle() nodeId:%{public}d key:%{public}s", child->GetId(), key.c_str());
262     child->OnRecycle();
263 }
264 
CheckTTypeChanged(uint32_t index)265 bool RepeatVirtualScrollCaches::CheckTTypeChanged(uint32_t index)
266 {
267     std::string oldTType;
268     if (auto iter = ttype4index_.find(index); iter != ttype4index_.end()) {
269         oldTType = iter->second;
270     }
271 
272     FetchMoreKeysTTypes(index, index, false);
273 
274     std::string newTType;
275     if (auto iter = ttype4index_.find(index); iter != ttype4index_.end()) {
276         newTType = iter->second;
277     }
278 
279     return oldTType != newTType;
280 }
281 
282 /** scenario:
283  *         Repeat gets updated due to data change.
284  *         1. TS calls RepeatVirtualScrollNode,
285  *            then calls this function.
286  * 2. RepeatVirtualScrollNode requests layout to rebuild the UI
287  * 3. layout sends RepeatVirtualScrollNode::GetFrameChild calls
288  * 4. how to service GetFrameChild  call:
289  *   - first check for L1 keys (same template type) if any can be updated.
290  *     These UINodes remain in the render tree.
291  *   - if no L1 item, the look for L2 keys (same template type)
292  */
InvalidateKeyAndTTypeCaches()293 void RepeatVirtualScrollCaches::InvalidateKeyAndTTypeCaches()
294 {
295     TAG_LOGD(AceLogTag::ACE_REPEAT,
296         "invalidating index-> key and index->ttype mapping, layout needs to request all UINodes again  .. ");
297     key4index_.clear();
298     index4Key_.clear();
299     ttype4index_.clear();
300     index4ttype_.clear();
301     // mark all cached UINodes need to update.
302     // TS onKey4Index will fetch key-> RepeatItem and uupdate RepeatItem.index if changed
303     // Call UpdateDirty2 to make partial updates right away
304     // Therefore, on return GetKeys4Range can set node4key -> CacheItem back to isValid.true
305     // for all retained keys.
306     for (auto& [key, item] : node4key_) {
307         item.isValid = false;
308     }
309 
310     // we do not request new index <-> because we are still
311     // inside observed Repeat rerender.
312     // instead for FetchMoreKeysTTypes will fetch the entire range
313 }
314 
315 /**
316  * scenario: scroll, try to update an existing UINode
317  *
318  * find an key / UINode in L2 and update the UINode to
319  *   render the data source item 'forIndex'.
320  */
UpdateFromL2(uint32_t forIndex)321 RefPtr<UINode> RepeatVirtualScrollCaches::UpdateFromL2(uint32_t forIndex)
322 {
323     TAG_LOGD(AceLogTag::ACE_REPEAT, "forIndex:%{public}d",  static_cast<int32_t>(forIndex));
324 
325     const auto iterTType = ttype4index_.find(forIndex);
326     if (iterTType == ttype4index_.end()) {
327         TAG_LOGD(AceLogTag::ACE_REPEAT, "no ttype for index %{public}d",  static_cast<int32_t>(forIndex));
328         return nullptr;
329     }
330     const auto ttype = iterTType->second;
331     const auto iterNewKey = key4index_.find(forIndex);
332     if (iterNewKey == key4index_.end()) {
333         TAG_LOGD(AceLogTag::ACE_REPEAT, "no key for index %{public}d",  static_cast<int32_t>(forIndex));
334         return nullptr;
335     }
336     const std::string forKey = iterNewKey->second;
337 
338     const auto& oldKey = GetL2KeyToUpdate(ttype);
339     if (!oldKey) {
340         // no key for this ttype available to update
341         TAG_LOGD(AceLogTag::ACE_REPEAT,
342             "for index %{public}d, ttype %{public}s, no UINode found to update",
343             static_cast<int32_t>(forIndex), ttype.c_str());
344         return nullptr;
345     }
346 
347     TAG_LOGD(AceLogTag::ACE_REPEAT,
348         "for index %{public}d, from ld key %{public}s requesting TS to update child UINodes ....",
349         static_cast<int32_t>(forIndex), oldKey.value().c_str());
350 
351     // call TS to do the RepeatItem update
352     onUpdateNode_(oldKey.value(), forIndex);
353 
354     TAG_LOGD(AceLogTag::ACE_REPEAT,
355         "for index %{public}d, from old key %{public}s requesting TS to update child UINodes - done ",
356         static_cast<int32_t>(forIndex), oldKey.value().c_str());
357 
358     return UINodeHasBeenUpdated(ttype, oldKey.value(), forKey);
359 }
360 
UpdateSameKeyItem(const std::string & key,uint32_t index)361 void RepeatVirtualScrollCaches::UpdateSameKeyItem(const std::string& key, uint32_t index)
362 {
363     // call TS to do the RepeatItem update
364     onUpdateNode_(key, index);
365 }
366 
CreateNewNode(uint32_t forIndex)367 RefPtr<UINode> RepeatVirtualScrollCaches::CreateNewNode(uint32_t forIndex)
368 {
369     TAG_LOGD(AceLogTag::ACE_REPEAT, "forIndex: %{public}d",  static_cast<int32_t>(forIndex));
370 
371     // get key
372     const auto iter = key4index_.find(forIndex);
373     if (iter == key4index_.end()) {
374         TAG_LOGE(AceLogTag::ACE_REPEAT, "fail to create node of %{public}d",  static_cast<int32_t>(forIndex));
375         return nullptr;
376     }
377     const auto& forKey = iter->second;
378 
379     ACE_SCOPED_TRACE("RepeatVirtualScrollCaches::CreateNewNode index[%d] -> key[%s]",
380         static_cast<int32_t>(forIndex), forKey.c_str());
381 
382     // see if node already created, just for safety
383     const auto nodeIter = node4key_.find(forKey);
384     if (nodeIter != node4key_.end()) {
385         // have a node for this key already, just return
386         return nodeIter->second.item;
387     }
388 
389     // need to create a new node for key
390 
391     // get ttype
392     const auto ttypeIter = ttype4index_.find(forIndex);
393     if (ttypeIter == ttype4index_.end()) {
394         TAG_LOGE(AceLogTag::ACE_REPEAT, "fail to create %{public}d node due to type is missing", forIndex);
395         return nullptr;
396     }
397     const auto& ttype = ttypeIter->second;
398 
399     // swap the ViewStackProcessor instance for secondary while we run the item builder function
400     // so that its results can easily be obtained from it, does not disturb main ViewStackProcessor
401     NG::ScopedViewStackProcessor scopedViewStackProcessor;
402     auto* viewStack = NG::ViewStackProcessor::GetInstance();
403 
404     // call TS side
405     onCreateNode_(forIndex);
406 
407     const auto& node4Index = viewStack->Finish();
408 
409     if (!node4Index) {
410         TAG_LOGE(AceLogTag::ACE_REPEAT,
411             "New Node create: For index %{public}d -> key %{public}s -> ttype %{public}s "
412             "item builder FAILED to gen FrameNode. ERROR",
413             forIndex, forKey.c_str(), ttype.c_str());
414         return nullptr;
415     }
416 
417     // add node to node4key4ttype_
418     const auto node4KeyIter = node4key4ttype_.find(ttype);
419     if (node4KeyIter != node4key4ttype_.end()) {
420         node4KeyIter->second[forKey] = node4Index;
421     } else {
422         std::unordered_map<std::string, RefPtr<UINode>> node4Key;
423         node4Key[forKey] = node4Index;
424         node4key4ttype_[ttype] = std::move(node4Key);
425     }
426 
427     // add node to node4key_
428     node4key_[forKey] = CacheItem { true, node4Index };
429     TAG_LOGD(AceLogTag::ACE_REPEAT,
430         "New Node create: For index %{public}d -> key %{public}s -> ttype %{public}s created new Node %{public}s . ",
431         forIndex, forKey.c_str(), ttype.c_str(), DumpUINode(node4Index).c_str());
432     return node4Index;
433 }
434 
ForEachL1IndexUINode(const std::function<void (uint32_t index,const RefPtr<UINode> & node)> & cbFunc)435 void RepeatVirtualScrollCaches::ForEachL1IndexUINode(
436     const std::function<void(uint32_t index, const RefPtr<UINode>& node)>& cbFunc)
437 {
438     for (const auto& key : activeNodeKeysInL1_) {
439         const auto& cacheItem = node4key_[key];
440         const auto& indexIter = index4Key_.find(key);
441         if (indexIter == index4Key_.end()) {
442             TAG_LOGE(AceLogTag::ACE_REPEAT, "fail to get index for %{public}s key", key.c_str());
443             continue;
444         }
445         cbFunc(indexIter->second, cacheItem.item);
446     }
447 }
448 
RecycleItemsByIndex(int32_t index)449 void RepeatVirtualScrollCaches::RecycleItemsByIndex(int32_t index)
450 {
451     auto keyIter = key4index_.find(index);
452     if (keyIter != key4index_.end()) {
453         // STATE_MGMT_NOTE
454         // can not just remove from L1, also need to detach from tree!
455         // how to fix cause a call to RepeatVirtualScrollNode::DropFromL1 in
456         TAG_LOGD(
457             AceLogTag::ACE_REPEAT, "remove index %{public}d -> key %{public}s from L1", index, keyIter->second.c_str());
458 
459         ACE_SCOPED_TRACE(
460             "RepeatVirtualScrollCaches::RecycleItemsByIndex index[%d] -> key [%s]", index, keyIter->second.c_str());
461 
462         // don't fire OnRecycle here, as we manage reuse/recycle indepedently
463         RemoveKeyFromL1(keyIter->second, false);
464     }
465 }
466 
467 /**
468  * iterate over all entries of L1 and call function for each entry
469  * if function returns true, entry is added to rebuild L1
470  * cbFunc return true, key
471  * cbFunc returns false drop from L1
472  */
RebuildL1(const std::function<bool (int32_t index,const RefPtr<UINode> & node)> & cbFunc)473 bool RepeatVirtualScrollCaches::RebuildL1(const std::function<bool(int32_t index, const RefPtr<UINode>& node)>& cbFunc)
474 {
475     std::unordered_set<std::string> l1Copy;
476     std::swap(l1Copy, activeNodeKeysInL1_);
477     bool modified = false;
478     for (const auto& key : l1Copy) {
479         const auto& indexIter = index4Key_.find(key);
480         if (indexIter == index4Key_.end()) {
481             continue;
482         }
483         const auto& cacheItem = node4key_[key];
484         int32_t index = static_cast<int32_t>(indexIter->second);
485         if (cbFunc(index, cacheItem.item)) {
486             AddKeyToL1(key, false);
487         } else {
488             RemoveKeyFromL1(key);
489             modified = true;
490         }
491     }
492     return modified;
493 }
494 
RebuildL1WithKey(const std::function<bool (const std::string & key)> & cbFunc)495 bool RepeatVirtualScrollCaches::RebuildL1WithKey(const std::function<bool(const std::string& key)>& cbFunc)
496 {
497     std::unordered_set<std::string> l1Copy;
498     std::swap(l1Copy, activeNodeKeysInL1_);
499     bool modified = false;
500     for (const auto& key : l1Copy) {
501         if (cbFunc(key)) {
502             AddKeyToL1(key, false);
503         } else {
504             RemoveKeyFromL1(key);
505             modified = true;
506         }
507     }
508     return modified;
509 }
510 
DropFromL1(const std::string & key)511 RefPtr<UINode> RepeatVirtualScrollCaches::DropFromL1(const std::string& key)
512 {
513     const auto& cacheItem4Key = GetCachedNode4Key(key);
514     if (!cacheItem4Key.has_value()) {
515         return nullptr;
516     }
517     auto uiNode = cacheItem4Key.value().item;
518     activeNodeKeysInL1_.erase(key);
519     return uiNode;
520 }
521 
SetLastActiveRange(uint32_t from,uint32_t to)522 void RepeatVirtualScrollCaches::SetLastActiveRange(uint32_t from, uint32_t to)
523 {
524     // STATE_MGMT_NOTE, only update when from or to != stActiveRanges_[0] ?
525     lastActiveRanges_[1] = lastActiveRanges_[0];
526     lastActiveRanges_[0] = { from, to };
527 
528     const auto updatedPermissableCacheCount = to - from + 1;
529     for (auto iter = cacheCountL24ttype_.begin(); iter != cacheCountL24ttype_.end(); iter++) {
530         std::pair<bool, uint32_t>& optCacheCount = iter->second;
531         if (optCacheCount.first == false) {
532             // Repeat.template({ cachedCount }) options not specified
533             if (optCacheCount.second < updatedPermissableCacheCount) {
534                 TAG_LOGD(AceLogTag::ACE_REPEAT,
535                     "Growing permissable size of spare nodes cache for ttype '%{public}s' to %{public}d .",
536                     iter->first.c_str(), updatedPermissableCacheCount);
537                 optCacheCount.second = updatedPermissableCacheCount;
538             }
539         }
540     }
541 }
542 
543 /**
544  * Get the Index of frameNode in L1 / active range
545  * return -1 if not find the frameNode
546  */
GetFrameNodeIndex(const RefPtr<FrameNode> & frameNode) const547 int32_t RepeatVirtualScrollCaches::GetFrameNodeIndex(const RefPtr<FrameNode>& frameNode) const
548 {
549     for (const auto& key : activeNodeKeysInL1_) {
550         const auto nodeIter = node4key_.find(key);
551         if (nodeIter == node4key_.end() || !nodeIter->second.item) {
552             continue;
553         }
554         const auto& node = nodeIter->second.item->GetFrameChildByIndex(0, true);
555         if (node != frameNode) {
556             continue;
557         }
558         const auto& indexIter = index4Key_.find(key);
559         if (indexIter == index4Key_.end()) {
560             return -1;
561         }
562         return indexIter->second;
563     }
564     return -1;
565 }
566 
567 /**
568  * intended scenario: scroll
569  * servicing GetFrameChild, search for key that can be updated.
570  *
571  * return a key whose UINode can be updated
572  * the key must not be in L1, i.e. activeNodeKeysInL1_
573  * the given ttype must match the template type the UINode for this key
574  * has been rendered for (this info is available from node4key4ttype_)
575  */
GetL2KeyToUpdate(const std::optional<std::string> & ttype) const576 std::optional<std::string> RepeatVirtualScrollCaches::GetL2KeyToUpdate(
577     const std::optional<std::string>& ttype) const
578 {
579     if (!ttype.has_value()) {
580         return std::nullopt;
581     }
582 
583     const auto itNodes = node4key4ttype_.find(ttype.value());
584     if (itNodes == node4key4ttype_.end()) {
585         return std::nullopt;
586     }
587     const auto& keys2UINode = itNodes->second;
588     std::set<std::string, KeySorterClass> l2Keys = GetSortedL2KeysForTType(keys2UINode);
589     auto keyIter = l2Keys.rbegin();
590     if (keyIter == l2Keys.rend()) {
591         TAG_LOGD(AceLogTag::ACE_REPEAT,
592             "for ttype %{public}s no key in L2 that could be updated. ",
593             ttype.value().c_str());
594         return std::nullopt;
595     }
596     TAG_LOGD(AceLogTag::ACE_REPEAT,
597         "for ttype %{public}s found key '%{public}s' from L2 to update. ",
598         ttype.value().c_str(), keyIter->c_str());
599     return *keyIter;
600 }
601 
602 /**
603  * scenario: UI rebuild following key invalidation by TS side
604  * L1 includes keys that are no longer used, the linked UINodes
605  * should be updated.
606  *
607  * This function checks all L1 keys (of active UINodes) if the key
608  * can still be found from
609  * (previously updated following invalidation) key -> index map and
610  *
611  */
GetL1KeyToUpdate(const std::string & ttype) const612 std::optional<std::string> RepeatVirtualScrollCaches::GetL1KeyToUpdate(const std::string& ttype) const
613 {
614     for (const auto& keyIter : activeNodeKeysInL1_) {
615         const std::string& key = keyIter;
616         if (index4Key_.find(key) == index4Key_.end()) {
617             // key is no longer used
618             // check if key rendered the expected ttype
619             const auto ttypeIter = node4key4ttype_.find(ttype);
620             if (ttypeIter != node4key4ttype_.end()) {
621                 const std::unordered_map<std::string, RefPtr<UINode>>& node4Key = ttypeIter->second;
622                 if (node4Key.find(key) != node4Key.end()) {
623                     TAG_LOGD(AceLogTag::ACE_REPEAT, "for ttype %{public}s found key to update %{public}s in L1. ",
624                         ttype.c_str(), key.c_str());
625                     return key;
626                 }
627             }
628         }
629     }
630     TAG_LOGD(AceLogTag::ACE_REPEAT, "for ttype %{public}s no key in L1 that could be updated. ", ttype.c_str());
631     return std::nullopt;
632 }
633 
634 /**
635  * scenario: UINode of fromKey has been updated to render data for 'forKey'
636  *     the template type (ttype) remains unchanged
637  *     update node4key4ttype_ and node4key_ entries to use new key point to same UINode
638  */
UINodeHasBeenUpdated(const std::string & ttype,const std::string & fromKey,const std::string & forKey)639 RefPtr<UINode> RepeatVirtualScrollCaches::UINodeHasBeenUpdated(
640     const std::string& ttype, const std::string& fromKey, const std::string& forKey)
641 {
642     // 1. update fromKey -> forKey in node4key4ttype_
643     for (auto& node4KeyIter : node4key4ttype_) {
644         node4KeyIter.second.erase(forKey);
645     }
646     const auto nodesIter = node4key4ttype_.find(ttype);
647     if (nodesIter != node4key4ttype_.end()) {
648         auto& node4key = nodesIter->second;
649         auto iter = node4key.find(fromKey);
650         if (iter != node4key.end()) {
651             auto node = iter->second;
652             node4key.erase(iter);
653             node4key.emplace(forKey, node);
654         }
655     }
656 
657     // 2. update the key: fromKey to forKey in node4key_
658     auto iter = node4key_.find(fromKey);
659     if (iter != node4key_.end()) {
660         auto cachedItem = iter->second;
661         cachedItem.isValid = true;
662         node4key_.erase(iter);
663         node4key_.emplace(forKey, cachedItem);
664         return cachedItem.item;
665     }
666     TAG_LOGE(AceLogTag::ACE_REPEAT, "fail to update L2 : %{public}s, %{public}s, %{public}s, ", ttype.c_str(),
667         fromKey.c_str(), forKey.c_str());
668     return nullptr;
669 }
670 
671 /** scenario: keys cache has been updated
672  *
673  * find which keys in key -> UINode map are no longer used
674  * returned set entries are pairs:
675  *   pair.first: is this key a L1 item,
676  *   pair.second: key
677  */
FindUnusedKeys(std::set<std::pair<bool,std::string>> & result) const678 void RepeatVirtualScrollCaches::FindUnusedKeys(std::set<std::pair<bool, std::string>>& result) const
679 {
680     for (const auto& iter : node4key_) {
681         const std::string key = iter.first;
682         const auto indexIter = index4Key_.find(key);
683         if (indexIter == index4Key_.end()) {
684             // key is no longer used
685             // is it in L1 ?
686             const bool keyInL1 = (index4Key_.find(key) != index4Key_.end());
687             result.emplace(keyInL1, key);
688         }
689     }
690 }
691 
692 /**
693  * scenario: in idle process , following GetChildren()
694  * execute purge()
695  *
696  * enforce L2 cacheCount for each ttype
697  * logical L2 cache is map key->UINode map filtered out L1 keys
698  * purge by by deleting UINodes, delete their entry from
699  *   node4key4ttype_ and node4key_
700  *
701  */
Purge()702 bool RepeatVirtualScrollCaches::Purge()
703 {
704     uint32_t deletedCount = 0;
705     for (auto& itTType : node4key4ttype_) {
706         const auto& ttype = itTType.first;
707         auto& uiNode4Key = itTType.second;
708 
709         // size of the unused node pool L2
710         // defined either in template { caacheCount }
711         // or set dynamically by framework to maximum number of items in L1
712         uint32_t cacheCount = (cacheCountL24ttype_.find(ttype) == cacheCountL24ttype_.end())
713                                   ? 0 // unknown ttype should never happen
714                                   : cacheCountL24ttype_[ttype].second;
715         TAG_LOGD(AceLogTag::ACE_REPEAT, "Cache::Purge cacheCount %{public}d",  static_cast<int32_t>(cacheCount));
716         std::set<std::string, KeySorterClass> l2Keys = GetSortedL2KeysForTType(uiNode4Key);
717 
718         // l2_keys is sorted by increasing distance from lastActiveRange
719         // will drop those keys and their UINodes with largest distance
720         // improvement idea: in addition to distance from range use the
721         // scroll direction for selecting these keys
722         auto safeDist = std::min(cacheCount, static_cast<uint32_t>(l2Keys.size()));
723         auto itL2Key = std::next(l2Keys.begin(), safeDist);
724 
725         while (itL2Key != l2Keys.end()) {
726             // delete remaining keys
727             TAG_LOGD(AceLogTag::ACE_REPEAT,
728                 "   ... purging spare node cache item old key '%{public}s' -> node %{public}s, ttype: '%{public}s', "
729                 "permissable spare nodes count %{public}d",
730                 itL2Key->c_str(), DumpUINodeWithKey(*itL2Key).c_str(), ttype.c_str(),
731                 static_cast<int32_t>(cacheCount));
732             uiNode4Key.erase(*itL2Key);
733             node4key_.erase(*itL2Key);
734             // check out transition case.
735             itL2Key++;
736             deletedCount += 1;
737         }
738     }
739     if (deletedCount > 0) {
740         TAG_LOGD(AceLogTag::ACE_REPEAT, "Purged total %d items.",  static_cast<int32_t>(deletedCount));
741         ACE_SCOPED_TRACE("RepeatVirtualScrollCaches::Purge %d items",  static_cast<int32_t>(deletedCount));
742     }
743     return (deletedCount > 0);
744 }
745 
746 /**
747  * given key return the index position (reverse lookup)
748  * invalidated keys (after Repeat rerender/ data change)
749  * are keys for which no index exists anymore,
750  * method returns uint max value for these.
751  * int max value causes that distance from active range is max
752  * these keys will be selected for update first.
753  */
GetIndex4Key(const std::string & key) const754 uint32_t RepeatVirtualScrollCaches::GetIndex4Key(const std::string& key) const
755 {
756     auto it = index4Key_.find(key);
757     if (it != index4Key_.end()) {
758         return it->second;
759     }
760     // key is no longer used
761     // return max uint32_t value
762     return UINT32_MAX;
763 }
764 
GetTType4Index(uint32_t index)765 std::optional<std::string> RepeatVirtualScrollCaches::GetTType4Index(uint32_t index)
766 {
767     const auto it = ttype4index_.find(index);
768     if (it == ttype4index_.end()) {
769         return std::nullopt;
770     }
771     return it->second;
772 }
773 
GetCachedNode4Key(const std::optional<std::string> & key)774 std::optional<CacheItem> RepeatVirtualScrollCaches::GetCachedNode4Key(const std::optional<std::string>& key)
775 {
776     if (!key.has_value()) {
777         return std::nullopt;
778     }
779     const auto it = node4key_.find(key.value());
780     if (it == node4key_.end()) {
781         return std::nullopt;
782     }
783     return it->second;
784 }
785 
GetCachedNode4Key4Ttype(const std::optional<std::string> & key,const std::optional<std::string> & ttype)786 RefPtr<UINode> RepeatVirtualScrollCaches::GetCachedNode4Key4Ttype(
787     const std::optional<std::string>& key, const std::optional<std::string>& ttype)
788 {
789     // if key and ttype given, search for UINode of givenkey and ttype
790     //  in caches, i.e. in node4key4ttype
791     if (!key.has_value() || !ttype.has_value()) {
792         return nullptr;
793     }
794     const auto it0 = node4key4ttype_.find(ttype.value());
795     if (it0 == node4key4ttype_.end()) {
796         return nullptr;
797     }
798     const auto it1 = it0->second.find(key.value());
799     if (it1 == it0->second.end()) {
800         return nullptr;
801     }
802     return it1->second;
803 }
804 
805 /**
806  *  for given index return distance from active range,
807  *  or 0 if within active range
808  *  distance is uint max for invalidated keys
809  *
810  * instead of just using previous active range
811  * use the ranges informed by previous two SetActiveRaneg calls.
812  * Obtain the scroll direction and use it to calc the distance.
813  * Items left 'behind' when scrolling get larger distance and are more
814  * likely updated or purged from L2 cache.
815  */
GetDistanceFromRange(uint32_t index) const816 uint32_t RepeatVirtualScrollCaches::GetDistanceFromRange(uint32_t index) const
817 {
818     // distance is uint max for invalidated keys
819     if (index == UINT32_MAX) {
820         return UINT32_MAX;
821     }
822     uint32_t last[2] = { lastActiveRanges_[0].first, lastActiveRanges_[0].second };
823     uint32_t prev[2] = { lastActiveRanges_[1].first, lastActiveRanges_[1].second };
824 
825     // this is experimental optimization, based on scrolling detection
826     // here we assume this is a scrolling, if previous range and last range has
827     // not empty intersection
828 
829     // if scrolling up, return 0 for any lower index
830     if (last[0] < prev[0] && prev[0] < last[1]) {
831         if (index < last[0]) {
832             return 0;
833         }
834     }
835 
836     // if scrolling down, return 0 for any greater index
837     if (last[0] < prev[1] && prev[1] < last[1]) {
838         if (index > last[1]) {
839             return 0;
840         }
841     }
842 
843     // this is not scrolling
844     if (index < last[0]) {
845         return last[0] - index;
846     }
847 
848     if (index > last[1]) {
849         return index - last[1];
850     }
851 
852     return 0;
853 }
854 
855 /**
856  * scenario: find L1 key that should be updated
857  * choose the key whose index is the furthest away from active range
858  * given two keys compare their distFromRange
859  */
CompareKeyByIndexDistance(const std::string & key1,const std::string & key2) const860 bool RepeatVirtualScrollCaches::CompareKeyByIndexDistance(const std::string& key1, const std::string& key2) const
861 {
862     return GetDistanceFromRange(GetIndex4Key(key1)) < GetDistanceFromRange(GetIndex4Key(key2));
863 }
864 
865 /**
866  * scenario: find L1 key(s) that should be updated
867  *
868  * return a sorted set of L2 keys, sorted by increasing distance from active range
869  */
GetSortedL2KeysForTType(const std::unordered_map<std::string,RefPtr<UINode>> & uiNode4Key) const870 std::set<std::string, KeySorterClass> RepeatVirtualScrollCaches::GetSortedL2KeysForTType(
871     const std::unordered_map<std::string, RefPtr<UINode>>& uiNode4Key) const
872 {
873     KeySorterClass sorter(this);
874     std::set<std::string, KeySorterClass> l2Keys(sorter);
875     for (const auto& itUINode : uiNode4Key) {
876         const auto& key = itUINode.first;
877         if (activeNodeKeysInL1_.find(key) == activeNodeKeysInL1_.end()) {
878             // key is not in L1
879             // add to l2Keys
880             l2Keys.emplace(key);
881         }
882     }
883     return l2Keys;
884 }
885 
DumpL1() const886 std::string RepeatVirtualScrollCaches::DumpL1() const
887 {
888     std::string result =
889         "L1 (visible + pre-rendered items, their count defined by List/Grid.cacheCount: total number=" +
890         std::to_string(activeNodeKeysInL1_.size()) + "--------------\n";
891     for (const auto& it : activeNodeKeysInL1_) {
892         const std::string& key = it;
893         auto indexIter = index4Key_.find(key);
894         if (indexIter == index4Key_.end()) {
895             continue;
896         }
897         result += "  index " + std::to_string(indexIter->second) + " -> key: '" + key +
898                   "', node: " + DumpUINodeWithKey(key) + "\n";
899     }
900     return result;
901 }
902 
DumpL2() const903 std::string RepeatVirtualScrollCaches::DumpL2() const
904 {
905     std::unordered_map<std::string, RefPtr<UINode>> allCaches;
906     for (const auto& [item, cacheItem] : node4key_) {
907         allCaches.try_emplace(item, cacheItem.item);
908     }
909     std::set<std::string, KeySorterClass> l2KeyResult = GetSortedL2KeysForTType(allCaches);
910 
911     std::string result = "RecycleItem: Spare items available for update, not on render tree: size=" +
912                          std::to_string(l2KeyResult.size()) + "--------------\n";
913     for (const auto& it : l2KeyResult) {
914         result += "   old key '" + it + "', node: " + DumpUINodeWithKey(it) + "\n";
915     }
916     return result;
917 }
918 
DumpKey4Index() const919 std::string RepeatVirtualScrollCaches::DumpKey4Index() const
920 {
921     std::string result = "key4index_: size=" + std::to_string(key4index_.size()) + "--------------\n";
922     for (const auto& it : key4index_) {
923         result += "   " + std::to_string(it.first) + " -> \"" + it.second +
924                   "\", node: " + DumpUINodeWithKey(it.second) + "\n";
925     }
926     result += "index4Key_: size=" + std::to_string(index4Key_.size()) + "--------------\n";
927     for (const auto& it : index4Key_) {
928         result += "   \"" + it.first + "\" -> " + std::to_string(it.second) + "\n";
929     }
930     return result;
931 }
932 
DumpTType4Index() const933 std::string RepeatVirtualScrollCaches::DumpTType4Index() const
934 {
935     std::string result = "ttype4index_: size=" + std::to_string(ttype4index_.size()) + "--------------\n";
936     for (const auto& it : ttype4index_) {
937         result += "   " + std::to_string(it.first) + " -> \"" + it.second + "\n";
938     }
939     result += "index4ttype_: size=" + std::to_string(index4ttype_.size()) + "--------------\n";
940     for (const auto& it : index4ttype_) {
941         result += "   \"" + it.first + "\" -> " + std::to_string(it.second) + "\n";
942     }
943     return result;
944 }
945 
DumpUINode4Key() const946 std::string RepeatVirtualScrollCaches::DumpUINode4Key() const
947 {
948     std::string result = "node4key_: size=" + std::to_string(node4key_.size()) + "--------------\n";
949     for (const auto& it : node4key_) {
950         result += "   \"" + it.first + "\" -> node: " + it.second.item->GetTag() + "(" +
951                   std::to_string(it.second.item->GetId()) + ") \n";
952     }
953     return result;
954 }
955 
DumpUINode4Key4TType() const956 std::string RepeatVirtualScrollCaches::DumpUINode4Key4TType() const
957 {
958     std::string result = "node4key4ttype_: size=" + std::to_string(node4key4ttype_.size()) + "--------------\n";
959     for (const auto& ttypeIter : node4key4ttype_) {
960         const auto& ttype = ttypeIter.first;
961         const auto& node4key = ttypeIter.second;
962         result += "ttype " + ttype + ": node4key: size=" + std::to_string(node4key.size()) + "--------------\n";
963         for (const auto& it : node4key) {
964             result += "   \"" + it.first + "\" -> node: " + it.second->GetTag() + "(" +
965                       std::to_string(it.second->GetId()) + ") \n";
966         }
967     }
968     return result;
969 }
970 
DumpUINodeWithKey(const std::string & key) const971 std::string RepeatVirtualScrollCaches::DumpUINodeWithKey(const std::string& key) const
972 {
973     const auto it = node4key_.find(key);
974     return (it == node4key_.end()) ? "no UINode on file"
975                                    : it->second.item->GetTag() + "(" + std::to_string(it->second.item->GetId()) + ")";
976 }
977 
DumpUINode(const RefPtr<UINode> & node) const978 std::string RepeatVirtualScrollCaches::DumpUINode(const RefPtr<UINode>& node) const
979 {
980     return (node == nullptr) ? "UINode nullptr" : node->GetTag() + "(" + std::to_string(node->GetId()) + ")";
981 }
982 } // namespace OHOS::Ace::NG
983