KiCad PCB EDA Suite
Loading...
Searching...
No Matches
libeval_compiler.h
Go to the documentation of this file.
1/*
2 This file is part of libeval, a simple math expression evaluator
3
4 Copyright (C) 2007 Michael Geselbracht, [email protected]
5 Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <https://www.gnu.org/licenses/>.
19*/
20
21#pragma once
22
23#include <cstddef>
24#include <functional>
25#include <map>
26#include <optional>
27#include <string>
28#include <stack>
29
31
32#include <kicommon.h>
33#include <base_units.h>
34#include <eda_units.h>
35#include <wx/intl.h>
36
37#if defined(WIN32)
38// This gets leaked by python headers on MSVC only and will cause chaos
39#undef COMPILER
40#endif
41
42#define TR_OP_BINARY_MASK 0x200
43#define TR_OP_UNARY_MASK 0x100
44
45#define TR_OP_MUL 0x201
46#define TR_OP_DIV 0x202
47#define TR_OP_ADD 0x203
48#define TR_OP_SUB 0x204
49#define TR_OP_LESS 0x205
50#define TR_OP_GREATER 0x206
51#define TR_OP_LESS_EQUAL 0x207
52#define TR_OP_GREATER_EQUAL 0x208
53#define TR_OP_EQUAL 0x209
54#define TR_OP_NOT_EQUAL 0x20a
55#define TR_OP_BOOL_AND 0x20b
56#define TR_OP_BOOL_OR 0x20c
57#define TR_OP_BOOL_NOT 0x100
58#define TR_OP_FUNC_CALL 24
59#define TR_OP_METHOD_CALL 25
60#define TR_UOP_PUSH_VAR 1
61#define TR_UOP_PUSH_VALUE 2
62
63// Short-circuit jumps for && / ||. They peek (do not pop) the left-hand result already on the
64// stack and, when it already decides the boolean, jump past the right-hand operand's microcode so
65// it is never executed. This is the compile-time pruning the SSA-style evaluator performs.
66// The opcodes deliberately sit outside both TR_OP_UNARY_MASK and TR_OP_BINARY_MASK so they are
67// never misclassified as arithmetic operators by a mask test.
68#define TR_OP_JZ 0x401 // jump if top == 0 (left side of &&)
69#define TR_OP_JNZ 0x402 // jump if top != 0 (left side of ||)
70
71// This namespace is used for the lemon parser
72namespace LIBEVAL
73{
74
75class COMPILER;
76
83
92
93
103
116
117class UOP;
118class UCODE;
119class CONTEXT;
120class VAR_REF;
121
122typedef std::function<void( CONTEXT*, void* )> FUNC_CALL_REF;
123
125{
126 wxString* str;
127 double num;
128 int idx;
129};
130
131// Lemon can't handle c'tors and d'tors, so we provide a poor-man's version.
132constexpr T_TOKEN_VALUE defaultTokenValue = { nullptr, 0.0, 0 };
133
134
140
141// Lemon can't handle c'tors and d'tors, so we provide a poor-man's version.
143
144
146{
147public:
149
150 int op;
153 bool valid;
157
158 void SetUop( int aOp, double aValue, EDA_UNITS aUnits );
159 void SetUop( int aOp, const wxString& aValue, bool aStringIsWildcard );
160 void SetUop( int aOp, std::unique_ptr<VAR_REF> aRef = nullptr );
161 void SetUop( int aOp, FUNC_CALL_REF aFunc, std::unique_ptr<VAR_REF> aRef = nullptr );
162};
163
164
165TREE_NODE* newNode( LIBEVAL::COMPILER* compiler, int op,
166 const T_TOKEN_VALUE& value = defaultTokenValue );
167
169{
170public:
172 {
173 }
174
176 {
177 }
178
179 virtual const std::vector<wxString>& GetSupportedUnits() const
180 {
181 static const std::vector<wxString> nullUnits;
182
183 return nullUnits;
184 }
185
186
187 virtual const std::vector<EDA_UNITS>& GetSupportedUnitsTypes() const
188 {
189 static const std::vector<EDA_UNITS> nullUnits;
190
191 return nullUnits;
192 }
193
194 virtual wxString GetSupportedUnitsMessage() const
195 {
196 return wxEmptyString;
197 }
198
199 virtual double Convert( const wxString& aString, int unitType ) const
200 {
201 return 0.0;
202 }
203};
204
205
207{
208public:
212 m_valueDbl( 0 ),
213 m_stringIsWildcard( false ),
214 m_stringIsLiteral( false ),
215 m_isDeferredDbl( false ),
216 m_isDeferredStr( false )
217 {}
218
219 VALUE( const wxString& aStr, bool aIsWildcard = false, bool aIsLiteral = true ) :
220 m_type( VT_STRING ),
222 m_valueDbl( 0 ),
223 m_valueStr( aStr ),
224 m_stringIsWildcard( aIsWildcard ),
225 m_stringIsLiteral( aIsLiteral ),
226 m_isDeferredDbl( false ),
227 m_isDeferredStr( false )
228 {}
229
230 VALUE( const double aVal ) :
233 m_valueDbl( aVal ),
234 m_stringIsWildcard( false ),
235 m_stringIsLiteral( false ),
236 m_isDeferredDbl( false ),
237 m_isDeferredStr( false )
238 {}
239
241 {
242 VALUE* v = new VALUE();
243 v->m_type = VT_NULL;
244 return v;
245 }
246
247 virtual ~VALUE() = default;
248
249 virtual double AsDouble() const
250 {
251 if( m_isDeferredDbl )
252 {
254 m_isDeferredDbl = false;
255 }
256
257 return m_valueDbl;
258 }
259
260 virtual const wxString& AsString() const
261 {
262 if( m_isDeferredStr )
263 {
265 m_isDeferredStr = false;
266 }
267
268 return m_valueStr;
269 }
270
271 virtual bool EqualTo( CONTEXT* aCtx, const VALUE* b ) const;
272
273 // NB: this is not an inverse of EqualTo as they both return false for undefined values.
274 virtual bool NotEqualTo( CONTEXT* aCtx, const VALUE* b ) const;
275
276 VAR_TYPE_T GetType() const { return m_type; };
277
278 void Set( double aValue )
279 {
281 m_valueDbl = aValue;
282 }
283
284 void SetDeferredEval( INPLACE_FUNCTION<double()> aLambda )
285 {
287 m_lambdaDbl = std::move( aLambda );
288 m_isDeferredDbl = true;
289 }
290
291 void SetDeferredEval( INPLACE_FUNCTION<wxString()> aLambda )
292 {
294 m_lambdaStr = std::move( aLambda );
295 m_isDeferredStr = true;
296 }
297
298 void Set( const wxString& aValue )
299 {
301 m_valueStr = aValue;
302 }
303
304 void Set( const VALUE &val )
305 {
306 m_type = val.m_type;
310 m_units = val.m_units;
311
312 if( m_type == VT_STRING )
314 }
315
316 void SetUnits( const EDA_UNITS aUnits ) { m_units = aUnits; }
317
318 EDA_UNITS GetUnits() const { return m_units; }
319
320 bool StringIsWildcard() const { return m_stringIsWildcard; }
321
322 bool StringIsLiteral() const { return m_stringIsLiteral; }
323
324private:
327 mutable double m_valueDbl; // mutable to support deferred evaluation
328 mutable wxString m_valueStr; // mutable to support deferred evaluation
329
334 mutable bool m_isDeferredDbl;
335 mutable bool m_isDeferredStr;
336
337};
338
340{
341public:
343 {}
344
345 virtual ~VAR_REF() = default;
346
347 virtual VAR_TYPE_T GetType() const = 0;
348 virtual VALUE* GetValue( CONTEXT* aCtx ) = 0;
349};
350
351
353{
354public:
355 struct STACK_OVERFLOW {};
356
357 using ERROR_CALLBACK = std::function<void( const wxString& aMessage, int aOffset )>;
358
359 static constexpr int STACK_CAPACITY = 100;
360
362 m_stack(),
363 m_stackPtr( 0 ),
364 m_inlineUsed( 0 )
365 {
366 m_ownedValues.reserve( 8 );
367 }
368
369 virtual ~CONTEXT()
370 {
372 }
373
374 // We own at least one list of raw pointers. Don't let the compiler fill in copy c'tors that
375 // will only land us in trouble.
376 CONTEXT( const CONTEXT& ) = delete;
377 CONTEXT& operator=( const CONTEXT& ) = delete;
378
385 virtual void Reset()
386 {
387 for( std::size_t i = 0; i < m_inlineUsed; ++i )
388 inlineValue( i )->~VALUE();
389
390 m_inlineUsed = 0;
391
392 for( VALUE* v : m_ownedValues )
393 delete v;
394
395 m_ownedValues.clear();
396 m_stackPtr = 0;
397 m_errorCallback = nullptr;
398 }
399
401 {
402 // Serve the first values from an inline buffer so the hot DRC evaluation path stays off
403 // the heap; only deeper expressions spill to individual allocations.
405 {
406 // Advance the count only after construction so a throwing VALUE() never leaves the
407 // destructor to tear down an uninitialized slot.
408 VALUE* value = new( inlineValue( m_inlineUsed ) ) VALUE();
409 ++m_inlineUsed;
410 return value;
411 }
412
413 m_ownedValues.emplace_back( new VALUE );
414 return m_ownedValues.back();
415 }
416
418 {
419 m_ownedValues.emplace_back( aValue );
420 return m_ownedValues.back();
421 }
422
423 void Push( VALUE* aValue )
424 {
427
428 m_stack[ m_stackPtr++ ] = aValue;
429 }
430
432 {
433 if( m_stackPtr == 0 )
434 {
435 ReportError( _( "Malformed expression" ) );
436 return AllocValue();
437 }
438
439 return m_stack[ --m_stackPtr ];
440 }
441
444 {
445 if( m_stackPtr == 0 )
446 {
447 ReportError( _( "Malformed expression" ) );
448 return AllocValue();
449 }
450
451 return m_stack[ m_stackPtr - 1 ];
452 }
453
454 int SP() const
455 {
456 return m_stackPtr;
457 };
458
461 {
462 m_stackPtr = 0;
463 }
464
466 {
467 m_errorCallback = std::move( aCallback );
468 }
469
472 {
473 m_errorCallback.swap( aCallback );
474 return aCallback;
475 }
476
477 bool HasErrorCallback() { return m_errorCallback != nullptr; }
478
479 void ReportError( const wxString& aErrorMsg );
480
481private:
482 static constexpr std::size_t INLINE_VALUE_COUNT = 32;
483
484 [[noreturn]] void stackOverflow();
485
486 VALUE* inlineValue( std::size_t aIndex )
487 {
488 return reinterpret_cast<VALUE*>( m_inlineStorage ) + aIndex;
489 }
490
491 std::vector<VALUE*> m_ownedValues;
492 VALUE* m_stack[STACK_CAPACITY]; // std::stack not performant enough
494
495 alignas( VALUE ) unsigned char m_inlineStorage[INLINE_VALUE_COUNT * sizeof( VALUE )];
496 std::size_t m_inlineUsed;
497
499};
500
501
503{
504public:
506 {}
507
508 virtual ~UCODE();
509
510 // We own at least one list of raw pointers. Don't let the compiler fill in copy c'tors that
511 // will only land us in trouble.
512 UCODE( const UCODE& ) = delete;
513 UCODE& operator=( const UCODE& ) = delete;
514
515 void AddOp( UOP* uop )
516 {
517 m_ucode.push_back(uop);
518 }
519
521 void MarkHasJumps() { m_hasJumps = true; }
522
524 int GetSize() const { return static_cast<int>( m_ucode.size() ); }
525
526 VALUE* Run( CONTEXT* ctx );
527 wxString Dump() const;
528
529 virtual std::unique_ptr<VAR_REF> CreateVarRef( const wxString& var, const wxString& field )
530 {
531 return nullptr;
532 }
533
534 virtual FUNC_CALL_REF CreateFuncCall( const wxString& name )
535 {
536 return nullptr;
537 }
538
539protected:
540 std::vector<UOP*> m_ucode;
541 bool m_hasJumps = false; // any short-circuit jumps? lets Run() skip the jump loop
542};
543
544
546{
547public:
548 UOP( int op, std::unique_ptr<VALUE> value ) :
549 m_op( op ),
550 m_ref(nullptr),
551 m_value( std::move( value ) )
552 {}
553
554 UOP( int op, std::unique_ptr<VAR_REF> vref ) :
555 m_op( op ),
556 m_ref( std::move( vref ) ),
557 m_value(nullptr)
558 {}
559
560 UOP( int op, FUNC_CALL_REF func, std::unique_ptr<VAR_REF> vref = nullptr ) :
561 m_op( op ),
562 m_func( std::move( func ) ),
563 m_ref( std::move( vref ) ),
564 m_value(nullptr)
565 {}
566
568 explicit UOP( int op ) :
569 m_op( op ),
570 m_ref( nullptr ),
571 m_value( nullptr )
572 {}
573
574 virtual ~UOP() = default;
575
578 int Exec( CONTEXT* ctx );
579
580 void SetJumpTarget( int aTarget ) { m_jumpTarget = aTarget; }
581
582 wxString Format() const;
583
584private:
585 int m_op;
586 int m_jumpTarget = -1;
587
589 std::unique_ptr<VAR_REF> m_ref;
590 std::unique_ptr<VALUE> m_value;
591};
592
594{
595public:
596 void Restart( const wxString& aStr )
597 {
598 m_str = aStr;
599 m_pos = 0;
600 }
601
602 void Clear()
603 {
604 m_str = "";
605 m_pos = 0;
606 }
607
608 int GetChar( size_t aOffset = 0 ) const
609 {
610 if( m_pos + aOffset >= m_str.length() )
611 return 0;
612
613 return m_str[m_pos + aOffset];
614 }
615
616 bool Done() const
617 {
618 return m_pos >= m_str.length();
619 }
620
621 void NextChar( int aAdvance = 1 )
622 {
623 m_pos += aAdvance;
624 }
625
626 size_t GetPos() const
627 {
628 return m_pos;
629 }
630
631 wxString GetString();
632
633 wxString GetChars( const std::function<bool( wxUniChar )>& cond ) const;
634
635 bool MatchAhead( const wxString& match,
636 const std::function<bool( wxUniChar )>& stopCond ) const;
637
638private:
639 wxString m_str;
640 size_t m_pos = 0;
641};
642
643
645{
646public:
647 COMPILER();
648 virtual ~COMPILER();
649
650 // We own at least one list of raw pointers. Don't let the compiler fill in copy c'tors that
651 // will only land us in trouble.
652 COMPILER( const COMPILER& ) = delete;
653 COMPILER& operator=( const COMPILER& ) = delete;
654
655 /*
656 * clear() should be invoked by the client if a new input string is to be processed. It
657 * will reset the parser. User defined variables are retained.
658 */
659 void Clear();
660
661 /* Used by the lemon parser */
662 void parseError( const char* s );
663 void parseOk();
664
665 int GetSourcePos() const { return m_sourcePos; }
666
667 void setRoot( LIBEVAL::TREE_NODE *root );
668 void freeTree( LIBEVAL::TREE_NODE *tree );
669
670 bool Compile( const wxString& aString, UCODE* aCode, CONTEXT* aPreflightContext );
671
672 void SetErrorCallback( std::function<void( const wxString& aMessage, int aOffset )> aCallback )
673 {
674 m_errorCallback = std::move( aCallback );
675 }
676
677 bool IsErrorPending() const { return m_errorStatus.pendingError; }
678 const ERROR_STATUS& GetError() const { return m_errorStatus; }
679
680 void GcItem( TREE_NODE* aItem ) { m_gcItems.push_back( aItem ); }
681 void GcItem( wxString* aItem ) { m_gcStrings.push_back( aItem ); }
682
683protected:
685 {
688 };
689
691
692 bool generateUCode( UCODE* aCode, CONTEXT* aPreflightContext );
693
694 void reportError( COMPILATION_STAGE stage, const wxString& aErrorMsg, int aPos = -1 );
695
696 /* Begin processing of a new input string */
697 void newString( const wxString& aString );
698
699 /* Tokenizer: Next token/value taken from input string. */
701 bool lexDefault( T_TOKEN& aToken );
702 bool lexString( T_TOKEN& aToken );
703
704 int resolveUnits();
705
706protected:
707 /* Token state for input string. */
708 void* m_parser; // the current lemon parser state machine
711
712 std::unique_ptr<UNIT_RESOLVER> m_unitResolver;
713
717
718 std::function<void( const wxString& aMessage, int aOffset )> m_errorCallback;
719
721
722 std::vector<TREE_NODE*> m_gcItems;
723 std::vector<wxString*> m_gcStrings;
724};
725
726
734KICOMMON_API std::optional<wxString> EscapeStringLiteral( const wxString& aText );
735
736
737} // namespace LIBEVAL
738
const char * name
A std::function-style callable wrapper that stores the target in a fixed inline buffer and never allo...
void SetErrorCallback(std::function< void(const wxString &aMessage, int aOffset)> aCallback)
bool IsErrorPending() const
std::unique_ptr< UNIT_RESOLVER > m_unitResolver
void newString(const wxString &aString)
void GcItem(wxString *aItem)
bool lexString(T_TOKEN &aToken)
void GcItem(TREE_NODE *aItem)
COMPILER(const COMPILER &)=delete
bool generateUCode(UCODE *aCode, CONTEXT *aPreflightContext)
std::function< void(const wxString &aMessage, int aOffset)> m_errorCallback
bool lexDefault(T_TOKEN &aToken)
std::vector< TREE_NODE * > m_gcItems
void reportError(COMPILATION_STAGE stage, const wxString &aErrorMsg, int aPos=-1)
const ERROR_STATUS & GetError() const
COMPILER & operator=(const COMPILER &)=delete
std::vector< wxString * > m_gcStrings
ERROR_STATUS m_errorStatus
void parseError(const char *s)
void Push(VALUE *aValue)
std::vector< VALUE * > m_ownedValues
std::size_t m_inlineUsed
VALUE * StoreValue(VALUE *aValue)
void ReportError(const wxString &aErrorMsg)
ERROR_CALLBACK ExchangeErrorCallback(ERROR_CALLBACK aCallback)
Install a callback and return the previous one.
std::function< void(const wxString &aMessage, int aOffset)> ERROR_CALLBACK
CONTEXT(const CONTEXT &)=delete
unsigned char m_inlineStorage[INLINE_VALUE_COUNT *sizeof(VALUE)]
VALUE * inlineValue(std::size_t aIndex)
static constexpr std::size_t INLINE_VALUE_COUNT
virtual void Reset()
Release every value allocated by the previous evaluation and rewind the stack so the same CONTEXT can...
VALUE * m_stack[STACK_CAPACITY]
void SetErrorCallback(ERROR_CALLBACK aCallback)
ERROR_CALLBACK m_errorCallback
void ClearStack()
Discard operands while retaining allocated values and context settings.
CONTEXT & operator=(const CONTEXT &)=delete
VALUE * Top()
Peek the top of the stack without popping (used by the short-circuit jumps).
static constexpr int STACK_CAPACITY
int GetChar(size_t aOffset=0) const
void NextChar(int aAdvance=1)
void Restart(const wxString &aStr)
size_t GetPos() const
void SetUop(int aOp, double aValue, EDA_UNITS aUnits)
virtual std::unique_ptr< VAR_REF > CreateVarRef(const wxString &var, const wxString &field)
void AddOp(UOP *uop)
UCODE(const UCODE &)=delete
std::vector< UOP * > m_ucode
void MarkHasJumps()
Flag that this ucode contains short-circuit jumps, so Run() uses the jump-aware loop.
int GetSize() const
Index of the next op to be added (used to backpatch short-circuit jump targets).
virtual FUNC_CALL_REF CreateFuncCall(const wxString &name)
UCODE & operator=(const UCODE &)=delete
virtual wxString GetSupportedUnitsMessage() const
virtual const std::vector< EDA_UNITS > & GetSupportedUnitsTypes() const
virtual double Convert(const wxString &aString, int unitType) const
virtual const std::vector< wxString > & GetSupportedUnits() const
virtual ~UOP()=default
UOP(int op, FUNC_CALL_REF func, std::unique_ptr< VAR_REF > vref=nullptr)
std::unique_ptr< VAR_REF > m_ref
FUNC_CALL_REF m_func
UOP(int op, std::unique_ptr< VALUE > value)
int Exec(CONTEXT *ctx)
Execute the op.
UOP(int op)
Bare op (used for the short-circuit jumps, whose only payload is a jump target).
void SetJumpTarget(int aTarget)
std::unique_ptr< VALUE > m_value
UOP(int op, std::unique_ptr< VAR_REF > vref)
void Set(double aValue)
virtual const wxString & AsString() const
void SetUnits(const EDA_UNITS aUnits)
bool StringIsWildcard() const
virtual ~VALUE()=default
void Set(const wxString &aValue)
INPLACE_FUNCTION< double()> m_lambdaDbl
static VALUE * MakeNullValue()
INPLACE_FUNCTION< wxString()> m_lambdaStr
void SetDeferredEval(INPLACE_FUNCTION< wxString()> aLambda)
virtual double AsDouble() const
EDA_UNITS GetUnits() const
VAR_TYPE_T GetType() const
void Set(const VALUE &val)
VALUE(const double aVal)
bool StringIsLiteral() const
void SetDeferredEval(INPLACE_FUNCTION< double()> aLambda)
VALUE(const wxString &aStr, bool aIsWildcard=false, bool aIsLiteral=true)
virtual VALUE * GetValue(CONTEXT *aCtx)=0
virtual VAR_TYPE_T GetType() const =0
virtual ~VAR_REF()=default
#define _(s)
EDA_UNITS
Definition eda_units.h:45
#define KICOMMON_API
Definition kicommon.h:27
TREE_NODE * newNode(LIBEVAL::COMPILER *compiler, int op, const T_TOKEN_VALUE &value)
constexpr T_TOKEN defaultToken
constexpr T_TOKEN_VALUE defaultTokenValue
std::function< void(CONTEXT *, void *)> FUNC_CALL_REF
std::optional< wxString > EscapeStringLiteral(const wxString &aText)
Escape text for use between the quotes of an expression string.
STL namespace.
void Format(OUTPUTFORMATTER *out, int aNestLevel, int aCtl, const CPTREE &aTree)
Output a PTREE into s-expression format via an OUTPUTFORMATTER derivative.
Definition ptree.cpp:194
COMPILATION_STAGE stage
T_TOKEN_VALUE value
@ VALUE
Field Value of part, i.e. "3.3K".