10 ms·

Show HN: Compile-time HTML parsing in C++14

175 points by rep_movsd 9y ago

tlb 9y ago
Wow. How does one debug complex constexpr code? I assume there's no printf. It'd be really cool if it supported some kind of interpolation, like Jinja templates, so it could generate dynamic page templates at compile time.
- rep_movsd 9y ago
  constexpr is a subset of what you can do at runtime. So my way of debugging is #define constexpr Which makes all the code plain code that executes at runtime, then you can put your couts and use your debuggers. Its orders of magnitude simpler than dealing with template meta-programming. constexpr_printf is the feature I want most of all. There is actually a patch for gcc that implements this. I dont know how Jinja works, but the idea here is you do templating at runtime, but your templates get compiled down to a tree like DS at compiletime
  - dom0 9y ago
    Jinja compiles to Python which is then compiled to CPython bytecode and executed by the CPython VM.
    - rep_movsd 9y ago
      I see - here the compile time data structure is converted into a tree at runtime and rendered. I decided to use a runtime DS to allow things like splicing and looping templates etc. It's also possible to make the runtime render the compiled time DS directly, which should be even faster if your requirements are simple enough
- Jeaye 9y ago
  Often times, the easiest way to debug complex template code is to intentionally fail the compilation, with a minimal context, so you can read the compiler's output on what the types and values are. Here's a simple example of a function I used to use: template <typename T, typename ...Ts> void show_types() { static_assert((T*)nullptr, "Type log"); } int main() { show_types<int, float, bool>(); } When trying to compile this, using something like `g++ show-type.cpp`, you'll get this output: show-type.cpp: In instantiation of ‘void show_types() [with T = int; Ts = {float, bool}]’: show-type.cpp:7:32: required from here show-type.cpp:3:3: error: static assertion failed: Type log { static_assert((T*)nullptr, "Type log"); } The same can be done for non-type template args, of course.
  - ubadair 9y ago
    I prefer this: T::asdfasdf(); Although I might start using yours.
- ehliu 9y ago
  https://github.com/saarraz/static-print https://github.com/saarraz/static-print (not mine) is a compiler patch that adds the kind of print you're looking for
- VHRanger 9y ago
  In Dlang, where compile time function execution is the norm, you use the equivalent of what would be "pragma printf" -- eg. You embed compiler warnings into your compile time branching to debug.
  - mhh__ 9y ago
    One can also just static assert with a ctfe-able message.
cletus 9y ago
I have nothing to add other than that's both cool and scary.
- rep_movsd 9y ago
  Nothing is as scary as boost :) This is as scary as a bunny painted in camouflage.
  - MrMorden 9y ago
    I don't know what's scarier: that I used the Boost preprocessor library a few months ago; or that the file format I had to deal with sucked the stars out of the sky in such a manner that a reasonable person could have agreed that BOOST_PP was the best possible choice under the circumstances.
kbenson 9y ago
The program will fail to compile if the HTML is malformed By malformed are we talking about incorrectly closed, or actual invalid HTML? HTML doesn't require all tags be closed...
- rep_movsd 9y ago
  The HTML that browsers accept is loosely defined The HTML specification has a grammar and defines whats allowed - a subset/derivation of XHTML/SGML and their ilk There are a bunch of test template files in the test/ folder that demonstrate what kinds of errors are caught.
  - lucideer 9y ago
    > The HTML that browsers accept is loosely defined This has changed since the advent of the HTML5 specification, the primary purpose of which was to retroactively describe existing browser HTML parsing behaviours and to document and specify them comprehensively in all of their complexity. The wisdom of this abominably complex approach may be questionable, but it's certainly no longer "loosely" defined. I'd be curious as to whether this implements HTML5...
    - taeric 9y ago
      I remember the promise of xhmtl and the sad reality that, by and large, nobody actually cared about well formed documents. The specification allowing for "implicit" tags is something that just doesn't make any bloody sense to me. It feels like someone looked at all warnings in a compiler and said, I'll just explicitly define exactly how I want each warning to behave, so that it is no longer dangerous behavior.
      - tannhaeuser 9y ago
        HTML always had tag omission and "self-closing" elements - these are features from its SGML roots. A formal SGML grammar for modern W3C HTML 5.1 can be found at [1] (my project). [1]: http://sgmljs.net/blog/blog1701.html http://sgmljs.net/blog/blog1701.html
