systemsdk / phpcpd / #4

Committed 30 Dec 2024 04:42PM UTC coverage: 75.789%. Remained the same

Build # #4

Build Type

push

Committed by DKravtsov

Commit Message

phpcpd 8.0.0 release. Made codebase refactoring. Updated requirements php 8.3, updated composer dependencies, updated tests to the PHPUnit 11. Updated dev environment to the php 8.4, Phing 3.0, added code quality tools: ecs, phpstan.

Run Details

271 of 379 new or added lines in 20 files covered. (71.5%)

65 existing lines in 13 files now uncovered.

648 of 855 relevant lines covered (75.79%)

2.18 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.56

/src/Detector/Strategy/SuffixTree/SuffixTreeHashTable.php

<?php

declare(strict_types=1);

namespace Systemsdk\PhpCPD\Detector\Strategy\SuffixTree;

/**
 * The hash table used for the {@link SuffixTree} class. It is specifically
 * written and optimized for its implementation and is thus probably of little
 * use for any other application.
 * <p>
 * It hashes from (node, character) pairs to the next node, where nodes are
 * represented by integers and the type of characters is determined by the
 * generic parameter.
 *
 * @author Benjamin Hummel
 * @author $Author: juergens $
 *
 * @version $Revision: 34670 $
 *
 * @ConQAT.Rating GREEN Hash: 6A7A830078AF0CA9C2D84C148F336DF4
 */
class SuffixTreeHashTable
{
    /**
     * These numbers were taken from
     * http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.
     *
     * @var int[]
     */
    private $allowedSizes = [53, 97, 193, 389, 769, 1543,
        3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433,
        1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319,
        201326611, 402653189, 805306457, 1610612741, ];

    /**
     * The size of the hash table.
     *
     * @var int
     */
    private $tableSize;

    /**
     * Storage space for the node part of the key.
     *
     * @var int[]
     */
    private $keyNodes;

    /**
     * Storage space for the character part of the key.
     *
     * @var array<null|AbstractToken>
     */
    private $keyChars;

    /**
     * Storage space for the result node.
     *
     * @var int[]
     */
    private $resultNodes;

    /**
     * Debug info: number of stored nodes.
     *
     * @var int
     */
    private $numStoredNodes = 0;

    /**
     * Debug info: number of calls to find so far.
     *
     * @var int
     */
    private $numFind = 0;

    /**
     * Debug info: number of collisions (i.e. wrong finds) during find so far.
     *
     * @var int
     */
    private $numColl = 0;

    /**
     * Creates a new hash table for the given number of nodes. Trying to add
     * more nodes will result in worse performance down to entering an infinite
     * loop on some operations.
     */
    public function __construct(int $numNodes)
    {
        $minSize = (int)ceil(1.5 * $numNodes);
        $sizeIndex = 0;

        while ($this->allowedSizes[$sizeIndex] < $minSize) {
            $sizeIndex++;
        }
        $this->tableSize = $this->allowedSizes[$sizeIndex];

        $this->keyNodes = array_fill(0, $this->tableSize, 0);
        $this->keyChars = array_fill(0, $this->tableSize, null);
        $this->resultNodes = array_fill(0, $this->tableSize, 0);
    }

    /**
     * Returns the next node for the given (node, character) key pair or a
     * negative value if no next node is stored for this key.
     */
    public function get(int $keyNode, AbstractToken $keyChar): int
    {
        $pos = $this->hashFind($keyNode, $keyChar);

        if ($this->keyChars[$pos] === null) {
            return -1;
        }

        return $this->resultNodes[$pos];
    }

    /**
     * Inserts the given result node for the (node, character) key pair.
     */
    public function put(int $keyNode, AbstractToken $keyChar, int $resultNode): void
    {
        $pos = $this->hashFind($keyNode, $keyChar);

        if ($this->keyChars[$pos] == null) {
            $this->numStoredNodes++;
            $this->keyChars[$pos] = $keyChar;
            $this->keyNodes[$pos] = $keyNode;
        }
        $this->resultNodes[$pos] = $resultNode;
    }

    /**
     * Extracts the list of child nodes for each node from the hash table
     * entries as a linked list. All arrays are expected to be initially empty
     * and of suitable size (i.e. for <em>n</em> nodes it should have size
     * <em>n</em> given that nodes are numbered 0 to n-1). Those arrays will be
     * filled from this method.
     * <p>
     * The method is package visible, as it is tighly coupled to the
     * {@link SuffixTree} class.
     *
     * @param int[] $nodeFirstIndex an array giving for each node the index where the first child
     *                              will be stored (or -1 if it has no children)
     * @param int[] $nodeNextIndex  this array gives the next index of the child list or -1 if
     *                              this is the last one
     * @param int[] $nodeChild      this array stores the actual name (=number) of the mode in the
     *                              child list
     */
    public function extractChildLists(array &$nodeFirstIndex, array &$nodeNextIndex, array &$nodeChild): void
    {
        // Instead of Arrays.fill($nodeFirstIndex, -1);
        foreach (array_keys($nodeFirstIndex) as $k) {
            $nodeFirstIndex[$k] = -1;
        }
        $free = 0;

        for ($i = 0; $i < $this->tableSize; $i++) {
            if ($this->keyChars[$i] !== null) {
                // insert $this->keyNodes[$i] -> $this->resultNodes[$i]
                $nodeChild[$free] = $this->resultNodes[$i];
                $nodeNextIndex[$free] = $nodeFirstIndex[$this->keyNodes[$i]];
                $nodeFirstIndex[$this->keyNodes[$i]] = $free++;
            }
        }
    }

    /**
     * Returns the position of the (node,char) key in the hash map or the
     * position to insert it into if it is not yet in.
     */
    private function hashFind(int $keyNode, AbstractToken $keyChar): int
    {
        $this->numFind++;
        $hash = $keyChar->hashCode();
        $pos = $this->posMod($this->primaryHash($keyNode, $hash));
        $secondary = $this->secondaryHash($keyNode, $hash);

        while ($this->keyChars[$pos] !== null) {
            if ($this->keyNodes[$pos] === $keyNode && $keyChar->equals($this->keyChars[$pos])) {
                break;
            }
            $this->numColl++;
            $pos = ($pos + $secondary) % $this->tableSize;
        }

        return $pos;
    }

    /**
     * Returns the primary hash value for a (node, character) key pair.
     */
    private function primaryHash(int $keyNode, int $keyCharHash): int
    {
        return $keyCharHash ^ (13 * $keyNode);
    }

    /**
     * Returns the secondary hash value for a (node, character) key pair.
     */
    private function secondaryHash(int $keyNode, int $keyCharHash): int
    {
        $result = $this->posMod(($keyCharHash ^ (1025 * $keyNode)));

        if ($result == 0) {
            return 2;
        }

        return $result;
    }

    /**
     * Returns the smallest non-negative number congruent to x modulo
     * {@link #tableSize}.
     */
    private function posMod(int $x): int
    {
        $x %= $this->tableSize;

        if ($x < 0) {
            $x += $this->tableSize;
        }

        return $x;
    }
}

