Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
100.00% covered (success)
100.00%
269 / 269
100.00% covered (success)
100.00%
23 / 23
CRAP
100.00% covered (success)
100.00%
1 / 1
MethodLinks
100.00% covered (success)
100.00%
269 / 269
100.00% covered (success)
100.00%
23 / 23
140
100.00% covered (success)
100.00%
1 / 1
 __construct
100.00% covered (success)
100.00%
1 / 1
100.00% covered (success)
100.00%
1 / 1
1
 emptySingleton
100.00% covered (success)
100.00%
4 / 4
100.00% covered (success)
100.00%
1 / 1
2
 getForDim
100.00% covered (success)
100.00%
24 / 24
100.00% covered (success)
100.00%
1 / 1
11
 asValueFirstLevel
100.00% covered (success)
100.00%
8 / 8
100.00% covered (success)
100.00%
1 / 1
4
 asKeyForForeach
100.00% covered (success)
100.00%
13 / 13
100.00% covered (success)
100.00%
1 / 1
6
 withLinksAtDim
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
3
 withKeysLinks
100.00% covered (success)
100.00%
7 / 7
100.00% covered (success)
100.00%
1 / 1
3
 asCollapsed
100.00% covered (success)
100.00%
8 / 8
100.00% covered (success)
100.00%
1 / 1
4
 asMergedWith
100.00% covered (success)
100.00%
20 / 20
100.00% covered (success)
100.00%
1 / 1
11
 withoutShape
100.00% covered (success)
100.00%
10 / 10
100.00% covered (success)
100.00%
1 / 1
7
 withAddedOffset
100.00% covered (success)
100.00%
5 / 5
100.00% covered (success)
100.00%
1 / 1
2
 asMaybeMovedAtOffset
100.00% covered (success)
100.00%
6 / 6
100.00% covered (success)
100.00%
1 / 1
3
 asMovedToKeys
100.00% covered (success)
100.00%
3 / 3
100.00% covered (success)
100.00%
1 / 1
1
 asMergedForAssignment
100.00% covered (success)
100.00%
18 / 18
100.00% covered (success)
100.00%
1 / 1
8
 normalize
100.00% covered (success)
100.00%
36 / 36
100.00% covered (success)
100.00%
1 / 1
14
 getLinksCollapsing
100.00% covered (success)
100.00%
8 / 8
100.00% covered (success)
100.00%
1 / 1
4
 getMethodAndParamTuples
100.00% covered (success)
100.00%
14 / 14
100.00% covered (success)
100.00%
1 / 1
7
 isEmpty
100.00% covered (success)
100.00%
10 / 10
100.00% covered (success)
100.00%
1 / 1
8
 hasDataForFuncAndParam
100.00% covered (success)
100.00%
10 / 10
100.00% covered (success)
100.00%
1 / 1
10
 withFuncAndParam
100.00% covered (success)
100.00%
10 / 10
100.00% covered (success)
100.00%
1 / 1
3
 asPreservedTaintednessForFuncParam
100.00% covered (success)
100.00%
19 / 19
100.00% covered (success)
100.00%
1 / 1
9
 asTaintednessForBackprop
100.00% covered (success)
100.00%
11 / 11
100.00% covered (success)
100.00%
1 / 1
4
 asFilteredForFuncAndParam
100.00% covered (success)
100.00%
17 / 17
100.00% covered (success)
100.00%
1 / 1
7
 toString
n/a
0 / 0
n/a
0 / 0
7
 __toString