mhh__ 9y ago
For reference: In D, you could just take a HTML parser then run it at compile time without writing any new code.
- reikonomusha 9y ago
  Likewise in Common Lisp, arguably much more easily.
  - systems 9y ago
    how ... macros?
    - stevelosh 9y ago
      Vanilla macros are one option. (defmacro html (string) (some-html-parser-library:parse string)) Or you could use a function and a compiler macro to make it more of an optimization -- if the argument is known at compile-time just parse it then, otherwise wait til runtime: (defun html (string) (some-html-parser-library:parse string)) (define-compiler-macro html (&whole form string) (if (constantp string) `',(some-html-parser-library:parse string) form)) Actual example, using `string-upcase` to stand in for an HTML parsing library: (defun html (string) (string-upcase string)) (define-compiler-macro html (&whole form string) (if (constantp string) `',(string-upcase string) form)) (defun foo (arg) (print (html arg)) (print (html "compile-time")) nil) (foo "run-time") ; "RUN-TIME" ; "COMPILE-TIME" (disassemble 'foo) ; disassembly for FOO ; Size: 128 bytes. Origin: #x10106A207D ; 7D: 498B4C2460 MOV RCX, [R12+96] ; thread.binding-stack-pointer ; no-arg-parsing entry point ; 82: 48894DF8 MOV [RBP-8], RCX ; 86: 488D5C24F0 LEA RBX, [RSP-16] ; 8B: 4883EC18 SUB RSP, 24 ; 8F: 488B55F0 MOV RDX, [RBP-16] ; 93: 488B0576FFFFFF MOV RAX, [RIP-138] ; #<SB-KERNEL:FDEFN HTML> ; 9A: B902000000 MOV ECX, 2 ; 9F: 48892B MOV [RBX], RBP ; A2: 488BEB MOV RBP, RBX ; A5: FF5009 CALL QWORD PTR [RAX+9] ; A8: 480F42E3 CMOVB RSP, RBX ; AC: 488D5C24F0 LEA RBX, [RSP-16] ; B1: 4883EC18 SUB RSP, 24 ; B5: 488B055CFFFFFF MOV RAX, [RIP-164] ; #<SB-KERNEL:FDEFN COMMON-LISP:PRINT> ; BC: B902000000 MOV ECX, 2 ; C1: 48892B MOV [RBX], RBP ; C4: 488BEB MOV RBP, RBX ; C7: FF5009 CALL QWORD PTR [RAX+9] ; CA: 488D5C24F0 LEA RBX, [RSP-16] ; CF: 4883EC18 SUB RSP, 24 ; D3: 488B1546FFFFFF MOV RDX, [RIP-186] ; "COMPILE-TIME" ; DA: 488B0537FFFFFF MOV RAX, [RIP-201] ; #<SB-KERNEL:FDEFN COMMON-LISP:PRINT> ; E1: B902000000 MOV ECX, 2 ; E6: 48892B MOV [RBX], RBP ; E9: 488BEB MOV RBP, RBX ; EC: FF5009 CALL QWORD PTR [RAX+9] ; EF: BA17001020 MOV EDX, 537919511 ; F4: 488BE5 MOV RSP, RBP ; F7: F8 CLC ; F8: 5D POP RBP ; F9: C3 RET ; FA: 0F0B10 BREAK 16 ; Invalid argument count trap `html` is only called once, to handle the call that isn't known at compile time.
Iv 9y ago
After going through several love-hate cycles in my career toward C++ I must say I have a kind of admiration for what the C++ authors are trying to achieve. It took me a while to understand why every iteration of C++ brings so many (often Turing-complete or close) side effect horrors. The reason is that C++ is more than a language: it is part of an actually philosophical quest that language design is about. It is about trying to bridge the language of the machines and the language of human abstractions as closely as possible. In itself it does not necessarily lead to the best language possible, but it explores an interesting limit. One can use higher level languages like Haskel, Prolog or even a bit lower like Ruby or Python and code nice abstractions. By doing so, however, the programmer typically loses track of what the machine implementation will be. C++ strives to be a language where you can still feel what the machine will actually implement while you code high-level abstractions. That is their goal, that is their quest. In doing so there are many side-effects that pop up, but their effort is commendable. That so many people still use it is impressive but, I think, irrelevant to the priorities they typically set.
- pcwalton 9y ago
  > The reason is that C++ is more than a language: it is part of an actually philosophical quest that language design is about. > It is about trying to bridge the language of the machines and the language of human abstractions as closely as possible. In itself it does not necessarily lead to the best language possible, but it explores an interesting limit. > C++ strives to be a language where you can still feel what the machine will actually implement while you code high-level abstractions. This has been false ever since the earliest days of ANSI C. The C and C++ standards define an abstract machine that is quite far from any machine that exists today. Type-based aliasing rules, to name one important example, are something that has almost nothing to do with anything that exists in the hardware. It's quite enlightening to read the description of LLVM IR [1] and observe how far it is from anything a machine does. In fact, LLVM IR is quite a bit lower level than C is, as memory is untyped in LLVM IR without metadata: this is not at all the case in C. In reality, C++ is an attempt to build a high-level language on top of the particular abstract virtual machine specification that happened to be the accidental byproduct of a consensus process among hardware/compiler vendors in 1989. It turns out that this has been a very helpful endeavor for a lot of people, but I don't think we should claim that it's anything more than that. There's nothing "philosophically" interesting about the C89 virtual machine. [1]: https://llvm.org/docs/LangRef.html https://llvm.org/docs/LangRef.html
Mmrnmhrm 9y ago
I am very disappointed with constexpr in C++14 and C++17. The work shown here is impressive, but the point is that it should not be. D has shown that variable initialization at compile time can be painless. The main limitations I find are: a) Lack of support in the standard library (e.g., you should code your own sort, vector class, etc.) b) Terrible Terrible Terrible compilation times. c) Lack of a dynamic memory allocation within constexpr. constexpr functions are not evaluated while parsing (e.g., the code is not compiled and then executed). My use case, which was to avoid a 1 second preprocessing time while loading a library, took more than 20 minutes to compile and used more than 60 GB of RAM (on GCC7, CLANG did not even manage to compile). Stuff like initializing a bitset can easily eat all your ram (e.g. this fails to compile): #include <bitset> int main() { std::bitset<102410241024> bs; } https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63728 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63728
- rep_movsd 9y ago
  It's coming soon, as always. A lot of the STL is already being constexpr-ized (as Stephen T Lavalej has mentioned) This code i wrote takes about 5 seconds on gcc and 1.5 seconds on clang to compile for a 1000 node HTML template (about 28 KB). Definitely slow, but not really really slow. I have a feeling recursion slows down the compile time, I will attempt an iteration based version eventually and see.
setzer22 9y ago
Sadly, the thing that stood out the most to me is the sentence We attempt to make the compiler generate the most sensible error message, followed by an incomprehensible error message completely unrelated to the problem. C++ should really get proper metaprogramming, with support for user-defined error messages. All this template stuff always seemed like an awful hack to me: Fighting the compiler instead of being the compiler.
- rep_movsd 9y ago
  It is a hack, but what else is there eh? Going from templates to constexpr is like moving from a war zone to a forest. It's still scary and dark, but at least you know what hit you. static_printf is coming soon. The error message looks incomprehensible, but the last couple of lines give you enough information - the error string and the line number - it looks much better on the console since its colorized
  - avar 9y ago
    > It is a hack, but what else is there eh? The non-hacky way to do this sort of thing in both C and C++ is to just use less clever two-phase compilation as part of your build process. I.e. you'd have your template compiler extract the HTML from your source (or more easily, dedicated template files), parse, validate and compile them. The end result of that would then be embedded in your binary somehow. The gettext set of tools are a good example how how this works in another related domain. You extract strings from your program, they and the contents of corresponding .po files are validated, then compiled to efficient .mo binary files for runtime use.
    - rep_movsd 9y ago
      Why rely on an external tool? All someone has to do here is #include my header and write their templates with a small suffix and prefix. No need to install, configure, script and so on. Your argument is similar to saying "Why should an IDE parse your code and underline errors? We can run make everytime" Another advantage of my approach is that you have access to the parsed template as a data structure - that you can compose or modify as you wish. The only other way to do this is to parse at runtime - which is definitely slower

