1###########################################################################
2# A module to filter symbols
3#
4# Copyright (C) 2015-2018 Andrey Ponomarenko's ABI Laboratory
5#
6# Written by Andrey Ponomarenko
7#
8# This library is free software; you can redistribute it and/or
9# modify it under the terms of the GNU Lesser General Public
10# License as published by the Free Software Foundation; either
11# version 2.1 of the License, or (at your option) any later version.
12#
13# This library is distributed in the hope that it will be useful,
14# but WITHOUT ANY WARRANTY; without even the implied warranty of
15# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16# Lesser General Public License for more details.
17#
18# You should have received a copy of the GNU Lesser General Public
19# License along with this library; if not, write to the Free Software
20# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
21# MA  02110-1301 USA
22###########################################################################
23use strict;
24
25my %Cache;
26
27sub symbolFilter($$$$)
28{ # some special cases when the symbol cannot be imported
29    my ($Symbol, $SInfo, $Type, $Level, $LVer) = @_;
30
31    if($SInfo->{"Private"})
32    { # skip private methods
33        return 0;
34    }
35
36    if(isPrivateData($Symbol))
37    { # non-public global data
38        return 0;
39    }
40
41    if(defined $In::Opt{"SkipInternalSymbols"}
42    and my $Pattern = $In::Opt{"SkipInternalSymbols"})
43    {
44        if($Symbol=~/($Pattern)/) {
45            return 0;
46        }
47    }
48
49    if($Symbol=~/\A_Z/)
50    {
51        if($Symbol=~/[CD][3-4]E/) {
52            return 0;
53        }
54    }
55
56    if($Type=~/Affected/)
57    {
58        my $Header = $SInfo->{"Header"};
59
60        if($In::Desc{$LVer}{"SkipSymbols"}{$Symbol})
61        { # user defined symbols to ignore
62            return 0;
63        }
64
65        if($In::Opt{"SymbolsListPath"} and not $In::Desc{$LVer}{"SymbolsList"}{$Symbol})
66        { # user defined symbols
67            if(not $In::Opt{"TargetHeadersPath"} or not $Header
68            or not isTargetHeader($Header, $LVer))
69            { # -symbols-list | -headers-list
70                return 0;
71            }
72        }
73
74        if($In::Opt{"AppPath"} and not $In::Opt{"SymbolsList_App"}{$Symbol})
75        { # user defined symbols (in application)
76            return 0;
77        }
78
79        my $ClassId = $SInfo->{"Class"};
80
81        if($ClassId)
82        {
83            if(not isTargetType($ClassId, $LVer)) {
84                return 0;
85            }
86        }
87
88        my $NameSpace = $SInfo->{"NameSpace"};
89        if(not $NameSpace and $ClassId)
90        { # class methods have no "NameSpace" attribute
91            $NameSpace = $In::ABI{$LVer}{"TypeInfo"}{$ClassId}{"NameSpace"};
92        }
93        if($NameSpace)
94        { # user defined namespaces to ignore
95            if($In::Desc{$LVer}{"SkipNameSpaces"}{$NameSpace}) {
96                return 0;
97            }
98            foreach my $NS (keys(%{$In::Desc{$LVer}{"SkipNameSpaces"}}))
99            { # nested namespaces
100                if($NameSpace=~/\A\Q$NS\E(\:\:|\Z)/) {
101                    return 0;
102                }
103            }
104        }
105        if($Header)
106        {
107            if(my $Skip = skipHeader($Header, $LVer))
108            { # --skip-headers or <skip_headers> (not <skip_including>)
109                if($Skip==1) {
110                    return 0;
111                }
112            }
113        }
114        if($In::Opt{"TypesListPath"} and $ClassId)
115        { # user defined types
116            my $CName = $In::ABI{$LVer}{"TypeInfo"}{$ClassId}{"Name"};
117
118            if(not $In::Desc{$LVer}{"TypesList"}{$CName})
119            {
120                if(my $NS = $In::ABI{$LVer}{"TypeInfo"}{$ClassId}{"NameSpace"})
121                {
122                    $CName=~s/\A\Q$NS\E\:\://g;
123                }
124
125                if(not $In::Desc{$LVer}{"TypesList"}{$CName})
126                {
127                    my $Found = 0;
128
129                    while($CName=~s/\:\:.+?\Z//)
130                    {
131                        if($In::Desc{$LVer}{"TypesList"}{$CName})
132                        {
133                            $Found = 1;
134                            last;
135                        }
136                    }
137
138                    if(not $Found) {
139                        return 0;
140                    }
141                }
142            }
143        }
144
145        if(not selectSymbol($Symbol, $SInfo, $Level, $LVer))
146        { # non-target symbols
147            return 0;
148        }
149
150        if($Level eq "Binary")
151        {
152            if($SInfo->{"InLine"}
153            or (not $SInfo->{"Static"} and isInLineInst($SInfo, $LVer)))
154            { # example: _ZN6Givaro6ZpzDomINS_7IntegerEE3EndEv is not exported (inlined)
155                if($ClassId and $SInfo->{"Virt"})
156                { # inline virtual methods
157                    if($Type=~/InlineVirt/) {
158                        return 1;
159                    }
160                    my $Allocable = (not isCopyingClass($ClassId, $LVer));
161                    if(not $Allocable)
162                    { # check bases
163                        foreach my $DCId (getSubClasses($ClassId, $LVer, 1))
164                        {
165                            if(not isCopyingClass($DCId, $LVer))
166                            { # exists a derived class without default c-tor
167                                $Allocable=1;
168                                last;
169                            }
170                        }
171                    }
172                    if(not $Allocable) {
173                        return 0;
174                    }
175                }
176                else
177                { # inline non-virtual methods
178                    return 0;
179                }
180            }
181        }
182    }
183    return 1;
184}
185
186sub selectSymbol($$$$)
187{ # select symbol to check or to dump
188    my ($Symbol, $SInfo, $Level, $LVer) = @_;
189
190    if($SInfo->{"Constructor"}==1)
191    {
192        if(index($Symbol, "C4E")!=-1) {
193            return 0;
194        }
195    }
196    elsif($SInfo->{"Destructor"}==1)
197    {
198        if(index($Symbol, "D4E")!=-1) {
199            return 0;
200        }
201    }
202
203    if($Level eq "Dump")
204    {
205        if($SInfo->{"Virt"} or $SInfo->{"PureVirt"})
206        { # TODO: check if this symbol is from
207          # base classes of other target symbols
208            return 1;
209        }
210    }
211
212    if(not $In::Opt{"StdcxxTesting"} and not $In::Opt{"KeepCxx"}
213    and $Symbol=~/\A(_ZS|_ZNS|_ZNKS)/)
214    { # stdc++ interfaces
215        return 0;
216    }
217
218    my $Target = 0;
219    if(my $Header = $SInfo->{"Header"}) {
220        $Target = isTargetHeader($Header, $LVer);
221    }
222
223    if(not $Target)
224    {
225        if(my $Source = $SInfo->{"Source"}) {
226            $Target = isTargetSource($Source, $LVer);
227        }
228    }
229
230    if($In::Opt{"ExtendedCheck"})
231    {
232        if(index($Symbol, "external_func_")==0) {
233            $Target = 1;
234        }
235    }
236    if($In::Opt{"CheckHeadersOnly"}
237    or $Level eq "Source")
238    {
239        if($Target)
240        {
241            if($Level eq "Dump")
242            { # dumped
243                if($In::Opt{"BinOnly"})
244                {
245                    if(not $SInfo->{"InLine"} or $SInfo->{"Data"}) {
246                        return 1;
247                    }
248                }
249                else {
250                    return 1;
251                }
252            }
253            elsif($Level eq "Source")
254            { # checked
255                return 1;
256            }
257            elsif($Level eq "Binary")
258            { # checked
259                if(not $SInfo->{"InLine"} or $SInfo->{"Data"}
260                or $SInfo->{"Virt"} or $SInfo->{"PureVirt"}) {
261                    return 1;
262                }
263            }
264        }
265    }
266    else
267    { # library is available
268        if(linkSymbol($Symbol, $LVer, "-Deps"))
269        { # exported symbols
270            return 1;
271        }
272        if($Level eq "Dump")
273        { # dumped
274            if($In::Opt{"BinOnly"})
275            {
276                if($SInfo->{"Data"})
277                {
278                    if($Target) {
279                        return 1;
280                    }
281                }
282            }
283            else
284            { # SrcBin
285                if($Target) {
286                    return 1;
287                }
288            }
289        }
290        elsif($Level eq "Source")
291        { # checked
292            if($SInfo->{"PureVirt"} or $SInfo->{"Data"} or $SInfo->{"InLine"}
293            or isInLineInst($SInfo, $LVer))
294            { # skip LOCAL symbols
295                if($Target) {
296                    return 1;
297                }
298            }
299        }
300        elsif($Level eq "Binary")
301        { # checked
302            if($SInfo->{"PureVirt"} or $SInfo->{"Data"})
303            {
304                if($Target) {
305                    return 1;
306                }
307            }
308        }
309    }
310    return 0;
311}
312
313sub linkSymbol($$$)
314{
315    my ($Symbol, $RunWith, $Deps) = @_;
316    if(linkSymbol_I($Symbol, $RunWith, "SymLib")) {
317        return 1;
318    }
319    if($Deps eq "+Deps")
320    { # check the dependencies
321        if(linkSymbol_I($Symbol, $RunWith, "DepSymLib")) {
322            return 1;
323        }
324    }
325    return 0;
326}
327
328sub linkSymbol_I($$$)
329{
330    my ($Symbol, $RunWith, $Where) = @_;
331    if(not $Where or not $Symbol) {
332        return 0;
333    }
334
335    my $SRef = $In::ABI{$RunWith}{$Where};
336
337    if($SRef->{$Symbol})
338    { # the exact match by symbol name
339        return 1;
340    }
341    if(my $VSym = $In::ABI{$RunWith}{"SymbolVersion"}{$Symbol})
342    { # indirect symbol version, i.e.
343      # foo_old and its symlink foo@v (or foo@@v)
344      # foo_old may be in symtab table
345        if($SRef->{$VSym}) {
346            return 1;
347        }
348    }
349
350    if($Symbol=~/[\@\$]/)
351    {
352        my ($Sym, $Spec, $Ver) = symbolParts($Symbol);
353        if($Sym and $Ver)
354        { # search for the symbol with the same version
355          # or without version
356            if($SRef->{$Sym})
357            { # old: foo@v|foo@@v
358              # new: foo
359                return 1;
360            }
361            if($SRef->{$Sym."\@".$Ver})
362            { # old: foo|foo@@v
363              # new: foo@v
364                return 1;
365            }
366            if($SRef->{$Sym."\@\@".$Ver})
367            { # old: foo|foo@v
368              # new: foo@@v
369                return 1;
370            }
371        }
372    }
373
374    return 0;
375}
376
377sub isPrivateData($)
378{ # non-public global data
379    my $Symbol = $_[0];
380    return ($Symbol=~/\A(_ZGV|_ZTI|_ZTS|_ZTT|_ZTV|_ZTC|_ZThn|_ZTv0_n)/);
381}
382
383sub isInLineInst($$) {
384    return (isTemplateInstance(@_) and not isTemplateSpec(@_));
385}
386
387sub isTemplateInstance($$)
388{
389    my ($SInfo, $LVer) = @_;
390
391    if(my $ClassId = $SInfo->{"Class"})
392    {
393        if(my $ClassName = $In::ABI{$LVer}{"TypeInfo"}{$ClassId}{"Name"})
394        {
395            if(index($ClassName,"<")!=-1) {
396                return 1;
397            }
398        }
399    }
400    if(my $ShortName = $SInfo->{"ShortName"})
401    {
402        if(index($ShortName,"<")!=-1
403        and index($ShortName,">")!=-1) {
404            return 1;
405        }
406    }
407
408    return 0;
409}
410
411sub isTemplateSpec($$)
412{
413    my ($SInfo, $LVer) = @_;
414    if(my $ClassId = $SInfo->{"Class"})
415    {
416        if($In::ABI{$LVer}{"TypeInfo"}{$ClassId}{"Spec"})
417        { # class specialization
418            return 1;
419        }
420        elsif($SInfo->{"Spec"})
421        { # method specialization
422            return 1;
423        }
424    }
425    return 0;
426}
427
428sub skipHeader($$)
429{
430    my ($Path, $LVer) = @_;
431
432    if(defined $Cache{"skipHeader"}{$LVer}{$Path}) {
433        return $Cache{"skipHeader"}{$LVer}{$Path};
434    }
435
436    if(defined $In::Opt{"Tolerance"}
437    and $In::Opt{"Tolerance"}=~/1|2/)
438    { # --tolerant
439        if(skipAlienHeader($Path)) {
440            return ($Cache{"skipHeader"}{$LVer}{$Path} = 1);
441        }
442    }
443    if(not keys(%{$In::Desc{$LVer}{"SkipHeaders"}})) {
444        return 0;
445    }
446    return ($Cache{"skipHeader"}{$LVer}{$Path} = skipHeader_I(@_));
447}
448
449sub skipHeader_I($$)
450{ # returns:
451  #  1 - if header should NOT be included and checked
452  #  2 - if header should NOT be included, but should be checked
453    my ($Path, $LVer) = @_;
454    my $Name = getFilename($Path);
455    if(my $Kind = $In::Desc{$LVer}{"SkipHeaders"}{"Name"}{$Name}) {
456        return $Kind;
457    }
458    foreach my $D (sort {$In::Desc{$LVer}{"SkipHeaders"}{"Path"}{$a} cmp $In::Desc{$LVer}{"SkipHeaders"}{"Path"}{$b}}
459    keys(%{$In::Desc{$LVer}{"SkipHeaders"}{"Path"}}))
460    {
461        if(index($Path, $D)!=-1)
462        {
463            if($Path=~/\Q$D\E([\/\\]|\Z)/) {
464                return $In::Desc{$LVer}{"SkipHeaders"}{"Path"}{$D};
465            }
466        }
467    }
468    foreach my $P (sort {$In::Desc{$LVer}{"SkipHeaders"}{"Pattern"}{$a} cmp $In::Desc{$LVer}{"SkipHeaders"}{"Pattern"}{$b}}
469    keys(%{$In::Desc{$LVer}{"SkipHeaders"}{"Pattern"}}))
470    {
471        if(my $Kind = $In::Desc{$LVer}{"SkipHeaders"}{"Pattern"}{$P})
472        {
473            if($Name=~/$P/) {
474                return $Kind;
475            }
476            if($P=~/[\/\\]/ and $Path=~/$P/) {
477                return $Kind;
478            }
479        }
480    }
481
482    return 0;
483}
484
485sub skipLib($$)
486{
487    my ($Path, $LVer) = @_;
488
489    my $Name = getFilename($Path);
490    if($In::Desc{$LVer}{"SkipLibs"}{"Name"}{$Name}) {
491        return 1;
492    }
493    my $ShortName = libPart($Name, "name+ext");
494    if($In::Desc{$LVer}{"SkipLibs"}{"Name"}{$ShortName}) {
495        return 1;
496    }
497    foreach my $Dir (keys(%{$In::Desc{$LVer}{"SkipLibs"}{"Path"}}))
498    {
499        if($Path=~/\Q$Dir\E([\/\\]|\Z)/) {
500            return 1;
501        }
502    }
503    foreach my $P (keys(%{$In::Desc{$LVer}{"SkipLibs"}{"Pattern"}}))
504    {
505        if($Name=~/$P/) {
506            return 1;
507        }
508        if($P=~/[\/\\]/ and $Path=~/$P/) {
509            return 1;
510        }
511    }
512    return 0;
513}
514
515sub addTargetLibs($)
516{
517    my $LibsRef = $_[0];
518    foreach (@{$LibsRef}) {
519        $In::Opt{"TargetLibs"}{$_} = 1;
520    }
521}
522
523sub isTargetLib($)
524{
525    my $LName = $_[0];
526
527    if($In::Opt{"OS"} eq "windows") {
528        $LName = lc($LName);
529    }
530    if(my $TN = $In::Opt{"TargetLib"})
531    {
532        if($LName!~/\Q$TN\E/) {
533            return 0;
534        }
535    }
536    if($In::Opt{"TargetLibs"}
537    and not $In::Opt{"TargetLibs"}{$LName}
538    and not $In::Opt{"TargetLibs"}{libPart($LName, "name+ext")}) {
539        return 0;
540    }
541    return 1;
542}
543
544sub pickType($$)
545{
546    my ($Tid, $LVer) = @_;
547
548    if(my $Dupl = $In::ABI{$LVer}{"TypeTypedef"}{$Tid})
549    {
550        if(defined $In::ABI{$LVer}{"TypeInfo"}{$Dupl})
551        {
552            if($In::ABI{$LVer}{"TypeInfo"}{$Dupl}{"Name"} eq $In::ABI{$LVer}{"TypeInfo"}{$Tid}{"Name"})
553            { # duplicate
554                return 0;
555            }
556        }
557    }
558
559    my $THeader = $In::ABI{$LVer}{"TypeInfo"}{$Tid}{"Header"};
560
561    if(isBuiltIn($THeader)) {
562        return 0;
563    }
564
565    if($In::ABI{$LVer}{"TypeInfo"}{$Tid}{"Type"}!~/Class|Struct|Union|Enum|Typedef/) {
566        return 0;
567    }
568
569    if(isAnon($In::ABI{$LVer}{"TypeInfo"}{$Tid}{"Name"})) {
570        return 0;
571    }
572
573    if(selfTypedef($Tid, $LVer)) {
574        return 0;
575    }
576
577    if(not isTargetType($Tid, $LVer)) {
578        return 0;
579    }
580
581    return 1;
582}
583
584sub isTargetType($$)
585{
586    my ($Tid, $LVer) = @_;
587
588    if(my $THeader = $In::ABI{$LVer}{"TypeInfo"}{$Tid}{"Header"})
589    { # NOTE: header is defined to source if undefined (DWARF dumps)
590        if(not isTargetHeader($THeader, $LVer))
591        { # from target headers
592            return 0;
593        }
594    }
595    elsif(my $TSource = $In::ABI{$LVer}{"TypeInfo"}{$Tid}{"Source"})
596    {
597        if(not isTargetSource($TSource, $LVer))
598        { # from target sources
599            return 0;
600        }
601    }
602    else
603    {
604        return 0;
605    }
606
607    if(my $Name = $In::ABI{$LVer}{"TypeInfo"}{$Tid}{"Name"})
608    {
609        if(my $Pattern = $In::Opt{"SkipInternalTypes"})
610        {
611            if($Name=~/($Pattern)/) {
612                return 0;
613            }
614        }
615
616        if($In::Desc{$LVer}{"SkipTypes"}{$Name}) {
617            return 0;
618        }
619    }
620
621    if($In::ABI{$LVer}{"PublicABI"})
622    {
623        if(isPrivateABI($Tid, $LVer)) {
624            return 0;
625        }
626    }
627
628    return 1;
629}
630
631sub selfTypedef($$)
632{
633    my ($TypeId, $LVer) = @_;
634    my %Type = getType($TypeId, $LVer);
635    if($Type{"Type"} eq "Typedef")
636    {
637        my %Base = getOneStepBaseType($TypeId, $LVer);
638        if($Base{"Type"}=~/Class|Struct/)
639        {
640            if($Type{"Name"} eq $Base{"Name"}) {
641                return 1;
642            }
643            elsif($Type{"Name"}=~/::(\w+)\Z/)
644            {
645                if($Type{"Name"} eq $Base{"Name"}."::".$1)
646                { # QPointer<QWidget>::QPointer
647                    return 1;
648                }
649            }
650        }
651    }
652    return 0;
653}
654
655sub isOpaque($)
656{
657    my $T = $_[0];
658    if(not defined $T->{"Memb"}
659    and not defined $T->{"Size"})
660    {
661        return 1;
662    }
663    return 0;
664}
665
666sub isPrivateABI($$)
667{
668    my ($TypeId, $LVer) = @_;
669
670    if($In::Opt{"CheckPrivateABI"}) {
671        return 0;
672    }
673
674    if(defined $In::ABI{$LVer}{"TypeInfo"}{$TypeId}{"PrivateABI"}) {
675        return 1;
676    }
677
678    return 0;
679}
680
681sub isReserved($)
682{ # reserved fields == private
683    my $MName = $_[0];
684
685    if($In::Opt{"KeepReserved"}) {
686        return 0;
687    }
688
689    if($MName=~/reserved|padding|f_spare/i) {
690        return 1;
691    }
692    if($MName=~/\A[_]*(spare|pad|unused|dummy)[_\d]*\Z/i) {
693        return 1;
694    }
695    if($MName=~/(pad\d+)/i) {
696        return 1;
697    }
698    return 0;
699}
700
701sub specificHeader($$)
702{
703    my ($Header, $Spec) = @_;
704    my $Name = getFilename($Header);
705
706    if($Spec eq "windows")
707    {# MS Windows
708        return 1 if($Name=~/(\A|[._-])(win|wince|wnt)(\d\d|[._-]|\Z)/i);
709        return 1 if($Name=~/([._-]w|win)(32|64)/i);
710        return 1 if($Name=~/\A(Win|Windows)[A-Z]/);
711        return 1 if($Name=~/\A(w|win|windows)(32|64|\.)/i);
712        my @Dirs = (
713            "win32",
714            "win64",
715            "win",
716            "windows",
717            "msvcrt"
718        ); # /gsf-win32/
719        if(my $DIRs = join("|", @Dirs)) {
720            return 1 if($Header=~/[\/\\](|[^\/\\]+[._-])($DIRs)(|[._-][^\/\\]+)([\/\\]|\Z)/i);
721        }
722    }
723    elsif($Spec eq "macos")
724    { # Mac OS
725        return 1 if($Name=~/(\A|[_-])mac[._-]/i);
726    }
727
728    return 0;
729}
730
731sub skipAlienHeader($)
732{
733    my $Path = $_[0];
734    my $Name = getFilename($Path);
735    my $Dir = getDirname($Path);
736
737    if($In::Opt{"Tolerance"}=~/2/)
738    { # 2 - skip internal headers
739        my @Terms = (
740            "p",
741            "priv",
742            "int",
743            "impl",
744            "implementation",
745            "internal",
746            "private",
747            "old",
748            "compat",
749            "debug",
750            "test",
751            "gen"
752        );
753
754        my @Dirs = (
755            "private",
756            "priv",
757            "port",
758            "impl",
759            "internal",
760            "detail",
761            "details",
762            "old",
763            "compat",
764            "debug",
765            "config",
766            "compiler",
767            "platform",
768            "test"
769        );
770
771        if(my $TERMs = join("|", @Terms)) {
772            return 1 if($Name=~/(\A|[._-])($TERMs)([._-]|\Z)/i);
773        }
774        if(my $DIRs = join("|", @Dirs)) {
775            return 1 if($Dir=~/(\A|[\/\\])(|[^\/\\]+[._-])($DIRs)(|[._-][^\/\\]+)([\/\\]|\Z)/i);
776        }
777
778        return 1 if($Name=~/[a-z](Imp|Impl|I|P)(\.|\Z)/);
779    }
780
781    if($In::Opt{"Tolerance"}=~/1/)
782    { # 1 - skip non-Linux headers
783        if($In::Opt{"OS"} ne "windows")
784        {
785            if(specificHeader($Path, "windows")) {
786                return 1;
787            }
788        }
789        if($In::Opt{"OS"} ne "macos")
790        {
791            if(specificHeader($Path, "macos")) {
792                return 1;
793            }
794        }
795    }
796
797    # valid
798    return 0;
799}
800
801sub isTargetHeader($$)
802{ # --header, --headers-list
803    my ($H, $V) = @_;
804
805    if(defined $In::Desc{$V}{"TargetHeader"})
806    {
807        if(defined $In::Desc{$V}{"TargetHeader"}{$H}) {
808            return 1;
809        }
810    }
811    elsif($In::ABI{$V}{"Headers"})
812    {
813        if(defined $In::ABI{$V}{"Headers"}{$H}) {
814            return 1;
815        }
816    }
817
818    return 0;
819}
820
821sub isTargetSource($$)
822{
823    my ($S, $V) = @_;
824
825    if($In::ABI{$V}{"Sources"})
826    {
827        if(defined $In::ABI{$V}{"Sources"}{$S}) {
828            return 1;
829        }
830    }
831
832    return 0;
833}
834
835sub ignorePath($)
836{
837    my $Path = $_[0];
838    if($Path=~/\~\Z/)
839    {# skipping system backup files
840        return 1;
841    }
842    if($Path=~/(\A|[\/\\]+)(\.(svn|git|bzr|hg)|CVS)([\/\\]+|\Z)/)
843    {# skipping hidden .svn, .git, .bzr, .hg and CVS directories
844        return 1;
845    }
846    return 0;
847}
848
849return 1;
850