e93/e93/syntax.c

// Syntax highlighting functions
// Copyright (C) 2000 Core Technologies.

// This file is part of e93.
//
// e93 is free software; you can redistribute it and/or modify
// it under the terms of the e93 LICENSE AGREEMENT.
//
// e93 is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// e93 LICENSE AGREEMENT for more details.
//
// You should have received a copy of the e93 LICENSE AGREEMENT
// along with e93; see the file "LICENSE.TXT".

// Overview of how e93 performs syntax highlighting:
//
// Syntax highlighting is the process of looking at the text, searching
// for patterns, and highlighting those patterns by changing color,
// font, or style. Most editors which perform syntax highlighting have
// built-in rules for what to search for. By having built in rules,
// an editor can search out the syntax efficiently, and
// reduce the complexity of the process, but it limits the user from
// modifying rules or adding new ones. A problem occurs when one tries to
// generalize the rule definition process so that users can define their
// own -- things slow down.
//
// e93 has always been meant as a generalized text editor, not a 'C' editor.
// Because of this, syntax highlighting must be generalized so that
// users can create their own rules for whatever they might be editing.
//
// Syntax rules are given in the form of 1 or more regular expressions.
// The first regular expression is called the "start" expression, and the
// second (possibly empty) set of expressions are called the "end"
// expressions.

// If only a start expression is defined, e93 matches it, and applies
// a defined style to the text wherever it matches.
// If both start and end expressions are defined, e93 matches the
// start, then matches the nearest end. The start match has a style associated
// with it, the area between the start and end has a style associated
// with it, and the end expression has a style associated with it.
// So far, so good...
//
// Of course this method of highlighting has some limitations.
// For instance, one cannot define a set of keywords which are
// highlighted only inside parenthesis. To overcome this limitation,
// e93 allows for rules to be defined which are only active during
// the match of other rules (nested rules).
// So, you could define a rule with a start expression of
// open parenthesis, an end expression of close parenthesis. Then
// you could define a rule to match certain keywords, and tell e93
// that this rule only applies between the start and end parenthesis.
// This nesting of rules is allowed to occur to an arbitrary depth.

// Now, the only problem is getting e93 to do all of this without
// bringing the editor to a complete crawl on a 600MHz machine.
// Here's how that works:
// For every expression that is defined for a given syntax
// highlighting ruleset, e93 matches ALL occurrences of that expression
// and keeps them cached.
// When the text is changed, e93 uses information it has about the
// expression to limit how much searching it needs to perform to update
// the caches.
// The syntax highlighting rules use these expression-match caches
// to work out which rule is in effect, and when. These rules also
// cache their state, and attempt to update as little as possible with
// each change.

// Because of all the caching, and complexity caused by this solution,
// the number of data structures is getting out of hand.
// This might help clear things up:

// A SYNTAX_MAP is a data structure that contains all the information needed
// to look at the syntax of a document, and convert it to style information
// which will be applied to the document. It holds a set of compiled regular
// expressions, and a mapping which tells how these expressions are converted
// into style information.

// A SYNTAX_EXPRESSION data structure holds a compiled regular expression
// which is going to be matched against the text of the document.

// A SYNTAX_STYLE_MAPPING data structure describes the relationship between
// a set of matched regular expressions, and which styles should
// be applied to the text when they match. Each SYNTAX_STYLE_MAPPING points
// to a regular expression which needs to be matched at the start,
// and an optional regular expression which needs to be matched at the
// end. It then describes which styles should be applied to the text
// for the starting match, the text between the matches, and the text
// of the ending match.
// SYNTAX_STYLE_MAPPINGs also describe which nested SYNTAX_STYLE_MAPPINGs should
// be active between matches. This allows for recursive mappings (eg. inside
// a set of parenthesis, one could search for a set of keywords).

// A SYNTAX_STYLE_MAPPING_LIST structure is nothing more than a container for a list
// of SYNTAX_STYLE_MAPPINGs

// This is really not all that confusing, but the terminology could use
// some work.

#include	"includes.h"

typedef struct expressionPiece
{
	struct syntaxExpression
		*parent;					// pointer to the expression that this is a piece of
	UINT32
		pieceIndex;					// index of this piece within the entire list of pieces used in the mapping (used to index array defined below)
	bool
		useRegisterMatch;			// tells if entire expression matches, or a register matches
	UINT32
		registerIndex;				// if useRegisterMatch is true, this gives the register index of the match
	struct expressionPiece
		*prev,
		*next;						// used to link the list of pieces together
} EXPRESSION_PIECE;

typedef struct expressionPieceList	// used to create arbitrary lists of expression pieces
{
	EXPRESSION_PIECE
		*piece;						// pointer to the piece given by this list entry
	struct expressionPieceList
		*prev,
		*next;						// used to link the list of pieces together
} EXPRESSION_PIECE_LIST;

typedef struct syntaxExpression		// keeps named expression
{
	struct syntaxMap
		*parent;					// pointer to the map this is part of
	COMPILED_EXPRESSION
		*compiledExpression;		// compiled regular expression
	struct syntaxExpression
		*prev,
		*next;						// pointer to next expression
	EXPRESSION_PIECE
		*firstPiece;				// pointer to list of pieces of this expression which are being mapped
	char
		expressionName[1];			// variable length array, name of this expression
} SYNTAX_EXPRESSION;

typedef struct syntaxStyleMapping	// describes relationship between expressions and styles
{
	struct syntaxMap
		*parent;					// pointer to the map this is part of
	EXPRESSION_PIECE
		*startExpressionPiece;		// expression piece which starts this style
	EXPRESSION_PIECE_LIST
		*endExpressionPieces;		// expression pieces which may end this style (NULL if style is begun and ended with startExpressionPiece)
	UINT32
		startStyle,					// style index used when matching startExpressionPiece
		betweenStyle,				// style index to use between start and end expressions (used only if endExpressionPieces are defined)
		endStyle;					// style index used when matching one of the endExpressionPieces (used only if endExpressionPieces are defined)
	struct syntaxStyleMappingList
		*betweenList;				// list of style maps which are active between the match of startExpressionPiece and the match of endExpressionPieces (used only if endExpressionPieces are defined)

	struct syntaxStyleMapping		// links together all the syntax style mappings for the given syntax map
		*prev,
		*next;
	char
		mappingName[1];				// variable length array, name of this mapping
} SYNTAX_STYLE_MAPPING;

