FreeCAD

1
#include "PreCompiled.h"
2
#ifndef _PreComp_
3
#include <unordered_map>
4
#ifndef FC_DEBUG
5
#include <random>
6
#endif
7
#endif
8

9
#include "ElementMap.h"
10
#include "ElementNamingUtils.h"
11

12
#include "App/Application.h"
13
#include "Base/Console.h"
14
#include "Document.h"
15
#include "DocumentObject.h"
16

17
#include <boost/algorithm/string/classification.hpp>
18
#include <boost/algorithm/string/split.hpp>
19

20

21
FC_LOG_LEVEL_INIT("ElementMap", true, 2);// NOLINT
22

23
namespace Data
24
{
25

26

27
// Because the existence of hierarchical element maps, for the same document
28
// we may store an element map more than once in multiple objects. And because
29
// we may want to support partial loading, we choose to tolerate such redundancy
30
// for now.
31
//
32
// In order to not waste memory space when the file is loaded, we use the
33
// following two maps to assign a one-time id for each unique element map.  The
34
// id will be saved together with the element map.
35
//
36
// When restoring, we'll read back the id and lookup for an existing element map
37
// with the same id, and skip loading the current map if one is found.
38
//
39
// TODO: Note that the same redundancy can be found when saving OCC shapes,
40
// because we currently save shapes for each object separately. After restoring,
41
// any shape sharing is lost. But again, we do want to keep separate shape files
42
// because of partial loading. The same technique used here can be applied to
43
// restore shape sharing.
44
static std::unordered_map<const ElementMap*, unsigned> _elementMapToId;
45
static std::unordered_map<unsigned, ElementMapPtr> _idToElementMap;
46

47

48
void ElementMap::init()
49
{
50
    static bool inited;
51
    if (!inited) {
52
        inited = true;
53
        ::App::GetApplication().signalStartSaveDocument.connect(
54
            [](const ::App::Document&, const std::string&) {
55
                _elementMapToId.clear();
56
            });
57
        ::App::GetApplication().signalFinishSaveDocument.connect(
58
            [](const ::App::Document&, const std::string&) {
59
                _elementMapToId.clear();
60
            });
61
        ::App::GetApplication().signalStartRestoreDocument.connect([](const ::App::Document&) {
62
            _idToElementMap.clear();
63
        });
64
        ::App::GetApplication().signalFinishRestoreDocument.connect([](const ::App::Document&) {
65
            _idToElementMap.clear();
66
        });
67
    }
68
}
69

70
ElementMap::ElementMap()
71
{
72
    init();
73
}
74

75

76
void ElementMap::beforeSave(const ::App::StringHasherRef& hasherRef) const
77
{
78
    unsigned& id = _elementMapToId[this];
79
    if (id == 0U) {
80
        id = _elementMapToId.size();
81
    }
82
    this->_id = id;
83

84
    for (auto& indexedName : this->indexedNames) {
85
        for (const MappedNameRef& mappedName : indexedName.second.names) {
86
            for (const MappedNameRef* ref = &mappedName; ref; ref = ref->next.get()) {
87
                for (const ::App::StringIDRef& sid : ref->sids) {
88
                    if (sid.isFromSameHasher(hasherRef)) {
89
                        sid.mark();
90
                    }
91
                }
92
            }
93
        }
94
        for (auto& childPair : indexedName.second.children) {
95
            if (childPair.second.elementMap) {
96
                childPair.second.elementMap->beforeSave(hasherRef);
97
            }
98
            for (auto& sid : childPair.second.sids) {
99
                if (sid.isFromSameHasher(hasherRef)) {
100
                    sid.mark();
101
                }
102
            }
103
        }
104
    }
105
}
106

107
void ElementMap::save(std::ostream& stream, int index,
108
                      const std::map<const ElementMap*, int>& childMapSet,
109
                      const std::map<QByteArray, int>& postfixMap) const
110
{
111
    stream << "\nElementMap " << index << ' ' << this->_id << ' ' << this->indexedNames.size()
112
           << '\n';
113

114
    for (auto& indexedName : this->indexedNames) {
115
        stream << '\n' << indexedName.first << '\n';
116

117
        stream << "\nChildCount " << indexedName.second.children.size() << '\n';
118
        for (auto& vv : indexedName.second.children) {
119
            auto& child = vv.second;
120
            int mapIndex = 0;
121
            if (child.elementMap) {
122
                auto it = childMapSet.find(child.elementMap.get());
123
                if (it == childMapSet.end() || it->second == 0) {
124
                    FC_ERR("Invalid child element map");// NOLINT
125
                }
126
                else {
127
                    mapIndex = it->second;
128
                }
129
            }
130
            stream << child.indexedName.getIndex() << ' ' << child.offset << ' ' << child.count
131
                   << ' ' << child.tag << ' ' << mapIndex << ' ';
132
            stream.write(child.postfix.constData(), child.postfix.size());
133
            stream << ' ' << '0';
134
            for (auto& sid : child.sids) {
135
                if (sid.isMarked()) {
136
                    stream << '.' << sid.value();
137
                }
138
            }
139
            stream << '\n';
140
        }
141

142
        stream << "\nNameCount " << indexedName.second.names.size() << '\n';
143
        if (indexedName.second.names.empty()) {
144
            continue;
145
        }
146

147
        boost::io::ios_flags_saver ifs(stream);
148
        stream << std::hex;
149

150
        for (auto& dequeueOfMappedNameRef : indexedName.second.names) {
151
            for (auto ref = &dequeueOfMappedNameRef; ref; ref = ref->next.get()) {
152
                if (!ref->name) {
153
                    break;
154
                }
155

156
                ::App::StringID::IndexID prefixID {};
157
                prefixID.id = 0;
158
                IndexedName idx(ref->name.dataBytes());
159
                bool printName = true;
160
                if (idx) {
161
                    auto key = QByteArray::fromRawData(idx.getType(),
162
                                                       static_cast<int>(qstrlen(idx.getType())));
163
                    auto it = postfixMap.find(key);
164
                    if (it != postfixMap.end()) {
165
                        stream << ':' << it->second << '.' << idx.getIndex();
166
                        printName = false;
167
                    }
168
                }
169
                else {
170
                    prefixID = ::App::StringID::fromString(ref->name.dataBytes());
171
                    if (prefixID.id != 0) {
172
                        for (auto& sid : ref->sids) {
173
                            if (sid.isMarked() && sid.value() == prefixID.id) {
174
                                stream << '$';
175
                                stream.write(ref->name.dataBytes().constData(),
176
                                             ref->name.dataBytes().size());
177
                                printName = false;
178
                                break;
179
                            }
180
                        }
181
                        if (printName) {
182
                            prefixID.id = 0;
183
                        }
184
                    }
185
                }
186
                if (printName) {
187
                    stream << ';';
188
                    stream.write(ref->name.dataBytes().constData(), ref->name.dataBytes().size());
189
                }
190

191
                const QByteArray& postfix = ref->name.postfixBytes();
192
                if (postfix.isEmpty()) {
193
                    stream << ".0";
194
                }
195
                else {
196
                    auto it = postfixMap.find(postfix);
197
                    assert(it != postfixMap.end());
198
                    stream << '.' << it->second;
199
                }
200
                for (auto& sid : ref->sids) {
201
                    if (sid.isMarked() && sid.value() != prefixID.id) {
202
                        stream << '.' << sid.value();
203
                    }
204
                }
205

206
                stream << ' ';
207
            }
208
            stream << "0\n";
209
        }
210
    }
211
    stream << "\nEndMap\n";
212
}
213

214
void ElementMap::save(std::ostream& stream) const
215
{
216
    std::map<const ElementMap*, int> childMapSet;
217
    std::vector<const ElementMap*> childMaps;
218
    std::map<QByteArray, int> postfixMap;
219
    std::vector<QByteArray> postfixes;
220

221
    collectChildMaps(childMapSet, childMaps, postfixMap, postfixes);
222

223
    stream << this->_id << " PostfixCount " << postfixes.size() << '\n';
224
    for (auto& postfix : postfixes) {
225
        stream.write(postfix.constData(), postfix.size());
226
        stream << '\n';
227
    }
228
    int index = 0;
229
    stream << "\nMapCount " << childMaps.size() << '\n';
230
    for (auto& elementMap : childMaps) {
231
        elementMap->save(stream, ++index, childMapSet, postfixMap);
232
    }
233
}
234

235
ElementMapPtr ElementMap::restore(::App::StringHasherRef hasherRef, std::istream& stream)
236
{
237
    const char* msg = "Invalid element map";
238

239
    unsigned id = 0;
240
    int count = 0;
241
    std::string tmp;
242
    if (!(stream >> id >> tmp >> count) || tmp != "PostfixCount") {
243
        FC_THROWM(Base::RuntimeError, msg);// NOLINT
244
    }
245

246
    auto& map = _idToElementMap[id];
247
    if (map) {
248
        return map;
249
    }
250

251
    std::vector<std::string> postfixes;
252
    postfixes.reserve(count);
253
    for (int i = 0; i < count; ++i) {
254
        postfixes.emplace_back();
255
        stream >> postfixes.back();
256
    }
257

258
    std::vector<ElementMapPtr> childMaps;
259
    count = 0;
260
    if (!(stream >> tmp >> count) || tmp != "MapCount" || count == 0) {
261
        FC_THROWM(Base::RuntimeError, msg);// NOLINT
262
    }
263
    childMaps.reserve(count - 1);
264
    for (int i = 0; i < count - 1; ++i) {
265
        childMaps.push_back(
266
            std::make_shared<ElementMap>()->restore(hasherRef, stream, childMaps, postfixes));
267
    }
268

269
    return restore(hasherRef, stream, childMaps, postfixes);
270
}
271

272
ElementMapPtr ElementMap::restore(::App::StringHasherRef hasherRef, std::istream& stream,
273
                                  std::vector<ElementMapPtr>& childMaps,
274
                                  const std::vector<std::string>& postfixes)
275
{
276
    const char* msg = "Invalid element map";
277
    const int hexBase {16};
278
    const int decBase {10};
279
    std::string tmp;
280
    int index = 0;
281
    int typeCount = 0;
282
    unsigned id = 0;
283
    if (!(stream >> tmp >> index >> id >> typeCount) || tmp != "ElementMap") {
284
        FC_THROWM(Base::RuntimeError, msg);// NOLINT
285
    }
286

287
    auto& map = _idToElementMap[id];
288
    if (map) {
289
        while (tmp != "EndMap") {
290
            if (!std::getline(stream, tmp)) {
291
                FC_THROWM(Base::RuntimeError, "unexpected end of child element map");// NOLINT
292
            }
293
        }
294
        return map;
295
    }
296

297
    const char* hasherWarn = nullptr;
298
    const char* hasherIDWarn = nullptr;
299
    const char* postfixWarn = nullptr;
300
    const char* childSIDWarn = nullptr;
301
    std::vector<std::string> tokens;
302

303
    for (int i = 0; i < typeCount; ++i) {
304
        int outerCount = 0;
305
        if (!(stream >> tmp)) {
306
            FC_THROWM(Base::RuntimeError, "missing element type");// NOLINT
307
        }
308
        IndexedName idx(tmp.c_str(), 1);
309

310
        if (!(stream >> tmp >> outerCount) || tmp != "ChildCount") {
311
            FC_THROWM(Base::RuntimeError, "missing element child count");// NOLINT
312
        }
313

314
        auto& indices = this->indexedNames[idx.getType()];
315
        for (int j = 0; j < outerCount; ++j) {
316
            int cIndex = 0;
317
            int offset = 0;
318
            int count = 0;
319
            long tag = 0;
320
            int mapIndex = 0;
321
            if (!(stream >> cIndex >> offset >> count >> tag >> mapIndex >> tmp)) {
322
                FC_THROWM(Base::RuntimeError, "Invalid element child");// NOLINT
323
            }
324
            if (cIndex < 0) {
325
                FC_THROWM(Base::RuntimeError, "Invalid element child index");// NOLINT
326
            }
327
            if (offset < 0) {
328
                FC_THROWM(Base::RuntimeError, "Invalid element child offset");// NOLINT
329
            }
330
            if (mapIndex >= index || mapIndex < 0 || mapIndex > (int)childMaps.size()) {
331
                FC_THROWM(Base::RuntimeError, "Invalid element child map index");// NOLINT
332
            }
333
            auto& child = indices.children[cIndex + offset + count];
334
            child.indexedName = IndexedName::fromConst(idx.getType(), cIndex);
335
            child.offset = offset;
336
            child.count = count;
337
            child.tag = tag;
338
            if (mapIndex > 0) {
339
                child.elementMap = childMaps[mapIndex - 1];
340
            }
341
            else {
342
                child.elementMap = nullptr;
343
            }
344
            child.postfix = tmp.c_str();
345
            this->childElements[child.postfix].childMap = &child;
346
            this->childElementSize += child.count;
347

348
            if (!(stream >> tmp)) {
349
                FC_THROWM(Base::RuntimeError, "Invalid element child string id");// NOLINT
350
            }
351

352
            tokens.clear();
353
            boost::split(tokens, tmp, boost::is_any_of("."));
354
            if (tokens.size() > 1) {
355
                child.sids.reserve(static_cast<int>(tokens.size()) - 1);
356
                for (unsigned k = 1; k < tokens.size(); ++k) {
357
                    // The element child string ID is saved as decimal
358
                    // instead of hex by accident. To simplify maintenance
359
                    // of backward compatibility, it is not corrected, and
360
                    // just restored as decimal here.
361
                    long childID = strtol(tokens[k].c_str(), nullptr, decBase);
362
                    auto sid = hasherRef->getID(childID);
363
                    if (!sid) {
364
                        childSIDWarn = "Missing element child string id";
365
                    }
366
                    else {
367
                        child.sids.push_back(sid);
368
                    }
369
                }
370
            }
371
        }
372

373
        if (!(stream >> tmp >> outerCount) || tmp != "NameCount") {
374
            FC_THROWM(Base::RuntimeError, "missing element name outerCount");// NOLINT
375
        }
376

377
        boost::io::ios_flags_saver ifs(stream);
378
        stream >> std::hex;
379

380
        indices.names.resize(outerCount);
381
        for (int j = 0; j < outerCount; ++j) {
382
            idx.setIndex(j);
383
            auto* ref = &indices.names[j];
384
            int innerCount = 0;
385
            while (true) {
386
                if (!(stream >> tmp)) {
387
                    FC_THROWM(Base::RuntimeError, "Failed to read element name");// NOLINT
388
                }
389
                if (tmp == "0") {
390
                    break;
391
                }
392
                if (innerCount++ != 0) {
393
                    ref->next = std::make_unique<MappedNameRef>();
394
                    ref = ref->next.get();
395
                }
396
                tokens.clear();
397
                boost::split(tokens, tmp, boost::is_any_of("."));
398
                if (tokens.size() < 2) {
399
                    FC_THROWM(Base::RuntimeError, "Invalid element entry");// NOLINT
400
                }
401

402
                int offset = 1;
403
                ::App::StringID::IndexID prefixID {};
404
                prefixID.id = 0;
405

406
                switch (tokens[0][0]) {
407
                    case ':': {
408
                        if (tokens.size() < 3) {
409
                            FC_THROWM(Base::RuntimeError, "Invalid element entry");// NOLINT
410
                        }
411
                        ++offset;
412
                        long elementNameIndex = strtol(tokens[0].c_str() + 1, nullptr, hexBase);
413
                        if (elementNameIndex <= 0 || elementNameIndex > (int)postfixes.size()) {
414
                            FC_THROWM(Base::RuntimeError, "Invalid element name index");// NOLINT
415
                        }
416
                        long elementIndex = strtol(tokens[1].c_str(), nullptr, hexBase);
417
                        ref->name = MappedName(
418
                            IndexedName::fromConst(postfixes[elementNameIndex - 1].c_str(),
419
                                                   static_cast<int>(elementIndex)));
420
                        break;
421
                    }
422
                    case '$':
423
                        ref->name = MappedName(tokens[0].c_str() + 1);
424
                        prefixID = ::App::StringID::fromString(ref->name.dataBytes());
425
                        break;
426
                    case ';':
427
                        ref->name = MappedName(tokens[0].c_str() + 1);
428
                        break;
429
                    default:
430
                        FC_THROWM(Base::RuntimeError, "Invalid element name marker");// NOLINT
431
                }
432

433
                if (tokens[offset] != "0") {
434
                    long postfixIndex = strtol(tokens[offset].c_str(), nullptr, hexBase);
435
                    if (postfixIndex <= 0 || postfixIndex > (int)postfixes.size()) {
436
                        postfixWarn = "Invalid element postfix index";
437
                    }
438
                    else {
439
                        ref->name += postfixes[postfixIndex - 1];
440
                    }
441
                }
442

443
                this->mappedNames.emplace(ref->name, idx);
444

445
                if (!hasherRef) {
446
                    if (offset + 1 < (int)tokens.size()) {
447
                        hasherWarn = "No hasherRef";
448
                    }
449
                    continue;
450
                }
451

452
                ref->sids.reserve((tokens.size() - offset - 1 + prefixID.id) != 0U ? 1 : 0);
453
                if (prefixID.id != 0) {
454
                    auto sid = hasherRef->getID(prefixID.id);
455
                    if (!sid) {
456
                        hasherIDWarn = "Missing element name prefix id";
457
                    }
458
                    else {
459
                        ref->sids.push_back(sid);
460
                    }
461
                }
462
                for (int l = offset + 1; l < (int)tokens.size(); ++l) {
463
                    long readID = strtol(tokens[l].c_str(), nullptr, hexBase);
464
                    auto sid = hasherRef->getID(readID);
465
                    if (!sid) {
466
                        hasherIDWarn = "Invalid element name string id";
467
                    }
468
                    else {
469
                        ref->sids.push_back(sid);
470
                    }
471
                }
472
            }
473
        }
474
    }
475
    if (hasherWarn) {
476
        FC_WARN(hasherWarn);// NOLINT
477
    }
478
    if (hasherIDWarn) {
479
        FC_WARN(hasherIDWarn);// NOLINT
480
    }
481
    if (postfixWarn) {
482
        FC_WARN(postfixWarn);// NOLINT
483
    }
484
    if (childSIDWarn) {
485
        FC_WARN(childSIDWarn);// NOLINT
486
    }
487

488
    if (!(stream >> tmp) || tmp != "EndMap") {
489
        FC_THROWM(Base::RuntimeError, "unexpected end of child element map");// NOLINT
490
    }
491

492
    return shared_from_this();
493
}
494

495
MappedName ElementMap::addName(MappedName& name, const IndexedName& idx, const ElementIDRefs& sids,
496
                               bool overwrite, IndexedName* existing)
497
{
498
    if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
499
        if (name.find("#") >= 0 && name.findTagInElementName() < 0) {
500
            FC_ERR("missing tag postfix " << name);// NOLINT
501
        }
502
    }
503
    while (true) {
504
        if (overwrite) {
505
            erase(idx);
506
        }
507
        auto ret = mappedNames.insert(std::make_pair(name, idx));
508
        if (ret.second) {              // element just inserted did not exist yet in the map
509
            ret.first->first.compact();// FIXME see MappedName.cpp
510
            mappedRef(idx).append(ret.first->first, sids);
511
            FC_TRACE(idx << " -> " << name);// NOLINT
512
            return ret.first->first;
513
        }
514
        if (ret.first->second == idx) {
515
            FC_TRACE("duplicate " << idx << " -> " << name);// NOLINT
516
            return ret.first->first;
517
        }
518
        if (!overwrite) {
519
            if (existing) {
520
                *existing = ret.first->second;
521
            }
522
            return {};
523
        }
524

525
        erase(ret.first->first);
526
    };
527
}
528

