3 Copyright (c) 2004, Intel Corporation
4 All rights reserved. This program and the accompanying materials
5 are licensed and made available under the terms and conditions of the BSD License
6 which accompanies this distribution. The full text of the license may be found at
7 http://opensource.org/licenses/bsd-license.php
9 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
10 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
18 Validate Dependency Expression syntax
19 recursive descent Algorithm
21 The original BNF grammar(taken from "Pre EFI Initialization Core Interface Specification
22 draft review 0.9") is thus:
23 <depex> ::= BEFORE <guid> END
27 <bool> ::= <bool> AND <term>
30 <term> ::= NOT <factor>
37 <guid> ::= '{' <hex32> ',' <hex16> ',' <hex16> ','
38 <hex8> ',' <hex8> ',' <hex8> ',' <hex8> ','
39 <hex8> ',' <hex8> ',' <hex8> ',' <hex8> '}'
40 <hex32> ::= <hexprefix> <hexvalue>
41 <hex16> ::= <hexprefix> <hexvalue>
42 <hex8> ::= <hexprefix> <hexvalue>
43 <hexprefix>::= '0' 'x'
45 <hexvalue> ::= <hexdigit> <hexvalue>
51 After cleaning left recursive and parentheses supported, the BNF grammar used in this module is thus:
52 <depex> ::= BEFORE <guid>
56 <bool> ::= <term><rightbool>
57 <rightbool>::= AND <term><rightbool>
58 | OR <term><rightbool>
60 <term> ::= NOT <factor>
62 <factor> ::= '('<bool>')'<rightfactor>
63 | NOT <factor> <rightbool> <rightfactor>
67 | <guid> <rightfactor>
68 <rightfactor> ::=AND <term><rightbool> <rightfactor>
69 | OR <term><rightbool> <rightfactor>
71 <guid> ::= '{' <hex32> ',' <hex16> ',' <hex16> ','
72 <hex8> ',' <hex8> ',' <hex8> ',' <hex8> ','
73 <hex8> ',' <hex8> ',' <hex8> ',' <hex8> '}'
74 <hex32> ::= <hexprefix> <hexvalue>
75 <hex16> ::= <hexprefix> <hexvalue>
76 <hex8> ::= <hexprefix> <hexvalue>
77 <hexprefix>::= '0' 'x'
79 <hexvalue> ::= <hexdigit> <hexvalue>
85 Note: 1. There's no precedence in operators except parentheses;
86 2. For hex32, less and equal than 8 bits is valid, more than 8 bits is invalid.
87 Same constraint for hex16 is 4, hex8 is 2. All hex should contains at least 1 bit.
88 3. "<factor> ::= '('<bool>')'<rightfactor>" is added to support parentheses;
89 4. "<factor> ::= GUID" is changed to "<factor> ::= <guid>";
90 5. "DEPENDENCY_END" is the terminal of the expression. But it has been filtered by caller.
91 During parsing, "DEPENDENCY_END" will be treated as illegal factor;
93 This code should build in any environment that supports a standard C-library w/ string
94 operations and File I/O services.
96 As an example of usage, consider the following:
98 The input string could be something like:
100 NOT ({ 0xce345171, 0xba0b, 0x11d2, 0x8e, 0x4f, 0x0, 0xa0, 0xc9, 0x69, 0x72,
101 0x3b } AND { 0x964e5b22, 0x6459, 0x11d2, 0x8e, 0x39, 0x0, 0xa0, 0xc9, 0x69,
102 0x72, 0x3b }) OR { 0x03c4e603, 0xac28, 0x11d3, 0x9a, 0x2d, 0x00, 0x90, 0x27,
103 0x3f, 0xc1, 0x4d } AND
105 It's invalid for an extra "AND" in the end.
107 Complies with Tiano C Coding Standards Document, version 0.33, 16 Aug 2001.
111 #include "DepexParser.h"
151 Left trim the space, '\n' and '\r' character in string.
152 The space at the end does not need trim.
157 Pbegin The pointer to the string
158 length length of the string
159 Pindex The pointer of pointer to the next parse character in the string
170 ((*Pindex
) < (Pbegin
+ length
)) &&
171 ((strncmp (*Pindex
, " ", 1) == 0) || (strncmp (*Pindex
, "\n", 1) == 0) || (strncmp (*Pindex
, "\r", 1) == 0))
187 Parse Hex bit in dependency expression.
191 Pbegin The pointer to the string
192 length Length of the string
193 Pindex The pointer of pointer to the next parse character in the string
197 BOOLEAN If parses a valid hex bit, return TRUE, otherwise FALSE
203 // <hexdigit> ::= [0-9] | [a-f] | [A-F]
205 if (((**Pindex
) >= '0' && (**Pindex
) <= '9') ||
206 ((**Pindex
) >= 'a' && (**Pindex
) <= 'f') ||
207 ((**Pindex
) >= 'A' && (**Pindex
) <= 'F')
226 Parse Hex32 in dependency expression.
230 Pbegin The pointer to the string
231 length Length of the string
232 Pindex The pointer of point to the next parse character in the string
236 BOOLEAN If parses a valid hex32, return TRUE, otherwise FALSE
246 LeftTrim (Pbegin
, length
, Pindex
);
248 if ((strncmp (*Pindex
, "0x", 2) != 0) && (strncmp (*Pindex
, "0X", 2) != 0)) {
253 while (ParseHexdigit (Pbegin
, length
, Pindex
)) {
257 if (Index
> 0 && Index
<= 8) {
275 Parse Hex16 in dependency expression.
279 Pbegin The pointer to the string
280 length Length of the string
281 Pindex The pointer of pointer to the next parse character in the string
285 BOOLEAN If parses a valid hex16, return TRUE, otherwise FALSE
295 LeftTrim (Pbegin
, length
, Pindex
);
297 if ((strncmp (*Pindex
, "0x", 2) != 0) && (strncmp (*Pindex
, "0X", 2) != 0)) {
302 while (ParseHexdigit (Pbegin
, length
, Pindex
)) {
306 if (Index
> 0 && Index
<= 4) {
324 Parse Hex8 in dependency expression.
328 Pbegin The pointer to the string
329 length Length of the string
330 Pindex The pointer of pointer to the next parse character in the string
334 BOOLEAN If parses a valid hex8, return TRUE, otherwise FALSE
344 LeftTrim (Pbegin
, length
, Pindex
);
346 if ((strncmp (*Pindex
, "0x", 2) != 0) && (strncmp (*Pindex
, "0X", 2) != 0)) {
351 while (ParseHexdigit (Pbegin
, length
, Pindex
)) {
355 if (Index
> 0 && Index
<= 2) {
373 Parse guid in dependency expression.
374 There can be any number of spaces between '{' and hexword, ',' and hexword,
375 hexword and ',', hexword and '}'. The hexword include hex32, hex16 and hex8.
379 Pbegin The pointer to the string
380 length length of the string
381 Pindex The pointer of pointer to the next parse character in the string
385 BOOLEAN If parses a valid guid, return TRUE, otherwise FALSE
393 LeftTrim (Pbegin
, length
, Pindex
);
394 if (strncmp (*Pindex
, "{", 1) != 0) {
399 LeftTrim (Pbegin
, length
, Pindex
);
400 if (!ParseHex32 (Pbegin
, length
, Pindex
)) {
405 LeftTrim (Pbegin
, length
, Pindex
);
406 if (strncmp (*Pindex
, ",", 1) != 0) {
412 for (Index
= 0; Index
< 2; Index
++) {
413 LeftTrim (Pbegin
, length
, Pindex
);
414 if (!ParseHex16 (Pbegin
, length
, Pindex
)) {
419 LeftTrim (Pbegin
, length
, Pindex
);
420 if (strncmp (*Pindex
, ",", 1) != 0) {
427 LeftTrim (Pbegin
, length
, Pindex
);
428 if (strncmp (*Pindex
, "{", 1) != 0) {
433 for (Index
= 0; Index
< 7; Index
++) {
434 LeftTrim (Pbegin
, length
, Pindex
);
435 if (!ParseHex8 (Pbegin
, length
, Pindex
)) {
440 LeftTrim (Pbegin
, length
, Pindex
);
441 if (strncmp (*Pindex
, ",", 1) != 0) {
448 LeftTrim (Pbegin
, length
, Pindex
);
449 if (!ParseHex8 (Pbegin
, length
, Pindex
)) {
454 LeftTrim (Pbegin
, length
, Pindex
);
455 if (strncmp (*Pindex
, "}", 1) != 0) {
461 LeftTrim (Pbegin
, length
, Pindex
);
462 if (strncmp (*Pindex
, "}", 1) != 0) {
481 Parse rightfactor in bool expression.
485 Pbegin The pointer to the string
486 length length of the string
487 Pindex The pointer of pointer to the next parse character in the string
491 BOOLEAN If string is a valid rightfactor expression, return TRUE, otherwise FALSE
499 LeftTrim (Pbegin
, length
, Pindex
);
502 // <rightfactor> ::=AND <term> <rightbool> <rightfactor>
504 if (strncmp (*Pindex
, OPERATOR_AND
, strlen (OPERATOR_AND
)) == 0) {
505 *Pindex
+= strlen (OPERATOR_AND
);
506 LeftTrim (Pbegin
, length
, Pindex
);
508 if (ParseTerm (Pbegin
, length
, Pindex
)) {
509 LeftTrim (Pbegin
, length
, Pindex
);
511 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
512 LeftTrim (Pbegin
, length
, Pindex
);
513 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
526 // <rightfactor> ::=OR <term> <rightbool> <rightfactor>
528 if (strncmp (*Pindex
, OPERATOR_OR
, strlen (OPERATOR_OR
)) == 0) {
529 *Pindex
+= strlen (OPERATOR_OR
);
530 LeftTrim (Pbegin
, length
, Pindex
);
532 if (ParseTerm (Pbegin
, length
, Pindex
)) {
533 LeftTrim (Pbegin
, length
, Pindex
);
535 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
536 LeftTrim (Pbegin
, length
, Pindex
);
537 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
550 // <rightfactor> ::= ''
566 Parse rightbool in bool expression.
570 Pbegin The pointer to the string
571 length length of the string
572 Pindex The pointer of pointer to the next parse character in the string
576 BOOLEAN If string is a valid rightbool expression, return TRUE, otherwise FALSE
584 LeftTrim (Pbegin
, length
, Pindex
);
587 // <rightbool>::= AND <term><rightbool>
589 if (strncmp (*Pindex
, OPERATOR_AND
, strlen (OPERATOR_AND
)) == 0) {
590 *Pindex
+= strlen (OPERATOR_AND
);
591 LeftTrim (Pbegin
, length
, Pindex
);
593 if (ParseTerm (Pbegin
, length
, Pindex
)) {
594 LeftTrim (Pbegin
, length
, Pindex
);
596 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
606 // <rightbool>::= OR <term><rightbool>
608 if (strncmp (*Pindex
, OPERATOR_OR
, strlen (OPERATOR_OR
)) == 0) {
609 *Pindex
+= strlen (OPERATOR_OR
);
610 LeftTrim (Pbegin
, length
, Pindex
);
612 if (ParseTerm (Pbegin
, length
, Pindex
)) {
613 LeftTrim (Pbegin
, length
, Pindex
);
615 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
641 Parse factor in bool expression.
645 Pbegin The pointer to the string
646 length length of the string
647 Pindex The pointer of pointer to the next parse character in the string
651 BOOLEAN If string is a valid factor, return TRUE, otherwise FALSE
659 LeftTrim (Pbegin
, length
, Pindex
);
662 // <factor> ::= '('<bool>')'<rightfactor>
664 if (strncmp (*Pindex
, OPERATOR_LEFT_PARENTHESIS
, strlen (OPERATOR_LEFT_PARENTHESIS
)) == 0) {
665 *Pindex
+= strlen (OPERATOR_LEFT_PARENTHESIS
);
666 LeftTrim (Pbegin
, length
, Pindex
);
668 if (!ParseBool (Pbegin
, length
, Pindex
)) {
671 LeftTrim (Pbegin
, length
, Pindex
);
673 if (strncmp (*Pindex
, OPERATOR_RIGHT_PARENTHESIS
, strlen (OPERATOR_RIGHT_PARENTHESIS
)) == 0) {
674 *Pindex
+= strlen (OPERATOR_RIGHT_PARENTHESIS
);
675 LeftTrim (Pbegin
, length
, Pindex
);
677 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
686 // <factor> ::= NOT <factor> <rightbool> <rightfactor>
688 if (strncmp (*Pindex
, OPERATOR_NOT
, strlen (OPERATOR_NOT
)) == 0) {
689 *Pindex
+= strlen (OPERATOR_NOT
);
690 LeftTrim (Pbegin
, length
, Pindex
);
692 if (ParseFactor (Pbegin
, length
, Pindex
)) {
693 LeftTrim (Pbegin
, length
, Pindex
);
695 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
696 LeftTrim (Pbegin
, length
, Pindex
);
698 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
711 // <factor> ::= TRUE <rightfactor>
713 if (strncmp (*Pindex
, OPERATOR_TRUE
, strlen (OPERATOR_TRUE
)) == 0) {
714 *Pindex
+= strlen (OPERATOR_TRUE
);
715 LeftTrim (Pbegin
, length
, Pindex
);
717 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
724 // <factor> ::= FALSE <rightfactor>
726 if (strncmp (*Pindex
, OPERATOR_FALSE
, strlen (OPERATOR_FALSE
)) == 0) {
727 *Pindex
+= strlen (OPERATOR_FALSE
);
728 LeftTrim (Pbegin
, length
, Pindex
);
730 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
737 // <factor> ::= <guid> <rightfactor>
739 if (ParseGuid (Pbegin
, length
, Pindex
)) {
740 LeftTrim (Pbegin
, length
, Pindex
);
742 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
764 Parse term in bool expression.
768 Pbegin The pointer to the string
769 length length of the string
770 Pindex The pointer of pointer to the next parse character in the string
774 BOOLEAN If string is a valid term, return TRUE, otherwise FALSE
782 LeftTrim (Pbegin
, length
, Pindex
);
785 // <term> ::= NOT <factor>
787 if (strncmp (*Pindex
, OPERATOR_NOT
, strlen (OPERATOR_NOT
)) == 0) {
788 *Pindex
+= strlen (OPERATOR_NOT
);
789 LeftTrim (Pbegin
, length
, Pindex
);
791 if (!ParseFactor (Pbegin
, length
, Pindex
)) {
798 // <term> ::=<factor>
800 if (ParseFactor (Pbegin
, length
, Pindex
)) {
818 Parse bool expression.
822 Pbegin The pointer to the string
823 length length of the string
824 Pindex The pointer of pointer to the next parse character in the string
828 BOOLEAN If string is a valid bool expression, return TRUE, otherwise FALSE
835 LeftTrim (Pbegin
, length
, Pindex
);
837 if (ParseTerm (Pbegin
, length
, Pindex
)) {
838 LeftTrim (Pbegin
, length
, Pindex
);
840 if (!ParseRightBool (Pbegin
, length
, Pindex
)) {
861 Parse whole dependency expression.
865 Pbegin The pointer to the string
866 length length of the string
870 BOOLEAN If string is a valid dependency expression, return TRUE, otherwise FALSE
883 LeftTrim (Pbegin
, length
, Pindex
);
884 if (strncmp (*Pindex
, OPERATOR_BEFORE
, strlen (OPERATOR_BEFORE
)) == 0) {
885 (*Pindex
) += strlen (OPERATOR_BEFORE
);
886 Result
= ParseGuid (Pbegin
, length
, Pindex
);
888 } else if (strncmp (*Pindex
, OPERATOR_AFTER
, strlen (OPERATOR_AFTER
)) == 0) {
889 (*Pindex
) += strlen (OPERATOR_AFTER
);
890 Result
= ParseGuid (Pbegin
, length
, Pindex
);
892 } else if (strncmp (*Pindex
, OPERATOR_SOR
, strlen (OPERATOR_SOR
)) == 0) {
893 (*Pindex
) += strlen (OPERATOR_SOR
);
894 Result
= ParseBool (Pbegin
, length
, Pindex
);
897 Result
= ParseBool (Pbegin
, length
, Pindex
);
901 LeftTrim (Pbegin
, length
, Pindex
);
902 return (BOOLEAN
) (Result
&& (*Pindex
) >= (Pbegin
+ length
));