typedef struct syntaxStyleMappingList	// these are used to link together lists of pointers to SYNTAXSTYLEMAPs which are active at any given time
{
	SYNTAX_STYLE_MAPPING
		*mappingEntry;				// pointer to map entry for this list element
	struct syntaxStyleMappingList
		*prev,
		*next;
} SYNTAX_STYLE_MAPPING_LIST;

typedef struct syntaxMap
{
	UINT32
		numExpressionPieces;		// number of pieces contained in the map
	SYNTAX_EXPRESSION
		*firstExpression;			// pointer to head of list of expressions for this map
	SYNTAX_STYLE_MAPPING
		*firstStyleMapping;			// pointer to the entire list of syntax style maps for this map
	struct syntaxInstance
		*firstInstance;				// first instance of this map
	SYNTAX_STYLE_MAPPING_LIST
		*rootMapList;				// list of syntax style maps which are active at the root
	struct syntaxMap
		*prev,						// pointer to the previous syntax map in the global list
		*next;						// pointer to the next syntax map in the global list
	char
		mapName[1];					// variable length array, name of this map
} SYNTAX_MAP;


// Each editor universe which performs syntax highlighting, is assigned a
// SYNTAX_INSTANCE. The SYNTAX_INSTANCE is used to maintain syntax
// highlighting cache information which is specific to the editor
// universe.
// This information includes the cached array of which expressions
// matched where in the text, and the cached state of the syntax coloring
// state machine. This is kept separate from the SYNTAX_MAP, since that
// definition is used across all editor universes which require it.

typedef struct styleElement
{
	SPARSE_ARRAY_HEADER
		saHeader;					// header needed for sparse array functions
	UINT32
		offset,						// offset to start of piece within match
		length;						// number of characters that were matched by the piece
} EXPRESSION_MATCH_ELEMENT;

typedef struct expressionPieceInstance	// used to keep track of matches to an expression for a given editor universe
{
	EXPRESSION_PIECE
		*expressionPiece;
	UINT32
		maximumStartDistance;		// tells maximum distance from start we have ever witnessed, use to tell how far back searches for this expression must begin
	SPARSE_ARRAY
		matchArray;
} EXPRESSION_PIECE_INSTANCE;

// For the outermost level of syntax highlighting rules, there is a table which is maintained
// by the syntax highlighting state machine that tells which mapping is in effect
// for which section of text.
// This table is used to keep from having to search all the expression matches, and
// rebuild the entire style table with each change to the text.
// When a change to the text occurs, this table is consulted to determine the
// range of style changes which will be required to get back in sync with what
// existed before.
typedef struct mappingElement
{
	SPARSE_ARRAY_HEADER
		saHeader;					// header needed for sparse array functions
	SYNTAX_STYLE_MAPPING
		*mapping;					// pointer to the mapping which matches at the root level
} MAPPING_ELEMENT;

typedef struct syntaxInstance
{
	SYNTAX_MAP
		*parentMap;					// map this instance is based on
	EDITOR_BUFFER
		*buffer;					// pointer to the buffer that this instance belongs to
	struct syntaxInstance
		*prev,						// doubly linked list of all instances on the parent map (so parent can traverse all instances linked to it)
		*next;
	SPARSE_ARRAY
		mappingArray;				// used to keep track of mappings at the root level
	EXPRESSION_PIECE_INSTANCE
		expressionPieces[1];		// variable length array of expression piece instance structures (one for each piece of an expression in the syntax map)
} SYNTAX_INSTANCE;


static SYNTAX_MAP
	*syntaxMapHead,					// head of global list of syntax maps
	*syntaxMapTail;

enum
{
	MAP_EXISTS,
	EXPRESSION_EXISTS,
	STYLE_MAPPING_EXISTS,
	LIST_MAPPING_EXISTS,
	EXPRESSION_PIECE_EXISTS
};

static const char *errorDescriptions[]=
{
	"Syntax map already exists",
	"Expression already exists",
	"Style mapping already exists",
	"List element already exists",
	"Expression piece already exists",
};


static bool DeleteOverlappingMatches(EXPRESSION_PIECE_INSTANCE *pieceInstance,UINT32 startOffset,UINT32 endOffset,UINT32 numBytes,UINT32 numBack)
// The text has changed between startOffset and endOffset for numBytes
// Call this to delete any matches that overlapped this area,
// and to adjust all those beyond this area
// numBack tells how far back we need to go when re-evaluating expressions
// this routine deletes all previous matches which begin that far back off the startOffset
{
	DeleteSARange(&pieceInstance->matchArray,startOffset-numBack,endOffset-startOffset+numBack);	// this cannot fail
	return(InsertSARange(&pieceInstance->matchArray,startOffset-numBack,numBytes+numBack));
}

