Adding a range operator to PHP / Mail.ru Group Blog

AloneCoder February 2, 2016 at 14:00

Adding a range operator to PHP

Transfer

_{In the picture - Ancient Psychic Tandem War Elephant © Adventure Time}

This article will discuss the process of introducing a new operator in PHP. To do this, the following steps will be performed:

Updating the lexical analyzer : he will know about the syntax of the new operator, which will then turn it into a token.
Parser update : the system will know where this operator can be used, and at the same time what is its priority and associativity.
Updating the compilation stage : here the traverse of the abstract syntax tree (AST) is processed and the operation codes are extracted from it.
Updating the Zend virtual machine : during script execution, it is used to process the interpretation of the new operation code for the operator.

In general, this article will briefly look at a few of the inside points of PHP. I express my gratitude to Nikita Popov for help in finalizing this article.

Range operator

This is the name of the operator that we will add to PHP. It is indicated by two characters: |>. For the sake of simplicity, its semantics will be defined as follows:

The increment of the increment will always be equal to one.
The operands can be integer or floating point.
If min = max, then a singleton array containing min will be returned.

These points will be discussed in the last section, “Updating the Zend Virtual Machine,” when we introduce semantics.

If at least one point is not executed, an exception will be thrown Error. That is:

If the operand is not an integer or a floating point.
If min> max.
If the range (max - min) is too large.

Examples:

1 |> 3; // [1, 2, 3]
2.5 |> 5; // [2.5, 3.5, 4.5]
$a = $b = 1;
$a |> $b; // [1]
2 |> 1; // Error exception
1 |> '1'; // Error exception
new StdClass |> 1; // Error exception

Lexical analyzer update

First, you need to register a new token in the analyzer. This is necessary so that when> tokens are selected from the source code, T_RANGE|> is returned to the token . To do this, you will have to update the file Zend / zend_language_scanner.l . Add the following code to it (in the section where all tokens are declared, about the 1200th line):

"|>" {
    RETURN_TOKEN(T_RANGE);
}

The analyzer is now in mode ST_IN_SCRIPTING. This means that it will only determine the sequence of characters |>. Between the curly braces is a C code that will be executed when |> is detected in the source code. In this example, the token returns T_RANGE.

Retreat. Since we are modifying the lexical analyzer, then for its regeneration we need Re2c. For normal PHP builds this dependency is not needed.

The identifier T_RANGEmust be declared in the file Zend / zend_language_parser.y . To do this, add to the end of the section where the remaining token identifiers are declared (approximately 220th line):

%token T_RANGE           "|> (T_RANGE)"

PHP now recognizes the new operator:

1 |> 2; // Parse error: syntax error, unexpected '|>' (T_RANGE) in...

But since its use is not described, we get a parsing error. In the next part, we will fix it.

Now we need to regenerate the ext / tokenizer / tokenizer_data.c file as a tokenizer extension in order to be able to work with the new token. This extension simply provides an interface between the analyzer and the user environment through the token_get_alland functions token_name. At the moment, he is in happy ignorance regarding the token T_RANGE:

echo token_name(token_get_all('2;')[2][0]); // UNKNOWN

To regenerate ext / tokenizer / tokenizer_data.c, go to the ext / tokenizer folder and execute the tokenizer_data_gen.sh file. Then we return to the root folder php-src and rebuild PHP. Check the extension of the tokenizer:

echo token_name(token_get_all('2;')[2][0]); // T_RANGE

Parser update

The parser needs to be updated so that it can check where the new token is used in PHP scripts T_RANGE. The parser is also responsible for:

prioritization and associativity of the new operator,
generating a new node in the abstract syntax tree.

All this is done using the Zend / zend_language_parser.y grammar file , which contains token declarations and production rules that Bison will use to generate the parser.

Retreat . Priority sets the rules for grouping expressions. For example, in the expression 3 + 4 * 2, the * character has a higher priority than +, so the expression will be grouped as 3 + (4 * 2).

Associativity describes the behavior of the operator during chain building: whether the operator can be embedded in the chain, and if so, how it will be grouped within a particular expression. Suppose a ternary operator has left-side associativity, then it will be grouped and executed from left to right. That is, the expression

1 ? 0 : 1 ? 0 : 1; // 1

will be executed as

(1 ? 0 : 1) ? 0 : 1; // 1

If you correct this and prescribe right-handed associativity, the expression will be executed as follows:

$a = 1 ? 0 : (1 ? 0 : 1); // 0

There are non-associative operators that cannot be embedded in chains at all. Say the> operator. So this expression will be erroneous:

1 < $a < 2;

Since the range operator will perform calculations in the array, it will be pointless to use it as an operand for itself (for example, 1 |> 3 |> 5). So let's make it non-associative. And at the same time we will give it the same priority as the combined comparison operator ( T_SPACESHIP). This is done by adding a token T_RANGEto the end of the next line (approximately 70th):

%nonassoc T_IS_EQUAL T_IS_NOT_EQUAL T_IS_IDENTICAL T_IS_NOT_IDENTICAL T_SPACESHIP T_RANGE

Now, to work with the new operator, you need to update the rule expr_without_variable. Add the following code to it (for example, right before the rule T_SPACESHIP, about the 930th line):

|   expr T_RANGE expr
            { $$ = zend_ast_create(ZEND_AST_RANGE, $1, $3); }

Symbol | used as or . This means that any of the listed rules can match. If a match is found, the code inside the curly brackets will be executed. $$ denotes the result node in which the value of the expression is stored. The function zend_ast_createis used to create our AST for a new operator. The node name is ZEND_AST_RANGE, it contains two values: $ 1 refers to the left operand ( expr T_RANGE expr), $ 3 refers to the right operand (expr T_RANGE expr ).

Now we need to set a constant for AST ZEND_AST_RANGE. To do this, update the Zend / zend_ast.h file by simply adding a constant under the list of two child nodes (for example, under ZEND_AST_COALESCE):

ZEND_AST_RANGE,

Now the execution of our range operator will just hang the interpreter:

1 |> 2;

Update compilation stage

As a result of the parser, we get the AST tree, which is then scanned in the reverse order. Initialization of the execution of functions is carried out as each node of the tree is visited. Initialized functions send operation codes, which are later executed by the Zend virtual machine during interpretation.

Compilation is done in Zend / zend_compile.c . Let's add the name of our new AST node ( ZEND_AST_RANGE) to the large branch operator in the function zend_compile_expr(for example, right after ZEND_AST_COALESCE, about the 7200th line):

 case ZEND_AST_RANGE:
            zend_compile_range(result, ast);
            return;

Now somewhere in the same file you need to declare a function zend_compile_range:

void zend_compile_range(znode *result, zend_ast *ast) /* {{{ */
{
    zend_ast *left_ast = ast->child[0];
    zend_ast *right_ast = ast->child[1];
    znode left_node, right_node;
    zend_compile_expr(&left_node, left_ast);
    zend_compile_expr(&right_node, right_ast);
    zend_emit_op_tmp(result, ZEND_RANGE, &left_node, &right_node);
}
/* }}} */

We begin by dereferencing the left and right operands of the node ZEND_AST_RANGEinto pointer variables left_astand right_ast. Next, we declare two znode variables in which the result of compiling the AST nodes of each of the two operands will be stored. This is the recursive part of processing the tree and compiling its nodes into operation codes.

Now, using the function, we zend_emit_op_tmpgenerate an operation code ZEND_RANGEwith its two operands.

Let's briefly discuss the operation codes and their types in order to better understand the meaning of using a function zend_emit_op_tmp.

Operation codes are instructions that are executed by a virtual machine. Each of them has:

Name (integer constant).
Node op1 (optional).
Node op2 (optional).
Results node (optional). It is usually used to store the temporary value of the operation to which the given code corresponds.
Extended value (optional). This is the integer value used to distinguish between behaviors for overloaded opcodes.

Retreat . The opcodes for PHP scripts can be found out with:

PHPDBG: sapi/phpdbg/phpdbg -np* program.php
Opcache
Extensions Vulcan Logic Disassembler (VLD) :sapi/cli/php -dvld.active=1 program.php
If the script is short and simple, then you can use 3v4l

Opcode nodes (structures znode_op) can be of different types:

IS_CV( C ompiled V ariables). These are simple variables (like $ a) that are cached in simple arrays to bypass searches in the hash table. They appeared in PHP 5.1 as an optimization of Compiled Variables. In VLDs, they are denoted with! N (n is an integer).
IS_VAR. For all complex expressions that act as variables (like $ a-> b). May contain zval IS_REFERENCE, in VLDs are denoted using $ n (n is an integer).
IS_CONST. For literal values (e.g., explicitly written string values).
IS_TMP_VAR. Temporary variables are used to store the intermediate result of the expression (and therefore do not exist for long). They can participate in reference counting (refcount) (in PHP 7), but they cannot contain it zval IS_REFERENCE, because temporary variables cannot be used as references. VLDs are denoted by ~ n (n is an integer).
IS_UNUSED. Commonly used to designate op node as unused. But sometimes znode_op.numdata can be stored for use by a virtual machine.

