Version 7.0
Copyright © 2021 Lowell D. Thomas
APG
… an ABNF Parser Generator
rule-dependencies.c
Go to the documentation of this file.
1 /* *************************************************************************************
2  Copyright (c) 2021, Lowell D. Thomas
3  All rights reserved.
4 
5  This file is part of APG Version 7.0.
6  APG Version 7.0 may be used under the terms of the BSD 2-Clause License.
7 
8  Redistribution and use in source and binary forms, with or without
9  modification, are permitted provided that the following conditions are met:
10 
11  1. Redistributions of source code must retain the above copyright notice, this
12  list of conditions and the following disclaimer.
13 
14  2. Redistributions in binary form must reproduce the above copyright notice,
15  this list of conditions and the following disclaimer in the documentation
16  and/or other materials provided with the distribution.
17 
18  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
22  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
24  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
25  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
26  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 
29 * *************************************************************************************/
37 #include "./api.h"
38 #include "./apip.h"
39 #include "./attributes.h"
40 
44 //#define DEPENDENCIES_DEBUG 1
45 #ifdef DEPENDENCIES_DEBUG
46 static void vPrintReferences(attrs_ctx* spAtt);
47 static void vPrintReferals(attrs_ctx* spAtt);
48 static void vPrintRulesByType(attrs_ctx* spAtt);
49 #endif /* DEPENDENCIES_DEBUG */
50 
51 // scans the (single-expansion) syntax tree of each rule to find out which other rules it refers to
52 static void vScan(attrs_ctx* spAtt, aint uiRuleIndex, api_attr_w* spAttr, abool* bpIsScanned);
53 
58 void vRuleDependencies(attrs_ctx* spAtt) {
59  // find all rules referred to by each rule
60  aint ui, uj, uiNewGroup, uiGroupNumber;
61  api_attr_w* spAttri;
62  api_attr_w* spAttrj;
63  aint uiRuleCount = spAtt->spApi->uiRuleCount;
64  abool baIsScanned[uiRuleCount];
65 
66  // scan each rule to see which rules it refers to
67  for (ui = 0; ui < uiRuleCount; ui++) {
68  memset((void*)baIsScanned, 0, (sizeof(abool) * uiRuleCount));
69  vScan(spAtt, ui, &spAtt->spWorkingAttrs[ui], baIsScanned);
70  }
71 
72  // for each rule, find all rules that reference it
73  for (ui = 0; ui < uiRuleCount; ui++) {
74  for (uj = 0; uj < uiRuleCount; uj++) {
75  if(ui != uj){
76  if(spAtt->spWorkingAttrs[uj].bpRefersTo[ui]){
77  spAtt->spWorkingAttrs[ui].bpIsReferencedBy[uj] = APG_TRUE;
78  }
79  }
80  }
81  }
82 
83  // find the non-recursive and recursive types
84  for (ui = 0; ui < spAtt->spApi->uiRuleCount; ui++) {
85  spAtt->spWorkingAttrs[ui].uiRecursiveType = ID_ATTR_N;
86  if (spAtt->spWorkingAttrs[ui].bpRefersTo[ui]) {
87  spAtt->spWorkingAttrs[ui].uiRecursiveType = ID_ATTR_R;
88  }
89  }
90 
91  // find the mutually-recursive groups
92  uiGroupNumber = 0;
93  for (ui = 0; ui < uiRuleCount; ui++) {
94  spAttri = &spAtt->spWorkingAttrs[ui];
95  if (spAttri->uiRecursiveType == ID_ATTR_R) {
96  uiNewGroup = APG_TRUE;
97  for (uj = 0; uj < spAtt->spApi->uiRuleCount; uj++) {
98  if(ui != uj){
99  spAttrj = &spAtt->spWorkingAttrs[uj];
100  if (spAttrj->uiRecursiveType == ID_ATTR_R) {
101  if (spAttri->bpRefersTo[uj] && spAttrj->bpRefersTo[ui]) {
102  if (uiNewGroup) {
103  uiGroupNumber++;
104  vpVecPush(spAtt->vpVecGroupNumbers, &uiGroupNumber);
105  spAttri->uiRecursiveType = ID_ATTR_MR;
106  spAttri->uiMRGroup = uiGroupNumber;
107  uiNewGroup = APG_FALSE;
108  }
109  spAttrj->uiRecursiveType = ID_ATTR_MR;
110  spAttrj->uiMRGroup = uiGroupNumber;
111  }
112  }
113  }
114  }
115  }
116  }
117 
118 #ifdef DEPENDENCIES_DEBUG
119  vPrintReferences(spAtt);
120  vPrintReferals(spAtt);
121  vPrintRulesByType(spAtt);
122 #endif /* DEPENDENCIES_DEBUG */
123 }
124 
125 static void vScan(attrs_ctx* spAtt, aint uiRuleIndex, api_attr_w* spAttr, abool* bpIsScanned){
126  api* spApi = spAtt->spApi;
127  aint uiRuleCount = spApi->uiRuleCount;
128  api_rule* spRule = &spApi->spRules[uiRuleIndex];
129  api_op* spOp = &spApi->spOpcodes[spRule->uiOpOffset];
130  api_op* spOpEnd = &spOp[spRule->uiOpCount];
131  bpIsScanned[uiRuleIndex] = APG_TRUE;
132  for (; spOp < spOpEnd; spOp++) {
133  if (spOp->uiId == ID_RNM) {
134  spAttr->bpRefersTo[spOp->uiIndex] = APG_TRUE;
135  if(!bpIsScanned[spOp->uiIndex]){
136  vScan(spAtt, spOp->uiIndex, spAttr, bpIsScanned);
137  }
138  }else if(spOp->uiId == ID_UDT){
139  spAttr->bpRefersToUdt[spOp->uiIndex] = APG_TRUE;
140  }
141  else if (spOp->uiId == ID_BKR) {
142  if(spOp->uiBkrIndex < uiRuleCount){
143  spAttr->bpRefersTo[spOp->uiBkrIndex] = APG_TRUE;
144  if(!bpIsScanned[spOp->uiBkrIndex]){
145  vScan(spAtt, spOp->uiBkrIndex, spAttr, bpIsScanned);
146  }
147  }else{
148  spAttr->bpRefersToUdt[uiRuleCount - spOp->uiBkrIndex] = APG_TRUE;
149  }
150  }
151  }
152 }
153 
154 #ifdef DEPENDENCIES_DEBUG
155 static void vPrintReferences(attrs_ctx* spAtt) {
156  aint ui, uj, uiCount;
157  api_attr_w* spAttri;
158  api_attr_w* spAttrj;
159  printf("RULE REFERENCES\n");
160  for (ui = 0; ui < spAtt->spApi->uiRuleCount; ui++) {
161  spAttri = &spAtt->spWorkingAttrs[ui];
162  printf("%s refers to:\n", spAttri->cpRuleName);
163  uiCount = 0;
164  for (uj = 0; uj < spAtt->spApi->uiRuleCount; uj++) {
165  spAttrj = &spAtt->spWorkingAttrs[uj];
166  if (spAttri->bpRefersTo[spAttrj->uiRuleIndex]) {
167  uiCount++;
168  printf("%4lu | %s\n", (luint)uj, spAttrj->cpRuleName);
169  }
170  }
171  if (!uiCount) {
172  printf(" %s\n", "<none>");
173  }
174  }
175  printf("\n");
176 }
177 
178 static void vPrintReferals(attrs_ctx* spAtt) {
179  aint ui, uj, uiCount;
180  api_attr_w* spAttri;
181  api_attr_w* spAttrj;
182  printf("RULE REFERALS\n");
183  for (ui = 0; ui < spAtt->spApi->uiRuleCount; ui++) {
184  spAttri = &spAtt->spWorkingAttrs[ui];
185  printf("%s is referenced by:\n", spAttri->cpRuleName);
186  uiCount = 0;
187  for (uj = 0; uj < spAtt->spApi->uiRuleCount; uj++) {
188  spAttrj = &spAtt->spWorkingAttrs[uj];
189  if (spAttri->bpIsReferencedBy[spAttrj->uiRuleIndex]) {
190  uiCount++;
191  printf("%4lu | %s\n", (luint)uj, spAttrj->cpRuleName);
192  }
193  }
194  if (!uiCount) {
195  printf(" %s\n", "<none>");
196  }
197  }
198  if(spAtt->spApi->uiUdtCount){
199  api_udt* spUdt;
200  for (ui = 0; ui < spAtt->spApi->uiUdtCount; ui++) {
201  spUdt = &spAtt->spApi->spUdts[ui];
202 // spAttri = &spAtt->spWorkingAttrs[ui];
203  printf("%s is referenced by:\n", spUdt->cpName);
204  uiCount = 0;
205  for (uj = 0; uj < spAtt->spApi->uiRuleCount; uj++) {
206  spAttrj = &spAtt->spWorkingAttrs[uj];
207  if (spAttrj->bpRefersToUdt[spUdt->uiIndex]) {
208  uiCount++;
209  printf("%4lu | %s\n", (luint)uj, spAttrj->cpRuleName);
210  }
211  }
212  if (!uiCount) {
213  printf(" %s\n", "<none>");
214  }
215  }
216  }
217  printf("\n");
218 }
219 
220 static void vPrintRulesByType(attrs_ctx* spAtt) {
221  api* spApi = spAtt->spApi;
222  aint ui, uj, uiCount;
223  aint uiTotal = 0;
224  printf("ID_ATTR_N (non-recursive, never refers to itself)\n");
225  for (ui = 0, uiCount = 0; ui < spApi->uiRuleCount; ui++) {
226  if (spAtt->spWorkingAttrs[ui].uiRecursiveType == ID_ATTR_N) {
227  uiCount++;
228  }
229  }
230  if (uiCount) {
231  for (ui = 0; ui < spApi->uiRuleCount; ui++) {
232  if (spAtt->spWorkingAttrs[ui].uiRecursiveType == ID_ATTR_N) {
233  printf("%4lu | %s\n", (luint) ui, spAtt->spWorkingAttrs[ui].cpRuleName);
234  uiTotal++;
235  }
236  }
237  } else {
238  printf("<none>\n");
239  }
240  printf("\n");
241  printf("ID_ATTR_R (recursive, refers to itself)\n");
242  for (ui = 0, uiCount = 0; ui < spApi->uiRuleCount; ui++) {
243  if ((spAtt->spWorkingAttrs[ui].uiRecursiveType == ID_ATTR_R)) {
244  uiCount++;
245  }
246  }
247  if (uiCount) {
248  for (ui = 0; ui < spApi->uiRuleCount; ui++) {
249  if (spAtt->spWorkingAttrs[ui].uiRecursiveType == ID_ATTR_R) {
250  printf("%4lu | %s\n", (luint) ui, spAtt->spWorkingAttrs[ui].cpRuleName);
251  uiTotal++;
252  }
253  }
254  } else {
255  printf("<none>\n");
256  }
257  printf("\n");
258  printf(
259  "ID_ATTR_MR (mutually-recursive, within a set, each rule refers to every other rule in the set, including itself)\n");
260  for (ui = 0, uiCount = 0; ui < spApi->uiRuleCount; ui++) {
261  if ((spAtt->spWorkingAttrs[ui].uiRecursiveType == ID_ATTR_MR)) {
262  if (spAtt->spWorkingAttrs[ui].uiMRGroup > uiCount) {
263  uiCount = spAtt->spWorkingAttrs[ui].uiMRGroup;
264  }
265  }
266  }
267  if (uiCount) {
268  printf("index| set| name\n");
269  printf("-----|------|-----\n");
270  for (uj = 1; uj <= uiCount; uj++) {
271  for (ui = 0; ui < spApi->uiRuleCount; ui++) {
272  if ((spAtt->spWorkingAttrs[ui].uiMRGroup == uj)) {
273  printf("%4lu | %4lu | %s\n", (luint) ui, (luint) uj, spAtt->spWorkingAttrs[ui].cpRuleName);
274  uiTotal++;
275  }
276  }
277  }
278  } else {
279  printf("<none>\n");
280  }
281  printf("\n");
282 }
283 #endif /* DEPENDENCIES_DEBUG */
api_attr_w::bpRefersToUdt
abool * bpRefersToUdt
a list of all the UDTs that this rule refers to
Definition: apip.h:111
api::uiUdtCount
aint uiUdtCount
The number of UDTs referenced in the SABNF grammar.
Definition: apip.h:148
api::spRules
api_rule * spRules
Points to an array of rule structures.
Definition: apip.h:145
api_attr_w::bpIsReferencedBy
abool * bpIsReferencedBy
a list of all the rules that refer to this rule
Definition: apip.h:113
ID_RNM
#define ID_RNM
rule name
Definition: parser.h:46
api::spOpcodes
api_op * spOpcodes
Pointer to the array of opcodes for the SANF grammar.
Definition: apip.h:162
attrs_ctx
The API will construct an attributes object. This is the attribute object's context.
Definition: attributes.h:41
api_attr_w
Working attribute information about a each rule.
Definition: apip.h:99
ID_BKR
#define ID_BKR
back reference to a previously matched rule or UDT name
Definition: parser.h:58
ID_UDT
#define ID_UDT
user-defined terminal
Definition: parser.h:55
api_rule
API information about each rule.
Definition: apip.h:55
apip.h
Private header file for the APG API suite of functions.
ID_ATTR_N
#define ID_ATTR_N
rule is non-recursive - never refers to itself
Definition: parser.h:100
api::spUdts
api_udt * spUdts
Points to an array of UDT structures, if one or more UDTs are referenced in the SABNF grammar.
Definition: apip.h:147
api::uiRuleCount
aint uiRuleCount
The number of rules in the SABNF grammar and in the array.
Definition: apip.h:146
aint
uint_fast32_t aint
The APG parser's unsigned integer type.
Definition: apg.h:79
api_udt::cpName
char * cpName
pointer to null-terminated string in the string table
Definition: apip.h:70
attrs_ctx::spApi
api * spApi
Pointer to the parent API context.
Definition: attributes.h:45
api_op::uiIndex
aint uiIndex
index of this referenced rule or UDT
Definition: apip.h:80
api
The API context.
Definition: apip.h:123
luint
uintmax_t luint
luint is used to cast integers suitable for the %"PRIuMAX" printf format.
Definition: apg.h:133
api_attr_w::uiRecursiveType
aint uiRecursiveType
ID_ATTR_N, ID_ATTR_R, ID_ATTR_MR, ID_ATTR_NMR, or ID_ATTR_RMR.
Definition: apip.h:109
api_attr_w::cpRuleName
char * cpRuleName
the rule name for these attributes
Definition: apip.h:107
api_op
API information about each opcode.
Definition: apip.h:78
api_udt
API information about each UDT.
Definition: apip.h:69
attrs_ctx::vpVecGroupNumbers
void * vpVecGroupNumbers
A vector for the discovery of groups of mutually recursive rules.
Definition: attributes.h:53
attributes.h
Header file for the attributes functions.
ID_ATTR_MR
#define ID_ATTR_MR
rule is one of a mutually-recursive group (each rule in the group refers to itself and all others)
Definition: parser.h:102
api_attr_w::bpRefersTo
abool * bpRefersTo
a list of all the rules that this rule refers to
Definition: apip.h:112
api_op::uiId
aint uiId
type of opcode, ID_ALT, etc.
Definition: apip.h:79
APG_TRUE
#define APG_TRUE
Definition: apg.h:291
attrs_ctx::spWorkingAttrs
api_attr_w * spWorkingAttrs
An array of private attribute structures.
Definition: attributes.h:46
abool
uint8_t abool
abool is the APG bool type.
Definition: apg.h:140
api_attr_w::uiRuleIndex
aint uiRuleIndex
the index of the rule for these attributes
Definition: apip.h:108
api_udt::uiIndex
aint uiIndex
index of this UDT in the UDT list
Definition: apip.h:71
api_op::uiBkrIndex
aint uiBkrIndex
if BKR, this is the index to the rule or UDT that is being back referenced
Definition: apip.h:90
api_attr_w::uiMRGroup
aint uiMRGroup
the group number, if this is a member of a mutually-recursive group (there may be multiple groups)
Definition: apip.h:110
ID_ATTR_R
#define ID_ATTR_R
rule is recursive - refers to itself, directly or indirectly, one or more times
Definition: parser.h:101
vRuleDependencies
void vRuleDependencies(attrs_ctx *spAtt)
Compute each rule's dependencies on the other rules, and possibly on itself if the rule is recursive.
Definition: rule-dependencies.c:58
api_rule::uiOpOffset
aint uiOpOffset
offset into the opcode table to the first opcode of this rule
Definition: apip.h:58
vpVecPush
void * vpVecPush(void *vpCtx, void *vpElement)
Adds one element to the end of the array.
Definition: vector.c:193
api_rule::uiOpCount
aint uiOpCount
the number of opcodes in this rule
Definition: apip.h:59
api.h
Public header file for the APG API suite of functions.
APG_FALSE
#define APG_FALSE
Definition: apg.h:292
Generated on Sun Jun 13 2021 14:32:59 for APG by   doxygen 1.8.17
APG Version 7.0 is licensed under the 2-Clause BSD License,
an Open Source Initiative Approved License.