1 //===-- DiffEngine.cpp - Structural file comparison -----------------------===//
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 file defines the implementation of the llvm-tapi difference
10 // engine, which structurally compares two tbd files.
11 //
12 //===----------------------------------------------------------------------===/
13 #include "DiffEngine.h"
14 #include "llvm/Support/Casting.h"
15 #include "llvm/Support/raw_ostream.h"
16 #include "llvm/TextAPI/InterfaceFile.h"
17 #include "llvm/TextAPI/Target.h"
18 
19 using namespace llvm;
20 using namespace MachO;
21 using namespace object;
22 
23 StringRef setOrderIndicator(InterfaceInputOrder Order) {
24   return ((Order == lhs) ? "< " : "> ");
25 }
26 
27 template <typename T, DiffAttrKind U>
28 inline void DiffScalarVal<T, U>::print(raw_ostream &OS, std::string Indent) {
29   OS << Indent << "\t" << setOrderIndicator(Order) << Val << "\n";
30 }
31 
32 template <>
33 inline void
34 DiffScalarVal<StringRef, AD_Diff_Scalar_Str>::print(raw_ostream &OS,
35                                                     std::string Indent) {
36   OS << Indent << "\t\t" << setOrderIndicator(Order) << Val << "\n";
37 }
38 
39 template <>
40 inline void
41 DiffScalarVal<uint8_t, AD_Diff_Scalar_Unsigned>::print(raw_ostream &OS,
42                                                        std::string Indent) {
43   OS << Indent << "\t" << setOrderIndicator(Order) << std::to_string(Val)
44      << "\n";
45 }
46 
47 template <>
48 inline void
49 DiffScalarVal<bool, AD_Diff_Scalar_Bool>::print(raw_ostream &OS,
50                                                 std::string Indent) {
51   OS << Indent << "\t" << setOrderIndicator(Order)
52      << ((Val == true) ? "true" : "false") << "\n";
53 }
54 
55 std::string SymScalar::stringifySymbolKind(MachO::SymbolKind Kind) {
56   switch (Kind) {
57   case MachO::SymbolKind::GlobalSymbol:
58     return "";
59   case MachO::SymbolKind::ObjectiveCClass:
60     return "_OBJC_METACLASS_$_";
61   case MachO::SymbolKind ::ObjectiveCClassEHType:
62     return "_OBJC_EHTYPE_$_";
63   case MachO::SymbolKind ::ObjectiveCInstanceVariable:
64     return "_OBJC_IVAR_$_";
65   }
66   llvm_unreachable("Unknown llvm::MachO::SymbolKind enum");
67 }
68 
69 std::string SymScalar::stringifySymbolFlag(MachO::SymbolFlags Flag) {
70   switch (Flag) {
71   case MachO::SymbolFlags::None:
72     return "";
73   case MachO::SymbolFlags::ThreadLocalValue:
74     return "Thread-Local";
75   case MachO::SymbolFlags::WeakDefined:
76     return "Weak-Defined";
77   case MachO::SymbolFlags::WeakReferenced:
78     return "Weak-Referenced";
79   case MachO::SymbolFlags::Undefined:
80     return "Undefined";
81   case MachO::SymbolFlags::Rexported:
82     return "Reexported";
83   }
84   llvm_unreachable("Unknown llvm::MachO::SymbolFlags enum");
85 }
86 
87 void SymScalar::print(raw_ostream &OS, std::string Indent, MachO::Target Targ) {
88   if (Val->getKind() == MachO::SymbolKind::ObjectiveCClass) {
89     if (Targ.Arch == MachO::AK_i386 &&
90         Targ.Platform == MachO::PlatformKind::macOS) {
91       OS << Indent << "\t\t" << ((Order == lhs) ? "< " : "> ")
92          << ".objc_class_name_" << Val->getName()
93          << getFlagString(Val->getFlags()) << "\n";
94       return;
95     }
96     OS << Indent << "\t\t" << ((Order == lhs) ? "< " : "> ") << "_OBJC_CLASS_$_"
97        << Val->getName() << getFlagString(Val->getFlags()) << "\n";
98   }
99   OS << Indent << "\t\t" << ((Order == lhs) ? "< " : "> ")
100      << stringifySymbolKind(Val->getKind()) << Val->getName()
101      << getFlagString(Val->getFlags()) << "\n";
102 }
103 
104 bool checkSymbolEquality(llvm::MachO::InterfaceFile::const_symbol_range LHS,
105                          llvm::MachO::InterfaceFile::const_symbol_range RHS) {
106   return std::equal(LHS.begin(), LHS.end(), RHS.begin(),
107                     [&](auto LHS, auto RHS) { return *LHS == *RHS; });
108 }
109 
110 template <typename TargetVecT, typename ValVecT, typename V>
111 void addDiffForTargSlice(V Val, Target Targ, DiffOutput &Diff,
112                          InterfaceInputOrder Order) {
113   auto TargetVector = llvm::find_if(
114       Diff.Values, [&](const std::unique_ptr<AttributeDiff> &RawTVec) {
115         if (TargetVecT *TVec = dyn_cast<TargetVecT>(RawTVec.get()))
116           return TVec->Targ == Targ;
117         return false;
118       });
119   if (TargetVector != Diff.Values.end()) {
120     ValVecT NewValVec(Order, Val);
121     cast<TargetVecT>(TargetVector->get())->TargValues.push_back(NewValVec);
122   } else {
123     auto NewTargetVec = std::make_unique<TargetVecT>(Targ);
124     ValVecT NewValVec(Order, Val);
125     NewTargetVec->TargValues.push_back(NewValVec);
126     Diff.Values.push_back(std::move(NewTargetVec));
127   }
128 }
129 
130 DiffOutput getSingleAttrDiff(const std::vector<InterfaceFileRef> &IRefVec,
131                              std::string Name, InterfaceInputOrder Order) {
132   DiffOutput Diff(Name);
133   Diff.Kind = AD_Str_Vec;
134   for (const auto &IRef : IRefVec)
135     for (auto Targ : IRef.targets())
136       addDiffForTargSlice<DiffStrVec,
137                           DiffScalarVal<StringRef, AD_Diff_Scalar_Str>>(
138           IRef.getInstallName(), Targ, Diff, Order);
139   return Diff;
140 }
141 
142 DiffOutput
143 getSingleAttrDiff(const std::vector<std::pair<Target, std::string>> &PairVec,
144                   std::string Name, InterfaceInputOrder Order) {
145   DiffOutput Diff(Name);
146   Diff.Kind = AD_Str_Vec;
147   for (const auto &Pair : PairVec)
148     addDiffForTargSlice<DiffStrVec,
149                         DiffScalarVal<StringRef, AD_Diff_Scalar_Str>>(
150         StringRef(Pair.second), Pair.first, Diff, Order);
151   return Diff;
152 }
153 
154 DiffOutput getSingleAttrDiff(InterfaceFile::const_symbol_range SymRange,
155                              std::string Name, InterfaceInputOrder Order) {
156   DiffOutput Diff(Name);
157   Diff.Kind = AD_Sym_Vec;
158   for (const auto *Sym : SymRange)
159     for (auto Targ : Sym->targets())
160       addDiffForTargSlice<DiffSymVec, SymScalar>(Sym, Targ, Diff, Order);
161   return Diff;
162 }
163 
164 template <typename T>
165 DiffOutput getSingleAttrDiff(T SingleAttr, std::string Attribute) {
166   DiffOutput Diff(Attribute);
167   Diff.Kind = SingleAttr.getKind();
168   Diff.Values.push_back(std::make_unique<T>(SingleAttr));
169   return Diff;
170 }
171 
172 template <typename T, DiffAttrKind U>
173 void diffAttribute(std::string Name, std::vector<DiffOutput> &Output,
174                    DiffScalarVal<T, U> Attr) {
175   Output.push_back(getSingleAttrDiff(Attr, Name));
176 }
177 
178 template <typename T>
179 void diffAttribute(std::string Name, std::vector<DiffOutput> &Output,
180                    const T &Val, InterfaceInputOrder Order) {
181   Output.push_back(getSingleAttrDiff(Val, Name, Order));
182 }
183 
184 std::vector<DiffOutput> getSingleIF(InterfaceFile *Interface,
185                                     InterfaceInputOrder Order) {
186   std::vector<DiffOutput> Output;
187   diffAttribute("Install Name", Output,
188                 DiffScalarVal<StringRef, AD_Diff_Scalar_Str>(
189                     Order, Interface->getInstallName()));
190   diffAttribute("Current Version", Output,
191                 DiffScalarVal<PackedVersion, AD_Diff_Scalar_PackedVersion>(
192                     Order, Interface->getCurrentVersion()));
193   diffAttribute("Compatibility Version", Output,
194                 DiffScalarVal<PackedVersion, AD_Diff_Scalar_PackedVersion>(
195                     Order, Interface->getCompatibilityVersion()));
196   diffAttribute("Swift ABI Version", Output,
197                 DiffScalarVal<uint8_t, AD_Diff_Scalar_Unsigned>(
198                     Order, Interface->getSwiftABIVersion()));
199   diffAttribute("InstallAPI", Output,
200                 DiffScalarVal<bool, AD_Diff_Scalar_Bool>(
201                     Order, Interface->isInstallAPI()));
202   diffAttribute("Two Level Namespace", Output,
203                 DiffScalarVal<bool, AD_Diff_Scalar_Bool>(
204                     Order, Interface->isTwoLevelNamespace()));
205   diffAttribute("Application Extension Safe", Output,
206                 DiffScalarVal<bool, AD_Diff_Scalar_Bool>(
207                     Order, Interface->isApplicationExtensionSafe()));
208   diffAttribute("Reexported Libraries", Output,
209                 Interface->reexportedLibraries(), Order);
210   diffAttribute("Allowable Clients", Output, Interface->allowableClients(),
211                 Order);
212   diffAttribute("Parent Umbrellas", Output, Interface->umbrellas(), Order);
213   diffAttribute("Symbols", Output, Interface->symbols(), Order);
214   for (auto Doc : Interface->documents()) {
215     DiffOutput Documents("Inlined Reexported Frameworks/Libraries");
216     Documents.Kind = AD_Inline_Doc;
217     Documents.Values.push_back(std::make_unique<InlineDoc>(
218         InlineDoc(Doc->getInstallName(), getSingleIF(Doc.get(), Order))));
219     Output.push_back(std::move(Documents));
220   }
221   return Output;
222 }
223 
224 void findAndAddDiff(const std::vector<InterfaceFileRef> &CollectedIRefVec,
225                     const std::vector<InterfaceFileRef> &LookupIRefVec,
226                     DiffOutput &Result, InterfaceInputOrder Order) {
227   Result.Kind = AD_Str_Vec;
228   for (const auto &IRef : CollectedIRefVec)
229     for (auto Targ : IRef.targets()) {
230       auto FoundIRef = llvm::find_if(LookupIRefVec, [&](const auto LIRef) {
231         auto FoundTarg = llvm::find(LIRef.targets(), Targ);
232         return (FoundTarg != LIRef.targets().end() &&
233                 IRef.getInstallName() == LIRef.getInstallName());
234       });
235       if (FoundIRef == LookupIRefVec.end())
236         addDiffForTargSlice<DiffStrVec,
237                             DiffScalarVal<StringRef, AD_Diff_Scalar_Str>>(
238             IRef.getInstallName(), Targ, Result, Order);
239     }
240 }
241 
242 void findAndAddDiff(
243     const std::vector<std::pair<Target, std::string>> &CollectedPairs,
244     const std::vector<std::pair<Target, std::string>> &LookupPairs,
245     DiffOutput &Result, InterfaceInputOrder Order) {
246   Result.Kind = AD_Str_Vec;
247   for (const auto &Pair : CollectedPairs) {
248     auto FoundPair = llvm::find(LookupPairs, Pair);
249     if (FoundPair == LookupPairs.end())
250       addDiffForTargSlice<DiffStrVec,
251                           DiffScalarVal<StringRef, AD_Diff_Scalar_Str>>(
252           StringRef(Pair.second), Pair.first, Result, Order);
253   }
254 }
255 
256 void findAndAddDiff(InterfaceFile::const_symbol_range CollectedSyms,
257                     InterfaceFile::const_symbol_range LookupSyms,
258                     DiffOutput &Result, InterfaceInputOrder Order) {
259   Result.Kind = AD_Sym_Vec;
260   for (const auto *Sym : CollectedSyms)
261     for (const auto Targ : Sym->targets()) {
262       auto FoundSym = llvm::find_if(LookupSyms, [&](const auto LSym) {
263         auto FoundTarg = llvm::find(LSym->targets(), Targ);
264         return (Sym->getName() == LSym->getName() &&
265                 Sym->getKind() == LSym->getKind() &&
266                 Sym->getFlags() == LSym->getFlags() &&
267                 FoundTarg != LSym->targets().end());
268       });
269       if (FoundSym == LookupSyms.end())
270         addDiffForTargSlice<DiffSymVec, SymScalar>(Sym, Targ, Result, Order);
271     }
272 }
273 
274 template <typename T>
275 DiffOutput recordDifferences(T LHS, T RHS, std::string Attr) {
276   DiffOutput Diff(Attr);
277   if (LHS.getKind() == RHS.getKind()) {
278     Diff.Kind = LHS.getKind();
279     Diff.Values.push_back(std::make_unique<T>(LHS));
280     Diff.Values.push_back(std::make_unique<T>(RHS));
281   }
282   return Diff;
283 }
284 
285 template <typename T>
286 DiffOutput recordDifferences(const std::vector<T> &LHS,
287                              const std::vector<T> &RHS, std::string Attr) {
288   DiffOutput Diff(Attr);
289   Diff.Kind = AD_Str_Vec;
290   findAndAddDiff(LHS, RHS, Diff, lhs);
291   findAndAddDiff(RHS, LHS, Diff, rhs);
292   return Diff;
293 }
294 
295 DiffOutput recordDifferences(llvm::MachO::InterfaceFile::const_symbol_range LHS,
296                              llvm::MachO::InterfaceFile::const_symbol_range RHS,
297                              std::string Attr) {
298   DiffOutput Diff(Attr);
299   Diff.Kind = AD_Sym_Vec;
300   findAndAddDiff(LHS, RHS, Diff, lhs);
301   findAndAddDiff(RHS, LHS, Diff, rhs);
302   return Diff;
303 }
304 
305 std::vector<DiffOutput>
306 DiffEngine::findDifferences(const InterfaceFile *IFLHS,
307                             const InterfaceFile *IFRHS) {
308   std::vector<DiffOutput> Output;
309   if (IFLHS->getInstallName() != IFRHS->getInstallName())
310     Output.push_back(recordDifferences(
311         DiffScalarVal<StringRef, AD_Diff_Scalar_Str>(lhs,
312                                                      IFLHS->getInstallName()),
313         DiffScalarVal<StringRef, AD_Diff_Scalar_Str>(rhs,
314                                                      IFRHS->getInstallName()),
315         "Install Name"));
316 
317   if (IFLHS->getCurrentVersion() != IFRHS->getCurrentVersion())
318     Output.push_back(recordDifferences(
319         DiffScalarVal<PackedVersion, AD_Diff_Scalar_PackedVersion>(
320             lhs, IFLHS->getCurrentVersion()),
321         DiffScalarVal<PackedVersion, AD_Diff_Scalar_PackedVersion>(
322             rhs, IFRHS->getCurrentVersion()),
323         "Current Version"));
324   if (IFLHS->getCompatibilityVersion() != IFRHS->getCompatibilityVersion())
325     Output.push_back(recordDifferences(
326         DiffScalarVal<PackedVersion, AD_Diff_Scalar_PackedVersion>(
327             lhs, IFLHS->getCompatibilityVersion()),
328         DiffScalarVal<PackedVersion, AD_Diff_Scalar_PackedVersion>(
329             rhs, IFRHS->getCompatibilityVersion()),
330         "Compatibility Version"));
331   if (IFLHS->getSwiftABIVersion() != IFRHS->getSwiftABIVersion())
332     Output.push_back(
333         recordDifferences(DiffScalarVal<uint8_t, AD_Diff_Scalar_Unsigned>(
334                               lhs, IFLHS->getSwiftABIVersion()),
335                           DiffScalarVal<uint8_t, AD_Diff_Scalar_Unsigned>(
336                               rhs, IFRHS->getSwiftABIVersion()),
337                           "Swift ABI Version"));
338   if (IFLHS->isInstallAPI() != IFRHS->isInstallAPI())
339     Output.push_back(recordDifferences(
340         DiffScalarVal<bool, AD_Diff_Scalar_Bool>(lhs, IFLHS->isInstallAPI()),
341         DiffScalarVal<bool, AD_Diff_Scalar_Bool>(rhs, IFRHS->isInstallAPI()),
342         "InstallAPI"));
343 
344   if (IFLHS->isTwoLevelNamespace() != IFRHS->isTwoLevelNamespace())
345     Output.push_back(recordDifferences(DiffScalarVal<bool, AD_Diff_Scalar_Bool>(
346                                            lhs, IFLHS->isTwoLevelNamespace()),
347                                        DiffScalarVal<bool, AD_Diff_Scalar_Bool>(
348                                            rhs, IFRHS->isTwoLevelNamespace()),
349                                        "Two Level Namespace"));
350 
351   if (IFLHS->isApplicationExtensionSafe() !=
352       IFRHS->isApplicationExtensionSafe())
353     Output.push_back(
354         recordDifferences(DiffScalarVal<bool, AD_Diff_Scalar_Bool>(
355                               lhs, IFLHS->isApplicationExtensionSafe()),
356                           DiffScalarVal<bool, AD_Diff_Scalar_Bool>(
357                               rhs, IFRHS->isApplicationExtensionSafe()),
358                           "Application Extension Safe"));
359 
360   if (IFLHS->reexportedLibraries() != IFRHS->reexportedLibraries())
361     Output.push_back(recordDifferences(IFLHS->reexportedLibraries(),
362                                        IFRHS->reexportedLibraries(),
363                                        "Reexported Libraries"));
364 
365   if (IFLHS->allowableClients() != IFRHS->allowableClients())
366     Output.push_back(recordDifferences(IFLHS->allowableClients(),
367                                        IFRHS->allowableClients(),
368                                        "Allowable Clients"));
369 
370   if (IFLHS->umbrellas() != IFRHS->umbrellas())
371     Output.push_back(recordDifferences(IFLHS->umbrellas(), IFRHS->umbrellas(),
372                                        "Parent Umbrellas"));
373 
374   if (!checkSymbolEquality(IFLHS->symbols(), IFRHS->symbols()))
375     Output.push_back(
376         recordDifferences(IFLHS->symbols(), IFRHS->symbols(), "Symbols"));
377 
378   if (IFLHS->documents() != IFRHS->documents()) {
379     DiffOutput Docs("Inlined Reexported Frameworks/Libraries");
380     Docs.Kind = AD_Inline_Doc;
381     std::vector<StringRef> DocsInserted;
382     // Iterate through inline frameworks/libraries from interface file and find
383     // match based on install name.
384     for (auto DocLHS : IFLHS->documents()) {
385       auto Pair = llvm::find_if(IFRHS->documents(), [&](const auto &DocRHS) {
386         return (DocLHS->getInstallName() == DocRHS->getInstallName());
387       });
388       // If a match found, recursively get differences between the pair.
389       if (Pair != IFRHS->documents().end()) {
390         InlineDoc PairDiff =
391             InlineDoc(DocLHS->getInstallName(),
392                       findDifferences(DocLHS.get(), Pair->get()));
393         if (!PairDiff.DocValues.empty())
394           Docs.Values.push_back(
395               std::make_unique<InlineDoc>(std::move(PairDiff)));
396       }
397       // If a match is not found, get attributes from single item.
398       else
399         Docs.Values.push_back(std::make_unique<InlineDoc>(InlineDoc(
400             DocLHS->getInstallName(), getSingleIF(DocLHS.get(), lhs))));
401       DocsInserted.push_back(DocLHS->getInstallName());
402     }
403     for (auto DocRHS : IFRHS->documents()) {
404       auto WasGathered =
405           llvm::find_if(DocsInserted, [&](const auto &GatheredDoc) {
406             return (GatheredDoc == DocRHS->getInstallName());
407           });
408       if (WasGathered == DocsInserted.end())
409         Docs.Values.push_back(std::make_unique<InlineDoc>(InlineDoc(
410             DocRHS->getInstallName(), getSingleIF(DocRHS.get(), rhs))));
411     }
412     if (!Docs.Values.empty())
413       Output.push_back(std::move(Docs));
414   }
415   return Output;
416 }
417 
418 template <typename T>
419 void printSingleVal(std::string Indent, const DiffOutput &Attr,
420                     raw_ostream &OS) {
421   if (Attr.Values.empty())
422     return;
423   OS << Indent << Attr.Name << "\n";
424   for (auto &RawItem : Attr.Values)
425     if (T *Item = dyn_cast<T>(RawItem.get()))
426       Item->print(OS, Indent);
427 }
428 
429 template <typename T>
430 void printVecVal(std::string Indent, const DiffOutput &Attr, raw_ostream &OS) {
431   if (Attr.Values.empty())
432     return;
433   OS << Indent << Attr.Name << "\n";
434   for (auto &Item : Attr.Values)
435     if (T *Vec = dyn_cast<T>(Item.get())) {
436       OS << Indent << "\t" << getTargetTripleName(Vec->Targ) << "\n";
437       for (auto &Item : Vec->TargValues)
438         Item.print(OS, Indent);
439     }
440 }
441 
442 template <>
443 void printVecVal<DiffSymVec>(std::string Indent, const DiffOutput &Attr,
444                              raw_ostream &OS) {
445   if (Attr.Values.empty())
446     return;
447   OS << Indent << Attr.Name << "\n";
448   for (auto &RawSymVec : Attr.Values)
449     if (DiffSymVec *SymVec = dyn_cast<DiffSymVec>(RawSymVec.get())) {
450       OS << Indent << "\t" << getTargetTripleName(SymVec->Targ) << "\n";
451       for (auto &Item : SymVec->TargValues)
452         Item.print(OS, Indent, SymVec->Targ);
453     }
454 }
455 
456 void DiffEngine::printDifferences(raw_ostream &OS,
457                                   const std::vector<DiffOutput> &Diffs,
458                                   int IndentCounter) {
459   std::string Indent = std::string(IndentCounter, '\t');
460   for (auto &Attr : Diffs) {
461     switch (Attr.Kind) {
462     case AD_Diff_Scalar_Str:
463       if (IndentCounter == 0)
464         printSingleVal<DiffScalarVal<StringRef, AD_Diff_Scalar_Str>>(Indent,
465                                                                      Attr, OS);
466       break;
467     case AD_Diff_Scalar_PackedVersion:
468       printSingleVal<
469           DiffScalarVal<PackedVersion, AD_Diff_Scalar_PackedVersion>>(Indent,
470                                                                       Attr, OS);
471       break;
472     case AD_Diff_Scalar_Unsigned:
473       printSingleVal<DiffScalarVal<uint8_t, AD_Diff_Scalar_Unsigned>>(Indent,
474                                                                       Attr, OS);
475       break;
476     case AD_Diff_Scalar_Bool:
477       printSingleVal<DiffScalarVal<bool, AD_Diff_Scalar_Bool>>(Indent, Attr,
478                                                                OS);
479       break;
480     case AD_Str_Vec:
481       printVecVal<DiffStrVec>(Indent, Attr, OS);
482       break;
483     case AD_Sym_Vec:
484       printVecVal<DiffSymVec>(Indent, Attr, OS);
485       break;
486     case AD_Inline_Doc:
487       if (!Attr.Values.empty()) {
488         OS << Indent << Attr.Name << "\n";
489         for (auto &Item : Attr.Values)
490           if (InlineDoc *Doc = dyn_cast<InlineDoc>(Item.get()))
491             if (!Doc->DocValues.empty()) {
492               OS << Indent << "\t" << Doc->InstallName << "\n";
493               printDifferences(OS, std::move(Doc->DocValues), 2);
494             }
495       }
496       break;
497     }
498   }
499 }
500 
501 bool DiffEngine::compareFiles(raw_ostream &OS) {
502   const auto *IFLHS = &(FileLHS->getInterfaceFile());
503   const auto *IFRHS = &(FileRHS->getInterfaceFile());
504   if (*IFLHS == *IFRHS)
505     return false;
506   OS << "< " << std::string(IFLHS->getPath().data()) << "\n> "
507      << std::string(IFRHS->getPath().data()) << "\n\n";
508   std::vector<DiffOutput> Diffs = findDifferences(IFLHS, IFRHS);
509   printDifferences(OS, Diffs, 0);
510   return true;
511 }
512