static bool UpdateExpressionCaches(CHUNK_HEADER *chunk,UINT32 offset,SYNTAX_INSTANCE *instance,SYNTAX_EXPRESSION *expression,UINT32 startOffset,UINT32 endOffset,UINT32 numBytes,UINT32 totalBytes,UINT32 *earliestExpressonChange)
// text in textUniverse has changed between startOffset and endOffset for numBytes
// run through and search the text to update the cached set of matches
// NOTE: chunk could be NULL if there is no text in the universe
{
	CHUNK_HEADER
		*newChunk,
		*outChunk;
	UINT32
		newOffset,
		outOffset;
	UINT32
		numBack;
	bool
		fail;
	bool
		found;
	UINT32
		count;
	UINT32
		i;
	UINT32
		matchOffset;
	EXPRESSION_MATCH_ELEMENT
		newElement;
	EXPRESSION_PIECE
		*piece;

	fail=false;
	if(expression->firstPiece)	// do not bother to do anything here if there are no pieces
	{
		REHuntBackToFarthestPossibleStart(chunk,offset,expression->compiledExpression,&numBack,&newChunk,&newOffset);

		if(startOffset-numBack<*earliestExpressonChange)
		{
			*earliestExpressonChange=(startOffset-numBack);
		}

		piece=expression->firstPiece;
		while(piece&&!fail)
		{
			fail=!DeleteOverlappingMatches(&instance->expressionPieces[piece->pieceIndex],startOffset,endOffset,numBytes,numBack);	// adjust pieces for the change
			piece=piece->next;
		}

		i=startOffset-numBack;
		found=true;
		while(!fail&&found&&(i<=startOffset+numBytes))
		{
			if(SearchForwardRE(newChunk,newOffset,expression->compiledExpression,i==0,true,startOffset+numBytes-i,totalBytes-i,false,&found,&matchOffset,&count,&newChunk,&newOffset,&outChunk,&outOffset,NULL))
			{
				if(found)
				{
					piece=expression->firstPiece;					// update all the pieces
					while(piece&&!fail)
					{
						if(!piece->useRegisterMatch)
						{
							newElement.offset=0;
							newElement.length=count;
							fail=!SetSARange(&instance->expressionPieces[piece->pieceIndex].matchArray,i+matchOffset,1,&newElement);	// add this in
						}
						else
						{
							if(GetRERegisterMatch(expression->compiledExpression,piece->registerIndex,&newElement.offset,&newElement.length))
							{
								fail=!SetSARange(&instance->expressionPieces[piece->pieceIndex].matchArray,i+matchOffset,1,&newElement);	// add this in

								if(newElement.offset>instance->expressionPieces[piece->pieceIndex].maximumStartDistance)
								{
//									fprintf(stderr,"%s: %d\n",instance->expressionPieces[piece->pieceIndex].expressionPiece->parent->expressionName,newElement.offset);
									instance->expressionPieces[piece->pieceIndex].maximumStartDistance=newElement.offset;	// keep track of largest offset here
								}
							}
						}
						piece=piece->next;
					}

					i+=matchOffset+1;								// skip to spot just after this one
					if(i<=startOffset+numBytes)						// see if we should adjust the chunk
					{
						if((++newOffset)>=newChunk->totalBytes)		// move forward in the input 1 step
						{
							newChunk=newChunk->nextHeader;
							newOffset=0;
						}
					}
				}
			}
			else
			{
				fail=true;
			}
		}
	}
	return(!fail);
}

static bool AdjustMappingTableForChange(SYNTAX_INSTANCE *instance,UINT32 startOffset,UINT32 endOffset,UINT32 numBytes)
// run through the mapping table, and reduce or expand as needed to account
// for the text change
{
	DeleteSARange(&instance->mappingArray,startOffset,endOffset-startOffset);	// this cannot fail
	return(InsertSARange(&instance->mappingArray,startOffset,numBytes));
}

static bool LocatePieceWithOffset(EXPRESSION_PIECE_INSTANCE *instance,UINT32 position,UINT32 *startPosition,UINT32 *length)
// Locate the nearest expression match which is >= position for the given instance
// If there is none, return false
{
	UINT32
		currentPosition;
	UINT32
		numElements;
	EXPRESSION_MATCH_ELEMENT
		*matchElement;
	bool
		done,
		found;

	found=false;
	if(instance->maximumStartDistance)				// see if this piece uses start offsets at all (if not, the search can go faster)
	{
		if(position>instance->maximumStartDistance)
		{
			currentPosition=position-instance->maximumStartDistance;
		}
		else
		{
			currentPosition=0;
		}
		done=false;
		while((currentPosition<=position)&&!done)
		{
			if(GetSARecordAtOrAfterPosition(&instance->matchArray,currentPosition,startPosition,&numElements,(void **)(&matchElement)))
			{
				*startPosition+=matchElement->offset;
				if(*startPosition>=position)
				{
					*length=matchElement->length;
					done=found=true;
				}
				else
				{
					currentPosition++;
				}
			}
			else
			{
				done=true;							// no more matches
			}
		}
	}
	else											// search the fast way
	{
		if(GetSARecordAtOrAfterPosition(&instance->matchArray,position,startPosition,&numElements,(void **)(&matchElement)))
		{
			*length=matchElement->length;
			found=true;
		}
	}
	return(found);
}

static SYNTAX_STYLE_MAPPING *FindStartPossiblesOrEnd(SYNTAX_INSTANCE *instance,SYNTAX_STYLE_MAPPING_LIST *possibles,SYNTAX_STYLE_MAPPING *endMapping,UINT32 position,UINT32 *matchPosition,UINT32 *matchLength,bool *wasEnd)
// given a position in the text, and a list of rules to match against, see if we can find a match
// for any starting expression of any of the rules
// if so, return the matched rule, position and length
// if nothing matches, return NULL
// NOTE: if none of the starting expressions match at or before the
// next end expression match, return that
{
	UINT32
		pieceIndex;
	UINT32
		startPosition,
		length;
	UINT32
		bestStartPosition,
		bestLength;
	SYNTAX_STYLE_MAPPING
		*bestPossible;
	EXPRESSION_PIECE_LIST
		*pieceListElement;

	bestStartPosition=bestLength=0;
	bestPossible=NULL;
	*wasEnd=false;

	while(possibles)
	{
		pieceIndex=possibles->mappingEntry->startExpressionPiece->pieceIndex;

		if(LocatePieceWithOffset(&instance->expressionPieces[pieceIndex],position,&startPosition,&length))
		{
			if(!bestPossible||startPosition<bestStartPosition)
			{
				bestPossible=possibles->mappingEntry;
				bestStartPosition=startPosition;
				bestLength=length;
			}
		}
		possibles=possibles->next;
	}

	if(endMapping&&endMapping->endExpressionPieces)			// see if there is a possible end to search for
	{
		pieceListElement=endMapping->endExpressionPieces;
		while(pieceListElement)
		{
			pieceIndex=pieceListElement->piece->pieceIndex;
			if(LocatePieceWithOffset(&instance->expressionPieces[pieceIndex],position,&startPosition,&length))
			{
				if(!bestPossible||startPosition<bestStartPosition)
				{
					bestPossible=endMapping;
					bestStartPosition=startPosition;
					bestLength=length;
					*wasEnd=true;
				}
			}
			pieceListElement=pieceListElement->next;
		}
	}

	if(bestPossible)		// found a match!
	{
		*matchPosition=bestStartPosition;
		*matchLength=bestLength;

//		fprintf(stderr,"Best was %s: %d:%d\n",&bestPossible->mappingName[0],bestStartPosition,bestLength);

		return(bestPossible);
	}
	return(NULL);
}

static bool HandleMatchesForDepth(EDITOR_BUFFER *buffer,SYNTAX_STYLE_MAPPING_LIST *startRules,SYNTAX_STYLE_MAPPING *endRule,UINT32 *currentPosition,UINT32 betweenStyle)
// Recursively find nested matches, adjust styles, until we find the end match for this depth,
// or run out of data
// NOTE: this will return false when it could not locate the end match for the current depth
// NOTE: even if this returns false, it may have updated currentPosition
{
	UINT32
		matchPosition,
		matchLength;
	SYNTAX_STYLE_MAPPING
		*mapping;
	bool
		wasEnd;

	while(true)
	{
		if((mapping=FindStartPossiblesOrEnd(buffer->syntaxInstance,startRules,endRule,*currentPosition,&matchPosition,&matchLength,&wasEnd)))
		{
			SetStyleRange(buffer->styleUniverse,*currentPosition,matchPosition-*currentPosition,betweenStyle);
			*currentPosition=matchPosition+matchLength;		// move to the end of this match

			if(!wasEnd)
			{
				SetStyleRange(buffer->styleUniverse,matchPosition,matchLength,mapping->startStyle);

				if(mapping->endExpressionPieces)			// if an ending expression was defined, go look for it
				{
					if(!HandleMatchesForDepth(buffer,mapping->betweenList,mapping,currentPosition,mapping->betweenStyle))
					{
						return(false);
					}
				}
			}
			else
			{
				SetStyleRange(buffer->styleUniverse,matchPosition,matchLength,mapping->endStyle);
				return(true);
			}
		}
		else	// had an end expression, but unable to locate it, so this mapping goes to the end of the text, and we're done
		{
			SetStyleRange(buffer->styleUniverse,*currentPosition,buffer->textUniverse->totalBytes-*currentPosition,betweenStyle);			// set style to end of document
			*currentPosition=buffer->textUniverse->totalBytes;
			return(false);
		}
	}
}

static void HandleMatchesForDepth0(EDITOR_BUFFER *buffer,SYNTAX_STYLE_MAPPING_LIST *startRules,UINT32 currentPosition,UINT32 lastPosition)
// When at depth 0, this attempts to find matches and calls HandleMatchesForDepth for greater depths
// At depth 0, we do some additional work to keep the mapping table up to date
// and to see if it is possible to stop working if we are in sync with the mapping
// table.
{
	UINT32
		matchPosition,
		matchLength;
	SYNTAX_STYLE_MAPPING
		*mapping;
	UINT32
		oldMappingStart,
		oldMappingNumElements;
	MAPPING_ELEMENT
		*oldMappingElement,
		newMappingElement;
	bool
		wasEnd,
		done;

	done=false;
	while(!done)
	{
		if((mapping=FindStartPossiblesOrEnd(buffer->syntaxInstance,startRules,NULL,currentPosition,&matchPosition,&matchLength,&wasEnd)))
		{
			SetStyleRange(buffer->styleUniverse,currentPosition,matchPosition-currentPosition,0);	// clear up to this point
			ClearSARange(&buffer->syntaxInstance->mappingArray,currentPosition,matchPosition-currentPosition);	// clear entries in the mapping table up to this point

			SetStyleRange(buffer->styleUniverse,matchPosition,matchLength,mapping->startStyle);	// set the starting style for the match
			currentPosition=matchPosition+matchLength;

			if(mapping->endExpressionPieces)	// if an ending expression has been defined, go look for it, but be willing to step deeper if a start match from the between list is located
			{
				done=!HandleMatchesForDepth(buffer,mapping->betweenList,mapping,&currentPosition,mapping->betweenStyle);	// hunt after the start for the end
				matchLength=currentPosition-matchPosition;	// update to get length of entire match
			}
			if(currentPosition>lastPosition)	// see if we need to test for being back in sync
			{
				if(GetSARecordAtOrAfterPosition(&buffer->syntaxInstance->mappingArray,currentPosition,&oldMappingStart,&oldMappingNumElements,(void **)(&oldMappingElement)))
				{
					if(oldMappingStart>=currentPosition)	// true if in sync with old mapping table now
					{
						done=true;
					}
				}
				else
				{
					done=true;					// if no old record, then also done
				}
			}
			newMappingElement.mapping=mapping;
			SetSARange(&buffer->syntaxInstance->mappingArray,matchPosition,matchLength,&newMappingElement);	// drop this into the mapping array
		}
		else
		{
			SetStyleRange(buffer->styleUniverse,currentPosition,buffer->textUniverse->totalBytes-currentPosition,0);	// clear style to end of document
			ClearSARange(&buffer->syntaxInstance->mappingArray,currentPosition,buffer->textUniverse->totalBytes-currentPosition);	// remove all mapping entries below here
			done=true;
		}
	}
}

