1 {
2 ***************************************************************************
3 * *
4 * This source is free software; you can redistribute it and/or modify *
5 * it under the terms of the GNU General Public License as published by *
6 * the Free Software Foundation; either version 2 of the License, or *
7 * (at your option) any later version. *
8 * *
9 * This code is distributed in the hope that it will be useful, but *
10 * WITHOUT ANY WARRANTY; without even the implied warranty of *
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
12 * General Public License for more details. *
13 * *
14 * A copy of the GNU General Public License is available on the World *
15 * Wide Web at <http://www.gnu.org/copyleft/gpl.html>. You can also *
16 * obtain it by writing to the Free Software Foundation, *
17 * Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1335, USA. *
18 * *
19 ***************************************************************************
20
21 Author: Mattias Gaertner
22
23 Abstract:
24 An Atom is the smallest unit for a parser. Usually a word or a symbol.
25 An Atom is defined by the Start- and Endposition in the code (TAtomPosition)
26
27 An TAtomRing is a ring of TAtomPosition
28
29 }
30 unit CodeAtom;
31
32 {$ifdef FPC}{$mode objfpc}{$endif}{$inline on}{$H+}
33
34 interface
35
36 {$I codetools.inc}
37
38 { $Define CheckAtomRing}
39
40 uses
41 {$IFDEF MEM_CHECK}
42 MemCheck,
43 {$ENDIF}
44 SysUtils,
45 // Codetools
46 FileProcs, KeywordFuncLists;
47
48 type
49 TCommonAtomFlag = (
50 cafNone, // = none of the below
51 cafSemicolon, cafEqual, cafColon, cafComma, cafPoint,
52 cafRoundBracketOpen, cafRoundBracketClose,
53 cafEdgedBracketOpen, cafEdgedBracketClose,
54 cafAssignment,
55 cafWord, cafEnd,
56 cafOtherOperator // = other operator
57 );
58 TCommonAtomFlags = set of TCommonAtomFlag;
59
60 const
61 AllCommonAtomWords = [cafWord, cafEnd];
62 CommonAtomFlagNames: array[TCommonAtomFlag] of shortstring = (
63 'None',
64 'Semicolon', 'Equal', 'Colon', 'Comma', 'Point',
65 'RoundBracketOpen', 'RoundBracketClose',
66 'EdgedBracketOpen', 'EdgedBracketClose',
67 'Assignment',
68 'Word', 'End', 'Operator'
69 );
70
71 type
72 TAtomPosition = record
73 StartPos: integer; // first char of Atom
74 EndPos: integer; // char behind Atom
75 Flag: TCommonAtomFlag;
76 end;
77 PAtomPosition = ^TAtomPosition;
78
79 const
80 StartAtomPosition: TAtomPosition = (StartPos:1; EndPos:1; Flag:cafNone);
81 CleanAtomPosition: TAtomPosition = (StartPos:0; EndPos:0; Flag:cafNone);
82
83 type
84
85 { TAtomRing }
86
87 TAtomRing = class
88 private
89 FMask: integer;
90 FSize: integer;
91 FCur: integer;
92 FFirst: integer;
93 FLast: integer;
94 FItems: {$ifdef FPC}^{$else}array of {$endif}TAtomPosition;
95 FSrcLen: integer;
96 // ring of TAtomPosition
97 procedure SetSize(NewSize: integer);
IndexToRelativePosnull98 function IndexToRelativePos(Index: integer): integer;
RelativeToIndexnull99 function RelativeToIndex(RelativePos: integer): integer; inline;
100 public
Emptynull101 function Empty: boolean; inline;
102 procedure Add(const NewAtom: TAtomPosition); inline;
GetCurrentnull103 function GetCurrent(var Atom: TAtomPosition): boolean;
IsCurrentnull104 function IsCurrent(const Atom: TAtomPosition): boolean;
SetCurrentnull105 function SetCurrent(const Atom: TAtomPosition): boolean;
HasPriornull106 function HasPrior: boolean; inline;
GoBacknull107 function GoBack(var Atom: TAtomPosition): boolean;
108 procedure UndoLastAdd; inline;
109 procedure AddReverse(const NewAtom: TAtomPosition); inline; // used when reading backwards
GetPriorAtomnull110 function GetPriorAtom: TAtomPosition; inline;
GetAtomAtnull111 function GetAtomAt(RelativePos:integer): TAtomPosition;
112 // 0=current=last added
113 // -1=prior current, added before current ...
114 // 1=next first undo item, ...
GetValueAtnull115 function GetValueAt(ReverseRelativePos:integer): TAtomPosition; inline; deprecated 'use GetAtomAt(-1-index)'; // Laz 1.9
IndexOfnull116 function IndexOf(StartPos: integer; out RelativePos: integer): boolean;
117 procedure SetIndex(RelativePos: integer);
Countnull118 function Count: integer; inline; deprecated 'use HasPrior or PriorCount instead'; // Laz 1.9
PriorCountnull119 function PriorCount: integer; inline;
NextCountnull120 function NextCount: integer; inline;
HasNextnull121 function HasNext: boolean; inline;
MoveToNextnull122 function MoveToNext(var Atom: TAtomPosition): boolean;
123 property Size: integer read FSize write SetSize; // rounded up to next power of 2
124 procedure Clear;
125 procedure ClearCurrent; // clear current and next, keep previous
126 procedure WriteDebugReport;
127 procedure ConsistencyCheck;
128 property SrcLen: integer read FSrcLen write FSrcLen;
129 constructor Create;
130 destructor Destroy; override;
CalcMemSizenull131 function CalcMemSize: PtrUInt;
132 end;
133
134 TAtomList = class
135 private
136 FCapacity: integer;
137 FCount: integer;
138 FItems: {$ifdef FPC}^{$else}array of {$endif}TAtomPosition;
GetItemsnull139 function GetItems(Index: integer): TAtomPosition;
140 procedure SetCapacity(const AValue: integer);
141 procedure SetItems(Index: integer; const AValue: TAtomPosition);
142 procedure Grow;
143 public
144 procedure Add(NewAtom: TAtomPosition);
145 procedure Clear;
146 constructor Create;
147 destructor Destroy; override;
148 property Capacity: integer read FCapacity write SetCapacity;
149 property Count: integer read FCount;
150 property Items[Index: integer]: TAtomPosition read GetItems write SetItems; default;
151 end;
152
153 //-----------------------------------------------------------------------------
154 // useful functions
AtomPositionnull155 function AtomPosition(StartPos, EndPos: integer): TAtomPosition; overload;
AtomPositionnull156 function AtomPosition(StartPos, EndPos: integer; Flag: TCommonAtomFlag): TAtomPosition; overload;
157
dbgsnull158 function dbgs(const a: TAtomPosition): string; overload;
159
160
161 implementation
162
163
164 { useful functions }
165
AtomPositionnull166 function AtomPosition(StartPos, EndPos: integer): TAtomPosition;
167 begin
168 Result.StartPos:=StartPos;
169 Result.EndPos:=EndPos;
170 Result.Flag:=cafNone;
171 end;
172
AtomPositionnull173 function AtomPosition(StartPos, EndPos: integer; Flag: TCommonAtomFlag
174 ): TAtomPosition;
175 begin
176 Result.StartPos:=StartPos;
177 Result.EndPos:=EndPos;
178 Result.Flag:=Flag;
179 end;
180
dbgsnull181 function dbgs(const a: TAtomPosition): string;
182 begin
183 Result:=CommonAtomFlagNames[a.Flag]+'['+dbgs(a.StartPos)+'-'+dbgs(a.EndPos)+']';
184 end;
185
186 { TAtomRing }
187
188 procedure TAtomRing.SetSize(NewSize: integer);
189 var i: integer;
190 begin
191 Clear;
192 if NewSize<2 then NewSize:=2;
193 if NewSize>$FFFFFFF then NewSize:=$FFFFFFF;
194 i:=0;
195 while (i<30) and (NewSize>(1 shl i)) do inc(i);
196 NewSize:=(1 shl i);
197 if FSize=NewSize then exit;
198 FSize:=NewSize;
199 FMask:=FSize-1;
200 ReAllocMem(FItems,FSize * SizeOf(TAtomPosition));
201 Clear;
202 end;
203
IndexToRelativePosnull204 function TAtomRing.IndexToRelativePos(Index: integer): integer;
205 begin
206 if FCur<0 then
207 RaiseCatchableException('IndexToRelativePos');
208 if FCur>=FFirst then begin
209 if Index>=FFirst then begin
210 Result:=Index-FCur;
211 end else begin
212 Result:=Index+FSize-FCur;
213 end;
214 end else begin
215 if Index>=FFirst then begin
216 Result:=Index-FSize-FCur;
217 end else begin
218 Result:=Index-FCur;
219 end;
220 end;
221 end;
222
RelativeToIndexnull223 function TAtomRing.RelativeToIndex(RelativePos: integer): integer;
224 begin
225 Result:=(FCur+FSize+RelativePos) and FMask;
226 end;
227
Emptynull228 function TAtomRing.Empty: boolean;
229 begin
230 Result:=FCur>=0;
231 end;
232
233 constructor TAtomRing.Create;
234 begin
235 inherited Create;
236 FItems:=nil;
237 Size:=16;
238 end;
239
240 destructor TAtomRing.Destroy;
241 begin
242 if FItems<>nil then FreeMem(FItems);
243 inherited Destroy;
244 end;
245
TAtomRing.CalcMemSizenull246 function TAtomRing.CalcMemSize: PtrUInt;
247 begin
248 Result:=PtrUInt(InstanceSize)
249 +PtrUInt(FSize)*SizeOf(TAtomPosition);
250 end;
251
252 procedure TAtomRing.Add(const NewAtom: TAtomPosition);
253 begin
254 if FCur>=0 then begin
255 if (FCur=FLast) then begin
256 FCur:=(FCur+1) and FMask;
257 FLast:=FCur;
258 if FFirst=FLast then
259 FFirst:=(FFirst+1) and FMask;
260 end else
261 FCur:=(FCur+1) and FMask;
262 end else begin
263 FCur:=0;
264 FFirst:=0;
265 FLast:=0;
266 end;
267 FItems[FCur]:=NewAtom;
268 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
269 end;
270
GetCurrentnull271 function TAtomRing.GetCurrent(var Atom: TAtomPosition): boolean;
272 begin
273 if FCur>=0 then begin
274 Atom:=FItems[FCur];
275 Result:=true;
276 end else
277 Result:=false;
278 end;
279
IsCurrentnull280 function TAtomRing.IsCurrent(const Atom: TAtomPosition): boolean;
281 var
282 p: PAtomPosition;
283 begin
284 if FCur<0 then exit(false);
285 p:=@FItems[FCur];
286 Result:=(Atom.StartPos=p^.StartPos) and (Atom.EndPos=p^.EndPos)
287 and (Atom.Flag=p^.Flag);
288 end;
289
TAtomRing.SetCurrentnull290 function TAtomRing.SetCurrent(const Atom: TAtomPosition): boolean;
291 var
292 Item: PAtomPosition;
293 begin
294 if Atom.StartPos>=Atom.EndPos then begin
295 Clear;
296 exit(false);
297 end;
298 Result:=true;
299 if FCur>=0 then begin
300 if FCur<>FFirst then begin
301 Item:=@FItems[(FCur+FSize-1) and FMask];
302 if Item^.EndPos>Atom.StartPos then begin
303 Clear;
304 Add(Atom);
305 exit;
306 end;
307 end;
308 if FCur<>FLast then begin
309 Item:=@FItems[(FCur+1) and FMask];
310 if Item^.StartPos<Atom.EndPos then begin
311 ClearCurrent;
312 Add(Atom);
313 exit;
314 end;
315 end;
316 FItems[FCur]:=Atom;
317 end else begin
318 Add(Atom);
319 end;
320 end;
321
HasPriornull322 function TAtomRing.HasPrior: boolean;
323 begin
324 Result:=FCur<>FFirst;
325 end;
326
TAtomRing.GoBacknull327 function TAtomRing.GoBack(var Atom: TAtomPosition): boolean;
328 begin
329 if FCur<>FFirst then begin
330 FCur:=(FCur+FSize-1) and FMask;
331 Atom:=FItems[FCur];
332 Result:=true;
333 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
334 end else
335 Result:=false;
336 end;
337
338 procedure TAtomRing.AddReverse(const NewAtom: TAtomPosition);
339 begin
340 if FFirst>=0 then begin
341 if (FCur=FFirst) then begin
342 FCur:=(FCur+FSize-1) and FMask;
343 FFirst:=FCur;
344 if FFirst=FLast then
345 FLast:=(FLast+FSize-1) and FMask;
346 end else
347 FCur:=(FCur+FSize-1) and FMask;
348 end else begin
349 FCur:=0;
350 FFirst:=0;
351 FLast:=0;
352 end;
353 FItems[FCur]:=NewAtom;
354 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
355 end;
356
357 procedure TAtomRing.UndoLastAdd;
358 begin
359 if FCur<>FFirst then begin
360 FCur:=(FCur+FSize-1) and FMask;
361 end else begin
362 Clear;
363 end;
364 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
365 end;
366
GetPriorAtomnull367 function TAtomRing.GetPriorAtom: TAtomPosition;
368 begin
369 if (FCur<>FFirst) then begin
370 Result:=FItems[RelativeToIndex(-1)];
371 exit;
372 end;
373 Result:=CleanAtomPosition;
374 end;
375
TAtomRing.GetAtomAtnull376 function TAtomRing.GetAtomAt(RelativePos: integer): TAtomPosition;
377 // 0=current -1=prior current ...
378 var
379 i: Integer;
380 begin
381 if (FCur>=0) then begin
382 if RelativePos>=0 then begin
383 i:=(FLast+FSize-FCur) and FMask;
384 if RelativePos<=i then begin
385 Result:=FItems[RelativeToIndex(RelativePos)];
386 exit;
387 end;
388 end else begin
389 i:=((FCur+FSize-FFirst) and FMask)+1;
390 if -RelativePos<=i then begin
391 Result:=FItems[RelativeToIndex(RelativePos)];
392 exit;
393 end;
394 end;
395 end;
396 Result:=CleanAtomPosition;
397 end;
398
TAtomRing.GetValueAtnull399 function TAtomRing.GetValueAt(ReverseRelativePos: integer): TAtomPosition;
400 begin
401 Result:=GetAtomAt(-1-ReverseRelativePos);
402 end;
403
IndexOfnull404 function TAtomRing.IndexOf(StartPos: integer; out RelativePos: integer): boolean;
405 var
406 p, l, r, m: Integer;
407 begin
408 //writeln('TAtomRing.IndexOf StartPos=',StartPos,' FCur=',FCur,' FFirst=',FFirst,' FLast=',FLast);
409 if FCur<0 then exit(false);
410 if FItems[FFirst].StartPos>StartPos then exit(false);
411 if FItems[FLast].StartPos<StartPos then exit(false);
412
413 if FFirst<=FLast then begin
414 l:=FFirst;
415 r:=FLast;
416 end else begin
417 l:=FFirst;
418 r:=FLast+FSize;
419 end;
420 //writeln('TAtomRing.IndexOf l=',l,' r=',r);
421 while l<=r do begin
422 m:=(l+r) shr 1;
423 p:=FItems[m and FMask].StartPos;
424 if StartPos>p then
425 l:=m+1
426 else if StartPos<p then
427 r:=m-1
428 else begin
429 // found
430 RelativePos:=IndexToRelativePos(m);
431 exit(true);
432 end;
433 end;
434 Result:=false;
435 end;
436
437 procedure TAtomRing.SetIndex(RelativePos: integer);
438 begin
439 FCur:=(FCur+FSize+RelativePos) and FMask;
440 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
441 end;
442
TAtomRing.Countnull443 function TAtomRing.Count: integer;
444 begin
445 Result:=PriorCount;
446 end;
447
448 procedure TAtomRing.Clear;
449 begin
450 FFirst:=-1;
451 FLast:=-1;
452 FCur:=-1;
453 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
454 end;
455
456 procedure TAtomRing.ClearCurrent;
457 begin
458 if FCur<0 then exit;
459 if FCur=FFirst then
460 Clear
461 else begin
462 FCur:=(FCur+FSize-1) and FMask;
463 FLast:=FCur;
464 end;
465 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
466 end;
467
PriorCountnull468 function TAtomRing.PriorCount: integer;
469 begin
470 if FCur>=0 then
471 Result:=((FCur+FSize-FFirst) and FMask)+1
472 else
473 Result:=0;
474 end;
475
NextCountnull476 function TAtomRing.NextCount: integer;
477 begin
478 if FCur>=0 then
479 Result:=(FLast+FSize-FCur) and FMask
480 else
481 Result:=0;
482 end;
483
TAtomRing.HasNextnull484 function TAtomRing.HasNext: boolean;
485 begin
486 Result:=FCur<>FLast;
487 end;
488
MoveToNextnull489 function TAtomRing.MoveToNext(var Atom: TAtomPosition): boolean;
490 begin
491 if FCur<>FLast then begin
492 FCur:=(FCur+1) and FMask;
493 Atom:=FItems[FCur];
494 Result:=true;
495 {$IFDEF CheckAtomRing}ConsistencyCheck;{$ENDIF}
496 end else
497 Result:=false;
498 end;
499
500 procedure TAtomRing.WriteDebugReport;
501 var i: integer;
502 p: TAtomPosition;
503 begin
504 DebugLn(['[TAtomRing.WriteDebugReport] Size=',FSize
505 ,' Cur=',FCur,' First=',FFirst,' Last=',FLast,' PriorCount=',PriorCount,' NextCount=',NextCount]);
506 if FCur>=0 then begin
507 DbgOut('ValuesAt: ');
508 for i:=1-PriorCount to NextCount do begin
509 p:=GetAtomAt(i);
510 DbgOut(' '+dbgs(i)+'='+dbgs(p.StartPos)+'-'+dbgs(p.EndPos));
511 end;
512 DebugLn('');
513 end;
514 end;
515
516 procedure TAtomRing.ConsistencyCheck;
517
518 procedure E(Msg: string);
519 begin
520 WriteDebugReport;
521 Msg:='TAtomRing.ConsistencyCheck: '+Msg;
522 debugln('ERROR: ',Msg);
523 RaiseCatchableException(Msg);
524 end;
525
526 var
527 i, Next: Integer;
528 begin
529 if FSize<2 then exit;
530 if FSize<>FMask+1 then E('invalid FMask');
531 if (FCur<-1) or (FCur>FMask) then E('invalid FCur');
532 if (FFirst<-1) or (FFirst>FMask) then E('invalid FFirst');
533 if (FLast<-1) or (FLast>FMask) then E('invalid FLast');
534 if FCur<0 then begin
535 if FFirst<>FCur then E('FFirst<>FCur');
536 if FLast<>FCur then E('FLast<>FCur');
537 end else begin
538 if FFirst<0 then E('FFirst<0');
539 if FLast<0 then E('FLast<0');
540 if FFirst<=FLast then begin
541 if FCur<FFirst then E('FCur<FFirst<=FLast');
542 if FCur>FLast then E('FCur>FLast>=FFirst');
543 end else begin
544 if (FCur>FLast) and (FCur<FFirst) then E('FLast<FCur<FFirst');
545 end;
546 i:=FFirst;
547 repeat
548 if FItems[i].StartPos>=FItems[i].EndPos then begin
549 if (i=FLast) and (FItems[i].StartPos=FItems[i].EndPos)
550 and (FItems[i].StartPos>SrcLen) then
551 // src end
552 else if (i=FFirst) and (FItems[i].StartPos=FItems[i].EndPos)
553 and (FItems[i].StartPos<1) then
554 // src start
555 else
556 E('StartPos>=EndPos at '+IntToStr(i));
557 end;
558 if i=FLast then break;
559 Next:=(i+1) and FMask;
560 if FItems[i].EndPos>FItems[Next].StartPos then E('FItems['+IntToStr(i)+'].EndPos>FItems['+IntToStr(Next)+'].StartPos');
561 i:=Next;
562 until false;
563 end;
564 end;
565
566 { TAtomList }
567
TAtomList.GetItemsnull568 function TAtomList.GetItems(Index: integer): TAtomPosition;
569 begin
570 Result:=FItems[Index];
571 end;
572
573 procedure TAtomList.SetCapacity(const AValue: integer);
574 begin
575 if FCapacity=AValue then exit;
576 FCapacity:=AValue;
577 if FItems<>nil then begin
578 if FCapacity>0 then begin
579 ReallocMem(FItems,SizeOf(TAtomPosition)*FCapacity);
580 end else begin
581 FreeMem(FItems);
582 FItems:=nil;
583 end;
584 end else begin
585 if FCapacity>0 then
586 GetMem(FItems,SizeOf(TAtomPosition)*FCapacity);
587 end;
588 end;
589
590 procedure TAtomList.SetItems(Index: integer; const AValue: TAtomPosition);
591 begin
592 FItems[Index]:=AValue;
593 end;
594
595 procedure TAtomList.Grow;
596 begin
597 Capacity:=Capacity*2+10;
598 end;
599
600 procedure TAtomList.Add(NewAtom: TAtomPosition);
601 begin
602 if FCount=FCapacity then Grow;
603 inc(FCount);
604 Items[Count-1]:=NewAtom;
605 end;
606
607 procedure TAtomList.Clear;
608 begin
609 FCount:=0;
610 Capacity:=0;
611 end;
612
613 constructor TAtomList.Create;
614 begin
615 inherited Create;
616 end;
617
618 destructor TAtomList.Destroy;
619 begin
620 Clear;
621 inherited Destroy;
622 end;
623
624 end.
625
626