175 points by rep_movsd 9y ago

tlb 9y ago

Wow. How does one debug complex constexpr code? I assume there's no printf. It'd be really cool if it supported some kind of interpolation, like Jinja templates, so it could generate dynamic page templates at compile time.

rep_movsd 9y ago
constexpr is a subset of what you can do at runtime. So my way of debugging is #define constexpr Which makes all the code plain code that executes at runtime, then you can put your couts and use your debuggers. Its orders of magnitude simpler than dealing with template meta-programming. constexpr_printf is the feature I want most of all. There is actually a patch for gcc that implements this. I dont know how Jinja works, but the idea here is you do templating at runtime, but your templates get compiled down to a tree like DS at compiletime
- dom0 9y ago
  Jinja compiles to Python which is then compiled to CPython bytecode and executed by the CPython VM.
  - rep_movsd 9y ago
    I see - here the compile time data structure is converted into a tree at runtime and rendered. I decided to use a runtime DS to allow things like splicing and looping templates etc. It's also possible to make the runtime render the compiled time DS directly, which should be even faster if your requirements are simple enough
Jeaye 9y ago
Often times, the easiest way to debug complex template code is to intentionally fail the compilation, with a minimal context, so you can read the compiler's output on what the types and values are. Here's a simple example of a function I used to use: template <typename T, typename ...Ts> void show_types() { static_assert((T*)nullptr, "Type log"); } int main() { show_types<int, float, bool>(); } When trying to compile this, using something like `g++ show-type.cpp`, you'll get this output: show-type.cpp: In instantiation of ‘void show_types() [with T = int; Ts = {float, bool}]’: show-type.cpp:7:32: required from here show-type.cpp:3:3: error: static assertion failed: Type log { static_assert((T*)nullptr, "Type log"); } The same can be done for non-type template args, of course.
- ubadair 9y ago
  I prefer this: T::asdfasdf(); Although I might start using yours.
ehliu 9y ago
https://github.com/saarraz/static-print https://github.com/saarraz/static-print (not mine) is a compiler patch that adds the kind of print you're looking for
VHRanger 9y ago
In Dlang, where compile time function execution is the norm, you use the equivalent of what would be "pragma printf" -- eg. You embed compiler warnings into your compile time branching to debug.
- mhh__ 9y ago
  One can also just static assert with a ctfe-able message.

cletus 9y ago

I have nothing to add other than that's both cool and scary.

rep_movsd 9y ago
Nothing is as scary as boost :) This is as scary as a bunny painted in camouflage.
- MrMorden 9y ago
  I don't know what's scarier: that I used the Boost preprocessor library a few months ago; or that the file format I had to deal with sucked the stars out of the sky in such a manner that a reasonable person could have agreed that BOOST_PP was the best possible choice under the circumstances.

kbenson 9y ago

The program will fail to compile if the HTML is malformed By malformed are we talking about incorrectly closed, or actual invalid HTML? HTML doesn't require all tags be closed...

rep_movsd 9y ago
The HTML that browsers accept is loosely defined The HTML specification has a grammar and defines whats allowed - a subset/derivation of XHTML/SGML and their ilk There are a bunch of test template files in the test/ folder that demonstrate what kinds of errors are caught.
- lucideer 9y ago
  > The HTML that browsers accept is loosely defined This has changed since the advent of the HTML5 specification, the primary purpose of which was to retroactively describe existing browser HTML parsing behaviours and to document and specify them comprehensively in all of their complexity. The wisdom of this abominably complex approach may be questionable, but it's certainly no longer "loosely" defined. I'd be curious as to whether this implements HTML5...
  - taeric 9y ago
    I remember the promise of xhmtl and the sad reality that, by and large, nobody actually cared about well formed documents. The specification allowing for "implicit" tags is something that just doesn't make any bloody sense to me. It feels like someone looked at all warnings in a compiler and said, I'll just explicitly define exactly how I want each warning to behave, so that it is no longer dangerous behavior.
    - tannhaeuser 9y ago
      HTML always had tag omission and "self-closing" elements - these are features from its SGML roots. A formal SGML grammar for modern W3C HTML 5.1 can be found at [1] (my project). [1]: http://sgmljs.net/blog/blog1701.html http://sgmljs.net/blog/blog1701.html