This brings us back to the function zend_emit_op_tmpthat will generate the zend_optype IS_TMP_VAR. We need this because our operator will be an expression, and the value it produces (an array) will be a temporary variable that can be used as an operand for another opcode (for example, ASSIGNfrom code $var = 1 |> 3;).

Zend Virtual Machine Update

To process the execution of our new opcode, you need to update the virtual machine. This implies updating the Zend / zend_vm_def.h file . Add to the very end:

ZEND_VM_HANDLER(182, ZEND_RANGE, CONST|TMP|VAR|CV, CONST|TMP|VAR|CV)
{
    USE_OPLINE
    zend_free_op free_op1, free_op2;
    zval *op1, *op2, *result, tmp;
    SAVE_OPLINE();
    op1 = GET_OP1_ZVAL_PTR_DEREF(BP_VAR_R);
    op2 = GET_OP2_ZVAL_PTR_DEREF(BP_VAR_R);
    result = EX_VAR(opline->result.var);
    // if both operands are integers
    if (Z_TYPE_P(op1) == IS_LONG && Z_TYPE_P(op2) == IS_LONG) {
        // for when min and max are integers
    } else if ( // if both operands are either integers or doubles
        (Z_TYPE_P(op1) == IS_LONG || Z_TYPE_P(op1) == IS_DOUBLE)
        && (Z_TYPE_P(op2) == IS_LONG || Z_TYPE_P(op2) == IS_DOUBLE)
    ) {
        // for when min and max are either integers or floats
    } else {
        // for when min and max are neither integers nor floats
    }
    FREE_OP1();
    FREE_OP2();
    ZEND_VM_NEXT_OPCODE_CHECK_EXCEPTION();
}

The opcode number must be one more than the previous maximum value, so you can take 182. To quickly find out the last maximum number, look at the file Zend / zend_vm_opcodes.h , there is a constant at the end ZEND_VM_LAST_OPCODE.

Retreat . The above code contains several pseudo-macros ( USE_OPLINEand GET_OP1_ZVAL_PTR_DEREF). These are not true C-macros; during the virtual machine generation, they are replaced by the Zend / zend_vm_gen.php script , unlike the procedure performed by the preprocessor during compilation of the source code. So if you want to see their definitions, then refer to the Zend / zend_vm_gen.php file .

The ZEND_VM_HANDLERpseudo macro contains a definition of each opcode. It can have five parameters:

Opcode number (182).
Opcode Name ( ZEND_RANGE).
Correct the left operand types (CONST | TMP | VAR | CV ) ( see. $vm_op_decodeIn the Zend / zend_vm_gen.php ).
The right types of right operand (CONST | TMP | VAR | CV ) ( see. $vm_op_decodeIn the Zend / zend_vm_gen.php ).
Optional flag value for a spread congested codes (see. $vm_ext_decodeIn Zend / zend_vm_gen.php ).

Given the above, we can see:

// CONST enables for
1 |> 5.0;
// TMP enables for
(2**2) |> (1 + 3);
// VAR enables for
$cmplx->var |> $var[1];
// CV enables for
$a |> $b;

Retreat . If one or both operands are not used, then they are marked with ANY.

Retreat . TMPVARappeared in ZE 3. It processes the same types of opcode nodes as it does TMP|VAR, but generates different code. TMPVARIt generates one method for processing TMPand VAR, which reduces the size of the virtual machine, but requires more conditional logic. And it TMP|VARgenerates separate methods for processing TMPand VAR, which increases the size of the virtual machine, but requires less conditional structures.

We turn to the "body" of our definition of opcode. We start by calling the pseudo USE_OPLINEmacro to declare the opline variable (zend_op structure). It will be used to read operands (using pseudo GET_OP1_ZVAL_PTR_DEREF-macros like ) and write the return value of the opcode.

Next, we declare two variables zend_free_op. These are simple zval pointers declared for each operand we use. They are needed during the check whether some operand needs to be freed. Then we declare four variables zval. op1and - op2pointers to these zval's, they contain the values of the operand. We declare a variable resultto store the results of the opcode operation. And finally, we announcetmpto store the intermediate value of the loop operation in a range. This value will be copied to the hash table at each iteration.

Variables op1and are op2initialized respectively by pseudo-macros GET_OP1_ZVAL_PTR_DEREFand GET_OP2_ZVAL_PTR_DEREF. Also, these macros are responsible for initializing the variables free_op1 and free_op2 . The constant BP_VAR_Rpassed to the above macros is a type flag. Its name stands for BackPatching Variable Read , it is used when reading compiled variables . And finally, we dereference oplineand assign resultits value for future use.