1	<?php
2
3	declare(strict_types=1);
4
5	namespace Systemsdk\PhpCPD\Detector\Strategy\SuffixTree;
6
7	/**
8	* The hash table used for the {@link SuffixTree} class. It is specifically
9	* written and optimized for its implementation and is thus probably of little
10	* use for any other application.
11	* <p>
12	* It hashes from (node, character) pairs to the next node, where nodes are
13	* represented by integers and the type of characters is determined by the
14	* generic parameter.
15	*
16	* @author Benjamin Hummel
17	* @author $Author: juergens $
18	*
19	* @version $Revision: 34670 $
20	*
21	* @ConQAT.Rating GREEN Hash: 6A7A830078AF0CA9C2D84C148F336DF4
22	*/
23	class SuffixTreeHashTable
24	{
25	/**
26	* These numbers were taken from
27	* http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.
28	*
29	* @var int[]
30	*/
31	private $allowedSizes = [53, 97, 193, 389, 769, 1543,
32	3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433,
33	1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319,
34	201326611, 402653189, 805306457, 1610612741, ];
35
36	/**
37	* The size of the hash table.
38	*
39	* @var int
40	*/
41	private $tableSize;
42
43	/**
44	* Storage space for the node part of the key.
45	*
46	* @var int[]
47	*/
48	private $keyNodes;
49
50	/**
51	* Storage space for the character part of the key.
52	*
53	* @var array<null\|AbstractToken>
54	*/
55	private $keyChars;
56
57	/**
58	* Storage space for the result node.
59	*
60	* @var int[]
61	*/
62	private $resultNodes;
63
64	/**
65	* Debug info: number of stored nodes.
66	*
67	* @var int
68	*/
69	private $numStoredNodes = 0;
70
71	/**
72	* Debug info: number of calls to find so far.
73	*
74	* @var int
75	*/
76	private $numFind = 0;
77
78	/**
79	* Debug info: number of collisions (i.e. wrong finds) during find so far.
80	*
81	* @var int
82	*/
83	private $numColl = 0;
84
85	/**
86	* Creates a new hash table for the given number of nodes. Trying to add
87	* more nodes will result in worse performance down to entering an infinite
88	* loop on some operations.
89	*/
90	public function __construct(int $numNodes)
91	{
92	$minSize = (int)ceil(1.5 * $numNodes);	1✔
93	$sizeIndex = 0;	1✔
94
95	while ($this->allowedSizes[$sizeIndex] < $minSize) {	1✔
96	$sizeIndex++;	1✔
97	}
98	$this->tableSize = $this->allowedSizes[$sizeIndex];	1✔
99
100	$this->keyNodes = array_fill(0, $this->tableSize, 0);	1✔
101	$this->keyChars = array_fill(0, $this->tableSize, null);	1✔
102	$this->resultNodes = array_fill(0, $this->tableSize, 0);	1✔
103	}
104
105	/**
106	* Returns the next node for the given (node, character) key pair or a
107	* negative value if no next node is stored for this key.
108	*/
109	public function get(int $keyNode, AbstractToken $keyChar): int
110	{
111	$pos = $this->hashFind($keyNode, $keyChar);	1✔
112
113	if ($this->keyChars[$pos] === null) {	1✔
114	return -1;	1✔
115	}
116
117	return $this->resultNodes[$pos];	1✔
118	}
119
120	/**
121	* Inserts the given result node for the (node, character) key pair.
122	*/
123	public function put(int $keyNode, AbstractToken $keyChar, int $resultNode): void
124	{
125	$pos = $this->hashFind($keyNode, $keyChar);	1✔
126
127	if ($this->keyChars[$pos] == null) {	1✔
128	$this->numStoredNodes++;	1✔
129	$this->keyChars[$pos] = $keyChar;	1✔
130	$this->keyNodes[$pos] = $keyNode;	1✔
131	}
132	$this->resultNodes[$pos] = $resultNode;	1✔
133	}
134
135	/**
136	* Extracts the list of child nodes for each node from the hash table
137	* entries as a linked list. All arrays are expected to be initially empty
138	* and of suitable size (i.e. for <em>n</em> nodes it should have size
139	* <em>n</em> given that nodes are numbered 0 to n-1). Those arrays will be
140	* filled from this method.
141	* <p>
142	* The method is package visible, as it is tighly coupled to the
143	* {@link SuffixTree} class.
144	*
145	* @param int[] $nodeFirstIndex an array giving for each node the index where the first child
146	* will be stored (or -1 if it has no children)
147	* @param int[] $nodeNextIndex this array gives the next index of the child list or -1 if
148	* this is the last one
149	* @param int[] $nodeChild this array stores the actual name (=number) of the mode in the
150	* child list
151	*/
152	public function extractChildLists(array &$nodeFirstIndex, array &$nodeNextIndex, array &$nodeChild): void
153	{
154	// Instead of Arrays.fill($nodeFirstIndex, -1);
155	foreach (array_keys($nodeFirstIndex) as $k) {	1✔
156	$nodeFirstIndex[$k] = -1;	1✔
157	}
158	$free = 0;	1✔
159
160	for ($i = 0; $i < $this->tableSize; $i++) {	1✔
161	if ($this->keyChars[$i] !== null) {	1✔
162	// insert $this->keyNodes[$i] -> $this->resultNodes[$i]
163	$nodeChild[$free] = $this->resultNodes[$i];	1✔
164	$nodeNextIndex[$free] = $nodeFirstIndex[$this->keyNodes[$i]];	1✔
165	$nodeFirstIndex[$this->keyNodes[$i]] = $free++;	1✔
166	}
167	}
168	}
169
170	/**
171	* Returns the position of the (node,char) key in the hash map or the
172	* position to insert it into if it is not yet in.
173	*/
174	private function hashFind(int $keyNode, AbstractToken $keyChar): int
175	{
176	$this->numFind++;	1✔
177	$hash = $keyChar->hashCode();	1✔
178	$pos = $this->posMod($this->primaryHash($keyNode, $hash));	1✔
179	$secondary = $this->secondaryHash($keyNode, $hash);	1✔
180
181	while ($this->keyChars[$pos] !== null) {	1✔
182	if ($this->keyNodes[$pos] === $keyNode && $keyChar->equals($this->keyChars[$pos])) {	1✔
183	break;	1✔
184	}
185	$this->numColl++;	1✔
186	$pos = ($pos + $secondary) % $this->tableSize;	1✔
187	}
188
189	return $pos;	1✔
190	}
191
192	/**
193	* Returns the primary hash value for a (node, character) key pair.
194	*/
195	private function primaryHash(int $keyNode, int $keyCharHash): int
196	{
197	return $keyCharHash ^ (13 * $keyNode);	1✔
198	}
199
200	/**
201	* Returns the secondary hash value for a (node, character) key pair.
202	*/
203	private function secondaryHash(int $keyNode, int $keyCharHash): int
204	{
205	$result = $this->posMod(($keyCharHash ^ (1025 * $keyNode)));	1✔
206
207	if ($result == 0) {	1✔
UNCOV 208	return 2;	×
209	}
210
211	return $result;	1✔
212	}
213
214	/**
215	* Returns the smallest non-negative number congruent to x modulo
216	* {@link #tableSize}.
217	*/
218	private function posMod(int $x): int
219	{
220	$x %= $this->tableSize;	1✔
221
222	if ($x < 0) {	1✔
UNCOV 223	$x += $this->tableSize;	×
224	}
225
226	return $x;	1✔
227	}
228	}

systemsdk / phpcpd / #4

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous