Uninteractive code generator

[Cortys]

Implement an uninteractive code generator which gets a user request (task and parameters) and generates a code snippet that fulfills that request.

[Cortys]

Feature branch for this issue: code-generator

Weekly status update: Added support for code snippets to the library modeling submodule. This includes:

• Additions and restructurings in the concept model
• Scrape caching
• A control flow graph DSL for use in scrape configs to describe code patterns.

[Cortys]

Weekly status update: Started with the implementation of pattern injection as a new type of action during the code search. The current implementation does however not support the completion of incomplete calls with missing callables yet. This will be worked on next.

[Cortys]

Weekly status update: Implemented basic call completion. This uses a recursive placeholder matching algorithm to find a set of candidate completions for incomplete calls. While the matcher already performs deep matching, only shallow placeholder replacement is currently used.

Next steps: Extend the call completion implementation so that it performs proper deep replacement of placeholders. This will be an important milestone for the generation of valid control flow graphs (CFGs). After that I plan to extend the generator with support for optionals and user input to allow for the generation of useful CFGs. After that the conversion of CFGs to executable code strings can begin.

[Cortys]

Weekly status update:

• Completed the recursive placeholder matcher. Callables, parameters and results are now matched and completed during search.
• Optimized most of the in-memory database queries during search. Previously many queries were written in Datalog, which does however have a significant constant overhead per query in its current implementation. For few queries this overhead is not relevant, since the generator however queries the database multiple times for each considered control flow graph, this caused a significant slowdown. Now all the queries on hot code paths are reimplemented using hand-optimized routines that directly access the database indices. This improved performance by a factor of ~20.
• Added basic caching to the placeholder matcher since this is one of the most expensive operations in each search step. Currently each incomplete call is cached separately. This could be improved even further by sharing computed completion candidates between similar incomplete calls that share a common origin pattern.

Next steps: Some minor edge cases are still open for the call completion. After those are handled, I plan to add support for optional parameters and to tweak the search heuristics to be suitable for at least the scikit clustering use case.

If time permits, I will then start with the implementation of the inverse parser, that will convert CFGs to Python code.

These steps were already schedules for this week but were delayed due to the optimizations I worked on. Those optimizations were necessary because initial tests showed that the previous implementation was insufficient for real world use cases.

[Cortys]

Weekly status update:

• Completed the call completion implementation. The remaining edge cases are now handled.
• Added support for optional parameters. The generator will now try to leave them out if the user did not provide suitable information to fill them.
• Various cleanups and restructurings of the generator. Most notably the monolithic librarian.generator.core namespace was split up into separate modules for every action type and the cost computation.
• Strengthened the spec validators for scraped basetypes. Now only recognized basetypes of the applied language/ecosystem are allowed.
• Started working on an improved search heuristic for the A search. For performance reasons the generator now uses a weighted A variant with a cost model that encodes a probability distribution over all possible CFGs (i.e. the cheapest CFG is the most probable one).
• Started documenting the cost/heuristic model of the generator to make the codebase more accessible, since the implementation is not entirely intuitive for performance reasons.

Next steps: Complete the new search heuristic. Then start implementing the reverse parser (already a week late, due to conceptual problems in the old search heuristic approach that had to be figured out first).

[Cortys]

Weekly status update:

• Completed the implementation of the new search heuristic. The generator now chooses a near optimal path for simple problems and correctly discards most suboptimal paths after one or two steps along them.
• Extended the language model: Introduced the notion of a constant, which replaces call-values. Constants are interpreted as single-instance datatypes of themselves. This allows the existing type-matcher to automatically fill in constant values into enum-typed parameters.
• Implemented a new optimizer for commutative actions. Previously only remove actions were optimized via their commutativity and completeness properties. Since receive actions are "mostly" commutative (not all permutations are allowed during search but all permutations would result in the same CFG if they were allowed) they can also be optimized if their incompleteness is handled. Now both action types are optimized via a single extensible pipeline. Actions can register their specific commutative behavior and are then automatically optimized. The new optimizer drastically improves search speed, since duplicate equivalent CFG states are now identified and thus don't have to be searched multiple times.
• The generator is developed interactively in a REPL and uses a collection of custom functions for visualization and debugging of the CFGs that are considered during search. Various improvements to those tools were made.
• Various code cleanups.
• Started working on the CFG to code converter.

Next steps: Implement the CFG to code converter and integrate a semantic type compatibility measure in the cost model.

[Cortys]

Weekly status update:

• Implemented a basic CFG to Python converter.
• Improved various aspects of the generator: Code cleanups, removed redundancy and improved consistency of the action implementation.

Next steps:

• Integrate a semantic type compatibility measure in the cost model.
• Develop a first model for interactive code generation. This is necessary for the integration of the generator into IDA, since required and optional parameters are only known once the search has started and the search can only be completed once values for those parameters are given. A purely uninteractive code generator, as it is right now, is thus not usable in IDA.

[Cortys]

Weekly status update:

• Reconsidered the previous cost heuristic since it did not perform well in more realistic scenarios. A new approach was developed and implemented. Previously the search would get stuck if multiple parameter values were given by the user. This is now handled properly. The cost heuristic now uses a much more accurate best-case model that no longer simply sums up the expected cost caused by each flaw individually but instead looks at the interplay of all flaws. This reduces the search time drastically. The key idea was to lower bound the total parameter flaw cost by log((n+1)!) where n is the number of parameter flaws.
• Compatibly typed callables (used by the call action type) are now cached for increased performance. This change replaced the last remaining Datalog query on a hot code path with a more performant direct index access implementation.
• Various other minor cleanups and improvements. Not really noteworthy.

Next steps: Integrate the generator into the existing IDA chatbot as a POC to show that it actually works.

[Cortys]

Weekly status update:

• Implemented a basic integration of the new code generator into IDA. This integration is mostly complete. There are however some stability issues caused by the Python integration library that is currently used. This needs to be changed.
• Various other minor improvements and cleanups.

Next steps: Finalize the generator and get it merged.

[Cortys]

Final update: Completed the integration of the code generation into IDA. Also fixed the stability issues the code executor was having when running as part of ida-ws.

The PR for this feature is #164.