How does one fix an interval collision?

[eschulte]

Hi,

When trying to replace a call with the called function (minimal example at the bottom of this issue) I'm getting interval collisions. I see that this error is external and looks like there should be some way for the user to catch and handle the error, but I couldn't find anything on this in the documentation. Is there a general way to catch and handle these errors? If not what do you recommend one do to move around code within a program based on functional-trees as attempted below?

Thanks!

A simple.c example program.

#include <stdio.h>

void run(char* text){
  puts(text);
}

int main(){
  run("Hello");
}

A function to replace a call with the body of the called function.

(defgeneric in-line (program call-ast)
  (:documentation "Inline the function from PROGRAM called at CALL-AST.")
  (:method ((program C) (call-ast c-call-expression))
    ;; 1. Find the definition AST.
    ;; 2. Rebind the variables with the arguments to the call.
    ;; 3. Replace the function call with the body with rebound variables.
    (with-attr-table program
      (let ((declaration-ast            ; (1)
              (first (get-declaration-asts :function (call-function call-ast)))))
        (setf (@ program call-ast)       ; (3)
              (reduce (lambda (ast pair) ; (2)
                        (destructuring-bind (function-parameter . call-value) pair
                          (if (equal ast function-parameter)
                              call-value
                              ast)))
                      (mapcar #'cons
                              (mapcar (op (first (identifiers _)))
                                      (function-parameters declaration-ast))
                              (call-arguments call-ast))
                      :initial-value (copy (function-body declaration-ast))))))))

The results of attempting the replacement on this simple example.

(defparameter simple
  (from-file (make-instance 'c)
             (asdf/system:system-relative-pathname :re-line "simple.c")))
;; #<C simple.c>
(defparameter call-ast (@ simple '(2 2 0 0)))
;; #<C-CALL-EXPRESSION 2321036 :TEXT "run(\"Hello\")">
(in-line (copy-tree simple) call-ast)
;; Interval collision: [14,19] intersects [2,19]
;;    [Condition of type FUNCTIONAL-TREES/INTERVAL-TREES:INTERVAL-COLLISION-ERROR]
;;
;; Restarts:
;;  0: [RETRY] Retry SLIME REPL evaluation request.
;;  1: [*ABORT] Return to SLIME's top level.
;;  2: [ABORT] abort thread (#<THREAD "repl-thread" RUNNING {7020C70003}>)
;;
;; Backtrace:
;;   0: (FUNCTIONAL-TREES/INTERVAL-TREES::COLLISION #<(2 19) CHILDREN NIL NIL> 14 19 #<unused argument>)
;;   1: (FUNCTIONAL-TREES/INTERVAL-TREES:ITREE-INSERT #<1=>NIL,[2,19]=>CHILDREN> 14 19 CHILDREN)
;;   2: (FUNCTIONAL-TREES/INTERVAL-TREES:ITREE-ADD-INTERVALS #<unavailable argument> (((1 . 1)) ((14 . 19) CHILDREN) ((20 . 20) CHILDREN) ((21 . 21) CHILDREN) ((22 . 25) CHILDREN) ((26 . 27) CHILDREN)))
;;   3: ((:METHOD FUNCTIONAL-TREES::COMPUTE-DESCENDANT-MAP (NODE NODE)) #<C-TRANSLATION-UNIT 1 :TEXT "#include <stdio.h>"> #<C-TRANSLATION-UNIT 1 :TEXT "#include <stdio.h>">) [fast-method]
;;   4: ((SB-PCL::EMF COPY) #<unused argument> #<unused argument> #<C-TRANSLATION-UNIT 1 :TEXT "#include <stdio.h>"> :STORED-HASH NIL :CHILDREN (#<C-PREPROC-INCLUDE 2 :TEXT "#include <stdio.h>"> #<SOFTWARE-EV..
;;   ...

[eschulte]

@pfdietz did you see this issue?

[jaruchti]

Hey Eric,

I missed this until now, but I think you might want the following instead:

(defgeneric in-line (program call-ast)                                                                                                                                                                   
  (:documentation "Inline the function from PROGRAM called at CALL-AST.")                                                                                                                                          
  (:method ((program C) (call-ast c-call-expression))                                                                                                                                                              
    ;; 1. Find the definition AST.                                                                                                                                                                                 
    ;; 2. Rebind the variables with the arguments to the call.                                                                                                                                                     
    ;; 3. Replace the function call with the body with rebound variables.                                                                                                                                          
    (with-attr-table program                                                                                                                                                               
      (let ((declaration-ast            ; (1)                                                                                                                                                                      
              (first (get-declaration-asts :function (call-function call-ast)))))                                                                                                                                  
        (setf (@ program call-ast)       ; (3)                                                                                                                                                                     
              (reduce (lambda (ast pair) ; (2)                                                                                                                                                                     
                        (destructuring-bind (function-parameter . call-value) pair                                                                                                                                 
                          (if (equal ast function-parameter)                                                                                                                                                       
                              (tree-copy call-value)                                                                                                                                                               
                              (tree-copy ast))))                                                                                                                                                                   
                      (mapcar #'cons                                                                                                                                                                               
                              (mapcar (op (first (identifiers _)))                                                                                                                                                 
                                      (function-parameters declaration-ast))                                                                                                                                       
                              (call-arguments call-ast))                                                                                                                                                           
                      :initial-value (copy (function-body declaration-ast))))))))
#<COMMON-LISP:STANDARD-GENERIC-FUNCTION IN-LINE #x3020045FA7AF>                                                                                                                                                    
SEL/SW/C> (in-line simple call-ast)
#<C-COMPOUND-STATEMENT 61 :TEXT "{⏎  p"> 

These interval issues usually come up when re-inserting an AST into a tree where it already exists. I thought we were checking for this automatically, but I guess this isn't working or isn't implemented, so an explicit tree-copy to create new serial numbers on the AST is needed 🤷