/************************************************************************/
/* */
/* TblDisp -- Describe state tables in concise, readable format */
/* */
/* This module presents the state tables created for a */
/* search in a human-readable format. This is useful for */
/* understanding, debugging and testing the software. */
/* */
/* TblDisp was created very late in the development -- */
/* over two years after the project started. It has */
/* quickly become the main tool for measuring the program's */
/* implementation of the RE, and has highlighted a number */
/* of (minor) cases where the search could be optimised */
/* further. */
/* */
/* Copyright (C) 1995-2000 Grouse Software. All rights reserved. */
/* Written for Grouse by behoffski (Brenton Hoff). */
/* */
/* Free software: no warranty; use anywhere is ok; spread the */
/* sources; note any mods; share variations and derivatives */
/* (including sending to behoffski@grouse.com.au). */
/* */
/************************************************************************/
#include "bakslash.h"
#include "compdef.h"
#include <string.h>
#include <stdio.h>
#include "tbldisp.h"
/*Summary of action entries for Description*/
typedef struct {
MatchEng_Action Code;
UINT8 NrEntries;
WORD RangeSpecs[MATCHENG_TABLE_SIZE / 2];
} ActionDescription;
/*Table of action entries to complete the description for each state*/
typedef struct {
UINT NrActions;
ActionDescription Action[MATCHENG_ACTIONS_MAX];
} TableDescription;
/*List of action codes and labels*/
typedef struct {
MatchEng_Action Code;
CHAR *pDesc;
} ActionLabelItem;
module_scope ActionLabelItem gTblDisp_Labels[MATCHENG_ACTIONS_MAX];
/************************************************************************/
/* */
/* PrepareLabels -- Set up labels used for table display */
/* */
/* Since GCC uses run-time values for the state machine */
/* action coding, the previous static array has been replaced */
/* by a dynamic array that must be initialised once the */
/* actual values are known. This function sets up the array. */
/* */
/************************************************************************/
public_scope void
TblDisp_PrepareLabels(void)
{
ActionLabelItem *pLabel = &gTblDisp_Labels[0];
/*Actions for start-match state*/
pLabel->Code = SKIP_MAX;
pLabel->pDesc = "SkipMax";
pLabel++;
pLabel->Code = SKIP17;
pLabel->pDesc = "Skip17";
pLabel++;
pLabel->Code = SKIP16;
pLabel->pDesc = "Skip16";
pLabel++;
pLabel->Code = SKIP15;
pLabel->pDesc = "Skip15";
pLabel++;
pLabel->Code = SKIP14;
pLabel->pDesc = "Skip14";
pLabel++;
pLabel->Code = SKIP13;
pLabel->pDesc = "Skip13";
pLabel++;
pLabel->Code = SKIP12;
pLabel->pDesc = "Skip12";
pLabel++;
pLabel->Code = SKIP11;
pLabel->pDesc = "Skip11";
pLabel++;
pLabel->Code = SKIP10;
pLabel->pDesc = "Skip10";
pLabel++;
pLabel->Code = SKIP9;
pLabel->pDesc = "Skip9";
pLabel++;
pLabel->Code = SKIP8;
pLabel->pDesc = "Skip8";
pLabel++;
pLabel->Code = SKIP7;
pLabel->pDesc = "Skip7";
pLabel++;
pLabel->Code = SKIP6;
pLabel->pDesc = "Skip6";
pLabel++;
pLabel->Code = SKIP5;
pLabel->pDesc = "Skip5";
pLabel++;
pLabel->Code = SKIP4;
pLabel->pDesc = "Skip4";
pLabel++;
pLabel->Code = SKIP3;
pLabel->pDesc = "Skip3";
pLabel++;
pLabel->Code = SKIP2;
pLabel->pDesc = "Skip2";
pLabel++;
pLabel->Code = AGAIN;
pLabel->pDesc = "Again";
pLabel++;
pLabel->Code = BYTE_SEARCH;
pLabel->pDesc = "ByteSearch";
pLabel++;
pLabel->Code = START_MATCH_PUSH;
pLabel->pDesc = "StartMatchPush";
pLabel++;
pLabel->Code = START_MATCH_PUSH_ADVANCE;
pLabel->pDesc = "StartMatchPushAdvance";
pLabel++;
pLabel->Code = START_OFFSET_MATCH;
pLabel->pDesc = "StartOffsetMatch";
pLabel++;
pLabel->Code = NOTE_LINE;
pLabel->pDesc = "NoteLine";
pLabel++;
pLabel->Code = NOTE_LINE_START_PUSH;
pLabel->pDesc = "NoteLineStartPush";
pLabel++;
pLabel->Code = END_OF_LINE_SEARCH;
pLabel->pDesc = "EOLSearch";
pLabel++;
pLabel->Code = END_OF_LINE_MATCH;
pLabel->pDesc = "EOLMatch";
pLabel++;
pLabel->Code = START_OF_LINE_SEARCH;
pLabel->pDesc = "StartOfLineSearch";
pLabel++;
pLabel->Code = FOUND_LINE_START;
pLabel->pDesc = "FoundLineStart";
pLabel++;
pLabel->Code = INC_LINE_COUNT;
pLabel->pDesc = "IncLineCount";
pLabel++;
/*Actions that advance the match*/
pLabel->Code = ADVANCE;
pLabel->pDesc = "Advance";
pLabel++;
pLabel->Code = AGAIN_PUSH_ADVANCE;
pLabel->pDesc = "AgainPushAdvance";
pLabel++;
pLabel->Code = BACK_AND_ADVANCE;
pLabel->pDesc = "BackAndAdvance";
pLabel++;
pLabel->Code = ADVANCE_PUSH_ZERO;
pLabel->pDesc = "AdvancePushZero";
pLabel++;
/*Actions that complete search*/
pLabel->Code = COMPLETED;
pLabel->pDesc = "Completed";
pLabel++;
/*Meta-match actions (test text but don't add to match length)*/
pLabel->Code = PREV_NONWORD;
pLabel->pDesc = "PrevNonword";
pLabel++;
pLabel->Code = PREV_WORD;
pLabel->pDesc = "PrevWord";
pLabel++;
/*Entries that don't match*/
pLabel->Code = NO_MATCH;
pLabel->pDesc = "NoMatch";
pLabel++;
pLabel->Code = ABANDON;
pLabel->pDesc = "Abandon";
pLabel++;
/*End-of-buffer handling actions*/
pLabel->Code = CHECK_BUFFER;
pLabel->pDesc = "CheckBuffer";
pLabel++;
/*And finally, action reserved for future special effects*/
pLabel->Code = SPECIAL;
pLabel->pDesc = "Special";
pLabel++;
pLabel->Code = (MatchEng_Action) NULL;
pLabel->pDesc = NULL;
} /*PrepareLabels*/
/************************************************************************/
/* */
/* DispFlag -- Report table summary described by flag variable */
/* */
/************************************************************************/
module_scope void
TblDisp_DispFlag(MatchEng_TableFlags Flag)
{
UINT TableType;
/*Display flag summary*/
TableType = MATCHENG_TABLE_TYPE_R(Flag);
switch (TableType) {
case MATCHENG_TABLE_TYPE_FAIL:
fprintf(stdout, "Fail");
break;
case MATCHENG_TABLE_TYPE_START:
fprintf(stdout, "Start");
break;
case MATCHENG_TABLE_TYPE_LITERAL:
fprintf(stdout, "Literal");
break;
case MATCHENG_TABLE_TYPE_CLASS:
fprintf(stdout, "Class");
break;
case MATCHENG_TABLE_TYPE_ALL_BUT:
fprintf(stdout, "AllBut");
break;
case MATCHENG_TABLE_TYPE_MATCH_ANY:
fprintf(stdout, "MatchAny");
break;
case MATCHENG_TABLE_TYPE_SUCCESS:
fprintf(stdout, "Success");
break;
case MATCHENG_TABLE_TYPE_START_LINE:
fprintf(stdout, "StartLine");
break;
case MATCHENG_TABLE_TYPE_WORD_BEGINNING:
fprintf(stdout, "WordBeginning");
break;
case MATCHENG_TABLE_TYPE_WORD_END:
fprintf(stdout, "WordEnd");
break;
case MATCHENG_TABLE_TYPE_WORD_BOUNDARY:
fprintf(stdout, "WordBoundary");
break;
case MATCHENG_TABLE_TYPE_WORD_NONBOUNDARY:
fprintf(stdout, "WordNonboundary");
break;
case MATCHENG_TABLE_TYPE_PREV_NONWORD:
fprintf(stdout, "PrevNonword");
break;
case MATCHENG_TABLE_TYPE_SUCCESS_WORD_END:
fprintf(stdout, "SuccessWordEnd");
break;
case MATCHENG_TABLE_TYPE_DEAD_END:
fprintf(stdout, "DeadEnd");
break;
default:
fprintf(stdout, "?? unknown type: 0x%02x", TableType);
break;
}
/*Report options included in flag*/
if (Flag & MATCHENG_TABLE_ITERATIVE) {
fprintf(stdout, "+iter");
}
if (Flag & MATCHENG_TABLE_ZERO_TRIP) {
fprintf(stdout, "+0trip");
}
if (Flag & MATCHENG_TABLE_WIDTH_META) {
fprintf(stdout, "+meta");
}
} /*DispFlag*/
/************************************************************************/
/* */
/* ActionSummary -- Display summary of entries matching action */
/* */
/* If the action named here is present in the description */
/* table, the bytes matching the action are displayed. */
/* C-style escapes are used to describe nonprinting values. */
/* */
/************************************************************************/
module_scope void
TblDisp_ActionSummary(MatchEng_Action Code,
CHAR *pLabel,
TableDescription *pDesc)
{
ActionDescription *pAct;
ActionDescription *pEnd;
UINT Range;
BYTE High;
BYTE Low;
UINT TextLen;
CHAR Encoding[8];
/*Search for code within description table*/
pEnd = &pDesc->Action[pDesc->NrActions];
pAct = &pDesc->Action[0];
for (;;) {
/*Have we exhausted the list?*/
if (pAct == pEnd) {
/*Yes, code isn't present in list*/
return;
}
/*Have we found an entry for this code?*/
if (pAct->Code == Code) {
/*Yes, found entry*/
break;
}
/*Move to the next action, if any*/
pAct++;
}
/*Found entry, report it*/
TextLen = 20;
fprintf(stdout, "%s: ", pLabel);
if (strlen(pLabel) < 18) {
/*Pad label to improve alignment of reports*/
fprintf(stdout, "%*s", 18 - strlen(pLabel), "");
} else {
/*Keep track of line length*/
TextLen += strlen(pLabel) + 2;
}
for (Range = 0; Range < pAct->NrEntries; Range++) {
/*Do we have space for the next entry?*/
if (TextLen > 66) {
/*Possibly not... move to a new line*/
fprintf(stdout, "\n%28s", "");
TextLen = 29;
}
/*Report entry as one of "'a'", "'a', 'b'" or "'a'-'b'"*/
High = HIBYTE(pAct->RangeSpecs[Range]);
Low = LOBYTE(pAct->RangeSpecs[Range]);
if (High == Low) {
/*Range represents a single item*/
Bakslash_EncodeByte(Low, Encoding);
TextLen += fprintf(stdout, "'%s'", Encoding);
} else if (High == (Low + 1)) {
Bakslash_EncodeByte(Low, Encoding);
TextLen += fprintf(stdout, "'%s', ", Encoding);
Bakslash_EncodeByte(High, Encoding);
TextLen += fprintf(stdout, "'%s'", Encoding);
} else if ((High == 0x00) && (Low == 0xff)) {
/*Dummy entry signalling endmarker value*/
TextLen += fprintf(stdout, "Endmarker");
} else if ((High == 0x00) && (Low == 0xfe)) {
/*Dummy entry signalling endmarker value*/
TextLen += fprintf(stdout, "NotEndmarker");
} else {
Bakslash_EncodeByte(Low, Encoding);
TextLen += fprintf(stdout, "'%s'-", Encoding);
Bakslash_EncodeByte(High, Encoding);
TextLen += fprintf(stdout, "'%s'", Encoding);
}
/*Add delimiter if not at the end of the list*/
if ((Range + 1) < pAct->NrEntries) {
TextLen += fprintf(stdout, ", ");
}
}
fprintf(stdout, "\n");
} /*ActionSummary*/
/************************************************************************/
/* */
/* DescribeTable -- Generate readable description of a table */
/* */
/* The description is built by organising the entries by */
/* action code, and by identifying ranges within each action. */
/* The result is a table with variable-length rows: each row */
/* describes an action, and the entries in each row describe */
/* ranges of characters within the rows. */
/* */
/************************************************************************/
module_scope void
TblDisp_DescribeTable(MatchEng_Action *pTab,
MatchEng_Action Endmarker,
MatchEng_Action NotEndmarker)
{
TableDescription Desc;
ActionDescription *pAction;
ActionDescription *pAfterLastAction;
UINT i;
MatchEng_Action Act;
WORD *pRange;
ActionLabelItem *pItem;
BOOL EndmarkerUsed = FALSE;
/*Initialise all description entries to 0*/
memset(&Desc, 0, sizeof(Desc));
/*Work through each entry of table, recording action occurrences*/
for (i = 0; i < 256; i++) {
Act = *pTab++;
pAction = &Desc.Action[0];
pAfterLastAction = &Desc.Action[Desc.NrActions];
for (;;) {
/*Have we run out of actions?*/
if (pAction == pAfterLastAction) {
/*Yes, need to create a new entry*/
Desc.NrActions++;
break;
}
/*Have we found the action?*/
if (Act == pAction->Code) {
/*Yes, finish search with desired entry*/
break;
}
/*Next entry, if any*/
pAction++;
}
/*Is this the first entry for this description?*/
pRange = &pAction->RangeSpecs[pAction->NrEntries - 1];
if (pAction->NrEntries == 0) {
/*Yes, create the first entry now*/
pAction->Code = Act;
pAction->NrEntries = 1;
*++pRange = BYTES2WORD(i, i);
if (Act == CHECK_BUFFER) {
EndmarkerUsed = TRUE;
}
continue;
}
/*Does this entry extend the last range?*/
if ((i - 1) == HIBYTE(*pRange)) {
/*Yes, merely extend range*/
*pRange = BYTES2WORD(i, LOBYTE(*pRange));
continue;
}
/*Need to add another range to action's description*/
pAction->Code = Act;
pAction->NrEntries++;
*++pRange = BYTES2WORD(i, i);
}
/*Only describe endmarkers/notendmarkers if relevant*/
if (EndmarkerUsed) {
/*Add endmarker using range (high, low) of (0x00, 0xff)*/
pAction = &Desc.Action[0];
pAfterLastAction = &Desc.Action[Desc.NrActions];
for (;;) {
/*Have we run out of actions?*/
if (pAction == pAfterLastAction) {
/*Yes, need to create a new entry*/
Desc.NrActions++;
pAction->Code = Endmarker;
pAction->NrEntries = 1;
pAction->RangeSpecs[0] =
BYTES2WORD(0x00, 0xff);
break;
}
/*Have we found the action?*/
if (Endmarker == pAction->Code) {
/*Yes, add entry signifying endmarker*/
pAction->RangeSpecs[pAction->NrEntries] =
BYTES2WORD(0x00, 0xff);
pAction->NrEntries++;
break;
}
/*Next entry, if any*/
pAction++;
}
/*Add notendmarker using special range of (0x00, 0xfe)*/
pAction = &Desc.Action[0];
pAfterLastAction = &Desc.Action[Desc.NrActions];
for (;;) {
/*Have we run out of actions?*/
if (pAction == pAfterLastAction) {
/*Yes, need to create a new entry*/
Desc.NrActions++;
pAction->Code = NotEndmarker;
pAction->NrEntries = 1;
pAction->RangeSpecs[0] =
BYTES2WORD(0x00, 0xfe);
break;
}
/*Have we found the action?*/
if (NotEndmarker == pAction->Code) {
/*Yes, add entry signifying endmarker*/
pAction->RangeSpecs[pAction->NrEntries] =
BYTES2WORD(0x00, 0xfe);
pAction->NrEntries++;
break;
}
/*Next entry, if any*/
pAction++;
}
}
/*Report table entries in fairly coherent order*/
for (pItem = &gTblDisp_Labels[0]; pItem->pDesc != NULL; pItem++) {
TblDisp_ActionSummary(pItem->Code, pItem->pDesc, &Desc);
}
} /*DescribeTable*/
/************************************************************************/
/* */
/* Describe -- Report state tables in coherent fashion */
/* */
/* This routine is springing into existence as part of the */
/* white-box testing of the system. It describes each state */
/* table in concise but readable format. This output is */
/* checked by part of the automated test rig, so don't */
/* change this routine unless you're willing to update the */
/* tests. */
/* */
/************************************************************************/
public_scope void
TblDisp_Describe(MatchEng_Spec *pSpec, CHAR *pTitle)
{
MatchEng_Action *pTab = pSpec->pTables;
MatchEng_TableFlags *pFlags = pSpec->pTableFlags;
UINT TableType;
UINT TableNr = 0;
/*Display the title for this specification*/
fprintf(stdout, "\n========== %s ==========\n", pTitle);
/*Work through each table of the spec in turn*/
for (;;) {
fprintf(stdout, "[Table %u, ", TableNr);
TblDisp_DispFlag(*pFlags);
fprintf(stdout, "]\n");
/*Generate the description for this table*/
TblDisp_DescribeTable(pTab,
pSpec->pEndmarkerActions[TableNr],
pSpec->pNotEndmarkerActions[TableNr]);
fprintf(stdout, "\n");
/*Was that the final table?*/
TableType = MATCHENG_TABLE_TYPE_R(*pFlags++);
if ((TableType == MATCHENG_TABLE_TYPE_SUCCESS) ||
(TableType == MATCHENG_TABLE_TYPE_SUCCESS_WORD_END)) {
/*Yes, finished displaying*/
break;
}
/*Move to the next table*/
pTab += MATCHENG_TABLE_SIZE;
TableNr++;
}
} /*Describe*/
/************************************************************************/
/* */
/* Start -- Begin managing what has to be managed */
/* */
/************************************************************************/
public_scope BOOL
TblDisp_Start(void)
{
/*Started successfully*/
return TRUE;
} /*Start*/
/************************************************************************/
/* */
/* Init -- Prepare module for operation */
/* */
/************************************************************************/
public_scope void
TblDisp_Init(void)
{
} /*Init*/