mhh__ 9y ago

For reference: In D, you could just take a HTML parser then run it at compile time without writing any new code.

reikonomusha 9y ago
Likewise in Common Lisp, arguably much more easily.
- systems 9y ago
  how ... macros?
  - stevelosh 9y ago
    Vanilla macros are one option. (defmacro html (string) (some-html-parser-library:parse string)) Or you could use a function and a compiler macro to make it more of an optimization -- if the argument is known at compile-time just parse it then, otherwise wait til runtime: (defun html (string) (some-html-parser-library:parse string)) (define-compiler-macro html (&whole form string) (if (constantp string) `',(some-html-parser-library:parse string) form)) Actual example, using `string-upcase` to stand in for an HTML parsing library: (defun html (string) (string-upcase string)) (define-compiler-macro html (&whole form string) (if (constantp string) `',(string-upcase string) form)) (defun foo (arg) (print (html arg)) (print (html "compile-time")) nil) (foo "run-time") ; "RUN-TIME" ; "COMPILE-TIME" (disassemble 'foo) ; disassembly for FOO ; Size: 128 bytes. Origin: #x10106A207D ; 7D: 498B4C2460 MOV RCX, [R12+96] ; thread.binding-stack-pointer ; no-arg-parsing entry point ; 82: 48894DF8 MOV [RBP-8], RCX ; 86: 488D5C24F0 LEA RBX, [RSP-16] ; 8B: 4883EC18 SUB RSP, 24 ; 8F: 488B55F0 MOV RDX, [RBP-16] ; 93: 488B0576FFFFFF MOV RAX, [RIP-138] ; #<SB-KERNEL:FDEFN HTML> ; 9A: B902000000 MOV ECX, 2 ; 9F: 48892B MOV [RBX], RBP ; A2: 488BEB MOV RBP, RBX ; A5: FF5009 CALL QWORD PTR [RAX+9] ; A8: 480F42E3 CMOVB RSP, RBX ; AC: 488D5C24F0 LEA RBX, [RSP-16] ; B1: 4883EC18 SUB RSP, 24 ; B5: 488B055CFFFFFF MOV RAX, [RIP-164] ; #<SB-KERNEL:FDEFN COMMON-LISP:PRINT> ; BC: B902000000 MOV ECX, 2 ; C1: 48892B MOV [RBX], RBP ; C4: 488BEB MOV RBP, RBX ; C7: FF5009 CALL QWORD PTR [RAX+9] ; CA: 488D5C24F0 LEA RBX, [RSP-16] ; CF: 4883EC18 SUB RSP, 24 ; D3: 488B1546FFFFFF MOV RDX, [RIP-186] ; "COMPILE-TIME" ; DA: 488B0537FFFFFF MOV RAX, [RIP-201] ; #<SB-KERNEL:FDEFN COMMON-LISP:PRINT> ; E1: B902000000 MOV ECX, 2 ; E6: 48892B MOV [RBX], RBP ; E9: 488BEB MOV RBP, RBX ; EC: FF5009 CALL QWORD PTR [RAX+9] ; EF: BA17001020 MOV EDX, 537919511 ; F4: 488BE5 MOV RSP, RBP ; F7: F8 CLC ; F8: 5D POP RBP ; F9: C3 RET ; FA: 0F0B10 BREAK 16 ; Invalid argument count trap `html` is only called once, to handle the call that isn't known at compile time.

Iv 9y ago

After going through several love-hate cycles in my career toward C++ I must say I have a kind of admiration for what the C++ authors are trying to achieve. It took me a while to understand why every iteration of C++ brings so many (often Turing-complete or close) side effect horrors. The reason is that C++ is more than a language: it is part of an actually philosophical quest that language design is about. It is about trying to bridge the language of the machines and the language of human abstractions as closely as possible. In itself it does not necessarily lead to the best language possible, but it explores an interesting limit. One can use higher level languages like Haskel, Prolog or even a bit lower like Ruby or Python and code nice abstractions. By doing so, however, the programmer typically loses track of what the machine implementation will be. C++ strives to be a language where you can still feel what the machine will actually implement while you code high-level abstractions. That is their goal, that is their quest. In doing so there are many side-effects that pop up, but their effort is commendable. That so many people still use it is impressive but, I think, irrelevant to the priorities they typically set.

pcwalton 9y ago
> The reason is that C++ is more than a language: it is part of an actually philosophical quest that language design is about. > It is about trying to bridge the language of the machines and the language of human abstractions as closely as possible. In itself it does not necessarily lead to the best language possible, but it explores an interesting limit. > C++ strives to be a language where you can still feel what the machine will actually implement while you code high-level abstractions. This has been false ever since the earliest days of ANSI C. The C and C++ standards define an abstract machine that is quite far from any machine that exists today. Type-based aliasing rules, to name one important example, are something that has almost nothing to do with anything that exists in the hardware. It's quite enlightening to read the description of LLVM IR [1] and observe how far it is from anything a machine does. In fact, LLVM IR is quite a bit lower level than C is, as memory is untyped in LLVM IR without metadata: this is not at all the case in C. In reality, C++ is an attempt to build a high-level language on top of the particular abstract virtual machine specification that happened to be the accidental byproduct of a consensus process among hardware/compiler vendors in 1989. It turns out that this has been a very helpful endeavor for a lot of people, but I don't think we should claim that it's anything more than that. There's nothing "philosophically" interesting about the C89 virtual machine. [1]: https://llvm.org/docs/LangRef.html https://llvm.org/docs/LangRef.html

Mmrnmhrm 9y ago

I am very disappointed with constexpr in C++14 and C++17. The work shown here is impressive, but the point is that it should not be. D has shown that variable initialization at compile time can be painless. The main limitations I find are: a) Lack of support in the standard library (e.g., you should code your own sort, vector class, etc.) b) Terrible Terrible Terrible compilation times. c) Lack of a dynamic memory allocation within constexpr. constexpr functions are not evaluated while parsing (e.g., the code is not compiled and then executed). My use case, which was to avoid a 1 second preprocessing time while loading a library, took more than 20 minutes to compile and used more than 60 GB of RAM (on GCC7, CLANG did not even manage to compile). Stuff like initializing a bitset can easily eat all your ram (e.g. this fails to compile): #include <bitset> int main() { std::bitset<102410241024> bs; } https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63728 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63728