529
void ElementMap::addPostfix(const QByteArray& postfix, std::map<QByteArray, int>& postfixMap,
530
                            std::vector<QByteArray>& postfixes)
531
{
532
    if (postfix.isEmpty()) {
533
        return;
534
    }
535
    auto res = postfixMap.insert(std::make_pair(postfix, 0));
536
    if (res.second) {
537
        postfixes.push_back(postfix);
538
        res.first->second = (int)postfixes.size();
539
    }
540
}
541

542
MappedName ElementMap::setElementName(const IndexedName& element, const MappedName& name,
543
                                      long masterTag, const ElementIDRefs* sid, bool overwrite)
544
{
545
    if (!element) {
546
        throw Base::ValueError("Invalid input");
547
    }
548
    if (!name) {
549
        erase(element);
550
        return {};
551
    }
552

553
    for (int i = 0, count = name.size(); i < count; ++i) {
554
        char check = name[i];
555
        if (check == '.' || (std::isspace((int)check) != 0)) {
556
            FC_THROWM(Base::RuntimeError, "Illegal character in mapped name: " << name);// NOLINT
557
        }
558
    }
559
    for (const char* readChar = element.getType(); *readChar != 0; ++readChar) {
560
        char check = *readChar;
561
        if (check == '.' || (std::isspace((int)check) != 0)) {
562
            FC_THROWM(Base::RuntimeError,// NOLINT
563
                      "Illegal character in element name: " << element);
564
        }
565
    }
566

567
    // Originally in ComplexGeoData::setElementName
568
    // LinkStable/src/App/ComplexGeoData.cpp#L1631
569
    // No longer possible after map separated in ElementMap.cpp
570

571
    // if(!_ElementMap)
572
    //     resetElementMap(std::make_shared<ElementMap>());
573

574
    ElementIDRefs _sid;
575
    if (!sid) {
576
        sid = &_sid;
577
    }
578

579
    std::ostringstream ss;
580
    Data::MappedName mappedName(name);
581
    for (int i = 0;;) {
582
        IndexedName existing;
583
        MappedName res = this->addName(mappedName, element, *sid, overwrite, &existing);
584
        if (res) {
585
            return res;
586
        }
587
        const int maxAttempts {100};
588
        if (++i == maxAttempts) {
589
            FC_ERR("unresolved duplicate element mapping '"// NOLINT
590
                   << name << ' ' << element << '/' << existing);
591
            return name;
592
        }
593
        if (sid != &_sid) {
594
            _sid = *sid;
595
        }
596
        mappedName = renameDuplicateElement(i, element, existing, name, _sid, masterTag);
597
        if (!mappedName) {
598
            return name;
599
        }
600
        sid = &_sid;
601
    }
602
}
603