Now let's fill in the "body" of the first if, provided that minthey maxare integers:

zend_long min = Z_LVAL_P(op1), max = Z_LVAL_P(op2);
zend_ulong size, i;
if (min > max) {
    zend_throw_error(NULL, "Min should be less than (or equal to) max");
    HANDLE_EXCEPTION();
}
// calculate size (one less than the total size for an inclusive range)
size = max - min;
// the size cannot be greater than or equal to HT_MAX_SIZE
// HT_MAX_SIZE - 1 takes into account the inclusive range size
if (size >= HT_MAX_SIZE - 1) {
    zend_throw_error(NULL, "Range size is too large");
    HANDLE_EXCEPTION();
}
// increment the size to take into account the inclusive range
++size;
// set the zval type to be a long
Z_TYPE_INFO(tmp) = IS_LONG;
// initialise the array to a given size
array_init_size(result, size);
zend_hash_real_init(Z_ARRVAL_P(result), 1);
ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(result)) {
    for (i = 0; i < size; ++i) {
        Z_LVAL(tmp) = min + i;
        ZEND_HASH_FILL_ADD(&tmp);
    }
} ZEND_HASH_FILL_END();
ZEND_VM_NEXT_OPCODE_CHECK_EXCEPTION();

We start by defining the variables minand max. They are declared as zend_longwhich should be used when declaring long integers (similar to how they zend_ulongare used to define long unsigned integers). The size is then declared using the zend_ulongvalue containing the size of the array to be generated.

Next, a check is performed: if min > max, then an exception is thrown Error. If you zend_throw_errorpass as the first argument to Null, then by default there will be an exception class Error. Using inheritance, you can fine-tune this exception by creating an entry for a new class in Zend / zend_exceptions.c. But we’ll talk more about this another time. If this exception occurs, then we call the pseudo- HANDLE_EXCEPTIONmacro, which proceeds to the execution of the next opcode.

Now we calculate the size of the array that will need to be generated. He must be one less than the actual size, since there is a possibility of overflow if min = ZEND_LONG_MIN (PHP_INT_MIN)and max = ZEND_LONG_MAX (PHP_INT_MAX).

After that, the calculated size is compared with a constant HT_MAX_SIZEto make sure that the array fits in the hash table. The total size of the array should not be greater than or equal to HT_MAX_SIZE. Otherwise, we throw an exception again Errorand exit the virtual machine.

We know that HT_MAX_SIZE = INT_MAX + 1. If the resulting value is greatersize, then we can increase the latter without fear of overflow. This is what we are doing as the next step, so that the value sizecorresponds to the size of the range.

Now change the type of zval tmp на IS_LONG. Then, using the macro, we array_init_sizeinitialize result. This macro assigns a result’уtype IS_ARRAY_EX, allocates memory for the structure zend_array(hash table), and sets up the corresponding hash table. The function then zend_hash_real_initallocates memory for the Bucket structures containing each element of the array. The second argument, 1, indicates that we want to make it a packed hashtable.

Retreat . Packaged hash table - this is, in fact, the actual array (actual array), that is, an array which can be accessed using integer keys (unlike typical associative arrays in PHP). This optimization was implemented in PHP 7. The reason for this innovation is that in PHP many arrays are indexed by integers (keys in ascending order). Packed hash tables provide direct access to the hash table pool. If you are interested in the details of the new hash table implementation, see Nikita's article .

Retreat . The structure _zend_arrayhas two aliases: zend_arrayand HashTable.

Fill the array with a macro ZEND_HASH_FILL_PACKED( definition ), which essentially tracks the current bucket for later insertion. During array generation, the intermediate result (array element) is stored in zval tmp. The macro ZEND_HASH_FILL_ADDcreates a copy tmp, inserts it into the current bucket of the hash table, and moves on to the next bucket for the next iteration.

Finally, the macro ZEND_VM_NEXT_OPCODE_CHECK_EXCEPTION(introduced in ZE 3 as a replacement for individual calls CHECK_EXCEPTION()and ZEND_VM_NEXT_OPCODE()embedded in ZE 2) checks to see if an exception has occurred. It did not arise, and the virtual machine moves on to the next opcode.

Let's now look at the block else if:

long double min, max, size, i;
if (Z_TYPE_P(op1) == IS_LONG) {
    min = (long double) Z_LVAL_P(op1);
    max = (long double) Z_DVAL_P(op2);
} else if (Z_TYPE_P(op2) == IS_LONG) {
    min = (long double) Z_DVAL_P(op1);
    max = (long double) Z_LVAL_P(op2);
} else {
    min = (long double) Z_DVAL_P(op1);
    max = (long double) Z_DVAL_P(op2);
}
if (min > max) {
    zend_throw_error(NULL, "Min should be less than (or equal to) max");
    HANDLE_EXCEPTION();
}
size = max - min;
if (size >= HT_MAX_SIZE - 1) {
    zend_throw_error(NULL, "Range size is too large");
    HANDLE_EXCEPTION();
}
// we cast the size to an integer to get rid of the decimal places,
// since we only care about whole number sizes
size = (int) size + 1;
Z_TYPE_INFO(tmp) = IS_DOUBLE;
array_init_size(result, size);
zend_hash_real_init(Z_ARRVAL_P(result), 1);
ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(result)) {
    for (i = 0; i < size; ++i) {
        Z_DVAL(tmp) = min + i;
        ZEND_HASH_FILL_ADD(&tmp);
    }
} ZEND_HASH_FILL_END();
ZEND_VM_NEXT_OPCODE_CHECK_EXCEPTION();

Retreat . We use long doublein cases where the simultaneous use of integer operands and floating point. The fact is that the accuracy doubleis only 53 bits, so when using this type, any integer greater than 2 ⁵³ will be presented inaccurately. And long doubleaccuracy is at least 64 bits, so it allows you to accurately use 64-bit integers.

The above code is very similar in logic to the previous one. The main difference is that now we process the data as floating point numbers. It belongs:

to receive them from a macro Z_DVAL_P,
destination type IS_DOUBLE для tmp,
as well as inserting zval (type double) using a macro Z_DVAL.

Finally, we need to handle cases in which either min, or max, or both of them are neither integer nor floating point. As stated in the second paragraph of the semantics of our range operator, only integers and floating point are supported as operands. In all other cases, an exception should be thrown Error. Let's insert the elsefollowing code into the block :

zend_throw_error(NULL, "Unsupported operand types - only ints and floats are supported");
HANDLE_EXCEPTION();

Now we have finished defining our opcode, it's time to regenerate the virtual machine. To do this, we run the file Zend / zend_vm_gen.php , and he will use the file Zend / zend_vm_def.h to regenerate Zend / zend_vm_opcodes.h , Zend / zend_vm_opcodes.c and Zend / zend_vm_execute.h .

Let's rebuild PHP to make sure our range operator is working:

var_dump(1 |> 1.5);
var_dump(PHP_INT_MIN |> PHP_INT_MIN + 1);

Output:

array(1) {
  [0]=>
  float(1)
}
array(2) {
  [0]=>
  int(-9223372036854775808)
  [1]=>
  int(-9223372036854775807)
}

Our operator is finally working! But we are not done yet. It remains to update the pretty printer of our AST tree (turns the tree back into code). Pretty printer does not yet support our new operator, you can verify this with assert():

assert(1 |> 2); // segfaults

Retreat . On failure, it assert()uses pretty printer to output an expression that was declared as part of its own error message. This is done only if the declared expression is not presented in string format (otherwise, pretty printer is not needed). By the way, this functionality appeared in PHP 7.

To fix this, we just need to update the Zend / zend_ast.c file , turning the node ZEND_AST_RANGEinto a string. First, we’ll change the comment on the priority table (about the 520th line), assigning priority 170 to our new operator (it should match the file zend_language_parser.y):

*  170     non-associative == != === !== |>

Then, for processing, ZEND_AST_RANGEinsert the zend_ast_export_exoperator into the function case(directly above the case ZEND_AST_GREATER):

case ZEND_AST_RANGE:                   BINARY_OP(" |> ",  170, 171, 171);
case ZEND_AST_GREATER:                 BINARY_OP(" > ",   180, 181, 181);
case ZEND_AST_GREATER_EQUAL:           BINARY_OP(" >= ",  180, 181, 181);

Now pretty printer has been updated and assert()works great:

assert(false && 1 |> 2); // Warning: assert(): assert(false && 1 |> 2) failed...

Conclusion

This article addresses a number of issues, albeit rather superficially. The stages through which the Zend engine goes through when running PHP scripts, how these stages are related to each other and how they can be modified to introduce a new operator in PHP are demonstrated. The article shows only one of the possible ways to implement the range operator. I hope that in the future I will be able to talk about other - perhaps better - options, as well as consider in more detail a number of other issues (for example, creating new inner classes).

Tags: