Version 7.0
Copyright © 2021 Lowell D. Thomas
APG
… an ABNF Parser Generator
backrefu.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 * *************************************************************************************/
42 #include "./apg.h"
43 #ifdef APG_BKR
44 #include "./lib.h"
45 
46 #include "./parserp.h"
47 #include "./backref.h"
48 #include "./backrefu.h"
49 
50 //static const int iError = 1;
51 static const char* s_cpEmpty = "vector is empty";
52 
53 // rule states
54 static const aint uiUndefined = APG_UNDEFINED;
55 static const aint uiNotFound = 0;
56 static const aint uiFound = 1;
57 static const aint uiOpen = 2;
58 //static const aint uiIsBkr = 3;
59 //static const aint uiRecursive = 4;
60 
61 typedef struct {
62  bkr_rule* spRule;
63 } bkru_frame;
64 
65 typedef struct {
66  const opcode* spOp;
67  bkr_rule* spRule;
68  jmp_buf aJumpBuf;
69  void* vpVecStack;
70 } bkru_input;
71 
72 static void vSESTWalk(backref* spCtx);
73 static void vOpWalk(backref* spCtx, bkru_input* spInput);
74 static void vRnmWalk(backref* spCtx, bkru_input* spInput);
75 static void vAltWalk(backref* spCtx, bkru_input* spInput);
76 static void vCatWalk(backref* spCtx, bkru_input* spInput);
77 static void vRepWalk(backref* spCtx, bkru_input* spInput);
78 static void vFreeAll(backref* spCtx);
79 static void vSetPhrase(backref* spCtx, aint uiIndex, aint uiOffset, aint uiLength);
80 static void vRestoreCheckPoints(backref* spCtx, aint* uipCheckPoints);
81 static void vSetCheckPoints(backref* spCtx, aint* uipCheckPoints);
82 
83 // !!!! DEBUG
84 //#include <stdio.h>
85 //typedef struct print_tag {
86 // bkr_rule* spRule;
87 // aint uiTreeDepth;
88 // aint uiDirection; // down = 1, up = 0, middle = 2;
89 // aint uiState;
90 //} print;
91 //static char* cpState(aint uiState);
92 //static void vPrintRule(print* spPrint);
93 //
95 //static const aint uiDown = 0;
96 //static const aint uiInner = 1;
97 //static const aint uiUp = 2;
98 // !!!! DEBUG
99 
100 void* vpBkruCtor(parser* spParserCtx) {
101  // component mem allocations
102  backref* spCtx = NULL;
103 
104  // temp allocations
105  aint* uipCounters = NULL;
106 
107  void* vpReturn = NULL;
108  aint ui = 0;
109  aint uiCount = spParserCtx->uiRuleCount + spParserCtx->uiUdtCount;
110  aint uiIndex;
111  while (APG_TRUE) {
112  // initialize the component context
113  spCtx = (backref*) vpMemAlloc(spParserCtx->vpMem, (aint) sizeof(backref));
114  memset((void*) spCtx, 0, (aint) sizeof(backref));
115  spCtx->spParserCtx = spParserCtx;
116  spCtx->spException = spMemException(spParserCtx->vpMem);
117 
118  // create space for temp array of counters
119  uipCounters = (aint*) vpMemAlloc(spParserCtx->vpMem, ((aint) sizeof(aint) * uiCount));
120  memset((void*) uipCounters, 0, ((aint) sizeof(aint) * uiCount));
121 
122  // initialize rules and UDTS
123  spCtx->spRules = (bkr_rule*) vpMemAlloc(spParserCtx->vpMem,
124  ((aint) sizeof(bkr_rule) * spParserCtx->uiRuleCount));
125  memset((void*) spCtx->spRules, 0, ((aint) sizeof(bkr_rule) * spParserCtx->uiRuleCount));
126  if (spParserCtx->uiUdtCount) {
127  spCtx->spUdts = (bkr_udt*) vpMemAlloc(spParserCtx->vpMem,
128  ((aint) sizeof(bkr_udt) * spParserCtx->uiUdtCount));
129  }
130  for (ui = 0; ui < spParserCtx->uiRuleCount; ui += 1) {
131  spCtx->spRules[ui].spRule = &spParserCtx->spRules[ui];
132  spCtx->spRules[ui].uiIsBackRef = APG_FALSE;
133  spCtx->spRules[ui].uiHasBackRef = uiUndefined;
134  spCtx->spRules[ui].uiBackRefIndex = uiUndefined;
135  }
136  for (ui = 0; ui < spParserCtx->uiUdtCount; ui += 1) {
137  spCtx->spUdts[ui].spUdt = &spParserCtx->spUdts[ui];
138  spCtx->spUdts[ui].uiIsBackRef = APG_FALSE;
139  spCtx->spUdts[ui].uiBackRefIndex = uiUndefined;
140  }
141 
142  // count the number of back universal-mode referenced rules and UDTs
143  spCtx->uiBkrCount = 0;
144  for (ui = 0; ui < spParserCtx->uiOpcodeCount; ui += 1) {
145  if (spParserCtx->spOpcodes[ui].sGen.uiId == ID_BKR) {
146  if (spParserCtx->spOpcodes[ui].sBkr.uiMode == ID_BKR_MODE_U) {
147  uiIndex = spParserCtx->spOpcodes[ui].sBkr.uiRuleIndex;
148  if (uipCounters[uiIndex] == 0) {
149  if (uiIndex < spParserCtx->uiRuleCount) {
150  spCtx->spRules[uiIndex].uiIsBackRef = APG_TRUE;
151  spCtx->spRules[uiIndex].uiBackRefIndex = spCtx->uiBkrCount;
152  } else {
153  spCtx->spUdts[uiIndex - spParserCtx->uiRuleCount].uiIsBackRef = APG_TRUE;
154  spCtx->spUdts[uiIndex - spParserCtx->uiRuleCount].uiBackRefIndex = spCtx->uiBkrCount;
155  }
156  spCtx->uiBkrCount += 1;
157  }
158  uipCounters[uiIndex] += 1;
159  }
160  }
161  }
162 
163  // !!!! DEBUG
164 // {
165 // aint uiCount = 0;
166 // printf("RULES THAT ARE UNIVERSAL-MODE BACK REFERENCED:\n");
167 // for (ui = 0; ui < spParserCtx->uiRuleCount; ui += 1) {
168 // bkr_rule* spRule = &spCtx->spRules[ui];
169 // if(spRule->uiIsBackRef){
170 // printf("rule: %s: uiIsBackRef: %"PRIuMAX": uiBackRefIndex: %"PRIuMAX"\n",
171 // spRule->spRule->cpRuleName, (luint) spRule->uiIsBackRef, (luint) spRule->uiBackRefIndex);
172 // uiCount++;
173 // }
174 // }
175 // for (ui = 0; ui < spParserCtx->uiUdtCount; ui += 1) {
176 // bkr_udt* spUdt = &spCtx->spUdts[ui];
177 // if(spUdt->uiIsBackRef){
178 // printf(" udt: %s: uiIsBackRef: %"PRIuMAX": uiBackRefIndex: %"PRIuMAX"\n",
179 // spUdt->spUdt->cpUdtName, (luint) spUdt->uiIsBackRef, (luint) spUdt->uiBackRefIndex);
180 // uiCount++;
181 // }
182 // }
183 // if(!uiCount){
184 // printf(" *** NONE ***\n");
185 // }
186 // printf("\n");
187 // }
188  // !!!! DEBUG
189 
190  if (spCtx->uiBkrCount == 0) {
191  // no universal-mode back referenced rules, nothing more to do, return a NULL context
192  break;
193  }
194 
195  // create an initialize the array of stack frames
196  spCtx->vppPhraseStacks = (void**) vpMemAlloc(spParserCtx->vpMem, ((aint) sizeof(void*) * spCtx->uiBkrCount));
197  memset(spCtx->vppPhraseStacks, 0, ((aint) sizeof(void*) * spCtx->uiBkrCount));
198  aint uiIndex = 0;
199  for (ui = 0; ui < uiCount; ui += 1) {
200  if (uipCounters[ui]) {
201  spCtx->vppPhraseStacks[uiIndex] = vpVecCtor(spParserCtx->vpMem, (aint) sizeof(bkr_phrase), 20);
202  uiIndex++;
203  }
204  }
205 
206  // walk the SEST an mark all rules that reference universal-mode back referenced rules & UDTs.
207  vSESTWalk(spCtx);
208 
209  // !!!! DEBUG
210 // {
211 // aint uiCount = 0;
212 // printf("RULES CONTAINING AT LEAST ONE UNIVERSAL-MODE BACK REFERENCED RULE IN ITS (SEST) SYNTAX TREE:\n");
213 // for (ui = 0; ui < spParserCtx->uiRuleCount; ui += 1) {
214 // bkr_rule* spRule = &spCtx->spRules[ui];
215 // if(spRule->uiHasBackRef){
216 // printf("rule: %s: uiHasBackRef: %"PRIuMAX"\n",
217 // spRule->spRule->cpRuleName, (luint) spRule->uiHasBackRef);
218 // uiCount++;
219 // }
220 // }
221 // if(!uiCount){
222 // printf(" *** NONE ***\n");
223 // }
224 // printf("\n");
225 // }
226  // !!!! DEBUG
227 
228  // stack of check points
229  spCtx->vpCheckPoints = vpVecCtor(spParserCtx->vpMem, ((aint) sizeof(aint) * spCtx->uiBkrCount), 100);
230 
231  // create the stack of open rules
232  spCtx->vpOpenRules = vpVecCtor(spParserCtx->vpMem, (aint) sizeof(aint), 100);
233 
234  spCtx->vpValidate = (void*) spCtx;
235  vpReturn = (void*) spCtx;
236  // success
237  break;
238  }
239  if (!vpReturn) {
240  // free allocated memory on error
241  vFreeAll(spCtx);
242  }
243 
244  // always free temporary storage, if any
245  vMemFree(spParserCtx->vpMem, uipCounters);
246  return vpReturn;
247 }
248 
249 static void vFreeAll(backref* spCtx){
250  // free all vectors
251  aint ui;
252  for(ui = 0; ui < spCtx->uiBkrCount; ui += 1){
253  vVecDtor(spCtx->vppPhraseStacks[ui]);
254  }
255  vVecDtor(spCtx->vpCheckPoints);
256  vVecDtor(spCtx->vpOpenRules);
257  // free all memory allocations
258  void* vpMem = spCtx->spParserCtx->vpMem;
259  vMemFree(vpMem, spCtx->vppPhraseStacks);
260  vMemFree(vpMem, (void*)spCtx->spRules);
261  vMemFree(vpMem, (void*)spCtx->spUdts);
262  memset((void*)spCtx, 0, sizeof(*spCtx));
263  vMemFree(vpMem, (void*)spCtx);
264 }
265 
266 static void vSetCheckPoints(backref* spCtx, aint* uipCheckPoints) {
267  aint ui;
268  for (ui = 0; ui < spCtx->uiBkrCount; ui += 1) {
269  uipCheckPoints[ui] = uiVecLen(spCtx->vppPhraseStacks[ui]);
270  }
271 }
272 static void vRestoreCheckPoints(backref* spCtx, aint* uipCheckPoints) {
273  aint ui;
274  for (ui = 0; ui < spCtx->uiBkrCount; ui += 1) {
275  vpVecPopi(spCtx->vppPhraseStacks[ui], uipCheckPoints[ui]);
276  }
277 }
278 static void vSetPhrase(backref* spCtx, aint uiIndex, aint uiOffset, aint uiLength) {
279  bkr_phrase sPhrase = { uiOffset, uiLength };
280  vpVecPush(spCtx->vppPhraseStacks[uiIndex], (void*) &sPhrase);
281 }
282 void vBkruRuleOpen(void* vpCtx, aint uiIndex) {
283  backref* spCtx = (backref*) vpCtx;
284  aint* uipCheckPoints;
285  if (spCtx->spRules[uiIndex].uiHasBackRef || spCtx->spRules[uiIndex].uiIsBackRef) {
286  // this rule is or has on its syntax tree a back referenced rule
287  // save checkpoints on the found back reference stack - may need to restore if this rule fails
288  uipCheckPoints = (aint*)vpVecPush(spCtx->vpCheckPoints, NULL);
289  vSetCheckPoints(spCtx, uipCheckPoints);
290  }
291  // let the operators in this rule's syntax tree know whether or not they need to bother looking for back referenced rules
292  vpVecPush(spCtx->vpOpenRules, (void*) &spCtx->spRules[uiIndex].uiHasBackRef);
293 }
294 
295 void vBkruRuleClose(void* vpCtx, aint uiIndex, aint uiState, aint uiPhraseOffset, aint uiPhraseLength) {
296  backref* spCtx = (backref*) vpCtx;
297  aint* uipCheckPoints;
298  if(uiState == ID_MATCH){
299  if (spCtx->spRules[uiIndex].uiIsBackRef){
300  // push the found back referenced phrase on MATCH
301  vSetPhrase(spCtx, spCtx->spRules[uiIndex].uiBackRefIndex, uiPhraseOffset, uiPhraseLength);
302  }
303  }else{
304  if (spCtx->spRules[uiIndex].uiHasBackRef || spCtx->spRules[uiIndex].uiIsBackRef) {
305  // restore the check points on NOMATCH
306  uipCheckPoints = (aint*)vpVecPop(spCtx->vpCheckPoints);
307  if(!uipCheckPoints){
308  XTHROW(spCtx->spException, s_cpEmpty);
309  }
310  vRestoreCheckPoints(spCtx, uipCheckPoints);
311  }
312 
313  }
314  // always pop the open rules stack - it was only of use to operators in syntax tree below this rule
315  if (!vpVecPop(spCtx->vpOpenRules)) {
316  XTHROW(spCtx->spException, s_cpEmpty);
317  }
318 }
319 
320 void vBkruUdtClose(void* vpCtx, aint uiIndex, aint uiState, aint uiPhraseOffset, aint uiPhraseLength) {
321  backref* spCtx = (backref*) vpCtx;
322  if (spCtx->spUdts[uiIndex].uiIsBackRef && (uiState == ID_MATCH)) {
323  vSetPhrase(spCtx, spCtx->spUdts[uiIndex].uiBackRefIndex, uiPhraseOffset, uiPhraseLength);
324  }
325 }
326 
327 void vBkruOpOpen(void* vpCtx) {
328  backref* spCtx = (backref*) vpCtx;
329  aint* uipCheckPoints;
330  aint* uipOpen = (aint*) vpVecLast(spCtx->vpOpenRules);
331  if (!uipOpen) {
332  XTHROW(spCtx->spException, s_cpEmpty);
333  }
334  if (*uipOpen) {
335  uipCheckPoints = (aint*)vpVecPush(spCtx->vpCheckPoints, NULL);
336  vSetCheckPoints(spCtx, uipCheckPoints);
337  }
338 }
339 
340 void vBkruOpClose(void* vpCtx, aint uiState) {
341  backref* spCtx = (backref*) vpCtx;
342  aint* uipCheckPoints;
343  aint* uipOpen = (aint*) vpVecLast(spCtx->vpOpenRules);
344  if (!uipOpen) {
345  XTHROW(spCtx->spException, s_cpEmpty);
346  }
347  if (*uipOpen) {
348  uipCheckPoints = (aint*)vpVecPop(spCtx->vpCheckPoints);
349  if(!uipCheckPoints){
350  XTHROW(spCtx->spException, s_cpEmpty);
351  }
352  if(uiState == ID_NOMATCH){
353  vRestoreCheckPoints(spCtx, uipCheckPoints);
354  }
355  }
356 }
357 
358 bkr_phrase sBkruFetch(void* vpCtx, aint uiIndex) {
359  backref* spCtx = (backref*) vpCtx;
360  bkr_phrase* spFrame;
361  bkr_phrase sReturn;
362  if (uiIndex < spCtx->spParserCtx->uiRuleCount) {
363 
364  // !!!! DEBUG
365 // aint uiLen = uiVecLen(spCtx->vppPhraseStacks[spCtx->spRules[uiIndex].uiBackRefIndex]);
366 // aint ui;
367 // bkr_phrase* spPhrase = (bkr_phrase*)vpVecFirst(spCtx->vppPhraseStacks[spCtx->spRules[uiIndex].uiBackRefIndex]);
368 // printf("sBkruFetch: phrase frames: %"PRIuMAX"\n", (luint)uiLen);
369 // for(ui = 0; ui < uiLen; ui++, spPhrase++){
370 // printf(" phrase offset: %"PRIuMAX": phrase length: %"PRIuMAX"\n", (luint)spPhrase->uiPhraseOffset, (luint)spPhrase->uiPhraseLength);
371 // }
372  // !!!! DEBUG
373 
374  spFrame = (bkr_phrase*) vpVecLast(spCtx->vppPhraseStacks[spCtx->spRules[uiIndex].uiBackRefIndex]);
375  if (!spFrame) {
376  XTHROW(spCtx->spException, "unexpected empty phrase stack vector");
377  }
378  sReturn.uiPhraseLength = spFrame->uiPhraseLength;
379  sReturn.uiPhraseOffset = spFrame->uiPhraseOffset;
380  } else {
381  spFrame = (bkr_phrase*) vpVecLast(
382  spCtx->vppPhraseStacks[spCtx->spUdts[uiIndex - spCtx->spParserCtx->uiRuleCount].uiBackRefIndex]);
383  if (!spFrame) {
384  XTHROW(spCtx->spException, "unexpected empty phrase stack vector");
385  }
386  sReturn.uiPhraseLength = spFrame->uiPhraseLength;
387  sReturn.uiPhraseOffset = spFrame->uiPhraseOffset;
388  }
389  return sReturn;
390 }
391 
392 static void vSetAllParents(backref* spCtx, bkru_input* spInput) {
393  aint uiLen = uiVecLen(spInput->vpVecStack);
394  if (uiLen) {
395  aint ui = 0;
396  bkru_frame* spBeg = (bkru_frame*) vpVecFirst(spInput->vpVecStack);
397  if (!spBeg) {
398  XTHROW(spCtx->spException, s_cpEmpty);
399  }
400  for (; ui < uiLen; ui += 1) {
401  spBeg[ui].spRule->uiHasBackRef = uiFound;
402  }
403  }
404 }
405 static void vRnmWalk(backref* spCtx, bkru_input* spInput) {
406  bkru_frame* spFrame;
407 // print sPrint;
408  bkr_rule* spRule = spInput->spRule;
409 // sPrint.spRule = spInput->spRule;
410  if (spRule->uiHasBackRef == uiOpen) {
411  if (spRule->uiIsBackRef) {
412  // set all rules on the open frames
413  vSetAllParents(spCtx, spInput);
414 // sPrint.uiDirection = uiInner;
415 // sPrint.uiTreeDepth = uiVecLen(spInput->vpVecStack);
416 // sPrint.uiState = uiIsBkr;
417 // vPrintRule(&sPrint);
418  }
419 // sPrint.uiDirection = uiInner;
420 // sPrint.uiTreeDepth = uiVecLen(spInput->vpVecStack);
421 // sPrint.uiState = uiRecursive;
422 // vPrintRule(&sPrint);
423  } else if (spRule->uiHasBackRef == uiUndefined) {
424  if (spRule->uiIsBackRef) {
425  // set all rules on the open frames
426  vSetAllParents(spCtx, spInput);
427 // sPrint.uiDirection = uiInner;
428 // sPrint.uiTreeDepth = uiVecLen(spInput->vpVecStack);
429 // sPrint.uiState = uiIsBkr;
430 // vPrintRule(&sPrint);
431  }
432 
433 // sPrint.uiDirection = uiDown;
434 // sPrint.uiTreeDepth = uiVecLen(spInput->vpVecStack);
435 // sPrint.uiState = spRule->uiHasBackRef;
436 // vPrintRule(&sPrint);
437 
438  spFrame = (bkru_frame*) vpVecPush(spInput->vpVecStack, NULL);
439  spFrame->spRule = spRule;
440  spInput->spOp = spRule->spRule->spOp;
441  spRule->uiHasBackRef = uiOpen;
442  vOpWalk(spCtx, spInput);
443  if (spRule->uiHasBackRef == uiOpen) {
444  spRule->uiHasBackRef = uiNotFound;
445  }
446  if (!vpVecPop(spInput->vpVecStack)) {
447  longjmp(spInput->aJumpBuf, 1);
448  }
449 
450 // sPrint.uiDirection = uiUp;
451 // sPrint.uiTreeDepth = uiVecLen(spInput->vpVecStack);
452 // sPrint.uiState = spRule->uiHasBackRef;
453 // vPrintRule(&sPrint);
454  } else {
455  if (spRule->uiHasBackRef || spRule->uiIsBackRef) {
456  // set all rules on the open frames
457  vSetAllParents(spCtx, spInput);
458 // sPrint.uiDirection = uiInner;
459 // sPrint.uiTreeDepth = uiVecLen(spInput->vpVecStack);
460 // sPrint.uiState = uiIsBkr;
461 // vPrintRule(&sPrint);
462  }
463  // already know the state
464 // sPrint.uiDirection = uiDown;
465 // sPrint.uiTreeDepth = uiVecLen(spInput->vpVecStack);
466 // sPrint.uiState = spRule->uiHasBackRef;
467 // vPrintRule(&sPrint);
468 // sPrint.uiDirection = uiUp;
469 // vPrintRule(&sPrint);
470  }
471 }
472 static void vAltWalk(backref* spCtx, bkru_input* spInput) {
473  const aint* uipChildBeg = spInput->spOp->sAlt.uipChildList;
474  const aint* uipChildEnd = uipChildBeg + spInput->spOp->sAlt.uiChildCount;
475  for (; uipChildBeg < uipChildEnd; uipChildBeg++) {
476  spInput->spOp = spCtx->spParserCtx->spOpcodes + *uipChildBeg;
477  vOpWalk(spCtx, spInput);
478  }
479 }
480 static void vCatWalk(backref* spCtx, bkru_input* spInput) {
481  const aint* uipChildBeg = spInput->spOp->sCat.uipChildList;
482  const aint* uipChildEnd = uipChildBeg + spInput->spOp->sCat.uiChildCount;
483  for (; uipChildBeg < uipChildEnd; uipChildBeg++) {
484  spInput->spOp = spCtx->spParserCtx->spOpcodes + *uipChildBeg;
485  vOpWalk(spCtx, spInput);
486  }
487 }
488 static void vRepWalk(backref* spCtx, bkru_input* spInput) {
489  spInput->spOp = spInput->spOp + 1;
490  vOpWalk(spCtx, spInput);
491 }
492 static void vOpWalk(backref* spCtx, bkru_input* spInput) {
493  switch (spInput->spOp->sGen.uiId) {
494  case ID_RNM:
495  spInput->spRule = &spCtx->spRules[spInput->spOp->sRnm.spRule->uiRuleIndex];
496  vRnmWalk(spCtx, spInput);
497  break;
498  case ID_UDT:
499  if (spCtx->spUdts[spInput->spOp->sUdt.spUdt->uiUdtIndex].uiIsBackRef) {
500  vSetAllParents(spCtx, spInput);
501  }
502  break;
503  case ID_ALT:
504  vAltWalk(spCtx, spInput);
505  break;
506  case ID_CAT:
507  vCatWalk(spCtx, spInput);
508  break;
509  case ID_REP:
510  vRepWalk(spCtx, spInput);
511  break;
512  default:
513  // all other operators either terminals or empty strings
514  break;
515  }
516 }
517 static void vSESTWalk(backref* spCtx) {
518  aint ui;
519  bkru_input sInput;
520  sInput.vpVecStack = vpVecCtor(spCtx->spParserCtx->vpMem, (aint) sizeof(bkru_frame), 100);
521  if (setjmp(sInput.aJumpBuf) != 0) {
522  vVecDtor(sInput.vpVecStack);
523  XTHROW(spCtx->spException,"internal error - unexpected vpVecPop() error walking the tree");
524  }
525 
526  // walk the SEST of each rule
527  for (ui = 0; ui < spCtx->spParserCtx->uiRuleCount; ui += 1) {
528  sInput.spRule = &spCtx->spRules[ui];
529  if (sInput.spRule->uiHasBackRef == uiUndefined) {
530 // printf("SEST WALK BEGIN: RULE: %s\n", sInput.spRule->spRule->cpRuleName);
531  vRnmWalk(spCtx, &sInput);
532 // printf("SEST WALK END: tree depth: %"PRIuMAX"\n", (luint) uiVecLen(sInput.vpVecStack));
533 // printf("\n");
534  }
535  }
536  vVecDtor(sInput.vpVecStack);
537 }
538 
539 // !!!! DEBUG
540 //static char* cpState(aint uiState) {
541 // if (uiState == uiUndefined) {
542 // return "undefined";
543 // }
544 // if (uiState == uiNotFound) {
545 // return "BKR not found";
546 // }
547 // if (uiState == uiFound) {
548 // return "BKR found";
549 // }
550 // if (uiState == uiOpen) {
551 // return "recursive rule open";
552 // }
553 // if (uiState == uiIsBkr) {
554 // return "rule is back referenced";
555 // }
556 // return "unknown";
557 //}
558 //static void vPrintRule(print* spPrint) {
559 // aint ui = 0;
560 // bkr_rule* spRule = spPrint->spRule;
561 //
562 // // indent
563 // for (; ui < spPrint->uiTreeDepth; ui += 1) {
564 // printf(" ");
565 // }
566 // if (spPrint->uiDirection == uiDown) {
567 // printf("+");
568 // } else if (spPrint->uiDirection == uiUp) {
569 // printf("-");
570 // } else if (spPrint->uiDirection == uiInner) {
571 // printf("=>");
572 // } else {
573 // printf("???");
574 // }
575 // printf("%s: node state: %s: rule uiHasBackRef: %s\n", spRule->spRule->cpRuleName, cpState(spPrint->uiState),
576 // cpState(spRule->uiHasBackRef));
577 //}
578 // !!!! DEBUG
579 #endif /* APG_BKR */
lib.h
This header "#include"s all publid lib headers and other standard headers needed by most objects.
apg.h
The APG header file.
bkru_frame::spRule
bkr_rule * spRule
Definition: backrefu.c:62
ID_RNM
#define ID_RNM
rule name
Definition: parser.h:46
bkr_udt::uiBackRefIndex
aint uiBackRefIndex
If this UDT is back referenced, this is the UDT's index in the bkr map.
Definition: backref.h:56
parserp.h
Private header for the SABNF parser.
vBkruRuleClose
void vBkruRuleClose(void *vpCtx, aint uiIndex, aint uiState, aint uiPhraseOffset, aint uiPhraseLength)
Definition: backrefu.c:295
backref::vpCheckPoints
void * vpCheckPoints
A stack of check points (a check point is the current record count in each of the frame stacks).
Definition: backref.h:79
vVecDtor
void vVecDtor(void *vpCtx)
The vector component destructor.
Definition: vector.c:161
ID_ALT
#define ID_ALT
alternation
Definition: parser.h:43
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
backref::spException
exception * spException
Pointer to the exception structure for reporting fatal errors.
Definition: backref.h:73
bkr_udt::uiIsBackRef
aint uiIsBackRef
APG_TRUE if this UDT has been back referenced in, APG_FALSE otherwise.
Definition: backref.h:55
rule::spOp
const union opcode_tag * spOp
Pointer to the first opcode of the rule.
Definition: parserp.h:122
bkr_phrase::uiPhraseOffset
aint uiPhraseOffset
The offset to the matched phrase.
Definition: backref.h:64
backref::uiBkrCount
aint uiBkrCount
Number of back referenced rules/UDTS.
Definition: backref.h:81
backref::spParserCtx
parser * spParserCtx
Pointer to the parser context that created this object.
Definition: backref.h:74
XTHROW
#define XTHROW(ctx, msg)
Exception throw macro.
Definition: exception.h:67
vpVecPop
void * vpVecPop(void *vpCtx)
Pops one element from the end of the array.
Definition: vector.c:250
vBkruRuleOpen
void vBkruRuleOpen(void *vpCtx, aint uiIndex)
Definition: backrefu.c:282
aint
uint_fast32_t aint
The APG parser's unsigned integer type.
Definition: apg.h:79
vpVecLast
void * vpVecLast(void *vpCtx)
Get the last element one the vector. The vector is not altered.
Definition: vector.c:343
backref.h
Private declarations common to both universal and parent modes.
spMemException
exception * spMemException(void *vpCtx)
Get a pointer to this memory objects's exception handler.
Definition: memory.c:174
ID_CAT
#define ID_CAT
concatenation
Definition: parser.h:44
bkr_udt
Back referencing information for each UDT.
Definition: backref.h:53
vpMemAlloc
void * vpMemAlloc(void *vpCtx, aint uiBytes)
Allocates memory.
Definition: memory.c:196
vBkruOpClose
void vBkruOpClose(void *vpCtx, aint uiState)
Definition: backrefu.c:340
bkr_phrase::uiPhraseLength
aint uiPhraseLength
The matched phrase length.
Definition: backref.h:65
uiVecLen
aint uiVecLen(void *vpCtx)
Get the vector length. That is, the number of elements on the vector.
Definition: vector.c:385
vpVecCtor
void * vpVecCtor(void *vpMem, aint uiElementSize, aint uiInitialAlloc)
The vector object constructor.
Definition: vector.c:118
ID_REP
#define ID_REP
repetition
Definition: parser.h:45
backref::spUdts
bkr_udt * spUdts
Pointer to the back reference UDT information.
Definition: backref.h:76
vMemFree
void vMemFree(void *vpCtx, const void *vpData)
Free memory previously allocated with vpMemAlloc().
Definition: memory.c:226
bkru_frame
Definition: backrefu.c:61
bkru_input::vpVecStack
void * vpVecStack
Definition: backrefu.c:69
bkru_input::spRule
bkr_rule * spRule
Definition: backrefu.c:67
bkr_rule::spRule
rule * spRule
Definition: backref.h:44
ID_MATCH
#define ID_MATCH
indicates a matched phrase parser state on return from parse tree below this node
Definition: parser.h:73
bkru_input
Definition: backrefu.c:65
backref
The back reference object's context.
Definition: backref.h:71
backref::vppPhraseStacks
void ** vppPhraseStacks
An array of frame structs, vector context if rule/UDT index is universally back referenced....
Definition: backref.h:77
APG_UNDEFINED
#define APG_UNDEFINED
Definition: apg.h:318
vpVecFirst
void * vpVecFirst(void *vpCtx)
Get the first element one the vector. The vector is not altered.
Definition: vector.c:326
bkru_input::aJumpBuf
jmp_buf aJumpBuf
Definition: backrefu.c:68
bkr_rule::uiIsBackRef
aint uiIsBackRef
APG_TRUE if this rule has been back referenced, APG_FALSE otherwise.
Definition: backref.h:46
APG_TRUE
#define APG_TRUE
Definition: apg.h:291
vBkruUdtClose
void vBkruUdtClose(void *vpCtx, aint uiIndex, aint uiState, aint uiPhraseOffset, aint uiPhraseLength)
Definition: backrefu.c:320
bkr_phrase
Defines one frame on the back reference stack.
Definition: backref.h:63
bkru_input::spOp
const opcode * spOp
Definition: backrefu.c:66
vpVecPopi
void * vpVecPopi(void *vpCtx, aint uiIndex)
Pops the element at the given zero-based index and all higher indexes.
Definition: vector.c:306
ID_NOMATCH
#define ID_NOMATCH
indicates that no phrase was matched on return from parse tree below this node
Definition: parser.h:74
bkr_rule::uiBackRefIndex
aint uiBackRefIndex
If this rule is back referenced, this is the rule's index in the bkr map.
Definition: backref.h:47
bkr_rule::uiHasBackRef
aint uiHasBackRef
APG_TRUE if this rule refers to a referenced rule in it syntax tree, APG_FALSE otherwise.
Definition: backref.h:45
vpBkruCtor
void * vpBkruCtor(parser *spParserCtx)
Definition: backrefu.c:100
vBkruOpOpen
void vBkruOpOpen(void *vpCtx)
Definition: backrefu.c:327
bkr_rule
Back referencing information for each rule.
Definition: backref.h:43
sBkruFetch
bkr_phrase sBkruFetch(void *vpCtx, aint uiIndex)
Definition: backrefu.c:358
backrefu.h
The universal-mode back reference object.
ID_BKR_MODE_U
#define ID_BKR_MODE_U
the back reference is universal mode
Definition: parser.h:118
vpVecPush
void * vpVecPush(void *vpCtx, void *vpElement)
Adds one element to the end of the array.
Definition: vector.c:193
backref::spRules
bkr_rule * spRules
Pointer to the back reference rule information.
Definition: backref.h:75
backref::vpOpenRules
void * vpOpenRules
A stack indicating if the top rule has a BKR in its syntax tree.
Definition: backref.h:80
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.