604
// try to hash element name while preserving the source tag
605
void ElementMap::encodeElementName(char element_type, MappedName& name, std::ostringstream& ss,
606
                                   ElementIDRefs* sids, long masterTag, const char* postfix,
607
                                   long tag, bool forceTag) const
608
{
609
    if (postfix && (postfix[0] != 0)) {
610
        if (!boost::starts_with(postfix, ELEMENT_MAP_PREFIX)) {
611
            ss << ELEMENT_MAP_PREFIX;
612
        }
613
        ss << postfix;
614
    }
615
    long inputTag = 0;
616
    if (!forceTag && (ss.tellp() == 0)) {
617
        if ((tag == 0) || tag == masterTag) {
618
            return;
619
        }
620
        name.findTagInElementName(&inputTag, nullptr, nullptr, nullptr, true);
621
        if (inputTag == tag) {
622
            return;
623
        }
624
    }
625
    else if ((tag == 0) || (!forceTag && tag == masterTag)) {
626
        int pos = name.findTagInElementName(&inputTag, nullptr, nullptr, nullptr, true);
627
        if (inputTag != 0) {
628
            tag = inputTag;
629
            // About to encode the same tag used last time. This usually means
630
            // the owner object is doing multistep modeling. Let's not
631
            // recursively encode the same tag too many times. It will be a
632
            // waste of memory, because the intermediate shapes has no
633
            // corresponding objects, so no real value for history tracing.
634
            //
635
            // On the other hand, we still need to distinguish the original name
636
            // from the input object from the element name of the intermediate
637
            // shapes. So we limit ourselves to encode only one extra level
638
            // using the same tag. In order to do that, we need to de-hash the
639
            // previous level name, and check for its tag.
640
            Data::MappedName mappedName(name, 0, pos);
641
            Data::MappedName prev = dehashElementName(mappedName);
642
            long prevTag = 0;
643
            prev.findTagInElementName(&prevTag, nullptr, nullptr, nullptr, true);
644
            if (prevTag == inputTag || prevTag == -inputTag) {
645
                name = mappedName;
646
            }
647
        }
648
    }
649

650
    if (sids && this->hasher) {
651
        name = hashElementName(name, *sids);
652
        if (!forceTag && (tag == 0) && (ss.tellp() != 0)) {
653
            forceTag = true;
654
        }
655
    }
656
    if (forceTag || (tag != 0)) {
657
        assert(element_type);
658
        auto pos = ss.tellp();
659
        boost::io::ios_flags_saver ifs(ss);
660
        ss << POSTFIX_TAG << std::hex;
661
        if (tag < 0) {
662
            ss << '-' << -tag;
663
        }
664
        else if (tag != 0) {
665
            ss << tag;
666
        }
667
        assert(pos >= 0);
668
        if (pos != 0) {
669
            ss << ':' << pos;
670
        }
671
        ss << ',' << element_type;
672
    }
673
    name += ss.str();
674
}
675