static bool UpdateMappingCache(EDITOR_BUFFER *buffer,UINT32 earliestExpressionChange,UINT32 startOffset,UINT32 endOffset,UINT32 numBytes)
// Now that all of the expressions have been updated, back up to the location
// of the first expression cache change, work out which syntax rule was in effect,
// and start running through the rules, updating the styles as we go, until we
// get to the first place after the last expression cache change where the cached
// rules and the current rule set are the same (when we fall back into the pattern
// that existed before) or to the end of the document, whichever comes first
{
	UINT32
		startPosition,
		numElements;
	MAPPING_ELEMENT
		*mappingElement;

	if(AdjustMappingTableForChange(buffer->syntaxInstance,startOffset,endOffset,numBytes))
	{
		if(earliestExpressionChange)
		{
			earliestExpressionChange--;		// step back one to get to a record which we know has data that was valid before the change
		}
		if(GetSARecordAtOrAfterPosition(&buffer->syntaxInstance->mappingArray,earliestExpressionChange,&startPosition,&numElements,(void **)(&mappingElement)))	// find the mapping in effect at the time of the earliest expression change
		{
			if(startPosition<earliestExpressionChange)	// if mapping was in effect, back up to the start of it
			{
				earliestExpressionChange=startPosition;
			}
		}
		// now, earliestExpressionChange points to the spot in the text where the last known root level status was "no mapping in effect"
		// start the search from here and run to at least startOffset+numBytes

		ViewsStartStyleChange(buffer);
		HandleMatchesForDepth0(buffer,buffer->syntaxInstance->parentMap->rootMapList,earliestExpressionChange,startOffset+numBytes);
		ViewsEndStyleChange(buffer);
		return(true);
	}
	return(false);
}

bool UpdateSyntaxInformation(EDITOR_BUFFER *buffer,UINT32 startOffset,UINT32 endOffset,UINT32 numBytes)
// A change has been made in buffer.
// The text between startOffset and endOffset has been replaced with numBytes
// This will recalculate all the syntax highlighting information for the area of the change
// NOTE: if this is called for a universe which has no syntax highlighting, it does
// nothing.
// NOTE: since regular expressions can match ending at boundaries, we need
// to begin checking 1 character before the change, so we can match expressions
// which may now be matching/not matching because of the ending boundary change
// NOTE: since regular expressions can match starting at boundaries, we need to look
// one character past the end for the same reason.
{
	bool
		fail;
	CHUNK_HEADER
		*chunk;
	UINT32
		offset;
	UINT32
		earliestExpressionChange;
	SYNTAX_EXPRESSION
		*expression;

	fail=false;
	if(buffer->syntaxInstance)	// only do work if this universe has a syntax instance
	{
		// fudge start and end parameters out by 1 so that boundary conditions are checked properly
		if(startOffset)
		{
			startOffset--;
			numBytes++;					// account for byte we just moved back
		}
		if((startOffset+numBytes)<buffer->textUniverse->totalBytes)
		{
			endOffset++;
			numBytes++;					// account for byte we just moved out
		}

		PositionToChunkPositionPastEnd(buffer->textUniverse,startOffset,&chunk,&offset);	// locate the start of the change

		earliestExpressionChange=startOffset;		// this is the max earliest expression change

		expression=buffer->syntaxInstance->parentMap->firstExpression;
		while(expression&&!fail)		// update all the expressions
		{
			fail=!UpdateExpressionCaches(chunk,offset,buffer->syntaxInstance,expression,startOffset,endOffset,numBytes,buffer->textUniverse->totalBytes,&earliestExpressionChange);
			expression=expression->next;
		}

		if(!fail)
		{
			fail=!UpdateMappingCache(buffer,earliestExpressionChange,startOffset,endOffset,numBytes);	// update the mapping of expressions to style
		}
	}
	return(!fail);
}

bool RegenerateAllSyntaxInformation(EDITOR_BUFFER *buffer)
// Run through buffer, and recreate its syntaxInstance, and update
// its editor universe's styleUniverse.
// This is done when a syntaxInstance is first added to an editor universe
// If there is a problem, SetError, return false
{
	return(UpdateSyntaxInformation(buffer,0,buffer->textUniverse->totalBytes,buffer->textUniverse->totalBytes));	// pretend as if the whole thing changed
}

SYNTAX_MAP *GetInstanceParentMap(SYNTAX_INSTANCE *instance)
// return the parent syntax map for the given instance
{
	return(instance->parentMap);
}

void CloseSyntaxInstance(SYNTAX_INSTANCE *instance)
// unlink instance from its parent map, and destroy it
{
	UINT32
		i;

	if(instance->next)
	{
		instance->next->prev=instance->prev;
	}
	if(instance->prev)
	{
		instance->prev->next=instance->next;
	}
	if(instance->parentMap->firstInstance==instance)				// if at the head of the list, move the head
	{
		instance->parentMap->firstInstance=instance->next;
	}

	for(i=0;i<instance->parentMap->numExpressionPieces;i++)
	{
		UnInitSA(&instance->expressionPieces[i].matchArray);
	}

	UnInitSA(&instance->mappingArray);

	MDisposePtr(instance);
}

SYNTAX_INSTANCE *OpenSyntaxInstance(SYNTAX_MAP *map,EDITOR_BUFFER *buffer)
// Create an instance of a syntax highlight map
// link it to map and return it
// If there is a problem, SetError, return NULL
{
	SYNTAX_INSTANCE
		*instance;
	SYNTAX_EXPRESSION
		*expression;
	EXPRESSION_PIECE
		*expressionPiece;
	bool
		fail;
	UINT32
		i;

	fail=false;
	if((instance=(SYNTAX_INSTANCE *)MNewPtr(sizeof(SYNTAX_INSTANCE)+sizeof(EXPRESSION_PIECE_INSTANCE)*map->numExpressionPieces)))
	{
		instance->buffer=buffer;
		fail=!InitSA(&instance->mappingArray,sizeof(MAPPING_ELEMENT));

		for(i=0;(i<map->numExpressionPieces)&&!fail;i++)
		{
			instance->expressionPieces[i].maximumStartDistance=0;	// never saw a match with an offset larger than this yet
			fail=!InitSA(&instance->expressionPieces[i].matchArray,sizeof(EXPRESSION_MATCH_ELEMENT));
		}
		if(!fail)
		{
			expression=map->firstExpression;	// assign all the expression pieces
			while(expression)
			{
				expressionPiece=expression->firstPiece;
				while(expressionPiece)
				{
					instance->expressionPieces[expressionPiece->pieceIndex].expressionPiece=expressionPiece;
					expressionPiece=expressionPiece->next;
				}
				expression=expression->next;
			}

			instance->parentMap=map;			// point at the parent map
			instance->prev=NULL;
			instance->next=map->firstInstance;
			if(map->firstInstance)
			{
				map->firstInstance->prev=instance;
			}
			map->firstInstance=instance;
			return(instance);
		}
		MDisposePtr(instance);
	}
	return(NULL);
}

// -----------------------------------------------------------------------------------------------------------

// Code for creating syntax maps

void RemoveMappingList(SYNTAX_STYLE_MAPPING_LIST *list)
// remove all elements of list
{
	SYNTAX_STYLE_MAPPING_LIST
		*next;

	while(list)
	{
		next=list->next;
		MDisposePtr(list);
		list=next;
	}
}

SYNTAX_STYLE_MAPPING_LIST *AddMappingListElement(SYNTAX_STYLE_MAPPING_LIST **listHead,SYNTAX_STYLE_MAPPING *mapping)
// Create a new mapping list element, and link it to the end of the given list
{
	SYNTAX_STYLE_MAPPING_LIST
		*previousElement;
	SYNTAX_STYLE_MAPPING_LIST
		*mappingListElement;

	previousElement=*listHead;
	while(previousElement&&(previousElement->mappingEntry!=mapping)&&previousElement->next)
	{
		previousElement=previousElement->next;
	}
	if((!previousElement)||(previousElement->mappingEntry!=mapping))
	{
		if((mappingListElement=(SYNTAX_STYLE_MAPPING_LIST *)MNewPtr(sizeof(SYNTAX_STYLE_MAPPING_LIST))))
		{
			mappingListElement->mappingEntry=mapping;
			if(previousElement)
			{
				previousElement->next=mappingListElement;
				mappingListElement->prev=previousElement;
				mappingListElement->next=NULL;
			}
			else
			{
				*listHead=mappingListElement;
				mappingListElement->prev=NULL;
				mappingListElement->next=NULL;
			}
			return(mappingListElement);
		}
	}
	else
	{
		SetError(errorDescriptions[LIST_MAPPING_EXISTS]);
	}
	return(NULL);
}

SYNTAX_STYLE_MAPPING_LIST *AddBetweenListElementToMapping(SYNTAX_STYLE_MAPPING *mapping,SYNTAX_STYLE_MAPPING *betweenMapping)
// Add betweenMapping to mapping
// if there is a problem, SetError, and return false
{
	return(AddMappingListElement(&mapping->betweenList,betweenMapping));
}

SYNTAX_STYLE_MAPPING_LIST *AddRootListElementToMap(SYNTAX_MAP *map,SYNTAX_STYLE_MAPPING *rootMapping)
// Add rootMapping to map
// if there is a problem, SetError, and return false
{
	return(AddMappingListElement(&map->rootMapList,rootMapping));
}

SYNTAX_STYLE_MAPPING *LocateSyntaxStyleMapping(SYNTAX_MAP *map,const char *name)
// locate a syntax style mapping with name in map, and return a pointer to it
// if none can be found, return NULL
// NOTE: this could probably benefit from a hash table
{
	SYNTAX_STYLE_MAPPING
		*mapping;

	mapping=map->firstStyleMapping;
	while(mapping&&strcmp(mapping->mappingName,name)!=0)
	{
		mapping=mapping->next;
	}
	return(mapping);
}

void SetMappingStartExpressionPiece(SYNTAX_STYLE_MAPPING *mapping,EXPRESSION_PIECE *startExpressionPiece)
// Set the pointer to the start expression piece for mapping
{
	mapping->startExpressionPiece=startExpressionPiece;
}

void RemoveExpressionList(EXPRESSION_PIECE_LIST *list)
// remove all elements of list
{
	EXPRESSION_PIECE_LIST
		*next;

	while(list)
	{
		next=list->next;
		MDisposePtr(list);
		list=next;
	}
}

EXPRESSION_PIECE_LIST *AddMappingEndExpressionPiece(SYNTAX_STYLE_MAPPING *mapping,EXPRESSION_PIECE *endExpressionPiece)
// Add endExpression piece to the end of the list of ending expression pieces hanging off of mapping
// NOTE: this considers it an error to have two of the same piece on the list
// if there is a problem, SetError, and return NULL
{
	EXPRESSION_PIECE_LIST
		*previousElement;
	EXPRESSION_PIECE_LIST
		*listElement;

	previousElement=mapping->endExpressionPieces;
	while(previousElement&&(previousElement->piece!=endExpressionPiece)&&previousElement->next)
	{
		previousElement=previousElement->next;
	}
	if((!previousElement)||(previousElement->piece!=endExpressionPiece))
	{

		if((listElement=(EXPRESSION_PIECE_LIST *)MNewPtr(sizeof(EXPRESSION_PIECE_LIST))))
		{
			listElement->piece=endExpressionPiece;
			if(previousElement)
			{
				previousElement->next=listElement;
				listElement->prev=previousElement;
				listElement->next=NULL;
			}
			else
			{
				mapping->endExpressionPieces=listElement;
				listElement->prev=NULL;
				listElement->next=NULL;
			}
		}
		return(listElement);
	}
	else
	{
		SetError(errorDescriptions[EXPRESSION_PIECE_EXISTS]);
	}
	return(NULL);
}

void SetMappingStyles(SYNTAX_STYLE_MAPPING *mapping,UINT32 startStyle,UINT32 betweenStyle,UINT32 endStyle)
// Set the pointer to the start expression piece for mapping
{
	mapping->startStyle=startStyle;
	mapping->betweenStyle=betweenStyle;
	mapping->endStyle=endStyle;
}

void RemoveMappingFromSyntaxMap(SYNTAX_MAP *map,SYNTAX_STYLE_MAPPING *mapping)
// pull mapping out of the map and delete it
{
	RemoveExpressionList(mapping->endExpressionPieces);	// get rid of list of ending expressions

	RemoveMappingList(mapping->betweenList);			// get rid of sub-lists

	if(mapping->next)
	{
		mapping->next->prev=mapping->prev;
	}
	if(mapping->prev)
	{
		mapping->prev->next=mapping->next;
	}
	if(map->firstStyleMapping==mapping)					// if at the head of the list, move the head
	{
		map->firstStyleMapping=mapping->next;
	}
	MDisposePtr(mapping);
}

SYNTAX_STYLE_MAPPING *AddMappingToSyntaxMap(SYNTAX_MAP *map,const char *mappingName)
// Add a mapping of expressions to styles to map
// Initially, the mapping is empty, and must be filled in by calls to the above routines
// if there is a problem, SetError, and return NULL
{
	SYNTAX_STYLE_MAPPING
		*mapping;

	if(!LocateSyntaxStyleMapping(map,mappingName))
	{
		if((mapping=(SYNTAX_STYLE_MAPPING *)MNewPtr(sizeof(SYNTAX_STYLE_MAPPING)+strlen(mappingName)+1)))
		{
			mapping->parent=map;

			strcpy(&mapping->mappingName[0],mappingName);	// copy over the name

			mapping->startExpressionPiece=NULL;
			mapping->endExpressionPieces=NULL;

			mapping->startStyle=0;
			mapping->betweenStyle=0;
			mapping->endStyle=0;

			mapping->betweenList=NULL;

			mapping->prev=NULL;
			mapping->next=map->firstStyleMapping;			// link it onto the list
			if(map->firstStyleMapping)
			{
				map->firstStyleMapping->prev=mapping;
			}
			map->firstStyleMapping=mapping;
			return(mapping);
		}
	}
	else
	{
		SetError(errorDescriptions[STYLE_MAPPING_EXISTS]);
	}
	return(NULL);
}

EXPRESSION_PIECE *LocateExpressionPiece(SYNTAX_EXPRESSION *expression,bool useRegisterMatch,UINT32 registerIndex)
// Attempt to find the piece of expression which has the given attributes,
// If no piece can be located, return NULL
{
	EXPRESSION_PIECE
		*piece;
	bool
		found;

	found=false;
	piece=expression->firstPiece;
	while(piece&&!found)
	{
		if((!useRegisterMatch&&!piece->useRegisterMatch)||(useRegisterMatch&&piece->useRegisterMatch&&(piece->registerIndex==registerIndex)))
		{
			found=true;
		}
		else
		{
			piece=piece->next;
		}
	}
	return(piece);
}

void RemovePieceFromExpression(SYNTAX_EXPRESSION *expression,EXPRESSION_PIECE *piece)
// Remove piece from expression
{
	if(piece->next)
	{
		piece->next->prev=piece->prev;
	}
	if(piece->prev)
	{
		piece->prev->next=piece->next;
	}
	if(expression->firstPiece==piece)				// if at the head of the list, move the head
	{
		expression->firstPiece=piece->next;
	}
	MDisposePtr(piece);
}

EXPRESSION_PIECE *AddPieceToExpression(SYNTAX_EXPRESSION *expression,bool useRegisterMatch,UINT32 registerIndex)
// Add a piece to expression
// NOTE: if there is already a piece on expression matching the given one, just return it
// if there is a problem, SetError, return NULL
{
	EXPRESSION_PIECE
		*piece;

	if(!(piece=LocateExpressionPiece(expression,useRegisterMatch,registerIndex)))
	{
		if((piece=(EXPRESSION_PIECE *)MNewPtr(sizeof(EXPRESSION_PIECE))))
		{
			piece->parent=expression;
			piece->prev=NULL;
			piece->next=expression->firstPiece;
			if(expression->firstPiece)
			{
				expression->firstPiece->prev=piece;
			}
			expression->firstPiece=piece;

			piece->useRegisterMatch=useRegisterMatch;	// tells if entire expression matches, or a register matches
			piece->registerIndex=registerIndex;			// if useRegisterMatch is true, this gives the register index of the match

			piece->pieceIndex=expression->parent->numExpressionPieces;
			expression->parent->numExpressionPieces++;
		}
	}
	return(piece);
}

SYNTAX_EXPRESSION *LocateSyntaxMapExpression(SYNTAX_MAP *map,const char *name)
// locate an expression with name in map, and return a pointer to it
// if none can be found, return NULL
{
	SYNTAX_EXPRESSION
		*expression;

	expression=map->firstExpression;
	while(expression&&strcmp(expression->expressionName,name)!=0)
	{
		expression=expression->next;
	}
	return(expression);
}

void RemoveExpressionFromSyntaxMap(SYNTAX_MAP *map,SYNTAX_EXPRESSION *expression)
// pull expression out of the map and delete it
// NOTE: it is the caller's responsibility to make sure there are no
// mappings which might be left pointing to the given expression
// after it is deleted
{
	REFree(expression->compiledExpression);

	if(expression->next)
	{
		expression->next->prev=expression->prev;
	}
	if(expression->prev)
	{
		expression->prev->next=expression->next;
	}
	if(map->firstExpression==expression)				// if at the head of the list, move the head
	{
		map->firstExpression=expression->next;
	}
	MDisposePtr(expression);
}

SYNTAX_EXPRESSION *AddExpressionToSyntaxMap(SYNTAX_MAP *map,const char *expressionName,const char *expressionText)
// Add a new expression to map
// If there is a problem, SetError, and return NULL
{
	SYNTAX_EXPRESSION
		*expression;

	if(!LocateSyntaxMapExpression(map,expressionName))
	{
		if((expression=(SYNTAX_EXPRESSION *)MNewPtr(sizeof(SYNTAX_EXPRESSION)+strlen(expressionName)+1)))
		{
			if((expression->compiledExpression=RECompile((UINT8 *)expressionText,(UINT32)strlen(expressionText),NULL)))
			{
				strcpy(&expression->expressionName[0],expressionName);	// copy over the name
				expression->parent=map;
				expression->prev=NULL;
				expression->next=map->firstExpression;		// link it onto the list
				if(map->firstExpression)
				{
					map->firstExpression->prev=expression;
				}
				map->firstExpression=expression;
				expression->firstPiece=NULL;						// no pieces defined to match yet
				return(expression);
			}
			MDisposePtr(expression);
		}
	}
	else
	{
		SetError(errorDescriptions[EXPRESSION_EXISTS]);
	}
	return(NULL);
}

