1//===-- CodeGen/CGObjCMacConstantLiteralUtil.h - ----------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This should be used for things that effect the ABI of
10// Obj-C constant initializer literals (`-fobjc-constant-literals`) to allow
11// future changes without breaking the ABI promises.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_LIB_CODEGEN_CGOBJCMACCONSTANTLITERALUTIL_H
16#define LLVM_CLANG_LIB_CODEGEN_CGOBJCMACCONSTANTLITERALUTIL_H
17
18#include "CGObjCRuntime.h"
19#include "clang/AST/ExprObjC.h"
20#include "clang/AST/Type.h"
21#include "llvm/ADT/APFloat.h"
22#include "llvm/ADT/APSInt.h"
23#include "llvm/ADT/ArrayRef.h"
24#include "llvm/ADT/DenseMapInfo.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/Support/ConvertUTF.h"
27#include <numeric>
28
29namespace clang {
30namespace CodeGen {
31namespace CGObjCMacConstantLiteralUtil {
32
33class NSConstantNumberMapInfo {
34
35 enum class MapInfoType {
36 Empty,
37 Int,
38 Float,
39 };
40
41 MapInfoType InfoType;
42 CanQualType QType;
43 llvm::APSInt Int;
44 llvm::APFloat Float;
45
46 /// Default constructor that can create an Empty info entry.
47 explicit NSConstantNumberMapInfo(MapInfoType I = MapInfoType::Empty)
48 : InfoType(I), QType(), Int(), Float(0.0) {}
49
50 bool isEmpty() const { return InfoType == MapInfoType::Empty; }
51
52public:
53 NSConstantNumberMapInfo(CanQualType QT, const llvm::APSInt &V)
54 : InfoType(MapInfoType::Int), QType(QT), Int(V), Float(0.0) {}
55 NSConstantNumberMapInfo(CanQualType QT, const llvm::APFloat &V)
56 : InfoType(MapInfoType::Float), QType(QT), Int(), Float(V) {}
57
58 unsigned getHashValue() const {
59 assert(!isEmpty() && "Cannot hash empty map info!");
60
61 unsigned QTypeHash = llvm::DenseMapInfo<QualType>::getHashValue(Val: QType);
62
63 if (InfoType == MapInfoType::Int)
64 return llvm::detail::combineHashValue(a: (unsigned)Int.getZExtValue(),
65 b: QTypeHash);
66
67 assert(InfoType == MapInfoType::Float);
68 return llvm::detail::combineHashValue(
69 a: (unsigned)Float.bitcastToAPInt().getZExtValue(), b: QTypeHash);
70 }
71
72 bool operator==(const NSConstantNumberMapInfo &RHS) const {
73 if (InfoType != RHS.InfoType || QType != RHS.QType)
74 return false;
75
76 // Handle the empty equality.
77 if (isEmpty())
78 return true;
79
80 if (InfoType == MapInfoType::Int)
81 return llvm::APSInt::isSameValue(I1: Int, I2: RHS.Int);
82
83 assert(InfoType == MapInfoType::Float);
84
85 // handle -0, NaN, and infinities correctly
86 return Float.bitwiseIsEqual(RHS: RHS.Float);
87 }
88};
89
90using std::iota;
91
92class NSDictionaryBuilder {
93 SmallVector<std::pair<llvm::Constant *, llvm::Constant *>, 16> Elements;
94 uint64_t Opts;
95
96public:
97 enum class Options : uint64_t { Sorted = 1 };
98
99 NSDictionaryBuilder(
100 const ObjCDictionaryLiteral *E,
101 ArrayRef<std::pair<llvm::Constant *, llvm::Constant *>> KeysAndObjects,
102 const Options O = Options::Sorted,
103 // When keys are emitted as constant CFStrings (the default), they are
104 // stored and looked up as UTF-16, so sort by UTF-16 code unit. When
105 // -fno-constant-cfstrings is passed, keys are instead emitted as
106 // OBJC_CLASS_$_NSConstantString and compared as raw bytes at lookup
107 // time, so sort by UTF-8 byte order (LKS < RKS) to match.
108 bool SortKeysByUTF16 = true) {
109 Opts = static_cast<uint64_t>(O);
110 uint64_t const NumElements = KeysAndObjects.size();
111
112 // Reserve the capacity for the sorted keys & values
113 Elements.reserve(N: NumElements);
114
115 // Setup the element indicies 0 ..< NumElements
116 SmallVector<size_t, 16> ElementIndicies(NumElements);
117 std::iota(first: ElementIndicies.begin(), last: ElementIndicies.end(), value: 0);
118
119 // Precompute the UTF-16 form of each string key (unless the keys are not
120 // emitted as constant CFStrings, in which case UTF-16 comparison does not
121 // apply). The runtime stores constant-CFString keys as UTF-16 and looks
122 // them up by UTF-16 code-unit order, so we must sort by the same order
123 // here. Sorting by the raw UTF-8 bytes instead would diverge for keys
124 // mixing characters in U+E000..U+FFFF with astral characters
125 // (U+10000..U+10FFFF), because UTF-16 encodes the latter with lead
126 // surrogates (0xD800..0xDBFF) that sort *below* 0xE000 -- causing the
127 // runtime's lookup to miss keys that are actually present.
128 //
129 // A key need not be well-formed UTF-8: string literals with invalid or
130 // partial sequences are legal in the AST (Sema warns about them separately;
131 // see warn_objc_dictionary_ill_formed_utf8_key). We deliberately mirror the
132 // constant CFString emitter (CodeGenModule::GetConstantCFStringEntry),
133 // which runs ConvertUTF8toUTF16 with strictConversion and keeps whatever
134 // prefix converts successfully, so we sort by exactly the code units the
135 // string is stored and looked up as. Any trailing bytes that fail to
136 // convert are dropped from the sort key; this cannot crash and yields a
137 // valid strict-weak ordering regardless of well-formedness.
138 //
139 // The raw UTF-8 bytes of each key, used for byte-order sorting when the
140 // keys are not emitted as UTF-16 constant CFStrings.
141 SmallVector<StringRef, 16> KeysUTF8;
142 KeysUTF8.reserve(N: NumElements);
143 SmallVector<SmallVector<llvm::UTF16, 16>, 16> KeysUTF16(NumElements);
144 for (size_t I = 0; I < NumElements; ++I) {
145 Expr *const K = E->getKeyValueElement(Index: I).Key->IgnoreImpCasts();
146 auto *SL = cast<ObjCStringLiteral>(Val: K);
147 // NOTE: Using the `StringLiteral->getString()` since it checks that
148 // `chars` are 1 byte
149 StringRef KS = SL->getString()->getString();
150 KeysUTF8.push_back(Elt: KS);
151 if (!SortKeysByUTF16)
152 continue;
153 SmallVectorImpl<llvm::UTF16> &Dst = KeysUTF16[I];
154 Dst.resize(N: KS.size()); // UTF-16 needs <= as many code units as UTF-8.
155 const llvm::UTF8 *SrcPtr =
156 reinterpret_cast<const llvm::UTF8 *>(KS.data());
157 llvm::UTF16 *DstPtr = Dst.data();
158 llvm::ConvertUTF8toUTF16(sourceStart: &SrcPtr, sourceEnd: SrcPtr + KS.size(), targetStart: &DstPtr,
159 targetEnd: DstPtr + Dst.size(), flags: llvm::strictConversion);
160 // ConvertUTF8toUTF16 advances DstPtr to the end of the converted prefix.
161 Dst.truncate(N: DstPtr - Dst.data());
162 }
163
164 // Now perform the sorts and shift the indicies as needed
165 llvm::stable_sort(Range&: ElementIndicies, C: [O, SortKeysByUTF16, &KeysUTF8,
166 &KeysUTF16](size_t LI, size_t RI) {
167 // This is a deterministic total order, so it still aids link-time
168 // de-dupe, and it supports the runtime's `O(log n)` worst-case
169 // lookup. ArrayRef::operator< is a lexicographic code-unit
170 // comparison.
171 if (O == Options::Sorted) {
172 if (SortKeysByUTF16)
173 return ArrayRef<llvm::UTF16>(KeysUTF16[LI]) <
174 ArrayRef<llvm::UTF16>(KeysUTF16[RI]);
175 // Sort by raw UTF-8 byte order (LKS < RKS) to match the lookup
176 // order used for OBJC_CLASS_$_NSConstantString keys.
177 return KeysUTF8[LI] < KeysUTF8[RI];
178 }
179 llvm_unreachable("Unexpected `NSDictionaryBuilder::Options given");
180 });
181
182 // Finally use the sorted indicies to insert into `Elements`.
183 for (auto &Idx : ElementIndicies) {
184 Elements.push_back(Elt: KeysAndObjects[Idx]);
185 }
186 }
187
188 SmallVectorImpl<std::pair<llvm::Constant *, llvm::Constant *>> &
189 getElements() {
190 return Elements;
191 }
192
193 Options getOptions() const { return static_cast<Options>(Opts); }
194
195 uint64_t getNumElements() const { return Elements.size(); }
196};
197
198} // namespace CGObjCMacConstantLiteralUtil
199} // namespace CodeGen
200} // namespace clang
201
202namespace llvm {
203
204using namespace clang::CodeGen::CGObjCMacConstantLiteralUtil;
205
206template <> struct DenseMapInfo<NSConstantNumberMapInfo> {
207 static unsigned getHashValue(const NSConstantNumberMapInfo &S) {
208 return S.getHashValue();
209 }
210
211 static bool isEqual(const NSConstantNumberMapInfo &LHS,
212 const NSConstantNumberMapInfo &RHS) {
213 return LHS == RHS;
214 }
215};
216
217} // namespace llvm
218
219#endif
220