676
MappedName ElementMap::hashElementName(const MappedName& name, ElementIDRefs& sids) const
677
{
678
    if (!this->hasher || !name) {
679
        return name;
680
    }
681
    if (name.find(ELEMENT_MAP_PREFIX) < 0) {
682
        return name;
683
    }
684
    App::StringIDRef sid = this->hasher->getID(name, sids);
685
    const auto& related = sid.relatedIDs();
686
    if (related == sids) {
687
        sids.clear();
688
        sids.push_back(sid);
689
    }
690
    else {
691
        ElementIDRefs tmp;
692
        tmp.push_back(sid);
693
        for (auto& checkSID : sids) {
694
            if (related.indexOf(checkSID) < 0) {
695
                tmp.push_back(checkSID);
696
            }
697
        }
698
        sids = tmp;
699
    }
700
    return MappedName(sid.toString());
701
}
702

703
MappedName ElementMap::dehashElementName(const MappedName& name) const
704
{
705
    if (name.empty()) {
706
        return name;
707
    }
708
    if (!this->hasher) {
709
        return name;
710
    }
711
    auto id = App::StringID::fromString(name.toRawBytes());
712
    if (!id) {
713
        return name;
714
    }
715
    auto sid = this->hasher->getID(id);
716
    if (!sid) {
717
        if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_TRACE)) {
718
            FC_WARN("failed to find hash id " << id);// NOLINT
719
        }
720
        else {
721
            FC_LOG("failed to find hash id " << id);// NOLINT
722
        }
723
        return name;
724
    }
725
    if (sid.isHashed()) {
726
        FC_LOG("cannot de-hash id " << id);// NOLINT
727
        return name;
728
    }
729
    MappedName ret(
730
        sid.toString());// FIXME .toString() was missing in original function. is this correct?
731
    FC_TRACE("de-hash " << name << " -> " << ret);// NOLINT
732
    return ret;
733
}
734

735
MappedName ElementMap::renameDuplicateElement(int index, const IndexedName& element,
736
                                              const IndexedName& element2, const MappedName& name,
737
                                              ElementIDRefs& sids, long masterTag) const
738
{
739
    int idx {0};
740
#ifdef FC_DEBUG
741
    idx = index;
742
#else
743
    static std::random_device _RD;
744
    static std::mt19937 _RGEN(_RD());
745
    static std::uniform_int_distribution<> _RDIST(1, 10000);
746
    (void)index;
747
    idx = _RDIST(_RGEN);
748
#endif
749
    std::ostringstream ss;
750
    ss << ELEMENT_MAP_PREFIX << 'D' << std::hex << idx;
751
    MappedName renamed(name);
752
    encodeElementName(element.getType()[0], renamed, ss, &sids, masterTag);
753
    if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
754
        FC_WARN("duplicate element mapping '"// NOLINT
755
                << name << " -> " << renamed << ' ' << element << '/' << element2);
756
    }
757
    return renamed;
758
}
759

760
void ElementMap::erase(const MappedName& name)
761
{
762
    auto it = this->mappedNames.find(name);
763
    if (it == this->mappedNames.end()) {
764
        return;
765
    }
766
    MappedNameRef* ref = findMappedRef(it->second);
767
    if (!ref) {
768
        return;
769
    }
770
    ref->erase(name);
771
    this->mappedNames.erase(it);
772
}
773

774
void ElementMap::erase(const IndexedName& idx)
775
{
776
    auto iter = this->indexedNames.find(idx.getType());
777
    if (iter == this->indexedNames.end()) {
778
        return;
779
    }
780
    auto& indices = iter->second;
781
    if (idx.getIndex() >= (int)indices.names.size()) {
782
        return;
783
    }
784
    auto& ref = indices.names[idx.getIndex()];
785
    for (auto* nameRef = &ref; nameRef; nameRef = nameRef->next.get()) {
786
        this->mappedNames.erase(nameRef->name);
787
    }
788
    ref.clear();
789
}
790

791
unsigned long ElementMap::size() const
792
{
793
    return mappedNames.size() + childElementSize;
794
}
795

796
bool ElementMap::empty() const
797
{
798
    return mappedNames.empty() && childElementSize == 0;
799
}
800

801
IndexedName ElementMap::find(const MappedName& name, ElementIDRefs* sids) const
802
{
803
    auto nameIter = mappedNames.find(name);
804
    if (nameIter == mappedNames.end()) {
805
        if (childElements.isEmpty()) {
806
            return IndexedName();
807
        }
808

809
        int len = 0;
810
        if (name.findTagInElementName(nullptr, &len, nullptr, nullptr, false, false) < 0) {
811
            return IndexedName();
812
        }
813
        QByteArray key = name.toRawBytes(len);
814
        auto it = this->childElements.find(key);
815
        if (it == this->childElements.end()) {
816
            return IndexedName();
817
        }
818

819
        const auto& child = *it.value().childMap;
820
        IndexedName res;
821

822
        MappedName childName = MappedName::fromRawData(name, 0, len);
823
        if (child.elementMap) {
824
            res = child.elementMap->find(childName, sids);
825
        }
826
        else {
827
            res = childName.toIndexedName();
828
        }
829

830
        if (res && boost::equals(res.getType(), child.indexedName.getType())
831
            && child.indexedName.getIndex() <= res.getIndex()
832
            && child.indexedName.getIndex() + child.count > res.getIndex()) {
833
            res.setIndex(res.getIndex() + it.value().childMap->offset);
834
            return res;
835
        }
836

837
        return IndexedName();
838
    }
839

840
    if (sids) {
841
        const MappedNameRef* ref = findMappedRef(nameIter->second);
842
        for (; ref; ref = ref->next.get()) {
843
            if (ref->name == name) {
844
                if (sids->empty()) {
845
                    *sids = ref->sids;
846
                }
847
                else {
848
                    *sids += ref->sids;
849
                }
850
                break;
851
            }
852
        }
853
    }
854
    return nameIter->second;
855
}
856

857
MappedName ElementMap::find(const IndexedName& idx, ElementIDRefs* sids) const
858
{
859
    if (!idx) {
860
        return {};
861
    }
862

863
    auto iter = this->indexedNames.find(idx.getType());
864
    if (iter == this->indexedNames.end()) {
865
        return {};
866
    }
867

868
    auto& indices = iter->second;
869
    if (idx.getIndex() < (int)indices.names.size()) {
870
        const MappedNameRef& ref = indices.names[idx.getIndex()];
871
        if (ref.name) {
872
            if (sids) {
873
                if (!sids->size()) {
874
                    *sids = ref.sids;
875
                }
876
                else {
877
                    *sids += ref.sids;
878
                }
879
            }
880
            return ref.name;
881
        }
882
    }
883

884
    auto it = indices.children.upper_bound(idx.getIndex());
885
    if (it != indices.children.end()
886
        && it->second.indexedName.getIndex() + it->second.offset <= idx.getIndex()) {
887
        auto& child = it->second;
888
        MappedName name;
889
        IndexedName childIdx(idx.getType(), idx.getIndex() - child.offset);
890
        if (child.elementMap) {
891
            name = child.elementMap->find(childIdx, sids);
892
        }
893
        else {
894
            name = MappedName(childIdx);
895
        }
896
        if (name) {
897
            name += child.postfix;
898
            return name;
899
        }
900
    }
901
    return {};
902
}
903

