From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id D0A867FE36 for ; Sun, 10 Jul 2016 13:51:22 +0200 (CEST) IronPort-PHdr: 9a23:Hdn6vhF8sZCbV3l1dxDnAp1GYnF86YWxBRYc798ds5kLTJ75r8ywAkXT6L1XgUPTWs2DsrQf2rKQ6PyrBTFIyK3CmUhKSIZLWR4BhJdetC0bK+nBN3fGKuX3ZTcxBsVIWQwt1Xi6NU9IBJS2PAWK8TWM5DIfUi/yKRBybrysXNWD14Lsi6vuptX6WEZhvHKFe7R8LRG7/036l/I9ps9cEJs30QbDuXBSeu5blitCLFOXmAvgtI/rpMYwuwwZgf8q9tZBXKPmZOx4COUAVHV1e1wyseLmrxWLdheI4mMZW2MQ2k5JBQbCxB73RJu0qTf9svJ40S+ce8H7G+MaQzOnuu1TRQP0hT1PHnhxzXvUh8B5iOgT9AqougZ8zoLdZKmaMfN/euXWetZMFjkJZdpYSyEUWtD0VIAIFedUeL8A94Q= Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=paurkedal@gmail.com; spf=Pass smtp.mailfrom=paurkedal@gmail.com; spf=None smtp.helo=postmaster@mail-oi0-f43.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of paurkedal@gmail.com) identity=pra; client-ip=209.85.218.43; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="paurkedal@gmail.com"; x-sender="paurkedal@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of paurkedal@gmail.com designates 209.85.218.43 as permitted sender) identity=mailfrom; client-ip=209.85.218.43; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="paurkedal@gmail.com"; x-sender="paurkedal@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-oi0-f43.google.com) identity=helo; client-ip=209.85.218.43; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="paurkedal@gmail.com"; x-sender="postmaster@mail-oi0-f43.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0DzAAC/NYJXhivaVdFdhRAGpgmHT4s4gXqGGAKBGAc5EwEBAQEBAQEBEQEBAQgLCwkhL4IyBAESAYITAQUSEQQZARsdAQMMBgULAwoCAhEVAgIiAREBBQEcBhMbB4dzAQMXogOBMT4xizuBaoJaBYUfChknDVKDSQEBAQEGAQEBARsCBhBxiXOFAIJCgloBBJkYAYw+ghOPLI5QEh6BDx8Bgj0RCxeBNzoyiXoBAQE X-IPAS-Result: A0DzAAC/NYJXhivaVdFdhRAGpgmHT4s4gXqGGAKBGAc5EwEBAQEBAQEBEQEBAQgLCwkhL4IyBAESAYITAQUSEQQZARsdAQMMBgULAwoCAhEVAgIiAREBBQEcBhMbB4dzAQMXogOBMT4xizuBaoJaBYUfChknDVKDSQEBAQEGAQEBARsCBhBxiXOFAIJCgloBBJkYAYw+ghOPLI5QEh6BDx8Bgj0RCxeBNzoyiXoBAQE X-IronPort-AV: E=Sophos;i="5.28,340,1464645600"; d="scan'208";a="184416982" Received: from mail-oi0-f43.google.com ([209.85.218.43]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 10 Jul 2016 13:51:21 +0200 Received: by mail-oi0-f43.google.com with SMTP id n8so12621318oif.3 for ; Sun, 10 Jul 2016 04:51:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=9PY8a4gohlJbvI0wCm8GQNzCqgjSAfnhZ9ilrD7ov7U=; b=wH1p8BdCOpIrxC5OOYj4xLRUnUyXFbVWkarluGxv59ErQw8cwHFkOmiqhZzZkWzYYo KLz0qRrlDm31itgcQnndEP+YKPnbwn8Dh1Fdu/FyT6zPDNtB2OjLISA1YL3jMn7gNWjC Rji2WIgZ7PLRpFv140yQH7dZIOctSmZD0towRkLotsXJFTqIjOFmH1sz5dYQSOS758qb CdXwddQhBFDL+ftZnVGiGYiTthJa5jaGe0CYlrI4BODzlTQRN/6+JlL3WuMfK9W88smt XrA8FdiP9KqKSmWTAjDBhC1WGK6v3OjyGVTP5yutG/NSYziNpReMsPTU8c37hjJqse4T Tr/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=9PY8a4gohlJbvI0wCm8GQNzCqgjSAfnhZ9ilrD7ov7U=; b=I5nqIf7I5SOxa8wxLKwG6Q2pOCgq49JDNNa7sZuCY4BGdJROdRHU+Ap2Lvl6kXKgeH t+kGJ9sAJZkc+5DstQBZVfHHnInjSLqRBMl7CUVTJCNMHkt/sN/ymKiuDJcqXE/DkoPZ s3unf7gDmvMvwAParBEOAN5iQEPJz0IoSy/Fovldcu5zhI1b6z/uTek7XgEqCzJg5hnO 8LVr4JdEdmxYUjmLaRY3ikD71RpMXH+u8A6j6ZiuRGRL3TJMllLlnY46mYQq82gcWsbC 3bhtAjU28IXkG4OMUZdop6y7aeEMEEIWvtXiaKFCjFGLrztX2orRHWqi0ust4DTBVpgp M7mw== X-Gm-Message-State: ALyK8tJ2h7I7m5UwLBzyuqVOzxH4PwCcmM+MRXGmX5Qh1aPg5jRdbz8wImbC/6WAtixERW8uJwd7izTB1yDwmQ== X-Received: by 10.202.84.67 with SMTP id i64mr7801732oib.93.1468151480008; Sun, 10 Jul 2016 04:51:20 -0700 (PDT) MIME-Version: 1.0 Received: by 10.202.228.201 with HTTP; Sun, 10 Jul 2016 04:51:19 -0700 (PDT) In-Reply-To: <1468150422.25014.75.camel@e130.lan.sumadev.de> References: <1468148606.25014.58.camel@e130.lan.sumadev.de> <1468150422.25014.75.camel@e130.lan.sumadev.de> From: "Petter A. Urkedal" Date: Sun, 10 Jul 2016 13:51:19 +0200 Message-ID: To: Gerd Stolpmann Cc: Martin DeMello , "caml-list@inria.fr" Content-Type: text/plain; charset=UTF-8 Subject: Re: [Caml-list] Is there an efficient precise ocamldep - Was: why is building ocaml hard? On 10 July 2016 at 13:33, Gerd Stolpmann wrote: > Rephrasing this question. Given we wanted to develop an improved version > of ocamldep that (a) reads in cmi files from non-project-local > directories, and (b) processes all files of the project as a whole, and > (c) outputs dependencies precisely. Is there an algorithm that is better > than > > - for all permutations p of the project files: > - env := > - for all files f of p: > - localenv := [] > - AST := parse f > - interpret the module calculus of the AST, taking env > (the toplevel modules) and localenv (the local module > scope) into account, with these details: > * if there is an unknown module identifier this is an > error, and we go on with the next permutation > * any definition of a module modifies localenv > * the "open" directive is interpreted strictly using > env and localenv > - no error yet: > - env := env + (f -> localenv) > (i.e. add the module corresponding to the file to env) > - if there is a permutation p that doesn't run into an error, > re-run the dependency analyzer for p and output the deps > between the (now unambiguously identified) toplevel modules > (the keys of env) > > I think this algorithm is a precise solution to the ocamldep problem > (well, I did not take mli files into account, but that shouldn't be too > difficult to add). However, it is horribly inefficient. Is there > anything better? I think at least we can reduce upper bound for number of iteration from n! to n(n-1)/2 by observing that once we find a module which is successfully analysed, we can keep it for the next iteration: The a pass over n local files will either succeed in finding a module which is successfully analysed, leaving n - 1 to be analysed, or fail, in which case the dependencies are unsatifiable.