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 for (Index
= 0; Index
< 7; Index
++) {
428 LeftTrim (Pbegin
, length
, Pindex
);
429 if (!ParseHex8 (Pbegin
, length
, Pindex
)) {
434 LeftTrim (Pbegin
, length
, Pindex
);
435 if (strncmp (*Pindex
, ",", 1) != 0) {
442 LeftTrim (Pbegin
, length
, Pindex
);
443 if (!ParseHex8 (Pbegin
, length
, Pindex
)) {
448 LeftTrim (Pbegin
, length
, Pindex
);
449 if (strncmp (*Pindex
, "}", 1) != 0) {
468 Parse rightfactor in bool expression.
472 Pbegin The pointer to the string
473 length length of the string
474 Pindex The pointer of pointer to the next parse character in the string
478 BOOLEAN If string is a valid rightfactor expression, return TRUE, otherwise FALSE
486 LeftTrim (Pbegin
, length
, Pindex
);
489 // <rightfactor> ::=AND <term> <rightbool> <rightfactor>
491 if (strncmp (*Pindex
, OPERATOR_AND
, strlen (OPERATOR_AND
)) == 0) {
492 *Pindex
+= strlen (OPERATOR_AND
);
493 LeftTrim (Pbegin
, length
, Pindex
);
495 if (ParseTerm (Pbegin
, length
, Pindex
)) {
496 LeftTrim (Pbegin
, length
, Pindex
);
498 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
499 LeftTrim (Pbegin
, length
, Pindex
);
500 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
513 // <rightfactor> ::=OR <term> <rightbool> <rightfactor>
515 if (strncmp (*Pindex
, OPERATOR_OR
, strlen (OPERATOR_OR
)) == 0) {
516 *Pindex
+= strlen (OPERATOR_OR
);
517 LeftTrim (Pbegin
, length
, Pindex
);
519 if (ParseTerm (Pbegin
, length
, Pindex
)) {
520 LeftTrim (Pbegin
, length
, Pindex
);
522 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
523 LeftTrim (Pbegin
, length
, Pindex
);
524 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
537 // <rightfactor> ::= ''
553 Parse rightbool in bool expression.
557 Pbegin The pointer to the string
558 length length of the string
559 Pindex The pointer of pointer to the next parse character in the string
563 BOOLEAN If string is a valid rightbool expression, return TRUE, otherwise FALSE
571 LeftTrim (Pbegin
, length
, Pindex
);
574 // <rightbool>::= AND <term><rightbool>
576 if (strncmp (*Pindex
, OPERATOR_AND
, strlen (OPERATOR_AND
)) == 0) {
577 *Pindex
+= strlen (OPERATOR_AND
);
578 LeftTrim (Pbegin
, length
, Pindex
);
580 if (ParseTerm (Pbegin
, length
, Pindex
)) {
581 LeftTrim (Pbegin
, length
, Pindex
);
583 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
593 // <rightbool>::= OR <term><rightbool>
595 if (strncmp (*Pindex
, OPERATOR_OR
, strlen (OPERATOR_OR
)) == 0) {
596 *Pindex
+= strlen (OPERATOR_OR
);
597 LeftTrim (Pbegin
, length
, Pindex
);
599 if (ParseTerm (Pbegin
, length
, Pindex
)) {
600 LeftTrim (Pbegin
, length
, Pindex
);
602 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
628 Parse factor in bool expression.
632 Pbegin The pointer to the string
633 length length of the string
634 Pindex The pointer of pointer to the next parse character in the string
638 BOOLEAN If string is a valid factor, return TRUE, otherwise FALSE
646 LeftTrim (Pbegin
, length
, Pindex
);
649 // <factor> ::= '('<bool>')'<rightfactor>
651 if (strncmp (*Pindex
, OPERATOR_LEFT_PARENTHESIS
, strlen (OPERATOR_LEFT_PARENTHESIS
)) == 0) {
652 *Pindex
+= strlen (OPERATOR_LEFT_PARENTHESIS
);
653 LeftTrim (Pbegin
, length
, Pindex
);
655 if (!ParseBool (Pbegin
, length
, Pindex
)) {
658 LeftTrim (Pbegin
, length
, Pindex
);
660 if (strncmp (*Pindex
, OPERATOR_RIGHT_PARENTHESIS
, strlen (OPERATOR_RIGHT_PARENTHESIS
)) == 0) {
661 *Pindex
+= strlen (OPERATOR_RIGHT_PARENTHESIS
);
662 LeftTrim (Pbegin
, length
, Pindex
);
664 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
673 // <factor> ::= NOT <factor> <rightbool> <rightfactor>
675 if (strncmp (*Pindex
, OPERATOR_NOT
, strlen (OPERATOR_NOT
)) == 0) {
676 *Pindex
+= strlen (OPERATOR_NOT
);
677 LeftTrim (Pbegin
, length
, Pindex
);
679 if (ParseFactor (Pbegin
, length
, Pindex
)) {
680 LeftTrim (Pbegin
, length
, Pindex
);
682 if (ParseRightBool (Pbegin
, length
, Pindex
)) {
683 LeftTrim (Pbegin
, length
, Pindex
);
685 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
698 // <factor> ::= TRUE <rightfactor>
700 if (strncmp (*Pindex
, OPERATOR_TRUE
, strlen (OPERATOR_TRUE
)) == 0) {
701 *Pindex
+= strlen (OPERATOR_TRUE
);
702 LeftTrim (Pbegin
, length
, Pindex
);
704 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
711 // <factor> ::= FALSE <rightfactor>
713 if (strncmp (*Pindex
, OPERATOR_FALSE
, strlen (OPERATOR_FALSE
)) == 0) {
714 *Pindex
+= strlen (OPERATOR_FALSE
);
715 LeftTrim (Pbegin
, length
, Pindex
);
717 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
724 // <factor> ::= <guid> <rightfactor>
726 if (ParseGuid (Pbegin
, length
, Pindex
)) {
727 LeftTrim (Pbegin
, length
, Pindex
);
729 if (ParseRightFactor (Pbegin
, length
, Pindex
)) {
751 Parse term in bool expression.
755 Pbegin The pointer to the string
756 length length of the string
757 Pindex The pointer of pointer to the next parse character in the string
761 BOOLEAN If string is a valid term, return TRUE, otherwise FALSE
769 LeftTrim (Pbegin
, length
, Pindex
);
772 // <term> ::= NOT <factor>
774 if (strncmp (*Pindex
, OPERATOR_NOT
, strlen (OPERATOR_NOT
)) == 0) {
775 *Pindex
+= strlen (OPERATOR_NOT
);
776 LeftTrim (Pbegin
, length
, Pindex
);
778 if (!ParseFactor (Pbegin
, length
, Pindex
)) {
785 // <term> ::=<factor>
787 if (ParseFactor (Pbegin
, length
, Pindex
)) {
805 Parse bool expression.
809 Pbegin The pointer to the string
810 length length of the string
811 Pindex The pointer of pointer to the next parse character in the string
815 BOOLEAN If string is a valid bool expression, return TRUE, otherwise FALSE
822 LeftTrim (Pbegin
, length
, Pindex
);
824 if (ParseTerm (Pbegin
, length
, Pindex
)) {
825 LeftTrim (Pbegin
, length
, Pindex
);
827 if (!ParseRightBool (Pbegin
, length
, Pindex
)) {
848 Parse whole dependency expression.
852 Pbegin The pointer to the string
853 length length of the string
857 BOOLEAN If string is a valid dependency expression, return TRUE, otherwise FALSE
870 LeftTrim (Pbegin
, length
, Pindex
);
871 if (strncmp (*Pindex
, OPERATOR_BEFORE
, strlen (OPERATOR_BEFORE
)) == 0) {
872 (*Pindex
) += strlen (OPERATOR_BEFORE
);
873 Result
= ParseGuid (Pbegin
, length
, Pindex
);
875 } else if (strncmp (*Pindex
, OPERATOR_AFTER
, strlen (OPERATOR_AFTER
)) == 0) {
876 (*Pindex
) += strlen (OPERATOR_AFTER
);
877 Result
= ParseGuid (Pbegin
, length
, Pindex
);
879 } else if (strncmp (*Pindex
, OPERATOR_SOR
, strlen (OPERATOR_SOR
)) == 0) {
880 (*Pindex
) += strlen (OPERATOR_SOR
);
881 Result
= ParseBool (Pbegin
, length
, Pindex
);
884 Result
= ParseBool (Pbegin
, length
, Pindex
);
888 LeftTrim (Pbegin
, length
, Pindex
);
889 return (BOOLEAN
) (Result
&& (*Pindex
) >= (Pbegin
+ length
));