904
std::vector<std::pair<MappedName, ElementIDRefs>> ElementMap::findAll(const IndexedName& idx) const
905
{
906
    std::vector<std::pair<MappedName, ElementIDRefs>> res;
907
    if (!idx) {
908
        return res;
909
    }
910

911
    auto iter = this->indexedNames.find(idx.getType());
912
    if (iter == this->indexedNames.end()) {
913
        return res;
914
    }
915

916
    auto& indices = iter->second;
917
    if (idx.getIndex() < (int)indices.names.size()) {
918
        const MappedNameRef& ref = indices.names[idx.getIndex()];
919
        int count = 0;
920
        for (auto nameRef = &ref; nameRef; nameRef = nameRef->next.get()) {
921
            if (nameRef->name) {
922
                ++count;
923
            }
924
        }
925
        if (count != 0) {
926
            res.reserve(count);
927
            for (auto nameRef = &ref; nameRef; nameRef = nameRef->next.get()) {
928
                if (nameRef->name) {
929
                    res.emplace_back(nameRef->name, nameRef->sids);
930
                }
931
            }
932
            return res;
933
        }
934
    }
935

936
    auto it = indices.children.upper_bound(idx.getIndex());
937
    if (it != indices.children.end()
938
        && it->second.indexedName.getIndex() + it->second.offset <= idx.getIndex()) {
939
        auto& child = it->second;
940
        IndexedName childIdx(idx.getType(), idx.getIndex() - child.offset);
941
        if (child.elementMap) {
942
            res = child.elementMap->findAll(childIdx);
943
            for (auto& v : res) {
944
                v.first += child.postfix;
945
            }
946
        }
947
        else {
948
            res.emplace_back(MappedName(childIdx) + child.postfix, ElementIDRefs());
949
        }
950
    }
951

952
    return res;
953
}
954

955
const MappedNameRef* ElementMap::findMappedRef(const IndexedName& idx) const
956
{
957
    auto iter = this->indexedNames.find(idx.getType());
958
    if (iter == this->indexedNames.end()) {
959
        return nullptr;
960
    }
961
    auto& indices = iter->second;
962
    if (idx.getIndex() >= (int)indices.names.size()) {
963
        return nullptr;
964
    }
965
    return &indices.names[idx.getIndex()];
966
}
967

968
MappedNameRef* ElementMap::findMappedRef(const IndexedName& idx)
969
{
970
    auto iter = this->indexedNames.find(idx.getType());
971
    if (iter == this->indexedNames.end()) {
972
        return nullptr;
973
    }
974
    auto& indices = iter->second;
975
    if (idx.getIndex() >= (int)indices.names.size()) {
976
        return nullptr;
977
    }
978
    return &indices.names[idx.getIndex()];
979
}
980

981
MappedNameRef& ElementMap::mappedRef(const IndexedName& idx)
982
{
983
    assert(idx);
984
    auto& indices = this->indexedNames[idx.getType()];
985
    if (idx.getIndex() >= (int)indices.names.size()) {
986
        indices.names.resize(idx.getIndex() + 1);
987
    }
988
    return indices.names[idx.getIndex()];
989
}
990

991
bool ElementMap::hasChildElementMap() const
992
{
993
    return !childElements.empty();
994
}
995

996
void ElementMap::hashChildMaps(long masterTag)
997
{
998
    if (childElements.empty() || !this->hasher) {
999
        return;
1000
    }
1001
    std::ostringstream ss;
1002
    for (auto& indexedNameIndexedElements : this->indexedNames) {
1003
        for (auto& indexedChild : indexedNameIndexedElements.second.children) {
1004
            auto& child = indexedChild.second;
1005
            int len = 0;
1006
            long tag = 0;
1007
            int pos = MappedName::fromRawData(child.postfix)
1008
                          .findTagInElementName(&tag, &len, nullptr, nullptr, false, false);
1009
            // TODO: What is this 10?
1010
            if (pos > 10) {
1011
                MappedName postfix = hashElementName(
1012
                    MappedName::fromRawData(child.postfix.constData(), pos), child.sids);
1013
                ss.str("");
1014
                ss << MAPPED_CHILD_ELEMENTS_PREFIX << postfix;
1015
                MappedName tmp;
1016
                encodeElementName(
1017
                    child.indexedName[0], tmp, ss, nullptr, masterTag, nullptr, child.tag, true);
1018
                this->childElements.remove(child.postfix);
1019
                child.postfix = tmp.toBytes();
1020
                this->childElements[child.postfix].childMap = &child;
1021
            }
1022
        }
1023
    }
1024
}
1025

1026
void ElementMap::collectChildMaps(std::map<const ElementMap*, int>& childMapSet,
1027
                                  std::vector<const ElementMap*>& childMaps,
1028
                                  std::map<QByteArray, int>& postfixMap,
1029
                                  std::vector<QByteArray>& postfixes) const
1030
{
1031
    auto res = childMapSet.insert(std::make_pair(this, 0));
1032
    if (!res.second) {
1033
        return;
1034
    }
1035

1036
    for (auto& indexedName : this->indexedNames) {
1037
        addPostfix(QByteArray::fromRawData(indexedName.first,
1038
                                           static_cast<int>(qstrlen(indexedName.first))),
1039
                   postfixMap,
1040
                   postfixes);
1041

1042
        for (auto& childPair : indexedName.second.children) {
1043
            auto& child = childPair.second;
1044
            if (child.elementMap) {
1045
                child.elementMap->collectChildMaps(childMapSet, childMaps, postfixMap, postfixes);
1046
            }
1047
        }
1048
    }
1049

1050
    for (auto& mappedName : this->mappedNames) {
1051
        addPostfix(mappedName.first.constPostfix(), postfixMap, postfixes);
1052
    }
1053

1054
    childMaps.push_back(this);
1055
    res.first->second = (int)childMaps.size();
1056
}
1057