char *GetSyntaxMapName(SYNTAX_MAP *map)
// return a pointer to the name of the given syntax map
{
	return(&map->mapName[0]);
}

SYNTAX_MAP *LocateNextSyntaxMap(SYNTAX_MAP *map)
// return a pointer to the syntax map defined after the passed one
// if none can be found, return NULL
// if NULL is passed in, return the first one
{
	if(map)
	{
		return(map->next);
	}
	else
	{
		return(syntaxMapHead);
	}
}

SYNTAX_MAP *LocateSyntaxMap(char *name)
// locate a syntax map with name, and return a pointer to it
// if none can be found, return NULL
{
	SYNTAX_MAP
		*map;

	map=syntaxMapHead;
	while(map&&strcmp(map->mapName,name)!=0)
	{
		map=map->next;
	}
	return(map);
}

void UnlinkSyntaxMap(SYNTAX_MAP *map)
// unlink map from the global list of maps
{
	if(map->next)
	{
		map->next->prev=map->prev;
	}
	else
	{
		syntaxMapTail=map->prev;
	}

	if(map->prev)
	{
		map->prev->next=map->next;
	}
	else
	{
		syntaxMapHead=map->next;
	}
}

bool LinkSyntaxMap(SYNTAX_MAP *map)
// link map to the global list of maps
// NOTE: this must be called only once for each map
// NOTE: this will fail only if a map already exists in the global list
// which has the same name as map.
{
	if(!LocateSyntaxMap(map->mapName))
	{
		map->prev=syntaxMapTail;
		map->next=NULL;
		if(syntaxMapTail)
		{
			syntaxMapTail->next=map;
			syntaxMapTail=map;
		}
		else
		{
			syntaxMapHead=syntaxMapTail=map;
		}
		return(true);
	}
	else
	{
		SetError(errorDescriptions[MAP_EXISTS]);
	}
	return(false);
}

void CloseSyntaxMap(SYNTAX_MAP *map)
// dispose of a syntax map
// NOTE: the map must not be in use by any buffer when this is called
{
	RemoveMappingList(map->rootMapList);	// get rid of the root mapping list

	while(map->firstStyleMapping)
	{
		RemoveMappingFromSyntaxMap(map,map->firstStyleMapping);
	}

	while(map->firstExpression)
	{
		while(map->firstExpression->firstPiece)
		{
			RemovePieceFromExpression(map->firstExpression,map->firstExpression->firstPiece);
		}
		RemoveExpressionFromSyntaxMap(map,map->firstExpression);
	}

	MDisposePtr(map);
}

SYNTAX_MAP *OpenSyntaxMap(char *name)
// create an empty syntax map with the given name, link it to the
// end of the global list
// if there is a problem, set the error, and return NULL
{
	SYNTAX_MAP
		*map;

	if((map=(SYNTAX_MAP *)MNewPtr(sizeof(SYNTAX_MAP)+strlen(name)+1)))
	{
		map->numExpressionPieces=0;
		map->firstExpression=NULL;
		map->firstStyleMapping=NULL;
		map->firstInstance=NULL;
		map->rootMapList=NULL;
		strcpy(&map->mapName[0],name);	// copy over the name
		map->prev=NULL;
		map->next=NULL;
		return(map);
	}
	return(NULL);
}

EDITOR_BUFFER *LocateNextEditorBufferOnMap(SYNTAX_MAP *map,EDITOR_BUFFER *buffer)
// Locate the next editor universe linked to map
// If buffer is passed as NULL, return the first buffer
// If there are no more buffers linked to the map, return NULL
{
	if(buffer)
	{
		if(buffer->syntaxInstance->next)
		{
			return(buffer->syntaxInstance->next->buffer);
		}
	}
	else
	{
		if(map->firstInstance)
		{
			return(map->firstInstance->buffer);
		}
	}
	return(NULL);
}

SYNTAX_MAP *GetAssignedSyntaxMap(EDITOR_BUFFER *buffer)
// Return the syntax map assigned to buffer
// if none has been assigned, return NULL
{
	if(buffer->syntaxInstance)						// get rid of anything that may have been there
	{
		return(GetInstanceParentMap(buffer->syntaxInstance));
	}
	return(NULL);
}

bool AssignSyntaxMap(EDITOR_BUFFER *buffer,SYNTAX_MAP *map)
// Assign or remove a SYNTAX_MAP from buffer
// if map is passed as NULL, remove any current map
{
	bool
		fail;

	fail=false;
	if(buffer->syntaxInstance)						// get rid of anything that may have been there
	{
		CloseSyntaxInstance(buffer->syntaxInstance);
		buffer->syntaxInstance=NULL;				// remember this is gone

		if(!map)
		{
			// Clear style information for the universe
			ViewsStartStyleChange(buffer);
			SetStyleRange(buffer->styleUniverse,0,buffer->textUniverse->totalBytes,0);	// clear out all style info
			ViewsEndStyleChange(buffer);
		}
	}
	if(map)
	{
		if((buffer->syntaxInstance=OpenSyntaxInstance(map,buffer)))
		{
			fail=!RegenerateAllSyntaxInformation(buffer);	// update all the information
		}
		else
		{
			fail=true;										// something went wrong trying to get the instance
		}
	}
	return(!fail);
}

void UnInitSyntaxMaps()
// undo what InitSyntaxMaps did
// NOTE: the caller much make sure no maps are in use
// before calling this routine.
{
	SYNTAX_MAP
		*map;

	while((map=syntaxMapHead))
	{
		UnlinkSyntaxMap(map);
		CloseSyntaxMap(map);
	}
}

bool InitSyntaxMaps()
// initialize the global table of syntax maps
{
	syntaxMapHead=syntaxMapTail=NULL;
	return(true);
}