n/a
0 / 0
n/a
0 / 0
1
1<?php declare( strict_types=1 );
2
3namespace SecurityCheckPlugin;
4
5use ast\Node;
6use Phan\Language\Element\FunctionInterface;
7
8/**
9 * Value object that represents method links.
10 * @todo We might store links inside Taintedness, but the memory usage might skyrocket
11 */
12class MethodLinks {
13    /** @var LinksSet */
14    private $links;
15
16    /** @var self[] */
17    private $dimLinks = [];
18
19    /** @var self|null */
20    private $unknownDimLinks;
21
22    /** @var LinksSet|null */
23    private $keysLinks;
24
25    /**
26     * @param LinksSet|null $links
27     */
28    public function __construct( ?LinksSet $links = null ) {
29        $this->links = $links ?? new LinksSet();
30    }
31
32    /**
33     * @return self
34     */
35    public static function emptySingleton(): self {
36        static $singleton;
37        if ( !$singleton ) {
38            $singleton = new self( new LinksSet );
39        }
40        return $singleton;
41    }
42
43    /**
44     * @note This returns a clone
45     * @param mixed $dim
46     * @param bool $pushOffsets
47     * @return self
48     */
49    public function getForDim( $dim, bool $pushOffsets = true ): self {
50        if ( $this === self::emptySingleton() ) {
51            return $this;
52        }
53        if ( !is_scalar( $dim ) ) {
54            $ret = ( new self( $this->links ) );
55            if ( $pushOffsets ) {
56                $ret = $ret->withAddedOffset( $dim );
57            }
58            if ( $this->unknownDimLinks ) {
59                $ret = $ret->asMergedWith( $this->unknownDimLinks );
60            }
61            foreach ( $this->dimLinks as $links ) {
62                $ret = $ret->asMergedWith( $links );
63            }
64            return $ret;
65        }
66        if ( isset( $this->dimLinks[$dim] ) ) {
67            $ret = ( new self( $this->links ) );
68            if ( $pushOffsets ) {
69                $ret = $ret->withAddedOffset( $dim );
70            }
71            if ( $this->unknownDimLinks ) {
72                $offsetLinks = $this->dimLinks[$dim]->asMergedWith( $this->unknownDimLinks );
73            } else {
74                $offsetLinks = $this->dimLinks[$dim];
75            }
76            return $ret->asMergedWith( $offsetLinks );
77        }
78        if ( $this->unknownDimLinks ) {
79            $ret = clone $this->unknownDimLinks;
80            $ret->links = $ret->links->asMergedWith( $this->links );
81        } else {
82            $ret = new self( $this->links );
83        }
84
85        return $pushOffsets ? $ret->withAddedOffset( $dim ) : $ret;
86    }
87
88    /**
89     * @return self
90     */
91    public function asValueFirstLevel(): self {
92        if ( $this === self::emptySingleton() ) {
93            return $this;
94        }
95        $ret = ( new self( $this->links ) )->withAddedOffset( null );
96        if ( $this->unknownDimLinks ) {
97            $ret = $ret->asMergedWith( $this->unknownDimLinks );
98        }
99        foreach ( $this->dimLinks as $links ) {
100            $ret = $ret->asMergedWith( $links );
101        }
102        return $ret;
103    }
104
105    /**
106     * @return self
107     */
108    public function asKeyForForeach(): self {
109        $emptySingleton = self::emptySingleton();
110        if ( $this === $emptySingleton ) {
111            return $this;
112        }
113
114        $hasBaseLinks = count( $this->links ) !== 0;
115        $hasKeyLinks = $this->keysLinks && count( $this->keysLinks ) !== 0;
116
117        if ( $hasBaseLinks ) {
118            $newLinks = $this->links->asAllMovedToKeys();
119            if ( $hasKeyLinks ) {
120                $newLinks = $newLinks->asMergedWith( $this->keysLinks );
121            }
122        } elseif ( $hasKeyLinks ) {
123            $newLinks = $this->keysLinks;
124        } else {
125            return $emptySingleton;
126        }
127
128        return new self( $newLinks );
129    }
130
131    /**
132     * @param mixed $dim
133     * @param MethodLinks $links
134     * @return self
135     */
136    public function withLinksAtDim( $dim, self $links ): self {
137        $ret = clone $this;
138        if ( is_scalar( $dim ) ) {
139            $ret->dimLinks[$dim] = $links;
140        } elseif ( $ret->unknownDimLinks ) {
141            $ret->unknownDimLinks = $ret->unknownDimLinks->asMergedWith( $links );
142        } else {
143            $ret->unknownDimLinks = $links;
144        }
145        return $ret;
146    }
147
148    public function withKeysLinks( LinksSet $links ): self {
149        if ( !count( $links ) ) {
150            return $this;
151        }
152        $ret = clone $this;
153        if ( !$ret->keysLinks ) {
154            $ret->keysLinks = $links;
155        } else {
156            $ret->keysLinks = $ret->keysLinks->asMergedWith( $links );
157        }
158        return $ret;
159    }
160
161    /**
162     * @return self
163     */
164    public function asCollapsed(): self {
165        if ( $this === self::emptySingleton() ) {
166            return $this;
167        }
168        $ret = new self( $this->links );
169        foreach ( $this->dimLinks as $links ) {
170            $ret = $ret->asMergedWith( $links->asCollapsed() );
171        }
172        if ( $this->unknownDimLinks ) {
173            $ret = $ret->asMergedWith( $this->unknownDimLinks->asCollapsed() );
174        }
175        return $ret;
176    }
177
178    /**
179     * Merge this object with $other, recursively, creating a copy.
180     *
181     * @param self $other
182     * @return self
183     */
184    public function asMergedWith( self $other ): self {
185        $emptySingleton = self::emptySingleton();
186        if ( $other === $emptySingleton ) {
187            return $this;
188        }
189        if ( $this === $emptySingleton ) {
190            return $other;
191        }
192        $ret = clone $this;
193
194        $ret->links = $ret->links->asMergedWith( $other->links );
195        foreach ( $other->dimLinks as $key => $links ) {
196            if ( isset( $ret->dimLinks[$key] ) ) {
197                $ret->dimLinks[$key] = $ret->dimLinks[$key]->asMergedWith( $links );
198            } else {
199                $ret->dimLinks[$key] = $links;
200            }
201        }
202        if ( $other->unknownDimLinks && !$ret->unknownDimLinks ) {
203            $ret->unknownDimLinks = $other->unknownDimLinks;
204        } elseif ( $other->unknownDimLinks ) {
205            $ret->unknownDimLinks = $ret->unknownDimLinks->asMergedWith( $other->unknownDimLinks );
206        }
207        if ( $other->keysLinks && !$ret->keysLinks ) {
208            $ret->keysLinks = $other->keysLinks;
209        } elseif ( $other->keysLinks ) {
210            $ret->keysLinks = $ret->keysLinks->asMergedWith( $other->keysLinks );
211        }
212
213        return $ret;
214    }
215
216    public function withoutShape( self $other ): self {
217        $ret = clone $this;
218
219        $ret->links = $ret->links->withoutShape( $other->links );
220        foreach ( $other->dimLinks as $key => $val ) {
221            if ( isset( $ret->dimLinks[$key] ) ) {
222                $ret->dimLinks[$key] = $ret->dimLinks[$key]->withoutShape( $val );
223            }
224        }
225        if ( $ret->unknownDimLinks && $other->unknownDimLinks ) {
226            $ret->unknownDimLinks = $ret->unknownDimLinks->withoutShape( $other->unknownDimLinks );
227        }
228        if ( $ret->keysLinks && $other->keysLinks ) {
229            $ret->keysLinks = $ret->keysLinks->withoutShape( $other->keysLinks );
230        }
231        return $ret;
232    }
233
234    /**
235     * @param Node|mixed $offset
236     * @return self
237     */
238    public function withAddedOffset( $offset ): self {
239        $ret = clone $this;
240        $ret->links = clone $ret->links;
241        foreach ( $ret->links as $func ) {
242            $ret->links[$func] = $ret->links[$func]->withOffsetPushedToAll( $offset );
243        }
244        return $ret;
245    }
246
247    /**
248     * Create a new object with $this at the given $offset (if scalar) or as unknown object.
249     *
250     * @param Node|string|int|bool|float|null $offset
251     * @param LinksSet|null $keyLinks
252     * @return self Always a copy
253     */
254    public function asMaybeMovedAtOffset( $offset, ?LinksSet $keyLinks = null ): self {
255        $ret = new self;
256        if ( $offset instanceof Node || $offset === null ) {
257            $ret->unknownDimLinks = $this;
258        } else {
259            $ret->dimLinks[$offset] = $this;
260        }
261        $ret->keysLinks = $keyLinks;
262        return $ret;
263    }
264
265    public function asMovedToKeys(): self {
266        $ret = new self;
267        $ret->keysLinks = $this->getLinksCollapsing();
268        return $ret;
269    }
270
271    /**
272     * @param self $other
273     * @param int $depth
274     * @return self
275     */
276    public function asMergedForAssignment( self $other, int $depth ): self {
277        if ( $depth === 0 ) {
278            return $other;
279        }
280        $ret = clone $this;
281        $ret->links = $ret->links->asMergedWith( $other->links );
282        if ( !$ret->keysLinks ) {
283            $ret->keysLinks = $other->keysLinks;
284        } elseif ( $other->keysLinks ) {
285            $ret->keysLinks = $ret->keysLinks->asMergedWith( $other->keysLinks );
286        }
287        if ( !$ret->unknownDimLinks ) {
288            $ret->unknownDimLinks = $other->unknownDimLinks;
289        } elseif ( $other->unknownDimLinks ) {
290            $ret->unknownDimLinks = $ret->unknownDimLinks->asMergedWith( $other->unknownDimLinks );
291        }
292        foreach ( $other->dimLinks as $k => $v ) {
293            $ret->dimLinks[$k] = isset( $ret->dimLinks[$k] )
294                ? $ret->dimLinks[$k]->asMergedForAssignment( $v, $depth - 1 )
295                : $v;
296        }
297        $ret->normalize();
298        return $ret;
299    }
300
301    /**
302     * Remove offset links which are already present in the "main" links. This is done for performance
303     * (see test backpropoffsets-blowup).
304     *
305     * @todo Improve (e.g. recurse)
306     * @todo Might happen sometime earlier
307     */
308    private function normalize(): void {
309        if ( !count( $this->links ) ) {
310            return;
311        }
312        foreach ( $this->dimLinks as $k => $links ) {
313            $alreadyCloned = false;
314            foreach ( $links->links as $func ) {
315                if ( $this->links->contains( $func ) ) {
316                    $dimParams = array_keys( $links->links[$func]->getParams() );
317                    $thisParams = array_keys( $this->links[$func]->getParams() );
318                    $keepParams = array_diff( $dimParams, $thisParams );
319                    if ( !$alreadyCloned ) {
320                        $this->dimLinks[$k] = clone $links;
321                        $this->dimLinks[$k]->links = clone $links->links;
322                        $alreadyCloned = true;
323                    }
324                    if ( !$keepParams ) {
325                        unset( $this->dimLinks[$k]->links[$func] );
326                    } else {
327                        $this->dimLinks[$k]->links[$func] = $this->dimLinks[$k]->links[$func]
328                            ->withOnlyParams( $keepParams );
329                    }
330                }
331            }
332            if ( $this->dimLinks[$k]->isEmpty() ) {
333                unset( $this->dimLinks[$k] );
334            }
335        }
336        if ( $this->unknownDimLinks ) {
337            $alreadyCloned = false;
338            foreach ( $this->unknownDimLinks->links as $func ) {
339                if ( $this->links->contains( $func ) ) {
340                    $dimParams = array_keys( $this->unknownDimLinks->links[$func]->getParams() );
341                    $thisParams = array_keys( $this->links[$func]->getParams() );
342                    $keepParams = array_diff( $dimParams, $thisParams );
343                    if ( !$alreadyCloned ) {
344                        $this->unknownDimLinks = clone $this->unknownDimLinks;
345                        $this->unknownDimLinks->links = clone $this->unknownDimLinks->links;
346                        $alreadyCloned = true;
347                    }
348                    if ( !$keepParams ) {
349                        unset( $this->unknownDimLinks->links[$func] );
350                    } else {
351                        $this->unknownDimLinks->links[$func] = $this->unknownDimLinks->links[$func]
352                            ->withOnlyParams( $keepParams );
353                    }
354                }
355            }
356            if ( $this->unknownDimLinks->isEmpty() ) {
357                $this->unknownDimLinks = null;
358            }
359        }
360    }
361
362    /**
363     * Returns all the links stored in this object as a single LinkSet object, destroying the shape. This should only
364     * be used when the shape is not relevant.
365     *
366     * @return LinksSet
367     */
368    public function getLinksCollapsing(): LinksSet {
369        $ret = clone $this->links;
370        foreach ( $this->dimLinks as $link ) {
371            $ret->mergeWith( $link->getLinksCollapsing() );
372        }
373        if ( $this->unknownDimLinks ) {
374            $ret->mergeWith( $this->unknownDimLinks->getLinksCollapsing() );
375        }
376        if ( $this->keysLinks ) {
377            $ret->mergeWith( $this->keysLinks );
378        }
379        return $ret;
380    }
381
382    /**
383     * @return array[]
384     * @phan-return array<array{0:FunctionInterface,1:int}>
385     */
386    public function getMethodAndParamTuples(): array {
387        $ret = [];
388        foreach ( $this->links as $func ) {
389            $info = $this->links[$func];
390            foreach ( $info->getParams() as $i => $_ ) {
391                $ret[] = [ $func, $i ];
392            }
393        }
394        foreach ( $this->dimLinks as $link ) {
395            $ret = array_merge( $ret, $link->getMethodAndParamTuples() );
396        }
397        if ( $this->unknownDimLinks ) {
398            $ret = array_merge( $ret, $this->unknownDimLinks->getMethodAndParamTuples() );
399        }
400        foreach ( $this->keysLinks ?? [] as $func ) {
401            $info = $this->keysLinks[$func];
402            foreach ( $info->getParams() as $i => $_ ) {
403                $ret[] = [ $func, $i ];
404            }
405        }
406        return array_unique( $ret, SORT_REGULAR );
407    }
408
409    /**
410     * @return bool
411     */
412    public function isEmpty(): bool {
413        if ( count( $this->links ) ) {
414            return false;
415        }
416        foreach ( $this->dimLinks as $links ) {
417            if ( !$links->isEmpty() ) {
418                return false;
419            }
420        }
421        if ( $this->unknownDimLinks && !$this->unknownDimLinks->isEmpty() ) {
422            return false;
423        }
424        if ( $this->keysLinks && count( $this->keysLinks ) ) {
425            return false;
426        }
427        return true;
428    }
429
430    /**
431     * @param FunctionInterface $func
432     * @param int $i
433     * @return bool
434     */
435    public function hasDataForFuncAndParam( FunctionInterface $func, int $i ): bool {
436        if ( $this->links->contains( $func ) && $this->links[$func]->hasParam( $i ) ) {
437            return true;
438        }
439        foreach ( $this->dimLinks as $dimLinks ) {
440            if ( $dimLinks->hasDataForFuncAndParam( $func, $i ) ) {
441                return true;
442            }
443        }
444        if ( $this->unknownDimLinks && $this->unknownDimLinks->hasDataForFuncAndParam( $func, $i ) ) {
445            return true;
446        }
447        if ( $this->keysLinks && $this->keysLinks->contains( $func ) && $this->keysLinks[$func]->hasParam( $i ) ) {
448            return true;
449        }
450        return false;
451    }
452
453    public function withFuncAndParam(
454        FunctionInterface $func,
455        int $i,
456        bool $isVariadic,
457        int $initialFlags = SecurityCheckPlugin::ALL_TAINT
458    ): self {
459        $ret = clone $this;
460
461        if ( $isVariadic ) {
462            $baseUnkLinks = $ret->unknownDimLinks ?? self::emptySingleton();
463            $ret->unknownDimLinks = $baseUnkLinks->withFuncAndParam( $func, $i, false, $initialFlags );
464            return $ret;
465        }
466
467        $ret->links = clone $ret->links;
468        if ( $ret->links->contains( $func ) ) {
469            $ret->links[$func] = $ret->links[$func]->withParam( $i, $initialFlags );
470        } else {
471            $ret->links[$func] = SingleMethodLinks::instanceWithParam( $i, $initialFlags );
472        }
473        return $ret;
474    }
475
476    /**
477     * @param FunctionInterface $func
478     * @param int $param
479     * @return PreservedTaintedness
480     */
481    public function asPreservedTaintednessForFuncParam( FunctionInterface $func, int $param ): PreservedTaintedness {
482        $ret = null;
483        if ( $this->links->contains( $func ) ) {
484            $ownInfo = $this->links[$func];
485            if ( $ownInfo->hasParam( $param ) ) {
486                $ret = new PreservedTaintedness( $ownInfo->getParamOffsets( $param ) );
487            }
488        }
489        if ( !$ret ) {
490            $ret = PreservedTaintedness::emptySingleton();
491        }
492        foreach ( $this->dimLinks as $dim => $dimLinks ) {
493            $ret = $ret->withOffsetTaintedness( $dim, $dimLinks->asPreservedTaintednessForFuncParam( $func, $param ) );
494        }
495        if ( $this->unknownDimLinks ) {
496            $ret = $ret->withOffsetTaintedness(
497                null,
498                $this->unknownDimLinks->asPreservedTaintednessForFuncParam( $func, $param )
499            );
500        }
501        if ( $this->keysLinks && $this->keysLinks->contains( $func ) ) {
502            $keyInfo = $this->keysLinks[$func];
503            if ( $keyInfo->hasParam( $param ) ) {
504                $ret = $ret->withKeysOffsets( $keyInfo->getParamOffsets( $param ) );
505            }
506        }
507        return $ret;
508    }
509
510    /**
511     * If $taintFlags are the taintedness flags of a sink, and $this are the links passed to that sink, return a
512     * Taintedness object representing the backpropagated exec taintedness to be added to the given function parameter.
513     */
514    public function asTaintednessForBackprop( int $taintFlags, FunctionInterface $func, int $param ): Taintedness {
515        $ret = Taintedness::safeSingleton();
516        if ( !$taintFlags ) {
517            return $ret;
518        }
519        $allLinks = $this->getLinksCollapsing();
520        if ( $allLinks->contains( $func ) ) {
521            $paramInfo = $allLinks[$func];
522            if ( $paramInfo->hasParam( $param ) ) {
523                $paramOffsets = $paramInfo->getParamOffsets( $param );
524                $taintAsYes = new Taintedness( Taintedness::flagsAsExecToYesTaint( $taintFlags ) );
525                $ret = $paramOffsets->appliedToTaintednessForBackprop( $taintAsYes )->asYesToExecTaint();
526            }
527        }
528
529        return $ret;
530    }
531
532    /**
533     * @param FunctionInterface $func
534     * @param int $param
535     * @return self
536     */
537    public function asFilteredForFuncAndParam( FunctionInterface $func, int $param ): self {
538        if ( $this === self::emptySingleton() ) {
539            return $this;
540        }
541        $retLinks = new LinksSet();
542        if ( $this->links->contains( $func ) ) {
543            $retLinks->attach( $func, $this->links[$func] );
544        }
545        $ret = new self( $retLinks );
546        foreach ( $this->dimLinks as $dim => $dimLinks ) {
547            $ret = $ret->withLinksAtDim( $dim, $dimLinks->asFilteredForFuncAndParam( $func, $param ) );
548        }
549        if ( $this->unknownDimLinks ) {
550            $ret = $ret->withLinksAtDim(
551                null,
552                $this->unknownDimLinks->asFilteredForFuncAndParam( $func, $param )
553            );
554        }
555        if ( $this->keysLinks && $this->keysLinks->contains( $func ) ) {
556            $ret->keysLinks = new LinksSet();
557            $ret->keysLinks->attach( $func, $this->keysLinks[$func] );
558        }
559        return $ret;
560    }
561
562    /**
563     * @codeCoverageIgnore
564     */
565    public function toString( string $indent = '' ): string {
566        if ( $this === self::emptySingleton() ) {
567            return '(empty)';
568        }
569        $elementsIndent = $indent . "\t";
570        $ret = "{\n$elementsIndent" . 'OWN: ' . $this->links->__toString() . ',';
571        if ( $this->keysLinks ) {
572            $ret .= "\n{$elementsIndent}KEYS: " . $this->keysLinks->__toString() . ',';
573        }
574        if ( $this->dimLinks || $this->unknownDimLinks ) {
575            $ret .= "\n{$elementsIndent}CHILDREN: {";
576            $childrenIndent = $elementsIndent . "\t";
577            foreach ( $this->dimLinks as $key => $links ) {
578                $ret .= "\n$childrenIndent$key" . $links->toString( $childrenIndent ) . ',';
579            }
580            if ( $this->unknownDimLinks ) {
581                $ret .= "\n$childrenIndent(UNKNOWN): " . $this->unknownDimLinks->toString( $childrenIndent );
582            }
583            $ret .= "\n$elementsIndent}";
584        }
585        return $ret . "\n$indent}";
586    }
587
588    /**
589     * @codeCoverageIgnore
590     */
591    public function __toString(): string {
592        return $this->toString();
593    }
594}