1058
void ElementMap::addChildElements(long masterTag, const std::vector<MappedChildElements>& children)
1059
{
1060
    std::ostringstream ss;
1061
    ss << std::hex;
1062

1063
    // To avoid possibly very long recursive child map lookup, resulting very
1064
    // long mapped names, we try to resolve the grand child map now.
1065
    std::vector<MappedChildElements> expansion;
1066
    for (auto it = children.begin(); it != children.end(); ++it) {
1067
        auto& child = *it;
1068
        if (!child.elementMap || child.elementMap->childElements.empty()) {
1069
            if (!expansion.empty()) {
1070
                expansion.push_back(child);
1071
            }
1072
            continue;
1073
        }
1074
        auto& indices = child.elementMap->indexedNames[child.indexedName.getType()];
1075
        if (indices.children.empty()) {
1076
            if (!expansion.empty()) {
1077
                expansion.push_back(child);
1078
            }
1079
            continue;
1080
        }
1081

1082
        // Note that it is allowable to have both mapped names and child map. We
1083
        // may have to split the current child mapping into pieces.
1084

1085
        int start = child.indexedName.getIndex();
1086
        int end = start + child.count;
1087
        for (auto iter = indices.children.upper_bound(start); iter != indices.children.end();
1088
             ++iter) {
1089
            auto& grandchild = iter->second;
1090
            int istart = grandchild.indexedName.getIndex() + grandchild.offset;
1091
            int iend = istart + grandchild.count;
1092
            if (end <= istart) {
1093
                break;
1094
            }
1095
            if (istart >= end) {
1096
                if (!expansion.empty()) {
1097
                    expansion.push_back(child);
1098
                    expansion.back().indexedName.setIndex(start);
1099
                    expansion.back().count = end - start;
1100
                }
1101
                break;
1102
            }
1103
            if (expansion.empty()) {
1104
                const int extra {10};
1105
                expansion.reserve(children.size() + extra);
1106
                expansion.insert(expansion.end(), children.begin(), it);
1107
            }
1108
            expansion.push_back(child);
1109
            auto* entry = &expansion.back();
1110
            if (istart > start) {
1111
                entry->indexedName.setIndex(start);
1112
                entry->count = istart - start;
1113

1114
                expansion.push_back(child);
1115
                entry = &expansion.back();
1116
            }
1117
            else {
1118
                istart = start;
1119
            }
1120

1121
            if (iend > end) {
1122
                iend = end;
1123
            }
1124

1125
            entry->indexedName.setIndex(istart - grandchild.offset);
1126
            entry->count = iend - istart;
1127
            entry->offset += grandchild.offset;
1128
            entry->elementMap = grandchild.elementMap;
1129
            entry->sids += grandchild.sids;
1130
            if (grandchild.postfix.size() != 0) {
1131
                if ((entry->postfix.size() != 0)
1132
                    && !entry->postfix.startsWith(ELEMENT_MAP_PREFIX)) {
1133
                    entry->postfix = grandchild.postfix + ELEMENT_MAP_PREFIX + entry->postfix;
1134
                }
1135
                else {
1136
                    entry->postfix = grandchild.postfix + entry->postfix;
1137
                }
1138
            }
1139

1140
            start = iend;
1141
            if (start >= end) {
1142
                break;
1143
            }
1144
        }
1145
        if (!expansion.empty() && start < end) {
1146
            expansion.push_back(child);
1147
            expansion.back().indexedName.setIndex(start);
1148
            expansion.back().count = end - start;
1149
        }
1150
    }
1151

1152
    for (auto& child : expansion.empty() ? children : expansion) {
1153
        if (!child.indexedName || (child.count == 0)) {
1154
            if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
1155
                FC_ERR("invalid mapped child element");// NOLINT
1156
            }
1157
            continue;
1158
        }
1159

1160
        ss.str("");
1161
        MappedName tmp;
1162

1163
        ChildMapInfo* entry = nullptr;
1164

1165
        // do child mapping only if the child element count >= 5
1166
        const int threshold {5};
1167
        if (child.count >= threshold || !child.elementMap) {
1168
            encodeElementName(child.indexedName[0],
1169
                              tmp,
1170
                              ss,
1171
                              nullptr,
1172
                              masterTag,
1173
                              child.postfix.constData(),
1174
                              child.tag,
1175
                              true);
1176

1177
            // Perform some disambiguation in case the same shape is mapped
1178
            // multiple times, e.g. draft array.
1179
            entry = &childElements[tmp.toBytes()];
1180
            int mapIndex = entry->mapIndices[child.elementMap.get()]++;
1181
            ++entry->index;
1182
            if (entry->index != 1 && child.elementMap && mapIndex == 0) {
1183
                // This child has duplicated 'tag' and 'postfix', but it
1184
                // has its own element map. We'll expand this map now.
1185
                entry = nullptr;
1186
            }
1187
        }
1188

1189
        if (!entry) {
1190
            IndexedName childIdx(child.indexedName);
1191
            IndexedName idx(childIdx.getType(), childIdx.getIndex() + child.offset);
1192
            for (int i = 0; i < child.count; ++i, ++childIdx, ++idx) {
1193
                ElementIDRefs sids;
1194
                MappedName name = child.elementMap->find(childIdx, &sids);
1195
                if (!name) {
1196
                    if ((child.tag == 0) || child.tag == masterTag) {
1197
                        if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
1198
                            FC_WARN("unmapped element");// NOLINT
1199
                        }
1200
                        continue;
1201
                    }
1202
                    name = MappedName(childIdx);
1203
                }
1204
                ss.str("");
1205
                encodeElementName(
1206
                    idx[0], name, ss, &sids, masterTag, child.postfix.constData(), child.tag);
1207
                setElementName(idx, name, masterTag, &sids);
1208
            }
1209
            continue;
1210
        }
1211

1212
        if (entry->index != 1) {
1213
            // There is some ambiguity in child mapping. We need some
1214
            // additional postfix for disambiguation. NOTE: We are not
1215
            // using ComplexGeoData::indexPostfix() so we don't confuse
1216
            // other code that actually uses this postfix for indexing
1217
            // purposes. Here, we just need some postfix for
1218
            // disambiguation. We don't need to extract the index.
1219
            ss.str("");
1220
            ss << ELEMENT_MAP_PREFIX << ":C" << entry->index - 1;
1221

1222
            tmp.clear();
1223
            encodeElementName(child.indexedName[0],
1224
                              tmp,
1225
                              ss,
1226
                              nullptr,
1227
                              masterTag,
1228
                              child.postfix.constData(),
1229
                              child.tag,
1230
                              true);
1231

1232
            entry = &childElements[tmp.toBytes()];
1233
            if (entry->childMap) {
1234
                FC_ERR("duplicate mapped child element");// NOLINT
1235
                continue;
1236
            }
1237
        }
1238

1239
        auto& indices = this->indexedNames[child.indexedName.getType()];
1240
        auto res = indices.children.emplace(
1241
            child.indexedName.getIndex() + child.offset + child.count, child);
1242
        if (!res.second) {
1243
            if (!entry->childMap) {
1244
                this->childElements.remove(tmp.toBytes());
1245
            }
1246
            FC_ERR("duplicate mapped child element");// NOLINT
1247
            continue;
1248
        }
1249

1250
        auto& insertedChild = res.first->second;
1251
        insertedChild.postfix = tmp.toBytes();
1252
        entry->childMap = &insertedChild;
1253
        childElementSize += insertedChild.count;
1254
    }
1255
}
1256

1257
std::vector<ElementMap::MappedChildElements> ElementMap::getChildElements() const
1258
{
1259
    std::vector<MappedChildElements> res;
1260
    res.reserve(this->childElements.size());
1261
    for (auto& childElement : this->childElements) {
1262
        res.push_back(*childElement.childMap);
1263
    }
1264
    return res;
1265
}
1266

1267
std::vector<MappedElement> ElementMap::getAll() const
1268
{
1269
    std::vector<MappedElement> ret;
1270
    ret.reserve(size());
1271
    for (auto& mappedName : this->mappedNames) {
1272
        ret.emplace_back(mappedName.first, mappedName.second);
1273
    }
1274
    for (auto& childElement : this->childElements) {
1275
        auto& child = *childElement.childMap;
1276
        IndexedName idx(child.indexedName);
1277
        idx.setIndex(idx.getIndex() + child.offset);
1278
        IndexedName childIdx(child.indexedName);
1279
        for (int i = 0; i < child.count; ++i, ++idx, ++childIdx) {
1280
            MappedName name;
1281
            if (child.elementMap) {
1282
                name = child.elementMap->find(childIdx);
1283
            }
1284
            else {
1285
                name = MappedName(childIdx);
1286
            }
1287
            if (name) {
1288
                name += child.postfix;
1289
                ret.emplace_back(name, idx);
1290
            }
1291
        }
1292
    }
1293
    return ret;
1294
}
1295

1296
long ElementMap::getElementHistory(const MappedName& name, long masterTag, MappedName* original,
1297
                                   std::vector<MappedName>* history) const
1298
{
1299
    long tag = 0;
1300
    int len = 0;
1301
    int pos = name.findTagInElementName(&tag, &len, nullptr, nullptr, true);
1302
    if (pos < 0) {
1303
        if (original) {
1304
            *original = name;
1305
        }
1306
        return tag;
1307
    }
1308
    if (!original && !history) {
1309
        return tag;
1310
    }
1311

1312
    MappedName tmp;
1313
    MappedName& ret = original ? *original : tmp;
1314
    if (name.startsWith(ELEMENT_MAP_PREFIX)) {
1315
        unsigned offset = ELEMENT_MAP_PREFIX_SIZE;
1316
        ret = MappedName::fromRawData(name, static_cast<int>(offset));
1317
    }
1318
    else {
1319
        ret = name;
1320
    }
1321

1322
    while (true) {
1323
        if ((len == 0) || len > pos) {
1324
            FC_WARN("invalid name length " << name);// NOLINT
1325
            return 0;
1326
        }
1327
        bool deHashed = false;
1328
        if (ret.startsWith(MAPPED_CHILD_ELEMENTS_PREFIX, len)) {
1329
            int offset = (int)POSTFIX_TAG_SIZE;
1330
            MappedName tmp2 = MappedName::fromRawData(ret, len + offset, pos - len - offset);
1331
            MappedName postfix = dehashElementName(tmp2);
1332
            if (postfix != tmp2) {
1333
                deHashed = true;
1334
                ret = MappedName::fromRawData(ret, 0, len) + postfix;
1335
            }
1336
        }
1337
        if (!deHashed) {
1338
            ret = dehashElementName(MappedName::fromRawData(ret, 0, len));
1339
        }
1340

1341
        long tag2 = 0;
1342
        pos = ret.findTagInElementName(&tag2, &len, nullptr, nullptr, true);
1343
        if (pos < 0 || (tag2 != tag && tag2 != -tag && tag != masterTag && -tag != masterTag)) {
1344
            return tag;
1345
        }
1346
        tag = tag2;
1347
        if (history) {
1348
            history->push_back(ret.copy());
1349
        }
1350
    }
1351
}
1352

1353
void ElementMap::traceElement(const MappedName& name, long masterTag, TraceCallback cb) const
1354
{
1355
    long encodedTag = 0;
1356
    int len = 0;
1357

1358
    auto pos = name.findTagInElementName(&encodedTag, &len, nullptr, nullptr, true);
1359
    if (cb(name, len, encodedTag, masterTag) || pos < 0) {
1360
        return;
1361
    }
1362

1363
    if (name.startsWith(POSTFIX_EXTERNAL_TAG, len)) {
1364
        return;
1365
    }
1366

1367
    std::set<long> tagSet;
1368

1369
    std::vector<MappedName> names;
1370
    if (masterTag) {
1371
        tagSet.insert(std::abs(masterTag));
1372
    }
1373
    if (encodedTag) {
1374
        tagSet.insert(std::abs(encodedTag));
1375
    }
1376
    names.push_back(name);
1377

1378
    masterTag = encodedTag;
1379
    MappedName tmp;
1380
    bool first = true;
1381

1382
    // TODO: element tracing without object is inherently unsafe, because of
1383
    // possible external linking object which means the element may be encoded
1384
    // using external string table. Looking up the wrong table may accidentally
1385
    // cause circular mapping, and is actually quite easy to reproduce. See
1386
    //
1387
    // https://github.com/realthunder/FreeCAD_assembly3/issues/968
1388
    //
1389
    // An arbitrary depth limit is set here to not waste time. 'tagSet' above is
1390
    // also used for early detection of 'recursive' mapping.
1391

1392
    for (int index = 0; index < 50; ++index) {
1393
        if (!len || len > pos) {
1394
            return;
1395
        }
1396
        if (first) {
1397
            first = false;
1398
            size_t offset = 0;
1399
            if (name.startsWith(ELEMENT_MAP_PREFIX)) {
1400
                offset = ELEMENT_MAP_PREFIX_SIZE;
1401
            }
1402
            tmp = MappedName(name, offset, len);
1403
        }
1404
        else {
1405
            tmp = MappedName(tmp, 0, len);
1406
        }
1407
        tmp = dehashElementName(tmp);
1408
        names.push_back(tmp);
1409
        encodedTag = 0;
1410
        pos = tmp.findTagInElementName(&encodedTag, &len, nullptr, nullptr, true);
1411
        if (pos >= 0 && tmp.startsWith(POSTFIX_EXTERNAL_TAG, len)) {
1412
            break;
1413
        }
1414

1415
        if (encodedTag && masterTag != std::abs(encodedTag)
1416
            && !tagSet.insert(std::abs(encodedTag)).second) {
1417
            if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_LOG)) {
1418
                FC_WARN("circular element mapping");
1419
                if (FC_LOG_INSTANCE.isEnabled(FC_LOGLEVEL_TRACE)) {
1420
                    auto doc = App::GetApplication().getActiveDocument();
1421
                    if (doc) {
1422
                        auto obj = doc->getObjectByID(masterTag);
1423
                        if (obj) {
1424
                            FC_LOG("\t" << obj->getFullName() << obj->getFullName() << "." << name);
1425
                        }
1426
                    }
1427
                    for (auto& errname : names) {
1428
                        FC_ERR("\t" << errname);
1429
                    }
1430
                }
1431
            }
1432
            break;
1433
        }
1434

1435
        if (cb(tmp, len, encodedTag, masterTag) || pos < 0) {
1436
            return;
1437
        }
1438
        masterTag = encodedTag;
1439
    }
1440
}
1441

1442

1443
}// Namespace Data
1444