rep_movsd 9y ago
It's coming soon, as always. A lot of the STL is already being constexpr-ized (as Stephen T Lavalej has mentioned) This code i wrote takes about 5 seconds on gcc and 1.5 seconds on clang to compile for a 1000 node HTML template (about 28 KB). Definitely slow, but not really really slow. I have a feeling recursion slows down the compile time, I will attempt an iteration based version eventually and see.

setzer22 9y ago

Sadly, the thing that stood out the most to me is the sentence We attempt to make the compiler generate the most sensible error message, followed by an incomprehensible error message completely unrelated to the problem. C++ should really get proper metaprogramming, with support for user-defined error messages. All this template stuff always seemed like an awful hack to me: Fighting the compiler instead of being the compiler.

rep_movsd 9y ago
It is a hack, but what else is there eh? Going from templates to constexpr is like moving from a war zone to a forest. It's still scary and dark, but at least you know what hit you. static_printf is coming soon. The error message looks incomprehensible, but the last couple of lines give you enough information - the error string and the line number - it looks much better on the console since its colorized
- avar 9y ago
  > It is a hack, but what else is there eh? The non-hacky way to do this sort of thing in both C and C++ is to just use less clever two-phase compilation as part of your build process. I.e. you'd have your template compiler extract the HTML from your source (or more easily, dedicated template files), parse, validate and compile them. The end result of that would then be embedded in your binary somehow. The gettext set of tools are a good example how how this works in another related domain. You extract strings from your program, they and the contents of corresponding .po files are validated, then compiled to efficient .mo binary files for runtime use.
  - rep_movsd 9y ago
    Why rely on an external tool? All someone has to do here is #include my header and write their templates with a small suffix and prefix. No need to install, configure, script and so on. Your argument is similar to saying "Why should an IDE parse your code and underline errors? We can run make everytime" Another advantage of my approach is that you have access to the parsed template as a data structure - that you can compose or modify as you wish. The only other way to do this is to parse at runtime - which is definitely slower